C++數(shù)據(jù)結(jié)構(gòu)與算法之哈夫曼樹(shù)的實(shí)現(xiàn)方法
本文實(shí)例講述了C++數(shù)據(jù)結(jié)構(gòu)與算法之哈夫曼樹(shù)的實(shí)現(xiàn)方法。分享給大家供大家參考,具體如下:
哈夫曼樹(shù)又稱(chēng)最優(yōu)二叉樹(shù),是一類(lèi)帶權(quán)路徑長(zhǎng)度最短的樹(shù)。
對(duì)于最優(yōu)二叉樹(shù),權(quán)值越大的結(jié)點(diǎn)越接近樹(shù)的根結(jié)點(diǎn),權(quán)值越小的結(jié)點(diǎn)越遠(yuǎn)離樹(shù)的根結(jié)點(diǎn)。
前面一篇圖文詳解JAVA實(shí)現(xiàn)哈夫曼樹(shù)對(duì)哈夫曼樹(shù)的原理與java實(shí)現(xiàn)方法做了較為詳盡的描述,這里再來(lái)看看C++實(shí)現(xiàn)方法。
具體代碼如下:
#include <iostream> using namespace std; #if !defined(_HUFFMANTREE_H_) #define _HUFFMANTREE_H_ /* * 哈夫曼樹(shù)結(jié)構(gòu) */ class HuffmanTree { public: unsigned int Weight; unsigned int Parent; unsigned int lChild; unsigned int rChild; }; typedef char **HuffmanCode; /* * 從結(jié)點(diǎn)集合中選出權(quán)值最小的兩個(gè)結(jié)點(diǎn) * 將值分別賦給s1和s2 */ void Select(HuffmanTree* HT,int Count,int *s1,int *s2) { unsigned int temp1=0; unsigned int temp2=0; unsigned int temp3; for(int i=1;i<=Count;i++) { if(HT[i].Parent==0) { if(temp1==0) { temp1=HT[i].Weight; (*s1)=i; } else { if(temp2==0) { temp2=HT[i].Weight; (*s2)=i; if(temp2<temp1) { temp3=temp2; temp2=temp1; temp1=temp3; temp3=(*s2); (*s2)=(*s1); (*s1)=temp3; } } else { if(HT[i].Weight<temp1) { temp2=temp1; temp1=HT[i].Weight; (*s2)=(*s1); (*s1)=i; } if(HT[i].Weight>temp1&&HT[i].Weight<temp2) { temp2=HT[i].Weight; (*s2)=i; } } } } } } /* * 霍夫曼編碼函數(shù) */ void HuffmanCoding(HuffmanTree * HT, HuffmanCode * HC, int *Weight, int Count) { int i; int s1,s2; int TotalLength; char* cd; unsigned int c; unsigned int f; int start; if(Count<=1) return; TotalLength=Count*2-1; HT = new HuffmanTree[(TotalLength+1)*sizeof(HuffmanTree)]; for(i=1;i<=Count;i++) { HT[i].Parent=0; HT[i].rChild=0; HT[i].lChild=0; HT[i].Weight=(*Weight); Weight++; } for(i=Count+1;i<=TotalLength;i++) { HT[i].Weight=0; HT[i].Parent=0; HT[i].lChild=0; HT[i].rChild=0; } //建造哈夫曼樹(shù) for(i=Count+1;i<=TotalLength;++i) { Select(HT, i-1, &s1, &s2); HT[s1].Parent = i; HT[s2].Parent = i; HT[i].lChild = s1; HT[i].rChild = s2; HT[i].Weight = HT[s1].Weight + HT[s2].Weight; } //輸出霍夫曼編碼 (*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*)); cd = new char[Count*sizeof(char)]; cd[Count-1]='\0'; for(i=1;i<=Count;++i) { start=Count-1; for(c = i,f = HT[i].Parent; f != 0; c = f, f = HT[f].Parent) { if(HT[f].lChild == c) cd[--start]='0'; else cd[--start]='1'; (*HC)[i] = new char [(Count-start)*sizeof(char)]; strcpy((*HC)[i], &cd[start]); } } delete [] HT; delete [] cd; } /* * 在字符串中查找某個(gè)字符 * 如果找到,則返回其位置 */ int LookFor(char *str, char letter, int count) { int i; for(i=0;i<count;i++) { if(str[i]==letter) return i; } return -1; } void OutputWeight(char *Data,int Length, char **WhatLetter, int **Weight,int *Count) { int i; char* Letter = new char[Length]; int* LetterCount = new int[Length]; int AllCount=0; int Index; int Sum=0; float Persent=0; for(i=0;i<Length;i++) { if(i==0) { Letter[0]=Data[i]; LetterCount[0]=1; AllCount++; } else { Index=LookFor(Letter,Data[i],AllCount); if(Index==-1) { Letter[AllCount]=Data[i]; LetterCount[AllCount]=1; AllCount++; } else { LetterCount[Index]++; } } } for(i=0;i<AllCount;i++) { Sum=Sum+LetterCount[i]; } (*Weight) = new int[AllCount]; (*WhatLetter) = new char[AllCount]; for(i=0;i<AllCount;i++) { Persent=(float)LetterCount[i]/(float)Sum; (*Weight)[i]=(int)(1000*Persent); (*WhatLetter)[i]=Letter[i]; } (*Count)=AllCount; delete [] Letter; delete [] LetterCount; } #endif void main() { HuffmanTree * HT = NULL; HuffmanCode HC; char Data[100]; char *WhatLetter; int *Weight; int Count; cout<<"請(qǐng)輸入一行文本數(shù)據(jù):"<<endl; cin>>Data; cout<<endl; OutputWeight(Data,strlen(Data), &WhatLetter, &Weight, &Count); HuffmanCoding(HT, &HC, Weight, Count); cout<<"字符 出現(xiàn)頻率 編碼結(jié)果"<<endl; for(int i = 0; i<Count; i++) { cout<<WhatLetter[i]<<" "; cout<<Weight[i]/1000.0<<"%\t"; cout<<HC[i+1]<<endl; } cout<<endl; }
希望本文所述對(duì)大家C++程序設(shè)計(jì)有所幫助。
- C++深入講解哈夫曼樹(shù)
- C++詳解哈夫曼樹(shù)的概念與實(shí)現(xiàn)步驟
- C++實(shí)現(xiàn)哈夫曼樹(shù)的方法
- C++實(shí)現(xiàn)哈夫曼樹(shù)編碼解碼
- C++實(shí)現(xiàn)哈夫曼樹(shù)算法
- C++ 哈夫曼樹(shù)對(duì)文件壓縮、加密實(shí)現(xiàn)代碼
- C++數(shù)據(jù)結(jié)構(gòu)之文件壓縮(哈夫曼樹(shù))實(shí)例詳解
- 解析C++哈夫曼樹(shù)編碼和譯碼的實(shí)現(xiàn)
- C++實(shí)現(xiàn)哈夫曼樹(shù)簡(jiǎn)單創(chuàng)建與遍歷的方法
- C++使用數(shù)組來(lái)實(shí)現(xiàn)哈夫曼樹(shù)
相關(guān)文章
c++的virtual和override作用及說(shuō)明
這篇文章主要介紹了c++的virtual和override作用及說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-11-11利用Matlab制作一款刮刮樂(lè)抽獎(jiǎng)特效
七夕節(jié)還不知道送啥,教你用MATLAB制作一款刮刮樂(lè)抽獎(jiǎng)特效,讓她的手氣決定她的禮物。文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2022-03-03C語(yǔ)言?超詳細(xì)講解算法的時(shí)間復(fù)雜度和空間復(fù)雜度
算法復(fù)雜度分為時(shí)間復(fù)雜度和空間復(fù)雜度。其作用:?時(shí)間復(fù)雜度是度量算法執(zhí)行的時(shí)間長(zhǎng)短;而空間復(fù)雜度是度量算法所需存儲(chǔ)空間的大小2022-03-03C++ 實(shí)現(xiàn)求最大公約數(shù)和最小公倍數(shù)
這篇文章主要介紹了c++ 實(shí)現(xiàn)求最大公約數(shù)和最小公倍數(shù)的相關(guān)資料,需要的朋友可以參考下2017-05-05數(shù)據(jù)結(jié)構(gòu)串的操作實(shí)例詳解
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)串的操作實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-07-07C/C++讀寫(xiě)文本文件、二進(jìn)制文件的方法
今天小編就為大家分享一篇C/C++讀寫(xiě)文本文件、二進(jìn)制文件的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-07-07