哈夫曼树课程设计

1、计计算算机机学学院院信信息息 管管理理与与信信息息系系统统专专业业数数据据结结构构课课程程设设计计题题 目：目： 哈夫曼树的应用哈夫曼树的应用 班班 级：级： 信管信管 0910109101 班班 姓姓 名：名： 赵林芬赵林芬 学学 号：号： 200917020114200917020114 同组人姓名：同组人姓名： 陈立芳陈立芳 王红王红 起起 迄迄 日日 期：期： 2011.03.01-03.042011.03.01-03.04 课程设计地点课程设计地点: : 系办公楼系办公楼 E3-A513E3-A513 指导教师：指导教师： 孙叶枫孙叶枫 评阅意见：评阅意见：成绩评定：成绩评定：评阅人

2、：评阅人： 日期：日期： 完成日期：完成日期：20112011 年年 3 3 月月 4 4 日日 目录目录1、设计目的、设计目的.32、需求分析、需求分析.42.1 选题的意义及背景 .4 42.2 输入/输出形式和输出值的范围 .4 43、概要设计、概要设计.43.1 设计思想 .4 43.2 函数间的关系 .4 44、详细设计、详细设计.54.1 哈夫曼的主要结构 .5 54.1.1 结构定义 .5 54.1.2 主要函数声明及功能描述 .6 64.2 源程序 .7 74.2.1 头文件 .7 74.2.2 源文件.8 85、程序测试结果及问题分析、程序测试结果及问题分析.176、总结、总

3、结.187、参考文献、参考文献.181.设计目的设计目的数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法） 。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。 在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育

4、报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。 数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：1、了解并掌握数

5、据结构与算法的设计方法，具备初步的独立分析和设计能力；2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2 2需求分析需求分析2.12.1 选题的意义及背景选题的意义及背景锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。在信息传递时，希望长度能尽可能短，即采用最短码。赫夫曼编码的应用，就是采用这种有效的数据压缩技术可以节省数据文件的存储空间和计算机网络的

6、传送时间。2.22.2 输入输入/ /输出形式和输出值的范围输出形式和输出值的范围 输入信息以加载存档的 reading.txt 文件为方式，加载不成功，提示出错信息，加载成功后，系统对其编码，并按照选择对各种相关信息存档3 3概要设计概要设计3.13.1 设计思想设计思想 哈夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。 利用多重结构体的形式设计出所需的变量类型，还有基本的文件读写知识，同时借助九大子函数结合一个主函数设计了此课程内容，第一部分为信息的读写及统计；第二部分为哈夫曼树及其编码的建立，再将编码信息写进文件；第三部分为给信息加密在写进文件，再在对其翻译。最后的主函数是整个程

7、序的组织者，利用 switch 选择循环将九大子函数联系起来，画龙点睛。这样整个程序的基本流出就出来了，再根据此流出设计出源程序。 3.23.2 函数间的关系函数间的关系哈夫曼系统，函数间的关系如图所示：头文件及头文件及原文件原文件文件的读文件的读写写哈夫曼的哈夫曼的建立及编建立及编码码文件加密文件加密编码及写编码及写入文件入文件从文件中从文件中读取信息读取信息将信息写将信息写进文件进文件构建哈夫构建哈夫曼树曼树建立哈夫建立哈夫曼编码曼编码给文件信给文件信息加密编息加密编码码将已编码将已编码信息写进信息写进文件文件将编码信将编码信息翻译及息翻译及写入文件写入文件将编码规将编码规则写进文则写进文

8、件件件统计信息统计信息中各字符中各字符的出现次数界面运行图如下：界界面面从文件从文件读取信读取信息息显示编显示编码规则码规则将原文将原文件信息件信息写入文写入文件件将编码将编码规则写规则写进文件进文件将编码将编码后的信后的信息写进息写进文件文件将译码将译码后的信后的信息写入息写入文件文件退退出出 4 4、详细设计、详细设计4.14.1 哈夫曼的主要结构哈夫曼的主要结构 4.1.14.1.1 结构定义结构定义：#define MAXVALUE 1000/定义最大权值#define MAXBIT 100/定义哈夫曼树中叶子结点个数typedef struct char data;/字符值int n

