【C进阶】顺序表详解

请添加图片描述

文章目录

  • 📝线性表的概念
  • 🌠 顺序表
    • 🌉顺序表的概念
  • 🌠声明--接口
    • 🌉启动
      • 🌠初始化
      • 🌉扩容
      • 🌠尾插
      • 🌉 打印
      • 🌠销毁
      • 🌉 尾删
      • 🌠头插
      • 🌉 头删
  • 🌠指定位置插入数据
    • 🌉删除指定位置数据
  • 🌠查找
    • 🌉修改
  • 🚩总结

📝线性表的概念

线性表是一种常见的抽象数据类型：线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述

顺序表：逻辑结构是线性的，物理结构是连续的

🌠 顺序表

🌉顺序表的概念

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

顺序表是一种线性表数据结构。顺序表和数组的区别：顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝
顺序表分类：

  1. 静态顺序表：使⽤定⻓数组存储元素【缺陷：空间给少了不够⽤，给多了造成空间浪费】
    在这里插入图片描述
  2. 动态顺序表：使用动态开辟的数组存储
    在这里插入图片描述

🌠声明–接口

静态顺序表：给定的数组长度，若不够，会导致后续的数据保存失败，导致数据丢失，给多了，会导致空间大量浪费。
因此推荐使用动态顺序表，动态顺序表的长度可以动态增长,不需要预先指定表长。常见的动态顺序表实现包括:向量(Vector)、数组列表(ArrayList)等。它们内部使用动态数组实现自动扩容机制。
本文实现动态顺序表。
接口函数是指定义在接口(interface)中的函数。
接口是一种抽象类型,它定义了一组函数原型而不提供具体实现。接口函数就是这组函数原型。
我们将创建在seqList.h文件，因此我们在每一个文件要使用直接包含该头文件就可以使用了。
接口如下：

//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);//保持接口一致性// 扩容
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);//查找/修改
int SLFind(SL* ps, SLDataType x);
void SLModify(SL* ps, int pos, SLDatatype x)

🌉启动

（不，是创建文件😘）为了让代码具有可读性，方便后期维护，我们将文件分成三个文件进行，创建三个文件：头文件：“SeqList.h”用来存放头文件接口函数，源文件"SeqList.c"用来实现接口函数，具体实现步骤，"test.c"检查错误，测试函数功能如图：
在这里插入图片描述

SeqList.h

# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//静态顺序表//#define N 100
//struct SeqList
//{
//	SLDataType a[N];
//	int size;
//};//动态顺序表typedef int SLDataType;typedef struct SeqList
{SLDataType* arr;//存储数据的底层结构int capacity;   //记录顺序表的空间大小int size;       //记录顺序表当前有效的数据个数
}SL;

int 【N】和int*arr这样写不方便后面代码修改数据类型，当文件想要把数据类型int，修改为char，但是一个一个改，不方便，一键替换，会有替换不必要的风险，因此我们用typedef重新把int取名为SLDataType，因此要修改，直接修改int即可。
为了代码可读性，偷点小懒，我们可以把struct SeqList使用typedef再取名为SL，写SL比struct SeqList，更加方便，快捷。

🌠初始化

Ok，“Seqlist.h"接口搞定了，来具体实现接口函数"SeqList.c”，老样子，把接口函数的文件包含起来1. 将顺序表的数组指针初始化为NULL 2.将顺序表的当前长度size和容量capacity初始化为0：

#include "SeqList.h"
//初始化函数
void SLInit(SL* ps)
{ps->arr=NULL;ps->size = ps->capacity = 0;
}

🌉扩容

当我们插入数据，若空间不够，将要扩容操作：使用realloc函数。
检查顺序表是否需要扩容
计算新容量
使用realloc扩容数组
更新数组指针和容量 
//扩容
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity) //如果当前长度等于容量,需要扩容{//如果原容量为0,则新容量为4 //否则新容量为原容量的2倍int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//使用realloc重新分配内存空间if (NULL == tmp)//realloc失败,输出错误信息并退出{perror("realloc");exit(1);}/扩容成功,更新数组指针和容量ps->arr = tmp;ps->capacity = newCapacity;}}

