哈夫曼编码译码器---课程设计报告

1、目录目录 21课程设计的目的和意义 32需求分析 43概要设计 44详细设计 .85调试分析和测试结果 .116总结 127致谢 138附录 13参考文.201 课程设计目的与意义在当今信息爆炸时代， 如何采用有效的数据压缩技术来节省数据文件的存储 空间和计算机网络的传送时间已越来越引起人们的重视。 哈夫曼编码正是一种应 用广泛且非常有效的数据压缩技术。哈夫曼编码的应用很广泛， 利用哈夫曼树求得的用于通信的二进制编码称为 哈夫曼编码。 树中从根到每个叶子都有一条路径， 对路径上的各分支约定： 指向 左子树的分支表示 “0”码，指向右子树的分支表示 “1”码，取每条路径上的 “0” 或“ 1”的

2、序列作为和各个对应的字符的编码，这就是哈夫曼编码。通常我们把数据压缩的过程称为编码， 解压缩的过程称为解码。 电报通信是 传递文字的二进制码形式的字符串。 但在信息传递时，总希望总长度尽可能最短， 即采用最短码。作为计算机专业的学生， 我们应该很好的掌握这门技术。 在课堂上， 我们能 过学到许多的理论知识， 但我们很少有过自己动手实践的机会！ 课程设计就是为 解决这个问题提供了一个平台。在课程设计过程中， 我们每个人选择一个课题， 认真研究， 根据课堂讲授内 容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还 可以增强我们的独立思考能力和动手能力； 通过编写实验代码和调试运

3、行， 我们 可以逐步积累调试 C 程序的经验并逐渐培养我们的编程能力、 用计算机解决实际 问题的能力。在课程设计过程中， 我们不但有自己的独立思考， 还借助各种参考文献来帮 助我们完成系统。 更为重要的是， 我们同学之间加强了交流， 在对问题的认识方 面可以交换不同的意见。 同时，师生之间的互动也随之改善， 我们可以通过具体 的实例来从老师那学到更多的实用的知识。数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。 课程设计是一个重要的教学环节。 我们在一般情况下都能够重视实验环节， 但是 容易忽略实验的总结， 忽略实验报告的撰写。 通过这次实验让我们明白： 作为一 名大学生必须

4、严格训练分析总结能力、 书面表达能力。 需要逐步培养书写科学实 验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。2 需求分析课 题：哈夫曼编码译码器问题描述： 打开一篇英文文章， 统计该文章中每个字符出现的次数， 然后以它们作为权值，对每一个字符进行编码， 编码完成后再对其编码进行译码。问题补充： 1. 从硬盘的一个文件里读出一段英语文章；2. 统计这篇文章中的每个字符出现的次数；3. 以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储结构的初态和终态进行输出；4. 对每个字符进行编码并将所编码写入文件然后对所编码进行破译。具体介绍：在本课题中， 我们在硬盘中预先建立一

5、个文档， 在里面编辑一篇文章。 然后运行程序， 调用函数读出该文章， 显示在界面； 再调用函数对该文章的字符 种类进行统计， 并对每个字符的出现次数进行统计， 并且在界面上显示； 然后以 每个字符出现次数作为权值， 调用函数构建哈夫曼树； 并调用函数将哈夫曼的存 储结构的初态和终态进行输出。 然后调用函数对哈夫曼树进行编码， 调用函数将 编码写入文件；再调用对编码进行译码，再输出至界面。至此，整个工作就完成 了3 概要设计对系统进行分析，给出系统结构图；厂哈弗曼树编码译码器编码译码退出Pare nt;q=q-Pare nt)ode-HCi.start=0;else HCi.code-HCi.s

