初阶数据结构【2】--顺序表(详细且通俗易懂,不看一下吗?)

本章概述

  • 线性表
  • 顺序表
  • 顺序表问题与思考
  • 彩蛋时刻!!!

线性表

  • 概念一些在逻辑上成线性关系的数据结构的集合线性表在逻辑上一定成线性结构,在物理层面上不一定成线性结构。常见的线性表:顺序表,链表,栈,队列,字符串……。
  • 逻辑线性结构就是人为想像的具有某种联系的结构,这种关系是线性的。如图所示:在这里插入图片描述
  • 线性物理结构在空间上是连续的,是线性的,就像火车一样,各个车厢是一节一节的连接的。反之,就是非线性物理结构。在内存中的体现就是地址空间是连续的,如图所示:在这里插入图片描述
  • 为什么有的线性表物理上不是线性结构呢?:这就好比我们在一家餐馆排队取餐一样,我们都各自排好队,人与人之间可能并不是紧挨着排队,我们之间会前后错落,这就导致我们在物理空间上不是连续的,不是线性的。但是,我们在逻辑上是线性的,因为我们都是前后交错的,不能乱插队。如图所示:在这里插入图片描述
    线性表是这些在逻辑上成线性结构的数据结构的统称,就像苹果,西瓜,香蕉……这些都统称为水果,线性表也是这个意思。其它线性数据结构,我会不断的给大家分享的,继续往后学习,你就会体会到这种线性存储数据的巧妙之处。

顺序表

  • 概念在逻辑和物理上都成线性关系的数据结构它是以数组为底层来进行数据存储的,所以在物理上体现线性。 如图所示:在这里插入图片描述
    读到这里,可能就有人有疑问了——既然顺序表是用数组来实现的,那么两者的区别是什么? 在讲这个问题之前,我先给大家看个图在这里插入图片描述
    我来解释一下这个图的意思:炒西兰花和绿野仙踪的本质都是西兰花,但是,对西兰花进行装饰和好看的摆盘,就成了绿野仙踪(价格也漂亮!),就是对西兰花进行了漂亮的封装一个普通的数组可以进行数据的存储和数据的访问,功能很少。但是,经过对数组进行封装,我们在它原来的功能基础上增加了删除数据,增加数据和自动增加数组容量,就摇身一变成了顺序表。
  • 结构顺序表的基本功能要对数据进行存储,所以我们自然少不了数组形式的存储。我们还要知道这个顺序表的有效数据个数(存储了多少个数据)对于动态顺序表,我们还要知道顺序表的容量。所以,针对于以上的特征我们要用到结构体。结构体知识忘的同学可以回顾:点击:《结构体》。
  • 分类分为静态顺序表动态顺序表
    • 静态顺序表:以定长数组为原理进行存储。 结构如图所示:在这里插入图片描述
      静态顺序表有个致命的缺点——容量大小是固定的。我们静态顺序表里面的数组大小是固定的,当我们要存储的数据量较多时,就会出现空间不够用,当我们存储的数据量很少时,就会出现空间的大量浪费。为了避免空间的不足或浪费,我们每次都要调整数组的容量,这就很不方便,代码执行效率太低了。所以,我们一般不用静态顺序表。我们最常用的是动态顺序表——因为它能自动改变数组的容量
    • 动态顺序表:用动态内存函数realloc进行空间的申请。结构如图所示:在这里插入图片描述
      动态顺序表相对于静态顺序表,里面多了一些东西。因为我们是在原来空间基础上扩容的,所以要用realloc,又因为我们要用动态内存函数realloc进行空间的开辟,所以我们要用SLDatatype * arr;来接受malloc因为存储什么类型的数据,我们不知道,所以要用typedef宏定义,我们根据数据类型直接改宏定义,就能改变全局数据类型。capacity就是用来确定我们要开辟的空间大小。我们后面展示的代码都是以动态数组为根据的。
  • 动态顺序表的实现:我们要建立三个文件来实现动态顺序表
1. 建个Sqlist.h文件:用于函数和结构体的声明。
2. 建个Sqlist.c文件:用于实现各个功能函数。
3. 建个 test.c 文件:用来测试顺序表的功能。

进行图片展示:在这里插入图片描述
接下来,我直接给大家展示顺序表的各个功能代码的实现。

  • Sqlist.h
