精华内容
下载资源
问答
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    常用数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。 1、数组 数组是可以再内存中连续存储多个元素的...

    本文目录:

    数据结构分类

    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。
    常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示:
    这里写图片描述
    每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。

    1、数组

    数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

    int[] data = new int[100];data[0]  = 1;
    

    优点:
    1、按照索引查询元素速度快
    2、按照索引遍历数组方便

    缺点:
    1、数组的大小固定后就无法扩容了
    2、数组只能存储一种类型的数据
    3、添加,删除的操作慢,因为要移动其他的元素。

    适用场景:
    频繁查询,对存储空间要求不大,很少增加和删除的情况。

    2、栈

    栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。
    这里写图片描述
    栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。

    3、队列

    队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队,示例图如下:
    这里写图片描述
    使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

    4、链表

    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
    这里写图片描述
    链表的优点:
    链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
    添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

    缺点:
    因为含有大量的指针域,占用空间较大;
    查找元素需要遍历链表来查找,非常耗时。

    适用场景:
    数据量较小,需要频繁增加,删除操作的场景

    5、树

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

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

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

    1、每个结点最多有两颗子树,结点的度最大为2。
    2、左子树和右子树是有顺序的,次序不能颠倒。
    3、即使某结点只有一个子树,也要区分左右子树。

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

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

    6、散列表

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

    记录的存储位置=f(key)

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

    哈希表在应用中也是比较常见的,就如Java中有些集合类就是借鉴了哈希原理构造的,例如HashMap,HashTable等,利用hash表的优势,对于集合的查找元素时非常方便的,然而,因为哈希表是基于数组衍生的数据结构,在添加删除元素方面是比较慢的,所以很多时候需要用到一种数组链表来做,也就是拉链法。拉链法是数组结合链表的一种结构,较早前的hashMap底层的存储就是采用这种结构,直到jdk1.8之后才换成了数组加红黑树的结构,其示例图如下:
    这里写图片描述
    从图中可以看出,左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

    哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。

    7、堆

    堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

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

    • 堆总是一棵完全二叉树。

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

    堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
    (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2),满足前者的表达式的成为小顶堆,满足后者表达式的为大顶堆,这两者的结构图可以用完全二叉树排列出来,示例图如下:
    这里写图片描述
    因为堆有序的特点,一般用来做数组中的排序,称为堆排序。

    8、图

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

    按照顶点指向的方向可分为无向图和有向图:
    这里写图片描述
    这里写图片描述
    图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构,这里不做展开,读者有兴趣可以自己学习深入。

    展开全文
  • 图解!24张图彻底弄懂九大常见数据结构

    万次阅读 多人点赞 2020-05-24 22:23:36
    ​数据结构想必大家都不会陌生,对于一个...数据结构种类繁多,本文将通过图解的方式对常用的数据结构进行理论上的介绍和讲解,以方便大家掌握常用数据结构的基本知识。 本文提纲: 1数组 数组可以说是最基本最...

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

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

    本文提纲:

     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  总结

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

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

    ------------

    感兴趣可微信搜索【业余码农】,阅读更多技术干货!

    展开全文
  • 数据结构算法常见面试考题

    万次阅读 多人点赞 2018-11-08 09:29:44
    数据结构上几种树集中的讨论一下: 1.AVLtree 定义:最先发明的自平衡二叉查找树。在AVL树中任何节点的个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)...

    (1) 红黑树的了解(平衡树,二叉搜索树),使用场景

    把数据结构上几种树集中的讨论一下:

    1.AVLtree

    定义:最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

    节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的,并需要重新平衡这个树。平衡因子可以直接存储在每个节点中,或从可能存储在节点中的子树高度计算出来。
    一般我们所看见的都是排序平衡二叉树。

    AVLtree使用场景:AVL树适合用于插入删除次数比较少,但查找多的情况。插入删除导致很多的旋转,旋转是非常耗时的。AVL 在linux内核的vm area中使用。

    2.二叉搜索树

    二叉搜索树也是一种树,适用与一般二叉树的全部操作,但二叉搜索树能够实现数据的快速查找。

    二叉搜索树满足的条件:

    1.非空左子树的所有键值小于其根节点的键值
    2.非空右子树的所有键值大于其根节点的键值
    3.左右子树都是二叉搜索树

    二叉搜索树的应用场景:如果是没有退化称为链表的二叉树,查找效率就是lgn,效率不错,但是一旦退换称为链表了,要么使用平衡二叉树,或者之后的RB树,因为链表就是线性的查找效率。

    3.红黑树的定义

    红黑树是一种二叉查找树,但在每个结点上增加了一个存储位表示结点的颜色,可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。

    当二叉查找树的高度较低时,这些操作执行的比较快,但是当树的高度较高时,这些操作的性能可能不比用链表好。红黑树(red-black tree)是一种平衡的二叉查找树,它能保证在最坏情况下,基本的动态操作集合运行时间为O(lgn)。

    红黑树必须要满足的五条性质:

    性质一:节点是红色或者是黑色; 在树里面的节点不是红色的就是黑色的,没有其他颜色,要不怎么叫红黑树呢,是吧。

    性质二:根节点是黑色; 根节点总是黑色的。它不能为红。

    性质三:每个叶节点(NIL或空节点)是黑色;

    性质四:每个红色节点的两个子节点都是黑色的(也就是说不存在两个连续的红色节点); 就是连续的两个节点不能是连续的红色,连续的两个节点的意思就是父节点与子节点不能是连续的红色。

    性质五:从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点。从根节点到每一个NIL节点的路径中,都包含了相同数量的黑色节点。

    红黑树的应用场景:红黑树是一种不是非常严格的平衡二叉树,没有AVLtree那么严格的平衡要求,所以它的平均查找,增添删除效率都还不错。广泛用在C++的STL中。如map和set都是用红黑树实现的。

    4.B树定义

    B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个),不属于二叉搜索树的范畴,因为它不止两路,存在多路。

    B树满足的条件:

    (1)树种的每个节点最多拥有m个子节点且m>=2,空树除外(注:m阶代表一个树节点最多有多少个查找路径,m阶=m路,当m=2则是2叉树,m=3则是3叉);
    (2)除根节点外每个节点的关键字数量大于等于ceil(m/2)-1个小于等于m-1个,非根节点关键字数必须>=2;(注:ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2)
    (3)所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子
    (4)如果一个非叶节点有N个子节点,则该节点的关键字数等于N-1;
    (5)所有节点关键字是按递增次序排列,并遵循左小右大原则;

    B树的应用场景:构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。

    5.B+树

    B+树是B树的一个升级版,B+树是B树的变种树,有n棵子树的节点中含有n个关键字,每个关键字不保存数据,只用来索引,数据都保存在叶子节点。是为文件系统而生的。

    相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定;我们先看看两者的区别

    (1)B+跟B树不同,B+树的非叶子节点不保存关键字记录的指针,这样使得B+树每个节点所能保存的关键字大大增加;
    (2)B+树叶子节点保存了父节点的所有关键字和关键字记录的指针,每个叶子节点的关键字从小到大链接;
    (3)B+树的根节点关键字数量和其子节点个数相等;
    (4)B+的非叶子节点只进行数据索引,不会存实际的关键字记录的指针,所有数据地址必须要到叶子节点才能获取到,所以每次数据查询的次数都一样;

    特点:
    在B树的基础上每个节点存储的关键字数更多,树的层级更少所以查询数据更快,所有指关键字指针都存在叶子节点,所以每次查找的次数都相同所以查询速度更稳定;

    应用场景: 用在磁盘文件组织 数据索引和数据库索引。

    6.Trie树(字典树)

    trie,又称前缀树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

    在图示中,键标注在节点中,值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie 可以看作是一个确定有限状态自动机,尽管边上的符号一般是隐含在分支的顺序中的。
    键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示 trie 的原理。

    trie树的优点:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。缺点:Trie树是一种比较简单的数据结构.理解起来比较简单,正所谓简单的东西也得付出代价.故Trie树也有它的缺点,Trie树的内存消耗非常大.

    其基本性质可以归纳为:

    1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
    2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
    3. 每个节点的所有子节点包含的字符都不相同。

    典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。

    (2) 红黑树在STL上的应用

    STL中set、multiset、map、multimap底层是红黑树实现的,而unordered_map、unordered_set 底层是哈希表实现的。

    multiset、multimap: 插入相同的key的时候,我们将后插入的key放在相等的key的右边,之后不管怎么进行插入或删除操作,后加入的key始终被认为比之前的大。

    (3) 了解并查集吗?(低频)

    什么是合并查找问题呢?

    顾名思义,就是既有合并又有查找操作的问题。举个例子,有一群人,他们之间有若干好友关系。如果两个人有直接或者间接好友关系,那么我们就说他们在同一个朋友圈中,这里解释下,如果Alice是Bob好友的好友,或者好友的好友的好友等等,即通过若干好友可以认识,那么我们说Alice和Bob是间接好友。随着时间的变化,这群人中有可能会有新的朋友关系,这时候我们会对当中某些人是否在同一朋友圈进行询问。这就是一个典型的合并-查找操作问题,既包含了合并操作,又包含了查找操作。

    并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。

    并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。

    并查集也是使用树形结构实现。不过,不是二叉树。每个元素对应一个节点,每个组对应一棵树。在并查集中,哪个节点是哪个节点的父亲以及树的形状等信息无需多加关注,整体组成一个树形结构才是重要的。类似森林

    (4) 贪心算法和动态规划的区别

    贪心算法:局部最优,划分的每个子问题都最优,得到全局最优,但是不能保证是全局最优解,所以对于贪心算法来说,解是从上到下的,一步一步最优,直到最后。

    动态规划:将问题分解成重复的子问题,每次都寻找左右子问题解中最优的解,一步步得到全局的最优解.重复的子问题可以通过记录的方式,避免多次计算。所以对于动态规划来说,解是从小到上,从底层所有可能性中找到最优解,再一步步向上。

    分治法:和动态规划类似,将大问题分解成小问题,但是这些小问题是独立的,没有重复的问题。独立问题取得解,再合并成大问题的解。

    例子:比如钱币分为1元3元4元,要拿6元钱,贪心的话,先拿4,再拿两个1,一共3张钱;实际最优却是两张3元就够了。

    (5) 判断一个链表是否有环,如何找到这个环的起点

    给定一个单链表,只给出头指针h:
    1、如何判断是否存在环?
    2、如何知道环的长度?
    3、如何找出环的连接点在哪里?
    4、带环链表的长度是多少?

    解法:
    1、对于问题1,使用追赶的方法,设定两个指针slow、fast,从头指针开始,每次分别前进1步、2步。如存在环,则两者相遇;如不存在环,fast遇到NULL退出。
    2、对于问题2,记录下问题1的碰撞点p,slow、fast从该点开始,再次碰撞所走过的操作数就是环的长度s。
    3、问题3:有定理:碰撞点p到连接点的距离=头指针到连接点的距离,因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。(证明在后面附注)
    4、问题3中已经求出连接点距离头指针的长度,加上问题2中求出的环的长度,二者之和就是带环单链表的长度
    http://blog.sina.com.cn/s/blog_725dd1010100tqwp.html

    (6) 实现一个strcpy函数(或者memcpy),如果内存可能重叠呢

    ——大家一般认为名不见经传strcpy函数实现不是很难,流行的strcpy函数写法是:

      1. char *my_strcpy(char *dst,const char *src)  
      2. {  
      3.     assert(dst != NULL);  
      4.     assert(src != NULL);  
      5.     char *ret = dst;  
      6.     while((* dst++ = * src++) != '\0')   
      7.         ;  
      8.     return ret;  
      9. }  
    

    如果注意到:
    1,检查指针有效性;
    2,返回目的指针des;
    3,源字符串的末尾 ‘\0’ 需要拷贝。

    内存重叠

    内存重叠:拷贝的目的地址在源地址范围内。所谓内存重叠就是拷贝的目的地址和源地址有重叠。
    在函数strcpy和函数memcpy都没有对内存重叠做处理的,使用这两个函数的时候只有程序员自己保证源地址和目标地址不重叠,或者使用memmove函数进行内存拷贝。
    memmove函数对内存重叠做了处理。
    strcpy的正确实现应为:

      1. char *my_strcpy(char *dst,const char *src)  
      2. {  
      3.     assert(dst != NULL);  
      4.     assert(src != NULL);  
      5.     char *ret = dst;  
      6.     memmove(dst,src,strlen(src)+1);  
      7.     return ret;  
      8. }  
    

    memmove函数实现时考虑到了内存重叠的情况,可以完成指定大小的内存拷贝

    (7) 快排存在的问题,如何优化

    快排的时间复杂度

    时间复杂度最快平均是O(nlogn),最慢的时候是O(n2);辅助空间也是O(logn);最开始学快排时最疑惑的就是这个东西不知道怎么得来的,一种是通过数学运算可以的出来,还有一种是通过递归树来理解就容易多了

    这张图片别人博客那里弄过来的,所谓时间复杂度最理想的就是取到中位数情况,那么递归树就是一个完全二叉树,那么树的深度也就是最低为Logn,这个时候每一次又需要n次比较,所以时间复杂度nlogn,当快排为顺序或者逆序时,这个数为一个斜二叉树,深度为n,同样每次需要n次比较,那那么最坏需要n2的时间

    优化:

    1.当整个序列有序时退出算法;
    2.当序列长度很小时(根据经验是大概小于 8),应该使用常数更小的算法,比如插入排序等;
    3.随机选取分割位置;
    4.当分割位置不理想时,考虑是否重新选取分割位置;
    5.分割成两个序列时,只对其中一个递归进去,另一个序列仍可以在这一函数内继续划分,可以显著减小栈的大小(尾递归):
    6.将单向扫描改成双向扫描,可以减少划分过程中的交换次数

    优化1:当待排序序列的长度分割到一定大小后,使用插入排序
    原因:对于很小和部分有序的数组,快排不如插排好。当待排序序列的长度分割到一定大小后,继续分割的效率比插入排序要差,此时可以使用插排而不是快排

    优化2:在一次分割结束后,可以把与Key相等的元素聚在一起,继续下次分割时,不用再对与key相等元素分割

    优化3:优化递归操作
    快排函数在函数尾部有两次递归操作,我们可以对其使用尾递归优化

    优点:如果待排序的序列划分极端不平衡,递归的深度将趋近于n,而栈的大小是很有限的,每次递归调用都会耗费一定的栈空间,函数的参数越多,每次递归耗费的空间也越多。优化后,可以缩减堆栈深度,由原来的O(n)缩减为O(logn),将会提高性能。

    (8) Top K问题(可以采取的方法有哪些,各自优点?)

    1.将输入内容(假设用数组存放)进行完全排序,从中选出排在前K的元素即为所求。有了这个思路,我们可以选择相应的排序算法进行处理,目前来看快速排序,堆排序和归并排序都能达到O(nlogn)的时间复杂度。

    2.对输入内容进行部分排序,即只对前K大的元素进行排序(这K个元素即为所求)。此时我们可以选择冒泡排序或选择排序进行处理,即每次冒泡(选择)都能找到所求的一个元素。这类策略的时间复杂度是O(Kn)。

    3.对输入内容不进行排序,显而易见,这种策略将会有更好的性能开销。我们此时可以选择两种策略进行处理:

    用一个桶来装前k个数,桶里面可以按照最小堆来维护
    a)利用最小堆维护一个大小为K的数组,目前该小根堆中的元素是排名前K的数,其中根是最小的数。此后,每次从原数组中取一个元素与根进行比较,如大于根的元素,则将根元素替换并进行堆调整(下沉),即保证小根堆中的元素仍然是排名前K的数,且根元素仍然最小;否则不予处理,取下一个数组元素继续该过程。该算法的时间复杂度是O(nlogK),一般来说企业中都采用该策略处理top-K问题,因为该算法不需要一次将原数组中的内容全部加载到内存中,而这正是海量数据处理必然会面临的一个关卡。

    b)利用快速排序的分划函数找到分划位置K,则其前面的内容即为所求。该算法是一种非常有效的处理方式,时间复杂度是O(n)(证明可以参考算法导论书籍)。对于能一次加载到内存中的数组,该策略非常优秀。

    (9) Bitmap的使用,存储和插入方法

    BitMap从字面的意思

    很多人认为是位图,其实准确的来说,翻译成基于位的映射。
    在所有具有性能优化的数据结构中,大家使用最多的就是hash表,是的,在具有定位查找上具有O(1)的常量时间,多么的简洁优美。但是数据量大了,内存就不够了。
    当然也可以使用类似外排序来解决问题的,由于要走IO所以时间上又不行。
    所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。
    其实如果你知道计数排序的话(算法导论中有一节讲过),你就会发现这个和计数排序很像。

    bitmap应用

       1)可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下。
       2)去重数据而达到压缩数据
    

    还可以用于爬虫系统中url去重、解决全组合问题。

    BitMap应用:排序示例

    假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0(如下图:)

    然后遍历这5个元素,首先第一个元素是4,那么就把4对应的位置为1(可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况,这里默认为Big-ending。不过计算机一般是小端存储的,如intel。小端的话就是将倒数第5位置1),因为是从零开始的,所以要把第五位置为一(如下图):

    然后再处理第二个元素7,将第八位置为1,,接着再处理第三个元素,一直到最后处理完所有的元素,将相应的位置为1,这时候的内存的Bit位的状态如下:

    然后我们现在遍历一遍Bit区域,将该位是一的位的编号输出(2,3,4,5,7),这样就达到了排序的目的。

    bitmap排序复杂度分析

    Bitmap排序需要的时间复杂度和空间复杂度依赖于数据中最大的数字。
    bitmap排序的时间复杂度不是O(N)的,而是取决于待排序数组中的最大值MAX,在实际应用上关系也不大,比如我开10个线程去读byte数组,那么复杂度为:O(Max/10)。也就是要是读取的,可以用多线程的方式去读取。时间复杂度方面也是O(Max/n),其中Max为byte[]数组的大小,n为线程大小。
    空间复杂度应该就是O(Max/8)bytes吧

    BitMap算法流程

    假设需要排序或者查找的最大数MAX=10000000(lz:这里MAX应该是最大的数而不是int数据的总数!),那么我们需要申请内存空间的大小为int a[1 + MAX/32]。
    其中:a[0]在内存中占32为可以对应十进制数0-31,依次类推:
    bitmap表为:
    a[0]--------->0-31
    a[1]--------->32-63
    a[2]--------->64-95
    a[3]--------->96-127

    我们要把一个整数N映射到Bit-Map中去,首先要确定把这个N Mapping到哪一个数组元素中去,即确定映射元素的index。我们用int类型的数组作为map的元素,这样我们就知道了一个元素能够表示的数字个数(这里是32)。于是N/32就可以知道我们需要映射的key了。所以余下来的那个N%32就是要映射到的位数。

    1.求十进制数对应在数组a中的下标:

    先由十进制数n转换为与32的余可转化为对应在数组a中的下标。
    如十进制数0-31,都应该对应在a[0]中,比如n=24,那么 n/32=0,则24对应在数组a中的下标为0。又比如n=60,那么n/32=1,则60对应在数组a中的下标为1,同理可以计算0-N在数组a中的下标。
    i = N>>K % 结果就是N/(2^K)
    Note: map的范围是[0, 原数组最大的数对应的2的整次方数-1]。

    2.求十进制数对应数组元素a[i]在0-31中的位m:

    十进制数0-31就对应0-31,而32-63则对应也是0-31,即给定一个数n可以通过模32求得对应0-31中的数。
    m = n & ((1 << K) - 1) %结果就是n%(2^K)

    3.利用移位0-31使得对应第m个bit位为1

    如a[i]的第m位置1:a[i] = a[i] | (1<<m)
    如:将当前4对应的bit位置1的话,只需要1左移4位与B[0] | 即可。

    Note:

    1 p+(i/8)|(0×01<<(i%8))这样也可以?
    2 同理将int型变量a的第k位清0,即a=a&~(1<<k)

    BitMap算法评价

    优点:
    1. 运算效率高,不进行比较和移位;
    2. 占用内存少,比如最大的数MAX=10000000;只需占用内存为MAX/8=1250000Byte=1.25M。
    3.
    缺点:
    1. 所有的数据不能重复,即不可对重复的数据进行排序。(少量重复数据查找还是可以的,用2-bitmap)。
    2. 当数据类似(1,1000,10万)只有3个数据的时候,用bitmap时间复杂度和空间复杂度相当大,只有当数据比较密集时才有优势。
    http://blog.csdn.net/pipisorry/article/details/62443757

    (10) 字典树的理解以及在统计上的应用

    Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点.

    就是在海量数据中找出某一个数,比如2亿QQ号中查找出某一个特定的QQ号。。

    (11) N个骰子出现和为m的概率

    典型的可以用动态规划的思想来完成

    1.现在变量有:骰子个数,点数和。当有k个骰子,点数和为n时,出现次数记为f(k,n)。那与k-1个骰子阶段之间的关系是怎样的?

    2.当我有k-1个骰子时,再增加一个骰子,这个骰子的点数只可能为1、2、3、4、5或6。那k个骰子得到点数和为n的情况有:
    (k-1,n-1):第k个骰子投了点数1
    (k-1,n-2):第k个骰子投了点数2
    (k-1,n-3):第k个骰子投了点数3

    (k-1,n-6):第k个骰子投了点数6
    在k-1个骰子的基础上,再增加一个骰子出现点数和为n的结果只有这6种情况!
    所以:f(k,n)=f(k-1,n-1)+f(k-1,n-2)+f(k-1,n-3)+f(k-1,n-4)+f(k-1,n-5)+f(k-1,n-6)

    3.有1个骰子,f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。
    用递归就可以解决这个问题:

    用迭代来完成

    (19) 海量数据问题(可参考左神的书)

    目前关于海量数据想到的解决办法:
    1.bitmap
    2.桶排序,外部排序,将需要排序的放到外存上,不用全部放到内存上

    (20) 一致性哈希

    说明

    http://www.zsythink.net/archives/1182

    优点

    1.当后端是缓存服务器时,经常使用一致性哈希算法来进行负载均衡。使用一致性哈希的好处在于,增减集群的缓存服务器时,只有少量的缓存会失效,回源量较小。
    2.尽量减少数据丢失问题,减少移动数据的风险

    展开全文
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据:所有能被输入到计算机中,且能...

    数据结构

    一些概念

    数据结构就是研究数据的逻辑结构物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

    1. 数据:所有能被输入到计算机中,且能被计算机处理的符号的集合。是计算机操作的对象的总称。
    2. 数据元素:数据(集合)中的一个“个体”,数据及结构中讨论的基本单位
    3. 数据项:数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。
    4. 数据类型:在一种程序设计语言中,变量所具有的数据种类。整型、浮点型、字符型等等

    5. 逻辑结构:数据之间的相互关系。

      • 集合 结构中的数据元素除了同属于一种类型外,别无其它关系。
      • 线性结构 数据元素之间一对一的关系
      • 树形结构 数据元素之间一对多的关系
      • 图状结构或网状结构 结构中的数据元素之间存在多对多的关系
    6. 物理结构/存储结构:数据在计算机中的表示。物理结构是描述数据具体在内存中的存储(如:顺序结构、链式结构、索引结构、哈希结构)等
    7. 在数据结构中,从逻辑上可以将其分为线性结构和非线性结构
    8. 数据结构的基本操作的设置的最重要的准则是,实现应用程序与存储结构的独立。实现应用程序是“逻辑结构”,存储的是“物理结构”。逻辑结构主要是对该结构操作的设定,物理结构是描述数据具体在内存中的存储(如:顺序结构、链式结构、索引结构、希哈结构)等。
    9. 顺序存储结构中,线性表的逻辑顺序和物理顺序总是一致的。但在链式存储结构中,线性表的逻辑顺序和物理顺序一般是不同的。

    10. 算法五个特性: 有穷性、确定性、可行性、输入、输出

    11. 算法设计要求:正确性、可读性、健壮性、高效率与低存储量需求。(好的算法)
    12. 算法的描述有伪程序、流程图、N-S结构图等。E-R图是实体联系模型,不是程序的描述方式。
    13. 设计算法在执行时间时需要考虑:算法选用的规模、问题的规模
    14. 时间复杂度:算法的执行时间与原操作执行次数之和成正比。时间复杂度有小到大:O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)。幂次时间复杂度有小到大O(2n)、O(n!)、O(nn)
    15. 空间复杂度:若输入数据所占空间只取决于问题本身,和算法无关,则只需要分析除输入和程序之外的辅助变量所占额外空间

    线性表

    线性表是一种典型的线性结构。头结点无前驱有一个后继,尾节点无后继有一个前驱。链表只能顺序查找,定位一个元素的时间为O(N),删除一个元素的时间为O(1)

    1. 线性表的顺序存储结构:把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。是一种随机存取的存储结构。顺序存储指内存地址是一块的,随机存取指访问时可以按下标随机访问,存储和存取是不一样的。如果是存储,则是指按顺序的,如果是存取,则是可以随机的,可以利用元素下标进行。数组比线性表速度更快的是:原地逆序、返回中间节点、选择随机节点。
      • 便于线性表的构造和任意元素的访问
      • 插入:插入新结点,之后结点后移。平均时间复杂度:O(n)
      • 删除:删除节点,之后结点前移。平均时间复杂度:O(n)
    2. 线性链表:用一组任意的存储单元来依次存放线性表的结点,这组存储单元即可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。因此,链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址。data域是数据域,用来存放结点的值。next是指针域(亦称链域),用来存放结点的直接后继的地址(或位置)。不需要事先估计存储空间大小。
      • 单链表中每个结点的存储地址是存放在其前趋结点next域中,而开始结点无前趋,故应设头指针head指向开始结点。同时,由于最后一个结点无后继,故结点的指针域为空,即NULL。头插法建表(逆序)、尾插法建表(顺序)。增加头结点的目的是算法实现上的方便,但增大了内存开销。
        • 查找:只能从链表的头指针出发,顺链域next逐个结点往下搜索,直到搜索到第i个结点为止。因此,链表不是随机存取结构
        • 插入:先找到表的第i-1的存储位置,然后插入。新结点先连后继,再连前驱。
        • 删除:首先找到ai-1的存储位置p。然后令p–>next指向ai的直接后继结点,即把ai从链上摘下。最后释放结点ai的空间.r=p->next;p->next=r->next;delete r。
        • 判断一个单向链表中是否存在环的最佳方法是快慢指针。
      • 静态链表:用一维数组来实现线性链表,这种用一维数组表示的线性链表,称为静态链表。静态:体现在表的容量是一定的。(数组的大小);链表:插入与删除同前面所述的动态链表方法相同。静态链表中指针表示的是下一元素在数组中的位置。
      • 静态链表是用数组实现的,是顺序的存储结构,在物理地址上是连续的,而且需要预先分配大小。动态链表是用申请内存函数(C是malloc,C++是new)动态申请内存的,所以在链表的长度上没有限制。动态链表因为是动态申请内存的,所以每个节点的物理地址不连续,要通过指针来顺序访问。静态链表在插入、删除时也是通过修改指针域来实现的,与动态链表没有什么分别
      • 循环链表:是一种头尾相接的链表。其特点是无须增加存储量,仅对表的链接方式稍作改变,即可使得表处理更加方便灵活。
        • 在单链表中,将终端结点的指针域NULL改为指向表头结点的或开始结点,就得到了单链形式的循环链表,并简单称为单循环链表。由于循环链表中没有NULL指针,故涉及遍历操作时,其终止条件就不再像非循环链表那样判断p或p—>next是否为空,而是判断它们是否等于某一指定指针,如头指针或尾指针等。
      • 双向链表:在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链。双链表一般由头指针唯一确定的,将头结点和尾结点链接起来构成循环链表,并称之为双向链表。设指针p指向某一结点,则双向链表结构的对称性可用下式描述:p—>prior—>next=p=p—>next—>prior。从两个方向搜索双链表,比从一个方向搜索双链表的方差要小。
        • 插入:先搞定插入节点的前驱和后继,再搞定后结点的前驱,最后搞定前结点的后继。
        • 在有序双向链表中定位删除一个元素的平均时间复杂度为O(n)
        • 可以直接删除当前指针所指向的节点。而不需要像单向链表中,删除一个元素必须找到其前驱。因此在插入数据时,单向链表和双向链表操作复杂度相同,而删除数据时,双向链表的性能优于单向链表

    栈和队列

    栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。先进后出。top= -1时为空栈,top=0只能说明栈中只有一个元素,并且元素进栈时top应该自增

    1. 顺序存储栈:顺序存储结构
    2. 链栈:链式存储结构。插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。通常不会出现栈满的情况。 不需要判断栈满但需要判断栈空。
    3. 两个栈共用静态存储空间,对头使用也存在空间溢出问题。栈1的底在v[1],栈2的底在V[m],则栈满的条件是top[1]+1=top[2]。
    4. 基本操作:删除栈顶元素、判断栈是否为空以及将栈置为空栈等
    5. 对于n各元素的入栈问题,可能的出栈顺序有C(2n,n)/(n+1)个。
    6. 堆栈溢出一般是循环的递归调用、大数据结构的局部变量导致的

    应用,代码

    1. 进制转换
    2. 括号匹配的检验
    3. 行编辑程序
    4. 迷宫求解:若当前位置“可通”,则纳入路径,继续前进;若当前位置“不可通”,则后退,换方向继续探索;若四周“均无通路”,则将当前位置从路径中删除出去。
    5. 表达式求解:前缀、中缀、后缀。
      • 操作数之间的相对次序不变;
      • 运算符的相对次序不同;
      • 中缀式丢失了括弧信息,致使运算的次序不确定
      • 前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式
      • 后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。
    6. 实现递归:多个函数嵌套调用的规则是:后调用先返回。
    7. 浏览器历史纪录,Android中的最近任务,Activity的启动模式,CPU中栈的实现,Word自动保存,解析计算式,解析xml/json。解析XML时,需要校验节点是否闭合,节点闭合的话,有头尾符号相对应,遇到头符号将其放入栈中,遇到尾符号时,弹出栈的内容,看是否有与之对应的头符号,栈的特性刚好符合符号匹配的就近原则。

    不是所有的递归程序都需要栈来保护现场,比方说求阶乘的,是单向递归,直接用循环去替代从1乘到n就是结果了,另外一些需要栈保存的也可以用队列等来替代。不是所有的递归转化为非递归都要用到栈。转化为非递归主要有两种方法:对于尾递归或单向递归,可以用循环结构算法代替

    队列

    队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入,而在另一端进行删除。允许删除的一端称为队头(front),允许插入的一端称为队尾(rear)。先进先出。

    1. 顺序队列:顺序存储结构。当头尾指针相等时队列为空。在非空队列里,头指针始终指向队头前一个位置,而尾指针始终指向队尾元素的实际位置
    2. 循环队列。在循环队列中进行出队、入队操作时,头尾指针仍要加1,朝前移动。只不过当头尾指针指向向量上界(MaxSize-1)时,其加1操作的结果是指向向量的下界0。除非向量空间真的被队列元素全部占用,否则不会上溢。因此,除一些简单的应用外,真正实用的顺序队列是循环队列。故队空和队满时头尾指针均相等。因此,我们无法通过front=rear来判断队列“空”还是“满”
    3. 链队列:链式存储结构。限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作,为此再增加一个尾指针,指向链表的最后一个结点。
    4. 设尾指针的循环链表表示队列,则入队和出队算法的时间复杂度均为O(1)。用循环链表表示队列,必定有链表的头结点,入队操作在链表尾插入,直接插入在尾指针指向的节点后面,时间复杂度是常数级的;出队操作在链表表头进行,也就是删除表头指向的节点,时间复杂度也是常数级的。

    5. 队空条件:rear==front,但是一般需要引入新的标记来说明栈满还是栈空,比如每个位置布尔值

    6. 队满条件:(rear+1) % QueueSize==front,其中QueueSize为循环队列的最大长度
    7. 计算队列长度:(rear-front+QueueSize)% QueueSize
    8. 入队:(rear+1)% QueueSize
    9. 出队:(front+1)% QueueSize
    10. 假设以数组A[N]为容量存放循环队列的元素,其头指针是front,当前队列有X个元素,则队列的尾指针值为(front+X mod N)

    串(String)是零个或多个字符组成的有限序列。长度为零的串称为空串(Empty String),它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意:空串和空白串的不同,例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。

    串的表示和实现:

    1. 定长顺序存储表示。静态存储分配的顺序表。
    2. 堆分配存储表示。存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表
    3. 串的链式存储结构。

    串匹配:将主串称为目标串,子串称之为模式串。蛮力法匹配。KMP算法匹配。Boyer-Moore算法匹配。

    数组和广义表

    数组和广义表可看成是一种特殊的线性表,其特殊在于: 表中的元素本身也是一种线性表。内存连续。根据下标在O(1)时间读/写任何元素。

    二维数组,多维数组,广义表、树、图都属于非线性结构

    数组

    数组的顺序存储:行优先顺序;列优先顺序。数组中的任一元素可以在相同的时间内存取,即顺序存储的数组是一个随机存取结构。

    关联数组(Associative Array),又称映射(Map)、字典( Dictionary)是一个抽象的数据结构,它包含着类似于(键,值)的有序对。 不是线性表。

    矩阵的压缩:

    1. 对称矩阵、三角矩阵:直接存储矩阵的上三角或者下三角元素。注意区分i>=j和i

    广义表

    广义表(Lists,又称列表)是线性表的推广。广义表是n(n≥0)个元素a1,a2,a3,…,an的有限序列,其中ai或者是原子项,或者是一个广义表。若广义表LS(n>=1)非空,则a1是LS的表头,其余元素组成的表(a2,…an)称为LS的表尾。广义表的元素可以是广义表,也可以是原子,广义表的元素也可以为空。表尾是指除去表头后剩下的元素组成的表,表头可以为表或单元素值。所以表尾不可以是单个元素值。

    例子:

    1. A=()——A是一个空表,其长度为零。
    2. B=(e)——表B只有一个原子e,B的长度为1。
    3. C=(a,(b,c,d))——表C的长度为2,两个元素分别为原子a和子表(b,c,d)。
    4. D=(A,B,C)——表D的长度为3,三个元素都是广义 表。显然,将子表的值代入后,则有D=(( ),(e),(a,(b,c,d)))。
    5. E=(a,E)——这是一个递归的表,它的长度为2,E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).

    三个结论:

    1. 广义表的元素可以是子表,而子表的元素还可以是子表。由此,广义表是一个多层次的结构,可以用图形象地表示
    2. 广义表可为其它表所共享。例如在上述例4中,广义表A,B,C为D的子表,则在D中可以不必列出子表的值,而是通过子表的名称来引用。
    3. 广义表的递归性

    考点:

    1. 广义表是0个或多个单因素或子表组成的有限序列,广义表可以是自身的子表,广义表的长度n>=0,所以可以为空表。广义表的同级元素(直属于同一个表中的各元素)具有线性关系
    2. 广义表的表头为空,并不代表该广义表为空表。广义表()和(())不同。前者是长度为0的空表,对其不能做求表头和表尾的运算;而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表),对其可进行分解,得到的表头和表尾均是空表()
    3. 已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是head(tail(head(tail(LS)))。根据表头、表尾的定义可知:任何一个非空广义表的表头是表中第一个元素,它可以是原子,也可以是子表,而其表尾必定是子表。也就是说,广义表的head操作,取出的元素是什么,那么结果就是什么。但是tail操作取出的元素外必须加一个表——“()“。tail(LS)=((d,e,f));head(tail(LS))=(d,e,f);tail(head(tail(LS)))=(e,f);head(tail(head(tail(LS))))=e。
    4. 二维以上的数组其实是一种特殊的广义表
    5. 在(非空)广义表中:1、表头head可以是原子或者一个表 2、表尾tail一定是一个表 3.广义表难以用顺序存储结构 4.广义表可以是一个多层次的结构

    树和二叉树

    一种非线性结构。树是递归结构,在树的定义中又用到了树的概念。

    基本术语:

    1. 树结点:包含一个数据元素及若干指向子树的分支;
    2. 孩子结点:结点的子树的根称为该结点的孩子;
    3. 双亲结点:B结点是A结点的孩子,则A结点是B结点的双亲;
    4. 兄弟结点:同一双亲的孩子结点;
    5. 堂兄结点:同一层上结点;
    6. 结点层次:根结点的层定义为1;根的孩子为第二层结点,依此类推;
    7. 树的高(深)度:树中最大的结点层
    8. 结点的度:结点子树的个数
    9. 树的度: 树中最大的结点度。
    10. 叶子结点:也叫终端结点,是度为0的结点;
    11. 分枝结点:度不为0的结点(非终端结点);
    12. 森林:互不相交的树集合;
    13. 有序树:子树有序的树,如:家族树;
    14. 无序树:不考虑子树的顺序;

    二叉树

    二叉树可以为空。二叉树结点的子树要区分左子树和右子树,即使只有一棵子树也要进行区分,说明它是左子树,还是右子树。这是二叉树与树的最主要的差别。注意区分:二叉树、二叉查找树/二叉排序树/二叉搜索树二叉平衡(查找)树

    二叉平衡树肯定是一颗二叉排序树。堆不是一颗二叉平衡树。

    二叉树与树是不同的,二叉树不等价于分支树最多为二的有序树。当一个结点只包含一个子节点时,对于有序树并无左右孩子之分,而对于二叉树来说依然有左右孩子之分,所以二叉树与树是两种不同的结构。

    性质:

    1. 在二叉树的第 i 层上至多有2i-1个结点。
    2. 深度为 k 的二叉树上至多含 2k-1 个结点(k≥1)
    3. 对任何一棵二叉树,若它含有n0个叶子结点、n2个度为 2 的结点,则必存在关系式:n0= n2+1。
    4. 具有 n 个结点的完全二叉树的深度为⎣log2 n⎦+1 。
    5. n个结点的二叉树中,完全二叉树具有最小的路径长度。
    6. 如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i(1<=i<=n),有:
      • 如果i=1,则结点i无双亲,是二叉树的根;如果i>1,则其双亲的编号是 i/2(整除)。
      • 如果2i>n,无左孩子;否则,其左孩子是结点2i。
      • 如果2i+1>n,则结点i无右孩子;否则,其右孩子是结点2i+1。

    二叉树的存储结构

    1. 顺序存储结构:仅仅适用于满或完全二叉树,结点之间的层次关系由性质5确定。
    2. 二叉链表法:每个节点存储左子树和右子树。三叉链表:左子树、右子树、父节点,总的指针是n+2
    3. 在有n个结点的二叉链表中,值为非空的链域的个数为n-1。在有N个结点的二叉链表中必定有2N个链域。除根结点外,其余N-1个结点都有一个父结点。所以,一共有N-1个非空链域,其余2N-(N-1)=N+1个为空链域。
    4. 二叉链存储法也叫孩子兄弟法,左指针指向左孩子,右指针指向右兄弟。而中序遍历的顺序是左孩子,根,右孩子。这种遍历顺序与存储结构不同,因此需要堆栈保存中间结果。而中序遍历检索二叉树时,由于其存储结构跟遍历顺序相符,因此不需要用堆栈。

    遍历二叉树和线索二叉树

    遍历二叉树:使得每一个结点均被访问一次,而且仅被访问一次。非递归的遍历实现要利用栈。

    • 先序遍历DLR:根节点->左子树->右子树
    • 中序遍历LDR:左子树->根节点->右子树。必须要有中序遍历才能得到一棵二叉树的正确顺序
    • 后续遍历LRD:左子树->右子树->根节点。需要栈的支持。
    • 层次遍历:用一维数组存储二叉树时,总是以层次遍历的顺序存储结点。层次遍历应该借助队列。

    线索二叉树:对二叉树所有结点做某种处理可在遍历过程中实现;检索(查找)二叉树某个结点,可通过遍历实现;如果能将二叉树线索化,就可以简化遍历算法,提高遍历速度,目的是加快查找结点的前驱或后继的速度。

    如何线索化?以中序遍历为例,若能将中序序列中每个结点前趋、后继信息保存起来,以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。对于二叉树的线索化,实质上就是遍历一次二叉树,只是在遍历的过程中,检查当前结点左,右指针域是否为空,若为空,将它们改为指向前驱结点或后继结点的线索。前驱就是在这一点之前走过的点,不是下一将要去往的点

    加上结点前趋后继信息(结索)的二叉树称为线索二叉树。n个结点的线索二叉树上每个结点有2个指针域(指向左孩子和右孩子),总共有2n个指针域;一个n个结点的树有n-1条边,那么空指针域= 2n - (n-1) = n + 1,即线索数为n+1。指针域tag为0,存放孩子指针,为1,存放前驱/后继节点指针。

    线索树下结点x的前驱与后继查找:设结点x相应的左(右)标志是线索标志,则lchild(rchild)就是前驱(后继),否则:

    • LDR–前驱:左子树中最靠右边的结点;后继:右子树中最靠左边的结点
    • LRD–前驱:右子树的根,若无右子树,为左子树跟。后继:x是根,后继是空;x是双亲的右孩子、x是双亲的左孩子,但双亲无右孩子,双亲是后继;x是双亲的左孩子,双亲有右孩子,双亲右子树中最左的叶子是后继
    • DLR–对称于LRD线索树—将LRD中所有左右互换,前驱与后继互换,得到DLR的方法。
    • 为简化线索链表的遍历算法,仿照线性链表,为线索链表加上一头结点,约定:
      • 头结点的lchild域:存放线索链表的根结点指针;
      • 头结点的rchild域: 中序序列最后一个结点的指针;
      • 中序序列第一结点lchild域指向头结点;
      • 中序序列最后一个结点的rchild域指向头结点;

    中序遍历的线索二叉树以及线索二叉树链表示意图
    xiansuobinarytree

    一棵左右子树均不空的二叉树在前序线索化后,其中空的链域的个数是1。前序和后续线索化后空链域个数都是1,中序是2。二叉树在线索化后,仍不能有效求解的问题是前序求前序先驱,后序求后序后继。

    中序遍历的顺序为:左、根、右,所以对于每一非空的线索,左子树结点的后继为根结点,右子树结点的前驱为根结点,再递归的执行上面的过程,可得非空线索均指向其祖先结点。在中序线索二叉树中,每一非空的线索均指向其祖先结点

    在二叉树上加上结点前趋、后继线索后,可利用线索对二叉树进行遍历,此时,不需栈,也不需递归。基本步骤:

    1. p=T->lchild; p指向线索链表的根结点;
    2. 若线索链表非空,循环:
      • 循环,顺着p左孩子指针找到最左下结点;访问之;
      • 若p所指结点的右孩子域为线索,p的右孩子结点即为后继结点循环: p=p->rchild; 并访问p所指结点;(在此循环中,顺着后继线索访问二叉树中的结点)
      • 一旦线索“中断”,p所指结点的右孩子域为右孩子指针,p=p->rchild,使 p指向右孩子结点;

    树和森林

    树的存储结构:

    1. 双亲表示法
    2. 孩子表示法
    3. 利用图表示树
    4. 孩子兄弟表示法(二叉树表示法):链表中每个结点的两指针域分别指向其第一个孩子结点和下一个兄弟结点

    将树转化成二叉树:右子树一定为空

    1. 加线:在兄弟之间加一连线
    2. 抹线:对每个结点,除了其左孩子外,去除其与其余孩子之间的关系
    3. 旋转:以树的根结点为轴心,将整树顺时针转45°

    森林转换成二叉树:

    1. 将各棵树分别转换成二叉树
    2. 将每棵树的根结点用线相连
    3. 以第一棵树根结点为二叉树的根

    树与转换后的二叉树的关系:转换后的二叉树的先序对应树的先序遍历;转换后的二叉树的中序对应树的后序遍历

    哈弗曼树/霍夫曼树

    一些概念

    1. 路径:从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径;
    2. 路径长度:路径上的分支数目称为路径长度;
    3. 树的路径长度:从根到每个结点的路径长度之和。
    4. 结点的权:根据应用的需要可以给树的结点赋权值;
    5. 结点的带权路径长度:从根到该结点的路径长度与该结点权的乘积;
    6. 树的带权路径长度=树中所有叶子结点的带权路径之和;通常记作 WPL=∑wi×li
    7. 哈夫曼树:假设有n个权值(w1, w2, … , wn),构造有n个叶子结点的二叉树,每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。

    前缀码的定义:在一个字符集中,任何一个字符的编码都不是另一个字符编码的前缀。霍夫曼编码就是前缀码,可用于快速判断霍夫曼编码是否正确。霍夫曼树是满二叉树,若有n个节点,则共有(n+1)/2个码子

    给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为霍夫曼树(Huffman Tree)。霍夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    假设哈夫曼树是二叉的话,则度为0的结点个数为N,度为2的结点个数为N-1,则结点总数为2N-1。哈夫曼树的结点个数必为奇数。

    哈夫曼树不一定是完全二叉树,但一定是最优二叉树。

    若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为[(n-1)/(m-1)]。边的数目等于度。

    图遍历与回溯

    图搜索->形成搜索树

    1. 穷举法。
    2. 贪心法。多步决策,每步选择使得构成一个问题的可能解,同时满足目标函数。
    3. 回溯法。根据题意,选取度量标准,然后将可能的选择方法按度量标准所要求顺序排好,每次处理一个量,得到该意义下的最优解的分解处理。

    无向图

    1. 回路或环:第一个顶点和最后一个顶点相同的路径。
    2. 简单回路或简单环:除第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路
    3. 连通:顶点v至v’ 之间有路径存在
    4. 连通图:无向图图 G 的任意两点之间都是连通的,则称G是连通图。
    5. 连通分量:极大连通子图,子图中包含的顶点个数极大
    6. 所有顶点度的和必须为偶数

    有向图:

    1. 回路或环:第一个顶点和最后一个顶点相同的路径。
    2. 简单回路或简单环:除第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路。
    3. 连通:顶点v至v’之间有路径存在
    4. 强连通图:有向图G的任意两点之间都是连通的,则称G是强连通图。各个顶点间均可达。
    5. 强连通分量:极大连通子图
    6. 有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度

    7. 生成树:极小连通子图。包含图的所有n个结点,但只含图的n-1条边。在生成树中添加一条边之后,必定会形成回路或环。

    8. 完全图:有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。
    9. 有向完全图:有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。
    10. 一个无向图 G=(V,E) 是连通的,那么边的数目大于等于顶点的数目减一:|E|>=|V|-1,而反之不成立。如果 G=(V,E) 是有向图,那么它是强连通图的必要条件是边的数目大于等于顶点的数目:|E|>=|V|,而反之不成立。没有回路的无向图是连通的当且仅当它是树,即等价于:|E|=|V|-1。

    图的存储形式

    1. 邻接矩阵和加权邻接矩阵
      • 无权有向图:出度: i行之和;入度: j列之和。
      • 无权无向图:i结点的度: i行或i列之和。
      • 加权邻接矩阵:相连为w,不相连为∞
    2. 邻接表
      • 用顶点数组表、边(弧)表表示该有向图或无向图
      • 顶点数组表:用数组存放所有的顶点。数组大小为图顶点数n
      • 边表(边结点表):每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表。
      • n个顶点的无向图的邻接表最多有n(n-1)个边表结点。有n个顶点的无向图最多有n*(n-1)/2条边,此时为完全无向图,而在邻接表中每条边存储两次,所以有n*(n-1)个结点

    图的遍历

    深度优先搜索利用栈,广度优先搜索利用队列

    求一条从顶点i到顶点s的简单路径–深搜。求两个顶点之间的一条长度最短的路径–广搜。当各边上的权值均相等时,BFS算法可用来解决单源最短路径问题。

    生成树和最小生成树

    每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分,将遍历经过的边同图的顶点构成一个子图,该子图称为生成树。因此有DFS生成树和BFS生成树。

    生成树是连通图的极小子图,有n个顶点的连通图的生成树必定有n-1条边,在生成树中任意增加一条边,必定产生回路。若砍去它的一条边,就会把生成树变成非连通子图

    最小生成树:生成树中边的权值(代价)之和最小的树。最小生成树问题是构造连通网的最小代价生成树。

    Kruskal算法:令最小生成树集合T初始状态为空,在有n个顶点的图中选取代价最小的边并从图中删去。若该边加到T中有回路则丢弃,否则留在T中;依此类推,直至T中有n-1条边为止。

    Prim算法、Kruskal算法和Dijkstra算法均属于贪心算法。

    1. Dijkstra算法解决的是带权重的有向图上单源最短路径问题,该算法要求所有边的权重都为非负值。
    2. Dijkstra算法解决了从某个原点到其余各顶点的最短路径问题,由循环嵌套可知该算法的时间复杂度为O(N*N)。若要求任一顶点到其余所有顶点的最短路径,一个比较简单的方法是对每个顶点当做源点运行一次该算法,等于在原有算法的基础上,再来一次循环,此时整个算法的复杂度就变成了O(N*N*N)。
    3. Bellman-Ford算法解决的是一般情况下的单源最短路径问题,在这里,边的权重可以为负值。该算法返回一个布尔值,以表明是否存在一个从源节点可以到达的权重为负值的环路。如果存在这样一个环路,算法将告诉我们不存在解决方案。如果没有这种环路存在,算法将给出最短路径和它们的权重。

    双连通图和关节点

    若从一个连通图中删去任何一个顶点及其相关联的边,它仍为一个连通图的话,则该连通图被称为重(双)连通图

    若连通图中的某个顶点和其相关联的边被删去之后,该连通图被分割成两个或两个以上的连通分量,则称此顶点为关节点

    没有关节点的连通图为双连通图

    1. 若生成树的根结点,有两个或两个以上的分支,则此顶点(生成树的根)必为关节点;
    2. 对生成树上的任意一个非叶“顶点”,若其某棵子树中的所有“顶点”没有和其祖先相通的回边,则该“顶点”必为关节点。

    有向无环图及其应用

    拓扑排序。在用邻接表表示图时,对有n个顶点和e条弧的有向图而言时间复杂度为O(n+e)。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。拓扑序列唯一不能唯一确定有向图。

    AOV网(Activity On Vertex):用顶点表示活动,边表示活动的优先关系的有向图称为AOV网。AOV网中不允许有回路,这意味着某项活动以自己为先决条件。

    拓扑有序序列:把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若vi是vj前驱,则vi一定在vj之前;对于没有优先关系的点,顺序任意。

    拓扑排序:对AOV网络中顶点构造拓扑有序序列的过程。方法:

    1. 在有向图中选一个没有前驱的顶点且输出之
    2. 从图中删除该顶点和所有以它为尾的弧
    3. 重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止(此时说明图中有环)

    采用深度优先搜索拓扑排序算法可以判断出一个有向图中是否有环(回路).深度优先搜索只要在其中记录下搜索的节点数n,当n大于图中节点数时退出,并可以得出有回路。若有回路,则拓扑排序访问不到图中所有的节点,所以也可以得出回路。广度优先搜索过程中如果访问到一个已经访问过的节点,可能是多个节点指向这个节点,不一定是存在环。

    算法描述:

    1. 把邻接表中入度为0的顶点依此进栈
    2. 若栈不空,则
      • 栈顶元素vj退栈并输出;
      • 在邻接表中查找vj的直接后继vk,把vk的入度减1;若vk的入度为0则进栈
    3. 若栈空时输出的顶点个数不是n,则有向图有环;否则,拓扑排序完毕。

    AOE网:带权的有向无环图,其中顶点表示事件,弧表示活动,权表示活动持续时间。在工程上常用来表示工程进度计划。

    一些定义:

    1. 事件的最早发生时间(ve(j)):从源点到j结点的最长的路径。意味着事件最早能够发生的时间。
    2. 事件的最迟发生时间(vl(j)):不影响工程的如期完工,事件j必须发生的时间。
    3. 活动ai由弧

    查找

    顺序查找、折半查找、索引查找、分块查找是静态查找,动态查找有二叉排序树查找,最优二叉树查找,键树查找,哈希表查找

    静态查找表

    顺序表的顺序查找:应用范围:顺序表或线性链表表示的表,表内元素之间无序。查找过程:从表的一端开始逐个进行记录的关键字和给定值的比较。

    顺序有序表的二分查找。平均查找时间(n+1)/n log2(n+1)

    分块查找:将表分成几块,块内无序,块间有序,即前一块中的最大值小于后一块中的最小值。并且有一张索引表,每一项存放每一块的最大值和指向该块第一个元素的指针。索引表有序,块内无序。所以,块间查找用二分查找,块内用顺序查找,效率介于顺序和二分之间;先确定待查记录所在块,再在块内查找。因此跟表中元素个数和块中元素个数都有关。

    1. 用数组存放待查记录,
    2. 建立索引表,由每块中最大(小)的关键字及所属块位置的信息组成。
    3. 当索引表较大时,可以采用二分查找
    4. 在数据量极大时,索引可能很多,可考虑建立索引表的索引,即二级索引,原则上索引不超过三级

    分块查找平均查找长度:ASLbs = Lb + Lw。其中,Lb是查找索引表确定所在块的平均查找长度, Lw是在块中查找元素的平均查找长度。在n一定时,可以通过选择s使ASL尽可能小。当s=sqrt(n)时,ASL最小。

    1. 时间:顺序查找最差,二分最好,分块介于两者之间
    2. 空间:分块最大,需要增加索引数据的空间
    3. 顺序查找对表没有特殊要求
    4. 分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块;另外,增加了索引的维护。
    5. 二分查找要求表有序,所以若表的元素的插入与删除很频繁,维持表有序的工作量极大。
    6. 在表不大时,一般直接使用顺序查找。

    动态查找

    二叉排序树的结点删除:

    1. x为叶子结点,则直接删除
    2. x只有左子树xL或只有右子树xR ,则令xL或xR直接成为双亲结点f的子树;
    3. x即有左子树xL也有右子树xR,在xL中选值最大的代替x,该数据按二叉排序树的性质应在最右边。

    平衡二叉树:每个结点的平衡因子都为 1、-1、0 的二叉排序树。或者说每个结点的左右子树的高度最多差1的二叉排序树。

    平衡二叉树的平衡:

    1. 左调整(新结点插入在左子树上的调整):
      • LL(插入在结点左子树的左子树上):旋转前后高度都为h+1
      • LR(新插入结点在左子树的右子树上):旋转前后高度仍为h+1
    2. 右调整(新结点插入在右子树上进行的调整):
      • RR(插入在的右子树的右子树上):处理方法和 LL对称
      • RL(插入在的右子树的左子树上):处理方法和 LR对称

    平衡树建立方法:

    1. 按二叉排序树插入结点
    2. 如引起结点平衡因子变为|2|,则确定旋转点,该点是离根最远(或最接近于叶子的点)
    3. 确定平衡类型后进行平衡处理,平衡后以平衡点为根的子树高不变
    4. 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列,可以参考Fibonacci数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。

    常见的平衡二叉树:

    1. 红黑树是平衡二叉树,也就是左右子树是平衡的,高度大概相等。这种情况等价于一块完全二叉树的高度,查找的时间复杂度是树的高度,为logn,插入操作的平均时间复杂度为O(logn),最坏时间复杂度为O(logn)
      红黑树
      • 节点是红色或黑色。
      • 根是黑色。
      • 所有叶子都是黑色(叶子是NIL节点)。
      • 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
      • 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。
    2. avl树也是自平衡二叉树;红黑树和AVL树查找、插入、删除的时间复杂度相同;包含n个内部结点的红黑树的高度是o(logn); TreeMap 是一个红黑树的实现,能保证插入的值保证排序
    3. STL和linux多使用红黑树作为平衡树的实现:
      1. 如果插入一个node引起了树的不平衡,AVL和RB-Tree都是最多只需要2次旋转操作,即两者都是O(1);但是在删除node引起树的不平衡时,最坏情况下,AVL需要维护从被删node到root这条路径上所有node的平衡性,因此需要旋转的量级O(logN),而RB-Tree最多只需3次旋转,只需要O(1)的复杂度。
      2. 其次,AVL的结构相较RB-Tree来说更为平衡,在插入和删除node更容易引起Tree的unbalance,因此在大量数据需要插入或者删除时,AVL需要rebalance的频率会更高。因此,RB-Tree在需要大量插入和删除node的场景下,效率更高。自然,由于AVL高度平衡,因此AVL的search效率更高。
      3. map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说,RB-tree的统计性能是高于AVL的。

    查找总结

    1. 既希望较快的查找又便于线性表动态变化的查找方法是哈希法查找。二叉排序树查找,最优二叉树查找,键树查找,哈希法查找是动态查找。分块、顺序、折半、索引顺序查找均为静态。分块法应该是将整个线性表分成若干块进行保存,若动态变化则可以添加在表的尾部(非顺序结构),时间复杂度是O(1),查找复杂度为O(n);若每个表内部为顺序结构,则可用二分法将查找时间复杂度降至O(logn),但同时动态变化复杂度则变成O(n);顺序法是挨个查找,这种方法最容易实现,不过查找时间复杂度都是O(n),动态变化时可将保存值放入线性表尾部,则时间复杂度为O(1);二分法是基于顺序表的一种查找方式,时间复杂度为O(logn);通过哈希函数将值转化成存放该值的目标地址,O(1)
    2. 二叉树的平均查找长度为O(log2n)——O(n).二叉排序树的查找效率与二叉树的高度有关,高度越低,查找效率越高。二叉树的查找成功的平均查找长度ASL不超过二叉树的高度。二叉树的高度与二叉树的形态有关,n个节点的完全二叉树高度最小,高度为[log2n]+1,n个节点的单只二叉树的高度最大,高度为n,此时查找成功的ASL为最大(n+1)/2,因此二叉树的高度范围为[log2n]+1——n.
    3. 链式存储不能随机访问,必须是顺序存储

    B_树的B+树

    B_树

    B-树就是B树。m阶B_树满足或空,或为满足下列性质的m叉树:

    B-树

    1. 树中每个结点最多有m棵子树
    2. 根结点在不是叶子时,至少有两棵子树
    3. 除根外,所有非终端结点至少有⎡m/2⎤棵子树
    4. 有s个子树的非叶结点具有 n = s-1个关键字,结点的信息组织为:(n,A0,K1,A1,K2,A2 … Kn,An)。这里:n为关键字的个数,ki(i=1,2,…,n)为关键字,且满足Ki小于Ki+1,,Ai(i=0,1,..n)为指向子树的指针。
    5. 所有的叶子结点都出现在同一层上,不带信息(可认为外部结点或失败结点)。
    6. 关键字集合分布在整颗树中
    7. 任何一个关键字出现且只出现在一个结点中
    8. 搜索有可能在非叶子结点结束
    9. 其搜索性能等价于在关键字全集内做一次二分查找
    10. 只适用于随机检索,不适用于顺序检索。
    11. 有结点的平衡因子都为零
    12. M阶B-树中含有N个关键字,最大深度为log⎡m/2⎤(n+1)/2+2

    B_树中结点的插入

    1. m代表B_树的阶,插入总发生在最低层
    2. 插入后关键字个数小于等于 m-1,完成。
    3. 插入后关键字个数等于m,结点分裂,以中点数据为界一分为二,中点数据放到双亲结点中。这样就有可能使得双亲结点的数据个数为m,引起双亲结点的分裂,最坏情况下一直波及到根,引起根的分裂——B_树长高。

    3阶B_树的插入。每个结点最多3棵子树,2个数据;最少2棵子树,1个数据。所以3阶B_树也称为2-3树。

    B_树中结点的删除

    1. 删除发生在最底层
      • 被删关键字所在结点中的关键字数目大于等于 m/2 ,直接删除。
      • 删除后结点中数据为⎡m/2⎤-2,而相邻的左(右)兄弟中数据大于⎡m/2⎤-1,此时左(右兄弟)中最大(小)的数据上移到双亲中,双亲中接(靠)在它后(前)面的数据移到被删数据的结点中
      • 其左右兄弟结点中数据都是⎡m/2⎤-1,此时和左(右)兄弟合并,合并时连同双亲中相关的关键字。此时,双亲中少了一项,因此又可能引起双亲的合并,最坏一直到根,使B-树降低一层。
    2. 删除不在最底层
      • 在大于被删数据中选最小的代替被删数据,问题转换成在最底层的删除

    B+树

    在实际的文件系统中,用的是B+树或其变形。有关性质与操作类似与B_树。

    B+树

    差异:

    1. 有n棵子树的结点中有n个关键字,每个关键字不保存数据,只用来索引,所有数据都保存在叶子节点。
    2. 所有叶子结点中包含全部关键字信息,及对应记录位置信息及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)
    3. 所有非叶子为索引,结点中仅含有其子树根结点中最大(或最小)关键字。 (而B树的非终节点也包含需要查找的有效信息)
    4. 非叶最底层顺序联结,这样可以进行顺序查找

    B+特性

    1. 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
    2. 不可能在非叶子结点命中
    3. 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层
    4. 更适合文件索引系统
    5. B+树插入操作的平均时间复杂度为O(logn),最坏时间复杂度为O(logn)

    查找过程

    • 在 B+ 树上,既可以进行缩小范围的查找,也可以进行顺序查找;
    • 在进行缩小范围的查找时,不管成功与否,都必须查到叶子结点才能结束;
    • 若在结点内查找时,给定值≤Ki, 则应继续在 Ai 所指子树中进行查找

    插入和删除的操作:类似于B_树进行,即必要时,也需要进行结点的“分裂”或“合并”。

    为什么说B+tree比B树更适合实际应用中操作系统的文件索引和数据库索引?

    1. B+tree的磁盘读写代价更低
      • B+tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
      • 举个例子,假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候,B树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
    2. B+tree的查询效率更加稳定
      • 由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

    B树和B+树都是平衡的多叉树。B树和B+树都可用于文件的索引结构。B树和B+树都能有效的支持随机检索。B+树既能索引查找也能顺序查找.

    哈希表

    1. 在记录的存储地址和它的关键字之间建立一个确定的对应关系;这样不经过比较,一次存取就能得到元素。
    2. 哈希函数——在记录的关键字与记录的存储位置之间建立的一种对应关系。是从关键字空间到存储位置空间的一种映象。
    3. 哈希表——应用哈希函数,由记录的关键字确定记录在表中的位置信息,并将记录根据此信息放入表中,这样构成的表叫哈希表。
    4. Hash查找适合于关键字可能出现的值的集合远远大于实际关键字集合的情形。
    5. 更适合查找,不适合频繁更新
    6. Hash表等查找复杂依赖于Hash值算法的有效性,在最好的情况下,hash表查找复杂度为O(1)。只有无冲突的hash_table复杂度才是O(1)。一般是O(c),c为哈希关键字冲突时查找的平均长度。插入,删除,查找都是O(1)。平均查找长度不随表中结点数目的增加而增加,而是随负载因子的增大而增大
    7. 由于冲突的产生,使得哈希表的查找过程仍然是一个给定值与关键字比较的过程。

    根据抽屉原理,冲突是不可能完全避免的,所以,选择好的散列函数和冲突处理方法:

    1. 构造一个性能好,冲突少的Hash函数
    2. 如何解决冲突

    常用的哈希函数

    1. 直接定址法。仅适合于:地址集合的大小 == 关键字集合的大小
    2. 数字分析法。对关键字进行分析,取关键字的若干位或其组合作哈希地址。仅适合于:能预先估计出全体关键字的每一位上各种数字出现的频度。
    3. 平方取中法。以关键字的平方值的中间几位作为存储地址。
    4. 折叠法。将关键字分割成位数相同的几部分,然后取这几部分的叠加和(舍去进位)做哈希地址。移位叠加/间界叠加。适合于: 关键字的数字位数特别多,且每一位上数字分布大致均匀情况。
    5. 除留余数法。取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址,即H(key)=key%p,p<=m。
    6. 随机数法。取关键字的伪随机函数值作哈希地址,即H(key)=random(key),适于关键字长度不等的情况。

    冲突解决

    1. 开放定址法。当冲突发生时,形成一个探查序列;沿此序列逐个地址探查,直到找到一个空位置(开放的地址),将发生冲突的记录放到该地址中。即Hi=(H(key)+di) % m,i=1,2,……k(k<=m-1),H(key)哈希函数,m哈希表长,di增量序列。缺点:删除:只能作标记,不能真正删除;溢出;载因子过大、解决冲突的算法选择不好会发生聚集问题。要求装填因子α较小,故当结点规模较大时会浪费很多空间。
      • 线性探测再散列:di=1,2,3,…,m-1
      • 二次探测再散列:di=12,-12,22,-22,…,±k2(k<=m/2)
      • 伪随机探测再散列: di为伪随机数序列
    2. 链地址法:将所有关键字为同义词的记录存储在一个单链表中,并用一维数组存放头指针。拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间。一旦发生冲突,在当前位置给单链表增加结点就行。
    3. 其他方法:再哈希法、建立公共溢出区
    4. 在用拉链法构造的散列表中,删除结点的操作易于实现。拉链法的缺点是:指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间。由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况。拉链法解决冲突时,需要使用指针,指示下一个元素的存储位置
    5. 开哈希表–链式地址法;闭哈希表–开放地址法.开哈希和闭哈希主要的区别在于,随着哈希表的密集度提高,使用闭哈希时,不仅会与相同哈希值的元素发生冲突,还容易与不同哈希值的元素发生冲突;而开哈希则不受哈希表疏密与否的影响,始终只会与相同哈希值的元素冲突而已。所以在密集度变大的哈希表中查找时,显然开哈希的平均搜索长度不会增长。
    6. 设有n个关键字具有相同的Hash函数值,则用线性探测法把这n个关键字映射到Hash表中需要做n*(n-1)/2次线性探测。如果使用二次探测再散列法将这n个关键字存入哈希表,至少要进行n*(n+1)/2次探测

    Hash查找效率:装填因子=表中记录数/表容量

    有B+Tree/Hash_Map/STL Map三种数据结构。对于内存中数据,查找性能较好的数据结构是Hash_Map,对于磁盘中数据,查找性能较好的数据结构是B+Tree。Hash操作能根据散列值直接定位数据的存储地址,设计良好的hash表能在常数级时间下找到需要的数据,但是更适合于内存中的查找。B+树是一种是一种树状的数据结构,适合做索引,对磁盘数据来说,索引查找是比较高效的。STL_Map的内部实现是一颗红黑树,但是只是一颗在内存中建立二叉树树,不能用于磁盘操作,而其内存查找性能也比不上Hash查找。

    内部排序

    1. 内部排序:全部数据可同时放入内存进行的排序。
    2. 外部排序:文件中数据太多,无法全部调入内存进行的排序。

    插入类:

    1. 直接插入排序。最坏情况是数据递减序,数据比较和移动量最大,达到O(n2),最好是数据是递增序,比较和移动最少为O(n)。趟数是固定的n-1,即使有序,也要依次从第二个元素开始。排序趟数不等于时间复杂度。
    2. 折半插入排序 。由于插入第i个元素到r[1]到r[i-1]之间时,前i个数据是有序的,所以可以用折半查找确定插入位置,然后插入。
    3. 希尔排序。缩小增量排序。5-3-1。在实际应用中,步长的选取可简化为开始为表长n的一半(n/2),以后每次减半,最后为1。插入的改进,最后一趟已基本有序,比较次数和移动次数相比直接插入最后一趟更少

    交换类:

    1. 冒泡排序。O(n2)通常认为冒泡是比较差的,可以加些改进,比如在一趟中无数据的交换,则结束等措施。
      • 在数据已基本有序时,冒泡是一个较好的方法
      • 在数据量较少时(15个左右)可以用冒泡
    2. 快速排序。
      • 时间复杂度。最好情况:每次支点总在中间,O(nlog2n),平均O(nlog2n)。最坏,数据已是递增或递减,O(n2)。pivotkey的选择越靠近中央,即左右两个子序列长度越接近,排序速度越快。越无序越快。
      • 空间复杂度。需栈空间以实现递归,最坏情况:S(n)=O(n);一般情况:S(n)=O(log2n)
      • 在序列已是有序的情况下,时间复杂度最高。原因:支点选择不当。改进:随机选取支点或最左、最右、中间三个元素中的值处于中间的作为支点,通常可以避免最坏情况。所以,快速排序在表已基本有序的情况下不合适。
      • 在序列长度已较短时,采用直接插入排序、起泡排序等排序方法。序列的个数通常取10左右。

    选择类排序:

    1. 简单选择排序。O(n2)。总比较次数n(n-1)/2。
    2. 堆排序。建堆 O(n),筛选排序O(nlogn)。找出若干个数中最大/最小的前K个数,用堆排序是最好。小根堆中最大的数一定是放在叶子节点上,堆本身是个完全二叉树,完全二叉树的叶子节点的位置大于[n/2]。时间复杂度不会因为待排序序列的有序程度而改变,但是待排序序列的有序程度会影响比较次数。
    3. 归并排序。时间:与表长成正比,若一个表表长是m,另一个是n,则时间是O(m+n)。单独一个数组归并,时间:O(nlogn),空间:O(n),比较次数介于(nlogn)/2和(nlogn)-n+1,赋值操作的次数是(2nlogn)。归并排序算法比较占用内存,但却是效率高且稳定的排序算法。在外排序中使用。归并的趟数是logn。
    4. 基数排序。在一般情况下,每个结点有 d 位关键字,必须执行 t = d次分配和收集操作。分配的代价:O(n);收集的代价:O(rd) (rd是基数);总的代价为:O( d ×(n + rd))。适用于以数字和字符串为关键字的情况。
    5. 枚举排序,通常也被叫做秩排序,比较计数排序。对每一个要排序的元素,统计小于它的所有元素的个数,从而得到该元素在整个序列中的位置,时间复杂度为O(n2)

    比较法分类的下界:O(nlogn)

    排序算法的一些特点:

    1. 堆排序、冒泡排序、快速排序在每趟排序过程中,都会有一个元素被放置在其最终的位置上。
    2. 有字符序列 {Q,H,C,Y,P,A,M,S,R,D,F,X} ,新序列{F,H,C,D,P,A,M,Q,R,S,Y,X},是快速排序算法一趟扫描的结果。(拿Q作为分割点,快速排序一轮。二路归并,第一趟排序,得到 n / 2 个长度为 2 的各自有序的子序列,第二趟排序,得到 n / 4 个长度为 4 的各自有序的子序列H Q C Y A P M S D R F X。如果是快速排序的话,第一个元素t将会被放到一个最准确的位置,t前的数均小于t,后面的数均大于t。希尔排序每个小分组内将会是有序的。堆排序,把它构成一颗二叉树的时候,该堆要么就是大根堆,要么就是小根堆,第一趟Y排在最后;冒泡,那么肯定会有数据下沉的动作,第一趟有A在第一位。)
    3. 在文件”局部有序”或文件长度较小的情况下,最佳内部排序的方法是直接插入排序。(归并排序要求待排序列已经部分有序,而部分有序的含义是待排序列由若干有序的子序列组成,即每个子序列必须有序,并且其时间复杂度为O(nlog2n);直接插入排序在待排序列基本有序时,每趟的比较次数大为降低,即n-1趟比较的时间复杂度由O(n^2)降至O(n)。在待排序的元素序列基本有序或者每个元素距其最终位置不远也可用插入排序,效率最高的排序方法是插入排序
    4. 排序趟数与序列的原始状态有关的排序方法是优化冒泡和快速排序法。(插入排序和选择排序不管序列的原始状态是什么都要执行n-1趟,优化冒泡和快排不一定。仔细理解排序的次数比较次数的区别)
    5. 不稳定的排序方法:快排,堆排,希尔,选择
    6. 要与关键字的初始排列次序无关,那么就是最好、最坏、一般的情况下排序时间复杂度不变, 总共有堆排序,归并排序,选择排序,基数排序
    7. 快速排序、Shell 排序、归并排序、直接插入排序的关键码比较次数与记录的初始排列有关。折半插入排序、选择排序无关。(直接插入排序在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置;折半插入排序,比较次数是固定的,与初始排序无关;快速排序,初始排序不影响每次划分时的比较次数,都要比较n次,但是初始排序会影响划分次数,所以会影响总的比较次数,但快排平均比较次数最小;归并排序在归并的时候,如果右路最小值比左路最大值还大,那么只需要比较n次,如果右路每个元素分别比左路对应位置的元素大,那么需要比较2*n-1次,所以与初始排序有关)
    8. 精俭排序,即一对数字不进行两次和两次以上的比较,插入和归并是“精俭排序”。插入排序,前面是有序的,后面的每一个元素与前面有序的元素比较,比较过的就是有序的了,不会再比较一次。归并每次合并后,内部都是有序的,内部的元素之间不用再比较。选择排序,每次在后面的元素中找到最小的,找最小元素的过程是在没有排好序的那部分进行,所有肯定会比较多次。堆排序也需比较多次。

    外部排序

    1. 生成合并段(run):读入文件的部分记录到内存->在内存中进行内部排序->将排好序的这些记录写入外存,形成合并段->再读入该文件的下面的记录,往复进行,直至文件中的记录全部形成合并段为止。
    2. 外部合并:将上一阶段生成的合并段调入内存,进行合并,直至最后形成一个有序的文件。
    3. 外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装入内存的部分,分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行多路归并排序
    4. 不管初始序列是否有序, 冒泡、选择排序时间复杂度是O(n^2),归并、堆排序时间复杂度是O(nlogn)
    5. 外部排序的总时间 = 内部排序(产出初始归并段)所需时间 + 外存信息读取时间 + 内部归并所需的时间
    6. 外排中使用置换选择排序的目的,是为了增加初始归并段的长度。减少外存读写次数需要减小归并趟数

    7. 根据内存容量设若干个输入缓冲区和一个输出缓冲区。若采用二路归并,用两个输入缓冲。

    8. 归并的方法类似于归并排序的归并算法。增加的是对缓冲的监视,对于输入,一旦缓冲空,要到相应文件读后续数据,对于输出缓冲,一旦缓冲满,要将缓冲内容写到文件中去。
    9. 外排序和内排序不只是考虑内外排序算法的性能,还要考虑IO数据交换效率的问题,内存存取速度远远高于外存。影响外排序的时间因素主要是内存与外设交换信息的总次数

    有效的算法设计

    1. 贪心法。Dijkstra的最短路径(时间复杂度O(n2));Prim求最小生成树邻接表存储时是O(n+e),图O(n2);关键路径及关键活动的求法。
    2. 回溯法
    3. 分支限界法
    4. 分治法。分割、求解、合并。二分查找、归并排序、快速排序。
    5. 动态规划。Floyd-Warshall算法求解图中所有点对之间最短路径时间复杂度为O(n3)

    动态规划解题的方法是一种高效率的方法,其时间复杂度通常为O(n2),O(n3)等,可以解决相当大的信息量。(数塔在n<=100层时,可以在很短的时间内得到问题解)

    • 适用的原则:原则为优化原则,即整体优化可以分解为若干个局部优化。
    • 动态规划比穷举法具有较少的计算次数
    • 递归算法需要很大的栈空间,而动态规划不需要栈空间

    贪心和动态规划的差别:

    1. 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。
    2. 在动态规划算法中,每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后,才能作出选择。而在贪心算法中,仅在当前状态下作出最好选择,即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。
    3. 贪心算法所作的贪心选择可以依赖于以往所作过的选择,但决不依赖于将来所作的选择,也不依赖于子问题的解。正是由于这种差别,动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为一个规模更小的子问题。

    P问题

    1. P问题,如果它可以通过运行多项式次(即运行时间至多是输入量大小的多项式函数的一种算法获得解决),可以找到一个能在多项式的时间里解决它的算法。—-确定性问题
    2. NP问题,虽然可以用计算机求解,但是对于任意常数k,它们不能在O(nk)时间内得到解答,可以在多项式的时间里验证一个解的问题。所有的P类问题都是NP问题。
    3. NP完全问题,知道有效的非确定性算法,但是不知道是否存在有效的确定性算法,同时,不能证明这些问题中的任何一个不存在有效的确定性算法。这类问题称为NP完全问题。
    展开全文
  • 常用数据结构与常用算法,

    万次阅读 多人点赞 2018-08-08 20:32:54
    1. 常见数据结构 人们进行程序设计时通常关注个重要问题,一是如何将待处理的数据存储到计算机内存中,即数据表示;二是设计算法操作这些数据,即数据处理。数据表示的本质是数据结构设计,数据处理的本质是算法...
  • 数据结构与算法学习笔记

    万次阅读 多人点赞 2018-09-25 13:55:49
    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏。...最常用数据结构预算法: 数据结构:数组、链表、栈、队列、散列表、二叉树‘、堆、跳表、图、Tire树 算法: 递归...
  • 数据结构的分类

    千次阅读 2016-10-20 09:28:30
    数据的逻辑结构可分为两大类:一是线性结构,一是非线性结构。线性结构且仅一个开始结点和一个终端结点,并且所有的结点最多只能一个前驱和一个后继。线性表是典型的线性结构。非线性结构的一个结点可能...
  • java 中几种常用数据结构

    万次阅读 多人点赞 2016-07-11 09:11:27
    java中几种常用数据结构,主要分为Collection和map个主要接口(接口只提供方法,并不提供实现),而程序中最终使用的数据结构是继承自这些接口的数据结构类。其主要的关系(继承关系): (----详细参见java...
  • 常用数据结构--线性结构

    万次阅读 多人点赞 2012-04-27 00:20:14
    常见数据结构分类方式如下图: 常用的线性结构:线性表,栈,队列,循环队列,数组。线性表中包括顺序表、链表等,其中,栈和队列只是属于逻辑上的概念,实际中不存在,仅仅是一种思想,一种理念;线性表则...
  • 常见数据结构 单链表结构和顺序存储结构的区别 线性链表 数组和链表的区别 判断疫个链表是否环,如何找到这个环 单链表和双链表的区别 头指针和头结点的区别 简述KMP算法 栈和队列的区别 栈和队列的相同之处和...
  • 常见数据结构与算法整理总结(上)

    万次阅读 多人点赞 2018-08-06 18:23:14
    下面是自己整理的常用数据结构与算法相关内容,如错误,欢迎指出。 为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是...
  • 常用大数据结构总结及应用场景-附示例截图

    千次阅读 多人点赞 2020-08-03 21:32:42
    什么是数据结构? 官方解释:数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的学科。 大白话:数据结构就是把数据元素按照一定的关系组织起来的集合,用来组成和...
  • Java常用数据结构总结

    万次阅读 2017-02-16 17:04:25
    数据元素相互之间的关系称为结构四类基本结构:集合、线性结构、树形结构、图状结构; 集合结构:除了同属于一种类型外,别无其它关系 线性结构:元素之间存在一对一关系常见类型: 数组,链表,队列,栈,它们之间在...
  • 数据结构常用算法

    万次阅读 多人点赞 2015-10-02 14:04:00
    1. 常见数据结构 人们进行程序设计时通常关注个重要问题,一是如何将待处理的数据存储到计算机内存中,即数据表示;二是设计算法操作这些数据,即数据处理。数据表示的本质是数据结构设计,数据处理的本质是算法...
  • 数据结构排序算法系列】数据结构排序算法

    万次阅读 多人点赞 2016-03-25 22:36:40
    如Windows操作系统的文件管理中会自动对用户创建的文件按照一定的规则排序(这个规则用户可以自定义,默认按照文件名排序)因此熟练掌握各种排序算法是非常重要的,本博客将对数据结构常见的八排序算法进行详细...
  • 数据结构–七查找算法总结

    万次阅读 多人点赞 2018-08-06 17:13:43
    数据结构–七查找算法总结 2017年08月15日 21:06:17 阅读数:10610 ...
  • 常见存储数据结构

    千次阅读 2018-06-18 23:48:55
    常见存储数据结构 最近在看存储和数据库方面的书籍,遇到了多种数据结构,做个简单总结,任何理解问题也请大佬明示。╮( ̄▽ ̄)╭ B+树 B+tree常用于多种数据库存储引擎中,它是B tree(一种自平衡的树状...
  • 常见数据结构与算法整理总结

    千次阅读 多人点赞 2018-01-10 14:03:30
    下面是自己整理的常用数据结构与算法相关内容,如错误,欢迎指出。 为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是...
  • JAVA常用数据结构及原理分析(面试总结)

    万次阅读 多人点赞 2017-05-21 17:27:58
    最近准备面试,因此整理一份Java中常用的数据结构资料,方便面试; java.util包中三个重要的接口及特点:List(列表)、Set(保证集合中元素唯一)、Map(维护多个key-value键值对,保证key唯一)。其不同子类的...
  • 数据结构——栈的详解

    万次阅读 多人点赞 2020-04-20 00:02:43
    但从数据类型角度看,他们是和线性表不相同的两类重要的的抽象数据类型。 C语言和C++中的栈C语言中的栈栈的定义C语言中栈的基本操作栈的初始化判断是否为空栈判断是否为满栈入栈出栈C语言实现栈的具体代码C++中的...
  • Java 面试常用数据结构

    千次阅读 2016-11-19 16:02:09
    面试常用数据结构 面试时数据结构应该算是必问的内容, 今天准备了个更常问的数据结构,链表和二叉树的实现 链表 (线性链表) 我们知道线性表的顺序存储结构的特点是逻辑关系上相邻的个元素在物理位置上也相邻,...
  • 线性和非线性数据结构分类

    千次阅读 2017-03-01 15:29:15
    数据结构按逻辑和存储结构,可以分为不同的类型  按逻辑可以分为以下三种:  1.集合  2.线性结构 是一个有序的数据元素集合,除第一个元素和最后一个元素外,其他元素与元素之间是首尾相接的,所以称之为线性...
  • c#常用数据结构解析

    万次阅读 多人点赞 2015-01-19 09:27:37
    可能去过小匹夫博客的盆油们读过这篇对于数据结构的总结,但是小匹夫当时写那篇文章的时候略匆忙,所以今天进行了一些增改,重新发表在蛮牛。作为程序猿,对于常见数据结构的掌握是非常必要的,也许这篇文章略显...
  • 为什么要学数据结构

    万次阅读 多人点赞 2019-11-19 09:45:23
    一、前言 在可视化化程序设计的今天,借助于...1) 能够熟练地选择和设计各种数据结构和算法 2) 至少要能够熟练地掌握一门程序设计语言 3) 熟知所涉及的相关应用领域的知识 其中,后个条件比较容易实现,而第一个...
  • C++常用数据结构总结

    万次阅读 多人点赞 2018-10-07 19:50:29
    空间排列方式只有线性和链式种方式,链式是通过记录每一个数据的地址来实现查找下一位数据的。而每一个容器所具有的特性就决定了它所适用的情况,总的来看容器常用的无非是增删改查操作,下面将从适用场景、常用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 857,507
精华内容 343,002
关键字:

常见的数据结构有哪两大类

数据结构 订阅