C语言数据结构之迷宫问题
本文实例为大家分享了数据结构c语言版迷宫问题栈实现的具体代码,供大家参考,具体内容如下
程序主要参考自严蔚敏老师的数据结构c语言版,在书中程序的大体框架下进行了完善。关于迷宫问题的思路可查阅原书。
#includeusingnamespacestd; #defineMAXSIZE10 typedefintStatus; typedefstruct{ intx; inty; }Postype; typedefstruct{ intord; Postypeseat; intdir; }SElemType;//栈的元素类型 typedefstruct{ //SElemTypedata[MAXSIZE]; SElemType*top; SElemType*base; }Stack;//栈的结构类型 typedefstruct{ chararr[MAXSIZE][MAXSIZE]; }MAZETYPE;//迷宫结构体 MAZETYPEmaze; voidInitMaze() { maze.arr[0][0]=maze.arr[0][1]=maze.arr[0][2]=maze.arr[0][3]=maze.arr[0][4]=maze.arr[0][5]=maze.arr[0][6]=maze.arr[0][7]=maze.arr[0][8]=maze.arr[0][9]='1'; maze.arr[1][0]=maze.arr[1][3]=maze.arr[1][7]=maze.arr[1][9]='1'; maze.arr[1][1]=maze.arr[1][2]=maze.arr[1][4]=maze.arr[1][5]=maze.arr[1][6]=maze.arr[1][8]='0'; maze.arr[2][0]=maze.arr[2][3]=maze.arr[2][7]=maze.arr[2][9]='1'; maze.arr[2][1]=maze.arr[2][2]=maze.arr[2][4]=maze.arr[2][5]=maze.arr[2][6]=maze.arr[2][8]='0'; maze.arr[3][0]=maze.arr[3][5]=maze.arr[3][6]=maze.arr[3][9]='1'; maze.arr[3][1]=maze.arr[3][2]=maze.arr[3][3]=maze.arr[3][4]=maze.arr[3][7]=maze.arr[3][8]='0'; maze.arr[4][0]=maze.arr[4][2]=maze.arr[4][3]=maze.arr[4][4]=maze.arr[4][9]='1'; maze.arr[4][1]=maze.arr[4][5]=maze.arr[4][6]=maze.arr[4][7]=maze.arr[4][8]='0'; maze.arr[5][0]=maze.arr[5][4]=maze.arr[5][9]='1'; maze.arr[5][1]=maze.arr[5][2]=maze.arr[5][3]=maze.arr[5][5]=maze.arr[5][6]=maze.arr[5][7]=maze.arr[5][8]='0'; maze.arr[6][0]=maze.arr[6][2]=maze.arr[6][6]=maze.arr[6][9]='1'; maze.arr[6][1]=maze.arr[6][3]=maze.arr[6][4]=maze.arr[6][5]=maze.arr[6][7]=maze.arr[6][8]='0'; maze.arr[7][0]=maze.arr[7][2]=maze.arr[7][3]=maze.arr[7][4]=maze.arr[7][6]=maze.arr[7][9]='1'; maze.arr[7][1]=maze.arr[7][5]=maze.arr[7][7]=maze.arr[7][8]='0'; maze.arr[8][0]=maze.arr[8][1]=maze.arr[8][9]='0'; maze.arr[8][2]=maze.arr[8][3]=maze.arr[8][4]=maze.arr[8][5]=maze.arr[8][6]=maze.arr[8][7]=maze.arr[8][8]='0'; maze.arr[9][0]=maze.arr[9][1]=maze.arr[9][2]=maze.arr[9][3]=maze.arr[9][4]=maze.arr[9][5]=maze.arr[9][6]=maze.arr[9][7]=maze.arr[9][8]=maze.arr[9][9]='1'; } StatusinitStack(Stack&s) { s.base=(SElemType*)malloc(MAXSIZE*sizeof(SElemType)); if(!s.base)return0; s.top=s.base; return1; } voidPush(Stack&s,SElemTypee) { *s.top++=e; } voidPop(Stack&s,SElemType&e) { e=*--s.top; } StatusStackEmpty(Stack&s) { if(s.top==s.base)return1; elsereturn0; } StatusPass(Postypecurpos) { if(maze.arr[curpos.x][curpos.y]=='0') return1; elsereturn0; } voidFoot(Postypecurpos) { maze.arr[curpos.x][curpos.y]='*'; } voidMarkPrint(Postypecurpos) { maze.arr[curpos.x][curpos.y]='!'; } StatusStructCmp(Postypea,Postypeb) { if(a.x=b.x&&a.y==b.y)return1; elsereturn0; } //下一个位置 PostypeNextPos(PostypeCurPos,intDir) { PostypeReturnPos; switch(Dir) { case1: ReturnPos.x=CurPos.x; ReturnPos.y=CurPos.y+1; break; case2: ReturnPos.x=CurPos.x+1; ReturnPos.y=CurPos.y; break; case3: ReturnPos.x=CurPos.x; ReturnPos.y=CurPos.y-1; break; case4: ReturnPos.x=CurPos.x-1; ReturnPos.y=CurPos.y; break; } returnReturnPos; } StatusMazePath(Postypestart,Postypeend) { Stacks; SElemTypee; initStack(s); Postypecurpos=start; intcurstep=1; do{ if(Pass(curpos)) { Foot(curpos); e={curstep,curpos,1}; Push(s,e); if(StructCmp(curpos,end))return1; curpos=NextPos(curpos,1); curstep++; } else { if(!StackEmpty(s)) { Pop(s,e); while(e.dir==4&&!StackEmpty(s)) { MarkPrint(e.seat);Pop(s,e); } if(e.dir<4&&!StackEmpty(s)) { e.dir++; Push(s,e); curpos=NextPos(e.seat,e.dir); } } } }while(!StackEmpty(s)); return0; } intmain() { InitMaze(); Postypes,e; s.x=s.y=1; e.x=e.y=8; if(MazePath(s,e)) printf("迷宫成功解密!\n"); else printf("解密失败\n"); for(inti=0;i<10;i++) { for(intj=0;j<10;j++) { printf("%c",maze.arr[i][j]); } printf("\n"); } cout<<"-================================="< 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。