數(shù)據(jù)結(jié)構(gòu)課設(shè)--哈夫曼二叉樹

1、數(shù)據(jù)結(jié)構(gòu)課設(shè)-哈夫曼二叉樹hufma ntree.h構(gòu)造哈夫曼樹并獲得哈夫曼編碼#in elude <fstream.h>#inelude <stdio.h>#in elude <stri ng.h>#in elude <proeess.h>template <elass T>struetTriNode二叉樹的三叉靜態(tài)鏈表結(jié)點Tdata;數(shù)據(jù)域intpare nt,left,righ t;父母結(jié)點和左、右孩子結(jié)點下標;classHuffma nTree哈夫曼樹類private:leafNum;int葉子結(jié)點個數(shù)TriNodev int

2、>*huftree;哈夫曼樹的結(jié)點數(shù)組char*hufcodes;哈夫曼編碼數(shù)組public:Huffma nTree(i ntweight, int n);構(gòu)造指定權(quán)值集合的哈夫曼樹Huffma nTree();int deep(i nt i);void prin t(char table,char stri ng);voidprin tk(i nti,char table);/凹入輸出private:void createHuffma nTree(i nt weight, i nt n);創(chuàng)建指定權(quán)值集合的哈夫曼樹voidgetHuffma nCode();獲得哈夫曼編碼;void

3、Huffma nTree:pri ntk(i nt i,char table) if(i>-1)prin tk(huftreei.left,table);for(i nt j=O;jv=deep(i);j+)cout«""cout<<huftreei.data;if(i<=leafNum-1)cout<<tablei;cout«e ndl;prin tk(huftreei.right,table);/凹入表示constMax_Weight=9999;默認最大權(quán)值HuffmanTree:HuffmanTree(intwe

4、ight, int n)構(gòu)造指定權(quán)值集合的哈夫曼樹n個葉子結(jié)點createHuffma nTree(weight, n); getHuffma nCode();voidHuffma nTree:createHuffma nTree(i ntweight, int n)創(chuàng)建指定權(quán)值集合的哈夫曼樹leafNum = n;huftree = new TriNode<i nt>2* n-1;/n個葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點int i;for(i=0;i<n;i+)結(jié)點數(shù)組初始化有n個葉子結(jié)點huftreei.data = weighti;huftreei.pare nt=

5、huftreei.left huftreei.right = -1;for(i=0;i<n-1;i+)構(gòu)造n-1個2度結(jié)點，每循環(huán)一次，構(gòu)造一個 2度結(jié)點int mini, min2, x1, x2;mi n1= mi n2 = Max_Weight;選擇最小和次最小權(quán)值，初值為最大權(quán)值x1=x2=-1;記錄兩個無父母的最小權(quán)值結(jié)點下標for (int j=0; jvn+i;j+)查找兩個無父母的最小權(quán)值結(jié)點if(huftreej.data<mi n1&&huftreej.pare nt=-1)min2 = min1; x2 = x1;min1 = huftreej

6、.data;/mi n1記下最小權(quán)值x1=j;x1記下最小權(quán)值結(jié)點的下標else if (huftreej.datavmin2&&huftreej.pare nt=-1)min2 = huftreej.data;min2 記下次小權(quán)值x2 = j;x2 記下次小權(quán)值結(jié)點的下標huftreex1.pare nt=n+i;將找出的兩棵權(quán)值最小的子樹合并為一棵子樹huftreex2.pare nt= n+i;huftree n+i.data=huftreex1.data+huftreex2.data;huftree n+i.pare nt = -1;huftree n+i .left

7、 = x1;huftree n+i.right = x2;voidHuffma nTree:getHuffma nCode()獲得當前哈夫曼樹的哈夫曼編碼int n=leafNum;hufcodes = newchar* n;求n個葉子結(jié)點的哈夫曼編碼for (int i=0; i<n; i+)char *code = newchar n;一個字符串表示一個編碼code n-1='0'int start=n-1;int child = i;int pare nt = huftreechild.pare nt;while(pare nt!=-1)/由葉結(jié)點向上直到根結(jié)點循環(huán)

8、start-;if (huftreepare nteft=child)codestart='0'左孩子結(jié)點編碼為0elsecodestart='1：右孩子結(jié)點編碼為1child = pare nt;pare nt = huftreechild.pare nt; hufcodesi=code+start;編碼數(shù)組各元素存儲由start開始的字符串voidHuffma nTree:pri nt(chartable,charstri ng)ofstream fou t;fout.ope n("code.dat",ios:out); cout«&q

9、uot;n 哈夫曼編碼：n"for (int i=0; i<leafNum; i+)cout<<tablei<<" : "<<hufcodesi<<endl;bool flag=false;cout«"哈夫曼編碼："<<endl; for(i nt j=O;stri ngj!='O'j+)for(i=0;i<leafNum;i+)if(stri ngj=tablei) flag=true;elseflag=false;if(flag)fout<

10、;<hufcodesi; cout<<hufcodesi; fout.close();Huffma nTree:Huffma nTree() delete huftree;delete hufcodes; int Huffma nTree:deep(i nt i)in t j=0;int pare nt = huftreei.pare nt;while(pare nt!=-1)j+;parent = huftreepare nt.pare nt;return j;main .cpp#include <iostream.h>#include "Hufman

11、Tree.h" int main()int i,j,n=O;int k=O,a=O;int weight10;char string50;char table26;coutvv"輸入字符串："vvendl;cin>>string;for(i=0;stringi!='0'i+)n+;for(i=0;i<n;i+)int m=0;bool flag=true;for(int p=0;p<k;p+) if(tablep=stringi) flag=false;if(flag)for(j=i;j<n;j+)if(stringi=stringj) m+;tablek=stringi;k+;coutvvkvv"號字符："<vtablek-1vv" 有"<<m<<