哈夫曼编码教程.docVIP

哈夫曼编码译码系统 需求分析 程序的基本功能： 构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n个字符以及n个对应的权值，建立哈夫曼树；利用已将建好的哈弗曼树求每个叶结点的哈夫曼编码，并保存。 编码：利用已构造的哈弗曼编码对“明文”文件中的正文进行编码，然后将结果存入“密文”文件中。 译码：将“密文”文件中的0、1代码序列进行译码。 打印“密文”文件：将文件以紧凑格式显示在终端上，同时，将此字符形式的编码保存。 打印哈夫曼树:将已在内存中的哈夫曼以凹入表形式显示在终端上。 输入输出要求： 从键盘接收字符集大小n、以及n个字符和n个权值； 构造哈夫曼树：将HFMTree数组中的各个位置的各个域都添上相关的值，并将结构体数组存入文件HTree.txt中。 打印哈夫曼树：从HFMTree数组读取相关的结点信息，以凹入表方式将各个结点画出来； 构造哈夫曼编码：先从文件HTree.txt中读入相关的字符信息进行哈夫曼编码，将字符与其对应的编码存入文件HNode.txt中； 编码：利用已构造的哈夫曼树对文件进行编码，打印结果，并将结果存入新建文件中； 译码：将密文文件中的内容利用HNode.txt中建立的编码规则进行翻译，打印结果，并将结果存入新建文件中。 测试数据： 输入叶子结点个数为4，权值集合为{1,3,5,7}，字符集合为{A,B,C,D}，且字符集与权值集合一一对应。 概要设计 抽象数据类型的定义： 采用静态链表作为哈夫曼树的存储结构； 求哈夫曼编码时使用一维数组HCode作为哈夫曼编码信息的存储。 主模块的流程及各子模块的主要功能： ①int main() { 主菜单； swich语句结构选择； return 0; } ②in_park() { 输入车牌号； 若停车场已满，停入便道中，否则停入停车场； } ③output() { 输入所要离开车辆的车牌号，以及离开时间； 停在便道内的第一辆车进入停车场； } show_car() { 依次显示停车场内的车辆信息； } show_queue() { 依次显示便道内的车辆信息； } 模块之间的层次关系： 详细设计 定义的相关数据类型： ① 哈夫曼树结点： typedef struct { int weight; int park; int lchild; int rchild; char ch; } ② 哈弗曼编码结点： typedef struct { Car Park[MAX_PARK]; int top; }ParkStack; 函数的调用关系： 调试分析 调试中遇到的问题及对问题的解决方法： ⑴遇到的问题： 编码时最后一位总是多出一位数字； 编码时出现无限循环； ⑵解决方法： 改变构造哈夫曼树时的循环条件； 改变构造哈夫曼编码的循环条件； 使用说明及测试结果 使用说明： 进入主菜单，选择所要进行的操作； 构造哈夫曼树：输入叶结点个数，及其字符与权值； 选择显示哈夫曼树，哈夫曼树以凹入表形式显示； 选择构造哈夫曼编码，即构造哈夫曼编码，若成功，则显示成功； 选择编码：选择进行键盘输入或者从文件中获取。 测试结果： 停车场容量为5，连续有7辆车到来，牌照号分别为f001、f002、f003、f004、f005、f006、f007，前5辆车进入停车场1-5号车位，第6、7辆车停入便道的1、2号位置上。牌照号为f003的车辆从停车场开走后，f006从便道进入停车场，便道上只剩f007。 伪码算法 #includeconio.h #includestdio.h #includestring.h #includeiostream.h #includefstream.h #include iomanip.h? #include stdlib.h #define N ?4 #define MAXVSLUE 1000 typedef struct { ?char letter; ?int weight; ?int parent; ?int lchild; ?int rchild; }HNodeType; HNodeType HNode[2*N-1]; #define MAXBIT 10 typedef struct { ?char bit[MAXBIT]; ?int start; }HCodeType; HCodeType HCode[N]; void Creat_HuffMtree(HNodeType HFMTree[],int n) ?; ????/* 构造哈夫曼 树*/ void HaffmanConde(HNodeType HFMTree[], ?HCodeType