軟件開(kāi)發(fā)技術(shù)基礎(chǔ) 第4版 課件 第2章 數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用

數(shù)據(jù)結(jié)構(gòu)

——基本概念及線性數(shù)據(jù)結(jié)構(gòu)基本概念1．?dāng)?shù)據(jù)（data）

數(shù)據(jù)是指能夠輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)識(shí)別和處理的符號(hào)的集合。

2．?dāng)?shù)據(jù)元素（dataelement）

數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。數(shù)據(jù)元素是一個(gè)數(shù)據(jù)整體中相對(duì)獨(dú)立的單位。但它還可以分割成若干個(gè)具有不同屬性的項(xiàng)（字段），故不是組成數(shù)據(jù)的最小單位西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良2基本概念3．?dāng)?shù)據(jù)結(jié)構(gòu)

是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合。數(shù)據(jù)結(jié)構(gòu)包含三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存貯結(jié)構(gòu)對(duì)數(shù)據(jù)所施加的運(yùn)算。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良3基本概念3．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良4線性結(jié)構(gòu)——通迅錄、成績(jī)單、花名冊(cè)樹(shù)形結(jié)構(gòu)——電子字典、家譜、目錄圖狀結(jié)構(gòu)——交通線路、通信網(wǎng)絡(luò)基本概念3．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良5(1)順序存貯所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存仍然相鄰。(2)鏈?zhǔn)酱尜A所有元素存放在可以不連續(xù)的存貯單元中，元素之間的關(guān)系通過(guò)地址確定，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存后不一定是相鄰的。(3)索引存貯（略） (4)散列存貯（略）基本概念3．算法分析西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良61）時(shí)間復(fù)雜度一個(gè)算法中的時(shí)間復(fù)雜度一般用語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)來(lái)衡量。數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素個(gè)數(shù)n稱為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)，語(yǔ)句的執(zhí)行次數(shù)也會(huì)變化2）空間復(fù)雜度

與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所占用的內(nèi)存開(kāi)銷規(guī)模。線性數(shù)據(jù)結(jié)構(gòu)

線性表是由有限個(gè)同類型的數(shù)據(jù)元素組成的有序序列，一般記作（a1,a2,…,an）。除了a1和an之外，任意元素ai都有一個(gè)直接前趨ai-1和一個(gè)直接后繼ai+1。a1無(wú)前趨，an無(wú)后繼。線性表的存儲(chǔ)結(jié)構(gòu)主要有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良7線性數(shù)據(jù)結(jié)構(gòu)：順序表采用順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲(chǔ)單元中。邏輯上相鄰的數(shù)據(jù)元素，其存儲(chǔ)位置也彼此相鄰。假定元素a1的物理地址是Loc(a1)，每個(gè)元素占d個(gè)存儲(chǔ)單元，則第i個(gè)元素的存儲(chǔ)位置為：Loc(ai)=Loc(a1)+(i-1)*d

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良8順序表主要算法判定線性表是否為空求線性表的長(zhǎng)度在表中第i個(gè)位置插入新元素x

在表中刪除第i個(gè)元素在表中查找某個(gè)元素西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良9線性數(shù)據(jù)結(jié)構(gòu)：棧棧是限制在表的一端進(jìn)行插入和刪除操作的線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良10a1a3a2進(jìn)棧出棧top線性數(shù)據(jù)結(jié)構(gòu)：棧的主要操作創(chuàng)建空棧。進(jìn)棧(push)操作:在棧頂插入元素。出棧(pop)操作:在棧頂刪除元素。讀棧頂元素:只是讀出棧頂元素，并不改變棧內(nèi)元素。

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良11線性數(shù)據(jù)結(jié)構(gòu)：循環(huán)隊(duì)列隊(duì)列是只能在表的一端進(jìn)行插入、在另一端進(jìn)行刪除操作的線性表。允許刪除元素的一端稱為隊(duì)頭，允許插入元素的一端稱為隊(duì)尾。解決隊(duì)列假溢出的辦法是將存放隊(duì)列元素的數(shù)組首尾相接，形成循環(huán)隊(duì)列。循環(huán)隊(duì)列的基本操作方式為：入隊(duì)列時(shí)先執(zhí)行rear=(rear+1)%M，再將新元素在rear指示位置加入；出隊(duì)列時(shí)先執(zhí)行front=(front+1)%M，再將下標(biāo)為front的元素取出。

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良12線性數(shù)據(jù)結(jié)構(gòu)：循環(huán)隊(duì)列西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良13將隊(duì)空和對(duì)滿的條件加以區(qū)分:

