数据结构综合实验报告_一元多项式

目录

1 设计内容和要求 ··························································································································································· 1

1.1 设计要求 ······································································································································································· 1

1.2 设计内容 ······································································································································································· 1 2 概要设计 ··········································································································································································· 1

2.1程序主要流程 ······························································································································································· 1 3 详细设计 ··········································································································································································· 3

3.1源程序 ············································································································································································ 3 4 调试分析 ··········································································································································································· 8 5 总结 ······················································································································································································ 9 6 致谢 ···················································································································································································· 10 参考文献··············································································································································································· 11

1 设计内容和要求

1.1 设计要求

编写一个实现多项式相加和相减的程序。

1、 首先，根据键盘输入的一元实系数多项式的系数与指数序列，对多项式进行初

始化，并按未知数x的降幂形式输出多项式的合理表示。

2、 对于从键盘输入的任意两个一元多项式，正确计算它们的和以及差的多项式，

并输出结果。

1.2 设计内容

利用单链表表示一元多项式，然后实现各个项的系数和指数的输入，并且进行建立和输出，以及实现各个一元多项式之间的相加和相乘的操作。

2 概要设计

实现的方法是先定义多项式结点的结构，该多项式每个结点由三个元素：输入的系数、输入的指数、以及指向下一个结点的指针构成。该链表采用链式存储结构。然后通过多次的输入，依次得到两个一元多项式的各个项的系数与指数。该输入以零结尾。然后通过对结点的判断是否为零后，进行相加或者终止的操作。再初始化一个链表LC，将LC的各项系数和指数的指针指向LA+LB所得的结果的值，完成了最后的输出。

2.1程序主要流程

建立链表,将多项式的系数与数指数作为链表节点的数据；

指示输入两个多项式的数据,分别存在LA与LB中；

利用Getlength(PotyNode *L)函数计算出LA与LB的表长；

使用循环语句进行两链表的相应数据相加,并将所得到的新链表存放到LC中； 打印输出。

如图2－1就是程序主流程图。

在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。

要求可以按照降指数次序进行排列，结合数据结构中排序的相关知识，运用相应函数实

现，实现两个多项式的加减运算。在此要建立多项式运算的相关规则。

如题所说，该程序要实现两个多项式的相加，要建立输入与输出。

根据一元多项式相加的运算规则，对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有的指数不相同的项，则分别复抄到“和多项式”中去。

3 详细设计

3.1源程序

#include "stdio.h"

#include "stdlib.h"

typedef int datatype; /*定义多项式节点的结构*/

typedef struct node

{

float coef; /*系数*/

int expn; /*指数*/

struct node *next; /*指向结构体的指针*/

}PotyNode;

/*建立连表，返回指向多项式头节点的指针*/

PotyNode *Creat_PotyNodeTail()

{

PotyNode *L,*s,*r; /*声明结构体指针*/

float c; /*系数*/

int e; /*指数*/

L=(PotyNode *)malloc(sizeof(PotyNode));

/*建立头节点，头节点指针设置为空*/

L->next=NULL;

r=L; /*是指针r指向头节点*/

printf("系数与指数:");

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

while(c!=0) /*输入的第一项系数不允许为0，防止无意义的输入*/

{

s=(PotyNode *)malloc(sizeof(PotyNode));

s->coef=c;

s->expn=e;

s->next=NULL;

r->next=s; /*连接节点*/

r=s; /*指针r指向当前节点，用于连接下一节点*/

printf("\n系数与指数:");

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

}

return L;

}

/*获得指向第 i 个节点的指针，主要在删除节点的时候用来获得准备删除的前一节点*/

int Getlength(PotyNode *L)

{

PotyNode *p;

int count=0;

p=L->next;

while(p)

{

count++;

p=p->next ;

}

return count;

}

/*连表初始化及数据输入*/

PotyNode *GetElem_PotyNode(PotyNode *L,int i)

{

PotyNode *p;

int j=0;

p=L;

while(p->next&&j!=i) /*当p不是尾节点，并且不是第 i 个节点*/

{

j++;

p=p->next;

}

if(i==j)

return p; /*找到节点*/

else

return NULL; /*没有找到节点*/

}

/*删除节点i*/

int Delete_PotyNode(PotyNode *L,int i)

{

PotyNode *q,*p; /*获得节点i的前一个节点，便于删除节点i*/

p=GetElem_PotyNode(L,i-1);

q=p->next;

if(q) /*如果P为空，则说明节点p也就是节点i-1就是尾节点，节点i实际并不存在*/

{

p->next=q->next;

free(q);

return 1;

}

else

return 0;

}

/*对输入的两个多项式LA，LB进行相加，结果为LC，返回指向LC头节点的指针*/ PotyNode * Add_PotyNode(PotyNode *LA,PotyNode *LB)

