《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》赫夫曼編碼實(shí)驗(yàn)報(bào)告

目錄TOC\o"1-3"\h\u28012一、概述 一、概述本設(shè)計(jì)是對(duì)輸入的一串電文字符實(shí)現(xiàn)赫夫曼編碼，再對(duì)赫夫曼編碼生產(chǎn)的代碼串進(jìn)行譯碼，輸出電文字符串。在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間越來(lái)越引起人們的重視，赫夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。二、系統(tǒng)分析赫夫曼編碼的應(yīng)用很廣泛，利用赫夫曼樹求得的用于通信的二進(jìn)制編碼成為赫夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和每個(gè)葉子對(duì)應(yīng)的字符的編碼，這就是赫夫曼編碼。通常我們把數(shù)據(jù)壓縮的過(guò)程稱為編碼，解壓縮的過(guò)程稱為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式的字符串，但在信息傳遞時(shí)，總希望總長(zhǎng)度能盡可能短，即采用最短碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi,編碼長(zhǎng)度為L(zhǎng)i，電文中有n種字符，則電文編碼總長(zhǎng)為∑WiLi。若將此對(duì)應(yīng)到二叉樹上，Wi為葉節(jié)點(diǎn)的權(quán)，Li為根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑長(zhǎng)度。那么，∑WiLi恰好為二叉樹上帶權(quán)路徑長(zhǎng)度。因此，設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼，就是以n種子符出現(xiàn)的頻率作權(quán)，構(gòu)造一刻赫夫曼樹，此構(gòu)造過(guò)程成為赫夫曼編碼。根據(jù)設(shè)計(jì)要求和分析，要實(shí)現(xiàn)設(shè)計(jì)，必須實(shí)現(xiàn)以下方面的功能：赫夫曼樹的建立；赫夫曼編碼的生成；編碼文件的譯碼；三、概要設(shè)計(jì)程序由哪些模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個(gè)模塊的功能。voidmain()voidHufffmanEncoding(HuffmanTreeHT,HuffmanCodeHC)//編碼部分char*decode(HuffmanCodeHc)//譯碼voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[])//生成Huffman樹voidselect(HufmanTreeHT,intk,int&s1,int&s2)//找尋parent為0,權(quán)最小的兩個(gè)節(jié)點(diǎn)其流程圖如下：進(jìn)行相應(yīng)的操作進(jìn)行相應(yīng)的操作輸出結(jié)果結(jié)束構(gòu)造赫夫曼樹程序結(jié)束退出對(duì)編碼串譯碼對(duì)字符串編碼開始進(jìn)行相應(yīng)的操作四、詳細(xì)設(shè)計(jì)4.1赫夫曼樹的建立由赫夫曼算法的定義可知，初始森林中共有n棵只含根節(jié)點(diǎn)的二叉樹。算法的第二步是：將當(dāng)前森林中的兩顆根節(jié)點(diǎn)的二叉樹，合并成一顆新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個(gè)新節(jié)點(diǎn)。顯然要進(jìn)行n-1次合并，所以共產(chǎn)生n-1個(gè)新節(jié)點(diǎn)，它們都是具有兩個(gè)孩子分支結(jié)點(diǎn)。由此可知，最新求得的赫夫曼樹中一共有2n-1個(gè)結(jié)點(diǎn)，其中n個(gè)結(jié)點(diǎn)是初始森林的n個(gè)孤立結(jié)點(diǎn)。并且赫夫曼樹中沒(méi)有度數(shù)為1的分支結(jié)點(diǎn)。我們可用一個(gè)大小為2n-1的一維數(shù)組來(lái)存儲(chǔ)赫夫曼樹中的結(jié)點(diǎn)。因此，赫夫曼樹的存儲(chǔ)結(jié)構(gòu)描述為：#definen100#definem2*n-1typedefstruct{intweight;intlchild,rchild,parent;}HTNode;TtypedefHTNodeHuffmanTree[m+1];開始開始結(jié)束第i個(gè)結(jié)點(diǎn)權(quán)值i=num?創(chuàng)建赫夫曼樹輸出字符統(tǒng)計(jì)情況第i個(gè)根結(jié)點(diǎn)i=2*num-1?i=num?否是否是否是4.1.1選擇選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法voidselect(HuffmanTreeT,intk,int*s1,int*s2){//在HT[1……k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，其序號(hào)分別為S1和S2inti,j;intmin1=100;for(i=1;i<=k;i++)//查找s1if(T[i].weight<min1&&T[i].parent==0){j=i;min1=T[i].weight;}*s1=j;min1=32767;for(i=1;i<=k;i++)//查找s2,不和s1相同if(T[i].weight<min1&&T[i].parent==0&&i!=(*s1)){j=i;min1=T[i].weight;}*s2=j;}4.1.2統(tǒng)計(jì)字符串中字符的種類以及各類字符的個(gè)數(shù)假設(shè)電子文件字符串全是大寫字母，那么該算法的實(shí)現(xiàn)思想是：先定義一個(gè)含有26個(gè)元素的臨時(shí)整型數(shù)組，用來(lái)存儲(chǔ)各種字母出現(xiàn)的次數(shù)。應(yīng)為大寫字母的ASCII碼與整數(shù)1~26個(gè)元素之間相差64，因此在算法中使用字母減去64作為統(tǒng)計(jì)數(shù)組的下標(biāo)對(duì)號(hào)入座，無(wú)須循環(huán)判斷來(lái)實(shí)現(xiàn)，從而提高了效率；另外，要求出電文字符串中有多少種字符，并保存這些字符以供編碼時(shí)使用。統(tǒng)計(jì)和保存都比較容易，用一個(gè)循環(huán)來(lái)判斷先前統(tǒng)計(jì)好的各類字符個(gè)數(shù)的數(shù)組元素是否為零，若不為零，則將其值存入一個(gè)數(shù)組對(duì)應(yīng)的元素中，同時(shí)將其對(duì)應(yīng)的字符也存入另一個(gè)數(shù)組元素中。具體實(shí)現(xiàn)如下：intjsq(char*s,intcnt[],charstr[]){//統(tǒng)計(jì)各字符串中各種字母的個(gè)數(shù)以及字符的種類char*p;inti,j,k;inttemp[27];for(i=1;i<=26;i++)temp[i]=0;for(p=s;*p!='\0';p++){//統(tǒng)計(jì)各種字符個(gè)數(shù)if(*p>='A'&&*p<='Z'){k=*p-64;temp[k]++;}}j=0;for(i=1,j=0;i<=26;i++)//統(tǒng)計(jì)有多少種字符if(temp[i]!=0){j++;str[j]=i+64;//將對(duì)應(yīng)的數(shù)組送到數(shù)組中cnt[j]=temp[i];//存入對(duì)應(yīng)數(shù)組的權(quán)值}returnj;}4.1.3構(gòu)造赫夫曼樹voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]){//構(gòu)造赫夫曼樹HTinti,s1,s2;for(i=1;i<=2*num-1;i++)//初始化HT，左右孩子，雙親，權(quán)值都為0{HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;HT[i].weight=0;}for(i=1;i<=num;i++)//輸入num個(gè)葉節(jié)點(diǎn)的權(quán)值HT[i].weight=cnt[i];for(i=num+1;i<=2*num-1;i++)//從numd后面開始新建結(jié)點(diǎn)存放新生成的父節(jié)點(diǎn){select(HT,i-1,&s1,&s2);//在HT[1……i-1]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，其序號(hào)分別為s1和s2HT[s1].parent=i;HT[s2].parent=i;//將s1和s2的parent賦值HT[i].lchild=s1;HT[i].rchild=s2;//新結(jié)點(diǎn)的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight;//新結(jié)點(diǎn)的權(quán)值}for(i=0;i<=num;i++)//輸入字符集中的字符HC[i].ch=str[i];i=1;while(i<=num)printf("字符%c,次數(shù)為:%d\n",HC[i].ch,cnt[i++]);}4.2赫夫曼編碼要求電文的赫夫曼編碼，必須先定義赫夫曼編碼類型，根據(jù)設(shè)計(jì)要求和實(shí)際需要定義的類型如下：typedefstruct{charch;charbits[n+1];intstart;}CodeNode;typedefCodeNodeHuffmanCode[n];4.2.1赫夫曼編碼算法voidHuffmanEncoding(HuffmanTreeHT,HuffmanCodeHC){//根據(jù)赫夫曼樹HT求赫夫曼編碼表ＨＣintc,p,i;charcd[n];intstart;cd[num]='\0';for(i=1;i<=num;i++){start=num;c=i;while((p=HT[c].parent)>0)//直至上訴到ht[c]是樹根為止{//若HT[c]是HT[p]的孩子，則生成0；否則生成代碼1cd[--start]=(HT[p].lchild==c)?'0':'1':c=p;}//endofwhilestrcpy(HC[i].bits,&cd[start]);HC[i].len=num-start;}}4.2.2建立正文的編碼文件建立編碼文件的基本思想是：將要編碼的字符串中的字符逐一與預(yù)先生成赫夫曼樹時(shí)保保存的字符編碼對(duì)照表進(jìn)行比較，找到之后，對(duì)該字符的編碼寫入代碼文件，直至所有字符處理完畢為止。具體算法如下：viodcoding(huffmanCodeHC,char*str){inti,j;FILE*fp;fp=fopen(“codefile.tex”,”w”);while(*str){//對(duì)電文中字符逐一生成編碼并寫入文件for(i=1;i<=num;i++)if(HC[i].ch==*str){for(j=0;j<=HC[i].len;j++)fputc(HC[i].bits[j],fp);break;}str++;}fclose(fp);}4.3代碼文件的譯碼譯碼的基本思想是:讀文件中編碼，并與生成的赫夫曼編碼表比較，遇到相等時(shí)，即取出其對(duì)應(yīng)的字符存入一個(gè)新串中。Char*decode(HuffmanCodeHC){//代碼文件codefile.tex譯碼FILE*fp;charstr[254];char*p;staticcharcd[n+1]inti,j,k=0,cjs;fp=fopen(“codefile.tex”,”r”);while(!feof(fp)){cjs=0;for(i=0;i<=num&&cjs==0&&!feof(fp);i++){cd[i]=‘’；cd[i+1]='\0';cd[i]=fgetc(fp);for(j=1;j<=num;j++)if(strcmp(HC[i].bits,cd)==0){str[k]=HC[j].ch;k++;cjs=1;break;}}str[k]='\0';;p=str;returnp;}五、運(yùn)行與測(cè)試運(yùn)行結(jié)果為六、總結(jié)與心得本次編寫過(guò)程中出現(xiàn)了較多的問(wèn)題，比如開始對(duì)赫夫曼樹的理解不是很清楚，導(dǎo)致在編寫過(guò)程中某些代碼錯(cuò)誤而沒(méi)能及時(shí)修改，在最后進(jìn)行修改時(shí)遇到了較多的麻煩。但是經(jīng)過(guò)這次對(duì)赫夫曼樹的學(xué)習(xí)后，我了解到赫夫曼編碼(HuffmanCoding)是一種編碼方式，以赫夫曼樹—即最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)的無(wú)損耗壓縮?？傊芤娣藴\。參考文獻(xiàn)【1】《數(shù)據(jù)結(jié)構(gòu)》嚴(yán)蔚敏.清華大學(xué)出版社.【2】《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》蘇仕華.極械工業(yè)出版社.【3】《程序設(shè)計(jì)》譚浩強(qiáng).清華大學(xué)出版社.附錄#include<stdio.h>#include<string.h>#definen100//葉子結(jié)點(diǎn)數(shù)#definem2*n-1//赫夫曼樹種的結(jié)點(diǎn)總數(shù)typedefstruct{charch;charbits[9];//存放編碼位串intlen;//編碼長(zhǎng)度}CodeNode;typedefCodeNodeHuffmanCode[n+1];typedefstruct{intweight;//權(quán)值intlchild,rchild,parent;//左右孩子及雙親指針}HTNode;//樹中的結(jié)點(diǎn)類型typedefHTNodeHuffmanTree[m+1];//0號(hào)單元不可用intnum;//字母類型的個(gè)數(shù)voidselect(HuffmanTreeT,intk,int*s1,int*s2){//在HT[1……k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，其序號(hào)分別為S1和S2inti,j;intmin1=100;for(i=1;i<=k;i++)//查找s1if(T[i].weight<min1&&T[i].parent==0){j=i;min1=T[i].weight;}*s1=j;min1=32767;for(i=1;i<=k;i++)//查找s2,不和s1相同if(T[i].weight<min1&&T[i].parent==0&&i!=(*s1)){j=i;min1=T[i].weight;}*s2=j;}intjsq(char*s,intcnt[],charstr[]){//統(tǒng)計(jì)各字符串中各種字母的個(gè)數(shù)以及字符的種類char*p;inti,j,k;inttemp[27];for(i=1;i<=26;i++)temp[i]=0;for(p=s;*p!='\0';p++){//統(tǒng)計(jì)各種字符個(gè)數(shù)if(*p>='A'&&*p<='Z'){k=*p-64;temp[k]++;}}j=0;for(i=1,j=0;i<=26;i++)//統(tǒng)計(jì)有多少種字符if(temp[i]!=0){j++;str[j]=i+64;//將對(duì)應(yīng)的數(shù)組送到數(shù)組中cnt[j]=temp[i];//存入對(duì)應(yīng)數(shù)組的權(quán)值}returnj;}voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]){//構(gòu)造赫夫曼樹HTinti,s1,s2;for(i=1;i<=2*num-1;i++)//初始化HT，左右孩子，雙親，權(quán)值都為0{HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;HT[i].weight=0;}for(i=1;i<=num;i++)//輸入num個(gè)葉節(jié)點(diǎn)的權(quán)值HT[i].weight=cnt[i];for(i=num+1;i<=2*num-1;i++)//從numd后面開始新建結(jié)點(diǎn)存放新生成的父節(jié)點(diǎn){select(HT,i-1,&s1,&s2);//在HT[1……i-1]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，其序號(hào)分別為s1和s2HT[s1].parent=i;HT[s2].parent=i;//將s1和s2的parent賦值HT[i].lchild=s1;HT[i].rchild=s2;//新結(jié)點(diǎn)的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight;//新結(jié)點(diǎn)的權(quán)值}for(i=0;i<=num;i++)//輸入字符集中的字符HC[i].ch=str[i];i=1;while(i<=num)printf("字符%c,次數(shù)為:%d\n",HC[i].ch,cnt[i++]);}voidHuffmanEncoding(HuffmanTreeHT,HuffmanCodeHC){//根據(jù)赫夫曼樹HT求赫夫曼編碼表HCintc,p,i,j;//c和p分別指示T中孩子和雙親的位置charcd[n];//臨時(shí)存放編碼串intstart;//指示編碼在cd中的起始位置cd[num]='\0';//最后一位放上串結(jié)束符for(i=1;i<=num;i++){start=num;//初始位置c=i;//從葉子節(jié)點(diǎn)T[i]開始上溯while((p=HT[c].parent)>0)//直至上溯到HT[c]是樹根為止{//若T[c]是T[p]的做孩子，則生成0；否則生成代碼1cd[--start]=(HT[p].lchild==c)?'0':'1';//cd數(shù)組用來(lái)存放每一個(gè)字母對(duì)應(yīng)的01編碼，c=p;}//while結(jié)束strcpy(HC[i].bits,&cd[start]);//將cd數(shù)組中德01代碼復(fù)制到i結(jié)點(diǎn)中HC[i].len=num-start;}//for結(jié)束}voidcoding(HuffmanCodeHC,char*str){inti,j;FILE*fp;fp=fopen("codefile.txt","w");while(*str){for(i=1;i<=num;i++)if(HC[i].ch==*str){for(j=0;j<HC[i].len;j++){fputc(HC[i].bits[j],fp);}break;}str++;}fclose(fp);}char