.
实 验 报 告
教育资料
课程名称 ____数据结构上机实验__________ 实验项目 ______线性表的应用 ____________ 实验仪器 ________PC机___________________
系 别_____电子信息与通信学院___ 专 业________ ___ 班级/学号______ __
学生姓名 ______ ___________ 实验日期 _______________________ 成 绩 _______________________
指导教师 _______________________
.
实验一. 线性表的应用
1. 实验目的：掌握线性链表的存储、运算及应用。利用链表实现一元多项式计算。 2. 实验内容：
1) 编写函数，实现用链表结构建立多项式； 2) 编写函数，实现多项式的加法运算； 3) 编写函数，实现多项式的显示；
4) 测试：编写主函数，它定义并建立两个多项式，显示两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能：
5) 多项式求值：编写一个函数，根据给定的x值计算并返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6) 多项式相减：编写一个函数，求两个多项式相减的多项式。
7) 多项式相乘：编写一个函数，求两个多项式的乘积多项式。 3. 算法说明：
1) 多项式的建立、显示和相加算法见讲义。可修改显示
教育资料
.
函数，使输出的多项式更符合表达规范。
2) 多项式减法：同次项的系数相减（缺项的系数是0）。例如a(x)=-5x+2x+3，b(x)= -4x+3x，则a(x)-b(x) =4x-5x-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3) 多项式乘法：两个多项式的相乘是“系数相乘，指数相加”。算法思想是用一个多项式中的各项分别与另一个多项式相乘，形成多个多项式，再将它们累加在一起。例如，a(x)=-5x+2x+3，b(x)=-4x+3x，则a(x)*b(x) = (-4x)*(-5x+2x+3)+(3x)*(-5x+2x+3) =
5
3
2
2
2
3
3
2
2
3
(20x-8x-12x)
4
3
2
543
+ (-15x+6x+9x)
32
=
20x-8x-27x+6x+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(\用if语句判断，若输出x^o和x^1值为0和1 直接输出数据。 else if(p->exp==1) printf(\ else if(p->exp==0) printf(\
.
else
printf(\ p=p->next; while (p!=h) {
if(p->coef>0)
printf(\不用输出加号 if(p->coef==1)
printf(\ else if(p->exp==1) printf(\ else if(p->exp==0) printf(\ else
printf(\ p=p->next; }
printf(\} 主函数 void main()
教育资料
系数为负， .
{
PNode *F1,*F2,*F3; float x; F1=CreatPoly(); F2=CreatPoly();
printf(\ printf(\ F3=PolyAdd(F1,F2); F3=paixu(F3); printf(\ ShowPloy(F3); F3=PolySub(F1,F2); printf(\ ShowPloy(F3); F3=PolyMult(F1,F2); printf(\ ShowPloy(F3);
printf(\的值为: \ scanf(\
printf(\); }
教育资料
.
多项式求值
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
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(\用if语句判断，若输出x^o和x^1值为0和1 直接输出数据。 else if(p->exp==1) printf(\ else if(p->exp==0) printf(\ else
教育资料
.
printf(\ p=p->next; while (p!=h) {
if(p->coef>0)
printf(\系数为负，不用输出加号
if(p->coef==1)
printf(\ else if(p->exp==1) printf(\ else if(p->exp==0) printf(\ else
printf(\ p=p->next; }
printf(\}
PNode * CreatPoly() //建立多项式链表，返回头指针 {
教育资料
.
PNode * head, *p, *s; int i,n;
head=(PNode *)malloc(sizeof(PNode)); head->exp=-1; p=head;
printf(\多项式的项数为: \ scanf(\ for(i=1;i<=n; i++) {
s=(PNode *)malloc(sizeof(PNode));
printf(\请输入多项式第%d项的系数和指数（用逗号隔开）: \
scanf(\ 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; //返回 }
教育资料
建立新 .
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; //返回头指针 }
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; }
void main() {
PNode *F1,*F2,*F3; float x; F1=CreatPoly(); F2=CreatPoly();
printf(\ printf(\ F3=PolyAdd(F1,F2); F3=paixu(F3); printf(\ ShowPloy(F3); F3=PolySub(F1,F2); printf(\ ShowPloy(F3);
教育资料
.
F3=PolyMult(F1,F2); printf(\ ShowPloy(F3);
printf(\的值为: \ scanf(\
printf(\}
实验总结：
这次试验提高了我的编程能力，让我认识到了我C语言的不足之处。也使我了解了线性链表是具有链接存储结构的线性表，它用节点存放线性表中的数据元素，逻辑上相邻的节点不能随机存取，因为这个原因我前期的程序一直出错，以后编程序的时候要牢记。
教育资料
（完整版）数据结构线性表的应用实验报告
