第五章-數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

第五章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)5.1引言數(shù)據(jù)是對客觀事物的符號表示，在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱，是程序加工的原始材料。它可以是數(shù)字、字符串或兩者兼而有之；可以是從磁帶或磁盤上讀出的一串二進(jìn)制數(shù)；也可以是模數(shù)轉(zhuǎn)換器的輸出(即采樣了大電子信號)；也可以是鍵盤操作的輸出等。

任何程序都要處理數(shù)據(jù)，把數(shù)據(jù)從最初的格式轉(zhuǎn)換成結(jié)果所需的格式。例如記賬程序，將業(yè)務(wù)往來的數(shù)據(jù)轉(zhuǎn)換成收入和支出的報表?？梢姡绦蚴菍⒃假Y料轉(zhuǎn)換成最終格式的一種或一組工具。數(shù)據(jù)的組織和處理過程是影響程序開發(fā)的最重要因素，也是主要控制程序設(shè)計的原始材料。簡潔而高效的程序設(shè)計，自然依賴于數(shù)據(jù)的組織形式，這便是數(shù)據(jù)結(jié)構(gòu)產(chǎn)生的背景。5.1.1什么是數(shù)據(jù)結(jié)構(gòu)所謂數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)之間的相互關(guān)系；它包括三方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。例如，一個線性表，它的邏輯結(jié)構(gòu)是指表中每個元素前后之間的邏輯關(guān)系；它的存儲結(jié)構(gòu)是指表中元素在存儲器中的存儲方式(是順序存儲還是鏈?zhǔn)酱鎯?；對它的運(yùn)算包括插入、刪除、檢索、更新、排序等等。學(xué)號姓名性別出生時間入學(xué)時間籍貫院系班級10011002……張三豐貂蟬……男女………………遼寧山西……計算機(jī)系計算機(jī)系……計061計061……5.1.1什么是數(shù)據(jù)結(jié)構(gòu)表中每個學(xué)生各占一行，每行的信息說明一個學(xué)生的情況，是學(xué)生檔案表的基本單位，我們把整個學(xué)生檔案為一個數(shù)據(jù)結(jié)構(gòu)。表中的每一行稱為一個結(jié)點(diǎn)(也稱為元素、記錄表目等，是數(shù)據(jù)結(jié)構(gòu)中的基本單位)。每一行由一系列數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)又稱字段，能唯一確定一個結(jié)點(diǎn)的字段稱為關(guān)鍵碼。上例中學(xué)號字段就是關(guān)鍵碼，它能唯一確定一個學(xué)生的情況。數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)緊密相關(guān)的一個概念，它是一個值的集合和定義在這個值集上的一組操作的總稱。按照“值”的不同特性，高級程序語言中的數(shù)據(jù)類型可以分為兩類：一類是非結(jié)構(gòu)的原子類型。原子類型是不可分解的。另一類是結(jié)構(gòu)類型，即由原子類型構(gòu)造而成的。抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型與數(shù)據(jù)類型實(shí)質(zhì)上是一個概念，對于用戶來講它們都是用來定義計算機(jī)中具有一定特性的數(shù)據(jù)的，“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。5.1.1什么是數(shù)據(jù)結(jié)構(gòu)上述學(xué)生檔案表就是一個線性表，表中結(jié)點(diǎn)與結(jié)點(diǎn)之間是簡單的線性關(guān)系，每一個數(shù)據(jù)元素都有自己相應(yīng)的數(shù)據(jù)類型。表中第一個結(jié)點(diǎn)稱為表頭，最后一個結(jié)點(diǎn)稱表尾，其他結(jié)點(diǎn)有一個前趨和一個后繼，這就是人事檔案表的邏輯結(jié)構(gòu)。如果結(jié)點(diǎn)和結(jié)點(diǎn)之間采用順序方式存放在計算機(jī)系統(tǒng)中，這就是存儲結(jié)構(gòu)。表中的結(jié)點(diǎn)隨學(xué)生情況的變更，要執(zhí)行增加、刪除、更新等操作，這就是數(shù)據(jù)的運(yùn)算問題。5.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)對數(shù)據(jù)之間關(guān)系的描述是數(shù)據(jù)的邏輯結(jié)構(gòu)，可以用一個二元組來表示：B=(K,R)式中，K是結(jié)點(diǎn)的有窮集合，R是K上的關(guān)系的有窮集合。有時也將數(shù)據(jù)的邏輯結(jié)構(gòu)稱為數(shù)據(jù)結(jié)構(gòu)。每個結(jié)點(diǎn)k(k∈K)的值(即數(shù)據(jù))可以由幾個字段組成。每個字段可以有一個或多個初等項(xiàng)和組合組成。結(jié)點(diǎn)可以分為初等類型和組合類型。只包含一個初等項(xiàng)的結(jié)點(diǎn)屬于初等類型，否則屬于組合類型。5.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)只包含一個初等項(xiàng)的結(jié)點(diǎn)屬于初等類型，否則屬于組合類型。所謂初等類型就是計算機(jī)能直接存儲并能直接用機(jī)器指令對它們進(jìn)行處理的數(shù)據(jù)類型。整型、實(shí)型、字符型等就是初等類型。組合類型是由初到類型用某種方式結(jié)合而成的數(shù)據(jù)類型，記錄(或結(jié)構(gòu))類型等就是組合類型。指針是一種特殊的類型，它的值一般來說對應(yīng)于存儲器中的一個地址或相對地址。學(xué)生檔案表中的結(jié)點(diǎn)就是屬于組合類型。根據(jù)數(shù)據(jù)元素之間的關(guān)系的不同特性，數(shù)據(jù)結(jié)構(gòu)通常分為四種基本結(jié)構(gòu)：1.

集合結(jié)構(gòu)中的元素僅僅只是同屬于一個集合，不存在其他關(guān)系2.

線性結(jié)構(gòu)結(jié)構(gòu)中的元素之間是一對一的關(guān)系。3.

樹型結(jié)構(gòu)結(jié)構(gòu)中的元素之間是一對多的關(guān)系。4.

