元多项式的相加报告.docVIP

数据结构课程设计报告 题目：一元多项式的相加 班级：信息与计算科学 姓名：施苏杰 学号:0911080128 1、实验目的 能够熟悉地掌握并完成链表的一些基本操作，包括： （1）链表的初始化和建立一个新的链表； （2）链表结点的插入以及删除； （3）链表的输出； 2、实验内容 建立两个稀疏多项式，用链式存储表示，将两个多项式相加后得到的链表打印输出。 3、算法分析 （1）数据存储结构 struct polynomial{ float coef; int expn; polynomial *next; }; (2)整体框架 1）在输入一元多项式polynomial* creatpolyn()中，可以完成自动排序，每当输入一个指数和系数，就判断该结点指数的大小，然后选择插入的位置。如果新生成的结点指数大于当前结点，就直接连接到链表的后面，如果新生成的结点指数小于当前结点，则插入到当前结点的前面，继续判断循环，直到插入到恰当的位置，如果两者的指数相等就将系数相加，如果系数不为零就把系数换成它们的和，否则就删掉这个结点。所以在输入系数和指数的时候，可以不按指数的递增，而选择乱序输入。 2）再相加函数void addpolyn(polynomial *pa,polynomial *pb)中，采用了书上所给的算法，pa=pa+pb，将相加的结果并入到pa中。将qa和qb分别指向pa和pb的当前结点，判断qa和qb所指结点指数的大小，如果qa的指数小于qb，则qa指向下一个结点，如果qb的指数小于qa，则将qb这个结点插入到pa中，若两者的指数相等，则将两者系数相加，判断是否为零，如果是零，就将结点删掉，qa qb都指向下一个结点，否则就将qa的系数换成它们的和。到最后如果pb上还有剩余结点，就将它们全部连到pa上，pa也一样。返回pa。 3）在输出函数void print(polynomial *fun)中，主要考虑下列问题：如果系数为1，就不打印系数，如果系数为-1，就只打印负号，其他的，系数为正就打印+号，为负就只打印系数，还有指数为0时，就只打印系数，不打x,指数为1就打x。 4、数据测试 输入系数和指数，用空格隔开，输入一组回车输下一组，以输入0 0结束。 1）输入 3 3↙2 2↙1 1↙0 0↙ 5 5↙2 3↙-4 4↙3 2↙0 0↙ 2）输入-2 1↙3 3↙4 5↙5 4↙0 0↙ 1 1↙-4 3↙0 0↙ 3）输入1 1↙3 0↙2 100↙0 0↙ 2 2↙-3 50↙0 0↙ 5、总结 我觉得数据结构是一门很重视逻辑思维的课程，这也体现在了课程设计编写程序中，比如在设计一元多项式相加这个程序时，关于指针的指向，结点的删除以及插入，各种条件的判断，就需要很强的逻辑性来完成，一旦一个指针发生了错误，就可能导致整个程序无法运行，一些逻辑上的错误也可能使得结果出错，所以我们在考虑问题是应该有一个严密的思维体系。总的来说，编写完这个程序，经过自己的实践，使我对链表的使用有了更深的了解，还有，这个程序还有一些不完善的地方，比如说没做乘法，我会通过编程能力的提高和更深入的学习来去完成。 6、致谢 我想感谢胡雪蕾老师的指导，梁晟，黄达益在算法上的支持以及对程序中几处bug的修改，最后，我想感谢我的同学和我在学习中无尽的探讨，使得我的程序得以实现。 主函数 void main() 输入一元多项式 polynomial* creatpolyn() 一元多项式的相加 void addpolyn(polynomial *pa,polynomial *pb) 输出一元多项式 void print(polynomial *fun)