《哈夫曼樹(shù)實(shí)驗(yàn)報(bào)告》由會(huì)員分享，可在線閱讀，更多相關(guān)《哈夫曼樹(shù)實(shí)驗(yàn)報(bào)告（14頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)名稱：實(shí)驗(yàn)三哈夫曼樹(shù) 學(xué)生姓名： 班 級(jí)： 班內(nèi)序號(hào)： 學(xué) 號(hào)： 日 期： 程序分析： 2.1 存儲(chǔ)結(jié)構(gòu)：二叉樹(shù) 2.2 程序流程： template class BiTree { public: BiTree(); //構(gòu)造函數(shù)，其前序序列由鍵盤輸入

2、 ~BiTree(void); //析構(gòu)函數(shù) BiNode* Getroot(); //獲得指向根結(jié)點(diǎn)的指針 protected: BiNode *root; //指向根結(jié)點(diǎn)的頭指針 }; //聲明類BiTree及定義結(jié)構(gòu)BiNode Data： 二叉樹(shù)是由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左右子樹(shù)構(gòu)成 二叉樹(shù)中的結(jié)點(diǎn)具有相同數(shù)據(jù)類型及層次關(guān)系 示意圖： root lchild parent rchild 哈

3、夫曼樹(shù)類的數(shù)據(jù)域，繼承節(jié)點(diǎn)類型為int的二叉樹(shù) class HuffmanTree:public BiTree data: HCode* HCodeTable;//編碼表 int tSize; //編碼表中的總字符數(shù) 二叉樹(shù)的節(jié)點(diǎn)結(jié)構(gòu) template struct BiNode //二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu) { T data; //記錄數(shù)據(jù) T lchild; //左孩子 T rchild; //右孩子 T pare

4、nt; //雙親 }; 示意圖： T data T lchild T rchild T parent 編碼表的節(jié)點(diǎn)結(jié)構(gòu) struct HCode { char data; //編碼表中的字符 char code[100]; //該字符對(duì)應(yīng)的編碼 }; 示意圖： char data char code[100] 待編碼字符串由鍵盤輸入，輸入時(shí)用鏈表存儲(chǔ)，鏈表節(jié)點(diǎn)為 struct Node { char character; //輸入的字符 unsigned int cou

5、nt;//該字符的權(quán)值 bool used; //建立樹(shù)的時(shí)候該字符是否使用過(guò) Node* next; //保存下一個(gè)節(jié)點(diǎn)的地址 }; Node* next bool used unsigned int count char character 示意圖： 2.3 關(guān)鍵算法分析： 1.初始化函數(shù)（void HuffmanTree::Init(string Input)） 算法偽代碼： 1.初始化鏈表的頭結(jié)點(diǎn) 2.獲得輸入字符串的第一個(gè)字符，并將其插入到鏈表尾部,n=1(n記錄的是鏈表中字符的個(gè)數(shù)) 3.從字符

6、串第2個(gè)字符開(kāi)始，逐個(gè)取出字符串中的字符 3.1 將當(dāng)前取出的字符與鏈表中已經(jīng)存在的字符逐個(gè)比較，如果當(dāng)前取出的字符與鏈表中已經(jīng)存在的某個(gè)字符相同，則鏈表中該字符的權(quán)值加1。 3.2 如果當(dāng)前取出的字符與鏈表中已經(jīng)存在的字符都不相同，則將其加入到鏈表尾部，同時(shí)n++ 4.tSize=n(tSize記錄鏈表中字符總數(shù)，即哈夫曼樹(shù)中葉子節(jié)點(diǎn)總數(shù)) 5.創(chuàng)建哈夫曼樹(shù) 6.銷毀鏈表 源代碼： void HuffmanTree::Init(string Input) { Node *front=new Node; //初始化鏈表的頭結(jié)點(diǎn)

7、 if(!front) throw exception("堆空間用盡"); front->next=NULL; front->character=NULL; front->count=0; Node *pfront=front; char ch=Input[0]; //獲得第一個(gè)字符 Node* New1=new Node; if(!New1) throw exception("堆空間用盡"); New1->character=ch; //將第一個(gè)字符插入鏈表 New1->count=1; New1->nex

8、t=pfront->next; pfront->next=New1; bool replace=0; //判斷在已經(jīng)寫(xiě)入鏈表的字符中是否有與當(dāng)前讀出的字符相同的字符 int n=1; //統(tǒng)計(jì)鏈表中字符個(gè)數(shù) for(int i=1;inext; if((int)pfront->character == (int)ch) /

9、/如果在鏈表中有與當(dāng)前字符相同的字符，該字符權(quán)值加1 { pfront->count++; replace=1; break; } }while(pfront->next); if(!replace) //如果在鏈表中沒(méi)找到與當(dāng)前字符相同的字符，則將該字符作為新成 員插入鏈表 { Node* New=new Node; if(!New) throw exception("堆空間用盡"); New->character=ch; New->cou

10、nt=1; New->next=pfront->next; pfront->next=New; n++; } pfront=front; //重置pfront和replace變量為默認(rèn)值 replace=0; } tSize=n; //tSize記錄的是編碼表中字符個(gè)數(shù) CreateHTree(front,n); //創(chuàng)建哈夫曼樹(shù) pfront=front; while(pfront)

