【数据结构】——线性表（顺序表）——内有代码详解

目录

 一、引言

二、线性表

2.1 定义

2.2 特点 

三、顺序表

3.1 顺序表的概念

3.2 顺序表的特点 

 3.3 顺序表的定义

3.3.1 静态定义

3.3.2 动态定义

3.4 顺序表的初始化

 3.4.1 静态初始化

3.4.2 动态初始化 

 

3.5 顺序表的销毁

3.6 顺序表元素的打印

3.7 顺序表的插入

3.7.1 检查空间，如果满了，进行增容

3.7.2 尾插

3.7.3 头插

3.7.4 中间插入

3.8 顺序表的删除

3.8.1 尾删

检查

1 温柔判断

2 暴力判断 

 代码：

3.8.2 头删

3.8.3 中间删除

3.9 顺序表的查询

四、总结

 一、引言

我们学完了算法和算法效率的度量，接下来我们将进入线性表的学习了，也是数据结构较为重要的一部分，

二、线性表

2.1 定义

线性表（linear list）：是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储。

2.2 特点 

  • 表中元素的个数有限。
  • 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
  • 表中元素都是数据元素，每个元素都是单个元素。
  • 表中元素的数据类型都相同，这意味着每个元素占有的相同大小的存储空间。
  • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

*线性表是一种逻辑结构 ，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层次的概念，因此不可以混淆哦。

三、顺序表

下面我们就有进入线性表的顺序表示——顺序表的学习了。

3.1 顺序表的概念

顺序表是一种线性表的存储结构，它通过一组地址连续的存储单元来表示线性表的元素集合。顺序表中的元素按照逻辑顺序依次存放在存储单元中，可以通过元素的下标来访问和操作元素。顺序表可以是静态分配的，也可以是动态分配的。

3.2 顺序表的特点 

顺序表的优点是元素的访问速度快，可以随机访问任意位置的元素；缺点是插入和删除操作需要移动大量的元素，时间复杂度为O(n)。因此，适合于元素的频繁访问和较少的插入删除操作的场景。

 3.3 顺序表的定义

3.3.1 静态定义

假设现线性表的元素类型为SLDataType，数组最大长度为N

顺序表的静态定义：

typedef int SLDataType;//元素数据类型
#define N 100    //顺序表的最大长度

//静态顺序表
struct SeqList
{
	SLDataType a[N];//顺序表的元素
	int size;//表中数据长度
};

静态顺序表因为数组的大小和空间以及固定，一定长度定义太小就会导致数据溢出程序崩溃。

3.3.2 动态定义

但是动态顺序表就能解决，它在执行中一旦发现空间占满可以通过语句进行扩充空间大小或者开辟一段更大的空间用来存储。所以我们一般用动态定义。

顺序表的动态定义：

typedef int SLDataType;//元素类型
#define INIT_CAPACITY 4//表长的初始定义

//动态顺序表
typedef struct SeqList
{
	SLDataType* a;//动态分配数组的指针
	int size;     //表的长度
	int capacity; //表的空间容量
}SL;              //类型定义

 

3.4 顺序表的初始化

 3.4.1 静态初始化

因为静态定义时已经定义了数组的长度，因此只需要将顺序表长度设为0就行了

//静态初始化
SL s;           //声明一个顺序表
void SLInit(SL s)
{
	s.size = 0;
}

3.4.2 动态初始化 

动态分配的初始化为顺序表分配一个预定义的数组空间，并将顺序表的当前长度设为0

//动态初始化
void SLInit(SL* ps)
{
    assert(ps);//检验ps
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);//分配存储空间
	if (ps->a == NULL)//检验是否分配成功
	{
		perror("malloc fail");
		return;
	}
	ps->capacity = INIT_CAPACITY;//初始存储容量
	ps->size = 0;//表长初始为0
}

 

3.5 顺序表的销毁

void SLDestroy(SL* ps)
{
	free(ps->a);    //释放顺序表空间
	ps->a = NULL;    //防止野指针
	ps->capacity = ps->size = 0;//归0
}

3.6 顺序表元素的打印

void SLPrint(SL* ps)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
}

 

3.7 顺序表的插入

