數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-樹

北京郵電大學(xué)電信工程學(xué)院第20頁北京郵電大學(xué)電信工程學(xué)院第1頁2008級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)三樹學(xué)生姓名：班級(jí)：班內(nèi)序號(hào)：學(xué)號(hào)：日期：2009年11月23日實(shí)驗(yàn)要求a.實(shí)驗(yàn)?zāi)康耐ㄟ^選擇兩個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：掌握二叉樹基本操作的實(shí)現(xiàn)方法了解赫夫曼樹的思想和相關(guān)概念學(xué)習(xí)使用二叉樹解決實(shí)際問題的能力b.實(shí)驗(yàn)內(nèi)容利用二叉樹結(jié)構(gòu)實(shí)現(xiàn)赫夫曼編/解碼器。基本要求：初始化(Init)：能夠?qū)斎氲娜我忾L(zhǎng)度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立赫夫曼樹建立編碼表(CreateTable)：利用已經(jīng)建好的赫夫曼樹進(jìn)行編碼，并將每個(gè)字符的編碼輸出。編碼(Encoding)：根據(jù)編碼表對(duì)輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹對(duì)編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。打印(Print)：以直觀的方式打印赫夫曼樹（選作）計(jì)算輸入的字符串編碼前和編碼后的長(zhǎng)度，并進(jìn)行分析，討論赫夫曼編碼的壓縮效果。

2.程序分析2.1存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu):二叉樹示意圖如下:2.2關(guān)鍵算法分析核心算法思想：哈夫曼編碼(HuffmanCoding)是可變字長(zhǎng)編碼。編碼時(shí)借助哈夫曼樹，也即帶權(quán)路徑長(zhǎng)度最小的二叉樹，來建立編碼。哈夫曼編碼可以實(shí)現(xiàn)無損數(shù)據(jù)壓縮。單個(gè)字符用一個(gè)特定長(zhǎng)度的位序列替代：在字符串中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。關(guān)鍵算法思想描述和實(shí)現(xiàn)：關(guān)鍵算法1：統(tǒng)計(jì)字符出現(xiàn)的頻度，記錄出現(xiàn)的字符及其權(quán)值，對(duì)未出現(xiàn)的字符不予統(tǒng)計(jì)編碼。將統(tǒng)計(jì)的葉子節(jié)點(diǎn)編制成數(shù)組。為創(chuàng)建哈夫曼樹作準(zhǔn)備。C++實(shí)現(xiàn)：for(inti=0;str[i]!='\0';i++) //統(tǒng)計(jì)頻度 frequency[(short)str[i]]++; 此處以一個(gè)一維的下標(biāo)表示ascII編碼，以元素之表示字符頻度，解決統(tǒng)計(jì)字符的問題。for(intj=0;j<128;j++) //統(tǒng)計(jì)葉子節(jié)點(diǎn)個(gè)數(shù) if(frequency[j]!=0)leaf++; 此處掃描一遍上面建立的數(shù)組得到葉子節(jié)點(diǎn)的個(gè)數(shù)，則由(leaf*2-1)得到總的節(jié)點(diǎn)個(gè)數(shù)。關(guān)鍵算法2：建立哈弗曼樹——即最優(yōu)二叉樹。這里實(shí)現(xiàn)時(shí)：每建立一個(gè)父節(jié)點(diǎn)就需要掃描權(quán)值序列得到兩個(gè)最小的權(quán)值。由于節(jié)點(diǎn)個(gè)數(shù)逐漸增多，因而掃描次數(shù)動(dòng)態(tài)變化，程序里設(shè)置計(jì)數(shù)變量來控制掃描次數(shù)的變化。另外設(shè)置標(biāo)記來標(biāo)識(shí)節(jié)點(diǎn)是否已經(jīng)被取出。由于前面得出了總的葉子節(jié)點(diǎn)個(gè)數(shù)，根據(jù)哈弗曼樹建立的規(guī)律可以知道總的節(jié)點(diǎn)數(shù)和建立哈弗曼樹過程中的父子節(jié)點(diǎn)間的對(duì)應(yīng)關(guān)系，因而可以通過下標(biāo)準(zhǔn)確定位節(jié)點(diǎn)，動(dòng)態(tài)建立哈弗曼樹。具體C++實(shí)現(xiàn)參看源代碼中的CreateTree()函數(shù)。關(guān)鍵算法3：建立字符編碼表。這里采用從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的順序逆序編碼，然后字符串轉(zhuǎn)置得到最終編碼。C++實(shí)現(xiàn)：while(parent!=-1) { if(ptreetable[parent].lchild==child) strcat(pcodetable[j].code,"0"); //左孩子編碼0 else strcat(pcodetable[j].code,"1"); //右孩子編碼1 child=parent; //實(shí)現(xiàn)遞歸 parent=ptreetable[child].parent; } 此處從葉子節(jié)點(diǎn)向根節(jié)點(diǎn)編碼，通過迭代法遞歸實(shí)現(xiàn)節(jié)點(diǎn)的查找。strrev(pcodetable[j].code); //字符串逆序這里調(diào)用String類中strrev()函數(shù)實(shí)現(xiàn)字符串的逆序。關(guān)鍵算法4：掃描原字符串，在字符編碼表中查找相應(yīng)字符的編碼，串接寫入編碼串。C++實(shí)現(xiàn)：for(inti=0;str[i]!='\0';i++) { num=0; for(intj=0;str[i]!=pcodetable[j].ch[0];j++,num++){;} //查找編碼表 strcat(pcode,pcodetable[num].code); //串接編碼 }關(guān)鍵算法5：解碼。這里從根節(jié)點(diǎn)出發(fā)，順序查找，根據(jù)0和1的決定走左支還是右支。當(dāng)查找到葉子節(jié)點(diǎn)時(shí)，將字符串接寫入解碼字符串，并將查找點(diǎn)置于根節(jié)點(diǎn)，開始后續(xù)解碼，循環(huán)直到編碼后的字符串遍歷完畢。C++實(shí)現(xiàn)：for(inti=0;pcode[i-1]!='\0';i++) { if(ptreetable[parent].lchild==-1) //找到葉子節(jié)點(diǎn) { strcat(pstr,pcodetable[parent].ch); //串接字符 parent=leaf*2-2; } if(pcode[i]=='0')parent=ptreetable[parent].lchild; //走左支 else parent=ptreetable[parent].rchild; //走右支關(guān)鍵算法6： 統(tǒng)計(jì)分析壓縮效果。由于是模擬編碼，重點(diǎn)在理解數(shù)據(jù)結(jié)構(gòu)和算法，故沒有進(jìn)行位操作，輸出的編碼依舊以字符串存儲(chǔ)，故計(jì)算壓縮后長(zhǎng)度需要折算。C++實(shí)現(xiàn)： intbefore=strlen(str); //原始編碼大小 intlength=strlen(pcode); //模擬的編碼串的大小 intafter=ceill((float)length/8); //如果進(jìn)行bit存儲(chǔ)時(shí)應(yīng)該有的壓縮效果 floatrate=after/(float)before; //壓縮比率時(shí)間復(fù)雜度與空間復(fù)雜度：1.編碼和解碼需要大量掃描數(shù)據(jù)，因而時(shí)間復(fù)雜度很高。由于遍歷的時(shí)候主要采用for循環(huán)結(jié)構(gòu)，故主要的時(shí)間復(fù)雜度集中在此。設(shè)不同字符的個(gè)數(shù)為n，則整個(gè)程序的時(shí)間復(fù)雜度可以累加計(jì)算，最后估算結(jié)果是：O(3*n(n+3)/2)。2.由于使用數(shù)組存儲(chǔ)字符串，有一定的空間浪費(fèi)，空間復(fù)雜度由初始定義的字符串最大可用長(zhǎng)度Max和不同字符個(gè)數(shù)n決定。計(jì)算總的空間復(fù)雜度約為O(Max*(n+4)/2+45n+20)。

