1、數據結構數據結構課程設計報告課程設計報告 課程名稱課程名稱 ：赫夫曼編碼系統 姓姓 名名 ： 學學 號號 ： 專專 業業 ： 班班 級級 ： 指導教師指導教師 ： 二二一二年一二年 十二月十二月 目錄目錄 contents 1.課程小組課程小組 -2 1.1.小組成員及分工-2 2.設計目的和要求設計目的和要求-2 3.需求分析需求分析 -2 4.設計說明設計說明 -2 4.1.文件編碼（加密） -2 4.2.文件解碼（解密） -3 5.詳細設計詳細設計 -3 5.1.程序主體結構-3 5.2.主要算法說明-3 5.2.1.huffman樹-3 5.2.2.huffman編碼-5 5.2.3.

2、字符權重計算-6 5.2.4.字符解碼-9 6.實驗結果實驗結果-10 6.1.實驗結果說明 -10 6.2.程序運行截圖 -11 7.設計體會設計體會-12 8.參考文獻參考文獻-13 9.附：程序代碼附：程序代碼 -13 1. 課程小組課程小組 1.1.小組成員及分工小組成員及分工 2. 設計目的和要求設計目的和要求 通過課程設計，讓學生進一步熟悉與鞏固數據結構中常用算法，加深體會利用數據結 構的算法解決實際問題的能力,培養學生進行復雜程序設計的技能，提高學生的思維能力、 并促進其綜合應用能力、分析能力和團隊合作能力的提高。 3. 需求分析需求分析 隨著網絡信息科技的不斷高速發展，網絡上的

3、問題也不斷顯露出來，特別是人們特別 關注的安全隱私問題，所以文件的傳輸安全性要特別地亟待解決和提高。 本次的課程設計以赫夫曼編碼為題，設計出赫夫曼文件編碼系統，旨在對文件中的內 容進行分析、統計、處理，進而按照赫夫曼編碼的理論，對文件進行簡單加密。特別是， 不同的文本文件有不同的字符處理形式，所以因此每一個文本都會有一個相應的密鑰，用 于對文本的解碼。 4. 設計說明設計說明 本次編寫的程序按著對文件的編碼（加密）和解碼（解密）的兩大步驟展開。 4.1.文件編碼（加密）文件編碼（加密） 首先選擇文件編碼程序。進入程序后，會要求操作人員選擇將要編碼的文件，并將其 導入到程序中，程序正確導入文件后

4、將會對文件從開始至結束掃描一遍，對文件中的字符 進行統計，在最后計算出每個字符出現的頻率，并將頻率換算成每個字符相應的權重。然 后根據得到的字符權重，構造赫夫曼樹并因此完成赫夫曼編碼（至此，文件的導入分析過 程已完成） 。 然后讓操作人員選擇對文件進行編碼。此時，程序將會繼續打開文件，繼續掃描一遍， 并在掃描的過程中將掃描到得字符根據剛才編好的赫夫曼編碼進行對照，將對應的赫夫曼 編碼寫入另一個文件（即加密的文件） ，所以，如果用戶代開加密的文件即看到里面全是二 進制代碼，并不能分析出里面究竟是什么內容。 （至此，加密的文件應經生成） 。 最后，因為每個文件中的內容不同，所以每個文件的赫夫曼編碼

5、也不同，而赫夫曼編 碼是根據字符的權重生成的，所以每個文件都對應一個字符權重系列（即密鑰） ，如果失去 這個密鑰，即使對文件進行了加密，也不同解密文件的內容，即文件加密失效，所以在生 成加密文件后，一定要導出文件的字符權重（即密鑰） ，以待之后的解碼使用。 （至此，文 件的加密工作應經全部完成） 。 4.2.文件解碼（解密）文件解碼（解密） 文件的解碼程序是一步完成的，即要求操作者首先將之前生成的字符權重（即密鑰） 導入程序，程序根據獲取到得字符權重，調用赫夫曼編碼子程序，進行赫夫曼編碼。然后 程序會提示操作者將加密后的文件導入程序中，程序會根據在程序中獲取到的二進制編碼 與赫夫曼編碼進行對照

