实验报告-一元多项式
一元多项式实验报告
学号：[1**********]5 姓名：罗启荣
1、 实验目的
1）掌握链表的灵活运用；
2）学习链表初始化和建立一个新的链表；
3）知道怎样去实现链表删除结点操作与插入结点；
4）理解链表的基本操作（包括数据域数据的相加）并能灵活运用。
2、 实验内容
建立两个链表为稀疏多项式，将他们每项按项相加，最后将得到的链表打印出来。
要求：运用单链表来存储多项式，并且结果链表要用原来的链表空间，空间复杂度为O （1）
3、 数据结构及算法思想
typedef int ElemType;
typedef struct CLNode
{
ElemType coef;
ElemType exp;
struct CLNode *next;
} CLNode, *CLinkList;
建立两个单链表，并按要求将结点数据相加，将结果链表存储在C 中。
4、 模块化分
a) 主程序；2）初始化单链表；3）建立单链表； 4）相加多项式
5、 详细设计及运行结果
a) 设计思路分析
要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为
运用尾插法建立两条单链表，以单链表polya 和polyb 分别表示两个一元多项式A 和B ，A+B的求和运算等同于单链表的插入问题（将单链表polyb 中的结点插入到单链表polya 中），因此“和多项式”中的结点无须另生成。 为了实现处理，设p 、q 分别指向单链表polya 和polyb 的当前项，比较p 、q 结点的指数项，由此得到下列运算规则：
① 若p->exp>q->exp，则结点p 所指的结点应是“和多项式”中的一项，令指针p 后移。
② 若p->exp=q->exp，则将两个结点中的系数相加，当和不为0时修改结点p 的系数。
③ 若p->expexp，则结点q 所指的结点应是“和多项式”中的一项，将结点q 插入在结点p 之前，且令指针q 在原来的链表上后移。
b) 运行结果
C 程序如下：
#include
#include
typedef struct Node //多项式数据类型的定义
{
float coef; //系数
int exp; //指数
struct Node *next; //指向多项式的下一结点
}PolyNode;
PolyNode * Createpoly() //创建链表
{
PolyNode *L,*r,*s;
float coef;
int exp;
L=(PolyNode *)malloc(sizeof(PolyNode)); //申请表头结点
空间
r=L; //r为尾指针 printf("coef:");
scanf("%f",&coef);
printf("exp: ");
scanf("%d",&exp);
while(coef!=0)
{
s=(PolyNode *)malloc(sizeof(PolyNode)); //
点，并插在链尾
s->coef=coef;
s->exp=exp;
r->next=s;
r=s;
printf("coef:");
scanf("%f",&coef);
printf("exp: ");
scanf("%d",&exp);
}
r->next=NULL;
return(L);
}
void Addpoly(PolyNode *pa, PolyNode *pb) //
项式相加
{
PolyNode
//temp用来存放临时结点
float sum;
p=pa->next; 建立项的结两个多*p,*q,*r,*temp;
q=pb->next;
r=pa;
while(p&&q)
{
if(p->exp>q->exp) //p指向的项指数小于q ，尾指针指向p ，且将p 指向链表的下一结点
{
r=p;
p=p->next;
}
else if(p->exp==q->exp) //
{
sum=p->coef+q->coef;
if(sum!=0)
{
p->coef=sum;
r=p;
}
else //
{
r->next=p->next;
free(p);
}
p=r->next;
temp=q;
q=q->next;
}
else //q指数相等时，系数相加 系数相加为0 指向项指数小于p 时，将q
加入多项式中
{
temp=q->next;
q->next=p;
r->next=q;
r=q;
q=temp;
}
}
if(q)
r->next=q;
free(pb);
}
void Print(PolyNode * p) //打印多项式
{
int i=0;
while(p->next)
{
p=p->next;
i++;
printf(" %g*x^%d\n",p->coef,p->exp);
}
printf("一共有%d项\n",i);
}
void main() //主函数
{
PolyNode * pa,* pb;int i;
printf("\n请输入多项式a(按指数递减顺序输入):\n");
pa=Createpoly();
Print(pa);
printf("\n请输入多项式b(按指数递减顺序输入):\n"); pb=Createpoly();
Print(pb);
printf("\n多项式相加结果是:\n");
Addpoly(pa,pb);
Print(pa);
printf("\n");
}