數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三哈夫曼編碼

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)3——哈夫曼樹學(xué)生姓名：XXX班級(jí)：班內(nèi)序號(hào)：學(xué)號(hào)：日期：2012年12月1日1．實(shí)驗(yàn)要求【實(shí)驗(yàn)?zāi)康摹客ㄟ^選擇下面兩個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：掌握二叉樹基本操作的實(shí)現(xiàn)方法了解赫夫曼樹的思想和相關(guān)概念學(xué)習(xí)使用二叉樹解決實(shí)際問題的能力【題目】利用二叉樹結(jié)構(gòu)實(shí)現(xiàn)赫夫曼編/解碼器?！净疽蟆砍跏蓟?Init)：能夠?qū)斎氲娜我忾L(zhǎng)度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立赫夫曼樹建立編碼表(CreateTable)：利用已經(jīng)建好的赫夫曼樹進(jìn)行編碼，并將每個(gè)字符的編碼輸出。編碼(Encoding)：根據(jù)編碼表對(duì)輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹對(duì)編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。打印(Print)：以直觀的方式打印赫夫曼樹（選作）計(jì)算輸入的字符串編碼前和編碼后的長(zhǎng)度，并進(jìn)行分析，討論赫夫曼編碼的壓縮效果。【測(cè)試數(shù)據(jù)】IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提示：1、用戶界面可以設(shè)計(jì)為“菜單”方式：能夠進(jìn)行交互。2、根據(jù)輸入的字符串中每個(gè)字符出現(xiàn)的次數(shù)統(tǒng)計(jì)頻度，對(duì)沒有出現(xiàn)的 字符一律不用編碼?！敬a要求】1、必須要有異常處理，比如刪除空鏈表時(shí)需要拋出異常；2、保持良好的編程的風(fēng)格：代碼段與段之間要有空行和縮近標(biāo)識(shí)符名稱應(yīng)該與其代表的意義一致函數(shù)名之前應(yīng)該添加注釋說明該函數(shù)的功能關(guān)鍵代碼應(yīng)說明其功能3、遞歸程序注意調(diào)用的過程，防止棧溢出2.程序分析2.1存儲(chǔ)結(jié)構(gòu)用二叉樹的結(jié)構(gòu)建立哈夫曼樹，每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)是structHNode{intweight;intlchild; intrchild; intparent;};weightweightlchildrchildparent哈夫曼樹結(jié)點(diǎn)結(jié)構(gòu)哈夫曼樹的特點(diǎn)：只有度為2的結(jié)點(diǎn)和葉子結(jié)點(diǎn)，所以具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹的結(jié)點(diǎn)總數(shù)為2n-1順序存儲(chǔ)結(jié)構(gòu)：設(shè)置一個(gè)的Tree[2*n-1]數(shù)組2.2關(guān)鍵算法分析程序第一遍統(tǒng)計(jì)原數(shù)據(jù)中各字符出現(xiàn)的頻率，利用得到的頻率值創(chuàng)建哈夫曼樹，并把樹的信息保存起來，以便解壓時(shí)創(chuàng)建同樣的哈夫曼樹進(jìn)行解壓；第二遍，根據(jù)第一遍掃描得到的哈夫曼樹進(jìn)行編碼，并把編碼后的碼字存儲(chǔ)。哈弗曼樹的c++描述如下：classHuffman{public: voidselectmin(int&x,int&y,inta);voidCreateHTree(inta[],intn);voidCreateTable(charcode[],intn);voidencode(charstring[],charcode[]);voiddecoding(char*s,char*d,intn); voidprint(intlength);private: HNode*HTree; HCode*HCodeTable;};【存儲(chǔ)算法】對(duì)輸入的任意長(zhǎng)度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立赫夫曼樹voidHuffman::CreateHTree(inta[],intn){ HTree=newHNode[2*n-1]; for(inti=0;i<n;i++) { HTree[i].weight=a[i]; HTree[i].lchild=-1; HTree[i].rchild=-1; HTree[i].parent=-1; } intx,y; for(inti=n;i<2*n-1;i++) { selectmin(x,y,i); HTree[x].parent=HTree[y].parent=i; HTree[i].weight=HTree[x].weight+HTree[y].weight; HTree[i].lchild=x; HTree[i].rchild=y; HTree[i].parent=-1; }}哈夫曼樹是一棵正則二叉樹。根據(jù)二叉樹的性質(zhì)，一棵有n個(gè)葉子的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)，可以用一個(gè)大小為2n-1的一維數(shù)組存放哈夫曼樹的各個(gè)結(jié)點(diǎn)。由于每個(gè)結(jié)點(diǎn)同時(shí)還包含其雙親信息和孩子結(jié)點(diǎn)的信息，我們可以用一個(gè)靜態(tài)三叉鏈表來存儲(chǔ)哈夫曼樹。weightLChildRChildparent02-1-1-113-1-1-126-1-1-139-1-1-14-1-1-15-1-1-1【初始化哈夫曼樹】weightLChildRChildparent02-1-1413-1-1426-1-1539-1-1645015511426【創(chuàng)建好的哈夫曼樹】【編碼】voidHuffman::CreateTable(charcode[],intn){ HCodeTable=newHCode[n]; for(inti=0;i<n;i++) { HCodeTable[i].data=code[i]; intchild=i; intparent=HTree[i].parent; intk=0; while(parent!=-1) { if(child==HTree[parent].lchild) HCodeTable[i].code[k]='0'; else HCodeTable[i].code[k]='1'; k++; child=parent; parent=HTree[child].parent; } HCodeTable[i].code[k]='\0'; char*b=newchar[k]; for(intj=0;j<k;j++) { b[j]=HCodeTable[i].code[k-1-j]; } b[k]='\0'; for(intm=0;m<=k;m++) { HCodeTable[i].code[m]=b[m]; } cout<<endl; }}【解碼】voidHuffman::decoding(char*s,char*d,intn){ cout<<"解a碼?過y后¨?的ì?字á?符¤?串??為a：êo"<<endl; while(*s!='\0') { intparent=2*n-1-1; while(HTree[parent].lchild!=-1) { if(*s=='0') parent=HTree[parent].lchild; else parent=HTree[parent].rchild; s++; } *d=HCodeTable[parent].data; cout<<*d; d++; } cout<<endl;}2.3其他增加菜單選項(xiàng)，可以重新開始程序或退出程序3.程序運(yùn)行結(jié)果1.程序流程圖開始開始輸入字符串輸入字符串輸入字符串輸入字符串算出每個(gè)字符權(quán)值并分別存儲(chǔ)權(quán)值和字符算出每