{

PotyNode *LC,*q1,*q2,*r,*s,*p;

int x=1;

q1=LA->next;

q2=LB->next;

LC=LA;

LC->next=NULL;/*指针r是当前指针便于进行各种操作*/

r=LC;

while(q1&&q2) /*当多项式LA，和LB都没有结束的时候*/

{ /*指针s指向多项式LA，LB中指数小的那一项，程序要求，用户输入的时候，多项式是降序排列的*/

if(q1->expn<q2->expn)

{

s=q1;

q1=q1->next;

}

else

{

if(q1->expn>q2->expn)

{

s=q2; q2=q2->next; }/*指数相同，相加*/ else { q1->coef+=q2->coef; s=q1; q1=q1->next; q2=q2->next;

}/*结果连接到多项式LC*/

s->next=NULL;

r->next=s;

r=s;

}

}

/*如果多象是LB已经结束，则把LA多项式剩余的部分连接到多项式LC上*/ if(q1) r->next=q1;

/*如果多象是LA已经结束，则把LA多项式剩余的部分连接到多项式LC上*/ if(q2) r->next=q2;/*去除多项式中系数为零的项*/

p=LC->next;

while(p->next)

{

if(p->coef==0)

{

p=p->next;

Delete_PotyNode(LC,x);

}

else

{

p=p->next;

x++;

}

}

return LC;

}

/*打印多项式*/

void print_PotyNode(PotyNode *L)

{

int i;

PotyNode *p=L->next;

for(i=0;i<Getlength(L);i++)

{

printf("%.1fX%d",p->coef,p->expn);

if(p->next==NULL)

return;

else printf("+");

p=p->next;

}

}

/*主函数*/

int main()

{

PotyNode *LA,*LB,*LC;

int x;

printf("请输入多项式A的每项系数与指数(系数和指数输入0结束多项式的输入):\n");

LA=Creat_PotyNodeTail();

printf("多项式A为:");

print_PotyNode(LA);

printf("\n请输入多项式B的每项系数与指数(系数和指数输入0结束多项式的输入):\n");

LB=Creat_PotyNodeTail();

printf("\n");

printf("多项式B为:");

print_PotyNode(LB);

printf("\n");

LC=Add_PotyNode(LA,LB);

printf("多项式A和B相加得:");

print_PotyNode(LC);

scanf("%d",&x);

}

4 调试分析

图4－1 根据提示输入数据

这是输入第二个多项式B的第项系数与指数的界面。

由此图可以看出，多项式B有4个变量，系数分别是1，2，3，0，且同时有输出多项式B。

在调试时可以根据系数与指数的不同，变量个数也有可能不同，相加后的多项式的变量个数也不相同。

5 总结

通过这次实验，我理解了利用单链表实现多项式的存储，熟悉了指针在链表中的重要性，并进一步掌握了多项式的相加和相减。这次编程同时让我们了解到编程一定要细心，一个细小的错误就会使整个程序不能运行。虽然我们十分谨慎，但在编程的过程中还是遇到了不少的问题，还好最后在同学和老师的帮助下我们都将难题一一的解决掉了。

这次的综合性设计是我们在对《数据结构》这门课程学习过程中的一大跃进，也是我们再次认识《数据结构》的一次很好的机会！使我们不仅可以学到扎实的理论知识，而且，还可以培养我们动手的实践能力！《数据结构》这门课

对于几个模块，在程序设计中并没有遇到多大的困难，只是在设计调试的过程中遇上了不少的麻烦。如在调试总程序时遇上可很多差错，在改错上花了不少的功夫。在同学和老师的帮助下解决了很多问题，这就是我们在程序设计中遇到的问题。

在完成的过程中，老师给了我们很大的帮助，在此谢谢老师。

6 致谢

这次我做的是一元多项式的程序设计，开始编程时并不是很顺利。有很多不懂的地方，但是最后通过查阅资料和请教老师把困难一个一个都克服了。这让我不禁感到很高兴，自己做出来的程序很有成就感。在这次的实习过程中我也学会了很多知识，以前自己模糊不清的概念在这次实习中也能够理解了，而且也学会很多

首先程序能够成功顺利的完成要感谢学校给我们提供了有利的资源，也感谢老师的谆谆教导，当我运行程序遇到错误或有不会的问题时老师都很有耐心的指导我们，所以这里非常感谢我的老师。除了学校和老师还要感谢我的同学们，在他们身边学到了很多东西。当我有问题来不及请教老师时我的同学都会很热心的教我，可能程序还会有很多不足的地方，不过我会尽力改进的，所以这个程序的完成并不是我自己的功劳要感谢学校，老师和同学的帮助。

参考文献

[1].徐孝凯、魏 荣 《数据结构》 机械工业出版社

[2].秦友淑、曹化工 《C语言程序设计教程》 华中科技大学出版社

[3].严蔚敏、吴伟民 《数据结构（C语言版）》 清华大学出版社

[4].严蔚敏、吴伟民、米宁 《数据结构题集(C语言版) 》清华大学出版社

本文来源：https://www.bwwdw.com/article/gmc4.html