数据结构与算法__第三章_清华大学出版社_赵玉兰

1、2栈（栈（Stack）u只允许在表的一端进行插只允许在表的一端进行插入和删除的线性表入和删除的线性表u允许插入和删除的一端称允许插入和删除的一端称为栈顶（为栈顶（top），另一端称），另一端称为栈底（为栈底（bottom）u不含元素的栈称为空栈不含元素的栈称为空栈 u插入：进栈，入栈插入：进栈，入栈 删除：出栈，退栈删除：出栈，退栈u特点特点后进先出（后进先出（LIFO）先进后出（先进后出（FILO）3问题问题u有三个元素按有三个元素按 a1, a2, a3 的次序依次进栈，其出栈的次序依次进栈，其出栈次序有几种可能？次序有几种可能？出栈次序：出栈次序： a1，a2，a3 a1，a3，a2 a

2、2，a1，a3 a2，a3，a1 a3，a2，a1注意：注意：栈只是对表插入和删除操作的位置进行了限栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。制，并没有限定插入和删除操作进行的时间。4栈的抽象数据类型栈的抽象数据类型ADT Stack Data 数据项列表数据项列表 top：栈顶位置：栈顶位置 Operations Constructor Process：创建一个空栈：创建一个空栈 IsEmpty Process：判断栈是否为空：判断栈是否为空 Output：如果栈为空，则返回：如果栈为空，则返回true，否则返回，否则返回false GetTop Proc

3、ess：取栈顶元素：取栈顶元素 Output：返回栈顶元素：返回栈顶元素5 Length Process：求栈中元素个数：求栈中元素个数 Output：返回栈中元素的个数：返回栈中元素的个数 Push Input：要添加的数据元素：要添加的数据元素 Process：向栈中添加元素：向栈中添加元素x，即进栈，即进栈 Pop Process：删除栈顶元素，即出栈：删除栈顶元素，即出栈 Output：返回栈顶元素：返回栈顶元素 Clear Process：删除栈中所有元素并置新的栈顶：删除栈中所有元素并置新的栈顶 /Stack6顺序栈顺序栈顺序栈的定义顺序栈的定义如何改造数组实现栈的顺序存储？如何改

4、造数组实现栈的顺序存储？ 0 1 2 3 4 5 6附设指针附设指针top指示栈顶元指示栈顶元素在数组中的位置。素在数组中的位置。 top确定用数组的哪确定用数组的哪一端表示栈底。一端表示栈底。a1a2a37顺序栈的基本操作顺序栈的基本操作出栈：先出栈出栈：先出栈 top再减再减1进栈：进栈：top先加先加1 再进栈再进栈栈空：栈空：top= -1 0 1 2 3 4 5 6 7 8a1topa2topa3top栈满：栈满：top=MaxStackSize-1top top8const int MaxStackSize=50; /栈中能容纳最大元素个数栈中能容纳最大元素个数class SeqS

5、tack DataType StackListMaxStackSize; int top; public: Stack (); /构造函数，初始化构造函数，初始化top bool IsEmpty (); /判断栈的状态是否为空判断栈的状态是否为空 bool IsFull (); DataType GetTop (); /取栈顶元素取栈顶元素 void Push (const DataType x); /入栈入栈 DataType Pop (); /出栈出栈 void Clear (); /栈清空栈清空;/ SeqStack9顺序栈的操作的实现顺序栈的操作的实现u构造函数，初始化一个空栈构造函数

