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

1

每日一练

1．试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。void delete（Linklist &L）

正确答案

ps：||代表注释

1．[题目分析] 本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。

LinkedList Delete（LinkedList L）∥L是带头结点的单链表，本算法删除其最小值结点。

{p=L->next； ∥p为工作指针。指向待处理的结点。假定链表非空。

pre=L； ∥pre指向最小值结点的前驱。

q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。

while（p->next!=null）

{ if（p->next->data<q->data）{pre=p；q=p->next；} ∥查最小值结点

p=p->next； ∥指针后移。

}

pre->next=q->next；∥从链表上删除最小值结点

free（q）； ∥释放最小值结点空间

}∥结束算法delete。

[算法讨论] 算法中函数头是按本教材类C描述语言书写的。原题中 void delete（linklist &L），是按C++的“引用”来写的，目的是实现变量的“传址”，克服了C语言函数传递只是“值传递”的缺点。

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

-end-