【数据结构】顺序表实现的层层分析！！

在这里插入图片描述
关注小庄 顿顿解馋◍˃ ᗜ ˂◍

引言：本篇博客我们来认识数据结构其中之一的顺序表，我们将认识到什么是顺序表以及顺序表的实现，请放心食用~

文章目录

  • 一.什么是顺序表
    • 🏠 线性表
    • 🏠 顺序表
  • 二.顺序表的实现
    • 🏠 静态顺序表
    • 🏠 动态顺序表
      • 接口的实现
  • 三.顺序表的优缺点

一.什么是顺序表

🏠 线性表

线性表是n个有相同特性数据元素的有限序列，是一种广泛使用的数据结构，常用的数据结构有链表，顺序表，队列和栈等

特点： 线性表在逻辑结构上是线性的(一条连续的直线),但在物理结构不一定连续。

理解：比如我们在排队时，我们脑海中认为我们队伍应该是排成一条直线的，实际上也应该如此，这里就是类似我们待会要讲的顺序表，但有有时不免有人会插队三五成群排在队伍左右边，类似我们线性表中的链表。

🏠 顺序表

顺序表是由一块连续的物理内存空间构成的，也就是说它的逻辑结构是线性，物理结构也是线性的。

那有什么结构是连续的一块的内存空间呢？

这里我们就可以用我们的数组来实现顺序表，你也可以理解为顺序表本质就是数组

二.顺序表的实现

我们一般用顺序表实现对我们的数据进行增删查改操作，来很好地运用我们的数据，顺序表一般分为静态顺序表和动态顺序表。

  • 顺序表结构的分析
    我们既然知道顺序表的本质是数组,那我们需要定义一个数组；
    其次我们要对我们的数据进行增删查改操作，那我们进行增的时候得知道我们空 间有多少容量吧，同时我们进行删除操作时也需要有“边界感”，如果不知道顺序表有没有数据就麻烦了。

因此，我们可以定义一个size来表示有效数据个数,用一个capacity代表顺序表的容量
在这里插入图片描述
注：这里由于数组下标是从0开始，所以我们的size要往前一步跟下标同步

🏠 静态顺序表

静态顺序表：使用定长数组来存储元素

静态顺序表的封装

//静态顺序表
typedef int Datatype;//相同类型元素 方便不同数据类型直接替换
#define N 100
struct Seqlist
{
	Datatype arr[N];
	int size;
	int capacity;
};

缺点: 静态顺序表的数组长度是限定的,导致无法灵活存放数据。空间大了导致浪费，空间小了导致数据丢失。

因此，在实际中，我们采用动态顺序表来操作我们的数据

🏠 动态顺序表

C语言动态内存管理工作是给我们程序员做的，给我们提供更多的灵活性，由程序员决定空间何时申请和释放。我们可利用这特点实现动态顺序表

//动态顺序表
typedef int Datatype; 
typedef struct Seqlist
{
	Datatype * arr;
	int size;
	int capacity;
}Seqlist;

接口的实现

  • 顺序表的初始化
