动态顺序表的详解(上)

简介: 动态顺序表的详解(上)

顺序表的详细介绍

首先顺序表属于线性表,线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。

顺序表是一种使用数组实现的线性表结构,相邻元素在数组中连续存储。在 C 语言中,可以使用数组和指针来实现顺序表。通常情况下,我们会在代码中定义结构体来实现顺序表,其中包括以下信息:

存储数据的数组

当前顺序表中元素的数量

顺序表的最大容量

而顺序表有静态顺序表和动态顺序表,其中静态顺序表是使用定长数组存储元素的。动态顺序表使用动态开辟的数组存储。

动态顺序表的实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们实现动态顺序表。

结构体的定义

typedef int SLDataType;
typedef struct SeqList
{
  SLDataType* a;//存储元素的指针
  int size;//记录有效数据
  int capacity;//记录空间容量
}SL;

在这里将int重定义为SLDataType的原因是这样我们需要改变存储元素的类型仅改一个int就可以了,十分的方便。

顺序表的初始化

首先顺序表已经创建好了,那么开始用之前也要初始化一下,直接看代码。

void SLInit(SL* psl)
{
  assert(psl);
  psl->a=NULL;
  psl->size=0;
  psl->capacity=0;
}

首先在使用之前,有效数据个数当然是0个,那么存放元素所指向的指针也就是空指针了,空间容量也自然是0个了,在这里我们每个函数都用assert来断言一下,保证传入指针非空。

顺序表的销毁

有初始化就会有销毁,在程序结束时我们需要释放掉动态开辟的数组,并将一切都赋值为0,那么我们直接看代码。

void SLDestroy(SL* psl)
{
  assert(psl);
  if(psl->a!=NULL)
  {
    free(psl->a);
    psl->a=NULL;
    psl->size=0;
    psl->capacity=0;
  }
}

销毁的过程,首先要先判断传入指针是否为空,之后通过传入指针psl找到a判断该指针是否为空指针,不为空指针说明有元素存储,那么就需要释放掉这块动态开辟的空间,并将其赋值为空指针,最后将有效数据和空间容量赋值为0即可。

顺序表的扩容

接下来我们需要对顺序表进行头部插入元素或者尾部插入元素或者是任意位置差入元素,但如果顺序表的容量不够,就无法插入,所以我们对顺序表的扩容单独封装一个函数,对其进行调用即可。

