一元多项式相加 数据结构实验报告

1、南昌航空大学实验报告课程名称： 数据结构 实验名称： 实验二 线性表的链式存储结构 班 级： 080611 学生姓名： 学号： 08 指导教师评定： 签 名: 题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。一、 需求分析1. 用户可以根据自己的需求分别输入两个一元多项式，并且能够实现输入的一元多项式的显示。2. 能够完成两个一元多项式的相加功能，而且还能显示相加后的逆置的一元多项式。3. 程序执行的命令包括：（1）构造链表A （2）构造链表B （3）两个链表的相加 （4）求链表的长度 （5）打印

2、（显示）已有的链表 （6）将已相加的链表进行逆序排列二、概要设计 为实现上述算法，需要线性表的抽象数据类型：ADT Polynomial 数据对象：D=ai:|aiTermSet,i=1n,n0TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1=<ai-1,ai>|ai-1,aiD,且ai-1中的指数值< ai 中的指数值i=2,n0基本操作:initlink(& L)操作结果：构造一个空的链表L。 Creatlink(&L,n) 操作结果：输入n项的系数和指数，建立一个非空的一元多项式L。LinkLength(L)初始条件：链表

3、L已经存在。操作结果：返回一元多项式L中的项数。 Displaylink（L） 初始条件：链表L已经存在。 操作结果：打印输出一元多项式L。Addpolyn(A,B,&C)初始条件：一元多项式A和B已存在。操作结果：完成多项式相加运算，即：C=A+B，并且带回C。subtracypolyn(&La,&Lb,)初始条件：一元多项式La和Lb已存在。操作结果：完成多项式的相减运算La=La+Lb，并且销毁多项式Lb。Multiplypolyn(&La ,&Lb)初始条件：多项式La，Lb已经存在。操作结果：完成多项式的相乘运算，即La=La*Lb，并销毁多项

