【初阶数据结构】深入解析顺序表:探索底层逻辑

请添加图片描述

🔥引言

本篇将深入解析顺序表:探索底层逻辑，理解底层是如何实现并了解该接口实现的优缺点，以便于我们在编写程序灵活地使用该数据结构。

请添加图片描述
Alt

🌈个人主页：是店小二呀
🌈C语言笔记专栏：C语言笔记
🌈C++笔记专栏： C++笔记
🌈初阶数据结构笔记专栏： 初阶数据结构笔记

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
请添加图片描述

文章目录

  • 一、线性表的概念
  • 二、顺序表的概念
  • 三、顺序表的分类
  • 四、实现顺序表的相关接口(Seqlist.h)
  • 五、正式开始模拟实现顺序表
    • 5.1 顺序表的初始化
    • 5.2 顺序表的扩容(为插入数据提供保障)
    • 5.3 顺序表的插入数据
      • 5.3.1 顺序表的尾插
      • 5.3.2 顺序表的头插
    • 5.4 顺序表的删除数据
      • 5.4.1 顺序表的尾删
      • 5.4.2 顺序表的头删
    • 5.5 查找指定位置的下标
    • 5.5 顺序表的任意位置插入(pos是下标)
    • 5.6 顺序表的任意位置删除(pos是下标)
    • 5.7 顺序表的判空(主要是否存在有效元素)
    • 5.8 顺序表的打印
    • 5.9 顺序表的销毁
  • 六、顺序表的优缺点
  • 七、顺序表和链表的区别

一、线性表的概念

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

二、顺序表的概念

顺序表属于线性表的其中一种。顺序表在逻辑、物理结构上是连续，顺序表底层逻辑实现一般是数组。关于物理结构上连续是指一段物理地址连续的存储单元依次存储数据元素的结构

三、顺序表的分类

顺序表分为两种：静态顺序表和动态顺序表，每一种都属于它自己的价值，在实际中。一般使用动态顺序表做的，比如我们经常用的通讯录(因为静态顺序表只适合事前知道需要多少内存的情况下，不然会出现申请多少内存问题)

在这里插入图片描述

四、实现顺序表的相关接口(Seqlist.h)

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

五、正式开始模拟实现顺序表

提前说明下:每一个接口都需要断言下传过来的指针是否为空指针去判断是否是一个有效的结构体变量。如果是第一次接触数据结构，首先需要搞清楚size代表了有效元素个数，而capacity代表的是这块空间的大小或者容量，这里两个东西不是一个意思。

小技巧:在循环中如果不知道结束条件的话，带入临界值去尝试是否符合条件

5.1 顺序表的初始化

void SLInit(SL* phead)
{
	assert(phead);
	phead->a = NULL;
	phead->size = phead->capacity = 0;
}

这里需要注意的是:空间上没有硬性要求不开空间，可以适当开辟空间，当空间不足时，需向系统申请空间。

5.2 顺序表的扩容(为插入数据提供保障)

void SLChekckCapacity(SL* phead)
{
	assert(phead);
	if (phead->size == phead->capacity)
	{
		int newcapacity =phead->capacity==0?4:phead->capacity * 2;
		SLDataType* pphead = (SLDataType*)realloc(phead->a, sizeof(SLDataType) * newcapacity);
		if (pphead == NULL)
		{
			perror("realloc fail!!");
			return 1;
		}
		phead->a = pphead;
		phead->capacity = newcapacity;
	}
}

这里需要注意的是:当有效元素个数等于当前空间容量为了下一次的插入元素，需要进行扩容操作。由于扩容功能需要多次调用，对此可以考虑设计为一个接口SLChekckCapacity进行复用。

在接口底层逻辑中，值得我们注意的是当capacity为空(零乘任何数为零)，会导致申请空间大小出现错误。这里有两种解决措施:提前开辟一定量空间或者使用新的变量newcapacity进行接收，防止数据丢失。最好不要phead直接接收扩容的地址，防止扩容(第二种情况)失败导致找不到之前空间地址。开辟以字符类型来维修开辟的空间，需要为‘\0‘开辟一个空间。

5.3 顺序表的插入数据

插入分为三类：头插\尾插\任意位置插入(其中任意位置插入，在实现查找功能先放着)

5.3.1 顺序表的尾插

void SLPlusBack(SL*phead, SLDataType x)
{
	assert(phead);
    if(phead->size == phead->capacity)
	SLChekckCapacity(phead);
	phead->a[phead->size] = x;
	phead->size++;
}

这里需要注意的是:这里主要利用下标赋值完成插入的操作

5.3.2 顺序表的头插

void SLPlusFront(SL* phead, SLDataType x)
{
	assert(phead);
    if(phead->size == phead->capacity)
	SLChekckCapacity(phead);
	for (int i = phead->size; i >0; i--)
	{
		phead->a[i] = phead->a[i - 1];
	}
	phead->a[0] = x;
	phead->size++;
}

