EEPW论坛

图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的，

即任意两个结点之间之间都可能相关。

图GraphG=(V,E)，V是顶点的有穷非空集合，E是顶点偶对的有穷集。

有向图Digraph：每条边有方向；

无向图Undigraph：每条边没有方向。

有向完全图：具有n*(n-1)条边的有向图；

无向完全图：具有n*(n-1)/2条边的无向图；

有根图：有一个顶点有路径到达其它顶点的有向图；

简单路径：是经过顶点不同的路径；

简单回路是开始和终端重合的简单路径；

网络：是带权的图。

ChinaNetBoy 19:43:58

********************************************

图的存储结构：

 邻接矩阵表示法：用一个n阶方阵来表示图的结构是唯一的，适合稠密图。

 无向图：邻接矩阵是对称的。

 有向图：行是出度，列是入度。

建立邻接矩阵算法的时间是O(n+n^2+e),其时间复杂度为O(n^2)

 邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。

 顶点表结构 vertex | firstedge，指针域存放邻接表头指针。

 邻接表：用头指针确定。

  无向图称边表；

 有向图又分出边表和逆邻接表；

 邻接表结点结构为 adjvex | next，

时间复杂度为O(n+e).，空间复杂度为O(n+e).。

图的遍历：  深度优先遍历：借助于邻接矩阵的列。

使用栈保存已访问结点。

 广度优先遍历：借助于邻接矩阵的行。

使用队列保存已访问结点。

********************************************

生成树的定义：若从图的某个顶点出发，

可以系统地访问到图中所有顶点，

则遍历时经过的边和图的所有顶点所构成的子图称作该图的生成树。

最小生成树：图的生成树不唯一，从不同的顶点出发可得到不同的生成树，

把权值最小的生成树称为最小生成树(MST)。

构造最小生成树的算法：

 Prim算法的时间复杂度为O(n^2)与边数无关适于稠密图。

 Kruskal算法的时间复杂度为O(lge),主要取决于边数，较适合于稀疏图。

********************************************

最短路径的算法： Dijkstra算法，时间复杂度为O(n^2). 类似于prim算法。

拓扑排序：是将有向无环图G中所有顶点排成一个线性序列，

若<u,v>∈E(G)，则在线性序列u在v之前，这种线性序列称为拓扑序列。

拓扑排序也有两种方法：

 无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。

********************************************

排序

**其中快速排序是20世纪最伟大的算法实现之一

记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。

排序是使文件中的记录按关键字递增(或递减)次序排列起来。

 基本操作：比较关键字大小；改变指向记录的指针或移动记录。

 存储结构：顺序结构、链表结构、索引结构。

经过排序后这些具有相同关键字的记录之间的相对次序保持不变,

则称这种排序方法是稳定的，否则排序算法是不稳定的。

排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序)，

反之，若存在数据的内外存交换，则称之为外排序。

内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。

评价排序算法好坏的标准主要有两条：

执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。

ChinaNetBoy 19:48:29

********************************************

插入排序：

 直接插入排序：  逐个向前插入到合适位置。

 哨兵(监视哨)有两个作用：  作为临变量存放R[i]

 是在查找循环中用来监视下标变量j是否越界。

 直接插入排序是就稳定排序。

时间复杂度为O(n^2)，比较次数为(n+2)(n-1)/2；移动次数为(n+4)(n-1)/2；

 希尔排序：  等间隔的数据比较并按要求顺序排列，最后间隔为1。

 希尔排序是就地的不稳定排序。

时间复杂度为O(n^1.25)，比较次数为(n^1.25)；移动次数为(1.6n^1.25)；

交换排序： 冒泡排序： 自下向上确定最轻的一个。

 自上向下确定最重的一个。

 自下向上确定最轻的一个，后自上向下确定最重的一个。

 冒泡排序是就地的稳定排序。

时间复杂度为O(n^2)，比较次数为n(n-1)/2；移动次数为3n(n-1)/2；

 快速排序： 以第一个元素为参考基准，设定、动两个指针，

发生交换后指针交换位置，直到指针重合。重复直到排序完成。

 快速排序是非就地的不稳定排序。

时间复杂度为O(nlog2n)，比较次数为n(n-1)/2；

选择排序： 直接选择排序：  选择最小的放在比较区前。

 直接选择排序就地的不稳定排序。时间复杂度为O(n^2)。比较次数为n(n-1)/2；

 堆排序 

 建堆：按层次将数据填入完全二叉树，从int(n/2)处向前逐个调整位置。

 然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。

 堆排序是就地不稳定的排序，时间复杂度为O(nlog2n)，不适宜于记录数较少的文件。。

归并排序：

 先两个一组排序，形成(n+1)/2组，再将两组并一组，直到剩下一组为止。

 归并排序是非就地稳定排序，时间复杂度是O(nlog2n),

