程序员考试下午试题程序填空解题方法

文章作者 100test 发表时间 2008:04:15 15:59:26
来源 100Test.Com百考试题网

一、步骤
　　 1、理解题意：
　　 主要是根据问题的描述，确定问题的已知条件，并了解算法（程序）要达到的目的。通俗讲，就是要知道问题的输入和输出。
　　 2、确定算法：
　　 每个题目在前面都有描述，通过对描述的分析，要确定题目应该属于哪一类数据结构以及相应的算法。有些题目可能不属于任何数据结构，则它可能与某类算法（8类）有关；但也有一些算法纯粹是数学方法。
　　 在描述中同时要理解算法过程。在分析算法时，可以以某个具体实例来试验。
　　 3、理解程序：
　　 分析程序结构，如果有很多子函数，首先弄清楚各函数之间的关系和各函数的作用；如果程序较长，则应该根据算法过程，把每个程序段与算法的每个过程对应起来，确定相应的程序段功能。
　　 在程序中，已经定义了某些变量，则在理解程序时，首先必须理解这些变量的含义
　　 4、根据C语言的语法填空。
　　 二、示例
　　 【示例】2004年上半年程序员下午试题试题六
　　 [函数说明]
　　 函数DelAInsB(LinkedList La，LinkedList lb，int key1，int key2，int len)的功能是，将线性表A中关键码为keyl的结点开始的len个结点，按原顺序移至线性表B中关键码为key2的结点之前，若移动成功，则返回0；否则返回-1。线性表的存储结构为带头结点的单链表，La为表A的头指针，Lb为表B的头指针。单链表结点的类型定义为：
　　 typedef struct node{
　　　 int key；
　　　 struct node*next；
　　 }*Linkedhist；

　　 [函数]
（1）　int DelllnsB(LinkedLiSt La，LinkedList Lb，int keyl，int key2，int len)
（2）　{ LinkedList ?p，q，s，prep，pres；
（3）　　int k；
（4）　　if (!La->next || !Lb->next || len<=0) return-1；
（5）　　p = La->next； prep = La；
（6）　　while (p &.&. p->key != keyl) { /* 查找表A中键值为key1的结点 */（7）　　　prep = p；p = p->next；
（8）　　}
（9）　　if (!p)　return -1；　/* 表A中不存在键值为key1的结点 */
（10）　 q = p； k = 1；
（11） 　while (q &.&. __(1)__) { /* 在表A中找出待删除的len个结点 */
（12） 　　__(2)__； k ；
（13）　 }
（14）　 if (!q) return -1； /* 表A中不存在要被删除的len个结点 */
（15）　 s = Lb->next； __(3)__；
（16）　 while (s &.&. s->key != key2) { /* 查找表B中键值为key2的结点 */（17）　　 pres = s； s = s->next；
（18）　 }
（19）　 if (!s) return -1； /* 表B中不存在键值为key2的结点 */
（20）　 __(4)__ =q->next； /* 将表A中的len个结点删除 */
（21）　 q->next= ??(5) ；
（22） 　pres->next = p； /* 将len个结点移至表B */
（23）　 return 0；
（24）　 }
　　 1、理解题目：
　　 已知条件为两个链表La和Lb，最后得到的结果也是两个链表，只不过是La中的部分结点移动到Lb中，因此，本问题主要是解决是怎么移动的。
　　 2、算法：
　　 在题目中没有给出结点移动的算法，我们先可以结合实例自己设计一个算法，然后看是不是与程序中的算法一致。如果不是，则再找算法。
　　 实例：

　　如图所示，如果我们找到实线的指针，它们分别指向La中的Key1结点（p指针）、Key1的前一个结点（q指针）、Aj（从Key1结点开始的第len个结点，r指针）和Lb中的Key2的前一个结点（s指针），则根据链表操作，用图中的虚线指针连接，我们就可以把La中从Key1结点开始的共len个结点全部移动到Lb链表中。因此算法大致如下：
　　 （1）找到p和q指针；
　　 （2）找到r指针；
　　 （3）找到s指针；
　　 （4）r->next=s->next（即把Aj结点连接到K2结点之前）；
　　 （5）s->next=q（即把K1结点连接到原来Lb中K2结点的前一个结点的后面）；
　　　　 注意：经过（4）、（5）两步操作，即实现了移动操作。
　　 （6）要注意的是现在La链表已经断开，也必须重新连接上，故要：
　　 但是注意一下程序，就会发现里面有很多判断，主要是看判断是否可以移动。我们考虑后（也可以看程序）发现，在以下几种情况下，操作不能进行：
　　 （1）La或Lb是空链表；
　　 （2）len表示个数的值，因此不能不大于0；
　　 （3）La中不存在Key1的结点；
　　 （4）La中从Key1结点开始的结点个数小于len个；
　　 （4）Lb中不存在Key2的结点；
　　 3、现在主要是看程序结构是不是和我们自己考虑的算法符合。
　　 程序段（5）～（8）：其中有p指针在向后移动，一直到Key1为止，因此，它们的功能就是找到指向Key1结点的指针；同时，另有一个指针prep一直在p的后面，因此它就是指向Key1的前一个结点的指针。
　　 程序段（10）～（13）：其中有一个k变量，每次循环后增加1，因此它是一个计数器。通过计数len次，就可以找到从Key1结点开始的第len个结点。这时，应该有一个指针（q）同时移动，使得这个指针就是指向第len个结点的指针。
　　 程序段（15）～（18）：其中有s指针在向后移动，一直到Key2为止，因此，它们的功能就是找到指向Key2的前一个结点的指针。
　　 程序段（20）～（22）：就是移动La中的结点到Lb，并把La中断开的链表连接。从上述的分析发现，程序结构是和我们自己考虑的算法一致的。
　　 4、考虑细节，并填空。
　　（1）我们的目的是找指向第len个结点的指针，找到后循环应该结束，因此，要填k　　（2）q指针应该同时移动，故应填：q=q->next
　　（3）这一段程序的功能是找到指向Key2的前一个结点的指针。其中s指针是指向Key2结点的，而pres指针跟在s后面。但是pres指针缺少初值，因此，这儿应该给pres赋值。故，应填：pres=Lb。
　　（4）程序块（20）、（21）、（22）的功能是移动La中的结点到Lb，并把La中断开的链表连接。根据链表操作的方法，显然（20）是把La中断开的链表连接，因此，（4）应该填：prep->next；而（21）、（22）是移动La中的结点到Lb，因此，（5）应该填：pres->next。