精品資料（2021-2022年收藏）課程設(shè)計報告5

1、合肥學(xué)院計算機科學(xué)與技術(shù)系課程設(shè)計報告20132014學(xué)年第二學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計名稱哈弗曼算法專業(yè)班級12級軟件工程指導(dǎo)教師李紅2014年9月題目：設(shè)計程序以實現(xiàn)構(gòu)造哈夫曼樹的哈夫曼算法。要求：求解所構(gòu)造的哈夫曼樹的帶全路徑長度。一、問題分析和任務(wù)定義根據(jù)要求需要：1、規(guī)劃哈夫曼樹的數(shù)據(jù)類型； 2、完成對哈夫曼樹的輸入； 3、構(gòu)造出哈夫曼樹； 4、求出哈夫曼樹的帶權(quán)路徑長度； 5、輸出哈夫曼樹的結(jié)點信息。二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計數(shù)據(jù)結(jié)構(gòu)的選擇：1. 由于一棵有n個葉子結(jié)點的哈夫曼樹上共有2n-1個結(jié)點，可以采用為2n-1的數(shù)組順序存儲結(jié)點信息。每個結(jié)點包括四個域：一個float

2、類型的weight用來存儲每個葉子結(jié)點的權(quán)值，三個int 類型的parent,rchild,lchild用來表示結(jié)點的父節(jié)點和左右孩子；結(jié)點的類型描述為：typedef struct float weight;int parent,lchild,rchild;hufm;若給定n個權(quán)值，則可定義數(shù)組tree來存儲哈夫曼樹上的結(jié)點：Hufm tree2n-1；為實現(xiàn)上述功能需要：1. 首先給定n個葉子結(jié)點的權(quán)值，構(gòu)造n棵單結(jié)點二叉樹；2. 在上面的二叉樹中選擇兩個權(quán)值最小的結(jié)點，分別為左右孩子構(gòu)造一棵新的二叉樹且新的二叉樹根結(jié)點的權(quán)值為其左右子樹根結(jié)點的權(quán)值之和。3. 然后刪除掉被選取的兩棵二叉樹

3、，并將新的二叉樹加入。4. 重復(fù)2,3兩步，直到只剩一顆二叉樹為止。5. 由于哈夫曼樹的帶權(quán)路徑長度就是等于所有非葉子結(jié)點值的和，因為樹的帶權(quán)路徑長度是通過將所有葉子結(jié)點乘以對應(yīng)的路徑長度之和求出來的，而將所有的非葉子結(jié)點的累加過程就是包括了上述的計算，所以直接就可以計算出。三、詳細設(shè)計和編碼 1、程序先輸入一個int的n表示共有n個葉子結(jié)點，然后輸入n個葉子結(jié)點的權(quán)值；同時將數(shù)組內(nèi)的所有值都初始化為-1； 2、根據(jù)概要設(shè)計的方法來構(gòu)造哈夫曼樹，將新的父節(jié)點放在數(shù)組下標(biāo)為n到2n-2中，所以進行一個外層循環(huán)，為確保每次能夠找到未含有父結(jié)點的權(quán)值最小的兩個結(jié)點，需要定義兩個整型的數(shù)，small1

4、,small2，在每次比較之前將一個最大值賦給它們，然后進行比較，在一個內(nèi)層的循環(huán)進行，如果找到一個比small1小的結(jié)點，就先把small1賦給small2然后，在將這個結(jié)點的權(quán)值賦給small1，同時類似的用兩個整型的數(shù)記錄這個結(jié)點的下標(biāo)；然后再每次內(nèi)層循環(huán)結(jié)束后，將這兩個葉子結(jié)點的parent值改為這個父節(jié)點的下標(biāo)，將父節(jié)點的左右孩子域改為兩個孩子結(jié)點的下標(biāo)，將父節(jié)點的權(quán)值weight變成兩個孩子的權(quán)值之和。 3、定義一個float類型的sum，初始化為0，然后在每次產(chǎn)生新結(jié)點的權(quán)值時，就將其累加，其為哈夫曼樹的帶權(quán)路徑長度。 4、最后將構(gòu)造好的哈夫曼樹輸出在屏幕上，并且輸出帶權(quán)路徑長度

5、。四、上機調(diào)試過程開始由于沒有想到求帶權(quán)路徑長度可以通過上述方法進行，所有還需要在樹建好以后進行每個葉子結(jié)點求其路徑長度，這大大的增加了程序的時間復(fù)雜性，最后將其改進。五、測試結(jié)果及其分析程序的一開始是將結(jié)構(gòu)體中的元素都初始化為0，但是由于為了更加清晰的表示出構(gòu)造哈弗曼樹的各個結(jié)點關(guān)系，防止與數(shù)組下標(biāo)為0的進行混淆，將其初始化為-1。圖中清晰的表示出了各個結(jié)點的信息，其中數(shù)組下標(biāo)為0n的為葉子結(jié)點，其lchild與rchild都是-1；weight記錄各個結(jié)點的權(quán)值，parent中的數(shù)字為每個結(jié)點的父節(jié)點所在的元素下標(biāo)，lchild與rchild分別為其左右孩子的下標(biāo)。六、用戶使用說明 根據(jù)屏

6、幕中的提示，先輸入葉子結(jié)點的個數(shù)，然后輸入n個葉子結(jié)點的權(quán)值，其可以為實數(shù)，然后回車就可以看到結(jié)果了。七、參考文獻1 王昆侖，李紅. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京：中國鐵道出版社，2006年5月。2 其它。八、附錄#include "stdio.h"#define max 100.0typedef struct float weight;int parent,lchild,rchild;hufm;int main()/p1,p2分別記錄相加后節(jié)點的兩個孩子的位置int n,i,j,p1,p2;float sum=0;hufm tree100;float small1,small2

7、;/用于得到parent為0的兩個最小的puts("請輸入葉子節(jié)點的個數(shù)");scanf("%d",&n);for(i=0;i<2*n-1;i+)treei.parent=-1;treei.lchild=-1;treei.rchild=-1;puts("請輸入哈夫曼樹的權(quán)值");for(i=0;i<n;i+)scanf("%f",&treei.weight);for(i=n;i<2*n-1;i+)p1=p2=0;small1=small2=max;for(j=0;j<=i-1

8、;j+)if(treej.parent=-1) if(treej.weight<small1) small2=small1; small1=treej.weight; p2=p1;p1=j; else if(treej.weight<small2) small2=treej.weight; p2=j; treep1.parent=treep2.parent=i; treei.weight=treep1.weight+treep2.weight; sum+=treei.weight;/求樹的帶權(quán)路徑長度 treei.lchild=p1; treei.rchild=p2;printf("輸出該哈夫曼樹的各個結(jié)點的值為：n");printf(" weight parent lchild rchildn");for(i=0;i<2*n-1;i+)printf("%d %4.