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