哈夫曼树及其应用(完美)

1、 数据结构课程设计设计题目： 哈夫曼树及其应用 学 院：计算机科学与技术 专 业：网 络 工 程 班 级：网 络 131 学 号：1308060312 学生姓名：谢 进 指导教师：叶 洁2015年 7 月 12 日设计目的： 赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。1、熟悉树的二叉树

2、的存储结构及其特点。 2、掌握建立哈夫曼树和哈夫曼编码的方法。 设计内容：欲发一封内容为AABBCAB (共长 100 字符,字符包括A 、B 、C 、D 、E 、F六种字符)，分别输入六种字符在报文中出现的次数（次数总和为100）， 对这六种字符进行哈夫曼编码。设计要求：对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长

3、度为WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，WiLi恰好为二叉树上带权路径长度。因此 ，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵赫夫曼树，此构造过程称为赫夫曼编码。设计实现的功能： 1.以二叉链表存储， 2.建立哈夫曼树； 3.求每个字符的哈夫曼编码并显示。 一：赫夫曼树的构造“（1）由给定的n个权值W1，W2，Wn构成n棵二叉树的集合FT1，T2，Tn,其中每棵二叉树Ti中只有一个带权为Wi的根节点，其左右子树均空。 （2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这

4、棵新的二叉树根结点的权值为其左、右子树根结点权值之和； （3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中； （4）重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。” 二：设计概要哈夫曼编译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码 。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。最简

5、单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。（1）其主要流程图如图所示。 开始结点数是否大于-1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I<2*N?I+编码为1结束否否否右子是否为空是是否否是是是 （2） 设计包含的几个方面： 赫夫曼树的建立赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算

6、法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n1次合并，所以共产生n1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的赫夫曼树中一共有2n1个结点，其中n个结点是初始森林的n个孤立结点。并且赫夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n-1的一维数组来存储赫夫曼树中的结点。 赫夫曼编码 要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下： typedet struct char ch; / 存放编码的字符 char bitsN1; / 存放编

7、码位串 int len; / 编码的长度 CodeNode; / 编码结构体类型 字符串的译码 译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。 三、 详细设计（1）赫夫曼树的存储结构描述为： #define N 50 / 叶子结点数 #define M 2*N-1 / 赫夫曼树中结点总数 typedef struct int weight; / 叶子结点的权值 int lchild, rchild, parent; / 左右孩子及双亲指针 HTNode; / 树中结点类型 typedef HTNode HuffmanTreeM+1

8、; 哈弗曼树的算法void CreateHT(HTNode ht,int n) /调用输入的数组ht,和节点数n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i<2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-3276832767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k<=i-1;k

9、+) if (htk.parent=-1) /只在尚未构造二叉树的结点中查找 if (htk.weight<min1) /若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti

10、.lchild=lnode;hti.rchild=rnode; /父节点的左节点和右节点（2）哈弗曼编码void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /根据哈夫曼树求哈夫曼编码 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到树根结点结束循环 if (htf.lchild=c) /处理左孩子结点 hc.cdhc.start-='0' else /处理右孩子结点 hc.cdhc.start-='1&#

11、39; c=f;f=htf.parent; hc.start+; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /输出哈夫曼编码的列表 int i,k; printf(" 输出哈夫曼编码:n"); for (i=0;i<n;i+) /输出data中的所有数据，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /输出所有data中数据的编码 printf("%c&q

12、uot;,hcdi.cdk); printf("n"); void editHCode(HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要进行编码的字符串存入string数组中printf("n输出编码结果:n");for (i=0;stringi!='#'i+) /#为终止标志for (j=0;j<n;j+)if(stringi=htj.data) /循环查找与输入字符相同的编号，相同的就输出

13、这个字符的编码for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk);break; /输出完成后跳出当前for循环（3）哈弗曼译码void deHCode(HTNode ht,HCode hcd,int n) /译码函数char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code); /把要进行译码的字符串存入code数组中while(code0!='#')for (i=0;i<n;i+)m=0; /m为想同编码个数的计数器 for (k=hcdi.

14、start,j=0;k<=n;k+,j+) /j为记录所存储这个字符的编码个数if(codej=hcdi.cdk) /当有相同编码时m值加1m+;if(m=j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已经使用过的code数组里的字符串删除codex=codex+j;（4）主函数void main() int n=26,i; char orz,back,flag=1; char str = 'A', 'B

15、', 'C', 'D', 'E', 'F' ; int fnum = 15, 10, 20, 18, 12, 25 ; /初始化 HTNode htM; /建立结构体 HCode hcdN; /建立结构体 for (i=0;i<n;i+) /把初始化的数据存入ht结构体中 hti.data=stri; hti.weight=fnumi; while (flag) /菜单函数，当flag为0时跳出循环 （5）显示部分源程序： printf("n"); printf(" *");

16、printf("n * 1-显示编码 *"); printf("n * 2-进行编码 *"); printf("n * 3-进行译码 *"); printf("n * 4-退出 *n"); printf(" * *"); printf("n"); printf(" 请输入选择的编号:"); scanf("%c",&orz); switch(orz) case 'a': case 'A': syst

17、em("cls"); /清屏函数 CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); getchar(); system("cls"); break; case 'b': case 'B': system("cls"); CreateHT(ht,n); CreateHCode(ht,hcd,n); printf("请输入要进行编码的字符串(以#结束):n"); editHCode(ht,hcd,n); getchar

