数据结构基础

目录

1、线性表

1.1、数组

1.2、链表

1.3、栈

1.4、队列

2、散列表

3、树

3.1、二叉树

3.1.1、存储原理

3.1.2、红黑树

a、平衡二叉树和红黑树

b、红黑树特征

c、左旋

d、右旋

e、颜色反转

3.1.3、二叉堆

3.1.4、二叉树的遍历

a、深度优先遍历

b、广度优先遍历

3.2、多路查找树

3.2.1、B树

3.2.2、B+树

4、图

4.1、基本概念

4.2、图的存储

4.2.1、邻接矩阵

无向图

有向图

带权图

4.2.2、邻接表

 4.3、图的遍历

 4.3.1、深度优先搜索(DFS)

4.3.2、广度优先搜索(BFS)

1、线性表

1.1、数组

  • 概念:有限个相同类型的变量所组成的有序集合。下标从零开始。
  • 存储原理:用一组连续的内存空间来存储一组具有相同类型的数据。
  • 元素访问:O(1),根据下标访问数据。首地址(假设为1000),数组类型(假设为int:4字节),那么第3个元素的地址为 1000 + (3-1)*4 = 1008。
  • 操作:读取元素、更新元素、插入元素、删除元素。
  • 时间复杂度:读取和更新->O(1),插入和删除->O(n)。
  • 优缺点:根据下标的随机访问很高效;但插入和删除操作,可能会导致大量元素被迫移动,效率较低。扩容时,需要重新申请内存进行存储,原空间就没用了。

1.2、链表

  • 概念:非连续的、非顺序的数据结构,由若干个节点组成。链表由一系列结点组成,每个结点包含一个存储元素的数据域和一个存储下一个结点地址的指针域。常见链表有单链表、双向链表、循环链表。
  • 存储原理:结点在内存中随机存储,通过每个结点中的指针域,将零碎的链表空间,进行关联。
  • 操作:查找结点、更新结点、插入结点、删除结点。
  • 时间复杂度:查找结点->O(n),插入/更新/删除结点->O(1)。
  • 优缺点:插入、删除、更新效率高,不需要连续的内存空间。但查询效率较低。

1.3、栈

  • 概念:线性数据结构,栈中元素只能先入后出。最早进入的元素的位置叫做栈底,最后进入的元素的位置叫做栈顶。
  • 存储原理:数组和链表都可以作为栈的底层数据结构。数组实现的栈也称为顺序栈或静态栈,链表实现的栈也称为链式栈或动态栈。
  • 操作:入栈(push)、出栈(pop)。
  • 时间复杂度:入栈/出栈->O(1)。

1.4、队列

  • 概念:线性数据结构,队列中元素只能先入先出。队列的出口端叫做队头,队列的入口端叫做队尾。
  • 存储原理:数组和链表都可以实现队列。用数组实现的队列也叫做顺序队列,用链表实现的队列也叫做链式队列。
  • 操作:入队(enquene)、出队(dequeue)。
  • 时间复杂度:入队/出队->O(1)。

2、散列表

  • 概念:也叫做哈希表,提供了key-value的映射关系。可以通过key,高效查询出其对应的value。
  • 存储原理:散列表本质上是一个数组。通过hash函数把key转换成数组下标,作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值。数组固定时,可快速检索;数组变化时,需要对全部数据重新hash。(可通过一致性Hash算法进行改进)
  • 优缺点:读写快,但Hash表中的元素是无序的,当遇到扩容时,需要重新计算所有元素的Hash值。
  • 应用:HashMap、Redis字典、布隆过滤器、位图。
  • 时间复杂度

        写操作:O(1) + O(m) = O(m) m为单链元素个数

        读操作:O(1) + O(m) m为单链元素个数

        Hash冲突写单链表:O(m)

        Hash扩容:O(n) n是数组元素个数 rehash

        Hash冲突读单链表:O(m) m为单链元素个数

  • 操作
    • 写操作(put)

                向散列表插入新的键值对。

                ①:通过hash函数,将key转换成数组下标;

                ②:将键值对插入对应的数组下标所在位置。

  • Hash冲突(碰撞)

                不同的key通过hash函数,得到相同的数组下标,该场景就被称为Hash冲突。Hash冲突可通过如下两种方式解决:

                ①:开放寻址法:当一个key通过Hash函数获得的对应的数组下标已经被占用时,就寻找下一个空档位置进行存储;

                ②:链表法:当发生Hash冲突时,将Hash冲突的多个键值对,使用链表进行存储。

  • 读操作(get)

                通过给定的key,在散列表中查询对应的value。

                ①:通过Hash函数,将key转换成数组下标;

                ②:找到数组下标对应的Entry,如果key不正确,说明有Hash冲突,通过链表头遍历该单链表,根据key值找到对应value。

  • Hash扩容

                Capacity:HashMap的当前长度。

                LoadFactor:HashMap的负载因子(阈值),默认值为0.75f。

                当HashMap.Size >= Capacity×LoadFactor时,需要进行扩容。

                ①:数组扩容,创建一个新的Entry空数组,长度是原数组的2倍。

                ②:对原数组的所有元素进行再Hash,把所有元素放入新的数组中。

