跳至正文
View Categories

2 min read

主要内容 #

  1. 双向链表添加节点
  2. 双向链表删除节点
  3. 双向链表查找节点

1. 双向链表添加节点 #

前面学习了如何创建一个双向链表，本节学习有关双向链表的一些基本操作，即如何在双向链表中添加、删除、查找数据元素。
本节知识基于已熟练掌握双向链表创建过程的基础上，我们继续199节所创建的双向链表来学习本节内容，创建好的双向链表如下图所示：

根据数据添加到双向链表中的位置不同，可细分为以下 3 种情况：
1) 添加至表头
将新数据元素添加到表头，只需要将该元素与表头元素建立双层逻辑关系即可。
换句话说，假设新元素节点为 temp，表头节点为 head，则需要做以下 2 步操作即可：

  1. temp->next=head; head->prior=temp;
  2. 将 head 移至 temp，重新指向新的表头；

例如，将新元素 7 添加至双链表的表头，则实现过程如下图所示：

2) 添加至表的中间位置
同单链表添加数据类似，双向链表中间位置添加数据需要经过以下 2 个步骤，如下图所示：

  1. 新节点先与其直接后继节点建立双层逻辑关系；
  2. 新节点的直接前驱节点与之建立双层逻辑关系；


3) 添加至表尾
与添加到表头是一个道理，实现过程如下（如下图所示）：

  1. 找到双链表中最后一个节点；
  2. 让新节点与最后一个节点进行双层逻辑关系；


因此，我们可以试着编写双向链表添加数据的 C 语言代码，参考代码如下：

Line* insertLine(Line* head, int data, int add) {
    //新建数据域为data的结点
    Line* temp = (Line*)malloc(sizeof(Line));
    temp->data = data;
    temp->prior = NULL;
    temp->next = NULL;
    //插入到链表头，要特殊考虑
    if (add == 1) {
        temp->next = head;
        head->prior = temp;
        head = temp;
    }
    else {
        int i;
        Line* body = head;
        //找到要插入位置的前一个结点
        for (i = 1; i < add - 1; i++) {
            body = body->next;
            //只要 body 不存在，表明插入位置输入错误
            if (!body) {
                printf("插入位置有误！\n");
                return head;
            }
        }
        //判断条件为真，说明插入位置为链表尾，实现第 2 种情况
        if (body && (body->next == NULL)) {
            body->next = temp;
            temp->prior = body;
        }
        else {
            //第 2 种情况的具体实现
            body->next->prior = temp;
            temp->next = body->next;
            body->next = temp;
            temp->prior = body;
        }
    }
    return head;
}

2. 双向链表删除节点 #

和添加结点的思想类似，在双向链表中删除目标结点也分为 3 种情况。
1) 删除表头结点
删除表头结点的过程如下图所示：

删除表头结点的实现过程是：

  1. 新建一个指针指向表头结点；
  2. 断开表头结点和其直接后续结点之间的关联，更改 head 头指针的指向，同时将其直接后续结点的 prior 指针指向 NULL；
  3. 释放表头结点占用的内存空间。

2) 删除表中结点
删除表中结点的过程如下图所示：

删除表中结点的实现过程是：

  1. 找到目标结点，新建一个指针指向改结点；
  2. 将目标结点从链表上摘除；
  3. 释放该结点占用的内存空间。

3) 删除表尾结点
删除表尾结点的过程如下图所示：

删除表尾结点的实现过程是：

  1. 找到表尾结点，新建一个指针指向该结点；
  2. 断点表尾结点和其直接前驱结点的关联，并将其直接前驱结点的 next 指针指向 NULL；
  3. 释放表尾结点占用的内存空间。

双向链表删除节点的 C 语言实现代码如下：

//删除结点的函数，data为要删除结点的数据域的值
Line* delLine(Line* head, int data) {
    Line* temp = head;
    while (temp) {
        if (temp->data == data) {
            //删除表头结点
            if (temp->prior == NULL) {
                head = head->next;
                if (head) {
                    head->prior = NULL;
                    temp->next = NULL;
                }
                free(temp);
                return head;
            }
            //删除表中结点
            if (temp->prior && temp->next) {
                temp->next->prior = temp->prior;
                temp->prior->next = temp->next;
                free(temp);
                return head;
            }
            //删除表尾结点
            if (temp->next == NULL) {
                temp->prior->next = NULL;
                temp->prior = NULL;
                free(temp);
                return head;
            }
        }
        temp = temp->next;
    }
    printf("表中没有目标元素，删除失败\n");
    return head;
}

3. 双向链表查找节点 #

常情况下，双向链表和单链表一样都仅有一个头指针。因此，双链表查找指定元素的实现同单链表类似，也是从表头依次遍历表中元素。
C 语言实现代码为：

//head为原双链表，elem表示被查找元素
int selectElem(line * head,int elem){
//新建一个指针t，初始化为头指针 head
    line * t=head;
    int i=1;
    while (t) {
        if (t->data==elem) {
            return i;
        }
        i++;
        t=t->next;
    }
    //程序执行至此处，表示查找失败
    return -1;
}
What are your Feelings