当前位置: 首页 > news >正文

手撕数据结构 —— 顺序表(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;
}

相关文章:

手撕数据结构 —— 顺序表(C语言讲解)

目录 1.顺序表简介 什么是顺序表 顺序表的分类 2.顺序表的实现 SeqList.h中接口总览 具体实现 顺序表的定义 顺序表的初始化 顺序表的销毁 打印顺序表 ​编辑 检查顺序表的容量 尾插 尾删 ​编辑 头插 头删 查找 在pos位置插入元素 删除pos位置的值 ​…...

女友学习前端第二天-笔记

2024/10/8笔记 表格 table 表格 tr 行 td 单元格内容 th 表头 第一行相当于h1 alignleft /center /right 对齐方式 应在table边上 比如<table alignleft> border 代表边框 也应在table边上 比如<table alignleft border"1"> cellpadding 单元外框与…...

电脑手机下载小米xiaomi redmi刷机包太慢 解决办法

文章目录 修改前下载速度修改后下载速度修改方法&#xff08;修改host&#xff09; 修改前下载速度 一开始笔者以为是迅雷没开会员的问题&#xff0c;在淘宝上买了一个临时会员后下载速度依然最高才100KB/s 修改后下载速度 修改方法&#xff08;修改host&#xff09; host文…...

Python中的策略模式:解锁编程的新维度

引言 策略模式是一种行为型设计模式&#xff0c;允许算法独立于使用它的客户端而变化。这使得我们可以根据不同的情况选择不同的算法或策略来解决问题&#xff0c;从而增强系统的灵活性。在日常开发中&#xff0c;策略模式常用于处理多种算法或行为之间的切换&#xff0c;比如…...

ara::core::Future::then()的概念和使用方法

1. 概念 在ara::core::Future的上下文中&#xff0c;then()是一种用于处理异步操作结果的机制。一个Future代表一个尚未完成的异步计算&#xff0c;它最终会产生一个结果或者一个错误。then()方法允许你在Future完成时注册一个回调函数&#xff08;或者说后续操作&#xff09;…...

九、5 USART串口数据包

数据包作用&#xff1a;把一个个单独的数据给打包起来&#xff0c;将同一批的数据进行打包和分割&#xff0c;方便接收方进行识别&#xff0c;方便我们进行多字节的数据通信。 1、串口收发HEX数据包 &#xff08;1&#xff09;数据包的格式是个人规定的&#xff0c;如以FF为包…...

SQL第12课——联结表

三点&#xff1a;什么是联结&#xff1f;为什么使用联结&#xff1f;如何编写使用联结的select语句 12.1 联结 SQL最强大的功能之一就是能在数据查询的执行中联结&#xff08;join)表。联结是利用SQL的select能执行的最重要的操作。 在使用联结前&#xff0c;需要了解关系表…...

CentOS7 虚拟机操作系统安装及相关配置教程

1、安装虚拟机 在VMware《主页》界面中点击《创建新的虚拟机》按钮&#xff1a; 选择你准备好的ISO文件&#xff0c;点击下一步&#xff1a; 然后填写虚拟机的名称以及虚拟机将来保存的位置&#xff1a; 再次下一步&#xff0c;填写虚拟机磁盘大小&#xff1a; 继续下一步&…...

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

创建脚本&#xff1a;WindowRoot.cs 编写脚本&#xff1a; 修改脚本&#xff1a;LoginWnd.cs 修改脚本&#xff1a;LoadingWnd.cs 修改脚本&#xff1a;ResSvc.cs 修改脚本&#xff1a;LoginSys.cs 运行项目 - 功能不变 本章结束...

04_23 种设计模式之《单例模式》

文章目录 一、单例模式基础知识单例模式有 3 个特点&#xff1a; 单例模式&#xff08;Singleton Pattern&#xff09;是一种创建型设计模式&#xff0c;它确保一个类只有一个实例&#xff0c;并提供一个全局访问点来获取这个实例。这种模式通常用于管理共享资源&#xff0c;如…...

视频加字幕用什么软件最快?12款工具快速添加字幕!

对于大多数同学来讲&#xff0c;剪辑中比较头疼的就是如何给视频加字幕和唱词啦&#xff0c;特别是用Pr或者FCXP等专业剪辑软件&#xff0c;加字幕也是特别费时的&#xff0c;哪怕是有批量添加的功能orz... 虽然关于这方面的内容已经很多啦&#xff0c;但是真正全面的内容还特…...

C++:string (用法篇)

