【初阶数据结构】序列系统重构：顺序表

文章目录

  • 1.线性表
  • 2.顺序表
    • 2.1 概念及结构
      • 2.1.1 静态顺序表
      • 2.2.2 动态顺序表
    • 2.2 接口实现
      • 2.2.1 顺序表打印
      • 2.2.2 顺序表初始化
      • 2.2.3 顺序表销毁
      • 2.2.4 顺序表容量检查
      • 2.2.5 顺序表尾插
      • 2.2.6 顺序表头插
      • 2.2.7 顺序表尾删
      • 2.2.8 顺序表头删
      • 2.2.9 顺序表在pos位置插入x
      • 2.2.10 顺序表在pos位置删除x
      • 2.2.11 顺序表查找
  • 3.顺序表的优劣
  • 4.代码展示
    • 4.1 SeqList.h
    • 4.2 SeqList.c
  • 希望读者们多多三连支持
  • 小编会继续更新
  • 你们的鼓励就是我前进的动力！

本篇介绍线性结构中的顺序表，这种连续排序的方式，这在需要频繁访问特定位置元素的应用场景（如矩阵运算、数组查询）中非常高效🚀

1.线性表

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

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

2.顺序表

2.1 概念及结构

顺序表是线性表的一种存储方式，它是用一组连续的存储单元依次存储线性表的数据元素。简单来说，就像是把线性表中的元素一个挨着一个地放在数组中进行增删查改工作，就像在一排连续的小格子里存放东西一样

请添加图片描述

2.1.1 静态顺序表

typedef int SLDataType;

//静态开辟（不推荐）
#define N 7
typedef struct SeqList
{
	SLDataType array[N];//指向动态开辟的数组
	int size;//数据个数
}SL;

静态顺序表就是创建一个普通的数组，通常数组的长度大小是固定的，所以这种存储方式是不灵活的，静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用，只适用于确定知道需要存多少数据的场景

2.2.2 动态顺序表

typedef int SLDataType;

#define INIT_CAPACITY 4
typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//数据个数
	int capacity;//空间容量
}SL;

动态顺序表是用的最多的顺序表，符合大多数场景下的使用，可以根据场景的需要试试调整数组的大小，比静态数组更加灵活

2.2 接口实现

2.2.1 顺序表打印

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

因为要访问ps指针，所以基本功能的实现都要用断言来预防非法访问，顺序表的打印和数组的打印基本思路一致，这里不过多赘述

2.2.2 顺序表初始化

void SeqInit(SL* ps)
{
	assert(ps);
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}

对顺序表初始化，这里有个头文件中的宏定义#define INIT_CAPACITY 4，目的是为了方便修改初始化时的大小，不然每次修改要改多处，定义之后就只需要修改一个地方即可，刚开始capacity也要给一定的容量，而不是0

2.2.3 顺序表销毁

void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

这里唯一要注意的点就是，释放完动态数组a之后要记得将指针置为空，不然会导致野指针的出现

2.2.4 顺序表容量检查

void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
	}
	ps->capacity *= 2;
}

size表示的是当前顺序表存储了多少数据，capacity表示的是当前顺序表能够存储多少数据，所以当数据存满了之后就需要进行扩容操作，通常我们每次扩容都只扩容两倍，以免空间的浪费

🔥值得注意的是： realloc开辟的空间大小不是ps->capacity * 2，而是sizeof(SLDataType) * ps->capacity * 2，前者是只考虑了扩大数组元素个数，但是没考虑到每个元素的字节大小，这是需要重点注意的

2.2.5 顺序表尾插

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->a[ps->size++] = x;
}//O(n)

尾插就是在顺序表最后面插入数据，先检查容量是否足够插入数据，然后ps->a[ps->size++] = x可以拆分为ps->a[ps->size] = x和ps->size++理解，先将下一个数据加入顺序表，然后修改size大小

尾插只需要把n个数据依次放到末尾，所以时间复杂度为O(n)

2.2.6 顺序表头插

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}//O(n^2)

还是一样，先检查容量是否足够插入数据，然后用覆盖的方式，将前一个数据覆盖到后一个数据上，即整体数据向右移动，也可以使用mommove函数，最后记得修改size大小，然后在开头插入数据

🔥值得注意的是： 头插每次插入n个数据之前都需要挪动数据，因此时间复杂度为O(n²)，所以得出结论尾插的效率是高于头插的

2.2.7 顺序表尾删

void SLPopBack(SL* ps)
{
	assert(ps->size> 0);
	ps->a[ps->size - 1] = 0;
	ps->size--;
}

