第6章算法与数据结构

1、 第6章 算法与数据结构通过本章的学习，学生应该能够：1理解算法的概念及算法度量方式；2了解数据结构的概念及基本术语；3理解并掌握线性结构的特性及基本操作；4理解并掌握二叉树的特性及基本操作；5理解并掌握图的特性及基本操作；6掌握三种基本的排序方法；7理解计算思维；8了解基本的算法设计技巧。6.1算法概述6.1.1算法及特性算法（Algorithm）是指为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。算法具有5个特性。（1）有穷性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。也就是说对于任意一组合法的输入数据，算法在执行有限步骤后一定能结束。 （2）确定性：组成算法

2、的每条指令是清晰的、无歧义的，算法的执行者或阅读者能确定其含义并执行。（3）可行性：算法中的操作可以通过已经实现的基本操作运算执行有限次而完成。（4）有输入：算法允许有多个或0个输入。 （5）输出：算法对数据进行处理后，至少有一个或多个输出。在算法的5个特性中，最基本的是有穷性、确定性和可行性。一个“好”的算法在设计时需要注意以下四个原则。（1）算法的正确性；（2）可读性；（3）健壮性；（4）高效率和低存储。6.1.2 算法的描述方式1算法的自然语言描述算法的自然语言描述自然语言就是人们日常使用的语言，可以使用汉语、英语或其他语言等。2算法的流程图描述流程图使用一些图框来表示各种操作。3算法的

3、伪代码描述算法的伪代码描述伪代码是用介于自然语言和程序设计语言之间的文字和符号来描述算法。伪代码不使用图形，在书写上方便，格式紧凑，比较好懂，不仅适宜设计算法过程，也便于向计算机语言算法（即程序）过渡。4用计算机语言表示用计算机语言表示算法算法用计算机语言表示算法必须严格遵循所用的语言的语法规则，这是和伪代码不同的。6.1.3 算法的度量 算法的度量分为空间和时间两方面。 空间复杂度S（n）根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。 时间复杂度T（n）根据算法写成的程序在执行时耗费时间的长度。

