数据结构c语言课程设计报告

扬州职业大学1数据结构课程设计报告设计题目：迷宫求解专业机电一体化班级08专接本学生学号104910252011指导教师高在村完成时间2011.5扬州职业大学2目录一.实验内容............................3二.需求分析............................3三．总体设计...........................3四．详细设计...........................5五．代码...............................9六.测试...............................14七.总结..............................16参考文献..............................17扬州职业大学3一.实验内容任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：界面友好，函数功能要划分好；总体设计应画一流程图；程序要加必要的注释；要提供程序设计方案；程序一定要经得起测试；宁可功能少一点，也要能运行起来，不能运行的程序是没有价值的。二.需求分析1.可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：使用非递归算法。2.用户可以根据自己的需求进行输入所需的迷宫，其中1表示迷宫的墙壁，0表示迷宫的通路，从而建立自己的迷宫；3.用户还可以自己设计迷宫的入口坐标，当然也可以设计出口了；4.程序执行的命令包括：（1）构造栈Stack,T描述迷宫中当前位置的结构类型,LinkNode链表结点三个类,其中Stack是Linknode的友元类.（2）构造存取迷宫的二维指针GetMaze(int&m,int&n)（3）恢复迷宫Restore(int**maze,intm,intn)（4）在迷宫中寻找一条通路Mazepath(int**maze,intm,intn)（5）输出所找到的通路PrintPath()(6)定义当前位置移动的4个方向move数组.三．总体设计㈠存储结构：扬州职业大学4首先用二维指针存储迷宫数据，迷宫数据由用户输入。一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。1．从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。经过的位置把0变为-1，带输出迷宫路径后在恢复迷宫院士为止2.本程序有三个模块：⑴主程序模块⑵三个类模块即其对象：实现栈链表抽象数据类型；⑶迷宫二维指针单元模块：存储迷宫,,寻路径,输出迷宫,恢复迷宫。(二)流程图扬州职业大学5四．详细设计(一).基本算法：存取迷宫GetMaze(int&m,int&n)求取一条路径MazePath（）if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)输入迷宫的长和宽内容显示结果Printpath（）迷宫无路经END数组move用于更改方向,函数Push,PrintPath,Restore调用函数GetPop,Push,Pop恢复迷宫Restore()调用扬州职业大学6首先用二维指针存储迷宫数据，迷宫数据由用户输入。一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、南、西、北4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宫的外墙；第1行第1列元素和第m行第m列元素置成“0”，表示迷宫的入口和出口；其余元素值用GetMaze函数获取.假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有4。如果用二维数组move记录4方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用move数组确定：x=x+move[loop][0]y=y+move[loop][1]从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。定义一个栈，按从入口到出口存取路径.在搜索过程中，每前进一步，如果有新位置入栈，则把上一个探索的位置存入栈中,当前位置”-1”（表示这个位置在通路上），并将该位置的坐标压入栈中。如果没有新位置入栈，则返回到上一个位置.到达出口后,最后一个位置入栈,输出路径,并回复路径.把-1变为0.总之,入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。扬州职业大学7(二).为实现算法，需要类的象数据类型：类及其对象:类Stack对象成员如下:Stack();构造函数，置空栈操作结果：构造一个空的栈S。Stack();析构函数voidPush(Te);把元素data压入栈中TPop();使栈顶元素出栈TGetPop();取出栈顶元素voidClear();把栈清空boolempty();判断栈是否为空，如果为空则返回1，否则返回0T类迷宫中当前位置的结构类型:T对象成员如下:x;x代表当前位置的行坐标y;y代表当前位置的列坐标dir;0:无效,1:东,2:南,3:西,4:北LinkNode类链表结点:对象成员如下:友元类StackTdataLinkNode*next(三).函数调用关系mainGetMazeMazepathEmpy()GetPop()Push()PrintPath()Restore()扬州职业大学8Pop()GetPop()Push()(四)算法的时间、空间复杂度1）本算法在空间上主要开辟了一个二维指针，规模都是迷宫(m+2)*(n+2)，一个是栈，一个是迷宫路径记录，输出时候调用栈，在恢复迷宫。2）在时间上为简单的链表栈的存储结构，二维指针GetMaze,Restore两函数算法时间复杂度为O（(m+2)*(n+2)）,Mazepath,PrintPath为O(1),（m为行数，n为列数）。(五)UML图T+X:int+y:int+dir:int扬州职业大学9五．代码/*以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1），（1,2,2），（2,2,2），（3,2,3），（3,1,2），…。*/#includeiostreamusingnamespacestd;classT//定义描述迷宫中当前位置的结构类型{public:intx;//x代表当前位置的行坐标inty;//y代表当前位置的列坐标LinkNode+TdataStack+push(Te):void+TGetpop():void+Tpop()+empty():bool+Stack()+~Stack()+Clear():void+nextLinkNodeLinkNode-topfriend扬州职业大学10intdir;//0:无效,1:东,2:南,3:西,4:北};classLinkNode//链表结点{friendclassStack;public:Tdata;LinkNode*next;};classStack{private:LinkNode*top;//指向第一个结点的栈顶指针public:Stack();//构造函数，置空栈~Stack();//析构函数voidPush(Te);//把元素data压入栈中TPop();//使栈顶元素出栈TGetPop();//取出栈顶元素voidClear();//把栈清空boolempty();//判断栈是否为空，如果为空则返回1，否则返回0};Stack::Stack()//构造函数，置空栈{top=NULL;}Stack::~Stack()//析构函数{}voidStack::Push(Te)//把元素x压入栈中{LinkNode*P;P=newLinkNode;P-data=e;P-next=top;top=P;}TStack::Pop()//使栈顶元素出栈{TTemp;LinkNode*P;P=top;top=top-next;Temp=P-data;扬州职业大学11deleteP;returnTemp;}TStack::GetPop()//取出栈顶元素{returntop-data;}voidStack::Clear()//把栈清空{top=NULL;}boolStack::empty()//判断栈是否为空，如果为空则返回1，否则返回0{if(top==NULL)return1;elsereturn0;}intmove[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//定义当前位置移动的4个方向boolMazepath(int**maze,intm,intn);//寻找迷宫maze中从（0，0）到（m,n）的路径//到则返回true,否则返回falsevoidPrintPath(Stackp);//输出迷宫的路径voidRestore(int**maze,intm,intn);//恢复迷宫int**GetMaze(int&m,int&n);//获取迷宫//返回存取迷宫的二维指针intmain(){intm=0,n=0;//定义迷宫的长和宽int**maze;//定义二维指针存取迷宫maze=GetMaze(m,n);//调用GetMaze(int&m,int&n)函数，得到迷宫if(Mazepath(maze,m,n))//调用Mazepath(int**maze,intm,intn)函数获取路径cout迷宫路径探索成功!\n;elsecout路径不存在!\n;return0;}int**GetMaze(int&m,int&n)//返回存取迷宫的二维指针{int**maze;//定义二维指针存取迷宫inti=0,j=0;cout请输入迷宫的长和宽:;inta,b;cinab;//输入迷宫的长和宽cout请输入迷宫内容:\n;m=a;n=b;//m,n分别代表迷宫的行数和列数扬州职业大学12maze=newint*[m+2];//申请长度等于行