这里需要注意的是:原数据整体向后移动，首次位置会数据重复，将首元素将其覆盖，实现头插的效果。

设置循环条件，数据向后移动(覆盖并数值不丢失)。如果是从前先后覆盖，比如1 2 3 4 5 变成 1 1 2 3 4 5，将i的值赋值给i+1，i从首元素下标开始并且覆盖方式nums[i+1]=nums[i]

5.4 顺序表的删除数据

删除分为三类：头删 尾删 任意位置删除(其中任意位置删除，在实现查找功能先放着)

提前说明:空表无法进行删除数据，需要在删除操作之前进行断言检查assert(phead->a)

5.4.1 顺序表的尾删

void SLPopBack(SL* phead)
{
	assert(phead);
	assert(phead->a);
	phead->size--;
}

这里需要注意的是:这里删除不是将数据设为0就是删除数据。正确的做法，通过size（有效数据个数）个数控制。顺序表不访问size外的无效数据，那么从某种意义上是删除了数据（班里有位同学退学，班里人数少一位，同学还是存在，只是座位没有它），不需要空间是否浪费，尾插数据时，可能下次还是用到那个空间。

5.4.2 顺序表的头删

void SLPopFront(SL* phead)
{
	assert(phead);
	assert(phead->a);
	for (int i = 0; i < phead->size-1; i++)
	{
		phead->a[i] = phead->a[i + 1];
	}
	phead->size--;
}

这里需要注意的是:数组删除数据的方式就是覆盖数据，那么只需要从后向前覆盖，首元素将被覆盖或者被删除

设置循环条件，数据向前移动(覆盖并数值不丢失)。如果是从后先前覆盖，比如1 2 3 4 5变成 2 3 4 5 5，将i+1的值赋值给i，i从首元素下标开始并且覆盖方式nums[i]=nums[i+1]

5.5 查找指定位置的下标

int SLFind(SL* phead, SLDataType x)
{
	assert(phead);
	assert(phead->a);
	for (int i = 0; i < phead->size; i++)
	{
		if (phead->a[i] == x)
            return i;
	}
	return -1;
}

这里需要注意的是:遍历顺序表，如果满足条件返回当前位置的下标，没有找到返回一个负数表示找不到。

5.5 顺序表的任意位置插入(pos是下标)

void SLInsert(SL* phead, int pos, SLDataType x)
{
	assert(phead);

	assert(0 <= pos && pos <= phead->size);
		SLChekckCapacity(phead);
		for (int i = phead->size; i>pos;i--)
		{
			phead->a[i] = phead->a[i-1];//pos+1 pos-->注意覆盖的顺序,向后就是后面开始
		}
		phead->a[pos] = x;	
		phead->size++;
}

这里需要注意的是:任意位置上的修改(任意是相对的，需要对pos进行限制)。具体流程就是以下标pos为界，pos之后的数据向后移动（跟头插类似，主要是在循环条件略显差异）

5.6 顺序表的任意位置删除(pos是下标)

void SLErase(SL* phead, int pos)
{
	assert(phead);
	assert(pos >= 0 && pos < phead->size);
	for (int i = pos;i<phead->size-1;i++)
	{
		phead->a[i] = phead->a[i + 1];
	}
	phead->size--;
}

这里需要注意的是:任意位置上的修改(任意是相对的，需要对pos进行限制)。具体流程就是以下标pos为界，pos之后的数据向前移动(跟头删是类似的，主要是在循环条件略显差异)

小总结:顺序表通过任意位置插入\删除去取代头尾的插入\删除操作，至于为什么需要了解头尾的插入\删除操作，虽然相当于基础，也是需要学习的(只有学会1+1，才能学会7+8)

5.7 顺序表的判空(主要是否存在有效元素)

bool SLEmpty(SL*phead)
{
	assert(phead);
    assert(phead->a);
    return phead->size==0;
}

5.8 顺序表的打印

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

5.9 顺序表的销毁

void SLDestory(SL*phead)
{
    assert(phead);
    if (phead->a)
    {
        free(phead->a);//free该前顺序表的动态开辟的空间
        phead->a = NULL;
        phead->size = phead->capacity = 0;
    }	
}

六、顺序表的优缺点

顺序表的优点:支持下标随机访问(时间复杂度O(1))

顺序表的缺点:

  • 在实现插入和删除操作过程中，通过大量的移动数据，效率较低
  • 空间不足需要扩容并且需要付出一定的代价，可能存在空间浪费
  • 只适合尾插尾删

七、顺序表和链表的区别

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定 连续
随机访问支持O(1)不支持：O(N)
任意位置插入或者删除 元素可能需要搬移元素，效率低 O(N)只需修改指针指向
插入动态顺序表，空间不够时需要 扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率高低

