哈夫曼編碼譯碼器課程設計

1、課 程 設 計 說 明 書課程名稱： 數(shù)據(jù)結構與算法 設計題目： 哈夫曼編譯碼器 院 系： 計算機科學與信息工程學院 學生姓名： 劉文杰 學 號：專業(yè)班級： 軟件工程16-2 指導教師： 孫高飛 2017年 12 月 11日設計題目哈夫曼編譯碼器限定人數(shù)3問題描述采用哈夫曼編碼思想實現(xiàn)對字符串的編碼，以及對編碼的解碼。字符串的長度不小于5000字節(jié)。讀取要編碼的文本文件，將文件的內(nèi)容進行編碼，生成新的文件。對編碼文件進行解碼，獲得文本文件。將譯碼的文本文件和原文件進行比較，恢復文件和原文件必須完全一致。設字符集及頻度如下表：字符空格ABCDEFGHIJKLM頻度1866413223210321

2、154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161基本要求與說明1、根據(jù)哈夫曼樹編碼原理，構造哈夫曼樹，創(chuàng)建一套哈夫曼編碼2、讀取文本文件，并對文件內(nèi)容編碼，生成編碼文件3、對編碼文件進行譯碼，獲得恢復文件4、比較恢復文件和原文件是否相同。課 程 設 計 任 務 書設計題目 哈夫曼編譯碼器學生姓名劉文杰所在院系計算機科學與信息工程學院專業(yè)、年級、班軟件工程16-2設計要求：1.根據(jù)哈夫曼樹編碼原理，構造哈夫曼樹，創(chuàng)建一套哈夫曼編碼。2.讀取文本文件，并對文件內(nèi)容編碼，生成編碼文件。3.對編碼文件進行譯碼，獲得恢復文件。4.比較恢復文件和原文件

3、是否相同。學生應完成的工作：1. 學生應認真學習參考程序，理解每個文件、每個函數(shù)以及各個變量的作用和意義。在此基礎上進一步改進程序，最后正確地運行程序。2. 對程序進行測試，設計詳細的測試計劃，然后根據(jù)測試計劃設計測試用例，對程序進行測試。測試時應注意對各種邊緣情況進行測試。3. 完成課程設計報告。參考文獻閱讀：1. 嚴蔚敏數(shù)據(jù)結構（C語言版）清華大學出版社，20112. 譚浩強C程序設計（第四版）清華大學出版，20103.蔣立翔C+程序設計技能百練 M中國鐵道出版社，2004工作計劃：1. 小組審題，查閱資料，進行設計前的必要資料準備（3天）。 2. 把程序完整運行出來（4天）。 3. 增加

4、改進程序（3天）。 4. 寫課程設計報告（3天）。 5. 提交課程設計報告及答辯（1天）任務下達日期：2017年 12月 01日 任務完成日期：2017年 12月 19 日指導教師（簽名）： 學生（簽名）： 哈夫曼編譯碼器摘 要：采用哈夫曼編碼思想實現(xiàn)對字符串的編碼，以及對編碼的解碼。字符串的長度不小于5000字節(jié)。讀取要編碼的文本文件，將文件的內(nèi)容進行編碼，生成新的文件。對編碼文件進行解碼，獲得文本文件。將譯碼的文本文件和原文件進行比較，恢復文件和原文件必須完全一致。關鍵詞：構建哈夫曼樹 哈弗曼編碼 哈夫曼譯碼 字符串編碼 打印編碼函數(shù)目 錄1.設計背景11.1哈夫曼樹的介紹11.2設計的作

