C语言单链表基本操作：头尾插法、增删查改与合并详解
本文深入讲解C语言中单链表的存储结构与基本操作方法。内容包括头插法与尾插法的实现原理、节点的增加删除与位置查询、链表合并及内存销毁。特别针对C语言指针操作的复杂性，提供了标准C与C++引用语法的对比方案，帮助开发者避免常见的指针传递错误，并附有完整可运行的示例代码。
存储结构定义
单链表由结点（Node）组成，每个结点包含数据域和指向下一个结点的指针域。在定义时，通常使用 typedef 简化类型名称，便于后续操作。
typedef int DataType;
typedef struct Node {
DataType data; // 结点数据域
struct Node *next; // 指向下一个结点的指针域
} Node, *LinkList;基本功能概览
一个完整的单链表实现通常包含以下核心功能模块：
- 创建链表：头插法
CreateListHead与尾插法CreateListTail。 - 检索操作：获取指定位置元素
GetElement、查找元素位置LocateElement、获取链表长度LengthLinkList。 - 修改操作：在指定位置插入元素
InsertList、删除指定位置元素DeleteList。 - 其他操作：合并两个非递减链表
MergeList、销毁链表Destroy、遍历打印PrintList。
创建单链表
第1步：头插法创建单链表
目的：将新结点插入到头结点之后，使得输入顺序与链表存储顺序相反（逆序）。
/**
* 头插法创建单链表，输入以-1结束
*/
void CreateListHead(LinkList &head) {
DataType x;
LinkList p;
head = (LinkList)malloc(LEN);
head->next = NULL;
scanf("%d", &x);
while (x != -1) {
p = (LinkList)malloc(LEN);
p->data = x;
p->next = head->next; // 新增结点指向原头结点后的第一个结点
head->next = p; // 头结点指向新增结点
scanf("%d", &x);
}
}第2步：尾插法创建单链表
目的：将新结点添加到链表末尾，保持输入顺序与链表存储顺序一致（正序）。
/**
* 尾插法创建单链表，输入以-1结束
*/
void CreateListTail(LinkList &head) {
LinkList p, q;
DataType x;
head = (LinkList)malloc(LEN);
q = head; // q始终指向尾部结点
scanf("%d", &x);
while (x != -1) {
p = (LinkList)malloc(LEN);
p->data = x;
q->next = p; // 尾部结点的next指向新结点
q = p; // 更新q为新结点
scanf("%d", &x);
}
q->next = NULL; // 最后结点的next置为空
}基本运算操作
第3步：获取指定位置的元素
入口：传入头指针、目标位置i。
动作：从头结点开始遍历，直到找到第i个结点。注意判断位置合法性。
int GetElement(LinkList head, int i, DataType &e) {
LinkList p = head->next;
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) return 0; // 位置无效或超出范围
e = p->data;
return 1;
}第4步：在指定位置插入元素
动作：先找到第i-1个结点，然后修改指针将其链接到新结点，新结点再链接到原第i个结点。
int InsertList(LinkList head, int i, DataType e) {
LinkList p = head;
int j = 1;
while (p && j < i) { // 寻找前驱结点
p = p->next;
j++;
}
if (!p || j > i) return 0;
LinkList q = (LinkList)malloc(LEN);
q->data = e;
q->next = p->next;
p->next = q;
return 1;
}第5步：删除指定位置的元素
动作：找到第i-1个结点，暂存第i个结点，修改前驱指向后继，释放第i个结点内存。
int DeleteList(LinkList head, int i, DataType &e) {
LinkList p = head;
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) return 0;
LinkList s = p->next;
e = s->data;
p->next = s->next;
free(s);
return 1;
}第6步：合并两个非递减单链表
结果：La 和 Lb 合并后存入 Lc，且 Lc 仍保持非递减有序。此过程原地调整指针，不产生额外空间开销（除了 Lc 的头结点）。
void MergeList(LinkList La, LinkList Lb, LinkList &Lc) {
LinkList pa, pb, pc;
pa = La->next;
pb = Lb->next;
pc = Lc = (LinkList)malloc(LEN); // Lc复用La的头结点空间更优，此处为独立申请
while (pa && pb) {
if (pa->data <= pb->data) {
pc->next = pa;
pc = pa;
pa = pa->next;
} else {
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb; // 连接剩余部分
free(Lb); // 释放Lb头结点，若需保留La/Lb则不应在此free
}第7步：销毁链表
风险提醒：执行此操作将释放所有动态分配内存，执行后链表不可用。
void Destroy(LinkList &L) {
LinkList p, q;
p = L;
while (p) {
q = p;
p = p->next;
free(q);
}
L = NULL;
}第8步：遍历打印
void PrintList(LinkList head) {
LinkList p = head->next;
if (p == NULL) {
cout << "List is NULL!" <<endl;
} else {
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
}C与C++语法差异注意事项
在上述许多函数签名中使用了 C++ 的引用参数写法（如 LinkList &head），以便直接修改实参指针。这在纯 C 语言环境中是编译错误的。若需在 .c 文件中实现相同效果，需使用“二级指针”或返回值方式。
方案一：使用二级指针（推荐用于修改头指针本身）
// 改变一个结构体指针，需要指针的指针
void CreatListTail(LinkList *head) {
int x;
LinkList *p, *q;
*head = (LinkList *) malloc(LEN);
q = *head;
scanf("%d", &x);
while (x != -1) {
p = (LinkList *) malloc(LEN);
p->data = x;
q->next = p;
q = p;
scanf("%d", &x);
}
q->next = NULL;
}方案二：通过返回值获取头指针
LinkList CreateListhead() {
int x;
LinkList head = (LinkList) malloc(LEN);
LinkList *p = &(head->next); // 或使用局部指针操作
// ... 省略具体循环逻辑 ...
return head;
}运行结果验证
通过测试代码调用上述函数，可以观察到头插法导致元素逆序，尾插法保持顺序，以及插入、删除、合并操作后的链表变化。以下是典型的运行输出截图：
提示：在实际调试中，建议结合 PrintList 观察每一步操作前后的链表状态，以确保指针断链或循环引用的情况未发生。
以上就是C语言实现单链表基本操作方法的详细内容，更多关于C语言单链表结构设计与应用技巧的资料请关注本站其它相关文章！
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
