数据结构实验报告(实验五).doc.doc

深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 实验：Huffman编码的设计与应用 学院： 计算机与软件学院 专业： 指导教师： 蔡平 报告人： 文成 学号： 2011150259 班级： 5 实验时间： 2012-10-22 实验报告提交时间： 2012-10-29 教务部制 一、实验目的与要求： 目的： 理解树、二叉树的顺序存储结构 2.掌握Huffman树的建立过程 3.掌握运用Huffman树进行编码和解码的过程 要求： 1.熟悉C++语言编程 2.熟练结构体数组函数的使用 实验内容： Problem A: 实验七,Huffman编码的设计与应用 1、问题描述 给定n个权值，根据这些权值构造huffman树，并进行huffman编码，以使得到的平均码长最短的编码。 请正确构造huffman类，将建树和编码函数作为成员函数。请编写主函数模仿编码过程确保类及函数是否能正确工作。 2、算法 1．建huffman树算法 (1)、根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F={T1, T2, …, Tn}，其中每棵二叉树Ti中只有一个带树为Ti的根结点 (2)、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和 (3)、在F中删除这两棵树，同时将新得到的二叉树加入F中 (4)、重复2, 3，直到F只含一棵树为止 2．huffman编码算法 ⑴、从huffman树的每一个叶子结点开始 ⑵、依次沿结点到根的路径，判断该结点是父亲结点的左孩子还是右孩子，如果是左孩子则得到编码0，否则得到编码1，先得到的编码放在后面 ⑶、直到到达根结点，编码序列即为该结点的编码的 ⑷、对所有的叶子结点重复2，3得到编码。 Input ⑴、第一行：测试次数。 ⑵、每个样本分2行： 第一行：数字m表示权值数目； 第二行：m个权值。 Output 每个测试样本按照权值输入先后顺序依次输出权值及编码，每个权值与编码用冒号分隔，且单独成行 Sample Input 2 4 1 3 5 7 5 3 5 4 8 6 Sample Output 1：100 3：101 5：11 7：0 3：100 5：00 4：101 8：11 6：01 实验步骤与过程： 源代码： A： #includeiostream using namespace std; const int MaxValue=1000; const int MaxN=1000; class HuffNode//哈夫曼树的结点 { public: int weight;//权值 int flag;//标记 int parent;//双亲结点下标 int leftChild;//左孩子下标 int rightChild;//右孩子下标 }; class Code//存放哈夫曼编码的数据元素 { public: char bit[MaxN];//数组 int start;//编码的起始下标 int weight;//字符的权值 }; class HuffMan { private: int length; int *weight; HuffNode *hufftree; Code *huffcode; int makeHufftree(int weight[],int n,HuffNode HuffTree[]); int HuffmanCode(HuffNode HuffTree[],int n,Code huffCode[]); public: HuffMan(int n,int wt[]); int Huffcoding(); int showHuff(); }; HuffMan::HuffMan(int n,int wt[]) { int i; length=n; we