实验四哈夫曼树与哈夫曼编码.doc

文档介绍：实验四 哈夫曼树与哈夫曼编码
一、实验内容
[问题描述]
　　n个字符在原文中出现的频率，求它们的哈夫曼编码。
[根本要求]
1. 初始化：从键盘读入n个字符，以与它们的权值，建立Huffman
树。〔〕2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。
对给定的待编码字符序列进展编码。
二、概要设计算法设计：
要是实现哈夫曼树的操作，首先创建一个哈夫曼树，在创建哈夫曼树的时候，对哈夫曼树的叶子和非叶子结点进展初始化，而在建立哈夫曼树时，最难的该是选择权值最小的两个顶点，然后两个结点的权值和作为新的权值，再选择两个权值最小的作为新的两个结点创建一个小的二叉树的子树；创建哈夫曼树后，进展编码，在编码过程中，先找到根，然后遍历，左孩子用0标记，右孩子用1标记，最后将编码好的哈夫曼树进展输出，就可以知道哈夫曼树的编码了。
流程图：
开始
输入哈弗曼树的带权结点数目 n
输入相应的权值和对应的字符
建立哈夫曼树Huffmantree(HT,w,n,e)
显示哈夫曼树outputHuffman(HT,m)
哈夫曼树的编码
CHuffmancode(HT,HC,n)
完毕
算法：
主函数
Huffmantree(HuffmanTree &HT,int*w,int n,char *e)*hc, int n)
CHuffmancode(HuffmanTree &HT,HuffmanCode &HC,int n)
outputHuffman(HuffmanTree HT, int m)
select(HuffmanTree *ht,int n, int *s1, int *s2)
模块：
在分析了实验要求和算法分析之后，将程序分为四个功能函数，分别如下：
首先建立一个哈夫曼树和哈夫曼编码的存储表示：
typedef struct {
int weight;
int parent,lchild,rchild;
char elem;
}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树
typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表CrtHuffmanTree(HuffmanTree *ht , int *w, int n)：w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。
构造哈夫曼树：
开始
叶子初始化
非叶子初始化
调用select函数选择权值最小的两个
这两个权值最小的两个字符非别作为同一个结点的左右孩子，其父母的权值为两个字符的权值之和
完毕
for(i=n+1;i<=m;++i)
{//在HT[1……i]选择parent为0且weight最小的两个
Select(HT,i-1,&s1,&s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT
[Select(HuffmanTr