#pragma once     	  	//头文件的定义格式
#include <stdio.h>   	//我们直接把需要的头文件都定义在<Sqlist.h>,
#include <stdlib.h>		//我们就不用在<test.c>写这些头文件了。
#include <assert.h>
typedef int SLDatatype;  //宏定义,便于我们后续修改数据类型。
typedef struct Sqlist
{SLDatatype* arr;   //接收malloc返回的空间地址int size;      //有效数据个数int capacity; 	 //顺序表的容量
}SL;void SqlistNit(SL* pp); //顺序表初始化
void my_printf(SL* p);  //打印函数
void Sqlistcheck(SL* p);  //检查空间够不够void Sqlistpopback(SL* p); //尾部删数据
void Sqlistpushback(SL* ps, SLDatatype x); //数据尾插void SqlistpopFront(SL* ps); //数据头删
void SqlistpushFront(SL* ps, SLDatatype x); //数据头插void SqlistpushSy(SL* p, int da, SLDatatype x);//任意位置插入数据
  • Sqlist.c
#define  _CRT_SECURE_NO_WARNINGS	1
#include "Sqlist.h"  //引用<Sqlist.h>头文件
void Sqlistcheck(SL*p)   //检查空间够不够
{assert(p);   //传递的指针不能为空if (p->size == p->capacity){int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2; //当容量不够时,就自动扩容原来的2倍。p->capacity = newcapacity;SLDatatype* temp = (SLDatatype*)realloc(p->arr, newcapacity * 2 * sizeof(SLDatatype));  //malloc开辟空间,用temp接收,要注意类型的转换。if (temp != NULL)p->arr = temp;  //判断空间开辟是否成功,开辟成功就赋值elsereturn 1;  //开辟失败就直接返回}
}
void Sqlistpushback(SL*ps,SLDatatype x)  //数据尾插
{assert(ps); //判断传递的是否为空指针Sqlistcheck(ps); //检查空间够不够ps->arr[ps->size++] = x; 
}
void SqlistpushFront(SL*ps,SLDatatype x)  //数据头插
{assert(ps);  //判断传递的是否为空指针Sqlistcheck(ps); //检查空间够不够for (int i = ps->size;i>0; i--){ps->arr[i] = ps->arr[i-1];}ps->arr[0] = x;ps->size++;  //因为我们插入了数据,所以有效数据个数就要增加。
}
void SqlistpopFront(SL*ps)  //数据头删
{assert(ps&&ps->size);  //有效数据个数不能为空,要不然就不用删了for (int i = 0; i + 1 < ps->size; i++){ps->arr[i] = ps->arr[i+1];}ps->size--;  //因为删除了数据,所以有效数据个数就减少
}
void SqlistNit(SL*pp)    //初始化
{pp->arr = NULL; //防止野指针的发生pp->size = pp->capacity = 0;
}
void my_printf(SL* p)  //打印数据
{int i = 0;for (i = 0; i < p->size; i++){printf("%d ",p->arr[i]);}printf("\n");
}
void Sqlistpopback(SL* p)  //尾部删数据
{assert(p);   	//判断传递的是否为空指针--p->size; 		 //因为删除了数据,所以有效数据个数就减少
}
void SqlistpushSy(SL* p,int da,SLDatatype x) //任意位置插入数据
{assert(p);  //判断传递的是否为空指针Sqlistcheck(p);  //检查空间是否足够for (int i = p->size;i-1>=da; i--){p->arr[i] = p->arr[i-1];}p->arr[da] = x;p ->size++;   //插入数据,有效数据个数就增加
}

我们对于容量的扩容,一般采用2倍扩容。前提是整数倍,因为内存空间没有小数这一说,当小于2倍时,扩容量较小,数据可能存放不下,当大于2倍时,扩容量较大,空间浪费。所以,我们一般采用2倍扩容,刚好在起始位置上增加1倍空间。

  • test.c :用来测试顺序表的各个功能函数。
#define  _CRT_SECURE_NO_WARNINGS	1
#include "Sqlist.h"
// 可以根据自己的需求来自行测试顺序表的各个函数的功能
void test()
{SL s1;SqlistNit(&s1);   		//给大家举个顺序表插入数据的例子Sqlistpushback(&s1,2);Sqlistpushback(&s1,2);Sqlistpushback(&s1,2);Sqlistpushback(&s1,2);my_printf(&s1);
}
int main()
{test();return 0;
}

结果运行图:在这里插入图片描述

  • 总结因为动态顺序表的空间和数组一样,所以我们就可以可以通过++- -来对空间进行访问。我们要注意传递的指针是否为空指针,当删除或插入数据时,要注意有效数据个数的变化。
  • 对于动态内存开辟不懂得同学可以查看:点击:《动态内存管理》。
  • 对于指针(一级和二级指针)不懂得同学可以查看:点击:《深入理解指针1》.

