新号别搞：数据结构-顺序表与链表

发布时间：2026/7/25 2:58:35

新号别搞：数据结构-顺序表与链表
1. 线性表1.1 线性表线性表(命名L)是相同类型的n个数据元素的有限序列。第 i 个数据元素称i为数据元素a在线性表中的位序表头无前驱 表尾无后继其它都有前驱后继顺序存储实现是顺序表链式存储实是链表顺序存储逻辑上相邻的数据元素存放在⼀段连续物理存储单元中数据元素之间的逻辑关系由物理存储关系体现链式存储逻辑上相邻的数据元素存储在任意的⼀组物理存储单元中数据元素之间的逻辑关系⽤指针来表⽰1.2类型 引用别名 引用变量给已存在变量取了⼀个别名编译器不会为引用变量开辟内存空间引用在C里面与取地址符号相同 引用在定义时必须初始化一个变量可以有多个引用引用一旦引用一个实体再不能引用其他实体2、静态顺序表2.1 结构定义typedef int SqDataType; typedef struct SequenceList // SequenceList 可以简化 { SqDataType arr[Sq_MAX_SIZE]; // 存储数据的静态数组 int size; // 记录顺序表中已经存⼊的数据个数 }SqList;静态顺序表结构定义2.2 了解静态顺序表用固定大小的静态数组来存储数据优点是实现简单缺点是适⽤场景局限#define Sq_MAX_SIZE 10 顺序表的最⼤存储的数据个数3、动态顺序表3.1 结构定义typedef int SqDataType; // 动态顺序表结构定义 typedef struct SequenceList //SequenceList 可以简化 { SqDataType* arr; // 存储数据的动态数组的指针 int size; // 记录顺序表中已经存⼊的数据个数 int capacity; // 动态数组的容量空间的⼤⼩ }SqList;动态顺序表结构定义3.2了解动态顺序表⽤⼀个堆上动态申请的数组来存储数据空间不够了 扩容处理3.3 动态顺序表实现(简)3.3.1 接口函数定义SqList.h头文件 #includestdio.h #includestdlib.h #includestdbool.h #includeassert.htypedefintSqDataType;重命名 数据元素类型typedef struct{|SqDataType* arr;//存储数据的动态数组的指针|intsize;//记录顺序表中已经存⼊的数据个数|intcapacity;//动态数组的容量空间的⼤⼩} SqList;初始化顺序表void SqListInit(SqList* ps); //书上 void SqListInit (SqList s);销毁顺序表void SqListDestroy(SqList* ps);插入数据插入i位 (头插 尾插)void SqListInsert(SqList* ps, int i, SqDataType x); //i位 void SqListPushFront(SqList* ps, SqDataType x); //头插 void SqListPushBack(SqList* ps, SqDataType x); //尾插删除数据 删除中间 头删 尾删SqDataType SqListDelete(SqList* ps, int i); //i位 void SqListPopFront(SqList* ps); //头删 void SqListPopBack(SqList* ps); //尾删返回i下标的值 第一个 值x 的下标不存在-1SqDataType GetElem(SqList* ps, int i); //i下标的值 int LocateElem(SqList* ps, SqDataType x); //第一个 值x 的下标检查顺序表为空否空作true 不空 false 获取有效元素个数 打印bool EmptysqList(SqList* ps); //顺序表空否 int SqListSize(SqList* ps); //获取有效元素个数 void SqListPrint(SqList* ps); //打印3.3.2 实现 SqList.cpp#include SqList.h初始化接口函数void SqListInit(SqList* ps) { assert(ps); ps-arr (SqDataType*)malloc(sizeof(SqDataType) * 4); if (ps-arr NULL) { perror(SqListInit: malloc failed); return; } ps-size 0; ps-capacity 4; }销毁接口函数void SqListDestroy(SqList* ps) { assert(ps); if (ps-arr) { free(ps-arr); ps-arr NULL; ps-capacity 0; ps-size 0; } }插入接口函数头插尾插void SqListInsert(SqList* ps, int i, SqDataType x) { assert(ps); assert(i 0 i ps-size); if (ps-size ps-capacity) { SqDataType* tmp (SqDataType*)realloc(ps-arr, sizeof(SqDataType) * ps-capacity * 2); if (tmp NULL) { perror(malloc failed);return; } ps-arr tmp; ps-capacity * 2; } // j为下标 i 为位序 for (int j ps-size - 1; j i; j--) { ps-arr[j 1] ps-arr[j]; } ps-arr[i] x; ps-size; } //头插 void SqListPushFront(SqList* ps, SqDataType x) { SqListInsert(ps, 0, x); } //尾插 void SqListPushBack(SqList* ps, SqDataType x) { SqListInsert(ps, ps-size, x); }删除接口函数头删尾删SqDataType SqListDelete(SqList* ps, int i) { assert(ps); assert(i 0 i ps-size); SqDataType x ps-arr[i]; for (int j i 1; j ps-size; j) { ps-arr[j - 1] ps-arr[j]; } ps-size--; return x; } //头删 void SqListPopFront(SqList* ps) { SqListDelete(ps, 0); } //尾删 void SqListPopBack(SqList* ps) { SqListDelete(ps, ps-size-1); }返回i下标的值 第一个 值x 的下标不存在-1//下标i的值 SqDataType GetElem(SqList* ps, int i) { assert(ps); assert(i 0 i ps-size); return ps-arr[i]; } //值i的下标 int LocateElem(SqList* ps, SqDataType x) { assert(ps); for (int i 0; i ps-size; i) { if(ps-arr[i] x) return i; } return -1; }检查顺序表为空否空作true 不空 false 获取有效元素个数 打印顺序表元素//检查顺序表为空否空作true 不空 false bool EmptysqList(SqList* ps) { assert(ps); return ps-size 0; } //获取有效元素个数 int SqListSize(SqList* ps) { assert(ps); return ps-size; } //打印顺序表元素 void SqListPrint(SqList* ps) { assert(ps); for (int i 0; i ps-size; i) { printf(%d , ps-arr[i]); }printf(\n); }3.3.3 测试text.cpp#include SqList.hvoid TestSqList1()(初始化)SqList sl; //SqListInit(sl); //cpp SqListInit(sl);(插入测试// 尾插 SqListInsert(sl, 0, 1); SqListInsert(sl, 1, 2); SqListInsert(sl, 2, 3); SqListInsert(sl, 3, 4); SqListInsert(sl, 4, 5); SqListInsert(sl, 5, 6); SqListPrint(sl); // 头插 SqListInsert(sl, 0, 100); SqListPrint(sl); // 中间插入 SqListInsert(sl, 1, 200); SqListPrint(sl);删除测试//删除顺序表第1个位置上的元素 printf(顺序表中有效元素个数为%d \n, SqListSize(sl)); SqListPrint(sl); // 删除末尾的数据 printf(删除的元素是:%d \n, SqListDelete(sl, SqListSize(sl) - 1)); SqListPrint(sl); // 删除中间的数据 printf(删除的元素是:%d \n, SqListDelete(sl, 2)); SqListPrint(sl);返回测试//i 下标的元素 printf(顺序表中第%d个元素是%d\n, 1, GetElem(sl, 1)); SqListPrint(sl); // x值的下标 printf(40 的下标是%d\n, LocateElem(sl, 40)); SqListPrint(sl); SqListDestroy(sl);4.链表4.1 优势及相关概念可以按需申请空间不再需要扩容插入和删除效率高结点存储数据和下一个结点指针头指针: 指向第⼀个结点的指针;尾结点的指针指向空带头结点不带头结点两种结构。头结点⼀个哨兵位,不存有效数据4.2 单链表实现4.2.1 接口函数实现(List.h)#includestdio.h #includestdlib.h#includestdbool.h #includeassert.h头文件typedef int LDataType;重命名类型创建新结点LNode* BuyListNode(int data);初始化LNode* ListInit(); //书上 void ListInit(LinkList L);i位置插入元素x 头插 尾插void ListInsert(LNode* L, int i, LDataType x); void ListPushFront(LNode* L, LDataType x); void ListPushBack(LNode* L, LDataType x);删除i结点用 x 带出结点值 头删 尾删LDataType ListDelete(LNode* L, int i); LDataType ListPopFront(LNode* L); LDataType ListPopBack(LNode* L);判断链表空否bool ListEmpty(LNode* L);打印void ListPrint(LNode* L); //(LinkList* L)获取有效元素个数int ListSize(LNode* L);返回第一个数据 x结点 的地址 反之回NULLLNode* ListLocateElem(LNode* L, LDataType x);返回下标i的结点LNode* ListGetElem(LNode* L, int i);销毁void ListDestroy(LNode* L);4.2.2 实现List.c包含头文件#includeList.h创建新结点LNode* BuyListNode(int data) { LNode* newNode (LNode*)malloc(sizeof(LNode)); if (newNode NULL) { perror(malloc fail); exit(-1); } newNode-data data; newNode-next NULL; return newNode; }初始化LNode* ListInit() { LNode* node BuyListNode(-1); return node; }打印链表void ListPrint(LNode* L) //(LinkList* L) { assert(L); printf(头结点-); LNode* cur L-next; while (cur) { printf(%d-, cur-data); cur cur-next; //后移指针 } printf(NULL\n); }判空bool ListEmpty(LNode* L) { return L-next NULL; }有效元素个数int ListSize(LNode* L) { assert(L); int size 0; LNode* cur L-next; while (cur) { size; cur cur-next; } return size; }i位置插入void ListInsert(LNode* L, int i, LDataType x) { assert(L i 0);//断言头结点非空插入位置非负 int j -1;//从头结点下标 -1开始 LNode* i_1Node L;//i_1Node 用于定位第 i-1 个结点初始指向头结点 while (i_1Node ! NULL j i - 1) { j; i_1Node i_1Node-next; } assert(i_1Node);//如果循环后 i_1Node 为 NULL说明链表长度不够i 越界 LNode* newNode BuyListNode(x); //先将新结点的 next 指向前驱的 next即原第 i 个结点地址可能为 NULL newNode-next i_1Node-next; //再将前驱的 next 指向新结点完成插入 i_1Node-next newNode; }【头插void ListPushFront(LNode* L, LDataType x) { ListInsert(L, 0, x);//相当于在 0 位置插入即头结点的后面 }尾插void ListPushBack(LNode* L, LDataType x) { assert(L); LNode* cur L; while (cur-next) { cur cur-next; } LNode* newNode BuyListNode(x); //将尾结点的 next 指向新结点新结点自动成为新尾 cur-next newNode; }删除结点返回值LDataType ListDelete(LNode* L, int i) { assert(i 0); int j -1; LNode* i_1Node L; while (i_1Node ! NULL j i - 1) { j; i_1Node i_1Node-next; } //检查前驱和前驱的 next 是否存在任一为空说明 i 非法 assert(i_1Node ! NULL i_1Node-next ! NULL); //iNode 指向待删除的第 i 个结点 LNode* iNode i_1Node-next; //将前驱的 next 指向被删结点的下一个结点从链表中移除 iNode i_1Node-next iNode-next; //取出被删数据释放结点内存 LDataType x iNode-data; free(iNode); return x; }头删LDataType ListPopFront(LNode* L) { return ListDelete(L, 0); }尾删LDataType ListPopBack(LNode* L) { assert(L L-next); LNode* cur L; //cur-next 存在 — 当前有后继 //cur-next-next 存在 — 后继的后继存在说明 cur 还不是倒数第二个 //循环退出时cur-next 为尾结点cur 为倒数第二个结点或头结点 while (cur-next cur-next-next) { cur cur-next; } LNode* del cur-next; LDataType x del-data; free(del); cur-next NULL; return x; }按值查找LNode* ListLocateElem(LNode* L, LDataType x) { assert(L); LNode* cur L-next; while (cur) { if (cur-data x) return cur; cur cur-next; } return NULL; }按位查找LNode* ListGetElem(LNode* L, int i) { assert(L i 0); int j 0; LNode* iNode L-next; //遍历直到 iNode 越界或 j 到达 i while (iNode ! NULL j i) { j; iNode iNode-next; } //如果 iNode 为 NULL说明 i 超出链表长度返回 NULL //否则返回第 i 个结点地址 return iNode; }销毁void ListDestroy(LNode* L) { LNode* cur L-next; while (cur) { LNode* next cur-next; //先保存下一个结点地址否则释放后丢失 free(cur); cur next; } free(L); }4.2.3 测试test.c头文件#include List.h手动链一个CreateListLNode* CreateList() { // 创建头结点 LNode* L BuyListNode(-1); // 先快速构造5个结点⽅便测试 LNode* node1 BuyListNode(1); LNode* node2 BuyListNode(2); LNode* node3 BuyListNode(3); LNode* node4 BuyListNode(4); LNode* node5 BuyListNode(5); // 然后通过⼿动的⽅式将结点链接起来 L-next node1; node1-next node2; node2-next node3; node3-next node4; node4-next node5; return L; }TestList1来测试void TestList1() { LNode* LT NULL; LT CreateList(); // 测试打印⽅法和获取结点个数⽅法 printf(链表LT中总共有%d个结点\n, ListSize(LT)); ListPrint(LT); // 测试按值获取 printf(链表中值%d结点为%p\n, 1, ListLocateElem(LT, 1)); // 测试按下标获取 printf(链表中下标%d的结点的值为%d\n, 0, ListGetElem(LT, 0)-data); ListInsert(LT, 5, 6); // 尾插 ListPrint(LT); ListInsert(LT, 2, 30); // 中间插 ListPrint(LT); ListInsert(LT, 0, 0); // 头插 ListPrint(LT); ListDelete(LT, 0); // 头删 ListPrint(LT); ListDelete(LT, 2); // 中间删 ListPrint(LT); ListDelete(LT, 5); // 尾删 ListPrint(LT); // 销毁链表 ListDestroy(LT); }完~走过路过不要错过有错请指出谢谢