圖型結(jié)構(gòu)結(jié)構(gòu)中的元素之間存在多對多的關(guān)系。5.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)基本結(jié)構(gòu)關(guān)系示意圖結(jié)點(diǎn)與結(jié)構(gòu)是相對而言的。不嚴(yán)格的說，結(jié)構(gòu)是由若干結(jié)點(diǎn)及其相互的關(guān)系所組成的。在特殊場合下，需要研究某個結(jié)點(diǎn)內(nèi)部組成時，也可以把結(jié)點(diǎn)看成一個結(jié)構(gòu)，而把組成該結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)看作為結(jié)點(diǎn)，把數(shù)據(jù)項(xiàng)組成該結(jié)點(diǎn)的組成方式看作為結(jié)點(diǎn)之間的關(guān)系。5.1.3數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是它的邏輯結(jié)構(gòu)在計算機(jī)存儲器中的實(shí)現(xiàn)，也稱為物理結(jié)構(gòu)。它是依賴于計算機(jī)的。計算機(jī)的存儲器是由許多存儲單元組成的，每個單元有唯一的地址，各存儲單元的地址是連續(xù)編碼的。一片相鄰的存儲單元的整體稱為存儲區(qū)M。要把邏輯結(jié)構(gòu)B＝(K,R)存到計算機(jī)中，就要建立一個從K的結(jié)點(diǎn)到M的映射S:K－>M，同時該映射應(yīng)具有顯式或隱式地體現(xiàn)關(guān)系R的能力。5.1.3數(shù)據(jù)的存儲結(jié)構(gòu)有四種基本的存儲映射方式：1. 順序映射方式主要用于線性數(shù)據(jù)結(jié)構(gòu)。該映射方式是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理上相鄰的存儲單元里，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系體現(xiàn)出來。2. 鏈接映射方式給每個結(jié)點(diǎn)附加一個指針字段，即將結(jié)點(diǎn)占用的存儲單元分為存放結(jié)點(diǎn)本身信息(數(shù)據(jù)項(xiàng))和存放其后繼結(jié)點(diǎn)所對應(yīng)的存儲單元的地址(指針項(xiàng))兩部分。指針項(xiàng)可以包含一個或多個指針，以指向結(jié)點(diǎn)的一個或多個后繼。3. 索引映射方式將結(jié)點(diǎn)按關(guān)鍵字排成一個序列，這樣每個結(jié)點(diǎn)在序列中均有一個對應(yīng)的位置數(shù)，這個位置就是結(jié)點(diǎn)索引。索引映射就是用結(jié)點(diǎn)索引號來確定結(jié)點(diǎn)的存儲地址。4. 散列映射方式這是一種根據(jù)結(jié)點(diǎn)關(guān)鍵字的值，通過計算來確定其存儲地址的方法，所以又稱為關(guān)鍵碼——地址轉(zhuǎn)換法。用散列映射時，K的結(jié)點(diǎn)k分散列地存儲在M的存儲單元里。5.1.4數(shù)據(jù)的運(yùn)算所謂數(shù)據(jù)的運(yùn)算是指對于數(shù)據(jù)的進(jìn)行某一特定處理的操作。計算機(jī)中的數(shù)據(jù)運(yùn)算是包括數(shù)值運(yùn)算和抽象數(shù)據(jù)類型的運(yùn)算兩方面內(nèi)容的。在本書第一章中已經(jīng)介紹了關(guān)于計算機(jī)中數(shù)值運(yùn)算的基本概念和方法，在本章中我們主要討論抽象數(shù)據(jù)類型的運(yùn)算。數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，而運(yùn)算的具體的實(shí)現(xiàn)要在存儲結(jié)構(gòu)上進(jìn)行。數(shù)據(jù)的每一種邏輯結(jié)構(gòu)都有一個運(yùn)算的集合。常用的運(yùn)算有檢索、插入、更新、排序等。5.2線性結(jié)構(gòu)線性結(jié)構(gòu)是一種最常用且最簡單的數(shù)據(jù)結(jié)構(gòu)，其結(jié)點(diǎn)之間存在著一一對應(yīng)的相互關(guān)系。無論是現(xiàn)實(shí)世界還是計算機(jī)應(yīng)用中，線性結(jié)構(gòu)都有廣泛的應(yīng)用。如我們利用自然語言，表述一句話或?qū)懽饕黄恼露际前盐淖职凑站€性的方式組織起來的；又如操作鍵盤向計算機(jī)中輸入的信息也是線性結(jié)構(gòu)。本節(jié)主要介紹線性結(jié)構(gòu)的存儲表示、運(yùn)算的具體實(shí)現(xiàn)等有關(guān)內(nèi)容。5.2.1線性表所謂線性表是由n≥0個結(jié)點(diǎn)組成的有限序列。表中有且只有一個開始結(jié)點(diǎn)(表頭)，它沒有前趨而只有一個后繼；有且只有一個終端結(jié)點(diǎn)(表尾)，它沒有后繼而只有一個前趨；其余結(jié)點(diǎn)都只有一個前趨和一個后繼。根據(jù)它們之間的關(guān)系可以排成一個線性序列：(a1，a2,……,an)這里，a1為開始結(jié)點(diǎn)；an為終端結(jié)點(diǎn)；ai-1是ai的前趨，ai是ai-1的后繼。n稱為該表的長度。長度n＝0的表稱為空表。將一個線性表存入計算機(jī)，可采用許多不同的方法。一種簡單而且自然的存儲方法是順序存儲：即把結(jié)點(diǎn)按其索引從小到大一個接一個地存放在一片連續(xù)的存儲區(qū)內(nèi)。假設(shè)表中每個結(jié)點(diǎn)所需L個內(nèi)存單位，則表的第I個結(jié)點(diǎn)的存儲地址為：LOC(ai)=LOC(a1)+L*(i-1)式中，LOC(a1)為表中第一個結(jié)點(diǎn)的存儲地址。利用此公式可以很快算出表中任一結(jié)點(diǎn)的地址。5.2.1線性表如果線性表的所有結(jié)點(diǎn)都具兩個主要類型，稱其為向量(或一維數(shù)組)。向量的結(jié)點(diǎn)稱為元素，元素的索引稱為下標(biāo)。向量有兩個主要的特性：一是均勻性，向量所有元素必須具有相同的元素描述(不管元素是簡單的還是復(fù)雜的，都要一致)，元素長度相同；二是有序性，向量中各元素是有序的，并且元素之間的次序時不能改變的。對向量經(jīng)常進(jìn)行的運(yùn)算有下列幾種：向量中的第i個元素；修改向量中的第i個元素；刪除向量中的第i個元素；在向量第i個元素之后(或之前)插入一個新元素；對向量中的元素按某個數(shù)據(jù)項(xiàng)值遞增(或遞減)的順序進(jìn)行重新排序；按某個特定值查找向量中的元素。5.2.1線性表對于向量中的插入和刪除運(yùn)算，由于需要保持運(yùn)算結(jié)果仍然是順序存儲，因此要移動一系列元素。在插入和刪除過程中，向量中元素的個數(shù)n不能超過某個整數(shù)N0。在所有的程序設(shè)計語言中，都已建立了向量(即一維數(shù)組)的形式定義并實(shí)現(xiàn)了對向量的運(yùn)算。因此，用語言編制程序時只要按所有語言的規(guī)定引用即可。5.2.2棧棧是一種線性表，它限定只能在表的一端進(jìn)行插入和刪除。在表中，允許插入和刪除的一端稱為棧頂，而不允許插入和刪除的另一端稱為棧底。根據(jù)上述定義，棧的修改時按后進(jìn)先出的原則進(jìn)行的，因此棧又稱后進(jìn)先出(LIFO)表。棧通常是順序存儲的，分配一片連續(xù)的存儲區(qū)域來存放棧中的結(jié)點(diǎn)，并用一個變量來指示當(dāng)前棧頂?shù)奈恢谩?.2.2棧棧在系統(tǒng)軟件中用得很多，包括編譯器和解釋程序。事實(shí)上，大多數(shù)C編譯器都利用棧將參數(shù)傳遞給函數(shù)。入棧和出棧是棧的兩個基本操作。要實(shí)現(xiàn)棧，需要兩個函數(shù)：push()和pop()。push()將新結(jié)點(diǎn)置于棧頂，而pop()函數(shù)將結(jié)點(diǎn)從棧頂取出。除此之外，還要用數(shù)組為棧在內(nèi)存中安排空間。根據(jù)存放數(shù)據(jù)的類型和可能要存放數(shù)據(jù)的最大數(shù)目，定義一維數(shù)組stack,用下標(biāo)變量top作為棧頂?shù)闹甘咀兞?。top=0表示棧空，數(shù)組元素stack[0]稱為棧底，stack[top]表示最新進(jìn)棧的元素，稱為棧頂。當(dāng)top的值等于數(shù)組的最大下標(biāo)時，則棧滿。5.2.2棧棧的一個重要作用是在程序設(shè)計語言中實(shí)現(xiàn)遞歸過程。程序設(shè)計語言的運(yùn)行組織是在程序運(yùn)行期間表示程序變量值的一組數(shù)據(jù)結(jié)構(gòu)。任何允許使用遞歸過程的語言，如C、pascal、APL、LISP和PL/1等，都要將屬于各遞歸層次的過程變量的值所組成的現(xiàn)場紀(jì)錄保存在一個棧中。每當(dāng)需要調(diào)用過程P時，就要在棧頂為P建立一個新的現(xiàn)場紀(jì)錄，無論棧中是否已有過去調(diào)用P時建立的其他現(xiàn)場紀(jì)錄。一旦結(jié)束當(dāng)前對過程P的調(diào)用，則將相應(yīng)的現(xiàn)場紀(jì)錄從棧中取走。當(dāng)P返回時，相應(yīng)的現(xiàn)場紀(jì)錄一定是在棧頂，因?yàn)橹挥挟?dāng)執(zhí)行P時所調(diào)用的其它過程都已返回后，P才能返回。從而保證在P返回時，其相應(yīng)的現(xiàn)場紀(jì)錄又出現(xiàn)在棧頂。從該記錄中，可知調(diào)用P的指令地址，以控制P的返回。5.2.2棧遞歸可以使程序簡潔而清晰，但一般情況下它既不省時間，也不省空間，因?yàn)樗仨氁蕾囅到y(tǒng)中的運(yùn)行棧，保存每次調(diào)用時的參數(shù)、變量及返回信息等。這個運(yùn)行棧對用戶來說是不可見的。通常任何遞歸過程(或函數(shù))都可修改成非遞歸的形式。這就需要用戶自己定義一個棧，以保存調(diào)用時的現(xiàn)場紀(jì)錄?，F(xiàn)場紀(jì)錄一般含有過程參數(shù)的當(dāng)前值、過程的所有局部變量的當(dāng)前值和表示返回地址的值(即當(dāng)前調(diào)用的過程結(jié)束時，控制返回位置的值)。非遞歸過程雖然運(yùn)行快，也省內(nèi)存，但它結(jié)構(gòu)復(fù)雜、不易理解，只有當(dāng)程序的運(yùn)行速度非常重要時，采用非遞歸過程才是適宜的。5.2.3隊(duì)列隊(duì)列也是一種線性表，對于它所有的插入都在表的一端進(jìn)行，而所有的刪除都在表的另一端進(jìn)行。插入數(shù)據(jù)的一端稱為隊(duì)列的頭，刪除數(shù)據(jù)的一端稱為隊(duì)列的尾。滿足先進(jìn)先出的原則，簡稱為先進(jìn)先出(FIFO)表。隊(duì)列總?cè)粘Ｉ钪械教幙梢姡y行、快餐店中顧客的隊(duì)都是隊(duì)列。隊(duì)列在程序設(shè)計中也經(jīng)常出現(xiàn)，例如操作系統(tǒng)中作業(yè)排隊(duì)。在可運(yùn)行多道程序的計算機(jī)系統(tǒng)中，同時有幾個作業(yè)運(yùn)行，運(yùn)行的結(jié)果都需要通過通道輸出。若通道未完成傳輸，則作業(yè)等待，并按請求輸出的先后順序排隊(duì)。當(dāng)通道傳輸完畢可接受新的傳輸任務(wù)時，排頭的作業(yè)便從隊(duì)列中退出，并準(zhǔn)備輸出。排頭的作業(yè)是下次要輸出的作業(yè)，排尾的作業(yè)是剛進(jìn)入隊(duì)列的作業(yè)。5.2.3隊(duì)列通常隊(duì)列用順序存儲的形式實(shí)現(xiàn)，分配一片連續(xù)的存儲空間來存放隊(duì)列元素，并用兩個變量分別指向當(dāng)前隊(duì)列的排頭和排尾。入隊(duì)和出隊(duì)是隊(duì)列的兩個基本操作。根據(jù)存放數(shù)據(jù)的類型和可能存放數(shù)據(jù)的最大數(shù)目，定義一維數(shù)組queue,用下標(biāo)變量front和rear分別指示隊(duì)列的排頭和排尾。5.2.3隊(duì)列由于隊(duì)列的兩端是變的，需要克服假溢出問題，即當(dāng)排頭位置的元素已經(jīng)出隊(duì)產(chǎn)生了空位置，但排尾元素填滿，隊(duì)列依然被認(rèn)為是滿的，在進(jìn)行入隊(duì)操作就會“溢出”。一個滿意的辦法是把隊(duì)列設(shè)想為一個首尾相接的環(huán)形表。5.2.3隊(duì)列初始狀態(tài)，變量front和rear的值為0，隊(duì)列空。如果有MAX+1個元素要參加排隊(duì)，則數(shù)組queue的下標(biāo)范圍從0到MAX。要加入一個數(shù)據(jù)時，排尾指示變量rear的值取下一個相鄰單元的下標(biāo)，數(shù)據(jù)賦給修改后rear指示的單元。如果修改前的rear值為MAX，則queae[0]作為queue[MAX]的下一個單元。如果修改后rear的值與front的值相等，表示環(huán)形隊(duì)列首尾相接，這時為隊(duì)滿，不能再加入任何數(shù)據(jù)了。需恢復(fù)rear的原來值，并向系統(tǒng)報告隊(duì)滿。從隊(duì)列取數(shù)據(jù)時，想修改front使其指示下一個隊(duì)列元素，然后取出front所指單元的數(shù)據(jù)。如果修改前front與rear的值相等，說明隊(duì)列空，沒有可取數(shù)據(jù)。結(jié)論是：向隊(duì)列加入數(shù)據(jù)時要判斷隊(duì)列是否滿，從隊(duì)列取數(shù)據(jù)時要判斷是否空。5.2.4鏈表采用順序存儲方式的線性表，在插入和刪除操作時往往造成大量信息的移動，效率較低。同時，順序存儲必須占用一片連續(xù)的存儲空間，存儲分配只能預(yù)先進(jìn)行。如果插入數(shù)據(jù)量超出預(yù)先分配的存儲空間，要臨時擴(kuò)大有很大困難。對插入和刪除操作頻繁、存儲空間大小難以預(yù)先確定的線性表，通常采用鏈?zhǔn)酱鎯?。鏈?zhǔn)酱鎯Φ木€性表稱為鏈表。其結(jié)點(diǎn)一般由兩部分組成：一部分存放結(jié)點(diǎn)的數(shù)據(jù)，稱為數(shù)據(jù)字段；另一部分存放指向一下結(jié)點(diǎn)的地址，稱為指針字段。5.2.4鏈表利用以上的存儲結(jié)構(gòu)就可以把物理上不連續(xù)的結(jié)點(diǎn)利用指針連成一個鏈表，即線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)可以應(yīng)用于各類線性表中，以提高存儲性能。1. 鏈?zhǔn)綏ｆ準(zhǔn)綏５慕Y(jié)構(gòu)如圖所示，top為指向棧頂結(jié)點(diǎn)的指針變量。在初始狀態(tài)下，top的值為空，用∧表示，說明棧中沒有任何結(jié)點(diǎn)。當(dāng)一個數(shù)據(jù)要進(jìn)棧時，先要向系統(tǒng)申請一個結(jié)點(diǎn)，把數(shù)據(jù)存入數(shù)據(jù)字段，然后按規(guī)定撥動指針將其鏈入棧中。當(dāng)要從棧中刪除一個結(jié)點(diǎn)時，要先取出棧頂結(jié)點(diǎn)中的數(shù)據(jù)，然后把該結(jié)點(diǎn)指針字段的值賦給指針變量top，調(diào)用free函數(shù)釋放該結(jié)點(diǎn)。5.2.4鏈表2. 鏈?zhǔn)疥?duì)列下圖是鏈?zhǔn)疥?duì)列及其插入和刪除操作示意圖。指針變量front指向隊(duì)列的頭結(jié)點(diǎn)，rear指向隊(duì)列的尾結(jié)點(diǎn)。隊(duì)空時，front和rear均為空。向?qū)χ胁迦胍粋€結(jié)點(diǎn)時，先向系統(tǒng)申請結(jié)點(diǎn)，將該結(jié)點(diǎn)鏈入rear所指向的指針字段，并使rear指向新的結(jié)點(diǎn)。如果插入的新結(jié)點(diǎn)前隊(duì)是空的，則還要使front指向新插入的結(jié)點(diǎn)。要從隊(duì)中刪除一個結(jié)點(diǎn)時，要把front所指結(jié)點(diǎn)的指針字段值賦給front，然后釋放該結(jié)點(diǎn)，也可能刪除一個結(jié)點(diǎn)后隊(duì)列為空，則需置rear為空。5.2.4鏈表3. 單向鏈表下圖是單向鏈表及其插入和刪除操作示意圖。指針變量head指向單向鏈表的表頭結(jié)點(diǎn)。表頭結(jié)點(diǎn)中數(shù)據(jù)字段通常不用，指針字段用于存放第一個結(jié)點(diǎn)的指針。5.2.3鏈表4. 單環(huán)鏈表將單鏈表的形式稍加改動，讓表中最后一個結(jié)點(diǎn)的指針指向單鏈表的表頭結(jié)點(diǎn)，這就形成了一個環(huán)鏈表，稱為單環(huán)鏈表。圖(a)所示的單環(huán)鏈表中，為了要找到最后一個結(jié)點(diǎn)，必須從head出發(fā)，訪問所有的結(jié)點(diǎn)。如果改用表尾變量rear來代替head,rear指向最后一個結(jié)點(diǎn)，如圖(b)所示。從最后一個結(jié)點(diǎn)的指針字段立即可找到第一個結(jié)點(diǎn)的位置。這樣改動后，無論找最后一個結(jié)點(diǎn)還是找第一個結(jié)點(diǎn)都很方便。實(shí)用中常采用這種方式。5.2.3鏈表5. 雙向鏈表雙向鏈表的每一個結(jié)點(diǎn)除了數(shù)據(jù)字段外，還包括兩個指針，一個指針，一個指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，另一個指針指向它的前趨結(jié)點(diǎn)。雙向鏈表有兩個好處：一是可以從兩個方向搜索某個結(jié)點(diǎn)，這不但使鏈表的排序操作變得比較簡單，而且在數(shù)據(jù)庫情況下允許用戶在兩個方向進(jìn)行搜索；二是無論利用向量前這一鏈還是向后這一鏈，都可以遍歷整個鏈表。如果有一根鏈?zhǔn)Я耍€可以利用另一根鏈修復(fù)整個鏈表。5.2.3鏈表6. 雙向循環(huán)鏈表類似單向環(huán)鏈表，也可以將雙鏈表的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來。這樣不增加額外內(nèi)存卻給某些運(yùn)算帶來了方便。通常將鏈表的頭尾指針存放在一個稱為表頭結(jié)點(diǎn)的特殊結(jié)點(diǎn)之中。該結(jié)點(diǎn)鏈接在始結(jié)點(diǎn)和終結(jié)點(diǎn)之間，從而構(gòu)成如圖5.11所示的雙向環(huán)鏈表。表頭結(jié)點(diǎn)的數(shù)據(jù)字段可以空著不用，也可以用來存儲諸如表中結(jié)點(diǎn)個數(shù)等信息。表頭結(jié)點(diǎn)的引入使得雙環(huán)鏈表一創(chuàng)建就有結(jié)點(diǎn)存在，這給某些運(yùn)算帶來方便。雙向鏈表的插入和刪除操作與雙鏈表相同。5.3樹形結(jié)構(gòu)樹形結(jié)構(gòu)是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，其結(jié)點(diǎn)之間具有分支和層次關(guān)系，在各種算法問題求解、文件管理系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中有廣泛的應(yīng)用。本節(jié)主要介紹樹形結(jié)構(gòu)的存儲表示、運(yùn)算的具體實(shí)現(xiàn)等有關(guān)內(nèi)容。5.3.1樹及其遍歷樹的遞歸定義：樹T是一個或多個結(jié)點(diǎn)的有限集合。它滿足如下條件：(1)有一個特別指定的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；(2)其余結(jié)點(diǎn)分別成為m≥0個互不相交的子集T1、T2、…、Tm,每一子集Ti都是一顆樹，稱為根的子樹。樹的結(jié)構(gòu)5.3.1樹及其遍歷一個結(jié)點(diǎn)的子樹個數(shù)稱為該結(jié)點(diǎn)的度數(shù)。度數(shù)為0的結(jié)點(diǎn)稱為葉或終端結(jié)點(diǎn)。度數(shù)大于0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)。樹形結(jié)構(gòu)中常使用家族關(guān)系來描述。圖中結(jié)點(diǎn)A是結(jié)點(diǎn)B和C的父結(jié)點(diǎn)，而B和C是A的子結(jié)點(diǎn)；B和C是兄弟；D、E、F是B的子結(jié)點(diǎn)，I又是E的子結(jié)點(diǎn)，B是D、E、F和I的祖先，D、E、F和I是B的后代。樹T中如果子樹T1、T2、…、Tm的相對次序是重要的，則稱樹T為有序樹。在有序樹中可以稱T1為根的第一棵子樹，T2為根的第二棵子樹，等等。由零棵或多棵樹構(gòu)成的集合稱為森林。刪去樹根，樹就變成森林，加上一個結(jié)點(diǎn)作樹根，森林就變成樹。右圖就是去掉樹根A得到的森林。5.3.1樹及其遍歷樹型結(jié)構(gòu)的重要運(yùn)算是遍歷。遍歷一棵樹就是按一定的次序系統(tǒng)地訪問樹的所有結(jié)點(diǎn)，使每個結(jié)點(diǎn)恰好被訪問一次。遍歷一棵樹的過程實(shí)際上把樹進(jìn)行線性化。遍歷樹和森林可以按深度優(yōu)先遍歷，也可按廣度優(yōu)先遍歷。1. 深度優(yōu)先遍歷，有先根次序和后根次序兩種方法。先根次序的遞歸定義：(1)訪問的一棵樹的根；(2)在先根次序下遍歷的一棵樹根的子樹；(3)在先根次序下遍歷其它的樹。后根次序的遞歸定義：(1)在后根次序下遍歷第一棵樹根的子樹；(2)訪問第一棵樹的根；(3)在后根次序下遍歷其它的樹。5.3.1樹及其遍歷如圖所示的森林，按先根次序遍歷得到的結(jié)點(diǎn)序列是:

BEFGKCHILMDJ按后根次序遍歷得到的結(jié)點(diǎn)序列是：

EFKGBHLMICJD5.3.1樹及其遍歷2. 廣度優(yōu)先遍歷首先依次訪問層數(shù)為0的結(jié)點(diǎn)，然后依次訪問層次為1的結(jié)點(diǎn)，等等，直到訪問完最后一層的所有結(jié)點(diǎn)。即訪問是從上到下、從左到右依次進(jìn)行的。按廣度優(yōu)先遍歷上圖所示的森林，得到的結(jié)點(diǎn)序列是：

BCDEFGHIJKLM遍歷樹形結(jié)構(gòu)是系統(tǒng)地訪問樹或森林的所有結(jié)點(diǎn)?？梢岳脴湫谓Y(jié)構(gòu)的遍歷來查找滿足某種條件的結(jié)點(diǎn)，形同于線性表的順序查找。5.3.2二叉樹二叉樹的定義：二叉樹是結(jié)點(diǎn)的有限集合，此集合或?yàn)榭占驗(yàn)橛梢粋€根結(jié)點(diǎn)和兩棵互不相交的稱為左右的二叉樹構(gòu)成。二叉樹的結(jié)構(gòu)5.3.2二叉樹由定義可知二叉樹中每個結(jié)點(diǎn)至多只有兩個子樹。二叉樹與樹有區(qū)別：樹至少有一個結(jié)點(diǎn)，而二叉樹可以是空的；樹的子樹不區(qū)分其次序，二叉樹的子樹有左右之分。下圖是二叉樹的五種基本形式。5.3.2二叉樹在計算機(jī)中，為了表示二叉樹結(jié)點(diǎn)之間的關(guān)系，最自然的方法是鏈接方法。二叉樹的每個結(jié)點(diǎn)至多只有兩棵子樹。因此，在每個結(jié)點(diǎn)中除存儲結(jié)點(diǎn)本身的數(shù)據(jù)外，再設(shè)置兩個指針字段llink和rlink,分別指向結(jié)點(diǎn)的左子樹和右子樹。當(dāng)結(jié)點(diǎn)的某個子樹為空時，相應(yīng)的指針為空指針。結(jié)點(diǎn)的形式為：5.3.2二叉樹這樣，一棵二叉樹里所有這種形式的結(jié)點(diǎn)，再加上一個指向樹根的指針root構(gòu)成二叉樹的存儲表示。這種存儲表示又稱為llink－rlink表示法。下圖是二叉樹的llink－rlink表示。5.3.2二叉樹樹和二叉樹不同，樹的每個結(jié)點(diǎn)的子結(jié)點(diǎn)數(shù)沒有作限制。因此，如果也采用二叉樹的方法在結(jié)點(diǎn)內(nèi)設(shè)置指針，則每個結(jié)點(diǎn)內(nèi)設(shè)置的指針數(shù)不好確定。若以樹中子結(jié)點(diǎn)最多的結(jié)點(diǎn)來統(tǒng)一設(shè)置指針，顯然浪費(fèi)內(nèi)存空間。若以每個結(jié)點(diǎn)的實(shí)際子結(jié)點(diǎn)數(shù)來設(shè)置指針，則各個結(jié)點(diǎn)大小不統(tǒng)一，很難管理。由于樹或森林與二叉樹之間有一個對應(yīng)關(guān)系，任何森林均可唯一地對應(yīng)到一棵二叉樹。反過來，任何一棵二叉樹也能唯一地對應(yīng)到一棵樹或森林。因此，通?？上劝褬浠蛏洲D(zhuǎn)換成一棵對應(yīng)的二叉樹，然后再用llink－rlink的方法進(jìn)行存儲和運(yùn)算。最后再將二叉樹轉(zhuǎn)換成樹或森林。如果將森林F看作樹的有序集合，F(xiàn)=(T1,T2,…,Tn)，則對應(yīng)于F的二叉樹B(F)定義如下：(1)若n=0,到B(F)為空；(2)若n>0,則B(F)的根是T1的根W1,B(F)的左子樹是B(T11,T12,…,T1m)，其中T11,T12,…,T1m是W1的子樹；B(F)的右子樹是B(T2,…,Tn)。5.3.2二叉樹用一種自然方式來描述這種轉(zhuǎn)換：兄弟之間用連線連起來；保留父結(jié)點(diǎn)到第一個子結(jié)點(diǎn)的連線，去掉其余子結(jié)點(diǎn)與父結(jié)點(diǎn)的連線。下圖表示森林轉(zhuǎn)換成二叉樹的結(jié)果。(a)森林b)轉(zhuǎn)換后未經(jīng)整理的二叉樹(c)經(jīng)整理后的二叉樹5.3.2二叉樹反之，一棵二叉樹唯一地對應(yīng)于一棵樹或森林。設(shè)B為一棵二叉樹，W為B的根，L、R分別為W的左、右子樹，則對應(yīng)的樹或森林F(B)定義如下：(1)若B為空，則F(B)是空的森林；(2)若B不為空，則F(B)是一棵樹T1加上森林F(R)，其中樹T1的根為W，W的子樹為F(L)。用一個自然方式來描述這種轉(zhuǎn)換：若結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子樹，則把該結(jié)點(diǎn)的右子樹，右子樹的右子樹，都與該結(jié)點(diǎn)的父結(jié)點(diǎn)用線連接起來，然后去掉所有父結(jié)點(diǎn)到右子樹的連線。(a)二叉樹(b)經(jīng)整理后的森林5.3.2二叉樹二叉樹概念很重要。一方面，許多實(shí)際問題中抽象出來的數(shù)據(jù)結(jié)點(diǎn)是二叉樹的形式，而且許多算法問題可以方便地用二叉樹形式來解決。另一方面，樹或森林與二叉樹之間有唯一的一一對應(yīng)關(guān)系，這為樹的存儲與運(yùn)算帶來了方便。二叉樹具有下列特性：(1)深度為k的二叉樹的結(jié)點(diǎn)總數(shù)最大為：2k-1(k≥1)；在二叉樹第i層的結(jié)點(diǎn)數(shù)最大為：2i-1(i≥1)。(2)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，而其度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。(3)如果有n個結(jié)點(diǎn)的完全二叉樹(其深度為log2n+1),從前第一層的結(jié)點(diǎn)自上而下、自左至右地對結(jié)點(diǎn)進(jìn)行編號(1～n)，則對任一結(jié)點(diǎn)i(1≤i≤n)有：a、如果i≠1，則其父結(jié)點(diǎn)的編號為;如果i=1，則i為根，無父結(jié)點(diǎn)b、如果2i≤n，則其左子樹結(jié)點(diǎn)的編號為2i;如2i>n,則I無左子結(jié)點(diǎn)。c、如果2i+1≤n，則其右子樹的編號為2i+1;如果2i+1>n，則I無右子結(jié)點(diǎn)。5.3.2二叉樹所有結(jié)點(diǎn)的平衡因子的絕對值不大于1的二叉樹稱為平衡二叉樹。所謂平衡因子，就是二叉樹中任一結(jié)點(diǎn)的右子樹的深度與左子樹的深度之差。圖5-20(a)是非平衡二叉樹的例子。5.3.2二叉樹一棵深度為k的有2k-1個結(jié)點(diǎn)的二叉樹，稱為深度為k的滿二叉樹(k≥1)。圖5-20(b)為一棵深度為4的滿二叉樹。5.3.2二叉樹如果一棵二叉樹有n(2i-1≤n≤2i+1-1,i≥1)個結(jié)點(diǎn)，其中2i-1個結(jié)點(diǎn)排滿上面i個層，而剩下的n-(2i-1)個結(jié)點(diǎn)從左到右排在第i+1層，則稱該二叉樹為完全二叉樹(有時又稱擬滿二叉樹)。圖5-20(c)是一棵完全二叉樹。5.3.2二叉樹如果一棵二叉樹有n(2i-1≤n≤2i+1-1,i≥1)個結(jié)點(diǎn)，其中2i-1個結(jié)點(diǎn)排滿上面i個層，而剩下的n-(2i-1)個結(jié)點(diǎn)隨意地排在第i+1層上，則稱該二叉樹為豐滿二叉樹，圖5-20(d)是一棵豐滿二叉樹。由上定義可知，滿二叉樹一定是完全二叉樹，也是豐滿二叉樹。而完全二叉樹一定是豐滿二叉樹。反之則不然。5.3.3遍歷二叉樹遍歷二叉樹是指按一定規(guī)律訪問二叉樹的每個結(jié)點(diǎn)，使每個結(jié)點(diǎn)被訪問一次，而且只被訪問一次。按照訪問結(jié)點(diǎn)的次序?？傻玫蕉鏄浣Y(jié)點(diǎn)的線性序列。由于二叉樹是一種非線性結(jié)構(gòu)，要找一個完整而有規(guī)律的遍歷方法，以便得到二叉樹結(jié)點(diǎn)的一個線性序列。令L、D、R分別表示遍歷左子樹、訪問根結(jié)點(diǎn)、遍歷右子樹，則對一棵二叉樹可有LDR、LRD、DLR、DRL、RDL和LRD六種情況。若限定先左后右，則只有DLR、LRD和LRD三種情況，分別稱為先根順序遍歷、中根順序遍歷和后根順序遍歷。三種遍歷二叉樹的遞歸算法定義如下：先根順序遍歷：若二叉樹為空，則退出；否則，訪問根結(jié)點(diǎn)，按先根順序遍歷左子樹，按先根順序遍歷右子樹。中根順序遍歷：若二叉樹為空，則退出；否則，按中根順序遍歷左子樹，訪問根結(jié)點(diǎn)，按中根順序遍歷右子樹。后根順序遍歷：若二叉樹為空，則退出；否則，按后根順序遍歷左子樹，按后根順序遍歷右子樹，訪問根結(jié)點(diǎn)。5.3.3遍歷二叉樹例如圖5-21所示的二叉樹的按照不同順序的遍歷序列有：先根遍歷序列：ABDGEHCFIJ中根遍歷序列：DGBEHACIFJ后根遍歷序列：GDHEBIJFCA5.4圖形結(jié)構(gòu)圖形結(jié)構(gòu)在計算機(jī)科學(xué)、人工智能、工程學(xué)等許多領(lǐng)域中均有廣泛的應(yīng)用。本節(jié)介紹圖形結(jié)構(gòu)的存儲表示及有關(guān)操作。5.4.1圖的概念數(shù)據(jù)結(jié)構(gòu)B=(K,R)僅含一種任意的關(guān)系N,則稱這種數(shù)據(jù)結(jié)構(gòu)為圖。通常，圖用G=(V,E)來表示。圖中結(jié)點(diǎn)又稱為頂點(diǎn)，V是結(jié)點(diǎn)的非空有限集合，結(jié)點(diǎn)的偶對稱為邊，E是邊的集合。圖中代表一條邊的偶對稱如是無序的，則此圖稱為無向圖；如果是有序的，則此圖稱為有向圖。無向圖和有向圖有些性質(zhì)是相同的。無向圖中(V1,V2)和(V2,V1)這兩個偶對代表同一條邊。有向圖中<V1,V2>和<V2,V1>這兩個偶對代表不同的兩條邊，它們有自己的始點(diǎn)和終點(diǎn)。有向圖中的邊有時也稱為弧。(a)無向圖(b)有向圖5.4.1圖的概念邊集E為空的圖稱為零圖。邊集E為空且結(jié)點(diǎn)V中只有一個元素的圖稱為平凡圖。任何一個具有n個結(jié)點(diǎn)的無向圖，其邊數(shù)小于等于n*(n-1)/2。邊數(shù)正好為n*(n-1)/2的n個結(jié)點(diǎn)的無向圖稱為完全圖。任何一個具有n個結(jié)點(diǎn)的有向圖，其最大邊數(shù)為n*(n-1)/2。若(V1,V2)∈E，則稱V1和V2是相鄰結(jié)點(diǎn)，而邊(V1,V2)則是與結(jié)點(diǎn)V1和V2相關(guān)連的邊。若<V1,V2>是有向圖一條邊，則稱結(jié)點(diǎn)V1鄰接到結(jié)點(diǎn)V2，結(jié)點(diǎn)V2鄰接于結(jié)點(diǎn)V1,而邊<V1,V2>是與結(jié)點(diǎn)V1和V2相關(guān)連的。與圖中結(jié)點(diǎn)k相關(guān)連的邊的數(shù)目，稱為該結(jié)點(diǎn)的度。在有向圖中，以結(jié)點(diǎn)k為終點(diǎn)的邊的數(shù)目，稱為k的入度；以結(jié)點(diǎn)k為始點(diǎn)的邊的數(shù)目，稱為k的出度。有向圖中出度為0的結(jié)點(diǎn)稱為葉。圖G=(V,E)和圖G’(V’,E’),若V’包含于V,E’包含于E,且E’中的邊所關(guān)連的結(jié)點(diǎn)均在V’中，則稱圖G’為圖G的子圖。5.4.1圖的概念在圖G=(V,E)中，如果存在結(jié)點(diǎn)序列V1、V2、…、Vk,使(V1,V2)、(V2,V3)、…、(Vk-1,Vk)都在E中(對有向圖，則使得<V1,V2>、…、<Vk-1,Vk>都在E中)，則稱從結(jié)點(diǎn)V1到Vk存在一條路徑。路徑上的邊數(shù)稱為長度。如果一條路徑上的點(diǎn)除V1和Vk可以相同外，其他結(jié)點(diǎn)都不相同，則稱該路徑為簡單路徑。如果V1和Vk是同一個結(jié)點(diǎn)，則此簡單路徑稱為回路。設(shè)圖G(V,E)中，至少存在一個結(jié)點(diǎn)W(W∈V)，由W出發(fā)可以到達(dá)圖中其他所有結(jié)點(diǎn)，則稱W是圖的根，稱圖G為有根圖。對于無向圖G=(V,E)，如果從Vi到Vj有一條路徑(從Vi到Vj也有一條路徑)，則稱Vi和Vj是連通的。若G中任意兩個結(jié)點(diǎn)都是連通的，則稱G是連通的。一個無向圖的最大連通子圖，稱為該圖的連通分支。5.4.1圖的概念對于有向圖G=(V,E)，如果略去有向邊的方向所得的無向圖是連通的，則稱G是弱連通的。若G是弱連通的，且G中任意兩結(jié)點(diǎn)之間至少有一個結(jié)點(diǎn)可以到達(dá)另一個結(jié)點(diǎn)，則稱G為單向連通的。若G中任意一對結(jié)點(diǎn)之間都是互相可達(dá)的，則稱此有向圖是強(qiáng)連通的。一有向圖的強(qiáng)連通的最大子樹，稱為該有向圖的強(qiáng)連通分支。如果給圖G=(V,E)的每一條邊加一個權(quán)值，稱此圖為帶權(quán)圖。帶權(quán)的連通圖又稱為網(wǎng)。如圖5-23所示。5.4.2圖的存儲表示法這里主要介紹圖的鄰接矩陣表示法。在計算機(jī)中常用鄰接矩陣來表示圖。表示圖中結(jié)點(diǎn)之間相鄰關(guān)系的矩陣稱為鄰接矩陣。一個有n個結(jié)點(diǎn)的圖G，其鄰接矩陣咳定義為n*n的矩陣A，即