最后一个数据的索引为size-1，所以将该位置的数据置为0即可，但又有人有疑问了，需不需要把删除的空间回收了?答案是不需要也没必要，因为通常空间的回收都是整体回收而不是一部分，而且多出来的空间也有可能被使用

🔥值得注意的是： 要考虑顺序表没有数据的情况，如果没有数据了还删除肯定是会造成访问错误的，所以要加断言assert(ps->size> 0)，头删也是如此

2.2.8 顺序表头删

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

先检查容量是否足够插入数据，然后用覆盖的方式，将后一个数据覆盖到前一个数据上，即整体数据向左移动，也可以使用mommove函数，最后记得修改size大小

2.2.9 顺序表在pos位置插入x

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos <= ps->size && pos >= 0);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

在pos位置之后将所有数据向左移，然后在pos位置插入数据，注意要断言pos <= ps->size && pos >= 0，避免传入的pos地址是个无效地址

2.2.10 顺序表在pos位置删除x

void SLErase(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos <= ps->size && pos >= 0);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

定义变量 begin 从要删除元素的下一个位置开始，使用 while 循环将从 pos + 1 位置开始的元素依次向左移动一个位置，覆盖要删除的元素

🔥值得注意的是： 最后一个元素不需要特殊处理。因为顺序表的元素个数是由 size 控制的，当 size 减 1 后，无论原来最后一个元素的值是什么，它都不在有效的元素列表中了，所以不需要对其进行特殊处理，如将其置为某个默认值或进行其他操作

2.2.11 顺序表查找

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

遍历数组，符合则返回索引值，不符合返回-1

3.顺序表的优劣

🚩1. 中间/头部的插入删除，时间复杂度为O(N)

🚩2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗

🚩3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间

4.代码展示

传送门：Gitee顺序表代码

4.1 SeqList.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLDataType;

//静态开辟（不推荐）
//#define N 7
//typedef struct SeqList
//{
//	SLDataType array[N];//指向动态开辟的数组
//	int size;//数据个数
//}SL;

//动态开辟
#define INIT_CAPACITY 4
typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//数据个数
	int capacity;//空间容量
}SL;

void SeqInit(SL* s);

void SeqDestory(SL* s);

void SLCheckCapacity(SL* ps);

void SLPushBack(SL* ps, SLDataType x);

void SLPushFront(SL* ps, SLDataType x);

void SLPopBack(SL* ps);

void SLPopFront(SL* ps);

void SLInsert(SL* ps, int pos, SLDataType x);

void SLErase(SL* ps, int pos, SLDataType x);

int SLFind(SL* ps, SLDataType x);

4.2 SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

//顺序表打印
void SLPrint(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

//顺序表初始化
void SeqInit(SL* ps)
{
	assert(ps);
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}

//顺序表销毁
void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

//检查空间，如果满了，进行增容
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
	}
	ps->capacity *= 2;
}

//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->a[ps->size++] = x;
}//O(n)

//顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}//O(n^2)

//顺序表头删
void SLPopFront(SL* ps)
{
	assert(ps); 
	assert(ps->size > 0);
	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}
//顺序表尾删
void SLPopBack(SL* ps)
{
	assert(ps->size> 0);
	ps->a[ps->size - 1] = 0;
	ps->size--;
}

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

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

//顺序表查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！

请添加图片描述

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

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

相关文章

Cosmos：英伟达发布世界基础模型，为机器人及自动驾驶开发加速！

Cosmos：英伟达发布世界基础模型，为机器人及自动驾驶开发加速！

1. 简介 在2025年消费电子展&#xff08;CES&#xff09;上&#xff0c;NVIDIA发布了全新的Cosmos平台&#xff0c;旨在加速物理人工智能&#xff08;AI&#xff09;系统的开发&#xff0c;尤其是自主驾驶车辆和机器人。该平台集成了生成式世界基础模型&#xff08;WFM&#x…
阅读更多...
Fine Report连接Mysql数据库

Fine Report连接Mysql数据库

点击 号 点击【数据库查询】 定义数据连接 数据库所在服务器的 IP 地址和端口号&#xff1b; 数据库的名称&#xff1b; 数据库的用户名和密码&#xff1b; 点击【测试连接】 编辑SQL语句 点击确定后&#xff0c;就会出现这张表的所有字段 注意&#xff1a; 一个sql语句对应…
阅读更多...
国内汽车法规政策标准解读：GB 44495-2024《汽车整车信息安全技术要求》

国内汽车法规政策标准解读：GB 44495-2024《汽车整车信息安全技术要求》

