1、线性表及其应用多项式相加相乘福建农林大学计算机与信息学院（程序设计类课程）实验报告课程名称：数据结构姓 名：邓建国系：计算机与信息专 业：网络工程年 级：09级学 号：091154050指导教师：黄思先职 称：副教授福建农林大学计算机与信息学院实验报告系： 计算机与信息 专业： 网络工程 年级： 09级 姓名： 邓建国 学号： * 实验室号：_ 计算机号： 实验一 线性表及其应用（多项式相加、相乘）一、实验目的和要求1、熟悉tc的运行环境，并可以熟练的使用tc；2、掌握链表存储的方法以及基本操作；3、掌握内存的动态分配和释放方法；4、熟悉C语言程序的基本格式与规范。二、实验内容和原理1、实验内
2、容：设计一个一元多项式的简单计算程序，其基本功能有：（1）输入并建立多项式；（2）输出多项式；（3）多项式的相加减；（4）多项式的相乘。利用单链表实现。 2、实验原理：将两多项式存入链表lianbiao1、lianbiao2，用pointer1扫描lianbiao1，pointer2扫描lianbiao2，结果保存在lianbiao3中(用pointer3来创建lianbiao3)三、实验环境硬件：（1）学生用微机（2）多媒体实验教室（3）局域网环境软件：（1）Windows XP中文操作系统 （2）Turbo C 3.0四、算法描述及实验步骤1、描述1.定义创建链表的函数，然后创建三个链表，
3、一个用于存放结果。2.定义多项式相加的函数实现多项式的相加功能，定义多项式的相乘功能。3.定义打印链表和释放链表的函数。4.最后在主函数里面调用这些函数，实现多项式的相加和相乘。 例子：A(X)=3X+7X6-9X9 B(X)=2X-3+7-3X+8X3+X5（1）执行加法操作，输出“lianbiao1+lianbiao2:(2,-3) (7,0) (8,5) (1,5) (7,6) (-9,9)”（2）执行乘法操作，输出“lianbiao1*lianbiao2:(6,-2) (21,1) (-9,2) (14,3) (55,6) (3,6) (-21,7) (-63,9) (27,10) (
4、56,11) (7,11) (-72,14) (-9,14)”2、框图3、代码(注释)#include stdio.h /* 输入输出函数的头文件 */#include alloc.h /* alloc.h是动态分配内存空间头文件 */typedef struct node /* 定义节点，包含两个数据域（c和e）和一个指针域（*next）*/ int c,e; /*c是指多项式的系数, e是项的指数*/ struct node *next; /* 定义next为指向下一个结点的指针*/Pn; /*定义Pn类型*/Pn *create() /*创建链表*/ Pn *pointer,*lianb
5、iao; int n; lianbiao=malloc(sizeof(Pn); /*用malloc动态分配函数给链表分配内存空间*/ printf(n:); /*提示用户输入多项式的项数*/ scanf(%d,&n); /*接收用户输入的多项式的项数*/ pointer=lianbiao; while(n) /*对n进行判断，当n不为零时执行while循环语句*/ pointer-next=malloc(sizeof(Pn); /*为链表新的节点申请空间*/ pointer=pointer-next; /*将pointer下移*/ printf(c e:); scanf(%d %d,&poin
6、ter-c,&pointer-e); /*将系数c,指数e存入链表中的新节点*/ n-; /*没当输入一项时，项数n就减一*/ pointer-next=NULL; /*如果pointer指向的下一个结点的指针域为空，说明链表已经创建好了*/ return lianbiao; void OUT(Pn *lianbiao) /*打印输出链表*/ Pn *pointer=lianbiao-next; while(pointer) /*打印出当前的结点系数c和指数e, 直到链表为空*/ printf(%d,%d) ,pointer-c,pointer-e); /*打印出多项式系数c和指数e*/ po
7、inter=pointer-next; /*打印出当前结点后,将指针移到下一个节点*/ printf(n); /*用n换行*/void Free(Pn *lianbiao) /*释放链表空间*/ Pn *pointer=lianbiao; /*将pointer指向头节点*/ while(pointer) /*释放链表中的结点,直到pointer链表为空时推出循体*/ lianbiao=lianbiao-next; /*删除当前节点*/ free(pointer); /*释放当前结点的空间*/ pointer=lianbiao; /* 当pointer指向头结点指针时结束循环*/ Pn *add
8、(Pn *lianbiao1,Pn *lianbiao2) /*多项式相加*/Pn *lianbiao3,*pointer3,*pointer1=lianbiao1-next,*pointer2=lianbiao2-next; /*建立新的链表lianbiao3，用于存放lianbiao1与lianbiao2相加后的结果*/int c,e; /*这里的c为多项式相加后的系数,而e为结点相加后的指数*/ pointer3=lianbiao3=malloc(sizeof(Pn); /*用malloc为lianbiao3申请空间*/ lianbiao3-next=NULL; while(pointe
9、r1|pointer2) /*当pointer1或pointer2不为空时，分成3种情况*/ if(pointer1&(pointer2=NULL|pointer1-ee) /*第一种是当pointer1不空并且pointer2为空,或者pointer1所指的指数e小于pointer2所指的指数e时*/ c=pointer1-c; /*将pointer1当前所指结点的系数c赋值给c*/ e=pointer1-e; /*将pointer1当前所指结点的系数e赋值给e*/ pointer1=pointer1-next; /*将pointer1移到下一结点*/ else if(pointer2&(p
10、ointer1=NULL|pointer2-ee) /*第二种是当pointer2不空且pointer1为空或者pointer2所指的指数e小于pointer1所指的指数e时*/ c=pointer2-c; e=pointer2-e; pointer2=pointer2-next; else /*第三种是当pointer1、pointer2都不为空且pointer1的指数e等于pointer2的指数e时*/ c=pointer1-c+pointer2-c; /*将pointer1与pointer2所指的系数相加*/ e=pointer1-e; pointer1=pointer1-next; /
11、*将pointer1下移*/ pointer2=pointer2-next; /*将pointer2下移*/ if(c) pointer3-next=malloc(sizeof(Pn); /*申请新结点的空间*/ pointer3=pointer3-next; /*pointer3下移*/ pointer3-c=c; /*把系数c放入新结点*/ pointer3-e=e; /*把指数e放入新结点*/ pointer3-next=NULL; /*当所指的指针为NULL时，链表结束*/ return lianbiao3; /* 返回两个多项式相加的结果lianbiao3 */Pn *mx1(Pn
12、*pointer1,Pn *lianbiao2) /*多项式相乘*/ Pn *lianbiao3,*pointer3,*pointer2=lianbiao2-next; /*定义链表lianbiao3 */ pointer3=lianbiao3=malloc(sizeof(Pn); /*为lianbiao3申请空间, 并将pointer3指向lianbiao3*/ lianbiao3-next=NULL; while(pointer2) /* 当pointer2不为空时， 执行while循环*/ pointer3-next=malloc(sizeof(Pn); /*为新创结点申请空间*/ po
13、inter3=pointer3-next; /*将pointer3指向新结点*/ pointer3-c=pointer1-c*pointer2-c; /*将pointer1的系数乘以pointer2-c*/ pointer3-e=pointer1-e+pointer2-e; /*将pointer1的指数乘以pointer2-e*/ pointer2=pointer2-next; /*pointer2下移*/ pointer3-next=NULL; return lianbiao3; /*将结果lianbiao3返回*/Pn *mxm(Pn *lianbiao1,Pn *lianbiao2) /
14、*多项式相乘*/ Pn *lianbiao3,*pointer1=lianbiao1-next,*htemp; lianbiao3=malloc(sizeof(Pn); lianbiao3-next=NULL; while(pointer1) /*当pointer1不为空，执行while循环*/ htemp=mx1(pointer1,lianbiao2); /*将相乘结果放到链表htemp*/ lianbiao3=add(lianbiao3,htemp); /*将htemp中的多项式加上lianbiao3中的多项式*/ pointer1=pointer1-next; Free(htemp);
15、/*释放链表htemp*/ return lianbiao3; /*返回结果lianbiao3 */main() Pn *lianbiao1,*lianbiao2,*lianbiao3; /*定义三个链表lianbiao1,lianbiao2,lianbiao3*/ clrscr(); printf(Create lianbiao1n); lianbiao1=create(); /*创建链表lianbiao1*/ printf(nPrintf lianbiao1n); OUT(lianbiao1); /*打印出链表lianbiao1*/ printf(nCreate lianbiao2n);
16、lianbiao2=create(); /*创建链表lianbiao2*/ printf(nPrintf lianbiao2n); OUT(lianbiao2); /*打印出链表lianbiao2*/ printf(nlianbiao1+lianbiao2:); lianbiao3=add(lianbiao1,lianbiao2); /*把lianbiao1和lianbiao2相加的结果赋给lianbiao3*/ OUT(lianbiao3); /*打印出lianbiao3*/ Free(lianbiao3); /*释放lianbiao3 */ printf(nlianbiao1*lianbi
17、ao2:); lianbiao3=mxm(lianbiao1,lianbiao2); /*把lianbiao1和lianbiao2相乘的结果赋给lianbiao3*/ OUT(lianbiao3); /*输出lianbiao3*/ Free(lianbiao1); /*释放lianbiao1*/ Free(lianbiao2); Free(lianbiao3); getch();五、调试过程#include malloc.h语句出错， 多了一个m，后来改为#include alloc.h， 就编译通过了。六、实验结果测试数据（1）：取两项多项式为： 9+3x 取一项多项式为： 2X-3实验结果
18、（1）：这两个项式相加结果为：lianbiao1+lianbiao2: 2X-3+9+3X 这两个项式相乘结果为：lianbiao1*lianbiao2: 18X-3+6X-2 实验截图（1）：测试数据（2）：取三项多项式为：(3,1) (7,6) (-9,9) 取五项多项式为：(2,-3) (7,0) (-3,1) (8,5) (1,5)实验结果（2）： 这两个项式相加：lianbiao1+lianbiao2:(2,-3)(7,0) (8,5) (1,5) (7,6)(-9,9)这两个项式相乘：lianbiao1*lianbiao2:(6,-2) (21,1) (-9,2) (14,3) (
19、55,6) (3,6) (-21,7) (-63,9) (27,10) (56,11) (7,11) (-72,14) (-9,14)实验截图（2）： 七、总结通过这次实验我熟悉tc的运行环境，并可以熟练的使用tc，掌握链表存储的方法以及基本操作、内存的动态分配和释放方法并且熟悉C语言程序的基本格式与规范。附录：参考文献 1宁正元、王秀娟算法与数据结构， 北京：清华大学出版社， 2006； 2严蔚敏、佩娟等数据结构，北京：国防工业出版社， 1981；3宁正元数据结构用C语言描述，北京：中国水利水电出版社，20004中国计算机科学与技术学科教程2002研究组中国计算机科学与技术学科教程2002，北京：清华大学出版社，2002；5陈小平数据结构，南京：南京大学出版社，1994。