🌠尾插

在这里插入图片描述
尾插的注意情况：
顺序表没有空间capacity为0，插不了，或者创建的空间capacity满了，或者空间足够，直接插。

void SLPushBack(SL* ps, SLDataType x)
{//断言--简单粗暴的解决方式//assert(ps !=NULL);assert(ps);//if判断--温柔的解决方式if(NULL == ps){return;}//空间不够，扩容SLCheckCapacity(ps);//空间足够，直接插入ps->arr[ps->size++] = x;//ps->size++;}

🌉 打印

打印函数，实现一个功能，我们可以实时进行输入数据验证，进行对函数的检查，我们把他封装在一个函数里，需要时，只需调用即可。

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

🌠销毁

到这里，顺序表的初始化，创建了尾插数据，打印检查，如果这样就完成了可不行，因为我们顺序表是动态内存分配的，还在内存的堆上有realloc分配的空间，不销毁会有内存泄漏的风险。

//销毁
void SLDestroy(SL* ps) 
{assert(ps);// 断言ps指针非空,防止传入NULL指针导致问题if (ps->arr) / 检查顺序表是否分配过内存{free(ps->arr);// 如果分配过内存,使用free释放内存}ps->arr = NULL;/ 释放完内存后,将arr指针设置为NULLps->size = ps->capacity = 0;/ 重置size和capacity为0,表示顺序表结构被销毁
}

🌉 尾删

尾部删除，你可能想到把最后那个元素标志为-1然后通过设置标识值来"删除",本身不修改元素内存,这样也可以，但是这样会篡改数据，如果原来是-1，怎么办？这样的代码如下：

//尾部删除
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//顺序表不为空ps->arr[ps->size - 1] = -1;ps->size--;
}

在这里插入图片描述

其实只要把最后一个元素数量减掉，最后一个数据去掉，size--，并不影响我们查找等功能。代码如下：

//尾部删除
void SLPopBack(SL* ps)
{assert(ps);// 断言ps指针非空assert(ps->size);// 断言顺序表不为空//顺序表不为空,可以进行删除操作ps->size--;//顺序表长度减1
}

🌠头插

顺序表的头插操作主要步骤如下:

         | 1 | 2 | 3 | 4 |  size = 4

  1. 检查顺序表是否为空,通过size判断

  2. 先把插入位置设为0,表示插入到头部

  3. 从尾到头依次移动元素,为新的元素腾出空间

          |   | 1 | 2 | 3 | 4 |  size = 4

   for(int i=ps->size; i>0; i--){ps->arr[i] = ps->arr[i-1];}

  1. 将新元素插入到0位置

          | 0 | 1 | 2 | 3 | 4 |size = 5

   ps->arr[0] = x;
  1. 顺序表长度size加1

它保证了元素的有序性,但移动元素的开销较大。时间复杂度为O(n)。

//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//判断是否扩容SLCheckCapacity(ps);//旧的数据往后挪动一位for (int i = ps->size;i>0;i--){ps->arr[i] = ps->arr[i - 1];//ps->arr[1]=ps->arr[0]}ps->arr[0] = x;ps->size++;
}

🌉 头删

方式和头插差不多，只需依次向前挪动数据，然后数据减一，size–就好了。

//头删void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//不为空执行挪动操作for (int i = 0; i<ps->size-1;i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

注意：为了防止头删除删到顺序表为空了，还删会出现越界，因此需要对顺序表的有效个数进行断言。

🌠指定位置插入数据

