当前位置: 首页 > news >正文

数据结构—笔记整理—初识数据结构

学习之路,长路漫漫,写学习笔记的过程就是把知识讲给自己听的过程。

目录


数据结构初定义

常用数据结构

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

①、数组

②、链表

③、栈

④、队列

⑤、树

⑥、堆

⑦、图

⑧、哈希表

数据结构

集合结构(非线性结构)

线性结构

数组

线性表

存储结构

模式匹配

二叉树

存储结构

顺序存储结构

二叉链表

哈夫曼编码

哈夫曼编码实现压缩,解压缩

数据元素是多对多的关系

存储结构

邻接矩阵

邻接表

十字链表

邻接多重表

边集数组

遍历

最小生成树

物理结构(存储结构)

顺序查找(线性查找)

折半查找(二分查找)

插值查找

斐波那契查找

线性索引查找

稠密索引

分块索引

二叉搜索树(又称二叉查找树/排序数)

平衡二叉搜索树(AVL树)

多路查找树(B树)

红黑树

散列表查找(哈希表)

内排序与外排序

冒泡排序

冒泡排序优化

简单选择排序

直接插入排序

希尔排序

堆排序

归并排序

快速排序

算法


数据结构初定义


        数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系,分为逻辑结构和存储结构。

常用数据结构


数组(Array)

是一种聚合数据类型,它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构,在各种编程语言中都有对应。一个数组可以分解为多个数组元素,按照数据元素的类型,数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。 

栈( Stack)

栈是一种特殊的线性表,它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照先进后出或后进先出的原则来存储数据,也就是说,先插入的数据将被压入栈底,最后插入的数据在栈顶,读出数据时,从栈顶开始逐个读出。栈在汇编语言程序中,经常用于重要数据的现场保护。栈中没有数据时,称为空栈。 

队列(Queue)

队列和栈类似,也是一种特殊的线性表。和栈不同的是,队列只允许在表的一端进行插入操作,而在另一端进行删除操作。一般来说,进行插入操作的一端称为队尾,进行删除操作的一端称为队头。队列中没有元素时,称为空队列。 

链表( Linked List)

链表是一种数据元素按照链式存储结构进行存储的数据结构,这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成,每个数据结点包括数据域和指针域两部分。其中,指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。 

树( Tree)

树是典型的非线性结构,它是包括,2个结点的有穷集合K。在树结构中,有且仅有一个根结点,该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点,而且可以有两个后继结点,m≥0。 

图(Graph)

图是另一种非线性数据结构。在图结构中,数据结点一般称为顶点,而边是顶点的有序偶对。如果两个顶点之间存在一条边,那么就表示这两个顶点具有相邻关系。  

堆(Heap)

堆是一种特殊的树形数据结构,一般讨论的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的,并且根结点的两个子树也是一个堆结构。 

散列表(Hash)

散列表源自于散列函数(Hash function),其思想是如果在结构中存在关键字和T相等的记录,那么必定在F(T)的存储位置可以找到该记录,这样就可以不用进行比较操作而直接取得所查记录。 [5] 

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


①、数组

优点:

按照索引查询元素的速度很快;按照索引遍历数组也很方便。

缺点:

数组的大小在创建后就确定了,无法扩容;数组只能存储一种类型的数据;添加、删除元素的操作很耗时间,因为要移动其他元素。

②、链表

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

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

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

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

单向链表的缺点是只能从头到尾依次遍历,而双向链表可进可退,既能找到下一个,也能找到上一个——每个节点上都需要多分配一个存储空间。

链表中的数据按照“链式”的结构存储,因此可以达到内存上非连续的效果,数组必须是一块连续的内存。

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

优点:

不需要初始化容量;可以添加任意元素;插入和删除的时候只需要更新引用。

缺点:

含有大量的引用,占用的内存空间大;查找元素需要遍历整个链表,耗时。

③、栈

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

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

④、队列

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

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

注意,栈是先进后出,队列是先进先出——两者虽然都是线性表,但原则是不同的,结构不一样嘛。

⑤、树

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

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

每个节点都只有有限个子节点或无子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点可以分为多个不相交的子树。下图展示了树的一些术语:

根节点是第 0 层,它的子节点是第 1 层,子节点的子节点为第 2 层,以此类推。

深度:对于任意节点 n,n 的深度为从根到 n 的唯一路径长,根的深度为 0。高度:对于任意节点 n,n 的高度为从 n 到一片树叶的最长路径长,所有树叶的高度为 0。树的种类有很多种,常见的有:

无序树:树中任意节点的子节点之间没有顺序关系。那怎么来理解无序树呢,到底长什么样子?假如有三个节点,一个是父节点,两个是同级的子节点,那么就有三种情况:

假如有三个节点,一个是父节点,两个是不同级的子节点,那么就有六种情况:

三个节点组成的无序树,合起来就是九种情况。

二叉树:每个节点最多含有两个子树。二叉树按照不同的表现形式又可以分为多种。完全二叉树:对于一颗二叉树,假设其深度为 d(d > 1)。除了第 d 层,其它各层的节点数目均已达最大值,且第 d 层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树。

