[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 模型基本…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
前端开发者常用网站
Can I use网站:一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use:Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站:MDN JavaScript权威网站:JavaScript | MDN...
Python爬虫实战:研究Restkit库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...
起重机起升机构的安全装置有哪些?
起重机起升机构的安全装置是保障吊装作业安全的关键部件,主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理: 一、超载保护装置(核心安全装置) 1. 起重量限制器 功能:实时监测起升载荷&a…...
EEG-fNIRS联合成像在跨频率耦合研究中的创新应用
摘要 神经影像技术对医学科学产生了深远的影响,推动了许多神经系统疾病研究的进展并改善了其诊断方法。在此背景下,基于神经血管耦合现象的多模态神经影像方法,通过融合各自优势来提供有关大脑皮层神经活动的互补信息。在这里,本研…...
统计学(第8版)——统计抽样学习笔记(考试用)
一、统计抽样的核心内容与问题 研究内容 从总体中科学抽取样本的方法利用样本数据推断总体特征(均值、比率、总量)控制抽样误差与非抽样误差 解决的核心问题 在成本约束下,用少量样本准确推断总体特征量化估计结果的可靠性(置…...
