哈夫曼編、譯碼器

1、數(shù)據(jù)結(jié)構(gòu) C+實(shí)現(xiàn)課程設(shè)計(jì)報(bào)告學(xué)院：計(jì)算機(jī)學(xué)院專業(yè)班級：軟件項(xiàng)目題目: 哈夫曼編 / 譯碼器【問題描述】利用哈夫曼編碼可以大大提高信道利用率，縮短 信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編 碼系統(tǒng)對傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼。對 于雙工信道，每端都需要一個(gè)完整的編 / 譯碼器。試為這樣的通信端 編寫一個(gè)哈夫曼編 / 譯碼器。一 . 需求分析1. 運(yùn)行環(huán)境 （ 軟、硬件環(huán)境 Visual studio 20082. 程序?qū)崿F(xiàn)的功能初始化：輸入一串字符 正文），計(jì)算不同字符 包括空格）的 數(shù)目以及每種字符出現(xiàn)的頻率 以該種字符出現(xiàn)的次數(shù)作為其出現(xiàn)頻 率），根據(jù)

2、權(quán)值建立哈夫曼樹，輸出每一種字符的哈夫曼編碼。編碼：利用求出的哈夫曼編碼，對該正文 字符串）進(jìn)行編碼， 并輸出。譯碼：對于得到的一串編碼，利用已求得的哈夫曼編碼進(jìn)行譯 碼，將譯出的正文輸出。輸出哈夫曼樹形態(tài)：以樹的形式輸出哈夫曼樹。3. 程序的輸入一串字符 （英文或短文 （英文4. 程序的輸出根據(jù)用戶需求不同有相應(yīng)的輸出5. 測試數(shù)據(jù)there are three students二. 設(shè)計(jì)說明1. 算法設(shè)計(jì)的思想 建立鏈表類、棧類、隊(duì)列類、哈夫曼結(jié)點(diǎn)類、哈夫曼樹類，通 過主函數(shù)調(diào)用的方法來實(shí)現(xiàn)程序的功能。2. 主要的數(shù)據(jù)結(jié)構(gòu)說明鏈表模板類 :templatevclass Type/ 模板鏈表

