Question

!!!高分,几个数据结构题目，求答案，高分!!!

1,一元多项式计算
任务，能够按照指数降序排列建立并输出多项式，能够完成两个多项式的相加相减运算，并输出结果。

2，建立二叉树，层序，中序遍历（不能用递归）
任务，要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列。
要求，分别建立二叉树存储结构的输入函数，输出层序遍历的函数。

3.两个4*4二维数组的求和
任务，要求数组初始化由键盘输入，并保证结果正确输出。

以上只要能满足要求任务即可，不用太考虑功能的圆满，以及界面的友好性，最好能给出源程序。

调试通过，立刻送分，尽量三个都做
感谢高手们，急，速度解答！！！！！！！！！！！！
4 楼的用得C++？ 还是用C吧 ，C++不熟~~~
另外，怕被抄袭，可以发到邮箱去
lqdwater@163.com

Answer 1

我直接给你个整合版的，运行通过了。

#include<stdio.h>
#include<stdlib.h>
#include<dos.h>
#include<conio.h>
#include<malloc.h>
#define MAX 4
typedef struct
{
float coef; //系数
int expn; //指数
}term;

typedef struct LNode
{
term data; //term多项式值
struct LNode *next;
}LNode,*LinkList;

typedef LinkList polynomail;

/*比较指数*/
int cmp(term a,term b)
{
if(a.expn>b.expn)
return 1;
if(a.expn==b.expn)
return 0;
if(a.expn<b.expn)
return -1;
else exit(-2);
}

/*又小到大排列*/
void arrange(polynomail pa)
{
polynomail h=pa,p,q,r;
if(pa==NULL)
exit(-2);
for(p=pa;p->next!=NULL;p=p->next);
r=p;
for(h=pa;h->next!=r;)//大的沉底
{
for(p=h;p->next!=r&&p!=r;p=p->next)
if(cmp(p->next->data,p->next->next->data)==1)
{
q=p->next->next;
p->next->next=q->next;
q->next=p->next;
p->next=q;
}
r=p;//r指向参与比较的最后一个，不断向前移动
}
}

/*打印多项式,求项数*/
int printpolyn(polynomail P)
{
int i;
polynomail q;
if(P==NULL)
printf("无项！\n");
else if(P->next==NULL)
printf("Y=0\n");
else
{
printf("该多项式为Y=");q=P->next;i=1;
if(q->data.coef!=0&&q->data.expn!=0)
{
printf("%.2fX^%d",q->data.coef,q->data.expn);
i++;
}
if(q->data.expn==0&&q->data.coef!=0)
printf("%.2f",q->data.coef);//打印第一项
q=q->next;
if(q==NULL)
{printf("\n");return 1;}

while(1)//while中，打印剩下项中系数非零的项，
{ //同时，指数为零的项只输出系数，系数为负的不输出+号
if(q->data.coef!=0&&q->data.expn!=0)
{
if(q->data.coef>0)
printf("+");
printf("%.2fX^%d",q->data.coef,q->data.expn);
i++;
}
if(q->data.expn==0&&q->data.coef!=0)
{
if(q->data.coef>0)
printf("+");
printf("%.2f",q->data.coef);
}
q=q->next;
if(q==NULL)
{
printf("\n");
break;
}
}
}
return 1;
}

/*1、创建并初始化多项式链表*/
polynomail creatpolyn(polynomail P,int m)
{
polynomail r,q,p,s,Q;
int i;
P=(LNode*)malloc(sizeof(LNode));
r=P;
printf("请依次输入多项式的系数和指数：(例如:想输入3X^2+4X^3,则输入3 2 4 3)");
for(i=0;i<m;i++)
{
s=(LNode*)malloc(sizeof(LNode));
scanf("%f%d",&s->data.coef,&s->data.expn);
r->next=s;
r=s;
}
r->next=NULL;
arrange(P);
if(P->next->next!=NULL)
{
for(q=P->next;q!=NULL/*&&q->next!=NULL*/;q=q->next)//合并同类项
for(p=q->next,r=q;p!=NULL;)
if(q->data.expn==p->data.expn)
{
q->data.coef=q->data.coef+p->data.coef;
r->next=p->next;
Q=p;p=p->next;
free(Q);
}
else
{
r=r->next;
p=p->next;
}
}
return P;
}

