第6章算法與數(shù)據(jù)結(jié)構(gòu)6.1概論6.2算法6.3數(shù)據(jù)結(jié)構(gòu)6.4數(shù)組6.5排序返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第1頁。6.1概論6.1.1引言一般來說，用計(jì)算機(jī)解決一個(gè)具體問題時(shí)大致需要經(jīng)過下列幾個(gè)步驟：首先要從具體問題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，最后編寫出程序，進(jìn)行測試、調(diào)試直至得到最終解答。尋求數(shù)學(xué)模型實(shí)質(zhì)是分析問題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。6.1.2有關(guān)概念和術(shù)語在系統(tǒng)地學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)知識(shí)之前，先對(duì)一些基本概念和術(shù)語賦予確切的含義。下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第2頁。6.1概論數(shù)據(jù)（Data）是信息的載體，是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合?，F(xiàn)實(shí)世界信息的分析、復(fù)制、傳播首先要符號(hào)化，以便于計(jì)算機(jī)的處理。數(shù)據(jù)分為兩類：數(shù)值型數(shù)據(jù)（主要用于數(shù)值計(jì)算）和非數(shù)值型數(shù)據(jù)（文字、圖形、圖像、音頻、視頻等）。數(shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、節(jié)點(diǎn)、頂點(diǎn)、記錄等。一個(gè)數(shù)據(jù)元素可由不可分割的若干個(gè)數(shù)據(jù)項(xiàng)（DataItem)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第3頁。6.1概論數(shù)據(jù)對(duì)象（DataObject）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。在具體問題中，數(shù)據(jù)元素都具有相同的性質(zhì)（元素值不一定相等），例如英文字符集是數(shù)據(jù)的一個(gè)子集，它由能夠表示單詞這樣的共同屬性的26個(gè)字母組成一個(gè)數(shù)據(jù)對(duì)象。數(shù)據(jù)元素是數(shù)據(jù)對(duì)象的一個(gè)實(shí)例。數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在任何問題中數(shù)據(jù)元素之間總是存在著聯(lián)系。把某一數(shù)據(jù)對(duì)象及該數(shù)據(jù)對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成的實(shí)體叫做數(shù)據(jù)結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有下列4類基本的結(jié)構(gòu)：上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第4頁。6.1概論（1）集合結(jié)構(gòu)。在集合結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)系是屬于同一個(gè)集合。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。（2）線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。（3）樹型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。（4）圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系。圖形結(jié)構(gòu)也稱為網(wǎng)狀結(jié)構(gòu)，如城市交通圖。圖6-1為表示上述4種基本結(jié)構(gòu)的示意圖。由于集合是數(shù)據(jù)元素之間關(guān)系極為松散的一種結(jié)構(gòu)，因此也可用其他結(jié)構(gòu)來表示。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第5頁。6.1概論數(shù)據(jù)類型（DataType）是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念，它最早出現(xiàn)在高級(jí)程序語言中，用以刻畫程序操作對(duì)象的特性。在高級(jí)程序語言編寫的程序中，每個(gè)變量、常量或表達(dá)式都有一個(gè)它所屬的確定的數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了在程序執(zhí)行期間變量或表達(dá)式所有可能取值的范圍，以及在這些值上允許的操作。因此數(shù)據(jù)類型是一個(gè)值的集合和定義在該值集上的一組操作的總稱。按“值”的不同特性，高級(jí)程序語言中的數(shù)據(jù)類型可分為兩類：一類是非結(jié)構(gòu)的原子類型。原子類型的值是不可分解的，如int類型。另一類是結(jié)構(gòu)類型。結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第6頁。6.1概論抽象數(shù)據(jù)類型（AbstractDataType，ADT）是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用。抽象數(shù)據(jù)類型可以使我們更容易描述現(xiàn)實(shí)世界。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念。另一方面，抽象數(shù)據(jù)類型范疇更廣，它不再局限于前述各處理器中已定義并實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自己定義的數(shù)據(jù)類型。抽象數(shù)據(jù)類型的特征是使用與實(shí)現(xiàn)相分離，實(shí)行封裝和信息隱蔽。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第7頁。6.1概論也就是說，在抽象數(shù)據(jù)類型設(shè)計(jì)時(shí)，把類型的定義與其實(shí)現(xiàn)分離開來。抽象數(shù)據(jù)類型的定義可由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作組成。而數(shù)據(jù)結(jié)構(gòu)又包括數(shù)據(jù)元素及元素間的關(guān)系，因此抽象數(shù)據(jù)類型一般由元素、關(guān)系及操作3種要素來定義。抽象數(shù)據(jù)類型可用三元組來表示：（D，R，P）其中D是數(shù)據(jù)對(duì)象，R是D上的關(guān)系集；P是對(duì)D的基本操作集。6.1.3算法與數(shù)據(jù)結(jié)構(gòu)研究內(nèi)容與關(guān)系算法和數(shù)據(jù)結(jié)構(gòu)研究的是計(jì)算機(jī)科學(xué)中許多最基本的問題，是研究問題求解技術(shù)、算法設(shè)計(jì)、程序設(shè)計(jì)的基礎(chǔ)。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第8頁。6.1概論21世紀(jì)60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對(duì)獨(dú)立，結(jié)構(gòu)程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要內(nèi)容，人們越來越重視數(shù)據(jù)結(jié)構(gòu)。從20世紀(jì)70年代中期到80年代，各種數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)。目前，數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)，一方面，面向個(gè)專門領(lǐng)域中特殊問題的數(shù)據(jù)結(jié)構(gòu)得到研究和發(fā)展，如多維圖形數(shù)據(jù)結(jié)構(gòu)等；另一方面，從抽象數(shù)據(jù)類型和面向?qū)ο蟮挠^點(diǎn)來討論數(shù)據(jù)結(jié)構(gòu)已成為一種新的趨勢，越來越被人們重視。數(shù)據(jù)結(jié)構(gòu)和算法這兩者之間有著十分密切的關(guān)系。數(shù)據(jù)結(jié)構(gòu)與數(shù)學(xué)、計(jì)算機(jī)硬件和軟件有十分密切的關(guān)系。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第9頁。6.1概論數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心課程，是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫、人工智能等課程的基礎(chǔ)。同時(shí)，在信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)等工程技術(shù)領(lǐng)域中也廣泛地使用數(shù)據(jù)結(jié)構(gòu)技術(shù)。數(shù)據(jù)結(jié)構(gòu)中的算法是十分重要的內(nèi)容。實(shí)現(xiàn)算法、表達(dá)算法、驗(yàn)證算法、分析算法，研究和改進(jìn)算法，構(gòu)成了計(jì)算機(jī)科學(xué)的多個(gè)分支。上一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第10頁。6.2算法算法是程序的核心、編程的基礎(chǔ)。在算法設(shè)計(jì)時(shí)先要確定相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，而在討論某種數(shù)據(jù)結(jié)構(gòu)時(shí)也必然會(huì)涉及相應(yīng)的算法。6.2.1算法的定義當(dāng)有了數(shù)據(jù)表示之后，就要考慮數(shù)據(jù)操作，把這些操作有效集成來完成各項(xiàng)任務(wù)，就是算法。算法（Algorithm）是對(duì)特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。算法應(yīng)該具有下列特性：（1）有窮性：算法必須總是（對(duì)任何合法的輸入值）在有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第11頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第12頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第13頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第14頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第15頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第16頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第17頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第18頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第19頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第20頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第21頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第22頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第23頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第24頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第25頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第26頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第27頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第28頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第29頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第30頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第31頁。6.2算法（2）確定性：算法中的每一條指令必須有確切的含義，無二義性。在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對(duì)相同的輸入只能得出相同的輸出。（3）可行性：算法是可行的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。（4）輸入：算法具有零個(gè)或多個(gè)輸入，這些輸入取自特定的數(shù)據(jù)對(duì)象集合。（5）輸出：算法具有一個(gè)或多個(gè)輸出，這些輸出同輸入之間存在某種特定的關(guān)系。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第32頁。6.2算法6.2.2算法設(shè)計(jì)的要求要設(shè)計(jì)一個(gè)好的算法，通常要考慮以下要求：（1）正確性：算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求。通常一個(gè)大型問題的要求，要以特定的規(guī)格說明方式給出，目前多數(shù)是用自然語言描述需求，它至少應(yīng)當(dāng)包括對(duì)于輸入、輸出和加工處理等的明確無歧義性的描述。設(shè)計(jì)或選擇的算法應(yīng)能正確地反映這種需求。通常認(rèn)為，算法對(duì)于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果即為合格的算法。(2)可讀性：算法應(yīng)當(dāng)思路清晰、層次分明、簡單明了、易讀易懂。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第33頁。6.2算法（3）健壯性；當(dāng)輸入不合法的數(shù)據(jù)時(shí)，算法應(yīng)能進(jìn)行適當(dāng)處理，不致于引起嚴(yán)重后果。（4）高效性：算法應(yīng)當(dāng)有效使用存儲(chǔ)空間和有較高的時(shí)間效率。6.2.3算法表示形式同一個(gè)算法會(huì)有不同的表示形式，一般來講，主要有4種表示形式：（1）文本：是用文字來說明解決問題的具體步驟。（2）流程圖：使用規(guī)范的圖形符號(hào)來說明解決問題的具體步驟。（3）偽代碼：混合使用程序設(shè)計(jì)語言的語句和自然語言來說明解決問題的具體步驟。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第34頁。6.2算法（4）程序代碼：直接以程序設(shè)計(jì)語言的語句來說明解決問題的具體步驟。流程圖是一種描述程序處理過程的圖示方法。常用的流程圖是用一些具有特定含義的框和流向線組成。常用的流程圖符號(hào)如圖6-2所示。流程圖表示了程序處理過程和步驟，又表示了程序的結(jié)構(gòu)，簡單、直觀，在程序設(shè)計(jì)中被廣泛采用。6.2.4算法性能分析算法與數(shù)據(jù)結(jié)構(gòu)是相輔相成的。解決某一特定類型問題的算法可以選擇不同的數(shù)據(jù)結(jié)構(gòu)，而且選擇恰當(dāng)與否直接影響算法的效率。反之，一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由各種算法的執(zhí)行來體現(xiàn)。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第35頁。6.2算法一個(gè)問題可能有多種不同的算法，一些算法比其他算法效率高。進(jìn)行算法分析的目的是尋找高效的算法來解決不同的問題，提高工作效率。衡量算法效率的方法主要有兩大類：事后統(tǒng)計(jì)方法（后期測試）和算法的事前分析估算方法。1．事后統(tǒng)計(jì)方法主要是在算法的關(guān)鍵部位插入計(jì)時(shí)器，當(dāng)算法執(zhí)行時(shí)，打開計(jì)時(shí)器，終止時(shí)關(guān)閉，這樣可以得到算法執(zhí)行時(shí)間的差值，從而衡量算法的效率。但這種方法存在一個(gè)明顯缺陷，即它與計(jì)算機(jī)軟硬件相關(guān)，并不能確切地反映多個(gè)算法的差別，不利于較大范圍內(nèi)的算法比較（異地、異時(shí)、異境）。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第36頁。6.2算法2．事前分析估算方法當(dāng)我們將一個(gè)算法轉(zhuǎn)換成程序并在計(jì)算機(jī)上執(zhí)行時(shí)，其運(yùn)行所需要的時(shí)間取決于下列因素：（1）算法選用何種策略。（2）機(jī)器執(zhí)行指令的速度。（3）書寫程序的語言。實(shí)現(xiàn)語言的級(jí)別越高，其執(zhí)行效率就越低。（4）編譯程序所生成目標(biāo)代碼的質(zhì)量。對(duì)于代碼優(yōu)化較好的編譯程序，其所生成的程序質(zhì)量較高。（5）問題的規(guī)模。隨著處理問題的數(shù)據(jù)增大，處理會(huì)越來越困難，把描述數(shù)據(jù)增大程度的量叫做問題規(guī)模。規(guī)模越大，消耗時(shí)間越多。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第37頁。6.2算法算法度量可以從時(shí)間復(fù)雜度和空間復(fù)雜度兩方面進(jìn)行。分析算法是一個(gè)復(fù)雜的工作，需要如圖論、集合論、組合分析、概率論等方面的理論基礎(chǔ)，這方面內(nèi)容可以參考其他資料。6.2.5常用算法算法是對(duì)某個(gè)問題求解過程的描述。同一問題有多種算法描述，問題的種類很多，算法更多?？傮w上可以把算法分為兩大類：數(shù)值算法和非數(shù)值算法。常用算法有以下幾種。1．累加、連乘在循環(huán)結(jié)構(gòu)中，最常用的算法是累加和連乘。累加是在原有和的基礎(chǔ)上每次加一個(gè)數(shù)，連乘則是在原有積的基礎(chǔ)上每次乘一個(gè)數(shù)。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第38頁。6.2算法在該算法中，累積個(gè)數(shù)與連乘次數(shù)都通過循環(huán)變量來控制。2．求素?cái)?shù)素?cái)?shù)也稱為質(zhì)數(shù)，就是一個(gè)大于2的整數(shù)；并只能被1和它本身整除，而不能被其他整數(shù)整除的數(shù)。判別某數(shù)m是否為素?cái)?shù)的方法很多，最簡單的是從素?cái)?shù)的定義來求解，其算法思想是：m從i=2，3…，m-1判別是否被i整除，只要有一個(gè)能整除，m就不是素?cái)?shù)；否則m是素?cái)?shù)。3．窮舉算法又稱“枚舉法”，即將可能出現(xiàn)的各種情況一一測試，判斷是否滿足條件，一般采用循環(huán)來實(shí)現(xiàn)。循環(huán)次數(shù)都與運(yùn)算量成正比。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第39頁。6.2算法因此，在多重循環(huán)中，為提高運(yùn)行速度，對(duì)程序更要考慮優(yōu)化，應(yīng)考慮以下方面：（1）盡量利用已知條件，減少循環(huán)重?cái)?shù)。（2）合理選擇內(nèi)外層的循環(huán)控制變量，即將循環(huán)次數(shù)多的放在內(nèi)循環(huán)。（3）盡量少用變體類型變量（可將上例中變量聲明語句去掉加以比較）。4．遞推算法“遞推算法”又稱為“迭代算法”，其基本思想是把一個(gè)復(fù)雜的計(jì)算過程轉(zhuǎn)化為簡單過程的多次重復(fù)。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第40頁。6.2算法每次重復(fù)都從舊值的基礎(chǔ)上遞推出新值，并由新值代替舊值。5．求最大值或最小值在若干個(gè)數(shù)中求最大值，一般先假設(shè)一個(gè)較小的數(shù)為最大值的初值，若無法估計(jì)較小的值，則取第一個(gè)數(shù)為最大值的初值；然后將每一個(gè)數(shù)與最大值比較，若該數(shù)大于最大值，將該數(shù)替換為最大值；依次逐一比較。求最小值的算法類似，只是先假設(shè)一個(gè)較大的數(shù)為最小值。上一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第41頁。6.3數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容是構(gòu)造復(fù)雜軟件系統(tǒng)的基礎(chǔ)，它的核心技術(shù)是分解與抽象。通過分解可以劃分出數(shù)據(jù)的3個(gè)層次；再通過抽象，舍棄數(shù)據(jù)元素的具體內(nèi)容，就得到邏輯結(jié)構(gòu)。類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實(shí)現(xiàn)細(xì)節(jié)，就得到運(yùn)算的定義。上述兩個(gè)方面的結(jié)合可以將問題變換為數(shù)據(jù)結(jié)構(gòu)。這是一個(gè)從具體（即具體問題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）的過程。然后，通過增加對(duì)實(shí)現(xiàn)細(xì)節(jié)的考慮進(jìn)一步得到存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)運(yùn)算，從而完成設(shè)計(jì)任務(wù)。這是一個(gè)從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實(shí)現(xiàn)）的過程。6.3.1數(shù)據(jù)結(jié)構(gòu)概論對(duì)于每種數(shù)據(jù)結(jié)構(gòu)，都要考慮它的代價(jià)和效益。下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第42頁。6.3數(shù)據(jù)結(jié)構(gòu)對(duì)于要解決的問題，都有時(shí)間和空間上的限制。在選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，需要考慮存儲(chǔ)空間和操作時(shí)間的限制，要選擇適合問題的最好的數(shù)據(jù)結(jié)構(gòu)。1．?dāng)?shù)據(jù)結(jié)構(gòu)的定義一個(gè)數(shù)據(jù)結(jié)構(gòu)有3個(gè)要素：一是數(shù)據(jù)元素的集合；二是關(guān)系的集合；三是進(jìn)行的運(yùn)算。在形式上，數(shù)據(jù)結(jié)構(gòu)通?？梢圆捎靡粋€(gè)二元數(shù)組來表示。數(shù)據(jù)結(jié)構(gòu)的形式定義為：Data_Structure=(D，R)其中，D是數(shù)據(jù)元素的有限集，R是關(guān)系上的有限集。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第43頁。6.3數(shù)據(jù)結(jié)構(gòu)把常用的數(shù)據(jù)結(jié)構(gòu)按照它們的表示方法和行為特性進(jìn)行分類，可分為順序表、鏈表、堆棧、隊(duì)列、樹、二叉樹、圖、集合等。2．?dāng)?shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)定義中的關(guān)系是指數(shù)據(jù)之間的邏輯關(guān)系，故也稱為數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)僅僅刻畫了數(shù)據(jù)元素之間的邏輯關(guān)系，但我們并不清楚這些結(jié)構(gòu)在計(jì)算機(jī)內(nèi)部是如何實(shí)現(xiàn)的，為此需要考慮數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)的內(nèi)存中是如何存放的。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為物理結(jié)構(gòu)，又稱存儲(chǔ)結(jié)構(gòu)。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示和元素間關(guān)系的表示。一種邏輯結(jié)構(gòu)可以采用多種存儲(chǔ)表示。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第44頁。6.3數(shù)據(jù)結(jié)構(gòu)通常，數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)采用順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的方法。顯然，它是依賴于計(jì)算機(jī)的。若邏輯結(jié)構(gòu)相同、物理結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)，用不同的名稱來標(biāo)識(shí)它們。我們可以按照數(shù)據(jù)的結(jié)構(gòu)（邏輯結(jié)構(gòu)和物理結(jié)構(gòu)）特性在該結(jié)構(gòu)存在期間的變動(dòng)情況，將它們劃分為靜態(tài)結(jié)構(gòu)、半靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)結(jié)構(gòu)。其中靜態(tài)結(jié)構(gòu)就是在數(shù)據(jù)結(jié)構(gòu)存在期間總是不變動(dòng)的。3．?dāng)?shù)據(jù)結(jié)構(gòu)常用算法數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，但運(yùn)算的具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第45頁。6.3數(shù)據(jù)結(jié)構(gòu)一般有以下幾種常用運(yùn)算：（1）檢索。檢索就是在數(shù)據(jù)結(jié)構(gòu)里查找滿足一定條件的節(jié)點(diǎn)。一般是給定一個(gè)某字段的值，找具有該字段值的節(jié)點(diǎn)。（2）插入。往數(shù)據(jù)結(jié)構(gòu)里增加新的節(jié)點(diǎn)。（3）刪除。把指定的結(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)中去掉。（4）更新。改變指定節(jié)點(diǎn)的一個(gè)或多個(gè)字段的值。（5）排序。把節(jié)點(diǎn)按某種指定的順序重新排列。例如遞增或遞減。6.3.2線性表線性表是一種線性結(jié)構(gòu)。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第46頁。6.3數(shù)據(jù)結(jié)構(gòu)它是最簡單、最基本也是最常用的一種線性結(jié)構(gòu)，經(jīng)常用于構(gòu)造更復(fù)雜、通用的數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)的特點(diǎn)是數(shù)據(jù)元素之間是一種線性關(guān)系，數(shù)據(jù)元素“一個(gè)接一個(gè)地排列”，也就是說，在數(shù)據(jù)元素的非空有限集中，數(shù)據(jù)元素的排列是順序的，排列在某個(gè)數(shù)據(jù)元素b之前的數(shù)據(jù)元素a稱為b的前驅(qū)，而數(shù)據(jù)元素b稱為a的后繼。線性結(jié)構(gòu)是除第一個(gè)元素之外，集合中的每個(gè)元素均有且只有一個(gè)前驅(qū)；除最后一個(gè)數(shù)據(jù)元素外，均有且只有一個(gè)后繼。定義線性表如下：線性表是具有相同數(shù)據(jù)類型的n個(gè)數(shù)據(jù)元素的有限序列，通常記為：上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第47頁。6.3數(shù)據(jù)結(jié)構(gòu)其中，n為表長，n=0時(shí)稱為空表。在線性表中數(shù)據(jù)元素可以是任意類型，但必須是相同類型的，也就是說必須屬于同一數(shù)據(jù)對(duì)象。邏輯上形式地可以定義為：一種數(shù)據(jù)結(jié)構(gòu)D_S=(D，R)，其中線性結(jié)構(gòu)的物理實(shí)現(xiàn)，通常使用順序存儲(chǔ)法和鏈接存儲(chǔ)法，即順序表和鏈表。選擇哪種物理結(jié)構(gòu)是根據(jù)具體應(yīng)用中主要作何種運(yùn)算而定。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第48頁。6.3數(shù)據(jù)結(jié)構(gòu)1．向量（一維數(shù)組）定義：向量結(jié)構(gòu)邏輯上是有限元素的有序集合，并且用一個(gè)整數(shù)符號(hào)（亦稱下標(biāo)）標(biāo)志向量中各元素。又稱一維數(shù)組。向量結(jié)構(gòu)具有以下兩個(gè)極為重要的特性：（1）均勻性。向量的所有元素具有相同的元素描述，即向量中每個(gè)元素的數(shù)據(jù)類型相同。（2）有序性。向量中各元素是有序的，元素之間的順序在其存在期間是不能改變的，下標(biāo)唯一確定了元素在向量中的位置。向量的物理結(jié)構(gòu)，即向量在計(jì)算機(jī)內(nèi)存中存放的組織形式。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第49頁。6.3數(shù)據(jù)結(jié)構(gòu)通常要求分配一塊連續(xù)存儲(chǔ)空間，按向量元素的邏輯順序，一個(gè)接一個(gè)地存放元素。對(duì)向量要經(jīng)常進(jìn)行的運(yùn)算有以下幾種：（1）取出向量中第i個(gè)元素。（2）更新向量中第i個(gè)元素。（3）在向量第i個(gè)元素之后插入新元素。（4）刪除向量中第i個(gè)元素。（5）重新排序向量中元素。在插入運(yùn)算中，首先把第i個(gè)元素之后的所有元素都向后移動(dòng)一個(gè)元素的位置，以空出位置插入新元素。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第50頁。6.3數(shù)據(jù)結(jié)構(gòu)在刪除運(yùn)算中，為保持向量元素的順序，必須把a(bǔ)i，ai+1，…，an元素向上移動(dòng)一個(gè)位置。因此，這兩個(gè)運(yùn)算開銷較大。2．棧棧是一種“限定性的線性表”，對(duì)于它所有插入和運(yùn)算都限制在表的同一端進(jìn)行，這一端稱為棧的“頂”，另一端稱為棧的“底”。棧在計(jì)算機(jī)系統(tǒng)中很有用，一般用來保存一些尚未處理和等待處理的數(shù)據(jù)項(xiàng)。棧對(duì)數(shù)據(jù)項(xiàng)的處理是遵循“后進(jìn)先出”的原則，即每次刪除的數(shù)據(jù)項(xiàng)即是最后插入的數(shù)據(jù)項(xiàng)，而最先插入的數(shù)據(jù)項(xiàng)被放在棧底，最后才處理它。因此，棧又稱為“后進(jìn)先出表（LIFO）”或下推表。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第51頁。6.3數(shù)據(jù)結(jié)構(gòu)一個(gè)典型的順序分配的?？梢杂靡痪S數(shù)組表示它的物理結(jié)構(gòu)，用一個(gè)指針sp指向它的棧頂元素，變量sp中存放著棧頂元素對(duì)應(yīng)的下標(biāo)地址。圖6-5（a）是一個(gè)棧的示意圖，進(jìn)棧和出棧運(yùn)算都是依靠改變sp指針來實(shí)現(xiàn)的。在棧上定義的運(yùn)算主要是在棧頂上作進(jìn)棧（插入）和出棧（刪除）操作。下面通過一個(gè)實(shí)例來分析一下進(jìn)棧和出棧運(yùn)算的具體執(zhí)行情況。假設(shè)我們定義一個(gè)由3個(gè)單元組成的一維數(shù)組作為棧存儲(chǔ)區(qū)，用一個(gè)單元sp存放棧的下標(biāo)地址。見圖6-5（b）。棧的基本運(yùn)算有以下兩種：上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第52頁。6.3數(shù)據(jù)結(jié)構(gòu)（1）進(jìn)棧push（x）。往棧stack中插入（或壓入）一個(gè)值為x的表目。（2）出棧pop（）。從棧stack中刪除（或彈出）一個(gè)表目。在計(jì)算機(jī)所使用的各種數(shù)據(jù)結(jié)構(gòu)中，棧的應(yīng)用十分廣泛：1）算術(shù)表達(dá)式的計(jì)算表達(dá)式通常形式如下：(A+B)*D+E/(F+A*D)+C一般情況是左、右各一個(gè)運(yùn)算對(duì)象，中間為運(yùn)算符；只有單目運(yùn)算是一個(gè)運(yùn)算符和右邊一個(gè)運(yùn)算對(duì)象（如~x），這種表達(dá)式稱為表達(dá)式的中綴表示。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第53頁。6.3數(shù)據(jù)結(jié)構(gòu)編議程序?yàn)榱颂幚矸奖?，首先把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，即兩個(gè)運(yùn)算對(duì)象在前，它們的運(yùn)算符在后，這種表達(dá)式也稱為逆波蘭表達(dá)式。上式轉(zhuǎn)換后，形式為：AB+D*EFAD*+/+C+從上式可以看到，轉(zhuǎn)換后的形式不再有括號(hào)。這種轉(zhuǎn)換可以通過棧來實(shí)現(xiàn)。對(duì)表達(dá)式中的字符一個(gè)一個(gè)地自左至右進(jìn)行掃描，當(dāng)遇到運(yùn)算對(duì)象時(shí)就直接輸出或存入一個(gè)數(shù)組中，而遇到運(yùn)算符時(shí)就進(jìn)棧。進(jìn)棧的原則是要保持棧頂?shù)倪\(yùn)算符的優(yōu)先級(jí)最高，也就是當(dāng)前遇到的運(yùn)算符的優(yōu)先級(jí)若高于棧頂運(yùn)算符的優(yōu)先級(jí)時(shí)，則進(jìn)棧作為棧頂元素，否則將棧頂運(yùn)算符退棧輸出，然后把優(yōu)先級(jí)低的運(yùn)算符進(jìn)棧。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第54頁。6.3數(shù)據(jù)結(jié)構(gòu)當(dāng)掃描時(shí)遇到開括弧“（”就直接進(jìn)棧，但在遇到閉括弧“）”時(shí)則將相應(yīng)開括弧后面的全部運(yùn)算符退棧輸出，然后再退出開括弧。括號(hào)內(nèi)的運(yùn)算符同樣按上述進(jìn)棧原則處理。3．隊(duì)列隊(duì)列也是一種限定性的線性表，對(duì)于它的所有插入都在表的一端進(jìn)行，所有刪除都在表的另一端進(jìn)行。進(jìn)行刪除的一端稱為隊(duì)列的頭，進(jìn)行插入的一端稱為隊(duì)列的尾。隊(duì)列結(jié)構(gòu)在日常生活中也不少見，我們經(jīng)常要排隊(duì)買東西，排隊(duì)時(shí)大家都遵守一條原則，就是遲來者必須排在隊(duì)的后面，先來者先服務(wù)。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第55頁。6.3數(shù)據(jù)結(jié)構(gòu)隊(duì)列和棧一樣，用來存放尚未處理而等待處理的數(shù)據(jù)。然而，數(shù)據(jù)項(xiàng)的處理順序與棧不同，隊(duì)列是依據(jù)“先進(jìn)先出”的原則，因此，隊(duì)列又可稱為“FIFO”表。隊(duì)列的物理實(shí)現(xiàn)，一般是采用順序存儲(chǔ)方法，要求系統(tǒng)分配一塊連續(xù)存儲(chǔ)空間，并用兩個(gè)變量作為指針，指向隊(duì)列的頭和尾。順序隊(duì)列基本運(yùn)算有以下兩種:1）在隊(duì)列中插入一個(gè)值為x的表目；2）在隊(duì)列中刪除一個(gè)表目。當(dāng)進(jìn)隊(duì)時(shí)，隊(duì)頭指針head不動(dòng)，只改變隊(duì)尾指針tail，進(jìn)隊(duì)前應(yīng)先判斷隊(duì)滿否，若隊(duì)滿，提示出錯(cuò)。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第56頁。6.3數(shù)據(jù)結(jié)構(gòu)當(dāng)出隊(duì)時(shí)，尾指針tail不動(dòng)，只改變隊(duì)頭指針head，出隊(duì)前應(yīng)先判斷隊(duì)滿否，若隊(duì)滿，提示出錯(cuò)。從圖6-6中還可以看到，隨著隊(duì)列操作的執(zhí)行，整個(gè)隊(duì)列會(huì)沿一個(gè)方向不斷移動(dòng)。最終結(jié)果是隊(duì)列前面有許多單元未被利用，由于不斷進(jìn)隊(duì)，隊(duì)尾可能已達(dá)到存儲(chǔ)區(qū)邊緣，而無法再往隊(duì)列中添加數(shù)據(jù)。為了充分利用存儲(chǔ)空間，可以把隊(duì)列構(gòu)成環(huán)狀結(jié)構(gòu)，使其頭尾相接。為了使隊(duì)列正常工作，還必須滿足隊(duì)列滿和空的條件。不失一般性，假設(shè)每個(gè)表目占一個(gè)單元，為隊(duì)列分配了M個(gè)單元的空間（從Q0到Q0+M-1），在隊(duì)列初始化時(shí)，置head=tail=0。下面討論隊(duì)空和隊(duì)滿條件。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第57頁。6.3數(shù)據(jù)結(jié)構(gòu)隊(duì)空實(shí)際意義是讀出（出隊(duì)）趕上寫入（進(jìn)隊(duì)），因此，隊(duì)空條件為:head=tail當(dāng)初始化時(shí)，顯然滿足隊(duì)空條件。隊(duì)滿實(shí)際意義是寫入（進(jìn)隊(duì)）趕上讀出（出隊(duì)）。當(dāng)趕上讀時(shí)，對(duì)循環(huán)隊(duì)列隊(duì)滿條件為:(head-tail+M)=1棧和隊(duì)列在端點(diǎn)運(yùn)算上都有很強(qiáng)的限制。棧只能作插入和刪除運(yùn)算，而隊(duì)列可以分別在兩端進(jìn)行插入和刪除。我們也可以使隊(duì)列的兩端都具有棧的特性。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第58頁。6.3數(shù)據(jù)結(jié)構(gòu)隊(duì)列在計(jì)算機(jī)操作系統(tǒng)和管理系統(tǒng)中有著廣泛的用途。例如，由于主機(jī)處理一個(gè)字符速度極快，而打印機(jī)打印一個(gè)字符相對(duì)于主機(jī)來講速度慢得多，解決這個(gè)問題要建立一個(gè)緩沖區(qū)，存放要求打印的數(shù)據(jù)，打印機(jī)從緩沖區(qū)中逐個(gè)取出字符打印，這樣的緩沖區(qū)實(shí)際上是一個(gè)“隊(duì)列”，按先進(jìn)先出原則取數(shù)。4．鏈表前面討論向量、棧和隊(duì)列都屬于順序表，占用的內(nèi)存單元較少，查找方便，但對(duì)它進(jìn)行插入、刪除、重新排列時(shí)要求大量地移動(dòng)數(shù)據(jù)，將耗費(fèi)主機(jī)時(shí)間，效率比較低。因此，只有靜態(tài)線性結(jié)構(gòu)適宜于采用順序表。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第59頁。6.3數(shù)據(jù)結(jié)構(gòu)以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的線性表稱為線性鏈表，可以克服以上不足，適用于進(jìn)行插入、刪除等操作，操作簡單、花費(fèi)時(shí)間少，并且不要求預(yù)先分配一塊連續(xù)存儲(chǔ)空間，所以鏈接結(jié)構(gòu)適用于動(dòng)態(tài)線性結(jié)構(gòu)。1）單鏈表這是動(dòng)態(tài)結(jié)構(gòu)中最簡單的一種基本類型，邏輯上仍是一組有序元素的集合，但物理上是無序的。因此，為了保持在線性表中的順序，除了存儲(chǔ)各元素的數(shù)據(jù)外，還必須保持一個(gè)指向下一個(gè)元素的指針。在單鏈表里分配給每個(gè)結(jié)點(diǎn)的存儲(chǔ)單元分為兩部分：一部分存放結(jié)點(diǎn)的數(shù)據(jù)，稱作值域；另一部分存放指向后繼節(jié)點(diǎn)的指針，稱為鏈域。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第60頁。6.3數(shù)據(jù)結(jié)構(gòu)終端節(jié)點(diǎn)沒有后繼，它的鏈域（link）為NULL（圖中用^表示空域，在計(jì)算機(jī)中可以表示成零和負(fù)數(shù)），另外還需要一個(gè)表頭指針head，保存第一個(gè)結(jié)點(diǎn)的地址。鏈表就是通過指針保證了邏輯上的有序性。單鏈表存儲(chǔ)結(jié)構(gòu)如圖6-7所示。在單鏈表中經(jīng)常要執(zhí)行的運(yùn)算，也就是在一般向量中要執(zhí)行的運(yùn)算，只是實(shí)現(xiàn)方法和順序存儲(chǔ)不同。在向量中訪問一個(gè)節(jié)點(diǎn)，只要根據(jù)給出的下標(biāo)變量值直接可以存取任一元素，在鏈表中，必須從head所指出的節(jié)點(diǎn)開始，沿著link域所組成的鏈一個(gè)一個(gè)節(jié)點(diǎn)往下查找，直到第i個(gè)節(jié)點(diǎn)為止，因此，查找Ki

