数据结构实验报告《一多项式及其运用》.docVIP

中南大学物理学院 数据结构实验报告- - - - 一元多项式相加及其运用 专业班级：电信0903 时间：2010年10月18日数据结构实验报告---- 一元多项式相加及其运用 【问题描述】 设计一个一元稀疏多项式简单计算器 【基本要求】 一元稀疏多项式简单计算器的功能是： （1）输入并建立多项式； （2）输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多 项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； （3）多项式a和b相加，建立多项式a+b； （4）多项式a和b相减，建立多项式a-b。 【运用拓展】 计算多项式在x处的值； 多项式a和b相乘，建立乘积多项式ab； 计算器的仿真友好界面。 【设计思路分析】 （1）解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表。 （2）运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题 （3）设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则： ① 若p-expnq-expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。 ② 若p-expn=q-expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。 ③ 若p-expnq-expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。 【 测试数据】 多项式a：6x+3x^5-7.1x^11 多项式b: 2-5x^5+11x^9 若计算a+b则有:(6x+3x^5-7.1x^11)+(2-5x^5+11x^9)=(-7.1x^11+11x^9-2x^5+6x+2)等。 【操作界面显示】 1：建立多项式的操作： 2：输出多项式及计算x的值 3：进行运算操作： 4：结束程序： 【程序代码】 #includestdio.h //调用输入输出函数 #includestdlib.h typedef struct Polynomial //定义一个Polyn结构体 { float coef; int exp; //系数指定为浮点型，指数指定为整型 struct Polynomial *next; }*Polyn,Polynomial; void Insert(Polyn p,Polyn h){ //查找位置插入新链节 if(p-coef==0) free(p); //p系数为0的话释放结点 else{ //否则查找插入位置 Polyn q1,q2; q1=h; q2=h-next; while(q2 p-exp q2-exp) //指数较大则插前面 { q1=q2; q2=q2-next; } if(q2 p-exp == q2-exp) //将指数相同相合并 { q2-coef += p-coef; free(p); if(!q2-coef) //系数为0的话释放结点 { q1-next=q2-next; free(q2); } } else { p-next=q2; q1-next=p;} //指数为新时将结点插入 }//第一个else } //void Insert Polyn CreatePolyn(Polyn head,int m){ //建立一个头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Pol