/*2、两多项式相加*/
polynomail addpolyn(polynomail pa,polynomail pb)
{
polynomail s,newp,q,p,r;
p=pa->next;q=pb->next;
newp=(LNode*)malloc(sizeof(LNode));
r=newp;
while(p&&q)
{
s=(LNode*)malloc(sizeof(LNode));
switch(cmp(p->data,q->data))
{
case -1:
s->data.coef=p->data.coef;
s->data.expn=p->data.expn;
r->next=s;
r=s;
p=p->next;
break;
case 0:
s->data.coef=p->data.coef+q->data.coef;
if(s->data.coef!=0.0)
{
s->data.expn=p->data.expn;
r->next=s;
r=s;
}
p=p->next;
q=q->next;
break;
case 1:
s->data.coef=q->data.coef;
s->data.expn=q->data.expn;
r->next=s;
r=s;
q=q->next;
break;
}//switch
}//while
/*if(p!=NULL)
r->next=p;
else
if(q!=NULL)
r->next=q;
else
r->next=NULL;*/ //这样不行，q，p为局部变量，传不到主函数中去
while(p)
{
s=(LNode*)malloc(sizeof(LNode));
s->data.coef=p->data.coef;
s->data.expn=p->data.expn;
r->next=s;
r=s;
p=p->next;
}
while(q)
{
s=(LNode*)malloc(sizeof(LNode));
s->data.coef=q->data.coef;
s->data.expn=q->data.expn;
r->next=s;
r=s;
q=q->next;
}
r->next=NULL;
for(q=newp->next;q->next!=NULL;q=q->next)//合并同类项
for(p=q;p!=NULL&&p->next!=NULL;p=p->next)
if(q->data.expn==p->next->data.expn)
{
q->data.coef=q->data.coef+p->next->data.coef;
r=p->next;
p->next=p->next->next;
free(r);
}
return newp;
}

/*3、两多项式相减*/
polynomail subpolyn(polynomail pa,polynomail pb)
{
polynomail s,newp,q,p,r,Q;
p=pa->next;q=pb->next;
newp=(LNode*)malloc(sizeof(LNode));
r=newp;
while(p&&q)
{
s=(LNode*)malloc(sizeof(LNode));
switch(cmp(p->data,q->data))
{
case -1:
s->data.coef=p->data.coef;
s->data.expn=p->data.expn;
r->next=s;
r=s;
p=p->next;
break;
case 0:
s->data.coef=p->data.coef-q->data.coef;
if(s->data.coef!=0.0)
{
s->data.expn=p->data.expn;
r->next=s;
r=s;
}
p=p->next;
q=q->next;
break;
case 1:
s->data.coef=-q->data.coef;
s->data.expn=q->data.expn;
r->next=s;
r=s;
q=q->next;
break;
}//switch
}//while
while(p)
{
s=(LNode*)malloc(sizeof(LNode));
s->data.coef=p->data.coef;
s->data.expn=p->data.expn;
r->next=s;
r=s;
p=p->next;
}
while(q)
{
s=(LNode*)malloc(sizeof(LNode));
s->data.coef=-q->data.coef;
s->data.expn=q->data.expn;
r->next=s;
r=s;
q=q->next;
}
r->next=NULL;
if(newp->next!=NULL&&newp->next->next!=NULL)//合并同类项
{
for(q=newp->next;q!=NULL;q=q->next)
for(p=q->next,r=q;p!=NULL;)
if(q->data.expn==p->data.expn)
{
q->data.coef=q->data.coef+p->data.coef;
r->next=p->next;
Q=p;p=p->next;
free(Q);
}
else
{
r=r->next;
p=p->next;
}
}
return newp;
}