6、tart=1;p=p-n ext;行程序得到如下界面:*Met1-编码。*2 -译确7-M-M*E退出-344(沁请输入相应撼作的序号沏3 -图6主界面运行截图2.选择1,按回车键，在输入对字符串进行编码，得到如下界面打开存赦字符串的文件-务输入要打幵的文件名=txti.txt谏人的字符串为二-le llo eeryboidvt Huf Fman codec debuwinig ppocess Is uery in te ire st io g 豊最终的哙大曼編码是：1111011O1311100111H1H110H01 si Bin lieiflBi01 lninenmi mi 110611

7、011180in00ini0 ii 00i0ie0iii00iiii0ei0iie0iie0ii008iii0iiiiiiiii80i0ii lieieseiiioei 0110000100100 10001006181001101000001101000018111111110110101160110000010101160000111110100161 10110诃fum flnmi hari ni 洌int hi 1011nt hfh ifurfu11 hihh mftft保存編码请输入曼保存的文件各.图7编码运行截图3. 输入按回车键保存哈弗曼编码:保存編码尸请输入要保存的文件名:tx

8、t2 -txt保存成功，文件名为:txt2.txto按叵车犍继续图8保存编码运行截图4. 输入按回车键进行译码得到如下界面：打开扁码的文件-请输入要打尸的文件茗：txts-txt得到的最终字符串为：,Hello euepybodly1* Huffman codec debugrsfing process is uery interesting?保存译码.请输入聲保存的立件名匚图9译码运行截图6总结通过一周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理 解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。首先我谈谈我在设计期间我遇到的难点。开始的时候，代码中有许多的错误,特别是

9、有一个“无法找到文件”的错误让我束手无策，最后还是屏蔽了定义的四 个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时， 由于对文件不是太熟悉， 只好翻开 C 语言书本仿照其模式编写。 许多的错误让我 明白了一个道理 - 细心是非常重要的。同时，对于编程者而言，思路清晰是相 当重要的。 在适当的时候和同学一起交流探讨是一个十分好的学习机会。 请教老 师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。而且，某些错误 对于我们来说有时候想半天都弄不来， 但老师几下下就搞好了， 这样就更加有效 地节约了时间。这次课程设计不但让我学得了一些编程知识， 还学会了系统的做一份课程设

10、计报告，学会了如何截图， 学会了如何更好的画流程图， 明白了做事情只有认真， 才能真正做得更好！这段时间里，可谓是酸甜苦辣都尝过。有时，为了一个错误而焦头烂额；有 时，连吃饭都是匆匆了事；但一旦程序运行成功，总会让我兴奋不已。通过这次课程设计， 我看清楚了自己的编程功底和动手能力还不如人意， 这 主要是平时实践太少的缘故。 我想， 在未来的暑假中， 我会努力尝试编写一些程 序。虽然我们信息管理专业的学生， 但现在编程的能力太差了， 毕竟多精通一门 技术总是好事。在这个程序中， 还有许多地方值得完善。 比如，读出文本只能是大写的文档， 空格和小写不能识别，更不用说是任意的 AS5码字符了。由于时

11、间问题，暂时 不能实现了。我想在暑假里好好研究这个问题7 致谢 在这次设计中我要感谢与我同组的两位同学喻霞林和董茗桓， 有很多不懂得 地方我们可以互相讨论研究，没有他们的配合我不可能完成这次课程设计！8 附录 ：#include #include #include #define M 10000#define N 128 typedef struct nodeint weight;struct node *LChild,*RChild,*Parent;struct node *next;HFMNode,*HFMTree;typedef structchar ch;char codeN+1; i

12、nt start;CodeNode;int n;void clearscreen() system(cls);void Open(char s)char name10;FILE *fp;int i=0;printf( 请输入要打开的文件名： ); gets(name);if(fp=fopen(name,rt)=NULL)printf( 打开失败！ n);exit(1);si+=fgetc(fp);while(si-1!=EOF)si+=fgetc(fp);si=0;fclose(fp);void Save(char s) char name10; FILE *fp;printf( 请输入要保存

13、的文件名： ); gets(name);if(fp=fopen(name,wt)=NULL)printf( 存储失败！ ); exit(1);fputs(s,fp);printf(n 保存成功，文件名为 :%s。 n,name);printf(n 按回车键继续 .);getchar();fclose(fp);void SearchStr(char s,char str,int count)int i,j,k=0;for(i=0;iN;i+)counti=0;for(i=0;si;i+)for(j=0;jk;j+)if(strj=si)countj+;break;if(j=k)strk=si;c

14、ountk+;strk=0;n=k;void SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)int i,min;HFMTree p;min=32767;for(i=0,p=HT;inext) if(p-weightParent=0)min=p-weight; *HT1=p;min=32767;for(i=0,p=HT;inext) if(p-weightParent=0&p!=*HT1) min=p-weight; *HT2=p;void CreatHFMTree(HFMTree *HT,int count)int i;HFMTree

15、 p,HT1,HT2;p=*HT=(HFMTree)malloc(sizeof(HFMNode);p-next=p-LChild=p-RChild=p-Parent=NULL; for(i=1;inext=(HFMTree)malloc(sizeof(HFMNode); p=p-next; p-next=p-LChild=p-RChild=p-Parent=NULL;for(i=0,p=*HT;iweight=counti; p=p-next;for(i=n;iParent=HT2-Parent=p;p-LChild=HT1;p-RChild=HT2;p-weight=HT1-weight+H

16、T2-weight;p=p-next;void HFMCode(HFMTree HT,CodeNode HC,char str) int i;HFMTree q,p=HT; for(i=0;in;i+)HCi.ch=stri;HCi.coden-1=0;for(i=0;iParent;q=q-Parent) if(q=q-Parent-LChild) HCi.code-HCi.start=0;else HCi.code-HCi.start=1;p=p-next;void TotalCoding(char s,CodeNode HC,char code)int i,j;code0=0;for(i

17、=0;si;i+)for(j=0;jParent;root=root-Parent); for(i=0,p=root;codei;i+)if(codei=0)p=p-LChild;else p=p-RChild;if(p-LChild=NULL&p-RChild=NULL) for(j=0,q=HT;q!=p;q=q-next,j+); sk+=strj;p=root; iksk=0;void Coding(char s,char str,char code,int count,HFMTree *HT,CodeNode HC)clearscreen();printf(n 打开存放字符串的文件

18、.nn);Open(s);SearchStr(s,str,count); CreatHFMTree(HT,count);HFMCode(*HT,HC,str); TotalCoding(s,HC,code);printf(n 读入的字符串为 :n); puts(s);printf(n 最终的哈夫曼编码是 :n); puts(code);printf(n 保存编码 ,); Save(code);void TransCode(char code,char str,char ss,HFMTree *HT,CodeNode HC) clearscreen(); printf(n打开编码的文件 .nn);Open(code);DeCoding(code,*HT,str,ss);printf(n 得到的最终字符串为 :n); puts(ss);printf(n