|
first = NULL;
while(head != NULL) //在链表中找键值最小的节点
{
//留意：这里for语句就是浮现选择排序头脑的处所
for (p = head,min = head; p->next != NULL; p = p->next) //轮回遍历链表中的节点，找出此时最小的节点
{
if (p->next->num < min->num) //找到一个比当前min小的节点
{
p_min = p; //生涯找到节点的前驱节点：显然p->next的前驱节点是p
min = p->next; //生涯键值更小的节点
}
}
//上面for语句竣事后，就要做两件事；一是把它放入有序链表中；二是按摄影应的前提判定，布置它分开原本的链表
//第一件事
if (first == NULL) //假若有序链表今朝照旧一个空链表
{
first = min; //第一次找到键值最小的节点
tail = min; //留意：尾指针让它指向最后的一个节点
}
else //有序链表中已经有节点
{
tail->next = min; //把刚找到的最末节点放到最后，即让尾指针的next指向它
tail = min; //尾指针也要指向它
}
//第二件事
if (min == head) //假如找到的最末节点就是第一个节点
{
head = head->next; //显然让head指向原head->next,即第二个节点，就OK
}
else //假如不是第一个节点
{
p_min->next = min->next; //上次最末节点的next指向当前min的next,这样就让min分开了原链表
}
}
if (first != NULL) //轮回竣事获得有序链表first
{
tail->next = NULL; //单向链表的最后一个节点的next应该指向NULL
}
head = first;
return head;
}
对链表举办直接插入排序的根基头脑就是假设链表的前面n-1个节点是已经按键值（就是用它排序的字段，我们取学号num为键值）排好序的，对付节点n在这个序列中找插入位置，使得n插入后新序列如故有序。凭证这种头脑，依次对链表从新到尾执行一遍，就可以使无序链表变为有序链表。
单向链表的直接插入排序图示：
---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原链表）
head 1->next 3->next 2->next n->next
---->[1]---->[NULL]（从原链表中取第1个节点作为只有一个节点的有序链表）
head
图11
（编辑：湖南网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
