哈夫曼編譯碼器課程設(shè)計報告

計算機學院 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告學號2015-2016學年 第1學期1508數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目：哈夫曼編/譯碼器專業(yè)：計算機科學與技術(shù)（對口）班級：13（3）姓名：陳霞指導教師：彭飛成績：計算機學院2015年11月12日目錄1設(shè)計內(nèi)容及要求31.1 內(nèi)容31.2 要求32概要設(shè)計42.1抽象數(shù)據(jù)類型定義42.2模塊劃分43設(shè)計過程及代碼53.1設(shè)計過程53.2代碼74設(shè)計結(jié)果與分析105參考文獻121 設(shè)計內(nèi)容及要求1.1 內(nèi)容利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼編/譯碼系統(tǒng)。1.2 要求一個完整的系統(tǒng)應(yīng)具有以下功能： （1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和 n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。 （2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件 htmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。 （3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。 （4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼寫入文件CodePrint中。 （5）T：印哈夫曼樹（TreePrinting）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。測試數(shù)據(jù) （1）數(shù)據(jù)一：已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其概率分別為 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此設(shè)計哈夫曼編碼。利用此數(shù)據(jù)對程序 進行調(diào)試。 （2）用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“ THISPROGRAMISMYFAVORITE”。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度57631514851802381811612 概要設(shè)計2.1 抽象數(shù)據(jù)類型定義ADTStack 數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,.,n,n0數(shù)據(jù)關(guān)系：若D為空集，則稱為空樹。 若D僅為一個數(shù)據(jù)元素，則R為空集，否則R=H，H是如下的二元關(guān) 系： （1）再D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)。（2）若D-root空集，則存在一個劃分D1，D2，Dm（m0）。（3）對應(yīng)于D-root的劃分，H-root，X1，有唯一的一個劃分H1，H2，Hm（m0）。 基本操作： InitTree(&T) 操作結(jié)果：構(gòu)造空樹T。DestroyTree(&T) 初始條件：樹T已存在。操作結(jié)果：樹T被銷毀。ClearTree(&T) 初始條件：樹T已存在。操作結(jié)果：將樹T清為空棧。 TreeEmpty(T) 初始條件：樹T已存在。 操作結(jié)果：若樹T為空，則返回TRUE，否則FALSE。 TreeDepth(T) 初始條件:樹T已存在。操作結(jié)果：返回T的深度。 Root（T） 初始條件：樹T已存在。 操作結(jié)果：返回樹T的根。2.2 模塊劃分本程序包括三個模塊：(1)主程序模塊 voidmain() 初始化；構(gòu)造哈夫曼樹；求哈夫曼編碼； 哈夫曼編碼輸出； （2）哈夫曼模塊實現(xiàn)哈夫曼樹的抽象數(shù)據(jù)類型 （3）求哈夫曼編碼模塊實現(xiàn)求哈夫曼編碼算法的數(shù)據(jù)類型3 設(shè)計過程及代碼3.1 設(shè)計過程1、 數(shù)據(jù)類型的定義 （1） 哈夫曼樹類型 typedefstruct/構(gòu)造樹chardata;/結(jié)點權(quán)值intweight;/權(quán)重intparent;/雙親結(jié)點intlchild;/左孩子intrchild;/右孩子HTNode;HTNodeht30; （2） 求哈夫曼編碼類型 typedefstruct charcd30;/存放當前結(jié)點的哈弗曼編碼intstart;/cdstartcdn存放哈弗曼碼HCode;HCodehcd30;2、主要模塊的算法描述開始Int I;inScanf(“%d”,&htt.wei+結(jié)束Int I,f,c;I=0InHc.start=n;c=iF!=-1multiplexHc.start+;I+主函數(shù)流程圖圖3.1.1哈弗曼編碼算法流程圖圖3.1.23.2 代碼#include #definen27/葉子數(shù)目 #definem(2*n-1)/結(jié)點總數(shù)#definemaxval10000.0 #definemaxsize100/哈夫曼編碼的最大位數(shù)typedefstruct charch;floatweight; intlchild,rchild,parent;hufmtree;typedefstruct charbitsn;/位串 intstart;/編碼在位串中的起始位置charch;/字符codetype;voidhuffman(hufmtreetree);/建立哈夫曼樹 voidhuffmancode(codetypecode,hufmtreetree);/根據(jù)哈夫曼樹求出哈夫曼編碼voiddecode(hufmtreetree);/依次讀入字符，根據(jù)哈夫曼樹譯碼 int main() printf( 哈夫曼編碼n);printf(總共有%d個字符n,n);hufmtreetreem; codetypecoden; inti,j;/循環(huán)變量 huffman(tree);/建立哈夫曼樹 huffmancode(code,tree);/根據(jù)哈夫曼樹求出哈夫曼編碼printf(【輸出每個字符的哈夫曼編碼】n); for(i=0;in;i+) printf(%c:,codei.ch);for(j=codei.start;jn;j+) printf(%c,codei.bitsj);printf(n); printf(【讀入字符，并進行譯碼】n); decode(tree);/依次讀入電文，根據(jù)哈夫曼樹譯碼 voidhuffman(hufmtreetree)/建立哈夫曼樹inti,j,p1,p2;/p1,p2分別記住每次合并時權(quán)值最小和次小的兩個根結(jié)點的下標 floatsmall1,small2,f;charc; for(i=0;im;i+)/初始化 treei.parent=0; treei.lchild=-1;treei.rchild=-1;treei.weight=0.0; printf(【依次讀入前%d個結(jié)點的字符及權(quán)值(中間用空格隔開)】n,n); for(i=0;in;i+)/讀入前n個結(jié)點的字符及權(quán)值 printf(輸入第%d個字符為和權(quán)值,i+1); scanf(%c%f,&c,&f); getchar(); treei.ch=c; treei.weight=f; for(i=n;im;i+)/進行n-1次合并，產(chǎn)生n-1個新結(jié)點 p1=0;p2=0;small1=maxval;small2=maxval;/maxval是float類型的最大值for(j=0;ji;j+)/選出兩個權(quán)值最小的根結(jié)點if(treej.parent=0) if(treej.weightsmall1) small2=small1;/改變最小權(quán)、次小權(quán)及對應(yīng)的位置 small1=treej.weight;p2=p1;p1=j;else if(treej.weightsmall2) small2=treej.weight;/改變次小權(quán)及位置 p2=j; treep1.parent=i;treep2.parent=i; treei.lchild=p1;/最小權(quán)根結(jié)點是新結(jié)點的左孩子treei.rchild=p2;/次小權(quán)根結(jié)點是新結(jié)點的右孩子treei.weight=treep1.weight+treep2.weight; /huffman voidhuffmancode(codetypecode,hufmtreetree)/根據(jù)哈夫曼樹求出哈夫曼編碼/codetypecode為求出的哈夫曼編碼/hufmtreetree為已知的哈夫曼樹inti,c,p; codetypecd;/緩沖變量for(i=0;in;i+) cd.start=n; cd.ch=treei.ch; c=i;/從葉結(jié)點出發(fā)向上回溯 p=treei.parent;/treep是treei的雙親while(p!=0) cd.start-; if(treep.lchild=c) cd.bitscd.start=0;/treei是左子樹，生成代碼0else cd.bitscd.start=1;/treei是右子樹，生成代碼1 c=p; p=treep.parent; codei=cd;/第i+1個字符的編碼存入codei /huffmancode voiddecode(hufmtreetree)/依次讀入字符，根據(jù)哈夫曼樹譯碼 inti,j=0; charbmaxsize; charendflag=2;/電文結(jié)束標志取2 i=m-1;/從根結(jié)點開始往下搜索printf(輸入發(fā)送的編碼(以2為結(jié)束標志)：);gets(b); printf(譯碼后的字符為);while(bj!=2) if(bj=0) i=treei.lchild;/走向左孩子else i=treei.rchild;/走向右孩子 if(treei.lchild=-1)/treei是葉結(jié)點 printf(%c,tr