C++学习（三十七）（C语言部分）之 链式栈（推箱子实现）

用链表实现栈
一开始在表头插入，就要一直在表头插入
一开始在表尾插入，就要一直在表头插尾
表头当栈底 也可以把表尾当栈底

实现的测试代码笔记如下：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<string.h>
  4 
  5 //节点的结构体
  6 typedef struct node
  7 {
  8     char *name;
  9     struct node *pnext;
 10 }list, *plist;
 11 
 12 //1.创建“火车头”  创建一个表头
 13 void createlisthead(plist *p_list)  //传入头结点指针 给他分配内存
 14 {
 15     //一级指针 形参和实参结合时
 16     //plist p_list = p_head;  形参和实参结合时候的赋值
 17     //p_list 改变 是不影响到p_head  就好像是a给b发送了一个文件 b对文件进行了修改，是不会影响a手中的文件
 18 
 19     //要改变一级指针的实参 函数要传入一级指针的地址 保存一级指针的地址 要使用二级指针
 20     *p_list = (plist)malloc(sizeof(list));
 21     (*p_list)->pnext = null;
 22 
 23 }
 24 
 25 //实现一个栈 
 26 //2.写入栈函数
 27 void push_stack(plist p_list, char *name)
 28 {
 29     //头插法
 30     plist node = (plist)malloc(sizeof(list));
 31     //node->name - name;  可以这么写 但是如果存入得扇区内存，会被释放掉 就会出错
 32     node->name = (char *)malloc(sizeof(char)*strlen(name) + 1);
 33     strcpy(node->name, name);
 34     node->pnext = p_list->pnext;
 35     p_list->pnext = node;
 36 }
 37 
 38 //3.获取栈顶元素
 39 char * getstacktop(plist p_list)
 40 {
 41     //如果不是空 就返回头结点的下一个节点的name
 42     plist p_temp = p_list->pnext;
 43     if (p_temp != null)
 44     {
 45         return p_temp->name;
 46     }
 47     return null;  //说明栈是空
 48 }
 49 
 50 //4.出栈
 51 void pop_stack(plist p_list)
 52 {
 53     //相当于删除结点  之前是头插法  那么最后一个在最前面
 54     plist p_temp = p_list->pnext;
 55     if (p_temp != null)
 56     {
 57         //p_remp保存第一个节点的地址
 58         p_temp = p_list->pnext;
 59         //让头结点的pnext连接到第二个节点
 60         p_list->pnext = p_temp->pnext;
 61     }
 62     free(p_temp);  //释放内存  释放掉第一个节点 是释放p_temp里面所保存的内存 而不是释放指针变量
 63 }
 64 
 65 //5.判断栈是否为空
 66 int isempty(plist p_list)
 67 {
 68     //如果栈为空 返回1
 69     return p_list->pnext == null;
 70 }
 71 
 72 int main()
 73 {
 74     plist p_head = null;  //作为链表的标记
 75     createlisthead(&p_head);
 76     /*if (null == p_head)
 77     {
 78         printf("内存分配失败！\n");
 79     }
 80     else
 81     {
 82         printf("内存分配成功！\n");
 83     }*/
 84 
 85     push_stack(p_head, "力");
 86     push_stack(p_head, "努");
 87     push_stack(p_head, "的");
 88     push_stack(p_head, "人");
 89     push_stack(p_head, "何");
 90     push_stack(p_head, "任");
 91     push_stack(p_head, "于");
 92     push_stack(p_head, "亚");
 93     push_stack(p_head, "不");
 94     push_stack(p_head, "的");
 95     push_stack(p_head, "出");
 96     push_stack(p_head, "付");
 97     while (!isempty(p_head))
 98     {
 99         printf("%s", getstacktop(p_head));
100         pop_stack(p_head);
101     }
102 
103     getchar();
104     return 0;
105 }

附：

 

 

