課程設(shè)計(jì)--哈夫曼編碼與譯碼

1、<p><b>　　哈夫曼編碼與譯碼</b></p><p>　　學(xué)生姓名： 指導(dǎo)老師：</p><p>　　摘 要 本課程設(shè)計(jì)主要解決的是利用哈夫曼樹生成的哈夫曼編碼進(jìn)行字符串的加密和解密，并將加密的編碼寫入文件。在此課程設(shè)計(jì)中，系統(tǒng)開發(fā)平臺(tái)為Windows XP，程序設(shè)計(jì)語言采用面向過程的高級(jí)語言C和面向?qū)ο蟮母呒?jí)語言C++，程序運(yùn)行平臺(tái)為Vis

2、ual C++ 6.0。在程序設(shè)計(jì)中，采用了結(jié)構(gòu)化與面向過程兩種解決問題的方法。程序通過調(diào)試運(yùn)行，初步實(shí)現(xiàn)了設(shè)計(jì)目標(biāo)，并且經(jīng)過適當(dāng)完善后，將可以應(yīng)用在商業(yè)中解決實(shí)際問題。</p><p>　　關(guān)鍵詞 哈夫曼樹，編碼，譯碼，文件操作，C，C++； </p><p><b>　　1 引 言</b></p><p><b>　　1.1 課

3、題背景</b></p><p>　　隨著信息時(shí)代的到來，各種信息日益豐富，信息迅速膨脹，對(duì)信息管理的工作量也日益增大。在信息化未到來之前，信息的存儲(chǔ)編碼也變得尤為重要，公司之間的信息需要編碼，用戶個(gè)人數(shù)據(jù)需要編碼，都需要占用很大的空間，所以一個(gè)好的、高效的編碼譯碼算法是十分重要的。好的加密算法不僅可以降低管理方的工作量和存儲(chǔ)量，還可以對(duì)用戶的信息進(jìn)行高效的管理，同時(shí)使在用中可以避免不必要的麻煩。 &l

4、t;/p><p>　　數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)(logical structure)是指數(shù)據(jù)元素之間邏輯關(guān)系的整體。所謂邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或鄰接關(guān)系。根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分為四類：集合、線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是面向問題的，反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式。為了區(qū)別于數(shù)據(jù)的

5、存儲(chǔ)結(jié)構(gòu)，常常將數(shù)據(jù)的邏輯結(jié)構(gòu)稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(storage structure)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示，換言之，存儲(chǔ)結(jié)構(gòu)除了數(shù)據(jù)元素之外，必須隱式或顯示地存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系。通常有兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。</p><p>　　樹是一種在實(shí)際應(yīng)用中被廣泛使用的數(shù)據(jù)結(jié)構(gòu)。它是由同一類型的記錄構(gòu)成的集合。哈夫曼樹是樹的一種子類型，又稱最優(yōu)樹，是一類帶

6、權(quán)路徑最短的樹，利用哈夫曼樹可以得到合適的字符編碼，這樣我們既可以對(duì)數(shù)據(jù)加密，也可以實(shí)現(xiàn)高效的存儲(chǔ)信息。因此哈夫曼編碼是一種常用的編碼方式。</p><p>　　1.2 課程設(shè)計(jì)目的</p><p>　　哈夫曼編碼與譯碼系統(tǒng)是為了實(shí)現(xiàn)信息的高效存儲(chǔ)與管理、加密、解密而設(shè)計(jì)的。通過建立一個(gè)有效，低存儲(chǔ)量，易于管理的編碼譯碼系統(tǒng)，使得企業(yè)對(duì)信息管理更加高效、準(zhǔn)確，更加科學(xué)化和正規(guī)化，降低企業(yè)對(duì)

7、信息管理的難度。</p><p>　　本課程設(shè)計(jì)主要是用數(shù)據(jù)結(jié)構(gòu)和文件實(shí)現(xiàn)的，通過程序的編寫、調(diào)試和運(yùn)行可以進(jìn)一步掌握數(shù)據(jù)結(jié)構(gòu)及算法的程序?qū)崿F(xiàn)的基本方法。理解對(duì)數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)及應(yīng)用，同時(shí)加深對(duì)哈夫曼樹的運(yùn)用及理解。本課程設(shè)計(jì)是利用哈夫曼編碼實(shí)現(xiàn)對(duì)字符串的加密、解密和低存儲(chǔ)量存儲(chǔ)，程序?qū)崿F(xiàn)哈夫曼樹的建立和哈夫曼編碼的生成，實(shí)現(xiàn)字符串的快速編碼、解密和保存。掌握哈夫曼編碼的工作原理，熟悉建立哈夫曼樹、利用哈夫曼編

8、碼進(jìn)行實(shí)際編碼、解碼等功能的實(shí)現(xiàn)，同時(shí)加深對(duì)文件的操作原理。 </p><p><b>　　1.3課程設(shè)計(jì)內(nèi)容</b></p><p>　　本課程設(shè)計(jì)主要是采用哈夫曼編碼對(duì)字符串的編碼、解碼，同時(shí)實(shí)現(xiàn)地存儲(chǔ)量要求。在設(shè)計(jì)的過程中，共用到兩種數(shù)據(jù)元素，第一種是哈夫曼樹建立是用到樹的結(jié)構(gòu)，樹節(jié)點(diǎn)信息包括父節(jié)點(diǎn)、左

