删除带头结点的单链表最小值结点-蒲公英云

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

向右看齐 2023-10-17 23:54 241阅读 0赞

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

王道19数据结构 P44
删除带头结点的单链表最小值结点（假设最小值结点唯一）

书上给的答案无法应对单链表为空的情况
因为指针为空时，无法访问其结构体成员

课本代码

LinkList DelMin(LinkList &L){
    LNode *pre = L, *p=pre->next; //L==NULL时此处报错
    LNode *minpre = pre, *min = p;
    while (p != NULL){
        if (p->data < min->data){
            min = p;
            minpre = pre;
        }
        pre = p;
        p = p->next;
    }
    minpre->next = min->next; //L->next==NULL时此处报错
    free(min);
    return L;
}

改进代码

加入空链表判断

LinkList DelMin(LinkList &L){
    if (L == NULL){
        return NULL;
    }
    if (L ->next == NULL){
        return NULL;
    }
    LNode *pre = L, *p=pre->next;
    LNode *minpre = pre, *min = p;
    while (p != NULL){
        if (p->data < min->data){
            min = p;
            minpre = pre;
        }
        pre = p;
        p = p->next;
    }
    minpre->next = min->next; 
    free(min);
    return L;
}

结构体定义

typedef char ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

打印单链表

void printList(LinkList &L){
    LNode *p = L;
    if (p == NULL){
        printf("NULL1");
    }
    else if (p->next == NULL){
        printf("NULL2");
    }
    else{
        while (p != NULL){
            printf("%c ", p->data);
            p = p->next;
        }
    }
    printf("\n");
}

头文件及主函数

#include <iostream> 
void main(){
    LNode *Head = (LNode*)malloc(sizeof(LNode)); //头结点
    LNode *A = (LNode*)malloc(sizeof(LNode));
    LNode *B = (LNode*)malloc(sizeof(LNode));
    LNode *C = (LNode*)malloc(sizeof(LNode));
    LNode *D = (LNode*)malloc(sizeof(LNode));
    LNode *E = (LNode*)malloc(sizeof(LNode));
    LNode *F = (LNode*)malloc(sizeof(LNode));
    LNode *G = (LNode*)malloc(sizeof(LNode));
    LNode *H = (LNode*)malloc(sizeof(LNode));
    LNode *I = (LNode*)malloc(sizeof(LNode));
    Head->data = '>';    Head->next = A;
    A->data = 'A';    A->next = B;
    B->data = 'B';    B->next = C;
    C->data = 'C';    C->next = D;
    D->data = 'D';    D->next = E;
    E->data = 'E';    E->next = F;
    F->data = 'F';    F->next = G;
    G->data = 'G';    G->next = H;
    H->data = 'H';    H->next = I;
    I->data = 'I';    I->next = NULL;
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L = Head;
    //L->next = NULL;
    //L = NULL;
    DelMin(L);
    printList(L);
}