推箱子实现，代码笔记如下所示：

 

  1 1、main.cpp文件
  2 
  3 //推箱子
  4 //操作说明 wasd表示上下左右移动 空格键可以退回到上一步
  5 #if 1
  6 #include<graphics.h>
  7 #include<stdio.h>
  8 #include <conio.h>
  9 
 10 #include "stack.h"
 11 //地图
 12 int map[9][8] = {
 13     0, 0, 1, 1, 1, 1, 1, 0,
 14     1, 1, 1, 0, 0, 0, 1, 0,
 15     1, 3, 5, 4, 0, 0, 1, 0,
 16     1, 1, 1, 0, 4, 3, 1, 0,
 17     1, 3, 1, 1, 4, 0, 1, 0,
 18     1, 0, 1, 0, 3, 0, 1, 1,
 19     1, 4, 0, 7, 4, 4, 3, 1,
 20     1, 0, 0, 0, 3, 0, 0, 1,
 21     1, 1, 1, 1, 1, 1, 1, 1
 22 };
 23 
 24 //实现退回操作
 25 void retrogress(plist p_list)
 26 {
 27     //1.获取栈顶数据
 28     plist p_temp = getstacktop(p_list);
 29     if (null == p_temp)
 30     {
 31         return;
 32     }
 33     for (int i = 0; i < 9; i++)
 34     {
 35         for (int j = 0; j < 8; j++)
 36         {
 37             map[i][j] = p_temp->p[i][j];
 38         }
 39     }
 40     pop_stack(p_list);  //出栈
 41 }
 42 
 43 //对于一个游戏1.初始化  加载图片
 44 image g_box, g_dbox, g_people, g_point, g_wall, g_blank;
 45 void init_game()
 46 {
 47     loadimage(&g_box, l"./source/box.jpg");  //相对路径
 48     loadimage(&g_dbox, l"./source/dbox.jpg");
 49     loadimage(&g_people, l"./source/people.jpg");
 50     loadimage(&g_point, l"./source/point.jpg");
 51     loadimage(&g_wall, l"./source/wall.jpg");
 52     loadimage(&g_blank, l"./source/blank.jpg");
 53 }
 54 
 55 //2.加载图片
 56 void paint_game()
 57 {
 58     for (int i = 0; i < 9; i++)
 59     {
 60         for (int j = 0; j < 8; j++)
 61         {
 62             switch (map[i][j])
 63             {
 64             case 0: //0表示空地
 65                 putimage(j * 45, i * 45, &g_blank);
 66                 break;
 67             case 1: // 1表示墙壁
 68                 putimage(j * 45, i * 45, &g_wall);
 69                 break;
 70             case 3: // 3表示目的地
 71                 putimage(j * 45, i * 45, &g_point);
 72                 break;
 73             case 4: // 4表示箱子
 74                 putimage(j * 45, i * 45, &g_box);
 75                 break;
 76             case 5: // 5表示人
 77                 putimage(j * 45, i * 45, &g_people);
 78                 break;
 79             case 7: // 7表示箱子在目的地   4+3
 80                 putimage(j * 45, i * 45, &g_dbox);
 81                 break;
 82             case 8: // 8表示人在目的地   5+3
 83                 putimage(j * 45, i * 45, &g_people);
 84                 break;
 85             }
 86         }
 87     }
 88 }
 89 
 90 //3.实现人物移动
 91 void movepeople(plist p_list)
 92 {
 93     int i, j;
 94     for (i = 0; i < 9; i++)
 95     {
 96         for (j = 0; j < 8; j++)
 97         {
 98             //找到人的位置
 99             if (map[i][j] == 5 || map[i][j] == 8)
100             {
101                 //if成立说明找到人
102                 break;
103             }
104         }
105         if (map[i][j] == 5 || map[i][j] == 8)
106         {
107             //if成立说明找到人
108             break;
109         }
110     }
111     switch (getch())
112     {
113 //表示往左边移动
114     case 'a':  
115         //人的左边是空地 或者 是目的
116         if (map[i][j - 1] == 0 || map[i][j - 1] == 3)
117         {
118             map[i][j - 1] += 5;  //人往左边移动
119             map[i][j] -= 5;  //人离开了当前位置
120         }//人的左边是箱子或者是箱子在目的
121         else if (map[i][j - 1] == 4 || map[i][j - 1] == 7)
122         {
123             if (map[i][j - 2] == 0 || map[i][j - 2] == 3)
124             {
125                 map[i][j - 2] += 4;
126                 map[i][j - 1] += 1;
127                 map[i][j] -= 5;
128             }
129         }
130         //每次移动都要入栈
131         push_stack(p_list, map);
132         break;
133 
134 //表示往右边
135     case 'd': 
136         //人的右边是空地 或者 是目的
137         if (map[i][j + 1] == 0 || map[i][j + 1] == 3)
138         {
139             map[i][j + 1] += 5;  //人往左边移动
140             map[i][j] -= 5;  //人离开了当前位置
141         }//人的右边是箱子或者是箱子在目的
142         else if (map[i][j + 1] == 4 || map[i][j + 1] == 7)
143         {
144             if (map[i][j + 2] == 0 || map[i][j + 2] == 3)
145             {
146                 map[i][j + 2] += 4;
147                 map[i][j + 1] += 1;
148                 map[i][j] -= 5;
149             }
150         }
151         //每次移动都要入栈
152         push_stack(p_list, map);
153         break;
154 
155 //表示往上边移动
156     case 'w':  
157         //人的上边是空地 或者 是目的
158         if (map[i - 1][j] == 0 || map[i - 1][j] == 3)
159         {
160             map[i - 1][j] += 5;  //人往上边移动
161             map[i][j] -= 5;  //人离开了当前位置
162         }//人的上边是箱子或者是箱子在目的
163         else if (map[i - 1][j] == 4 || map[i - 1][j] == 7)
164         {
165             if (map[i - 2][j] == 0 || map[i - 2][j] == 3)
166             {
167                 map[i - 2][j] += 4;
168                 map[i - 1][j] += 1;
169                 map[i][j] -= 5;
170             }
171         }
172         //每次移动都要入栈
173         push_stack(p_list, map);
174         break;
175 
176 //表示什么往下边移动
177     case 's':  
178         //人的下边是空地 或者 是目的
179         if (map[i + 1][j] == 0 || map[i + 1][j] == 3)
180         {
181             map[i + 1][j] += 5;  //人往左边移动
182             map[i][j] -= 5;  //人离开了当前位置
183         }//人的下边是箱子或者是箱子在目的
184         else if (map[i + 1][j] == 4 || map[i + 1][j] == 7)
185         {
186             if (map[i + 2][j] == 0 || map[i + 2][j] == 3)
187             {
188                 map[i + 2][j] += 4;
189                 map[i + 1][j] += 1;
190                 map[i][j] -= 5;
191             }
192         }
193         //每次移动都要入栈
194         push_stack(p_list, map);
195         break;
196     case vk_space: //空格
197         if (!isempty(p_list))
198         {
199             retrogress(p_list);
200             paint_game();
201         }
202     }
203 }
204 
205 //4.判断游戏是否结束
206 int  iswin()
207 {
208     for (int i = 0; i < 9; i++)
209     {
210         for (int j = 0; j < 8; j++)
211         {
212             if (map[i][j] == 4)
213             {
214                 return 0;
215             }
216         }
217     }
218     return 1;
219 }
220 
221 int main()
222 {
223     initgraph(360, 405);  //初始化图形界面
224     init_game();
225     plist p_head = null;
226     createlisthead(&p_head);
227     paint_game();
228     while (!iswin())
229     {
230         paint_game();
231         movepeople(p_head);
232     }
233     paint_game();
234     getchar();//防止运行到closegraph() 直接退出 看不到效果
235     closegraph(); //关闭图形界面
236 
237     return 0;
238 }
239 
240 
241 *********************分割线************************
242 
243 
244 2、stack.h文件
245 #include <stdlib.h>
246 #include <stdio.h>
247 /*
248 以后  头文件是用来声明函数 或者类
249 */
250 typedef struct node
251 {
252     //char *name;   //前面是不是讲过动态分配二维数组
253     //通过指针数组来实现
254     int **p;  //目的：分配二维数组用来保存我的地图信息
255     struct node * pnext; 
256 }list, *plist;
257 
258 void createlisthead(plist *p_list);
259 
260 void push_stack(plist p_list, int(*parr)[8]);
261 
262 //返回整个结点的内容
263 plist  getstacktop(plist p_list);  
264 
265 void pop_stack(plist p_list);
266 
267 int isempty(plist p_list);
268 
269 
270 *********************分割线************************
271 
272 
273 3、stack.cpp文件
274 #include "stack.h"
275 
276 void push_stack(plist p_list, int(*parr)[8])
277 {
278     plist node = (plist)malloc(sizeof(list));
279     //先给二级指针申请内存   
280     node->p = (int **)malloc(sizeof(int)* 9); // p就相当于是一个  指针数组  int *p[9]
281     for (int i = 0; i < 9; i++)
282     {
283         //通过这个就能够分配一个二维数组
284         node->p[i] = (int*)malloc(sizeof(int)* 8);
285     }
286     for (int i = 0; i < 9; i++)
287     {
288         for (int j = 0; j < 8; j++)
289         {
290             node->p[i][j] = parr[i][j];
291         }
292         //代码  提升写代码能  语法有关
293         //思路  实现功能 首先你要有思路
294         //逻辑   你的方法的逻辑性是否可以
295         // 栈  链表
296     }
297     //连接指针
298     node->pnext = p_list->pnext;
299     p_list->pnext = node;
300     // int a[5] 
301     // int *a[5]  a二级指针  
302 }
303 
304 plist  getstacktop(plist p_list)
305 {
306     if (p_list->pnext != null)
307     {
308         return p_list->pnext;
309     }
310     return null;
311 }
312 
313 void pop_stack(plist p_list)
314 {
315     plist p_temp = null;
316     if (p_list->pnext != null)
317     {
318         //p_temp保存第一节点的地址
319         p_temp = p_list->pnext;
320 
321         //让头节点的pnext连接到第二个结点
322         p_list->pnext = p_temp->pnext;
323     }
324     //释放掉第一个结点
325     free(p_temp);  //会释放p_temp里面所保存的内存 而不是释放指针变量
326 }
327 
328 int isempty(plist p_list)
329 {
330     return p_list->pnext == null;
331 }
332 
333 void createlisthead(plist *p_list) //传入头节点指针 给它分配内存
334 {
335     *p_list = (plist)malloc(sizeof(list));
336     (*p_list)->pnext = null;
337 }

 

最后实现效果如下所示;

 

2019-04-01  21:33:15