本文共 2930 字，大约阅读时间需要 9 分钟。

• 数据结构课程设计

• 迷宫问题求解（栈和队列）

任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；

要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

• 分析

该课设意在考察栈和队列的数据结构，我主要说一下代码的设计思路，供诸君参考，也方便以后自己复习。

要说考察掌握栈和队列最好是自己定义一个栈数据结构，我这里偷懒了，直接用的stack头文件，queue没用上。

• 迷宫使用0（能走）1（不能走）表示
• 路径存放在栈中
• 路径节点包含坐标信息x,y和下一个节点相对于该节点的方向信息next（上0右1下2左3 初始值为-1）
• 输出路径时需要倒换栈中元素顺序（如果使用自己的数据结构可以避免调换，直接倒序输出）

测试数据已给出在代码最后，我自认为代码注释很明白了，有什么问题或者bug欢迎评论留言

• Code，环境codeblocks17 通过

// @ChenYe 2018/12/27#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define green SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_GREEN|FOREGROUND_INTENSITY)#define white SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_BLUE|FOREGROUND_GREEN)#define red SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_INTENSITY)#define yellow SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_INTENSITY)#define MAXSIZE 100 // 正方形迷宫的最大尺寸using namespace std;typedef struct Position{    int x,y;    // 横纵坐标    int next;    // 表示方向，上0右1下2左3 初始值为-1}Position;int SearchWay(int x1,int y1,int x2,int y2,int Maze[MAXSIZE][MAXSIZE]){// 寻找 x1 y1-->x2 y2 的路径    int x,y,next,Find;    stack
       
         S;    Position p;    p.x=x1;p.y=y1;p.next=-1;    S.push(p);    Maze[x1][y1] = -1;  // 走过的路标记为-1    while(!S.empty())    {        x = S.top().x;        y = S.top().y;        next = S.top().next;        if(x==x2&&y==y2)    // 走到了终点        {            cout<<"迷宫路径如下："<
        
          SO; while(!S.empty()) // 调整栈中元素顺序 { SO.push(S.top()); S.pop(); } while(!SO.empty()) // 输出 { cout<<"("<
         
          <<","<
          
           <<")-->"; SO.pop(); } cout<<"end\n"; return 1; } // 没走到终点 Find = 0; while(next<4&&Find==0) // 查找该位置，即当前(x,y)可以走的方向 { next++; switch(next) { case 0: x = S.top().x-1; y = S.top().y; break; case 1: x = S.top().x; y = S.top().y+1; break; case 2: x = S.top().x+1; y = S.top().y; break; case 3: x = S.top().x; y = S.top().y-1; break; } if(Maze[x][y]==0) // （x，y）可以走 { Find = 1; } } if(Find == 1)// 走得通 {// 标记走的方向, 入栈 S.top().next = next; Position temp; temp.x = x; temp.y = y; temp.next = -1; S.push(temp); Maze[x][y] = -1; // 访问过标记为-1 } else// 走不通 {// 退栈 Maze[S.top().x][S.top().y] = 0; // 迷宫节点回溯为0 S.pop(); } } return 0; // 无路径}void ManuallyCreate(){ int x1,y1,x2,y2; int Maze[MAXSIZE][MAXSIZE]; int n; yellow; cout<<"注意：迷宫为正方形，3<=尺寸<=100；1表示墙壁,0表示路径。"<
           
            >n; cout<<"输入迷宫："<
            
             >Maze[i][j]; if(Maze[i][j]!=1&&Maze[i][j]!=0) // 迷宫合法检验 { red;cout<<"error input!!!"<
             
              >x1>>y1) { if(Maze[x1][y1]==1) { red;cout<<"起点不可行,请重新输入"<
              
               >x2>>y2) { if(Maze[x2][y2]==1||(x2>=n||y2>=n)) { red;cout<<"终点不可行,请重新输入"<
               
                >x1>>y1) { if(Maze[x1][y1]==1) { red;cout<<"起点不可行,请重新输入"<
                
                 >x2>>y2) { if(Maze[x2][y2]==1||(x2>9||y2>9)) { red;cout<<"终点不可行,请重新输入"<
                 
                  >choice; if(choice==2) { system("cls"); AutomaticallyCreate(); } else if(choice==1) { system("cls"); ManuallyCreate(); } else { red; cout<<"error input!!!"<
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://pjoen.baihongyu.com/