函数功能: 在带头结点单链表中删除一个值为x的结点，函数返回值为头指针。请选择正确的选项 链式表

有一个单链表，其结点的元素值以非递减有序排列，编写一个函数删除该单链表中余的元素值相同的结点。

阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 函数 GetListElemPtr(LinkList L，int i)的功能是查找含头结点单链表的第i个元素。若找到，则返回指向该结点的指针，否则返回空指针。 函数DelListElem(LinkList L，int i，ElemType *e) 的功能是删除含头结点单链表的第 i个元素结点，若成功则返回 SUCCESS ，并由参数e 带回被删除元素的值，否则返回ERROR 。 例如，某含头结点单链表 L 如图 4-1 (a) 所示，删除第 3 个元素结点后的单链表如 图 4-1 (b) 所示。图4-1

define SUCCESS 0 define ERROR -1 typedef int Status; typedef int ElemType; 链表的结点类型定义如下: typedef struct Node{ ElemType data; struct Node *next; }Node ,*LinkList; 【C 代码】 LinkList GetListElemPtr(LinkList L ，int i) { /* L是含头结点的单链表的头指针，在该单链表中查找第i个元素结点: 若找到，则返回该元素结点的指针，否则返回NULL */ LinkList p; int k; /*用于元素结点计数*/ if (i<1 ∣∣ !L ∣∣ !L->next) return NULL; k = 1; P = L->next; / *令p指向第1个元素所在结点*/ while (p && （1） ) { /*查找第i个元素所在结点*/ （2） ; ++k; } return p; } Status DelListElem(LinkList L ，int i ，ElemType *e) { /*在含头结点的单链表L中，删除第i个元素，并由e带回其值*/ LinkList p，q; /*令p指向第i个元素的前驱结点*/ if (i==1) （3） ； else p = GetListElemPtr(L ，i-1); if (!p ∣∣ !p->next) return ERROR; /*不存在第i个元素*/ q = (4) ； /*令q指向待删除的结点*/ p->next = q->next; /*从链表中删除结点*/ (5) ； /*通过参数e带回被删除结点的数据*/ free(q); return SUCCESS; }

阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。

【说明】

函数DelA_InsB(LinkedList La，LinkedList Lb，int key1，int key2，int len)的功能是：将线性表A中关键码为key1的结点开始的len个结点，按原顺序移至线性表B中关键码为key2的结点之前，若移动成功，则返回0；否则返回-1。线性表的存储结构为带头结点的单链表，La为表A的头指针，Lb为表B的头指针。单链表结点的类型定义为

typedef struct node {

int key;

struct node * next;

} *LinkedList;

【函数】

int DelA_InsB ( LinkedList La, LinkdeList Lb,int key1,int key2,,int len)

{ LinkedList p,q,s,prep,pres;

int k;

if( ! La-＞next || ! Lb-＞ next ||| en ＜=0)return-1;

p = La -＞ next;prep = La;

while(p&&p- ＞key != key1) { /*查找表A中键值为key1的结点*/

prep = p;p = p -＞ next;

}

if( ! p) return - 1; /*在表A中不存在键值为key1的结点*/

q=p;k=1;

while(q &&(1))} /*表A中不存在要被删除的len个结点*/

(2);k++;

}

if( ! q)return -1; /*表A中不存在要被删除的len个结点*/

s = Lb -＞ next;(3);

while(s && s -＞ key != key2) { /*查找表B中键值为key2的结点*/

pres =s;s =s-＞next;

}

if( ! s) return - t; /*表B中不存在键值为key2的结点*/

(4)=q-＞ next; /*将表A中的len个结点删除*/

q-＞next=(5);

pres -＞ next = p; /*将len个结点移至表B */

return 0;

}

【题目描述】

试题四（共15分）

阅读以下说明和 C 函数，将应填入 （n） 处的语句或语句成分写在答题纸的对应栏内。

【说明】

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

例如，某单链表如图4-1 所示。若令 minK 为 20、maxK 为 50，则删除后的链表如图4-2所示。

链表结点类型定义如下：

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;

}

【我提交的答案】：1: LinkList2: p->next3: p->next4: q->next5: !deTag

【参考答案分析】：

试题四（共15分）

（1）Node           （3分）

（2）p->next           （3分）

（3）p->next           （3分）

（4）q->next           （3分）

（5）!delTag，或delTag==0，或delTag!=1    （3分）

第一小题指针类型为什么是NODE而不是LinkList

试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法void delete(Linklist＆L)。【北京理工大学2001九、3(8分)】

删除单链表L中某个结点p之后的一个结点，时间复杂度为（）

已知带头结点的单链表有data和next两个域，设计一个算法，将该链表中的重复元素结点删除。

A、p=p->next;

B、p->next=p->next->next;

C、p->next=p;

D、p->next->next=p->next->next->next;

●设rear是指向非空带头结点的循环单链表的尾指针，则删除链表第一个结点的操作可表示为 (22) 。

(22) A．p=rear；rear=rear→next;free(p)；

B．rear=rear→next；free(p)；

C．rear=rear→next→next；free(p)；

D．p=rear→next→next；rear→next=p→next；free(p)；