c语言编写链表的建立，插入，删除，取数据元素，倒置等算法

### C语言实现链表的基本操作 #### 1. 链表的创建 链表可以通过动态内存分配的方式创建。以下是单向链表的创建过程： ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点结构体 struct Node { int data; struct Node* next; }; // 创建新节点并初始化 struct Node* createNode(int value) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (!newNode) { printf("Memory error\n"); exit(0); } newNode->data = value; newNode->next = NULL; return newNode; } ``` 上述代码展示了如何通过 `malloc` 函数为一个新的节点分配空间，并将其数据字段设置为目标值[^3]。 --- #### 2. 插入操作 插入可以分为多种情况，比如在头部插入、尾部插入或者指定位置插入。以下是一个简单的头插法示例： ```c void insertAtHead(struct Node** headRef, int newValue) { struct Node* newNode = createNode(newValue); newNode->next = *headRef; *headRef = newNode; } ``` 此函数实现了在链表头部插入一个新节点的功能。 对于尾部插入，则需要遍历到链表末尾再执行插入动作： ```c void insertAtTail(struct Node** headRef, int newValue) { struct Node* newNode = createNode(newValue); if (*headRef == NULL) { *headRef = newNode; return; } struct Node* current = *headRef; while (current->next != NULL) { current = current->next; } current->next = newNode; } ``` --- #### 3. 删除操作 删除某个特定值的节点可以从链表中移除第一个匹配项： ```c void deleteNode(struct Node** headRef, int key) { struct Node* temp = *headRef; struct Node* prev = NULL; if (temp != NULL && temp->data == key) { *headRef = temp->next; free(temp); return; } while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } if (temp == NULL) return; prev->next = temp->next; free(temp); } ``` 这段代码处理了两种特殊情况：目标节点位于链表开头或不存在于链表中的情形。 --- #### 4. 获取数据元素 为了访问链表中的第 n 个元素，可以设计如下辅助函数： ```c int getElementByIndex(struct Node* head, int index) { struct Node* current = head; int count = 0; while (current != NULL) { if (count == index) { return current->data; } count++; current = current->next; } printf("Index out of bounds.\n"); return -1; // 或者抛出异常 } ``` 该逻辑会逐一遍历链表直至找到索引对应的节点。 --- #### 5. 反转链表 链表反转有多种方法可供选择，其中一种常见的是迭代方式： ```c struct Node* reverseListIterative(struct Node* head) { struct Node* previous = NULL; struct Node* current = head; struct Node* nextTemp = NULL; while (current != NULL) { nextTemp = current->next; current->next = previous; previous = current; current = nextTemp; } return previous; } ``` 这种方法利用三个指针完成整个翻转流程[^4]。 另一种更简洁但可能较难理解的方法是递归版本： ```c struct Node* reverseListRecursive(struct Node* node) { if (node == NULL || node->next == NULL) { return node; } struct Node* rest = reverseListRecursive(node->next); node->next->next = node; node->next = NULL; return rest; } ``` 它基于分治思想逐步构建新的逆序列表。 --- ### 总结 以上介绍了使用C语言实现链表的主要功能模块及其核心算法原理。每部分均提供了具体代码片段作为参考依据。