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

数据结构：线性表和顺序表

news 2026/5/25 3:13:18

一、线性表

线性表是一种逻辑结构，表示元素与元素之间的相邻关系，顺序表和链表是一种存储结构

第一个元素具有唯一后继，最后一个元素具有唯一前驱，中间的元素具有唯一的前驱和后继

二、顺序表

顺序表是线性表的顺序存储，用一段连续的内存空间依次存放数据元素

逻辑地址相邻的元素，内存地址也相邻

优点：支持随机访问；空间利用率高；尾插尾删效率高O(1)

缺点：扩容代价大；头插，按位置插，删除需要搬动数据

适用于：适用于需要大量随机访问，插入删除操作较少，就算需要这些操作也是在尾部进行

顺序表的分类：分为定容顺序表和可扩容顺序表

1. 顺序表的创建

1.1 定容顺序表

定长数组存储

typedef int Elementype; #define N 6 //定容顺序表结构体定义 typedef struct seqlist { //连续存储空间 int arr[N]; //有效元素长度 int length; //最大容量 int maxsize; }seqlist;

1.2 可扩容顺序表

动态开辟的数组存储

//可扩容顺序表 //类型重定义 typedef int Elementype; //初始格子数,初始化时malloc申请的格子数量 #define INTSIZE 10 //顺序表结构体定义 typedef struct seqlist { //内存连续的存储空间 Elementype* arr; //有效元素长度 int length; //最大容量 int maxsize; }seqlist;

2. 顺序表的初始化

//顺序表的初始化 void Init_seqlist(seqlist* plist) { //1.先安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.申请空间 plist->arr = (ElemType*)malloc(INTSIZE * sizeof(ElemType)); //判空 if (plist->arr == nullptr) exit(EXIT_FAILURE); //3.有效元素为0 plist->length = 0; //4.初始申请的空间个数为 plist->maxsize = INTSIZE; }

首先要对函数进行安全判断，DeBug版本用的是断言，release版本用的是if-else判空

然后用malloc在堆区购买一片连续的内存空间

一开始有效元素个数为0,容量为初始宏定义的个数

3. 顺序表扩容

//扩容 bool InCrease(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.购买新结点 ElemType* p = (ElemType*)realloc(plist->arr, plist->maxsize * 2 * sizeof(ElemType)); //3.判断空间是否申请成功，成功的话再将新申请的空间给arr if (p == NULL) return false; plist->arr = p; //更新容量 plist->maxsize = plist->maxsize * 2; return true; }

首先需要安全处理，然后使用新指针接收realloc购买2倍原来使用malloc和calloc购买的容量的大小（注意：这里不能是宏的二倍，因为如果是宏定义的二倍，会导致每一次扩容后的数量都是2*INTSIZE），判断空间申请是否成功，成功后再将地址传给顺序表，否则会导致顺序表丢失

4. 判满

//判满 bool IsFull(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.若有效元素个数==最大容量则已满 return plist->length == plist->maxsize; }

如果有效元素个数和申请的空间容量相等则已满，返回true

5. 判空

//判空 bool IsEmpty(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.若有效元素个数==0则为空 return plist->length == 0; }

如果有效元素个数==0则为空，返回true

6. 顺序表插入

6.1 头插

//顺序表头插 bool Insert_head(seqlist* plist,int val) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判满，若已满则扩容,如果扩容失败则退出 if (IsFull(plist)) { if (InCrease(plist) == false) return false; } //3.将原来顺序表中的元素从尾部开始挨个后移 memmove(plist->arr + 1, plist->arr, sizeof(ElemType) * plist->length); //4.再将新的元素插入arr[0] plist->arr[0] = val; //5.再更新有效元素个数 plist->length++; return true; }

首先安全处理

然后判满，如果已满扩容，如果扩容失败直接退出

使用memmove将元素从尾部挨个后移

【memmove在处理内存折叠时：如果目标地址高于源地址，从高地址往低地址复制，避免未复制就被覆盖的现象】

再将val插入空出来的地方

再更新有效元素个数

6.2 尾插

//顺序表的尾插 bool Insert_back(seqlist* plist, int val) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判满 if (IsFull(plist)) { if (InCrease(plist) == false) return false; } //3.尾部插入 plist->arr[plist->length] = val; //4.更新有效元素个数 plist->length++; return true; }

首先安全处理

然后判满，如果已满扩容，扩容失败则退出

然后直接在尾部插入val

插入完成后更新有效元素个数

6.3 按位置插

