基于栈的走迷宫最短路径实现

成绩课程设计说明书(论文)题 目 课 程 名 称 数据结构课程设计 院（系、部、中心） 计算机工程学院 专 业 班 级 学 生 姓 名 学 号 设 计 地 点 设计起止时间：2016年12月25日至 2016年12月31日 数据结构课程设计题目（例如表达式求值问题求解）一、课程设计目的和要求目的：深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。要求：熟练运用C+语言、基本数据结构和算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计的全过程，不断地完善程序以提高程序的性能。二、题意说明及分析一个迷宫如图所示，它有一个入口和出口，其中白色单元表示通路，黑色单元表示路不通。寻找一条从入口到出口的路径，每步只能从一个白色单元走到相邻的白色单元，直至出口。使用栈实现走迷宫的功能，演示走迷宫的过程。可走的白色单元用0表示，不可走的黑色单元用1表示，使用栈，栈顶元素temp标记位置，走出迷宫。输出迷宫和走出路径。入口三、算法设计与分析用ArrayList 作为栈的数据结。ArrayList是java中Collection集合中线性表，可以通过add.remove操作添加删除元素，coordition是定义的内部类，用来存放一个节点的横纵坐标。这样，栈中的每个元素就是迷宫中一个位置的坐标。寻路算法(若存在路径，返回true；若不存在，返回false)：while 栈非空获取栈顶元素temp = stack.getTopif temp是出口位置跳出循环else 继续向下执行if temp上边可走 and temp上边未遍历把temp所在位置标记为已遍历，将temp 上边的位置加入栈顶进入下一次循环if temp右边可走 and temp右边未遍历把temp所在位置标记为已遍历，将temp 右边的位置加入栈顶进入下一次循环if temp下边可走 and temp下边未遍历把temp所在位置标记为已遍历，将temp 下边的位置加入栈顶进入下一次循环if temp左边可走 and temp左边未遍历把temp所在位置标记为已遍历，将temp 左边的位置加入栈顶进入下一次循环上下左右都不可走，标记temp为已读，并从栈中移出，进入下次循环最后退出while循环有两种情况：1）找到出口位置，那栈中保留的就是从入口到出口的路径2）栈为空，说明没有路径能从入口到出口四、源程序package com.test;import java.util.ArrayList;import java.util.List;public class Maprinth private int map;/存放迷宫矩阵，0表示可走，1表示不可走 private coordinate start;/记录起点坐标 private coordinate end;/记录终点坐标 private List stack;/栈 /* * 坐标 * */ class coordinate public int x; public int y; public coordinate(int x,int y) this.x = x; this.y = y; /* * 入栈 * */ public void push(coordinate co) if(this.stack!=null) this.stack.add(co); else this.stack = new ArrayList(); stack.add(co); /* * 获取栈顶元素 * */ public coordinate getTop() if(!stack.isEmpty() return stack.get(stack.size()-1); else return null; /* * 出栈操作 * */ public coordinate pop() if(!stack.isEmpty() return stack.remove(stack.size()-1); else return null; /* * 产生例题的迷宫矩阵 * */ public void generatemap2() map = new int66; map00 = 0;map01 = 1;map02 = 0;map03 = 0;map04 = 0;map05 = 1; map10 = 0;map11 = 0;map12 = 0;map13 = 1;map14 = 0;map15 = 1; map20 = 1;map21 = 0;map22 = 1;map23 = 0;map24 = 0;map25 = 1; map30 = 0;map31 = 0;map32 = 0;map33 = 1;map34 = 1;map35 = 1; map40 = 0;map41 = 1;map42 = 1;map43 = 0;map44 = 0;map45 = 0; map50 = 0;map51 = 0;map52 = 0;map53 = 0;map54 = 1;map55 = 1; start = new coordinate(0,0); end = new coordinate(4,5); /打印迷宫矩阵 printmap(); public void printmap() if(this.map!=null) for(int i=0;imap.length;i+) for(int j=0;jmap.length;j+) System.out.print(mapij+ ); System.out.println(); /* * 寻路函数 * return true: 存在路径 * return false：不存在路径 * */ public boolean search() /记录遍历情况数组 0 表示未遍历 ，1 表示遍历 int flag = new intmap.lengthmap.length; /栈 this.stack = new ArrayList(); coordinate start = this.start; coordinate end = this.end; stack.add(start); int i=0; /栈非空 while(!stack.isEmpty()&(i0) /上可走且未遍历 if(maptemp.x-1temp.y!=1)&(flagtemp.x-1temp.y=0) /标记已遍历 flagtemp.xtemp.y = 1; /入栈 push(new coordinate(temp.x-1,temp.y); continue; /向右 if(temp.ymap.length-1) /右可走且未遍历 if(maptemp.xtemp.y+1!=1)&(flagtemp.xtemp.y+1=0) flagtemp.xtemp.y = 1; /stack.add(new coordinate(temp.x,temp.y+1); /入栈 push(new coordinate(temp.x,temp.y+1); continue; /向下 if(temp.x0) /左可走且未遍历 if(maptemp.xtemp.y-1!=1)&(flagtemp.xtemp.y-1=0) flagtemp.xtemp.y = 1; /stack.add(new coordinate(temp.x,temp.y-1); /入栈 push(new coordinate(temp.x,temp.y-1); continue; /上下左右都不能走,标记已遍历并移出 flagtemp.xtemp.y = 1; /stack.remove(stack.size()-1); /出栈 pop(); /出入口没有路径 if(stack.size()=0) return false; /找到路径 else return true; /* * 打印路径 * */ public void printPath() if(!stack.isEmpty() for(int i=0;i); System.out.println(+stack.get(stack.size()-1).x+,+stack.get(stack.size()-1).y+); public static void main(String args) Maprinth Maprinth = new Maprinth(); Maprinth.generatemap2(); if(Maprinth.search() /打印路径 Maprinth.printPath(); else System.out.println(无可用路径！); 五、结果及分析输出了这个迷宫和所走的最短路径六、总结与思考通过本次课程设计，我对栈的了解更深了一个层次。栈是一种特殊的线性表，特殊之处在于插入和删除操作的位置受到限制，栈的插入和删除操作只允许在线性表的一端进行，特点是先进后出。允许操作的一端为栈顶，栈中插入元素的操作为入栈，删除元素的操作