信息12-1班 201211041039 庄建——课程设计报告.doc

成绩：__________________ 算法与数据结构 课程设计报告 学院名称　 理学院 专业班级　　　 1、 模块2：一元多项式计算 2、 模块8：建立二叉树，层序、先序遍历 3、 模块9：赫夫曼树的建立 1、模块2：一元多项式计算 （1）系统分析 建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果 （2）概要设计 存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 1． 单连表的抽象数据类型定义： ADT List{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={ai-1,ai| ai-1, ai∈D,i=2,…,n} 基本操作： InitList（＆L） //操作结果：构造一个空的线性表 CreatPolyn(L) //操作结果：构造一个以单连表存储的多项试 DispPolyn(L) //操作结果：显示多项试 Polyn(pa,pb) //操作结果：显示两个多项试相加，相减的结果 } ADT List 2． 本程序包含模块： typedef struct LNode //定义单链表 { }LNode,*LinkList; void InitList(LinkList L) //定义一个空表 { } void CreatPolyn(LinkList L) //用单链表定义一个多项式 { } void DispPolyn(LinkList L) //显示输入的多项式 { } void Polyn(LinkList pa,LinkList pb) {} void main() { //定义一个单连表； coutendl *****************欢迎来到一元多项式计算程序 *************** endl; LNode *L1,*L2; Polyn(L1,L2); } 2.1 加，减操作模块——实现加减操作 各模块之间的调用关系如下： 主程序模块 加法操作模块 减法操作模块 基本算法： 1、输入输出 （1）功能：将要进行运算的多项式输入输出。 （2）数据流入：要输入的多项式的系数与指数。 （3）数据流出：合并同类项后的多项式。 （4）程序流程图：多项式输入流程图如图1所示。 （5）测试要点：输入的多项式是否正确，若输入错误则重新输入  2、多项式的加法 （1）功能：将两多项式相加。 （2）数据流入：输入函数。 （3）数据流出：多项式相加后的结果。 （4）程序流程图：多项式的加法流程图如图2所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。 图表 2 3、多项式的减法 （1）功能：将两多项式相减。 （2）数据流入：调用输入函数。 （3）数据流出：多项式相减后的结果。 （4）程序流程图：多项式的减法流程图如图3所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。 1. 根据题目要求采用单连表存储结构 typedef struct LNode //定义单链表 { }LNode,*LinkList; void InitList(LinkList L) //定义一个空表 { } void CreatPolyn(LinkList L) //用单链表定义一个多项式 { } void DispPolyn(LinkList L) //显示输入的多项式 { } void Polyn(LinkList pa,LinkList pb) {} 2．主函数 main void main() { LNode *L1,*L2; Polyn(L1,L2); } 2. 函数的调用关系层次结构 多项式 Polyn 用单链表定义多项式 CreatPolyn 定义一个空表 InitList 显示输入的多项式 DispPolyn } 五. 调试分析 采用单连表形式按照指数降序排列建立并输出多项式；在相加，相减的过程 中如果指数相同就执行系数相加，相减，否则就把大的项直接写入。完成两个多 项式的相加、相减;将从新得到的单连表结果输出；该算法的时间复杂度为两个 多