hf.cpp

哈夫曼树是一种带权路径长度最短的树。 所谓路径长度就是某个端结点到树的根结点的距离,等于该端结点的祖先数,或该结点所在层数减1,用lk表示。

#include<conio.h>
#include<stdio.h>
#include<malloc.h>
#define n  100
int h[50],m[50];
int i=0,j=0,v=1,t=1;   /*用来标记huffman树的深度*/
int k=195,K=192,chp=179,chr=27; /*输出huffman时用到的字符*/
int huffrecod=0;         /*用于记录huffman的编码与字符的个数*/
typedef struct Lnode{            /*用来记录字符的个数*/
char code;
int  values;
struct Lnode *next;
}Lnode,*listnode;

typedef struct charhuffman{   /*用来记录字符的huffman编码序列*/
char code;
int huffuman[15];
int count; /*记录编码的个数*/
}charhuffman,*huffmanchar;

typedef struct treenode{ /*二叉树的构造体*/
char code;
int values;
struct treenode *lchild;
struct treenode *rchild;
}treenode,*ntree;

typedef struct queuenode/*队列的构造体*/
{
  int values;
  struct treenode *pntree;
  struct queuenode *next;
}queuenode,*listqueue;

huffmanchar huff;

listqueue returnroot(listnode heap)
{
 listqueue s,t,k;
 ntree p;
 s=(listqueue)malloc(sizeof(queuenode)); /*建立队列的头结点*/
 k=s;
 s->values=0; s->pntree=NULL; s->next=NULL;
 while(heap!=NULL)
 {
  p=(ntree)malloc(sizeof(treenode));
  p->code=heap->code;
  p->values=heap->values;p->lchild=NULL;p->rchild=NULL;
  t=(listqueue)malloc(sizeof(queuenode));
  t->values=heap->values;
  t->pntree=p; s->next=t; t->next=NULL;
  s=s->next;
  heap=heap->next;
 }
return k;
}

listnode creatleaflist(char s[])  /*输入字符序列，确定叶子结点及权值*/
{listnode heap,p,r;
 int i,j=0; 
 p=(listnode)malloc(sizeof(Lnode));
 heap=p;
 p->next=NULL;p->code=s[0];p->values=1;
  while(s[j]!=NULL)
 {for(i=0;i<j;i++)
  { if(s[i]==s[j])
    { r=heap;
      while(s[i]!=r->code)
      r=r->next;
      if(s[i]==r->code)
         r->values++; 
      break;    
      }/*if(s[i]==s[j])*/
     else
      {  if(i==(j-1))
        {
         r=(listnode)malloc(sizeof(Lnode));
         p->next=r;r->next=NULL;
         p=p->next;p->code=s[j];p->values=1;
         break;
        }/*if(i==(j-1))*/
      }
    }/*for(i=0;i<j;i++)*/
  j++;
 } /*while(s[j]!=NULL)*/
return heap;
}

listqueue heaplistqueue(listqueue heapqueue) /*确定哈曼树*/
{listqueue pk,pks,rs,rss,freep;
  int a,b,i,j;
  ntree pa,pb,ps;
  pk=heapqueue;
  pks=heapqueue;
  while(pk->next->next!=NULL)
  { i=0,j=0; /*用来确定是否删除最小两权植的结点*/
    pks=pks->next;
    a=pks->values;
    b=pks->next->values;
    while(pks->next!=NULL) /*找到最小两个权值*/
    {pks=pks->next;
     if(a>pks->values){b=a;a=pks->values;}
     else{if(b>pks->values) b=pks->values;}
    }
    rs=pk;
    heapqueue=rs->next;
    while(heapqueue!=NULL)
    { if(heapqueue->values==a&&i==0)
        {pa=heapqueue->pntree;
          rs->next=heapqueue->next;
          freep=heapqueue;
          free(freep);
          heapqueue=rs->next;
          i=1;       
        }else
         {if(heapqueue->values==b&&j==0)
          {pb=heapqueue->pntree;
           rs->next=heapqueue->next;
           freep=heapqueue;
           free(freep);
           heapqueue=rs->next;
           j=1;
          }else
             {rs=heapqueue;
              heapqueue=heapqueue->next;
             } 
         } 
    }/*while(heapqueue!=NULL)*/
    heapqueue=rs;
    ps=(ntree)malloc(sizeof(treenode));
    ps->code=‘‘;ps->lchild=pa;ps->rchild=pb;ps->values=a+b;
    rss=(listqueue)malloc(sizeof(queuenode));
    rss->values=a+b;
    rss->pntree=ps; 
    heapqueue->next=rss;
    rss->next=NULL;
    pks=pk;
   }
 return pk;
}

void printdata(ntree heaptree)  /*输出哈夫曼编码及输出哈夫曼树*/
{
 int j;
 if(heaptree->code!=‘‘)
  {printf("%d",heaptree->values);
   printf(" %c",chr);
   printf("%c",heaptree->code);
   printf("--(");
   huff[huffrecod].code=heaptree->code;
   huff[huffrecod].count=i;
   for(j=0;j<i;j++){
     huff[huffrecod].huffuman[j]=h[j];
     printf("%d",h[j]);
     }
   printf(")\n");
   huffrecod++;
   i--;
  }
  else
  {h[i++]=0;
   v=i;
   printf("%d\n",heaptree->values);
   while(--v)
   printf("%c ",chp);
   printf("%c ",k);
   printdata(heaptree->lchild);
   h[i++]=1;
   t=i;
   while(--t)
   printf("%c ",chp);
   printf("%c ",K);
   printdata(heaptree->rchild);
   i--;
  }
}

void encode(char s[],huffmanchar huff)
{ int nt=0;
  int hfcount;
  int ihuff;
  while(s[nt]!=NULL)
  { for(ihuff=0;ihuff<50;ihuff++)
    { if(s[nt]==huff[ihuff].code)
      {for(hfcount=0;hfcount<huff[ihuff].count;hfcount++)
        {printf("%d",huff[ihuff].huffuman[hfcount]);
        }
        break;
      }
    }
    nt++;
  }
}

void main()
{ 
 int i=0,j=0;
 char s[n],c;
 listnode heap; /*确定叶子结点*/  
 ntree heaptree; /*确定哈夫曼树*/
 listqueue heapqueue,pk;
 huff=(huffmanchar)malloc(50*sizeof(charhuffman));
 gotoxy(30+wherex(),wherey());
 textcolor(BLACK); 
 textbackground(WHITE); 
 cprintf("This huffman program\r\n");
 printf("please input char list and in Enter of end!:\n\n");
 c=getchar();
 if(c==‘\n‘)
 exit(0);
 while(c!=‘\n‘)
 {s[i++]=c;
  c=getchar();
  }
 heap=creatleaflist(s);
 heapqueue=returnroot(heap);
 printf("\nthe chars appear of frequency:\n");
 while(heap!=NULL)
 {printf("%c%d\t",heap->code,heap->values);
  heap=heap->next;
  } 
 printf("\n");
 pk=heaplistqueue(heapqueue);
 printf("\nthe huffman:\n");
 printdata(pk->next->pntree);
 printf("\nthe char coding:\n");
 for(j=0;j<huffrecod;j++)
 { printf("%c-",huff[j].code);
   for(i=0;i<huff[j].count;i++)
   {printf("%d",huff[j].huffuman[i]);}
   printf("\t");
  }
 printf("\nthe chars encode:\nSTART--<");
 encode(s,huff);
 printf(">--END");
 getch();
}