第一篇：樹和哈夫曼樹實(shí)驗(yàn)報(bào)告

樹和哈夫曼樹實(shí)驗(yàn)報(bào)告

一．實(shí)驗(yàn)?zāi)康?/p>

練習(xí)樹和哈夫曼樹的有關(guān)操作，和各個算法程序，理解哈夫曼樹的編碼和譯碼 二．實(shí)驗(yàn)環(huán)境

Microsoft visual c++ 三．實(shí)驗(yàn)問題描述

1.問題描述：建立一棵用二叉鏈表方式存儲的二叉樹，并對其進(jìn)行遍歷（先序、中序和后序），打印輸出遍歷結(jié)果。

基本要求：從鍵盤接受輸入先序序列，以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立），并將此二叉樹按照“樹狀形式”打印輸出，然后對其進(jìn)行遍歷（先序、中序和后序），最后將遍歷結(jié)果打印輸出。在遍歷算法中要求至少有一種遍歷采用非遞歸方法。測試數(shù)據(jù)：

ABC??DE?G??F???（其中?表示空格字符）輸出結(jié)果為： 先序：ABCDEGF 先序：CBEGDFA 先序：CGEFDBA 2.問題描述：利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接受端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)?；疽螅?至少完成功能1-2）一個完整的系統(tǒng)應(yīng)具有以下功能： I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中?；疽螅?/p>

E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。

D：譯碼（Decoding)。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。

P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrint中。T：印哈夫曼樹（TreePrinting）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。測試數(shù)據(jù)：

設(shè)權(quán)值w=（5，29，7，8，14，23，3，11），n=8。

按照字符‘0’或‘1’確定找左孩子或右孩子，則權(quán)值對應(yīng)的編碼為：

5：0001，29：11，7：1110，8：1111 14：110，23：01，3：0000，11：001 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。四．實(shí)驗(yàn)主要程序流

實(shí)驗(yàn)題目一主要程序：

1．void CreatBiTree(BitTree *bt)//用擴(kuò)展先序遍歷序列創(chuàng)建二叉樹，如果是#當(dāng)前樹根置為空，否則申請一個新節(jié)點(diǎn)// { char ch;ch=getchar();if(ch=='.')*bt=NULL;else { *bt=(BitTree)malloc(sizeof(BitNode));(*bt)->data=ch;CreatBiTree(&((*bt)->LChild));CreatBiTree(&((*bt)->RChild));} } 2．void Visit(char ch)//訪問根節(jié)點(diǎn) { printf(“%c ”,ch);} 3．

void PreOrder(BitTree root){ if(root!=NULL){ Visit(root->data);PreOrder(root->LChild);PreOrder(root->RChild);} } 4． void InOrder(BitTree root){ if(root!=NULL){ InOrder(root->LChild);Visit(root->data);InOrder(root->RChild);} } 5．int PostTreeDepth(BitTree bt)//后序遍歷求二叉樹的高度遞歸算法// { int hl,hr,max;if(bt!=NULL){ hl=PostTreeDepth(bt->LChild);//求左子樹的深度

hr=PostTreeDepth(bt->RChild);//求右子樹的深度

max=hl>hr?hl:hr;//得到左、右子樹深度較大者

return(max+1);//返回樹的深度 } else return(0);//如果是空樹，則返回0 } 6．void PrintTree(BitTree Boot,int nLayer)//按豎向樹狀打印的二叉樹 // { int i;if(Boot==NULL)return;PrintTree(Boot->RChild,nLayer+1);for(i=0;idata);PrintTree(Boot->LChild,nLayer+1);} 7．void main(){ BitTree T;int h;int layer;int treeleaf;layer=0;printf(“請輸入二叉樹中的元素(以擴(kuò)展先序遍歷序列輸入,其中.代表空子樹):n”);CreatBiTree(&T);printf(“先序遍歷序列為:”);PreOrder(T);printf(“n中序遍歷序列為:”);InOrder(T);printf(“n后序遍歷序列為:”);PostOrder(T);h=PostTreeDepth(T);printf(“此二叉樹的深度為:%dn”,h);printf(“此二叉樹的橫向顯示為：n”);PrintTree(T,layer);} 實(shí)驗(yàn)二主要程序流： 1．int main(){ HuffmanTree huftree;char Choose;while(1){ cout<<“n**********************歡迎使用哈夫曼編碼/譯碼系統(tǒng)**********************n”;cout<<“*您可以進(jìn)行以下操作: *n”;cout<<“*1.建立哈夫曼樹 *n”;cout<<“*2.編碼(源文已在文件ToBeTra中，或鍵盤輸入)*n”;cout<<“* 3.譯碼(碼文已在文件CodeFile中)*n”;cout<<“* 4.顯示碼文 *n”;cout<<“* 5.顯示哈夫曼樹 *n”;cout<<“* 6.退出 *n”;cout<<“***********************************************************************n”;cout<<“請選擇一個操作:”;cin>>Choose;switch(Choose){ case '1': huftree.CreateHuffmanTree();break;case '2': huftree.Encoder();break;case '3': huftree.Decoder();break;case '4': huftree.PrintCodeFile();break;case '5': huftree.PrintHuffmanTree();break;case '6': cout<<“n**********************感謝使用本系統(tǒng)!*******************nn”;system(“pause”);return 0;}//switch }//while }//main 2．// 建立哈夫曼樹函數(shù)

// 函數(shù)功能：建立哈夫曼樹（調(diào)用鍵盤建立哈夫曼樹或調(diào)用從文件建立哈夫曼樹的函數(shù)）void HuffmanTree::CreateHuffmanTree(){char Choose;cout<<“你要從文件中讀入哈夫曼樹(按1)，還是從鍵盤輸入哈夫曼樹(按2)？”;cin>>Choose;if(Choose=='2'){ //鍵盤輸入建立哈夫曼樹 CreateHuffmanTreeFromKeyboard();}//choose=='2' else { //從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹

CreateHuffmanTreeFromFile();} } 3.// 從鍵盤建立哈夫曼樹函數(shù)

// 函數(shù)功能：從鍵盤建立哈夫曼樹 //函數(shù)參數(shù)：無 //參數(shù)返回值：無

void HuffmanTree::CreateHuffmanTreeFromKeyboard(){ int Num;cout<<“n請輸入源碼字符集個數(shù)：”;cin>>Num;if(Num<=1){ cout<<“無法建立少于2個葉子結(jié)點(diǎn)的哈夫曼樹。nn”;return;} LeafNum=Num;Node=new HuffmanNode[2*Num-1];for(int i=0;i

cout<<“請輸入第”<>Node[i].weight;//源文的字符權(quán)重存入Node[].weight Node[i].parent=-1;Node[i].lchild=-1;Node[i].rchild=-1;Node[i].code=“