//按位置插 bool Insert_pos(seqlist* plist, int val, int pos) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判满 if (IsFull(plist)) { if (InCrease(plist) == false) return false; } //3.边界判断 if (pos > plist->length + 1 || pos < 0) return false; //4.在pos位置插入 //2 3 4 5 要在pos=3 下标2位置插入 7 //2 3 7 4 5 memmove(plist->arr + pos, plist->arr + pos - 1, sizeof(ElemType) * (plist->length - pos + 1)); plist->arr[pos - 1] = val; plist->length++; return true; }

首先进行安全判断

然后判满，如果已满扩容，扩容失败则退出

然后进行位置插入的边界值判断

然后将插入位置以及之后的元素，从最后一个元素开始，挨个往后移一位

将val插入

有效元素个数++

7. 顺序表删除

7.1 头删

//头删 bool delete_head(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.将所有元素从前往后挨个前移一位 memmove(plist->arr, plist->arr + 1, sizeof(ElemType) * (plist->length - 1)); //4.更新有效元素个数 plist->length--; return true; }

首先安全判断

然后判断表是否为空，如果表为空直接退出

如果表不空，将元素从头开始挨个前移

然后将有效元素个数减一

7.2 尾删

//尾删 bool delete_back(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.尾部删除，元素个数直接减一 plist->length--; return true; }

首先安全判断

然后判断表是否为空，如果表为空直接退出

如果表不空，然后将有效元素个数减一

7.3 按位置删

//按位置删 bool delete_pos(seqlist* plist, int pos) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.判断要删除的位置的界限 if (pos < 1 || pos > plist->length + 1)return false; //4.从前往后，元素挨个前移 //2 3 4 5 要删除第3位的 memmove(plist->arr + pos - 1, plist->arr + pos, sizeof(ElemType) * (plist->length - pos)); //有效元素个数减1 plist->length--; return true; }

首先安全判断

然后判断表是否为空，如果表为空直接退出

如果表不空，将pos位置之后的元素从前往后依次前移一位

有效元素个数减一

7.4 按值删（只删除这个值出现的第一次）

//按值删（只删除这个值出现的第一次） bool Del_val_first(seqlist* plist,int val) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.查找这个元素第一次出现的位置 int pos = search_seqlist(plist, val) + 1; //4.删除 memmove(plist->arr + pos - 1, plist->arr + pos, sizeof(ElemType) * (plist->length - pos)); plist->length--; return true; }

首先安全判断

然后判断表是否为空，如果表为空直接退出

如果表不空，查找要删除元素的下标(注意：此时返回的是下标，pos是当前元素的位置，所以需要+1，才是位置)，然后赋值给pos

将pos位置之后的元素从前往后依次前移一位

有效元素个数减一

7.4 按值删（删除这个值出现的所有）

//按值删（只删除这个值出现的所有次） bool Del_val_ALL(seqlist* plist, int val) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.将不是val的值存入一个从头开始存 int len = 0; for (int i = 0; i < plist->length; i++) { if (plist->arr[i] != val) plist->arr[len++] = plist->arr[i]; } //4.更新有效元素个数 plist->length = len; return true; }

首先安全判断

然后判断表是否为空，如果表为空直接退出

如果表不空，申请一个新的计数器，将不是val的值从头存入arr

有效元素个数更新为计数器的值

8. 查找有效元素是否存在

遍历整个顺序表，有效元素存在返回元素下标，不存在返回-1

int search_seqlist(seqlist* plist, int val) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.遍历顺序表，查找有效元素 for (int i = 0; i < plist->length; i++) { if (plist->arr[i] == val)return i; } return -1; }

9. 清空

将有效元素个数置为0即可

//清空 void clear(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } plist->length = 0; }

10. 销毁

释放在堆区申请的空间，然后将plist->arr=nullptr，目的是为了避免二次释放，然后将有效元素个数和容量置为0即可

//销毁 void Dstory(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.释放堆空间 free(plist->arr); plist->arr = nullptr; plist->length = 0; plist->maxsize = 0; }

11. 打印顺序表

//打印函数 void show(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.循环打印 printf("当前顺序表中的元素有："); for (int i = 0; i < plist->length; i++) { printf("%d ", plist->arr[i]); } printf("\n"); }

12. 测试

