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