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