精华内容
下载资源
问答
  • 数据结构迷宫代码,数据结构(C语言版),迷宫的C++语言实现.在数据结构的非空有限集中,按照一定事先布置的顺序实现.线性表是最常用的数据结构,不断的更新,不断的变化...粉色范围沃尔费威尔俄文热辐射大范围而...
  • 数据结构 严蔚敏 C语言迷宫 status mazePath(seqStack *S, posType start, posType end) { posType curPos; //current positon int curStep; //the ordinary number sElemType e; curPos = start; curStep ...
  • 数据结构C语言版)上面的第三章栈与队列中的迷宫问题。
  • 主要为大家详细介绍了C语言实现数据结构迷宫实验,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 数据结构 c语言做的迷宫程序 c语言做的迷宫程序
  • (1)用C语言实现顺序存储结构上队列的基本操作,然后利用该队列的基本操作找出迷宫的一条最短路径。 (2)设计一个二维数组MZEZEl+2)o+]表示迷宫,数组元素为0表示该位置可以通过,数组元素为!表示该位置不可以通行。...

    戳这里还有其他数据结构的题目噢

    https://blog.csdn.net/qq_45724947/article/details/115625130?spm=1001.2014.3001.5501


    题目:迷宫问题。假设迷宫由m行n列构成,有一个入口和一个出 口,大口坐标为(1, 1), 出口坐标为(m, n),试设计并验证以下算法:找出一-条从入口通往出口的路径,或报告一个“无法通过”的信息。
    (1)用C语言实现顺序存储结构上队列的基本操作,然后利用该队列的基本操作找出迷宫的一条最短路径。
    (2)设计一个二维数组MZEZEl+2)o+]表示迷宫,数组元素为0表示该位置 可以通过,数组元素为!表示该位置不可以通行。MAZEUID MAZEIm]分别为迷宫的入口和出口。
    (3)输入建宫的大小m行和口列,动态生成二维数组:由随机数产生0或1.建立遗言。注意m*n中的迷宫需要进行扩展,扩展部分的元素设置为1.相当于在迷宫周围布上一圈不准通过的墙。
    (4)要求输出模拟迷宫的二维数组:若存在最短路经,则由出口回溯到入口(出队列并利用栈实现),再打印从入口到出口的这条路径,例如(1,1),.....(j),.... (m)若没有路径,则打印-No pubr.
    (5)迷宫的任何位置(i,j)上均有八个可以移动的方向,用二维数组Diretion存放八个方向上的位置偏移量。
    Direction[8][2] ={ {-1,1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}
    (6)为避免出现原地踏步步的情况为了标志已经通过的位置,采用一个标志数组MARK[m+2][n+2],初值均为0,在寻找路径的过程中,若通过了位置(i,j),则将MARK[i][]置为1.
    (7)为了记录查找过程中到达位置(i,j)及首次到达(ij)的前一位置
    (i prej pre), 需要记住前一位置(i pre,j_ pre)在队列中的序号 pre,即队列中数据
    元素应该是一个三元组(j,pre)。
    (8)搜索过程简单描述如下:将入口MAZE[1][1]作为第一个出发点, 依次在
    八个方向上搜索可通行的位置,将可通行位置(ij,pre)入队,形成第一层新的出发
    点,然后依次出队,即对第一层中各个位置分别搜索它所在八个方向上的可通行
    位置,形成第二层新的出发点,..如此进行下去,直至达到出口MAZE[m][n]
    或者迷宫所有位置都搜索完毕为止。

     直接上代码:

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <windows.h>
    
    //创建基本迷宫三元组 
    typedef struct Data{
    	int row;//行 
    	int col;//列 
    	int previous;//前一个可通过的位置(开始探索方向的位置) 
    }sData,qData;
    
    int** createPuzzle(int row,int col){  // 实现 动态数组创建矩阵 函数 
    	int **Puzzle;
    	Puzzle = (int **)malloc(sizeof(int *) * row);//分配指针数组
    	for(int i=0; i<row; i++)
    	{
    		Puzzle[i] = (int *)malloc(sizeof(int) * col);//分配每个指针所指向的数组
    	}
    	return Puzzle;
    }
    
    #define STACK_INIT_SIZE 1000  // 存储空间初始分配量
    #define STACKINCREMENT 10  // 存储空间分配增量
    #define true 1
    #define false 0
    #define OK 1
    #define OVERFLOW -1
    
    typedef int ElemType;
    typedef int Status; //函数返回类型,其值为结果状态码
    
    struct stack1{
    	sData base[STACK_INIT_SIZE];
    	int top;  //指示栈顶位置
    };
    typedef struct stack1 SqStack;
    
    Status Push(SqStack *s,sData data){      //  元素入栈
    	if(s->top==STACK_INIT_SIZE-1)
    		return OVERFLOW;
    	else{
    	s->top++;
    	s->base[(s->top)]=data;
    	}
    	return OK;
    }
    
    Status Pop(SqStack *s,sData *data){      //  栈顶元素出栈
    	if(s->top==-1)
    		return OVERFLOW;
    	else{
    		*data=s->base[s->top];
    		s->top--;
    	}	
    	return OK;
    }
    
    Status Get(SqStack *s,sData *data){   // 得到栈顶元素
    	if(s->top==-1)
    		return OVERFLOW;
    	else{
    		*data=s->base[s->top];
    		}
    	return OK;
    }
    
    Status InitStack(SqStack *s){    //    初始化栈
    	s->top=-1;
    	if(!s->base)
    		return OVERFLOW;
    	return OK;
    }
    
    Status StackTraverse(SqStack *s){         //栈元素的遍历
    	if(s->top==-1){
    		printf("栈已空!\n");
    		return OK;
    	}
    	while(s->top!=-1){
    		printf("(%d,%d) ",s->base[s->top].row,s->base[s->top].col);  // 输出坐标
    		s->top--;
    	}
    	printf("\n");
    	return OK;
    }
    
    Status searchStackData(SqStack *s,sData data){//搜索当前位置 
    	while(s->top>=0){
    		if((s->base[s->top].row == data.row)&&(s->base[s->top].col == data.col))
    			return true;
    		s->top--;
    	}
    	return false;
    }
    
    #define ERROR 0   
    #define OK 1
    #define OVERFLOW -1
    #define true 1
    #define false 0
    #define STACK_INIT_SIZE 1000
    
    typedef int Status;   
    
    typedef struct QUeue1{
    	qData base[STACK_INIT_SIZE];    
    	int front;  // 队头
    	int rear;  // 队尾
    }QNode;
    
    Status InitQueue(QNode *Q){  // 初始化队列
    	Q->front=0;  
    	Q->rear=0;
    	if(!Q->base)
    		return OVERFLOW;
    	return OK;
    }
    
    Status EnQueue(QNode *Q,qData data){  // 入队列
    	if(Q->rear==STACK_INIT_SIZE-1)
    		return OVERFLOW;
    	else{
    		Q->base[(Q->rear)]=data;
    		Q->rear++;  //指向下一个元素
    	}
    	return OK;
    }
    
    Status DeQueue(QNode *Q,qData *data){  // 出队列,队列不为空,返回其值
    	if(Q->front==Q->rear)
    		return OVERFLOW;
    	else{
    		*data = Q->base[Q->front];
    	}
    	return OK;
    }
    
    Status rand(ElemType **p,int row,int col){ // 随机产生迷宫
    	srand(unsigned(time(NULL)));
    	int r,c;
    	for(r = 0;r<row;r++)  
    		for(c = 0;c < col;c++){
    			if(r==0||c==0||r==row-1||c==col-1){   // 数组的第一行最后一行第一列最后一列均为墙
    				p[r][c]=1;
    			}
    			else{
    				p[r][c] = rand()%100;
    				if(p[r][c]>=30)
    					p[r][c]=0;    // 0 表示课通过 
    				else
    					p[r][c]=1;// 出现墙 
    			}
    		}
    	p[1][1]=0;  //起点
    	p[row-2][col-2]=0;  // 终点
    	return OK;
    }
    
    int num = 1;
    
    Status printPuzzle(int **m,SqStack *s, int row, int col){  // 打印迷宫
    	sData *data,data1;
    	int k = s->top;    // 记录栈元素的总个数
    	int num1=0;
    	int flag=1;
    	data = &data1;
    	for(int i=0;i<row;i++){
    		for(int j=0;j<col;j++){
    			if(i==0||j==0||i==row-1||j==col-1||m[i][j]==1){   //  输出迷宫墙
    				printf("■");}
    			else{
    				data->row=i;
    				data->col=j;
    				if(searchStackData(s,data1)&&flag==1){	//输出当前位置 		
    					printf("※");
    					num1++;
    					if(num1 == num)
    						flag=0;
    				}
    				else{
    					printf("  ");
    				}
    					s->top=k;
    			}
    			}
    		printf("\n");  
    	}
    	return OK;
    }
    
    //迷宫寻找路径
    int search_path(int **m,int **mark,QNode *Q,int row,int col,int d[][2]){
    	int flag = 0;//判断是否可以走出迷宫 
    	sData *data,data1,data2;//data2为将要探索时的坐标点
    							//data1为探索点
    	data=&data1;
    	data->col = 1;
    	data->row = 1;
    	data->previous = -1;
    	EnQueue(Q,data1);
    	while(Q->front != Q->rear){   // 队列非空 
    		int i,j;
    		DeQueue(Q,data);
    		i = data->row;  //将行 列赋给i j 便于加上方向判断是否有路径
    		j = data->col;
    		mark[i][j] = true;  // 示已经走过
    		data2 = data1;
    		data2.previous = Q->front;   // 记录上个开始探索方向的初始位置
    		if((i==row-2)&&(j==col-2))   // 走出迷宫
    		{ 	flag=1;
    		 	break;}
    		for(int k=0;k<8;k++){   // 搜索八个方向
    			i=data->row;
    			j=data->col;
    			i+=d[k][0];
    			j+=d[k][1];
    			if(m[i][j]==1 || mark[i][j]==true)   // 遇见路障或者已在队列里
    				continue;
    			else{
    				data2.row=i;
    				data2.col=j;
    				mark[i][j]=true;
    				EnQueue(Q,data2); // 找到通路,入队
    			}
    		} 
    		Q->front++;
    	}  //while
    	return flag;	 
    }
    
    Status PushData(QNode *q,SqStack *s){   //  将通过的路径放进栈
    	sData data1;
    	int i;
    	i=q->front;  // 上一个元素的位置
    	while(i!=-1){    // 起点的值为 -1
    		data1=q->base[i];
    		Push(s,data1);  // 坐标入栈
    		i=q->base[i].previous;
    	}
    	return OK;
    }
    int showPuzzle(ElemType **m, int row, int col){
    	sData *data,data1;
    	data=&data1;
    	for(int i=0;i<row;i++){
    		for(int j=0;j<col;j++){
    			if(i==0||j==0||i==row-1||j==col-1||m[i][j]==1)    //  输出迷宫墙
    				printf("■");
    			else
    				printf("  ");
    		}
    		printf("\n");  
    	}
    	return OK;
    }
    
    int main(){
    	int row,col;  //  随机产生迷宫的大小
    	int flag;  // 判断是否走出了迷宫
    	int k;
    	int Directrion[8][2]={{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1}};   // 右下角逆时针方向寻找路径
    	ElemType **m=NULL,**mark=NULL;
    	SqStack *s,s1;
    	QNode *Q,q;
    	Q = &q;
    	s = &s1;
    	InitQueue(Q); // 初始化 ======
    	InitStack(s);
    	printf("请输入迷宫的大小!\n");
    	scanf("%d%d",&row,&col);
    	row=row+2;col=col+2;  // 迷宫外部需要加上墙,所以数组大小加2(上下,左右)
    	m=createPuzzle(row,col);  // 动态产生迷宫 m 
    	mark=createPuzzle(row,col);   // 标记走过的位置
    	for(int i=0;i<row;i++)
    		for(int j=0;j<col;j++)
    			mark[i][j]=false;   //  false 表示没有走过的位置
    	rand(m,row,col);  // 随机产生迷宫障碍物
    	flag=search_path(m,mark,Q,row,col,Directrion);  // 寻找路径
    	if(flag==1){    // 可以走出迷宫
    		PushData(Q,s);
    		k=s->top;
    		for(int i=0;i<k+1;i++){
    			system("cls");
    			printPuzzle(m,s,row,col);  // 打印迷宫
    			num++;
    			Sleep(500);
    		}
    		StackTraverse(s);   // 输出坐标
    	}
    	else
    	{
    		showPuzzle(m,row,col);
    		printf("No Path!\n");
    	}
    return 0;
    }

     (请不要直接复制使用。代码仅供参考,希望读者借此代码自身可以理解学习)

    如果代码对您有帮助,不要忘记评论收藏噢~

    展开全文
  • 迷宫 迷宫 迷宫迷宫迷宫迷宫迷宫迷宫迷宫迷宫数据结构
  • C语言数据结构迷宫.rarC语言数据结构迷宫.rarC语言数据结构迷宫.rar
  • c语言数据结构迷宫算法 有详细的注释 动态堆栈的详细
  • 数据结构 c语言迷宫程序 数据结构 c语言迷宫程序
  • 数据结构 C语言 迷宫问题求解 栈 针对严蔚敏 吴伟民编著的数据结构C语言版)中讲到栈的时候,会有一个迷宫求解的实验题,我写了一下,然后希望对别人有帮助……运行环境visual studio 2012
  • . . . #include <stdio.h> #include <stdlib.h> #include <time.h> #define M 20 #define N 20 #define visited 2 #define TRUE 1 #define FALSE 0 #define INITSIZE 100 typedef int Status; typedef struct{ //...
  • 初学数据结构C语言,尝试实现了迷宫求解问题。代码组织比较差,改进的地方也有很多,博君一乐而已。希望能够帮助到别人
  • 数据结构上机作业,C语言迷宫源代码,编译通过可运行
  • 自己编写的程序,数据结构C语言版的迷宫问题求解,希望对大家有所帮助
  • c语言数据结构迷宫求解 严蔚敏版 使用栈和结构体
  • C语言迷宫问题的源程序 C语言数据结构迷宫问题
  • 数据结构(C语言版)黄国瑜数据结构(C语言版)黄国瑜[General Information]书名=数据结构(C语言版)作者=页数=438SS号=0出版日期=Vss号封面页书名页版权页前言页目录页第1章 数据结构的基本概念1.1 何谓数据结构1.2 ...

    数据结构(C语言版)黄国瑜数据结构(C语言版)黄国瑜

    [General Information]

    书名=数据结构(C语言版)

    作者=

    页数=438

    SS号=0

    出版日期=

    Vss号

    封面页

    书名页

    版权页

    前言页

    目录页

    第1章 数据结构的基本概念

    1.1 何谓数据结构

    1.2 算法与伪码

    1.3 程序结构化与设计风格

    1.4 程序分析的方法

    1.5 时间复杂度分析

    1.6 渐近式表示法

    1.6.1 时间复杂度各类等级

    1.6.2 渐近式表示法

    1.7 递归式的复杂度计算

    第2章 数组

    2.1 何谓数组

    2.2 一维数组

    2.3 一维数组的使用

    2.4 一维数组的存取

    2.5 一维数组的遍历

    2.6 一维数组的高级应用

    2.7 二维数组

    2.8 数组表示法

    2.9 特殊类型的数组

    2.9.1 稀疏数组

    2.9.2 上三角数组

    2.9.3 下三角数组

    第3章 链表

    3.1 何谓链表

    3.2 单链表的建立

    3.2.1 单链表内节点的配置

    3.2.2 单链表内节点的释放

    3.2.3 单链表的建立与释放

    3.2.4 单链表的查找

    3.3 单链表的基本处理

    3.3.1 单链表内节点的插入

    3.3.2 单链表内节点的删除

    3.3.3 单链表的反转

    3.3.4 单链表的链接

    3.3.5 单链表的比较

    第4章 堆栈

    4.1 何谓堆栈

    4.2 用数组仿真堆栈

    4.3 用链表仿真堆栈

    4.4 表达式表示法

    4.5 中序表达式的表示法及计算

    4.6 前序表达式的表示法及计算

    4.7 后序表达式的表示法及计算

    4.8 表达式的转换

    第5章 队列

    5.1 何谓队列

    5.2 用数组仿真队列

    5.3 用链表仿真队列

    5.4 环状队列

    5.5 双向队列

    5.5.1 输入限制性双向队列

    5.5.2 输出限制性双向队列

    第6章 递归

    6.1 何谓递归

    6.2 函数调用与参数传递

    6.3 数学问题

    6.3.1 阶乘问题

    6.3.2 最大公因子问题

    6.3.3 费氏级数问题

    6.3.4 组合公式

    6.4 河内塔问题

    6.5 N皇后问题

    6.6 迷宫问题

    第7章 基础树状结构

    7.1 何谓树状结构

    7.1.1 何谓树

    7.1.2 树的相关名称及意义

    7.2 二叉树

    7.2.1 何谓二叉树

    7.2.2 二叉树和树的比较

    7.2.3 二叉树的相关特色

    7.3 二叉树表示法

    展开全文
  • C语言数据结构迷宫求解 最近在学数据结构,然后在迷宫求解问题上,在网上搜索到的代码写的不够详细,所以打算写一下详细一点的代码,尽量包含一些完整的注释,帮助大家理解。下面贴出代码 这份代码使用的是回溯法来...

    C语言数据结构迷宫求解

    最近在学数据结构,然后在迷宫求解问题上,在网上搜索到的代码写的不够详细,所以打算写一下详细一点的代码,尽量包含一些完整的注释,帮助大家理解。下面贴出代码

    这份代码使用的是回溯法来求解,回溯法就是沿这一个方向进行探索,如果失败,则原路返回,如果可以走通,则继续往下走。

    #include <stdio.h>
    #include <stdlib.h>
    #include<malloc.h>
    typedef struct Data {
    	int x;
    	int y;
    	int k;							//这是下一步走的方向(与主函数里的move[][0]对应,move二维数组里的x位)
    
    } data;							//数据结构体,记录迷宫走的坐标
    
    typedef struct StackTop {
    	data* d;
    	int top;				//栈顶
    	int size;			//栈的大小
    
    }Stack;					//栈的结构体
    
    
    void CreateStacks(Stack **p)					//创建栈
    {
    	Stack *top = NULL;
    	top = (Stack*)malloc(sizeof(struct StackTop));
    	if (top == NULL)
    	{
    		printf("Create failed\n");
    		exit(0);
    	}
    	else
    	{
    		top->d = (data*)malloc(100 * sizeof(data));			//这个100是为了创建较大一点的线性表
    		top->top = -1;					//在寻找路径时会先进行入栈,所以初始化为-1
    		top->size = 100;				//往大的方面写,以免不够用
    	}
    	*p = top;
    
    }
    
    int IsEmpty(Stack *p)			//判断栈是否为空
    {
    	if (p->top == -1)
    	{
    		printf("NULL\n");
    		return 1;
    	}
    	else {
    		return 0;
    	}
    
    }
    
    
    void Push(Stack **p, data x)					//入栈
    {
    	data s;
    	Stack* top;
    	top = *p;
    	if (top->top == top->size - 1)				//因为top是记录数组下标的,所以是从0开始记录,而size从1开始记录
    	{
    		printf("FULL\n");
    		exit(0);
    	}
    	else
    	{
    		top->top++;							//栈顶加一
    		top->d[top->top] = x;					//入栈
    	}
    
    }
    
    void Pop(Stack **p)
    {
    	Stack* top;
    	top = *p;
    	if (IsEmpty(top))
    	{
    		exit(0);
    	}
    	else
    	{
    		top->top--;
    
    	}
    
    }
    
    data getStackTop(Stack *top)					//取栈顶首元素
    {
    	if (top->top == -1)
    	{
    		printf("NULL\n");
    
    	}
    	else
    	{
    		return top->d[top->top];
    	}
    
    }
    
    void Path(int maze[][12], int mark[][12], int x1, int y1, int x2, int y2, Stack **p, int diretction[8][2])
    {
    	Stack* top;
    	top = *p;
    	int dir;								//下一步要走的方向
    	int dir1, dir2, dir3, dir4;				//dir3与dir4为dir1,dir2两个当前坐标加上diretction数组的移动坐标得到的移动后的坐标
    	int flag = 0;
    	data s;
    	data s1;
    	s.x = x1;
    	s.y = y1;
    	s.k = -1;
    
    	mark[x1][y1] = 1;
    	Push(&top, s);
    
    	while (!IsEmpty(top))
    	{
    		s1 = getStackTop(top);
    		Pop(&top);
    		dir1 = s1.x;               //dir1为移动前坐标
    		dir2 = s1.y;				//dir2为移动前坐标
    		dir = s1.k + 1;				//拿到diretction二维数组的前一个下标,等价于方向,因为diretction只需要第一个下标变化
    		while (dir <= 7)
    		{
    
    			dir3 = dir1 + diretction[dir][0];     //dir3与dir4为dir1,dir2两个当前坐标加上diretction数组的移动坐标得到的移动后的坐标
    			dir4 = dir2 + diretction[dir][1];
    			if (maze[dir3][dir4] == 0 && mark[dir3][dir4] == 0)                  //迷宫路径为0,且当前位置没走过
    			
    			{
    				mark[dir3][dir4] = 1;								//记录走过路径
    				s1.x = dir1;										//覆盖位置
    				s1.y = dir2;
    				s1.k = dir;
    				Push(&top, s1);									//入栈
    				dir1 = dir3;									//当前位置更替为之前移动的位置
    				dir2 = dir4;
    				dir = -1;
    			}
    			if (dir3 == x2 && dir4 == y2)			//如果抵达终点,进行出栈,将路径打印出来
    			{
    				printf("The revers path is:\n");
    				while (!IsEmpty(top))
    				{
    					s = getStackTop(top);
    
    					printf("the node is :%d  %d\n", s.x, s.y);
    					Pop(&top);
    
    				}
    				flag = 1;							//标志符,将外面的循环结束
    				break;
    
    			}
    
    			dir++;
    		}
    		if (flag == 1)    //将外面的循环结束
    		{
    			break;
    		}
    	}
    }
    
    
    int main()
    {
    	Stack *p = NULL;
    	int maze[12][12] = {
    	{1,1,1,1,1,1,1,1,1,1,1,1},
    	{1,0,1,1,1,0,0,0,0,0,0,1},
    	{1,0,0,0,1,0,0,0,1,0,0,1},
    	{1,0,1,0,1,1,0,0,1,0,0,1},
    	{1,0,1,0,0,1,0,1,1,0,0,1},
    	{1,0,1,0,0,1,0,1,1,0,0,1},
    	{1,1,1,1,0,1,0,1,0,0,0,1},
    	{1,0,0,1,0,0,0,1,0,1,1,1},
    	{1,0,0,1,0,0,0,1,0,1,1,1},
    	{1,0,1,1,0,1,0,1,0,0,0,1},
    	{1,0,0,0,0,1,0,1,1,1,0,1},
    	{1,1,1,1,1,1,1,1,1,1,1,1} };	//迷宫是10*10,但是为了方便,不让节点走出迷宫范围外,选择12*12,在迷宫周围布上一层“围墙“(0是路径,1是墙)
    	int x = 1, y = 1;     //迷宫起点
    	int mark[12][12];		//这是记录路径的表,记录走过的路径
    	for (int i = 0; i < 12; i++)
    	{
    		for (int j = 0; j < 12; j++)				//因为懒得一个个输入0了,所以直接初始化了。
    		{
    			mark[i][j] = 0;
    		}
    	}
    	int move[8][2] = { {0,1} ,{1,0},{-1,0} ,{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };			//行走的方向
    	int x1 = 10, y1 = 10;				//终点
    	CreateStacks(&p);					//创建栈
    	Path(maze, mark, x, y, x1, y1, &p, move);		//寻找路径
    	return 0;
    }
    
    
    展开全文
  • 迷宫程序 数据结构 C语言,一个小小的迷宫程序希望对大家有帮助,谢谢
  • 数据结构C语言迷宫

    2020-04-12 01:22:28
    这是大一数据结构迷宫作业,用c实现 #include <stdio.h> #include <stdlib.h> #define MAXSIZE 12 #define ERROR -1 #define OK 1 #define FALSE 0 #define TRUE 1 typedef enum{RIGHT,DOWN,LEFT,UP ...

    这是大一数据结构迷宫作业,用c实现

    #include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 12
    #define ERROR -1
    #define OK   1
    #define FALSE 0
    #define TRUE  1
    typedef enum{RIGHT,DOWN,LEFT,UP
    			}diraction;
    typedef enum{YES,NO
    			}MarkTag;
    typedef struct position   //迷宫中位置的坐标
    	{   
    		int x;
       		int y;
    	}Position;
    typedef struct
    {  	
    	int order;          //当前位置在路径中的序号
      	Position coordinate;       //当前位置在迷宫中的坐标
      	diraction orientation;       //从当前位置走到下一位置的方向
    }SElemType;              //栈元素的类型
    typedef struct
    { 
    	SElemType *elem;
      	int top;
    }Stack;
    char maze[MAXSIZE][MAXSIZE]=
    	 {
    		 {'*','*','*','*','*','*','*','*','*','*','*'},
    		 {'*','0','0','0','0','0','0','1','0','0','*'},		 
    		 {'*','0','0','1','0','0','0','1','1','0','*'},		 
    		 {'*','1','0','1','0','1','1','0','0','0','*'},		 
    		 {'*','0','0','1','1','0','0','0','0','0','*'},		 
    		 {'*','0','0','1','1','0','0','0','0','0','*'},		 
    		 {'*','0','1','1','0','0','1','0','0','0','*'},		 
    		 {'*','0','1','1','1','0','1','1','0','0','*'},		 
    		 {'*','0','0','0','0','0','0','0','0','0','*'},		 
    		 {'*','*','*','*','*','*','*','*','*','*','*'}
     	}; 	
    int InitStack(Stack *S)             //创建一个空栈
    {
    	 S->elem=(SElemType*)malloc(MAXSIZE*MAXSIZE*sizeof(SElemType));
    	 if(!S->elem)  
    	 	return ERROR;
    	 S->top=0;
    	     return OK;
    }  
    int Push(Stack *S,SElemType e)     //元素e入栈
    {   
    	if(S->top>=MAXSIZE*MAXSIZE)  
    	   return ERROR;
     	S->elem[S->top++]=e;
     		return OK;
    } 
    int Pop(Stack *S,SElemType *e) //栈顶元素出栈,由e带回栈顶元素
    {   
    	if(S->top<=0)
    	     return ERROR;
      	*e=S->elem[--S->top];
      		 return OK;
    }
    int Empty(Stack S)    //判断栈是否为空
    {  
    	if(S.top==0)
    	    return TRUE;
       	else   
       		return FALSE;
    } 
    int createMaze(Position *startpos,Position *endpos)
    { 
    	Position start,end;
        printf("\n\n");
     	printf("请输入迷宫入口的位置:");
     	scanf("%d%d",&start.y,&start.x);
    	printf("请输入迷宫出口的位置:");
     	scanf("%d%d",&end.y,&end.x);
         *startpos=start; *endpos=end;
     return OK;
    }  //createMaze
    int canPass(Position canpos)
    {    
    	if(maze[canpos.x][canpos.y]=='0')  
    	   return TRUE;
         	return FALSE;
    }   //canPass
    void markPos(Position canpos,MarkTag tag)     //为已经探索过的位置加标记
    {  
      	switch(tag)
     	{ 
    	  case YES: maze[canpos.x][canpos.y]='R'; break;   //路径标记
    	  case NO:  maze[canpos.x][canpos.y]='X'; break;   //死胡同标记
     	}
    }  
    //根据当前的位置坐标和下一步要探索的方向dir求下一步要走的位置坐标
    Position nextPos(Position canpos,diraction dir)
    {    
    Position nextpos;
    switch(dir)
      {  case RIGHT:nextpos.x=canpos.x ;nextpos.y =canpos.y +1; break;
         case DOWN :nextpos.x=canpos.x+1 ;nextpos.y =canpos.y; break;
         case LEFT :nextpos.x=canpos.x ;nextpos.y =canpos.y -1; break;
         case UP :nextpos.x=canpos.x-1 ;nextpos.y =canpos.y;  break;
      }
      return nextpos;
    }
    diraction nextDir(diraction dir)//回溯到上个节点的下个方向
    {  switch(dir)
      {   case RIGHT: return DOWN;
          case DOWN : return LEFT;
          case LEFT: return UP;
      }
    }
    int Solve(Stack *S,Position start,Position end)
    {//若迷宫中存在从入口start到出口end的通道,则求得一条存放在栈S中,并返回TRUE,若迷宫中不存在从入口start到出口end的通道,并返回FALSE
     Position canpos;
     SElemType e;
     int canstep=1;   //共用的步数
    if(InitStack(S)==ERROR)  
    	return FALSE;
     	canpos=start;
    do{
     	if(canPass(canpos)){      //当前位置可以通过
    	     markPos(canpos,YES);   //留下足迹
    	     e.order=canstep;e.coordinate=canpos;e.orientation=RIGHT;
    	     Push(S,e);             //当前位置加入路径
        if(canpos.x==end.x&&canpos.y==end.y)   //当前位置是出口
          	return TRUE;
         canpos=nextPos(canpos,RIGHT);
         canstep++;
      	}	
      	else{              //当前位置不能通过
    		if(!Empty(*S))
    			{
     			if(Pop(S,&e)==ERROR)
     	   			return FALSE;
         		while(e.orientation==UP&&!Empty(*S)){
         //四个方向都试探过,没有找到通路也不能继续探索,则回溯
          		canpos=e.coordinate;
          		markPos(canpos,NO);
    		    if(Pop(S,&e)==ERROR)  
    		    	return FALSE;
    					}
    	    	if(e.orientation!=UP){   //四个方向还没有试探完
    		      e.orientation=nextDir(e.orientation);
    		      Push(S,e);  //换下一个方向探索
    		      canpos=nextPos(e.coordinate,e.orientation);
    				}				
    		 	}	
     		}	
     	}
    while(!Empty(*S));
    	return FALSE;
    }
    void main()
    {   
    	int i,j;
    	printf("迷宫地图,0位路径,1为墙壁,X为不能通过,R为可以通过路径,*为墙壁\n"); 
        for(i=0;i<10;i++){
    		 	for(j=0;j<11;j++)
    	    	printf("%c ",maze[i][j]);	    	
    	        printf("\n");
    	        }
    	Position startPos,endPos;
        Stack path; 
    	SElemType e;
    	if(createMaze(&startPos,&endPos)==ERROR) return ;
     		Solve(&path,startPos,endPos);
    	while(!Empty(path)){    //输出出口到入口的路径
      	Pop(&path,&e);
      	printf("(%d,%d)",e.coordinate.x,e.coordinate.y);
     }
    	printf("\n");//输出迷宫的图形
    	    for(i=0;i<11;i++)
    	     {
    		 	for(j=0;j<10;j++)	 	
    	    	printf("%c ",maze[i][j]);    	
    	        printf("\n");
    	        }
    }
    
    展开全文
  • 有注释,根据严蔚敏的数据结构C语言版)里的伪代码弄的,编译环境是gcc,已生成exe文件。
  • 数据结构C语言)课设7——迷宫求解 题目描述: 以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 #include <...
  • 数据结构迷宫 c语言完整代码 迷宫代码 迷宫完整代码
  • 数据结构 迷宫求解 c语言编写 ------------------- ------------------- -------------------
  • 数据结构C语言版本)

    万次阅读 多人点赞 2018-04-22 19:42:32
    数据结构C语言版本) 第1章 绪论 1.常用的数据结构类型:集合、线性、树形、图状。 2.数据结构: - 逻辑结构:数据元素之间的关系 - 存储结构:数据结构在计算机中的表示。存储结构分为:顺序存储结构和...
  • 通过自己创建一个迷宫 然后实现迷宫的走法 c语言数据结构
  • 数据结构C语言版)经典问题 绝对经典 不信你下了看看
  • 主要为大家详细介绍了C语言数据结构迷宫问题,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,296
精华内容 918
关键字:

数据结构迷宫c语言

c语言 订阅
数据结构 订阅