首页  思维导图  详情

数据结构&算法

2021-03-30 10:18:48   0  举报





AI智能生成

为你推荐

查看更多



Java_数据结构和算法

数据结构与算法

数据结构

常见的数据结构与常见的排序算法，每个都有文字描述和代码。内容都是根据我自己的学习和了解进行编写的。

数据结构与算法

作者其他创作

大纲/内容

算法就是为了解决某一个特定问题而规定的一系列的操作，是一组有序的指令的集合

数据结构与算法就是一对好兄弟

一个算法有0个或多个输入

输入

至少有一个输出，没有输出的算法没有意义

输出

算法中执行指令的个数应该是有限的，执行有穷的步骤后能结束

有穷性

对于特定的合法输入它的输出应该是唯一的

确定性

算法能够实现，并且在有限的时间内完成

可行性

算法的五个特性

没有语法错误，对于合法的输入能够产生满足要求的输出，对于特定的输入也能够产生正确的输出

正确性

算法另一个目的是为了交流，方便阅读

可读性

对于不合理的要求，能够给出合理的提示信息，而不是崩溃

健壮性

时间效率高与存储空间小

评价一个算法性能的优劣，实际上就是评价算法的资源占用率计算机最重要的资源就是时间和空间

使用时间复杂度衡量程序运行需要的时间

使用空间复杂度衡量程序所占内存的大小

算法的评价

算法的设计要求

基本概念

程序中语句执行的次数

编程实现这个算法，统计所需要的时间

事后统计

采用渐近时间复杂度分析估算

事前分析

计算机程序运行时间的方法

简称时间复杂度。在进行算法分析时，语句总的执行次数，记作T(n)，是关于问题规模n的函数，分析T(n)随着问题规模n的变化情况，确定T(n)的数量级

T(n) = O(f(n))，表示锁着问题规模n的增大，算法执行的时间增长率和f(n)函数的增长率相同，f(n)是问题规模n的一个函数

随着输入规模n的增大，T(n)增长越慢的算法越好

渐近时间复杂度

计算次数为：2n + 1时间复杂度为：O(n)

忽略常数项

计算次数为：n^2 + n时间复杂度为：O(n^2)

忽略低次项

随着问题规模的增大，常数项和低次项对于结果的影响非常小，所以常数项和低次项都可以忽略

可以忽略的原因

时间复杂度计算的一些原则

时间复杂度

计算1+2+3+...+n的累加和，高斯算法

