大學(xué)計算機基礎(chǔ)-第7章 數(shù)據(jù)結(jié)構(gòu)課件

第7章數(shù)據(jù)結(jié)構(gòu)7.1數(shù)據(jù)結(jié)構(gòu)概念及定義7.2線性表7.3棧和隊列7.4樹7.5排序7.6查找技術(shù)數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運算。棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運算。線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。二級大綱之二--------數(shù)據(jù)結(jié)構(gòu)線性表的基本知識（定義、結(jié)構(gòu)）棧和隊列的基本知識（定義、結(jié)構(gòu)）樹的基本概念（定義、相關(guān)術(shù)語）二叉樹（定義、性質(zhì)、遍歷）常用排序算法與二分查找法的時間復(fù)雜度本章重點內(nèi)容7.1.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)（data）-------是指能夠輸入到計算機中，并能被計算機存儲、識別和處理的符號集合。數(shù)據(jù)結(jié)構(gòu)（DataStructure）-------研究數(shù)據(jù)的特性以及數(shù)據(jù)之間存在的關(guān)系；是計算機存儲、組織數(shù)據(jù)的方式。如：學(xué)生之間、同事之間總會存在一定的聯(lián)系。什么是數(shù)據(jù)結(jié)構(gòu)?邏輯結(jié)構(gòu)------如何表示這些數(shù)據(jù)元素的關(guān)系（與計算機無關(guān)）存儲結(jié)構(gòu)------怎樣在計算機中存儲數(shù)據(jù)元素運算------對每種邏輯結(jié)構(gòu)進行相應(yīng)的處理7.1.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容7.1.2數(shù)據(jù)元素和數(shù)據(jù)項數(shù)據(jù)元素（DataElement）------是數(shù)據(jù)的基本單位，具有完整明確的實際意義，也稱元素、節(jié)點、頂點、記錄。數(shù)據(jù)項（DataItem）------是組成數(shù)據(jù)元素的最小單位，也稱為字段或域。如：學(xué)生通訊錄中，一個學(xué)生是一個數(shù)據(jù)元素，而姓名、電話號碼、住址等是數(shù)據(jù)元素的3個數(shù)據(jù)項。數(shù)據(jù)元素和數(shù)據(jù)項7.1.3數(shù)據(jù)對象和數(shù)據(jù)類型數(shù)據(jù)對象（DataObject）------是性質(zhì)相同的數(shù)據(jù)元素組成的集合，是數(shù)據(jù)的一個子集。如：整數(shù)對象集、實數(shù)對象集。數(shù)據(jù)類型（DataType）------是一個值的集合與在這些值上定義的一組操作的總稱。如：整型、字符型、邏輯型數(shù)據(jù)對象和數(shù)據(jù)類型7.4.5數(shù)據(jù)的存儲結(jié)構(gòu)

什么是數(shù)據(jù)的存儲結(jié)構(gòu)?定義:數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示和實現(xiàn)，故又稱數(shù)據(jù)的“物理結(jié)構(gòu)”。存儲結(jié)構(gòu)包含的內(nèi)容數(shù)據(jù)結(jié)構(gòu)舉例學(xué)號姓名語文數(shù)學(xué)化學(xué)平均成績2010001向恩立829083852010002趙軍928599922010003劉冰80757978….….…..….….…..邏輯結(jié)構(gòu)：用二維表表示數(shù)據(jù)間的關(guān)系。表中的每一行是一個數(shù)據(jù)元素（或記錄、結(jié)點），它由學(xué)號、姓名、各科成績及平均成績等數(shù)據(jù)項組成。7.1.6數(shù)據(jù)結(jié)構(gòu)的定義7.1.7線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)

數(shù)據(jù)元素有唯一前趨和唯一后繼（第一個沒有前趨，最后一個沒有后繼。如：1對1是線性結(jié)構(gòu)非線性結(jié)構(gòu)