隊(duì)空條件:

front=rear

隊(duì)滿條件:(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE

(a)循環(huán)隊(duì)列空(b)非空循環(huán)隊(duì)列(c)循環(huán)隊(duì)列滿線性數(shù)據(jù)結(jié)構(gòu)：?jiǎn)捂湵砦靼步煌ù髮W(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良14單鏈表用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。由于邏輯上相鄰的元素其物理位置不一定相鄰，為了建立元素間的邏輯關(guān)系，需要在線性表的每個(gè)元素中附加其后繼元素的地址信息。這種地址信息稱為指針。附加了其他元素指針的數(shù)據(jù)元素稱為結(jié)點(diǎn)。帶頭結(jié)點(diǎn)單鏈表的邏輯結(jié)構(gòu)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良15為了能順次訪問(wèn)每個(gè)結(jié)點(diǎn)，需要保存單鏈表第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。這個(gè)地址稱為線性表的頭指針，本節(jié)用head表示。為了操作上的方便，可以在單鏈表的頭部增加一個(gè)特殊的頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的類型與其他結(jié)點(diǎn)一樣，只是頭結(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?。head

a1a2an∧帶頭結(jié)點(diǎn)的單鏈表帶頭結(jié)點(diǎn)單鏈表的邏輯結(jié)構(gòu)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良16head38數(shù)據(jù)域指針域38229486

a2

86…

…

94…

…

a3

NULL

a1

22

存儲(chǔ)地址單鏈表存儲(chǔ)結(jié)構(gòu)示意圖單鏈表中指針移動(dòng)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良17圖2單鏈表指針后移一步ai2167ai+17650ai-192579257p=p.next2167pp

圖1帶頭結(jié)點(diǎn)的空鏈表head∧∧單鏈表插入結(jié)點(diǎn)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良18(a)第1步,生成結(jié)點(diǎn)s(b)第2步，s結(jié)點(diǎn)指向結(jié)點(diǎn)ai

(c)第3步，結(jié)點(diǎn)ai-1指向s結(jié)點(diǎn)圖3

在單鏈表中插入結(jié)點(diǎn)x

pai-1

xai

sp.next=s③ai-1

ai

px

s②s.next=p.nextai-1

ai

px

s①單鏈表刪除結(jié)點(diǎn)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良19刪除第i個(gè)結(jié)點(diǎn)，需進(jìn)行如下操作：

①若第i個(gè)結(jié)點(diǎn)存在則找到第i和第i-1個(gè)結(jié)點(diǎn)的指針p和q②通過(guò)語(yǔ)句q.next=p.next將第i-1個(gè)結(jié)點(diǎn)的指針域賦值為第i+1個(gè)結(jié)點(diǎn)的指針，將第i個(gè)結(jié)點(diǎn)從鏈表中斷開(kāi)。③釋放第i個(gè)結(jié)點(diǎn)所占空間以便于重用。qpai-1aiai+1q.next=p.next

20精勤求學(xué)敦篤勵(lì)志果毅力行忠恕任事西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良查找和排序查找基本概念查找表:

由同一類數(shù)據(jù)構(gòu)成的用于查找的集合稱作查找表。查找表是具有一定存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)集合，比如順序表結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、樹(shù)形結(jié)構(gòu)等。查找往往根據(jù)數(shù)據(jù)元素的某個(gè)屬性進(jìn)行。例如根據(jù)學(xué)號(hào)查找某個(gè)學(xué)生記錄。這種被用于查找的元素屬性一般稱為關(guān)鍵字，它往往可以唯一標(biāo)識(shí)一個(gè)元素。

22查找基本概念靜態(tài)查找表:查找表一旦建立，在以后的查找過(guò)程中就不會(huì)改變。它所對(duì)應(yīng)的查找算法屬于靜態(tài)查找技術(shù)。動(dòng)態(tài)查找表：查找表建立后，在后來(lái)的查找過(guò)程中仍會(huì)改變查找表的內(nèi)容。它所對(duì)應(yīng)的查找算法屬于動(dòng)態(tài)查找技術(shù)。

23查找基本概念平均查找長(zhǎng)度：

為了確定數(shù)據(jù)元素在查找表中的位置，需要將給定值和表中的數(shù)據(jù)元素的關(guān)鍵字進(jìn)行比較的次數(shù)的期望值。平均查找長(zhǎng)度ASL的計(jì)算方法為：24其中：在等概率條件下（

Pi=1/n）這時(shí)平均查找長(zhǎng)度為：1．順序查找順序查找的方法是從表的一端開(kāi)始，逐一比較給定的數(shù)據(jù)key和表中數(shù)據(jù)元素的關(guān)鍵字x的值，若兩個(gè)數(shù)據(jù)一致則查找成功，同時(shí)給出該數(shù)據(jù)元素在表中的位置，否則查找失敗。25順序表查找的平均查找長(zhǎng)度為：2．折半查找(也稱二分查找)26假定元素按關(guān)鍵字的值升序排列，折半查找的思路是將給定的數(shù)據(jù)與有序表中間位置的元素做比較，若兩者相等則查找成功；若前者小于后者則在中間位置左邊的元素中繼續(xù)查找；若前者大于后者則在中間位置右邊的元素中繼續(xù)查找。不斷重復(fù)這一過(guò)程直到查找成功，或者直到查找區(qū)間縮小為一個(gè)元素時(shí)卻仍未找到目標(biāo)，則查找失敗。

2．折半查找(也稱二分查找)27折半查找算法的步驟描述如下：①設(shè)置查找區(qū)間初值，設(shè)下界low=0，設(shè)上界high=length-1②若low≤high則計(jì)算中間位置mid=(low+high)/2③若key<data[mid]，則設(shè)high=mid-1并繼續(xù)執(zhí)行步驟②；若key>data[mid]，則設(shè)low=mid+1并繼續(xù)執(zhí)行步驟②；若key=data[mid]則查找成功，返回目標(biāo)元素位置mid+1

（位置從1計(jì)數(shù)）。④若當(dāng)low=high時(shí)，key!=data[mid]則查找失敗，返回0。

2．折半查找(也稱二分查找)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心28對(duì)給定有序數(shù)列{5，6，11，17，21，23，28，30，32，40}進(jìn)行半查找算法，查找關(guān)鍵字值為30的數(shù)據(jù)元素。則查找過(guò)程如下：第1次：{5，6，11，17，21，23，28，30，32，40}

low=0mid=(0+9)/2=4high=9第2次：{5，6，11，17，21，23，28，30，32，40}

low=5mid=7high=9排序基本概念

排序的定義為：假設(shè)含n個(gè)記錄的序列為{R1，R2，…，Rn}，其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}。這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系Kp1≤Kp2≤…≤Kpn，按此固有關(guān)系將最初的記錄序列重新排列為{Rp1,Rp2,…，Rpn}的操作稱作排序。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心29排序基本概念

