版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、.數(shù) 據(jù) 結 構實驗報告實驗名稱:哈夫曼樹學生姓名:袁普班 級:2013211125班班內序號:14號學 號:2013210681日 期:2014年12月1. 實驗目的和內容利用二叉樹結構實現(xiàn)哈夫曼編/解碼器。基本要求:1、 初始化(Init):能夠對輸入的任意長度的字符串 s進行統(tǒng)計,統(tǒng)計每個字符的頻度,并建立哈夫曼樹2、 建立編碼表(CreateTable):利用已經建好的哈夫曼樹進行編碼,并將每個字符的編碼輸出。3、 編碼(Encoding):根據(jù)編碼表對輸入的字符串進行編碼,并將編碼后的字符串輸出。4、 譯碼(Decoding):利用已經建好的哈夫曼樹對編碼后的字符串進行譯碼,并輸出譯
2、碼結果。5、 打印(Print):以直觀的方式打印哈夫曼樹(選作)6、 計算輸入的字符串編碼前和編碼后的長度,并進行分析,討論赫夫曼編碼的壓縮效果。7、 可采用二進制編碼方式(選作)測試數(shù)據(jù):I love data Structure, I love Computer。I will try my best to study data Structure.提示:1、用戶界面可以設計為“菜單”方式:能夠進行交互。2、根據(jù)輸入的字符串中每個字符出現(xiàn)的次數(shù)統(tǒng)計頻度,對沒有出現(xiàn)的字符一律不用編碼2. 程序分析2.1 存儲結構用struct結構類型來實現(xiàn)存儲樹的結點類型struct HNode int w
3、eight; /權值int parent; /父節(jié)點int lchild; /左孩子int rchild; /右孩子;struct HCode /實現(xiàn)編碼的結構類型 char data; /被編碼的字符char code100; /字符對應的哈夫曼編碼; 2.2 程序流程 輸入字符串 統(tǒng)計出現(xiàn)的字符種類和次數(shù),構建權值數(shù)組,初始化樹結點與編碼表根據(jù)哈夫曼構建規(guī)則構建哈夫曼樹,根據(jù)編碼規(guī)則對出現(xiàn)字符進行編碼,構建編碼表將輸入的字符挨個編碼對編碼后的字符進行解碼分析存儲大小2.3 關鍵算法分析 算法1:void Huffman:Count() 1 算法功能:對出現(xiàn)字符的和出現(xiàn)字符的統(tǒng)計,構建權值結
4、點,初始化編碼表 2 算法基本思想:對輸入字符一個一個的統(tǒng)計,并統(tǒng)計出現(xiàn)次數(shù),構建權值數(shù)組, 3 算法空間、時間復雜度分析:空間復雜度O(1),要遍歷一遍字符串,時間復雜度O(n) 4 代碼邏輯: leaf=0; /初始化葉子節(jié)點個數(shù) int i,j=0; int s128=0; 用于存儲出現(xiàn)的字符 for(i=0;stri!=0;i+) 遍歷輸入的字符串 s(int)stri+; 統(tǒng)計每個字符出現(xiàn)次數(shù) for(i=0;i128;i+) if(si!=0) dataj=(char)i; 給編碼表的字符賦值 weightj=si; 構建權值數(shù)組 j+; leaf=j; /葉子節(jié)點個數(shù)即字符個數(shù)
5、for(i=0;ileaf;i+) coutdatai的權值為:weightiendl; 算法2:void Init(); 1 算法功能:構建哈弗曼樹 2 算法基本思想:根據(jù)哈夫曼樹構建要求,選取權值最小的兩個結點結合,新結點加入數(shù)組,再繼續(xù)選取最小的兩個結點繼續(xù)構建。 3 算法空間、時間復雜度分析:取決于葉子節(jié)點個數(shù),時間復雜度O(n),空間復雜度O(1) 4 代碼邏輯HTree=new HNode2*leaf-1; n2=n0-1,一共需要2n-1個結點空間 for(int i=0;ileaf;i+) HTreei.weight=weighti; 給每個結點附權值 HTreei.lchil
6、d=-1; 初始化左右孩子和父節(jié)點,都為-1 HTreei.rchild=-1; HTreei.parent=-1; int x,y; /用于記錄兩個最小權值 for(int i=leaf;i2*leaf-1;i+) Selectmin(HTree,i,x,y); 選出兩個最小權值的結點 HTreex.parent=i; 父節(jié)點設置為新建立的結點 HTreey.parent=i; HTreei.weight=HTreex.weight+HTreey.weight; 父節(jié)點權值為兩個相加 HTreei.lchild=x; 使父節(jié)點指向這兩個孩子結點 HTreei.rchild=y; HTreei
7、.parent=-1; 父節(jié)點的父節(jié)點設為-1 算法3:void Selectmin(HNode*hTree,int n,int&i1,int &i2); 1 算法功能:從現(xiàn)有的結點中選擇出兩個最小的結點,返回其位置 2 算法基本思想:先選出兩個沒有構建的結點,然后向后依次比較,篩選出最小的兩個結點 3 算法空間、時間復雜度分析:空間復雜度O(1),要遍歷所有結點,時間復 雜度O(N) 4 代碼邏輯int i;for(i=0;in;i+) /n為現(xiàn)在有的結點個數(shù),是個變化值,會有相加后的新權值加入 if(hTreei.parent=-1) /父節(jié)點不是-1意味著這個結點還沒有被選擇過i1=i;
8、 記錄結點位置break; i+; /執(zhí)行一遍for循環(huán)就加1,意為下次查找從當前位置開始查找for(;ihTreei2.weight) 進行比較,使I1為最小的,I2為第二小的int j=0;j=i2;i2=i1;i1=j; i+;for(;in;i+) 將I1 I2 與后面的結點進行比較if(hTreei.parent=-1&hTreei.weighthTreei1.weight) 如果結點小于I1i2=i1; 使I2=I1 I1=新結點i1=i; else if(hTreei.parent=-1&hTreei.weighthTreei2.weight) I1新結點I2,使I2為新節(jié)點i2
9、=i; 算法4:void CreateTable(); 1 算法功能:對出現(xiàn)的字符進行編碼 2 算法基本思想:根據(jù)字符在哈夫曼樹中的位置,從下到上編碼,是左孩子編0,右孩子編1 3 算法空間、時間復雜度分析:空間復雜度O(1),要遍歷data數(shù)組,時間復雜度0(N) 4 代碼邏輯HCodeTable=new HCodeleaf; 新建編碼結點,個數(shù)為葉子節(jié)點個數(shù) for(int i=0;ileaf;i+) HCodeTablei.data=datai; int child=i; 初始化要編碼的結點的位置 int parent=HTreei.parent; 初始化父結點 int k=0; /統(tǒng)計
10、編碼個數(shù) while(parent!=-1) if(child=HTreeparent.lchild) HCodeTablei.codek=0; /左孩子標0 else HCodeTablei.codek=1; /右孩子標1 k+; child=parent; 孩子結點上移 parent=HTreechild.parent; 父節(jié)點也上移 HCodeTablei.codek=0; /將編碼反向 char code100; for(int u=0;uk;u+) codeu=HCodeTablei.codek-u-1; for(int u=0;uk;u+) HCodeTablei.codeu=co
11、deu; coutdatai的哈夫曼編碼為:; coutHCodeTablei.codeendl; length3i=k; /每一個字符編碼的長度,為求編碼總長度做準備 算法5:void Encoding(); 1 算法功能:對輸入的字符串進行編碼 2 算法基本思想:找到每個字符對應的編碼,將編碼按順序輸出 3 算法空間、時間復雜度分析:空間復雜度O(1),時間復雜度0(n) 4 代碼邏輯 coutendl輸入的字符串轉化為哈夫曼編碼為:endl; for (int i=0;stri!=0;i+) 遍歷輸入的每一個字符 for(int j=0;jleaf;j+) if(stri=HCodeTa
12、blej.data) 找到字符對應的編碼 s1=s1+HCodeTablej.code; 將所有編碼按順序加起來 coutHCodeTablej.code; 輸出編碼 coutendl;算法6:void Decoding(); 1 算法功能:對編碼串進行解碼 2 算法基本思想:找到每段編碼對應的字符,輸出字符 3 算法空間、時間復雜度分析:時間復雜度0(N),空間復雜度0(1) 4 代碼邏輯(可用偽代碼描述) cout解碼后的字符串為: endl; char *s = const_cast(s1.c_str(); 將編碼字符串轉化為char while(*s!=0) int parent=2*
13、leaf-2; 父節(jié)點為最后一個節(jié)點 while(HTreeparent.lchild!=-1) /還有左子樹,不可能是葉子節(jié)點 if(*s=0) 編碼為0,為左孩子 parent=HTreeparent.lchild; else parent=HTreeparent.rchild; 編碼為1,為右孩子 s+; coutHCodeTableparent.data; 輸出字符 coutendl; 注意分析程序的時間復雜度、內存申請和釋放,以及算法思想的體現(xiàn)。2.4 其他在此次試驗中使用了類和STL中的string,使用string可以方便的將單個字符的編碼加起來成為總的編碼后的數(shù)值,再利用STL中的轉化函數(shù)可以直接將string轉化為char,方便進行解碼工作??偠灾?,使用STL使得編碼大大的簡潔了。3. 程序運行結果分析調試過程中遇到的問題主要是執(zhí)行時有內存錯誤,檢查后發(fā)現(xiàn)是數(shù)組有越界現(xiàn)象,這提醒我在編寫時一定要仔細,特別是在for循環(huán)條件上一定要注意范圍 總結4.1實驗的難點和關鍵點 首先在輸入字符串時我發(fā)現(xiàn)直接用cin無法輸入空格,在上網查詢后找到了getline函數(shù)解決了這個問題。然后還有就是如何存儲編碼后總的那個字符串,因為每一個字符編碼的長度
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 教師個人實習總結范文
- 建筑合伙合同協(xié)議書(3篇)
- 消防安全主題倡議書(35篇)
- 建筑管理人員勞動聘用合同(3篇)
- 片段教學心得
- 幼兒園教研工作總結15篇
- 輸液性靜脈炎的研究進展課件
- 黃芪中7種黃酮類物質含量的測定高效液相色譜法
- 保定學院《簡牘書法專題》2021-2022學年第一學期期末試卷
- 保定學院《高等代數(shù)方法(一)》2021-2022學年第一學期期末試卷
- 2025高考一輪復習:15位古代名人傳記文言文挖空練習高考語文文言文備考總復習(全國)
- 供應鏈管理師技能競賽理論考試題及答案
- 第三單元 整本書閱讀 《朝花夕拾》 精讀、略讀、瀏覽 公開課一等獎創(chuàng)新教學設計-【課堂無憂】新課標同步核心素養(yǎng)課堂
- 2024-2025學年 浙教版七年級數(shù)學上冊期中(第1-4章)培優(yōu)試卷
- 拒絕校園欺凌教育主題課件
- GB/T 44109-2024信息技術大數(shù)據(jù)數(shù)據(jù)治理實施指南
- 武漢大學介紹PPT
- 解決多模穴流動不平衡問題之流道翻轉技術
- 數(shù)據(jù)挖掘(第2版)全套教學課件
- 勞務派遣勞務外包服務方案(技術方案)
- 廣東省清遠市英德市2023-2024學年八年級上學期期中物理試題
評論
0/150
提交評論