非線性結(jié)構(gòu)的其它數(shù)據(jù)結(jié)構(gòu)。如：1對多(樹）、多對多（圖）、無關(guān)系（集合）非線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的分類（分為兩大類）7.2線性表

7.2.1線性表的基本概念7.2.2線性表的邏輯結(jié)構(gòu)特征7.2.3線性表的順序存儲結(jié)構(gòu)7.2.4線性表的基本運算7.2.5線性表的鏈式存儲7.2.6基本運算在鏈表上的實現(xiàn)7.2.7其它鏈表7.2線性表

定義：

線性表是n（n≥1）個數(shù)據(jù)元素a1，a2，…，an組成的有限序列，其數(shù)據(jù)元素按“一個接一個排列”的方式進行組織。其中n稱為數(shù)據(jù)元素的個數(shù)或線性表的長度，當(dāng)n=0時稱為空表，n>0時稱為非空表。舉例（2，4，6，8，10）是一個線性表，數(shù)據(jù)元素類型是整型，數(shù)據(jù)元素的取值為偶數(shù)；（A，B，C，D，E，F(xiàn)）也是一個線性表，數(shù)據(jù)元素類型是字符型，數(shù)據(jù)元素的取值為大寫英文字母；什么是線性表？7.2.2線性表的邏輯結(jié)構(gòu)特點

有且僅有一個開始元素a1，沒有直接前驅(qū)，僅只有一個直接后繼a1；有且僅有一個終端元素an，沒有直接后繼，僅只有一個直接前驅(qū)an-1；其他元素ai（2≤i≤n?1）都有且僅有一個直接前驅(qū)ai?1和一個直接后繼ai+1；邏輯結(jié)構(gòu)主要特點7.2.3線性表的順序存儲結(jié)構(gòu)

定義：把線性表的數(shù)據(jù)元素按邏輯次序依次存放在一組地址連續(xù)的存儲單元中，用這種方法存儲的線性表簡稱為順序表。存儲特點：所有元素結(jié)點的存儲空間是連續(xù)的。數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。什么是順序存儲結(jié)構(gòu)？7.2.4線性表的基本運算

舉例：一個長度為8的線性表順序存儲在長度為10的存儲空間中，現(xiàn)在要求刪除線性表中的第1個元素和第7個元素，如圖所示。線性表的順序存儲優(yōu)缺點結(jié)構(gòu)比較簡單，適合小線性表（元素少）或者其中元素不常變動的線性表。對于大的線性表，特別是元素變動頻繁的大線性表不宜采用順序存儲結(jié)構(gòu)，因為插入與刪除的效率比較低。7.2.4線性表的基本運算Data為數(shù)據(jù)域，用來存放元素本身的信息，類型由具體問題而定；Next為指針域，用來存放下一個結(jié)點的地址，即存儲一個指針，該指針指向本元素的直接后繼元素所在的結(jié)點。DataNext7.2.5線性表的鏈式存儲

在單鏈表中結(jié)點的結(jié)構(gòu)描述7.2.6鏈表的基本運算

鏈表的插入運算方法：該算法要求先找到第i?1個結(jié)點，故其時間頻度為n，時間復(fù)雜度為O(n)。但在插入元素時不需移動元素，只需修改指針即可。

7.2.7其他鏈表將單鏈表最后一個結(jié)點的指針改為指向鏈表中的頭結(jié)點，就使得整個鏈表構(gòu)成一個環(huán)，又沒有增加額外的存儲空間，這種鏈表被稱為單循環(huán)鏈表。循環(huán)鏈表7.3棧和隊列

7.3.1棧的定義7.3.2隊列7.3.1棧的定義

定義：-------棧（Stack）又叫堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算，這一端被稱為棧頂，相對地，把另一端稱為棧底。什么是棧？棧的基本運算入棧運算出棧運算讀棧頂元素【例7.9】對于一個棧，給出輸入項a,b,c。如果輸入項序列由a,b,c組成，則可能產(chǎn)生的序列有哪些？7.3.1棧的定義

7.3.2隊列

定義：也是一種受限的線性表。若限定線性表的插入只能在表尾位置進行，而刪除只能在表頭進行，則稱這種線性表為隊列。什么是隊列？與棧不同的是，隊列是先進先出（FirstInFirstOut，F(xiàn)IFO）的線性表，而棧是后進先出（LastInFirstOut，LIFO）的線性表。隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)也用一維數(shù)組來模擬實現(xiàn)。隊列的插入在隊尾進行，刪除卻在隊頭進行，所以，必須由兩個變量分別記錄隊頭、隊尾在數(shù)組中的位置，分別稱為隊頭指針和隊尾指針。

空順序隊列

非空順序隊列

7.3.2隊列

