栈与队列的三个例子
1.小括号匹配
#define FORMATSTR "%c " typedef char ElemType; #define BufSize 128 #include "Stack.h" int CheckBracket(char *str, int len) { int i = 0; SQSTACK S; char ch; InitSqstack(&S, len); while(str[i]) { ch = str[i]; if(ch == '(') PushS(&S, ch); else if(ch == ')') if(!PopS(&S, &ch)) { DestroySqstack(&S); return 0; } ++i; } if(IsSqstackEmpty(S)) ; else i = 0; DestroySqstack(&S); return i; } int main(void) { //栈示例 - 括号匹配 char string[BufSize]; gets(string); if(CheckBracket(string, strlen(string))) puts("Match!"); else puts("Mismatch!"); return 0; }
2.迷宫求解
#define FORMATSTR typedef struct { int x, y, v; //坐标与方向 }ElemType; #include "Stack.h" int Map[10][10] = { 1,1,1,1,1,1,1,1,1,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,0,0,1,1,0,0,1, 1,0,1,1,1,0,0,0,0,1, 1,0,0,0,1,0,0,0,0,1, 1,0,1,0,0,0,1,0,0,1, 1,0,1,1,1,0,1,1,0,1, 1,1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1, }; int tox[5] = {0, 0,1,0,-1}; //偏正方向 int toy[5] = {0,-1,0,1, 0}; //偏正方向 int main(void) { //链式栈示例 - 迷宫求解,给定的迷宫,输出所有解。 LINKSTACK S; ElemType e; int x, y, v; //当前坐标 int ox, oy; //修正坐标 int i, j, k = 0; e.x = 1; e.y = 1; //出发点 e.v = 0; //方向 InitLinkstack(&S); PushL(S, e); Map[1][1] = 8; while(!IsLinkstackEmpty(S)) { PopL(S, &e); x = e.x; y = e.y; v = e.v + 1; //back from here if(e.v > 0) Map[y+toy[e.v]][x+tox[e.v]] = 0; while(v <= 4) { ox = x + tox[v]; oy = y + toy[v]; if(ox == 8 && oy == 9) //终点 { printf("Answer %d:\n", ++k); for(i = 0; i < 10; ++i) { for(j = 0; j < 10; ++j) printf("%d ", Map[i][j]); putchar(10); } ++v; } else if(ox > 0 && oy > 0 && !Map[oy][ox]) { e.x = x; e.y = y; e.v = v; PushL(S, e); x = ox, y = oy; v = 1; Map[y][x] = 8; } else ++v; } } DestroyLinkstack(&S); return 0; }
3.最短路径
#define FORMATSTR typedef struct { int x, y, pre; //坐标与方向 }ElemType; #include "Queue.h" int Map[10][10] = { 1,1,1,1,1,1,1,1,1,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,0,0,1,1,0,0,1, 1,0,1,1,1,0,0,0,0,1, 1,0,0,0,1,0,0,0,0,1, 1,0,1,0,0,0,1,0,0,1, 1,0,1,1,1,0,1,1,0,1, 1,1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1, }; int tox[5] = {0, 0,1,0,-1}; //偏正方向 int toy[5] = {0,-1,0,1, 0}; //偏正方向 int main(void) { //队列示例 - 迷宫的最短路径 SQQUEUE Q; ElemType e; int x, y, v; //当前坐标 int ox, oy; //修正坐标 int i, j, k = 0, step = 2; //从02开始 e.x = 1; e.y = 1; //出发点 e.pre = 2; //前驱 InitSqqueue(&Q, 10*10); EnSqqueue(&Q, e); Map[1][1] = step; while(!IsSqqueueEmpty(Q)) //BFS { DeSqqueue(&Q, &e); x = e.x; y = e.y; v = e.pre += 1; for(i = 1; i <= 4; ++i) { e.x = x + tox[i]; e.y = y + toy[i]; if(Map[e.y][e.x] == 0) { EnSqqueue(&Q, e); Map[e.y][e.x] = e.pre; if(e.x == 8 && e.y == 8) //终点 { printf("The Shortest Path is:\n"); for(i = 0; i < 10; ++i) { for(j = 0; j < 10; ++j) printf("%02d ", Map[i][j]); putchar(10); } DestroySqqueue(&Q); return 0; //找到就停 } } } } DestroySqqueue(&Q); return 0; }
2020年8月28日 23:28
I came onto your blog while focusing just slightly submits. Nice strategy for next, I will be bookmarking at once seize your complete rises... 그래프사이트
2020年8月30日 01:22
Hi there, I discovered your blog per Google bit searching for such kinda educational advise moreover your inform beholds very remarkable for me. sagame888
2020年8月31日 13:58
This is important, though it's necessary to help you head over to it weblink: 성기확대수술
2020年8月31日 14:03
You ought to basically fantastic not to mention solid advice, which means notice: 스포츠중계
2020年9月11日 14:58
On this page you can read my interests, write something special. ที่เด็ด
2022年9月05日 14:52
Chhattisgarh Board Model Paper 2023 Pdf Designed and Suggested by CGBSE Raipur Board Experts to Class 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 Grade Question Paper for Hindi Medium, English Medium, Urdu Medium and others for Theory, Objective (MCQ) and Bit Questions. CG Board Question Paper New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.