9、子樹節(jié)點(diǎn)、右子樹節(jié)點(diǎn)以及該節(jié)點(diǎn)的權(quán)值其信息如圖1-1所示，第二種是在存儲(chǔ)個(gè)字符對(duì)應(yīng)編碼時(shí)用到的結(jié)構(gòu)，其中包括字符、字符密文以及其長(zhǎng)度，如圖1-2所示：</p><p>　　圖1-1 樹節(jié)點(diǎn)數(shù)據(jù)元素</p><p>　　圖1-2 每個(gè)字符密文數(shù)據(jù)元素</p><p>　　程序功能是實(shí)現(xiàn)對(duì)用戶輸入信息的編碼與解碼，并存入文件中，具體如圖1-3所示：</p>

10、<p>　　圖1-3 功能模塊圖</p><p><b>　　2 設(shè)計(jì)思路與方案</b></p><p><b>　　2.1 設(shè)計(jì)思路</b></p><p>　　C語言是結(jié)構(gòu)化和模塊化的語言，它是面向過程的。在處理較小規(guī)模的程序時(shí)，程序員用C語言還比較得心應(yīng)手。</p><p>　　C

11、++是由C語言發(fā)展而來的，與C語言兼容。用C語言編寫的程序基本上可以不加修改地用于C++。從C++的名字可以看出它是C的超集。C++既可以用于面向過程的結(jié)構(gòu)化程序設(shè)計(jì)，又可用于面向?qū)ο蟮某绦蛟O(shè)計(jì)，是一種功能強(qiáng)大的混合型的程序設(shè)計(jì)語言。</p><p>　　C++對(duì)C的“增強(qiáng)”，表現(xiàn)在兩個(gè)方面：</p><p>　　（1）在原來面向過程的機(jī)制基礎(chǔ)上，對(duì)C語言的功能做了不少擴(kuò)充。</p&

12、gt;<p>　?。?）增加了面向?qū)ο蟮臋C(jī)制。</p><p>　　作為一種編程約定，C++程序員傾向于只有當(dāng)所有的成員均為公共時(shí)才使用結(jié)構(gòu)。結(jié)構(gòu)（struct）是一種特殊的類，它的特殊之處在于其成員都是公共的（除非另作聲明）。C++程序員只有在所有成員都是公共的時(shí)候才會(huì)使用結(jié)構(gòu)。</p><p>　　在計(jì)算機(jī)中進(jìn)行編碼的方法有很多種，此文選擇哈弗曼編碼。哈弗曼編碼由哈弗曼樹

13、得到，所以我們要選擇存儲(chǔ)樹的數(shù)據(jù)結(jié)構(gòu)，為了高效的產(chǎn)生哈弗曼編碼，樹的存儲(chǔ)采用三叉鏈表的方式，同時(shí)增加一個(gè)選項(xiàng)以存儲(chǔ)各個(gè)樹結(jié)點(diǎn)的權(quán)值。同時(shí)將得到的密文存儲(chǔ)到文件中，以便我們進(jìn)行查看。</p><p><b>　　2.2 設(shè)計(jì)方案</b></p><p>　　通過分析可知，本課程設(shè)計(jì)主要功能是通過哈弗曼樹得到哈弗曼編碼，利用得到的哈弗曼編碼對(duì)字符串進(jìn)行編碼與譯碼，并存入文

14、件便于查看。由于構(gòu)造哈弗曼樹和根據(jù)哈弗曼樹得到編碼時(shí)要經(jīng)常對(duì)節(jié)點(diǎn)的父結(jié)點(diǎn)，左右子樹結(jié)點(diǎn)進(jìn)行訪問，所以采用三叉鏈表的方式存儲(chǔ)樹結(jié)點(diǎn)，同時(shí)在該結(jié)點(diǎn)信息中還需要增加一個(gè)選項(xiàng)存儲(chǔ)結(jié)點(diǎn)的權(quán)值。其次，為了解決得到的哈弗曼編碼的存儲(chǔ)問題，再建立一個(gè)結(jié)構(gòu)體，用于存儲(chǔ)每個(gè)字符所對(duì)應(yīng)編碼及編碼長(zhǎng)度，編碼的存儲(chǔ)簡(jiǎn)化了編碼與譯碼的操作。同時(shí)，將得到的密文存儲(chǔ)到文件中，便于我們查看。</p><p>　　定義一個(gè)結(jié)構(gòu)體HTNode將樹結(jié)點(diǎn)

15、，父結(jié)點(diǎn)，左右子樹結(jié)點(diǎn)及該結(jié)點(diǎn)的權(quán)值聯(lián)系在一起，便于操作。具體定義如下：</p><p>　　typedef struct//建立樹結(jié)點(diǎn)</p><p><b>　　{ </b></p><p>　　int weight;</p><p>　　int parent,lchild,rchild;</p>

16、<p><b>　　}HTNode; </b></p><p>　　定義一個(gè)結(jié)構(gòu)體CodeNode將各個(gè)字符對(duì)應(yīng)編碼及編碼的長(zhǎng)度聯(lián)系在一起，便于操作。具體定義如下：</p><p>　　typedef struct//建立每個(gè)編碼的結(jié)構(gòu)體</p><p><b>　　{</b></p>&l