分配排序：

 箱排序：

 按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。

 箱排序的平均时间复杂度是线性的O(n).

 基数排序： 从低位到高位依次对关键字进行箱排序。

 基数排序是非就稳定的排序，时间复杂度是O(d*n+d*rd)。

各种排序方法的比较和选择： 

********************************************

各种排序用法时机

 .待排序的记录数目n；n较大的要用时间复杂度为O(nlog2n)的排序方法；

 记录的大小(规模)；记录大最好用链表作为存储结构，

而快速排序和堆排序在链表上难于实现；

 关键字的结构及其初始状态；

 对稳定性的要求；

 语言工具的条件；

 存储结构；

 时间和辅助空间复杂度。

********************************************

查找

查找的同时对表做修改操作(如插入或删除)

则相应的表称之为动态查找表，否则称之为静态查找表。

衡量查找算法效率优劣的标准是在查找过程中对关键字

需要执行的平均比较次数(即平均查找长度ASL).

********************************************

线性表查找的方法：

 顺序查找：逐个查找，ASL=(n+1)/2;

 二分查找：取中点int(n/2)比较,若小就比左区间，大就比右区间。

用二叉判定树表示。ASL=（∑（每层结点数*层数））/N。

 分块查找。要求“分块有序”，将表分成若干块内部不一定有序，

并抽取各块中的最大关键字及其位置建立有序索引表。

********************************************

二叉排序树(BST)定义是：二叉排序树是空树或者满足如下性质的二叉树：

 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

 左、右子树本身又是一棵二叉排序树。

二叉排序树的插入、建立、删除的算法平均时间性能是O(nlog2n)。

二叉排序树的删除操作可分三种情况进行处理：

 *P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。

 *P只有一个孩子*child,此时只需将*child和*p的双亲直接连接就可删去*p.

 *p有两个孩子,则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。

********************************************

关于B-树(多路平衡查找树)。

它适合在磁盘等直接存取设备上组织动态的查找表，

是一种外查找算法。建立的方式是从下向上拱起。

********************************************

散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。

散列函数的选择有两条标准：简单和均匀。

常见的散列函数构的造方法：  .平方取中法：hash=int((x^2)%100)

 .除余法：表长为m，hash=x%m

 .相乘取整法：hash=int(m*(x*A-int(x*A))；A=0.618

 .随机数法：hash=random(x)。

********************************************

ChinaNetBoy 19:52:55

处理冲突的方法：

 开放定址法：

 一般形式为hi=(h(key)+di)%m1≤i≤m-1，开放定址法要求散列表的装填因子α≤1。

 开放定址法类型：  线性探查法：address=(hash(x)+i)%m；

 二次探查法：address=(hash(x)+i^2)%m；

 双重散列法：address=(hash(x)+i*hash(y))%m；

   拉链法：  是将所有关键字为同义词的结点链接在同一个单链表中。

 拉链法的优点：  拉链法处理冲突简单，且无堆积现象；

 链表上的结点空间是动态申请的适于无法确定表长的情况；

 拉链法中α可以大于1，结点较大时其指针域可忽略，因此节省空间；

 拉链法构造的散列表删除结点易实现。

 拉链法也有缺点：当结点规模较小时，

用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。

*******************************************

文件

文件是性质相同的记录的集合。

记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。

文件　 逻辑结构是一种线性结构。

　　　 操作有：检索和维护。并有实时和批量处理两种处理方式。

文件　 存储结构是指文件在外存上的组织方式。

　　　 基本的组织方式有：顺序组织、索引组织、散列组织和链组织。

　　　 常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。

评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。

检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。

ChinaNetBoy 19:54:43

顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。

主关键字有序称顺序有序文件，否则称顺序无序文件。

一切存储在顺序存储器(如磁带)上的文件都只能顺序文件，只能按顺序查找法存取。

顺序文件的插入、删除和修改只能通过复制整个文件实现。

********************************************

索引文件的组织方式：

通常是在主文件之外建立一张索引表指明逻辑记录和

物理记录之间一一对应的关系，它和主文件一起构成索引文件。

索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。

若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。

是一种静态索引。

索引顺序文件常用的有两种：　

 ISAM索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。

 VSAM虚拟存储存取方法：采用B+树作为动态索引结构，由索引集、顺序集、数据集组成。

ChinaNetBoy 19:55:27

********************************************

散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。

散列文件　

 优点是：文件随机存放，记录不需要排序；

插入删除方便；存取速度快；不需要索引区，节省存储空间。

 缺点是：不能进行顺序存取，只能按关键字随机存取，

且询问方式限地简单询问，需要重新组织文件。

********************************************

多重表文件：对需要查询的次关键字建立相应的索引，

对相同次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项。

倒排表：次关键字索引表称倒排表，

主文件和倒排表构成倒排文件。