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

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

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

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

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

4、

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

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

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

8、cout<<"請輸入需要編碼的字符(5個)："<>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<