哈夫曼编译码器课程设计报告(完整版)

1、XXX学院 本科数据结构课程设计总结报告设计题目 ： 实验一、哈夫曼编 / 译码器学生姓名 ： XXX系别： XXX专业： XXX班级： XXX学号： XXX指导教师 ： XXXXXX2012年 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

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

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

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

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

7、e #include / 定义赫夫曼树结点的结构体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); /从已建好的赫夫曼树中选

8、择 parent 为 0，weight 最小的两个结点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 字符串寻找相应叶子节点的递归算法5void Convert_tree(unsignedchar T100100,ints

9、,int*i,intj);/将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树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;6case 5:Print_tree();break;case 0:ex

10、it(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);7/ 初始化函数，输入 n 个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件 hfmtre

11、e 中void Init()FILE *fp;int i,n,w52; /数组存放字符的权值char character52; /存放 n 个字符printf(n输入字符个数 n:);scanf(%d,&n);/输入字符集大小printf(输入 %d个字符及其对应的权值 :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)prin

12、tf(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);printf(n赫夫曼树建立成功，并已存于文件hfmtree.txt中 n);fclose(fp);8/ 建立赫夫曼树的算法void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)int m,i,x,y;HuffmanTree p;if

13、(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.weight=HTx.w

14、eight+HTy.weight;/ 从 HT1 到 HTj 中选择 parent 为 0， weight 最小的两个结点，用x 和 y返回其序号void select(HuffmanTree HT,int j,int *x,int *y)9int 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 (HT

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

16、manCode)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)printf(O

17、pen 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)11for(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 file codefile.txt error!

19、n);if(fw=fopen(textfile.txt,wb+)=NULL)12printf(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文件中的字符已全部读入，存放在code 数组中text=(cha

20、r *)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文件成功译码，兵已存入 textfile.txt文件！nn);13/ 将文件 codefi1e 以紧凑格式显示在

21、终端上 , 每行 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(n文件 codefi1e 显示如下 :n);fscanf(fp,%c,&temp);/从文件读入一个字符

22、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);14/ 将已在内存中的哈夫曼树显示在屏幕上，并将此字符形式的哈夫曼树写入文件 treeprint 中。void Print_tree()unsigned char T100100;int i,j,m=0;FILE *

23、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-1;i+)for (j=0;Tij!=0;j+)if(Tij= ) printf( );fputc(Tij,fp);elseprintf(%

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

25、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(*code!=0)/若译码未结束16code+;if(HTi.lchild=0&HTi.rchild=0)/若找到叶子节点*text=HTi.ch;/将叶子节点的字符

26、存入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);/从该节点的左子树去找elsefind(HT,code,text,HTi.rchild,m);/从该节点的右子树去找else*text=0; /译码结束/ 将文件中的赫夫曼树转换成凹凸表形式的赫夫曼树打印出来void Convert_tree(unsigned c

27、har T100100,int s,int *i,int j)int k,l;17l=+(*i);for(k=0;ks;k+)Tlk= ;Tlk=HTj.weight;if(HTj.lchild)Convert_tree(T,s+1,i,HTj.lchild);if(HTj.rchild)Convert_tree(T,s+1,i,HTj.rchild);Tl+k=0;/八、运行结果分析截图说明：1、运行后界面如图（ 1）：图（ 1）选择要选择的操作序号可以运行各个步骤；2、初始化赫夫曼树：18输入 tobetrans.txt中各元素及其出现频率，如图（2）图（ 2）3、编码及译码，如图（ 3）

28、图（ 3）4、打印编码文件，如图（4）19图（ 4）5、打印赫夫曼树，如图（5）图（ 5）6、各步骤所存的文件内容如图（6）20图（ 6）九、收获及体会课程设计是让我们充分利用我们专业课程所学知识的机会， 也是我们迈向社会，从事工作前一个必不少的过程。通过这次课程设计， 我深深体会到将知识运用到实践中的重要作用。 我这两天的课程设计， 是让我学会脚踏实地迈开这一步，也是为明天能稳健地在社会大潮中奔跑打下坚实的基础。我的课程设计题目是赫夫曼编译码器。最初做这个程序的时候， 让我觉得完成这次程序设计真的是太难了，然后我查阅了课本，并去图书馆借了资料， 在写这个程序的时候也参考了网上的设计流程， 写

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

30、char ch;/ 该字符域用于存放节点的关键字intweight;intparent, lchild, rchild; HTNode, *HuffmanTree ;/ 动态分配数组存储哈夫曼树typedefchar * HuffmanCode;/ 动态分配数组存储哈夫曼编码表voidMenu();/ 显示菜单voidHuffmanCoding( HuffmanTree &HT, char *character,int * w,int n);/ 建立哈夫曼树voidselect( HuffmanTree HT, int j, int *x, int*y);/从已建好的赫夫曼树中选择 paren

31、t为 0， weight 最小的两个结点voidInit();voidCoding();/ 编码voidDecoding();/ 译码voidPrint_code();/ 打印译码好的代码voidPrint_tree();/ 打印哈夫曼树intRead_tree(HuffmanTree &); / 从文件中读入赫夫曼树voidfind( HuffmanTree &HT,char *code, char*text,inti,intm);/ 译码时根据 01 字符串寻找相应叶子节点的递归算法voidConvert_tree(unsignedchar T100100,int s,int*i,intj

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

33、 0 :exit(1);default:printf(Input error!n);getchar();return0;void Menu()/ 操作选择界面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 个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree 中void I

34、nit()FILE *fp;inti, n, w52;/ 数组存放字符的权值char character52;/ 存放 n 个字符23printf(n 输入字符个数n: );scanf( %d, &n);/ 输入字符集大小printf( 输入 %d个字符及其对应的权值: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

35、.txt,w ) =NULL)printf(Open file hfmtree.txt error!n);for (i = 1; i 0），构造哈夫曼树 HT int m, i, x, y;HuffmanTree p;if(n = 1)return ;m = 2 * n - 1;HT = ( HuffmanTree)malloc(m + 1) *sizeof ( HTNode);for (p = HT + 1, i = 1; i ch = *character; p-weight = *w; p-parent = 0; p-lchild = 0; p-rchild = 0;for (;i ch

36、 = 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.weight = HTx.weight + HTy.weight;24/ 从 HT1 到 HTj 中选择 parent 为 0，weight 最小的两个结点，用 x 和 y 返回其序号 void select( HuffmanTree HT, int j , int * x, int * y)inti;/ 查找 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;