數(shù)據(jù)結構（Java版）課件 第1章 緒論

第1章緒論

目錄2引言基本概念算法小結第一部分第二部分第三部分第四部分學習目的課程內容數(shù)據(jù)與數(shù)據(jù)結構數(shù)據(jù)類型與抽象數(shù)據(jù)類型算法的概念算法描述算法分析第一部分引言學習目的4抽象模型實踐積累信息處理從具體問題中抽象出適當?shù)臄?shù)學模型：分析問題，提取操作的對象，找出操作對象之間的邏輯關系，給出相應的數(shù)學模型。設計解決此數(shù)學模型的算法。編程、運行、調試，得出結果設計算法學會使用計算機解決實際的應用問題課程內容5過程抽象實現(xiàn)評價邏輯結構基本運算數(shù)據(jù)表示數(shù)據(jù)處理儲存結構算法不同數(shù)據(jù)結構比較和算法性能分析第二部分基本概念數(shù)據(jù)與數(shù)據(jù)結構7數(shù)據(jù)

數(shù)據(jù)(Data)是能夠被計算機程序識別、存儲、加工和處理的描述客觀事物的數(shù)字等符號集合的總稱。數(shù)據(jù)項

數(shù)據(jù)項(DataItem)是具有獨立含義的、數(shù)據(jù)不可分割的最小標識單位，是數(shù)據(jù)元素的組成部分，也可稱為字段和域。數(shù)據(jù)元素

數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位，又可稱為元素、結點、頂點和記錄，是一個數(shù)據(jù)整體中可以標識和訪問的數(shù)據(jù)單元。數(shù)據(jù)與數(shù)據(jù)結構8數(shù)據(jù)對象

數(shù)據(jù)對象(DataObject)是性質相同的數(shù)據(jù)元素的集合，也叫數(shù)據(jù)元素類，是數(shù)據(jù)的一個子集，數(shù)據(jù)元素是數(shù)據(jù)對象的一個實例。數(shù)據(jù)結構

數(shù)據(jù)結構(DataStructure)是相互之間存在著一種或者多種關系的數(shù)據(jù)元素的集合，數(shù)據(jù)結構概念包含3個方面的內容，即數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構和數(shù)據(jù)的操作，只有3個方面的內容相同才能稱為完全相同的數(shù)據(jù)結構。數(shù)據(jù)與數(shù)據(jù)結構

數(shù)據(jù)的邏輯結構9數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間存在的邏輯關系，由數(shù)據(jù)元素的集合和定義在此集合上的關系組成。兩要素：數(shù)據(jù)元素的集合、關系的集合。數(shù)據(jù)與數(shù)據(jù)結構

數(shù)據(jù)的邏輯結構分類10邏輯結構樹形結構商業(yè)策略集合圖形結構線性結構集合中元素的關系極為松散，關系為“屬于同一個集合”。線性結構是數(shù)據(jù)元素中具有線性關系的數(shù)據(jù)結構，線性結構中的結點存在“一對一”的關系。樹形結構是數(shù)據(jù)元素之間具有層次關系的一種非線性結構，樹形結構中的結點存在“一對多”的關系。圖形結構也是一種非線性結構，圖形結構中的結點存在“多對多”的關系。數(shù)據(jù)與數(shù)據(jù)結構

數(shù)據(jù)的存儲結構11邏輯結構在計算機中的存儲表示或實現(xiàn)叫數(shù)據(jù)的存儲結構，也叫物理結構。數(shù)據(jù)的邏輯結構從邏輯關系角度觀察數(shù)據(jù)，與數(shù)據(jù)的存儲無關，是獨立于計算機的；而數(shù)據(jù)的存儲結構是邏輯結構在計算機中的實現(xiàn)，依賴于計算機。12存儲結構索引存儲結構商業(yè)策略順序存儲結構散列存儲結構鏈式存儲結構順序存儲結構在連續(xù)的存儲單元中存放數(shù)據(jù)元素，元素的物理存儲次序和邏輯次序一致，即物理位置相鄰的元素在邏輯上也相鄰，每個元素與其前驅元素和后繼元素的存儲位置相鄰，數(shù)據(jù)元素的物理存儲結構體現(xiàn)它們之間的邏輯關系。鏈式存儲結構使用地址分散的存儲單元存放數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素的物理位置不一定相鄰，數(shù)據(jù)元素間的邏輯關系通常由附加的指針表示，指針記錄前驅元素和后繼元素的存儲地址。索引存儲結構在存儲數(shù)據(jù)元素的基礎上增加索引表。散列存儲結構也叫哈希存儲結構，數(shù)據(jù)元素的具體存儲地址根據(jù)該數(shù)據(jù)元素的關鍵字值通過散列函數(shù)直接計算出來。數(shù)據(jù)與數(shù)據(jù)結構

