大学士考试网

考研动态 考研英语 考研政治 考研数学 专业课 模拟试题 历年真题

2014年考研数据结构辅导(16)

专业课  时间: 2019-03-09 12:17:12  作者: 匿名 

尾递归和单向递归的消除不需要借用栈

单向递归和尾递归可直接用迭代实现其非递归过程

其他情形必须借助栈实现非递归过程。

证明:若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着i

   i

   若Pi>Pj 说明大的数先于小的数出栈,那么在Pi出栈前Pj一定在栈中

证明:1)j

   2)iPk 说明Pi出栈前,Pk在栈中

   3)iPj 说明Pi出栈前Pj在栈中

   而Pi是最先出栈的那么在Pi为栈顶的时候,Pj和Pk一定都同时被压入栈中,那么就与1矛盾了,1要求Pj要在Pk入栈前出栈,而此时Pk Pj都在栈中所以假设不成立。

猜你喜欢

精选专题