1 // haffman.cpp : 定义控制台应用程序的入口点。 2 // 3 4 #include "stdafx.h" 5 #include<iostream> 6 using namespace std; 7 8 typedef struct hfnode 9 { 10 char ch; //存储字符 11 int weight; //存储权值 12 int parent; //双亲结点位置 13 int lchild; //左右孩子结点位置 14 int rchild; 15 } hfnode,*hfmtree; 16 17 typedef struct node 18 { 19 char code[10]; 20 } node,*hfcode; 21 22 #define Nsymbols 10 23 24 hfnode *Inithfm(hfnode *tree,int n) //千万不能用关键字命名。把这些节点作为带权值的二叉树的根节点，左右子树为空 25 { 26 //tree = new hfnode[n]; //多余了，已经在main函数中声明了。 27 for(int i = 0;i < n; i++) 28 { 29 tree[i].ch = '0'; 30 tree[i].weight = 0; 31 tree[i].lchild = 0; 32 tree[i].rchild = 0; 33 tree[i].parent = 0; 34 } 35 cout << "请输入想要编码的字符序列,按照先字符后次数的顺序输入" << endl; 36 for(int i = 0;i < 4; i++) 37 { 38 cin >> tree[i].ch >>tree[i].weight; 39 } 40 cout <<endl; 41 42 for(int i = 0;i < 4;i++) 43 cout << tree[i].ch << " "<<tree[i].weight<<" "; 44 cout << endl; 45 return tree; 46 } 47 48 void select(hfnode *tree,int n,int *p1,int *p2) //选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 49 { 50 //找一个作为参考,返回的是结点 51 int x,y; 52 for(int i = 0;i <= n;i++) 53 { 54 if(tree[i].parent==0) 55 { 56 x = i; 57 break;//找到一个参考点即可 58 } 59 } 60 61 62 for(int i = 0;i <= n;i++) //找出最小的结点 63 { 64 if((tree[i].parent==0)&&(tree[i].weight!=0)) 65 { 66 if(tree[i].weight < tree[x].weight) 67 x = i; 68 } 69 } 70 71 for(int j = 0;j <= n;j++) 72 { 73 if((tree[j].parent==0)&&(j!=x)) 74 { 75 y = j; 76 break;//找到一个参考点即可 77 } 78 } 79 for(int j = 0;j <= n;j++) //找出次小的结点 80 { 81 if((tree[j].parent==0)&&(tree[j].weight!=0)&&j!=x) 82 { 83 if(tree[j].weight < tree[y].weight) 84 y = j; 85 } 86 } 87 *p1 = x; 88 *p2 = y; 89 } 90 //对哈弗曼树进行编码。 91 92 void HfCode(hfnode *tree,int n,node *hfmcode,int m) 93 { 94 int c,f; 95 int start = 0; 96 97 for(int i=0;i<10;i++) 98 { 99 for(c=i,f=tree[c].parent;f!=0;c=f,f=tree[c].parent) //追溯法，从叶子节点出发，一路往上追溯。 100 { 101 if(tree[f].lchild==c) 102 hfmcode[i].code[start++] = '0'; 103 else 104 hfmcode[i].code[start++] = '1'; 105 } 106 start = 0; 107 } 108 } 109 110 void Print(node *hfmcode,int m) 111 { 112 for(int i = 0;i < m;i++) 113 { 114 for(int j = 0;j < m;j++) 115 cout <<hfmcode[i].code[j]; 116 cout << endl; 117 } 118 cout << endl; 119 } 120 121 122 123 int main() 124 { 125 int p1=0,p2=0; //为了接收最小和次小的两个节点 126 hfnode tree[Nsymbols]; //当我们不是用指针，这种情况下，已经全部赋值了。不用再一次赋值了。 127 Inithfm(tree,Nsymbols); //初始化结构体数组。 128 129 //建立哈弗曼树 130 131 for(int m = 4;m < 2*4-1;m++) //二叉树性质 132 { 133 select(tree,m-1,&p1,&p2); 134 tree[p1].parent = m; 135 tree[p2].parent = m; 136 tree[m].lchild = p1; 137 tree[m].rchild = p2; 138 tree[m].weight = tree[p1].weight + tree[p2].weight; 139 tree[m].parent =0; //其实这句也可以不用，因为初始化时已经初始化为0了。 140 } 141 142 node hfmcode[4]; 143 // 初始化，不然打印的时候会出现未知错。 144 for(int i = 0;i < 4;i++) 145 { 146 for(int j = 0;j < 4;j++) 147 hfmcode[i].code[j]=' '; 148 } 149 150 HfCode(tree,Nsymbols,hfmcode,4); //编码函数 151 Print(hfmcode,4); //打印函数 152 return 0; 153 }
实验名称：哈弗曼编码
实验目的：了解前缀编码的概念，理解数据压缩的基本方法；
掌握Huffman编码的设计思想并能熟练应用。
实验要求：对有字符集｛A，B，C，D｝，各字符在电文中出现的次数集为｛1,3,4,7｝；
要求编程实现Huffman树的构造，并在此基础上编程实现Huffman编码。
实验步骤及内容：
1、首先建立一个定义哈弗曼树的结构体Node，及结构体指针LinkList，该结构体包含一个存储字符的ch,存储权值的weight，存储双亲结点的parent，存储左右孩子的lchild与rchild。代码如下：
typedef struct hfnode
{
char ch; //存储字符
int weight; //存储权值
int parent; //双亲结点位置
int lchild; //左右孩子结点位置
int rchild;
} hfnode,*hfmtree;
2、定义一个存储编码的结构体，主要是为了方便打印，代码如下：
typedef struct node
{
char code[10];
} node,*hfcode;
3、初始化函数，因为默认值是一个不确定的值，必须进行初始化才行。
hfnode *Inithfm(hfnode *tree,int n) //千万不能用关键字命名。把这些节点作为带权值的二叉树的根节点，左右子树为空
{
//tree = new hfnode[n]; //多余了，已经在main函数中声明了。
for(int i = 0;i < n; i++)
{
tree[i].ch = '0';
tree[i].weight = 0;
tree[i].lchild = 0;
tree[i].rchild = 0;
tree[i].parent = 0;
}
cout << "请输入想要编码的字符序列,按照先字符后次数的顺序输入" << endl;
for(int i = 0;i < 4; i++)
{
cin >> tree[i].ch >>tree[i].weight;
}
cout <<endl;
for(int i = 0;i < 4;i++)
cout << tree[i].ch << " "<<tree[i].weight<<" ";
cout << endl;
return tree;
}
4、选择两棵根结点权值最小的树作为左右子树。
void select(hfnode *tree,int n,int *p1,int *p2) //选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
{
//找一个作为参考,返回的是结点
int x,y;
for(int i = 0;i <= n;i++)
{
if(tree[i].parent==0)
{
x = i;
break;//找到一个参考点即可
}
}
for(int i = 0;i <= n;i++) //找出最小的结点
{
if((tree[i].parent==0)&&(tree[i].weight!=0))
{
if(tree[i].weight < tree[x].weight)
x = i;
}
}
for(int j = 0;j <= n;j++)
{
if((tree[j].parent==0)&&(j!=x))
{
y = j;
break;//找到一个参考点即可
}
}
for(int j = 0;j <= n;j++) //找出次小的结点
{
if((tree[j].parent==0)&&(tree[j].weight!=0)&&j!=x)
{
if(tree[j].weight < tree[y].weight)
y = j;
}
}
*p1 = x;
*p2 = y;
}
5、构造哈弗曼树
//建立哈弗曼树
for(int m = 4;m < 2*4-1;m++) //二叉树性质
{
select(tree,m-1,&p1,&p2);
tree[p1].parent = m;
tree[p2].parent = m;
tree[m].lchild = p1;
tree[m].rchild = p2;
tree[m].weight = tree[p1].weight + tree[p2].weight;
tree[m].parent =0; //其实这句也可以不用，因为初始化时已经初始化为了。
}
6、对哈弗曼树进行编码。编码函数如下：
//对哈弗曼树进行编码。
void HfCode(hfnode *tree,int n,node *hfmcode,int m)
{
int c,f;
int start = 0;
for(int i=0;i<10;i++)
{
for(c=i,f=tree[c].parent;f!=0;c=f,f=tree[c].parent) //追溯法，从叶子节点出发，一路往上追溯。
{
if(tree[f].lchild==c)
hfmcode[i].code[start++] = '0';
else
hfmcode[i].code[start++] = '1';
}
start = 0;
}
}
7、打印编码
void Print(node *hfmcode,int m)
{
for(int i = 0;i < m;i++)
{
for(int j = 0;j < m;j++)
cout <<hfmcode[i].code[j];
cout << endl;
}
cout << endl;
}
另配上一副自己用画图工具画的理论分析图：
结果与C++代码结果一致。
总结：
此次实验，让我理解了结构体数组的使用以及初始化，内存管理等方面的熟悉，感觉收获挺大的。