数据结构_哈夫曼编码器.doc

题目：编制一个哈夫曼编码器。 需求分析 用户以文件（ data.dat）的形式输入字符的权值和要编译的信息：先是要编译的信息，以句号结束。接着在是字符个数。最后是按字符、字符的权值的顺序写入字符信息。 结果以文件（printf.dat）形式呈现。 测试数据为： THIS PROGRAM IS MY FAVORITE.27 186A64B13C22D32E103F21G15H47I57J1K5L32M20N57O63P15Q1R48S51T80U23V8W18X1Y16Z1 程序执行的命令： 读取编码和要编码的信息 创建哈夫曼编码树 进行编码 将结果输入文件中 概要设计 设定树的抽象数据类型定义： ADT Tree{ 数据对象D：D是具体的相同特性的数据元素的集合。 数据关系R:若D为空集，则称为空集； 若D仅含一个数据元素，则R为空集，否则R={H},H是如下二元关系： 在D中存在唯一的称为数据元素ROOT，它在关系下无前驱； 若D-{ROOT}不等于Φ，则存在D-{ROOT}的一个划分D1，D2，…Dm(m0)。对任意J不等于K(1=J.K=M)有Dj∩Dk=Φ,且对任意i（1=i=m）,唯一存在数据元素Xi∈Di,有 ROOT，Xi∈H。 对于D-{ROOT}的划分，H-{ROOT,X1,…,ROOT,Xm}有唯一的一个划分H1，H2，…，Hm(m0),对于任意J不等于K(1=j,k=m)有Hj∩Hk=Φ,且对任意i(1=i=m),Hi是Di上的二元关系，（D，{Hi}）是一棵符合本定义的树，成为根ROOT的子树。 基本操作： void HuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,Char_weiht *zifu,int zinum) 操作结果：创建哈夫曼树。 void Select(HuffmanTree HT,int num,int s1,int s2) 初始条件：哈夫曼树存在。 操作结果：返回权值最小且父节点为0的节点。 void Do_Huffman(char*string,Char_weight *zifu,HuffmanCode HC) 初始条件：哈夫曼树存在。 操作结果：将编码存入文件中。 } 本程序包含三个模块 主程序模块 树模块 详细设计 #includestdio.h #includestdlib.h #includestring.h #define MAXCHAR 30 #define MAXSTRING 100 typedef struct { char a; int weight; }Char_weight; typedef struct{ int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char **HuffmanCode; void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,Char_weight *zifu,int zinum); void Select(HuffmanTree HT,int num,int s1,int s2); void Do_Huffman(char *string,Char_weight *zifu,HuffmanCode HC); int zinum; int main() { HuffmanTree HT; HuffmanCode HC; int i; FILE *fp; Char_weight zifu[MAXCHAR]; char string[MAXSTRING]={0},temp; if(NULL==(fp=fopen(data.dat,r))) { printf(open file data wrong\n); exit(1); } fscanf(fp,%c,temp); for(i=0;.!=temp;i++) { string[i]=temp; fscanf(fp,%c,temp); } string[i]=\0; fscanf(fp,%d,zinum); for(i=0;izinum;i++) { fscanf(fp,%c,(zifu[i].a)); fscanf(fp,%d\n,(zifu[i].weight)); } if(EOF==fclose(fp)) { printf(close file data wrong\n); exit(1); } HuffmanCoding(HT,HC,zifu,zinum); Do_Huffman(string,z