目录 背景 概述 标准适用范围 汽车信息安全管理体系要求 ​​​​​​​信息安全基本要求 信息安全技术要求 ◆ 外部连接安全要求&#xff1a; ◆通信安全要求&#xff1a; ◆软件升级安全要求&#xff1a; ◆ 数据安全要求&#xff1a; 检查试验方法 同一型式判定…
阅读更多...
我的年度总结

我的年度总结

这一年的人生起伏&#xff1a;从曙光到低谷再到新的曙光 其实本来没打算做年度总结的&#xff0c;无聊打开了帅帅的视频&#xff0c;结合自己最近经历的&#xff0c;打算简单聊下。因为原本打算做的内容会是一篇比较丧、低能量者的呻吟。 实习生与创业公司的零到一 第一段工…
阅读更多...
隧道IP广播与紧急电话系统：提升隧道安全的关键技术

隧道IP广播与紧急电话系统：提升隧道安全的关键技术

隧道IP广播与紧急电话系统&#xff1a;提升隧道安全的关键技术 随着现代城市交通的迅猛发展&#xff0c;隧道作为重要的交通基础设施&#xff0c;其安全性与应急处理能力显得尤为重要。隧道IP广播与紧急电话系统作为保障隧道安全的关键技术&#xff0c;正发挥着越来越重要的作…
阅读更多...
前端将项目部署到服务器(Nginx)的完整步骤（超级详细、保姆级）

前端将项目部署到服务器(Nginx)的完整步骤（超级详细、保姆级）

本文详细介绍了在Linux服务器上安装Nginx的步骤&#xff0c;包括准备环境&#xff08;如Xshell和Xftp的使用&#xff09;、安装依赖、下载、编译和配置Nginx&#xff0c;以及通过Xshell连接服务器、上传静态资源和重启服务的过程。 目录 一、准备环境 二、安装Xshell Xshell下…
阅读更多...
LeetCode 3280. 将日期转换为二进制表示

LeetCode 3280. 将日期转换为二进制表示

在这个问题中&#xff0c;我们需要将一个公历日期&#xff08;格式为 yyyy-mm-dd&#xff09;转换为其二进制表示。具体来说&#xff0c;我们需要将年、月、日分别转换为二进制字符串&#xff0c;并按照 year-month-day 的格式组合这些字符串。 解题思路 提取年、月、日&#…
阅读更多...
Vue2+OpenLayers给2个标点Feature分别添加独立的点击事件（提供Gitee源码）

Vue2+OpenLayers给2个标点Feature分别添加独立的点击事件（提供Gitee源码）

前言&#xff1a;之前开发都是将所有的点位存放在一个图层上面&#xff0c;并统一赋予它们相同的点击事件&#xff0c;如果其中某些点的点击事件不一样呢&#xff0c;这种问题如何解决呢&#xff0c;本篇博客就是解决这个通点。 目录 一、案例截图 二、安装OpenLayers库 三…
阅读更多...
【Unity】unity3D 调用LoadSceneAsync 场景切换后比较暗 部门材质丢失

【Unity】unity3D 调用LoadSceneAsync 场景切换后比较暗 部门材质丢失

解决方法&#xff1a;两个场景使用同样灯光 现象 直接进入第二个场景是可以正常显示 调用LoadSceneAsync来切换后&#xff0c;第二个场景出现比较暗的情况 解决方法&#xff1a;两个场景使用同样灯光&#xff0c;在loading 的场景中加入灯光。 Light—Directional Light 如果…
阅读更多...
【大模型系列篇】数字人音唇同步模型——腾讯开源MuseTalk

【大模型系列篇】数字人音唇同步模型——腾讯开源MuseTalk

之前有一期我们体验了阿里开源的半身数字人项目EchoMimicV2&#xff0c;感兴趣的小伙伴可跳转至《AI半身数字人开箱体验——开源项目EchoMimicV2》&#xff0c;今天带大家来体验腾讯开源的数字人音唇同步模型MuseTalk。 MuseTalk 是一个实时高品质音频驱动的唇形同步模型&#…
阅读更多...
海云安开发者安全智能助手D10荣膺 “ AI标杆产品 ” 称号，首席科学家齐大伟博士入选2024年度 “ 十大杰出青年 ”

海云安开发者安全智能助手D10荣膺 “ AI标杆产品 ” 称号，首席科学家齐大伟博士入选2024年度 “ 十大杰出青年 ”

2024年12月27日&#xff0c;粤港澳大湾区AI领袖峰会在深圳成功举办&#xff0c;大会表彰了在人工智能技术创新、应用实践和产业发展等方面取得优异成绩的企业和个人&#xff0c;深圳海云安网络安全技术有限公司开发者安全智能助手D10荣膺“AI标杆产品”称号。同时&#xff0c;公…
阅读更多...
Go基础之环境搭建