不管是哪一种数据结构都有他的优点和缺点，对此在使用数据结构中应该知道它的优缺点是什么，加以合理地利用解决实际中的问题。

请添加图片描述

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二初阶数据结构笔记，希望对你在学习初阶数据结构中有所帮助！

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

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

相关文章

java：使用JSqlParser给sql语句增加tenant_id和deleted条件

java：使用JSqlParser给sql语句增加tenant_id和deleted条件

# 示例代码 【pom.xml】 <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-core</artifactId><version>3.4.3.1</version> </dependency>【MyJSqlParserTest.java】 package com.chz.myJSqlParser;pu…
阅读更多...
如何利用 Google 搜索结果页来引导?

如何利用 Google 搜索结果页来引导?

在数据驱动的决策世界中&#xff0c;获取准确而全面的信息至关重要。Google 搜索结果抓取是一种强大的技术&#xff0c;可以让企业、调查人员和研究人员从搜索引擎结果中提取可靠的数据。本综合指南将深入研究 Google 搜索结果的最佳实践、工具和道德考量&#xff0c;以确定能够…
阅读更多...
4、视觉里程计：特征点法、直接法和半直接法

4、视觉里程计：特征点法、直接法和半直接法

先说一下我自己的总体理解&#xff1a; 特征点法&#xff0c;基于最小化重投影误。 提取特征点&#xff0c;计算描述子&#xff0c;匹配&#xff0c;运动估计。 计算描述子和匹配部分可以用光流法跟踪替代 总体上先知道像素之间的关系&#xff0c;在估计运动&#xff08;最…
阅读更多...
铝合金板件加工迎来3D视觉新时代

铝合金板件加工迎来3D视觉新时代

在制造业的浩瀚星空中&#xff0c;铝合金板件加工一直以其轻质、高强度、耐腐蚀的特性&#xff0c;扮演着举足轻重的角色。然而&#xff0c;随着市场竞争的加剧和产品需求的多样化&#xff0c;传统的加工方式已难以满足现代制造业对高效率、高精度的追求。在这个关键时刻&#…
阅读更多...
详细教学wps中公式如何居中，公式编号如何右对齐

详细教学wps中公式如何居中，公式编号如何右对齐

废话少说&#xff0c;首先打开WPS&#xff0c;新建一个空白文档。 详细步骤如下&#xff1a; &#xff08;1&#xff09;新建一个模板样式&#xff0c;在开始一栏中&#xff0c;点击新建样式具体操作看下图&#xff1a; &#xff08;2&#xff09;设计样式 修改样式名称为公…
阅读更多...
2024年制作AI问答机器人给企业带来的几大好处

2024年制作AI问答机器人给企业带来的几大好处

引言 在当今数字化时代&#xff0c;企业需要不断寻求创新&#xff0c;以提升客户服务水平、降低成本&#xff0c;并改善用户体验。其中&#xff0c;AI问答机器人作为一种智能化解决方案&#xff0c;正在成为越来越多企业的首选。本文将探讨制作AI问答机器人给企业内外部带来的…
阅读更多...
期权交易单位是什么？期权懂新手必看！

期权交易单位是什么？期权懂新手必看！

今天带你了解期权交易单位是什么&#xff1f;很多对期权还不太熟悉的朋友&#xff0c;不知道期权的单位是什么&#xff0c;下面小编就来告诉你期权的交易单位到底是什么&#xff1f; 期权交易单位是什么&#xff1f; 50ETF期权的交易单位&#xff0c;用大白话来说&#xff0c;…
阅读更多...
5.2 模块之间的交互和通信方式方法总结

5.2 模块之间的交互和通信方式方法总结

事件驱动通信&#xff1a; 事件驱动通信是一种通信模式&#xff0c;它基于事件的发生和相应来进行通信。在事件驱动通信中&#xff0c;各个组件之间通过发送事件来进行通信&#xff0c;而不是直接调用对方的方法。 事件驱动通信的基本原理是&#xff0c;当一个组件发生某个特…
阅读更多...
for语句初识

for语句初识

情景导入 某校某年级某班某位男生很爱哭&#xff0c;“wa”、“wa”、“wa”声音经常不绝于耳&#xff0c;现在请你通过编程来模拟他的哭声&#xff0c;他每发出一次哭声&#xff0c;则你输出一行——一个“wa”&#xff1b; 他哭了2次&#xff0c;我们可以这样写&#xff1a; …
阅读更多...
洗地机哪个牌子最好用？2024洗地机希亦、云鲸、追觅、必胜哪一款更好

洗地机哪个牌子最好用？2024洗地机希亦、云鲸、追觅、必胜哪一款更好

