哈夫曼樹(shù)-課程設(shè)計(jì)報(bào)告

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：哈夫曼樹(shù)及其應(yīng)用學(xué)生姓名：劉昶志學(xué)號(hào)：1021111609班級(jí)：10211116指導(dǎo)教師：張軍2012年6目錄需求分析說(shuō)明~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~3總體設(shè)計(jì)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~4詳細(xì)設(shè)計(jì)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~5實(shí)現(xiàn)局部~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~7程序測(cè)試~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~9總結(jié)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~10一．需求分析說(shuō)明設(shè)計(jì)目的：熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)。掌握建立哈夫曼樹(shù)和哈夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算。設(shè)計(jì)內(nèi)容數(shù)據(jù)的讀入﹑存儲(chǔ)，生成文件，將鍵盤(pán)輸入的信息存入指定的文件中；設(shè)計(jì)一程序求解此問(wèn)題．哈夫曼〔Huffman〕編碼原理是一種利用二叉樹(shù)實(shí)現(xiàn)的編碼原理哈夫曼〔Huffman〕編碼是1952年為文本文件而建立，是一種統(tǒng)計(jì)編碼。屬于無(wú)損壓縮編碼。哈夫曼編碼的碼長(zhǎng)是變化的，對(duì)于出現(xiàn)頻率高的信息，編碼的長(zhǎng)度較短；而對(duì)于出現(xiàn)頻率低的信息，編碼長(zhǎng)度較長(zhǎng)。這樣，處理全部信息的總碼長(zhǎng)一定小于實(shí)際信息的符號(hào)長(zhǎng)度。鍛煉我們的編碼能力，真正理解數(shù)據(jù)結(jié)構(gòu)的編碼思想,并且鍛煉我們的動(dòng)手能力和成員間的配合，提高程序編寫(xiě)能力。在信息傳遞時(shí)，希望長(zhǎng)度能盡可能短，即采用最短碼。哈夫曼編碼的應(yīng)用，就是采用這種有效的數(shù)據(jù)壓縮技術(shù)可以節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間。二．總體設(shè)計(jì)哈夫曼樹(shù)編/譯碼系統(tǒng)哈夫曼樹(shù)編/譯碼系統(tǒng)初始化初始化退出重新建立哈夫曼樹(shù)重新建立哈夫曼樹(shù)編碼編碼打印編碼譯碼〔1〕.初始化：提示初始化界面→提示各字符及其權(quán)值將存放在hfmTree中→以字母出現(xiàn)次數(shù)為權(quán)值建立哈弗曼樹(shù)→彈出選擇菜單進(jìn)行進(jìn)一步操作；〔2〕.編碼：彈出編碼界面→讀取文件→提示輸入要編碼的字符串→對(duì)文本進(jìn)行哈弗曼編碼并輸出編碼→保存編碼文件；〔3〕.譯碼：彈出譯碼界面→利用建立好的哈弗曼樹(shù)進(jìn)行譯碼→將譯碼輸出→保存譯碼文件；三．詳細(xì)設(shè)計(jì)1.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)#include<iostream.h>//包含的庫(kù)函數(shù)#include<string.h>#include<iomanip.h>constintn=6;//葉子數(shù)目constintm=2*n-1;//森林中樹(shù)的棵樹(shù)constintc=4;classtree{public:chardata;intweight;//權(quán)值intparent;//雙親intlch,rch;//左右孩子voidcreathafumantree();//建立哈夫曼樹(shù)voideditcode();//編碼函數(shù)voidtrancode(charb[],intmax);//譯碼函數(shù)};2．算法設(shè)計(jì)哈夫曼樹(shù)編碼算法：輸入字符，權(quán)值算法：輸入一些字符,然后再輸入相對(duì)應(yīng)數(shù)量的權(quán)值,建哈夫曼樹(shù),然后進(jìn)行編碼,并得到相對(duì)應(yīng)的哈夫曼編碼。voidtree::editcode(){//編碼inti,j,k,f,count=0;intcode[n+1][c+1];for(i=1;i<=n;i++)for(j=1;j<=c;j++)code[i][j]=2;for(i=1;i<=n;i++){k=1;j=hftree[i].parent;f=i;while(j!=0){if(hftree[j].lch==f){code[i][k++]=0;}else{code[i][k++]=1;}j=hftree[j].parent; f=hftree[f].parent;}}cout<<endl;for(i=1;i<=n;i++){cout<<"權(quán)值為"<<hftree[i].weight<<"的編碼為:"<<"";for(j=c;j>=1;j--){if(code[i][j]!=2){cout<<code[i][j]<<"";count+=1;}}cout<<endl;} count=count/n;cout<<"平均編碼的長(zhǎng)度為:"<<count<<endl;}哈夫曼樹(shù)譯碼算法：譯碼：彈出譯碼界面→利用建立好的哈弗曼樹(shù)進(jìn)行譯碼→將譯碼輸出→保存譯碼文件voidtree::trancode(charb[],intmax){//譯碼inti=0;intj=m;cout<<"該段代碼編譯為:"<<endl;while(b[i]!='\0'){if(b[i]=='0')j=hftree[j].lch;elsej=hftree[j].rch;if(hftree[j].lch==0&&hftree[j].rch==0){cout<<hftree[j].weight;j=m;}i++;}}四．實(shí)現(xiàn)局部classtree{public:chardata;intweight;//權(quán)值intparent;//雙親intlch,rch;//左右孩子voidcreathafumantree();//建立哈夫曼樹(shù)voideditcode();//編碼函數(shù)voidtrancode(charb[],intmax);//譯碼函數(shù)};voidtree::editcode(){//編碼inti,j,k,f,count=0;intcode[n+1][c+1];for(i=1;i<=n;i++)for(j=1;j<=c;j++)code[i][j]=2;for(i=1;i<=n;i++){k=1;j=hftree[i].parent;f=i;while(j!=0){if(hftree[j].lch==f){code[i][k++]=0;}else{code[i][k++]=1;}j=hftree[j].parent; f=hftree[f].parent;}}cout<<endl;for(i=1;i<=n;i++){cout<<"權(quán)值為"<<hftree[i].weight<<"的編碼為:"<<"";for(j=c;j>=1;j--){if(code[i][j]!=2){cout<<code[i][j]<<"";count+=1;}}cout<<endl;} count=count/n;cout<<"平均編碼的長(zhǎng)度為:"<<count<<endl;}voidtree::trancode(charb[],intmax){//譯碼inti=0;intj=m;cout<<"該段代碼編譯為:"<<endl;while(b[i]!='\0'){if(b[i]=='0')j=hftree[j].lch;elsej=hftree[j].rch;if(hftree[j].lch==0&&hftree[j].rch==0){cout<<hftree[j].weight;j=m;}i++;}}五．程序測(cè)試1.menu菜單圖2.輸入各值并生成編碼圖3.輸入編碼生成譯碼圖六．總結(jié)1.設(shè)計(jì)體會(huì)當(dāng)剛拿到程序課題時(shí)，一看，感覺(jué)都挺容易的，都是我們學(xué)過(guò)的一些內(nèi)容，應(yīng)該很容易完成，于是就從中選了一個(gè)哈夫曼樹(shù)的應(yīng)用。結(jié)果一作才知道，并不如我們想的那么容易。對(duì)于建立哈夫曼樹(shù)，創(chuàng)立哈夫曼編碼等算法，總是因一點(diǎn)不對(duì)而編譯不成功。2.心得體會(huì)通過(guò)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我的c++語(yǔ)言水平有了比擬大的提高，其中c++語(yǔ)言關(guān)于類(lèi)的操作理解的比以前深刻不少。另外是數(shù)據(jù)結(jié)構(gòu)方面的提高，對(duì)哈夫曼樹(shù)的構(gòu)造，及哈夫曼碼方面也有不少的提高。在工程中也出現(xiàn)了很多的問(wèn)題，最大的問(wèn)題就是對(duì)程序設(shè)計(jì)框架結(jié)構(gòu)的不了解，在實(shí)現(xiàn)代碼與功能的連接時(shí)經(jīng)常會(huì)出現(xiàn)各種不同的錯(cuò)誤，在實(shí)現(xiàn)一些功能時(shí)系