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

发布时间：2026/10/12 2:08:11

新号别搞：数据结构-顺序表与链表
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/10/12 2:07:14 阅读更多 →
告别数据孤岛，PostgreSQL 在电力多维分析中的实战技巧

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

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

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

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

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

2026/10/4 13:46:41 阅读更多 →

最新新闻

AI语音智能体开发日记（三）解决小程序配网中的蓝牙命名与MAC地址获取问题

AI语音智能体开发日记（三）解决小程序配网中的蓝牙命名与MAC地址获取问题

相关链接： AI语音智能体开发日记（一）如何为“小智”服务器启用并调试 License 功能-CSDN博客 AI语音智能体开发日记（二）解决 Wi-Fi 配网小程序的兼容性问题-CSDN博客 AI语音智能体开发日记（三&#xff09…

2026/10/12 2:08:11 阅读更多 →
remark42 依赖解析：xdg-go/stringprep 的 RFC-3454 stringprep 与 RFC-4013 SASLprep 实现

remark42 依赖解析：xdg-go/stringprep 的 RFC-3454 stringprep 与 RFC-4013 SASLprep 实现

后端前端 【免费下载链接】remark42 comment engine 项目地址： https://gitcode.com/gh_mirrors/re/remark42 点击查看 免费下载 本文聚焦于 remark42 后端 vendor 目录中随依赖携带的第三方 Go 库 xdg-go/stringprep，完整解读其 README 所声明的核心能…

2026/10/12 2:08:10 阅读更多 →
深入解析 go-toml：在 Boulder ACME CA 项目中解析与操作 TOML 配置的 Go 库实战指南

深入解析 go-toml：在 Boulder ACME CA 项目中解析与操作 TOML 配置的 Go 库实战指南

网络安全后端微服务 【免费下载链接】boulder An ACME-based certificate authority, written in Go. 项目地址： https://gitcode.com/gh_mirrors/bo/boulder 点击查看 免费下载 导读 go-toml 是一个用 Go 语言编写的 TOML（Toms Obvious, Minimal Lan…

2026/10/12 2:08:10 阅读更多 →
ESP32隐藏射频通路：绕过协议栈直控无线收发的实测记录

ESP32隐藏射频通路：绕过协议栈直控无线收发的实测记录

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/12 2:08:10 阅读更多 →
AI语音智能体开发日记（四）在FreeRTOS中构建线程安全的UART2通信模块

AI语音智能体开发日记（四）在FreeRTOS中构建线程安全的UART2通信模块

相关链接： AI语音智能体开发日记（一）如何为“小智”服务器启用并调试 License 功能-CSDN博客 AI语音智能体开发日记（二）解决 Wi-Fi 配网小程序的兼容性问题-CSDN博客 AI语音智能体开发日记（三&#xff09…

2026/10/12 2:08:10 阅读更多 →
Elasticsearch Reindex 实战指南：从机制解析到性能调优避坑

Elasticsearch Reindex 实战指南：从机制解析到性能调优避坑

1. 为什么需要 reindex：五个让我踩过坑的典型场景先给没接触过的朋友一个基本认知：reindex 不是某个数据库独享的功能，主流存储引擎基本都有类似的能力。我最早接触是在 Elasticsearch 上，后面在消息队列、关系型数据库分库分表扩…

2026/10/12 2:07:10 阅读更多 →

日新闻

复古胶片颗粒感噪点合成器：Canvas ImageData 像素高斯杂色注入算法

复古胶片颗粒感噪点合成器：Canvas ImageData 像素高斯杂色注入算法

在数码相机、高清显示屏与现代矢量图形技术高度发达的今天，画面可以做到绝对的锐利、平滑与无瑕。然而，当一张秋日手账插画或拍立得照片过于“平整无瑕”时，往往会散发出一种冰冷生硬的“数码塑料感（Digital Plasticity&#xff0…

2026/10/12 0:00:59 阅读更多 →
活字印刷古籍线装排版：Canvas 竖排文字与栏线自适应算法

活字印刷古籍线装排版：Canvas 竖排文字与栏线自适应算法

在现代网页与移动端设计中，横排（Horizontal Layout）早已经成为了绝对的主流。然而，当我们翻开泛黄的线装古籍、宋版木刻诗集，或是欣赏一张茶道雅集的手写便签时，那种**自上而下纵向书写、自右向左逐列铺展&…

2026/10/12 0:00:59 阅读更多 →
周日晚间的“精神松绑减震器”：无压力情绪倾倒箱与温和轻声陪伴

周日晚间的“精神松绑减震器”：无压力情绪倾倒箱与温和轻声陪伴

每到周日的晚上八点到十点，很多人心里都会悄悄亮起一盏警示灯。 在心理学上，这种现象有一个专门的称谓——“周日夜晚焦虑症（Sunday Scaries）”。明天又是周一，闹钟又要重新在七点响彻卧房；脑海里仿佛有一个…

2026/10/12 0:00:59 阅读更多 →

周新闻

流感时间序列预测实战：ARIMA/LSTM全流程拆解与避坑指南

流感时间序列预测实战：ARIMA/LSTM全流程拆解与避坑指南

简介：基于 ARIMA、LSTM、Transformer 等模型的流感时间序列预测 Python 源码，面向计算机相关专业课程设计与期末大作业学生，以及项目实战学习者。内容覆盖预处理、平稳性检验、定阶、残差分析、多模型对比预测的完整时序建模流程，…

2026/10/12 0:16:30 阅读更多 →
影刀RPA新手教程：键盘模拟输入实战——输入文本与模拟按键的区别

影刀RPA新手教程：键盘模拟输入实战——输入文本与模拟按键的区别

影刀RPA新手教程：键盘模拟输入实战——输入文本与模拟按键的区别 做影刀RPA自动化，十个新手有八个栽在"往输入框里填东西"这件事上：要么填不进去，要么填了一半，要么直接把原来内容追加在后面。这背后的根因&…

2026/10/12 0:16:38 阅读更多 →
影刀RPA新手教程：阅文起点小说数据采集实战——书籍信息与章节内容

影刀RPA新手教程：阅文起点小说数据采集实战——书籍信息与章节内容

影刀RPA新手教程：阅文起点小说数据采集实战——书籍信息与章节内容 1. 认识影刀：什么场景该用RPA采小说数据 起点中文网的页面结构相对稳定——分类榜单、书籍详情、章节内容三块独立页面，跳转链路清晰。这种场景非常适合影刀自动化&#x…

2026/10/12 0:16:43 阅读更多 →

月新闻

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/11 10:45:37 阅读更多 →
Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/11 14:36:53 阅读更多 →
黑夜航拍船只数据集训练YOLOV5模型全流程解析

黑夜航拍船只数据集训练YOLOV5模型全流程解析

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/11 14:36:54 阅读更多 →