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

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