数据结构与算法（Java语言版）课件全套 耿祥义 第1-14章 数据结构简介-经典算法思想

第1章数据结构简介2024/11/91主要内容逻辑结构物理结构算法与结构1.1逻辑结构逻辑结构是指有限多个节点（结点，顶点，元素）之间的逻辑关系，不涉及节点（结点，顶点，元素）在计算机中的存储位置。2024/11/92主要的逻辑结构有线性结构，树形结构，图结构和集合这四种结构。⒈线性结构2024/11/93在实际生活中，经常遇到具有线性结构的一组数据，比如，中国农历的二十四节气：立春、雨水、惊蛰、春分、清明、谷雨、立夏、小满、芒种、夏至、小暑、大暑、立秋、处暑、白露、秋分、寒露、霜降、立冬、小雪、大雪、冬至、小寒、大寒2024/11/94⒈线性结构2024/11/95⒈线性结构2024/11/96⒈线性结构2024/11/972024/11/982.

树结构

2024/11/992.

树结构用倒置的树形示意一个树2024/11/9102.

树结构一个树T=(A,R)

由多个互不相交的树构成2024/11/9112.

树结构树的每个结点至多有2个子结点，称这样的树是二叉树二叉查询树，特点是，每个结点上的值都大于等于它的左子树上的结点里的值、小于它的右子树上结点里的值。首先猜m是上面的二叉树的根结点中的数，如果猜测错误，反馈信息给你，你猜测的比根结点中的数大，那你就继续猜测这个数是当前结点的右子结点，如果告知你，你猜测的数不大于根结点中的数，那你就继续猜测这个数是当前节点的左子结点，依次类推，您可以较快的猜测到这个数。2024/11/9122.

树结构树的层从上至下，从0层开始根结点没有父结点，非根、非叶结点有且只有一个父结点，但有一个或多个子结点，叶结点有且只有一个父结点，但没有子结点。根据树结构的这个特点，可以把树的结点按层次分类：树的结点按层次分类，从根开始定义，根为第0层，根的子结点为第1层，以此类推。每一层上的结点只能和上一层中的至多一个结点有关系，但可能和下一层的0个或多个结点有关系。2024/11/9133.

图结构钢筋焊接起来的平面架中的焊点：a,b,c,d,e2024/11/9143.

图结构钢筋焊接起来的平面架中的焊点：a,b,c,d,e

这个图结构中，人们规定(a,b)和(b,a)是一样的（都代表同一根钢筋），即(a,b)和(b,a)都是没有方向的“标量”边，这样的图结构称作无向图2024/11/9153.

图结构当V×V的子集E满足下列①和②时，称E是V上的图关系，记作G=(V,E)

2024/11/9163.

图结构当V×V的子集E满足下列①和②时，称E是V上的图关系，记作G=(V,E)

对于G=(V,E)，如果(a,b)是边，那么默认(b,a)也就是边，并规定(a,b)边等于(b,a)边，这样规定的G=(V,E)是无向图，简称V是无向图，即无向图的边是没有方向的。无向图2024/11/9173.

图结构当V×V的子集E满足下列①和②时，称E是V上的图关系，记作G=(V,E)

如果(a,b)，(b,a)都是边，就规定(a,b)边不等于(b,a)边，这样规定的G=(V,E)是有向图，简称V是有向图，即有向图的边是有方向的。2024/11/9184.

集合集合A中的元素除了同属一个集合外，无其它任何关系，即关系集合是空集合，可表示为(A,∅)（∅是A×A的空子集）2024/11/919对于(A,R)，计算机程序在存储空间中存放集合A的节点（结点，顶点，元素）的形式，称为A的节点（结点，顶点，元素）的物理结构，也称为A的存储结构。1.2物理结构比如，对于一个线性表，可根据需要采用顺序存储（节点的物理地址是依次相邻的）或链式存储（节点的物理地址不必是相邻的）。常用的存储结构有顺序存储、链式存储和哈希存储等，有关细节见后续的章节，例如，第4章至第11章2024/11/920实施于集合上的算法，在其执行完毕后，必须保持集合的逻辑结构不变，比如，对于线性表，实施了增加或删除节点的操作后，要保证新的节点构成的集合仍然是线性结构，否则算法必须对当前的线性表的节点进行调整，使得当前线性表在逻辑上仍然是一个线性结构。1.3算法与结构有关细节见后续的章节，例如，第4章至第11章。算法的设计取决于数据的逻辑结构，而算法的实现依赖于数据的存储结构第2章算法复杂度2024/11/921主要内容●算法●算法的复杂度

●常见的复杂度2.1算法算法(algorithm)就是一个正确的计算过程，该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。2024/11/9222024/11/923算法的4个主要特性：2.1算法算法的4个主要特性是：●确切性：算法由语句组成，每个语句的功能是确切的。●输入数据：可以向算法输入多个或0个数据（方法可以有参数或无参数），即算法可以接收或不接收外部数据。●输出数据：算法可以给出明确的计算结果（方法的返回值）或输出若干数据到客户端以反映算法产生的效果。●可行性：基本操作都是在有限时间内被完成。所谓有限时间是指这个时值仅仅依赖于特定的硬件设施，不依赖于一个正整数n，即不会随着n的增加而增大。●确切性●输入数据●输出数据●可行性2024/11/924一个算法不能在有限的时间内结束，就不属于算法复杂度的研究的范畴，比如一个算法里出现的无限循环，就不再属于算法复杂度的研究的范畴了2.2复杂度算法，从执行到结束，涉及两个度量：一个是执行方法所消耗的时间，一个是执行方法所需要的内存空间。2024/11/925方法里声明的局部变量，包括参数都不归类到基本操作，即不是基本操作。2.2复杂度⒈基本操作一个基本操作是一个语句或一个运算表达式。一个基本操作是一个语句或一个运算表达式，而且必须是在有限时间内能被完成的计算步骤，其耗时仅仅依赖于特定的硬件设施，不依赖于一个正整数n，不会随着n的增加而增大。2024/11/926在计算算法执行的基本操作的总数时，要真对最坏的情况，即在某种条件下执行的基本操作的总数是最多的情况2.2复杂度3时间复杂度算法执行的基本操作的总数T(n)。算法的复杂度主要是度量随着n的增大，T(n)值的趋势。2024/11/927学习复杂度，记住一个通俗的道理：时间累加，空间不累加.2.2复杂度4复杂度比较2024/11/9282.3常见复杂度⒈O(1)复杂度算法中的基本操作被执行的总次数是一个常量，即不依赖一个正整数n、不会随着n的增加而增大，那么将算法的时间复杂度，记作O(1)。算法中的所占用的内存是一个常量，即所占内存不依赖一个正整数n、不会随着n的增加而增大，那么将算法的空间复杂度，记作O(1)。

