C语言教程基础篇【全】.ppt

分析： 考虑将结点p插入链表head中，分如下三种情况： 1、第一种情况，链表还未建成（空链表），待插入结点p实际上是第一个结点。这时必然有head==null。 只要让头指针指向p就可以了。语句为 head = p; p-next = null; 2、第二种情况，链表已建成，待插入结点p的数据要比头结点的数据还要小，这时有p-num head-num 。 当然p结点要插在head结点前。 3、第三种情况，链表已建成，待插入结点p的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针r和q，利用循环比较来找到正确位置。然后将结点p插入到链表中正确的位置。 第八讲 结构体 6 head 8 12 null 13 p 15 q r 说明：这种情况下，p结点已经与链表的第一个结点比较过了，所以从链表的下一个结点开始比较。138，继续比较。 第八讲 结构体 3. 先看简单情况，河中无柱子：S=0， Jump(0,y) 当y=1时，Jump(0,1)=2； 说明：河中有一片荷叶，可以过两只青蛙，起始时L上有两只青蛙，1#在2#上面。 第一步：1# 跳到荷叶上； 第二步：2# 从L直接跳至R上； 第三步：1# 再从荷叶跳至R上。 如下图： 2# 1# 2 1 3 L 左岸 R 右岸 第六讲 递归及其实现 当y=2时， Jump(0,2)=3； 说明：河中有两片荷叶时，可以过3只青蛙。起始时： 1#，2#，3# 3只青蛙落在L上， 第一步：1# 从L跳至叶 1上， 第二步：2# 从L跳至叶 2上， 第三步：3# 从L直接跳至R上， 第四步：2# 从叶2跳至R上， 第五步：1# 从叶1跳至R上， 叶1 3 1 5 L R 叶2 2 4 采用归纳法：Jump(0,y)=y+1； 意思是：在河中没有石柱的情况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数+1。 第六讲 递归及其实现 再看Jump(S, y)先看一个最简单情况： S=1，y=1。从图上看出需要9步，跳过4只青蛙。1# 青蛙从 L － Y；2# 青蛙从 L － S；1# 青蛙从 Y － S；3# 青蛙从 L － Y；4# 青蛙从 L － R；3# 青蛙从 Y － R；1# 青蛙从 S － Y；2# 青蛙从 S － R；1# 青蛙从 Y － R； S Y 5 4 6 L R 1 2 3 7 8 9 1# 2# 4# 3# 3# 1# 2# 1# 1# 第六讲 递归及其实现 用L1 L2 L3 L4表示左岸石柱上落在一起的青蛙的高度位置。 L1 在最上面，L4 在最下面的位置。 引入这个信息就可比较容易地看出对青蛙占位的约束条件。 同理R1 R2 R3 R4也是如此。 对水中石柱S，也分成两个高度位置S1 S2。 对荷叶Y无须分层，因为它只允许一只青蛙落在其上。 t=0为初始时刻，青蛙从小到大落在石柱L上。 t=1为第一步：1#从L跳至荷叶Y上；L上只剩2# 3# 4#。 T=2 为第二步；2#从L跳至石柱S上，处在S2位置上，L上只剩3#和4#。 T=3为第三步，1#从Y跳至S，将Y清空。 这时可看出，S上有1#、2#，L上有3#、4#，好象是原来在L上的4只青蛙，分成了上下两部分，上面的2只通过荷叶y转移到了S上。这一过程是一分为二的过程。即将L上的一队青蛙，分解为两个队，每队各二只，且将上面的二只转移到了S上。这时我们可以考虑形成两个系统，一个是L，Y，R系统，一个是S，Y，R系统。前者二只青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。从第五步到第九步可以看出的确是这么做的。 第六讲 递归及其实现 对于LYR系统，相当于Jump(0,1)对于SYR系统，相当于Jump(0,1) 两个系统之和为2*Jump(0,1)，因此有：Jump(1,1)=2*Jump(0,1)=2*2=4。 现在再看S=2，y=1 Jump(2,1) 我们将河中的两个石柱称作S1和S2，荷 叶叫y， 考虑先将L上的青蛙的一半借助于S2和y 转移到S1上，当然是一半小号的青蛙在 S1上，大的留在L上。 y L R S1 S2 第六讲 递归及其实现 这样 L S1 S2 y R 系统分解为 ： （L S2 y R 系统） + （S1 S2 y R 系统）= 2 * （L S2 y R 系统）= 2 * Jump(1,1) 用归纳法Jump(S, y)=2*Jump(S-1, y) 第六讲 递归及其实现 main() { int s,y,sum; //