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

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

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

2．數(shù)據(jù)元素（dataelement）

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

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

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

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

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

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

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

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

隊空條件:

front=rear

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

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

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

a2

86…

…

94…

…

a3

NULL

a1

22

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

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

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

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

pai-1

xai

sp.next=s③ai-1

ai

px

s②s.next=p.nextai-1

ai

px

s①單鏈表刪除結(jié)點西安交通大學(xué)計算機教學(xué)實驗中心趙英良19刪除第i個結(jié)點，需進行如下操作：

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

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

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

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

23查找基本概念平均查找長度：

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

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

2．折半查找(也稱二分查找)27折半查找算法的步驟描述如下：①設(shè)置查找區(qū)間初值，設(shè)下界low=0，設(shè)上界high=length-1②若low≤high則計算中間位置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]則查找成功，返回目標元素位置mid+1

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

2．折半查找(也稱二分查找)西安交通大學(xué)計算機教學(xué)實驗中心28對給定有序數(shù)列{5，6，11，17，21，23，28，30，32，40}進行半查找算法，查找關(guān)鍵字值為30的數(shù)據(jù)元素。則查找過程如下：第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個記錄的序列為{R1，R2，…，Rn}，其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}。這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系Kp1≤Kp2≤…≤Kpn，按此固有關(guān)系將最初的記錄序列重新排列為{Rp1,Rp2,…，Rpn}的操作稱作排序。西安交通大學(xué)計算機教學(xué)實驗中心29排序基本概念

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

30排序基本概念

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

西安交通大學(xué)計算機教學(xué)實驗中心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í)行過程在序列{35，22，16，19，22}上應(yīng)用插入排序的過程，為了對序列中相同記錄加以區(qū)別，使用了下劃線。

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

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

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

初始狀態(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é)計算機教學(xué)實驗中心36任取待排序序列中某個記錄S(例如第一個記錄)作為基準，經(jīng)過比較和交換，將整個序列劃分為如下形式：{左側(cè)子序列}S{右側(cè)子序列}并且滿足：

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

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

當22的位置已經(jīng)確定后，只需對{19，16}和{27,45,35,22}分別排序即可。可分別取19和27為基準元素。

{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é)敦篤勵志果毅力行忠恕任事西安交通大學(xué)計算機教學(xué)實驗中心趙英良非線性數(shù)據(jù)結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

(b)有向圖

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

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