期末复习 / 课程实验必备 学习 C 语言数据结构的时候很多同学会头疼链表指针、内存管理、各种增删改查逻辑。网上代码片段多完整带注释工程较少。本篇把平时写的全套链式数据结构代码整理出来单向链表、栈、队列、双向链表、哈希表、二叉树。 所有代码保留原始逻辑不动给每一个函数添加注释标明功能、参数、返回值方便调试也可以直接用于课程实验参考。包含经典算法快慢指针、二叉树四种遍历、哈希冲突处理、内核侵入链表实战示例。注意需要自行补全.h头文件代码务必注意malloc之后配套free避免内存泄漏。说明代码均为链式实现全部手动管理malloc/free内存头文件*.h只放结构体、函数声明.c文件实现逻辑错误处理内存分配失败打印提示并返回 NULL/-11、link.c 有头单向链表功能概述带头部哨兵节点的单向链表。支持头插、尾插、头删、尾删、按值删除、查找、修改、链表销毁快慢指针算法求中间结点、倒数第 k 个结点。#include link.h #include stdlib.h #include stdio.h /******************************** * 功能: 创建有头单向链表哨兵头节点不存业务数据 * 参数无 * 返回值 * 成功返回头结点地址 * 失败: NULL(malloc内存分配失败) * *****************************/ Link_Node *create_link() { Link_Node *phead NULL; phead malloc(sizeof(Link_Node)); if (NULL phead) { printf(fail malloc\n); return NULL; } phead-pnext NULL; return phead; } /************************************************* * 功能单向链表头部插入新节点 * 参数 * phead链表哨兵头结点地址 * data: 需要插入的业务数据 * 返回值 * 成功0 * 失败-1(malloc失败) * ***********************************************/ int insert_head_link(Link_Node *phead, Data_Type data) { Link_Node *pinsert malloc(sizeof(Link_Node)); if (NULL pinsert) { printf(fail malloc\n); return -1; } pinsert-data data; pinsert-pnext NULL; pinsert-pnext phead-pnext; phead-pnext pinsert; return 0; } /************************************************* * 功能遍历链表打印所有有效节点数据 * 参数 * phead链表哨兵头结点地址 * 返回值无 * ***********************************************/ void link_for_each(Link_Node *phead) { Link_Node *p NULL; p phead-pnext; while (p ! NULL) { printf(%d , p-data); p p-pnext; } printf(\n); } /************************************************* * 功能判断单向链表是否为空链表 * 参数 * phead链表哨兵头结点地址 * 返回值 * 链表为空1 * 链表非空0 * ***********************************************/ int is_empty_link(Link_Node *phead) { if (NULL phead-pnext) { return 1; } return 0; } /************************************************* * 功能单向链表尾部插入新节点 * 参数 * phead链表哨兵头结点地址 * data: 需要插入的业务数据 * 返回值 * 成功0 * 失败-1(malloc失败) * ***********************************************/ int insert_tail_link(Link_Node *phead, Data_Type data) { Link_Node *p NULL; Link_Node *pinsert malloc(sizeof(Link_Node)); if (NULL pinsert) { printf(fail malloc\n); return -1; } pinsert-data data; pinsert-pnext NULL; if (is_empty_link(phead)) { phead-pnext pinsert; } else { p phead-pnext; while (p-pnext ! NULL) { p p-pnext; } p-pnext pinsert; } return 0; } /********************************************* * 功能删除链表第一个有效节点删除头后面节点 * 参数 * phead链表哨兵头结点地址 * 返回值 * 成功0空链表也返回0 * ********************************************/ int delete_head_link(Link_Node *phead) { if (is_empty_link(phead)) { return 0; } Link_Node *pdel phead-pnext; phead-pnext pdel-pnext; free(pdel); return 0; } /******************************************* * 功能删除链表尾有效节点 * 参数 * phead链表哨兵头结点地址 * 返回值成功0空链表也返回0 * *****************************************/ int delete_tail_link(Link_Node *phead) { Link_Node *p phead-pnext; if (is_empty_link(phead)) { return 0; } else if (NULL p-pnext) { delete_head_link(phead); } else { while (p-pnext-pnext ! NULL) { p p-pnext; } free(p-pnext); p-pnext NULL; } return 0; } /************************************************* * 功能根据data值查找对应节点 * 参数 * phead链表哨兵头结点地址 * data待匹配查找的数据 * 返回值 * 成功匹配到的节点指针 * 失败NULL(头指针为空 / 没有找到节点) * ***********************************************/ Link_Node *find_link(Link_Node *phead, Data_Type data) { if (NULL phead) { printf(phead is null\n); return NULL; } Link_Node *p phead-pnext; while (p) { if (p-data data) { return p; } p p-pnext; } return NULL; } /************************************************* * 功能修改链表指定节点数据 * 参数 * phead链表哨兵头结点地址 * olddata需要被修改的旧数据 * newdata替换后的新数据 * 返回值 * 成功0 * 失败-1(头指针空 / 找不到对应节点) * ***********************************************/ int change_link(Link_Node *phead, Data_Type olddata, Data_Type newdata) { if (NULL phead) { printf(phead is null\n); return -1; } Link_Node *ptmp find_link(phead, olddata); if (NULL ptmp) { return -1; } ptmp-data newdata; return 0; } /************************************************* * 功能销毁整个链表释放全部有效节点哨兵头节点 * 参数 * phead链表哨兵头结点地址 * 返回值无 * ***********************************************/ void destroy_link(Link_Node *phead) { if (NULL phead) { printf(phead is null\n); return ; } while (!is_empty_link(phead)) { delete_head_link(phead); } free(phead); return ; } /************************************************* * 功能删除链表中第一个匹配data的节点 * 参数 * phead链表哨兵头结点地址 * data待删除节点的业务数据 * 返回值 * 成功0 * 失败-1(头指针空 / 找不到对应节点) * ***********************************************/ int delete_point_node(Link_Node *phead, Data_Type data) { if (NULL phead) { printf(phead is null\n); return -1; } Link_Node *pdel NULL; Link_Node *ppre phead; while (ppre-pnext ! NULL) { if (ppre-pnext-data data) { pdel ppre-pnext; ppre-pnext pdel-pnext; free(pdel); return 0; } ppre ppre-pnext; } return -1; } /************************************************* * 功能快慢指针算法查找链表中间节点 * 参数 * phead链表哨兵头结点地址 * 返回值 * 成功中间节点指针 * 失败NULL(头空 / 链表为空) * ***********************************************/ Link_Node * find_mid_node(Link_Node *phead) { if (NULL phead) { printf(phead is null\n); return NULL; } if (is_empty_link(phead)) return NULL; Link_Node *pfast phead-pnext; Link_Node *pslaw pfast; while (pfast ! NULL) { pfast pfast-pnext; if (pfast ! NULL) { pfast pfast-pnext; pslaw pslaw-pnext; } } return pslaw; } /************************************************* * 功能快慢指针查找链表倒数第K个节点 * 参数 * phead链表哨兵头结点地址 * K倒数第k个节点下标 * 返回值 * 成功倒数第K个节点指针 * 失败NULL(头空 / 链表空 / K值超出链表长度) * ***********************************************/ Link_Node *find_last_k_node(Link_Node *phead, int K) { if (NULL phead) { printf(phead is null\n); return NULL; } if (is_empty_link(phead)) { return NULL; } Link_Node *pfast phead-pnext; Link_Node *pslow phead-pnext; for (int i 0; i K; i) { if (NULL pfast) { return NULL; } pfast pfast-pnext; } while (pfast ! NULL) { pfast pfast-pnext; pslow pslow-pnext; } return pslow; }2、queue.c 链式队列功能概述链式实现队列遵循先进先出 FIFO。队列控制块保存头指针、尾指针、元素计数支持入队、出队、获取队头元素、清空队列、销毁队列。二叉树层序遍历依赖该队列。#include queue.h #include stdio.h #include stdlib.h /************************************************* * 功能创建链式队列控制块初始化头尾指针、元素计数 * 参数无 * 返回值 * 成功队列控制块指针 * 失败NULL(malloc失败) * ***********************************************/ Queue *create_queue() { Queue *pque malloc(sizeof(Queue)); if (NULL pque) { printf(fail malloc\n); return NULL; } pque-phead NULL; pque-ptail NULL; pque-clen 0; return pque; } /************************************************* * 功能判断队列是否为空 * 参数 * pque队列控制块指针 * 返回值 * 队列为空1 * 队列非空0 * ***********************************************/ int is_empty_queue(Queue *pque) { return NULL pque-phead; } /************************************************* * 功能入队操作在队尾新增节点 * 参数 * pque队列控制块指针 * data待入队数据 * 返回值 * 成功0 * 失败-1(队列指针为空 / malloc失败) * ***********************************************/ int push_queue(Queue *pque, Data_Type data) { if (NULL pque) return -1; Que_Node *pnode malloc(sizeof(Que_Node)); if (NULL pnode) { printf(fail malloc\n); return -1; } pnode-data data; pnode-pnext NULL; if (is_empty_queue(pque)) { pque-phead pnode; pque-ptail pnode; } else { pque-ptail-pnext pnode; pque-ptail pnode; } pque-clen; return 0; } /************************************************* * 功能出队操作删除队头节点 * 参数 * pque队列控制块指针 * pdata输出参数保存出队数据可以传入NULL不需要接收数据 * 返回值 * 成功0 * 失败-1(队列为空 / 队列指针为空) * ***********************************************/ int pop_queue(Queue *pque, Data_Type *pdata) { if (NULL pque) return -1; if (is_empty_queue(pque)) return -1; Que_Node *pdel pque-phead; pque-phead pdel-pnext; if (NULL pque-phead) { pque-ptail NULL; } if (pdata ! NULL) { *pdata pdel-data; } free(pdel); pque-clen--; return 0; } /************************************************* * 功能清空队列所有业务节点不销毁队列控制块 * 参数 * pque队列控制块指针 * 返回值无 * ***********************************************/ void clear_queue(Queue *pque) { if (NULL pque) return ; while (!is_empty_queue(pque)) pop_queue(pque, NULL); } /************************************************* * 功能获取队头元素不删除节点 * 参数 * pque队列控制块指针 * pdata输出参数接收队头数据 * 返回值 * 成功0 * 失败-1(队列为空 / 队列指针为空) * ***********************************************/ int get_queue_head(Queue *pque, Data_Type *pdata) { if (NULL pque) return -1; if (is_empty_queue(pque)) return -1; if (pdata ! NULL) { *pdata pque-phead-data; } return 0; } /************************************************* * 功能销毁整个队列释放全部业务节点队列控制块内存 * 参数 * pque队列控制块指针 * 返回值无 * ***********************************************/ void destroy_queue(Queue *pque) { if (NULL pque) return; clear_queue(pque); free(pque); } /************************************************* * 功能遍历打印队列全部元素 * 参数 * pque队列控制块指针 * 返回值无 * ***********************************************/ void queue_for_each(Queue *pque) { if (NULL pque) return ; Que_Node *p pque-phead; while (p) { printf(%d , p-data); p p-pnext; } printf(\n); }3、stack.c 链式栈功能概述链式栈遵循后进先出 LIFO所有操作都在栈顶完成。支持入栈、出栈、获取栈顶、清空栈、销毁栈。#include stack.h #include stdio.h #include stdlib.h /************************************************* * 功能创建链式栈控制块初始化栈顶指针、元素计数 * 参数无 * 返回值 * 成功栈控制块指针 * 失败NULL(malloc失败) * ***********************************************/ Stack *create_stack() { Stack *pstack malloc(sizeof(Stack)); if (NULL pstack) { printf(fail malloc); return NULL; } pstack-ptop NULL; pstack-clen 0; return pstack; } /************************************************* * 功能入栈栈顶位置插入新节点 * 参数 * pstack栈控制块指针 * data待入栈业务数据 * 返回值 * 成功0 * 失败-1(栈指针为空 / malloc失败) * ***********************************************/ int push_stack(Stack *pstack, Data_Type data) { if (NULL pstack) { printf(pstack is null\n); return -1; } Stack_Node *pnode malloc(sizeof(Stack_Node)); if (NULL pnode) { printf(malloc fail\n); return -1; } pnode-data data; pnode-pnext pstack-ptop; pstack-ptop pnode; pstack-clen; return 0; } /************************************************* * 功能遍历打印栈从栈顶向栈底输出 * 参数 * pstack栈控制块指针 * 返回值无 * ***********************************************/ void stack_for_each(Stack *pstack) { if (NULL pstack) { printf(pstack is null\n); return ; } Stack_Node *p pstack-ptop; while (p ! NULL) { printf(%d , p-data); p p-pnext; } printf(\n); } /************************************************* * 功能判断栈是否为空 * 参数 * pstack栈控制块指针 * 返回值 * 栈为空1 * 栈非空0 * ***********************************************/ int is_empty_stack(Stack *pstack) { return NULL pstack-ptop; } /************************************************* * 功能出栈删除栈顶节点 * 参数 * pstack栈控制块指针 * pdata输出参数接收出栈数据可以传NULL * 返回值 * 成功0 * 失败-1(栈空 / 栈指针为空) * ***********************************************/ int pop_stack(Stack *pstack, Data_Type *pdata) { if (NULL pstack) { printf(pstack is null\n); return -1; } if (is_empty_stack(pstack)) return -1; Stack_Node *pdel pstack-ptop; pstack-ptop pdel-pnext; if (pdata ! NULL) { *pdata pdel-data; } free(pdel); pstack-clen--; return 0; } /************************************************* * 功能获取栈顶数据不弹出节点 * 参数 * pstack栈控制块指针 * pdata输出参数接收栈顶数据 * 返回值 * 成功0 * 失败-1(栈空 / 栈指针为空) * ***********************************************/ int get_stack_top(Stack *pstack, Data_Type *pdata) { if (NULL pstack) { printf(pstack is null\n); return -1; } if (is_empty_stack(pstack)) return -1; if (pdata ! NULL) { *pdata pstack-ptop-data; } return 0; } /************************************************* * 功能清空栈所有业务节点不销毁栈控制块 * 参数 * pstack栈控制块指针 * 返回值无 * ***********************************************/ void clear_stack(Stack *pstack) { if (NULL pstack) { printf(pstack is null\n); return ; } while (!is_empty_stack(pstack)) pop_stack(pstack, NULL); } /************************************************* * 功能销毁整个栈释放业务节点栈控制块 * 参数 * pstack栈控制块指针 * 返回值无 * ***********************************************/ void destroy_stack(Stack *pstack) { if (NULL pstack) { printf(pstack is null\n); return ; } clear_stack(pstack); free(pstack); }4、doulink.h 带头双向链表头文件功能概述带头双向链表每个节点拥有前驱ppre、后继pnext指针头文件只放结构体定义与函数声明。#ifndef __DOULINK_H__ #define __DOULINK_H__ //双向链表存储业务数据结构体 typedef struct stu { int id; char name[32]; int score; }Data_Type; //双向链表结点类型 typedef struct node { Data_Type data; //数据域 struct node *ppre; //前驱指针域 struct node *pnext; //后继指针域 }Dou_Node; /** * brief 创建有头双向链表头节点 * return 成功返回头节点指针失败返回NULL */ extern Dou_Node *create_doulink(); /** * brief 双向链表头部插入节点 * param phead 双向链表哨兵头节点 * param data 待插入业务数据 * return 成功0失败-1 */ extern int insert_head_doulink(Dou_Node *phead, Data_Type data); /** * brief 双向链表遍历dir控制正向/反向遍历 * param phead 双向链表哨兵头节点 * param dir 遍历方向标识 * return 无返回值 */ extern void doulink_for_each(Dou_Node*phead, int dir); /** * brief 双向链表尾部插入节点 * param phead 双向链表哨兵头节点 * param data 待插入业务数据 * return 成功0失败-1 */ extern int insert_tail_doulink(Dou_Node *phead, Data_Type data); /** * brief 删除双向链表头部有效节点 * param phead 双向链表哨兵头节点 * return 成功0失败-1 */ extern int delete_head_doulink(Dou_Node *phead); /** * brief 删除双向链表尾部有效节点 * param phead 双向链表哨兵头节点 * return 成功0失败-1 */ extern int delete_tail_doulink(Dou_Node *phead); /** * brief 根据名字查找双向链表节点 * param phead 双向链表哨兵头节点 * param name 待查找名字字符串 * return 找到返回节点指针找不到返回NULL */ extern Dou_Node *find_doulink(Dou_Node *phead, char *name); /** * brief 销毁双向链表全部节点内存 * param phead 双向链表哨兵头节点 * return 无返回值 */ extern void destroy_doulink(Dou_Node *phead); #endif5、hash.c 拉链法哈希表功能概述采用拉链法解决哈希冲突哈希函数取名字首字母映射数组下标链表头插法插入元素实现插入、遍历、查找、销毁哈希表。#include hash.h #include stdio.h #include stdlib.h #include string.h /************************************************* * brief 哈希映射函数字符转换哈希表数组下标 * param key 输入字符一般取姓名首字母 * return 哈希数组下标 * note 大小写a‑z/A‑Z映射0‑25其他字符映射哈希表最后一个位置 * ***********************************************/ int hash_function(char key) { if (key a key z) { return key-a; } else if (key A key Z) { return key-A; } else { return HASH_MAX_SIZE-1; } } /************************************************* * brief 拉链哈希表头插法插入一条数据 * param hash_table 哈希表指针数组 * param data 待插入业务数据 * return 成功0失败‑1(malloc失败) * ***********************************************/ int insert_hash_table(Hash_Node **hash_table, Data_Type data) { int addr hash_function(data.name[0]); Hash_Node *pnode malloc(sizeof(Hash_Node)); if (NULL pnode) { printf(fail malloc\n); return -1; } pnode-data data; pnode-pnext NULL; pnode-pnext hash_table[addr]; hash_table[addr] pnode; return 0; } /************************************************* * brief 完整遍历哈希表输出全部存储元素 * param hash_table 哈希表指针数组 * return 无返回值 * ***********************************************/ void hash_for_each(Hash_Node **hash_table) { Hash_Node *p NULL; for (int i 0; i HASH_MAX_SIZE; i) { p hash_table[i]; while (p) { printf(%s:%s\n, p-data.name, p-data.tel); p p-pnext; } printf(\n); } } /************************************************* * brief 根据姓名查找哈希表元素并打印匹配结果 * param hash_table 哈希表指针数组 * param name 待查找姓名 * return 固定返回0 * ***********************************************/ int find_hash_table(Hash_Node **hash_table, char *name) { int addr hash_function(name[0]); Hash_Node *p hash_table[addr]; while (p) { if (0 strncmp(p-data.name, name, strlen(name))) { printf(%s:%s\n, p-data.name, p-data.tel); } p p-pnext; } return 0; } /************************************************* * brief 销毁哈希表所有链表节点内存 * param hash_table 哈希表指针数组 * return 无返回值 * ***********************************************/ void destroy_hash_table(Hash_Node **hash_table) { Hash_Node *pdel NULL; for (int i 0; i HASH_MAX_SIZE; i) { while (hash_table[i] ! NULL) { pdel hash_table[i]; hash_table[i] pdel - pnext; free(pdel); } } }6、tree.c 二叉树功能概述二叉树使用先序序列化字符串#代表空节点递归构建二叉树实现先序、中序、后序递归遍历统计节点总数、求树深度队列实现层序广度遍历后序递归销毁整棵树。#include tree.h #include stdio.h #include stdlib.h #include queue.h //二叉树先序序列化字符串#代表空节点 char tree[] ABE#C##FM###DG##HI###; int idx 0; /************************************************* * brief 根据先序序列化字符串递归创建二叉树 * return 树根节点指针失败返回NULL * note 全局变量tree读取字符串idx记录当前读取位置#代表空节点返回NULL * ***********************************************/ Tree_Node *create_bin_tree() { BTData_Type mydata tree[idx]; if (# mydata) { return NULL; } Tree_Node *pnode malloc(sizeof(Tree_Node)); if (NULL pnode) { printf(fail malloc\n); return NULL; } pnode-data mydata; pnode-pl create_bin_tree(); pnode-pr create_bin_tree(); return pnode; } /************************************************* * brief 二叉树先序遍历根 → 左子树 → 右子树 * param proot 二叉树根节点指针 * return 无返回值 * ***********************************************/ void pre_order(Tree_Node *proot) { if (NULL proot) return ; printf(%c, proot-data); pre_order(proot-pl); pre_order(proot-pr); } /************************************************* * brief 二叉树中序遍历左子树 → 根 → 右子树 * param proot 二叉树根节点指针 * return 无返回值 * ***********************************************/ void mid_order(Tree_Node *proot) { if (NULL proot) return ; mid_order(proot-pl); printf(%c, proot-data); mid_order(proot-pr); } /************************************************* * brief 二叉树后序遍历左子树 → 右子树 → 根 * param proot 二叉树根节点指针 * return 无返回值 * ***********************************************/ void pos_order(Tree_Node *proot) { if (NULL proot) return; pos_order(proot-pl); pos_order(proot-pr); printf(%c, proot-data); } /************************************************* * brief 统计二叉树总节点数量 * param proot 二叉树根节点指针 * return 节点个数空树返回0 * ***********************************************/ int get_tree_node_cnt(Tree_Node *proot) { if (NULL proot) return 0; return 1get_tree_node_cnt(proot-pl)get_tree_node_cnt(proot-pr); } /************************************************* * brief 获取二叉树深度树层数 * param proot 二叉树根节点指针 * return 树深度空树返回0 * ***********************************************/ int get_tree_layer_cnt(Tree_Node *proot) { if (NULL proot) return 0; int cntl get_tree_layer_cnt(proot-pl); int cntr get_tree_layer_cnt(proot-pr); return cntl cntr ? cntl1 : cntr1; } /************************************************* * brief 后序递归销毁二叉树所有节点内存 * param proot 二叉树根节点指针 * return 无返回值 * ***********************************************/ void destroy_tree(Tree_Node *proot) { if (NULL proot) return; destroy_tree(proot-pl); destroy_tree(proot-pr); free(proot); } /************************************************* * brief 二叉树层序遍历广度优先BFS依赖队列实现 * param proot 二叉树根节点指针 * return 无返回值 * ***********************************************/ void layer_order(Tree_Node *proot) { if (NULL proot) return; Queue *pque create_queue(); if (NULL pque) return; Data_Type outdata; push_queue(pque, proot); while (!is_empty_queue(pque)) { pop_queue(pque, outdata); printf(%c,outdata-data); if (outdata-pl ! NULL) { push_queue(pque, outdata-pl); } if (outdata-pr ! NULL) { push_queue(pque, outdata-pr); } } destroy_queue(pque); }知识点总结一、单向链表 link.c带哨兵头节点头插 O (1)、尾插 O (n)经典算法快慢指针求中间节点、快慢指针求倒数第 K 节点内存管理销毁必须释放头节点 全部业务节点。二、链式栈 stack.cLIFO 后进先出全部操作在栈顶入栈头插出栈删除头节点。三、链式队列 queue.cFIFO 先进先出队尾入队队头出队维护头、尾指针提升效率典型应用场景二叉树层序遍历BFS 广度优先搜索。四、双向链表 doulink.h节点同时保存前驱ppre、后继pnext找前驱不需要遍历插入删除注意两个指针都要修改。五、二叉树 tree.c构建利用先序序列化字符串递归构建二叉树#标记空节点三种深度优先 DFS 遍历先序、中序、后序广度优先 BFS层序遍历依赖队列常用算法统计节点总数、求树深度后序方式销毁整棵树。