赫夫曼課程設(shè)計(jì)

1、目目 錄錄前言前言.1 1正文正文.1 11.1 課程設(shè)計(jì)的教學(xué)目的和任務(wù) .11.2 課程設(shè)計(jì)的主要內(nèi)容 .11.3 課程設(shè)計(jì)報(bào)告的要求.22.1.問(wèn)題描述及基本要求 .22.2. 算法思想 .22.3 模塊劃分 .22.3.1 構(gòu)造赫夫曼樹(shù).22.3.2 赫夫曼編碼(huffmancode).32.4. 數(shù)據(jù)結(jié)構(gòu) .52.5. 算法的時(shí)空分析 .52.6 測(cè)試數(shù)據(jù) .62.7. 測(cè)試情況 .6總總 結(jié)結(jié).7 7參考文獻(xiàn)：參考文獻(xiàn)：.7 7附附 錄錄.9 9塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 1 頁(yè) 共 14 頁(yè)前言前言赫夫曼編碼(Huffman Coding)是一種編碼方式，赫夫曼編碼是可變

2、字長(zhǎng)編碼(VLC)的一種。赫夫曼壓縮是個(gè)無(wú)損的壓縮算法，一般用來(lái)壓縮文本和程序文件。赫夫曼壓縮屬于可變代碼長(zhǎng)度算法一族。意思是個(gè)體符號(hào)（例如，文本文件中的字符）用一個(gè)特定長(zhǎng)度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。赫夫曼編碼的應(yīng)用很廣泛，利用赫夫曼樹(shù)求地的二進(jìn)制編碼稱為赫夫曼編碼。赫夫曼樹(shù)中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹(shù)的分支表示“0”碼，指向右子樹(shù)的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為對(duì)應(yīng)的編碼，這就是赫夫曼編碼。我們?cè)趯?duì)一些問(wèn)題進(jìn)行求解時(shí)，會(huì)發(fā)現(xiàn)有些問(wèn)題很難找到規(guī)律，或者根本無(wú)規(guī)

3、律可尋。對(duì)于這樣的問(wèn)題，可以利用計(jì)算機(jī)運(yùn)算速度快的特點(diǎn)，先搜索查找所有可能出現(xiàn)的情況，再根據(jù)題目條件從所有可能的情況中，刪除那些不符合條件的解。由赫夫曼算法的定義可知，初始森林中共有 n 棵只含有根結(jié)點(diǎn)的二叉樹(shù)。算法的的第二步是：算法的的第二步是：將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹(shù)，合并成一棵新的二叉樹(shù)，每合并一次，森林中就減少一棵樹(shù)，產(chǎn)生一個(gè)新結(jié)點(diǎn)。則要進(jìn)行 n-1 次合并，所以共產(chǎn)生 n-1 個(gè)新結(jié)點(diǎn)。由此可知，最終求得的赫夫曼樹(shù)中一共有 2n-1 個(gè)結(jié)點(diǎn)。其中， n 個(gè)結(jié)點(diǎn)是初始森林中的 n 個(gè)孤立結(jié)點(diǎn)。并且赫夫曼樹(shù)中沒(méi)有度數(shù)為 1 的分支的結(jié)點(diǎn)。采用赫夫曼編碼方案，即應(yīng)用赫夫曼樹(shù)

4、構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。正文正文1.1 課程設(shè)計(jì)的教學(xué)目的和任務(wù)(1) 使學(xué)生進(jìn)一步理解和掌握所學(xué)的各種基本抽象數(shù)據(jù)類(lèi)型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛑械氖褂梅椒ā?2) 使學(xué)生初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、設(shè)計(jì)、編碼、測(cè)試等基本方法和基本技能。(3) 使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。(4) 使學(xué)生能用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。1.2 課程設(shè)計(jì)的主要內(nèi)容(1) 問(wèn)題分析和任務(wù)定義。根據(jù)題目的要求，充分地分析和理解問(wèn)題，明確問(wèn)題要求做什么？限制條件是什么？(

5、2) 邏輯設(shè)計(jì)。對(duì)問(wèn)題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類(lèi)型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類(lèi)型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫(xiě)出每個(gè)抽象數(shù)據(jù)類(lèi)型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說(shuō)明） ，各個(gè)主要模塊的算法，并畫(huà)出模塊之間的調(diào)用關(guān)系圖。(3) 物理設(shè)計(jì)。定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫(xiě)出各函數(shù)的偽代碼算法。在這個(gè)過(guò)程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試，抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說(shuō)明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫(xiě)出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類(lèi)型定義，寫(xiě)出函數(shù)形式的算法框架。(4)程序編碼

