用链表实现一元多项式相加、相减

以下代码的功能为用不带头结点的单向链表实现两个一元多项式的相加、相减。涉及的内容有：建立链表、复制链表、链表排序、输出链表、依据两个多项式的系数和指数的关系，对两个多项式相加减、释放链表所占的空间。 主要难点在于链表的排序和多项式相加减。

#include <bits/stdc++.h> struct node { float coefficient; //系数 int exponent; //指数 node *next; }; node *buildList(); node *copyList(node *head); node *plusList(node *head1, node *head2); node *minusList(node *head1, node *head2); void outputList(node *head); node *sort(node *head); void destroy(node *head); int main() { node *head1 = NULL; node *head2 = NULL; node *headPlus = NULL; node *headMinus = NULL; node *copyHead1 = NULL; node *copyHead2 = NULL; printf("please input list1\n"); head1 = buildList(); printf("please input list2\n"); head2 = buildList(); printf("This is list1\n"); outputList(head1); printf("This is list2\n"); outputList(head2); head1 = sort(head1); head2 = sort(head2); printf("This is list1 by sort\n"); outputList(head1); printf("This is list2 by sort\n"); outputList(head2); copyHead1 = copyList(head1); copyHead2 = copyList(head2); headPlus = plusList(head1, head2); printf("list1 plus list2\n"); outputList(headPlus); headMinus = minusList(copyHead1,copyHead2); printf("list1 minus list2\n"); outputList(headMinus); destroy(headPlus); destroy(headMinus); return 0; } node *buildList() { node *head=NULL, *p, *q; float coefficient; int exponent; scanf("%f%d", &coefficient, &exponent); if(coefficient==0 && exponent==0) return head; else { p = (node *)malloc(sizeof(node)); p->coefficient = coefficient; p->exponent = exponent; p->next = NULL; head = p; } while(scanf("%f%d", &coefficient, &exponent)&&(coefficient!=0||exponent!=0)) { q = (node *)malloc(sizeof(node)); q->coefficient = coefficient; q->exponent = exponent; p->next = q; p = q; } p->next = NULL; return head; } node *sort(node *head) { node *p, *q, *t; p = head->next; q = head; head->next = NULL; while(p != NULL) { if(p->exponent < head->exponent) { q = head; head = p; p = p->next; head->next = q; } else { node *qPre = head; node *pNext= p->next; q = head->next; while(q != NULL && (q->exponent < p->exponent)) { q = q->next; qPre = qPre->next; } if(q == NULL) { qPre->next = p; p->next = NULL; p = pNext; } else { qPre->next = p; p->next = q; p = pNext; } } } return head; } node *plusList(node *head1, node *head2) { node *headPlus, *pa, *pb, *r; pa = head1; pb = head2; int exponent; if(pa != NULL && pb != NULL) { if(pa->exponent < pb->exponent) { headPlus = pa; r = pa; pa = pa->next; } else if(pa->exponent > pb->exponent) { headPlus = pb; r = pb; pb = pb->next; } else { node *t; t = pb; pa->coefficient = pa->coefficient + pb->coefficient; headPlus = pa; r = pa; pa= pa->next; pb = pb->next; free(t); } } while(pa != NULL && pb != NULL) { if(pa->exponent < pb->exponent) { r->next = pa; r = pa; pa = pa->next; } else if(pa->exponent > pb->exponent) { r->next = pb; r = pb; pb = pb->next; } else { pa->coefficient = pa->coefficient + pb->coefficient; r->next = pa; r = pa; pa = pa->next; node *pbPre= pb; pb = pb->next; free(pbPre); } } if(pa) { r->next = pa; } else { r->next = pb; } return headPlus; } node *minusList(node *head1, node *head2) { node *p = head2; while(p != NULL) { p->coefficient = -p->coefficient; p = p->next; } p = plusList(head1, head2); return p; } void outputList(node *head) { node *p = head; int flag = 1 , haveOutput = 0; while(p != NULL) { if(p->coefficient == 0) { p = p->next; if(p == NULL && haveOutput == 0) { printf("0\n"); return ; } continue; } if(flag == 1) { printf("%f*x^%d",p->coefficient,p->exponent); haveOutput = 1; flag = 0; p = p->next; continue; } if(p->coefficient > 0) printf("+"); printf("%f*x^%d",p->coefficient,p->exponent); haveOutput = 1; p = p->next; } printf("\n"); } node *copyList(node *head) { node *copyHead, *p, *q; p = (node *)malloc(sizeof(node)); p->coefficient = head->coefficient; p->exponent = head->exponent; p->next = NULL; head = head->next; copyHead = p; while(head != NULL) { q = (node *)malloc(sizeof(node)); q->coefficient = head->coefficient; q->exponent = head->exponent; p->next = q; p = q; head = head->next; } p->next = NULL; return copyHead; } void destroy(node *head) { node *p, *q; p = head; head = NULL; while(p != NULL) { q = p; p = p->next; free(q); } }

作者写本文代码也花了不少时间，现将容易踩的坑总结如下，希望大家看后能注意避开，节省调试时间。 1、不带头结点的链表传递的是头指针的复制版，如果在函数中改变了复制版头指针的位置将不会影响原指针，要注意返回新的头指针。对于传递的是指针还是指针的指针在编写代码的过程中要注意区分。 2、对链表的操作经常要用到循环，那么循环结束条件的书写也需要注意，因为很多人喜欢在while循环的括号中访问指针指向的结点内容，如果此时没有先判断该指针是否为空就可能导致程序异常中断而且不易发现。正确的写法应该是while(p != NULL && p->结点内容)，这样会先判断p是否为空，如果为空则后面的条件不再判断，循环直接终止。 3、在程序结束前要记得释放之前申请的内存，此时要注意确定哪个指针才是指向头结点的，作者在本文中会合并链表，所以原链表的头指针是没用的，调用函数释放内存时应传入合并后链表的新的头指针。

注意：本段代码给链表排序后并没有合并同类项，如果输入形如x^2 + x^2…这样的含有同类项的多项式，在最终的结果中会分开显示。读者可以根据排序后的链表分别逐个检查前后是否有幂相同的项，有则将它们合并后再进行相加相减操作，即可得到正确的输出。

本文代码的内容比较容易读懂，即使个别地方有点复杂，读者也可以自己在草稿纸上模拟代码的执行过程弄懂，总而更加清楚代码是如何实现功能的，所以并没有写详细的注释，如果读者有什么问题欢迎留言提问。