一元稀疏多项式计算器数据结构预习报告.doc

《一元稀疏多项式计算器数据结构预习报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构预习报告学号0061姓名任旭辉一、实验题目一元稀疏多项式计算器二、基本要求求分析1、一元稀疏多项式简单计算器的功能是：1.1输入并建立多项式；1.2输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；1.3多项式a和b相加，建立多项式a+b；1.4多项式a和b相减，建立多项式a-b。1.5多项式求值1.6求多项式的导函数；1.4多项式a和b相乘2、设计思路:2.1定义线性表的动态分配顺序存储结构；2.2建立多项式存储结构，定义指针

2、*next2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en3、设计思路分析要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为序数coef指数expn指针域next

3、运用尾插法建立两条单链表，以单链表polynp和polynh分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polynp中的结点插入到单链表polynh中），因此“和多项式”中的结点无须另生成。为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：①若p->expnexpn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。②若p->expn=q->expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。③若p->expn>q

4、->expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。三、测试数据：1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15)=(-7.8x^15-1.2x^9+12x^-3-x);3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);4、(x+x^3)+(-x-x

5、^3)=0;5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200);6、(x+x^2+x^3)+0=x+x^2+x^3.7、互换上述测试数据前后两个多项式四、概要设计1、元素类型、结点类型和指针类型：typedefstructPolynomial{floatcoef;//系数intexpn;//指数structPolynomial*next;}*Polyn,Polynomial;2、建立一个头指针为head、项数为m的一元多项式,建立新结点以接收数据,调用Insert函数插入结点:PolynCreatePoly

6、n(Polynhead,intm){inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;icoef,&p->expn);Insert(p,head);}returnhead;}3、主函数和其他函数：voidmain(){intm,n,a,x

7、;charflag;Polynpa=0,pb=0,pc;}floatValuePolyn(Polynhead,intx)//输入x值，计算并返回多项式的值五、调用关系图（图1）六、程序代码：#include#include//定义多项式的项typedefstructPolynomial{floatcoef;//系数intexpn;//指数structPolynomial*next;}*Polyn,Polynomial;voidInsert(Polynp,Polynh){if(p->coef==0)fre

8、e(p);//系数为0的话释放结点else{Polynq1,q2;q1=h;q2=h->next;while(q2&&p->expnexpn){//查找插入位置q1=q