1.cpp

大家可能遇到的信息论实验 哈夫曼编码 一种编码方法

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

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

void Select(HuffmanTree &HT,int num,int s[3])
{
 int i,t;
 for(i=1;i<=num;i++)
 {
  if(HT[i].parent==0)
  {
   s[1]=i;
   ++i;
   break;
  }
 }
 for(;i<=num;i++)
 {
  if(HT[i].parent==0)
  {
   if(HT[s[1]].weight <= HT[i].weight)
   {
    s[2]=i;
    ++i;
    break;
   }
   else
   {
    s[2]=s[1];
    s[1]=i;
    ++i;
    break;
   }
  }
 }
 for(;i<=num;i++)
 {
  if(HT[i].parent==0)
   if(HT[i].weight < HT[s[2]].weight)
   {
    s[2]=i;
    if(HT[s[2]].weight < HT[s[1]].weight)
    {
     t=s[2];
     s[2]=s[1];
     s[1]=t;
    }
   }
 }
}

void main()
{
 int n,i,*w;
 printf(">>>>>>>20052840胡浩的哈夫曼编码与译码<<<<<<<<\n");
 printf(">>>>>>>请输入字符数目:");
 scanf("%d",&n);
 getchar();
 HuffmanTree HT;
 HuffmanCode HC;
 char *v;
 v=(char *)malloc((n+1)*sizeof(char));
 w=(int *)malloc((n+1)*sizeof(int));
 printf(">>>>>>>请分别输入出现的字符:");
 for(i=1;i<=n;i++)
  scanf("%c",&v[i]);
 printf(">>>>>>>所要字符出现次数:");
 for(i=1;i<=n;i++)
  scanf("%d",&w[i]);
 int m,s[3]={0},f,c,start;
 char *cd;
 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];
  HT[i].lchild=0;
  HT[i].parent=0;
  HT[i].rchild=0;
 }
 for(;i<=m;++i)//初始化双亲节点
 {
  HT[i].weight=0;
  HT[i].lchild=0;
  HT[i].parent=0;
  HT[i].rchild=0;
 }
 for(i=n+1;i<=m;++i)//建立双亲与叶子的关系
 {
  Select(HT,i-1,s);
  HT[s[1]].parent=i; HT[s[2]].parent=i;
  HT[i].lchild=s[1]; HT[i].rchild=s[2];
  HT[i].weight=HT[s[1]].weight + HT[s[2]].weight;
 }
 //建立huffman树完毕
 HC=(HuffmanCode)malloc((n+1)*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);
 for(i=1;i<=n;i++)
 {
  printf("%c--------",v[i]);
  puts(HC[i]);
 }
 getchar();
 char str[255],sn[50];
 printf(">>>>>>>请输入需要翻译的编码:");
 gets(str);
 i=0;
 while(str[i])
 {
  putchar(str[i]);
  ++i;
 }
 printf("的译码为:");
 int p,q=0,r;
 while(1)//总循环
 {
  if(str[q]=='\0')break;//计算完成跳出
  p=0;
  r=1;
  while(r)//分别计算
  {
   sn[p]=str[q];
   ++q;
   ++p;
   sn[p]='\0';
   for(i=1;i<=n;i++)//查找
   {
    if(strcmp(HC[i],sn)==0)
    {
     putchar(v[i]);
     r=0;
     break;
    }
   }
  }
 }
 putchar(10);
}