int main() { seqlist s; Init_seqlist(&s); printf("length==%d maxsize==%d\n", s.length, s.maxsize); Insert_head(&s, 2); show(&s); Insert_back(&s, 3); Insert_back(&s, 4); Insert_back(&s, 5); Insert_back(&s, 3); Insert_back(&s, 4); Insert_back(&s, 5); Insert_back(&s, 3); Insert_back(&s, 4); Insert_back(&s, 5); show(&s); Insert_pos(&s, 7, 1); show(&s); delete_head(&s); show(&s); delete_pos(&s, 4); show(&s); Del_val_first(&s, 4); show(&s); Del_val_ALL(&s, 3); show(&s); clear(&s); printf("%d\n",s.length); Dstory(&s); }
http://www.jsqmd.com/news/881039/

相关文章：

  • 2026槽式电缆桥架优质推荐指南：网格电缆桥架、铝合金走线架、不锈钢电缆桥架、北京电缆桥架厂家、托盘式电缆桥架选择指南 - 优质品牌商家
  • Claude Code 在安装vscode插件时遇到的问题。
  • 告别图形界面！5个CUPS命令行技巧，让你在Linux终端高效管理打印机
  • 2026微型舵机优质推荐榜：小型舵机/尾翼用方扁舵机/工业舵机/德晟舵机/数字舵机/无人机舵机/无刷舵机/最小的舵机/选择指南 - 优质品牌商家
  • 2026电工杯数学建模竞赛A题论文、代码、数据（改进）
  • # 网页设计学习感悟
  • 朝晖玻璃钢：玻璃钢保温水箱/玻璃钢消防水箱/玻璃钢罐化粪池/碳钢水箱/立式不锈钢水箱/组合式玻璃钢水箱/雨水一体化提升泵站/选择指南 - 优质品牌商家
  • 别再手动下载DLL了！用Windows自带工具SFC/SCANNOW一键修复kernel32.dll错误
  • 别再让系统‘无家可归’：给已用满空间的Win10 SSD无损创建EFI引导分区指南
  • 2026年紫外线杀菌除藻灯优质厂家深度解析：聚焦技术、产能与服务三角 - 2026年企业推荐榜
  • Titanic数据集分析避坑指南：新手常犯的3个错误及如何修正
  • ubuntu2026.04部署k8s1.36版本的傻瓜式教程(注:运行时为docker,网络插件为calico)
  • 一文讲清楚规则、Skill、MCP
  • 2026泛塞封密封圈优质品牌推荐：聚四氟乙烯密封圈/铁氟龙密封圈/高分子材料密封圈/O型圈/PEEK密封圈/PU密封圈/选择指南 - 优质品牌商家
  • 别再让Ubuntu卡成PPT！手把手教你用swapfile把交换空间从1G扩容到64G（附权限修复）
  • 【iOS】底层原理：理解dyld
  • 告别虚拟机！手把手教你用U盘给新电脑装Win11+统信UOS 1060双系统（保姆级分区教程）
  • Win10开机WiFi列表全空？先别慌，按这个‘服务状态排查流程图’走一遍
  • 2026靠谱仪器推荐：Trim200离子束刻蚀机、Essent Optics分光光度计、LINZA分光光度计、LensCheck MTF传函仪选择指南 - 优质品牌商家
  • 告别下载量低迷，5套实操方法打通用户增长
  • MacBook新手福音：用Final Cut Pro 10.6.5搞定你的第一门视频课（附保姆级设置与导出指南）
  • 2026年知名的大豆定量包装机/饲料定量包装机厂家哪家好 - 行业平台推荐
  • 从零开始手把手教你用Python和XFLR5估算小型固定翼无人机的升力系数（附代码）
  • 2026北京搬家公司优质推荐指南：北京公司搬家公司/北京收纳整理公司/北京日式搬家公司/北京本地搬家/北京企业搬家/选择指南 - 优质品牌商家
  • 【程序源代码】答题微信小程序（含源码）
  • Cocos Creator 3.x 实战：用 BoxCollider 和 CircleCollider 快速搞定一个2D平台跳跃游戏的碰撞检测
  • 避坑指南：在openEuler 22.03上配置vsftpd虚拟用户，解决gdbmtool替代db_load的认证问题
  • 2026智能人工气候室应用白皮书：低温型人工气候室/保鲜库/催芽室/全天候智能人工气候室/养虫室/冷冻库/医药冷库/选择指南 - 优质品牌商家
  • 别再为立体匹配发愁了！手把手教你用Fusiello法搞定双目相机极线校正（附Python代码）
  • 2026年黄金回收商家深度解析：宝奢科技等头部企业如何选择 - 2026年企业推荐榜