9、um;/某个值的字符出现的次数TotalNode; /统计结点，包括字符种类和出现次数typedef struct TotalNode tot300;/统计结点数组int num;/统计数组中含有的字符个数Total; /统计结构体，包括统计数组和字符种类数typedef struct char mes300;/字符数组int num;/总字符数Message; /信息结构体，包括字符数组和总字符数typedef structint locked500;/密码数组int num;/密码总数Locking; /哈夫曼编码后的密文信息typedef struct char data;/字符int

10、weight;/权值int parent;/双亲结点在数组 HuffNode中的序号int lchild;/左孩子结点在数组 HuffNode中的序号int rchild;/右孩子结点在数组 HuffNode中的序号HNodetype; /哈夫曼树结点类型，包括左右孩子，权值和信息typedef struct int bitMAXBIT;int start;HCodetype; /哈夫曼编码结构体，包括编码数组和起始位4.1.24.1.2 主要函数声明及功能描述如下主要函数声明及功能描述如下：void reading_file(Message *message);从文件中读取信息void wr

11、iting_file(Message *message);将信息写进文件void total_message(Message *message,Total *total);统计信息中各字符的出现次数void HaffmanTree(Total *total,HNodetype HuffNode);构建哈夫曼树void HaffmanCode(HNodetype HuffNode,HCodetype HuffCode,Total *total);建立哈夫曼编码void writing_HCode(HNodetype HuffNode,HCodetype HuffCode,Total *total

12、);将编码规则写进文件void lock(Message *message,HNodetype HuffNode,HCodetype HuffCode,Total *total,Locking *locking);给文件信息加密编码void writing_lock(Locking *locking);将已编码信息写进文件void writing_translate(Locking *locking,HCodetype HuffCode,HNodetype HuffNode,Total *total);将已编码信息翻译过来并写进文件4.24.2 源程序源程序 4.2.14.2.1 头文件头文件

13、 head.hhead.h#define MAXVALUE 1000/定义最大权值#define MAXBIT 100/定义哈夫曼树中叶子结点个数typedef struct char data;/字符值 int num;/某个值的字符出现的次数TotalNode; /统计结点，包括字符种类和出现次数typedef struct TotalNode tot300;/统计结点数组 int num;/统计数组中含有的字符个数Total; /统计结构体，包括统计数组和字符种类数typedef struct char mes300;/字符数组 int num;/总字符数Message; /信息结构体，

14、包括字符数组和总字符数typedef struct int locked500;/密码数组 int num;/密码总数Locking; /哈夫曼编码后的密文信息typedef struct char data;/字符 int weight;/权值 int parent;/双亲结点在数组 HuffNode中的序号 int lchild;/左孩子结点在数组 HuffNode中的序号 int rchild;/右孩子结点在数组 HuffNode中的序号HNodetype; /哈夫曼树结点类型，包括左右孩子，权值和信息typedef struct int bitMAXBIT; int start;HCo

15、detype; /哈夫曼编码结构体，包括编码数组和起始位void reading_file(Message *message);/从文件中读取信息void writing_file(Message *message);/将信息写进文件void total_message(Message *message,Total *total);/统计信息中各字符的次数void HaffmanTree(Total *total,HNodetype HuffNode);/构建哈夫曼树void HaffmanCode(HNodetype HuffNode,HCodetype HuffCode,Total *to

16、tal);/建立哈夫曼编码void writing_HCode(HNodetype HuffNode,HCodetype HuffCode,Total *total);/将编码规则写进文件void lock(Message *message,HNodetype HuffNode,HCodetype HuffCode,Total *total,Locking *locking);/给文件信息加密编码void writing_lock(Locking *locking);/将已编码信息写进文件void writing_translate(Locking *locking,HCodetype Huf

17、fCode,HNodetype HuffNode,Total *total);/将已编码信息翻译过来并写进文件4.2.24.2.2 源文件源文件 source.cppsource.cpp#include#include#includehead.husing namespace std;int main() int i,j,choice,mark=0;/mark 标记文件信息是否读入到内存中 HNodetype HuffNode500;/保存哈夫曼树中各结点信息 HCodetype HuffCode300; Locking *locking; Total *total; Message *mes