3、树

  • 树是N(N>=0)个节点的有限集合,树的顶部有且仅有一个节点,称为根。
  • 当N = 0时,称为空树。
  • 当N != 0时,其余节点又可分为m个互不相交的有限集合(子树)。
  • 常见的树有二叉树、多路树、堆等。

3.1、二叉树

二叉树
满二叉树
完全二叉树
二叉查找树
  • 二叉树:树的每个节点最多有两个孩子节点,分别称为左孩子和右孩子,且左孩子必然小于右孩子。
  • 满二叉树:树的所有非叶子节点都有左右孩子,且所有叶子节点在同一层级。
  • 完全二叉树:类比满二叉树,编号位置与满二叉树一样,且编号连续的树,称为完全二叉树。
  • 二叉查找树:左孩子小于父节点,右孩子大于父节点。查询和插入的时间复杂度为O(logn)。

3.1.1、存储原理

链表存储
数组存储
  • 逻辑存储结构,可使用数组和链表进行存储。
  • 链表存储(常见二叉树):每个Node包含:节点数据、指向左孩子的指针、指向右孩子的指针。
  • 数组存储(完全二叉树):根节点为下标为0的数组位置,然后从上往下,从左往右依次标记下标位置。若父节点下标 = n,左孩子节点下标 = 2 * n + 1,右孩子节点下标 = 2 * (n+1)。

3.1.2、红黑树

a、平衡二叉树和红黑树

  • 平衡二叉树:在二叉树的基础上,每次新增节点的时候,都会通过左旋和右旋操作,来保证左子树和右子树的高度差不超过1,防止二叉树退化成链表。
  • 红黑树:一种特殊的平衡二叉树。
平衡二叉树
红黑树

b、红黑树特征

  1. 每一个节点,要么是黑色的,要么是红色的;
  2. 根节点是黑色的;
  3. 叶子节点(空)是黑色的;
  4. 红色节点不能连续存在;
  5. 从一个节点到它的任意根节点,所经过的黑色节点数必须是相同的。

在插入节点时,会通过变色和旋转两种操作,来保证红黑树满足上述五个条件。

红黑树是一种弱平衡二叉树,相对于平衡二叉树,插入和删除时旋转次数少,所以在插入和删除较多的情况下,使用红黑树;而在修改少,查找次数多的情况下,使用平衡二叉树。

c、左旋

  1. X为基点逆时针旋转
  2. X的父节点被x原来的右孩子Y取代
  3. c保持不变
  4. Y节点原来的左孩子c变成X的右孩子

d、右旋

  1. X为基点顺时针旋转
  2. X的父节点被x原来的左孩子Y取代
  3. b保持不变
  4. Y节点原来的右孩子c变成X的左孩子

e、颜色反转

        当前节点与父节点、叔叔节点同为红色,这种情况违反了红黑树的规则,需要将红色向祖辈上传, 父节点和叔叔节点红色变为黑色,爷爷节点从黑色变为红色(爷爷节点必为黑色,因为此前是符合红黑 树规则的)。这样每条叶子结点到根节点的黑色节点数量并未发生变化,因此都其他树结构不产生影响。

3.1.3、二叉堆

大顶堆
小顶堆
数组存储
  • 二叉堆本质上是一种完全二叉树。
  • 大顶堆:任何一个父节点的值,都大于或等于其左、右孩子节点的值。堆顶是整个堆中的最大元素。
  • 小顶堆:任何一个父节点的值,都小于或等于其左、右孩子节点的值。堆顶是整个堆中的最小元素。
  • 存储原理:数组存储。完全二叉树的编号从上往下、从左往右连续,所以可直接通过数组存储。

3.1.4、二叉树的遍历

