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

超详细讲解线性表和顺序表!!

超详细讲解线性表和顺序表!!

  • 线性表
  • 顺序表
    • 顺序表的概念及结构
      • 静态顺序表
      • 动态顺序表
    • 顺序表接口实现
      • 1、创建
      • 2、初始化
      • 3、扩容
      • 4、尾插
      • 5、打印
      • 6、销毁
      • 7、尾删
      • 8、头插
      • 9、头删
      • 10、插入任意位置
      • 11、删除任意位置
      • 12、查找
      • 13、修改

线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储
地址的计算:
线性表中第一个元素的存储地址(基地址)和表中每个元素所占存储单元的多少,就可以计算出线性表中任意一个数据元素的存储地址,从而实现对顺序表中数据元素的随机存取。
设线性表中有n个元素,每个元素占k个单元,第一个元素的地址为Loc(a_1),则第i个元素的地址Loc(a_i):Loc(a_i)=Loc(a_1)+(i-1)*k

顺序表

顺序表的概念及结构

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

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
在这里插入图片描述
顺序表一般可以分为:静态顺序表与动态顺序表。

静态顺序表

静态顺序表:使用定长数组存储元素。
在这里插入图片描述
静态顺序表从某种意义上来说就是数组

如果数组空间满了就无法继续插入。
无法很好地确定要给定的内存空间,大了浪费空间,小了空间不足。

静态顺序表的大小在编译时确定,对静态顺序表的删除和插入是对其元素进行,而不是其存储空间的删除和插入,因此静态顺序表的大小在进行删除和插入操作后不会改变。
对于静态顺序表的查找,若按序号查找,则时间复杂度为O(1)。若按值查找,则需要将待查元素与表中每一个元素进行比较,直到找到或者遍历整个数组却找不到元素,此操作的时间复杂度为O(N)。

动态顺序表

在这里插入图片描述

顺序表接口实现

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

void SLInit(SL* ps);//名字简写           初始化
void SLPushBack(SL* ps, SLDatatype x);  //尾插
void SLPopBack(SL* ps);                 //尾删
void SLPushFront(SL* ps, SLDatatype x); //头插
void SLPopFront(SL* ps);                //头删
void SLPrit(SL* ps);                    //打印
void SLDestory(SL* ps);                 //释放
void SLCheckCapacity(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);    //修改

在此之前,明白何为接口函数:
接口函数就是某个模块写了(主要)给其它模块用的函数,可以实现隐藏信息,封装等,数据进行操作时进行调用的函数,通过调用数据结构的接口帮助你完成一系列操作

1、创建

因为是一个比较大的板块,在一开始创建时尽量分开不同板块编写。
在这里插入图片描述

#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>//#define N 200
typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;//指向动态数组指针int size;       //数据个数int capacity;  //容量-空间大小
}SL;

使用 typedef 定义一个新的数据类型,这里我们把它取名为 SLDataType(顺序表数据类型)。

2、初始化

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

3、扩容

插入元素的时候理所应当需要考虑插入元素时空间是否足够,如果空间不够,则使用realloc函数扩容。(realloc函数在一开始没空间申请空间时等作用于malloc函数的作用)

//检查容量-扩容
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newcapacitv = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDatatype* tmp = (SLDatatype*)realloc(ps->a, newcapacitv * sizeof(SLDatatype));if (tmp == NULL){perror("relloc:");exit(-1);//结束程序}ps->a = tmp;ps->capacity = newcapacitv;}
}

4、尾插

void SLPushBack(SL* ps, SLDatatype x)
{SLCheckCapacity(ps);//检查容量空间ps -> a[ps->size] = x;ps->size++;
}

尾插有三种情况:
① 第一种情况是顺序表压根就没有空间。
② 第二种情况就是我们创建的 capacity 空间满了。
③ 第三种情况是空间足够,直接插入数据即可。

5、打印

打印我们表中所存放的函数。

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

6、销毁

不销毁会存在内存泄漏的风险。

void SLDestory(SL* ps)//动态开辟的内存越界使用有时
{                     //有时要在free的时候才能检查出来。if (ps->a){free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;}
}

7、尾删

删除最后一个元素。只需要元素数量–就好,无法访问最后一个元素那么它便是无效的数据。

void SLPopBack(SL* ps)
{assert(ps->size);ps->size--;
}

当然,包括尾删以及其他步骤,我们都必须要注意越界访问的问题。比如尾删步骤中,如果内存中一个元素都没有了,size有可能减到-1的位置上而出现错误,需要断言一下。
当然,温柔的检查以及暴力的检查读者们喜欢哪个就全取决于自己了。

// 温柔的检查if (ps->size == 0){return;}// 暴力的检查assert(ps->size > 0);//ps->a[ps->size - 1] = 0;ps->size--;
}

8、头插

