数据结构与算法基础-Java版



数据结构与算法基础（java版）

这是代码和思维导图
链接：https://pan.baidu.com/s/1hybDPGenDnFHWbszdEmUaA
提取码：i26u

1.1数据结构概述

什么是数据结构？

• 数据结构是指相互存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
• 白话：数据与数据之间的关系

数据结构主要学什么？

• 数据的存储结构：数据在计算机内存是什么方式存储的
  • 顺序存储结构
  • 链式存储结构
• 数据的逻辑结构：数据与数据之间是什么关系
  • 集合结构：集合结构中的数据同属于一个集合，他们之间是并列的关系，除此之外没有其他的关系。
  • 线性结构：线性结构中的元素存在一对一的相互关系。
  • 树形结构：树形结构中的元素存在一对多的相互关系。
  • 图形结构：树形结构中的元素存在多对多的相互关系。

1.2算法概述

什么是算法？

• 是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述问题的策略机制。
• 白话：解决问题的思路

算法的特性

• 输入：可以为算法提供0到多个输入
• 输出：每个算法至少有一个输出
• 有穷性：算法在有限的时间得出结果
• 确定性：一个结果对应一个输出
• 可行性：算法能解决实际问题

算法的基本要求

• 正确性：能正确的解决问题
• 可读性：算法有一定的可读性
• 健壮性：对不同的输入都有相应的反应，不合法的输入要给出相应的提示输出
• 时间复杂度：算法要占用的时间
• 空间复杂度：算法运行占用的内存

2.1数组的基本使用

数组（Array） 是一种很常见的数据结构。它由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。

我们直接可以利用元素的索引（index）可以计算出该元素对应的存储地址。

数组的特点是：提供随机访问 并且容量有限。

数组的基本使用

• 数组的创建，获取数组长度，数组元素赋值，遍历数组

2.2 数组元素的添加

数组元素的添加

• 创建一个新的数组，复制原数组，再把目标元素添加到新数组

2.3数组元素的删除

数组元素的删除

• 创建一个新的数组来接收

2.4面向对象的数组

面向对象的数组

• 把数组当成一个对象创建
• 在数组类中定义增删改的方法（感觉像在写简单的arrayList源码）

2.5查找算法之线性查找

2.6查找算法之二分法查找

二分查找的前提：被查找的目标数组必须是有序数组

实现思路：把数组切成两半，从中间开始找

2.7查找算法整合

2.8栈

栈 (stack)只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 后进先出（LIFO, Last In First Out） 的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。

栈常用一维数组或链表来实现，用数组实现的栈叫作 顺序栈 ，用链表实现的栈叫作 链式栈 。

以下代码写了的基本操作

2.9队列

