數(shù)據(jù)結(jié)構(gòu)(C語言版)第1章

1、2第1章 緒 論學(xué)習(xí)目標(biāo)與要求：了解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)類型及抽象數(shù)據(jù)類型等基本概念。掌握數(shù)據(jù)結(jié)構(gòu)和算法的概念。掌握數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)操作(運算)3個方面的概念及其相互之間的關(guān)系。掌握算法的評價標(biāo)準(zhǔn)。分析算法的時間復(fù)雜度，評價一個算法的好壞。31.1 引 言1968年美國唐年美國唐歐歐克努特克努特(Donald E.Knuth)開開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系。創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系。 數(shù)據(jù)結(jié)構(gòu)是一門介于數(shù)學(xué)、計算機硬件和計算數(shù)據(jù)結(jié)構(gòu)是一門介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的核心課程機軟件三者之間的核心課程(如圖如圖1.1所示所示)。 數(shù)學(xué) 代數(shù)系統(tǒng) 編譯理論

2、 存儲裝置 硬件(計算機系統(tǒng)設(shè)計) 算子關(guān)系 數(shù)據(jù) 類型 數(shù)據(jù)表示法 數(shù)據(jù)的操作 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)存取 機器組織 文件系統(tǒng) 數(shù)據(jù)組織 信息檢索 軟件(計算機程序設(shè)計) 41.1 引 言為了使讀者對數(shù)據(jù)結(jié)構(gòu)有一個感性的認識，為了使讀者對數(shù)據(jù)結(jié)構(gòu)有一個感性的認識，下面給出幾個數(shù)據(jù)結(jié)構(gòu)的示例，讀者可以下面給出幾個數(shù)據(jù)結(jié)構(gòu)的示例，讀者可以通過這些示例去理解數(shù)據(jù)結(jié)構(gòu)的概念。通過這些示例去理解數(shù)據(jù)結(jié)構(gòu)的概念?！臼纠?】 職工基本情況表。參見教材P2【示例2】 井字棋對弈問題?！臼纠?】 教學(xué)計劃編排問題。51.2 基本概念與術(shù)語數(shù)據(jù)數(shù)據(jù)(Data)是對客觀事物的一種符號表示，是指所有能輸入到是對客觀事物的一

3、種符號表示，是指所有能輸入到計算機中并被計算機程序加工處理的符號的總稱。計算機中并被計算機程序加工處理的符號的總稱。 數(shù)據(jù)元素數(shù)據(jù)元素(Data Element)是組成數(shù)據(jù)的基本單位，在計算機程是組成數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。序中通常作為一個整體進行考慮和處理。 數(shù)據(jù)項數(shù)據(jù)項(Data Item)是數(shù)據(jù)不可分割的、具有獨立意義的最小數(shù)是數(shù)據(jù)不可分割的、具有獨立意義的最小數(shù)據(jù)單位，是對數(shù)據(jù)元素屬性的描述。據(jù)單位，是對數(shù)據(jù)元素屬性的描述。 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項反映了數(shù)據(jù)組織的數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項反映了數(shù)據(jù)組織的3個層次，即數(shù)據(jù)個層次，即數(shù)據(jù)可以由若干個數(shù)據(jù)元

4、素組成，數(shù)據(jù)元素又由若干個數(shù)據(jù)項組成?？梢杂扇舾蓚€數(shù)據(jù)元素組成，數(shù)據(jù)元素又由若干個數(shù)據(jù)項組成。數(shù)據(jù)對象數(shù)據(jù)對象(Data Object)是性質(zhì)相同的數(shù)據(jù)元素的集合。是性質(zhì)相同的數(shù)據(jù)元素的集合。 數(shù)據(jù)類型數(shù)據(jù)類型(Data Type)是指一組結(jié)構(gòu)相同的值構(gòu)成的值集是指一組結(jié)構(gòu)相同的值構(gòu)成的值集(類型類型)和定義在這個值集和定義在這個值集(類型類型)上的操作集。上的操作集。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(Data Structure)是指數(shù)據(jù)元素之間的邏輯關(guān)系和這是指數(shù)據(jù)元素之間的邏輯關(guān)系和這種關(guān)系在計算機中的存儲表示，以及在這種結(jié)構(gòu)上定義的運算。種關(guān)系在計算機中的存儲表示，以及在這種結(jié)構(gòu)上定義的運算。 61

