實驗:哈夫曼樹編碼及譯碼的實現實驗題目給定字符集的HUFFMANN編碼與解碼，這里的字符集及其字符頻數自己定義，要求輸出個字符集的哈夫曼編碼及給定的字符串的哈夫曼碼及譯碼結果。實驗原理首先規定構建哈夫曼樹，然后進行哈夫曼樹的編碼，接著設計函數進行字符串的編碼過程，最后進行哈夫曼編碼的譯碼。首先定義一個結構體，這個結構體定義時盡可能的大，用來存放左右的變量，再定義一個地址空間，用于存放數組，數組中每個元素為之前定義的結構體。輸入n個字符及其權值。構建哈夫曼樹：在上述存儲結構上實現的哈夫曼算法可大致描述為：首先將地址空間初始化，將ht［0???n-1］中所有的結點里的指針都設置為空，并且將權值設置為0.輸入:讀入n個葉子的權值存于向量的前n個分量中。它們是初始森林中n個孤立的根結點上的權值。合并:對森林中的樹共進行n-1次合并，所產生的新結點依次放入向量ht的第i個分量中。每次合并分兩步：在當前森林ht［0???i-1］的所有結點中，選取權最小和次小的兩個根結點［s1］和［s2］作為合并對象，這里0Ws1，s2Wi-1。將根為ht［s1］和ht［s2］的兩棵樹作為左右子樹合并為一棵新的樹，新樹的根是新結點ht［i］。具體操作：將ht［s1］和ht［s2］的parent置為i，將ht［i］的Ichild和rchild分別置為s1和s2.新結點ht［i］的權值置為ht［s1］和ht［s2］的權值之和。哈夫曼的編碼：約定左子為0，右子為1，則可以從根結點到

葉子結點的路徑上的字符組成的字符串作為該葉子結點的編碼。當用戶輸入字母時。就在已經找好編碼的編碼結構體中去查找該字母。查到該字母就打印所存的哈夫曼編碼。接著就是完成用戶輸入0、1代碼時把代碼轉成字母的功能。這是從樹的頭結點向下查找，如果當前用戶輸入的0、1串中是0則就走向該結點的左子。如果是1這就走向該結點的右結點，重復上面步驟。直到發現該結點屬于輸入了字母的結構體則打印該結構體的字母。重復上面步驟。直到找完用戶輸入0、1串為止。則就完成了程序所有的譯碼過程。三.源程序代碼#include<math.h>#include<stdio.h>#include<time.h>〃調用數組頭文件〃用getch()要調用的頭//宏定義//定義哈夫曼編碼的結構#include<string.h>〃調用數組頭文件〃用getch()要調用的頭//宏定義//定義哈夫曼編碼的結構#defineMAX200typedefstruct{數組chardata;intweight;//定義權值intparent;intlchild;//定義左子樹intrchild;//定義右子樹}huffmannode;//定義保存哈夫曼結構體typedef//定義保存哈夫曼結構體charbits[50];intstart;}huffmancode;voidmain(){huffmannodeht[100];//定義儲存權值的空間huffmancodecd[100];charstring[100];//定義數組存儲空間charhcd[100];inti,j,x,y,s1,s2,m1,m2,n,c,f,k;printf("請輸入字符個數n=");//輸入字符的個數scanf(〃%d〃,&n);for(i=0;i<n;i++){getchar();//獲得輸入的字符printf("請輸入第%d字符變量和權值大小:〃，i+1);scanf("%c%d〃,&ht[i].data,&ht[i].weight);//輸入字符函數和權值for(i=0;i<2*n-1;i++){ht[i].parent=ht[i].lchild=ht[i].rchild=0;//初始化父結點，左右子結點}for(i=n;i<2*n-1;i++){s1=s2=0;//初始化變量m1=m2=MAX;for(j=0;j<i;j++){if(ht[j].weight<m1&&ht[j].parent==0)//尋找無父結點的最小值{m2=m1;s2=s1;m1=ht[j].weight;s1=j;//尋找當前最小值}elseif(ht[j].weight<m2&&ht[j].parent==0)//

