顺序表的基本操作(必学)

 

目录

线性表:

顺序表:

概念和结构:

动态顺序表常用操作实现:

头文件(数组顺序表的声明):

各种基本操作总的声明: 

顺序表的初始化:

顺序表的销毁

顺序表的打印

检查是否需要扩容

尾插

头插

头删

尾删

顺序表的查找

顺序表的插入

顺序表的删除

顺序表的问题


线性表:

线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛应用的数据结构,常见的线性表:顺序表,链表,栈,队列,字符串……。

线性表在逻辑上是线性结构,也就说是连续的一条直线。但在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。

顺序表:

概念和结构:

顺序表是用一段物理地址连续的存储单元依次存放数据元素的线性结构,一般情况下用数组存储。 顺序表有一个特点:必须从头开始存数据

1.静态顺序表:使用定长数组存储元素

 2.动态顺序表:使用动态开辟的数组存储

动态顺序表常用操作实现:

头文件(数组顺序表的声明):


typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;    int size;      //数据的个数int capacity;    //容量大小
}SeqList;

使用SLDateType代替int是因为如果需要更改数据类型,直接将int修改即可,操作方便。

各种基本操作总的声明: 

//初始化
void SeqListInit(SeqList* ps);
//销毁
void SeqListDestroy(SeqList* ps);
//打印
void SeqListPrint(SeqList* ps);
//尾插
void SeqListPushBack(SeqList* ps, SLDateType x);
//头插
void SeqListPushFront(SeqList* ps, SLDateType x);
//头删
void SeqListPopFront(SeqList* ps);
//尾删
void SeqListPopBack(SeqList* ps);
//检查是否需要扩容
void SeqListCheckCapacity(SeqList* ps);// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

顺序表的初始化:

void SeqListInit(SeqList* ps)
{assert(ps);ps->capacity = 0;ps->size = 0;ps->a = NULL;
}

顺序表的销毁

void SeqListDestroy(SeqList* ps)
{assert(ps);if (ps->a != NULL){free(ps->a);ps->a = NULL;ps->capacity = 0;ps->size = 0;}
}

顺序表的打印

void SeqListPrint(SeqList* ps)		
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}

检查是否需要扩容

void SeqListCheckCapacity(SeqList* ps)
{assert(ps);if (ps->size == ps->capacity){int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * NewCapacity);if (tmp == NULL){perror("realloc");return;}ps->a = tmp;ps->capacity = NewCapacity;}}

尾插

void SeqListPushBack(SeqList* ps, SLDateType x)
{assert(ps);SeqListCheckCapacity(ps);ps->a[ps->size] = x;ps->size++; 
}

头插

void SeqListPushFront(SeqList* ps, SLDateType x)
{assert(ps);SeqListCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}

头删