5、用、目的11.3設計任務及要求22.設計方案22.1實驗內(nèi)容22.2操作思路22.3基本操作33. 方案實施43.1 C語言編程43.2程序介紹123.3程序流程圖以及說明13圖3 主程序流程圖134. 結果與結論144.1程序運行結果144.2總結165. 收獲與致謝176. 參考文獻171.設計背景1.1哈夫曼樹的介紹 Huffman Tree，中文名是哈夫曼樹或霍夫曼樹或者赫夫曼樹，它是最優(yōu)二叉樹。定義：給定n個權值作為n個葉子結點，構造一棵二叉樹，若樹的帶權路徑長度達到最小，則這棵樹被稱為哈夫曼樹。 (01) 路徑和路徑長度定義：在一棵樹中，從一個結點往下可以達到的孩子或?qū)O子結點之間的

6、通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結點的層數(shù)為1，則從根結點到第L層結點的路徑長度為L-1。 (02) 結點的權及帶權路徑長度定義：若將樹中結點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。 (03) 樹的帶權路徑長度定義：樹的帶權路徑長度規(guī)定為所有葉子結點的帶權路徑長度之和，記為WPL。1.2設計的作用、目的 通過完成具體編碼算法的程序設計和調(diào)試工作，提高編程能力，深刻理解信源編碼、信道編譯碼的基本思想和目的，掌握編碼的基本原理與編碼過程，增強邏輯思維能力，培養(yǎng)和提高自學能力以及綜合運用所學理

7、論知識去分析解決實際問題的能力，逐步熟悉開展科學實踐的程序和方法。主要目的是加深對理論知識的理解，掌握查閱有關資料的技能，提高實踐技能，培養(yǎng)獨立分析問題、解決問題及實際應用的能力。 通過課程設計各環(huán)節(jié)的實踐，應達到如下要求： 1理解無失真信源編碼的理論基礎，掌握無失真信源編碼的基本方法； 2根據(jù)哈夫曼編碼算法，考慮一個有多種可能符號（各種符號發(fā)生的概率不同）的信源，得到哈夫曼編碼和碼樹； 3掌握哈夫曼編碼的優(yōu)缺點； 4通過完成具體編碼算法的程序設計和調(diào)試工作，提高編程能力，深刻理解信源編碼、信道編譯碼的基本思想和目的，掌握編碼的基本原理與編碼過程，增強邏輯思維能力，培養(yǎng)和提高自學能力以及綜合運

8、用所學理論知識去分析解決實際問題的能力，逐步熟悉開展科學實踐的程序和方法。1.3設計任務及要求1. 理解無失真信源編碼的理論基礎，掌握無失真信源編碼的基本方法；2. 掌握哈夫曼編碼/費諾編碼方法的基本步驟及優(yōu)缺點；3. 深刻理解信道編碼的基本思想與目的，理解線性分組碼的基本原理與編碼過程；2.設計方案2.1實驗內(nèi)容假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、wn，哈夫曼樹的構造規(guī)則為：1.將w1、w2、，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)； 2. 在森林中選出根結點的權值最小的兩棵樹進行合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左

9、、右子樹根結點權值之和； 3. 從森林中刪除選取的兩棵樹，并將新樹加入森林； 4. 重復(02)、(03)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。2.2操作思路以5,6,7,8,15為例，來構造一棵哈夫曼樹。第1步：創(chuàng)建森林，森林包括5棵樹，這5棵樹的權值分別是5,6,7,8,15。 第2步：在森林中，選擇根節(jié)點權值最小的兩棵樹(5和6)來進行合并，將它們作為一顆新樹的左右孩子(誰左誰右無關緊要，這里，我們選擇較小的作為左孩子)，并且新樹的權值是左右孩子的權值之和。即，新樹的權值是11。 然后，將"樹5"和"樹6"從森林中刪除，并將新的樹

10、(樹11)添加到森林中。 第3步：在森林中，選擇根節(jié)點權值最小的兩棵樹(7和8)來進行合并。得到的新樹的權值是15。 然后，將"樹7"和"樹8"從森林中刪除，并將新的樹(樹15)添加到森林中。 第4步：在森林中，選擇根節(jié)點權值最小的兩棵樹(11和15)來進行合并。得到的新樹的權值是26。 然后，將"樹11"和"樹15"從森林中刪除，并將新的樹(樹26)添加到森林中。 第5步：在森林中，選擇根節(jié)點權值最小的兩棵樹(15和26)來進行合并。得到的新樹的權值是41。 然后，將"樹15"和"樹