队列 是 先进先出( FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是 入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue

队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

以下代码写了的基本操作

2.10单链表

链表（LinkedList） 虽然是一种线性表，但是并不会按线性的顺序存储数据，使用的不是连续的内存空间来存储数据。

链表的插入和删除操作的复杂度为 O(1) ，只需要知道目标位置元素的上一个元素即可。但是，在查找一个节点或者访问特定位置的节点的时候复杂度为 O(n) 。

使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但链表不会节省空间，相比于数组会占用更多的空间，因为链表中每个节点存放的还有指向其他节点的指针。除此之外，链表不具有数组随机读取的优点。

单链表 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向 null。

以下写了单链表的基本操作

2.11删除单链表中的节点

节点的删除

2.12往单链表中插入节点

插入节点

2.13循环链表

循环链表 其实是一种特殊的单链表，和单链表不同的是循环链表的尾结点不是指向 null，而是指向链表的头结点。

2.14双向循环链表

每一个节点都可以找其节点的上一个节点和下一个节点，因为是循环链表，所有没有最后一个节点

2.15递归和斐波拉契

递归：在方法（函数）的内部调用该方法（函数本身的编程方式）

2.16汉诺塔问题

​ 相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。（A,B,C依次为左中右）

3.1时间复杂度和空间复杂度

‘时间复杂度和空间复杂度详解’

时间复杂度：一般情况下，算法的基本操作语句的重复执行次数就是问题规模n的某个函数。用T(n)表示，若有某个辅助函数f(n)，使得当n趋近无穷大时，T(n) / f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。当作T(n) = O( f(n) )，称O( f(n) )为算法的渐进时间复杂度，简称时间复杂度。

T(n)不同，但时间复杂度可能相同。如：T(n) = n^2 + 5n + 6于T(n) = 3n^2 + 3n + 2 它们的T(n)不同，但时间复杂度相同，都为O(n^2)。

3.2交换算法之冒泡排序

冒泡排序：冒泡排序是一种简单的排序算法，也是笔试题中出现最多的一种排序算法题。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。（‘排序动画’）

算法描述：

• 从一个元素开始，两两比较，如果左边元素比右边大，就交换他们的位置。
• 对每一个相邻元素做相同的工作，这样第一轮比较之后最大的元素就会在最右边。
• 下一轮做重复的操作，但是不用比较最后一个元素。
• 重复以上操作，知道排序完成。

3.3交换算法之快速排序

快速排序：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，数据结构与算法基础-Java版;以达到整个序列有序。（‘排序动画’）

算法描述：

• 设置数组第一个数为标准数，设置一个开始下标start和结束下标end
• 拿结束下标指向的最后一个元素和标准数相比，如果比标准数大，下标就减一end–，指向倒数第二个元素，如果比标准数小，就用end指向的元素，替换掉start指向的元素
• 拿开始下标指向的第一个元素和标准数相比，如果比标准数小，下标就加一start++，指向第二个元素，如果比标准数大，就用start指向的元素，替换掉end指向的元素
• 重复23，开始下标和结束下标都重合，把标准数赋值到重合的位置，这样就得到了前部分的所有数比标准数小，后一部分的所有数比标准数大
• 然后分别将前后的作为整体，再进行1234步骤，一次循环递归就会得到顺序数组
• 注意：如果只有以上步骤没有条件判断就会死循环，所有需要加一个判断即，当开始下标小于结束下标时，才能比较排序

3.4插入算法之插入排序

插入排序：插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。（‘排序动画’）

算法描述：

• 从一个元素开始遍历（从前往后），如果当前元素比前一个元素大就继续遍历
• 如果当前元素比前一个元素小，记录当前元素
• 遍历当前元素前的所有元素（从后往前），如果当前元素比前一个元素小，那么前一个元素往后移一位，继续往前比较知道当前元素比前一个元素大，就把记录的元素放在当前位置
• 知道第一步遍历结束，排序就完成了

3.5插入排序之希尔排序

前言：假设有一个数组，数组元素为[3,4,5,6,7,2]，如果这个数组用插入排序的话，排序的效率比较低。（‘排序动画’）

希尔排序：1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法描述：

• 将元素组的长度除以2得到步长d，根据步长将数组分组（例如：第一个元素是第一个arr[1],那么和第一个元素同组的第二个元素就是arr[1 + d]，依次分组）
• 分组的组内元素进行插入排序，第一次分组结束
• 第二次分组再将步长除以2，再将组内的元素进行插入排序
• 重复123知道步长为0，在进行插入排序后，排序完成

3.6选择排序之简单选择排序

选择排序：选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述：

• 先假设第一个为最小，依次遍历比较，如果比标记的数小就交换位置
• 重复第一步知道排序结束

3.7排序算法之归并排序

归并排序：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述：

• 把长度为n的输入序列分为两个长度为n/2的子序列；
• 对这两个子序列采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

3.8排序算法之基数排序

基数排序：基数排序是按照低位（个位）先排序，然后收集；再按照高位（十位百位等取决于最大数）排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法描述：

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）。

3.9基数排序之队列实现

队列实现基数排序 --》把二维数组换成队列实现即可

4.1树结构概述

树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。

树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。

4.2二叉树的概述

二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。

二叉树 的分支通常被称作“左子树”或“右子树”。并且，二叉树 的分支具有左右次序，不能随意颠倒。

满二叉树：所有叶子节点都在最后有i曾，而且节点的总数为：2^n - 1 (n是树的高度)。

完全二叉树：所有叶子节点都在最后一层或倒数第二层，且最后一层的叶子节点在，倒数第二节的叶子节点在。

4.3创建二叉树

二叉树的创建

• 创建节点对象，二叉树对象
• 创建测试类，在测试类中创建二叉树

4.4遍历二叉树

遍历二叉树有三种顺序，前序遍历，中序遍历，后续遍历

• 前，中，后的意思是针对根节点在遍历结果中的位置
• 前序遍历就是再是
• 中序遍历就是然后最后
• 后序遍历就是然后，总结就是递归的思路实现

4.5二叉树中节点的查找

二叉树的查找和遍历很类似，也分为前序查找，中序查找，后续查找三种，下面会写其中的一种

4.6删除二叉树的字数

删除节点首先要找到需要删除的节点，让这个节点的父节点不指向这个节点（指向null），就等于删除了这个节点

4.7顺序存储的二叉树概述

顺序存储的二叉树：顺序存储的二叉树通常情况下只考虑

• 第n个元素的左子节点是：2*n + 1
• 第n个元素的右子节点是：2*n + 2
• 第n个 元素的父节点是：(n - 1) / 2

4.8顺序存储的二叉树的遍历

顺序存储的二叉树的遍历，三种，前序，中序，后序遍历

4.9常用排序算法之堆排序

大顶堆：父节点都大于子节点

小顶堆：父节点都小于子节点

升序排序用大顶堆，降序排序用小顶堆

4.10线索二叉树的概述

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

注意：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

线索化二叉树时，一个节点的前一个结点，叫前驱节点

线索化二叉树时，一个节点的后一个节点，叫后继节点

4.11线索二叉树代码实现

4.12线索二叉树的遍历

4.13赫夫曼树概述

赫夫曼树（最优二叉树）：它是n个带权节点构成的所有二叉树中，带权路径长度最小的二叉树。

叶节点的带权路径：从根结点出发，经过乘。

树的带权路径长度WPL(weighted path length)：树中所有叶子节点的带权路径长度之和。

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

3.14创建赫夫曼树的流程分析

创建赫夫曼树的流程分析

• 排序，取出根节点权值最小的两颗二叉树
• 组成一颗新的二叉树，前面取出来的两颗二叉树是新二叉的两个子树
• 根节点的权值是前两取出来的两颗二叉树的根节点的权值之和

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-q0yYo3tg-55)(file:///D:all app文件ImageC2CR~Z4P(S)]PX(RMJOU25YNSC2.png)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d47PdeRS-57)(file:///D:all app文件ImageC2CLOISR}I%TQ$[`I16SL%C5{V.png)]

4.15代码实现赫夫曼树

4.16赫夫曼编码原理分析

‘这节建议看原视频’

4.17数据压缩之创建赫夫曼树

进行赫夫曼编码

• 先统计每一个byte出现的次数，并放入集合
• 创建一棵赫夫曼树
• 创建赫夫曼编码
• 编码

4.18数据压缩之创建编码表&编码

进行赫夫曼编码

• 先统计每一个byte出现的次数，并放入集合
• 创建一棵赫夫曼树
• 创建赫夫曼编码
• 编码

4.19使用赫夫曼编码进行解码

解码主要分为两个步骤：

• 把byte数组转为二进制的字符串
• 把字符串按照指定的赫夫曼编码进行解码

4.20使用赫夫曼编码压缩文件

理解了以上的赫夫曼编码解码写一个压缩文件还是比较容易的

4.21使用赫夫曼编码解压文件

4.22二叉排序数的概述

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。定义：对于二叉树中的任何一个非叶子节点，要求左子节点比当前节点小，右子节点比当前节点大。一棵空树也算二叉排序树。

4.23创建二叉排序树&添加节点

创建二叉排序树&添加节点

4.24二叉排序树中查找结点

二叉排序树中查找结点

4.25二叉排序树中删除结点

删除节点有三种情况：

• 删除的节点为根节点
• 删除的节点是有一棵子树的节点
• 删除的节点是有两颗子树的节点

4.26平衡二叉树概述

平衡二叉树，又称AVL树。它或者是一棵，或者是具有下列性质的二叉树：对于任何一个子树而言，它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。

常用算法有：红黑树、AVL树、Treap等。

4.27构建平衡二叉树之单旋转

视频地址

4.28构建平衡二叉树之双旋转

双旋转是在单旋转的基础之上的

4.29计算机中数据的存储原理

数据存储的方式：硬盘和内存。

内存：

• 优点：使用电信号来保存数据的，不存在机器操作，所以访问速度非常快
• 缺点：造价高，断电后数据丢失。一般作为CPU的高速缓存

磁盘：

• 优点：造价低，容量大，断电数据不丢失
• 缺点：由于存储介质的特性，再加上机械运动耗费时间，所以磁盘的速度比较慢。

预读的长度一般为页(page) 的整倍数.

页:
页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页(在许多操作系统中，页得大小通常为(4k)，主存和磁盘以页为单位交换数据。
文件系统及数据库系统的设计者利用了磁盘预读原理，将-一个节点的大小设为等于- 一个页，这样每个节点只需要一次 I/0就可以完全载入。

4.30"2-3树"的插入原理

2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。2-3树不是二叉树，其节点可拥有3个孩子。不过，2-3树与满二叉树相似。若某棵2-3树不包含3-节点，则看上去像满二叉树，其所有内部节点都可有两个孩子，所有的叶子都在同一级别。另一方面，2-3树的一个内部节点确实有3个孩子，故比相同高度的满二叉树的节点更多。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数，即至少有2^h-1个节点。换一个角度分析，包含n的节点的2-3树的高度不大于log2(n+1)。

4.31"B树"和"B+树"原理

B树也是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，我们把树中结点最大的孩子数目称为B树的阶。通常记为m。

一棵m阶B树或为空树，或为满足如下特性的m叉树：

• 树中每个结点至多有m棵子树。（即至多含有m-1个关键字) (“两棵子树指针夹着一个关键字”)
• 若根结点不是终端结点，则至少有两棵子树。(至少一个关键字)
• 除根结点外的所有非叶结点至少有 ⌈m/2⌉棵子树。（即至少含有⌈m/2⌉-1个关键字）
• 所有非叶结点的结构如下：
• 所有的叶子结点出现在同一层次上，不带信息。(就像是折半查找判断树中查找失败的结点)

B+树是应文件系统所需而产生的一种B-tree的变形树。

一棵m阶的B+树和m阶的B树的异同点在于：

• 有n棵子树的结点中含有n-1 个关键字；
• 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。
• 所有的非终端结点可以看成是部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)

