2、某带头结点的非空单链表L中所有元素为整数，结点类型定义如下： typedef struct node { int data; struct node *next; } LinkNode; 设计一个尽可能高效的算法，将所有小于零的结点移到所有大于等于零的结点的前面。

在C语言中，可以用typedef声明新的类型名来代替已有的类型名，比如有学生链表结点： typedef struct node{ int data; struct node * link; }NODE, * LinkList; 下述说法正确的是______。

A．NODE是结构体struct node的别名

B．* LinkList也是结构体struct node的别名

C．LinkList也是结构体struct node的别名

D．LinkList等价于node*

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

【说明】

函数sort (NODE *head)的功能是；用冒泡排序法对单链表中的元素进行非递减排序。对于两个相邻结点中的元素，若较小的元素在前面，则交换这两个结点中的元素值。其中，head指向链表的头结点。排序时，为了避免每趟都扫描到链表的尾结点，设置一个指针endptr，使其指向下趟扫描需要到达的最后一个结点。例如，对于图4-1(a)的链表进行一趟冒泡排序后，得到图4-1(b)所示的链表。

链表的结点类型定义如下：

typedef struct Node {

int data;

struct Node *next;

} NODE;

【C语言函数】

void sort (NODE *head)

{ NODE *ptr,*preptr, *endptr;

int tempdata;

ptr = head -＞ next;

while ((1)) /*查找表尾结点*/

ptr = ptr -＞ next;

endptr = ptr; /*令endptr指向表尾结点*/

ptr =(2);

while(ptr != endptr) {

while((3)) {

if (ptr-＞data ＞ ptr-＞next-＞data){

tempdata = ptr-＞data; /*交换相邻结点的数据*/

ptr-＞data = ptr-＞next-＞data;

ptr-＞next-＞data = tempdata;

}

preptr =(4); ptr = ptr -＞ next;

}

endptr =(5); ptr = head-＞next;

}

}

以下程序的功能是：建立一个带有头结点的甲—向链表，并将存储在数组中的字符依次转存到链表的各个结点中，请从与下划线处号码对应的一组选项中选择出正确的选项。

#include ＜stdlib.h＞

struct node

{ char data; struct node *next: };

(1) CreatList(char *s)

{

struct node *h,*p,*q;

h = (struct node *)malloc sizeof(struct node));

p=q=h;

while(*s! ='\0')

{

p = (struct node *)malloc(sizeof (struct node));

p-＞data = (2) ;

q-＞next = p;

q - (3) ;

S++;

}

p-＞next='\0';

return h;

}

main()

{

char str[]="link list";

struct node *head;

head = CreatList(str);

}

(1)

A．char*

B．struct node

C．struct node*

D．char

阅读以下说明和C语言函数，将应填入(n)。

【说明】

已知包含头结点(不存储元素)的单链表的元素已经按照非递减方式排序，函数 compress(NODE*head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。

处理过程中，当元素重复出现时，保留元素第一次出现所在的结点。

图2-1(a)、(b)是经函数compress()处理前后的链表结构示例图。

链表的结点类型定义如下：

typedef struct Node{

int data；

struct Node *next；

}NODE；

【C语言函数】

void compress(NODE *head)

{ NODE *ptr，*q；

ptr= (1)； /*取得第一个元素结点的指针*/

while( (2)&& ptr-＞next) {

q=ptr-＞next；

while(q&&(3)) { /*处理重复元素*/

(4)q-＞next；

free(q)；

q=ptr-＞next；

}

(5) ptr-＞next；

}/*end of while */

}/*end of compress*/

以下程序中函数fun的功能是：构成—个如图所示的带头结点的单向链表，在结点的数据域中放入了具有两个字符的字符串。函数disp的功能是显示输出该单向链表中所有结点中的字符串。请填空完成函数disp。

include＜stdio.h＞

typedef struct node /*链表结点结构*/

{ char sub[3];

struct node *next;

}Node;

Node fun(char s) /* 建立链表*/

{ ...... }

void disp(Node *h)

{ Node *p;

p=h-＞next;

while([ ])

{printf("%s\n",p-＞sub);p=[ ];}

}

main()

{ Node *hd;

hd=fun(); disp(hd);printf("\n");

}

此题为判断题(对，错)。

阅读以下说明和 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; }

试题四（共 15 分）

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

[说明]

