計(jì)算機(jī)基礎(chǔ)（第2版）課件第4章 數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)

第4章數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)4數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)4.1算法和算法分析4.2數(shù)據(jù)結(jié)構(gòu)的基本概念4.3數(shù)據(jù)結(jié)構(gòu)的分類及表示4.4線性結(jié)構(gòu)4.1

算法和算法分析

算法的概念算法的特征

算法的效率4.1.1算法的概念通俗地講,算法是解決問題的方法；嚴(yán)格地說，算法是對(duì)特定問題求解步驟的一種描述,是指令的有限序列。對(duì)于一個(gè)問題，如果可以通過一個(gè)計(jì)算機(jī)程序,在有限的存儲(chǔ)空間內(nèi)運(yùn)行有限長的時(shí)間而得到正確的結(jié)果，則稱這個(gè)問題是算法可解的。但算法不等于程序,也不等于計(jì)算方法。當(dāng)然，程序也可以作為算法的一種描述,但程序通常還需考慮很多與方法和分析無關(guān)的細(xì)節(jié)問題，這是因?yàn)樵诰帉懗绦驎r(shí)要受到計(jì)算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制。通常,程序的編制不可能優(yōu)于算法的設(shè)計(jì)。4.1.2算法的特征作為一個(gè)算法，一般應(yīng)具有以下幾個(gè)基本特征。(1)可行性(Eflectiveness)算法的可行性包括以下兩個(gè)方面。①算法中的每一個(gè)步驟必須能夠?qū)崿F(xiàn)。如在算法中不允許出現(xiàn)分母為0的操作，在實(shí)數(shù)范圍內(nèi)不可能求一個(gè)負(fù)數(shù)的平方根等。②算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期的目的。針對(duì)實(shí)際問題設(shè)計(jì)的算法,人們總是希望能夠得到滿意的結(jié)果。但一個(gè)算法又總是在某個(gè)特定的計(jì)算工具上執(zhí)行的、因此,算法在執(zhí)行過程中往往要受到計(jì)算工具的限制,使執(zhí)行結(jié)果產(chǎn)牛偏差。例如，A/B*C與A*C/B,如果B的數(shù)據(jù)類型是整型與B的數(shù)據(jù)類型是實(shí)型，可能會(huì)產(chǎn)生不同的結(jié)果。因此,算法與計(jì)算公式是有差別的。在設(shè)計(jì)一個(gè)算法時(shí),必須要考慮它的可行性,否則是不會(huì)得到滿意結(jié)果的。4.1.2算法的特征(2)確定性(Definiteness)算法的確定性,是指算法中的每一個(gè)步驟都必須是有明確定義的,不允許有模梭兩可的解釋,也不允許有多義性。這一性質(zhì)也反映了算法與數(shù)學(xué)公式的明顯差別。在解決實(shí)際問題時(shí),可能會(huì)出現(xiàn)這樣的情況:針對(duì)某種特殊問題，數(shù)學(xué)公式是正確的,但按此數(shù)學(xué)公式設(shè)計(jì)的計(jì)算過程可能會(huì)使計(jì)算機(jī)系統(tǒng)無所適從。這是因?yàn)楦鶕?jù)數(shù)學(xué)公式設(shè)計(jì)的計(jì)算過程只考慮了正常使用的情況，而當(dāng)出現(xiàn)異常情況時(shí),此計(jì)算過程就不能適應(yīng)了。(3)有窮性(Finiteness)算法的有窮性，是指算法必須在有限的時(shí)間內(nèi)做完，即算法必須在執(zhí)行有限步驟之后終止。數(shù)學(xué)中的無窮級(jí)數(shù)、在實(shí)際計(jì)算時(shí)只能取有限項(xiàng),即計(jì)算無窮級(jí)數(shù)值的過程只能是有窮的。因此，一個(gè)數(shù)的無窮級(jí)數(shù)表示只是一個(gè)計(jì)算公式,而根據(jù)精度要求確定的計(jì)算過程才是有窮的算法。算法的有窮性還應(yīng)包括合理的執(zhí)行時(shí)間的含義。因?yàn)?、如果一個(gè)算法需要執(zhí)行千萬年,顯然失去了實(shí)用價(jià)值。4.1.2算法的特征(4)擁有足夠的情報(bào)一個(gè)算法是否有效，還取決于為算法所提供的情報(bào)是否足夠。通常,算法中的各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài),這是算法執(zhí)行的起點(diǎn)或是依據(jù)。因此，一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān),不同的輸入將會(huì)有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯(cuò)誤時(shí),算法本身也就無法執(zhí)行或?qū)е聢?zhí)行有錯(cuò)。一般來說．當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才是有效的，面當(dāng)提供的情報(bào)不夠時(shí),算法可能無效。綜上所述，所謂算法。是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則,并且每一個(gè)規(guī)則都是有效的,且是明確的,此順序?qū)⒃谟邢薜拇螖?shù)下終止。4.1.3算法的效率(1)設(shè)計(jì)一個(gè)好的算法通常需要考慮以下幾方面的要求。①正確性。要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能,并達(dá)到所期望的性能要求。②可讀性。為了便于理解、測試和修改算法,算法應(yīng)該具有良好的可讀性。③健壯性。當(dāng)輸入非法的數(shù)據(jù)時(shí),算法應(yīng)能恰當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行相應(yīng)處理,而不是產(chǎn)生莫名其妙的輸出結(jié)果。并且處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行,而是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值,以便在更高的抽象層次上進(jìn)行處理。④高效性。要求算法的執(zhí)行時(shí)間要盡可能短，算法的效率就越高。⑤低存儲(chǔ)量。完成相同的功能,執(zhí)行算法時(shí)所占用的附加存儲(chǔ)空間要盡可能地少。4.1.3算法的效率(2)考慮算法的效率問題，即算法的時(shí)間效率(所需運(yùn)算的時(shí)間)和空間效率(所占存儲(chǔ)空間)兩方面。一般情況下，鑒于運(yùn)算空間(內(nèi)存)較為充足，所以把算法的時(shí)間復(fù)雜度作為重點(diǎn)分析。①時(shí)間復(fù)雜度(TimeComplexity)一個(gè)算法所需的運(yùn)算時(shí)間通常與所解決問題的規(guī)模大小有關(guān)。問題規(guī)模是一個(gè)和輸入有關(guān)的量，用n表示問題規(guī)模的量。通常把算法運(yùn)行所需的時(shí)間T表示為n的函數(shù)，記為T(n)。當(dāng)n逐漸增大時(shí)T(n)的極限情況，一般簡稱為時(shí)間復(fù)雜度。隨著數(shù)據(jù)輸入規(guī)模的增大,fn)的增長率與T(n)的增長率相近，因此、T(n)同f(n)在數(shù)量級(jí)上是一致的。記作T(n)=O(f(n))。算法時(shí)問復(fù)雜度的數(shù)量級(jí)越大，表示該算法的效率越低，反之越高。例如,O(1)為常數(shù)數(shù)量級(jí),即算法的時(shí)間復(fù)雜性與輸人規(guī)模n無關(guān)。4.1.3算法的效率②空間復(fù)雜度(SpaceComplexity)一個(gè)算法的空間復(fù)雜度是指程序運(yùn)行開始到結(jié)束所需要的存儲(chǔ)空間。類似于算法的時(shí)間復(fù)雜度,算法所需存儲(chǔ)空間的量度記作S(n)=O(f(n))。其中n為問題的規(guī)模,一個(gè)程序上機(jī)執(zhí)行時(shí),除了需要存儲(chǔ)空間來存放本身所用的指令、常數(shù)、變量和輸入數(shù)據(jù)以外,還需要一些對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和實(shí)現(xiàn)算法所必需的輔助空間。在進(jìn)行時(shí)間復(fù)雜度分析時(shí),如果所占空間量依賴于特定的輸入,一般都是按最壞情況來分析。4.2

