应用题 3.已知一个带有头结点的单链表L,其结点结构由两部分组成:数据域data,指针域link。设计一个算法,以最高效的方法实现在单链表中删除数据域最小值结点。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
【正确答案】(1)算法的基本思想:单链表中删除结点,为使结点删除后不出现“断链”,应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表,求得最小值结点及其前驱。遍历结束后再执行删除操作。
(2)算法的设计如下:
typedef struct LNode{
int data:
struct LNode * next;
}LNode*Linkedlist;
LinkedList Delete(LinkedList L){//L是带头结点的单链表,本算法删除其最小值结点
Linkedlist*p,*q,*pre:
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
【答案解析】