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

1、西安郵電學院数据结构课程设计报告题目1:哈夫曼编码/译码器题目2：学生信息管理系统系部名称：通信工程系专业名称：通信工程班级：学号：*学生姓名：指导教师：*时间：2009年12月16日 至2009年12月25日题目1.哈夫曼编码/译码器一、课程设计目的通过对哈夫曼编码/译码器的实现，熟悉了解huffman树的创建过程以及存 储结构，对huffman编码/译码过程及原则有了更深层次的认识，锻炼了动手能 力，使知识更好的学以致用，为解决数据压缩问题提供方法。二、课程设计内容通过统计文件中各字符的出现频率，建立huffman树，再通过建立的已经huffman的树，对文件中各字符进行编码，将结果存入新

2、的文件中，然后从文件 中读取huffman编码，进行解码，结果存入新的文件中，并与源文件进行比较。三、需求分析1 统计字符频率：存文件中读入字符，并对各字符出现频率进行统计；2. 建立huffman树：将各字符出现的频率作为权值，建立 huffman树；3. huffman编码：通过已经建立的 huffman树，对个各字符进行编码，并 存入新的文件中；4. 译码：读取存放huffman编码的文件，对文件中编码进行译码，把译码结 果存入新的文件中；5结果验证：将译码结果与原文件内容进行比较；四、概要设计1.系统结构图（功能模块图）统计字符频率9 创建huffman树对文件编码对编码译码对编码译码

3、2 功能模块说明1：统计字符频率：定义结构体typedef struct strchar data;char num;str;其中data域存放字符名称，num域存放字符出现频率，读取文件 ywq1.txt，通过循环比较将结果赋入 s2128中；2：创建huffman树： 定义结构体typedef structchar data;int weight;int pare nt;int lchild;int rchild;htnode,huffma ntreem+1;crthuffmantree()函数，初始化各s2的值赋值给各节点，字符出现作为huffman树存储节点类型，调用 节点均为0 ;然

4、后将存储字符频率的数组 频率作为权值，创建 huffman树；3:对文件编码：定义结构体typedef structchar data;char bitsn+1;codenode,huffma ncoden;作为huffmancode的存储类型，调用 crthuffmancode()函数，从叶子节 点向上回溯，是lchild 则赋值 0'是rchild则赋值为 1'对各字符编 码，再调用 writetofile()函数，将结果写入文件ywq2.txt中；4:对文件译码:读取编码文件ywq2.txt中数据，调用 decodhuffmancode()函数，从根 节点开始，读取1&#

5、39;走向rchild，读取0',走向lchild,直到叶子节 点，将叶子节点data域的值写入文件ywq3.txt中；五、详细设计及运行结果1 读文件统计字符频率(read()函数中实现):源文件ywq1.txt:t ywql-llt -记爭本匚 | 口|><丈悴世）漏需0）格式财 査看迺 帮助qj）|aabbbccccddddd运行结果:2：创建 huffman 树，crthuffmantree():运行结果:"建立的哈夫曼树为：nunbtp data ueight1 :a22 :b33 :c勺4 :d5lchildrchildparentab50050609

6、63: huffman 编码，crthuffmancode();运行结果: .每个字符对应的编码为：<1a00 ><2h01><3c10><4d11> 编码纟吉果为：00001010110110101111111111编码文件ywq2.txt:文件®編転®棺式曲査若迥帮肋®obd08161g11d10101011111111113:译码，decodhuffmancode():打开文件符chywq2.txt读取字rdecodhuffma ncode()文件结束是否找根节点ch =0'找 lchild ；ch =

