第一题
#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我
三个多小时的劳动啊
参考资料:老严老李的书