首页 > 编程学习 > 常见的数据结构基本介绍

常见的数据结构基本介绍

发布时间:2022/11/27 9:57:10

文章目录

  • 常见的数据结构介绍
    • 栈和队列的介绍
    • 数组数据结构
    • 链表数据结构
    • 二叉树和二叉查找树
    • 平衡二叉树
    • 红黑树结构

常见的数据结构介绍

数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。

通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率

常见的数据结构有如下几种:

  • 队列
  • 数组
  • 链表
  • 二叉树
  • 二叉查找树
  • 平衡二叉树
  • 红黑树

栈和队列的介绍

栈数据结构的执行特点

后进先出,先进后出

栈数据结构分为栈顶和栈底, 数据从栈顶进栈顶出

在这里插入图片描述

数据进入栈模型的过程称为:压/进栈; 数据离开栈模型的过程称为:弹/出栈

例如下图, 我们按照顺序分别将数据A、数据B、数据C、数据D压入栈模型中:

  • 先压入栈的在下面, 后压入栈的在上面

在这里插入图片描述

后进先出, 先进后出, 所以弹出栈时, 是数据D先弹出

在这里插入图片描述

队列数据结构的特点:

先进先出,后进后出

队列数据有两端开口, 一端称为前端, 一端称为后端

在这里插入图片描述

数据从后端进入队列模型的过程称为入队列:

在这里插入图片描述

数据从前端离开队列模型的过程称为出队列:

数组数据结构

常见数据结构之数组

数组内存中的一块连续区域

在这里插入图片描述

数组是一种查询快,增删慢的模型

查询速度快: 查询数据通过地址值和索引定位,查询任意数据耗时相同**。**(元素在内存中是连续存储的)

删除效率低:要将原始数据删除,同时后面每个数据前移。

添加效率极低:添加位置后面的每个数据需要后移,再添加元素。

链表数据结构

链表的特点:

链表中的元素是在内存中不连续存储的,每个元素节点包含数据值和下一个元素的地址。

链表查询慢: 因为无论查询哪个数据都要从头开始找

在这里插入图片描述

添加链表的流程:

在这里插入图片描述

链表的增删数据相对比较快:

添加数据的流程

在这里插入图片描述

删除数据的流程

在这里插入图片描述

链表的种类:

链表又分为单向链表和双向链表:

  • 单向链表: 从前往后的查找
  • 双向链表: 既可以从前往后的查找, 也可以从后往前的查找

在这里插入图片描述

二叉树和二叉查找树

二叉树的特点:

只能有一个根节点,每个节点最多支持2个直接子节点。

节点的度:节点拥有的子树的个数称为节点的度,二叉树的度不大于2, 叶子节点度为0的节点,也称之为终端结点。

高度:终端结点的高度为1,终端结点的父节点高度为2,以此类推,根节点的高度最高。

层:根节点在第一层,以此类推

兄弟节点 :拥有共同父节点的节点互称为兄弟节点

二叉树结构类似于如下模型:

在这里插入图片描述

二叉查找树又称二叉排序树或者二叉搜索树, 它的特点如下:

每一个节点上最多有两个子节点

左子树上所有节点的值都小于根节点的值

右子树上所有节点的值都大于根节点的值

通俗的讲:

  • 比根节点小的数据存左边
  • 比根节点大的数据存右边
  • 根节点数据一样大的不存

二叉查找树, 提高了检索数据的性能, 是一个增删改查都比较快得数据结构

在这里插入图片描述

平衡二叉树

二叉树查找存在的问题:

比如: 将7, 10, 11, 12, 13按照二叉查找树的规则存入, 会出现瘸子现象,导致查询的性能与单链表一样,查询速度变慢!

在这里插入图片描述

平衡二叉树:

平衡二叉树是在满足查找二叉树的大小规则下,让树尽可能矮小,以此提高查数据的性能。

在这里插入图片描述

平衡二叉树有如下要求:

任意节点的左右两个子树的高度差不超过1,任意节点的左右两个子树都是一颗平衡二叉树

识别如下是否是平衡二叉树:

在这里插入图片描述

平衡二叉树在添加元素后可能导致不平衡:

基本策略是进行左旋,或者右旋保证平衡。

平衡二叉树-旋转的四种情况

左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡

左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡

右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡

右左: 当根节点右子树的左子树有节点插入,导致二叉树不平衡

在这里插入图片描述

红黑树结构

红黑树概述:

红黑树是一种自平衡的二叉查找树,是计算机科学中用到的一种数据结构。

1972年出现,当时被称之为平衡二叉B树。1978年被修改为如今的"红黑树"。

每一个节点可以是红或者黑;红黑树不是通过高度平衡的,它的平衡是通过“红黑规则”进行实现的。

在这里插入图片描述

红黑规则:

每一个节点或是红色的,或者是黑色的,根节点必须是黑色

如果一个节点没有子节点或者父节点, 则该节点相应的指针属性值为NIL, 这些NIL视为叶节点, 叶节点是黑色的

如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况, 可以两个黑色相连)。

对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。

红黑树每一个节点会多一个字段来标识颜色:

在这里插入图片描述

添加节点: 添加的节点的颜色,可以是红色的,也可以是黑色的。默认用红色效率高。

红黑树小结:

红黑树不是高度平衡的,它的平衡是通过"红黑规则"进行实现的

规则如下:

每一个节点或是红色的,或者是黑色的,根节点必须是黑色, 默认添加元素时使用的是红色

如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的;

如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况, 黑色可以相连)

对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。

红黑树增删改查的性能都很好
总结: 各种数据结构的特点和作用是什么样的

队列:先进先出,后进后出。

栈:后进先出,先进后出。

数组:内存连续区域,查询快,增删慢。

链表:元素是游离的,查询慢,首尾操作极快。

二叉树:永远只有一个根节点, 每个结点不超过2个子节点的树。

查找二叉树:小的左边,大的右边,但是可能树很高,查询性能变差。

平衡查找二叉树:让树的高度差不大于1,增删改查都提高了。

红黑树(就是基于红黑规则实现了自平衡的排序二叉树)

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式