电脑做ppt一般下载哪个网站好,保定网站建设推广公司怎么样,网页制作师培训学校,动画设计与制作工作文章目录 前言数据结构介绍数组链表队列和栈树堆 总结 前言
数据结构是计算机存储、组织数据的方式。在工作中#xff0c;我们通常会直接使用已经封装好的集合API#xff0c;这样可以更高效地完成任务。但是作为一名程序员#xff0c;掌握数据结构是非常重要的#xff0c;… 文章目录 前言数据结构介绍数组链表队列和栈树堆 总结 前言
数据结构是计算机存储、组织数据的方式。在工作中我们通常会直接使用已经封装好的集合API这样可以更高效地完成任务。但是作为一名程序员掌握数据结构是非常重要的因为它可以帮助我们更好地理解和设计算法从而提高程序的效率和可靠性。本文将对常见的几种数据结构进行介绍通过了解这些数据结构的特点和优势可以更好地在不同场景下选择合适的数据结构。
数据结构介绍
常见的数据结构大体分为两种类型线性和非线性。
线性数据结构见名思义整体结构的图像是一条直线。包括数组、链表、栈、队列等。 非线性数据结构包括树、堆、图等。
数组
数组是由多个元素组成的一个集合表现形式如下图 在内存中存储数组的空间是连续的每个元素占据一定的内存空间这也是为什么在声明数组时要指定长度不然不知道要占用多少空间。以 Java 语言为例当声明一个数组后数组变量会指向数组对象的起始地址也就是第一个元素的位置如下图 以此看来当查询数组中的某个元素时通过下标就可以计算出这个元素的内存地址比如想查找下标为2的元素那么arr[2]的内存地址 arr的内存地址 2 * 元素大小也就可以直接通过内存地址访问元素时间复杂度为O(1)。
但是数组也会带来一个问题由于数组长度是固定的所以在添加或删除元素时会涉及到创建新的数组来替换原数组导致复杂度较高。例如下面的代码演示了如何在数组末尾添加一个元素
int[] arr {1, 2, 3, 4, 5}; arr[arr.length] 6; // 将要添加的元素放到数组的最后一个位置 int[] newArr new int[arr.length 1]; // 创建一个新的数组长度加1 for (int i 0; i newArr.length; i) { newArr[i] arr[i]; // 将原数组中的元素复制到新数组中
} arr newArr; // 使用新数组替换原数组示例代码在内存中的活动如下图 在 Java 中有很多集合的底层实现都是基于数组例如大家常用的 ArrayList、Vector、HashMap、ArrayBlockingQueue等等。
链表
链表由一系列结点组成每个节点包括两个部分一个是存储数据元素的数据域另一个是存储下一个节点地址的指针域。以 Java 为例一个节点的结构是这样表示的
public class NodeT {//存储数据元素的数据域private T value;//下一个节点地址的指针域private Node next;
}每个元素的指针指向下一个元素从而形成链表表现形式如下图。 与数组不同链表在内存中是非连续的空间可以充分利用计算机内存空间实现灵活的内存动态管理解决了数组需要预先知道数据大小的缺点。其在内存中的存储如下图 相比于数组链表的插入和删除操作可以达到O(1)的复杂度只需要将链尾的指针指向下个节点或者指向null即可但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。
上面介绍的是单向链表单向链表有个缺点只能只能从头到尾遍历。如果要删除倒数第二个节点只能从头遍历。为了更加灵活的操作和更高的效率就有了双向链表其结构表示如下图 如果结构为双向链表要删除倒数第二个节点只用找到尾节点的前面一个节点并删除即可。Java 中的 LinkedList 就是一个双向链表的实现。
队列和栈
数组和链表的关注点主要聚焦于数据的存储结构和访问方式而队列和栈关注的则是数据的处理顺序和逻辑有自己的特点。
队列的特点是先进先出FIFO第一个进入队列的元素会第一个被访问或取出或者说在添加元素时在队尾排队依次入队在队头依次出队。其表现形式如下图 栈的特点是先进后出FILO第一个入栈的元素最后一个被访问或被取出或者说最后一个入栈的元素会第一个被访问或被取出。栈只允许在栈顶进行插入和删除操作。
有一个很形象的描述就是可以将栈想象成一个弹夹最先装入的子弹会被压入底部而射出时则是从顶部弹出。 两者的底层实现可以根据具体需求和场景选择数组或链表作为底层数据结构。例如 Java 中的 ArrayBlockingQueue 是通过数组实现的阻塞队列LinkedBlockingQueue 通过队列实现的非阻塞队列。
树
树是一种非线性结构是由n个有限节点组成一个具有层次关系的集合。树也有很多类型比如二叉树、平衡树、2-3-4树、红黑树、B树、B树。
二叉树是每个节点最多有两个子树的树结构通常用于实现二叉查找树其特点为左子节点的值小于根节点的值右子节点的值大于根节点的值。以 Java 为例一个二叉查找树的结构是这样表示的
public class Node {//当前节点的值private int value;//父节点、左子节点、右子节点private Node parent,left,right;}表现形式如下图 其查询的时间复杂度为O(log n)相对于链表查询效率大大提升。但是在最坏情况下可能会退化成O(n)比如下面这种情况 为了避免这种情况诞生了AVL树。AVL树是一种自平衡的二叉查找树在进行插入和删除操作时会通过左旋或者右旋自动调整自身的结构确保每个节点的左右子树的高度差不超过1从而保持树的平衡也保障了查询的时间复杂度为O(log n)。
以下图为例当插入节点5时节点7左右子树的高度差为2这时候节点7就需要进行右旋保持树的平衡。 右旋就是以某个节点为旋转点其左子节点变为其父节点左子节点的右子节点变为其左子节点右子节点不变。 同理左旋就是以某个节点为旋转点其右子节点变为其父节点右子节点的左子节点变为其右子节点左子节点不变。 虽然AVL通过旋转保持树的平衡但是在插入和删除频繁的场景中频繁的旋转会导致性能下降为解决此问题红黑树被提出。
红黑树大家应该都比较耳熟面试的时候应该经常会被问到但是理不理解是另一回事。
红黑树也是自平衡的二叉查找树它是通过节点颜色来保证树的平衡的。相对AVL红黑树较难被理解第一疑惑就是“不也是左旋右旋吗还这么麻烦节点颜色变来变去迷惑谁呢”。
红黑树后面专门写一篇文章介绍这里先给结论红黑树的旋转次数相对于AVL树来说较少因此在插入、删除等操作较多的情况下通常使用红黑树比如大家都知道的HashMap。下图显示的是按顺序插入9, 7, 6, 10, 5, 8, 4, 2, 1, 0的AVL树和红黑树可以看到两者在结构上存在一定的差异。 上面说的几种树都是二叉树即每个节点只有两个分支并且都都是有序的。因为只有两个分支所以这也是二叉树的通病当数据越来越多的时候树的高度也会越高这种情况就不适合数据库和文件系统这种场景了。
上面提到的几种树结构都是二叉树每个节点只有两个子节点并且都是有序的。当数据量不断增加时二叉树的高度也会逐渐增加从而导致查询效率降低并且在有磁盘I/O操作的场景下树越高越不利于查询。
为了解决上述问题采用多叉树结构可以有效地降低树的高度提高查询效率。
常见的多叉树有2-3-4树、B树和B树通常在数据库和文件系统中会使用到其表现形式如下图。 B树是B树的一种扩展它更适合用于磁盘或其他存储设备中。在B树中非叶子节点不保存数据信息只保存关键字和子节点指针这样会存储更多有效数据比如索引。同时每个叶子节点都指向相邻叶子节点的指针这样的话在数据库范围查询会变得非常高效。
堆
堆是一种特殊的树形数据结构其特点为每个节点都大于或等于小于或等于其每个子节点。
常见的堆有二叉堆、斐波那契堆等二叉堆是一种完全二叉树可以分为最大堆和最小堆最大堆中的每个节点都大于或等于其子节点最小堆中的每个节点都小于或等于其子节点。下图左为最大堆的表示右不符合为一个完全二叉树依次从左到右插入的节点为完全二叉树。 堆通常被用作优先队列因为堆的根节点总是最大的或最小的。
总结
很多编程语言都提供了不同类型的集合类以 Java 为例我们常用的集合有List、Set、Queue、Map其底层的实现就是数组、链表或树这几种数据结构。所以通过了解数据结构我们可以更好地选择和使用这些集合甚至可以自行设计更高效的数据结构来解决问题。