例子1Max.javaExample2_1.java2024/11/9292.3常见复杂度1.O(1)复杂度

例子2Sum.javaExample2_2.java2024/11/9302.3常见复杂度2.O(n)复杂度

2024/11/9312.3常见复杂度2.O(n)复杂度例子3SumAndMult.java

Example2_3.java

2024/11/9322.3常见复杂度2.O(n)复杂度例子4ArrayMax.java

Example2_4.java

2024/11/9332.3常见复杂度2.O(n)复杂度例子5FindMissNumber.java

Example2_5.java

理论上知道，同一台计算机，执行“异或”运算要比“加减”运算快。所以，对于同一个算法，在复杂度相同的情况下，尽量使用速度快的基本操作。如果软件的需求不十分介意速度，选择的基本操作能使得的代码更简练、阅读性更好，那么也可以使用这样的基本操作。2024/11/9342.3常见复杂度3.2024/11/9352.3常见复杂度3.例子6Multi.java

Example2_6.java

2024/11/9362.3常见复杂度3.例子7BubbleSort.java

Example2_7.java

2024/11/9372.3常见复杂度4.

2024/11/9382.3常见复杂度4.例子8OutPutNumber.java

Example2_8.java

2024/11/9392.3常见复杂度5.

2024/11/9402.3常见复杂度5.例子9FindNumber.java

Example2_9.java

2024/11/9412.3常见复杂度5.例子10Euclidean.java

Example2_10.java

2024/11/9422.3常见复杂度6.

如果一个方法里又调用了其它方法，即一个算法又包含另外一个算法，那么该方法的复杂度将和它包含的方法复杂度有关，需合并考察复杂度。

2024/11/9432.3常见复杂度6.例子11DataInArray.java

Example2_11.java

2024/11/9442.3常见复杂度6.例子12GCDInArray.java

Example2_12.java

2024/11/9452.3常见复杂度7.复杂度比较

程序中大部分算法都是这些复杂度中之一，除非特别需要，后续章节不再给出每个方法的复杂度。复杂度的比较规则：第3章递归算法2024/11/946主要内容● 递归算法● 递归的复杂度● 问题与子问题● 递归与迭代● 多重递归● 经典递归● 优化递归递归算法是非常最重的算法，是很多算法的基础算法。递归算法不仅能使得代码优美简练，容易理解解决问题的思路或发现数据的内部的逻辑规律，而且具有很好的可读性。和排序算法不同，许多经典的排序算法已经是玲珑剔透、日臻完善，在许多应用中只要选择一种排序算法直接使用即可（见第4章和第12章），而对于递归算法，真正理解递归算法内部运作机制的细节、才能真对实际问题正确的使用递归算法或写出正确的递归算法。3.1递归算法递归算法是指一个方法在执行过程中又调用了自身、形成了递归调用，这样的方法被称为递归方法或递归算法。2024/11/947

2024/11/9483.1递归算法递归过程中的压栈、弹栈方法f递归过程是，第k次调用f需要等待第k+1次调用f结束执行过程后才能结束执行过程。那么第R(n)次（最后一次）调用f结束执行过程后，就会依次使得第k次调用结束执行过程。方法被调用时，方法的（入口）地址会被压入栈（栈是一种先进后出的结构）中，称为压栈操作，同时方法的局部变量被分配内存空间。

……调用调用调用调用调用结束

结束

结束

结束结束

图3.1递归执行过程第1次调用第R(n)次调用2024/11/9493.1递归算法递归过程中的压栈、弹栈方法调用结束，会进行弹栈，称为弹栈操作，同时释放方法的局部变量所占的内存。递归过程的压栈操作可以让栈的长度不断增加，而弹栈操作会让栈的长度变小，最终使栈的长度为0。…………

第1次弹栈第m次弹栈第k次弹栈第1次压栈第m次压栈第k次压栈2024/11/9503.1递归算法时间复杂度方法调用结束，会进行弹栈，称为弹栈操作，同时释放方法的局部变量所占的内存。要针对具体的递归方法，来计算该递归方法的时间复杂度。递归方法是一个递归过程，从递归开始到递归结束，方法被调的总数R(n)是依赖于一个正整数n的函数。那么递归方法中基本操作被执行的总数T(n)就依赖递归的总数R(n)和每次递归时基本操作被执行的总数。2024/11/9513.1递归算法空间复杂度方法调用结束，会进行弹栈，称为弹栈操作，同时释放方法的局部变量所占的内存。递归会让栈的长度不断发生变化，如果栈的长度较大可能导致栈溢出，使得进程（运行的程序）被操作系统终止。递归过程的压栈操作增加栈的长度、弹栈操作减小栈的长度。递归过程中可能交替地进行压栈操作和弹栈操作，直至栈的长度为0（见例子2）。计算出递归过程中，某一时刻（某一次递归）栈出现的最大长度和每次递归中方法的局部变量所占的内存空间，即计算出栈最大长度以及局部变量所占的全部内存空间和所依赖的正整数的关系，才可以知道空间复杂度。2024/11/9523.2线性递归与非线性递归●线性递归线性递归是指，每次递归时，方法调用自身一次。

如果我们忘记了今天是星期几，就需要知道昨天是星期几，如此这般地向前（过去）翻日历（相当于递归里的压栈，导致栈的长度在增加），等到能翻到某个日历页上显示了星期几，就结束翻阅日历（相当于结束压栈），然后再一页一页的撕掉日历（相当于弹栈），日历上神奇地出现了星期数，即方法依次计算出自己的返回值。Week.java例子1Example3_1.java2024/11/9533.2线性递归与非线性递归●线性递归递归方法f(intn)的递归的总次数：R(n)=n，而每次递归的基本操作只有2个基本操作，因此时间复杂度是O(n)。向下方向的弧箭头表示方法被调用，向上方向的直箭头表示方法调用结束。例子1压栈操作过程中得到的栈的最大长度是R(n)=n，空间复杂度是O(n)。2024/11/9543.2线性递归与非线性递归●非线性递非线性递归是指，每次递归时方法，调用自身2次或2次以上。

