1、 计算机科学与技术系 课程设计报告 2009 2010 学年第 2 学期 课程课程 数据结构与算法 课 程 设 计 名 称课 程 设 计 名 称 一元多项式的计算问题 学生姓名学生姓名 学号学号 专业班级专业班级 指导教师指导教师 2010 年 6 月 题目： （题目： （一元多项式的计算问题）要求能够按照指数降序排列建立并输出一元多项式；能够 完成两个一元多项式的相加、相减，并将结果输入。 一一、问题分析和任务定义问题分析和任务定义 1.问题问题分析分析 本程序关键点是如何将输入的两个多项式相加、相减操作。 如何将输入的一元多项式按指数的降序排列 如何确定要输入的多项式的项数； 如何将输入的
2、两个一元多项式显示出来。 如何将输入的两个一元多项式进行相加操作。 如何将输入的两个一元多项式进行相减操作。 本程序是通过链表实现一元多项式的相加减操作。 2、任务定义任务定义 此程序需要完成如下的要求：将多项式按照指数降序排列建立并输出，将两个一元多项式 进行相加、相减操作，并将结果输入。 a： 输入多项式的项数并建立多项式； b： 输出多项式，输出形式分别为浮点和整数序列，序列按指数升序排列； c： 多项式 a 和 b 相加，建立多项式 a+b； d： 多项式 a 和 b 相减，建立多项式 a-b。 e： 多项式的输出。 二、数据结构的选择和概要设计：二、数据结构的选择和概要设计： （1）
3、 数据结构的选用数据结构的选用 A:基于链表中的节点可以动态生成的特点， 以及链表可以灵活的添加或删除节点的数据结 构，为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数， 下 一 个 指 针 3 个 元 属 ； 例 如 ， 图 1 中 的 两 个 线 性 链 表 分 别 表 示 一 元 多 项 式 和一元多项式。从图中可见，每个结点表示多项 式中的一项。 图 1 多项式表的单链存储结构 B：本设计使用了以下数据结构： typedef struct float coef; /系数 int expn; /指数 ElemType； typedef struct LNode
4、ElemType data; struct LNode *next; LNode; C：设计本程序需用到九个模块，用到以下九个子函数如下： 1、void Menu()/建立菜单 2、LNode *InitList() / 创建链表 3、void ChaLNode(LNode *L,ElemType x)/插入链表 4、LNode *AddPolyn(LNode *A,LNode *B)/多项式相加 5、void Invert(LNode *L)/逆序输出链表 6、void Print(LNode *L)/输出多项式 7、main()/主程序模块调用链一元多项式的各种基本操作模块。 （2）多项式
5、的输入多项式的输入 先输入多项式的项数，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生 一个新的节点，建立起它的右指针，并用头节点指向它； （3） 两个多项式的加法两个多项式的加法 “和多项式”链表中的结点无需另生成， 而应该从两个多项式的链表中摘取。 其运算规 则如下： 假设指针 A 和 B 分别指向多项式 a 和多项式 b 中当前进行比较的某个结点，则比较两 个结点中的指数项，有下列 3 种情况： 指针 A 所指结点的指数值指针 B 所指结点的指数值，则应摘取指针 A 所指结点插 入到“和多项式”链表中去； 指针 A 所指结点的指数值=指针 B 所指结点的指数值，则将两个结点中的
6、系数相加， 若和数不为零，则修改 A 所指结点的系数值，同时释放 B 所指结点；反之，从多项式 A 的 链表中删除相应结点，并释放指针 A 和 B 所指结点。例如，由图 2 中的两个链表表示的多 项式相加得到的“和多项式”链表如图 2 所示，图中的长方框表示已被释放的结点。 图 2 相加得到的和多项式 上述多项式的相加过程归并两个有序表的过程极其类似， 不同之处仅在于， 后者在 比较数据元素时只出现两种情况。 因此， 多项式相加的过程也完全可以利用线性链表的基本 操作来完成。 （4）两个多项式的减法两个多项式的减法 两个多项式的减法实现，依然调用的是多项式加法的函数，只是在调用前，把多项式 二的系数全部变为相反数 c.coef=-c.coef;，然后多项式一和多项式二相加，这样就实现了 多项式的相减。流程图如上。 （5）流程图流程图 （1）在主函数中调用函数进行多项式的输入、输出，运用选择语句来选择加法、减法进行 操作，流程图如图 3： 图图 3 主函数流
