數(shù)據(jù)結(jié)構(gòu)實驗報告-樹

1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗二樹學生姓名：高鵬班級：2011211123班內(nèi)序號：19學號：2011211442口期：2012 年 11 月 28 口1. 實驗要求利用二叉樹結(jié)構(gòu)實現(xiàn)赫夫曼編/解碼器?；疽螅?、初始化(init)：能夠?qū)斎氲娜我忾L度的字符串s進行統(tǒng)計，統(tǒng)計每個字符的頻 度，并建立赫夫曼樹2、建立編碼表(createtable)：利用已經(jīng)建好的赫夫曼樹進行編碼，并將每個字符的 編碼輸出。3、編碼(encoding)：根據(jù)編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸 出。4、譯碼(decoding)：利用已經(jīng)建好的赫夫曼樹對編碼后的字符串進行譯碼，并輸出 譯碼結(jié)果。5

2、、打印(print)：以直觀的方式打印赫夫曼樹(選作)6、計算輸入的字符串編碼前和編碼后的長度，并進行分析，討論赫夫曼編碼的壓 縮效果。測試數(shù)據(jù)：i love data structure, i love computer0 i will try my best to study data structure.2. 程序分析2.1存儲結(jié)構(gòu)哈夫曼樹2.2關(guān)鍵算法分析(1) 構(gòu)造哈夫曼樹與編碼表；(2) 建立編碼、解碼、選擇、逆置與打印函數(shù)；(3) 輸入需要編碼的字符，選擇出其屮權(quán)值最小的兩個字符;(4) 對字符進行編碼并逆置；(5) 打印出編碼表和頻度排序表。關(guān)鍵代碼分析：1、主函數(shù)：#i nc

3、lude<iostream>#include<conio.h>#include<fstream>#in cludezzcolorc on sole h#include，zdsa. h"voi d main()handle handle; /使用句柄初始化界面handie二initiate();word wcolors1, wcolorsl1, wcolors21; wcolors0二foregrou'djblue|foreground一red; wcolorsl0二foreground green|foreground red; wcolo

4、rs20二foreground_green|foreground_blue; for (int a=l;a<=3;a+)textout (handle, 20, 8, wcolors2, 1,"哈夫曼樹歡迎您的到來；sleep (500);textout (handl e, 20, & wcolors2, 1,"“)；sleep (500);int f lagl (0), flag2(0), flag3(0);wh訂e (! flagl)system ("cls");/ 清屏flag2=0;textout (handle, 20, 3, w

5、colorsl, 1,"哈夫曼樹歡迎您的到來；textout (handle, 20, 7, wcolors2, 1,"請輸入任意字符串，以#結(jié)束：")； /得到字符數(shù)組int t (-1), k(0);char _s100;array a100, achange100;for(int i=0;i<100;i+)cin>>ai. data;_si二ai. data;ai. mark=-l;achangei. mark=0;t+;if (ai. data二二'#')break;_st二，0,;得到字符的頻度for(int j=o;j

6、<t;j+)if(ajl. mark=-l)achangck. data二aj. data;achangek. mark=l;for (int l=j+l;l<t;1+)if(aj data=al. data)achangek. mark+; /統(tǒng)計出各字符的頻數(shù) al. mark=0;k+;初始化哈夫曼類huffman hu;）；）；）；）；）；hu. croatetrce (achangc, k);hu.createcodetable(achange, k); string st=hu. encode(o, t); int length=st. length();char *a

7、r二new charlength+1; momcpy (ar, st. c_str (), lcngth); ar length=, 0'string stl=hu. decode (ar, k);/設定菜單欄 while(!flag2)system("cls");textout (handle, 20, 5, wcolors2, 1, "1.輸入的字符及頻度 textout (handle, 20, 7, wcolorsl, 1, "2對應的哈夫曼樹 textout (handle, 20, 9, wcolors2, 1, "3.對應