将数组内容整体后移,就可以在最前面出现一个空的位置。
首先创建一个 end 变量用来指向要移动的数据,因为指向的是数据的下标,所以是 size 要减 1 。随后进入 while 循环,如果 end >= 0 说明还没有移动完,就会进入循环。循环体内利用下标,进行向后移动操作,移动结束后再 end-- ,进行下一个数据的向后移动。挪动数据成功后,就可以插入了。此时顺序表第一个位置就被腾出来了,就可以在下标0位置插入欲插入的数据 x 了。最后size++ 。

void SLPushFront(SL* ps, SLDatatype x)
{SLCheckCapacity(ps);//从后向前挪动数据int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps ->size++;
}

9、头删

思路和头插类似。

//头删
void SLPopFront(SL* ps)
{assert(ps->size);int begin = 1;while (begin < ps->size){ps->a[begin-1] = ps->a[begin];begin++;}ps->size--;
}

10、插入任意位置

 
//任意插入
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++;
}

11、删除任意位置

删除指定位置的数据,我们仍然要限制 pos 的位置。限制条件部分和 SeqListInsert 不同的是,因为 psl->size 这个位置没有效数据,所以删除的位置不能是 psl->size!
任意位置删除的函数可以替代头删和尾删。

//任意删除
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//注意边界的处理/*int begin = pos;while (begin < ps->size - 1){ps->a[begin] = ps->a[begin + 1];begin++;}*/int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

12、查找

//查找
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;}

13、修改

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

相关文章:

超详细讲解线性表和顺序表!!

超详细讲解线性表和顺序表&#xff01;&#xff01;线性表顺序表顺序表的概念及结构静态顺序表动态顺序表顺序表接口实现1、创建2、初始化3、扩容4、尾插5、打印6、销毁7、尾删8、头插9、头删10、插入任意位置11、删除任意位置12、查找13、修改线性表 线性表&#xff08;linea…...

大数据之-Nifi-Nifi的安装_启动_认识Nifi的操作台---大数据之Nifi工作笔记0002

然后我们看一下如何安装nifi 这个上一节已经说了 然后看一下环境准备,这个自己去安装就可以了,需要jdk,1.8就可以了,然后 maven安装上就可以了 然后去下载,这里下载Linux版本的 1.9.2的版本比较稳定 下载以后,避免端口冲突要修改端口默认是8080,修改为58080 然后启动很简单,看…...

【大数据clickhouse】clickhouse 常用查询优化策略详解

一、前言 在上一篇我们分享了clickhouse的常用的语法规则优化策略&#xff0c;这些优化规则更多属于引擎自带的优化策略&#xff0c;开发过程中只需尽量遵守即可&#xff0c;然而&#xff0c;在开发过程中&#xff0c;使用clickhouse更多将面临各种查询sql的编写甚至复杂sql的…...

【Java项目】基于Java+MySQL+Tomcat+maven+Servlet的个人博客系统的完整分析

✨哈喽&#xff0c;进来的小伙伴们&#xff0c;你们好耶&#xff01;✨ &#x1f6f0;️&#x1f6f0;️系列专栏:【Java项目】 ✈️✈️本篇内容:个人博客系统前后端分离实现&#xff01; &#x1f680;&#x1f680;个人代码托管github&#xff1a;博客系统源码地址&#xff…...

java 程序员怎么做找工作

java 程序员怎么做找工作 在网络招聘网站上搜索职位。在中国&#xff0c;像智联招聘、前程无忧、猎聘网等招聘网站上&#xff0c;有许多公司在招聘JAVA程序员。通过这些网站可以快速找到自己合适的工作。 关注社交媒体和专业网站。 加入一些面向JAVA程序员的社交媒体和专业网…...

S7-1200对于不同项目下的PLC之间进行开放式以太网通信的具体方法示例

S7-1200对于不同项目下的PLC之间进行开放式以太网通信的具体方法示例 如下图所示,打开TIA博途创建一个新项目,并通过“添加新设备”组态 S7-1200 客户端 ,选择 CPU1214C DC/DC/DC (client IP:192.168.0.102),建立新子网; 首先编写客户端程序:打开OB1编程界面,选择指令…...

操作系统(四):磁盘调度算法,先来先服务,最短寻道时间优先,电梯算法

文章目录一、磁盘结构二、先来先服务三、最短寻道时间优先四、电梯算法 SCAN一、磁盘结构 盘面&#xff08;Platter&#xff09;&#xff1a;一个磁盘有多个盘面&#xff1b; 磁道&#xff08;Track&#xff09;&#xff1a;盘面上的圆形带状区域&#xff0c;一个盘面可以有多…...

maven解决包冲突简单方式(插件maven helper | maven指令)

文章目录使用idea插件maven helper使用maven指令在Java开发中&#xff0c;常常会遇到不同jar包之间存在冲突的情况&#xff0c;这可能会导致编译错误、运行时异常等问题。 使用idea插件maven helper 在idea安装插件maven helper 安装重启完之后点击pom文件&#xff0c;有一个De…...