5、.2 基本概念與術(shù)語1. 邏輯結(jié)構(gòu) (1)線性結(jié)構(gòu)。 (2)集合結(jié)構(gòu)。 (3)樹形結(jié)構(gòu)。 (4)圖狀結(jié)構(gòu)。數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)如圖1.4所示。 71.2 基本概念與術(shù)語2. 存儲結(jié)構(gòu)(1) 順序存儲結(jié)構(gòu)是指把邏輯上相鄰的結(jié)點存儲在物理上相鄰的存儲單元里，結(jié)點之間的邏輯關(guān)系由存儲單元位置的鄰接關(guān)系來體現(xiàn)。 (2) 鏈?zhǔn)酱鎯Y(jié)構(gòu)是把邏輯上相鄰的結(jié)點存儲在物理上任意的存儲單元里，結(jié)點之間的邏輯關(guān)系由附加的指針域來體現(xiàn)。 (3) 索引存儲結(jié)構(gòu)是用結(jié)點的索引號來確定結(jié)點的存儲地址。 81.2 基本概念與術(shù)語3. 數(shù)據(jù)的運算對幾種常用的運算進行簡要介紹。(1)檢索：即在數(shù)據(jù)結(jié)構(gòu)里查找滿足一定條件的結(jié)點，

6、一般是給定某字段的值，找具有該字段值的結(jié)點。(2)插入：即往數(shù)據(jù)結(jié)構(gòu)里增加新的結(jié)點。(3)刪除：把指定的結(jié)點從數(shù)據(jù)結(jié)構(gòu)里去掉。(4)更新：改變指定結(jié)點的一個或多個字段的值。91.3 抽象數(shù)據(jù)類型首先我們了解一下在程序設(shè)首先我們了解一下在程序設(shè)計語言中出現(xiàn)的各種數(shù)據(jù)類計語言中出現(xiàn)的各種數(shù)據(jù)類型。型。101.3.1 數(shù)據(jù)類型數(shù)據(jù)類型是一個值的集合和定義在這個值集上數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。的一組操作的總稱。在高級程序設(shè)計語言中，數(shù)據(jù)類型可分為兩類：在高級程序設(shè)計語言中，數(shù)據(jù)類型可分為兩類：一類是原子類型，另一類則是結(jié)構(gòu)類型。一類是原子類型，另一類則是結(jié)構(gòu)類型。 在某

7、種意義上，數(shù)據(jù)結(jié)構(gòu)可以看成是在某種意義上，數(shù)據(jù)結(jié)構(gòu)可以看成是“一組具一組具有相同結(jié)構(gòu)的值有相同結(jié)構(gòu)的值”，而數(shù)據(jù)類型則可被看成是，而數(shù)據(jù)類型則可被看成是由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作所組由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作所組成的。成的。111.3.2 抽象數(shù)據(jù)類型概述抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Type，ADT)，是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。一組操作。 抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型，是一抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型，是一個數(shù)據(jù)模型及定義在該模型上的一組運算。個數(shù)據(jù)模型及定義在該模型上的一

8、組運算。 抽象數(shù)據(jù)類型的描述包括給出抽象數(shù)據(jù)類型的抽象數(shù)據(jù)類型的描述包括給出抽象數(shù)據(jù)類型的名稱、數(shù)據(jù)的集合、數(shù)據(jù)之間的關(guān)系和操作的名稱、數(shù)據(jù)的集合、數(shù)據(jù)之間的關(guān)系和操作的集合等方面的描述。集合等方面的描述。 121.3.2 抽象數(shù)據(jù)類型概述抽象數(shù)據(jù)類型的形式化定義如下：抽象數(shù)據(jù)類型的形式化定義如下：ADT=(D,S,P)D=數(shù)據(jù)對象S=D上的關(guān)系集P=對D的基本操作集定義形式：定義形式：ADT 抽象數(shù)據(jù)類型名稱 數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系： 基本操作： 操作名1： 操作名n：ADT抽象數(shù)據(jù)類型名稱 131.4 算法和算法分析在計算機領(lǐng)域，一個算法實質(zhì)上是針對所處理問題的在計算機領(lǐng)域，一個算法實質(zhì)上是

9、針對所處理問題的需要，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎(chǔ)上實施的需要，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎(chǔ)上實施的一種運算。一種運算。由于數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)不是唯一的，所以處由于數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)不是唯一的，所以處理同一個問題的算法也不是唯一的；即使對于具有相理同一個問題的算法也不是唯一的；即使對于具有相同邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的問題而言，由于設(shè)計思想和同邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的問題而言，由于設(shè)計思想和設(shè)計技巧不同，編寫出來的算法也不大相同。設(shè)計技巧不同，編寫出來的算法也不大相同。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程的目的，就是要學(xué)會根據(jù)實際學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程的目的，就是要學(xué)會根據(jù)實際問題的需要，為數(shù)據(jù)選擇合