4、式Lb。Changlink（L） 初始条件：一元多项式L已经存在。 操作结果：完成多项式的逆置功能，即将链表逆置。ADT Polynomial2. 本程序有三个模块： 主程序模块 main()初始化；接受命令；显示结果； 链表单元模块：实现链表抽象数据类型操作，即函数的定义模块；三、详细设计元素类型，结点类型typedef struct lnode float num; int expn; struct lnode *next;*linklist,lnode; linklist initlink() linklist p; p=(lnode*)malloc(sizeof(lnode); p-&

5、gt;next=null; return p;2.对抽象数据类型中的部分基本操作的伪码算法如下：/*创建一个非空链表*/linklist creatlink(linklist p,float a,int b,int n) linklist r,s; int i; r=p; for(i=0;i<n;i+) s=(lnode*)malloc(sizeof(lnode); s->num=ai; s->expn=bi; r->next=s; r=s; r->next=null; return p;/*求链表的长度*/int length(linklist p) int n

6、=0; linklist q=p->next; while(q!=null) n+; q=q->next; return n;/*显示链表*/void display(linklist p) int n=length(p),i; linklist q=p->next; if(n=0) printf("The Polymial is nulln"); else if(n=1) printf("%3.1f%3d",q->num,q->expn); else for(i=1;i<n;i+) printf("%3.1

7、f%3d->",q->num,q->expn); q=q->next; printf("%3.1f%3d",q->num,q->expn); printf("n");/*比较指数*/int cmpexpn(int expn1,int expn2) if(expn1>expn2) return -1; else if(expn1=expn2) return 0; else return 1;/*两个一元多项式相加*/linklist addPolyn(linklist ha,linklist hb,lin

8、klist hc) linklist la,lb,lc,r; float sum; la=ha->next; lb=hb->next; lc=hc; while(la && lb) switch (cmpexpn(la->expn,lb->expn) case -1: r=(lnode*)malloc(sizeof(lnode); r->num=lb->num; r->expn=lb->expn; lc->next=r; lc=r; r->next=null; lb=lb->next; break; case 0

9、: sum=la->num+lb->num; if(sum!=0) r=(lnode*)malloc(sizeof(lnode); r->num=sum; r->expn=la->expn; lc->next=r; lc=r; r->next=null; la=la->next; lb=lb->next; else la=la->next; lb=lb->next; break; case 1: r=(lnode*)malloc(sizeof(lnode); r->num=la->num; r->expn=la

10、->expn; lc->next=r; lc=r; r->next=null; la=la->next; break; if(la) r=(lnode*)malloc(sizeof(lnode); r->num=la->num; r->expn=la->expn; lc->next=r; lc=r; r->next=null; la=la->next; if(lb) r=(lnode*)malloc(sizeof(lnode); r->num=lb->num; r->expn=lb->expn; lc-&

11、gt;next=r; lc=r; r->next=null; lb=lb->next; return lc;/*逆置链表*/void changlink(linklist L) linklist p,q,r; p=L->next; q=p->next;while(q) r=q->next;q->next=p; p=q; q=r; L->next->next=NULL; L->next=p; free(p); free(q); free(r);3.主函数和其他函数的伪码算法void main() int len1,len2; int i,n,

12、a2100,b2100; float m,a1100,b1100; linklist A,B,C;A=initlink(); B=initlink(); C=initlink(); printf("Please input Polymial A's length:n"); scanf("%d",&len1); printf("Please input Polymial A's num and expn:n"); for(i=0;i<len1;i+) scanf("%f",&m)

13、; scanf("%d",&n); a1i=m; a2i=n; printf("Please input Polymial B's length:n"); scanf("%d",&len2); printf("Please input Polymial B's num and expn:n"); for(i=0;i<len2;i+) scanf("%f",&m); scanf("%d",&n); b1i=m; b2i=n;

14、 creatlink(A,a1,a2,len1); creatlink(B,b1,b2,len2); printf("The Polymial A is;n"); display(A); printf("The Polymial B is;n"); display(B); addPolyn(A,B,C); changlink(C); printf("The Polymial's result is;n"); display(C);4 函数调用关系maininitlink changlink addPolyn initlink

15、display creatlink cmpexpn length 四、调试分析在刚开始的时候，我先创建链表，在运行时程序报“错误 mimi.c 17: 未定义的符号'null'在 initlink 函数中”和“警告 mimi.c 17: 不可移动的指针（地址常数）赋值在 initlink 函数中”，在我查阅C语言的课本说NULL实际是由stdio.h头文件中的一条宏定义命令定义的。但是在我的程序中却报错，最后我记得C语言是识别大小写的，如果将null改为NULL程序就不会报错的。 其实该实验的重心是实现两个一元多项式的相加，在我首次编好程序后，运行发现结果中的相加结果只进行了一

16、次的相加，后面的几个项是原La的项，最后我只能再重新编写该函数。4. 在函数addPolyn中我发现好多语句是相似的，想用一个函数来实现这样的功能，可惜没有想到好的函数。4. 算法的时空分析各操作的算法时间复杂度比较合理Initlist，cmpexpn为O(1)printList, length,creatlink，changlink为O(n), addPolyn为0（n1+n2）注：n为链表的长度，n1为一元多项式A的长度，n2为一元多项式B的长度。5.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，各模块有较好的可重用性。五、用户手册 本程序的运行

17、环境为windows xp操作系统，并且在TC2.0中运行，执行文件为Exp2Prb2.c； 进入演示程序后，完成编译，再点击超级工具集里的中文DOS环境运行选项，进入DOS环境中，用户根据需求键入相应的数据，可以看到相应的结果。六、测试结果 因为在wintc中的运行结果不好截屏，所以在TC2.0中运行得到的结果如下图所示：我输入的一元多项式是Y1=1+3X2 Y2=1+4X+3X2+4X3运行的结果是 Y=4X3+6X2+4X+2七、附录：源程序#include<stdio.h>#include<stdlib.h>#define null 0/*一元多项式的链式定义*

18、/typedef struct lnode float num; int expn; struct lnode *next;*linklist,lnode;/*创建一个空链表*/linklist initlink() linklist p; p=(lnode*)malloc(sizeof(lnode); p->next=null; return p;/*创建一个非空链表*/linklist creatlink(linklist p,float a,int b,int n) linklist r,s; int i; r=p; for(i=0;i<n;i+) s=(lnode*)mal

19、loc(sizeof(lnode); s->num=ai; s->expn=bi; r->next=s; r=s; r->next=null; return p;/*求链表的长度*/int length(linklist p) int n=0; linklist q=p->next; while(q!=null) n+; q=q->next return n;/*显示链表*/void display(linklist p) int n=length(p),i; linklist q=p->next; if(n=0) printf("The P

20、olymial is nulln"); else if(n=1) printf("%3.1f%3d",q->num,q->expn); else for(i=1;i<n;i+) printf("%3.1f%3d->",q->num,q->expn); q=q->next; printf("%3.1f%3d",q->num,q->expn); printf("n");/*比较指数*/int cmpexpn(int expn1,int expn2) if(

21、expn1>expn2) return -1; else if(expn1=expn2) return 0; else return 1;/*两个一元多项式相加*/linklist addPolyn(linklist ha,linklist hb,linklist hc) linklist la,lb,lc,r; float sum; la=ha->next; lb=hb->next; lc=hc; while(la && lb) switch (cmpexpn(la->expn,lb->expn) case -1: r=(lnode*)mallo

22、c(sizeof(lnode); r->num=lb->num; r->expn=lb->expn; lc->next=r; lc=r; r->next=null; lb=lb->next; break; case 0: sum=la->num+lb->num; if(sum!=0) r=(lnode*)malloc(sizeof(lnode); r->num=sum; r->expn=la->expn; lc->next=r; lc=r; r->next=null; la=la->next; lb=lb

23、->next; else la=la->next; lb=lb->next; break; case 1: r=(lnode*)malloc(sizeof(lnode); r->num=la->num; r->expn=la->expn; lc->next=r; lc=r; r->next=null; la=la->next; break; if(la) r=(lnode*)malloc(sizeof(lnode); r->num=la->num; r->expn=la->expn; lc->next=r

24、; lc=r; r->next=null; la=la->next; if(lb) r=(lnode*)malloc(sizeof(lnode); r->num=lb->num; r->expn=lb->expn; lc->next=r; lc=r; r->next=null; lb=lb->next; return lc;/*逆置链表*/void changlink(linklist L) linklist p,q,r; p=L->next; q=p->next;while(q) r=q->next; q->next=p; p=q; q=r; L->next->next=NULL; L->next=p; free(p); free(q); free(r);/*主函数*/void main() int len1,len2; int i,n,a2100,b2100; float m,a1100,b1100; lin