18、(); system("cls"); break; case 'c': case 'C': system("cls"); CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf("请输入编码(以#结束):n"); deHCode(ht,hcd,n); getchar(); system("cls"); break; case 'd': case 'D': flag=0; br

19、eak; default: system("cls"); 四、调试结果五.实验总结 1.做这个项目前，应该明确需求，划清功能模块。 A.明确需求，就是明确所做的是什么，有什么要求，有望达成什么样的结果。 B.功能模块，就是确定实现的方法，并将其分而治之，由大化小，各个部分实现，是程序清晰化。 2.确定实现算法，就这个题目来说，是实现哈夫曼编码和译码，那首先就得创建哈夫曼树，创建哈夫曼树是这个题目的核心。创建哈夫曼树，在计算机里是很抽象的，在创建之前，应该手写一遍哈夫曼树的创建过程，以及确定一种编号方式（很重要，后面的编码译码就是对你创建的哈夫曼树的编号的操作。） 在创建的过

20、程中，明确思路和步骤，顺便写出伪代码，便于后续书写。 3.在写编码函数之前，可以先将单个字符编码出来，那样的话，一个字符串编码就只是增加了判断字符是否相等，然后，通过循环将其输出。 4.译码时，应当注意将前面已经译码过的二进制数删除（这里其实是换成字符格式的），以便接下来的字符继续译码。 5.做课程设计时，应该明确一种核心的实现思路，然后每一个功能模块的实现，都围绕这个核心的思路去确定算法，这样，就便于写出每一个模块的具体实现，也便于将其全部联系起来。程序清单：/ hafuman.cpp : 定义控制台应用程序的入口点。/#include "stdafx.h"#includ

21、e<iostream>using namespace std;#include <stdio.h>#include <stdlib.h> /要用system函数要调用的头文件#include<conio.h> /用getch()要调用的头文件#include <string.h>#define N 50 /义用N表示50叶节点数#define M 2*N-1 /用M表示节点总数 当叶节点数位n时总节点数为2n-1#define MAXSIZE 100 struct HTNodechar data; /结点值int weight; /权

22、值int parent; /双亲结点int lchild; /左孩子结点int rchild; /右孩子结点; struct HCodechar cdN; /存放哈夫曼码int start; /从start开始读cd中的哈夫曼码;void CreateHT(HTNode ht, int n) /调用输入的数组ht,和节点数nint i, k, lnode, rnode;int min1, min2;for (i = 0; i<2 * n - 1; i+)hti.parent = hti.lchild = hti.rchild = -1; /所有结点的相关域置初值-1for (i = n;

23、 i<2 * n - 1; i+) /构造哈夫曼树min1 = min2 = 32767; /int的范围是-3276832767lnode = rnode = -1; /lnode和rnode记录最小权值的两个结点位置for (k = 0; k <= i - 1; k+)if (htk.parent = -1) /只在尚未构造二叉树的结点中查找if (htk.weight<min1) /若权值小于最小的左节点的权值min2 = min1; rnode = lnode;min1 = htk.weight; lnode = k;else if (htk.weight<mi

24、n2)min2 = htk.weight; rnode = k;htlnode.parent = i; htrnode.parent = i; /两个最小节点的父节点是ihti.weight = htlnode.weight + htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和hti.lchild = lnode; hti.rchild = rnode; /父节点的左节点和右节点void CreateHCode(HTNode ht, HCode hcd, int n)int i, f, c;HCode hc;for (i = 0; i<n; i+) /根据

25、哈夫曼树求哈夫曼编码hc.start = n; c = i;f = hti.parent;while (f != -1) /循序直到树根结点结束循环if (htf.lchild = c) /处理左孩子结点hc.cdhc.start- = '0'else /处理右孩子结点hc.cdhc.start- = '1'c = f; f = htf.parent;hc.start+; /start指向哈夫曼编码hc.cd中最开始字符hcdi = hc;void DispHCode(HTNode ht, HCode hcd, int n) /输出哈夫曼编码的列表int i,

26、k;printf(" 输出哈夫曼编码:n");for (i = 0; i<n; i+) /输出data中的所有数据，即A-Zprintf(" %c:t", hti.data);for (k = hcdi.start; k <= n; k+) /输出所有data中数据的编码printf("%c", hcdi.cdk);printf("n");void editHCode(HTNode ht, HCode hcd, int n) /编码函数char stringMAXSIZE;int i, j, k;cin

27、 >> ("%s", string); /把要进行编码的字符串存入string数组中printf("n输出编码结果:n");for (i = 0; stringi != '#' i+) /#为终止标志for (j = 0; j<n; j+)if (stringi = htj.data) /循环查找与输入字符相同的编号，相同的就输出这个字符的编码for (k = hcdj.start; k <= n; k+)printf("%c", hcdj.cdk);break; /输出完成后跳出当前for循环

28、void deHCode(HTNode ht, HCode hcd, int n) /译码函数char codeMAXSIZE;int i, j, k, m, x;cin>>("%s", code); /把要进行译码的字符串存入code数组中while (code0 != '#')for (i = 0; i<n; i+)m = 0; /m为想同编码个数的计数器for (k = hcdi.start, j = 0; k <= n; k+, j+) /j为记录所存储这个字符的编码个数if (codej = hcdi.cdk) /当有相同编

29、码时m值加1m+;if (m = j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf("%c", hti.data);for (x = 0; codex - 1 != '#' x+) /把已经使用过的code数组里的字符串删除codex = codex + j;void main()int n = 6, i;char orz, flag = 1;char str = 'A', 'B', 'C', 'D', 'E', 'F' ;int f