资源预览内容
第1页 / 共32页
第2页 / 共32页
第3页 / 共32页
第4页 / 共32页
第5页 / 共32页
第6页 / 共32页
第7页 / 共32页
第8页 / 共32页
第9页 / 共32页
第10页 / 共32页
亲,该文档总共32页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
.天津商业大学数据结构课程设计报告题 目:迷宫问题学 院:信息工程学院专 业:计算机科学与技术班 级:13-01班姓 名:王同组人员:谭 陈指导教师:黄2014年12月26日Word 资料目 录1. 课程设计的内容12. 需求分析13. 概要设计13.1抽象数据类型定义13.2 模块划分14. 详细设计14.1 数据类型的定义14.2 主要模块的算法描述14.3 函数之间的调用关系25. 程序运行说明与测试25.1 用户手册25.2 测试结果及分析26. 课程设计总结2附 录(源程序清单)2Word 资料 .1. 课程设计的内容【问题描述】以一个mn的长方阵表示迷宫,0和1表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条入口到出口的通路,或得出没有通路的结论。【基本要求】首先实现一个栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。如:对于下列数据的迷宫,输出的一条通路为:(1,1,1),(1,2,2),(2,2,2)(3,2,3),(3,1,2)2. 需求分析(1)以二维数组mazeM+2N+2表示迷宫,其中mazei0和mazeiN+1(0=i=N+1)以及maze0j和mazeM+1j(0=j=0数据关系:R1 | a(i-1),aiD,i = 2,3n基本操作: InitStack(&S) 操作结果:构造一个空栈S。DestroyStack(&S) 初始结果:栈S已存在。 操作结果:销毁栈S。ClearStack(&S) 初始结果:栈S已存在。 操作结果:将S清为空栈。StackLength(S) 初始结果:栈S已存在。 操作结果:返回栈S的长度StackEmpty(S) 初始条件:栈S已存在。 操作结果:若S为空栈,则返回TRUE,否则返回FALSEGetTop(S,&e) 初始条件:栈S已存在。 操作结果:若栈S不空,则以e返回栈顶元素e。Push(&S,e) 初始条件:栈S已存在。 操作结果:在栈S的栈顶插入新的栈顶元素。Pop(&S,&e) 初始条件:栈S已存在。 操作结果:删除S的栈顶元素,并以e返回其值。StackTraverse(S,visit() 初始条件:栈S已存在。 操作结果:从栈底到栈顶依次对S中的每个元素调用visit()ADT Stack(2) 设定迷宫的抽象数据类型为:ADT maze 数据对象:D = a(i,j) | a(i,j)0,1,0=i=m+1,0=j=n+1,m,n=10 数据关系:R = M,N M = |a(i-1,j),a(i,j)D,i=1,2,m+1,j=0,1,n+1 N = | a(i,j-1),a(i,j)D,I = 0,1,m+1,j = 1,2,n+1 基本操作: InitMaze(&M,maze,m,n) 初始条件:二维数组mazem+1n+1 已存在,其中自第一行至第m+1行、每行中自第一列至第n+1列的元素已有值,并且以值0表示通路,以值1表示障碍。 操作结果:构成迷宫的字符型数组,以字符0表示通路,以字符1障碍,并在迷宫四周加上一圈障碍。 MazePath(&M)初始条件:迷宫M已被赋值。 操作结果:若迷宫M中存在一条通路,则按如下规定改变迷宫M的状态:以数字0代表可通过,数字1代表不可通过。 3.1 模块划分(1) 主程序模块: void main() int stoMN; struct mark start,end; /start,end入口和出口的坐标 int add42=0,1,1,0,0,-1,-1,0;/行增量和列增量 方向依次为东西南北 initmaze(sto);/建立迷宫 printf(输入入口的横坐标,纵坐标逗号隔开n); scanf(%d,%d,&start.x,&start.y); printf(输入出口的横坐标,纵坐标逗号隔开n); scanf(%d,%d,&end.x,&end.y); MazePath(start,end,sto,add); /find path system(PAUSE); (2) 栈模块实现栈抽象数据类型;(3) 迷宫模块实现迷宫抽象数据类型,建立迷宫,求解迷宫的一条路径。4. 详细设计4.1 数据类型的定义(1) 坐标位置,类型:struct mark /定义迷宫内点的坐标类型 int x; int y; ;(2) 迷宫类型void initmaze(int mazeMN) /按照用户输入的M行和N列的二维数组(元素值为0或1)/设置迷宫maze的初值,包括加上边缘一圈的值void MazePath(struct mark start,struct mark end,int mazeMN,int diradd42)/求解迷宫maze中从入口Start到出口end的一条路径/若存在,则返回TRUE,否则返回FALSE(3) 栈类型struct Element int x,y; /x行,y列 int d; /d下一步的方向 ; typedef struct LStack /链栈 Element elem; struct LStack *next; *PLStack;4.2 主要模块的算法描述(1) 求迷宫路径的伪码算法void MazePath(struct mark start,struct mark end,int mazeMN,int diradd42) int i,j,d;int a,b; Element elem,e; PLStack S1, S2; InitStack(S1); InitStack(S2); mazestart.xstart.y=2; /入口点作上标记 elem.x=start.x; elem.y=start.y; elem.d=-1; /开始为-1 Push(S1,elem); while(!StackEmpty(S1) /栈不为空 有路径可走 Pop(S1,elem); i=elem.x; j=elem.y; d=elem.d+1; /下一个方向 while(d(%d,%d,%d),e.x,e.y,e.d); return; /跳出两层循环,本来用break,但发现出错,exit又会结束程序,选用return还是不错滴o(_)o. if(mazeab=0) /找到可以前进的非出口的点 mazeab=2; /标记走过此点 elem.x=i; elem.y=j; elem.d=d; Push(S1,elem); /当前位置入栈 i=a; /下一点转化为当前点 j=b; d=-1; d+; printf(没有找到可以走出此迷宫的路径n); (2) 建立迷宫的伪码算法void initmaze(int mazeMN) int i,j; int m,n; /迷宫行,列 printf(请输入迷宫的行数 m=); scanf(%d,&m); printf(请输入迷宫的列数 n=); scanf(%d,&n); printf(n请输入迷宫的各行各列:n用空格隔开,0代表路,1代表墙n,m,n); for(i=1;i=m;i+) for(j=1;j=n;j+)mazeij = (int) (rand() % 2); /scanf(%d,&mazeij); printf(你建立的迷宫为o(_)o.n); for(i=0;i=m+1;i+) /加一圈围墙 mazei0=1; mazein+1=1; for(j=0;j=n+1;j+) maze0j=1; mazem+1j=1; for(i=0;i=m+1;i+) /输出迷宫 for(j=0;j=n+1;j+) printf(%d ,mazeij); printf(n); (3) 主函数的伪码算法:void main() int stoMN; struct mark start,end; /start,end入口和出口的坐标 int add42
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号