a、深度优先遍历

  • 前序遍历(链表实现):输出顺序为:根节点->左孩子->右孩子:1 2 4 5 3 6
  • 中序遍历(链表实现):输出顺序为:左孩子->根节点->右孩子:4 2 5 1 3 6
  • 后序遍历(链表实现):输出顺序为:左孩子->右孩子->根节点:4 5 2 6 3 1

b、广度优先遍历

  • 层序遍历(队列实现):从根节点开始,从上往下、从左往右依次遍历:1 2 3 4 5 6

3.2、多路查找树

树的每一个节点的孩子数可以多余两个,且每一个节点可以存储多个元素。

3.2.1、B树

        对二叉查找树进行了改进,将相关的数据尽量集中在一起,以便一次读取多个数据,减少硬盘的操作次数。

  • B树中所有节点的孩子节点数中的最大值称为B树的阶,记为M
  • 树中的每个节点至多有M棵子树 ---即:如果定了M,则这个B树中任何节点的子节点数量都不能超M
  • 若根节点不是终端节点,则至少有两棵子树
  • 除根节点和叶节点外,所有点至少有m/2棵子树
  • 所有的叶子结点都位于同一层

3.2.2、B+树

  • 非叶子结点的子树指针与关键字个数相同
  • 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树
  • 为所有叶子结点增加一个链指针
  • 所有关键字都在叶子结点出现

4、图

4.1、基本概念

  • 一种复杂的非线性表结构。
  • 顶点:图中元素叫做顶点。
  • 边:两个顶点之间建立的连接关系,叫做边。
  • 度:与顶点相连的边的条数叫做度。
  • 有向图:边有方向的图,比如A到B的直线距离,微信的添加好友。
  • 无向图:边无方向的图,比如网络拓扑图。
  • 带权图:每条边都带有一个权重,可利用权重表示一些可以度量的值,比如qq两个用户之间的亲密度。

4.2、图的存储

4.2.1、邻接矩阵

        邻接矩阵,底层是一个二维数组。

无向图

假设二维数组为arr[],如果顶点i与顶点j之间有边,则将arr[i][j]与arr[j][i]标记为1。

有向图

假设二维数组为arr[],如果右箭头从顶点i指向顶点j,则将arr[i][j]标记为1。

带权图

与无向图类似,只不过存储的值不是1,而是两个顶点相连的权重值。

4.2.2、邻接表

  •         邻接矩阵,在存储无向图时,a[i][j] = a[j][i],浪费一半存储空间
  •         邻接表,底层结构为数组 + 链表。
  •        所有顶点构成一个数组。
  •         每个顶点对应一个链表,链表元素为与当前顶点相连的其他顶点值与权重。

 4.3、图的遍历

 4.3.1、深度优先搜索(DFS)

        从起点出发,选择一个与之相连的顶点,不断向前走,直到无法继续为止;然后尝试其他未走过的顶点,直到走到终点为止。

        DFS解决的是连通性的问题,即给定一个起点和一个终点,判断是否存在一条路径能从起点连接到终点。

        深度优先搜索,可利用 栈(先进后出) 进行实现。

假设以顶点A为起点进行深度遍历:

  1. 输出A,A入栈,栈中元素为A,输出元素为A;
  2. 与A相连的有BDG,选择顶点B,输出B,B入栈,栈中元素为A->B,输出元素为A B;
  3. 与B相连的有EF,选择顶点E,输出E,E入栈,栈中元素为A->B->E,输出元素为A B E;
  4. 与E相连的未读取的顶点有G,输出G,G入栈,栈中元素为A->B->E->G,输出元素为A B E G;
  5. 没有与G相连的未读取的顶点,G出栈,栈中元素为A->B->E,输出元素为A B E G;
  6. 没有与E相连的未读取的顶点,E出栈,栈中元素为A->B,输出元素为A B E G;
  7. 与B相连的未读取的顶点有F,输出F,F入栈,栈中元素为A->B->F,输出元素为A B E G F;
  8. 与F相连的未读取的顶点有CD,输出C,C入栈,栈中元素为A->B->F->C,输出元素为A B E G F C;
  9. 与C相连的未读取的顶点有H,输出H,H入栈,栈中元素为A->B->F->C->H,输出元素为A B E G F C H;
  10. 没有与H相连的未读取的顶点,H出栈,栈中元素为A->B->F->C,输出元素为A B E G F C H;
  11. 没有与C相连的未读取的顶点,C出栈,栈中元素为A->B->F,输出元素为A B E G F C H;
  12. 与F相连的未读取的顶点有D,输出D,D入栈,栈中元素为A->B->F->D,输出元素为A B E G F C H D;
  13. 所有元素均已访问完,D出栈、F出栈、B出栈、A出栈,输出元素为A B E G F C H D。

