----数据结构与算法

《----数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、问题分析和任务定义课程设计的题目是一元多项式计算，即实现两个一元多项式之间的运算，并输出运算的结果。1.问题分析（1）输入的形式和输入值的范围：输入是从键盘输入的，输入的内容为多项式的系数和指数，系数为任意整数，指数为大于等于0的整数（2）输出的形式从屏幕输出，显示用户输入的多项式，并显示多项式加、减以后的多项式的值。（3）存储结构在这次设计中开始我是采用顺序存储结构，使得多项式相加的算法定义十分简洁。至此，一元多项式的表示及相加问题似乎已经解决了。然而，在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。特别是在处理形如的多

2、项式时，就要用一个长度为20001的线性表来表示，表中仅有3个非零元素，这种对内存空间的浪费是应当避免的，但是如果只存储非零系数项则显示必须同时存储相应的指数。   一般情况下的一元n次多项式可写成其中，是指数为的项的非零系数，且满足若用一个长度为m且每个元素有两个数据项(系数项和指数项)的线性表便可惟一确定多项式。在最坏情况下，n+1(=m)个系数都不为零，则经只存储每项系数的方案要多存储一倍的数据。但是，对于S(x)类的多项式，这种表示将大大节省空间。2、任务定义a：输入并建立多项式；b：输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,……,cn

3、,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；c：多项式a和b相加，建立多项式a+b；d：多项式a和b相减，建立多项式a-b。e：多项式的输出形式为类数学表达式。系数值为1的非零项的输出形式中略系数1。而-1x的输出形式为-x。二、数据结构的选择和概要设计：本题设计要求能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加，相减，并将结果输入。（1）数据结构的选用A:基于链表中的节点可以动态生成的特点，以及链表可以灵活的添加或删除节点的数据结构，为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数

4、，指数，下一个指针3个元属；例如，图1中的两个线性链表分别表示一元多项式和一元多项式。从图中可见，每个结点表示多项式中的一项。图1多项式表的单链存储结构B：本设计使用了以下数据结构：typedefstructterm{//项的表示，多项式的项作为LinkList的数据元素floatcoef;//系数intexpn;//指数structterm*next;}term;C：设计本程序需用到九个模块，用到以下九个子函数如下：1：term*CreatPolyn(term*Printm)//输入m项的系数和指数，建立表示一元多项式的有序链表P2：term*selsort(

5、term*h){//按照指数降序用冒泡排列进行排序3：Compare(term*a,term*b){//按指数的大小进行比较4：voidPrintfPoly(term*P){//打印输出一元多项式P5：term*APolyn(term*Pa,term*Pb){//多项式加法：Pa=Pa＋Pb，利用两个多项式的结点构成"和多项式"。6：term*A(term*Pa,term*Pb){//输入一个一元多项式7：term*BPolyn(term*Pa,term*Pb){//多项式减法：Pa=Pa-Pb，利用两个多项式的结点构成"差多项式"。8：term*B(term*

6、Pa,term*Pb){//输入第二个一元多项式。9：main()//主程序模块调用链一元多项式的各种基本操作模块。（2）多项式的输入采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入。（3）两个多项式的加法“和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：①指

7、针qa所指结点的指数值<指针qb所指结点的指数值，则应摘取qa指针所指结点插入到“和多项式”链表中去；②指针qa所指结点的指数值>指针qb所指结点的指数值，则应摘取指针qb所指结点插入到“和多项式”链表中去；③指针qa所指结点的指数值=指针qb所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。图2相加得到的和多项式    上述多项式的

8、相加过程归并两个有序表的