6、，初始化一个空栈 Stack ( ) StackList = new DataTypeMaxStackSize; top=-1; / Stack10u判断栈是否为空判断栈是否为空 bool IsEmpty ( ) if (top=-1) return true; else return false; / IsEmpty11u判断栈是否已满判断栈是否已满 bool IsFull( ) if (top=MaxStackSize-1) return true; else return false; / IsFull12u取栈顶元素取栈顶元素 DataType GetTop( ) if (IsEmpt

7、y( ) cout”栈空！栈空！”endl; return nulldata; return StackListtop; 13u向栈顶压入元素向栈顶压入元素 void Push (DataType x) if (IsFull( ) cout”栈满！栈满！”endl; else StackList+top = x; / Push14u删除栈顶元素删除栈顶元素 DataType Pop( ) if (IsEmpty( ) cout”栈空！栈空！”next=NULL; /创建头结点创建头结点 void Push (DataType data);18 DataType Pop ( ); DataTyp

8、e GetTop ( ); void Clear ( ) top-next=NULL; bool IsEmpty ( ) return top -next= = NULL; ;/ LinkStack19类中操作算法的描述类中操作算法的描述u入栈操作入栈操作 void Push (DataType item ) p=new StackNode ( item); p-next=top-next; top-next=p; /Push20u出栈操作出栈操作 DataType pop ( ) if ( top-next!=NULL ) p=top-next; retvalue=p-data; /暂存栈顶

9、数据暂存栈顶数据 top -next=p-next; /修改栈顶指针修改栈顶指针 delete p; /释放，返回数据释放，返回数据 return retvalue; else /栈空的情况栈空的情况 cout”the stack is empty!”next!=NULL) return top-next-data; else /栈空的情况栈空的情况 cout”the stack is empty!”1时，先把塔时，先把塔 A 上的上的 n-1 个圆盘移到塔个圆盘移到塔 B，然后将，然后将 n 号盘从塔号盘从塔 A 移到塔移到塔 C，再将，再将 n-1 个圆盘从塔个圆盘从塔 B移到塔移到塔C。

10、即把求解即把求解 n 个圆盘的个圆盘的Hanoi问题转化为求解问题转化为求解 n-1 个圆盘个圆盘的的 Hanoi 问题，依次类推，直至转化成只有一个圆盘问题，依次类推，直至转化成只有一个圆盘的的 Hanoi 问题。问题。3132u解决汉诺塔问题的算法解决汉诺塔问题的算法 main( ) int n; coutn; hanoi( n ,A,B,C ); void hanoi (int n,char x,char y,char z) if (n=1) move (1,x,z); else hanoi (n-1,x,z,y); move (n,x,z); hanoi (n-1,y,x,z); 33

11、递归过程和运行时栈递归过程和运行时栈递归函数的运行轨迹递归函数的运行轨迹u描述方法描述方法1）写出函数当前调用层执行的各语句，并用箭头表示语）写出函数当前调用层执行的各语句，并用箭头表示语句的执行次序；句的执行次序；2）对函数的每个递归调用，写出相应的函数调用，从调）对函数的每个递归调用，写出相应的函数调用，从调用处画一条箭头指向被调用函数入口，表示调用路线，用处画一条箭头指向被调用函数入口，表示调用路线，从被调用函数末尾处画一条箭头指向调用语句的下面，从被调用函数末尾处画一条箭头指向调用语句的下面，表示返回路线；表示返回路线；3）在返回路线上标出本层调用所得的函数值。）在返回路线上标出本层调

12、用所得的函数值。 34un=3 时汉诺塔递归算法的运行轨迹时汉诺塔递归算法的运行轨迹Hanoi ( 3, A, B, C）Move ( A, 3, C )Hanoi ( 2, A, C, B）Hanoi ( 2, A, C, B）Hanoi ( 3, A, B, C）Hanoi ( 1, A, B, C）递归第三层递归第三层递归第二层递归第二层递归第一层递归第一层Move ( A, 1, C )Hanoi ( 1, C, A, B）Move ( C, 1, B )Hanoi ( 1, B, C, A）Move ( B, 1, A )Hanoi ( 1, A, B, C）Move ( A, 1,

13、 C )Hanoi ( 1, A, B, C）Move ( A, 2, B )Hanoi ( 1, C, A, B）Hanoi ( 2, B, A, C）Hanoi ( 1, B, C, A）Move ( B, 2, C )Hanoi ( 1, A, B, C）Hanoi ( 2, B, A, C）(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)35递归函数的内部执行过程递归函数的内部执行过程u当一个函数在运行期间调用另一个函数时，在运当一个函数在运行期间调用另一个函数时，在运行被调用函数之前，系统需要将实参和返回值地行被调用函数之前，系统需要将实

14、参和返回值地址等数据传递给被调函数，当函数调用时，这些址等数据传递给被调函数，当函数调用时，这些数据与局部变量一起构成一条数据与局部变量一起构成一条“工作记录工作记录”，被，被压入系统提供的栈（运行时栈）。压入系统提供的栈（运行时栈）。u当被调函数返回时，按照返回地址执行调用函数当被调函数返回时，按照返回地址执行调用函数中下一条指令，同时释放栈中相应的工作记录。中下一条指令，同时释放栈中相应的工作记录。36主程序主程序Call proc1rproc1proc2proc3sCall proc2tCall proc3系统运行时栈系统运行时栈局部变量局部变量返回地址返回地址实际参数实际参数工作记录工

15、作记录37u递归调用的内部执行过程递归调用的内部执行过程运行开始时，首先为递归调用建立一个系统运行时栈；运行开始时，首先为递归调用建立一个系统运行时栈；每次执行递归调用之前，把递归函数的值参和局部变每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址等组成的工作记录量的当前值以及调用后的返回地址等组成的工作记录压入栈中；压入栈中；每次递归调用结束后，将栈顶元素出栈，使相应的值每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。指定的位置继续执行。38un=3 时汉诺

16、塔递归算法的部分执行过程时汉诺塔递归算法的部分执行过程 main() hanoi ( 3,A,B,C ); void hanoi(int n,char x,char y,char z) if (n=1) move (1,x,z); else hanoi (n-1,x,z,y); move (n,x,z); hanoi (n-1,y,x,z); 0123456789ABC321返回返回地址地址zyxn 3ABC 01CAB82ACB61ABC61239递归总结递归总结u递归是重要的设计和编程工具，使许多算法变得递归是重要的设计和编程工具，使许多算法变得简单，易于设计和实现。简单，易于设计和实现。

17、 优点优点u递归使算法的时间复杂度和空间复杂度同时增大，递归使算法的时间复杂度和空间复杂度同时增大，有时会导致效率急剧恶化，或者溢出系统栈。有时会导致效率急剧恶化，或者溢出系统栈。 缺点缺点u使用递归时应该权衡效率和设计的关系。在有足使用递归时应该权衡效率和设计的关系。在有足够的空间并且时间要求不高的情况下可以使用递够的空间并且时间要求不高的情况下可以使用递归。归。40定义定义u队列（队列（Queue）是只允许在表的一端进行删除，而）是只允许在表的一端进行删除，而在另一端进行插入的线性表。在另一端进行插入的线性表。允许删除的一端叫做队头（允许删除的一端叫做队头（front）允许插入的一端叫做队

18、尾（允许插入的一端叫做队尾（rear）u特点特点先进先出（先进先出（FIFO，First In First Out）a1 a2 a3. an 入队入队出队出队frontrear41ADT队列的定义队列的定义ADT Queue Data 数据项列表数据项列表 front：队列中第一个元素的位置：队列中第一个元素的位置 rear：队列中最后一个元素的位置：队列中最后一个元素的位置 Operations Constructor Process：初始化队首和队尾：初始化队首和队尾 IsEmpty Process：判断是否为空队列：判断是否为空队列 Output：若队列空，返回：若队列空，返回true，

19、否则返回，否则返回false42 Length Process：求队列中元素个数：求队列中元素个数 Output：返回队列的元素个数：返回队列的元素个数 Front Process：取出队头元素：取出队头元素 Output：返回队头元素：返回队头元素 Enter Input：要进入队列的元素：要进入队列的元素 Process：在队尾插入新的元素：在队尾插入新的元素 Leave Process：删除队头元素：删除队头元素 Output：返回队头元素：返回队头元素 ClearQueue Process：删除队列中所有元素并设置初始状态：删除队列中所有元素并设置初始状态/Queue43顺序队列顺序队

20、列顺序队列的定义顺序队列的定义const int MaxQSize=50;class SeqQueue int front, rear; DataType QueueListMaxQSize; public: SeqQueue();/构造函数构造函数,初始化数据成员初始化数据成员 void Enter(DataType item); DataType Leave(); void Clear(); DataType Front(); int Length(); bool IsEmpty(); bool IsFull(); ;/ SeqQueue44顺序队列的进队和出队顺序队列的进队和出队 u设两

21、个指针设两个指针 front 和和 rear（初始（初始 frontrear0）ufront 指向队头元素，出队时先取出，再指向队头元素，出队时先取出，再 front+1urear 指向队尾元素的下一个位置，进队时先将新元素加入，指向队尾元素的下一个位置，进队时先将新元素加入，再再 rear+1u队空条件：队空条件：front=rear，此时不能出队，此时不能出队u队满条件：队满条件：rear=MaxQSize，此时不能进队，此时不能进队图3.10 头尾指针和队列中元素的变化rear543210543210d1d2d3543210d1d2d3d4d5d6frontfrontrearrear54

22、3210d5d6rearfront(a) 空队列(b) d1,d2,d3入队(c) d4,d5,d6入队(d) d1,d2,d3,d4出队45u存在问题存在问题 rear=MaxQSize时，再有元素进队时，再有元素进队发生溢出发生溢出l当当front= 0真溢出真溢出l当当front 0假溢出假溢出u解决假溢出的方案解决假溢出的方案固定队头，出队时，剩余元素均向前固定队头，出队时，剩余元素均向前移动移动固定队尾，入队时，剩余元素均向前固定队尾，入队时，剩余元素均向前移动移动循环队列：把队列设想成环形，让循环队列：把队列设想成环形，让 0 接在接在 MaxQSize-1 后后更好更好图3.10

23、 头尾指针和队列中元素的变化rear543210543210d1d2d3543210d1d2d3d4d5d6frontfrontrearrear543210d5d6rearfront(a) 空队列(b) d1,d2,d3入队(c) d4,d5,d6入队(d) d1,d2,d3,d4出队图3.10 头尾指针和队列中元素的变化rear543210543210d1d2d3543210d1d2d3d4d5d6frontfrontrearrear543210d5d6rearfront(a) 空队列(b) d1,d2,d3入队(c) d4,d5,d6入队(d) d1,d2,d3,d4出队46循环队列循环队

24、列u也是队列的顺序存储结构也是队列的顺序存储结构u实现实现利用利用“模模”运算运算入队入队lQueueListrear=item; rear=(rear+1)%MaxQSize; 出队出队litem=QueueListfront; front=(front+1)% MaxQSize; 01frontrear.MaxQSize-147u仍然存在问题仍然存在问题如何判断队列是如何判断队列是“空空”还是还是“满满”？3.11循环队列示意图(a)一般情况 (b)队满时 4 5 32 1 0 front rear (c)队空时 45 3 21 0 d1 d2 d3 d4 d5 d6 frontrear

25、453 2 1 0front rear d1 d2 d3 队空：队空：front=rear队满：队满：front=rear48u三种处理方法三种处理方法给队列设一个标志位以区别队列是空还是满给队列设一个标志位以区别队列是空还是满给队列增加一个统计元素个数的变量给队列增加一个统计元素个数的变量 count，当，当count=MaxQSize 时队满；时队满；count=0 时队空时队空少用一个变量，约定少用一个变量，约定 rear+1 等于等于 front（从后面赶上队（从后面赶上队头指针）为队满的情况头指针）为队满的情况l队满条件：队满条件：( rear+1 ) % MaxQSize=fron

26、tl队空条件：队空条件： frontrear49u循环队列类的操作算法描述循环队列类的操作算法描述构造函数，初始化一个空队列构造函数，初始化一个空队列 SeqQueue () front=rear=0; / SeqQueue入队操作入队操作 void Enter (DataType item) if ( (rear+1)%MaxQSize=front ) /判断是否队满判断是否队满 cout”队列已满，不能入队！队列已满，不能入队！”endl; else QueueListrear=item; rear=(rear+1)%MaxQSize; / Enter50出队操作出队操作 DataType

27、 Leave() if ( front=rear ) /判断是否队空判断是否队空 cout”队列已空，不能出队队列已空，不能出队”next = NULLfront图图 3.13 链队列链队列a1a2a3a4 rear53u链队列描述链队列描述 class QNode /链队结点的类链队结点的类 DataType data; QNode *next; public: QNode(DataType item=nulldata) data= item; next=NULL; friend class LinkQueue; ; / QNode54class LinkQueue QNnode *fron

28、t, *rear; public: LinkQueue() rear =front=new QNode(); void Enter (DataType item ); DataType Leave(); DataType Front(); void Clear () front-next = rear-next = NULL; bool IsEmpty () return front next= NULL; ; / LinkQueue 55u链队列基本操作的算法描述链队列基本操作的算法描述入队操作入队操作 void Enter ( DataType item ) rear-next = new

29、 QNode ( item); rear=rear-next; /Enter56出队操作出队操作 DataType Leave( ) if (!IsEmpty ( ) ) /判队不空判队不空 p = front-next; DataType retvalue = p-data;/保存队头的值保存队头的值 front-next = p-next; delete p; if ( front-next=NULL ) /删除队列中唯一结点后，重新设置删除队列中唯一结点后，重新设置rear rear=front; return retvalue; else cout” 队列空队列空!”next-data

30、; else cout”队列空，无队头元素！队列空，无队头元素！”0 时重复（时重复（1），（），（2） （1）若）若N0，则将，则将 N % r 压入栈压入栈 s 中，执行（中，执行（2）；）； 若若N0，将栈，将栈 s 的内容依次出栈，算法结束。的内容依次出栈，算法结束。（2）用）用 N/r 代替代替 N61u算法描述算法描述 void conversion ( int N，int r ) SeqStack s; int x; while ( N ) s.Push (N % r ); N=N / r ; while (! s.IsEmpty ( ) x=s.Pop ( ) ; coutx

31、; /while /conversion62应用应用2：表达式求值：表达式求值u表达式表达式表达式由操作数（表达式由操作数（operand）、运算符（）、运算符（operator）和）和分界符（分界符（delimiter）组成）组成l操作数：变量或常数操作数：变量或常数l运算符：算术运算符、关系运算符、逻辑运算符运算符：算术运算符、关系运算符、逻辑运算符l分界符：括号分界符：括号表达式的表示方法表达式的表示方法l前缀表达式前缀表达式l中缀表达式中缀表达式l后缀表达式后缀表达式63u后缀表达式（逆波兰式）求值后缀表达式（逆波兰式）求值后缀表达式不含括号后缀表达式不含括号运算符放在两个操作数后面运

32、算符放在两个操作数后面例例l中缀表达式中缀表达式 2 + ( 3 * 8 4 ) / 5l后缀表达式后缀表达式 2 3 8 * 4 - 5 / +所有的求值计算皆按运算符出现的顺序，严格从左向所有的求值计算皆按运算符出现的顺序，严格从左向右进行右进行比中缀表达式的计算简单比中缀表达式的计算简单64算法思想算法思想l设一个栈；设一个栈；l顺序扫描后缀表达式的每一项，根据其类型做如下顺序扫描后缀表达式的每一项，根据其类型做如下处理：处理：p如果该项是操作数，则将其压入栈顶；如果该项是操作数，则将其压入栈顶；p如果该项是运算符如果该项是运算符 ，则连续从栈顶退出两个操，则连续从栈顶退出两个操作数作数

33、 x 和和 y，形成运算指令，形成运算指令 x y，并将结果重新，并将结果重新压入栈顶。压入栈顶。l表达式所有项扫描并处理完后（以符号表达式所有项扫描并处理完后（以符号“=”为结为结束），栈顶存放的就是计算结果。束），栈顶存放的就是计算结果。65栈栈输入输入操作序列操作序列 A B C D + E F / PushABCDC DPushPushPop, Pop, PushPushPop, Pop, PushB (C D)Pop, Pop, PushA+ B (C D)EFE/FPushPushPop, Pop, PushPop, Pop, PushA+B (C-D) E/F66u中缀表达式的计

34、算中缀表达式的计算中缀表达式的计算次序中缀表达式的计算次序l根据运算符优先级由高到低的顺序进行运算根据运算符优先级由高到低的顺序进行运算l有括号出现时先算括号内的，后算括号外的，多层有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行括号，由内向外进行l乘方连续出现时先算最右面的乘方连续出现时先算最右面的计算方法计算方法1l按中缀表达式的顺序计算（本书）按中缀表达式的顺序计算（本书）计算方法计算方法2l先将中缀表达式转换为后缀表达式先将中缀表达式转换为后缀表达式l再进行后缀表达式求值再进行后缀表达式求值67计算方法计算方法1l根据上述三条运算规则，在运算的每一步中，对任根据上述三条运

35、算规则，在运算的每一步中，对任意相继出现的运算符意相继出现的运算符 1和和 2，都要比较优先关系，都要比较优先关系l运算符间的优先关系见下表运算符间的优先关系见下表 2 1 * * / + / + ( )( ) # # * * / / + + （ ） # # = = =68l算法思想算法思想p设定两栈：操作数栈设定两栈：操作数栈 OPND，运算符栈，运算符栈 OPTRp栈初始化：设操作数栈栈初始化：设操作数栈 OPND 为空；运算符栈为空；运算符栈 OPTR 的栈底元素为表达式起始符的栈底元素为表达式起始符 #；p依次读入字符：是操作数则入依次读入字符：是操作数则入OPND栈，是运算符则栈，是

36、运算符则要判断（设要判断（设OPTR 的栈顶元素为的栈顶元素为 1 ，当前读入的运，当前读入的运算符为算符为 2 ）： 1）if 1 2，则退栈、计算，结果压入，则退栈、计算，结果压入 OPND栈；栈；p重复，直至读入字符和重复，直至读入字符和OPTR的栈顶元素均为的栈顶元素均为 #，此时此时OPND 的栈顶即为计算结果的栈顶即为计算结果69OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*, (37-2)#Push(opnd,7)#,*, (3,7-2)#Push(o

37、ptr,-)#,*, (, -3,72)#Push(opnd,2)#,*, (, -3,7,2)#Operate(7-2)#,*, (3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)70l算法描述算法描述void EvaluateExpression( OperandType &result) /s1为操作对象栈，为操作对象栈，s2为运算符栈，为运算符栈，OP为运算符集合为运算符集合 SeqStack s1,s2; s2.Push(#); c=getchar(); while (c!=#) & (s2.GetTop()!=#)

38、if (!In(c,OP) s1.Push(c); c=getchar(); 71 else switch (compare (s2.GetTop(), c) case : temat=s2.Pop(); b=s1.Pop(); a=s1.Pop(); result= Operate(a,temat,b); s1.Push(result); c=getchar();break; /switch /while result=s1.GetTop(); /EvaluateExpression72计算方法计算方法2将中缀表达式转换成后缀表达式将中缀表达式转换成后缀表达式l设置一个栈，栈底元素为表达式起

39、始符设置一个栈，栈底元素为表达式起始符 #；l依次读入中缀表达式的每一字符，是操作数则直接依次读入中缀表达式的每一字符，是操作数则直接输出，是运算符则要判断（设栈顶元素为输出，是运算符则要判断（设栈顶元素为 1 ，当前，当前读入的运算符为读入的运算符为 2 ）：1）if 1 2， 则退栈，并输出；则退栈，并输出；3）if 1= 2 且不为且不为#， 则退栈，但不输出，若退则退栈，但不输出，若退出的是出的是 ( 则读入下一字符则读入下一字符 ；l重复，直至读入字符和栈顶元素均为重复，直至读入字符和栈顶元素均为 #，算法结，算法结束，此时输出序列即为后缀表达式束，此时输出序列即为后缀表达式73应用

40、应用3：迷宫求解问题：迷宫求解问题 入口入口出口出口74u基本思想基本思想从入口出发，沿某一方向向前探索从入口出发，沿某一方向向前探索l若当前位置若当前位置“可通可通”，则纳入路径，继续前进；，则纳入路径，继续前进；l若当前位置若当前位置“不可通不可通”，则换方向继续探索，则换方向继续探索;若四周若四周“均无通路均无通路”，则沿原路退回到前一位置，换，则沿原路退回到前一位置，换方向继续探索方向继续探索75u迷宫求解问题的迷宫求解问题的递归递归算法算法算法中用到的数据结构算法中用到的数据结构lint Mazem+2p+2：表示迷宫：表示迷宫pm表示行数，表示行数，p表示列数表示列数p第第0、m+

41、1行，第行，第0、p+1 列是迷宫的围墙列是迷宫的围墙pMazeij=1时，表示该位置是墙壁，不能通行时，表示该位置是墙壁，不能通行Mazeij=0时，表示该位置是通路时，表示该位置是通路lint markm+2p+2：标志矩阵：标志矩阵p初始为初始为0，当某一位置，当某一位置ij走过时，置走过时，置 markij=176loffsets move4：表示方向：表示方向Struct offsets int a, b; char *d; moveq.dmoveq.amoveq.bE(东东)01S(南南)10W(西西)0-1N(北北)-10N(北北)i-1, jW(西西)i, j-1当前位置当前位

42、置i, jE(东东)i, j+1S(南南) i+1, j77递归函数递归函数int SeekPath (int x, int y) int i,g,h; char *d; if ( x=m & y=p ) return 1; for (i=0; i4; i+) g=x+movei.a; h=y+movei.b; d=movei.dir; if ( !Mazegh & !markgh ) markgh=1; if ( SeekPath(g,h) ) cout“(“g“,”h“),”“Direction”dir“,”; return 1; if ( x=1&y=1 ) cout“no pathvin Maze”endl; return 0;78递归函数的主程序递归函数的主程序const