V2CE – 数据结构 | 每日一练(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-

正文完