探索数据结构：深入了解顺序表的奥秘


✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 什么是顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，它与数组非常类似，但是相比于数组顺序表有一个非常明显的优点——可以动态内存增长空间大小

2. 顺序表的功能

顺序表可以大致包含以下几个功能：

  1. 初始化顺序表中的数据。

  2. 打印顺序表中的数据。

  3. 对顺序表进行尾插(末尾插入数据)。

  4. 对顺序表中数据进行尾删(末尾删除数据)。

3. 顺序表的定义

定义顺序表我们首先需要一个动态内存开辟的空间，当前数据的个数(size)，以及方便扩容的容量大小(capacity)。

typedef int SLDataType; //类型重命名，方便后续修改类型
#define N 4 //初始化空间大小
typedef struct SeqList
{SLDataType* a;    //指向动态开辟的数组size_t size;      //有效数据个数size_t capacity;  //容量大小
}SeqList;

4. 功能的具体实现

4.1 初始化顺序表

(1) 代码实现

初始化顺序表时我们可以先开辟四个空间，之后不够再进行扩容。

void SeqListInit(SeqList* p)
{assert(p);  //断言p->a =(SLDataType*)malloc(N*sizeof(SLDataType));  //初始顺序表为四个空间if (p == NULL){perror("malloc fail:");return ;}p->size = 0;  //初始数据个数为0p->capacity = 4;  //初始空间容量为4
}
(2) 复杂度分析
  • 时间复杂度：由于没有其他未知数的引入，所以所需时间是个常数，也就是O(1)。
  • 空间复杂度：动态开辟N个空间，所以空间复杂度为O(N)。

4.2 打印数据

(1) 代码实现

打印数据只用循环打印就可以了。

void SeqListPrint(const SeqList* p)
{assert(p);  //断言if (p->size == 0)  //判断顺序表是否为空{printf("顺序表为空\n");return;}int i = 0;for (i = 0; i < p->size; i++)  //打印顺序表{printf("%d ", p->a[i]);}printf("\n");
}
(2) 复杂度分析
  • 时间复杂度：因为会打印顺序表中的所有数据，所以时间复杂度为O(N)。
  • 空间复杂度：打印顺序表并不需要开辟格外的空间，所以空间复杂度为O(N)。

4.3 尾插数据

尾插数据，顾名思义就是在顺序表末尾插入数据，在插入数据之前我们应该检查顺序表是否为满。

(1) 检查是否已满
void CheckCapacity(SeqList* p)
{assert(p);  //断言if (p->size == p->capacity)  //检查容量，满了则增容{size_t newcapacity = 2 * p->capacity;  //，扩容为原来的2倍SLDataType* prt = (SLDataType*)realloc(p->a, newcapacity * sizeof(SLDataType));  //扩容if (prt == NULL){perror("realloc fail:");return ;}p->a = prt;  // prt不为空，开辟成功p->capacity = newcapacity;  //更新容量}
}
(2) 插入数据
void SeqListPushBack(SeqList* p, SLDataType x)
{assert(p);  //断言CheckCapacity(p);  //检查顺序表容量是否已满p->a[p->size] = x;  //尾插数据p->size++;  //有效数据个数+1
}
(3) 复杂度分析
  • 时间复杂度：没有变量影响时间，时间复杂度为O(1)。
  • 空间复杂度：以最坏的情况考虑，会进行扩容，空间复杂度为O(N)。

4.4 尾删数据

同理，尾删数据就是删除顺序表中最后一个元素，我们只需将size–。注意：删除之前要保证顺序表中有数据。

(1) 代码实现
void SeqListPopBack(SeqList* p)
{assert(p);  //断言assert(p->size > 0);  //顺序表不能为空p->size--;  //有效数据个数-1
}
(2) 复杂度分析
  • 时间复杂度：没有变量影响时间，时间复杂度为O(1)。
  • 空间复杂度：没有变量影响空间，空间复杂度为O(N)。

4.5 头插数据

头部插入数据就是在第一个元素位置插入一个元素。

(1) 代码实现
void SeqListPushFront(SeqList* p, SLDataType x)
{assert(p);  //断言CheckCapacity(p);  //检查顺序表容量是否已满int i = 0;for (i = p->size - 1; i >= 0; i--)  //顺序表中[0,size-1]的元素依次向后挪动一位{p->a[i + 1] = p->a[i];}p->a[0] = x;  //头插数据p->size++;  //有效数据个数+1
}
(2) 复杂度分析
  • 时间复杂度：因为从头部插入数据，后续数据需要依次覆盖，所以时间复杂度为O(N)。
  • 空间复杂度：因为可能会进行扩容，按最坏的情况来算，空间复杂度为O(N)。