數(shù)據(jù)結(jié)構(gòu)的基本概念1.什么是數(shù)據(jù)數(shù)據(jù)Data:客觀事物的符號(hào)表示。在計(jì)算機(jī)學(xué)科中，數(shù)據(jù)的概念被大大的擴(kuò)充了,不僅包含數(shù)學(xué)中的整數(shù)實(shí)數(shù)，任何能用計(jì)算機(jī)識(shí)別的符號(hào)都可作為數(shù)據(jù)。例如,課程名、地名、書名都是數(shù)據(jù)。2.什么是程序程序描述了數(shù)據(jù)加工處理的過程,即程序的任務(wù)是對(duì)數(shù)據(jù)進(jìn)行加工處理。3.什么是程序設(shè)計(jì)程序設(shè)計(jì)是將問題的求解過程用某種計(jì)算機(jī)語言表達(dá)出來。為編寫程序,首先要分析實(shí)際問題所涉及的對(duì)象，要解決數(shù)據(jù)如何表達(dá)、如何存儲(chǔ)、如何處理的問題。數(shù)據(jù)結(jié)構(gòu)就是研究關(guān)于數(shù)據(jù)表達(dá),數(shù)據(jù)存儲(chǔ)及數(shù)據(jù)處理的方法。有些計(jì)算機(jī)專家認(rèn)為程序設(shè)計(jì)=數(shù)據(jù)結(jié)構(gòu)＋算法。4.2

