大家好我是CSDN的一名技术博主。在C/C的学习和项目开发中指针、链表、栈和队列是绕不开的核心基础。很多初学者在理解指针与内存的关系时感到困惑更不用说用指针去构建链表、栈和队列这些动态数据结构了。本文将为你系统性地梳理这四大核心概念从指针的本质出发一步步手把手带你实现单链表、链式栈和链式队列并提供完整的、可直接运行的C语言代码。无论你是正在准备数据结构考试的学生还是希望夯实C语言功底的开发者这篇文章都能帮你建立起清晰的知识体系并具备实际动手实现的能力。1. 背景与核心概念从内存到数据结构在深入代码之前我们必须理解这些技术解决的根本问题以及它们之间的关系。1.1 指针内存的导航员指针是什么你可以将计算机的内存想象成一个巨大的、连续编号的酒店房间每个房间是一个字节编号就是地址。指针就是一个变量但这个变量里存放的不是普通的数据如整数、字符而是另一个变量的“房间号”即内存地址。它解决什么问题间接访问与修改通过地址直接操作内存中的数据效率高。动态内存管理程序运行时可以根据需要向系统申请malloc和释放free任意大小的内存这是实现链表等动态数据结构的基础。实现复杂数据结构如链表、树、图的节点连接。函数参数传递通过传递指针传址调用可以在函数内部修改实参的值。关键理解指针变量本身也占用内存存放地址对指针进行取地址操作得到的是指针变量自己的地址对指针进行*解引用操作得到的是该指针所指向地址里存储的值。1.2 链表动态的“火车”链表是什么链表是一种物理存储单元上非连续、非顺序的线性数据结构。它由一系列“节点”组成每个节点包含两部分数据域存储实际的数据元素。指针域存储指向下一个节点地址的指针。与数组的对比数组内存连续大小固定。插入/删除元素可能需要移动大量元素时间复杂度O(n)但随机访问快O(1)。链表内存不连续大小动态。插入/删除节点已知前驱节点时只需修改指针时间复杂度O(1)但随机访问慢需要从头遍历O(n)。为什么需要链表当数据量未知或频繁插入删除时数组的固定大小和元素移动会成为性能瓶颈。链表则提供了极大的灵活性。1.3 栈与队列受限的线性表栈和队列是两种操作受限的线性表它们可以用数组顺序存储或链表链式存储来实现。栈 (Stack)后进先出 (LIFO) 的线性表。只允许在表的一端栈顶进行插入入栈/Push和删除出栈/Pop操作。类比一摞盘子你只能拿走或放上最顶上的那个。应用场景函数调用栈、表达式求值、括号匹配、浏览器的前进后退。队列 (Queue)先进先出 (FIFO) 的线性表。只允许在表的一端队尾插入入队/Enqueue在另一端队头删除出队/Dequeue。类比排队买票先来的人先买到票离开。应用场景消息队列、CPU任务调度、广度优先搜索BFS。链式实现 vs 顺序实现顺序栈/队列用数组实现。需要预先分配固定大小可能造成空间浪费或溢出。链式栈/队列用链表实现。动态分配节点理论上只要内存足够就不会满更灵活。本文重点讲解链式实现。2. 环境准备与版本说明本文的所有代码示例均使用标准C语言编写不依赖任何特定平台或第三方库。操作系统Windows 10/11, Linux, macOS 均可。编译器GCC (MinGW-w64)、Clang 或 Visual Studio 的 MSVC 编译器。推荐使用gcc --version检查确保支持C11或以上标准。开发环境任何文本编辑器如VS Code, Sublime Text或IDE如CLion, Code::Blocks均可。编译命令gcc -o program main.c linkedlist.c stack.c queue.c假设文件已拆分运行./program(Linux/macOS) 或program.exe(Windows)项目文件结构建议pointer_data_structures/ ├── main.c # 主函数测试代码 ├── linkedlist.h # 链表相关函数声明和结构体定义 ├── linkedlist.c # 链表函数实现 ├── stack.h # 链式栈相关声明 ├── stack.c # 链式栈函数实现 ├── queue.h # 链式队列相关声明 └── queue.c # 链式队列函数实现为了讲解清晰下文代码可能会集中在一个文件中演示但会标明各部分所属。3. 核心原理与语法拆解3.1 指针的核心操作理解以下操作是读懂后续链表代码的关键。#include stdio.h int main() { int a 10; // 定义一个整型变量a假设其地址为0x1000 int *p a; // 定义指针变量p并将a的地址存入p。p的值是0x1000 printf(a的值: %d\n, a); // 输出: 10 printf(a的地址: %p\n, a); // 输出: 0x1000 (示例) printf(指针p的值(即a的地址): %p\n, p); // 输出: 0x1000 printf(通过p访问a的值(*p): %d\n, *p); // 输出: 10 (解引用) *p 20; // 通过指针修改a的值 printf(修改后a的值: %d\n, a); // 输出: 20 // 指针的指针 int **pp p; // pp是一个指向指针p的指针 printf(指针p的地址: %p\n, p); printf(二级指针pp的值(即p的地址): %p\n, pp); printf(通过pp访问a的值(**pp): %d\n, **pp); // 输出: 20 return 0; }关键点取地址运算符。*在声明时表示指针类型int *p在表达式中表示解引用运算符*p 20。指针必须初始化后才能使用野指针未初始化或指向已释放内存是程序崩溃的常见原因。3.2 动态内存管理malloc 和 free链表节点需要在程序运行时动态创建这离不开malloc和free。#include stdio.h #include stdlib.h // 包含 malloc 和 free 的原型 int main() { // 申请一块足以存放一个int类型的内存并返回其首地址 int *dynamic_int (int*)malloc(sizeof(int)); if (dynamic_int NULL) { printf(内存申请失败\n); exit(1); // 退出程序 } *dynamic_int 100; // 向这块内存写入数据 printf(动态分配的整数: %d\n, *dynamic_int); // 使用完毕后必须释放内存防止内存泄漏 free(dynamic_int); dynamic_int NULL; // 良好的习惯释放后置为NULL避免成为野指针 // 为结构体申请内存 struct Node { int data; struct Node* next; }; struct Node *node_ptr (struct Node*)malloc(sizeof(struct Node)); if (node_ptr) { // 等价于 if (node_ptr ! NULL) node_ptr-data 1; node_ptr-next NULL; // ... 使用节点 free(node_ptr); } return 0; }重要原则有malloc必有对应的free且free后最好将指针置为NULL。3.3 链表节点的结构定义这是所有链式结构的基石。// linkedlist.h #ifndef LINKEDLIST_H #define LINKEDLIST_H typedef int ElemType; // 将数据类型抽象为ElemType方便以后修改 // 定义单链表节点结构体 typedef struct ListNode { ElemType data; // 数据域 struct ListNode *next; // 指针域指向下一个节点 } ListNode, *LinkList; // ListNode是结构体类型LinkList是指向结构体的指针类型 // 函数声明 LinkList create_head_insert(); // 头插法创建链表 void traverse_list(LinkList L); // 遍历链表 // ... 其他函数声明 #endiftypedef简化了类型名LinkList等价于ListNode*通常用于表示整个链表的头指针。struct ListNode *next是一个指向自身结构体类型的指针这是实现链式结构的关键。4. 完整实战单链表的实现我们首先实现一个带头节点的单链表。头节点不存储实际数据其next指向第一个有效节点。这可以简化插入和删除操作因为空链表和非空链表的操作可以统一。4.1 创建链表头插法头插法每次将新节点插入到链表的头部头节点之后。// linkedlist.c #include stdio.h #include stdlib.h #include linkedlist.h // 头插法创建单链表带头节点 // 输入一系列整数以-1结束 LinkList create_head_insert() { LinkList L (LinkList)malloc(sizeof(ListNode)); // 创建头节点 if (!L) { printf(内存分配失败\n); exit(1); } L-next NULL; // 初始为空链表 ListNode *s NULL; ElemType x; printf(请输入链表元素整数以-1结束: ); scanf(%d, x); while (x ! -1) { s (ListNode*)malloc(sizeof(ListNode)); if (!s) exit(1); s-data x; // 关键头插步骤 s-next L-next; // 新节点指向原第一个节点 L-next s; // 头节点指向新节点 printf(请输入下一个元素-1结束: ); scanf(%d, x); } printf(链表创建完成头插法。\n); return L; // 返回头指针 }图解假设依次输入 1, 2, 3。创建头节点LL-next NULL。输入1创建节点s1s1-next L-next (NULL)L-next s1。链表头 - 1 - NULL。输入2创建节点s2s2-next L-next (s1)L-next s2。链表头 - 2 - 1 - NULL。输入3创建节点s3s3-next L-next (s2)L-next s3。链表头 - 3 - 2 - 1 - NULL。结果头插法生成的链表顺序与输入顺序相反。4.2 遍历链表void traverse_list(LinkList L) { if (L NULL) { printf(链表不存在\n); return; } ListNode *p L-next; // p指向第一个有效节点 printf(链表元素为: ); while (p ! NULL) { printf(%d - , p-data); p p-next; // p移动到下一个节点 } printf(NULL\n); }4.3 按值查找节点ListNode* locate_elem(LinkList L, ElemType e) { ListNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; // 找到返回节点指针未找到返回NULL }4.4 在指定位置插入节点假设在第i个位置从1开始计数头节点不算插入新节点e。// 在第i个位置插入元素e int list_insert(LinkList L, int i, ElemType e) { if (i 1) return 0; // 位置非法 ListNode *p L; // p指向头节点 int j 0; // 当前p指向的是第几个节点头节点是第0个 // 寻找第i-1个节点 while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) { // i值超过链表长度1 return 0; } ListNode *s (ListNode*)malloc(sizeof(ListNode)); if (!s) exit(1); s-data e; s-next p-next; p-next s; return 1; // 插入成功 }4.5 删除指定位置节点// 删除第i个位置的节点并通过e返回其值 int list_delete(LinkList L, int i, ElemType *e) { if (i 1) return 0; ListNode *p L; int j 0; // 寻找第i-1个节点 while (p-next ! NULL j i - 1) { p p-next; j; } if (p-next NULL) { // 第i个节点不存在 return 0; } ListNode *q p-next; // q指向待删除节点 *e q-data; // 保存被删除节点的值 p-next q-next; // 将第i-1个节点的next指向第i1个节点 free(q); // 释放被删除节点的内存 return 1; }4.6 主函数测试// main.c (链表测试部分) #include stdio.h #include linkedlist.h void test_linkedlist() { printf( 单链表测试 \n); LinkList myList create_head_insert(); traverse_list(myList); printf(\n在位置2插入元素99:\n); if (list_insert(myList, 2, 99)) { traverse_list(myList); } else { printf(插入失败\n); } ElemType deleted_val; printf(\n删除位置3的元素:\n); if (list_delete(myList, 3, deleted_val)) { printf(删除的值为: %d\n, deleted_val); traverse_list(myList); } else { printf(删除失败\n); } printf(\n查找元素99:\n); ListNode *found locate_elem(myList, 99); if (found) { printf(找到元素99其地址为: %p\n, (void*)found); } else { printf(未找到元素99。\n); } // 注意实际项目中需要编写销毁链表的函数来释放所有节点内存 // destroy_list(myList); } int main() { test_linkedlist(); // 后续可以调用栈和队列的测试函数 return 0; }5. 完整实战链式栈的实现链式栈的本质就是一个受限的单链表我们规定所有的插入入栈和删除出栈操作只能在链表的头部进行。这样单链表的头节点就扮演了“栈顶”的角色。5.1 结构定义与初始化// stack.h #ifndef STACK_H #define STACK_H #include linkedlist.h // 复用ListNode typedef struct { ListNode *top; // 栈顶指针指向栈顶元素即链表的第一个有效节点 int size; // 栈中元素个数可选方便判断 } LinkStack; // 函数声明 void init_stack(LinkStack *S); int is_stack_empty(LinkStack *S); int push(LinkStack *S, ElemType e); int pop(LinkStack *S, ElemType *e); int get_top(LinkStack *S, ElemType *e); void traverse_stack(LinkStack *S); #endif// stack.c #include stdio.h #include stdlib.h #include stack.h // 初始化栈 void init_stack(LinkStack *S) { S-top NULL; S-size 0; } // 判断栈是否为空 int is_stack_empty(LinkStack *S) { return S-top NULL; // 或者 return S-size 0; }5.2 入栈操作 (Push)int push(LinkStack *S, ElemType e) { ListNode *s (ListNode*)malloc(sizeof(ListNode)); if (!s) { printf(内存分配失败入栈失败\n); return 0; } s-data e; s-next S-top; // 新节点指向原栈顶 S-top s; // 栈顶指针指向新节点 S-size; return 1; }图解栈初始为空S-top NULL。入栈元素10创建节点s1s1-next NULLS-top s1。入栈元素20创建节点s2s2-next s1S-top s2。 栈顶始终是S-top指向的节点。5.3 出栈操作 (Pop) 与获取栈顶 (GetTop)int pop(LinkStack *S, ElemType *e) { if (is_stack_empty(S)) { printf(栈为空无法出栈\n); return 0; } ListNode *p S-top; // p指向待出栈的栈顶节点 *e p-data; // 保存栈顶元素值 S-top p-next; // 栈顶指针下移 free(p); // 释放原栈顶节点内存 S-size--; return 1; } int get_top(LinkStack *S, ElemType *e) { if (is_stack_empty(S)) { printf(栈为空无栈顶元素\n); return 0; } *e S-top-data; // 仅读取不修改栈结构 return 1; }5.4 遍历栈从栈顶到栈底void traverse_stack(LinkStack *S) { if (is_stack_empty(S)) { printf(栈为空。\n); return; } printf(栈内元素(栈顶-栈底): ); ListNode *p S-top; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); }6. 完整实战链式队列的实现链式队列需要两个指针一个指向队头front用于出队一个指向队尾rear用于入队。我们通常也采用带头节点的设计来简化边界条件。6.1 结构定义与初始化// queue.h #ifndef QUEUE_H #define QUEUE_H #include linkedlist.h typedef struct { ListNode *front; // 队头指针指向头节点 ListNode *rear; // 队尾指针指向最后一个节点 } LinkQueue; // 函数声明 void init_queue(LinkQueue *Q); int is_queue_empty(LinkQueue *Q); int enqueue(LinkQueue *Q, ElemType e); int dequeue(LinkQueue *Q, ElemType *e); int get_front(LinkQueue *Q, ElemType *e); void traverse_queue(LinkQueue *Q); #endif// queue.c #include stdio.h #include stdlib.h #include queue.h // 初始化队列创建头节点front和rear都指向它 void init_queue(LinkQueue *Q) { Q-front Q-rear (ListNode*)malloc(sizeof(ListNode)); if (!Q-front) exit(1); Q-front-next NULL; // 头节点next域为空 } int is_queue_empty(LinkQueue *Q) { return Q-front Q-rear; // 队空条件头尾指针指向同一个节点头节点 }6.2 入队操作 (Enqueue)int enqueue(LinkQueue *Q, ElemType e) { ListNode *s (ListNode*)malloc(sizeof(ListNode)); if (!s) return 0; s-data e; s-next NULL; Q-rear-next s; // 将新节点链接到队尾 Q-rear s; // 队尾指针后移指向新的队尾 return 1; }图解初始化后front和rear都指向头节点H。入队元素10创建节点s1H-next s1rear s1。队列H - 10。入队元素20创建节点s2s1-next s2rear s2。队列H - 10 - 20。6.3 出队操作 (Dequeue) 与获取队头int dequeue(LinkQueue *Q, ElemType *e) { if (is_queue_empty(Q)) { printf(队列为空无法出队\n); return 0; } ListNode *p Q-front-next; // p指向待出队的节点第一个有效节点 *e p-data; Q-front-next p-next; // 头节点的next指向下一个节点 // 特殊情况如果出队的是最后一个节点出队后队列为空需要将rear指回头节点 if (Q-rear p) { Q-rear Q-front; } free(p); return 1; } int get_front(LinkQueue *Q, ElemType *e) { if (is_queue_empty(Q)) { printf(队列为空无队头元素\n); return 0; } *e Q-front-next-data; return 1; }6.4 遍历队列void traverse_queue(LinkQueue *Q) { if (is_queue_empty(Q)) { printf(队列为空。\n); return; } printf(队列元素(队头-队尾): ); ListNode *p Q-front-next; // 跳过头节点 while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); }7. 综合测试与运行结果将链表、栈、队列的测试整合到一个主程序中。// main.c (完整测试) #include stdio.h #include linkedlist.h #include stack.h #include queue.h void test_linkedlist() { // ... 前面链表测试代码此处省略以节省篇幅 printf(链表测试结束。\n\n); } void test_stack() { printf( 链式栈测试 \n); LinkStack S; init_stack(S); printf(依次入栈: 10, 20, 30\n); push(S, 10); push(S, 20); push(S, 30); traverse_stack(S); ElemType top_val; get_top(S, top_val); printf(当前栈顶元素: %d\n, top_val); ElemType pop_val; pop(S, pop_val); printf(出栈元素: %d\n, pop_val); traverse_stack(S); printf(栈测试结束。\n\n); } void test_queue() { printf( 链式队列测试 \n); LinkQueue Q; init_queue(Q); printf(依次入队: 100, 200, 300\n); enqueue(Q, 100); enqueue(Q, 200); enqueue(Q, 300); traverse_queue(Q); ElemType front_val; get_front(Q, front_val); printf(当前队头元素: %d\n, front_val); ElemType deq_val; dequeue(Q, deq_val); printf(出队元素: %d\n, deq_val); traverse_queue(Q); printf(队列测试结束。\n\n); } int main() { test_linkedlist(); test_stack(); test_queue(); return 0; }编译与运行gcc -o demo main.c linkedlist.c stack.c queue.c ./demo预期输出片段 单链表测试 请输入链表元素整数以-1结束: 1 2 3 -1 链表创建完成头插法。 链表元素为: 3 - 2 - 1 - NULL ... 链式栈测试 依次入栈: 10, 20, 30 栈内元素(栈顶-栈底): 30 - 20 - 10 - NULL 当前栈顶元素: 30 出栈元素: 30 栈内元素(栈顶-栈底): 20 - 10 - NULL ... 链式队列测试 依次入队: 100, 200, 300 队列元素(队头-队尾): 100 - 200 - 300 - NULL 当前队头元素: 100 出队元素: 100 队列元素(队头-队尾): 200 - 300 - NULL8. 常见问题与排查思路问题现象可能原因排查与解决思路程序编译通过但运行时崩溃Segmentation Fault1. 访问了未初始化的野指针。2. 访问了已通过free()释放的内存。3. 指针越界访问如链表遍历时p-next但p为NULL。1. 检查所有指针变量是否在解引用*p或p-前已被正确赋值指向有效内存或NULL。2. 确保free()后不再使用该指针并养成置NULL的习惯。3. 在循环条件while(p)或while(p-next)中仔细检查p是否为NULL。使用调试器如gdb定位崩溃行。内存泄漏申请的内存malloc没有对应的free。1. 为每个数据结构如链表、栈、队列编写销毁函数在程序结束前或不再需要时调用遍历所有节点并free。2. 使用 Valgrind 等工具检测内存泄漏。链表/栈/队列操作结果不符合预期1. 指针修改逻辑错误如头插法、入栈、入队时指针指向顺序错误。2. 边界条件处理不当如空表插入、删除唯一节点。1.画图在纸上画出操作前后节点的连接关系一步步跟踪指针变化。2. 重点测试边界空结构插入第一个元素、删除最后一个元素、在只有一个元素的结构上操作等。3. 使用printf打印关键指针的值和节点的数据辅助调试。头节点使用混乱混淆了带头节点和不带头节点的链表操作。明确设计本文的链表、队列都使用了头节点。头节点的next指向第一个有效数据节点。空链表时head-next NULL。操作时通常从head-next开始遍历。函数参数传递错误试图在函数内修改指针本身如改变链表头但使用了值传递。如果需要修改指针本身如初始化LinkStack S后在函数内为S.top赋值必须传递指针的地址即使用二级指针LinkStack *S或直接传递结构体指针。本文栈和队列的参数都是结构体指针LinkStack *S和LinkQueue *Q。9. 最佳实践与工程建议防御性编程所有使用指针前判断是否为NULL。malloc后立即检查返回值。函数入口检查参数有效性。int my_function(LinkList L, int position) { if (L NULL || position 1) { return ERROR_CODE; // 定义错误码 } // ... 正常逻辑 }模块化与封装将数据结构的声明.h与实现.c分离。提供清晰的接口函数隐藏内部实现细节如节点结构体可以放在.c文件中.h中只提供不透明指针。为每个数据结构编写完整的创建、销毁、增删改查接口。资源管理谁申请谁释放在同一个逻辑层次管理内存。例如create_list对应一个destroy_list函数。在复杂项目中考虑使用智能指针C或引用计数来管理生命周期避免内存泄漏和悬空指针。错误处理不要仅仅printf错误信息函数应该通过返回值如0/1NULL或特定的错误码告知调用者操作成功与否。调用者需要检查这些返回值并做出相应处理。性能考量链式结构插入删除快但访问慢。如果业务场景需要频繁随机访问应考虑数组或平衡树等结构。频繁的malloc和free会产生内存碎片。对于小块内存的频繁分配/释放可以考虑使用内存池。扩展思考双向链表每个节点增加一个prev指针指向前驱支持双向遍历但增删操作稍复杂。循环链表尾节点的next指向头节点适合环形缓冲等场景。链式栈/队列的变种如共享栈、双端队列Deque都可以在链表基础上实现。掌握指针和这些基础数据结构是理解更复杂数据结构树、图和算法排序、搜索的基石。建议读者不要只停留在阅读代码一定要亲手在IDE中敲一遍并尝试进行修改和扩展例如实现一个不带头节点的链表或者用链表实现一个简单的LRU缓存这样才能真正内化知识。 C语言指针与链表实战：从内存管理到链式栈、队列的完整实现
大家好我是CSDN的一名技术博主。在C/C的学习和项目开发中指针、链表、栈和队列是绕不开的核心基础。很多初学者在理解指针与内存的关系时感到困惑更不用说用指针去构建链表、栈和队列这些动态数据结构了。本文将为你系统性地梳理这四大核心概念从指针的本质出发一步步手把手带你实现单链表、链式栈和链式队列并提供完整的、可直接运行的C语言代码。无论你是正在准备数据结构考试的学生还是希望夯实C语言功底的开发者这篇文章都能帮你建立起清晰的知识体系并具备实际动手实现的能力。1. 背景与核心概念从内存到数据结构在深入代码之前我们必须理解这些技术解决的根本问题以及它们之间的关系。1.1 指针内存的导航员指针是什么你可以将计算机的内存想象成一个巨大的、连续编号的酒店房间每个房间是一个字节编号就是地址。指针就是一个变量但这个变量里存放的不是普通的数据如整数、字符而是另一个变量的“房间号”即内存地址。它解决什么问题间接访问与修改通过地址直接操作内存中的数据效率高。动态内存管理程序运行时可以根据需要向系统申请malloc和释放free任意大小的内存这是实现链表等动态数据结构的基础。实现复杂数据结构如链表、树、图的节点连接。函数参数传递通过传递指针传址调用可以在函数内部修改实参的值。关键理解指针变量本身也占用内存存放地址对指针进行取地址操作得到的是指针变量自己的地址对指针进行*解引用操作得到的是该指针所指向地址里存储的值。1.2 链表动态的“火车”链表是什么链表是一种物理存储单元上非连续、非顺序的线性数据结构。它由一系列“节点”组成每个节点包含两部分数据域存储实际的数据元素。指针域存储指向下一个节点地址的指针。与数组的对比数组内存连续大小固定。插入/删除元素可能需要移动大量元素时间复杂度O(n)但随机访问快O(1)。链表内存不连续大小动态。插入/删除节点已知前驱节点时只需修改指针时间复杂度O(1)但随机访问慢需要从头遍历O(n)。为什么需要链表当数据量未知或频繁插入删除时数组的固定大小和元素移动会成为性能瓶颈。链表则提供了极大的灵活性。1.3 栈与队列受限的线性表栈和队列是两种操作受限的线性表它们可以用数组顺序存储或链表链式存储来实现。栈 (Stack)后进先出 (LIFO) 的线性表。只允许在表的一端栈顶进行插入入栈/Push和删除出栈/Pop操作。类比一摞盘子你只能拿走或放上最顶上的那个。应用场景函数调用栈、表达式求值、括号匹配、浏览器的前进后退。队列 (Queue)先进先出 (FIFO) 的线性表。只允许在表的一端队尾插入入队/Enqueue在另一端队头删除出队/Dequeue。类比排队买票先来的人先买到票离开。应用场景消息队列、CPU任务调度、广度优先搜索BFS。链式实现 vs 顺序实现顺序栈/队列用数组实现。需要预先分配固定大小可能造成空间浪费或溢出。链式栈/队列用链表实现。动态分配节点理论上只要内存足够就不会满更灵活。本文重点讲解链式实现。2. 环境准备与版本说明本文的所有代码示例均使用标准C语言编写不依赖任何特定平台或第三方库。操作系统Windows 10/11, Linux, macOS 均可。编译器GCC (MinGW-w64)、Clang 或 Visual Studio 的 MSVC 编译器。推荐使用gcc --version检查确保支持C11或以上标准。开发环境任何文本编辑器如VS Code, Sublime Text或IDE如CLion, Code::Blocks均可。编译命令gcc -o program main.c linkedlist.c stack.c queue.c假设文件已拆分运行./program(Linux/macOS) 或program.exe(Windows)项目文件结构建议pointer_data_structures/ ├── main.c # 主函数测试代码 ├── linkedlist.h # 链表相关函数声明和结构体定义 ├── linkedlist.c # 链表函数实现 ├── stack.h # 链式栈相关声明 ├── stack.c # 链式栈函数实现 ├── queue.h # 链式队列相关声明 └── queue.c # 链式队列函数实现为了讲解清晰下文代码可能会集中在一个文件中演示但会标明各部分所属。3. 核心原理与语法拆解3.1 指针的核心操作理解以下操作是读懂后续链表代码的关键。#include stdio.h int main() { int a 10; // 定义一个整型变量a假设其地址为0x1000 int *p a; // 定义指针变量p并将a的地址存入p。p的值是0x1000 printf(a的值: %d\n, a); // 输出: 10 printf(a的地址: %p\n, a); // 输出: 0x1000 (示例) printf(指针p的值(即a的地址): %p\n, p); // 输出: 0x1000 printf(通过p访问a的值(*p): %d\n, *p); // 输出: 10 (解引用) *p 20; // 通过指针修改a的值 printf(修改后a的值: %d\n, a); // 输出: 20 // 指针的指针 int **pp p; // pp是一个指向指针p的指针 printf(指针p的地址: %p\n, p); printf(二级指针pp的值(即p的地址): %p\n, pp); printf(通过pp访问a的值(**pp): %d\n, **pp); // 输出: 20 return 0; }关键点取地址运算符。*在声明时表示指针类型int *p在表达式中表示解引用运算符*p 20。指针必须初始化后才能使用野指针未初始化或指向已释放内存是程序崩溃的常见原因。3.2 动态内存管理malloc 和 free链表节点需要在程序运行时动态创建这离不开malloc和free。#include stdio.h #include stdlib.h // 包含 malloc 和 free 的原型 int main() { // 申请一块足以存放一个int类型的内存并返回其首地址 int *dynamic_int (int*)malloc(sizeof(int)); if (dynamic_int NULL) { printf(内存申请失败\n); exit(1); // 退出程序 } *dynamic_int 100; // 向这块内存写入数据 printf(动态分配的整数: %d\n, *dynamic_int); // 使用完毕后必须释放内存防止内存泄漏 free(dynamic_int); dynamic_int NULL; // 良好的习惯释放后置为NULL避免成为野指针 // 为结构体申请内存 struct Node { int data; struct Node* next; }; struct Node *node_ptr (struct Node*)malloc(sizeof(struct Node)); if (node_ptr) { // 等价于 if (node_ptr ! NULL) node_ptr-data 1; node_ptr-next NULL; // ... 使用节点 free(node_ptr); } return 0; }重要原则有malloc必有对应的free且free后最好将指针置为NULL。3.3 链表节点的结构定义这是所有链式结构的基石。// linkedlist.h #ifndef LINKEDLIST_H #define LINKEDLIST_H typedef int ElemType; // 将数据类型抽象为ElemType方便以后修改 // 定义单链表节点结构体 typedef struct ListNode { ElemType data; // 数据域 struct ListNode *next; // 指针域指向下一个节点 } ListNode, *LinkList; // ListNode是结构体类型LinkList是指向结构体的指针类型 // 函数声明 LinkList create_head_insert(); // 头插法创建链表 void traverse_list(LinkList L); // 遍历链表 // ... 其他函数声明 #endiftypedef简化了类型名LinkList等价于ListNode*通常用于表示整个链表的头指针。struct ListNode *next是一个指向自身结构体类型的指针这是实现链式结构的关键。4. 完整实战单链表的实现我们首先实现一个带头节点的单链表。头节点不存储实际数据其next指向第一个有效节点。这可以简化插入和删除操作因为空链表和非空链表的操作可以统一。4.1 创建链表头插法头插法每次将新节点插入到链表的头部头节点之后。// linkedlist.c #include stdio.h #include stdlib.h #include linkedlist.h // 头插法创建单链表带头节点 // 输入一系列整数以-1结束 LinkList create_head_insert() { LinkList L (LinkList)malloc(sizeof(ListNode)); // 创建头节点 if (!L) { printf(内存分配失败\n); exit(1); } L-next NULL; // 初始为空链表 ListNode *s NULL; ElemType x; printf(请输入链表元素整数以-1结束: ); scanf(%d, x); while (x ! -1) { s (ListNode*)malloc(sizeof(ListNode)); if (!s) exit(1); s-data x; // 关键头插步骤 s-next L-next; // 新节点指向原第一个节点 L-next s; // 头节点指向新节点 printf(请输入下一个元素-1结束: ); scanf(%d, x); } printf(链表创建完成头插法。\n); return L; // 返回头指针 }图解假设依次输入 1, 2, 3。创建头节点LL-next NULL。输入1创建节点s1s1-next L-next (NULL)L-next s1。链表头 - 1 - NULL。输入2创建节点s2s2-next L-next (s1)L-next s2。链表头 - 2 - 1 - NULL。输入3创建节点s3s3-next L-next (s2)L-next s3。链表头 - 3 - 2 - 1 - NULL。结果头插法生成的链表顺序与输入顺序相反。4.2 遍历链表void traverse_list(LinkList L) { if (L NULL) { printf(链表不存在\n); return; } ListNode *p L-next; // p指向第一个有效节点 printf(链表元素为: ); while (p ! NULL) { printf(%d - , p-data); p p-next; // p移动到下一个节点 } printf(NULL\n); }4.3 按值查找节点ListNode* locate_elem(LinkList L, ElemType e) { ListNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; // 找到返回节点指针未找到返回NULL }4.4 在指定位置插入节点假设在第i个位置从1开始计数头节点不算插入新节点e。// 在第i个位置插入元素e int list_insert(LinkList L, int i, ElemType e) { if (i 1) return 0; // 位置非法 ListNode *p L; // p指向头节点 int j 0; // 当前p指向的是第几个节点头节点是第0个 // 寻找第i-1个节点 while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) { // i值超过链表长度1 return 0; } ListNode *s (ListNode*)malloc(sizeof(ListNode)); if (!s) exit(1); s-data e; s-next p-next; p-next s; return 1; // 插入成功 }4.5 删除指定位置节点// 删除第i个位置的节点并通过e返回其值 int list_delete(LinkList L, int i, ElemType *e) { if (i 1) return 0; ListNode *p L; int j 0; // 寻找第i-1个节点 while (p-next ! NULL j i - 1) { p p-next; j; } if (p-next NULL) { // 第i个节点不存在 return 0; } ListNode *q p-next; // q指向待删除节点 *e q-data; // 保存被删除节点的值 p-next q-next; // 将第i-1个节点的next指向第i1个节点 free(q); // 释放被删除节点的内存 return 1; }4.6 主函数测试// main.c (链表测试部分) #include stdio.h #include linkedlist.h void test_linkedlist() { printf( 单链表测试 \n); LinkList myList create_head_insert(); traverse_list(myList); printf(\n在位置2插入元素99:\n); if (list_insert(myList, 2, 99)) { traverse_list(myList); } else { printf(插入失败\n); } ElemType deleted_val; printf(\n删除位置3的元素:\n); if (list_delete(myList, 3, deleted_val)) { printf(删除的值为: %d\n, deleted_val); traverse_list(myList); } else { printf(删除失败\n); } printf(\n查找元素99:\n); ListNode *found locate_elem(myList, 99); if (found) { printf(找到元素99其地址为: %p\n, (void*)found); } else { printf(未找到元素99。\n); } // 注意实际项目中需要编写销毁链表的函数来释放所有节点内存 // destroy_list(myList); } int main() { test_linkedlist(); // 后续可以调用栈和队列的测试函数 return 0; }5. 完整实战链式栈的实现链式栈的本质就是一个受限的单链表我们规定所有的插入入栈和删除出栈操作只能在链表的头部进行。这样单链表的头节点就扮演了“栈顶”的角色。5.1 结构定义与初始化// stack.h #ifndef STACK_H #define STACK_H #include linkedlist.h // 复用ListNode typedef struct { ListNode *top; // 栈顶指针指向栈顶元素即链表的第一个有效节点 int size; // 栈中元素个数可选方便判断 } LinkStack; // 函数声明 void init_stack(LinkStack *S); int is_stack_empty(LinkStack *S); int push(LinkStack *S, ElemType e); int pop(LinkStack *S, ElemType *e); int get_top(LinkStack *S, ElemType *e); void traverse_stack(LinkStack *S); #endif// stack.c #include stdio.h #include stdlib.h #include stack.h // 初始化栈 void init_stack(LinkStack *S) { S-top NULL; S-size 0; } // 判断栈是否为空 int is_stack_empty(LinkStack *S) { return S-top NULL; // 或者 return S-size 0; }5.2 入栈操作 (Push)int push(LinkStack *S, ElemType e) { ListNode *s (ListNode*)malloc(sizeof(ListNode)); if (!s) { printf(内存分配失败入栈失败\n); return 0; } s-data e; s-next S-top; // 新节点指向原栈顶 S-top s; // 栈顶指针指向新节点 S-size; return 1; }图解栈初始为空S-top NULL。入栈元素10创建节点s1s1-next NULLS-top s1。入栈元素20创建节点s2s2-next s1S-top s2。 栈顶始终是S-top指向的节点。5.3 出栈操作 (Pop) 与获取栈顶 (GetTop)int pop(LinkStack *S, ElemType *e) { if (is_stack_empty(S)) { printf(栈为空无法出栈\n); return 0; } ListNode *p S-top; // p指向待出栈的栈顶节点 *e p-data; // 保存栈顶元素值 S-top p-next; // 栈顶指针下移 free(p); // 释放原栈顶节点内存 S-size--; return 1; } int get_top(LinkStack *S, ElemType *e) { if (is_stack_empty(S)) { printf(栈为空无栈顶元素\n); return 0; } *e S-top-data; // 仅读取不修改栈结构 return 1; }5.4 遍历栈从栈顶到栈底void traverse_stack(LinkStack *S) { if (is_stack_empty(S)) { printf(栈为空。\n); return; } printf(栈内元素(栈顶-栈底): ); ListNode *p S-top; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); }6. 完整实战链式队列的实现链式队列需要两个指针一个指向队头front用于出队一个指向队尾rear用于入队。我们通常也采用带头节点的设计来简化边界条件。6.1 结构定义与初始化// queue.h #ifndef QUEUE_H #define QUEUE_H #include linkedlist.h typedef struct { ListNode *front; // 队头指针指向头节点 ListNode *rear; // 队尾指针指向最后一个节点 } LinkQueue; // 函数声明 void init_queue(LinkQueue *Q); int is_queue_empty(LinkQueue *Q); int enqueue(LinkQueue *Q, ElemType e); int dequeue(LinkQueue *Q, ElemType *e); int get_front(LinkQueue *Q, ElemType *e); void traverse_queue(LinkQueue *Q); #endif// queue.c #include stdio.h #include stdlib.h #include queue.h // 初始化队列创建头节点front和rear都指向它 void init_queue(LinkQueue *Q) { Q-front Q-rear (ListNode*)malloc(sizeof(ListNode)); if (!Q-front) exit(1); Q-front-next NULL; // 头节点next域为空 } int is_queue_empty(LinkQueue *Q) { return Q-front Q-rear; // 队空条件头尾指针指向同一个节点头节点 }6.2 入队操作 (Enqueue)int enqueue(LinkQueue *Q, ElemType e) { ListNode *s (ListNode*)malloc(sizeof(ListNode)); if (!s) return 0; s-data e; s-next NULL; Q-rear-next s; // 将新节点链接到队尾 Q-rear s; // 队尾指针后移指向新的队尾 return 1; }图解初始化后front和rear都指向头节点H。入队元素10创建节点s1H-next s1rear s1。队列H - 10。入队元素20创建节点s2s1-next s2rear s2。队列H - 10 - 20。6.3 出队操作 (Dequeue) 与获取队头int dequeue(LinkQueue *Q, ElemType *e) { if (is_queue_empty(Q)) { printf(队列为空无法出队\n); return 0; } ListNode *p Q-front-next; // p指向待出队的节点第一个有效节点 *e p-data; Q-front-next p-next; // 头节点的next指向下一个节点 // 特殊情况如果出队的是最后一个节点出队后队列为空需要将rear指回头节点 if (Q-rear p) { Q-rear Q-front; } free(p); return 1; } int get_front(LinkQueue *Q, ElemType *e) { if (is_queue_empty(Q)) { printf(队列为空无队头元素\n); return 0; } *e Q-front-next-data; return 1; }6.4 遍历队列void traverse_queue(LinkQueue *Q) { if (is_queue_empty(Q)) { printf(队列为空。\n); return; } printf(队列元素(队头-队尾): ); ListNode *p Q-front-next; // 跳过头节点 while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); }7. 综合测试与运行结果将链表、栈、队列的测试整合到一个主程序中。// main.c (完整测试) #include stdio.h #include linkedlist.h #include stack.h #include queue.h void test_linkedlist() { // ... 前面链表测试代码此处省略以节省篇幅 printf(链表测试结束。\n\n); } void test_stack() { printf( 链式栈测试 \n); LinkStack S; init_stack(S); printf(依次入栈: 10, 20, 30\n); push(S, 10); push(S, 20); push(S, 30); traverse_stack(S); ElemType top_val; get_top(S, top_val); printf(当前栈顶元素: %d\n, top_val); ElemType pop_val; pop(S, pop_val); printf(出栈元素: %d\n, pop_val); traverse_stack(S); printf(栈测试结束。\n\n); } void test_queue() { printf( 链式队列测试 \n); LinkQueue Q; init_queue(Q); printf(依次入队: 100, 200, 300\n); enqueue(Q, 100); enqueue(Q, 200); enqueue(Q, 300); traverse_queue(Q); ElemType front_val; get_front(Q, front_val); printf(当前队头元素: %d\n, front_val); ElemType deq_val; dequeue(Q, deq_val); printf(出队元素: %d\n, deq_val); traverse_queue(Q); printf(队列测试结束。\n\n); } int main() { test_linkedlist(); test_stack(); test_queue(); return 0; }编译与运行gcc -o demo main.c linkedlist.c stack.c queue.c ./demo预期输出片段 单链表测试 请输入链表元素整数以-1结束: 1 2 3 -1 链表创建完成头插法。 链表元素为: 3 - 2 - 1 - NULL ... 链式栈测试 依次入栈: 10, 20, 30 栈内元素(栈顶-栈底): 30 - 20 - 10 - NULL 当前栈顶元素: 30 出栈元素: 30 栈内元素(栈顶-栈底): 20 - 10 - NULL ... 链式队列测试 依次入队: 100, 200, 300 队列元素(队头-队尾): 100 - 200 - 300 - NULL 当前队头元素: 100 出队元素: 100 队列元素(队头-队尾): 200 - 300 - NULL8. 常见问题与排查思路问题现象可能原因排查与解决思路程序编译通过但运行时崩溃Segmentation Fault1. 访问了未初始化的野指针。2. 访问了已通过free()释放的内存。3. 指针越界访问如链表遍历时p-next但p为NULL。1. 检查所有指针变量是否在解引用*p或p-前已被正确赋值指向有效内存或NULL。2. 确保free()后不再使用该指针并养成置NULL的习惯。3. 在循环条件while(p)或while(p-next)中仔细检查p是否为NULL。使用调试器如gdb定位崩溃行。内存泄漏申请的内存malloc没有对应的free。1. 为每个数据结构如链表、栈、队列编写销毁函数在程序结束前或不再需要时调用遍历所有节点并free。2. 使用 Valgrind 等工具检测内存泄漏。链表/栈/队列操作结果不符合预期1. 指针修改逻辑错误如头插法、入栈、入队时指针指向顺序错误。2. 边界条件处理不当如空表插入、删除唯一节点。1.画图在纸上画出操作前后节点的连接关系一步步跟踪指针变化。2. 重点测试边界空结构插入第一个元素、删除最后一个元素、在只有一个元素的结构上操作等。3. 使用printf打印关键指针的值和节点的数据辅助调试。头节点使用混乱混淆了带头节点和不带头节点的链表操作。明确设计本文的链表、队列都使用了头节点。头节点的next指向第一个有效数据节点。空链表时head-next NULL。操作时通常从head-next开始遍历。函数参数传递错误试图在函数内修改指针本身如改变链表头但使用了值传递。如果需要修改指针本身如初始化LinkStack S后在函数内为S.top赋值必须传递指针的地址即使用二级指针LinkStack *S或直接传递结构体指针。本文栈和队列的参数都是结构体指针LinkStack *S和LinkQueue *Q。9. 最佳实践与工程建议防御性编程所有使用指针前判断是否为NULL。malloc后立即检查返回值。函数入口检查参数有效性。int my_function(LinkList L, int position) { if (L NULL || position 1) { return ERROR_CODE; // 定义错误码 } // ... 正常逻辑 }模块化与封装将数据结构的声明.h与实现.c分离。提供清晰的接口函数隐藏内部实现细节如节点结构体可以放在.c文件中.h中只提供不透明指针。为每个数据结构编写完整的创建、销毁、增删改查接口。资源管理谁申请谁释放在同一个逻辑层次管理内存。例如create_list对应一个destroy_list函数。在复杂项目中考虑使用智能指针C或引用计数来管理生命周期避免内存泄漏和悬空指针。错误处理不要仅仅printf错误信息函数应该通过返回值如0/1NULL或特定的错误码告知调用者操作成功与否。调用者需要检查这些返回值并做出相应处理。性能考量链式结构插入删除快但访问慢。如果业务场景需要频繁随机访问应考虑数组或平衡树等结构。频繁的malloc和free会产生内存碎片。对于小块内存的频繁分配/释放可以考虑使用内存池。扩展思考双向链表每个节点增加一个prev指针指向前驱支持双向遍历但增删操作稍复杂。循环链表尾节点的next指向头节点适合环形缓冲等场景。链式栈/队列的变种如共享栈、双端队列Deque都可以在链表基础上实现。掌握指针和这些基础数据结构是理解更复杂数据结构树、图和算法排序、搜索的基石。建议读者不要只停留在阅读代码一定要亲手在IDE中敲一遍并尝试进行修改和扩展例如实现一个不带头节点的链表或者用链表实现一个简单的LRU缓存这样才能真正内化知识。