數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、長安大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告課題：赫哈曼編碼的應(yīng)用姓名：王寶寶學(xué)號：2402100305專業(yè)班級：24021003指導(dǎo)教師：張少博2011 年 6 月 14日1目錄一、需求分析 3二、設(shè)計原理與概要4三、程序流程圖.5四、程序源代碼8五、運行結(jié)果與驗證16六、設(shè)計總結(jié) .182第一部分需求分析本設(shè)計要求是對輸入的一串字符實現(xiàn)赫夫曼編碼， 再對赫夫曼編碼生成的代碼串進行譯碼，輸出電文字符串。在當(dāng)今信息爆炸的時代， 如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視， 赫夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。赫夫曼編碼的應(yīng)用很廣泛，如在

2、音樂、電影、攝影、通信等領(lǐng)域都有它應(yīng)用的身影，存儲、分析、加工、處理是它們制作的第二階段，怎樣使制作出來的作品質(zhì)量最好、 體積最少，是關(guān)系產(chǎn)品受到青睞的原因之一。 體積的大小也就是它所占據(jù)存儲空間， 在保證文件質(zhì)量最好， 又有效的節(jié)省存儲空間， 需要用最好的壓縮存儲解碼算法， 而赫夫曼編碼是一種將信息轉(zhuǎn)換成二進制編碼有效的方法之一，赫夫曼編碼是利用赫夫曼樹求得的用于通信的二進制編碼。 而這次我們的課程設(shè)計對編碼譯碼的要求不是太高， 只是將大寫字母或小寫字母轉(zhuǎn)化成二進制編碼，或?qū)⒍M編碼轉(zhuǎn)化成大寫字母或小寫字母， 雖然功能有一點局限， 但也是一次成功的嘗試，能滿足一般的需求。根據(jù)設(shè)計要求和分析，

3、要實現(xiàn)本設(shè)計，必須實現(xiàn)以下幾個方面的功能：（ 1） 赫夫曼樹的建立；（ 2） 赫夫曼的編碼生成；（ 3） 編碼文件的譯碼；3二設(shè)計原理與概要樹中從根到每個葉子都有一條路徑， 對路徑上的個分支約定： 指向左子樹的分支表示“ 0”碼，指向右子樹的分支表示“ 1”碼，取每條路徑上的“ 0”或“1”的序列作為和各個葉子對應(yīng)的字符編碼，這就是赫夫曼編碼。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程就是解碼。電報通信是傳遞文字的二進制形式的字符串。 但在信息傳遞時， 總希望長度盡可能短， 即采用最短碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為 Wi ，編碼的長度為 Li ，電文中有 n 種字符，則電文編碼的總長

4、度為 WiLi, 若將此對應(yīng)到二叉樹上， Wi 為葉結(jié)點的權(quán)， Li 為根結(jié)點到葉結(jié)點的路徑長度。那么， wiLi 恰好為二叉樹上帶權(quán)路徑的長度。設(shè)計要求：1. 初始化。根據(jù)下表給出的英文字母的使用頻度，建立哈夫曼樹?？崭瘢?0.2 E：0.105 T： 0.071 O：0.0644A： 0.063 N：0.059 I： 0.054 R： 0.053S：0.052 H：0.047 D：0.035 L： 0.029C： 0.023 U：0.0225 F：0.0221 M：0.021P：0.0175 Y、W ：0.012 G： 0.011 B：0.0105V： 0.008 K：0.003 X： 0

5、.002 J、 Q：0.001Z：0.0012. 編碼。利用已建好的哈夫曼樹，對電報正文進行編碼。3. 譯碼。對編碼好的內(nèi)容進行譯碼。4. 打印編碼。5. 打印哈夫曼樹。運行環(huán)境：Windows 95/98 環(huán)境， Microsot Visual C+ 6.0 (簡稱 VC)4總流程圖：定義各種變量輸入需要編碼的字符串（為大寫或小寫）統(tǒng)計字符的種類及各種字符出現(xiàn)的頻率建立赫夫曼樹生成赫夫曼編碼建立各種字符的赫夫曼編碼及編碼文件從文件中讀編碼文件譯碼輸出譯碼后的字符串圖（ 1）5建立正文的編碼文件的流程圖：開始輸入電文字符串電文字符只能包截取單個電文字符含26個英文字母和英文空格字符電文字符是否

6、否合法？是累計對應(yīng)編碼的下標(biāo)值累計對應(yīng)編碼的長度值是是否還有剩余電文字符？否連接編碼字符串打印電文的赫夫曼編碼結(jié)束圖 （2）6代碼文件的譯碼流程圖：開始輸入赫夫曼編碼截取單個編碼字符編碼字符是否合法？是是編碼字符是否等于 0？遍歷左子樹否是否為樹的葉子節(jié)點？是檢索對應(yīng)字符是是否還有剩余編碼字符？否連接電文字符打印電文結(jié)束圖（ 3）編碼字符只能包含英文字符 0和 1否否遍歷右子樹7程序源代碼 :#include stdio.h#include string.h#include malloc.h/權(quán)重信息數(shù)組static float weights=0.2,0.105,0.071,0.0644,0

