一元多项式的计算数据结构课程设计

1、一元多项式的计算一加，减摘要（题目）一元多项式计算任务：能够按照指数降序排列建立并输由多项式；能够完成两个多项式的相加、相减，并将结果输入；目录1 1. .引言2 2 . .需求分析3 3 . .概要设计4 4 . .详细设计5 5 . .测试结果6 6 . .调试分析7 7 . .设计体会8 8 . .结束语：引言：通过C语言使用链式存储结构实现一元多项式加法、 减法和乘法的运算。 按指数降序排列。二：需求分析建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果三：概要设计存储结构：一元多项式的表示在计算机内可以用链表来表示，为了

2、节省存储空间,只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。1 .单连表的抽象数据类型定义：ADTList数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitList(&L)/操作结果：构造一个空的线性表CreatPolyn(&L)/操作结果：构造一个以单连表存储的多项试DispPolyn(L)/操作结果：显

3、示多项试Polyn(&pa,&pb)/操作结果：显示两个多项试相加，相减的结果ADTList2.本程序包含模块：typedefstructLNode/定义单链表LNode,*LinkList;voidInitList(LinkList&L)/voidCreatPolyn(LinkList&L)/voidDispPolyn(LinkListL)/定义一个空表用单链表定义一个多项式显示输入的多项式voidPolyn(LinkList&pa,LinkList&pb)()voidmain()(/定义一个单连表；coutendl*欢迎来到一元多项式计算程序

4、LNode*L1,*L2;Polyn(L1,L2);2.1力口，减操作模块一一实现加减操作各模块之间的调用关系如下：主程序模块加法操作模块减法操作模块基本算法：1、输入输出(1)功能：将要进行运算的多项式输入输出。(2)数据流入：要输入的多项式的系数与指数。(3)数据流出：合并同类项后的多项式。(4)程序流程图：多项式输入流程图如图1所示。(5)测试要点：输入的多项式是否正确，若输入错误则重新输入* endl;图表12、多项式的加法(1)功能：将两多项式相加。(2)数据流入：输入函数。(3)数据流出：多项式相加后的结果。(4)程序流程图：多项式的加法流程图如图2所小。(5)测试要点：两多项式是

5、否为空，为空则提示重新输入，否则，进行运算。图表23、多项式的减法(1)功能：将两多项式相减。(2)数据流入：调用输入函数。(3)数据流出：多项式相减后的结果。(4)程序流程图：多项式的减法流程图如图3所小。(5)测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运图表3四.详细设计.根据题目要求采用单连表存储结构typedefstructLNode/定义单链表voidPolyn(LinkList&pa,LinkList&pb)(.主函数mainvoidmain()(LNode*L1,*L2;Polyn(L1,L2);.函数的调用关系层次结构多项式Polyn用单链表定义

6、多项式CreatPolyn定义一个空表InitList显示输入的多项式DispPolyn五.调试分析采用单连表形式按照指数降序排列建立并输出多项式； 在相加， 相减的过程中如果指数相同就执行系数相加，相减，否则就把大的项直接写入。完成两个多项式的相加、相减；将从新得到的单连表结果输出；该算法的时间复杂度为两个多项式的项式之和六：调试结果.测试的数据及结果(LNode,*LinkList;voidInitList(LinkList&L)/(voidCreatPolyn(LinkList&L)/(voidDispPolyn(LinkListL)/(定义一个空表用单链表定义一个多项式

7、显示输入的多项式114X15+13X14+12X1356X67+45X4656XA67+45XA46+14XA15+13XA14+12XA133-56XA67-45XA46+14XA15+13X14+12X134keytocontinue.算法的时间复杂度及改进算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+n减法运算的时间复杂度为O(m-n),其中mn分别表示二个一元多项式的项数。问题和改进思想：在设计该算法时，出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常

8、那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后先做一个节点的排序函数，通过对链表排序后再进行之后加减运算。七.心、得体会：一元多项式计算是一个的单链表的运用，通过这个程序可以测我们以前的学习情况，看看我们是否对单链表真正的理解。一元多项式计算器的基本功能定为：(1)建立多项式(2)输出多项式(3)两个多项式相加，建立并输出和多项式(4)两个多项式相减，建立并输出差多项式能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出;乍:由a ah h费式亍页页的项数：3小入堂1项的系

9、数与揖数：12市入篁2项的素数与指数：13小入第3项的素数与轴数：14131415正入h的项数：2市入篁1项的系数与揖数:45弥入甯2项的素数与指数：5646671.输出多项式a和h2.建立多项式a+b3.建立多项式a-b结束语:时间过的很快，在不知不觉中，课程设计也接近了尾声.说起课程设计，我认为最重要的就是做好设计的预习，并且认真的去复习以前的知识和查各种资料同时认真的研究老师给的题目，老师对题目的讲解要一丝不苟的去听去想，因为只有都明白了，做起设计来才会有底，有信心。课程设计是一门培养学生综合运用所学知识，发现，提出，分析和解决实际问题的学科，它能充分锻炼我们的动手能力，时我们实践能力的

10、重要环节，是对学生实际工作能力的具体训练和考察过程。我想这次不只是一次简单的课程设计，更体现了数据结构算法和生活的紧密联系。生活中也存在许多与数据结构有关联的事情，它让人不得不深思，这一个学期的学习，这两年来的大学学习生涯，自己究竟学会了什么，掌握了多少，我也不清楚，我以前也疯狂的玩过，现在才知道自己时多么的缺乏知识，大多数问题自己不能解决，感觉将来自己是否能胜任以后作编译人员的职位。我想大家都心里都有很多的感触。对于自己，我想我已经认识到了自己的不足，在今后的学习过程中，我一定以最好的心态去对待，以最好的面貌来迎接大三的软件专业课程，并且经常上机调试，坚持理论与实践相结合。相信自己将会有很大

11、的进步。附录详细设计#include#includetypedefstructPolynomialfloatcoef;intexpn;structPolynomial*next;*Polyn,Polynomial;/PolynvoidInsert(Polynp,Polynh)if(p-coef=0)free(p);/elsePolynq1,q2;q1=h;q2=h-next;while(q2&p-expnexpn)/查找插入位置q1=q2;q2=q2-next;if(q2&p-expn=q2-expn)/将指数相同相合并q2-coef+=p-coef;free(p);为结点指针

12、类型系数为0的话释放结点if(!q2-coef)/系数为0的话释放结点q1-next=q2-next;free(q2);else/指数为新时将结点插入p-next=q2;q1-next=p;/InsertPolynCreatePolyn(Polynhead,intm)/建立一个头指针为head、项数为m的一元多项式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial);head-next=NULL;for(i=0;icoef,&p-expn);Insert(p,head);/调用Insert函数插入结点returnhead;/

13、CreatePolynvoidDestroyPolyn(Polynp)/销毁多项式pPolynq1,q2;q1=p-next;q2=q1-next;while(q1-next)free(q1);q1=q2;/指针后移q2=q2-next;voidPrintPolyn(PolynP)Polynq=P-next;intflag=1;/项数计数器if(!q)/若多项式为空，输出0putchar(0);printf(n);return;while(q)if(q-coef0&flag!=1)putchar(+);/系数大于0且不是第一项if(q-coef!=1&q-coef!=-1)/系

14、数非1或-1的普通情况printf(%g”,q-coef);if(q-expn=1)putchar(X);elseif(q-expn)printf(XA%d,q-expn);elseif(q-coef=1)if(!q-expn)putchar(1);elseif(q-expn=1)putchar(X);elseprintf(XA%d,q-expn);)if(q-coef=-1)if(!q-expn)printf(-1);elseif(q-expn=1)printf(-X);elseprintf(-XA%d,q-expn);)q=q-next;flag+;/whileprintf(n);/Pri

15、ntPolynintcompare(Polyna,Polynb)if(a&b)if(!b|a-expnb-expn)return1;elseif(!a|a-expnexpn)return-1;elsereturn0;elseif(!a&b)return-1;/a多项式已空，但b多项式非空elsereturn1;/b多项式已空，但a多项式非空/comparePolynAddPolyn(Polynpa,Polynpb)/求解并建立多项式a+b,返回其头指针Polynqa=pa-next;Polynqb=pb-next;Polynheadc,hc,qc;hc=(Polyn)mallo

16、c(sizeof(structPolynomial);/hc-next=NULL;headc=hc;while(qa|qb)qc=(Polyn)malloc(sizeof(structPolynomial);switch(compare(qa,qb)case1:qc-coef=qa-coef;qc-expn=qa-expn;建立头结点qa=qa-next;break;case0:qc-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

17、=qb-next;break;/switchif(qc-coef!=0)hc-next=qc;hc=qc;)elsefree(qc);/当相加系数为0时，释放该结点/whilereturnheadc;/AddPolynPolynSubtractPolyn(Polynpa,Polynpb)/求解并建立多项式a+b,返回其头指针Polynh=pb;Polynp=pb-next;Polynpd;while(p)/将pb的系数取反p-coef*=-1;p=p-next;pd=AddPolyn(pa,h);for(p=h-next;p;p=p-next)/恢复pb的系数p-coef*=-1;return

18、pd;/SubtractPolynintmain()intm,n,flag=0;floatx;Polynpa=0,pb=0,pc,pd,pe,pf;/定义各式的头指针，pa与pb在使用前付初值NULLprintf(请输入a的项数:);scanf(%d,&m);pa=CreatePolyn(pa,m);/建立多项式aprintf(请输入b的项数:);scanf(%d,&n);pb=CreatePolyn(pb,n);/建立多项式a/输出菜单printf(*n);printf(操作提示：nt1.输出多项式a和bnt2.建立多项式a+bnt3.建立多项式a-bn);printf(t4.n*n);for(;flag=0)scanf(%d”,&flag);if(flag=1);PrintPolyn(pb);continue;if(flag=2)pc=AddPolyn(pa,pb);printf(多项式