1、數據結構常璐璐 計算機科學技術系數據結構課程地位數據結構課程地位 教材內容劃分：教材內容劃分：l第一部分：第一部分：數據結構的基本概念（第數據結構的基本概念（第1章）章）l第二部分：第二部分：基本的數據結構基本的數據結構 包括：線性包括：線性結構結構線性表、棧和隊列、串、數組與廣義表線性表、棧和隊列、串、數組與廣義表 （第（第25章）章） 非線性結構非線性結構樹、圖（第樹、圖（第6、7章）章）l第三部分：第三部分：基本技術基本技術 包括：查找技術與排序包括：查找技術與排序技術（第技術（第8、9、10章）章）1.1 數據結構討論的范疇數據結構討論的范疇1.2 基本概念基本概念1.3 算法和算法的

2、量度算法和算法的量度第一章第一章1.11.1 數據結構討論的范疇數據結構討論的范疇尼克萊斯尼克萊斯沃思（沃思（NiklausWirth） ： Algorithm + Data Structures = Programs程序設計程序設計: :算法算法: 數據結構數據結構: 為計算機處理問題編制 一組指令集 處理問題的策略處理問題的策略問題的數學模型問題的數學模型非數值計算的程序設計問題例一例一: 求一組(n個)整數整數中的最大值算法: ? ?模型：？基本操作是“比較兩個數的大小比較兩個數的大小”取決于整數值的范圍整數值的范圍例二：例二：計算機對弈算法：?模型：?對弈的規則和策略棋盤及棋盤的格局例

3、三：例三：足協的數據庫管理算法：?模型：?需要管理的項目？如何管理？ 用戶界面？各種表格概括地說：概括地說： 數據結構是一門討論數據結構是一門討論“描述現描述現實世界實體的數學模型實世界實體的數學模型( (非數值計非數值計算算) )及其上的操作在計算機中如何及其上的操作在計算機中如何表示和實現表示和實現”的學科。的學科。1.2 基本概念基本概念一、數據與數據結構一、數據與數據結構二、數據類型二、數據類型三、抽象數據類型三、抽象數據類型一、數據與數據結構一、數據與數據結構所有能被輸入被輸入到計算機中，且能被計算機處理的符號處理的符號的集合。數據數據: :是計算機操作的對象計算機操作的對象的總稱。

4、是計算機處理的信息的信息的某種特定的符號表示形式表示形式。是數據（集合）中的一個“個體個體”數據元素數據元素: :是數據結構中討論的基本基本單位 數據項：數據項：是數據結構中討論的最小最小單位一個數據元素可以由若干個數據項組成一個數據元素可以由若干個數據項組成例如：描述一個運動員的數據元素可以是年年 月月 日日姓姓名名俱俱樂樂部部名名稱稱出出生生日日期期參參加加日日期期職職務務業業績績稱之為組合項稱之為組合項數據結構：數據結構：帶結構結構的數據元素的集合假設用三個三個 4 位的十進制數位的十進制數表示一個含 12 位位數的十進制數。數的十進制數。3214,6587,9345 a1(3214),

5、a2(6587),a3(9345)則在數據元素 a1、a2 和 a3 之間存在著“次序次序”關系關系 a1,a2 、 a2,a3 3214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3例如例如: :又例，在2行3列的二維數組a1, a2, a3, a4, a5, a6中六個元素之間存在兩個關系: a1 a2 a3 a4 a5 a6行的次序關系行的次序關系:列的次序關系列的次序關系: :row = ,col = , a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6數據結構：數據結構： 帶結構結構的數據元素的集合再例，在一維數組 a1,

6、a2, a3, a4, a5, a6 的數據元素之間存在如下的次序關系次序關系:| i=1, 2, 3, 4, 5 或者說，數據結構數據結構是相互之間存在著某相互之間存在著某種種邏輯關系邏輯關系的數據元素的集合的數據元素的集合。數據結構：數據結構： 帶結構結構的數據元素的集合可見，不同的“關系關系”構成不同的“結構結構”數據的邏輯結構邏輯結構可歸結為以下四類四類: :線性線性結構樹形樹形結構圖狀圖狀結構集合集合結構數據結構的形式定義數據結構的形式定義為:數據結構數據結構是一個二元組 Data_Structures = (D, S)其中:D 是數據元素的有限集數據元素的有限集， S 是 D上關系

7、的有限集關系的有限集。例1 復數的二元組定義 復數由實部和虛部構成（構成元素），兩者之間存在著一種次序關系（邏輯關系）。 可以表示為： Complex=(C,R) 其中,C= c1,c2 R=說明:表示有序數對,用圖示法表示時畫箭頭 ( )表示無序數對,用圖示法表示時畫線段 例2 設有數據邏輯結構為: B=(K,R) K=k1,k2,k3,k4,k5,k6,k7,k8,k9 R=,畫出這個結構的圖示.k1k2k3k4k5k6k7k8k9網狀結構網狀結構(有向圖有向圖)數據的存儲結構存儲結構 邏輯結構在存儲器中的表示(映象映象) )“數據元素”的映象 ？“關系”的映象 ？數據元素的映象方法：數據