void InitSeqlist(Seqlist* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

注：这里要传结构体指针，通过传址调用来修改size和capacity

  • 顺序表的打印
    这里就体现size的用处了，从下标0开始，到size就停止打印
void PrintSeqlist(Seqlist* ps)
{
	assert(ps->size != 0);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
}
  • 顺序表的头插和尾插
    在这里插入图片描述

顺序表的头插和尾插我们需要解决容量问题
对于空顺序表和空间足够的顺序表我们自然无需担心，但对于size==capacity时的顺序表就需要扩容了，那该怎么扩呢？

我们有三种扩容方式：

  1. 一次扩容一个空间
  2. 一次扩容固定大小空间
  3. 成倍数扩容（1.5或2倍）
    理解：对于第一种扩容方式，有限次数扩容还好，但多次扩容会降低效率；对于第二种空间给少会数据丢失，给多会空间浪费
    最好方法就是成倍扩容，参考文章数组成倍扩容原因

因此进行尾插和头插前要判断是否扩容，不够就成倍扩

void Capacity(Seqlist* ps)
{
	assert(ps);

	int newcapacity = 0;
	if (ps->capacity == ps->size)
	{
		newcapacity = ps->capacity == 0 ? 4 : 2 * newcapacity;
		int* temp = (int*)realloc(ps->arr,newcapacity * sizeof(int));
		if(NULL == temp)
		{
		  perror("realloc failed");
		  exit(1);
		}
		ps->arr = temp;
	}
	ps->capacity = newcapacity;
}

尾插直接让size下标的空间用来赋值就可以了

void Pushtail(Seqlist* ps, Datatype x)
{
	assert(ps);
	//判断是否要扩容
	Capacity(ps);
	ps->arr[ps->size++] = x;
}

注：插入数据，size代表的有效数据个数也要增加

头插要先实现数据的左移再插入

void Pushhead(Seqlist* ps, Datatype x)
{
	assert(ps);
	//判断容量问题
	Capacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
  • 顺序表的头删和尾删
    请思考一个问题，清除数据，是否一定要删除这个数据？
    当然不是的，我们用不了这个数据使它失效也是可以的

尾删

void Deltail(Seqlist* ps)
{
	assert(ps->size);
	assert(ps);
	ps->size--;
}

头删直接左移数据再使数据无效即可

void Delhead(Seqlist* ps)
{
	assert(ps->size);
	assert(ps);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
	//删除数据不代表一定要删除
}

注：删除数据，要使size代表的有效数据个数对应减少

  • 指定位置删除数据和指定位置之前插入数据

删除数据注意size–就可以了，直接循环遍历到pos位置

void PosDel(Seqlist* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	assert(pos > 0&&pos<=ps->size);
	//pos等于size
	if (pos == ps->size)
	{
		ps->size--;
		return;
	}
	for (int i = pos - 1; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

注意 pos与下标差了1 还有pos的合法性

指定位置插入数据也是可以按照循环移动数据但要注意容量问题

void PosPush(Seqlist* ps, Datatype x, int pos)
{
	assert(ps);
	//要确保插入位置的合法性
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	Capacity(ps);
	for (i = ps->size; i > pos-1; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos-1] = x;
	ps->size++;
}

注意 pos合法性和下标关系

延伸：对于指定位置的插入和删除也可以采用memmove来实现

//顺序表的指定位置插入（memmove实现）
void SLInsert1(SL* ps, int pos, Datatype x)
{
	assert(ps);
	//要确保插入位置的合法性
	assert(pos >= 0 && pos < ps->size);
	Datatype arr2[1] = { 0 };
	arr2[0] = x;
	memmove(ps->arr+pos+1,ps->arr+pos,(ps->size-pos)*sizeof(Datatype));
	memmove(ps->arr + pos, arr2, 4);
	ps->size++;//记得插入后size要增加
}

//顺序表指定位置的删除(memmove)
void SLErase1(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	memmove(ps->arr+pos,ps->arr+pos+1,(ps->size-pos-1)*sizeof(Datatype));
	ps->size--;
}
  • 查找数据
    直接遍历即可
void SLFind(Seqlist* ps, Datatype x)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			printf("找到了下标为%d", i);
			return;
		}
	}
	printf("没找到!");
	return;
}

三.顺序表的优缺点

到这里我们的顺序表基本实现完了，我们分析一下他的优缺点

优点
1.利用数组下标支持随机访问
2.数组空间连续，cpu高速缓存命中率高

缺点
1.进行插入和删除时移动数据效率低下
2.扩容可能造成空间浪费和数据丢失
3.扩容要申请空间拷贝数据，有不小的消耗

总结：顺序表适用于频繁访问和元素高效存储的应用场景

那有什么方法可以解决顺序表暴露的问题呢？请听下回的链表~

本次分享到这就结束了，不妨来个一键三连呀~

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

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

相关文章

mysql在服务器中的主从复制Linux下

mysql在服务器中的主从复制Linux下

mysql在服务器中的主从复制Linux下 为什么要进行主从复制主从复制的原理主从复制执行流程操作步骤主库创建从库创建 测试 为什么要进行主从复制 在业务中通常会有情况&#xff0c;在sql执行时&#xff0c;将表锁住&#xff0c;导致不能进行查询&#xff0c;这样就会影响业务的…
阅读更多...
Window部署Exceptionless

Window部署Exceptionless

Exceptionless Elasticsearch 版本&#xff1a; Exceptionless&#xff1a;8.1.0 Elasticsearch&#xff1a;7.17.5 JDK&#xff1a;11.0.10 目录 一、Elasticsearch运行 二、 Exceptionless 一、Elasticsearch运行 bin目录下elasticsearch.bat 直接运行 访问 http://lo…
阅读更多...
Google发布开放的模型Gemma

Google发布开放的模型Gemma

今天&#xff0c;Google 发布了一系列最新的开放式大型语言模型 —— Gemma&#xff01;Google 正在加强其对开源人工智能的支持&#xff0c;我们也非常有幸能够帮助全力支持这次发布&#xff0c;并与 Hugging Face 生态完美集成。 Gemma 提供两种规模的模型&#xff1a; 7B …
阅读更多...
StarRocks加速查询——低基数全局字典

StarRocks加速查询——低基数全局字典

前言 StarRocks-2.0引入了低基数全局字典&#xff0c;可以通过全局字典将字符串的相关操作转换成整型相关操作&#xff0c;极大提升了查询性能。StarRocks 2.0后的版本默认会开启低基数字典优化。 一、低基数字典 对于利用整型替代字符串进行处理&#xff0c;通常使用字典编码…
阅读更多...
一、网络基础知识

一、网络基础知识

1、IP地址和端口号 1.1、IP地址 定义&#xff1a;用于在网络中唯一标识设备的地址。格式&#xff1a;通常由四个数字组成&#xff0c;以点分十进制表示&#xff0c;例如&#xff1a;192.168.0.1。(IPv4)作用&#xff1a;允许网络中的设备相互通信&#xff0c;通过IP地址可以定…
阅读更多...
期货量化001：获取玉米主连的数据到execel表中

期货量化001：获取玉米主连的数据到execel表中

用efinance库&#xff1a; import efinance as ef import pandas as pd# 获取期货基本信息 futures_info ef.futures.get_futures_base_info()# 根据名称找到玉米主力的行情ID corn_quote_id futures_info[futures_info[期货名称] 玉米主连][行情ID].values[0]# 获取玉米的…
阅读更多...
【这个词（Sequence-to-Sequence）在深度学习中怎么解释，有什么作用？】

【这个词（Sequence-to-Sequence）在深度学习中怎么解释，有什么作用？】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;深度学习笔记 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; Sequence-to-Sequence&#xff08;Seq2Seq&#xff09; Sequence-to-Sequence&#xff08;Seq2Seq…
阅读更多...
【机器学习】数据清洗——基于Pandas库的方法删除重复点

【机器学习】数据清洗——基于Pandas库的方法删除重复点

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;机器学习 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进…
阅读更多...
华为OD机试真题C卷-篇4

华为OD机试真题C卷-篇4

200分值题 可以处理的最大任务员工派遣快递员的烦恼符号运算伐木工反射计数分披萨推荐多样性贪心的歌手螺旋数组矩阵(100) 可以处理的最大任务 有一个tasks任务列表&#xff0c;需要处理其中的任务&#xff1b;tasks[i] [si, ei]&#xff0c;该任务可以在si<day<ei之间…
阅读更多...
网络安全-nc（Netcat）工具详解

网络安全-nc（Netcat）工具详解

经常在反弹shell的时候使用nc命令&#xff0c;但是从来没有了解过&#xff0c;今天翻书看到了&#xff0c;准备记录一下。 nc全称Netcat&#xff0c;是TCP/IP连接的瑞士军刀。哈哈我最喜欢瑞士军刀了。 有一个比较偏的知识点&#xff0c;nc还可以探测目标的端口是否开放&…
阅读更多...
Flink中的双流Join

Flink中的双流Join

1. Flink中双流Join介绍 Flink版本Join支持类型Join API1.4innerTable/SQL1.5inner,left,right,fullTable/SQL1.6inner,left,right,fullTable/SQL/DataStream Join大体分为两种&#xff1a;Window Join 和 Interval Join 两种。 Window Join又可以根据Window的类型细分为3种…
阅读更多...
【王道数据结构】【chapter6图】【P234t5】

【王道数据结构】【chapter6图】【P234t5】

假设图用邻接表表示&#xff0c;设计一个算法&#xff0c;输出从顶点vi到顶点vj的所有简单路径 #include <iostream>] #include <string.h> #define maxsize 10 typedef struct node{int data;struct node *next; }node ,*pnode;pnode buynode(int x) {pnode tmp(p…
阅读更多...
【Linux取经路】文件系统之缓冲区

【Linux取经路】文件系统之缓冲区

文章目录 一、先看现象二、用户缓冲区的引入三、用户缓冲区的刷新策略四、为什么要有用户缓冲区五、现象解释六、结语 一、先看现象 #include <stdio.h> #include <string.h> #include <unistd.h>int main() {const char* fstr "Hello fwrite\n"…
阅读更多...
电路设计（26）——速度表的multisim仿真

电路设计（26）——速度表的multisim仿真

1.设计要求 设计一款电路&#xff0c;能够实时显示当前速度。 用输入信号模拟行驶的汽车&#xff0c;信号频率的1hz代表汽车速度的1m/s。最后速度显示&#xff0c;以km/h为单位。 2.电路设计 当输入信号频率为40HZ时&#xff0c;显示的速度应该为144KM/h&#xff0c;仿真结果为…
阅读更多...
petalinux_zynq7 驱动DAC以及ADC模块之一：建立IP

petalinux_zynq7 驱动DAC以及ADC模块之一：建立IP

0. 环境 - ubuntu18 - vivado 2018.3 - mizar z7010 ada106模块 1. vivado 1.1 创建vivado工程 运行vivado source /tools/Xilinx/Vivado/2018.3/settings64.sh vivado& 创建vivado工程 Vivado -> Create Project -> Next -> -> Project name: …
阅读更多...
OpenCV中图像的HSV色彩空间

OpenCV中图像的HSV色彩空间

在HSV 色彩空间中H, S, V 这三个通道分别代表着色相(Hue)&#xff0c;饱和度(Saturation)和明度(Value)&#xff0c; 原本输出的HSV 的取值范围分别是0-360, 0-1, 0-1; 但是为了匹配目标数据类型OpenCV 将每个通道的取值范围都做了修改,于是就变成了0-180, 0-255, 0-255 impo…
阅读更多...
人机交互新研究：MIT开发了结合脑电和眼电的新式眼镜，与机器狗交互

人机交互新研究：MIT开发了结合脑电和眼电的新式眼镜，与机器狗交互

还记得之前的AI读心术吗&#xff1f;最近&#xff0c;「心想事成」的能力再次进化&#xff0c; ——人类可以通过自己的想法直接控制机器人了&#xff01; 来自麻省理工的研究人员发表了Ddog项目&#xff0c;通过自己开发的脑机接口&#xff08;BCI&#xff09;设备&#xff…
阅读更多...
设置墙、楼板每层的厚度和材质——群问题整理003

设置墙、楼板每层的厚度和材质——群问题整理003

你好&#xff0c;这里是BIM的乐趣&#xff0c;我是九哥~ 今天分享的是设置墙、楼板等每层的厚度和材质。 我们都知道&#xff0c;Revit中墙、板这类系统族&#xff0c;厚度设置和普通族是不太一样的&#xff0c;他的厚度参数可读&#xff0c;但是并不可设置&#xff0c;因为我…
阅读更多...
华为发布应用流程

华为发布应用流程

华为发布流程
阅读更多...
flannel网络拓扑

flannel网络拓扑

测试环境创建 在k8s中部署flannel网络插件 https://blog.csdn.net/weixin_64124795/article/details/128894411 参考文章部署k8s集群和flannel网络插件 我的k8s集群物理环境 我的集群中只有两个节点master和node1节点 [rootmaster sjs]# kubectl get node NAME STATU…
阅读更多...
最新文章

Copyright @ 2022~2023