哈夫曼编译码器课程设计报告

1、XXX学院本科数据结构课程设计总结报告设计题目 ：实验学生姓名 ：XXX系别：XXX专业：XXX班级：XXX学号：XXX指导教师 ： XXX XXX、哈夫曼编 / 译码器2012年6月21日XXX学院课程设计任务书题目专业、班级 XXX学号 XXX 姓名 XXX主要内容、基本要求、主要参考资料等：1. 主要内容利用哈夫曼编码进行信息通信可大大提高信道利用率， 缩短信息传输时间，降低 传输成本。要求在发送端通过一个编码系统对待传数据预先编码； 在接收端将传 来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道），每端 都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编

2、/译码 系统。2. 基本要求系统应具有以下功能：（1） C:编码（Coding）。对文件tobetrans中的正文进行编码，然后将结果存 入文件codefile 中，将以此建好的哈夫曼树存入文件 HuffmanTree中（2） D：解码（Decoding ）。利用已建好的哈夫曼树将文件 codefile 中的代码进 行译码，结果存入textfile 中。（3） P:打印代码文件（Print ）。将文件codefile 以紧凑格式显示在终端上， 每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。（4）T：打印哈夫曼树（Tree Printing ）。将已在内存中的哈夫曼树以

3、直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 treepri nt中。3. 参考资料：数据结构（C语言版）严蔚敏、吴伟民编著；数据结构标准教程胡超、闫宝玉编著完成期限：2012年6月21日指导教师签名：课程负责人签名：2012 年 6 月 21 日一、设计题目（任选其一）实验一、哈夫曼编/译码器二、实验目的1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；2深化对算法课程中基本概念、理论和方法的理解；3巩固构造赫夫曼树的算法；4设计试验用程序实验赫夫曼树的构造。三、运行环境（软、硬件环境）Windows xp sp3，Visual C+ 6.0 英

4、文版四、算法设计的思想（1） 初始化赫夫曼树，输入文件tobetra ns.txt中各字符及其权值，并保存于 hfmtree.txt 文件中（2） 编码（Coding ）。对文件tobetrans中的正文进行编码，然后将结果存入文 件 codefile 中（3） D：解码（Decoding ）。利用已建好的哈夫曼树将文件 codefile 中的代码进 行译码，结果存入textfile 中。（4） P:打印代码文件（Print ）。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。（5）T：打印哈夫曼树（Tree Printin

5、g ）。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件treepri nt中。五、流程图赫夫曼编/译码器六、算法设计分析1. 赫夫曼树节点的数据类型定义为：typedef struct /赫夫曼树的结构体char ch;int weight;/权值int pare nt,lchild,rchild; HTNode,*HuffmanTree;2. void HuffmanCoding(HuffmanTree &,char *,int *,int);建立赫夫曼树的算法，此函数块调用了 Select ()函数。void select(HuffmanTree HT,

6、int j,int *x,i nt *y); 从已建好的赫夫曼树中选择 pare nt为0, weight最小的两个结点。3 利用已建好的哈夫曼树从文件hfmtree.txt中读入，对文件中的正文进行编码，然后将结果存入文件codefile.txt 中。4. cod ing编码功能：对输入字符进行编码5. Decod ing译码功能：利用已建好的哈夫曼树将文件 codefile.txt中的代码进行译码，结果存入文件textfile.txt 中。6. Print()打印功能函数：输出哈夫曼树以及对应的编码七、源代码/#include #include #include / 定义赫夫曼树结点的结构

7、体 typedef structchar ch; / 增加一个域，存放该节点的字符 int weight;int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char *HuffmanCode; /指向赫夫曼编码的指针void tips(); / 打印操作选择界面建立赫夫从已建好的void HuffmanCoding(HuffmanTree &,char *,int *,int); / 曼树的算法void select(HuffmanTree HT,int j,int *x,int *y); / 赫夫曼树中选择 parent 为 0，w

8、eight 最小的两个结点void Init();void Coding(); / void Decoding(); / void Print_code(); / void Print_tree(); /编码译码打印译码好的代码 打印哈夫曼树int Read_tree(HuffmanTree &); / 从文件中读入赫夫曼树 void find(HuffmanTree &HT,char *code,char *text,int i,int m); / 译码时根据 01 字符串寻找相应叶子节点的递归算法 void Convert_tree(unsigned char T100100,int s,

9、int *i,int j); / 将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; / 全局变量int n=0; / 全局变量，存放赫夫曼树叶子结点的数目int main()char select;while(1)tips();scanf(%c,&select);switch(select) / 选择操作，根据不同的序号选择不同的操作 case 1:Init();break;case 2:Coding();break;case 3:Decoding();break;case 4:Print_code();break;case 5:Print_tree();break;

