【数据结构】线性表——顺序表

文章目录

  • 一、线性表
  • 二、顺序表
    • 2.1概念及结构
    • 2.2、顺序表接口实现
      • 2.2.1、顺序表的动态存储
      • 2.2.2、顺序表初始化
      • 2.2.3、检查空间判断进行增容
      • 2.2.4、顺序表尾插、尾删
      • 2.2.5、顺序表头插、头删
      • 2.2.6、顺序表查找
      • 2.2.7、顺序表在pos位置插入x
      • 2.2.8、顺序表删除pos位置的值
      • 2.2.9、顺序表销毁
      • 2.2.10、顺序表打印
  • 三、顺序表的劣势


一、线性表

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

线性表逻辑上是线性结构,也就说是连续的一条直线(如图一)。但是在物理结构上并不一定连续的(如图二)。线性表物理上存储时,通常以数组和链式结构的形式存储。(假设在32位机器上)
在这里插入图片描述
在这里插入图片描述


二、顺序表

2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改

顺序表一般可以分为:

  1. 静态顺序表:使用定长数组存储元素。(如下图)在这里插入图片描述

  2. 动态顺序表:使用动态开辟的数组存储。在这里插入图片描述

说白了顺序表就是数组😆没想到把~意不意外
虽说顺序表就是数组,但是也不能说顺序表没用,在高级的储存单元里面(如二叉树)底层就是使用顺序表的。

2.2、顺序表接口实现

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

2.2.1、顺序表的动态存储

函数命名规则借鉴CPP的stl库进行命名。

首先创建一个结构体,用于储存顺序表结构。

typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;
  • typedef int SLDateType;把顺序表结构的类型重命名为:SLDateType。若将来如果要改变数据顺序表内容的结构类型。可以极为方便的改变。
  • 在结构体中定义了。顺序表的总体大小和当前容量。以便确认是否需要扩容。
  • 定义的SLDateType*用于接收动态开辟的内存。
  • size是顺序表的大小。
  • capacity是顺序表当前的元素数量。

2.2.2、顺序表初始化

void SeqListInit(SeqList* ps) {SLDateType* arr = (SLDateType*)malloc(sizeof(SLDateType) * 2);if (arr == NULL) {perror("malloc in SeqListInit of arr::");}ps->a = arr;ps->size = 2;ps->capacity = 0;
}
  • 因为顺序表的结构体是没有进行内存划分的。所以需要把顺序表的结构体进行初始化。
  • 默认开辟两个空间。
  • 在成功开辟后。把size设置为2。capacity设置为0。

2.2.3、检查空间判断进行增容

void CheckCapacity(SeqList* ps) {if (ps->capacity == ps->size) {SLDateType* arr = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->size * 2);if (arr == NULL) {perror("realloc in SeqListPushBack");}ps->a = arr;ps->size *= 2;}
}
  • 每次进行插入都需要判断空间是否足够,所以,需要提前完成检查空间函数。
  • 每次扩容扩二倍。

2.2.4、顺序表尾插、尾删

void SeqListPushBack(SeqList* ps, SLDateType x) {assert(ps);CheckCapacity(ps);//int i = ps->capacity;(ps->a)[ps->capacity] = x;ps->capacity++;
}
  • 与数组的插入,并无二意。
void SeqListPopBack(SeqList* ps) {assert(ps && ps->capacity);ps->capacity--;
}
  • 只要把当前数据。进行减减。无需把顺序表中的内容进行删除。因为再次尾插数据,就会把之前的数据覆盖。

2.2.5、顺序表头插、头删

void SeqListPushFront(SeqList* ps, SLDateType x) {assert(ps);CheckCapacity(ps);memmove(((ps->a) + 1), ps->a, sizeof(SLDateType) * ps->capacity);ps->a[0] = x;ps->capacity++;
}
  • 顺序表的头插需要把全部数据往后移动一位。
  • 移动完成后就插入数据到头部空位。
void SeqListPopFront(SeqList* ps) {assert(ps && ps->capacity);ps->capacity--;memmove(ps->a, ((ps->a) + 1), sizeof(SLDateType) * ps->capacity);
}
  • 头删只需要把后面一位的数据全部往前移动一位。即可覆盖首元素的数据。

2.2.6、顺序表查找

int SeqListFind(SeqList* ps, SLDateType x) {assert(ps && ps->capacity);for (int i = 0; i < ps->capacity; i++) {if (ps->a[i] == x) {return i;}}return -1;
}
  • 与数组查找数据一样,循环遍历即可。

2.2.7、顺序表在pos位置插入x

