




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、 實(shí)驗(yàn)一 哈夫曼編碼一、實(shí)驗(yàn)?zāi)康?、 掌握哈夫曼編碼原理;2、 熟練掌握哈夫曼樹的生成方法; 3、理解數(shù)據(jù)編碼壓縮和譯碼輸出編碼的實(shí)現(xiàn)。二、實(shí)驗(yàn)要求實(shí)現(xiàn)哈夫曼編碼和譯碼的生成算法。三、實(shí)驗(yàn)容先統(tǒng)計(jì)要壓縮編碼的文件中的字符字母出現(xiàn)的次數(shù),按字符字母和空格出現(xiàn)的概率對其進(jìn)行哈夫曼編碼,然后讀入要編碼的文件,編碼后存入另一個(gè)文件;接著再調(diào)出編碼后的文件,并對其進(jìn)行譯碼輸出,最后存入另一個(gè)文件中。五、實(shí)驗(yàn)原理1、哈夫曼樹的定義:假設(shè)有n個(gè)權(quán)值,試構(gòu)造一顆有n個(gè)葉子節(jié)點(diǎn)的二叉樹,每個(gè)葉子帶權(quán)值為wi,其中樹帶權(quán)路徑最小的二叉樹成為哈夫曼樹或者最優(yōu)二叉樹;2、哈夫曼樹的構(gòu)造:weight為輸入的頻率數(shù)組,
2、把其中的值賦給依次建立的HTNode對象中的data屬性,即每一個(gè)HTNode對應(yīng)一個(gè)輸入的頻率。然后根據(jù)data屬性按從小到大順序排序,每次從data取出兩個(gè)最小和此次小的HTNode,將他們的data相加,構(gòu)造出新的HTNode作為他們的父節(jié)點(diǎn),指針parent,leftchild,rightchild賦相應(yīng)值。在把這個(gè)新的節(jié)點(diǎn)插入最小堆。按此步驟可以構(gòu)造構(gòu)造出一棵哈夫曼樹。 通過已經(jīng)構(gòu)造出的哈夫曼樹,自底向上,由頻率節(jié)點(diǎn)開始向上尋找parent,直到parent為樹的頂點(diǎn)為止。這樣,根據(jù)每次向上搜索后,原節(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子還是右孩子,來記錄1或0,這樣,每個(gè)頻率
3、都會(huì)有一個(gè)01編碼與之唯一對應(yīng),并且任何編碼沒有前部分是同其他完整編碼一樣的。六、實(shí)驗(yàn)流程1 初始化,統(tǒng)計(jì)文本文件中各字符的個(gè)數(shù)作為權(quán)值,生成哈夫曼樹;2 根據(jù)符號(hào)概率的大小按由大到小順序?qū)Ψ?hào)進(jìn)行排序;3 把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn);4 重復(fù)步驟(2)(3),直到概率和為1;5 從根節(jié)點(diǎn)開始到相應(yīng)于每個(gè)符號(hào)的“樹葉”,概率大的標(biāo)“0”,概率小的標(biāo)“1”;6 從根節(jié)點(diǎn)開始,對符號(hào)進(jìn)行編碼;7 譯碼時(shí)流程逆向進(jìn)行,從文件中讀出哈夫曼樹,并利用哈夫曼樹將編碼序列解碼。七、實(shí)驗(yàn)程序#include<iostream>#include<fstream>#include&l
4、t;iomanip>#include<vector>using namespace std;typedef struct /節(jié)點(diǎn)結(jié)構(gòu)char data; /記錄字符值long int weight; /記錄字符權(quán)重unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹typedef char * *HuffmanCode;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表void Select(HuffmanTree &HT,int i,int &s1,int &s2) /在HT1.t中選擇
5、parent不為0且權(quán)值最小的兩個(gè)結(jié)點(diǎn),其序號(hào)分別為s1和s2 s1=0;s2=0;int n1=30000,n2=30000;for(int k=1;k<=i;k+)if(HTk.parent=0)if(HTk.weight<n1)n2=n1; n1=HTk.weight;s2=s1; s1=k;elseif(HTk.weight<n2)n2=HTk.weight;s2=k;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)/將要編碼的字符串存入空樹中ifstream fin1("zi
6、fu.txt");ifstream fin2("weight.txt");if(n<=1)return;int m=2*n-1;int i;HT=new HTNodem+1;char *zifu;int *weight; zifu= new charn+1;weight=new intn+1;for(i=1;i<=n;i+)/將待編碼的字符放在zifu數(shù)組中char ch;ch=fin1.get();zifui=ch;for(i=1;i<=n;i+)/將帶編碼字符對應(yīng)的權(quán)值放在weight數(shù)組中fin2>>weighti;for( i
7、=1;i<=n;i+)HTi.data=zifui;HTi.weight=weighti;for(i=n+1;i<=m;i+)HTi.data=''for(i=1;i<=m;i+)HTi.parent=HTi.lchild=HTi.rchild=0;for(i=n+1;i<=m;+i)int s1,s2;Select(HT,i-1,s1,s2);HTs1.parent=i; HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCo
8、de)malloc(n+1)*sizeof(char*);開辟一個(gè)求編碼的工作空間char *cd;cd=(char *)malloc(n*sizeof(char);/開辟空間存放權(quán)值cdn-1='0'for(i=1;i<=n;i+)int start=n-1;int c,f;for( c=i, f=HTi.parent;f!=0;c=f,f=HTf.parent)/從葉子到根逆向求編碼if(HTf.lchild=c)cd-start='0'/若是左孩子編為'0'elsecd-start='1'/若是右孩子編為'1&
9、#39;HCi=(char *)malloc(n-start)*sizeof(char);/為第i個(gè)編碼分配空間strcpy(HCi,&cdstart);delete cd;/釋放工作空間void printHuffmanTree(HuffmanTree HT,int n) /顯示有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹的編碼表 ofstream fout("hfmtree.txt"); /將對應(yīng)字符的的哈弗曼樹存入cout<<"NUM"<<" "<<"data"<<&quo
10、t; "<<"weight"<<" "<<"parent"<<" "<<"lchild"<<" "<<"rchlid"<<endl;for(int i=1;i<=2*n-1;i+)fout<<HTi.weight<<setw(3)<<HTi.parent<<setw(3)<<HTi.lc
11、hild<<setw(3)<<HTi.rchild<<endl;cout<<i<<setw(5)<<HTi.data<<setw(3)<<HTi.weight<<setw(3)<<HTi.parent<<setw(3)<<HTi.lchild<<setw(3)<<HTi.rchild<<endl;void printHuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)/
12、輸出字符的對應(yīng)哈弗曼編碼并存入code.txt文件cout<<"Huffman code is:"<<endl;ofstream fout("code.txt");for(int i=1;i<=n;i+)cout<<HTi.data<<" -> "cout<<(HCi)<<endl;fout<<(HCi)<<endl;void code_file(HuffmanTree HT,HuffmanCode HC,int n)/對文件t
13、obetran.txt進(jìn)行編碼,并將編碼存入codefile文件中ifstream fin("tobetran.txt");ofstream fout("codefile.txt");vector<char> a;char ch;while(ch=fin.get()!='*')a.push_back(ch); cout<<"待編碼的字符串為:"for(int k=0;k<a.size();k+)cout<<ak;cout<<endl;cout<<&quo
14、t;n編碼結(jié)果:"<<endl;for(int i=0;i<a.size();i+) for(int j=1;j<=n;j+)if(ai=HTj.data) fout<<HCj; break;fin.close();fout.close();void Decoding(HuffmanTree HT,HuffmanCode HC,int n)/打開codefile文件并對文件容進(jìn)行譯碼int const m=2*n-1;ifstream fin("codefile.txt");ofstream fout("textfil
15、e.txt");vector<char> a;for(char c;fin>>c;) a.push_back(c); int count=0;for(int k=0;k<a.size();k+) cout<<ak;count+;if(count%50=0)cout<<endl;int i=0;int p; /用p來記住m的值cout<<endl;cout<<"n譯碼結(jié)果:"<<endl;while(i<a.size()p=m; /從哈弗曼數(shù)的根開始遍歷while(HTp
16、.lchild) if(ai='1') p=HTp.rchild; else p=HTp.lchild; i+;fout<<HTp.data; cout<<HTp.data;void main()int n;cout<<"輸入權(quán)值個(gè)數(shù):" /設(shè)置權(quán)值數(shù)值cin>>n; printf("n");HuffmanTree HT; /哈夫曼樹HTHuffmanCode HC; /哈夫曼編碼表HCHuffmanCoding(HT,HC,n); /進(jìn)行哈夫曼編碼printHuffmanCoding(HT
17、,HC,n); /顯示編碼的字符printf("n");code_file(HT,HC,n); /顯示要編碼的字符串,并把編碼值顯示出來Decoding(HT,HC,n); /譯碼并顯示譯碼后的字符串printf("nnn");system("pause");八、結(jié)果分析哈夫曼編碼是動(dòng)態(tài)變長編碼,臨時(shí)建立概率統(tǒng)計(jì)表和編碼樹。概率小的碼比較長,概率小的碼比較長。概率大的碼短,這樣把一篇文件編碼后,就會(huì)壓縮許多。從樹的角度看,哈夫曼編碼方式是盡量把短碼都利用上。首先,把一階節(jié)點(diǎn)全都用上,如果碼字不夠時(shí),然后,再從某個(gè)節(jié)點(diǎn)伸出若干枝,引出二階節(jié)點(diǎn)作為碼字,以此類推,顯然所得
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 財(cái)務(wù)會(huì)計(jì)與管理知識(shí)實(shí)訓(xùn)分析教程
- 設(shè)備工作計(jì)劃
- 2009年資產(chǎn)評估師-財(cái)務(wù)會(huì)計(jì)測驗(yàn)試題分章練
- 從資源整合角度解析體能訓(xùn)練行業(yè)的連鎖加盟模式
- 2025年Android中高級(jí)面試必知必會(huì)講的明明白白!-備戰(zhàn)2025,android中高級(jí)面試必知必會(huì)
- 建筑施工特種作業(yè)-建筑架子工附著式腳手架真題庫-1
- 閏土的題目及答案
- 2023年學(xué)業(yè)水平合格考試三年分類匯編(真題)-專題一宇宙中的地球02太陽對地球的影響
- 11 2 成對數(shù)據(jù)的統(tǒng)計(jì)分析-高考數(shù)學(xué)真題分類 十年高考
- 新疆且末縣堯勒薩依金礦開采項(xiàng)目環(huán)評報(bào)告
- 2025年一級(jí)建造師《市政實(shí)務(wù)》考點(diǎn)精粹
- 融資專員測試題及答案
- 河北秦皇島事業(yè)單位招聘中小學(xué)教師類D類考試模擬題帶答案2024年
- T-ZZB 2218-2021 燃?xì)庥镁呙}沖點(diǎn)火器
- 好讀書讀好書課件
- 以科技創(chuàng)新為導(dǎo)向的醫(yī)療人才培養(yǎng)計(jì)劃
- 《中華人民共和國公務(wù)員法概述》課件
- 2025年ASQ質(zhì)量經(jīng)理(CMQ.OE)認(rèn)證考試練習(xí)題庫(350題)
- 裝修驗(yàn)房合同協(xié)議
- 專業(yè)市場營銷咨詢服務(wù)合同
- 企業(yè)信息管理制度
評論
0/150
提交評論