隊列的基本運算出隊操作：即刪除隊列的隊頭元素。入隊操作：在隊列的隊尾插入結(jié)點，將Rear指針加1，將數(shù)據(jù)存入Rear指針指向的位置。7.3.2隊列

7.4樹7.4.1樹的定義與相關(guān)術(shù)語7.4.2二叉樹的定義與基本操作7.4.3二叉樹的性質(zhì)7.4.4二叉樹的存儲結(jié)構(gòu)7.4.5二叉樹的遍歷7.4.1樹的定義與相關(guān)術(shù)語樹是n(n≥0)個結(jié)點的有限集合T。當(dāng)n=0時，稱為空樹；當(dāng)n＞0時，該集合滿足如下條件：其中必有一個稱為根（Root）的特定結(jié)點，它沒有直接前驅(qū)，但有零個或多個直接后繼。其余n-1個結(jié)點可以劃分成m（m>0）個互不相交的有限集T1，T2，T3，…Tm，其中Ti又是一棵樹，稱為根（Root）的子樹。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但有零個或多個直接后繼。什么是樹？樹的相關(guān)術(shù)語結(jié)點：包含一個數(shù)據(jù)元素及若干指向其他結(jié)點的分支信息。結(jié)點的度：一個結(jié)點的子樹的個數(shù)稱為此結(jié)點的度。葉子結(jié)點：無后繼的結(jié)點，即度為0的結(jié)點，也稱為終端結(jié)點。樹結(jié)構(gòu)如右圖所示：7.4.1樹的定義與相關(guān)術(shù)語樹的相關(guān)術(shù)語樹的度：樹中所有結(jié)點的度的最大值。孩子結(jié)點：一個結(jié)點的直接后繼稱為該結(jié)點的孩子結(jié)點。在圖中，B、C、D是A的孩子結(jié)點。雙親結(jié)點：一個結(jié)點的直接前驅(qū)稱為該結(jié)點的雙親結(jié)點。在圖中，A是B、C、D的雙親結(jié)點。兄弟結(jié)點：同一雙親結(jié)點的孩子結(jié)點之間互稱兄弟結(jié)點。在圖中，B、C、D互為兄弟結(jié)點。結(jié)點的層次：從根結(jié)點開始定義，根結(jié)點的層次為l，根的直接后繼的層次為2，依此類推。7.4.1樹的定義與相關(guān)術(shù)語樹的相關(guān)術(shù)語樹的深度：樹中所有結(jié)點的層次的最大值。在圖中，樹的深度為4。祖先結(jié)點：一個結(jié)點的祖先結(jié)點是指從根結(jié)點到該結(jié)點的路徑上的所有結(jié)點。在圖中，L的祖先結(jié)點是E、B、A。子孫結(jié)點：一個結(jié)點的直接后繼和間接后繼稱為該結(jié)點的子孫結(jié)點。在圖，B結(jié)點的子孫結(jié)點是E、F、K、L。7.4.1樹的定義與相關(guān)術(shù)語樹的相關(guān)術(shù)語有序樹：在樹T中，如果各子樹Ti之間是有先后次序的，則稱為有序樹。森林：m(m＞0)棵互不相交的樹的集合。將一棵非空樹的根結(jié)點刪去，樹就變成一個森林；反之，給森林增加一個統(tǒng)一的根結(jié)點，森林就變成一棵樹。7.4.1樹的定義與相關(guān)術(shù)語7.4.2二叉樹的定義與基本操作

滿足以下兩個條件的樹形結(jié)構(gòu)叫做二叉樹。每個結(jié)點的度都不大于2。有序樹每個結(jié)點的孩子結(jié)點次序不能任意顛倒二叉樹是有序樹。什么是二叉樹？二叉樹的基本操作將BinaryTree初始化為空二叉樹創(chuàng)建一棵非空二叉樹BinaryTree銷毀二叉樹BinaryTree判斷二叉樹是否為空求根結(jié)點求雙親求左孩子求右孩子遍歷操作：按某個次序依次訪問二叉樹中每個結(jié)點一次且僅一次。7.4.2二叉樹的定義與基本操作

7.4.3二叉樹的性質(zhì)