3.7.1 检查空间，如果满了，进行增容

插入时，要保证内存足够用不能存在溢出，而我们在初始化时运用了malloc分配内存空间，当内存不够用时就可以用realloc进行扩容。

void CheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)//检查空间是否够用
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
		//扩大内存空间
		if (tmp == NULL)//检验扩容是否成功
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;//将顺序表指向扩容的空间
		ps->capacity *= 2;//空间容量随之扩大
	}

}

3.7.2 尾插

顾名思义就是从顺序表的最后插入数据：

void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps);//检查指针
    CheckCapacity(ps)；//扩容


	//ps->a[ps->size] = x;
	//ps->size++;

	ps->a[ps->size++] = x;//尾部插入数据
}

3.7.3 头插

顾名思义就是从顺序表的前面插入数据：

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);//检查指针
    CheckCapacity(ps)；//扩容

	int end = ps->size-1;//设置最后的数据位置
	while (end + 1)//数据整体后移
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;//头插
	ps->size++;//增加数据长度
}

3.7.4 中间插入

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//检查pos范围
    CheckCapacity(ps);//扩容
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;

}

3.8 顺序表的删除

3.8.1 尾删

检查

尾删顺序表时可能会删除过头，所以我们要进行判断：

1 温柔判断

顾名思义如果删除过头了则安安静静的不执行本次删除：

	//温柔检查
	if (ps->size < 0)
		return;
2 暴力判断 

如果删除过头则会弹出弹窗提醒你：

	//暴力检查
	assert(ps->size > 0);

如同还会告诉你错误行： 

 代码：
void SLPopBack(SL* ps)
{
	//暴力检查
	assert(ps->size > 0);

	//温柔检查
	//if (ps->size < 0)
	//	return;

	ps->size--;//减少数组个数
}

 

3.8.2 头删

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);//防止删减过头
	int begin = 0;
	while (begin < ps->size)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}

 

3.8.3 中间删除

void SeqListErase(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//判断pos范围
	int begin = pos;
	while (begin < ps->size-1)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;

}

3.9 顺序表的查询


int SLFind(SL* ps, SLDataType x)
{
    assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;//找到就返回
		}
	}
	return -1;//没找到返回-1
}

四、总结

       经过观察我们也发现头插和尾插可以用中间插入表示；头删和尾删也可以用中间删除表示。而头插和头删的时间复杂度是O(N^2),刚好是插入和删除的最坏情况；尾插和尾删的时间复杂度为O(N)，刚好是它们的最好情况所以改选什么知道了吗。

        顺序表仅仅是线性表的一种，而线性表也仅仅是数据结构的一种，接下来姜糖还会给大家带去更好的作品，大家记得一键三连呀，谢谢大家支持。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/686209.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

百度AI大底座

百度AI大底座

“百度AI大底座”是源自百度多年产业深度实践积累、结合AI全栈技术科研成果打造的国内首个全栈自研的AI基础设施&#xff0c; 面向企业和产业AI开发与应用提供端到端自主可控、自我进化的解决方案&#xff0c;能够快捷、低成本地实现“AI能力的随用随 取”。AI大底座可助力企业…
阅读更多...
Python 学习flask创建项目

Python 学习flask创建项目

1、使用pycharm创建flask项目 2、运行访问地址 3、可以看到访问地址内容 4、可以增加路由&#xff0c;尝试访问获取参数
阅读更多...
树莓派4B_OpenCv学习笔记4:测试摄像头_imread加载显示图像_imwrite保存图片

树莓派4B_OpenCv学习笔记4:测试摄像头_imread加载显示图像_imwrite保存图片

今日继续学习树莓派4B 4G&#xff1a;&#xff08;Raspberry Pi&#xff0c;简称RPi或RasPi&#xff09; 本人所用树莓派4B 装载的系统与版本如下: 版本可用命令 (lsb_release -a) 查询: Opencv 版本是4.5.1&#xff1a; 今日对之前的测试CSI摄像头函数进行一些理解说明&#x…
阅读更多...
Shell脚本文本处理三剑客（grep、awk、sed）和正则表达式

Shell脚本文本处理三剑客（grep、awk、sed）和正则表达式