文章目录 前言一、string 是什么&#xff1f;二、C语法补充1. auto2. 范围for 三、string类对象的常见构造1. Construct string object2. String destructor3. operator 四、string迭代器相关1. begin与end1&#xff09;begin2&#xff09;end3&#xff09;使用 2. rbegin 与 r…...

力扣随机题

最接近原点的K个点 题目 973. 最接近原点的 K 个点 - 力扣&#xff08;LeetCode&#xff09; 思路 这就是一道排序题&#xff0c;直接根据公式排序&#xff0c;然后返回对应范围的数组就行了 代码 public int[][] kClosest(int[][] points, int k) {Arrays.sort(points, n…...

CSS样式基础样式选择器(案例+代码实现+效果图)

目录 1.css样式的规则 2.引入css样式的方式 1)行内式 2)内嵌式 3)外链式 1-link导入 2-import导入 4)总 3.css基础选择器 1)标签选择器 案例&#xff1a;使用标签选择器编写一个圆 1.代码 2.效果 2)类选择器 案例&#xff1a;使用类选择器为div添加背景色 1.代码 2.效果 3)id…...

Linux系统编程—I/O缓冲区(C语言实现)

I/O缓冲区 进程的I/O缓冲区机制是计算机操作系统中一个重要的概念&#xff0c;它涉及到数据在内存和外设之间的传输。以下是关于进程的I/O缓冲区机制的详细解释&#xff1a; 1.定义与作用 定义&#xff1a;I/O缓冲区是指在内存里开辟的一块区域&#xff0c;用来存放接收用户输…...

MySQL多表查询:行子查询

先看我的表数据 dept表 emp表 行子查询 子查询返回的结果是一行&#xff08;可以是多列&#xff09;, 这种子查询称为行子查询 常用的操作符: , <>, IN, NOT IN 例子1. 查询与“张无忌” 的薪资及直属领导相同的员工信息 拆解成两个问题 a. 查询"张无忌"…...

.NET CORE程序发布IIS后报错误 500.19

发布IIS后浏览时报错误500.19&#xff0c;同时配置文件web.config的路径中也存在问号“?”。 可能原因&#xff1a;没有安装运行时...

Qt 6 相比 Qt 5 的主要提升与更新

自从 Qt 6 发布以来&#xff0c;作为 Qt 框架的一个重大版本更新&#xff0c;它在多个核心方面进行了深度优化和改进。与 Qt 5 相比&#xff0c;Qt 6 不仅提升了性能&#xff0c;还改进了对现代硬件和图形 API 的支持&#xff0c;并增强了开发者的工作流程。本文将详细介绍 Qt …...

【数据结构】介绍

介绍数据结构 数据结构是计算机科学中重要的概念&#xff0c;是指组织和管理数据的方式。它涉及到数据的存储、操作和访问等操作。数据结构可以分为线性结构、树形结构和图形结构等。 线性结构是最简单的数据结构之一(本玄也是这样觉得(*&#xffe3;▽&#xffe3;*))&#…...

论医疗类系统全国运营推广策略

一、线上推广 搜索引擎优化&#xff08;SEO&#xff09;- 重点策略 持续更新网站内容&#xff0c;包括系统功能介绍、成功案例、行业新闻等&#xff0c;提高网站的权重和流量。进行搜索引擎优化&#xff08;SEO&#xff09;&#xff0c;确定与医疗机构辅助系统相关的关键词&a…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...

【大厂机试题解法笔记】矩阵匹配

题目 从一个 N * M&#xff08;N ≤ M&#xff09;的矩阵中选出 N 个数&#xff0c;任意两个数字不能在同一行或同一列&#xff0c;求选出来的 N 个数中第 K 大的数字的最小值是多少。 输入描述 输入矩阵要求&#xff1a;1 ≤ K ≤ N ≤ M ≤ 150 输入格式 N M K N*M矩阵 输…...

linux设备重启后时间与网络时间不同步怎么解决?

linux设备重启后时间与网络时间不同步怎么解决&#xff1f; 设备只要一重启&#xff0c;时间又错了/偏了&#xff0c;明明刚刚对时还是对的&#xff01; 这在物联网、嵌入式开发环境特别常见&#xff0c;尤其是开发板、树莓派、rk3588 这类设备。 解决方法&#xff1a; 加硬件…...

华为OD机考- 简单的自动曝光/平均像素

import java.util.Arrays; import java.util.Scanner;public class DemoTest4 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint[] arr Array…...