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

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

2、>*huftree;哈夫曼樹(shù)的結(jié)點(diǎn)數(shù)組char*hufcodes;哈夫曼編碼數(shù)組public:Huffma nTree(i ntweight, int n);構(gòu)造指定權(quán)值集合的哈夫曼樹(shù)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)值集合的哈夫曼樹(shù)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;默認(rèn)最大權(quán)值HuffmanTree:HuffmanTree(intwe

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

5、huftreei.left huftreei.right = -1;for(i=0;i<n-1;i+)構(gòu)造n-1個(gè)2度結(jié)點(diǎn)，每循環(huán)一次，構(gòu)造一個(gè) 2度結(jié)點(diǎn)int mini, min2, x1, x2;mi n1= mi n2 = Max_Weight;選擇最小和次最小權(quán)值，初值為最大權(quán)值x1=x2=-1;記錄兩個(gè)無(wú)父母的最小權(quán)值結(jié)點(diǎn)下標(biāo)for (int j=0; jvn+i;j+)查找兩個(gè)無(wú)父母的最小權(quán)值結(jié)點(diǎn)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é)點(diǎn)的下標(biāo)else if (huftreej.datavmin2&&huftreej.pare nt=-1)min2 = huftreej.data;min2 記下次小權(quán)值x2 = j;x2 記下次小權(quán)值結(jié)點(diǎn)的下標(biāo)huftreex1.pare nt=n+i;將找出的兩棵權(quán)值最小的子樹(shù)合并為一棵子樹(shù)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()獲得當(dāng)前哈夫曼樹(shù)的哈夫曼編碼int n=leafNum;hufcodes = newchar* n;求n個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼for (int i=0; i<n; i+)char *code = newchar n;一個(gè)字符串表示一個(gè)編碼code n-1='0'int start=n-1;int child = i;int pare nt = huftreechild.pare nt;while(pare nt!=-1)/由葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)循環(huán)

8、start-;if (huftreepare nteft=child)codestart='0'左孩子結(jié)點(diǎn)編碼為0elsecodestart='1：右孩子結(jié)點(diǎn)編碼為1child = pare nt;pare nt = huftreechild.pare nt; hufcodesi=code+start;編碼數(shù)組各元素存儲(chǔ)由start開(kāi)始的字符串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"號(hào)字符："<vtablek-1vv" 有"<<m<<