6、。把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚。(5) 程序調(diào)試與測(cè)試。塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 2 頁(yè) 共 14 頁(yè)采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)確定疑點(diǎn)，通過(guò)修改程序來(lái)證實(shí)它或繞過(guò)它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果。(6) 結(jié)果分析。程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析。(7) 撰寫(xiě)課程設(shè)計(jì)報(bào)告。1.3 課程設(shè)計(jì)報(bào)告的要求課程設(shè)計(jì)報(bào)告要求規(guī)范書(shū)寫(xiě)。應(yīng)當(dāng)包括如下內(nèi)容： 問(wèn)題描述：描述

7、要求編程解決的問(wèn)題。 基本要求：給出程序要達(dá)到的具體的要求。 測(cè)試數(shù)據(jù)：設(shè)計(jì)測(cè)試數(shù)據(jù)，或具體給出測(cè)試數(shù)據(jù)。要求測(cè)試數(shù)據(jù)能全面地測(cè)試所設(shè)計(jì)程序的功能。 算法思想：描述解決相應(yīng)問(wèn)題算法的設(shè)計(jì)思想。 模塊劃分：描述所設(shè)計(jì)程序的各個(gè)模塊（即函數(shù)）功能。 數(shù)據(jù)結(jié)構(gòu)：給出所使用的基本抽象數(shù)據(jù)類(lèi)型，所定義的具體問(wèn)題的數(shù)據(jù)類(lèi)型，以及新定義的抽象數(shù)據(jù)類(lèi)型。 源程序：給出所有源程序清單，要求程序有充分的注釋語(yǔ)句，至少要注釋每個(gè)函數(shù)參數(shù)的含義和函數(shù)返回值的含義。 測(cè)試情況：給出程序的測(cè)試情況，并分析運(yùn)行結(jié)果。 算法的時(shí)空分析(包括基本操作和其他算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析)和改進(jìn)設(shè)想；經(jīng)驗(yàn)和體會(huì)等。 參考文獻(xiàn)

8、：列出參考的相關(guān)資料和書(shū)籍。2.1.問(wèn)題描述及基本要求利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本，試設(shè)計(jì)一個(gè)赫夫曼編碼系統(tǒng)。從鍵盤(pán)輸入一段報(bào)文（如what did you do that made you so happy） ，輸出這段報(bào)文的赫夫曼編碼。2.2. 算法思想赫夫曼編碼是根據(jù)可變長(zhǎng)最佳編碼定理，應(yīng)用赫夫曼算法而產(chǎn)生的一種編碼，是消除編碼冗余度最常用的方法。它的平均碼字長(zhǎng)度在具有相同輸入概率集合的前提下，比其它任何一種可譯碼都小，因此，也常被稱為緊湊碼。將輸入的字符串統(tǒng)計(jì)其個(gè)數(shù)算出百分率，最為它的權(quán)值，然后將各權(quán)值創(chuàng)建赫夫曼樹(shù)，計(jì)算出對(duì)應(yīng)的編碼。通過(guò)

9、譯碼字符串，從根部出發(fā)，按字符0和1確定找左右孩子。2.3 模塊劃分2.3.1 構(gòu)造赫夫曼樹(shù)給定 n 個(gè)實(shí)數(shù) w1，w2， ，wn（n） ，求一個(gè)具有 n 個(gè)結(jié)點(diǎn)的二叉數(shù)，使其帶權(quán)路徑長(zhǎng)度最小。所謂樹(shù)的帶權(quán)路徑長(zhǎng)度，就是樹(shù)中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為 0 層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)） 。樹(shù)的帶權(quán)路徑長(zhǎng)度記為 WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N 個(gè)權(quán)值 Wi(i=1,2,.n)構(gòu)成一棵有N 個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為 Li(i=1,2,.n)?？梢宰C明赫夫曼樹(shù)的WPL 是最小的。(1) 根據(jù)與 n 個(gè)權(quán)值

10、w1,w2wn對(duì)應(yīng)的 n 個(gè)結(jié)點(diǎn)構(gòu)成具有 n 棵二叉樹(shù)的森林 F=T1,T2Tn,其中第 i 棵二叉樹(shù) Ti(1 i n)都只有一個(gè)權(quán)值為 wi 的根結(jié)點(diǎn)，其左、右子樹(shù)均為空塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 3 頁(yè) 共 14 頁(yè)(2) 在森林 F 中選出兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為一棵新樹(shù)的左、右子樹(shù)，且置新樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)權(quán)值之和(3) 從 F 中刪除構(gòu)成新樹(shù)的那兩棵，同時(shí)把新樹(shù)加入 F 中(4) 重復(fù)第(2)和第(3)步，直到 F 中只含有一棵為止，此樹(shù)便為赫夫曼樹(shù)void CreatHFMTree(HFMTree *HT,int count)/創(chuàng)建赫夫曼樹(shù)int i