随着近几年科技水平的进步&#xff0c;洗地机也开始快速更新迭代&#xff0c;功能越来越全面&#xff0c;现在的洗地机相比早几年的机型相比无论是清洁力还是用户体验甚至拓展功能上都有很大的提升。这也让很多想选购洗地机的朋友们选择更加迷茫&#xff0c;不知道如何挑选&…
阅读更多...
Jsch上传本地目录文件到服务器

Jsch上传本地目录文件到服务器

文章目录 1.Jsch简介1.1 什么是Jsch1.2 Jsch使用步骤和简单示例 2.技术关键点3.Jsch实战3.1 maven依赖3.2 功能实现3.3 效果3.4 封装工具类 4.总结 摘要: 在一些框架开发工作中&#xff0c;需要为项目使用说明文档&#xff0c;来指导用户如何正确使用框架。比如通过markdown编写…
阅读更多...
React Redux

React Redux

React Redux是Redux的官方React UI绑定层。它允许您的React组件从Redux存储读取数据&#xff0c;并将操作分派到存储以更新状态。redux是一个管理状态数据state的容器。提供了可预测的状态管理。 React Redux 8.x需要React 16.8.3或更高版本/Rect Native 0.59或更高&#xff0c…
阅读更多...
萌啦OZON数据分析工具：OZON电商卖家的得力助手

萌啦OZON数据分析工具：OZON电商卖家的得力助手

在当下电商领域&#xff0c;数据分析的重要性不言而喻。对于在OZON这一俄罗斯电商平台上耕耘的卖家而言&#xff0c;拥有一款高效、准确的数据分析工具&#xff0c;无疑是提升销售业绩、优化运营策略的关键。今天&#xff0c;我们就来聊聊“萌啦OZON数据分析工具”&#xff0c;…
阅读更多...
每日一练——反转链表

每日一练——反转链表

206. 反转链表 - 力扣&#xff08;LeetCode&#xff09; /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode* reverseList(struct ListNode* head) {if (NULL head)return head;struct ListNode*…
阅读更多...
从0到100：找搭子小程序开发笔记(一)

从0到100：找搭子小程序开发笔记(一)

背景调查 “找搭子”小程序&#xff1a;能够解决人们在社交、休闲和约会方面的需求&#xff0c;提供方便快捷的方式来找到合适的伴侣或活动伙伴。许多人在社交场合中感到焦虑或不安&#xff0c;因此他们更倾向于使用在线平台来认识新的朋友或搭子。有些人可能生活在一个较小或…
阅读更多...
LayerNorm层归一化

LayerNorm层归一化

1.背景 与 Batch normalization 不同&#xff0c;Layer normalization 是在特征维度上进行标准化的&#xff0c;而不是在数据批次维度上。像 Batch Norm 它的核心是数据批次之间的归一化【强调的是第 i 批次和第 i1 批次的区别&#xff0c;然后BN去缩小他们的的区别】&#xf…
阅读更多...
opencv_GUI

opencv_GUI

图像入门 import numpy as np import cv2 as cv # 用灰度模式加载图像 img cv.imread(C:/Users/HP/Downloads/basketball.png, 0)# 即使图像路径错误&#xff0c;它也不会抛出任何错误&#xff0c;但是打印 img会给你Nonecv.imshow(image, img) cv.waitKey(5000) # 一个键盘绑…
阅读更多...
JAVAEE值之网络原理(1)_传输控制协议(UDP)、概念、特点、结构、代码实例

JAVAEE值之网络原理(1)_传输控制协议(UDP)、概念、特点、结构、代码实例

前言 在前两节中我们介绍了UDP数据报套接字编程&#xff0c;但是并没有对UDP进行详细介绍&#xff0c;本节中我们将会详细介绍传输层中的UDP协议。 一、什么是UDP&#xff1f; UDP工作在传输层&#xff0c;用于程序之间传输数据的。数据一般包含&#xff1a;文件类型&#xff0…
阅读更多...
掌握Google搜索结果获取

掌握Google搜索结果获取

在数据驱动的决策世界中&#xff0c;获取准确而全面的信息至关重要。Google 搜索结果抓取是一种强大的技术&#xff0c;可以让企业、调查人员和研究人员从搜索引擎结果中提取可靠的数据。本综合指南将深入研究 Google 搜索结果的最佳实践、工具和道德考量&#xff0c;以确定能够…
阅读更多...
攻防演练之-网络安全产品大巡礼二

攻防演练之-网络安全产品大巡礼二

书接上文&#xff0c;《网络安全攻防演练风云》专栏之攻防演练之-网络安全产品大巡礼一&#xff0c;这里。 “咱们中场休息一会&#xff0c;我去接杯水哈”&#xff0c;看着认真听讲的众人&#xff0c;王工很是满意&#xff0c;经常夹在甲乙两方受气的他&#xff0c;这次终于表…
阅读更多...
最新文章

Copyright @ 2022~2023