/*4、销毁已建立的两个多项式*/
void delpolyn(polynomail pa,polynomail pb)
{
polynomail p,q;
p=pa;
while(p!=NULL)
{
q=p;
p=p->next;
free(q);
}
p=pb;
while(p!=NULL)
{
q=p;
p=p->next;
free(q);
}
printf("两个多项式已经销毁\n");
}

void multinomial() //原第一题的主函数
{
polynomail pa=NULL,pb=NULL;
polynomail p,q;
polynomail addp=NULL,subp=NULL,mulp=NULL;
int n,m;
char sign='y';
printf("1、创建两个一元多项式\n");
printf("2、两多项式相加得一新多项式\n");
printf("3、两多项式相减得一新多项式\n");
printf("4、销毁已建立的两个多项式\n");
printf("5、退出\n");
printf("\n");
while(sign!='n')
{
printf("请选择：");
scanf("%d",&n);
switch(n)
{
case 1:
if(pa!=NULL)
{
printf("已建立两个一元多项式，请选择其他操作！");
break;
}
printf("请输入第一个多项式：\n");
printf("要输入几项：");
scanf("%d",&m);
while(m==0)
{
printf("m不能为0，请重新输入m:");
scanf("%d",&m);
}
pa=creatpolyn(pa,m);
printpolyn(pa);
printf("请输入第二个多项式：\n");
printf("要输入几项：");
scanf("%d",&m);
while(m==0)
{
printf("m不能为0，请重新输入m:");
scanf("%d",&m);
}
pb=creatpolyn(pb,m);
printpolyn(pb);
break;
case 2:
if(pa==NULL)
{
printf("请先创建两个一元多项式！\n");
break;
}
addp=addpolyn(pa,pb);
printpolyn(addp);
break;
case 3:
if(pa==NULL)
{
printf("请先创建两个一元多项式！\n");
break;
}
subp=subpolyn(pa,pb);
printpolyn(subp);
break;
case 4:
if(pa==NULL)
{
printf("请先创建两个一元多项式！\n");
break;
}
delpolyn(pa,pb);
pa=pb=NULL;
break;
case 5:
if(addp!=NULL)
{
p=addp;
while(p!=NULL)
{
q=p;
p=p->next;
free(q);
}
}
if(subp!=NULL)
{
p=subp;
while(p!=NULL)
{
q=p;
p=p->next;
free(q);
}
}
exit(-2);
}//switch
}//while
}

/*···················以上是第一题的东西·····················*/

typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
bool CreateBiTree(BiTree &T)//建立二叉树
{
char ch;
scanf("%c",&ch);//读入该结点的值
if (ch=='0') T=NULL;//若输入0，表示该结点为空
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=ch;
CreateBiTree(T->lchild);//创建该结点的左，右子树
CreateBiTree(T->rchild);
}
return 1;//返回真
}
void preorder1( BiTree b)//非递归，先序遍历
{
BiTree stack[100],p;//stack[]用来保存访问过程中的结点的指针
int top; //top指向当前的栈顶
if (b!=NULL)
{
top=1; //根结点入栈
stack[top]=b;
while (top>0) //栈不为空时循环
{
p=stack[top]; //退栈并访问该结点
top--;
printf("%c",p->data); //输出该结点的数据
if (p->rchild!=NULL) //若右孩子存在，则入栈
{
top++;
stack[top]=p->rchild;
}
if (p->lchild!=NULL) //若左孩子存在，则入栈
{
top++;
stack[top]=p->lchild;
}
}
}
}
void Inorder1(BiTree &T)//非递归，中序遍历
{
BiTree stack[100],p;//stack[]用来保存访问过程中的结点的指针
int top=0;//top指向当前的栈顶
p=T;//p首先被赋值为根结点
do
{
while (p!=NULL)//该结点不为空，则进栈
{
top++; //栈顶上移
stack[top]=p;//该结点进栈
p=p->lchild;//并开始访问该结点的左孩子
}
if (top>0)//栈不为空
{
p=stack[top];//p为栈顶元素
top--;//出栈一个元素
printf("%c",p->data);//打印该结点的数据
p=p->rchild;//访问右孩子
}
}
while ((p!=NULL)||(top!=0));
}
void postorder1( BiTree &T)//非递归，后序遍历
{
BiTree stack[100],p;//stack[]用来保存访问过程中的结点的指针
int tag[100], top=0; //tag[]表示stack[]相应的结点是否访问
p=T;
do
{
while (p!=NULL) //扫描左结点，不为空则进栈
{
top++;//栈顶上移
stack[top]=p;//该结点的指针进栈
tag[top]=0;//此结点没有被遍历，过被赋值为0
p=p->lchild;//访问左子树
} //p所指结点为无左子树的结点或其左子树已遍历过
if(top>0)
{
if(tag[top]==1)
{ // p的左右子树都访问过
printf("%c",stack[top]->data);top--;//栈顶下移，打印该结点的数据
}
else{p=stack[top];
if(top>0){p=p->rchild; tag[top]=1;}//访问结点
}
} //扫描右子树
//表示当前结点的右子树已访问过
}
while (top!=0);
}
void Translevel(BiTree T)//层序遍历
{
struct Bin
{
BiTree R[100];
int f,r;
}q;
q.f=0;
q.r=0;
if(T)
printf("%c",T->data);
q.R[q.r]=T;
q.r=q.r+1;
while(q.f<q.r)
{
T=q.R[q.f];
q.f=q.f+1;
if(T->lchild)
{
printf("%c",T->lchild->data);
q.R[q.r]=T->lchild;
q.r=q.r+1;
}
if(T->rchild)
{
printf("%c",T->rchild->data);
q.R[q.r]=T->rchild;
q.r=q.r+1;
}
}
}
void tree() //原第二题的主函数
{
char a;
BiTree T=NULL;
printf("按照先序建立二叉树,空结点输入0,非空结点输入结点数据\n");
printf("请建立二叉树:");
CreateBiTree(T); //调用创建二叉树的函数
printf("使用非递归方法实现先序输出:");
preorder1(T); //非递归先序遍历
printf("\n");

printf("使用非递归方法实现中序输出:");
Inorder1(T); //非递归中序遍历
printf("\n");

printf("使用非递归方法实现后序输出:");
postorder1(T); //非递归后序遍历
printf("\n");

printf("使用层次遍历输出:");
Translevel(T); //层序遍历
printf("\n");
printf("感谢使用，按任意键结束！"); //防止直接运行EXE时，在没看清结果前，程序已结束运行。
scanf("%c",&a);
getchar();
}

/*···················以上是第二题的东西·····················*/

void sum() //原第三题的主函数
{
int a[MAX][MAX],b[MAX][MAX],c[MAX][MAX],m,n,p,q;
char i;
printf("请输入第一个4*4的二维数组：\n");
for (m=0;m<MAX;m++)
{ for (n=0;n<MAX;n++)
{
scanf("%d",&p);
a[m][n]=p;
}
}
printf("您输入的第一个4*4的二维数组是：\n");
for (m=0;m<MAX;m++)
{ for (n=0;n<MAX;n++)
{
printf("%3d,",a[m][n]);
}
printf("\n");
}
printf("请输入第二个4*4的二维数组：\n");
for (m=0;m<MAX;m++)
{ for (n=0;n<MAX;n++)
{
scanf("%d",&q);
b[m][n]=q;
}
}
printf("您输入的第二个4*4的二维数组是：\n");
for (m=0;m<MAX;m++)
{ for (n=0;n<MAX;n++)
{
printf("%3d,",b[m][n]);
}
printf("\n");
}
for (m=0;m<MAX;m++)
{ for (n=0;n<MAX;n++)
{
c[m][n]=a[m][n]+b[m][n];
}
}
printf("经计算，您输入的两个二维数组之和为：\n");
for (m=0;m<MAX;m++)
{ for (n=0;n<MAX;n++)
{
printf("%3d,",c[m][n]);
}
printf("\n");
}
printf("\n");
printf("感谢使用，按任意键结束！"); //防止直接运行EXE时，在没看清结果前，程序已结束运行。
scanf("%c",&i);
getchar();
}

