./電子科技大學實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法學生：*浩學號：*************點名序號：***指導教師：錢**實驗地點：基礎(chǔ)實驗大樓實驗時間：2015.5.72014-2015-2學期信息與軟件工程學院實驗報告<二>學生：**浩學號：*************指導教師：錢**實驗地點：科研教學樓A508實驗時間：一、實驗室名稱：軟件實驗室二、實驗項目名稱：數(shù)據(jù)結(jié)構(gòu)與算法—樹三、實驗學時：4四、實驗原理：霍夫曼編碼〔HuffmanCoding是一種編碼方式,是一種用于無損數(shù)據(jù)壓縮的熵編碼〔權(quán)編碼算法。1952年,DavidA.Huffman在麻省理工攻讀博士時所發(fā)明的。在計算機數(shù)據(jù)處理中,霍夫曼編碼使用變長編碼表對源符號〔如文件中的一個字母進行編碼,其中變長編碼表是通過一種評估來源符號出現(xiàn)機率的方法得到的,出現(xiàn)機率高的字母使用較短的編碼,反之出現(xiàn)機率低的則使用較長的編碼,這便使編碼之后的字符串的平均長度、期望值降低,從而達到無損壓縮數(shù)據(jù)的目的。例如,在英文中,e的出現(xiàn)機率最高,而z的出現(xiàn)概率則最低。當利用霍夫曼編碼對一篇英文進行壓縮時,e極有可能用一個比特來表示,而z則可能花去25個比特〔不是26。用普通的表示方法時,每個英文字母均占用一個字節(jié)〔byte,即8個比特。二者相比,e使用了一般編碼的1/8的長度,z則使用了3倍多。倘若我們能實現(xiàn)對于英文中各個字母出現(xiàn)概率的較準確的估算,就可以大幅度提高無損壓縮的比例?；舴蚵鼧溆址Q最優(yōu)二叉樹,是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度,就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度〔若根結(jié)點為0層,葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù)。樹的路徑長度是從樹根到每一結(jié)點的路徑長度之和,記為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是最小的。五、實驗?zāi)康模罕緦嶒炌ㄟ^編程實現(xiàn)赫夫曼編碼算法,使學生掌握赫夫曼樹的構(gòu)造方法,理解樹這種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用價值,并能熟練運用C語言的指針實現(xiàn)構(gòu)建赫夫曼二叉樹,培養(yǎng)理論聯(lián)系實際和自主學習的能力,加強對數(shù)據(jù)結(jié)構(gòu)的原理理解,提高編程水平。六、實驗容：〔1實現(xiàn)輸入的英文字符串輸入,并設(shè)計算法分別統(tǒng)計不同字符在該字符串中出現(xiàn)的次數(shù),字符要區(qū)分大小寫；〔2實現(xiàn)赫夫曼樹的構(gòu)建算法；〔3遍歷赫夫曼生成每個字符的二進制編碼；〔4顯示輸出每個字母的編碼。七、實驗器材〔設(shè)備、元器件：PC機一臺,裝有C或C++語言集成開發(fā)環(huán)境。八、數(shù)據(jù)結(jié)構(gòu)與程序：/**********************************************************************程序名稱：哈夫曼樹的相關(guān)操作****程序容：生成哈夫曼樹及其編碼表、對字符串進行編碼等****編寫作者：家浩****完成時間：2015.5.15********************************************************************/#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXSIZE10000charfile_address[100];//全局通用文件地址typedefstructhnode//哈夫曼樹的節(jié)點結(jié)構(gòu)定義{intweight;intlchild,rchild,parent;}THNode,*TpHTree;typedefstructhuffman_code//哈夫曼編碼表的元素結(jié)構(gòu)定義{intweight;//編碼對應(yīng)的權(quán)值char*pcode;//指向編碼字符串的指針}THCode,*TpHcodeTab;//*************************************************************//****聲明函數(shù)//*************************************************************TpHcodeTabbuild_codesheet<TpHTreepht,intleaves_num>;//根據(jù)哈夫曼樹得到編碼表TpHTreecreate_huffman_tree<intweights[],intn>;//構(gòu)造哈夫曼樹voidselect_mintree<TpHTree,int,int*,int*>;//從森林中選擇權(quán)值最小的兩棵子樹voiddestroy_codesheet<TpHcodeTabcodesheet,intn>;//銷毀哈夫曼編碼表intread_file<charfile_address[100],char*message>;//從文本文件讀入字符串intcalc_freq<chartext[],int**freq,char**dict,intn>;//統(tǒng)計字符串text中字符出現(xiàn)的頻率//*************************************************************//****主函數(shù)//*************************************************************intmain<void>{ inti,msg_num,choose; chars;//清空緩存 intleaves_num=0; do { TpHTreepht=NULL;//建立樹根 TpHcodeTabcodesheet;//建立編碼表 charmsg[MAXSIZE];//建立信息數(shù)組 int*weights=NULL;//建立頻率數(shù)組 char*dict=NULL;//建立字符數(shù)組 printf<"\n""哈夫曼樹\n""">; printf<"\n讀取文件還是手動輸入信息？\n""1：手動輸入信息\n""2：讀取文件\n""請選擇：">; scanf<"%d",&choose>; if<choose==1> { printf<"請輸入信息：\n">; scanf<"%c",&s>;//清理鍵盤緩存 gets<msg>; msg_num=strlen<msg>; } else { printf<"輸入文件地址〔例如：F:\\\\filename.txt:\n">; scanf<"%c",&s>;//清理鍵盤緩存 gets<file_address>;//輸入文件地址 msg_num=read_file<file_address,msg>;//讀取文本文件 } leaves_num=calc_freq<msg,&weights,&dict,msg_num>;//統(tǒng)計文本串中的字符頻率,同時得到哈夫曼樹的葉節(jié)點數(shù) pht=create_huffman_tree<weights,leaves_num>;//創(chuàng)建哈夫曼樹 codesheet=build_codesheet<pht,leaves_num>; //構(gòu)造哈夫曼編碼表 printf<"\n字符頻率編碼表\n">; printf<"符號--頻率--編碼\n">; for<i=0;i<leaves_num;i++> printf<"%4c--%-3d--%-6s\n",dict[i],codesheet[i].weight,codesheet[i].pcode>; printf<"\n">; destroy_codesheet<codesheet,leaves_num>;//銷毀哈夫曼編碼表 if<pht> //釋放所有臨時空間 free<pht>; if<dict> free<dict>; if<weights> free<weights>; printf<"\n\t0：結(jié)束\n\t1：繼續(xù)\n""\t請選擇：">; scanf<"%d",&choose>; }while<choose>; return0;}//*************************************************************//****構(gòu)造哈夫曼編碼表//*************************************************************TpHcodeTabbuild_codesheet<TpHTreepht,intleaves_num>{ inti,cid,pid,cursor,len; TpHcodeTabsheet; char*pch=<char*>malloc<leaves_num+1>; if<!pch>{ printf<"申請空間失??！">; exit<0>; } memset<pch,0,<leaves_num+1>>;//清零新分配的空間 sheet=<TpHcodeTab>malloc<sizeof<THCode>*leaves_num>; if<!sheet>{ printf<"申請編碼表存空間失??！">; exit<0>; } for<i=0;i<leaves_num;++i>{ sheet[i].weight=pht[i].weight; } for<i=0;i<leaves_num;++i>{ cursor=leaves_num; cid=i; pid=pht[cid].parent; while<pid!=-1>//不為根節(jié)點{ if<pht[pid].lchild==cid> pch[--cursor]='0';//左分支編碼為'0' else pch[--cursor]='1';//右分支編碼為'1' cid=pid; pid=pht[cid].parent; } len=leaves_num-cursor+1; sheet[i].pcode=<char*>malloc<len>; if<!sheet[i].pcode>{ printf<"為節(jié)點%d的編碼申請存空間失?。?,i>; exit<0>; } memset<sheet[i].pcode,0,len>; strncpy<sheet[i].pcode,&pch[cursor],strlen<&pch[cursor]>>; } free<pch>; returnsheet;}//*************************************************************//****構(gòu)造哈夫曼樹//*************************************************************TpHTreecreate_huffman_tree<intweights[],intn>{ TpHTreepht; intminA,minB;//用于保存權(quán)值最小的兩棵子樹的序號 inti,a=0; if<n<1>{ printf<"沒有葉子節(jié)點！\n">; return0; } a=<2*n>-1; pht=<TpHTree>malloc<sizeof<THNode>*a>; if<!pht>{ printf<"分配數(shù)組空間失??！\n">; exit<0>; } for<i=0;i<a;++i> //哈夫曼數(shù)組初始化{ pht[i].weight=<i<n>?weights[i]:0; pht[i].lchild=-1; pht[i].rchild=-1; pht[i].parent=-1; } for<i=n;i<a;++i>{ select_mintree<pht,<i-1>,&minA,&minB>; pht[minA].parent=i; pht[minB].parent=i; pht[i].lchild=minA; pht[i].rchild=minB; pht[i].weight=pht[minA].weight+pht[minB].weight; } returnpht;}//*************************************************************//****選出權(quán)值最小的兩棵子樹//*************************************************************voidselect_mintree<TpHTreepht,intn,int*minA,int*minB>{ intid,min1=-1,min2=-1;//最小值,次小值 intmaxa=10000,maxb=10000; for<id=0;id<=n;id++>{ if<pht[id].parent==-1>{ if<pht[id].weight<maxa>{ min2=min1; min1=id; maxa=pht[id].weight; } elseif<pht[id].weight<maxb>{ min2=id; maxb=pht[id].weight; } } } *minA=min1; *minB=min2; return;}//*************************************************************//****銷毀哈夫曼編碼表//*************************************************************voiddestroy_codesheet<TpHcodeTabsheet,intn>{inti;for<i=0;i<n;++i>free<sheet[i].pcode>;free<sheet>;return;}//*************************************************************//****讀取文本文件//*************************************************************intread_file<charfile_address[100],char*message>{ intstr_len;//字符串長度 FILE*pFile=NULL; pFile=fopen<file_address,"r">; //打開文件 if<!pFile> { printf<"打開文件失敗!\n">; exit<0>; } else{ printf<"打開文件成功!\n">; } memset<message,0,MAXSIZE>; //清除緩沖 if<fgets<message,MAXSIZE,pFile>==NULL>{ printf<"fgetserror\n">; exit<0>; } else{ printf<"成功讀取文件,容如下：\n%s\n",message>; } str_len=strlen<message>; fclose<pFile>; returnstr_len;}//*************************************************************//****統(tǒng)計字符出現(xiàn)的頻率//*************************************************************intcalc_freq<chartext[],int**freq,char**dict,intn>//n為字符串長度{ inti,k; intchar_num=0; int*chars;//不同種類的字符 char*fre; //字符的出現(xiàn)頻率 inttimes[256]={0}; for<i=0;i<n;++i> //各個字符出現(xiàn)的頻率 times[