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