手撕数据结构 —— 顺序表（C语言讲解）

目录

1.顺序表简介

什么是顺序表

顺序表的分类

2.顺序表的实现

SeqList.h中接口总览

具体实现

顺序表的定义

顺序表的初始化

顺序表的销毁

打印顺序表

​编辑 

检查顺序表的容量

尾插

尾删

​编辑 

头插

头删 

查找

在pos位置插入元素

删除pos位置的值

​编辑 

修改

3.完整代码附录

SeqList.h

SeqList.c

1.顺序表简介

什么是顺序表

顺序表是一种用物理地址连续的存储单元 依次存储数据元素的线性结构。

等等，物理地址连续的存储单元…… 这不就是我们在C语言中学习过的数组吗？是的，我们可以这样理解，顺序表的底层物理结构就是数组。需要注意的是，顺序表的底层物理结构是数组，并不是说顺序表就是数组。顺序表要求依次存储，也就是存储数据元素的时候，从第一个位置紧挨着存储，对顺序表进行增、删、改、查操作之后的顺序表也必须满足这一特性。

顺序表的分类

顺序表一般可以分为静态顺序表和动态顺序表。静态顺序表使用定长数组存储元素，动态顺序表使用动态开辟的数组存储元素。

静态顺序表示意图：

动态顺序表示意图：

 

静态顺序表只适用于存储空间大小明确的场景。如果静态顺序表的大小N定大了，就会造成空间的浪费，如果N定小了就会造成空间不够用。在实际应用中，我们很少能够确切的知道需要处理的数据元素的大小，所以，静态顺序表在实际应用中并不实用，现实中基本都是使用动态顺序表，根据需要动态的分配空间。

2.顺序表的实现

基于上述原因，我们实现动态顺序表。我们需要创建两个文件，分别是SeqList.h和SeqList.c，SeqList.h中用来存放接口的声明，SeqList.c中存放接口的定义。（文章末尾附完整代码）

SeqList.h中接口总览

实现顺序表，主要实现顺序表的增删改查，需要实现以下接口。

具体实现

顺序表的定义

我们定义的顺序表的底层物理空间为动态开辟的，用变量a指向这块空间，用变量size记录存储的有效数据的个数，用变量capacity表示容量空间的大小，当size == capacity的时候就需要进行扩容操作了。

顺序表的初始化

对于初始化操作，我们主要初始化struct SeqList结构体变量中的成员即可。

  • 对于最开始的容量可以根据实际需求动态设置即可；
  • size初始化为0，因为还没有向顺序表中添加元素。
  • capacity的初始值和动态申请的空间大小一致。

注意：

  • 我们初始化顺序表的时候，指向顺序表的指针不能为空，我们使用assert()函数暴力的检查，如果ps指针为空，程序就会崩溃。使用assert()函数的时候，需要包含头文件assert.h。
  • 我们还需要注意动态内存分配失败的情况，如果初始化的时候，动态分配内存失败，那么后面的程序都没有执行的必要了，我们使用exit()函数终止整个程序。使用exit()函数的时候，需要包含头文件stdlib.h。

后面的所有操作都需要判断指向顺序表的指针是否为空的情况（该指针不能为空！！！）

顺序表的销毁

销毁顺序表时，主要销毁的是struct SeqList结构体变量中的成员

  • 对于变量a，需要将变量a指向的空间释放，也就是把使用权归还给操作系统；并将a置为空，避免出现野指针。
  • 变量size和变量capacity置为0即可。

打印顺序表

直接循环打印即可。

 

检查顺序表的容量

当size == capacity的时候，说明顺序表的所有空间都用来存储有效元素了，当再次往顺序表中插入元素的时候，就没有空间了，需要扩容，我们选择2倍扩容。

  • 扩容的时候，我们选择realloc函数。该函数会自动的帮我们申请一块空间，同时将原数组中的内容拷贝至新数组中，并且释放旧的数组空间，返回新空间的起始地址。

几个注意点：

  • 检查realloc函数执行是否失败，如果失败，终止整个程序。
  • 返回的新空间的起始地址需要赋值给变量a，因为我们始终认为struct SeqList结构体变量中的成员a才是指向数组空间的。
  • 最后不要忘记放大变量capacity的值。

尾插

当进行插入操作的时候，我们需要判断顺序表的容量有没有满，如果满了就扩容，这一步可以复用我们前面实现的SLCheckCapacity()函数。

  • size表示有效元素的个数，作为下标的话就是有效元素的下一个位置。
  • 不要忘记将size++。

进行任何插入操作时，我们都需要先检查容量是否足够。通过复用SLCheckCapacity()函数即可。

