Chinaunix首页 | 论坛 | 博客
  • 博客访问: 631418
  • 博文数量: 1008
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 5175
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-31 09:44
文章分类
文章存档

2012年(1008)

我的朋友

分类:

2012-08-01 11:20:47

  1. /******************************************************************************
  2. * 文件:SeqStack.h
  3. * 功能:线性表顺序存储
  4. * 说明:栈顺序存储结构的线性表类定义
  5.         及类成员函数包括压栈、出栈等函数的实现
  6. * 时间:2011-4-4                                              
  7. Author: Lzy
  8. *******************************************************************************/
  9. #include <iostream.h>
  10. #include "LinearList.h"

  11. /********************************************************************
  12. * 类名: 类模板SeqStack
  13. * 功能: 栈顺序表类定义
  14. * 说明:栈顺序表相关操作函数的实现
  15. /********************************************************************/
  16. template<class T>
  17. class SeqStack
  18. {
  19. private:
  20.     int top;                                    //栈顶
  21.     int MaxSize;                                //最大的栈元素
  22.     T *stack;                                    //栈数组

  23. public:
  24.     SeqStack(int MaxStackSize = 10);
  25.     ~SeqStack() {if(stack) delete[]stack;}
  26.     virtual bool IsEmpty() const {return top == -1;}
  27.     virtual bool IsFull() const {return top == MaxSize-1;}
  28.     T & Getop() const;                            //获得栈顶元素
  29.     virtual bool Push(const T &x);                //元素x入栈
  30.     virtual bool Pop(T &x);                        //元素出栈,保存在X
  31.     virtual bool Pop();                            //元素出栈
  32.     virtual void ClearStack(){top = -1;}        //清除栈中所有元素
  33.     virtual void Output(ostream& out) const;    //输出栈元素
  34. };

  35. /********************************************************************
  36. * 所属类名: SeqStack
  37. * 成员名称:SeqStack
  38. * 函数功能:构造函数
  39. * 说    明:用于初始化栈
  40. /********************************************************************/
  41. template<class T>
  42. SeqStack<T>::SeqStack(int MaxStackSize)
  43. {
  44.     MaxSize = MaxStackSize;
  45.     stack = new T[MaxSize];                        //初始化栈大小
  46.     if(stack == NULL)
  47.         throw NoMem();                            //抛出异常
  48.     top = -1;                                    
  49. }

  50. /********************************************************************
  51. * 所属类名: SeqStack
  52. * 成员名称:Getop()
  53. * 函数功能:获得栈顶元素
  54. * 说    明:
  55. /********************************************************************/
  56. template<class T>
  57. T & SeqStack<T>::Getop() const
  58. {
  59.     if(IsEmpty())
  60.         throw OutOfBounds();                //栈为空
  61.     else
  62.         return stack[top];
  63. }

  64. /********************************************************************
  65. * 所属类名: SeqStack
  66. * 成员名称:Push
  67. * 函数功能:压栈
  68. * 说    明:把X放入栈顶
  69. /********************************************************************/
  70. template<class T>
  71. bool SeqStack<T>::Push(const T &x)
  72. {
  73.     if(IsFull())
  74.         throw OutOfBounds();                //栈已满
  75.     stack[++top] = x;                        //数据存入
  76.     return true;
  77. }

  78. /********************************************************************
  79. * 所属类名: SeqStack
  80. * 成员名称:Pop
  81. * 函数功能:出栈
  82. * 说    明:删除栈顶元素,保存在X中
  83. /********************************************************************/
  84. template<class T>
  85. bool SeqStack<T>::Pop(T &x)
  86. {
  87.     if(IsEmpty())
  88.         throw OutOfBounds();                //栈为空
  89.     x = stack[top--];                        //数据弹出
  90.     return true;
  91. }

  92. /********************************************************************
  93. * 所属类名: SeqStack
  94. * 成员名称:Pop
  95. * 函数功能:出栈
  96. * 说    明:删除栈顶元素,数据不保存
  97. /********************************************************************/
  98. template<class T>
  99. bool SeqStack<T>::Pop()
  100. {
  101.     if(IsEmpty())
  102.         throw OutOfBounds();                //栈为空
  103.      top--;                                    //删除数据
  104.     return true;
  105. }

  106. /********************************************************************
  107. * 所属类名: SeqStack
  108. * 成员名称:<<
  109. * 函数功能:<<重载
  110. * 说    明:
  111. /********************************************************************/
  112. template<class T>
  113. ostream& operator<<(ostream& out, const SeqStack<T>& x)
  114. {
  115.     x.Output(out);
  116.     return out;
  117. }

  118. /********************************************************************
  119. * 所属类名: SeqStack
  120. * 成员名称:Output
  121. * 函数功能:把表输送至输出流
  122. * 说    明:
  123. /********************************************************************/
  124. template<class T>
  125. void SeqStack<T>::Output(ostream& out) const
  126. {
  127.     for(int i = 0; i <=top; i++)
  128.         out<<stack[i]<<" ";
  129. }
  1. /******************************************************************************
  2. * 文件:
  3. * 功能:线性表测试程序
  4. * 说明:
  5. * 时间:2011-4-4                                              
  6. Author: Lzy
  7. *******************************************************************************/
  8. #include <iostream.h>
  9. #include "SeqStack.h"

  10. void main()
  11. {
  12.     SeqStack<int>L(20);
  13.     for(int i = 1; i < 21; ++i)
  14.         L.Push(i);
  15.     int z;
  16.     for(i = 1; i < 21; i++)
  17.     {
  18.          L.Pop(z);
  19.         cout<<z<<" ";
  20.     }
  21.     cout<<endl;
  22. }
阅读(146) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~