数据结构与算法--栈和队列2.pptVIP

递归过程 f(5,3)= f(5,2)+f(2,3) =f(5,1)+f(3,2)+f(2,3) =1+f(3,1)+f(1,2)+f(2,3) =1+1+f(1,1)+f(2,3) =1+1+1+f(2,2) =1+1+1+1+f(2,1) =1+1+1+1+1 =5 void print() //输出栈内元素 { if(head!=NULL) { node* p=head; while(p!=NULL) { cout“ ”p-x“ ”p-y; cout“ ”p-directionendl; p=p-next; } } else cout\n栈为空，打印失败\n; } }; //栈类的定义结束 算法分析 void CreateMaze()//创建迷宫 { int max_way=MAX_X*MAX_Y; // 400 int x,y; for(x=0;xMAX_X;x++) for(y=0;yMAX_Y;y++) maze[x][y]=1; //0~19都是墙壁 srand((unsigned)time(NULL)); for(int i=0;i=max_way;i++) { x=rand()%(MAX_X-2)+1; y=rand()%(MAX_Y-2)+1; maze[x][y]=0; // 0表示可走的路 } maze[1][1]=0; //入口 maze[MAX_X-2][MAX_Y-2]=0; //[18][18]出口 maze[0][1]=8; maze[MAX_X-1][MAX_Y-2]=0; //maze[19][18] } void PrintMaze() //输出迷宫的当前状态 { int x,y; system(“cls”); coutendl; for(x=0;xMAX_X;x++) { for(y=0;yMAX_Y;y++) ｛ if(maze[x][y]==0){cout ;continue;}//通路 if(maze[x][y]==1){cout■;continue;}//墙 if(maze[x][y]==2){cout×;continue;}//死胡同 if(maze[x][y]==3){cout↓;continue;}//向下走 if(maze[x][y]==4){cout→;continue;}//向右走 if(maze[x][y]==5){cout←;continue;}//向左走 if(maze[x][y]==6){cout↑;continue;}//向上走 if(maze[x][y]==7){cout※;continue;}//当前站立位置 if(maze[x][y]==8){cout ;continue;}//通路 } coutendl; } Sleep(200);//延时函数 } void main() { CreateMaze(); //创建迷宫 PrintMaze(); //输出当前迷宫的初始状态 stack_for_maze stack; //定义一个栈的对象，用来记录行走路线 move(stack); //行走中…… PrintMaze(); //输出迷宫的最终状态 stack.print(); } 算法分析 void move(stack_for_maze s) { int x=1,y=1;//出发点 while(1) { maze[x][y]=2; if(maze[x][y+1]==0) // → { s.push(x,y,‘R); //当前位置压栈 maze[x][y]=4; y=y+1; //向右走到一个新位置 maze[x][y]=7; PrintMaze(); if((x==MAX_X-1)(y==MAX_Y-2)) { s.push(x,y,*); cout\n成功走出！！！\n; return; } else continue; } // 省略其余三个方向的试探代码 //上下左右均不通则回退，即出栈一次， //如果出栈导致栈空则说