C++单链表实现多项式相加：代码详解与优化

#include using namespace std; typedef struct LNode { int coef; //系数 int expn; //指数 struct LNode *next; }LinkNode;

void CreateLinkR(LinkNode *&L) //尾插法存储多项式的系数和指数 { LinkNode *r,*s; L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 r=L; //r始终指向尾结点,初始时指向头结点 int n; //项数 cout<<'请输入多项式的项数'<<endl; cin>>n; for(int i=0;i<n;i++) { s=(LinkNode *)malloc(sizeof(LinkNode)); //创建数据结点s cout<<'请输入第'<<i+1<<'项的系数和指数'<<endl;
cin>>s->coef>>s->expn; //输入第一项单项式的系数和指数 r->next = s; r=s; } r->next = NULL; }

void AddLinkR(LinkNode *&L,LinkNode *&R,LinkNode *&Q) { LinkNode *r,*s,*p; L=(LinkNode *)malloc(sizeof(LinkNode)); r=L; p=R->next; //p指向R的第一项 while(p) //将R的所有项插入L中 { s=(LinkNode *)malloc(sizeof(LinkNode)); //创建数据结点s s->coef=p->coef; s->expn=p->expn; r->next=s; r=s; p=p->next; } p=Q->next; //p指向Q的第一项 while(p) //将Q的所有项与L中对应的项相加 { s=L->next; //s指向L的第一项 while(s->next && s->next->expnexpn) //找到L中第一个指数大于p的项 s=s->next; if(s->next && s->next->expn==p->expn) //如果L中存在指数相等的项 { if(s->next->coef+p->coef==0) //如果相加后系数为0，删除该项 { r=s->next; s->next=r->next; free(r); } else s->next->coef+=p->coef; //否则将系数相加 } else //如果L中不存在指数相等的项，插入新结点 { s=(LinkNode *)malloc(sizeof(LinkNode)); s->coef=p->coef; s->expn=p->expn; s->next=L->next; L->next=s; } p=p->next; } }

void PrintLink(LinkNode *L) //输出链表 { LinkNode *p=L->next; while(p) { cout<coef<<'x^'<expn; if(p->next) cout<<'+'; p=p->next; } cout<<endl; }

int main() { LinkNode *R,*Q,*L; cout<<'请输入第一个多项式:'<<endl; CreateLinkR(R); cout<<'请输入第二个多项式:'<<endl; CreateLinkR(Q); AddLinkR(L,R,Q); cout<<'相加后的多项式为:'<<endl; PrintLink(L); return 0;