数据结构实验第9次课赫夫曼编译码器.ppt

1、二叉树用于编码 设每种字符在电文中出现的次数为wi，其编码长度为li，电文中只有n种字符，则电文的总长度为,电文总长度=,若置wi为叶子结点，li恰为从根到叶子的路径长度，则电文总长度为二叉树上的带权路径长度。设计电文总长度最短的二进制前缀编码的问题，转换为以n种字符出现的频率作权，设计一棵赫夫曼树的问题。,例：已知某系统在通信联络中只可能出现8种字符，其概率分别是：0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11, 试设计赫夫曼编码 归一化处理：W=5, 29, 7, 8, 14, 23, 3, 11，n=8, m=15,建立赫夫曼树和生成赫夫曼编

2、码 一棵有n个叶子结点的赫夫曼树共有2n-1个结点，存储在一个大小为2n-1的一维数组中。 typedef struct unsigned int weight; unsigned int parent, lchild, rchild; HTNode, *HuffmanTree; typedef char *CharPointer; typedef CharPointer *HuffmanCode; *动态分配数组存储赫夫曼编码 注：在赫夫曼树的存储中，没有使用相对位置来描述结点之间的相互关系，而是采用明示的方式来表示.,void HuffmanCoding(HuffmanTree ,HC=(

3、HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char*)malloc(n* sizeof(char); cdn-1=0; for(i=1; i=n; +i) start=n-1; for(c=i, f=HTi.parent; f!=0; c=f, f= HTf.parent) if(HTf.lchild=c) cd- -start=0; elde cd- -start=1; HCi= (char*)malloc(n-start)* sizeof(char); strcpy(HCi, ,第9次课 赫夫曼编/译码器,一、实验目的： 掌握最优二叉树概念，最优

4、二叉树在编码问题中应用。 了解二叉树静态二叉链表的存储方式。 掌握通过文件读入数据的方法。,二、实验内容： 赫夫曼编/译码器,要求： 1.建立赫夫曼树，生成赫夫曼编码， 2.实现编码，利用建立的赫夫曼树，对字符串“THIS PROGRAM IS MY FAVORITE”进行编码 3.实行译码，利用建立好的赫夫曼树，对上述编码进行译码。,测试数据： 字符集和频度 字符 频度 空格 186 A 64 B 13 C 22 D 32 E 103 F 21 G 15 H 47 I 57 J 1 K 5 L 32 M 20 N 57 O 63 P 15 Q 1 R 48 S 51 T 80 U 23 V

5、8 W 18 X 1 Y 16 Z 1,#include #include #include #define MaxWeight 2000 typedef struct char ch; int weigth; CharSet;,typedef struct char ch; int weigth; int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char *HuffmanCode; char ToBeTran100=THIS PROGRAM IS MY FAVORITE; char CodeFile1000;,void ReadC

6、harSet(int ,main() CharSet CharArray100; HuffmanTree HT; HuffmanCode HC; int n,m; ReadCharSet(n,CharArray); n=n+1; HuffmanCoding(HT,HC, CharArray,n,m); Encoding(HC); Decoding(HT,m); return(0); ,void ReadCharSet(int ,void HuffmanCoding(HuffmanTree ,for(i=n+1;i=m;+i) Select(HT,i-1,s1, s2); HTs1.parent

7、=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weigth=HTs1.weigth+HTs2.weigth; ,HC=(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char*)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;+i) start=n-1; for (c=i,f=HTi.parent; f!=0; c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,