问答题
下面的C函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式。【复旦大学1999六(1 5分)】
#include
typedef struct node{char data;struct node*link;)node ;
node*select(node*head)
(node*p,*q, *r,*s;
p=(node*)malloc(sizeof(node));
P一>link=head;head=p;
while(P一>link!=null)
(q=p->link;r=p;
while( (1) )
{if(q->link一>datalink一>data) r=q;
q=q->link;
}
if( (2) )
(s=r一>link;r一>link=s一>link;
S一>link=( (3) );
( (4) );
}
( (5) ) ;
}
p=head;head=head一>link;free(p);return(head);
}
【正确答案】正确答案:题中为操作方便,先增加头结点(最后删除),p指向无序区的前一记录,r指向最小值点的前驱,一趟排序结束,无序区第一个记录与r所指结点的后继交换指针。 (1)q一>link!==null (2)r!=p (3)p一>link (4)p一>link==s (5)p=p一>link
【答案解析】