4.5 头删数据

从头部删除数据，与尾部删除数据不同，需要依次往前覆盖。

(1) 代码实现
void SeqListPopFront(SeqList* p)
{assert(p);  //断言assert(p->size > 0);  //顺序表不能为空int i = 0;for (i = 1; i < p->size; i++)  //顺序表中[1,size-1]的元素依次向前挪动一位{p->a[i - 1] = p->a[i];}p->size--;  //有效数据个数-1
}
(2) 复杂度分析
  • 时间复杂度：因为需要往前覆盖数据，所以时间复杂度自然为O(N)。
  • 空间复杂度：因为并没有开辟其他空间，所以空间复杂度为O(1)。

4.6 查找指定值

根据输入参数，在顺序表中查找指定的值并返回其下标，若未找到则返回-1。

(1) 代码实现
int SeqListFind(const SeqList* p, SLDataType x)
{assert(p);  //断言int i = 0;for (i = 0; i < p->size; i++){if (p->a[i] == x){return i;  //查找到，返回该值在数组中的下标}}return -1;  //没有查找到
}
(2) 复杂度分析
  • 时间复杂度：以最坏的情况分析，时间复杂度为O(N)。
  • 空间复杂度：并没有格外的空间消耗，空间复杂度为O(1)。

4.7 指定位置修改

我们可以通过指定下标或者查找指定值的下标来修改任意位置的值。

(1) 代码实现
void SeqListModify(SeqList* p, int pos, SLDataType x)
{assert(p);  //断言assert(p->size > 0);  //顺序表不能为空assert(pos >= 0 && pos < p->size);  //检查pos下标的合法性p->a[pos] = x;  //修改pos下标处对应的数据
}
(2) 复杂度分析
  • 时间复杂度：因为是通过指定下标修改，所以时间复杂度为O(1)。
  • 空间复杂度：没有开辟额外的空间，所以空间复杂度为O(1)。

4.8 指定位置插入

和前面其他插入一样，指定位置插入也需要判断是否扩容。

(1) 代码实现
void SeqListInsert(SeqList* p, int pos, SLDataType x)
{assert(p);//断言assert(pos <= p->size); //检查pos下标的合法性SeqListCheck(p);//扩容int cur = p->size;while (cur > pos){p->a[cur] = p->a[cur - 1];//覆盖--cur;}p->a[pos] = x;p->size++;
}
(2) 复杂度分析
  • 时间复杂度：需要依次覆盖，时间复杂度为O(N)。
  • 空间复杂度：可能需要扩容，空间复杂度为O(N)。

4.9 指定位置删除

和前面的删除差不多，但是指定删除可能会依次覆盖。

(1) 代码实现
void SeqListErase(SeqList* p, int pos)
{assert(p);  //断言assert(p->size > 0);  //顺序表不能为空assert(pos >= 0 && pos < p->size);  //检查pos下标的合法性int i = 0;for (i = pos + 1; i < p->size; i++)  //将pos位置后面的数据依次向前挪动一位{p->a[i - 1] = p->a[i];}p->size--;  //有效数据个数-1
}
(2) 复杂度分析
  • 时间复杂度：需要依次覆盖，时间复杂度为O(N)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.10 回收空间

在结束操作之后，需要释放开辟的空间，以防止内存泄漏。

(1) 代码实现
void SeqListDestory(SeqList* p)
{assert(p);  //断言free(p->a);   //释放动态开辟的空间p->a = NULL;  //置空p->size = 0;  //数据个数置0p->capacity = 0;  //空间容量大小置0
}
(2) 复杂度分析
  • 时间复杂度：没有额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

5. 完整代码

5.1 SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 4 //初始化空间大小
typedef int SLDataType; //类型重命名，方便后续修改类型
typedef struct SeqList
{SLDataType* a;    //指向动态开辟的数组size_t size;      //有效数据个数size_t capacity;  //容量大小
}SeqList;void SeqListInit(SeqList* p);//初始化顺序表
void SeqListPrint(const SeqList* p);//打印顺序表
void SeqListPushBack(SeqList* p, SLDataType x);//尾插
void SeqListPopBack(SeqList* p);//尾删
void SeqListPushFront(SeqList* p, SLDataType x);//头插
void SeqListPopFront(SeqList* p);//头删
int SeqListFind(const SeqList* p, SLDataType x);//查找数据
void SeqListModify(SeqList* p, int pos, SLDataType x);//修改数据
void SeqListInsert(SeqList* p, int pos, SLDataType x);//指定插入
void SeqListErase(SeqList* p, int pos);//指定删除
void SeqListDestory(SeqList* p);//释放空间

