试谈数据结构研究

1、数据结构研究什么数据处理中数据之间的逻辑关系、数据在计算机中的存储方式和在这种“结构”上能进行的操作(运算)。如何表示数据，如何存储数据，如何对数据进行处理3种逻辑结结构线性结构树树形结构构(图结结构线性结构的的性质和和概念性质：全序性：线线性结构构的全部部结点两两两都可可以比较较前后关关系。单索性：除除头结点点外，每每个结点点有唯一一的直接接前驱结结点；除除尾结点点外，每每个结点点有唯一一的直接接后继结结点。概念：直接前驱、直接后后继结点点：前后后相邻的的结点；前驱、后继继结点：前面、后后面的结结点。在不混淆的的前提下下，直接接前驱和和直接后后继可简简称为前前驱和后后继。树结构的性性质和概概

2、念性质和概念念：根结点：“树的根根”，一棵棵树只有有唯一的的一个根根结点。叶子结点：“树的叶叶子”，一棵棵树有很很多叶子子。除根结点外外，每个个结点有有唯一的的父结点点；除叶叶子结点点外，每每个结点点允许有有多个子子结点。父亲结点，子女结结点，兄弟结结点，祖先结结点，子孙结结点。树结构是一一棵“倒立的的树”。4种存储结结构顺序结构的的优缺点点用一块连续续的、无间隙隙的存储储空间按按顺序存存储各结结点。各结点地址址计算方方法(问问题1)：结点i的地地址 = 起始始地址 + ii每个结结点所占占存储空空间大小小各结点之间间逻辑关关系表示示(问题题2)：地址相相邻关系系就表达达了结点点之间的的逻辑关

3、关系。顺序存储结结构是在在内存中中开辟一一个连续续的空间间用来存存储数据据,因此此对于内内存的需需求和苛苛刻,必必须是连连续的空空间.在在数据查查找(特特别是不不按照规规律排列列的数据据),时时间复杂杂度教少少.效率率高. 链式结构的的优缺点点链式存储结结构是采采取连表表指针来来指示数数据的存存储位置置,这就就可以是是在内存存中随意意的存储储,没有有必须连连续储存存空间的的要求,对于内内存的要要求相对对教容易易.但是是要是是是从小到到大顺序序排列的的数据,链式存存储结构构的时间间复杂度度教小,效率高高.但是是要是不不规则排排布的数数据一般般时间复复杂度较较高,效效率更低低算法渐进复复杂度的的表

4、示方方法算法时间复复杂度的的渐进分分析：在在时间复复杂度tt(n)中，剔剔除不会会从实质质上改变变函数数数量级的的项，经经过这样样处理得得到的函函数是tt(n)的近似似效率值值，但这这个近似似值与原原函数已已经足够够接近，当当问题规规模很大大时尤其其如此。这这种效率率的度量量就称为为算法的的渐进复复杂度。(在不引引起混淆淆的情况况下，也也可简称称时间复复杂度)算法的最好好、最坏坏和平均均时间复复杂度算法的复杂杂度往往往取决于于输入数数据，例例如一个个排序算算法的时时间复杂杂度往往往取决于于输入数数据的原原始有序序程度。因因此分析析算法复复杂度时时往往要要区分最最好情况况、最坏情情况和平均情情况

5、。例如，在一一个包含含n个元元素的数数组中查查找某个个数据(假定该该数据是是数组元元素)：最好情况：该数据据就是第第0个元元素，只只需比较较1次就就可以结结束了，其其复杂度度为O(1)。最坏情况：该数据据是数组组最后一一个元素素，则需需要比较较n次，其其复杂度度为O(n) 。评均情况：假设需需要查找找的数据据是第00个元素素、第11个元素素、最后后一个元元素的概概率相等等，则平平均需要要查找的的次数为为：11/nn + 21/nn + + n1/nn = (n+1)/2。其其复杂度度为O(n)。基本的算法法复杂度度类型线性表、顺顺序表、链链表、栈栈和队列列的基本本概念线性表是一一类线性性（区别

6、别于树型型结构和和图结构构）数据据结构，它它有多种种存储结结构和应应用方法法，从而而可以细细分为顺顺序表、链表、队列、栈等。“线性表”是从逻辑辑结构的的角度来来描述数数据结构构的，它它主要有有两种存存储结构构：顺序序存储结结构和链式存存储结构构。顺序表(ssequuenttiall liist)又称为为向量(vvecttor)，它采采用定长长的一维维数组存存储结构构。向量的主要要特性：元素的类型型相同。元素顺序地地存储在在一块有有连续地地址的存存储空间间中，每每一个元元素按其其顺序有有唯一的的索引值值，又称称下标值值，用它它可以方方便地访访问元素素内容。STL提供供了3种种通用实实体：容器、迭

7、代器器和算法。链表(liinkeed lisst)的的特点是是动态申申请内存存空间，并并通过指指针来链链接结点点，按照照线性表表的前驱驱/后继继关系把把一个个个结点链链接起来来。几种用于线线性表的的链式存存储结构构：单链表；双链表；循环单链表表；循环双链表表。链表存储是是最常用用的存储储方式之之一，它它不仅可可以用来来表示线线性表，而且也也可以用用于其他他非线性性的数据据结构中中，如树树结构和和图结构构。栈(staack)是一种种限制访访问端口口的线性性表，常常称为后后进先出出表(LIFFOLLastt Inn, FFirsst OOut)。栈的一端称称为“栈顶”，表元素素的插入入和删除除均限

8、制制在栈顶顶；表的的另一端端成为“栈底”。表元素的插插入，成成为压栈栈(pussh)。表元素的删删除，称称为出栈栈(popp)。队列(quueuee)也属属于限制制访问端端口的线线性表。数数据进入入/取出出的方式式为先进进先出表表(FIIFOFirrst In, Fiirstt Ouut)，因因此队列列也称为为先进先先出表。只允许从队队列尾(reaar)进入数数据。只允许从队队列头(froont)取出数数据。顺序表的抽抽象数据据类型：插入元元素/插入一一个元素素，使之之成为第第inddex个个元素templlatee void Vecctorr:iinseert( coonstt ELLEM&

9、 ittem, innt iindeex )asseert( Siize=00 & inndexxinddex; i- )/移移动元素素elmmlisstii = ellmliisti-11;elmllisttinndexx = ittem;Sizee+;顺序表的抽抽象数据据类型：删除元元素templlatee void Vecctorr:rremoove( innt iindeex )/删删除第iindeex个元元素asseert( inndexx=00 & inndexxSiize );for( innt ii=inndexx; iiSiize-1; i+ )/移移动元素素elmmliss

10、tii = ellmliisti+11;Sizee-;顺序表的优优缺点优点：直接存储元元素，每每个元素素不需要要存储指指针等其其他信息息。直接访问元元素，访访问第kk个元素素的时间间为O(1)，与与n无关关。缺点：插入新元素素需要移移动大量量的元素素，复杂杂度为OO(n)。删除元素也也需要移移动大量量的元素素，复杂杂度为OO(n)。顺序表的缺缺点之一一：插入新新元素时时需要移移动大量量的元素素。设顺序表的的长度为为n，在各各个位置置插入的的概率相相等，则则插入算算法平均均需要移移动n/2个元元素。其其复杂度度为O(n)。顺序表的缺缺点之二二：删除元元素时需需要移动动大量的的元素。删除算法的的复

11、杂度度也为OO(n) 。单链表的理理解在单链表中中，每个个结点由由两部分分组成：存放结点数数据的ddataa域；存放指向后后继结点点的neext指指针域。因为每个结结点中只只有指向向后继结结点的指指针，因因此由这这种结点点链接而而成的链链表，称称为单链链表。表首指针ffirsst：指指向单链链表中第第0个结结点(结结点序号号从0开开始计起起)。单链表的抽抽象数据据类型：释放所所有结点点单链表的抽抽象数据据类型：插入结结点单链表的抽抽象数据据类型：删除结结点单链表的优优缺点双链表的理理解双链表的抽抽象数据据类型：插入结结点(简简单情形形)双链表的抽抽象数据据类型：删除结结点(简简单情形形)栈的理

12、解STL中的的栈栈的应用11：十进进制整数数转换成成二进制制栈的应用22：括号号匹配顺序栈的理理解顺序栈的抽抽象数据据类型：压栈顺序栈的抽抽象数据据类型：出栈顺序栈的抽抽象数据据类型：取出栈栈顶结点点顺序栈的抽抽象数据据类型：判空链式栈的理理解链式栈的抽抽象数据据类型：释放所所有结点点链式栈的抽抽象数据据类型：压栈链式栈的抽抽象数据据类型：出栈链式栈的抽抽象数据据类型：取出栈栈顶结点点链式栈的抽抽象数据据类型：判空顺序栈和链链式栈的的比较计算表达式式的值：中缀表表达式后缀表表达式(不要求记记忆算法法执行过过程)计算表达式式的值：计算后后缀表达达式的值值队列的理解解STL中的的队列队列的应用用：

13、BFFS的实实现顺序队列的的理解顺序队列的的抽象数数据类型型：入队队列顺序队列的的抽象数数据类型型：出队队列顺序队列的的抽象数数据类型型：取出出队列头头结点链式队列的的理解链式队列的的抽象数数据类型型：入队队列链式队列的的抽象数数据类型型：出队队列链式队列的的抽象数数据类型型：取出出队列头头结点顺序队列和和链式队队列的比比较第3章 字字符串编号知识识点类型掌握程程度代码要要求3_01字符串串的模式式匹配概念理解字符串的模模式匹配配：给定定目标字字符串TT(Taargeet)和和一个模模板P(Pattterrn)，也也是字符符串，在在目标字字符串TT中查找找与模板板完全相相同的子子串，返返回T中

14、中和P匹匹配的第第一个子子串(简简称为配配串)的的首字符符位置。3_02朴素的的模式匹匹配算法法算法掌握原原理代码段段第0趟开始始比较。在在第0趟趟，将模模板P的的第0个个字符对对准T的的第0个字符，将将两字符符串对应应位置上上的字符符一一比比较，如如果匹配配成功则结束，否否则(即即匹配失失败)将将P右移移一个位位置进入入第1趟趟比较，。第s趟趟比较是是从T的的第s个个字符和和P的第第0个字字符开始始比较。反复进行每每一趟的的比较，直直到出现现以下情情况：执行到某一一趟，模模板所有有字符与与目标串串中对应应的字符符都相等等，匹配配成功。模式移动到到最后可可能与TT比较的的位置，但但还不能能匹配

15、，则则匹配失失败。3_03KMPP算法：模式串串前缀函函数值的的人工求求解算法掌握原原理3_04KMPP算法：模式串串前缀函函数值的的推导算法掌握原原理3_05KMPP算法：模式串串前缀函函数值的的求解算法掌握原原理代码段段3_06KMPP算法：实现算法掌握原原理代码段段第4章 二二叉树编号知识识点类型掌握程程度代码要要求4_01树与子子树概念理解4_02二叉树树的定义义概念理解4_03二叉树树的基本本概念概念理解4_04满二叉叉树概念理解4_05完全二二叉树概念理解4_06扩充二二叉树概念理解4_07扩充二二叉树的的外部路路径长度度和内部部路径长长度计算掌握方方法4_08扩充二二叉树的的性质

16、性质理解4_09二叉树树性质11(满二二叉树定定理)性质理解4_10二叉树树性质22(满二二叉树定定理推论论)性质理解4_11二叉树树性质33性质理解4_12二叉树树性质44性质理解4_13二叉树树性质55性质理解4_14二叉树树性质66性质理解4_15二叉树树的二叉叉链表实实现原理掌握4_16二叉树树的二叉叉链表实实现：从从二叉树树根结点点出发，查查找指定定结点的的父结点点算法掌握原原理代码段段4_17二叉树树的二叉叉链表实实现：返返回指定定结点左左兄弟算法掌握原原理代码段段4_18二叉树树的二叉叉链表实实现：返返回指定定结点右右兄弟算法掌握原原理代码段段4_19二叉树树的二叉叉链表实实现：

17、删删除二叉叉树的递递归算法法算法掌握原原理代码段段4_20二叉树树的遍历历概念理解4_21二叉树树的前序序(中序序、后序序)遍历历算法掌握原原理4_22前序(中序、后后序)遍遍历的递递归实现现算法掌握原原理代码段段4_23前序遍遍历的非非递归实实现算法掌握原原理代码段段4_24三叉链链表原理掌握4_25完全二二叉树的的数组实实现性质理解4_26二叉链链表及线线索二叉叉链表性性质性质理解4_27前序(中序或或后序)线索二二叉树原理掌握原原理4_28二叉搜搜索树：定义概念理解4_29给定关关键码序序列，构构造二叉叉搜索树树算法掌握原原理4_30二叉搜搜索树：插入结结点算法掌握原原理代码段段4_31

18、二叉搜搜索树：删除结结点算法掌握原原理代码段段4_32二叉搜搜索树：查找结结点算法掌握原原理代码段段4_33STLL优先级级队列应用掌握方方法完整程程序4_34最小(大)堆堆定义概念理解4_35堆的创创建筛筛选法算法掌握原原理4_36堆的操操作：插插入结点点算法掌握原原理4_37堆的操操作：删删除结点点算法掌握原原理4_38前缀编编码概念理解4_39加权平平均编码码长度概念理解4_40Hufffmaan树加加权外部部路径长长度概念理解4_41构造HHufffmann树算法掌握原原理编号知识识点5_01森林的的概念森林(fooresst)：由零棵棵或多棵棵不相交交的树组组成的集集合。注意：自然然

19、界中的的树和森森林是不不同的概概念。而而数据结结构中的的树和森森领只有有微小的的差别，删去根根结点，则则树就变变成森林林；加上一一个结点点作为根根，则森森林就变变成树。在树或森林林与二叉叉树之间间存在一一个自然然的、一一一对应应的关系系。任何何树或森森林都唯唯一地对对应到一一棵二叉叉树；反反过来，任任何二叉叉树也都都唯一地地对应到到一棵树树或一个个森林。5_02一般树树转换成成二叉树树把一般树转转换成二二叉树，可可分为33个步骤骤：连线：在所所有兄相相邻的弟弟结点之之间加一一条连线线。切线：对树树中的每每个结点点，只保保留他与与第一个个子女结结点之间间的连线线，删除除它与其其它子女女结点之之间

20、的连连线。旋转：以树树及子树树的根结结点为轴轴心，将将所有水水平方向向的连线线顺时针针旋转一一定角度度，使之之结构层层次分明明。(也也就是所所有水平平方向连连线中右右边的结结点作为为左边结结点的右右子女结结点)5_03森林转转换成二二叉树把森林转换换成二叉叉树，可可分为33个步骤骤：连线：在每每棵树的的所有兄兄弟结点点之间加加一条连连线，并并将每棵棵树的根根结点用用水平线线连接(与将一一般树转转换成二二叉树相相比，这这是唯一一增加的的操作)。切线：对树树中的每每个结点点，只保保留他与与第一个个子女结结点之间间的连线线，删除除它与其其它子女女结点之之间的连连线。旋转：以树树及子树树的根结结点为轴

21、轴心，将将所有水水平方向向的连线线顺时针针旋转一一定角度度，使之之结构层层次分明明。(也也就是所所有水平平方向连连线中右右边的结结点作为为左边结结点的右右子女结结点)5_04二叉树树还原为为一般树树把二叉树还还原成一一般树，可可分为33个步骤骤：连线：如果果某结点点N是其其父结点点的左子子女结点点，则将该该结点的的右子女女及沿着着其右指指针不断断搜索到到的右子子孙，都都分别与与结点NN的父结结点用虚虚线连接接。切线：去掉掉原二叉叉树中每每个结点点与其右右子女结结点之间间的连线线，仅保保留与左左子女结结点之间间的连线线。整理：把虚虚线改为为实线，按层次整理好。5_05二叉树树还原为为森林把二叉树

22、还还原成森森林，可可分为22个步骤骤：切线：先从从根结点点出发沿沿着其右右指针不不断遍历历到的所所有右子子孙，将将每个右右子孙结结点N与与N的父父结点的的连线去去掉，得得到分离离的二叉叉树。还原：把分分离后的的每棵二二叉树还还原为一一般树。所所有的这这些一般般树就组组成了森森林。5_06树的动动态“左子结结点/右右兄弟结结点”二叉链链表表示示5_07树的先先根、后后根次序序遍历与二叉树的的深度优优先遍历历有3种种次序不不同的是是：树的的深度优优先遍历历只有先先根次序序和后根次次序，不方便便按照中中序法定定义中根根次序，因因为一个个根结点点有多于于两个子子结点时时无法明明确给出出根结点点和这些些

23、子结点点的次序序。先根次序遍遍历的递归定定义为：访问根结点点；按先根次序序遍历第第一棵子子树；按先根次序序遍历其其他子树树。后根次序遍遍历的递归定定义为：按先根次序序遍历第第一棵子子树；访问根结点点；按先根次序序遍历其其他子树树。(注意理解解“后根”)按先根次序序遍历树树，等价价于按先先序遍历历对应的的二叉树树；按后根根次序遍遍历树，等等价于按按中序遍历历对应的的二叉树树。即：树的先根次次序遍历历对应二二叉树的的先序遍遍历(表等价价)树的后根次次序遍历历对应二二叉树的的中序遍遍历5_08树的广广度优先先遍历广度优先遍遍历也称称为宽度度优先遍遍历，或或层次遍遍历。广度优先遍遍历过程程为：首首先依

24、次次访问层层次为00的结点点；然后后依次访访问层次次为1的的结点，等等等。5_09树的子子结点表表表示法法子结点(链链)表表表示法包包含以下下两部分分：用数组存储储每个结结点，每每个结点点包含33个域：结点值值、父结点点编号、子结点点链表表表头指针针顺序存存储方式式。将每个结点点的子结结点按从从左到右右的顺序序连接成成一个单单链表，并并用它的的表头指指针域指指向这个个链表链式存存储方式式。优点：访问问每个结结点的所所有子结结点很方方便。缺点：访问问每个结结点的兄兄弟结点点很难实实现。其他操作讨讨论：插插入结点点、删除除结点、创创建树、删删除树、按按各种方方式遍历历、合并并两棵树树等等。5_10

25、树的父父指针表表示法实现树的最最简单方方法是对对每个结结点只保保存一个个指针域域parrentt，指向向其父结结点，这这种实现现方法称称为父指指针表示示法。父指针表示示法在实实现树的的操作方方面没有有任何优优势，但但是它可可以实现现一种特特殊的数数据结构构并查查集。5_11等价关关系及等等价类“同班同学学”、“同属于于一个集集合”、“森林中中两个顶顶点属于于同一棵棵树”都是等价价关系。等价关系(equuivaalennt rrelaatioon)的的三个条条件(或或称为性性质)：自反性：如如XX，则则XX；(假设用用“XY”表示“X与YY等价”)对称性：如如XY，则则YX；传递性：如如XY，且

26、且YZ，则则XZ。如果XYY，则称称X与YY是一个个等价对对(eqquivvaleencee)。5_12并查集集的概念念及作用用判定两个顶顶点是否否属于同同一个等等价类(或集合合，或同同一棵树树)。将两个等价价类(或或两个集集合，或或两棵树树)合并并。一个等价关关系R将将集合AA划分成成为若干干个子集集合，这些子子集合互互不相交交，且这些些子集合合的并集集就是AA。5_13并查集集的三个个重要运运算查找(Fiind)：查找一一个元素素属于哪哪个集合合。判断：判断断两个元元素是否否属于同同一个集集合。往往往包含含在合并并运算中中。合并(Unnionn)：合并两两个集合合。5_14用父指指针表示示

27、法实现现并查集集的思路路和方法法要判别每个个结点属属于哪棵棵树，只只需要记记录每个个结点的的父结点点编号(不需要要记录每每个结点点的其他他信息，比比如左子子女、右右兄弟等等)。对对于每棵棵树的根根结点，由由于它没没有父结结点，则则可以用用它所在在的树中中结点数数目代替替它的父父结点编编号(并并取负值值，假定定结点的的编号没没有负值值)。定义parrenttn数组，ppareenti中中存放的的就是结结点i所所在的树树中结点点i父亲亲结点的的序号。例例如，如如果paarennt44 = 5，就就是说44号结点点的父亲亲是5号号结点。约定：如果果结点ii的父结结点(即即parrentti)是负数数

28、的话，表表示结点点i就是是它所在在树的根根结点；并且用用负的绝绝对值作作为这棵棵树中所所含结点点个数。例例如，如如果paarennt77 = -44，说明明7号结结点就是是它所在在树的根根结点，这这棵树有有4个结结点。初始时，所所有结点点的paarennt 值为为-1，说说明每个个结点自自成一棵棵树，且且都是根根结点。对读入的每每个等价价对XY，先先判定结点点X和YY是否属属于同一一个集合合，如果果是，则则不管；如果不不是，则则合并结点点X和结结点Y所所在的集集合。(并查集集的3种种运算的的实现在在例3中讨讨论)5_15并查集集：查找找运算及及优化方方案的实实现5_16并查集集：合并并运算及及

29、优化方方案的实实现5_17并查集集应用第6章 图图结构编号知识识点类型掌握程程度代码要要求6_01图的基基本概念念概念理解图是由顶点点集合和和顶点间间关系集集合(即即边的集集合或弧的集集合)组组成的数数据结构构，通常常可以用用G(V,E)来表表示，其其顶点集集合和边边的集合合分别用用V(G)和E(G)表示示。V(G)中的的元素称称为顶点点，用u、v等符号号表示；顶点个个数称为为图的阶阶，通常常用n表示。EE(G)中的的元素称称为边，用e等符号号表示；边的个个数称为为图的边边数，通通常用mm表示。顶点的度(deggreee)：一个顶顶点的度度是与它它相关联联的边的的条数，记记作deeg(u) 在

30、有向向图中，顶顶点的度度等于该该顶点的的出度与与入度之之和。其其中，顶顶点u的出度度是以uu为起始始顶点的的有向边边(即从从顶点uu出发的的有向边边)的数数目，记记作odd(u)；顶顶点u的的入度是是以u为终点点的有向向边(即即进入到到顶点uu的有向向边)的的数目，记记作idd(u)。顶顶点u的度数数：deg(uu) = odd(u) + idd(u)。即在无向图图和有向向图中，所所有顶点点的度的的总和，等等于边的的数目的的两倍。这这是因为为，不管管是有向向图还是是无向图图，在统统计所有有顶点的的度的总总和时，每条边都统计了两次。生成树：一一个无向向连通图图的生成成树是它它的包含含所有顶顶点的

31、极极小连通通子图，这这里所谓谓的极小小就是边边的数目目极小。如如果图中中有n个顶点点，则生生成树有有n-1条条边。在图G(VV, E)中，若若从顶点点vi出发发，沿着着一些边边经过一一些顶点点vp1, vpp2, , vppm，到到达顶点点vj，则则称顶点点序列(vi, vp1, vpp2, vppm, vj)为为从顶点点vi到顶顶点vjj的一条条路径，其其中(vvi, vp1), (vp1, vpp2), , (vpmm, vjj)为图图G中的边边。如果果G是有向向图，则则, , , 为图图中的有有向边。路径的长度度：路径径中边的的数目通通常称为为路径的的长度。权值：某些些图的边边具有与与它

32、相关关的数，称称为权值值。这些些权值可可以表示示从一个个顶点到到另一个个顶点的的距离、花费的的代价、所需的的时间等等。如果果一个图图，其所所有边都都具有权权值，则则称为网网络。根据网络中中的边是是否具有有方向性性，又可可以分为为有向网网和无向网网。网络络可以用用G(V, E)表示示，其中中边的集集合E中中每个元元素包含含3个分分量：边边的两个个顶点和和权值。6_02图的邻邻接矩阵阵概念理解在邻接矩阵阵中，除除了一个个记录各各个顶点点信息的的顶点数数组外，还还有一个个表示各各顶点之之间关系系的矩阵阵，称为为邻接矩矩阵。6_03图的邻邻接表实实现算法掌握原原理代码段段邻接表：把把同一个个顶点发发出

33、的边边链接在在同一个个称为边边链表的的单链表表中。(这种邻邻接表也也称为出出边表)逆邻接表：也称为为入边表表，顶点点i的边边链表中中链接的的是所有有进入该该顶点的的边。适适合求顶顶点的入入度。以有向图为为例介绍绍邻接表表的实现现方法。为为了方便便求解顶顶点的出出度和入入度，在在实现时时，把出出边表和和入边表表同时包包含在表表示顶点点的结构构体中。6_04图的遍遍历概念理解图的遍历(Graaph Traaverrsall)的含含义：从从已给图图中的某某一顶点点出发，沿沿着一些些边访遍遍图中所所有的顶顶点，且且使每个个顶点仅仅被访问问一次(注意理理解)。6_05图的深深度优先先搜索算法掌握原原理深

34、度优先搜搜索(DDeptth FFirsst SSearrch)：是一一个递归归过程，有有回退过过程，它它的思想想在很多多题目当当中要用用到对图图6.44.1(a)所所示的无无向连通通图，采采用DFFS思想想搜索的的过程为为：(在图(aa)中，箭头旁的数字跟下面的序号对应)从顶点A出出发，访访问顶点点序号最最小的邻邻接顶点点，即顶顶点B；然后访问顶顶点B的的一个未未访问过过的邻接接顶点，即即顶点CC；(3) 接接着访问问顶点CC的一个个未访问问过的邻邻接顶点点，即顶顶点G；(4) 此此时顶点点G已经经没有未未访问过过的邻接接顶点了了，所以以回退到顶顶点C；(5) 回回退到顶顶点C后后，顶点点C

35、也没没有未访访问过的的邻接顶顶点了，所所以继续续回退到到顶点BB；。6) 顶顶点B还还有一个个未访问问过的邻邻接顶点点，即顶顶点E，所所以访问问顶点EE；(7) 然然后访问问顶点EE的一个个未访问问过的邻邻接顶点点，即顶顶点F；(8) 顶顶点F有有两个未未访问过过的邻接接顶点，选择顶点序号最小的，即顶点D，所以访问D；(9) 此此时顶点点D已经经没有未未访问过过的邻接接顶点了了，所以以回退到顶顶点F；(10) 顶点FF还有一一个未访访问过的的邻接顶顶点，即即顶点HH，所以以访问顶顶点H；(11) 然后访访问顶点点H的一一个未访访问过的的邻接顶顶点，即即顶点II；(12) 此时顶顶点I已已经没有

