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

A□B□C□A□B□C□实验难度:学期： 2017秋季学期任课教师: 实验题目: 组员及组长： 承担工作：联系电话：电子邮件： 完成提交时间： 年月日一、 【实验构思（Conceive）】（10%）（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）首先输入迷宫数据，在计算机的屏幕上显示一个8行8列的矩阵表示迷宫。矩阵中的每个数据或为通路（以0表示），或为墙（以1表示），所求路径必须是简单路径，即在求得的路径上不能重复出现同一道块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作为“当前位置入栈”；从当前路径删除前一通道块的操作为“出栈”。若找到出口，则从栈中弹出数据，在屏幕上显示从入口到出口的路径坐标。二、 【实验设计（Design）】（20%）（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）1、 定义坐标（X，Y）:structCoor{introw;intcolumn;intdirection;}；2、 定义方向：structMove{introw;intcolumn;};3、 定义/链表结点：structLinkNode{Coordata;LinkNode*next;};4、 定义栈：classstack{private:LinkNode*top;public:stack();~stack();voidPush(Coordata);CoorPop();CoorGetPop();voidClear();boolIsEmpty();};流程图：三、【实现(Implement)】(30%)(本部分应包括：抽象数据类型各操作的具体实现代码、关键操作的具体算法实现、函数实现，主程序实现等，并给出关键算法的时间复杂度分析。如有界面则需包括界面的关键实现方法等。)定义迷宫定义移动的4个方向：Movemove[4]={{0,1},{1,0},{0,-1},{-1,0}};几个函数功能的描述：stack(); 〃构造函数，置空栈~stack(); 〃析构函数voidPush(Coordata); 〃把元素data压入栈中CoorPop(); 〃使栈顶元素出栈CoorGetPop(); 〃取出栈顶元素voidClear(); 〃把栈清空boolIsEmpty(); 〃判断栈是否为空boolMazepath(int**maze,intm,intn);〃寻找迷宫maze中从(0,0)到(m,n)的路径〃到则返回true,否则返回falsevoidPrintPath(stackp); 〃输出迷宫的路径voidPrintPath2(intm,intn,stackp,int**maze); 〃输出路径voidRestore(int**maze,intm,intn); 〃恢复迷宫主函数实现：intmain(){system("colorf5”);intm=0,n=0;int**maze; 〃定义二维指针存取迷宫cout<<"**************欢迎使用迷宫游戏模拟程序*************"<<endl;cout<<"* 软件工程 *"<<endl;cout<<"* 孙越 *"<<endl;cout<<"* 20161120232 *"<<endl;cout<<"***************************************************"<<endl;maze=GetMaze(m,n);〃调用GetMaze函数，得到迷宫if(Mazepath(maze,m,n))〃调用Mazepath函数获取路径cout<<"迷宫路径探索成功!\n”;elsecout<<"路径不存在!\n”;return0;}复杂度分析：空间复杂度：O(1)；时间复杂度：随机生成迷宫：O(n*n)；探寻出口：O(n*n)；输出迷宫：O(n*n)；判断当前位置可通：O(1)。四、【测试结果(Testing)】(10%)(本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析，可附截图）选择以坐标形式输出迷宫：输出如下图所示:111—1A-111—111oo111—1*Tr111111(row111—1A-111—111oo111—1*Tr111111(row，column,direction)输出迷宫选⑴或以方阵形式输出迷宫选⑵：2111111Processreturned0(0x0)Pressanykeytocontinue.executiontime:31.399sTOC\o"1-5"\h\zE DE\codeblock\c++_code\j^^^^-副本.exe — □X孙越 ■'ID:\IDE\codeblock\c++_code睫宫游戏-副本■'ID:\IDE\codeblock\c++_code睫宫游戏-副本.exe**************欢迎使用迷宫游戏模拟程序*************软件I：程 *孙越 * 20161120232 %兽瞽艾露常搭瓮苛MS*徉荷露露箱篇苻我*******请输入迷宫内容：(0表示通路,1表示不连通。中间用空格键分并)00110020161120232 *案富艾装畚带霜S履其？需福蜀苔福琴箱：*?001001请输入迷宫内容：(0表示通路,1表示不连通。中间用空格键分开)001100001100□□□□□■□■■□□□□■■□□□□□□□□■请选择以坐标形式(row,column,direction)输出迷宫选⑴或以方阵形式输出迷宫选⑵：1迷唐的路径为括号内的内容分别表示为(行坐标,列坐标，数字化方向，方向)坐标(row,column,direction)中x在朋向当前位置所在的彳「数，y指向当前位置所在的列数，direction表小下一位置走向。(1,1,2,-)(1,2,1,I)(2,2,1,I)(3,2,1,I)(4,2,2,-)(4,3,0,)迷宫路径探索成功！Processreturned0(0x0)executiontime:42.504sPressanykeytocontinue.选择以方阵形式输出迷宫：输出如下图所示(其中8代表路径，1代表墙)迷宫不存在，路径探索失败:D:\IDE\ccdeblock\c++_cod已谜宫游戏-副本exe**************欢迎使用迷宫游戏模拟程序*************软件i:食 *孙越 *% 20161120232 %L"Ju"JL"JJJu"Jfc"JJJfcjUfc'2JJ】夕u"J JJJfa"Jh"JL"Ju"JJu"J"JJL"JJJJJfc"JL-^JJfa"JliAdJJrji「£,r[r*,r£r*■r£rr|ir£rrjir£rr-Ji「■；，r*J'ir[rr£rr£rr£rr£rrjir£rrji「£■rji「£■rjir£rr£r「：■r£rr£rrjir£rrji「£，rjir£rr[r*■r£rr£rr£rr|ir£rrjir£rrjil；，r]，请输入迷宫的行数和列数：(中间用纪格键分.开)43.……□□□□□■□□□□□■路径不存花!Processreturned0(0x0)executiontime:14.860sPressanykeytocontinue.五、【实验总结】(10%)(本部分应包括：自己在实验中完成的任务，及存在的问题，所完成实验过程中的具体经验总结、心得)通过该题目的设计过程，我加深了对栈的逻辑结构，存储结构及入栈出栈过程的理解，对栈的基本运算的实现有所掌握，对课本中所学的各种数据结构进一步理解和掌握，学会了如何把学到的知识用于解决实际问题，锻炼了自己动手的能力。但是程序依旧还存在一些问题，比如开始的时候，调试过程中 自己定义不可通取值从ch>='0'&&ch〈='9'都可以执行，但是在执行过程中显示迷宫时有“吃墙”现象，有一部分“墙”出现缺失。经过反复调试程序，最后发现在定义if(maze[p][q]==1)cout<<"□"；出错，后来改为if(maze[p][q]>=1)cout<<"□"；后，吃图现象再没有发生。但是处理了这个问题后还是会在显示迷宫模块的时候有一些迷宫方格，但经过多次调试后还是没能解决。六、 思考题或【项目运作描述（Operate）】（10%）（注：选择C难度的才需要填写“项目运作描述”，其他难度的只需完成思考题）（项目运作描述应包括：项目的成本效益分析，应用效果等的分析。）接到实验项目后，其实第一个想法是看实验指导书，看了实验指导书之后知道了要设计该程序大概需要什么模块函数，然后根据这些模块一个个做出分析。跟据实现提示，计算机解迷宫通常用的是“穷举求解”方法，即从人口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。用二维数组指针存储迷宫数据，通常设定人口点的下标为（1，1），出口点的下标为（n，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。主要操作如下：1、 生成迷宫：根据提示输入数据，然后生成一个8行8列的迷宫。2、 探索迷宫路径：由输入的入口位置开始，对相邻的（上，下，左，右）四个方向的方块进行探索，若可通则“纳入路径''，否则顺着“来向”退到“前一通道块”，朝着“来向”之外的其它方向继续探索。3、 保存迷宫路径：若探索到出口则把探索到的路径压入另一个栈中，并最后弹出路径坐标，输出在屏幕上。将一个个函数完善后，最重要的就处理函数接口，怎样使各个子模块实施其的详细功能是一个很重要的问题，只有解决了这个问题才能充分调用这些函数，让主程序能够有效调用这些函数。其中最主要的函数就是获取迷宫的二维指针函数和寻找迷宫路径函数，需要弄清楚二维数组指针的操作。最后就是在main（）函数中调用这些函数，画了一个函数调用的流程图，根据流程图调用函数，即可实现迷宫问题的操作。七、 【代码】（10%）（本部分应包括：完整的代码及充分的注释。注意纸质的实验报告无需包括此部分。格式统一为，字体：Georgia,行距：固定行距12，字号：小五#include<iostream>#include<fstream>#include<stdlib.h>#definetrue1#definefalse0usingnamespacestd;structCoor{introw;intcolumn;intdirection;};〃定义描当前位置的结构类型structMove{introw;intcolumn;};〃定义下一个位置的方向structLinkNode{Coordata;LinkNode*next;};〃链表结点〃定义栈〃定义栈classstack{private:LinkNode*top;public:stack();~stack();voidPush(Coordata);CoorPop();CoorGetPop();voidClear();intIsEmpty();};〃构造函数，置空栈〃析构函数〃把元素data压入栈中〃使栈顶元素出栈〃取出栈顶元素〃把栈清空〃判断栈是否为空〃构造函数，置空栈stack::stack()〃构造函数，置空栈{top=NULL;}stack::~stack(){〃析构函数voidstack::Push(Coorx)//把元素data压入栈中{LinkNode*TempNode;TempNode=newLinkNode;TempNode->data=x;TempNode->next=top;top=TempNode;}Coorstack::Pop() 〃使栈顶元素出栈{CoorTemp;LinkNode*TempNode;TempNode=top;top=top->next;Temp=TempNode->data;deleteTempNode;returnTemp;}Coorstack::GetPop() 〃取出栈顶元素{returntop->data;}voidstack::Clear() 〃清空栈{top=NULL;}intstack::IsEmpty() 〃判断是否空栈{if(top==NULL)returntrue;elsereturnfalse;}Movemove[4]={{0,1},{1,0},{0,-1},{-1,0}}; 〃定义移动的4个方向intMazepath(int**maze,intm,intn); 〃寻找迷宫maze中从(0，0)至U(m,n)的路径，找到则返回true,否则返回falsevoidPrintPath(stackp); 〃输出迷宫的路径voidPrintPath2(intm,intn,stackp,int**maze);〃输出路径voidRestore(int**maze,intm,intn); 〃恢复迷宫int**GetMaze(int&m,int&n); 〃获取迷宫〃返回存取迷宫的二维指针intmain(){system("colorf5");intm=0,n=0;int**maze; //定义二维指针存取迷宫cout<<"**************欢迎使用迷宫游戏模拟程序*************"<<endl;cout<<"* 软件工程 *"<<endl;cout<<"* 孙越 *"<<endl;cout<<"* 20161120232 *"<<endl;cout<<"***************************************************"<<endl;maze=GetMaze(m,n); 〃调用GetMaze函数，得到迷宫if(Mazepath(maze,m,n))〃调用Mazepath函数获取路径cout<<"迷宫路径探索成功!\n”;elsecout<<"路径不存在!\n”;return0;}int**GetMaze(int&m,int&n)//获取迷宫{ 〃返回存取迷宫的二维指针int**maze;inti=0,j=0;cout<<"请输入迷宫的行数和列数:(中间用空格键分开)"；inta,b;cin>>a>>b;cout<<"请输入迷宫内容:(0表示通路,1表示不连通。中间用空格键分开)\n”;m=a;n=b;maze=newint*[m+2];//申请长度等于行数加2的二级指针for(i=0;i<m+2;i++) //申请每个二维指针的空间{maze[i]=newint[n+2];}for(i=1;i<=m;i++)for(j=1;j<=n;j++)cin>>maze[i][j];〃给迷宫的四周加一堵墙，即把迷宫四周定义为1for(i=0;i<m+2;i++)maze[i][0]=maze[i][n+1]=1;for(i=0;i<n+2;i++)maze[0][i]=maze[m+1][i]=1;for(intp=0;p<m+2;++p){for(intq=0;q<=n+2;++q){if(maze[p][q]==0)cout<<”・”；if(maze[p][q]>=1)cout<<”口”；}cout<<endl;}returnmaze;//返回存贮迷宫的二维指针maze}intMazepath(int**maze,intm,intn)//寻找迷宫maze中从(0，0)^U(m,n)的路径，找到则返回true，否则返回false{stackq,p; 〃定义栈p、q,分别存探索迷宫的存储和路径过程CoorTemp1,Temp2;introw,column,loop;Tempi.row=i;introw,column,loop;Tempi.row=i;Tempi.column=i;q.Push(Tempi);p.Push(Tempi);maze[i][i]=8;while(!q.IsEmpty()){Temp2=q.GetPop();〃将入口位置入栈〃标志入口位置巳到达过〃栈q非空，则反复探索〃获取栈顶元素if(!(p.GetPop().row==q.GetPop().row&&p.GetPop().column==q.GetPop().column))p.Push(Temp2); 〃如果有新位置入栈，则把上一个探索的位置存入栈pfor(loop=0;loop<4;loop++) 〃探索当前位置的4个相邻位置row=Temp2.row+move[loop].row; 〃计算出新位置x位置值column=Temp2.column+move[loop].column;〃计算出新位置y位置值〃判断新位置是否可达〃标志新位置巳到达过〃判断新位置是否可达〃标志新位置巳到达过〃新位置入栈〃成功到达出口{Tempi.row=row;Tempi.column=column;maze[row][column]=8;q.Push(Tempi);}if((row==(m))&&(column==(n))){Tempi.row=m;Tempi.column=n;Tempi.direction=0;p.Push(Tempi); 〃把最后一个位置入栈charchoose;cout<<"请选择以坐标形式(row，column，direction)输出迷宫选(i)或以方阵形式输出迷宫选(2):”;cin>>choose;if(choose=='i'){PrintPath(p); 〃坐标显示输出Restore(maze,m,n);}else{PrintPath2(m,n,p,maze); 〃矩阵显示输出Restore(maze,m,n);}returni; 〃表示成功找到路径}}if(p.GetPop().row==q.GetPop().row&&p.GetPop().column==q.GetPop().column)〃如果没有新位置入栈，则返回到上一个位置{p. Pop();q. Pop();}}return0; 〃表示查找失败，即迷宫无路经voidPrintPath(stackp)〃输出路径{cout<<"迷宫的路径为\n”;cout<<"括号内的内容分别表示为(行坐标,列坐标，数字化方向，方向)\n";stackt; 〃定义一个栈，按从入口到出口存取路径inta,b;Coordata;LinkNode*temp;temp=newLinkNode;//申请空间temp->data=p.Pop();〃取栈p的顶点元素，即第一个位置t.Push(temp->data);〃第一个位置入栈tdeletetemp; //释放空间while(!p.IsEmpty())〃栈p非空，则反复转移{temp=newLinkNode;temp->data=p.Pop(); 〃获取下一个位置〃得到行走方向a=t.GetPop().row-temp->data.row;//行坐标方向b=t.GetPop().column-temp->data.column;//列坐标方向if(a==i)