哈弗曼编码与译码.doc

哈弗曼编码与译码.doc哈弗曼编码与译码
一个完整的系统应具有以下功能：
(1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。
(2) E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
(3) D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。
以下为选做：
(4) P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
(5) T：印赫夫曼树（Tree printing）。将已在内存中的赫夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint 中。
测试要求
(1) 已知某系统在通信联络中只可能出现八种字符，,,,,,,,，试设计赫夫曼编码。
(2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THIS PROGRAME 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
实现提示
(1) 编码结果以文本方式存储在文件Codefile中。
(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。
(3) 在程序的一次执行过程中，第一次执行I，D或C命令之后，赫夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
#include <>
#include <>
#include <>
#include <>
typedef struct {
char letter;
float wt;
}hfm,*hfmlist;
//*************************全局变量************************************
unsigned int s1,s2,n;
char choose;
int DEPTH=0;
char a[20];
//***************Huffman树和Huffman编码的存储表示**********************
typedef struct{
unsigned int weight;
unsigned int code;
unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree; //动态分配数组存储Huffman树
typedef char * *HuffmanCode; //动态分配数组存储Huffman编码表
//***************************初始化Huffman树***************************
void select(HuffmanTree HT,int l){
int a,b,c,j;
s1=s2=1;
a=b=1000;
for(j=1;j<=l;j++){
if(HT[j].code==0){
c=HT[j].weight;
if(c<a){b=a;a=c;s2=s1;s1=j;}
else if(c<b){b=c;s2=j;}
}//if
}//for
HT[s1].code=HT[s2].code=1;
}//select
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, hfmlist HL,unsigned int n){
//w存放n个权值（均