11、26"從森林中刪除，并將新的樹(樹41)添加到森林中。 此時，森林中只有一棵樹(樹41)。這棵樹就是我們需要的哈夫曼樹！3. 方案實施3.1 C語言編程 #include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX 99999#define N 27/定義最多節(jié)點個數(shù)#define M 2*N - 1/中間節(jié)點個數(shù)typedef struct int weight;int parent;int LChild;int RChild;HTNode,HuffmanTreeM+1;/

12、因為零號單元不使用typedef char * HuffmanCodeN+1;HuffmanCode co;/創(chuàng)建全局變量用于儲存HuffmanCodechar CHN;int weightN = 64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1;HuffmanTree ht;char word30;/全局變量用于儲存鍵入的內(nèi)容void Init_CH()int i;CH26 = ' 'CH0 = 'A'for(i=1;i<26;i+)CHi = 'A&

13、#39;+i;for(i=0;i<27;i+)printf("%c ",CHi);void select(int *sr,int *sl,int n)int i,point;point = MAX;for(i=0;i<n;i+)if(hti+1.weight<point && hti+1.parent=0)*sr = i+1;/*sr是最小的point = ht*sr.weight;ht*sr.parent = 1;point = MAX;for(i=0;i<n;i+)if(hti+1.weight<point &&am

