1、精品文檔數據結構課程設計 題目： Huffman編碼 姓名： 班級： 學號： 指導老師： 日期： 2021年6月24日 前言3課程設計報告5一實驗目的5二實驗題目：赫夫曼編碼71.問題描述72.需求分析7三. 概要設計9四. 詳細設計111.設計思想11五. 測試分析16六. 使用說明18七. 測試結果19八. 附錄201.源代碼202.運行結果25前言 隨著計算機的普遍應用與日益開展，其應用早已不局限于簡單的數值運算，而涉及到問題的分析、數據結構框架的設計以及設計最短路線等復雜的非數值處理和操作。算法與數據結構的學習就是為以后利用計算機資源高效地開發非數值處理的計算機程序打下堅實的理論、方法

2、和技術根底。 算法與數據結構旨在分析研究計算機加工的數據對象的特性，以便選擇適當的數據結構和存儲結構，從而使建立在其上的解決問題的算法到達最優。 數據結構是在整個計算機科學與技術領域上廣泛被使用的術語。它用來反映一個數據的內部構成，即一個數據由那些成分數據構成，以什么方式構成，呈什么結構。數據結構有邏輯上的數據結構和物理上的數據結構之分。邏輯上的數據結構反映成分數據之間的邏輯關系，而物理上的數據結構反映成分數據在計算機內部的存儲安排。數據結構是數據存在的形式。?數據結構?主要介紹一些最常用的數據結構，說明各種數據結構內在的邏輯關系，討論其在計算機中的存儲表示，以及在其上進行各種運算時的實現算法

3、，并對算法的效率進行簡單的分析和討論。數據結構是介于數學、計算機軟件和計算機硬件之間的一門計算機專業的核心課程，它是計算機程序設計、數據庫、操作系統、編譯原理及人工智能等的重要根底，廣泛的應用于信息學、系統工程等各種領域。 學習數據結構是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設計可以提高學生的思維能力，促進學生的綜合應用能力和專業素質的提高。課程設計報告一實驗目的數據結構作為一門學科主要研究數據的各種邏輯結構和存儲結構，以及對數據的各種操作。因此，主要有三個方面的內容：數據的邏輯結構；數據的物理存儲結構；對數據的操作或算法。通常，算法的設計取決于數據的邏輯結構

4、，算法的實現取決于數據的物理存儲結構。數據結構是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應，通過這組算法集合可以對數據結構中的數據進行某種操作。數據結構課程主要是研究非數值計算的程序設計問題中所出現的計算機操作對象以及它們之間的關系和操作的學科。數據結構是介于數學、計算機軟件和計算機硬件之間的一門計算機專業的核心課程，它是計算機程序設計、數據庫、操作系統、編譯原理及人工智能等的重要根底，廣泛的應用于信息學、系統工程等各種領域。學習數據結構是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設計可以提高學生的思維能力，促進學生的綜合應用能力

5、和專業素質的提高。通過此次課程設計主要到達以下目的：1、了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力；2、初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等根本方法和技能；3、提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；4、訓練用系統的觀點和軟件開發一般標準進行軟件開發，培養軟件工作者所應具備的科學的工作方法和作風。二實驗題目：赫夫曼編碼1.問題描述 某系統在通信聯絡中只可能出現8種字符a,b,c,d,e,f,g,h，其概率分別是:0.06，0.28，0.07，0.09，0.14，0.21，0.03，0.12輸入8種字符的概率； 構造赫夫曼樹；輸出每個

6、字符的赫夫曼編碼;2.需求分析赫夫曼編碼的應用很廣泛，利用赫夫曼樹求得的用于通信的二進制編碼成為赫夫曼編碼。樹中從根到 每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0碼，指向右子樹的分支表示 “1碼，取每條路徑上的“0或“1的序列作為和每個葉子對應的字符的編碼，這就是赫夫曼編碼。 通常我們把數據壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式 的字符串，但在信息傳遞時，總希望總長度能盡可能短，即采用最短碼。 假設每種字符在電文中出現的次數為W i ,編碼長度為L i ，電文中有n 種字符，那么電文編碼總長為W i L i 。 假設將此對應到二叉樹