數(shù)據(jù)結(jié)構(gòu)的基本概念4.數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念數(shù)據(jù)Data:客觀對(duì)象的符號(hào)表示。在計(jì)算機(jī)科學(xué)中,數(shù)據(jù)的含義非常廣泛,我們把一切能夠輸人計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息,包括文字、表格,圖像等,都稱為數(shù)據(jù)。例如,課程名、地名、書名都是數(shù)據(jù)。再如,一個(gè)個(gè)人書庫管理程序所要處理的數(shù)據(jù)可能是一張。數(shù)據(jù)元素DataElement:數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮和處理。如在表4-1所示的個(gè)人書庫中，為了便于處理，把其中的每一行(代表一本書)作為一個(gè)基本單位來考慮,故該數(shù)據(jù)由10個(gè)數(shù)據(jù)元素構(gòu)成。一般情況下，一個(gè)數(shù)據(jù)元素中含有若干個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)DataStructure:相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。4.2

數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科,主要研究和討論以下三個(gè)方面的問題。(1)數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯關(guān)系如下。a.元素之問沒有關(guān)系——集合b.元素之間具有線性關(guān)系——線性數(shù)據(jù)結(jié)構(gòu)(線性表結(jié)構(gòu))c元素之間具有層次關(guān)系——層次數(shù)據(jù)結(jié)構(gòu)(樹結(jié)構(gòu))d.元素之間具有網(wǎng)狀關(guān)系——網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)(圖結(jié)構(gòu))(2)在對(duì)數(shù)據(jù)進(jìn)行處理時(shí),各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)只有兩種形式。a.順序:數(shù)據(jù)元素逐個(gè)連續(xù)存放(通過物理相鄰來確定關(guān)系)b.非順序:數(shù)據(jù)元素任意存放(通過存儲(chǔ)地址確定關(guān)系)(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。4.3

數(shù)據(jù)結(jié)構(gòu)的分類及表示1.常用的數(shù)據(jù)結(jié)構(gòu):現(xiàn)實(shí)世界中,客觀事物對(duì)象之間的關(guān)系雖然形形色色,但從抽象的觀點(diǎn)看,主要有集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。2.數(shù)據(jù)結(jié)構(gòu)的表示:圖示表示、二元組表示。圖示表示是由頂點(diǎn)和邊構(gòu)成的圖,其中頂點(diǎn)表示數(shù)據(jù),邊表示數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系。二元組表示是用一個(gè)二元組(D，S)表示數(shù)據(jù)結(jié)構(gòu)，其中D是數(shù)據(jù)元素集合,S是D上關(guān)系的集合。4.4線性結(jié)構(gòu)

線性表?xiàng)：完?duì)列

