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

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

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

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

5、是哈夫曼樹?！驹敿氃O計】具體代碼實現如下： #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); 【運行結果】截圖一 【心得體會】本實驗是有老師提供模板，然后自己增加功能函數的代碼實現的。因此，在完成未完成的功能函數之前還必須要細心閱讀所給出代碼，整體觀察各個部分之前的聯系，搞清楚已給出和未完成的代碼功能之后，才根據算法，設計出該功能的函數代碼。在實驗過程中，大大小小的問題是難免的，有些解決不了的，就問了這方面比較擅長的同學，也在網上進行了提問，通過大家的幫忙克服了不少的問題，小問題都是馬虎造成的，都要進行反復地