Fibonacci.java例子2Example3_2.java2024/11/9553.2线性递归与非线性递归●非线性递例子2递归过程中，每次递归时方法调用自身2次，使得每次递归出现了2个递归“分支”，然后选择一个分支，继续递归，直到该分支递归结束，再沿着下一分支继续递归，当2个分支都递归结束，递归过程才结束，而且递归过程交替地进行压栈和弹栈操作，直至栈的长度为0。

2024/11/9563.3问题与子问题将规模大的问题，使用递归算法逐步分解成规模小的问题，最终解决规模大的问题。一个问题的子问题就是数据规模比此问题的规模更小的问题。当一个问题，可以分解成许多子问题时就可以考虑用递归算法来解决这个问题。2024/11/9573.3问题与子问题

SumMulti.java例子3Example3_3.java2024/11/9583.3问题与子问题

Reverse.java例子4Example3_4.javaMaxInArray.java2024/11/9593.4递归与迭代递归的思想是根据上一次操作的结果，确定当前操作的结果。迭代的思想是，根据当前操作的结果，确定下一次操作的结果。对于解决相同的问题，递归代码简练，容易理解解决问题的思路或发现数据的内部的逻辑规律，具有很好的可读性。由于迭代不涉及方法的递归调用，所以，通常情况下递归算法的空间复杂度会大于迭代的复杂度，当递归过程的递归总数比较大时，会导致栈溢出。2024/11/9603.4递归与迭代例子5中ComputePI类中的recursionMethod(intn)方法和iterationMethod(intn)都是通过计算级数的近似值返回圆周率的近似值，recursionMethod(intn)使用的是递归，iterationMethod(intn)使用的是迭代。ComputePI.java例子5Example3_5.java2024/11/9613.4递归与迭代

SearchNumber.java例子6Example3_6.java

2024/11/9623.4递归与迭代Euclidean.java例子7Example3_7.java

2024/11/9633.5多重递归所谓多重递归，是指一个递归方法调用另一个或多个递归方法，称该递归方法多重递归方法。

不要求输出含有偶数多个6的数。

2024/11/9643.5多重递归

2024/11/9653.6经典递归选择三个经典的递归：杨辉三角形、老鼠走迷宫和汉诺塔，进一步体会递归算法不仅能使得代码优美简练，容易理解解决问题的思路或发现数据的内部的逻辑规律，而且具有很好的可读性。特别是汉诺塔递归，通过其递归算法，洞悉其数据规律，给出相应的迭代算法。经典的递归：杨辉三角形，老鼠走迷宫，汉诺塔2024/11/9663.6经典递归杨辉三角

最早出现于中国南宋数学家杨辉1261年所著的《详解九章算法》中。法国数学家帕斯卡（Pascal）在1654年发现该三角形，所以又称帕斯卡三角形。

2024/11/9673.6经典递归杨辉三角最早出现于中国南宋数学家杨辉1261年所著的《详解九章算法》中。法国数学家帕斯卡（Pascal）在1654年发现该三角形，所以又称帕斯卡三角形。

2024/11/9683.6经典递归PascalTriangle.java例子9Example3_9.java杨辉三角

YanhuiTriangle.java

2024/11/9693.6经典递归老鼠走迷宫老鼠首先向东走，如果走到出口结束递归，否则向南…向西…向北。

2024/11/9703.6经典递归老鼠走迷宫例子10的主类Example3_10使用move(int[][]a,inti,intj)方法走迷宫。其中，用int型二维数组模拟迷宫，二维数组元素值是1表示墙，0表示路，2表示出口。老鼠走过迷宫后，输出老鼠走过的路时，用☆表示老鼠走过的路，■表示墙，★表示出口，□表示老鼠未走过的路。Mouse.java例子10Example3_10.java2024/11/9713.6经典递归汉诺塔（递归算法）汉诺塔(HanoiTower)问题是来源于印度的一个古老问题。有名字为A，B，C的三个塔，A塔上有从小到大64个盘子，每次搬运一个盘子，最后要把64个盘子搬运到C塔。在搬运盘子的过程中，可以把盘子暂时放在3个塔中的任何一个上，但不允许大盘放在小盘上面。3个盘子的汉诺塔

2024/11/9723.6经典递归汉诺塔（递归算法）3个盘子的汉诺塔

HannoiTower.java例子11Example3_11.java2024/11/9733.6经典递归汉诺塔（迭代算法）

这些规律是通过研究汉诺塔的递归算法发现的。就像本章一开始说的，递归可以发现数据的内部的逻辑规律。2024/11/9743.6经典递归汉诺塔（迭代算法）

一个偶数通过不断地右位移可计算出尾部连续的0的个数，例如：8的二进制1000右位移3次，得到奇数，因此知道8的二进制尾部连续0的个数是3。这些规律是通过研究汉诺塔的递归算法发现的。就像本章一开始说的，递归可以发现数据的内部的逻辑规律。2024/11/9753.6经典递归汉诺塔（迭代算法）这些规律是通过研究汉诺塔的递归算法发现的。就像本章一开始说的，递归可以发现数据的内部的逻辑规律。

HanoiTowerIterator.java例子12ZeroCount.javaExample3_12.java2024/11/976计算Fibonacci序列的递归过程中需要将f(n-1)分支进行完毕，再进行f(n-2)分支。需要注意到的是，在进行f(n-1)分支递归时，会完成了f(n-2)分支递归，那么再进行f(n-2)分支就是一个重复的递归过程。简而言之，优化递归就是避免重复子递归。优化递归就是在每次递归开始前，首先到某个对象中，通常为散列表对象，也可以是数组，查找本次递归是否已经被实施完毕，即是否已经有了递归结果，如果散列表对象中已经有了本次递归的结果，就直接使用这个结果，不再浪费时间进行本次递归，否则就进行本次递归，并将递归结果保存到散列表对象。3.7优化递归2024/11/9773.7优化递归

OptimizeFibonacci.java例子13Example3_13.javaOptimizeFibonacci类的散列表是静态成员变量，会不断累积子递归的结果，尽管会浪费内存空间，但会使得后面的递归速度越来越快。2024/11/9783.7优化递归

