【说明】
函数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;
}
}
参考答案：
(1)ptr -＞ next
(2)head-＞next
(3)ptr !=endptr，或其等价形式
(4)ptr
(5)preptr
解析：
本题考查链表运算能力。 从题目中的以下代码可知，ptr最后应指向表尾结点。 ptr = head -＞ next; while ( (1) ) /*查找表尾结点*/ ptr = ptr -＞ next; endptr = ptr; /*令endptr指向表尾结点*/ 显然，空(1)处应填入“ptr-＞next”，这样循环结束时，ptr指向表尾结点。若填入“ptr”，则循环结束时，ptr为空指针。 进行冒泡排序时，从头至尾依次比较逻辑上相邻的两个结点的数据，如果小元素在前大元素在后，则交换。这样，经过一趟扫描，就将最大元素交换到了表的最后。下一趟可将次大元素交换到最大元素之前。显然，空(2)处应填入“head-＞next”。 由于程序设置的endptr用于指示出每趟扫描需到达的最后一个结点，ptr用于依次扫描链表中的结点，因此空(3)处的循环条件为“ptr != endptr”。 显然，指针preptr起的作用是指向ptr的前驱结点，因此，ptr每向后修改一次，相应地preptr就要修改一次，空(4)处应填入“ptr”。本趟循环结束后，下一趟扫描也就确定了，因此在空(5)处填入“preptr”。