8、元素的映象方法：用二進制位(bit)的位串表示數據元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2關系的映象方法：關系的映象方法：（表示x, y的方法）順序映象順序映象以相對的存儲位置表示后繼關系以相對的存儲位置表示后繼關系例如例如: :存儲復數存儲復數 z=3.0-2.3i z=3.0-2.3i 用順序結構，內存存儲情況為:20012002200320043.0-2.3鏈式映象鏈式映象以附加信息以附加信息( (指針指針) )表示后繼關系表示后繼關系20012002200320043.0203620362037-2.3在不同

9、的編程環境中，存儲結構可有不同的描述方法。當用高級程序設計語言進行編程時，通常可用高級編程語言中提供的數據類型描述之。二、數據類型二、數據類型在用高級程序語言編寫的程序中，必須對程序中出現的每個變量、常量或表達式，明確說明明確說明它們所屬的數據類型數據類型。 不同類型的變量，其所能取的值的范圍值的范圍不同，所能進行的操作進行的操作不同。例如，C 語言中提供的基本數據類型基本數據類型有:整型整型 int浮點型浮點型 float字符型字符型 char空類型空類型 void雙精度型雙精度型 double實型（實型（ C+語言）語言）三、抽象數據類型三、抽象數據類型 (Abstract Data Ty

10、pe 簡稱簡稱ADT)例如，例如，抽象數據類型復數復數的定義： 數據對象：數據對象： De1,e2e1,e2RealSet 數據關系：數據關系： R1 | e1是復數的實數部分 | e2 是復數的虛數部分 ADT Complex 基本操作：基本操作： AssignComplex( &Z, v1, v2 )操作結果：構造復數 Z,其實部和虛部 分別被賦以參數 v1 和 v2 的值。 DestroyComplex( &Z)操作結果：復數Z被銷毀。 GetReal( Z, &realPart )初始條件：復數已存在。操作結果：用realPart返回復數Z的實部值。 GetIm

11、ag( Z, &ImagPart )初始條件：復數已存在。操作結果：用ImagPart返回復數Z的虛部值。 Add( z1,z2, &sum )初始條件：z1, z2是復數。操作結果：用sum返回兩個復數z1, z2 的 和值。 ADT Complex假設:z1和z2是上述定義的復數則 Add(z1, z2, z3) 操作的結果z3 = z1 + z2即為用戶企求的結果ADT 有兩個重要特征:數據抽象數據抽象 用ADT描述程序處理的實體時，強調的是其本質的特征本質的特征、其所能完成的其所能完成的功能功能以及它和外部用戶的接口外部用戶的接口（即外界外界使用它的方法使用它的方法）。

12、數據封裝數據封裝 將實體的外部特性和其內部外部特性和其內部實現細節分離實現細節分離，并且對外部用戶隱藏對外部用戶隱藏其內部實現細節。其內部實現細節。抽象數據類型的描述方法抽象數據類型的描述方法抽象數據類型可用（D，S，P）三元組表示。其中：D 是數據對象； S 是 D 上的關系集； P 是對 D 的基本操作集。 ADT 抽象數據類型名抽象數據類型名 數據對象：數據對象：數據對象的定義 數據關系：數據關系：數據關系的定義 基本操作：基本操作：基本操作的定義 ADT 抽象數據類型名其中基本操作的定義格式為:基本操作名基本操作名（參數表） 初始條件：初始條件：初始條件描述 操作結果操作結果：操作結果

13、描述 賦值參數賦值參數 只為操作提供輸入值。引用參數引用參數 以&打頭，除可提供輸入值外，還將返回操作結果。初始條件初始條件 描述了操作執行之前數據結構和參數應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。操作結果操作結果 說明了操作正常完成之后，數據結構的變化狀況和應返回的結果。若初始條件為空，則省略之。抽象數據類型的表示和實現抽象數據類型的表示和實現 抽象數據類型需要通過固有數據固有數據類型類型(高級編程語言中已實現的數據類型)來實現。例如，對以上定義的復數。typedef struct float realpart； float imagpart；complex；/ -存

14、儲結構的定義存儲結構的定義/ -基本操作的函數原型說明基本操作的函數原型說明void Assign( complex &Z, float realval, float imagval )；/ 構造復數 Z,其實部和虛部分別被賦以參數 / realval 和 imagval 的值float GetReal( cpmplex Z )； / 返回復數 Z 的實部值float Getimag( cpmplex Z )； / 返回復數 Z 的虛部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回兩個復數 z1, z2

15、 的和 / -基本操作的實現基本操作的實現void add( complex z1, complex z2, complex &sum ) / 以 sum 返回兩個復數 z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 其它省略 1.3 1.3 算法和算法的衡量算法和算法的衡量一、算法一、算法二、算法設計的原則二、算法設計的原則三、算法效率的衡量方法和準則三、算法效率的衡量方法和準則四、算法的存儲空間需求四、算法的存儲空間需求 算法算法是為了解決某類

