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

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

3、類class LinkListprivate :HuaffmanTreeNodevType> *head 。 /鏈表的頭結點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是否有相同的結 點，如果有相同返回該結點 ,否則返回 NULL void CreateList(> 。 /創建一個哈弗曼結點的鏈表int GetLength(> 。HuaffmanTreeNodevType>* Delete(HuaffmanTreeNodevType> *p> 。 /刪除結點 HuaffmanTreeNodevType>*Copy(> 。 /復制鏈表bool CheckAllTure(> 。 /檢查是否全部加入哈弗曼樹。棧模板類 :

5、templatevtypename T>/ 模板棧類class Stackprivate :T DataMAX 。int top。public :Stack<T>(> 。/構造函數 bool push(T num> 。/進棧操作T pop(>。 /出棧操作T Get_top(> 。/ 得到棧頂的元素 bool Empty(> 。/判斷棧是否為空 bool Full(> 。/判斷棧是否已滿 void Clear(>。 /清空棧 。隊列模板類 :template<typename T>/ 模板隊列類 class Queue p

6、rivate :T numMAX 。 /隊列中的數據元素 int front,rear 。/ 隊首，隊尾的標志 public :Queue(void >。/構造函數 Queue(void>。 /析構函數 void EnQueue(T p>。/ 入隊操作T DeQueue(> 。 / 出隊操作 bool IsEmpty(> 。/ 判斷隊列是否為空 bool IsFull(> 。/ 判斷隊列是否已滿 void Clear(>。 /清空隊列 。哈夫曼結點模板類 :templatevclass Type/模板哈夫曼結點類 class HuaffmanTreeN

7、odeprivate :int Key。 /該字符出現的次數；Type Data。/ 輸入的字符元素；HuaffmanTreeNodevType> *parent 。/雙親結點指針。HuaffmanTreeNodevType> *lchild 。/左孩子結點指針。HuaffmanTreeNodevType> *rchild 。 /右孩子結點指針。 int Tag。/記錄該結點是雙親的左右孩子，左孩子為，有孩子為。HuaffmanTreeNodevType> *next 。 /下一個結點，用于鏈表 bool Flag。 /標記該結點是否已經計入哈弗曼樹public:Hua

8、ffmanTreeNode(void > 。 /默認構造函數。t,HuaffmanTreeNodevType>HuaffmanTreeNode( intk,Typed,int*p=NULL,HuaffmanTreeNodevType >*l=NULL,HuaffmanTreeNodevType> *r=NULL> 。 /構造函數HuaffmanTreeNode( void >。/默認析構函數。int GetKey(> 。/得到該結點在正文中出現的次數 void SetKey(int key> 。/設置關鍵字的次數Type GetData(>

9、 。 /得到該結點對應的文字編碼void SetData(Type data>。 /設置結點的文字編碼 HuaffmanTreeNode<Type> *GetParent(> 。 /得到該結點的雙親結點void SetParent(HuaffmanTreeNode<Type> *p> 。/ 設置雙親結點 HuaffmanTreeNode<Type> *GetLchild(> 。 /得到左孩子結點void SetLchild(HuaffmanTreeNode<Type> *p> 。 /設置左孩子結點 HuaffmanT

10、reeNode<Type> *GetRchild(> 。 /得到右孩子結點void SetRchild(HuaffmanTreeNode<Type> *p> 。/ 設置右孩子結點 int GetTag(>。/ 得到標記void SetTag(int t>。/ 設置標記HuaffmanTreeNode<Type> *GetNext(> 。 /得到下一個結點 void SetNext(HuaffmanTreeNode<Type> *p> 。 /設置下一個結點 bool GetFlag(> return Fla

11、g。 void SetFlag(bool tag>Flag=tag 。 。哈夫曼樹模板類 :templatevclass Type/模板哈夫曼樹類class HuaffmanTreeHuaffmanTreeNodevType> *Root 。 /樹根結點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 /合并兩個結點void CreateTree(LinkListvType> L1> 。 /創建哈夫曼樹int * GetCode(Type data,LinkListvType> L> 。 /得到編碼void Coding(LinkListvType> L> 。 /編碼void DeCode(LinkListvT

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

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

15、evlype> 說輸根結點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 /合并兩個結點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>。/譯碼函數void Display(HuaffmanTreeNode<Type>*p, int n>。/遍歷哈夫曼樹HuaffmanTreeNode<Type> *Find(Type data,Link

17、List<Type> L> void GetCharFrenquency(LinkList<Type> L>。/得到每種字符出現的次數 void ShowPriorText(LinkList<Type> L> 。void ShowNodeBit(LinkList<Type> L> 。輸出每個結點的哈弗碼編碼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 。三. 上機結果及體會1. 完成情況該程序可以統計每種字符出現的次數 , 每個字符的哈夫曼編碼 編碼后的密文以及哈夫曼樹 , 也可以將編碼后的密文進行譯文。2. 程序的運行結果 輸入數據C:Wi n d owssyste m 3 2c m d. exe慣輸入字符串，以回車結束!there are three students干采甲a.4.F顯不字符的種類及每種字符岀現的次數。 E-輸出原來的卒李。mHuf f manf虱吳個瑩點的H uF £ man 岀整個文章的Huffman 出擔碼得到的譯文。0-退出。信選擇

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

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

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

38、t;6.輸出解碼得到的譯文。"vvendl。coutvv"0.退出。"vvendl。coutvv "請選擇要進行的操作序號：”。cin>>choice 。void main(>/ 主函數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"是否繼續？ v繼續請按任意數字鍵，退出請按)cin>>choice 。if(choice=0> break。

40、elsesystem("cls">。Mune(> 。continue。/ 鏈表類#pragmaonce #include"HuaffmanTreeNode.h"templatevclass Type/ 模板鏈表類class LinkList private :HuaffmanTreeNodevType> *head 。 /鏈表的頭結點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是否有相同的結 點，如果有相同返回該結點 ,否則返回 NULL void CreateList(> 。 /創建一個哈弗曼結點的鏈表int GetLength(> 。HuaffmanTreeNodevType>* De

42、lete(HuaffmanTreeNodevType> *p> 。 /刪除結點 HuaffmanTreeNodevType>*Copy(> 。 /復制鏈表bool CheckAllTure(> 。 /檢查是否全部加入哈弗曼樹。templatevclass Type>LinkListvType>:LinkList(> /構造函數 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(> /返回頭結點的函數returnthis->headt

44、emplate<class Type>void LinkList<Type>:SetHead(HuaffmanTreeNode<Type> *h> / 設置頭結點的函數實現this->head =h 。template<class Type>HuaffmanTreeNode<Type>* LinkList<Type>:IsTheSame(HuaffmanTreeNode<Type> *pa> / 判斷兩個結點是否 存在于鏈表中HuaffmanTreeNode<Type> *curr

45、ent= this ->GetHead (>->GetNext (> 。/ 取到第一個有值的結點 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相同的結點if (NULL=current|current->GetData (>= '0'> /沒有相同的結點，作為第一個結點放在鏈表的第一個位置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'> / 有相同的結點 int a=current->GetKey (> 。 +a。current->SetKey (a> 。 /重新設置結點的關鍵字 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"請輸入字符串，以回車結束！ "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> / 取出鏈表中的前兩個數 據元素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>(> 。/構造函數bool push(T num> 。/進棧操作T pop(>。 /出棧操作T Get_top(> 。/ 得到棧頂的元素bool Empty(> 。/判斷棧是否為空bool Full(> 。/判斷棧是否已滿void Clear(>。 /清空棧。/*輸入：無前置條件：無動作：初始化棧輸出：無后置條件：棧被創建*/template<typename T>Stack<T>:Stack(>this->top =-1 。/*輸入：輸入要入棧的元素

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

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

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

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

62、T DeQueue(> 。 / 出隊操作 bool IsEmpty(> 。/ 判斷隊列是否為空 bool IsFull(> 。/ 判斷隊列是否已滿 void Clear(>。 /清空隊列。 template<typename T> Queue<T>:Queue(>this->front=-1 。 /將標記初始化為 -1 this->rear=-1。template<typename T>Queue<T>:Queue(> / 析構函數的實現 template<typename T> voi

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