• C/C++数据结构之深入了解线性表：顺序表、单链表、循环链表和双向链表

    线性表是一种基本的数据结构，它在计算机科学中起着至关重要的作用。线性表用于存储一系列具有相同数据类型的元素，这些元素之间存在顺序关系。在C/C++中，我们可以使用各种方式来实现线性表，其中包括顺序表、单链表、循环链表和双向链表。本篇博客将深入探讨这些数据结构的概念，并通过示例代码进行详细分析。

    什么是线性表？

    线性表是一种抽象数据类型，它表示具有相同数据类型的元素的有序集合。线性表中的元素之间存在明确的线性顺序，通常由一个首元素和一个尾元素界定。线性表的常见操作包括插入、删除、查找和遍历。在C/C++中，线性表可以通过数组或链表来实现。

    顺序表（Array）

    顺序表是一种使用数组来实现的线性表，其中元素在内存中是连续存储的。这使得顺序表具有O(1)时间复杂度的随机访问特性，但在插入和删除操作时可能需要移动大量元素。顺序表的大小通常是固定的，除非重新分配内存。

    顺序表的定义

    在C/C++中，顺序表可以定义如下：

    1. #include 
    2.  
    3. #define MAX_SIZE 100  // 顺序表的最大容量
    4.  
    5. typedef struct {
    6.     int data[MAX_SIZE];  // 数据存储数组
    7.     int length;          // 当前长度
    8. } SeqList;

    顺序表的示例

    以下是一个简单的C程序，用于初始化、插入和遍历顺序表：

    1. #include 
    2.  
    3. #define MAX_SIZE 100
    4.  
    5. typedef struct {
    6.     int data[MAX_SIZE];
    7.     int length;
    8. } SeqList;
    9.  
    10. // 初始化顺序表
    11. void init(SeqList *list) {
    12.     list->length = 0;
    13. }
    14.  
    15. // 在指定位置插入元素
    16. int insert(SeqList *list, int position, int element) {
    17.     if (position < 0 || position > list->length || list->length >= MAX_SIZE) {
    18.         return 0;  // 插入失败
    19.     }
    20.  
    21.     for (int i = list->length; i > position; i--) {
    22.         list->data[i] = list->data[i - 1];
    23.     }
    24.  
    25.     list->data[position] = element;
    26.     list->length++;
    27.     return 1;  // 插入成功
    28. }
    29.  
    30. // 遍历顺序表
    31. void traverse(SeqList *list) {
    32.     for (int i = 0; i < list->length; i++) {
    33.         printf("%d ", list->data[i]);
    34.     }
    35.     printf("\n");
    36. }
    37.  
    38. int main() {
    39.     SeqList list;
    40.     init(&list);
    41.     
    42.     insert(&list, 0, 1);
    43.     insert(&list, 1, 2);
    44.     insert(&list, 2, 3);
    45.  
    46.     traverse(&list);
    47.  
    48.     return 0;
    49. }

    这段代码演示了如何初始化顺序表、在指定位置插入元素以及遍历顺序表。输出将是 1 2 3。

    单链表（Singly Linked List）

    单链表是一种通过节点之间的指针链接来实现的线性表。每个节点包含数据元素和一个指向下一个节点的指针。单链表不要求内存中的节点是连续的，因此插入和删除操作比顺序表更高效。

    单链表的定义

    在C/C++中，单链表可以定义如下：

    1. #include 
    2.  
    3. typedef struct Node {
    4.     int data;           // 数据元素
    5.     struct Node *next;  // 指向下一个节点的指针
    6. } ListNode;
    7.

    单链表的示例

    以下是一个简单的C程序，用于初始化、插入和遍历单链表：

    1. #include 
    2. #include 
    3.  
    4. typedef struct Node {
    5.     int data;
    6.     struct Node *next;
    7. } ListNode;
    8.  
    9. // 初始化单链表
    10. ListNode *init() {
    11.     return NULL;
    12. }
    13.  
    14. // 在链表末尾插入元素
    15. ListNode *insert(ListNode *head, int element) {
    16.     ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    17.     if (newNode == NULL) {
    18.         perror("Memory allocation failed");
    19.         exit(1);
    20.     }
    21.  
    22.     newNode->data = element;
    23.     newNode->next = NULL;
    24.  
    25.     if (head == NULL) {
    26.         return newNode;
    27.     }
    28.  
    29.     ListNode *current = head;
    30.     while (current->next != NULL) {
    31.         current = current->next;
    32.     }
    33.     current->next = newNode;
    34.     return head;
    35. }
    36.  
    37. // 遍历单链表
    38. void traverse(ListNode *head) {
    39.     ListNode *current = head;
    40.     while (current != NULL) {
    41.         printf("%d ", current->data);
    42.         current = current->next;
    43.     }
    44.     printf("\n");
    45. }
    46.  
    47. // 释放单链表的内存
    48. void destroy(ListNode *head) {
    49.     while (head != NULL) {
    50.         ListNode *temp = head;
    51.         head = head->next;
    52.         free(temp);
    53.     }
    54. }
    55.  
    56. int main() {
    57.     ListNode *head = init();
    58.     
    59.     head = insert(head, 1);
    60.     head = insert(head, 2);
    61.     head = insert(head, 3);
    62.  
    63.     traverse(head);
    64.  
    65.     destroy(head);
    66.  
    67.     return 0;
    68. }

    这段代码演示了如何初始化单链表、在链表末尾插入元素以及遍历单链表。输出将是 1 2 3。

    循环链表（Circular Linked List）

    循环链表是一种单链表的变体，其中最后一个节点的指针指向第一个节点，形成一个循环。循环链表可以用于解决环形问题，如约瑟夫问题（Josephus Problem）。

    循环链表的定义

    循环链表的定义与单链表类似，唯一不同之处在于最后一个节点的指针指向第一个节点。

    1. #include 
    2.  
    3. typedef struct Node {
    4.     int data;
    5.     struct Node *next;
    6. } CircularListNode;

    循环链表的示例

    以下是一个简单的C程序，用于初始化、插入和遍历循环链表：

    1. #include 
    2. #include 
    3.  
    4. typedef struct Node {
    5.     int data;
    6.     struct Node *next;
    7. } CircularListNode;
    8.  
    9. // 初始化循环链表
    10. CircularListNode *init() {
    11.     return NULL;
    12. }
    13.  
    14. // 在链表末尾插入元素
    15. CircularListNode *insert(CircularListNode *head, int element) {
    16.     CircularListNode *newNode = (CircularListNode *)malloc(sizeof(CircularListNode));
    17.     if (newNode == NULL) {
    18.         perror("Memory allocation failed");
    19.         exit(1);
    20.     }
    21.  
    22.     newNode->data = element;
    23.     newNode->next = NULL;
    24.  
    25.     if (head == NULL) {
    26.         newNode->next = newNode; // 指向自己形成循环
    27.         return newNode;
    28.     }
    29.  
    30.     CircularListNode *current = head;
    31.     while (current->next != head) {
    32.         current = current->next;
    33.     }
    34.     current->next = newNode;
    35.     newNode->next = head; // 最后一个节点指向头节点形成循环
    36.     return head;
    37. }
    38.  
    39. // 遍历循环链表
    40. void traverse(CircularListNode *head) {
    41.     if (head == NULL) {
    42.         return;
    43.     }
    44.  
    45.     CircularListNode *current = head;
    46.     do {
    47.         printf("%d ", current->data);
    48.         current = current->next;
    49.     } while (current != head);
    50.     printf("\n");
    51. }
    52.  
    53. // 释放循环链表的内存
    54. void destroy(CircularListNode *head) {
    55.     if (head == NULL) {
    56.         return;
    57.     }
    58.  
    59.     CircularListNode *current = head;
    60.     CircularListNode *temp;
    61.     do {
    62.         temp = current;
    63.         current = current->next;
    64.         free(temp);
    65.     } while (current != head);
    66. }
    67.  
    68. int main() {
    69.     CircularListNode *head = init();
    70.     
    71.     head = insert(head, 1);
    72.     head = insert(head, 2);
    73.     head = insert(head, 3);
    74.  
    75.     traverse(head);
    76.  
    77.     destroy(head);
    78.  
    79.     return 0;
    80. }

    这段代码演示了如何初始化循环链表、在链表末尾插入元素以及遍历循环链表。输出将是 1 2 3，并形成循环。

    双向链表（Doubly Linked List）

    双向链表是一种链表，每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。这种结构使得在双向链表中可以轻松地进行双向遍历，但相对于单链表，它需要更多的内存空间来存储额外的指针。

    双向链表的定义

    在C/C++中，双向链表可以定义如下：

    1. #include 
    2.  
    3. typedef struct Node {
    4.     int data;
    5.     struct Node *prev;  // 指向前一个节点的指针
    6.     struct Node *next;  // 指向后一个节点的指针
    7. } DoublyListNode;

    双向链表的示例

    以下是一个简单的C程序，用于初始化、插入和遍历双向链表：

    1. #include 
    2. #include 
    3.  
    4. typedef struct Node {
    5.     int data;
    6.     struct Node *prev;
    7.     struct Node *next;
    8. } DoublyListNode;
    9.  
    10. // 初始化双向链表
    11. DoublyListNode *init() {
    12.     return NULL;
    13. }
    14.  
    15. // 在链表末尾插入元素
    16. DoublyListNode *insert(DoublyListNode *head, int element) {
    17.     DoublyListNode *newNode = (DoublyListNode *)malloc(sizeof(DoublyListNode));
    18.     if (newNode == NULL) {
    19.         perror("Memory allocation failed");
    20.         exit(1);
    21.     }
    22.  
    23.     newNode->data = element;
    24.     newNode->prev = NULL;
    25.     newNode->next = NULL;
    26.  
    27.     if (head == NULL) {
    28.         return newNode;
    29.     }
    30.  
    31.     DoublyListNode *current = head;
    32.     while (current->next != NULL) {
    33.         current = current->next;
    34.     }
    35.     newNode->prev = current;
    36.     current->next = newNode;
    37.     return head;
    38. }
    39.  
    40. // 遍历双向链表（正向）
    41. void traverseForward(DoublyListNode *head) {
    42.     DoublyListNode *current = head;
    43.     while (current != NULL) {
    44.         printf("%d ", current->data);
    45.         current = current->next;
    46.     }
    47.     printf("\n");
    48. }
    49.  
    50. // 遍历双向链表（反向）
    51. void traverseBackward(DoublyListNode *head) {
    52.     DoublyListNode *current = head;
    53.     while (current->next != NULL) {
    54.         current = current->next;
    55.     }
    56.  
    57.     while (current != NULL) {
    58.         printf("%d ", current->data);
    59.         current = current->prev;
    60.     }
    61.     printf("\n");
    62. }
    63.  
    64. // 释放双向链表的内存
    65. void destroy(DoublyListNode *head) {
    66.     DoublyListNode *current = head;
    67.     DoublyListNode *temp;
    68.     while (current != NULL) {
    69.         temp = current;
    70.         current = current->next;
    71.         free(temp);
    72.     }
    73. }
    74.  
    75. int main() {
    76.     DoublyListNode *head = init();
    77.     
    78.     head = insert(head, 1);
    79.     head = insert(head, 2);
    80.     head = insert(head, 3);
    81.  
    82.     traverseForward(head);
    83.     traverseBackward(head);
    84.  
    85.     destroy(head);
    86.  
    87.     return 0;
    88. }

    这段代码演示了如何初始化双向链表、在链表末尾插入元素以及正向和反向遍历双向链表。输出将是 1 2 3 和 3 2 1。

    了解更多内容获取更多相关资源前往公众号：每日推荐系列

    总结

    线性表是计算机科学中常见的数据结构，用于存储一系列具有相同数据类型的元素。在C/C++中，我们可以使用不同的数据结构来实现线性表，包括顺序表、单链表、循环链表和双向链表。每种数据结构都有其独特的特点和适用场景，根据具体需求选择合适的数据结构是非常重要的。

  • 相关阅读:
    详细指南：使用C语言控制TI ADS1262和ADS1263模数转换器
    SSM框架学习
    lnmp架构之mysql部署
    视频怎么制作成gif动画？这个方法试试看
    linux常用指令
    transformer一统天下？depth-wise conv有话要说
    竞赛选题 深度学习验证码识别 - 机器视觉 python opencv
    【前端学java】Java中的异常处理（15）完结
    计算机操作系统 （王道考研）笔记（三）文件
    jsp交通管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目
  • 原文地址：https://blog.csdn.net/qq_72290695/article/details/134095048