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

《哈夫曼编译码器课程设计报告材料(完整版).doc》由会员分享，可在线阅读，更多相关《哈夫曼编译码器课程设计报告材料(完整版).doc（32页珍藏版）》请在三一文库上搜索。

1、实用标准文案XXX学院本科数据结构课程设计总结报告设计题目：实验一、哈夫曼编/译码器学生姓名：XXX系别：XXX专业：XXX班级：XXX学号:XXX指导教师：XXX XXX文档2012年6月21日31XXX学院课程设计任务书题目专业、班级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日指导教师签名：年 6 月 21 日课程负责人签名：2012、设计题目（任选其一）实验一、哈夫曼编/译码器实验目的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 Printing

5、 ）。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件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

6、HT,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. Prin t()打印功能函数：输出哈夫曼树以及对应的编码。七、源代码/#include <stdio.h>#include &l

7、t;stdlib.h>#include <string.h>/ 定义赫夫曼树结点的结构体 typedef structchar ch; / 增加一个域，存放该节点的字符 int weight;int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char *HuffmanCode; /指向赫夫曼编码的指针void tips(); / 打印操作选择界面建立赫夫从已建好的void HuffmanCoding(HuffmanTree &,char *,int *,int); / 曼树的算法void select(Huf

8、fmanTree HT,int j,int *x,int *y); / 赫夫曼树中选择 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

