1、算法与数据结构课程设计报告 1 成绩：_ 算法与数据结构 课程设计报告 算法与数据结构课程设计报告 2 目录目录 1、 模块模块 2：一元多项式计算一元多项式计算 2、 模块模块 8：建立二叉树，层序、先序遍历建立二叉树，层序、先序遍历 3、 模块模块 9：赫夫曼树的建立赫夫曼树的建立 算法与数据结构课程设计报告 3 1、模块、模块 2：一元多项式计算一元多项式计算 （1）系统分析 建立一元多项式并按照指数降序排列输出多项式， 将一元多项式输入并存储 在内存中，能够完成两个多项式的加减运算并输出结果 （2）概要设计 存储结构：存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储
2、空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系 数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项 结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情 况进行分析，实现一元多项式的相加、相减操作。 1 单连表的抽象数据类型定义： ADT List 数据 对象： D=ai|ai ElemSet,i=1,2,n,n0 数据 关系： R1=| ai-1, aiD,i=2,n 基本操作： InitList（L） /操作结果：构造一个空的线性表 CreatPolyn( void InitList(LinkList 算法与数据结构课程设计报告
3、 4 LNode *L1,*L2; Polyn(L1,L2); 2.1 加，减操作模块实现加减操作 各模块之间的调用关系如下： 主程序模块 加法操作模块 减法操作模块 基本算法：基本算法： 1、输入输出 （1）功能：将要进行运算的多项式输入输出。 （2）数据流入：要输入的多项式的系数与指数。 （3）数据流出：合并同类项后的多项式。 （4）程序流程图：多项式输入流程图如图 1 所示。 （5）测试要点：输入的多项式是否正确，若输入错误则重新输入 用户菜单 多项式链表 各函数 退出 指针数组 主函数 开始 申请结点空间 输入多项式的项数 输入多项式各项的系数 x, 指数 y 图表 1 算法与数据结构
4、课程设计报告 5 2、多项式的加法 （1）功能：将两多项式相加。 （2）数据流入：输入函数。 （3）数据流出：多项式相加后的结果。 （4）程序流程图：多项式的加法流程图如图 2 所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运 算。 图表 2 开始 定义存储结果的空链 r 是 否 输出存储多项式的和的链 r 结束 是 否 同指数项系数相加后存入 r 直接把 p 中 各项存入 r 直接把 q 中 各项存入 r 存储多项式2的空 链 Q 是否为空 存储多项式 1 的空 链 P 是否为空 合并同类项 算法与数据结构课程设计报告 6 3、多项式的减法 （1）功能：将两多项式相
5、减。 （2）数据流入：调用输入函数。 （3）数据流出：多项式相减后的结果。 （4）程序流程图：多项式的减法流程图如图 3 所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运 算。 开始 定义存储结果的空链 r 是 否 输出存储多项式的和的链 r 结束 是 否 同指数项系数相加后存入 r 把 p 中各项系数 改变符号后存入 r 直接把 q 中 各项存入 r 存储多项式2的空 链 Q 是否为空 存储多项式 1 的空 链 P 是否为空 合并同类项 图表 3 算法与数据结构课程设计报告 7 1. 根据题目要求采用单连表存储结构 typedef struct LNode /定义单
6、链表 LNode,*LinkList; void InitList(LinkList Polyn(L1,L2); 2. 函数的调用关系层次结构 多项式 Polyn 用单链表定义多项式 CreatPolyn 定义一个空表 InitList 显示输 入的多项式 DispPolyn 五. 调试分析 采用单连表形式按照指数降序排列建立并输出多项式；在相加，相减的过 程 中如果指数相同就执行系数相加，相减，否则就把大的项直接写入。完成两 个多 项式的相加、相减;将从新得到的单连表结果输出；该算法的时间复杂度为 两个 多项式的项式之和 (3)详细设计 #include #include typedef struct Polynomial float coef; int expn; struct Polynomial *next; 算法与数据结构课程设计报告 8 *Polyn,Polynomial; /Polyn 为结点指针类型 void In
