哈夫曼树实验报告(付原C语言程序)

哈夫曼树实验报告 需求分析： 从终端读入一串字符，利用建立好的哈夫曼树对其进行编码，储存到文件当中去，然后从文件读入哈夫曼编码，针对每个字母对其进行译码，翻译为原来的信息。 二、概要设计 程序分为以下几个模块： 1、从终端读入字符集大小，n个字符和 n个权值，建立哈夫曼树，写入文件hfmTree中去。 2、对hfmTree进行编码，建立hfm编码表。 3、从文件ToTran读入信息，根据 hfm编码表对其进行hfm编码，将编码后的信息写入文件Codefile中去 4、对Codefile文件反向译码，结果储存在 Textfile中去。 5、将建立的hfmTree打印在终端上，并储存于相应的Treeprint文件中去。 抽象的数据定义如下： 哈夫曼树结构 typedef struct //定义哈夫曼树的结构 { int weight; //权值 int parent; //双亲 int lchild; //左孩子 int rchild; //右孩子 }htnode,huffmantree[M+1]; 建立哈夫曼树 void crthuffmantree(huffmantree ht,int w[],int n) //初始化哈夫曼树 { int i,s1,s2,m; for(i=1;i<=n;i++) { ht[i].weight=w[i]; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } m=2*n-1; for(i=n+1;i<=m;i++) { ht[i].weight=0; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } for(i=n+1;i<=m;i++) { select(ht,i-1,&s1,&s2); ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i; ht[s2].parent=i; ht[i].lchild=s1; ht[i].rchild=s2; } } typedef char *huffmancode[N+1]; //建立哈夫曼树编码表 void crthuffmancode(huffmantree ht,huffmancode hc,int n) { char *cd; //新建立一个指针 int start,i,c,p; cd=(char*)malloc(n*sizeof(char))；//分配求一个字符的哈夫曼编码的空间 cd[n-1]='\0'; //编码结束符 for(i=1;i<=n;i++) { start=n-1; c=i; p=ht[i].parent; while(p!=0) { --start; if(ht[p].lchild==c) cd[start]='0'; else cd[start]='1'; c=p; p=ht[p].parent; } hc[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(hc[i],&cd[start]); } free(cd); } select(huffmantree ht,int pos,int *s1,int *s2) //取最小和次小权值 { int j,m1,m2; m1=m2=maxint; for(j=1;j<=pos;j++) { if(ht[j].weight