哈夫曼编译码Word文档下载推荐.docx

1、本实验拟设其中的数据为abbcccdddd.二、概要设计1.总体设计 一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P：印代码文件（Print）。将文件Cod

2、eFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。（5）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。2.函数划分：该程序有一个主函数和多个子函数，主函数完成对子函数的调用，各子函数实现相应的功能。可以定义相应的抽象数据类型。三、详细设计1.算法void CrtHuffmanTree（HuffmanTree *ht , int *w,ElemTypes *d, int n） /* w存放已知的n个权值，构造哈夫曼树ht *

3、/ int m,i; int s1,s2; m=2*n-1; *ht=（HuffmanTree）malloc（m+1）*sizeof（HTNode）; /*0号单元未使用*/ for（i=1;i=n;i+） /*1-n号放叶子结点，初始化*/ （*ht）i.weight = wi; （*ht）i.data=di; （*ht）i.LChild = 0; （*ht）i.parent = 0; （*ht）i.RChild = 0; for（i=n+1;=m;i+） （*ht）i.weight = 0; /*非叶子结点初始化*/* -初始化完毕！对应算法步骤1-*/i+） /*创建非叶子结点,建哈夫曼

4、树*/ /*在（*ht）1（*ht）i-1的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select（ht,i-1,&s1,&s2）; （*ht）i.data=NULL; （*ht）s1.parent=i; （*ht）s2.parent=i; （*ht）i.LChild=s1; （*ht）i.RChild=s2; （*ht）i.weight=（*ht）s1.weight+（*ht）s2.weight; void Print_d（HuffmanTree *HT,int m,char ch,int n,FILE *fp,FILE *fps） /译码，

5、递归调用 char c; if（!feof（fp） /当文件CodeFile未结束 if（ch=1） if（*HT）（*HT）m.RChild.RChild=0） /当到达叶子节点时 printf（%c,（*HT）（*HT）m.RChild.data）;/输出翻译后的字符 fprintf（fps, int m=2*n-1; c=fgetc（fp）; Print_d（HT,m,c,n,fp,fps）; else /未到达叶子结点时，继续从文件CodeFile读入0 1代码 Print_d（HT,（*HT）m.RChild,c,n,fp,fps）; 0） if（*HT）（*HT）m.LChild.

6、LChild=0） /当到达叶子节点时,（*HT）（*HT）m.LChild.data）; else Print_d（HT,（*HT）m.LChild,c,n,fp,fps）; void PrintTree（HuffmanTree HT,int m,int nLayer） /* 按竖向树状打印的二叉树 */ if（m!=0） if（HT = NULL） return; PrintTree（HT,HTm.RChild,nLayer+1）; for（int i=0;nLayer; printf（-）; printf（%dn,HTm.weight）; PrintTree（HT,HTm.LChild,

7、nLayer+1）;2.主要函数的实现CrtHuffmanTree（&HT,w,d,n）; /构建哈夫曼树。CrtHuffmanCode（&HT,&HC,n,flag）; /对哈夫曼树编码 /对文件编码Print_d（&HT,m,ch,n,fp,fps）; /译码PrintTree（HT,m,nLayer）;/打印四、调试结果 五、课程设计总结1、遇难到哪些问题，解决的方法。一些算法的构成不理解，并且不会自己编写，对哈夫曼译码的算法不会等2、通过本次课程设计，自己得到了哪些方面的训练和提高（经验和教训）。多看书，多上网查资料，多向老师同学请教等，重视基本知识的运用，结合实际等六、附源程序清单#

8、include stdlib.hstring.h#define ElemTypes chartypedef char* HuffmanCode;/*动态分配数组，存储哈夫曼编码*/typedef struct ElemTypes data; unsigned int weight ; /* 用来存放各个结点的权值*/ unsigned int parent, LChild,RChild ; /*指向双亲、孩子结点的指针*/HTNode, * HuffmanTree; /*动态分配数组，存储哈夫曼树*/void select（HuffmanTree *ht,int n, int *s1, int