14、p; hti+1.parent=0)*sl = i+1;/*sl是第二小point = ht*sl.weight;ht*sl.parent = 1;void InitHuffmanCode()int i,sr,sl;for(i=1;i<=N;i+)hti.weight = weighti-1;hti.parent = 0;hti.LChild = 0;hti.RChild = 0;for(i=N+1;i<=M;i+)hti.weight = 0;hti.parent = 0;hti.LChild = 0;hti.RChild = 0;printf("-初始化完成-n&qu

15、ot;);for(i=N+1;i<=M;i+)select(&sr,&sl,i-1);hti.weight = htsr.weight + htsl.weight;htsr.parent = i;htsl.parent = i;hti.LChild = sr;hti.RChild = sl;for(i=1;i<=M;i+)printf("%d %dn",hti.parent,i);void CreateHuffmanCode()FILE * trans;int i,start,p,c;char *cd;cd = (char *)malloc(N*

16、sizeof(char);cdN-1 = '0'for(i=1;i<=N;i+)start = N-1;c = i;p = hti.parent;while(p)-start;if(htp.LChild = c)cdstart = '0'elsecdstart = '1'c = p;p = htp.parent;coi = (char*)malloc(N-start)*sizeof(char);strcpy(coi,&cdstart);printf("%s %dn",coi,i);if(trans=fopen(&

17、quot;C:trans.txt","w")=NULL)printf("cannot open trans.txt!");exit(0);fputs("-哈夫曼編碼表初始化如下-n",trans);for(i=0;i<N;i+)fputc(CHi,trans);fputs(" :",trans);fputs(coi+1,trans);fputs("n",trans);fclose(trans);void InputHuffmanWord()FILE *fp;if(fp = fop

18、en("C:storeWord.txt","w") = NULL)printf("cannot open storeWord.txt!");exit(0);printf("請輸入以'#'結束的大寫字母字符串:n");while(strcmp(word,"#")!=0)fputs(word,fp);gets(word);fclose(fp);/選擇原碼輸入類型void SelectInputType()system("cls");int point;while(

19、1)printf(" '0':從鍵盤鍵入編碼內(nèi)容n");printf(" '1':從文件中讀取編碼內(nèi)容n");printf(" '2':退出n");scanf("%d",&point);system("cls");switch(point)case 0:InputHuffmanWord();break;case 1:printf("將編碼內(nèi)容保存在storeWord.txt文件即可。n");printf("請進

20、行下一步操作！n");break;case 2:printf("已經(jīng)退出輸入編碼內(nèi)容。n");return ;default:printf("Input error!n");break;/編碼void Huffman_Encod()int p = M,i,flag;FILE *Input,*Output;char ch;if(Output = fopen("C:storeWord.txt","r") = NULL)printf("cannot open store.txt!");exi

21、t(0);if(Input = fopen("C:storeCode.txt","w") = NULL)printf("cannot open storeCode.txt!");exit(0);while(!feof(Output)/遇到輸入文件的結束標識flag = 0;ch = fgetc(Output);/putchar(ch);for(i=0;i<N;i+)if(CHi = ch)fputs(coi+1,Input);flag = 1;if(flag = 0)fputc('*',Input);fclose

22、(Output);fclose(Input);/譯碼void Huffman_Decod()FILE *fp,*Input;int p = M,i=0;char ch;if(fp = fopen("C:storeCode.txt","r") = NULL)printf("cannot open storeCode.txt!");exit(0);if(Input = fopen("C:storeWord_1.txt","w") = NULL)printf("cannot open sto

23、reWord_1.txt!");exit(0);ch = fgetc(fp);while(!feof(fp)if(ch = '0')p = htp.LChild;else if(ch = '1')p = htp.RChild;else if(ch = '*')fputs("*",Input);putchar(ch);elseprintf("Input error!");if(htp.LChild = 0 && htp.RChild = 0)fputc(CHp-1,Input);pu

24、tchar(CHp-1);p = M;ch = fgetc(fp);fclose(fp);fclose(Input);printf("n");/譯碼與原碼比較void Compare_word()char ch_1,ch_2;int flag = 1;FILE *origin,*decod;if(origin = fopen("C:storeWord.txt","r") = NULL)printf("cannot open storeCode.txt!");exit(0);if(decod = fopen(&quo

25、t;C:storeWord_1.txt","r") = NULL)printf("cannot open storeWord_1.txt!");exit(0);while(!feof(decod)ch_1 = getc(decod);ch_2 = getc(origin);if(ch_1 != '*')if(ch_1 != ch_2)flag = 0;fclose(decod);fclose(origin);if(flag = 0)printf("原碼與譯碼不相符！n");elseprintf("原

26、碼與譯碼相符！n");void main()int point;Init_CH();InitHuffmanCode();CreateHuffmanCode();while(1)printf("* 哈夫曼編譯器 *n");printf("n '0':初始化哈夫曼表n");printf(" '1':輸入編碼內(nèi)容n");printf(" '2':開始編碼n");printf(" '3':開始譯碼n");printf("

27、 '4':與譯碼與原碼比較n");printf(" '5':退出哈夫曼編譯器n");scanf("%d",&point);system("cls");switch(point)case 0:printf("哈夫曼表初始化完成！n請進行下一步操作！n");break;case 1:SelectInputType();break;case 2:Huffman_Encod();printf("編碼結束！請進行下一步操作！n");break;case 3

28、:Huffman_Decod();printf("譯碼結束！已將譯碼內(nèi)容存放storeWord_1.txt!n");printf("請進行下一步操作！n");break;case 4:Compare_word();break;case 5:printf("已經(jīng)退出編譯器。n");return ;default:printf("Input error!n");break; 3.2程序介紹本程序的編碼和運行都是在Visual C+ 6.0中實現(xiàn)的，在Visual Stdio中也能實現(xiàn)， 整個程序雖然看似龐大，但編寫過程

29、清晰，采用模塊化編寫，各個問題逐個擊破，也方便對程序的管理和運行。整個程序的編寫分為五大部分,五大部分緊密相連，環(huán)環(huán)相扣，共同實現(xiàn)程序的編碼。 在上述存儲結構上實現(xiàn)的哈夫曼算法可大致描述為(設T的類型為HuffmanTree)：(1)初始化將T0m-1中2n-1個結點里的三個指針均置為空(即置為-1)，權值置為0。(2)輸入 讀入n個葉子的權值存于向量的前n個分量(即T0n-1)中。它們是初始森林中n個孤立的根結點上的權值。(3)合并 對森林中的樹共進行n-1次合并，所產(chǎn)生的新結點依次放人向量T的第i個分量中(nim-1)。每次合并分兩步： 在當前森林T0i-1的所有結點中，選取權最小和次小的

30、兩個根結點p1和Tp2作為合并對象，這里0p1，p2i-1。 將根為Tp1和Tp2的兩棵樹作為左右子樹合并為一棵新的樹，新樹的根是新結點Ti。具體操作：將Tp1和Tp2的parent置為i，將Ti的lchild和rchild分別置為p1和p2新結點Ti的權值置為Tp1和Tp2的權值之和。注意： 合并后Tpl和Tp2在當前森林中已不再是根，因為它們的雙親指針均已指向了Ti，所以下一次合并時不會被選中為合并對象。3.3程序流程圖以及說明說明圖3 主程序流程圖4. 結果與結論4.1程序運行結果為了最大化優(yōu)化程序，盡可能美觀，設計了五個輸入選擇步驟，可多次進行選擇輸入輸出操作，輸入時可從鍵盤鍵入或者從

31、文件指定路徑獲取。printf("* 哈夫曼編譯器 *n");printf("n '0':初始化哈夫曼表n");printf(" '1':輸入編碼內(nèi)容n");printf(" '2':開始編碼n");printf(" '3':開始譯碼n");printf(" '4':與譯碼與原碼比較n");printf(" '5':退出哈夫曼編譯器n");printf(&quo

32、t;請輸入以'#'結束的大寫字母字符串:n");while(strcmp(word,"#")!=0)fputs(word,fp);gets(word);fclose(fp);根據(jù)編寫的程序，通過while循環(huán)，在輸入#時程序輸入結束，即可進行譯碼，并將譯碼內(nèi)容，通過程序存放在C盤中。譯碼內(nèi)容存放在指定位置，找到打開即可見。最后可審核源碼譯碼是否相符，退出哈夫曼編譯器。4.2總結本次課程設計，讓我對哈夫曼編碼以及C語言有了更深的理解和操作能力。開始針對題目進行分析，將所涉及的知識點，及相關函數(shù)做了分析，大體能夠把握整體的設計流程及思路。再通過查閱相關

33、資料，使自己的知識也更加豐富了，明白了哈夫曼編碼的原理以及仿真的實現(xiàn)。首先對給題目進行了計算，進行哈夫曼編碼，求出平均碼長，編碼效率，開始時不是很順利，以前學的很多書本上的東西記得不太清楚了，經(jīng)過復習課本的內(nèi)容，掌握原理后順利求出結果。然后是利用C語言編寫程序，由于我現(xiàn)在正在公司實習，接觸到編程的東西比較多，所以對C語言編程還是比較熟悉的，所以我選擇使用C語言來實現(xiàn)仿真，仔細研究后得到程序的算法，還有我也參考了一部分網(wǎng)上的算法，但是在運行時還是出錯了，之后又經(jīng)過幾次的修改，終于得出了結果，可是和自己計算的碼卻是相反的，而其它結果卻是相同，讓我疑惑了，我又仔細想了想了，原因應該出現(xiàn)在編碼的時候，在編碼過程中如果0和1賦值相反的話，就會出現(xiàn)這種情況，但是兩種的碼字應該都是正確的。過而能改，善莫大焉。在課程設計過程中，我們不斷發(fā)現(xiàn)錯誤，不斷改正，不斷領悟，不斷獲取最終的檢測調(diào)試環(huán)節(jié)，本身就是在踐行過而能改，善莫大焉的知行觀。這次課程設計終于