數(shù)據(jù)結(jié)構(gòu)哈夫曼編譯碼器

3.2.2設(shè)計(jì)流程圖圖2.1總流程圖定義哈夫曼結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)和哈夫曼編碼存儲(chǔ)結(jié)構(gòu)，之后定義一個(gè)結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)數(shù)組用來存放結(jié)點(diǎn)信息，和定義一個(gè)編碼存儲(chǔ)結(jié)構(gòu)數(shù)組用來存放字符的哈夫曼編碼，同時(shí)定義全局?jǐn)?shù)組存放字符和它的使用頻度。先將已建立好的二叉樹初始化，再對(duì)其中的葉結(jié)點(diǎn)其賦予字符名和對(duì)應(yīng)使用頻度作為結(jié)點(diǎn)名和結(jié)點(diǎn)權(quán)值，最后通過哈夫曼算法構(gòu)造哈夫曼樹，同時(shí)在屏幕輸出哈夫曼樹。通過已建立好的哈夫曼樹再對(duì)字符進(jìn)行二進(jìn)制編碼，編碼結(jié)束后，對(duì)應(yīng)每個(gè)字符都有一個(gè)二進(jìn)制編碼，此編碼即為哈夫曼編碼，將字符及其哈夫曼編碼存放到哈夫曼編碼存儲(chǔ)結(jié)構(gòu)體數(shù)組中去，構(gòu)成哈夫曼編碼表，同時(shí)在屏幕上輸出哈夫曼編碼表。編碼函數(shù)執(zhí)行，即對(duì)輸入的字符串根據(jù)哈夫曼編碼表進(jìn)行編碼，將字符串的二進(jìn)制編碼存放到一個(gè)字符數(shù)組中去。建立文件，將字符數(shù)組中的二進(jìn)制編碼寫入文件，這需要定義輸出流類的對(duì)象并與文件關(guān)聯(lián)，通過操作對(duì)象來操作文件的數(shù)據(jù)寫入。將文件中的二進(jìn)制編碼進(jìn)行譯碼，這需要定義輸入流類的對(duì)象并與文件關(guān)聯(lián)，將文件中的編碼讀取到另一字符數(shù)組中去，調(diào)用譯碼函數(shù)進(jìn)行譯碼。結(jié)束。4.1哈夫曼樹的建立4.1.1哈夫曼樹的存儲(chǔ)結(jié)構(gòu) 為了實(shí)現(xiàn)通過哈夫曼算法建立哈夫曼樹，首先要定義哈夫曼樹的存儲(chǔ)結(jié)構(gòu)。由于構(gòu)造哈夫曼樹之后，編碼時(shí)要從葉結(jié)點(diǎn)出發(fā)走一條從葉結(jié)點(diǎn)到根的路徑，而譯碼時(shí)要從根結(jié)點(diǎn)出發(fā)走一條從根到葉結(jié)點(diǎn)的路徑。對(duì)于每個(gè)結(jié)點(diǎn)而言，既需知道雙親的信息，又需知道孩子的信息。因此，可以使用帶雙親的孩子鏈表作為結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)。由哈夫曼算法可知，如果哈夫曼有n個(gè)葉結(jié)點(diǎn)，則最終生成的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)。因此，可以用一個(gè)長(zhǎng)度為2n的一維數(shù)組存放哈夫曼樹的所有結(jié)點(diǎn)。詳細(xì)定義如下：#defineLeafnum27#defineHufnum2*LeafnumtypedefcharDataType;typedefstructTnode{ DataTypename; doubleweight; intlchild,rchild,parent;}Huftree;HuftreeTree[Hufnum]; 其中，name表示結(jié)點(diǎn)數(shù)據(jù)的名稱（即字符名稱），weight表示結(jié)點(diǎn)的權(quán)值（即字符使用頻度），lchild、rchild分別是結(jié)點(diǎn)的左、右孩子在數(shù)組中的下標(biāo)值，葉結(jié)點(diǎn)的左右孩子的下標(biāo)值均為0；parent表示結(jié)點(diǎn)雙親在數(shù)組中的位置。它的主要作用有兩點(diǎn)：第一，區(qū)分根結(jié)點(diǎn)和非根結(jié)點(diǎn)；第二，使得查找某個(gè)結(jié)點(diǎn)的雙親變的更為簡(jiǎn)單。若parent=0，則該結(jié)點(diǎn)是樹的根結(jié)點(diǎn)，否則為非根結(jié)點(diǎn)。因?yàn)榘焉种械膬煽枚鏄浜喜⒊梢豢枚鏄鋾r(shí)，必須從森林的所有結(jié)點(diǎn)中選取兩個(gè)根結(jié)點(diǎn)的權(quán)值為最小的結(jié)點(diǎn)，此時(shí)就是根據(jù)parent來區(qū)分根與非根結(jié)點(diǎn)的。4.1.2建立哈夫曼樹 本設(shè)計(jì)只對(duì)26個(gè)英文大寫字符及空格進(jìn)行了哈夫曼編碼，各字符及對(duì)應(yīng)使用頻度如下表所示：表4.1字符及其使用頻度字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161需要定義全局?jǐn)?shù)組來存放這些字符名稱和對(duì)應(yīng)頻度：charch[]={'\0','','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};floatw[]={0,186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1}; 定義函數(shù)CreatTreeHuffman，其中包括對(duì)已建立好的哈夫曼樹的初始化，即將結(jié)點(diǎn)數(shù)據(jù)名稱初始化為’\0’，將結(jié)點(diǎn)權(quán)值、結(jié)點(diǎn)雙親及左右孩子的下標(biāo)值都初始化為0；對(duì)已初始化的哈夫曼樹賦值，將全局?jǐn)?shù)組ch4.2哈夫曼編碼表的建立4.2.1哈夫曼編碼表的存儲(chǔ)結(jié)構(gòu)typedefstructCnode{ charbits[Leafnum+1]; intstart; charch;}hufcode; 由于葉子結(jié)點(diǎn)總數(shù)即字符個(gè)數(shù)為L(zhǎng)eafnum，故不等長(zhǎng)編碼的長(zhǎng)度不會(huì)超過Leafnum，再加上結(jié)束符號(hào)’\0’4.2.2建立哈夫曼編碼表 建立哈夫曼編碼表即建立一個(gè)表格用來存儲(chǔ)每個(gè)字符名稱和對(duì)應(yīng)的哈夫曼編碼，此過程建立在已經(jīng)構(gòu)造好的哈夫曼樹上，從葉結(jié)點(diǎn)開始，沿著雙親鏈向上，記錄沿途經(jīng)過分支上的二進(jìn)制編碼，直到到達(dá)根結(jié)點(diǎn)，于是對(duì)應(yīng)每一個(gè)字符都有一個(gè)二進(jìn)制串，即它的哈夫曼編碼，用上面定義的哈夫曼編碼表存儲(chǔ)結(jié)構(gòu)數(shù)組存放起來，即存在位串?dāng)?shù)組bits中。4.3編碼 本程序的功能是能對(duì)從鍵盤輸入的任意有限長(zhǎng)度的字符串（限定在大寫英文字符和空格）進(jìn)行哈夫曼編碼，因此需要定義函數(shù)WritecodeHuffman來實(shí)現(xiàn)對(duì)輸入的字符串逐個(gè)進(jìn)行編碼，此過程實(shí)質(zhì)上是將字符與編碼表里的字符名稱相比較，當(dāng)名稱一致時(shí)，就輸出對(duì)應(yīng)字符的bits數(shù)組中的二進(jìn)制編碼，然后依次輸出每個(gè)字符的哈夫曼編碼，將他們連續(xù)的顯示在屏幕上。4.4文件寫入由于要將這些二進(jìn)制串寫入文件，所以事先再定義一個(gè)全局字符數(shù)組Huffmancode來存儲(chǔ)這些二進(jìn)制串。在主函數(shù)先在某目錄下建立一個(gè).txt文件，名為codefile，再定義了一個(gè)輸出流類ofstream的對(duì)象ofs，定義ofs的同時(shí)將其與文件codefile關(guān)聯(lián)，于是，就可以通過操作ofs來實(shí)現(xiàn)文件數(shù)據(jù)的寫入，即將字符數(shù)組Huffmancode中的二進(jìn)制編碼寫入文件。[1]4.5譯碼 譯碼的過程與編碼的過程相反，先將codefile文件中的二進(jìn)制編碼讀出來，這時(shí)在主函數(shù)中也定義一個(gè)輸入流類ifstream的對(duì)象ifs，同時(shí)將它與文件codefile關(guān)聯(lián)，通過ifs讀取codefile文件中的二進(jìn)制編碼，存放到數(shù)組buffer中，再通過譯碼函數(shù)進(jìn)行譯碼，TranscodeHuffman譯碼函數(shù)定義如下：voidTranscodeHuffman(Hufcodecode[],Huftreetree[],chars[]){ inti; char*q=NULL; i=Hufnum-1;q=s; while(*q!='\0') { if(*q=='0')i=tree[i].lchild; if(*q=='1')i=tree[i].rchild; if((tree[i].lchild==0)&&(tree[i].rchild==0)) { cout<<code[i].ch; i=Hufnum-1; } q++; } cout<<endl;} 該函數(shù)帶三個(gè)參數(shù)，分別是已建立好的哈夫曼樹結(jié)點(diǎn)數(shù)組，哈夫曼編碼表數(shù)組和需要進(jìn)行譯碼的字符數(shù)組，該字符數(shù)組存放的即為由0、1組成的一串編碼，函數(shù)中設(shè)置字符類型指針q開始指向字符數(shù)組的第一個(gè)字符，若為0，則進(jìn)入左孩子，否則進(jìn)入右孩子，再執(zhí)行q++，直到某結(jié)點(diǎn)的左右孩子下標(biāo)值均為0的時(shí)候，此時(shí)的結(jié)點(diǎn)即為葉結(jié)點(diǎn)，于是輸出對(duì)應(yīng)字符，再將起始結(jié)點(diǎn)設(shè)為根結(jié)點(diǎn)，重復(fù)上述過程，直到翻譯出所有字符。測(cè)試結(jié)果5.1哈夫曼樹輸出圖5.1哈夫曼樹輸出第一列是字符序號(hào)，也就是在建立的存儲(chǔ)結(jié)構(gòu)數(shù)組tree中各結(jié)點(diǎn)的下標(biāo)值，1到27對(duì)應(yīng)的是葉結(jié)點(diǎn)；第二列是字符名稱，每個(gè)葉結(jié)點(diǎn)對(duì)應(yīng)一個(gè)字符；第三列是字符使用頻度，也即葉結(jié)點(diǎn)的權(quán)值；后面三列則列出了每個(gè)結(jié)點(diǎn)雙親及左右孩子在結(jié)構(gòu)數(shù)組中的下標(biāo)值，雖然是以表格方式表示這棵樹，但從中可以體現(xiàn)出整個(gè)哈夫曼樹的樹形結(jié)構(gòu)。5.2哈夫曼編碼表輸出根據(jù)哈夫曼樹所建立的哈夫曼編碼表輸出如圖5.2．圖5.2哈夫曼編碼表輸出 哈夫曼編碼表第一列和第二列仍給出字符序號(hào)和字符名稱，第三列是字符編碼，即對(duì)應(yīng)于各個(gè)字符的哈夫曼編碼。此表列出了所有27個(gè)字符和與其對(duì)應(yīng)的哈夫曼編碼，每個(gè)哈夫曼編碼都存在編碼表結(jié)構(gòu)數(shù)組中，這樣，對(duì)任意輸入的字符串（限定在大寫英文字符和空格）進(jìn)行哈夫曼編碼時(shí)，只需逐個(gè)按照表格找到其對(duì)應(yīng)編碼，再將它們存放到一起，即可得到字符串的哈夫曼編碼。5.3編碼和譯碼對(duì)任意字符串的編碼和譯碼運(yùn)行如圖5.3．圖4.3字符串編碼和譯碼結(jié)果輸出 主函數(shù)執(zhí)行時(shí)，先調(diào)用CreatTreeHuffman和CreatcodeHuffman兩函數(shù)建立哈夫曼樹和哈夫曼編碼表，對(duì)應(yīng)也輸出顯示它們。于是再進(jìn)入功能執(zhí)行部分，即函數(shù)WritecodeHuffman，在窗口中顯示“請(qǐng)輸入字符串：”，于是手動(dòng)輸入任意大寫英文字符或空格，即可將它的哈夫曼編碼顯示出來。5.4文件讀寫 本程序還實(shí)現(xiàn)了文件的讀寫過程，即將輸入字符串的二進(jìn)制編碼寫入文件codefile中，也能讀出codefile文件中的二進(jìn)制編碼再進(jìn)行譯碼便顯示到終端上，這個(gè)過程即可視為實(shí)際生活中兩計(jì)算機(jī)之間模擬數(shù)據(jù)傳輸過程，將發(fā)送方的信息數(shù)據(jù)（字符串）進(jìn)行哈夫曼編碼，得到二進(jìn)制串，即文件寫入過程；接收方再將二進(jìn)制串翻譯成信息，即文件讀取過程。codefile文件打開如圖5-4．主函數(shù)中先創(chuàng)建一個(gè)文件名為”d:\\codefile.txt”的文本文件，再定義一個(gè)文件輸出流類ofstream的對(duì)象ofs，并將其與文件codefile關(guān)聯(lián)到一起，再將之前存放字符串哈夫曼編碼的數(shù)組寫入文件，隨后定義一個(gè)文件輸入流類ifstream的對(duì)象ifs，并將其與文件codefile關(guān)聯(lián)，同時(shí)定義一個(gè)緩存字符數(shù)組buffer用于存放從codefile文件中讀取出來的二進(jìn)制編碼，最后調(diào)用譯碼函數(shù)transcodehuffman對(duì)buffer中的編碼進(jìn)行譯碼，把譯出的字符顯示出來。總結(jié)及調(diào)試分析附錄：源代碼#include<iostream>#include<fstream>usingnamespacestd;#defineleafnum27#definehufnum2*leafnum#definemaxdouble9999.9typedefchardatatype;typedefstructtnode//哈夫曼樹結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu){ datatypename; doubleweight; intlchild,rchild,parent;}huftree;typedefstructcnode//哈夫曼編碼表結(jié)構(gòu){ charbits[leafnum+1]; intstart; charch;}hufcode;hufcodecode[leafnum+1];huftreetree[hufnum+1];charhuffmancode[1000];charch[]={'\0','','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};floatw[]={0,186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};voidcreattreehuffman(huftreetree[])//建立哈夫曼樹{ inti,j,p1,p2; doubleleast1,least2; for(i=1;i<=hufnum;i++) { tree[i].name='\0'; tree[i].parent=0; tree[i].lchild=0; tree[i].rchild=0; tree[i].weight=0.0; } for(i=1;i<=leafnum;i++) { tree[i].name=ch[i]; tree[i].weight=w[i]; } for(i=leafnum+1;i<=hufnum;i++) { p1=0;p2=0;least1=least2=maxdouble; for(j=1;j<i;j++) if(tree[j].parent==0) if(tree[j].weight<least1) { least2=least1; least1=tree[j].weight; p2=p1; p1=j; } else { if(tree[j].weight<least2) { least2=tree[j].weight; p2=j; } } tree[p1].parent=i; tree[p2].parent=i; tree[i].lchild=p1; tree[i].rchild=p2; tree[i].weight=tree[p1].weight+tree[p2].weight; } tree[hufnum-1].parent=0;}voidcreatcodehuffman(hufcodecode[],huftreetree[])//建立哈夫曼編碼{ inti,c,p; hufcodebuf; for(i=1;i<=leafnum;i++) { buf.ch=ch[i]; buf.start=leafnum; c=i; p=tree[i].parent; while(p!=0) { buf.start--; if(tree[p].lchild==c) buf.bits[buf.start]='0'; elsebuf.bits[buf.start]='1'; c=p; p=tree[p].parent; } code[i]=buf; }}voidwritecodehuffman(hufcodecode[],huftreetree[])//哈弗曼編碼{ inti,j,k,n=0; charc[100]; cout<<"請(qǐng)輸入字符串:"<<endl; gets(c); cout<<endl; cout<<"則字符串的哈夫曼編碼為:"<<endl; for(i=0;i<strlen(c);i++) { for(j=1;j<=leafnum;j++) if(c[i]==tree[j].name) for(k=code[j].start;k<leafnum;k++) { cout<<code[j].bits[k]; huffmancode[n]=code[j].bits[k]; n++; } }}voidtranscodehuffman(hufcodecode[],huftreetree[],chars[])//哈夫曼譯碼{ inti; char*q=NULL; i=hufnum-1;q=s; while(*q!='\0') { if(*q=='0')i=tree[i].lchild; if(*q=='1')i=tree[i].rchild; if((tree[i].lchild==0)&&(tree[i].rchild==0)) { cout<<code[i].ch; i=hufnum-1; } q++; } cout<<endl;}voidprinttreehuffman(huftreetree[])//輸出哈夫曼樹{ inti; cout<<"根據(jù)字符的使用概率所建立的哈夫曼數(shù)為:"<<endl; cout<<"字符序號(hào)字符名稱字符頻率雙親位置左孩子右孩子"<<endl; for(i=1;i<hufnum;i++) { cout<<""<<i<<"\t"<<tree[i].name<<"\t"; cout<<tree[i].weight<<"\t"<<tree[i].parent<<"\t"<<tree[i].lchild<<""<<tree[i].rchild<<endl; }}voidprintcodehuffman(hufcodecode[])//輸出每個(gè)字符的哈夫曼編碼{ inti,j; cout<<"根據(jù)哈夫曼樹對(duì)字符所建立