顺序表问题与思考

  • 中间/头部的插入删除,时间复杂度为O(n).
  • 增容需要申请新空间,拷贝数据,释放就空间,会有不小的消耗,执行效率不是很好。
  • 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再插入5个数据后,那么就会有95个空间浪费了。思考一下:我们该怎样解决以上的问题呢?预告:下期《链表》就会解决的

彩蛋时刻!!!

给大家听个欢快的曲子,给大家放松放松一下:机器人之梦:《September》在这里插入图片描述
每章一句人生漫长,祝我们都可爱的不像话!感谢你能看到这里,点赞+关注+收藏+转发是对我最大的鼓励,咱们下期见!!!

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

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

相关文章

学习文档(6)

Redis数据类型 Redis 常用的数据类型有哪些&#xff1f; Redis 中比较常见的数据类型有下面这些&#xff1a; 5 种基础数据类型&#xff1a;String&#xff08;字符串&#xff09;、List&#xff08;列表&#xff09;、Set&#xff08;集合&#xff09;、Hash&#xff08;散…

影楼即将倒闭!!!!stable diffusion comfyui制作:AI人像摄影专业工作流

最近我们在学习ComfyUI&#xff0c;并用它搭建的摄影写真工作流&#xff0c;只需几张照片即可生成可交付的艺术写真照。 AI写真有以下好处&#xff1a; 创意无限&#xff1a;AI写真可以创造出超越现实的场景和效果&#xff0c;为用户提供更多的创意空间。用户可以通过简单的输…

MySQL 读写分离

优质博文&#xff1a;IT-BLOG-CN 一、背景 随着机票业务不断增长&#xff0c;订单库的读性能遇到了挑战&#xff0c;因此对订单库进行读写分离操作。主要目的是提高数据库的并发性能和可扩展性。当系统的所有写操作效率尚可&#xff0c;读数据请求效率较低时&#xff0c;比如…

快速解决Windows端口被占用

检查占用的端口号,显示9210端口被占用 使用运行打开cmd&#xff0c;直接输入如下命令 netstat -ano | find "9210"可以看到 9210端口执行的进程是PID为26836 知道PID后打开电脑的任务管理器-详细信息,找到PID是26836的进程,可以看到是QQ,关掉就解决了

微软开源项目 Detours 详细介绍与使用实例分享

目录 1、Detours概述 2、Detours功能特性 3、Detours工作原理 4、Detours应用场景 5、Detours兼容性 6、Detours具体使用方法 7、Detours使用实例 - 使用Detours拦截系统库中的UnhandledExceptionFilter接口,实现对程序异常的拦截 C++软件异常排查从入门到精通系列教程…

路由通信 的 VLAN技术

一、VLAN基础 虚拟局域网&#xff08;Virtual Local Area Network&#xff0c;VLAN&#xff09; 根据管理功能、组织机构或应用类型对交换局域网进行分段而形成的逻辑网络。 交换机最多支持4094个VLAN&#xff0c;其中默认管理VLAN是VLAN1&#xff0c;不能创建&#xff0c;也…

Python爬虫使用示例-古诗词摘录

一、分析需求 目标地址&#xff1a; https://www.sou-yun.cn/Query.aspx?typepoem&id二、提取诗句 import os import re import requests import parsel#url https://www.sou-yun.cn/PoemIndex.aspx?dynastyTang&author14976&typeJie urlhttps://www.sou-yun.…

关于md5强比较和弱比较绕过的实验

在ctf比赛题中我们的md5强弱比较的绕过题型很多&#xff0c;大部分都是结合了PHP来进行一个考核。这一篇文章我将讲解一下最基础的绕过知识。 MD5弱比较 比较的步骤 在进行弱比较时&#xff0c;PHP会按照以下步骤执行&#xff1a; 确定数据类型&#xff1a;检查参与比较的两…

【文心智能体 | AI大师工坊】如何使用智能体插件,完成一款购物类智能体的开发,来体验一下我的智能体『科技君Tom』

目录 1.1、智能体运行效果1.2、创作灵感来源智能体平台拥有个人化且人性化的大致框架&#xff0c;可以让小白也能搭建出一个智能体其次是拥有丰富的插件&#xff0c;可以更加快速的得到自己想要的效果~ 1.3、如何制作智能体常见问题与解决方案关于人设与回复逻辑插件使用模型的…

