数据结构课程设计--数据结构课程设计----Huffman编码.doc

数据结构课程设计-Huffman编码 学号： 姓名：数据结构课程设计 题目： Huffman编码 姓名： 班级： 学号： 指导老师： 日期： 2013年6月24日 前言3课程设计报告5一实验目的5二实验题目：赫夫曼编码71.问题描述72.需求分析7三. 概要设计9四. 详细设计111.设计思想11五. 测试分析16六. 使用说明18七. 测试结果19八. 附录201.源代码202.运行结果25前言 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。 算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。课程设计报告一实验目的数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二实验题目：赫夫曼编码1.问题描述 已知某系统在通信联络中只可能出现8种字符（a,b,c,d,e,f,g,h），其概率分别是:0.06，0.28，0.07，0.09，0.14，0.21，0.03，0.12输入8种字符的概率； 构造赫夫曼树；输出每个字符的赫夫曼编码;2.需求分析赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。树中从根到 每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示 “1”码，取每条路径上的“0”或“1”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式 的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。 假设每种字符在电文中出现的次数为W i ,编码长度为L i ，电文中有n 种字符，则电文编码总长为W i L i 。 若将此对应到二叉树上，W i 为叶节点的权 ，L i 为根节点到叶节点的路径长度。那么，W i L i 恰好为二叉 树上带权路径长度。 因此，设计电文总长最短的二进制前缀编码，就是以n 种子符出现的频率作权，构造一刻赫夫曼树， 此构造过程成为赫夫曼编码。 本演示程序用C+6.0编写，完成赫夫曼树的构造以及赫夫曼编码的设计。（1）输入的形式和输入值的范围：n中字符，其出现的频率（2） 输出的形式： 二进制前缀编码（3） 程序所能达到的功能：设计一颗赫夫曼树，由此得到二进制前缀编码，即赫夫曼编码。（4）测试数据：已知某系统在通信联络中只可能出现8种字符（a,b,c,d,e,f,g,h），其概率分别是:0.06，0.28，0.07，0.09，0.14，0.21，0.03，0.12输入8种字符的概率； 构造赫夫曼树；输出每个字符的赫夫曼编码;三. 概要设计（1）为了实现上述程序功能，需要定义单链表的抽象数据类型：ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。数据关系R： 若D=，则R=，称BinaryTree为空二叉树； 若D，则R=H基本操作：void HuffmanCoding(HuffmanTree&,HuffmanCode&,int)操作结果：求赫夫曼编码void Select(HuffmanTree,int,int*,int*)操作结果：查找权值较小的两个结点void OutputHuffmanCode(HuffmanTree,HuffmanCode,int)操作结果：输出赫夫曼编码（2）本程序包含4个函数： 主函数main() 求赫夫曼编码函数HuffmanCoding();查找权值较小的两个结点函数Select (); 输出赫夫曼编码函数OutputHuffmanCode ()各函数间关系如下： HuffmanCoding()Main Select () OutputHuffmanCode () 四. 详细设计实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。1.设计思想哈夫曼编译码系统的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。在通信中可以采用0和1的不同排列来表示不同的字符，称为二进制编码。而赫夫曼树在数据编码中的应用是数据的最小冗余编码问题他是数据压缩学的基础。若每个字符出现的频率相同，则可以采用等长的二进制编码，频率不同，采用不等长的二进制编码，频率达的字符采用位数较少的编码，频率小的采用位数较多的编码。赫夫曼编码就是一种不等长的二进制编码，而赫夫曼树是一种最优二叉树，它的编码也是一种最优编码。在赫夫曼树中，规定往左编码为0，往右编码为1，则得到叶子节点的编码为从根结点带叶子结点中所有路径中0和1的顺序排列。（1） 设计包含的几个方面：赫夫曼树的构造假设有n个权值，则构造出的赫夫曼树有n个叶子结点。n个权值分别为w1,w2,wn,则赫夫曼树构造规则为：1、将w1,w2,.wn,看成有n棵树的森林。2、在森林中选出两个根结点最小的树合并，作为一棵新树的左右子书，且新树根结点权值为左右子树根结点权值之和。3、从森林中删除选取的两棵树，并将新树加入森林。4、重复2和3步骤，直到森林中只剩一棵树为止赫夫曼编码（1）结点类型typedef struct ElemType elem; unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树（2）其他模块伪码算法void HuffmanCoding(HuffmanTree&,HuffmanCode&,int)（伪码算法）void Select(HuffmanTree,int,int*,int*)（伪码算法）void OutputHuffmanCode(HuffmanTree,HuffmanCode,int)（伪码算法）(3)算法分析设计void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int n);int i,m,s1,s2,start,c,f;char*cd;char chl/元素if(n=1)return;m=2*n-1;HT=new HTNodem+1;for(i=1;i=n;i+)/初始化前n个节点coutchwei;HTi.elem=ch;HTi.weight=wei;HTi.parent=HTi.lchild=HTirchild=0;for(i=n+1;i=m;+i)/初始化后n+1.mHTi.elem=0;HTi.weight=HTi.parent=HTilchild=HTi.rchild=0;for(i=n+1;i=m;+i)/生成n+1.mSelect(HT,i-1,&s1,&s2);/查找权值较小的两个节点HTs1.parent=i;HTs2parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=new char*n+1;cd=new charn;cdn-1=0;for(i=1;i=m;+i)/生成HuffmanCodestart=n-1;for(c=i;f=HTi.parent;f!=0;c=f;f=HTf.parent)if(HTf.child=c)cd-start=0;else cd-start=1;HCi=new charn-start;strcpy(HCi,&cdstart);五. 测试分析在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错，但是若没有定义所引用的相关头文件，必定调试不通过；在执行译码操作时，不知什么原因，总是不能把要编译的二进制数与编译成的字符用连接号连接起来，而是按顺序直接放在一起，视觉效果不是很好。还有就是，很遗憾的是，我们的哈夫曼编码/译码器没有像老师要求的那样完成编一个文件的功能，这是我们设计的失败之处。 通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。 这次课程设计，我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存数据，对文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏，我的程序有了更高的质量。六. 使用说明1.程序名为keshe.exe，运行环境为DOS。程序执行后显示：2.输入要编码的字符种类数为8然后程序显示：3.然后依次输入8个字符及出现比例七. 测试结果1.输入第一个字符与所占比例：a , 62. 输入第一个字符与所占比例：b, 283. 输入第一个字符与所占比例：c, 74. 输入第一个字符与所占比例：d, 95. 输入第一个字符与所占比例：e, 146. 输入第一个字符与所占比例：f, 217. 输入第一个字符与所占比例：g, 38. 输入第一个字符与所占比例：h, 12八. 附录1.源代码 #include#include#include#includetypedef int Status;typedef char ElemType;typedef struct ElemType elem; unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树typedef char*HuffmanCode;/ 动态分配数组存储赫夫曼编码表void HuffmanCoding(HuffmanTree&,HuffmanCode&,int);void Select(HuffmanTree,int,int*,int*);void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);Status main()HuffmanTree HT;HuffmanCode HC;int i,n;/the number of elements;coutn;HuffmanCoding(HT,HC,n);OutputHuffmanCode(HT,HC,n);return 1;void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int n)int i,m,s1,s2,start,c,f;char *cd;char ch;/元素;int wei;/权重;if(n=1)return;m=2*n-1;HT=new HTNodem+1;for(i=1;i=n;+i)/初始化前n个结点coutchwei;HTi.elem=ch;HTi.weight=wei;HTi.parent=HTi.lchild=HTi.rchild=0; for(i=n+1;i=m;+i)/初始化后几个结点n+1.mHTi.elem=0;HTi.parent=HTi.lchild=HTi.rchild=0; for(i=n+1;i=m;+i) /生成n+1.m个结点; Select(HT,i-1,&s1,&s2);/查找权值较小的两个结点 HTs1.parent=i;HTs2.pare