数据结构程序设计.doc

课程设计报告 题目： 迷宫问题非递归求解 2010年 5 月 29 日一、需求分析说明任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 二、总体设计（从总体上说明该题目的框架，用文字和图表说明 三、详细设计：一、 需求分析1、本程序实现迷宫的探索过程. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径并输出路径。 2、本演示程序中，输入形式以“回车符”为结束标志，且允许出现重复字符。3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变量。输入的形式以回车结束。4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径二、概要设计为实现上述程序功能，应以栈存储结点。为此，需要定义一个抽象数据类型。1. 抽象数据类型定义为：ADT stack数据对象：D=ai|aiLinkList, i=1,2,.n, n0数据关系：R1=|ai-1,aiD|=2,n ，即当前结点与下一个结点的关系基本操作：stack(); 构造函数，建立一个空栈； 操作结果：通过字符串a构造两个位数不限的长整数。void Push(DataType data);初始条件：已存在栈操作结果：把元素data压入栈顶 DataType Pop();初始条件：已存在栈，且非空操作结果： 栈顶元素出栈，且删除栈顶元素DataType GetPop(); 初始条件：已存在栈，且非空操作结果：获取栈顶元素void Clear(); 初始条件：已存在栈操作结果：把当前的栈清空bool IsEmpty();初始条件：已存在栈操作结果：如果栈为空，则结果为“真”，否则为“假” ADT OrderedList 2.本程序包含三个模块：1)主程序模块：void main() 初始化；do 接受命令； 处理命令；while(“命令”=”退出”)2)、栈模块实现定义的抽象数据类型3)、路径探索模块实现探索迷宫路径 四、 程序代码 /LinkList.h文件/#include#includeusing namespace std;struct DataType /定义描述迷宫中当前位置的结构类型 int x; /x代表当前位置的行坐标 int y; /y代表当前位置的列坐标 int pre; /pre表示移动到下一步的方向;struct Move /定义下一个位置的方向 int x; int y;struct LinkNode /链表结点 DataType data; LinkNode *next;/下面定义栈class stackprivate: LinkNode *top; /指向第一个结点的栈顶指针public: stack(); /构造函数，置空栈 stack(); /析构函数 void Push(DataType data); /把元素data压入栈中 DataType Pop(); /使栈顶元素出栈 DataType GetPop(); /取出栈顶元素 void Clear(); /把栈清空 bool IsEmpty(); /判断栈是否为空，如果为空则返回1，否则返回0;/LinkList.cpp文件/#includeLinkList.hstack:stack() /构造函数，置空栈 top=NULL;stack:stack() /析构函数/* LinkNode *p=top; while(top!=NULL) p=top; top=top-next; / delete p; */ void stack:Push(DataType x) /把元素data压入栈中 LinkNode *TempNode; TempNode=new LinkNode; TempNode-data=x; TempNode-next=top; top=TempNode;DataType stack:Pop() /使栈顶元素出栈 DataType Temp; LinkNode *TempNode; /if(top=NULL) return NULL;/ else/ TempNode=top; top=top-next; Temp=TempNode-data; delete TempNode; return Temp;/ DataType stack:GetPop() /取出栈顶元素 return top-data;void stack:Clear() /把栈清空 top=NULL;bool stack:IsEmpty() /判断栈是否为空，如果为空则返回1，否则返回0 if(top=NULL) return true; else return false; /main.cpp文件/#includeLinkList.hMove 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 Restore(int *maze,int m,int n); /恢复迷宫int* GetMaze(int &m,int &n); /获取迷宫（可从文件中读取，也可输入） /返回存取迷宫的二维指针int main() int m=0,n=0; /定义迷宫的长和宽 int *maze; /定义二维指针存取迷宫 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+; /如果是字符，宽就加1 if(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(); /读取结束 else /Choose=2 ,输入迷宫 coutab; /输入迷宫的长和宽 cout请输入迷宫内容:n; m=a; n=b; /m,n分别代表迷宫的行数和列数 maze=new int *m+2; /申请长度等于行数加2的二级指针 for(i= 0;im+2;i+) /申请每个二维指针的空间 mazei=new intn+2; for(i=1;i=m;i+) /输入迷宫的内容，1代表可通，0代表不通 for(j=1;jmazeij; 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(); /给迷宫的四周加一堵墙，即把迷宫四周定义为1 for(i=0;im+2;i+) mazei0=mazein+1=1; for(i=0;in+2;i+) maze0i=mazem+1i=1; return maze; /返回存贮迷宫的二维指针mazebool Mazepath(int *maze,int m,int n) /寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回false stack q,p; /定义栈p、q,分别存探索迷宫的过程和存储路径 DataType Temp1,Temp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); /将入口位置入栈 p.Push(Temp1); maze11=-1; /标志入口位置已到达过 while(!q.IsEmpty() /栈q非空，则反复探索 Temp2=q.GetPop(); /获取栈顶元素 if(!(p.GetPop().x=q.GetPop().x&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入栈，则把上一个探索的位置存入栈p for(loop=0;loop4;loop+) /探索当前位置的4个相邻位置 x=Temp2.x+moveloop.x; /计算出新位置x位置值 y=Temp2.y+moveloop.y; /计算出新位置y位置值 if(mazexy=0) /判断新位置是否可达 Temp1.x=x; Temp1.y=y; mazexy=-1; /标志新位置已到达过 q.Push(Temp1); /新位置入栈 if(x=(m)&(y=(n) /成功到达出口 Temp1.x=m; Temp1.y=n; Temp1.pre=0; p.Push(Temp1); /把最后一个位置入栈 PrintPath(p); /输出路径 Restore(maze,m,n); /恢复路径 return 1; /表示成功找到路径 if(p.GetPop().x=q.GetPop().x&p.GetPop().y=q.GetPop().y) /如果没有新位置入栈，则返回到上一个位置 p.Pop(); q.Pop(); return 0; /表示查找失败，即迷宫无路经void PrintPath(stack p) /输出路径 cout迷宫的路径为n; coutdata=p.Pop(); /取栈p的顶点元素，即第一个位置 t.Push(temp-data); /第一个位置入栈t delete temp; /释放空间 while(!p.IsEmpty() /栈p非空，则反复转移 temp=new LinkNode; temp-data=p.Pop(); /获取下一个位置 /得到行走方向 a=t.GetPop().x-temp-data.x; /行坐标方向 b=t.GetPop().y-temp-data.y; /列坐标方向 if(a=1) temp-data.pre=1; /方向向下，用1表示 else if(b=1) temp-data.pre=2; /方向向右，用2表示 else if(a=-1) temp-data.pre=3; /方向向上，用3表示 else if(b=-1) temp-data.pre=4; /方向向左，用4表示 t.Push(temp-data); /把新位置入栈 delete temp; /输出路径，包括行坐标，列坐标，下一个位置方向 while(!t.IsEmpty() /栈非空，继续输出 data=t.Pop(); cout(data.x,data.y,data.pre,; /输出行坐标，列坐标 switch(data.pre) /输出相应的方向 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 Restore(int *maze,int m,int n) /恢复迷宫 int i,j; for(i=0;im+2;i+) /遍历指针 for(j=0;jn+2;j+) if(mazeij=-1) /恢复探索过位置，即把-1恢复为0 mazeij=0; 五、程序测试1、由于对迷宫路径探索的算法和二维指针的推敲不足，使程序调试时费时不少2、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性3、本程序模块划分比较合理，且利用指针存储迷宫，操作方便。4