堆栈的访问规则被限制为Push和Pop两种操作,Push(入栈或压栈)向栈顶添加元素,Pop(出栈或弹出)则取出当前栈 顶的元素,也就是说,只能访问栈顶元素而不能访问栈中其它元素。
现在我们用堆栈解决一个有意思的问题,定义 一个二维数组:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走 的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。程序如下:(参考《Linux c 编程一 站式学习》)
#include<stdio.h> typedef struct point { int row, col; } item_t; #define MAX_ROW 5 #define MAX_COL 5 static item_t stack[512]; static int top = 0; void push(item_t p) { stack[top++] = p; } item_t pop(void) { return stack[--top]; } int is_empty(void) { return top == 0; } int maze[MAX_ROW][MAX_COL] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; void print_maze(void) { int i, j; for (i = 0; i < MAX_ROW; i++) { for (j = 0; j < MAX_COL; j++) printf("%d ", maze[i][j]); putchar('\n'); } printf("*********\n"); } struct point predecessor[MAX_ROW][MAX_COL] = { {{ -1, -1}, { -1, -1}, { -1, -1}, { -1, -1}, { -1, -1}}, {{ -1, -1}, { -1, -1}, { -1, -1}, { -1, -1}, { -1, -1}}, {{ -1, -1}, { -1, -1}, { -1, -1}, { -1, -1}, { -1, -1}}, {{ -1, -1}, { -1, -1}, { -1, -1}, { -1, -1}, { -1, -1}}, {{ -1, -1}, { -1, -1}, { -1, -1}, { -1, -1}, { -1, -1}}, }; void visit(int row, int col, struct point pre) { struct point visit_point = { row, col }; maze[row][col] = 2; predecessor[row][col] = pre; push(visit_point); } int main(void) { struct point p = { 0, 0 }; maze[p.row][p.col] = 2; push(p); while (!is_empty()) { p = pop(); if (p.row == MAX_ROW - 1 /* goal */ && p.col == MAX_COL - 1) break; if (p.col + 1 < MAX_COL /* right */ && maze[p.row][p.col + 1] == 0) visit(p.row, p.col + 1, p); if (p.row + 1 < MAX_ROW /* down */ && maze[p.row + 1][p.col] == 0) visit(p.row + 1, p.col, p); if (p.col - 1 >= 0 /* left */ && maze[p.row][p.col - 1] == 0) visit(p.row, p.col - 1, p); if (p.row - 1 >= 0 /* up */ && maze[p.row - 1][p.col] == 0) visit(p.row - 1, p.col, p); print_maze(); } if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) { printf("(%d, %d)\n", p.row, p.col); while (predecessor[p.row][p.col].row != -1) { p = predecessor[p.row][p.col]; printf("(%d, %d)\n", p.row, p.col); } } else printf("No path!\n"); return 0; }
以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索int
, struct
, 迷宫
, 堆栈
, row
, col
, void
cols
,以便于您获取更多的相关知识。
时间: 2024-09-03 00:24:35