void SeqListInsert(SeqList* ps, int pos, SLDateType x) {assert(ps && ps->capacity);CheckCapacity(ps);memmove(ps->a + pos, ps->a + pos - 1, sizeof(SLDateType) * (ps->capacity - pos + 1));ps->a[pos - 1] = x;ps->capacity++;
}
  • 找到对应位置后,从当前位置位置到数据结尾的内容全部向后移动一位。然后再在该位置进行数据的赋值。

2.2.8、顺序表删除pos位置的值

void SeqListErase(SeqList* ps, int pos) {assert(ps && ps->capacity);memmove(ps->a + pos - 1, ps->a + pos, sizeof(SLDateType) * (ps->capacity - pos + 1));ps->capacity--;}
  • 找到需要删除的pos位置后。把pos后一位的内容全部向前移动一位即可把pos值原先的内容覆盖。做到删除pos位置的值

2.2.9、顺序表销毁

void SeqListDestroy(SeqList* ps) {assert(ps && ps->a);free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}
  • 直接把动态开辟的内存释放掉,然后再把ps结构体中全部内容赋为空或零值。

2.2.10、顺序表打印

void SeqListPrint(SeqList* ps) {assert(ps && ps->a);for (int i = 0; i < ps->capacity; i++) {printf("%d ", ps->a[i]);}printf("\n");
}
  • 与数组的循环打印并无二样。
  • 把循环结束条件定为capacity,这样做可以把尾删的数据不再打印数据中。

三、顺序表的劣势

  1. 中间/头部的插入删除,时间复杂度为O(N)
  2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
  3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

以上就是本章所有内容。若有勘误请私信不才。万分感激💖💖 如果对大家有帮助的话,就请多多为我点赞收藏吧~~~💖💖
请添加图片描述

ps:表情包来自网络,侵删🌹

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

JAVA基础:分页 (学习笔记)【DVD分页查看】

分页 分页一张表---创建entry类 分页多张表---创建pojo类 1&#xff0c;准备实体类 com.jr.entry.DVD 2&#xff0c;接口问题&#xff1a; &#xff08;1&#xff09;根据条件 --- 获得符合条件的总条数 &#xff08;2&#xff09;根据条件 --- 获得符合条件的集合数据。 …

macOS开发环境配置与应用开发(详细讲解)

&#x1f4dd;个人主页&#x1f339;&#xff1a;一ge科研小菜鸡-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 1. 引言 macOS作为Apple公司推出的桌面操作系统&#xff0c;以其稳定性、优雅的用户界面和强大的开发工具吸引了大量开发者。对于…

Qt桌面应用开发 第二天(信号和槽 Lambda表达式)

目录 1.信号和槽 1.1信号 1.2信号和槽重载问题 1.3 注意事项 1.4信号和槽Lambda表达式 1.信号和槽 信号的发送者——信号——信号的接受者——信号的处理&#xff08;槽函数&#xff09; connect(信号的发送者&#xff0c;发送的信号&#xff0c;信号的接受者&#xff0…

ubuntu 22.04 server 安装 anaconda3

ubuntu 22.04 server 安装 anaconda3 https://www.anaconda.com/download/success Anaconda Installers wget https://repo.anaconda.com/archive/Anaconda3-2024.10-1-Linux-x86_64.sh 其他的是 默认 Executing transaction: done installation finished. Do you wish to…

如何设置VSCODE快捷键光标移到行首和行尾

{ "key": "cmdhome", "command": "cursorTop", },{ "key": "cmdend", "command": "cursorBottom", }

台新金控在台北金融科技展上展示自研GenAI应用与LLM

在今年的台北金融科技展上&#xff0c;多家金融机构展示了他们的生成式人工智能&#xff08;GenAI&#xff09;应用。其中&#xff0c;台新金控也展示了包括升级后的智能客服、面向企业金融客户的拟真客服人员、影片生成服务以及音乐生成服务等应用。 然而&#xff0c;台新的亮…

项目开发流程规范文档

项目开发流程规范文档 目标: 明确项目组中需求管理人员, 交互设计, 美工以及开发之间的工作输入输出产物. 明确各岗位职责. 以免造成开发, 产品经理以及项目经理之间理解不到位, 沟通成本过高,返工造成资源浪费. 所有环节产生的文档都可以作为项目交付的资源. 而不是事后再补文…

Go API 多种响应的规范化处理和简化策略

