哈夫曼编码课设说明书

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

实践教学

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

计算机与通信学院

2016年秋季学期

算法与数据结构课程设计

题 目：哈夫曼的编/译码系统 敢死队问题 专业班级：

姓 名： 学 号： 指导教师： 成 绩：_______________

目录

摘要 .......................................................................................................................... 1 一．哈夫曼码的编/译码系统 ................................................................................. 2 1.采用类语言定义相关的数据类型 ................................................................... 2 2.算法设计 ........................................................................................................... 2 3.函数的调用关系图 ........................................................................................... 5 4.调试分析 ........................................................................................................... 5 5.测试结果 ........................................................................................................... 6 6.源程序（带注释） ........................................................................................... 8 二．敢死队问题 .................................................................................................... 23 1.采用类语言定义相关的数据类型 ................................................................. 23 2.算法设计 ......................................................................................................... 24 3.函数的调用关系图 ......................................................................................... 28 4.调试分析 ......................................................................................................... 28 5.测试结果 ......................................................................................................... 30 6.源程序（带注释） ......................................................................................... 30 总结 ........................................................................................................................ 37 参考文献 ................................................................................................................ 38 致谢 ........................................................................................................................ 38

算法与数据结构课程设计

摘要

哈夫曼编译系统是为了实现一个利用哈夫曼算法的编码和译码系统。比如，再利用电报进行通讯时，需要将文字转换成由二进制的字符组成的字符串。但是在传送过程中，总希望长度能够尽可能的短，于是我们想采用长度不等的编码。但是这种编码必须遵循：任何一个字符的编码都不是另一个字符编码的前缀。因此哈夫曼编译系统能够正确的使得对于输入的字符进行编码以及译码，并且是的在译码过程中不会出错，同时能够将编码以及译码的结果正确的存入文件当中。

敢死队问题主要是用两种数据结构方法实现敢死队问题。从1到M个数据，采用链表和队列存储，由于是轮回数数，需要循环，因此所用的链表是单向循环链表，所用的队列是循环队列。战士去执行任务，若没有完成任务，则需要把该战士的号码从队列或者链表中删除。由于要求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务，所以程序从1号到M号逐个开始计数，从计数的战士开始的第五个战士去执行任务，若没完成任务，则删除之，从被删除战士下一个号码开始计数，后边的第五个战士接着开始去执行任务，若没完成任务，则删除之，如此循环，直到最后一个战士，若最后一个战士是排长，即1号，则终止循环，记下开始计数的战士的号码即为所求。

关键词： 哈夫曼树；队列；链表；指针

1

算法与数据结构课程设计

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

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

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

哈夫曼码的编/译系统主要采用的数据结构为树和链表和数组。其中链表是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，结点可以动态生成。而树是包含n（n>0）个结点的有穷集合K，且在K中定义了一个关系N，N满足 以下条件：

（1）有且仅有一个结点 K0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根。

（2）除K0外，K中的每个结点，对于关系N来说有且仅有一个前驱。 （3）K中各结点，对关系N来说可以有m个后继（m>=0） 输入/输出数据： 数据 权值 父结点，左右孩子结点 节点数 开始位置

数据类型： 字符型 浮点型 整型 整型 整型 表A-1主要数据类型

2.算法设计

? 构造哈夫曼树的算法

在哈夫曼树中，没有度为1的结点，这类二叉树称为严格二叉树。那么对于一颗含有n个结点的哈弗曼树共有2n-1个结点所以哈夫曼算法可以用一维数组实现。显然每个结点的存储结构都应该有一个域存放权值；构成Huffman树之后，

2