2022年数据结构迷宫问题源代码 .pdf

《2022年数据结构迷宫问题源代码 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构迷宫问题源代码 .pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构迷宫问题源代码#include<stdio.h> #include<malloc.h> #include<stdlib.h> #include <conio.h> #include"typedef.h" #include "ADTStack.h" #include"maze.h" #include"CONSTANT.h" #define MAXLEN 15 #define TRUE 1 #define FALSE 0 #define OK 1 #define

2、ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define NULL 0 PosType start; PosType end; MazeType maze; bool found; #define MAXLEN 15/ 迷宫包括外墙最大行列数目#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status; / 坐标位置类型typedef

3、 struct int r,c; PosType;/ 迷宫中 r 行 c 列的位置/ 迷宫类型typedef struct int step; PosType seat; / 当前的坐标位置int di; / 往下一坐标位置的方向名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - ElemType; / 结点类型typedef struct ElemType *base; ElemType *top; int size; Stac

4、k; Status FootPrint(MazeType maze,PosType curpos); Status MarkPrint(MazeType maze,PosType curpos); void PrintMaze(MazeType maze); Status MazePath(MazeType maze,PosType start,PosType end); void InitMaze(MazeType maze, char aMAXLENMAXLEN, int row, int col); Status Pass(MazeType maze, PosType curpos);