OptimizePascalTriangle.java例子14Example3_14.javaOptimizePascalTriangle类的散列表是静态成员变量，会不断累积子递归的结果，尽管会浪费内存空间，但会使得后面的递归速度越来越快。第4章数组与Arrays类2024/11/979主要内容● 数组的引用● 数组的排序● 数组的二分查找●数组的复制● 数组的比较● 数组的匹配● 公共子数组● 数组的更新● 数组的前缀运算● 数组的动态遍历● 数组与洗牌● 数组与生命游戏

数组是最常用的一种线性数据结构，数组一旦被创建，那么数组的长度（数组的元素的个数）就不可以再发生变化，即不可以对数组进行删除，添加或插入操作。关于数组的算法还是非常多的，比如排序，复制，二分查找，动态遍历等。4.1引用与参数存值

2024/11/9802024/11/9814.1引用与参数存值1.数组的引用数组属于引用型数据，即数组中存放着一个引用值，数组使用下标运算访问自己的元素（下从0开始，每个元素的下标等于它前面的元素的个数）。可以让System类调用静态方法intidentityHashCode(Objectobject)返回（得到）数组a的引用：intaddress=System.identityHashCode(a);也可以让数组a调用inthashCode()方法返回（得到）数组的引用：intaddress=a.hashCode();两个类型相同的数组，一旦二者的引用相同，二者就具有相同的元素。2024/11/9824.1引用与参数存值1.数组的引用数组属于引用型数据，即数组中存放着一个引用值，数组使用下标运算访问自己的元素（下从0开始，每个元素的下标等于它前面的元素的个数）。例子1中的主类Example4_1使用了intidentityHashCode()方法和inthashCode()方法，注意例子1的输出结果，特别是数组b的值（b的引用）赋值给数组a之后，程序的输出结果。例子1Example4_1.java2024/11/9834.1引用与参数存值2.参数存值使用参数存储值就是一个方法可以将某些数据存放在参数中，如果参数是引用类型，比如数组，那么方法执行完毕，保存在参数中的值一直还存在、不会消失。例子2Example4_2.java当a，b，c构成等边三角形时返回3，将三角形面积存放在数组area的元素中，构成等腰三角形时（不是等边）返回2，将三角形面积存放在数组area的元素中，构成三角形时（不是等边，也不是等腰）返回1，将三角形面积存放在数组area的元素中，不构成三角形时返回0，将Double.NaN（没有值）存放在数组area的元素中。Triangle.java2024/11/9844.1引用与参数存值2.参数存值使用参数存储值就是一个方法可以将某些数据存放在参数中，如果参数是引用类型，比如数组，那么方法执行完毕，保存在参数中的值一直还存在、不会消失。例子3Example4_3.java例子3中char型数组的元素值是某个小写英文字母，FindLetters类中的findMaxCountLetters(char[]english,int[]saveCount)方法返回char型数组中出现次数最多的字母之一，并将这个字母出现的次数存放到参数指定的int型数组的元素中。FindLetters.java4.2数组与排序2024/11/985排序算法是重要的基础算法。各种排序算法都是非常成熟的算法，Arrays类封装了快速排序和归并排序，编写程序时直接使用即可。2024/11/9864.2数组与排序1.快速排序

双轴快速排序不是稳定排序。稳定排序是指，数组里大小一样的数据，排序后，保持原始的先后顺序不变。起泡法是稳定排序，而选择法是不稳定排序。如果是给对象排序（非基本类型数据），那么创建对象类需要实现Comparable<T>泛型接口来指定对象的大小关系，否则，sort()方法将按对象的引用排序对象，这种排序往往没有什么实际意义（就像生活中，很少按人的身份证排序）。快速排序是一种基于递归的经典排序算法。它的思路是选定一个基准元素，然后把比这个元素小的元素放在它左边，比它大的元素放在它右边。再分别对它左边和右边的元素进行递归处理，直到排序完成。2024/11/9874.2数组与排序1.快速排序

例子4Example4_4.javaStudent.java

主类Example4_4分别使用Arrays类的sort(Object[]a)方法和我们自己定义的BasicSort类中的方法，按身高（height）排序Student类的对象。BasicSort.java2024/11/9884.2数组与排序2.归并排序例子5Example4_5.javaMerge.java