10、case 0:exit(1);default :printf(Input error!n);getchar();return 0;void tips() / 操作选择界面printf( n);printf( -请选择操作-n);printf( n);printf(n);printf( 1初始化赫夫曼树 -n)printf( 2编码 n);printf( 3译码 n);printf( 4打印代码文件 -n);printf( 5打印赫夫曼树 -n);printf( 0退出 n);printf( n);/ 初始化函数，输入 n 个字符及其对应的权值，根据权值建立哈夫曼树，并 将其存于文件 hfmtr

11、ee 中void Init()FILE *fp;int i,n,w52; / 数组存放字符的权值 char character52; /存放 n 个字符printf(n 输入字符个数 n:);scanf(%d,&n);/输入字符集大小printf(”输入(个字符及其对应的权值：n,n);for (i=0;in;i+)char b=getchar();scanf(%c,&characteri);scanf(%d,&wi);/输入 n 个字符和对应的权值HuffmanCoding(HT,character,w,n); /建立赫夫曼树if(fp=fopen(hfmtree.txt,w)=NULL)p

12、rintf(Open file hfmtree.txt error!n);for (i=1;i=2*n-1;i+)if(fwrite(&HTi,sizeof(HTNode),1,fp)!=1) /将建立的赫夫曼树存入文件 hfmtree.txt 中printf(File write error!n);prin tf(n赫夫曼树建立成功，并已存于文件 hfmtree.txt 中n);fclose(fp);/ 建立赫夫曼树的算法void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)int m,i,x,y;HuffmanTre

