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-