共有回帖数 0 个
-
#include stdio.h
#include stdlib.h
#define N 6 //6*6迷宫（不得更改）
#define INIT_STACK_SIZE 2*N //初始分配栈的大小
#define INCREMENT_SIZE N //栈大小增量
//迷宫中的块
typedef struct {
char mark; //'0'可通 , '1'墙壁
char visited; //标记是否访问过
}block;
//栈元素
typedef struct {
int i; //行
int j; //列
}s_elem;
//栈
typedef struct {
s_elem *base; //存放所有路径
s_elem *shortest_path; //存放最短路径
int top; //！指向栈顶元素的下一个位置
int stacksize; //当前栈的容量
}stack;
void AllPath_ShorestPath(block (*maze)[N] ,int i,int j);
int Position(int *i ,int *j,int count);
void Output_AllPath(stack *ps);
void Output_ShorestPath(stack *ps);
int Initstack(stack *ps);
int Push(stack *ps,int i,int j);
int Pop(stack *ps);
int MIN=100; //MIN记录当前所求得的最短路径
stack StackPath; // 存放路径
int main(void)
{
int i,j;
block maze[N][N]={'1','0','1','0','1','0','1','0','1','0','1','0',
'1','0','0','0','0','0','0','0','0','0','1','0',
'1','0','0','0','0','0','0','0','0','0','1','0',
'1','0','0','0','1','0','1','0','0','0','1','0',
'1','0','1','0','0','0','0','0','0','0','1','0',
'1','0','1','0','1','0','1','0','1','0','1','0'};
maze[1][1].visited='1';
//输出迷宫
for(i=0;iN;i++)
{
for(j=0;jN;j++)
printf("%c ",maze[j].mark);
if(i!=N-1) putchar(10);
}
printf("（起点[2][2],终点[%d][%d]）nnn",N-1,N-1);
//求所有路径和最短路径并输出
puts(" 所有路径：");
Initstack(&StackPath);
Push(&StackPath,1,1);
AllPath_ShorestPath(maze ,1,1);
Output_ShorestPath(&StackPath);
//释放申请的内存
free(StackPath.base);
free(StackPath.shortest_path);
getchar();
return 0;
}
void AllPath_ShorestPath (block (*maze)[N] ,int i,int j) //从 maze[j] 开始深度优先遍历
{
int count=1;
int n=i,m=j; //保存当前位置
while(Position(&i,&j,count))
{
if(i==N-2 && j==N-2) //终点
{
if(!Push(&StackPath,i,j)) exit(1);
Output_AllPath(&StackPath);
if(!Pop(&StackPath)) exit(1);
}
else if(maze[j].mark=='0' && maze[j].visited=='0') //可通并且未访问过
{
maze[j].visited='1'; //标记为访问过
if(!Push(&StackPath,i,j)) exit(1);
AllPath_ShorestPath(maze,i,j);
if(!Pop(&StackPath)) exit(1);
maze[j].visited='0';
}
i=n;j=m; //恢复当前位置
count++;
} //end while
}
int Position(int *i ,int *j,int count) // i行 j列
{
switch(count)
{
case 1:(*j)++; //right
return 1;
case 2:(*i)++; //down
return 1;
case 3:(*j)--; //left
return 1;
case 4:(*i)--; //up
return 1;
default:return 0;
}
}
void Output_AllPath(stack *ps)
{
int i=0,k=0;
s_elem *base=ps-base;
for(i=0;i ps-top;base++,i++) //输出一条路径
printf("[%d][%d] ",base-i+1,base-j+1);
putchar(10); putchar(10);
//求最短路径
if(MIN ps-top-1)
{
for(k=0;k ps-top;k++)
ps-shortest_path[k]=ps-base[k];
MIN=ps-top-1;
}
}
void Output_ShorestPath(stack *ps)
{
int k=0;
s_elem *p=ps-shortest_path;
printf("nnn 最短路径：nn");
for(k=0;k = MIN;k++,p++)
printf("[%d][%d] ",p-i+1,p-j+1);
}
//栈函数
int Initstack(stack *ps)
{
ps-base=(s_elem *)malloc(sizeof(s_elem)*INIT_STACK_SIZE);
ps-shortest_path=(s_elem *)malloc(sizeof(s_elem)*INIT_STACK_SIZE);
if(!ps-base||!ps-shortest_path)
{
puts("内存不足!!!");
return 0;
}
ps-top=0; //空栈
ps-stacksize=INIT_STACK_SIZE;
return 1;
}
int Push(stack *ps,int i,int j)
{
int top=ps-top;
if(ps-top == ps-stacksize) //栈满
{
ps-base=(s_elem *)realloc(ps-base,sizeof(s_elem)*(INIT_STACK_SIZE+INCREMENT_SIZE));
ps-shortest_path=(s_elem *)realloc(ps-shortest_path,sizeof(s_elem)*(INIT_STACK_SIZE+INCREMENT_SIZE));
if(!ps-base ||!ps-shortest_path)
{
puts("内存不足!!!");
return 0;
}
ps-stacksize+=INCREMENT_SIZE;
}
ps-base[top].i=i; ps-base[top].j=j;
ps-top++;
return 1;
}
int Pop(stack *ps)
{
if(ps-top == 0) //栈空
{
puts("空栈!!!");
return 0;
}
ps-top--;
return 1;
}
编译通过。
这是文本形式，最好做成图形迷宫。
但是搞乐半天，还不清楚怎么玩丫。
LZ在程序中用到乐堆栈的内容
楼主 2016-01-08 10:13 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