11、;HFMTree p,HT1,HT2; /HT1，HT2 分別存放權(quán)值最小和次小的節(jié)點(diǎn)的位置p=*HT=(HFMTree)malloc(sizeof(HFMNode);p-next=p-LChild=p-RChild=p-Parent=NULL; /初始化赫夫曼鏈表且有 2n-1個(gè)節(jié)點(diǎn)for(i=1;inext=(HFMTree)malloc(sizeof(HFMNode); p=p-next; p-next=p-LChild=p-RChild=p-Parent=NULL; for(i=0,p=*HT;iweight=counti; p=p-next; for(i=n;iParent=HT2-

12、Parent=p; p-LChild=HT1; p-RChild=HT2;p-weight=HT1-weight+HT2-weight;/將兩個(gè)節(jié)點(diǎn)的權(quán)值相加存入一個(gè)節(jié)點(diǎn) p=p-next; /p 指向下一個(gè)沒(méi)有存儲(chǔ)權(quán)值的節(jié)點(diǎn) 2.3.2 赫夫曼編碼(huffmancode)1 根據(jù)最優(yōu)二叉樹(shù)構(gòu)造赫夫曼編碼，利用赫夫曼樹(shù)很容易求出給定字符集及其概率(或頻度)分布的最優(yōu)前綴碼。赫夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。該技術(shù)一般可將數(shù)據(jù)文件壓縮掉 20至 90，其壓縮效率取決于被壓縮文件的特征。（1）用字符 si作為葉子，counti做為葉子 si的權(quán)，構(gòu)造一棵赫夫曼樹(shù)，并將樹(shù)中左分支

13、和右分支分別標(biāo)記為 0 和 1；（2）將從根到葉子的路徑上的標(biāo)號(hào)依次相連，作為該葉子所表示字符的編碼。該編碼即為最優(yōu)前綴碼（也稱赫夫曼編碼） 。代碼如下：void TotalCoding(char s,CodeNode HC,char code)/利用赫夫曼編碼表對(duì)整個(gè)字符串進(jìn)行編碼 int i,j;code0=0; /編碼數(shù)組初始化 for(i=0;si;i+) for(j=0;jn;j+) if(si=HCj.ch) strcpy(code+strlen(code),HCj.code+HCj.start);2 給定字符集的赫夫曼樹(shù)生成后，求赫夫曼編碼的具體實(shí)現(xiàn)過(guò)程是：依次以葉子 si塔里木

14、大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 4 頁(yè) 共 14 頁(yè)(0in-1)為出發(fā)點(diǎn)，向上回溯至根為止。上溯時(shí)走左分支則生成代碼 0，走右分支則生成代碼 1。(1)由于生成的編碼與要求的編碼反序，將生成的代碼先從后往前依次存放在一個(gè)臨時(shí)向量中，并設(shè)一個(gè)指針 start 指示編碼在該向量中的起始位置.(2)當(dāng)某字符編碼完成時(shí)，從臨時(shí)向量的 start 處將編碼復(fù)制到該字符相應(yīng)的位串中即可。(3)因?yàn)樽址笮?n，故變長(zhǎng)編碼的長(zhǎng)度不會(huì)超過(guò) n，加上一個(gè)結(jié)束符0 .2.3.3 建立赫夫曼表void HFMCode(HFMTree HT,CodeNode HC,char str)/從每個(gè)葉子節(jié)點(diǎn)開(kāi)始，利用赫夫曼

15、樹(shù)對(duì)每個(gè)字符進(jìn)行編碼，最終建立一個(gè)赫夫曼表int i;HFMTree q,p=HT;for(i=0;in;i+) /將字符存入赫夫曼編碼結(jié)構(gòu)體數(shù)組的字符單元中 HCi.ch=stri; HCi.coden-1=0; /初始化編碼的最后一位 for(i=0;iParent;q=q-Parent) /判斷 q 所指向的節(jié)點(diǎn)，左孩子置 0，右孩子置 1 if(q=q-Parent-LChild) HCi.code-HCi.start=0; else HCi.code-HCi.start=1; p=p-next; /判斷下一個(gè)葉子節(jié)點(diǎn) 2.3.4 赫夫曼譯碼算法依次讀人文件的二進(jìn)制碼，從赫夫曼樹(shù)的根結(jié)

16、點(diǎn)(即 Tm-1)出發(fā)，若當(dāng)前讀人 0，則走向左孩子，否則走向右孩子。一旦到達(dá)某一葉子 T 時(shí)便譯出相應(yīng)的字符 H.ch。然后重新從根出發(fā)繼續(xù)譯碼，直至文件結(jié)束。代碼如下：void DeCoding(char code,HFMTree HT,char str,char s)/對(duì)赫夫曼編碼進(jìn)行解碼，放入字符串 s 中int i,j,k=0;HFMTree root,p,q;for(root=HT;root-Parent;root=root-Parent); /用 root 指向赫夫曼樹(shù)的根結(jié)點(diǎn)for(i=0,p=root;codei;i+) /從根結(jié)點(diǎn)開(kāi)始按編碼順序訪問(wèn)樹(shù)if(codei=0)

17、p=p-LChild; else p=p-RChild; if(p-LChild=NULL&p-RChild=NULL) /到根節(jié)點(diǎn)時(shí)將該節(jié)點(diǎn)對(duì)應(yīng)的字符輸出 for(j=0,q=HT;q!=p;q=q-next,j+); sk+=strj; p=root; /回溯到根結(jié)點(diǎn) 塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 5 頁(yè) 共 14 頁(yè)sk=0; /解碼完畢，在字符串最后一個(gè)單元存入02.4. 數(shù)據(jù)結(jié)構(gòu)主要定義了兩個(gè)結(jié)構(gòu)體2.4.1 定義赫夫曼樹(shù)節(jié)點(diǎn)結(jié)構(gòu)體typedef struct node int weight;struct node *LChild,*RChild,*Parent; /分別

18、指向該節(jié)點(diǎn)的左孩子，右孩子，和雙親節(jié)點(diǎn)struct node *next; /指向建立的赫夫曼樹(shù)的下一個(gè)節(jié)點(diǎn)HFMNode,*HFMTree;2.4.2 定義赫夫曼編碼的結(jié)構(gòu)體typedef struct char ch; /存儲(chǔ)對(duì)應(yīng)的字符char codeN+1; /存儲(chǔ)對(duì)應(yīng)字符的編碼int start; /存儲(chǔ)編碼的起始位置CodeNode;2.4.3 各個(gè)函數(shù)間的關(guān)系如圖：圖圖 2.12.1 各函數(shù)簡(jiǎn)的調(diào)用關(guān)系各函數(shù)簡(jiǎn)的調(diào)用關(guān)系2.5. 算法的時(shí)空分析時(shí)間復(fù)雜度：構(gòu)造赫夫曼樹(shù):T(n)= O(n) 塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 6 頁(yè) 共 14 頁(yè)建立赫夫曼表：T(n)=O(n2)

19、進(jìn)行譯碼：T(n)= O(n) 赫夫曼編碼 T(n)= O(n) 2.6 測(cè)試數(shù)據(jù)對(duì)下列給出的字符集數(shù)據(jù)建立赫夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼字符串：what did you do that made you so happy字符 空格 A B C D E F G H I J K L M 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 12.7. 測(cè)試情況2.7.1 編碼首先在初始界面，選擇編碼，鍵盤(pán)中輸入 1 如圖 2.2

20、：圖圖 1 1 編譯初始界面編譯初始界面塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 7 頁(yè) 共 14 頁(yè)圖圖 2 2 編碼界面編碼界面2.7.2 通過(guò)編碼出來(lái)的密碼文件解碼最終的到的字符串，通過(guò)與原來(lái)的字符串對(duì)比，完全一樣.說(shuō)明編碼解碼成功?？偪?結(jié)結(jié)通過(guò)該題目的設(shè)計(jì)過(guò)程,對(duì)數(shù)據(jù)結(jié)構(gòu)以及二叉樹(shù)的邏輯結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)的理解,對(duì)樹(shù)的數(shù)據(jù)結(jié)構(gòu)上基本運(yùn)算的實(shí)現(xiàn)有所掌握,對(duì)課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)一步理解和掌握,學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題,鍛煉了自己動(dòng)手的能力。完成所有的工作是非常困難和耗時(shí)的。在以后的學(xué)習(xí)中我會(huì)更加注意自己各個(gè)方面的能力的協(xié)調(diào)發(fā)展。在課程設(shè)計(jì)時(shí)我遇到了很多的問(wèn)題，在老師的幫助，和對(duì)各

21、種資料的查閱中，將問(wèn)題解決，培養(yǎng)了我自主動(dòng)手，獨(dú)立研究的能力，為今后在學(xué)習(xí)工作中能更好的發(fā)展打下了堅(jiān)實(shí)的基礎(chǔ)。參考參考文獻(xiàn)：文獻(xiàn)：1譚浩強(qiáng)編著.C+課程設(shè)計(jì).北京：清華大學(xué)社，20042S.B.Lippman，J.Lajoie 著.潘愛(ài)民譯.C+Primer（3rd Edition）中文版.北京：中國(guó)電力出版社，20023H.M.Deitel，Paul James Deitel 著.薛萬(wàn)鵬譯.C+程序設(shè)計(jì)教程.北京：機(jī)械工業(yè)出版社，20004Stephen R.Savis 著.C+ For Dummies 4th edition，IDG Books Worldwide，Inc.，20025Ha

22、rvey M.Deitel .Jack W.Davidson 著.邱仲潘譯.C+大學(xué)教程（第二版）.北京：電子工業(yè)出版社，20026James P.Cohoon.Jack W.Davidson 著.劉瑞挺等譯.C+程序設(shè)計(jì)（第三版）.北京：電子工業(yè)出版社塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 8 頁(yè) 共 14 頁(yè)7Decoder 編著.C/C+程序設(shè)計(jì).北京：中國(guó)鐵道出版社，20028Brian Overland 著.董梁等譯.C+語(yǔ)言命令譯解（第二版）.北京：機(jī)械工業(yè)出版社，20029 H.M.Deitel，Paul James Deitel 著.薛萬(wàn)鵬譯.C/C+程序設(shè)計(jì)大全.北京：機(jī)械工業(yè)出版

23、社.199710Al Strevens,Clayton Walnum 著.林麗閩等譯.標(biāo)準(zhǔn) C+寶典.北京：電子工業(yè)出版社.2001 11Michael J.Young 著.Mastering Visual C+6.0 Sybex Inc.199912Leen Ammeraal 著.劉瑞挺等譯.C+程序設(shè)計(jì)教程（第三版）.北京：zhongguo 鐵道出版社，200313 呂鳳翥著. C+語(yǔ)言程序設(shè)計(jì).北方交通大學(xué)出版社，200314 袁啟昌著.C+語(yǔ)言程序設(shè)計(jì).清華大學(xué)出版社，200415 劉振安，劉燕君，孫忱 C+語(yǔ)言課程設(shè)計(jì).機(jī)械工業(yè)出版社，200716 楊進(jìn)才，沈顯君，劉蓉編.C+語(yǔ)言程

24、序設(shè)計(jì)教程.清華大學(xué)出版社，200617 宋振會(huì)著. C+語(yǔ)言編程基礎(chǔ)教程.清華大學(xué)出版社，2005塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 9 頁(yè) 共 14 頁(yè)附附 錄錄#include#include#include#include#includetypedef struct /赫夫曼樹(shù)的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select 函數(shù)，選出 HT

25、樹(shù)到 a 為止，權(quán)值最小且 parent 為 0 的 2 個(gè)節(jié)點(diǎn)int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; /選出最小的節(jié)點(diǎn)for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 10 頁(yè) 共 14 頁(yè)for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void h

26、fmcoding(hfmtree &HT,hfmcode &HC,int n) /構(gòu)建赫夫曼樹(shù) HT，并求出 n 個(gè)字符的赫夫曼編碼 HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;+i) /初始化 n 個(gè)葉子結(jié)點(diǎn)printf(請(qǐng)輸入第%d 字符信息和權(quán)值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.

27、weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的結(jié)點(diǎn)HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 11 頁(yè) 共 14 頁(yè)for(i=n+1;i=m;+i) /建立赫夫曼樹(shù)Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.w

28、eight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /給 n 個(gè)字符編碼start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code

29、100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件輸入輸出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;coutn;cout 計(jì)算機(jī)（3）班 Q07620307 XXXn;while(choice!=Q&choice!=q) /當(dāng) choice 的值不為 q 且不為Q 時(shí)循環(huán)cout *赫夫曼編碼/譯碼器*n; cout I.Init E.Encoding D.Decoding Q.Exitn;塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 12 頁(yè) 共 14 頁(yè)

30、coutchoice; if(choice=I|choice=i) /初始化赫夫曼樹(shù)coutn;hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfmTree.txt);if(!output_file)coutcant oen file!endl;return 1;for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();cout赫夫曼樹(shù)已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入 hfmTree.txt 文件中!endl; else if(choice=E|choice=e) /進(jìn)行編碼，并將字符放入ToBeTran.txt，碼值放入 CodeFile.txt 中printf(請(qǐng)輸入字符：);gets(str);output_file.open(ToBeTran.txt);if(!output_file)coutcant oen file!endl;return 1;output_filestrendl;output_file.close();output_file.open(CodeFile.txt);if(!output_f