1 引言数组有一个明显的缺点插入或删除元素时需要移动大量数据。例如在数组开头插入一个元素需要将所有元素向后移动一位。c/* 数组在开头插入元素需要移动所有元素 */ for (int i size; i 0; i--) { arr[i] arr[i-1]; } arr[0] new_value;链表通过指针连接各个节点插入和删除只需修改指针不需要移动数据。c/* 链表的节点结构 */ typedef struct Node { int data; /* 数据域 */ struct Node *next; /* 指针域指向下一个节点 */ } Node;每个节点包含数据和指向下一个节点的指针最后一个节点的指针为NULL。这种结构就是单向链表。2 链表节点的结构体定义2.1 节点结构单向链表节点包含两个部分数据域存储实际数据可以是任意类型指针域指向下一个节点ctypedef struct Node { int data; /* 数据域 */ struct Node *next; /* 指针域 */ } Node;注意在结构体内部不能直接用Node*因为Node这个类型名还没有定义完成必须用struct Node*。2.2 带头节点 vs 不带头节点链表有两种常见形式类型特点优点缺点带头节点有一个不存储数据的头节点操作统一不需要单独处理空链表多占用一个节点空间不带头节点头指针直接指向第一个数据节点节省空间插入删除需要单独处理头指针变化本章使用不带头节点的方式更直观地理解指针操作。cNode *head NULL; /* 空链表头指针指向 NULL */2.3 头指针的作用头指针指向链表的第一个节点是整个链表的入口。texthead ↓ ┌─────┐ ┌─────┐ ┌─────┐ │ data│ → │ data│ → │ data│ → NULL │ next│ │ next│ │ next│ └─────┘ └─────┘ └─────┘3 动态创建节点3.1 创建新节点c#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; /* 创建新节点 */ Node* create_node(int value) { Node *new_node (Node*)malloc(sizeof(Node)); if (new_node NULL) { printf(内存分配失败\n); return NULL; } new_node-data value; new_node-next NULL; return new_node; }3.2 头插法在链表头部插入新节点c/* 头插法新节点成为新的头节点 */ Node* insert_head(Node *head, int value) { Node *new_node create_node(value); if (new_node NULL) return head; new_node-next head; /* 新节点指向原来的头节点 */ return new_node; /* 新节点成为新的头节点 */ }执行过程text原链表head → [10] → [20] → NULL 插入 5new_node → [5] → head (指向[10]) 结果head → [5] → [10] → [20] → NULL3.3 尾插法在链表尾部插入新节点c/* 尾插法新节点添加到末尾 */ Node* insert_tail(Node *head, int value) { Node *new_node create_node(value); if (new_node NULL) return head; /* 空链表特殊处理 */ if (head NULL) { return new_node; } /* 找到最后一个节点 */ Node *current head; while (current-next ! NULL) { current current-next; } current-next new_node; return head; }3.4 在指定位置插入c/* 在指定位置插入位置从0开始计数 */ Node* insert_at(Node *head, int pos, int value) { if (pos 0) return head; Node *new_node create_node(value); if (new_node NULL) return head; /* 插入头部 */ if (pos 0) { new_node-next head; return new_node; } /* 找到前一个节点 */ Node *prev head; for (int i 0; i pos - 1 prev ! NULL; i) { prev prev-next; } /* 位置超出链表长度 */ if (prev NULL) { free(new_node); printf(位置无效\n); return head; } new_node-next prev-next; prev-next new_node; return head; }4 链表的遍历4.1 遍历并打印c/* 遍历链表并打印所有元素 */ void print_list(Node *head) { Node *current head; printf(链表内容); while (current ! NULL) { printf(%d , current-data); current current-next; } printf(\n); }4.2 获取链表长度c/* 计算链表长度 */ int list_length(Node *head) { int count 0; Node *current head; while (current ! NULL) { count; current current-next; } return count; }4.3 查找元素c/* 查找值为value的节点返回位置从0开始找不到返回-1 */ int find_node(Node *head, int value) { Node *current head; int pos 0; while (current ! NULL) { if (current-data value) { return pos; } current current-next; pos; } return -1; } /* 获取指定位置的节点值 */ int get_at(Node *head, int pos, int *value) { Node *current head; int i 0; while (current ! NULL i pos) { current current-next; i; } if (current NULL) { return -1; /* 位置无效 */ } *value current-data; return 0; }5 链表的释放5.1 释放整个链表链表节点是动态分配的使用完后必须释放否则会造成内存泄漏。c/* 释放整个链表 */ void free_list(Node *head) { Node *current head; Node *next; while (current ! NULL) { next current-next; /* 先保存下一个节点地址 */ free(current); /* 释放当前节点 */ current next; /* 移动到下一个节点 */ } }为什么不能直接 free(current) 再 current current-next因为free(current)后current-next已经不能访问了。5.2 删除指定节点c/* 删除第一个值为value的节点 */ Node* delete_node(Node *head, int value) { if (head NULL) return NULL; /* 删除头节点 */ if (head-data value) { Node *temp head; head head-next; free(temp); return head; } /* 查找要删除的节点 */ Node *prev head; Node *current head-next; while (current ! NULL current-data ! value) { prev current; current current-next; } /* 找到则删除 */ if (current ! NULL) { prev-next current-next; free(current); } return head; }6 完整示例学生成绩链表c#include stdio.h #include stdlib.h #include string.h /* 学生节点结构 */ typedef struct StudentNode { char name[50]; int id; float score; struct StudentNode *next; } StudentNode; /* 创建学生节点 */ StudentNode* create_student(const char *name, int id, float score) { StudentNode *new_node (StudentNode*)malloc(sizeof(StudentNode)); if (new_node NULL) return NULL; strcpy(new_node-name, name); new_node-id id; new_node-score score; new_node-next NULL; return new_node; } /* 插入到头部 */ StudentNode* insert_head(StudentNode *head, const char *name, int id, float score) { StudentNode *new_node create_student(name, id, score); if (new_node NULL) return head; new_node-next head; return new_node; } /* 插入到尾部 */ StudentNode* insert_tail(StudentNode *head, const char *name, int id, float score) { StudentNode *new_node create_student(name, id, score); if (new_node NULL) return head; if (head NULL) { return new_node; } StudentNode *current head; while (current-next ! NULL) { current current-next; } current-next new_node; return head; } /* 打印所有学生 */ void print_students(StudentNode *head) { StudentNode *current head; printf(\n学生列表\n); printf(姓名\t\t学号\t成绩\n); printf(------------------------\n); while (current ! NULL) { printf(%-15s %d\t%.1f\n, current-name, current-id, current-score); current current-next; } printf(\n); } /* 计算平均分 */ float average_score(StudentNode *head) { if (head NULL) return 0; StudentNode *current head; float sum 0; int count 0; while (current ! NULL) { sum current-score; count; current current-next; } return sum / count; } /* 查找学生 */ StudentNode* find_student(StudentNode *head, int id) { StudentNode *current head; while (current ! NULL) { if (current-id id) { return current; } current current-next; } return NULL; } /* 删除学生 */ StudentNode* delete_student(StudentNode *head, int id) { if (head NULL) return NULL; if (head-id id) { StudentNode *temp head; head head-next; free(temp); return head; } StudentNode *prev head; StudentNode *current head-next; while (current ! NULL current-id ! id) { prev current; current current-next; } if (current ! NULL) { prev-next current-next; free(current); } return head; } /* 释放链表 */ void free_students(StudentNode *head) { StudentNode *current head; StudentNode *next; while (current ! NULL) { next current-next; free(current); current next; } } int main(void) { StudentNode *head NULL; /* 插入学生 */ head insert_tail(head, 张三, 1001, 88.5); head insert_tail(head, 李四, 1002, 92.0); head insert_tail(head, 王五, 1003, 78.5); head insert_head(head, 赵六, 1000, 95.0); /* 打印 */ print_students(head); /* 平均分 */ printf(平均分%.2f\n, average_score(head)); /* 查找 */ StudentNode *found find_student(head, 1002); if (found) { printf(找到学生%s 成绩%.1f\n, found-name, found-score); } /* 删除 */ head delete_student(head, 1002); printf(删除学号1002后\n); print_students(head); /* 释放 */ free_students(head); return 0; }7 常见错误与注意事项7.1 忘记检查 malloc 返回值cNode *new_node (Node*)malloc(sizeof(Node)); new_node-data value; /* 如果 malloc 失败new_node 为 NULL程序崩溃 */7.2 修改链表时丢失节点c/* 错误在删除节点时直接 current current-next 后释放 */ Node *temp current; current current-next; /* 先移动指针 */ free(temp); /* 正确但顺序要对 */7.3 对空链表解引用cNode *current head; while (current-next ! NULL) { /* 如果 head 为 NULL崩溃 */ /* ... */ }7.4 忘记释放链表cvoid func(void) { Node *head create_list(); /* 使用链表... */ /* 忘记 free_list(head) → 内存泄漏 */ }7.5 指针悬挂cNode *p head; free_list(head); p-data 10; /* 错误p 指向已释放的内存 */7.6 循环引用c/* 错误节点指向自己或形成环 */ last-next first; /* 形成循环链表遍历时死循环 */8 本章小结本章系统介绍了单向链表的实现1. 链表节点结构ctypedef struct Node { int data; struct Node *next; } Node;2. 创建节点使用malloc动态分配设置数据域和指针域next 置为 NULL3. 插入操作头插法新节点指向原头节点头指针指向新节点尾插法找到最后一个节点将其 next 指向新节点中间插入找到前一个节点修改指针4. 遍历操作从头指针开始依次访问每个节点用current current-next移动指针当current NULL时结束5. 释放操作遍历链表逐个free节点释放前先保存下一个节点地址6. 注意事项总是检查malloc返回值修改指针前先保存下一个节点空链表特殊处理使用完后必须释放