8、的哈夫曼編碼表 textout (handle, 20, 11, wcolorsl, 1, "4.對應的哈夫曼編碼 textout (handle, 20, 13, wcolors2, 1, "5.對應的字符串tex tout (handle, 20, 17, wcolorsl, 1,，zps：按 ese 返回至上一層");/菜單欄char ch2, cha2, chai3;char s100,si100; chl=chal=chal 2=, 0'char c;char * str;int m, _i, len, lenl, m2 (5); flag3=0

9、,flag2=0;while(!flag3)if( kbhit ()int key=_getch();if(flag3)break;swi tch(key)case 49:/i 鍵system("cls");textout (handle, 1, 1, wcolors2, 1, "ps：按 q 返回上一層菜單");textout (handle, 1, 3, wcolors, 1,"輸入的字符:”)；textout (handle, 15, 3, wcolors, 1, s);textout (handle, 1, 6, wcolors2, 1

10、,"輸入的字符“);textout (handle, 1, & wcolors2, 1,"輸入的頻度“)；for (m=0;m<k;m+) ch0=achangem. data; if(achangem. mark二10)chai0=' o' +achangem. mark/10; chai1=, 0, +achangem. mark%10; textout (handle, 15+4*m, 8, wcolorsl, 1, chai);if(achangem. mark<10)cha0=, o' +achangem. mark;t

11、ex tout (handle, 15+4*m, 8, wcolorsl, 1, cha);textout (handle, 15+4*m, 6, wcolorsl, 1, ch);cin»c;if(c= q,)flag3=l;break;case 50:/2 鍵system("cls");textout (handle, 1, 1, wcolors2, 1,，zps：按 q 返冋上一層菜單"); tex tout (handle, 1, 3, wcolors, 1,"輸入的字符：“)； tex tout (handle, 15, 3, wco

12、lors, 1, s);textout (handle, 35, 3, wcolors2, 1,"哈夫曼樹:“);hu. zuobiao(2*k2, k, 1<<(hu. countl+1);for(m=0;m<2*k-l;m+)if(hu. htreemj. weight>=10) chai 0=，o' +hu. htreem. weight/10; chai1=，o' +hu. htreeem. weight%10;textout (handle, hu. htreem. x, hu. htreem. y, wcolorsl, 1, cha

13、i); if(hu. htreem. lchild!=-l)textout (handle, hu. htreem. x-1, hu. htreem. y+1, wcolorsl, 1,;i f(hu. htreem. weight<10) cha0=，o' +hu. htree m. weight;textout (handle, hu. htreemj. x, hu. htreemj. y, wcolorsl, 1, cha); if(hu. htreemj. lchild!=-l)textout (handle, hu. htreemj. xl, hu. htreem. y

14、+1, wcolorsl, 1, " / ”);cin»c;if (c二二'q') flag3=l;break;case 51:/3 鍵system (z/clsz/);tex tout (handle, 1, 1, wcolors2, 1, "ps：按 q 返回上一層菜單"); textout (handl e, 1, 3, wcolors, 1,"輸入的字符:“);textout (handle, 15, 3, wcolors, 1, _s);textout (handle, 1, 6, wcolors2, 1,"

15、字符：”)；textout (handle, 1, & wcolors2, 1,"編碼：”);for(m=0;m<k;m+)cha0=achangem. data;len二hu. hcodetablem. code, length();for(_i=0;_i<len;_i+)s_i=hu. hcodetablem. codei;si+l=，0,;textout (handle, 10+5*m, 6, wcolorsl, 1, cha);textout (handle, 10+5*m, & wcolorsl, 1, s);cin>>c;if(c=

16、 q,)flag3=l;break;case 52:/4 鍵system("cls");toxtout (handle, 1, 1, wcolors2, 1, "ps：按 q 返回上一層菜單");tex tout (handle, 1, 3, wcolors, 1,"輸入的字符：“)；textout (handl e, 15, 3, wcolors, 1, _s);textout (handle, 1, 4, wcolors2, 1, 原字符”)；textout (handle, 1, & wcolors2, 1,"哈夫曼編碼

17、");lcn二st. lcngth();for(i=0;_i<len;i+十)s_i=st_i;s_i+l0,;textout (handle, 1, 6, wcolors, 1, _ s);textout (handle, 1, 10, wcolors, 1, s);cin>>c;if (c=，q') flag3=l;break;case 53:/5 鍵system (z/clsz/);tex tout (handle, 1, 1, wcolors2, 1, "ps：按 q 返回上一層菜單"); textout (handl e, 1,

18、 3, wcolors, 1,"輸入的字符:“);textout (handle, 15, 3, wcolors, 1, _s);textout (handle, 1, 5, wcolorsl, 1,"哈夫曼編碼：”);textout (handle, 1, 9, wcolorsl, 1,"字符串:”);len二st. length ();lenl=stl. length();for(_i=0;_i<len;_i+) s_i=st_i;si+l=，0,;for (i=0; i<lenl;i+)sii=stli;sm_i+l0,;tex tout (ha

19、ndle, 1, 7, wcolors2, 1, s); textout (handle, 1, 11, wcolors2, 1, si); cin»c;if (c二二'q') flag3=l;break;case 27:/按esc返回初始界面flag3=l;flag2=l;break;2、創(chuàng)建哈夫曼樹void huffman:crcatetrce(array a, int n)htree=new hxode2*n-l;/根據(jù)權(quán)重數(shù)組a初始化哈夫曼樹 for(int i二0;in;i+)htreei. weight =ai. mark;htreei. parent=-

20、l;htreei.lchild=-l;htreei. rchild二-1;int x, y, i 1, count (1);for(int j=n;j<2*n-l;j+)查找最小的兩個數(shù)for (il=0;il<j;il+)if (htreeil. pare nt 二二 t) x=i1, y二i1;break;for(int k二il+1;k<j;k+)if (htreek. parent=t)if(htreek. weight<htreex. weight)y二x;x二k;elseif(htreek. weight<htreey. weight| |(x=y)&

21、amp;&htreek. weight>=htreey. weight)y 二k;if(j=n)htreex. deep=htreey. decpcount;elseif(x=j-l| y=j-l)htreex. deep=iitreey. deep=+count;else htreetx. deep=htreey. deep=count;/結(jié)點操作htreex. parent=htrecy. parcnt=j;htreej. weight=htreex. weight+htreey. weight;htreeej. lchild=x;htreej.rchild=y;htreet

22、j. parent二t;for(int ii二0;ii<2*n-2;ii+)htreeii. deep=count+l-htreeii. deep;htree2*n-2. deep=0;countl二count+1;3、創(chuàng)建編碼表void huffman:createcodetable(array b, int n)hcodetable=new hnoden ;/生成編碼表for (int i=0;i<n;i+)hcodetablei. data二bi. data;int chi id二i;int parent二htreech訂d. patent;while(parent!=1)i

23、f (childhtreeparent. lchild)hcodetablei.code= o' +hcodetablei. code;/ 用字符串儲存哈夫曼編碼if (chi idhtree parent. rchi 1 d)hcodetablei. codev +hcodetablei.code;child=parent;parent=htreechi 1d.parent;4、編碼 s為字符串d為編碼串string huffman:encode(array s,int n)string str;int j (0);while(sj. data!二'0' &&

24、amp;j<n)for(int i二0;i<n;i+)if (iicodetablei. data=sj. data) str+=hcodetablei. code;j+；return str;5、解碼 為編碼串e為字符串 string huffman:decode(char *w, int n)string str; while(*w!=，0 )int parent=2*n-l-l;/根結(jié)點while(htreeparent. lchild!=-l)if (*w=，0)parent=htreeparent. lchiid;elseparent=htreeparent. rchil

25、d;str+=hcodetableparent. data;return str;6、計算坐標，i田i出哈夫曼樹void huffman:zuobiao(int parent, int n, int t) if(parent=2*n-2)htreeparent. x=35, htreeparent. y=4; if(htreeparent. lchild!=-l)int lehild=iitreeparent. lchild; htreetlchild. x=htreeparent.x-t; htreelchild. y=htreeparent.y+2; zuobiao (lehi id, n

26、, t/2);if(htreeparent. lchild!=-l)int rchild=iitreeparent. rchild; htreerchild. x=htreeparent.x+t; htreerchild. y=htreeparent, y+2; zuobiao(rchild, n, t/2);return;7、創(chuàng)建的結(jié)構(gòu)體和類 struct unode/結(jié)點權(quán)值/雙親指針左孩子指針右孩子指針/深度/坐標int weight; int parent; int lchild;int rchild;int deep; int x, y;； struct hnodechar data; string code;數(shù)據(jù)/編碼;struct array /數(shù)據(jù)域/標記域或權(quán)重域char data; int mark;class huffmanpublic:深度/哈夫曼樹/哈夫曼樹編碼表/創(chuàng)建哈夫曼樹/創(chuàng)建編碼表/編碼/解碼/初始化結(jié)點坐標int count 1;hnode *htree;hnode *hcodetable;void createtree(array a, int n);void createcodetable(array b,int n); string encode(array