哈弗曼数据结构-课程设计.doc

目录 TOC \o 1-3 \h HYPERLINK \l _Toc31461摘要 PAGEREF _Toc31461 4 HYPERLINK \l _Toc29264目录 PAGEREF _Toc29264 5 HYPERLINK \l _Toc32587一.设计目的 PAGEREF _Toc32587 5 HYPERLINK \l _Toc10264二.需求分析 PAGEREF _Toc10264 6 HYPERLINK \l _Toc5522.1哈夫曼编码/译码器简介 PAGEREF _Toc552 6 HYPERLINK \l _Toc275182.2需求分析 PAGEREF _Toc27518 6 HYPERLINK \l _Toc10777三.概要设计 PAGEREF _Toc10777 7 HYPERLINK \l _Toc68843.1问题分析哈夫曼树的定义 PAGEREF _Toc6884 7 HYPERLINK \l _Toc11618四.详细设计 PAGEREF _Toc11618 7 HYPERLINK \l _Toc18232 4.1编码函数 PAGEREF _Toc18232 7 HYPERLINK \l _Toc179034.2译码函数 PAGEREF _Toc17903 9 HYPERLINK \l _Toc257444.3运行结果 PAGEREF _Toc25744 10 HYPERLINK \l _Toc31248五.调试分析 PAGEREF _Toc31248 12 HYPERLINK \l _Toc24665六.小结 PAGEREF _Toc24665 12 HYPERLINK \l _Toc2127参考文献 PAGEREF _Toc2127 13  一.设计目的 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。 在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。 数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 二.需求分析 2.1哈夫曼编码/译码器简介 举例说明，先前快速远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。在传送电文时，希望总长尽可能地短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，以减少经费。哈夫曼树就是根据此原理设计出来的一种存储结构。 本次要做的哈夫曼编码/译码器的主要功能是：运用二叉树来设计二进制的前缀编码。若给一个文件，先统计文件中每个字符出现的频数，即作为此字符的权值，然后将里面的字符编码成相应的哈夫曼编码；反之，根据哈夫曼译码原理把所给二进制数编译成对应的字符串。 2.2需求分析 （1）编写相应的源代码。 （2）要求能实现编码/译码功能。 （3）演示程序以人机对话的形式进行。每次测试显示正确的结果。 （4）界面友好，易与操作。 三.概要设计 3.1问题分析哈夫曼树的定义 typedef struct Huffmantree