7、.063,0.059,0.054,0.053,0.052,0.047,0.035,0.029,0.023,0.0225,0.0221,0.021,0.0175,0.012,0.012,0.011,0.0105,0.008,0.003,0.002,0.001,0.001,0.001;/字符信息數(shù)組static char values= ,E,T,O,A,N,I,R,S,H,D,L,C,U,F,M,P,Y,W,G,B,V,K,X,J,Q,Z;/動態(tài)分配數(shù)組存儲赫夫曼樹typedef struct/節(jié)點權(quán)重值float weight;/節(jié)點對應(yīng)的父節(jié)點unsigned int parent;/左子節(jié)

8、點的索引值unsigned int lchild;/右子節(jié)點的索引值unsigned int rchild;HTNode,*HuffmanTree;/動態(tài)分配數(shù)組存儲赫夫曼編碼表typedef char *HuffmanCode;/返回 i 個節(jié)點中權(quán)值最小的樹的根節(jié)點序號int min(HuffmanTree t,int i)int j,flag;float k=1.0;/逐個迭代求解最小權(quán)重for(j=1;j=i;j+)8if(tj.weights2)temp=s1;s1=s2;s2=temp;/根據(jù)節(jié)點的權(quán)重值數(shù)組，構(gòu)造赫夫曼樹，同時求解每個節(jié)點的編碼void HuffmanCoding

9、(HuffmanTree &HT,HuffmanCode &HC,float *w,int n)/中間變量int m,i,s1,s2,start;unsigned c,f;HuffmanTree p;char *cd;/節(jié)點個數(shù)至少為2if(n=1)/直接返回return;/所需節(jié)點總數(shù)m=2*n-1;/創(chuàng)建存儲赫夫曼樹的數(shù)組，0 號單元留空HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/初始化終端節(jié)點9for(p=HT+1,i=1;i=n;+i,+p,+w)(*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).

10、rchild=0;/初始化非終端節(jié)點for(;i=m;+i,+p)(*p).weight=0.0;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;/創(chuàng)建赫夫曼樹，核心算法for(i=n+1;i=m;+i)select(HT,i-1,s1,s2);/更新終端節(jié)點的信息HTs1.parent=HTs2.parent=i;/更新非終端節(jié)點的子節(jié)點的索引值HTi.lchild=s1;HTi.rchild=s2;/更新非終端節(jié)點的權(quán)重值HTi.weight=HTs1.weight+HTs2.weight;/創(chuàng)建存儲節(jié)點赫夫曼編碼的數(shù)組HC=(HuffmanCode)m

11、alloc(n+1)*sizeof(char*);/中間變量cd=(char*)malloc(n*sizeof(char);/字符串結(jié)束符cdn-1=0;for(i=1;i=n;i+)start=n-1;/根據(jù)節(jié)點的父節(jié)點索引值求解節(jié)點的赫夫曼編碼for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)/左分支為 0cd-start=0;else/右分支為 1cd-start=1;/動態(tài)分配對應(yīng)編碼存儲空間大小10HCi=(char*)malloc(n-start)*sizeof(char);/字符串拷貝strcpy(HCi,&cd

12、start);/釋放內(nèi)存空間free(cd);/將電報正文進行編碼void coding(HuffmanCode HC)/索引變量int index;/電報正文索引值int textIndex;/電報正文字符的索引值int valueIndex;/電報正文包含的字符個數(shù)int teleLength;/電報正文字符對應(yīng)的赫夫曼編碼表中的索引int *codeIndex;/中間變量，存儲電報正文char *teleText;/中間變量，用于存儲電報正文的赫夫曼編碼char *huCoding;/電報正文對應(yīng)赫夫曼編碼的總長度,初始化長度為 0int codeLength=0;/編碼，根據(jù)已建好的赫

