实验：Huffman.docVIP

深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： Huffman编码的设计与应用实验 学院： 计算机与软件学院 专业： 网络工程 指导教师： 杨芳 报告人：李楚煌 学号： 2013150383 班级： 8 实验时间： 2014-10-23 实验报告提交时间： 2014-10-24 教务处制 一、实验目的 1、理解树、二叉树的链式存储结构（三叉链表） 2、掌握Huffman树的生成算法 3、掌握运用Huffman树，生成对应字符的Huffman编码算法 4、掌握运用字符的Huffman编码，将一个字符串编码成一串Huffman编码序列方法 5、掌握利用Huffman树（编码），对一串Huffman编码序列进行解码的方法 二、实验要求 熟悉C++语言编程 熟练使用C++语言，实现Huffman编码和解（译）码算法 三、实验内容 本次实验内容：Huffman编码的设计与应用 1、问题描述 给定n个字符及其对应的权值，构造Huffman树，并进行huffman编码和译（解）码。 构造Huffman树时，要求左子树根的权值小于右子树根的权值。 进行Huffman编码时，假定Huffman树的左分支上编码为‘0’，右分支上编码为‘1’。 2、算法 构造Huffman树算法： ⑴、根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F={T1, T2, …, Tn}，其中每棵二叉树Ti中只有一个权值为wi的根结点 ⑵、在F中选取两棵根结点的权值最小的树，作为左、右子树构造一棵新的二叉树，且置其根结点的权值为其左、右子树权值之和 ⑶、在F中删除这两棵树，同时将新得到的二叉树加入F中 ⑷、重复⑵, ⑶，直到F只含一棵树为止 Huffman编码算法： ⑴、从Huffman树的每一个叶子结点开始 ⑵、依次沿结点到根的路径，判断该结点是父亲结点的左孩子还是右孩子，如果是左孩子则得到编码‘0’，否则得到编码‘1’，先得到的编码放在后面 ⑶、直到到达根结点，编码序列即为该叶子结点对应的Huffman编码 Huffman译（解）码算法： ⑴、指针指向Huffman树的根结点，取第一个Huffman码 ⑵、如果Huffman码为‘0’，将指针指向当前结点的左子树的根结点；如果Huffman码为‘1’，将指针指向当前结点的右子树的根结点 ⑶、如果指针指向的当前结点为叶子结点，则输出叶子结点对应的字符；否则，取下一个Huffman码，并返回⑵ ⑷、如果Huffman码序列未结束，则返回⑴继续译码 3、输入 第一行：样本字符个数，假设为n。 第二行，n个字符（用空格隔开） 第三行，n个字符对应的权值（用空格隔开） 第四行，待编码的字符串 第五行，待译码的Huffman码序列 4、输入样本 4 a b c d 9 3 2 6 abcd 111001010 5、输出 第一行，每个字符对应的Huffman编码（用空格隔开） 第二行，字符串对应的Huffman编码序列 第三行，Huffman码序列对应的字符串 6、输出样本 0 101 100 11 010110011 Dcba 四、程序清单 #include iostream usingnamespacestd; #include cstring #define MaxC 15 #define MaxH 10 #define MaxCS 100 voidSelect(inti1,int*s1,int*s2); typedefstruct { charc; intweight; intparent,lchild,rchild; charcode[MaxC]; }HNode,*HTree; HNode HT[2*MaxH]; voidCreateHT(intn,char*c,int*w) { inti,m,s1,s2; m = 2*n - 1;