哈弗曼樹的建立_編碼和譯碼操作

1、 北京工商大學(xué)課程設(shè)計(jì)報(bào)告 編號(hào)：北京工商大學(xué)_數(shù)據(jù)結(jié)構(gòu)_課程設(shè)計(jì)(報(bào)告)院 （系）:_ _班 級(jí):_ _學(xué) 號(hào):_ _姓 名:_ _同組學(xué)生：_指導(dǎo)教師_成 績(jī)_實(shí)踐地點(diǎn)：_實(shí)踐時(shí)間： Huffman樹的建立及編碼【課程設(shè)計(jì)目的】 通過(guò)對(duì)哈夫曼樹的概念、構(gòu)造算法的理解，進(jìn)行編碼，從而掌握赫夫曼樹的編碼原則。 【課程設(shè)計(jì)任務(wù)】霍夫曼（Huffman）編碼原理是一種利用二叉樹實(shí)現(xiàn)的編碼原理霍夫曼（Huffman）編碼是1952年為文本文件而建立，是一種統(tǒng)計(jì)編碼。屬于無(wú)損壓縮編碼。 霍夫曼編碼的碼長(zhǎng)是變化的，對(duì)于出現(xiàn)頻率高的信息，編碼的長(zhǎng)度較短；而對(duì)于出現(xiàn)頻率低的信息，編碼長(zhǎng)度較長(zhǎng)。這樣，處理全部

2、信息的總碼長(zhǎng)一定小于實(shí)際信息的符號(hào)長(zhǎng)度。霍夫曼編碼具有一些明顯的特點(diǎn)： 1) 編出來(lái)的碼都是異字頭碼，保證了碼的唯一可譯性。 2) 由于編碼長(zhǎng)度可變。因此譯碼時(shí)間較長(zhǎng)，使得霍夫曼編碼的壓縮與還原相當(dāng)費(fèi)時(shí)。 3) 編碼長(zhǎng)度不統(tǒng)一，硬件實(shí)現(xiàn)有難度。 4) 對(duì)不同信號(hào)源的編碼效率不同，當(dāng)信號(hào)源的符號(hào)概率為2的負(fù)冪次方時(shí)，達(dá)到100的編碼效率；若信號(hào)源符號(hào)的概率相等，則編碼效率最低。 5) 由于"0"與"1"的指定是任意的，故由上述過(guò)程編出的最佳碼不是唯一的，但其平均碼長(zhǎng)是一樣的，故不影響編碼效率與數(shù)據(jù)壓縮性能輸入:從終端讀入字符集大小n,以及n個(gè)字符和n個(gè)權(quán)值

3、,建立哈弗曼樹.輸出:從終端讀入的字符集最終輸出編譯后的哈弗曼編碼,字符集形式輸出.【設(shè)計(jì)思路】 （1） 定義哈弗曼樹的結(jié)點(diǎn)結(jié)構(gòu)；（2）定義哈弗曼編碼的結(jié)構(gòu).；（3）構(gòu)造哈弗曼樹；（4）構(gòu)造n棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹，并找出根結(jié)點(diǎn)權(quán)值最小的兩棵樹；（5）輸出字符的哈弗曼編碼?！靖乓O(shè)計(jì) (流程)】1程序用到的抽象數(shù)據(jù)類型的定義:typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;2主模塊的流程以及各子模塊的主要功能:主main函數(shù)調(diào)用了HuffmanTree HT函

4、數(shù), HuffmanCode HC=NULL;函數(shù),HuffmanCoding(HT,HC,w,n);函數(shù),最終實(shí)現(xiàn)編譯功能.【構(gòu)造哈夫曼樹的算法】 （1）根據(jù)與n個(gè)權(quán)值W1,W2,Wn對(duì)應(yīng)的n個(gè)結(jié)點(diǎn) 構(gòu)成具有n棵二叉樹的森 林。F=T1，T2，,Tn其中,每棵二叉樹Ti(1<=i<=n)都只有一個(gè)權(quán)值為Wi的根結(jié) 點(diǎn)，其左、右子樹均為空；（2）在森林F中選出兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為一棵新樹的左、右子樹，且置新樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根 結(jié)點(diǎn)的權(quán)值之和；（3）從F中刪除構(gòu)成新樹的那兩棵樹，同時(shí)把新樹加入F中；（4）重復(fù)（2）和（3）步，直到F中只含有一棵樹為 止，此樹便

