哈夫曼编码及译码系统.doc

通达学院 算法与数据结构程序设计 题 目： 哈夫曼编码和译码系统 业 学 生 姓 名 班 级 学 号 指 导 教 师 指 导 单 位 日 期 教师评语 同学出勤率(满勤、较高、一般，较低)，学习态度(端正、较端正、一般、较差)，程序设计基础（好、较好、一般、较差），演示程序(已经、没有)达到了基本要求，算法设计（好、较好、一般），界面友好程度（好、较好、一般），答辩过程中回答问题（准确、较准确、错误率较高），撰写报告格式(规范、一般)、内容（丰满、简单）、表述(清晰、一般、不清楚)，（圆满、较好、基本)完成了课题任务。 教师签名： 年 月 日 成绩评定 备 注 一、题目要求： 题 目 ：哈夫曼编码和译码系统 基本要求： (1) 能输入字符集和各字符频度建立哈夫曼树； (2) 产生各字符的哈夫曼编码，并进行解码。 提高要求： (1) 能设计出简捷易操作的窗口界面； (2) 编码和译码存储在文件中。 二、需求分析： 2.1基本思想 根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是: 初始化:由给定的n个权值{w1, w2,…, wn}构造n棵只有一个根结点的二叉树,从而得到一个二叉树集合F={ T1,T2,…,Tn}; 选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和; 删除与加入:在F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到F中; 重复(2)、(3)两步,当集合F中只剩下一棵二叉树时,这棵二叉树便是哈夫曼树. 2.2存储结构 在由哈夫曼算法构造的哈夫曼树中,非叶子结点的度均为2，根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,其中有n-1个非叶子结点,它们是在n-1次的合并过程中生成的.为了便于选取根结点权值最小的二叉树以及合并操作,设置一个数组HuffmanNode[2n-1]保存哈夫曼树中各结点的信息,数组元素的结点结构如图所示. weight parent lchild rchild inf 图 哈夫曼树的结点结构 其中: weight:权值域,保存该结点的权值; Lchild:指针域,保存该结点的左孩子结点在数组中的下标; Rchild:指针域,保存该结点的右孩子结点在数组中的下标; parent:指针域,保存该结点的双亲结点在数组中的下标. 三、概要设计： 1.我首先创建了两个结构体HTNode和Node，分别来记录哈弗曼树各节点的信息以及叶子节点的信息。 建立六个成员函数，如下图所示： 各功能函数实现如下功能： 1、void CreateWeight(){......} 作用：产生叶子结点的字符和权值。 2、void CreateHuffmanTree(){......} 作用：创建HuffmanTree。 3、void CrtHuffmanNodeCode(){......} 作用：生成叶子结点的编码 4、void CrtHuffmanCode(){......} 作用：生成所有字符的编码 void TrsHuffmanTree( ){......} 作用：解码 6、主函数main() 四、详细设计 void CreateWeight(char ch[],int *s,WeightNode CW,int *p) 其中形参分别表示： char ch[]//存放用户输入的字符串 int *s//字符串ch[]的长度 WeightNode CW//存放叶子节点的信息 int *p//叶子节点的个数 核心功能： 函数通过定义三个变量i，j，k，来控制三个循环，主要是为了遍历字符串，找出叶子节点的字符与权值信息。 void CreateHuffmanTree(Huffman ht,WeightNode CW,int n) 形参表示： Huffman ht//Huffman的一个对象ht WeightNode CW//权值大小 int n//叶子节点的个