可以看出顺序表尾插的时间复杂度是O(1)。

尾删

进行尾部删除元素的时候，我们可以直接让size--即可，因为size表示存储的有效元素的个数，当size--之后，最后一个元素就不是有效元素了，可以被覆盖。当然，你也可以将最后一个有效元素修改为指定值之后再进行size--操作，但这并没有什么意义。 

进行删除操作的时候，需要确保数组中存有有效元素。我们同样可以使用assert()函数进行暴力的检查。

 

可以看出顺序表尾删的时间复杂度也是O(1)。 

我们可以得出结论：顺序表在尾部进行插入和删除的效率非常高，时间复杂度都是O(1)，因此，顺序表适合进行尾插尾删操作。

注意：后面所有的删除操作都需要确保数组中存有有效元素。

头插

进行头部插入时，也就是在数组的最开始位置插入元素，我们需要将所有的有效元素向后移动一个位置，然后再插入元素。

 

可以看出顺序表头插的时间复杂度是O(N)，如果频繁大量的进行头插操作，效率将非常低下。 

头删 

进行头删操作时，只需要将除了第一个有效元素后面的元素都往前移动一个位置，然后进行size--操作即可。

可以看出顺序表头删的时间复杂度也是O(N)，如果频繁大量的进行头删操作，效率将非常低下。

我们可以得出结论：顺序表在头部进行插入和删除的时间复杂度都是O(N)，因此，顺序表不适合进行大量的头插、头删操作。

查找

在顺序表中查找元素的时候，只需要遍历顺序表即可，找到了就返回下标，没找到返回-1。-1不是合法的下标，当返回-1的时候，就表明查找的元素不存在。

在pos位置插入元素

在pos位置插入元素，只需要将pos位置以及pos位置之后的元素都向后移动一个位置，然后将pos位置的值覆盖即可。插入元素之后不要忘记将size++。

  • pos的取值必须合法，在插入数据的时候，pos可以是最后一个有效元素的下一个位置。

删除pos位置的值

删除pos位置的值只需要将pos之后的有效元素都向前挪动一个位置，然后将size--即可。

  • 删除pos位置的值的时候也需要注意pos的取值，此时，pos的取值不能是有效元素的下一个位置。

 

修改

进行修改操作时，我们只需要将指定位置的值修改即可。

值得一提的是，直接使用赋值语句就能修改，为什么还需要封装成函数呢？

  • 因为我们封装的函数有严格的边界检查。
  • 直接赋值使用的 [ ] 并没有严格的边界检查，[ ] 的下标检查是一种抽查机制，不能保证准确的发现越界问题。 

3.完整代码附录

SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>// 定义动态顺序表
typedef int SLDataType;typedef struct SeqList
{SLDataType* a;   // 指向动态开辟的数组空间int size;        // 存储有效数据个数int capacity;    // 空间大小
}SL;// 初始化
void SLInit(SL* ps);
// 销毁
void SLDestroy(SL* ps);
// 打印
void SLPrint(SL* ps);
// 容量检查
void SLCheckCapacity(SL* ps);// 头插
void SLPushBack(SL* ps, SLDataType x);
// 头删
void SLPopBack(SL* ps);
// 尾插
void SLPushFront(SL* ps, SLDataType x);
// 尾删
void SLPopFront(SL* ps);// 返回下标，没有找打返回-1
int SLFind(SL* ps, SLDataType x);// 在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);// 删除pos位置的值
void SLErase(SL* ps, int pos);// 修改pos位置的元素
void SLModify(SL* ps, int pos, SLDataType x);

SeqList.c

#include"SeqList.h"// 初始化 
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);if (ps->a == NULL){perror("malloc failed");exit(-1);}ps->size = 0;ps->capacity = 4;
}// 销毁 
void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}// 打印 
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}// 容量检查 
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity *= 2;}
}// 尾插 
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}// 尾删 
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);ps->size--;
}// 头插 
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++;
}// 头删 
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--;
}// 查找 
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;
}// 在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);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位置的值
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}// 修改 
void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->a[pos] = x;
}

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

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

相关文章

【JavaEE】【多线程】Thread类讲解

【JavaEE】【多线程】Thread类讲解

目录 Thread构造方法Thread 的常见属性创建一个线程获取当前线程引用终止一个线程使用标志位使用自带的标志位 等待一个线程线程休眠线程状态线程安全线程不安全原因总结解决由先前线程不安全问题例子 Thread构造方法 方法说明Thread()创建线程对象Thread(Runnable target)使用…
阅读更多...
初始Redis

初始Redis