節(jié)點(diǎn)所需要的時(shí)間代價(jià)與i的大小成正比。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第61頁。6.3數(shù)據(jù)結(jié)構(gòu)在單鏈表上可以定義以下運(yùn)算：（1）查找Ki節(jié)點(diǎn);（2）刪除Ki節(jié)點(diǎn);（3）在Ki節(jié)點(diǎn)后插入新節(jié)點(diǎn)；（4）打印Ki節(jié)點(diǎn)前驅(qū)點(diǎn)和后繼點(diǎn)；（5）重新排序單鏈表中的節(jié)點(diǎn)（按遞增或遞減）。在單鏈表中實(shí)現(xiàn)刪除操作是方便的，只需要改變Ki-1

節(jié)點(diǎn)的link域，使其指向Ki+1節(jié)點(diǎn)，如圖6-8所示。當(dāng)刪除第一個(gè)節(jié)點(diǎn)時(shí)，要修改頭指針head。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第62頁。6.3數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)插入操作只需要修改Ki

節(jié)點(diǎn)的鏈域，使其指向新節(jié)點(diǎn)，而新節(jié)點(diǎn)的鏈域指向Ki+1節(jié)點(diǎn)，如圖6-9所示。當(dāng)i=0作為第一節(jié)點(diǎn)插入時(shí)要修改頭指針head。按一定規(guī)則重新排列單鏈表中的節(jié)點(diǎn)，如要求值域數(shù)據(jù)遞增（或遞減）重排。在重排過程中，鏈域部可以不修改，只需要交換值域。2）循環(huán)鏈表對(duì)單鏈表稍作修改，把它最后一個(gè)節(jié)點(diǎn)的指針不為空域（^）而讓它指向第一個(gè)節(jié)點(diǎn)，這就得到了循環(huán)鏈表。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第63頁。6.3數(shù)據(jù)結(jié)構(gòu)圖6-10為單循環(huán)鏈表示意圖，使用圖6-10（a）結(jié)構(gòu)時(shí)，為了找到最后一個(gè)節(jié)點(diǎn)，則必須從表頭head出發(fā)訪問每一個(gè)節(jié)點(diǎn)，如果改用表尾tail指針，保存指向終端節(jié)點(diǎn)的地址，從Kn