7、1'找 rchild ；否叶子节点是保存 ywq3.txt结束运行结果:.译码为:aabbbccccddddd文件 ywq3.txt:r j»q3. txt -记車本4:结果验证:比较源文件ywq1.txt与译码文件ywq3.txt可知，译码结果与源文件一致运行结果:编译前后结果的比较二4/wql -txt .txt据一致,aahhhccccddddd aabhbcicccddddd o o oc 00 0 i按任意犍退岀-presskey to continue六、调试情况，设计技巧及体会通过本次数据结构-哈夫曼编码的应用-课程设计为期两周的实习， 让我对数据结构这门课有了

8、深刻的体会，数据结构是在c语言的基础上建立起来 的，它是一个程序的必要条件之一，通过本次实习，也让我真正领略到数据结构在一个程序中占有多么重要的地位，程序=算法+数据结构。不同的程序运用不同的数据结构可以起到事半功倍的作用。在这次实习，我就已经深深体会到数据结构的精彩运用。这次实习的题目是哈夫曼编码的应用， 在给定的源文件情况下，要根椐所学 的哈夫曼树来建立各字符对应的编码从而达到使字符编码化的目的，又要通过解码使所生成的编码能原封不动地解成原来的文件。在编写程序的过程中，也遇到了许多问题，也更让我体会到了编写程序应该 是一步一个脚印得来的，编写一个模块，调试一个，不能全部编写的差不多了， 在

9、进行调试，这样反而是得不偿失，遇到一大堆的错误让人无从找起。从最开始的统计，建树，选择最小次小值，至v后来的编码、译码，自己写了一些，也参考 了一下别人好的程序，例如在选择最小值和次小值时，按照书上是给mini和min2 初始赋值为32767,但参照了一些好的程序之后，我选择将mini, min2初始赋值位一个小于等于零的数，这样会更好，因为字符的频率不吭能为一个小于等于 零的数，如此更符合逻辑；又如统计字符频率时利用 asc码进行统计会更加方便 与明了。当我们写一段程序前，一定要反复的思考，怎样写更方便，更完美，这 样才能写出一个好的程序来。另外调试程序前要有一个大概的图样， 这样在编程时可

10、以有目的，针对性的 建立函数，对函数的形参与实参也要在大脑中有个清晰的认识， 否则问题出在这 就很难解决了。由于哈夫曼编码中会运用到很多循环，所以在编写循环时一定要 注意控制语句，防止造成死循环。七、参考文献c语言程序设计科学出版社数据结构（c语言描述）-清华大学出版社数据结构（使用c语言）-电子科技大学出版社八、附录：源代码#i nclude "stdio.h"#i nclude "stri ng.h" #in clude "stdlib.h" #i nclude "con io.h" #defi ne n 10

11、0 #defi ne m 2*n-1typedef struct/定义哈夫曼树存储节点结构体类型char data;int weight;int pare nt;int lchild;int rchild;huffma ntreem;typedef struct/定义哈夫曼编码结构体类型char data;char bitsn;huffma ncoden;typedef struct str/定义字符串存储单元结构体类型char data;char num;str;int read(str s2)file *fp;char ch;int i,k;str s1128;for(i=0;i<=

12、128;i+)s1i. num = 0; s1i.data = 0;s2i. num = 0; s2i.data = 0;if(fp=fope n("d:ywqywq1.txt","r")=null)printf("n库文件不存在r)；exit(1);printf("n.读取字符串为:n");ch=fgetc(fp);while(!feof(fp)/统计字符频率prin tf("%c",ch);s1ch. nu m+; s1ch.data = ch;ch=fgetc(fp);fclose(fp);for(

13、i=1,k=1;i<=128;i+)if(s1i. nu m!=0)s2k. num = s1i. num;s2k.data = s1i.data;k+;printf("nn.统计结果为(字符频率):n"); for(i=1;i<k;i+)prin tf("<%c%d> ”,s2i.data,s2i. nu m);printf("(共%d 种字符)n”,k-1);return k;void selectmin(huffmantree ht,int i,int *p1,int *p2)/查找哈夫曼链表中两个权值最小的 节点int j

