電文編碼

從鍵盤接收一串電文字符，輸出對應的Huffman編碼，同時，能翻譯由Huffman編碼生成的代碼串，輸出對應的電文字串

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXSIZE 50
typedef char DataType;

typedef struct	// 哈夫曼樹結點的結構
{
   DataType data;	// 資料用字符表示
   int weight;	// 權值
   int parent;	// 雙親
   int lchild,rchild;	// 左右孩子
} HuffNode;

typedef struct	// 哈夫曼編碼的存盤結構
{
   DataType cd[MAXSIZE];	// 存放編碼位串
   int start;	// 編碼的起始位置
} HuffCode;


int HuffmanCreate(HuffNode *ht)
{int n=0;
   int i,j,p1,p2,m1,m2;
   char c;

   int frequency[58]={0};

   while((c=getchar())!='\n'){
      frequency[c-65]++;
   }
   for(int i=0;i<58;i++){
      if(frequency[i]!=0){
            n++;
         ht[n].data=i+65;
         ht[n].weight=frequency[i];

      }
   }

   for(i=1;i<n+1;i++)
   {
         printf("%c" ,ht[i].data);	// 先輸出結點
         printf("%d",ht[i].weight);
         printf("\n");
   }
   for(i=1;i<=2*n -1;i++)	// 對陣列初始化
      ht[i].parent=ht[i].lchild=ht[i].rchild=0;
   for(i=n+1;i<=2*n-1;i++)
   {
      m1=m2=32767;	// 令 m1 、m2 為整數最大值
      p1=p2=1;
      for(j=1;j<i;j++)	//	找出 parent 為 0 且權值最小的兩個結點
         {
            if(ht[j].parent==0)
            {
               if(ht[j].weight<m1)
               {
                  m2=m1;
                  p2=p1;
                  m1=ht[j].weight;
                  p1=j;
               }

               else if(ht[j].weight<m2)
               {
                  m2=ht[j].weight;
                  p2=j;
               }
            }
         }
         ht[i].lchild=p1;	//p1 為新結點的左孩子
         ht[i].rchild=p2;		//p2	為新結點的右孩子
         ht[i].weight=m1+m2;	//	新結點的權值為最小權值和次小權值的和
         ht[p1].parent=i;
         ht[p2].parent=i;

   }
   for(i=1;i<=n;i++){
      printf("此節點%c ,父節點%d ,左孩子 %d,右孩子%d",ht[i].data,ht[i].parent,
             ht[i].lchild,ht[i].rchild);
             printf("\n");
      }
//printf("哈夫曼樹已成功建立！	\n");
return n;

}



void Encoding(HuffNode *ht,HuffCode *hcd,int n)
{
   HuffCode d;
   int i,j,f;
   for(i=1;i<=n;i++)	// 對所有結點回圈
   {
      d.start=n+1;	// 起始位置
      f=ht[i].parent; // 雙親的位置
      for(j=i;f!=0;j=f,f=ht[j].parent)
      {
         if(ht[f].lchild==j)
            d.cd[ --d.start]='0';	// 規定左樹代碼為	0
         else
            d.cd[ --d.start]='1';	// 規定右樹代碼為	1
      }
      hcd[i]=d;
   }
   printf("輸出哈夫曼編碼：	\n");
   for(i=1;i<=n;i++)
   {
      printf("%c" ,ht[i].data);	// 先輸出結點
      for(j=hcd[i].start;j<=n;j++)		// 在輸出其對應編碼
         printf("%c",hcd[i].cd[j]);
      printf("\n");
   }
}


void Decoding(HuffNode *ht,int n)
{
   DataType c,ch[200];	//c 接收輸入電文，	ch 儲存
   int i,temp,f;
   printf("請輸入電文,以“#”為結束標志：\n");
   c=getchar();
   i=0;
   while(c!='#')
   {
      i++;	//ch 陣列下標后移
      ch[i]=c;	// 將單個字符依次存入	ch 字串中
      c=getchar();
   }
   temp=i;	// 標記陣列存盤末位位置
   i=1;
   printf("輸出哈夫曼譯碼：	\n");
   while(i<=temp)
   {
      f=2*n -1;	// 每次都從根節點開始查找
      while(ht[f].lchild!=0)
      {
         if(ch[i]=='0')
            f=ht[f].lchild;
         if(ch[i]=='1')
            f=ht[f].rchild;
         i++;
      }
      printf("%c",ht[f].data);
   }
   printf("\n");
}


void main()
{
   int n=0,select;
   char ch;
   HuffNode ht[MAXSIZE*2];	// 定義存放哈夫曼樹的陣列
   HuffCode hcd[MAXSIZE];	// 定義存放編碼的陣列
   while(1)
   {
      printf( "1---建立哈夫曼樹	\n");
      printf( "2---編碼   \n");
      printf( "3---譯碼  \n");
      printf("4---退出系統 	\n");
      printf(" 請輸入您所要實作的功能："	);
      scanf("%d",&select);
      switch(select)
      {


         case 1:
               printf("請輸入字串："	);
               //scanf("%d",&ch);
               getchar();
               n=HuffmanCreate(ht);
               break;
         case 2:
               Encoding(ht,hcd,n);
               break;
         case 3:
               Decoding(ht,n);
               break;
         case 4:
               exit(0);
      }


   }
}

運行結果