链栈

溯影

《数据结构C++语言描述》清华大学出版社  任燕编著

小弟改遍了一些程序使之可以作为程序来运行
同时小弟还是老样子重载输出运算符，便于输出链栈每个结点的数据域中的数据
程序小弟调试过没有错

还行大神赐教！！！

1. #include <iostream>
   
2. #include <cstdlib>
   
3. #include <assert.h>
   
4. #include <cstdbool>
   
5. using namespace std;
   
6. 
   
7. template <typename elemtype>
   
8. class LinkStack{
   
9. public:
   
10.         class LinkNode{
    
11.         public:
    
12.                 elemtype data;
    
13.                 LinkNode *next;
    
14.         };
    
15. 
    
16.         typedef LinkNode* NodePointer;
    
17. 
    
18.         //把链栈置空
    
19.         void clear();
    
20. 
    
21.         //求链栈中结点的个数
    
22.         int getLength();
    
23. 
    
24.         //判断链栈是否为空
    
25.         bool isEmpty();
    
26. 
    
27.         //读取栈顶结点的数据域
    
28.         bool getTop(elemtype &e);
    
29. 
    
30.         //重载赋值运算符
    
31.         LinkStack operator=(LinkStack right);
    
32. 
    
33.         //弹出栈顶结点
    
34.         bool pop(elemtype &e);
    
35. 
    
36.         //在栈顶压入一个数据域为e的结点
    
37.         void push(elemtype e);
    
38. 
    
39.         LinkStack();//链栈构造函数
    
40. 
    
41.         //析构函数
    
42.         virtual ~LinkStack();
    
43. 
    
44.         //链栈拷贝构造函数
    
45.         LinkStack(LinkStack &other);
    
46. 
    
47.         template <typename out_put>
    
48.         friend ostream& operator<<(ostream& out, LinkStack<out_put> other);
    
49. 
    
50. protected:
    
51.         NodePointer top;//链栈栈顶指针
    
52. };
    
53. 
    
54. template <typename elemtype>
    
55. void LinkStack<elemtype>::clear(){
    
56.         NodePointer s;
    
57. 
    
58.         while (top){
    
59.                 s = top;
    
60.                 top = top->next;
    
61.                 delete s;
    
62.         }
    
63.         top = NULL;
    
64. }
    
65. 
    
66. template <typename elemtype>
    
67. int LinkStack<elemtype>::getLength(){
    
68.         int length = 0;
    
69.         NodePointer p = this->top;
    
70. 
    
71.         while (p){
    
72.                 length++;
    
73.                 p = p->next;
    
74.         }
    
75.         return length;
    
76. }
    
77. 
    
78. template <typename elemtype>
    
79. bool LinkStack<elemtype>::getTop(elemtype &e){
    
80.         if (!top){
    
81.                 return false;
    
82.         }
    
83.         else{
    
84.                 e = top->data;
    
85.                 return true;
    
86.         }
    
87. }
    
88. 
    
89. //判断链栈是否为空
    
90. template <typename elemtype>
    
91. bool LinkStack<elemtype>::isEmpty(){
    
92.         return top ? false : true;
    
93. }
    
94. 
    
95. //重载赋值运算符
    
96. template <typename elemtype>
    
97. LinkStack<elemtype> LinkStack<elemtype>::operator=(LinkStack<elemtype> right){
    
98.         NodePointer p;//左边链栈当前处理结点的指针
    
99. 
    
100.         NodePointer rp = right.top;
     
101.         NodePointer s;//预指向左边链栈新节点的指针
     
102. 
     
103.         if (this != &right){
     
104.                 clear();
     
105.                 while (rp){
     
106.                         s = new LinkNode;
     
107.                         assert(s != 0);
     
108.                         s->data = rp->data;
     
109. 
     
110.                         if (!top){
     
111.                                 top = s;
     
112.                         }
     
113.                         else{
     
114.                                 p->next = s;
     
115.                         }
     
116.                         p = s;
     
117.                         rp = rp->next;
     
118.                 }
     
119.                 if (p){
     
120.                         p->next = NULL;
     
121.                 }
     
122.         }
     
123.         return *this;//返回对象
     
124. }
     
125. 
     