7、上，W i 為葉節點的權 ，L i 為根節點到葉節點的路徑長度。那么，W i L i 恰好為二叉 樹上帶權路徑長度。 因此，設計電文總長最短的二進制前綴編碼，就是以n 種子符出現的頻率作權，構造一刻赫夫曼樹， 此構造過程成為赫夫曼編碼。 本演示程序用C+6.0編寫，完成赫夫曼樹的構造以及赫夫曼編碼的設計。1輸入的形式和輸入值的范圍：n中字符，其出現的頻率2 輸出的形式： 二進制前綴編碼3 程序所能到達的功能：設計一顆赫夫曼樹，由此得到二進制前綴編碼，即赫夫曼編碼。4測試數據：某系統在通信聯絡中只可能出現8種字符a,b,c,d,e,f,g,h，其概率分別是:0.06，0.28，0.07，0.09

8、，0.14，0.21，0.03，0.12輸入8種字符的概率； 構造赫夫曼樹；輸出每個字符的赫夫曼編碼;三. 概要設計1為了實現上述程序功能，需要定義單鏈表的抽象數據類型：ADT BinaryTree 數據對象D：D是具有相同特性的數據元素的集合。數據關系R： 假設D=，那么R=，稱BinaryTree為空二叉樹； 假設D，那么R=H根本操作：void HuffmanCoding(HuffmanTree&,HuffmanCode&,int)操作結果：求赫夫曼編碼void Select(HuffmanTree,int,int*,int*)操作結果：查找權值較小的兩個結點void O

9、utputHuffmanCode(HuffmanTree,HuffmanCode,int)操作結果：輸出赫夫曼編碼2本程序包含4個函數： 主函數main() 求赫夫曼編碼函數HuffmanCoding();查找權值較小的兩個結點函數Select (); 輸出赫夫曼編碼函數OutputHuffmanCode ()各函數間關系如下： HuffmanCoding()Main Select () OutputHuffmanCode () 四. 詳細設計實現概要設計中定義的所有的數據類型，對每個操作給出偽碼算法。對主程序和其他模塊也都需要寫出偽碼算法。1.設計思想哈夫曼編譯碼系統的主要功能是先建立哈夫曼

10、樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進行譯碼 。 在通信中可以采用0和1的不同排列來表示不同的字符，稱為二進制編碼。而赫夫曼樹在數據編碼中的應用是數據的最小冗余編碼問題他是數據壓縮學的根底。假設每個字符出現的頻率相同，那么可以采用等長的二進制編碼，頻率不同，采用不等長的二進制編碼，頻率達的字符采用位數較少的編碼，頻率小的采用位數較多的編碼。赫夫曼編碼就是一種不等長的二進制編碼，而赫夫曼樹是一種最優二叉樹，它 的編碼也是一種最優編碼。在赫夫曼樹中，規定往左編碼為0，往右編碼為1，那么得到葉子節點的編碼為從根結點帶葉子結點中所有路徑中0和1的順序排列。 

11、;（1） 設計包含的幾個方面：  赫夫曼樹的構造       假設有n個權值，那么構造出的赫夫曼樹有n個葉子結點。n個權值分別為w1,w2,wn,那么赫夫曼樹構造規那么為： 1、將w1,w2,.wn,看成有n棵樹的森林。 2、在森林中選出兩個根結點最小的樹合并，作為一棵新樹的左右子書，且新樹根結點權值為左右子樹根結點權值之和。 3、從森林中刪除選取的兩棵樹，并將新樹參加森林。 4、重復2和3步驟，直到森林中只剩一棵樹為止 赫夫曼編碼1結點類型typedef

12、 struct ElemType elem; unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;/動態分配數組存儲赫夫曼樹2其他模塊偽碼算法void HuffmanCoding(HuffmanTree&,HuffmanCode&,int)偽碼算法void Select(HuffmanTree,int,int*,int*)偽碼算法void OutputHuffmanCode(HuffmanTree,HuffmanCode,int)偽碼算法(3)算法分析設計void Huffman

