数据结构与算法（Java语言版）课件 第1、2章 数据结构简介、算法复杂度

第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