上学期学的数据结构，当时老师给的题目是：
从一文件中读取字符，分别统计该文件中英文字符ABCD...等26个字母出现的概率，并以各自的概率为权值，为26个字符建立一棵赫夫曼树，并对每个字符进行哈弗曼编码和哈弗曼解码。
当时课堂检测时老师要求文件内容为ＡＡＡＡＡＢＢＢＣＤＦＧ（反正就是某一个字母频率高，其他很多字母缺失），结果我的代码运行之后就出现阶梯一样的编码结果。老师说我代码哪里错了。可是这两天我重新编码（主要是当初的代码没备份，电脑硬盘坏过一次换了资料都没了），发现结果还是这样的奇怪的阶梯。然后我才想明白哈弗曼树的目的是树的带权长度最小，那么没有出现过的字母权都是０，所以它们的编码长度是没有意义的。出现这样的结果应该是正常的。如果一定要纠结这个问题，应该再写一部分判断权是否为０，只统计并记录权为非０的字母。这里只附上目前的代码（没加判断权为０的这部分，往后看有空再加，这两天要复习，就先不玩了）。
#include
#include
#include
#include
#define N 555
#define M 26
typedef struct Node{
float weight; //权值
int parent; //父节点的序号，为0的是根节点
int lchild,rchild; //左右孩子节点的序号，为0的是叶子节点
}HTNode,*HuffmanTree; //用来存储赫夫曼树中的所有节点
typedef char **HuffmanCode; //用来存储每个叶子节点的赫夫曼编码
void select_minium (HuffmanTree &HT , int i ,int * min1 , int * min2){
int j=0;int temp;
for (; j <= i;j ++){
if(HT[*min1].parent) //min1对应的父节点必须为0
(*min1)=j;
else
if(HT[*min2].parent || *min1==*min2)//min2对应的父节点必须为0且min1min2不相等
(*min2)=j;
else
if (HT[*min2].weight
temp=*min2;
*min2=*min1;
*min1=temp;
}
else if(!HT[j].parent){
if (HT[j].weight <= HT[*min1].weight){
//权值比最小的还小或相等时，将此时的min1赋给min2,此时的哈弗曼结点序号付给min1.
*min2 = *min1;
*min1 = j;
}
else if (HT[j].weight < HT[*min2].weight )
//权值比min1的大,但比min2的小，只需改变min2。。。。。。..
*min2 = j;
}
}
}
HuffmanTree create_HuffmanTree(float *wet,int n,HuffmanTree &HT){
//一棵有n个叶子节点的赫夫曼树共有2n-1个节点
int total = 2*n-1;
HT = (HuffmanTree)malloc((total)*sizeof(HTNode));
if(!HT){
printf("HuffmanTree malloc faild!");
exit(-1);
}
int i;
//HT[0..n-1]中存放需要编码的n个叶子节点
for(i=0;i
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].weight=*wet;
wet++;
}//HT[n..2n-2]中存放的是中间构造出的每棵二叉树的根节点
for(;i
int min1=0;
int min2=0;
//用来保存每一轮选出的两个weight最小且parent为0的节点
//每一轮比较后选择出min1和min2构成一课二叉树,
//最后构成一棵赫夫曼树
select_minium(HT, i, &min1, &min2);//选出两个weight最小且parent为0的节点min1,min2
HT[min1].parent=i;
HT[min2].parent=i;
HT[i].lchild=min1;
HT[i].rchild=min2;
//这里左孩子和右孩子可以反过来，构成的也是一棵赫夫曼树，只是所得的编码不同
HT[i].weight=HT[min1].weight + HT[min2].weight ;
HT[i].parent =0;
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, float *wet ,int n){
printf("\nHuffmanCoding...\n");
//用来保存指向每个赫夫曼编码串的指针
HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
if(!HC){
printf("HuffmanCode malloc faild!");
exit(-1);
}
int i, start, c, f;
for(i = 0; i <= M; i++)
HC[i] = (char *)malloc((M +1)* sizeof(char));
//临时空间，用来保存每次求得的赫夫曼编码串
char cd[M]={0};
if (!cd){
printf("code malloc faild!");
exit(-1);
}
cd[n-1] = '\0'; //编码结束符，亦是字符数组的结束标志
//求每个字符的赫夫曼编码
for (i = 0; i < n; ++ i){//逐个字符求哈弗曼编码
start = n -1 ;//编码结束符的位置
for (c = i, f = HT[i].parent;f != 0; c =f, f = HT[f].parent)
//从叶子到跟逆向求哈弗曼编码
if (HT[f].lchild == c )
cd[ -- start] = '0';//左孩子则为0
else
cd[ -- start ] = '1';//右孩子为1
HC[i] = (char *)malloc((n - start+1) * sizeof (char ));//为第i个字符编码分配空间
strcpy(HC[i],&cd[start]);//从cd复制编码串到HC
printf("字母%c 的哈弗曼编码为 %s\n",'A'+i,HC[i]);
}
//free ( cd );
}//HuffmanCoding
void Read_File(char str[N]){//读取文件内容，并将文件中的字符串放在字符数组str[N]中
FILE *fp;
if((fp=fopen("E:\\VSProjects\\HuffmanTree\\Huffuman\\text.txt","rt"))==NULL){
printf("\nConnot open file!");//如果打开不成功则显示不能打开文件
getchar();
exit(1);//关闭所有文件，终止正调用的过程
}
fgets(str,N,fp);
printf("文件内容：\n");
printf("\n%s\n\n",str);
}
void Count(int Cnt[M], float wet[M], char str[N]){
//统计str中ABCD...出现的次数放在Cnt[M]中，计算频率作为权值放在wet[M]中
int i,all_number;
all_number=0;
for (i=0;i
Cnt[i]=0;//计数初值赋值0
for (i=0;str[i] != '\0';i++){
Cnt[str[i]-'A']++;
all_number++;
}//统计各个字母出现次数
for (i=0;i
wet[i]= ((float)Cnt[i])/all_number;
}//计算频率作为权值放在wet[M]中
//打印输出各个字母的出现次数和权值
for (i = 0 ; i < M ; i ++){
printf("字母%c 出现的次数是 %d ,权值为 %f \n", 'A' + i, Cnt[i] ,wet[i]);
}
}
void decode(HuffmanTree &HT ){//依次读入电文，根据哈夫曼树译码
int i,j=0;
char ch[N];
i=2*M-1-1; //从根结点开始往下搜索
printf("输入发送的编码：");
gets(ch);
printf("译码后的字符为");
while(ch[j]){
if(ch[j]=='0')
i=HT[i].lchild; //走向左孩子
else
i=HT[i].rchild; //走向右孩子
if(HT[i].lchild==0) { //tree[i]是叶结点
printf("%c",'A'+i);
i=2*M-1-1; //回到根结点
}
j++;
}
printf("\n");
}//decode
void main ( void ){
char str[N];//文件中的字符串放在字符数组str[N]中
int Cnt[M];//统计各个字母出现次数放在数组Cnt[M]中
float wet[M];//频率作为权值放在wet[M]中
HuffmanTree HT[2*M-1];//哈弗曼树的结点，一共有2*M -1=51个
HuffmanCode HC[M];//哈弗曼编码
Read_File(str);
//读取文件内容，并将文件中的字符串放在字符数组str[N]中
Count(Cnt, wet, str);
//统计str中ABCD...出现的次数放在Cnt[M]中，计算频率作为权值放在wet[M]中
create_HuffmanTree(wet, M, *HT );//创建哈弗曼树
HuffmanCoding(*HT, *HC, wet , M);//哈弗曼编码
decode( *HT );//哈弗曼译码
}
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
