数据结构：堆栈
算法思想：堆栈弹栈，压栈，回溯法
1 //迷宫问题 2 #include<stdio.h> 3 #include<stdlib.h> 4 #define m 9 5 #define n 9 6 #define MAXSIZE 100 7 //迷宫问题 8 9 //定义移动位置 ,其中 10 typedef struct{ 11 int x,y; 12 }item; 13 //定义一个数据类型为dataType，在栈里面存在此数据 14 //主要作为迷宫移动位置的临时存放点，其中x为当前位置的横坐标，y为当前位置的纵坐标 15 //d为 搜索的次数(方向) 16 typedef struct{ 17 int x,y,d; 18 }dataType; 19 20 //定义一个栈 21 typedef struct{ 22 dataType data[MAXSIZE]; 23 int top; 24 }list,*pList; 25 26 27 //创建栈 28 29 pList initList(){ 30 pList p; 31 p = (pList)malloc(sizeof(list)); 32 if(p){ 33 p->top = -1; 34 } 35 36 return p; 37 } 38 39 //判断栈是否为空 40 int isEmpty(pList p){ 41 if(p->top==-1){ 42 return 1;//如果是空栈就返回1 43 }else{ 44 return 0; 45 } 46 } 47 48 //压栈 49 int pushList(pList p,dataType data){ 50 if(p->top==MAXSIZE-1){//如果栈超出了大小，返回0 51 return 0; 52 } 53 p->top++; 54 p->data[p->top] = data;//压栈操作 55 return 1;//压栈成功，返回1 56 } 57 58 //弹栈 59 int popList(pList p,dataType *data){ 60 if(isEmpty(p)){ 61 return 0;//如果是空栈，就不弹，直接返回0 62 }else{ 63 *data = p->data[p->top]; 64 p->top--; 65 return 1; 66 } 67 } 68 69 //销毁栈 70 void destory(pList *p){ 71 if(*p){ 72 free(*p); 73 } 74 *p = NULL; 75 return; 76 } 77 78 int mazePath(int maze[][n+2],item move[],int x0,int y0){//maze表示一个迷宫的数组，move表示当前探索，x0,y0表示初始位置 79 pList p;//定义栈 80 dataType temp;//定义临时位置 81 int x,y,d,i,j;//x，y用来存放临时位置的角标，d表示临时的探索次数，i,j所在位置的迷宫角标 82 p = initList();//创建栈 83 if(!p){//如果创建失败 84 printf("创建栈失败"); 85 return 0; 86 } 87 88 //初始化走过的位置 89 temp.x = x0; 90 temp.y = y0; 91 temp.d = -1; 92 93 //把迷宫入口压栈 94 pushList(p,temp); 95 96 //当栈里面不为空时 97 while(!isEmpty(p)){ 98 popList(p,&temp);//弹栈 99 x = temp.x; 100 y = temp.y; 101 d = temp.d+1;//给d+1，让其进行第一次探索 102 while(d<4){//四次探索 103 i = x+move[d].x;//原来的位置加上探索的位置 104 j = y+move[d].y; 105 106 //当某条路是通路的时候 107 if(maze[i][j]==0){//表示此路可走 108 //使用temp来保存路径 109 temp.x = x; 110 temp.y = y; 111 temp.d = d; 112 //将路径压栈 113 pushList(p,temp); 114 //x、y来保存当前新的路径 115 x = i; 116 y = j; 117 maze[x][y] = -1;//把走过的路径的值设为-1 118 119 if(x==m && y==n){//判断是否走到头，如果走到头 120 while(!isEmpty(p)){//如果栈不为空 121 popList(p,&temp);//弹栈 122 printf("(%d,%d,%d),<-",temp.x,temp.y,temp.d);//打印路径 123 } 124 //程序结束，销毁栈 125 destory(&p); 126 return 1; 127 }else{//如果能走通，但是却没有走完迷宫，把d置为0 128 d = 0; 129 } 130 } else{//如果路不通，换个方向在进行探索 131 d++; 132 } 133 } 134 135 } 136 //如果最后都没找到，说明迷宫没有通路 137 destory(&p); 138 return 0; 139 140 } 141 142 void main(){ 143 item move[4];//定义一个控制探索路径的移动数组 144 //定义迷宫数组 145 int maze[11][11]={ 146 {1,1,1,1,1,1,1,1,1,1,1}, 147 {1,0,0,0,1,0,1,1,1,0,1}, 148 {1,0,1,0,0,0,0,1,0,1,1}, 149 {1,0,0,1,0,0,0,1,0,0,1}, 150 {1,1,0,1,0,1,0,1,0,1,1}, 151 {1,0,1,0,1,0,0,1,0,0,1}, 152 {1,0,0,0,0,0,1,0,1,0,1}, 153 {1,1,1,1,0,1,0,0,0,0,1}, 154 {1,0,0,1,0,0,0,1,0,1,1}, 155 {1,0,0,0,0,1,0,1,0,0,1}, 156 {1,1,1,1,1,1,1,1,1,1,1} 157 }; 158 159 //定义第一次移动 ,方向为北 160 move[0].x = 0; 161 move[0].y = 1; 162 163 //定义第二次移动，方向为南 164 move[1].x = 0; 165 move[1].y = -1; 166 167 //规定第三次移动，方向为东 168 move[2].x = 1; 169 move[2].y = 0; 170 171 //规定第三次移动,方向为西 172 move[3].x = -1; 173 move[3].y = 0; 174 175 mazePath(maze,move,1,1); 176 }