云南大学软件学院数据结构实验4

实验难度ABC序号学号姓名成绩指导教师（签名）学期2017秋季学期任课教师实验题目组员及组长承担工作联系电话电子邮件完成提交时间年月日云南大学软件学院数据结构实验报告一、【实验构思（CONCEIVE）】10（本部分应包括描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）首先输入迷宫数据，在计算机的屏幕上显示一个8行8列的矩阵表示迷宫。矩阵中的每个数据或为通路（以0表示），或为墙（以1表示），所求路径必须是简单路径，即在求得的路径上不能重复出现同一道块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作为“当前位置入栈”；从当前路径删除前一通道块的操作为“出栈”。若找到出口，则从栈中弹出数据，在屏幕上显示从入口到出口的路径坐标。二、【实验设计DESIGN】20（本部分应包括抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）1、定义坐标（X，Y）STRUCTCOORINTROWINTCOLUMNINTDIRECTION2、定义方向STRUCTMOVEINTROWINTCOLUMN3、定义/链表结点STRUCTLINKNODECOORDATALINKNODENEXT4、定义栈CLASSSTACKPRIVATELINKNODETOPPUBLICSTACKSTACKVOIDPUSHCOORDATACOORPOPCOORGETPOPVOIDCLEARBOOLISEMPTY5流程图三、【实现（IMPLEMENT）】30（本部分应包括抽象数据类型各操作的具体实现代码、关键操作的具体算法实现、函数实现，主程序实现等，并给出关键算法的时间复杂度分析。如有界面则需包括界面的关键实现方法等。）1定义迷宫定义移动的4个方向MOVEMOVE40,1,1,0,0,1,1,02几个函数功能的描述STACK/构造函数，置空栈STACK/析构函数VOIDPUSHCOORDATA/把元素DATA压入栈中COORPOP/使栈顶元素出栈COORGETPOP/取出栈顶元素VOIDCLEAR/把栈清空BOOLISEMPTY/判断栈是否为空BOOLMAZEPATHINTMAZE,INTM,INTN/寻找迷宫MAZE中从（0，0）到（M,N）的路径/到则返回TRUE,否则返回FALSEVOIDPRINTPATHSTACKP/输出迷宫的路径VOIDPRINTPATH2INTM,INTN,STACKP,INTMAZE/输出路径VOIDRESTOREINTMAZE,INTM,INTN/恢复迷宫3主函数实现INTMAINSYSTEM“COLORF5“INTM0,N0INTMAZE/定义二维指针存取迷宫COUT0STRUCTCOOR/定义描当前位置的结构类型INTROWINTCOLUMNINTDIRECTIONSTRUCTMOVE/定义下一个位置的方向INTROWINTCOLUMNSTRUCTLINKNODE/链表结点COORDATALINKNODENEXTCLASSSTACK/定义栈PRIVATELINKNODETOPPUBLICSTACK/构造函数，置空栈STACK/析构函数VOIDPUSHCOORDATA/把元素DATA压入栈中COORPOP/使栈顶元素出栈COORGETPOP/取出栈顶元素VOIDCLEAR/把栈清空INTISEMPTY/判断栈是否为空STACKSTACK/构造函数，置空栈TOPNULLSTACKSTACK/析构函数VOIDSTACKPUSHCOORX/把元素DATA压入栈中LINKNODETEMPNODETEMPNODENEWLINKNODETEMPNODEDATAXTEMPNODENEXTTOPTOPTEMPNODECOORSTACKPOP/使栈顶元素出栈COORTEMPLINKNODETEMPNODETEMPNODETOPTOPTOPNEXTTEMPTEMPNODEDATADELETETEMPNODERETURNTEMPCOORSTACKGETPOP/取出栈顶元素RETURNTOPDATAVOIDSTACKCLEAR/清空栈TOPNULLINTSTACKISEMPTY/判断是否空栈IFTOPNULLRETURNTRUEELSERETURNFALSEMOVEMOVE40,1,1,0,0,1,1,0/定义移动的4个方向INTMAZEPATHINTMAZE,INTM,INTN/寻找迷宫MAZE中从（0，0）到（M,N）的路径，找到则返回TRUE,否则返回FALSEVOIDPRINTPATHSTACKP/输出迷宫的路径VOIDPRINTPATH2INTM,INTN,STACKP,INTMAZE/输出路径VOIDRESTOREINTMAZE,INTM,INTN/恢复迷宫INTGETMAZEINT/获取迷宫/返回存取迷宫的二维指针INTMAINSYSTEM“COLORF5“INTM0,N0INTMAZE/定义二维指针存取迷宫COUTABCOUTMAZEIJ/给迷宫的四周加一堵墙，即把迷宫四周定义为1FORI0I1COUTCHOOSEIFCHOOSE1PRINTPATHP/坐标显示输出RESTOREMAZE,M,NELSEPRINTPATH2M,N,P,MAZE/矩阵显示输出RESTOREMAZE,M,NRETURN1/表示成功找到路径IFPGETPOPROWQGETPOPROWQPOPRETURN0/表示查找失败，即迷宫无路经VOIDPRINTPATHSTACKP/输出路径COUTDATAPPOP/取栈P的顶点元素，即第一个位置TPUSHTEMPDATA/第一个位置入栈TDELETETEMP/释放空间WHILEPISEMPTY/栈P非空，则反复转移TEMPNEWLINKNODETEMPDATAPPOP/获取下一个位置/得到行走方向ATGETPOPROWTEMPDATAROW/行坐标方向BTGETPOPCOLUMNTEMPDATACOLUMN/列坐标方向IFA1TEMPDATADIRECTION1/方向向下，用1表示ELSEIFB1TEMPDATADIRECTION2/方向向右，用2表示ELSEIFA1TEMPDATADIRECTION3/方向向上，用3表示ELSEIFB1TEMPDATADIRECTION4/方向向左，用4表示TPUSHTEMPDATA/把新位置入栈DELETETEMPCOUT“坐标（ROW,COLUMN,DIRECTION）中X在指向当前位置所在的行数，Y指向当前位置所在的列数，“COUT“DIRECTION表示下一位置走向。“ENDL/输出路径，包括行坐标，列坐标，下一个位置方向WHILETISEMPTY/栈非空，继续输出DATATPOPCOUTDATAROW,DATACOLUMN,DATADIRECTION“,“/输出行坐标，列坐标SWITCHDATADIRECTION/输出相应的方向CASE1COUT“N“BREAKCASE2COUT“N“BREAKCASE3COUT“N“BREAKCASE4COUT“N“BREAKCASE0COUT“N“BREAKVOIDPRINTPATH2INTM,INTN,STACKP,IN