相关新闻

AMD锐龙调试工具完全指南：30分钟从入门到精通

AMD锐龙调试工具完全指南：30分钟从入门到精通

AMD锐龙调试工具完全指南：30分钟从入门到精通 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址: https://gitcode.co…

2026/7/25 2:58:35 阅读更多 →
告别数据孤岛，PostgreSQL 在电力多维分析中的实战技巧

告别数据孤岛，PostgreSQL 在电力多维分析中的实战技巧

文章目录每日一句正能量突破查询瓶颈：电力场景下的多维数据结构设计复杂趋势检索与 SQL 优化实战索引策略与时序处理差异思考每日一句正能量 时间不是一堵原谅的墙，而是一条允许所有人慢慢走远的河。 时间并不能自动带来原谅。原谅需要主动的释怀&#x…

2026/7/25 2:58:35 阅读更多 →
Docker从手工安装到自动化构建：完整指南与最佳实践

Docker从手工安装到自动化构建：完整指南与最佳实践

在容器化技术普及的今天，Docker已经成为开发者和运维人员的必备技能。但很多初学者在从手工安装到自动化构建的过渡阶段会遇到各种问题：环境配置复杂、镜像构建效率低、多服务管理困难等。本文将系统讲解Docker从基础安装到高级自动化构建的完整流程&…

