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

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.系统结构图（功能模块图）字符名称s出现次数初始化结点赋值Huffma编码存入文件f读取编码对编码

3、译码-存入文件成功L失败2功能模块说明1：统计字符频率： 定义结构体typedef struct strchar data;char num;str;其中 data 域存放字符名称， num 域存放字符出现频率，读取文件 ywq1.txt ，通过循环比较将结果赋入 S2128 中；2：创建 Huffman 树: 定义结构体 typedef structchar data;int weight;int parent;int lchild;int rchild;HTNode,HuffmanTreeM+1;CrtHuffmanTree() 函数，初始化各S2 的值赋值给各节点，字符出现作为 Huff

4、man 树存储节点类型，调用 节点均为 0 ；然后将存储字符频率的数组 频率作为权值，创建 Huffman 树；3：对文件编码：定义结构体typedef structchar data;char bitsN+1;CodeNode,HuffmanCodeN;作为HuffmanCode的存储类型，调用 CrtHuffmanCode()函数，从叶子节 点向上回溯，是 lchild 则赋值 0，是 rchild 则赋值为 1，对各字符编 码，再调用 WriteToFile() 函数，将结果写入文件 ywq2.txt 中；4：对文件译码 :读取编码文件ywq2.txt中数据，调用 DecodHuffma

5、nCode()函数，从根 节点开始，读取 1，走向 rchild ，读取 0, 走向 lchild, 直到叶子节 点，将叶子节点 data 域的值写入文件 ywq3.txt 中；五、详细设计及运行结果1读文件统计字符频率 (read() 函数中实现 )：开始源文件ywq1.txt :r i,tn - 记事#T.fn|x文件届辑格式电亘看妁花旺叩jmiiicrcrdmiiia运行结果: 陕职宇符串光:aabbb&cecddlddd 一统说直果划字符 频率头2 2：创建 Huffman 树，CrtHuffmanTree():n运行结果：.建立旳帀夫曼树为：nunbcv* data weightlc

6、hildtchildparent00$ftn000963: Huffman编码，CrtHuffmanCode();运行结果: 每个字符对应的錦码为:.编码结果为土 编码文件ywq2.txt :* yva?-tE-t -口问冈龙件町 鋪辑町 蒂式辺 芒看辻 书肋onvaucai ui 011 eh 01 di minniiii3:译码，DecodHuffmanCode():1 r打开文件符chywq2.txt读取字1DecodHuffma nCode()文件结束是否找根节点ch =0,找 lchild ；ch =1,找 rchild ；1 F否叶子节点是保存 ywq3.txt结束运行结果: 译码

7、为：abbbccccddddd文件 ywq3.txt:yq3. tit -记專本.i n x丈件 垢揖 格式 苣看閤 苦就QPrihtibccnrdddiiii4:结果验证:致。运行结果:aabbbccccdddddaabbbccccddddd64 OC PI _P| JO* *编译前后结杲旳比较；衣牛网匸孙子符为; 前后薮据一甄编钢成动！（按任意犍i&出*Press any key to continue六、调试情况，设计技巧及体会的，它是一个程序的必要条件之一， 在一个程序中占有多么重要的地位， 的数据结构可以起到事半功倍的作用 构的精彩运用通过本次数据结构-哈夫曼编码的应用-课程设计为期

8、两周的实习， 让我对数据结构这门课有了深刻的体会，数据结构是在C语言的基础上建立起来 通过本次实习，也让我真正领略到数据结构 程序=算法+数据结构。不同的程序运用不同 在这次实习，我就已经深深体会到数据结这次实习的题目是哈夫曼编码的应用， 在给定的源文件情况下，要根椐所学 的哈夫曼树来建立各字符对应的编码从而达到使字符编码化的目的， 又要通过解 码使所生成的编码能原封不动地解成原来的文件。在编写程序的过程中，也遇到了许多问题，也更让我体会到了编写程序应该 是一步一个脚印得来的，编写一个模块，调试一个，不能全部编写的差不多了， 在进行调试，这样反而是得不偿失，遇到一大堆的错误让人无从找起。 从最

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

10、有个清晰的认识， 否则问题出在这 就很难解决了。由于哈夫曼编码中会运用到很多循环，所以在编写循环时一定要 注意控制语句，防止造成死循环。七、参考文献科学清华大学电子科技大学C语言程序设计数据结构（C语言描述） 数据结构（使用C语言）八、附录：源代码#i nclude stdio.h#include string.h #i nclude stdlib.h #in elude coni o.h #defi ne N 100#define M 2*N-1typedef struct /char data; int weight; int parent; int lchild; int rchild;