36、有未访问问过的邻邻接顶点点了，所所以回退退到顶点点H；(13) 回退到到顶点HH后，顶顶点H也也没有未未访问过过的邻接接顶点了了，所以以继续回回退到顶顶点F；(14) 回退到到顶点FF后，顶顶点F也也没有未未访问过过的邻接接顶点了了，所以以继续回回退到顶顶点E；(15) 回退到到顶点EE后，顶顶点E也也没有未未访问过过的邻接接顶点了了，所以以继续回回退到顶顶点B；(16) 回退到到顶点BB后，顶顶点B也也没有未未访问过过的邻接接顶点了了，所以以继续回回退到顶顶点A；6_06图的广广度优先先搜索算法掌握原原理广度优先搜搜索(BBreaadthh Fiirstt Seearcch) ：是一一个分层

37、层的搜索索过程，没没有回退退的情况况，是非非递归的的。6_07图的最最小生成成树概念理解生成树：连连通图GG的一个个子图如如果是一一棵包含含G的所所有顶点点的树，则则该子图图称为GG的生成成树。用不同的遍遍历图的的方法，可可以得到到不同的的生成树树；从不不同的顶顶点出发发，也可可能得到到不同的的生成树树。生成树是连连通图的的最小连连通子图图。所谓谓最小是指指：若在在树中任任意增加加一条边边，则将将出现一一个回路路；若去掉掉一条边边，将会会使之变变成非连连通图。按照生成树树的定义义，n 个顶顶点的连连通网络络的生成成树有 n 个顶顶点、nn-1 条边。最小生成树树：生成成树各边边的权值值总和称称

