利用哈夫曼編碼實(shí)現(xiàn)壓縮和解壓縮.doc

《利用哈夫曼編碼實(shí)現(xiàn)壓縮和解壓縮.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、利用哈夫曼編碼實(shí)現(xiàn)壓縮和解壓縮1.問題描述利用哈夫曼編碼，實(shí)現(xiàn)壓縮和解壓縮的數(shù)據(jù)元素具有如下形式:結(jié)點(diǎn)：weightparentlchildrchildweight:存儲(chǔ)結(jié)點(diǎn)的權(quán)值parent:是結(jié)點(diǎn)雙親在向量中的下標(biāo)lchild:結(jié)點(diǎn)的左兒子向量下標(biāo)rchild:結(jié)點(diǎn)右兒子向量下標(biāo)編碼：bitschstartbits:位串，存放編碼ch:字符start:編碼在位串中的起始位置文件操作記錄：bcountlchparentbitsrchb:記錄字符在數(shù)組中的位置count:字符出現(xiàn)頻率（權(quán)值）lch、rch、pa

2、rent:定義哈夫曼樹指針變量bits[256]:定義存儲(chǔ)哈夫曼編碼的數(shù)組2.功能需求對(duì)于給定的一組字符，可以根據(jù)其權(quán)值進(jìn)行哈夫曼編碼，并能輸出對(duì)應(yīng)的哈夫曼樹和哈夫曼編碼；實(shí)現(xiàn)哈夫曼解碼。能夠分析文件，統(tǒng)計(jì)文件中出現(xiàn)的字符，再對(duì)文件進(jìn)行編碼，實(shí)現(xiàn)文件的壓縮和解壓縮，能夠?qū)τ谖募膲嚎s，比例進(jìn)行統(tǒng)計(jì)，能夠打印文件。3.實(shí)現(xiàn)要點(diǎn)（1）構(gòu)造哈弗曼樹過程中，首先將初始森林的各根結(jié)點(diǎn)的雙親和左、右兒子指針置-1；葉子在向量T的前n個(gè)分量中，構(gòu)成初始森林的n個(gè)結(jié)點(diǎn)；對(duì)森林中的樹進(jìn)行n次合并，并產(chǎn)生n-1個(gè)新結(jié)點(diǎn)，依次放入向

3、量T的第i個(gè)分量中。（2）編碼過程中，從葉子T[i]出發(fā)，利用雙親的指針找到雙親T[p]；再根據(jù)T[p]的孩子指針可以知道T[i]是T[p]的左兒子還是右兒子，若是左兒子，則生成代碼0，否則生成代碼1；（3）在文件壓縮和解壓過程中，主要參考網(wǎng)上資料，每個(gè)步驟都基本理解，并注上了詳細(xì)解析。4．函數(shù)定義功能：輸入權(quán)重，構(gòu)造一棵哈弗曼樹voidhuffman(hftreeT){if(n<1

4、

5、n>m)return;inti,j,p1,p2;floatsmall1,small2;//初始化cout<<"請(qǐng)輸入葉子權(quán)重(

6、5個(gè))："<>T[i].weight;}for(i=n;i

7、[j].weight;p2=p1;p1=j;}elseif(T[j].weight

8、cout<<"請(qǐng)輸入需要編碼的字符(5個(gè))："<>codes[i].ch;start=n;c=i;p=T[i].parent;while(p!=-1){start--;if(T[p].lchild==c)codes[i].bits[start]='0';elsecodes[i].bits[start]='1';c=p;p=T[p].parent;}codes[i].start=start;}cout<<"輸入成功?。?<

9、>b,b!=endflag){if(b==0)i=T[i].lchild;elsei=T

10、[i].rchild;if(T[i].lchild==-1){cout<