1 Stack <items> S(sz) ∥栈初始化:创建一个大小为sz的栈,其数据元素类型为 Items 2 items e: int k 3 e.=0; ej=0; ek0; S Push( e ) mazel e i lej1=0 将入囗作为立足点并入栈 4 while(! s IsEmpty( ∥若栈不空则继续循环试探 若空表示已找到所有简单路径,可以结束程序 5{e-sPop();/出栈,准备试探下一方向或实现回溯一步操作 if (e. k-4)maze[e i[.jI /四个方向均试探完毕 消足迹,当再执行到5时回溯一步 else if(ei=n&&ejn) printmaze();∥当前立足点为出囗 成功找到一条简单路径并输出,当再执行到5时回溯一步 else{k=ek;e.k=e.k+l; S Push(e);∥记住立足点的下一试探方向 ei= ei+di[k]; ej==ej+djk];ek=0;/沿k方向前进一步 if( mazee ille. j}=‘)若为通道则切换为新立足点并入栈 &S Push(e ) mazel i[ej=0 2021220
2021/2/20 16 1 Stack <items> s(sz); //栈初始化：创建一个大小为sz 的栈，其数据元素类型为items 2 items e; int k; 3 e.i=0; e.j=0; e.k=0; s.Push( e ); maze[ e.i ][e.j]=‘0’; //将入口作为立足点并入栈 4 while ( ! s.IsEmpty( ) ) //若栈不空则继续循环试探 //若空表示已找到所有简单路径，可以结束程序 5 {e=s.Pop( ); //出栈，准备试探下一方向或实现回溯一步操作 6 if ( e.k==4 ) maze[ e.i ][e.j]=‘ ‘; //四个方向均试探完毕 //消足迹,当再执行到5 时回溯一步 else if ( e.i==n && e.j==n ) printmaze(); //当前立足点为出口 //成功找到一条简单路径并输出，当再执行到5 时回溯一步 else{k=e.k; e.k=e.k+1;s.Push( e ); //记住立足点的下一试探方向 e.i=e.i+di[k]; e.j=e.j+dj[k]; e.k=0; //沿 k 方向前进一步 if ( maze[e.i][e.j]==‘ ‘ )//若为通道则切换为新立足点并入栈 {s.Push( e ); maze[ e.i ][e.j]=‘0’;} } }
作业: 完善迷宫问题解决算法(迷宫数组的输入 inputmazeo算法、 简单路径的输出 printmaze(算法等) 编写软件并上机实习 要求11月6日前完成 2021220
2021/2/20 17 作业： 完善迷宫问题解决算法（迷宫数组的输入inputmaze() 算法、 简单路径的输出printmaze() 算法等） 编写软件并上机实习 要求 11 月 6 日前完成
4.3队列 定义:队列是限制插入操作只能在一端进行,而删除操作只能在另 端进行的线性表,并按先进向出(FIFO)的原则进行操作 在一个队列中,能进行删除的一端称为队首( front),能进行 插入操作的一端称为队尾(rear) 出列 emeI 入列 队首(font 队尾(rear) 与栈类似,队列的封闭性也非常好 栈能对输入序列部分或全局起求逆作用 队列对输入序列起缓冲作用,队列的应用非常广泛 2021220
2021/2/20 18 4.3 队列 定义：队列是限制插入操作只能在一端进行，而删除操作只能在另 一端进行的线性表，并按先进向出（FIFO）的原则进行操作。 在一个队列中，能进行删除的一端称为队首（front），能进行 插入操作的一端称为队尾（rear）。 出列 入列 队首（front） 队尾（rear） 与栈类似，队列的封闭性也非常好 栈能对输入序列部分或全局起求逆作用 队列对输入序列起缓冲作用，队列的应用非常广泛 e0 e1 … en-2 en-1
队列的基本操作 Template class Type class Queue public Queue( int=10) ∥/构造函数,队列初始化操作 void EnQueue( const Type&item);∥/列操作 Type DeQueue( //列操作 ype GetFront() ∥读渎取队首元素操作 void Make Empty ( ∥置队空操作 int IsEmpty (const; ∥判队空操作 int IsFull () const ∥判队满操作 2021220
2021/2/20 19 队列的基本操作 Template < class Type > class Queue { public: Queue ( int = 10 ); //构造函数，队列初始化操作 void EnQueue ( const Type & item ); //入列操作 Type DeQueue ( ); //出列操作 Type GetFront ( ); //读取队首元素操作 void MakeEmpty ( ); //置队空操作 int IsEmpty ( ) const; //判队空操作 int IsFull ( ) const; //判队满操作 }
队列的顺序存储结构——循环队列(环型队列 由于在队列的入列和出列操作中,其对应的队尾和队首指 针(下标)都是进1操作(否则出列操作需要移动所有的数据元 素),随着入列和岀列操作的进行,队尾和队首指针都在逐步增 大,因此队列若用普通的顺序存储结构来实现,则很容易上溢, 基本不能使用,因此实际中一般使用循环队列 通过求余运算(%),可以实现下标的循环累进 index=( index +1)%m 因此,对队首和队尾进行如下操作就可以实现循环队列 front=(font+1)% maxSize队首指针循环进1 rear=(rear+1)% maxSize队尾指针循环进1 maxSize表示数组的最大尺寸 front和rear的最大取值为 maxSize-1 2021220 20
2021/2/20 20 队列的顺序存储结构——循环队列（环型队列） 由于在队列的入列和出列操作中，其对应的队尾和队首指 针（下标）都是进1 操作（否则出列操作需要移动所有的数据元 素），随着入列和出列操作的进行，队尾和队首指针都在逐步增 大，因此队列若用普通的顺序存储结构来实现，则很容易上溢， 基本不能使用，因此实际中一般使用循环队列。 通过求余运算（%），可以实现下标的循环累进： index = ( index + 1 ) % m 0 1 2 … m-1 因此，对队首和队尾进行如下操作就可以实现循环队列： front = ( front +1 ) % maxSize 队首指针循环进1 rear = ( rear + 1 ) % maxSize 队尾指针循环进1 maxSize表示数组的最大尺寸 front 和 rear 的最大取值为maxSize-1