全国计算机等级考试四级复习纲要二

五、图
　　
　　图的概念

　　图是一种较线性表和树形结构更为复杂的数据结构。在线性表中每个数据元素只有一个（直接）前驱和后继，即各数据元素之间仅有线性关系。在树形结构中，数据元素之间有明显的层次关系，每一层中的数据元素只和上一层中的一个元素（即双亲结点）相关。而在图中，任意两个数据元素之间均有可能相关。

　　图（graph）是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都有着广泛的应用。图的二元组定义为:
　　
　　G=（V，E）

　　其中，V是非空的顶点集合，即

　　V=｛v i |1≤i≤n，n≥1，v i ∈elemtype，n为顶点数｝

　　E是V上二元关系的集合，一般只讨论仅含一个二元关系的情况，且直接用E表示这个关系。这样，E就是V上顶点的序偶或无序对（每个无序对（x，y）是两个对称序偶<x，y>和<y，x>的简写形式）的集合。对于V上的每个顶点，在E中都允许有任意多个前驱和任意多个后继，即对每个顶点的前驱和后继个数均不加限制。回顾一下线性表和树的二元组定义，都是在其二元关系上规定了限制条件，线性表的限制条件是只允许每个结点有一个前驱和一个后继，树的限制条件是只允许每个结点有一个前驱。因此，图比线性表和树更具有广泛性，它包含线性表和树在内，线性表和树可以认为是图的简单情况。
　　
　　对于一个图G，若E是序偶的集合，则每个序偶对应图形中的一条有向边，若E是无序对的集合，则每个无序对对应图形中的一条无向边，所以可把E看作为边的集合。这样，图的二元组定义可叙述为:图的非空顶点集（vertexset）和边集（edgeset）所组成。针对图G，顶点集和边集可分别记为V（G）和E（G）。边集E（G）允许是空集，若是空集，图G中的顶点均为孤立顶点。对于一个图G，若边集E（G）为有向边的集合，则称此图为有向图（digraph），若边集E（G）为无向边的集合，则称此图为无向图（undigraph）。
　　
　　六、排序

　　1.直接插入排序

　　直接插入排序的基本思想是把表中元素依次插入一个已排好序的表中，就像人们打扑克摸牌时把牌插入手中的若干张牌里一样。表中n个元素依次插入的比较次数为1+2+3+…+（n-1）=n（n-1）/2。在插入时，元素的移动次数最多为1+2+3+…+（n-1）=n（n-1）/2。如果表中元素已排好序，则只需比较n-1次，而移动次数为0。
　　
　　2.直接选择排序
　　
　　直接选择排序的基本思想是在表的n个元素中，经过n-1次比较得到其最大值（或最小值，下同），这就排好了第一个元素;再经过n-2次比较得到余下元素中的最大值，这就排好了第二个元素…直到比较1次后排好第n-1个元素，第n个元素的位置也就自然确定了。所需的比较次数为（n-1）+（n-2）++1=n（n-1）/2。所需移动次数最多也为n（n-1）/2。如果表中元素排好序，也需要比较n（n-1）/2次，而移动次数为0。

　　3.冒泡排序
　　
　　冒泡排序的基本思想是将表中元素两个相邻元素依次比较，若不符合排序要求，则交换位置，这样经过n-1次比较后，将确定出最大（或最小）元素的位置，这称为一趟扫描。经过n-1次扫描后，就完成了整个表的排序。第一趟扫描的比较次数是n-1，第二趟扫描的比较次数是n-2……，总的比较次数是（n-1）+（n-2）+……+1=n（n-1）/2。如果恰好表中元素按反序排列，则需要移动的次数为3×n（n-1）/2。如果表中元素已排好序，并采用交换标志来表示并未发生过交换，则只需一趟扫描，只比较n-1次，就够了;当然，移动次数也是0。
　　
　　4.归并排序

　　归并排序的基本思想是表中元素两两比较排序，使表中的n个元素变成n/2个已排序的组，再两两组比较，而变成n/4个已排序的组……，直到表中只含有一个已排序的组，即完成排序。所需要的比较次数为nlog 2 n，移动次数为n。若表已排好序，则比较次数仍为nlog 2 n，但移动次数为0。

　　5.快速排序

　　快速排序的基本思想是把表中某元素作为基准，将表划分为大于该值和小于该值的两部分，然后用递归的方法处理这两个子表，直到完成整个表的排序。快速排序的比较次数为（n-1）+（n-2）+…+1=n（n-1）/2，移动次数最多也是n（n-1）/2。如果每次的基准元素刚好是表的中值，使表分为大小相等的两个子表，则比较次数为nlog 2 n;如果表已排好序，则移动次数为0。
　　6.常用排序方法的性能比较如下表所示:
　　
　　常用排序方法的性能比较
　　
　　排序方法 平均时间 最坏情况的时间 辅助存储
　　
　　冒泡法、直接选择法、直接插入法 O（n2 ） O（n2 ） O（1）
　　
　　快速排序 O（nlog2 n） O（n2 ） O（log2 n）
　　
　　堆排序 O（nlog2n） O（nlog2 n） O（1）
　　
　　归并排序 O（nlog2 n） O（nlog2 n） O（n）

　　注:在上表中，我们将n（n-1）/2也记为O（n2 ）。如果在待排序的表中含有多个码值相同的记录，经过排序后，这些记录的相对次序不变，则称这种排序方法是稳定的，否则是不稳定的。根据上述说法，可以看出直接插入法、归并法是稳定的;而直接选择法、冒泡法、快速排序法、堆排序法是不稳定的。　

希望与更多计算机等级考试的网友交流，请进入计算机等级考试论坛

更多信息请访问：考试吧计算机等级考试栏目