思路

这题是我做数据结构以来，碰到最难的题目了。以往我写的代码都只有几十行，一百来行顶天了。结果这次有将近两百行。 代码量的增加，首先带来的问题就是如何顺利写完。 因此结构化的设计是首要选择，而且必须要有清晰的程序设计思路： 自顶向下 就是先审题，将程序划分为几个独立的模块（函数），然后再一个模块一个模块的写出来。

这种思维我初学python的时候就使用过了，但在这道题中才真正见到了 自顶向下设计思维的强大之处！！

在修改 BUG的时候，可以根据错误的答案，“罪责”到某个具体模块，再到某个具体语句。

有时候调试都不需要，真的是太强大了！！

我觉得老师讲解这道题最精华部分就在于思路解析的过程，至于代码如何实现都是毛毛雨，建议反复观看老师的具体解题思路。

代码

#include<stdio.h> #include<stdlib.h> typedef struct PolyNode *Polynomial;// 这里的作用应该是定义了一个指向PolyNode类型的节点 struct PolyNode{ int coef; int expon; Polynomial link; //这里不用加“* ”号的原因，应该是前面已经定义过了，Polynomial本身就代表了指针。 }; //这里用void，因为这里操作的是内存，改变的是地基，多项式已经被改变了，不需要返回什么 void Attach( int c, int e, Polynomial *pRear ) { Polynomial P; P = (Polynomial)malloc(sizeof(struct PolyNode)); P->coef = c; P->expon = e; P->link = NULL; (*pRear)->link = P;//把新节点接上多项式 *pRear = P;//移动尾巴指针 } Polynomial ReadPoly() { int N, c, e; Polynomial P, Rear, t; scanf("%d", &N); P = (Polynomial)malloc(sizeof(struct PolyNode));//创造一个新的空节点，好处的接入节点的时候方便。 P->link = NULL; Rear = P;//这里Rear的初值是多项式的最后一个节点。 while( N-- ){ scanf("%d %d", &c, &e); Attach( c, e, &Rear);//关于&这个符号，不加&表示符号，加了就表示一个地址。 } t = P; P = P->link; free(t); return P; } Polynomial Add( Polynomial P1, Polynomial P2 ) { Polynomial temp1, temp2, Rear, P, temp; temp1 = P1; temp2 = P2;//t1和t2是工作指针，像蜜蜂中的工蜂一样 P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL; Rear = P; //老操作，为了操作简便，先整个空节点，Rear指针为了Attach服务 while( temp1 && temp2 ) { //所有可能就只有三种，指数相等，大于，小于，把这三种情况都讨论完，那程序也就完成了 if( temp1->expon == temp2->expon ){ if( temp1->coef + temp2->coef == 0 ){ temp1 = temp1->link; temp2 = temp2->link; } else{ Attach( temp1->coef+temp2->coef, temp1->expon, &Rear); temp1 = temp1->link; temp2 = temp2->link; } } else if( temp1->expon < temp2->expon ){ Attach( temp2->coef, temp2->expon, &Rear); temp2 = temp2->link; } else{ Attach( temp1->coef, temp1->expon, &Rear); temp1 = temp1->link; } } //如果还剩下一个多项式，那就将其接上 while(temp1){ Attach( temp1->coef, temp1->expon, &Rear); temp1 = temp1->link; } while(temp2){ Attach( temp2->coef, temp2->expon, &Rear); temp2 = temp2->link; } temp = P; P = P->link; free(temp); return P; } Polynomial Mult( Polynomial P1, Polynomial P2 ){ Polynomial temp1, temp2, Rear, P, t; int e, c; if( !P1 || !P2) return NULL; temp1 = P1; temp2 = P2; P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;//这里即使是一个节点，链表的最后指针域也要加NULL，这个是一个思维的严密性 Rear = P; //这里先创造一个多项式，然后新的多项式用于插入排序 while(temp2){ Attach( temp1->coef*temp2->coef, temp1->expon+temp2->expon, &Rear); temp2 = temp2->link; } temp1 = temp1->link;//这里t1的第一个项被利用完了 while(temp1){ temp2 = P2;//这个程序的运行逻辑就是t1的某一个对t2的全部，这样t1的循环结束，全部也就结束了 Rear = P;//这里Rear指向了P的头节点,因为是插入操作，所以每次都需要重置尾指针 while(temp2){ //先将新节点的系数和指数求好，就等while语句来给这个新节点分配插入位置 e = temp1->expon + temp2->expon; c = temp1->coef * temp2->coef; //这一步是插入排序的一个关键步骤，让Rear找到新节点的插入位置 //当新节点等于或者大于现有的某节点时，就会停下。 while( Rear->link && Rear->link->expon > e ){ Rear = Rear->link; } //如果是因为等于而跳出循环，那么要考虑两种情况，一种是相加为0，一种是相加不为0 if( Rear->link && Rear->link->expon == e ){ if(Rear->link->coef + c){ Rear->link->coef += c; } else{//当求和为0的时候，自己把哪个节点free掉。这就是计算机思维和数学思维之间的碰撞 t = Rear->link; Rear->link = t->link; free(t); } } else{//如果因为大于而跳出循环，那么就创建一个新节点，接到Rear节点后面 t = (Polynomial)malloc(sizeof(struct PolyNode)); t->coef = c; t->expon = e; t->link = Rear->link; Rear->link = t; Rear = Rear->link; } temp2 = temp2->link; } temp1 = temp1->link; } temp2 = P; P = P->link; free(temp2);//这里有一个疑问，t2换成t1可以吗？ return P; } void PrintPoly( Polynomial P ){ int flag = 0;//flag为了解决最开头不用空格。 if(!P){ printf("0 0\n"); return; } while(P){ if(!flag){//这个只在开头起作用一次，就是第一次不打空格 flag = 1; } else{ printf(" "); } printf("%d %d", P->coef, P->expon); P = P->link; } printf("\n"); } int main() { Polynomial P1, P2, PP, PS;// 相乘之所以叫PP，是因为PP就表示相乘。而多项式求和之所以命名为PS，是因为PS叫缩写是Polynomial Sum。 P1 = ReadPoly(); P2 = ReadPoly(); PP = Mult( P1, P2 ); PrintPoly( PP ); PS = Add( P1, P2 ); PrintPoly( PS ); return 0; }

代码我是基本参考老师写出来的，参考性较强。

最后的忠告

写程序提升最大的时候，不是敲代码那段时间。 而是 构思程序 和 修改BUG 这两段时间！