5.2 SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListInit(SeqList* p)
{assert(p);  //断言p->a =(SLDataType*)malloc(N*sizeof(SLDataType));  //初始顺序表为四个空间if (p == NULL){perror("malloc fail:");return ;}p->size = 0;  //初始数据个数为0p->capacity = 4;  //初始空间容量为4
}
void CheckCapacity(SeqList* p)
{assert(p);  //断言if (p->size == p->capacity)  //检查容量，满了则增容{size_t newcapacity = 2 * p->capacity;  //，扩容为原来的2倍SLDataType* prt = (SLDataType*)realloc(p->a, newcapacity * sizeof(SLDataType));  //扩容if (prt == NULL){perror("realloc");return ;}p->a = prt;  // prt不为空，开辟成功p->capacity = newcapacity;  //更新容量}
}
void SeqListPushBack(SeqList* p, SLDataType x)
{assert(p);  //断言CheckCapacity(p);  //检查顺序表容量是否已满p->a[p->size] = x;  //尾插数据p->size++;  //有效数据个数+1
}
void SeqListPrint(const SeqList* p)
{assert(p);  //断言if (p->size == 0)  //判断顺序表是否为空{printf("顺序表为空\n");return;}int i = 0;for (i = 0; i < p->size; i++)  //打印顺序表{printf("%d ", p->a[i]);}printf("\n");
}
void SeqListPopBack(SeqList* p)
{assert(p);  //断言assert(p->size > 0);  //顺序表不能为空p->size--;  //有效数据个数-1
}
void SeqListPushFront(SeqList* p, SLDataType x)
{assert(p);  //断言CheckCapacity(p);  //检查顺序表容量是否已满int i = 0;for (i = p->size - 1; i >= 0; i--)  //顺序表中[0,size-1]的元素依次向后挪动一位{p->a[i + 1] = p->a[i];}p->a[0] = x;  //头插数据p->size++;  //有效数据个数+1
}
void SeqListPopFront(SeqList* p)
{assert(p);  //断言assert(p->size > 0);  //顺序表不能为空int i = 0;for (i = 1; i < p->size; i++)  //顺序表中[1,size-1]的元素依次向前挪动一位{p->a[i - 1] = p->a[i];}p->size--;  //有效数据个数-1
}
int SeqListFind(const SeqList* p, SLDataType x)
{assert(p);  //断言int i = 0;for (i = 0; i < p->size; i++){if (p->a[i] == x){return i;  //查找到，返回该值在数组中的下标}}return -1;  //没有查找到
}
void SeqListModify(SeqList* p, int pos, SLDataType x)
{assert(p);  //断言assert(p->size > 0);  //顺序表不能为空assert(pos >= 0 && pos < p->size);  //检查pos下标的合法性p->a[pos] = x;  //修改pos下标处对应的数据
}
void SeqListInsert(SeqList* p, int pos, SLDataType x)
{assert(p);//断言assert(pos <= p->size); //检查pos下标的合法性SeqListCheck(p);//扩容int cur = p->size;while (cur > pos){p->a[cur] = p->a[cur - 1];//覆盖--cur;}p->a[pos] = x;p->size++;
}
void SeqListErase(SeqList* p, int pos)
{assert(p);  //断言assert(p->size > 0);  //顺序表不能为空assert(pos >= 0 && pos < p->size);  //检查pos下标的合法性int i = 0;for (i = pos + 1; i < p->size; i++)  //将pos位置后面的数据依次向前挪动一位{p->a[i - 1] = p->a[i];}p->size--;  //有效数据个数-1
}
void SeqListDestory(SeqList* p)
{assert(p);  //断言free(p->a);   //释放动态开辟的空间p->a = NULL;  //置空p->size = 0;  //数据个数置0p->capacity = 0;  //空间容量大小置0
}

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

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

相关文章

小白水平理解面试经典题目leetcode 606. Construct String from Binary Tree【递归算法】

小白水平理解面试经典题目leetcode 606. Construct String from Binary Tree【递归算法】

