输入格式: 输入在第一行给出第一个多项式POLYA的系数和指数，并以0,0 结束第一个多项式的输入；在第二行出第一个多项式POLYB的系数和指数，并以0,0 结束第一个多项式的输入。 输出格式： 对每一组输入，在一行中输出POLYA+POLYB和多项式的系数和指数。 输入样例: 5,0 2,1 1,6 8,15 0,0 -2,1 3,6 4,8 0,0 输出样例: 5,0 4,6 4,8 8,15
本题主要思路； 1.建立两个头指针分别为head1和head2链表，链表每一个节点分别记录每一个多项式的系数coef和指数exp. 2.preA遍历链表head1,preB遍历链表head2. 3.建立一个只有一个头节点的链表head,逐步遍历链表head1和head2.分别有如下三种情况 ①preA->expexp,将节点preA利用尾插法插入链表head。 ②preB->expexp,将节点preB利用尾插法插入链表head. ③preB->exp=preA->exp,这种情况分为两种 当preA->coef+preB->coef=0时： 释放节点preA和preB. 当preA->coef+preB->coef≠0时： 将多项式系数相同的项的指数相加，记录在preA,并利用尾插法将preA节点插如链表head.
一、建立结构题和宏定义类型名，代码如下
typedef int DataType; struct Node { DataType coef; DataType exp; struct Node* next; }; typedef struct Node *PNode; typedef struct Node *LinkList;二、建立链表头节点和建立完整链表函数，该链表的头节点的值为空，尾节点的指针为NULL,建立链表方式为尾插法，代码如下
LinkList SetNullList_Link() { LinkList head = (LinkList)malloc(sizeof(struct Node)); if (head != NULL) head->next = NULL; else printf("alloc failure"); return head; } void CreateList(struct Node* head) { DataType coef,exp; PNode p = NULL; PNode q = head; scanf("%d,%d", &coef,&exp); while (coef!=0) { p = (struct Node*)malloc(sizeof(struct Node)); p->coef = coef; p->exp = exp; p->next=NULL; q->next=p; q=p; scanf("%d,%d", &coef,&exp); } }三、对链表进行冒泡排序，指数小的在前面，指数大的在后面，代码如下
void MoveMaxToTail (LinkList head) { PNode pre,q; int tcoef,texp; for(pre=head->next;pre->next!=NULL;pre=pre->next) for(q=pre->next;q!=NULL;q=q->next) { if(q->exp<pre->exp) { tcoef=pre->coef; texp=pre->exp; pre->coef=q->coef; pre->exp=q->exp; q->coef=tcoef; q->exp=texp; } } }四、该函数为本题重点，形参分别为两个多项式对应链表，函数返回值为新链表的头指针，代码如下
LinkList PolynomialAddition(LinkList head1,LinkList head2) { PNode preA=head1->next,qA=preA->next; free(head1); PNode preB=head2->next,qB=preB->next; free(head2); PNode head = (LinkList)malloc(sizeof(struct Node)); head->next=NULL; PNode pre=head; while(preA!=NULL&&preB!=NULL)//当链表链表有一个遍历到表尾时结束 { if(preA->exp<preB->exp)//当满足条件时，将preA节点插入新链表 { preA->next=pre->next; pre->next=preA; preA=qA; if(preB==NULL) continue; qA=qA->next; pre=pre->next; } else if(preB->exp<preA->exp)//当满足条件时，将preB插入新链表 { preB->next=pre->next; pre->next=preB; preB=qB; pre=pre->next; if(preB==NULL) continue; qB=qB->next; } else if(preA->coef+preB->coef==0)//当满足条件，书房preA和preB { free(preA); preA=qA; if(preA!=NULL) qA=qA->next; free(preB); preB=qB; if(preB!=NULL) qB=qB->next; } else//当preA->coef+preB->coef≠0时 { preA->coef=preB->coef+preA->coef; preA->next=pre->next; pre->next=preA; preA=qA; if(preA!=NULL) qA=qA->next; pre=pre->next; free(preB); preB=qB; if(preB!=NULL) qB=qB->next; } }//当循环结束时，两条链表遍历不一定就此结束，以为链表长度不一定相同，所以要进行以下操作 //将链表中未遍历的部分直接接入新链表 if(preA!=NULL) pre->next=preA; else pre->next=preB; return head; }五、打印链表，代码如下
void print(LinkList head) { LinkList p; p=head->next; while(p!=NULL) { printf("%d,%d ",p->coef,p->exp); p=p->next; } }六、主函数如下
int main() { LinkList head1; LinkList head2; LinkList head; head1=SetNullList_Link(); head2=SetNullList_Link(); CreateList(head1); CreateList(head2); MoveMaxToTail (head1); MoveMaxToTail (head2); head=PolynomialAddition(head1,head2); print(head); return 0; }输入输出示例