17、t;p><b>　　char ch;</b></p><p>　　char bits[10];</p><p><b>　　int len;</b></p><p>　　}CodeNode;</p><p>　　同時(shí)，為了操作的方便，我們做如下處理：</p><p>　

18、　typedef HTNode HafumanTree[m+1];//重命名HTNode</p><p>　　typedef CodeNode HafumanCode[n+1];//重命名CodeNode</p><p><b>　　3 詳細(xì)設(shè)計(jì)</b></p><p>　　3.1 menu菜單功能</p><p&

19、gt;　　Menu菜單主要用于讓用戶選擇何種方式構(gòu)造哈弗曼樹，此時(shí)需要用戶輸入0或者1來進(jìn)行控制。該段代碼位于viod main()函數(shù)中。其代碼如下：</p><p>　　printf(" -------------------------------------------------------------------------- \n");</p><p&

20、gt;　　printf(" 歡迎使用編碼譯碼系統(tǒng)\n");</p><p>　　printf(" -------------------------------------------------------------------------- \n");</p><p>　　printf("請(qǐng)

21、輸入獲得權(quán)值的方法,輸入1表示自己輸入每個(gè)節(jié)點(diǎn)的權(quán)值,輸入0表示將每個(gè)字符在輸入字符串中出現(xiàn)的次數(shù)作為其權(quán)值:");</p><p>　　scanf("%d",&method); //通過用戶的輸入來判斷使用何種方式</p><p>　　其流程圖如圖3-1所示：</p><p>　　圖3-1 menu菜單</p&

22、gt;<p>　　3.2 int counttotal(char *s,int quan[],char str[])函數(shù)</p><p>　　當(dāng)用戶選擇通過輸入的字符串自動(dòng)獲取權(quán)值（統(tǒng)計(jì)出現(xiàn)的字符種數(shù)以及每種字符出現(xiàn)的次數(shù)， 將該種字符出現(xiàn)的次數(shù)作為它的權(quán)值）時(shí)，main函數(shù)將會(huì)調(diào)用該函數(shù)計(jì)算各個(gè)節(jié)點(diǎn)的權(quán)值，將相應(yīng)的字符存入str[]字符數(shù)組，同時(shí)該字符對(duì)應(yīng)的權(quán)值存入quan[]數(shù)組中。算法流程圖

23、如圖3-1：</p><p>　　圖3-1計(jì)算字符權(quán)值及字符種類算</p><p>　　說明：counttotal（）函數(shù)代碼見附錄。</p><p>　　3.3 void selectmin()函數(shù) </p><p>　　該函數(shù)的作用是在所有給定權(quán)值的結(jié)點(diǎn)中選出權(quán)值最小的兩個(gè)結(jié)點(diǎn)并返回，用于構(gòu)造哈弗曼樹。代碼如下：</p>

24、<p>　　void selectmin(HafumanTree HT,int k,int *s1,int*s2)</p><p>　　//選擇權(quán)值最小的兩個(gè)</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　int m

25、in=9999;//聲明一個(gè)int類型的數(shù)值min，賦個(gè)較大的輸給它</p><p>　　for(i=1;i<=k;i++)//選擇權(quán)值最小的一個(gè)節(jié)點(diǎn)（且該節(jié)點(diǎn)無父節(jié)點(diǎn)）</p><p><b>　　{</b></p><p>　　if((HT[i].weight<min)&&(HT[i].parent==0

26、))</p><p><b>　　{</b></p><p><b>　　j=i;</b></p><p>　　min=HT[i].weight;</p><p><b>　　}</b></p><p><b>　　}</b><

27、;/p><p><b>　　*s1=j;</b></p><p><b>　　min=9999;</b></p><p>　　for(i=1;i<=k;i++)</p><p><b>　　{</b></p><p>　　if((HT[i].weigh

28、t<min)&&(HT[i].parent==0)&&(i!=*s1))</p><p>　　//選擇權(quán)值最小的一個(gè)節(jié)點(diǎn)（且該節(jié)點(diǎn)無父節(jié)點(diǎn)）</p><p><b>　　{ j=i;</b></p><p>　　min=HT[i].weight;</p><p><b&

29、gt;　　}</b></p><p><b>　　}</b></p><p><b>　　*s2=j;</b></p><p><b>　　}</b></p><p>　　說明:本函數(shù)返回兩個(gè)權(quán)值最小的結(jié)點(diǎn)信息分別存儲(chǔ)在s1和s2中，為下一步構(gòu)造哈弗曼樹做準(zhǔn)備。&l

30、t;/p><p>　　3.4 void creathafumantree( )函數(shù)</p><p>　　Creathafumantree（）函數(shù)用于構(gòu)造一棵哈夫曼樹，構(gòu)造哈弗曼樹的步驟為：</p><p>　　根據(jù)給定n個(gè)權(quán)值構(gòu)成n棵二叉樹的集合F，其中每棵二叉樹Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，其左右字?jǐn)?shù)均為空。</p><p>　　在F中選取

31、兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左、右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)權(quán)值之和。</p><p>　　在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中。</p><p>　　重復(fù)步驟（2）和（3），直到F只含一棵樹為止，得到的樹便是哈夫曼樹。</p><p>　　其算法流程圖如圖3-3所示：</p>&l