13、Coding(HuffmanTree&HT,HuffmanCode&HC,int n);int i,m,s1,s2,start,c,f;char*cd;char chl/元素if(n<=1)return;m=2*n-1;HT=new HTNodem+1;for(i=1;i<=n;i+)/初始化前n個節點cout<<"輸入元素和所占比例："cin>>ch>>wei;HTi.elem=ch;HTi.weight=wei;HTi.parent=HTi.lchild=HTirchild=0;for(i=n+1;i<

14、;=m;+i)/初始化后n+1.mHTi.elem='0'HTi.weight=HTi.parent=HTilchild=HTi.rchild=0;for(i=n+1;i<=m;+i)/生成n+1.mSelect(HT,i-1,&s1,&s2);/查找權值較小的兩個節點HTs1.parent=i;HTs2parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=new char*n+1;cd=new charn;cdn-1='0'for(i=1;i&

15、lt;=m;+i)/生成HuffmanCodestart=n-1;for(c=i;f=HTi.parent;f!=0;c=f;f=HTf.parent)if(HTf.child=c)cd-start='0'else cd-start='1'HCi=new charn-start;strcpy(HCi,&cdstart);五. 測試分析在我自己課程設計中，就在編寫好源代碼后的調試中出現了不少的錯誤，遇到了很多麻煩及困難，我的調試及其中的錯誤和我最終找出錯誤，修改為正確的能夠執行的程序中，通過分析，我學到了：在定義頭文件時可多不可少，即我們可多寫些頭文件，肯

16、定不會出錯，但是假設沒有定義所引用的相關頭文件，必定調試不通過；在執行譯碼操作時，不知什么原因，總是不能把要編譯的二進制數與編譯成的字符用連接號連接起來，而是按順序直接放在一起，視覺效果不是很好。還有就是，很遺憾的是，我們的哈夫曼編碼/譯碼器沒有像老師要求的那樣完成編一個文件的功能，這是我們設計的失敗之處。 通過本次數據結構的課程設計，我學習了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更穩固了課堂中學習有關于哈夫曼編碼的知識，真正學會一種算法了。當求解一個算法時,不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細地分析每一步怎么做，無論

17、自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。 這次課程設計，我在編輯中犯了不應有的錯誤，設計統計字符和合并時忘記應該怎樣保存數據，對文件的操作也很生疏。在不斷分析后明確并改正了錯誤和疏漏，我的程序有了更高的質量。六. 使用說明1.程序名為keshe.exe，運行環境為DOS。程序執行后顯示：2.輸入要編碼的字符種類數為8然后程序顯示：3.然后依次輸入8個字符及出現比例七. 測試結果1.輸入第一個字符與所占比例：a , 62. 輸入第一個字符與所占比例：b, 283. 輸入第一個字符與所占比例：c, 74. 輸入第一個字符與所占比例：d, 95. 輸入第一個字符與所占

18、比例：e, 146. 輸入第一個字符與所占比例：f, 217. 輸入第一個字符與所占比例：g, 38. 輸入第一個字符與所占比例：h, 12八. 附錄1.源代碼 #include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>typedef int Status;typedef char ElemType;typedef struct ElemType elem; unsigned int weight; unsigned int parent,lchild,rch

19、ild;HTNode,*HuffmanTree;/動態分配數組存儲赫夫曼樹typedef char*HuffmanCode;/ 動態分配數組存儲赫夫曼編碼表void HuffmanCoding(HuffmanTree&,HuffmanCode&,int);void Select(HuffmanTree,int,int*,int*);void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);Status main()HuffmanTree HT;HuffmanCode HC;int i,n;/the number of element

20、s;cout<<"請輸入要編碼的字符種類數："cin>>n;HuffmanCoding(HT,HC,n);OutputHuffmanCode(HT,HC,n);return 1;void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int n)int i,m,s1,s2,start,c,f;char *cd;char ch;/元素;int wei;/權重;if(n<=1)return;m=2*n-1;HT=new HTNodem+1;for(i=1;i<=n;+i)/初始化前n個

21、結點cout<<"輸入元素和所占比例："cin>>ch>>wei;HTi.elem=ch;HTi.weight=wei;HTi.parent=HTi.lchild=HTi.rchild=0; for(i=n+1;i<=m;+i)/初始化后幾個結點n+1.mHTi.elem='0'HTi.parent=HTi.lchild=HTi.rchild=0; for(i=n+1;i<=m;+i) /生成n+1.m個結點; 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=new char*n+1; cd=new charn; cdn-1='0' for(i=1;i<=n;+i) /生成HuffmanCode start=n-1; for(c=i,f=HTi.parent;f!=0;c=f