数据结构综合实验报告

1、目录1设计内容和要求11.1设计要求11.2设计内容12概要设计12. 1程序主要流程 13详细设计33. 1源程序34调试分析85总结96致谢10参考文献 111设计内容和要求1.1设计要求编写一个实现多项式相加和相减的程序。1、首先，根据键盘输入的一元实系数多项式的系数与指数序列，对多项式进行初始化，并按未知数x的降幕形式输出多项式的合理表示。2、对于从键盘输入的任意两个一元多项式，正确计算它们的和以及差的多 项式，并输出结果。1.2设计内容利用单链表表示一元多项式，然后实现各个项的系数和指数的输入，并且进 行建立和输出，以及实现各个一元多项式之间的相加和相乘的操作。2概要设计实现的方法是

2、先定义多项式结点的结构，该多项式每个结点由三个元素：输 入的系数、输入的指数、以及指向下一个结点的指针构成。该链表采用链式存储结 构。然后通过多次的输入，依次得到两个一元多项式的各个项的系数与指数。该输 入以零结尾。然后通过对结点的判断是否为零后，进行相加或者终止的操作。再初 始化一个链表LC,将LC的各项系数和指数的指针指向LA+LB所得的结果的值，完 成了最后的输出。2. 1程序主要流程建立链表,将多项式的系数与数指数作为链表节点的数据；指示输入两个多项式的数据，分别存在LA与LB中；利用Get length (PotyNode *L)函数讣算出LA与LB的表长；使用循环语句进行两链表的相

3、应数据相加，并将所得到的新链表存放到LC 中；打印输出。如图21就是程序主流程图。图2-1程序主要流程在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用 程序流程图）、源程疗:、测试数据和结果、算法的时间复杂度、另外可以提出算 法的改进方法。要求可以按照降指数次序进行排列，结合数据结构中排序的相关知识，运用 相应函数实现，实现两个多项式的加减运算。在此要建立多项式运算的相关规则。如题所说，该程序要实现两个多项式的相加，要建立输入与输出。根据一元多项式相加的运算规则，对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元 多项式

4、中所有的指数不相同的项，则分别复抄到“和多项式”中去。3详细设计3.1源程序#include "stdio. h" #include "stdlib. h" typedef int datatype;typedef struct nodefloat coef;int expn;struct node *next;/*定义多项式节点的结构*/*系数*/*指数*/*指向结构体的指针权PotyNode;/*建立连表，返回指向多项式头节点的指针欢/PotyNode *Creat_PotyNodeTail()PotyNode *L,*s, *r;/*声明结构体指针

5、*/float c;/*系数*/int e;/*指数*/L=(PotyNode *)malloc(sizeof(PotyNode);/*建立头节点，头节点指针设置为空*/L-next二NULL;r二L;/*是指针r指向头节点*/printff系数与指数：")；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;/*

6、连接节点*/r=s;/*指针r指向当前节点，用于连接下一节点*/printf Cn系数与指数:”)；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,

7、int i)PotyNode *p;int j二0;P 二L;while(p->next&&j!=i)/*" p不是尾节点，并且不是第i个节点*/j+；p=p->next;辻(i二二 j)return p;/*找到节点*/else/*删除节点i*/int Delete_PotyNode(PotyNode *L,int i)PotyNode *q,和；/*获得节点i的前一个节点，便于删除节点i*/p=GetElem_Potyode (L, iT);q二p_next;辻(q)/*如果P为空，则说明节点p也就是节点i-l就是尾节点，节点i实际并不存在*/p-&g

8、t;next=q->next;free(q);return 1;elsereturn 0;/*对输入的两个多项式LA, LB进行相加，结果为LC,返回指向LC头节点的 指针*/PotyNode * Add_PotyNode(PotyNode *LA, PotyNode *LB)PotyNode *LC, *ql, *q2, *r, *s, *p;int x=l;ql=LA>next;q2二LB->next;LOLA;LC-next二NULL;/*指针r是当前指针便于进行各种操作*/r=LC;while(ql&&q2)/*当多项式LA,和LB都没有结束的时候*/