32、t;p>　　圖 3-3 函數(shù)creathafumantree( )的算法流程圖</p><p>　　說明：其源代碼見附錄</p><p>　　3.5 void Hafumanencode( )函數(shù)</p><p>　　Hafumanencode( )函數(shù)是根據(jù)creathafumantree( )函數(shù)構(gòu)造的哈弗曼樹得到哈弗曼編碼。根據(jù)每個(gè)字符在哈夫曼樹中的位置

33、來編譯每個(gè)字符的0、1密文代碼，從葉節(jié)點(diǎn)判斷該葉節(jié)點(diǎn)是其父節(jié)點(diǎn)的左右字左字為‘0’，右子為‘1’，在判斷父節(jié)點(diǎn)是上級(jí)父節(jié)點(diǎn)的左右子直至根節(jié)點(diǎn)，將生成的0、1字符串按所表示的字符倒序存入HC相應(yīng)的字符的bins[]數(shù)組，代碼如下：</p><p>　　void Hafumanencode(HafumanTree HT,HafumanCode HC)</p><p><b>　　{&

34、lt;/b></p><p>　　int c,p,i;</p><p>　　char cd[n];//臨時(shí)數(shù)組用于記錄字符在哈夫曼樹的位置</p><p>　　int start;</p><p>　　cd[num]='\0';//給cd賦個(gè)結(jié)束符</p><p>　　for

35、(i=1;i<=num;i++)</p><p><b>　　{</b></p><p>　　start=num;</p><p><b>　　c=i;</b></p><p>　　while((p=HT[c].parent)>0)</p><p>　　//根據(jù)

36、節(jié)點(diǎn)是其父節(jié)點(diǎn)的左右子來記錄它的位置</p><p><b>　　{</b></p><p>　　cd[--start]=(HT[p].lchild==c)?'0':'1';</p><p>　　c=p;//將父節(jié)點(diǎn)轉(zhuǎn)為子節(jié)點(diǎn)</p><p><b>　　}<

37、/b></p><p>　　strcpy(HC[i].bits,&cd[start]);//將得到的0、1字串存入結(jié)構(gòu)體HC</p><p>　　printf("%c:%s\n",HC[i].ch,HC[i].bits);</p><p>　　HC[i].len=num-start;//求每個(gè)字符0、1編碼長(zhǎng)度<

38、;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　3.6 void codenum( )函數(shù)</p><p>　　codenum（）函數(shù)主要用于對(duì)輸入字符串進(jìn)行編碼。根據(jù)Hafumanencode( )函數(shù)得到的編碼，將字符串轉(zhuǎn)化為密文，為了方便查看，最

39、后會(huì)將得到的密文存入文件code.txt中。該函數(shù)由于要涉及到文件操作，故定義了文件流指針fp。該函數(shù)的算法流程圖如圖3-4所示：</p><p>　　3.7 char *decode( )函數(shù)</p><p>　　decode（）函數(shù)用于將已加密的密文進(jìn)行譯碼翻譯為原字符串。解碼時(shí)從code.txt</p><p>　　文件夾中，一個(gè)一個(gè)字符的讀出那串0、1代碼賦

40、給一個(gè)臨時(shí)字符串cd[]，用該字符串與每個(gè)字符的HC[i].bins密文比較，直到與一個(gè)字符的密文相同時(shí)，譯出該字符，將字符存放在臨時(shí)字符數(shù)組tempstr[]中，清空臨時(shí)字符串繼續(xù)讀取0、1代碼進(jìn)行翻譯，直至文件密文結(jié)束為止。于是就得到了原先被加密的那串字符串。該函數(shù)的算法流程圖如圖3-5所示：</p><p><b>　　4 運(yùn)行結(jié)果</b></p><p>　　

41、(1) 運(yùn)行程序，菜單如圖4-1：</p><p>　　圖 4-1 功能菜單</p><p>　　(2) 若要自己輸入每個(gè)字符的權(quán)值，輸入1后回車，如圖4-2：</p><p>　　圖4-2 菜單狀態(tài)輸入1(選擇自己輸入權(quán)值)</p><p>　　(3) 在(2)之后需要輸入字符的種類數(shù)，這里假定有三種，輸入3回車，</p>&

42、lt;p><b>　　圖4-3：</b></p><p>　　圖4-3 輸入字符出現(xiàn)的種類數(shù)</p><p>　　(4) 在(3)之后需要輸入第一個(gè)字符和該字符的權(quán)值，假定輸入字符a和權(quán)值3，回車會(huì)提示輸入第二字符和其權(quán)值，輸入字符b和權(quán)值5，回車，繼續(xù)提示輸入第三字符和其權(quán)值，輸入字符c和權(quán)值7，確認(rèn)回車，如圖4-3：</p><p>

43、　　圖4-4 輸入字符和字符的權(quán)值</p><p>　　(5) 在(4)確認(rèn)之后哈夫曼樹已經(jīng)構(gòu)造好，并且編碼已經(jīng)得到，這時(shí)會(huì)輸出各個(gè)字符、相應(yīng)權(quán)值及該字符的哈夫曼編碼，同時(shí)會(huì)提示輸入要按照得到的哈夫曼編碼進(jìn)行編碼的字符串，如圖4-5：</p><p>　　圖4-5 各字符的哈夫曼編碼</p><p>　　(6) 在(5)之后需要輸入要進(jìn)行編碼的字符串，假定輸入字符串

44、abcbcbaa，如圖4-6：</p><p>　　圖4-6 輸入要編碼的字符串 </p><p>　　(7) 在(6)之后確認(rèn)輸入，程序會(huì)將得到的編碼輸出，并將編碼寫入文件code.txt(當(dāng)前工程工作路徑下)，寫入后會(huì)提示寫入文件成功，同時(shí)程序會(huì)根據(jù)每個(gè)字符的哈夫曼編碼和code.txt文件中的字符串編碼譯碼，并輸出，最后會(huì)提示是否要繼續(xù)運(yùn)行該程序。如圖4-7：</p>

45、<p>　　圖4-7 編碼譯碼及寫入文件</p><p>　　(8) 在(7)之后輸入1后回車，繼續(xù)運(yùn)行該編碼譯碼程序，同時(shí)演示第二種編碼譯碼方式(即不主動(dòng)輸入權(quán)值，將該種字符出現(xiàn)的次數(shù)作為它的權(quán)值)，輸入0回車，如圖4-8：</p><p>　　圖4-8 繼續(xù)運(yùn)行并選擇第二種方式</p><p>　　(9) 在(8)之后確認(rèn)回車，系統(tǒng)會(huì)提示輸入將要編碼的

46、字符串，假定這里輸入字符串a(chǎn)sddcxxsad，如圖4-9：</p><p>　　圖4-9 輸入要進(jìn)行編碼的字符串</p><p>　　(10) 在(9)之后確認(rèn)回車，系統(tǒng)將對(duì)輸入的字符串進(jìn)行統(tǒng)計(jì)，得到輸入字符的種類并計(jì)算出各字符的權(quán)值，同時(shí)根據(jù)得到的權(quán)值構(gòu)造哈夫曼樹并得到哈夫曼編碼，最后會(huì)根據(jù)哈夫曼編碼對(duì)字符串進(jìn)行編碼，同時(shí)會(huì)將編碼寫入文件，譯碼輸出。如圖4-10：</p>

47、<p>　　圖4-10 編碼譯碼及寫入文件</p><p>　　(11) 在程序運(yùn)行后系統(tǒng)會(huì)提示輸入0或1選擇編碼方式，若輸入其它的數(shù)值，系統(tǒng)會(huì)提示錯(cuò)誤輸入，如圖4-11：</p><p>　　圖4-11 錯(cuò)誤輸入</p><p>　　(12) 在程序運(yùn)行后系統(tǒng)會(huì)提示是否需要繼續(xù)進(jìn)行編碼譯碼，輸入0則推出系統(tǒng)，如圖4-12：</p><

48、;p>　　圖4-12 退出系統(tǒng)</p><p><b>　　5 結(jié)束語</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)和現(xiàn)代計(jì)算機(jī)技術(shù)的實(shí)際應(yīng)用相結(jié)合，是我們?cè)诒緦W(xué)期學(xué)完理論課程之后對(duì)自己學(xué)習(xí)能力的一次很好的檢驗(yàn)，從開始的算法思路到運(yùn)行調(diào)試后的可執(zhí)行程序，都是一個(gè)很好的學(xué)習(xí)和鍛煉的過程。既可以使我們鞏固了原有的理論知識(shí)，培養(yǎng)了我們靈活運(yùn)用和組合集成所學(xué)過知識(shí)及技能

49、來分析、解決實(shí)際問題的能力，也可以使我們體會(huì)到自身知識(shí)和能力能在實(shí)際中的應(yīng)用和發(fā)揮。不但可以激發(fā)創(chuàng)新意識(shí)，還可以開發(fā)創(chuàng)造能力、培養(yǎng)溝通能力。這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的時(shí)間里雖然時(shí)間有限，但確實(shí)使我受益非淺。通過實(shí)踐課程設(shè)計(jì)我豐富了編譯工具操作經(jīng)驗(yàn)，更加深了對(duì)C和C++語言的了解，熟悉了其環(huán)境，更增強(qiáng)了對(duì)哈夫曼樹的理解與運(yùn)用。</p><p>　　而且，在完成本課程設(shè)計(jì)的過程中，也充滿磨練了我的意志，鍛煉了我的耐心、認(rèn)

50、真。在實(shí)踐的過程中，需要不倦的查閱資料，甚至需要求助于老師、同學(xué)。要善于思考，多動(dòng)手。我深知，獨(dú)立完成這樣一項(xiàng)任務(wù)需要克服許多困難。</p><p>　　總之，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)讓我受益良多，我會(huì)好好珍惜像這種難得的機(jī)會(huì)，努力學(xué)習(xí)知識(shí)。也感謝幫助了我的老師、同學(xué)。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏，

