数据结构课程设计

题目：编制一个可进行传数据编码及接收数据译码的编/译系统

要求：（1）用Huffman树给出Huffman编码；

（2）可单独或小组的形式完成，但至多3人；

（3）写出实验报告，并提交电子文档及源程序。

一、 需求分析：

1、根据用户指定的字符表和频度的实际统计数据建立Huffman树；

2、其中其叶子结点表示字符的权值及父母、左、右孩子等结点的信息；

3、其左右分支分别用代码0、1表示；

4、本系统的目的是为用户提供编/译码系统，根据用户输入的字符依字符集的权值进行编码保存；

5、根据接收到的编码进行译码；

6、输出其内容。

二、测试数据：

（1）、利用教科书(P148)例6-2中的数据调试程序。

（2）、用下表给出的字符集和频度的实际统计数据建立Huffman树，并实现以下报文的编码和译码：“THIS # PROGRAM # IS # MY # FAVORITE”。

字符 # A B C D E F G H I J K L M

频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20

字符 N O P Q R S T U V W X Y Z

频度 57 63 15 1 48 51 80 23 8 18 1 16 1

三、 详细设计：

抽象数据类型HuffmanTree的定义如下：

typedef struct

{

char data; //结点字符

int weight; //结点权值

int parent,lchild,rchild; //父子结点

}HTNode,HuffmanTree;

typedef char HuffmanCode;

基本操作P：

CreateHuffmanTree（&HT,）;

初始条件：给出HuffmanTree的定义。

操作结果：构造HuffmanTree。

HuffmanCoding(HuffmanTree HT,HuffmanCode &HC)

初始条件：HT存在。

操作结果：得出编码HC。

PrintHuffmanCode(HuffmanTree HT,HuffmanCode HC)

初始条件：HT，HC存在。

操作结果：显示字符与其对应的编码。

g(int)

初始条件：HT，HC存在。

操作结果：从根到叶子遍历树，得出译码。