9、 *s2） int i; int min; i i+） if（*ht）i.parent = 0） min = i; i = n+1; if（*ht）i.weight （*ht）min.weight） min = i; *s1 = min; if（*ht）i.parent = 0 & i!=（*s1） *s2 = min;void CrtHuffmanCode（HuffmanTree *ht, HuffmanCode *hc, int n,int flag）/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/ char *cd; unsigned int c; int start; int

10、 p; hc=（HuffmanCode *）malloc（n+1）*sizeof（char *）; /*分配n个编码的头指针*/ cd=（char * ）malloc（n * sizeof（char ）; /*分配求当前编码的工作空间*/ cdn-1=0; /*从右向左逐位存放编码，首先存放编码结束符*/i+） /*求n个叶子结点对应的哈夫曼编码*/ start=n-1; /*初始化编码起始指针*/ for（c=i,p=（*ht）i.parent; p!=0; c=p,p=（*ht）p.parent） /*从叶子到根结点求编码*/ if（ （*ht）p.LChild = c） cd-start

11、= /*左分支标0*/ else /*右分支标1*/ hci=（char *）malloc（n-start）*sizeof（char）; /*为第i个编码分配空间*/ strcpy（hci,&cdstart）; free（cd）; if（flag=2） FILE *fp1; if（fp1=fopen（e:hfmTree.txt,w）=NULL） /创建文件hfmTree存储字符形式的编码File open error!n exit（0）;n将下面的哈夫曼树写入文件hfmTree.txt中.n fprintf（fp1,字符t权值t编码n for（i=1;i+）%ct%dt%sn,（*ht）i.d

12、ata,（*ht）i.weight,hci）; fprintf（fp1, /写入文件hfmTree中n成功写入! if（fclose（fp1） /关闭文件Can not close the file! if（ flag=1） /当flag=1时对文件ToBeTran编码 FILE *fp; FILE *fps; char ch; int i; if（fp=fopen（ToBeTran.txtr）=NULL） /从文件ToBeTran中读取要编码的文章。 exit（0）; if（fps=fopen（CodeFile.txt）=NULL） /创建文件CodeFile存储文件ToBeTran的编码n

13、对文件ToBeTran.txt的文章进行编码: while（!feof（fp） ch=fgetc（fp）; for（i=1; if（ch!= if（ch=（*ht）i.data） fprintf（fps,%s,hci）; printf（ n代码成功保存到文件CodeFile.txx中.nn if（fclose（fp） /关闭文件 if（fclose（fps） /关闭文件void TreePrint（HuffmanTree *ht,int m） FILE *fp; if（fp=fopen（TreePrint.txt）=NULL） /同时将此字符形式的哈夫曼树写入文件TreePrint中 exit

14、（0）; printf（将字符形式的哈夫曼树存储到文件TreePrint中.n fprintf（fp,编号t字符t权值tparenttLChildtRChildn fprintf（fp,%dt%ct%dt%dt%dt%dn,i,（*ht）i.data,（*ht）i.weight,（*ht）i.parent,（*ht）i.LChild,（*ht）i.RChild）;存储成功! if（fclose（fp） /关闭文件void PutCode（） char ch; int i=0;）=NULL） /读取0 1 代码 输出文件CodeFile.txt中的代码 while（! ch=fgetc（fp）; if（ch!,ch）; i=i+1; if（i%50=0）void main（） HuffmanTree HT; HuffmanCode HC; FILE *fp,*fps,*fpss; int *w; char *d,str1000,s2; char data,ch; int i,n,choice; / 结点个数; int wei; / 权值; int m,flag; int nLayer=0;*n*ttt哈夫曼编译码ttt*n do*tt输入你要选择的选项（请先选择 1）tt *n*ttt1.初始化哈夫曼树tt *n*ttt2.对文件编码ttt *n*ttt3.对译文