void SLCheckCapacity(SL* psl)
{
  assert(psl);
  if(psl->size==psl->capacity)
  {
    int newcapacity=psl->capacity==0?4:psl->capacity*2;
    SLDataType* tmp=(SLDataType*)realloc(psl->a,sizeof(SLDataType)*newcapacity);
    if(tmp==NULL)
    {
      perror("realloc fail");
      return;
    }
    psl->a=tmp;
    psl->capacity=newcapacity;
}

首先,我们依然先来断言保证传入指针非空,之后查看通过传入指针psl找到的有效数据个数是否等于空间容量,如果相等则说明需要进行扩容,那么我们首先第一次一定是要进行扩容的,因为我们并没有给他开辟空间,所以用三目运算符来敲定如果通过psl指针找到的空间容量capacity等于0,则赋值为4个空间大小,之后在扩容很明显不是0,就扩容为上一次capacity的两倍(倍数根据实际情况选定)。做完这些事情我们只是把空间容量改了,真正能够存储元素的空间还没有开辟,所以接下来,我们定义一个临时变量tmp来接受动态开辟的空间,为什么不直接通过psl指针找到的a,因为如果我们在某一次扩容出现问题,直接赋给psl所指向的a,那么会导致之前psl所指向的a的元素数据丢失,造成不必要的麻烦,为了检查tmp是否正确开辟,我们用一个if语句来提醒,如果if语句没有生效就说明成功开辟,那么我们再把临时变量tmp赋值给通过psl所找到的a指针即可,最后扩容成功,也要newcapacity赋值给capacity即可。

顺序表的尾插

我们已经实现了顺序表的扩容,那么就可以来插入元素了,直接看代码。

void SLPushBack(SL* psl,SLDataType x)
{
  assert(psl);
  SLCheckCapacity(&psl);
  psl->a[psl->size]=x;
  psl->size++;
}

首先依然是先来断言保证传入指针非空,之后通过扩容函数判断是否需要扩容,之后将x值赋给通过psl找到的a的第psl->size个下标赋给这个位置的a,也就是最后一个位置。最后有效数据个数psl->size++即可。

顺序表的头插

实现了尾插之后我们来看一下实现头插,也是直接看代码。

void SLPushFront(SL* psl,SLDataType x)
{
  assert(psl);
  SLCheckCapacity(&psl);
  int end=psl->size-1;
  while(end>=0)
  {
    psl->a[end+1]=psl->a[end];
    end--;
  }
  psl->a[0]=x;
  psl->size++;
}

首先,我们实现数据头插,就需要将所有数据向后移动一位,从而达到首地址无元素的情况,所以我们先定义一个end变量为有效数据个数-1,之后通过while循环倒着将所有的元素向后移动一位,end–即可。循环结束后首地址就没有元素存放,这时我们将,x存放到psl指向a的首地址即可,最后size++。

顺序表的打印

为了防止我们插入元素无法显示出来,所以我们,先封装一个打印函数,能够将顺序表给打印出来。

void SLPrint(SL* psl)
{
  assert(psl);
  for(int i=0;i<psl->size;i++)
  {
    printf("%d ",psl->a[i]);
  }
  printf("\n");
}

这个函数实现十分的简单就不再过多赘述。

目录
相关文章
|
搜索推荐 物联网 计算机视觉
什么是智慧班牌?智慧班牌系统有哪些功能?
智慧班牌可以通过以云平台为基础,结合互联网、物联网系统进行校园管理,实现学校数据、教学资源共享,推进校园信息化交流建设。而展示在班牌终端的信息可以随时更改和上传新的信息,减少班牌更替带来的财物力的损失
358 1
|
存储 算法 安全
订单号和 id 列可不可以是同一列?
在分布式场景中,单表已经不能满足我们的需求了,所以用自增 id 的方案也就不合适了。当比如我们进行分表设计时,主键列到底如何生成就成了一个问题,流行的方法是利用像 snowflake 这样的算法计算出一个趋势有序的值作为 id。(当然还有其他多种方法)这样就满足了扩展性和一定程度上解决了检索性能的问题。
订单号和 id 列可不可以是同一列?
|
监控 前端开发 安全
CentOS7 部署 Zabbix 监控平台———监控网络设备,Linux 主机、Windows 主机
Zabbix 能监视各种网络参数,保证服务器系统的安全运营;并提供灵活的通知机制以让系统管理员快速定位/解决存在的各种问题。是一个基于 Web 界面的提供分布式系统监视以及网络监视功能的企业级开源解决方案。
1671 0
CentOS7 部署 Zabbix 监控平台———监控网络设备,Linux 主机、Windows 主机
|
12月前
|
人工智能 开发者 Python
python读取word文档 | AI应用开发
在RAG系统中,构建知识库时需读取多种外部文档,其中Word文档较为常见。本文介绍如何使用`python-docx`库读取Word文档(.docx格式)中的标题、段落、表格和图片等内容。首先通过`pip install python-docx`安装库,然后利用提供的接口提取所需信息。尽管该库功能强大,但在识别标题样式时需自定义逻辑,并且仅提供图片的URI而非直接加载。示例代码展示了读取文本、识别标题、读取表格及获取图片URI的方法。【10月更文挑战第2天】
496 2
|
机器学习/深度学习 算法
基于鲸鱼优化的knn分类特征选择算法matlab仿真
**基于WOA的KNN特征选择算法摘要** 该研究提出了一种融合鲸鱼优化算法(WOA)与K近邻(KNN)分类器的特征选择方法,旨在提升KNN的分类精度。在MATLAB2022a中实现,WOA负责优化特征子集,通过模拟鲸鱼捕食行为的螺旋式和包围策略搜索最佳特征。KNN则用于评估特征子集的性能。算法流程包括WOA参数初始化、特征二进制编码、适应度函数定义(以分类准确率为基准)、WOA迭代搜索及最优解输出。该方法有效地结合了启发式搜索与机器学习,优化特征选择,提高分类性能。
使用LabVIEW时遇到VISA属性错误 -1073807331的解决方案
使用LabVIEW时遇到VISA属性错误 -1073807331的解决方案
418 1
|
关系型数据库 Linux 网络安全
"Linux系统实战:从零开始部署Apache+PHP Web项目,轻松搭建您的在线应用"
【8月更文挑战第9天】Linux作为服务器操作系统,凭借其稳定性和安全性成为部署Web项目的优选平台。本文以Apache Web服务器和PHP项目为例,介绍部署流程。首先,通过包管理器安装Apache与PHP;接着创建项目目录,并上传项目文件至该目录;根据需要配置Apache虚拟主机;最后重启Apache服务并测试项目。确保防火墙允许HTTP流量,正确配置数据库连接,并定期更新系统以维持安全。随着项目复杂度提升,进一步学习高级配置将变得必要。
850 0
|
搜索推荐 小程序 Java
基于SpringBoot+Vue大学毕业设计管理系统设计和实现(源码+LW+调试文档+讲解等)
基于SpringBoot+Vue大学毕业设计管理系统设计和实现(源码+LW+调试文档+讲解等)
|
存储 算法 API
C/C++ 数据结构设计与应用(一): 数据结构的选择与应用 (Data Structure Selection and Application)
C/C++ 数据结构设计与应用(一): 数据结构的选择与应用 (Data Structure Selection and Application)
407 1
|
算法 Java
Java实现五子棋对战小游戏
Java实现五子棋对战小游戏
Java实现五子棋对战小游戏