Re: 霍夫曼碼？

什麼是霍夫曼碼?
Cauchy 撰寫於文章 <76o1b5$1g4$[e-mail]>...
>
>神啊..救救我吧! 撰寫於文章 <3SJLeK$[e-mail]>...
>>請問一下如果我想寫一串將英文字母
>>變成霍夫曼碼的程式，要怎麼宣告節
>>點的struct type啊？到底需不需到用
>>到link list，（最好是不要用到啦）....？？
>
>我以前寫過 程式給你參考看看
>
>/*
>     Huffman Code
>     Author:  林嵩慶
>     DATE:   96/11/04
>*/
>
>#include <stdio.h>
>#include <string.h>
>#include <limits.h>
>
>#define ALPHASIZE 256
>#define NODESIZE (2 * ALPHASIZE - 1)
>
>void Construct_Huffman_Codetree(char *buffer, long size);
>void BuildTree(void);
>int FindSmallest(long *wt);
>int FindSecondSmallest(long *wt);
>
>long weight[NODESIZE];
>int father[NODESIZE];
>int parity[NODESIZE];
>int rightChild[NODESIZE];
>int leftChild[NODESIZE];
>int root;
>int stack[NODESIZE];
>void ShowCode(int code);
>
>void main()
>{
> char data[15];
> int i;
>
> strcpy(data, "AAAAABBBCDD");
>
> printf("Original data = %s\n\n", data);
>
> Construct_Huffman_Codetree(data, 11);
> BuildTree();
>
> for (i = 0; i < ALPHASIZE; i++)
>  {
>  if (weight[i] == 0)
>   continue;
>
>  printf("%c == ", i);
>  ShowCode(i);
>  printf("\n");
>  }
>}
>
>void ShowCode(int code)
>{
>    int q, i, j;
>
>    q = code;
>    i = 0;
>    while (q != root)
>     {
>     stack[i] = parity[q];
>     i++;
>     q = father[q];
>     }
>    for (j = i-1; j >= 0; j--)
>     printf("%d", stack[j]);
>}
>
>/*
> 依weight中的統計資料建立huffman tree
>*/
>void BuildTree(void)
>{
> long wt = 1;
> int i, fatherNode, lt, rt;
>
> for (i = 0; i < NODESIZE; i++)
>  {
>  father[i] = -1;
>  rightChild[i] = -1;
>  leftChild[i] = -1;
>  parity[i] = -1;
>  }
>
> for (i = ALPHASIZE; i < NODESIZE; i++)
>  weight[i] = -1;
>
> fatherNode = ALPHASIZE;
> for (;;)
>  {
>  lt = FindSmallest(&wt);
>  rt = FindSecondSmallest(&wt);
>  if (rt == -1)
>   {
>   root = lt;
>   break;
>   }
>  parity[lt] = 0;
>  parity[rt] = 1;
>  father[lt] = fatherNode;
>  father[rt] = fatherNode;
>  rightChild[fatherNode] = rt;
>  leftChild[fatherNode] = lt;
>  weight[fatherNode] = weight[rt] + weight[lt];
>  fatherNode++;
>  }
>}
>
>int FindSmallest(long *wt)
>{
> int i, rt = -1;
> long w;
>
> w = LONG_MAX;
> for (i = 0; i < NODESIZE; i++)
>  {
>  if (father[i] == -1 && weight[i] >= *wt && weight[i] < w)
>   {
>   rt = i;
>   w = weight[i];
>   }
>  }
> *wt = w;
> return rt;
>
>}
>
>int FindSecondSmallest(long *wt)
>{
> int i, rt = -1, rt2 = -1;
> long w;
>
> rt = FindSmallest(wt);
> w = LONG_MAX;
> for (i = 0; i < NODESIZE; i++)
>  {
>  if (father[i] == -1 && weight[i] >= *wt && weight[i] < w && i != rt)
>   {
>   rt2 = i;
>   w = weight[i];
>   }
>  }
> *wt = w;
> return(rt2);
>}
>
>/*
> 統計資料中每個字元的個數,將統計個數存到weight中
>
> buffer 指向資料開頭的指標
> size 資料的長度
>*/
>
>void Construct_Huffman_Codetree(char *buffer, long size)
>{
> long i;
>
> for (i = 0; i < ALPHASIZE; i++)
>  weight[(int)i] = 0;
>
> for (i = 0; i < size; i++)
>  weight[*(buffer+i)]++;
>
>}
>
>