c/c++语言开发共享栈的简单应用-迷宫问题

 1 #pragma once  2 #include <stdio.h>  3 #include <stdlib.h>  4 #define stack_init_size 100//储存空间初始分配量  5 #define stackincrement  10//存储空间分配增量  6 #define ok 1  7 #define error 0  8 typedef struct {  9     int x;  //行值 10     int y;  //列值 11 }postype;  //迷宫坐标位置类型 12 typedef struct  13 { 14     int ord;      //序号 15     int di;       //方向 16     postype seat; //位置   17  18 } stacktype; //栈元素类型 19  20 typedef struct { 21     stacktype *base;   //在构造之前和销毁之后，base的值为null 22     stacktype *top;    //栈顶指针 23     int stacksize;     //当前已分配的存储空间，以元素为单位 24      25 }sqstack; //顺序栈 26  27 //栈的初始化 28 int initstack(sqstack *p) { 29  30  31     p->base = (stacktype*)malloc(stack_init_size * sizeof(stacktype)); 32     if (p->base == null)  return error;  //内存分配失败 33     p->top = p->base;     //栈顶与栈底相同表示一个空栈 34     p->stacksize = stack_init_size; 35     return ok; 36  37 } 38 //判断栈是否为空 39 int emptystack(sqstack *p) { 40     //若为空栈 则返回ok，否则返回error 41     if (p->top == p->base) return ok; 42     else return error; 43 } 44 //顺序栈的压入 45 int push(sqstack *p, stacktype e) { 46     //插入元素e为新的栈顶元素 47     if ((p->top - p->base) >= p->stacksize)   //栈满，追加储存空间 48     { 49         p->base = (stacktype*)realloc(p->base, (p->stacksize + stackincrement) * sizeof(stacktype)); 50         if (p->base == null)   return error;// 储存空间分配失败 51         p->top = p->base + p->stacksize;    52         p->stacksize += stackincrement; 53     } 54     *(p->top) = e; 55     (p->top)++; 56     return ok; 57 } 58 // 顺序栈的弹出      59 int pop(sqstack *p, stacktype *e) { 60     //若栈不空，则删除p的栈顶元素，用e返回其值 61     if (p->top == p->base) return error; 62     --(p->top); 63     *e = *(p->top); 64     return ok; 65  66  67 } 68 //将顺序栈置空 栈还是存在的，栈中的元素也存在， 69 //如果有栈中元素的地址任然能调用 70 int clearstack(sqstack *p) { 71     p->top = p->base; 72     return ok; 73 } 74 //顺序栈的销毁 75 int destroystack(sqstack *p) { 76     //释放栈底空间并置空 77     free(p->base); 78     p->base = null; 79     p->top = null; 80     p->stacksize = 0; 81  82     return ok; 83 }

  1 #include <stdio.h>   2 #include <stdlib.h>   3 #include "sqstack.h" //引入顺序栈储存结构及其基本操作   4 #define maxlength 25  //设迷宫最大行列为25   5 #define error 0   6 #define ok 1   7 #define true 1   8 #define false 0   9 typedef int status;  10 typedef int mazetype[maxlength][maxlength]; //迷宫数组[行][列]  11 postype begin, end;   //迷宫入口坐标，出口坐标  12 postype direc[4] = { {0,1},{1,0},{0,-1},{-1,0} }; //{行增量，列增量}，移动方向依次为东南西北  13 mazetype maze; //迷宫数组  14 int x, y;//迷宫的行，列  15 int curstep = 1;  //当前足迹，初值在入口处为1  16 struct selemtype  17 {  18     int ord;  //通道块在路径上的“序号”  19     postype seat;   //通道块在迷宫中的“坐标位置”  20     int di;  //从此通道块走向下一通道块的“方向”(0-3表示东-北)  21 };  22 void print() {  23     //输出迷宫结构  24     int i, j;  25     for (i = 0; i < x; i++)  26     {  27         for (j = 0; j < y; j++)  28             printf("%3d", maze[i][j]);  29         printf("n");  30     }  31 }  32 void init()  33 {  34     //设定迷宫布局(墙值为0，通道值为1)  35     //全局变量maze 未初始化 所以均为值均为0  36     int i, j, x1, y1;  37     printf("请输入迷宫的行数，列数(包括外墙):");  38     scanf("%d%d", &x, &y);  39     for (i = 1; i < x - 1; i++)  40         for (j = 1; j < y - 1; j++)  41             maze[i][j] = 1;  //定义通道初值为1  42     printf("请输入迷宫内墙单元数:");  43     scanf("%d", &j);  44     printf("请依次输入迷宫内墙每个单元的行数，列数:n");  45     //file *fp; 注释掉的这五行之前是方便我调试的  46     //fp = fopen("maze.txt", "r");  47     //int *px1 = &x1, *py1 = &y1;  48     for(i=1;i<=j;i++)  49     {  50         //fscanf(fp, "%d%d", px1, py1);  51         //maze[x1][y1] = 0;  52         scanf("%d%d", &x1, &y1);  53         maze[x1][y1] = 0; //定义墙值为0  54     }  55     printf("迷宫结构如下:n");  56     print();  57     printf("请输入入口的行数，列数:");  58     scanf("%d%d", &begin.x, &begin.y);  59     printf("请输入出口的行数，列数:");  60     scanf("%d%d", &end.x, &end.y);  61 }  62 void markprint(postype seat)  63 {//标记迷宫块不可通过  64     maze[seat.x][seat.y] = -1;  65       66   67 }  68 status pass(postype b)  69 {  70     //当迷宫m的b点的值为1，return ok;  71     //否则return error;  72     if (maze[b.x][b.y] == 1)  73         return ok;  74     else  75         return error;  76 }  77 void footprint(postype b)  78 {  79 //使迷宫m的b点的值变为足迹(curstep),表示经过  80     maze[b.x][b.y] = curstep;  81   82 }  83 postype nextpos(postype  b,int di)  84 {  85     //根据当前位置b及其移动方向di，修改b为下一位置  86     b.x += direc[di].x;  87     b.y += direc[di].y;  88     return b;  89 }  90 status mazepath(postype start, postype end)  91 {  92     //若迷宫m中存在从入口start到出口end的通道  93     //则求得一条存放在栈中，并返回true；否则返回false  94     sqstack s,*s; //顺序栈  95     s = &s;  96     postype curpos;  97     stacktype e,*pe;  98     pe = &e;  99     initstack(s); 100     curpos = start; 101     do 102     { 103         if (pass(curpos)) //当前可以通过，则是未曾走到的通道块 104         { 105             footprint(curpos); //留下足迹 106             e.ord = curstep;  //栈元素序号为当前序号 107             e.seat = curpos;  //栈元素位置为当前位置 108             e.di = 0;  //从当前位置出发，下一位置为东 109             push(s, e); //入栈当前位置及其状态 110             curstep++;   //足迹加1 111             if (curpos.x == end.x&&curpos.y == end.y)  //到达出口 112                 return true; 113             curpos = nextpos(curpos, e.di); //由当前位置及移动方向确定下一个当前位置 114         } 115         else //当前位置不能通过 116             if (!emptystack(s))  //栈不为空 117             { 118                 pop(s, pe); // 退栈到前一位置 119                 curstep--;  //足迹减1 120                 while (e.di == 3 && !emptystack(s))  //前一位置处于最后一个方向(北) 121                 { 122                     markprint(e.seat); //留下不能通过的标记(-1) 123                     pop(s, pe); //退一步 124                     curstep--; //足迹再减1 125  126                 } 127                 if (e.di < 3)  //没有到最后一个方向(北) 128                 { 129                     e.di++;  //换下一个方向探索 130                     push(s, e); //入栈该位置的下一个方向 131                     curstep++;// 足迹加1 132                     curpos = nextpos(e.seat, e.di); 133  134                 } 135  136             } 137  138     } 139     while (!emptystack(s)); 140     return false; 141      142      143 } 144 int main()  145 { 146     init();  //初始化迷宫 147     if (mazepath(begin, end)) //有通路 148     { 149         printf("从此迷宫入口到出口的一条路径如下:n"); 150         print(); 151     } 152     else 153         printf("此迷宫没有从入口到出口的路径n"); 154     return 0; 155  156      157 } 158