38、为生成成树的权权，权最最小的生生成树称称为最小小生成树树。构造最小生生成树的的准则：必须只使用用该网络络中的边边来构造造最小生生成树；必须使用且且仅使用用 n-1 条条边来联联结网络络中的 n 个个顶点；不能使用产产生回路路的边。构造最小生生成树的的方法：克鲁斯斯卡尔(Kruuskaal)算算法和普普里姆(Priim)算算法。都都得遵守守以上准准则。6_08Kruuskaal算法法算法掌握原原理完整程程序Kruskkal算算法执行行过程：将m条边存存储在eedgees数组组中，并并按权值值从小到到大排序序。依次检查每每条边，如如果该边边的两个个顶点不不属于同同一个集集合，则则选用该该边、并并将

39、这两两个集合合合并；否否则弃用用这条边边。6_09最短路路径问题题概念理解最短路径问问题：如如果从图图中某一一顶点(称为源源点)到到达另一一顶点(称为终终点)的的路径可可能不止止一条，如如何找到到一条路路径，使使得沿此此路径各各边上的的权值总总和达到到最小。求解算法：权值为非负负的单源源最短路路径问题题(固定定源点)Diijksstraa算法(迪克斯斯特拉算算法,119599)；权值为任意意值的单单源最短短路径问问题(固固定源点点) Belllmaan-FFordd算法(贝尔曼曼福特特算法)；Bellmman-Forrd算法法的改进进 SPFFA算法法；所有顶点之之间的最最短路径径问题Floo

