代碼區(qū)

#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct HuffNode{//赫夫曼結(jié)點(diǎn) int weight,parent,lchild,rchild;//權(quán)值,雙親,左/右孩子 }HuffNode; typedef struct HuffTree{//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹(shù) int n;//赫夫曼樹(shù)葉子結(jié)點(diǎn)個(gè)數(shù) HuffNode *hf;//結(jié)點(diǎn)向下遞推 }HuffTree; typedef char ** HuffCode;//動(dòng)char ** 二級(jí)指針 動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表 //顯示赫夫曼表 void DisplayHuffTree(HuffTree HT){int i,m = 2*HT.n-1;printf("序號(hào)\t權(quán)值\t雙親\t左孩子\t右孩子\n");for(i=1;i<=m;i++)printf("%2d\t%2d\t%2d\t%2d\t%2d\n",i,HT.hf[i].weight,HT.hf[i].parent,HT.hf[i].lchild,HT.hf[i].rchild); }//找出最小的兩個(gè)結(jié)點(diǎn)s1，s2//雙親必須 == 0 //1-n存放初始的葉子結(jié)點(diǎn),i = n+1;i---2n-1存放合并后的雙親結(jié)點(diǎn) void Select(HuffTree HT,int i,int &s1,int &s2){//HT數(shù)組//i為將要成為的雙親//si,s2為兩個(gè)較小的結(jié)點(diǎn),即將成為左/右孩子 int j;int min = INT_MAX;//min初始為整數(shù)最大值 for(j=1;j<=i;j++){//找出權(quán)值最小的那個(gè)結(jié)點(diǎn)，把下標(biāo)j賦給s1 if(HT.hf[j].parent==0&&HT.hf[j].weight<=min)//找出雙親等于0&&比較后權(quán)值較小的結(jié)點(diǎn)//雙親 == 0是沒(méi)有變成葉子的結(jié)點(diǎn) {s1 = j;//j下標(biāo)給s1 min = HT.hf[j].weight;//把較小的結(jié)點(diǎn)權(quán)值賦給min//最后那個(gè)就是最先的權(quán)值 結(jié)點(diǎn) }}//再篩選一次，找出另一個(gè)最小的結(jié)點(diǎn) min = INT_MAX;for(j=1;j<=i;j++){if(HT.hf[j].parent==0&&j!=s1&&HT.hf[j].weight<=min){s2 = j;min = HT.hf[j].weight;}} }//1-n存放初始的葉子結(jié)點(diǎn),i = n+1;i---2n-1存放合并后的雙親結(jié)點(diǎn) void CreateHuffTree(HuffTree &HT,int n1){int m = 2*n1-1;//m == 2n-1為總結(jié)點(diǎn)數(shù) HT.hf = (HuffNode *)malloc((m+1)*sizeof(HuffNode));//0號(hào)單元沒(méi)用 HT.n = n1;int i;for(i=1;i<=m;i++){//初始全部賦值為0 HT.hf[i].parent = 0;HT.hf[i].lchild = 0;HT.hf[i].rchild = 0;HT.hf[i].weight = 0;}printf("輸入結(jié)點(diǎn)的權(quán)值\n"); for(i=1;i<=HT.n;i++){//輸入前n個(gè)結(jié)點(diǎn)的權(quán)值 scanf("%d",&HT.hf[i].weight); }printf("顯示空/初始化赫夫曼表\n");DisplayHuffTree(HT);//顯示赫夫曼表 int s1,s2;for(i=HT.n+1;i<=m;i++){Select(HT,i-1,s1,s2);//找出最小的兩個(gè)結(jié)點(diǎn)s1,s2 HT.hf[s1].parent = i;//i是s1的雙親 HT.hf[s2].parent = i;//i是s2的雙親 HT.hf[i].weight = HT.hf[s1].weight+HT.hf[s2].weight;//下標(biāo)為i的權(quán)值是下標(biāo)為s1和s2的權(quán)值之和 printf("s1=%d s2=%d s1的權(quán)值%d s2的權(quán)值%d i的權(quán)值%d\n",s1,s2,HT.hf[s1].weight,HT.hf[s2].weight,HT.hf[i].weight);HT.hf[i].lchild = s1;//i下標(biāo)結(jié)點(diǎn)的左孩子是s1的下標(biāo) HT.hf[i].rchild = s2;//i下標(biāo)結(jié)點(diǎn)的右孩子是s2的下標(biāo) }printf("顯示構(gòu)造完成的赫夫曼表\n"); DisplayHuffTree(HT); }void CreateHuffCode(HuffTree HT,HuffCode &HC){HC = (HuffCode/*(char ** )*/)malloc((HT.n+1)*sizeof(char *));char *cd;//臨時(shí)空間 cd = (char*)malloc(HT.n*sizeof(char));int start = HT.n-1;cd[start] = '\0';//最后存儲(chǔ)結(jié)束標(biāo)志 int c,f,i;//孩子c//雙親f for(i=1;i<=HT.n;i++){start = HT.n-1;//start為夫曼表的最后一個(gè)結(jié)點(diǎn) c = i;//c是赫夫曼表的第一個(gè)結(jié)點(diǎn) f = HT.hf[c].parent;//f是夫曼表的第一個(gè)結(jié)點(diǎn)的雙親 while(f){start --;//從后向前 if(HT.hf[f].lchild==c)//第i個(gè)結(jié)點(diǎn)的雙親的孩子 == c cd[start] = '0';//cd【start】位置存放0//左子樹(shù)0，右子樹(shù)1 elsecd[start] = '1';//cd【start】位置存放1//左子樹(shù)0，右子樹(shù)1 c = f;f = HT.hf[c].parent;}HC[i] = (char*)malloc((HT.n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd); } //輸出赫夫曼編碼表 void DisplayHuffCode(HuffTree HT,HuffCode HC){int i,m = 2*HT.n-1;printf("序號(hào)\t權(quán)值\t雙親\t赫夫曼編碼\n");for(i=1;i<=m;i++)printf("%2d\t%2d\t%2d\t%s\n",i,HT.hf[i].weight,HT.hf[i].parent,HC[i]); }int main(){HuffTree HT;HuffCode HC;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表 CreateHuffTree(HT,8);//構(gòu)造赫夫曼表 CreateHuffCode(HT,HC);//構(gòu)造赫夫曼編碼表 int i;printf("赫夫曼編碼表\n"); DisplayHuffCode(HT,HC);for(i=1;i<=HT.n;i++){printf("%s\n",HC[i]);}return 0; }

測(cè)試區(qū)

總結(jié)

以上是生活随笔為你收集整理的赫夫曼二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。