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

一、问题分析和任务定义 课程设计的题目是一元多项式计算，即实现两个一元多项式之间的运算，并输出运算的结果。 1.问题分析  输入的形式和输入值的范围： 输入是从键盘输入的，输入的内容为多项式的系数和指数，系数为任意整数，指数为大于等于0的整数 输出的形式 从屏幕输出，显示用户输入的多项式，并显示多项式加减以后的多项式的值。 采用顺序存储结构，使得多项式相加的算法定义十分简洁。至此，一元多项式的表示及相加问题似乎已经解决了。然而，在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。特别是在处理形如 的多项式时，就要用一长度为20 001的线性表来表示，表中仅有3个非零元素，这种对内存空间的浪费是应当避免的，但是如果只存储非零系数项则显示必须同时存储相应的指数。??? 一般情况下的一元n次多项式可写成 其中，是指数为的项的非零系数，且满足 若用一个长度为m且每个元素有两个数据项(系数项和指数项)的线性表 便可惟一确定多项式。在最坏情况下，n+1(=m)个系数都不为零，则经只存储每项系数的方案要多存储一倍的数据。但是，对于S(x)类的多项式，这种表示将大大节省空间。a： 输入并建立多项式； b： 输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,……,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； c： 多项式a和b相加，建立多项式a+b； d： 多项式a和b相减，建立多项式a-b。 ： 多项式的输出形式为类数学表达式。 系数值为1的非零项的输出形式中略系数1。而-1x的输出形式为-x。数据结构的选用 为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属；例如，图中的两个线性链表分别表示一元多项式和一元多项式。从图中可见，每个结点表示多项式中的一项。B：本设计使用了以下数据结构： typedef struct term { //项的表示，多项式的项作为LinkList的数据元素 float coef; //系数 int expn; //指数 struct term *next; }term; C：设计本程序需用到九个模块，用到以下九个子函数如下： 1：term* CreatPolyn(term *Print m) // 输入m项的系数和指数，建立表示一元多项式的有序链表P 2：term* selsort(term *h) {//按照指数降序用冒泡排列进行排序 3：Compare(term *a, term *b) {//按指数的大小进行比较 4：void PrintfPoly(term *P) {//打印输出一元多项式Pterm* A(term *Pa, term * Pb) {//输入一个一元多项式 7：term* BPolyn(term *Pa, term * Pb) { // 多项式减法：Pa = Pa-Pb，利用两个多项式的结点构成差多项式。 8：term* B(term *Pa, term *Pb) {//输入第二个一元多项式。 9：main()//主程序模块调用链一元多项式的各种基本操作模块多项式的输入 采用插法的方式，输入多项式中一个项的 系数和 指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入 （3） 两个多项式的加法 “和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：假设指针q和q分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：①指针q所指结点的指数值指针q所指结点的指数值，则应摘取q指针所指结点插入到“和多项式”链表中去；②指针q所指结点的指数值指针q所指结点的指数值，则应摘取指针q所指结点插入到“和多项式链表中去；③指针q所指结点的指数值=指针q所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改q所指结点的系数值，同时释放q所指结点；反之，从多项式A的链表中删除相应结点，并释放指针q和q所指结点。例如，由图中的两个链表表示的多项式相加得到的“和多项式”链表如图所示，图中的长方框表示已被释放的结点。 ????上述多项式的相加过程归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况。因此，多项式相加的过程也完全可以利用线性链表的基本操作来完成。两个多项式的减法 从2个多项式的部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相减；相的和不为0的话，用插法建立一个新的节点。p的系数小于