admin 【软考】程序员考试下午试题程序填空解题方法
一、步骤
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
（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。
0条评论