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

wordXXX学院本科数据结构课程设计总结报告 设计题目：实验一、哈夫曼编/译码器 学生某某：XXX 系 别：XXX 专 业：XXX 班 级：XXX 学 号：XXX 指导教师：XXX XXXxxx学院课 程 设 计 任 务 书题目一、赫夫曼编译码器 专业、班级xxx 学号xxx 某某 xxx主要内容、根本要求、主要参考资料等：1. 主要内容利用哈夫曼编码进展信息通信可大大提高信道利用率，缩短信息传输时间，降低传输本钱。要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进展译码复原。对于双工信道既可以双向传输信息的信道，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。2. 根本要求 系统应具有以下功能：1C：编码Coding。对文件tobetrans中的正文进展编码，然后将结果存入文件codefile中，将以此建好的哈夫曼树存入文件HuffmanTree中2D：解码Decoding。利用已建好的哈夫曼树将文件codefile中的代码进展译码，结果存入textfile中。3P：打印代码文件Print。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。4T：打印哈夫曼树Tree Printing。将已在内存中的哈夫曼树以直观的方式树或凹入表形式显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。3. 参考资料：数据结构C语言版 严蔚敏、吴伟民编著； 数据结构标准教程 胡超、闫宝玉编著完 成 期 限： 2012年6月21 日 指导教师签名：课程负责人签名：一、设计题目任选其一实验一、哈夫曼编/译码器二、 实验目的1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；2 深化对算法课程中根本概念、理论和方法的理解；3 巩固构造赫夫曼树的算法；4 设计试验用程序实验赫夫曼树的构造。三、运行环境软、硬件环境Windows xp sp3，英文版四、算法设计的思想1初始化赫夫曼树，输入文件tobetrans2编码Coding。对文件tobetrans中的正文进展编码，然后将结果存入文件codefile中3D：解码Decoding。利用已建好的哈夫曼树将文件codefile中的代码进展译码，结果存入textfile中。4P：打印代码文件Print。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。5T：打印哈夫曼树Tree Printing。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。五、 流程图六、 算法设计分析1.赫夫曼树节点的数据类型定义为：typedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;HTNode,*HuffmanTree;2.void HuffmanCoding(HuffmanTree &,char *,int *,int);建立赫夫曼树的算法，此函数块调用了Select函数。void select(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() 打印功能函数：输出哈夫曼树以与对应的编码。七、源代码/#include <stdio.h>#include <stdlib.h>#include <string.h>/定义赫夫曼树结点的结构体typedef struct char 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，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字符串寻找相应叶子节点的递归算法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 '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(" -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() FILE *fp;int i,n,w52; /数组存放字符的权值char character52; /存放n个字符printf("n输入字符个数 n:");scanf("%d",&n); /输入字符集大小printf("输入%d个字符与其对应的权值:n",n);for (i=0;i<n;i+) char b=getchar(); scanf("%c",&characteri); scanf("%d",&wi); /输入n个字符和对应的权值 HuffmanCoding(HT,character,w,n); /建立赫夫曼树if(fp=fopen("hfmtree.txt","w")=NULL) printf("Open file hfmtree.txt error!n");for (i=1;i<=2*n-1;i+) printf("File write error!n");printf("n赫夫曼树建立成功，并已存于文件hfmtree.txt中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->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最小的两个结点，用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;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中的正文进展编码，然后将结果存入文件codefile中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)*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("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); /从文件读入下一个字符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!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文件中的字符已全部读入，存放在code数组中 text=(char *)malloc(100*sizeof(char);p=text; m=2*n-1;if(*code='0') find(HT,code,text,HTm.lchild,m); /从根节点的左子树去找else find(HT,code,text,HTm.rchild,m); /从根节点的右子树去找 fputc(pi,fw);fclose(fp);fclose(fw);printf("n已将codefile.txt文件成功译码，兵已存入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("n文件codefi1e显示如下:n");fscanf(fp,"%c",&temp); /从文件读入一个字符for (i=1;!feof(fp);i+) printf("%c",temp); if(i%50=0) printf("n"); fscanf(fp,"%c",&temp); /从文件读入一个字符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); /将内存中的赫夫曼树转换成凹凸表形式的树，存于数组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",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("hfmtree.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(*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); /从根节点的左子树找 else find(HT,code,text,HTm.rchild,m); /从根节点的右子树找 else /如果不是叶子节点 if(*code='0') find(HT,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) 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、初始化赫夫曼树：输入tobetrans.txt中各元素与其出现频率，如图2图23、编码与译码，如图3图34、打印编码文件，如图4图45、打印赫夫曼树，如图5图56、各步骤所存的文件内容如图6图6九、收获与体会课程设计是让我们充分利用我们专业课程所学知识的机会，也是我们迈向社会，从事工作前一个必不少的过程。通过这次课程设计，我深深体会到将知识运用到实践中的重要作用。我这两天的课程设计，是让我学会脚踏实地迈开这一步，也是为明天能稳健地在社会大潮中奔跑打下坚实的根底。我的课程设计题目是赫夫曼编译码器。最初做这个程序的时候，让我觉得完成这次程序设计真的是太难了，然后我查阅了课本，并去图书馆借了资料，在写这个程序的时候也参考了网上的设计流程，写完刚运行时出现了很多问题。尤其是编码错误，导致内存无法read，通过同组人员的交流请教，逐渐明白过来，然后经过不知道多少次修改才顺利运行。本次试验也让我明白了理论与实际相结合的重要性，并提高了自己组织数据与编写大型程序的能力，培养了根本的、良好的程序设计技能以与合作能力。通过对各个步骤各个流程的控制，逐渐让我产生了兴趣，在实际编写过程中，和同学们相互讨论让我学到的不仅仅是一些解决问题的方法，更是解决问题的思想。课程设计本身也是一种相互学习的过程,/#include<stdio.h>#include<stdlib.h>/为exit()提供原型#include<string.h>/哈夫曼树结点的结构typedefstruct char ch; /该字符域用于存放节点的关键字int weight;int parent, lchild, rchild;HTNode, *HuffmanTree; /动态分配数组存储哈夫曼树typedefchar *HuffmanCode; /动态分配数组存储哈夫曼编码表void Menu(); /显示菜单void HuffmanCoding(HuffmanTree &HT, char *character, int * w, int n); /建立哈夫曼树void select(HuffmanTree 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字符串寻找相应叶子节点的递归算法void Convert_tree(unsignedchar T100100, int s, int *i, int j); /将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; /全局变量int n = 0; /全局变量，存放赫夫曼树叶子结点的数目int main()char select;while (1)Menu();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;case'0':exit(1);default:printf("Input error!n");getchar();return 0;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 Init()FILE *fp;int i, n, w52; /数组存放字符的权值char character52; /存放n个字符printf("n输入字符个数 n:");scanf("%d", &n); /输入字符集大小printf("输入%d个字符与其对应的权值:n", n);for (i = 0; i<n; i+)char b = getchar();scanf("%c", &characteri);scanf("%d", &wi); /输入n个字符和对应的权值HuffmanCoding(HT, character, 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) printf("File write error!n");printf("n赫夫曼树建立成功，并已存于文件hfmtree.txt中n");fclose(fp);/构造哈夫曼树的算法void HuffmanCoding(HuffmanTree &HT, char *character, int * w, int n) /w存放n个字符的权值均>0，构造哈夫曼树HTint 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->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最小的两个结点，用x和y返回其序号void select(HuffmanTreeHT, intj, int *x, int *y)int i;/查找weight最小的结点for (i = 1; i <= j; i+)if (HTi.parent = 0)*x = i;