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

．[题目分析] 本题要求将链表中数据域值最小的结点移到链表的最前面首先要查找最小值结点将其移到链表最前面实质上是将该结点从链表上摘下(不是删除并回收空间)再插入到链表的最前面

LinkedList delinsert(LinkedList list)∥list是非空线性链表链结点结构是(datalink)data是数据域link是链域本算法将链表中数据域值最小的那个结点移到链表的最前面

{p=list>link;∥p是链表的工作指针

pre=list;∥pre指向链表中数据域最小值结点的前驱

q=p;∥q指向数据域最小值结点初始假定是第一结点

while (p>link!=null)

{if(p>link>data<q>data){pre=p;q=p>link;}∥找到新的最小值结点;

p=p>link;

}

if (q!=list>link)∥若最小值是第一元素结点则不需再操作

{pre>link=q>link;∥将最小值结点从链表上摘下;

q>link= list>link;∥将q结点插到链表最前面

list>link=q;

}

}∥算法结束

[算法讨论] 算法中假定list带有头结点否则插入操作变为q>link=list;list=q

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