非递归方法大家应该都会哦? Max(nodetype *h) { nodetype *p;
nodetype *q; //存放含最大值的结点 Int max=0; P=h;
While(p!=NULL){
if (max
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)二叉树(遍历等)
例2.判断数组元素是否递增
int jidge(int a[],int n) { if(n==1) return 1; else
if(a[0]>a[1]) return 0;
else return jidge(a+1,n-1); }
例3.求二叉树的高度(根据二叉树的递归性质:(左子树)根(右子树)) int depth(nodetype *root) { if(root==NULL) return 0; else {
h1=depth(root->lch); h2=depth(root->rch);
return max(h1,h2)+1; } }
自己想想求二叉树结点个数(与上例类似)
例4.已知中序遍历和后序遍历,求二叉树. 设一二叉树的:
中序 S:E D F B A G J H C I ^start1 ^j ^end1 后序 T:E F D B J H G I C A ^start2 ^end2 node *create(char *s,char *t, int start1,int start2,int end1,int end2)
{ if (start1>end1) return NULL; //回归条件 root=(node *)malloc(sizeof(node)); root->data=t[end2];
找到S中T[end2]的位置为 j
root->lch=create(S,T,s1,j-1,start1,j+start2-start1-1); root->rch=create(S,T,j+1,end1,j+start2-start1,end2-1); return root; }
例5.组合问题
n 个数: (1,2,3,4,?n)求从中取r个数的所有组合. 设n=5,r=3;
递归思想：先固定一位 5 (从另四个数当中选二个) 5,4 (从另三个数当中选一个) 5,4,3 (从另二个数当中选零个) 即：n-2个数中取r-2个数的所有组合 ? 程序:
void combire(int n,int r) { for(k=n;k>=n+r-1;k--) { a[r]=k;
if(r==0) 打印a数组(表示找到一个解); else combire(n-1,r-1); } }
第五天
回溯法:
回溯跟递归都是程序员考试里常出现的问题,大家必须掌握! 回溯法的有关概念:
1) 解答树:叶子结点可能是解,对结点进行后序遍历. 2) 搜索与回溯
五个数中任选三个的解答树(解肯定有三层,至叶子结点): ROOT 虚根
/ / | \\ \\ 1 2 3 4 5 / | | \\ / | \\ /\\ | 2 3 4 5 3 4 5 4 5 5 /|\\ /\\ | /\\ | | 3 4 5 4 5 5 4 5 5 5
回溯算法实现中的技巧:栈 要搞清回溯算法，先举一个(中序遍历二叉树的非递归算法)来说明栈在非递归中所起的作用。
A 过程：push()->push()->push()->push()栈内结果:ABDE(E为叶子,结束进栈)
/ \\ pop() ABD(E无右孩子,出栈) B C pop() AB(D无右孩子,出栈) /\\ pop() A(B有右孩子,右孩子进栈) D F . . / /\\ . . E G H . . / . .
I 最后结果： EDBGFIHAC 简单算法: ?
if(r!=NULL) //树不空 { while(r!=NULL) { push(s,r);
r=r->lch; //一直向左孩子前进 }
while(!empty(s)) // 栈非空,出栈 { p=pop(s);
printf(p->data);
p=p->rch; //向右孩子前进 while(p!=NULL) { push(s,p);
p=p->lch; //右孩子进栈 }
}
} //这就是传说中的回溯,嘻嘻??没吓着你吧
5选3问题算法: 思想: 进栈:搜索 出栈:回溯
边建树(进栈)边遍历(出栈) 基本流程:
太复杂了,再说我不太喜欢用WORD画图（有损形象），以后再整理! 程序: n=5;r=3 ??
init(s) //初始化栈 push(s,1) //根进栈
while(s.top 判断该\解\是否为解. x=pop(s); //保留x,判断是否为最大值n,如果是n,则出栈 while(x==n) x=pop(s); push(s,x+1); while(s.top 背包问题: TW=20 , w[5]={6,10,7,5,8} 解的条件:1) 该解答树的叶子结点 2) 重量最大 解答树如下： ROOT / | | | \\ 6 10 7 5 8 / | | \\ / | \\ / \\ | 10 7 5 8 7 5 8 5 8 8 | | | 5 8 8 程序: temp_w 表示栈中重量和 ? init(s); //初始化栈 i=0; While(w[i]>TW) i++; If(i==n) Return -1; //无解 Else { Push(s,i); Temp_w=w[i]; i++; while(i max_w=0; while(!empty(s)) { if(max_w while(x temp_w=temp_w+w[x]; x++; while(x 请大家思考:四色地图问题,比如给中国地图涂色,有四种颜色,每个省选一种颜色,相邻的省不能取同样的颜色.不许偷懒，不能选人口不多于xxxxＷ的\大国\哦!如果真的有一天台湾独立了，下场就是这样了，一种颜色就打发了，不过台湾的程序员们赚到了，省事！呵呵。 贪婪法: 不求最优解,速度快(以精确度换速度) 例:哈夫曼树,最小生成树 装箱问题: 有n个物品,重量分别为w[n]，要把这n个物品装入载重为TW的集装箱内,需要几个集装箱? 思想1:对n个物品排序 拿出第1个集装箱，从大到小判断能不能放。 2 ? 3 ?