哈夫曼树的应用课程设计.doc-资料库

supertao_2009-2122175-4744302542998435255.doc.pdf-第1页.png

第1页 / 共24页

supertao_2009-2122175-4744302542998435255.doc.pdf-第2页.png

第2页 / 共24页

supertao_2009-2122175-4744302542998435255.doc.pdf-第3页.png

第3页 / 共24页

supertao_2009-2122175-4744302542998435255.doc.pdf-第4页.png

第4页 / 共24页

supertao_2009-2122175-4744302542998435255.doc.pdf-第5页.png

第5页 / 共24页

supertao_2009-2122175-4744302542998435255.doc.pdf-第6页.png

第6页 / 共24页

supertao_2009-2122175-4744302542998435255.doc.pdf-第7页.png

第7页 / 共24页

supertao_2009-2122175-4744302542998435255.doc.pdf-第8页.png

第8页 / 共24页

学号：课程设计哈夫曼树的应用题目教学院专业班级姓名指导教师年月日

课程设计（论文）课程设计任务书 2009 ～2010 学年第 1 学期学生姓名：指导教师：专业班级：工作部门：一、课程设计题目：哈夫曼树应用二、课程设计要求： 1) 从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树并将它存于文件 hfmTree 中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上； 2) 利用已经建好的哈夫曼树（如不在内存，则从文件 htmTree 中读入），对文件 Text.txt 中的正文进行编码，然后将结果存入文件 Code.txt 中。 3) 利用已建好的哈夫曼树将文件 Code.txt 中的代码进行译码，结果存入文件 Text.txt 中，并输出结果。三、进度安排 1．分析问题，给出数学模型，选择数据结构。 2．设计算法，给出算法描述，给出源程序清单。 3．编辑、编译、调试源程序，撰写课程设计报告。四、基本要求 1.界面友好，函数功能要划分好 2.总体设计应画一流程图 3.程序要加必要的注释 4.要提供程序测试方案 5.程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 1

课程设计（论文）目录 1 引言.............................................................................................................................3 1.1 设计要求................................................................................................................. 3 2 哈夫曼树的介绍.............................................................................................................3 2.1 定义......................................................................................................................... 3 2.2 基本术语................................................................................................................. 4 2.3 哈夫曼树的构造..................................................................................................... 4 3 问题分析.........................................................................................................................4 3.1 相关技术................................................................................................................. 4 3.2 需求分析................................................................................................................. 5 4 系统框架.........................................................................................................................5 4.1 系统框架................................................................................................................. 5 4.2 功能模块说明......................................................................................................... 6 5 哈夫曼树函数代码.........................................................................................................7 6 程序的调试运行...........................................................................................................19 7 心得体会.......................................................................................错误！未定义书签。参考文献...........................................................................................................................22 2

课程设计（论文） 1 引言本课程设计旨在熟悉与了解哈夫曼树的建立以及其应用--哈夫曼的编码和译码的实现。我们要对文本字母个数进行统计，进而建立哈弗曼树，利用建立好的哈弗曼树对文本进行编码，将编码文件保存；打开编码文件，利用哈弗曼树进行译码，将译码后文件存入文件，再比较原文件和译码文件是否一致来检查自己的程序的正误。 1.1 设计要求 1．从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树并将它存于文件 hfmTree 中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上； 2．利用已经建好的哈夫曼树（如不在内存，则从文件 htmTree 中读入），对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中，并输出结果，将文件 CodeFile 以紧凑格式先是在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrint 中。 3．利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFi 中。 2.1 定义 2 哈夫曼树的介绍给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。 3

课程设计（论文） 2.2 基本术语 2.2.1 路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L-1。 2.2.2 结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 2.2.3 树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL。[1] 2.3 哈夫曼树的构造假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设为 w1,w2,…,wn,则哈夫曼树的构造规则为： (1) 将 w1,w2,…,wn 看成是有 n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。 3 问题分析 3.1 相关技术 Visual C++与 C++不同，C++是由 C 语言发展而来的，既可以用于面向过程的 4

课程设计（论文）结构化程序设计，也可以用于面向对象的程序设计,是一门功能强大的程序设计语言。而 Visual C++是一个功能强大的可视化软件开发工具，自 1993 年 Microsoft 公司推出 Visual C++1.0 后，随着其新版本的不断问世，Visual C++已成为专业程序员进行软件开发的首选工具。 Visual C++6.0是 Microsoft 公司在1998年推出的基于 Windows 9X 和 Windows NT 一个优秀集成开发环境。该开发环境为用户提供了良好的可视化编程环境，程序员可以利用该开发环境轻松地访问 C++源代码编辑器、资源编辑器和使用内部调试器，并且可以创建项目文件。Visual C++6.0不仅包括编译器，而且它还包括许多有用组件，如程序向导 AppWizard、类向导 Class Wizard 等，通过这些组件的协同工作，可以在 VisualC++6.0集成开发环境中轻松的完成创建源文件、编辑资源，以及对程序的编译、连接和调试等各项工作。 3.2 需求分析在通信过程中，为了提高信道利用率，缩短信息传输时间降，降低传输成本，一般需要一些编码译码器。而哈夫曼的编码译码具有编和译的双向功能,即在发送端通过编码系统对传入的数据进行编码,在接受端将数据译码.将具有这两项功能的编译码器用于双工信道,就可满足双工信道的双向编译功能.在输入某段报文时,系统将自动完成编译输出.这样就大大方便了许多。 4 系统框架 4.1 系统框架对系统进行分析，给出系统结构图。如图3.1 5

课程设计（论文）哈夫曼树译码器哈夫曼树构造及编译退出哈夫曼树译码继续图 3.1 系统流程图 4.2 功能模块说明（1）.编码：提示要编码的文件文件名→读取文件→以字母出现次数为权值建立哈弗曼树→对文本进行哈弗曼编码并输出编码→提示将编码保存的文件名→保存编码文件；（2）.译码：提示输入要译码的文件名→利用建立好的哈弗曼树进行译码→将译码输出→提示保存译码文件的文件名→保存译码文件； 6

（3）.退出：退出系统，程序运行结束。课程设计（论文） 5 哈夫曼树函数代码 #include #include typedef struct hfmtree { char data;//值 int weight;//权 struct hfmtree *parent,*lchild,*rchild;//双亲，左孩子，右孩子 }hfmtree; main() { hfmtree* huffmancoding(hfmtree *hf,int i,int *wei,char *da);//构造赫夫曼树 void treeprin(hfmtree *hf);//将赫夫曼树的图存放在 c:\\treeprint.txt 文件中 void Printcode(hfmtree *hf);//打印代码文件 void storage(hfmtree *hf);//将赫夫曼树储存到 hfmtree.txt 文件中 void Storedcode(hfmtree *hf);//进行编码操作，并将结果存放到 c:\\code file.txt 中,要进行翻译的文件存放在 c:\\tobetran.txt; void coding(hfmtree *hf)//进行译码 hfmtree *hf; int i,j,*wei,flag1=1,flag2=1; char *da,ch;//分别记录值以及权值 FILE *fp;//用来判断必备的文件是否存在 printf("由于是第一次进行赫夫曼树构造所以必须进行初始化操作 \n");//********************************************************** 7

资料库

哈夫曼树的应用课程设计.doc

相关推荐

课程资源

热门标签

最新资料