數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)3——哈夫曼編碼學(xué)生姓名：班 級(jí)：班內(nèi)序號(hào)：學(xué) 號(hào)：日 期：2013年11月24日1.實(shí)驗(yàn)要求利用二叉樹(shù)結(jié)構(gòu)實(shí)現(xiàn)赫夫曼編/解碼器。基本要求：1、 初始化(Init):能夠?qū)斎氲娜我忾L(zhǎng)度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立赫夫曼樹(shù)2、 建立編碼表(CreateTable)：利用已經(jīng)建好的赫夫曼樹(shù)進(jìn)行編碼，并將每個(gè)字符的編碼輸出。3、 編碼(Encoding)：根據(jù)編碼表對(duì)輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。4、 譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹(shù)對(duì)編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。5、 打印(Print):以直觀的方式打印赫夫曼樹(shù)(選作)6、 計(jì)算輸入的字符串編碼前和編碼后的長(zhǎng)度，并進(jìn)行分析，討論赫夫曼編碼的壓縮效果。2.程序分析2.1存儲(chǔ)結(jié)構(gòu)：structHNode{charc;//存字符內(nèi)容intweight;intlchild,rchild,parent;};structHCodechardata;charcode[100];}；//字符及其編碼結(jié)構(gòu)classHuffman{private:HNode*huffTree;//Huffman樹(shù)HCode*HCodeTable;//Huffman編碼表public:Huffman(void);voidCreateHTree(inta[],intn);//創(chuàng)建huffman樹(shù)voidCreateCodeTable(charb[],intn);//創(chuàng)建編碼表voidEncode(char*s,string*d);〃編碼voidDecode(char*s,char*d);//解碼voiddiffer(char*,intn);charstr2[100];//數(shù)組中不同的字符組成的串intdif;//str2[]的大小~Huffman(void);};結(jié)點(diǎn)結(jié)構(gòu)為如下所示:三叉樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)：structHNode//哈夫曼樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)體{ intweight;//結(jié)點(diǎn)權(quán)值intparent;//雙親指針intlchild;//左孩子指針intrchild;//右孩子指針chardata;//字符};示意圖為：intweightintparentintlchildintrchildCharc編碼表節(jié)點(diǎn)結(jié)構(gòu)：structHCode//編碼表結(jié)構(gòu)體{chardata;//字符charcode[100];//編碼內(nèi)容}；示意圖為：chardatacharcode[100]基本結(jié)構(gòu)體記錄字符和出現(xiàn)次數(shù):structnode{intnum;chardata;};示意圖為:intnumchardata2.關(guān)鍵算法分析(1).初始化：偽代碼：輸入需要編譯的文本內(nèi)容將輸入的內(nèi)容保存到數(shù)組str1中統(tǒng)計(jì)出現(xiàn)的字符數(shù)目，并且保存到變量count中統(tǒng)計(jì)出現(xiàn)的不同的字符，存到str2中，將str2的大小存到dif中時(shí)間復(fù)雜度O(n！).創(chuàng)建哈夫曼樹(shù)算法偽代碼：創(chuàng)建一個(gè)長(zhǎng)度為2*n-1的三叉鏈表將存儲(chǔ)字符及其權(quán)值的鏈表中的字符逐個(gè)寫入三叉鏈表的前n個(gè)結(jié)點(diǎn)的data域，并將對(duì)應(yīng)結(jié)點(diǎn)的孩子域和雙親域賦為空從三叉鏈表的第n個(gè)結(jié)點(diǎn)開(kāi)始，3.1從存儲(chǔ)字符及其權(quán)值的鏈表中取出兩個(gè)權(quán)值最小的結(jié)點(diǎn)x,y，記錄其下標(biāo)x,y。3.2將下標(biāo)為x和y的哈夫曼樹(shù)的結(jié)點(diǎn)的雙親設(shè)置為第i個(gè)結(jié)點(diǎn)3.3將下標(biāo)為x的結(jié)點(diǎn)設(shè)置為i結(jié)點(diǎn)的左孩子，將下標(biāo)為y的結(jié)點(diǎn)設(shè)置為i結(jié)點(diǎn)的右孩子，i結(jié)點(diǎn)的權(quán)值為x結(jié)點(diǎn)的權(quán)值加上y結(jié)點(diǎn)的權(quán)值，i結(jié)點(diǎn)的雙親設(shè)置為空根據(jù)哈夫曼樹(shù)創(chuàng)建編碼表時(shí)間復(fù)雜度O(n).創(chuàng)建編碼表算法偽代碼：初始化編碼表初始化一個(gè)指針，從鏈表的頭結(jié)點(diǎn)開(kāi)始，遍歷整個(gè)鏈表2.1將鏈表中指針當(dāng)前所指的結(jié)點(diǎn)包含的字符寫入編碼表中2.2得到該結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼樹(shù)的葉子結(jié)點(diǎn)及其雙親2.3如果哈夫曼樹(shù)只有一個(gè)葉子結(jié)點(diǎn)，將其字符對(duì)應(yīng)編碼設(shè)置為02.4如果不止一個(gè)葉子結(jié)點(diǎn)，從當(dāng)前葉子結(jié)點(diǎn)開(kāi)始判斷2.4.1如果當(dāng)前葉子結(jié)點(diǎn)是其雙親的左孩子，則其對(duì)應(yīng)的編碼為0，否則為12.4.2child指針指向葉子結(jié)點(diǎn)的雙親，parent指針指向child指針的雙親，重復(fù)2.4.1的操作2.5將已完成的編碼倒序2.6取得鏈表中的下一個(gè)字符輸出編碼表時(shí)間復(fù)雜度O(n)選擇兩個(gè)最小權(quán)值的函數(shù)算法偽代碼：從下標(biāo)為i=0的開(kāi)始遍歷。前兩次將x，y賦值為序號(hào)最小的兩個(gè)結(jié)點(diǎn)的地址序號(hào)。開(kāi)始進(jìn)行比較：進(jìn)行如下分類對(duì)于任何不存在父節(jié)點(diǎn)的結(jié)點(diǎn)：若x權(quán)值＜=y權(quán)值且i權(quán)值＞=y權(quán)值，貝9無(wú)疑i權(quán)值最大，為輸出x、y為權(quán)值較小的兩個(gè)故而x，y值不便；其余情況皆為x、i的權(quán)值是較小的兩個(gè)，令y賦值為i，則保證x、y權(quán)值是最小的兩個(gè)。若y權(quán)值＜=x權(quán)值且i權(quán)值＞=x權(quán)值，則i權(quán)值是最大，x、y不變。其余情況皆為i、y權(quán)值最小，令x賦值為i，保證x、y序號(hào)結(jié)點(diǎn)的權(quán)值最小完成如上循環(huán)，直至i=k則推出循環(huán)，第k個(gè)結(jié)點(diǎn)在樹(shù)的位置已經(jīng)確定時(shí)間復(fù)雜度O(n).將字符串倒序的函數(shù)(voidHuffmanTree::Reverse(char*pch))算法偽代碼：得到字符串的長(zhǎng)度初始化兩個(gè)記錄下標(biāo)的變量，一個(gè)為字符串開(kāi)頭字符所在的下標(biāo)i，另一個(gè)為字符串結(jié)尾字符所在的下標(biāo)j將下標(biāo)為i和j的字符交換i++,j--時(shí)間復(fù)雜度O(n).編碼函數(shù)算法偽代碼：從開(kāi)頭的字符開(kāi)始，逐一對(duì)a中的字符進(jìn)行編碼在編碼表中查找與當(dāng)前字符對(duì)應(yīng)的字符如果找到了與當(dāng)前字符對(duì)應(yīng)的編碼表中的字符，將其編碼追加到解碼串的末尾。重復(fù)以上步驟，直到所有待編碼串中的字符都編碼完畢輸出編碼后的字符串時(shí)間復(fù)雜度O(n)(7),解碼函數(shù)(voidHuffman::Decode())算法偽代碼：得到指向哈夫曼樹(shù)的根結(jié)點(diǎn)的指針和指向待解碼串中的第1個(gè)字符的指針逐個(gè)讀取待解碼串中的字符，若為0,則指向哈夫曼樹(shù)當(dāng)前結(jié)點(diǎn)的指針指向當(dāng)前結(jié)點(diǎn)的左孩子，若為1，則指向當(dāng)前結(jié)點(diǎn)的右孩子指向待解碼串的指針指向解碼串中的下一個(gè)字符，直到指向哈夫曼樹(shù)結(jié)點(diǎn)的指針的孩子結(jié)點(diǎn)為空如果哈夫曼樹(shù)只有一個(gè)葉子結(jié)點(diǎn)，直接將待解碼串中的編碼轉(zhuǎn)換為對(duì)應(yīng)的字符如果指向哈夫曼樹(shù)結(jié)點(diǎn)的指針的孩子結(jié)點(diǎn)已經(jīng)為空，則將葉子結(jié)點(diǎn)下標(biāo)對(duì)應(yīng)的字符追加到解碼串中。輸出解碼串時(shí)間復(fù)雜度O(n)程序運(yùn)行結(jié)果1.主函數(shù)流程圖

C:\Windoww'qystem32\cmd.exe請(qǐng)送擇功能”輸入編詩(shī)字符呂Z喻出編袒表3輸出字符串編誦及玉縮比4解毋X底出）1請(qǐng)輸KIlouedataStructure.IloueComputer.IwilltrympbesttostuidpdataStpucture隋訝擇（1繼續(xù)運(yùn)行聘溟出）1請(qǐng)遂擇功能（1輸入編譯字符呂2喻出編袒表3輸出宇符串編碼茨玉縮LL4解有S退出）nueij(htLChildRChildparentcharcade&13-1-14111111-1-1陰r-Bl1BQB22-1-12&■Q311G31-1123c011OS143-1-130I01111b2-1-12bsMU11164-1-132a09Q071-1-124b011010R2-1-1S7二R1RRfi93-1-131d11S1610C-113Gc1310111-11241011011124-1-132109S1132-1-1k7nm皿144-1-133o0310151-1-125D011160166-1-11*1?11172-1-1283Q1S1G1811-1140t19B196-1-137unee2U2-1-12UuMltdll211-1-125VI011161223-1-131y11011J?32133924271129VJ3252152136N02G42533N327431334\9ZU417ZM34\a294232435\330525435\3316922明328%12^38

main.cpp#include"huffman.h”voidmain(){HuffmanH;inti;charstr1[100]={'\0'};stringd;intcount=0;do{cout<<"請(qǐng)選擇功能（輸入編譯字符串2輸出編碼表3輸出字符串編碼及壓縮比4解碼5退出）"<<endl;intn;cin>>n;charch='a';cin.get(ch);switch(n){case1:{cout<<”請(qǐng)輸入”<<endl;cin.getline(str1,100);intm=0;while(str1[m++])count++;}break;case2:{H.differ(str1,count);H.CreateCodeTable(H.str2,H.dif);}break;case3:{H.Encode(str1,&d);}break;case4:{cout<<"請(qǐng)輸入解碼數(shù)據(jù)"<<endl;chars[200]=('\0'};chard[100]=('\0'};cin.getline(s,200,'\n');H.Decode(s,d);cout<<"解碼數(shù)據(jù)為："<<d<<endl;}break;case5:break;default:cout<<'請(qǐng)輸入正確序號(hào)”<<endl;break;}cout<<"請(qǐng)選擇(繼續(xù)運(yùn)行0退出)"<<endl;cin>>i;}while(i);cout<<”謝謝使用”<<endl;}huffman.h#pragmaonce#include<iostream>#include<string>#include<iomanip>usingnamespacestd;structHNode{charc;//存字符內(nèi)容intweight;intlchild,rchild,parent;};structHCode{chardata;charcode[100];};〃字符及其編碼結(jié)構(gòu)classHuffman{private:HNode*huffTree;//Huffman樹(shù)HCode*HCodeTable;//Huffman編碼表public:Huffman(void);voidCreateHTree(inta[],intn);//創(chuàng)建huffman樹(shù)voidCreateCodeTable(charb[],intn);//創(chuàng)建編碼表voidEncode(char*s,string*d);〃編碼voidDecode(char*s,char*d);//解碼voiddiffer(char*,intn);charstr2[100];//數(shù)組中不同的字符組成的串intdif;//str2[]的大小~Huffman(void);};huffman.cpp#include"huffman.h"Huffman::Huffman(void){}voidSelect(HNode*hTree,intn,int&i1,int&i2){inti;〃找一個(gè)比較值的起始值for(i=0;i<n;i++)//找i1{if(hTree[i].parent==-1){i1=i;break;}}i++;for(;i<n;i++)//找i2{if(hTree[i].parent==-1){i2=i;break;}}if(hTree[i1].weight>hTree[i2].weight)//i1指向最小的{intj;j=i2;i2=i1;i1=j;}〃開(kāi)始找最小的兩個(gè)i++;for(;i<n;i++){if(hTree[i].parent==-1&&hTree[i].weight<hTree[i1].weight){i2=i1;i1=i;}elseif(hTree[i].parent==-1&&hTree[i].weight<hTree[i2].weight){i2=i;}}}voidReverse(charc[]){intn=0;chartemp;while(c[n+1]!='\0')//統(tǒng)計(jì)字符個(gè)數(shù){n++;}for(inti=0;i<=n/2;i++){temp=c[i];c[i]=c[n-i];c[n-i]=temp;}}〃找到只含有不同字符的數(shù)組，權(quán)重及其大小voidHuffman::differ(char*str,intn){char*temp=newchar[n];//申請(qǐng)動(dòng)態(tài)數(shù)組存儲(chǔ)字符串以便之后對(duì)字符串排序for(inti=0;i<n;i++){temp[i]=*(str+i);}charctemp;for(inti=0;i<n-1;i++)//冒泡排序法,排序以后方便統(tǒng)計(jì)不同字符串出現(xiàn)的個(gè)數(shù){for(intj=0;j<n-1-i;j++){if(temp[j]>temp[j+1]){ctemp=temp[j];temp[j]=temp[j+1];temp[j+1]=ctemp;}}}dif=1;for(inti=1;i<n;i++)//統(tǒng)計(jì)不同字符個(gè)數(shù){if(temp[i]!=temp[i-1]){dif++;}int*a=newint[dif];//用a[dif]來(lái)統(tǒng)計(jì)權(quán)重intl=0;//統(tǒng)計(jì)不同字符出現(xiàn)的頻度intk=0;//控制哈夫曼數(shù)組下標(biāo)ctemp=temp[0];//做標(biāo)記for(inti=0;i<=n;i++)//因?yàn)樗冉?jīng)排序了{(lán)if(temp[i]==ctemp){l++;//統(tǒng)計(jì)同字符出現(xiàn)的頻度if(i==n-1)a[k]=l;}else{str2[k]=ctemp;a[k]=l;ctemp=temp[i];k++;l=1;}}delete[]temp;//釋放動(dòng)態(tài)內(nèi)存空間CreateHTree(a,dif);}voidHuffman::CreateHTree(inta[],intn){ 〃根據(jù)權(quán)重?cái)?shù)組a[1到n]初始化Huffman樹(shù)huffTree=newHNode[2*n-1];for(inti=0;i<n;i++){huffTree[i].weight=a[i];huffTree[i].lchild=-1;huffTree[i].rchild=-1;huffTree[i].parent=-1;huffTree[i].c=str2[i];}intli,ri;for(inti=n;i<2*n-1;i++)〃開(kāi)始建Huffman樹(shù){ 〃從?i-1中選出兩個(gè)權(quán)值最小的結(jié)點(diǎn)，Select(huffTree,i,li,ri);huffTree[li].parent=huffTree[ri].parent=i;huffTree[i].weight=huffTree[li].weight+huffTree[ri].weight;huffTree[i].lchild=li;huffTree[i].rchild=ri;huffTree[i].parent=-1;huffTree[i].c='\0';}}voidHuffman::CreateCodeTable(charb[],intn){HCodeTable=newHCode[n];//申請(qǐng)與不同字符個(gè)數(shù)對(duì)應(yīng)的動(dòng)態(tài)空間，以存儲(chǔ)不同字符代表的編碼for(inti=0;i<n;i++){HCodeTable[i].data=huffTree[i].c;intic=i;intip=huffTree[i].parent;intk=0;while(ip!=-1){if(ic==huffTree[ip].lchild)//左孩子標(biāo)"HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';〃右孩子標(biāo)‘’k++;ic=ip;ip=huffTree[ic].parent;}HCodeTable[i].code[k]='\0';//字符編碼串最后添加結(jié)束符Reverse(HCodeTable[i].code);}cout<<setiosflags(ios::left)<<setw(5)<<"n"<<setw(12)<<"weight"<<setw(12)<<"LChild"<<setw(12)<<"RChild"<<setw(12)<<"parent"<<setw(12)<<"char"<<setw(12)<<"code"<<endl;for(inti=0;i<2*dif-1;i++){if(i<dif){cout<<setiosflags(ios::left)<<setw(5)<<i<<setw(12)<< huffTree[i].weight<<setw(12)<<huffTree[i].lchild<<setw(12)<< huffTree[i].rchild<<setw(12)<<huffTree[i].parent<<setw(12)<<HCodeTable[i].data<<setw(12)<<HCodeTable[i].code<<endl;}elsecout<<setiosflags(ios::left)<<setw(5)<<i<<setw(12)<< huffTree[i].weight<<setw(12)<<huffTree[i].lchild<<setw(12)<< huffTree[i].rchild<<setw(12)<<huffTree[i].parent<<setw(12)<<"\\0”<<setw