[C][数据结构][顺序表]详细讲解+实现
目录
- 1.线性表
- 2.顺序表 - SeqList
- 3.实现
- 4.顺序表缺点
1.线性表
- 线性表(linear list)是n个具有相同特性的数据元素的有限序列
- 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
- 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储
2.顺序表 - SeqList
-
概念及结构
- 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改 (此数组必须从第一个位置开始,连续存储)

-
动态顺序表 – 使用动态开辟的数组存储
3.实现
- 接口
typedef int SLDataType;//类型重命名,方便以后维护替换别的类型typedef struct SeqList
{SLDataType* arr;//指向动态数组指针int size;//有效数据个数int capacity;//容量 - 空间大小
}SL;//顺序表初始化
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);//检测增容
void SLCheckCapacity();//增删查改
//尾插/尾删 - O(1)
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);//头插/头删 - O(N)
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);//从任意位置插入/删除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);//查找和修改
int SLSearch(SL* ps, SLDataType x);
void SLModify(SL* ps, int pos, SLDataType x);
- 接口实现
void SLInit(SL* ps)
{assert(ps);ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}void SLDestroy(SL* ps)
{assert(ps);if (ps->arr){free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->size = 0;}
}void SLPrint(SL* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SLCheckCapacity(SL* ps)
{assert(ps);//检查容量空间,满了扩容if (ps->size == ps->capacity){ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //最大容量扩容SLDataType* tmp = realloc(ps->arr, ps->capacity * sizeof(SLDataType));if (NULL == tmp){perror("realloc:");exit(1);}ps->arr = tmp;}
}void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size] = x;ps->size++;//SLInsert(ps, ps->size, x); //以上代码可以用这个封装替换了
}void SLPopBack(SL* ps)
{assert(ps);//暴力检查 - 适用于调试阶段assert(ps->size > 0);//温柔检查 - 适用于和用户交互使用//if (0 == ps->size)//{// printf("SeqList is empty\n");// return;//}ps->size--;SLErase(ps, ps->size - 1); //以上代码可以用这个封装替换了
}void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = x;ps->size++;//SLInsert(ps, 0, x); //以上代码可以用这个封装替换了
}void SLPopFront(SL* ps)
{int begin = 1;while (begin < ps->size){ps->arr[begin - 1] = ps->arr[begin];begin++;}ps->size--;//SLErase(ps, 0); //以上代码可以用这个封装替换了
}void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size); //检验位置合法性SLCheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= pos){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[pos] = x;ps->size++;
}void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//挪动数据int begin = pos;while (begin < ps->size - 1){//后面的数据往前搬ps->arr[begin] = ps->arr[begin + 1];begin++;}ps->size--;
}int SLSearch(SL* ps, SLDataType x)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->arr[pos] = x;
}
4.顺序表缺点
- 空间不够,需要扩容。
- 扩容有一定性能损耗
- 一般扩容两倍,存在一些空间浪费
- 头部或者中间位置插入删除效率低下 – 挪动数据
- 改善方案 – 链表 – 对顺序表缺陷的优化
- 按需申请释放空间
- 头部或者中间插入删除,不需要挪动数据
相关文章:
[C][数据结构][顺序表]详细讲解+实现
目录 1.线性表2.顺序表 - SeqList3.实现4.顺序表缺点 1.线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构࿰…...
vscode运行Java utf-8文件中文乱码报错
问题现象 vscode 运行utf-8 java文,爆出如下错误 hello.java:5: ����: ����GBK�IJ���ӳ���ַ&a…...
Mybatis杂记
group by查询返回map类型 1,2 List<Map<String, Object>> getCount();xml: <select id"getCount" resultType"java.util.HashMap">SELECT company_id, ifnull(sum(count_a count_b),0) ctFROM test.com_countWHERE is_del 0 GROUP BY…...
修改缓存供应商--EhCache
除了我们默认的缓存形式simlpe之外, 我们其实还有许多其他种类的缓存供应 Ehcache就是其中的一种形式 Ehcache在SpringBoot当中的使用: 其实跟我们之前整合第三方的资源是一样的形式 1>导入依赖: <!-- 更换缓存, 将默认使用的 Simple 更换为Ehcache--> <depe…...
20240606更新Toybrick的TB-RK3588开发板在Android12下的内核
20240606更新Toybrick的TB-RK3588开发板在Android12下的内核 2024/6/6 10:51 0、整体编译: 1、cat android12-rk-outside.tar.gz* | tar -xzv 2、cd android12 3、. build/envsetup.sh 4、lunch rk3588_s-userdebug 5、./build.sh -AUCKu -d rk3588-toybrick-x0-a…...
x264 参考帧管理源码分析
x264参考帧管理 在x264中,参考帧的管理是一个重要的组成部分,因为它涉及到视频编码过程中的帧间预测。以下是关于x264参考帧管理的一些关键点: 参考帧的分类:在x264中,帧可以分为几类,包括参考帧、当前编码帧和未使用帧等。 参考帧的作用:参考帧用于帧间预测,通过比较当…...
大语言模型应用与传统程序的不同
大语言模型(LLM) 被描述的神乎其神,无所不能,其实,大语言模型只是一个模型,它能够理解和生成自然语言,唯有依靠应用程序才能够发挥作用。例如,基于大模型可以构建一个最简单的会话机…...
MySQL换路径(文件夹)
#MySQL作为免费数据库很受欢迎,即使公司没有使用,自己也可以用。它是一个服务,在点击CtrlAltDelete选择任务管理器后,它在服务那个归类里。 经常整理计算机磁盘分类的小伙伴,如果你们安装了MySQL,并且想移…...
企业诚信管理:构建顾客忠诚的高性价比之道
在当今竞争激烈的市场环境中,企业若想脱颖而出,赢得顾客的长期青睐,必须找到一种高效且高性价比的策略来维系顾客忠诚。售后服务作为这种策略的核心,不仅解决了顾客在购买后的各种问题,还在无形中提升了顾客对品牌的信…...
如何利用pandas解析html的表格数据
如何利用pandas解析html的表格数据 我们在编写爬虫的过程中,经常使用的就是parsel、bs4、pyquery等解析库。在博主的工作中经常的需要解析表格形式的html页面,常规的写法是,解析table表格th作为表头,解析td标签作为表格的行数据 …...
hadoop疑难问题解决_NoClassDefFoundError: org/apache/hadoop/fs/adl/AdlFileSystem
1、问题描述 impala执行查询:select * from stmta_raw limit 10; 报错信息如下: Query: select * from sfmta_raw limit 10 Query submitted at: 2018-04-11 14:46:29 (Coordinator: http://mrj001:25000) ERROR: AnalysisException: Failed to load …...
文件传输基础——Java IO流
系列文章目录 文章目录 系列文章目录前言一、文件的编码二、File类的使用三、RandomAccessFile类的使用 前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用…...
Mysql时间操作
一、MySql时间戳转换 select unix_timestamp(); #获取时间戳格式时间 select FROM_UNIXTIME(1717399499); #将时间戳转换为普通格式时间二、Mysql时间相加减结果转换为秒 方法1:time_to_sec(timediff(endTime, startTime)) SELECTDISTINCT(column1),min(last_mo…...
Nvidia Jetson/Orin +FPGA+AI大算力边缘计算盒子:无人机自主飞行软件平台
案例简介 北京泛化智能科技有限公司(gi)所主导开发的 Generalized Autonomy Aviation System (GAAS) 是为无人机以及城市空中交通 (UAM, Urban Air Mobility) 所设计的开源无人机自主飞行框架。通过 SLAM、路径规划和 Global Optimization Graph 等功能…...
weak的底层原理
weak 引用在 iOS 中通过维护一个全局的弱引用表来实现。当弱引用的对象被释放时,所有指向它的弱引用会被自动置为 nil,从而防止悬挂指针。 弱引用表(Weak Table)的键和值 理解弱引用表的键和值对于理解 weak 引用的底层机制非常重…...
03-3.1.3 栈的链式存储的实现
👋 Hi, I’m Beast Cheng👀 I’m interested in photography, hiking, landscape…🌱 I’m currently learning python, javascript, kotlin…📫 How to reach me --> 458290771qq.com 喜欢《数据结构》部分笔记的小伙伴可以订…...
传输协议TCP-原理部分
传输控制协议TCP(Transmission Control Protocol)一种基于连接的可靠的稳定的无重复的传输协议。 1、TCP头部信息 TCP协议头部信息如下: 一共占用20个字节 16位源端口号:发送进程的主机端口16位目的端口号:接收主机…...
【android】设置背景图片
改变值,可显示zai在 在theves下面的两个value都要增加名字代码 <item name"windowActionBar">false</item><item name"android:windowNoTitle">true</item><item name"android:windowFullscreen">tru…...
Java微服务实战:使用Spring Boot构建高效服务
引言 在当今的软件开发实践中,微服务架构已成为推动快速开发和部署的关键因素之一。与传统的单体应用相比,微服务架构提供了更高的灵活性和可维护性。本文将探讨如何使用Java和Spring Boot来构建一个微服务应用,介绍基本概念,并通…...
【大模型】基于Hugging Face调用及微调大模型(1)
文章目录 一、前言二、Transformer三、Hugging Face3.1 Hugging Face Dataset3. 2 Hugging Face Tokenizer3.3 Hugging Face Transformer3.4 Hugging Face Accelerate 四、基于Hugging Face调用模型4.1 调用示例4.2 调用流程概述4.2.1 Tokenizer4.2.2 模型的加载4.2.3 模型基本…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
机器学习的数学基础:线性模型
线性模型 线性模型的基本形式为: f ( x ) ω T x b f\left(\boldsymbol{x}\right)\boldsymbol{\omega}^\text{T}\boldsymbol{x}b f(x)ωTxb 回归问题 利用最小二乘法,得到 ω \boldsymbol{\omega} ω和 b b b的参数估计$ \boldsymbol{\hat{\omega}}…...
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章 摘要: 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言,受限于 C 语言本身的内存安全和并发安全问题,开发复杂模块极易引入难以…...
