欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2.3.2单链表基本操作(不带头节点)

程序员文章站 2024-03-21 14:49:34
...

注意:以下是不带头节点操作

// 插入(按位序插入)(在前驱节点后插入)
bool ListInsert(LinkList &L, int i, ElemType e) {
    LNode *s, *p;
    int j = 1;
    if (i < 1)
        return false;
    if (L == NULL)
        return false;
    if (i == 1) { // 因为首节点无前驱(即头节点),所以需要特殊处理
        s = (LNode *) malloc(sizeof(LNode));
        s->next = L->next;
        L = s;
        return true;
    }
    p = L; // p指针指向首节点
    while (p != NULL && j < i - 1) { // 寻找待插入节点的前驱
        p = p->next;
        j++;
    }
    if (p == NULL)
        return false;
    s = (LNode *) malloc(sizeof(LNode));
    if (s == NULL)
        return false; // 申请空间失败
    s->next = p->next;
    s->data = e;
    p->next = s;
    return true;
}


// 删除(按位序删除)
bool ListDel(LinkList &L, int i, ElemType &e) {
    LNode *p, *q;
    int j = 1;
    if (i < 1)
        return false; // 删除位置不合法
    if (L == NULL) // 表为空表
        return false;
    if (i == 1) { // 因为首节点无前驱(即头节点),所以需要特殊处理
        e = L->data;
        q = L->next;
        L = q;
        return true;
    }
    p = L; // p指针指向首节点
    while (p != NULL && j < i - 1) { // 寻找待删除节点的前驱
        p = p->next;
        j++;
    }
    // p == NULL || p->next == NULL 顺序不能颠倒
    // 删除位置分别考虑>=length+1,=length
    if (p == NULL || p->next == NULL)
        return false;
    q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

2.3.2 单链表基本操作(带头节点)