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

上傳人：奔*** IP屬地：河北更新時間：2024-04-02 格式：doc 頁數(shù)：25 大?。?45.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩24頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計　　題目： Huffman編碼 　　姓名： 　　班級： 　　學(xué)號： 　　指導(dǎo)老師：

2、 　　日期： 2013年6月24日 　　前言3　　課程設(shè)計報告5　　一．實驗?zāi)康?　　二．實驗題目：赫夫

3、曼編碼7　　1.問題描述7　　2.需求分析7　　三. 概要設(shè)計9　　四. 詳細設(shè)計11

4、　1.設(shè)計思想11　　五. 測試分析16　　六. 使用說明18　　七. 測試結(jié)果19　　八. 附錄20　　1.源代碼20&

5、lt;/p>　　2.運行結(jié)果25　　前言　　隨著計算機的普遍應(yīng)用與日益發(fā)展，其應(yīng)用早已不局限于簡單的數(shù)值運算，而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計以及設(shè)計最短路線等復(fù)雜的非數(shù)值處理和操作。算法與數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)就是為以后利用計算機資源高效地開發(fā)非數(shù)值

6、處理的計算機程序打下堅實的理論、方法和技術(shù)基礎(chǔ)。　　算法與數(shù)據(jù)結(jié)構(gòu)旨在分析研究計算機加工的數(shù)據(jù)對象的特性，以便選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)，從而使建立在其上的解決問題的算法達到最優(yōu)。　　數(shù)據(jù)結(jié)構(gòu)是在整個計算機科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(shù)據(jù)由那些成分數(shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)

7、和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分數(shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分數(shù)據(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)系，討論其在計算機中的存儲表示，以及在其上進行各種運算時的實現(xiàn)算法，并對算法的效率進行簡單的分析和討論。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程

8、，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。　　學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設(shè)計可以提高學(xué)生的思維能力，促進學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。　　課程設(shè)計報告<

9、p>　　一．實驗?zāi)康?lt;/b>　　數(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)，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應(yīng)，

10、通過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進行某種操作。　　數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。　　學(xué)習(xí)數(shù)據(jù)結(jié)

11、構(gòu)是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設(shè)計可以提高學(xué)生的思維能力，促進學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達到以下目的：　　1、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；　　2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；

12、　　3、提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；　　4、訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。　　二．實驗題目：赫夫曼編碼　　1.問題描述

13、　已知某系統(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)造赫夫曼樹；　　③輸出每個字符的赫夫曼編碼;&l

14、t;p>　　2.需求分析　　赫夫曼編碼的應(yīng)用很廣泛，利用赫夫曼樹求得的用于通信的二進制編碼成為赫夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示 “1”碼，取每條路徑上的“0”或“1”的序列作為和每個葉子對應(yīng)的字符的編碼，這就是赫夫曼編碼。

15、　通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串，但在信息傳遞時，總希望總長度能盡可能短，即采用最短碼。　　假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為W i ,編碼長度為L i ，電文中有n 種字符，則電文編碼總長為∑W i L i 。若將此對應(yīng)到二叉樹上，W i 為葉節(jié)點的權(quán) ，L i 為根節(jié)點到葉節(jié)點的路徑長度。那么，∑W i L i 恰好為二叉

16、樹上帶權(quán)路徑長度。 　　因此，設(shè)計電文總長最短的二進制前綴編碼，就是以n 種子符出現(xiàn)的頻率作權(quán)，構(gòu)造一刻赫夫曼樹，此構(gòu)造過程成為赫夫曼編碼。 　　本演示程序用C++6.0編寫，完成赫夫曼樹的構(gòu)造以及赫夫曼編碼的設(shè)計。　?。?）輸入的形式和輸入值的范圍：n中字符，其出現(xiàn)的頻率<p&g

17、t;　?。?）輸出的形式：二進制前綴編碼　　（3）程序所能達到的功能：設(shè)計一顆赫夫曼樹，由此得到二進制前綴編碼，即赫夫曼編碼。　　（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，

18、0.09，0.14，0.21，0.03，0.12　?、佥斎?種字符的概率；　?、跇?gòu)造赫夫曼樹；　　③輸出每個字符的赫夫曼編碼;　　三. 概要設(shè)計　?。?）

