DS-4-单链表的各种插入与删除的实现

typedef struct LNode {

    int data;

    struct LNode *next;

}LNode, *LinkList;

带头结点的按位序插入：

//在第i个位置插入元素e

bool ListInsert(LinkList &L, int i, char e) {

    if (i < )

        return false;

    LNode *p;        //p指向当前扫描到的结点

    int j = ;        //当前p指向的是第几个结点

    p = L;            //L指向头结点,第0个结点

    while (p != NULL && j < i - ) {        //循环找到要插入结点的前一个结点

        p = p->next;

        j++;

    }

    if (p == NULL)        //i值不合法（最后一个结点指向NULL，这是要在NULL的后边插入）

        return false;

    LNode *s = （LNode *）malloc（sizeof(LNode)）; //新结点

    s->data = e;

    s->next = p->next;

    p->next = s;

    return true;

}

不带头结点的按位序插入：（对于插入第一个结点时需要特殊处理，其他部分与带头结点的一样）

bool ListInsert(LinkList &L, int i, char e) {

    if (i == ) {

        LNode *s = （LNode *）malloc（sizeof(LNode)）;

        s->data = e;

        s->next = L;

        L = s;

        return true

    }

    if (i < )

        return false;

    LNode *p;        //p指向当前扫描到的结点

    int j = ;        //当前p指向的是第几个结点

    p = L;            //L指向头结点,第0个结点

    while (p != NULL && j < i - ) {        //循环找到要插入结点的前一个结点

        p = p->next;

        j++;

    }

    if (p == NULL)        //i值不合法（最后一个结点指向NULL，这是要在NULL的后边插入）

        return false;

    LNode *s = （LNode *）malloc（sizeof(LNode)）; //新结点

    s->data = e;

    s->next = p->next;

    p->next = s;

    return true;

}

指定结点的后插操作：

//在p结点之后插入元素e

bool InsertNextNode(LNode *p, char e) {

    if (p == NULL)

        return false;

    LNode *s = （LNode *）malloc（sizeof(LNode)）;

    if (s == NULL)

        return false;    //内存分配失败

    s->data = e;

    s->next = p->next;

    p->next = s;

    return true;

}

这里的后插操作其实就相当于已经找到了p，和按位序插入while循环后边的代码一样了，所以按位序插入后边部分可以调用这个函数：

//在第i个位置插入元素e

bool ListInsert(LinkList &L, int i, char e) {

    if (i < )

        return false;

    LNode *p;        //p指向当前扫描到的结点

    int j = ;        //当前p指向的是第几个结点

    p = L;            //L指向头结点,第0个结点

    while (p != NULL && j < i - ) {        //循环找到要插入结点的前一个结点

        p = p->next;

        j++;

    }

　　return InsertNextNode(p,e）
 }

指定结点的前插操作：

如果给了头指针的话，只需要循环查找到要插入结点的前一个结点，然后插入即可

//在p结点之前插入元素e

bool InsertPriorNode(LinkList L, LNode *p, char e)

然而如果不给头指针的话，就需要偷天换日一下，把新结点插入到p结点后边，然后把新结点的数据元素和和p结点互换，逻辑上实现同样的效果

//在p结点之前插入元素e

bool InsertPriorNode(LNode *p, char e) {

    if (p == NULL)

        return false;

    LNode *s = （LNode *）malloc（sizeof(LNode)）;

    if (s == NULL)

        return false;    //内存分配失败

    s->next = p->next;

    p->next = s;

    s->data = p->data;

    p->data = e;

    return true;

}

如果是直接传入了结点s，道理是一样的；

//在p结点之前插入结点s

bool InsertPriorNode(LNode *p, LNode *s) {

    if (p == NULL || s == NULL)

        return false;

    s->next = p->next;

    p->next = s;

    char temp = p->data;

    p->data = s->data;

    s->data = temp;

    return true;

}

按位序删除（带头结点）：

前半部分与插入结点一样，先循环查找p

//删除表L中第i个位置的元素，并用e返回删除元素的值

bool ListDelete(LinkList &L, int i, char &e) {

    if (i < )

        return false;

    LNode *p;        //p指向当前扫描到的结点

    int j = ;        //当前p指向的是第几个结点

    p = L;            //L指向头结点,第0个结点

    while (p != NULL && j < i - ) {

        p = p->next;

        j++;

    }

    if (p == NULL)

        return false;

    if (p->next == NULL)

        return false;

    LNode *q = p->next;    //令q指向被删除的结点

    e = q->data;        //用e返回被删的值

    p->next = q->next;    //断开连接

    free(q);            //释放被删结点空间

    return true;

}

指定结点的删除：

删除结点p，需要修改其前驱结点的next指针
方法1：传入头指针，循环寻找p的前驱结点

方法2：偷天换日（类似于结点前插的实现）

下面是方法2的代码实现：

//删除指定结点p

bool DeleteNode(LNode *p) {

    if (p == NULL)

        return false;

    LNode *q = p->next;        //令q指向*p的后继结点

    p->data = p->next->data;

    p->next = q->next;

    free(q);

    return true;

}

如果p是最后一个结点就只能从表头开始依次寻找p的前驱...

巴特西

DS-4-单链表的各种插入与删除的实现

最新文章

热门文章