首页 > 编程笔记 > C语言笔记 阅读：613

C语言链表

通义灵码
C语言中的链表是一种非常重要的数据结构，它可以动态地分配内存空间，实现高效的数据操作。链表由一系列的节点构成，每个节点包含了数据和一个指向下一个节点的指针。在本文中，我们将详细介绍 C语言链表的实现方法，同时提供完整的源代码和运行结果。

链表的基本概念

链表是由若干个节点组成的数据结构，每个节点包含两部分：数据和指向下一个节点的指针。链表中的节点可以是任意类型的数据，通常使用结构体来表示。在 C语言中，定义一个链表节点的结构体如下：
  1. struct ListNode {
  2.     int data;           // 节点数据
  3.     struct ListNode* next;  // 指向下一个节点的指针
  4. };
链表中的第一个节点称为头节点，最后一个节点称为尾节点。头节点和尾节点都没有数据，只是为了方便操作而设置的。在链表中插入一个节点，就是将新节点插入到某个节点之后，删除一个节点，就是将该节点从链表中删除，并将其前一个节点的指针指向该节点的下一个节点。

链表的优点是可以动态地分配内存空间，可以在程序运行时动态地添加或删除节点，而且不会浪费内存空间。但是，链表的缺点是访问节点需要遍历整个链表，效率比较低。

链表的实现

下面是 C语言中链表的实现代码，其中包括链表的创建、插入、删除、遍历等操作。我们使用一个简单的整数链表作为例子，完整的源代码如下： 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // 定义链表节点结构体
  5. struct ListNode {
  6.     int data;
  7.     struct ListNode* next;
  8. };
  9.  
  10. // 创建链表
  11. struct ListNode* createList() {
  12.     struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
  13.     head->next = NULL;
  14.     return head;
  15. }
  16.  
  17. // 在链表尾部插入一个节点
  18. void insertNode(struct ListNode* head, int data) {
  19.     struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
  20.     newNode->data = data;
  21.     newNode->next = NULL;
  22.     struct ListNode* p = head;
  23.     while (p->next != NULL) {
  24.         p = p->next;
  25.     }
  26.     p->next = newNode;
  27. }
  28.  
  29. // 删除一个节点
  30. void deleteNode(struct ListNode* head, int data) {
  31.     struct ListNode* p = head->next;
  32.     struct ListNode* pre = head;
  33.     while (p != NULL) {
  34.         if (p->data == data) {
  35.             pre->next = p->next;
  36.             free(p);
  37.             return;
  38.         }
  39.         pre = p;
  40.         p = p->next;
  41.     }
  42. }
  43.  
  44. // 遍历链表
  45. void traverseList(struct ListNode* head) {
  46.     struct ListNode* p = head->next;
  47.     while (p != NULL) {
  48.         printf("%d ", p->data);
  49.         p = p->next;
  50.     }
  51.     printf("\n");
  52. }
  53.  
  54. int main() {
  55.     // 创建链表
  56.     struct ListNode* head = createList();
  57.    
  58.     // 在链表尾部插入节点
  59.     insertNode(head, 1);
  60.     insertNode(head, 2);
  61.     insertNode(head, 3);
  62.     insertNode(head, 4);
  63.     insertNode(head, 5);
  64.    
  65.     // 遍历链表
  66.     traverseList(head);
  67.    
  68.     // 删除节点
  69.     deleteNode(head, 3);
  70.    
  71.     // 遍历链表
  72.     traverseList(head);
  73.    
  74.     return 0;
  75. }
运行结果如下：

1 2 3 4 5
1 2 4 5

在这个例子中，我们首先创建了一个空链表，然后插入了 5 个节点，节点的数据分别为 1、2、3、4 和 5。接着，我们遍历了整个链表，输出了每个节点的数据。然后，我们删除了节点 3，并再次遍历了链表，可以看到节点 3 已经被成功删除。

总结

链表是一种非常重要的数据结构，在 C语言中实现链表也是非常常见的。链表的优点是可以动态地分配内存空间，实现高效的数据操作。

但是，链表的缺点是访问节点需要遍历整个链表，效率比较低。在实际开发中，需要根据实际情况选择使用链表还是其他数据结构。

相关文章