數(shù)據(jù)的存儲結構分類13數(shù)據(jù)與數(shù)據(jù)結構

數(shù)據(jù)操作數(shù)據(jù)操作是指對數(shù)據(jù)結構中的數(shù)據(jù)元素進行運算或處理。數(shù)據(jù)操作定義在數(shù)據(jù)的邏輯結構上，每種邏輯結構都需要一組對其數(shù)據(jù)元素進行處理以實現(xiàn)特定功能的操作，如插入、刪除、更新等。數(shù)據(jù)操作的實現(xiàn)依賴于數(shù)據(jù)的存儲結構。常用的數(shù)據(jù)操作：創(chuàng)建操作、插入操作、刪除操作、查找操作、修改操作、遍歷操作、銷毀操作數(shù)據(jù)類型

數(shù)據(jù)類型(DataType)是一組性質相同的值的集合和定義在此集合上的一組操作的總稱。在用高級程序語言編寫的程序中必須對程序中出現(xiàn)的每個變量、常量明確說明它們所屬的數(shù)據(jù)類型。高級程序設計語言通常預定義基本數(shù)據(jù)類型和構造數(shù)據(jù)類型。

基本數(shù)據(jù)類型：只能作為一個整體來進行處理不可分解的數(shù)據(jù)類型。

構造數(shù)據(jù)類型：使用已有的基本數(shù)據(jù)類型和已定義的構造數(shù)據(jù)類型通過一定的語法規(guī)則組織起來的數(shù)據(jù)類型。數(shù)據(jù)抽象15

數(shù)據(jù)抽象是指“定義和實現(xiàn)相分離”，即將一個類型的數(shù)據(jù)及其上的操作的邏輯含義和具體實現(xiàn)相分離，只考慮執(zhí)行什么操作(做什么)，而不考慮怎樣實現(xiàn)這些操作(怎樣做)。

數(shù)據(jù)抽象是一種信息隱蔽技術，可利用數(shù)據(jù)抽象研究復雜對象，忽略次要和實現(xiàn)細節(jié)，抽象出本質特征，抽象層次越高，復用程度越高。

數(shù)據(jù)抽象是通過抽象數(shù)據(jù)類型來實現(xiàn)的。抽象數(shù)據(jù)類型16

抽象數(shù)據(jù)類型(AbstractDataType，ADT)是從問題的數(shù)學模型中抽象出來的邏輯結構及定義在邏輯結構上的一組操作，僅描述了數(shù)據(jù)的特性和數(shù)據(jù)操作的語法規(guī)則，隱藏了數(shù)據(jù)的存儲結構和操作的實現(xiàn)細節(jié)。

抽象數(shù)據(jù)類型是實現(xiàn)軟件模塊化設計思想的重要手段，一個抽象數(shù)據(jù)類型是描述一種特定功能的基本模塊，由各種基本模塊可組織和構造起來一個大型的軟件系統(tǒng)。

在一般的面向對象語言中，抽象數(shù)據(jù)類型通?？梢圆捎贸橄箢惢蚪涌诘姆绞竭M行描述。第三部分算法算法的概念算法的定義