拿上图来说,d 为 3,除了第 3 层,第 1 层、第 2 层 都达到了最大值(2 个子节点),并且第 3 层的所有节点从左向右联系地紧密排列(H、I、J、K、L),符合完全二叉树的要求。

满二叉树:一颗每一层的节点数都达到了最大值的二叉树。有两种表现形式,第一种,像下图这样(每一层都是满的),满足每一层的节点数都达到了最大值 2。

第二种,像下图这样(每一层虽然不满),但每一层的节点数仍然达到了最大值 2。

二叉查找树:英文名叫 Binary Search Tree,即 BST,需要满足以下条件:

任意节点的左子树不空,左子树上所有节点的值均小于它的根节点的值;任意节点的右子树不空,右子树上所有节点的值均大于它的根节点的值;任意节点的左、右子树也分别为二叉查找树。

基于二叉查找树的特点,它相比较于其他数据结构的优势就在于查找、插入的时间复杂度较低,为 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)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

B 树:一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多于两个的子树。数据库的索引技术里就用到了 B 树。

⑥、堆

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

堆中某个节点的值总是不大于或不小于其父节点的值;堆总是一棵完全二叉树。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

⑦、图

图是一种复杂的非线性结构,由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G 表示一个图,V 是图 G 中顶点的集合,E 是图 G 中边的集合。

上图共有 V0,V1,V2,V3 这 4 个顶点,4 个顶点之间共有 5 条边。

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

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

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

⑧、哈希表

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

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

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

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

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

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

数据结构


数据结构是相互之间存在一种或多种特定关系的数据元素的集合

逻辑结构(分为线性结构和非线性结构)

反映数据元素之间的逻辑关系的数据结构,是针对具体问题的,可以表示成一种或多种存储结构

集合结构(非线性结构)

集合通常是由一组无序的, 不能重复的元素构成 数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系

线性结构

线性结构是一个有序数据元素的集合,常用的线性结构有:线性表,栈,队列,双队列,数组,串。 非线性结构,其逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。常见的非线性结构有:二维数组,多维数组,广义表,树(二叉树等)。

线性结构是一个有序数据元素的集合

数组


线性表

0个或多个具有相同类型的数据元素的有限序列

存储结构

顺序存储结构

顺序存储结构,用一段地址连续的存储单元 一次存储线性表的数据元素。比如数组

每个数据元素存数据元素信息外(数据域),还要存储它的后继元素的存储地址(指针域)

优点:

  • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间

  • 可以快速的存取表中任意位置的元素,时间复杂度为O(1)

缺点:

  • 插入和删除操作需要移动大量元素

  • 当线性表变化较大时,难以确定存储空间的容量

  • 造成存储空间的"碎片"

链式存储结构

用一组任意的存储单元存储线性表的数据元素, 这组存储单元可以是连续的,也可以是不连续的

单链表

链表中每个结点可以包含若干个数据域和若干个指针域。 如果每个结点中只包含一个指针域,则称其为单链表

优点:

  • 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制

  • 插入和删除更快,时间复杂度为O(n),在给出某位置的指针后,复杂度仅为O(1)

缺点:

  • 查找效率比顺序存储结构差,时间复杂度为O(n)

静态链表

用数组描述的链表叫静态链表(用数组代替指针)

