2014年考研数据结构辅导(16)
专业课
时间: 2019-03-09 12:17:12
作者: 匿名
尾递归和单向递归的消除不需要借用栈
单向递归和尾递归可直接用迭代实现其非递归过程
其他情形必须借助栈实现非递归过程。
证明:若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着i i 若Pi>Pj 说明大的数先于小的数出栈,那么在Pi出栈前Pj一定在栈中 证明:1)j 2)i 3)i 而Pi是最先出栈的那么在Pi为栈顶的时候,Pj和Pk一定都同时被压入栈中,那么就与1矛盾了,1要求Pj要在Pk入栈前出栈,而此时Pk Pj都在栈中所以假设不成立。
猜你喜欢
-
- 03-082017年西医综合考试大纲:内科学考查内容
- 03-082017年西医综合考试大纲:生物化学考查内容
- 03-082017年西医综合考试大纲:生理学考查内容
- 03-082017西医临综考纲与2016对比考点一览汇总
- 03-082017西医综合考试大纲公布
- 03-082017西医临综考纲与2016对比考点一览【生理学】
- 03-082017西医临综考纲与2016对比考点一览【外科学】
- 03-082017西医临综考纲与2016对比考点一览【内科学】
- 03-082017西医临综考纲与2016对比考点一览【生物化学】
- 03-082017西医临综考纲与2016对比考点一览【病理学】