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

news/2025/1/17 5:19:46/

文章目录

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

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;
}

希望读者们多多三连支持

小编会继续更新

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

请添加图片描述


http://www.ppmy.cn/news/1563800.html

相关文章

卷积神经05-GAN对抗神经网络

卷积神经05-GAN对抗神经网络

卷积神经05-GAN对抗神经网络 使用Python3.9CUDA11.8Pytorch实现一个CNN优化版的对抗神经网络 简单的GAN图片生成 CNN优化后的图片生成 优化模型代码对比 0-核心逻辑脉络 1&#xff09;Anacanda使用CUDAPytorch2&#xff09;使用本地MNIST进行手写图片训练3&#xff09;…
阅读更多...
11-1.Android 项目结构 - androidTest 包与 test 包（单元测试与仪器化测试）

11-1.Android 项目结构 - androidTest 包与 test 包（单元测试与仪器化测试）

androidTest 包与 test 包 在 Android 项目中&#xff0c;androidTest 包与 test 包用于存放不同类型的测试代码的 1、测试类型 &#xff08;1&#xff09;androidTest 包 主要用于存放单元测试&#xff08;Unit Tests&#xff09;代码 单元测试是针对应用程序中的独立模块…
阅读更多...
HarmonyOS NEXT应用开发边学边玩系列：从零实现一影视APP (五、电影详情页的设计实现)

HarmonyOS NEXT应用开发边学边玩系列：从零实现一影视APP (五、电影详情页的设计实现)

在上一篇文章中&#xff0c;完成了电影列表页的开发。接下来&#xff0c;将进入电影详情页的设计实现阶段。这个页面将展示电影的详细信息&#xff0c;包括电影海报、评分、简介以及相关影人等。将使用 HarmonyOS 提供的常用组件&#xff0c;并结合第三方库 nutpi/axios 来实现…
阅读更多...
代码随想录day24 | 贪心算法理论基础 leetcode 455.分发饼干 376.摆动序列 53. 最大子序和

代码随想录day24 | 贪心算法理论基础 leetcode 455.分发饼干 376.摆动序列 53. 最大子序和

贪心算法理论基础 贪心算法是一种在每一步选择中都做出当前看起来最优的选择&#xff0c;从而期望通过局部最优解得到全局最优解的算法。贪心算法的基本思想是&#xff1a;在解决问题时&#xff0c;尽量选择当前最好的选项&#xff0c;最终达到全局最优解. 分发饼干 题目&am…
阅读更多...
如何禁用 PySpark 在运行时打印信息

如何禁用 PySpark 在运行时打印信息

我已经开始使用 PySpark。PySpark 的版本是3.5.4&#xff0c;它是通过 进行安装的pip。 这是我的代码&#xff1a; from pyspark.sql import SparkSession pyspark SparkSession.builder.master("local[8]").appName("test").getOrCreate() df pyspark…
阅读更多...
音视频入门基础：RTP专题（3）——SDP简介

音视频入门基础：RTP专题（3）——SDP简介

一、引言 会话描述协议&#xff08;Session Description Protocol&#xff0c;简称SDP&#xff09;描述了流媒体的初始化参数&#xff0c;包含音视频的编解码器、源地址和时间信息。SDP协议从不会被单独使用&#xff0c;而依赖于RTP和RTSP等协议。SDP也作为WebRTC的组件之一&a…
阅读更多...
论文高级GPT指令推荐

论文高级GPT指令推荐

一、科研选题与方向确认二、文献综述与整理 一、科研选题与方向确认 头脑风暴选题指令&#xff1a;Brainstorm potential research topics within [你的研究领域], focusing on areas with limited existing research and significant potential impact. For each topic, prov…
阅读更多...
基于Java的愤怒的小鸟游戏的设计与实现【源码+文档+部署讲解】

基于Java的愤怒的小鸟游戏的设计与实现【源码+文档+部署讲解】

目录 摘要 Abstract 1 绪论 1.1 游戏开发的背景 1.2 典型的Java游戏介绍 1.2.1 Minecraft介绍 1.2.2 Super Mario Bros介绍 1.2.3 The Sims介绍 1.3 游戏开发的意义 2 开发环境 2.1 开发语言 2.2 开发工具 2.3 JDK介绍 2.4 Java Awt介绍 2.5 Java Swing 介绍 2.…
阅读更多...
最新文章

Copyright @ 2022~2023