数据结构课程设计报告一元多项式的计算.docx

《数据结构课程设计报告一元多项式的计算.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告一元多项式的计算.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、元多项式的计算需求分析建立一元多项式并按照指数降序罗列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果.、概要设计存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间， 只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零 项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的 指针。创建一元多项式链表，对一元多项式的运算中会浮现的各种可能情况进行 分析，实现一元多项式的相加、相减操作。基本算法：1、输入输出（1）功能：将要进行运算的多项式输入输出。（2）数据流入：要输入的多项式的系数与指数。（3）数据流出：

2、合并同类项后的多项式。（4）程序流程图：多项式输入流程图如图1所示。（5）测试要点：输入的多项式是否正确，若输入错误则重新输入图表1pd=SubtractPolyn (pa, pb);多项式a-b：DestroyPolyn(pd);continue;if (flag=4) break ;/forDestroyPolyn (pa);DestroyPolyn (pb);return 0;四、调试结果1. 测试的数据及结果c C ,DAProgram FilesC Free St a ndardtem p L.exe,勺 i 2 3 4勺 1 2 3 * I 4第第第第|示7T入入入入入入入入f提:

3、4系系:3hf 致的的的的数的的的I 项项项项项项项项项f4 3 2 1 5 4-32 ft:期期期 自旨OIKXD a ?*? 力. 与与与与数数数E bDKDbB * 力:4 力.m 与与与| /攵攵m 12 3 4和f f a a & 式式式 项项项 多多多 出至出 nt I I I 傕allblfri 作 Lfr / a h /&/a/I 行项项费费行1 5XW4XT 7XZ2X 5X3 MX 2 7(2,SX人3：SXF-xr-xs+R2.算法的时间复杂度及改进算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+n),减法运算的 时间复杂度为0(m-n),其中m, n分别表示

4、二个一元多项式的项数。问题和改进思想：在设计该算法时，浮现了一些问题，例如在建立链表时头指针 的设立导致了之后运用到相关的指针时没能很好的挪移指针浮现了数据重复输出或者是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个 链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插入删除等操作。为 了使输入数据按指数降序罗列，可在数据的输入后先做一个节点的排序函数，通过对链 表排序后再进行之后加减运算。2、多项式的加法(1)功能：将两多项式相加。(2)数据流入：输入函数。(3)数据流出：多项式相加后的结果。(4)程序流程图：多项式的加法流程图如图2所示。(5)测试要点

5、：两多项式是否为空，为空则提示重新输入，否则，进行运算。图表2结束3、多项式的减法(1)功能：将两多项式相减。(2)数据流入：调用输入函数。(3)数据流出：多项式相减后的结果。(4)程序流程图：多项式的减法流程图如图3所示。(5)测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。图表3三、详细设计#include#includetypedef struct Polynomial float coef;int expn;struct Polynomial *next;)*Polyn, Pol ynomial;/Polyn 为结点指针类型void Insert(Polyn p, Po

6、lyn h) if (p-coef=0) free(p);系数为0的话释放结点else (Polyn ql,q2;ql=h;q2=h-next;while(q2&p-expnexpn) 查找插入位置ql=q2;q2=q2-next;)if (q2&p-expn=q2-expn) 将指数相同相合并 q2-coef+=p-coef;free (p);if(!q2-coef) 系数为0的话释放结点ql-next=q2-next;free (q2);)else 指数为新时将结点插入p-next=q2;ql-next=p;/InsertPolyn CreatePolyn (Polyn head, int

7、 m) 建立一个头指针为 head 项数为 m 的一元 多项式 int i;Polyn p;p=head=(Polyn)malloc(sizeof(struct Polynomial);head-next=NULL;for(i=0;inext;q2=ql-next;while(ql-next) free (ql);ql-q2; 指针后移 q2=q2-next;)void PrintPolyn(Polyn P) Polyn q=P-next;int flag=l;项数计数器if(!q) 若多项式为空，输出0putchar ( O);return;)while (q) if (q-coef0&fl

8、ag! = l) putchar(+); 系数大于 0 且不是第一项if (q-coef!=l&q-coef!=T) 系数非1或者T的普通情况if (q-expn=l) putchar (X);)else if (q-coef=l) if (!q-expn) putchar( 1);else if (q-expn=l) putchar ( X);if (q-coef二二-1) q=q-next;flag+；/while/PrintPolynint compare(Polyn a, Polyn b) if(!b| |a-expnb-expn) return 1;else if(!a|a-expn

9、expn) return -1;else return 0;)else if (!a&b) return T;a多项式已空，但b多项式非空else return 1 ;/b多项式已空，但a多项式非空/comparePolyn AddPolyn(Polyn pa, Polyn pb) 求解并建立多项式a+b,返回其头指针Polyn qa=pa-next;Polyn qb=pb-next;Polyn headc, he, qc;hc= (Polyn) malloc (sizeof (struct Polynomial); 建立头结点hc-next=NULL;headc=hc;while(qa| |

10、qb) qc=(Polyn)malloc(sizeof(struct Polynomial);switch(compare(qa, qb) case 1:(qc-coef=qa-coef;qc-expn=qa-expn;qa=qa-next;break;case 0:Iqc-coef=qa-coef+qb-coef;qc-expn=qa-expn;qa=qa-next;qb=qb-next;break;case -1:(qc-coef=qb-coef;qc-expn=qb-expn;qb=qb-next;break;/switchif (qc-coef!=0)qc-next=hc-next;h

11、c-next=qc;hc=qc;)else free(qc);当相加系数为0时,释放该结点/whilereturn headc;/AddPolynPolyn SubtractPolyn(Polyn pa, Polyn pb) /求解并建立多项式a+b,返回其头指针Polyn h=pb;Polyn p=pb-next;Polyn pd;while(p) 将pb的系数取反p-coef*=-l;p=p-next;pd=AddPolyn(pa,h);for (p=h-next;p;p=p-next) 恢复 pb 的系数p-coef*=-l;return pd;/SubtractPolynint mai

12、n() int m, n, flag=0;float x;Polyn pa=0, pb=0, pc, pd, pe, pf ；定义各式的头指针，pa与pb在使用前付初值NULL 请输入a的项数pa=CreatePolyn(pa, m);建立多项式 a请输入b的项数pb=CreatePolyn (pb, n)；建立多项式 a输出菜单操作提示： 1.输出多项式a和b 2.建立多项式a+b 3.建立多项式退出for ( ; ;flag=0) 执行操作：if (flag=l) 多项式a：多项式b：)if (flag=2)pc=AddPolyn (pa, pb);多项式a+b：DestroyPolyn(pc);continue;