13、e p;if(n=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;ich=*character;p-weight=*w;p-parent=0;p-lchild=0;p-rchild=0 ;for(;ich=0;p-weight=0;p-parent=0;p-lchild=0;p-rchild=0; for(i=n+1;i=m;+i)select(HT,i-1,&x,&y);HTx.parent=i;HTy.parent=i;HTi.lchild=x;HTi.rchild=y;HTi.wei

14、ght=HTx.weight+HTy.weight;/ 从 HT1 到 HTj 中选择 parent 为 0，weight 最小的两个结点，用 返回其序号void select(HuffmanTree HT,int j,int *x,int *y)int i;/ 查找 weight 最小的结点for (i=1;i=j;i+)if (HTi.parent=0)*x=i;break;for (;i=j;i+)if (HTi.parent=0)&(HTi.weightHT*x.weight)*x=i;HT*x.parent=1;/ 查找 weight 次小的结点for (i=1;i=j;i+)if

15、(HTi.parent=0)*y=i;break;for (;i=j;i+)if (HTi.parent=0)&(i!=*x)&(HTi.weightHT*y.weight) *y=i;codefile 中/ 对文件 tobetrans 中的正文进行编码，然后将结果存入文件 void Coding()FILE *fp,*fw;int i,f,c,start;char *cd; HuffmanCode HC;if(n=0)n=Read_tree(HT);/ 从文件 hfmtree.txt 中读入赫夫曼树 , 返回叶子结点 数/求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中HC=

16、(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char *)malloc(n*sizeof(char);cdn-1=0; for(i=1;i=n;+i)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char *)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart);free(cd);if(fp=fopen(tobetrans.txt,rb)=NULL)

17、printf(Open file tobetrans.txt error!n);if(fw=fopen(codefile.txt,wb+)=NULL)printf(Open file codefile.txt error!n);char temp;fscanf(fp,%c,&temp); / 从文件读入第一个字符 while(!feof(fp)for(i=1;i=n;i+) if(HTi.ch=temp) break; / for(int r=0;HCir!=0;r+) / fputc(HCir,fw); fscanf(fp,%c,&temp); /在赫夫曼树中查找字符所在的位置将字符对应的编

18、码存入文件从文件读入下一个字符 fclose(fw); fclose(fp); printf(n 已将文件 hfmtree.txt 成功编码 , 并已存入 codefile.txt 中！ nn);/ 将文件 codefile 中的代码进行译码，结果存入文件 textfile 中void Decoding()FILE *fp,*fw;int m,i;char *code,*text,*p;if(n=0)n=Read_tree(HT);/ 从文件 hfmtree.txt 中读入赫夫曼树 , 返回叶子结点 数if(fp=fopen(codefile.txt,rb)=NULL)printf(Open

19、file codefile.txt error!n);if(fw=fopen(textfile.txt,wb+)=NULL)printf(Open file textfile.txt error!n);code=(char *)malloc(sizeof(char);fscanf(fp,%c,code); / 从文件读入一个字符 for(i=1;!feof(fp);i+)code=(char *)realloc(code,(i+1)*sizeof(char); / 增加空间 fscanf(fp,%c,&codei); / 从文件读入下一个字符codei-1=0;/ codefile.txt文件

20、中的字符已全部读入，存放在 code 数组中text=(char *)malloc(100*sizeof(char);p=text;m=2*n-1;if(*code=0)find(HT,code,text,HTm.lchild,m); /从根节点的左子树去找elsefind(HT,code,text,HTm.rchild,m); /从根节点的右子树去找for(i=0;pi!=0;i+) / 把 译 码 好 的 字 符 存 入 文 件 textfile.txt 中fputc(pi,fw);fclose(fp);fclose(fw);printf(n 已将 codefile.txt 文件成功译码，

21、 兵已存入 textfile.txt 文件！ nn);/ 将文件 codefi1e 以紧凑格式显示在终端上 , 每行 50 个代码。同时将此字符 形式的编码文件写入文件 codeprint 中。void Print_code()FILE *fp,*fw;char temp;int i;if(fp=fopen(codefile.txt,rb)=NULL)printf(Open file codefile.txt error!n); if(fw=fopen(codeprint.txt,wb+)=NULL)printf(Open file codeprint.txt error!n);printf(

22、n 文件 codefi1e 显示如下 :n);fscanf(fp,%c,&temp); / 从文件读入一个字符for (i=1;!feof(fp);i+)printf(%c,temp);if(i%50=0) printf(n);fputc(temp,fw); / 将该字符存入文件 codeprint.txt 中 fscanf(fp,%c,&temp); / 从文件读入一个字符printf(nn 已将此字符形式的编码写入文件 codeprint.txt 中！ nn);fclose(fp);fclose(fw);/ 将已在内存中的哈夫曼树显示在屏幕上，并将此字符形式的哈夫曼树写入 文件 treep

23、rint 中。void Print_tree()unsigned char T100100;int i,j,m=0;FILE *fp;if(n=0)n=Read_tree(HT); / 从文件 hfmtree.txt 中读入赫夫曼树 , 返回叶子结 点数将内存中的赫夫曼树转换成凹凸表形式Convert_tree(T,0,&m,2*n-1); / 的树，存于数组 T 中if(fp=fopen(treeprint.txt,wb+)=NULL) printf(Open file treeprint.txt error!n); printf(n 打印已建好的赫夫曼树： n);for(i=1;i=2*n

24、-1;i+)for (j=0;Tij!=0;j+)if(Tij= ) printf( );fputc(Tij,fp);else printf(%d,Tij);fprintf(fp,%dn,Tij); printf(n);fclose(fp);printf(n已将该字符形式的哈夫曼树写入文件treeprint.txt中！ nn);/ 从文件 hfmtree.txt 中读入赫夫曼树，返回叶子节点数int Read_tree(HuffmanTree &HT)FILE *fp;int i,n;HT=(HuffmanTree)malloc(sizeof(HTNode); if(fp=fopen(hfmt

25、ree.txt,r)=NULL) printf(Open file hfmtree.txt error!n);for (i=1;!feof(fp);i+)HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode); /增加空间fread(&HTi,sizeof(HTNode),1,fp); /读入一个节点信息fclose(fp); n=(i-1)/2; return n;/ 译码时根据 01 字符串寻找相应叶子节点的递归算法 void find(HuffmanTree &HT,char *code,char *text,int i,int m) if(*co

26、de!=0)/若译码未结束若找到叶子节点code+;if(HTi.lchild=0&HTi.rchild=0) /*text=HTi.ch; /将叶子节点的字符存入 text 中从根节点的左子树找从根节点的右子树找从该节点的左子树去找从该节点的右子树去找text+;if(*code=0)find(HT,code,text,HTm.lchild,m); / elsefind(HT,code,text,HTm.rchild,m); /else / 如果不是叶子节点 if(*code=0) find(HT,code,text,HTi.lchild,m); / else find(HT,code,te

27、xt,HTi.rchild,m); /else*text=0; / 译码结束/ 将文件中的赫夫曼树转换成凹凸表形式的赫夫曼树打印出来 void Convert_tree(unsigned char T100100,int s,int *i,int j)int k,l;l=+(*i);for(k=0;kDREB匚codefile -记事本 X交件 遍辑疋）韬式 直看理）耕助11 91 0011111106110000111 01 011 01111111 01 DQS10f teztfile -记事本-口伙立件1编辑 格式盘）查看迫 帮助堪）ABCDEflECBBADDREBF treeprin

28、t -记李本匚丁口J区J丈件（E）編辑 格式 査看匹）肅朗孤）161 6131311121 10141613131图（6）九、收获及体会课程设计是让我们充分利用我们专业课程所学知识的机会，也是我们迈向社会，从事工作前一个必不少的过程。通过这次课程设计，我深深体会到将知识运用到实践中的重要作用。我这两天的课程设计，是让我学会脚踏实地迈开这一步， 也是为明天能稳健地在社会大潮中奔跑打下坚实的基础。我的课程设计题目是赫夫曼编译码器。最初做这个程序的时候，让我觉得完成这次程序设计真的是太难了，然后我查阅了课本，并去图书馆借了资料，在写这个程序的时候也参考了网上的设计流程，写完刚运行时出现了很多问题。尤

29、其是编码错误，导致内存无法read，通过同组人员的交流请教，逐渐明白过来，然后经过不知道多少次修改才顺利运行。本次试验也让我明白了理论与实际相结 合的重要性，并提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能以及合作能力。通过对各个步骤各个流程的控制，逐渐让我产生了兴趣，在实际编写过程中，和同学们相互讨论让我学到的不仅仅是一些解 决问题的方法，更是解决问题的思想。课程设计本身也是一种相互学习的过程 J/Illllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll#i nclude #inclu

30、de ll 为 exit()提供原型#in eludell哈夫曼树结点的结构typedef struct char ch;ll该字符域用于存放节点的关键字int weight;int pare nt, lchild, rchild; HTNode * HuffmanTree;ll动态分配数组存储哈夫曼树typedef char * HuffmanCode;ll动态分配数组存储哈夫曼编码表void Menu();/ 显示菜单void HuffmanCoding( HuffmanTree &HT, char Character,int * w, int n); ll 建立哈夫曼树void sele

31、ct( Huffma nTree HT, i nt j, int *x, int *y);ll 从已建好的赫夫曼树中选择 pare nt为0, weight最小的两个结点void Init();void Coding();ll 编码void Decoding(); ll 译码void Print_code();ll打印译码好的代码void Print_tree();ll 打印哈夫曼树int Read_tree( HuffmanTree &); ll从文件中读入赫夫曼树void find( HuffmanTree &HT, char *code, char *text, int i, int m

32、); ll 译码时根据 01 字符 串寻找相应叶子节点的递归算法void Convert_tree( unsigned char T100100, int s, int *i, int j); ll 将内存中的赫夫曼 树转换成凹凸表形式的赫夫曼树HuffmanTree HT; ll 全局变量int n = 0; ll全局变量，存放赫夫曼树叶子结点的数目int main()char select;while (1)Me nu();scanf( %c, &select);switch (select) ll选择操作，根据不同的序号选择不同的操作case 1 :lnit();break;case 2

33、 :Coding(); break;case 3 :Decod in g(); break;case 4 :Print_code(); break;case 5 :Print_tree();break;case 0 :exit(1);default :printf(Input error!n );getchar();return 0;void Menu()/操作选择界面pri ntf(n)；pri ntf(-请选择操作-n)；pri ntf(n)；printf(n)；pri ntf(1初始化赫夫曼树-n)；pri ntf(2编码-n)；pri ntf(3译码-n)；pri ntf(4打印代码文

34、件-n)；pri ntf(5打印赫夫曼树-n)；pri ntf(0退岀-n)；pri ntf(n)；hfmtree 中/初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件 void Init()|FILE *fp;int i, n, w52;/数组存放字符的权值char character52;/ 存放 n 个字符printf( n输入字符个数n:“)；seanf( %d, &n);/输入字符集大小printf(输入介字符及其对应的权值:n , n);for (i = 0; in; i+)char b = getchar();seanf( %c, &character

35、i);scanf( %d, &wi);/输入n个字符和对应的权值HuffmanCoding(HT, character, w, n);/ 建立赫夫曼树if (fp = fopen( hfmtree.txt , w) = NULLprintf( Ope n file hfmtree.txt error!n);for (i = 1; i 0),构造哈夫曼树HTint m, i, x, y;Huffma nTree p;if (n = 1) return ;m = 2 * n - 1;HT = ( HuffmanTree)malloc(m + 1) * sizeof (HTNode);for (p

36、= HT + 1, i = 1; i ch = *character; p-weight = *w; p-pare nt = 0; p-lchild = 0; p-rchild = 0;for (; i ch = 0; p-weight = 0; p-parent = 0; p-lchild = 0; p-rchild =0; for (i = n + 1; i = m; +i)select(HT, i - 1, &x, &y);HTx.pare nt = i; HTy.pare nt = i;HTi.lchild = x; HTi.rchild = y;HTi.weight = HTx.we

37、ight + HTy.weight;/从HT1到HTj中选择pare nt为0, weight最小的两个结点，用x和y返回其序号 void select( HuffmanTree HT int j, int if ( HTi.parent = 0)*y = i; break ;for (; i = j; i+)if ( HTi.parent = 0) & (i != *x) & ( HTi.weightHT* y.weight) fclose(fp);n = (i - 1) / 2;return n;/译码时根据01字符串寻找相应叶子节点的递归算法void find( HuffmanTree

38、&HT, char *code, char *text, int i, int m)if (*code !=0 )/若译码未结束code+;if (HTi.lchild = 0 & HTi.rchild = 0)/ 若找到叶子节点 x, int * y)int i;/查找weight最小的结点for (i = 1; i = j ; i+)if ( HTi.parent = 0)*x = i; break ;for (; i = j; i+)if ( HTi.parent = 0) & ( HTi.weight HT* x.weight)*x = i;HT* x.parent = 1;/查找we

39、ight次小的结点for (i = 1; i = j ; i+)HC = ( HuffmanCode)malloc(n + 1) * sizeof (char*);cd = ( char *)malloc(n *sizeof (char);cdn - 1 =0;for (i = 1; i = n; +i)start = n -1;for (c = i, f = HTi.parent; f != 0; c = f, f = HTf.parent)if (HTf.lchild = c)cd-start =O;else cd-start =1;HCi = ( char *)malloc(n - st

40、art) *sizeof (char);strcpy(HCi, & cdstart);free(cd);if (fp = fopen(tobetrans.txt, rb ) = NULLprintf( Ope n file tobetra ns.txt error! n);if (fw = fopen( codefile.txt , wb+) = NULLchar *code, *text, *p;if (n = 0)n = Read_tree(HT); /从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数if (fp = fopen(codefile.txt,rb)=NULI)pri

41、ntf(Ope n file codefile.txt error!nif (fw = fopen( textfile.txt, wb+)=);NULLprintf( Open file textfile.txt error! n);code = ( char *)malloc( sizeof (char);fscanf(fp,%c, code);/从文件读入一个字符for (i = 1; !feof(fp); i+)code = ( char *)realloc(code, (i + 1) *sizeof (char); / 增加空间fscanf(fp,%c, &codei);/ 从文件读入

42、下一个字符codei - 1 =0;/ codefile.txt文件中的字符已全部读入，存放在 code数组中text = ( char *)malloc(100 * sizeof (char);p = text;m = 2 * n - 1;printf( Ope n file codefile.txt error! n)if (fw = fopen( codeprint.txt , wb+) = NULLprintf( Ope n file codepri nt.txt error! n);printf( n 文件 codefile 显示如下:n);fscanf(fp,%c, &temp);

43、/ 从文件读入一个字符for (i = 1; !feof(fp); i+)printf( %c, temp);if (i % 50 = 0) printf(n);fputc(temp, fw);/ 将该字符存入文件 codeprint.txt中fscanf(fp,%c, &temp);/ 从文件读入一个字符printf( nn已将此字符形式的编码写入文件codeprint.txt 中！ nn);fclose(fp);printf( %d, Tij); fprintf(fp,%dn, Tij);printf( n);fclose(fp);printf( n已将该字符形式的哈夫曼树写入文件tree

44、print.txt中！ nn);/从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数int Read_tree( HuffmanTree &HT) 一FILE Tlk=;Tlk = HT j .weight;if (HT j .lchild)Convert_tree( T, s + 1, i , HT j .lchild);if (HT j .rchild)Convert_tree( T, s + 1, i , HT j .rchild);Tl+k =0;fp;int i, n;HT = ( HuffmanTree)malloc( sizeof (HTNode);if (fp = fo

45、pen( hfmtree.txt , r ) = NULLprintf( Ope n file hfmtree.txt error!n);for (i = 1; !feof(fp); i+)HT = ( HuffmanTree)realloc(HT, (i + 1) *sizeof (HTNode)； 增加空间fread(&HTi, sizeof (HTNode, 1, fp)； 读入一个节点信息/从根节点的右子树找/从该节点的左子树去找/从该节点的右子树去找i, int j)find(HT, code, text, HTm.rchild, m); else /如果不是叶子节点if (*code =O)fin d(HT, code, text, HTi.lchild, m); elsefin d(HT, code, text, HTi.rchild, m);else*text =0 ; / 译码结束/将文件中的赫夫曼树转换成凹凸表形式的赫夫曼树打印出来void Convert_tree(unsigned char T100100, int s, int *int k, l;l = +(* i);for (k = 0; k s; k+)*y = i;/对文件t