一个对外提供API接口的服务&#xff0c;在真正动工开发接口前一般需要先确定一下接口响应的通用格式&#xff0c;无论接口响应里返不返回业务数据&#xff0c;返回的数据是字符串、列表、对象还是其他类型都会遵照这个通用的响应格式。 既然一个项目接口的响应格式是确定的&…

poi excel数据统计导出

##poi excel导出案例 1.ajxa导出请求没有任何反应&#xff0c;打断点看了workBook中也有数据&#xff0c;网上查阅说ajax请求导出无法接收流&#xff0c;换成location.href,果然可以了 2.控制器代码 response.setCharacterEncoding("UTF-8");response.setContentTyp…

基于Python的影院电影购票系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…

SQL Server 多数据源配置

目录 1、添加依赖 2. 配置数据源 3. 创建数据源配置类 4. 创建Mapper接口和XML映射文件 5. 使用Mapper 6.启动类配置 7.项目结构目录 1、添加依赖 首先&#xff0c;在pom.xml文件中添加SQL Server的JDBC驱动&#xff1a; <!-- SQL Server Connector --> <dep…

FlinkSql读取外部Mysql和HBase数据库的方法(scala)

我的Flink版本为1.13.6 <flink.version>1.13.6</flink.version> FlinkSql读取外部的MySQL是走的JDBC所以需要以下两个依赖&#xff1a; <dependency><groupId>org.apache.flink</groupId><artifactId>flink-connector-jdbc_${scala.bina…

使用Rust实现http/https正向代理

相关库的安装 利用vcpkg安装openssl库 vcpkg install openssl:x64-windows并设置openssl库位置的环境变量 $Env:OPENSSL_DIR"D:/vcpkg/packages/openssl_x64-windows/"安装openssl软件&#xff0c;因为需要利用openssl生成自签名证书 Cargo依赖 [dependencies] …

vue3如何使用pinia设置全局状态,附常见面试题

1. stores/index.ts 文件 在 index.ts 中创建 store 实例并封装了注册逻辑&#xff0c;这样可以方便地将整个 Pinia 实例注册到 Vue 应用中。代码如下&#xff1a; import type { App } from vue import { createPinia } from piniaconst store createPinia()// 全局注册 st…

【微知】Nvida Mellanox网卡中速率SDR、DDR、QDR、FDR、EDR、HDR、NDR全称与速率?

文章目录 综述背景全称早期速率&#xff1a;中期当前 其他 综述 Single Data Rate (SDR) 10Gbps Double Data Rate (DDR) 20Gbps Quad Data Rate (QDR) 40Gbps Fourteen Data Rate (FDR) 56Gbps Enhanced Data Rate (EDR) 100Gbps High Data Rate (HDR) 200Gbps Next Data Rat…

融合虚拟化与容器技术,打造灵活又安全的AI算力服务

随着人工智能技术的不断进步&#xff0c;AI企业在迅速推进大模型业务时&#xff0c;往往会倾向于采用容器化的轻量部署方案。相较于传统的虚拟机部署&#xff0c;容器化在快速部署、资源利用、环境一致性和自动化编排等方面具备显著优势。 然而&#xff0c;容器技术所固有的隔…

Hunyuan-Large:推动AI技术进步的下一代语言模型

腾讯近期推出了基于Transformer架构的混合专家&#xff08;MoE&#xff09;模型——Hunyuan-Large&#xff08;Hunyuan-MoE-A52B&#xff09;。该模型目前是业界开源的最大MoE模型之一&#xff0c;拥有3890亿总参数和520亿激活参数&#xff0c;展示了极强的计算能力和资源优化优…

岛屿数量 广搜版BFS C#

和之前的卡码网深搜版是一道题 力扣第200题 99. 岛屿数量 题目描述 给定一个由 1&#xff08;陆地&#xff09;和 0&#xff08;水&#xff09;组成的矩阵&#xff0c;你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成&#xff0c;并且四周都是水域。…

本地使用conda创建django虚拟环境

1、首先本地安装好conda。 2、创建django的虚拟环境 conda create -n django # 这里的 django只是虚拟的名称&#xff0c;自己随便名字就行&#xff0c;只要你自己知道这个是django的虚拟环境就行。 3、安装成功&#xff0c;查看虚拟环境 conda env list 4、激活虚拟环境…

rabbitMQ

官网&#xff1a;https://www.rabbitmq.com/ 一 介绍与安装 1 安装 我们同样基于Docker来安装RabbitMQ&#xff0c;使用下面的命令即可&#xff1a; docker run \-e RABBITMQ_DEFAULT_USERitheima \-e RABBITMQ_DEFAULT_PASS123321 \-v mq-plugins:/plugins \--name rabbi…