数据结构算法（c语言） 迷宫求解

注释非常详细，希望对你有所帮助。

#include #include #define M 15 #define N 15 struct mark //定义迷宫内点的坐标类型 { int x; int y; }; struct Element //＂恋＂栈元素，嘿嘿。

。

{ int x,y; //x行，y列 int d; //d下一步的方向 }； typedef struct LStack //链栈 { Element elem; struct LStack *next; }*PLStack； /*************栈函数****************/ int InitStack(PLStack &S)//构造空栈 { S=NULL; return 1; } int StackEmpty(PLStack S)//判断栈是否为空 { if(S==NULL) return 1; else return 0; } int Push(PLStack &S, Element e)//压入新数据元素 { PLStack p; p=(PLStack)malloc(sizeof(LStack)); p->elem=e; p->next=S; S=p; return 1; } int Pop(PLStack &S,Element &e) //栈顶元素出栈 { PLStack p; if(!StackEmpty(S)) { e=S->elem; p=S; S=S->next; free(p); return 1; } else return 0； } /***************求迷宫路径函数***********************/ void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2]) { int i,j,d;int a,b; Element elem,e; PLStack S1, S2; InitStack(S1); InitStack(S2); maze[start.x][start.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{ a=i+diradd[d][0]; b=j+diradd[d][1]; if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口 { elem.x=i; elem.y=j; elem.d=d; Push(S1,elem); elem.x=a; elem.y=b; elem.d=886； //方向输出为-1 判断是否到了出口 Push(S1,elem); printf(＂\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为：（行坐标，列坐标，方向）\n＂); while(S1) //逆置序列 并输出迷宫路径序列 { Pop(S1,e); Push(S2,e); } while(S2) { Pop(S2,e); printf(＂-->(%d,%d,%d)＂,e.x,e.y,e.d); } return； //跳出两层循环，本来用break，但发现出错，exit又会结束程序，选用return还是不错滴 } if(maze[a][b]==0) //找到可以前进的非出口的点 { maze[a][b]=2； //标记走过此点 elem.x=i; elem.y=j; elem.d=d; Push(S1,elem)； //当前位置入栈 i=a； //下一点转化为当前点 j=b; d=-1; } d++; } } printf（＂没有找到可以走出此迷宫的路径\n＂）； } /*************建立迷宫*******************/ void initmaze(int maze[M][N]) { int i,j; int m,n； //迷宫行，列 [/M] printf（＂请输入迷宫的行数 m=＂）; scanf(＂%d＂,&m); printf（＂请输入迷宫的列数 n=＂）; scanf(＂%d＂,&n); printf(＂\n请输入迷宫的各行各列：\n用空格隔开，0代表路，1代表墙\n＂,m,n); for(i=1;ifor(j=1;jscanf(＂%d＂,&maze[i][j]); printf（＂你建立的迷宫为（最外圈为墙）...\n＂); for(i=0;i{ maze[i][0]=1; maze[i][n+1]=1; } for(j=0;j{ maze[0][j]=1; maze[m+1][j]=1; } for(i=0;i{ for(j=0;jprintf(＂%d ＂,maze[i][j]); printf(＂\n＂); } } void main() { int sto[M][N]; struct mark start,end; //start,end入口和出口的坐标 int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}}；//行增量和列增量 方向依次为东西南北 [/M] 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＂)； } 测试数据，算法复杂度你就自己来写吧，如果你连这都不自己做，那你一定是在应付作业。

劝你还是自己运行测试一下吧，免得答辩时老师问你，什么都不知道，那你就悲剧了。

祝你好运！！

数据结构算法（c语言） 迷宫求解

注释非常详细，希望对你有所帮助。

#include#include#define M 15 #define N 15 struct mark //定义迷宫内点的坐标类型 { int x; int y; }; struct Element //＂恋＂栈元素，嘿嘿。

。

{ int x,y; //x行，y列 int d; //d下一步的方向 }； typedef struct LStack //链栈 { Element elem; struct LStack *next; }*PLStack； /*************栈函数****************/ int InitStack(PLStack &S)//构造空栈 { S=NULL; return 1; } int StackEmpty(PLStack S)//判断栈是否为空 { if(S==NULL) return 1; else return 0; } int Push(PLStack &S, Element e)//压入新数据元素 { PLStack p; p=(PLStack)malloc(sizeof(LStack)); p->elem=e; p->next=S; S=p; return 1; } int Pop(PLStack &S,Element &e) //栈顶元素出栈 { PLStack p; if(!StackEmpty(S)) { e=S->elem; p=S; S=S->next; free(p); return 1; } else return 0； } /***************求迷宫路径函数***********************/ void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2]) { int i,j,d;int a,b; Element elem,e; PLStack S1, S2; InitStack(S1); InitStack(S2); maze[start.x][start.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{ a=i+diradd[d][0]; b=j+diradd[d][1]; if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口 { elem.x=i; elem.y=j; elem.d=d; Push(S1,elem); elem.x=a; elem.y=b; elem.d=886； //方向输出为-1 判断是否到了出口 Push(S1,elem); printf(＂\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为：（行坐标，列坐标，方向）\n＂); while(S1) //逆置序列 并输出迷宫路径序列 { Pop(S1,e); Push(S2,e); } while(S2) { Pop(S2,e); printf(＂-->(%d,%d,%d)＂,e.x,e.y,e.d); } return； //跳出两层循环，本来用break，但发现出错，exit又会结束程序，选用return还是不错滴} if(maze[a][b]==0) //找到可以前进的非出口的点 { maze[a][b]=2； //标记走过此点 elem.x=i; elem.y=j; elem.d=d; Push(S1,elem)； //当前位置入栈 i=a； //下一点转化为当前点 j=b; d=-1; } d++; } } printf（＂没有找到可以走出此迷宫的路径\n＂）； } /*************建立迷宫*******************/ void initmaze(int maze[M][N]) { int i,j; int m,n； //迷宫行，列 [/M] printf（＂请输入迷宫的行数 m=＂）; scanf(＂%d＂,&m); printf（＂请输入迷宫的列数 n=＂）; scanf(＂%d＂,&n); printf(＂\n请输入迷宫的各行各列：\n用空格隔开，0代表路，1代表墙\n＂,m,n); for(i=1;ifor(j=1;jscanf(＂%d＂,&maze[i][j]); printf（＂你建立的迷宫为（最外圈为墙）...\n＂); for(i=0;i{ maze[i][0]=1; maze[i][n+1]=1; } for(j=0;j{ maze[0][j]=1; maze[m+1][j]=1; } for(i=0;i{ for(j=0;jprintf(＂%d ＂,maze[i][j]); printf(＂\n＂); } } void main() { int sto[M][N]; struct mark start,end; //start,end入口和出口的坐标 int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}}；//行增量和列增量 方向依次为东西南北 [/M] 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＂)； } 测试数据，算法复杂度你就自己来写吧，如果你连这都不自己做，那你一定是在应付作业。

劝你还是自己运行测试一下吧，免得答辩时老师问你，什么都不知道，那你就悲剧了。

祝你好运！！

数据结构 迷宫问题 用栈解决

核心算法是搜索，这里如果要求用栈实现那就是深度优先搜索。

如果他不指定是用栈， 那么用队列来做就是广度优先搜索。

正常的深度优先搜索是可以用递归来实现的， 即然要求你非递归 你可以用栈来模拟递归的效果，毕竟函数的递归调用本质也是用栈来实现的

数据结构 迷宫问题

#include #include #include typedef struct pos /*描述迷宫当前位置和方向*/{ int x; int y; int way; /*0：无效，1：左，2：下，3：右，4：上*/}P;typedef struct LinkNode /*链表结构，用于栈的元素类型*/{ P pos; struct LinkNode *next;}LinkNode;typedef struct stack /*链式栈，用于存储迷宫路径信息*/{ LinkNode *head； /*头指针*/}Stack;int row=0； /*迷宫的行数*/int line=0； /*迷宫的列数*/void InitStack(Stack *s) /*栈置空*/{ s->head=NULL;}void Push(Stack *s,P p) /*数据入栈*/{ LinkNode *LN=(LinkNode *)malloc(sizeof(LinkNode)); LN->pos=p; LN->next=s->head; s->head=LN;}P Pop(Stack *s) /*栈顶元素出栈*/{ P pos; LinkNode *LN; LN=s->head; s->head=s->head->next; pos=LN->pos; delete LN; return pos;}P GetPop(Stack s) /*读取栈顶元素*/{ return s.head->pos;}int Empty(Stack s) /*判空*/{ if(s.head==NULL) return 1; else return 0;}int **InitMaze（) /*返回迷宫的二维指针*/{ int **maze=NULL; int i; int j; printf（＂请输入迷宫的行跟列（x,y）:＂); scanf(＂%d,%d＂,&row,&line)； /*输入迷宫的行和列*/ maze=(int **)malloc((row+2)*sizeof(int *)); for(i=0;i { maze[i]=(int *)malloc(sizeof(int)*(line+2)); } printf（＂请输入迷宫\n＂）； /*输入迷宫，1代表路障，0代表通行*/ for(i=1;i for(j=1;j scanf(＂%d＂,&maze[i][j]); for(i=0;i maze[0][i]=1; for(i=0;i maze[row+1][i]=1; for(i=0;i maze[i][0]=1; for(i=0;i maze[i][line+1]=1; for(i=0;i { for(j=0;j printf(＂%3d＂,maze[i][j]); printf(＂\n＂); } return maze;}void PrintWay(Stack p) /*输出路径*/{ P pos; Stack t； /*临时栈，用于存储从入口到出口的路径*/ LinkNode *temp; int a,b; InitStack(&t); temp=(LinkNode *)malloc(sizeof(LinkNode)); temp->pos=Pop(&p)； /*取栈顶元素，即出口*/ Push(&t,temp->pos)； /*入栈*/ free(temp); while(!Empty(p)) { temp=(LinkNode *)malloc(sizeof(LinkNode)); temp->pos=Pop(&p)； /*获取下一个元素*/ a=GetPop(t).x-temp->pos.x； /*左：a=0,b=1； 下：a=1,b=0*/ b=GetPop(t).y-temp->pos.y； /*右：a=0,b=-1 上：a=-1,b=0;*/ if(b==1) temp->pos.way=1; else if(a==1) temp->pos.way=2; else if(b==-1) temp->pos.way=3; else if(a==-1) temp->pos.way=4; Push(&t,temp->pos)； /*新位置入栈*/ free(temp); } printf（＂迷宫的路径为：\n＂）; printf（＂前两个数字表示位置，最后一个数字表示方向\n＂）; printf(＂1表示向左，2表示向下，3表示向右，4表示向上，0表示无方向\n＂); while(!Empty(t)） /*输出路径*/ { pos=Pop(&t); printf(＂%3d,%3d,%3d\n＂,pos.x,pos.y,pos.way); }}int FindMaze(int **maze,int r,int l) /*寻找路径，找到返回1，没找到返回0*/{ Stack p,q； /*栈p,q分别表示探索迷宫的路径和过程*/ P temp1,temp2; int a,b; InitStack(&p); InitStack(&q); temp1.x=1; temp1.y=1; // maze[1][1]=-1； /*标记已经走过*/ Push(&p,temp1); Push(&q,temp1); while(!Empty(q)) { temp2=GetPop(q); if(!(GetPop(p).x==GetPop(q).x &&GetPop(p).y==GetPop(q).y)) Push(&p,temp2)； /*若有新元素入栈，就把q的栈顶元素存入p中*/ a=temp2.x; b=temp2.y+1； /*当前位置左方向相邻的方块*/ if(maze[a][b]==0) { temp1.x=a; temp1.y=b; maze[a][b]=-1； /*标记已走过*/ Push(&q,temp1); } if(a==r&&b==l) /*到达出口*/ { temp1.way=0; Push(&p,temp1); PrintWay(p); return 1; } a=temp2.x+1; b=temp2.y； /*当前位置下方向相邻的方块*/ if(maze[a][b]==0) { temp1.x=a; temp1.y=b; maze[a][b]=-1； /*标记已走过*/ Push(&q,temp1); } if(a==r&&b==l) /*到达出口*/ { temp1.way=0; Push(&p,temp1); PrintWay(p); return 1; } a=temp2.x; b=temp2.y-1； /*当前位置右方向相邻的方块*/ if(maze[a][b]==0) { temp1.x=a; temp1.y=b; maze[a][b]=-1； /*标记已走过*/ Push(&q,temp1); } if(a==r&&b==l) /*到达出口*/ { temp1.way=0; Push(&p,temp1); PrintWay(p); return 1; } a=temp2.x-1; b=temp2.y； /*当前位置上方向相邻的方块*/ if(maze[a][b]==0) { temp1.x=a; temp1.y=b; maze[a][b]=-1； /*标记已走过*/ Push(&q,temp1); } if(a==r&&b==l) /*到达出口*/ { temp1.way=0; Push(&p,temp1); PrintWay(p); return 1; } if(GetPop(p).x==GetPop(q).x &&GetPop(p).y==GetPop(q).y） /*若四个方向都走不通，则数据出栈，退回一格*/ { Pop(&p); Pop(&q); } } return 0； /*探索迷宫失败*/}void main(){ int **maze=InitMaze（)； /*初始化迷宫*/ if(FindMaze(maze,row,line)） /*探索路径*/ printf（＂路径探索成功！\n＂）; else printf（＂路径探索失败！\n＂）; getch();}

数据结构C语言迷宫问题？迷宫来历：这是实验心

注：下面分别是三个文件：栈的定义与声明（头文件）、栈的实现、迷宫问题。

/* 顺序栈表示：类型和界面函数声明 */ enum { MAXNUM = 20 /* 栈中最大元素个数，应根据需要定义 */ }； typedef int DataType； /* 栈中元素类型，应根据需要定义 */ struct SeqStack { /* 顺序栈类型定义 */ int t； /* 栈顶位置指示 */ DataType s[MAXNUM]; }; typedef struct SeqStack SeqSack, *PSeqStack； /* 顺序栈类型和指针类型 */ /*创建一个空栈；为栈结构申请空间，并将栈顶变量赋值为-1*/ PSeqStack createEmptyStack_seq( void )；/*判断pastack所指的栈是否为空栈，当pastack所指的栈为空栈时，则返回1，否则返回0*/ int isEmptyStack_seq( PSeqStack pastack )；/* 在栈中压入一元素x */ void push_seq( PSeqStack pastack, DataType x )；/* 删除栈顶元素 */ void pop_seq( PSeqStack pastack )；/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */ DataType top_seq( PSeqStack pastack )；/* 顺序栈表示：函数定义 */#include #include #include ＂sstack.h＂/*创建一个空栈；为栈结构申请空间，并将栈顶变量赋值为-1*/ PSeqStack createEmptyStack_seq( void ) { PSeqStack pastack = (PSeqStack)malloc(sizeof(struct SeqStack)); if (pastack==NULL) printf(＂Out of space!! \n＂); else pastack->t = -1; return pastack； }/*判断pastack所指的栈是否为空栈，当pastack所指的栈为空栈时，则返回1，否则返回0*/ int isEmptyStack_seq( PSeqStack pastack ) { return pastack->t == -1； }/* 在栈中压入一元素x */ void push_seq( PSeqStack pastack, DataType x ) { if( pastack->t >= MAXNUM - 1 ) printf( ＂Stack Overflow! \n＂ ); else { pastack->t++; pastack->s[pastack->t] = x； } }/* 删除栈顶元素 */ void pop_seq( PSeqStack pastack ) { if (pastack->t == -1 ) printf( ＂Underflow!\n＂ ); else pastack->t--； }/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */ DataType top_seq( PSeqStack pastack ) { return pastack->s[pastack->t]； }/* 迷宫问题的非递归算法（栈实现）*/#define MAXNUM 100/* 栈中最大元素个数 */#define N 11 /*地图的第一维长度*/#include #include typedef struct { int x；/* 行下标 */ int y；/* 列下标 */ int d；/* 运动方向 */ } DataType; struct SeqStack { /* 顺序栈类型定义 */ int t； /* 指示栈顶位置 */ DataType s[MAXNUM]; }; typedef struct SeqStack *PSeqStack； /* 顺序栈类型的指针类型 */ PSeqStack pastack; /* pastack是指向顺序栈的一个指针变量 */ PSeqStack createEmptyStack_seq( void ) { PSeqStack pastack; pastack = (PSeqStack)malloc(sizeof(struct SeqStack)); if (pastack == NULL) printf(＂Out of space!! \n＂); else pastack->t = -1; return pastack; } int isEmptyStack_seq( PSeqStack pastack ) { return pastack->t == -1； }/* 在栈中压入一元素x */ void push_seq( PSeqStack pastack, DataType x ) { if( pastack->t >= MAXNUM - 1 ) printf( ＂Overflow! \n＂ ); else { pastack->t++; pastack->s[pastack->t] = x； } }/* 删除栈顶元素 */ void pop_seq( PSeqStack pastack ) { if (pastack->t == -1 ) printf( ＂Underflow!\n＂ ); else pastack->t--； }/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */ DataType top_seq( PSeqStack pastack ) { return (pastack->s[pastack->t]); } void pushtostack(PSeqStack st, int x, int y, int d) { DataType element; element.x = x; element.y = y; element.d = d; push_seq(st, element); } void printpath(PSeqStack st) { DataType element; printf(＂The revers path is:\n＂)； /* 打印路径上的每一点 */ while(!isEmptyStack_seq(st)) { element = top_seq(st); pop_seq(st); printf(＂the node is: %d %d \n＂, element.x, element.y)； } }/* 迷宫maze[M][N]中求从入口maze[x1][y1]到出口maze[x2][y2]的一条路径 *//* 其中 1void mazePath(int maze[][N], int direction[][2], int x1, int y1, int x2, int y2) { int i, j, k, g, h; PSeqStack st; DataType element; st = createEmptyStack_seq( ); maze[x1][y1] = 2； /* 从入口开始进入，作标记 */ pushtostack(st, x1, y1, -1)； /* 入口点进栈 */ while ( !isEmptyStack_seq(st)） { /* 走不通时，一步步回退 */ element = top_seq(st); pop_seq(st); i = element.x; j = element.y; for (k = element.d + 1; k g = i + direction[k][0];h = j + direction[k][1]; if (g == x2 && h == y2 && maze[g][h] == 0) { /* 走到出口点 */ printpath(st)； /* 打印路径 */ return; } if (maze[g][h] == 0) { /* 走到没走过的点 */ maze[g][h] = 2； /* 作标记 */ pushtostack(st, i, j, k)； /* 进栈 */ i = g; j = h; k = -1； /* 下一点转换成当前点 */ } } } printf(＂The path has not been found.\n＂)；/* 栈退完未找到路径 */ } int main(){ int direction[][2]={0,1,1,0,0,-1,-1,0}; int maze[][N] = { 1,1,1,1,1,1,1,1,1,1,1, 1,0,1,0,0,1,1,1,0,0,1, 1,0,0,0,0,0,1,0,0,1,1, 1,0,1,1,1,0,0,0,1,1,1, 1,0,0,0,1,0,1,1,0,1,1, 1,1,0,0,1,0,1,1,0,0,1, 1,1,1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,1 }; mazePath(maze,direction,1,1,6,9); getchar(); return 0; }

c语言版数据结构,要求用队列求解迷宫最短路径。

// Migong_Queue.cpp ： 定义控制台应用程序的入口点。

#include ＂stdafx.h＂#include ＂stdlib.h＂#define MaxSize 100 struct { int i,j; int pre; }Qu[MaxSize]; int front = -1,rear = -1; int mgpath(int **,int ,int ,int ,int); void print(int); int _tmain(int argc, _TCHAR* argv[]) { int l,h; FILE *migong=fopen(＂C:\\Users\\Administrator\\Documents\\Visual Studio 2010\\Projects\\数据结构实验\\Migong_Queue\\migong.txt＂,＂r＂); if(migong==NULL) { printf(＂Can't open the file!!!＂); exit(0); } char ch=fgetc(migong); l=0; while(ch!='\n') { if(ch!=',') l++; ch=fgetc(migong); }//l为迷宫的长度 rewind(migong)； //接下来是算出迷宫的高度h!~~ h=0; ch=fgetc(migong); while(!feof(migong)) { if(ch=='\n') h++; ch=fgetc(migong); } if(l { printf(＂It's too small!＂); exit(0); } rewind(migong); int **mg=(int **)malloc(sizeof(int *)*h); for(int h_=0;h_ { mg[h_]=(int *)malloc(sizeof(int)*l); } for(int h_=0;h_ { for(int l_=0;l_ { ch=fgetc(migong); if(ch!=',') {mg[h_][l_]=ch-'0';l_++;} } ch=fgetc(migong); } fclose(migong); printf(＂The map is presented as follows:\n＂); for(int _x=0;_x for(int _y=0;_y { printf(＂%d ＂,mg[_x][_y]); if((_y+1)%l==0) printf(＂\n＂); } mgpath(mg,1,1,8,8); return 0; } int mgpath(int **mg,int xi,int yi,int xe,int ye) { int i,j,find=0,di; rear++; Qu[rear].i=xi; Qu[rear].j=yi; Qu[rear].pre=-1; mg[xi][yi]=-1; while(front { front++; i=Qu[front].i;j=Qu[front].j; if(i==xe&&j==ye) { find=1; print(front); return 1; } for(di=0;di { switch(di) { case 0:i=Qu[front].i-1;j=Qu[front].j;break; case 1:i=Qu[front].i;j=Qu[front].j+1;break; case 2:i=Qu[front].i+1;j=Qu[front].j;break; case 3:i=Qu[front].i;j=Qu[front].j-1;break; } if(mg[i][j]==0) { rear++; Qu[rear].i=i;Qu[rear].j=j; Qu[rear].pre=front; mg[i][j]=-1; } } } return 0; } void print(int front) { int k=front,j,ns=0; printf(＂\n＂); do { j=k; k=Qu[k].pre; Qu[j].pre=-1; }while(k!=0); printf（＂迷宫路径如下：\n＂）; k=0; while(k { if(Qu[k].pre==-1) { ns++; printf(＂\t(%d,%d)＂,Qu[k].i,Qu[k].j); if(ns%5==0)printf(＂\n＂); } k++; } printf(＂\n＂)； } 我是从文件中读取迷宫数组的！你也可以改为直接输入！希望对你有帮助！谢谢！

能给个数据结构自动生成迷宫图的算法吗？

#include #include #include int M,N;typedef struct _Position{int x;int y;}Position;void Print( int** const );void Line( int** const p, Position, Position );int main(){srand( (unsigned)time(NULL) );Position a,b;int i,j;printf（＂请输入迷宫行列：＂）；scanf(＂%d %d＂,&M,&N);while(getchar()!='\n');int** const p = (int**) malloc( M*sizeof(int*) );for( i=0; i{p[i] = (int*) malloc( N*sizeof(int) );for( j=0; j{p[i][j]=1;}}p[1][1]=p[M-2][N-2]=0;a.x=M-2;a.y=N-2;b.x=1;b.y=1;Line( p, a, b );while(1){a.x=rand()%(M-1)+1;a.y=rand()%(N-1)+1;b.x=rand()%(M-1)+1;b.y=rand()%(N-1)+1;if( a.x {i=a.x;a.x=b.x;b.x=a.x;}Line( p, a, b);if( rand()%6 ==0 ) break;}Print( p );getchar();return 0;}void Print( int** const dat ){int i,j;for( i=0; i{for( j=0; j{printf(＂%d＂,dat[i][j]);}printf(＂\n＂);}printf(＂\n＂);}void Line( int** const p, Position Fr, Position To ){srand( (unsigned)time(NULL) );int a,b,x,y,i,j;a=Fr.x;b=Fr.y;i=Fr.x-1;while(i>=To.x){if(i==To.x){j=To.y;}else{j=rand()%(N-1)+1;}p[i][j]=0;x=i;y=j;while(j!=b){p[i][j]=0;if(p[i+1][j]==0){break;}if(j>b){j--;}else{j++;}if(i!=a && (rand()%2)==0){p[i][j]=0;i++;}}a=x;b=y;i=x-1;}}

数据结构中定义一个迷宫数组,如何输出

*迷宫源程序*/ #include #include #include #include #include #define N 20/*迷宫的大小，可改变*/ int oldmap[N][N]；/*递归用的数组，用全局变量节约时间*/ int yes=0;/*yes是判断是否找到路的标志，1找到，0没找到*/ int way[100][2],wayn=0;/*way数组是显示路线用的，wayn是统计走了几个格子*/ void Init(void)；/*图形初始化*/ void Close(void)；/*图形关闭*/ void DrawPeople(int *x,int *y,int n)；/*画人工探索物图*/ void PeopleFind(int (*x)[N]）；/*人工探索*/ void WayCopy(int (*x)[N],int (*y)[N]）；/*为了8个方向的递归，把旧迷宫图拷贝给新数组*/ int FindWay(int (*x)[N],int i,int j）；/*自动探索函数*/ void MapRand(int (*x)[N]）；/*随机生成迷宫函数*/ void PrMap(int (*x)[N]）；/*输出迷宫图函数*/ void Result(void)；/*输出结果处理*/ void Find(void)；/*成功处理*/ void NotFind(void)；/*失败处理*/ void main(void)/*主函数*/ { int map[N][N]； /*迷宫数组*/ char ch; clrscr();

数据结构算法 用C++ 迷宫最短路径

一般迷宫寻路可以用递归的算法，或者用先进后出的栈数据结构实现 用的是深度优先的算法，可以寻找到走出迷宫的路径 但本题要求求出最短的路径，这就要使用广度优先的算法 一般在程序中需要用到先进先出的队列数据结构 下面是程序的代码，主要原理是用到 quei,quej和prep三个数组来构成队列 分别储存路径的行，列坐标和上一个节点在队列中的位置 大致算法如下，右三个嵌套的循环实现 首先是第一个节点进入队列 当队列不空（循环1） { 遍历队列中每节点（循环2） { 将八个方向能够走的节点加入队列（循环3） } 旧的节点出列 } #include#include using namespace std; #define MAXNUM 50void main() { int m,n,i,j,x; cout>m>>n; int maze[MAXNUM][MAXNUM]; srand((int)time(NULL)); for(i=0;i700){maze[i][j]=1；} //控制矩阵中1的个数，太多1迷宫很容易走不通 else{maze[i][j]=0;} } cout<<maze[i][j]<<' '; } cout<<endl； } //以上是输入和迷宫生成，一下是走迷宫 int move[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1}; int *quei=new int[m*n]；//储存行坐标队列 int *quej=new int[m*n]；//储存列坐标队列 int *prep=new int[m*n]；//储存之前一步在队列中的位置 int head,rear,length；//队列头，队列尾，队列长度 head=0;rear=1;length=1; quei[head]=1;quej[head]=1;prep[head]=-1；//入口位置进队列 int pos；//当前节点在队列中的位置， int ii,jj,ni,nj；//当前节点的坐标，新节点的坐标 int dir；//移动方向 if(maze[1][1]==1)length=0；//第一点就不能通过 else maze[1][1]=1; while(length)//队列非空继续 { for(pos=head;pos<head+length;pos++)//寻找这一层所有节点 { ii=quei[pos];jj=quej[pos]；//当前位置坐标 if(ii==m&&jj==n)break; for(dir=0;dir<8;dir++)//寻找8个方向 { ni=ii+move[dir][0];nj=jj+move[dir][1]；//新坐标 if(maze[ni][nj]==0)//如果没有走过 { quei[rear]=ni;quej[rear]=nj;prep[rear]=pos；//新节点入队 rear=rear+1; maze[ni][nj]=1；//标记已经走过 } } } if(ii==m&&jj==n)break; head=head+length; length=rear-head；//这一层节点出列 } if(ii==m&&jj==n) { while(pos!=-1) { cout<<'('<<quei[pos]<<','<<quej[pos]<<')'; pos=prep[pos]; if (pos!=-1)cout<<','; } } else { cout<<＂THERE IS NO PATH.＂<<endl; } delete []quei; delete []quej; delete []prep;}