实验目标：
（1）将e入栈
（2）用e返回出栈元素
（3）返回栈顶元素
（4）清空栈，变为空栈
（5）遍历栈元素（从栈顶到栈底）
（6）回文是指正读反读均相同的字符序列，如”acdca”、”dceecd”均是回文，但”book”不是回文。试写一个算法判定输入的字符串是否为回文，并将结果输出，例如：”acdca”是回文
这里发现，链栈可以直接用链表修改获得，甚至链表的头插法就是天然的入栈过程
实验代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
| #include<bits/stdc++.h>>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int SElemType;
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStack;
Status InitStack(LinkStack &S){
S=(struct StackNode*)malloc(sizeof(struct StackNode));
if(!S->data) return FALSE;
S->data=0;
S->next=NULL;
return OK;
}
Status Push(LinkStack &S,char e){
struct StackNode* newNode=(struct StackNode*)malloc(sizeof(struct StackNode));
if(!newNode->data) return FALSE;
newNode->data=e;
newNode->next=S->next;
S->next=newNode;
}
Status Pop(LinkStack &S,SElemType &e){
struct StackNode* posNode=S->next;
if(posNode==NULL) return FALSE;
S->next=posNode->next;
posNode=S->next;
e=posNode->data;
return e;
}
Status GetTop(LinkStack &S,SElemType &e){
struct StackNode* posNode=S->next;
if(posNode==NULL) return FALSE;
e=posNode->data;
cout<<e<<endl;
return e;
}
void Clear(LinkStack &S){
struct StackNode* p=S->next;
struct StackNode* q;
if(p==NULL) cout<<"该链表为空，不需删除！"<<endl;
while(p != NULL){
q=p->next;
free(p);
p=q;
}
S->next==NULL;
cout<<"清空成功！"<<endl;
}
void Traverse(LinkStack &S){
struct StackNode* pmove=S->next;
if(pmove==NULL) cout<<"遍历失败该链表为空"<<endl;
while(pmove){
int x;
x=pmove->data;
cout<<x<<' ';
pmove=pmove->next;
}
cout<<endl;
}
void HuiWen(){
LinkStack S;
InitStack(S);
int n;
char WenZi;
int flag=1;
cout<<"请输入本次要输入的字符的个数：";
cin>>n;
cout<<endl<<"请输入要检查的数列：";
for(int i=1;i<=n;i++){
cin>>WenZi;
Push(S,WenZi);
}
cout<<endl;
for(int i=1;i<=n;i++){
struct StackNode* p=S->next;
struct StackNode* q=S->next;
for(int j=1;j<n-i+1;j++){
p=p->next;
}
if(p->data!=q->data){
cout<<"不是回文数列！"<<endl;
flag=0;
break;
}
q=q->next;
}
if(flag==1) cout<<"是回文数列!"<<endl;
}
int main()
{
LinkStack S;
int e;
while(1){
cout<<endl;
cout<<"**1,初始化栈"<<endl;
cout<<"**2,将元素e入栈"<<endl;
cout<<"**3,出栈，用e返回出栈元素"<<endl;
cout<<"**4,返回栈顶元素"<<endl;
cout<<"**5,清空栈"<<endl;
cout<<"**6,遍历栈元素（从栈底到栈顶）"<<endl;
cout<<"**7,测试回文列"<<endl;
cout<<"**0,退出系统"<<endl;
int choice;
cout<<"请输入要进行的操作：";
cin>>choice;
cout<<endl;
switch(choice){
case 1:InitStack(S);break;
case 2:{
int n;
cout<<"请输入本次入栈的元素个数：";
cin>>n;
cout<<endl<<"请输入要插入的元素：";
for(int i=1;i<=n;i++){
cin>>e;
Push(S,e);
}
cout<<"入栈成功！";
cout<<endl<<"本次插入的元素如下：";
Traverse(S);
break;
}
case 3:{
int n;
cout<<"请输入本次出栈的元素个数：";
cin>>n;
cout<<endl;
for(int i=n;i>0;i--) Pop(S,e);
cout<<"出栈成功！"<<endl;
cout<<"剩下的元素为：";
Traverse(S);
break;
}
case 4:GetTop(S,e);break;
case 5:Clear(S);break;
case 6:Traverse(S);break;
case 7:HuiWen();break;
case 0:exit(0);
}
}
system("pause");
return 0;
}
|