樹與二叉樹

圖

查找

排序4.4.1

線性表(1)線性表的概念及特征線性表(LinearList)：由n個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）組成的有限序列。數(shù)據(jù)元素之間具有線性關(guān)系。其中數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長度。當(dāng)n=0時(shí)稱為空表。常常將非空的線性表(n>0)記作L=(a1,a2,a3，…,an),其中ai是數(shù)據(jù)元素。線性結(jié)構(gòu)的特征：除第一個(gè)外、每個(gè)數(shù)據(jù)元素均有且只有一個(gè)前驅(qū)元素；除最后一個(gè)外,每個(gè)數(shù)據(jù)元素均有且只有一個(gè)后繼元索。線性表的特征：數(shù)據(jù)元素之間的關(guān)系是它們在數(shù)據(jù)集合中的相對(duì)位置。線性表是一種典型的線性結(jié)構(gòu)。表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置,ai是第i個(gè)數(shù)據(jù)元素,稱i為數(shù)據(jù)元素ai在線性表中的位序。4.4.1

線性表(2)線性表的基本操作及存儲(chǔ)結(jié)構(gòu)線性表的數(shù)據(jù)元素存儲(chǔ)方式分順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。順序存儲(chǔ)是指在計(jì)算機(jī)中用一-組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素。假設(shè)存儲(chǔ)每個(gè)元素占用L個(gè)存儲(chǔ)單元,并且以所占的第一個(gè)單元的地址作為該元素的存儲(chǔ)地址。線性表的順序存儲(chǔ)的優(yōu)點(diǎn):邏輯順序與物理順序一致，隨機(jī)存取等;但是也存在一些缺點(diǎn),比如插入，刪除操作要移動(dòng)元素;存儲(chǔ)空間是預(yù)分配的，不靈活，空間浪費(fèi)；表的存儲(chǔ)空間難擴(kuò)充等。這樣就需要一種靈活的存儲(chǔ)方式——鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用任意存儲(chǔ)空向單元來存放線性表的各個(gè)元素，為了能體現(xiàn)元素之間的邏輯關(guān)系(線性),在存放每個(gè)元素的同時(shí)，也存放相關(guān)元素的信息(相關(guān)元素的存儲(chǔ)地址)，即用指針來表示元素之間的邏輯關(guān)系。存放一個(gè)數(shù)據(jù)元素占用的空間為結(jié)點(diǎn)。線性表的基本操作包括線性表的初始化、插入、刪除、定位元素x在線性表中的位置,求某個(gè)元素的前驅(qū)及后繼、求線性表的長度、銷毀線性表等。4.4.2棧和隊(duì)列(1)棧的定義及特征操作棧(stack)的定義：一種特殊的線性表(數(shù)據(jù)元素之間的關(guān)系是線性關(guān)系),其插入,刪除只能在表的一-端進(jìn)行,另一端固定不動(dòng)。如(a1,a2,a3,…,an)是一個(gè)棧。表尾稱為棧頂,表頭稱為棧底，即a1為棧底元素，an為棧頂元素；在表尾插入元素的操作稱進(jìn)棧操作,在表頭刪除元素的操作稱為出棧操作；元素按a1,a2,a3,…,an的次序進(jìn)棧,第一個(gè)進(jìn)棧的元素一定在棧底，最后一個(gè)進(jìn)棧的元素一定在棧頂，第一個(gè)出棧的元素為棧頂元素,如圖4-5所示。①棧的特征及操作由于限制了插入刪除只能在一端進(jìn)行,那么元素的操作順序有“先進(jìn)后出"或“后進(jìn)先出”的特點(diǎn)(LastInFirstout-LIFOFirstInlastout——FILO)。柱的基本操作包括初始化戰(zhàn)、入棧、出棧、取棧頂元素、清空棧等操作。②棧的存儲(chǔ)方式戰(zhàn)的順序存儲(chǔ)方式同一般線性表的順序存儲(chǔ)結(jié)構(gòu)完全相同，是利用一組連續(xù)的內(nèi)存單元依次存放自找底到棧頂?shù)臄?shù)據(jù)元素，棧頂元素的位置由一個(gè)稱為棧頂指針的變量指示。其中若base=NULL,則棧結(jié)構(gòu)不存在;若top初始值=base，則棧為空棧;若出棧,則top=top-1:若入棧，則top=top+1，棧頂指針始終指向棧頂元素的下一個(gè)位置。棧的順序存儲(chǔ)方式特點(diǎn):簡單、方便,但易產(chǎn)生圈出。上溢(Overflow)棧已經(jīng)滿,又要壓入元素;下溢(Underflow)棧已經(jīng)空,還要彈出元素。上溢是一種錯(cuò)誤，使問題的處理無法進(jìn)行下去；而下溢一般認(rèn)為是一種結(jié)束條件,即問題處理結(jié)束。4.4.2棧和隊(duì)列(2)隊(duì)列的定義及特征操作隊(duì)列(Queue)的定義:是一種特殊的線性表,數(shù)據(jù)元素之間的關(guān)系是線性關(guān)系。其插入、刪除分別在表的兩端進(jìn)行,一羹只能插入,另一端只能刪除。隊(duì)首(front):進(jìn)行刪除的一端;隊(duì)尾(rear):進(jìn)行插入的一端;入隊(duì):在隊(duì)尾插入一個(gè)元素;出隊(duì):在隊(duì)首刪除一個(gè)元素。①隊(duì)列的特征隊(duì)列的特點(diǎn):由于限制了插入、刪除分別在兩端進(jìn)行,那么元素的操作順序有“先進(jìn)先出”或“后進(jìn)后出”的特點(diǎn)(FirstlnFirstOut—FIFOLastInLastOut—LILO)。隊(duì)列類似于日常的排隊(duì),新來的人站在隊(duì)尾、隊(duì)頭的人進(jìn)行事務(wù)處理后離隊(duì)。隊(duì)列通常設(shè)置兩個(gè)變量分別指示隊(duì)頭元素位置和隊(duì)尾元素的位置,這兩個(gè)變量分別稱為隊(duì)頭指針、隊(duì)尾指針。如打印機(jī)隊(duì)列管理。在一臺(tái)打印機(jī)共享使用時(shí),任何時(shí)刻它只能處理-一個(gè)用戶的打印請(qǐng)求。打印任務(wù)的組織就用一個(gè)隊(duì)列來組織(先請(qǐng)求的,先處理)。當(dāng)用戶發(fā)出打印請(qǐng)求時(shí),把打印任務(wù)入隊(duì);當(dāng)打印機(jī)空閑時(shí),從打印隊(duì)列中出隊(duì)一-個(gè)任務(wù);當(dāng)打印機(jī)阻塞時(shí),系統(tǒng)管理員可以清空隊(duì)列。②隊(duì)列的存儲(chǔ)方式同一般線性表的順序存儲(chǔ)結(jié)構(gòu)完全相同。但是由于在兩端操作,設(shè)兩個(gè)指示器(rear和front)，分別指示隊(duì)列的尾和首。其中若rear=front=0，則隊(duì)列為空隊(duì)列;若front=rear，則隊(duì)列空;若入隊(duì)，則rear=rear+1;若出隊(duì)，則front=front+1,棧頂指針始終指向棧頂元素的下一個(gè)位置。特別約定:頭指針始終指向隊(duì)列頭元素,而尾指針始終指向隊(duì)列尾元素的下一位置！4.4.3樹與二叉樹(1)樹、二叉樹的基本概念樹(Tree)是由n個(gè)結(jié)點(diǎn)的有限集合。如果n=0，稱為空樹；如果n>0,則有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn),它只有直接后維，但沒有直接前驅(qū);當(dāng)n>1,除根以外的其他結(jié)點(diǎn)劃分為m(m>0)個(gè)互不相交的有限集T1,T2，….Tm,其中每個(gè)集合本身又是一棵樹，并且稱為根的子樹(SubTree)。二叉樹的定義:二叉樹或?yàn)榭諛?或是由一個(gè)根結(jié)點(diǎn)加上兩裸分別稱為左子樹和右子樹的、互不相交的二叉樹組成。二又樹中每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(二叉樹中不存在度大于2的結(jié)點(diǎn))。兩種特殊形態(tài)的二叉樹:滿二叉樹(FullBinaryTree)——一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹；完全二叉樹(CompleteBinaryTree)——若設(shè)二叉樹的高度為h,則共有h層。除第h層外,其他各層(0—h-l)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù),第h層從右向左連續(xù)缺若干結(jié)點(diǎn),這就是完全二叉樹。4.4.3樹與二叉樹

