当前位置： 首页 > news >正文

数据结构-单链表（C语言简单实现）

news 2025/7/5 7:53:08

简介

以顺序结构进行数据存储时，它的特点就是可以用一组任意的存储单元存储数据元素，这组存储单元可以是连续的，也可以是不连续的，这些数据可以存在内存未被占用的任意位置。它也是有缺点的，就是在插入和删除时需要移动大量的元素，需要耗费一点时间。

以下是它的一个示意图

单链表

想要创建这样的数据结构，首先需要使用结构体先定义一个节点:

typedef struct node
{int data;  // 数据struct node *next;  // 指向下一个节点的地址
}node_t;

然后需要使用结构体定义单链表:

typedef struct list
{struct node *head;  // 头部struct node *tail;  // 尾部
}list_t;

相关函数

  • 首先需要定义一个静态函数用于创建节点
static node_t *create_node(int data)
{node_t *pnew = malloc(sizeof(node_t));  // 分配内存空间pnew->data  = data;  // 分配数据pnew->next = NULL;  // 默认指向空return pnew;  // 返回地址
}
  • 初始化函数

图片.png

void list_init(list_t *plist)
{plist->head = create_node(0);  // 为头部创建一个节点plist->tail = create_node(0);  // 为尾部创建一个节点plist->head->next = plist->tail;  // 头部的next指向尾部plist->tail->next = NULL;  // 尾部的next指向NULL
}
  • 释放单链表的函数

图片.png

void list_deinit(list_t *plist)
{node_t *pnode = plist->head;  // 将pnode指向头部// 当pnode非空时，进行循环，说明还有数据while(pnode){node_t *ptmp = pnode->next;  // 备份pnode的nextfree(pnode);  // 释放pnodepnode = ptmp;  // 将之前pnode的next指向现在的pnode}
}
  • 遍历单链表

图片.png

void list_travel(list_t *plist)
{// 遍历: 首先将pnode指向head,直到pnode指向tail结束，pnode每次往后移一位for(node_t *pnode = plist->head; pnode != pnode->tail; pnode = pnode->next){// 三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;if(pmid != pnode->tail)printf("%d ", pmid->data);}printf("\n");
}
  • 按照顺序添加数据到单链表中

图片.png

void list_add(list_t *plist, int data)
{// 1. 创建一个新的节点node_t *pnew = create_node(data);// 2. 遍历链表for(node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 2.1 三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 2.2 当找到比data大的数据，就插入到它后面，或者找到最后都没找到比它大的，就插到最后if(pmid->data > pnew->data || pmid == plist->tail){pfirst->next = pnew;pnew->next = pmid;break;}}
}
  • 前插函数(将数据插到最前面)

图片.png

void list_add_first(list_t *plist, int data)
{// 1. 创建一个新的节点node_t *pnew = create_node(data);// 2. 备份头部的nextnode_t *ptmp = plist->head->next;// 3. 将头部的next指向新节点plist->head->next = pnew;// 4. 将新节点的next指向之前头部指向nextpnew->next = ptmp;
}
  • 后插函数(将数据插到最后面)

图片.png

void list_add_last(list_t *plist, int data)
{// 1. 创建一个新的节点node_t *pnew = create_node(data);// 2. 遍历链表for(node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 2.1 三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 2.2 当pmid执行plist->tail时，插入if(pmid == plist->tail){pfirst->next = pnew;pnew->next = pmid;break;}}
}
  • 删除指定数据所在的节点

图片.png

void list_del(list_t *plist, int data)
{// 1. 遍历链表for(node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 1.1 三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 1.2 当找到数据相等的，并且此数据不是尾节点，因为尾节点是初始化定义的if(data == pmid->data && pmid != plist->tail){pfirst->next = plast;free(pmid);  // 此时pmid就是要删除的那个节点break;}}
}

示例代码

创建三个文件: list.c、list.h、main.c，实现上面的相关函数

  • list.c