排序分為內(nèi)部排序和外部排序。若整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成，則稱此類排序問(wèn)題為內(nèi)部排序；反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過(guò)程不可能在內(nèi)存中完成，則稱此類排序問(wèn)題為外部排序。本節(jié)只討論內(nèi)部排序的若干方法

30排序基本概念

內(nèi)部排序方法有很多類型。按方法實(shí)現(xiàn)特點(diǎn)可分為插入排序、選擇排序、交換排序、歸并排序等等；按方法效率可分為簡(jiǎn)單的排序法、先進(jìn)的排序法等等。簡(jiǎn)單的排序法包括插入排序、選擇排序、冒泡排序等，它們的時(shí)間復(fù)雜度為O(n2)。而先進(jìn)的排序法包括快速排序、歸并排序等，它們的時(shí)間復(fù)雜度大約為O(nlog2n)。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心311、直接插入排序

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心32初始狀態(tài)：[35] 22 16 19 22第1趟：[22 35] 16 19 22第2趟：[16 22 35] 19 22第3趟：[16 19 22 35] 22第4趟：[16 19 22 22 35]直接插入排序執(zhí)行過(guò)程在序列{35，22，16，19，22}上應(yīng)用插入排序的過(guò)程，為了對(duì)序列中相同記錄加以區(qū)別，使用了下劃線。

2、簡(jiǎn)單選擇排序西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心33在序列{35，22，16，19，22}上應(yīng)用簡(jiǎn)單選擇排序的過(guò)程。

初始狀態(tài)：[35 22 16 19 22]

第1趟：[16] [22 35 19 22]

第2趟：[16 19] [35 22 22]

第3趟：[16 19 22]

[35 22]