11、 //銷毀整個(gè)鏈表 { front=pfront; pfront=pfront->next; delete front; } 時(shí)間復(fù)雜度： 若輸入的字符串長(zhǎng)度為n，則時(shí)間復(fù)雜度為O(n) 2.創(chuàng)建哈夫曼樹(shù)（void HuffmanTree::CreateCodeTable(Node *p)） 算法偽代碼： 1. 創(chuàng)建一個(gè)長(zhǎng)度為2*tSize-1的三叉鏈表 2. 將存儲(chǔ)字符及其權(quán)值的鏈表中的字符逐個(gè)寫(xiě)入三叉鏈表的前tSize個(gè)結(jié)點(diǎn)的data域，并將對(duì)應(yīng)結(jié)點(diǎn)的孩子域和雙親域

12、賦為空 3. 從三叉鏈表的第tSize個(gè)結(jié)點(diǎn)開(kāi)始，i=tSize 3.1 從存儲(chǔ)字符及其權(quán)值的鏈表中取出兩個(gè)權(quán)值最小的結(jié)點(diǎn)x,y，記錄其下標(biāo)x,y。 3.2 將下標(biāo)為x和y的哈夫曼樹(shù)的結(jié)點(diǎn)的雙親設(shè)置為第i個(gè)結(jié)點(diǎn) 3.3 將下標(biāo)為x的結(jié)點(diǎn)設(shè)置為i結(jié)點(diǎn)的左孩子，將下標(biāo)為y的結(jié)點(diǎn)設(shè)置為i結(jié)點(diǎn)的右孩子，i結(jié)點(diǎn)的權(quán)值為x結(jié)點(diǎn)的權(quán)值加上y結(jié)點(diǎn)的權(quán)值，i結(jié)點(diǎn)的雙親設(shè)置為空 4. 根據(jù)哈夫曼樹(shù)創(chuàng)建編碼表 源代碼： void HuffmanTree::CreateHTree(Node *p,int n) { root= new BiNode[2*n-1]

13、; //初始化哈夫曼樹(shù) Node *front=p->next; if(n==0) throw exception("沒(méi)有輸入字符"); for(int i=0;icount; root[i].lchild=-1; root[i].rchild=-1; root[i].parent=-1; front=front->next; } front=p; int New1,New2

14、; for(i=n;i<2*n-1;i++) { SelectMin(New1,New2,0,i); //從0~i中選出兩個(gè)權(quán)值最小的結(jié)點(diǎn) root[New1].parent=root[New2].parent=i; //用兩個(gè)權(quán)值最小的結(jié)點(diǎn)生成新結(jié)點(diǎn)， 新節(jié)點(diǎn)為其雙親 root[i].data=root[New1].data+root[New2].data;//新結(jié)點(diǎn)的權(quán)值為其孩子的權(quán)值的和 root[i].lchild=New1; roo

15、t[i].rchild=New2; root[i].parent=-1; } CreateCodeTable(p); //創(chuàng)建編碼表 } 時(shí)間復(fù)雜度： 在選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)的函數(shù)中要遍歷鏈表，時(shí)間復(fù)雜度為O(n),故該函數(shù)的時(shí)間復(fù)雜度為O（n^2） 3．創(chuàng)建編碼表（void HuffmanTree::CreateCodeTable(Node *p)） 算法偽代碼： 1.初始化編碼表 2.初始化一個(gè)指針，從鏈表

16、的頭結(jié)點(diǎn)開(kāi)始，遍歷整個(gè)鏈表 2.1 將鏈表中指針當(dāng)前所指的結(jié)點(diǎn)包含的字符寫(xiě)入編碼表中 2.2 得到該結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼樹(shù)的葉子結(jié)點(diǎn)及其雙親 2.3 如果哈夫曼樹(shù)只有一個(gè)葉子結(jié)點(diǎn)，將其字符對(duì)應(yīng)編碼設(shè)置為0 2.4 如果不止一個(gè)葉子結(jié)點(diǎn)，從當(dāng)前葉子結(jié)點(diǎn)開(kāi)始判斷 2.4.1 如果當(dāng)前葉子結(jié)點(diǎn)是其雙親的左孩子，則其對(duì)應(yīng)的編碼為0，否則為1 2.4.2 child指針指向葉子結(jié)點(diǎn)的雙親，parent指針指向child指針的雙親，重復(fù)2.4.1的操作 2.

17、5 將已完成的編碼倒序 2.6 取得鏈表中的下一個(gè)字符 3．輸出編碼表 源代碼： void HuffmanTree::CreateCodeTable(Node *p) { HCodeTable=new HCode[tSize]; //初始化編碼表 Node *front=p->next; for(int i=0;icharacter; //將第i個(gè)字符寫(xiě)入編碼表

18、 int child=i; //得到第i個(gè)字符對(duì)應(yīng)的葉子節(jié)點(diǎn) int parent=root[i].parent; //得到第i個(gè)字符對(duì)應(yīng)的葉子節(jié)點(diǎn)的雙親 int k=0; if(tSize==1) //如果文本中只有一種字符，它的編碼為0 { HCodeTable[i].code[k]=0; k++; } while(parent!=-1) //從第i個(gè)字符對(duì)應(yīng)的葉子節(jié)點(diǎn)開(kāi)始，尋找它到根結(jié)點(diǎn)的

19、路徑 { if(child==root[parent].lchild) //如果當(dāng)前結(jié)點(diǎn)為雙親的左孩子，則編碼為0， 否則編碼為1 HCodeTable[i].code[k]=0; else HCodeTable[i].code[k]=1; k++; child=parent; parent=root[child].parent; } HCodeTable[i

20、].code[k]=\0; Reverse(HCodeTable[i].code); //將編碼逆置 front=front->next; //得到下一個(gè)字符 } cout<<"編碼表為："<

21、曼樹(shù)獲取編碼，時(shí)間復(fù)雜度為O（n^2） 4． 選擇兩個(gè)最小權(quán)值的函數(shù) 算法偽代碼： 1. 從下標(biāo)為begin的結(jié)點(diǎn)開(kāi)始，尋找第一個(gè)沒(méi)用過(guò)的結(jié)點(diǎn) 2. 遍歷哈夫曼樹(shù)中從下標(biāo)為begin到下標(biāo)為end的結(jié)點(diǎn)序列，尋找沒(méi)用過(guò)的同時(shí)權(quán)值又是最小的結(jié)點(diǎn)。 3. 暫時(shí)改變找到的權(quán)值最小結(jié)點(diǎn)的雙親域，防止第2次找到相同的結(jié)點(diǎn)。 4. 將權(quán)值最小結(jié)點(diǎn)的下標(biāo)記錄下來(lái)。 5. 重復(fù)步驟1~4，找到第2個(gè)權(quán)值最小的結(jié)點(diǎn) 源代碼： void HuffmanTree::SelectMin(int &New1,int &New2,int begin,int e

22、nd) { int min; for(int j=0;j<2;j++) //要選擇兩個(gè)權(quán)值最小的結(jié)點(diǎn) { int sign=begin; for(int i=begin;i

23、 for(i=begin;iroot[i].data) { min=root[i].data; sign=i; } } } root[sign].parent=0;//暫時(shí)改變所找最小結(jié)點(diǎn)的雙親域，防止第2次找到的是同一個(gè)結(jié)點(diǎn) if(!j) New1=sign; else New2=sign;

24、 } } 時(shí)間復(fù)雜度： 兩次遍歷鏈表，時(shí)間復(fù)雜度為O（n） 5. 將字符串倒序的函數(shù)（void HuffmanTree::Reverse(char *pch)） 算法偽代碼： 1． 得到字符串的長(zhǎng)度 2． 初始化兩個(gè)記錄下標(biāo)的變量，一個(gè)為字符串開(kāi)頭字符所在的下標(biāo)i，另一個(gè)為字符串結(jié)尾字符所在的下標(biāo)j 3． 將下標(biāo)為i和j的字符交換 4． i++,j - - 時(shí)間復(fù)雜度： 時(shí)間復(fù)雜度為O（n） 6.編碼函數(shù)（void HuffmanTree::Encode(string &

25、s,string &d)） 算法偽代碼： 1. 從s開(kāi)頭的字符開(kāi)始，逐一對(duì)s中的字符進(jìn)行編碼 2. 在編碼表中查找與當(dāng)前字符對(duì)應(yīng)的字符 3．如果找到了與當(dāng)前字符對(duì)應(yīng)的編碼表中的字符，將其編碼追加到解碼串的末尾。 4. 重復(fù)以上步驟，直到所有待編碼串中的字符都編碼完畢 5. 輸出編碼后的字符串 源代碼： void HuffmanTree::Encode(string &s,string &d) { for(int j=0;j

26、);j++) //逐個(gè)對(duì)待編碼字符串中的字符進(jìn)行編碼 { for(int i=0;i

