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

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

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

3、1）流程圖： 開始 輸入葉子結(jié)點(diǎn)個(gè)數(shù) 輸入結(jié)點(diǎn)權(quán)值，m=2n-1 給結(jié)點(diǎn)1n和n+1m分別賦初值 構(gòu)建赫夫曼樹結(jié)束遍歷赫夫曼樹，求赫夫曼編碼輸出赫夫曼樹（2）下面的代碼是用來(lái)生成赫夫曼樹的，其中這個(gè)過(guò)程匯總了select方法來(lái)不斷尋找當(dāng)前所有結(jié)點(diǎn)中權(quán)值最小的結(jié)點(diǎn)，然后生成新的結(jié)點(diǎn)，再生成相應(yīng)的樹。for(p=*HT+1,i=1;i=n;+i,+p,+w) (*p).weight=*w; (*p).parent=0; /給每個(gè)結(jié)點(diǎn)權(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最小的兩個(gè)結(jié)點(diǎn),其序號(hào)分別為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、所有實(shí)現(xiàn)功能的函（1）int main() ：接收原始數(shù)據(jù)：從終端讀入整數(shù)集大小n，n個(gè)整數(shù)和n個(gè)權(quán)值，調(diào)用函數(shù)HuffmanCoding(&HT,&HC,w,n); ，以及輸出編碼。（

5、2）void select(HuffmanTree t,int i,int *s1,int *s2)：在所有的樹中，找到權(quán)值最小的兩個(gè)賦值給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)建赫夫曼樹輸出赫夫曼樹，以及遍歷赫夫曼樹求編碼。四、詳細(xì)方案設(shè)計(jì)開始創(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é)點(diǎn)開始赫夫曼編碼：遍歷赫夫曼樹求每個(gè)赫夫曼樹的編碼，i=1i=n(*HT)i.weight=0，結(jié)點(diǎn)狀態(tài)標(biāo)志是是否是否結(jié)束此時(shí)編碼為1(*p).lchild=0; (*p).rchild=0; 右子是否空此時(shí)編碼為0左子是否空P權(quán)值是否為1p是否為空5、 代碼詳細(xì)設(shè)計(jì)1、 源代碼#in

7、clude #include / 赫夫曼樹和赫夫曼編碼的存儲(chǔ)表示typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode, *HuffmanTree; / 動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹typedef char *HuffmanCode; / 動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表/ 函數(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個(gè)字符的權(quán)值(均0),構(gòu)造赫夫曼樹HT,并求出n個(gè)字符的赫夫曼編碼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號(hào)單元未用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最小的兩個(gè)結(jié)點(diǎn),其序號(hào)分別 為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é)點(diǎn) 左孩子 右孩子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，無(wú)棧非遞歸遍歷赫夫曼樹,求赫夫曼編碼，以上同算法6.12 *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); / 分配n個(gè)字符編碼的頭指針向量(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(請(qǐng)依次輸入%d個(gè)權(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、 測(cè)試與調(diào)試結(jié)果7、 分析與改進(jìn)此算法的時(shí)間復(fù)雜度為O(n2)。由實(shí)驗(yàn)結(jié)果知道，建立赫夫曼樹，