课程设计演示 编制一个求解迷宫通路的程序

1、数据结构课程设计 -编制一个求解迷宫通路的程序模块设计本程序除主函数模块外总计5个模块:栈模块-实现栈抽象数据类型迷宫模块-实现迷宫抽象数据类型迷宫随机地图生成模块-用户自定义迷宫地图的生成菜单模块-实现与用户交互菜单游戏模块-实现游戏功能负责实现其中的: 迷宫随机地图生成模块,菜单模块,游戏模块.模块设计模块设计随机地图生成模块算法设计:平面图的任意生成树,使用随机DFS.算法思路:算法通过 n * m 矩阵的每一个点 映射到矩阵 ( 2*n+3 ) * ( 2*m+3 ) 的点上,通过DFS对的对应点进行遍历,使之形成通路.算法分析:用这个算法，生成的迷宫的特点是，分支不多，但往往很深，难

2、度较大.算法最好情况下时间复杂度为:O(n+m),最坏情况下时间复杂度为:O(n*m),平均时间复杂度为: O(n*m)随机地图生成模块假设用户输入 n = 3,m = 3:123112324563789012345678000000000010000000002001002003000300000000040040050060005000000000600700800900070000000008000000000则点则点的映射的映射如图所示如图所示: - - .随机地图生成模块迷宫生成算法迷宫生成算法:void Make_Maze(int mapMAZE_MAX+2MAZE_MAX+2,i

3、nt x,int y) int z1,z2; for(z1=0,z2=2*y+2;z1=2*x+2;z1+)mapz10=1,mapz1z2=1; for(z1=0,z2=2*x+2;z1=2*y+2;z1+)map0z1=1,mapz2z1=1; srand(unsigned)time(NULL); search(map,rand()%x+1,rand()%y+1);map12=1;map2*x+12*y=1;随机地图生成模块 - :12311232456378901234567801111111111100000001210100200300131000000014104005006001

4、5100000001610700800900171000000018111111111for( i=0,j=2*m+2; i=2*n+2; i+ ) mapi0=1,mapij=1;for( i=0,j=2*n+2; i=2*m+2; i+ ) map0i=1,mapji=1;随机地图生成模块 - :123112324563789012345678011111111111000000012101002003001310000000141040050060015100000001610700800900171000000018111111111srand(unsigned)time(NULL);

5、search(map, rand()%n+1, rand()%m+1); -开始迷宫地图的DFS生成假设假设: rand()%n = 2,rand()%m = 2 那么那么: rand()%n + 1 = 3,rand()%m + 1 = 3 search(map,3,3);随机地图生成模块使用使用 DFS 递归生成迷宫递归生成迷宫:int search(int mapMAZE_MAX+2MAZE_MAX+2,int x,int y) static int d42=0,1,1,0,0,-1,-1,0; int zx=x*2,zy=y*2,next,turn,i; mapzxzy=1;turn

6、= rand()%2 ? 1 : 3; for(i=0,next=rand()%4; i4; i+,next=(next+turn)%4) if(mapzx+2*dnext0 zy+2*dnext1=0 ) mapzx+dnext0zy+dnext1=1;search(map,x+dnext0,y+dnext1); return 0;随机地图生成模块 - :123112324563789012345678011111111111000000012101002003001310000000141040050060015100000001610700800900171000000018111111

7、111search(map,3,3);static int d42=0,1, / 1,0,/ 0,-1,/ -1,0;/ int zx=x*2,zy=y*2,next,turn,i;随机地图生成模块 - :123112324563789012345678011111111111000000012101002003001310000000141040050060015100000001610700800910171000000018111111111search(map,3,3); mapzxzy=1;turn = rand()%2 ? 1 : 3;for(i=0,next=rand()%4;

8、i4; i+,next=(next+turn)%4)if(mapzx+2*dnext0 zy+2*dnext1=0 )mapzx+dnext0zy+dnext1=1;search(map,x+dnext0,y+dnext1);static int d42=0,1, / 0 1,0,/ 1 0,-1,/ 2 -1,0;/ 3 int zx=x*2,zy=y*2,next,turn,i;( 3 + 1 ) % 4 = 4 % 4 = 0( 3 + 3 ) % 4 = 6 % 4 = 2 3 2 0 1next = 3next = 0 1 2 3 随机地图生成模块 - :12311232456378

9、9012345678011111111111000000012101002003001310000000141040050060015100000101610700800910171000000018111111111search(map,3,3); mapzxzy=1;turn = rand()%2 ? 1 : 3;for(i=0,next=rand()%4; i4; i+,next=(next+turn)%4)if(mapzx+2*dnext0 zy+2*dnext1=0 )mapzx+dnext0zy+dnext1=1;search(map,x+dnext0,y+dnext1);stat

