数据结构线性表多项式加减实验报告

数据结构实验报告实验名称：实验一——线性表日期：2013年10月28日实验要求实验目的熟悉C++语言的根本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力实验内容利用线性表实现一个一元多项式Polynomialf(x)=a0+a1x+a2x2+a3x3+…+anxnPolynomial的结点结构如下：structterm{floatcoef;//系数intexpn;//指数};要求：能够实现一元多项式的输入和输出能够进行一元多项式相加能够进行一元多项式相减能够计算一元多项式在x处的值能够计算一元多项式的导数〔选作〕能够进行一元多项式相乘〔选作〕编写测试main()函数测试线性表的正确性2.程序分析考虑到数据结构的实现，因为多项式是线性结构因此选择线性表，而本次实验中涉及到多项式的加减，要进行节点的添加或者删除，用顺序表显然不能满足要求，而且由于不知道多项式的项数，很容易造成空间的浪费，当两个多项式指数相差很远时，操作要移动很多项，步骤很麻烦繁琐。综上，我选择了单链表，每个节点有三个局部，分别储存系数、指数、和指针，这样在计算加减或者指数不等时，只需要简单的摘连加链即可，而且不会造成空间的太多浪费。每次利用尾插法将结点插入基准多项式。2.1存储结构本次实验采取的多项式加减算法是将一个多项式作为基准，把另一个多项式加到基准多项式中去，求和后的多项式仍然存储在第一个线性表中，因此用单链表的数据结构更为方便。单链表存储结构非空链表空链表非空链表空链表在本次实验中，因为形式的特殊性，每个节点如下列图表示：空链表frontΛ…frontΛ……frontΛ其中每个结点前两个分别储存float型系数coef和int型指数expn，第三个作为指针指向下一个节点〔不是最后一个结点时，否那么为NUll〕2.2关键算法分析1、输入多项式自然语言描述：指定多项式的项数n建立一个叫term的struct结构类型，用来储存指定多项式的系数和指数的数据。设置一个term类型的结构数组ea[]。按升幂次序逐项输入多项式各项的系数和指数并存入结构数组ea[]。利用尾插法建立单链表，将数组ea[]中的数据分别赋给节点Node的coef域和exp域,最后一个节点指空。伪代码：输入项数n输入ea结构数组各项数据利用尾插法建立单链表在堆中建立新结点3.2将数据写入到新结点中Node->exp[i]=ea->exp[i];Node->coef[i]=ea->coef[i];3.3将新结点参加到链表中修改尾指针最后一个结点指为空时间复杂度O(n),空间复杂度S(n)2、输出多项式自然语言描述：得到链表的结点个数n设置工作指针f指向头结点后一个节点由于第一项前不需要加号，故单独输出第一项〔f->coef〕x^〔f->exp〕之后移动f循环遍历剩余的节点，逐项输出+〔f->coef〕x^〔f->exp〕伪代码描述：*f=first->next；2．输出〔f->coef〕x^〔f->exp〕3.1f=f->next;3.2输出+〔f->coef〕x^〔f->exp〕时间复杂度O(n)，空间复杂度S(1)3、多项式相加自然语言描述：设有两个多项式链表A和B，设置工作指针p和q分别指向其第一项假设p->exp<q->exp，那么结点p保存不变，p指向A链表的下一个结点继续比拟。假设p->exp>q->exp，那么结点q应为结果中的一个结点，将q结点参加到p结点之前，q结点指向下一个位置，继续比拟。假设p->exp=q->exp，那么p与q所指为同类项，那么为以下两种情况：合并的系数为0，那么删除p结点合并的系数不为0，将其重新赋予p结点两结点合并后可删除q结点，并将p、q分别指向下一个位置继续比拟〔a〕假设p已指空，q依然存在，那么逐项将q复制至A链表的最后；〔b〕假设q指空，那么不需再进行操作。当p、q均不存在，运算结束。伪代码描述初始化工作指针p和q，以及p结点的前驱结点指针p_prior；假设p和q都不为空，那么循环如下操作：2.1假设，那么p_prior=p;p=p->next;2.2否那么，假设，那么：2.2.1将q结点参加到A链表p结点之前；2.2.2q指向B链表下一个结点；2.3否那么：； 2.3.1假设为0，删除p结点； 2.3.2p指向下一个结点；删除q结点；q指向下一个结点；3.假设p为空且q不为空，那么将q结点及其后续所有结点追加到A链表的最后；4.将B链表置成空链表；算法时间复杂度O(n)，空间复杂度S(1)多项式相减将作为减数的多项式的系数全部变为负数，再与被减多项式相加，系数有负号时要加括号。5、赋值运算自然语言描述：输入x的值设置工作指针p指向第一项，并得到多项式项数n设置初始值为0的临时变量result设置初始值为1的临时变量temp。循环p->exp次，将temp与x相乘的结果赋值给temp将temp乘以p->coef将TempResult参加result指针p后移以上4-7步骤循环n次伪代码描述：1.得到多项式项数n，输入x的值3.intresult=0；4.1floattemp=1;4.2循环p->exp次temp*=x;4.3temp*=p->coef;4.4result+=temp;4.5p=p->next;算法时间复杂度O(n2)，空间复杂度S(1)2.3其他多项式A的输入：多项式在x点值得计算：多项式B的输入及A+B、A-B的多项式程序运行结果开始测试主函数流程：开始输入多项式A的项数输入多项式A的项数按升幂次序逐项输入A多项式各项系数和指数按升幂次序逐项输入A多项式各项系数和指数输出A输出A1111输入x的赋值输入x的赋值A做赋值运算并输出结果resultA做赋值运算并输出结果result输入多项式B的项数输入多项式B的项数输出结果dB输出结果dB按升幂次序逐项输入B多项式各项系数和指数按升幂次序逐项输入B多项式各项系数和指数输出B输出BA与B做相加运算A与B做相加运算输出结果addA与B做相减运算输出结果minus结束输出结果dA结束输出结果dA测试条件：问题规模n的数量级为1。A的项数为3。每项的系数指数分别为〔2.1，3〕〔2.2，5〕〔3.5，7〕。x的值为2.2测试结论：测试的功能有：多项式输入、多项式输出、多项式相加、多项式相减、多项式计算。均能正常完成要求。4.总结调试时出现的问题及解决的方法最初对对于结点和struct数组关系混淆，以致于无法的到有效的单链表，对于多项式的建立更无从谈起。入手之后主函数设计代码冗杂，因此有增设了两个函数setnumA和setnumB，将代码进一步简化。对于多项式具体点的计算问题，由于逻辑错误，导致计算结果有问题，后来经调整，参加float变量temp=1，解决了这个问题。多项式减法：将其转化为相反数的相加，并参加括号，成功解决了多项式的符号问题。