数据结构 哈夫曼编码问题

Question

#include
#include
#include
#include
#include
#include
#include
#include
#include

#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean;

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)
{
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=n*2-1;
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號未用
for(p=*HT+1,i=1;i<n;++i,++p,++w)
{
(*p).weight = *w; //對每個weight初始化
(*p).parent = 0; //對每個parent初始化
(*p).lchild = 0; //對每個lchild初始化
(*p).rchild = 0; //對每個rchild初始化
}

for(;i<m;++i,++p)
    (*p).parent = 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 = (*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個字符編碼
//的頭指針向量【第0個不用】
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]);        //複製：從cd輔助編碼（串）到HC
}
free(cd);       //釋放工作空間

}

int min(HuffmanTree t,int i)
{
int j,flag;
unsigned int k = UINT_MAX;
for(j=1;j<=i;j++)

{

if(t[j].weight<k && t[j].parent ==0) //循環查找最小的值
k = t[j].weight,flag = j;
}
t[flag].parent = 1; //對已經查找出來的最小值進行標記 .parent為1
return flag;

}

void select(HuffmanTree t,int i,int *s1,int *s2)
{
int j;
*s1 = min(t,i);
*s2 = min(t,i);
if(*s1>*s2)
{
j = *s1;
*s1 = *s2;
*s2 = j; //s1為最小的兩個值中序號小的那個
}
}

void main()
{
HuffmanTree HT;
HuffmanCode HC;
printf("請輸入權值的個數（>1）:");
int n,i,*w;
scanf("%d",&n);
w = (int*)malloc(n*sizeof(int));
printf("請依次輸入%d個權值（整數）：\n",n);
for(i=0;i<=n-1;i++)
scanf("%d",w+i);
HuffmanCoding(&HT,&HC,w,n);
for(i = 1;i<=n; i++)
puts(HC[i]);
}

Answer 1

http://wenku.baidu.com/link?url=MopnljD-t07AbJD4ath7-FiOCgxJ-isqkTeYKg5tV9YTSoL3GZ7L_jZYR2XpGUsXTLS-o3aWon7uxV_tLaBgE5t-qYbA75DGVb9o6vp7BNC