/*···················以上是第三题的东西·····················*/
void main() //完整整合版的主函数
{
int n;
printf("欢迎使用课程设计整合版");
printf("请选择您想运行的程序：\n");
printf("1.一元多项式的计算。\n");
printf("2.建立二叉树，层序，中序遍历。\n");
printf("3.两个4*4的二维数组求和。\n");
printf("4.退出。\n");
printf("\n");
printf("请选择：");
scanf("%d",&n);
switch(n)
{
case 1:multinomial();break;
case 2:tree();break;
case 3:sum();break;
case 4:printf("感谢使用，按任意键结束！");break;
}
}

Answer 2

void Layer(DataType *t) //借用队列完成二叉树的层次遍历
{
SeqQueue MySeq;
DataType *p;
MySeq.Append(t);
while (MySeq.NotEmpty( ))
{ p=MySeq.Delete( );
cout<<p->data<<" ";
if (p->Left()!=NULL) MySeq.Append(p->Left());
if (p->Right()!=NULL) MySeq.Append(p->Right());
}
}
给你一个代码！！主函数自己去编！

Answer 3

第一题
#include <cstdio>
#include <cstdlib>
#define MAX 20 //多项式最大系数
typedef struct //定义存放多项式的数组
{
float coef; //系数
int exp; //指数
}polyArray[MAX];
typedef struct pnode //定义单链表结点类型
{
float coef;
int exp;
struct pnode *next;
}polyNode;

void dispPoly(polyNode *L)//输出多项式
{
polyNode *p=L->next;
while(p!=NULL)
{
printf(" %gX^%d",p->coef ,p->exp );
p=p->next ;
}
printf("\n");
}
void createList(polyNode *&L,polyArray a ,int n)//尾插法建表
{
polyNode *s,*r;int i;
L=(polyNode *) malloc(sizeof(polyNode));//创建头结点
L->next =NULL;
r=L; //r始终指向表尾，最开始指向头结点
for(i=0;i<n;i++)
{
s=(polyNode *) malloc(sizeof(polyNode));//创建新结点
s->coef =a[i].coef ;
s->exp =a[i].exp ;
r->next =s;
r=s;
}
r->next =NULL;
}

void sort(polyNode *&head)
{
polyNode *p=head->next ,*q,*r;
if(p!=NULL) //原表有一个或以上的数据结点
{
r=p->next ; //保存p结点后继指针
p->next =NULL; // 构造只含一个数据元素的有序表
p=r;
while(p!=NULL)
{
r=p->next ;
q=head;
while(q->next!=NULL&&q->next ->exp > p->exp )
q=q->next; //在有序表中寻找这样的q :q->exp>p->exp>q->next->exp
p->next =q->next ; //将P插入到q之后
q->next =p;
p=r;
}
}
}

