哈夫曼编(译)码实验方案.docVIP

哈夫曼编(译)码器实验方案 一、需求分析 1、利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信心传输时间，降低传输成本。但是，这要求在发送器端通过一个编码系统对待传输数据预先编码，在接受端将传来的数据进行译码(复原)。对于双工信道(即可以可以双向传输信息的通道)，每端都需要一个完整的编/译码系统。 2、一个完整的编/译码系统应具有以下功能： (1)、建立哈夫曼树(Createhuffman)。从终端读入字符集大小n，以及n个字符和n个频度，建立哈夫曼树，并将它存于文件input.txt中。 (2)、哈夫曼树编码。利用以建好的哈夫曼树(如果不在内存，则从文件input.txt中读入)，进行编码，然后将结果输出在客户终端显示屏上并存入文件output.txt中。 (3)、编码(Encoding)。在客户终端显示屏上输入字符，然后将其翻译为码流并输出来。 (4)、译码(Decoding)。在客户终端显示屏上输入码流，然后将其翻译为字符并输出来。 3、编码结果以文本方式存储在文件CodeFile中；用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择“Q”为止。 二、概要设计 (1)、抽象数据类型定义如下： ADT Huffman{ 数据对象： D={ ai | 1≤i≤n，n≥0，ai 属ElemType类型} 数据关系： R={ ai，aj| ai，aj∈D，1≤i≤n，1≤j≤n，其中每个元素只有一个前驱， 可以有零个和多个后继，有且只有一个元素没有前驱} 基本运算： Inithuffman(t,n)：初始化哈夫曼树：建立一棵哈夫曼树t。 Createhcode(t, hcd, n)：对建立哈夫曼树进行编码并储存在数组hcd中。 Encoding(t,hcd)：将字符进行编码。 Decoding(t,hcd)：将码流进行译码。 Readhuffman(t)：读取哈夫曼树的数据。 Writehuffman(t)：存储哈夫曼树的数据。 } (2)、主程序 void main（） { 初始化哈夫曼树 ; for( ; ; ) { switch (返回菜单函数代码) { case C: 建立哈夫曼树编码 ; break ; case P: 输出哈夫曼树编码 ; break ; case E: 编码 ; break ; case D: 译码 ; break ; case Q: 退出 ; default : 输入菜单代码有误，请重新输入 ; break ; } } } (2)、模块间调用流程图 菜单代码 C P E D Q 三、详细设计 (1)、头文件定义及预定义 #includestdio.h (2)、定义数据类型 typedef struct /*定义哈夫曼树类型*/ { char data ; /*结点值*/ double weight ; /*频度*/ int parent ; /*双亲点*/ int lchild ; /*左孩子结点*/ int rchild ; /*右孩子*/ }Hufffman ; typedef struct /*定义存放哈夫曼编码类型*/ { char cd [N] ; /*存放当前结点的哈夫曼码*/ int start ; /*cd [start] ~ cd [n]存放哈夫曼码*/ }Hcode ; (3)、函数声明 char menu() ; /*声明菜单函数*/ void Inithuffman(Huffman t[],int n); /*声明初始化哈夫曼树*/ void Createhcode(Huffman t[],Hcode hcd[],int n); /*声明建立哈夫曼树编码*/ void Printhuffman() ; /*输出哈夫曼树编码*/ void Encoding(Huffman t[],Hcode hcd[]) ; /*声明编码函数*/ void Decoding(Huffman t[],Hcode hcd[]) ;