C语言：单链表与栈队列实现

前言本文基于指针与动态内存管理核心知识点系统讲解C语言三大基础数据结构。内容涵盖结构定义、核心操作实现及高频面试真题解析所有代码严格遵循笔试规范注重边界条件处理和内存安全。作为嵌入式及C/C岗位笔试第二大高频考点本专题既适合零基础入门也适用于知识点巩固与校招/社招面试冲刺复习。一、单链表全解链表是线性表的链式存储结构通过指针将离散的内存节点串联起来解决了数组插入删除效率低、大小固定的痛点是指针与动态内存最经典的落地场景。1. 链表 vs 数组核心对比对比维度数组单链表内存分布连续内存空间离散内存节点通过指针连接大小固定性大小固定扩容麻烦动态增减按需申请释放随机访问支持下标 O (1) 随机访问不支持随机访问必须从头遍历 O (n)插入删除中间插入删除需移动元素 O (n)已知位置时仅需修改指针 O (1)内存利用率有预分配空间浪费无浪费但每个节点多一个指针开销2. 节点定义#include stdio.h #include stdlib.h #include assert.h // 单链表节点结构 typedef int SLTDataType; typedef struct SListNode { SLTDataType data; // 数据域 struct SListNode* next; // 指针域指向下一个节点 } SListNode;3. 核心操作手撕实现① 创建新节点// 创建一个值为x的新节点 SListNode* BuySListNode(SLTDataType x) { SListNode* newNode (SListNode*)malloc(sizeof(SListNode)); if (newNode NULL) { perror(malloc failed); exit(-1); } newNode-data x; newNode-next NULL; return newNode; }② 尾插法末尾插入节点// 在链表尾部插入值为x的节点 void SListPushBack(SListNode** pphead, SLTDataType x) { assert(pphead ! NULL); SListNode* newNode BuySListNode(x); // 空链表直接让头指针指向新节点 if (*pphead NULL) { *pphead newNode; return; } // 非空找到尾节点 SListNode* tail *pphead; while (tail-next ! NULL) { tail tail-next; } tail-next newNode; }注意修改头指针必须传二级指针否则只是修改形参副本。③ 头插法头部插入节点// 在链表头部插入值为x的节点 void SListPushFront(SListNode** pphead, SLTDataType x) { assert(pphead ! NULL); SListNode* newNode BuySListNode(x); // 新节点指向原头头指针更新为新节点 newNode-next *pphead; *pphead newNode; }④ 尾删法删除尾节点// 删除链表最后一个节点 void SListPopBack(SListNode** pphead) { assert(pphead ! NULL); assert(*pphead ! NULL); // 空链表不能删 // 只有一个节点直接释放头置空 if ((*pphead)-next NULL) { free(*pphead); *pphead NULL; return; } // 多个节点找到倒数第二个节点 SListNode* prev *pphead; while (prev-next-next ! NULL) { prev prev-next; } free(prev-next); prev-next NULL; }⑤ 头删法删除头节点// 删除链表第一个节点 void SListPopFront(SListNode** pphead) { assert(pphead ! NULL); assert(*pphead ! NULL); SListNode* del *pphead; *pphead del-next; // 头指针移到下一个 free(del); }⑥ 查找节点// 查找值为x的节点找到返回节点地址找不到返回NULL SListNode* SListFind(SListNode* phead, SLTDataType x) { SListNode* cur phead; while (cur ! NULL) { if (cur-data x) { return cur; } cur cur-next; } return NULL; }⑦ 指定位置后插入// 在pos节点之后插入值为x的节点 void SListInsertAfter(SListNode* pos, SLTDataType x) { assert(pos ! NULL); SListNode* newNode BuySListNode(x); newNode-next pos-next; pos-next newNode; }⑧ 销毁整个链表// 销毁链表释放所有节点 void SListDestroy(SListNode** pphead) { assert(pphead ! NULL); SListNode* cur *pphead; while (cur ! NULL) { SListNode* next cur-next; free(cur); cur next; } *pphead NULL; }二、栈的实现与应用栈是一种 ** 后进先出LIFO** 的线性表只能在栈顶进行插入和删除操作是算法题中最常用的数据结构之一。1. 顺序栈数组实现数组实现的栈缓存友好、访问效率高是工业界主流实现方式。结构定义typedef int STDataType; typedef struct Stack { STDataType* a; // 动态数组 int top; // 栈顶位置指向栈顶元素的下一个位置 int capacity; // 栈容量 } Stack;初始化与销毁// 初始化栈 void StackInit(Stack* ps) { assert(ps ! NULL); ps-a (STDataType*)malloc(sizeof(STDataType) * 4); if (ps-a NULL) { perror(malloc failed); exit(-1); } ps-top 0; ps-capacity 4; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps ! NULL); free(ps-a); ps-a NULL; ps-top ps-capacity 0; }入栈与扩容// 元素入栈 void StackPush(Stack* ps, STDataType x) { assert(ps ! NULL); // 满了则扩容 if (ps-top ps-capacity) { int newCapacity ps-capacity * 2; STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity); if (tmp NULL) { perror(realloc failed); exit(-1); } ps-a tmp; ps-capacity newCapacity; } ps-a[ps-top] x; ps-top; }出栈与取栈顶// 栈顶元素出栈 void StackPop(Stack* ps) { assert(ps ! NULL); assert(ps-top 0); // 空栈不能删 ps-top--; } // 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps ! NULL); assert(ps-top 0); return ps-a[ps-top - 1]; } // 判断栈是否为空 int StackEmpty(Stack* ps) { assert(ps ! NULL); return ps-top 0; }2. 链栈链表实现用链表头作为栈顶头插头删模拟入栈出栈优点是无容量限制缺点是每个节点有指针开销缓存性差。面试中优先写数组实现更简洁高效符合常规考察方向。三、队列的实现与应用队列是一种先进先出FIFO的线性表只能在队尾插入、队头删除常用于任务调度、消息缓冲等场景。1. 循环队列数组实现数组实现队列如果直接用头尾指针出队后前面的空间会浪费因此采用循环队列复用空间是面试核心考点。核心难点判空与判满循环队列头尾重合时无法区分是空还是满主流两种解决方案牺牲一个存储单元约定尾指针下一个是头指针时为满最常用面试首选增加 size 计数变量额外维护元素个数空时 size0满时 size 容量结构定义牺牲一个单元方案typedef int QDataType; typedef struct CircularQueue { QDataType* a; int front; // 队头下标 int rear; // 队尾下标指向队尾元素的下一个位置 int capacity; // 总容量实际有效元素数为capacity-1 } CQueue;初始化// 初始化循环队列k为有效元素最大个数 void CQueueInit(CQueue* q, int k) { assert(q ! NULL); // 多开一个空间用于区分空满 q-a (QDataType*)malloc(sizeof(QDataType) * (k 1)); q-front q-rear 0; q-capacity k 1; }入队与判满// 入队成功返回1满了返回0 int CQueueEnQueue(CQueue* q, QDataType x) { assert(q ! NULL); if ((q-rear 1) % q-capacity q-front) { return 0; // 队列已满 } q-a[q-rear] x; q-rear (q-rear 1) % q-capacity; return 1; }出队与判空// 出队成功返回1空队列返回0 int CQueueDeQueue(CQueue* q) { assert(q ! NULL); if (q-front q-rear) { return 0; // 队列为空 } q-front (q-front 1) % q-capacity; return 1; } // 获取队头元素 QDataType CQueueFront(CQueue* q) { assert(q ! NULL); assert(q-front ! q-rear); return q-a[q-front]; } // 判断队列是否为空 int CQueueIsEmpty(CQueue* q) { assert(q ! NULL); return q-front q-rear; }2. 链队列链表实现用链表头尾分别作为队头队尾尾插头删适合元素数量不确定的场景实现简单但缓存效率低。四、高频面试手撕真题1. 反转单链表笔试 100% 高频题目给你单链表的头节点反转该链表并返回反转后的头节点。思路三指针迭代法逐个改变节点指向。struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* cur head; while (cur ! NULL) { struct ListNode* next cur-next; // 保存下一个节点 cur-next prev; // 反转当前节点指向 prev cur; // prev后移 cur next; // cur后移 } return prev; // prev最终成为新头 }2. 链表判环快慢指针经典题题目判断链表中是否有环。思路快慢指针快指针每次走两步慢指针每次走一步有环则一定会相遇。bool hasCycle(struct ListNode *head) { struct ListNode* slow head; struct ListNode* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; }3. 有效的括号栈经典应用题目给定一个只包含括号的字符串判断括号是否有效闭合。思路左括号入栈遇到右括号则匹配栈顶不匹配或栈空则无效最后栈空则有效。bool isValid(char * s) { Stack st; StackInit(st); for (int i 0; s[i] ! \0; i) { // 左括号入栈 if (s[i] ( || s[i] [ || s[i] {) { StackPush(st, s[i]); } else { // 右括号时栈空无效 if (StackEmpty(st)) { StackDestroy(st); return false; } char top StackTop(st); StackPop(st); // 匹配校验 if ((s[i] ) top ! () || (s[i] ] top ! [) || (s[i] } top ! {)) { StackDestroy(st); return false; } } } // 最后栈必须为空 bool ret StackEmpty(st); StackDestroy(st); return ret; }4. 用栈实现队列题目用两个栈实现一个队列支持入队、出队、取队头、判空。思路一个栈负责入队一个栈负责出队出队栈空时把入队栈全部倒入出队栈顺序就反转成了队列顺序。typedef struct { Stack pushSt; // 入队栈 Stack popSt; // 出队栈 } MyQueue; void myQueuePush(MyQueue* obj, int x) { StackPush(obj-pushSt, x); } int myQueuePop(MyQueue* obj) { // 出队栈空了把入队栈全部倒过来 if (StackEmpty(obj-popSt)) { while (!StackEmpty(obj-pushSt)) { StackPush(obj-popSt, StackTop(obj-pushSt)); StackPop(obj-pushSt); } } int ret StackTop(obj-popSt); StackPop(obj-popSt); return ret; }五、面试高频考点与易错坑点1. 经典面试问答Q1数组和链表有什么区别各自的适用场景答内存分布数组是连续内存链表是离散节点通过指针连接访问效率数组支持 O (1) 随机访问链表必须遍历 O (n)增删效率数组中间增删需移动元素 O (n)链表已知位置时增删 O (1)空间扩容数组大小固定扩容有开销链表动态增减按需分配 适用场景数据量固定、频繁随机访问选数组频繁增删、数据量不确定选链表。Q2栈和队列有什么区别各有什么典型应用答 栈是后进先出队列是先进先出。 栈的典型应用括号匹配、表达式求值、函数调用栈、递归转迭代 队列的典型应用任务调度、消息缓冲、广度优先搜索、生产者消费者模型。Q3循环队列为什么要牺牲一个单元还有其他方案吗答 因为循环队列中头尾指针重合时无法区分队列是空还是满。 牺牲一个存储单元是最常用的方案约定 rear 下一个位置是 front 时为满空时则是 rearfront以此区分两种状态。 其他方案额外增加一个 size 变量记录元素个数空时 size0满时 size 等于容量逻辑更直观但多一个变量开销。Q4单链表为什么常用二级指针传参什么时候需要二级指针答 当我们需要修改链表的头指针本身时比如头插、头删、空链表插入第一个节点就必须传头指针的地址也就是二级指针。 因为 C 语言传参是传值直接传头指针只是传了一份副本函数内修改副本不会影响外面的头指针。如果只是遍历、修改节点数据不修改头指针传一级指针即可。Q5反转链表有哪些方法迭代法的核心思路是什么答 主要有迭代法和递归法两种面试优先写迭代法更直观无栈溢出风险。 迭代法核心是三指针prev 记录前一个节点cur 记录当前节点next 保存下一个节点遍历过程中逐个将 cur 的 next 指向 prev同时三个指针同步后移最终 prev 成为新的头节点。2. 常见易错坑点空链表不判空删除、查找操作前不判断链表是否为空直接解引用空指针崩溃尾删漏处理单节点只处理多节点情况只剩一个节点时尾删会出现野指针修改头指针不传二级指针头插头删只传一级指针导致外面头指针没变化循环队列取模遗漏头尾指针移动忘记取模导致数组越界链表销毁只释放头节点只 free 头节点其余节点全部泄漏必须遍历逐个释放插入节点顺序错误先断开原链接再赋值新节点 next导致后续节点地址丢失以上就是单链表、栈、队列的全部核心内容是数据结构的入门基础也是笔试手撕代码的高频必考题建议结合代码手动实现重点掌握边界条件处理与底层逻辑。制作不易如果对你有用希望能点赞收藏支持一下。