void SeqListPopFront(SeqList* ps)
{assert(ps->size > 0);int begin = 1;while (begin<ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

尾删

void SeqListPopBack(SeqList* ps)
{assert(ps->size > 0);ps->size--;
}

顺序表的查找

int SeqListFind(SeqList* ps, SLDateType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}

顺序表的插入

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SeqListCheckCapacity(ps);int end = ps->size - 1;while (end>=pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;}

顺序表的删除

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

顺序表的问题

  1. 中间/头部的插入删除,时间复杂度为O(N)。
  2. 增容需要申请空间,拷贝数据,释放旧空间,会有不小消耗。
  3. 增容一般是2倍增长,必然会有一定的空间浪费。

因为以上这些问题,又有另一种表,叫链表。详情请关注下一篇文章。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Vue2+3入门到实战】(4)Vue基础之指令修饰符 、v-bind对样式增强的操作、v-model应用于其他表单元素 详细示例

目录 一、今日学习目标1.指令补充 二、指令修饰符1.什么是指令修饰符&#xff1f;2.按键修饰符3.v-model修饰符4.事件修饰符 三、v-bind对样式控制的增强-操作class1.语法&#xff1a;2.对象语法3.数组语法4.代码练习 四、京东秒杀-tab栏切换导航高亮1.需求&#xff1a;2.准备代…

大数据深度解析NLP文本摘要技术:定义、应用与PyTorch实战

文章目录 大数据深度解析NLP文本摘要技术&#xff1a;定义、应用与PyTorch实战1. 概述1.1 什么是文本摘要&#xff1f;1.2 为什么需要文本摘要&#xff1f; 2. 发展历程2.1 早期技术2.2 统计方法的崛起2.3 深度学习的应用2.4 文本摘要的演变趋势 3. 主要任务3.1 单文档摘要3.2 …

2023年国赛高教杯数学建模E题黄河水沙监测数据分析解题全过程文档及程序

2023年国赛高教杯数学建模 E题 黄河水沙监测数据分析 原题再现 黄河是中华民族的母亲河。研究黄河水沙通量的变化规律对沿黄流域的环境治理、气候变化和人民生活的影响&#xff0c;以及对优化黄河流域水资源分配、协调人地关系、调水调沙、防洪减灾等方面都具有重要的理论指导…

mmdetection使用projects/gradio_demo

我用google的colab搭建。 # Check nvcc version !nvcc -V # Check GCC version !gcc --version # install dependencies: (use cu111 because colab has CUDA 11.1) %pip install -U openmim !mim install "mmengine>0.7.0" !mim install "mmcv>2.0.0rc4…

智能优化算法应用:基于蜣螂算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于蜣螂算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于蜣螂算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.蜣螂算法4.实验参数设定5.算法结果6.参考文献7.MA…

WPS复选框里打对号,显示小太阳或粗黑圆圈的问题解决方法

问题描述 WPS是时下最流行的字处理软件之一&#xff0c;是目前唯一可以和微软office办公套件相抗衡的国产软件。然而&#xff0c;在使用WPS的过程中也会出现一些莫名其妙的错误&#xff0c;如利用WPS打开docx文件时&#xff0c;如果文件包含复选框&#xff0c;经常会出…

民富购:塑造数字时代下的电商革新与社会责任典范

在数字经济时代,电子商务已经成为建立市场关系、创新产业和服务业态、促进经济增长的重要途径和手段。特别是在中国,新型电子商务的迅猛发展已经改变了生产和生活的方方面面,不仅催生了众多新业态,还通过“互联网”战略让许多传统产业和服务焕发了新的生机。民富购,作为扬羊(广…

【数据结构入门精讲 | 第十七篇】一文讲清图及各类图算法

在上一篇中我们进行了的并查集相关练习&#xff0c;在这一篇中我们将学习图的知识点。 目录 概念深度优先DFS伪代码 广度优先BFS伪代码 最短路径算法&#xff08;Dijkstra&#xff09;伪代码 Floyd算法拓扑排序逆拓扑排序 概念 下面介绍几种在对图操作时常用的算法。 深度优先D…

融资项目——swagger2的注解

1. ApiModel与ApiModelProperty(在实体类中使用) 如上图&#xff0c;ApiModel加在实体类上方&#xff0c;用于整体描述实体类。ApiModelProperty(value"xxx",example"xxx")放于每个属性上方&#xff0c;用于对属性进行描述。swagger2网页上的效果如下图&am…

2023RT-Thread开发者大会

参加了一次RT-Thread的开发者大会&#xff0c;相当有意思&#xff0c;虽然一天奔波挺累&#xff0c;但睡了半天之后简单剪了下22号的视频&#xff0c;也就有时间写自己的参会笔记了。 与openEuler社区不同&#xff0c;RT-Thread社区更专注于嵌入式&#xff0c;与硬件厂商结合…

算法通关村-番外篇排序算法

大家好我是苏麟 , 今天带来番外篇 . 冒泡排序 BubbleSort 最基本的排序算法&#xff0c;最常用的排序算法 . 我们以关键字序列{26,53,48,11,13,48,32,15}看一下排序过程: 动画演示 : 代码如下 : (基础版) class Solution {public int[] sortArray(int[] nums) {for(int i …

INFINI Gateway 如何防止大跨度查询

背景 业务每天生成一个日期后缀的索引&#xff0c;写入当日数据。 业务查询有时会查询好多天的数据&#xff0c;导致负载告警。 现在想对查询进行限制–只允许查询一天的数据&#xff08;不限定是哪天&#xff09;&#xff0c;如果想查询多天的数据就走申请。 技术分析 在每…

Go 泛型发展史与基本介绍

Go 泛型发展史与基本介绍 Go 1.18版本增加了对泛型的支持&#xff0c;泛型也是自 Go 语言开源以来所做的最大改变。 文章目录 Go 泛型发展史与基本介绍一、为什么要加入泛型&#xff1f;二、什么是泛型三、泛型的来源四、为什么需要泛型五、Go 泛型设计的简史六、泛型语法6.1 …

WT2605C音频蓝牙语音芯片:单芯片实现蓝牙+MP3+BLE+电话本多功能应用

在当今的电子产品领域&#xff0c;多功能、高集成度成为了一种趋势。各种产品都需要具备多种功能&#xff0c;以满足用户多样化的需求。针对这一市场趋势&#xff0c;唯创知音推出了一款集成了蓝牙、MP3播放、BLE和电话本功能的音频蓝牙语音芯片——WT2605C&#xff0c;实现了单…

开源verilog模拟 iverilog verilator +gtkwave仿真及一点区别

开源的 iverilog verilator 和商业软件动不动几G几十G相比&#xff0c;体积小的几乎可以忽略不计。 两个都比较好用&#xff0c;各有优势。 iverilog兼容性好。 verilator速度快。 配上gtkwave 看波形&#xff0c;仿真工具基本就齐了。 说下基本用法 计数器 counter.v module…

龙芯loongarch64服务器编译安装tensorflow-io-gcs-filesystem

前言 安装TensorFlow的时候,会出现有些包找不到的情况,直接使用pip命令也无法安装,比如tensorflow-io-gcs-filesystem,安装的时候就会报错: 这个包需要自行编译,官方介绍有限,这里我讲解下 编译 准备 拉取源码:https://github.com/tensorflow/io.git 文章中…

将mapper.xml保存为idea的文件模板

将mapper.xml保存为idea的文件模板 在idea的File and Code Templates中将需要使用模板的内容添加为模板文件。 那么接下来请看图&#xff0c;跟着步骤操作吧。 mapper.xml文件内容 <?xml version"1.0" encoding"UTF-8"?> <!DOCTYPE mapper P…

算法基础之最长公共子序列

最长公共子序列 核心思想&#xff1a; 线性dp 集合定义 : f[i][j]存 a[1 ~ i] 和 b[1 ~ j] 的最长公共子序列长度 状态计算&#xff1a; 分为取/不取a[i]/b[j] 共四种情况 其中 中间两种会包含两个都不取的情况(去掉) 但是因为取最大值 有重复也没事用f[i-1][j] 和 f[i][j-1]表…

【SpringBoot篇】解决缓存击穿问题② — 基于逻辑过期方式

&#x1f38a;专栏【SpringBoot】 &#x1f354;喜欢的诗句&#xff1a;天行健&#xff0c;君子以自强不息。 &#x1f386;音乐分享【如愿】 &#x1f384;欢迎并且感谢大家指出小吉的问题&#x1f970; 文章目录 &#x1f38d;什么是逻辑过期方式⭐思路&#x1f339;代码 &am…

RPC(6):RMI实现RPC

1RMI简介 RMI(Remote Method Invocation) 远程方法调用。 RMI是从JDK1.2推出的功能&#xff0c;它可以实现在一个Java应用中可以像调用本地方法一样调用另一个服务器中Java应用&#xff08;JVM&#xff09;中的内容。 RMI 是Java语言的远程调用&#xff0c;无法实现跨语言。…