10、ic int d42=0,1, / 0 1,0,/ 1 0,-1,/ 2 -1,0;/ 3 int zx=x*2,zy=y*2,next,turn,i; 3 2 0 1next = 3search(map,2,3);随机地图生成模块 - :123112324563789012345678011111111111000000012101002003001310000000141040050061015100000101610700800910171000000018111111111search(map,2,3); mapzxzy=1;turn = rand()%2 ? 1 : 3;for(i=

11、0,next=rand()%4; i4; i+,next=(next+turn)%4)if(mapzx+2*dnext0 zy+2*dnext1=0 )mapzx+dnext0zy+dnext1=1;search(map,x+dnext0,y+dnext1);static int d42=0,1, / 0 1,0,/ 1 0,-1,/ 2 -1,0;/ 3 int zx=x*2,zy=y*2,next,turn,i; 3 2 0 1next = 2随机地图生成模块 - :12311232456378901234567801111111111100000001210100200300131000

12、0000141040050161015100000101610700800910171000000018111111111search(map,2,3); mapzxzy=1;turn = rand()%2 ? 1 : 3;for(i=0,next=rand()%4; i4; i+,next=(next+turn)%4)if(mapzx+2*dnext0 zy+2*dnext1=0 )mapzx+dnext0zy+dnext1=1;search(map,x+dnext0,y+dnext1);static int d42=0,1, / 0 1,0,/ 1 0,-1,/ 2 -1,0;/ 3 in

13、t zx=x*2,zy=y*2,next,turn,i; 3 2 0 1next = 2随机地图生成模块 - :123112324563789012345678011111111111000000012101112113101310101000141041051161015101000101610711810910171000000018111111111 mapzxzy=1;turn = rand()%2 ? 1 : 3;for(i=0,next=rand()%4; i4; i+,next=(next+turn)%4)if(mapzx+2*dnext0 zy+2*dnext1=0 )mapz

14、x+dnext0zy+dnext1=1;search(map,x+dnext0,y+dnext1);static int d42=0,1, / 0 1,0,/ 1 0,-1,/ 2 -1,0;/ 3 int zx=x*2,zy=y*2,next,turn,i;随机地图生成模块 - :1231123245637890000000011121131001010000410511610010001007118109100000000map12=1;map2*x+12*y=1;随机地图生成模块 - :123112324563789010000001112113100101000041051161001

15、0001007118109100000010map12=1;map2*x+12*y=1;随机地图生成模块void Maze_File_Make (int mazeMapMAZE_MAX * 2MAZE_MAX * 2,int x,int y )memset (map,0,sizeof(map);Make_Maze(map,x,y);FILE * outCreat;outCreat = fopen(mazeCreate.out,w);FILE * outBiData;outBiData = fopen(mazeBiData.in,w);for(int j=1;j=y*2+1;j+)for(int

16、 i=1;i=x*2+1;i+)fprintf ( outCreat,%s ,( mapij? :) );fprintf ( outBiData,%d ,( mapij = mapij ? 0 : 1 ) );if(j=y*2)fprintf ( outCreat,n );fprintf(outBiData,n );fclose( outBiData );fclose( outCreat );outBiData = fopen(mazeBiData.in, r);for (int i = 0; i != 2 * y + 1; + i )for ( int j = 0; j != 2 * x +

17、 1; + j )fscanf ( outBiData , %d,&mazeMapij);fclose(outBiData);mazeCreate.out:mazeBiData.in:菜单模块键入选择键入选择操作提示信息操作提示信息操作命令清单操作命令清单菜单模块/光标移动HANDLE hConsole;void gotoxy(int x, int y) hConsole = GetStdHandle(STD_OUTPUT_HANDLE);COORD coord; coord.X = x; coord.Y = y; SetConsoleCursorPosition(hConsole,

18、coord); 游戏模块PosType prePos;int getPos(); /获取键盘输入获取键盘输入Status MovePos(MazeType &maze, int pos ); /位置移动位置移动bool isMoveable ( MazeType &maze ,PosType pos)if ( maze.arrpos.rowpos.col = 1 )return false;return true;void disPlay ( MazeType &maze, PosType pos )/显示迷宫地图显示迷宫地图void disPlay_2 ( MazeType &maze, PosType pos )int row = maze.x ;int col = maze.y ;for(int i=0;irow;i+) for(int j=0;jcol;j+)if ( pos.row = i & pos.col = j )continue;if ( prePos.row = i & prePos.col = j )gotoxy( 2 * j ,i );printf ( );c