2026/7/25 2:58:35 阅读更多 →

最新新闻

AI Agent中Token优化策略与成本控制实战

AI Agent中Token优化策略与成本控制实战

1. 理解Token在AI Agent中的核心作用在构建AI驱动的智能体（Agent）系统时，输入输出tokens的处理能力直接决定了系统的性能和成本效益。Token是大型语言模型处理文本的基本单位，它不同于简单的字符或单词切割，而是基于语…

2026/7/25 3:11:39 阅读更多 →
2026丹东女人街女装店靠谱店铺深度测评性价比高避坑推荐

2026丹东女人街女装店靠谱店铺深度测评性价比高避坑推荐

买国风女装怕踩坑？女人街这家店值得看 想穿出东方韵味，却总担心面料质感差、版型显胖、搭配困难……这些问题让不少国风爱好者犹豫。其实，选对靠谱实体店才是关键。在丹东女人街，缤缤服饰女装店的香云纱新中式国风女装系列&#x…

2026/7/25 3:11:39 阅读更多 →
2026丹东元宝区女人街优质女装店性价比高不踩雷推荐

2026丹东元宝区女人街优质女装店性价比高不踩雷推荐

女人街买女装，性价比是关键痛点 逛女人街买女装，不少姐妹都踩过坑：款式看着不错，买回家质感差；价格虚高，穿两次就过时；国风单品看着美，搭配起来却像“戏服”。其实，选女装…

