佛山科學(xué)技術(shù)學(xué)院實(shí)驗(yàn)報告課程名稱 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)項(xiàng)目 用Huffman樹進(jìn)行編碼與解碼算法專業(yè)班級姓名學(xué)號指導(dǎo)教師 肖祥慧成績?nèi)掌?012/10/30一、 實(shí)驗(yàn)?zāi)康模?、 通過本實(shí)驗(yàn)，熟悉二叉樹、Huffman樹的概念，掌握二叉樹的儲存結(jié)構(gòu)及各種算法。2、 熟悉用Huffman樹進(jìn)行電文的加密與解密算法。二、 實(shí)驗(yàn)內(nèi)容；1、 Huffman樹的儲存方式2、 加密與解密算法在電文編碼中的應(yīng)用三、 實(shí)驗(yàn)原理；給定n個權(quán)值作為n個葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹。Huffman樹是一種特殊的二叉樹，其葉結(jié)點(diǎn)的編碼是一種前綴碼，同時，通過統(tǒng)計(jì)字符的頻度，能夠達(dá)到編碼電文的最小化。假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點(diǎn)。N個權(quán)值分別設(shè)為w1、w2、...，wn，則哈夫曼樹的構(gòu)造規(guī)則為：（1） 將w1、w2、...，wn看成是有n棵樹的森林（每棵樹僅有一個結(jié)點(diǎn)）；（2） 在森林中選出兩個根結(jié)點(diǎn)的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；（3） 從森林中刪除選取得兩棵樹，并將新樹加入森林；（4） 重復(fù)（2）、（3）步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。四、 實(shí)驗(yàn)步驟1、根據(jù)二叉樹程序的學(xué)習(xí)，完成Huffman樹的構(gòu)造、編碼和解碼的實(shí)現(xiàn)。（1） 統(tǒng)計(jì)電文中字符的出現(xiàn)頻率。（2） 用統(tǒng)計(jì)頻率建立Huffman樹，并生成前綴碼；（3） 建立Huffman樹的解碼算法。用隨機(jī)輸入的電文完成編碼與解碼過程。五、程序源代碼及注釋#include<stdio.h>#include<stdlib.h>#include<string.h>#defineN100#defineM2*N-1typedefstruct{intweight;〃權(quán)值intparent; //父母節(jié)點(diǎn)intlchild; //左子結(jié)點(diǎn)intrchild; //右子結(jié)點(diǎn)}HTNode,Huffman[M+1]; 〃哈夫曼樹的存儲表示typedefchar*HuffmanCode[2*M]; 〃哈夫曼樹的編碼typedefstructNode{intweight;〃葉子節(jié)點(diǎn)的權(quán)值charc; 〃葉子節(jié)點(diǎn)intnum; 〃葉子節(jié)點(diǎn)的二進(jìn)制碼的長度}WNode,WeightNode[N];/*****產(chǎn)生葉子節(jié)點(diǎn)的字符和權(quán)值*****/voidCreateWeight(charch[],int*s,WeightNodeCW,int*p){ 〃統(tǒng)計(jì)字符出現(xiàn)個數(shù)，放入CWinti,j,k;inttag;*p=0; 〃葉子節(jié)點(diǎn)個數(shù)for(i=0;ch[i]!='\0';i++){tag=1;for(j=0;j<i;j++)if(ch[j]==ch[i])tag=0;break;if(tag)CW[++*p].c=ch[i];CW[*p].weight=1;for(k=i+1;ch[k]!='\0';k++)if(ch[i]==ch[k])*s=i; 〃字符串長度/*******創(chuàng)建HuffmanTree*******/voidCreateHuffmanTree(HuffmanHT,WeightNodew,intn){ //初始化哈夫曼樹inti,j;ints1,s2;for(i=1;i<=n;i++)HT[i].weight=w[i].weight;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;for(i=n+1;i<=2*n-1;i++)HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;for(i=n+1;i<=2*n-1;i++)for(j=1;j<=i-1;j++)if(!HT[j].parent)break;s1=j; //找到第一個雙親不為零的結(jié)點(diǎn)for(;j<=i-1;j++)if(!HT[j].parent)s1=HT[s1].weight>HT[j].weight?j:s1;HT[s1].parent=i;HT[i].lchild=s1;for(j=1;j<=i-1;j++)if(!HT[j].parent)break;s2=j;for(;j<=i-1;j++)if(!HT[j].parent)s2=HT[s2].weight>HT[j].weight?j:s2;HT[s2].parent=i;HT[i].rchild=s2;}} HT"w—/************葉子節(jié)點(diǎn)的編碼************/voidCrtHuffmanNodeCode(HuffmanHT,charch[],HuffmanCodeH,WeightNodeweight,intm,intn){inti,c,f,start;char*cd;cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0'; 〃編碼結(jié)束符for(i=1;i<=n;++i){start=n-1; 〃編碼結(jié)束符的位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)〃從葉子到根逆向求編碼if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';weight[i].num=n-start;〃二進(jìn)制碼的長度(包含末尾0)H[i]=(char*)malloc((n-start)*sizeof(char));〃為第i個字符編碼分配空間strcpy(H[i],&cd[start]);〃從cd復(fù)制編碼到HC}free(cd);〃釋放cd內(nèi)存}/*********所有字符的編碼*********/voidCrtHuffmanCode(charch[],HuffmanCodeh,HuffmanCodehc,WeightNodeweight,intn,intm){inti,k;for(i=0;i<m;i++){for(k=1;k<=n;k++) 〃從weight[k].c中查找與ch[i]相等的下標(biāo)Kif(ch[i]==weight[k].c)break;hc[i]=(char*)malloc((weight[k].num)*sizeof(char));strcpy(hc[i],h[k]); //拷貝二進(jìn)制編碼}}/*******解碼*******/voidTrsHuffmanTree(HuffmanHT,WeightNodew,HuffmanCodeHC,intn,intm)inti=0,j,p;printf("\n打印原文信息：\n");while(i<m)p=2*n-1; 〃從父親結(jié)點(diǎn)向下遍歷直到葉子節(jié)點(diǎn)for(j=0;HC[i][j]!='\0';j++)if(HC[i][j]='0')p=HT[p].lchild;elsep=HT[p].rchild;}printf("%c”,w[p].c);〃打印原信息i++;}}voidmain(){inti,n=0;//n為葉子結(jié)點(diǎn)的個數(shù)intm=0;//m為字符串ch[]的長度charch[N];//ch[N]存放輸入的字符串HuffmanHT;〃哈夫曼樹HuffmanCodeH,HC; //H存放葉子結(jié)點(diǎn)的編碼，HC存放所有節(jié)點(diǎn)的編碼WeightNodeweight; //存放葉子結(jié)點(diǎn)的信息printf("************哈夫曼樹************\n");printf("請輸入信息：\n");gets(ch); 〃輸入字符串CreateWeight(ch,&m,weight,&n); 〃產(chǎn)生葉子結(jié)點(diǎn)信息，m為字符串ch[]的長度printf("葉子節(jié)點(diǎn)信息：\nNode");for(i=1;i<=n;i++) 〃輸出葉子結(jié)點(diǎn)的字符和權(quán)值printf("%c",weight[i].c);printf("\n權(quán)值：”)；for(i=1;i<=n;i++)printf("%d",weight[i].weight);CreateHuffmanTree(HT,weight,n); 〃產(chǎn)生哈夫曼樹printf("\n******哈夫曼樹信息********\n");printf("\ti\tweight\tparent\tlchild\trchild\n");for(i=1;i<=2*n-1;i++) 〃打印哈夫曼樹的信息printf("\t%d\t%d\t%d\t%d\t%d\n”,i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);CrtHuffmanNodeCode(HT,ch,H,weight,m,n);〃葉子結(jié)點(diǎn)的編碼printf("葉子結(jié)點(diǎn)編碼：\n"); 〃打印葉子結(jié)點(diǎn)的編碼for(i=1;i<=n;i++){printf("\t%c:",weight[i].c);printf("%s\n",H[i]);}CrtHuffmanCode(ch,H,HC,weight,n,m); //所有字符的編碼printf("打印字符串編碼：\n");for(i=0;i<m;i++)printf("%s",HC[i]);//解碼//解碼