public static void sum2(int n){ int sum = n * (n + 1) / 2; System.out.println(\"高斯sum = \" + sum); }

总共执行了1次

顺序执行，时间复杂度：T(n) = O(1)，是常数阶

算法1

计算1+2+3+...+n的累加和

public static void sum1(int n){ int sum = 0; for (int i = 1; i <= n; i++) { sum += i; } System.out.println(\"for循环sum = \" + sum); }

总共执行了 n + 1 次，1是常数对结果的影响不大，所以可以省略

时间复杂度：T(n) = O(n)，是线性阶

算法2

public static void method1(int n){ int i = 1; int count = 0; while (i <= n){ i = i * 2; count++; } System.out.println(\"count==\" + count); }

解得x如上，其中：常数2对结果影响不大可以忽略，底数2也可以忽略

时间复杂度：T(n) = O(logn)

算法3

public static void method2(int n){ int count = 0; int s = 0; while (s <= n){ count++; s = s + count; } System.out.println(\"count==\" + count); }

时间复杂度：T(n) = O(n^2)

算法4

public static void method3(int n){ int count = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { count++; } } System.out.println(\"count=\" + count); }

总共执行了n*n次

算法5

时间复杂度为：O(n)

数组的平均数

图解

常见时间复杂度的增长率

时间复杂度分析

为了求解某一问题，在执行操作期间所需要的存储空间大小，不包含用来存储输入所需要的空间

空间复杂度就是算法需要用到的额外空间

记作：S(n) = O(f(n))

结论：算法的空间复杂度是以时间复杂度为上限的

空间复杂度

引自马士兵老师

常见排序列表图

选泡插，快归堆希统计基，恩方恩老恩一三，对恩加 K恩乘 K，不稳稳稳不稳稳，不稳不稳稳稳稳！

解析：恩方：对应选、泡、插的平均时间复杂度恩老恩：对应快、归、堆的平均时间复杂度一三：对应希尔排序的平均时间复杂度对恩加K：对应桶排序和计数排序的平均时间复杂度恩乘K：对应基数排序的平均时间复杂度

排序算法宋词记忆法(引用自马士兵老师)

两个相等的数字在数组排完顺序之后，它们的相对顺序可能会变化

算法的稳定性

验证一步走一步

多打印中间结果

由简单到复杂

没思路时先细分

先局部后整体

变量更名

语句合并

边界处理

先粗糙后精细

如果很难下手，就把每个小模块都封装成方法，慢慢来

写算法的原则

算法的验证

算法思想： sum = 1 + 2 + 3 + 4 + 5 + ... + 100 sum = 100 + 99 + 98 + 97 + 96 + ... + 1 每一项对应相加也就是二倍的sum 2倍的sum = 101 + 101 + 101 + 101 + ... + 101一共有100个101 2 * sum = 100 * 101解得： sum = 100 * 101 / 2即： sum = n * (n + 1) / 2

1.高斯算法

在一个数组中，从第一个位置开始在数组中寻找最小的数字，找到最小的数字之后和第一个位置上的数字进行交换，换完之后第一个位置就是最小的数字了，然后第一个位置不参与排序了，再从第二个位置开始在数组中寻找最小的数字，找到后和第二个位置上的数字交换，以此类推。。。。。。

怎么找最小的数：每次将开始位置设置为最小数，如果这个最小数大于下一个位置上的数字，将下一个位置上的数设置为最小数如果比下一个位置上的数字小，那么最小数还是它本身全部比较完之后，将最小数的位置和开始位置进行交换，这样就、完成了一次排序

代码

代码优化(每次找到最小值和最大值，对头和尾都进行交换)

2.选择排序

整体思想：将数组中最大的数字像泡泡一样浮到最后一个位置上去，以此类推完成排序

每次都从第一个数字开始，两两比较，寻找最大的数字如果前面的数字比后面的数字大，就交换位置，如果前面的数字比后面的数字小，就不用交换位置，继续下一组的比较。比较原则： 0 1 1 2 2 3 3 4 ......

例：对9 6 1 3 5 进行冒泡排序

代码优化(如果一次交换都没发生的话，证明数组已经排序完成了，这样就是最好的情况O(n)了)

3.冒泡排序

主要思想是需要比出来小的，如果前面的比后面的大，就换位置

从第二个位置上的数开始比较，每次都只会跟\"前面\"的数字进行比较，如果比前面的数字小就进行交换，以此类推，直到找到合适的位置才结束这个数的排序例如： 9 6 1 3 5 从第二个位置上的数字6开始向前比较，6比9小所以6和9交换位置，第一次排序结束，得到 6 9 1 3 5 从第三个位置上的数字1开始向前比较，1小于9所以1和9交换位置，得到 6 1 9 3 5 1再跟前面的6进行比较，1小于6所以1和6交换位置，第二次排序结束，得到 1 6 9 3 5 ......直到排完最后一个

对9 6 1 3 5进行排序

将当前开始排序的数字存入到一个临时变量中，最后直接插入到需要插入的位置，提前将后面的所有数字都后移

修改算法(用临时变量记录标记项，去掉swap方法)

4.插入排序

改进的插入排序，比插入排序的效率高一些

相对插入排序来说，多了一个间隔的概念，先确定一个间隔，每这个间隔的数字成一组，每一组进行相对位置上的排序（例如：这一组的下标是1 4 7 10 ，这组数排完序之后，下标还是1 4 7 10），然后向后推移，找下一组所有组都排完了之后，开始减小间隔，直至间隔为1排完一遍之后，完成了排序。例如： (9 6 3) (5 7 1) (4 2 8) 以3为间隔分成三组 9 5 4 、6 7 2 、3 1 8，三组分别排完序之后： 4 5 9 、2 6 7 、1 3 8，重新组成的数组为 (4 2 1)( 5 6 3)( 9 7 8)，即以间隔为3的排序完成，下来可以进行间隔为2的排序，然后按照间隔为1排序（插入排序）排序完成

间隔为4的排序，下图接

间隔为2和1的排序

间隔大的时候移动的次数少间隔小的时候移动的距离短

1.最常见的，arr.length / 2

寻找最大间隔采用 int h = 1; while (h <= arr.length / 3){ h = h * 3 + 1; }除以3的原因是，如果大于1/3的话，3*h+1就大于数组的长度了

2.Knuth序列，比/2效率高

间隔的选择

5.希尔排序

主要的思想就是递归

如果数组没有排好顺序首先对数组进行一分为二，如果想对这两半进行归并，必须要求子数组必须排好如果想让子数组排好，必须对子数组分成两半进行归并，............. 直到不能分为止（子数组中有两个或者一个），然后开始从最小的子数组开始逐步归并

三个指针，新建一个新的数组，比较情况： 1和2，1比2小将1放入到新数组中 4和2，2比4小将2放入到新数组中 4和3，3比4小将3放入到新数组中 4和5，4比5小将4放入到新数组中 6和5，5比6小将5放入到新数组中 ................

第一种情况（前半截和后半截都是有顺序的）

给merge方法添加三个参数左起点，右起点，右边界目的是为了给子数组进行排序

图解中仅对第一次分组后的前一半进行的画图解释

第二种情况（使用到递归）

TimSort(改进的归并排序)

6.归并排序

在数组中先随便找一个数字，作为轴，比轴矮的排到前面，比轴高的排到后面，此时，数组就被分成了两部分，在前半部分和后半部分，分别再找轴，再排。重复以上的操作，直到分割完之后剩下一个元素的时候，开始返回(递归的结束条件)。

核心思想：依照每个轴排完之后，轴的位置就是这数字的位置，不用变了，再找下一个轴，以此类推

部分图解

例如：对1，4，6，9，10，2，3，5，8，7排序

选定每个数组中最后的数字作为轴，数组从前往后开始遍历，如果比轴小，就不动，如果大于轴承，就和轴前面的数字进行交换，用换回来的数字再跟轴比，如果比轴小，就不动，如果大于轴，继续跟轴前面没有交换过的数字进行交换以此类推

描述

定义一个索引值 == arr.length - 2，这个值代表的是倒数第二个数字的下标，如果“排序的索引值”+ 1 == 这个索引值时，将最后位置的数和这个索引值上的数进行交换，即这次的排序完成

结束条件

一次比较的过程

例如：对1 6 9 10 2 5 8 7进行排序

第一种(以每个数组的最后一个位置为轴)

还是以数组的最后为轴，从左往右找第一个比轴大的数，从右往左找第一个比轴小的数，让这两个数字直接做交换

以7为轴的第一次交换

一次的比较过程

完整的过程图解

精致代码

第二种(两边同时找，找到之后直接做交换)

思想，每次找两个轴，将数组分成三个区域，******大前提：第一个轴比第二个小******第一个区域存放小于第一个轴的数，第二个区域存放大于第一个轴小于第二个轴的区域，第三个区域存放大于第二个轴的数

算出数组长度的1/7（记做A）找到数组的终点，减去A，找到第一个数再减去A，找到第二个数再减去A，找到第三个数再减去A，找到第四个数再减去A，找到第五个数将这五个数排好顺序（从小到大）*****如果这五个数有一个相等，就用单轴快排*****如果这五个数都不相等，就选第二个和第四个数作为两个轴，使用双轴快排

找轴

图解（这里选定数组的第一个和最后一个数为轴）

第三种(Java内部使用的双轴快排)

7.快速排序

计数排序是桶排序思想中特殊的一种情况

非比较排序

适用场景：量大但是范围小例如：企业中万名员工年龄排序快速得知高考名次

创建一个新的数组用来计数（全部初始化为0），这个数组的长度就是上述场景中范围的长度，数组中对应的索引就是在范围中对应的数字

开始遍历数据：依次取得范围中的数字，当作数组的索引，给对应数组下标上的数加1

创建一个新的数组，和原来的数组一样长。将计数数组按照顺序存入

说白了就是记录了每个数出现了多少次

职务分为三个级别：A、B、C

张三 A李四 B王五 C赵六 B陈七 A

创建新的数组，和原来的数组一样长int[] newArr = new int[原员工数组的长度]

代码(存在问题，不稳定，而且如果从100~150开始就浪费了(因为索引都是从0开始的))

找出范围的最小值，数组中全部减去最小值，最后给新数组中每个数再加上最小值

解决浪费

采用累加数组

解决不稳定

举例：公司中每个员工的职务（这个例子没啥意义，就是这种思想）

8.计数排序

筒思想的一种

多关键字排序

排数字的时候，最大的数字有几位，就排几次

421 240 115 532 305 430 124

将每个数字的个、十、百位都可以当作是一种关键字

第一次：以个位上的数进行排序得到：240 430 421 532 124 115 305

第二次：在第一次排序完的基础上，以十位上的数排序得到：305 115 421 124 430 532 240

第三次：在第二次排序完的基础上，以百位上的数排序得到：115 124 240 305 421 430 532

如果再有千位万位，以此类推

代码实现

例如：对一组数进行排序

实际中的例子：员工排序，先排年龄，再排工龄、再排身高体重.....

9.基数排序

给小数排序

也可以给小数同时乘以100，全部变成整数，先进行计算，最后再统一除以100输出

先用桶排序，分好，再用归并排序将每个桶中进行排序

例：采用桶+插实现的例子

10.桶排序

基本思想（1）将待排序序列构造成一个大顶堆（2）此时，整个序列的最大值就是堆顶的根节点（3）将其与末尾元素进行交换，此时末尾就为最大值（4）然后将剩余n - 1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到了一个有序序列了

具体实施方法：1.将无需序列构建成一个堆，根据升序降序需求，选择大顶堆或者小顶堆这里采用升序的思路2.自左向右，自上而下，先找到最后一个非叶子结点。比较它的两个子结点，再拿子结点中大的数组和这个非叶子结点进行比较，如果非叶子结点小，就换。继续找下一个倒数的非叶子结点，以此类推，知道所有的非叶子结点都找完3.将堆顶元素与末尾元素交换，将最大元素(堆顶的元素)与末尾元素进行交换。这个数不再参与下一次的运算（排出了一个数）3.以此类推，反复执行，直到没有非叶子结点，递归结束

初始化数组

第一次排序完成后，9就不参与运算了。以此类推

详细图解

例：对4 6 8 5 9进行排序

11.堆排序

冒泡：基本不用，太慢

选择：基本不用，不稳

插入：样本小且基本有序的时候效率比较高

算法总结

常见算法汇总

算法

描述客观事物的数值、字符，能输入到计算机并且被计算机处理的各种符号的集合

数据就是信息在计算机中的表示

数据

数据元素就是数据的基本单位

在计算机程序中，通常把数据元素作为一个整体进行处理

例如：描述学生信息的一条数据记录就是一个数据元素描述一个点坐标的信息就是一个数据元素数据元素通常由若干个数据项组成

例如：描述学生信息中的姓名、学号、成绩都是数据项点坐标中的横坐标、纵坐标就是数据项

数据元素

一组相同性质的数据元素的集合

例如：学校中所有学生的集合就是数据对象平面坐标系中所有的点的集合就是数据项

数据对象

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

数据结构就是数据元素之间的关系

数据结构分为逻辑结构和物理结构

集合：数据仅仅属于同一个集合，他们之间没有其他的相互关系

线性：描述一对一的关系

树形：描述一对多的关系

图形：描述多对多的关系

数据的逻辑结构有四种

D：数据元素的集合

S：D中元素之间的关系的集合

span style=\"font-size: inherit;\

在set集合中，数据元素除了属于同一个集合外，不存在其他的关系，这就是集合的结构

例1：集合

在数据结构linearity中，数据元素是有序的，有一个被称为“第一个”的数据元素（01）还有一个被称为“最后一个”的元素（03），除了第一个元素外，其他每个元素都有一个直接前驱元素除了最后一个元素外，其他每个元素都有一个直接后继的元素

数据元素之间是一对一的关系

例2：线形

在tree数据结构中，除了第一个元素（01）外，每个元素都有且只有一个直接前驱元素，每个元素可以有多个直接后继元素

数据元素之间是一对多的关系

例3：树形

在graph数据结构中，每个元素可以有多个直接前驱元素，每个元素也可以有多个直接后继元素

数据元素之间是多对多的关系

例4：图形

数据的逻辑结构一般采用二元组的形式定义

数据的物理结构就是逻辑结构在计算机中的存储表示

顺序存储

链式存储

两种存储表示形式

顺序存储就是使用一块连续的存储空间，数据之间紧挨在一起数据的前驱和后继的关系可以通过数据元素在内存中相对位置反映出来

数据元素的存储位置不是连续的，每个元素中都会保存下一个元素的存储位置

数据的物理结构

数据结构

1.基本概念

abstract data type 简称：ADT

由一组数据模型及该模型上的一组操作组成

抽象数据类型一半使用一个三元组表示：ADT =（D，S，P）D：数据对象S：D上的关系P：D上的操作

在定义抽象数据类型时，可以使用以下的格式：ADT 抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 数据操作：<基本操作的定义>}

抽象数据类型可以对应一个Java类，数据对象与数据关系可以通过类的成员变量来存储和表示，数据操作可以使用方法来实现

2.抽象数据类型

生活中的线性结构：排队

注：凡是涉及到索引的方法，都要先判断索引是否越界

一般来说抽象数据类型都会抽象成一个接口

线性表的抽象数据类型

使用Java中的接口来表示ADT中的数据操作，在使用类完成抽象数据类型时，只要这个类实现接口即可完成抽象数据类型中定义的操作

package pers.chenjiahao.linearity.operator;/** * 通过接口定义一组线性表中的操作 */public interface MyList { int getSize(); // 返回线性表中的元素的个数 boolean isEmpty(); // 判断线性表是否为空span style=\"font-size: inherit;\

MyList接口

线性表的顺序存储就是使用一组地址连续的存储空间来依次存储线性表中的元素以数据元素在计算机内存的地址相邻性来表示数据元素之间的关系在Java中可以使用数组来存储线性表中的数据元素，数组就是一块连续的存储空间

插入元素

删除元素

原理

创建一个MyArrayList类，实现MyList接口

完整代码

// 返回元素的个数 @Override public int getSize() { return size; }

1.getSize()

// 判断线性表是否为空@Override public boolean isEmpty() { return size == 0; }

2.isEmpty()

// 判断当前线性表中是否包含元素e @Override public boolean contains(Object e) { return indexOf(e) >= 0; }

4.contains(Object e)

// 返回元素e在线性表中第一次出现位置的索引值，如果不存在返回-1 @Override public int indexOf(Object e) { // 判断e是否为空 if (e == null){ // 如果线性表中，用户可能添加了null for (int i = 0; i < size; i++) { if (elements[i] == null){ return i; } } }else { // 遍历数组 for (int i = 0; i < size; i++) { if (e.equals(elements[i])){ return i; } } } // 能走到这里说明元素不存在 return -1; }

5.indexOf(Object e)

// 在线性表中删除第一个与e相同的元素 @Override public Object remove(Object e) { // 获取e在线性表中的索引值 int index = indexOf(e); if (index < 0){ // 线性表中不存在元素e return null; } return remove(index); }

6.remove(Object e)

// 在线性表中删除指定索引值的元素 @Override public Object remove(int i) { // 判断i是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + \"越界\"); } // 把要删除的元素保存起来 Object old = elements[i]; // 把i+1开始的元素，依次前移 for (int j = i; j < size - 1; j++) { elements[j] = elements[j + 1]; } // 把最后的元素放置为null elements[size - 1] = null; // 修改元素的个数 size--; return old; }

7.remove(int i)

// 返回指定位置的元素 @Override public Object get(int i) { // 判断是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + \"越界\"); } return elements[i]; }

9.get(int i)

// 重写toString方法 @Override public String toString() { // 把线性表中每个元素连接起来，便利数组中已添加的元素 StringBuilder sb = new StringBuilder(); sb.append(\"[\"); for (int i = 0; i < size; i++) { sb.append(elements[i]); if (i < size - 1){ sb.append(\

12.toString()

13.private void expandSpace()

各个功能模块代码

测试类

顺序存储是使用数组实现的，数组可以通过索引值快速访问每个元素

优点

在插入/删除元素时，需要移动大量的元素

当线性表长度变化较大时，很难确定存储空间的容量

缺点

特点

适用于元素的插入/删除操作较少，主要是查询操作

应用场景

线性表的顺序存储

单向链表，也叫单链表

每个存储单元至少有两个域，一个用来存储数据，一个用来保存下个存储单元的引用

不需要移动元素

插入和删除元素

创建一个MySingleLink类，实现MyList接口

// 判断线性表是否为空 @Override public boolean isEmpty() { return size == 0; }

// 判断线性表中是否包含指定的元素 @Override public boolean contains(Object e) { return indexOf(e) >= 0; }

// 返回元素e在线性表中第一次出现的索引值 @Override public int indexOf(Object e) { // 保存元素e的索引值 int index = 0; Node pNode = head; while (pNode != null){ if (e == null && pNode.data == null){ return index; }else if (e != null && e.equals(pNode.data)){ return index; } index++; pNode = pNode.next; } return -1; }

// 从线性表中删除第一个与e相同的元素 @Override public Object remove(Object e) { // 找到元素e第一次出现的位置 int index = indexOf(e); if (index < 0){ // 元素不存在 return null; } return remove(index); }

// 从线性表中删除指定索引的元素 @Override public Object remove(int i) { // 判断是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + \"越界\"); } Node pNode = head; // 删除头结点(i为0时候) if (i == 0){ head = head.next; size--; return pNode.data; // 返回删除头结点的数据 } // 删除的是中间的元素，找到i-1结点 for (int j = 1; j < i; j++) { pNode = pNode.next; } // 保存删除结点的数据 Object old = pNode.next.data; // 将i - 1 结点的next指针与改变一下(让i-1的next指向i+1结点，相当于删除了i) pNode.next = pNode.next.next; size--; return old; }

// 返回线性表中i索引值的元素 @Override public Object get(int i) { // 判断是否越界 Node pNode = getNode(i); return pNode.data; }

// 重写toString()方法 @Override public String toString() { // 把链表中各个结点的数据与连接起来 StringBuilder sb = new StringBuilder(); sb.append(\"[\"); Node pNode = head; while (pNode != null){ sb.append(pNode.data); // 使用逗号分割 if (pNode.next != null){ sb.append(\

// 定义一个方法来检查索引值是否越界 private void checkIndex(int i){ if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + \"越界\"); } }

13.private void checkIndex(int i)

// 定义一个方法返回i索引值的元素 private Node getNode(int i){ if (i < 0 || i>= size){ return null; } if (i == 0){ return head; } // 找到i结点 Node pNode = head; for (int j = 0; j < i; j++) { pNode = pNode.next; } return pNode; }

14.private Node getNode(int i)

*****15.private class Node

单向链表

双向链表中，扩展了结点的结构，每个结点除了存储数据外，通过一个引用指向后继结点，再定义一个引用指向前驱结点

创建一个MyDualLinkedList类，实现MyList接口

// 判断链表是否为空 @Override public boolean isEmpty() { return size == 0; }

// 判断链表中是否包含指定的元素e，如果存在返回true @Override public boolean contains(Object e) { return indexOf(e) >= 0; }

// 判断元素e在链表中第一次出现的位置，如果不存在该元素，返回-1 @Override public int indexOf(Object e) { // 保存元素e在链表中的索引值 int i = 0; // 依次遍历链表中的各个结点，比较结点的元素与指定的e是否一样 if (e == null){ for(Node pNode = first; pNode != null ; pNode = pNode.next){ if (pNode.data == null){ return i; } i++; } }else{ for(Node pNode = first; pNode != null ; pNode = pNode.next){ if (e.equals(pNode.data)){ return i; } i++; } } return -1; }

// 从链表中删除指定的元素 @Override public Object remove(Object e) { // 先找到元素e对应的索引值 int index = indexOf(e); if (index < 0){ return null; } return remove(index); }

// 从链表中删除指定索引值的元素，并返回删除的元素 @Override public Object remove(int i) { // 判断索引值是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + \"越界\"); } // 找到i对应的结点 Node pNode = getNode(i); // 删除结点的前驱 Node prevNode = pNode.prev; // 删除结点的后继 Node nextNode = pNode.next; // 如果前驱结点为null if (prevNode == null){ // 删除的就是头结点 first = nextNode; }else { // 将prevNode中的next指向nextNode prevNode.next = nextNode; } // 如果后继节点为null if (nextNode == null){ // 删除的就是尾结点 last = prevNode; }else { // 将nextNode中的prev指向prevNode nextNode.prev = prevNode; } // 修改元素的个数 size--; return pNode.data; }

// 返回指定索引值的元素 @Override public Object get(int i) { // 检查索引值是否越界 checkIndex(i); // 找到索引值为i的结点 return getNode(i).data; }

// 重写toString @Override public String toString() { // 依次遍历各个节点，把元素转换为字符串 StringBuilder sb = new StringBuilder(); sb.append(\"[\"); for (Node node = first; node != null ; node = node.next) { sb.append(node.data); // 元素之间使用逗号分割 if (node != last){ sb.append(\

// 校验是否越界的方法 private void checkIndex(int i){ if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + \"越界\"); } }

// 返回索引值对应的结点 private Node getNode(int i) { Node pNode = first; for (int j = 0; j < i; j++) { pNode = pNode.next; } return pNode; }

addFirst(Object e)

addLast(Object e)

// 删除第一个元素，删除头元素 public Object removeFirst(){ return remove(0); }

removeFirst()

// 删除最后一个元素，删除尾元素 public Object removeLast(){ return remove(size - 1); }

removeLast()

// 返回头元素 public Object getFirst(){ return get(0); }

getFirst()

// 返回尾元素 public Object getLast(){ return get(size - 1); }

getLast()

在链表中，经常会有针对头元素与尾元素的操作

双向链表

线性表的链式存储

线性表的基本操作：查询、插入、删除

直接通过索引值访问每个元素，实现了数组元素的随机访问

每次都要从头结点或尾结点开始依次查找

查询

需要移动大量的元素

只需要修改结点的前驱和后继指针即可，不需要移动元素

插入与删除

优先选择顺序存储

查询操作多

优先选择链式存储

插入与删除操作多

总结

时间上

预先分配一块连续的存储空间，在使用过程中会出现闲置的空间

存储空间是动态分配的，不会浪费空间

如果线性表的长度经常变化，优先选择链式存储

如果线性表的长度变化不大，优先选择顺序存储

空间上

顺序存储与链式存储实现线性表的比较

3.线性表

栈与队列，从逻辑结构上看，也是线性结构，是操作受限的线性结构

栈(Stack)，也称堆栈，是一种操作受限的线性表。

栈只允许在线性表的一段进行插入/删除等操作，不允许在其他位置插入/删除

如果栈中没有数据元素称为空栈

向栈中插入元素，称为进栈/入栈/压栈，从栈中删除元素称退栈/出栈/弹栈

栈的插入/删除操作只允许在栈顶进行，后进栈的元素必定先出栈，称为先进后出或后进先出

堆栈抽象数据类型

package pers.chenjiahao.linearity.stackoperator;/** * 定义接口，定义栈的操作 */public interface MyStack { int getSize(); // 判断栈的长度 boolean isEmpty(); // 判断栈是否为空 void push(Object e); // 压栈，入栈 Object pop(); // 弹栈，出栈 Object peek(); // 返回栈顶元素}

MyStack接口

顺序栈可以通过数组存储堆栈的元素

堆栈的操作都在栈顶完成，选择数组中索引值较大的一端作为栈顶

创建一个MyArrayStack类，实现MyStack接口

package pers.chenjiahao.linearity.arraystack;import pers.chenjiahao.linearity.stackoperator.MyStack;/** * 栈的顺序实现 */public class MyArrayStack implements MyStack { // 定义数组来保存栈的元素 private Object[] elements; // 栈的默认容量 private static final int DEFAULT_CAPACITY = 16; // 栈顶指针 private int top; // 无参构造中，对数组默认初始化 public MyArrayStack() { elements = new Object[DEFAULT_CAPACITY]; } // 有参构造中，指定栈的初始化大小 public MyArrayStack(int initialCapacity) { elements = new Object[initialCapacity]; } // 返回元素的个数 @Override public int getSize() { return top; } // 判断栈中是否为空 @Override public boolean isEmpty() { return top <= 0; } // 入栈/压栈 @Override public void push(Object e) { // 判断栈是否已满，如果已满，数组需要扩容 if (top >= elements.length){ // 定义一个更大的数组 Object[] newData = new Object[elements.length * 2]; // 将原来的数组的内容复制到大的数组中 for (int i = 0; i < elements.length; i++) { newData[i] = elements[i]; } // 让原来的数组名指向新的数组 elements = newData; } // 把元素存储到栈顶指针指向的位置 elements[top] = e; // 栈顶指针上移 top++; } // 出栈/弹栈 @Override public Object pop() { // 判断栈是否为空 if (top <= 0){ throw new StackOverflowError(\"栈已空\

// 返回元素的个数 @Override public int getSize() { return top; }

// 判断栈中是否为空 @Override public boolean isEmpty() { return top <= 0; }

// 入栈/压栈 @Override public void push(Object e) { // 判断栈是否已满，如果已满，数组需要扩容 if (top >= elements.length){ // 定义一个更大的数组 Object[] newData = new Object[elements.length * 2]; // 将原来的数组的内容复制到大的数组中 for (int i = 0; i < elements.length; i++) { newData[i] = elements[i]; } // 让原来的数组名指向新的数组 elements = newData; } // 把元素存储到栈顶指针指向的位置 elements[top] = e; // 栈顶指针上移 top++; }

3.push(Object e)

// 出栈/弹栈 @Override public Object pop() { // 判断栈是否为空 if (top <= 0){ throw new StackOverflowError(\"栈已空\"); } top--; // 栈顶指针下移 return elements[top]; }

4.pop()

5.peek()

// 重写toString()，从栈顶到占底输出 @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append(\"[\"); // 从栈顶到占地的顺序添加各个元素 for (int i = top - 1; i >= 0; i--) { sb.append(elements[i]); // 元素之间用逗号分割 if (i > 0){ sb.append(\

6.toString()

package pers.chenjiahao.linearity.arraystack.test;import pers.chenjiahao.linearity.arraystack.MyArrayStack;public class MyArrayStackTest { public static void main(String[] args) { // 创建栈 MyArrayStack stack = new MyArrayStack(); System.out.println(stack.isEmpty()); // true System.out.println(stack.getSize()); // 0 // 压栈 stack.push(\"aa\"); stack.push(\"bb\"); stack.push(\"cc\"); stack.push(\"dd\

顺序实现

使用链表作为栈的存储结构，有时也成为链栈

栈只允许在线性表的一端进行操作，可以选择链表的表头作为栈顶

第一个结点可以当作为栈底

不管是压栈还是弹栈，都要在链表的首结点进行

创建一个MyLinkStack类，实现MyStack接口

// 返回栈中元素的个数 @Override public int getSize() { return size; }

// 判断栈是否为空 @Override public boolean isEmpty() { return size == 0; }

// 出栈/弹栈 @Override public Object pop() { // 判断栈是否为空 if (size < 1){ throw new StackOverflowError(\"栈已空\"); } // 保存原来栈顶元素 Object oldData = top.data; // 后移栈顶指针 top = top.next; size--; return oldData; }

// 返回栈顶元素 @Override public Object peek() { // 判断栈是否为空 if (size < 1){ throw new StackOverflowError(\"栈已空\"); } return top.data; }

// 重写toString方法 @Override public String toString() { // 将链表中各个结点的数据给返回 StringBuilder sb = new StringBuilder(); sb.append(\"[\"); for (Node pNode = top; pNode != null; pNode = pNode.next){ sb.append(pNode.data); // 数据元素之间使用逗号分割 if (pNode.next != null){ sb.append(\

*****private class Node

package pers.chenjiahao.linearity.linkstack.test;import pers.chenjiahao.linearity.linkstack.MyLinkStack;public class MyLinkStackTest { public static void main(String[] args) { // 创建链栈 MyLinkStack stack = new MyLinkStack(); System.out.println(stack.isEmpty()); // true System.out.println(stack.getSize()); // 0 // 压栈 stack.push(\"ppp\"); stack.push(\"aaa\"); stack.push(\"xxx\"); stack.push(\"ooo\

链式实现

十进制转为别的进制

图解：十进制转为二进制

1.进制转换

假设表达式中包含三种括号：()、[]、{}，这三种括号可以任意嵌套

对于任意一个左括号都需要一个对应的右括号匹配，最早出现的右括号应该与最早出现的左括号匹配

读取整个表达式，如果是左括号就直接入栈，等待与它对应的右括号出现如果是右括号，则与当前栈顶的左括号判断是否匹配如果不匹配，说明表达式不合法如果是右括号，表示栈已空，表示不合法读完整个表达式，堆栈不空，表示有左括号没匹配上，表达式不合法；读完整个表达式，栈是空的表示所有括号都能匹配

算法思路

package pers.chenjiahao.linearity.stackapplication.bracketmatching;import pers.chenjiahao.linearity.arraystack.MyArrayStack;/** * 检测表达式中的括号是否匹配 */public class BracketMatch { public static void main(String[] args) { System.out.println(bracketMath(\"([{}])\")); // true System.out.println(bracketMath(\"([{{])\")); // false System.out.println(bracketMath(\"([{}}])\

2.检测表达式中括号是否匹配

先乘除后加减

先括号内，再括号外

从左到右进行运算

四则运算的规则

4+3+(6-10+2*3)*4

7+(6-10+2*3)*4

7+(-4+2*3)*4

7+(-4+6)*4

7+2*4

7+8

例：4+3+(6-10+2*3)*4

读取表达式

如果是操作数就存储到operand操作数栈中

操作符栈是空，直接入栈

当前操作符优先级高，操作符入栈

把操作符栈中的栈顶操作符与当前操作符进行优先级比较

如果是操作符

遍历完整个表达式，连个栈都不为空，依次弹出操作符栈中的操作符和操作数栈中的两个操作数进行计算，把结果再存储到操作数栈中

如果操作符栈不为空，或操作数栈中的数不止一个，则表达式错误

如果操作符栈为空，操作数栈中只有一个数字，返回这个数，即计算的答案

package pers.chenjiahao.linearity.stackapplication.calculateexpression;import pers.chenjiahao.linearity.arraystack.MyArrayStack;/** * 使用栈来计算算数表达式的值 */public class CalculateExpression { public static void main(String[] args) { String expression = \"4+3+(6-10+2*3)*4\

3.算术表达式的求值

栈的应用

栈

队列(Queue)简称为队，也是一种受限的线性表

只允许在线性表的一段进行插入，在另一端进行删除

插入数据的一端称为队尾(rear)

删除数据的一段称为队首(front)

向队列添加数据称为入队/进队，新入队的元素称为队尾元素

从队列中删除元素称为出队或离队，元素出队之后，它的后续元素称为新的队首元素

队列是先进先出的(FIFO)

队列抽象数据类型

package pers.chenjiahao.linearity.queueoperator;public interface MyQueue { int getSize(); // 返回元素的个数 boolean isEmpty();// 判断队列是否为空 void enQueue(Object e); // 入队 Object deQueue(); // 出队 Object peek();// 返回队首元素}

MyQueue接口

在队列的实现中，可以把数据设想为一个圆环，这种数组称为循环数组，用循环数组实现的队列称为循环队列

用front指针指向队首元素所在的单元，使用rear指针指向队尾元素所在单元的后一个单元

在元素入队时，将心如对的元素保存到rear指向的单元，然后rear指针后移

在元素出队时，将队首指针front指向的元素返回，然后front后移

少用一个存储单元，当队尾指针rear的下一个单元是队首指针front时，停止入队

(rear+1)%capacity==front时表示队列已满

front==rear时表示队列为空

图解：表示队列已满

第一种方式

增设一个变量表示队列为空还是满，通常使用size变量表示元素的个数

当size==0时队列为空

当size==capacity时表示队列已满

第二种方式

队列为空和队列已满的表示

创建一个MyArrayQueue类，实现MyQueue接口

package pers.chenjiahao.linearity.arrayqueue;import pers.chenjiahao.linearity.queueoperator.MyQueue;import pers.chenjiahao.linearity.queueoperator.exception.QueueEmptyException;/** * 队列的顺序存储实现 */public class MyArrayQueue implements MyQueue { // 定义数组存储队列中的元素 private Object[] elements; // 设置初始化容量的默认值 private static final int DEFAULT_CAPACITY = 8; // 队首 private int front; // 队尾 private int rear; // 元素的个数 private int size; // 无参构造 public MyArrayQueue() { elements = new Object[DEFAULT_CAPACITY]; } // 指定初始化容量的构造 public MyArrayQueue(int initialCapacity) { elements = new Object[initialCapacity]; } // 返回元素的个数 public int getSize(){ return size; } // 判断队列是否为空 public boolean isEmpty(){ return size == 0; } // 入队 public void enQueue(Object e){ // 如果队列已满，可以对数组扩容 if (size >= elements.length){ expandQueue(); } // 把元素存储到rear指针指向的单元 elements[rear] = e; // rear指针后移 rear = (rear + 1) % elements.length; // 元素加一 size++; } // 出队 public Object deQueue(){ // 如果队列为空 if (size <= 0){ // 抛出队列为空异常 throw new QueueEmptyException(\"队列为空\"); } // 队列不为空，把front指向的元素返回 Object old = elements[front]; // 将front指针后移 front = (front + 1) % elements.length; // 元素个数-1 return old; } // 返回队首元素 public Object peek(){ // 队列为空，抛出异常 if (size <= 0){ // 抛出队列为空异常 throw new QueueEmptyException(\"队列为空\

// 返回元素的个数 public int getSize(){ return size; }

// 判断队列是否为空 public boolean isEmpty(){ return size == 0; }

// 入队 public void enQueue(Object e){ // 如果队列已满，可以对数组扩容 if (size >= elements.length){ expandQueue(); } // 把元素存储到rear指针指向的单元 elements[rear] = e; // rear指针后移 rear = (rear + 1) % elements.length; // 元素加一 size++; }

3.enQueue(Object e)

// 出队 public Object deQueue(){ // 如果队列为空 if (size <= 0){ // 抛出队列为空异常 throw new QueueEmptyException(\"队列为空\"); } // 队列不为空，把front指向的元素返回 Object old = elements[front]; // 将front指针后移 front = (front + 1) % elements.length; // 元素个数-1 return old; }

4.deQueue()

// 返回队首元素 public Object peek(){ // 队列为空，抛出异常 if (size <= 0){ // 抛出队列为空异常 throw new QueueEmptyException(\"队列为空\"); } return elements[front]; }

private void expandQueue()

package pers.chenjiahao.linearity.arrayqueue.test;import pers.chenjiahao.linearity.arrayqueue.MyArrayQueue;import pers.chenjiahao.linearity.queueoperator.MyQueue;/** * 测试顺序队列 */public class MyArrayQueueTest { public static void main(String[] args) { MyQueue queue = new MyArrayQueue(); // 入队 queue.enQueue(\"a\"); queue.enQueue(\"b\"); queue.enQueue(\"C\"); queue.enQueue(\"d\"); // 返回队首元素 System.out.println(queue.peek()); // 出队 System.out.println(queue.deQueue()); System.out.println(queue.deQueue()); System.out.println(queue.deQueue()); System.out.println(queue.deQueue()); // System.out.println(queue.deQueue()); queue.enQueue(\"1\"); queue.enQueue(\"2\"); queue.enQueue(\"3\"); queue.enQueue(\"4\"); queue.enQueue(\"5\"); queue.enQueue(\"6\"); queue.enQueue(\"7\"); queue.enQueue(\"8\"); queue.enQueue(\"J\"); queue.enQueue(\"Q\"); queue.enQueue(\"K\"); }}

使用单向链表来实现队列

把链表的头部作为队首，把链表的尾部作为队尾

创建一个MyLinkQueue类，实现MyQueue接口

// 判断队列是否为空 @Override public boolean isEmpty() { return size == 0; }

// 出队 @Override public Object deQueue() { // 判断队列是否为空 if (size <= 0){ throw new QueueEmptyException(\"队列为空\"); } // 保存要出队的数据 Object old = front.element; // 指针下移 front = front.next; // 如果出队后队列为空，调整尾指针 if (front == null){ rear = null; } // 元素-1 size--; return old; }

// 返回队首元素 @Override public Object peek() { // 判断队列是否为空 if (size <= 0){ throw new QueueEmptyException(\"队列为空\"); } return front.element; }

private class Node

package pers.chenjiahao.linearity.linkqueue.test;import pers.chenjiahao.linearity.linkqueue.MyLinkQueue;import pers.chenjiahao.linearity.queueoperator.MyQueue;public class MyLinkQueueTest { public static void main(String[] args) { MyQueue queue = new MyLinkQueue(); System.out.println(queue.getSize()); System.out.println(queue.isEmpty()); queue.enQueue(\"a\"); queue.enQueue(\"b\"); queue.enQueue(\"c\"); System.out.println(queue.getSize()); System.out.println(queue.getSize()); System.out.println(queue.peek()); queue.deQueue(); System.out.println(queue.getSize()); System.out.println(queue.isEmpty()); }}

队列

4.栈与队列

树是由一个集合及该集合上的定义的一种关系构成的。集合中的元素称为树的结点，定义的关系称为父子关系，父子关系的树的结点之间建立一个层次结构。

树的递归定义：树是由n(n>=0)个结点组成的有限集当n=0时，称为空树；当n>0时，就是一颗非空树: （1）有且仅有一个特定的称为根的结点（root）; （2）当n>1时，其他结点可以分为m(m>0)个互不相交的有限集T1，T2...，其中每个有限集又是一颗树，称为根节点的子树(SubTree)

当n>0时，在非空树中，根节点是唯一的当m>0时，某个结点的子树是没有限制的，并且各个子树肯定是不相交的

树的定义

结点拥有的子树的数量称为结点的度(Degree)

度为0的结点称为叶子结点(Leaf)或终端结点，度不为0的结点称为分支结点或非终端结点

除了根结点外，分支结点也称为内部节点

树的度是树内各个结点中度的最大值

结点的子树的根称为该结点的孩子(Child)，相应的该结点称为孩子结点的双亲(Parent)结点或父结点

父子结点之间的连线是树的一条边，树种结点数等于树的边数+1（结点数=边数+1）

在树中，根结点没有双亲结点，其他结点都有并且只有一个父结点，每个结点可以有多个孩子结点

同一个双亲的孩子之间互称为兄弟(Sibling)

结点的祖先是从根结点到该结点所经过的分支上的所有的结点

以某结点为根的子树上的任一结点都称为该结点的子孙

结点的层次(Level)是从根结点开始，根为第一层，根的孩子为第二层，以此类推，注意：有人把层次的定义是从0开始的，即根为第0层

如果根结点在第i层，则其子树的根就在i+1层

双亲结点（父结点）在同一个层次上的结点互为堂兄弟，即DEF互为堂兄弟

树中结点的最大层次称为树的深度(Depth)或高度，当前树的高度是4

如果将树的结点的各个子树看作是从左到右有顺序的，不能互换的，则称该树为有序树，否则为无序树，如果不特殊说明，一般讨论的是有序树

树中所有结点最大度数为m的有序树称为m叉树

森林(Forest)是m(m>=0)棵互不相交的集合，对树的每个结点而言，其子树的集合就是森林，删去树的根就得到一个森林，反之，把森林加一个树的根就变成一棵树