第七章图
1.图：图G是由顶点集V和边集E组成，顶点集是有穷非空集，边集是有穷集；2.G中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；G中每条边都没有方向的称无向图。
3.顶点n与边数e的关系：无向图的边数e介于0~n(n-1)/2之间，有n(n-1)/2条边的称无向完全图；有向图的边数e介于0~n(n-1)之间，有n(n-1)条边的称有向完全图；4.无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和。所有图均满足：所有顶点的度数和的一半为边数。
5.图G（V，E），如V’是V的子集，E’是E的子集，且E’中关联的顶点均在V’中，则G’(V’,E’)是G的子图。
6.在有向图中，从顶点出发都有路径到达其它顶点的图称有根图；7.在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；8.在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；
9.将图中每条边赋上权，则称带权图为网络。
10.图的存储结构：（1）邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。无向图是对称矩阵；有向图行是出度，列是入度。（2）邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex
next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex
firstedge,并顺序存储在一个向量中；vertex保存顶点信息，firstedge保存邻接表头指针。11.邻接矩阵表示法与邻接表表示法的比较：1）邻接矩阵是唯一的，邻接表不唯一；2）存储稀疏图用邻接表，存储稠密图用邻接矩阵；3）求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便；4）判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n)；5）求边数e，邻接矩阵耗时为O(n^2)，与e无关，邻接表的耗时为O(e+n)；
12.图的遍历：（1）图的深度优先遍历：类似与树的前序遍历。按访问顶点次序得到的序列称DFS序列。对邻接表表示的图深度遍历称DFS，时间复杂度为O(n+e);对邻接矩阵表示的图深度遍历称DFSM，时间复杂度为O(n^2);（2）图的广度优先遍历：类似与树的层次遍历。按访问顶点次序得到的序列称BFS序列。对邻接表表示的图广度遍历称BFS，时间复杂度为O(n+e);对邻接矩阵表示的图广度遍历称BFSM，时间复杂度为O(n^2);
13.将没有回路的连通图定义为树称自由树。14.生成树：连通图G的一个子图若是一棵包含G中所有顶点的树，该子图称生成树。有DFS生成树和BFS生成树，BFS生成树的高度最小。非连通图生成的是森林。15.最小生成树：将权最小的生成树称最小生成树。（是无向图的算法）（1）普里姆算法：1）确定顶点S、初始化候选边集T[0~n-2]；formvex
tovex
lenght2）选权值最小的T[i]与第1条记录交换；3）从T[1]中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；4）选权值最小的T[i]与第2条记录交换；5）从T[2]中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；6）重复n-1次。初始化时间是O(n),选轻边的循环执行n-1-k次，调整轻边的循环执行n-2-k；算法的时间复杂度为O(n^2)，适合于稠密图。（2）克鲁斯卡尔算法：1）初始化确定顶点集和空边集；对原边集按权值递增顺序排序；2）取第1条边，判断边的2个顶点是不同的树，加入空边集，否则删除；3）重复e次。对边的排序时间是O(elog2e)；初始化时间为O(n)；执行时间是O(log2e)；算法的时间复杂度为O(elog2e)，适合于稀疏图。
16.路径的开始顶点称源点，路径的最后一个顶点称终点；17.单源最短路径问题：已知有向带权图，求从某个源点出发到其余各个顶点的最短路径；18.单目标最短路径问题：将图中每条边反向，转换为单源最短路径问题；19.单顶点对间最短路径问题：以分别对不同顶点转换为单源最短路径问题；20.所有顶点对间最短路径问题：分别对图中不同顶点对转换为单源最短路径问题；
21.迪杰斯特拉算法：1）初始化顶点集S[i],路径权集D[i],前趋集P[i]；2）设置S[s]为真，D[s]为0；3）选取D[i]最小的顶点加入顶点集；4）计算非顶点集中顶点的路径权集；5）重复3）n-1次。算法的时间复杂度为O(n^2)。
22.拓扑排序：对一个有向无环图进行拓扑排序，是将图中所有顶点排成一个线性序列，满足弧尾在弧头之前。这样的线性序列称拓扑序列。（1）无前趋的顶点优先：总是选择入度为0的结点输出并删除该顶点的所有边。设置各个顶点入度时间是O(n+e)，设置栈或队列的时间是O(n)，算法时间复杂度为O(n+e)。（2）无后继的顶点优先：总是选择出度为0的结点输出并删除该顶点的所有边。设置各个顶点出度时间是O(n+e)，设置栈或队列的时间是O(n)，算法时间复杂度为O(n+e)。求得的是逆拓扑序列。第八章排序1.文件：由一组记录组成，记录有若干数据项组成，唯一标识记录的数据项称关键字；2.排序是将文件按关键字的递增（减）顺序排列；
3.排序文件中有相同的关键字时，若排序后相对次序保持不变的称稳定排序，否则称不稳定排序；
4.在排序过程中，文件放在内存中处理不涉及数据的内、外存交换的称内排序，反之称外排序；
5.排序算法的基本操作：1）比较关键字的大小；2）改变指向记录的指针或移动记录本身。
6.评价排序方法的标准：1）执行时间；2）所需辅助空间，辅助空间为O(1)称就地排序；另要注意算法的复杂程度。
7.若关键字类型没有比较运算符，可事先定义宏或函数表示比较运算。
8.插入排序（1）直接插入排序算法中引入监视哨R[0]的作用是：1）保存R[i]的副本；2）简化边界条件，防止循环下标越界。关键字比较次数最大为(n+2)(n-1)/2；记录移动次数最大为(n+4)(n-1)/2；算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序；（2）希尔排序实现过程：是将直接插入排序的间隔变为d。d的取值要注意：1）最后一次必为1；2）避免d值互为倍数；关键字比较次数最大为n^1.25；记录移动次数最大为1.6n^1.25；算法的平均时间是O(n^1.25)；是一种就地的不稳定的排序；
9.交换排序（1）冒泡排序实现过程：从下到上相邻两个比较，按小在上原则扫描一次，确定最小值，重复n-1次。关键字比较次数最小为n-1、最大为n(n-1)/2；记录移动次数最小为0，最大为3n(n-1)/2；算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序；（2）快速排序实现过程：将第一个值作为基准，设置i,j指针交替从两头与基准比较，有交换后,交换j，i。i=j时确定基准，并以其为界限将序列分为两段。重复以上步骤。关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2；算法的最好时间是O(nlog2n)；最坏时间是O(n^2)；平均时间是O(nlog2n)；辅助空间为O(log2n)；是一种不稳定排序；
10.选择排序（1）直接选择排序实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步，共重复n-1次。关键字比较次数为n(n-1)/2；记录移动次数最小为0，最大为3(n-1)；算法的最好时间是O(n^2)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的不稳定的排序；（2）堆排序实现过程：把序列按层次填入完全二叉树，调整位置使双亲大于或小于孩子，建立初始大根或小根堆，调整树根与最后一个叶子的位置，排除该叶子重新调整位置。算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；是一种就地的不稳定排序；
11.归并排序实现过程：将初始序列分为2个一组，最后单数轮空，对每一组排序后作为一个单元，对2个单元排序，直到结束。算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；辅助空间为O(n)；是一种稳定排序；
12.分配排序（1）箱排序实现过程：按关键字的取值范围确定箱子的个数，将序列按关键字放入箱中，输出非空箱的关键字。在桶内分配和收集，及对各桶进行插入排序的时间为O(n),算法的期望时间是O(n),最坏时间是O(n^2)。（2）基数排序实现过程：按基数设置箱子，对关键字从低位到高位依次进行箱排序。算法的最好时间是O(d*n+d*rd)；最坏时间是O(d*n+d*rd)；平均时间是O(d*n+d*rd)；辅助空间O(n+rd)；是一种稳定排序；
13.各种内部排序方法的比较和选择：（1）按平均时间复杂度分为：1)平方阶排序：直接插入、直接选择、冒泡排序；2)线性对数阶：快速排序、堆排序、归并排序；3)指数阶：希尔排序；4)线性阶：箱排序、基数排序。
（2）选择合适排序方法的因素：1)待排序的记录数；2)记录的大小；3)关键字的结构和初始状态；4)对稳定性的要求；5)语言工具的条件；6)存储结构；7)时间和辅助空间复杂度。
（3）结论：1)若规模较小可采用直接插入或直接选择排序；2)若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序；3)若规模较大可采用快速排序、堆排序或归并排序；4)任何借助于比较的排序，至少需要O(nlog2n)的时间，箱排序和基数排序只适用于有明显结构特征的关键字；5)有的语言没有提供指针及递归，使归并、快速、基数排序算法复杂；6)记录规模较大时为避免大量移动记录可用链表作为存储结构，如插入、归并、基数排序，但快速、堆排序在链表上难以实现，可提取关键字建立索引表，然后对索引表排序。第九章查找
1.查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表，否则称之为静态查找表。2.衡量一个查找算法次序优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL).
3.线性表上进行查找的方法主要有三种：顺序查找、二分查找和分块查找。（1）顺序查找的算法基本思想：是从表的一端开始顺序扫描线性表，依次将扫描到的结点关键字与给定值K比较，若当前扫描到的结点关键字与k相等则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。1）顺序查找方法可用链式存储结构和顺序存储结构实现。2）在顺序存储结构的顺序查找算法中所设的哨兵是为了简化循环的边界条件而引入的附加结点(元素)，其作用是使for循环中省去判定防止下标越界的条件从而节省了比较的时间。3）在等概率情况下，查找成功时其平均查找长度约为表长的一半(n+1)/2.查找失败的话其平均查找长度为n+1.（2）二分查找(又称折半查找)，它的算法思想：是对一有序表中的元素，从初始的查找区间开始，每经过一次与当前查找区间的中点位置上的结点关键字进行比较，若相等，则查找成功，否则，当前查找区间的缩小一半，按k值大小在某半个区间内重复相同的步骤进行查找，直到查找成功或失败为止。1）二分查找在等概率的情况下查找成功的平均查找长度ASL为lg(n+1)-1,在查找失败时所需比较的关键字个数不超过判定树的深度，最坏情况下查找成功的比较次数也不超过判定树的深度┌lg(n+1)┐(不小于lg(n+1)的最小整数)2）二分查找只适用于顺序存储结构而不能用链式存储结构实现。因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。（3）分块查找(又称索引顺序查找)的基本思想：是将原表分成若干块，各块内部不一定有序，但表中的块是"分块有序"的，并抽取各块中的最大关键字及其起始位置建立索引表。因为索引表是有序的，分块查找就是先用二分查找或顺序查找确定待查结点在哪一块，然后在已确定的块中进行顺序查找(不能用二分查找，因为块内是无序的)。分块查找实际上是两次查找过程，它的算法效率介与顺序查找和二分查找之间。
4.以上三种查找方法的比较如下表：查找算法存储结构优点缺点适用于顺序查找顺序结构链表结构算法简单且对表的结构无任何要求查找效率低n较小的表的查找和查找较少但改动较多的表(用链表作存储结构)二分查找顺序结构查找效率高关键字要有序且只能用顺序存储结构实现特别适用于一经建立就很少改动又经常需要查找的线性表分块查找顺序结构链表在表中插入或删除记录时就只要在该记录所属块内操作，因为块内记录的存放是随意的，所以插入和删除比较容易要增加一个辅助数组的存储空间，并要进行将初始表分块排序运算适用于有分块特点的记录，如一个学校的学生登记表可按系号或班号分块。5.树的查找：以树做为表的组织形式有一个好处，就是可以实现对动态查找表进行高效率的查找。这里讲到了二叉排序树和B-树，以及在这些树表上进行查找和修改操作的方法。6.二叉排序树(BST)又称二叉查找树，其定义是：二叉排序树要或者是空树或者满足如下性质的二叉树：1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值；2)若它的右子树非空，则右子树上所有结点的值均大于根结点的值；3)左、右子树本身又是一棵二叉排序树。
（1）二叉排序树实际上是满足BST性质的二叉树。（2）二叉排序树的插入、建立的算法平均时间性能是O(nlgn),但其执行时间约为堆排序的2至3倍。二叉排序树的删除操作可分三种情况进行处理：1)*P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。2)*P只有一个孩子*child,此时只需将*child和*p的双亲直接连接就可删去*p.3)*p有两个孩子,则将操作转换成删除*p结点的中序后继，在删去它之前把这个结点的数据复制到原来要删的结点位置上就完成了删除。（3）二叉排序树上的查找和二分查找类似，它的关键字比较次数不超过树的深度。在最好的情况下，二叉排序树在生成的过程中比较匀称，此时的叉排序树是平衡的二叉树(也就是树中任一结点的左右子树的高度大致相同)，它的高度约为1.44lgn，完全平衡的二叉树高度约为lgn.在最坏的情况下，输入的实例产生的二叉排序树的高度将达到O(n),这种情况应当避免。
7.关于B-树(多路平衡查找树)。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。B树的阶是指B-树的度数，B-树的结点具有k个孩子时，该结点必有k-1(k=2)个关键字。实际上B-树是二叉排序树的推广，它就是一棵m叉树，且满足四个性质，这些性质与二叉排序树有相似之处，请仔细理解之。
8.上面的几种查找方法均是建立在比较关键字的基础上，因此它们的平均和最坏情况下所需的比较次数的下界是lgn+O(1).
9.散列技术：可以无需任何比较就找到待查关键字，其查找的期望时间为O(1).散列表的概念：就是将所有可能出现的关键字的集合U(全集)映射到一个表T[0..m-1]的下标集上，这个表就是散列表。10.而关键字与这个表地址之间以什么样的关系发生联系呢，这就要通过一个函数来建立，这个函数是以U中的关键字为自变量，以相应结点的存储地址为函数值，它就称为散列函数。将结点按其关键字的散列地址存储到散列表的过程称为散列。11.根据某种散列函数，一个关键字的散列函数值是唯一的，但是有可能两个或多个不同关键字的函数值是相同的，这时就会把几个结点存储到同一个表位置上，这时就造成冲突(或碰撞)现象，这两个关键字称为该散列函数的同义词。要完全(不是"安全")避免冲突需满足两个条件，一是关键字集合U不大于散列表长m，另一个是选择合适的散列函数,如果用h(ki)=0)这样的函数的话，看看有什么结果。
12.通常情况下U总是大大于m的，因此不可能完全避免冲突。冲突的频繁程度还与表的填满程度相关。装填因子α表示表中填入的结点数与表长的比值，通常取α≤1，因为α越大，表越满，冲突的机会也越大。13.散列函数的选择有两条标准：简单和均匀。看看h(ki)=0这样的函数，简单是简单，但绝不均匀。
14.下面是常见的几种散列函数构的造方法：（1）平方取中法（2）除余法：它是用表长m来除关键字，取余数作为散列地址。若选除数m是关键字的基数的幂次，就会使得高位不同而低位相同的关键字互为同义词。因此最好选取素数为除数.（3）相乘取整法：有两个步骤，先用关键字key乘上某个常数A(0)（4）随机数法，此法以关键字为自变量，通过一随机函数得到的值作为散列地址。
15.处理冲突的方法：当不可避免发生冲突时，就必须对冲突加以解决，使发生冲突的同义词能存储到表中。
16.通常有两类方法处理冲突：开放定址法和拉链法。前者是将所有结点均存放在散列T[0..m-1]中，后者是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表中。
17.开放定址法的一般形式为：hi=(h(key)+di)%m1≤i≤m-.开放定址法要求散列表的装填因子α≤1。开放定址法又有线性探查法、二次探查法和双重散列法之分。（1）由于线性探查法在构造散列表时，遇到冲突(有同义词)的时候会按探查序列向后面的空地址插入，从而使原来应插入到此位置的结点又与它发生冲突，当一连串的位置均已有结点时，本应插入到这些位置的结点又只能将其插入到更后面的同一个空结点上，这种散列地址不同的结点争夺同一个后继散列地址的现象就是聚集或堆积。(注意，同义词发生冲突不是堆积)为了减小堆积现象的发生，可以用二次探查法和双重散列法进行探查。（2）拉链法解决冲突的做法是，将所有关键字为同义词的结点链接在同一个单链表中。
19.与开放定址法相比，拉链法有如下几个优点：(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；(简单无堆积)(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适于造表前无法确定表长的情况；(动态申表长)(3)开放定址法为减少冲突要求装填因子α较小，当结点规模较大时会浪费很多空间，拉链法中α可以大于1，且结点较大时，其指针域可忽略不计，因此节省空间；(空间可节省)(4)拉链法构造的散列表删除结点易实现，而开放定址法中则不能真正删除结点只能做删除标记。(删除易实现)20.拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。
21.在散列表上的运算有查找、插入和删除,主要是查找。这三个操作的算法并不复杂，也容易理解。关于查找操作的时间性能，可看教材p的表9.1。由表可见，散列表的平均查找长度不是结点个数n的函数，而是装填因子α的函数。α越小，冲突的概率越小，但空间的浪费将增加，当α大小合适时，散列表上的平均查找长度就是一个常数，时间性能是O(1).第十章文件
1.对数据结构来说，文件是性质相同的记录的集合。2.2.记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。主关键字项(唯一标识一个记录的字段)、次关键字项、主关键字、次关键字。单关键字文件、多关键字文件等。
3.文件的逻辑结构是一种线性结构。
4.文件上的操作主要有两类：检索和维护。并有实时和批量处理两种处理方式。
5.文件的存储结构是指文件在外存上的组织方式，基本的组织方式有：顺序组织、索引组织、散列组织和链组织。文件组织的各种方式往往是这四种基本方式的结合。
6.常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。
7.评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。通常文件组织的主要目的，是为了能高效、方便地对文件进行操作，而检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。
8.顺序文件：是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。1）一切存储在顺序存储器(如磁带)上的文件都只能顺序文件。这种顺序文件只能按顺序查找法存取(注意，没有折半法了)2）存储在直接存取存储器(如磁盘)上的顺序文件可以顺序查找法存取，也可以用分块查找法或二分查找法存取。3）顺序文件多用于磁带。
9.索引文件：组织方式：通常是在文件本身(主文件)之外，另外建立一张表，它指明逻辑记录和物理记录之间一一对应的关系，这张表就叫做索引表，它和主文件一起构成索引文件。1）索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。2）若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。通常可达四级索引。
10.索引顺序文件：是最常用的文件组织：因为索引顺序文件的主文件也是有序的，所以它既适合于随机存取也适合于顺序存取。另一方面，索引非顺序文件的索引是稠密索引，而索引顺序文件的稀疏索引，占用空间较少，因此索引顺序文件是最常用的一种文件组织。1）索引顺序文件常用的有两种：ISAM文件和VSAM文件
11.散列文件：是利用散列存储方式组织的文件，亦称为直接存取文件。1）它类似于散列表，即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到存储设备上。与散列表不同的是，对于文件来说，记录通常是成组存放的，若干个记录组成一个存储单位，称为桶。对散列而言，处理冲突的方法主要采用拉链法。2）散列文件的优点是:文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间。缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。
12.对被查询的次关键字也建立相应的索引，则这种包含有多个次关键字索引的文件称为多关键字文件。1）两种多关键字文件的组织方法：多重表文件和倒排表。2）一般的文件组织中，是先找记录，然后再找到该记录所含的各次关键字；而倒排文件是先给定次关键字，然后查找含有该次关键字的各个记录，因此称为倒排。
北京白癜风治疗中心白癜风最好的专科医院