例子5里，我们依然给出了归并排序算法，其目的是体现递归算法的重要性（归并排序使用了递归算法），在实际应用中，完全没必要这样做，只需用Arrays类的parallelSort()方法即可，让你的代码更加简练有效。归并排序算法如下：①将待排序数组分成两个子数组，每个子数组通过递归进行排序。②将两个排好序的子数组合并成一个有序数组。4.3数组的二分查找2024/11/989二分法可用于查找一个数据是否在一个升序数组中。我们曾在第2章的例子9，第3章的例子6介绍过二分法。因为二分法是成熟的经典算法，所以Java将其作为一个方法封装在Arrays类中。在开发程序时，可以直接使用Arrays类即可，不必再像第2章例子9或第3章的例子6去编写算法的具体代码。2024/11/9904.3数组的二分查找1.二分法例子6Example4_6.java例子6的主类Example4_6，在循环10000次的循环语句的循环体中，每次使用Random对象得到1至7之间的一个数字。循环结束后输出1至7之间的各个数字出现的次数,该例子中使用了Arrays类中的binarySearch()方法。Arrays类中的binarySearch()方法是一个重载的方法，该方法使用二分法算法查找一个数据key是否在升序数组a中，如果在数组中，返回和key相等的数组元素的索引位置，如果不在数组中，返回一个负数（不一定是-1）2024/11/9914.3数组的二分查找1.二分法例子7Example4_7.javaFilterData.java例子7中的FilterData类的int[]filterArray(int[]arr,int[]filter)方法返回一个数组，该数组的元素值是数组arr经过数组filter过滤后的数据。过滤过程中，使用binarySearch()方法判断数组中哪些值不在filter中，然后通过保留不在filter中值，完成过滤过程。有时候想过滤数组arr，即想去掉数组arr中的某些值。为了过滤数组arr，可以用另外一个数组filer做过滤器，即数组filer中的元素值都是数组arr准备去掉的值。4.4数组的复制2024/11/992数组属于引用型变量，两个类型相同的数组，比如数组a和数组b，如果将a的引用赋值给b，那么二者的元素就完全相同了（见4.1节）。如果想得到一个数组b，b的元素值和a的相同，但二者的引用不同，就需要使用复制的办法，即把数组a的元素值赋值到数组b的元素中，而不是将a的引用赋值给b。2024/11/9934.4数组的复制1.复制数组的方法例子8Example4_8.javaGetRondomNumber.javacopyOf(int[]a,intnewLength)把数组a中从索引0开始的newLength多个元素值赋值到一个新数组中，并返回新数组的引用。如果newLength的值大于数组a的长度，新数组从newLength索引位置开始的元素值都是默认值。比如对于int型数组，默认是就是0。copyOfRange(int[]a,intfrom,intto)把数组a中从索引from开始的到索引位置to结束的元素值（但不包括索引位置是to的元素值）赋值到一个新数组中，并返回新数组的引用。用区间法表示就是把索引范围是半闭半开区间[from,to)的元素值赋值到一个新数组中，并返回新数组的引用。2024/11/9944.4数组的复制1.复制数组的方法例子9Example4_9.javaLeaveOneAround.java围圈留一是一个古老的问题（也称约瑟夫问题）：若干个人围成一圈，从某个人开始顺时针（或逆时针）数到第3个人，该人从圈中退出，然后继续顺时针（或逆时针）数到第3个人，该人从圈中退出，依此类推，程序输出圈中最后剩下的一个人。围圈留1问题可以简化为旋转数组（向左或向右旋转数组），旋转数组2次即可确定出退出圈中的人，即此时数组首元素中的号码就应该是要退出圈中的人。例子9中，LeaveOneAround类的leaveOne(int[]people)方法通过旋转数组确定数组people中出圈的元素，并用copyOfRange()方法保留剩余的元素。2024/11/9954.4数组的复制2.处理重复数据例子9Example4_10.javaHandleRecurring.java有时候需要处理数组中重复的数据，即让重复的数据只保留一个。例子10中，HandleRecurring类的handleRecurring(int[]arr)方法处理数组arr中重复的数据，该方法返回的数组中的数据是arr中去掉重复数据后的数据（重复的数据只保留一个）。4.5数组的比较2024/11/996Arrays类中的静态方法intcompare()和booleanequals()都是重载的方法，用于比较两个数组，二者的区别仅仅是返回值的类型不同。2024/11/9974.5数组的比较例子11Example4_11.javaFindWord.java例子11中，FindWord类的findWord(Stringstr,Stringword)方法输出str中出现的word并返回word出现的次数。例子11的主类Exmple4_11输出一段英文中出现的girl和girl出现的次数4.6公共子数组2024/11/998如果数组a的某个子数组和数组b的某个子数组的长度相同（不要求两个子数组的起始索引相同），所包含的元素值也依次相同，就称二者有公共子数组。2024/11/9994.6公共子数组让长度小的数组，比如b的首单元和数组a的未单元对齐，数组b一直向左移动，直到数组b的尾部a的首单元对齐。向左滑动法那么在左移的过程中，数组a和数组b二者的所有公共子数组一定会出现左对齐的情况。数组a数组b2024/11/91004.6公共子数组例子12Example4_12.javaFindZeroCount.java让长度小的数组，比如b的首单元和数组a的未单元对齐，即b的左端和a的右端对齐，然后进行异或运算，运算结果存放到一个其它数组c中，让数组b按一个单元（元素）为单位向左依次移动（滑动），每移动一个单元，进行异或运算，运算结果存放到数组c中。数组b一直向左移动，直到数组b的尾部，即最后一个单元和数组a的首单元对齐。向左滑动法那么在左移的过程中，数组a和数组b二者的所有公共子数组一定会出现左对齐的情况。由异或运算法则可知，相同的整数异或的结果是0，那么只要根据数组c中连续出现的0的个数，就可以找到一个最大的公共子数组。MaxCommon.java4.7数组的更新2024/11/9101Arrays类提供了对数组整体更新的方法：fill()和setAll()。1.整体更新为单值：voidfill(int[]a,intval)该方法将参数数组a的每个元素的而值都设置为参数val指定的值。2.动态更新setAll()方法是一个重载方法，例如：publicstaticvoidsetAll(double[]a,IntToDoubleFunctiongenerator)将参数数组a的每个元素的值都设置为参数generator的计算结果。2024/11/91024.7数组的更新例子13Example4_13.javapublicstaticvoidsetAll(int[]a,IntUnaryOperatorgenerator)IntUnaryOperator是一个函数接口，其中的抽象方法的参数是int型，返回值是int型。可以将一个Lambda表达式传递给generator，该Lambda表达式必须是1个int型参数，Lambda表达式中必须有return语句，返回的值是int型数据。setAll()方法会使用Lambda表达式依次设置数组a的元素的值。例子13中，主类Example4_13使用fill()和setAll()方法整体更新数组的元素的值.4.8数组的前缀算法2024/11/9103数组a的前缀算法是：①i初始化0，进行②。②如果i的值满足结束条件，进行③，否则将某个运算结果赋值到数组的第i+1个元素中（通常是a[i]与a[i+1]参与的运算）。i++，执行②。③结束2024/11/91044.8数组的前缀算法例子14Example4_14.javapublicstaticvoidparallelPrefix(int[]a,IntBinaryOperatorop)IntBinaryOperator是一个函数接口，其中的抽象方法的是2个int参数，返回值是int型。可以将一个Lambda表达式传递给op，该Lambda表达式必须是2个int型参数，Lambda表达式中必须有return语句，返回的值是int型数据。例如：IntBinaryOperatorop=(i,j)->{returni+j;};Arrays.parallelPrefix(arr,op);parallelPrefix()在执行过程中，让i取数组的第i个元素的值，j取数组的第i+1个元素的值，将Lambda表达式中return语句的返回值设置为数组第j个元素的值后，然后i再自增，再重复前面的计算。。4.9动态遍历2024/11/9105遍历数组的方法（算法）在遍历数组时，让数组的每个元素参与某种运算，并输出运算后的结果，称这样的遍历方法为动态遍历方法。①将数组a的全部元素或部分元素封装到Spliterator.OfInt对象中。②Spliterator.OfInt对象调用voidforEachRemaining(IntConsumerconsumer)方法遍历Spliterator.OfInt对象中封装的数组元素。2024/11/91064.9动态遍历例子15Example4_15.javaforEachRemaining(IntConsumerconsumer)方法遍历Spliterator.OfInt对象中封装的数组元素。该方法的参数intConsumer是一个函数接口，该接口中的抽象方法的参数是int型，返回类型是void型。那么在调用forEachRemaining(IntConsumerconsumer)方法时，可以将一个Lambda表达式传递给consumer，该Lambda表达式必须是1个int型参数，不需要return语句（如果有return，不允许返回任何值）。比如，可以将下列Lambda表达式(value)->{System.out.println(value);}传递给consumer，forEachRemaining(IntConsumerconsumer)方法在执行过程中将使用这个Lambda表达式，让Lambda表达式的参数valule依次取Spliterator.OfInt对象中封装的数组元素1.动态方法2024/11/91074.9动态遍历例子16Com.java