void add (polyNode *ha,polyNode *hb,polyNode *&hc)
{
polyNode *pa=ha->next ,*pb=hb->next ,*s,*tc;
float c;
hc=(polyNode*)malloc(sizeof(polyNode));//创建头结点
tc=hc;
while(pa!=NULL&&pb!=NULL)
{
if(pb->exp > pb->exp )
{
s=(polyNode*)malloc(sizeof(polyNode)); //复制结点
s->exp =pa->exp ;
s->coef =pa->coef ;
tc->next =s;
tc=s;
pa=pa->next;
}
else if(pa->exp <pb->exp )
{
s=(polyNode*)malloc(sizeof(polyNode)); //复制结点
s->exp =pb->exp ;
s->coef =pb->coef ;
tc->next =s;
tc=s;
pb=pb->next ;
}
else //pa->exp==pb->exp
{
c=pa->coef +pb->coef ;
if(c!=0)
{
s=(polyNode*)malloc(sizeof(polyNode)); //系数之和不为0创建新结点
s->exp =pa->exp ;
s->coef =c ;
tc->next =s;
tc=s;

}
pa=pa->next ; //若c不为0，前面已处理过；为0，也是这两条语句，直接跳过
pb=pb->next ;
}

}
if(pb!=NULL)pa=pb;//复制余下的结点,跳出while,要么pb==NULL,要么pa==NULL
while(pa!=NULL)
{
s=(polyNode*)malloc(sizeof(polyNode)); //复制结点
s->exp =pa->exp ;
s->coef =pa->coef ;
tc->next =s;
tc=s;
pa=pa->next;

}
tc->next=NULL;
}
int main()
{
polyNode *ha,*hb,*hc;
polyArray a ={{1.2,0},{-2.5,1},{3.2,3},{-2.5,5}};
polyArray b ={{-1.2,0},{2.5,1},{3.2,3},{-2.5,5},{5.4,10}};
createList(ha,a,4);
createList(hb,b,5);
printf("原多项式A:");dispPoly(ha);
printf("原多项式B:");dispPoly(hb);
sort(ha);
sort(hb);
printf("排序后多项式A:");dispPoly(ha);
printf("排序后多项式B:");dispPoly(hb);
add(ha,hb,hc);
printf("多项式相加:");dispPoly(hc);
return 0;
}
第二题
#include <cstdio>
#include <cstdlib>
#define MAXSIZE 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;

void createBTNode (BTNode *&b,char *str) //括号表示法创建二叉链
{
BTNode *st[MAXSIZE],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;//初始为空
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case'(':top++;st[top]=p;k=1;break; //为左结点
case')':top--;break;
case',':k=2;break; //为右结点
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data =ch;
p->lchild =p->rchild =NULL;
if(b==NULL) //P指向的是根结点
b=p;
else //已建立根结点
{
switch(k)
{
case 1:st[top]->lchild =p;break;
case 2:st[top]->rchild =p;break;
}
}
}
j++;
ch=str[j];
}

}

void InOrder(BTNode *b)
{
BTNode *st[MAXSIZE],*p;
int top=-1;
if(b!=NULL)
{
p=b;
while(top>-1||p!=NULL) //处理*b结点的左子树
{
while(p!=NULL) //扫描*p的所有左结点并进栈
{
top++;
st[top]=p;
p=p->lchild ;
}
if(top>-1)
{
p=st[top];
top--; //出栈*p结点
printf("%c ",p->data);
p=p->rchild ;//扫描P的右孩子结点
}
}
}
}

void travLevel(BTNode *b)//层次遍历
{
BTNode *qu[MAXSIZE]; //定义顺序环形队列
int front,rear;
front=rear=0;
if(b!=NULL)
printf("%c ",b->data );
rear++;
qu[rear]=b; //根结点进队
while(front!=rear) //队列不空则循环
{
front=(front+1)%MAXSIZE;
b=qu[front]; //队头出队列
if(b->lchild !=NULL)//输出左孩子并入队列
{
printf("%c ",b->lchild ->data );
rear=(rear+1)%MAXSIZE;
qu[rear]=b->lchild ;
}
if(b->rchild !=NULL) //输出右孩子并入队列
{
printf("%c ",b->rchild ->data );
rear=(rear+1)%MAXSIZE;
qu[rear]=b->rchild ;
}

}
}
int main()
{
BTNode *b;
createBTNode (b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("中序遍历\n");
InOrder(b);
printf("\n");
printf("层次遍历\n");
travLevel(b);
return 0;
}
第三题貌似比较简单，你自己搞定
让别人看看也无妨
VS2005调试通过，VC++应该也可以
程序应该没问题，我照书小抄一下，有什么疑问CALL我
三个多小时的劳动啊

Answer 4

我的天啊，看傻了

Answer 5

汗……
有文化的还是多

Answer 6

我很想帮你 但我看不懂。。不好意思