您当前的位置:首页 > 计算机 > 编程开发 > C语言

删除带头结点的单链表中的最小值节点

时间:01-03来源:作者:点击数:

问题描述:

试编写在带头结点的单链表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)。

若本题改为不带头结点的单链表,则实现上会有所不同,留给读者自行思考。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门