13、夫曼樹，對電報正文進行編碼printf(please input telegram text length,eg.len(ASD)=3:); scanf(%d,&teleLength);/分配用于存儲編碼表索引值的存儲空間codeIndex=(int*)malloc(teleLength*sizeof(int);/分配用于存儲電文字符的存儲空間teleText=(char*)malloc(teleLength*sizeof(char);printf(please input telegram text,eg.ASD:);/輸入電報正文字符串scanf(%s,teleText);/根據(jù)赫夫曼編碼

14、表對電報正文進行編碼for(textIndex=0;textIndex96)11textChar=textChar-32;/如果電報正文中包含非法字符直接返回if(textChar=64)|(textChar=91)|(textChar=123) printf(something wrong with your input telegram text%s!n,teleText);return;/依次查找對應(yīng)字符for(valueIndex=1;valueIndex=27;valueIndex+)if(valuesvalueIndex-1=textChar)/累計編碼的索引值codeIndext

15、extIndex=valueIndex;/找到對應(yīng)字符 ,累計編碼長度值codeLength+=strlen(HCvalueIndex);/終止內(nèi)層循環(huán)break;/動態(tài)分配存儲電文編碼的內(nèi)存空間huCoding=(char*)malloc(codeLength+1)*sizeof(char);/初始化上述內(nèi)存數(shù)據(jù)for(index=0;index=codeLength;index+)/字符串結(jié)束符huCodingindex=0;/組裝電文編碼信息for(textIndex=0;textIndexstrlen(teleText);textIndex+)/編碼字符串的連接huCoding=str

16、cat(huCoding,HCcodeIndextextIndex);printf(telegram Huffman code:%sn,huCoding);/釋放內(nèi)存空間free(teleText);free(codeIndex);free(huCoding);/將電報正文的赫夫曼編碼進行譯碼操作void decoding(HuffmanTree HT)/索引變量int index;12/記錄臨時索引值int tempIndex=53;/單個編碼char huCode;/電文編碼的長度int huCodeLen;/電文字符串（字符數(shù)組）char *huCodes;/赫夫曼樹的節(jié)點HTNode

17、htNode;/編碼，根據(jù)已建好的赫夫曼樹，對電報正文進行編碼printf(please input telegram Huffman code length,eg.len(10110110)=8:); scanf(%d,&huCodeLen);/分配用于存儲電文字符編碼的存儲空間huCodes=(char*)malloc(huCodeLen*sizeof(char);printf(please input telegram Huffman code,eg.10110110=AI:);/輸入電報正文的編碼字符串scanf(%s,huCodes);/獲取根節(jié)點htNode=HT53;/遍歷赫夫曼

18、樹 ,依次檢索編碼信息for(index=0;indexstrlen(huCodes);index+)/獲取單個編碼字符huCode=huCodesindex;/沒有找到對應(yīng)的編碼字符if(tempIndex=0)printf(something wrong with your input telegram Huffman code %s!n,huCodes);return;if(huCode=1)/向右遍歷if(HThtNode.rchild.lchild=0 & HThtNode.rchild.rchild=0)/遍歷至葉子節(jié)點 ,找到一個電文子字符tempIndex=htNode.rch

19、ild;printf(%c,valuestempIndex-1);/再次指向根節(jié)點htNode=HT53;else/繼續(xù)遍歷，記錄當(dāng)前節(jié)點的信息tempIndex=htNode.rchild;htNode=HTtempIndex;13else if(huCode=0)/向左遍歷if(HThtNode.lchild.lchild=0 & HThtNode.lchild.rchild=0)/遍歷至葉子節(jié)點 ,找到一個電文子字符tempIndex=htNode.lchild;printf(%c,valuestempIndex-1);/再次指向根節(jié)點htNode=HT53;else/繼續(xù)遍歷，記錄當(dāng)前

20、節(jié)點的信息tempIndex=htNode.lchild;htNode=HTtempIndex;else/輸入電文編碼有誤，結(jié)束本次譯碼操作printf(something wrong with your input telegram Huffman code %s!n,huCodes);return;printf(n);/打印赫夫曼樹void printHuffmanTree(HuffmanTree HT)int index;/赫夫曼樹節(jié)點HTNode htNode;printf(Huffman tree table:n);printf(WEIGHT PARENT LCHILD RCHILD

21、n);/m=2*n-1for(index=1;index54;index+)/獲取當(dāng)前樹節(jié)點htNode=HTindex;/依次輸出節(jié)點的權(quán)重值和孩子節(jié)點的索引值printf(%12.4f%5d%6d%7dn,htNode.weight,htNode.parent,htNode.lchild,htNo de.rchild);void printHuffmanCode(HuffmanCode HC)/索引變量14int index;printf(Huffman code table:n);/依次打印每個關(guān)鍵字對應(yīng)的赫夫曼編碼for(index=1;index=27;index+)/顯示空格字符if(index=1)printf(%7c-,_);elseprintf(%7c-,valuesindex-1);/打印對應(yīng)的赫夫曼編碼printf(%sn,HCindex);void main()/電文的赫夫曼編碼char c;HuffmanTree HT;HuffmanCode HC;/創(chuàng)建赫夫曼樹，同時求解赫夫曼編碼HuffmanCoding(HT,HC,weights,27);/printf(Huffman tree has been create