1,若(Vj,Vj)或<Vj,Vj>∈EA[i,j]= 0,否則圖5-24中G1和G2的鄰接矩陣分別為A1和A2。5.4.2圖的存儲表示法圖5-24G1和G2的鄰接矩陣5.4.2圖的存儲表示法對于帶權(quán)圖(網(wǎng))，其鄰接矩陣中值為1的元素用相應(yīng)邊的權(quán)取代即可。如圖5-25所示。用鄰接矩陣表示圖，對有向圖需要n*n個單元來存儲此矩陣。對于無向圖，由于它的鄰接矩陣是對稱的，只需存儲其下三角部分即可。帶權(quán)有向圖G3

鄰接矩陣

圖5-25帶權(quán)有向圖的鄰接矩陣5.4.2圖的存儲表示法用鄰接矩陣表示圖，對有向圖需要n*n個單元來存儲此矩陣。對于無向圖，由于它的鄰接矩陣是對稱的，只需存儲其下三角部分即可。用鄰接矩陣表示圖，很容易判定任意兩結(jié)點(diǎn)之間的相鄰關(guān)系和各個結(jié)點(diǎn)的度數(shù)。5.4.3圖的遍歷和生成樹在給定的圖G中，從任一結(jié)點(diǎn)V0出發(fā)，系統(tǒng)地訪問圖中每一個結(jié)點(diǎn)一次，稱為圖的遍歷。圖的遍歷有按深度和按廣度優(yōu)先兩種。1.深度優(yōu)先遍歷先訪問結(jié)點(diǎn)V0，然后選擇一個與V0鄰接的未訪問過的結(jié)點(diǎn)V1，再從V1出發(fā)按深度優(yōu)先遍歷。當(dāng)遇到一個所有鄰接與它的結(jié)點(diǎn)均被訪問完了的結(jié)點(diǎn)W時，退回到以訪問序列的最后一個擁有未被訪問過的序列結(jié)點(diǎn)，再從該結(jié)點(diǎn)按深度優(yōu)先遍歷。當(dāng)任何已被訪問過的結(jié)點(diǎn)的所有鄰接結(jié)點(diǎn)均未被訪問過，此遍歷結(jié)束。5.4.3圖的遍歷和生成樹按深度優(yōu)先遍歷圖5-26的有向圖和無向圖的結(jié)點(diǎn)序列分別為:有向圖

