当前位置: 首页 > 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;被称为"无类…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...

__VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined.

这个警告表明您在使用Vue的esm-bundler构建版本时&#xff0c;未明确定义编译时特性标志。以下是详细解释和解决方案&#xff1a; ‌问题原因‌&#xff1a; 该标志是Vue 3.4引入的编译时特性标志&#xff0c;用于控制生产环境下SSR水合不匹配错误的详细报告1使用esm-bundler…...

第22节 Node.js JXcore 打包

Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本&#xff0c;基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...