18、sage; locking=new Locking; locking-num=0; total=new Total; total-num=0; message=new Message; message-num=0; /初始化变量 while(1) cout*; cout*1:从文件读取信息 2:显示编码规则 3:将原文件信息写进文件 *; cout*4:将编码规则写进文件 5:将编码后的信息写进文件 6:将译码后的信息写进文件 7:退出 *; cout*; coutendl; coutchoice; switch(choice) case 1: reading_file(message);/从

19、文件中读取信息 mark=1; break; case 2:/显示编码规则 if(mark=0)cout请先从文件中读取信息!endl; else total_message(message,total); HaffmanTree(total,HuffNode); HaffmanCode(HuffNode,HuffCode,total); for(i=0;inum;i+)/显示编码规则 couttoti.data ; for(j=HuffCodei.start+1;jnum;j+) coutHuffCodei.bitj; coutendl; break; case 3:/将原文件信息写进文件

20、if(mark=0)cout请先从文件中读取信息!endl; else writing_file(message);/将信息写进文件 break; case 4:/将编码规则写进文件 if(mark=0)cout请先从文件中读取信息!endl; else total_message(message,total); HaffmanTree(total,HuffNode); HaffmanCode(HuffNode,HuffCode,total); writing_HCode(HuffNode,HuffCode,total); break; case 5:/将编码后的信息写进文件 if(mark=

21、0)cout请先从文件中读取信息!endl; else total_message(message,total); HaffmanTree(total,HuffNode); HaffmanCode(HuffNode,HuffCode,total); lock(message,HuffNode,HuffCode,total,locking); writing_lock(locking); break; case 6:/将译码后的信息写进文件 if(mark=0)cout请先从文件中读取信息!endl; else total_message(message,total); HaffmanTree(

22、total,HuffNode); HaffmanCode(HuffNode,HuffCode,total); writing_translate(locking,HuffCode,HuffNode,total); break; case 7: exit(1); default: cout输入错误，请重新选择endl; for(i=0;inum;i+) if(locking-lockedi=-1)cout ; else coutlockedi; coutendl; for(i=0;inum;i+) couttoti.data toti.numendl; for(i=0;inum)-1;i+) c

23、outHuffNodei.parent ; coutendl; return 0;void reading_file(Message *message) int i=0; char ch; ifstream infile(c:reading.txt,ios:in|ios:out); if(!infile)/打开失败则结束 cout打开 c:reading.txt 文件失败endl; exit(1); else cout读取文件成功mesi=ch; i+; message-num=i;/记录总字符数 infile.close();/关闭文件/从文件中读取信息void writing_file(M

24、essage *message)/将信息写进文件 int i; ofstream outfile(c:writing.txt,ios:in|ios:out);/打开文件 if(!outfile)/打开失败则结束 cout打开 c:writing.txt 文件失败endl; exit(1); for(i=0;inum;i+)/写文件 outfile.put(message-mesi); cout信息写进文件成功endl; outfile.close();/关闭文件/将原信息写入文件void total_message(Message *message,Total *total) int i,j,

25、mark; for(i=0;inum;i+)/遍历 message 中的所有字符信息 if(message-mesi!= )/字符不为空格时 mark=0; for(j=0;jnum;j+)/在 total 中搜索当前字符 if(total-totj.data=message-mesi)/搜索到，则此字符次数加 1，mark 标志为 1 total-totj.num+; mark=1; break; if(mark=0)/未搜索到，新建字符种类，保存进 total 中，字符类加 1 total-tottotal-num.data=message-mesi; total-tottotal-num

