阅读以下说明和流程图,将应填入(n)处的字句写在对应栏内。
【说明】
已知头指针分别为La和lb的有序单链表,其数据元素都是按值非递减排列。现要归并La和Lb得到单链表Lc,使得Lc中的元素按值非递减排列。程序流程图如下所示:
第1题:
试题四(共 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 */
第2题:
第3题:
【论述题】假设有两个按元素值非递减次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值非递增次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。
第4题:
第5题:
设指针la和lb分别指向两个无头结点单链表中的首元结点,试设计从表la中删除自第i个元素起共len个元素,并将它们插入到表lb的第j个元素之后的算法。