试编写在带头结点的单链表L中删除一个最小值结点的高效算法(假设最小值结点是唯一的)。
算法思想:用p从头至尾扫描单链表,pre指向*p结点的前驱,用minp保存值最小的结点指针(初值为p),minpre指向*minp结点的前驱(初值为pre)。一边扫描,一边比较,若p->dafa小于minp->dara,则将p、pre分别赋值给minp、minpre,如下图所示。当p扫描完毕,minp指向最小值结点,minpre指向最小值结点的前驱结点,再将minp所指结点删除即可。
本题代码如下:
LinkList Delete_Min(LinkList &L){
//L是带头结点的单链表,本算法删除其最小值结点
LNode *pre = L, *p=pre->next; //p 为工作指针,pre 指向其前驱
LNode *minpre=pre, *minp=p; //保存最小值结点及其前驱
while(p!=NULL){
if(p->data<minp->data){
minp=p; //找到比之前找到的最小值结点更小的结点
minpre=pre;
}
pre=p; //继续扫描下一个结点
p=p->next;
}
minpre->next=minp->next; //删除最小值结点
free(minp);
return L;
}
算法需要从头至尾扫描链表,时间复杂度为O(n),空间复杂度为O(1)。
若本题改为不带头结点的单链表,则实现上会有所不同,留给读者自行思考。