哈夫曼樹實驗報告-3_第1頁
哈夫曼樹實驗報告-3_第2頁
哈夫曼樹實驗報告-3_第3頁
哈夫曼樹實驗報告-3_第4頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

2011-2012學年第一學期數據結構課內實驗報告學院：計算機學院專業：計算機科學與技術姓名：李變學號：04091146（09）指導老師：王春梅實驗題目實驗目的：a.創建哈夫曼樹;b.哈夫曼編碼c.哈夫曼譯碼；實驗內容：創建哈夫曼樹；哈夫曼編碼；哈夫曼譯碼；數據結構及算法思想：創建哈夫曼樹的描述：數據結構：數據的邏輯結構是樹狀結構；采用靜態的三叉鏈表存放；算法思想：1.先把三叉鏈表中1-N個元素進行初始化，存放葉子節點，他們都沒有孩子和雙親。2.再初始化后n-1個非葉子節點元素。3.從當前森林中（在森林中樹的根節點的雙親為0）選擇兩棵根的權值最小的樹；刪除合并是將選到的兩棵樹的根權和存入數組當前最前面的空閑元素中，并置入相應的雙親與孩子的位置。4.重復上述步驟直到森林中只含有一棵二叉樹為止； 哈夫曼樹編碼的描述： 數據結構：數據的邏輯結構是樹狀結構；采用靜態的三叉鏈表存放； 算法思想：1.申請存儲哈夫曼編碼串的頭指針數組，申請一個字符型指針，用來存放臨時的編碼串；2.從葉子節點開始向上倒退，若其為它雙親節點的左孩子則編碼標0，否則標1；直到根節點為止，最后把臨時存儲編碼復制到對應的指針數組所指向的內存中；3.重復上述步驟，直到所有的葉子節點都被編碼完；哈夫曼樹譯碼的描述： 數據結構：數據的邏輯結構是樹狀結構；采用靜態的三叉鏈表存放； 算法思想：1.從根結點開始向下遞推，若其編碼當前的數值為0，則到該節點的左孩子，否則轉到其右孩子；重復上述步驟直到該編碼中全部訪問完，則樹中對應的葉子節點則為所求2.依據上述步驟，對編碼數組中所有編碼全部進行譯碼；模塊劃分：1.選擇兩個權值最小的結點；2.創建哈夫曼樹；3.打印哈夫曼樹4.哈夫曼編碼5.哈夫曼譯碼詳細設計及運行結果：1.創建哈夫曼樹：2.哈夫曼編碼：3.哈夫曼譯碼：調試情況，設計技巧及體會這次實驗最大遺憾是沒有把二叉樹很好的打印出來，對于本程序的主要部分，Huffman樹的生成和Huffman碼的編譯，沒有任何的創新，無論是算法還是基本框架都是套用課本上的經典算法，時間復雜度都為o(n).另外在創建哈夫曼樹時選擇兩個權值的結點的效率不是太高。每次都要先找到最大的權值，然后再進行比較，經過兩次循環找到兩個最小的權值，這一個函數的時間復雜度比創建，編碼，譯碼的時間復雜度都要高。哈夫曼編碼時通過動態的指針數組存放個葉子節點的編碼，節省了好多空間，效率比較好。通過這次試驗，自我感覺收獲很深，無論是對于編程本身還是對集成開發環境的使用上，還有對知識掌握的熟練程度上，都有了很大的提高。本次實驗中出現的最大問題仍然是函數間參數的傳遞問題，上一個二叉樹實驗也遇到了同樣的問題，函數間傳遞參數掌握的很不好。為了解決這個問題我花了大量的時間。剛開始時，程序老提示函數參數類型不匹配，可我感覺是正確的，后來通過請教同學才明白，原來我函數形參類型是指針型，而我穿過去的實參全是變量值；后來程序編譯可以通過但是運行

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論