[工学]数 据 结 构 课 程 设 计--2- 副本.doc

第一章 需求分析 1.1 功能描述两个一元多项式加法与乘法的实现，顾名思义，本程序的主要功能就是对两个一元多项式进行代数上的加法与乘法运算。从程序的名称上看，似乎程序的源代码并不难写，其实事实也正如此。但是，如果要求程序本身不仅好用而且能够让广大读者能够理解程序的内在含义，做到这一点的确不容易，因此本人将尽力向大家对该程序的功能作出详细解析。功能一：两个一元多项式的加法。在数学上两个一元多项式的加法实现很简单，即将两个多项式相加后再进行整理合并即可，然而如果要想用程序实现此操作，就没那么简单了。但是，由于此操作在数学上可实现，因此可将同样的思想运用在编程上，理论上也应该可以实现，事实也正是如此。在两个多项式相加过程中，程序是这样处理的:先将两个多项式中的所有项都开辟空间将其存储起来，然后在新生成的多项式上进行整理合并操作，最后即得出相加后的最简结果，关于其具体过程读者可以参考后面第二章中的模块说明部分，那里给出了详尽说明。功能二：两个一元多项式的乘法。同前面一元多项式的加法相比较，显然一元多项式的乘法实现相对来说比较复杂，这体现在两个方面：一是要将每个多项式中的所有项都与另一个多项式中的所有项两两之间都要进行相乘，此过程工作量相当大；二是要将相乘以后的所有项都开辟空间将其存储起来，得到一个新的多项式，然后在此多项式上再进行整理合并操作，得到相乘以后的最简结果。关于其具体过程读者可以参考后面第二章中的模块说明部分，那里给出了详尽说明。由于上述两点，乘法部分的程序模块理解起来比加法部分的程序模块理解起来也更加吃力。下面给出本论文的课程设计的题目：*动态双链循环链表结构下的一元多项式的加法、乘法的实现： 设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn请实现求 Am(x)+Bn(x)和Am(x)Bn(x)要求： 1)采用动态存储结构实现；2)要求输出结果中无重复阶项和无零系数项；3)要求输出结果的升幂和降幂两种排列情况1.2 未来描述本程序目前只能实现两个一元多项式的加法与乘法运算，但程序的未来却不仅仅于此。由于程序中均采用双链循环链表作为多项式的存储结构，调用函数处理链表时都是从其头结点开始，故当要求实现多个多项式的加法与乘法运算时，只需对程序作稍微修改，即可实现此功能，关于其具体说明读者可以参考后面第五章节的内容，那里给出了详尽的描述。此外，程序的功能还可以继续扩展，只要添加合适的模块与程序连接即可实现，比如说添加实现两个多项式减法与除法的模块即可实现减法与除法运算，一旦模块添加成功也就意味着可以实现多个多项式的减法与除法运算。基于上述几点，程序的最终功能是可以实现任意多个多项式的加减乘除混合运算，因此程序的未来还是很有发展空间的。此外，本程序还可以添加一个很有用的函数模块，即查找运算。程序的空间复杂度和时间复杂度也可以进一步提高。另外，本程序对运算结果的输出只有三种方式，但是不同的用户对运算结果的输出要求也不尽相同，对此程序只要多连接几个函数模块即可实现。关于程序未来的详细描述，读者可以参考后面第五章的内容，那里给出了详尽的描述。 第二章 系统设计2.1 多项式双链循环链表的生成函数程序在对多项式进行处理之前，首先要将多项式以合适的形式存储起来，以便于程序基于其存储形式对其进行数学运算的操作。本程序中对多项式的存储采用的均是双链循环链表，而表中的结点均是结构体型的数据，多项式中的每一项都要用一个结点来存储，其中包括四个数据：项的系数coef，项中x的指数exp，指向下一项的指针next，指向前一项的指针prior。因此，首先要生成能存储多项式的双链循环链表，现将其生成函数算法给出如下：typedef struct pnode float coef; int exp; struct pnode *next; struct pnode *prior; polynode;polynode *creatlist( ) /多项式的双链循环链表的生成函数polynode *p,*q,*head; head=p=malloc(sizeof(polynode); printf( n); printf( 请输入头结点数据：); scanf(%f%d,&p-coef,&p-exp); printf( 输入其他结点数据：);while(p-coef!=100)&(p-exp!=100) /当向多项式链表结点中中输入100、100时,则完成多项式的建立q=p;p=malloc(sizeof(polynode);scanf(%f%d,&p-coef,&p-exp);q-next=p;p-prior=q; p-prior-next=head; /最后一个结点不作为链表中的元素 p=p-prior;head-prior=p; printf( n);return head; 从函数的第一行可以看出，creatlist是带有返回值的函数，且返回的是一个polynode类型的指针数据；从函数的最后一句“return head”可以看出，函数返回的是双链循环链表的头指针。函数一开始先生成链表的头结点head，然后向头结点的coef和exp中任意输入两个数（从程序后面对链表进行运算处理的部分可以知道，对链表的头结点是不进行任何处理的，且在输出链表中数据时也不从头结点开始输出，而是从其所指的结点开始，因此头结点中的两个数据可以任意输入），紧接着函数用while循环开始建立链表的有效部分，即不停地生成结点p然后依次输入多项式中每一项的数据，再按先后顺序将各结点链接起来。若多项式存储完毕，则向最后生成的一个结点中输入100，100后（最后一个结点不作为链表中的元素），即可完成多项式双向循环链表的的生成。 2.2 实现两个一元多项式的加法函数 在完成用双链循环链表存储多项式的基础上，就可以在基于双链循环链表的存储结构上进行一系列的数学运算，本节介绍两个多项式的加法运算模块。加法运算的主要思想是：重新生成一条双链循环链表，链表中的第一个结点依然是头结点，其中的数据依然是任意输入的。将前面生成的两个多项式链表的第二个结点中的exp进行比较：当二者相等则将这两个结点中的coef相加，若相加以后的结果等于零，则在新生成的链表中不生成新结点，若相加以后不等于零，则在新链表中生成新结点，结点中的coef值即为上述二者中的coef值的和，结点中的exp值即为上述二者中的exp值；当二者不相等则需在新链表中生成两个新结点，结点中的数据分别存储上述二者中的数据。现将其加法函数算法给出如下：polynode *plus(polynode *a1,polynode *a2) /实现两个一元多项式的加法函数 polynode *ptr,*q,*q1,*q2; float x; q1=a1;q2=a2; q=malloc(sizeof(polynode); q-coef=0; q-exp=-1; q-next=q; ptr=q; q1=q1-next; q2=q2-next; while(q1!=a1)&(q2!=a2) if(q1-exp=q2-exp) x=q1-coef+q2-coef; if(x!=0)q-next=malloc(sizeof(polynode); q=q-next;q-coef=x;q-exp=q1-exp;q1=q1-next;q2=q2-next; else q-next=malloc(sizeof(polynode); q=q-next; if(q1-expq2-exp) q-coef=q2-coef; q-exp=q2-exp; q2=q2-next; else q-coef=q1-coef; q-exp=q1-exp; q1=q1-next; while(q1!=a1) q-next=malloc(sizeof(polynode); q=q-next;q-coef=q1-coef; q-exp=q1-exp;q1=q1-next; while(q2!=a2) q-next=malloc(sizeof(polynode); q=q-next;q-coef=q2-coef; q-exp=q2-exp;q2=q2-next; q-next=ptr; return ptr; 算法的最后有两个while循环，当两个多项式的项数不等长时即发挥作用。当a2链表处理完时a1链表中还有剩余的项，则在新链表中生成新结点直接将a1中的剩余项复制到新链表中即完成两个链表的加法运算；同理当a1链表处理完时a2链表中还有剩余的项，也做同样的处理。由算法的最后一句可知，该函数的返回值也是链表的头结点。 2.3 实现两个一元多项式的乘法函数 在完成用双链循环链表存储多项式的基础上，就可以在基于双链循环链表的存储结构上进行一系列的数学运算，本节介绍两个多项式的乘法运算模块。乘法运算的主要思想是：重新生成一条双链循环链表，链表中的第一个结点依然是头结点，其中的数据依然是任意输入的。假设待处理的两个多项式是A=X+X2+X4-X5， B=2X+2X2+2X3,则在程序中规定A*B的方法为A中的所有项从第一项X开始与B中的所有项从第一项2X开始按先后次序分别相乘，直至将A中的最后一项3X3与B中的所有项都乘完为止。A中每一项都要乘三次，故一共要乘九次。在每次相乘之前新链表上都生成一个新结点，新结点中的coef和exp的值即为两项相乘之后的X的系数和指数。现将其乘法函数算法给出如下：polynode *multiply(polynode *a1,polynode *a2) /实现两个一元多项式的乘法函数int n=1;polynode *head,*p1,*p2,*p,*q,*t;p1=a1-next;p2=a2-next;head=p=malloc(sizeof(polynode);p-coef=0;p-exp=-1;for(;p1!=a1;p1=p1-next)for(;p2!=a2;p2=p2-next) q=p;p=malloc(sizeof(polynode);p-coef=(p1-coef)*(p2-coef);p-exp=p1-exp+p2-exp;q-next=p;p-prior=q;p2=a2-next;p-next=head;head-prior=p;for(p=head-next;p-next!=head;p=p-next) /将两个多项式相乘以后的结整理合并的部分 for(t=p-next;t!=head;t=t-next) if(p-exp=t-exp) p-coef=p-coef+t-coef; t-prior-next=t-next; t-next-prior=t-prior; return head; 当上述两个多项式完成乘法运算以后，得到的新链表还有待处理，因为链表中可能有很多结点的exp值相等，即在相乘后得到的多项式中可能存在很多X的指数相同的项。因此，在上述算法的最后增加了一个for循环，它从新链表头结点所指的第一个多项式结点开始处理链表，其具体处理过程是这样的：取出链表中第一个多项式结点的exp的值按先后次序与链表中其他所有结点的exp的值进行比较，若发现exp值相同的项，则将其与第一个结点合并，即系数合并且合并之后保存在第一个结点的exp中，同时把被合并的项从链表上删除，因此链表的长度是不断更新的且链表中结点内的数据也是不断变化着的。与第一个结点的处理相同，for循环将链表上剩余的所有结点都进行了同样的处理，故最后得到的多项式链表是一条经过整理合并后的最简多项式链表。由算法的最后一句可以看出，该函数返回的也是链表的头结点。 2.4 将结果按幂的升序处理函数当实现了两个多项式的加法与乘法运算并且经过整理合并之后，得到的结果可能是乱序存储在链表中的。比如上节所述的两个多项式A=X+X2+X4-X5， B=2X+2X2+2X3,则按照程序处理A与B的加法运算得到的初始结果应为：A+B=3X+3X2+X4-X5+X3,而有时我们希望将所得结果按照一定的次序输出，比如将结果按X幂的升序输出，此时我们就希望链表中结点是按exp值的升序依次链接的。在基于双链循环链表的存储结构上此操作不难实现，只需调用一个函数对链表进行升序处理即可，处理完后链表的长度不改变。现将其算法给出如下：void upsort(polynode *a) /将结果按幂的升序处理函数 polynode *p,*q,t;for(p=a-next;p-next!=a;p=p-next) for(q=p-next;q!=a;q=q-next)if(p-expq-exp)t.coef=p-coef;t.exp=p-exp;p-coef=q-coef;p-exp=q-exp;q-coef=t.coef;q-exp=t.exp;由上面算法可知，程序是用选择法对链表中结点进行排序的，其具体处理过程是这样的：用第一个多项式结点中exp值按先后顺序与链表中所有剩余结点的exp值进行比较，每当发现被比较的结点中的exp值比第一个结点中的exp值大，则将二者中的所有数据进行交换，否则不交换；比较一直进行到链表中的最后一个结点为止。因为有外侧for循环的存在，当第一个多项式结点处理完之后，链表中其余结点也将按先后顺序得到同样的处理。因此，当所有结点都处理完之后链表就成为了一条按结点中exp值升序链接的多项式链表，这正是我们所要的。此函数只对链表进行内部处理，没有返回值。将结果按幂的降序处理函数与其升序处理函数道理相类似，因此不再另设章节详细说明。 2.5 输出函数 在对多项式链表进行了各种数学运算处理后，程序还需要将处理结果输出，因此需要一个输出函数按先后次序输出链表各结点中的数据。链表中的任何一个结点都包含了两个数据coef和exp，即多项式中某一项的X前的系数和其指数，这两个数据正是需要输出的数据。若只是简单的输出这两个数据很容易实现，但是如何使输出的效果达到最好，即能够让用户对输出结果一看就懂，这就需要在链表的输出上做一定的处理。比如上节所述的两个多项式A=X+X2+X4-X5， B=2X+2X2+2X3,则将二者相加后的结果进行幂的升序处理后得到的输出结果应是：A+B=3X+3X2+2X3+X4-X5， 我们观察其第一项是3X，故在链表中与其对应的结点中的coef=3，exp=1。此时，若按常规将两个数据都输出得到的结果应是3X1，而用户一般情况下都希望得到的是最简结果即3X，所以程序中是按最简输出处理的。再如其最后两项X4和-X5，他们前面的系数分别是1和-1，若此时也按常规将与其对应的结点中的数据全都输出得到的结果应是1X4和-1X5，显然这样的输出一般情况下也不符合用户的要求，故对这样的输出也做了特别处理。现将程序输出函数的算法给出如下：void print(polynode *f)/输出函数polynode *t; t=f-next; while(t!=f) if(fabs(t-coef)=1.0) if(t-coef=1) if(t-exp=1) printf(x); if(t-exp=0) printf(1); if(t-expexp); if(t-exp0)&(t-exp!=1) printf(x%d,t-exp); else if(t-exp=1) printf(-x); if(t-exp=0) printf(-1); if(t-expexp); if(t-exp0)&(t-exp!=1) printf(-x%d,t-exp); else if(t-exp=1) printf(%-1.0fx,t-coef); if(t-exp=0) printf(%-1.0f,t-coef); if(t-expcoef,t-exp); if(t-exp0)&(t-exp!=1) printf(%-1.0fx%d,t-coef,t-exp); if(t-next!=f)&(t-next-coef0) printf(+); t=t-next; 由上面算法可以看出，凡是遇到coef等于1和-1或是exp等于1的结点，对于它们的输出都做了特别处理，而对于一般的结点都按正常输出，即coef和exp的值都要输出。对于此算法还有一点需要说明的是，在输出X前的系数即coef时，只输出了其整数部分，而对于其后面的小数部分没有输出，因此对于精确度要求很高的运算时，输出结果可能有误差。此时读者只要对程序稍微修改即可，比如输出语句printf(%-1.0fx%d,t-coef,t-exp);那么读者只需改动t-coef的输出格式控制符%f的f前的数字即可，使其输出精度更高。 第三章 编码 3.1 主函数流程图 select的值select的值开 始调用switchcase函数select的值调用creatlist函数errorerrorexit(0)select的值调用加法函数exit(0)调用乘法函数exit(0)exit(0)结 束 case1 case2 case3 case4 case2 case3 case4case4 case43.2 多项式的双链循环链表的生成函数流程图开 始生成头结点head=p=malloc( )scanf(%f%d,&p-coef,&p-exp)注意p-coef!=100，p-exp!=100p-coef!=100?p-exp!=100?q=p生成新结点p=malloc( )scanf(%f%d,&p-coef,&p-exp)q-next=pp-prior=q将最后一个结点从链表上删除p-prior-next=headp=p-priorhead-prior=preturn head完成链表的建立结 束 是 否 3.3 实现两个一元多项式的加法函数流程图q1=a1且q2=a2 ?结 束开 始两条待处理链表a1,a2a1中q1-exp=a2中q2-exp ?生成新链表head=q=malloc( )x=q1-coef+q2-coefq-next=malloc( )q-coef=q1-coefq-exp=q1-expq-next=malloc( )q=q-nextq-coef=xq-exp=q1-expq-next=malloc( )q-coef=q2-coefq-exp=q2-expx=0 ?q1=q1-nextq2=q2-nextreturn head 是 否 否 是 否 是 3.4实现两个一元多项式的乘法函数流程图p-next=malloc( )p-coef=p1-coef*p2-coefp-exp=p1-exp+p2-expp2=p2-nextreturn headfor(t=p-next;t!=head;t=t-next)if(p-exp=t-exp) p-coef=p-coef+t-coef;t-prior-next=t-next;t-next-prior=t-prior; p=head-nextp1=p1-nextP2=p2-nextp2!=a2 ?p!=head ?结 束 开 始生成新链表head=p=malloc( )两条待处理链表a1,a2p1=a1-next,p2=a2-nextp1=a1且p2=a2 ? 否 是 是 否 是 否 3.5将结果按幂的升序处理函数流程图t.coef=p-coef;t.exp=p-exp;p-coef=q-coef;p-exp=q-exp;q-coef=t.coef;q-exp=t.exp;p-expq-exp ?开 始待处理链表头结点headp=head-nextp=p-nextq=q-nextreturn headq=p-nextp!=head ?结 束q!=head ? 是 否 否 是 否 是 第四章 测试 4.1测试用例选择及说明为了验证程序运行正常，读者可以用让程序运行多个例子进行测试，下面作者仅举一例进行测试，验证程序的正确性。比如两个多项式A=X2+X3,B=2X4+2X6,则二者相加与相乘后的幂原序结果分别为:A+B= X2+X3+2X4+2X6,A*B=2X6+2X8+2X7+2X9。在建立两个多项式链表时，其头结点数据可以任意输入，因为程序在对其进行运算时是从头结点中next所指的结点开始的，即从每条链表的第二个结点开始。例子中头结点的coef和exp均为1。下面分步骤给出程序运行时的截图： 图 1 图 1为程序初始运行时的界面，选择不同的select的值执行不同的功能。由于要先生成多项式链表再进行运算，故此时应该选择1或4。 图 2 图 2中select的值为1，故先生成A，B两条多项式链表。每条链表的最后一个结点中的coef和exp均输入100，作为链表完成建立的标志。 图 3 图 3表示的是A+B部分。从图中可以看出，幂原序输出的结果与预先算出的结果一致。 图 4 图 4表示的是A*B部分。从图中可以看出，幂原序输出的结果与预先算出的结果一致。 图 5 图 5中select的值为4，程序结束运行，与功能菜单中的命令一致。 第五章 维护 5.1 程序的未来展望 不同的用户对程序的要求可能不同， 本程序的主要功能是实现两个多项式的加法与乘法运算，但是很多情况下也需要实现两个多项式的减法与除法运算，考虑到这一点程序在设计之初就为之做了准备，即各种运算都是通过调用函数来实现的，因此本程序容易实现和其他函数模块的链接，故当用户希望程序能够实现减法与除法运算时只需在程序中再添加两个函数模块即可。另外，本程序对运算结果的输出只有三种方式，但是不同的用户对运算结果的输出要求也不尽相同。比如A+B=X+X2+X3+X4+X5+X6,若用户要求输出时A+B= X+X3+X5+X2+X4+X6即在输出时将奇次幂优先输出且按幂由小到大输出，对此同样可以通过在程序中添加函数模块实现此功能。本程序通过修改还可以实现多个多项式的加法，只要不断的调用生成函数和加法函数即可实现，同样多个多项式的其他运算也可以用相同的办法实现。此外，本程序还可以添加一个很有用的函数模块，即查找运算:当用户给定某一项时要求从链表中找出与之对应的项并返回其地址或从链表中找出指定幂的项前的系数coef或从链表中找出指定系数的项的指数exp，当查找成功时返回查找值，当没有找到时返回error。上述均是关于程序功能的扩展，均未涉及到程序的性能描述，若用户要求提高程序的性能时，本程序还是有提高的空间，因为程序的空间复杂度和时间复杂度都有提高的空间，因此可从其空间复杂度和时间复杂度方面提高。 综上所述，从该程序展望其未来可以知道程序的兼容性很好，只要增加各种不同功能的函数模块理论上都可以实现程序功能的扩展。由于程序中时间和空间的消耗还可以进一步减小，故程序的性能还可以进一步提高。 附录 1 程序清单：#include#include#includetypedef struct pnode float coef; int exp; struct pnode *next; struct pnode *prior; polynode; polynode *creatlist(); /多项式的双链循环链表的生成函数声明polynode *plus(polynode *a1,polynode *a2); /实现两个一元多项式的加法函数声明polynode *multiply(polynode *a1,polynode *a2);/实现两个一元多项式的乘法函数声明void upsort(polynode *head); /将结果按幂的升序处理函数声明void downsort(polynode *head); /将结果按幂的降序处理函数声明void print(polynode *head); /输出函数声明void print1();void print2();void print3();void switchcase( ); /根据输入值的不同选择不同的操作void main()switchcase( ); void switchcase( )polynode *q;polynode *p1,*p2; int select,i;printf( 功能菜单n);printf( =n);printf( = 1：-建立两个多项式链表- =n);printf( = 2：实现两个多项式的加法运算 =n);printf( = 3：实现两个多项式的乘法运算 =n);printf( = 4：-结束运行- =n);printf( =n);for(i=0; ;i+) printf(nn 请输入select的值：);scanf(%d,&select); switch(select) case 1:printf(n A,B的建立n); printf( =n); p1=creatlist(); p2=creatlist(); printf( A=); print(p1); printf(n); printf( B=); print(p2); printf(n); printf( =n);break; case 2: q=plus(p1,p2); printf(n A+B部分：n); print1(); printf(A+B=); print(q); printf(n); upsort(q); print2(); printf(A+B=); print(q); printf(n); downsort(q); print3(); printf(A+B=); print(q); printf(n); printf( =n); break; case 3:q=multiply(p1,p2); printf(n A*B部分：n); print1(); printf(A*B=); print(q);printf(n); upsort(q); print2(); printf(A*B=); print(q);printf(n); downsort(q); print3(); printf(A*B=); print(q);printf(n);printf( =n); break; default:printf(n 谢谢使用，再见！n); exit(0); polynode *creatlist( )/多项式的双链循环链表的生成函数polynode *p,*q,*head; head=p=malloc(sizeof(polynode);printf( n);printf( 请输入头结点数据：);scanf(%f%d,&p-coef,&p-exp); printf( 输入其他结点数据：);while(p-coef!=100)&(p-exp!=100)/当向多项式链表结点中中输入100、100时,则完成多项式的建立q=p;p=malloc(sizeof(polynode);scanf(%f%d,&p-coef,&p-exp);q-next=p;p-prior=q; p-prior-next=head; p=p-prior; head-prior=p; printf( n);return head; polynode *plus(polynode *a1,polynode *a2) /实现两个一元多项式的加法函数 polynode *head,*q,*q1,*q2; float x; q1=a1;q2=a2; q=malloc(sizeof(polynode); q-coef=0; q-exp=-1; q-next=q; head=q; q1=q1-next; q2=q2-next; while(q1!=a1)&(q2!=a2) if(q1-exp=q2-exp) x=q1-coef+q2-coef; if(x!=0)q-next=malloc(sizeof(polynode); q=q-next;q-coef=x;q-exp=q1-exp;q1=q1-next;q2=q2-next; else q-next=malloc(sizeof(polynode); q=q-next; if(q1-expq2-exp) q-coef=q2-coef; q-exp=q2-exp; q2=q2-next; else q-coef=q1-coef; q-exp=q1-exp; q1=q1-next; while(q1!=a1) q-next=malloc(sizeof(polynode); q=q-next; q-coef=q1-coef; q-exp=q1-exp; q1=q1-next; while(q2!=a2) q-next=malloc(sizeof(polynode); q=q-next; q-coef=q2-