6、識別，顯示出對應的字符，因此，文件的解密工作完成。 5. 詳細設計詳細設計 5.1.程序主體結構程序主體結構 程序主體結構分為文件編碼與文件解碼兩個子程序。 文件編碼后分別導出編碼后文件與文件密鑰。 文件解碼需導入編碼文件與文件密鑰，然后顯示文本內容。 5.2.主要算法說明主要算法說明 5.2.1.huffman 樹樹 /huffmantree list: list 為赫夫曼樹. typedef struct char data; /存放字符數據 int weight; /存放字符權重 int parent, lchild, rchild; /分別為根、左子樹、右子樹 huffmantree;

7、 /static info: info 為存放字符權重的數組指針. typedef struct char data; /存放字符數據 int weight; /存放字符權重 static; /int codesize: codesize 為字符種類個數. void creathuffmantree(huffmantree * int lnode, rnode; int value1, value2; huffmantree *ptr; limit = codesize * 2 - 1;/limit 為赫夫曼樹結點個數 if (list = (huffmantree *)malloc(size

8、of(huffmantree) * limit) = null) printf( 內存不足, 操作失敗!n); exit(0); /*初始化赫夫曼樹各結點信息*/ for(i=0, ptr=list; idata = infoi.data; ptr-weight = infoi.weight; ptr-parent = ptr-lchild = ptr-rchild = -1; for(; idata = 0; ptr-weight = 0; ptr-parent = ptr-lchild = ptr-rchild = -1; /*開始建立赫夫曼樹*/ for(i=codesize; ilim

9、it; +i) value1 = value2 = 32767; lnode = rnode = -1; /此部分函數功能為選擇權值最小的兩個結點 for(j=0; ji; +j) if (listj.parent = -1) if (listj.weight value1) value2 = value1; rnode = lnode; value1 = listj.weight; lnode = j; else if (listj.weight value2) value2 = listj.weight; rnode = j; /此部分函數功能為選擇出的結點建立關系 listlnode.p

10、arent = i; listrnode.parent = i; listi.weight = listlnode.weight + listrnode.weight; listi.lchild = lnode; listi.rchild = rnode; 5.2.2.huffman 編碼編碼 void creathuffmancode(huffmantree *list, huffmancode int flag1, flag2; char *tempcode; if (code = (char *)malloc(sizeof(char *) * codesize) = null) prin

11、tf( 內存不足, 操作失敗!n); exit(0); if (tempcode = (char *)malloc(sizeof(char) * codesize) = null) printf( 內存不足, 操作失敗!n); exit(0); tempcodecodesize-1 = 0; /*從葉子結點到根結點逆向求編碼*/ for(i=0; idata = ch; ptr-number = 1; ptr-next = characterlist.next; characterlist.next = ptr; +typenumber; else while (current != null

12、) current = current-next; if (current != null) +(current-number); +characternumber; else if (ptr = (data *)malloc(sizeof(data) = null) printf( 內存不足, 操作失敗!n); exit(0); ptr-data = ch; ptr-number = 1; ptr-next = current; previous-next = ptr; +typenumber; +characternumber; fclose(fp); codesize = typenum

13、ber; info = (static *)malloc(sizeof(static) * codesize); current = characterlist.next; /將統計好的字符權重信息存入權重文件中 for (int i=0; idata; infoi.weight = (int)(current-number * 100.0 / characternumber); current = current-next; 5.2.4.字符解碼字符解碼 /此代碼用于比較查找赫夫曼編碼 bool comparedata(char *tempcode, int position codesiz

14、e; +position) if (strcmp(tempcode, codeposition) = 0) return true; return false; void displaycontext() inportcharacterweight(); creathuffmantree(list, info, codesize); creathuffmancode(list, code, codesize); inportfilecoding(); file *fp; int position; int end; char *tempcode; char ch; fp = fopen(fil

15、ename, rb); if (tempcode = (char *)malloc(sizeof(char) * codesize) = null) printf( 內存不足, 操作失敗!n); exit(0); end = 0; /*此部分為解碼過程*/ printf(n 文件內容為:nn ); while (ch = fgetc(fp) != eof) tempcodeend = ch; +end; tempcodeend = 0; if (comparedata(tempcode, position) printf(%c, infoposition.data); end = 0; pri

16、ntf(nn 按任意鍵結束!); getch(); 6. 實驗結果實驗結果 6.1.實驗結果說明實驗結果說明 經過多次對本程序的實驗，此次編譯完成的程序可以對簡單的文本文件進行加密和解 密，因為限于對文件的基本操作不是太完全清楚，只是匆匆查閱了一些關于 c 語言文件操 作部分的資料，所以這也是文件操作方面的一個瑕疵。所以綜上，次此的程序只能進行簡 單的加密與解密操作。 6.2.程序運行截圖程序運行截圖 （圖 1：赫夫曼加密程序主體窗口） （圖 2：赫夫曼文件編碼程序窗口） （圖 3：用于測試的文本 原始文本內內容） （圖 4：導出文件編碼后，在創建的編碼文件中生成的二進制數） （圖 5：導出的

17、文本密鑰（即字符權重） ） （圖 6：赫夫曼文件譯碼程序窗口） （圖 7：將之前生成的編碼文件與密鑰導入進來后顯示出原來的文本內容） 7. 設計體會設計體會 進過此次的實驗，讓我對樹結構及最優二叉樹概念與操作的理解。 在此次選擇赫夫曼編碼操作的時候，本打算用赫夫曼編碼的程序對文件進行壓縮存儲， 可是限于不知道怎樣將生成的赫夫曼編碼進行 bit 級別的存儲（只知道進行 byte 級別的存 儲） ，所以壓縮存儲的想法失敗了，之后根據赫夫曼編碼的結構及生成的文件，不得不讓我 想到了文件的加密與解密，于是按著這個思路來設計了本文件加密解密系統。在設計的時 候，曾準備根據網上之前對 26 個英文字符的使

18、用統計來事先對字符權重進行分配（這樣加 密的文件可解密性增加了） ，而且考慮到文件中不僅有 26 個英文字母，如果對各種字符的 使用頻率進行統計，這個事先工作的負擔會很重，所以之后編寫了自動統計文本字符的頻 率程序，這樣工作量會減小很多（而且文件的可解密性大大減小，但是也帶來了記錄密鑰 的不方便） 。 總體感覺程序還行，就是代碼的簡潔性還是有點差，條理還是不那么清晰。 8. 參考文獻參考文獻 1嚴蔚敏、吳偉明.數據結構.清華大學出版社.1997.4 2thomas h.cormen、charles e.leiserson .算法導論.機械工業出版社.2006.9 9. 附：程序代碼附：程序代碼

19、 #include #include #include #include /赫夫曼樹結構 typedef struct char data; int weight; int parent, lchild, rchild; huffmantree; /字符權重結構 typedef struct char data; int weight; static; /統計字符時所用到的鏈表結構 typedef struct node char data; int number; struct node *next; data; /赫夫曼代碼結構 typedef char* huffmancode; /創建

20、赫夫曼樹 void creathuffmantree(huffmantree * /創建赫夫曼代碼 void creathuffmancode(huffmantree *list, huffmancode /從文件中讀取數據并計算各字符出現頻率 void datacount(static * /文件編碼程序 void fileencoding(); /創建文件編碼 void creatfilecoding(); /導出編碼后文件 void exportfileencoding(huffmantree *list, huffmancode code, int codesize); /導出文件中字

21、符權重 void exportcharacterweight(); /文件譯碼程序 void filedecoding(); /導入編碼后的文件 void inportfilecoding(); /導入文件中字符權重 void inportcharacterweight(); /顯示譯碼后的文件內容 void displaycontext(); bool comparedata(char *tempcode, int void bound(char character, int size); /赫夫曼樹 huffmantree *list; /赫夫曼代碼 huffmancode code; /

22、字符權重信息 static *info; /字符種數 int codesize; /文件名 char filename30; int main() char choice; while (true) system(cls); printf( 赫夫曼編碼加密程序n); bound(-, 25); printf( 1. 文 件 編 碼 n); printf( 2. 文 件 譯 碼 n); printf( 0. 退 出 程 序 n); bound(-, 25); printf( 請選擇: ); fflush(stdin); choice = getchar(); switch (choice) ca

23、se 1: fileencoding(); break; case 2: filedecoding(); break; case 0: printf(n); system(pause); return 0; break; default: printf(n 您的輸入有誤, 按任意鍵后請從新輸入!); getch(); break; void creathuffmantree(huffmantree * int lnode, rnode; int value1, value2; huffmantree *ptr; limit = codesize * 2 - 1; if (list = (huf

24、fmantree *)malloc(sizeof(huffmantree) * limit) = null) printf( 內存不足, 操作失敗!n); exit(0); for(i=0, ptr=list; idata = infoi.data; ptr-weight = infoi.weight; ptr-parent = ptr-lchild = ptr-rchild = -1; for(; idata = 0; ptr-weight = 0; ptr-parent = ptr-lchild = ptr-rchild = -1; for(i=codesize; ilimit; +i)

25、value1 = value2 = 32767; lnode = rnode = -1; for(j=0; ji; +j) if (listj.parent = -1) if (listj.weight value1) value2 = value1; rnode = lnode; value1 = listj.weight; lnode = j; else if (listj.weight value2) value2 = listj.weight; rnode = j; listlnode.parent = i; listrnode.parent = i; listi.weight = l

26、istlnode.weight + listrnode.weight; listi.lchild = lnode; listi.rchild = rnode; void creathuffmancode(huffmantree *list, huffmancode int flag1, flag2; char *tempcode; if (code = (char *)malloc(sizeof(char *) * codesize) = null) printf( 內存不足, 操作失敗!n); exit(0); if (tempcode = (char *)malloc(sizeof(cha

27、r) * codesize) = null) printf( 內存不足, 操作失敗!n); exit(0); tempcodecodesize-1 = 0; for(i=0; idata = ch; ptr-number = 1; ptr-next = characterlist.next; characterlist.next = ptr; +typenumber; else while (current != null) current = current-next; if (current != null) +(current-number); +characternumber; els

28、e if (ptr = (data *)malloc(sizeof(data) = null) printf( 內存不足, 操作失敗!n); exit(0); ptr-data = ch; ptr-number = 1; ptr-next = current; previous-next = ptr; +typenumber; +characternumber; fclose(fp); codesize = typenumber; info = (static *)malloc(sizeof(static) * codesize); current = characterlist.next;

29、for (int i=0; idata; infoi.weight = (int)(current-number * 100.0 / characternumber); current = current-next; void fileencoding() char choice; while (true) system(cls); printf( 文件編碼程序n); bound(-, 25); printf( 1. 創 建 文 件 編 碼 n); printf( 2. 導 出 文 件 編 碼 n); printf( 3. 導 出 文 件 密 鑰 n); printf( 0. 返 回 主 菜

30、單 n); bound(-, 25); printf( 請選擇: ); fflush(stdin); choice = getchar(); switch (choice) case 1: creatfilecoding(); break; case 2: exportfileencoding(list, code, codesize); break; case 3: exportcharacterweight(); break; case 0: return; default: printf(n 您的輸入有誤, 按任意鍵后請從新輸入!); getch(); break; void creat

31、filecoding() datacount(info); creathuffmantree(list, info, codesize); creathuffmancode(list, code, codesize); printf(n 創建文件編碼成功! 按任意鍵繼續!); getch(); void exportfileencoding(huffmantree *list, huffmancode code, int codesize) int i; char ch; char outfilename30; file *infile, *outfile; system(cls); infi

32、le = fopen(filename, rb); printf(n 請創建導出文件名: ); fflush(stdin); gets(outfilename); if (outfile = fopen(outfilename, wb) = null) printf( 輸出文件創建失敗!n); exit(0); while (ch = fgetc(infile) != eof) for(i=0; icodesize; +i) if (listi.data = ch) fputs(codei, outfile); break; fcloseall(); printf(n 導出文件成功! 按任意鍵繼續!); getch(); void exportcharacterweight() char outfilename30; file *fp; system(cls); printf(n 請創建導出文件名: ); fflush(stdin); gets(outfilename); if (fp = fopen(outfilename, wb) = null) printf( 輸出文件創建失敗!n); exit(0); for(int i=0; idata = data; ptr-number = weight; ptr-next =