【02】Windows特殊权限-Trustedinstaller

知识点&#xff1a; “TrustedInstaller” 是 Windows 操作系统中的一个特殊账户&#xff0c;用于管理和保护重要的系统文件。它是 Windows 模块安装程序 (Windows Modules Installer) 的一部分&#xff0c;负责安装、修改和删除 Windows 更新和可选组件。默认情况下&#xff…

【Java SE 】类和对象详解

&#x1f525;博客主页&#x1f525;&#xff1a;【 坊钰_CSDN博客 】 欢迎各位点赞&#x1f44d;评论✍收藏⭐ 目录 1&#xff0c; 面向对象认识 1.1 什么时面向对象 1.2 面向对象和面向过程 1.2.1 一个例子理解对象和过程 1. 对于电脑来说 2. 对于我们人来说 2. 类的定…

linux用户态条件变量和内核态完成变量

如果我们的线程要等一个条件满足之后才可以继续向下执行&#xff0c;这个条件不满足的话&#xff0c;就要等待这个条件。这种场景经常见到&#xff0c;比如我们使用recv接收网络数据的时候&#xff0c;或者使用epoll_wait来等待事件的时候&#xff0c;在默认情况下&#xff0c;…

双指针 — 复写零

目录 1. 题目解析 2. 算法讲解 1.算法原理 2.“异地”操作 3.“就地”操作 误解 正解 从后往前完成复写操作 找到最后一个复写的数 处理边界情况 3. 编写代码 正解顺序 1.找到最后一个复写的数 2.处理边界情况 3.从后往前完成复写操作 性能分析&#xff1a; …

【白话文通俗易懂搞明白并解决】跨域问题

文章目录 跨域出现的场景跨域的定义解决跨域的方法方法一&#xff1a;JSONP方法二&#xff1a;添加响应头方法三&#xff1a;通过nginx代理跨域 跨域过滤器代码示例 跨域出现的场景 在前后端分离项目中&#xff0c;经常会出现跨域问题&#xff0c;表现为&#xff1a; 当在浏览…

拟声 0.37.0 | 拟物风格,超级优美,功能丰富

拟声是一款功能丰富的音视频播放器&#xff0c;支持多种音频来源&#xff0c;并具备独特的歌词弹幕、音源转换、跨设备共享与控制等功能。其创新的LRC歌词编解码器和新拟物风格的UI设计为用户提供了一个全新的视听体验。 大小&#xff1a;36M 百度网盘&#xff1a;https://pan…

7.存储过程中的事务管理(7/10)

1.引言 在现代信息技术快速发展的今天&#xff0c;数据库已经成为存储和管理数据的核心工具。无论是企业级应用、电子商务平台还是个人项目&#xff0c;数据库都扮演着不可或缺的角色。在这些应用中&#xff0c;数据的完整性、一致性和可靠性是至关重要的。这就引出了数据库事…

vue3--通用组件 popup 封装

在业务场景中,假设这里我们要实现点击 汉堡 后,会有一个自下而上的popup弹出层 因此这里我们需要先实现这样的一个公共的popup弹出层 那么我们这里的popup弹出层需要具备以下能力: 当popup展开时,内容视图应该不属于任何一个组件内部,而应该直接被插入到body下,这里需要…

【C++11】可变模板参数详解

个人主页&#xff1a;chian-ocean 文章专栏 C 可变模板参数详解 1. 引言 C模板是现代C编程中一个非常强大且灵活的工具。在C11标准中&#xff0c;引入了可变模板参数&#xff08;variadic templates&#xff09;&#xff0c;它为模板编程带来了革命性改变。它的出现允许我们…

【英特尔IA-32架构软件开发者开发手册第3卷:系统编程指南】2001年版翻译,1-8

文件下载与邀请翻译者 学习英特尔开发手册&#xff0c;最好手里这个手册文件。原版是PDF文件。点击下方链接了解下载方法。 讲解下载英特尔开发手册的文章 翻译英特尔开发手册&#xff0c;会是一件耗时费力的工作。如果有愿意和我一起来做这件事的&#xff0c;那么&#xff…

FlinkCDC 实现 MySQL 数据变更实时同步

文章目录 1、基本介绍2、代码实战2.1、数据源准备2.2、代码实战2.3、数据格式 1、基本介绍 Flink CDC 是 Apache Flink 提供的一个功能强大的组件&#xff0c;用于实时捕获和处理数据库中的数据变更。可以实时地从各种数据库&#xff08;如MySQL、PostgreSQL、Oracle、MongoDB…