4.4.3樹與二叉樹二叉樹由根(Root)、左子樹(Leftchild)、右子樹（Rightchild)三部分組成。二叉樹的遍歷可以分解為訪問根、遍歷左子樹和遍歷右子樹。約定先左后右，有種遍歷方法，即DLR,LDR,LRD，分別稱為先序遍歷、中序遍歷、后序遍歷。先序遍歷(DLR)的方法:若二叉樹非空,訪問根結(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹。中序遍歷(LDR)的方法:若二叉樹非空,中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。后序遍歷(LRD)的方法:若二叉樹非空，后序遍歷左子樹;后序歷右子樹，訪問根結(jié)點(diǎn)。4.4.4圖(1)圖的概念和存儲(chǔ)圖是由頂點(diǎn)集合（vertex）及頂點(diǎn)問的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph=（V，E），其中V

=

{x

|

x

屬于某個(gè)數(shù)據(jù)對(duì)象}是頂點(diǎn)的有窮非空集合；E1=

{（x,y）|x,y屬于V}E2

={<x,y>1|x,y屬于V&&

Path（x,y）}。其中，E1是頂點(diǎn)之間關(guān)系的有窮集合，也叫作邊（edge）集合，此時(shí)的圖稱為無向圖。E2

表示從x到y(tǒng)的一條弧，且稱x為弧尾，y為弧頭，這樣的圖稱為有向圖。

圖是多對(duì)多的結(jié)構(gòu)，比線性結(jié)構(gòu)、樹結(jié)構(gòu)復(fù)雜，所以其存儲(chǔ)結(jié)構(gòu)也要復(fù)雜些。與線性結(jié)構(gòu)、樹結(jié)構(gòu)一樣，圖的存儲(chǔ)結(jié)構(gòu)至少要保存兩類信息：1）頂點(diǎn)的信息；2）頂點(diǎn)間的關(guān)系。頂點(diǎn)的編號(hào):為了使圖的存儲(chǔ)結(jié)構(gòu)與圖一一對(duì)應(yīng),在討論圖的存儲(chǔ)結(jié)構(gòu)時(shí),首先要給圖的所有頂點(diǎn)編號(hào)。圖的存儲(chǔ)方式主要包括數(shù)組表示法和鄰接表表示法。數(shù)組表示法也叫作鄰接矩陣、在圖的鄰接矩陣表示中,有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表,還有一個(gè)表示各個(gè)頂點(diǎn)之問關(guān)系的鄰接矩陣。4.4.4圖(2)圖的遍歷及最小生成樹從圖中某頂點(diǎn)出發(fā)訪遍圖中所有的頂點(diǎn),且使每個(gè)頂點(diǎn)僅被訪問一次,這一過程就叫作圖的遍歷(TraversingGraph)。圖中可能存在回路。且圖的任一頂點(diǎn)都可能與其他頂點(diǎn)相通,在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。為了避免重復(fù)訪問,可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組visited[1。輔助數(shù)組visited[1的初始狀態(tài)為0，在圖的遍歷過程中,一旦某一個(gè)頂點(diǎn)i被訪問,就立即讓visited[i]為1，防止它被多次訪問,兩種圖的遍歷方法:深度優(yōu)先搜索DFS(DepthFirstSearch)，廣度優(yōu)先搜索BFS(BreadthFirstSearch)。最小生成樹:在n個(gè)城市之間建立通信網(wǎng)絡(luò),則連通n個(gè)城市只需要n-1條線路，這是一個(gè)生成樹概念的應(yīng)用問題。如何構(gòu)造一個(gè)造價(jià)最低的通信網(wǎng)絡(luò)呢?在n個(gè)城市之間,最多可能設(shè)置的直接線路是n(n-1)/2條，每一條線路都有一個(gè)造價(jià)預(yù)算,如何在這些可能的線路中選擇n-1條以使總的耗費(fèi)最少而又實(shí)現(xiàn)通信網(wǎng)絡(luò)呢?4.4.4圖可以用連通網(wǎng)表示n個(gè)城市及n個(gè)城市之問可能設(shè)置的通信線路,其中頂點(diǎn)表示城市,邊表示兩城市之間的通信線路,邊上的權(quán)值表示線路造價(jià)預(yù)算。n個(gè)頂點(diǎn)的連通網(wǎng)可以有多個(gè)生成樹,每一棵生成樹都可以是一個(gè)通信網(wǎng)絡(luò)。一棵生成樹的代價(jià)定義為生成樹上各邊權(quán)值之和。要選擇一棵總耗費(fèi)最少的生成樹是我們要解決的問題使用不同的遍歷圖的方法，可以得到不同的生成樹;從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹有n個(gè)頂點(diǎn)、n-1條邊。構(gòu)造最小生成樹的準(zhǔn)則:1必須使用且僅使用該網(wǎng)絡(luò)中的n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn);2不能使用產(chǎn)生回路的邊;3各邊上的權(quán)值的總和達(dá)到最小。4.4.5查找查找是數(shù)據(jù)處理領(lǐng)域中的一個(gè)重要內(nèi)容,查找的效率將直接影響到數(shù)據(jù)處理的效率,查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。通常,根據(jù)不同的數(shù)據(jù)結(jié)構(gòu),應(yīng)采用不同的查找方法。(1)順序查找順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素,其基本方法是從線性表的第一個(gè)元素開始,依次將線性表中的元索與被查元素進(jìn)行比較,若相等則表示找到(查找成功):若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等,則表示線性表中沒有要找的元素(查找失敗)。在進(jìn)行順序查找過程中,如果線性表中的第一個(gè)元素就是被查找元素,則只需做一次比較就查找成功,查找效率最高；但如果被查的元素是線性表中的最后一個(gè)元素,或者被查元素根本不在線性表中,則為了查找這個(gè)元素需要與線性表中所有的元素進(jìn)行比較,這是順序查找的最壞情況。在平均情況下,利用順序查找法在線性表中查找一個(gè)元素,大約要與線性表中一半的無素進(jìn)行比較。由此可以看出,對(duì)于大的線性表來說,順序查找的效率是很低的。雖然順序查找的效率不高，但在下列兩種情況下也只能采用順序查找。如果線性表為無序表(表中元素的排列是無序的),則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),都只能用順序查找。即使是有序線性表,如n采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),也只能用順序查找。4.4.5查找(2)二分法查找二分法查找(又稱對(duì)分查找)只適用于順序存儲(chǔ)的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列(從小到大，但允許相鄰元素值相等)。設(shè)有序線性表的長度為n,被元素為x，則對(duì)分查找的方法如下。將x與線性表的中間項(xiàng)進(jìn)行比較,若中間項(xiàng)的值等于x,則說明查到,查找結(jié)束;若x小于中間項(xiàng)的值,則在線性表的前半部分(中間項(xiàng)以前的部分)以相同的方法進(jìn)行查找;若x大于中間項(xiàng)的值,則在線性表的后半部分(中間項(xiàng)以后的部分)以相同的方法進(jìn)行查找。這個(gè)過程一直進(jìn)行到查找成功或子表長度為0(說明線性表中沒有這個(gè)元素)為止。顯然,當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找，并且,二分查找的效率要比順序查找高得多?？梢宰C明,對(duì)于長度為n的有序線性表,在最壞情況下,二分查找只需要比較logn次,而順序查找需要比較n次。4.4.6排序排序也是數(shù)據(jù)處理的重要內(nèi)容。所謂排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列。排序的方法有很多,根據(jù)待排序序列的規(guī)模以及對(duì)數(shù)據(jù)處理的要求,可以采用不同的排序方法。本節(jié)主要介紹一些常用的排序方法。排序可以在各種不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。在本節(jié)所介紹的排序方法中，其排序的對(duì)象一般認(rèn)為是順序存儲(chǔ)的線性表,在程序設(shè)計(jì)語言中就是一維數(shù)組。(1)交換類排序所謂交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。冒泡排序法與快速排序法都屬丁交換類的排序方法。4.4.6排序①冒泡排序法:冒泡排序法是一種最簡單的交換類排序方法,它是通過相鄰數(shù)據(jù)元素的交換逐步將線性表變冒泡排序法的基本過程如下:首先,從表頭開始往后掃描線性表,在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中、前面的元素大于后面的元素,則將它們互換,稱為消去了一個(gè)遞序。顯然，在掃描過程中，不斷地將兩相鄰元索中的大者往后移動(dòng)，最后就將線性表中的最大者換到了表的最后,這也是線性表中最大元素應(yīng)有的位置。然后,從后到前掃描剩下的線性表，同樣,在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中、后面的元素小于前面的元素，則將它們互換，這樣就又消去了一個(gè)逆序。顯然,在掃描過程中，不斷地將兩相鄰元素中的小者往前移動(dòng)，最后就將剩下線性表中的最小者換到了表的最前面,這也是線性表中最小元素應(yīng)有的位置。對(duì)剩下的線性表重復(fù)上述過程、直到剩下的線性表變空為止,此時(shí)的線性表已經(jīng)變?yōu)橛行?。在上述排序過程中，對(duì)線性表的每一次來回掃描后,都將其中的最大者沉到了表的底部、最小者像氣泡一樣冒到表的前頭。冒泡排序由此而得名,且冒泡排序又稱下沉排序。假設(shè)線性表的長度為n，則在最壞情況下,冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n-1)/2。但這個(gè)工作量不是必需的、一般情況下要小于這個(gè)工作量。4.4.6排序②快速排序法:在前面所討論的冒泡排序法中,由于在掃描過程中只對(duì)相鄰兩個(gè)元素進(jìn)行比較,因此,在互換兩個(gè)相鄰元素時(shí)只能消除一-個(gè)逆序。如果通過兩個(gè)(不是相鄰的)元素的交換,能夠消除線性表中的多個(gè)逆序，就會(huì)大大加快排序的速度。顯然，為了通過一次交換能消除多個(gè)逆序、就不能像冒泡排序法那樣對(duì)相鄰兩個(gè)元素進(jìn)行比較，因?yàn)檫@只能使相鄰兩個(gè)元素進(jìn)行交換,從而只能消除一個(gè)逆序。下面介紹的快速排序法可以實(shí)現(xiàn)通過一次交換而消除多個(gè)逆序?？焖倥判蚍ㄒ彩且环N互換類的排序方法，但由于它比冒泡排序法的速度快,因此,稱為快速排序法?？焖倥判蚍ǖ幕舅枷肴缦?。從線性表中選取一個(gè)元素,設(shè)為T,將線性表后面小于T的元素移到前面,而前面大于T的元素移到后面，結(jié)果就將線性表分成了兩部分(稱為兩個(gè)子表)，T插入到其分界線的位置處，這個(gè)過程稱為線性表的分割。通過對(duì)線性表的一次分割,就以T為分界線,將線性表分成了前后兩個(gè)子表，且前面子表中的所有元素均不大于T,而后面子表中的所有元素均不小于T。如果對(duì)分