40、yd-Warrshaall算算法(弗弗洛伊德德算法)；6_10Dijjksttra算算法算法掌握原原理完整程程序为求得这些些最短路路径，DDijkkstrra提出出按路径径长度的的递增次次序，逐逐步产生生最短路路径的算算法。首首先求出出长度最最短的一一条最短短路径，再再参照它它求出长长度次短短的一条条最短路路径，依依次类推推，直到到从顶点点v到其其它各顶顶点的最最短路径径全部求求出为止止。第7章 内内排序编号知识识点类型掌握程程度代码要要求7_01排序问问题的基基本概念念概念理解在计算机应应用软件件中经常常需要对对所管理理的各种种数据进进行处理理，排序往往往是这些些数据处处理中需需要用到到的核

41、心心运算。内排序：如如果待排排序的记记录个数数较少，整个排序过程中所有的记录都可以直接存放在内存中，这样的排序叫做内排序(internal sorting)。外排序：如如果待排排序的记记录数量量太大，内内存无法法容纳所所有的记记录，因因此排序序过程中中还需要要访问外外存，这这样的排排序叫做做外排序序(exxterrnall soortiing)。由于讨论的的是内排排序，在在大部分分情况下下本章都都是考虑虑基于顺顺序存储储的排序序，即待排排序的数数据是存存储在数数组中。记录(reecorrd)：参与排排序的元元素称为为记录，记记录是进进行排序序的基本本单位。序列(seequeencee)：所所有