的link域立即可以得到節(jié)點(diǎn)Ki，如圖6-10（b）所示。這樣，無論是查找第一個(gè)節(jié)點(diǎn)還是查找最后一個(gè)節(jié)點(diǎn)都很方便，所以在使用中多采用后一種方式。循環(huán)列表的優(yōu)點(diǎn)是：從循環(huán)表任一節(jié)點(diǎn)出發(fā)都能訪問到所有的節(jié)點(diǎn)。在循環(huán)鏈表中的插入和刪除運(yùn)算類似于單鏈表。3）雙向循環(huán)鏈表上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第64頁。6.3數(shù)據(jù)結(jié)構(gòu)上兩節(jié)討論的兩種鏈表，從任何一個(gè)節(jié)點(diǎn)的鏈域可以直接得到后繼節(jié)點(diǎn)，但不能直接找出它的前驅(qū)節(jié)點(diǎn)。如果在每一個(gè)節(jié)點(diǎn)中增加一個(gè)指向前驅(qū)節(jié)點(diǎn)的指針，就得到雙向循環(huán)鏈表。圖6-11為雙向循環(huán)鏈表的示意圖。在實(shí)際應(yīng)用中還可以根據(jù)運(yùn)算的要求設(shè)計(jì)各種不同的雙向循環(huán)鏈表。同單鏈表相比較，在雙鏈表中除了多占用存儲(chǔ)空間外，在進(jìn)行查找、插入和刪除運(yùn)算時(shí)都比較方便。4）鏈?zhǔn)綏：玩準(zhǔn)疥?duì)列當(dāng)存儲(chǔ)器只有許多不連續(xù)的小塊存儲(chǔ)空間可用時(shí)，可以動(dòng)態(tài)地分配給棧和隊(duì)列使用。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第65頁。6.3數(shù)據(jù)結(jié)構(gòu)用“鏈”連接構(gòu)成的棧和隊(duì)列叫做鏈?zhǔn)綏：玩準(zhǔn)疥?duì)列，或稱為離散棧和離散隊(duì)列。6.3.3樹和二叉樹樹形結(jié)構(gòu)是非線性數(shù)據(jù)結(jié)構(gòu)的重要形式，在計(jì)算機(jī)科學(xué)及軟件工程中有極其廣泛的應(yīng)有，它可以表示一些復(fù)雜的層次（分支）結(jié)構(gòu)。例如，在編譯程序中，可以用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)，可以用樹來組織信息等。1．樹的概念及術(shù)語樹（Tree）T是n（n>0）個(gè)點(diǎn)的有限集合，任何一個(gè)非空樹都滿足如下兩個(gè)條件：上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第66頁。6.3數(shù)據(jù)結(jié)構(gòu)（1）有且只有一個(gè)特定的稱為根的節(jié)點(diǎn)；（2）除根以外的其余節(jié)點(diǎn)被分成m（m>0）個(gè)不相交的有限集合，T1，T2，…，Tm，其中每一個(gè)集合又是一棵樹，并且是稱為根的子樹。由上述可知，樹的遞歸定義闡述了樹的固有屬性，即一棵樹由若干子樹構(gòu)成，而子樹又由若干更小的子樹構(gòu)成。如圖6-12所示。樹是由根節(jié)點(diǎn)、分支節(jié)點(diǎn)、葉節(jié)點(diǎn)和樹枝組成。（1）根節(jié)點(diǎn)：樹中最上面的節(jié)點(diǎn)叫“樹根節(jié)點(diǎn)”，簡稱“根”。（2）分支節(jié)點(diǎn)：至少有一棵子樹的節(jié)點(diǎn)，成為分支節(jié)點(diǎn)或非終端節(jié)點(diǎn)（即至少有一個(gè)后繼節(jié)點(diǎn)的節(jié)點(diǎn)）。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第67頁。6.3數(shù)據(jù)結(jié)構(gòu)（3）葉節(jié)點(diǎn)：沒有子樹的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)或終端節(jié)點(diǎn)（即沒有后繼節(jié)點(diǎn)的節(jié)點(diǎn)）。（4）樹枝：兩個(gè)節(jié)點(diǎn)之間的連線稱為樹枝，簡稱“枝”。（5）樹的層次：從根算起，跟節(jié)點(diǎn)的層次為1；沿樹可以從根節(jié)點(diǎn)直接到達(dá)的節(jié)點(diǎn)層次為2；從層次2直接到達(dá)的節(jié)點(diǎn)層次為3，其余類推。（6）樹的深度：在數(shù)中節(jié)點(diǎn)最大層次，成為這棵樹的深度。（7）度：一個(gè)節(jié)點(diǎn)的子樹的個(gè)數(shù)成為該節(jié)點(diǎn)的度。（8）樹的度：在樹的節(jié)點(diǎn)中最大的度稱為樹的度。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第68頁。6.3數(shù)據(jù)結(jié)構(gòu)樹形結(jié)構(gòu)中常使用家族樹的一些慣用詞。（1）節(jié)點(diǎn)的孩子：節(jié)點(diǎn)的子樹的根稱為該節(jié)點(diǎn)的孩子。（2）節(jié)點(diǎn)的雙親：孩子的根為雙親.（3）兄弟：同一個(gè)雙親孩子之間稱為兄弟。（4）祖父：孩子雙親的雙親稱為祖父。（5）祖先（長輩）：一個(gè)節(jié)點(diǎn)的祖先是指從根到該節(jié)點(diǎn)的路徑上所有的節(jié)點(diǎn)。（6）堂兄弟：雙親在同一層的孩子之間為堂兄弟。2．樹的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第69頁。6.3數(shù)據(jù)結(jié)構(gòu)樹邏輯結(jié)構(gòu)除圖6-12表示方法以外，還可以用圓括號(hào)表示為廣義表：（A（B（D，E），C（F，G（J），H）））其表示方法歸納如下：首先將根點(diǎn)放入表中，把它的子樹用圓括號(hào)括起來，按從左到右的次序依次放入表中，且以逗號(hào)分開，對(duì)子樹也采用同樣方法處理。該表顯示了樹的層次。樹的物理結(jié)構(gòu)一般由多重鏈表、雙重鏈表、三重鏈表3種形式實(shí)現(xiàn)。3．樹結(jié)構(gòu)的應(yīng)用上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第70頁。6.3數(shù)據(jù)結(jié)構(gòu)樹結(jié)構(gòu)有著廣泛的應(yīng)用，下面列舉它的幾個(gè)方面的應(yīng)用。（1）常用樹結(jié)構(gòu)來定義層次關(guān)系。（2）有序樹可以指明節(jié)點(diǎn)的子樹間的某種順序關(guān)系。（3）判定樹。樹的另一種非常有價(jià)值的應(yīng)用是進(jìn)行判斷。4．樹的操作在使用樹結(jié)構(gòu)時(shí)經(jīng)常進(jìn)行如下的操作：（1）查找樹中具有某種性質(zhì)的節(jié)點(diǎn)。（2）按某種次序搜索樹中全部節(jié)點(diǎn)。（3）找出樹中某個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。（4）找出樹中某個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第71頁。6.3數(shù)據(jù)結(jié)構(gòu)（5）從已知樹中除去某一棵子樹。（6）用某棵樹去替換指定的葉。5．二叉樹1）二叉樹的概念二叉樹是度為2的有序樹。在樹結(jié)構(gòu)的應(yīng)用中，二叉樹起著特別重要的作用。一般樹很容易的轉(zhuǎn)換化成二叉樹的表示。定義：二叉樹由節(jié)點(diǎn)有限集合構(gòu)成，這個(gè)有限集合或者為空集，或者由一個(gè)根節(jié)點(diǎn)及兩個(gè)不相交的分別稱為左子樹或右子樹的二叉樹（它們也是節(jié)點(diǎn)的集合）組成。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第72頁。6.3數(shù)據(jù)結(jié)構(gòu)這是個(gè)遞歸的定義。二叉樹可以是空集合，根可以是有空的左子樹或右子樹，或者左右子樹皆為空。圖6-17表示二叉樹5種基本形式。二叉樹不是樹的特殊情形，樹和二叉樹之間的區(qū)別是：（1）樹至少要有一個(gè)節(jié)點(diǎn)，樹中每個(gè)節(jié)點(diǎn)可以有0、1、2、…，棵子樹；（2）二叉樹可以是空集，二叉樹的節(jié)點(diǎn)的子樹最多只有兩棵（即度<=2），并區(qū)分為左子樹和右子樹，圖6-17中（c）和（d）為兩棵不同的二叉樹，但如果是樹，它們就是相同的樹。二叉樹的概念非常重要。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第73頁。6.3數(shù)據(jù)結(jié)構(gòu)首先，從許多實(shí)際問題中抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹形式，而且許多算法問題用二叉樹形式來解決非常簡單方便。2）二叉樹的性質(zhì)性質(zhì)1:在二叉樹中，第i層的節(jié)點(diǎn)數(shù)最多為2i-1