第4趟：[16 19 22 22] [35]3、冒泡排序西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心34基本思路：第一趟排序?qū)θ坑涗汻1，R2，…，Rn自左向右順次兩兩比較，若Rk大于Rk+1則交換Rk和Rk+1(k=1,2,…,n-1)，第一趟排序完成后Rn成為序列中最大記錄。第二趟排序?qū)π蛄星皀-1個(gè)記錄采用同樣的比較和交換方法，第二趟排序完成后Rn-1成為序列中僅比Rn小的次大的記錄。第三趟排序?qū)π蛄星皀-2個(gè)記錄采用同樣處理方法。如此做下去，最多做n-1趟排序，整個(gè)序列就排序完成。3、冒泡排序西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心35

下圖顯示了在序列{35，22，16，19，22}上應(yīng)用冒泡排序的過(guò)程。

初始狀態(tài)：3522 16 19 [22

第1趟：2216 19 22 [35]

第2趟：1619 22 [22

[35]

第3趟：1619 [22

22 [35]

第4趟：16[19

22 22 [35]4、快速排序西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心36任取待排序序列中某個(gè)記錄S(例如第一個(gè)記錄)作為基準(zhǔn)，經(jīng)過(guò)比較和交換，將整個(gè)序列劃分為如下形式：{左側(cè)子序列}S{右側(cè)子序列}并且滿足：

①左側(cè)子序列中所有記錄的關(guān)鍵字都小于或等于S的關(guān)鍵字。②右側(cè)子序列中所有記錄的關(guān)鍵字都大于或等于S的關(guān)鍵字。然后分別對(duì)左右兩個(gè)子序列重復(fù)執(zhí)行上述過(guò)程，直到排序完成4、快速排序西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心37

在{22,35,27,16,45,19,22}上應(yīng)用劃分算法（即一趟快速排序）4、快速排序西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心38

當(dāng)22的位置已經(jīng)確定后，只需對(duì){19，16}和{27,45,35,22}分別排序即可?？煞謩e取19和27為基準(zhǔn)元素。

{22，35，27，16，45，19，22}

{19，16}22{27，45，35，22}

{16}19

22{22}27{35，45}

1619222227

35{45}

39精勤求學(xué)敦篤勵(lì)志果毅力行忠恕任事西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良非線性數(shù)據(jù)結(jié)構(gòu)

—樹(shù)與圖樹(shù)的遞歸定義樹(shù)是由n個(gè)具有相同特性的數(shù)據(jù)元素組成的集合。若n=0，則稱其為空樹(shù)。一棵非空樹(shù)T必須滿足：1）其中有一個(gè)特定的元素稱為T的根root。2）除根以外的集合可劃分為m個(gè)不相交子集T1，T2，…，Tm，其中每個(gè)子集都是樹(shù)。它們稱為根root的子樹(shù)。

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心41GACFDEB樹(shù)的一般形式與樹(shù)相關(guān)的術(shù)語(yǔ)結(jié)點(diǎn)：在樹(shù)結(jié)構(gòu)中一般把數(shù)據(jù)元素及其若干指向子樹(shù)的分支稱為結(jié)點(diǎn)。結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的非空子樹(shù)的個(gè)數(shù)。樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值。葉子結(jié)點(diǎn)：沒(méi)有非空子樹(shù)的結(jié)點(diǎn)。分支結(jié)點(diǎn)：至少有一個(gè)非空子樹(shù)的結(jié)點(diǎn)。孩子結(jié)點(diǎn)和父結(jié)點(diǎn)：某結(jié)點(diǎn)所有子樹(shù)的根結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)，同時(shí)該結(jié)點(diǎn)也稱為其孩子結(jié)點(diǎn)的父結(jié)點(diǎn)。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心42與樹(shù)相關(guān)的術(shù)語(yǔ)兄弟結(jié)點(diǎn)：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)。結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層次為1,其子結(jié)點(diǎn)的層次為2。依次類推，子結(jié)點(diǎn)的層次總比父結(jié)點(diǎn)多一層。樹(shù)的深度：樹(shù)中結(jié)點(diǎn)所在的最大層次。有序樹(shù)和無(wú)序樹(shù)：將樹(shù)中各結(jié)點(diǎn)的子樹(shù)看成自左向右有序的，則稱該樹(shù)為有序樹(shù)。否則稱為無(wú)序樹(shù)。森林：由零棵或有限棵互不相交的樹(shù)組成的集合。

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心43二叉樹(shù)的定義二叉樹(shù)可以是空樹(shù)，當(dāng)二叉樹(shù)非空時(shí)，其中有一個(gè)根元素，余下的元素組成兩個(gè)互不相交二叉樹(shù)，分別稱為根的左子樹(shù)和右子樹(shù)。二叉樹(shù)是有序樹(shù)，也就是說(shuō)任意結(jié)點(diǎn)的左、右子樹(shù)不可交換。而一般樹(shù)的子樹(shù)間是無(wú)序的。特殊形式的二叉樹(shù)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心44AFC滿二叉樹(shù)GDBEAC完全二叉樹(shù)DBE二叉樹(shù)有下列重要性質(zhì)在二叉樹(shù)的第k層上至多有2k-1個(gè)結(jié)點(diǎn)(k≥1)深度為h的二叉樹(shù)上至多含2h-1個(gè)結(jié)點(diǎn)(h≥1)包含n(n>0)個(gè)結(jié)點(diǎn)的二叉樹(shù)總的分支數(shù)為n-1任何一棵二叉樹(shù)，若含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式n0=n2+1具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2(n)]+1西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心45二叉樹(shù)有下列重要性質(zhì)6.若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下、從左至右進(jìn)行1至n的編號(hào)，則對(duì)二叉樹(shù)中任意一個(gè)編號(hào)為i的結(jié)點(diǎn)：①若i=1，則該結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)父結(jié)點(diǎn)。否則，編號(hào)為[i/2]的結(jié)點(diǎn)為其父結(jié)點(diǎn)；②若2i>n，則該結(jié)點(diǎn)無(wú)左孩子。否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；③若2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子。否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心46二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心47二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)ABC∧∧D∧∧E∧∧利用結(jié)點(diǎn)形式存儲(chǔ)的樹(shù)稱為二叉鏈表。從根結(jié)點(diǎn)出發(fā)，可以訪問(wèn)二叉樹(shù)的任何結(jié)點(diǎn)。為了能夠訪問(wèn)二叉樹(shù)，必須保留指向根結(jié)點(diǎn)的指針。這和單鏈表必須保留頭指針的道理一樣。

