數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計----Huffman編碼

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

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

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

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

5、和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要到達(dá)以下目的：1、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等根本方法和技能；3、提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；4、訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般標(biāo)準(zhǔn)進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。二實驗題目：赫夫曼編碼1.問題描述 某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)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種字符的概率； 構(gòu)造赫夫曼樹；輸出每個

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

7、上，W i 為葉節(jié)點的權(quán) ，L i 為根節(jié)點到葉節(jié)點的路徑長度。那么，W i L i 恰好為二叉 樹上帶權(quán)路徑長度。 因此，設(shè)計電文總長最短的二進(jìn)制前綴編碼，就是以n 種子符出現(xiàn)的頻率作權(quán)，構(gòu)造一刻赫夫曼樹， 此構(gòu)造過程成為赫夫曼編碼。 本演示程序用C+6.0編寫，完成赫夫曼樹的構(gòu)造以及赫夫曼編碼的設(shè)計。1輸入的形式和輸入值的范圍：n中字符，其出現(xiàn)的頻率2 輸出的形式： 二進(jìn)制前綴編碼3 程序所能到達(dá)的功能：設(shè)計一顆赫夫曼樹，由此得到二進(jìn)制前綴編碼，即赫夫曼編碼。4測試數(shù)據(jù)：某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)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種字符的概率； 構(gòu)造赫夫曼樹；輸出每個字符的赫夫曼編碼;三. 概要設(shè)計1為了實現(xiàn)上述程序功能，需要定義單鏈表的抽象數(shù)據(jù)類型：ADT BinaryTree 數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R： 假設(shè)D=，那么R=，稱BinaryTree為空二叉樹； 假設(shè)D，那么R=H根本操作：void HuffmanCoding(HuffmanTree&,HuffmanCode&,int)操作結(jié)果：求赫夫曼編碼void Select(HuffmanTree,int,int*,int*)操作結(jié)果：查找權(quán)值較小的兩個結(jié)點void O

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

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

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

12、 struct ElemType elem; unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;/動態(tài)分配數(shù)組存儲赫夫曼樹2其他模塊偽碼算法void HuffmanCoding(HuffmanTree&,HuffmanCode&,int)偽碼算法void Select(HuffmanTree,int,int*,int*)偽碼算法void OutputHuffmanCode(HuffmanTree,HuffmanCode,int)偽碼算法(3)算法分析設(shè)計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個節(jié)點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);/查找權(quán)值較小的兩個節(jié)點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);五. 測試分析在我自己課程設(shè)計中，就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯誤，遇到了很多麻煩及困難，我的調(diào)試及其中的錯誤和我最終找出錯誤，修改為正確的能夠執(zhí)行的程序中，通過分析，我學(xué)到了：在定義頭文件時可多不可少，即我們可多寫些頭文件，肯

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

17、自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。 這次課程設(shè)計，我在編輯中犯了不應(yīng)有的錯誤，設(shè)計統(tǒng)計字符和合并時忘記應(yīng)該怎樣保存數(shù)據(jù)，對文件的操作也很生疏。在不斷分析后明確并改正了錯誤和疏漏，我的程序有了更高的質(zhì)量。六. 使用說明1.程序名為keshe.exe，運行環(huán)境為DOS。程序執(zhí)行后顯示：2.輸入要編碼的字符種類數(shù)為8然后程序顯示：3.然后依次輸入8個字符及出現(xiàn)比例七. 測試結(jié)果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;/動態(tài)分配數(shù)組存儲赫夫曼樹typedef char*HuffmanCode;/ 動態(tài)分配數(shù)組存儲赫夫曼編碼表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<<"請輸入要編碼的字符種類數(shù)："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;/權(quán)重;if(n<=1)return;m=2*n-1;HT=new HTNodem+1;for(i=1;i<=n;+i)/初始化前n個

21、結(jié)點cout<<"輸入元素和所占比例："cin>>ch>>wei;HTi.elem=ch;HTi.weight=wei;HTi.parent=HTi.lchild=HTi.rchild=0; for(i=n+1;i<=m;+i)/初始化后幾個結(jié)點n+1.mHTi.elem='0'HTi.parent=HTi.lchild=HTi.rchild=0; for(i=n+1;i<=m;+i) /生成n+1.m個結(jié)點; Select(HT,i-1,&s1,&s2);/查找權(quán)值較小的兩個結(jié)點 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