精华内容
下载资源
问答
  • 数据结构迷宫问题

    2019-08-11 21:40:09
    分别用广度优先搜索和深度优先搜索实现迷宫路径的动态查找。
  • . . . #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++编写的迷宫问题路径求解程序,使用的是栈方法,即将路径上每一步存在栈中,迷宫文件格式见程序提示,压缩包内已经给出了三个测试用的迷宫地图可用来测试,支持分步显示查找路径过程功能,当给...
  • 数据结构 迷宫问题

    2012-02-27 11:58:22
    以一个M×N的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 (1) 根据二维数组,输出迷宫的图形。 (2) 探索迷宫的四个...
  • 使用者自定义的数据结构 向量和矩阵不是MATLAB提供的将数据组合成一个实体的唯一手段使用者自定 义的数据结构也是有效的它能够使程序设计者创造出数字字符串和数组混 合在一起的变量类型作为例子我们创造一个包含一...
  • C语言数据结构迷宫问题思路:首先,迷宫如何用计算机语言表示?一般用二维数组。0表示墙,1表示路。其次,其次就是如何从迷宫中走出来了。结合堆栈,进行搜索。你可以尝试着对问题进行分层,然后逐步细化来解决。...
  • 已运行过,可自定义迷宫 从键盘输入起点和终点,输出路径。 运用了链栈进行存储,下载即可运行 已运行过,可自定义迷宫 从键盘输入起点和终点,输出路径。 运用了链栈进行存储,下载即可运行 已运行过,可...
  • 摘要 本文详细介绍了迷宫问题的设计与实现 该程序具有迷宫的设计生成 逃离 迷宫的路线的寻找 打印逃离路线及标拄了逃离路线的迷宫等功能 在课程设计 中程序设计语言采用 Visual C++ 程序运行平台为 Windows 98/2000...
  • 数据结构迷宫代码

    2017-12-07 20:45:01
    首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以 三元组(i,j,d)的形式输出,其中(i,j)指示迷宫中的一个位置(行号和列号),d 表示走到下一 位置的方向(对于迷宫中...
  • 数据结构 (C语言版)上面的第三章栈与队列中的迷宫问题
  • 数据库课程设计 迷宫问题 附有可执行的代码
  • 关于数据结构C的 严蔚敏般的 大二时做实验的 希望对你有帮助
  • 数据结构 迷宫问题 希望有用 ,不好意思 数据结构 迷宫问题 希望有用
  • 第一行数据表示一个 n*n (n)的迷宫;第二行开始的n行为迷宫数据。 其中:0表示路,1表示墙,起点在左上角 ,1> 的位置,终点在右下角 ,n> 的位置。 输出:若有解,输出从入口到出口的一条路径,否则输出 there is ...
  • 迷宫实验是取自心理学的一个古典实验。在该实验中,把一只老鼠从一个无顶大盒子的门放入,在盒中设置了许多墙,对行进方向形成了多处阻挡。盒子仅有一个出口处放置一块奶酪,吸引老鼠在迷宫中寻找道路以到达出口。对...
  • 这个文档详细的介绍了利用栈和队列解决迷宫问题的步骤,对与初学者学习数据结构能很好的进行辅导
  • 就是大学的时候做的实习包括源代码,实习报告,可以拿去给老师交差。
  • 链式栈结构的实现 #include"fstream" #include<string> #include<iostream> using namespace std; #define OK 1 #define ERROR 0 typedef int SElemType; typedef int Status; typedef struct SNode ...

    链式栈结构的实现

    思路:

    使用链式栈存储可通过的路径;

    若当前结点已经走过上下左右四个方向仍不可通行,则把这个点弹出;

    具体迷宫实现是课本的函数例子。
    在这里插入图片描述

    在这里插入图片描述

    代码部分

    #include<string>
    #include<iostream>
    
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    typedef int SElemType;
    typedef int Status;
    
    typedef struct//迷宫
    {
    	int x;
    	int y;
    }PosType;
    
    typedef struct {//使用结构体存储栈中元素
    	int ord;//通道块在路径中的序号
    	PosType seat;//通道块在迷宫中的“坐标位置”
    	int di;//从此通道块走向下一通道块的“方向”
    }MazeNode;
    
    typedef struct SNode {//链式存储栈结点
    	MazeNode data;
    	struct SNode* next;
    }StackNode;
    
    typedef struct LStack//链式栈结构
    {
    	StackNode *top;
    	StackNode *bottom;//定义栈底,却不对栈底进行操作
    	int size;
    }LinkStack;
    
    int Maze[10][10] = {  //定义迷宫
    {1,1,1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,0,0,0,0,1},
    {1,0,0,0,0,1,1,0,1,1},
    {1,0,1,1,1,0,0,0,0,1},
    {1,0,0,0,1,0,0,0,0,1},
    {1,0,1,0,0,0,1,0,0,1},
    {1,0,1,1,1,0,1,1,0,1},
    {1,1,0,0,0,0,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1}
    };
    
    LinkStack InitStack(LinkStack s)//栈初始化
    {
    	s.top = s.bottom = NULL;
    	s.size = 0;
    	return s;
    }
    
    int StackEmpty(LinkStack s)//判断栈是否为空
    {
    	if (s.top == NULL && s.bottom == NULL)
    	{
    		return ERROR;
    	}
    	else
    	{
    		return OK;
    	}
    }
    
    LinkStack push(LinkStack s, MazeNode x)//进栈操作
    {
    	StackNode *t = (StackNode *)malloc(sizeof(StackNode));
    	if (t == NULL)
    		return s;
    	if (StackEmpty(s) == ERROR)
    	{
    		s.top = s.bottom = t;
    		t->next = NULL;
    		s.top->data = x;
    		printf("(%d,%d)\n", s.top->data.seat.x, s.top->data.seat.y);
    		s.size++;
    		printf("%d\n", s.size);
    		return s;
    	}
    	else
    	{
    		t->next = s.top;//续上原来的栈顶
    		s.top = t;
    		s.top->data = x;
    		s.size++;
    		return s;
    
    	}
    }
    
    LinkStack pop(LinkStack s)//出栈操作
    {
    	StackNode *t;
    	MazeNode q;
    	if (StackEmpty(s) == ERROR)
    	{
    		printf("栈为空,无法进行出栈操作\n");
    		return s;
    	}
    	if (s.top == s.bottom)//出栈元素为栈底元素
    	{
    		q = s.top->data;
    		printf("出栈元素为(%d,%d)\n", q.seat.x, q.seat.y);
    		free(s.top);
    		s.top = s.bottom = NULL;
    		s.size--;
    		return s;
    	}
    	else
    	{
    		q = s.top->data;
    		printf("出栈元素为(%d,%d)\n", q.seat.x, q.seat.y);
    		t = s.top->next;
    		free(s.top);
    		s.top = t;
    		s.size--;
    		return s;
    	}
    }
    
    void PrintAll(LinkStack s)//输出所有栈中元素
    {
    	if (StackEmpty(s) == ERROR)
    	{
    		printf("此栈为空栈!\n");
    	}
    	printf("栈中元素为:");
    	while (s.top != NULL)
    	{
    		printf("(%d,%d)\n", s.top->data.seat.x, s.top->data.seat.y);
    		s.top = s.top->next;
    	}
    }
    
    LinkStack DeleteStack(LinkStack s)//销毁栈
    {
    	StackNode *t;
    	while (s.top != NULL)
    	{
    		t = s.top->next;
    		free(s.top);
    		s.top = t;
    	}
    	return s;
    }
    
    
    
    bool pass(PosType postion)//判断是否可以通过
    {
    	if (Maze[postion.x][postion.y] == 0)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }
    
    PosType NextPos(PosType now, int dirction)//转向函数
    {
    	PosType next;
    	switch (dirction)
    	{
    	case 1:
    	{
    		next.x = now.x;
    		next.y = now.y + 1;
    		printf("向右走~\n");
    		break;
    	}
    	case 2:
    	{
    		next.x = now.x + 1;
    		next.y = now.y;
    		printf("向下走~\n");
    		break;
    	}
    	case 3:
    	{
    		next.x = now.x;
    		next.y = now.y - 1;
    		printf("向左走~\n");
    		break;
    	}
    	case 4:
    	{
    		next.x = now.x - 1;
    		next.y = now.y;
    		printf("向上走~\n");
    		break;
    	}
    	default:
    		break;
    	}
    	return next;
    }
    
    void footprint(PosType p,int step)
    {
    	Maze[p.x][p.y] =4;//走过且走通的点标记为4
    	printf("走过~");
    }
    
    void Markprint(PosType p)
    {
    	Maze[p.x][p.y] = -1;//走过且走不通的点退栈,标记为0
    }
    
    
    int main()
    {
    	printf("输出预设迷宫矩阵:\n");
    	for (int i = 0; i < 10; i++)
    	{
    		for (int j = 0; j < 10; j++)
    		{
    			if (Maze[i][j] == 0)
    			{
    				printf("O\t");//走通路径
    			}
    			else
    			{
    				printf("#\t");//墙壁
    			}
    		}
    		printf("\n");
    	}
    	LinkStack path;
    	path.size = 0;
    	path = InitStack(path);//栈初始化
    	PosType curpose;
    	curpose.x = 1;
    	curpose.y = 1;
    	int curstep = 1;//步数
    	do
    	{
    		if (pass(curpose))//模仿课本程序
    		{
    			footprint(curpose,curstep);
    			MazeNode e;
    			e.di = 1;
    			e.ord = curstep;
    			e.seat.x = curpose.x;
    			e.seat.y = curpose.y;
    			path = push(path, e);
    			if (curpose.x == 8 && curpose.y == 8)break;
    			curpose = NextPos(curpose,e.di);
    			curstep++;
    		}
    		else
    		{                                 //这里课本错误,不应该直接pop,因为这时候curpose根本没有入栈
    			if (StackEmpty(path) == OK)
    			{
    				MazeNode e=path.top->data;
    				while (StackEmpty(path) == OK && path.top->data.di == 4)
    				{
    					path = pop(path);
    					Markprint(path.top->data.seat);
    					printf("栈顶元素为:(%d,%d)", path.top->data.seat.x, path.top->data.seat.y);
    					curstep--;
    					//break;
    				}
    				footprint(path.top->data.seat, curstep);
    				if (path.top->data.di < 4)
    				{
    					curpose = NextPos(path.top->data.seat, path.top->data.di + 1);
    					path.top->data.di++;
    					curstep++;
    					path=push(path, path.top->data);
    				}
    			}
    		}
    
    	} while (StackEmpty(path) == OK);
    	printf("\n");
    	printf("输出迷宫可走通路径:\n");
    	for (int i = 0; i < 10; i++)               //输出迷宫结果
    	{
    		for (int j = 0; j < 10; j++)
    		{
    			if (Maze[i][j] == 4)
    			{
    				printf("√\t");//走通路径
    			}
    			else if (Maze[i][j] == -1)
    			{
    				printf("×\t");//未走通路径
    			}
    			else
    			{
    				printf("#\t");//墙壁
    			}
    		}
    		printf("\n");
    	}
    	system("PAUSE");
    	return 0;
    }
    

    运行结果

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    问题与反思

    定义栈结构时,由于data又是一个mazenode栈,可以说栈又嵌套了栈,为函数外部的赋值造成了困难。以后要尽量避免。如果需要栈嵌套,函数最好使用指针传参,否则函数内部的值传不出去。

    展开全文
  • 很完善的代码, ...迷宫中不能使用递归算法查找路径。 2.试探方向限定为上、下、左、右四个方向。 3.迷宫要随机生成。 4.生成从迷宫入口到出口的最短和最长路径。 5.迷宫的入口和出口由键盘输入。
  • 数据结构迷宫问题C++实现

    千次阅读 2017-05-27 22:27:52
    利用堆栈性质实现数据结构迷宫问题

    出现实现图:



    .h文件实现堆栈简易操作(此处没有将声明与实现分离,应注意!)

    #pragma warning (disable : 4715)
    #ifndef  STACK_H
    #define STACK_H
    struct Position//结构体位置,表示迷宫每一格的行号和 列号
    {
    	int row;//行号
    	int col;//列号
    };
    class Stack
    {
    public:
    	Stack(int MaxSize = 10);
    	~Stack() { delete[] Element; };
    	bool IsEmpty() const { return top == -1; }
    	bool IsFull() const { return top == Maxtop; }
    	Position Top() const;//返回栈顶元素
    	Stack& Add(Position &x);//添加元素
    	Stack& Delete(Position &x);//删除元素
    private:
    	int top;//栈顶,入栈和出栈的地方。
    	int Maxtop;//栈顶元素位置。
    	Position *Element;
    };
    Stack::Stack(int MaxSize)
    {
    	Maxtop = MaxSize - 1;
    	Element = new Position[MaxSize];
    	top = -1;
    }
    Position Stack::Top() const
    {
    	if (IsEmpty())
    	{
    	}
    	else
    		return Element[top];
    }
    Stack& Stack::Add(Position &x)
    {
    	if (IsFull())
    	{
    	}
    	else
    	{
    		++ top;
    		Element[top].row = x.row;
    		Element[top].col = x.col;
    	}
    	return *this;
    }
    Stack& Stack::Delete(Position &x)
    {
    	if (IsEmpty())
    	{
    	}
    	else
    	{
    	
    		x.row = Element[top].row;
    		x.col = Element[top].col;
    		--top;
    	}
    	return *this;
    }
    #endif 

    源文件:

    #include<iostream>
    #include"STack.h"
    using namespace std;
    int main()
    {
    	cout << "老鼠迷宫!" << endl;
    //构建迷宫。maze[1][1]表示入口, maze[10][10]表示出口。
    	char **maze = new char *[12];
    	for (int i = 0; i < 12; ++i)
    		maze[i] = new char[12];
    
    	//给迷宫加“墙”。
    	for (int i = 0; i < 12; ++i)
    	{
    		maze[11][i] = '+';
    		maze[0][i] = '+';
    		maze[i][0] = '+';
    		maze[i][11] = '+';
    	}
    	//构建迷宫,用符号+表示墙壁,空格表示通路,以使迷宫尽可能好看!
    	for (int a = 1; a < 11; ++a)
    		for (int b = 1; b < 11; ++b)
    			maze[a][b] = ' ';
    	for (int i = 2; i < 7; ++i)
    		maze[1][i] = '+';
    	maze[2][6] = maze[2][8] = maze[3][4] = maze[3][6] = maze[4][2] = maze[4][4] = maze[4][6] = maze[4][8] = maze[4][9] = '+';
    	maze[5][2] = maze[5][4] = maze[5][6] = maze[5][8] = maze[6][2] = maze[6][3] = maze[6][4] = maze[6][6] = maze[6][8] = maze[6][10] = '+';
    	maze[7][2] = maze[7][6] = maze[7][8] = maze[7][10] = maze[8][2] = maze[8][4] = maze[8][5] = maze[8][6] = maze[8][8] = '+';
    	maze[9][1] = maze[9][8] = maze[10][5] = maze[10][6] = maze[10][7] = maze[10][8] = '+';
    	//输出迷宫 布局。
    	cout << "迷宫如下所示:" << endl;
    	for (int a = 0; a < 12; ++a)
    	{
    		for (int b = 0; b < 12; ++b)
    			cout << maze[a][b] << " ";
    		cout << endl;
    	}
    	//构建迷宫完毕,开始寻找路径。
    	Stack* Path = new Stack(10*10 - 1);//栈用来储存路径以及遇到障碍物时方标返回上一步。
    
    	Position offset[4];//设置模拟移动方法。
    	offset[0].row = 0; offset[0].col = 1;//右移
    	offset[1].row = 1; offset[1].col = 0;//下移
    	offset[2].row = 0; offset[2].col = -1;//左移
    	offset[3].row = -1; offset[3].col = 0;//上移
    
    	Position here;//代表当前位置。
    	here.col = 1;
    	here.row = 1;
    	maze[1][1] = '#';//入口堵住,防止返回入口。
    	int option = 0;//上、下、左、右四种走法。记录走的次数,一共四次,上下左右分布探索。
    	int Lastoption = 3;
    	//模拟移动,开始寻找出口。
    	while (here.row != 10 || here.col != 10)
    	{
    		int x, y;
    		while (option <= Lastoption)//最多循环4次,尝试每种走法。
    		{
    			x = here.row + offset[option].row;
    			y = here.col + offset[option].col;
    			if (maze[x][y] == ' ')//只要寻找得到通路,就退出循环。
    				break;
    			option++;
    		}
    		if (option <= Lastoption)
    		{//移动一次,是通路,此处位置入栈,移动数option归0。
    			Path->Add(here);
    			here.row = x;
    			here.col = y;
    
    			maze[x][y] = '*';//将该处修改为墙壁,防止返回,做重复工作。
    			option = 0;
    		}
    		else//不是通路,会退一步,路径记录栈栈顶元素出栈。
    		{
    			if (Path->IsEmpty())//出现空栈,表明该迷宫没有出口!
    				cout << "这个迷宫没有出口!" << endl;
    			Position next;
    			next.col = next.row = 0;
    			Path->Delete(next);//新的位置,表示here的前一步,用来回退。
    
    			if (next.row == here.row)
    			option = 2 + next.col - here.col;//通过计算得出回退后应该执行哪一种走法!
    			else
    				option = 3 + next.row - here.row;
    			here = next;
    		}
    	}
    	cout << "老鼠找到了迷宫的出口!!" << endl;//以图形的样式输出寻找得到的路径。
    	for (int i = 0; i < 12; ++i)
    	{
    		for (int a = 0; a < 12; ++a)
    			cout << maze[i][a] << " ";
    		cout << endl;
    	}
    	system("pause");
    }
                  



    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,026
精华内容 6,010
关键字:

数据结构迷宫问题

数据结构 订阅