性質(zhì)1：在二叉樹的第i層上結(jié)點數(shù)最多為2i?1。性質(zhì)2：深度為k的二叉樹至多有2k?1個結(jié)點（k≥1）。性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。二叉樹的重要性質(zhì)（五個)2134589111067121314(b)完全二叉樹滿二叉樹定義：深度為k且有2k?1個結(jié)點的二叉樹。在滿二叉樹中，每層結(jié)點都是滿的，即每層結(jié)點都具有最大結(jié)點數(shù)（2i-1)。如圖所示的二叉樹即為一棵滿二叉樹。7.4.3二叉樹的性質(zhì)

定義：深度為k，結(jié)點數(shù)為n的二叉樹，如果其結(jié)點1…n的位置序號分別與滿二叉樹的結(jié)點1…n的位置序號一一對應(yīng)，則為完全二叉樹。如右圖所示即為滿二叉樹。7.4.3二叉樹的性質(zhì)

完全二叉樹性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為性質(zhì)5：對于具有n個結(jié)點的完全二叉樹，如果按照從上到下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從1開始順序編號，則對于任意的序號為i的結(jié)點有”如i=1，則序號為i的結(jié)點是根結(jié)點，無雙親結(jié)點；如i>1，則序號為i的結(jié)點的雙親結(jié)點序號為:如2*i＞n，則序號為i的結(jié)點無左孩子；如2*i≤n，則序號為i的結(jié)點的左孩子結(jié)點的序號為2*i。如2*i+1＞n，則序號為i的結(jié)點無右孩子；如2*i+1≤n，則序號為i的結(jié)點的右孩子結(jié)點的序號為2*i+1。

。7.4.3二叉樹的性質(zhì)

二叉樹的重要性質(zhì)（五個)7.4.4二叉樹的存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)順序存儲結(jié)構(gòu):是用一組連續(xù)的存儲單元來存放二叉樹的數(shù)據(jù)元素。如圖所示：二叉樹的兩種存儲結(jié)構(gòu)7.4.4二叉樹的存儲結(jié)構(gòu)

鏈式存儲結(jié)構(gòu)如圖所示

二叉樹的兩種存儲結(jié)構(gòu)7.4.5二叉樹的遍歷

定義：“遍歷”的含義是對結(jié)構(gòu)中的每個數(shù)據(jù)元素都訪問一次且僅僅訪問一次。方法：確定一條搜索路徑，使得結(jié)構(gòu)中的每個數(shù)據(jù)元素都出現(xiàn)在這條搜索路徑上，才能確保每個數(shù)據(jù)元素都被訪問到。什么是二叉樹的遍歷？二叉樹的三種遍歷方法先序遍歷（DLR）操作過程若二叉樹為空，則空操作，否則依次執(zhí)行如下3個操作。訪問根結(jié)點。按先序遍歷左子樹。按先序遍歷右子樹。7.4.5二叉樹的遍歷

二叉樹的三種遍歷方法中序遍歷（LDR）操作過程若二叉樹為空，則空操作，否則依次執(zhí)行如下3個操作。按中序遍歷左子樹訪問根結(jié)點按中序遍歷右子樹7.4.5二叉樹的遍歷

二叉樹的三種遍歷方法后序遍歷（LRD）操作過程若二叉樹為空，則空操作，否則依次執(zhí)行如下3個操作。按后序遍歷左子樹按后序遍歷右子樹訪問根結(jié)點7.4.5二叉樹的遍歷

7.5排序

7.5.1排序的基本概念7.5.2排序方法7.5.3插入類排序7.5.4選擇類排序7.5.5交換類排序7.5.1排序的基本概念排序（Sorting）是數(shù)據(jù)處理領(lǐng)域中經(jīng)常使用的一種重要運算，分為內(nèi)、外排序。文件放在內(nèi)存處理的，稱為“內(nèi)排序”；排序過程中不僅使用內(nèi)存，還使用外存，稱為“外排序”。本節(jié)著重介紹內(nèi)排序算法如果待排序的記錄集合中有多個排序碼相同的記錄，經(jīng)過排序后這些記錄的相對次序仍保持不變，這種排序算法稱為“穩(wěn)定”的，否則稱為“不穩(wěn)定”的。排序的基本概念7.5.2排序的方法

插入類排序：直接插入排序，二分法插入排序，希爾排序。選擇類排序：直接選擇排序，堆排序。交換類排序：起泡排序，快速排序。分配類排序：基數(shù)排序。歸并類排序。排序方法的分類（五類）排序算法的評價時間復(fù)雜度--------時間復(fù)雜度是指算法執(zhí)行所需要的時間，取決于算法中執(zhí)行數(shù)據(jù)比較的次數(shù)和移動的次數(shù)?？臻g復(fù)雜度---------空間復(fù)雜度是指算法執(zhí)行所需要的附加空間的大小。7.5.2排序的方法

