c/c++语言开发共享C++基于栈的深搜算法实现马踏棋盘

#include <stdio.h>  #include <stdlib.h>  #define m 8 //行  #define n 8 //列     typedef struct snode    //坐标  {      int flag;      int x;      int y;  }stack;  typedef struct node          {      int top;    //记录走了多少步top+1      int flag;  //记录上一步走的方向      stack * p;    //路径栈  }lnode;     lnode * createstacke();        //创建，并初始化  void judge(lnode * s, int chess[][n]); //判断往哪走  void push(lnode * s, stack x);  //入栈操作  void pop(lnode * s); //出栈操作  int isfull(lnode * s); //判满  int isempty(lnode * s); //判空   int main()  {      int chess[m][n] = {0};        //棋盘      int i, j;  //循环变量      lnode * step;                    //step存的是走的路径            step = createstacke();            judge(step, chess);         for (i = 0; i < n; i++){          for (j = 0; j < m; j++){              printf("%2d ", chess[i][j]);          }          printf("n");      }         return 0;  }  lnode * createstacke()  {      lnode * s = (lnode *)malloc(sizeof(lnode));            if (!s){          printf("内存空间不足!n");          system("pause");          exit(0);      }      s->p = (stack *)malloc(sizeof(stack) * m * n);      if (!s->p){          printf("内存空间不足!n");          system("pause");          exit(0);      }      s->top = -1;    // 把top放在栈底      return s;  }  void judge(lnode * s, int chess[][n])          {      int ch[8][2] = {                        //马可能走的八个方向                      {1, -2}, { 2, -1},                      {2, 1 }, { 1, 2 },                      {-1, 2}, {-2, 1 },                      {-2, -1},{-1, -2}                  };      int i, j = 1, flag = 1;      stack t;         printf("请输入马的初始位置：(%d * %d)n", m, n);      scanf("%d%d", &t.y, &t.x);      if (t.x <= 0 || t.x > n || t.y <= 0 || t.y > n){          printf("输入的坐标超出范围！n");          exit(0);      }      t.x--;      t.y--;      chess[t.y][t.x] = 1;                //选择马的第一个落脚点      push(s, t);      while (s->top < m * n - 1 && s->top != -1){          for (i = 0; i < 8; i++){              t.x = s->p[s->top].x + ch[i][0];              t.y = s->p[s->top].y + ch[i][1];              //如果它的坐标没有超出范围，并且没有走过，则把该路线存入路径栈              if (t.x >= 0 && t.y >= 0 && t.x < n && t.y < m && !chess[t.y][t.x]){                          if(flag){            //没有退回去                      push(s, t);                      chess[t.y][t.x] = s->top + 1;                      s->p[s->top - 1].flag = i;                      flag = 1;                      break;                  }                  else{                //退回去了                      if (s->p[s->top].flag < i){        //重新走时，让它的方向不等于原先的方向                          flag = 1;                      }                  }              }          }              //如果没有能走的路时，即，所有的路径都超出范围，或者，该位置已经走过了，则，退到上一步，重新选择；          if (i == 8){                        chess[s->p[s->top].y][s->p[s->top].x] = 0;              pop(s);              flag = 0;          }      }  }  void push(lnode * s, stack x)  {      if (isfull(s)){          printf("栈上溢，不能进行入栈操作!n");          exit (0);       }      else{          s->top++;          s->p[s->top] = x;                }  }  void pop(lnode * s)  {      if (isempty(s)){          printf("栈为空，不能进行出栈操作!n");          exit(0);      }      s->top--;  }  int isfull(lnode * s)  {      if (s->top >= m * n){          return 1;      }      else{          return 0;      }  }  int isempty(lnode * s)  {      if (s->top == -1){          return 1;      }      else{          return 0;      }  }