哈夫曼編碼及譯碼器-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告

.PAGE.航空航天大學課程設(shè)計報告課程設(shè)計名稱：數(shù)據(jù)構(gòu)造課程設(shè)計課程設(shè)計題目：實現(xiàn)哈夫曼編碼和譯碼器院〔系〕：計算機學院專業(yè)：計算機科學與技術(shù)班級：24010102學號：82姓名：偉和指導教師：徐蕾..此頁為任務(wù)書目錄1.題目分析11.1.題目重述11.1.1.系統(tǒng)功能需求分析12.程序設(shè)計22.1.系統(tǒng)功能模塊說明22.1.1.系統(tǒng)功能模塊構(gòu)造22.1.2.系統(tǒng)模塊功能說明32.2.數(shù)據(jù)構(gòu)造說明32.2.1.構(gòu)造體定義說明32.2.2.哈夫曼樹42.2.3.字符-哈夫曼編碼對照表42.3.函數(shù)說明43.算法描述63.1.哈夫曼樹的構(gòu)建63.2.字符-哈夫曼編碼對照表63.3.編碼63.4.譯碼74.程序測試84.1.字符集輸入84.2.編碼測試94.3.譯碼測試10參考文獻12附錄〔程序清單〕13..題目分析題目重述本次課程設(shè)計的目標是實現(xiàn)一個哈夫曼編碼和譯碼器。該哈夫曼編碼和譯碼器需要根據(jù)用戶輸入的字符集及相應(yīng)字符出現(xiàn)的頻率，對字符集所包含的字符進展哈夫曼編碼。同時，作為編碼器需要其對用戶提供的明文字符串進展編碼，使明文字符串變?yōu)槎M制密文；作為譯碼器需要對用戶提供的二進制密文進展譯碼，使二進制密文變?yōu)樽址魑摹Ｏ到y(tǒng)功能需求分析通過對課程設(shè)計的題目分析，可以得出哈夫曼編碼和譯碼器的功能需求，需求如下：讀取用戶輸入的字符集和相應(yīng)字符出現(xiàn)的頻率；根據(jù)用戶輸入構(gòu)建哈夫曼樹；根據(jù)哈夫曼樹構(gòu)建字符-哈夫曼編碼對照表；根據(jù)字符-哈夫曼編碼對照表對明文字符串進展編碼；根據(jù)哈夫曼樹對二進制密文進展譯碼。..程序設(shè)計系統(tǒng)功能模塊說明根據(jù)對系統(tǒng)的分析，哈夫曼編碼與譯碼器系統(tǒng)共分為五個功能模塊，分別為：用戶輸入獲取模塊、哈夫曼樹構(gòu)造模塊、字符-哈夫曼編碼對照表構(gòu)造模塊、編碼模塊、譯碼模塊。系統(tǒng)功能模塊構(gòu)造自底向上考慮各系統(tǒng)功能模塊之間的依賴關(guān)系，譯碼模塊依賴于哈夫曼樹構(gòu)造模塊，編碼模塊依賴于字符-哈夫曼編碼對照表構(gòu)造模塊，字符-哈夫曼編碼對照表構(gòu)造模塊依賴于哈夫曼編碼構(gòu)造模塊，哈夫曼編碼構(gòu)造模塊依賴于用戶輸入獲取模塊。系統(tǒng)功能構(gòu)造框圖如圖2-1：圖STYLEREF1\s2SEQ圖\*ARABIC\s11哈夫曼編碼與譯碼器系統(tǒng)功能構(gòu)造框圖系統(tǒng)模塊功能說明用戶輸入獲取模塊獲取并保存用戶從鍵盤上輸入的字符集和相應(yīng)字符出現(xiàn)的頻率。哈夫曼樹構(gòu)造模塊根據(jù)用戶輸入獲取模塊保存的字符數(shù)據(jù)，構(gòu)造哈夫曼樹。字符-哈夫曼編碼對照表構(gòu)造模塊根據(jù)哈夫曼樹構(gòu)造模塊構(gòu)造的哈夫曼樹，建立字符-哈夫曼編碼對照表。編碼模塊根據(jù)字符-哈夫曼編碼對照表構(gòu)造模塊構(gòu)造的字符-哈夫曼編碼對照表，對用戶提供的明文進展編碼。譯碼模塊根據(jù)哈夫曼樹構(gòu)造模塊構(gòu)造的哈夫曼樹，對用戶提供的密文字符進展譯碼。數(shù)據(jù)構(gòu)造說明在程序中主要用到了二叉樹和鏈表等數(shù)據(jù)構(gòu)造。構(gòu)造體定義說明struct_NODE構(gòu)造構(gòu)造體定義如下：typedefstruct_NODE{ charword; intvalue; _NODE*left,*right;}Node,*LPNode; 構(gòu)造體用途：作為哈夫曼樹的結(jié)點構(gòu)造，構(gòu)成哈夫曼樹。struct_CONTAINER構(gòu)造構(gòu)造體定義如下：typedefstruct_CONTAINER{ LPNodev; struct_CONTAINER*last,*next;}Container,*LPContainer; 構(gòu)造體用途：用于在用戶輸入時保存字符信息，并構(gòu)成雙向鏈表。struct_CODENODE構(gòu)造構(gòu)造體定義如下：typedefstruct_CODENODE{ charword; charcode[100]; struct_CODENODE*next;}CodeNode,*LPCodeNode; 構(gòu)造體用途：作為單鏈表的結(jié)點構(gòu)造，構(gòu)成字符-哈夫曼編碼對照表。哈夫曼樹在本程序中，哈夫曼樹是使用struct_NODE構(gòu)造構(gòu)建的二叉樹，其滿足樹的葉子結(jié)點的帶全路徑和在所有可能組成的二叉樹中最小。字符-哈夫曼編碼對照表在本程序中，字符-哈夫曼編碼對照表是一個單鏈表，用于保存字符與哈夫曼編碼的對應(yīng)關(guān)系。函數(shù)說明GetInput函數(shù)該函數(shù)的功能是讀取用戶輸入的字符集數(shù)據(jù)，并構(gòu)建相應(yīng)的哈夫曼樹。函數(shù)的返回值是哈夫曼樹的指針。createHuffmanTree函數(shù)該函數(shù)的功能是根據(jù)用戶輸入構(gòu)建哈夫曼樹。createCodeList函數(shù)該函數(shù)的功能是根據(jù)哈夫曼樹構(gòu)建與之對應(yīng)的字符-哈夫曼編碼對照表。code函數(shù)該函數(shù)用于實現(xiàn)編碼功能。uncode函數(shù)該函數(shù)用于實現(xiàn)譯碼功能。算法描述哈夫曼樹的構(gòu)建在本程序中，GetInput函數(shù)首先將用戶輸入的每個字符信息儲存到struct_NODE構(gòu)造中看做是哈夫曼樹的葉子結(jié)點，并將struct_NODE構(gòu)造的地址儲存到struct_CONTAINER構(gòu)造中，按字符出現(xiàn)頻率升序插入到雙向鏈表中，然后調(diào)用createHuffmanTree函數(shù)構(gòu)造哈夫曼樹。在構(gòu)造哈夫曼樹的過程中，首先從雙向鏈表中選取字符出現(xiàn)頻率最小和第二小的結(jié)點，從中提取哈夫曼樹的子樹，將兩個子樹合并成一個子樹，再將父節(jié)點的地址存入struct_CONTAINER構(gòu)造中，并插入到雙向鏈表中。重復此步驟直到鏈表中只剩下一個結(jié)點。這樣該struct_CONTAINER構(gòu)造中存儲的struct_NODE類型的指針就指向要得到哈夫曼樹的根節(jié)點了。字符-哈夫曼編碼對照表用深度優(yōu)先搜索的方法遞歸的遍歷哈夫曼樹，展開的過程中向調(diào)用的遞歸函數(shù)傳遞要訪問的結(jié)點的哈夫曼編碼。當訪問葉子結(jié)點時，從結(jié)點中提取字符信息，并和其哈夫曼編碼一同儲存到struct_CODENODE構(gòu)造中，然后將struct_CODENODE構(gòu)造插入到單鏈表中。如此，當遍歷完成時，字符-哈夫曼編碼對照表便構(gòu)造完成了。編碼從源文件中讀取一個字符，在字符-哈夫曼編碼對照表中查找該字符，將查找到的結(jié)點中儲存的哈夫曼編碼寫入到目標文件中。圖STYLEREF1\s31構(gòu)建哈夫曼樹流程圖圖STYLEREF1\s32編碼流程圖譯碼從源文件中讀取字符，按照字符的指示訪問哈夫曼樹的子樹，即從根節(jié)點出發(fā)，假設(shè)讀取到‘0’那么訪問左子樹，假設(shè)讀取到‘1’那么訪問右子樹，知道子樹為哈夫曼樹的葉子結(jié)點為止，此時向目標文件中輸出結(jié)點中的字符。圖STYLEREF1\s33譯碼流程圖..程序測試字符集輸入輸入的字符集及字符出現(xiàn)頻率如表4-1所示：表STYLEREF1\s4SEQ表\*ARABIC\s11字符集輸入用例字符abc出現(xiàn)頻率1035預(yù)計生成字符-哈夫曼編碼對照如表4-2所示：表STYLEREF1\s4SEQ表\*ARABIC\s12字符-哈夫曼編碼對照表字符abc哈夫曼編碼10001程序運行效果如圖4-1所示：圖STYLEREF1\s4SEQ圖\*ARABIC\s11程序運行效果圖編碼測試運行程序編碼模塊，如圖4-2所示：圖STYLEREF1\s4SEQ圖\*ARABIC\s12程序運行編碼模塊效果圖程序編碼輸入文件如圖4-3所示：圖STYLEREF1\s4SEQ圖\*ARABIC\s13程序編碼輸入文件截圖輸出分析如表4-3所示：表STYLEREF1\s4SEQ表\*ARABIC\s13編碼輸出分析abcbcaacb100010001110100程序編碼輸入文件如圖4-4所示：圖STYLEREF1\s4SEQ圖\*ARABIC\s14程序編碼輸出文件截圖譯碼測試將編碼后的文件逆向輸入進展譯碼。運行程序譯碼模塊，如圖4-5所示：圖STYLEREF1\s4SEQ圖\*ARABIC\s15程序運行譯碼模塊效果圖程序譯碼輸入文件如圖4-6所示：圖STYLEREF1\s4SEQ圖\*ARABIC\s16程序譯碼輸入文件截圖程序譯碼輸出文件如圖4-7所示：圖STYLEREF1\s4SEQ圖\*ARABIC\s17程序譯碼輸出文件截圖..參考文獻[1]嚴蔚敏,吳偉民.數(shù)據(jù)構(gòu)造(C語言版)[M].:清華大學,2006[2]呂國英.算法設(shè)計與分析[M].:清華大學,2006[3]徐寶文,志.C程序設(shè)計語言[M].:機械工業(yè),2004[4]ErichGamma,RichaedHelm.設(shè)計模式(英文版)[M].:機械工業(yè),2004..附錄〔程序清單〕#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstruct_NODE{ charword; intvalue; _NODE*left,*right;}Node,*LPNode;typedefstruct_CONTAINER{ LPNodev; struct_CONTAINER*last,*next;}Container,*LPContainer;typedefstruct_CODENODE{ charword; charcode[100]; struct_CODENODE*next;}CodeNode,*LPCodeNode;voidinsert(LPContainerlist,LPContainernode){ LPContainerp; p=list->last; while(node->v->value<p->v->value) { p=p->last; } node->last=p; node->next=p->next; p->next->last=node; p->next=node;}LPNodecreateHuffmanTree(LPContainerlist){ LPContainerp; LPNodeleft,right,t; while(list->next!=list->last) { p=list->next; list->next=p->next; left=p->v; free(p); p=list->next; list->next=p->next; list->next->last=list; right=p->v; t=(LPNode)malloc(sizeof(Node)); t->word=-1; t->value=left->value+right->value; t->left=left; t->right=right; p->v=t; insert(list,p); } p=list->next; list->next=p->next; list->next->last=list; left=p->v; free(p); returnleft;}LPNodeGetInput(){ Containerlist; LPContainerp; LPNodehead; inti,num; printf("輸入字符集規(guī)模："); scanf("%d",&num); list.v=(LPNode)malloc(sizeof(Node)); list.v->word=-1; list.v->value=0; list.v->left=list.v->right=NULL; list.next=&list; list.last=&list; for(i=0;i<num;i++) { p=(LPContainer)malloc(sizeof(Container)); p->v=(LPNode)malloc(sizeof(Node)); p->v->left=p->v->right=NULL; getchar(); printf("輸入字符："); scanf("%c",&p->v->word); printf("輸入該字符的權(quán)值："); scanf("%d",&p->v->value); insert(&list,p); } printf("正在構(gòu)造哈夫曼樹……\n"); head=createHuffmanTree(&list); printf("哈夫曼樹創(chuàng)立成功!\n"); free(list.v); returnhead;}voiddfs(LPNodet,char*code,LPCodeNodelist){ LPCodeNodep; charl[100],r[100]; if(t->word!=-1) { p=(LPCodeNode)malloc(sizeof(CodeNode)); p->word=t->word; strcpy(p->code,code); p->next=list->next; list->next=p; return; } strcpy(l,code); strcat(l,"0"); dfs(t->left,l,list); strcpy(r,code); strcat(r,"1"); dfs(t->right,r,list);}LPCodeNodecreateCodeList(LPNodetree){ CodeNodehead; head.next=NULL; dfs(tree,"",&head); returnhead.next;}voidcode(LPCodeNodelist){ FILE*sfp,*dfp; charpath[256],c; LPCodeNodep; printf("請輸入源文件路徑："); scanf("%s",path); sfp=fopen(path,"rt"); printf("請輸入目標文件路徑："); scanf("%s",path); dfp=fopen(path,"wt"); while((c=fgetc(sfp))!=EOF) { p=list; while(p->word!=c) p=p->next; fputs(p->code,dfp); } fclose(sfp); fclose(dfp);}voiduncode(LPNodetree){ FILE*sfp,*dfp; charpath[256],c; LPNodep; printf("請輸入源文件路徑："); scanf("%s",path); sfp=fopen(path,"rt"); printf("請輸入目標文件路徑："); scanf("%s",path); dfp=fopen(path,"wt"); p=tree; while((c=fgetc(sfp))!=EOF) { if(c=='0')