100行Pytorch代码实现三维重建技术神经辐射场 (NeRF)

提起三维重建技术&#xff0c;NeRF是一个绝对绕不过去的名字。这项逆天的技术&#xff0c;一经提出就被众多研究者所重视&#xff0c;对该技术进行深入研究并提出改进已经成为一个热点。不到两年的时间&#xff0c;NeRF及其变种已经成为重建领域的主流。本文通过100行的Pytorch…...

linux操作系统篇

目录 操作系统概述基本特征并发共享虚拟异步进程管理内存管理文件管理设备管理宏内核和微内核宏内核微内核中断分类外中断异常陷入(系统调用)进程管理进程与线程的区别进程状态切换进程调度算法**批处理系统****交互式系统**进程同步临界...

redis+token实现登录校验,前后端分离,及解跨域问题的4种方法

目录 一、使用自定义filter实现跨域 1、客户端向服务端发送请求 2、服务端做登录验证了&#xff0c;并生成登路用户对应的token&#xff0c;保存到redis 3、响应&#xff08;报错&#xff09;-----跨域问题 4、解决跨域问题--------服务器端添加过滤器&#xff0c;设置请求…...

怎么解密MD5,常见的MD5解密方法,一看就会

MD5是一种被广泛使用的密码散列函数&#xff0c;曾在计算机安全领域使用很广泛&#xff0c;但是也因为它容易发生碰撞&#xff0c;而被人们认为不安全。那么&#xff0c;MD5应用场景有哪些&#xff0c;我们怎么解密MD5&#xff0c;本文将带大家了解MD5的相关知识&#xff0c;以…...

Vue3 目录结构

Vue3 目录结构 架构搭建 请确保你的电脑上成功安装 Node.js&#xff0c;本项目使用 Vite 构建工具&#xff0c;需要 Node.js 版本 > 12.0.0。 查看 Node.js 版本&#xff1a; node -v建议将 Node.js 升级到最新的稳定版本&#xff1a; 使用 nvm 安装最新稳定版 Node.js…...

Tsp_nurrec表空间满处理记录20230215

Tsp_nurrec表空间满处理记录20230215 一、问题: 问题:护理病历表空间不足。 二、解决过程:1.查询表空间使用效率 SELECT UPPER(F.TABLESPACE_NAME) “表空间名”, D.TOT_GROOTTE_MB "表空间大小(M)",D.TOT_GROOTTE_MB - F.TOTAL_BYTES "已使用空间(M)"…...

影像测量设备都有什么?有哪些影像仪器?

影像测量仪器是广泛应用于机械、电子、仪表的仪器。主要由机械主体、标尺系统、影像探测系统、驱动控制系统和测量软件等与高精密工作台结构组成的光电测量仪器。一般分为三大类&#xff1a;手动影像仪、自动影像仪和闪测影像仪。测量元素主要有&#xff1a;长度、宽度、高度、…...

Transformer:开启CV研究新时代

来源&#xff1a;投稿 作者&#xff1a;魔峥 编辑&#xff1a;学姐 起源回顾 有关Attention的论文早在上世纪九十年代就提出了。 在2012年后的深度学习时代&#xff0c;Attention再次被翻了出来&#xff0c;被用在自然语言处理任务&#xff0c;提高RNN模型的训练速度。但是由…...

Flink X Hologres构建企业级Streaming Warehouse

摘要&#xff1a;本文整理自阿里云资深技术专家&#xff0c;阿里云Hologres负责人姜伟华&#xff0c;在FFA实时湖仓专场的分享。点击查看>>本篇内容主要分为四个部分&#xff1a; 一、实时数仓分层的技术需求 二、阿里云一站式实时数仓Hologres介绍 三、Flink x Hologres…...

关于 mysql数据库插入中文变空白 的解决方法

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/129048030 红胖子网络科技的博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV、OpenGL、ffmpeg、OSG、单片机、软…...

不可错过的SQL优化干货分享-sql优化、索引使用

本文是向大家介绍在sql调优的几个操作步骤&#xff0c;它能够在日常遇到慢sql时有分析优化思路&#xff0c;能够让开发者更好的了解sql执行的顺序和原理。一、前言在日常开发中&#xff0c;我们经常遇到一些数据库相关的问题&#xff0c;比方说&#xff1a;SQL已经走了索引了&a…...

vue3:直接修改reative的值,页面却不响应,这是什么情况?

目录 前言 错误示范&#xff1a; 解决办法&#xff1a; 1.使用ref 2.reative多套一层 3.使用Object.assign 前言&#xff1a; 今天看到有人在提问&#xff0c;问题是这样的&#xff0c;我修改了reative的值&#xff0c;数据居然失去了响应性&#xff0c;页面毫无变化&…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...