顺序栈SqStack
基本操作
1 Status InitStack()//构造一个空栈S
2 Status DestroyStack()//销毁栈S，S不再存在
3 Status ClearStack()//把S置为空栈
4 Status StackEmpty()//若S为空栈，则返回true，否则返回false
5 int StackLength()//返回S的元素个数，即栈的长度
6 Status GetTop(SElemType &e)//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
7 Status Push(SElemType e)//插入元素e为新的栈顶元素
8 Status Pop(SElemType &e)//若栈不空，则删除S的栈顶元素，并用e返回其值，并返回OK，否则返回ERROR
9 Status StackTraverse(int p)//从栈底到栈顶依次对栈中每个元素调用函数visit().一旦visit()失败则操作失败
几个小程序（代码正误检验，数制转换，括号匹配检验，行编辑程序）
1 CheckStackCode();//测试Stack代码正确性
2 Conversion();//数制转换
3 BracketsMatching();//括号匹配的检验
4 LineEdit();//行编辑程序
1 //
2 //by coolxxx
3 //#include<bits/stdc++.h>
4 #include<iostream>
5 #include<algorithm>
6 #include<string>
7 #include<iomanip>
8 #include<map>
9 #include<stack>
10 #include<queue>
11 #include<set>
12 #include<bitset>
13 #include<memory.h>
14 #include<time.h>
15 #include<stdio.h>
16 #include<stdlib.h>
17 #include<string.h>
18 //#include<stdbool.h>
19 #include<math.h>
20 #define min(a,b) ((a)<(b)?(a):(b))
21 #define max(a,b) ((a)>(b)?(a):(b))
22 #define abs(a) ((a)>0?(a):(-(a)))
23 #define lowbit(a) (a&(-a))
24 #define sqr(a) ((a)*(a))
25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
26 #define mem(a,b) memset(a,b,sizeof(a))
27 #define eps (1e-10)
28 #define J 10000
29 #define mod 1000000007
30 #define MAX 0x7f7f7f7f
31 #define PI 3.14159265358979323
32 #pragma comment(linker,"/STACK:1024000000,1024000000")
33 #define N 104
34
35 using namespace std;
36 typedef long long LL;
37 /*
38 double anss;
39 LL aans,sum;
40 int cas,cass;
41 int n,m,lll,ans;
42 */
43
44
45 const int OK=1;
46 const int ERROR=0;
47 const int INFEASIBLE=-1;
48 const int STACK_INIT_SIZE=100;//存储空间初始分配量
49 const int STACKINCREMENT=10;//存储空间分配增量
50 typedef int Status;
51 typedef int SElemType;
52
53 Status OutputInt(SElemType e);
54 Status OutputChar(SElemType e);
55 typedef struct
56 {
57 SElemType *base;//栈构造之前和销毁之后，base的值为NULL
58 SElemType *top;//栈顶指针
59 int stacksize;//当前已分配的存储空间，以元素为单位
60
61 Status InitStack()//构造一个空栈S
62 {
63 base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
64 if(!base)exit(OVERFLOW);//存储分配失败
65 top=base;
66 stacksize=STACK_INIT_SIZE;
67 return OK;
68 }//InitStack
69
70 Status DestroyStack()//销毁栈S，S不再存在
71 {
72 free(base);
73 base=NULL;
74 top=NULL;
75 stacksize=0;
76 return OK;
77 }//DestroyStack
78
79 Status ClearStack()//把S置为空栈
80 {
81 top=base;
82 return OK;
83 }//ClearStack
84
85 Status StackEmpty()//若S为空栈，则返回true，否则返回false
86 {
87 if(top==base)return true;
88 return false;
89 }//StackEmpty
90
91 int StackLength()//返回S的元素个数，即栈的长度
92 {
93 return top-base;
94 }//StackLength
95
96 Status GetTop(SElemType &e)//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
97 {
98 if(top==base)return ERROR;
99 e=*(top-1);
100 return OK;
101 }//GetTop
102
103 Status Push(SElemType e)//插入元素e为新的栈顶元素
104 {
105 if(top-base>=stacksize)//栈满，追加存储空间
106 {
107 base=(SElemType *)realloc(base,(stacksize+STACKINCREMENT)*sizeof(SElemType));
108 if(!base)exit(OVERFLOW);//存储分配失败
109 top=base+stacksize;
110 stacksize+=STACKINCREMENT;
111 }
112 (*top++)=e;
113 return OK;
114 }//Push
115
116 Status Pop(SElemType &e)//若栈不空，则删除S的栈顶元素，并用e返回其值，并返回OK，否则返回ERROR
117 {
118 if(top==base)return ERROR;
119 e=(*--top);
120 return OK;
121 }//Pop
122
123 Status StackTraverse(int p)//从栈底到栈顶依次对栈中每个元素调用函数visit().一旦visit()失败则操作失败
124 {
125 SElemType *i=base;
126 Status (*visit)(SElemType);
127 if(p==1)visit=OutputInt;
128 else if(p==0)visit=OutputChar;
129 while(top>i)
130 visit(*i++);
131 puts("");
132 return OK;
133 }//StackTraverse
134 }SqStack;
135
136 Status OutputInt(SElemType e)
137 {
138 printf("%d ",e);
139 return OK;
140 }
141 Status OutputChar(SElemType e)
142 {
143 printf("%c",e);
144 return OK;
145 }
146
147
148 void CheckStackCode()
149 {
150 typedef int SElemType;
151 int i;
152 SqStack S;
153 SElemType e;
154 if(S.InitStack()==OK)
155 {
156 for(i=1;i<=12;i++)
157 S.Push(i);
158 }
159 printf("栈中元素依次为：");
160 S.StackTraverse(1);
161 S.Pop(e);
162 printf("弹出的栈顶元素 e=%d\n",e);
163 printf("栈空否：%d(1：空 0：否)\n",S.StackEmpty());
164 S.GetTop(e);
165 printf("栈顶元素 e=%d 栈的长度为%d\n",e,S.StackLength());
166 S.Push(13);
167 printf("栈中元素依次为：");
168 S.StackTraverse(1);
169 S.GetTop(e);
170 printf("栈顶元素 e=%d 栈的长度为%d\n",e,S.StackLength());
171 S.DestroyStack();
172 printf("销毁栈后，S.top=%d S.base=%d S.stacksize=%d\n",S.top,S.base,S.stacksize);
173 }
174
175 void Conversion()//对于输入的任意一个非负十进制整数n，打印输出与其等值的八进制数
176 {
177 typedef int SElemType;
178 int n;
179 SqStack S;
180 SElemType e;
181
182 S.InitStack();//构造空栈
183 scanf("%d",&n);
184 while(n)
185 {
186 S.Push(n%8);
187 n/=8;
188 }
189 while(!S.StackEmpty())
190 {
191 S.Pop(e);
192 printf("%d",e);
193 }
194 puts("");
195
196 S.DestroyStack();
197 }
198
199 void BracketsMatching()//三种括号()[]{}，检验是否合法
200 {
201
202 char s[N];
203 SqStack S;
204 SElemType e;
205 int i;
206 S.InitStack();
207 scanf("%s",s);
208
209 for(i=0;i<strlen(s);i++)
210 {
211 if(s[i]=='(' || s[i]=='{' || s[i]=='[')
212 S.Push(s[i]);
213 else if(s[i]==')' || s[i]=='}' || s[i]==']')
214 {
215 if(S.GetTop(e) && ((e=='(' && s[i]==')') || (e=='[' && s[i]==']') || (e=='{' && s[i]=='}')))
216 S.Pop(e);
217 else
218 {
219 puts("NO");
220 S.DestroyStack();
221 return;
222 }
223 }
224 }
225 if(S.StackEmpty())puts("YES");
226 else puts("NO");
227 S.DestroyStack();
228 }
229
230 void LineEdit()//从终端接收一行并传送至调用过程的数据区，#为退格符，@为退行符
231 {
232 int i;
233 char ch;
234 SqStack S;
235 SElemType e;
236 S.InitStack();
237 while(ch!=EOF)
238 {
239 for(ch=getchar();ch!=EOF && ch!='\n';ch=getchar())
240 {
241 if(ch=='#')S.Pop(e);
242 else if(ch=='@')S.ClearStack();
243 else S.Push(ch);
244 }
245 S.StackTraverse(0);
246 S.ClearStack();
247 }
248 S.DestroyStack();
249 }
250
251
252 int main()
253 {
254 #ifndef ONLINE_JUDGEW
255 freopen("1.txt","r",stdin);
256 // freopen("2.txt","w",stdout);
257 #endif
258 int i,j,k;
259 // init();
260 // for(scanf("%d",&cass);cass;cass--)
261 // for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
262 // while(~scanf("%s",s))
263 /*
264 while(~scanf("%d%d",&n,&m))
265 {
266
267 }
268 */
269
270 CheckStackCode();//测试Stack代码正确性
271
272 Conversion();//数制转换
273
274 BracketsMatching();//括号匹配的检验
275
276 LineEdit();//行编辑程序
277
278 return 0;
279 }
280 /*
281 //
282
283 //
284 */
马踏棋盘问题（NxN）
暴力(顺序栈实现)
1 //
2 //by coolxxx
3 //#include<bits/stdc++.h>
4 #include<iostream>
5 #include<algorithm>
6 #include<string>
7 #include<iomanip>
8 #include<map>
9 #include<stack>
10 #include<queue>
11 #include<set>
12 #include<bitset>
13 #include<memory.h>
14 #include<time.h>
15 #include<stdio.h>
16 #include<stdlib.h>
17 #include<string.h>
18 //#include<stdbool.h>
19 #include<math.h>
20 #define min(a,b) ((a)<(b)?(a):(b))
21 #define max(a,b) ((a)>(b)?(a):(b))
22 #define abs(a) ((a)>0?(a):(-(a)))
23 #define lowbit(a) (a&(-a))
24 #define sqr(a) ((a)*(a))
25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
26 #define mem(a,b) memset(a,b,sizeof(a))
27 #define eps (1e-10)
28 #define J 10000
29 #define mod 1000000007
30 #define MAX 0x7f7f7f7f
31 #define PI 3.14159265358979323
32 #pragma comment(linker,"/STACK:1024000000,1024000000")
33 #define N 8
34 using namespace std;
35 typedef long long LL;
36 double anss;
37 LL aans;
38 int cas,cass;
39 LL n,m,lll,ans;
40 int a[N][N];
41 bool u[N][N];
42 int dx[]={-2,-1,1,2,2,1,-1,-2};
43 int dy[]={1,2,2,1,-1,-2,-2,-1};
44
45 const int OK=1;
46 const int ERROR=0;
47 const int INFEASIBLE=-1;
48 const int STACK_INIT_SIZE=10000;//存储空间初始分配量
49 const int STACKINCREMENT=10000;//存储空间分配增量
50 typedef int Status;
51
52 typedef struct
53 {
54 int x,y,dir;
55 }SElemType;
56
57 Status OutputInt(SElemType e);
58 Status OutputChar(SElemType e);
59 typedef struct
60 {
61 SElemType *base;//栈构造之前和销毁之后，base的值为NULL
62 SElemType *top;//栈顶指针
63 int stacksize;//当前已分配的存储空间，以元素为单位
64
65 Status InitStack()//构造一个空栈S
66 {
67 base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
68 if(!base)exit(OVERFLOW);//存储分配失败
69 top=base;
70 stacksize=STACK_INIT_SIZE;
71 return OK;
72 }//InitStack
73
74 Status DestroyStack()//销毁栈S，S不再存在
75 {
76 free(base);
77 base=NULL;
78 top=NULL;
79 stacksize=0;
80 return OK;
81 }//DestroyStack
82
83 Status ClearStack()//把S置为空栈
84 {
85 top=base;
86 return OK;
87 }//ClearStack
88
89 Status StackEmpty()//若S为空栈，则返回true，否则返回false
90 {
91 if(top==base)return true;
92 return false;
93 }//StackEmpty
94
95 int StackLength()//返回S的元素个数，即栈的长度
96 {
97 return top-base;
98 }//StackLength
99
100 Status GetTop(SElemType &e)//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
101 {
102 if(top==base)return ERROR;
103 e=*(top-1);
104 return OK;
105 }//GetTop
106
107 Status Push(SElemType e)//插入元素e为新的栈顶元素
108 {
109 if(top-base>=stacksize)//栈满，追加存储空间
110 {
111 base=(SElemType *)realloc(base,(stacksize+STACKINCREMENT)*sizeof(SElemType));
112 if(!base)exit(OVERFLOW);//存储分配失败
113 top=base+stacksize;
114 stacksize+=STACKINCREMENT;
115 }
116 (*top++)=e;
117 return OK;
118 }//Push
119
120 Status Pop(SElemType &e)//若栈不空，则删除S的栈顶元素，并用e返回其值，并返回OK，否则返回ERROR
121 {
122 if(top==base)return ERROR;
123 e=(*--top);
124 return OK;
125 }//Pop
126
127 Status StackTraverse(int p)//从栈底到栈顶依次对栈中每个元素调用函数visit().一旦visit()失败则操作失败
128 {
129 SElemType *i=base;
130 Status (*visit)(SElemType);
131 if(p==1)visit=OutputInt;
132 else if(p==0)visit=OutputChar;
133 while(top>i)
134 visit(*i++);
135 puts("");
136 return OK;
137 }//StackTraverse
138 }SqStack;
139 Status OutputInt(SElemType e)
140 {
141 printf("%d ",e);
142 return OK;
143 }
144 Status OutputChar(SElemType e)
145 {
146 printf("%c",e);
147 return OK;
148 }
149
150 SqStack S;
151 void print()
152 {
153 int i,j;
154 for(i=0;i<N;i++,puts(""))
155 for(j=0;j<N;j++)
156 printf("%d ",a[i][j]);
157 puts("");
158 }
159 int main()
160 {
161 #ifndef ONLINE_JUDGEW
162 freopen("1.txt","r",stdin);
163 // freopen("2.txt","w",stdout);
164 #endif
165 int i,j,k;
166 int x,y,z,xx,yy;
167 // init();
168 // for(scanf("%d",&cass);cass;cass--)
169 // for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
170 // while(~scanf("%s",s))
171 while(~scanf("%d%d",&n,&m))
172 {
173 mem(a,0);mem(u,0);
174 S.InitStack();
175 SElemType e,to;
176 e.x=n,e.y=m,e.dir=-1;
177 u[n][m]=1;
178 S.Push(e);
179 loop : while(S.top-S.base<N*N && !S.StackEmpty())
180 {
181 SElemType & now=*(S.top-1);
182 for(++now.dir;now.dir<8;now.dir++)
183 {
184 xx=now.x+dx[now.dir],yy=now.y+dy[now.dir];
185 if(xx>=0 && xx<N && yy>=0 && yy<N && !u[xx][yy])
186 {
187 u[xx][yy]=1;
188 to.x=xx,to.y=yy,to.dir=-1;
189 S.Push(to);
190 goto loop;
191 }
192 }
193 S.Pop(e);
194 u[e.x][e.y]=0;
195 }
196 if(S.StackEmpty()){puts("No Answer\n");continue;}
197 SElemType *id;
198 for(id=S.base,cas=0;id!=S.top;id++)
199 {
200 e=(*id);
201 a[e.x][e.y]=++cas;
202 }
203 print();
204 S.DestroyStack();
205 }
206 return 0;
207 }
马踏棋盘贪心优化
1 //
2 //by coolxxx
3 //#include<bits/stdc++.h>
4 #include<iostream>
5 #include<algorithm>
6 #include<string>
7 #include<iomanip>
8 #include<map>
9 #include<stack>
10 #include<queue>
11 #include<set>
12 #include<bitset>
13 #include<memory.h>
14 #include<time.h>
15 #include<stdio.h>
16 #include<stdlib.h>
17 #include<string.h>
18 //#include<stdbool.h>
19 #include<math.h>
20 #define min(a,b) ((a)<(b)?(a):(b))
21 #define max(a,b) ((a)>(b)?(a):(b))
22 #define abs(a) ((a)>0?(a):(-(a)))
23 #define lowbit(a) (a&(-a))
24 #define sqr(a) ((a)*(a))
25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
26 #define mem(a,b) memset(a,b,sizeof(a))
27 #define eps (1e-10)
28 #define J 10000
29 #define mod 1000000007
30 #define MAX 0x7f7f7f7f
31 #define PI 3.14159265358979323
32 #pragma comment(linker,"/STACK:1024000000,1024000000")
33 #define N 8
34 using namespace std;
35 typedef long long LL;
36 double anss;
37 LL aans;
38 int cas,cass;
39 LL n,m,lll,ans;
40 int a[N][N];
41 bool u[N][N];
42 int dx[]={-2,-1,1,2,2,1,-1,-2};
43 int dy[]={1,2,2,1,-1,-2,-2,-1};
44 struct xxx
45 {
46 int c,num;
47 };
48 bool cmp(xxx aa,xxx bb)
49 {
50 return aa.c<bb.c;
51 }
52 void print()
53 {
54 int i,j;
55 for(i=0;i<N;i++,puts(""))
56 for(j=0;j<N;j++)
57 printf("%d ",a[i][j]);
58 puts("");
59 }
60 void cal(int x,int y,xxx d[])
61 {
62 int i,j,xx,yy,x1,y1;
63 for(i=0;i<8;i++)
64 {
65 d[i].c=0;d[i].num=i;
66 xx=x+dx[i],yy=y+dy[i];
67 if(xx>=0 && xx<N && yy>=0 && yy<N && !u[xx][yy])
68 {
69 d[i].c++;
70 for(j=0;j<8;j++)
71 {
72 x1=xx+dx[j],y1=yy+dy[j];
73 if(x1>=0 && x1<N && y1>=0 && y1<N && !u[x1][y1])
74 {
75 d[i].c++;
76 }
77 }
78 }
79 }
80 }
81 void dfs(int x,int y,int top)
82 {
83 if(top==65)
84 {
85 print();
86 lll++;
87 return;
88 }
89 int i,j,xx,yy;
90 xxx d[8];
91 cal(x,y,d);
92 sort(d,d+8,cmp);
93 for(i=0;i<8;i++)
94 {
95 if(d[i].c==0)continue;
96 j=d[i].num;
97 xx=x+dx[j],yy=y+dy[j];
98 if(xx>=0 && xx<N && yy>=0 && yy<N && !u[xx][yy])
99 {
100 u[xx][yy]=1;
101 a[xx][yy]=top;
102 dfs(xx,yy,top+1);
103 if(lll==cas)return;
104 u[xx][yy]=0;
105 a[xx][yy]=0;
106 }
107 }
108 }
109 int main()
110 {
111 #ifndef ONLINE_JUDGEW
112 // freopen("1.txt","r",stdin);
113 // freopen("2.txt","w",stdout);
114 #endif
115 int i,j,k;
116 int x,y,z,xx,yy;
117 // init();
118 // for(scanf("%d",&cass);cass;cass--)
119 // for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
120 // while(~scanf("%s",s))
121 puts("输入起点坐标和需要的解的数量");
122 while(~scanf("%d%d",&n,&m))
123 {
124 scanf("%d",&cas);
125 j=clock();
126 mem(a,0);mem(u,0);lll=0;
127 a[n][m]=1;u[n][m]=1;
128 dfs(n,m,2);
129 k=clock();
130 printf("用时 %.3lf s\n",0.001*(k-j));
131 puts("输入起点坐标和需要的解的数量");
132 }
133 return 0;
134 }
为了写的快就随便优化没怎么细想，如果觉得我的算法复杂度还是太高可以转http://blog.csdn.net/bone_ace/article/details/41579957
原文链接: https://www.cnblogs.com/Coolxxx/p/5929384.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/241571
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