14、,mi n1,mi n2; min1 = mi n2 = -1;for(j = 1;j<=i;j+)if(htj.pare nt = 0)if(htj.weight<mi n1|mi n1=-1)if(mi n1!=-1)mi n2 = min 1;*p2=*p1; min1 = htj.weight;*p1=j;else if(htj.weight<mi n2|mi n2=-1)mi n2 = htj.weight;*p2=j;void crthuffma ntree(huffma ntree ht,str s,i nt n) int i,m,p1,p2;for(i=1;i

15、< n; i+)hti.data = si.data;hti.weight = si. num;hti.pare nt = 0;hti.lchild = 0; hti.rchild = 0;m=2* n-3;for(i=n; i<=m;i+)hti.data = 0;hti.weight = 0;hti.pare nt = 0;hti.lchild = 0;hti.rchild = 0;for(i=n; i<=m;i+)selectmi n(ht,i-1,&p1,&p2);hti .weight=htp1.weight+htp2.weight; htp1.pa

16、re nt=i;htp2.pare nt=i;hti .lchild=p1;h ti .rchild=p2;/创建哈夫曼树/初始化节点调用selectmin函数void crthuffma ncode(huffma ntree ht,huffma ncode hc,i nt k)利用建立好的哈夫曼树对字符串进行编码int c,p,i;char cdn+1;int start;for(i=1;i<k;i+)hci.data = hti.data;start = k-1;cdstart = '0：c=i;while(p=htc.pare nt)!=null)右分支为1ywq2.txt

17、 中 cd-start = (htp.lchild=c)?'0':'1：/左分支为 0,c=p;strcpy(hci.bits,&cdstart);printf("nn.每个字符对应的编码为:n");for(i=1;i<k;i+)prin tf("<%d %c %s> n ”,i,hci.data,hci.bits);void writetofile(huffma ncode hc,i nt n)/ 将编码结果存储在文件文件file *fp1,*fp2;char ch;int i;if(fp仁 fope n( &q

18、uot;d:ywqywq1.txt","r")=null)printf("n文件不存在!");exit(1); if(fp2=fope n( "d:ywqywq2.txt","w")=null) printf("n文件不存在!");exit(1);ch = fgetc(fp1);printf("n.编码结果为："); while(ch != eof) for(i=1;i< n; i+) if(ch = hci.data)fputs(hci.bits,fp2);

19、prin tf("%s",hci.bits);ch = fgetc(fp1);fclose(fp1);fclose(fp2);prin tf("n");void decodhuffma ncode(huffma ntree ht,i nt n)/ 码结果进行译码，并将结果存储在文件ywq3中file *fp1,*fp2;char ch;int p,k;if(fp仁 fope n( "d:ywqywq2.txt","r")=null)printf("n文件不存在!"); exit(1);if(fp

20、2=fope n( "d:ywqywq3.txt","w")=null)printf("n文件未能创建r); exit(1);p=k=2* n-3;ch=fgetc(fp1);printf(".译码为：”)；while(ch!=eof) if(ch='0')p=htp.lchild; else if(ch='1') p=htp.rchild; if(htp.data!=0)prin tf("%c",htp.data); fputc(htp.data,fp2); p=k;ch = fg

21、etc(fp1);prin tf("n");fclose(fp1); fclose(fp2);void compare(i nt k)file *fp1,*fp2;char s1n,s2n;int i=1,j=1;printf("nn.编译前后结果的比较:");if(fp 仁 fope n("d:ywqywq1.txt","rt")=null)printf("n打开文件失败！n");exit(1);printf("nn原文件ywq1.txt中的字符为：");for(i=1;(s1i=fgetc(fp1)!=eof;i+)prin tf("%c",s1i);fclose(fp1);if(fp2=fope n("d:ywqywq3.txt","rt")=null) printf("n打开文件失败！n");exit(1);printf("n 文 件 ywq3.txt 中的字符为：");for(i=1;(s2i=fgetc(fp