《数据结构实验报告完成多项式的运算.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告完成多项式的运算.docx（16页珍藏版）》请在三一文库上搜索。
1、简单介绍：本次作业力在学会链表表示线性表的插入、删除、查找等基本操作设计与实现，学习利用链表提供的接口去求解实际问题，同时熟悉链表的的存储方法。再基于线性链表的基础设计完成多项式的相加运算程序。一、 实验目的和要求完成多项式的相加、相乘运算。（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问题（3）熟悉线性表的的存储方法二、 实验内容和原理1.实验内容设计一个一元多项式的简单计算程序，其基本功能有：（1）输入并建立多项式；（2）输出多项式；（3）多项式的相加运算。利用单链表实现。2.实验原理使用单链表实现一元多项式的存储，并实现两个一元多项式的加法
2、运算。三、 实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Windows XP中文操作系统 （2）VC6.0四、 算法描述及实验步骤1、 描述：加法：输入建立一元多项式,进行简单加法运算,输出结果；通过建立单链表A和B分别存放多项式的a和b的各项系数及指数；并且利用A使得不产生新的节点而在A中存放数据运算结果；该过程通过定义指针变量p和q使它们分别指向两个多项式的第一个节点，之后依次比较它们所指向的项的指数，即一种情况指数相等时系数相加且和不为零，修改当前p所指项的系数（和），同时删除q所指项，若和为零则同时删除p和q各自所指；情况二，p当前项指数大于q当
3、前项，将q所指插入p所指之前作为结果项之一；情况三，p当前项指数小于q当前项，p所指作为多项式和的一项，移动p指向下一项，进行比较，在移动p，q至其中以个链空，把另一个链余下节点插在p所指之后；乘法：定义指针p,q指向所操作节点，通过A链表的每一项与B链表各项相乘，指数相加，系数相乘，将值赋给新节点各自域，构成一新的链表，最后返回头结点。可这样有一个问题，即新生成的链表，即最终结果混乱，没有对数据进行过滤，相同指数项应在执行加法运算，所以可以这样实现，通过A链表的每一项与B链表各项相乘的新生成节点单独构成一链表，并将第一个链表加入另一新链表，循环此操作将后生成的链表加之先前的链表，即可实现排序
4、问题。1）加法算法如下：polynomial * polyadd(polynomial *A,polynomial *B)polynomial *p,*q,*s,*r;float x;p=A-next;q=B-next;s=p;while(p!=NULL)&(q!=NULL)if(p-exp)(q-exp)r=q-next;q-next=p;s-next=q; s=q;q=r;else if(p-exp)exp)s=p;p=p-next;elsex=(p-coef)+(q-coef);/*if(x!=0)p-coef=x;s=p;elses-next=p-next;free(p);*/p=s-
5、next;r=q;q=q-next;free(r); if(q!=NULL)s-next=q;free(B); return A;2） 乘法算法polynomial * polyand(polynomial *A,polynomial *B) /*核心算法实现两链表的乘法运算*/polynomial * p,* q,* n,* head,* r,* temp,* m; /定义当前指针p，q风别指向两链表和头指针，尾指针，及新生成节点n int exp; /定义整型指数float coef; /定义浮点型系数head=(polynomial *)malloc(sizeof(polynomial)
6、; /创头节点为新生链表准备head-next=NULL; /置空链表 r=head; /临时变量，为后移指针做准备p=A-next; /当前指针跳过A链表头指向实际运算数while(p!=NULL) /控制操作，循环A链表与内部while所控制B链表进行项之间的运算 temp=(polynomial *)malloc(sizeof(polynomial); /在内部创头节点为新生链表准备 即A中每一项与B中各项相乘构成一新链表 temp-next=NULL; /置空链表 m=temp; /临时变量，为后移指针做准备q=B-next; /当前指针跳过B链表头指向实际运算数while(q!=NU
7、LL) n=(polynomial *)malloc(sizeof(polynomial); /建立新节点exp=p-exp+q-exp; /进行系数相加操作 coef=p-coef*q-coef; / /进行指数相乘操作n-coef=coef; /赋值新节点的系数域n-exp=exp; /赋值新节点的指数域 m-next=n; /链接节点至头结点，构成链表m=m-next; /后移指针，为下一节点做准备q=q-next; /控制B链表下一项/printf(%f %d ,coef,exp); /调试用p=p-next; /控制A链表下一项m-next=NULL; /链表尾置空/head=hea
8、d-next;polyadd(head,temp); /return head; 2、1）加法算法流程图polynomial *p,*q,*s,*r; float x;p=A-next;q=B-next;s=p;Y (p-exp)(q-exp) Nr=q-next;s-next=q;free(B);return A;p=s-next;r=q;q=q-next;free(r);x=(p-coef)+(q-coef);q-next=p;s-next=q;Y x！=0 Ns=q; (p-exp)exp)N Y(p!=NULL)&(q!=NULL)q=r;p-coef=x;s=p;s-next=p-n
9、ext;free(p);s=p;p=p-next; q!=NULLY 2）乘法算法流程图polynomial * p,* q,* n,* head,* r,* temp,* m;int exp；float coef；head=(polynomial *)malloc(sizeof(polynomial); head-next=NULL;p=A-next;temp=(polynomial *)malloc(sizeof(polynomial);temp-next=NULL; m=temp;q=B-next;n=(polynomial *)malloc(sizeof(polynomial);exp
10、=p-exp+q-exp; coef=p-coef*q-coef; n-coef=coef; n-exp=exp; m-next=n; m=m-next; q=q-next;p!=NULL;q!=NULL;p=p-next; m-next=NULL; polyadd(head,temp);return head;3、 代码(注释)#include stdio.h#include malloc.htypedef struct linknode /*定义节点*/float coef;int exp;struct linknode * next;polynomial;polynomial * cre
11、atlist() /*创建单链表*/float x; /*节点中存放项系数和指数*/int z;polynomial *head,*r,*n; /*下指针,分别是头指针、尾指针和新建立节点的指针*/head=(polynomial *)malloc(sizeof(polynomial); /*malloc分配内存单元给头指针申请空间*/head-next=NULL; /*头指针next指向空位空链表状态*/r=head; printf(建立一元多项式:(以系数0结束)n);/*打印文字提醒用户输入*/while(x!=0) /*建立单链表*/n=(polynomial *)malloc(siz
12、eof(polynomial); /*建立新节点,将用户输入的数据分别作为项(各节点)的系数和指数*/n-coef=x;n-exp=z;r-next=n; /*为指针指向下一新建节点*/r=r-next; /*后移尾指针*/r=n;printf(请按升幂输入系数和指数:); scanf(%f%d,&x,&z);r-next=NULL;head=head-next; /*链接节点使之勾成链表*/return (head); /*还回head指针(链表头标志或是说地址)给函数调用者*/void print(polynomial * head) /*打印输出函数*/polynomial *p; /*
13、为传入的链表设立当前指针*/p=head-next; /*将指针后移指向包含实际数据的节点*/while(p!=NULL) /*判断需要打印的链表是否为空*/printf(%.2fX(%d) ,p-coef,p-exp);/*打印当前指针所指项的数据*/p=p-next; /*后移指针指向下一节点*/printf(n); polynomial * polyadd(polynomial *A,polynomial *B) /*核心算法实现两链表的加法运算并将结果保存在A中*/polynomial *p,*q,*s,*r; /*为链表设立指针分别指向链表A和链表B(多项式A和B)，s为临时存放为后
14、续移动指针做地址保留*/float x;p=A-next;q=B-next;s=A;/*/ /*s作为p的前驱*/while(p!=NULL)&(q!=NULL) /*判断所比较链表是否为空不同时为空时反复执行下列函数*/if(p-exp)(q-exp) /*将q插入p之前*/ r=q-next; /*保存当前q的下一结点地址为r后移作准备*/q-next=p; /*将p接到到q之后*/s-next=q; /*将q彻底的插入到A链表中p之前作为结果项之一*/ s=q; /*修改当前指针为下一节点作比较准备*/q=r;else if(p-exp)exp) /*将p作为结果项之一，后移p进行下一结
15、点比较*/s=p; /*后移s*/p=p-next; /*后移当前指针p指向下一节点*/else /*当前链表中节点的指数相等进行系数加法运算*/x=(p-coef)+(q-coef); /*实现系数相加赋给x，节点中的系数单元*/ if(x!=0) /*判断系数和是否为零,不为零执行系数替换原有数据*/p-coef=x;s=p; /*p的前驱指针后移*/else /*系数和为零*/s-next=p-next; /*为释放p准备*/free(p);p=s-next; /*p指针指向下一节点*/ r=q; /*为释放q作准备*/q=q-next; /*q 指向下一节点*/free(r); if(
16、q!=NULL) /*循环结束将q中剩余节点直接插入p的为节点之后作为结果项*/ s-next=q;free(B); /*运算结束释放B链锁占空间*/ return A; /*还回A链给函数调用者*/ polynomial * polyand(polynomial *A,polynomial *B) /*核心算法实现两链表的乘法运算*/polynomial * p,* q,* n,* head,* r,* temp,* m; /定义当前指针p，q风别指向两链表和头指针，尾指针，及新生成节点n int exp; /定义整型指数float coef; /定义浮点型系数head=(polynomia
17、l *)malloc(sizeof(polynomial); /创头节点为新生链表准备head-next=NULL; /置空链表 r=head; /临时变量，为后移指针做准备p=A-next; /当前指针跳过A链表头指向实际运算数while(p!=NULL) /控制操作，循环A链表与内部while所控制B链表进行项之间的运算 temp=(polynomial *)malloc(sizeof(polynomial); /在内部创头节点为新生链表准备 即A中每一项与B中各项相乘构成一新链表 temp-next=NULL; /置空链表 m=temp; /临时变量，为后移指针做准备q=B-next;
18、/当前指针跳过B链表头指向实际运算数while(q!=NULL) n=(polynomial *)malloc(sizeof(polynomial); /建立新节点exp=p-exp+q-exp; /进行系数相加操作 coef=p-coef*q-coef; / /进行指数相乘操作n-coef=coef; /赋值新节点的系数域n-exp=exp; /赋值新节点的指数域 m-next=n; /链接节点至头结点，构成链表m=m-next; /后移指针，为下一节点做准备q=q-next; /控制B链表下一项/printf(%f %d ,coef,exp); /调试用p=p-next; /控制A链表下一
19、项m-next=NULL; /链表尾置空/head=head-next;polyadd(head,temp); /return head; void selet(polynomial * A,polynomial * B)int p;polynomial * C;printf(1、实现相加运算n2、实现相乘运算n);printf(请选择运算:);scanf(%d,&p);while(p!=1&p!=2)printf(输入错误,请重新选择:n);scanf(%d,&p);if(p=1) C=polyadd(A,B);else if(p=2)C=polyand(A,B);printf(The re
20、sult is:n); print(C); /*调用输出打印函数，打印运算结果*/ int main() /*主函数*/polynomial * A,* B; /*设立指针分别指向多项式链表A和链表B以及C作为结果*/A=creatlist(); /*建立打印多项式A*/print(A);B=creatlist(); /*建立打印多项式B*/ print(B); selet(A,B);return 0; /*还回系统调用0，结束整个程序*/4、 调试过程1打印输出调试：输入（3, 4） （-2 ,5） （2.6 ,7） 即3x4-2x5+2.6x6输出3.00x(4) -2.00x(5) 2.
21、60x(6) 如图：输出正常；2加法运算调试输入数据：（2,3）（3,4）（4,5）和（1,2）（3,4）（-5,5）即2x3+3x4+4x5和x2+3x4-5x5 并没有项预期的一样实现加法运算，而是在打印出各项数据后程序终止。如图：输入数据：（2,3）（3,4）（4,5）和（1,3）（3,4）（-5,5）即2x3+3x4+4x5和x3+3x4-5x5 结果和项预期的一样实现了加法运算，如图：对比得知数据和唯一不同的是的第一项的的指数大于的第一项指数因此应该想到程序在执行比较第一项之后并不能进行该有的操作即而之后的第二项第三项却可以执行有暗示着实现(p-exp)(q-exp)并没内部错误：因
22、此矛头指向了polynomial *p,*q,*s,*r; float x;p=A-next;q=B-next;s=p;/*出错原因*/ 而其中正是出错所在了，是作为的前驱而不是p -next的前驱，故而该是s=A；修改后正常的实现了改算法；但由于程序以实现该算法的核心思想为主因此并没有过多注意的在用户界面上实现和排序问题和出错等处理。因此对用户输入的要求严格。3乘法运算调试通过以上改正后进行测试测试数据（3,4）（4,5）（5,6）和（2，4）（3，6）（6,7） 未能得到预期结果；分析：可知第一项6.00x(8)并没能出现可能有两个原因，一是执行运算时跳过了B链表第一项；二是运算了单没能打
23、印出；有后面的数据8.00x(9)可知,是第二种可能；因此在执行运算后用printf(%f %d ,coef,exp);得结果如图：可以确定错误出处了，经检查知运算后多了head=head-next;将其删除即可。六、实验结果测试数据（1）：2,3 3,4 5,6 和1,2 2,3 3,4 5,7即2x3+3x4+5x6 和1x22x3+3x4+5x7实验结果（1）：加法1.00x(2) 4.00x(3) 6.00x(4) 5.00x(5) 5.00x(7)即1.00x2+4.00x3+ 6.00x4+ 5.00x5+ 5.00x7乘法9.00x(8) 12.00x(9) 15.00x(10)
24、 38x(11) 30x(13)即9x2+12x3+15 x4+38x5+30x(13)实验截图（1）：加法乘法 测试数据（2）：加法1,2 2,3 3,5和-3,2 2,3 4,4 0.4 ,5即1x2 +2x3+3x5和 -3x2 +2x3+4x4+0.4 x5乘法：3,4 5,6 0.5,7和5,6 -3,7 -0.8,8 即3x4+5x6+0.5x7和5x6-3x7-0.8x8实验结果（2）：加法-2.00x(2) 4.00x(3) 4.00x(4) 3.4x(5) 即-2.00x2+4.00x3 +4 .00x4+ 3.4x5乘法 15.00x(10) -9.00x(11) 22.6
25、0x(12) -12.50x(13) -5.50x(14) -0.40x(15)即5.00x10-9.00x11+22.60x12-12.50x13-5.50x14-0.40x15实验截图（2）：加法乘法七、总结在设计该算法时，由于过于依赖书本上的例子，导致很多不必要的麻烦，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插入删除等操作。大大压缩了程序代码，节省了程序空间使用，但不能避免的是必须要求输入数据时按升幂排序的不足当然可在数据的输入后先做一个节点的排序函数，通过对链表排序后再进行之后加法或乘法运算也是可以的。但它也给后续乘法的实现提供了便利，当前我们的重点是实现单链表的加法乘法运算，故而，我选择了这个算法，并真正的实现了它。设计中让我更深的体会到了动手能力的重要性，在实现乘法时虽然花了我很多时间去研究书上虽然错误的算法，但那提高了我的洞察能力，并让我独自思考，最终虽然很局限（数据输入上）的实现了一元多项式的加乘法运算，可是我学到了远远不止这些。附录：16 / 16文档可自由编辑打印