19、為了實現(xiàn)上述程序功能，需要定義單鏈表的抽象數(shù)據(jù)類型：　　ADT BinaryTree {　　數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。　　數(shù)據(jù)關(guān)系R：若D=，則R=，稱BinaryTree為空二叉樹；　　若D，則R={H}<

20、;/p>　　基本操作：　　void HuffmanCoding(HuffmanTree&,HuffmanCode&,int)　　操作結(jié)果：求赫夫曼編碼　　void Select(HuffmanTree,int,int*,int*)&

21、lt;/p>　　操作結(jié)果：查找權(quán)值較小的兩個結(jié)點　　void OutputHuffmanCode(HuffmanTree,HuffmanCode,int)　　操作結(jié)果：輸出赫夫曼編碼　?。?）本程序包含4個函數(shù)：　?、?主函數(shù)main()　?、?求赫夫曼編碼函數(shù)HuffmanC

22、oding();　　③查找權(quán)值較小的兩個結(jié)點函數(shù)Select ();　?、?輸出赫夫曼編碼函數(shù)OutputHuffmanCode ()　　　　各函數(shù)間關(guān)系如下： 　　HuffmanCoding()　　Main Select ()&l

23、t;/p>　　OutputHuffmanCode ()　　四. 詳細設(shè)計　　實現(xiàn)概要設(shè)計中定義的所有的數(shù)據(jù)類型，對每個操作給出偽碼算法。對主程序和其他模塊也都需要寫出偽碼算法。　　1.設(shè)計思想

24、;　　哈夫曼編譯碼系統(tǒng)的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進行譯碼。 　　在通信中可以采用0和1的不同排列來表示不同的字符，稱為二進制編碼。而赫夫曼樹在數(shù)據(jù)編碼中的應(yīng)用是數(shù)據(jù)的最小冗余編碼問題他是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。若每個字符出現(xiàn)的頻率相同，則可以采用等長的二進制編碼，頻率不同，采用不等長的二進制編碼，頻率達的字符采用位數(shù)較

25、少的編碼，頻率小的采用位數(shù)較多的編碼。赫夫曼編碼就是一種不等長的二進制編碼，而赫夫曼樹是一種最優(yōu)二叉樹，它的編碼也是一種最優(yōu)編碼。在赫夫曼樹中，規(guī)定往左編碼為0，往右編碼為1，則得到葉子節(jié)點的編碼為從根結(jié)點帶葉子結(jié)點中所有路徑中0和1的順序排列。 　　設(shè)計包含的幾個方面： 　　① 赫夫曼樹的構(gòu)造 <

26、;/p>　　假設(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)值之和。 <

27、;/p>　　3、從森林中刪除選取的兩棵樹，并將新樹加入森林。 　　4、重復(fù)2和3步驟，直到森林中只剩一棵樹為止　?、?#160;赫夫曼編碼　?。?）結(jié)點類型

28、　typedef struct {　　ElemType elem;　　unsigned int weight;　　unsigned int parent,lchild,rchild;　　} HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲赫夫曼樹</

29、p>　?。?）其他模塊偽碼算法　　void HuffmanCoding(HuffmanTree&,HuffmanCode&,int)　　（偽碼算法）　　void Select(HuffmanTree,int,int*,int*)&l

30、t;/p>　?。▊未a算法）　　void OutputHuffmanCode(HuffmanTree,HuffmanCode,int)　?。▊未a算法）　　(3)算法分析設(shè)計　　void HuffmanCodin

31、g(HuffmanTree&HT,HuffmanCode&HC,int n);　　{　　int i,m,s1,s2,start,c,f;　　char*cd;　　char chl//

32、元素　　if(n<=1)　　return;　　m=2*n-1;　　HT=new HTNode[m+1];　　f

33、or(i=1;i<=n;i++)　　{//初始化前n個節(jié)點　　cout<<"輸入元素和所占比例：";　　cin>>ch>>wei;　　HT[i].elem=ch;　　H

34、T[i].weight=wei;　　HT[i].parent=HT[i].lchild=HT[i]rchild=0;　　}　　for(i=n+1;i<=m;++i)　　{//初始化后n+1...m<

35、p>　　HT[i].elem='0';　　HT[i].weight=HT[i].parent=HT[i]lchild=HT[i].rchild=0;　　}　　for(i=n+1;i<=m;++i)　　{//

36、生成n+1...m　　Select(HT,i-1,&s1,&s2);//查找權(quán)值較小的兩個節(jié)點　　HT[s1].parent=i;HT[s2]parent=i;　　HT[i].lchild=s1;HT[i].rchild=s2;　　HT[i].weight

37、=HT[s1].weight+HT[s2].weight;　　}　　HC=new char*[n+1];　　cd=new char[n];　　cd[n-1]='\0';　　fo

38、r(i=1;i<=m;++i)　　{//生成HuffmanCode　　start=n-1;　　for(c=i;f=HT[i].parent;f!=0;c=f;f=HT[f].parent)　　{<p

39、>　　if(HT[f].child==c)cd[--start]='0';　　else cd[--start]='1';　　}　　HC[i]=new char[n-start];　　strcpy(

40、HC[i],&cd[start]);　　}　　}　　五. 測試分析　　在我自己課程設(shè)計中，就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯誤，遇到了很多麻煩及

41、困難，我的調(diào)試及其中的錯誤和我最終找出錯誤，修改為正確的能夠執(zhí)行的程序中，通過分析，我學(xué)到了：　　在定義頭文件時可多不可少，即我們可多寫些頭文件，肯定不會出錯，但是若沒有定義所引用的相關(guān)頭文件，必定調(diào)試不通過；　　在執(zhí)行譯碼操作時，不知什么原因，總是不能把要編譯的二進制數(shù)與編譯成的字符用連接號連接起來，而是按順序直接放在一起，視覺效果不是很好。還有就是，

