實驗報告實驗目的掌握哈夫曼樹及其應用。實驗內容利用哈夫曼算法，構造最優二叉樹，然后對構造好的二叉樹的葉子結點進行前綴編碼。實驗步驟（1）審清題意，分析并理出解決問題的基本思路。（2）根據基本思路，設計好程序的算法。（3）根據算法編寫源程序。（4）在計算機上編譯程序，檢驗程序的可運行性數據結構設計：//赫夫曼樹和赫夫曼編碼的存儲結構typedefstruct//結點的結構，在教科書第147頁{unsignedintweight;//結點的權值unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動態分配數組存儲赫夫曼樹typedefchar**HuffmanCode;//動態分配數組存儲赫夫曼編碼表voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)//算法6.12{//w存放n個字符的權值(均>0)，構造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HCintstart;unsignedf;//以下是從葉子到根逆向求每個字符的赫夫曼編碼intm,i,s1,s2;unsignedc;HuffmanTreep;char*cd;if(n<=1)//葉子結點數不大于nreturn;m=2*n-1;//n個葉子結點的赫夫曼樹共有m個結點HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號單元未用for(p=HT+1,i=1;i<=n;++i,++p,++w)//從1號單元開始到n號單元，給葉子結點賦值{//p的初值指向1號單元(*p).weight=*w;//賦權值(*p).parent=0;//雙親域為空(是根結點)(*p).lchild=0;//左右孩子為空(是葉子結點，即單結點樹)(*p).rchild=0;}for(;i<=m;++i,++p)//i從n+1到m(*p).parent=0;//其余結點的雙親域初值為0for(i=n+1;i<=m;++i)//建赫夫曼樹{//在HT[1～i-1]中選擇parent為0且weight最小的兩個結點，其序號分別為s1和s2select(HT,i-1,s1,s2);HT[s1].parent=HT[s2].parent=i;//i號單元是s1和s2的雙親HT[i].lchild=s1;//i號單元的左右孩子分別是s1和s2HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//i號單元的權值是s1和s2的權值之和}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n個字符編碼的頭指針向量([0]不用)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)//c是其雙親的左孩子cd[--start]='0';//由葉子向根賦值'0'else//c是其雙親的右孩子cd[--start]='1';//由葉子向根賦值'1'HC[i]=(char*)malloc((n-start)*sizeof(char));//為第i個字符編碼分配空間strcpy(HC[i],&cd[start]);//從cd復制編碼(串)到HC}free(cd);//釋放工作空間}源代碼：#include<string.h>//字符串函數頭文件#include<ctype.h>//字符函數頭文件#include<malloc.h>//malloc()等#include<limits.h>//INT_MAX等#include<stdio.h>//標準輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等#include<stdlib.h>//atoi()，exit()#include<io.h>//eof()#include<math.h>//數學函數頭文件，包括floor()，ceil()，abs()等#include<sys/timeb.h>//ftime()#include<stdarg.h>//提供宏va_start，va_arg和va_end，用于存取變長參數表//函數結果狀態代碼。在教科書第10頁#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;//Status是函數的類型，其值是函數結果狀態代碼，如OK等typedefintBoolean;//Boolean是布爾類型，其值是TRUE或FALSE，第7、8章用到//赫夫曼樹和赫夫曼編碼的存儲結構typedefstruct//結點的結構，在教科書第147頁{unsignedintweight;//結點的權值unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動態分配數組存儲赫夫曼樹typedefchar**HuffmanCode;//動態分配數組存儲赫夫曼編碼表intmin(HuffmanTreet,inti){//返回赫夫曼樹t的前i個結點中權值最小的樹的根結點序號，函數select()調用intj,m;unsignedintk;//k存最小權值，初值取為不小于可能的值(無符號整型最大值)for(j=1;j<=i;j++)//對于前i個結點if(t[j].parent==0)//t[j]的權值小于k，又是樹的根結點{k=t[j].weight;//t[j]的權值賦給km=j;//序號賦給m}t[m].parent=1;//給選中的根結點的雙親賦非零值，避免第2次查找該結點returnm;//返回權值最小的根結點的序號}voidselect(HuffmanTreet,inti,int&s1,int&s2){//在赫夫曼樹t的前i個結點中選擇2個權值最小的樹的根結點序號，s1為其中序號(權值)較小的intj;s1=min(t,i);//權值最小的根結點序號s2=min(t,i);//權值第2小的根結點序號if(s1>s2)//s1的序號大于s2的{//交換j=s1;s1=s2;//s1是權值最小的2個中序號較小的s2=j;//s2是權值最小的2個中序號較小的}}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)//算法6.12{//w存放n個字符的權值(均>0)，構造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HCintstart;unsignedf;//以下是從葉子到根逆向求每個字符的赫夫曼編碼intm,i,s1,s2;unsignedc;HuffmanTreep;char*cd;if(n<=1)//葉子結點數不大于nreturn;m=2*n-1;//n個葉子結點的赫夫曼樹共有m個結點HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號單元未用for(p=HT+1,i=1;i<=n;++i,++p,++w)//從1號單元開始到n號單元，給葉子結點賦值{//p的初值指向1號單元(*p).weight=*w;//賦權值(*p).parent=0;//雙親域為空(是根結點)(*p).lchild=0;//左右孩子為空(是葉子結點，即單結點樹)(*p).rchild=0;}for(;i<=m;++i,++p)//i從n+1到m(*p).parent=0;//其余結點的雙親域初值為0for(i=n+1;i<=m;++i)//建赫夫曼樹{//在HT[1～i-1]中選擇parent為0且weight最小的兩個結點，其序號分別為s1和s2select(HT,i-1,s1,s2);HT[s1].parent=HT[s2].parent=i;//i號單元是s1和s2的雙親HT[i].lchild=s1;//i號單元的左右孩子分別是s1和s2HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//i號單元的權值是s1和s2的權值之和}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n個字符編碼的頭指針向量([0]不用)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)//c是其雙親的左孩子cd[--start]='0';//由葉子向根賦值'0'else//c是其雙親的右孩子cd[--start]='1';//由葉子向根賦值'1'HC[i]=(char*)malloc((n-start)*sizeof(char));//為第i個字符編碼分配空間strcpy(HC[i],&cd[start]);//從cd復制編碼(串)到HC}free(cd);//釋放工作空間}voidmain(){HuffmanTreeHT;HuffmanCodeHC;int*w,n,i;printf("請輸入權值的個數(>1)：");scanf("%d",&n);w=(int*)malloc(n*sizeof(int));//動態生成存放n個權值的空間printf("請依次輸入%d個權值(整型)：\n",n);for(i=0;i<=n-1;i++)