27、 設(shè)待編碼字符串長(zhǎng)度為n，編碼表中字符個(gè)數(shù)為m，則復(fù)雜度為O（n*m） 7.解碼函數(shù) 算法偽代碼： 1. 得到指向哈夫曼樹(shù)的根結(jié)點(diǎn)的指針和指向待解碼串中的第1個(gè)字符的指針 2. 逐個(gè)讀取待解碼串中的字符，若為0，則指向哈夫曼樹(shù)當(dāng)前結(jié)點(diǎn)的指針指向當(dāng)前結(jié)點(diǎn)的左孩子，若為1，則指向當(dāng)前結(jié)點(diǎn)的右孩子 3. 指向待解碼串的指針指向解碼串中的下一個(gè)字符，直到指向哈夫曼樹(shù)結(jié)點(diǎn)的指針的孩子結(jié)點(diǎn)為空 4. 如果哈夫曼樹(shù)只有一個(gè)葉子結(jié)點(diǎn)，直接將待解碼串中的編碼轉(zhuǎn)換為對(duì)應(yīng)的字符 5. 如果指向哈夫曼樹(shù)結(jié)點(diǎn)的指針的孩子結(jié)點(diǎn)已經(jīng)為空，則將葉子結(jié)點(diǎn)下標(biāo)對(duì)應(yīng)的字符追加到解碼串中。

