数据结构哈夫曼编码.doc

摘要 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原），将所得结果存储到已开辟空间中。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。本程序可以对任何大小的字符型文件进行Huffman编码，生成一个编码文件。并可以在程序运行结束后的任意时间对它解码还原生成字符文件。对一条电文进行输入，并实现Huffman编码对Huffman编码生成的代码串进行译码输出电文数字Abstract Use hoffmann code was communication can improve the utilization rate of channel, shorten the information transmission time, reduce the transmission cost. This requirement in the sending end through a coding system in advance to transmit data coding, in the receiver will spread of the data decoding (restoration), will the results of open space to store already. Try for such information sending and receiving station write a hoffmann yards of make up/decoding system. This program can on any of the size of the file type character Huffman coding, generates a code files. And can the running of the application at any time after the end of the reduction of decoding it generated character files. Namely: first to a message for input, and realize the Huffman coding, and then to Huffman coding generated code string decode, finally digital output message 关键字 哈夫曼编码； 哈夫曼译码 Keywords Hoffmann code; Hoffmann decode 1 设计要求 对输入的一串电文字符实现哈夫曼编码，输出电文字符串。通常我们把数据压缩的过程称为编码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi恰好为二叉树上带权路径长度。因此 ，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成；(3) 对编码文件的译码。 系统结构图 （功能模块图） 图2-1 哈夫曼结构图 3 详细设计 3.1 哈夫曼树的建立 3.1.1哈夫曼树的存储结构描述为： #define N 50 // 叶子结点数 #define M 2*N-1 // 哈夫曼树中结点总数 typedef struct { int weight; // 叶子结点的权值 int lchild, rchild, parent; // 左右孩子及双亲指针 }HTNode; // 树中结点类型 typedef HTNode HuffmanTree[M+1]; 3.1.2哈夫曼树的算法: void CreateHT(HTNode ht[],int n) //调用输入的数组ht[]和节点数n { int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i++) ht[i].parent=ht[i].lchild=ht[i].rchild=-1; //所有结点的相关域置初值-1 for (i=n;i2*