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

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

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

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

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

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

7、;/用于得到parent為0的兩個最小的puts("請輸入葉子節點的個數");scanf("%d",&n);for(i=0;i<2*n-1;i+)treei.parent=-1;treei.lchild=-1;treei.rchild=-1;puts("請輸入哈夫曼樹的權值");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;/求樹的帶權路徑長度 treei.lchild=p1; treei.rchild=p2;printf("輸出該哈夫曼樹的各個結點的值為：n");printf(" weight parent lchild rchildn");for(i=0;i<2*n-1;i+)printf("%d %4.