数据结构考研分类复习真题 第二章 答案[29]

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

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语言函数传递只是值传递的缺点

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []