devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

双链表的创建，按需删除等操作（可运行c语言源代码）_双链表的删除与输出

作者：知新_RL | 2024-04-20 09:01:39

赞

踩

双链表的删除与输出

目录

一、双链表

1.1定义

1.2图解

二、代码

1.1双链表的创建

1.2输出双链表

1.3双链表的删除（进阶）

1.4全部代码（本地直接运行这个）

一、双链表

1.1定义

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点(插入、删除操作时)，只能从头开始遍历，访问后继结点的时间复杂度o(1)，访问前驱结点的时间复杂度为 o(n)。为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针 prior 和 next，分别指向其前驱结点和后继结点，

1.2图解

双链表：

双链表的插入：

双链表的删除：

二、代码

1.1双链表的创建

  1. // 创建双链表的函数
  2. struct Node* createLinkedList(int arr[], int size) {
  3.     struct Node* head = NULL; // 头指针初始化为 NULL
  4.     struct Node* tail = NULL; // 尾指针初始化为 NULL
  5.  
  6.     // 遍历数组并创建节点
  7.     for (int i = 0; i < size; i++) {
  8.         // 为新节点分配内存空间
  9.         struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  10.         newNode->data = arr[i]; // 设置新节点的数据值
  11.         newNode->next = NULL; // 新节点的后继节点指针初始化为 NULL
  12.  
  13.         // 处理链表头尾
  14.         if (head == NULL) {
  15.             // 如果链表为空，将新节点设置为头节点和尾节点
  16.             head = newNode;
  17.             tail = newNode;
  18.         } else {
  19.             // 如果链表不为空，将新节点链接到尾部，并更新尾节点指针
  20.             tail->next = newNode; // 当前尾节点的后继节点指向新节点
  21.             newNode->prev = tail; // 新节点的前驱节点指向当前尾节点
  22.             tail = newNode; // 更新尾节点指针为新节点
  23.         }
  24.     }
  25.  
  26.     return head; // 返回链表的头指针
  27. }

1.2输出双链表

  1. // 输出节点数值的函数
  2. void printNodeValues(struct Node* head) {
  3.     printf("当前链表： ");
  4.     while (head != NULL) {
  5.         printf("%d ", head->data);
  6.         head = head->next;
  7.     }
  8.     printf("\n");
  9. }

1.3双链表的删除（进阶）

删除值在 m 到 n 之间的节点

  1. // 删除值在 m 到 n 之间的节点的函数
  2. void deleteNodesInRange(struct Node** headRef, int m, int n) {
  3.     // 从双链表的头部开始遍历
  4.     struct Node* current = *headRef;
  5.  
  6.     while (current != NULL) {
  7.         // 如果当前节点的值在 m 和 n 之间
  8.         if (current->data >= m && current->data <= n) {
  9.             // 如果当前节点有前驱节点，将其指向当前节点的下一个节点
  10.             if (current->prev != NULL) {
  11.                 current->prev->next = current->next;
  12.             }
  13.             // 如果当前节点有后继节点，将其指向当前节点的前驱节点
  14.             if (current->next != NULL) {
  15.                 current->next->prev = current->prev;
  16.             }
  17.             // 释放当前节点的内存空间
  18.             struct Node* temp = current;
  19.             // 将当前节点指针移动到下一个节点
  20.             current = current->next;
  21.             // 释放当前节点的内存空间
  22.             free(temp);
  23.         } else {
  24.             // 如果当前节点的值不在 m 和 n 之间，继续遍历下一个节点
  25.             current = current->next;
  26.         }
  27.     }
  28. }

1.4全部代码（本地直接运行这个）

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // 双链表节点结构
  5. struct Node {
  6.     int data;
  7.     struct Node* prev;
  8.     struct Node* next;
  9. };
  10.  
  11. // 创建双链表的函数
  12. struct Node* createLinkedList(int arr[], int size) {
  13.     struct Node* head = NULL; // 头指针初始化为 NULL
  14.     struct Node* tail = NULL; // 尾指针初始化为 NULL
  15.  
  16.     // 遍历数组并创建节点
  17.     for (int i = 0; i < size; i++) {
  18.         // 为新节点分配内存空间
  19.         struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  20.         newNode->data = arr[i]; // 设置新节点的数据值
  21.         newNode->next = NULL; // 新节点的后继节点指针初始化为 NULL
  22.  
  23.         // 处理链表头尾
  24.         if (head == NULL) {
  25.             // 如果链表为空，将新节点设置为头节点和尾节点
  26.             head = newNode;
  27.             tail = newNode;
  28.         } else {
  29.             // 如果链表不为空，将新节点链接到尾部，并更新尾节点指针
  30.             tail->next = newNode; // 当前尾节点的后继节点指向新节点
  31.             newNode->prev = tail; // 新节点的前驱节点指向当前尾节点
  32.             tail = newNode; // 更新尾节点指针为新节点
  33.         }
  34.     }
  35.  
  36.     return head; // 返回链表的头指针
  37. }
  38.  
  39. // 删除值在 m 到 n 之间的节点的函数
  40. void deleteNodesInRange(struct Node** headRef, int m, int n) {
  41.     // 从双链表的头部开始遍历
  42.     struct Node* current = *headRef;
  43.  
  44.     while (current != NULL) {
  45.         // 如果当前节点的值在 m 和 n 之间
  46.         if (current->data >= m && current->data <= n) {
  47.             // 如果当前节点有前驱节点，将其指向当前节点的下一个节点
  48.             if (current->prev != NULL) {
  49.                 current->prev->next = current->next;
  50.             }
  51.             // 如果当前节点有后继节点，将其指向当前节点的前驱节点
  52.             if (current->next != NULL) {
  53.                 current->next->prev = current->prev;
  54.             }
  55.             // 释放当前节点的内存空间
  56.             struct Node* temp = current;
  57.             // 将当前节点指针移动到下一个节点
  58.             current = current->next;
  59.             // 释放当前节点的内存空间
  60.             free(temp);
  61.         } else {
  62.             // 如果当前节点的值不在 m 和 n 之间，继续遍历下一个节点
  63.             current = current->next;
  64.         }
  65.     }
  66. }
  67.  
  68. // 输出节点数值的函数
  69. void printNodeValues(struct Node* head) {
  70.     printf("当前链表： ");
  71.     while (head != NULL) {
  72.         printf("%d ", head->data);
  73.         head = head->next;
  74.     }
  75.     printf("\n");
  76. }
  77.  
  78. int main() {
  79.     int arr[] = {1, 2, 3, 4, 5};
  80.     int size = sizeof(arr) / sizeof(arr[0]);
  81.  
  82.     printf("正在创建双链表...\n");
  83.     struct Node* head = createLinkedList(arr, size);
  84.     printNodeValues(head); // 调用新的输出函数
  85.     int m = 2; // 设定要删除的范围
  86.     int n = 4;
  87.  
  88.     printf("正在删除数值在 %d 到 %d 之间的节点...\n", m, n);
  89.     deleteNodesInRange(&head, m, n);
  90.  
  91.     printNodeValues(head); // 调用新的输出函数
  92.     printf("\n");
  93.  
  94.     return 0;
  95. }

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/456489
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号