----数据结构与算法.doc

一、问题分析和任务定义课程设计的题目是一元多项式计算，即实现两个一元多项式之间的运算，并输出运算的结果。1.问题分析 （1） 输入的形式和输入值的范围： 输入是从键盘输入的，输入的内容为多项式的系数和指数，系数为任意整数，指数为大于等于0的整数（2） 输出的形式 从屏幕输出，显示用户输入的多项式，并显示多项式加、减以后的多项式的值。 （3）存储结构在这次设计中开始我是采用顺序存储结构，使得多项式相加的算法定义十分简洁。至此，一元多项式的表示及相加问题似乎已经解决了。然而，在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。特别是在处理形如的多项式时，就要用一个长度为20 001的线性表来表示，表中仅有3个非零元素，这种对内存空间的浪费是应当避免的，但是如果只存储非零系数项则显示必须同时存储相应的指数。 一般情况下的一元n次多项式可写成其中，是指数为的项的非零系数，且满足若用一个长度为m且每个元素有两个数据项(系数项和指数项)的线性表便可惟一确定多项式。在最坏情况下，n+1(=m)个系数都不为零，则经只存储每项系数的方案要多存储一倍的数据。但是，对于S(x)类的多项式，这种表示将大大节省空间。2、任务定义a： 输入并建立多项式； b： 输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； c： 多项式a和b相加，建立多项式a+b； d： 多项式a和b相减，建立多项式a-b。 e： 多项式的输出形式为类数学表达式。 系数值为1的非零项的输出形式中略系数1。而-1x的输出形式为-x。二、数据结构的选择和概要设计：本题设计要求能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加，相减，并将结果输入。（1） 数据结构的选用 A:基于链表中的节点可以动态生成的特点，以及链表可以灵活的添加或删除节点的数据结构，为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属；例如，图1中的两个线性链表分别表示一元多项式和一元多项式。从图中可见，每个结点表示多项式中的一项。图1 多项式表的单链存储结构B：本设计使用了以下数据结构：typedef struct term /项的表示，多项式的项作为LinkList的数据元素 float coef; /系数 int expn; /指数 struct term *next; term;C：设计本程序需用到九个模块，用到以下九个子函数如下：1：term* CreatPolyn(term *Print m) / 输入m项的系数和指数，建立表示一元多项式的有序链表P2：term* selsort(term *h) /按照指数降序用冒泡排列进行排序3：Compare(term *a, term *b) /按指数的大小进行比较4：void PrintfPoly(term *P) /打印输出一元多项式P5：term* APolyn(term *Pa, term * Pb) / 多项式加法：Pa = PaPb，利用两个多项式的结点构成和多项式。6：term* A(term *Pa, term * Pb) /输入一个一元多项式7：term* BPolyn(term *Pa, term * Pb) / 多项式减法：Pa = Pa-Pb，利用两个多项式的结点构成差多项式。8：term* B(term *Pa, term *Pb) /输入第二个一元多项式。9：main()/主程序模块调用链一元多项式的各种基本操作模块。（2）多项式的输入 采用尾插法的方式，输入多项式中一个项的 系数和 指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入。 （3） 两个多项式的加法 “和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：指针qa所指结点的指数值指针qb所指结点的指数值，则应摘取指针qb所指结点插入到“和多项式”链表中去；指针qa所指结点的指数值=指针qb所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。图2 相加得到的和多项式上述多项式的相加过程归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况。因此，多项式相加的过程也完全可以利用线性链表的基本操作来完成。（4）两个多项式的减法 两个多项式的减法实现，是从2个多项式的尾部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相减；相减的和不为0的话，用尾插法建立一个新的节点。p的系数小于q的系数的话，就应该复制q接点到多项式中。p的系数大于q的系数的话，就应该复制p接点到多项式中，并且建立的接点的系数为原来的相反数；当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生。当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生，并且建立的接点的系数为原来的相反数。（5）流程图 （1）在主函数中调用函数进行多项式的输入、输出，运用选择语句来选择加法、减法进行操作，流程图如图3：1输入一一元多项式的项数n23YYN结束开始1：加2：减3：退出输入n个非零项再输入一一元多项式的项数依次输入n个非零项调用加法运算term* APolyn再输入一一元多项式的项数依次输入n个非零项调用减法运算term* BPolyn输出相加结果输出相减结果YN图3 主函数流程图（2）两个多项式相加就是两个多项式中同指数项的对应系数相加，若和不为零，则形成“和多形式”中的一项，所有指数不同的项均直接移位至“和多项式”中，流程图如图4：开始比较qa和qb所指节点的指数项1：qa所指结点的指数值 qb所指结点的指数值=1=0=-1结束摘取qa指针所指结点插入到“和多项式”链表中去将两个结点中的系数相加。看和数是否为零修改qa所指结点的系数值，同时释放qb所指结点删除相应结点，并释放qa和qb所指结点摘取qb指针所指结点插入到“和多项式”链表中去YNNYYNY图4 两个一元多项式相加（3）两个一元多项式的相减就是2个多项式的尾部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相减；相减的和不为0的话，建立一个新的节点。p的系数小于q的系数的话，就应该复制q接点到多项式中。p的系数大于q的系数的话，就应该复制p接点到多项式中，并且建立的接点的系数为原来的相反数；当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生。当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生，并且建立的接点的系数为原来的相反数。开始1：第2个多项式空，第1个数不为空0：2个多项式的某一项都不为空时-1：第1个多项式空，第1个数不为空 =1=0=-1结束将第一个数剩下的全用新节点产生将两个结点中的系数相减。看是否为零用尾插法建立一个新的节点删除相应结点，并释放qa和qb所指结点将第2个数剩下的全用新节点产生，并且建立的接点的系数为原来的相反数YNNYYNY图5 两个一元多项式相减三、详细设计和编码1、算法思想（1） 输入并建立多项式creatpolyn()（2） 输出多项式，输出形式为整数序列，序列按指数降序排列printpolyn()（3） 多项式a和b相加，建立多项式a+b，输出相加的多项式addpolyn()（4） 多项式a和b相减，建立多项式a-b，输出相减的多项式subpolyn()用带表头结点的单链表存储多项式。2、算法描述：A:建立多项式链表for (i = 1; i coef,&P-expn); /键入多项式的系数和指数项if(P-coef) q = P; P = P-next = (term*)malloc(sizeof(term); /生成一个结点 q-next = NULL; free(P); 多项式单链表可以用尾插法建表来生成。通过从键盘按升幂的次序输入多项式各项的系数和指数，以输入指数-1为结束标志。B: 按照指数降序排列for(p = h,q = h-next;q;p = p-next,q = q-next) if (p-expn expn) /如果p的指数小于q的指数f = p-coef;i = p-expn;p-coef = q-coef;p-expn = q-expn; q-coef = f;q-expn = i; /把p和q互换fini = 1; 按照题目要求进行排序，采用的是冒泡排序C：比较if (a-expn expn) return -1; /如果多项式a的指数小于多项式b的指数，则回到-1if (a-expn b-expn) return 1; /如果多项式a的指数小于多项式b的指数，则回到-1这个模块主要是比较两个多项式的指数大小D：输出一元多项式if(q-coef!=1) /如果系数不等于1printf(%g,q-coef); /把系数输出if(q-expn=1) putchar(X); /如果系数为1则直接输出Xelse if(q-expn) printf(X%d,q-expn); /输出的形式为X%d else if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); /如果指数为1，则输出Xelse printf(X%d,q-expn); q = q-next; while (q) if(q-coef 0) putchar(+); /如果系数大于