实验七

《数据结构》课程实验

《数据结构》

实验报告

题目:_二叉树的应用 学号:___01112116____ 姓名: ____戴元潮_____

东南大学成贤学院计算机系

2014年4月24日

1

《数据结构》课程实验

实验题目

一、 实验目的

1. 掌握二叉树的基本运算，运用其解决具体问题。

二、 实验内容

1．哈夫曼码的编/译码系统 设计任务：

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 基本要求：

一个完整的系统应具有以下功能：

（1）初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并对n个字符进行编码，编码结结果存储在文件code中。

（2）编码（Encoding）。利用字符的编码，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。将原文ToBeTran和译文CodeFile的内容显示出来。

（3）译码（Decoding）。利用字符编码将文件CodeFile中的代码进行译码，结果存入文件TextFile中。将原文CodeFile和译文TextFile的内容显示出来。

测试数据：

（1）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。

字符 空格 A B C D E F G H I J K L M

频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 实现提示：

（1） 对于字符集比较大时，也可以将字符集及权值存储在文件中。

（2） 如果文件读写不熟悉，可以采用数组的方式，将数据存储在内存中，但成绩会

降低。

（3） 程序以菜单形式运行。

2. 在实验六基础上设计一个算法，输出二叉树中从根结点到每个叶子结点的路径。

2

《数据结构》课程实验

三、 实验步骤

学生分组完成，每组1-3人，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告，提交可独立运行的程序和规范的课程设计报告。 四、 实验结果

提交可独立运行的程序和规范的课程设计报告，报告内容如下： 一、需求分析

1.问题概述 2.功能需求

二、概要设计

1.主界面设计：设计系统运行时主界面

2.抽象数据类型定义：详细描述系统所定义的抽象数据类型； 3.主程序结构设计：系统主程序的函数构成和调用关系；

三、详细设计

1.抽象数据类型设计：详细描述抽象数据类型的存储结构和操作的算法

实现；

2.主程序算法设计：给出主程序各函数的算法实现。

四、C++语言程序实现：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。

五、程序测试及结果分析：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。给出程序的测试情况，并分析运行结果。

六、经验和体会（包括对算法改进的设想） 七、小组成员分工介绍

3

《数据结构》课程实验

一、需求分析

1.问题概述

用户信息间的保密性。 2.功能需求

将用户所输入的字母进行编码，存入文件，进行传输。接收方收到编码进行译码，从而确保信息的保密性。 二、概要设计

1.主界面设计：设计系统运行时主界面 以菜单形式，进行选择操作。 菜单：

****************************** 欢迎使用赫夫曼编码解码系统 ****************************** (1)初始化赫夫曼链表 (2)编码 (3)译码 (4)打印编码 (5)打印赫夫曼树 (6)打印译码 (7)退出

2.抽象数据类型定义：详细描述系统所定义的抽象数据类型； typedef struct {

int weight,K;

int parent,lchild,rchild; }HTNode,* HuffmanTree;

typedef char **HuffmanCode;

//-----------全局变量----------------------- HuffmanTree HT; HuffmanCode HC; int w[50],i,j,n; char z[50]; int flag=0; int numb=0;

3. 主程序结构设计：系统主程序的函数构成和调用关系；

4