16、問題而規定的一個有限長的操作序列操作序列。一個算法必須滿足以下五五個重要特性特性：1 1有窮性有窮性 2 2確定性確定性 3 3可行性可行性4 4有輸入有輸入 5 5有輸出有輸出一、算法一、算法1 1有窮性有窮性 對于任意一組合法輸入值，在執行有窮步驟有窮步驟之后一定能結束，即：算法中的每個步驟都能在有限時間有限時間內完成。 2 2確定性確定性 對于每種情況每種情況下所應執行的操作，在算法中都有確切確切的規定，使算法的執行者或閱讀者都能明確其含義及如何執行。并且并且在任何條件下，算法都只有一在任何條件下，算法都只有一條執行路徑。條執行路徑。3 3可行性可行性 算法中的所有操作都必須足夠基本，都

17、可以通過已經實現的基本操作運算有限次實現之。4 4有輸入有輸入 作為算法加工對象的量值，通常體現為算法中的一組變量。有些輸入量需要在算法執行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中。 5 5有輸出有輸出 它是一組與“輸入”有確定關系的量值，是算法進行信息加工后得到的結果，這種確定關系即為算法的功能。二、算法設計的原則二、算法設計的原則設計算法時，通常應考慮達到以下目標：1正確性正確性2. . 可讀性可讀性3健壯性健壯性4高效率與低存儲量需求高效率與低存儲量需求1 1正確性正確性 首先，首先，算法應當滿足滿足以特定的“規格說明規格說明”方式給出的需求需求。其次，其次，對算

18、法是否“正確正確”的的理解可以有以下四個層次四個層次：a a程序中不含語法錯誤；b b程序對于幾組輸入數據能夠得出滿足要求的結果； c c程序對于精心選擇的、典型、苛刻且帶有刁程序對于精心選擇的、典型、苛刻且帶有刁難性的幾組輸入數據能夠得出滿足要求的結果難性的幾組輸入數據能夠得出滿足要求的結果； d d程序對于一切合法的輸入數據都能得出滿足要求的結果；2. . 可讀性可讀性 算法主要是為了人的閱讀與交流閱讀與交流，其次才是為計算機執行，因此算法應該易易于于人的理解理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調試。3健壯性健壯性 當輸入的數據非法非法時，算法應當恰當地作出反映或進行相應處

19、理進行相應處理，而不是產生莫名奇妙的輸出結果。并且，處理出處理出錯的方法錯的方法不應是中斷程序的執行，而應是返回返回一個表示錯誤或錯誤性質的值表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。4.高效率與低存儲量需求高效率與低存儲量需求通常，效率指的是算法執行時間；存儲量指的是算法執行過程中所需的最大存儲空間，兩者都與問題的規模有關。三、算法效率的衡量方法和準則三、算法效率的衡量方法和準則通常有兩種兩種衡量算法效率的方法: 事后統計法事后統計法事前分析估算法事前分析估算法缺點：缺點：1必須執行程序 2其它因素掩蓋算法本質和算法執行時間時間相關的因素因素：1 1算法算法選用的策略的策略2

20、2問題的規模問題的規模3 3編寫程序的語言語言4 4編譯編譯程序產生的機器代碼的質量的質量5 5計算機計算機執行指令的速度的速度 算法的時間復雜度算法的時間復雜度l算法中包含簡單操作的次數，在計算機上所運行的時間算法中包含簡單操作的次數，在計算機上所運行的時間l語句頻度：語句重復執行的次數語句頻度：語句重復執行的次數 所有語句頻度之和記做所有語句頻度之和記做T (n)，它是該算法所求解的問，它是該算法所求解的問題規模題規模n的函數。的函數。當當n- 時時，T(n)的數量級稱為漸近時的數量級稱為漸近時間復雜度，簡稱時間復雜度。記做：間復雜度，簡稱時間復雜度。記做：T(n)=O(f(n) 我們總是

21、考慮在最壞情況下的時間復雜度，以保證算我們總是考慮在最壞情況下的時間復雜度，以保證算法的運行時間不會比它更長（最壞情況下估算算法執行時法的運行時間不會比它更長（最壞情況下估算算法執行時間的一個上界）間的一個上界） 一個特定算法的一個特定算法的“運行工作量運行工作量”的大小，只依賴于的大小，只依賴于問問題的規模題的規模（通常用整數量（通常用整數量n表示），或者說，它是表示），或者說，它是問題規問題規模的函數模的函數。與待處理數據的初態無關。與待處理數據的初態無關。 一個特定算法的算法的“運行工作量運行工作量”的大小，只依賴于問題的規模（通常用整數量n表示），或者說，它是問題規模的函數是問題規模的函數。 假如，隨著問題規模 n 的增長，算法執行時間的增長率和算法執行時間的增長率和 f(n) 的增長的增長率相同率相同，則可記作：T (n) = O(f(n)稱稱T (n) 為算法的為算法的(漸近)