主题

主题

 
   

关于一个递归+一个参数的DFS手写栈的笔记

一个递归+一个参数的DFS很常用到。不仅仅是在搜索中,主要还有类似于“树的遍历”这样的问题,可能面临着爆栈的危险(一条链)。虽然考试中还是不会,但是在平时做题的时候可能会遇到,于是需要解决这样一个问题。

假设我们有一个程序:

https://code.csdn.net/snippets/2175254

像这个一样。现在我们需要把这个程序转换为手写栈。

我们研究一下这个程序的运行步骤:

A(1);

X(1);//X(1) is accepted by Y(1)

B(1);

A(2);

X(2);//X(2) is accepted by Y(2)

A(3);

X(3);//X(3) is not accepted by Y(3)

D(3);

C(2);

Z(2);//Z(2) is accepted by Y(2)

B(2);

A(4);

X(4);//X(4) is not accepted by Y(4)

D(4);

C(2);

Z(2);//Z(2) is not accepted by Y(2)

D(2);

C(1);

Z(1);//Z(1) is not accepted by Y(1);

D(1);

(不知道 be accepted by是不是正确的来着?)

于是我们在我们的手写栈程序中:

先把1入栈,即Pushin(1),之后for(;;)来操作这个栈。

在for(;;)的第一部分,应该是A(top)。但是考虑到之后弹栈之后重新回到for(;;)的第一部分,不能重复执行A(top),于是我们需要一个判重数组,比方说Adone[],来判断当前是否要执行A(top)。

接下来执行的是X(top)。但是同样考虑到之后弹栈之后重新回到for(;;)的这一部分,不能重复执行X(top),于是我们同样需要一个判重数组,比方说Xdone[],来判断当前应该是执行X(top)还是Z(top)。

接下来我们要判断条件Y(top)是否满足。如果是,我们就执行B(top),之后把下一个元素进栈,即Pushin(next),否则我们应该先D(top),之后Pushout(),再执行C(top)。

如何结束程序?我们发现,执行完D(1)之后,1就被Pushout了。这个时候我们应该结束程序。

代码如下:

https://code.csdn.net/snippets/2175584

为了减短代码与长度,减小空间消耗,我们可以——

  1. 把A与X放到同一个部分。

 
 
评论