42、待排排序记录录的集合合称为序列列。所谓谓排序就就是将序序列中的的记录按按照特定定的顺序序排列起起来。7_02用系统统函数实实现排序序应用掌握方方法完整程程序在实际编程程时，可可能不需需要自己己实现排排序算法法，直接接调用系系统函数数实现排排序即可可。但这并并不意味味着本章章介绍的的排序算算法原理理、程序序实现不不需要掌掌握。实现排序的的系统函函数主要要有：qqsorrt、ssortt函数qsortt函数：采用快速排排序算法法(7.4.11节)实实现。sort函函数：STL提供供的算法法，常常常结合SSTL中中的容器器和迭代代器使用用。7_03插入法法排序算法掌握原原理完整程程序逐个处理待待排序

43、的的记录，每个新记录都要与前面那些已排好序的记录进行比较，然后插入到适当的位置。7_04冒泡法法排序算法掌握原原理完整程程序554204520425042054202402042002冒泡法是不不是一定定要比较较n-11趟？不一定！比比如前面面的例22中，nn=8，但但实际上上只需要要进行55趟比较较，后面面2趟没没有进行行交换。也也就是说说，如果果在某一一趟比较较过程中中，没有有发现 前一个个数比后后一个数数大的情情况，即即没有进进行交换换数据，那那么后面面就不需需要再进进行比较较了。极端的情况况，假设设n个数数已经是是按从小小到大的的顺序排排好了，那那么实际际上只需需要进行行一趟比比较就可可以得出出结论了了。7_05选择法法排序算法掌握原原理完整程程序直接选择排排序法也也需要用用一个二二重循环环来实现现，同样样可以带带着以下3个类似似问题来来理解其其思想(有n个个数，要要求按照照从小到到大的顺顺序排序)：要进行多少少趟选择