4、这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致大家在有生之年都等不到运行结果。 一个算法的执行时间大致上等于其所有语句执行时间的总和，每一条语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。在进行算法分析时，我们并不需要得到准确的算法执行时间，但关心的是算法中语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级（Order of Magnitude）。在这里，用“O”来表示数量级，这样就可以给出算法的时间复杂度概念。所谓算法的渐进时间复杂度，即是算法的时间量度，记作： T(n)=O(f(n) 一般情况下，伴随问题

5、规模n的增大，T(n)的增长较慢的算法为最优的算法。时间复杂度分析的基本策略是从算法内部（或最深层部分）向外展开工作。所遵循的一般法则如下。（1）顺序语句：将各个语句的运行时间求和即可（这意味着，其中的最大值就是所得的运行时间）。（2）选择语句：一个选择语句的运行时间从不超过判断再加上所有选择部分中运行时间较长者的总的运行时间。（3）单层循环：一个循环的运行时间至多是该循环内语句的运行时间乘以迭代的次数。（4）嵌套循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。T(n)3000200010005101520n200log2n算

6、法 A100n5n22n32n算法 B0算法 B图1 多种数量级的时间复杂度图示 算法中常用的时间复杂度频率计数有7个：O(1)常数型、O(n)线性型、O(n2)平方型、O(n3)立方型、O(2n)指数型、O(log2n)对数型、O(nlog2n)二维型。一般情况下，随着n的增大，T(n)增长较慢的算法为最优的算法。由此可知应该选择使用多项式阶O(nk)的算法，而避免使用指数阶的算法。6.2 数据结构概述6.2.1什么是数据结构 在计算机科学或信息科学中，数据结构是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。计算机及相关学科中，数据结构是一门重要的专业基

7、础课，数据结构主要研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等。6.2.2 6.2.2 数据结构的数据结构的基本术语基本术语 1. 1. 数据（数据（DataData） 数据是描述客观事物的数值、字符以及能输入机器能输入机器且能被处能被处理理的各种符号集合。简而言之，数据就是计算机化的信息。 2. 2. 数据元素（数据元素（Data ElementData Element） 数据元素是组成数据的基本单位，数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项数据项组成（Data Item）。 表1 学 籍

8、 表 学号姓名性别籍贯出生年月住址101赵红玲女河北1983.11北京 数据项记录3. 3. 数据对象（数据对象（Data ObjectData Object） 数据对象是性质相同的数据元素的集合，是数据的一个子数据对象是性质相同的数据元素的集合，是数据的一个子集。集。例如：整数数据对象是集合N=0， 1， 2， ，字母字符数据对象是集合C=A，B，Z，表1-1所示的学籍表也可看作一个数据对象。 4.4.数据结构数据结构 ：数据之间的相互关系：数据之间的相互关系 (1) 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。 (2) 线性结构：结构中的数据元素之间存在着一对

9、一一对一的线性关系。 (3) 树形结构：结构中的数据元素之间存在着一对多一对多的层次关系。 (4) 图状结构或网状结构：结构中的数据元素之间存在着多对多多对多的任意关系。 在形式上，数据结构通常用一个二元组来描述：Data_structure=(D,S) 其中，D为数据结构的有限集，S是D上关系的有限集。例：一年四季名称所组成的数据结构可以表示为：B=(D,R)D=春，夏，秋，冬R=,例：假设家庭成员组成的数据结构可以表示成：B=(D,R)D=祖父，叔叔，父亲，儿子，女儿，孙子R=, 5. 5. 存储存储结构结构 存储结构（又称物理结构）是逻辑结构在计算机中的存储映存储结构（又称物理结构）是逻

10、辑结构在计算机中的存储映象象，是逻辑结构在计算机中的实现，它包括数据元素的表示数据元素的表示和和关系的表示关系的表示。 逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。 顺序映象 （顺序存储结构）顺序映象用元素在存储器中的相对位置相对位置表示数据元素之间的逻辑关系。 非顺序映象（非顺序存储结构）非顺序映像借助指示元素存储地址的指针指针表示元素之间的逻辑关系。 用用一维数组一维数组来描述顺序存储结构，用来描述顺序存储结构，用指针指针来描述链式存储结构。来描述链式存储结构。 6.3

11、线性结构 线性结构描述的是一对一的相互关系。即一个线性结构中除了第一个元素之外，其他每个元素只有一个直接前驱；除了最后一个元素之外，其他每个元素只有一个直接后继。线性结构包括线性表、栈、队列、字符串、数组等，其中线性表是最基本的线性结构。（a1, a2, ai-1，ai, ai1 ，, an）线性表的定义：线性表的定义：是是n个数据元素的有限序列个数据元素的有限序列n=0时称为时称为数据元素数据元素表头表头ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表表尾表尾6.

12、3.1线性表 线性表的特点可概括如下： 同一性 有穷性 有序性 线性表是最常见的数据结构，因为矩阵、数组、字符串、堆栈、 队列等都符合线性条件。线性表线性表的顺序存储结构的顺序存储结构 用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上理上相邻相邻的存储单元中的存储结构。的存储单元中的存储结构。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻线性表顺序存储特点：线性表顺序存储特点：1. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，

13、其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元素存放位置若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（亦可求出（利用数组下标利用数组下标）。计算方法是：）。计算方法是： 设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为首地址首地址），设每个），设每个元素占用存储空间（地址长度）为元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素则表中任一数据元素的的存放地址存放地址为：为： LOC(ai) = LOC(a1) + L *（i-1） 它是一种它是一种随机存取随机存取的数据结构。的数据结构。 在顺序表中第i个位置插入一个新元素时，需

14、要将第n至第i位的元素向后移动一个位置；然后才能将要插入的元素写到第i个位置；表长加1。 在顺序表中删除第i个元素，需要将第i +1至第n 位的元素向前移动一个位置；表长减1。线性表顺序表示的优点是： (1）无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）； (2）可方便地随机存取表中的任一元素。 其缺点是：其缺点是： （1）插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低;（2）预分配空间（浪费）；（3）表的扩充不方便。 3 链式存储链式存储特点：u用一组任意的存储单元存储线性表的数据元素

15、u利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素u每个数据元素ai，除存储本身信息外还需存储其直接后继的信息u结点u 数据域：元素本身信息u 指针域：指示直接后继的存储位置datanext数据域指针域 由于链表的每个结点只有一个指针域，故将这种链表又称为单链表单链表。 单链表中第一个结点无前趋，应设一个头指针H指向第一个结点。 单链表中最后一个结点没有直接后继，则指定最后一个结点的指针域为“空”（NULL）。 整个链表的存取必须从头指针开始。 单链表的逻辑状态 带头结点单链表图示 (a) 带头结点的空单链表HHa1a2an(b) 带头结点的单链表 在单链表中查找第i个结点，需要从头指针H

16、出发，顺着链域进行扫描。每扫描一个结点，计数器增1，当计数器等于i时，即找到了第i个结点。 如果要在第i个位置插入元素e，需要找到第i-1个结点并由指针p指示，然后申请一个新的结点并由指针s指示，其数据域的值为e。修改s和p两个结点的指针域信息，把新结点链接到表中。 如果要删除第i个位置的结点，需要找到第i-1个结点并由指针p指示，然后修改p结点的指针域信息，让它指向新的后继结点的地址即可。链表的运算效率分析链表的运算效率分析1. 查找查找 因线性链表只能顺序存取，即在查找时要因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为从头指针找起，查找的时间复杂度为 O(n)。时间效

17、率分析时间效率分析2. 插入和删除插入和删除 因线性链表不需要移动元素，只要修因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为改指针，一般情况下时间复杂度为 O(1)。 但是，如果要在单链表中进行但是，如果要在单链表中进行前插前插或或删除删除操作，操作，由于要从头查找前驱结点，所耗时间复杂度为由于要从头查找前驱结点，所耗时间复杂度为 O(n)。栈（Stack）：具有一定操作约束的线性表 只在一端（栈顶栈顶，Top）做 插入、删除 插入数据：入栈入栈（Push） 删除数据：出栈出栈（Pop） 后入先出后入先出：Last In First Out（LIFO）6.3.2 栈队列(Que

18、ue)：具有一定操作约束的线性表 插入和删除操作：只能在一端插入（队尾），而在另一端删除（队头）。数据插入：入队列数据删除：出队列先来先服务 先进先出：先进先出：FIFO 6.3.3 队列串(String)是零个或多个字符组成的有限序列。一般记为： S= a1a2.an (n0)其中S是串的名字，名字，用单引号括起来的字符序列是串的值值，ai(1in)可以是字母、数字或其它字符。n是串中字符的个数，称为串的长度长度，n=0时的串称为空串空串 (Null String)。 6.3.4 串 串中任意个连续的字符组成的子序列称为该串的子串子串。包含子串的串相应地称为主串主串。通常将字符在串中的序号称

19、为该字符在串中的位置位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。 假如有串A=China Beijing，B=Beijing，C=China，则它们的长度分别为13、7和5。B和C是A的子串，B在A中的位置是7，C在A中的位置是1。 当且仅当两个串的值相等时，称这两个串是相等相等的，即只有当两个串的长度相等，并且每个对应位置的字符都相等时才相等。 串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。 在各种应用中，空格常常是串的字符集合中的一个元素，因而可以出现在其它字符中间。由一个或多个空格组成的串 称为空格串空格串（bla

20、nk string ，请注意此处不是空串）。它的长度为串中空格字符的个数。 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。 客观世界中许多事物存在层次关系 人类社会家谱 社会组织结构 磁盘文件管理 分层次组织在管理上具有更高的效率! 6.4 树状结构树是n（n0）个结点构成的有限集合T。 当n=0时，称为空树； 当n0时，称为非空树，满足如下条件： 其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。 其余n-1个结点可以划分成m（m0）个互不相交的有限集T1，T2，T3，Tm，其中子集Ti又是一棵树，称为根root的子树。6.4.1 树 树T

21、子树T1子树T2子树T3子树是不相交的； 除了根结点外，每个结点有且仅有一个父结点； 一棵N个结点的树有N-1条边。 树的基本术语 p结点的度：一个结点的子树个数称为此结点的度。p树的度：树中所有结点的度的最大值。p 叶子结点：度为0的结点，也称为终端结点。p 分支结点：度不为0的结点，也称为非终端结点。 p 孩子结点：一个结点的直接后继称为该结点的孩子结点。p 双亲结点：一个结点的直接前驱称为该结点的双亲结点。p兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。 p祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。p子孙结点：以某结点为根的子树中的任一结点都称为该结点的子孙

22、。p结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。 p树的高度（深度）： 树中所有结点的层次的最大值。 p 有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。否则称为无序树 。p 森林：m（m0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。 6.4.2 二叉树1 二叉树的定义 定义：我们把满足以下两个条件的树形结构叫做二叉树（Binary Tree）： （1） 每个结点至多只有二棵子树（即度都不大于2）； （2）二叉树的子树有左右之分，其次序不能任意颠倒。 位于左边的孩

23、子叫做左孩子，位于右边的孩子叫做右孩子。 二叉树的五种基本形态。 (a) 空二叉树(b) 只有根结点 的二叉树(c) 只有左子树 的二叉树(d) 左右子树均非 空的二叉树(e) 只有右子树的二叉树满二叉树：深度为k且有2k-1个结点的二叉树。 在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。 满二叉树的顺序表示，即从二叉树的根开始，按照从上到下、从左到右的顺序逐层进行编号（1， 2， ， n）。 完全二叉树：深度为k，结点数为n的二叉树，如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应。满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树。 完全二叉树的特点：

24、叶子只能在层次最大的两层上出现； 对任意一个结点，右分支下的子孙的最大层次为L，则左分支为L或L+1 。2 二叉树的性质 性质1: 在二叉树的第i层上至多有2i-1个结点(i1)。性质2: 深度为k的二叉树至多有2k-1个结点（k1）。性质3: 对任意一棵二叉树T，若终端结点数为n0，而其度数为2的 结点数为n2，则n0=n2+1。 性质4：具有n个结点的完全二叉树的深度为log2n+1。 性质5: 对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号， 则对于任意的序号为i的结点有： （1） 如i=1，则序号为i的结点是根结点，无双亲结点；如i1

25、，则序号为i的结点的双亲结点序号为i/2。 （2） 如2in，则序号为i的结点无左孩子；如2in，则序号为i的结点的左孩子结点的序号为2i。 （3）如2i1n，则序号为i的结点无右孩子；如2i1n，则序号为i的结点的右孩子结点的序号为2i1。 3 二叉树的存储 二叉树的结构是非线性的， 每一结点最多可有两个后继。二叉树的存储结构有两种： 顺序存储结构和链式存储结构。 1.顺序存储结构 用一组地址连续的存储单元，依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i 的结点元素存储在数组的第i 1个分量中。 完全二叉树与顺序存储结构 2. 链式存储结构 对于任意的二叉树来说，

26、每个结点只有两个孩子，一个双亲结点。我们可以设计每个结点至少包括三个域：数据域、 左孩子域和右孩子域： LChildDataRChildtypedef struct BiTNodeTElemType data; struct BiTNode *LChild; struct BiTNode *RChild; BiTNode, *BiTree; 有时，为了便于找到父结点，可以增加一个Parent域，Parent域指向该结点的父结点。该结点结构如下： LChildDataparentRChild二叉树和二叉链表 BCDGEFADEFCBGA(a) 二叉树T(b) 二叉树 T 的二叉链表4. 二叉树的

27、遍历 遍历二叉树：按某种搜索路径，使二叉树每个结点均被访问一次，且仅被访问一次。 遍历需寻找某种规律，使二叉树的结点能排列在一个线性队列上 。 （1）先序遍历（DLR）： 若二叉树为空，则空操作，否则依次执行如下3个操作 (1) 访问根结点； (2) 按先序遍历其左子树； (3) 按先序遍历其右子树。 （2）中序遍历（LDR）操作过程： 若二叉树为空，则空操作，否则依次执行如下3个操作： (1) 按中序遍历左子树； (2) 访问根结点； (3) 按中序遍历右子树。 （3） 后序遍历（LRD）操作过程： 若二叉树为空，则空操作，否则依次执行如下3个操作： (1) 按后序遍历左子树； (2) 按后

28、序遍历右子树； (3) 访问根结点。 树的主要存储方法有以下三种： 1. 双亲表示法 这种方法用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置， 其结点的结构如下： DataParent数据 双亲 6.4.3 树的存储 树的双亲表示法 2. 孩子表示法 这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。n个结点共有n个孩子链表（叶子结点的孩子链表为空表），而n个结点的数据和n个孩子链表的头指针又组成一个顺序表。 3. 孩子兄弟表示法链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。 1. 树的遍历 树的遍

29、历方法主要有以下两种： 1） 先根遍历 若树非空，则遍历方法为： (1) 访问根结点。 (2) 从左到右，依次先根遍历根结点的每一棵子树。 2） 后根遍历 若树非空，则遍历方法为： （1） 从左到右，依次后根遍历根结点的每一棵子树。 （2） 访问根结点。 6.4.4 树和森林的遍历先根遍历序列：ABECFHGD。 后根遍历序列：EBHFGCDA。 ACBDEFGH2. 森林的遍历 森林的遍历方法主要有以下两种： 1） 先序遍历 若森林非空，则遍历方法为： (1) 访问森林中第一棵树的根结点。 (2) 先序遍历第一棵树的根结点的子树森林。 (3) 先序遍历除去第一棵树之后剩余的树构成的森林。 2

30、） 中序遍历 若森林非空， 则遍历方法为： (1) 中序遍历森林中第一棵树的根结点的子树森林。 (2) 访问第一棵树的根结点。 (3) 中序遍历除去第一棵树之后剩余的树构成的森林。 先序遍历序列：ABCDEFGHIJ。 中序遍历序列：BCDAFEHJIG。 邻接点：边的两个顶点邻接点：边的两个顶点关联边：若边关联边：若边e= (v, u), e= (v, u), 则称顶点则称顶点v v、u u 关联边关联边顶点的度顶点的度在无向图中在无向图中, ,顶点顶点V V的度的度 = = 与与V V相关联的边的数目，记作相关联的边的数目，记作TD(V)TD(V)在有向图中在有向图中, ,顶点顶点V V的

31、度的度= V= V的出度的出度+V+V的入度的入度顶点顶点V V的出度的出度= =以以V V为起点有向边数为起点有向边数顶点顶点V V的入度的入度= =以以V V为终点有向边数为终点有向边数2. 图的基本术语 V0 V4 V3 V1 V2 V0 V1 V2 V36.5 图 V0 V4 V3 V1 V2 V0 V1 V2 V3完全图完全图： 无向完全图：无向完全图：任意两顶点间都有边的图。任意两顶点间都有边的图。 在一个含有在一个含有n n个顶点的无向完全图中，有个顶点的无向完全图中，有n(n-1)/2n(n-1)/2条边。条边。 有向完全图有向完全图:任意两顶点之间都有方向互为相反的两条弧相连

32、接的有向图。任意两顶点之间都有方向互为相反的两条弧相连接的有向图。 在一个含有在一个含有n n个顶点的有向完全图中，有个顶点的有向完全图中，有n(n-1)n(n-1)条弧。条弧。2. 图的基本术语 V0 V4 V3 V1 V2 V0 V1 V2 V3 路径路径GG中的中的顶点序列顶点序列v v1 1,v,v2 2, , ,v ,vk k, ,若各边若各边(v(vi i,v,vi+1i+1) ) E, E, 则称该序列是从顶点则称该序列是从顶点v v1 1到顶点到顶点v vk k的路径；的路径； 回路回路若路径的顶点和终点相同，则称回路。若路径的顶点和终点相同，则称回路。 简单路径简单路径 在一

33、条路径中在一条路径中,若除起点和终点外若除起点和终点外,所有顶点所有顶点各不相同各不相同,则该路径为简单路径；则该路径为简单路径； 简单回路简单回路由简单路径组成的回路称为简单回路；由简单路径组成的回路称为简单回路；路径和回路(a)(b)(c) V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 设有两个图设有两个图G=（V，E）、）、G1=（V1，E1），若），若V1 V，E1 E，E1关联的顶点都在关联的顶点都在V1中，则称中，则称 G1是是G的的子图子图；例例 (b)、(c) 是是 (a) 的子图的子图子图 非连通图 连通图 强连通图 非强连通图 V

34、0 V1 V2 V3 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V2 V3 V1 V5 V4 在无（有）向图在无（有）向图G=中，若中，若对任何两个顶点对任何两个顶点 v、u 都存在从都存在从v 到到 u 的路径的路径，则称，则称G是是连通图连通图对有向图而言，称对有向图而言，称强连通图强连通图连通图、强连通图连通分量非连通图 V0 V2 V3 V1 V5 V4无向图G 的极大连通子图称为G的连通分量极大连通子图：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通；强连通分量 V0 V1 V2 V3 V0 V2 V3 V1有向图有向图D 的极大强连通子图

35、称为的极大强连通子图称为D 的强连通分量的强连通分量极大强连通子图极大强连通子图：该子图是：该子图是D的强连通子图，将的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强的任何不在该子图中的顶点加入，子图不再是强连通的；连通的；连通图 G1G1的生成树 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2生成树 包含无向图G 所有顶点的的极小连通子图称为G 的生成树。 极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。 若T是G 的生成树当且仅当T 满足如下条件： T是G 的连通子图 T包含G 的所有顶点 T中无回路 边的

36、权：在图的边或弧上表示数字，表示与该边边的权：在图的边或弧上表示数字，表示与该边相关的数据信息，这个数据信息就称该边的权相关的数据信息，这个数据信息就称该边的权（weightweight）。）。 网（网（networknetwork）：边（或弧）上带权的图称为网。）：边（或弧）上带权的图称为网。 V0 V4 V3 V1 V2824653图的存储结构要保存两类信息：1)顶点的数据2)顶点间的关系 V0 V4 V3 V1 V2 V0 V1 V2 V3邻接矩阵表示法邻接表表示法V0V1V2V3V46.5.2 图的存储Aij=1 若(vi,vi+1)E 或 E0 否则0 1 0 1 010 1 0 1

37、0 1 0 1 110 1 0 00 1 1 0 00 1 1 00 0 0 00 0 0 110 0 0 V0 V4 V3 V1 V2 V0 V1 V2 V3图图G的邻接矩阵是满足如下条件：的邻接矩阵是满足如下条件：V0 V1 V2 V3 V4V0 V1 V2 V31. 邻接矩阵0 1 0 1 010 1 0 10 1 0 1 110 1 0 00 1 1 0 0邻接矩阵表示法的空间代价只与图的顶点数有关 V0 V4 V3 V1 V21）无向图邻接矩阵是）无向图邻接矩阵是对称矩阵对称矩阵，可考虑矩阵的压缩存储，可考虑矩阵的压缩存储2）G占用存储空间只与它的顶点数有关，与边数无关；占用存储空间

38、只与它的顶点数有关，与边数无关； 适用于边稠密的图适用于边稠密的图V0 V1 V2 V3 V4邻接矩阵表示的特点 V0 V4 V3 V1 V22 0 1 2 3 4m-1V0V1V2V3V413422110034下标 编号 指针2.2.邻接邻接表表示表表示1. 无向图的邻接表无向图的邻接表 顶点：通常按编号顺序将顶点数据存储在一维数组中；顶点：通常按编号顺序将顶点数据存储在一维数组中； 关联同一顶点的边：用关联同一顶点的边：用线性链表线性链表存储存储表头数据表头数据指向邻接表的指向邻接表的指针指针邻接结点邻接结点数据数据指向下一邻接指向下一邻接点的指针点的指针1）有向图的邻接表（出边表）顶点：

39、用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储下标 编号 指针 V0V1V2V31230 0 1 2 3m-1 V0 V1 V2 V3有向图的邻接表和逆邻接表2）有向图的逆邻接表（入边表）顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储V0V1V2V3 0 1 2 3m-10023 V0 V1 V2 V3有向图的邻接表和逆邻接表 采用怎样的策略进行图的遍历 有两种遍历方法： 深度优先遍历（DFS：Depth First Search） 广度优先遍历（BFS：Breadth First Search）6.5.3 图的图的遍历遍历 图的遍历：从图的某顶点出发

40、，访问图中所有顶图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。点，并且每个顶点仅访问一次。 V0 V7 V6 V5 V4 V3 V2 V1 V0 V1 V3 V2 V7 V6 V5 V4 一 、深度优先遍历（DFS）1）从图中某顶点v出发，访问顶点v；2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历； V0,V1,V3,V7,V4,V2,V5,V6 由于没有规定访问邻接点的顺序，DFS序列不唯一例求图G以V0起点的深度优先序列：V0,V1,V4,V7,V3,V2,V5,V6 V0 V7 V6 V5 V4 V3 V2 V1 V0 V1 V3 V2 V7 V6

41、V5 V4图中某未访问过的顶点vi出发：1）访问顶点vi ；2）访问 vi 的所有未被访问的邻接点w1 ,w2 , wk ；3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 直到图中所有访问过的顶点的邻接点都被访问；二、广度优先遍历（BFS） V0 V7 V6 V5 V4 V3 V2 V1V0 V1 V3 V2 V7 V6 V5 V4由于没有规定访问邻接点的顺序，BFS序列不唯一例求图G 的以V0起点的的广度优先序列:V0,V1,V2,V3,V4,V5,V6,V7 V0 V7 V6 V5 V4 V3 V2 V1 V0 V1 V3 V2 V7 V6 V5 V46.5.4 6.5.4 最

42、小生成树最小生成树 设G =(V,E)是无向连通带权图，即一个网络网络。 E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树生成树。 生成树上各边权的总和称为该生成树的耗费耗费。 在G的所有生成树中，耗费最小的生成树称为G的最小生成树最小生成树。 网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。 最小生成树的应用 设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)是一条具有最小代价的边，且u