已知包含头结点（不存储元素）的单链表的元素已经按照非递减方式排序，函数compress(NODE *head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。

处理过程中，当元素重复出现时，保留元素第一次出现所在的结点。

图4-1(a)、(b)是经函数 compress()处理前后的链表结构示例图。

链表的结点类型定义如下：

typedef struct Node {

int data;

struct Node *next;

}NODE;

[C 语言函数]

void compress(NODE *head)

{ NODE *ptr,*q;

ptr = （1） ; /* 取得第一个元素结点的指针 */

while ( （2） && ptr -> next) {

q = ptr -> next;

while(q && （3） ) { /* 处理重复元素 */

（4） = q -> next;

free(q);

q = ptr -> next;

}

（5） = ptr -> next;

}/* end of while */

}/* end of compress */

以下程序中函数fun的功能是：构成一个如图所示的带头结点的单词链表，在结点的数据域中放入了具有两个字符的字符串。函数disp的功能是显示输出该单链表中所有结点中的字符串。请填空完成函数disp。[*]

include＜stdio.h＞

typedef struct node /*链表结点结构*/

{char sub[3]；

struct node *next；

}Node；

Node fun(char s) /*建立链表*/

{ … }

void disp(Node *h)

{ Node *

函数min()的功能是：在带头结点的单链表中查找数据域中值最小的结点。请填空

include ＜stdio.h＞

struct node

{ int data;

struct node *next;

};

int min(struct node *first)/*指针first为链表头指针*/

{ struct node *p; int m;

p=first-＞next; re=p-＞data; p=p-＞next;

for( ;p!=NULL;p=【 】)

if(p-＞data＜m ) re=p-＞data;

return m;

}

以下程序的功能是建立—个带有头结点的单向链表，链表结点中的数据通过键盘输入，当输入数据为-1时，表示输入结束(链表头结点的data域不放数据，表空的条件是ph-＞next==NULL)，请填空。

include＜stdio.h＞

struct list { int data；struct list *next；}；

struct list * creatlist()

{ struct list *p，*q，*ph；int a；ph=(struct list *)malloc(sizeof(struct

以下程序把三个NODEIYPE型的变量链接成—个简单的链表，并在while循环中输出链表结点数据域中的数据。请填空。

include＜stdio.h＞

struct node

{ int data;struct node*next;);

typedef struct node NODETYPE;

main()

{ NODETYPEa,b,c,*h,*p;

a.data=10;b.data=20;c.data=30;h=&a;

anext=&b;b.next=&c;c,next='\0';

p=h;

while(p){printf("%d,",p-＞data):【 】;}

printf("\n");

}

链表题：一个链表的结点结构

struct Node

{

int data ;

Node *next ;

};

typedef struct Node Node ;

(1)已知链表的头结点head,写一个函数把这个链表

逆序( Intel)

有以下结构说明和变量定义，指针p、q、r分别指向链表中的3个连续结点。 struct node { int data；struct node*next；)*p，*q，*r； 现要将q所指结点从链表中删除，同时要保持链表的连续，以下不能按要求完成操作的语句是( )。

A.p->next=q->next；

B.P-next=P->next->next；

C.p->next=r；

D.p=q->next；

以下程序的功能是：建立一个带有头结点的单向链表，并将存储在数组中的字符依次转存到链表的各个结点中，请填空。 #include ＜stdlib.h＞ stuct node { char data; struet node * next; }; stntct node * CreatList(char * s) { struet node *h,*p,*q; h = (struct node * ) malloc(sizeof(struct node) ); p=q=h; while( * s! ='\0') { p = (struct node *) malloc ( sizeof(struct node) ); p - ＞ data = ( ) q- ＞next=p; q=p; a++; p- ＞ next ='\0'; return h; } main( ) { char str[ ]= "link list"; struet node * head; head = CreatList(str);

A．*s

B．s

C．*s++

D．(*s)++

阅读以下说明和 C 函数，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 函数 Combine(LinkList La，LinkList Lb)的功能是:将元素呈递减排列的两个含头结 点单链表合并为元素值呈递增(或非递减)方式排列的单链表，并返回合并所得单链表 的头指针。例如，元素递减排列的单链表 La 和 Lb 如图 4-1 所示，合并所得的单链表如图 4-2 所示。图 4-1 合并前的两个链表示意图图 4-2 合并后所得链表示意图

设链表结点类型定义如下： typedef struct Node{ int data; struct Node *next; }Node ,*LinkList; 【C 函数】 LinkList Combine(LinkList La ，LinkList Lb) { //La 和 Lb 为含头结点且元素呈递减排列的单链表的头指针 //函数返回值是将 La 和 Lb 合并所得单链表的头指针 //且合并所得链表的元素值呈递增（或非递减)方式排列 （1） Lc ,tp ,pa ,pb;; //Lc 为结果链表的头指针 ，其他为临时指针 if (!La) return NULL; pa = La->next; //pa 指向 La 链表的第一个元素结点 if (!La) return NULL; pa = La->next; //pb 指向 Lb 链表的第一个元素结点 Lc = La; //取 La 链表的头结点为合并所得链表的头结点 Lc->next = NULL; while ( （2） ){ //pa 和 pb 所指结点均存在(即两个链表都没有到达表尾) //令tp指向 pa 和 pb 所指结点中的较大者 if (pa->data > pb->data) { tp = pa; pa = pa->next; } else{ tp = pb; pb = pb->next; } （3） = Lc->next; //tp 所指结点插入 Lc 链表的头结点之后 Lc->next = （4） ; } tp = (pa)? pa : pb; //设置 tp 为剩余结点所形成链表的头指针 //将剩余的结点合并入结果链表中， pa 作为临时指针使用 while (tp) { pa = tp->next; tp->next = Lc->next; Lc->next = tp; （5） ; } return Lc; }