①，②，③，⑥，④，⑤，⑦無向圖

①，②，④，⑧，⑤，⑥，③，⑦(a)有向圖

(b)無向圖圖5-26圖的深度優(yōu)先遍歷示例5.4.3圖的遍歷和生成樹對于連通的無向圖和強(qiáng)連通的有向圖，從圖中任何一個結(jié)點(diǎn)出發(fā)均可系統(tǒng)地遍歷所有結(jié)點(diǎn)。對不連通的無向圖和不是強(qiáng)連通的有向圖，從圖中任意一個結(jié)點(diǎn)出發(fā)一般不能系統(tǒng)地遍歷所有的結(jié)點(diǎn)。要訪問其它結(jié)點(diǎn)尚需從未訪問過的結(jié)點(diǎn)中找一個結(jié)點(diǎn)作為起點(diǎn)，再進(jìn)行遍歷。從圖G=(V,E)中任一點(diǎn)出發(fā)遍歷圖時，將邊集E(G)分成兩個集合T(G)和B(G)，其中T(G)是遍歷時走過的邊集，B(G)是剩余的邊集。顯然，G=(V,T)是G=(V,E)的子圖，稱此子圖為以V6為起點(diǎn)的深度優(yōu)先遍歷生成樹。上述圖5-26從結(jié)點(diǎn)①出發(fā)的深度優(yōu)先生成樹如圖5-27所示。5.4.3圖的遍歷和生成樹(a)從有向圖結(jié)點(diǎn)①出發(fā)的深度優(yōu)先生成樹(b)從無向圖結(jié)點(diǎn)①出發(fā)的深度優(yōu)先生成樹圖5-27深度優(yōu)先生成樹5.4.3圖的遍歷和生成樹2.廣度優(yōu)先遍歷訪問圖G=(V,E)中結(jié)點(diǎn)V0，然后訪問與V0相鄰接的所有未被訪問過的結(jié)點(diǎn)V1、V2、…、Vk，然后再依次訪問與V1、V2、…、Vk，相鄰接的所有未被訪問過的結(jié)點(diǎn)，如此一直進(jìn)行下去，之至所有結(jié)點(diǎn)均被訪問遍歷為止。其他情況與深度優(yōu)先遍歷類似。圖5-28是圖5-26有向圖和無向圖的廣度優(yōu)先遍歷結(jié)點(diǎn)序列和廣度優(yōu)先遍歷生成樹：(a)從結(jié)點(diǎn)①出度的遍歷序列：①、②、④、⑤、⑥、③、(b)從結(jié)點(diǎn)①出度的遍歷序列：①、②、③、④、⑤、⑥、⑦、⑧(a)有向圖廣度優(yōu)先遍歷生成樹(b)無向圖廣度優(yōu)先遍歷生成樹5.5內(nèi)部排序按規(guī)定的順序?qū)⒁唤M數(shù)據(jù)重新排列稱為排序(或分類)。排序過程中文件放在內(nèi)存處理的稱為內(nèi)部排序；如果排序過程中還要使用外存的稱為外部排序。這里介紹的是內(nèi)部排序。如果待排序文件中存在多個相同關(guān)鍵碼的記錄，經(jīng)過排序后這些記錄原來的相對次序仍保持不變的，稱這種排序算法是穩(wěn)定的，否則稱為不穩(wěn)定的。排序有廣泛的應(yīng)用，下面介紹幾種常用的排序方法。5.5.1簡單插入排序簡單插入排序是插入排序的一種。它是將待排序的數(shù)據(jù)逐一取出，與已排序數(shù)據(jù)進(jìn)行比較，并插在適當(dāng)?shù)奈恢?。第i次插入時，a[1]、a［2］、…、a[i—1]已排序好。取出a[i]，在1到i的范圍為其找一個合適的位置