（i>=1），其深度為k的二叉樹的節(jié)點(diǎn)總數(shù)最多為2k-1個(gè)（k>=1）。性質(zhì)2:對(duì)任一棵二叉樹，如果葉節(jié)點(diǎn)數(shù)為n0，而其度為2的節(jié)點(diǎn)數(shù)為n2，則n0=n2+1k=log2(n)+1上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第74頁。6.3數(shù)據(jù)結(jié)構(gòu)性質(zhì)4:如果有n個(gè)節(jié)點(diǎn)的順序二叉樹（其深度k=[log2(n)]+1），則對(duì)任意節(jié)點(diǎn)i，1≤i≤n，有:（1）若i≠1，則i的雙親是[i/2]；若i=1，則i是根，無雙親。（2）若2i≤n，則i的左孩子是2i；若2i>n，則i無右孩子。（3）若2i+1≤n，則i的右孩子是2i+1；若2i+1>n，則i無右孩子。對(duì)于滿二叉樹或順序二叉樹，可用向量表示。一般情況下，采用鏈接存儲(chǔ)方法。3）周游二叉樹上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第75頁。6.3數(shù)據(jù)結(jié)構(gòu)周游二叉樹也稱為遍歷二叉樹，就是按某種規(guī)則對(duì)二叉樹中的每個(gè)節(jié)點(diǎn)訪問一次。在訪問每個(gè)節(jié)點(diǎn)時(shí)，可以打印節(jié)點(diǎn)的有關(guān)信息，也可以對(duì)節(jié)點(diǎn)進(jìn)行其他一些操作。對(duì)線性結(jié)構(gòu)這是一件容易解決的問題，但二叉樹是非線性結(jié)構(gòu)，這就需要找到一個(gè)完整而有規(guī)則的周游方法，以便得到二叉樹中各節(jié)點(diǎn)信息的一個(gè)線性排序。考慮到二叉樹的基本組成部分是（N，L，R），如圖6-18所示。如果限定先左后右的次序，則有以下3種主要形式（均為遞歸定義）：（1）前序周游（NLR）：先訪問根，然后按前序周游左子樹，再按前序周游右子樹。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第76頁。6.3數(shù)據(jù)結(jié)構(gòu)（2）中序周游（LNR）：按中序周游左子樹，再處理根，最后按中序周游右子樹。（3）后序周游（LRN）：按后序周游左子樹，再按后序周游右子樹，最后處理根（以圖6-19為例）。棧是實(shí)現(xiàn)遞歸的最常用的結(jié)構(gòu)，所以對(duì)于遞歸定義的二叉樹周游運(yùn)算，最自然的實(shí)現(xiàn)方式是利用一個(gè)棧來記下尚待周游的節(jié)點(diǎn)或子樹，以備以后訪問。下面簡單討論3種周游的算法。（1）前序周游算法：從已知二叉樹的根節(jié)點(diǎn)開始訪問，處理完根節(jié)點(diǎn)后，只要有左子樹就應(yīng)該繼續(xù)向左訪問，但同時(shí)應(yīng)把該節(jié)點(diǎn)的右子樹（如果存在的話）的指向進(jìn)棧保存，以便左子樹訪問完后進(jìn)一步按前序訪問右子樹。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第77頁。6.3數(shù)據(jù)結(jié)構(gòu)（2）中序周游算法：在中序周游時(shí)首先查看該節(jié)點(diǎn)是否有左子樹，如果有的話，則應(yīng)向左繼續(xù)搜索下去，直到左子樹葉節(jié)點(diǎn)為止。待中序處理完該節(jié)點(diǎn)的左子樹后，于訪問該節(jié)點(diǎn)，然后，轉(zhuǎn)向右子樹進(jìn)行搜索，并以同樣方法處理右子樹的每個(gè)節(jié)點(diǎn)。這樣，在每次找到一個(gè)節(jié)點(diǎn)后，應(yīng)該先把該節(jié)點(diǎn)進(jìn)棧保存，待處理完該節(jié)點(diǎn)的左子樹返回時(shí)再訪問該節(jié)點(diǎn)。（3）后序周游算法：在后序周游時(shí)，先查看該節(jié)點(diǎn)的左子樹（如果存在的話），在按后序訪問該節(jié)點(diǎn)的左子樹時(shí)，該節(jié)點(diǎn)應(yīng)該進(jìn)棧保存，以便返回時(shí)再進(jìn)一步按后序訪問它的右子樹。由于后序周游最后一步是訪問該節(jié)點(diǎn)，所以在轉(zhuǎn)向按后序訪問它的右子樹時(shí)，該節(jié)點(diǎn)仍應(yīng)該進(jìn)棧保存。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第78頁。6.3數(shù)據(jù)結(jié)構(gòu)這樣，在后序周游二叉樹時(shí)，樹中每個(gè)節(jié)點(diǎn)必須進(jìn)棧兩次，并且只有在訪問完該節(jié)點(diǎn)的右子樹后（左子樹已訪問過）才能訪問該節(jié)點(diǎn)。為了區(qū)別當(dāng)前正在訪問該節(jié)點(diǎn)的是左子樹還是右子樹這兩種情況，在兩次進(jìn)站時(shí)對(duì)該節(jié)點(diǎn)加以不同標(biāo)志，以表示當(dāng)前正在處理它的是左子樹還是右子樹。二叉樹上的前序、中序、后序周游有很大的用途。如果我們把算術(shù)表達(dá)式構(gòu)成二叉樹的形式，那么對(duì)二叉樹的前序、后序周游，它的輸出結(jié)果就是相應(yīng)的簡單算術(shù)表達(dá)式的前綴和后綴表達(dá)式的形式。6.3.4圖1．圖的定義及基本術(shù)語上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第79頁。6.3數(shù)據(jù)結(jié)構(gòu)圖的定義：一個(gè)圖G由兩個(gè)集合V和E組成，V是有限的非空頂點(diǎn)集，E是有限邊集，分別用V（G）和E（G）表示頂點(diǎn)集和邊集，G=（V，E）表示圖。在圖中的節(jié)點(diǎn)可以稱為圖的頂點(diǎn)。圖的邏輯結(jié)構(gòu)可以這樣描述：設(shè)數(shù)據(jù)結(jié)構(gòu)B=（K，R），K為節(jié)點(diǎn)的有限集合，R為K上的一個(gè)任意關(guān)系。如果對(duì)于K中節(jié)點(diǎn)相對(duì)于關(guān)系R的前驅(qū)、后繼節(jié)點(diǎn)個(gè)數(shù)不加限制，則B成為圖結(jié)構(gòu)。圖中的有關(guān)術(shù)語：（1）邊：在圖G中，若有（K，K‘）∈E（G），則稱K與K’之間存在一條邊。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第80頁。6.3數(shù)據(jù)結(jié)構(gòu)若（K，K‘）是有序偶，則稱K與K'之間有一條有向邊，用﹤K，K'﹥表示，邊的起點(diǎn)為K，終點(diǎn)為K'。（2）有向圖：在圖G中，對(duì)每一個(gè)二元組（K，K‘）∈E（G）都是有序偶，則稱具有這種關(guān)系的圖G為有向圖。（3）無向圖：在圖G中，對(duì)每一個(gè)二元組（K，K‘）∈E（G）都是無序偶，則稱具有這種關(guān)系的圖G為無向圖。（4）節(jié)點(diǎn)的度：就是與該節(jié)點(diǎn)有關(guān)聯(lián)的邊的數(shù)目。（5）圖的度：指圖中各節(jié)點(diǎn)度數(shù)的最大值。圖G3是一個(gè)度為3的圖。（6）葉：指的是圖中的終端節(jié)點(diǎn)（即沒有后繼節(jié)點(diǎn)）。在有向圖中終端節(jié)點(diǎn)的出度為0。圖G3中V3位葉節(jié)點(diǎn)。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第81頁。6.3數(shù)據(jù)結(jié)構(gòu)（7）子圖：圖G=(V,E)，G'=(V',E')中，若V'V，E'E，并且E'中的邊所關(guān)聯(lián)的節(jié)點(diǎn)都在V'中，則稱G'是圖G的子圖。（8）路徑：在圖G=(V,E)中，如果存在節(jié)點(diǎn)序列Vp,Vi1,Vi2,…,Vin,Vg,使得<Vp，Vi1>，<Vi1，Vi2>，…，<Vin，Vg>都在E中（若對(duì)有向圖，則使得<Vp，Vi1>，<Vi1，Vi2>，……,<Vin，Vg>都在E中），則稱從節(jié)點(diǎn)Vp到節(jié)點(diǎn)Vg存在一條路徑。路徑長度定義為這條路徑上的邊數(shù)。（9）簡單路徑：如果在一條路徑上的節(jié)點(diǎn)除Vp和Vg可以相同外，其他節(jié)點(diǎn)都不相同，則稱此路徑為簡單路徑。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第82頁。6.3數(shù)據(jù)結(jié)構(gòu)（10）圈（環(huán)）：若路徑上第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)相同，即Vp=Vg，則稱此簡單路徑為圈（也稱為環(huán)或回路）。（11）有根圖：在圖中至少有一個(gè)節(jié)點(diǎn)V，從V出發(fā)可以到達(dá)圖中任何一個(gè)節(jié)點(diǎn)，即V到每個(gè)節(jié)點(diǎn)都有路徑，則稱圖為有根圖，V是圖的根。圖6-23為有根圖。根為V1。（12）連通圖：對(duì)無向圖G=(V,E)而言，如果V1到V2有一條路徑（從V2到V1也一定有一條路徑），我們稱V1和V2是連通的。若圖G中任意兩個(gè)節(jié)點(diǎn)Vi和Vj（Vi≠Vj）都是連通的，則稱無向圖G是連通圖。圖6-21中G1和G2是連通圖。（13）連通分量：無向圖G中的連通分量是G中的極大連通子圖。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第83頁。6.3數(shù)據(jù)結(jié)構(gòu)圖6-24所示的G1的兩個(gè)子圖H1和H2組成的圖G4是不連通的，而H1和H2是連通的，稱它們?yōu)镚4的連通分量，即為圖G4的極大連通子圖。（14）強(qiáng)連通子圖：對(duì)有向圖G=（V，E）而言，若對(duì)于G中任意兩個(gè)節(jié)點(diǎn)Vi和Vj（Vi≠Vj），都有一條從Vi到Vj的有向路徑，同時(shí)還有一條從Vj到Vi的有向路徑，則稱有向圖G是強(qiáng)連通圖。圖6-21中G3不是強(qiáng)連通圖，因?yàn)閺腣3到V2不存在路徑。若圖6-23中加上V4到V1的有向路徑，則此有根圖為強(qiáng)連通圖。（15）強(qiáng)連通分量：有向圖中極大的強(qiáng)連通子圖稱為強(qiáng)連通分量。G3的強(qiáng)連通分量如圖6-25所示。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第84頁。6.3數(shù)據(jù)結(jié)構(gòu)（16）加權(quán)圖：給圖中每條邊加上帶數(shù)字的權(quán)，稱為加權(quán)圖。帶權(quán)的連通圖又稱為“網(wǎng)絡(luò)”。如圖6-26所示。圖是一種非常有用的數(shù)據(jù)結(jié)構(gòu)。因?yàn)閳D的結(jié)構(gòu)復(fù)雜而使用廣泛，所以其存儲(chǔ)表示方法也是多種多樣的，對(duì)應(yīng)于不同的應(yīng)用問題有不同的表示方法，常用的有相鄰矩陣、鄰接表和鄰接多重表等。2．圖的周游和生成樹周游圖的定義：對(duì)一個(gè)圖G，從圖中任意一個(gè)節(jié)點(diǎn)V0出發(fā)，系統(tǒng)地訪問G中所有的節(jié)點(diǎn)，且只訪問一次，稱為圖的周游。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第85頁。6.3數(shù)據(jù)結(jié)構(gòu)圖的周游比樹的周游復(fù)雜，因?yàn)閳D中任意一個(gè)節(jié)點(diǎn)可以和其余任何節(jié)點(diǎn)相鄰接，故在訪問了某個(gè)節(jié)點(diǎn)后，可能順著某條路徑又一次訪問該節(jié)點(diǎn)，為了避免多次訪問，故增加了一個(gè)標(biāo)志mark，當(dāng)mark=i時(shí)，表示第i個(gè)節(jié)點(diǎn)已訪問過。常用的圖的周游方法有：（1）縱向優(yōu)先搜索法（即按深度方向周游）：從起點(diǎn)V0開始，訪問節(jié)點(diǎn)V0，然后選取與V0鄰接的未被訪問的任一頂點(diǎn)V1，訪問V1后，再從V1出發(fā)，按深度方向周游，再選取與V1鄰接的未被訪問的任一個(gè)節(jié)點(diǎn)，重復(fù)上述過程，當(dāng)遇到一個(gè)所有鄰接節(jié)點(diǎn)都訪問過的節(jié)點(diǎn)時(shí)，上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第86頁。6.3數(shù)據(jù)結(jié)構(gòu)回到已訪問節(jié)點(diǎn)序列中最后一個(gè)還有未被訪問的相鄰節(jié)點(diǎn)的節(jié)點(diǎn)w，再從w出發(fā)按深度方向周游，最后，當(dāng)任何已被訪問過的節(jié)點(diǎn)都不存在未被訪問的相鄰節(jié)點(diǎn)時(shí)，周游結(jié)束。（2）橫向優(yōu)先搜索法（即按寬度方向周游）：從圖中某個(gè)節(jié)點(diǎn)V0出發(fā)，訪問節(jié)點(diǎn)V0，然后訪問與該節(jié)點(diǎn)相鄰的全部節(jié)點(diǎn)V1,V2,…,Vt，然后再依次訪問與V1,V2,…,Vt相鄰接的所有未被訪問過的節(jié)點(diǎn)，如此進(jìn)行下去，直到訪問完所有的節(jié)點(diǎn)為止。上一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第87頁。6.4數(shù)組6.4.1數(shù)組概念數(shù)組是一組相同類型的變量的集合，它不是一種數(shù)據(jù)類型。在VB中有兩種類型的數(shù)組，即變量數(shù)組和控件數(shù)組。變量數(shù)組又分為靜態(tài)（定長）數(shù)組和動(dòng)態(tài)（不定長）數(shù)組。6.4.2數(shù)組的聲明數(shù)組要先聲明后使用，聲明就是定義數(shù)組的名字、維數(shù)和類型。1）靜態(tài)數(shù)組格式：Dim<數(shù)組名>（<維數(shù)>）[As<類型>]功能：定義一個(gè)數(shù)組，并為其分配存儲(chǔ)空間。下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第88頁。6.4數(shù)組說明：（1）數(shù)組名的命名規(guī)則與簡單變量相同。（2）<維數(shù)>定義數(shù)組的大小。其形式為：[<下標(biāo)下界1>To]<下標(biāo)上界>,[<下標(biāo)下界2>To<下標(biāo)上界2>]，…下標(biāo)的范圍為-2147483648~2147483647，默認(rèn)的下標(biāo)下界為0，也可由OptionBase1指定為1。只有一個(gè)下標(biāo)的數(shù)組為一維數(shù)組，有兩個(gè)及兩個(gè)以上下標(biāo)的數(shù)組為多維數(shù)組。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第89頁。6.4數(shù)組（3）如指定數(shù)據(jù)類型，則數(shù)組元素都具有相同的數(shù)據(jù)類型；如不指定數(shù)組類型，則默認(rèn)為變體類型，這是數(shù)組中的元素可以有不同的數(shù)據(jù)類型。2）動(dòng)態(tài)數(shù)組動(dòng)態(tài)數(shù)組在聲明時(shí)未給出維數(shù)，在使用數(shù)組時(shí)根據(jù)實(shí)際情況再?zèng)Q定數(shù)組大小，這樣可以節(jié)省內(nèi)存。建立動(dòng)態(tài)數(shù)組的方法為：（1）在聲明數(shù)組時(shí)不給出具體維數(shù)，如：Dima（）AsInteger。（2）在過程中用Redim語句確定數(shù)組的大小，如Redima（1To20）。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第90頁。6.4數(shù)組6.4.3數(shù)組賦值在用Dim語句給出數(shù)組聲明之后，數(shù)值型數(shù)組的元素都初始化0，字符型數(shù)組的元素都初始化為空。我們在使用數(shù)組時(shí)都要給它賦予一定的初值，給數(shù)組賦初值常用以下方法：1）用循環(huán)語句給數(shù)組賦值2）用Array函數(shù)給數(shù)組賦值數(shù)組變量名=Array（arglist）對(duì)數(shù)組元素的使用需給出變量名和下標(biāo)3）通過文本控件或InputBox（）函數(shù)賦值4）數(shù)組間賦值上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第91頁。6.4數(shù)組VB6.0提供了可對(duì)數(shù)組整體賦值的新功能,方便了數(shù)組對(duì)數(shù)組的賦值操作。但真正使用不那么方便,有不少限制。數(shù)組賦值形式如下:數(shù)組名2=數(shù)組名16.4.4數(shù)組的算法數(shù)組是程序設(shè)計(jì)中使用最多的數(shù)據(jù)結(jié)構(gòu)。將數(shù)組元素的下標(biāo)和循環(huán)語句結(jié)合使用，能解決大量的實(shí)際問題。關(guān)鍵是要掌握數(shù)組下標(biāo)與循環(huán)變量之間的關(guān)系。需要注意的是，數(shù)組定義時(shí)用數(shù)組名表示該數(shù)組的整體，但在具體操作時(shí)是針對(duì)每個(gè)數(shù)組元素進(jìn)行的。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第92頁。6.4數(shù)組1．?dāng)?shù)組排序排序是將一組數(shù)按遞增或遞減的次序排列。排序的算法很多（詳見6.5節(jié)），此處著重介紹數(shù)組操作時(shí)，數(shù)組下標(biāo)如何與循環(huán)變量進(jìn)行有機(jī)的聯(lián)系。2．分類統(tǒng)計(jì)分類統(tǒng)計(jì)是經(jīng)常遇到的運(yùn)算，是將一批數(shù)據(jù)中按分類的條件統(tǒng)計(jì)每一類中包含的個(gè)數(shù)。3．大量數(shù)據(jù)的輸入和編輯6.4.5控件數(shù)組1．控件數(shù)組的概念上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第93頁。6.4數(shù)組控件數(shù)組就是具有相同名稱和類型的一組控件。每個(gè)控件都有唯一的一個(gè)索引號(hào)（Index），以此來區(qū)分不同的控件。使用控件數(shù)組添加控件所消耗的資源比直接向窗體添加多個(gè)相同類型的控件所消耗的資源要少，控件數(shù)組可以共享同樣的事件過程。在系統(tǒng)運(yùn)行中，可以利用系統(tǒng)返回的索引值來識(shí)別事件是由哪個(gè)控件引發(fā)的。另外，若要在運(yùn)行時(shí)創(chuàng)建新控件，則新控件必須是控件數(shù)組的成員，沒有控件數(shù)組機(jī)制是不可能在運(yùn)行時(shí)創(chuàng)建新控件的。使用控件數(shù)組時(shí)，每個(gè)新成員都繼承數(shù)組的公共事件過程。2．控件數(shù)組的建立上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第94頁。6.4數(shù)組可以使用下列方法之一來創(chuàng)建控件數(shù)組：（1）給控件起相同的名字。（2）復(fù)制現(xiàn)有的控件。（3）將控件Index的屬性設(shè)置為非Null數(shù)值。下面介紹用第一種方法建立控件數(shù)組：（1）畫出控件數(shù)組中要添加的控件，并確定哪一個(gè)控件是數(shù)組中的第一個(gè)控件。（2）將選定控件的Name屬性設(shè)置為數(shù)組名。（3）在為數(shù)組中的其他控件輸入相同名稱時(shí)，VB將顯示一個(gè)對(duì)話框，問是否要?jiǎng)?chuàng)建控件數(shù)組，此時(shí)要選擇“是”上一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第95頁。6.5排序6.5.1排序概述排序是指將一組任意排列的關(guān)鍵字按照指定的次序重新排列的過程。排序的目的是為了更快速和更方便的查找到指定的關(guān)鍵字。排序操作是計(jì)算機(jī)系統(tǒng)的基本操作。一般根據(jù)排序操作執(zhí)行的地方不同分為兩類：（1）內(nèi)部排序：在計(jì)算機(jī)內(nèi)存中進(jìn)行，不需要訪問外存就可完成的排序。（2）外部排序：參加排序的記錄量很大，需要在計(jì)算機(jī)外存中進(jìn)行的排序。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第96頁。6.5排序內(nèi)部排序方法如圖6-33所示：一般來說，在排序過程中有兩種基本操作：一是比較兩個(gè)關(guān)鍵字的大?。欢且苿?dòng)記錄位置。前一種操作對(duì)大多數(shù)排序方法都是必要的，而后者可通過改變記錄的存儲(chǔ)方式來避免。待排序記錄通常有3種存儲(chǔ)結(jié)構(gòu)：（1）以數(shù)組為存儲(chǔ)結(jié)構(gòu)的順序存儲(chǔ)方法，排序過程通過記錄的多次比較和移動(dòng)來實(shí)現(xiàn)；（2）以鏈表為存儲(chǔ)結(jié)構(gòu)的鏈?zhǔn)酱鎯?chǔ)方法，排序過程無需移動(dòng)記錄，只需比較關(guān)鍵字和修改指針即可，一般把這類排序稱為表排序；上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第97頁。6.5排序（3）一些排序方法不宜在鏈表上實(shí)現(xiàn)，若仍需避免移動(dòng)記錄，則可建立一個(gè)輔助表來登記建立的關(guān)鍵字和存儲(chǔ)地址等信息，排序過程只針對(duì)輔助表進(jìn)行，不需移動(dòng)記錄本身。衡量評(píng)價(jià)不同排序方法的優(yōu)劣有兩點(diǎn)：一是在數(shù)據(jù)規(guī)模一定的條件下，算法執(zhí)行所耗時(shí)間，一般高效算法應(yīng)盡可能少的比較次數(shù)和數(shù)據(jù)元素移動(dòng)次數(shù)；二是執(zhí)行算法所需要的輔助存儲(chǔ)空間。理想的空間效率是算法執(zhí)行期間所需要的輔助空間與待排序的數(shù)據(jù)量無關(guān)。6.5.2排序方法1．冒泡排序上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第98頁。6.5排序冒泡排序時(shí)一種簡單的排序方法。它的基本思想是通過比較相鄰兩個(gè)元素來決定是否需要進(jìn)行交換，通過交換把關(guān)鍵字較小的元素由底部向頂部移動(dòng)（如同氣泡在水中的運(yùn)動(dòng)），這樣關(guān)鍵字較大的元素由頂部向底部移動(dòng)。具體來講，冒泡就是從R數(shù)組（n個(gè)元素）的下標(biāo)值較大的存儲(chǔ)位置移到下標(biāo)值較小的存儲(chǔ)位置。冒泡排序的關(guān)鍵操作：（1）冒泡趟數(shù)：首先將第一個(gè)元素與第二個(gè)元素進(jìn)行比較，若為逆序，則要交換，然后比較第二個(gè)與第三個(gè)元素。依此類推，直到第n-1個(gè)和第n個(gè)記錄為止。經(jīng)過此趟處理，目前最大元素被移動(dòng)到數(shù)組最后一個(gè)位置上。然后對(duì)前n-1個(gè)元素進(jìn)行類似的處理，直至對(duì)前2個(gè)元素處理為止。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第99頁。算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第100頁。6.5排序總共進(jìn)行了n-1遍處理，所以外循環(huán)變量i從1開始到n變化。（2）每一趟冒泡操作都會(huì)減少一個(gè)比較元素，這體現(xiàn)在內(nèi)循環(huán)變量j會(huì)根據(jù)外循環(huán)變量i的值決定循環(huán)比較次數(shù)。（3）如果相鄰元素是否交換取決于比較符，若相等也要交換，則排序是不穩(wěn)定。冒泡排序方法算法：上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第101頁。6.5排序2．選擇順序（直接選擇排序）選擇順序也是一種簡單排序方法。它的基本思想是在每一遍處理中選擇出關(guān)鍵字最小的元素，與其最后對(duì)應(yīng)位置的元素交換。直接選擇排序的基本過程是：從所有n個(gè)元素中選擇出關(guān)鍵字最小的元素，作為有序序列的第一個(gè)元素，與第一個(gè)元素交換，這是第一遍處理。接著再從n-1個(gè)記錄中選擇出最小的元素與第2個(gè)元素交換，以此類推。經(jīng)過n-1遍處理之后，次大元素在n-1號(hào)位置，最大元素在n號(hào)位置，排序過程結(jié)束。直接選擇排序的關(guān)鍵步驟：（1）選擇最小值的開始位置i，從1開始到n，每趟減少一個(gè)數(shù)據(jù)。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第102頁。6.5排序（2）確定每趟查找的范圍，從j到n。（3）在每趟選擇過程，只要發(fā)現(xiàn)有比當(dāng)前最小元素min小的元素，立即保留該元素位置。（4）每趟完成之后，min始終保持當(dāng)前元素中最小的位置。直接選擇排序算法：上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第103頁。6.5排序3．直接插入排序直接插入排序的思想：一次將要排序的每個(gè)元素按照其關(guān)鍵字的大小插入到已經(jīng)排好的有序序列中。其處理過程為：把序列中第一個(gè)元素看作是已經(jīng)排好序的有序序列，然后將第二個(gè)元素插入到有序序列中。以此類推，將第i個(gè)元素插入到由前i-1元素所組成的有序序列中，直到最后一個(gè)元素。經(jīng)過n-1次的插入操作之后，原來無序的元素變成了新的有序序列。直接插入排序算法：上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第104頁。6.5排序4．縮小增量排序（希爾排序）縮小增量排序又稱為希爾排序，它是在直接排序基礎(chǔ)之上做的改進(jìn)。上一頁下一頁返回算法與數(shù)據(jù)結(jié)構(gòu)全文共141頁，當(dāng)前為第105頁。6.5排序基本思想是：把元素按照一定的增量進(jìn)行分組，對(duì)于每一組進(jìn)行插入排序；增量會(huì)逐漸減少，直到為1；增量和分組中所包含的元素個(gè)數(shù)成反比，隨著分組中元素個(gè)數(shù)不斷增加，直到包括所有元素，完成排序操作?？s小增量排序的關(guān)鍵步驟：（1）建立一個(gè)跳躍性的直接出入方法intervel，它操作的結(jié)果是相隔intervel之間的元素之間使用直接排序方法已經(jīng)排好序。（2）設(shè)置一個(gè)存儲(chǔ)間隔的數(shù)組，其中的元素個(gè)數(shù)和值要根據(jù)排序數(shù)據(jù)的多少來定，最后一個(gè)元素一定是1，例如設(shè)置為5，2，1。（3）按照間隔數(shù)組的元素個(gè)數(shù)，決定分組排序的個(gè)數(shù)。上一頁下一頁