算法是有窮規(guī)則的集合，其規(guī)則確定一個解決某一特定類型問題的指令序列，其中每一條指令表示計算機的一個或者多個操作。算法的概念算法必須滿足以下5個特性。有窮性：對于任意的合法輸入值，算法必須在執(zhí)行有窮步驟后結束，并且每一步都在有窮的時間內完成。確定性：算法對各種情況下執(zhí)行的每個操作都有確切的規(guī)定，算法的執(zhí)行者和閱讀者都能明確其含義和如何執(zhí)行，并且在任何條件下算法都只有一條執(zhí)行路徑。可行性：算法中的操作必須都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)，并且每一條指令都符合語法規(guī)則，滿足語義要求，都能被確切執(zhí)行。有輸入：輸入數(shù)據(jù)是算法的處理對象，一個算法具有零個或多個輸入數(shù)據(jù)，既可以由算法指定，也可以在算法執(zhí)行過程中通過輸入得到。有輸出：輸出數(shù)據(jù)是算法對輸入數(shù)據(jù)進行信息加工后得到的結果，輸出數(shù)據(jù)和輸入數(shù)據(jù)具有確定的對應關系，即算法的功能。一個算法有一個或多個輸出數(shù)據(jù)。20基本目標高效率商業(yè)策略正確性可讀性健壯性算法應滿足應用問題的需求，這是算法設計最重要、最基本的目標。算法應具有良好的容錯性，可以檢查錯誤是否出現(xiàn)并且對錯誤進行適當?shù)奶幚恚词馆斎氲臄?shù)據(jù)不合適，也能避免出現(xiàn)不可控的結果。算法的執(zhí)行時間越短，時間效率越高；算法執(zhí)行時所占的存儲空間越小，空間效率越高。時間效率和空間效率往往不可兼得，用戶在解決實際問題時要根據(jù)實際情況權衡得失，進行高效率算法的設計。算法的表達思路應清晰，層次分明，易于理解，可讀性強，以便于后續(xù)對算法的使用和修改。算法的概念

算法設計的4個基本目標算法的概念

算法與數(shù)據(jù)結構21算法建立在數(shù)據(jù)結構之上，對數(shù)據(jù)結構的操作需要使用算法來描述。算法設計依賴于數(shù)據(jù)的邏輯結構，算法實現(xiàn)依賴于數(shù)據(jù)的存儲結構。22算法描述010203自然語言用中文或英文對算法進行表達，簡單易懂，但缺乏嚴謹性。自然語言使用某種具體的程序設計語言（如Python語言）對算法進行描述。此種方式嚴謹，算法可直接在計算機上執(zhí)行，但算法復雜、不易理解，需要借助大量的外部注釋才能使用戶明白。程序設計語言偽代碼是介于自然語言和程序設計語言之間的算法描述語言，是將程序設計語言的語法規(guī)則用自然語言進行表示，忽略了嚴格的語法規(guī)則和描述細節(jié)，更易被用戶理解，并且更容易轉換成程序設計語言執(zhí)行。偽代碼23算法描述

例題設計算法求兩個整數(shù)的最大公約數(shù)。假設c為兩個整數(shù)a和b的最大公約數(shù)。用數(shù)學方法求兩個數(shù)的最大公約數(shù)，分別將a和b兩個整數(shù)分解成若干質因數(shù)的乘積，再從中選擇最大的公約數(shù)。此種方法很難用于實際計算之中，因為大數(shù)的質因數(shù)很難進行分解。質因數(shù)分解法中國古代的數(shù)學經(jīng)典著作《九章算術》中寫道：“以少減多，更相減損，求其等也，以等數(shù)約之，即除也，其所以相減者皆等數(shù)之重疊，顧以等數(shù)約之?！逼渲?，等數(shù)即指兩數(shù)的最大公約數(shù)。更相減損法實際上，輾轉相除法就是現(xiàn)代版的更相減損術，使用循環(huán)實現(xiàn)：輾轉相除法算法分析24算法分析技術主要是通過某種方法討論算法的復雜度，評價算法的效率，以便在解決實際問題時根據(jù)實際情況和算法的優(yōu)缺點對算法進行取舍。算法的優(yōu)劣主要通過算法復雜度進行衡量，復雜度的高低反映了所需計算機資源的多少。計算機資源主要包括時間資源和空間資源。因此算法的復雜度通常以時間復雜度和空間復雜度來體現(xiàn)。算法分析

算法的時間復雜度25R算法的時間復雜度(TimeComplexity)是指算法的執(zhí)行時間隨問題規(guī)模的變化而變化的趨勢，反映算法執(zhí)行時間的長短。