28、 6. 輸出解碼串 源代碼： void HuffmanTree::Decode(string &s,string &d) { for(int i=0;i

29、 parent=root[parent].lchild; else //編碼為1則尋找右孩子 parent=root[parent].rchild; i++; } if(tSize==1) //如果編碼表只有一個(gè)字符，則根結(jié)點(diǎn)即為葉子結(jié)點(diǎn) i++; d.append(1,HCodeTable[parent].data);//將葉子節(jié)點(diǎn)對(duì)應(yīng)的字符追加到解碼串中 } cout<

30、度： 設(shè)待解碼串長(zhǎng)度為n，則復(fù)雜度為O(n) 8. 計(jì)算哈夫曼編碼的壓縮比（void HuffmanTree::Calculate(string s1,string s2)） 算法偽代碼： 1. 獲得編碼前字符串的長(zhǎng)度，即其占用的字節(jié)數(shù) 2. 獲得編碼后的字符串的長(zhǎng)度，將其除以8然后向上取整，得到其占用的字節(jié)數(shù) 3. 壓縮比將兩個(gè)相除 源代碼： void HuffmanTree::Calculate(string s1,string s2) { int cal1=s1.length();

31、 int cal2=s2.length(); cal2=ceill((float)cal2/8); //將編碼串的比特?cái)?shù)轉(zhuǎn)化為字節(jié)數(shù) cout<<"編碼前的字符串長(zhǎng)度："<

32、rintTree(int TreeNode,int layer) ） 算法偽代碼： 1. 如果待打印結(jié)點(diǎn)為空，則返回 2. 遞歸調(diào)用函數(shù)打印當(dāng)前結(jié)點(diǎn)的右子樹(shù) 3. 根據(jù)當(dāng)前結(jié)點(diǎn)所在的層次確定其前面要輸出多少空格，先輸出空格，在打印當(dāng)前結(jié)點(diǎn)的權(quán)值 4. 遞歸調(diào)用函數(shù)打印當(dāng)前結(jié)點(diǎn)的左子樹(shù) 源代碼： void HuffmanTree::PrintTree(int TreeNode,int layer) { if(TreeNode==-1) //如果待打印結(jié)點(diǎn)為空，則返回

33、 return; else { PrintTree(root[TreeNode].rchild,layer+1); //先打印該結(jié)點(diǎn)的右子樹(shù)，layer記錄的是該結(jié)點(diǎn)所在的層次 for(int i=0;i

34、度： 中序遍歷哈夫曼樹(shù)，復(fù)雜度為O(n) 10. 菜單函數(shù)（void HuffmanTree::Menu()） 算法偽代碼： 1. 逐一讀取鍵盤緩存區(qū)中的字符，并將它們逐一追加到記錄輸入字符串的string變量中，直到讀到回車輸入符為止 2. 刪除string變量末尾的回車輸入符 3．利用string變量創(chuàng)建哈夫曼樹(shù)，初始化編碼表。 4. 直觀打印哈夫曼樹(shù) 5. 對(duì)輸入的字符串進(jìn)行編碼

35、 6. 對(duì)編碼后的字符串進(jìn)行解碼 7. 計(jì)算編碼前后的壓縮比并輸出 源代碼： void HuffmanTree::Menu() { cout<<"請(qǐng)輸入你要編碼的文本,按回車鍵確定輸入"<

36、etter!=\n); Input.erase(Input.length()-1,1); //去掉Input末尾的回車符 Init(Input); //根據(jù)輸入的字符串創(chuàng)建哈夫曼樹(shù)及其編碼表 cout<<"直觀打印哈夫曼樹(shù)"<

37、打印編碼串 cout<<"解碼后的字符串為"<

38、打印哈夫曼樹(shù)。 3.為了輸入空格，輸入時(shí)采取逐個(gè)字符輸入的方式 三．程序運(yùn)行結(jié)果分析： 主函數(shù)流程圖： 開(kāi)始 調(diào)用菜單函數(shù) 等待用戶輸入字符串 利用用戶輸入的字符串創(chuàng)建哈夫曼樹(shù)和編碼表 直觀打印哈夫曼樹(shù)和編碼表 對(duì)輸入的字符串編碼 對(duì)編碼串解碼 計(jì)算編碼前后的壓縮比 結(jié)束 運(yùn)行結(jié)果 各函數(shù)運(yùn)行正常，沒(méi)有bug 四. 總結(jié)： 在實(shí)現(xiàn)整個(gè)算法設(shè)計(jì)中運(yùn)用了二叉樹(shù)結(jié)構(gòu)及類創(chuàng)新，同時(shí)又復(fù)習(xí)了上學(xué)期C++的相應(yīng)內(nèi)容?？偨Y(jié)與流程分析過(guò)程雖然很辛苦但屢敗屢戰(zhàn)，獲益匪淺，收獲了很多。也認(rèn)識(shí)到自己的不足，希望自己繼續(xù)努力。