赫夫曼输入和建立

Typedef struct{
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;
//动态分配数组存储赫夫曼编码表
Typedef char **HuffmanCode;
//动态分配数组存储赫夫曼编码表
Void HuffmanCoding ( HuffmanTree &HT, HuffmanCode &HC, int *w, int n){//w存放n个字符的权值，构造赫夫曼树HT，求赫夫曼编码HC
if(n<=1) return;
m=2*n-1;//结点总数
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用
for(p=HT,i=1; i<=n; ++i,++p,++w) *p={*w,0,0,0};
for( ;i<=m; ++i, ++p) *p={0,0,0,0};
for(i=n+1;i<=m;++i){//建赫夫曼树
Select(HT,i-1,s1,s2);
//在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为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;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
//分配n个字符编码的头指针向量
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));
//为第i个字符编码分配空间
Strcpy(HC[i],&cd[start]);//从cd复制编码到HC
}
free(cd);//释放工作空间}//HuffmanCoding

HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
P=m; cdlen=0;
for(i=1;i<=m;++i) HT[i].weight=0 ;
//遍历赫夫曼树时用作结点状态标志
While(p){
If(HT[p].weight==0)
{//向左
HT[p].weight=1;
If(HT[p].lchild!=0){p=HT[p].lchild; cd[cdlen++]=“0”;}
Else if(HT[p].rchild==0){
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
Cd[cdlen]=“\0”;strcpy(HC[p],cd); //复制编码
}
}// 向左
Else if (HT[p].weight==1)
{ //向右
HT[p].weight=2;
If(HT[p].rchild!=0){p=HT[p].rchild; cd[cdlen++]=“1”;}
}
Else
{ //HT[p].weight==2,退回
HT[p].weight=0; p=HT[p].parent; --cdlen;
//退回父结点，编码长度减1
}//else
}//while