您的当前位置：首页一元多项式相加数据结构实验报告

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

来源：飒榕旅游知识分享网

南昌航空大学实验报告

课程名称：数据结构实验名称：实验二线性表的链式存储结构班级： 080611 学生姓名：学号： 08 指导教师评定：签名:

题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的

单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。

一、需求分析

1. 用户可以根据自己的需求分别输入两个一元多项式，并且能够实现输入的一元多项式的

显示。

2. 能够完成两个一元多项式的相加功能，而且还能显示相加后的逆置的一元多项式。 3. 程序执行的命令包括：

（1）构造链表A （2）构造链表B （3）两个链表的相加（4）求链表的长度（5）打印（显示）已有的链表（6）将已相加的链表进行逆序排列

二、概要设计

⒈ 为实现上述算法，需要线性表的抽象数据类型：

ADT Polynomial {

数据对象：D={ai:|ai∈TermSet,i=1…n,n≥0

TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数}

数据关系：R1={|ai-1,ai∈D,且ai-1中的指数值< ai 中的指数值

i=2,…n≥0}

基本操作:

initlink(& L)

操作结果：构造一个空的链表L。

Creatlink(&L,n)

操作结果：输入n项的系数和指数，建立一个非空的一元多项式L。

LinkLength(L)

初始条件：链表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，并销毁多项式Lb。 Changlink（L）

初始条件：一元多项式L已经存在。

操作结果：完成多项式的逆置功能，即将链表逆置。 }ADT Polynomial

2. 本程序有三个模块：

⑴ 主程序模块

main(){ 初始化； {

接受命令；显示结果；｝｝

⑵ 链表单元模块：实现链表抽象数据类型操作，即函数的定义模块；

三、详细设计

⒈元素类型，结点类型 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; }

2.对抽象数据类型中的部分基本操作的伪码算法如下： /*创建一个非空链表*/

linklist creatlink(linklist p,float a[],int b[],int n) { linklist r,s; int i; r=p;

for(i=0;i{ s=(lnode*)malloc(sizeof(lnode)); s->num=a[i]; s->expn=b[i]; 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 Polymial is null\\n\"); else if(n==1)

printf(\"%3.1f%3d\ else

{ for(i=1;i{ printf(\"%3.1f%3d->\ q=q->next; }

printf(\"%3.1f%3d\ }

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,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*)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:

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->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->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,a2[100],b2[100]; float m,a1[100],b1[100]; linklist A,B,C;

A=initlink(); B=initlink(); C=initlink();

printf(\"Please input Polymial A's length:\\n\"); scanf(\"%d\

printf(\"Please input Polymial A's num and expn:\\n\"); for(i=0;i5

{ scanf(\"%f\ scanf(\"%d\ a1[i]=m; a2[i]=n; }

printf(\"Please input Polymial B's length:\\n\"); scanf(\"%d\

printf(\"Please input Polymial B's num and expn:\\n\"); for(i=0;icreatlink(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 函数调用关系

main

initlink changlink addPolyn initlink display

creatlink

cmpexpn length

四、调试分析

⒈在刚开始的时候，我先创建链表，在运行时程序报“错误 mimi.c 17: 未定义的符号'null'在 initlink 函数中”和“警告 mimi.c 17: 不可移动的指针（地址常数）赋值在 initlink 函数中”，在我查阅C语言的课本说NULL实际是由stdio.h头文件中的一条宏定义命令定义的。但是在我的程序中却报错，最后我记得C语言是识别大小写的，如果将null改为NULL程序就不会报错的。

⒉ 其实该实验的重心是实现两个一元多项式的相加，在我首次编好程序后，运行发现结果中的相加结果只进行了一次的相加，后面的几个项是原La的项，最后我只能再重新编写

该函数。

4. 在函数addPolyn中我发现好多语句是相似的，想用一个函数来实现这样的功能，可惜

没有想到好的函数。

4. 算法的时空分析

各操作的算法时间复杂度比较合理

Initlist，cmpexpn为O(1)printList, length,creatlink，changlink为O(n), addPolyn为0（n1+n2）

注：n为链表的长度，n1为一元多项式A的长度，n2为一元多项式B的长度。

5.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使

调试也较顺利，各模块有较好的可重用性。

五、用户手册

⒈ 本程序的运行环境为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 #include #define null 0

/*一元多项式的链式定义*/ 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;is=(lnode*)malloc(sizeof(lnode)); s->num=a[i]; s->expn=b[i]; 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 Polymial is null\\n\"); else if(n==1)

printf(\"%3.1f%3d\ else

{ for(i=1;i{ printf(\"%3.1f%3d->\ q=q->next;

}

printf(\"%3.1f%3d\ }

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,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*)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:

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->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->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,a2[100],b2[100]; float m,a1[100],b1[100]; linklist A,B,C; A=initlink(); B=initlink(); C=initlink();

printf(\"Please input Polymial A's length:\\n\"); scanf(\"%d\

printf(\"Please input Polymial A's num and expn:\\n\"); for(i=0;iprintf(\"Please input Polymial B's length:\\n\"); scanf(\"%d\

printf(\"Please input Polymial B's num and expn:\\n\"); for(i=0;icreatlink(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); }

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

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

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