1 前言：

??這個程序主要是用來實現建立哈夫曼，以及遍歷哈夫曼,
? 關于哈夫曼建立的原理，以及應用請參考《大話數據結構》第200頁，6.12 赫夫曼樹以及應用

??假設有一串英文字符
??? "ABBCCCCDDDDDDEEEEEEEEFFFFFFFFFGGGGGGGGGGHHHHHHHHHHH"
??? 從這里看每個字符頻率出現都不一樣,用哈夫曼來進行優化,其中次數分別為:
??? A : 1 , B : 2 , C : 4,D : 6,E : 8,F : 9,G : 10 ,H : 11

2 建成的哈夫曼圖如下：

3 程序運行結果

?

4 完整代碼

#include<stdio.h> #include<malloc.h>/*這個程序主要是用來實現建立哈夫曼，以及遍歷哈夫曼,關于哈夫曼建立的原理，以及應用請參考《大話數據結構》第200頁，6.12 赫夫曼樹以及應用1 背景假設有一串英文字符"ABBCCCCDDDDDDEEEEEEEEFFFFFFFFFGGGGGGGGGGHHHHHHHHHHH"從這里看每個字符頻率出現都不一樣,用哈夫曼來進行優化,其中次數分別為:A : 1 , B : 2 , C : 4,D : 6,E : 8,F : 9,G : 10 ,H : 11 *///定義哈夫曼結構體 typedef struct HaFuManTree{char letter; //字母int number ; //出現次數int used; //是否用過struct HaFuManTree *pLeft ;//左孩子struct HaFuManTree *pRight ;//右孩子struct HaFuManTree *next; //下一個節點 }HaFuManTree ,*PHaFuManTree;//函數申明 PHaFuManTree add(PHaFuManTree pNode2,PHaFuManTree newNode); PHaFuManTree initHanFuMan(PHaFuManTree pNode); PHaFuManTree getSmalleast(PHaFuManTree pNode); void inorderTraversal(PHaFuManTree pNode); PHaFuManTree ininLinked();int main(){ printf("初始化鏈表\n"); PHaFuManTree pNode = ininLinked();printf("初始化哈夫曼樹\n"); pNode = initHanFuMan(pNode);printf("中序遍歷哈夫曼樹\n"); inorderTraversal(pNode);return 1; }//初始化單鏈表 PHaFuManTree ininLinked(){ int A =1,B=2,C=4,D=6,E=8,F=9,G=10,H=11; PHaFuManTree pHead = (HaFuManTree *)malloc(sizeof(HaFuManTree)*1); pHead->next = NULL; PHaFuManTree pTail = pHead;PHaFuManTree nodeA = (HaFuManTree *)malloc(sizeof(HaFuManTree)*1); nodeA->letter = 'A'; nodeA->number = A; nodeA->used = 0; nodeA->pLeft = NULL; nodeA->pRight = NULL; pTail->next = nodeA; pTail = nodeA;PHaFuManTree nodeB = (HaFuManTree *)malloc(sizeof(HaFuManTree)*1); nodeB->letter = 'B'; nodeB->number = B; nodeB->used = 0; nodeB->pLeft = NULL; nodeB->pRight = NULL; nodeB->next = NULL; pTail->next = nodeB; pTail = nodeB;PHaFuManTree nodeC = (HaFuManTree *)malloc(sizeof(HaFuManTree)*1); nodeC->letter = 'C'; nodeC->number = C; nodeC->used = 0; nodeC->pLeft = NULL; nodeC->pRight = NULL; nodeC->next = NULL; pTail->next = nodeC; pTail = nodeC;PHaFuManTree nodeD = (HaFuManTree *)malloc(sizeof(HaFuManTree)*1); nodeD->letter = 'D'; nodeD->number = D; nodeD->used = 0; nodeD->pLeft = NULL; nodeD->pRight = NULL; nodeD->next = NULL; pTail->next = nodeD; pTail = nodeD;PHaFuManTree nodeE = (HaFuManTree *)malloc(sizeof(HaFuManTree)*1); nodeE->letter = 'E'; nodeE->number = E; nodeE->used = 0; nodeE->pLeft = NULL; nodeE->pRight = NULL; nodeE->next = NULL; pTail->next = nodeE; pTail = nodeE;PHaFuManTree nodeF = (HaFuManTree *)malloc(sizeof(HaFuManTree)*1); nodeF->letter = 'F'; nodeF->number = F; nodeF->used = 0; nodeF->pLeft = NULL; nodeF->pRight = NULL; nodeF->next = NULL; pTail->next = nodeF; pTail = nodeF;PHaFuManTree nodeG = (HaFuManTree *)malloc(sizeof(HaFuManTree)*1); nodeG->letter = 'G'; nodeG->number = G; nodeG->used = 0; nodeG->pLeft = NULL; nodeG->pRight = NULL; nodeG->next = NULL; pTail->next = nodeG; pTail = nodeG;PHaFuManTree nodeH = (HaFuManTree *)malloc(sizeof(HaFuManTree)*1); nodeH->letter = 'H'; nodeH->number = H; nodeH->used = 0; nodeH->pLeft = NULL; nodeH->pRight = NULL; nodeH->next = NULL; pTail->next = nodeH; pTail = nodeH; return pHead;}; //在鏈表后面添加元素 PHaFuManTree add(PHaFuManTree pNode2,PHaFuManTree newNode){PHaFuManTree pNode = pNode2;while(pNode->next != NULL){pNode = pNode->next;}pNode->next = newNode;return pNode2; };//初始化哈夫曼樹 PHaFuManTree initHanFuMan(PHaFuManTree pNode){// 1 從鏈表中取出兩個最小的元素 small_1 ,small_2;PHaFuManTree small_1 = getSmalleast(pNode);// 2 如果small_1為NULL,結束程序.if(!small_1){printf("哈夫曼樹為NULL,程序退出");exit(1);}else{// 3 如果small_1不為NULL,small_2為NULL,結束遞歸small_1->used = 1;PHaFuManTree small_2 = getSmalleast(pNode);if(!small_2){return small_1;}else{// 4 如果small_1,small_2都不為NULL,循環遞歸.//4.1 將small_2標志為已用small_2->used = 1 ;//4.2 創建一個新節點 newNodePHaFuManTree newNode = (HaFuManTree *)malloc(sizeof(HaFuManTree)*1);newNode->used = 0;newNode->letter = 'N';newNode->pLeft = NULL;newNode->pRight = NULL;newNode->next = NULL;newNode->number = NULL;//4.3 將newNode指向small_1,small_2if(small_1->number < small_2->number){newNode->pLeft = small_1;newNode->pRight = small_2;}else{newNode->pLeft = small_2;newNode->pRight = small_1;}newNode->number = small_1->number + small_2->number;//4.4 將newNode加入到鏈表的尾部pNode = add(pNode,newNode);//4.5再次遞歸initHanFuMan(pNode);}}}; //得到鏈表中最小元素 PHaFuManTree getSmalleast(PHaFuManTree pNode){pNode = pNode->next;while(pNode!=NULL && pNode->used){pNode = pNode->next;};if(pNode != NULL){PHaFuManTree small = pNode;pNode = pNode->next;while(pNode != NULL){if(small->number > pNode->number && !pNode->used){small = pNode;}pNode = pNode->next;};return small;}else{return NULL;}}; //中序遍歷哈夫曼樹void inorderTraversal(PHaFuManTree pNode){if(pNode == NULL) return;if(pNode->pLeft != NULL){inorderTraversal(pNode->pLeft);};if(pNode->pLeft == NULL && pNode->pRight == NULL){printf("letter = %c , number = %d\n",pNode->letter,pNode->number);}if(pNode->pRight != NULL){inorderTraversal(pNode->pRight );};};

?

?

?

總結

以上是生活随笔為你收集整理的c 实现哈夫曼编码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。