算法分析

算法的時間復雜度通常采用算法的漸進分析中的大O表示法作為算法時間復雜度的漸進度量值，稱為算法的漸進時間復雜度。大O表示法是指當且僅當存在正整數(shù)c和n?0，使得0≤T(n)≤cf(n)對所有的n≥n0成立時，算法執(zhí)行時間的增長率與f(n)的增長率相同，記為T(n)=O(f(n))。一般地，如果f(n)=aknk+ak-1nk-1+…+a1n1+a0，且ai≥0，T(n)=O(nk)，即使用大O表示法時只需保留關于數(shù)據(jù)元素個數(shù)n的多項式的最高次冪的項并去掉其系數(shù)。比如，若算法的執(zhí)行時間是常數(shù)級，不依賴數(shù)據(jù)量的大小，則時間復雜度為O(1)；若算法的執(zhí)行時間與數(shù)據(jù)量為線性關系，則時間復雜度為O(n)；對數(shù)級、平方級、立方級、指數(shù)級的時間復雜度分別為O(log2n)、O(n2)、O(n3)、O(2n)。這些函數(shù)按數(shù)量級遞增排列具有下列關系：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)27R010203一個循環(huán)的時間代價=循環(huán)次數(shù)每次執(zhí)行的基本指令數(shù)目多個并列的循環(huán)的時間代價=每個循環(huán)的時間代價之和多層嵌套循環(huán)的時間代價=每層循環(huán)的時間代價之積算法分析

算法的時間復雜度循環(huán)語句的時間代價一般可用以下3條原則進行分析：算法分析

算法的空間復雜度算法的空間復雜度(SpaceComplexity)是指算法執(zhí)行時所占用的額外存儲空間量隨問題規(guī)模的變化而變化的趨勢。執(zhí)行一個算法所需要的存儲空間主要包含以下兩個部分。(1)固定空間部分：主要包括算法的程序指令、常量、變量所占的空間，與所處理問題的規(guī)模無關。(2)可變空間部分：主要包括輸入的數(shù)據(jù)元素占用的空間和程序運行過程中額外的存儲空間，與處理問題的規(guī)模有關。算法分析

算法的空間復雜度當問題的規(guī)模為n時，S(n)表示此時算法占用的存儲空間量，稱為算法的空間復雜度，當n增大時S(n)也隨之增大。通常采用算法的漸進分析中的大O表示法作為算法空間復雜度的漸進度量值，稱為算法的漸進空間復雜度，記作S(n)=O(f(n))，其分析與算法的漸進時間復雜度相同。算法描述

例題設n為正整數(shù)，試確定下列程序段中語句“x+=1”的頻度。算法描述

例題設n為正整數(shù)，試確定下列程序段中語句“x+=1”的頻度。算法描述

例題設n為正整數(shù)，試確定下列程序段中語句“x+=1”的頻度。解：(1)i為1時，j值只能取1，語句執(zhí)行一次；i為2時，j可取1或2，語句執(zhí)行兩次；i為n時，j可取1、2、…,n，語句執(zhí)行n次，所以語句頻度=1+2+…+n=n(n+1)/2。(2)i為1時，j值只能取1，k值可取1、2、…、n，語句執(zhí)行n次；i為2時，j可取1或2，k值可取1、2、…、n，語句執(zhí)行2n次；i為n時，j可取1、2、…、n，語句執(zhí)行n×n次，所以語句頻度=n2(n+1)/2。(3)i與j初始和為1，其后每循環(huán)一次i和j中有且僅有一個值增1，即i與j的和增1。由于循環(huán)條件為i+j<=n，因此循環(huán)共執(zhí)行n次。所以，語句頻度為n。(4)分析y的初始值為100，當y≤0時循環(huán)結束，x++每執(zhí)行10次y減小1，所以x+=1的語句頻度為1000。第四部分小結34小結(1)數(shù)據(jù)結構包括邏輯結構和存儲結構兩個方面。數(shù)據(jù)的邏輯結構分為集合、線性結構、樹形結構和圖形結構4種。數(shù)據(jù)的