阅读以下说明和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*/
第1题：
第2题：
第3题：
第4题：
试题四（共 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 */
第5题：
阅读以下说明和 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; }
第6题：
阅读以下说明和 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; }
第7题：
[说明]
已知包含头节点(不存储元素)的单链表的元素已经按照非递减方式排序，函数compress(NODE *head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。
处理过程中，当元素重复出现时，保留元素第一次出现所在的节点。
图8-29(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*/
第8题：
阅读以下说明和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;
}
}
第9题：
阅读以下说明和流程图，将应填入(n)处的字句写在对应栏内。
【说明】
已知头指针分别为La和lb的有序单链表，其数据元素都是按值非递减排列。现要归并La和Lb得到单链表Lc，使得Lc中的元素按值非递减排列。程序流程图如下所示：