Go基础之环境搭建

文章目录 1 Go 1.1 简介 1.1.1 定义1.1.2 特点用途 1.2 环境配置 1.2.1 下载安装1.2.2 环境配置 1.2.2.1 添加环境变量1.2.2.2 各个环境变量理解 1.2.3 验证环境变量 1.3 包管理工具 Go Modules 1.3.1 开启使用1.3.2 添加依赖包1.3.3 配置国内包源 1.3.3.1 通过 go env 配置1.…
阅读更多...
基于 STM32 的多功能时间管理器项目

基于 STM32 的多功能时间管理器项目

引言 在快节奏的生活中&#xff0c;时间管理显得尤为重要。本项目旨在通过 STM32 开发一个多功能时间管理器&#xff0c;功能包括计时器、闹钟和日历。用户可以方便地设置不同的提醒和计时任务&#xff0c;以更好地管理日常生活和工作。 项目名称 多功能时间管理器 环境准备 …
阅读更多...
Windows上安装和配置Tabby终端工具并实现远程ssh连接内网服务器

Windows上安装和配置Tabby终端工具并实现远程ssh连接内网服务器

文章目录 前言1. Tabby下载安装2. Tabby相关配置3. Tabby简单操作4. ssh连接Linux4.1 ubuntu系统安装ssh4.2 Tabby远程ssh连接ubuntu 5. 安装内网穿透工具5.1 创建公网地址5.2 使用公网地址远程ssh连接 6. 配置固定公网地址 前言 今天我要给大家分享一个非常实用且强大的开源跨…
阅读更多...
国产Docker可视化面板Dpanel的安装与功能解析

国产Docker可视化面板Dpanel的安装与功能解析

国产Docker可视化面板Dpanel的安装及功能介绍 Docker 可视化面板系统&#xff0c;提供完善的 docker 管理功能。 支持查看基本信息、运行状态统计、网络统计、磁盘统计、用量统计等功能 ​​ ​​ 容器管理&#xff1a; ​​ 创建/修改容器 ​​ 支持基本配置、环境变量、…
阅读更多...
平滑算法 效果比较

平滑算法 效果比较

目录 高斯平滑 效果对比 移动平均效果比较： 高斯平滑 效果对比 右边两个参数是1.5 2 代码： smooth_demo.py import numpy as np import cv2 from scipy.ndimage import gaussian_filter1ddef gaussian_smooth_array(arr, sigma):smoothed_arr = gaussian_filter1d(arr, s…
阅读更多...
蓝桥杯_B组_省赛_2022（用作博主自己学习）

蓝桥杯_B组_省赛_2022（用作博主自己学习）

题目链接算法11.九进制转十进制 - 蓝桥云课 进制转换 21.顺子日期 - 蓝桥云课 时间与日期 31.刷题统计 - 蓝桥云课 时间与日期 41.修剪灌木 - 蓝桥云课 思维 51.X 进制减法 - 蓝桥云课 贪心 61.统计子矩阵 - 蓝桥云课 二维前缀和 71.积木画 - 蓝桥云课 动态规划 82.扫雷 - 蓝桥…
阅读更多...
Leetcode 2140. 解决智力问题 动态规划

Leetcode 2140. 解决智力问题 动态规划

原题链接&#xff1a;Leetcode 2140. 解决智力问题 class Solution { public:long long mostPoints(vector<vector<int>>& questions) {int n questions.size();vector<long long> dp(n, 0);for (int i n - 1; i > 0; i--) {int a questions[i][0]…
阅读更多...
JavaScript-正则表达式方法(RegExp)

JavaScript-正则表达式方法(RegExp)

RegExp 对象用于将文本与一个模式匹配。 有两种方法可以创建一个 RegExp 对象&#xff1a;一种是字面量&#xff0c;另一种是构造函数。 字面量由斜杠 (/) 包围而不是引号包围。 构造函数的字符串参数由引号而不是斜杠包围。 new RegExp(pattern[, flags])一.符集合 1.选择…
阅读更多...
网安——计算机网络基础

网安——计算机网络基础

一、计算机网络概述 1、Internet网相关概念及发展 网络&#xff08;Network&#xff09;有若干结点&#xff08;Node&#xff09;和连接这些结点的链路&#xff08;link&#xff09;所组成&#xff0c;在网络中的结点可以是计算机、集线器、交换机或路由器等多个网络还可以通…
阅读更多...
最新文章

Copyright @ 2022~2023