數(shù)據(jù)結(jié)構(gòu)+哈夫曼編碼+實驗報告

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