数据结构

1.1 数据结构概述

数据结构是计算机存储、组织数据的方式通常情况下精心选择的数据结构可以带来更高的运行或者存储效率。数据结构的优良将直接影响着我们程序的性能常用的数据结构有数组Array、栈Stack、队列Queue、链表Linked List、树Tree、图Graph、堆Heap、散列表Hash等

1.2 数据结构的分类

1.2.1 排列方式

1集合

集合数据结构中的元素之间除了“同属一个集合” 的相互关系外别无其他关系

2线性结构

线性结构数据结构中的元素存在一对一的相互关系

3树形结构

树形结构数据结构中的元素存在一对多的相互关系

4图形结构

图形结构数据结构中的元素存在多对多的相互关系

1.2.2 逻辑结构

数据结构按逻辑上划分为线性结构与非线性结构

• 线性结构有且仅有一个开始结点和一个终端结点并且所有结点都最多只有一个直接前驱和一个直接后继。

典型的线性表有链表、栈和队列。它们共同的特点就是数据之间的线性关系除了头结点和尾结点之外每个结点都有唯一的前驱和唯一的后继也就是所谓的一对一的关系。

• 非线性结构对应于线性结构非线性结构也就是每个结点可以有不止一个直接前驱和直接后继。常见的非线性结构包括树、图等。

1.3 数据结构的实现

1.2.1 数组

• 数组Array数组是有序元素的序列在内存中的分配是连续的数组会为存储的元素都分配一个下标索引此下标是一个自增连续的访问数组中的元素通过下标进行访问数组下标从0开始访问

• 数组的优点是查询速度快

• 数组的缺点是删除增加、删除慢由于数组为每个元素都分配了索引且索引是自增连续的因此一但删除或者新增了某个元素时需要调整后面的所有元素的索引

新增一个元素40到3索引下标位置

删除2索引元素

总结数组查询快增删慢适用于频繁查询增删较少的情况

1.2.2 链表

• 链表Linked List链表是由一系列节点Node也可称元素组成数据元素的逻辑顺序是通过链表的指针地址实现通常情况下每个节点包含两个部分一个用于存储元素的内存地址名叫数据域另一个则指向下一个相邻节点地址的指针名叫指针域根据链表的指向不同可分为单向链表、双向链表、循环链表等我们本章介绍的是单向链表也是所有链表中最常见、最简单的链表

链表的节点Node

完整的链表

• 链表的优点新增节点、删除节点快

在链表中新增一个元素

在单向链表中新增一个元素最多只会影响上一个节点比在数组中的新增效率要高的多

在链表中删除一个元素

• 链表的缺点
  • 1查询速度慢查询从头部开始一直查询到尾部如果元素刚好是在最尾部那么查询效率势必非常低
  • 2链表像对于数组多了一个指针域的开销内存相对占用会比较大

总结数据量较小需要频繁增加删除操作的场景查询操作相对较少

1.2.3 栈

• 栈Stack是一种特殊的线性表仅能在线性表的一端操作栈顶允许操作栈底不允许操作。 栈的特点是先进后出从栈顶放入元素的操作叫入栈压栈取出元素叫出栈弹栈。

入栈操作

出栈操作

栈的特点先进后出Java中的栈内存就是一个栈的数据结构先调用的方法要等到后调用的方法结束才会弹栈出栈

1.2.4 队列

• 队列Queue队列与栈一样也是一种线性表其限制是仅允许在表的一端进行插入而在表的另一端进行删除。队列的特点是先进先出从一端放入元素的操作称为入队取出元素为出队

队列的特点先进先出

1.2.5 树

树是一种数据结构它是由nn>=1个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。它具有以下的特点

• 1每个节点有0个或多个子节点
• 2没有父节点的节点称为根节点
• 3每一个非根节点有且只有一个父节点
• 4除了根节点外每个子节点可以分为多个不相交的子树
• 5右子树永远比左子树大读取顺序从左到右

树的分类有非常多种平衡二叉树AVL、红黑树RBLR-B Tree、B树B-Tree、B+树B+Tree等但最早都是由二叉树演变过去的

二叉树的特点每个结点最多有两颗子树

1.2.6 堆

• 堆Heap堆可以看做是一颗用数组实现的二叉树所以它没有使用父指针或者子指针。堆根据“堆属性”来排序“堆属性”决定了树中节点的位置。

堆的特性如果一个结点的位置为k则它的父结点的位置为[k/2]而它的两个子结点的位置则分别为2k和2k+1。这样在不使用指针的情况下我们也可以通过计算数组的索引在树中上下移动从arr[k]向上一层就令k等于k/2,向下一层就令k等于2k或2k+1。

堆的定义如下n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时称之为堆

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1)满足前者的表达式的成为小顶堆小根堆满足后者表达式的为大顶堆大根堆很明显我们上面画的堆数据结构是一个大根堆

大小根堆数据结构图

一般来说将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

1.2.7 散列表

• 散列表Hash也叫哈希表是根据键和值 (key和value) 直接进行访问的数据结构通过key和value来映射到集合中的一个位置这样就可以很快找到集合中的对应元素。它利用数组支持按照下标访问的特性所以散列表其实是数组的一种扩展由数组演化而来。

散列表首先需要根据key来计算数据存储的位置也就是数组索引的下标

• HashValue=hash(key)

散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字然后就将该数字对数组长度进行取余取余结果就当作数组的下标将value存储在以该数字为下标的数组空间里这种存储空间可以充分利用数组的查找优势来查找元素所以查找的速度很快。

在散列表中左边是个数组数组的每个成员包括一个指针指向一个链表的头当然这个链表可能为空也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去也是根据这些特征找到正确的链表再从链表中找出这个元素。

1.2.8 图

• 图Graph图是一系列顶点元素的集合这些顶点通过一系列边连接起来组成图这种数据结构。顶点用圆圈表示边就是这些圆圈之间的连线。顶点之间通过边连接。

图分为有向图和无向图

• 有向图边不仅连接两个顶点并且具有方向
• 无向图边仅仅连接两个顶点没有其他含义

例如我们可以把图这种数据结构看做是一张地图

地图中的城市我们看做是顶点高铁线路看做是边很显然我们的地图是一种无向图以长沙到上海为例经过的城市有长沙、南昌、杭州、上海等地那么从上海也可以按照原有的路线进行返回

实现了图这种数据结构之后我们可以在此数据结构上做一些复杂的算法计算如广度优先搜索算法、深度优先搜索算法等

• 广度搜索搜索到一个顶点时先将此顶点的所有子顶点全部搜索完毕再进行下一个子顶点的子顶点搜索

例如上图以武汉为例进行广度搜索

1首先搜索合肥、南昌、长沙等城市

2通过合肥搜索到南京

3再通过南昌搜索到杭州、福州

4最终通过南京搜索到上海完成图的遍历搜索

不通过南京搜索到杭州是因为已经通过南昌搜索到杭州了不需要再次搜索

• 深度搜索搜索到一个顶点时先将此顶点某个子顶点搜索到底部子顶点的子顶点的子顶点…然后回到上一级继续搜索第二个子顶点一直搜索到底部

例如上图以武汉为例进行深度搜索

1首先搜索合肥、南京、上海等城市

2回到武汉进行第二子顶点的搜索搜索南昌、杭州等地

3回到南昌搜索福州

4回到武汉搜索长沙

图是一种比较复杂的数据结构在存储数据上有着比较复杂和高效的算法分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。我们本次了解到这里即可

记得点赞