为了给没有指针的高级语言设计的视线单链表的方法,很少用(虽然java,c#也没有指针,但是引用类型相当于变样实现了指针)

优点: 插入和删除只需要修改游标,无需移动元素 从而改进了在顺序存储结构中的插入,删除移动大量元素的缺点

缺点: 没有解决连续存储分配带来的表长难以确认的问题 失去了顺序存储结构随机存取的特性

循环链表

将单链表中终端结点的指针段由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表就

称为单循环链表,简称循环链表

双向链表

在单链表的每个结点中,再设置一个指向其前驱结点的指针域 (就意味着双向链表的结点都有俩个指针域,一个指向直接后继, 一个指向直接前驱)

栈(特殊的线性表)

限定仅在表尾进行插入和删除操作的线性表,又称后进先出(LIFO)的线性表 (允许插入和删除的一端称为栈顶,另一端称为栈底)

队列(特殊的线性表)

只允许在一端进行插入操作,而另一端进行删除操作的线性表 先进先出(FIFO)

顺序存储结构(顺序队列)

循环队列

链式存储结构(链队列)

串(字符串)

有0个或多个字符组成的有限序列

针对的是字符集,就是说把字符串中多个字符连在一起

存储结构

顺序存储结构

链式存储结构

模式匹配


朴素的描述匹配 (从头开始一个个字符匹配)

效率很低,复杂度为O((n-m+1)*m) n是总的字符串,m是需要匹配的字符串

KMP模式匹配算法

算法证明和更详细的说明,请参阅《算法导论》第2版第32章字符串匹配

KMP模式匹配算法改进

树形结构(非线性结构)

数据元素之间存在一对多的层次关系

数是n(n>=0)个节点的有限集。若n=0,称为空树。树的节点是互不交互的。 + :节点拥有的子数(节点)数量称为"度",度为0的称为叶节点。 + 树的度:树的度是树内各节点的度的最大值 + 节点的层次:跟为第一层,一次类推。 + 数的深度:数中节点的最大层次称为"深度"或"高度"

二叉树


特点

  • 每个结点最多有俩棵子树

  • 左右子树是顺序的,次序不能颠倒

  • 即使树中只有一棵子树,也要区分左右

五种形态

  • 空二叉树

  • 只有一个根结点

  • 根结点只有左子树

  • 根结点只有右子树

  • 根结点既有左子树,又有右子树

性质

在二叉树的第i层上之多有2i-1(i-1是上标)个结点

深度为K的二叉树至多有2k-1(k>=1,k是上表)个结点

特殊二叉树

斜树

  • 所有结点都只有左子树的二叉树叫左斜树

  • 所有结点都只有右子树的二叉树叫右斜树

满二叉树

一个二叉树中,所有分支结点都存在左子树和右子树, 并且所有叶子都在同一层上,称为满二叉树

完全二叉树

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中 在最左边,这就是完全二叉树。

线索二叉树

每个二叉树左右俩个指针域,如果为空,放着也浪费空间。 所以第一次遍历二叉树时,如果左指针域为空就存前驱地址, 右指针域为空就存后继地址。但是左侧需要一个tag来标识左指 针域存的是左孩子结点还是前驱,右侧也同样需要。

存储结构


顺序存储结构

只用于完全二叉树(因为完全二叉树定义的严格, 可以用顺序结构表示出二叉树的结构,很有优越性。详情参考P172) 该结构不太通用,通用的见二叉链表

二叉链表

二叉树每个结点最多有俩个孩子,所以可以用 一个数据域+俩个指针域这样的结构存储二叉树

遍历

概念

从根结点出发,按照某种次序依次访问二叉树中 所有结点,使得每个结点被访问一次且仅被访问一次

遍历方法(限定了从左到右的习惯)

前序遍历

根结点=>左子树=>右子树 (切记:是先把所有左子树遍历完了,再遍历右子树)

中序遍历

从根结点开始(并不是先访问根结点),遍历根结点的 左子树=>根结点=>右子树

后序遍历

从根结点开始(并不是先访问根结点),遍历根结点的 左子树=>右子树=>根结点

层序遍历(BFS常用)

根结点一层层从上而下遍历

哈夫曼树(也叫最优二叉树)

带权路径长度WPL最小的二叉树称作哈夫曼树

哈夫曼编码


哈夫曼编码实现压缩,解压缩

原理:先构造哈夫曼树,然后对字符串再次编码,二进制的长度会明显缩小, 所以达到了压缩的效果。解压缩也要用哈夫曼树,才能知道哪几个二进制对应哪个字符

图形结构(非线性结构)

数据元素是多对多的关系

概念:有顶点的有穷非空集合和顶点之间边的集合组成 表示为G(V,E),其中G表示一个图,V是图G中顶点的集合,E是边的集合

特点:图中数据元素称为顶点,图中不允许没有顶点

术语

顶点

图中数据元素称为顶点,图中不允许没有顶点

无向边

顶点Vi到Vj(i和j是下标)之间的边没有方向, 则称这条边为无向边,用无序偶对(ViVj)来表示

有向边

顶点Vi到Vj之间的边有方向, 则称这条边为有向边,也称为弧

无向图

图中任意俩个顶点之间的边都是无向边

连通图

概念:从顶点V导顶点V'有路径,称V和V'是连通的。 如果对于图中任意俩个顶点都是连通的则称为连通图 (能连通就行,不一定要相邻)

连通分量

  • 要是子图

  • 子图要是连通的

  • 连通子图还有极大顶点数

  • 具有极大顶点数的连通子图包含依附于这些顶点的所有边

生成树

一个连通图的生成树是一个极小的连通子图, 它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边(p221)

有向图

图中任意俩个顶点之间的边都是有向边

强连通图

概念:如果对于图中任意俩个顶点都是连通的则称为连通图 (能连通就行,不一定要相邻)

强连通分量

参考连通分量定义

有向树

概念:一个有向图恰有一个顶点的入口为0(根节点), 其余顶点的入度均为1,则是一颗有向树

简单图

不存在顶点到其自身的边(自己到自己),且同一条边不重复出现

无向完全图

在无向图中,任意俩个顶点之间都存在边

有向完全图

在有向图中,任意俩个顶点之间都存在方向互为相反的俩条弧网

有的图的边或弧具有与它相关的数字,这叫做权。权可以表示一个顶点到另 一个顶点的距离或者耗费,这种带权的图称为网

存储结构


邻接矩阵

用俩个数组来表示图,一个一维数组存储图中顶点信息, 一个二维数组(邻接矩阵)存储图中的边或弧的信息

缺点

对于边数相对于顶点较少(顶点多,边数少)的图, 这种结构存在存储空间的浪费

邻接表

数组和链表相结合的存储方法称为邻接表

特点

  • 图中顶点用一个一维数组存储

  • 每个顶点的所有邻接点构成一个新线性表,

  • 如果是有向图,还可以建立有向图的逆邻接表,

即对每个顶点vi都建立一个链接为vi为弧头的表。 (可以很容易得到顶点的入度或以顶点为弧头的弧)

优缺点

想了解入度就必须遍历整个图才知道,反之,逆邻接链表解决了入度却不了解出度的情况。俩者不可兼得

十字链表

把邻接表和逆邻接表结合起来

邻接多重表

主要优化无向图

边集数组

俩个一维数组构成,一个存储顶点的信息,一个存储边的信息。 这个边数组每个数据元素由一条边的起点下标,终点下标和权重组成

遍历

深度优先(DFS)

约定原则:在没有碰到重复顶点的情况下,始终向右手边走。 走回到顶点之后,还要按原路一步步返回,在一步步验证是否都都走过了

广度优先(BFS)

图需要变形下,改造成类似树那样有明显的层级关系的样式

最小生成树

概念:我们把构造连通网的最小代价生成树称为最小生成树

所谓最小代价,就是n个顶点,用n-1条边 把一个连通图连接起来,并且使得权值的和最小

算法

普里姆(Prim)算法

以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树

克鲁斯卡尔(Kruskal)算法

以最小权值边开始构建

最短路径

迪杰斯特拉(Dijkstra)算法

一步步求出与顶点的最短路径,过程中都是基于已经求出的最大路径的基础上

佛洛伊德(Floyd)算法

拓扑排序算法

物理结构(存储结构)

数据的逻辑结构在计算机中的存储形式

顺序存储结构

数据元素存放在地址连续的存储单元里, 数据间的逻辑关系和物理关系是一致的 (不方便插入,删除)

不方便插入,删除

链式存储结构

数据元素存放在任意的存储单元里,这组存储单元可以是连续的, 也可以是不连续的 (很灵活,给个指针就能找到。需要一个指针存放数据元素的地址)

很灵活,给个指针就能找到。需要一个指针存放数据元素的地址

索引存储结构

为了方便查找,整体无序,但索引块之间有序,需要额外空间,存储索引表。 优点:对顺序查找的一种改进,查找效率高 缺点:需额外空间存储索引

散列存储结构

选取某个函数,数据元素根据函数计算存储位置可能存在多个数据元素存储在同一位置,引起地址冲 优点:查找基于数据本身即可找到,查找效率高,存取效率高。 缺点:存取随机,不便于顺序查找。

数据运算

查找运算

顺序表查找

顺序查找(线性查找)

从表中第一个(或最后一个)记录开始,逐个进行记录的的关键字和给定值比较。

有序表查找

折半查找(二分查找)

切记:表必须是有序的。mid=(low+high)/2。复杂度是0(logn)

可以优化的地方:每次都从1/2处查找,对于有些场景还是不太适合的, 比如查找am单词,很显然从字典的前面查找效率更高,所以优化点是从哪里开始折半

插值查找

公式:mid=low+(key-a[low])*(high-low)/a[high]-a[low] ;low和high是数组的下标

适合场景:

表长较大,而关键字分配又比较均匀的查找表,性能比折半查找要好得多。复杂度也是0(logn)

斐波那契查找

构造另外一个斐波那契数列用于辅助

公式:mid=low+F[K-1]-1 ;F是斐波那契数列

比较:平均效率优于折半查找,最坏情况下,效率低于折半

线性索引查找

数据集增长非常快的情况下,保证关键字有序,代价很高昂。所以这种数据都是按先后顺序存储。

稠密索引

索引项一定要按照关键码有序的排列

分块索引

把数据集的记录分成了若干块,满足俩个条件

  • 块内无序

  • 块间有序

倒排索引(P312)

概念:记录号表存储具有相同次关键字的所有记录的记录号 (可以指向记录的指针或者该记录的主关键字)

搜索引擎最基础的搜索技术

二叉搜索树(又称二叉查找树/排序数)


特点:

  • 若左子树不为空,则左子树上所有结点值均小于根结点的值

  • 若右子树不为空,则右子树上所有结点的值均大于它的根结点的值

  • 它的左右子树也分别为二叉排序树

优点:

是一个既使得插入和删除效率不错,又可以比较高效率的实现查找的算法

缺点:

极端情况下,会退化成链表。时间复杂度为O(n)

平衡二叉搜索树(AVL树)


概念:是一种二叉排序树,其中每一个节点 的左子树和右子树的高度差绝对值不超过1

优缺点:

维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多, 更多的地方是用追求局部而不是非常严格整体平衡的红黑树。 当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树。

多路查找树(B树)


概念:每一个结点的孩子树可以多余俩个,且每一个结点处可以存储多个元素

4种形式

2-3树

每一个结点都具有俩个孩子(称为2结点),或三个孩子(称为3结点)

2-3-4树

2-3树的扩展,最多四个孩子

B树

一种平衡的多路查找树

所有叶子结点都位于同一层

B+树

应文件系统那个所需而出的一种B树的变形树

出现在分支节点中的元素会在叶子结点中再次列出,每一个叶子结点都会保存一个指向后一叶子结点的指针

红黑树

概念:一种自平衡二叉查找树,和AVL树类似(并不是真正的平衡二叉树), 都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。

适合:适合搜索,插入,删除较多的情况

性质:

每个结点要么是红色,要么是黑色

根结点永远是黑色

所有的叶节点都是空结点(即null),并且是黑色的

每个红色结点的俩个子结点都是黑色(从每个叶子到跟的路径上不会有俩个连续的红色结点)

从任一结点到其子树中每个叶子结点的路径都包含相同数量的黑色结点

关键性质:

这些性质强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。主要原因在于,性质4导致了路径不能有两个毗连的红色节点,最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点,根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长

散列表查找(哈希表)

概念:散列技术是在记录的存储位置和它的关键字之间建立一个稳定的对于关系f, 使得每个关键字key对于一个存储位置f(key),f称为散列函数,又称为哈希(Hash)函数

特点

  • 在存储时,通过散列函数计算记录的散列地址,并按此散列地址存储该记录

  • 查找记录时,我们通过同样的散列函数计算记录的散列地址,按此散列地址访问该记录

缺点

有时候俩个关键字不同,但是算出来的地址相同,称为冲突

散列函数构造方法

直接定址法

数字分析法

平方取中法

折叠法

除留余数法

随机数法

散列冲突的解决方法

开放定址法

一个冲突,就去寻找下一空的散列函数

再散列函数法

准备多个散列函数,有冲突就换一个

链地址法

公共溢出区法

冲突的都单独存储到溢出表中

排序运算

概念

内排序与外排序

内排序是在排序整个过程中,待排序的所有记录都放置在内存中。外排序是由于排序的记录太多, 不能同时放置在内存,整个排序过程需要在内外存之间多次交换数据才能进行

排序种类

冒泡排序

复杂度O(n2) 2是上标

正宗的冒泡排序是相邻元素俩俩比较

冒泡排序优化

加个flag,如果后面后面已经是有序的了,就不需要再继续后面的循环判断了

简单选择排序

每个元素依次和后面所有的元素比较大小

直接插入排序

将一个记录插入到已经排好序的有序表中,从而得到一个新的记录数+1的有序表

希尔排序

把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;虽则增量逐渐减少, 每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组

堆排序

利用堆这种数据结构所设计的一种排序算法

归并排序

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序

快速排序

通过一次排序将待排序记录分割称独立的俩部分,其中一部分记录的关键字均比另一部分小, 则可分别堆这俩部分记录继续进行排序,以达到整个序列有序的目的

算法

算法是解决特定问题求解步骤的描述。

时间复杂度(大O表示法)

推导方法

\1. 用常数1取代运行时间汇总的所有加法常数

\2. 在修改后的运行次数函数中,只保留最高阶

\3. 如果最高阶项存在且不是1,则去除与这个项相乘的常数, 得到的结果就是大O阶

常见的复杂度

常数阶 => O(1)

线性阶 => O(n)

对数阶 => O(log2n,缩写为logn)

平方阶 => O(n2)

内容结束,感谢浏览,如果需要pdf等类型文档,记得私信!💪

相关文章:

actionScript 数组去重

public function unique(array:Array):Array { for (var i:int0; i < array.length; i) { for (var j:inti 1; j < array.length; j) { //注意 if (array[i] array[j]) { array.splice(j, 1); j--; } } } return array…...

【C++音视频开发】初级篇 | RGB与YUV

前言 本专栏将不间断更新有关C音视频开发的内容&#xff0c;其中有初级篇、中级篇与高级篇的内容&#xff0c;包括但不限于音视频基础、FFmpeg实战、QT、流媒体客户端、流媒体服务器、WebRTC实战、Android NDK等等。是博主花了将近5000元购买的课程中的知识点&#xff0c;其中…...

qsettings 读写注册表

qsettings简单的实现一个注册表读写操作&#xff0c;记录程序中需要保存的信息。使用qsettings声明对象之前&#xff0c;需要指明qsettings的组织名和应用名&#xff0c;分别利用QCoreApplication::setOrganizationName()和QCoreApplication::setApplicationName()来指定组织名…...

CodeForces - 545E Paths and Trees 最短路建树

题目链接&#xff1a;点击查看 Little girl Susie accidentally found her elder brothers notebook. She has many things to do, more important than solving problems, but she found this problem too interesting, so she wanted to know its solution and decided to a…...

ADB学习笔记

简介&#xff1a; ADB的全称为Android Debug Bridge&#xff08;调试桥&#xff09;&#xff0c; 它是一个客户端-服务器端程序&#xff0c;其中客户端是你用来操作的电脑, 服务器端是android设备。作用显而易见&#xff0c;能方便我们在PC上对手机进行调试的一些工作。 原理…...

http load介绍

前几天工作中要对项目的接口做简单压测&#xff0c;就使用了http load做了简单测试&#xff0c;下面介绍一下这款工具的使用说明。简介&#xff1a;http_load是基于linux平台的性能测试工具&#xff0c;它体积非常小&#xff0c;仅100KB。它以并行复用的方式运行&#xff0c;可…...

TestNG使用总结

TestNG简介&#xff1a; TestNG是一个测试框架&#xff0c;其灵感来自JUnit和NUnit&#xff0c;但同时引入了一些新的功能&#xff0c;使其功能更强大&#xff0c;使用更方便。 TestNG相较于Junit的优点&#xff1a; 可指定执行顺序&#xff0c; dependsOnMethods 属性来应对…...

面向对象编程的弊端

英文原文&#xff1a;What’s Wrong with OOP and FP 我不理解为什么人们会对面向对象编程和函数式编程做无休无止的争论。就好象这类问题已经超越了人类智力极限&#xff0c;所以你可以几个世纪的这样讨论下去。经过这些年对编程语言的研究&#xff0c;我已经清楚的看到了问题…...

flex 计算指定日期是本年度第几周

/** * 计算指定日期是本年度第几周 *传日年月日&#xff0c;返回number */ private function weekOfYear(yyyy:Number,mm:Number,dd:Number):Number{ var myDate:Date new Date(yyyy, mm - 1, dd); var startDate:Date new Date(yyyy,0,1); v…...

SpringCloud Zuul(四)之工作原理

一、筛选器概述 Zuul的中心是一系列过滤器&#xff0c;这些过滤器能够在HTTP请求和响应的路由期间执行一系列操作。 以下是Zuul过滤器的主要特征&#xff1a; 类型&#xff1a;通常定义路由流程中应用过滤器的阶段&#xff08;尽管它可以是任何自定义字符串&#xff09;执行…...

webservice学习记录笔记(一)

一、先理解什么是服务 现在的应用程序变得越来越复杂&#xff0c;甚至只靠单一的应用程序无法完成全部的工作。更别说只使用一种语言了。 写应用程序查询数据库时&#xff0c;并没有考虑过为什么可以将查询结果返回给上层的应用程序&#xff0c;甚至认为&#xff0c;这就是数…...

接口测试那些事儿

什么是接口&#xff1f; 首先&#xff0c;在讲接口测试之前&#xff0c;我们先要搞清楚接口类型的概念。 接口&#xff1a;可能是系统与系统&#xff08;包括服务与服务&#xff09;之间的调用&#xff0c;像A系统&#xff08;服务&#xff09;给B系统&#xff08;服务&#x…...

CodeForces - 1084C The Fair Nut and String 思维

The Fair Nut found a string s. The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences p1,p2,…,pk , such that: For each i (1≤i≤k), spi a.For each i(1≤i<k), there is…...

Gym - 101986B Parallel Lines dfs暴力

链接&#xff1a;点击查看 题意&#xff1a;偶数个点&#xff0c;两点可连成一条线&#xff0c;求平行线最大对数 题解&#xff1a;当时想的时候傻逼了&#xff0c;想成了每次选两个点就是16*15/2 * 14*13/2 ..... 其实不需要这样&#xff0c;因为每个点必须要匹配一个的&…...

POJ - 2406 Power Strings next数组应用循环节

题目链接&#xff1a;点击查看 Language:Default Power Strings Time Limit: 3000MS Memory Limit: 65536KTotal Submissions: 61784 Accepted: 25534Description Given two strings a and b we define a*b to be their concatenation. For example, if a "abc" and…...

CodeForces - 545D Queue 贪心 排序

题目链接&#xff1a;点击查看 Little girl Susie went shopping with her mom and she wondered how to improve service quality. There are n people in the queue. For each person we know time ti needed to serve him. A person will be disappointed if the time he …...

Jmeter访问HTTPS请求

公司最近在搞全站HTTPS改造&#xff0c;进一步提高网站的安全性&#xff0c;防止运营商劫持。那么&#xff0c;改造完成后&#xff0c;所有前后端的URL将全部为https。 So &#xff0c;研究下怎么用Jmeter访问https请求呢。 其实很简单&#xff0c; 第一步在jmeter中创建HTT…...

HDU - 6188 Duizi and Shunzi 贪心

Nike likes playing cards and makes a problem of it. Now give you n integers, ai(1≤i≤n) We define two identical numbers (eg: 2,2) a Duizi, and three consecutive positive integers (eg: 2,3,4) a Shunzi. Now you want to use these integers to form Shunzi and …...

JSON相关知识点

JSON是工作中经常会遇到的一种数据结构&#xff0c;下面来讲讲与他相关的一些知识点。 JSON简介&#xff1a; JSON: JavaScript Object Notation(JavaScript 对象表示法) JSON 是存储和交换文本信息的语法,类似 XML。 JSON 比 XML 更小、更快&#xff0c;更易解析。 JSONObj…...

牛客网 Applese 走方格

题目链接&#xff1a;点击查看 题解&#xff1a;我们容易发现到当n,m都为奇数时&#xff0c;是回不到原点的&#xff0c;因为你无论哪个方向走一去一回就是两步&#xff0c;所以n和m必然有一个偶数&#xff0c;那至于我们怎么走呢&#xff0c;看下图&#xff0c;注意的是n1,m2…...

mysql重置Root密码

方法一: 在my.ini的[mysqld]字段加入&#xff1a; skip-grant-tables 重启mysql服务&#xff0c;这时的mysql不需要密码即可登录数据库 然后进入mysql mysql>use mysql; mysql>更新 user set passwordpassword(新密码) WHERE Userroot; mysql>flush privileges; 运…...

idea常用技巧收集

idea相比eclipse的优点我在这里就不赘述了&#xff0c;更多参考&#xff1a;idea官网,本文重点讲下自己在idea使用过程中常用的一些技巧&#xff0c;以后随时更新…… 主要分成三大块&#xff1a; 1. 系统设置 2. 快捷键 3. 其他设置 系统设置 主题风格设置&#xff1a;默…...

架构设计 例子和实践 系统设计说明书

架构设计 例子和实践 系统设计说明书(架构、概要、详细)目录结构演进架构中的领域驱动设计Web架构设计经验分享软件架构设计从MVC框架看MVC架构的设计领域驱动设计(Domain Driven Design)参考架构详解关于垂直切分Vertical Sharding的粒度企业应用集成与开源ESB产品ServiceMix和…...

想要玩转实现负载均衡,你知道这些吗?

转载自 想要玩转实现负载均衡&#xff0c;你知道这些吗&#xff1f; 一、前言 互联网早期&#xff0c;业务流量比较小并且业务逻辑比较简单&#xff0c;单台服务器便可以满足基本的需求&#xff1b;但随着互联网的发展&#xff0c;业务流量越来越大并且业务逻辑也越来越复杂&…...

初识spring RestTemplate

《spring实战》读书笔记之初识spring RestTemplate。首先需要先了解下什么是REST。 REST&#xff1a;官方解释&#xff0c;表述性状态转移。 感觉还是不知所云&#xff0c;参考下怎样用通俗的语言解释REST&#xff0c;以及RESTful&#xff1f; 即URL定位资源&#xff0c;用H…...

程序员着装的改变

是什么力量&#xff0c;让任何地方的程序员都享有「免于体面的自由」&#xff1f; 在今天的社会里&#xff0c;工程师往往代表着知识水平和社会地位。每当普通人听到这个头衔&#xff0c;总会报之以敬仰的目光&#xff1a; 但有一种工程师&#xff0c;虽然也是如假包换的高级技…...

谈谈系统稳定性设计

转载自 谈谈系统稳定性设计 一、差旅随想 因为base在分公司&#xff0c;需要经常去总部出差&#xff0c;所以搭乘飞机成了家常便饭&#xff0c;很多时候坐在飞机上会不由的感叹&#xff0c;设计制造这样精密复杂的机器的那帮人真的是了不起&#xff0c;他们是怎样保证这样一台…...

成为更优秀的程序员:退后一步看问题

转载自 成为更优秀的程序员&#xff1a;退后一步看问题 一天&#xff0c;在工作中… Bug #3890 来自客户&#xff1a; 有个程序出现了错误&#xff0c;程序提示说“SpeedCalculator::compute()里出现了除零情况”。 请尽快修复&#xff01; 你打开SpeedCalculator.php&#…...

ZOJ - 2968 Difference Game 思维

题目链接&#xff1a;点击查看 Now you are going to play an interesting game. In this game, you are given two groups of distinct integers and C coins. The two groups, named Ga and Gbrespectively, are not empty and contain the same number of integers at firs…...

20个高级Java面试题汇总

转载自 20个高级Java面试题汇总 译文链接&#xff1a;http://www.codeceo.com/article/20-java-advanced-interview-questions.html 英文原文&#xff1a;Advanced Java Interview Questions 翻译作者&#xff1a;码农网 – 小峰 这是一个高级Java面试系列题中的部分。这一部分…...

单元测试框架-Junit介绍

在工作中编写接口脚本中经常用到junit作为测试框架&#xff0c;下面总结一下junit的用法和编写规范&#xff0c;供大家参考。 junit简介&#xff1a; 基于Java语言的单元测试框架&#xff0c;在日常工作中被广泛运用于单元测试和接口测试。 junit官网&#xff1a;http://jun…...

javaSE之动态代理

动态代理技术&#xff1a; 使程序更加灵活&#xff0c;可以在代理java类的时候加入一些功能。 很类似过滤器&#xff0c;区别&#xff1a; 过滤器是自己编写西横须实现的功能 动态代理是JVM内部机制 实现步骤&#xff1a; 1.真是业务对象&#xff08;被代理对象&#xff09; 2…...

CodeForces - 500B New Year Permutation floyd+选择排序

User ainta has a permutation p1, p2, ..., pn. As the New Year is coming, he wants to make his permutation as pretty as possible. Permutation a1, a2, ..., an is prettier than permutation b1, b2, ..., bn, if and only if there exists an integer k (1…...

支付系统的防重设计

转载自 支付系统的防重设计 导读 “目前在互联网应用的大部分支付场景中&#xff0c;对接支付宝、微信移动支付产品这样需要用户参与支付流程的支付方式已经变得非常普遍&#xff0c;类似的还有PC端银行网银支付&#xff1b;而通过绑定用户银行卡、对接银行卡快捷支付通道直接…...

Hibernate 主键生成策略

<generator>:主键生成策略 increment:递增,hibernate自动产生主键.max(id) ,采用带走1算法,多进程/集群环境下不推荐使用. identity:设置表主键是自增字段,映射文件采用该策略,依赖底层库, auto_increment identity 适用于MySQL、DB2、MS SQL Server&#xff0c;…...

flex 事件机制详解

事件机制的工作流程 1&#xff1a;关于事件流 当一个事件发生&#xff0c;必然存在一个派发事件的对象&#xff0c;这里称之为目标对象。 当事件发生后flashPlayer生成一个携带数据的对象&#xff0c;然后检查目标对象是否处于显示层中&#xff0c;如果是则遍历从根容器一直到目…...

codeforces 501 C. Misha and Forest 巧妙的拓扑排序

Lets define a forest as a non-directed acyclic graph (also without loops and parallel edges). One day Misha played with the forest consisting of n vertices. For each vertex v from 0 to n - 1 he wrote down two integers, degreev and sv, were the first inte…...

HDU - 3746 Cyclic Nacklace next数组求 循环节

题目链接&#xff1a;点击查看 CC always becomes very depressed at the end of this month, he has checked his credit card yesterday, without any surprise, there are only 99.9 yuan left. he is too distressed and thinking about how to tide over the last days. …...

Redis进阶之内存模型

转载自 Redis进阶之内存模型 前言 Redis是目前最火爆的内存数据库之一&#xff0c;通过在内存中读写数据&#xff0c;大大提高了读写速度&#xff0c;可以说Redis是实现网站高并发不可或缺的一部分。 我们使用Redis时&#xff0c;会接触Redis的5种对象类型&#xff08;字符…...

CodeForces - 557C Arthur and Table 预处理 前缀

题目链接&#xff1a;点击查看 题意&#xff1a;有n个桌腿&#xff0c;要砍掉某些桌腿&#xff0c;使剩下的桌腿中长度最大的桌腿的数量如果超过一半。砍掉每个桌腿需要付出代价。求最小的代价和&#xff0c;操蛋&#xff0c;砍掉的意思是直接去掉&#xff0c;我理解成了&…...

MD5加密算法详解

注&#xff1a;MD5不是绝对的安全&#xff0c;有俩md5解决 /******************************************************************************* * keyBean 类实现了RSA Data Security, Inc.在提交给IETF 的RFC1321中的keyBean message-digest * 算法。 *****************…...

每天一个adb命令:screen 命令详解

screen命令分为截屏screencap命令及录制视频screenrecord命令。 screencap命令&#xff1a; sage: screencap [-hp] [-d display-id] [FILENAME]-h: this message-p: save the file as a png.-d: specify the display id to capture, default 0. If FILENAME ends with .png …...

markdown编写入门

什么是markdown&#xff1f; Markdown 是一种轻量级的「标记语言」&#xff0c;通过简单的标记符号来格式化排版&#xff0c;是文本展现的更加优美&#xff0c;形象。 markdown优点&#xff1a; 1.不像office&#xff0c;存在版本兼容问题&#xff0c;markdown无此问题&#…...

CCPC-Wannafly Winter Camp Day5 (Div2, onsite)

题目链接&#xff1a;点击查看 Kropki&#xff1a; 题目描述&#xff1a; 你有一个11到nn的排列p_1, p_2, \dots, p_np1​,p2​,…,pn​&#xff0c;对于所有的i (1\leq i\leq n-1)i(1≤i≤n−1)&#xff0c;如果p_ipi​和p_{i1}pi1​中&#xff0c;有一个数是另一个的两倍&…...

十分钟快速了解 ES6 Promise

转载自 十分钟快速了解 ES6 Promise 什么是Promise Promise最早由社区提出并实现&#xff0c;典型的一些库有Q&#xff0c;when&#xff0c; bluebird等&#xff1b;它们的出现是为了更好地解决JavaScript中异步编程的问题&#xff0c;传统的异步编程最大的特点就是地狱般的回…...

POJ - 2955 Brackets 入门区间dp

We give the following inductive definition of a “regular brackets” sequence: the empty sequence is a regular brackets sequence,if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, andif a and b are regular brackets seque…...

分布式系统Paxos算法

转载自 分布式系统Paxos算法 这是一个有关Paxos算法非常形象的讲解与示范。Paxos是能够基于一大堆完全不可靠的网络条件下却能可靠确定地实现共识一致性的算法。也就是说&#xff1a;它允许一组不一定可靠的处理器&#xff08;服务器&#xff09;在某些条件得到满足情况下就能…...

小乐乐学数学 哈理工第八届程序设计竞赛同步赛(高年级)H 树状数组 + 离线 + 互质区间

链接&#xff1a;https://ac.nowcoder.com/acm/contest/301/H 来源&#xff1a;牛客网 题目描述 小乐乐上了一节数学课&#xff0c;数学老师讲的很好&#xff0c;小乐乐听的也如痴如醉。 小乐乐听了老师的讲解&#xff0c;知道了什么是素数&#xff0c;现在他想做几个习题。 …...

《Maven实战》读书笔记

之前对Maven有些认识&#xff0c;通过这本书《Maven实战》一起系统的回顾一下&#xff0c;总结的东西不会很全面&#xff0c;但都是日常工作中最常用的。 简介&#xff1a; maven翻译为“知识的积累”&#xff0c;基于项目对象模型&#xff08;Project Object Model&#xff0…...

记一次爬虫实践(一):思路及模拟登录

需求背景 因为我们的应用通常运行在h5上&#xff0c;因此图片格式选择了加载较快的webp格式&#xff0c;但是运营提起有在pc上批量下载图片&#xff08;要求图片格式&#xff09;的需求&#xff0c;目前比较麻烦&#xff0c;需要登录h5-找到接口中对应图片资源-一张张另存为到…...