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

實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康恼莆展蚵鼧浼捌鋺?yīng)用。實(shí)驗(yàn)內(nèi)容利用哈夫曼算法，構(gòu)造最優(yōu)二叉樹，然后對(duì)構(gòu)造好的二叉樹的葉子結(jié)點(diǎn)進(jìn)行前綴編碼。實(shí)驗(yàn)步驟（1）審清題意，分析并理出解決問題的基本思路。（2）根據(jù)基本思路，設(shè)計(jì)好程序的算法。（3）根據(jù)算法編寫源程序。（4）在計(jì)算機(jī)上編譯程序，檢驗(yàn)程序的可運(yùn)行性數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：//赫夫曼樹和赫夫曼編碼的存儲(chǔ)結(jié)構(gòu)typedefstruct//結(jié)點(diǎn)的結(jié)構(gòu)，在教科書第147頁{unsignedintweight;//結(jié)點(diǎn)的權(quán)值unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹typedefchar**HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)//算法6.12{//w存放n個(gè)字符的權(quán)值(均>0)，構(gòu)造赫夫曼樹HT，并求出n個(gè)字符的赫夫曼編碼HCintstart;unsignedf;//以下是從葉子到根逆向求每個(gè)字符的赫夫曼編碼intm,i,s1,s2;unsignedc;HuffmanTreep;char*cd;if(n<=1)//葉子結(jié)點(diǎn)數(shù)不大于nreturn;m=2*n-1;//n個(gè)葉子結(jié)點(diǎn)的赫夫曼樹共有m個(gè)結(jié)點(diǎn)HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號(hào)單元未用for(p=HT+1,i=1;i<=n;++i,++p,++w)//從1號(hào)單元開始到n號(hào)單元，給葉子結(jié)點(diǎn)賦值{//p的初值指向1號(hào)單元(*p).weight=*w;//賦權(quán)值(*p).parent=0;//雙親域?yàn)榭?是根結(jié)點(diǎn))(*p).lchild=0;//左右孩子為空(是葉子結(jié)點(diǎn)，即單結(jié)點(diǎn)樹)(*p).rchild=0;}for(;i<=m;++i,++p)//i從n+1到m(*p).parent=0;//其余結(jié)點(diǎn)的雙親域初值為0for(i=n+1;i<=m;++i)//建赫夫曼樹{//在HT[1～i-1]中選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2select(HT,i-1,s1,s2);HT[s1].parent=HT[s2].parent=i;//i號(hào)單元是s1和s2的雙親HT[i].lchild=s1;//i號(hào)單元的左右孩子分別是s1和s2HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//i號(hào)單元的權(quán)值是s1和s2的權(quán)值之和}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n個(gè)字符編碼的頭指針向量([0]不用)cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間cd[n-1]='\0';//編碼結(jié)束符for(i=1;i<=n;i++){//逐個(gè)字符求赫夫曼編碼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個(gè)字符編碼分配空間strcpy(HC[i],&cd[start]);//從cd復(fù)制編碼(串)到HC}free(cd);//釋放工作空間}源代碼：#include<string.h>//字符串函數(shù)頭文件#include<ctype.h>//字符函數(shù)頭文件#include<malloc.h>//malloc()等#include<limits.h>//INT_MAX等#include<stdio.h>//標(biāo)準(zhǔn)輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等#include<stdlib.h>//atoi()，exit()#include<io.h>//eof()#include<math.h>//數(shù)學(xué)函數(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章用到//赫夫曼樹和赫夫曼編碼的存儲(chǔ)結(jié)構(gòu)typedefstruct//結(jié)點(diǎn)的結(jié)構(gòu)，在教科書第147頁{unsignedintweight;//結(jié)點(diǎn)的權(quán)值unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹typedefchar**HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表intmin(HuffmanTreet,inti){//返回赫夫曼樹t的前i個(gè)結(jié)點(diǎn)中權(quán)值最小的樹的根結(jié)點(diǎn)序號(hào)，函數(shù)select()調(diào)用intj,m;unsignedintk;//k存最小權(quán)值，初值取為不小于可能的值(無符號(hào)整型最大值)for(j=1;j<=i;j++)//對(duì)于前i個(gè)結(jié)點(diǎn)if(t[j].parent==0)//t[j]的權(quán)值小于k，又是樹的根結(jié)點(diǎn){k=t[j].weight;//t[j]的權(quán)值賦給km=j;//序號(hào)賦給m}t[m].parent=1;//給選中的根結(jié)點(diǎn)的雙親賦非零值，避免第2次查找該結(jié)點(diǎn)returnm;//返回權(quán)值最小的根結(jié)點(diǎn)的序號(hào)}voidselect(HuffmanTreet,inti,int&s1,int&s2){//在赫夫曼樹t的前i個(gè)結(jié)點(diǎn)中選擇2個(gè)權(quán)值最小的樹的根結(jié)點(diǎn)序號(hào)，s1為其中序號(hào)(權(quán)值)較小的intj;s1=min(t,i);//權(quán)值最小的根結(jié)點(diǎn)序號(hào)s2=min(t,i);//權(quán)值第2小的根結(jié)點(diǎn)序號(hào)if(s1>s2)//s1的序號(hào)大于s2的{//交換j=s1;s1=s2;//s1是權(quán)值最小的2個(gè)中序號(hào)較小的s2=j;//s2是權(quán)值最小的2個(gè)中序號(hào)較小的}}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)//算法6.12{//w存放n個(gè)字符的權(quán)值(均>0)，構(gòu)造赫夫曼樹HT，并求出n個(gè)字符的赫夫曼編碼HCintstart;unsignedf;//以下是從葉子到根逆向求每個(gè)字符的赫夫曼編碼intm,i,s1,s2;unsignedc;HuffmanTreep;char*cd;if(n<=1)//葉子結(jié)點(diǎn)數(shù)不大于nreturn;m=2*n-1;//n個(gè)葉子結(jié)點(diǎn)的赫夫曼樹共有m個(gè)結(jié)點(diǎn)HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號(hào)單元未用for(p=HT+1,i=1;i<=n;++i,++p,++w)//從1號(hào)單元開始到n號(hào)單元，給葉子結(jié)點(diǎn)賦值{//p的初值指向1號(hào)單元(*p).weight=*w;//賦權(quán)值(*p).parent=0;//雙親域?yàn)榭?是根結(jié)點(diǎn))(*p).lchild=0;//左右孩子為空(是葉子結(jié)點(diǎn)，即單結(jié)點(diǎn)樹)(*p).rchild=0;}for(;i<=m;++i,++p)//i從n+1到m(*p).parent=0;//其余結(jié)點(diǎn)的雙親域初值為0for(i=n+1;i<=m;++i)//建赫夫曼樹{//在HT[1～i-1]中選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2select(HT,i-1,s1,s2);HT[s1].parent=HT[s2].parent=i;//i號(hào)單元是s1和s2的雙親HT[i].lchild=s1;//i號(hào)單元的左右孩子分別是s1和s2HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//i號(hào)單元的權(quán)值是s1和s2的權(quán)值之和}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n個(gè)字符編碼的頭指針向量([0]不用)cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間cd[n-1]='\0';//編碼結(jié)束符for(i=1;i<=n;i++){//逐個(gè)字符求赫夫曼編碼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個(gè)字符編碼分配空間strcpy(HC[i],&cd[start]);//從cd復(fù)制編碼(串)到HC}free(cd);//釋放工作空間}voidmain(){HuffmanTreeHT;HuffmanCodeHC;int*w,n,i;printf("請輸入權(quán)值的個(gè)數(shù)(>1)：");scanf("%d",&n);w=(int*)malloc(n*sizeof(int));//動(dòng)態(tài)生成存放n個(gè)權(quán)值的空間printf("請依次輸入%d個(gè)權(quán)值(整型)：\n",n);for(i=0;i<=n-1;i++)