精华内容
下载资源
问答
  • 常见的数据存储结构有哪些
    千次阅读
    2021-06-25 19:57:50

    目录

    一、什么是数据结构

    二、常用数据结构有哪些

    2.1 基本数据结构

    2.2 常用数据结构 (逻辑结构)

    2.2.1 数组(静态数组、动态数组)

    2.2.2 线性表

    2.2.3 队列

    2.2.4 栈

    2.2.5 树(二叉树、查找树、平衡树、线索、堆)

    2.2.6 图(Graph)

    2.2.7 堆 (Heap)

    2.2.8 散列表(哈希表) (Hash)

    2.3 数据存储结构比较

    2.4 数据结构的操作

    2.5 算法的空间复杂度与时间复杂度


    数据结构可以从两个方面分析:逻辑结构与物理结构(存储结构)。

    其中逻辑结构指的是数据的组织方式,物理结构指的是数据在内存上的存储方式

    逻辑结构分为四种类型:集合结构,线性结构,树形结构,图形结构。

    物理结构又叫存储结构,分为四种种,顺序存储结构、链式存储结构、索引结构、散列结构。

    一、什么是数据结构

    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
     

    数据结构与算法的关系:

    数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组方法”。
    数据结构是为算法服务的,算法是要作用再特定的数据结构上的。

    二、常用数据结构有哪些

    2.1 基本数据结构

    数据元素相互之间的关系称为结构。有四类基本结构:集合、线性结构、树形结构、图状结构。 集合结构:除了同属于一种类型外,别无其它关系 ;

    线性结构:元素之间存在一对一关系常见类型有: 数组,链表,队列,栈,它们之间在操作上有所区别。例如:链表可在任意位置插入或删除元素, 而队列在队尾插入元素,队头删除元素,栈只能在栈顶进行插入,删除操作;

    树形结构:元素之间存在一对多的关系,常见类型有:树(有许多特例:二叉树、平衡二叉树、查找树等) 图形结构:元素之间存在多对多的关系,图形结构中每个结点的前驱结点数和后续结点多个数可以任意。

    2.2 常用数据结构 (逻辑结构)

    本文作者:https://www.zhihu.com/people/san-hao-bai-du-ren-79

    (由于文章总是被三无号到处复制发布,选择这种方式插入原文链接影响阅读实在抱歉!)

    本文原文链接:https://blog.csdn.net/qq_41687938/article/details/118227614

    2.2.1 数组(静态数组、动态数组)

     在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中, 数组属于构造数据类型。
     一个数组可以分解为多个数组元素,这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同,数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

    2.2.2 线性表

    线性表并不是一种具体的存储结构,它包含顺序存储结构和链式存储结构,是顺序表和链表的统称。顺序表、链表(单向链表、双向链表、循环链表)

    2.2.3 队列

    栈隶属于线性表,是特殊的线性表,因为它对线性表中元素的进出做了明确的要求只能从线性表的一端进,从另一端出,且要遵循“先入先出”的特点,即先进队列的元素也要先出队列。即只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素 时,称为队空。

    2.2.4 栈

    栈隶属于线性表,是特殊的线性表,因为它对线性表中元素的进出做了明确的要求。栈中的元素只能从线性表的一端进出(另一端封死),且要遵循“先入后出”的原则,即先进栈的元素后出栈。即先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据,最后一 个数据被第一个读出来

    2.2.5 树(二叉树、查找树、平衡树、线索、堆)

    树是包含n(n>0)个结点的有穷集合K,且在K中定义了一个关系N,N满足以下条件:
    1)有且仅有一个结点K0,他对于关系N来说没有前驱,称K0为树的根结点。简称为根(root)。
    2)除K0外,K中的每个结点,对于关系N来说有且仅有一个前驱。
    3)K中各结点,对关系N来说可以有m个后继(m>=0)。

    2.2.6 图(Graph)

    图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

    2.2.7 堆 (Heap)

    在计算机科学中,堆是一种特殊的树形数据结构,每个结点都有一个值。通常我们所说的堆的数据结构,是指二叉堆。堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆。

    2.2.8 散列表(哈希表) (Hash)

    若结构中存在关键字和K相等的记录,则该记录必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function),按这个思想建立的表为散列表。

    2.3 数据存储结构比较

    顺序结构:一段连续的内存空间。
        优点:随机访问
        缺点:插入删除效率低,大小固定
    链式结构:不连续的内存空间
        优点:大小动态扩展,插入删除效率高
        缺点:不能随机访问。
    索引结构:为了方便查找,整体无序,但索引块之间有序,需要额外空间,存储索引表。
        优点:对顺序查找的一种改进,查找效率高
        缺点:需额外空间存储索引表
    散列结构:选取某个函数,数据元素根据函数计算存储位置。可能存在多个数据元素存储在同一位置,引起地址冲突。
        优点:查找基于数据本身即可找到,查找效率高。存取效率高
        缺点:存取随机,不便于顺序查找。

    2.4 数据结构的操作

    查询、删除、插入等

    2.5 算法的空间复杂度与时间复杂度

    大O复杂度表示法

    更多相关内容
  • 九大常见数据结构

    千次阅读 多人点赞 2020-10-16 14:44:54
    数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不一样的处理效率。 常用的数据结构可根据数据访问的特点分为线性结构和非线性结构。线性结构包括常见的...

    数据结构想必大家都不会陌生,对于一个成熟的程序员而言,熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不一样的处理效率。

    常用的数据结构可根据数据访问的特点分为线性结构和非线性结构。线性结构包括常见的链表、栈、队列等,非线性结构包括树、图等。数据结构种类繁多,本文将通过图解的方式对常用的数据结构进行理论上的介绍和讲解,以方便大家掌握常用数据结构的基本知识。

    1、数组

    数组可以说是最基本最常见的数据结构。数组一般用来存储相同类型的数据,可通过数组名和下标进行数据的访问和更新。数组中元素的存储是按照先后顺序进行的,同时在内存中也是按照这个顺序进行连续存放。数组相邻元素之间的内存地址的间隔一般就是数组数据类型的大小。

     2、链表

    链表相较于数组,除了数据域,还增加了指针域用于构建链式的存储数据。链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的查找和访问,使得链表的自由度更高。

    这表现在对节点进行增加和删除时,只需要对上一节点的指针地址进行修改,而无需变动其它的节点。不过事物皆有两极,指针带来高自由度的同时,自然会牺牲数据查找的效率和多余空间的使用。

    一般常见的是有头有尾的单链表,对指针域进行反向链接,还可以形成双向链表或者循环链表。

    链表和数组对比

    链表和数组在实际的使用过程中需要根据自身的优劣势进行选择。链表和数组的异同点也是面试中高频的考察点之一。这里对单链表和数组的区别进行了对比和总结。

     3、跳表

    从上面的对比中可以看出,链表虽然通过增加指针域提升了自由度,但是却导致数据的查询效率恶化。特别是当链表长度很长的时候,对数据的查询还得从头依次查询,这样的效率会更低。跳表的产生就是为了解决链表过长的问题,通过增加链表的多级索引来加快原始链表的查询效率。这样的方式可以让查询的时间复杂度从O(n)提升至O(logn)。

    跳表通过增加的多级索引能够实现高效的动态插入和删除,其效率和红黑树和平衡二叉树不相上下。目前redis和levelDB都有用到跳表。

    从上图可以看出,索引级的指针域除了指向下一个索引位置的指针,还有一个down指针指向低一级的链表位置,这样才能实现跳跃查询的目的。

     4、栈

    栈是一种比较简单的数据结构,常用一句话描述其特性,后进先出。栈本身是一个线性表,但是在这个表中只有一个口子允许数据的进出。这种模式可以参考腔肠动物...即进食和排泄都用一个口...

    栈的常用操作包括入栈push和出栈pop,对应于数据的压入和压出。还有访问栈顶数据、判断栈是否为空和判断栈的大小等。由于栈后进先出的特性,常可以作为数据操作的临时容器,对数据的顺序进行调控,与其它数据结构相结合可获得许多灵活的处理。

     5、队列

    队列是栈的兄弟结构,与栈的后进先出相对应,队列是一种先进先出的数据结构。顾名思义,队列的数据存储是如同排队一般,先存入的数据先被压出。常与栈一同配合,可发挥最大的实力。

     6、树

    树作为一种树状的数据结构,其数据节点之间的关系也如大树一样,将有限个节点根据不同层次关系进行排列,从而形成数据与数据之间的父子关系。常见的树的表示形式更接近“倒挂的树”,因为它将根朝上,叶朝下。

    树的数据存储在结点中,每个结点有零个或者多个子结点。没有父结点的结点在最顶端,成为根节点;没有非根结点有且只有一个父节点;每个非根节点又可以分为多个不相交的子树。

    这意味着树是具备层次关系的,父子关系清晰,家庭血缘关系明朗;这也是树与图之间最主要的区别。

    别看树好像很高级,其实可看作是链表的高配版。树的实现就是对链表的指针域进行了扩充,增加了多个地址指向子结点。同时将“链表”竖起来,从而凸显了结点之间的层次关系,更便于分析和理解。

    树可以衍生出许多的结构,若将指针域设置为双指针,那么即可形成最常见的二叉树,即每个结点最多有两个子树的树结构。二叉树根据结点的排列和数量还可进一度划分为完全二叉树、满二叉树、平衡二叉树、红黑树等。

    完全二叉树:除了最后一层结点,其它层的结点数都达到了最大值;同时最后一层的结点都是按照从左到右依次排布。

    满二叉树:除了最后一层,其它层的结点都有两个子结点。

    平衡二叉树

    平衡二叉树又被称为AVL树,它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    二叉排序树:是一棵空树,或者:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。

    树的高度:结点层次的最大值

    平衡因子:左子树高度 - 右子树高度

    二叉排序树意味着二叉树中的数据是排好序的,顺序为左结点<根节点<右结点,这表明二叉排序树的中序遍历结果是有序的。(还不懂二叉树四种遍历方式[前序遍历、中序遍历、后序遍历、层序遍历]的同学赶紧补习!)

    平衡二叉树的产生是为了解决二叉排序树在插入时发生线性排列的现象。由于二叉排序树本身为有序,当插入一个有序程度十分高的序列时,生成的二叉排序树会持续在某个方向的字数上插入数据,导致最终的二叉排序树会退化为链表,从而使得二叉树的查询和插入效率恶化。

    平衡二叉树的出现能够解决上述问题,但是在构造平衡二叉树时,却需要采用不同的调整方式,使得二叉树在插入数据后保持平衡。主要的四种调整方式有LL(左旋)、RR(右旋)、LR(先左旋再右旋)、RL(先右旋再左旋)。这里先给大家介绍下简单的单旋转操作,左旋和右旋。LR和RL本质上只是LL和RR的组合。

    在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改,当平衡因子大于1时,就需要进行平衡化处理。从发生不平衡的结点起,沿刚才回溯的路径取直接下两层的结点,如果这三个结点在一条直线上,则采用单旋转进行平衡化,如果这三个结点位于一条折线上,则采用双旋转进行平衡化。

    左旋:S为当前需要左旋的结点,E为当前结点的父节点。

    左旋的操作可以用一句话简单表示:将当前结点S的左孩子旋转为当前结点父结点E的右孩子,同时将父结点E旋转为当前结点S的左孩子。可用动画表示:

     右旋:S为当前需要左旋的结点,E为当前结点的父节点。右单旋是左单旋的镜像旋转。

    左旋的操作同样可以用一句话简单表示:将当前结点S的左孩子E的右孩子旋转为当前结点S的左孩子,同时将当前结点S旋转为左孩子E的右孩子。可用动画表示:

    红黑树

    平衡二叉树(AVL)为了追求高度平衡,需要通过平衡处理使得左右子树的高度差必须小于等于1。高度平衡带来的好处是能够提供更高的搜索效率,其最坏的查找时间复杂度都是O(logN)。但是由于需要维持这份高度平衡,所付出的代价就是当对树种结点进行插入和删除时,需要经过多次旋转实现复衡。这导致AVL的插入和删除效率并不高。

    为了解决这样的问题,能不能找一种结构能够兼顾搜索和插入删除的效率呢?这时候红黑树便申请出战了。

    红黑树具有五个特性:

    1. 每个结点要么是红的要么是黑的。

    2. 根结点是黑的。

    3. 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。

    4. 如果一个结点是红的,那么它的两个儿子都是黑的。

    5. 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

     黑树通过将结点进行红黑着色,使得原本高度平衡的树结构被稍微打乱,平衡程度降低。红黑树不追求完全平衡,只要求达到部分平衡。这是一种折中的方案,大大提高了结点删除和插入的效率。C++中的STL就常用到红黑树作为底层的数据结构。

    红黑树VS平衡二叉树

    除了上面所提及的树结构,还有许多广泛应用在数据库、磁盘存储等场景下的树结构。比如B树、B+树等。这里就先不介绍了诶,下次在讲述相关存储原理的时候将会着重介绍。(其实是因为懒)

    7、堆

    了解完二叉树,再来理解堆就不是什么难事了。堆通常是一个可以被看做一棵树的数组对象。堆的具体实现一般不通过指针域,而是通过构建一个一维数组与二叉树的父子结点进行对应,因此堆总是一颗完全二叉树。

    对于任意一个父节点的序号n来说(这里n从0算),它的子节点的序号一定是2n+1,2n+2,因此可以直接用数组来表示一个堆。

    不仅如此,堆还有一个性质:堆中某个节点的值总是不大于或不小于其父节点的值。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。 

    堆常用来实现优先队列,在面试中经常考的问题都是与排序有关,比如堆排序、topK问题等。由于堆的根节点是序列中最大或者最小值,因而可以在建堆以及重建堆的过程中,筛选出数据序列中的极值,从而达到排序或者挑选topK值的目的。 

     8、散列表

    散列表也叫哈希表,是一种通过键值对直接访问数据的机构。在初中,我们就学过一种能够将一个x值通过一个函数获得对应的一个y值的操作,叫做映射。散列表的实现原理正是映射的原理,通过设定的一个关键字和一个映射函数,就可以直接获得访问数据的地址,实现O(1)的数据访问效率。在映射的过程中,事先设定的函数就是一个映射表,也可以称作散列函数或者哈希函数。

    散列表的实现最关键的就是散列函数的定义和选择。一般常用的有以下几种散列函数:

    直接寻址法:取关键字或关键字的某个线性函数值为散列地址。

    数字分析法:通过对数据的分析,发现数据中冲突较少的部分,并构造散列地址。例如同学们的学号,通常同一届学生的学号,其中前面的部分差别不太大,所以用后面的部分来构造散列地址。

    平方取中:当无法确定关键字里哪几位的分布相对比较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为散列地址。这是因为:计算平方之后的中间几位和关键字中的每一位都相关,所以不同的关键字会以较高的概率产生不同的散列地址。

    取随机数法:使用一个随机函数,取关键字的随机值作为散列地址,这种方式通常用于关键字长度不同的场合。

    除留取余法:取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要,一般取素数或者直接用 n。

    确定好散列函数之后,通过某个key值的确会得到一个唯一的value地址。但是却会出现一些特殊情况。即通过不同的key值可能会访问到同一个地址,这个现象称之为冲突。

    冲突在发生之后,当在对不同的key值进行操作时会使得造成相同地址的数据发生覆盖或者丢失,是非常危险的。所以在设计散列表往往还需要采用冲突解决的办法。

    常用的冲突处理方式有很多,常用的包括以下几种:

    开放地址法(也叫开放寻址法):实际上就是当需要存储值时,对Key哈希之后,发现这个地址已经有值了,这时该怎么办?不能放在这个地址,不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希,比如往后移动一个地址,如果没人占用,就用这个地址。如果超过最大长度,则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。

    再哈希法:在产生冲突之后,使用关键字的其他部分继续计算地址,如果还是有冲突,则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。

    链地址法:链地址法其实就是对Key通过哈希之后落在同一个地址上的值,做一个链表。其实在很多高级语言的实现当中,也是使用这种方式处理冲突的。

    公共溢出区:这种方式是建立一个公共溢出区,当地址存在冲突时,把新的地址放在公共溢出区里。

    目前比较常用的冲突解决方法是链地址法,一般可以通过数组和链表的结合达到冲突数据缓存的目的。

    左侧数组的每个成员包括一个指针,指向一个链表的头。每发生一个冲突的数据,就将该数据作为链表的节点链接到链表尾部。这样一来,就可以保证冲突的数据能够区分并顺利访问。

    考虑到链表过长造成的问题,还可以使用红黑树替换链表进行冲突数据的处理操作,来提高散列表的查询稳定性。

     9、图

    图相较于上文的几个结构可能接触的不多,但是在实际的应用场景中却经常出现。比方说交通中的线路图,常见的思维导图都可以看作是图的具体表现形式。

    图结构一般包括顶点和边,顶点通常用圆圈来表示,边就是这些圆圈之间的连线。边还可以根据顶点之间的关系设置不同的权重,默认权重相同皆为1。此外根据边的方向性,还可将图分为有向图和无向图。

    图结构用抽象的图线来表示十分简单,顶点和边之间的关系非常清晰明了。但是在具体的代码实现中,为了将各个顶点和边的关系存储下来,却不是一件易事。 

    邻接矩阵

    目前常用的图存储方式为邻接矩阵,通过所有顶点的二维矩阵来存储两个顶点之间是否相连,或者存储两顶点间的边权重。

    无向图的邻接矩阵是一个对称矩阵,是因为边不具有方向性,若能从此顶点能够到达彼顶点,那么彼顶点自然也能够达到此顶点。此外,由于顶点本身与本身相连没有意义,所以在邻接矩阵中对角线上皆为0。

    有向图由于边具有方向性,因此彼此顶点之间并不能相互达到,所以其邻接矩阵的对称性不再。

    用邻接矩阵可以直接从二维关系中获得任意两个顶点的关系,可直接判断是否相连。但是在对矩阵进行存储时,却需要完整的一个二维数组。若图中顶点数过多,会导致二维数组的大小剧增,从而占用大量的内存空间。

    而根据实际情况可以分析得,图中的顶点并不是任意两个顶点间都会相连,不是都需要对其边上权重进行存储。那么存储的邻接矩阵实际上会存在大量的0。虽然可以通过稀疏表示等方式对稀疏性高的矩阵进行关键信息的存储,但是却增加了图存储的复杂性。

    因此,为了解决上述问题,一种可以只存储相连顶点关系的邻接表应运而生。

    邻接表

    在邻接表中,图的每一个顶点都是一个链表的头节点,其后连接着该顶点能够直接达到的相邻顶点。相较于无向图,有向图的情况更为复杂,因此这里采用有向图进行实例分析。

     

    邻接表中,每一个顶点都对应着一条链表,链表中存储的是顶点能够达到的相邻顶点。存储的顺序可以按照顶点的编号顺序进行。比如上图中对于顶点B来说,其通过有向边可以到达顶点A和顶点E,那么其对应的邻接表中的顺序即B->A->E,其它顶点亦如此。

    通过邻接表可以获得从某个顶点出发能够到达的顶点,从而省去了对不相连顶点的存储空间。然而,这还不够。对于有向图而言,图中有效信息除了从顶点“指出去”的信息,还包括从别的顶点“指进来”的信息。这里的“指出去”和“指进来”可以用出度和入度来表示。

    入度:有向图的某个顶点作为终点的次数和。

    出度:有向图的某个顶点作为起点的次数和。

    由此看出,在对有向图进行表示时,邻接表只能求出图的出度,而无法求出入度。这个问题很好解决,那就是增加一个表用来存储能够到达某个顶点的相邻顶点。这个表称作逆邻接表。

    逆邻接表

    逆邻接表与邻接表结构类似,只不过图的顶点链接着能够到达该顶点的相邻顶点。也就是说,邻接表时顺着图中的箭头寻找相邻顶点,而逆邻接表时逆着图中的箭头寻找相邻顶点。

    邻接表和逆邻接表的共同使用下,就能够把一个完整的有向图结构进行表示。可以发现,邻接表和逆邻接表实际上有一部分数据时重合的,因此可以将两个表合二为一,从而得到了所谓的十字链表。

    十字链表

    十字链表似乎很简单,只需要通过相同的顶点分别链向以该顶点为终点和起点的相邻顶点即可。

    但这并不是最优的表示方式。虽然这样的方式共用了中间的顶点存储空间,但是邻接表和逆邻接表的链表节点中重复出现的顶点并没有得到重复利用,反而是进行了再次存储。因此,上图的表示方式还可以进行进一步优化。

    十字链表优化后,可通过扩展的顶点结构和边结构来进行正逆邻接表的存储:(下面的弧头可看作是边的箭头那端,弧尾可看作是边的圆点那端)

    data:用于存储该顶点中的数据;

    firstin指针:用于连接以当前顶点为弧头的其他顶点构成的链表,即从别的顶点指进来的顶点;

    firstout指针:用于连接以当前顶点为弧尾的其他顶点构成的链表,即从该顶点指出去的顶点;

    边结构通过存储两个顶点来确定一条边,同时通过分别代表这两个顶点的指针来与相邻顶点进行链接:

    tailvex:用于存储作为弧尾的顶点的编号;

    headvex:用于存储作为弧头的顶点的编号;

    headlink 指针:用于链接下一个存储作为弧头的顶点的节点;

    taillink 指针:用于链接下一个存储作为弧尾的顶点的节点;

    以上图为例子,对于顶点A而言,其作为起点能够到达顶点E。因此在邻接表中顶点A要通过边AE(即边04)指向顶点E,顶点A的firstout指针需要指向边04的tailvex。同时,从B出发能够到达A,所以在逆邻接表中顶点A要通过边AB(即边10)指向B,顶点A的firstin指针需要指向边10的弧头,即headlink指针。依次类推。

    十字链表采用了一种看起来比较繁乱的方式对边的方向性进行了表示,能够在尽可能降低存储空间的情况下增加指针保留顶点之间的方向性。具体的操作可能一时间不好弄懂,建议多看几次上图,弄清指针指向的意义,明白正向和逆向邻接表的表示。

    10  总结

    数据结构博大精深,没有高等数学的讳莫如深,也没有量子力学的玄乎其神,但是其在计算机科学的各个领域都具有强大的力量。本文试图采用图解的方式对九种数据结构进行理论上的介绍,但是其实这都是不够的。

    即便是简单的数组、栈、队列等结构,在实际使用以及底层实现上都会有许多优化设计以及使用技巧,这意味着还需要真正把它们灵活的用起来,才能够算是真正意义上的熟悉和精通。但是本文可以作为常见数据结构的一个总结,当你对某些结构有些淡忘的时候,不妨重新回来看看。

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 数据结构】八种常见数据结构介绍

    万次阅读 多人点赞 2021-02-05 13:59:44
    数据结构是计算机存储、组织数据的方式。一种好的数据结构可以带来更高的运行或者存储效率。数据在内存中是呈线性排列的,但是我们可以使用指针等道具,构造出类似“树形”的复杂结构。下面介绍八个常见数据结构

    相似文章推荐:


    零. 总览

    数据结构是计算机存储、组织数据的方式。一种好的数据结构可以带来更高的运行或者存储效率。数据在内存中是呈线性排列的,但是我们可以使用指针等道具,构造出类似“树形”的复杂结构。下面介绍八个常见的数据结构。
    在这里插入图片描述

    一. 数组

    数组是一种线性结构,而且在物理内存中也占据着一块连续空间。

    • 优点:访问数据简单。
    • 缺点:添加和删除数据比较耗时间。
    • 使用场景:频繁查询,对存储空间要求不大,很少增加和删除的情况。

    数据访问:由于数据是存储在连续空间内,所以每个数据的内存地址都是通过数据小标算出,所以可以直接访问目标数据。(这叫做“随机访问”)。比如下方,可以直接使用a[2]访问Red。
    在这里插入图片描述
    数据添加:数据添加需要移动其他数据。首先增加足够的空间,然后把已有的数据一个个移开。
    在这里插入图片描述
    在这里插入图片描述
    数据删除:反过来,如果想要输出数据Green,也是一样挨个把数据往反方向移动。
    在这里插入图片描述
    在这里插入图片描述

    二. 链表

    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。

    • 优点:数据添加和删除方便
    • 缺点:访问比较耗费时间
    • 适用场景:数据量较小,需要频繁增加,删除操作的场景

    数组和链表数据结构对比列表如下:
    在这里插入图片描述

    数据访问:因为数据都是分散存储的,所以想要访问数据,只能从第一个数据开始,顺着指针的指向逐一往下访问。
    在这里插入图片描述

    数据添加:将Blue的指针指向的位置变成Green,然后再把Green的指针指向Yellow。
    在这里插入图片描述
    数据删除:只要改变指针的指向就可以了,比如删除Yellow,只需把Green指针指向的位置从Yellow编程Red即可。

    虽然Yellow本身还存储在内存中,但是不管从哪里都无法访问这个数据,所以也就没有特意去删除它的必要了。今后需要用到Yellow所在的存储空间时,只要用新数据覆盖掉就可以了。
    在这里插入图片描述

    三. 栈

    栈也是一种数据呈线性排列的数据结构,不过在这种结构中,我们只能访问最新添加的数
    据。从栈顶放入元素的操作叫入栈,取出元素叫出栈。

    特点:后进先出(Last In First Out,简称LIFO)

    在这里插入图片描述
    在这里插入图片描述

    四. 队列

    队列中的添加和删除数据的操作分别是在两端进行的。队列可以在一端添加元素,在另一端取出元素,也就是:先进先出(First In First Out,简称FIFO)
    在这里插入图片描述
    在这里插入图片描述

    五. 哈希表

    哈希表,也叫散列表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。例如,下列键(key)为人名,value为性别。

    一般来说,我们可以把键当作数据的标识符,把值当作数据的内容。
    在这里插入图片描述

    • 数据存储

    假设我们需要存储5个元素,首先使用哈希函数(Hash)计算Joe的键,也就是字符串"Joe"的哈希值,得到4928,然后将哈希值除以数组长度5(mod运算),求得其余数。因此,我们将Joe的数据存进数组的3号箱子中。
    在这里插入图片描述

    • 冲突

    如果两个哈希值取余的结果相同,我们称这种情况为“冲突”。假设Nell键的哈希值为6276,mod 5的结果为1。但此时1号箱已经存储了Sue的数据,可使用链表在已有的数据的后面继续存储新的数据。
    在这里插入图片描述

    • 查询

    假设最终的哈希表为:
    在这里插入图片描述
    如果要查找Ally的性别,首先算出Alley键的哈希值,然后对它进行mod运算。最终结果为3。
    在这里插入图片描述
    然而3号箱中数据的键是Joe而不是Ally。此时便需要对Joe所在的链表进行线性查找。找到了键为Ally的数据。取出其对应的值,便知道了Ally的性别为女(F)。
    在这里插入图片描述

    • 特点

    可以利用哈希函数快速访问到数组的目标数据。如果发生哈希冲突,就使用链表进行存储。

    如果数组的空间太小,使用哈希表的时候就容易发生冲突,线性查找的使用频率也会更高;反过来,如果数组的空间太大,就会出现很多空箱子,造成内存的浪费。因此,给数组设定合适的空间非常重要。

    在存储数据的过程中,如果发生冲突,可以利用链表在已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址法”。除了链地址法以外,还有几种解决冲突的方法。其中,应用较为广泛的是“开放地址法”。

    六. 堆

    堆是一种图的树形结构,被用于实现“优先队列”(priority queues)。优先队列是一种数据结构,可以自由添加数据,但取出数据时要从最小值开始按顺序取出。在堆的树形结构中,各个顶点被称为“结点”(node),数据就存储在这些结点中。堆有下列特点:

    • 每个节点最多有两个子节点
    • 排列顺序必须从上到下,同一行从左到右
    • 堆中某个节点的值总是不大于或不小于其父节点的值;
    • 存放数据时,一般会把新数据放在最下面一行靠左的位置。如果最下面一行没有多余空间时,就再往下另起一行,并把数据添加到这一行的最左端。

    堆的性质:

    • 堆是一个完全二叉树
    • 堆中某个结点的值总是不大于或不小于其父结点的值;
    • 将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
    • 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树
    • 一棵深度为 k k k且有 2 k − 1 2^k - 1 2k1个结点的二叉树称为满二叉树。也就是说除了叶子节点都有2个子节点,且所有的叶子节点都在同一层。

    在这里插入图片描述

    七. 树

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

    • 每个节点有零个或多个子节点;
    • 没有父节点的节点称为根节点
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外,每个子节点可以分为多个不相交的子树

    在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树。二叉树是树的特殊一种,具有如下特点:

    • 每个结点最多有两颗子结点
    • 左子树和右子树是有顺序的,次序不能颠倒
    • 即使某结点只有一个子树,也要区分左右子树

    二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

    二叉树有很多扩展的数据结构,包括平衡二叉树、红黑树、B+树等,这些数据结构在二叉树的基础上衍生了很多的功能,在实际应用中广泛用到,例如mysql的数据库索引结构用的就是B+树,还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大,但算法上比较复杂,想学习的话还是需要花时间去深入的。

    八. 图

    图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。按照顶点指向的方向可分为无向图和有向图

    无向图:
    在这里插入图片描述
    有向图:
    在这里插入图片描述


    参考:《我的第一本算法书》

    展开全文
  • java常用数据结构有哪些

    千次阅读 2022-03-31 14:04:18
    java数据结构有:1、数组;2、链表,一种递归的数据结构;3、栈,按照“后进先出”、“先进后出”的原则来存储数据;4、队列;5、树,是由 n(n>0)个有限节点组成的一个具有层次关系的集合;6、堆;7、图;8、...

    java数据结构有:1、数组;2、链表,一种递归的数据结构;3、栈,按照“后进先出”、“先进后出”的原则来存储数据;4、队列;5、树,是由 n(n>0)个有限节点组成的一个具有层次关系的集合;6、堆;7、图;8、哈希表。

    本教程操作环境:windows7系统、java8版、DELL G3电脑。

    Java常见数据结构

    这 8 种数据结构有什么区别呢?

    ①、数组

    优点:

    按照索引查询元素的速度很快;

    按照索引遍历数组也很方便。

    缺点:

    数组的大小在创建后就确定了,无法扩容;

    数组只能存储一种类型的数据;

    添加、删除元素的操作很耗时间,因为要移动其他元素。

    ②、链表

    《算法(第 4 版)》一书中是这样定义链表的:

    链表是一种递归的数据结构,它或者为空(null),或者是指向一个结点(node)的引用,该节点还有一个元素和一个指向另一条链表的引用。

    Java 的 LinkedList 类可以很形象地通过代码的形式来表示一个链表的结构:

    public class LinkedList {
    
        transient Node first;
    
        transient Node last;
    
     
    
        private static class Node {
    
            E item;
    
            Node next;
    
            Node prev;
    
     
    
            Node(Node prev, E element, Node next) {
    
                this.item = element;
    
                this.next = next;
    
                this.prev = prev;
    
            }
    
        }
    
    }

     这是一种双向链表,当前元素 item 既有 prev 又有 next,不过 first 的 prev 为 null,last 的 next 为 null。如果是单向链表的话,就只有 next,没有 prev。

     由于不必按照顺序的方式存储,链表在插入、删除的时候可以达到 O(1) 的时间复杂度(只需要重新指向引用即可,不需要像数组那样移动其他元素)。除此之外,链表还克服了数组必须预先知道数据大小的缺点,从而可以实现灵活的内存动态管理。

    有些小伙伴不知道本文内容和更多相关学习资料的请点赞收藏+评论转发+关注我,后面会有很多干货。我有一些面试题、架构、设计类资料可以说是程序员面试必备!所有资料都整理到网盘了,需要的话欢迎下载!私信我回复【000】即可免费获取


    优点:

    不需要初始化容量;

    可以添加任意元素;

    插入和删除的时候只需要更新引用。

    缺点:

    含有大量的引用,占用的内存空间大;

    查找元素需要遍历整个链表,耗时。

    ③、栈

    栈就好像水桶一样,底部是密封的,顶部是开口,水可以进可以出。用过水桶的小伙伴应该明白这样一个道理:先进去的水在桶的底部,后进去的水在桶的顶部;后进去的水先被倒出来,先进去的水后被倒出来。

    同理,栈按照“后进先出”、“先进后出”的原则来存储数据,先插入的数据被压入栈底,后插入的数据在栈顶,读出数据的时候,从栈顶开始依次读出。

     

    ④、队列

    队列就好像一段水管一样,两端都是开口的,水从一端进去,然后从另外一端出来。先进去的水先出来,后进去的水后出来。

    和水管有些不同的是,队列会对两端进行定义,一端叫队头,另外一端就叫队尾。队头只允许删除操作(出队),队尾只允许插入操作(入队)。
     

    ⑤、树

    树是一种典型的非线性结构,它是由 n(n>0)个有限节点组成的一个具有层次关系的集合。 

    之所以叫“树”,是因为这种数据结构看起来就像是一个倒挂的树,只不过根在上,叶在下。树形数据结构有以下这些特点:

    每个节点都只有有限个子节点或无子节点;

    没有父节点的节点称为根节点;

    每一个非根节点有且只有一个父节点;

    除了根节点外,每个子节点可以分为多个不相交的子树。

    下图展示了树的一些术语:

     

     

     

     

     

     

    基于二叉查找树的特点,它相比较于其他数据结构的优势就在于查找、插入的时间复杂度较低,为 O(logn)。假如我们要从上图中查找 5 个元素,先从根节点 7 开始找,5 必定在 7 的左侧,找到 4,那 5 必定在 4 的右侧,找到 6,那 5 必定在 6 的左侧,找到了。

    理想情况下,通过 BST 查找节点,所需要检查的节点数可以减半。

    平衡二叉树:当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树,根据科学家的英文名也称为 AVL 树。

    平衡二叉树本质上也是一颗二叉查找树,不过为了限制左右子树的高度差,避免出现倾斜树等偏向于线性结构演化的情况,所以对二叉搜索树中每个节点的左右子树作了限制,左右子树的高度差称之为平衡因子,树中每个节点的平衡因子绝对值不大于 1。

    平衡二叉树的难点在于,当删除或者增加节点的情况下,如何通过左旋或者右旋的方式来保持左右平衡。

    Java 中最常见的平衡二叉树就是红黑树,节点是红色或者黑色,通过颜色的约束来维持着二叉树的平衡:

    1)每个节点都只能是红色或者黑色

    2)根节点是黑色

    3)每个叶节点(NIL 节点,空节点)是黑色的。

    4)如果一个节点是红色的,则它两个子节点都是黑色的。也就是说在一条路径上不能出现相邻的两个红色节点。

    5)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

     

    ⑥、堆

    堆可以被看做是一棵树的数组对象,具有以下特点:

    堆中某个节点的值总是不大于或不小于其父节点的值;

    堆总是一棵完全二叉树。

    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

     

    在线性结构中,数据元素之间满足唯一的线性关系,每个数据元素(除第一个和最后一个外)均有唯一的“前驱”和“后继”;

    在树形结构中,数据元素之间有着明显的层次关系,并且每个数据元素只与上一层中的一个元素(父节点)及下一层的多个元素(子节点)相关;

    而在图形结构中,节点之间的关系是任意的,图中任意两个数据元素之间都有可能相关。

    ⑧、哈希表

    哈希表(Hash Table),也叫散列表,是一种可以通过关键码值(key-value)直接访问的数据结构,它最大的特点就是可以快速实现查找、插入和删除。

    数组的最大特点就是查找容易,插入和删除困难;而链表正好相反,查找困难,而插入和删除容易。哈希表很完美地结合了两者的优点, Java 的 HashMap 在此基础上还加入了树的优点。

     

    哈希函数在哈希表中起着⾮常关键的作⽤,它可以把任意长度的输入变换成固定长度的输出,该输出就是哈希值。哈希函数使得一个数据序列的访问过程变得更加迅速有效,通过哈希函数,数据元素能够被很快的进行定位。

    若关键字为 k,则其值存放在 hash(k) 的存储位置上。由此,不需要遍历就可以直接取得 k 对应的值。

    对于任意两个不同的数据块,其哈希值相同的可能性极小,也就是说,对于一个给定的数据块,找到和它哈希值相同的数据块极为困难。再者,对于一个数据块,哪怕只改动它的一个比特位,其哈希值的改动也会非常的大——这正是 Hash 存在的价值!

    尽管可能性极小,但仍然会发生,如果哈希冲突了,Java 的 HashMap 会在数组的同一个位置上增加链表,如果链表的长度大于 8,将会转化成红黑树进行处理——这就是所谓的拉链法(数组+链表)。

    总结:

     有些小伙伴不知道本文内容和更多相关学习资料的请点赞收藏+评论转发+关注我,后面会有很多干货。

     

    展开全文
  • 数据结构有什么用? 常见数据结构 栈 队列 数组 链表 红黑树
  • 数据结构在实际应用中非常常见,现在各种算法基本都牵涉到数据结构,因此,掌握数据结构算是软件工程师的必备技能。 一、什么是数据结构 数据结构,直白地理解,就是研究数据的存储方式。 我们知道,数据存储只有一...
  • 数据结构:八大常见数据结构

    千次阅读 2019-11-26 14:42:39
    数据结构目录: 一、结构分类 二、区别联系 1. 数组 2. 栈 ...数据结构是指,相互之间存在着一种或多种关系的...数据结构大多是以三种分类方式分类,分别是逻辑结构,物理结构存储结构,一般来讲大多是以逻辑结...
  • 数据结构常见问题:12单元5 线性表的存储结构.doc
  • 常见数据结构总结(8种)

    千次阅读 2022-07-05 16:55:34
    每一种数据结构都有着独特的数据存储方式。常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 1. 顺序表(数组 Array) 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构...
  • 上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见数据结构,原来我们学过的数据结构有这么多~ 首先,先来回顾下C语言中常见的基本数据...
  • 常见数据结构类型

    千次阅读 2021-10-08 15:28:55
    常见数据结构 目录常见数据结构数据结构是什么?数据结构分类1、数组2、链表3、栈4、队列5、树6、图7、哈希表 数据结构是什么? 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素...
  • 最近在学习数据结构必要对自己这两天的学习做一个总结,今天就来总结下,数据结构的逻辑结构 按照分类标准的不同,我们把数据结构分为逻辑机构和存储结构,今天主要讲解逻辑结构 逻辑结构:是指数据对象中的...
  • 数据结构分类及八种常见数据结构

    千次阅读 2020-05-09 11:04:00
    一.数据结构分类 数据的逻辑结构 ...链式存储结构:使用若干地址分散的存储单元存储数据元素,逻辑上相邻的数据元素在物理位置上不一定相邻,数据元素之间的关系需要采用附加信息特别指定。c语言采
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。 1、数组 数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0...
  • 线性表结构存储数据往往是可以依次排列的,就像小朋友手拉手,每位学生的前面和后面都仅一个小朋友和他拉手,具备这种“一对一”关系的数据就可以使用线性表来存储。 例如,存储类似 {1,3,5,7,9} 这样的数据时,...
  • 常用的数据结构有哪些

    千次阅读 2018-12-07 13:27:18
    (1)线性数据结构:元素之间一般存在元素之间存在一对一关系,是最常用的一类数据结构,典型的:数组、栈、队列和线性表。 (2)树形结构:结点间具有层次关系,每一层的一个结点能且只能和上一层的一个结点相关...
  • 在计算机中,数据元素并不是孤立、杂乱无序的,而是具有内在联系的数据集合。数据元素之间存在一种或多种特定关系,也就是数据的组织形式。为编写出一个 好"的程序,必须分析待处理...这也就是研究数据结构的意义所在。
  • Java中常见的八种数据结构

    千次阅读 2021-12-15 13:53:48
    Java中8种常见数据结构 哈希表(Hash) 队列(Queue) 树(Tree) 堆(Heap) 数组(Array) 栈(Stock) 链表(Linked List) 图(Graph) 哈希表(Hash) 哈希表也叫散列表,是一种可以通过关键码值(Key-Value)直接访问的数据...
  • 数据4种逻辑结构: 1.集合结构:数据元素之间没有任何关系....常见的4种数据存储结构: 1.顺序存储结构:借助数据元素之间的相对位置来表示元素之间的逻辑结构.(vector动态数组、deque双端队列、stack栈容器、queue队...
  • 通过上节我们知道,数据结构是学习数据存储方式的一门学科,那么,数据存储方式哪几种呢?本节将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈...
  • 数据结构面试常见问题

    千次阅读 多人点赞 2021-01-04 16:00:05
    目录一、绪论二、线性表三、栈和队列四、串、数组和广义表五、树和二叉树六、图七...1.最小生成树的算法有哪些?说明一下它们的时间复杂度以及各自的特点。 普里姆(Prim)算法 克鲁斯卡尔(Kruskal)算法 原理 Pr
  • Java常见的8种数据结构

    千次阅读 2022-01-25 14:48:57
    数据结构是指数据在计算机内存空间中或磁盘中的组织形式 算法是完成特定任务的过程 二分法查找 r=2^s s:查找步数 r查找范围 幂函数 s=log2® 已知范围获取需要的次数 对数 算法复杂度使用O(N)函数进行标示 主要是...
  • 数据的逻辑结构存储结构(物理结构)详解什么是数据结构数据的逻辑结构集合线性结构树形结构图形结构数据的物理结构(存储结构)1、顺序存储结构2、链式存储结构3、索引存储结构4、链式存储结构存储结构特点顺序存储...
  • 数据结构有两个概念、逻辑结构,物理结构存储) 逻辑结构:描述数据节点之间的关系,集合结构,线性结构,树形结构,图形结构四种。 物理结构:描述数据在内存中是如何存储的(分配内存空间),顺序存储结构,...
  • 数据库-数据存储-非结构化数据的存储方式。针对Oracle、MySQL、SQL Server、DB2等结构化数据,我们可以选择存储在关系型数据库中。针对诸如视频、音频、文件等非结构化数据,又是如何存储呢?一般视频、大文件都不会...
  • 数据结构(一)线性存储结构

    千次阅读 2019-06-13 14:05:52
    线性结构作为最常用的数据结构,其特点是数据元素之间存在一对一的线性关系。 线性结构拥有两种不同的存储结构,即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的,链式存储...
  • 数据结构是计算机存储、组织数据的方式。...在不同场景下,数据需要以特定的方式存储,我们不同的数据结构可以满足我们的需求。常用的数据结构有:数组、栈、队列、链表、图、树、前缀树、哈希表。 ...
  • 数据的逻辑结构存储结构

    千次阅读 2019-09-07 21:50:35
    2,线性结构数据元素之间存在一一对应的关系,其开始节点和终端节点具有唯一性,除了开始开始节点和终端节点,其他的元素且仅一个前驱节点和后继节点,线性表就是一个典型。 3,树形结构数据元素之间存在着...
  • 数据结构:八种数据结构大全

    万次阅读 多人点赞 2021-07-29 12:36:10
    常用的数据结构有:数组(Array)、栈(Stack)、队列(Queue)、链表(Linked List)、树(Tree)、图(Graph)、堆(Heap)、散列表(Hash)等; 1.2 数据结构的分类 1.2.1 排列方式 1)集合 集合:数据结构中的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,327,676
精华内容 931,070
热门标签
关键字:

常见的数据存储结构有哪些