43、U，vV-U，则必存在一棵包含边(u,v)的最小生成树。这个性质简称为MST性质。 本节介绍的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了上面的最小生成树性质。1 1、最小生成树性质、最小生成树性质 设G=(V,E)是连通带权图，V=1,2,n。 Prim算法的基本思想基本思想是： （1）首先置S=1，生成树边集T= ； （2）然后，只要S是V的真子集，就作如下的贪心选择：贪心选择：选取满足条件选取满足条件i i S S，j j V-SV-S，且，且cijcij最小的边，将顶点最小的边，将顶点j j添加到添加到S S中

44、中, ,将边将边（i,j)i,j)加入加入T T。 这个过程一直进行到S=V时为止。 在这个过程中选取到的所有边恰好构成G的一棵最小生成树最小生成树。 2 2、PrimPrim算法算法3.Kruskal3.Kruskal算法算法贪心策略：总是选择最小代价连通两个不同的连通分贪心策略：总是选择最小代价连通两个不同的连通分支。支。基本思想基本思想：（1）首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。（2）然后从第一条边开始，依边权递增的顺序查看每一条边(v,w) ： （a)如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就保留边(v,w) (b)如果端点v和

45、w在当前的同一个连通分支中，就直接丢弃边(v,w)。 这个过程一直进行到只剩下一个连通分支时为止。6.5.5 6.5.5 最短路径最短路径 给定给定带权有向图带权有向图G =(V,E)G =(V,E)，其中每条边的权是，其中每条边的权是非负实数。另外，还给定非负实数。另外，还给定V V中的一个顶点，称为中的一个顶点，称为源源。现在要计算从源到所有其它各顶点的现在要计算从源到所有其它各顶点的最短路长度最短路长度。这里路的长度是指路上各边权之和。这个问题通常这里路的长度是指路上各边权之和。这个问题通常称为称为单源最短路径问题单源最短路径问题。例如例如，对右图中的有向图，应用Dijkstra算法计算

