哈夫曼的编译码系统-关键路径-理发师问题-算法与数据结构课程设计说明书.doc

PAGE

*******************

实践教学

*******************

XXXX大学

计算机科学与技术学院

2021年春季学期

算法与数据结构课程设计

题目：哈夫曼的编/译码系统

实现关键路径的计算

理发师问题

专业班级：计算机科学与技术四班

姓名：XXXX

学号：1010240000

指导教师：张老师

成绩：

目录TOC\o1-3\h\z\u

摘要 3

一．哈夫曼码的编/译码系统 4

1. 采用类语言定义相关的数据类型 4

2. 算法设计 4

3.函数的调用关系图 5

4.调试分析 5

5.测试结果 6

6.源程序 7

二．实现关键路径的计算问题 11

1.采用类语言定义相关的数据类型 11

2.算法设计 11

3函数的调用关系图 12

4.调试分析 13

5.测试结果 13

6.源程序 13

三．理发师问题 18

1.采用类语言定义相关的数据类型 18

2.算法设计 18

3函数的调用关系图 19

4.调试分析 20

5.测试结果 20

6.源程序 21

总结 26

参考文献 27

致谢 28

PAGE10

摘要

在哈夫曼码的编/译码系统问题中，要求对输入的哈夫曼码进行译码和以及将输入的文本编译成哈夫曼码，根据提供的各个结点的权值利用树的链式存储结构构建哈夫曼树求解。在实现关键路径的计算问题中，要求根据提供的至少6个结点找到关键路径，将各个结点存入邻接矩阵，对各个结点进行拓扑排序和逆拓扑排序建立AOE网求解，再比对活动的最早开始时间和最迟开始时间得到关键路径。在理发师问题中，要求模拟一个有着N张座椅和三种等级的理发师的理发店一天的经营状况，最后输出顾客在店内的逗留时间、队列的平均长度、收尾的时间、营业额以及各个等级的理发师创收，本题用数组模拟队列求解。

关键词：哈夫曼树；AOE网；拓扑排序；队列

一．哈夫曼码的编/译码系统

编写一个哈夫曼码的编/译码系统，实现对输入的文本信息自动统计并依此为依据建立一个哈夫曼码的编/译码系统。

采用类语言定义相关的数据类型

intweight;表示结点的权重。

intparent,left,right;分别表示结点的父亲结点、左孩子结点和右孩子结点。

算法设计

创建哈夫曼树：输入N，N为叶子结点的个数，构建长度为2N的数组用于存放各个结点，其中第1号到第N号为叶子结点（为提高代码可读性摈弃了0号位置），它们代表的内容存入另一个数组，在起点为N+1重点为2N-1的for循环内，每次挑选权值最小的两个结点构建结点，如图1-1第一部分，左孩子的边标为“0”，右孩子的边标为“1”，如图1-1第二部分，并将它们的左孩子、右孩子以及父亲结点的序号分别存入left、parent、right。

利用哈夫曼树进行编码：输入一句字符串，去除空格后，先查找字符串内容是否都被哈夫曼树包含，之后找到此字符的所在序号（序号在1到N内），如果此节点是其父亲节点的左孩子则所属字符串加0，右孩子则加1，从下往上直至根节点，在将得到的字符反转，得到哈夫曼码，其余字符依次实现。

利用哈夫曼树进行译码：输入一句由‘0’和‘1’组成的字符串，由根结点开始，如果是‘0’则沿左孩子向下反之则沿右孩子下降，直至叶子结点得到该字符串代表的字符。得到字符后从下一个字符反复重复如上操作，直至遍历完字符串。

图1-1哈夫曼树的构建

3.函数的调用关系图

首先在主函数中选择creatHFtree函数，在creatHFtree内调用select函数构建哈夫曼树，在得到哈夫曼树后，可以选择Code或Decode函数选择编码或译码，如图1-1所示。

图SEQ图\*ARABIC1-2函数的调用关系图

4.调试分析

调试中遇到的问题及对问题的解决方法

得到的哈夫曼码与实际的相反，原因：构建哈夫曼码是是从叶子结点开始，而实际应当从根节点开始。解决方法：将得到的哈夫曼码反转。

算法的时间复杂度和空间复杂度

构建哈夫曼树的时间复杂度为O(n),空间复杂度为O(2n)，其中n为叶子结点个数。

哈夫曼编/译码的时间复杂度为O(n)，空间复杂度为为O(n)，其中n为字符串长度。

5.测试结果

测试用例：

叶子：a，b，c，d，e，f，g，对应权值：1