编程中的基本数据结构与算法思想( 二 ) _算法

在C++中，函数不能嵌套定义，但可以嵌套调用，在函数调用时，编译器需要确保在逐级调用后能够回归到最初的调用点，编译器会隐式实现一个堆栈，用来保存每一级函数调用时的函数返回地址和局部变量，依次入栈和出栈。
C++也支持递归函数的递归调用，同样是由编译器隐式地实现了一个堆栈。
5 深度搜索与广度搜索如果将上述的问题稍微扩展一点，要从源点到目标点，中间的节点可能有多个分叉，这样的问题可以用一个树或图来描述。

文章插图

而探路的方法可以分为两种，一种是深度优先搜索（下一点、下一点……回溯……），一种是广度优先搜索（下一点的全部分叉、下一点的全部分叉……）：
5.1 深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形：

1）把根节点压入栈中。
2）每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
3）找到所要找的元素时结束程序。
4）如果遍历整个树还没有找到，结束程序。

文章插图

5.2 广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：

1）把根节点放到队列的末尾。
2）每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。（取出的元素也可以保存到一个队列）
3）找到所要找的元素时结束程序。
4）如果遍历整个树还没有找到，结束程序。

文章插图

广度优先搜索相对于深度优先搜索，因为是逐层探索的，可以确保以较少的点到达目标点，缺点是存储量较大。
6 递归算法递归就是某个函数直接或间接的调用自身。
语法形式上: 在一个函数的运行过程中, 调用这个函数自己：

直接调用: 在fun()中直接执行fun()；
间接调用: 在fun1()中执行fun2(); 在fun2()中又执行fun1() ；

问题的求解过程是划分成许多相同性质的子问题的求解，而小问题的求解过程可以很容易的求出。这些子问题的解就构成里原问题的解。
待求解问题的解可以描述为输入变量x的函数f(x) 。
通过寻找函数g( ) ，使得f(x) = g(f(x-1)) 。
且已知f(0)的值, 就可以通过f(0)和g( )求出f(x)的值。
扩展到多个输入变量x, y, z等, x-1也可以推广到 x - x1 , 只要递归朝着 “出口” 的方向即可。
递归算法分解出的子问题与原问题之间是纵向的, 同类的关系（枚举分解出的子问题之间是横向的, 同类的关系）。
递归的三个要点:

递归式：如何将原问题划分成子问题；
递归出口：递归终止的条件, 即最小子问题的求解,可以允许多个出口；
界函数：问题规模变化的函数, 它保证递归的规模向出口条件靠拢。

如一个求阶乘的递归程序，给定n, 求阶乘n!

文章插图

阶乘的栈：

文章插图

二分搜索的递归实现：
int binarySearchRecursion(int arr[], int findData, int start, int end){ if(arr==NULL || start>end)return -1;int mid = start+(end-start)/2;if(arr[mid] == findData)return mid;else if(findData < arr[mid])binarySearchRecursion(arr, findData, start, mid-1);elsebinarySearchRecursion(arr, findData, mid+1, end);7 归并排序归并排序（merge sort）是建立在归并操作上的一种有效的排序算法。该算法是分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并（2-way or binary merges sort）。