數據結構

——基本概念及線性數據結構基本概念1．數據（data）

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

2．數據元素（dataelement）

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

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

與時間復雜度類似，空間復雜度是指算法在計算機內執行時所占用的內存開銷規模。線性數據結構

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

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

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

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

西安交通大學計算機教學實驗中心趙英良12線性數據結構：循環隊列西安交通大學計算機教學實驗中心趙英良13將隊空和對滿的條件加以區分:

隊空條件:

front=rear

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

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

a1a2an∧帶頭結點的單鏈表帶頭結點單鏈表的邏輯結構西安交通大學計算機教學實驗中心趙英良16head38數據域指針域38229486

a2

86…

…

94…

…

a3

NULL

a1

22

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

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

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

在單鏈表中插入結點x

pai-1

xai

sp.next=s③ai-1

ai

px

s②s.next=p.nextai-1

ai

px

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

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

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

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

22查找基本概念靜態查找表:查找表一旦建立，在以后的查找過程中就不會改變。它所對應的查找算法屬于靜態查找技術。動態查找表：查找表建立后，在后來的查找過程中仍會改變查找表的內容。它所對應的查找算法屬于動態查找技術。

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

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

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

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

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

2．折半查找(也稱二分查找)西安交通大學計算機教學實驗中心28對給定有序數列{5，6，11，17，21，23，28，30，32，40}進行半查找算法，查找關鍵字值為30的數據元素。則查找過程如下：第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排序基本概念

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

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

30排序基本概念

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

西安交通大學計算機教學實驗中心32初始狀態：[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]直接插入排序執行過程在序列{35，22，16，19，22}上應用插入排序的過程，為了對序列中相同記錄加以區別，使用了下劃線。

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

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

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

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

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

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

當22的位置已經確定后，只需對{19，16}和{27,45,35,22}分別排序即可?？煞謩e取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精勤求學敦篤勵志果毅力行忠恕任事西安交通大學計算機教學實驗中心趙英良非線性數據結構

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

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

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

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

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

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

?。喉旤cx到y的一條單向通路，則稱為弧，用<x,y>表示。?

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

頂點的度：一個頂點v的度是與它相關聯的邊的條數。圖的基本概念西安交通大學計算機教學實驗中心50?無向圖：若圖是由一些頂點和邊構成則稱之為無向圖。?

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

權：某些圖的邊或弧具有與它相關的數，稱之為權。這種帶權圖叫做網絡。0132528130123410234(a)無向圖

(b)有向圖

(c)網絡

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