算法例题.docx

1 / 6
算法例题
假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
答：[题目分析]因为两链表已按元不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。
试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。voiddelete（Linklist &L）
答：[题目分析]本题要求在单链表中删除最小值结点。单链表中删除结点， 为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前
驱。遍历结束后再执行删除操作。
LinkedList Delete（LinkedList L）
∥ L 是带头结点的单链表，本算法删除其最小值结点。
{p=L->next；∥ p 为工作指针。指向待处理的结点。假定链表非空。pre=L；∥ pre 指向最小值结点的前驱。
q=p；∥ q 指向最小值结点，初始假定第一元素结点是最小值结点。while（p->next!=null）
2 / 6
{if（p->next->datadata）{pre=p；q=p->next；} ∥ 查最小值结点
p=p->next；∥ 指针后移。
}
pre->next=q->next；∥ 从链表上删除最小值结点
free（q）；∥ 释放最小值结点空间
}∥ 结束算法 delete。
[算法讨论]算法中函数头是按本教材类C 描述语言书写的。原题中voiddelete（linklist&L），是按 C++的“引用”来写的，目的是实现变量的“传址”， 克服了 C 语言函数传递只是“值传递”的缺点。
已知非空线性链表由 list 指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。
答：[题目分析]本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间），再插入到链表的最前面。
LinkedList delinsert（LinkedList list）
∥ list 是非空线性链表，链结点结构是（data，link），data 是数据域，link 是链域。
∥ 本算法将链表中数据域值最小的那个结点移到链表的最前面。
{p=list->link；∥ p 是链表的工作指针
pre=list；∥ pre 指向链表中数据域最小值结点的前驱。q=p；∥ q 指向数据域最小值结点，初始假定是第一结点while（p->link!=null）
3 / 6
{if（p->link->datadata）{pre=p；q=p->link；} ∥ 找到新的最小值结点；
p=p->link；
}
if (q!=list->link) ∥ 若最小值是第一元素结点，则不需再操作
{pre->link=q->link；∥ 将最小值结点从链表上摘下； q->link= list->link；∥ 将q 结点插到