Mysql最大的问题在于,访问速度比较慢 而Redis是内存中存储数据的中间件,可以作为数据库使用,比较快,和Mysql相比,存储空间有限 Redis是在分布式系统中,才能发挥威力的,在单机程序,直接通过变量存储数据的方式,是比使用redis更优的选择 那么要求更大更快,就可以把redis和mysq…
阅读更多...
修改银河麒麟操作系统V10（SP1）网卡名称为ethx

修改银河麒麟操作系统V10（SP1）网卡名称为ethx

修改银河麒麟桌面操作系统V10&#xff08;SP1&#xff09;网卡名称为ethx 步骤一&#xff1a;查看当前网卡信息步骤二&#xff1a;修改GRUB配置文件步骤三&#xff1a;更新GRUB配置步骤四&#xff1a;编辑网络接口文件步骤五&#xff1a;重启机器 &#x1f496;The Begin&#…
阅读更多...
【Kubernetes】常见面试题汇总（五十五）

【Kubernetes】常见面试题汇总（五十五）

目录 121. POD 创建失败&#xff1f; 122. POD 的 ready 状态未进入&#xff1f; 特别说明&#xff1a; 题目 1-68 属于【Kubernetes】的常规概念题&#xff0c;即 “ 汇总&#xff08;一&#xff09;~&#xff08;二十二&#xff09;” 。 题目 69-113 属于【Kube…
阅读更多...
数据结构-排序1

数据结构-排序1

1.排序的概念 排序&#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性&#xff1a;假定在待排序的记录序列中&#xff0c;存在多个具有相同的关键字的记录&#xff0c;若经过排序…
阅读更多...
【项目安全设计】软件系统安全设计规范和标准（doc原件）

【项目安全设计】软件系统安全设计规范和标准（doc原件）

1.1安全建设原则 1.2 安全管理体系 1.3 安全管理规范 1.4 数据安全保障措施 1.4.1 数据库安全保障 1.4.2 操作系统安全保障 1.4.3 病毒防治 1.5安全保障措施 1.5.1实名认证保障 1.5.2 接口安全保障 1.5.3 加密传输保障 1.5.4终端安全保障 资料获取&#xff1a;私信或者进主页。…
阅读更多...
『网络游戏』窗口基类【06】

『网络游戏』窗口基类【06】

创建脚本&#xff1a;WindowRoot.cs 编写脚本&#xff1a; 修改脚本&#xff1a;LoginWnd.cs 修改脚本&#xff1a;LoadingWnd.cs 修改脚本&#xff1a;ResSvc.cs 修改脚本&#xff1a;LoginSys.cs 运行项目 - 功能不变 本章结束
阅读更多...
【数据管理】DAMA-元数据专题

【数据管理】DAMA-元数据专题

导读&#xff1a;元数据是关于数据的组织、数据域及其关系的信息&#xff0c;是描述数据的数据。在数据治理中&#xff0c;元数据扮演着至关重要的角色&#xff0c;是数据治理的基础和支撑。以下是对数据治理中元数据专题方案的详细介绍&#xff1a; 目录 一、元数据的重要性 …
阅读更多...
Qt教程（001）：Qt概述与安装

Qt教程（001）：Qt概述与安装

文章目录 一、Qt概述1.1 什么是Qt1.2 Qt优点1.3 Qt发展史1.4 支持的平台1.5 成功案例1.6 下载安装1.7 QtCreator介绍 一、Qt概述 1.1 什么是Qt Qt是一个跨平台的C图形用户界面应用程序框架。它为应用程序开发者提供建立艺术级图形界面所需的所有功能。它是完全面向对象的&…
阅读更多...
如何高效使用Prompt与AI大模型对话

如何高效使用Prompt与AI大模型对话

一、如何与人工智能对话 在人工智能的世界里&#xff0c;提示词&#xff08;Prompt&#xff09;就像是一把钥匙&#xff0c;能够解锁AI智能助手的潜力&#xff0c;帮助你更高效地获取信息、解决问题。但如何正确使用这把钥匙&#xff0c;却是一门艺术。本文将带你了解提示词的…
阅读更多...
如何通过视觉分析检测车辆逆行行为

如何通过视觉分析检测车辆逆行行为

随着交通网络的快速扩展和车辆数量的持续增加&#xff0c;城市交通管理面临着前所未有的挑战。交通事故的多发原因之一是车辆逆行&#xff0c;这种行为不仅严重威胁其他车辆和行人的安全&#xff0c;也加重了交通拥堵问题。因此&#xff0c;如何有效监控并预防车辆逆行成为城市…
阅读更多...
【Verilog学习日常】—牛客网刷题—Verilog进阶挑战—VL45