2026/7/25 3:11:39 阅读更多 →
OpenHarmony 网格、列表进阶与懒加载实战开发

OpenHarmony 网格、列表进阶与懒加载实战开发

承接前两篇 ArkUI 组件内容，本文聚焦Grid 网格布局、List 列表高阶用法、组件懒加载、瀑布流等高频实用能力，结合完整案例讲解特性、适配方案与性能优化，适合页面布局进阶开发。一、概述在应用开发中，图文宫格、商品陈列、相册、分…

2026/7/25 3:11:39 阅读更多 →
OpenHarmony 进阶 UI 组件、自定义组件实战与交互开发

OpenHarmony 进阶 UI 组件、自定义组件实战与交互开发

一、引言在上一篇文章中，我们学习了 OpenHarmony ArkUI 基础组件与基础布局，能够完成常规页面搭建。在实际项目开发中，还会用到选择器、弹窗、进度条、开关等进阶交互组件；同时页面中大量重复的 UI 模块，需要通过自定义…

2026/7/25 3:11:39 阅读更多 →
B端拓客中法人号码核验的精准解决方案

B端拓客中法人号码核验的精准解决方案

1. B端拓客中的法人号码核验痛点企业服务领域（B端）的销售团队都面临一个经典难题：如何从海量企业信息中筛选出有效的法人联系方式？这个问题看似简单，实际操作中却存在诸多陷阱。我服务过三家不同规模的ToB企业&#xf…