顺序表指定位置插入数据的主要思路是:

  1. 检查顺序表ps和插入位置pos是否合法

  2. 从尾到头遍历元素,当索引大于等于插入位置pos时,后移一个位置

   for(int i=ps->size-1; i>=pos; i--){ps->arr[i+1] = ps->arr[i];}
  1. 将新元素插入到pos位置
   ps->arr[pos] = x;
  1. 顺序表长度size加1

具体步骤:

假设现有顺序表:{1,2,3,4},插入元素0到位置1:

         |1|2|3|4|size=4

  1. pos设为1

  2. 从尾到头遍历,i>=pos时后移元素

          | |1|2|3|4|size=4

  3. 在pos=1位置插入0

          |0|1|2|3|4|size=5

通过从尾到头遍历元素,每次将元素后移一个位置,为插入元素腾出指定位置pos,然后插入新元素,实现了顺序表指定位置插入。

时间复杂度为O(n),需要移动指定位置之后的所有元素。

//指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);SLCheckCapacity(ps);for(int i=ps->size-1; i>=pos; i--){ps->arr[i+1] = ps->arr[i];}ps->arr[pos] = x;ps->size++;
}

🌉删除指定位置数据

顺序表删除指定位置数据的主要步骤是:

  1. 检查顺序表ps和位置pos是否合法

  2. 从删除位置开始,将后面的元素前移一个位置

   for(int i=pos; i<ps->size-1; i++){  ps->arr[i] = ps->arr[i+1];}
  1. 顺序表长度size减1

具体操作如下:

假设顺序表为:{1,2,3,4},删除位置2的元素:

         |1|2|3|4|size=4

  1. 确定删除位置pos=2

  2. 从pos开始,将后面元素前移一个位置

          |1|3|4| |size=4

  3. pos减1

          |1|3|4| |size=3

代码：

void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos以后的数据往前挪动一位for (int i=pos;i<ps->size-1;i++){ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2]=ps->arr[i-1];}ps->size--;
}

🌠查找

遍历元素，找到相同元素的数据返回即可，找不到返回-1

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

🌉修改

//修改
void SLModify(SL* ps, int pos, SLDatatype x)  
{assert(ps);assert(pos >= 0 &amp;&amp; pos < ps->size);ps->a[pos] = x;}

🚩总结

感谢你的收看，如果文章有错误，可以指出，我不胜感激，让我们一起学习交流，如果文章可以给你一个小小帮助，可以给博主点一个小小的赞😘

请添加图片描述

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

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

相关文章

matlab 线性四分之一车体模型

matlab 线性四分之一车体模型

1、内容简介 略 57-可以交流、咨询、答疑 路面采用公式积分来获得&#xff0c;计算了车体位移、非悬架位移、动载荷等参数 2、内容说明 略 3、仿真分析 略 线性四分之一车体模型_哔哩哔哩_bilibili 4、参考论文 略
阅读更多...
Redis高并发分布锁实战

Redis高并发分布锁实战

Redis高并发分布锁实战 问题场景 场景一: 没有捕获异常 // 仅仅加锁 // 读取 stock15 Boolean ret stringRedisTemplate.opsForValue().setIfAbsent("lock_key", "1"); // jedis.setnx(k,v) // TODO 业务代码 stock-- stringRedisTemplate.delete(&quo…
阅读更多...
php脚本输出中文在浏览器中显示乱码

php脚本输出中文在浏览器中显示乱码

问题说明 这个问题一般出现在较低版本的php中&#xff0c;原因是php和浏览器的字符解析方式不对应 &#xff0c;导致中文字符被错误解析成乱码 &#xff08;注&#xff0c;此处的php版本任意切换是依赖于小皮面板&#xff08;phpstudy&#xff09;实现的&#xff0c;感兴趣可以…
阅读更多...
Docker容器故障排查与解决方案

Docker容器故障排查与解决方案

Docker是一种相对使用较简单的容器&#xff0c;我们可以通过以下几种方式获取信息&#xff1a; 1、通过docker run执行命令&#xff0c;或许返回信息 2、通过docker logs 去获取日志&#xff0c;做有针对性的筛选 3、通过systemctl status docker查看docker服务状态 4、通过…
阅读更多...
【牛牛送书 | 第四期】《高效使用Redis：一书学透数据存储与高可用集群》带你快速学习使用Redis

