资源描述：
《哈夫曼编码解码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Huffman编/解码一．问题描述1.题目内容：利用Huffman编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据进行预先编码，在接收端进行解码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/解码系统。2.基本要求：一个完整的系统应该具有以下功能：1.I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立Huffman树，并将它存入hfmTree中。2.E：编码（Encoding）。利用已经建好的Huffman树（如果不在内存，则应从文件hfmTre
2、e中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。3.D：解码（Decoding）。利用已经建立好的Huffman树将文件CodeFile中的代码进行解码，结果存入TextFile中。4.P：打印代码文件（Print）。将文件CodeFile以紧凑的格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。5.T：打印Huffman树（TreePrinting）。将已经在内存中的Huffman树以直观的形式（凹入的形式）显示在终端上，同时将此字符形式的Huffman树写入文件TreePrint中。3.测试数
3、据：用下表给出的字符集和频度的实际统计数据建立Huffman树，并对以下报文进行编码和译码：“THISPROGRAMISMYFAVORITE”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161二．需求分析1.编码结果以文本的方式存储在文件CodeFile中。2.用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出（quit）。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了Q为止。3.在程序的一次执行过程中，第一次
4、执行I，D，C命令后，Huffman树已经存在在内存中了，不必再读入。每次执行中不一定执行了I命令，因为文件hfmTree可能已经早已建好。4.测试数据的权值（频度）应为正整数。三．概要设计为实现上述程序功能，需要顺序栈一个抽象数据类型。1．栈的抽象数据类型定义为：ADTStack{数据对象：D={ai
5、ai∈CharSet,i=1,2..,n}数据关系:R1={
6、ai-1,ai∈D,i=2,...,n}基本操作:InitStack（&S）操作结果：构建一个空栈S。DestroyStack(&S)操作结果：销毁栈S。参数说明：栈S已存在。ClearStack(
7、&S)操作结果:将栈清空。参数说明：栈S已存在。StackEmpty（S）操作结果:若栈为空则返回TURE；否则返回FALSE。参数说明：栈S已存在。StackLength（S）操作结果:返回栈中的元素个数，亦即栈的长度。参数说明：栈S已存在。GetTop(S,&e)操作结果:将e赋值为栈S的栈顶元素。参数说明：栈S已存在且非空。Push(&S,e)操作结果:将e插入为栈S的新的栈顶元素。参数说明：栈S已存在。Pop(&S,&e)操作结果:若栈非空，删除栈S的栈顶元素，并将值赋给e。参数说明：栈S已存在。StackTraverse(S)操作结果:从栈低到栈顶依次输出S的各个元素
8、。参数说明：栈S已存在。}2．程序包含三个模块：1）主函数模块2）初始化模块（包括了选择子模块）3）编码模块4）解码模块5）打印代码文件模块6）打印Huffman树模块（包括了打印子模块）各模块之间调用关系如图所示：主函数模块编码模块解码模块打印代码模块打印树模块初始化模块四．详细设计1．元素类型、结点类型和指针类型。typedefchar**Huffmancode;／／哈夫曼编码的类型typedefchar*Huffmanco;／／哈夫曼编码数组元素的类型typedefstructSqStack_type{char*elem;intstacksize;inttop;}SqSt
9、ack;typedefstruct{char*elem;int*value;}SqNode,*SqNodelist;typedefstructHTNode_type{／／哈夫曼树结点类型intweight;intparent,lChild,rChild;}HTNode,*HuffTree;２.主函数的伪码算法如下：voidmain(){chara;intn=0,num=0;intflag=0;intmsize=STACK_INIT_SIZE;／／num记录TOBETRAN中字母个数，flag
