A_yue.

图像是偷的啦
现在还画不了这么好啦

Huffman

#include<stdio.h>
#include<stdlib.h>
#define MAXLEAF 50 /*叶子数最大值*/
#define MAXNODE 2*MAXLEAF-1 //最大节点数目
#define MAXCODE 30 //最大编码位数
#define MAXVALUE 1000 //最大权值
typedef struct node
{ /*节点类型定义*/
int weight;
char letter;
int parent;
int lchild;
int rchild;
} huffnode;
typedef struct code
{ /*编码类型定义*/
int bits[MAXCODE];
int start;
} huffcode;
void HuffManTree(huffnode a[],int n)
{ /*构造哈夫曼树*/
int i,j,m1,m2,x1,x2;

for(i=0;i<n-1;i++)
{
       m1=m2=MAXVALUE;
    x1=x2=0;
    for(j=0;j<n+i;j++)
    { /*找出最小的两个权值节点*/
     if(a[j].parent==-1&&a[j].weight<m1)
     {
      m2=m1;
      x2=x1;
      m1=a[j].weight;
      x1=j;
     }
     else if(a[j].parent==-1&&a[j].weight<m2)
     {
      m2=a[j].weight;
      x2=j;

}

    }

    a[x1].parent=n+i;
    a[x2].parent=n+i;
    a[n+i].lchild=x1;
    a[n+i].rchild=x2;
    a[n+i].weight=a[x1].weight+a[x2].weight;


}

}
void HuffManCode(huffnode a[],int n)
{ /*哈夫曼编码*/
int i,j,c,p;
huffcode cd ,code[MAXNODE];
HuffManTree(a,n);
for(i=0;i<n;i++)
{
   cd.start=n;
   c=i;
   p=a[c].parent;
   while(p!=-1)
   {
    if(a[p].lchild==c)//左孩子为0
     cd.bits[cd.start]=0;
    else
     cd.bits[cd.start]=1;//右孩子为1
    cd.start--;
    c=p;
    p=a[p].parent;

   }

cd.start++;
   for(j=cd.start;j<=n;j++)
    code[i].bits[j]=cd.bits[j];
    code[i].start=cd.start;

}
puts("\n输出哈夫曼编码:");
puts("字符   权值    哈夫曼编码");
for(i=0;i<n;i++)
{    printf("%c     ",a[i].letter);
      printf(" %d       ",a[i].weight);
for(j=code[i].start;j<=n;j++)
   printf("%d",code[i].bits[j]);

   printf("\n");
}
}

void Error(char *str)
{
printf("error:%s",str);
puts("请按任意键返回");
getchar();
exit(0);

}

int main()
{
int i,j,n;
huffnode huff_node[MAXNODE];
huffcode huff_code[MAXNODE];
puts("请输入叶子节点数目");
scanf("%d",&n);
if(n<0||n>MAXLEAF)
   Error("输入叶子节点数目越界");
for(i=0;i<2*n-1;i++)
{
   huff_node[i].weight=0;
   huff_node[i].rchild=-1;
   huff_node[i].parent=-1;
   huff_node[i].lchild=-1;
   huff_node[i].letter='\0';

}
printf("\n请输入%d个叶子节点的字母和权值\n",n);
    getchar();
for(i=0;i<n;i++)

{       puts("请输入字母和权值");
    scanf("%c%d",&huff_node[i].letter,&huff_node[i].weight);
    getchar();

}
puts("======================================");
    printf("字符   权值\n");
for(i=0;i<n;i++)
{
   printf("%c     %4d \n",huff_node[i].letter,huff_node[i].weight);

}
puts("======================================");
HuffManCode(huff_node,n);

}

评论
热度(1)
©A_yue. | Powered by LOFTER