可以自己编写简单的遍历数组的动态方法，即方法的参数是一个函数接口。2.编写动态方法例子16中，Com接口有一个抽象方法compute()，是一个函数接口（除了其它方法外，有且只有一个抽象方法的接口是函数接口）。Com接口中的outPut()方法的参数是一个函数接口，因此可以向该参数传递Lambda表达式。Example4_16.java2024/11/91084.9动态遍历例子172.多线程遍历Example4_17.java可以用多线程遍历数组。在使用多线程之前，需要将封装数组元素的Spliterator进行拆分，即分解成几部分，每一部分称作Spliterator的一个分区，然后让一个线程负责遍历一个分区。Spliterator对象可以调用Spliterator<T>trySplit()方法将自己一拆为二，即trySplit()方法从当前Spliterator对象中分离出一半的数组元素构成一个新的Spliterator对象（当前Spliterator对象中的数组元素减少一半），并返回这个新的Spliterator对象（对于数组，按索引顺序，分离出后一半元素值）。对于较大的数组，将对应的Spliterator进行分区，使用多线程可以加快遍历数组的速度。4.10数组与洗牌2024/11/9109

2024/11/91104.10数组与洗牌例子18ShuffleCard.java

Example4_18.java4.11数组与生命游戏2024/11/9111生命游戏属于二维细胞自动机的一种，是英国数学家JohnHortonConway(约翰.何顿.康威)在1970年发明的一种特殊二维细胞自动机。将二维平面上的每一个格子看成是一个细胞生命体，每个细胞生命都有“生和死”两种状态，每一个细胞旁边都有邻居细胞存在，比如把3*3的9个格子构成的正方形看成一个基本单位的话，那么这个正方形中心的细胞的邻居就是它旁边的8个细胞（至多8个）。4.11数组与生命游戏2024/11/9112一个细胞的下一代的生死状态变化遵循下面的生命游戏算法。①细胞周围有3个细胞为生，下一代该细胞为生（当前细胞若原先为死，则转为生，若原先为生，则保持不变）。②细胞周围有2个细胞为生，下一代该细胞的生死状态保持不变。③细胞周围是其它情况，下一代该细胞为死。（即该细胞若原先为生，则转为死，若原先为死，则保持不变）。2024/11/91134.11数组与生命游戏例子18AggregateOperation.javaExample4_19.java例子19中，AggregateOperation类定义了一些关于二维数组的一些方法，以便LifeGame类调用使用，使得LifeGame类的代码更加简练，提高可读性。主类Example4_19使用LifeGame类输出了生命游戏中生命状态的变化。LifeGame.java第5章链表与LinkedList类2024/11/91145.1链表的特点2024/11/9115链表是由若干个节点组成，这些节点形成的逻辑结构是线性结构，节点的存储结构是链式存储，即节点的物理地址不必是依次相邻的。对于单链表，每个结点含有一个数据，并含有下一个节点的引用。对于双链表，每个节点含有一个数据，并含有上一个节点的引用和下一个结点的引用（Java实现的是双链表）2024/11/91165.1链表的特点图示意的是有5个节点的双链表（省略了上一个节点的引用箭头示意）。注意，链表的节点序号是从0开始，每个节点的序号等于它前面的节点的个数。链表中的节点的物理地址不必是相邻的，因此，链表的优点是不需要占用一块连续的内存存储空间。图5.12024/11/91175.1链表的特点

●删除头、尾节点的复杂度O(1)删除前面所示意5个节点的的链表的头节点(大象-节点)后的示意图。2024/11/91185.1链表的特点

●查询头、尾节点的复杂度O(1)查询狮子和鳄鱼的时间复杂度都是O(1)。2024/11/91195.1链表的特点

●添加头尾节点的复杂度O(1)要给图5.1所示意的链表的添加新的尾节点（企鹅-节点），根据双链表保存的尾节点的地址，找到尾节点（鳄鱼-节点），将这个尾节点中的下一个节点的引用设置成新添加的节点（企鹅-节点）的引用，将添加的新节点（企鹅-节点）中的上一个节点的引用设置成鳄鱼-节点的引用，将添加的新节点（企鹅-节点）中的下一个节点的引用设置成null，即让新添加的节点成为尾结点。2024/11/91205.1链表的特点●查询中间节点的时间复杂度O(n)链表的节点的物理地址不是相邻的，节点通过互相保存引用链接在一起。

2024/11/91215.1链表的特点●删除中间节点的复杂度O(n)链表的节点的物理地址不是相邻的，节点通过互相保存引用链接在一起。

删除了老虎-节点2024/11/91225.1链表的特点●插入中间节点的复杂度O(n)

插入新节点后，新链表中的节点序号按新的链表长度从0开始排列。2024/11/91235.1链表的特点●插入中间节点的复杂度O(n)图5.1的链表中插入新的第2个节点（羚羊-节点）5.2创建链表2024/11/9124链表由Java集合框架（JavaCollectionsFramework，JCF）中的LinkedList<E>泛型类所实现。2024/11/91255.2创建链表LinkedList<E>泛型类实现了Java集合框架中的List和Queue泛型接口。LinkedLis<E>t泛型类继承了List和Queue泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了List和Queue泛型接口中的抽象方法。2024/11/91265.2创建链表例子1Example5_1.java使用LinkedList<E>泛型类声明链表时，必须要指定E的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等），即指定链表中节点里的对象的类型。例如，指定E是String类型：LinkedList<String>listOne=newLinkedList<>();或LinkedList<String>listOne=newLinkedList<String>();例子1中的主类Example5_1中首先创建一个空链表listOne，然后向空链表listOne添加4个节点，随后再用listOne创建链表listTwo。修改listTwo节点的数据，并不影响listOne节点中的数据。5.3查询与相等2024/11/9127查询链表节点中的数据的常用方法：

