哈夫曼编、译码器

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