1、实验一 线性表及其应用(多项式相加、相乘)一、实验目的和要求1、熟悉tc的运行环境,并可以熟练的使用tc;2、掌握链表存储的方法以及基本操作;3、掌握内存的动态分配和释放方法;4、熟悉C语言程序的基本格式与规范。二、实验内容和原理1、实验内容:设计一个一元多项式的简单计算程序,其基本功能有:(1)输入并建立多项式;(2)输出多项式;(3)多项式的相加减;(4)多项式的相乘。利用单链表实现。 2、实验原理:将两多项式存入链表lianbiao1、lianbiao2,用pointer1扫描lianbiao1,pointer2扫描lianbiao2,结果保存在lianbiao3中(用pointer3来
2、创建lianbiao3)三、实验环境硬件:(1)学生用微机(2)多媒体实验教室(3)局域网环境软件:(1)Windows XP中文操作系统 (2)Turbo C 3.0四、算法描述及实验步骤1、描述1.定义创建链表的函数,然后创建三个链表,一个用于存放结果。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
3、) (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) (56,11) (7,11) (-72,14) (-9,14)”2、框图3、代码(注释)#include stdio.h /* 输入输出函数的头文件 */alloc.h /* alloc.h是动态分配内存空间头文件 */typedef struct node /* 定义节点,包含两个数据域(c和e)和一个指针域(*next)*/ int c,e; /*c是指多
4、项式的系数, e是项的指数*/ struct node *next; /* 定义next为指向下一个结点的指针*/Pn; /*定义Pn类型*/Pn *create() /*创建链表*/ Pn *pointer,*lianbiao; int n; lianbiao=malloc(sizeof(Pn); /*用malloc动态分配函数给链表分配内存空间*/ printf(n:); /*提示用户输入多项式的项数*/ scanf(%d,&n); /*接收用户输入的多项式的项数*/ pointer=lianbiao; while(n) /*对n进行判断,当n不为零时执行while循环语句*/ point
5、er-next=malloc(sizeof(Pn); /*为链表新的节点申请空间*/ pointer=pointer-next; /*将pointer下移*/ printf(c e: scanf(%d %dpointer-c,&e); /*将系数c,指数e存入链表中的新节点*/ n-; /*没当输入一项时,项数n就减一*/ next=NULL; /*如果pointer指向的下一个结点的指针域为空,说明链表已经创建好了*/ return lianbiao; void OUT(Pn *lianbiao) /*打印输出链表*/ Pn *pointer=lianbiao- while(pointer)
6、 /*打印出当前的结点系数c和指数e, 直到链表为空*/ printf(%d,%d) ,pointer-c,pointer- /*打印出多项式系数c和指数e*/ /*打印出当前结点后,将指针移到下一个节点*/n /*用n换行*/void Free(Pn *lianbiao) /*释放链表空间*/ Pn *pointer=lianbiao; /*将pointer指向头节点*/ while(pointer) /*释放链表中的结点,直到pointer链表为空时推出循体*/ lianbiao=lianbiao- /*删除当前节点*/ free(pointer); /*释放当前结点的空间*/ point
7、er=lianbiao; /* 当pointer指向头结点指针时结束循环*/Pn *add(Pn *lianbiao1,Pn *lianbiao2) /*多项式相加*/Pn *lianbiao3,*pointer3,*pointer1=lianbiao1-next,*pointer2=lianbiao2- /*建立新的链表lianbiao3,用于存放lianbiao1与lianbiao2相加后的结果*/int c,e; /*这里的c为多项式相加后的系数,而e为结点相加后的指数*/ pointer3=lianbiao3=malloc(sizeof(Pn); /*用malloc为lianbiao3
8、申请空间*/ lianbiao3- while(pointer1|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- /*将pointer1移到下
9、一结点*/ else if(pointer2&(pointer1=NULL|pointer2-pointer1-e) /*第二种是当pointer2不空且pointer1为空或者pointer2所指的指数e小于pointer1所指的指数e时*/ c=pointer2- e=pointer2- pointer2=pointer2- else /*第三种是当pointer1、pointer2都不为空且pointer1的指数e等于pointer2的指数e时*/ c+pointer2- /*将pointer1与pointer2所指的系数相加*/ /*将pointer1下移*/ /*将pointer2下
10、移*/ if(c) pointer3- /*申请新结点的空间*/ pointer3=pointer3- /*pointer3下移*/c=c; /*把系数c放入新结点*/e=e; /*把指数e放入新结点*/ pointer3- /*当所指的指针为NULL时,链表结束*/ return lianbiao3; /* 返回两个多项式相加的结果lianbiao3 */Pn *mx1(Pn *pointer1,Pn *lianbiao2) /*多项式相乘*/ Pn *lianbiao3,*pointer3,*pointer2=lianbiao2- /*定义链表lianbiao3 */ /*为lianbia
11、o3申请空间, 并将pointer3指向lianbiao3*/while(pointer2) /* 当pointer2不为空时, 执行while循环*/ pointer3- /*为新创结点申请空间*/ pointer3=pointer3- /*将pointer3指向新结点*/c=pointer1-c*pointer2- /*将pointer1的系数乘以pointer2-c*/e=pointer1-e+pointer2- /*将pointer1的指数乘以pointer2-e*/ pointer2=pointer2- /*pointer2下移*/ /*将结果lianbiao3返回*/Pn *mxm
12、(Pn *lianbiao1,Pn *lianbiao2) /*多项式相乘*/ Pn *lianbiao3,*pointer1=lianbiao1-next,*htemp; lianbiao3=malloc(sizeof(Pn); while(pointer1) /*当pointer1不为空,执行while循环*/ htemp=mx1(pointer1,lianbiao2); /*将相乘结果放到链表htemp*/ lianbiao3=add(lianbiao3,htemp); /*将htemp中的多项式加上lianbiao3中的多项式*/ pointer1=pointer1- Free(hte
13、mp); /*释放链表htemp*/ /*返回结果lianbiao3 */main() Pn *lianbiao1,*lianbiao2,*lianbiao3; /*定义三个链表lianbiao1,lianbiao2,lianbiao3*/ clrscr();Create lianbiao1n lianbiao1=create(); /*创建链表lianbiao1*/nPrintf lianbiao1n OUT(lianbiao1); /*打印出链表lianbiao1*/nCreate lianbiao2n lianbiao2=create(); /*创建链表lianbiao2*/nPrint
14、f lianbiao2n OUT(lianbiao2); /*打印出链表lianbiao2*/nlianbiao1+lianbiao2: lianbiao3=add(lianbiao1,lianbiao2); /*把lianbiao1和lianbiao2相加的结果赋给lianbiao3*/ OUT(lianbiao3); /*打印出lianbiao3*/ Free(lianbiao3); /*释放lianbiao3 */nlianbiao1*lianbiao2: lianbiao3=mxm(lianbiao1,lianbiao2); /*把lianbiao1和lianbiao2相乘的结果赋给l
15、ianbiao3*/ /*输出lianbiao3*/ Free(lianbiao1); /*释放lianbiao1*/ Free(lianbiao2); getch();五、调试过程malloc.h语句出错, 多了一个m,后来改为#include , 就编译通过了。六、实验结果测试数据(1):取两项多项式为: 9+3x 取一项多项式为: 2X-3实验结果(1):这两个项式相加结果为:lianbiao1+lianbiao2: 2X-3+9+3X 这两个项式相乘结果为:lianbiao1*lianbiao2: 18X-3+6X-2实验截图(1):测试数据(2):取三项多项式为:(3,1) (7,6
16、) (-9,9) 取五项多项式为:(2,-3) (7,0) (-3,1) (8,5) (1,5)实验结果(2): 这两个项式相加:(2,-3)(7,0) (8,5) (1,5) (7,6)(-9,9)这两个项式相乘:(6,-2) (21,1) (-9,2) (14,3) (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。