全國(guó)計(jì)算機(jī)等級(jí)考試四級(jí)復(fù)習(xí)綱要二

五、圖
　　
　　圖的概念

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

　　圖（graph）是圖型結(jié)構(gòu)的簡(jiǎn)稱。它是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。圖在各個(gè)領(lǐng)域都有著廣泛的應(yīng)用。圖的二元組定義為:
　　
　　G=（V，E）

　　其中，V是非空的頂點(diǎn)集合，即

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

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

　　1.直接插入排序

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

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

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

　　5.快速排序

　　快速排序的基本思想是把表中某元素作為基準(zhǔn)，將表劃分為大于該值和小于該值的兩部分，然后用遞歸的方法處理這兩個(gè)子表，直到完成整個(gè)表的排序�？焖倥判虻谋容^次數(shù)為（n-1）+（n-2）+…+1=n（n-1）/2，移動(dòng)次數(shù)最多也是n（n-1）/2。如果每次的基準(zhǔn)元素剛好是表的中值，使表分為大小相等的兩個(gè)子表，則比較次數(shù)為nlog 2 n;如果表已排好序，則移動(dòng)次數(shù)為0。
　　6.常用排序方法的性能比較如下表所示:
　　
　　常用排序方法的性能比較
　　
　　排序方法 平均時(shí)間 最壞情況的時(shí)間 輔助存儲(chǔ)
　　
　　冒泡法、直接選擇法、直接插入法 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 ）。如果在待排序的表中含有多個(gè)碼值相同的記錄，經(jīng)過(guò)排序后，這些記錄的相對(duì)次序不變，則稱這種排序方法是穩(wěn)定的，否則是不穩(wěn)定的。根據(jù)上述說(shuō)法，可以看出直接插入法、歸并法是穩(wěn)定的;而直接選擇法、冒泡法、快速排序法、堆排序法是不穩(wěn)定的。　

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

更多信息請(qǐng)?jiān)L問(wèn)：考試吧計(jì)算機(jī)等級(jí)考試欄目