数据�l�构�W�二章算法设计题 [11]_跨考网

　1. 已知非空�U�性链表由list指出�Q�链�l�点的构造�ؓ(f��)�Q?/span>data,link�Q?/span>.请写一���法�Q�将链表中数据域值最���的那个铄���点移到链表的最前面。要求：(x��)不得额外甌���新的铄���炏V���?a target="_blank">北京航空航天大学 2001 四（10分）�?/span>

　　【参考答案�?/span>

　　[题目分析] 本题要求���链表中数据域值最���的�l�点�U�d��链表的最前面。首先要查找最���值结炏V��将其移到链表最前面�Q�实质上是将该结点从链表上摘下（不是删除�q�回收空��_(d��)���Q�再插入到链表的最前面�?/span>

　LinkedList delinsert�Q?/span>LinkedList list�Q?/span>

　　�?/span>list是非�I�线性链表，铄���点结构是�Q?/span>data�Q?/span>link�Q�，data是数据域�Q?/span>link是链域�?/span>

　　∥本���法���链表中数据域值最���的那个�l�点�U�d��链表的最前面�?/span>

　　{p=list->link�Q�∥p是链表的工作指针

　　pre=list�Q?/span> �?/span>pre指向链表中数据域最���值结点的前驱�?/span>

　　q=p�Q?/span> �?/span>q指向数据域最���值结点，初始假定是第一�l�点

　　while �Q?/span>p->link!=null�Q?/span>

　　{if�Q?/span>p->link->data<q->data�Q?/span>{pre=p�Q?/span>q=p->link�Q?/span>} ∥找到新的最���值结点；

　　p=p->link�Q?/span>

　　}

　　if (q!=list->link) ∥若最���值是�W�一元素�l�点�Q�则不需再操�?/span>

　　{pre->link=q->link�Q?/span> ∥将最���值结点从链表上摘下；

　　q->link= list->link�Q�∥��?/span>q�l�点插到链表最前面�?/span>

　　list->link=q�Q?/span>

　　}

　　}∥算法结�?/span>

　　[���法讨论] ���法中假�?/span>list带有头结点，否则�Q�插入操作变�?/span>q->link=list�Q?/span>list=q�?/span>