42、很遺憾的是，我們的哈夫曼編碼/譯碼器沒有像老師要求的那樣完成編一個文件的功能，這是我們設(shè)計的失敗之處。　　通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計，我學(xué)習(xí)了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識，真正學(xué)會一種算法了。當求解一個算法時,不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細地分析每一步怎么做，無論自

43、己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。　　這次課程設(shè)計，我在編輯中犯了不應(yīng)有的錯誤，設(shè)計統(tǒng)計字符和合并時忘記應(yīng)該怎樣保存數(shù)據(jù)，對文件的操作也很生疏。在不斷分析后明確并改正了錯誤和疏漏，我的程序有了更高的質(zhì)量。　　六. 使用說明　　1.程序名為k

44、eshe.exe，運行環(huán)境為DOS。程序執(zhí)行后顯示：　　2.輸入要編碼的字符種類數(shù)為8然后程序顯示：　　3.然后依次輸入8個字符及出現(xiàn)比例　　七. 測試結(jié)果　　1.輸入第一個字符與所占比例：a , 6<p

45、>　　2. 輸入第一個字符與所占比例：b, 28　　3. 輸入第一個字符與所占比例：c, 7　　4. 輸入第一個字符與所占比例：d, 9　　5. 輸入第一個字符與所占比例：e, 14　　6. 輸入第一個字符與所占比例：f, 21<p&g

46、t;　　7. 輸入第一個字符與所占比例：g, 3　　8. 輸入第一個字符與所占比例：h, 12　　八. 附錄　　1.源代碼　　#include<iostream.h>

47、;　　#include<stdio.h>　　#include<stdlib.h>　　#include<string.h>　　typedef int Status;　　typedef char ElemType;&l

48、t;/p>　　typedef struct　　{　　ElemType elem;　　unsigned int weight;　　unsigned int parent,lchild,rchild;<

49、/p>　　}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲赫夫曼樹　　typedef char**HuffmanCode;// 動態(tài)分配數(shù)組存儲赫夫曼編碼表　　void HuffmanCoding(HuffmanTree&,HuffmanCode&,int);<p&g

50、t;　　void Select(HuffmanTree,int,int*,int*);　　void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);　　Status main()　　{

51、HuffmanTree HT;　　HuffmanCode HC;　　int i,n;//the number of elements;　　cout<<"請輸入要編碼的字符種類數(shù)：";　　cin>>n;</

52、b>　　HuffmanCoding(HT,HC,n);　　OutputHuffmanCode(HT,HC,n);　　return 1;　　}　　vo

53、id HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int n)　　{　　int i,m,s1,s2,start,c,f;　　char *cd;<p&

54、gt;　　char ch;//元素;　　int wei;//權(quán)重;　　if(n<=1)return;　　m=2*n-1;　　HT=new HTNode[m+1];　　for(i=1;i&

55、lt;=n;++i)　　{//初始化前n個結(jié)點　　cout<<"輸入元素和所占比例：";　　cin>>ch>>wei;　　HT[i].elem=ch;　　HT[i].weig

56、ht=wei;　　HT[i].parent=HT[i].lchild=HT[i].rchild=0;　　}　　for(i=n+1;i<=m;++i)　　{//初始化后幾個結(jié)點n+1...m

57、;　　HT[i].elem='0';　　HT[i].parent=HT[i].lchild=HT[i].rchild=0;　　}　　for(i=n+1;i<=m;++i)　　{//生成n+1...m個結(jié)點;<

58、;/p>　　Select(HT,i-1,&s1,&s2);//查找權(quán)值較小的兩個結(jié)點　　HT[s1].parent=i;HT[s2].parent=i;　　HT[i].lchild=s1;HT[i].rchild=s2;　　HT[i].weight=HT[s1].wei

59、ght+HT[s2].weight;　　}　　HC=new char*[n+1];　　cd=new char[n];　　cd[n-1]='\0';　　for(i=1;i<

60、=n;++i)　　{//生成HuffmanCode　　start=n-1;　　for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)　　{if(HT[f].lchild==c)cd[--start]='0';<

61、/p>　　else cd[--start]='1';　　}　　HC[i]=new char[n-start];　　strcpy(HC[i],&cd[start]);

62、　　}　　}　　void Select(HuffmanTree HT,int n,int *s1,int *s2)　　{//查找權(quán)值較小的兩個結(jié)點　　int i;</p&

63、gt;　　(*s1)=(*s2)=0;　　for(i=1;i<=n;i++)　　if(HT[i].weight<HT[(*s2)].weight&&HT[i].parent==0)　　if(HT[i].weight<HT[(*s1)].weight)<

64、/p>　　{(*s2)=(*s1);　　(*s1)=i;　　}　　else(*s2)=i;　　if((*s1)>(*s2))<p&g

65、t;　　{i=(*s1);　　(*s1)=(*s2);　　(*s2)=i;　　}　　return;

66、　　}　　void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)　　{//輸出 HuffmanCode　　int i;<p&

67、gt;　　cout<<"\nnumber---element---weight---huffman code\n";　　for(i=1;i<=n;i++)　　cout<<" "<<i<<" "<<HT[i].e

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載