9、字符串寻找相应叶子节点的递归算法void Convert_tree(unsigned char T100100,int s,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 '

10、2':Coding();break;case '3':Decoding();break;case '4':Print_code();break;case '5':Print_tree();break;case '0':exit(1);default :printf("Input error!n"); getchar(); return 0;void tips() /操作选择界面printf(" n");printf(" -请选择操作-n");printf(&quo

11、t; 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 Init()FI

12、LE *fp;int i,n,w52; / 数组存放字符的权值 char character52; /存放 n 个字符printf("n 输入字符个数 n:");scanf("%d",&n);/输入字符集大小printf(”输入(个字符及其对应的权值：n",n);for (i=0;i<n;i+)char b=getchar();scanf("%c",&characteri);scanf("%d",&wi);/输入 n 个字符和对应的权值HuffmanCoding(HT,cha

13、racter,w,n); /建立赫夫曼树if(fp=fopen("hfmtree.txt","w")=NULL)printf("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.t

14、xt 中n");fclose(fp);/ 建立赫夫曼树的算法void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)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<=n;+i,+p,+character,+w) p->ch=*character;p->weight=*w;p->parent=0;p->

15、;lchild=0;p->rchild=0 ;for(;i<=m;+i,+p)p->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.parent=i;HTy.parent=i;HTi.lchild=x;HTi.rchild=y;HTi.weight=HTx.weight+HTy.weight;/ 从 HT1 到 HTj 中选择 parent 为 0，weight 最小的两个结点，用 返回

16、其序号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.weight<HT*x.weight)*x=i;HT*x.parent=1;/ 查找 weight 次小的结点for (i=1;i<=j;i+)if (HTi.parent=0)*y=i;break;for (;i<=j;i+)if (HTi

17、.parent=0)&&(i!=*x)&&(HTi.weight<HT*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=(HuffmanCode)malloc(n+1

18、)*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("tobet

19、rans.txt","rb")=NULL)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.

20、ch=temp) break; / for(int r=0;HCir!='0'r+) / fputc(HCir,fw); fscanf(fp,"%c",&temp); /在赫夫曼树中查找字符所在的位置将字符对应的编码存入文件从文件读入下一个字符 fclose(fw); fclose(fp); printf("n 已将文件 hfmtree.txt 成功编码 , 并已存入 codefile.txt 中！ nn");/ 将文件 codefile 中的代码进行译码，结果存入文件 textfile 中void Decoding()FILE

21、*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!n");if(fw=fopen("textfile.txt","wb+")=NULL)printf("Open file textfile.txt e

22、rror!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=(char *)malloc(100*size

23、of(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

24、");/ 将文件 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

25、("Open file codeprint.txt error!n");printf("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); /

26、 从文件读入一个字符printf("nn 已将此字符形式的编码写入文件 codeprint.txt 中！ nn");fclose(fp);fclose(fw);/ 将已在内存中的哈夫曼树显示在屏幕上，并将此字符形式的哈夫曼树写入 文件 treeprint 中。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); / 将内存中的赫

27、夫曼树转换成凹凸表形式 的树，存于数组 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);else printf("%d",Ti

28、j);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("hfmtree.txt","r")=N

29、ULL) 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

30、) if(*code!='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

31、,code,text,HTi.lchild,m); / else find(HT,code,text,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;k<s;k+)Tlk=''；Tlk=HTj.weight;if(HTj.lchild)Co nvert_tree(T,s+1,i,HTj.lchild);if(HT

32、j.rchild)Con vert_tree(T,s+1,i,HTj.rchild);Tl+k='0'/ /八、运行结果分析截图说明：1、运行后界面如图（1）:图（1）选择要选择的操作序号可以运行各个步骤;2、初始化赫夫曼树:输入tobetrans.txt中各元素及其出现频率，如图（2）图（2）3、编码及译码，如图（3）己将CDdEf lie文件成功译码，兵已存Ataxtf件I请选择操作夫尋已将文件hfntrtt. St成功編码序己存人def ilc.tXt中!曼夫 文曼 赫 码夫 化-祀赫- 始57器 初褊译弄週图（3）4、打印编码文件，如图（4）芹树 文曼 -代赫- 芻译H

33、IR 1 2 3 4 5 0文件匚口（1石£ ilE显于如下=1 im 0011111 Ban 111 uihi 1011111101竹 10 己将此字符形式的編码写入文件中!图（4）5、打印赫夫曼树，如图（5）图（5）6、各步骤所存的文件内容如图（6）图（6）九、收获及体会课程设计是让我们充分利用我们专业课程所学知识的机会，也是我们迈向社会，从事工作前一个必不少的过程。通过这次课程设计，我深深体会到将知识运用到实践中的重要作用。我这两天的课程设计，是让我学会脚踏实地迈开这一步， 也是为明天能稳健地在社会大潮中奔跑打下坚实的基础。我的课程设计题目是赫夫曼编译码器。最初做这个程序的时候

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

35、 <stdio.h>#i nclude <stdlib.h>/为exit()提供原型#in clude<stri ng.h>/哈夫曼树结点的结构typedef struct char ch;/该字符域用于存放节点的关键字int weight;int pare nt, lchild, rchild; HTNode * HuffmanTree;/动态分配数组存储哈夫曼树typedef char * HuffmanCode;/动态分配数组存储哈夫曼编码表void Menu();/ 显示菜单void HuffmanCoding( HuffmanTree &H

36、T, char Character,int * w, int n);/ 建立哈夫曼树void select( Huffma nTree HT, i nt j, int *x, int *y);/ 从已建好的赫夫曼树中选择 pare nt为0, weight最小的两个结点void Init();void Coding();/ 编码void Decoding();/ 译码void Print_code();/打印译码好的代码void Print_tree();/ 打印哈夫曼树int Read tree( HuffmanTree &); /从文件中读入赫夫曼树void find( Huffm

37、anTree &HT, char *code, char *text, int i, int m);/ 译码时根据 01 字符串寻找相应叶子节点的递归算法void Convert_tree( unsigned char T100100, int s, int *i, int j);/ 将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; / 全局变量int n = 0;/全局变量，存放赫夫曼树叶子结点的数目int main()char select;case '1' :Init();break;case '2' :Coding();

38、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")； jpri ntf("n"）；pr

39、intf("n"）；pri ntf("1初始化赫夫曼树-n")；pri ntf("2编码n");pri ntf("3译码n");pri ntf("4打印代码文件n")；pri ntf("5打印赫夫曼树n")；pri ntf("0退岀n");pri ntf("n"）；hfmtree 中/初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件 void Init()FILE *fp;/数组存放字符的权值/存放n个字符i

40、nt i, n, w52;char character52;printf( "n输入字符个数n:“)；seanf( "%d", &n);/输入字符集大小printf("输入介字符及其对应的权值:n" , n);for (i = 0; i<n; i+)char b = getchar();seanf( "%c", &characteri);scanf( "%d", &wi);/输入n个字符和对应的权值HuffmanCoding(HT, character, w, n);/ 建立

41、赫夫曼树if (fp = fopen( "hfmtree.txt" , "w") = NULLprintf( "Ope n file hfmtree.txt error!n");for (i = 1; i <= 2 * n - 1; i+)if (fwrite(&HTi,sizeof (HTNod®, 1, fp) != 1)/ 将建立的赫夫曼树存入文件hfmtree.txt 中pr in tf("File write error!' n");printf( "n赫夫曼树建

42、立成功，并已存于文件hfmtree.txt 中n");fclose(fp);/构造哈夫曼树的算法void HuffmanCoding( HuffmanTree &HT, char *character, int * w, int n)/w存放n个字符的权值(均>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 = HT + 1, i = 1; i &l

43、t;= n; +i, +p, +character, +w)p->ch = *character; p->weight = *w; p->pare nt = 0; p->lchild = 0; p->rchild = 0;for (; i <= m; +i, +p) p->ch = 0; p->weight = 0; p->parent = 0; p->lchild = 0; p->rchild=0; fc)r (i = n + 1; i <= m; +i)select(HT, i - 1, &x, &y)

44、;HTx.pare nt = i; HTy.pare nt = i;HTi.lchild = x; HTi.rchild = y;HTi.weight = HTx.weight + HTy.weight; /从HT1到HTj中选择pare nt为0, weight最小的两个结点，用x和y返回其序号 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

45、; i+)if ( HTi.parent = 0) && ( HTi.weight< HT* x.weight)*x = i;HT* x.parent = 1;/查找weight次小的结点for (i = 1; i <=j ; i+)if ( HTi.parent = 0)*y = i; break ;for (; i <=j; i+)if ( HTi.parent = 0) && (i != *x) && ( HTi.weight<HT* y.weight)*y = i;/对文件tobetrans中的正文进行编码，然后将

46、结果存入文件codefile中void Coding()FILE *fp, *fw;int i, f, c, start;char *cd;Huffma nCodeHC;if (n = 0)n = Read_tree(HT); /从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数HC指向的/求赫夫曼树中各叶子节点的字符对应的的编码，并存于空间中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'