126. //弹栈
     
127. template <typename elemtype>
     
128. bool LinkStack<elemtype>::pop(elemtype &e){
     
129.         NodePointer s = top;
     
130.         if (!top){
     
131.                 return false;
     
132.         }
     
133.         else{
     
134.                 e = top->data;
     
135.                 top = top->next;
     
136.                 delete s;
     
137.         }
     
138.         return true;
     
139. }
     
140. 
     
141. 
     
142. //压栈
     
143. template <typename elemtype>
     
144. void LinkStack<elemtype>::push(elemtype e){
     
145.         NodePointer s;
     
146. 
     
147.         s = new LinkNode;
     
148.         assert(s != 0);
     
149.         s->data = e;
     
150.         s->next = top;
     
151.         top = s;
     
152. }
     
153. 
     
154. template <typename elemtype>
     
155. LinkStack<elemtype>::LinkStack(){
     
156.         top = NULL;
     
157. }
     
158. 
     
159. template <typename elemtype>
     
160. LinkStack<elemtype>::~LinkStack(){
     
161.         clear();
     
162.         cout << "清理栈完毕" << endl;
     
163. }
     
164. 
     
165. //链栈拷贝构造函数
     
166. template <typename elemtype>
     
167. LinkStack<elemtype>::LinkStack(LinkStack<elemtype> &other){
     
168.         NodePointer p;
     
169.         NodePointer op = other.top;
     
170. 
     
171.         NodePointer s;
     
172. 
     
173.         top = p = NULL;
     
174. 
     
175.         while (op){//这些代码你懂的
     
176.                 s = new LinkNode;
     
177.                 assert(s != 0);
     
178.                 s->data = op->data;
     
179.                 if (!top){
     
180.                         top = s;
     
181.                         cout << "第一个结点插入中" << endl;
     
182.                 }
     
183.                 else{
     
184.                         p->next = s;
     
185.                         cout << "结点插入中" << endl;
     
186.                 }
     
187.                 p = s;
     
188.                 op = op->next;
     
189.         }
     
190.         if (p){
     
191.                 p->next = NULL;//链栈栈底结点的指针置空
     
192.         }
     
193. }
     
194. 
     
195. //输出运算符重载
     
196. template <typename out_put>
     
197. ostream& operator<<(ostream& out, LinkStack<out_put> other){
     
198.         LinkStack<out_put>::NodePointer s = other.top;
     
199.         while (s){
     
200.                 out << "值:" << s->data << endl;
     
201.                 s = s->next;
     
202.         }
     
203.         return out;
     
204. }
     
205. 
     
206. int main(void){
     
207.         LinkStack<int> s1;
     
208.         for (int i = 1; i < 11; i++){
     
209.                 s1.push(i);//测试压栈成员函数
     
210.         }
     
211.         cout << "链栈插入完毕:" << endl;
     
212.         cout << "链栈为:" << endl;
     
213.         cout << s1 << endl;//测试重载输出运算符
     
214.         cout << "弹栈:" << endl;
     
215.         for (int i = 1; i < 11; i++){
     
216.                 int e;
     
217.                 if (s1.pop(e)){//测试弹栈成员函数
     
218.                         cout << e << endl;
     
219.                 }
     
220.         }
     
221. 
     
222.         LinkStack<int> s2;
     
223.         for (int i = 1; i <= 5; i++){
     
224.                 s2.push(i);
     
225.         }
     
226. 
     
227.         s1 = s2;//测试赋值运算符的重载
     
228. 
     
229.         cout << "s1为:" << endl;
     
230.         cout << s1;
     
231. 
     
232. 
     
233.         return 0;
     
234. }
     
235. 
     
236. 
     
237. 
     

复制代码

运行结果:
链栈插入完毕:
链栈为:
第一个结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
值:10
值:9
值:8
值:7
值:6
值:5
值:4
值:3
值:2
值:1
清理栈完毕

弹栈:
10
9
8
7
6
5
4
3
2
1
第一个结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
第一个结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
清理栈完毕
清理栈完毕
s1为:
第一个结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
值:5
值:4
值:3
值:2
值:1
清理栈完毕
清理栈完毕
清理栈完毕
请按任意键继续. . .