递归思想及应用续(二十九)
今天我们继续来学习递归,下来我们先来回顾下函数的调用过程:在程序运行后有一个特殊的内存区供函数调用使用。那么这个内存区有什么用呢?1、用于保存函数中的实参,局部变量,临时变量等;2、从起始地址开始往一个方向增长(如:高地址 --> 低地址);3、有一个专用“指针”标识当前已使用内存的“顶部”。
创新互联主营澜沧网站建设的网络公司,主营网站建设方案,成都app开发,澜沧h5小程序定制开发搭建,澜沧网站营销推广欢迎澜沧等地区企业咨询
那么程序中的栈区,就是一段特殊的专用内存区。如下图所示
下来我们来看一个示例:逆序打印单链表中的偶数结点。如下所示
下来我们来看看具体源码是怎么实现的,如下
#include#include #include "DTString.h" #include "LinkList.h" using namespace std; using namespace DTLib; struct Node { int value; Node* next; }; Node* create_list(int v, int len) { Node* ret = NULL; Node* slider = NULL; for(int i=0; i value = v++; n->next = NULL; if( slider == NULL ) { slider = n; ret = n; } else { slider->next = n; slider = n; } } return ret; } void destory_list(Node* list) { while( list ) { Node* del = list; list = list->next; delete del; } } void print_list(Node* list) { while( list ) { cout << list->value << "->"; list = list->next; } cout << "NULL" << endl; } void r_print_even(Node* list) { if( list != NULL ) { r_print_even(list->next); if( (list->value % 2) == 0) { cout << list->value << endl; } } } int main() { Node* list = create_list(2, 5); print_list(list); r_print_even(list); return 0; }
我们来看看运行结果
我们看到已经实现了这个功能。
下来我们来看看著名的“八皇后”问题,那么什么是八皇后问题呢?在一个 8×8 的国际棋盘上,有 8 个皇后,每个皇后占一格;要求皇后间不会出现相互“***”的现象(不能有两个皇后处于同一行、同一列或同一对角线上)。
那么实现的关键是什么呢?我们先来看看关键的数据结构定义:
1、棋盘,它便是用一个二维数组(10*10),0表示位置为空,1表示皇后,2表示边界;
2、位置,struct Pos。
struct Pos
{
int x;
int y;
}
3、方向:
水平:(-1,0),(1,0)
垂直:(0,-1),(0,1)
对角线:(-1,1),(-1,-1),(1,-1),(1,1)
其中的算法思路:
1、初始化:j = 1
2、初始化:i = 1
3、从第 j 行开始,恢复 i 的有效值(通过函数调用栈进行回溯),判断第 i 个位置
a. 位置 i 可放入皇后:标记位置(i,j),j++,转步骤 2
b. 位置 i 不可放入皇后:i++,转步骤 a
c. 当 i > 8 时,j--,转步骤 3
-- 结束:第 8 行有位置可放入皇后。
下来我们来看看具体的源码实现,如下
#include#include #include "DTString.h" #include "LinkList.h" using namespace std; using namespace DTLib; template < int SIZE > class QueueSolution : public Object { protected: enum { N = SIZE + 2 }; struct Pos : public Object { Pos(int px = 0, int py = 0) : x(px), y(py) { } int x; int y; }; int m_chessboard[N][N]; Pos m_direction[3]; LinkList m_solution; int m_count; void init() { m_count = 0; for(int i=0; i qs; qs.run(); return 0; }
我们来看看运行结果
我们看到总共有 92 种解法。我们来看看四皇后,看看有多少种解法
我们看到总共有 2 种解法,如上图所示。通过今天对递归的学习,总结如下:1、程序运行后的栈存储区专供函数调用使用;2、栈存储区用于保存实参,局部变量,临时变量等;3、利用栈存储区能够方便的实现回溯算法;4、八皇后问题是栈回溯的经典应用。
网页名称:递归思想及应用续(二十九)
转载来源:http://myzitong.com/article/pejccj.html