B+的特性：

1).所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2).不可能在非叶子结点命中；

3).非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4).更适合；

B+树的优势：

1.单一节点存储更多的元素，使得查询的IO次数更少。

2.所有查询都要查找到叶子节点，查询性能稳定。

3.所有叶子节点形成有序链表，便于范围查询

磁盘中B+树索引：

局部性原理与磁盘预读，预读的长度一般为页（page）的整倍数，（在许多操作系统中，页得大小通常为4k）

数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入，(由于节点中有两个数组，所以地址连续)。

5.1哈希表概述

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

5.2散列函数的设计

散列函数的设计

• 直接定址法
• 数字分析法
• 平方取中法
• 取余法
• 随机数法

哈希表的底层结构就是一个,数组的长度即哈希表的长度,数组中的每个(也叫桶)存放的是一条,链表中的每个节点用来存放元素。即一个数组的每个数组元素是一条链表,链表的每个节点存放元素,可以将数组的每个元素看做桶,桶里面可以有多个元素。桶里元素直接的数据结构是链表。

5.3散列冲突的解决方案

开放地址法

• 线性探测法
• 二次探测法
• 再哈希法

链地址法

6.1图结构概述

顶点

图中的数据元素，我们称之为顶点，图至少有一个顶点（非空有穷集合）