【牛牛送书 | 第四期】《高效使用Redis：一书学透数据存储与高可用集群》带你快速学习使用Redis

前言&#xff1a; 当今互联网技术日新月异&#xff0c;随着数据量的爆炸式增长&#xff0c;如何高效地存储和管理数据成为了每个公司都必须面对的挑战。与此同时&#xff0c;用户对于应用程序的响应速度和稳定性要求也越来越高。在这个背景下&#xff0c;Redis 作为一个…
阅读更多...
【lv14 day10内核模块参数传递和依赖】

【lv14 day10内核模块参数传递和依赖】

一、模块传参 module_param(name,type,perm);//将指定的全局变量设置成模块参数 /* name:全局变量名 type&#xff1a; 使用符号 实际类型 传参方式 bool bool insmod xxx.ko 变量名0 或 1 invbool bool insmod xxx.ko 变量名0 或 1 charp char * insmod xxx.ko 变量名“字符串…
阅读更多...
解析Hadoop三大核心组件：HDFS、MapReduce和YARN

解析Hadoop三大核心组件：HDFS、MapReduce和YARN

目录 HadoopHadoop的优势 Hadoop的组成HDFS架构设计Yarn架构设计MapReduce架构设计 总结 在大数据时代&#xff0c;Hadoop作为一种开源的分布式计算框架&#xff0c;已经成为处理大规模数据的首选工具。它采用了分布式存储和计算的方式&#xff0c;能够高效地处理海量数据。Had…
阅读更多...
基于51单片机的智能监护与健康检测[proteus仿真]

基于51单片机的智能监护与健康检测[proteus仿真]

基于51单片机的自行车测速系统设计[proteus仿真] 个人健康检测系统这个题目算是课程设计和毕业设计中常见的题目了&#xff0c;本期是一个基于51单片机的智能监护与健康检测 需要的源文件和程序的小伙伴可以关注公众号【阿目分享嵌入式】&#xff0c;赞赏任意文章 2&#xff…
阅读更多...
Liunx--nginx负载均衡--前后端分离项目部署

Liunx--nginx负载均衡--前后端分离项目部署

一.nginx简介 Nginx是一个高性能的HTTP和反向代理服务器&#xff0c;它以其轻量级、占用资源少、并发能力强而广受欢迎。 详细介绍 开发背景与特点&#xff1a;Nginx由俄罗斯人Igor Sysoev开发&#xff0c;它是一个自由的、开源的软件。Nginx设计上注重性能和效率&#xff0c;能…
阅读更多...
图像读取裁剪与人脸识别

图像读取裁剪与人脸识别

图像读取 Image read ⇒ \Rightarrow ⇒ torchvision.datasets from torchvision import datasets dataset datasets.ImageFolder(data_dir, transformtransforms.Resize((512, 512)))Return value illustration dataset[0][0]是PIL.Image objects&#xff0c;这利用IPyth…
阅读更多...
音视频技术-电脑连接调音台时交流声的产生与消除

音视频技术-电脑连接调音台时交流声的产生与消除

当电脑&#xff08;笔记本/台式机&#xff09;声卡通过音频线与调音台&#xff08;或扩音机&#xff09;连接时&#xff0c;能听到“交流声”。有时很轻微&#xff0c;有时很明显&#xff0c;甚至干扰正常的演讲或发言。 很多时候&#xff0c;我们在台上演讲时&#xff0c;都会…
阅读更多...
Easy-Jmeter: 性能测试平台

Easy-Jmeter: 性能测试平台

