赫夫曼樹課程設(shè)計

1、數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計名稱：赫夫曼樹的建立 專業(yè)班級：信息與計算科學2013級一班 姓名： 課題分工（概要設(shè)計，詳細方案與代碼設(shè) 計，調(diào)試與結(jié)果）（需求分析，調(diào)試與結(jié)果，改進方案） 課題組成人員： 指導(dǎo)教師： 完成日期：2015年6月25日一、摘要運用C語言編寫程序（工具VC+6.0），建立函數(shù)輸入二叉樹，并輸出赫夫曼樹，完成編碼。建立赫夫曼樹的過程，給定權(quán)值Wi（i=1，2，3，.）構(gòu)成左右子樹為空二叉樹集合，從集合中選取權(quán)值最小的樹構(gòu)成新的二叉樹，新二叉樹根結(jié)點的權(quán)值為其左右子樹權(quán)值之和，將新的二叉樹加入到集合中，如此重復(fù)，直到只有一棵樹（赫夫曼樹）。構(gòu)造好赫夫曼樹之后，從根到葉子結(jié)點的路徑及

2、為編碼。二、系統(tǒng)需求分析在信息傳遞時，希望總長度可能的短，及采用最短碼赫夫曼編碼的應(yīng)用，就是采用這種有效的數(shù)據(jù)壓縮技術(shù)可以節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間。建立最優(yōu)二叉樹函數(shù)，要求可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹以及赫夫曼編碼。三、系統(tǒng)概要設(shè)計1、存儲結(jié)構(gòu)：采用了數(shù)組和結(jié)構(gòu)體結(jié)合的存儲方式。以下是樹中結(jié)點的存儲結(jié)構(gòu)形式，其中包括了權(quán)值，左孩子，右孩子，父親這幾個結(jié)點。typedef struct unsigned int weight; /權(quán)值 unsigned int parent,lchild,rchild; HTNode；/ 動態(tài)分配數(shù)組存儲赫夫曼樹2、基本算法： （

3、1）流程圖： 開始 輸入葉子結(jié)點個數(shù) 輸入結(jié)點權(quán)值，m=2n-1 給結(jié)點1n和n+1m分別賦初值 構(gòu)建赫夫曼樹結(jié)束遍歷赫夫曼樹，求赫夫曼編碼輸出赫夫曼樹（2）下面的代碼是用來生成赫夫曼樹的，其中這個過程匯總了select方法來不斷尋找當前所有結(jié)點中權(quán)值最小的結(jié)點，然后生成新的結(jié)點，再生成相應(yīng)的樹。for(p=*HT+1,i=1;i=n;+i,+p,+w) (*p).weight=*w; (*p).parent=0; /給每個結(jié)點權(quán)值賦值(*p).lchild=0; (*p).rchild=0; /雙親，左右孩子賦初值 for(;i=m;+i,+p) (*p).parent=0; for(i=n

4、+1;i=m;+i) / 建赫夫曼樹 / 在HT1i-1中選擇parent為0且weight最小的兩個結(jié)點,其序號分別為s1和s2 select(*HT,i-1,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; 3、所有實現(xiàn)功能的函（1）int main() ：接收原始數(shù)據(jù)：從終端讀入整數(shù)集大小n，n個整數(shù)和n個權(quán)值，調(diào)用函數(shù)HuffmanCoding(&HT,&HC,w,n); ，以及輸出編碼。（

5、2）void select(HuffmanTree t,int i,int *s1,int *s2)：在所有的樹中，找到權(quán)值最小的兩個賦值給s1和s2,供HuffmanCoding使用。（3）int min1(HuffmanTree t,int i）：找最小權(quán)值。（4）void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n)：構(gòu)建赫夫曼樹輸出赫夫曼樹，以及遍歷赫夫曼樹求編碼。四、詳細方案設(shè)計開始創(chuàng)建赫夫曼樹：是結(jié)束(*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchi

6、ld=0; i=i+1否否是i=i+1i=m(*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight;i=ni=1初始化赫夫曼表且有m=2n-1結(jié)點開始赫夫曼編碼：遍歷赫夫曼樹求每個赫夫曼樹的編碼，i=1i=n(*HT)i.weight=0，結(jié)點狀態(tài)標志是是否是否結(jié)束此時編碼為1(*p).lchild=0; (*p).rchild=0; 右子是否空此時編碼為0左子是否空P權(quán)值是否為1p是否為空5、 代碼詳細設(shè)計1、 源代碼#in

7、clude #include / 赫夫曼樹和赫夫曼編碼的存儲表示typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode, *HuffmanTree; / 動態(tài)分配數(shù)組存儲赫夫曼樹typedef char *HuffmanCode; / 動態(tài)分配數(shù)組存儲赫夫曼編碼表/ 函數(shù)void select()調(diào)用int min1(HuffmanTree t,int i) int j,flag; unsigned int k=UINT_MAX; / 取k為不小于可能的值 for(j=1;j=i;j+) if(

8、tj.weight*s2) j=*s1;*s1=*s2; *s2=j; / 算法6.13 P148 / w存放n個字符的權(quán)值(均0),構(gòu)造赫夫曼樹HT,并求出n個字符的赫夫曼編碼HC void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) int m,i,s1,s2; unsigned c,cdlen; HuffmanTree p; char *cd; if(n=1) return; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0號單元未用for(p=*

9、HT+1,i=1;i=n;+i,+p,+w) (*p).weight=*w; /賦權(quán)值(*p).parent=0; /給雙親，左右孩子賦初值(*p).lchild=0; (*p).rchild=0; for(;i=m;+i,+p) (*p).parent=0; for(i=n+1;i=m;+i) / 建赫夫曼樹 / 在HT1i-1中選擇parent為0且weight最小的兩個結(jié)點,其序號分別 為s1和s2 select(*HT,i-1,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (

10、*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; printf(赫夫曼樹為：n); printf(元素權(quán)值父結(jié)點 左孩子 右孩子n); for(i=1;i=2*n-1;i+) printf(%5d %5d %5d %5dn,(*HT)i.weight,(*HT)i.parent,(*HT)i.lchild,(*HT)i.rchild); / 以下為算法6.13，無棧非遞歸遍歷赫夫曼樹,求赫夫曼編碼，以上同算法6.12 *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); / 分配n個字符編碼的頭指針向量(0不用) cd=(

11、char*)malloc(n*sizeof(char); / 分配求編碼的工作空間 c=m; cdlen=0; for(i=1;i1)：); scanf(%d,&n); w=(int *)malloc(n*sizeof(int); printf(請依次輸入%d個權(quán)值(整型)：n,n); for(i=0;i=n-1;i+) scanf(%d,w+i); HuffmanCoding(&HT,&HC,w,n); printf(赫夫曼編碼： n);for(i=1;i=n;i+) puts(HCi); system(pause); return 0; 6、 測試與調(diào)試結(jié)果7、 分析與改進此算法的時間復(fù)雜度為O(n2)。由實驗結(jié)果知道，建立赫夫曼樹，