两个一元多项式的表示及相加-数据结构实验报告.doc

实验报告

1、需求分析：

两个一元多项式的表示及相加

2、总体设计：

（1）抽象数据类型

1,（ADT）polynomial的定义

ADTpolynomial{

数据对象：D={ai|ai∈termset,i=1,2,3,···，m，m=0termset中的每一个元素包含一个表示系数和表示指数的整数}

数据关系：R1={ai-1,ai|ai-1,ai∈D,且ai-1中的指数ai中的指数,i=2,···，n}

基本操作：

createpolyn(intm)

操作结果：输入m项的系数和指数，建立一元多项式。

print(p)

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

操作结果：打印输出一元多项式p。

addpolyn(ha,hb);

初始条件：一元多项式ha和hb已存在

操作结果：完成一元多项式的相加，即ha=ha+hb,并销毁一元多项式hb。

}ADTpolynomial

2，（ADT）polynomial的实现

Typedefstruct{//项的表示，多项式的项作为linklist的数据元素

Floatcoef；//系数

Intexpn;//指数

}term，elemtype;//term作为本ADT，elemtype为linklist的数据对象名

typedefstructnode

{ElemTypedata;

??structnode*next;}

polynode,*LinkList;

Typedeflinklistpolynomial;//用带头结点的有序链表表示多项式

//-----基本操作的函数原型说明-----

polynomialcreatepolyn(intm)

//输入m项的系数和指数，建立表示一元多项式的有序链表p

Voidaddpolyn(polynmailpa,polynmailpb);

//完成多项式的相加，即pa=pa+pb,并销毁pb

voidprint(polynomialp)

//输出函数，打印出多项式相加结果

（2）数据存储结构分析

一元多项式在计算机内用链表来表示，为了节省存储空间，只存储其中的非0数据项。它包含含三个域，分别存放多项式的系数，指数，以及指向下一个元素上的指针。

（3）主程序流程

开始

开始

将pa和pb相加

建立一元多项式pb

建立一元多项式pa

结束

（4）重要算法流程图：将pa和pb相加

3、详细代码

#includestdio.h

#includemalloc.h

#includestdlib.h

#defineLENsizeof(polynode)

typedefstruct

{

floatcoef;

intexpn;

}ElemType;

typedefstructnode

{

ElemTypedata;

structnode*next;

}polynode,*Linklist;

typedefLinklistpolynomial;

polynomialhead;

polynomialcreatepolyn(intm)

{inti,e;

floatc;

polynomialp,s;

head=(polynomial)malloc(LEN);

p=(polynomial)malloc(LEN);

head-data.coef=0.0;

head-data.expn=0;

p=head;

for(i=1;i=m;i++)

{

s=(polynomial)malloc(LEN);

scanf(%f,%d,c,e);

s-data.coef=c;

s-data.expn=e;

p-next=s;

p=s;

}

p-next=NULL;

return(head);

}

voidpolyadd(polynomialha,polynomialhb)//一元多项式相加函数，用于将两个多项式相加，然后将和多项式存放在多项式ha中，并将多项式hb删除

{

polynomialp,q,pre,temp;

floatsum;

p=ha-next;

q=hb-next;

pre=ha;

while(p!=NULLq!=NULL)

{

if(p-data.expnq-data.expn)

{

pre-next=p;

pre=pre-next;

p=p-next;

}

elseif(p-data.expn==q-data.expn)

{sum=p