【数据结构实验】迷宫问题——线性表

目录

实验目的

实验内容（题目） 

实验环境

 程序代码

实验分析 

实验目的

1. 掌握并理解线性表的存储结构定义，包括线性表的顺序存储结构与链式存储结构。
2. 学习并掌握线性表的基本操作实现，如插入、删除、查找、遍历等基本运算。
3. 明确线性表的存储结构特点，包括它们的时间和空间复杂性，以及如何根据应用场景选择合适的线性表存储结构。
4. 通过设计一个解决迷宫问题的算法，本实验不仅旨在将线性表的理论知识应用于具体问题解决过程中，还意在提高分析问题和设计算法的实际能力，为更复杂的数据结构操作和应用打下坚实的基础。

实验内容（题目） 

迷宫问题：迷宫为一个mⅹn的阵列，阵列中的值为0或1（具体数值随机生成），分别表示可以通行（简称“通”）和不可以通行（简称“不通”），左上角（即“(1,1)”）为入口，右下角为出口（即“(m,n)”），每个格点的出行方向有8个。要求：设计一个算法完成找一条从入口到出口的最短路径。

实验环境

（1）软件系统

操作系统：Windows 10

编程环境：Embarcadero Dev-C++ 6.3，包含GNU GCC编译器和GDB调试器

（2）硬件系统

CPU：Intel(R) Core(TM) i7-10875H CPU @ 2.30GHz

内存：16GB

硬盘：500GB SSD

 程序代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 点结构定义
struct Point {
    int x, y;
    // 步数字段，用于记录从起点到当前点的步数
    int step;
};

// 方向数组，表示点可以移动的8个方向（上下左右以及对角线）
const int directions[8][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

vector<vector<int> > maze; // 迷宫
vector<vector<bool> > visited; // 访问标记
vector<vector<Point> > path; // 用于回溯路径

// 检查坐标 (x, y) 是否可以进入
bool isValid(int x, int y, int rows, int cols) {
    return x >= 0 && y >= 0 && x < rows && y < cols && maze[x][y] == 0 && !visited[x][y];
}

// BFS 算法找到迷宫的最短路径
bool bfs(int rows, int cols, Point &endPoint) {
    queue<Point> q;
    q.push({0, 0, 0}); // 起点入队
    visited[0][0] = true; // 标记起点已访问

    while (!q.empty()) {
        Point current = q.front();
        q.pop();

        // 到达终点
        if (current.x == rows - 1 && current.y == cols - 1) {
            endPoint = current; // 保存终点信息
            return true; // 找到路径
        }

        // 探索所有可能的方向
        for (int i = 0; i < 8; ++i) {
            int newX = current.x + directions[i][0];
            int newY = current.y + directions[i][1];

            if (isValid(newX, newY, rows, cols)) {
                q.push({newX, newY, current.step + 1});
                visited[newX][newY] = true;
                path[newX][newY] = current; // 记录来时的路径
            }
        }
    }

    return false;
}

// 从终点递归回溯到起点，并打印路径
void printPath(Point endPoint) {
    if (endPoint.x == 0 && endPoint.y == 0) {
        cout << "(" << endPoint.x + 1 << ", " << endPoint.y + 1 << ")";
        return;
    }
    printPath(path[endPoint.x][endPoint.y]);
    cout << " -> (" << endPoint.x + 1 << ", " << endPoint.y + 1 << ")";
}

int main() {
    int rows, cols;
    cout << "请输入迷宫的行数：";
    cin >> rows;
    cout << "请输入迷宫的列数：";
    cin >> cols;

    // 初始化迷宫和访问标记
    maze.resize(rows, vector<int>(cols));
    visited.resize(rows, vector<bool>(cols, false));
    path.resize(rows, vector<Point>(cols));

    cout << "请输入迷宫矩阵（0代表可通行，1代表不通行）：" << endl;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            cin >> maze[i][j];
        }
    }

    Point endPoint;
    if (bfs(rows, cols, endPoint)) {
        cout << "找到路径，路径如下：" << endl;
        printPath(endPoint);
        cout << endl << "总共需要步数：" << endPoint.step << endl;
    } else {
        cout << "未找到路径。" << endl;
    }

    return 0;
}

注意事项：

我使用的是DEVC++5.11，同学们如果遇到中文无法输入、显示乱码导致编译不通过的现象，只需要将编译器gcc设置为32位：

实验分析 

从以下方面分析：

1、正确性（输入的测试数据和测试结果，附测算截屏）

此代码使用了广度优先搜索（BFS）算法，它能够保证找到从起点到终点的最短路径，如果迷宫中存在一条路径。BFS通过探索最近的未访问邻居节点，并逐步扩展到更远的节点来工作。一旦到达终点，算法就会停止，确保了找到的路径是最短的。在回溯打印路径时，printPath 函数从终点递归地回溯到起点，保持了路径的连续性和正确性。

测算截屏：

2、可读性（主要在源代码中体现）

代码的可读性良好，因为使用了自解释的变量名和结构，且函数功能单一明确。例如，isValid 函数用于检查一个点是否可以进入，bfs函数用于执行宽度优先搜索，而 printPath 函数用于输出路径。同时，所有函数和数据结构都有清晰的注释，易于理解其用途。

3、健壮性（容错性，主要在源代码中体现，在此简要说明）

代码的健壮性表现在它能够处理无法到达终点的情况，并给出相应的输出信息。输入被严格限制在迷宫的边界内，且所有的vector都被初始化，这减少了出错的可能性。程序没有采用异常处理结构来处理输入错误等问题，这是未来改进的一个方向。

4、时间和空间复杂度（针对核心算法函数分析）

• 时间复杂度：广度优先搜索的时间复杂度为O(V + E)，其中V是顶点（迷宫中的单元格）数量，E是边的数量（在迷宫中，一个单元格可以最多与8个其他单元格相连）。在最坏的情况下，时间复杂度为O(n*m)，其中n和m分别是迷宫的行数和列数。
• 空间复杂度：空间复杂度也是O(n*m)，因为需要存储每个单元格的访问状态和来时的路径。此外，队列在最坏的情况下可能需要存储所有的单元格，如果迷宫几乎都是0（完全开放），则在队列中的元素数量将接近单元格的总数。