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

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

// 插入(按位序插入)(在前驱节点后插入)
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 单链表基本操作(带头节点)

上一篇:1.2 单链表


下一篇:递归算法-删除不带头结点的单链表中所有值为x的结点(后继结点删法)