3.程序運(yùn)行結(jié)果

測(cè)試條件：以隨機(jī)輸入的一串字符串。（測(cè)試對(duì)字符的兼容能力）實(shí)驗(yàn)題目中給出的字符串。（測(cè)試小規(guī)模數(shù)據(jù)的編解碼能力）網(wǎng)上摘錄的大段文字。（測(cè)試大規(guī)模數(shù)據(jù)編解碼能力）測(cè)試結(jié)論：本程序?qū)λ蠥SCII編碼均支持，對(duì)大規(guī)模和小規(guī)模編碼均能實(shí)現(xiàn)正確編解碼和壓縮。

4.總結(jié)1、哈夫曼編碼的基本思想是對(duì)出現(xiàn)頻率高的輸入單元賦予較短的比特片，而對(duì)出現(xiàn)頻率低的輸入單元賦予較長(zhǎng)的比特片，從而使編碼后的字符串平均長(zhǎng)度降低,達(dá)到無損數(shù)據(jù)壓縮的目的。這種壓縮的思想需要去理解和掌握。而通過哈弗曼樹的方式來編碼的這種巧妙的構(gòu)思應(yīng)好好體會(huì)。2、這算是寫過的最長(zhǎng)的代碼了，中間遇到了不少阻礙。上課老師講了實(shí)現(xiàn)的思想方法，但自己在將這種思想付諸實(shí)踐形成代碼的過程中卻并非容易。有時(shí)看老師寫代碼就像是說話或者說寫作文一樣簡(jiǎn)單，但是自己真正動(dòng)手操作的時(shí)候卻發(fā)現(xiàn)并非易事。自己對(duì)編程語言的掌握和理解還不夠透，寫程序不夠熟練，在算法到代碼還有很長(zhǎng)的鴻溝。須是在今后的編程實(shí)踐中勤加練習(xí)，多問多思，終有一天達(dá)到老師的水準(zhǔn)。3、學(xué)習(xí)哈弗曼編碼是一個(gè)點(diǎn)，從這個(gè)點(diǎn)出發(fā)，可以思考很多，比如ASCII碼的編碼會(huì)了，GB編碼呢？UTP-8編碼呢？能否仿照實(shí)現(xiàn)呢？比如其他的壓縮算法呢？能否擴(kuò)展開去，了解和掌握更多形式的編碼和壓縮技術(shù)呢？編碼和壓縮在后續(xù)課程中體現(xiàn)較多，應(yīng)用也很廣，應(yīng)當(dāng)擴(kuò)展開去學(xué)習(xí)。4、思考改進(jìn)：A．由于主要考慮模擬算法、理解數(shù)據(jù)結(jié)構(gòu)，所以只是模擬實(shí)現(xiàn)壓縮，最后只是用字符串存儲(chǔ)的壓縮后的編碼，嚴(yán)格說實(shí)際壓縮還沒有實(shí)現(xiàn)，后續(xù)應(yīng)考慮能否對(duì)bit位進(jìn)行操作，實(shí)現(xiàn)能夠?qū)嶋H存儲(chǔ)的代碼。B．本程序只能處理ASCII編碼，對(duì)漢字編碼和其他編碼格式尚不支持，后續(xù)應(yīng)考慮研究不同的編碼格式，進(jìn)行編碼轉(zhuǎn)換，實(shí)現(xiàn)對(duì)多種編碼格式的壓縮支持。C．用數(shù)組處理字符串造成了一定的空間的浪費(fèi)，后續(xù)應(yīng)考慮采取其他方式處理字符串。D．程序中對(duì)數(shù)據(jù)進(jìn)行了大量的掃描和遍歷，當(dāng)數(shù)據(jù)量很大的時(shí)候，時(shí)間復(fù)雜度將很高，應(yīng)該考慮改進(jìn)哈弗曼編碼。網(wǎng)上應(yīng)該有類似的優(yōu)化的哈弗曼算法，應(yīng)學(xué)習(xí)和借鑒。