#include "list.h"// 定义分配节点内存函数
static node_t *create_node(int data)
{node_t *pnew = malloc(sizeof(node_t));pnew->data = data;pnew->next = NULL;return pnew;
}// 初始化
void list_init(list_t *plist)
{// 1. 给首尾分配内存plist->head = create_node(0);plist->tail = create_node(0);// 2. 头指向尾plist->head->next = plist->tail;// 3. 尾指向空plist->tail->next = NULL;
}// 释放
void list_deinit(list_t *plist)
{// 1. 取到单链表的头部node_t *pnode = plist->head;// 2. 当头部不为空的时候，说明还有数据，继续循环while (pnode){// 2.1 备份pnode->nextnode_t *ptmp = pnode->next;// 2.2 释放pnodefree(pnode);// 2.3 重新指定pnode是ptmppnode = ptmp;}
}// 遍历数据单链表
void list_travel(list_t *plist)
{for (node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 创建三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 判断pmid是有效节点if (pmid != plist->tail){printf("%d ", pmid->data);}}printf("\n");
}// 按顺序添加数据到单链表中
void list_add(list_t *plist, int data)
{// 1. 创建新的节点node_t *pnew = create_node(data);// 2. 遍历单链表for (node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 2.1 创建三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 2.2 判断当找到pmid的数据大于等于data或者找到最后都没找到比data大的，就插到最后if (pmid->data >= pnew->data || pmid == plist->tail){// 2.2.1 放在pmid后面,pfirst的前面pfirst->next = pnew;pnew->next = pmid;break;}}
}// 前插函数
void list_add_first(list_t *plist, int data)
{// 1. 创建新的节点node_t *pnew = create_node(data);// 2. 备份头部的nextnode_t *ptmp = plist->head->next;// 3. 将头部的next指向新的节点plist->head->next = pnew;// 4. 将新的节点next指向之前头部的nextpnew->next = ptmp;
}// 后插函数
void list_add_last(list_t *plist, int data)
{// 1. 创建新的节点node_t *pnew = create_node(data);// 2. 遍历节点，找到tail前面的节点for (node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 2.1 创建三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 2.2 当pmid==tail时，说明pfirst是tail前面的节点if (pmid == plist->tail){// 2.2.1 将pfirst的next指向pnewpfirst->next = pnew;// 2.2.2 将pnew的next执行tail(pmid)pnew->next = pmid;break;}}
}// 删除指定数字所在所在的节点
void list_del(list_t *plist, int data)
{// 1. 遍历单链表for (node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 1.1 三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 1.2 当找到数据相等的，并且此数据不是尾节点，因为尾节点是初始化定义的if (data == pmid->data && pmid != plist->tail){// 1.2.1 将pfirst的next指向plastpfirst->next = plast;// 1.2.2 释放pmidfree(pmid);break;}}
}
  • list.h声明单链表的相关函数和定义节点和单链表
#ifndef __LIST_H
#define __LIST_H#include <stdio.h>
#include <stdlib.h>// 定义节点
typedef struct node
{int data;struct node *next;
} node_t;// 声明单链表的结构体
typedef struct list
{node_t *head; // 保存头节点的地址node_t *tail; // 保存尾节点的地址
} list_t;extern void list_init(list_t *plist);
extern void list_deinit(list_t *plist);
extern void list_travel(list_t *plist);
extern void list_add(list_t *plist, int data);
extern void list_add_first(list_t *plist, int data);
extern void list_add_last(list_t *plist, int data);
extern void list_del(list_t *plist, int data);#endif
  • main.c主函数使用单链表
#include "list.h"int main(void)
{// 1. 创建单链表list_t list;// 2. 初始化单链表list_init(&list);// 3. 插入三个数据10 30 20printf("插入三个数据10 30 20,结果应该排好顺序的: ");list_add(&list, 10);list_add(&list, 30);list_add(&list, 20);// 4. 循环遍历输出单链表list_travel(&list);// 5. 在头部插入一个15printf("在头部插入15: ");list_add_first(&list, 15);// 6.遍历输出单链表list_travel(&list);// 7. 在尾部插入一个1printf("在尾部插入一个1: ");list_add_last(&list, 1);// 8. 遍历输出list_travel(&list);// 9. 删除一个20printf("删除一个20: ");list_del(&list, 20);// 10. 遍历输出list_travel(&list);// 11. 释放整个链表list_deinit(&list);return 0;
}
http://www.lryc.cn/news/130326.html

相关文章：

  • .netcore grpc身份验证和授权
  • 分布式 - 服务器Nginx：一小时入门系列之负载均衡
  • Linux学习之基本指令二
  • 神经网络基础-神经网络补充概念-41-梯度的数值逼近
  • tornado在模板中遍历二维数组
  • 前端-初始化Vue3+TypeScript
  • 龙蜥社区安全联盟（OASA）正式成立，启明星辰、绿盟、360 等 23 家厂商重磅加入
  • Flask-SQLAlchemy
  • 大数据bug-sqoop（二：sqoop同步mysql数据到hive进行字段限制。）
  • Windows小记
  • centos安装elasticsearch7.9
  • 221、仿真-基于51单片机的智能啤酒发酵罐多点温度压力水位排水加水检测报警系统设计(程序+Proteus仿真+配套资料等)
  • C语言好题解析（三）
  • OpenCV之remap的使用
  • leetcode 377. 组合总和 Ⅳ
  • C++笔记之花括号和圆括号初始化区别，列表初始化和初始化列表区别
  • git报错Add correct host key
  • Kvm配置ovs网桥
  • AraNet：面向阿拉伯社交媒体的新深度学习工具包
  • P13-CNN学习1.3-ResNet(神之一手~)
  • 【C++】set/multiset容器
  • docker拉取镜像时报错Error response from daemon: Head ““no basic auth credentials
  • Redis消息传递：发布订阅模式详解
  • 最强自动化测试框架Playwright（36）- 句柄
  • 推荐一个绘图平台（可替代Visio）
  • 【探索Linux】—— 强大的命令行工具 P.6（调试器-gdb、项目自动化构建工具-make/Makefile）
  • echarts-convert.js使用
  • 数据结构之队列详解（包含例题）
  • Prometheus的搭建与使用
  • 实战指南，SpringBoot + Mybatis 如何对接多数据源