【正文】 《 數(shù)據(jù)結(jié)構(gòu) 》 課程設(shè)計(jì)報(bào)告 課程名稱 ： 赫夫曼編碼系統(tǒng) 姓 名 ： 學(xué) 號(hào) ： 專 業(yè) ： 班 級(jí) ： 指導(dǎo)教師 ： 二〇一二年 十二月 1 / 29 目錄 Contents 1. 課程小組 2 . 小組成員及分工 2 2. 設(shè)計(jì)目的和要求 2 3. 需求分析 2 4. 設(shè)計(jì)說明 2 . 文件編碼（加密） 2 . 文件解碼（解密） 3 5. 詳細(xì)設(shè)計(jì) 3 . 程序主體結(jié)構(gòu) 3 . 主要算法說明 3 . Huffman 樹 3 . Huffman 編碼 5 . 字符權(quán)重計(jì)算 6 . 字符解碼 9 6. 實(shí)驗(yàn)結(jié)果 10 . 實(shí)驗(yàn)結(jié)果說明 10 . 程序運(yùn)行截圖 11 7. 設(shè)計(jì)體會(huì) 12 8. 參考文獻(xiàn) 13 9. 附：程序代碼 13 2 / 29 1. 課程小組 . 小組 成員及分工 … 2. 設(shè)計(jì)目的和要求 通過課程設(shè)計(jì)，讓學(xué)生進(jìn)一步熟悉與鞏固數(shù)據(jù)結(jié)構(gòu)中常用算法，加深體會(huì)利用數(shù)據(jù)結(jié)構(gòu)的算法解決實(shí)際問題的能力 ,培養(yǎng)學(xué)生進(jìn)行復(fù)雜程序設(shè)計(jì)的技能，提高學(xué)生的思維能力、并促進(jìn)其綜合應(yīng)用能力、分析能力和團(tuán)隊(duì)合作能力的提高。 3. 需求分析 隨著網(wǎng)絡(luò)信息科技的不斷高速發(fā)展，網(wǎng)絡(luò)上的問題也不斷顯露出來，特別是人們特別關(guān)注的安全隱私問題，所以文件的傳輸安全性要特別地亟待解決和提高。 本次的課程設(shè)計(jì)以赫夫曼編碼為題，設(shè)計(jì)出赫夫曼文件編碼系統(tǒng)，旨在對(duì)文件中的內(nèi)容進(jìn)行分析、統(tǒng)計(jì)、處理，進(jìn)而按照赫夫曼編碼的理論 ，對(duì)文件進(jìn)行簡(jiǎn)單加密。特別是，不同的文本文件有不同的字符處理形式，所以因此每一個(gè)文本都會(huì)有一個(gè)相應(yīng)的密鑰，用于對(duì)文本的解碼。 4. 設(shè)計(jì)說明 本次編寫的程序按著對(duì)文件的編碼（加密）和解碼（解密）的兩大步驟展開。 . 文件編碼（加密） 首先選擇文件編碼程序。進(jìn)入程序后，會(huì)要求操作人員選擇將要編碼的文件，并將其導(dǎo)入到程序中，程序正確導(dǎo)入文件后將會(huì)對(duì)文件從開始至結(jié)束掃描一遍，對(duì)文件中的字符進(jìn)行統(tǒng)計(jì)，在最后計(jì)算出每個(gè)字符出現(xiàn)的頻率，并將頻率換算成每個(gè)字符相應(yīng)的權(quán)重。然后根據(jù)得到的字符權(quán)重，構(gòu)造赫夫曼樹并因此完成赫夫曼編碼（至 此，文件的導(dǎo)入分析過程已完成）。 然后讓操作人員選擇對(duì)文件進(jìn)行編碼。此時(shí)，程序?qū)?huì)繼續(xù)打開文件，繼續(xù)掃描一遍，并在掃描的過程中將掃描到得字符根據(jù)剛才編好的赫夫曼編碼進(jìn)行對(duì)照，將對(duì)應(yīng)的赫夫曼編碼寫入另一個(gè)文件（即加密的文件），所以，如果用戶代開加密的文件即看到里面全是二進(jìn)制代碼，并不能分析出里面究竟是什么內(nèi)容。（至此，加密的文件應(yīng)經(jīng)生成）。 最后，因?yàn)槊總€(gè)文件中的內(nèi)容不同，所以每個(gè)文件的赫夫曼編碼也不同，而赫夫曼編碼是根據(jù)字符的權(quán)重生成的，所以每個(gè)文件都對(duì)應(yīng)一個(gè)字符權(quán)重系列（即密鑰），如果失去這 3 / 29 個(gè)密鑰，即使對(duì) 文件進(jìn)行了加密，也不同解密文件的內(nèi)容，即文件加密失效，所以在生成加密文件后，一定要導(dǎo)出文件的字符權(quán)重（即密鑰），以待之后的解碼使用。（至此，文件的加密工作應(yīng)經(jīng)全部完成）。 . 文件解碼（解密） 文件的解碼程序是一步完成的，即要求操作者首先將之前生成的字符權(quán)重（即密鑰）導(dǎo)入程序， 程序根據(jù)獲取到得字符權(quán)重，調(diào)用赫夫曼編碼子程序，進(jìn)行赫夫曼編碼 。然后程序會(huì)提示操作者將加密后的文件導(dǎo)入程序中，程序會(huì)根據(jù)在程序中獲取到的二進(jìn)制編碼與赫夫曼編碼進(jìn)行對(duì)照識(shí)別，顯示出對(duì)應(yīng)的字符，因此，文件的解密工作完成。 5. 詳細(xì)設(shè)計(jì) . 程序主體結(jié) 構(gòu) 程序主體結(jié)構(gòu)分為文件編碼與文件解碼兩個(gè)子程序。 文件編碼后分別導(dǎo)出編碼后文件與 文件密鑰 。 文件解碼需導(dǎo)入編碼文件與 文件密鑰 ，然后顯示文本內(nèi)容。 . 主要算法說明 . Huffman 樹 //HuffmanTree list: list 為赫夫曼樹 . typedef struct { char data。 //存放字符數(shù)據(jù) int weight。 //存放字符權(quán)重 int parent, lchild, rchild。 //分別為根、左子樹、右子樹 }HuffmanTree。 //Static info: info 為存放字符權(quán)重的數(shù)組指針 . typedef struct { char data。 //存放字符數(shù)據(jù) int weight。 //存放字符權(quán)重 }Static。 //int codeSize: codeSize 為字符種類個(gè)數(shù) . void CreatHuffmanTree(HuffmanTree *amp。list, Static *info, int codeSize) 4 / 29 { int i, j, limit。 int lnode, rnode。 int value1, value2。 HuffmanTree *ptr。 limit = codeSize * 2 1。 //limit 為赫夫曼樹結(jié)點(diǎn)個(gè)數(shù) if ((list = (HuffmanTree *)malloc(sizeof(HuffmanTree) * limit)) == NULL) { printf( 內(nèi)存不足 , 操作失敗 !\n)。 exit(0)。 } /*******************初始化赫夫曼樹各結(jié)點(diǎn)信息 **************************/ for(i=0, ptr=list。 icodeSize。 ++i, ++ptr) { ptrdata = info[i].data。 ptrweight = info[i].weight。 ptrparent = ptrlchild = ptrrchild = 1。 } for(。 ilimit。 ++i, ++ptr) { ptrdata = 39。039。 ptrweight = 0。 ptrparent = ptrlchild = ptrrchild = 1。 } /***********************開始建立赫夫曼樹 ******************************/ for(i=codeSize。 ilimit。 ++i) { value1 = value2 = 32767。 lnode = rnode = 1。 //此部分函數(shù)功能為選擇權(quán)值最小的兩個(gè)結(jié)點(diǎn) for(j=0。 ji。 ++j) { if (list[j].parent == 1) { if (list[j].weight value1) { value2 = value1。 rnode = lnode。 value1 = list[j].weight。 lnode = j。 5 / 29 } else if (list[j].weight value2) { value2 = list[j].weight。 rnode = j。 } } } //此部分函數(shù)功能為選擇出的結(jié)點(diǎn)建立關(guān)系 list[lnode].parent = i。 list[rnode].parent = i。 list[i].weight = list[lnode].weight + list[rnode].weight。 list[i].lchild = lnode。 list[i].rchild = rnode。 } } . Huffman 編碼 void CreatHuffmanCode(HuffmanTree *list, HuffmanCode amp。code, int codeSize) { int i, start。 int flag1, flag2。 char *tempCode。 if ((code = (char **)malloc(sizeof(char *) * codeSize)) == NULL) { printf( 內(nèi)存不足 , 操作失敗 !\n)。 exit(0)。 } if