51、吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社，2011.5 </p><p>　　[2] 汪潔，數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法實(shí)現(xiàn)與習(xí)題解答.人民郵電出版社，2004.1</p><p>　　[3] 譚浩強(qiáng)，C++程序設(shè)計(jì)（第一版）.北京：清華大學(xué)出版社，2010.6</p><p>　　[4] 譚浩強(qiáng)，C程序設(shè)計(jì)（第三版）.北京：清華大學(xué)出版社，2005.7</p>

52、<p><b>　　附 錄 ：源程序</b></p><p>　　// 程序名稱：哈夫曼編碼與譯碼</p><p><b>　　// 程序作者：</b></p><p>　　// 最后修改日期：2012-6-27</p><p>　　#include <iostream>&

53、lt;/p><p>　　#include <stdlib.h></p><p>　　#include <string.h></p><p>　　using namespace std;</p><p>　　#define n 100//葉節(jié)點(diǎn)的個(gè)數(shù)小等于n</p><p>　　#def

54、ine m 2*n-1//總結(jié)點(diǎn)的個(gè)數(shù)為m=2*n-1</p><p>　　int num;//定義一個(gè)全局變量用于存放字符種類個(gè)數(shù)</p><p>　　typedef struct </p><p>　　//結(jié)構(gòu)體用于存放樹節(jié)點(diǎn)包括節(jié)點(diǎn)的父節(jié)點(diǎn)、左子、右子以及權(quán)值</p><p><b>　　{ <