3、類class LinkListprivate :HuaffmanTreeNodevType> *head 。 /鏈表的頭結(jié)點(diǎn)public:Type List1000 。LinkList( void >。LinkList( void >。HuaffmanTreeNodevType> *GetHead(> 。/void SetHead(HuaffmanTreeNodevType> *h> 。/void Insert(HuaffmanTreeNodevType> *p> 。 /HuaffmanTreeNode<Type>* lsThe

4、Same(HuaffmanTreeNode<Type> *pa>。 /判斷 pa是否有相同的結(jié) 點(diǎn)，如果有相同返回該結(jié)點(diǎn) ,否則返回 NULL void CreateList(> 。 /創(chuàng)建一個(gè)哈弗曼結(jié)點(diǎn)的鏈表int GetLength(> 。HuaffmanTreeNodevType>* Delete(HuaffmanTreeNodevType> *p> 。 /刪除結(jié)點(diǎn) HuaffmanTreeNodevType>*Copy(> 。 /復(fù)制鏈表bool CheckAllTure(> 。 /檢查是否全部加入哈弗曼樹。棧模板類 :

5、templatevtypename T>/ 模板棧類class Stackprivate :T DataMAX 。int top。public :Stack<T>(> 。/構(gòu)造函數(shù) bool push(T num> 。/進(jìn)棧操作T pop(>。 /出棧操作T Get_top(> 。/ 得到棧頂?shù)脑?bool Empty(> 。/判斷棧是否為空 bool Full(> 。/判斷棧是否已滿 void Clear(>。 /清空棧 。隊(duì)列模板類 :template<typename T>/ 模板隊(duì)列類 class Queue p

6、rivate :T numMAX 。 /隊(duì)列中的數(shù)據(jù)元素 int front,rear 。/ 隊(duì)首，隊(duì)尾的標(biāo)志 public :Queue(void >。/構(gòu)造函數(shù) Queue(void>。 /析構(gòu)函數(shù) void EnQueue(T p>。/ 入隊(duì)操作T DeQueue(> 。 / 出隊(duì)操作 bool IsEmpty(> 。/ 判斷隊(duì)列是否為空 bool IsFull(> 。/ 判斷隊(duì)列是否已滿 void Clear(>。 /清空隊(duì)列 。哈夫曼結(jié)點(diǎn)模板類 :templatevclass Type/模板哈夫曼結(jié)點(diǎn)類 class HuaffmanTreeN

7、odeprivate :int Key。 /該字符出現(xiàn)的次數(shù)；Type Data。/ 輸入的字符元素；HuaffmanTreeNodevType> *parent 。/雙親結(jié)點(diǎn)指針。HuaffmanTreeNodevType> *lchild 。/左孩子結(jié)點(diǎn)指針。HuaffmanTreeNodevType> *rchild 。 /右孩子結(jié)點(diǎn)指針。 int Tag。/記錄該結(jié)點(diǎn)是雙親的左右孩子，左孩子為，有孩子為。HuaffmanTreeNodevType> *next 。 /下一個(gè)結(jié)點(diǎn)，用于鏈表 bool Flag。 /標(biāo)記該結(jié)點(diǎn)是否已經(jīng)計(jì)入哈弗曼樹public:Hua

8、ffmanTreeNode(void > 。 /默認(rèn)構(gòu)造函數(shù)。t,HuaffmanTreeNodevType>HuaffmanTreeNode( intk,Typed,int*p=NULL,HuaffmanTreeNodevType >*l=NULL,HuaffmanTreeNodevType> *r=NULL> 。 /構(gòu)造函數(shù)HuaffmanTreeNode( void >。/默認(rèn)析構(gòu)函數(shù)。int GetKey(> 。/得到該結(jié)點(diǎn)在正文中出現(xiàn)的次數(shù) void SetKey(int key> 。/設(shè)置關(guān)鍵字的次數(shù)Type GetData(>

9、 。 /得到該結(jié)點(diǎn)對應(yīng)的文字編碼void SetData(Type data>。 /設(shè)置結(jié)點(diǎn)的文字編碼 HuaffmanTreeNode<Type> *GetParent(> 。 /得到該結(jié)點(diǎn)的雙親結(jié)點(diǎn)void SetParent(HuaffmanTreeNode<Type> *p> 。/ 設(shè)置雙親結(jié)點(diǎn) HuaffmanTreeNode<Type> *GetLchild(> 。 /得到左孩子結(jié)點(diǎn)void SetLchild(HuaffmanTreeNode<Type> *p> 。 /設(shè)置左孩子結(jié)點(diǎn) HuaffmanT

10、reeNode<Type> *GetRchild(> 。 /得到右孩子結(jié)點(diǎn)void SetRchild(HuaffmanTreeNode<Type> *p> 。/ 設(shè)置右孩子結(jié)點(diǎn) int GetTag(>。/ 得到標(biāo)記void SetTag(int t>。/ 設(shè)置標(biāo)記HuaffmanTreeNode<Type> *GetNext(> 。 /得到下一個(gè)結(jié)點(diǎn) void SetNext(HuaffmanTreeNode<Type> *p> 。 /設(shè)置下一個(gè)結(jié)點(diǎn) bool GetFlag(> return Fla

11、g。 void SetFlag(bool tag>Flag=tag 。 。哈夫曼樹模板類 :templatevclass Type/模板哈夫曼樹類class HuaffmanTreeHuaffmanTreeNodevType> *Root 。 /樹根結(jié)點(diǎn)Queuevint> qu。 /存放密碼public:HuaffmanTree(void >。 HuaffmanTree(void >。pa,HuaffmanTreeNodevType>*void SetRoot(HuaffmanTreeNodevType> *p> this->Root=p

12、 。 HuaffmanTreeNodevType> *GetRoot(> return Root。 HuaffmanTreeNodevType> *Merge(HuaffmanTreeNodevType>* pb> o /合并兩個(gè)結(jié)點(diǎn)void CreateTree(LinkListvType> L1> 。 /創(chuàng)建哈夫曼樹int * GetCode(Type data,LinkListvType> L> 。 /得到編碼void Coding(LinkListvType> L> 。 /編碼void DeCode(LinkListvT

13、ype> L> 。/譯碼函數(shù)void Display(HuaffmanTreeNodevType>*p, int n>。 /遍歷哈夫曼樹 HuaffmanTreeNodevType> *Find(Type data,LinkListvType> L> 。void GetCharFrenquency(LinkListvType> L> 。 /得到每種字符出現(xiàn)的次數(shù) void ShowPriorText(LinkListvType> L> 。void ShowNodeBit(LinkListvType> L> 。 /輸出

14、每個(gè)結(jié)點(diǎn)的哈弗碼編碼 int GetHeight(HuaffmanTreeNodevType>*p> 。/得到樹的高度 。3. 程序的主要流程圖輸入字符串4T統(tǒng)計(jì)每種字符出現(xiàn)的° F次數(shù)4.程序的主要模塊輸出原文本#pragmaonce#include"LinkList.h"#include"Stack.h"輸出Huafuman樹#include"Queue.h" templatevclass Type/ 模板哈夫class HuaffmanTree輸出每個(gè)結(jié)點(diǎn)的Huafumar編碼HuaffmanTreeNod

15、evlype> 說輸根結(jié)點(diǎn)Huafuman密Queuevint> qu。/存放密碼 public:HuaffmanTree(void >。輸出譯文HuaffmanTree( voic。void SetRoot(HuaffmanTreeNode<Type> *p> this->Root=p。HuafanTreeNode<Type> *GetRoot(> return Root o HuaffmanTreeNode>pb> o /合并兩個(gè)結(jié)點(diǎn)void CreateTree(LinkList<Type> L1>

16、 。哈夫曼樹Merge(HuaffmanTreeNode<TOde<Type>int * GetCode(Type data,LinkList<Type> L>。得到編碼void Coding(LinkList<Type> L>。/編碼void DeCode(LinkList<Type> L>。/譯碼函數(shù)void Display(HuaffmanTreeNode<Type>*p, int n>。/遍歷哈夫曼樹HuaffmanTreeNode<Type> *Find(Type data,Link

17、List<Type> L> void GetCharFrenquency(LinkList<Type> L>。/得到每種字符出現(xiàn)的次數(shù) void ShowPriorText(LinkList<Type> L> 。void ShowNodeBit(LinkList<Type> L> 。輸出每個(gè)結(jié)點(diǎn)的哈弗碼編碼int GetHeight(HuaffmanTreeNode<Type>*p> 。/ 得到樹的高度。template<class Type>HuaffmanTree<Type>:

18、HuaffmanTree(>template<class Type>HuaffmanTree<Type>:HuaffmanTree(> this->Root =NULL 。template<class Type>*pa,HuaffmanTreeNode<Type> *HuaffmanTree<Type>:Merge(HuaffmanTreeNode<Type> HuaffmanTreeNode<Type> *pb>HuaffmanTreeNode<Type> *temp= n

19、ew HuaffmanTreeNode<Type>(> 。if (pa->GetKey (><pb->GetKey (>>temp->SetLchild (pa> 。pa->SetTag (0>。temp->SetRchild (pb> 。pb->SetTag (1>。pa->SetFlag (true>。pb->SetFlag (true>。elsetemp->SetLchild (pb> 。pb->SetTag (0>。temp->Se

20、tRchild (pa> 。pa->SetTag (1>。pa->SetFlag (true>。pb->SetFlag (true>。temp->SetData ('0'>。temp->SetKey (pa->GetKey (>+pb->GetKey (>> 。pa->SetParent (temp>。pb->SetParent (temp>。return temp。template<class Type>void HuaffmanTree<Typ

21、e>:CreateTree(LinkList<Type> L1>HuaffmanTreeNode<Type> *pa,*pbpa=L1.GetHead (>->GetNext (> 。 pb=pa->GetNext (> 。while(pb>HuaffmanTreeNode<Type>*temp= new HuaffmanTreeNode<Type>(pa->GetKey(>+pb->GetKey(>, '0',0> 。pa->SetParent(

22、temp>。 pb->SetParent(temp>。if (pa->GetKey(>>pb->GetKey(>> temp->SetLchild(pb> 。 pb->SetTag(0>。 pb->SetFlag(true>。 temp->SetRchild(pa> 。 pa->SetTag(1>。 pa->SetFlag(true>。elsetemp->SetLchild(pa> 。 pa->SetTag(0>。 pa->SetFlag(

23、true>。 temp->SetRchild(pb> 。 pb->SetTag(1>。 pb->SetFlag(true>。L1.Insert (temp> 。 pa=pb->GetNext (> 。if (pa=NULL> this->SetRoot (pb> 。 return 。 pb=pa->GetNext (> 。if (!pb>this ->SetRoot(pa> 。 return。template<class Type>void HuaffmanTree<T

24、ype>:Display(HuaffmanTreeNode<Type> *p, int n>if (p=NULL>return 。 this->Display(p->GetRchild(>,n+1> 。for(int i=0。 i<n。 i+>cout<<'t'。if(p->GetData(>='0'>cout<<p->GetKey(><<endl 。elsecout<<p->GetKey(><<

25、 "("<<p->GetData(><< '>'<<endl。 this->Display(p->GetLchild(>,n+1> 。template<class Type>int *HuaffmanTree<Type>:GetCode(Type data,LinkList<Type> L>Stack<int> s。 int *integer=newint100。HuaffmanTreeNode<Type> *cur

26、rent=L.GetHead(>->GetNext(> 。while(current>if (current->GetData(>=data>break。current=current->GetNext(> 。if(current>while(current->GetParent (>>s.push(current->GetTag(>> 。current=current->GetParent(> 。int i=0 。while (!s.Empty(>>qu.EnQueue (

27、s.pop(>>。i+ 。return integer。template<class Type>HuaffmanTreeNode<Type> * HuaffmanTree<Type>:Find(Type data,LinkList<Type> L> HuaffmanTreeNode<Type> *current=L.GetHead(>->GetNext(> 。 while(current>if (current->GetData(>=data> return current

28、。current=current->GetNext(> 。 return NULL 。template<class Type>void HuaffmanTree<Type>:Coding(LinkList<Type> L>qu.Clear (> 。int i=0 。while(L.List i<123&&L.List i>96>|L.List i=32>GetCode(L.Listi,L> 。 i+ 。 template<class Type> void HuaffmanTre

29、e<Type>:DeCode(LinkList<Type> L>int i=0 。while(!qu.IsEmpty (>>HuaffmanTreeNode<Type> *current= this ->GetRoot (> 。 while(current->GetData (>= '0'>if (qu.DeQueue(>=0>current=current->GetLchild(> 。elsecurrent=current->GetRchild(> 。 co

30、ut<<current->GetData (> 。 template<class Type> void HuaffmanTree<Type>:GetCharFrenquency (LinkList<Type> L> HuaffmanTreeNode<Type> *current=L.GetHead(>->GetNext(> 。 while(current> if (current->GetData(>!= '0'>cout<<current->

31、;GetData(><< " " <<current->GetKey(><<endl 。 current=current->GetNext(> 。template<class Type>void HuaffmanTree<Type>:ShowPriorText(LinkList<Type> L>int i=0 。while(L.List i<123&&L.List i>96>|L.List i=32>cout<<L.

32、Listi 。i+ 。 template<class Type> void HuaffmanTree<Type>:ShowNodeBit(LinkList<Type> L>HuaffmanTreeNode<Type> *current=L.GetHead(>->GetNext(> 。 while(current> if (current->GetData(>!= '0'> cout<<current->GetData (><< " &qu

33、ot; 。 GetCode(current->GetData(>,L> 。 cout<<endl 。 current=current->GetNext(> 。template<class Type>int HuaffmanTree<Type>:GetHeight(HuaffmanTreeNode<Type> *p>if (!p> return 0。 int hl,hr 。hl=GetHeight(p->GetLchild(>> 。 hr=GetHeight(p->GetRchild

34、(>> 。 return hl>hr?+hl:+hr 。三. 上機(jī)結(jié)果及體會(huì)1. 完成情況該程序可以統(tǒng)計(jì)每種字符出現(xiàn)的次數(shù) , 每個(gè)字符的哈夫曼編碼 編碼后的密文以及哈夫曼樹 , 也可以將編碼后的密文進(jìn)行譯文。2. 程序的運(yùn)行結(jié)果 輸入數(shù)據(jù)C:Wi n d owssyste m 3 2c m d. exe慣輸入字符串，以回車結(jié)束!there are three students干采甲a.4.F顯不字符的種類及每種字符岀現(xiàn)的次數(shù)。 E-輸出原來的卒李。mHuf f manf虱吳個(gè)瑩點(diǎn)的H uF £ man 岀整個(gè)文章的Huffman 出擔(dān)碼得到的譯文。0-退出。信選擇

35、要進(jìn)行的操作序號：.按1進(jìn)行的操作按2進(jìn)行的操作按3進(jìn)行的操作哈夫曼樹以旋轉(zhuǎn)90度輸出。其中數(shù)字表示權(quán)值，括號里的字符表示元素的。按4進(jìn)行的操作按5進(jìn)行的操作王乘卑顯示字符的種類及每種字符岀現(xiàn)的汝數(shù)。Huffman 碼。Huf f nan 苗文 c進(jìn)行的操乍序號：5rr:-攢岀擘個(gè)文章的血丘鮎。輸出霹碼得到的譯文。0.i青續(xù)？（繼續(xù)請按任意數(shù)字鍵，退岀請按0）按6進(jìn)行的操作主菜單顯不字符的種類及每種字符岀現(xiàn)的次數(shù)。 2 攢出原來的文本。3.f®Huffman 樹 $翕的HuffmanS碼。iUlUve I 幾章的Huffman文。碼得到的毎文。魯確逐進(jìn)行的操作序號：6there ar

36、e three students是否繼續(xù)？（繼續(xù)請按任意數(shù)字鍵，退岀請按0）按o結(jié)束3. 程序可以改進(jìn)及擴(kuò)充的功能設(shè)計(jì)實(shí)現(xiàn)假想改進(jìn)：將哈夫曼樹以正常的樹的形式輸出擴(kuò)充：可以將漢字進(jìn)行編碼4. 收獲及體會(huì)更加深入的理解數(shù)據(jù)的存儲結(jié)構(gòu)，能更好的利用數(shù)據(jù)的存儲來增 加空間的利用率.通過自己動(dòng)手編寫，將所學(xué)內(nèi)容運(yùn)用到實(shí)際中。四. 參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)C + +實(shí)現(xiàn) 修訂版）繆淮扣、顧訓(xùn)穰、沈俊 編著附錄（源程序：/主函數(shù)#include"HuaffmanTree.h"#include<iostream> usingnamespacestd。int choice。void M

37、une( void >cout<<endl<< "主菜單 "<<endl 。cout<v"1.顯示字符的種類及每種字符出現(xiàn)的次數(shù)。"vvendl。cout<<"2.輸出原來的文本。"vvendl。cout<v"3.輸出 Huffman 樹。"vvendl。coutvv"4.得到每個(gè)結(jié)點(diǎn)的Huffman編碼。"vvendl。coutvv"5.輸出整個(gè)文章的 Huffman密文。"vvendl。coutvv&quo

38、t;6.輸出解碼得到的譯文。"vvendl。coutvv"0.退出。"vvendl。coutvv "請選擇要進(jìn)行的操作序號：”。cin>>choice 。void main(>/ 主函數(shù)LinkListv char> L 。L.CreateList (> 。HuaffmanTreevchar> obj。obj.CreateTree(L>。Mune(>。while(choice>0&&choicev7>switch(choice>case 1:obj.GetCharFrenq

39、uency(L> 。 break。case 2:obj.ShowPriorText(L> 。 break。case 3:obj.Display(obj.GetRoot(>,1> 。 break。case 4:obj.ShowNodeBit(L> 。 break。case 5:obj.Coding(L> 。 break。case 6:obj.DeCode(L> 。 break。default :break。coutvv"是否繼續(xù)？ v繼續(xù)請按任意數(shù)字鍵，退出請按)cin>>choice 。if(choice=0> break。

40、elsesystem("cls">。Mune(> 。continue。/ 鏈表類#pragmaonce #include"HuaffmanTreeNode.h"templatevclass Type/ 模板鏈表類class LinkList private :HuaffmanTreeNodevType> *head 。 /鏈表的頭結(jié)點(diǎn)public:Type List1000 。LinkList( void >。LinkList( void >。HuaffmanTreeNodevType> *GetHead(> 。

41、/ void SetHead(HuaffmanTreeNodevType> *h> 。/ void Insert(HuaffmanTreeNodevType> *p> 。 /HuaffmanTreeNode<Type>* lsTheSame(HuaffmanTreeNode<Type> *pa>。 /判斷 pa是否有相同的結(jié) 點(diǎn)，如果有相同返回該結(jié)點(diǎn) ,否則返回 NULL void CreateList(> 。 /創(chuàng)建一個(gè)哈弗曼結(jié)點(diǎn)的鏈表int GetLength(> 。HuaffmanTreeNodevType>* De

42、lete(HuaffmanTreeNodevType> *p> 。 /刪除結(jié)點(diǎn) HuaffmanTreeNodevType>*Copy(> 。 /復(fù)制鏈表bool CheckAllTure(> 。 /檢查是否全部加入哈弗曼樹。templatevclass Type>LinkListvType>:LinkList(> /構(gòu)造函數(shù) this->head =new HuaffmanTreeNodevType>(> 。this->head ->SetKey (0>。this->head ->SetLchil

43、d (NULL> 。 this->head ->SetNext (NULL> 。 this->head ->SetParent (NULL> 。 this->head ->SetRchild (NULL> 。templatevclass Type>LinkListvType>:LinkList(> templatevclass Type> HuaffmanTreeNodevType> *LinkListvType>:GetHead(> /返回頭結(jié)點(diǎn)的函數(shù)returnthis->headt

44、emplate<class Type>void LinkList<Type>:SetHead(HuaffmanTreeNode<Type> *h> / 設(shè)置頭結(jié)點(diǎn)的函數(shù)實(shí)現(xiàn)this->head =h 。template<class Type>HuaffmanTreeNode<Type>* LinkList<Type>:IsTheSame(HuaffmanTreeNode<Type> *pa> / 判斷兩個(gè)結(jié)點(diǎn)是否 存在于鏈表中HuaffmanTreeNode<Type> *curr

45、ent= this ->GetHead (>->GetNext (> 。/ 取到第一個(gè)有值的結(jié)點(diǎn) while(current>if (current->GetData (>=pa->GetData (>>return current 。elsecurrent=current->GetNext (> 。return NULL 。template<class Type>void LinkList<Type>:Insert (HuaffmanTreeNode<Type>* p>if (t

46、his ->GetHead (>->GetNext (>=NULL>this->GetHead(>->SetNext(p> 。return 。HuaffmanTreeNode<Type> *current= this->lsTheSame (p>。 /判斷是否有與 p相同的結(jié)點(diǎn)if (NULL=current|current->GetData (>= '0'> /沒有相同的結(jié)點(diǎn)，作為第一個(gè)結(jié)點(diǎn)放在鏈表的第一個(gè)位置HuaffmanTreeNode<Type> *pa= th

47、is->GetHead (>->GetNext (> 。HuaffmanTreeNode<Type> *pb=pa->GetNext (> 。while(pb>if (pb->GetKey(>>p->GetKey(>>pa->SetNext(p>。p->SetNext(pb> 。break。pa=pb。pb=pb->GetNext(> 。 pa->SetNext (p> 。 p->SetNext (pb> 。/*p->SetNext (th

48、is->GetHead (>->GetNext (>> 。 this->GetHead(>->SetNext (p> 。 */ elseif(current->GetData (>!= '0'> / 有相同的結(jié)點(diǎn) int a=current->GetKey (> 。 +a。current->SetKey (a> 。 /重新設(shè)置結(jié)點(diǎn)的關(guān)鍵字 int flag=1 。 while(flag=1>HuaffmanTreeNode<Type> *pre= this->

49、GetHead (>->GetNext (> HuaffmanTreeNode<Type> *Current=pre->GetNext (> 。flag=0 。while(Current> /if(pre->GetKey(>=Current->GetKey (>> 。 if (pre->GetKey(>>Current->GetKey(>>int temp=pre->GetKey (> 。Type data=pre->GetData (> 。 bool fl

50、aging=pre->GetFlag (> 。pre->SetKey (Current->GetKey (>> 。 pre->SetData (Current->GetData (>> 。 pre->SetFlag (Current->GetFlag (>> 。Current->SetKey (temp> 。 Current->SetData (data> 。Current->SetFlag (flaging> 。 flag=1 。 pre=Current 。 Current

51、=Current->GetNext(> 。 template<class Type> void LinkList<Type>:CreateList(>coutvv"請輸入字符串，以回車結(jié)束！ "vvendl。Type p。int i=0。p=cin.get (> 。Listi=p i+ 。while(p!= 'n'> HuaffmanTreeNode<Type> *current= new HuaffmanTreeNode<Type>(1,p,0> 。this->Ins

52、ert (current> 。p=cin.get (> 。Listi=p 。 i+ 。 template<class Type> int LinkList<Type>:GetLength(>HuaffmanTreeNode<Type> *current->GetHead(>->GetNext(> 。int num=0 。 while(current> num+。 current=current->GetNext(> 。return num。template<class Type>Huaf

53、fmanTreeNode<Type>* LinkList<Type>:Delete(HuaffmanTreeNode<Type> *p> / 取出鏈表中的前兩個(gè)數(shù) 據(jù)元素HuaffmanTreeNode<Type> *pre,*current,*temp= new HuaffmanTreeNode<Type>(> 。 pre=this->GetHead(> 。current=pre->GetNext(> 。 while(current>if (current->GetFlag (>

54、= false>current->SetFlag (true>。return current 。elsecurrent=current->GetNext(> 。return NULL 。template<class Type>HuaffmanTreeNode<Type>*LinkList<Type>:Copy(>HuaffmanTreeNode<Type> *pa,*pb 。LinkList<Type> L 。pa=this->GetHead(>->GetNext(> 。wh

55、ile(pa>pb=new HuaffmanTreeNode<Type>(> 。 pb->SetKey(pa->GetKey(>> 。 pb->SetData (pa->GetData (>> 。L.Insert(pb> 。 pa=pa->GetNext (> 。return L.GetHead (> 。template<class Type>bool LinkList<Type>:CheckAllTure(>HuaffmanTreeNode<Type> *

56、current= this ->GetHead(>->GetNext(> while(current>if (current->GetFlag(>= false>returnfalse。current=current->GetNext(> 。returntrue。/ 棧類#include<iostream>#define MAX 2000 / 定義棧的最大存儲量為 usingnamespacestd。template<typename T>/ 模板棧類class Stackprivate :T DataMAX

57、。int top 。public :Stack<T>(> 。/構(gòu)造函數(shù)bool push(T num> 。/進(jìn)棧操作T pop(>。 /出棧操作T Get_top(> 。/ 得到棧頂?shù)脑豣ool Empty(> 。/判斷棧是否為空bool Full(> 。/判斷棧是否已滿void Clear(>。 /清空棧。/*輸入：無前置條件：無動(dòng)作：初始化棧輸出：無后置條件：棧被創(chuàng)建*/template<typename T>Stack<T>:Stack(>this->top =-1 。/*輸入：輸入要入棧的元素

58、前置條件：棧未滿 動(dòng)作：向棧中增加一個(gè)元素 輸出：無后置條件：棧的元素增加一個(gè)*/template<typename T>bool Stack<T>:push(T num>if (this ->Full (>>returnfalse。elsethis->top + 。this->Data top=num 。 returntrue。/*輸入：無前置條件：棧不為空 動(dòng)作：輸出棧中的一個(gè)元素 輸出：棧的元素 后置條件：棧中的元素個(gè)數(shù)減少一個(gè) */ template<typename T>T Stack<T>:pop(

59、>if (this ->Empty (>> returnfalse。 elseT temp=this ->Data top 。 cout<<this->Data top 。 top-。 return temp。/*輸入：無 前置條件：存在頂部節(jié)點(diǎn) 動(dòng)作：輸出頂部節(jié)點(diǎn) 輸出：頂部節(jié)點(diǎn) 后置條件：無"<<endl*/ template<typename T> T Stack<T>:Get_top(> if (this ->Empty (>> coutvv"棧為空，不能得到

60、頂部節(jié)點(diǎn)! return NULL 。elsereturnthis->Data top 。/*輸入：無 前置條件：無 動(dòng)作：判斷棧是否為空 輸出：無 后置條件：無*/template<typename T>bool Stack<T>:Empty(>return top=-1。/*輸入：無前置條件：無 動(dòng)作：判斷棧是否滿了 輸出：無后置條件：無*/template<typename T>bool Stack<T>:Full(>return top=MAX-1 。/*輸入：無 前置條件：無 動(dòng)作：清空棧中的元素 輸出：無 后置條件：

61、棧為空*/ template<typename T> void Stack<T>:Clear (> this->top=-1 。/*輸入：前置條件：動(dòng)作：輸出：后置條件：*/ 隊(duì)列類#pragmaonce template<typename T>/ 模板隊(duì)列類 class Queueprivate :T numMAX 。 /隊(duì)列中的數(shù)據(jù)元素 int front,rear 。/ 隊(duì)首，隊(duì)尾的標(biāo)志 public :Queue(void >。/構(gòu)造函數(shù)Queue(void>。 /析構(gòu)函數(shù)void EnQueue(T p>。/ 入隊(duì)操作

62、T DeQueue(> 。 / 出隊(duì)操作 bool IsEmpty(> 。/ 判斷隊(duì)列是否為空 bool IsFull(> 。/ 判斷隊(duì)列是否已滿 void Clear(>。 /清空隊(duì)列。 template<typename T> Queue<T>:Queue(>this->front=-1 。 /將標(biāo)記初始化為 -1 this->rear=-1。template<typename T>Queue<T>:Queue(> / 析構(gòu)函數(shù)的實(shí)現(xiàn) template<typename T> voi

63、d Queue<T>:EnQueue(T p> / 入隊(duì)函數(shù)的實(shí)現(xiàn)if (this ->IsFull(>> /如果隊(duì)列已滿，則退出程序 cout<<"Stack is full !" <<endl 。 exit(1> 。else/如果沒有滿，則將元素入隊(duì) rear=(rear+1>%MAX 。 numrear=p 。 template<typename T>T Queue<T>:DeQueue(> /出隊(duì)的函數(shù)實(shí)現(xiàn) if(this->IsEmpty(>> /如果隊(duì)列為空則返回 NULL cout<<"Queue is empty !" <<endl。return NULL 。else/如果隊(duì)列不為空，則將隊(duì)首元素出對 front=(front+1>%MAX 。T p=numfront 。 return p。 template<typename T>bool Queue<T>:IsEmpty(> / 判斷隊(duì)列是否為空的函數(shù)實(shí)現(xiàn)if (front=rear> ret