程序员数据结构笔记（四）

来源：软件水平考试发布时间：2012-11-05 软件水平考试视频评论

枚举:
　　背包问题:
　　枚举策略：1)可能的方案：2^N
　　　　　　　2)对每一方案进行判断.

　　枚举法一般流程：
　　　　while(还有其他可能方案)
　　　　{ 按某种顺序可难方案;
　　　　　检验方案;
　　　　　if(方案为解)
　　　　　　保存方案;
　　　　　}
　　　　}
　　枚举策略:
　　例：把所有排列枚举出来 P6=6!.
　　　Min:123456
　　　Max:654321
　　　a1a2a3a4a5a6=>?(下一排列)=>?
　　　比如:312654的下和种情况=>314256

递归
　　递归算法通常具有这样的特征：为求解规模为N的问题，设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出题目所需的解。而这些规模较小的问题也采用同样的方法分解成规模更小的问题，通过规模更小的问题构造出规模校小的问题的解，如此不断的反复分解和综合，总能分解到最简单的能直接得到解的情况。
　　因此,在解递归算法的题目时,要注意以下几点:
　　1) 找到递归调用的结束条件或继续递归调用条件.
　　2) 想方设法将处理对象的规模缩小或元素减少.
　　3) 由于递归调用可理解为并列同名函数的多次调用,而函数调用的原则是一层一层调用,一层一层返回.因此,还要注意理解调用返回后的下一个语句的作用.在一些简单的递归算法中,往往不需要考虑递调用返回后的语句处理.而在一些复杂的递归算法中,则需要考虑递归调用返回后的语句处理和进一步的递归调用.
　　4) 在读递归程序或编写递归程序时,必须要牢记递归函数的作用,这样便于理解整个函数的功能和知道哪儿需要写上递归调用语句.当然,在解递归算法的题目时,也需要分清递归函数中的内部变量和外部变量.
　　表现形式:
　　●定义是递归的(二叉树,二叉排序树)
　　●存储结构是递归的(二叉树,链表,数组)
　　●由前两种形式得出的算法是递归的
　　一般流程: function(variable list(规模为N))
　　　{ if(规模小,解已知) return 解;
　　　　else {
　　　　　把问题分成若干个部分;
　　　　　某些部分可直接得到解;
　　　　　而另一部分(规模为N-1)的解递归得到;
　　　　}
　　}
　　例1：求一个链表里的最大元素.
　　大家有没想过这个问题用递归来做呢?
　　非递归方法大家应该都会哦?
　　　　Max(nodetype *h) {
　　　　　nodetype *p;
　　　　　nodetype *q; //存放含最大值的结点
　　　　　Int max=0;
　　　　　P=h;
　　　　　While(p!=NULL){
　　　　　　if (max<p->data) {
　　　　　　　max=p->data;
　　　　　　　q=p;
　　　　　　}
　　　　　　p=p->next;
　　　　　}
　　　　　return q;
　　　　}
　　下面真经来了,嘻嘻嘻~~~
　　　　*max(nodetype *h) {
　　　　　nodetype *temp;
　　　　　temp=max(h->next);
　　　　　if(h->data>temp->data)
　　　　　　return h;
　　　　　else
　　　　　　return temp;
　　　　}
　　大家有空想想下面这个算法：求链表所有数据的平均值(我也没试过)，不许偷懒，用递归试试哦!
　　递归程序员考试题目类型：1)就是链表的某些操作(比如上面的求平均值)
　　　　　　　　　　　　　　2)二叉树(遍历等)

视频学习

我考网版权与免责声明

① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件，版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源：我考网"，违者本网将依法追究责任；

② 本网部分稿件来源于网络，任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益，应该及时向我考网书面反馈，并提供身份证明、权属证明及详细侵权情况证明，我考网在收到上述法律文件后，将会尽快移除被控侵权内容。