数据结构 | 每日一练（51）

1

每日一练

1． 已知非空线性链表由 list 指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。

正确答案

ps：||代表注释

1．[题目分析] 本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间），再插入到链表的最前面。

LinkedList delinsert（LinkedList list）∥list是非空线性链表，链结点结构是（data，link），data是数据域，link是链域。

∥本算法将链表中数据域值最小的那个结点移到链表的最前面。

{p=list->link；∥p是链表的工作指针

pre=list； ∥pre指向链表中数据域最小值结点的前驱。

q=p； ∥q指向数据域最小值结点，初始假定是第一结点

while （p->link!=null）

{ if（p->link->data<q->data）{pre=p；q=p->link；} ∥找到新的最小值结点；

p=p->link；

}

if (q!=list->link) ∥若最小值是第一元素结点，则不需再操作

{pre->link=q->link； ∥将最小值结点从链表上摘下；

q->link= list->link；∥将q结点插到链表最前面。

list->link=q；

}

}∥算法结束

[算法讨论] 算法中假定list带有头结点，否则，插入操作变为q->link=list；list=q。

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-