数据结构哈弗曼编码译码器课程设计

数据结构与算法课程设计报告 课程设计题目：哈弗曼编码/译码器 专业班级： 信息与计算科学1001班 姓 名： 学 号： 设计室号： 理学院机房 设计时间： 2011-12-26 批阅时间： 指导教师： 成 绩： 哈夫曼算法的编码和译码系统目录一.设计要求2. 功能设计流程3. 详细设计4. 调试5. 总结6. 参考文献七.附录源代码 一设计要求 设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。1.1基本要求1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；6)设字符集及频度如下表：字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 1.2进一步完成内容1)译码功能；2)显示哈夫曼树；3)界面设计的优化。 二功能流程图2.1主要流程实现图 图的算法实现 打印哈夫曼树译码文件编码文件初始化哈夫曼树 2.2主要菜单选择函数Main函数中包裹四个主要功能函数，即用于构造和初始哈夫曼树的HuffmanCoding函数用于对指定文件进行编码的void Coding函数用于对哈夫曼编码进行译码的void Decoding函数用于在屏幕终端上显示哈弗满树的void Print_tree函数其相互联系如下图所示Main函数HuffmanCodingPrint_treevoid CodingDecoding()其中用于初始化哈夫曼树的 Huffman coding()函数包含两个子函数，即（1）void select(HuffmanTree HT,int j,int *s1,int *s2)从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点（2）void Init()输入n个字符及其对应的权值，根据权值建立哈夫曼树，其相互联系如图所示HuffmanCoding（）void Init()void select在本程序中，主界面为一个功能选择界面，根据提示，使用者可以选择不同的功能进行操作。但由于在编制写程序的源代码中，出于方便编写的考虑，我们对一些功能所要引用的文件进行了提前的命名，因此在使用之前使用者应该提前知晓操作程序所需要的特定文件名，现总结如下：Tobetrans.txt:用于存储待编码的文本文件Codefile.txt:用于存储由Tobetrans.txt编码得到的哈弗曼编码信息Textfile.txt: 用于存储由Codefile.txt译码得到的文本文件hfmtree.txt:用于存储哈夫曼树的文本文件 三详细设计3.1初始化哈夫曼树：基本思想：首先根据使用者输入的待编码字符和相应的权重值，再根据哈夫曼树的建立过程机型哈夫曼树的构造主要步骤及主要功能函数：（1）首先根据给定的权重构造n棵二叉树的森林，其中每个二叉树都只有一个权值为wi的根节点（2）在森林中选取两个权值最小的根节点作为一个新二叉树的左右结点其具体函数为void select(HuffmanTree HT,int j,int *s1,int *s2) /其中s1,s2为权值最小的两个根节点for (i=1;i=j;i+) if (HTi.parent=0) *s1=i; break; for (;i=j;i+) if (HTi.parent=0)&(HTi.weightHT*s1.weight) *s1=i; HT*s1.parent=1;通过遍历所有节点找到权值最小的结点（3）设新二叉树的根节点为左右子结点的权值和其函数表达为for(i=n+1;i=m;+i) select(HT,i-1,&s1,&s2); HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight;（4）从森林中删除选中的那两棵二叉树，同时加入新构造的那个二叉树（5）重复上述步骤，得到所需的哈弗曼二叉树3.2编码：基本思想：根据已构造好的哈夫曼树，对于每一个根节点从自身位置开始往根节点回溯，并且规定哈夫曼树中的左节点代表0，有节点代表1，从而得到每个字符的哈弗曼编码主要步骤及主要功能函数：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);3.3译码：基本思想：根据编码的具体过程，逆向推导。从第一个数值开始，如果为零则代表沿左节点元素，如果为一则代表右节点方向主要步骤及主要功能函数：if(*code=0) find(HT,code,text,HTm.lchild,m); else find(HT,code,text,HTm.rchild,m); for(i=0;pi!=0;i+) /把译码好的字符存入文件textfile.txt中 fputc(pi,fw);3.4输出哈夫曼树：基本思想：以凸凹的形式表现哈夫曼树的结构。首先统计叶子结点个数，然后构造一个矩阵，没有元素存在时用空格代替，否则将节点的权重值打印在终端主要步骤及主要功能函数：（1）首先统计叶子节点的总个数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);（2）建立矩阵，利用元素和空格构造一个凸凹的图像，直观的表现结构图，其中元素所在的列数即为在哈夫曼树中所在的层数void Convert_tree(unsigned char T100100,int s,int *i,int j)int k,l;l=+(*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;3.5数据结构的定义/*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/typedef struct int weight; char ch; /增加一个域用于存放该节点的字符 int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode; /指向赫夫曼编码的指针 四调试4.1菜单选择及初始化哈夫曼树界面4.2编码 将编码结果写入codefile文件中4.3译码 在textfile文件中写入译码结果4.4以凹凸表形式打印哈夫曼树为简便输入，我们选取几个较少的元素作为范例，对其进行输入和赋值，元素为a.b.c.d.e.f.g.h.i.j,对应的权重值为1.2.3.4.5.6.7.8.9.0，运行 五总结 通过这次的综合训练让我对所学的知识加深了印象，要想学好c语言要重在实践，要通过不断的上机操作才能更好地学习它尤其是对算法有更深的认识。对整个程序的设计，算法是非常重要的，设计程序的整体框架，就是利用算法进行设计，在短短的几天里，我们去图书馆或在网上查找了很多资料，学了一些以前没有接触过的函数，以此来完善程序的功能。然而很多函数虽然用的语法没错，但是不能运用自如，为自己所用。最后逐步完善各个函数的功能模块，同时算法也有了一定的认识。这些都为以后的学习和实践，提高自身能力有很大的帮助，本次课设也锻炼我们的实践能力和提高了处理问题的能力，获益匪浅 六参考文献刘玉龙数据结构与算法.电子工业出版社.严蔚敏. 数据结构（C语言版）. 清华大学出版社严蔚敏等数据结构题集（C语言版）. 清华大学出版社徐孝凯. 数据结构实用教程（C/C+描述）. 北京:清华大学出版社. 陈慧南. 数据结构（使用C+语言描述）. 南京:东南大学出版社. 殷人昆, 陶永雷, 谢若阳等. 数据结构（用面向对象方法与C+描述）. 北京:清华大学出版社. 七附录源代码#include #include #include /*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/typedef struct int weight; char ch; /增加一个域用于存放该节点的字符 int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode; /指向赫夫曼编码的指针/*本程序用到的函数原型*/void welcome(); /打印操作选择界面void HuffmanCoding(HuffmanTree &,char *,int *,int);/建立赫夫曼树的算法void select(HuffmanTree HT,int j,int *s1,int *s2); /从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点void Init(); /输入n个字符及其对应的权值，根据权值建立哈夫曼树void Coding(); /编码void Decoding(); /译码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) welcome(); scanf(%c,&select); switch(select) case i: case I:Init();break; case c: case C:Coding();break; case d: case D:Decoding();break; case t: case T:Print_tree();break; case e: case E:exit(1); default :printf(Input error!n); getchar();return 0;void welcome() /打印操作选择界面printf(*n);printf( 请选择如下操作 n);printf( n);printf(I 初始化哈夫曼树 n);printf(C 编码文件 n);printf(D 译码 n);printf(T 打印哈夫曼树 n);printf( *n);printf( *n);system(color A);/*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/void Init() FILE *fp;int i,n,w52; /w数组存放n个字符的权值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) 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);printf(n建立赫夫曼树成功，已将其存于文件hfmtree.txt中n);fclose(fp);/建立赫夫曼树的算法/void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)int m,i,s1,s2;HuffmanTree 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,&s1,&s2); HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight;/*从HT1到HTj中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/void select(HuffmanTree HT,int j,int *s1,int *s2)int i;/找weight最小的结点for (i=1;i=j;i+) if (HTi.parent=0) *s1=i;break;for (;i=j;i+) if (HTi.parent=0)&(HTi.weightHT*s1.weight) *s1=i; HT*s1.parent=1;/找weight次小的结点for (i=1;i=j;i+) if (HTi.parent=0) *s2=i;break;for (;i=j;i+) if (HTi.parent=0)&(i!=*s1)&(HTi.weightHT*s2.weight) *s2=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); /从根节点的右子树去找 for(i=0;pi!=0;i+) /把译码好的字符存入文件textfile.txt中 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); fputc(temp,fw); /将该字符存入文件codeprint.txt中 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中读入赫夫曼