问题 填空题

[说明]

已知单链表L含有头节点,且节点中的元素值以递增的方式排列。下面的函数DeleteList在L中查找所有值大于mink且小于maxK的元素,若找到,则逐个删除,同时释放被删节点的空间。若链表中不存在满足条件的元素,则返回-1,否则返回0。

例如,某单链表如下图(a)所示。若令minK为20、maxK为50,则删除后的链表如图(b)所示。

链表节点类型定义如下:

typedef struct Node

int data;

struct Node *next;

Node, *LinkList;

[C函数]

int DeleteList (LinkList L, int minK, int maxK)

/*在含头节点的单链表L中删除大于minK且小于maxK的元素*/

(1) *q=L, *p=L->next; /*p指向第一个元素节点*/

int delTag=0;

while (p)

if (P->data <= minK)

q=p; p= (2) ;

else

if (p->data < maxK) /*找到删除满足条件的节点*/

q->next= (3) ; free(p);

p= (4) ; delTag=1;

else break;

if ( (5) ) return -1;

return 0;

(5)处应填()。

答案

参考答案:!delTag,或delTag==0,或delTag!=1

解析:

本题目考查C语言指针和动态链表的应用。

函数DeleteList(LinkList L, int minK, int maxK)的功能是在L在含头节点的单链表L中删除大于minK且小于maxK的元素,因此除了头指针L以外,至少还需要两个临时指针,一个用于遍历链表中的元素,另外一个用于删除节点时重新链接节点,p和q就起这样的作用。

空(1)处用于定义指针变量p和q,由于p和q之前已经有“*”,因此,空(1)处应填入“Node”,若填入“LinkList”,则p和q为指向指针变量的指针变量,此后对它们的使用方式就不正确了。

由于链表中的元素已经按照升序排列,所以在第一个大于minK的元素之前都可以令指针一直沿着指针链后移,即“q=p; p=p->next”,直到p指向第一个大于minK的元素节点为止,在此过程中,q始终指向p所指节点的前驱。因此,空(2)处应填入“p->next”。

删除节点的处理由以下代码完成:

if (P->data < maxK) { /*找到删除满足条件的节点*/

q->next= (3) ; free(p);

p= (4) ; delTag=1;

}

当p指向需要被删除的节点时,q正好指向其前驱节点,如下图(a)所示,因此,“q->next=p->next”就可以将p所指节点从链表中删除,如下图(b)所示:

函数调用“free(p)”将p所指节点的空间释放(由系统回收)。因此空(3)应填入“p->next”。此后,应再令p指向下一个需要被删除的节点,即空(4)应填入“q->next”。delTag的作用是判断链表中是否存在满足删除条件的节点,因此根据题目的描述,空(5)处应填入“!delTag”,当delTag的值保持为0时,说明链表中不存在满足删除条件的节点。

单项选择题
单项选择题