c 链表 c双链表

链表是一种基础且重要的数据结构，它在计算机科学中扮演着关键角色，特别是在C语言这样的低级编程语言中。链表不同于数组，因为它的元素不连续存储在内存中，而是通过指针链接在一起。这里我们将深入探讨C语言中的单链表和双链表。 ## 1. 单链表 单链表由一系列节点组成，每个节点包含两部分：数据域（存储实际信息）和指针域（指向下一个节点的地址）。在C语言中，我们可以定义一个结构体来表示链表节点： ```c typedef struct Node { int data; // 数据域 struct Node* next; // 指针域，指向下一个节点 } Node; ``` ### 1.1 创建链表 创建链表通常从头节点开始，然后通过插入节点来扩展链表。插入操作可以在链表的开头（头部插入）或末尾（尾部插入）进行： ```c Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->next = NULL; return newNode; } // 头部插入 void insertAtStart(Node** head, int data) { Node* newNode = createNode(data); newNode->next = *head; *head = newNode; } // 尾部插入 void insertAtEnd(Node** head, int data) { Node* newNode = createNode(data); if (*head == NULL) { *head = newNode; } else { Node* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } } ``` ### 1.2 查找、删除和遍历链表 查找特定元素，删除特定节点，以及遍历链表都是链表操作的基本部分： ```c // 查找节点 Node* search(Node* head, int target) { Node* temp = head; while (temp != NULL && temp->data != target) { temp = temp->next; } return temp; // 返回找到的节点或NULL } // 删除节点 void deleteNode(Node** head, int target) { Node* temp = *head; Node* prev = NULL; if (temp != NULL && temp->data == target) { *head = temp->next; free(temp); return; } while (temp != NULL && temp->data != target) { prev = temp; temp = temp->next; } if (temp == NULL) return; prev->next = temp->next; free(temp); } // 遍历链表 void traverse(Node* head) { Node* temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } ``` ## 2. 双链表 双链表与单链表相似，但每个节点还包含一个指向前一个节点的指针，这使得在链表中向前和向后移动变得更容易。在C语言中，双链表的节点定义如下： ```c typedef struct DoublyNode { int data; struct DoublyNode* prev; // 指向前一个节点 struct DoublyNode* next; // 指向下一个节点 } DoublyNode; ``` ### 2.1 双链表操作 创建、插入、查找、删除和遍历双链表的操作与单链表类似，但需要处理前向和后向指针： ```c DoublyNode* createDoublyNode(int data) { DoublyNode* newNode = (DoublyNode*)malloc(sizeof(DoublyNode)); newNode->data = data; newNode->prev = NULL; newNode->next = NULL; return newNode; } // 头部插入 void insertAtStartDoubly(DoublyNode** head, int data) { DoublyNode* newNode = createDoublyNode(data); if (*head != NULL) { newNode->next = *head; (*head)->prev = newNode; } *head = newNode; } // 尾部插入 void insertAtEndDoubly(DoublyNode** head, int data) { DoublyNode* newNode = createDoublyNode(data); if (*head == NULL) { *head = newNode; } else { DoublyNode* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; newNode->prev = temp; } } // 删除节点 void deleteDoublyNode(DoublyNode** head, int target) { DoublyNode* temp = *head; DoublyNode* prev = NULL; if (temp != NULL && temp->data == target) { if (temp->next != NULL) { temp->next->prev = NULL; } *head = temp->next; free(temp); return; } while (temp != NULL && temp->data != target) { prev = temp; temp = temp->next; } if (temp == NULL) return; if (prev != NULL) { prev->next = temp->next; } else { *head = temp->next; } if (temp->next != NULL) { temp->next->prev = prev; } free(temp); } // 遍历链表 void traverseDoubly(DoublyNode* head) { DoublyNode* temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } ``` ## 总结 C语言中的链表和双链表是实现动态数据结构的关键工具。它们在内存管理上提供了更大的灵活性，尤其是在处理大量数据时。理解和掌握链表的基本操作（创建、插入、查找、删除和遍历）是成为熟练的C程序员的重要一步。在实际编程中，链表可以被用于实现各种复杂的数据结构，如栈、队列、树等，因此对链表的理解和应用是至关重要的。