看看这个迷宫代码如何补充完整~
自己用了广度搜索敲了个找迷宫最短路径~~不过只求出了最短步数~看看如果打印出最短路径？~PS：第一次用广度搜索写~并且在没有参考资料的前提下~写得不好请勿见怪~
先放在这里保存一下~
程序代码：#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<windows.h>
#define LEN_Stack sizeof (Stack) //栈的容量
#define LEN_Qnode sizeof (Qnode) //队列的容量
#define M 10 //迷宫最大长度
typedef struct Maze //迷宫
{
int x; //迷宫x坐标
int y; //迷宫y坐标
int n; //迷宫状态
int count; //当前步数
int flag; //记录遍历状态
}Maze;
Maze maze[M][M]={0};
typedef struct Qnode //队列
{
Maze maze; //迷宫结构体
struct Qnode* next; //队列指针
}Qnode,*QnodePrt;
typedef struct
{
QnodePrt front; //队头指针
QnodePrt rear; //队尾指针
}LinkQnode;
typedef struct Stack //栈
{
Maze maze;
struct Stack* next;
}Stack,*StackPrt;
typedef struct
{
StackPrt base; //栈顶指针
StackPrt top; //栈底指针
}LinkStack;
void initilize(); //初始化数据
void Stack_creat(LinkStack* stack); //创建一个栈
void Stack_insert(LinkStack* stack,Maze* tmaze); //入栈
void Stack_push(LinkStack* stack); //出栈
void Stack_destory(LinkStack* stack); //清空栈
int Stack_empty(LinkStack* stack); //判断栈是否为空
void Queue_creat(LinkQnode* queue); //创建一个队列
void Queue_insert(LinkQnode* queue,Maze* tmaze); //入队
void Queue_push(LinkQnode* queue); //出队
void Queue_destory(LinkQnode* queue); //清空队列
int Queue_empty(LinkQnode* queue); //判断队列是否为空
int fun(); //开始
void GetPoint(LinkQnode* queue,int* x,int* y); //获取当前迷宫坐标
int SavePoint(Maze* tmaze,int count); //记录坐标
void print(); //打印迷宫
int Start_x=1; //起点x坐标
int Start_y=1; //起点y坐标
int End_x=8; //终点x坐标
int End_y=8; //终点y坐标
LinkStack stack={0};
LinkQnode queue={0};
int main()
{
int count=0;
Stack_creat(&stack);
Queue_creat(&queue);
initilize();
print();
count=fun();
if (!Queue_empty(&queue))
{
Queue_destory(&queue);
printf("迷宫最短步数为:%d\n",count);
}
else
puts("没找到出口!");
return 0;
}
void Stack_creat(LinkStack* stack) //创建一个栈
{
stack->base=stack->top=(StackPrt)malloc(LEN_Stack);
memset(stack->base,0,LEN_Stack);
}
void Stack_insert(LinkStack* stack,Maze* tmaze) //入栈
{
StackPrt p=(StackPrt)malloc(LEN_Stack);
p->next=stack->top;
p->maze=*tmaze;
stack->top=p;
}
void Stack_push(LinkStack* stack) //出栈
{
StackPrt p=stack->top;
if (Stack_empty(stack)) //如果栈为空
return ;
stack->top=stack->top->next;
free(p);
}
void Stack_destory(LinkStack* stack) //清空栈
{
while (!Stack_empty(stack))
Stack_push(stack);
}
int Stack_empty(LinkStack* stack) //判断栈是否为空
{
return stack->base==stack->top;
}
void Queue_creat(LinkQnode* queue) //创建一个队列
{
queue->front=queue->rear=(QnodePrt)malloc(LEN_Qnode);
memset(queue->front,0,LEN_Qnode);
}
void Queue_insert(LinkQnode* queue,Maze* tmaze) //入队
{
queue->rear=queue->rear->next=(QnodePrt)malloc(LEN_Qnode);
queue->rear->next=NULL;
queue->rear->maze=*tmaze;
// printf("%d %d\n",queue->rear->maze.x,queue->rear->maze.y);
}
void Queue_push(LinkQnode* queue) //出队
{
QnodePrt p=queue->front;
if (Queue_empty(queue)) //如果队列为空
return ;
queue->front=queue->front->next;
free(p);
p=queue->front->next;
memset(queue->front,0,LEN_Qnode);
queue->front->next=p;
}
void Queue_destory(LinkQnode* queue) //清空队列
{
while (!Queue_empty(queue))
Queue_push(queue);
}
int Queue_empty(LinkQnode* queue) //判断队列是否为空
{
return queue->front==queue->rear;
}
void print()
{
char* p=" o#";
int i=0;
int j=0;
for (i=0;i!=M;++i)
for (j=0;j!=M+1;++j)
putchar(j!=M?p[maze[i][j].n]:'\n');
}
void initilize()
{
int a[M][M]=
{
{2,2,2,2,2,2,2,2,2,2},
{2,0,2,2,2,2,0,2,2,2},
{2,0,0,0,0,2,0,2,2,2},
{2,0,2,2,0,0,0,0,0,2},
{2,0,2,2,0,2,2,2,0,2},
{2,0,0,0,2,2,0,2,0,2},
{2,2,0,2,2,2,0,2,0,2},
{2,2,0,2,0,0,0,0,0,2},
{2,2,0,0,0,2,2,2,0,2},
{2,2,2,2,2,2,2,2,2,2},
};
int i=0;
int j=0;
memset(maze,0,sizeof(Maze));
for (i=0;i!=M;++i) //初始化迷宫数据
for (j=0;j!=M;++j)
{
maze[i][j].x=i;
maze[i][j].y=j;
maze[i][j].n=a[i][j];
}
}
int fun() //开始
{
int x=Start_x;
int y=Start_y;
int count=0; //步数
if (SavePoint(&maze[x][y],count)) //起点坐标入队
return count;
while (!Queue_empty(&queue))
{
if (queue.front->next->maze.count==count)
count++;
GetPoint(&queue,&x,&y); //获取当前节点坐标
if (SavePoint(&maze[x-1][y],count)) //处理四个方向
return count;
if (SavePoint(&maze[x+1][y],count))
return count;
if (SavePoint(&maze[x][y-1],count))
return count;
if (SavePoint(&maze[x][y+1],count))
return count;
Queue_push(&queue);
}
return -1;
}
void GetPoint(LinkQnode* queue,int* x,int* y)
{
*x=queue->front->next->maze.x;
*y=queue->front->next->maze.y;
}
int SavePoint(Maze* tmaze,int count) //记录坐标
{
if (tmaze->n!=0||tmaze->flag!=0)
return 0;
tmaze->count=count;
tmaze->flag=1;
Queue_insert(&queue,tmaze);
Stack_insert(&stack,tmaze);
if (tmaze->x==End_x&&tmaze->y==End_y)
return 1;
return 0;
}[此贴子已经被作者于2017-3-16 14:32编辑过]
预先设计的栈到头来反而可以不用~~
~~~~~~~
。我还没学到广度搜索来，在学队列。