j，將從

a[j]到a[i-1]的數(shù)據(jù)依次后移一個位置，在空出來的位置j上插入原來的a[j]。例如，現(xiàn)有待排序記錄8個，它們的關(guān)鍵分別為7、5、4、9、1、6、3、2。從i=2開始經(jīng)過七步插入即可完成排序。圖5-29表示直接插入的處理過程。5.5.2簡單選擇排序簡單選擇排序是選擇排序的一種。該排序十分簡單。首先從所有待排序記錄選出關(guān)鍵碼最小的記錄，將其與第1個記錄交換，然后在其余未排序的記錄中選出關(guān)鍵碼最小的記錄，將其與第2個記錄交換位置。如此反復(fù)進(jìn)行，直到全部記錄排完序?yàn)橹?。圖5-30給出這種排序方法的示例。5.5.3冒泡排序冒泡排序是交換排序的一種。該排序方法是:從底部開始,反復(fù)地從下向上比較相鄰的數(shù)據(jù),如果a[i]<a[i-1],則交換,既小的數(shù)據(jù)向上浮。第一遍比較后，最小的數(shù)據(jù)浮到最上面。第二遍繼續(xù)從下向上逐個比較，將次最小的浮到a[2]的位置。如此反復(fù)進(jìn)行直到所有數(shù)據(jù)均排好序?yàn)橹埂D5-31給出了冒泡排序示例。5.6檢索檢索又稱查找，是從一大堆數(shù)據(jù)中按某種方式找出所需內(nèi)容的過程。檢索是數(shù)據(jù)處理中常用的一種重要運(yùn)算。檢索的結(jié)果有兩種可能：檢索失敗，就是在數(shù)據(jù)結(jié)構(gòu)中不存在滿足條件的結(jié)點(diǎn)；檢索成功，就是在數(shù)據(jù)結(jié)構(gòu)中找到了滿足條件的結(jié)點(diǎn)。在日常生活中，查找信息是人們一項(xiàng)非常頻繁且重要的活動。例如，在通訊錄中查找某個人的電話號碼和地址，或在字典中查找某個詞的讀音和詞義。在信息時代，我們將大量的信息存儲在計算機(jī)系統(tǒng)中，如何快速、準(zhǔn)確的查找到我們需要的數(shù)據(jù)也是非常重要的。在計算機(jī)檢索過程中，我們使用的數(shù)據(jù)結(jié)構(gòu)稱為查找表。所謂查找表，就是同一類型的數(shù)據(jù)(或記錄)組成的集合。下面介紹幾種常用的檢索方法。5.6.1順序檢索這是一種最簡單的檢索方法。檢索時用待查的關(guān)鍵碼與給定數(shù)據(jù)結(jié)構(gòu)中各結(jié)點(diǎn)的關(guān)鍵碼依次比較，直到找出相應(yīng)的結(jié)點(diǎn)則檢索成功，或找遍所有結(jié)點(diǎn)都沒有相應(yīng)的結(jié)點(diǎn)則檢索失敗。順序檢索時存儲表示可以是順序的，也可以是鏈?zhǔn)降?，對查找表中結(jié)點(diǎn)之間沒有排序的要求。例如，已知一組由10個數(shù)據(jù)元素組成的查找表為： (13，41，23，15，19，33，28，06，55，37)現(xiàn)在要用順序檢索法查找關(guān)鍵字為33和66的數(shù)據(jù)元素。根據(jù)順序檢索方法，第一步取出查找表中的第一個元素13與關(guān)鍵字33做比較，得到的結(jié)果為不相等，第二步，順序地取第二個元素41與關(guān)鍵字33比較，……，以此類推，直到取到第六個元素33，它與關(guān)鍵字相同，然后輸出結(jié)果為：6，即目標(biāo)關(guān)鍵字在查找表的位置為6。5.6.1順序檢索關(guān)鍵字33的順序查找過程如圖5-32所示。5.6.1順序檢索順序檢索關(guān)鍵字66的過程和檢索33的方法完全一致。但是我們會發(fā)現(xiàn)順序比較之后，查找表中不能找到與關(guān)鍵字66相同的數(shù)據(jù)，此時遍歷的指針應(yīng)該是指向查找表中最后一個數(shù)據(jù)之后的位置。這個值并不是一個特殊值，它會根據(jù)查找表中元素個數(shù)的不同而不同，而且如果要區(qū)分出這個返回值是指關(guān)鍵字所在的位置，或是指關(guān)鍵字不存在，還需要與查找表中數(shù)據(jù)元素的個數(shù)做比較。因此，改進(jìn)的算法在順序檢索遍歷開始時，會設(shè)置一個“哨兵”位置，即位于第一個元素之前的0號位置，如果遍歷完查找表之后不能找到與關(guān)鍵字匹配的元素，則返回值為0，這樣對于數(shù)據(jù)個數(shù)不同的查找表，如果返回值為0就意味著檢索失敗。5.6.1順序檢索關(guān)鍵字66的順序查找過程如圖5-33所示。5.6.2二分法檢索采用二分法檢索(折半查找)，要求查找表中的結(jié)點(diǎn)按關(guān)鍵碼值的大小排序，并且要求采用順序存儲表示。二分檢索時，先用待檢索的關(guān)鍵碼值與數(shù)據(jù)結(jié)構(gòu)中間位置的結(jié)點(diǎn)的關(guān)鍵碼比較，若相等則檢索成功，返回結(jié)點(diǎn)的位置序號；若不相等，則根據(jù)比較結(jié)果確定下一步檢索是在左子表中進(jìn)行，還是在右子表中進(jìn)行。直到檢索成功或檢索失敗為止。5.6.2二分法檢索例如，已知一組由10個數(shù)據(jù)元素組成的查找表為： (13，41，23，15，19，33，28，06，55，37)用二分法檢索關(guān)鍵字為33和66的數(shù)據(jù)元素。首先，要將查找表進(jìn)行排序，如由小到大排序?yàn)?06，13，15，19，23，28，33，37，41，55)。然后，確定查找表的中間位置，一般的方法為

