精品資料（2021-2022年收藏）課程設(shè)計(jì)報(bào)告(3)

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

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

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

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

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

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

7、為0的兩個(gè)最小的puts(請(qǐng)輸入葉子節(jié)點(diǎn)的個(gè)數(shù));scanf(%d,&n);for(i=0;i2*n-1;i+)treei.parent=-1;treei.lchild=-1;treei.rchild=-1;puts(請(qǐng)輸入哈夫曼樹(shù)的權(quán)值);for(i=0;in;i+)scanf(%f,&treei.weight);for(i=n;i2*n-1;i+)p1=p2=0;small1=small2=max;for(j=0;j=i-1;j+)if(treej.parent=-1) if(treej.weightsmall1) small2=small1; small1=treej.weight; p2=p1;p1=j; else if(treej.weightsmall2) small2=treej.weight; p2=j; treep1.parent=treep2.parent=i; treei.weight=treep1.weight+treep2.weight; sum+=treei.weight;/求樹(shù)的帶權(quán)路徑長(zhǎng)度 treei.lchild=p1; treei.rchild=p2;printf(輸出該哈夫曼樹(shù)的各個(gè)結(jié)點(diǎn)的值為：n);printf( weight parent lchild rchildn);for(i=0;i2*n-1;i+)pr