二叉樹(shù)的遍歷西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心48三種主要的遍歷算法——先序遍歷、中序遍歷和后序遍歷。

1）先序遍歷：首先訪問(wèn)根結(jié)點(diǎn)，然后按先序遍歷方式訪問(wèn)左子樹(shù)，最后按先序遍歷方式訪問(wèn)右子樹(shù)。2）中序遍歷：首先按中序遍歷方式訪問(wèn)左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后按中序遍歷方式訪問(wèn)右子樹(shù)。3）后序遍歷：首先按后序遍歷方式訪問(wèn)左子樹(shù)，然后按后序遍歷方式訪問(wèn)右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。圖的基本概念西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心49圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。一般記作Graph＝(V,E)。其中V是頂點(diǎn)的有限非空集合；E是頂點(diǎn)之間關(guān)系的有限集合。?

邊：頂點(diǎn)x到y(tǒng)的一條雙向通路，稱為邊，用(x,y)表示。?

弧：頂點(diǎn)x到y(tǒng)的一條單向通路，則稱為弧，用<x,y>表示。?

鄰接點(diǎn)：如果(x,y)是圖中的一條邊，則稱x與y互為鄰接點(diǎn)；如果<x,y>是圖中的一條弧，則稱y為x的鄰接點(diǎn)。?

頂點(diǎn)的度：一個(gè)頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。圖的基本概念西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心50?無(wú)向圖：若圖是由一些頂點(diǎn)和邊構(gòu)成則稱之為無(wú)向圖。?

有向圖：若圖是由一些頂點(diǎn)和弧構(gòu)成則稱之為有向圖。?

權(quán)：某些圖的邊或弧具有與它相關(guān)的數(shù)，稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。0132528130123410234(a)無(wú)向圖

(b)有向圖

(c)網(wǎng)絡(luò)

圖的基本概念西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心51?路徑：在圖中，若從頂點(diǎn)vi出發(fā)，沿一些邊或弧，經(jīng)過(guò)頂點(diǎn)vp1、vp2、…、vpm到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vi，vp1，…，vpm，vj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。若路徑上各頂點(diǎn)均不互相重復(fù)，則稱這樣的路徑為簡(jiǎn)單路徑。?路徑長(zhǎng)度：非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊或弧的條數(shù)，帶權(quán)圖的路徑長(zhǎng)度