huffman.txt

解决快速排序问题

#include<string.h> 
#include<stdlib.h> 
#include<stdio.h>

int m,s1,s2;

typedef struct { 
unsigned int weight; 
unsigned int parent,lchild,rchild; 
}HTNode,*HuffmanTree;

typedef char ** HuffmanCode;

void Select(HuffmanTree HT,int n) 
{ 
      int i,j; 
   for(i=1;i<=n;i++)
    if(HT[i].parent==0) 
   {s1=i;
      break;
   }
      for(j=i+1;j<=n;j++)
     if(HT[j].parent==0) 
   {
    s2=j;
    break;
   }
      for(i=1;i<=n;i++)
   {
    if(HT[i].parent==0)
       if(HT[s1].weight>HT[i].weight)
       if(s2!=i)
         s1=i;
   }
      for(j=1;j<=n;j++)
   {
    if(HT[j].parent==0)
       if(HT[s2].weight>HT[j].weight)
       if(s1!=j)
         s2=j;
   }
   if(s1>s2)
{
    int temp=s1;
    s1=s2;
    s2=temp;
}
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) 
{
int i;
char *cd;
int p;
int cdlen;
if (n<=1) return; 
    m = 2 * n - 1; 
    HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); 
    for (i=1; i<=n; i++) 
{ 
      HT[i].weight=w[i-1]; 
      HT[i].parent=0; 
      HT[i].lchild=0; 
      HT[i].rchild=0; 
    } 
   for (i=n+1; i<=m; i++) 
{ 
    HT[i].weight=0; 
    HT[i].parent=0; 
    HT[i].lchild=0; 
    HT[i].rchild=0; 
   } 
   
   //添加查看，便于调试
printf("构造过程显示：\n");
   for(i=1;i<=m;i++)
     printf("%4d%4d%4d%4d%4d\n",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild);
system("pause");

for(i=n+1;i<=m;i++)
{
   Select(HT,i-1);
   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;
   //添加查看，便于调试
   /*printf("s1=%d,s2=%d\n",s1,s2);
   for(j=1;j<=i;j++)
     printf("%d%4d%4d%4d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
      system("pause");
   */
}
cd = (char *)malloc(n*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=0;
    p=HT[p].parent;
    --cdlen;
   }
}

}

int main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("请输入节点数：\n");
scanf("%d",&n);
HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode));
w=(int *)malloc(n*sizeof(int));
printf("请输入节点的权值：\n");
for(i=0;i<n;i++)
   scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n); 
printf("输出编码：\n");
for(i=1;i<=n;i++)
   printf("%2d(%4d):%s\n",i,w[i-1],HC[i]); 
return 0;
system("pause");
}