尋找無父結點的次小值m2=ht[j].weight;s2=j;}}ht[s1].parent=i;ht[s2].parent=i;ht[i].weight=m1+m2;為i的權值ht[i].lchild=s1;ht[i].rchild=s2;}for(i=0;i<n;i++){〃尋找次小值//s1的父結點為i//最小值的權值相加//i的左子為s1//i的右子為s2〃尋找次小值//s1的父結點為i//最小值的權值相加//i的左子為s1//i的右子為s2printf("\n輸出哈夫曼譯碼:\n〃)；for(i=0;i<n;i++){printf(〃％c:〃,ht[i].data);//輸出字符for(j=cd[i].start;j<=n;j++)(printf(〃%c〃,cd[i].bits[j]);//輸出字符的01代碼}printf(〃\n〃)；}printf("\n請輸入字符串信息:\n〃)；scanf(〃％s〃，string);//輸入字符串for(i=0;string[i]!='\0';i++){for(c=0;c<=n;c++)if(string[i]==ht[c].data)//尋找與輸入字符相匹配的字母{for(j=cd[c].start;j<=n;j++)printf(〃％c〃，cd[c].bits[j]);//輸出字母代碼

break;printf（"請輸入哈夫曼譯碼:\n〃）;scanf(〃％s〃，hcd);//輸入0、1代碼scanf(〃％s〃，hcd);//輸入0、1代碼f=2*n-2;for(i=0;hcd[i]!='\0';i++){//判斷輸入為0，尋找左//判斷輸入為1,尋找右if(hcd[i]=='0')子f=ht[f].lchild;elseif(hcd[i]=='1')f=ht[f].rchild;子if(f<n){printf(〃%c〃,ht[f].data);//輸出字符串//判斷輸入為0，尋找左//判斷輸入為1,尋找右}printf(〃\n〃)；

getch();}四.運行結果（截圖）□|x,F八計算機類作業、練習、教程'算法與數據結構語言描述\熟據結衿作業'哈夫曼柳\D.63339847981132323321kab□|x,F八計算機類作業、練習、教程'算法與數據結構語言描述\熟據結衿作業'哈夫曼柳\D.63339847981132323321kabcef9hij:/lj..-l/l.l/l./lj...l/lj...l/lJ-?\大大大太太太太大盜+■B3肩+■H+■B+-H+■B+■M+■B+■M卜J口口口口口口口口口rK-0昆養昆養昆昆昆昆_木毒=1量量量量量量量量量康變變變變變變變變矗如rHMMMHMHx子I"■■r1234567891*入入入入入入入入入入L-r-M.-r-MAM.-r-M.-r-M.-r-Mj-.M.-r-M.-r-M.-r-M.-r-m腌出哈夫曼譯碼：Ll：0100b：011L：110F：000KfEl：101i：001Lj：11109f：0101居輸入字符串信息:E?F八計算機類作業、練習、教程、算法與致據結構-C語言描述'簸據結構作業、哈夫曼樹\D.--「「府輸入字符串信息：abcdefghhl000111111110000100101請輸入哈夫曼譯碼二01011001001瞄9五.實驗體會通過編程，我進一步學習了哈弗曼編碼的特點、存儲方法和基本原理，提高了自己運用C語言正確編程及調試的能力，運用數據結構解決簡單的實際問題的能力，為后續數據結構課程的學習打下基礎。在此次實驗中遇到了很多語句賦值的錯誤，還有for語句使用的不熟練，以及自己的粗心而造成的標點符號使用錯誤，宏語句的定義等等，主要的解決方案是，看一些關于C語言編程的書籍，請教其他同學，使得編譯成功自己的程序。這次的設計可以看作是一次理論與