全國計算機等級考試四級復習綱要二

五、圖
　　
　　圖的概念

　　圖是一種較線性表和樹形結構更為復雜的數(shù)據(jù)結構。在線性表中每個數(shù)據(jù)元素只有一個（直接）前驅(qū)和后繼，即各數(shù)據(jù)元素之間僅有線性關系。在樹形結構中，數(shù)據(jù)元素之間有明顯的層次關系，每一層中的數(shù)據(jù)元素只和上一層中的一個元素（即雙親結點）相關。而在圖中，任意兩個數(shù)據(jù)元素之間均有可能相關。

　　圖（graph）是圖型結構的簡稱。它是一種復雜的非線性數(shù)據(jù)結構。圖在各個領域都有著廣泛的應用。圖的二元組定義為:
　　
　　G=（V，E）

　　其中，V是非空的頂點集合，即

　　V=｛v i |1≤i≤n，n≥1，v i ∈elemtype，n為頂點數(shù)｝

　　E是V上二元關系的集合，一般只討論僅含一個二元關系的情況，且直接用E表示這個關系。這樣，E就是V上頂點的序偶或無序?qū)Γ�每個無序?qū)Γ▁，y）是兩個對稱序偶<x，y>和<y，x>的簡寫形式）的集合。對于V上的每個頂點，在E中都允許有任意多個前驅(qū)和任意多個后繼，即對每個頂點的前驅(qū)和后繼個數(shù)均不加限制�；仡櫼幌戮�性表和樹的二元組定義，都是在其二元關系上規(guī)定了限制條件，線性表的限制條件是只允許每個結點有一個前驅(qū)和一個后繼，樹的限制條件是只允許每個結點有一個前驅(qū)。因此，圖比線性表和樹更具有廣泛性，它包含線性表和樹在內(nèi)，線性表和樹可以認為是圖的簡單情況。
　　
　　對于一個圖G，若E是序偶的集合，則每個序偶對應圖形中的一條有向邊，若E是無序?qū)Φ募�合，則每個無序?qū)�對應圖形中的一條無向邊，所以可把E看作為邊的集合。這樣，圖的二元組定義可敘述為:圖的非空頂點集（vertexset）和邊集（edgeset）所組成。針對圖G，頂點集和邊集可分別記為V（G）和E（G）。邊集E（G）允許是空集，若是空集，圖G中的頂點均為孤立頂點。對于一個圖G，若邊集E（G）為有向邊的集合，則稱此圖為有向圖（digraph），若邊集E（G）為無向邊的集合，則稱此圖為無向圖（undigraph）。
　　
　　六、排序

　　1.直接插入排序

　　直接插入排序的基本思想是把表中元素依次插入一個已排好序的表中，就像人們打撲克摸牌時把牌插入手中的若干張牌里一樣。表中n個元素依次插入的比較次數(shù)為1+2+3+…+（n-1）=n（n-1）/2。在插入時，元素的移動次數(shù)最多為1+2+3+…+（n-1）=n（n-1）/2。如果表中元素已排好序，則只需比較n-1次，而移動次數(shù)為0。
　　
　　2.直接選擇排序
　　
　　直接選擇排序的基本思想是在表的n個元素中，經(jīng)過n-1次比較得到其最大值（或最小值，下同），這就排好了第一個元素;再經(jīng)過n-2次比較得到余下元素中的最大值，這就排好了第二個元素…直到比較1次后排好第n-1個元素，第n個元素的位置也就自然確定了。所需的比較次數(shù)為（n-1）+（n-2）++1=n（n-1）/2。所需移動次數(shù)最多也為n（n-1）/2。如果表中元素排好序，也需要比較n（n-1）/2次，而移動次數(shù)為0。

　　3.冒泡排序
　　
　　冒泡排序的基本思想是將表中元素兩個相鄰元素依次比較，若不符合排序要求，則交換位置，這樣經(jīng)過n-1次比較后，將確定出最大（或最�。┰�素的位置，這稱為一趟掃描。經(jīng)過n-1次掃描后，就完成了整個表的排序。第一趟掃描的比較次數(shù)是n-1，第二趟掃描的比較次數(shù)是n-2……，總的比較次數(shù)是（n-1）+（n-2）+……+1=n（n-1）/2。如果恰好表中元素按反序排列，則需要移動的次數(shù)為3×n（n-1）/2。如果表中元素已排好序，并采用交換標志來表示并未發(fā)生過交換，則只需一趟掃描，只比較n-1次，就夠了;當然，移動次數(shù)也是0。
　　
　　4.歸并排序

　　歸并排序的基本思想是表中元素兩兩比較排序，使表中的n個元素變成n/2個已排序的組，再兩兩組比較，而變成n/4個已排序的組……，直到表中只含有一個已排序的組，即完成排序。所需要的比較次數(shù)為nlog 2 n，移動次數(shù)為n。若表已排好序，則比較次數(shù)仍為nlog 2 n，但移動次數(shù)為0。

　　5.快速排序

　　快速排序的基本思想是把表中某元素作為基準，將表劃分為大于該值和小于該值的兩部分，然后用遞歸的方法處理這兩個子表，直到完成整個表的排序。快速排序的比較次數(shù)為（n-1）+（n-2）+…+1=n（n-1）/2，移動次數(shù)最多也是n（n-1）/2。如果每次的基準元素剛好是表的中值，使表分為大小相等的兩個子表，則比較次數(shù)為nlog 2 n;如果表已排好序，則移動次數(shù)為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 ）。如果在待排序的表中含有多個碼值相同的記錄，經(jīng)過排序后，這些記錄的相對次序不變，則稱這種排序方法是穩(wěn)定的，否則是不穩(wěn)定的。根據(jù)上述說法，可以看出直接插入法、歸并法是穩(wěn)定的;而直接選擇法、冒泡法、快速排序法、堆排序法是不穩(wěn)定的�！�

希望與更多計算機等級考試的網(wǎng)友交流，請進入計算機等級考試論壇

更多信息請訪問：考試吧計算機等級考試欄目