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

數(shù)據(jù)結(jié)構(gòu)與算法 課程設(shè)計（2013/2014學年第一學期17周）班級： 學號： 姓名：指導教師： 楊東鶴 王敏麗目 錄一、 題目二、 需求分析三、 概要設(shè)計四、 程序說明五、 詳細設(shè)計六、 實驗心得與體會七、 備注一、題目：赫夫曼編碼/譯碼器1. 問題描述利用赫夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個赫夫曼碼的編/譯碼系統(tǒng)。2. 基本要求一個完整的系統(tǒng)應具有以下功能：(1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立赫夫曼樹，并將它存于文件hfmTree中。(2) E：編碼（Encoding）。利用已建好的赫夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。(3) D：譯碼（Decoding）。利用已建好的赫夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件Textfile中。以下為選做：(4) P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。(5) T：印赫夫曼樹（Tree printing）。將已在內(nèi)存中的赫夫曼樹以直觀的方式（比如樹）顯示在終端上，同時將此字符形式的赫夫曼樹寫入文件TreePrint 中。3. 測試要求(1) 已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其頻率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，試設(shè)計赫夫曼編碼。(2) 用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立赫夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAME IS MY FAVORITE”。字符 ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度57631514851802381811614. 實現(xiàn)提示(1) 編碼結(jié)果以文本方式存儲在文件Codefile中。(2) 用戶界面可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。(3) 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令之后，赫夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。二、需求分析：數(shù)據(jù)結(jié)構(gòu)與算法是計算機專業(yè)重要的核心課程之一，在計算機專業(yè)的學習過程中占有非常重要的地位。數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計就是要運用本課程以及到目前為止的有關(guān)課程中的知識和技術(shù)來解決實際問題。特別是面臨非數(shù)值計算類型的應用問題時，需要選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)，設(shè)計出滿足一定時間和空間限制的有效算法。本課程設(shè)計要求同學獨立完成一個較為完整的應用需求分析。并在設(shè)計和編寫具有一定規(guī)模程序的過程中，深化對數(shù)據(jù)結(jié)構(gòu)與算法課程中基本概念、理論和方法的理解；訓練綜合運用所學知識處理實際問題的能力，強化面向?qū)ο蟮某绦蛟O(shè)計理念；使自己的程序設(shè)計與調(diào)試水平有一個明顯的提高。 三、概要設(shè)計：開始退出建哈弗曼樹哈弗曼譯碼哈弗曼編碼DecodingCodingInitHuffmanCodingselect結(jié)束四、程序說明：（1） typedef struct/哈夫曼樹結(jié)點結(jié)構(gòu)（2） int weight; （3） char data; /存放該節(jié)點的字符（4） int parent,lchild,rchild;（5） HTNode,*HuffmanTree;（6） typedef char* HuffmanCode; /指向哈夫曼編碼的指針（7） void HuffmanCoding(HuffmanTree &,char *,int *,int);/建立哈夫曼樹（8） void select(HuffmanTree HT,int j,int *s1,int *s2); /選擇parent為0且weight最小的兩個結(jié)點（9） void Init(); /初始化（10） void Coding(); /編碼（11） void Decoding(); /譯碼（12） void find(HuffmanTree &HT,char *code,char *text,int i,int m);/尋找相應葉子節(jié)點的遞歸算法（13） HuffmanTree HT; /指向存放哈夫曼樹的存儲空間（14） int n=0; /哈夫曼樹葉子結(jié)點數(shù)目（15） int main()/主函數(shù)五、詳細設(shè)計：/*主函數(shù)*/int main()char select;while(1)printf(n*-*-*n);printf(tttt請輸入操作:n);printf(n);printf(ttttI-建哈夫曼樹n);printf(ttttC-哈夫曼編碼n);printf(ttttD-哈夫曼譯碼n);printf(ttttQ-退出n);printf(ntttt);scanf(%c,&select);switch(select)case I:Init();break;case C:Coding();break;case D:Decoding();break;case Q:exit(1);default :printf(操作錯誤n);getchar();return 0;/*初始化函數(shù)，輸入n個字符及其對應的權(quán)值，根據(jù)權(quán)值建立哈夫曼樹*/void Init() FILE *fp;int i,w52; /w數(shù)組存放n個字符的權(quán)值char character52; /存放n個字符printf(ntttt輸入字符個數(shù) n:);scanf(%d,&n); /輸入字符集個數(shù)printf(tttt輸入%d個字符及其對應的權(quán)值n,n);for(i=0;in;i+)char b=getchar();/讀入空格scanf(%c,&characteri);scanf(%d,&wi); /輸入個字符和對應的權(quán)值HuffmanCoding(HT,character,w,n); /建立哈夫曼樹if(fp=fopen(hfmtree.txt,w)=NULL) /建立新文件進行只寫printf(hfmtree.txt打開失敗!n);for(i=1;i=2*n-1;i+)if(fwrite(&(HTi.data),sizeof(char),1,fp)!=1)printf(寫入文件失敗!n);if(fwrite(&(HTi.weight),sizeof(int),1,fp)!=1)printf(寫入文件失敗!n);if(fwrite(&(HTi.parent),sizeof(int),1,fp)!=1)printf(寫入文件失敗!n);if(fwrite(&(HTi.lchild),sizeof(int),1,fp)!=1)printf(寫入文件失敗!n);if(fwrite(&(HTi.rchild),sizeof(int),1,fp)!=1)printf(寫入文件失敗!n);printf(n哈夫曼樹建立成功，已將其存于hfmtree.txtn);fclose(fp);/建立哈夫曼樹的算法void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)int m,i,s1,s2;HuffmanTree p;if(n=1)return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;idata=*character;p-weight=*w;p-parent=0;p-lchild=0;p-rchild=0;/給前面?zhèn)€節(jié)點賦初值，p、character、w指針后移向下一個葉節(jié)點for(;idata=0;p-weight=0;p-parent=0;p-lchild=0;p-rchild=0;/給后面要生成的節(jié)點賦初值全為0for(i=n+1;i=m;+i)select(HT,i-1,&s1,&s2);/從HT1到HTi-1中選擇parent為0且weight最小的兩個?結(jié)點，用s1和s2返回其序號HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;/把最小值賦給s1次小值賦給s2HTi.weight=HTs1.weight+HTs2.weight;/生成新節(jié)點/*從HT1到HTj中選擇parent為0且weight最小的兩個結(jié)點，用s1和s2返回其序號*/void select(HuffmanTree HT,int j,int *s1,int *s2)int i;for(i=1;i=j;i+) if(HTi.parent=0)*s1=i;break;/有個沒訪問過的就跳出循環(huán)，以此為起點比較for(;i=j;i+)if(HTi.parent=0)&(HTi.weightHT*s1.weight)*s1=i;/則s1為最小結(jié)點的序號HT*s1.parent=1;/提前給HT*s1.parent賦值1，以免找次小結(jié)點、判斷條件時受影響for(i=1;i=j;i+)if(HTi.parent=0)*s2=i;break;/有一個沒訪問過的就跳出循環(huán)，以此為起點比較for(;i=j;i+)if(HTi.parent=0)&(i!=*s1)&(HTi.weightHT*s2.weight)*s2=i; /找weight次小的結(jié)點void Coding() FILE *fp,*fw;int i,f,c,start;char *cd;HuffmanCode HC;/*以下程序段求赫夫曼樹中各葉子節(jié)點的字符對應的編碼，并存于HC指向的空間中*/HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i)start=n-1;/為了后面HC空間的分配中的n-start，沒有編碼就只分配一個sizeof空間，即結(jié)束符，即n-(n-1)=1for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char *)malloc(n-start)*sizeof(char);/為第i個字符編碼分配空間，用于下面語句的賦值strcpy(HCi,&cdstart);/取首地址開始賦值free(cd);if(fp=fopen(tobetran.txt,rb)=NULL)/打開文件進行只讀printf(tobetran.txt打開失敗!n);if(fw=fopen(codefile.txt,wb+)=NULL)/建立新文件進行讀/寫printf(codefile.txt打開失敗!n);char temp;fscanf(fp,%c,&temp); /從fp所指的文件中讀入第一個字符到temp變量while(!feof(fp)for(i=1;i=n;i+)if(HTi.data=temp)break; /若和1號節(jié)點相同則跳出循環(huán)，否則繼續(xù)查找for(int r=0;HCir!=0;r+) /在哈夫曼樹中查找字符所在的位置fputc(HCir,fw); /將字符對應的編碼存入文件，把HCir寫到fw所指示文件fscanf(fp,%c,&temp); /從文件讀入下一個字符fclose(fw);fclose(fp);printf(nhfmtree.txt編碼成功，已將其存于codefile.txtn);void Decoding() FILE *fp,*fw;int m,i;char *code,*text,*p;if(fp=fopen(codefile.txt,rb)=NULL)/打開文件進行只讀printf(codefile.txt打開失敗!n);if(fw=fopen(textfile.txt,wb+)=NULL)/建立新文件讀/寫,若已建立，內(nèi)容會清空printf(textfile.txt打開失敗!n);code=(char *)malloc(sizeof(char);fscanf(fp,%c,code); /從文件讀入一個0或1字符for(i=1;!feof(fp);i+)code=(char *)realloc(code,(i+1)*sizeof(char); /增加空間，把code所指示的空間大小設(shè)置為(i+1)*sizeof(char)fscanf(fp,%c,&codei); /從文件讀入下一個0或1的字符/至此codefile.txt文件中的0、1已全部讀入，存放在code數(shù)組中text=(char *)malloc(100*sizeof(char);p=text;m=2*n-1;if(*code=0)find(HT,code,text,HTm.lchild,m); /從根節(jié)點的左子樹找elsefind(HT,code,text,HTm.rchild,m); /從根節(jié)點的右子樹找for(i=0;pi!=0;i+) /把譯碼好的字符存入文件textfile.txt中fputc(pi,fw);/把pi寫到fw所指示的文件中fclose(fp);fclose(fw);printf(ncodefile.txt譯碼成功，已將其存于textfile.txtn);/*譯碼時根據(jù)01字符串尋找相應葉子節(jié)點的遞歸算法*/void find(HuffmanTree &HT,char *code,char *text,int i,int m)if(*code!=0) /若譯碼未結(jié)束code+;if(HTi.lchild=0&HTi.rchild=0) /若找到葉子節(jié)點*text=HTi.data; /將葉子節(jié)點字符存入text中text+;if(*code=0)find(HT,code,text,HTm.lchild,m); /繼續(xù)從根節(jié)點的左子樹找elsefind(HT,code,text,HTm.rchild,m); /繼續(xù)從根節(jié)點的右子樹找else /如果不是葉子節(jié)點if(*code=0)find(HT,code,text,HTi.lchild,m); /從該節(jié)點左子樹找elsefind(HT,code,text,HTi.rchild,m); /從該節(jié)點右子樹找else*text=0; /譯碼結(jié)束六、調(diào)試分析：由所給字符和權(quán)值建立哈弗曼樹：由所建立的哈弗曼樹編碼hfmtree.txt:由哈弗曼樹和哈弗曼編碼譯碼codefile.txt:七、實驗心得與體會：初始的創(chuàng)建是哈夫曼編碼譯碼系統(tǒng)成功的關(guān)鍵，結(jié)點字符或者權(quán)重信息，作為檢驗，對驗證和糾錯起到了非常大的作用。在適當?shù)牡胤秸{(diào)用它們，運行時可以看到驗證編寫程序的正確性；通過本次實驗，提高了自已調(diào)試程序的能力。充分體會到了在程序執(zhí)行時的提示性輸出的重要性。編寫大一點的程序，應先寫出算法，再寫程序，一段一段調(diào)試；對于沒有實現(xiàn)的操作用空操作代替，這樣容易找出錯誤所在。最忌諱將所有代碼寫完后再調(diào)試，這樣若程序有錯誤，太難找。需要特別強調(diào)的是：1感覺文件操作自己并不是很熟練，盡管在向顯示器輸出的時候并沒有什么錯誤但是讀寫文件的時候就沒那么順利了，是文件沒有打開或者文件結(jié)束的緣故。2.用哈夫曼編碼存儲文件的時候還應注意數(shù)字0,1與字符0,1的不同，0在ASCII碼中代表NULL。3.該程序函數(shù)清晰功能明確，程序具有通用性，對于不同的輸入文章都可進行處理，由于采用哈夫曼編碼對照表，使得查看哈夫曼編碼是效率較高無需每次遍歷哈夫曼樹八、備注：一、具體要求：課程設(shè)計成果的內(nèi)容必須由以下四個部分組成，缺一不可。(1) 上交源程序：學生按照實驗題目的具體要求所開發(fā)的所有源程序（應該放到一個文件夾中）；(2) 上交程序的說明文件：（保存在.txt中）在說明文檔中應該寫明上交程序所在的目錄，上交程序的主程序文件名，如果需要安裝，要有程序的安裝使用說明；(3) 設(shè)計報告：（保存在word 文檔中，文件名要求： 按照“姓名_學號_設(shè)計題目”起名，如文件名為“ 張三_XXX_哈夫曼編碼 ”.doc。打印稿用A4紙）。其中包括: 題目； 實驗目的； 需求分析： 在該部分中敘述實現(xiàn)的功能要求； 概要設(shè)計：在此說明每個部分的算法設(shè)計說明（可以是描述算法的流程圖），每個程序中使用的存儲結(jié)構(gòu)設(shè)計說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義）； 詳細設(shè)計各個算法實現(xiàn)的源程序，對每個題目要有相應的源程序（可以是一組源程序，每個功能模塊采用不同的函數(shù)實現(xiàn)）。源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量、重點功能部分要加上清晰的程序注釋； 調(diào)試分析測試數(shù)據(jù)，測試輸出的結(jié)果，時間復雜度分析，和每個模塊設(shè)計和調(diào)試時存在問題的思考（問題是哪些？問題如何解決？），算法的改進設(shè)想； 總結(jié)： 總結(jié)可以包括 : 設(shè)計過程的收獲、遇到問題及解決問題過程的思考、程序調(diào)試能力的思考、對數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在設(shè)計過程中對數(shù)據(jù)結(jié)構(gòu)課程的認識等內(nèi)容。二、工作內(nèi)容及工作計劃：一周（17）時間地點工作內(nèi)容指導教師12月 23日上午10-306實驗要求，需求分析； 楊東鶴、王敏麗下