数据结构程序设计课题

-衡阳师范学院工科课程设计 -数据结构课程设计报告题 目：迷宫问题（栈） 学 号：14450139 14450132 姓 名：鲁向阳 肖吟月 班 级：物联网班（1405） 指导教师：王杰老师 日 期： 2016年 6月 目录1概述31.1课程设计目的31.2开发环境31.3任务分配32需求分析42.1题目内容42.2设计思想说明42.3数据结构设计53算法的设计63.1定义坐标（X，Y）:63.2定义方向：63.3定义/链表结点：63.4定义栈：73.5定义迷宫定义移动的4个方向：74各模块的伪码算法84.1根据输入产生一个8*8的迷宫：84.2探索路径函数：114.3输出迷宫145函数的调用关系图176.1自动生成迷宫运行情况187心得体会19参考文献20附 录20欢迎下载1概述1.1 课程设计目的本次课程设计是迷宫求解问题，主要是模拟从入口到出口的通路。程序中的数据采取的是“栈”作为数据的逻辑结构，并且使用链式存储结构，即是实现一个以链表作存储结构的栈类型。本课程设计实现了链栈的建立，入栈，出栈，判断栈是否为空的方法，关键的是迷宫通路路径的“穷举求解”和递归求解的方法。1.2 开发环境具有Intel酷睿i3处理器且满足以下要求的计算机：4GB 内存，500GB 硬盘；安装Visual C+ 6.0。1.3 任务分配两人一起查找相关资料，整合并进行探讨。其中一人通过查找的资料先行拟定文件的大纲，初步定稿后，然后再由另一个人进行进一步加工，细化，最后两人一起核实文件，进行进一步的升华，最终完成该任务。2需求分析2.1 题目内容以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。2.2 设计思想说明计算机解迷宫通常用的是“穷举求解”方法，首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则从入口出发，顺着某个方向进行探索，若能走通，则继续往前进，否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。可以用二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置均可约定有东、南、西、北四个方向可通。要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径，若遇到死路，则将该位置在栈的顶层）弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结束。此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序排列，再把所有坐标顺序排列好后，即可得到正确的迷宫通路。2.3 数据结构设计（1）以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫的四周有一圈障碍。（2）程序输出的结果以三元组（i,j,di）的形式输出，其中：（i,j）指示迷宫中的一个坐标，di表示走到下一坐标的方向，di的取值为0、1、2、3分别表示北、东、南、西。（3）若设定的迷宫存在通路，则以方阵形式将迷宫及其通路输出到标准输出文件上，对于迷宫中的每个方块，有上下左右4个方块相邻，第i行第j列的当前方块的位置记为（i,j）,规定上方方块为方位0，并按顺时针方向递增编号。在试探过程中，假设按从方位0到方位3的顺序查找下一个可走的方块。（4）先将入口进栈（其初始方位设置为-1），在栈不空时循环：取栈顶方块（不退栈），若该方块是出口，则输出栈中所有方块即为路径，否则，找下一个可走的相邻方块，若不存在这样的方块，说明当前路径不可能走通，则回溯。也就是恢复当前方块为0后退栈；若存在这样的方块，则将这个可走的相邻方块进栈（其初始方位设置为-1）。3算法的设计3.1 定义坐标（X，Y）#include#includeusing namespace std;struct Coor int row; int column; int direction; ; 3.2 定义方向struct Move int row;int column;3.3 定义/链表结点struct LinkNode Coor data;LinkNode *next;3.4 定义栈class stackprivate:LinkNode *top; public:stack(); stack(); void Push(Coor data); Coor Pop(); Coor GetPop(); void Clear(); bool IsEmpty(); ;3.5 定义迷宫定义移动的4个方向Move move4=0,1,1,0,0,-1,-1,0;6、几个函数功能的描述: stack(); /构造函数，置空栈 stack(); /析构函数void Push(Coor data); /把元素data压入栈中Coor Pop(); /使栈顶元素出栈Coor GetPop(); /取出栈顶元素void Clear(); /把栈清空bool IsEmpty(); /判断栈是否为空bool Mazepath(int *maze,int m,int n); /寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回falsevoid PrintPath(stack p); /输出迷宫的路径void PrintPath2(int m,int n,stack p,int *maze); /输出路径void Restore(int *maze,int m,int n); /恢复迷4各模块的伪码算法4.1 根据输入产生一个8*8的迷宫m=a; n=b; maze=new int *m+2; /申请长度等于行数加2的二级指针 for(i= 0;im+2;i+) /申请每个二维指针的空间 mazei=new intn+2;for(i=1;i=m;i+) for(j=1;jmazeij;cout是否保存新迷宫？n;coutchoose;if(choose=Y|choose=y)char ch;ofstream fop(Newtest.txt); for(i=1;i=m;i+)for(j=1;j=n;j+)ch=0+mazeij;fopch;fopendl;flush(cout);fop.close(); /给迷宫的四周加一堵墙，即把迷宫四周定义为1for(i=0;im+2;i+) mazei0=mazein+1=1;for(i=0;in+2;i+) maze0i=mazem+1i=1;for(int p=0;pm+2;+p)for(int q=0;q=n+2;+q)if(mazepq=0)cout=1)cout;coutendl;return maze; /返回存贮迷宫的二维指针maze4.2 探索路径函数bool Mazepath(int *maze,int m,int n) /寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回falsestack q,p; /定义栈p、q,分别存探索迷宫的存储和路径过程Coor Temp1,Temp2; int row,column,loop;Temp1.row=1;Temp1.column=1;q.Push(Temp1); /将入口位置入栈p.Push(Temp1);maze11=8; /标志入口位置已到达过while(!q.IsEmpty() /栈q非空，则反复探索Temp2=q.GetPop(); /获取栈顶元素if(!(p.GetPop().row=q.GetPop().row&p.GetPop().column=q.GetPop().column) p.Push(Temp2); /如果有新位置入栈，则把上一个探索的位置存入栈pfor(loop=0;loop4;loop+) /探索当前位置的4个相邻位置row=Temp2.row+moveloop.row; /计算出新位置x位置值column=Temp2.column+moveloop.column; /计算出新位置y位置值if(mazerowcolumn=0) /判断新位置是否可达Temp1.row=row;Temp1.column=column;mazerowcolumn=8; /标志新位置已到达过q.Push(Temp1); /新位置入栈if(row=(m)&(column=(n) /成功到达出口Temp1.row=m;Temp1.column=n;Temp1.direction=0;p.Push(Temp1); /把最后一个位置入栈char choose;coutchoose; if(choose=1) PrintPath(p); /坐标显示输出 Restore(maze,m,n); elsePrintPath2(m,n,p,maze); /矩阵显示输出 Restore(maze,m,n); return 1; /表示成功找到路径if(p.GetPop().row=q.GetPop().row&p.GetPop().column=q.GetPop().column) /如果没有新位置入栈，则返回到上一个位置p.Pop();q.Pop();return 0; /表示查找失败，即迷宫无路经4.3 输出迷宫void PrintPath(stack p) /输出路径cout迷宫的路径为n;coutdata=p.Pop(); /取栈p的顶点元素，即第一个位置t.Push(temp-data); /第一个位置入栈tdelete temp; /释放空间while(!p.IsEmpty() /栈p非空，则反复转移temp=new LinkNode;temp-data=p.Pop(); /获取下一个位置 /得到行走方向a=t.GetPop().row-temp-data.row; /行坐标方向b=t.GetPop().column-temp-data.column; /列坐标方向if(a=1) temp-data.direction=1; /方向向下，用1表示else if(b=1) temp-data.direction=2; /方向向右，用2表示else if(a=-1) temp-data.direction=3; /方向向上，用3表示else if(b=-1) temp-data.direction=4; /方向向左，用4表示t.Push(temp-data); /把新位置入栈delete temp;cout坐标（row,column,direction）中x在指向当前位置所在的行数，y指向当前位置所在的列数，;coutdirection表示下一位置走向。endl; /输出路径，包括行坐标，列坐标，下一个位置方向while(!t.IsEmpty() /栈非空，继续输出data=t.Pop();cout(data.row,data.column,data.direction,; /输出行坐标，列坐标switch(data.direction) /输出相应的方向 case 1:cout)n;break;case 2:cout)n;break;case 3:cout)n;break;case 4:cout)n;break;case 0:cout)n;break;void PrintPath2(int m,int n,stack p,int *maze) /输出路径cout迷宫的路径为n;for (int i = 0; i m+2; +i )for (int j = 0; j n+2; +j)cout mazeij ;cout endl;5函数的调用关系图6 测试结果6.1 自动生成迷宫运行情况(1)选择生成迷宫输入1如下图所示（2）选择以坐标形式输出迷宫：7心得体会通过这段时间的课程设计，本人对计算机的应用，数据结构的作用以及C语言的使用都有了更深的了解。尤其是C语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在设计此程序时，刚开始感到比较迷茫，然后一步步分析，试着写出基本的算法，思路渐渐清晰，最后完成程序。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。在遇到描写迷宫路径的算法时，我感到有些困难，后来经过一步步分析和借鉴书本上的穷举求解的算法，最后把算法写出来。在利用递归方法求路径时花费了我很长时间，由于本人对递归方面的知识运用较少，导致我不熟悉它的用法，但最终还是通过询问同学、查找书本和上网了解关于递归方面的知识写出来了。这次课程设计让我更加深入了解很多方面的知识，如链结构的栈类型及其基本操作，数组的运用等等。在程序的编写中不要一味的模仿，要自己去摸索，只有带着问题反复实践，才能熟练地掌握和运用。在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。参考文献1 严蔚敏、吴伟民：数据结构（C语言版）M，清华大学出版社 2007年版2 谭浩强：C语言设计（第三版）M，清华大学出版社 2005年版3 曹衍龙、林瑞仲、徐慧：C语言实例解析精粹（第二版）M，人民邮电出版社附 录#include#includeusing namespace std;struct Coor /定义描当前位置的结构类型int row; int column; int direction; ;struct Move /定义下一个位置的方向int row;int column;struct LinkNode /链表结点Coor data;LinkNode *next;/定义栈class stackprivate:LinkNode *top; public:stack(); /构造函数，置空栈 stack(); /析构函数void Push(Coor data); /把元素data压入栈中Coor Pop(); /使栈顶元素出栈Coor GetPop(); /取出栈顶元素void Clear(); /把栈清空bool IsEmpty(); /判断栈是否为空;stack:stack() /构造函数，置空栈top=NULL;stack:stack() /析构函数void stack:Push(Coor x) /把元素data压入栈中LinkNode *TempNode;TempNode=new LinkNode;TempNode-data=x;TempNode-next=top;top=TempNode;Coor stack:Pop() /使栈顶元素出栈Coor Temp; LinkNode *TempNode;TempNode=top;top=top-next;Temp=TempNode-data;delete TempNode;return Temp;Coor stack:GetPop() /取出栈顶元素return top-data;void stack:Clear() /把栈清空top=NULL;bool stack:IsEmpty() if(top=NULL) return true;else return false;Move move4=0,1,1,0,0,-1,-1,0; /定义移动的4个方向bool Mazepath(int *maze,int m,int n); /寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回falsevoid PrintPath(stack p); /输出迷宫的路径void PrintPath2(int m,int n,stack p,int *maze); /输出路径void Restore(int *maze,int m,int n); /恢复迷宫int* GetMaze(int &m,int &n); /获取迷宫（可从文件中读取，也可输入） /返回存取迷宫的二维指针int main()system(color f5);int m=0,n=0; int *maze; /定义二维指针存取迷宫cout ntt*欢迎使用迷宫模拟程序* endl;cout tt 14级计算机物联网班 endl;cout tt 鲁向阳 肖吟月 endl;cout tt 学号：14450139 14450132 endl;maze=GetMaze(m,n); /调用GetMaze(int &m,int &n)函数，得到迷宫if(Mazepath(maze,m,n) /调用Mazepath(int *maze,int m,int n)函数获取路径cout迷宫路径探索成功!n;else cout路径不存在!n;return 0;int* GetMaze(int &m,int &n) /获取迷宫（可从文件中读取，也可输入） /返回存取迷宫的二维指针int *maze; int i=0,j=0;char Choose; /定义一个标志，选择读取文件或直接输入，获取迷宫coutChoose; if(Choose=1) /当标志Choose为1时，读取文件cout=0&ch=9) /获取文件中的数字字符j+; /如果是字符，列就加1if(ch=n) i+; /如果是换行，就行加1 n=j; /得到宽，即列数j=0; fip.close(); /读取文件结束m=i; /得到长即行数maze=new int *m+2; /申请长度等于行数加2的二级指针for(i= 0;i=0&ch=9)mazeij=ch-0; /把数字字符转化为数字，并存到指针里coutmazeij ; /在屏幕中显示迷宫j+;if(ch=n) /遇到换行，指针也相应换行coutendl;i+;j=1;fip2.close(); /读取结束coutendl; else /Choose=2 ,输入迷宫 coutab; cout请输入迷宫内容:(0表示通路,1表示不连通。中间用空格键分开)n;m=a; n=b; maze=new int *m+2; /申请长度等于行数加2的二级指针 for(i= 0;im+2;i+) /申请每个二维指针的空间 mazei=new intn+2;for(i=1;i=m;i+) for(j=1;jmazeij;cout是否保存新迷宫？n;coutchoose;if(choose=Y|choose=y)char ch;ofstream fop(Newtest.txt); for(i=1;i=m;i+)for(j=1;j=n;j+)ch=0+mazeij;fopch;fopendl;flush(cout);fop.close(); /给迷宫的四周加一堵墙，即把迷宫四周定义为1for(i=0;im+2;i+) mazei0=mazein+1=1;for(i=0;in+2;i+) maze0i=mazem+1i=1;for(int p=0;pm+2;+p)for(int q=0;q=n+2;+q)if(mazepq=0)cout=1)cout;coutendl;return maze; /返回存贮迷宫的二维指针mazebool Mazepath(int *maze,int m,int n) /寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回falsestack q,p; /定义栈p、q,分别存探索迷宫的存储和路径过程Coor Temp1,Temp2; int row,column,loop;Temp1.row=1;Temp1.column=1;q.Push(Temp1); /将入口位置入栈p.Push(Temp1);maze11=8; /标志入口位置已到达过while(!q.IsEmpty() /栈q非空，则反复探索Temp2=q.GetPop(); /获取栈顶元素if(!(p.GetPop().row=q.GetPop().row&p.GetPop().column=q.GetPop().column) p.Push(Temp2); /如果有新位置入栈，则把上一个探索的位置存入栈pfor(loop=0;loop4;loop+) /探索当前位置的4个相邻位置row=Temp2.row+moveloop.row; /计算出新位置x位置值column=Temp2.column+moveloop.column; /计算出新位置y位置值if(mazerowcolumn=0) /判断新位置是否可达Temp1.row=row;Temp1.column=column;mazerowcolumn=8; /标志新位置已到达过q.Push(Temp1); /新位置入栈if(row=(m)&(column=(n) /成功到达出口Temp1.row=m;Temp1.column=n;Temp1.direction=0;p.Push(Temp1); /把最后一个位置入栈char choose;coutchoose; if(choose=1) PrintPath(p); /坐标显示输出 Restore(maze,m,n); elsePrintPath2(m,n,p,maze); /矩阵显示输出 Restore(maze,m,n); return 1; /表示成功找到路径if(p.GetPop().row=q.GetPop().row&p.GetPop().column=q.GetPop().column) /如果没有新位置入栈，则返回到上一个位置p.Pop();q.Pop();return 0; /表示查找失败，即迷宫无路经void PrintPath(stack p) /输出路径cout迷宫的路径为n;coutdata=p.Pop(); /取栈p的顶点元素，即第一个位置t.Push(temp-dat