試驗四二叉樹的應(yīng)用-哈夫曼編碼試驗報告

1、哈夫曼編碼實驗四 二叉樹的應(yīng)用-哈夫曼編碼一、實驗?zāi)康?. 在二叉樹基本操作的基礎(chǔ)上，掌握對二叉樹的一些其它操作的具體實現(xiàn)方法。2. 掌握構(gòu)造哈夫曼樹以及哈夫曼編碼的方法。、實驗內(nèi)容哈夫曼樹和哈夫曼編碼：從終端輸入若干個字符，統(tǒng)計字符出現(xiàn)的頻率，將字符出現(xiàn)的頻率作為結(jié)點的 權(quán)值，建立哈夫曼樹，然后對各字符進(jìn)行哈夫曼編碼。最后打印哈夫曼樹和對應(yīng)的 哈夫曼編碼。設(shè)計要求： 哈夫曼殊和哈夫曼編碼的存儲表示參考教材事例 在程序中構(gòu)造四個子程序為 int freqchar (char *text, HTree *t) /*統(tǒng)計字符出現(xiàn)的頻率 */ int createhtree(HTree *t) /*

2、 根據(jù)字符出現(xiàn)的頻率建立哈夫曼樹 */ void codi ng(HTree *t, int head_i,char *code)/*對哈夫曼樹進(jìn)行編碼*/ void printhtree(HTree *t,int head_i,int deep,int* path)/*中序打印樹*/三、實驗步驟、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計描述# in clude <stdio.h># in clude <malloc.h># in clude <iostream.h># in clude vconi o.h># in clude <stri ng.h>#

3、defi ne MAX_LENGTH 100typedef char *Huffma nCode;typedef struct/defi ne structure Huffma nTreeun sig ned int weight;un sig ned int pare nt,lchild,rchild;HTNode,*Huffma nTree;總5頁第6頁、函數(shù)調(diào)用及主函數(shù)設(shè)計程序調(diào)試及運行結(jié)果分析h hh 弋_ 口 t t t 12 3 I1AI1AI1AI1A 請請請請.fflftTEll.weight-854T2 J.weight-26 T3 J.weight=35I立的哈夫曼樹如下列

4、次序；Tt2 and HT(3 create HT4, weight=61 T【4J and HTtl create HTESJ, weiQht=915合夫曼編碼如下:TE1JTL2TE3Jress0 1 i 0 0 #=!;喚 分fdpfdp i TflTflTfl t fi.fifin 昌ss文 c刼 D UMIMIS t 哈哈哈y 溝也自e 點點點y "pfJiTan實驗總結(jié)哈弗曼編碼輸入抽象數(shù)據(jù)類型，不易掌握，需要慢慢修改。 四、主要算法流程圖及程序清單1、主要算法流程圖：void Select(HuffmanTree HT,int i,int &s1,int &am

5、p;s2)void Huffma nCodi ng(Huffma nTree &H T,Huffma nCode&HC,i nt *w,i nt n)2 、程序清單哈夫曼轉(zhuǎn)化函數(shù)：void Select(Huffma nTree HT,i nt i,i nt & s1,i nt & s2)int j,k=1;while(HTk.pare nt!=O)k+;s仁k;for(j=1;j<=i;+j)if(HTj.pare nt=O&&HTj.weight<HTs1.weight) s1=j;k=1;while(HTk.pare nt!=O

6、|k=s1)k+;s2=k;for(j=1;j<=i;+j)if(HTj.pare nt=O&&H Tj.weight<HTs2.weight&&j!=s1) s2=j;void Huffma nCodi ng(Huffma nTree &H T,Huffma nCode&HC,i nt *w,i nt n)int m,i,s1,s2,start,c,f;Huffma nTree p;if(*=1)return;m=2* n-1;HT=(Huffma nTree)malloc(m+1)*sizeof(HTNode);for(p=HT+

7、1,i=1;i<=n;+i,+p,+w)p->weight=*w;cout«e ndlvv"HT"vvivv".weight="vvp->weight<v""p->pare nt=0;p->lchild=0;初始化哈夫曼樹p->rchild=0;for(;i<=m;+i,+p)/in itial HT n+1.2* n1p->weight=0;p->pare nt=0;p->lchild=0;p->rchild=0;coutvvendlvvendlvv&

8、quot;建立的哈夫曼樹如下列次序："；for(i=n+1;i<=m;+i)Select(HT,i-1,s1,s2);s1 is the least, s2 is the seco nd leastHTs1.pare nt=i; HTs2.pare nt=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;cout«e ndlvv"HT"vvs1<v" a nd HT"<<s2<<" create" c

9、out«" HT"<<i<<", weight="«HTi.weight;HC=(Huffma nCode)malloc( n+1)*sizeof(char *);char *cd;cd=(char *)malloc( n*sizeof(char);cd n-1='0'cout«endl«endlvv"哈夫曼編碼如下:"<<endl;for(i=1;i<=n;+i)start=n-1;for(c=i,f=HTi.pare nt;f!=0;

10、c=f,f=HTf.pare nt)if(HTf.lchild=c)cd-start='0'elsecd-start='1'HCi=(char*)malloc( n-start)*sizeof(char);strcpy(HCi, &cdstart);printf("nHT%d節(jié)點的哈夫曼編碼是：s",i,HCi);coutvve ndl;free(cd);主函數(shù)：void mai n()/ma in() fun ctio nHuffma nTree HT;Huffma nCode HC;int n,i;int *w,WMAX_LENGTH;coutvv"請輸入哈夫曼樹的元素個數(shù)："；cin>&