一、正则表达式 1.正则表达式基础 正则表达式&#xff08;regular expression&#xff09;描述了一种字符串匹配的模式&#xff08;pattern&#xff09;&#xff0c;可以用来检查一个串是否含有某种子串&#xff0c;将匹配的子串替换或者从某个串中取出符号某个条件的子串等&…
阅读更多...
【微信小程序】页面事件

【微信小程序】页面事件

下拉刷新 上拉触底 上拉触底距离指的是触发上拉触底事件时&#xff0c;滚动条距离页面底部的距离。 可以在全局或页面的json配置文件中&#xff0c;通过onReachBottomDistance属性来配置上拉触底的距离。 小程序默认的触底距离是50x,在实际开发中&#xff0c;可以根据自己的需…
阅读更多...
【C++】─篇文章带你熟练掌握 map 与 set 的使用

【C++】─篇文章带你熟练掌握 map 与 set 的使用

目录 一、关联式容器二、键值对三、pair3.1 pair的常用接口说明3.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/utility/pair/pair/)3.1.2 [有参构造函数 / 拷贝构造函数](https://legacy.cplusplus.com/reference/utility/pair/pair/)3.1.3 [有参构造函数](htt…
阅读更多...
vue3 基于el-tree增加、删除节点（非TypeScript 写法）

vue3 基于el-tree增加、删除节点（非TypeScript 写法）

话不多说&#xff0c;直接贴代码 <template><div class"custom-tree-container"><!-- <p>Using render-content</p><el-tree style"max-width: 600px" :data"dataSource" show-checkbox node-key"id" …
阅读更多...
智能网联汽车信息安全风险识别与应对策略研究综述

智能网联汽车信息安全风险识别与应对策略研究综述

摘要&#xff1a;随着智能网联汽车技术的飞速发展&#xff0c;其信息安全问题逐渐成为公众关注的焦点。本文概述了智能网联汽车技术的发展背景和信息安全风险的来源&#xff0c;采用STRIDE威胁分析方法对智能网联汽车的四层模型进行风险识别&#xff0c;进一步探讨了抗女巫攻击…
阅读更多...
Renesas MCU之FreeRTOS的应用

Renesas MCU之FreeRTOS的应用

目录 概述 1 FSP配置FreeRTOS 1.1 软件版本信息 1.2 配置FreeRTOS 2 FreeRTOS的Task 2.1 FSP下的项目结构 2.2 Task代码 2.2.1 Task测试案例配置 2.2.2 测试代码实现 3 自定义Task 3.1 编写代码 3.2 测试函数 4 测试 4.1 Task断点测试 4.2 板卡运行测试 概述 …
阅读更多...
spring boot sso

spring boot sso

代码&#xff1a;https://gitee.com/forgot940629/ssov2 授权服务 登录成功后&#xff0c;session中会存储UsernamePasswordAuthenticationToken&#xff0c;之后每次请求code时都会用UsernamePasswordAuthenticationToken生成OAuth2Authentication&#xff0c;并将OAuth2Aut…
阅读更多...
动态规划（多重背包问题+二进制优化）

动态规划（多重背包问题+二进制优化）

引言 多重背包&#xff0c;相对于01背包来说&#xff0c;多重背包是每个物品会有相应的个数&#xff0c;最多可以选那么多个&#xff0c;因而对于朴素多重背包&#xff0c;需要在01背包的基础上&#xff0c;再加一层物品的循环 朴素多重背包例题 P2347 [NOIP1996 提高组] 砝…
阅读更多...
【FAS】《Liveness Detection on Face Anti-spoofing》

【FAS】《Liveness Detection on Face Anti-spoofing》

文章目录 原文总结与评价CNN-RNN vs 三维卷积作者的方法 原文 [1]欧阳文汉.反人脸图像欺诈的活体识别方法研究[D].浙江大学,2020.DOI:10.27461/d.cnki.gzjdx.2020.002675. 总结与评价 时序运动信息与传统的空间纹理信息相结合 基于相位平移的运动放大算法不错 视觉大小细胞…
阅读更多...
【Python报错】已解决Attributeerror: ‘list‘ object has no attribute ‘join‘( Solved)

【Python报错】已解决Attributeerror: ‘list‘ object has no attribute ‘join‘( Solved)

解决Python报错&#xff1a;AttributeError: ‘list’ object has no attribute ‘join’ (Solved) 在Python中&#xff0c;字符串&#xff08;str&#xff09;对象有一个非常有用的join()方法&#xff0c;它允许你将序列中的元素连接&#xff08;join&#xff09;成一个字符串…
阅读更多...
深入理解C++三五零法则

深入理解C++三五零法则

三五零法则就是三法则&#xff08;The Rule of Three&#xff09;、五法则&#xff08;The Rule of Five&#xff09;、零法则&#xff08;The Rule of Zero&#xff09;。三五零法则是和C的特殊成员函数有关&#xff0c;特别是那些涉及对象如何被创建、复制、移动和销毁的函数…
阅读更多...
苹果不会在WWDC 2024中推出任何搭载M4芯片的Mac电脑

苹果不会在WWDC 2024中推出任何搭载M4芯片的Mac电脑

虽然苹果公司已在上月推出了首搭 M4 芯片的 iPad Pro&#xff0c;不过彭博社的马克・古尔曼在最近的实时通讯中透露苹果公司不会在即将进行的 WWDC 2024 开发者大会中推出任何搭载 M4 芯片的 Mac 电脑&#xff08;不会推出任何硬件产品&#xff09;。 此前报道&#xff0c;苹果…
阅读更多...
如何自动生成数据库的样本数据（以MySQL和SQLynx为例）

如何自动生成数据库的样本数据（以MySQL和SQLynx为例）

目录 1 功能概述 2 主要特点 3 使用场景 4 使用示例 5 结论 SQLynx 是一款领先的 SQL 集成开发环境&#xff08;IDE&#xff09;&#xff0c;其强大的功能得到了全球用户的广泛认可。SQLynx 不仅在数据库管理和 SQL 查询方面表现出色&#xff0c;还提供了一项特别实用的功能…
阅读更多...
【Python报错】已解决AttributeError: ‘method‘ object has no attribute ‘xxx‘

【Python报错】已解决AttributeError: ‘method‘ object has no attribute ‘xxx‘

解决Python报错&#xff1a;AttributeError: ‘method’ object has no attribute ‘xxx’ 在Python中&#xff0c;AttributeError通常表明你试图访问的对象没有你请求的属性或方法。如果你遇到了AttributeError: method object has no attribute xxx的错误&#xff0c;这通常意…
阅读更多...
宇宙数字宣布2023年上半年盈利翻倍，数字货币挖矿业务持续增长

宇宙数字宣布2023年上半年盈利翻倍，数字货币挖矿业务持续增长

2023年3月8日宇宙数字公司在2023年上半年盈利翻倍的消息,彰显了该公司在数字货币挖矿领域的卓越表现和领先地位。这一成就是宇宙数字创新研发策略成功的明证,同时也体现了其高效能挖矿产品和解决方案在全球市场的广泛认可和需求。 随着数字货币市场的持续变化和发展,宇宙数字公…
阅读更多...
15- Redis 中的 整数集合 数据结构

15- Redis 中的 整数集合 数据结构

整数集合是 Set 对象的底层实现之一。当一个 Set 对象只包含整数值元素&#xff0c;并且元素数量不大时&#xff0c;就会使用整数集合这个数据结构作为底层实现。 1. 整数集合结构设计 整数集合本质上是一块连续内存空间&#xff0c;它的结构定义如下&#xff1a; typedef s…
阅读更多...
七月份大理站、ACM独立出版、高录用稳检索，2024年云计算与大数据国际学术会议（ICCBD 2024)

七月份大理站、ACM独立出版、高录用稳检索，2024年云计算与大数据国际学术会议（ICCBD 2024)

【ACM独立出版 | 高录用 | EI核心检索稳定】 2024年云计算与大数据国际学术会议&#xff08;ICCBD 2024) 2024 International Conference on Cloud Computing and Big Data (ICCBD 2024) 一、重要信息 大会官网&#xff1a;www.iccbd.net &#xff08;点击投稿/参会/了解会…
阅读更多...
最新文章

Copyright @ 2022~2023