【Verilog学习日常】—牛客网刷题—Verilog进阶挑战—VL45

异步FIFO 描述 请根据题目中给出的双口RAM代码和接口描述&#xff0c;实现异步FIFO&#xff0c;要求FIFO位宽和深度参数化可配置。 电路的接口如下图所示。 双口RAM端口说明&#xff1a; 端口名 I/O 描述 wclk input 写数据时钟 wenc input 写使能 waddr input 写…
阅读更多...
用 LoRA 微调 Stable Diffusion：拆开炼丹炉，动手实现你的第一次 AI 绘画

用 LoRA 微调 Stable Diffusion：拆开炼丹炉，动手实现你的第一次 AI 绘画

总得拆开炼丹炉看看是什么样的。这篇文章将带你从代码层面一步步实现 AI 文本生成图像&#xff08;Text-to-Image&#xff09;中的 LoRA 微调过程&#xff0c;你将&#xff1a; 了解 Trigger Words&#xff08;触发词&#xff09;到底是什么&#xff0c;以及它们如何影响生成结…
阅读更多...
计组与体系软题1-数据表示与校验码

计组与体系软题1-数据表示与校验码

一、数的编码方式 题1-0的表示 题2-补码的补码原码 1. 这道题涉及到数的编码范围和进制转换2. 题3-采用补码的目的 二、编码范围 题1-补码的表示范围(-2^(n-1)~2 ^(n-1)-1) n是字长/位数&#xff0c;2^7128&#xff0c;范围为-128~127题2-原码范围&#xff08;-2^&#xff0…
阅读更多...
LORD-GX5-45 ROS安装

LORD-GX5-45 ROS安装

1、驱动安装 https://github.com/LORD-MicroStrain/MSCL 上述下载 x64:C&#xff0c;在下载完的deb文件下执行 sudo dpkg -i <PACKAGE_NAME>.deb #install MSCL sudo apt install -f #install dependencies2、源码安装 #新建工作空间 mkdir -p ~…
阅读更多...
【C++】认识匿名对象

【C++】认识匿名对象

文章目录 目录 文章目录前言一、对匿名对象的解读二、匿名对象的对象类型三、匿名对象的使用总结 前言 在C中&#xff0c;匿名对象是指在没有呗命名的情况下创建的临时对象。它们通常在单个语句中执行一系列操作或调用某个函数&#xff0c;并且不需要将结果存放进变量中。 匿名…
阅读更多...
【STM32单片机_(HAL库)】4-2-1【定时器TIM】定时器输出PWM实现呼吸灯实验

【STM32单片机_(HAL库)】4-2-1【定时器TIM】定时器输出PWM实现呼吸灯实验

1.硬件 STM32单片机最小系统LED灯模块 2.软件 pwm驱动文件添加定时器HAL驱动层文件添加GPIO常用函数定时器输出PWM配置步骤main.c程序 #include "sys.h" #include "delay.h" #include "led.h" #include "pwm.h"int main(void) {HA…
阅读更多...
音视频入门基础：FLV专题（13）——FFmpeg源码中，解析任意Type值的SCRIPTDATAVALUE类型的实现

音视频入门基础：FLV专题（13）——FFmpeg源码中，解析任意Type值的SCRIPTDATAVALUE类型的实现

一、SCRIPTDATAVALUE类型 从《音视频入门基础&#xff1a;FLV专题&#xff08;9&#xff09;——Script Tag简介》中可以知道&#xff0c;根据《video_file_format_spec_v10_1.pdf》第80到81页&#xff0c;SCRIPTDATAVALUE类型由一个8位&#xff08;1字节&#xff09;的Type和…
阅读更多...
动态代理有用吗？一文了解靠谱的动态代理有哪些标准

动态代理有用吗？一文了解靠谱的动态代理有哪些标准

在当今互联网时代中&#xff0c;从网络安全、隐私保护、市场调研和互联网营销到软件测试、缓存管理和数据库连接&#xff0c;用户为了更好地完成此类工作&#xff0c;往往会使用动态代理&#xff0c;那么进一步了解动态代理、明确动态代理的使用场景和选择标准则是十分有必要的…
阅读更多...
OJ在线评测系统 后端微服务架构 注册中心 Nacos入门到启动

OJ在线评测系统 后端微服务架构 注册中心 Nacos入门到启动

注册中心 服务架构中的注册中心是一个关键组件&#xff0c;用于管理和协助微服务之间的通信。注册中心的主要职责是服务的注册和发现&#xff0c;确保各个微服务能够相互找到并进行调用。 主要功能&#xff1a; 服务注册&#xff1a;微服务在启动时&#xff0c;将自身信息&am…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023