问答题
选择排序法每一趟排序的基本原理是从当前未排好序的那些元素中选一个值最小的元素，将其与未排好的那些元素的第一个元素交换位置。根据这个原理，请写出对一个带有头结点的单链表按数据域从小到大进行选择排序的算法。约定：链结点构造为(data，link)，每一个链结点的数据域中存一个整型数，但是头结点数据域中不存放任何信息；设头结点指针为list。限制：排序过程中不得不申请任何链结点空间，也不得改变任何链结点的数据域内容。【北京航空航天大学2006三(10分)】
【正确答案】正确答案：上题是按“交换结点值”进行选择排序，本题要求交换结点。因此必须知道“值最小的元素”和“未排好的那些元素的第一个元素”前驱的指针。设“值最小的元素”的前驱的指针是start，待排序的第一个元素的指针是P，其前驱的指针是pre。则结点交换的核心语句段是：pre一>link=start一>link；start一>link一>link=p一>link；pre=pre一>link；／／前驱后移P一>link=start一>link一>link；start一>link=p；
【答案解析】