9、*指针s指向多项式LA, LB中指数小的那一项，程序要求，用户输入的时候，多项式是降序排列的*/if(ql->expn<q2->expn)s 二 ql；ql=ql->next;elseif(ql->expn>q2->expn)s=q2 ;q2二q2-next;/*指数相同，相加*/elseql->coef+二q2-coef;s 二 ql；ql=ql->next;q2二q2-next;"结果连接到多项式LC*/s->next二NULL;r->next=s;/*如果多象是LB已经结束，则把LA多项式剩余的部分连接到多项式L

10、C上*/ if(ql) r->next=ql;/*如果多象是LA已经结束，则把LA多项式剩余的部分连接到多项式LC上*/辻(q2) r-next二q2;/*去除多项式中系数为零的项*/p二LC->next;while(p->next)if (p>coef0)p二p_>next;Delete_PotyNode(LC, x);elsep=p->next;x+;return LC;/*打印多项式*/void print.PotyNode(PotyNode *L)int i;PotyNode *p=L->next;for (i=0; i<Getlengt

11、h (L) ;i卄)printf(“ lfX%d,p->coef,p->expn);辻(p->next二二NULL)return;else printf("+");p二p-next;/*主函数*/int mdin()PotyNode *LA,*LB, *LC;int x;printff请输入多项式A的每项系数与指数(系数和指数输入0结束多项式的 输入)：n)；LA=Creat_PotyNodeTail();printf C多项式A为：");print_PotyNode(LA);printf (Xn请输入多项式B的每项系数与指数(系数和指数输入0结

12、束多项 式的输入)：n");LB=Creat_PotyNodeTail();printf("n");printff多项式B为：")；print_PotyNode(LB);printf("n");LC=Add_PotyXode(LA, LB);printf C多项式A和B相加得：");print_PotyNode(LC);scanf(”%d", &x);4调试分析图4 1根据提示输入数据这是输入第二个多项式B的第项系数与指数的界面。由此图可以看出，多项式B有4个变量，系数分别是1, 2, 3, 0,且同时有

13、输岀多项式B。在调试时可以根据系数与指数的不同，变量个数也有可能不同，相加后的多 项式的变量个数也不相同。5总结通过这次实验，我理解了利用单链表实现多项式的存储，熟悉了指针在链表 中的重要性，并进一步掌握了多项式的相加和相减。这次编程同时让我们了解到编 程一定要细心，一个细小的错误就会使整个程序不能运行。虽然我们十分谨慎，但 在编程的过程中还是遇到了不少的问题，还好最后在同学和老师的帮助下我们都将 难题一一的解决掉了。这次的综合性设讣是我们在对数据结构这门课程学习过程中的一大跃 进，也是我们再次认识数据结构的一次很好的机会！使我们不仅可以学到扎实 的理论知识，而且，还可以培养我们动手的实践能力

14、！数据结构这门课对于儿个模块，在程序设计中并没有遇到多大的困难，只是在设汁调试的过 程中遇上了不少的麻烦。如在调试总程序时遇上可很多差错，在改错上花了不少的 功夫。在同学和老师的帮助下解决了很多问题，这就是我们在程序设讣中遇到的问 题。在完成的过程中，老师给了我们很大的帮助，在此谢谢老师。6致谢这次我做的是一元多项式的程序设计，开始编程时并不是很顺利。有很多不 懂的地方，但是最后通过查阅资料和请教老师把困难一个一个都克服了。这让我不 禁感到很高兴，自己做出来的程序很有成就感。在这次的实习过程中我也学会了很 多知识，以前自己模糊不清的概念在这次实习中也能够理解了，而且也学会很多首先程序能够成功顺利的完成要感谢学校给我们提供了有利的资源，也感谢 老师的谆谆教导，当我运行程序遇到错误或有不会的问题时老师都很有耐心的指导 我们，所以这里非常感谢我的