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-