赫夫曼樹數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

赫夫曼樹的建立設(shè)計目的本課程設(shè)計是為了配合《數(shù)據(jù)結(jié)構(gòu)》課程的開設(shè)，通過設(shè)計一完整的程序，使學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫、類C語言的算法轉(zhuǎn)換成C程序并用TC上機調(diào)試的基本方法。建立函數(shù)輸入一個二叉樹的結(jié)點個數(shù)及其所對應(yīng)的權(quán)值，建立其對應(yīng)的赫夫曼樹，并輸出其對應(yīng)的赫夫曼編碼。通過設(shè)計程序，了解并掌握赫夫曼樹的各種性質(zhì)及其存儲結(jié)構(gòu)，學(xué)會赫夫曼編碼的求解過程，并了解赫夫曼編碼的廣泛用途，掌握鏈表的靈活運用；學(xué)習(xí)鏈表初始化和建立一個新的單循環(huán)鏈表，并學(xué)會分析鏈表功能選擇合適鏈表進行編程。設(shè)計方案論證2.1問題描述赫夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度(若根結(jié)點為0層，葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù))。樹的帶權(quán)路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權(quán)值Wi(i=1,2,...n)構(gòu)成一棵有N個葉結(jié)點的二叉樹，相應(yīng)的葉結(jié)點的路徑長度為Li(i=1,2,...n)?？梢宰C明哈夫曼樹的WPL是最小的。2.2建立赫夫曼樹的算法思想從n個權(quán)值｛W1,W2,......,Wn｝構(gòu)造n棵只有一個結(jié)點的二叉樹，其中每棵二叉樹的左右子樹均為空，從而得到n棵樹的森林F=(T1,T2,......,Tn｝在森林F中，選出權(quán)值最小和次最小的二叉樹分別作為左子樹和右子樹，構(gòu)造一棵新的二叉樹，且新二叉樹根的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和。在森林F中刪除這兩棵二叉樹，同時把新的二叉樹加入到森林F中。重復(fù)2和3兩步驟，直到森林中只有一棵樹為止，這棵樹便是哈夫曼樹。2.3赫夫曼樹的構(gòu)造過程下圖展示了赫夫曼樹的構(gòu)造過程，其中根節(jié)點上標注的數(shù)字是所賦的權(quán)值。

(A)(B)12(C)(D)(A)(B)12(C)(D)圖1赫夫曼樹的構(gòu)造過程可以計算得到該赫夫曼樹的路徑長度:WPL=(12+8)*3+2*15+1*17=107o

2.4赫夫曼編碼求解過程編寫求赫夫曼編碼操作就是按照建立赫夫曼樹的算法思想建立一棵赫夫曼樹，然后自底向上求得葉子結(jié)點（既每個字符）的赫夫曼編碼。步驟1：以4個帶權(quán)｛7,2,5,4｝字符為例，手動實現(xiàn)求解這4個字符的赫夫曼編碼。假設(shè)字符個數(shù)為n,則這棵赫夫曼樹HT中結(jié)點個數(shù)為m，即m=2n-1=7。按照算法思想（1），其存儲結(jié)構(gòu)HT的初始狀態(tài)如圖2所示7000200050004000■000■000■000HTweightparentIchildrchild1234567圖2HT初始狀態(tài)圖步驟2：按照算法思想步驟（2）、（3）、（4），HT的終結(jié)狀態(tài)如圖3（a）所示（其中parent、Ichild和rchild的值分別為結(jié)點在表中的序號）。（b）與（b）與HT相應(yīng)的樹形1234567(a)HT的終結(jié)狀態(tài)圖3HT的終結(jié)狀態(tài)圖和樹形步驟3：從葉子結(jié)點出發(fā)走一條從葉子結(jié)點到根路徑便可求出每個字符的赫夫曼編碼。碼。以求解值為2（結(jié)點序號為2）的結(jié)點的赫夫曼編碼為例：結(jié)點2是雙親結(jié)點5的左孩子，求得第一個編碼為“0”；結(jié)點5是雙親結(jié)點6的右孩子，求得第二個編碼為“1”；結(jié)點6是雙親結(jié)點7的右孩子，求得第三個編碼為“1”；結(jié)點7沒有雙親，即結(jié)點7為根結(jié)點，整個赫夫曼編碼求解完畢。因為，求解過程是自底向上的過程，因此，權(quán)值為2的結(jié)點的赫夫曼編碼為110（是求解過程順序得到的編碼逆序）。最終得到的4個赫夫曼編碼如圖4所示（a）編碼的最終狀態(tài)（a）編碼的最終狀態(tài)（b）相應(yīng)的樹形圖44個字符的赫夫曼編碼及樹型2.5算法設(shè)計（1）主程序模塊voidmain(){初始化;while(“命令”==“繼續(xù)”)接受命令;處理命令;

二叉樹的存儲結(jié)構(gòu)表示typedefstructBiTNode(chardata;intweigh;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;赫夫曼樹的存儲結(jié)構(gòu)和赫夫曼編碼的存儲結(jié)構(gòu)根據(jù)赫夫曼樹的特點和操作特性，可以按圖5所示的存儲結(jié)構(gòu)定義赫夫曼樹。HTNodeHuffmanCodechar*charHuffmanTreeHTNodeHuffmanCodechar*char圖5赫夫曼樹和赫夫曼編碼的存儲結(jié)構(gòu)具體算法描述如下:typedefstructunsignedintweigh;//unsignedintweigh;//根結(jié)點的權(quán)值unsignedintparent,lchild,rchild;//unsignedintparent,lchild,rchild;//雙親、左孩子和右孩子的序號}HTNode,*HuffmanTree;〃動態(tài)分配數(shù)組存儲赫夫曼樹}HTNode,*HuffmanTree;〃動態(tài)分配數(shù)組存儲赫夫曼樹Typedefchar**HuffmanCode;〃動態(tài)分配數(shù)組存儲赫夫曼編碼表Typedefchar**HuffmanCode;〃動態(tài)分配數(shù)組存儲赫夫曼編碼表存儲二叉樹中的非空的權(quán)值非零的節(jié)點的結(jié)構(gòu)typedefstructtempsave{intweigh;charch;}tempsave,*temp;最小權(quán)值的求解是在哈弗曼樹中i個結(jié)點中找出權(quán)值最小的結(jié)點序號，相應(yīng)的N一S圖如圖所示最小值k初始值為無符號數(shù)量最大值i=i『弟個結(jié)點權(quán)值當(dāng)前最小值序號fl&gFj第』斐個結(jié)點不再是根結(jié)點返回最小權(quán)結(jié)點序號n雎圖6查找i個結(jié)點中最小權(quán)值結(jié)點序號的N-S圖具體算法描述如下：intmin(HuffmanTreet,inti){//求解最小權(quán)值的操作//初始條件：赫夫曼樹已存在//操作結(jié)果：返回i個結(jié)點中權(quán)值最小樹的根結(jié)點序號，被select()調(diào)用intj,flag;unsignedintk=UINT_MAX; //取k為不小于可能的值for(j=1;j<=i;j++)if(t[j].weight<k&&t[j].parent==0){k=t[j].weight;flag=j;}t[flag].parent=1;returnflag;}voidselect(HuffmanTreet,inti,int&s1,int&s2)//si為最小的兩個值中序號小的那個intj；s1=min(t,i);s2=min(t,i);if(s1>s2)j=s1;s1=s2;s2=j;2.6程序設(shè)計思路2.6.1功能模塊圖各模塊之間的調(diào)用關(guān)系如下：圖7功能模塊圖2.6.2功能模塊思路設(shè)計（1） 主程序模塊（2） 二叉樹創(chuàng)建模塊：實現(xiàn)二叉樹的創(chuàng)建；從鍵盤建立二叉樹采用先序遍歷的順序進行創(chuàng)建，并輸入數(shù)據(jù)，由鍵盤輸入每個節(jié)點的數(shù)據(jù)，當(dāng)輸入為“聃，當(dāng)前操作的節(jié)點指針為NULL，采用先左子樹后右子樹的順序函數(shù)根據(jù)輸入數(shù)據(jù)的形式，生成相應(yīng)的二叉樹結(jié)構(gòu)。（3） 查找非零節(jié)點模塊：查找二叉樹中非零節(jié)點，并存儲其在一個數(shù)組中；（4） 哈夫曼樹模塊：實現(xiàn)哈夫曼樹的創(chuàng)建；（5） 輸出模塊：輸出創(chuàng)建的哈夫曼編碼；（6） 查找最小葉節(jié)點模塊：查找非零葉節(jié)點中最小的兩個。系統(tǒng)流程圖如下：

2.7程序源代碼#include<stdio.h>#include<string.h>#include<malloc.h>#include<limits.h>#include<stdlib.h>typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree; //動態(tài)分配數(shù)組存儲赫夫曼樹typedefchar**HuffmanCode; //動態(tài)分配數(shù)組存儲赫夫曼編碼表intmin(HuffmanTreet,inti){//求解最小權(quán)值的操作//初始條件：赫夫曼樹已存在//操作結(jié)果：返回i個結(jié)點中權(quán)值最小樹的根結(jié)點序號，被select()調(diào)用intj,flag;unsignedintk=UINT_MAX; //取k為不小于可能的值for(j=1;j<=i;j++)if(t[j].weightvk&&t[j].parent==0){k=t[j].weight;flag=j;}t[flag].parent=1;returnflag;}voidselect(HuffmanTreet,inti,int&s1,int&s2) //si為最小的兩個值中序號小的那個intj；s1=min(t,i);s2=min(t,i);if(s1>s2)j=s1;s1=s2;s2=j;…………曲)intm,i,s1,s2,start;unsignedc,f;HuffmanTreep;char*cd;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));……)(*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}for(;i<=m;++i,++p)(*p).parent=0;for(i=n+1;i<=m;++i){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;}//從葉子到根逆向求每個字符的哈夫曼編碼HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;i++){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}voidmain(){printf("HuffmanTreeCreating&HuffmanEncoding,byss1271.\n");HuffmanTreeHT;HuffmanCodeHC;int*w,n,i;printf("請輸入權(quán)值的個數(shù)(需要大于1)：");scanf("%d”,&n);w=(int*)malloc(n*sizeof(int));printf("請依次輸A%d個權(quán)值(整型，每輸入完成一個請回車確認)：\n”,n);for(i=0;i<=n-1;i++)scanf("%d”,w+i);HuffmanCoding(HT,HC,w,n);printf("哈夫曼編碼結(jié)果為：\n");for(i=1;i<=n;i++)puts(HC[i]);}運行結(jié)果分析在本程序中，建立赫夫曼樹需要用戶輸入節(jié)點的個數(shù)及其對應(yīng)的權(quán)值，結(jié)點限定為大于0的整數(shù)，權(quán)值為不小于0的數(shù)。輸入節(jié)點個數(shù)后按空格鍵在輸入權(quán)值(每輸入一個權(quán)值鍵一下回車)，再按回車鍵進行下一步輸入。演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示提示信息之后，由用戶在鍵盤上輸入程序要求的數(shù)據(jù)。輸入完畢后顯示運算結(jié)果。3.1運行結(jié)果及截圖運行程序，提示輸入權(quán)值的個數(shù)(即結(jié)點的個數(shù)，需大于1)，運行結(jié)果如圖9所示

圖9提示輸入權(quán)值個數(shù)輸入結(jié)點個數(shù)后，擊回車鍵，提示輸入各個結(jié)點的權(quán)值，每輸入一個權(quán)值后回車確認，知道提示下步操作，運行結(jié)果如圖10所示圖10鍵入權(quán)值數(shù)量各個結(jié)點權(quán)值輸入完畢后，回車確認，便會輸出該樹的赫夫曼編碼，根據(jù)赫夫曼編碼也可會出相應(yīng)的赫夫曼樹，運行結(jié)果如圖11所示e*C:\Docu*entsandSettings\AdMinistrator\Debug\Cppllin.exe*■HuffmanTreeCreating&HuffmanEncoding,byss!271.著麟覷奧卜蠢完成一個請回車確認〉:123恰夫曼編碼結(jié)果為：10110Pressanykeytocontinue_圖ii輸出赫夫曼樹編碼3.2運行情況分析（1） 在輸入一個空樹的情況下，程序給出提示，若用戶想繼續(xù)則輸入y后按回車鍵，否則輸入n后回車。（2） 在輸入樹非空的情況下，程序會顯示剛輸入樹的先序遍歷結(jié)果，以及生成的赫夫曼樹的先序遍歷的結(jié)果。其中每個節(jié)點組成為：節(jié)點名（權(quán)值，左孩子節(jié)點名，右孩子節(jié)點名）。（3） 算法的時空分析創(chuàng)建二叉樹的算法createBiTree，查找非零節(jié)點的算法find以及打印赫夫曼樹的算法print，都是遍歷二叉樹的操作。顯然遍歷二叉樹的算法中的基本操作是訪問節(jié)點，則不論按哪一種次序進行遍歷，對含n個節(jié)點的二叉樹，其時間復(fù)雜度均為O（n）.所需輔助空間為遍歷過程中棧的最大容量，即樹的深度，最壞情況下為n，則空間復(fù)雜讀也為O（n）。設(shè)計體會這次設(shè)計我認為做的比較好的地方是清楚的將問題分為幾個小的方面，用幾個模塊分別完成對應(yīng)的功能，這樣思路清晰，便于編寫程序和調(diào)試。這是一個值得保持的好習(xí)慣。不好的一方面是對于生成的赫夫曼樹缺乏一種簡潔的表述，感覺自己的的表示方法有些繁瑣。如果能夠用打印的方法輸出生成的赫夫曼樹就比較好。通過本次課程設(shè)計，使我對赫夫曼樹有了更深一步的了解。在c語言的使用方面也有了一定的提高，對函數(shù)的調(diào)用上也有進步，比如開始我想用函數(shù)返回一個數(shù)組，但總是通不過編譯，后來一查資料，才知道C中不能直接返回一個數(shù)組，于是我改用返回指向數(shù)組的指針，終于解決了問題。同時，以前的模糊的概念也清晰了些。比如以前以為只要想返回多個值，就可以用引用。但在調(diào)試程序的時候發(fā)現(xiàn)并不是所有類型都有引用，比如數(shù)組就沒有。同時本程序還有一些不足之處，如初始化編碼長時，在中途如果輸入有誤就得全部重輸，這樣非常不利于初始化很長的代碼的輸入，如果能夠在出錯時可以改正就好了。這個實驗題鞏固和加深了我所學(xué)的知識，令我對以后的學(xué)習(xí)更加有興趣。我認為以后的實驗題如果能夠更貼近實際、貼進生活且難度適中就是最能激發(fā)學(xué)生學(xué)習(xí)興趣的好實驗題了。通過這次試驗我也著實感受了一次編程的樂趣，從中學(xué)到了不少的知識，更牢固的掌握了專業(yè)技能。雖然都說“程序=數(shù)據(jù)結(jié)構(gòu)+算法”，但我在學(xué)習(xí)運用數(shù)據(jù)結(jié)構(gòu)編程之前，并沒能深刻體會到這一點，直到這