55、;/b></p><p>　　int weight;</p><p>　　int parent,lchild,rchild;</p><p><b>　　}HTNode;</b></p><p>　　typedef HTNode HafumanTree[m+1];//重命名HTNode HT</p

56、><p>　　typedef struct//結(jié)構(gòu)體由于存放每個(gè)字符的密文和長(zhǎng)度</p><p><b>　　{</b></p><p><b>　　char ch;</b></p><p>　　char bits[10];</p><p><b>　　in

57、t len;</b></p><p>　　}CodeNode;</p><p>　　typedef CodeNode HafumanCode[n+1];//重命名CodeNode HC</p><p>　　int main(int argc, char* argv[])</p><p><b>　　{<

58、/b></p><p>　　int quan[27],k=1,length,count=1,total,method;</p><p>　　//聲明一個(gè)數(shù)組用以存放26字符的權(quán)</p><p>　　值,length表示要加密字符串的長(zhǎng)度</p><p>　　//count用于控制輸入字符和權(quán)值的次數(shù),total</p>

59、<p>　　用于循環(huán)控制,k用于控制解密，加密的次數(shù)</p><p>　　//method用于控制使用何種方法進(jìn)行輸入權(quán)值</p><p>　　char getstr[300],str[27];</p><p>　　//聲明兩個(gè)字符串?dāng)?shù)組一個(gè)用于存輸入,一個(gè)由于存放</p><p><b>　　輸入中含有的字符<

60、;/b></p><p>　　char *s; //聲明一個(gè)char型指針用于指向字符HafumanTree HT;</p><p>　　HafumanCode HC; //聲明m+1個(gè)樹節(jié)點(diǎn)</p><p>　　HafumanTree HT; //聲明n+1個(gè)code</p><p>　　int c

61、ounttotal(char *s,int quan[],char str[]);//聲明需要調(diào)用的函數(shù)</p><p>　　void creathafumantree(HafumanTree HT,HafumanCode HC,int quan[],char str[]);</p><p>　　void Hafumanencode(HafumanTree HT,HafumanCo

62、de HC);</p><p>　　void codenum(HafumanCode HC,char *str);</p><p>　　char *decode(HafumanCode HC);</p><p><b>　　while(k)</b></p><p><b>　　{</b></p

63、><p>　　printf(" --------------------------------------------------------------------- \n");</p><p>　　printf(" 歡迎使用編碼譯碼系統(tǒng)\n");</p><p>　　printf(

64、" --------------------------------------------------------------------- \n");</p><p>　　printf("請(qǐng)輸入獲得權(quán)值的方法,輸入1表示自己輸入每個(gè)節(jié)點(diǎn)的權(quán)值,輸入0表示將每個(gè)字符在輸入字符串中出現(xiàn)的次數(shù)作為其權(quán)值:");</p><p>　　scanf(

65、"%d",&method);</p><p>　　if(method==0) </p><p><b>　　{</b></p><p>　　printf("請(qǐng)輸入要編碼的字符串(請(qǐng)輸入小寫字母):");</p><p>　　gets(getstr); //

66、</p><p>　　scanf("%s",&getstr); //獲得輸入的字符串</p><p>　　num=counttotal(getstr,quan,str);//統(tǒng)計(jì)字符串中含有字符種類個(gè)數(shù)</p><p>　　creathafumantree(HT,HC,quan,str); //根據(jù)字符權(quán)值構(gòu)建哈夫曼樹&

67、lt;/p><p>　　Hafumanencode(HT,HC);//根據(jù)哈夫曼樹確定每個(gè)字符的code</p><p>　　codenum(HC,getstr);//將字符串譯碼存入文件夾</p><p>　　s=decode(HC);//將暗文解碼</p><p>　　printf("解密為：\n"

68、);</p><p>　　printf("%s\n",s);</p><p>　　printf("是否想繼續(xù)編碼、解碼,是輸入1回車,否輸入0回車:");</p><p>　　scanf("%d",&k);</p><p><b>　　}</b><

