10数据结构课程设计报告 哈弗曼编码

数据结构——哈夫曼编码/译码器1数据结构课程设计学院：信息科学与工程学院班级：电科06-1班姓名：学号：0601051224指导教师：杨红梅数据结构——哈夫曼编码/译码器2摘要随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。数据结构——哈夫曼编码/译码器3目录摘要......................................................................................2目录......................................................................................3一.设计目的........................................................................4二.需求分析........................................................................52.1哈夫曼编码/译码器简介......................................52.2需求分析.................................................................5三.概要设计........................................................................63.1问题分析哈夫曼树的定义....................................6四.详细设计........................................................................74.1源代码....................................................................74.2运行结果................................................................22五.调试分析......................................................................23六.小结..............................................................................23数据结构——哈夫曼编码/译码器4一.设计目的数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：一、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；二、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；三、提高综合运用所学的理论知识和方法独立分析和解决问题的能数据结构——哈夫曼编码/译码器5力；四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二.需求分析2.1哈夫曼编码/译码器简介举例说明，先前快速远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。在传送电文时，希望总长尽可能地短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，以减少经费。哈夫曼树就是根据此原理设计出来的一种存储结构。本次要做的哈夫曼编码/译码器的主要功能是：运用二叉树来设计二进制的前缀编码。若给一个文件，先统计文件中每个字符出现的频数，即作为此字符的权值，然后将里面的字符编码成相应的哈夫曼编码；反之，根据哈夫曼译码原理把所给二进制数编译成对应的字符串。2.2需求分析（1）编写相应的源代码。（2）要求能实现编码/译码功能。（3）演示程序以人机对话的形式进行。每次测试显示正确的结果。（4）界面友好，易与操作。数据结构——哈夫曼编码/译码器6三.概要设计3.1问题分析哈夫曼树的定义1、哈夫曼树节点的数据类型定义为：typedefstruct{HuffmanTreeHT;//引用上一个数据类型char*c;//存放将要建立哈夫曼树的字符intlongth;//字符的大小，即开始第一步输入的一个整数HuffmanCodeHC;//存放对应的哈夫编码即对应的01代码}Huffman;2、所实现的功能函数如下（1）intmin(HuffmanTreet,inti)接收原始数据：从终端读入字符集大小n，n个字符和n个权值，建立哈夫曼树，存于文件hfmtree.dat中。供InitHuffman（）函数调用（2）voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)初始化哈夫曼树，处理InputHuffman(HuffmanHfm)函数得到的数据，按照哈夫曼规则建立2叉树。此函数块调用了Select（）函数。（3）voidSelect(HuffmanTreeHT,intend,int*s1,int*s2)把输入的字符按权值从小到大排序，挑出最小权值供HuffmanCoding()调用并且根节点的权值等于他的左右孩子的权值和（4）voidDecoding()编码功能函数：利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入）对文件中的正文进行编码，然后将结果存入文件codefile.dat中。如果正数据结构——哈夫曼编码/译码器7文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。（5）voidDecoding(HuffmanHfm)译码功能函数：利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。（6）voidCode_printing()打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。（7）主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。四.详细设计4.1源代码#includeiostream.h#includeiomanip.h#includestring.h#includemalloc.h#includestdio.h//typedefintTElemType;constintUINT_MAX=1000;typedefstruct{数据结构——哈夫曼编码/译码器8intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;//-----------全局变量-----------------------HuffmanTreeHT;HuffmanCodeHC;int*w,i,j,n;char*z;intflag=0;intnumb=0;//-----------------求赫夫曼编码-----------------------intmin(HuffmanTreet,inti){//函数voidselect()调用intj,flag;intk=UINT_MAX;//取k为不小于可能的值for(j=1;j=i;j++)if(t[j].weightk&&t[j].parent==0)k=t[j].weight,flag=j;t[flag].parent=1;returnflag;}//--------------------slect函数----------------------voidselect(HuffmanTreet,inti,int&s1,int&s2){//s1为最小的两个值中序号小的那个数据结构——哈夫曼编码/译码器9intj;s1=min(t,i);s2=min(t,i);if(s1s2){j=s1;s1=s2;s2=j;}}//--------------算法6.12--------------------------voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCintm,i,s1,s2,start;//unsignedc,f;intc,f;HuffmanTreep;char*cd;if(n=1)return;//检测结点数是否可以构成树m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用for(p=HT+1,i=1;i=n;++i,++p,++w){p-weight=*w;p-parent=0;p-lchild=0;数据结构——哈夫曼编码/译码器10p-rchild=0;}for(;i=m;++i,++p)p-parent=0;for(i=n+1;i=m;++i)//建赫夫曼树{//在HT[1