一、单向链表基础概念单向链表属于线性链式存储结构结点分为数据域存储有效数据 指针域保存下一个结点的地址仅能单向向后遍历不能回退访问前面结点使用管理结构体保存链表头指针、结点总数量优点动态malloc分配内存不需要预先分配整块内存插入删除不需要大量移动元素只修改指针缺点不支持随机访问查找元素必须从头开始遍历指针域会额外消耗一部分内存文件说明link001.h头文件结构体定义 函数声明link001.c源文件链表所有功能实现main001.c测试main函数二、头文件 link001.h#ifndef _LINK001_H #define _LINK001_H #include stdio.h #include stdlib.h /* 链表结点结构体 */ typedef struct node { int data; //数据域 struct node *pnext; //指针域指向下一个结点 }Node_t; /* 链表管理结构体 */ typedef struct link { Node_t *phead; //链表头结点指针 int clen; //链表结点个数 }Link_t; //函数对外声明 extern Link_t *create_link(); extern int insert_link_head(Link_t *plink,int data); extern int insert_link_tail(Link_t *plink,int data); extern void free_link_head(Link_t *plink); extern void free_link_tail(Link_t *plink); extern int free_link(Link_t *plink); extern void show_link(Link_t *plink); extern Node_t *check_link(Link_t *plink,int data); extern Link_t *change_link(Link_t *plink,int data0,int data1); extern int free_data_node(Link_t *plink,int data); extern Link_t *nixu_link(Link_t *plink); extern Link_t *shengxu_link(Link_t *plink); #endif三、功能实现 link001.c1. create_link 创建链表功能分配链表管理结构体初始化头指针置NULL、结点计数clen为0。Link_t *create_link() { Link_t *plink malloc(sizeof(Link_t)); if(plink NULL) { printf(malloc error\n); return NULL; } plink-phead NULL; //空链表头置NULL plink-clen 0; return plink; }2. insert_link_head 头插法功能在链表头部插入新结点新结点指向原头结点更新链表头指针计数自增。 返回0成功‑1失败链表指针为NULL或者malloc失败。int insert_link_head(Link_t *plink,int data) { if(plink NULL) return -1; Node_t *pinsert malloc(sizeof(Node_t)); if(pinsert NULL) { printf(malloc error\n); return -1; } pinsert-data data; pinsert-pnext plink-phead; //新结点指向原来头结点 plink-phead pinsert; //更新头指针 plink-clen; return 0; }3. insert_link_tail 尾插法功能在链表尾部插入结点链表为空直接挂头链表非空遍历找到末尾结点末尾结点指向新结点计数自增。 返回0成功‑1失败。int insert_link_tail(Link_t *plink,int data) { if(plink NULL) return -1; Node_t *pinsert malloc(sizeof(Node_t)); if(pinsert NULL) { printf(malloc error\n); return -1; } pinsert-data data; pinsert-pnext NULL; if(plink-clen ! 0) { Node_t *ptemp plink-phead; while(ptemp-pnext ! NULL) //循环找到最后一个结点 { ptemp ptemp-pnext; } ptemp-pnext pinsert; } else { plink-phead pinsert; //空链表头直接指向新结点 } plink-clen; return 0; }4. free_link_head 头删功能删除链表的第一个结点移动头指针释放旧头结点计数减一空链表直接返回。void free_link_head(Link_t *plink) { if(plink NULL || plink-clen 0) return; Node_t *pfree plink-phead; plink-phead pfree-pnext; //头指针向后移动 free(pfree); //释放旧头结点 plink-clen--; }5. free_link_tail 尾删功能删除链表最后一个结点结点数为1调用头删结点≥2找到倒数第二个结点释放尾结点。void free_link_tail(Link_t *plink) { if(plink NULL || plink-clen 0) return; if(plink-clen 2) { Node_t *pfree plink-phead; while(pfree-pnext-pnext ! NULL) //找到倒数第二个结点 { pfree pfree-pnext; } free(pfree-pnext); pfree-pnext NULL; plink-clen--; } else if(plink-clen 1) { free_link_head(plink); //只有一个结点直接调用头删 } }6. free_link 销毁整个链表功能循环头删释放全部数据结点最后释放链表管理结构体。 返回0成功‑1入参指针为NULL。int free_link(Link_t *plink) { if(plink NULL) return -1; while(plink-clen ! 0) { free_link_head(plink); } free(plink); //释放管理结构体 return 0; }7. show_link 遍历打印链表功能从头结点开始循环遍历打印链表所有data数据。void show_link(Link_t *plink) { if(plink NULL) { printf(link ptr is NULL\n); return; } Node_t *ptemp plink-phead; while (ptemp ! NULL) { printf(%d ,ptemp-data); ptemp ptemp-pnext; } printf(\n); }8. check_link 查找结点功能根据data值遍历链表查找结点找到返回结点地址找不到返回NULL。Node_t *check_link(Link_t *plink,int data) { if(plink NULL) return NULL; Node_t *ptemp plink-phead; while (ptemp ! NULL) { if(ptemp-data data) { return ptemp; //找到返回结点指针 } ptemp ptemp-pnext; } return NULL; //未找到 }9. change_link 修改结点数据功能查找data0将结点数据修改为data1成功返回链表指针失败返回NULL。Link_t *change_link(Link_t *plink,int data0,int data1) { if(plink NULL) return NULL; Node_t *ptemp check_link(plink, data0); if(ptemp ! NULL) { ptemp-data data1; return plink; } return NULL; }10. free_data_node 按值删除结点功能删除链表第一个data等于入参的结点区分删除头结点、中间结点、尾结点。 返回0成功‑1失败空链表/没有找到元素。int free_data_node(Link_t *plink,int data) { if(plink NULL || plink-clen 0) return -1; Node_t *pcur plink-phead; Node_t *ppre NULL; //保存前驱结点 while(pcur ! NULL pcur-data ! data) { ppre pcur; pcur pcur-pnext; } if(pcur NULL) return -1; //没有找到目标结点 if(ppre NULL) { //待删结点是头结点 plink-phead pcur-pnext; } else { //中间或者尾部结点前驱跳过待删结点 ppre-pnext pcur-pnext; } free(pcur); plink-clen--; return 0; }11. nixu_link 链表反转功能借助临时链表头插实现链表反转结点数小于等于1直接返回原链表。 返回反转后的链表指针。Link_t *nixu_link(Link_t *plink) { if(plink NULL || plink-clen 1) return plink; Link_t *ptmp_link create_link(); if(ptmp_link NULL) return plink; Node_t *pnode plink-phead; while(pnode ! NULL) { insert_link_head(ptmp_link, pnode-data); pnode pnode-pnext; } //清空原链表结点 while(plink-clen 0) { free_link_head(plink); } //接管临时链表数据 plink-clen ptmp_link-clen; plink-phead ptmp_link-phead; free(ptmp_link); return plink; }12. shengxu_link 链表升序插入排序功能直接插入排序对单向链表进行升序排列。 返回排序完成的链表指针。Link_t *shengxu_link(Link_t *plink) { if(plink NULL || plink-clen 1) return plink; Node_t *ptmp plink-phead-pnext; plink-phead-pnext NULL; Node_t *pinsert; while(ptmp ! NULL) { pinsert ptmp; ptmp ptmp-pnext; if(pinsert-data plink-phead-data) { //插入链表头部 pinsert-pnext plink-phead; plink-phead pinsert; } else { //向后寻找插入位置 Node_t *p plink-phead; while(p-pnext ! NULL p-pnext-data pinsert-data) { p p-pnext; } pinsert-pnext p-pnext; p-pnext pinsert; } } return plink; }四、测试main函数 main001.c#include link001.h int main(void) { Link_t *plink create_link(); if(plink NULL) { return -1; } insert_link_head(plink, 3); insert_link_head(plink, 1); insert_link_head(plink, 6); insert_link_tail(plink, 4); insert_link_tail(plink, 8); printf(原始链表); show_link(plink); change_link(plink,6,9); printf(修改6→9); show_link(plink); free_data_node(plink, 1); printf(删除元素1); show_link(plink); nixu_link(plink); printf(链表反转); show_link(plink); shengxu_link(plink); printf(升序排序); show_link(plink); free_link(plink); return 0; }五、编译运行内存检测编译gcc main001.c link001.c -o link_demo运行程序./link_demovalgrind检测内存泄漏写链表务必检测内存泄漏保证每一块malloc都有对应的freevalgrind --leak-checkfull ./link_demo运行输出结果原始链表6 1 3 4 8 修改6→99 1 3 4 8 删除元素19 3 4 8 链表反转8 4 3 9 升序排序3 4 8 9