对应到好友关系图，每一个用户就代表一个顶点。

边

顶点之间的关系用边表示。

对应到好友关系图，两个用户是好友的话，那两者之间就存在一条边。

度

度表示一个顶点包含多少条边，在有向图中，还分为出度和入度，出度表示从该顶点出去的边的条数，入度表示进入该顶点的边的条数。

对应到好友关系图，度就代表了某个人的好友数量。

无向图和有向图

边表示的是顶点之间的关系，有的关系是双向的，比如同学关系，A是B的同学，那么B也肯定是A的同学，那么在表示A和B的关系时，就不用关注方向，用不带箭头的边表示，这样的图就是无向图。

有的关系是有方向的，比如父子关系，师生关系，微博的关注关系，A是B的爸爸，但B肯定不是A的爸爸，A关注B，B不一定关注A。在这种情况下，我们就用带箭头的边表示二者的关系，这样的图就是有向图。

无权图和带权图

对于一个关系，如果我们只关心关系的有无，而不关心关系有多强，那么就可以用无权图表示二者的关系。

对于一个关系，如果我们既关心关系的有无，也关心关系的强度，比如描述地图上两个城市的关系，需要用到距离，那么就用带权图来表示，带权图中的每一条边一个数值表示权值，代表关系的强度。

6.2图结构代码实现

图代码实现

• 顶点用数组表示
• 邻接矩阵用二维数组

6.3图遍历的原理

深度优先搜索算法（DFS）：

• 我们假设初始状态所有顶点都没被访问，然后从每一顶点v出发，先访问该顶点
• 然后依次从他的各个未访问的邻接点出发，深度优先遍历图，直到图中所有和v相通的顶点都被访问到。
• 遍历完之后，还有其他顶点没有被访问到，则另选一个未被访问的定点作为起始点。
• 重复上述过程，直到所有顶点 都被访问完为止。
  

广度优先搜索算法（BFS）：

• 从图中的某一顶点出发，在访问了v之后依次访问v的各个没有访问到的邻接点
• 然后分别从这些邻接点出发依次访问他们的邻接点，使得先被访问的顶点的邻接点先与后被访问顶点的邻接点被访问，知道图中所有已被访问的顶点的邻接点都被访问到。

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.bianchenghao6.com/h6javajc/19617.html