数据结构与算法分析(C++)(一)

1.前言

这段时间接二连三有人询问C++推荐的书籍,我个人感觉自己的C++编程其实也稀疏平常,给人指导实在不敢当,就推荐了我自己决定不错的两本书:《C++ Primer》 和 《Data Structures and Algorithm Analysis in C++》,前者可以作为入门的教材,内容详实而且很用代码用例,我当年学习的时候就受益颇多,后者更像一本进阶的书,我手头上只有英文的原本,虽然英语水平一般,但是读起来竟然有种酣畅淋漓的快感,因此我想坚持把这本书翻译一遍,一方面是为了让自己理解地更深入,如果仅仅是通读一遍,很多细节描述和分析,多半都会被我忽略掉,而总结呈现出来,就会用心颇多;另一方面也是希望如果有人对这本书或者对C++这门编程语言有深入的了解,可以一起探讨,文章中的一些计算机专业词汇,有些我也是初识,多有困顿,如有翻译不当或者理解偏差还希望大家指出不足。

至于翻译的方式,我决定先跳过前面的简介和简单的数学公式推导证明,这部分是基础性的简介,涉及的问题不深也很容易理解,跳过后对后面的影响并不太大,因此就从第1章的第3小节开始,如果后面把整本数翻译出来,会考虑把前面的两小节补上以求完整,这里也是给自己立个flag,希望自己能坚持下去,每天抽出一些琐碎的时间完成。

书籍链接:Data Structures and Algorithm Analysis in C++

1.1 递归简介(一)

A function that is defined in terms of itself is called recusive.

大多数我们熟悉的数学函数都表达为非常简洁的公式,例如我们可以温度的华氏温标转换为摄氏温标:
$$C=5(F-32)/9$$

根据这个公式,我们能够很轻松写一个C++函数,排除掉相关的声明和括号,这样的一行公式可以转换为一行C++代码。

万物皆有例外,数学公式的定义有时候也会不走寻常路。例如,我们定一个函数$f$,定义域为非负整数,且满足$f(0)=0$, $f(x)=2f(x-1)+x^2$。 从这个定义中,我们可以轻易知道:

$$f(1) = 1, \ f(2) = 6, \ f(3) = 21, … $$

像这样,一个函数以自己本身的形式定义被称为递归。 C++允许函数递归。 值得一说的是,C++ 所提供的仅仅是递归的思想,并非所有的递归函数通过C++实现是高效的或者正确的。 关键是这种递归函数$f$ 能够通过寥寥几行表述,就像那些非递归的函数一样(例如,上面的温度转换函数)。

下面的一段代码展示了函数$f$的C++ 实现:

1
2
3
4
5
6
7
int f( int x )
{
if( x == 0 )
return 0;
else
return 2 * f( x - 1 ) + x * x;
}

其中,第3、4行被称为Base case (个人觉得翻译成基础/基准条件比较恰当,好比一个基准点,其后面定义域内函数的值,都可以通过递归到该基准点,而到了该基准点后递归就停止),它对应的函数值是直接已知的,而不是通过递归过程得到。 没有基准条件$f(0)=0$,仅仅定义一个函数$f(x)=2*f(x-1)+x^2$ 是没有意义的,也就是说C++ 函数不能接受就没有Base case 的递归!上述代码中的第6行,就是调用递归的过程。

这里有几条关于递归的重要而且很容易使人困惑的点。常见的问题是:这难道不仅仅是一个循环的逻辑吗?答案是否,我们以一个函数本身的形式定义了它,而不是以一个函数本身的形式定义了一个特殊的实例。 换句话说,通过计算$f(5)$求$f(5)$的值是一个循环。通过计算$f(4)$求$f(5)$并不是一个循环,当然除非,$f(4)$最终是通过$f(5)$计算得到。 关于递归实现的具体方式以及缘由,后面的章节(第3章)将会正式解答,这里仅仅给出一个简单的描述。

实际上递归调用的处理过程与其它处理过程并无差异。 如果我们输入值 4 到函数$f$,则第6行会计算$2*f(3)+4*4$,那么就会调用$f(3)$,而它会计算$2*f(2)+3*3$, 接着又会调用$f(2)$,而它会计算$2*f(1)+2*2$,接着它又会调用$f(1)$,而它会计算$2*f(0)+1*1$,此时,$f(0)$的值必须要被计算,因为它是一个Base case,而且我们已经预先知道$f(0)=0$。 这使得计算$f(1)$可以完成,即$f(1)=1$,接着$f(2)$, $f(3)$ 和 $f(4)$都会被分别计算出来:

1
2
3
4
5
6
7
8
9
f(4) = 2*f(3) + 4*4
= 2*(2*f(2) + 3*3) + 4*4
= 2*(2*(2*f(1) + 2*2) + 3*3) + 4*4
= 2*(2*(2*(2*f(0) + 1*1) + 2*2) + 3*3) + 4*4
= 2*(2*(2*(2*0 + 1*1) + 2*2) + 3*3) + 4*4
= 2*(2*(2*1 + 2*2)+ 3*3) + 4*4
= 2*(2*6 + 3*3) + 4*4
= 2*21 + 4*4
= 58

该过程中,所有的记录(bookkeeping)都需要与等待函数调用(指那些已经启动但是还在等待递归调用完成)保持联络(此处有待完善)。 如果,我们想尝试调用$f(-1)$ 将会导致计算$f(-2)$,$f(-3)$等,由于这样递归下去永远都不会达到一个基准条件,那么程序就不能完成计算。

递归的强大最明显体现在,它提供了一种以有限陈述定义无限目标集合的可能性。通过这种方式,一个无限次的计算可以被描述为有限次的递归程序,即使程序本身不包含明确的迭代次数。
The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

下面一段代码,给出一个错误的递归:

1
2
3
4
5
6
7
int bad( int n )
{
if( n == 0 )
return 0;
else
return bad( n/3 + 1 ) + n - 1;
}

$bad(1)$ 是通过第6行计算,但是还是需要调用$bad(1)$,很明显,代码没有给出$bad(1)$的任何定义,因此,计算机将会重复地调用$bad(1)$试图尝试得到它的值,最终,记录系统将会运行到内存溢出,程序也会被终结掉。一般来讲,我们认为这种函数的特例不能得到结果,除了被正确定义外。对于上面的$bad$函数,由于$bad(2)$会调用$bad(1)$,所以$bad(2)$也不能被计算,同样,$bad(3)$,$bad(4)$等,都不能被计算出来,事实上,这段代码对于任何非负整数,除了0以外,都不能得到解算。因此,对于递归程序而言,不能存在这样所谓的“特例”。

上述的思考,可以推到出两条递归的两条基本准则:

  • Base case: 递归必须具有一些不需要通过递归就能得到结果的基准条件;
  • Making progress:对于基准条件外的情形,递归总是能够朝着一个基准条件“推进”。