flying in the dark!
真想不到,第一次上课竟然会是"9.11"事件纪念日.美国竟然还是不改老毛病,伊拉克战争死了多少平民百姓啊?!!!在此请先为死难者默哀3分钟,老美如果再这样多管闲事下去,上帝会二度惩罚美国人的啊！ 能听到周SIR讲课真的挺开心的,我觉得他讲课比某些高程(高级工程师)还深动[转载时注：此处应该是 生动](当然,他的数据结构水平应该不亚于高程),为了考中程,上学期的<算法分析>选修课我也去揍了揍热闹.可惜由于SARS的关系,课只上了将近一半就停了.可以说我报程序员的原因就是因为有周SIR开导我们,听他的课真的是一种享受,不像大学里的某些人,水平不怎么高还在这里作威作福. 好了,发了这么多劳骚,开始转入正题了. 读这文章的人想必都是想报考或者将考程序员的同志们吧!首先一点必须问问自己,我考程序员的目的到底是为了什么?如果你的答案是:"只是为了拿一本证书".那我劝你早点GIVE UP吧!那样学起来会很累,因为没有兴趣.如果你想加入程序员的行列,为将来开发打下坚实的基础,那就试着看完这一小篇读书笔记吧!或许会对你有所帮助. 有句话必须记住:程序员考试仅仅是为了检验自己学到的而已,仅此而已!我想这便是程序员考试的最终意义所在吧!有些事情更注重过程!
数据结构
知识: 1.数据结构中对象的定义,存储的表示及操作的实现. 2.线性:线性表、栈、队列、数组、字符串（广义表不考） 树：二叉树 集合：查找，排序 图(不考)能力： 分析，解决问题的能力过程： ● 确定问题的数据。 ● 确定数据间的关系。 ● 确定存储结构（顺序－数组、链表－指针） ● 确定算法 ● 编程 ● 算法评价（时间和空间复杂度，主要考时间复杂度）一、数组 1、存放于一个连续的空间 2、一维～多维数组的地址计算方式 已知data[0][0]的内存地址，且已知一个元素所占内存空间Ｓ求data[i][j]在内存中的地址。 公式：（add+(i*12+j)*S)(假设此数组为data[10][12]) 注意：起始地址不是data[0][0]时候的情况。起始地址为data[-3][8]和情况； 3、顺序表的定义 存储表示及相关操作 4、顺序表操作中时间复杂度估计 5、字符串的定义（字符串就是线性表），存储表示 模式匹配算法（简单和KMP（不考）） 6、特殊矩阵：存储方法（压缩存储（按行，按列）） 三对角：存储于一维数组 三对角问题：已知Aij能求出在一维数组中的下标k;已知下标k求Aij。 7、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分，不考）
算法 ● 数组中元素的原地逆置； 对换 ● 在顺序表中搜索值为X的元素； ● 在有序表中搜索值为X的元素；（折半查找） ● 在顺序表中的第i个位置插入元素X； ● 在顺序表中的第i个位置删除元素X； ● 两个有序表的合并；算法？ 线性表数据结构定义： Typedef struct { int data[max_size]; int len; }linear_list; ● 模式匹配 ● 字符串相加 ● 求子串 ● （i,j）<=>K 注意：不同矩阵所用的公式不同； ● 稀疏矩阵的转置（两种方式，后种为妙） ● 和数组有关的算法
例程：求两个长整数之和。 a=13056952168 b=87081299 数组: a[]:1 3 0 5 6 9 5 2 1 6 8 b[]:8 7 0 8 1 2 9 9 由于以上的结构不够直观(一般越是直观越容易解决) 将其改为: a[]:11 8 6 1 2 5 9 6 5 0 3 1 a[0]=11(位数) b[]: 8 9 9 2 1 8 0 7 8 0 0 0 b[0]=8 c进位 0 1 1 0 0 1 1 1 1 0 0 c[]:11 7 6 4 3 3 0 4 4 2 3 1 c[0]的值(C位数)由c[max_s+1]决定! 注意:在求C前应该将C(max_s+1)位赋0.否则为随机数; 较小的整数高位赋0. 算法:已知a,b两个长整数,结果:c=a+b; 总共相加次数: max_s=max(a[],b[]) 程序: for(i=1;i<=max_s;i++) { k=a[i]+b[i]+c[i]; c[i]=k%10; c[i+1]=k/10; } 求c位数: if(c[max_s+1]==0) c[0]=max_s; else c[0]=max_s+1; 以下代码是我编的(毕竟是初学者.不太简洁大家不要见怪!): /*两长整数相加*/ #include<stdio.h> #include<string.h> #define PRIN printf("\n"); int flag=0; /*a[0]>b[0]?1:0*/ /* max(a[],b[]) {}*/ change(char da[],char db[],int a[],int b[],int c[]) { int i; if(a[0]>b[0]) { for(i=1;i<=a[0];a[i]=da[a[0]-i]-'0',i++); /*a[0]-'0' so good!*/ for(i=1;i<=b[0];b[i]=db[b[0]-i]-'0',i++); for(i=b[0]+1;i<=a[0];b[i]=0,i++); for(i=1;i<=a[0]+1;c[i]=0,i++); flag=1; } else { for(i=1;i<=b[0];b[i]=db[b[0]-i]-'0',i++); for(i=1;i<=a[0];a[i]=da[a[0]-i]-'0',i++); for(i=a[0]+1;i<=b[0];a[i]=0,i++); for(i=1;i<=b[0]+1;c[i]=0,i++); } } add(int a[],int b[],int c[]) { int i,sum; if(flag==1) { for(i=1;i<=a[0];i++) { sum=a[i]+b[i]+c[i]; c[i+1]=sum/10; c[i]=sum%10; } if(c[a[0]+1]==0) c[0]=a[0]; else c[0]=a[0]+1; } else { for(i=1;i<=b[0];i++) { sum=a[i]+b[i]+c[i]; c[i+1]=sum/10; c[i]=sum%10; } if(c[b[0]+1]==0) c[0]=b[0]; else c[0]=b[0]+1; } } void print(int m[]) { int i; for(i=m[0];i>=1;i--) printf("%d,",m[i]); PRIN } main(){ int s; int a[20],b[20],c[20]; char da[]={"123456789"}; char db[]={"12344443"}; a[0]=strlen(da); b[0]=strlen(db); printf("a[0]=%d\t",a[0]); printf("b[0]=%d",b[0]); PRIN change(da,db,a,b,c); printf("flag=%d\n",flag); PRIN printf("-----------------\n"); if(flag==1) { print(a); PRIN s=abs(a[0]-b[0]); printf("+"); for(s=s*2-1;s>0;s--) printf(" "); print(b); PRIN } else { s=abs(a[0]-b[0]); printf("+"); for(s=s*2-1;s>0;s--) printf(" "); print(a); PRIN print(b); PRIN } add(a,b,c); printf("-----------------\n"); print(c); }时间复杂度计算: ● 确定基本操作 ● 计算基本操作次数 ● 选择T(n) ● lim(F(n)/T(n))=c ● 0(T(n))为时间复杂度 上例子的时间复杂度为O(max_s);
二:链表 1、知识点 ●逻辑次序与物理次序不一致存储方法； ●单链表的定义：术语（头结点、头指针等） ●注意带头结点的单链表与不带头结点的单链表区别。（程序员考试一般不考带头结点，因为稍难理解） ●插入、删除、遍历（p==NULL表明操作完成）等操作 ● 循环链表：定义，存储表示，操作； ● 双向链表：定义，存储方法，操作； 单链表和循环链表区别在最后一个指针域值不同。 2、操作 ●单链表：插入X，删除X，查找X，计算结点个数 ●单链表的逆置（中程曾考） head->NULL/p->a1/p->a2/p->a3/p……an/NULL 注：p代表指针;NULL/p代表头结点 ＝》 head->NULL/p->an/p->an-1/p->an-2/p……a1/NULL ●循环链表的操作：插入X，删除X，查找X，计算结点个数； 用p=head->next来判断一次计算结点个数完成； 程序段如下： k=0; do{ k++; p=p->next; }while(p!=head->next); ● 双向链表 ●多项式相加 ● 有序链表合并
转眼又过了一周了,前面一周里面我编了一些程序:链表,长整型数相加,三元组表转置以及一些简单的函数.其实有些算法想想是很简单,不过写起来还是需要一定耐心和C基础的,如果你自己觉得各算法都很懂了,不妨开机编编试试.或许会有一些新的发现与体会.栈和队列 1、知识点: ● 栈的定义:操作受限的线性表 ● 特点:后进先出 ● 栈的存储结构:顺序,链接 / push(s,d) ● 栈的基本操作: \ pop(s) 栈定义： struct { datatype data[max_num]; int top; }; ●队列定义 特点:先进先出 /入队列 in_queue(Q,x) ●队列的操作: \出队列 del_queue(Q) ●队列存储结构: 链队列: Typedef struct node{ Datatype data; Struct node *next; }NODE; Typedef struct { NODE *front; NODE *rear; }Queue; 顺序队列: struct { datatype data[max_num]; int front,rear; }; 问题: 队列ó线性表 假溢出<=循環队列 队列满，队列空条件一样<=浪费一个存储空间 递归 定义：问题规模为N的解依赖于小规模问题的解。问题的求解通过小规模问题的解得到。 包括二个步骤： 1） 递推 6!=>5!=>4!=>3!=>2!=>1!=>0! 2） 回归 720<=120<=24<=6 <=2 <=1 <=0 递归工作栈实现递归的机制。 2、有关算法： 1） 顺序，链表结构下的出栈，入栈 2） 循環，队列的入队列，出队列。 3） 链队列的入队列，出队列。 4） 表达式计算：后缀表达式 35+6/4368/+*- 中缀表达式 （3+5）/6-4*（3+6/8）
由于中缀比较难处理，计算机内一般先将中缀转换为后缀。 运算：碰到操作数，不运算，碰到操符，运算其前两个操作数。 中缀=>后缀 5) 迷宫问题 6) 线性链表的递归算法 一个链表=一个结点+一个链表 int fuction(NODE *p) { if(p==NULL) return 0; else return(function(p->next)); } 树与二叉树 一、 知识点: 1. 树的定义: data_struct(D,R); 其中:D中有一个根,把D和出度去掉,可以分成M个部分. D1,D2,D3,D4,D5…DM R1,R2,R3,R4,R5…RM 而子树Ri形成树. 1) 递归定义 高度
--0
--1
--1
--2
--2
此树的高度为2
2.二叉树定义: 结点个数>=0 . 3. 术语:左右孩子,双亲,子树,度,高度等概念. 4. 二叉树的性质 ●层次为I的二叉树 I层结点 2I 个 ●高度为H的二叉树结点 2H+1-1个 ●H(点)=E(边)+1 ●个数为N的完全二叉树高度为|_LOG2n_| ●完全二叉树结点编号:从上到下,从左到右.
二叉树的存储结构: 1) 扩展成为完全二叉树,以一维数组存储。
2) 双亲表示法
3) 双亲孩子表示法
结构: typedef struct { datatype data; int parent; int lchild; int rchild; }NODE; NODE tree[N]; // 生成N个结点的树 4) 二叉链表 5) 三叉链表 6) 哈夫曼树 5.二叉树的遍历 先根 \ 中根 栈 中根遍历(左子树)根(右子树),再用相同的方法处理左子树,右子树. 后根 / 先,中序已知求树:先序找根,中序找确定左右子树. 层次遍历(队列实现) 6.线索二叉树(穿线树) 中序线索二树树目的:利用空指针直接得到中序遍历的结果. 手段(方法):左指针为空,指向前趋,右指针为空,指向后继. 结点结构:
Ltag=0,lch指向左孩子,ltag=1,指向前趋结点 Rtag=0,rch指向右孩子;rtag=1,指向后继结点 中序遍历: 1) 找最左结点(其左指针为空) 2) 当该结点的rtag=1,该结点的rch指向的就为后继 3) 当rtag=0,后继元素为右子树中最左边那个 N个结点的二树有空指针N+1个 周六我去了周SIR的办公室，他很热情，我问的是中序线索化二叉树的问题(递归)，关于这个问题我会在以后的笔记中作重点补充。我在这学校从来没有碰到过像他这样热情的老师，真的，大一的时候我们学校就开了C，当时我就连#include<stdio.h>这句话的意思都不晓得，别说是让我写程序了（到这份上也不怕把丑事都抖出来了:《数据结构》的课程设计也是哈科大的littlebob兄帮我做的，很遗憾，他高程就差几分，希望他早日成功，我们都要向他学习）等于说我的C知识九成都是在大二下学期的时候学的。而且全是自学的。拿这个周末来说吧。我三天时间就看完了一本C语言大全。当然，并不是从头到尾，只是根据自己的实际情况，重点是指针和数据结构那块。C最要的便是指针。程序员考试下午试题最重要的便是递归问题（1～2道，没有掌握就没希望了哦）。我说这些并不是为了表明自己多么用功，只是希望每位"学者"都有所侧重。
八大类算法
程序员考试下午试题最后一道一般是八大类算法里头的.大家尤其要注意的是递归，因为近几年都考了，而且有的还考两题。可以说如果我们不掌握递归就没有掌握C，况且递归是C里的难点。为了控制合格率，程序员考试不会让我们轻松过关的，为了中国软件业，我想也应该这样啊。 /数据结构(离散) 迭代 \数值计算(连续) 枚举 策略好坏很重要 递推 递归 回溯 分治 贪婪 动态规划 其中：递推、递归、分治、动态规划四种算法思想基本相似。都是把大问题变成小问题，但技术上有差别。
枚举: 背包问题: 枚举策略：1)可能的方案：2N 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)二叉树(遍历等) 例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); } }
分治法: 思想:把规模为n的问题进行分解,分解成几个小规模的问题.然后在得到小规模问题的解的基础上,通过某种方法组合成该问题的解. 例:数轴上有n个点x[n],求距离最小的两个点. 分:任取一点,可以把x[i]这n个点分成两个部分 小的部分 分点 大的部分 |_._.__.__.____._|__._._.__._.__._______._.__._._.__.___._____._| 治:解=min{小的部分的距离最小值; 大的部分的距离最小值; 大的部分最小点和小的部分最大点这两点之差;}
快考试了，老师没有多说什么，他只是给我们讲了讲近三年试题情况，并详细讲述了两道题目：一道递归，另一道回溯。不过今天不知怎么回事，我感觉特别累，也特别想睡觉。所以没什么感觉。这里就不说了，两道题目都有的，递归那题是2001年最后一题,回溯是在《程序员教程》P416，老师说高程曾经考过，有兴趣自己看看也能看懂的。老师特意为我们出了一份下午试题，我现在把他拿出来让大家参考参考。到这里，就到这里！
程序员考试下午试题（模拟）
2.二叉树定义: 结点个数>=0 . 3. 术语:左右孩子,双亲,子树,度,高度等概念. 4. 二叉树的性质 ●层次为I的二叉树 I层结点 2I 个 ●高度为H的二叉树结点 2H+1-1个 ●H(点)=E(边)+1 ●个数为N的完全二叉树高度为|_LOG2n_| ●完全二叉树结点编号:从上到下,从左到右.
二叉树的存储结构: 1) 扩展成为完全二叉树,以一维数组存储。
2) 双亲表示法
3) 双亲孩子表示法
结构: typedef struct { datatype data; int parent; int lchild; int rchild; }NODE; NODE tree[N]; // 生成N个结点的树 4) 二叉链表 5) 三叉链表 6) 哈夫曼树 5.二叉树的遍历 先根 \ 中根 栈 中根遍历(左子树)根(右子树),再用相同的方法处理左子树,右子树. 后根 / 先,中序已知求树:先序找根,中序找确定左右子树. 层次遍历(队列实现) 6.线索二叉树(穿线树) 中序线索二树树目的:利用空指针直接得到中序遍历的结果. 手段(方法):左指针为空,指向前趋,右指针为空,指向后继. 结点结构:
Ltag=0,lch指向左孩子,ltag=1,指向前趋结点 Rtag=0,rch指向右孩子;rtag=1,指向后继结点 中序遍历: 1) 找最左结点(其左指针为空) 2) 当该结点的rtag=1,该结点的rch指向的就为后继 3) 当rtag=0,后继元素为右子树中最左边那个 N个结点的二树有空指针N+1个 周六我去了周SIR的办公室，他很热情，我问的是中序线索化二叉树的问题(递归)，关于这个问题我会在以后的笔记中作重点补充。我在这学校从来没有碰到过像他这样热情的老师，真的，大一的时候我们学校就开了C，当时我就连#include<stdio.h>这句话的意思都不晓得，别说是让我写程序了（到这份上也不怕把丑事都抖出来了:《数据结构》的课程设计也是哈科大的littlebob兄帮我做的，很遗憾，他高程就差几分，希望他早日成功，我们都要向他学习）等于说我的C知识九成都是在大二下学期的时候学的。而且全是自学的。拿这个周末来说吧。我三天时间就看完了一本C语言大全。当然，并不是从头到尾，只是根据自己的实际情况，重点是指针和数据结构那块。C最要的便是指针。程序员考试下午试题最重要的便是递归问题（1～2道，没有掌握就没希望了哦）。我说这些并不是为了表明自己多么用功，只是希望每位"学者"都有所侧重。
八大类算法
程序员考试下午试题最后一道一般是八大类算法里头的.大家尤其要注意的是递归，因为近几年都考了，而且有的还考两题。可以说如果我们不掌握递归就没有掌握C，况且递归是C里的难点。为了控制合格率，程序员考试不会让我们轻松过关的，为了中国软件业，我想也应该这样啊。 /数据结构(离散) 迭代 \数值计算(连续) 枚举 策略好坏很重要 递推 递归 回溯 分治 贪婪 动态规划 其中：递推、递归、分治、动态规划四种算法思想基本相似。都是把大问题变成小问题，但技术上有差别。
枚举: 背包问题: 枚举策略：1)可能的方案：2N 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)二叉树(遍历等) 例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); } }
分治法: 思想:把规模为n的问题进行分解,分解成几个小规模的问题.然后在得到小规模问题的解的基础上,通过某种方法组合成该问题的解. 例:数轴上有n个点x[n],求距离最小的两个点. 分:任取一点,可以把x[i]这n个点分成两个部分 小的部分 分点 大的部分 |_._.__.__.____._|__._._.__._.__._______._.__._._.__.___._____._| 治:解=min{小的部分的距离最小值; 大的部分的距离最小值; 大的部分最小点和小的部分最大点这两点之差;}
快考试了，老师没有多说什么，他只是给我们讲了讲近三年试题情况，并详细讲述了两道题目：一道递归，另一道回溯。不过今天不知怎么回事，我感觉特别累，也特别想睡觉。所以没什么感觉。这里就不说了，两道题目都有的，递归那题是2001年最后一题,回溯是在《程序员教程》P416，老师说高程曾经考过，有兴趣自己看看也能看懂的。老师特意为我们出了一份下午试题，我现在把他拿出来让大家参考参考。到这里，就到这里！