5、PosType NextPos(PosType curpos,int i); typedef struct NodeType ElemType data; NodeType *next; NodeType,*LinkType; / 栈类型typedef struct int r; int c; char arrMAXLENMAXLEN;/ 可取 ' ','*','','#' MazeType; Status InitStack(Stack &S); /InitStack Status Push(Stack &S,E

6、lemType e) ; Status Pop(Stack &S, ElemType &e) ; Status DestroyStack(Stack &S); /DestroyStack void ClearStack(Stack &S); /ClearStack Status StackEmpty(Stack S); /StackEmpty int StackLength(Stack S); void StackTraverse(Stack S, Status(*visit)(ElemType e); 名师资料总结 - - -精品资料欢迎下载 - - - -

7、- - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - / 创建栈void Initialization() printf("n*"); printf("n * CreatMaze-c MazePath-m PrintMaze Quit*"); printf("n*"); printf("n * Operation: *"); printf("n*"); printf("nn ent

8、er a operation code:c,m,p,q:"); / 读入操作命令符，显示提示信息void ReadCommand(char &cmd) do cmd=getche(); while(!(cmd='c'|cmd='m'|cmd='p'); / 解释 ch-具体执行void Interpret(char cmd) switch(cmd) case 'c': int rnum, cnum, i=0,m=1,n=1; char a2MAXLENMAXLEN; char input20; char data

9、1000; printf("n请输入迷宫数据文件名！n"); scanf("%s",input); FILE *fp; fp=fopen(input,"r"); if(!fp) printf("n不能打开文件n"); break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - while(!feof(fp) fscanf(fp,"%s&

10、quot;,&datai); if(i=0) rnum=(int )datai-(int)'0' if(i=1) cnum=(int)datai-(int)'0' if(i>=2) if(n>cnum)m+;n=1; a2mn=datai; n+; i+; fclose(fp); InitMaze(maze, a2, rnum, cnum); printf("n迷宫建立完成!n"); break; case 'm': printf("n请输入迷宫入口的坐标，以空格为间隔:-"); sca

11、nf("%d %d",&start.r,&start.c); printf("n请输入迷宫出口的坐标，以空格为间隔:-"); scanf("%d %d",&end.r,&end.c); MazePath(maze, start, end); break; case 'p': if(found) printf("n求解迷宫的结果如下-n"); PrintMaze(maze); else printf("n找不到路径！n"); 名师资料总结 - - -

12、精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - void main() char cmd; printf(" welcome to the game! "); Initialization(); do ReadCommand(cmd); / 读入一个操作符命令Interpret(cmd); / 解释执行命令操作符while(cmd!='q'); #include "stdio.h" #inclu

13、de "malloc.h" #include"typedef.h" #include"CONSTANT.h" Status InitStack(Stack &S) / 构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType); if (!S.base) return OVERFLOW; / 存储分配失败S.top = S.base; S.size = STACK_INIT_SIZE; return OK; /InitStack Status Push(S

14、tack &S,ElemType e) if (S.top - S.base >= S.size) / 栈满，追加存储空间S.base = (ElemType*)realloc( S.base,(S.size + STACKINCREMENT)*sizeof (ElemType); if (!S.base) return OVERFLOW; / 存储分配失败S.top = S.base + S.size; S.size += STACKINCREMENT; *S.top+ = e; return OK; /Push 名师资料总结 - - -精品资料欢迎下载 - - - - - -

15、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - Status Pop(Stack &S, ElemType &e) / 若栈不空，则删除S的栈顶元素，/ 用 e 返回其值，并返回OK；/ 否则返回 ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK; /Pop Status DestroyStack(Stack &S) / 释放栈 S所占据的存储空间if(!S.base) return ERR

16、OR; free(S.base);S.base=NULL; S.top= NULL; return OK; /DestroyStack Status ClearStack(Stack &S) / 将栈 S清为空栈? S.top=S.base; return OK; /ClearStack Status StackEmpty(Stack S) / 如果栈为空栈，则返回TRUE ，否则返回FALSE if(S.top=S.base)return TRUE; else return FALSE; /StackEmpty int StackLength(Stack S) / 返回栈 S的长度，

17、实际上是栈中元素的个数return S.top-S.base; /StackLength Status StackTraverse(Stack S,Status (*visit)(ElemType e) int i; / 从栈底到栈顶依次对栈中每个元素调用visit 函数，如果visit 失败，则操作失败if(S.top=S.base) return ERROR; for(i=0;i<S.top - S.base;i+) if(visit(S.basei)=ERROR) return ERROR; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

18、- - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - return OK; /StackTraverse #include<stdio.h> #include<malloc.h> #include<stdlib.h> #include"typedef.h" #include"CONSTANT.h" #include "ADTStack.h" Status MarkPrint(MazeType maze,PosType curp

19、os) maze.arrcurpos.rcurpos.c=''/""表示曾走过但不通return OK; / 曾走过而且是通路标记并返回OK Status FootPrint(MazeType maze,PosType curpos) maze.arrcurpos.rcurpos.c='*'/"*"表示可通return OK; PosType NextPos(PosType &curpos,int i) PosType cpos; cpos=curpos; scanf("%d",&i);

20、 switch(i) /1.2.3.4 分别表示东 ,南,西,北方向case 1 : cpos.c+=1; break; case 2 : cpos.r+=1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - break; case 3 : cpos.c-=1; break; case 4 : cpos.r-=1; break; return cpos; / 判断当前位置是否可通Status Pass(MazeType maz

21、e, PosType curpos) if(maze.arrcurpos.rcurpos.c=' ') return TRUE; else return FALSE; / 创建迷宫/ 按照用户输入的二维数组（或），设置迷宫maze 的初值，包括加上边缘一圈的值void InitMaze(MazeType maze, char aMAXLENMAXLEN, int row, int col) maze.r=row; maze.c=col; int i; for( i=0;i<=col+1;i+) a0i='1' arow+1i='1' for

22、(i=0;i<=row+1;i+) ai0='1' aicol+1='1' for(i=0;i<=maze.r+2;i+) for(int j=0;j<maze.c+2;j+) if(aij='1') maze.arrij='#' else maze.arrij=' ' 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - Status

23、 MazePath(MazeType maze,PosType start,PosType end) / 求解迷宫maze 中，从入口start 到出口 end 的一条路径，若存在，返回TRUE, 否则返回FALSE PosType curpos; int curstep=1; Stack S; bool found; ElemType e; InitStack(S); curpos=start;/ 设定 " 当前位置 " 为" 入口位置 " found=FALSE; do if(Pass(maze,curpos) / 当前位置可以通过，即是未曾走到过的

24、通道块留下足迹FootPrint(maze,curpos);/做可以通过的标识e.seat=curpos; e.di=1; / 为栈顶元素赋值Push(S,e); / 加入路径if(curpos.r=end.r && curpos.c=end.c) found=TRUE;/如果到达终点返回true else curpos=NextPos(curpos,1); curstep+;/ 下一位置是当前位置的东邻 else / 当前位置不能通过if(!StackEmpty(S) Pop(S,e); while(e.di=4 && !StackEmpty(S) MarkP

25、rint(maze,e.seat); / 留下不能通过的标记Pop(S,e); curstep-; if(e.di<4) e.di+; / 换下个方向Push(S,e); / 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - curpos=NextPos(e.seat,e.di); / 进行探索 while(!StackEmpty(S)&&!found); /DestroyStack(S); return

26、found; /MazePath 将标记路径信息的迷宫（字符型方阵）输出到终端(包括外墙 ) void PrintMaze(MazeType maze) for(int i=0;i<=maze.r+2;i+) for(int j=0;j<=maze.c+2;j+) printf(" %c",maze.arrij);/输出迷宫 printf("n"); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -