三、详细设计

（1）：存储结构

一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。

（2）：数据链表

由于采用链表的方法，我们可以建立3条链；一条用于存放多项式HA，一条用于存放多项式HB，还有一条用于存放新形成的HC。此外，我们的程序应具备以下几个功能：建立链表，撤销链表，打印链表，按要求插入一个新的结点，复制链表；为了使上面程序结构分析进一步细化，为了使程序结构更加清晰，我们可以把上面的内容都编写成函数形式。

1、建立链表

该程序建立链表的函数与大多数建立链表的操作基本一致，但是由于实体是一元多项式的关系。我们更希望，在处理客户输入的数据的同时，能对数据进行适当的处理。也就是数学上所说的，“对一元多项式进行化简，并按照降幂排序。”由于在前面的练习中，我们得知，在链表中插入一个结点的函数，具有对链表的成员进行排序与合并的功能。如此一来，我们可以巧妙地处理，在建立链表的同时，调用”在链表中插入一个结点的函数”，对新建立的链表进行化简。

该函数的算法描述如下；

声明指针变量，并作为头指针的指针变量赋初值NULL； 创建一个新的结点，并输入链表的信息；

若输入的系数值与函数值同不为0时，调用”在链表中插入一个结点的insert函数”，将结点插入链表中；(注：这里建立链表的函数与以往的不同，我们是通过假想有一条空链，不断地调用insert函数来实现建立链表的功能。简言之；链表中成员的链接全都靠insert函数来实现，而该函数仅仅是不断地提供建立链表所要的数据罢了。)

若还要继续插入结点，转到步骤2继续进行；

6

否则，程序结束，把头指针返回主程序。 2、撤销链表

撤销链表是为了把链表所占用的地址回收起来，防止造成浪费。我们该程序可以采用从链表的始端逐步销去结点。在这个过程中，我们需要链表的头地址作为形式参数，还需要建立一个指针用来指向新头地址。

该函数的算法描述如下：

指针变量；并把头地址指针赋给新指针变量； 把头地址指针指向下一个结点； 删除新指针变量；

若还要继续删除结点，转到步骤1继续执行； 否则，结束程序。

3、按要求插入一个新的结点

由于前面的建立链表的creat函数，调用了该函数，所以我们这个函数的设计思想也明朗多了，由于建立的链表是有序的，并且需要合并指数相同的结点，所以要新结点需要按指数值降幂的顺序插入链表中。判断链表是否为空，如果为空则直接插入即可；否则按照要插入结点指数值的大小在链表中寻找他要插入的位置，对于插入位置有第一个节点、最后一个结点和链表中间这三种情况分别进行处理。

函数的形式参数：链表的头地址，指向要插入结点的指针； 返回结果：插入结点后新链表的头地址。 该函数的算法描述如下：

声明指针变量并令它指向连头结点； 判断指向要插入结点的指针是否为空；

如果是，则不需要插入新结点，直接返回头地址，程序结束； 否则再判断链表是否为空；

如果是，则直接插入结点，然后返回链表的头地址，程序结束； 否则，在链表中寻找待插入结点的插入位置：

1，若链表中存在着与“插入的结点”的指数相同的情况，我们依然插入链中，只是把该结点的系数修改为”0”，把链中的结点系数修改为”两系数之

7

和”。(为了方便，我们并没有把结点进行删除的操作，只是在输出的操作里加入权限设置。)

2，若链表中不存在着与“插入的结点”的指数相同的情况，我们正常地插入链中。

返回插入结点后链表的头地址，程序结束。 4、主函数

主函数主要负责输出界面的指引语句，并合理地调用各个函数，还要有适当的循环操作以及停止循环的语句，以致可以方便地达到合并两个一元多项式的功能。

四、调试分析

（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析:

在输入诸如“0,3”，“2,0”时，程序无法正常运行或总是出错. 解决：对指数或系数为0的情况应单独讨论。为此，建立了delZeroCoef函数来解决问题。

（2）算法的时间复杂度及改进

算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+n）,减法运算的时间复杂度为O(m-n)，其中m，n分别表示二个一元多项式的项数。

问题和改进思想：在设计该算法时，出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后先做一个节点的排序函数，通过对链表排序后再进行之后加减运算。

五、 源程序代码

#include

#include

8

#include

typedef struct LNode { float coef; int expn;

struct LNode *next; }LNode;

LNode* InitPolyn(LNode *La,int n) { if(n <= 0) return NULL;

LNode *h = La = (LNode*)malloc(sizeof(LNode)), *Lb; La->coef = 0.0; int i;

printf(\依次输入%d个非零项（每项前一个为系数，后一个为指数）\\n\

for (i = 1; i <= n; ++i) {

scanf(\if(La->coef) Lb = La;

La = La->next = (LNode*)malloc(sizeof(LNode)); }

Lb->next = NULL; free(La); return h; }

LNode* selsort(LNode *h) { LNode *g, *La, *Lb; if(!h) return NULL; float f;

int i, fini = 1;

for(g = h;g->next&&fini;g = g->next) { fini = 0;

for(La = h,Lb = h->next;Lb;La = La->next,Lb = Lb->next) if (La->expn < Lb->expn) { f = La->coef;i = La->expn;

La->coef = Lb->coef;La->expn = Lb->expn; Lb->coef = f;Lb->expn = i; fini = 1; } }

for(g = h,La = g->next;La;) if(g->expn==La->expn) { g->coef += La->coef; g->next = La->next; Lb = La;

La = La->next;

9

free(Lb); }

else if(g->next) { g = g->next; La = La->next; }

return h; }

void PrintfPoly(LNode *La) { LNode *Lb = La; if(!Lb) {

putchar('0'); return; }

if(Lb->coef!=1) {

printf(\

if(Lb->expn==1) putchar('X');

else if(Lb->expn) printf(\}

else if(!Lb->expn) putchar('1'); else if(Lb->expn==1) putchar('X'); else printf(\Lb = Lb->next; while (Lb) {

if(Lb->coef > 0) putchar('+'); if(Lb->coef!=1) {

printf(\

if(Lb->expn==1) putchar('X');

else if(Lb->expn) printf(\}

else if(!Lb->expn) putchar('1'); else if(Lb->expn==1) putchar('X'); else printf(\Lb = Lb->next; } }

Compare(LNode *a, LNode *b) {

if (a->expn < b->expn) return -1; if (a->expn > b->expn) return 1; return 0; }

LNode* AddPolyn(LNode *Pa, LNode *Pb) { LNode *h, *qa = Pa, *qb = Pb, *La, *Lb; float sum;

10