10、適的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，問題的需要，為數(shù)據(jù)選擇合適的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，進而設(shè)計出合理和實用的算法。進而設(shè)計出合理和實用的算法。141.4.1 算法的基本概念1. 算法2. 算法的特征(1)有窮性。 (2)確定性。 (3)可行性。 (4)有輸入。 (5)有輸出。 3. 算法與程序的區(qū)別(1)一個算法必須在有窮步之后結(jié)束，一個程序不一定滿足有窮性。 (2)程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。(3)算法代表了對問題的求解過程，而程序則是算法在計算機上的實現(xiàn)。(4)算法和數(shù)據(jù)結(jié)構(gòu)是相輔相成的。151.4.1 算法的基本概念4. 算法的設(shè)計目標(biāo)(1) 正確性。 (2) 可讀性。

11、(3) 健壯性。 (4) 高效率。 (5) 低存儲量需求。 161.4.1 算法的基本概念5. 算法的描述(1) 自然語言 (2) 流程圖 (3) 高級程序設(shè)計語言 (4) 類語言 定義變量 x 結(jié)束 輸入 x x0 d=x%10; 輸出 d; x=x/10; 否 是 171.4.2 算法的時間復(fù)雜度一個程序的時間復(fù)雜度一個程序的時間復(fù)雜度(Time Complexity)是指程序是指程序運行從開始到結(jié)束所需要的時間。運行從開始到結(jié)束所需要的時間。一個算法是由控制結(jié)構(gòu)和原操作構(gòu)成的，其執(zhí)行時間一個算法是由控制結(jié)構(gòu)和原操作構(gòu)成的，其執(zhí)行時間取決于兩者的綜合效果。取決于兩者的綜合效果。 定義定義(

12、大大O記號記號)：如果存在兩個正常數(shù)：如果存在兩個正常數(shù)c和和n0，使得對，使得對所有的所有的n, nn0，有：，有：f(n) cg(n)則有：則有：f(n) (g(n)使用大使用大O記號表示的算法的時間復(fù)雜度，稱為算法的記號表示的算法的時間復(fù)雜度，稱為算法的漸近時間復(fù)雜度漸近時間復(fù)雜度(Asymptotic Complexity)。181.4.3 算法的空間復(fù)雜度算法的空間復(fù)雜度算法的空間復(fù)雜度(Space Complexity)是指算是指算法從開始運行到運行結(jié)束所需的存儲空間，即法從開始運行到運行結(jié)束所需的存儲空間，即算法執(zhí)行過程中所需的最大存儲空間。算法執(zhí)行過程中所需的最大存儲空間。類似

13、于算法的時間復(fù)雜度，算法的空間復(fù)雜度類似于算法的時間復(fù)雜度，算法的空間復(fù)雜度通常也是采用一個數(shù)量級來度量。記作：通常也是采用一個數(shù)量級來度量。記作：S(n)=O(g(n)，稱，稱S(n)為算法的漸近空間復(fù)雜為算法的漸近空間復(fù)雜度。度。算法運行所需的存儲空間包括以下兩部分：算法運行所需的存儲空間包括以下兩部分：(1)固定部分。 (2)可變部分。 19本 章 小 結(jié)(1) 數(shù)據(jù)結(jié)構(gòu)研究的三方面內(nèi)容是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)研究的三方面內(nèi)容是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和對數(shù)據(jù)的運算。數(shù)據(jù)的邏輯結(jié)構(gòu)可數(shù)據(jù)的存儲結(jié)構(gòu)和對數(shù)據(jù)的運算。數(shù)據(jù)的邏輯結(jié)構(gòu)可分為集合、線性、樹和圖四種基本結(jié)構(gòu)。數(shù)據(jù)的存儲分為集合、線性、樹和圖四種基本結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈?zhǔn)?、索引和散列四種存儲結(jié)構(gòu)。結(jié)構(gòu)有順序、鏈?zhǔn)?、索引和散列四種存儲結(jié)構(gòu)。(2) 算法是對特定問題求解步驟的一種描述，是指令算法是對特定問題求解步驟的一種描述，是指令的有限序列。算法具有有窮性、確定性、可行性、輸?shù)挠邢扌蛄?。算法具有有窮性、確定性、可行性、輸入、輸出特性。入、輸出特性。(3) 一個好的算法應(yīng)該達到正確性、可讀性、健壯性、一個好的算法應(yīng)該達到正確性、可讀性、健