管理课件哈夫曼编码实验报告.doc

数据结构实验报告 实验名称： 实验三——哈夫曼编码 学生姓名： 牛佳宁 班 级： 2010211107 班内序号： 27 学 号：日 期： 2011年12月10日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 1、读入一串字符，统计字符个数及权值。 2、建立哈夫曼树。 3、根据哈夫曼树建立哈夫曼表。 4、将字符串进行编码。 5、输入一串01数，进行解码。　 2. 程序分析 2.1 存储结构 哈夫曼树为正则二叉树，有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的数组来储存哈夫曼树的各个结点，如图 weight Lchild RChild parent 2 -1 -1 -1 3 -1 -1 -1 6 -1 -1 -1 9 -1 -1 -1 对应的编码表可用如图所示结构 data code Z 100 C 101 B 11 2.2 关键算法分析 一、创建哈夫曼树 1、根据权值初始化哈夫曼树 for(int i=0;in;i++) { HTree[i].weight=a[i]; HTree[i].LChild=-1; HTree[i].RChild=-1; HTree[i].parent=-1； } 2、开始建立哈夫曼树， int x,y; for (int i=n;i2*n-1;;i++) { selectMin(x,y,o,i);//从1到i选择两个权值最小的 HTree[x].parent=HTree[y].parent=i; HTree[i].weight=HTree[x].weight+HTree[y].weight; HTree[i].LChild=x; HTree[i].parent=-1; } 二、建立哈夫曼编码表 void Huffman::CreateCodeTable(char b[],int n) { HCodeTable=new HCode [n]; for (int i=0;in;i++) { HCodeTable[i].data=b[i];//生成编码表 int child=i; int parent=HTree[i].parent; int k=0; while (parent!=-1) { if(child==HTree[parent].LChild) HCodeTable[i].code[k]=0;//左孩子标‘0’； else HCodeTable[i].code[k]=1;//右孩子标‘1’； k++; child=parent; parent=HTree[child].parent; } HCodeTable[i].code[k]=\0; char*b=new char[k];//将编码字符逆置,再初始化一个数组倒着储存编码数组，再将该数组重新赋给编码数组 for(int j=0;jk;j++) { b[j]=HCodeTable[i].code[k-1-j]; } for(int jj=0;jjk;jj++) { HCodeTable[i].code [jj]=b[jj]; } } } 三、编码函数：根据编码表进行编码，从编码表中第一个开始遍历，若找到要编码的字符则输出编码，并进行下一个字符的查找 void Huffman::Encode(char*s,int n) { while(*s!=\0) { for(int i=0;in;i++) { if(*s==HCodeTable[i].data) { coutHCodeTable[i].code; s++; } } } coutendl; } 四、解码：利用哈夫曼树进行解码，编码串左到右依次逐位判断，从根结点开始根据每一位是0还是1，确定是左分支还是右分支，直到到叶子节点为止，从编码表中找到对应字符并输出 void Huffman::Decode(char*s,char*d,int n)//s为编码串， { while(*s!=\0) { int parent=2*n-1-1;//根节点在HTree中的下标； while(HTree[parent].LChild!=-1) { if(*s==0) parent=HTree[parent].LChild; else parent=HTree[parent].RChild; s++; } *d=HCodeTabl