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

考研数据结构笔记(3)

顺序表存储结构

  • 存储结构
    • 顺序结构
      • 定义
      • 基本操作的实现
        • 静态分配
          • 问题
        • 动态分配
          • 代码功能
      • 顺序表的特点:
    • 顺序表小结
    • 顺序表的插入删除
      • 插入
      • 删除
      • 小结
    • 顺序表的查找
      • 按位查找
      • 按值查找
      • 小结

存储结构

在这里插入图片描述

顺序结构

定义

在这里插入图片描述

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列(每个数据元素所占空间一样大)。

顺序表一一用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。
在这里插入图片描述
在这里插入图片描述

sizeof(int)= 4B
sizeof(Customer)= 8B

基本操作的实现

静态分配

在这里插入图片描述
在这里插入图片描述

ElemType可以为int类型,float类型。

代码样例:

在这里插入图片描述

在main函数中首先声明一个Sqlist L;(声明一个顺序表),则在内存中分配存储顺序表L的空间。包括:MaxSize*sizeof(ElemType)和存储length的空间,data[]数组的每个元素为4个字节。initlist进行顺序表的初始化。(设置数据元素的默认值为0)

在这里插入图片描述
该步骤出现错误,i值范围应该为L.length,为具体顺序表长度。

如果删去设置数据元素的默认值的步骤。以下代码会出脏数据。

在这里插入图片描述

即对data[]数据内容会出现奇怪的数据(脏数据)。

问题

如果“静态数组”存满了怎么办?

可以放弃治疗,顺序表的表长刚开始确定后就无法更改(存储空间是静态的)

下面介绍动态分配内存。

动态分配

在这里插入图片描述

定义一个指针data,指向顺序表的第一个元素,

代码功能

在这里插入图片描述

定义一个动态分配的顺序表。

在这里插入图片描述

初始化顺序表。

在这里插入图片描述

增加动态数组的长度。

在这里插入图片描述

主函数

在这里插入图片描述还有函数的头文件

内存展示:

在这里插入图片描述
首先进入主函数,seqlist函数用来声明一个顺序表,调用initlist函数申请一片内存空间并初始化顺序表,data指针指向data[0],调用increasesize函数,data指针先指向*P,函数新申请一片空间并让data指向第一个元素,for循环复制原来的函数值,最后free函数释放的原来的顺序表空间。

顺序表的特点:

  • 随机访问,即可以在 o(1) 时间内找到第i个元素。
  • 存储密度高,每个节点只存储数据元素。
  • 拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)。
  • 插入、删除操作不方便,需要移动大量元素。

在这里插入图片描述

顺序表小结

在这里插入图片描述

顺序表的插入删除

在这里插入图片描述

插入

ListInsert(&Li,e): 插入操作。在表L中的第i个位置上插入指定元素e。

代码实现:
在这里插入图片描述

由于用存储位置的相邻来体现数据元素之间的逻辑关系,所以数据元素相邻同样也存储位置的相邻。

内存分配:
在这里插入图片描述

在这里插入图片描述
我们现在在b,d元素之间插入c,表示在data[1]后面插入一个元素,则原来data[2]及以后的元素全部后移一位,然后将c插入到data[2]中。然后length+1。
在这里插入图片描述
整体代码实现:
在这里插入图片描述

在这里插入图片描述

代码改进:用户交互时给予提示
在这里插入图片描述

在这里插入图片描述

删除

ListDelete(&L,i,&e): 删除操作。删除表L中第i个位置的元素并用e返回删除元素的值。

在这里插入图片描述
将元素c删除,并将后面的元素依次向前移一位。
在这里插入图片描述

代码实现:

在这里插入图片描述

首先定义一个顺序表并初始化,然后插入数据,调用listdelete函数将第三个元素删除并将后面的元素依次向前移动。(先移动前面的元素,再移动后面的元素)

在这里插入图片描述

在这里插入图片描述

小结

在这里插入图片描述

顺序表的查找

在这里插入图片描述

按位查找

GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。、

静态分配代码:
在这里插入图片描述
动态分配代码:
在这里插入图片描述

解释了当初为什么malloc函数前面要强制转为int*
在这里插入图片描述

时间复杂度
在这里插入图片描述

按值查找

按值查找操作。在表L中查找具有给定关键字值的元素LocateElem(L,e):