其中l(wèi)ow為待查范圍的下界，high為上界，mid為中間位置。本例中，low和high的初值分別為1和10，。之后，比較第五個元素23與33的大小關(guān)系，因?yàn)?3<33則選擇查找表的右半部分作為下一步的待查范圍，即

，同理如果mid對應(yīng)的元素比33大，則選擇查找表的左半部分作為下一步的待查范圍，而

。以此類推直到找到匹配元素或查找區(qū)間的大小小于0(查找不成功)。5.6.2二分法檢索圖5-33關(guān)鍵字33二分法檢索過程5.6.2二分法檢索圖5-34關(guān)鍵字66二分法檢索過程5.6.2二分法檢索通過對順序查找和二分法檢索過程的分析，我們可以直觀的看到，順序查找具有一定的盲目性，如果關(guān)鍵字恰好是第一個元素，那么查找活動只需要一步就可以完成，而如果關(guān)鍵字不存在則需要遍歷整個查找表。而二分法在查找過程中，每次都可以使查找范圍去除一半的元素，直觀上查找效率是要高于順序查找的。但二分法查找只適用于查找表有序的情況，所以當(dāng)查找表元素過多時排序可能就需要消耗大量的時間。當(dāng)然在具體分析各種查找方法的性能時，需要考慮該查找算法在查找成功時的平均查找長度，所謂平均查找長度是指在確定記錄在查找表中的位置，需要和關(guān)鍵字進(jìn)行比較的次數(shù)的期望值。在后續(xù)的數(shù)據(jù)結(jié)構(gòu)的課程中會詳細(xì)分析各種檢索方法的性能，在這里就不再做深入討論。5.6.3分塊檢索分塊檢索又稱索引順序查找，是順序查找的一種改進(jìn)方法，也可以理解為二分法的一種擴(kuò)展。分塊檢索要求把查找表分成若干塊，在每一塊中結(jié)點(diǎn)的存放是任意的，但塊與塊之間必須是有序的。如果按遞增次序排列，則第一塊中所有結(jié)點(diǎn)的關(guān)鍵碼值均小于第二塊中所有結(jié)點(diǎn)的關(guān)鍵碼值，第二塊中所有結(jié)點(diǎn)的關(guān)鍵碼值均小于第三塊所有結(jié)點(diǎn)的關(guān)鍵碼值，依此類推。根據(jù)各個塊之間的關(guān)鍵字大小和起始位置建立“索引表”。在查找過程中，首先根據(jù)索引表確定關(guān)鍵字所在的塊，然后在選定的塊中根據(jù)順序查找的原則進(jìn)行查找。5.6.2二分法檢索例如，已知一組由10個數(shù)據(jù)元素組成的查找表為： (13，41，23，15，19，33，28，06，55，37)用分塊檢索法查找關(guān)鍵字為33和66的數(shù)據(jù)元素。首先對現(xiàn)有的數(shù)據(jù)元素按照從小到大的順序進(jìn)行分塊(三塊)，并建立索引表。如圖5-35所示。當(dāng)數(shù)據(jù)元素根據(jù)大小不同而需要進(jìn)行位置調(diào)整時，可以參考本章第五節(jié)中所提供的排序算法進(jìn)行操作。5.6.3分塊檢索然后，比較待查關(guān)鍵字與各個索引塊中最大關(guān)鍵字的大小順序，以確定待查關(guān)鍵字可能的位置，本例中因?yàn)?8<33<55，所以可以判定33處于第三塊中。之后，在第三塊中按照順序查找的方法進(jìn)行查找，這里就不再詳述。而對于關(guān)鍵字66>55(查找表中最后一塊的最大關(guān)鍵字)，所以可以直接判定它不在查找表中，即查找失敗。雖然分塊查找需要對查找表進(jìn)行建立索引表的預(yù)處理，但當(dāng)索引表建好之后，每次查找時，分塊查找明顯地提高了順序查找的效率，也不像二分法查找要求全部元素都有序，算法比較簡單，應(yīng)用也很廣泛。5.6.4散列表檢索散列表既是一種存儲表示，也是一種檢索方法。散列法又稱關(guān)鍵碼—地址轉(zhuǎn)換法(也稱哈希法)。散列表的基本思路是：以關(guān)鍵碼的值為自變量，通過某種函數(shù)關(guān)系運(yùn)算后直接確定結(jié)點(diǎn)相應(yīng)的存儲地址，將該結(jié)點(diǎn)存入計算得到的存儲單元里。檢索時根據(jù)待檢索的關(guān)鍵碼值，通過上述同樣的函數(shù)關(guān)系運(yùn)算后得到地址，再到相應(yīng)存儲單元里去取結(jié)點(diǎn)。其中，使用的函數(shù)稱為散列函數(shù)(哈希函數(shù))，用散列法存儲的線性表稱為散列表。在理想的情況下，查找表中的數(shù)據(jù)通過哈希函數(shù)對應(yīng)到一個存儲地址，在查找時待查關(guān)鍵字通過哈希函數(shù)運(yùn)算后直接取對應(yīng)地址的元素即可，否則，如果對應(yīng)位置元素為空則表明查找失敗。5.6.4散列表檢索在進(jìn)行散列表檢索時有兩個難點(diǎn)要處理，一是構(gòu)造哈希函數(shù)的方法，二是處理沖突的方法。構(gòu)造哈希函數(shù)的目的是要將查找表中的關(guān)鍵字盡可能均勻地散列到存儲空間中。所謂均勻，是指每一個關(guān)鍵字經(jīng)過哈希函數(shù)處理后映射到存儲空間的任一地址的概率是相等的。也就是說要，通過哈希函數(shù)給每個關(guān)鍵字賦予一個“隨機(jī)地址”，而且是他們均勻的分配到整個地址區(qū)域中，以節(jié)省空間并減少沖突。所謂沖突，是指不同的關(guān)鍵字通過哈希函數(shù)處理得到相同的地址的現(xiàn)象。5.6.4散列表檢索在一般情況下，我們很難同時兼顧節(jié)省查找時間和存儲空間的需求，并完全避免沖突。由于查找表的數(shù)據(jù)信息可能非常龐大，如果我們選擇太過復(fù)雜的哈希函數(shù)，那么在構(gòu)造散列表是耗費(fèi)大量是時間，而且如果要完全避免沖突，我們可能需要浪費(fèi)大量的存儲空間。比如，查找表中的數(shù)據(jù)是4000個0~9999的整數(shù)數(shù)據(jù)，且沒有重復(fù)。最簡單的哈希函數(shù)，就是開辟10000個存儲單元，將關(guān)鍵字存在它自己對應(yīng)的序數(shù)單元中，但這樣就會浪費(fèi)掉6000個單元的存儲空間。因此如何權(quán)衡這種關(guān)系，還需要針對具體情況進(jìn)行分析和設(shè)計。常用的哈希函數(shù)構(gòu)造方法有：直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法和隨機(jī)數(shù)法等。常用的處理沖突方法有：開放定址法、再哈希法、鏈地址法和建立一個公共溢出區(qū)等。在后續(xù)的數(shù)據(jù)結(jié)構(gòu)課程中，我們會詳細(xì)的討論這些常用的哈希函數(shù)構(gòu)造方法和解決沖突的方法，并分析他們的特點(diǎn)，在此就不再詳述。5.6.4散列表檢索下面我們再以這組由10個數(shù)據(jù)元素組成的查找表為例： (13，41