数据结构实验4-1

数据结构实验报告实验一一元多项式的表示和相减、相乘实验人：学号:时间：一、实验目的1.掌握链表的存储方式2.掌握一元多项式的存储及运算。二、实验内容已知一元多项式P(x)和Q(x)已存在，求P(x)-Q(x)和P(x)*Q(x)并输出。要求：1.通过键盘随机输入两多项式P(x)和Q(x)的内容。2.输出结果要有P(x)和Q(x)的以及它们的差P(x)-Q(x)和乘积P(x)*Q(x)。三、实验步骤：1.创建一元多项P(x)和Q(x)。2.求P(x)-Q(x)，P(x)*Q(x)。3.输出P(x)、Q(x)、P(x)-Q(x)，P(x)*Q(x)。四、算法说明首先，定义一元多项式的存储方式，然后从键盘输入P(x)和Q(x)对应多项式的各对系数和指数，建立相应的一元多项式；其次进行多项数加法时，新建一个存储结果的链表，分别将两多项式各项依次插入结果多项式即完成多项式相加运算，得到P(x)+Q(x)的结果；进行多项数加法时，将减项多项式各项系数化为相反数后进行加法操作，即完成多项式相减运算，得到P(x)-Q(x)的结果。最后进行多项式乘法时，创建双循环结构，将两多项式各项依次相乘，并将每两项相乘结果有序插入到储存运算结果的多项式链表中，最后得到P(x)*Q(x)的结果。五、测试结果参考下图（测试数值不要一样）数据结构实验报告六、源代码#includestdio.h#includemalloc.htypedefstruct{floatcoef;//多项式的系数intexpn;//多项式的指数}ElemType;typedefstructLNode{//结点类型ElemTypedata;structLNode*next;}*LinkList;//线性表的单链表存储结构voidMakeNode(LinkList&s,ElemTypee){//生成结点s=(LinkList)malloc(sizeof(LNode));s-data=e;}voidInsAfter(LinkListp,LinkLists){//插入结点s-next=p-next;p-next=s;}intcompare(ElemTypee1,ElemTypee2){//比较if(e1.expne2.expn)return1;elseif(e1.expne2.expn)return-1;return0;}voidOrderInsert(LinkList&L,ElemTypee,int(*compare)(ElemType,ElemType)){//有序插入LinkListp=L,q=p-next,s;intn;while(q){数据结构实验报告n=compare(e,q-data);if(n0){MakeNode(s,e);InsAfter(p,s);break;}elseif(n==0){q-data.coef=q-data.coef+e.coef;if(q-data.coef==0){p-next=q-next;free(q);}break;}p=p-next;q=p-next;}if(q==NULL){MakeNode(s,e);InsAfter(p,s);//最大，放在最后一个位置}}voidIntList(LinkList&L){//初始化链表L=(LinkList)malloc(sizeof(LNode));L-next=NULL;}voidSetCurElem(LinkList&L,ElemTypee){//设置结点L-data.coef=e.coef;L-data.expn=e.expn;}voidCreatePolyn(LinkList&L,intm){ElemTypee;e.coef=0.0;e.expn=-1;IntList(L);SetCurElem(L,e);//设置头结点的数据元素printf(请输入%d对多项式的值：\n,m);for(inti=1;i=m;i++){数据结构实验报告scanf(%f%d,&e.coef,&e.expn);//输入值OrderInsert(L,e,compare);}}voidshow(LinkListL){//输出方法LinkListp=L-next;if(p){//第一个输出printf(%.2fX^%d,p-data.coef,p-data.expn);p=p-next;}while(p){if(p-data.coef0)printf(+);printf(%.2fX^%d,p-data.coef,p-data.expn);p=p-next;}printf(\n);}voidListDestory(LinkList&L){//销毁LinkListp=L,q;while(p){q=p;p=p-next;free(q);}}voidAdd(LinkListL1,LinkListL2,LinkList&L3){//多项式相加ElemTypee;intn;IntList(L3);e.coef=0.0;e.expn=-1;SetCurElem(L3,e);//设置头结点的数据元素LinkListp1=L1-next,p2=L2-next,q;//r1始终指向新建链表的尾部,p1和p2表示当前结点while(p1&&p2){n=compare(p1-data,p2-data);数据结构实验报告switch(n){case-1:{OrderInsert(L3,p1-data,compare);p1=p1-next;break;}//L1中的值小，插入之case1:{OrderInsert(L3,p2-data,compare);p2=p2-next;break;}//L2中的值小，插入之case0:{//相同e.coef=p1-data.coef+p2-data.coef;e.expn=p1-data.expn;if(e.coef!=0){OrderInsert(L3,e,compare);}p1=p1-next;p2=p2-next;break;}}}if(p1){OrderInsert(L3,p1-data,compare);p1=p1-next;}//添加L1elseif(p2){OrderInsert(L3,p2-data,compare);p2=p2-next;}//添加L2}voidsubtract(LinkListL1,LinkListL2,LinkList&L4){//多项式相减LinkListp2=L2-next;LinkListL0;intn=0;while(p2){n++;p2=p2-next;}IntList(L0);ElemTypee;e.coef=0.0;e.expn=-1;SetCurElem(L0,e);for(inti=1;i=n;i++){e.expn++;OrderInsert(L0,e,compare);}LinkListp0=L0-next;数据结构实验报告p2=L2-next;while(p2){p0-data.coef=-p2-data.coef;p0-data.expn=p2-data.expn;p2=p2-next;p0=p0-next;}Add(L1,L0,L4);}voidMultiply(LinkListL1,LinkListL2,LinkList&L5){//多项式相乘ElemTypee;intn;IntList(L5);e.coef=0.0;e.expn=-1;SetCurElem(L5,e);//设置头结点的数据元素LinkListp1=L1-next,p2=L2-next,q;//r1始终指向新建链表的尾部,p1和p2表示当前结点while(p1){p2=L2-next;while(p2){e.coef=p1-data.coef*p2-data.coef;e.expn=p1-data.expn+p2-data.expn;OrderInsert(L5,e,compare);p2=p2-next;}p1=p1-next;}}intmain(){LinkListL1,L2,L3,L4,L5;intm,n;printf(请输入多项式P(X)的项数：);scanf(%d,&m);CreatePolyn(L1,m);printf(多项式P(X)为：\n);show(L1);数据结构实验报告printf(请输入多项式Q(X)的项数：);scanf(%d,&n);CreatePolyn(L2,n);printf(多项式Q(X)为：\n);show(L2);Add(L1,L2,L3);printf(多项式P(X)+Q(X)为：\n);show(L3);subtract(L1,L2,L4);printf(多项式P(X)-Q(X)为：\n);show(L4);Multiply(L1,L2,L5);printf(多项式P(X)*Q(X)为：\n);show(L5);return0;}七、分析总结经过这次课程设计，我深刻认识到算法在程序设计中的重要性，一个完整的程序总是由若干个函数构成的，这些相应的函数体现了算法的基本思想。一开始创建多项式并没有遇到什么问题，但是减法运算开始遇到问题，经过调试和反复尝试后问题得以解决。在多项式相加的基础上进行修改，多项式相减和多项式相乘就容易得多。多项式相减的运算主要是整体把另一个多项式前加一个负号，其他和相加运算的写法大同小异。多项式相乘的运算，则需要两个循环进行操作，第一个多项式中的一个单项式与第二个多项式中的各个单项式相乘，再回上去第一个多项式的第二个单项式与第二个多项式中的各个单项式相乘，如此循环。全部相乘完毕之后，形成第三个多项式，还要比较各系数进行合并。多项式相减与多项式相乘的一个共同点是都要比较各系数进行合并，用case循环。此次上机实验应用了线性表实现了一次实际操作，完成了一个一元多项式的简单计算器，不仅对此次编译程序的算法有了新的认识，还让我深刻的体会到了线性表的重要性以及其应用的方便，并且书中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。