在这里插入图片描述

假设按值查找int类型数字9,但是“==”无法用于结构体数据相同,只能依次比较结构体数据相同或者定义方法来判断。
在这里插入图片描述
在这里插入图片描述

时间复杂度O(n)
在这里插入图片描述

小结

在这里插入图片描述

相关文章:

考研数据结构笔记(3)

顺序表存储结构 存储结构顺序结构定义基本操作的实现静态分配问题 动态分配代码功能 顺序表的特点: 顺序表小结顺序表的插入删除插入删除小结 顺序表的查找按位查找按值查找小结 存储结构 顺序结构 定义 线性表是具有相同数据类型的n(n>0)个数据元素的有限序列(每个数据元素…...

第二讲 数据结构 AcWing 827. 双链表

目录 双链表代码 && 思路 双链表 实现一个双链表,双链表初始为空,支持 5 种操作: 在最左侧插入一个数; 在最右侧插入一个数; 将第 k个插入的数删除; 在第 k 个插入的数左侧插入一个数&#xff1b…...

假期作业 2月6号

一、填空题 1、一个类的头文件如下所示&#xff0c;num初始化值为5&#xff0c;程序产生对象T&#xff0c;且修改num为10&#xff0c;并使用show()函数输出num的值10。 #include <iostream.h> class Test { private: static int num; public: Test(int); void show(); };…...

【wu-lazy-cloud-network】Java自动化内网穿透

项目介绍 wu-lazy-cloud-network 是一款基于&#xff08;wu-framework-parent&#xff09;孵化出的项目&#xff0c;内部使用Lazy ORM操作数据库&#xff0c;主要功能是网络穿透&#xff0c;对于没有公网IP的服务进行公网IP映射 使用环境JDK17 Spring Boot 3.0.2 功能 1.内网…...

【C++】C++入门(二)

个人主页 &#xff1a; zxctsclrjjjcph 文章封面来自&#xff1a;艺术家–贤海林 如有转载请先通知 文章目录 1. 前言2. 缺省参数2.1 缺省参数概念2.2 缺省参数分类 3. 函数重载3.1 函数重载概念3.2 C支持函数重载的原理--名字修饰(name Mangling) 1. 前言 在前面一篇文章中简…...

6.electron之上下文隔离,预加载JS脚本

如果可以实现记得点赞分享&#xff0c;谢谢老铁&#xff5e; Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 Electron 将 Chromium 和 Node.js 嵌入到了一个二进制文件中&#xff0c;因此它允许你仅需一个代码仓库&#xff0c;就可以撰写支持 Windows、…...

【翻译】 Processing的安卓项目构建(译者用的是Android Studio)

原文链接&#xff1a;https://github.com/processing/processing-android/wiki/Building-Processing-for-Android&#xff0c;版本Apr 2, 2023 译者声明&#xff1a;这个文档是开源公开的&#xff0c;协议是GNU协议。译者自己得使用这个文档&#xff0c;所以才翻译的&#xff0…...

华为机考入门python3--(8)牛客8-合并表记录

分类&#xff1a;字典排序 知识点&#xff1a; 将输入转成int的列表 my_list list(map(int, input().strip().split( ))) 将列表转为元组 tuple(my_list) 访问元素为元组的列表 for first, second, third in my_list: 对字典进行排序 sorted(my_dict.items())…...

vue3-内置组件-KeepAlive

KeepAlive <KeepAlive> 是一个内置组件&#xff0c;它的功能是在多个组件间动态切换时缓存被移除的组件实例。 基本使用 默认情况下&#xff0c;一个组件实例在被替换掉后会被销毁。这会导致它丢失其中所有已变化的状态——当这个组件再一次被显示时&#xff0c;会创建…...

RxJava Subject

目录 AsyncSubjectBehaviorSubjectPublishSubjectReplaySubjectSerializedSubjectUnicastSubject 在Rxjava中&#xff0c; Subject可以同时表示Observer和Observable, 允许从单个源到多个子观察者multiple child Observers。 除了 onSubscribe(io.reactivex.disposables.Dispos…...

[N-141]基于springboot,vue网上拍卖平台

开发工具&#xff1a;IDEA 服务器&#xff1a;Tomcat9.0&#xff0c; jdk1.8 项目构建&#xff1a;maven 数据库&#xff1a;mysql5.7 系统分前后台&#xff0c;项目采用前后端分离 前端技术&#xff1a;vueelementUI 服务端技术&#xff1a;springbootmybatis-plusredi…...

新能源光伏发电设计全面解析

伴随碳达峰、碳中和“双碳”政策大力推行&#xff0c;以及新能源市场的利好&#xff0c;目前多个城市在大力推进光伏发电项目&#xff0c;本篇文章将详细介绍关于光伏发电设计的信息。 一、光伏发电概念 光伏发电是指利用太阳辐射能在太阳能电池板上产生的电能&#xff0c;通…...

踩坑实录(Third Day)

临近年关&#xff0c;同事们该回家的也都回家了&#xff0c;所以我对工作的欲望不是很强烈&#xff0c;所以就主要是自己学习了一下&#xff0c;在 B 站看看视频&#xff0c;自己敲代码&#xff0c;所以今天没遇到什么坑&#xff0c;但是可以分享一下之前踩到的两个坑。 此为第…...

Linux联网安装MySQL Server

yum安装 以下代码复制粘贴到控制台即可 yum list | grep mysql-server #查看可以下载的MySQLyum install -y mysql-server #安装MySQLmysql_secure_installation #引导安装 引导安装实例如下 systemctl enable mysqld 设置开机自动启动 systemctl sta…...

使用GDI画图片生成合成图片并调用打印机进行图片打印

使用GDI画图片生成合成图片并调用打印机进行图片打印 新建窗体应用程序PrinterDemo&#xff0c;将默认的Form1重命名为FormPrinter&#xff0c;添加对 Newtonsoft.Json.dll用于读写Json字符串 zxing.dll&#xff0c;zxing.presentation.dll用于生成条形码&#xff0c;二维码…...

【PyQt】04-Designer

文章目录 前言一、初级 Designer1.1 拖拽设计界面1.2 搞定之后记得保存ui文件1.3 载入代码1.4 运行结果 二、登入界面代码效果展示账号密码错误时账号和密码正确 总结 前言 自然还是跟着王铭东老师学的 一、初级 Designer 1.1 拖拽设计界面 进度条是这个 1.2 搞定之后记得保…...

第4节、电机多段转动【51单片机+L298N步进电机系列教程】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;本节介绍用控制步进电机三个主要参数角度、速度、方向&#xff0c;实现简单的步进电机多段控制 一、目标功能 输入多个目标角度&#xff0c;以及每个角度对应的速度&#xff0c;实现步进电机的多段多速…...

算法学习——华为机考题库1(HJ1 - HJ10)

算法学习——华为机考题库1&#xff08;HJ1 - HJ10&#xff09; HJ1 字符串最后一个单词的长度 描述 计算字符串最后一个单词的长度&#xff0c;单词以空格隔开&#xff0c;字符串长度小于5000。&#xff08;注&#xff1a;字符串末尾不以空格为结尾&#xff09; 输入描述&…...

PSQL常用操作

目录 前言 准备工作 添加postgres用户 初始化数据库 启动服务 创建数据库 psql连接数据库 常规操作 数据库 schema相关 插件 其他 前言 老折腾&#xff0c;还是记录点啥吧...... 基于本地PG数据库(打包为绿色版本了)&#xff0c;实操记录&#xff0c;版本pgsql12…...

C++ “万能血“ void*指针

本篇文章我们来介绍一下C “万能血” void指针 为什么说他万能呢&#xff1f; 原因:C void* 是一种特殊的指针类型&#xff0c;可用于存放任意对象的地址。在函数传参中也可以作为任何实参的形参 void型详细介绍 void* 是C中的一种特殊的指针类型&#xff0c;被称为"无类…...

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

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

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

WEB3全栈开发——面试专业技能点P4数据库

一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库&#xff0c;基于 mysql 库改进而来&#xff0c;具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点&#xff1a; 支持 Promise / async-await&#xf…...

轻量级Docker管理工具Docker Switchboard

简介 什么是 Docker Switchboard &#xff1f; Docker Switchboard 是一个轻量级的 Web 应用程序&#xff0c;用于管理 Docker 容器。它提供了一个干净、用户友好的界面来启动、停止和监控主机上运行的容器&#xff0c;使其成为本地开发、家庭实验室或小型服务器设置的理想选择…...