5、是哈夫曼樹。【詳細(xì)設(shè)計(jì)】具體代碼實(shí)現(xiàn)如下： #include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char *HuffmanCode; typedef struct unsigned int s1; unsigned int s2; MinCode; void Error(char *message

6、); void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,unsigned int *w,unsigned int n); MinCode Select(HuffmanTree HT,unsigned int n); void Error(char *message) fprintf(stderr,"Error:%sn",message); exit(1); void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,unsigned int *w,u

7、nsigned int n)unsigned int i,s1=0,s2=0; HuffmanTree p; char *cd; unsigned int f,c,start,m; MinCode min; if(n<=1) Error("Code too small!"); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT,i=0;i<=n;i+,p+,w+) p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0;

8、 for(;i<=m;i+,p+) p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; for(i=n+1;i<=m;i+) min=Select(HT,i-1); s1=min.s1; s2=min.s2; HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; printf("HT List:n"); printf("Numberttwei

9、ghtttparentttlchildttrchildn"); for(i=1;i<=m;i+) printf("%dtt%dtt%dtt%dtt%dn",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd=(char *)malloc(n*sizeof(char *); cdn-1='0' for(i=1;i<=n;i+) start=n-1; for(c=i,f=HTi.parent;f!=0;c

10、=f,f=HTf.parent) if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char *)malloc(n-start)*sizeof(char *); strcpy(HCi,&cdstart); free(cd); MinCode Select(HuffmanTree HT,unsigned int n) unsigned int min,secmin; unsigned int temp; unsigned int i,s1,s2,tempi; MinCode code; s1=1;s2

11、=1; for(i=1;i<=n;i+) if(HTi.parent=0)min=HTi.weight; s1=i; break; tempi=i+; for(;i<=n;i+) if(HTi.weight<min&&HTi.parent=0) min=HTi.weight; s1=i; for(i=tempi;i<=n;i+) if(HTi.parent=0&&i!=s1) secmin=HTi.weight; s2=i; break; for(i=1;i<=n;i+) if(HTi.weight<secmin&&a

12、mp;i!=s1&&HTi.parent=0) secmin=HTi.weight; s2=i; if(s1>s2) temp=s1; s1=s2; s2=temp; code.s1=s1; code.s2=s2; return code; void main() HuffmanTree HT=NULL; HuffmanCode HC=NULL; unsigned int *w=NULL; unsigned int i,n; printf("Input n:n"); scanf("%d",&n); w=(unsigned i

13、nt *)malloc(n+1)*sizeof(unsigned int *); w0=0; printf("Enter weight:n"); for(i=1;i<=n;i+) printf("w%d=",i); scanf("%d",&wi); HuffmanCoding(HT,HC,w,n); printf("HuffmanCode:n"); printf("NumberttWeightttCoden"); for(i=1;i<=n;i+) printf("%dtt%dtt%sn",i,wi,HCi); 【運(yùn)行結(jié)果】截圖一 【心得體會(huì)】本實(shí)驗(yàn)是有老師提供模板，然后自己增加功能函數(shù)的代碼實(shí)現(xiàn)的。因此，在完成未完成的功能函數(shù)之前還必須要細(xì)心閱讀所給出代碼，整體觀察各個(gè)部分之前的聯(lián)系，搞清楚已給出和未完成的代碼功能之后，才根據(jù)算法，設(shè)計(jì)出該功能的函數(shù)代碼。在實(shí)驗(yàn)過(guò)程中，大大小小的問(wèn)題是難免的，有些解決不了的，就問(wèn)了這方面比較擅長(zhǎng)的同學(xué)，也在網(wǎng)上進(jìn)行了提問(wèn)，通過(guò)大家的幫忙克服了不少的問(wèn)題，小問(wèn)題都是馬虎造成的，都要進(jìn)行反復(fù)地