69、/p><p>　　else if(method==1)</p><p><b>　　{</b></p><p>　　total=1; //每次都要將其清零，以達(dá)到控制循環(huán)的效果</p><p>　　printf("請(qǐng)輸入要編碼字符所出現(xiàn)的種類數(shù):");</p><p>　　s

70、canf("%d",&length);</p><p>　　for(count=1;count<=length;count++)</p><p><b>　　{</b></p><p>　　printf("請(qǐng)輸入第%d個(gè)字符和該字符的權(quán)值(中間留一個(gè)空格):",count);</p&g

71、t;<p>　　cin>>str[total]>>quan[total];</p><p><b>　　total++;</b></p><p><b>　　}</b></p><p>　　num=length;</p><p>　　creathafumantr

72、ee(HT,HC,quan,str);//根據(jù)字符權(quán)值構(gòu)建哈夫曼樹</p><p>　　Hafumanencode(HT,HC);//根據(jù)哈夫曼樹確定每個(gè)字符的code</p><p>　　printf("請(qǐng)輸入要編碼的字符串:");</p><p>　　cin>>getstr;</p><p>　　co

73、denum(HC,getstr);//將字符串譯碼存入文件夾</p><p>　　s=decode(HC);//將暗文解碼</p><p>　　printf("解密為：\n");</p><p>　　printf("%s\n",s);</p><p>　　printf(&q

74、uot;是否想繼續(xù)編碼、解碼,是輸入1回車,否輸入0回車:\n");</p><p>　　scanf("%d",&k);</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b&

75、gt;</p><p>　　printf("錯(cuò)誤輸入!\n");</p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　system(

76、"pause");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int counttotal(char *s,int quan[],char str[])//計(jì)算字符串中字符權(quán)值</p><p><

77、;b>　　{</b></p><p><b>　　char *p;</b></p><p>　　int i,j,k,quantemp[27];</p><p>　　for(i=1;i<27;i++)//將所有字符的權(quán)值賦成0</p><p>　　quantemp[i]=0;<

78、/p><p>　　for(p=s;*p!='\0';p++)//判斷字符串是否結(jié)束</p><p>　　if(*p>='a'&&*p<='z')//判斷字符是否為26字母</p><p><b>　　{</b></p><p&g

79、t;　　k=*p-96;//看是26個(gè)字符中的哪個(gè)字符</p><p>　　quantemp[k]++;//字符權(quán)值加1</p><p><b>　　}</b></p><p><b>　　j=0;</b></p><p>　　for(i=1,j=0;i<27;i++)&

80、lt;/p><p><b>　　{</b></p><p>　　if(quantemp[i]!=0)</p><p><b>　　{</b></p><p>　　j++;//用于統(tǒng)計(jì)字符種類個(gè)數(shù)</p><p>　　str[j]=i+96;//str按字母表順序存

81、儲(chǔ)出現(xiàn)過的字符</p><p>　　quan[j]=quantemp[i];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return j; //返回該數(shù)據(jù)給num賦值</p><p>&l

82、t;b>　　}</b></p><p>　　void selectmin(HafumanTree HT,int k,int *s1,int*s2)//選擇權(quán)值最小的兩個(gè)</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>

83、　　int min=9999;//聲明一個(gè)int類型的數(shù)值min，賦個(gè)較大的輸給它</p><p>　　for(i=1;i<=k;i++)//選擇權(quán)值最小的一個(gè)節(jié)點(diǎn)（且該節(jié)點(diǎn)無父節(jié)點(diǎn)）</p><p><b>　　{</b></p><p>　　if((HT[i].weight<min)&&(HT[i].

84、parent==0))</p><p><b>　　{</b></p><p><b>　　j=i;</b></p><p>　　min=HT[i].weight;</p><p><b>　　}</b></p><p><b>　　}<

85、/b></p><p><b>　　*s1=j;</b></p><p><b>　　min=9999;</b></p><p>　　for(i=1;i<=k;i++)</p><p><b>　　{</b></p><p>　　if((HT

86、[i].weight<min)&&(HT[i].parent==0)&&(i!=*s1))</p><p>　　//選擇權(quán)值最小的一個(gè)節(jié)點(diǎn)（且該節(jié)點(diǎn)無父節(jié)點(diǎn)）</p><p><b>　　{</b></p><p><b>　　j=i;</b></p><p&

87、gt;　　min=HT[i].weight;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　*s2=j;</b></p><p><b>　　}</b></p><p>

88、<b>　　//構(gòu)建哈夫曼樹</b></p><p>　　void creathafumantree(HafumanTree HT,HafumanCode HC,int quan[],char str[]) </p><p><b>　　{</b></p><p>　　int i,s1,s2;</p>&l

89、t;p>　　for(i=1;i<2*num-1;i++)//將所有的節(jié)點(diǎn)賦空</p><p><b>　　{</b></p><p>　　HT[i].lchild=0;HT[i].rchild=0;</p><p>　　HT[i].parent=0;HT[i].weight=0;</p><p>

90、;<b>　　}</b></p><p>　　for(i=1;i<=num;i++)//將num個(gè)字符的權(quán)值賦給num葉節(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　HT[i].weight=quan[i];</p><p><b>　　}</b&

91、gt;</p><p>　　for(i=1;i<=num;i++)//將num個(gè)字符賦給codenode</p><p><b>　　{</b></p><p>　　HC[i].ch=str[i];</p><p><b>　　}</b></p><p>&

92、lt;b>　　i=1;</b></p><p>　　while(i<=num)</p><p><b>　　{ </b></p><p>　　printf("字符為%c,權(quán)值為%d\n",HC[i].ch,quan[i]);</p><p><b>　　i++;<

93、;/b></p><p>　　}//輸出每個(gè)字符的及其權(quán)值</p><p>　　for(i=num+1;i<=2*num-1;i++)</p><p><b>　　{</b></p><p>　　selectmin(HT,i-1,&s1,&s2);</p><p>

