2010年下半年初级软考辅导:程序员数据结构笔记（四）_计算机_软件水平考试_复习指导

枚举:
　　背包问题:
　　枚举策略：1)可能的方案：2N
　　2)对每一方案进行判断.
　　枚举法一般流程：
　　while
　　}
　　枚举策略:
　　例：把所有排列枚举出来P6=6!.
　　Min:123456
　　Max:654321
　　a1a2a3a4a5a6=>?=>?
　　比如:312654的下和种情况=>314256
　　递归
　　递归算法通常具有这样的特征：为求解规模为N的问题，设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出题目所需的解。而这些规模较小的问题也采用同样的方法分解成规模更小的问题，通过规模更小的问题构造出规模校小的问题的解，如此不断的反复分解和综合，总能分解到最简单的能直接得到解的情况。
　　因此，在解递归算法的题目时，要注意以下几点:
　　1)找到递归调用的结束条件或继续递归调用条件.
　　2)想方设法将处理对象的规模缩小或元素减少.
　　3)由于递归调用可理解为并列同名函数的多次调用，而函数调用的原则是一层一层调用，一层一层返回.因此，还要注意理解调用返回后的下一个语句的作用.在一些简单的递归算法中，往往不需要考虑递调用返回后的语句处理.而在一些复杂的递归算法中，则需要考虑递归调用返回后的语句处理和进一步的递归调用.
　　4)在读递归程序或编写递归程序时，必须要牢记递归函数的作用，这样便于理解整个函数的功能和知道哪儿需要写上递归调用语句.当然，在解递归算法的题目时，也需要分清递归函数中的内部变量和外部变量.
　　表现形式:
　　定义是递归的
　　存储结构是递归的
　　由前两种形式得出的算法是递归的
　　一般流程:function)
　　}
　　例1：求一个链表里的最大元素.
　　大家有没想过这个问题用递归来做呢?
　　非递归方法大家应该都会哦?
　　Max
　　p=p->next;
　　}
　　returnq;
　　}
　　下面真经来了，嘻嘻嘻~~~
　　max
　　大家有空想想下面这个算法：求链表所有数据的平均值，不许偷懒，用递归试试哦!
　　递归程序员考试题目类型：1)就是链表的某些操作
　　2)二叉树
　　例2.判断数组元素是否递增
　　intjidge
　　例3.求二叉树的高度根)
　　intdepth
　　}
　　自己想想求二叉树结点个数
　　例4.已知中序遍历和后序遍历，求二叉树.
　　设一二叉树的:
　　中序S:EDFBAGJHCI
　　^start1^j^end1
　　后序T:EFDBJHGICA
　　^start2^end2
　　nodecreate
　　例5.组合问题
　　n个数:求从中取r个数的所有组合.
　　设n=5，r=3;
　　递归思想：先固定一位5
　　5，4
　　5，4，3
　　即：n-2个数中取r-2个数的所有组合
　　…
　　程序:
　　voidcombire
　　}