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

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

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

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

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...