数据结构——双向循环链表

avatar
作者
筋斗云
阅读量:1

文章目录

1. 概念

2. 区别

2.1 结构上的区别

2.2 访问方式区别

2.3 优缺点对比

3. 流程

4. 基本操作

节点和结构定义

初始化单向循环链表

插入节点

删除节点

获取指定位置的元素

修改指定位置的元素

释放单向循环链表的内存

打印所有元素

5. 代码示例

1. 概念

双向循环链表是一种链表数据结构，其中每个节点包含指向前一个节点和下一个节点的指针。与普通双向链表不同，双向循环链表的最后一个节点的后继指针指向头节点，第一个节点的前驱指针指向尾节点，形成一个环。

双向循环链表节点定义

每个节点包含三个部分：数据域、前驱指针域和后继指针域。

typedef struct DNode {     int data;             // 数据域，存储节点的值     struct DNode *prev;   // 前驱指针域，指向前一个节点     struct DNode *next;   // 后继指针域，指向后一个节点 } DNode;

双向循环链表结构定义

双向循环链表包含一个头指针和链表中的节点个数。

typedef struct {     DNode *head; // 指向双向循环链表的头节点     size_t size; // 双向循环链表中的节点个数 } DoublyCircularLinkedList;

2. 区别

2.1 结构上的区别

双向链表（Doubly Linked List）：

  • 每个节点包含一个数据域、一个指向前一个节点的指针和一个指向下一个节点的指针。
  • 头节点的前驱指针指向 NULL，尾节点的后继指针指向 NULL。
  • 只能从头节点到尾节点单向遍历，也可以从尾节点到头节点单向遍历。

双向循环链表（Doubly Circular Linked List）：

  • 每个节点也包含一个数据域、一个指向前一个节点的指针和一个指向下一个节点的指针。
  • 头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点，形成一个环。
  • 可以从任意节点开始遍历，最终会回到该节点。

2.2 访问方式区别

双向链表：

  • 可以从头节点向尾节点单向遍历，也可以从尾节点向头节点单向遍历。

双向循环链表：

  • 可以从任意节点开始双向遍历，最终会回到该节点，因此在循环中进行操作时更加方便。

2.3 优缺点对比

双向链表的优缺点

优点：

  1. 双向遍历：可以从任一节点向前和向后遍历。
  2. 删除操作更高效：在已知节点的情况下，删除节点时不需要知道其前驱节点，因为可以通过节点本身直接访问其前驱节点和后继节点。

缺点：

  1. 实现和维护复杂：比单向链表复杂，需要处理更多的指针操作。
  2. 内存占用较大：每个节点包含两个指针，内存占用较单向链表多。

双向循环链表的优缺点

优点：

  1. 双向遍历和循环遍历：不仅可以双向遍历，还可以从任一节点循环遍历。
  2. 删除操作更高效：同双向链表，删除节点时不需要知道其前驱节点。
  3. 循环访问方便：适合需要循环访问数据的应用场景，如约瑟夫环问题。

缺点：

  1. 实现和维护更复杂：需要处理更多的指针操作以及头节点和尾节点的循环链接。
  2. 内存占用较大：每个节点包含两个指针，内存占用较单向链表多。

3. 流程

初始化单向循环链表：

  • 设置头指针为NULL。
  • 设置节点个数为0。

插入新节点：

  • 判断插入位置是否是0。
  • 如果是0，进一步判断链表是否为空：
    • 如果链表为空，新节点指向自己，头指针指向新节点。
    • 如果链表不为空，找到尾节点，新节点指向头节点，头指针指向新节点，尾节点指向新节点。
  • 如果插入位置不是0，找到插入位置的前一个节点，新节点指向前一个节点的后继节点，前一个节点指向新节点。
  • 节点个数加1。

删除节点：

  • 判断删除位置是否是0。
  • 如果是0，保存头节点，进一步判断链表是否只有一个节点：
    • 如果链表只有一个节点，头指针置为NULL。
    • 如果链表有多个节点，找到尾节点，头指针指向头节点的后继节点，尾节点指向新头节点。
  • 如果删除位置不是0，找到删除位置前一个节点，保存要删除的节点，前一个节点指向要删除节点的后继节点。
  • 释放被删除的节点，节点个数减1。

获取指定位置的元素：

  • 判断索引是否合法，如果不合法返回无效索引。
  • 从头节点开始遍历，遍历到目标位置节点，返回节点数据。

修改指定位置的元素：

  • 判断索引是否合法，如果不合法忽略位置。
  • 从头节点开始遍历，遍历到目标位置节点，修改节点数据。

释放单向循环链表内存：

  • 判断链表是否为空，如果为空直接返回。
  • 从头节点开始遍历，保存下一个节点，释放当前节点，继续遍历，直到回到头节点。
  • 头指针置为NULL，节点个数置为0。

4. 基本操作

下面是详细介绍单向循环链表实现中每个函数的功能、参数、操作步骤

节点和结构定义

#include <stdio.h> #include <stdlib.h>  // 单向循环链表节点结构定义 typedef struct Node {     int data;           // 节点存储的数据     struct Node *next;  // 指向下一个节点的指针 } Node;  // 单向循环链表结构定义 typedef struct {     Node *head;         // 单向循环链表头节点指针     size_t size;        // 单向循环链表中的节点个数 } CircularLinkedList;

初始化单向循环链表

// 初始化单向循环链表 void initCircularLinkedList(CircularLinkedList *list) {     list->head = NULL; // 初始化头节点为空     list->size = 0;    // 初始化节点个数为0 }
  • 功能：初始化一个空的单向循环链表。
  • 参数：CircularLinkedList *list，指向需要初始化的链表结构。
  • 操作：
    • 将链表的头节点指针 head 设置为 NULL。
    • 将链表的节点个数 size 设置为 0。

插入节点

// 在指定位置插入元素 void insertAt(CircularLinkedList *list, size_t index, int element) {     if (index > list->size) {         return; // 忽略无效的插入位置     }      Node *newNode = (Node *)malloc(sizeof(Node)); // 创建新节点     newNode->data = element;      if (index == 0) { // 插入位置是头节点         if (list->head == NULL) { // 如果链表为空             newNode->next = newNode;             list->head = newNode;         } else {             Node *tail = list->head;             while (tail->next != list->head) {                 tail = tail->next;             }             newNode->next = list->head;             list->head = newNode;             tail->next = newNode;         }     } else {         Node *prevNode = list->head;         for (size_t i = 0; i < index - 1; i++) {             prevNode = prevNode->next;         }         newNode->next = prevNode->next;         prevNode->next = newNode;     }      list->size++; // 更新节点个数 }
  • 功能：在指定位置插入新节点。
  • 参数：
    • CircularLinkedList *list，指向链表结构。
    • size_t index，插入位置的索引。
    • int element，插入节点的值。
  • 操作：
    • 检查插入位置是否合法，如果不合法则直接返回。
    • 创建一个新节点并赋值。
    • 如果插入位置是头节点：
      • 如果链表为空，设置新节点的 next 指针指向自己，并将 head 指针指向新节点。
      • 如果链表不为空，找到尾节点，设置新节点的 next 指针指向头节点，将 head 指针指向新节点，并更新尾节点的 next 指针指向新节点。
    • 如果插入位置不是头节点，找到插入位置的前一个节点，设置新节点的 next 指针指向前一个节点的后继节点，并更新前一个节点的 next 指针指向新节点。
    • 更新链表的节点个数。

删除节点

// 删除指定位置的元素并返回被删除的元素 int deleteAt(CircularLinkedList *list, size_t index) {     if (index >= list->size) {         return -1; // 忽略无效的删除位置     }      int deletedElement;      if (index == 0) { // 删除位置是头节点         Node *temp = list->head;         if (list->head->next == list->head) { // 如果链表只有一个节点             list->head = NULL;         } else {             Node *tail = list->head;             while (tail->next != list->head) {                 tail = tail->next;             }             list->head = temp->next;             tail->next = list->head;         }         deletedElement = temp->data;         free(temp); // 释放被删除节点的内存     } else {         Node *prevNode = list->head;         for (size_t i = 0; i < index - 1; i++) {             prevNode = prevNode->next;         }         Node *temp = prevNode->next;         prevNode->next = temp->next;         deletedElement = temp->data;         free(temp); // 释放被删除节点的内存     }      list->size--; // 更新节点个数     return deletedElement; }
  • 功能：删除指定位置的节点并返回被删除的节点的值。
  • 参数：
    • CircularLinkedList *list，指向链表结构。
    • size_t index，删除位置的索引。
  • 操作：
    • 检查删除位置是否合法，如果不合法则返回 -1。
    • 如果删除位置是头节点：
      • 保存头节点。
      • 如果链表只有一个节点，将 head 指针置为 NULL。
      • 如果链表有多个节点，找到尾节点，更新头节点指针，并将尾节点的 next 指针指向新的头节点。
      • 释放被删除的头节点，返回其数据。
    • 如果删除位置不是头节点，找到删除位置的前一个节点，保存要删除的节点，更新前一个节点的 next 指针指向要删除节点的后继节点，释放要删除的节点，返回其数据。
    • 更新链表的节点个数。

获取指定位置的元素

// 获取指定位置的元素 int getElementAt(const CircularLinkedList *list, size_t index) {     if (index >= list->size) {         return -1; // 返回无效的索引     }      Node *currentNode = list->head;     for (size_t i = 0; i < index; i++) {         currentNode = currentNode->next;     }      return currentNode->data; // 返回指定位置的元素 }
  • 功能：获取指定位置的节点值。
  • 参数：
    • const CircularLinkedList *list，指向链表结构。
    • size_t index，目标位置的索引。
  • 操作：
    • 检查索引是否合法，如果不合法则返回 -1。
    • 从头节点开始遍历，直到找到目标位置的节点。
    • 返回目标位置节点的值。

修改指定位置的元素

// 修改指定位置的元素 void modifyAt(CircularLinkedList *list, size_t index, int newValue) {     if (index >= list->size) {         return; // 忽略无效的修改位置     }      Node *currentNode = list->head;     for (size_t i = 0; i < index; i++) {         currentNode = currentNode->next;     }      currentNode->data = newValue; // 修改节点的值 }
  • 功能：修改指定位置的节点值。
  • 参数：
    • CircularLinkedList *list，指向链表结构。
    • size_t index，目标位置的索引。
    • int newValue，新值。
  • 操作：
    • 检查索引是否合法，如果不合法则直接返回。
    • 从头节点开始遍历，直到找到目标位置的节点。
    • 修改目标位置节点的值。

释放单向循环链表的内存

// 释放单向循环链表内存 void destroyCircularLinkedList(CircularLinkedList *list) {     if (list->head == NULL) {         return;     }     Node *currentNode = list->head;     Node *nextNode;     do {         nextNode = currentNode->next;         free(currentNode);         currentNode = nextNode;     } while (currentNode != list->head);      list->head = NULL;     list->size = 0; }
  • 功能：释放单向循环链表中所有节点的内存。
  • 参数：CircularLinkedList *list，指向需要释放的链表结构。
  • 操作：
    • 如果链表为空，直接返回。
    • 从头节点开始遍历，每次保存当前节点的下一个节点的指针，释放当前节点的内存。
    • 继续遍历，直到回到头节点。
    • 将链表的头节点指针 head 置为 NULL，将链表的节点个数 size 置为 0。

打印所有元素

// 打印单向循环链表中的所有元素 void printCircularLinkedList(const CircularLinkedList *list) {     if (list->head == NULL) {         printf("链表为空\n");         return;     }     Node *currentNode = list->head;     do {         printf("%d ", currentNode->data);         currentNode = currentNode->next;     } while (currentNode != list->head);     printf("\n"); }
  • 功能：打印单向循环链表中的所有节点值。
  • 参数：const CircularLinkedList *list，指向需要打印的链表结构。
  • 操作：
    • 如果链表为空，打印“链表为空”并返回。
    • 从头节点开始遍历，每次打印当前节点的值。
    • 继续遍历，直到回到头节点。

5. 代码示例

下面是一个完整的双向循环链表实现的代码，包括初始化、插入、删除、获取和修改元素，以及释放链表的内存的所有基本操作。

#include <stdio.h> #include <stdlib.h>  // 双向循环链表节点结构定义 typedef struct DNode {     int data;             // 节点存储的数据     struct DNode *prev;   // 指向前一个节点的指针     struct DNode *next;   // 指向后一个节点的指针 } DNode;  // 双向循环链表结构定义 typedef struct {     DNode *head; // 双向循环链表头节点指针     size_t size; // 双向循环链表中的节点个数 } DoublyCircularLinkedList;  // 初始化双向循环链表 void initDoublyCircularLinkedList(DoublyCircularLinkedList *list) {     list->head = NULL; // 初始化头节点为空     list->size = 0;    // 初始化节点个数为0 }  // 在指定位置插入元素 void insertAt(DoublyCircularLinkedList *list, size_t index, int element) {     if (index > list->size) {         return; // 忽略无效的插入位置     }      DNode *newNode = (DNode *)malloc(sizeof(DNode)); // 创建新节点     newNode->data = element;     newNode->prev = NULL;     newNode->next = NULL;      if (index == 0) { // 插入位置是头节点         if (list->head == NULL) { // 如果链表为空             newNode->next = newNode;             newNode->prev = newNode;             list->head = newNode;         } else {             DNode *tail = list->head->prev;             newNode->next = list->head;             newNode->prev = tail;             list->head->prev = newNode;             tail->next = newNode;             list->head = newNode;         }     } else {         DNode *current = list->head;         for (size_t i = 0; i < index - 1; i++) {             current = current->next;         }         newNode->next = current->next;         newNode->prev = current;         if (current->next != NULL) {             current->next->prev = newNode;         }         current->next = newNode;     }      list->size++; // 更新节点个数 }  // 删除指定位置的元素并返回被删除的元素 int deleteAt(DoublyCircularLinkedList *list, size_t index) {     if (index >= list->size) {         return -1; // 忽略无效的删除位置     }      int deletedElement;      if (index == 0) { // 删除位置是头节点         DNode *temp = list->head;         if (list->head->next == list->head) { // 如果链表只有一个节点             list->head = NULL;         } else {             DNode *tail = list->head->prev;             list->head = temp->next;             list->head->prev = tail;             tail->next = list->head;         }         deletedElement = temp->data;         free(temp); // 释放被删除节点的内存     } else {         DNode *current = list->head;         for (size_t i = 0; i < index - 1; i++) {             current = current->next;         }         DNode *temp = current->next;         current->next = temp->next;         if (temp->next != NULL) {             temp->next->prev = current;         }         deletedElement = temp->data;         free(temp); // 释放被删除节点的内存     }      list->size--; // 更新节点个数     return deletedElement; }  // 获取指定位置的元素 int getElementAt(const DoublyCircularLinkedList *list, size_t index) {     if (index >= list->size) {         return -1; // 返回无效的索引     }      DNode *currentNode = list->head;     for (size_t i = 0; i < index; i++) {         currentNode = currentNode->next;     }      return currentNode->data; // 返回指定位置的元素 }  // 修改指定位置的元素 void modifyAt(DoublyCircularLinkedList *list, size_t index, int newValue) {     if (index >= list->size) {         return; // 忽略无效的修改位置     }      DNode *currentNode = list->head;     for (size_t i = 0; i < index; i++) {         currentNode = currentNode->next;     }      currentNode->data = newValue; // 修改节点的值 }  // 释放双向循环链表内存 void destroyDoublyCircularLinkedList(DoublyCircularLinkedList *list) {     if (list->head == NULL) {         return;     }     DNode *currentNode = list->head;     DNode *nextNode;     do {         nextNode = currentNode->next;         free(currentNode);         currentNode = nextNode;     } while (currentNode != list->head);      list->head = NULL;     list->size = 0; }  // 打印双向循环链表中的所有元素 void printDoublyCircularLinkedList(const DoublyCircularLinkedList *list) {     if (list->head == NULL) {         printf("链表为空\n");         return;     }     DNode *currentNode = list->head;     do {         printf("%d ", currentNode->data);         currentNode = currentNode->next;     } while (currentNode != list->head);     printf("\n"); }  // 主函数测试双向循环链表操作 int main() {     DoublyCircularLinkedList myList; // 声明双向循环链表      initDoublyCircularLinkedList(&myList); // 初始化双向循环链表     printf("初始化双向循环链表成功!\n");      insertAt(&myList, 0, 1); // 在索引0处插入元素1     insertAt(&myList, 1, 2); // 在索引1处插入元素2     insertAt(&myList, 2, 3); // 在索引2处插入元素3     printf("向双向循环链表插入了3个元素\n");     printDoublyCircularLinkedList(&myList); // 打印链表中的元素      printf("双向循环链表长度为: %zu\n", myList.size); // 获取双向循环链表长度      insertAt(&myList, 1, 4); // 在索引1处插入元素4     printf("在索引1处插入元素4\n");     printDoublyCircularLinkedList(&myList); // 打印链表中的元素      printf("双向循环链表长度为: %zu\n", myList.size); // 再次获取双向循环链表长度      printf("删除索引1处的元素,该元素值是: %d\n", deleteAt(&myList, 1)); // 删除索引1处的元素     printDoublyCircularLinkedList(&myList); // 打印链表中的元素      destroyDoublyCircularLinkedList(&myList); // 销毁双向循环链表     printf("双向循环链表销毁成功!\n");      return 0; }

 

相关阅读
  1. 如何查看和设置我的Android N设备的权限？
  2. 如何在安卓手机上自定义应用图标？
  3. 如何在安卓微信中同时听语音和查看图片？
  4. 华为哪些设备将支持升级至安卓7.0？
  5. 微信安卓软件中Q10功能有哪些独特之处？
  6. 安卓用户如何挑选最佳视频播放器应用？
  7. 安卓系统中用户文件目录的确切位置是什么？
  8. 小米4用户如何安全升级到安卓8.0系统？
  9. 如何成功将魅蓝5升级至安卓原生7.0版本？
  10. 16GB存储的安卓手机是否能满足日常需求？

广告一刻

为您即时展示最新活动产品广告消息，让您随时掌握产品活动新动态！