C语言实现数据结构多项式求和问题

多项式相加实验报告

实验目的：

利用线性链表存储和表示任意的多项式加深对线性链表算法的认识，深入对线性链表操作

的理解

问题表述：

任意输入两个项数不定的多项式，可以用一个动态分配内存的线性链表进行存储，根据一

元多项式相加的算法规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若

其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，

设计：

数据结构表述：

ADT Polynomial

{

数据对象：D={ai|ai∈TermSEt,i=1,2,…,m, m>=0

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

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

基本操作：

CreatPolyn(&L)

操作结果：输入系数和指数，建立表示一元多项式的有序链表 L；

}ADT Polynomial

算法：

struct polyn

{

int expn;

float coef;

struct polyn *next;

};

//------------------------------------------基本操作的算法描述----------------------------------------------

Int compare（point a，point b）

}//InList

Point InsPolyn(point &L,int i)//在原多项式中插入新的项

//把一个有内容的多项式结点插入到已有的一元多项式链表中

{

struct polyn *s,*p;

int j=0;

p=L;

while(p!=NULL&&j<i-1)//找到多项式最后一个结点

{

p=p->next;

if(s->coef==0.0)//如果输入 0 则多项式结束

{

free(s);

return(Error);

}

else

{

printf("input expn : ");

scanf("%d",&s->expn);

}while(!Locate(L,s->expn));

s->next=NULL;

{

struct polyn *L;

int i;

L=(struct polyn *)malloc(LEN);//开辟头结点空间

L->next=NULL;

for(i=1;InsPolyn(L,i)==1;i++);//反复插入新项

return(L);

}//create

void AddPolyn(point &a,point b)

//多项式加法：a=a+b,利用两个多项式的结点构成和多项式

while(qa&&qb)//判断两个链表的当前结点是否都存在

{

a=qa->expn;

b=qb->expn;

switch(Cmp(a,b))

{

case -1: //a<b 直接移动到 a 下一结点

ha=qa;

qa=ha->next;

break;

sum=qa->coef+qb->coef;

hb->next=qb->next;

free(qb);

qb=hb->next;

break;

}

}

if(qb!=NULL)ha->next=qb;//如果 b 还有结点，则将其全部接入 a 链表后面

free(hb);

return;

}//add

void Print(point *L)

//按照特定的形式输出多项式

{

struct polyn *p;

if(L->next==NULL)//判断链表是否为空

if(p!=L->next)//判断 p 是不是多项式首项

{

if(p->coef>0)printf("+");//打印+号

}

if(p->expn==0)printf("%d",p->coef);//输出常数项

else printf("%-5.2fX(%d)",p->coef,p->expn);

}

printf("\n");

return;

}//shuchu