Re: [問題] 列出Huffman code的演算法

看板C_and_CPP作者fenir (severus)時間14年前 (2010/06/26 16:46)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《godman362 (青)》之銘言： : 雖然是個很久以前問過的問題 : 不過剛好最近有處理到Huffman編CodeBook的問題 : 想了一個演算法，讓大家見笑好了： : 先來設一下Node的struct內容 : struct Node : { : int Filter; : string BitCode; : Node *LeftChild; : Node *RightChild; : }; : void PostOrderEncode(Node *node, string LRBit, string FatherBitCode) : { : node-BitCode = FatherBitCode + LRBit; : if (node->LeftChild != NULL) : PostOrderEncode(node->LeftChild, "0", node->BitCode); : if (node->RightChild != NULL) : PostOrderEncode(node->RightChild, "1", node->BitCode); : if (node->Filter != -1) : cout <<node->BitCode <<endl; : } : 由於建立Huffman時，會有非Leaf Node的中間節點 : 中間節點的部份，通常把值設為-1，因為如果是處理圖片的Pixel是不能用0的 : 設這個參數在Node的結構中，主要是方便過濾而已，不設並不影響 : 使用此PostOrderEncode Function，一開始想當然爾是丟入root點 : 也就會變成：PostOrderEncode(root, "", ""); : 在LRBit這個參數中，所代表的是你往左或是往右搜尋 : 也就是下一個節點應該在BitCode後面加入的編碼 : 而FatherBitCode的部份，則是目前這個節點的BitCode : 也就是將目前節點和下一個節點應該編碼的字串結合，就成了此節點的BitCode : 故此可編出所有Leaf的BitCode : 最後講一下過濾，就是印出非末端節點的BitCode，中間節點的BitCode與我們無關 : 以上，一些小小的心得分想 : 感謝有興趣的人撥空收看首先非常感謝godman362 (青) 剛好最近也是寫Huffman Code卡在怎麼建立CodeBook 爬文剛好找到了這篇因為我學的是C語言所以我把他的演算法改成C如下這是我定義的struct: typedef struct node { char key; char BitCode[10]; int weight; struct node *left; struct node *right; }Node; 副程式: void PostOrderEncode(Node *node, char LRBit[], char FatherBitCode[]) { strcat(FatherBitCode, LRBit); /*字串串接, <string.h>*/ strcpy(node->BitCode, FatherBitCode); if (node->left != NULL) PostOrderEncode(node->left, "0", node->BitCode); if (node->right != NULL) PostOrderEncode(node->right, "1", node->BitCode); if (node->weight != 0) printf("%c %s\n", node->key, node->BitCode); } 使用這個function時呼叫 PostOrderEncode(&root, "", s); s是一個空字串的陣列讓字串串接時候有空間可以放程式可以跑但是出來的結果問題頗大測試1----------- 假設現在有兩個字母A和B BitCode輸出應該要是"",0和1三種 □ ／＼ A B 正確BitCode: 實際執行結果: □:"" (空的字串) □:01 A :0 A :0 B :1 B :01 測試2----------- 假設現在有三個字母A,B和C ▽ ／＼ □ C ／＼ A B 正確BitCode: 實際執行結果: ▽:"" (空的字串) ▽:01 □:0 □:001 A :00 A :00 B :01 B :001 C :1 C :01 結論: 只有最左下的是正確的其他的BitCode前面都會多幾個0 看了很久都覺得邏輯應該沒問題所以真的實在不知道要如何改起呀 Orz 請各問大大幫忙囉謝謝 --

推

exponential7

11/09 15:43,

11/09 15:43

推

WizZ

11/09 15:43,

11/09 15:43

推

kesking

11/09 15:43,

11/09 15:43