链表在c语言中通过结构体和指针实现，每个节点包含数据和指向下一个节点的指针；1.定义节点结构体；2.使用指针连接节点；3.实现创建、插入、删除、遍历等操作；4.链表适合频繁插入删除且数据大小动态变化的场景；5.检测环使用快慢指针法；6.反转链表可用迭代或递归方法。
c语言中，链表是通过结构体和指针实现的，它是一种动态数据结构，允许在运行时添加或删除元素，无需预先知道数据的大小。核心在于每个节点包含数据和指向下一个节点的指针。
解决方案：
C语言实现链表的核心在于定义节点结构体，并使用指针连接这些节点。以下是一个简单的单链表实现，包括创建、插入、删除和遍历等基本操作：
立即学习“C语言免费学习笔记（深入）”；
#include <stdio.h> #include <stdlib.h> // 定义链表节点结构体 typedef struct Node { int data; // 数据域 struct Node* next; // 指针域，指向下一个节点 } Node; // 创建新节点 Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); // 动态分配内存 if (newNode == NULL) { perror("Failed to allocate memory"); exit(EXIT_FAILURE); } newNode->data = data; newNode->next = NULL; // 新节点是尾节点，next指向NULL return newNode; } // 在链表头部插入节点 void insertAtBeginning(Node** head, int data) { Node* newNode = createNode(data); newNode->next = *head; // 新节点的next指向原来的头节点 *head = newNode; // 更新头节点为新节点 } // 在链表尾部插入节点 void insertAtEnd(Node** head, int data) { Node* newNode = createNode(data); if (*head == NULL) { // 如果链表为空 *head = newNode; // 新节点成为头节点 return; } Node* current = *head; while (current->next != NULL) { // 找到尾节点 current = current->next; } current->next = newNode; // 尾节点的next指向新节点 } // 在指定位置插入节点（pos从0开始计数） void insertAtPosition(Node** head, int data, int pos) { if (pos < 0) { printf("Invalid position.n"); return; } if (pos == 0) { // 在头部插入，等同于insertAtBeginning insertAtBeginning(head, data); return; } Node* newNode = createNode(data); Node* current = *head; Node* previous = NULL; int i = 0; while (current != NULL && i < pos) { previous = current; current = current->next; i++; } if (i != pos) { // 位置超出链表长度 printf("Position out of range.n"); free(newNode); // 释放已分配的内存 return; } newNode->next = current; previous->next = newNode; } // 删除指定数据的节点（删除第一个匹配的节点） void deleteNode(Node** head, int data) { Node* current = *head; Node* previous = NULL; // 如果链表为空 if (*head == NULL) { return; } // 如果头节点就是要删除的节点 if (current->data == data) { *head = current->next; free(current); return; } // 遍历链表找到要删除的节点 while (current != NULL && current->data != data) { previous = current; current = current->next; } // 如果没找到要删除的节点 if (current == NULL) { return; } // 删除节点 previous->next = current->next; free(current); } // 遍历链表 void printList(Node* head) { Node* current = head; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("n"); } // 释放链表内存 void freeList(Node** head) { Node* current = *head; Node* nextNode; while (current != NULL) { nextNode = current->next; free(current); current = nextNode; } *head = NULL; // 将头指针置空 } int main() { Node* head = NULL; // 初始化头指针 insertAtEnd(&head, 1); insertAtEnd(&head, 2); insertAtEnd(&head, 3); printf("链表内容: "); printList(head); // 输出：1 2 3 insertAtBeginning(&head, 0); printf("头部插入后: "); printList(head); // 输出：0 1 2 3 insertAtPosition(&head, 5, 2); printf("指定位置插入后: "); printList(head); // 输出：0 1 5 2 3 deleteNode(&head, 2); printf("删除节点后: "); printList(head); // 输出：0 1 5 3 freeList(&head); printf("链表释放后: "); printList(head); // 输出：（空） return 0; }
链表和数组的区别是什么？什么时候应该使用链表？
链表和数组是两种常见的数据结构，它们在内存分配、插入删除效率和访问方式上存在显著差异。数组在内存中是连续存储的，因此可以通过索引快速访问任何元素，但插入和删除元素（尤其是在数组中间位置）需要移动大量元素，效率较低。链表则通过指针连接各个节点，节点在内存中可以是不连续的，插入和删除节点只需要修改指针，效率较高，但访问特定位置的元素需要从头节点开始遍历，效率较低。
使用场景：
- 当你需要频繁插入和删除元素，而对元素的访问顺序不敏感时，链表是更好的选择。
- 当你需要快速访问元素，并且元素的数量在编译时已知或很少变化时，数组是更好的选择。
- 当数据量动态变化且难以预估大小时，链表可以避免数组扩容带来的性能开销。
如何检测链表中是否存在环？
检测链表中是否存在环，可以使用快慢指针（Floyd算法）。定义两个指针，一个快指针每次移动两步，一个慢指针每次移动一步。如果链表中存在环，快指针最终会追上慢指针。如果快指针到达链表末尾（NULL），则说明链表中不存在环。
#include <stdbool.h> // 引入 bool 类型 bool hasCycle(Node* head) { if (head == NULL || head->next == NULL) { return false; // 空链表或只有一个节点，不可能有环 } Node* slow = head; Node* fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; // 慢指针走一步 fast = fast->next->next; // 快指针走两步 if (slow == fast) { return true; // 快慢指针相遇，说明有环 } } return false; // 快指针到达链表末尾，说明没有环 }
如何反转一个链表？
反转链表是一个常见的链表操作，可以使用迭代或递归两种方法实现。迭代方法通过修改每个节点的next指针，使其指向前一个节点。递归方法则通过递归调用，逐步将链表反转。
迭代方法：
Node* reverseList(Node* head) { Node* prev = NULL; Node* current = head; Node* next = NULL; while (current != NULL) { next = current->next; // 保存下一个节点 current->next = prev; // 当前节点的next指向前一个节点 prev = current; // 前一个节点更新为当前节点 current = next; // 当前节点更新为下一个节点 } return prev; // prev现在指向新的头节点 }
递归方法：
Node* reverseListRecursive(Node* head) { if (head == NULL || head->next == NULL) { return head; // 空链表或只有一个节点，直接返回 } Node* newHead = reverseListRecursive(head->next); // 递归反转后面的链表 head->next->next = head; // 将当前节点的下一个节点的next指向当前节点 head->next = NULL; // 当前节点的next置为NULL return newHead; // 返回新的头节点 }
选择哪种方法取决于个人偏好和具体场景。迭代方法通常更容易理解和调试，而递归方法则更简洁，但可能涉及更多的函数调用开销。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