附錄源碼：（包含兩個(gè).cpp文件一個(gè).h文件）//Main.cpp#include<iostream>#include"Huffman.h"usingnamespacestd;intmain(){ cout<<"************歡迎測(cè)試Huffman編碼***************"<<endl; cout<<"請(qǐng)輸入要編碼的字符串：（暫不支持中文編碼）"<<endl; Huffmanobj; obj.Init(); obj.CreateTree(); obj.CreateTable(); obj.Encoding(); obj.Decoding(); cout<<"請(qǐng)選擇操作：\n"<<"1.打印原始字符串的統(tǒng)計(jì)數(shù)據(jù)\n"<<"2.以表格方式打印Huffman樹\n" <<"3.打印編碼表\n"<<"4.打印編碼后的字符串\n" <<"5.輸出解碼后的字符串\n"<<"6.分析壓縮效果\n"; unsignedintoption; while(true) { cin>>option; switch(option) { case1: cout<<'\n'<<"總共的字符個(gè)數(shù)："<<strlen(obj.str)/sizeof(char)<<endl; cout<<"不同的字符總數(shù)："<<obj.leaf<<endl; cout<<"字符\t"<<"頻率\t"<<endl; for(intj=0;j<obj.leaf;j++) cout<<obj.pcodetable[j].ch<<'\t'<<obj.pcodetable[j].freq<<endl; break; case2: cout<<"Huffman樹表如下：\n"; cout<<"序號(hào)\t"<<"權(quán)值\t"<<"父節(jié)點(diǎn)\t"<<"左孩子\t"<<"右孩子\n"; for(intt=0;t<2*obj.leaf-1;t++) { cout<<t<<":"<<'\t'<<obj.ptreetable[t].weight<<"\t"<<obj.ptreetable[t].parent<<"\t"<<obj.ptreetable[t].lchild<<"\t" <<obj.ptreetable[t].rchild<<endl; } break; case3: cout<<"字符\t"<<"編碼\t"<<endl; for(intj=0;j<obj.leaf;j++) cout<<obj.pcodetable[j].ch<<'\t'<<obj.pcodetable[j].code<<endl; break; case4: cout<<"\n編碼后的字符串如下：\n"<<obj.pcode<<endl; break; case5: cout<<"\n解碼后的字符串如下：\n"<<obj.pstr<<endl; break; case6: obj.Analyse(); break; default: cout<<"\n缺省輸出：\n"; cout<<"\n編碼后的字符串如下：\n"<<obj.pcode<<endl; obj.Analyse(); return0; } } return0;}//Huffman.h#include<string>constintMax=1000;structtreetable //樹表的元素 { intweight; //權(quán)值 intparent; //父節(jié)點(diǎn) intlchild; //左孩子 intrchild; //右孩子 intmark; //標(biāo)記是否已經(jīng)編碼 };structcodetable //編碼表的元素 { charch[2]; //字符 intfreq; //頻度 charcode[Max/2]; //字符編碼 };classHuffman //Huffman類定義{public: Huffman(){;} ~Huffman(); intInit(); //初始化類,統(tǒng)計(jì)必要的原始字符串?dāng)?shù)據(jù) intCreateTree(); //建立哈弗曼樹表 intCreateTable(); //建立編碼表 intEncoding(); //對(duì)給定的字符串進(jìn)行編碼 intDecoding(); //對(duì)編碼后的字符串進(jìn)行解碼 intAnalyse(); //分析編碼壓縮的相關(guān)數(shù)據(jù) friendintmain();private: charstr[Max]; //保存用戶輸入字符串 treetable*ptreetable; //保存哈弗曼樹表 codetable*pcodetable; //保存編碼表 intleaf; //葉子節(jié)點(diǎn)個(gè)數(shù) char*pcode; //保存壓縮后的字符串 char*pstr; //保存解壓縮之后的字符串};//HuffmanFunc.cpp#include"Huffman.h"#include<iostream>#include<string>#include<cmath>usingnamespacestd;/*****************************************************************************************************************************************/intHuffman::Init(){ cin.getline(str,Max); cout<<"正在初始化編碼……"<<endl; shortfrequency[128]={0}; leaf=0; for(inti=0;str[i]!='\0';i++) //統(tǒng)計(jì)頻度 frequency[(short)str[i]]++; for(intj=0;j<128;j++) //統(tǒng)計(jì)葉子節(jié)點(diǎn)個(gè)數(shù) if(frequency[j]!=0)leaf++; ptreetable=newtreetable[leaf*2-1]; pcodetable=newcodetable[leaf]; for(intk=0,m=0;k<128;k++) //建立葉子節(jié)點(diǎn)表 { if(frequency[k]!=0) { pcodetable[m].freq=ptreetable[m].weight=frequency[k]; pcodetable[m].ch[0]=(char)k; pcodetable[m].ch[1]='\0'; pcodetable[m].code[0]='\0'; ptreetable[m].mark=0; m++; } } for(intk=0;k<leaf;k++) //標(biāo)記葉子節(jié)點(diǎn)：無左右孩子 ptreetable[k].lchild=ptreetable[k].rchild=-1; return0;}/*****************************************************************************************************************************************/intHuffman::CreateTree(){intmin=Max; intnum(0),times(leaf),front(leaf),count1(0),count2(0),lcvalue(0),rcvalue(0); for(ints=0;s<(2*leaf-2);s++) { for(inti=0;i<times;i++) { if(ptreetable[i].mark!=1&&min>=ptreetable[i].weight) {min=ptreetable[i].weight;num=i;} } count1++; if(count1==2){times++;count1=0;} ptreetable[num].mark=1; //標(biāo)記已讀 count2++; if(count2==1) //左孩子 { lcvalue=min; ptreetable[num].parent=front; ptreetable[front].lchild=num; } if(count2==2) //右孩子 { rcvalue=min; ptreetable[num].parent=front; ptreetable[front].rchild=num; ptreetable[front].weight=lcvalue+rcvalue; front++; count2=0; } min=Max; } ptreetable[2*leaf-2].parent=-1; ptreetable[2*leaf-2].mark=-1; return0;}/*****************************************************************************************************************************************/intHuffman::CreateTable(){ for(intj=0,parent=0,child=0;j<leaf;j++) { parent=ptreetable[j].parent; child=j; while(parent!=-1) { if(ptreetable[parent].lchild==child) strcat(pcodetable[j].code,"0"); else strcat(pcodetable[j].code,"1"); child=parent; parent=ptreetable[child].parent; } strrev(pcodetable[j].code); } return0;}/*****************************************************************************************************************************************/intHuffman::Encoding(){ intnum; pcode=newchar[Max]; pcode[0]='\0'; for(inti=0;str[i]!='\0';i++) { num=0; for(intj=0;str[i]!=pcodetable[j].ch[0];j++,num++){;} strcat(pcode,pcodetable[num].code); } return0;}/*****************************************************************************************************************************************/intHuffman::Decoding(){ intparent=leaf*2-2; pstr=newchar[Max]; pstr[0]='\0'; for(inti=0;pcode[i-1]!='\0';i++) { if(ptreetable[parent].lchild==-1) {