26、.num=1; total-num+; /统计信息中各字符的出现次数通过各权值的一一比较选取最小和次小两权值建立二叉树，记录节点的左右孩通过各权值的一一比较选取最小和次小两权值建立二叉树，记录节点的左右孩子及双亲的位置关系最终构建成哈夫曼树，且记录的左孩子权值比右孩子小子及双亲的位置关系最终构建成哈夫曼树，且记录的左孩子权值比右孩子小voidvoid HaffmanTree(TotalHaffmanTree(Total *total,HNodetype*total,HNodetype HuffNode)HuffNode) intint i,j,min1,min2,x1,x2;i,j,min1,

27、min2,x1,x2;首先初始化哈夫曼树并存入叶子结点权值和信息首先初始化哈夫曼树并存入叶子结点权值和信息 for(i=0;inum)-1;i+)for(i=0;inum)-1;i+) if(inum-1)HuffNodei.data=total-toti.data;if(inum-1)HuffNodei.data=total-toti.data; HuffNodei.weight=total-toti.num;HuffNodei.weight=total-toti.num; HuffNodei.parent=-1;HuffNodei.parent=-1; HuffNodei.lchild=-

28、1;HuffNodei.lchild=-1; HuffNodei.rchild=-1;HuffNodei.rchild=-1; for(i=0;inum-1;i+)for(i=0;inum-1;i+) min1=min2=MAXVALUE;min1=min2=MAXVALUE; x1=x2=0;x1=x2=0;接着选取最小接着选取最小 x1x1 和次小和次小 x2x2 的两权值的两权值 for(j=0;jnum+i;j+)for(j=0;jnum+i;j+) if(HuffNodej.parent=-if(HuffNodej.parent=-1&HuffNodej.weightmin1

29、)1&HuffNodej.weightmin1) min2=min1;min2=min1; x2=x1;x2=x1; min1=HuffNodej.weight;min1=HuffNodej.weight; x1=j;x1=j; elseelse if(HuffNodej.parent=-if(HuffNodej.parent=-1&HuffNodej.weightmin2)1&HuffNodej.weightnum+i;/HuffNodex1.parent=total-num+i;/修改亲人结点位置修改亲人结点位置 HuffNodex2.parent=total-nu

30、m+i;HuffNodex2.parent=total-num+i; HuffNodetotal-HuffNodetotal-num+i.weight=HuffNodex1.weight+HuffNodex2.weight;num+i.weight=HuffNodex1.weight+HuffNodex2.weight; 最后选出的左最后选出的左孩子比右孩子权值小孩子比右孩子权值小 HuffNodetotal-num+i.lchild=x1;HuffNodetotal-num+i.lchild=x1; HuffNodetotal-num+i.rchild=x2;HuffNodetotal-nu

31、m+i.rchild=x2; 哈夫曼树构建成功哈夫曼树构建成功在建立的哈夫曼树基础上，利用数组使左分支为在建立的哈夫曼树基础上，利用数组使左分支为 0 0，右分支为，右分支为 1 1，从叶结点向上，从叶结点向上直到根结点建立哈夫曼编码，并保存每个叶结点起始位。该函数利用了直到根结点建立哈夫曼编码，并保存每个叶结点起始位。该函数利用了 whilewhile的循环并多次利用的循环并多次利用 forfor 循环以完成目标循环以完成目标voidvoid HaffmanCode(HNodetypeHaffmanCode(HNodetype HuffNode,HCodetypeHuffNode,HCode

32、type HuffCode,TotalHuffCode,Total *total)*total) intint i,j,c,p;i,j,c,p; HCodetypeHCodetype cd;cd; for(i=0;inum;i+)/for(i=0;inum;i+)/建立叶子结点个数的编码建立叶子结点个数的编码 cd.start=total-num-1;/cd.start=total-num-1;/起始位的初始化起始位的初始化 p=HuffNodei.parent;p=HuffNodei.parent; c=i;c=i; while(p!=-1)/while(p!=-1)/从叶结点向上爬直到到达

33、根结点从叶结点向上爬直到到达根结点 if(HuffNodep.lchild=c)/if(HuffNodep.lchild=c)/左分支都为左分支都为 0 0 cd.bitcd.start=0;cd.bitcd.start=0; elseelse cd.bitcd.start=1;/cd.bitcd.start=1;/右分支都为右分支都为 1 1 cd.start-;/cd.start-;/起始位向前移动起始位向前移动 c=p;c=p; p=HuffNodep.parent;p=HuffNodep.parent; for(j=cd.start+1;jnum;j+)for(j=cd.start+1

34、;jnum;j+)/保存求出的每个叶结点编码和起始位保存求出的每个叶结点编码和起始位 HuffCodei.bitj=cd.bitj;HuffCodei.bitj=cd.bitj; HuffCodei.start=cd.start;HuffCodei.start=cd.start; 哈夫曼编码的建立成功哈夫曼编码的建立成功利用文件的输入输出规则打开利用文件的输入输出规则打开 HCodeHCode 文件，打开失败则结束操作，否则将信息文件，打开失败则结束操作，否则将信息利用数组及利用数组及 forfor 循环写进文件循环写进文件voidvoid writing_HCode(HNodetypewri

35、ting_HCode(HNodetype HuffNode,HCodetypeHuffNode,HCodetype HuffCode,TotalHuffCode,Total *total)*total) intint i,j;i,j; ofstreamofstream outfile(c:HCode.txt,ios:in|ios:out);outfile(c:HCode.txt,ios:in|ios:out); if(!outfile)/if(!outfile)/打开失败则结束并输出打开失败则结束并输出 coutcout打开打开 c:HCode.txtc:HCode.txt 文件失败文件失败e

36、ndl;endl; exit(1);exit(1); for(i=0;inum;i+)/for(i=0;inum;i+)/写文件写文件 outfile.put(HuffNodei.data);outfile.put(HuffNodei.data);outfileoutfile ; for(j=HuffCodei.start+1;jnum;j+)for(j=HuffCodei.start+1;jnum;j+) outfileHuffCodei.bitj;outfileHuffCodei.bitj; outfileendl;outfileendl; coutcout编码规则写进文件成功编码规则写进

37、文件成功endl;endl; outfile.close();/outfile.close();/关闭文件关闭文件 void lock(Message *message,HNodetype HuffNode,HCodetype HuffCode,Total *total,Locking *locking) int i,j,m; for(i=0;inum;i+)/遍历信息 if(message-mesi= )/碰到空格则以-1 形式保存进 locked 数组中 locking-lockedlocking-num=-1; locking-num+; else for(j=0;jnum;j+)/搜索

38、信息对应的编码 if(HuffNodej.data=message-mesi) for(m=HuffCodej.start+1;mnum;m+) locking-lockedlocking-num=HuffCodej.bitm;locking-num+;/locked 数组总数加 1 /给文件信息加密编码void writing_lock(Locking *locking) int i; ofstream outfile(c:locking.txt,ios:in|ios:out); if(!outfile)/打开失败则结束 cout打开 c:locking.txt 文件失败endl; exit

39、(1); for(i=0;inum;i+)/写文件 if(locking-lockedi=-1) outfile.put( ); else outfilelockedi; cout已编码信息写进文件成功endl; outfile.close();/关闭文件/将哈夫曼编码后的密文信息写进文件void writing_translate(Locking *locking,HCodetype HuffCode,HNodetype HuffNode,Total *total) int i,j,mark100,start100,min,max; ofstream outfile(c:translate.

40、txt,ios:in|ios:out);/打开文件 if(!outfile)/打开失败则结束 cout打开 c:translate.txt 文件失败endl; exit(1); for(i=0;inum;i+)/start 数组初始化 starti=HuffCodei.start+1; for(i=0;inum;i+)/mark 数组初始化 marki=1; min=0; for(max=0;maxnum;max+)/写文件 if(locking-lockedmax=-1)/碰到空格信息则直接输出空格 outfile.put( ); min+; else for(i=min;i=max;i+)/查找从 min 开始到 max 的编码对应的信息 for(j=0;jnum;j+) if(startj=total-num+1) markj=0;/对应编码比所给编码短则不在比较 if(markj=1&locking-lockedi=HuffCodej.bitstartj) startj+; else markj=0; for(i=0;inum;i+)/