在C语言中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表可以是单向的，也可以是双向的，甚至是循环的。链表的基本操作包括创建节点、插入节点、删除节点、查找节点、遍历链表等。下面我将详细介绍如何用C语言实现单链表的基本操作。
1. 定义链表节点
首先，我们需要定义一个结构体来表示链表的节点：
#include
#include
// 定义链表节点结构体
typedef struct Node {
int data; // 数据域
struct Node* next; // 指针域，指向下一个节点
} Node;
2. 创建新节点
创建新节点的函数需要接收数据，并返回一个新节点的指针：
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 分配内存
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data; // 设置数据
newNode->next = NULL; // 新节点的下一个节点为空
return newNode;
}
3. 插入节点
插入节点可以有多种方式，这里我们实现在链表末尾插入节点：
void insertNode(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; // 将新节点插入链表末尾
}
}
4. 删除节点
删除节点通常需要找到要删除的节点的前一个节点：
void deleteNode(Node** head, int key) {
Node* temp = *head, *prev = NULL;
if (temp != NULL && temp->data == key) {
*head = 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);
}
5. 遍历链表
遍历链表是查看链表中所有元素的简单方法：
void printList(Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
6. 主函数
在主函数中，我们可以创建链表，插入和删除节点，并打印链表：
int main() {
Node* head = NULL;
insertNode(&head, 1);
insertNode(&head, 2);
insertNode(&head, 3);
insertNode(&head, 4);
printf("Created Linked List: ");
printList(head);
deleteNode(&head, 2);
printf("Linked List after deleting 2: ");
printList(head);
return 0;
}
【拓展】链表的排序功能
插入排序算法
插入排序的基本思想是：遍历链表，将每个节点按顺序插入到一个新的链表中，确保新链表是有序的。对于链表来说，插入排序特别合适，因为它不需要随机访问，而链表的节点插入操作相对简单。
定义链表节点
首先，我们定义链表节点的结构体：
#include
#include
typedef struct Node {
int data;
struct Node* next;
} Node;
创建新节点
创建新节点的函数：
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
插入排序函数
实现插入排序的函数：
void insertNodeSorted(Node** head, int data) {
Node* newNode = createNode(data);
Node* current;
Node* prev;
// 如果链表为空或新节点的数据小于等于头节点的数据
if (*head == NULL || (*head)->data >= newNode->data) {
newNode->next = *head;
*head = newNode;
return;
}
// 找到插入点
current = *head;
while (current->next != NULL && current->next->data < newNode->data) {
current = current->next;
}
// 插入新节点
newNode->next = current->next;
current->next = newNode;
}
打印链表
打印链表的函数：
void printList(Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
主函数
在主函数中，我们可以创建多个节点，并将它们插入到链表中，然后打印排序后的链表：
int main() {
Node* head = NULL;
insertNodeSorted(&head, 5);
insertNodeSorted(&head, 3);
insertNodeSorted(&head, 2);
insertNodeSorted(&head, 4);
insertNodeSorted(&head, 1);
printf("Sorted Linked List: ");
printList(head);
return 0;
}
实训项目：
C语言实现链表排序功能实训-CSDN博客