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

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

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

3、n(&pa,&pb)/操作结果：显示两个多项试相加，相减的结果 ADT List2 . 本程序包含模块：typedef struct LNode /定义单链表LNode,*LinkList;void InitList(LinkList &L) / void CreatPolyn(LinkList &L) / void DispPolyn(LinkList L) /定义一个空表用单链表定义一个多项式显示输入的多项式void Polyn(LinkList &pa,LinkList &pb)void main()/定义一个单连表；cout<<

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

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

6、Polyn(LinkList &L) / void DispPolyn(LinkList L) / 定义一个空表用单链表定义一个多项式显示输入的多项式void Polyn(LinkList &pa,LinkList &pb)2 .主函数main void main()LNode *L1,*L2;Polyn(L1,L2);3 .函数的调用关系层次结构多项式Polyn用单链表定义多项式CreatPolyn定义一个空表InitList 显示输入的多项式DispPolyn五.调试分析采用单连表形式按照指数降序排列建立并输出多项式；在相加，相减的过 程中如果指数相同就执行系数相加

7、，相减，否则就把大的项直接写入。完成两 个多 项式的相加、相减；将从新得到的单连表结果输出；该算法的时间复杂度为 两个多项式的项式之和六：调试结果1 .测试的数据及结果仅 C: Progra> FilesMicrosoft Visual 5t11(1:1口?1>工口1©(:13一兀多项式的加，减ii小心映魏：31314154667小入堂1项的系数与揖数：12 市入篁2项的素数与指数：13 小入第3项的家数与指数:14正入h的项数：2市入篁1项的系数与揖数:45 弥入甯2项的素数与指数：56臊作提示：1.输出多项式a和h2 .建立多项式a+b3 .建立多项式a-b4 .退出

8、作a:b:作a+作a-作an 行项项行项行项行es 多希另另PP114XA15+13XA14+12XA1356X67+45X462：56XA67+45XA46+14XA15+13XA14+12XA133：-56XA67-45XA46+14XA15+13X14+12X13 4key to continue2.算法的时间复杂度及改进算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+。减法运算的时间复杂度为 O(m-n),其中旦n分别表示二个一元多项式的项 数。问题和改进思想：在设计该算法时，出现了一些问题，例如在建立链表时头指针 的设立导致了之后运用到相关的指针时没能很好的移动指针出现了

9、数据重复输 出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通 过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较 插入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后先做一个 节点的排序函数，通过对链表排序后再进行之后加减运算。七.心、得体会：一元多项式计算是一个的单链表的运用，通过这个程序可以测我们以前的学习情况，看看我们是否对单链表真正的理解。一元多项式计算器的基本功能定为：(1)建立多项式(2)输出多项式(3)两个多项式相加，建立并输出和多项式(4)两个多项式相减，建立并输出差多项式能够按照指数降序排列建立并输出 多项式；能够完成两个多

10、项式的相加、相减，并将结果输出；结束语:时间过的很快，在不知不觉中，课程设计也接近了尾声 .说起课程设计，我认为 最重要的就是做好设计的预习，并且认真的去复习以前的知识和查各种资料同时 认真的研究老师给的题目，老师对题目的讲解要一丝不苟的去听去想， 因为只有 都明白了，做起设计来才会有底，有信心。课程设计是一门培养学生综合运用所 学知识，发现，提出，分析和解决实际问题的学科，它能充分锻炼我们的动手能力， 时我们实践能力的重要环节，是对学生实际工作能力的具体训练和考 察过程。我 想这次不只是一次简单的课程设计，更体现了数据结构算法和生活的紧密联系。生活中也存在许多与数据结构有关联的事情， 它让人

11、不得不深思，这一个学期的 学习，这两年来的大学学习生涯，自己究竟学会了什么，掌握了多少，我也不清 楚，我以前也疯狂的玩过，现在才知道自己时多么的缺乏知识， 大多数问题自己 不能解决，感觉将来自己是否能胜任以后作编译人员的职位。 我想大家都心里都 有很多的感触。对于自己，我想我已经认识到了自己的不足， 在今后的学习过程 中，我一定以最好的心态去对待，以最好的面貌来迎接大三的软件专业课程， 并 且经常上机调试，坚持理论与实践相结合。相信自己将会有很大的进步。附录详细设计#include<stdio.h>#include<malloc.h>typedef struct Pol

12、ynomialfloat coef;int expn;struct Polynomial *next;为结点指针类型系数为0的话释放结点查找插入位置*Polyn,Polynomial;/Polynvoid Insert(Polyn p,Polyn h)if(p->coef=0) free(p); /elsePolyn q1,q2;q1=h;q2=h->next;while(q2&&p->expn<q2->expn) /q1=q2;q2=q2->next;if(q2&&p->expn=q2->expn) /将指数相同

13、相合并q2->coef+=p->coef;free(p)；if(!q2->coef)/系数为0的话释放结点q1->next=q2->next;free(q2);else/指数为新时将结点插入p->next=q2;q1->next=p;/InsertPolyn CreatePolyn(Polyn head,int m)/建立一个头指针为head、项数为m的一元多项式int i;Polyn p;p=head=(Polyn)malloc(sizeof(struct Polynomial);head->next=NULL;for(i=0;i<m;i

14、+)p=(Polyn)malloc(sizeof(struct Polynomial);/建立新结点以接收数据printf("请输入第曲的系数与指数:",i+1);scanf("%f %d",&p->coef,&p->expn);Insert(p,head); / 调用Insert 函数插入结点return head;/CreatePolynvoid DestroyPolyn(Polyn p)/销毁多项式 pPolyn q1,q2;q1=p->next;q2=q1->next;while(q1->next)f

15、ree(q1);q1=q2;/指针后移q2=q2->next;void PrintPolyn(Polyn P)Polyn q=P->next;int flag=1;/项数计数器if(!q) /若多项式为空，输出0putchar('O');printf("n");return;while (q)if(q->coef>0&&flag!=1) putchar('+'); /系数大于 0 且不是第一项if(q->coef!=1&&q->coef!=-1)/ 系数非 1 或-1 的普通

16、情况 printf("%g”,q->coef);if(q->expn=1) putchar('X');else if(q->expn) printf("XA%d",q->expn);elseif(q->coef=1)if(!q->expn) putchar('l');else if(q->expn=1) putchar('X');else printf("XA%d",q->expn);if(q->coef=-1)if(!q->expn)

17、printf("-1");else if(q->expn=1) printf("-X");else printf("-XA%d",q->expn);q=q->next;flag+；/whileprintf("n");/PrintPolynint compare(Polyn a,Polyn b)if(a&&b)if(!b|a->expn>b->expn) return 1;else if(!a|a->expn<b->expn) return -1;

18、else return 0;else if(!a&&b) return -1;/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,hc,qc;建立头结点hc=(Polyn)malloc(sizeof(struct Polynomial);/hc->next=NULL;headc=hc;while(qa|q

19、b)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: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

20、;qb=qb->next;break;switchif(qc->coef!=0)qc->next=hc->next;hc->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*=-1;p=p->next;pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next) / 恢复 pb 的系数p->coef*=-1;return pd;/SubtractPolynint main()int m,n,flag=0;float x;Polyn pa=0,pb=0,pc,pd,pe,pf;/定义各式的头指针，pa与pb在使用前付初值NULLprintf(" 请输入a的项数:");scanf("%d",&m);pa=CreatePolyn(pa,m);/建立多项式 aprintf("