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

数据结构考研分类复习真题 第二章 答案[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语言函数传递只是 值传递 的缺点