《实验报告一元多项式》由会员分享，可在线阅读，更多相关《实验报告一元多项式（18页珍藏版）》请在金锄头文库上搜索。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划实验报告一元多项式数据结构实验报告实验名称：实验1一元多项式Polynomial学生姓名：孙广东班级：XX班内序号：08学号：XX日期：XX年11月1日1实验要求实验目的：1.熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、异常处理的使用3.掌握单链表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容：利用线性表实现一个一元多项式Polynomialf(x)=a0+a1x+a2x2+a3x3+anxn要求：1能够实现一元多项式的输入和输出2能够进行一元多
2、项式相加3能够进行一元多项式相减4能够计算一元多项式在x处的值5能够计算一元多项式的导数6能够进行一元多项式相乘7编写测试main()函数测试线性表的正确性2.程序分析由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是带头结点的单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，程序的时间空间复杂度增加，而且顺序表的结点个数动态增加不便，因为决定采用单链表的方式解决。本程序完成的主要功能：1.输入和输出：需要输入的信息有多项式的系数和指数，用来向系统动态申请内存；系数和指数用来构造每个结点，形成链
3、表。在构造链表的时候我添加了出泡排序以及合并同类项的功能，因此输入时没有要求。输出即是将多项式的内容向屏幕输出。2.多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别考虑可能出现的不同情况。将每项运算得到的结果都插入到新的链表中，形成结果多项式。多项式相减可视为加上第二个多项式的相反数。3.多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果更新到结果多项式的链表中。4.多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。存储结构2申请动态内存创建新结点；3输入各项的系数以
4、及指数，分别存入coef和expn；4再将输入的系数以及指数赋给每一个结点的coef和expn域，直到输入系数为0时结束；5利用头插法将每个结点加入链表，形成一元多项式链表。6循环输入：直到系数为0伪代码：1.element*s=newelement;2.s-coef=mod;3.s-exp=ind;4.s-next=front-next;5.front-next=s;6.cinmodind;7.运用头插法将结点插入链表。时间复杂度：o(n)/n为链表长度空间复杂度：o(n)冒泡排序算法:for(inti=0;inext;4for(intj=0;jnext;if(p-expp-next-exp
5、)q-next=p-next;p-next=p-next-next;q-next-next=p;elsep=p-next;时间复杂度：o(n2);空间复杂度：o(1);合并同类项算法：1.从头遍历每一个结点，比较前后2个结点中exp的值大小2.前结点的exp比后一个小，继续向后遍历3.前结点的exp与后一个相等，合并，删掉后一个结点，继续遍历4.遍历到最后一个结点时结束1element*l=front-next;2while(l-next!=NULL)34if(l-exp=l-next-exp)56l-coef+=l-next-coef;7element*temp=l-next;8l-next
6、=temp-next;9deletetemp;1011else12l=l-next;13时间复杂度：O(n)/n为链表长度空间复杂度：O(1)输出多项式算法自然语言描述：1.获取头结点；2.循环n-1次将指针的指向后移；依照多项式的各种情况，设置输出方式，当下一项系数为负时，不输出+号，否则输出+号伪代码描述：1element*p=front-next;2while(p!=NULL)34if(p-coef)56coutcoefexp;7if(p-next!=NULL&p-next-coef0)8coutnext;时间复杂度：O(n)空间复杂度：o(1)多项式的相加相减自然语言描述：1初始化工作
7、指针p和q,以及p节点前驱节点指针p_prior2若p和q都不为空,则循环以下操作:若p-,则p_prior=p;p=p-nenx;否则,若p-q-,则:将q结点加入到A链表p结点之前q指向B链表的下一个结点否则:p-=p-+q-;若p-为0,则删除结点pp指向下一个结点删除q结点q指向下一个结点3若p为空并且q不为空,则将q结点及其后所有结点追加到A链表的最后端4将B链表制成空链表伪代码描述：1.若p-expexp(1)q结点不变(2)p结点向下移(1)pre=p;(2)p=p-next;2.若p-expq-exp执行一下主要操作步骤(1)pre-next=q;(2)pre=q;(3)q=q
8、-next;(4)pre-next=p;示意图:3.若p-exp=q-exp执行以下操作步骤:(a)若合并系数为零,则删除p结点,主要步骤:(1)pre-next=p-next;(2)deletep;(3)p=pre-next;(4)Node*temp=q;(5)q=q-next;(6)deletetemp;示意图:一元多项式相加问题一问题描述设计算法实现一元多项式的简单运算。二数据结构设计分析任意一元多项式的描述方法可知，一个一元多项式的每一个子项都由“系数-指数”两部分组成，所以可以将它抽象成一个由“系数-指数对”构成的线性表。基于这样的分析，可以采用一个带有头结点的单链表来表示一个一元多
9、项式。具体数据类型定义为：typedefstructnodefloatcofe;/系数域intexp;/指数域structnode*next;/指针域指向下一个子项*polynode,poly;Polynodehead_a,head_b,head_c;这三个指针分别作为链表A，B和C的头指针。三功能设计1.输入并建立多项式的功能模块此模块要求按照“系数-指数对”的输入格式输入各个子项，输入一个子项，通过遍历链表比较指数的大小，将新结点插在合适的位置，使多项式的指数按递增的顺序存储。当遇到输入结束标志是停止输入，而转去执行程序下面的部分。具体函数构造为：polynodecreat_polynod
10、e()polynodeA,p,q,s;/建立这种类型的头指针，尾指针，遍历指针和动态指针floata;intb;A=newpoly;A-next=NULL;q=A;p=A;cina;cinb;while(a!=0|b!=0)s=newpoly;s-cofe=a;s-exp=b;while(q-next)if(q-next-expnext;/遍历链表，若指数大于原链表指数，指针后移一个elses-next=q-next;q-next=s;break;/若不是，将结点插入指针后面if(q-next=NULL)s-next=p-next;p-next=s;p=s;/q遍历到链表尾仍未插入，将结点插入
11、最后，改变尾指针使其指向新结点cina;cinb;q=A;/让q返回头指针处，以便下一次遍历链表if(p!=NULL)p-next=NULL;returnA;2.多项式相加的功能模块此模块根据在1中建立的两个多项式进行相加运算，并存放在以C为头指针的一个新链表中。可以采用如下方法进行设计：设指针p,q,r分别指向描述多项式的链表A,B,C头部，比较p-exp与q-exp；若p-exp小，则做如下操作：while(p!=NULL&q!=NULL)/在两个指针不为空的情况下循环r-exp=p-exp;r-next=s-next;s-next=r;s=r;r=newpoly;if(p-expexp)
12、r-cofe=p-cofe;if(r-cofe=0)deleter;p=p-next;continue;/若r指向的系数为，则p前进，释放r并强制执行下一次p=p-next;/p指针指向的指数小，将此结点赋给r，p指针前进若p-exp=q-&g(来自:写论文网:实验报告一元多项式)t;exp，则：elseif(p-exp=q-exp)r-cofe=p-cofe+q-cofe;/若两指针指数部分相等，则系数相加赋给rif(r-cofe=0)deleter;p=p-next;q=q-next;continue;r-exp=p-exp;r-next=s-next;s-next=r;s=r;p=p-n
13、ext;q=q-next;/两指针均前进若p-expq-exp,则：elseif(p-expq-exp)r-cofe=q-cofe;if(r-cofe=0)deleter;q=q-next;continue;r-exp=q-exp;r-next=s-next;s-next=r;s=r;q=q-next;在两个指针中有一个为空以后，可以进行如下操作将多项式中剩余项赋到C中：while(p=NULL&q!=NULL)式r=newpoly;r-cofe=q-cofe;r-exp=q-exp;r-next=s-next;s-next=r;s=r;q=q-next;/若有一个多项式已经结束则把另一个多项式的值赋给新多项while(q=NULL&p!=NULL)r=newpoly;r-cofe=p-cofe;r-exp=p-exp;r-next=