46、从源顶点1到其它顶点间最短路径。0 10 30 100 0 50 0 10 20 0 60 0用邻接矩阵表示如右图：Dijkstra 算法p 令S=源点s + 已经确定了最短路径的顶点vip 对任一未收录的顶点v，定义distv为s到v的最短路径长度，但该路径仅经过S中的顶点。p 若路径是按照递增（非递减）的顺序生成的，则真正的最短路必须只经过S中的顶点每次从未收录的顶点中选一个dist最小的收录增加一个v进入S，可能影响另外一个w的dist值！ distw = mindistw, distv + 的权重（为什么？）贪心 插入排序的基本思想是：在一个已排好序的记录子集的基础上，每一步将下一个待

47、排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。 打扑克牌时的抓牌就是插入排序一个很好的例子，每摸一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序序列。 6.6 排序1. 直接插入排序012345678486235775514359848623577551435983562485577621477625548353577625548p稳定性：p空间复杂度：只需一个记录的辅助空间，空间复杂度 O(1)。p时间复杂度：主要时间耗费在关键字比较和移动元素上。最好情况：顺序T = O( N )最坏情况：逆序T = O( N2 ) 直接插入排序方法是稳定的排序方法。直

48、接插入排序方法是稳定的排序方法。 直接插入排序算法简便，比较适用于待排序记录待排序记录数目较少且基本有序数目较少且基本有序的情况。当待排记录数目较大时，直接插入排序的性能就不好，为此我们可以对直接插入排序做进一步的改进。在直接插入排序法的基础上，从减少减少“比较关键字比较关键字”和和“移动记录移动记录”两种操作的次数着手来进行改进。 2. 冒泡排序冒泡排序4862357755143598224048623577551435982240483562775514359822404835627755143598224048356255771435982240483562551477359822404

49、8356255143577982240483562551435779822404835625514357722984048356255143577224098(a) 一趟冒泡排序示例4835353514141435484814353522625514353522351414354822353535552240776222402222404040(b) 冒泡排序全过程55354048556277983. 简单简单选择排序选择排序 基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并与第i个记录进行交换。共需进行i-1趟比较，直到所有记录排序完成为止。 时间复杂度为O(n2)如何快速找到最小元？如何快速找到最小元？4862357755143598ik146235775548