数据结构(赫夫曼树的建立) 学位论文.doc

哈夫曼树的建立 数据结构课程设计文档 班 级： 小组组长: 成 员： 指导老师： 第一章 前 言 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 通过此次课程设计主要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 概要设计 数据结构设计 使用树TREE的结构，编造最优二叉树（即哈夫曼树），涉及到主要函数有Inithuffmantree,Destoryhuffmantree,huffmancodeing,Visithuffmantree等，用于在一定时间复杂度内寻找到最佳（最短）路径，节约比较次数。 层次调用关系 在main（）函数中调用哈夫曼树的各种操作函数 ADT描述? Huffman?tree? { ? 数据对象D:?D为带有各自实数W(D)的数据元素的集合 数据关系：D=NULL 则huffmantree不存在D≠NULL?R={H}.H为如下二元 关系：? ???①D中存在唯一根数据元素root,这个元素无前驱。? ???②D-{root}?≠NULL.则存在D-{root}?={D1，Dr}.且D1∧Dr=NULL? ???③若D1?≠NULL?，则D1?中存在唯一元素xr,root,?xr∈H??? ?? 且存在Dr上关系Hr∈H,H=?{root,x1,root,xr,H1,Hr};? ?? ④符合①?②?③的R的组合中，存在一个组合R’使D中所有结点到 root的长度与其权值W(Di)相乘的和最小，此时的D/R集合称为 huffmantree. } 详细设计 编译环境：VC6.0 实现该该程序的主要算法是： 基本操作 Init huffmantree(T) 操作结果：构造一个已知节点和权值的哈夫曼树 Destory huffmantree(T) 条件：huffmantree 已存在 结果：销毁huffmantree huffman coding（T） 条件：huffmantree 已经存在 结果：输出huffman code Visit huffmantree（T) 条件：huffmantree 已经存在 结果：显示huffman tree 一、二叉树的设计 typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; } HTNode,*HuffmanTree; typedef char **HuffmanCode; typedef struct { unsigned int s1; unsigned int s2; }MinCode; 二、主要过程 int main() { int code=0; HuffmanTree HT=NULL; HuffmanCode HC=NULL; unsigned int