4.3.2、广度优先搜索(BFS)

        先查找离顶点最近的,然后是次近的,依次往外搜索。

        BFS解决的是最短路径问题。

        可使用 队列(先进先出)实现广度优先搜索。

假设以顶点A为起点进行广度遍历:

  1. A入队,队列元素有A,输出为空;
  2. 输出A,A出队,放入与A相关联的BDG元素,输出为A,队列元素有BDG;
  3. 输出B,B出队,放入与B相关联的EF元素,输出为AB,队列元素有DGEF;
  4. 输出D,D出队,没有与D相关联的未读取的元素,输出为ABD,队列元素有GEF;
  5. 输出G,G出队,没有与G相关联的未读取的元素,输出为ABDG,队列元素有EF;
  6. 输出E,E出队,没有与E相关联的未读取的元素,输出为ABDGE,队列元素有F;
  7. 输出F,F出队,放入与F相关联的未读取的元素C,输出为ABDGEF,队列元素有C;
  8. 输出C,C出队,放入与C相关联的未读取的元素H,输出为ABDGEFC,队列元素有H;
  9. 输出H,H出队,没有与H相关联的未读取的元素,输出为ABDGEFCH,队列元素为空。

以上内容为个人学习理解,如有问题,欢迎在评论区指出。

部分内容截取自网络,如有侵权,联系作者删除。

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

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

相关文章

洛谷 P3375 【模板】KMP 字符串匹配

题目描述 给出两个字符串 s1​ 和 s2​,若 s1​ 的区间 [l,r] 子串与 s2​ 完全相同,则称 s2​ 在 s1​ 中出现了,其出现位置为 l。 现在请你求出 s2​ 在 s1​ 中所有出现的位置。 定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串…

4 三组例子,用OpenCV玩转图像-AI-python

读取,缩放,旋转,写入图像 首先导入包,为了显示导入matplotlib/为了在matplotlib显示 导入CV2/查看版本 导入图片/查看图片类型 图片数组 数组大小 对于opencv通道顺序蓝色B、绿色G、红色R matplotlib通道顺序为 红色R、绿色G、蓝…

无涯教程-Perl - delete函数

描述 此函数从哈希中删除指定的键和关联的值,或从数组中删除指定的元素。该操作适用于单个元素或切片。 语法 以下是此函数的简单语法- delete LIST返回值 如果键不存在,并且与已删除的哈希键或数组索引关联的值,则此函数返回undef。 Perl 中的 delete函数 - 无涯教程网无…

机器学习---概述(二)

文章目录 1.模型评估1.1 分类模型评估1.2 回归模型评估 2. 拟合2.1 欠拟合2.2 过拟合2.3 适当拟合总结: 3.深度学习3.1层次(Layers):3.2 神经元(Neurons):3.3 总结 1.模型评估 模型评估是机器学…

【Python】Locust持续优化:InfluxDB与Grafana实现数据持久化与可视化分析

目录 前言 influxDB 安装运行InfluxDB 用Python 上报数据到influxdb ocust 数据写入到 influx Locust的生命周期 上报数据 优化升级 配置Grafana 总结 资料获取方法 前言 在进行性能测试时,我们需要对测试结果进行监控和分析,以便于及时发现问…

项目实战 — 消息队列(4){消息持久化}

目录 一、消息存储格式设计 🍅 1、queue_data.txt:保存消息的内容 🍅 2、queue_stat.txt:保存消息的统计信息 二、消息序列化 三、自定义异常类 四、创建MessageFileManger类 🍅 1、约定消息文件所在的目录和文件名…

迅为全国产龙芯3A5000电脑运行统信UOS、银河麒麟、loongnix系统

iTOP-3A5000开发板采用全国产龙芯3A5000处理器,基于龙芯自主指令系统 (LoongArch) 的LA464微结构,并进一步提升频率,降低功耗,优化性能。在与龙芯3A4000处理器保持引脚兼容的基础上,频率提升至2.5GHZ,功耗降…

谷粒商城第九天-解决商品品牌问题以及前后端使用检验框架检验参数

目录 一、总述 二、商品分类问题 三、前端检验 四、后端检验 五、总结 一、总述 在完成完商品分类的时候,后来测试的时候还是发现了一些问题,现在将其进行解决,问题如下: 1. 取消显示的时候,如果取消了显示&…