Leetcode 606. 从二叉树构造字符串 题目描述 例子 小白做题 坐在自习室正在准备刷题的小白看到这道题&#xff0c;想想自己那可是没少和白月光做题呢&#xff0c;也不知道小美刷题刷到哪里了&#xff0c;这题怎么还没来问我&#xff0c;难道是王谦谦去做题了&#xff1f; 这…
阅读更多...
Mac安装Appium

Mac安装Appium

一、环境依赖 一、JDK环境二、Android-SDK环境&#xff08;android自动化&#xff09;三、Homebrew环境四、Nodejs 安装cnpm 五、安装appium六、安装appium-doctor来确认安装环境是否完成七、安装相关依赖 二、重头大戏&#xff0c; 配置wda&#xff08;WebDriverAgent&#x…
阅读更多...
Unity（第九部）物体类

Unity（第九部）物体类

拿到物体的某些数据 using System.Collections; using System.Collections.Generic; using UnityEngine;public class game : MonoBehaviour {// Start is called before the first frame updatevoid Start(){//拿到当前脚本所挂载的游戏物体//GameObject go this.gameObject;…
阅读更多...
Windows 11 23H2 based Tiny11 2311 中文输入法出错

Windows 11 23H2 based Tiny11 2311 中文输入法出错

参考&#xff1a; 1&#xff1a; Chinese IME dictionaries shows "not ready yet" in Windows Server 2022 - Windows Server | Microsoft Learn 2&#xff1a; Chinese basic typing not completing download - Microsoft Community 安装了 Tiny11 2311&#xff…
阅读更多...
Pycharm的下载安装与汉化

Pycharm的下载安装与汉化

一.下载安装包 1.接下来按照步骤来就行 2.然后就能在桌面上找到打开了 3.先建立一个文件夹 二.Pycharm的汉化
阅读更多...
13. Springboot集成Protobuf

13. Springboot集成Protobuf

目录 1、前言 2、Protobuf简介 2.1、核心思想 2.2、Protobuf是如何工作的&#xff1f; 2.3、如何使用 Protoc 生成代码&#xff1f; 3、Springboot集成 3.1、引入依赖 3.2、定义Proto文件 3.3、Protobuf生成Java代码 3.4、配置Protobuf的序列化和反序列化 3.5、定义…
阅读更多...
【深入了解设计模式】组合设计模式

【深入了解设计模式】组合设计模式

组合设计模式 组合模式是一种结构型设计模式&#xff0c;它允许你将对象组合成树状结构来表现“整体-部分”关系。组合模式使得客户端可以统一对待单个对象和组合对象&#xff0c;从而使得代码更加灵活和易于扩展。 概述 ​ 对于这个图片肯定会非常熟悉&#xff0c;上图我们可…
阅读更多...
qt波位图

qt波位图

1&#xff0c;QPainter 绘制&#xff0c;先绘制这一堆蓝色的东西, 2&#xff0c;在用定时器&#xff1a;QTimer&#xff0c;配合绘制棕色的圆。用到取余&#xff0c;取整 #pragma once#include <QWidget> #include <QPaintEvent>#include <QTimer>QT_BEGIN_…
阅读更多...
OpenAI划时代大模型——文本生成视频模型Sora作品欣赏（十三）

OpenAI划时代大模型——文本生成视频模型Sora作品欣赏（十三）

Sora介绍 Sora是一个能以文本描述生成视频的人工智能模型&#xff0c;由美国人工智能研究机构OpenAI开发。 Sora这一名称源于日文“空”&#xff08;そら sora&#xff09;&#xff0c;即天空之意&#xff0c;以示其无限的创造潜力。其背后的技术是在OpenAI的文本到图像生成模…
阅读更多...
gofly框架接口入参验证使用介绍

gofly框架接口入参验证使用介绍

接口传入的参数做相关性质验证是开发中较为常用&#xff0c;gofly框架内置校验工具&#xff0c;提供开发效率&#xff0c;开发接口简单调用即可实现验证&#xff0c;下面介绍gofly框架数据验证设计思路及使用方法。 gofly框架提供了功能强大、使用便捷、灵活易扩展的数据/表单…
阅读更多...
C++：菱形继承问题

C++：菱形继承问题

目录 1、什么是菱形继承 2、虚拟继承 3、一些常见问题 1. 什么是菱形继承&#xff1f;菱形继承的问题是什么&#xff1f; 2. 什么是菱形虚拟继承&#xff1f;如何解决数据冗余和二义性的 3. 继承和组合的区别&#xff1f;什么时候用继承&#xff1f;什么时候用组合&#…
阅读更多...
Http基础之http协议、无状态协议、状态码、http报文、跨域-cors

Http基础之http协议、无状态协议、状态码、http报文、跨域-cors

Http基础 HTTP基础HTTP协议请求方法持久连接管线化 无状态协议使用Cookie状态管理 状态码1XX2XX OK200 OK204 NO Content206 Content-Range 3XX 重定向301302304307 4XX400401403404 5XX500503 HTTP报文请求报文响应报文通用首部字段Cache-ControlConnectionDate请求首部字段Ac…
阅读更多...
19.2 DeepMetricFi:基于深度度量学习改进Wi-Fi指纹定位

19.2 DeepMetricFi:基于深度度量学习改进Wi-Fi指纹定位

P. Chen and S. Zhang, "DeepMetricFi: Improving Wi-Fi Fingerprinting Localization by Deep Metric Learning," in IEEE Internet of Things Journal, vol. 11, no. 4, pp. 6961-6971, 15 Feb.15, 2024, doi: 10.1109/JIOT.2023.3315289. 摘要 Wi-Fi RSSI指纹定位…
阅读更多...
RISC-V特权架构 - 特权模式与指令

RISC-V特权架构 - 特权模式与指令

RV32/64 特权架构 - 特权模式与指令 1 特权模式2 特权指令2.1 mret&#xff08;从机器模式返回到先前的模式&#xff09;2.2 sret&#xff08;从监管模式返回到先前的模式&#xff09;2.3 wfi&#xff08;等待中断&#xff09;2.4 sfence.vma&#xff08;内存屏障&#xff09; …
阅读更多...
【MySQL】数据库的操作

【MySQL】数据库的操作

【MySQL】数据库的操作 目录 【MySQL】数据库的操作创建数据库数据库的编码集和校验集查看系统默认字符集以及校验规则查看数据库支持的字符集查看数据库支持的字符集校验规则校验规则对数据库的影响数据库的删除 数据库的备份和恢复备份还原不备份整个数据库&#xff0c;而是备…
阅读更多...
算法------（13）KMP

算法------（13）KMP

例题&#xff1a;&#xff08;1&#xff09;AcWing 831. KMP字符串 。。其实写完也不太理解。。随便写点吧 KMP就是求next数组和运用next的数组的过程。相比传统匹配模式一次更新一单位距离的慢速方法&#xff0c;next数组可以让下表字符串一次更新n - next【n】个距离&#x…
阅读更多...
【研发日记】Matlab/Simulink技能解锁(三)——在Stateflow编辑窗口Debug

【研发日记】Matlab/Simulink技能解锁(三)——在Stateflow编辑窗口Debug

文章目录 前言 State断点 Transition断点 条件断点 按State步进 Watch Data Value Sequence Viewer 分析和应用 总结 前言 见《【研发日记】Matlab/Simulink技能解锁(一)——在Simulink编辑窗口Debug》 见《【研发日记】Matlab/Simulink技能解锁(二)——在Function编辑…
阅读更多...
C++之类和对象(2)

C++之类和对象(2)

目录 1.类的6个默认成员函数 2. 构造函数 2.1 概念 2.2 特性 3.析构函数 3.1 概念 3.2 特性 4. 拷贝构造函数 4.1 概念 4.2 特征 5.赋值运算符重载 5.1 运算符重载 5.2 赋值运算符重载 2. 赋值运算符只能重载成类的成员函数不能重载成全局函数 3. 用户没有显式实现时&…
阅读更多...
Flink CDC 提取记录变更时间作为事件时间和 Hudi 表的 precombine.field 以及1970-01-01 取值问题

Flink CDC 提取记录变更时间作为事件时间和 Hudi 表的 precombine.field 以及1970-01-01 取值问题

博主历时三年精心创作的《大数据平台架构与原型实现&#xff1a;数据中台建设实战》一书现已由知名IT图书品牌电子工业出版社博文视点出版发行&#xff0c;点击《重磅推荐&#xff1a;建大数据平台太难了&#xff01;给我发个工程原型吧&#xff01;》了解图书详情&#xff0c;…
阅读更多...
深入剖析k8s-控制器思想

深入剖析k8s-控制器思想

引言 本文是《深入剖析Kubernetes》学习笔记——《深入剖析Kubernetes》 正文 控制器都遵循K8s的项目中一个通用的编排模式——控制循环 for {实际状态 : 获取集群中对象X的实际状态期望状态 : 获取集群中对象X的期望状态if 实际状态 期望状态 {// do nothing} else {执行…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023