11、HuffmanTreeM;typedef struct / char data;char bitsN; HuffmanCodeN;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=128;i+) s1i.num = 0; s1i.data = 0;s2i.num = 0; s2i.data = 0; if(fp=fopen(d:ywqywq1.txt

12、,r)=NULL) printf(n 库文件不存在 !); exit(1);printf(n . 读取字符串为 :n);统计字符频率ch=fgetc(fp);while(!feof(fp) / printf(%c,ch); s1ch.num+; s1ch.data = ch; ch=fgetc(fp); fclose(fp); for(i=1,k=1;i=128;i+)if(s1i.num!=0)s2k.num = s1i.num; s2k.data = s1i.data; k+; printf(nn .统计结果为(字符 频率):n);for(i=1;ik;i+)printf( ,s2i.da

13、ta,s2i.num);printf(” ( 共4种字符)n,k-1); return k;void SelectMin(HuffmanTree ht,int i,int *p1,int *p2) /查找哈夫曼链表中两个权值最小的节点int j,min1,min2;min1 = min2 = -1;for(j = 1;j=i;j+)if(htj.parent = 0)if(htj.weightmin1|min1=-1)if(min1!=-1)min2 = min1;*p2=*p1;min1 = htj.weight;*p1=j;else if(htj.weightmin2|min2=-1)mi

14、n2 = htj.weight;*p2=j;创建哈夫曼树初始化节点void CrtHuffmanTree(HuffmanTree ht,str s,int n) / int i,m,p1,p2; for(i=1;in;i+)/hti.data = si.data; hti.weight = si.num;hti.parent = 0;hti.lchild = 0;hti.rchild = 0;m=2*n-3;for(i=n;i=m;i+)hti.data = 0;hti.weight = 0;hti.parent = 0;hti.lchild = 0;hti.rchild = 0;for(i=

15、n;i=m;i+)调用 SelectMin 函数SelectMin(ht,i-1,&p1,&p2); / hti.weight=htp1.weight+htp2.weight; htp1.parent=i;htp2.parent=i;hti.lchild=p1;hti.rchild=p2;void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int k) / 利用建立好的哈夫 曼树对字符串进行编码int c,p,i;char cdN+1;int start;for(i=1;ik;i+)hci.data = hti.data;start = k-1;

16、cdstart = 0;c=i;while(p=htc.parent)!=NULL)cd-start = (htp.lchild=c)?0:1; / 左分支为 0，右分支为1c=p;strcpy(hci.bits,&cdstart);printf(nn . 每个字符对应的编码为 :n);for(i=1;ik;i+)printf( n,i,hci.data,hci.bits);void WriteToFile(HuffmanCode hc,int n) /FILE *fp1,*fp2;char ch;int i;if(fp1=fopen(d:ywqywq1.txt,r)=NULL) 将编码结果存

17、储在文件文件 ywq2.txt 中printf(n文件不存在 !);exit(1);if(fp2=fopen(d:ywqywq2.txt,w)=NULL)printf(n 文件不存在 !); exit(1);ch = fgetc(fp1); printf(n .编码结果为： );while(ch != EOF) for(i=1;in;i+) if(ch = hci.data) fputs(hci.bits,fp2); printf(%s,hci.bits);ch = fgetc(fp1); fclose(fp1);fclose(fp2); printf(n);码结果进行译码，并将结果存储在文件

18、 ywq3 中void DecodHuffmanCode(HuffmanTree ht,int n) /FILE *fp1,*fp2;char ch;int p,k;if(fp1=fopen(d:ywqywq2.txt,r)=NULL)printf(n 文件不存在 !); exit(1); if(fp2=fopen(d:ywqywq3.txt,w)=NULL)printf(n 文件未能创建 !); exit(1); p=k=2*n-3; ch=fgetc(fp1); printf(. 译码为 : );while(ch!=EOF) if(ch=0)p=htp.lchild; else if(ch

19、=1) p=htp.rchild; if(htp.data!=0) printf(%c,htp.data); fputc(htp.data,fp2);p=k;ch = fgetc(fp1);printf(n); fclose(fp1); fclose(fp2);void compare(int k)FILE *fp1,*fp2;char s1N,s2N;int i=1,j=1; printf(nn . 编译前后结果的比较 :);if(fp1=fopen(d:ywqywq1.txt,rt)=NULL) printf(n 打开文件失败！ n); exit(1);printf(nn 原文件 ywq1.txt 中的字符为 : ); for(i=1;(s1i=fgetc(fp1)!=EOF;i+)printf(%c,s1i); fclose(fp1);if(fp2=fopen(d:ywqywq3.txt,rt)=NULL) printf(n 打开文件失败！ n); exit(1