九度OJ → 题目1368:二叉树中和为某一值的路径 ← DFS

【题目来源】 由于九度OJ(http://ac.jobdu.com/)已经永久关闭,故无法在其上进行在线提交代码。 幸运的是,在AcWing上有此题目“二叉树中和为某一值的路径”,但描述有些不同。可详见:https://www.acwing.com…

redis 集群 1:李代桃僵 —— Sentinel

目前我们讲的 Redis 还只是主从方案,最终一致性。读者们可思考过,如果主节点凌晨 3 点突发宕机怎么办?就坐等运维从床上爬起来,然后手工进行从主切换,再通知所有的程序把地址统统改一遍重新上线么?毫无疑问…

绿色项目管理:为环境和效益双赢

绿色项目管理:为环境和效益双赢 在21世纪的今天,我们正面临着各种全球性的环境问题,从气候变化到资源枯竭。作为项目经理,我们有责任和机会确保我们的项目对环境的影响最小,并在可能的情况下为环境做出积极的贡献。 …

P9503 『MGOI』Simple Round I | B. 魔法照相馆

题目背景 照片留下了值得留恋的瞬间,但对于魔法士来说最重要的是向前看。——殿堂魔法士 W 题目描述 小 M 正在准备入学所必需的魔法士证件,因此他来到了纵深巷的魔法照相馆。 在等待的时候,小 M 注意到魔法照相馆有三个幕布,颜…

建筑行业是不是一个夕阳产业?一建值得考吗?

建筑行业行业是不是夕阳产业,提出这个问题的人已经了解了现在建筑行业的不景气,从3年疫情到放开疫情管控,2023年是疫情放开后最好的一年。 建筑上下游各产业链行业失业率攀升,房屋建筑土地没人卖,多修建公共建筑&…

RISC-V公测平台发布:如何在SG2042上玩转OpenMPI

About HS-2 HS-2 RISC-V通用主板是澎峰科技与合作伙伴共同研发的一款专为开发者设计的标准mATX主板,它预装了澎峰科技为RISC-V高性能服务器定制开发的软件包,包括各种标准bencmark、支持V扩展的GCC编译器、计算库、中间件以及多种典型服务器应用程序。…

音频客观感知MOS对比,对ViSQOL、PESQ、MosNet(神经网络MOS分)和polqa一致性对比和可信度验证

原创:转载需附链接: https://blog.csdn.net/qq_37100442/article/details/132057139?spm1001.2014.3001.5502 一、背景 Mos分评价音质重要指标,最近也有很多机构和公司在研究适合自己的评价体系。目前Mos分主要分为主观评测和客观感知评价。…

6.6 实现卷积神经网络LeNet训练并预测手写体数字

模型架构 代码实现 import torch from torch import nn from d2l import torch as d2lnet nn.Sequential(nn.Conv2d(1,6,kernel_size5,padding2),nn.Sigmoid(),#padding2补偿5x5卷积核导致的特征减少。nn.AvgPool2d(kernel_size2,stride2),nn.Conv2d(6,16,kernel_size5),nn.S…

黑马大数据学习笔记5-案例

目录 需求分析背景介绍目标需求数据内容DBeaver连接到Hive建库建表加载数据 ETL数据清洗数据问题需求实现查看结果扩展 指标计算需求需求指标统计 可视化展示BIFineBI的介绍及安装FineBI配置数据源及数据准备 可视化展示 P73~77 https://www.bilibili.com/video/BV1WY4y197g7?…

宋浩概率论笔记(三)随机向量/二维随机变量

第三更:本章的内容最重要的在于概念的理解与抽象,二重积分通常情况下不会考得很难。此外,本次暂且忽略【二维连续型随机变量函数的分布】这一章节,非常抽象且难度较高,之后有时间再更新。

回归决策树模拟sin函数

# -*-coding:utf-8-*- import numpy as np from sklearn import tree import matplotlib.pyplot as pltplt.switch_backend("TkAgg") # 创建了一个随机数生成器对象 rng rngnp.random.RandomState(1) print("rng",rng) #5*rng.rand(80,1)生成一个80行、1列…

恒盛策略:上交所过户费收费标准?

随着我国股市的发展,股票买卖所的过户费成为了广阔投资者关注的焦点之一。在我国股票商场中,上交所是最重要的买卖所之一,因而上交所过户费的收费规范备受到了广泛关注。那么,上交所过户费的收费规范究竟怎么拟定?对投…