前言链表（Linked List）是一种常见的数据结构，它允许我们动态地分配内存，并通过指针将元素链接在一起。在C语言中，链表通常通过结构体（struct）和指针来实现。下面，我将为你详细解释链表的基本概念以及如何在C语言中实现链表。
链表的基本概念节点（Node）：链表中的每一个元素都称为一个节点。节点通常包含一个数据域（用于存储数据）和一个指针域（用于指向下一个节点）。头节点（Head Node）：链表的第一个节点，通常包含一个特殊的指针（如NULL）作为链表的结束标志。尾节点（Tail Node）：链表的最后一个节点，其指针域通常指向NULL。单向链表（Single Linked List）：每个节点只包含一个指向下一个节点的指针。双向链表（Doubly Linked List）：每个节点包含两个指针，一个指向下一个节点，另一个指向前一个节点。示例C语言实现单向链表下面是一个简单的单向链表的C语言实现：
代码语言：javascript复制#include
#include
// 定义链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed\n");
exit(0);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 在链表末尾添加节点
void appendNode(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;
}
}
// 打印链表
void printList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
Node* head = NULL;
appendNode(&head, 1);
appendNode(&head, 2);
appendNode(&head, 3);
printList(head); // 输出: 1 2 3
return 0;
}这个示例中，我们定义了一个Node结构体来表示链表的节点，并提供了创建新节点、在链表末尾添加节点和打印链表的函数。在main函数中，我们创建了一个链表并添加了三个节点，然后打印出链表的内容。
C语言实现双向链表在C语言中实现双向链表（Doubly Linked List）与实现单向链表类似，但每个节点需要包含两个指针：一个指向下一个节点（next），另一个指向前一个节点（prev）。下面是一个简单的双向链表实现示例：
代码语言：javascript复制#include
#include
// 定义双向链表节点结构体
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
} Node;
// 创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed\n");
exit(0);
}
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL; // 双向链表节点还需要初始化prev为NULL
return newNode;
}
// 在链表末尾添加节点
void appendNode(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;
newNode->prev = temp; // 双向链表需要设置prev指针
}
}
// 在链表开头添加节点
void prependNode(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode; // 更新头节点的prev指针
*head = newNode; // 更新头指针
}
}
// 打印链表
void printList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// 清理链表内存
void freeList(Node* head) {
Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}
int main() {
Node* head = NULL;
appendNode(&head, 1);
appendNode(&head, 2);
prependNode(&head, 0); // 在开头添加节点
printList(head); // 输出: 0 1 2
freeList(head); // 释放链表内存
return 0;
}在这个示例中，我们定义了一个Node结构体来表示双向链表的节点，包含了data、next和prev三个成员。createNode函数用于创建新节点，并初始化next和prev为NULL。appendNode函数用于在链表末尾添加节点，同时更新了新节点的prev指针。prependNode函数用于在链表开头添加节点，同时更新了新节点的next指针和头节点的prev指针。printList函数用于打印链表的内容，只遍历next指针。最后，freeList函数用于释放链表占用的内存。
注意，在添加或删除节点时，需要确保正确更新相关节点的prev和next指针，以避免链表断开或形成环。同时，在释放链表内存时，也要确保遍历整个链表并释放每个节点的内存。