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