霍夫曼树的问题
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char* *HuffmanCode;
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, * HuffmanTree;
void CreateHuffmanTree(HuffmanTree *HT, unsigned int *w, int n);
void Select(HuffmanTree HT, int i, int *s1, int *s2);
void HuffmanTreeCoding(HuffmanTree HT, HuffmanCode *HC, int n);
void PreOrderTraverse(HuffmanTree HT, int length); //先序遍历
int main(void)
{
int n;
int i;
unsigned int *w;
HuffmanTree HT = NULL; //构造霍夫曼数的头结点
printf("Please enter the leaf's total of HuffmanTree:");
scanf("%d", &n);
w = (unsigned int *)malloc( (n+1) * sizeof(unsigned int) ); //0号单元不用，所以构造n+1个结点
printf("Please enter the leaf's weight value of huffmantree\n");
for(i = 1; i <= n; i++)
{
printf("please enter the value of %d: ",i);
scanf("%d", &w[i]);
}
CreateHuffmanTree(&HT, w, n);
HuffmanCode HC = NULL; //用于存储多个字符串的二级指针
HuffmanTreeCoding(HT, &HC, n); //因为要改变指针变量HC的指向，所以要讲HC的地址传入
for(int i = 1; i <= n; i++)
{
printf("%d : %s\n", w[i], HC[i]);
}
printf("\n");
//PreOrderTraverse(HT, 2 * n);
return 0;
}
void CreateHuffmanTree(HuffmanTree *HT, unsigned int *w, int n)
{
int m;
int i,s1,s2;
HuffmanTree p;
if(n <= 1)
{
printf("parameter is illegal!"); //若结点个数小于等于1，则无法进行树的构造
return ;
}
m = 2 * n - 1; //构造霍夫曼树需要的结点总数
*HT = (HuffmanTree)malloc( (m+1) * sizeof(HTNode) );
//因为0号单元不用，所以m需要加一
p = *HT;
p++; // (*HT)[0]不用
for(i = 0; i <= m; p++, i++)
{
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
p = *HT;
p++;
for(i=1; i<=n; p++, i++)
{
p->weight = w[i];
}//存入权值，便于筛选
for(i = n+1; i <= m; i++)//0号单元未用，以用单元0~n,故 i=n+1
{
Select(*HT, i-1, &s1, &s2);
//从前i-1个分量中选择parent为０，且权值最小的两个结点，并取其下标给s1,s2
(*HT)[s1].parent = i;
(*HT)[s2].parent = i;
(*HT)[i].lchild = s1;
(*HT)[i].rchild = s2;
(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
}
}
void Select(HuffmanTree HT, int i, int *s1, int *s2)
{
int k, j;
HuffmanTree p;
p = HT;
k = 1;
while(HT[k].parent != 0) k++;
*s1 = k;
for(j = 1; j <= i; j++)
{
if( (HT[j].parent == 0) && (HT[j].weight < HT[*s1].weight) )
*s1 = j;
}//寻找权值最小的结点
k = 1;
while( (HT[k].parent != 0) || (k == *s1) ) k++;
*s2 = k;
for(j=1;j<=i;j++)
{
if( (HT[j].parent == 0) && (HT[j].weight < HT[*s2].weight) && (j != *s1) )
*s2 = j;
} //寻找次小的结点
}
void HuffmanTreeCoding(HuffmanTree HT, HuffmanCode *HC, int n)
{
int i,start;
unsigned int c,f;
char *cd = NULL;
*HC = (HuffmanCode)malloc(n * sizeof(char *)); //构造字符指针类型的数组
cd = (char *)malloc(n * sizeof(char)); //用于存储霍夫曼编码
cd[n-1] = '\0'; //末尾赋值字符串结尾标志
for(i = 1; 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';
else
cd[--start] = '1';
}
(*HC)[i] = (char *)malloc( (n-start) * sizeof(char) );
strcpy( (*HC)[i],&cd[start]);
}
free(cd);
}
void PreOrderTraverse(HuffmanTree HT, int length)
{
HTNode stack[1000];
int top = -1;
HTNode p = HT[length - 1];
while( p.weight != 0 || top != -1 )
{
while(p.weight != 0)
{
printf("%d ",p.weight);
if(top < 1000)
{
top++;
stack[top] = p;
}
else
{
printf("max");
return;
}
p = HT[p.lchild];
}
if(top != -1)
{
p = stack[top];
top--;
p = HT[p.rchild];
}
}
}
*HT = (HuffmanTree)malloc( (m+1) * sizeof(HTNode) );
//因为0号单元不用，所以m需要加一
p = *HT;
p++; // (*HT)[0]不用
for(i = 0; i <= m; p++, i++)
{
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