目录 写在开始1 系统架构2 表结构设计3 测试平台生命周期4 分布式压测5 压力机管理6 用例管理6.1 新增、编辑用例6.2 调试用例6.3 启动测试6.4 动态控量6.5 测试详情6.6 环节日志6.7 实时数据6.8 测试结果 7 测试记录7 用例分析8 系统部署8.1普通部署8.2容器化部署 写在最后 写…
阅读更多...
嵌入式C语言（三）

嵌入式C语言（三）

typeof() 使用typeof可以获取一个变量或表达式的类型。 typeof的参数有两种形式&#xff1a;表达式或类型。 int i;typeof(i) j 20; --> int j 20;typeof(int *) a; -->int *a; int f(); -->typeof(f()) k;--? int k我们可以看出通过typeof获取一个变量的…
阅读更多...
前后端分离Vue+node.js在线学习考试系统gqw7o

前后端分离Vue+node.js在线学习考试系统gqw7o

与其它应用程序相比&#xff0c;在线学习平台的设计主要面向于学校&#xff0c;旨在为管理员和学生、教师、院系提供一个在线学习平台。学生、教师、院系可以通过系统及时查看公告信息等。 在线学习平台是在Windows操作系统下的应用平台。为防止出现兼容性及稳定性问题&#xf…
阅读更多...
使用 Verilog 做一个可编程数字延迟定时器 LS7211-7212

使用 Verilog 做一个可编程数字延迟定时器 LS7211-7212

今天的项目是在 Verilog HDL 中实现可编程数字延迟定时器。完整呈现了延迟定时器的 Verilog 代码。 所实现的数字延迟定时器是 CMOS IC LS7212&#xff0c;用于生成可编程延迟。延迟定时器的规格可以在这里轻松找到。基本上&#xff0c;延迟定时器有 4 种操作模式&#xff1a;…
阅读更多...
用c# 自己封装的Modbus工具类库源码

用c# 自己封装的Modbus工具类库源码

前言 Modbus通讯协议在工控行业的应用是很多的&#xff0c;并且也是上位机开发的基本技能之一。相关的类库也很多也很好用。以前只负责用&#xff0c;对其并没有深入学习和了解。前段时间有点空就在这块挖了挖。想做到知其然还要知其所以然。所以就有了自己封装的Modbus工具类库…
阅读更多...
Leetcode3014. 输入单词需要的最少按键次数 I

Leetcode3014. 输入单词需要的最少按键次数 I

题目&#xff1a; 代码(首刷看解析 2024年2月21日&#xff09;&#xff1a; class Solution { public:int minimumPushes(string word) {int n word.size();if (n < 8) return n;int mo n % 8;int x n / 8;int res 0;for (int i 1; i < x 1; i) {res i * 8;}res …
阅读更多...
leet hot 100-6 三数之和

leet hot 100-6 三数之和

三数之和 原题链接思路代码 原题链接 leet hot 100-5 15. 三数之和 思路 从前往后定义第一个数字 first 开始遍历整个数组 然后要求 frist和上一个数字不重复否则就是重复组合 从frist往后遍历第二个数字 同样要求第二个数字不能重复 再定义第三个数字从后往前面数 三个数字…
阅读更多...
iOS面试：4.多线程GCD

iOS面试：4.多线程GCD

一、多线程基础知识 1.1 什么是进程&#xff1f; 进程是指在系统中正在运行的一个应用程序。对于电脑而已&#xff0c;你打开一个软件&#xff0c;就相当于开启了一个进程。对于手机而已&#xff0c;你打开了一个APP&#xff0c;就相当于开启了一个进程。 1.2 什么是线程&am…
阅读更多...
http协议基础与Apache的简单介绍

http协议基础与Apache的简单介绍

一、相关介绍&#xff1a; 互联网&#xff1a;是网络的网络&#xff0c;是所有类型网络的母集因特网&#xff1a;世界上最大的互联网网络。即因特网概念从属于互联网概念。习惯上&#xff0c;大家把连接在因特网上的计算机都成为主机。万维网&#xff1a;WWW&#xff08;world…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023