数据结构是计算机存储、组织数据的方式;通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构的优良将直接影响着我们程序的性能;常用的数据结构有:数组(Array)、栈(Stack)、队列(Queue)、链表(Linked List)、树(Tree)、图(Graph)、堆(Heap)、散列表(Hash)等;
集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系;
线性结构:数据结构中的元素存在一对一的相互关系;
树形结构:数据结构中的元素存在一对多的相互关系;
图形结构:数据结构中的元素存在多对多的相互关系;
数据结构按逻辑上划分为线性结构与非线性结构;
典型的线性表有:链表、栈和队列。它们共同的特点就是数据之间的线性关系,除了头结点和尾结点之外,每个结点都有唯一的前驱和唯一的后继,也就是所谓的一对一的关系。
数据结构可视化网站:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
新增一个元素40到3索引下标位置:
删除2索引元素:
总结:数组查询快,增删慢,适用于频繁查询,增删较少的情况;
链表的节点(Node):
完整的链表:
在链表中新增一个元素:
在单向链表中,新增一个元素最多只会影响上一个节点,比在数组中的新增效率要高的多;
在链表中删除一个元素:
总结:数据量较小,需要频繁增加,删除操作的场景,查询操作相对较少;
入栈操作:
出栈操作:
栈的特点:先进后出,Java中的栈内存就是一个栈的数据结构,先调用的方法要等到后调用的方法结束才会弹栈(出栈);
Tips:
队列的特点:先进先出;
Tips:
树是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
树的分类有非常多种,平衡二叉树(AVL)、红黑树RBL(R-B Tree)、B树(B-Tree)、B+树(B+Tree)等,但最早都是由二叉树演变过去的;
二叉树的特点:每个结点最多有两颗子树
Tips:
堆分为两种:大根堆和小根堆,两者的差别在于节点的排序方式。
这就是所谓的“堆属性”,并且这个属性对堆中的每一个节点都成立。
根据这一属性,那么最大堆总是将其中的最大值存放在树的根节点。而对于最小堆,根节点中的元素总是树中的最小值。堆属性非常有用,因为堆常常被当做优先队列使用,因为可以快速地访问到“最重要”的元素。
Tips:堆的根节点中存放的是最大(大根堆)或者最小(小根堆)元素,但是其他节点的排序顺序是未知的。例如,在一个最大堆中,最大的那一个元素总是位于 index 0 的位置,但是最小的元素则未必是最后一个元素。唯一能够保证的是最小的元素是一个叶节点,但是不确定是哪一个。
大小根堆数据结构图:
因为堆有序的特点,因此我们可以使用堆的属性来做数组中的排序,简称为堆排序(Heap Sort)。
常见的堆有二叉堆、斐波那契堆等。
小根堆:https://www.cs.usfca.edu/~galles/visualization/Heap.html
散列表首先需要根据key来计算数据存储的位置,也就是数组索引的下标;
散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字(hash值),然后就将hash值对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,这种存储空间可以充分利用数组的查找优势来查找元素,所以查找的速度很快。
在散列表中,左边是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。
散列表:https://www.cs.usfca.edu/~galles/visualization/OpenHash.html
图分为有向图和无向图:
例如,我们可以把图这种数据结构看做是一张地图:
地图中的城市我们看做是顶点,高铁线路看做是边;很显然,我们的地图是一种无向图,以长沙到上海为例,经过的城市有长沙、南昌、杭州、上海等地;那么从上海也可以按照原有的路线进行返回;
实现了图这种数据结构之后我们可以在此数据结构上做一些复杂的算法计算,如广度优先搜索算法、深度优先搜索算法等;
例如上图:以武汉为例进行广度搜索,
例如上图:以武汉为例进行深度搜索,
Tips:
图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。我们本次了解到这里即可;
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。