常见数据结构

2023-12-15 16:51:32

数据结构概述

数据结构是计算机底层存储、组织数据的方式,是指数据相互之间是以什么方式排列在一起的。 通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。

栈数据结构的执行特点:后进先出,先进后出。

栈模型:?

压栈:

?

弹栈:

?

队列

队列执行特点:先进先出,后进后出

队列模型:

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

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

数组

元素在内存中是连续存储的。?

获取数据速度快:元素地址=基地址值+索引*每个元素的存储大小,获取任意数据耗时相同。

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

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

链表

特点:

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

链表获取数据慢:无论获取哪个数据都要从头开始找。?(对比数组)

链表增删相对快。(对比数组)

结点的存储结构:

添加一个链表:添加一个数据A,再添加c,再添加D。

在AC之间添加一个数据:

删除C:

链表的种类:

二叉树

二叉树概述

特点:

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

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

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

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

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

二叉查找树

二叉查找树又称二叉排序树或者二叉搜索树。

特点:

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

2,左子节点的值小于当前节点的值

3,右子节点的值大于当前节点的值

目的:提高检索数据的性能。

二叉查找树添加节点:

小的存左边,大的存右边,一样的不存。

平衡二叉树

二叉树查找存在的问题:可能出现瘸子现象,导致查询的性能与单链表一样,查询速度变慢!

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

平衡二叉树的要求:

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

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

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

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

左左

?当根节点左子树的左子树有节点插入,导致二叉树不平衡,做一个右旋,再移动相关结点。

左右

当根节点左子树的右子树有节点插入,导致二叉树不平衡,先子树左旋,再根树右旋,再移动相关结点。

右右

当根节点右子树的右子树有节点插入,导致二叉树不平衡,做一个左旋,再移动相关结点。

右左

当根节点右子树的左子树有节点插入,导致二叉树不平衡,先子树右旋,再根树左旋,再移动相关结点。

红黑树

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

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

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

红黑规则:

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

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

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

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

结点的存储结构:

添加节点:

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

红黑树增删改查的性能都很好。

文章来源:https://blog.csdn.net/daqi1983/article/details/135015703
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。