数据结构课程设计报告哈夫曼编码Word格式.docx

1、宿舍12.14-12.184调试与测试12.18-12.215撰写课程设计报告12.21-12.23二、应收集的资料及主要参考文献1严蔚敏，吴伟民数据结构：C语言版北京：清华大学出版社，19972 耿国华数据结构北京：高等教育出版社，20053 姚伯元课程设计（论文）规范化管理与培养学生综合素质中国高等教育网教学研究，20054 严蔚敏，陈文博编著.数据结构及应用算法教程.北京：清华大学出版社，20015 苏仕华编著.数据结构与算法分析.合肥：中国科技大学出版社，20046 苏仕华等著.数据结构课程设计.北京：机械工业出版社，2005发出任务书日期： 20010 年 11 月 20 日 指导教

2、师签名：计划完成日期： 20010 年 12 月 23 日 教学单位责任人签章：摘要 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成

3、，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出

4、来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 目录1、设计目的 12、需求分析 12.1选题的意义及背景 12.2 输入/输出形式和输出值的范围 23、概要设计 23.1设计思想 23.2函数间的关系 24、详细设计 24.1哈夫曼的主要结构 24.1.1结构定义： 24.1.2主要函数声明及功能描述如下 34.2源程序 44.2.1头文件head.h 44.2.2源文件source.cpp 55、程序测试结果 136、总结 157、参考文献 15 1、设计目的 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。

5、因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。 在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。 数据结构课程主要是研究非数值计

6、算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过此次课程设计主要达到以下目的：1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科 学的工作方法和作风。2、需求分析2.1选题的意义及背景锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力

7、和成员间的配合，提高程序编写能力。在信息传递时，希望长度能尽可能短，即采用最短码。赫夫曼编码的应用，就是采用这种有效的数据压缩技术可以节省数据文件的存储空间和计算机网络的传送时间。2.2 输入/输出形式和输出值的范围 输入信息以加载存档的reading.txt文件为方式，加载不成功，提示出错信息，加载成功后，系统对其编码，并按照选择对各种相关信息存档。 3、概要设计3.1设计思想 哈夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。3.2函数间的关系哈夫曼系统，函数间的关系如图所示： 3-1哈夫曼编码问题中函数间的关系 4、详细设计4.1哈夫曼的主要结构 4.1.1结构定义：#define

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

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

10、*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）;将编码规则写进文件void loc

11、k（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.2源程序 4.2.1头文件head.h /从文件中读取信息/将信息写进文件/统计信息中各字符的次

12、数/构建哈夫曼树/建立哈夫曼编码/将编码规则写进文件/给文件信息加密编码/将已编码信息写进文件/将已编码信息翻译过来并写进文件4.2.2源文件source.cpp#includehead.h#includefstreamusing namespace std;int main（） int i,j,choice,mark=0;/mark标记文件信息是否读入到内存中 HNodetype HuffNode500;/保存哈夫曼树中各结点信息 HCodetype HuffCode300; Locking *locking; Total *total; Message *message; locking=

13、new Locking; locking-num=0; total=new Total; total- message=new Message; message- /初始化变量 while（1） cout*;*1:从文件读取信息 2:显示编码规则 3:将原文件信息写进文件 *coutchoice; switch（choice） case 1: reading_file（message）; mark=1; break; case 2:/显示编码规则 if（mark=0）cout请先从文件中读取信息! else total_message（message,total）;/统计信息中各字符的出现次数

14、 HaffmanTree（total,HuffNode）; HaffmanCode（HuffNode,HuffCode,total）; for（i=0;inum;i+）/显示编码规则 toti.data for（j=HuffCodei.start+1;ji+） if（locking-lockedi=-1）coutlockedi;toti.numnum）-1;HuffNodei.parent return 0;void reading_file（Message *message） /*打开reading文件，失败则结束。不断读取字符并保存进message数组中， 直到遇到#结束，记录字符总数*/

15、 int i=0; char ch; ifstream infile（c:reading.txt,ios:in|ios:out）; if（!infile）/打开失败则结束打开c:reading.txt文件失败读取文件成功 while（infile.get（ch） & ch!=#）/读取字符直到遇到#mesi=ch; i+;num=i;/记录总字符数 infile.close（）;/关闭文件/从文件中读取信息void writing_file（Message *message）/将信息写进文件/*打开writing文件，失败则结束。将信息写进文件*/ int i; ofstream outfil

16、e（writing.txt/打开文件outfile）/打开失败则结束 couti+）/写文件 outfile.put（message-mesi）;信息写进文件成功 outfile.close（）;/将原信息写入文件void total_message（Message *message,Total *total） /*将message中的字符种类及出现次数统计保存到total数组中，重复字符用mark标记， 否则新建字符种类。记录下字符种类的个数*/ int i,j,mark;i+）/遍历message中的所有字符信息 if（message-mesi! ）/字符不为空格时 mark=0; for

17、（j=0;j+）/在total中搜索当前字符 if（total-totj.data=message-mesi）/搜索到，则此字符次数加1，mark标志为1totj.num+; if（mark=0）/未搜索到，新建字符种类，保存进total中，字符类加1 total-tottotal-num.data=message-mesi;num.num=1;num+;/统计信息中各字符的出现次数void HaffmanTree（Total *total,HNodetype HuffNode） /*通过每次选取最小和次小两权值建立二叉树，最终构建成哈夫曼树， 且左孩子权值比右孩子小*/ int i,j,min1,min2,x1,x2;