booleanequals(Objectlist)如果此链表和list长度相同，并且对应的每个节点中的对象也相等，那么方法返回true，否则返回flase。2024/11/91285.3查询与相等例子2People.javaExample5_2.java例子2中的主类Example5_2中比较了get(intindex)方法和getLast()方法的运行时间。例子2中的People类重写了booleanequals(Objecto)方法.2024/11/91295.3查询与相等例子3RandomLayMines.javaExample5_3.java

主类Example5_3使用layMines(char[][]area,intamount)方法布雷39颗。2024/11/91305.3查询与相等例子4TeamGame.javaExample5_4.java

5.4添加2024/11/9131链表添加节点常用方法：

2024/11/91325.4添加例子5Example5_5.java例子5中的主类Example5_5中比较了voidaddLast(Ee)方法和voidadd(intindex,Ee)方法的运行时间。5.5删除2024/11/9133链表删除节点常用方法：

2024/11/91345.5删除例子6RandomNumber.java例子6中RandomNumber类的getRandom(intnumber,intamount)方法通过随机删除链表中的节点来得到若干个随机数。Example5_6.java例子6中的主类Exmple5_6使用RandomNumber类的getRandom(intnumber,intamount)方法模拟双色球，同时过滤一个链表。2024/11/91355.5删除例子7HandleRecurring.javaExample5_7.java有时候需要处理数组中重复的数据，即让重复的数据只保留一个。在某些场景下，数据重复属于冗余问题。冗余可能给具体的实际问题带来危害，比如，你在撰写一篇文章时，用编辑器同时打开了一个文档多次，那么有时候就会引起混乱。所以，应当只打开文档一次，以免在修改，保存文档时发生数据处理不一致的情况。例子7中，HandleRecurring类的handleRecurring(LinkedList<E>list)方法处理链表list中重复的数据，该方法返回的链表中没有重复的数据（对于重复的数据，保留其中一个）。5.6更新2024/11/9136链表更新节点的常用方法：

Collections类的静态方法static<T>voidfill(List<?superT>list,Tobj)将链表list的每个节点中的对象都设置为参数obj指定的对象。2024/11/91375.6更新例子8Example5_8.java例子8的主类Example5_8使用set(intindex,Eelement)方法和fill(List<?superT>list,Tobj)方法更新链表节点中的对象。5.7链表的视图2024/11/9138链表的视图是由链表中若干个节点所构成，其状态变化和链表是同步的。视图的好处是，可以将经常需要修改的节点放在一个视图中，有利于数据的一致性处理。

使用视图时，要注意视图中节点和原链表节点的对应关系。2024/11/91395.7链表的视图List<E>subList(intfromIndex,inttoIndex)方法是AbstractList类所实现的List接口中的一个方法（AbstractList类是LinkedList的间接父类）。该方法返回一个当前链表中节点序号fromIndex（含）和toIndex（不含）之间的节点构成的视图。需要特别注意的是，一旦链表添加或删除节点，就会破坏视图的索引，即会影响之前链表subList()方法返回的视图，这个视图将无法再继续被使用（如果继续使用，运行时刻会触发ConcurrentModificationException异常），链表必须用subList()方法重新返回一个新的视图。更改视图的节点（增加或删除节点）或对节点的数据的修改都会使得当前链表发生同步的改变。2024/11/91405.7链表的视图使用视图时，要注意视图中节点和原链表节点的对应关系。原链表list中狮子节点是第1个节点，但在视图listView中狮子节点是第0个节点，原链表list中老虎节点是第2个节点，但在视图listView中老虎节点是第1个节点，原链表list中猎豹节点是第3个节点，但在视图listView中猎豹节点是第2个节点。2024/11/91415.7链表的视图使用视图时，要注意视图中节点和原链表节点的对应关系。如果视图listView增加一个节点，比如尾节点：鬣狗那么原链表list会同步更新、发生变化，猎豹节点和河马节点之间多了一个鬣狗节点：2024/11/91425.7链表的视图例子9Example5_9.java例子9的主类Example5_9使用链表的视图更新链表节点中的天气信息。5.8链表的排序2024/11/9143publicdefaultvoidsort(Comparator<?superE>c)方法是List接口的默认排序方法（default关键字修饰的方法），LinkedList继承了该排序方法（去掉了关键字default）。该排序方法的参数c是Comparator泛型接口，Comparator泛型接口是一个函数接口，即此接口中的抽象方法只有一个：intcompare(Ta,Tb)，此方法比较两个参数a和b的顺序，返回值是正数表示a大于b，返回负数表示a小于b,返回零表示a等于b。2024/11/91445.8链表的排序Comparator是一个函数接口，因此在使用该方法时，可以向参数c传递一个Lambda表达式，该Lambda表达式必须是2个参数，Lambda表达式中必须有return语句，返回的值是int型数据（和其代表的intcompare(Ta,Tb)方法保持一致）。例如sort((a,b)->{if(a.height>b.height)return1;elseif(a.height<b.height)return-1;elsereturn0;})