2026/7/25 3:10:39 阅读更多 →

日新闻

突破文档下载限制：kill-doc让你看到的都能保存

突破文档下载限制：kill-doc让你看到的都能保存

突破文档下载限制：kill-doc让你看到的都能保存 【免费下载链接】kill-doc 看到经常有小伙伴们需要下载一些免费文档，但是相关网站浏览体验不好各种广告，各种登录验证，需要很多步骤才能下载文档，该脚本就是为了解决您的…

2026/7/25 0:00:35 阅读更多 →
C++ string类模拟实现：从深拷贝到内存管理的完整指南

C++ string类模拟实现：从深拷贝到内存管理的完整指南

1. 项目概述：为什么我们要“手撕”string类？在C的学习道路上，尤其是从C语言过渡到C的“初阶”阶段，string类绝对是一个绕不开的核心。标准库里的std::string用起来太方便了，、find、substr，几个操作符和函数…

2026/7/25 0:00:35 阅读更多 →
三角洲寻宝鼠工具：高效文件搜索与资源管理实战指南

三角洲寻宝鼠工具：高效文件搜索与资源管理实战指南

1. 先搞清楚“三角洲寻宝鼠”到底是什么工具从名称来看，“三角洲寻宝鼠”更像是一个资源查找或文件检索类工具，而不是游戏或娱乐软件。这类工具的核心价值在于帮助用户快速定位特定资源，比如文档、图片、压缩包或特定格式的文件。如果你经常需…

2026/7/25 0:00:35 阅读更多 →

周新闻

Go语言静态资源打包方案对比与实践指南

Go语言静态资源打包方案对比与实践指南

1. 项目背景与核心需求在Go语言开发中，我们经常需要处理静态资源文件的打包问题。无论是Web应用的模板文件、前端资源，还是配置文件、证书等，都需要随程序一起分发。传统做法是将这些文件与编译后的二进制文件放在同一目录下，但这…

2026/7/24 3:59:20 阅读更多 →
Go语言实现高性能LDAP认证服务的架构与实践

Go语言实现高性能LDAP认证服务的架构与实践

1. 项目背景与核心价值LDAP（轻量级目录访问协议）作为企业级身份认证的黄金标准，已经服务了超过80%的财富500强公司。我在金融科技领域实施统一认证体系时，发现传统Java方案存在启动慢、内存占用高等痛点。而Go语言凭借其协程并发模…

2026/7/24 1:23:39 阅读更多 →
【AI面试官实战指南】：用ChatGPT模拟10类高频技术岗面试，3天提升应答精准度92%

【AI面试官实战指南】：用ChatGPT模拟10类高频技术岗面试，3天提升应答精准度92%

更多请点击： https://intelliparadigm.com 第一章：AI面试官实战指南的核心价值与适用场景 AI面试官并非替代人类HR的“黑箱工具”，而是以可解释、可审计、可迭代的方式，赋能招聘全链路的关键基础设施。其核心价值在于将主观经验沉…

2026/7/24 18:52:18 阅读更多 →

月新闻