实验报告
课程名称____数据结构上机实验__________ 实验项目______线性表的应用 ____________实验仪器________PC机___________________
系别_____电子信息与通信学院___
专业________ ___
班级/学号______ __
学生姓名______ ___________
实验日期_______________________
成绩_______________________
指导教师_______________________
实验一.线性表的应用
1.实验目的：掌握线性链表的存储、运算及应用。利用链
表实现一元多项式计算。
2.实验内容：
1)编写函数，实现用链表结构建立多项式；
2)编写函数，实现多项式的加法运算；
3)编写函数，实现多项式的显示；
4)测试：编写主函数，它定义并建立两个多项式，显示
两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。
选做内容：修改程序，选择实现以下功能：
5)多项式求值：编写一个函数，根据给定的x值计算并
返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。
6)多项式相减：编写一个函数，求两个多项式相减的多
项式。
7)多项式相乘：编写一个函数，求两个多项式的乘积多
项式。
3.算法说明：
1)多项式的建立、显示和相加算法见讲义。可修改显示
函数，使输出的多项式更符合表达规范。
2)多项式减法：同次项的系数相减（缺项的系数是0）。
例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x)
=4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。
3)多项式乘法：两个多项式的相乘是“系数相乘，指数
相加”。算法思想是用一个多项式中的各项分别与另
一个多项式相乘，形成多个多项式，再将它们累加在
一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则
a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3)
= (20x5-8x4-12x3) + (-15x3+6x2+9x) =
20x5-8x4-27x3+6x2+9x。
4.实验步骤：
根据实验报告的要求，我对文件夹里的C文件进行了丰
富和修改，步骤如下：
链表结构建立多项式：
typedef struct polynode
{ float coef; //系数
int exp; //指数
struct polynode *next; //下一结点指针
} PNode;
编写函数，实现多项式的加法运算；
PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功
能。
{ //实现两多项式（头指针分别为f1和f2）相加，返回和多项式f3=f1+f2。
PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q;
int exp;
float coef;
f3=(PNode *)malloc(sizeof(PNode)); //建立头指针f3->exp=-1; //对头指针初始化
f3->next=f3;
pc=f3; //将pc指向头指针
while (pa->exp!=-1 || pb->exp!=-1) // 返回头指针时，跳出循环
{
if (pa->exp>pb->exp)
{
exp=pa->exp;
coef=pa->coef;
pa=pa->next;
}
else if (pa->exp
{
exp=pb->exp;
coef=pb->coef;
pb=pb->next;
}
else
{
exp=pa->exp;
coef=pa->coef+pb->coef;
pa=pa->next;
pb=pb->next;
}
if (coef!=0)
{
q=(PNode *)malloc(sizeof(PNode)); //建立新的q指针存放负指数的指针
q->exp=exp;
q->coef=coef; //将q插入链表中
q->next=pc->next;
pc->next=q;
pc=q;
}
}
return f3; //返回
}
实现多项式的显示；
void ShowPloy(PNode *h)
//用if语句判断，当指数为0是，只输出系数；当
指数为1时，输出系数和X；当系数为1时，输出X
和指数。
{
h=paixu(h); //整理函数，使之降幂排列
PNode *p=h->next;
if(p==h)
{
printf("表达式为空\n");
return;
}
if(p->coef==1)
printf("x^%d",p->exp); //用if语句判断，若输出x^o和x^1值为0和1 直接输出数据。
else if(p->exp==1)
printf("%gx", p->coef);
else if(p->exp==0)
printf("%g", p->coef);
else
printf("%gx^%d", p->coef, p->exp);
p=p->next;
while (p!=h)
{
if(p->coef>0)
printf("+"); //系数为负，不用输出加号
if(p->coef==1)
printf("x^%d",p->exp);
else if(p->exp==1)
printf("%gx", p->coef);
else if(p->exp==0)
printf("%g", p->coef);
else
printf("%gx^%d", p->coef, p->exp);
p=p->next;
}
printf("\n");
}
主函数
void main()
{
PNode *F1,*F2,*F3;
float x;
F1=CreatPoly();
F2=CreatPoly();
printf("\nf1(x)=");ShowPloy(F1);
printf("\nf2(x)=");ShowPloy(F2);
F3=PolyAdd(F1,F2);
F3=paixu(F3);
printf("\nf1+f2=:");
ShowPloy(F3);
F3=PolySub(F1,F2);
printf("\nf1-f2=:");
ShowPloy(F3);
F3=PolyMult(F1,F2);
printf("\nf1*f2=:");
ShowPloy(F3);
printf("\nx的值为: ");
scanf("%f", &x);
printf("\nf1(x=%.3f)=%.3f\n",x,PolyValue(F1,x) );
}
多项式求值
double PolyValue(PNode *h, float x) {
//编写算法，求以h为头指针的多项式在x点的值并返回该值。
double f=0.0;
//求出f=f(x);
PNode *pa;
h=paixu(h);
pa=h->next;
while(pa->exp!=-1) //使用f+=coef*pow，返回f {
f+=(pa->coef)*pow(x,pa->exp);
pa=pa->next;
}
return f;
}
多项式相减
PNode * PolySub(PNode *f1,PNode *f2)
{//编写此算法，实现两多项式（头指针分别为f1和f2）相减，返回差多项式f3=f1-f2。
PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q,*head;
f3=(PNode *)malloc(sizeof(PNode)); //建立头指针
f3->exp=-1; //头指针的初始化
f3->next=f3;
pc=f3; //pc指向头指针,便于操作。
while(pb->exp!=-1) //返回头指针时，跳出循环。
{
q=(PNode *)malloc(sizeof(PNode)); //建立新的q指针存放负指数的指针
q->coef=pb->coef*(-1);
q->exp=pb->exp; //将q插入链表中
q->next=pc->next;
pc->next=q;
pc=q;
pb=pb->next;
}
head=PolyAdd(f1,f3); //调用加法函数做减法
return head; //返回头指针
}
多项式相乘
PNode * PolyMult(PNode *f1,PNode *f2)
{//实现两多项式（头指针分别为f1和f2）相乘，返回乘积多项式f3=f1*f2。
PNode *pa=f1->next,*pb=f2->next,*pc,*u,*head;
int exp;
float coef;
head=(PNode *)malloc(sizeof(PNode));
head->exp=-1;
head->next=head;
pc=head;
while(pa->exp!=-1) //多项式相乘，录入u指针，查到头指针。
{
while(pb->exp!=-1)
{
coef=pa->coef*pb->coef;
exp=pa->exp+pb->exp;
u=(PNode *)malloc(sizeof(PNode));
u->coef=coef;
u->exp=exp;
u->next=pc->next;
pc->next=u;
pc=u;
pb=pb->next;
}
pb=pb->next;
pa=pa->next;
}
return head; //返回头指针
}
程序运行截图
测试成功~！
程序完整源代码如下：
#include
#include
#include
typedef struct polynode
{ float coef; //系数
int exp; //指数
struct polynode *next; //下一结点指针
} PNode;
PNode * paixu(PNode *f) //将多项式降幂排列
{
PNode *p,*q,*r,*p0,*q0;
p=f->next;
q=p->next;
p0=f;
q0=p;
while(p->exp!=-1) //p为q的前驱，q与p指数指数值进行比较，
{
while(q->exp!=-1) //q为头指针推出循环，q移动一圈
{
if(p->exp>q->exp) //比较，若p大于q则q后移
{
q0=q;
q=q->next;
}
else if(p->exp
p之前
{
r=q->next;
q->next=p0->next;
q0->next=r;
p0->next=q;
p=q;
q=r;
}
else if(p->exp==q->exp) //若相等，p的coef 与q的相加，然后删除q节点，释放q的空间
{
p->coef+=q->coef;
q0->next=q->next;
q=q->next;
}
}
p0=p;
p=p->next;
q=p->next;
q0=p;
}
return f;
}
void ShowPloy(PNode *h)
//用if语句判断，当指数为0是，只输出系数；当指数为1时，输出系数和X；当系数为1时，输出X和指数。
{
h=paixu(h); //整理函数，使之降幂排列
PNode *p=h->next;
if(p==h)
{
printf("表达式为空\n");
return;
}
if(p->coef==1)
printf("x^%d",p->exp); //用if语句判断，若输出x^o和x^1值为0和1 直接输出数据。
else if(p->exp==1)
printf("%gx", p->coef);
else if(p->exp==0)
printf("%g", p->coef);
else
printf("%gx^%d", p->coef, p->exp);
p=p->next;
while (p!=h)
{
if(p->coef>0)
printf("+"); //系数为负，不用输出加号
if(p->coef==1)
printf("x^%d",p->exp);
else if(p->exp==1)
printf("%gx", p->coef);
else if(p->exp==0)
printf("%g", p->coef);
else
printf("%gx^%d", p->coef, p->exp);
p=p->next;
}
printf("\n");
}
PNode * CreatPoly() //建立多项式链表，返回头指针{
PNode * head, *p, *s;
int i,n;
head=(PNode *)malloc(sizeof(PNode));
head->exp=-1;
p=head;
printf("多项式的项数为: ");
scanf("%d",&n);
for(i=1;i<=n; i++)
{
s=(PNode *)malloc(sizeof(PNode));
printf("请输入多项式第%d项的系数和指数（用逗号隔开）: ",i);
scanf("%g,%d",&s->coef,&s->exp);
p->next=s;
p=s;
}
p->next=head;
return head;
}
void FreePoly(PNode *h)
{
//编写此算法，将以h为头指针的多项式的链表结点逐个释放。
PNode *p,*q;
p=h->next;
while(p->exp)!+-1;
{
q=p->next;
free(p);
p=q;
}
free(h);
return;
}
//Free函数用于销毁链表，最后指向头指针，跳出循环并释放头指针。
PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。
{ //实现两多项式（头指针分别为f1和f2）相加，返回和多项式f3=f1+f2。
PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q;
int exp;
float coef;
f3=(PNode *)malloc(sizeof(PNode)); //建立头指针f3->exp=-1; //对头指针初始化
f3->next=f3;
pc=f3; //将pc指向头指针
while (pa->exp!=-1 || pb->exp!=-1) // 返回头指针时，跳出循环
{
if (pa->exp>pb->exp)
{
exp=pa->exp;
coef=pa->coef;
pa=pa->next;
}
else if (pa->exp
{
exp=pb->exp;
coef=pb->coef;
pb=pb->next;
}
else
{
exp=pa->exp;
coef=pa->coef+pb->coef;
pa=pa->next;
pb=pb->next;
}
if (coef!=0)
{
q=(PNode *)malloc(sizeof(PNode)); //建立新的q指针存放负指数的指针
q->exp=exp;
q->coef=coef; //将q插入链表中
q->next=pc->next;
pc->next=q;
pc=q;
}
}
return f3; //返回
}