2024/11/91455.8链表的排序例子10Student.java例子10的主类Example5_10分别按学生的数学和英文成绩升序排序链表、降序排序链表。Example5_10.java5.9遍历链表2024/11/9146某些集合根据其数据存储结构和所具有的操作也会提供返回数据的方法，例如LinkedList类中的get(intindex)方法将返回当前链表中第index节点中的对象。LinkedList的存储结构不是顺序结构，即节点的物理地址不必是依次相邻的，因此，链表调用get(intindex)方法的速度比顺序存储结构的集合调用get(intindex)方法的速度慢。当用户需要遍历集合中的节点时，应当使用该集合提供的迭代器，而不是让集合本身来遍历其中的节点。2024/11/91475.9遍历链表单向迭代器是从链表的头节点开始，遍历到尾节点。●单向迭代器链表对象可以使用Iterator<E>iterator()方法获取一个实现Iterator接口的对象，该对象就是针对当前链表的单向迭代器。迭代器内部使用了游标技术，单向迭代器的游标的初始状态是指向链表的头节点的前面，如果游标可以向后移动（向链表的尾节点方向），单向迭代器调用hasNext()方法返回true，否则返回false。连续的调用next()方法会将游标移动到尾节点，这时游标将无法向后移动，再调用next()方法否则触发运行异常NoSuchElementException（链表是空链表，直接调用next()方法也会触发运行异常NoSuchElementException）。2024/11/91485.9遍历链表●双向迭代器链表对象可以使用ListIterator<E>listIterator()方法获取一个实现ListIterator接口的对象（ListIterator接口是Iterator的子接口），该对象就是针对当前链表的双向迭代器。双单向迭代器是双游标迭代器，一个向后游标（向链表的尾节点方向），一个向前游标（向链表的头节点方向）。双游标是同时移动，向前游标在向后游标的后面。

初始状态向后游标指向头节点的前面，向前游标指向头节点。2024/11/91495.9遍历链表●遍历与更新迭代器对链表实施的添加、删除、更新节点等操作一直等到迭代器遍历链表完毕再生效。双向迭代器调用next()或previous()方法返回节点中的数据后，迭代器紧接着调用add(Eobj)方法，可以在该节点后插入一个节点（新节点序号从当前节点开始递增），调用set(Eobj)方法可以更新该节点中的数据，调用remove()方法可以删除该节点。单向迭代器在遍历链表时也可以同时更新链表，但只能删除节点。单向迭代器调用next()方法返回节点中的数据后，迭代器紧接着调用remove()方法可以删除该节点。2024/11/91505.9遍历链表●遍历与锁定单向或双向迭代器在遍历链表时，将不允许链表本身调用方法更改链表节点的结构。单向或双向迭代器在遍历链表时，将不允许链表本身调用方法更改链表节点的结构，即不允许链表调用方法增加节点、删除节点、排序链表，但允许链表调用set(intindex，Eobj)方法更新节点中的数据，因为更新节点只是更新链表的节点中的数据，不属于更改链表的节点的结构。

在迭代器没有结束遍历之前，如果链表进行增加节点、删除节点、排序链表这些操作，程序运行时（无编译错误）将触发java.util.ConcurrentModificationException异常。程序必须等到迭代器被使用完毕，才允许链表调用add()、remove()方法添加、删除节点或排序链表。2024/11/91515.9遍历链表●for-each语句链表获得迭代器后，在使用迭代器之前又对链表进行了更新，比如添加、删除或排序链表，那么就无法再使用该迭代器遍历链表。如果想使用迭代器，就必须让链表重新返回一个新的迭代器。使用for-each语句遍历一个链表时，禁止当前链表调用add()、remove()方法添加、删除节点或排序链表，其原因是，for-each算法的内部中启用了迭代器。2024/11/91525.9遍历链表例子11例子11的主类Example5_11分别使用单向迭代器和双向迭代器遍历了链表，在遍历的过程中也更新了链表。Example5_11.java2024/11/91535.9遍历链表例子12约瑟夫问题（也称围圈留一问题）：若干个人围成一圈，从某个人开始顺时针（或逆时针）数到第3个人，该人从圈中退出，然后继续顺时针（或逆时针）数到第3个人，该人从圈中退出，依此类推，程序输出圈中最后剩下的一个人。Example5_12.javaLeaveOneAround.java这里例子12中的LeaveOneAround类的leaveOne(LinkedList<Integer>people)方法通过遍历链表，解决约瑟夫问题：在遍历链表的过程中删除相应的节点模拟出圈的人。2024/11/91545.9遍历链表例子13一个遍历链表的方法（算法）在遍历链表时，让链表的每个节点中的对象参与某种运算，并输出运算后的结果，称这样的遍历方法为动态遍历方法。Example5_13.java●动态遍历publicdefaultvoidforEachRemaining(Consumer<?superE>action)方法是Iterator接口中的默认方法，链表返回的迭代器（单向或双向）可以使用该方法动态的遍历链表。此方法的参数类型是Consumer函数接口，该接口中的抽象方法voidaccept(Tt)的返回类型是void型。那么在调用此方法时，可以将一个Lambda表达式传递给action。2024/11/91555.9遍历链表例子14Example5_14.java●动态遍历例子14的主类Example5_14动态遍历节点中是数组的一个链表，在遍历这个链表时，让节点中的数组参与运算，计算数组的元素值之和.链表的节点中可以是任何引用型的数据，例如类，数组，接口等类型的数据。第6章顺序表与ArrayList类2024/11/91566.1顺序表的特点2024/11/9157顺序表也是线性表的一种具体体现，顺序表节点形成的逻辑结构是线性结构、节点的存储结构是顺序存储，即节点的物理地址是依次相邻的。2024/11/91586.1顺序表的特点顺序表使用数组来实现，顺序表的节点的物理地址是依次相邻的，因此可以随机访问任何一个节点，不必从头节点计数查找其它节点。●查询节点

2024/11/91596.1顺序表的特点和链表不同，顺序表没有单独添加头节点的操作，但是有添加尾节点的操作。●添加节点

2024/11/91606.1顺序表的特点

●删除节点

6.2创建顺序表2024/11/9161顺序表由Java集合框架（JavaCollectionsFramework，JCF）中的ArrayList<E>泛型类所实现。2024/11/91626.2创建顺序表ArrayList<E>泛型类的实列使用数组管理节点，因此节点就是对象，后面的叙述不再说节点里的对象。ArrayList<E>泛型类实现了Java集合框架中的List泛型接口(和链表不同，没有实现Queue泛型接口)。ArrayList<E>泛型类继承了List泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了List泛型接口中的抽象方法。2024/11/91636.2创建顺序表顺序表可以使用add(Eobj)方法向顺序表依次增加节点。创建空顺序表，使用ArrayList<E>泛型类声明顺序表时，必须要指定E的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等）即指定顺序表中节点（对象）的类型。例如，指定E是String类型：ArrayList<String>arrlistOne=newArrayList<>();或ArrayList<String>arrlistOne=newArrayList<String>();例子1Example6_1.java例子1中的主类Example6_1中首先创建一个空顺序表arrlistOne，然后向