94、;　　//選擇兩個(gè)權(quán)值最小的葉節(jié)點(diǎn),分別存放于s1和s2</p><p>　　HT[s1].parent=i;</p><p>　　HT[s2].parent=i;//兩個(gè)節(jié)點(diǎn)指向同一父節(jié)點(diǎn)</p><p>　　HT[i].lchild=s1;HT[i].rchild=s2;</p><p>　　HT[i].weight=HT[s1

95、].weight+HT[s2].weight;</p><p>　　//父節(jié)點(diǎn)的權(quán)值為子節(jié)點(diǎn)相加（父節(jié)點(diǎn)繼續(xù)放入選擇區(qū)）</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Hafumanencode(HafumanTree HT,H

96、afumanCode HC)</p><p><b>　　{</b></p><p>　　int c,p,i;</p><p>　　char cd[n];//臨時(shí)數(shù)組用于記錄字符在哈夫曼樹的位置</p><p>　　int start;</p><p>　　cd[num]='\0

97、';//給cd賦個(gè)結(jié)束符</p><p>　　for(i=1;i<=num;i++)</p><p><b>　　{</b></p><p>　　start=num;</p><p><b>　　c=i;</b></p><p>　　while(

98、(p=HT[c].parent)>0)</p><p>　　//根據(jù)節(jié)點(diǎn)是其父節(jié)點(diǎn)的左右子來記錄它的位置</p><p><b>　　{</b></p><p>　　cd[--start]=(HT[p].lchild==c)?'0':'1';</p><p>　　c=p;

99、//將父節(jié)點(diǎn)轉(zhuǎn)為子節(jié)點(diǎn)</p><p><b>　　}</b></p><p>　　strcpy(HC[i].bits,&cd[start]);//將得到的0、1字串存入結(jié)構(gòu)體HC</p><p>　　printf("%c:%s\n",HC[i].ch,HC[i].bits);</p><

100、;p>　　HC[i].len=num-start;//求每個(gè)字符0、1編碼長(zhǎng)度</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//根據(jù)哈夫曼樹確定每個(gè)字符的0、1代碼code</p><p>　　void codenum(Hafu

101、manCode HC,char *str) </p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　FILE *fp;//聲明一個(gè)文件夾指針</p><p>　　fp=fopen("code.txt",

102、"w");//打開文件夾codefile</p><p>　　printf("密文為：\n");</p><p>　　while(*str)//字符串未結(jié)束時(shí)</p><p><b>　　{</b></p><p>　　for(i=1;i<=n

103、um;i++)</p><p><b>　　{</b></p><p>　　if(HC[i].ch==*str)//判斷字符是否在Codenode中存在</p><p><b>　　{</b></p><p>　　for(j=0;j<HC[i].len;j++)</p&

104、gt;<p>　　//將codenode中該字符的1、0代碼存入文件夾</p><p><b>　　{</b></p><p>　　fputc(HC[i].bits[j],fp);</p><p><b>　　}</b></p><p>　　printf("%s",

105、HC[i].bits);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　str++;//字符后移</p><p><b>

106、　　}</b></p><p>　　printf("\n");</p><p>　　printf("編碼寫入文件--code.txt成功!!!"); //提示寫入文件成功</p><p>　　printf("\n");</p><p>　　fclose(fp

107、);</p><p><b>　　}</b></p><p>　　char *decode(HafumanCode HC)</p><p><b>　　{</b></p><p><b>　　FILE *fp;</b></p><p>　　char te

108、mpstr[9999];</p><p><b>　　char *p;</b></p><p>　　static char cd[n+1];//char型數(shù)組用于存放從文件夾中讀取的1、0代碼</p><p>　　int i,j,k=0,end;</p><p>　　fp=fopen("code.txt&q

109、uot;,"r");</p><p>　　while(!feof(fp))//當(dāng)文件夾讀取沒有結(jié)束</p><p><b>　　{</b></p><p>　　end=0;//判讀一個(gè)字符是否譯碼結(jié)束</p><p>　　for(i=0;(i<num)&

110、&(end==0)&&(!feof(fp));i++)</p><p>　　//當(dāng)一個(gè)字符未譯完并且文件未讀取結(jié)束</p><p><b>　　{ </b></p><p>　　cd[i]=' ';cd[i+1]='\0';//讓cd[]賦成空格</p><

111、;p>　　cd[i]=fgetc(fp);//讀取文件夾中的一個(gè)字符</p><p>　　for(j=1;j<=num;j++)</p><p><b>　　{</b></p><p>　　if(strcmp(HC[j].bits,cd)==0)</p><p>　　//看cd

112、[]的字符串是否等于Codenode中的某個(gè)密文</p><p><b>　　{</b></p><p>　　tempstr[k]=HC[j].ch;</p><p><b>　　end=1;</b></p><p>　　printf("=%s=",HC[j].bits);<

113、;/p><p><b>　　k++;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　//將譯出的字符賦給臨時(shí)字符串tempstr[],標(biāo)記一個(gè)字符譯碼結(jié)束jsjs賦1，跳出循環(huán)</p><

114、;p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　tempstr[k]='\0';//賦給臨