用单链表实现一元多项式相加
#include<stdio.h> #include<stdlib.h> typedef struct Node{ float coef;//系数 int exp;//项数 struct Node *next; }LNode,*Linklist; void newPolynomial(Linklist &head){ LNode *p; int i,tempExp; float tempCoef; scanf("%f%d",&tempCoef,&tempExp); head=(struct Node*)malloc(sizeof(struct Node)); head->next=NULL; while(tempCoef!=0){ //当系数为0的时候停止录入数据 p=(struct Node*)malloc(sizeof(struct Node)); p->coef=tempCoef; p->exp=tempExp; p->next=head->next; head->next=p; scanf("%f%d",&tempCoef,&tempExp); } } void addupPolynomial(Linklist &p1,Linklist &p2,Linklist &sum){ Linklist temp1,temp2,tempSum; sum=(struct Node*)malloc(sizeof(struct Node)); sum->next=NULL;//新多项式的头结点 temp1=p1->next; temp2=p2->next; while(temp1!=NULL&&temp2!=NULL){ //当p1,p2多项式都没遍历完 tempSum=(struct Node*)malloc(sizeof(struct Node)); if(temp1->exp==temp2->exp){ tempSum->exp=temp1->exp; tempSum->coef=temp1->coef+temp2->coef; tempSum->next=sum->next; sum->next=tempSum; temp1=temp1->next; temp2=temp2->next; }else if(temp1->exp<temp2->exp){ tempSum->exp=temp1->exp; tempSum->coef=temp1->coef; tempSum->next=sum->next; sum->next=tempSum; temp1=temp1->next; }else{ tempSum->exp=temp2->exp; tempSum->coef=temp2->coef; tempSum->next=sum->next; sum->next=tempSum; temp2=temp2->next; } } while(temp1!=NULL){//当p1没遍历完 tempSum=(struct Node*)malloc(sizeof(struct Node)); tempSum->exp=temp1->exp; tempSum->coef=temp1->coef; tempSum->next=sum->next; sum->next=tempSum; temp1=temp1->next; } while(temp2!=NULL){//当p2没遍历完 tempSum=(struct Node*)malloc(sizeof(struct Node)); tempSum->exp=temp2->exp; tempSum->coef=temp2->coef; tempSum->next=sum->next; sum->next=tempSum; temp2=temp2->next; } } void bubbleSort(Linklist &head){ //冒泡排序 Linklist p,q,tail; tail = NULL; while((head->next->next) != tail) { p = head; q = head->next; while(q->next != tail) { if((q->exp) > (q->next->exp)) { p->next = q->next; q->next = q->next->next; p->next->next = q; q = p->next; } q = q->next; p = p->next; } tail = q; } } void printPolynomial(Linklist &head){ Linklist temp; temp=head; printf("多项式为："); while(temp->next!=NULL){ temp=temp->next; if(temp->next!=NULL){ printf("%.1fx^%d+",temp->coef,temp->exp); }else{ printf("%.1fx^%d",temp->coef,temp->exp); } } } void newPolynomial(Linklist &head); void addupPolynomial(Linklist &p1,Linklist &p2,Linklist &sum); void bubbleSort(Linklist &head); void printPolynomial(Linklist &head); int main() { Linklist L1,L2,sumL; printf("\n**************请输入第一个多项式***************\n"); newPolynomial(L1); bubbleSort(L1); printPolynomial(L1); printf("\n**************请输入第二个多项式***************\n"); newPolynomial(L2); bubbleSort(L2); printPolynomial(L2); addupPolynomial(L1,L2,sumL); bubbleSort(sumL); printf("\n相加的多项式为:"); printPolynomial(sumL); }算法的核心思想是， 先把输入的多项式，按次数从小到大排序，然后用temp1，temp2同时分别遍历两个多项式，
当temp1所指结点的次数小于temp2所指结点，取temp1所指结点作为新多项式的新项， 同时temp1前进一个节点，temp2不动； 当temp1所指结点的次数大于temp2所指结点，取temp2所指结点作为新多项式的新项， 同时temp2前进一个节点，temp1不动； 当temp1所指结点的次数等于temp2所指结点的次数，取temp1所指结点和temp2所指结点之和作为新多项式的新项，此时temp1，temp2都前进一个结点。
注意，排序是必不可少的一步 这里的排序方法采用的是冒泡排序，不懂的同鞋可以自行百度学习；
