《数据结构》综合性实验教学大纲范本.doc

《《数据结构》综合性实验教学大纲范本.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》综合性实验项目教学大纲(DataStructure)实验项目名称：哈夫曼编码/译码器计划学时：4学时所涉及相关课程：《软件工程》、《C语言程序设计》课程类型：专业课一、实验目的与要求目的：通过实验，可使学生深刻理解逻辑结构、存储结构的特性，培养实际问题分析能力。通过编写算法，掌握的程序设计方法和技术，为开发计算机软件打下良好的基础。要求：熟悉VC++的编程和调试环境，根据实验内容和要求，认真完成程序编写、上机调试、运行结果分析，书写实验报告。二、实验内容提要Huffman编码是最优变长码，请设计一个Huffman编码程序，实现以下功能：1、接收原始数据：从终端读入字符集

2、大小n，以及n个字符和权值，建立Huffman树，并将它存入文件hfmtree.dat中。2、编码：利用已建立的Huffman树，对文件中的正文进行编码，将结果存入文件codefile.dat中。3、译码：利用已建立的Huffmar树将codefile.dat中的代码进行译码，结果存入文件textfile.dat中。4、打印编码规则：即字符与编码之间的一一对应关系。5、打印Huffman树：将已存入内存中的Huffman树以直观的方式显示在终端上。三、实验步骤及结果测试Huffman编码是一种最优变长码，即带权路径长度最小。本实验实现了最简单的一种Huffman编码，可以实现把一个

3、文件中的字符集合进行编码，转换为相应的0/1代码，同时可以把0/1代码进行译码，还原原始文件等功能。实验步骤如下：　　1、数据结构设计每个结点有三个指针域：lchild，rchild，parent，本身字符信息以及相应的权值。在编码类型设计中，为了实现字符与编码的一一对应关系，定义了存放字符域letter和存放二进制代码域bit。具体数据结构类型定义如下：#defineMAXLEAF50/*叶子最多个数*/typedefstructhnode{/*结点类型定义*/charletter;intweight,parent,lchild,rchild;}HuffmanNode;typed

4、efstruct{/*编码类型定义*/charletter,bit[MAXLEAF];intstart;}HCode;2、功能函数设计（1）Huffman树的初始化函数InitHuffman()提供两种建立Huffman树的方法：①ComputerLoading。②ManCreate。当用户选择从文件中读取时，程序调用函数WriteHuffman()以得到树的初始化。（2）建立Huffman树函数HuffmanTree()此算法的基本思想为：①由给定的n个树值{w1,w2,w3,…,wm}，构造m棵由空二叉树扩充得到的扩充二叉树，每一个扩充二叉树只有一个外部结点，它的权值为wi。②

5、在已经构造的所有扩充二叉树中，选到根结点的权值最小和次小的两个，将它们作为左、右子树，构造成一棵新的扩充二叉树，它的根结点的权值为两子树的权值之和。③重复执行步骤②，每次都扩充二叉树的个数减一，当只剩下一棵扩充二叉树时，它是所要构造的Huffman树。（3）编码函数HuffmanCode()从根结点开始，寻找每一个叶子结点，在寻找的过程中，经过左子树时，编码增加“0”，经过右子树时，编码增加“1”，当每一个叶子结点都访问过时，便得到相应的编码。（4）译码函数Hencode()开始时，读入所有的0/1代码入内存，遇过“0”转向左孩子结点，遇到“1”转向右孩子结点，直到遇到叶子结点时，

6、访问该结点时，继续下一组代码转换，直到所有的代码读写结束。（5）查看编码规则函数HshowCode()对已经建立好的Huffman编码，通过此函数以较为直观的方式显示给用户看。首先进行合理性检查，如果树还没有建好，则拒绝显示编码规则。当通过检测后，把能以前建立好的代码打印出即可。（6）对一些字母进行编码函数CharCode()如同上面的查看函数，这里也设计了防错。当条件满足进，把文件中的所有字符读入内存，用上面建立的编码规则进行编码，并把转换后的0/1代码存入文件codefile.dat中。（7）查看已建立的Huffman树函数HuffmanShowTree()当树不为空时，运用相

7、关数学知识，借用C函数库中的图形功能画出树的图形。（8）Huffman树的主选择函数HuffmanMenu()打印所有可供选择的操作。用户可根据需要选择相应的操作，程序再执行相应的功能函数即可。若选择不在此选择范围之内，系统认为是选择了查看编码规则这一函数。3、根据上面的分析再进行编码和结果测试。四、实验条件计算机机房，微型计算机，VisualC++软件。五、考核形式根据应用系统的难易程度、界面是否友好、操作是否方便、程序的正确程度进行打分，满分100分。六、实验报告