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

ca516f14-9f01-4cda-bcec-2148019ee094.doc.pdf-第1页.png

第1页 / 共28页

ca516f14-9f01-4cda-bcec-2148019ee094.doc.pdf-第2页.png

第2页 / 共28页

ca516f14-9f01-4cda-bcec-2148019ee094.doc.pdf-第3页.png

第3页 / 共28页

ca516f14-9f01-4cda-bcec-2148019ee094.doc.pdf-第4页.png

第4页 / 共28页

ca516f14-9f01-4cda-bcec-2148019ee094.doc.pdf-第5页.png

第5页 / 共28页

ca516f14-9f01-4cda-bcec-2148019ee094.doc.pdf-第6页.png

第6页 / 共28页

ca516f14-9f01-4cda-bcec-2148019ee094.doc.pdf-第7页.png

第7页 / 共28页

ca516f14-9f01-4cda-bcec-2148019ee094.doc.pdf-第8页.png

第8页 / 共28页

课程设计（论文）课程设计任务书 2010 ～2011 学年第 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 2.需求分析.........................................................................................................4 2.1 哈夫曼编码/译码器简介..................................................................... 4 2.2. 问题描述.............................................................................................4 2.3 需求分析................................................................................................4 3.概要设计.........................................................................................................5 3.1 问题分析哈夫曼树的定义................................................................... 5 4.详细设计.........................................................................................................6 4.1 系统框架图...........................................................................................6 4.2 总体流程图...........................................................................................7 4.3 编码函数................................................................................................8 4.4 译码函数..............................................................................................10 4.5 运行结果..............................................................................................11 5.调试分析.......................................................................................................13 6.小结...............................................................................................................14 参考文献...........................................................................................................15 附录：源程序代码...........................................................................................16 2

课程设计（论文） 1·设计目的数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：一、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；二、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；三、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 3

课程设计（论文） 2.需求分析 2.1 哈夫曼编码/译码器简介举例说明，先前快速远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。在传送电文时，希望总长尽可能地短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，以减少经费。哈夫曼树就是根据此原理设计出来的一种存储结构。本次要做的哈夫曼编码/译码器的主要功能是：运用二叉树来设计二进制的前缀编码。若给一个文件，先统计文件中每个字符出现的频数，即作为此字符的权值，然后将里面的字符编码成相应的哈夫曼编码；反之，根据哈夫曼译码原理把所给二进制数编译成对应的字符串。 2.2. 问题描述 1.从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树并将它存于文件 hfmTree 中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上； 2．利用已经建好的哈夫曼树（如不在内存，则从文件 htmTree 中读入），对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中，并输出结果，将文件 CodeFile 以紧凑格式先是在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrint 中。 3．利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile 中。 2.3 需求分析一个完整的系统应具有以下功能： 1）I：初始化（Initialization）。从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。输出哈夫曼树，及各字符对应的编码。 2）W：输入（Input）。从终端读入需要编码的字符串 s，将字符串 s 存入文件 Tobetran.txt 4

课程设计（论文）中。 3）E：编码（Encoding）与译码（Decoding）。编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件 htmTree 中读入），对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。译码（Decoding）。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile 中。印代码文件（Print）。将文件 CodeFile 以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码写入文件 CodePrint 中。 4）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。 5）Q：退出程序。返回 WINDOWS 界面。 3.概要设计 3.1 问题分析哈夫曼树的定义 typedef struct Huffmantree { char ch; /*键值*/ int weight,mark; /*weight 为权值,mark 为标志域*/ struct Huffmantree *parent,*lchild,*rchild,*next; /*结构指针*/ }Hftree,*linktree; 使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。 5

课程设计（论文） 4.详细设计 4.1 系统框架图对系统进行分析，给出系统结构图。如图4.1 哈夫曼树译码器 z 哈夫曼树构造及编译退出哈夫曼树译码继续图 4.1 系统流程图 6

课程设计（论文） Case2 4.2 总体流程图哈夫曼树算法的总体流程图如图 4.2 void Main（） Switch() Case1 输入叶子节点相关信息 system("cls") 构造哈夫曼编码 void Haffmancode(int n) 构造哈弗曼树 HNodeType *HaffmanTree(int n) break Case 2 Switch() Case 1 译码 void Haffmanfile(int n) 图 4.2 总体流程图 7

课程设计（论文） 4.3 编码函数以下是源程序中实现编码的部分： void Huffmancoding(linktree tree) { */ int index=0; char *code; linktree ptr=tree; code=(char *)malloc(10*sizeof(char)); /*此数组用于统计哈夫曼编码 printf("字符以及它的相应权数---------哈夫曼编码\n\n"); if(ptr==NULL) cout<<"哈夫曼树是空的!\n"; exit(0); { } else { while(ptr->lchild&&ptr->rchild&&ptr->mark==0) { while(ptr->lchild&&ptr->lchild->mark==0) { code[index++]='0'; ptr=ptr->lchild; if(!ptr->lchild&&!ptr->rchild //打印哈夫曼树中的结点 { ptr->mark=1; code[index]='\0'; printf("\tw[%c]=%d\t\t\t",ptr->ch,ptr->weight); for(index=0;code[index]!='\0';index++) printf("%c",code[index]); printf("\n"); ; ptr=tree; 8

资料库

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

相关推荐

课程资源

热门标签

最新资料