7.5.3插入排序基本思想：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n?1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表。直接插入排序的空間復(fù)雜度：只需要一個元素的輔助空間，用于元素的位置交換。直接插入排序的時間復(fù)雜度：因此，直接插入排序的時間復(fù)雜度為O（n2）。直接插入排序基本思想：在插入Ri時（這時R1，R2，…，Ri?1已為有序表），可以不斷二分有序表來確定插入位置，通過待插入記錄與有序表居中的記錄按排序碼比較，將有序表一分為二，下次比較在其中一個有序子表中進行，將子表又一分為二。這樣繼續(xù)下去，直到要比較的子表中只有一個記錄時，比較一次便確定了插入位置。空間復(fù)雜度：只需要一個元素的輔助空間，用于元素的位置交換。時間復(fù)雜度：確定插入位置所進行的折半查找，關(guān)鍵碼的比較次數(shù)至多為log2(n+1)」次，移動記錄的次數(shù)和直接插入排序相同，故時間復(fù)雜度仍為O(n2)。7.5.3插入排序二分法插入排序7.5.3插入排序基本思想：先選定一個整數(shù)增量d1<n，把全部記錄分成若干個組，所有記錄距離為d1倍數(shù)的記錄放在同一個組，在各組內(nèi)進行排序，然后取d2<d1，重復(fù)上述分組和排序過程，直到di=1，即所有記錄放在一組中排序結(jié)束。各組內(nèi)排序可采用直接插入排序?？臻g復(fù)雜度：只需要一個元素的輔助空間，用于元素的位置交換。時間復(fù)雜度：希爾排序時效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動次數(shù)依賴于步長因子序列的選取，特定情況下可以準確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動次數(shù)。希爾插入排序7.5.4選擇排序

基本思想：第一趟，從n個記錄中找出關(guān)鍵碼最小的記錄與第一個記錄交換；第二趟，從第二個記錄開始的n-1個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；如此，第i趟，則從第i個記錄開始的n-i+1個記錄中選出關(guān)鍵碼最小的記錄與第i個記錄交換，直到整個序列按關(guān)鍵碼有序?？臻g復(fù)雜度：只需要一個元素的輔助空間，用于元素的位置交換。時間復(fù)雜度：簡單選擇排序移動記錄的次數(shù)較少，但關(guān)鍵碼的比較次數(shù)依然是n(n+1)，所以時間復(fù)雜度仍為O(n2)。簡單選擇排序的7.5.5交換類排序基本思想：對含有n個記錄的表，從第一個排序碼開始將兩兩相鄰的一對記錄排序碼進行比較，如果它們的次序不對，就交換它們的位置，直到得到一個排序碼最大的記錄，并將它放到r[n]；第二趟冒泡對前面n?1個記錄的表，再得到一個關(guān)鍵碼最大的記錄，將它放到r[n?1]；如此執(zhí)行n?1趟，得到n個記錄的有序表?？臻g復(fù)雜度：只需要一個元素的輔助空間，用于元素的位置交換。時間復(fù)雜度：冒泡排序算法的時間復(fù)雜度為O(n2)。

冒泡排序7.5.5交換類排序

基本思想是通過比較關(guān)鍵碼、交換記錄，以某個記錄為界（該記錄稱為支點），將待排序列分成兩部分。其中，一部分所有記錄的關(guān)鍵碼大于等于支點記錄的關(guān)鍵碼，另一部分所有記錄的關(guān)鍵碼小于支點記錄的關(guān)鍵碼。我們將待排序列按關(guān)鍵碼以支點記錄分成兩部分的過程，稱為一次劃分。對各部分不斷劃分，直到整個序列按關(guān)鍵碼有序。空間復(fù)雜度：快速排序是遞歸的。存儲開銷在理想情況下為O(log2n)，即樹的高度；在最壞情況下，即二叉樹是一個單鏈，為O(n)。時間復(fù)雜度：在n個記錄的待排序列中，一次劃分需要約n次關(guān)鍵碼比較，時效為O(n)，若設(shè)T(n)為對n個記錄的待排序列進行快速排序所需時間?？焖倥判?.6查找技術(shù)7.6