本文為大家提供自考02142數據結構導論串講筆記(完整版)，有需要的同學可以下載文末附件自取。

自考02142數據結構導論串講筆記(完整版)

第一張概論

1.1 引言

兩項基本任務：數據表示，數據處理

軟件系統生存期：軟件計劃，需求分析，軟件設計，軟件編碼，軟件測試，軟件維護由一種邏輯結構和一組基本運算構成的整體是實際問題的一種數學模型，這種數學模型的建立，選擇和實現是

數據結構的核心問題。

機外表示 ------邏輯結構 ------存儲結構

處理要求 -----基本運算和運算 -------算法

1.2.1 數據，邏輯結構和運算

數據：凡是能夠被計算機存儲，加工的對象通稱為數據

數據元素：是數據的基本單位，在程序中作為一個整體加以考慮和處理。又稱元素、頂點、結點、記錄。

數據項： 數據項組成數據元素， 但通常不具有完整確定的實際意義， 或不被當作一個整體對待。 又稱字段或域，是數據不可分割的最小標示單位。

1.2.2 數據的邏輯結構

邏輯關系：是指數據元素之間的關聯方式，又稱“鄰接關系”

邏輯結構 :數據元素之間邏輯關系的整體稱為邏輯結構。即數據的組織形式。

四種基本邏輯結構：

1 集合：任何兩個結點間沒有邏輯關系，組織形式松散

2 線性結構：結點按邏輯關系依次排列成一條“鎖鏈”

3 樹形結構：具有分支，層次特性，形態像自然界中的樹

4. 圖狀結構：各個結點按邏輯關系互相纏繞，任何兩個結點都可以鄰接。

注意點 :

1. 邏輯結構與數據元素本身的形式，內容無關。

2. 邏輯結構與數據元素的相對位置無關

3. 邏輯結構與所含結點個數無關。

運算：運算是指在任何邏輯結構上施加的操作，即對邏輯結構的加工。

加工型運算：改變了原邏輯結構的“值” ，如結點個數，結點內容等。

引用型運算 :不改變原邏輯結構個數和值，只從中提取某些信息作為運算的結果。

引用：查找，讀取

加工：插入，刪除，更新

同一邏輯結構 S 上的兩個運算 A 和 B, A 的實現需要或可以利用 B，而 B 的實現不需要利用 A，則稱 A 可以歸約為 B。

假如 X 是 S上的一些運算的集合， Y是 X 的一個子集， 使得 X 中每一運算都可以規約為 Y 中的一個或多個運算，而 Y 中任何運算不可規約為別的運算，則稱 Y 中運算(相對于 X)為基本運算。將邏輯結構 S和在 S上的基本運算集 X 的整體( S,X)稱為一個數據結構。數據結構包括邏輯結構和處理方式。

1.3 存儲實現和運算實現

由于邏輯結構是設計人員根據解題需要選定的數據組織形式， 因此存儲實現建立的機內表示應遵循選定的邏輯結構。另一方面，由于邏輯結構不包括結點內容即數據元素本身的表示，因此存儲實現的另一主要內容是建立數據元素的機內表示。按上述思路建立的數據的機內表示稱為數據的存儲結構。

存儲結構包括三部分：

1. 存儲結點 ，每個存儲結點存放一個數據元素。

2. 數據元素之間關聯方式的表示， 也就是邏輯結構的機內表示。

3. 附加設施 ，如方便運算實現而設置的“啞結點”等。

四種基本存儲方式：

1. 順序存儲方式 ：每個存儲結點只含一個數據元素。所有存儲結點相繼存放在一個連續的存儲區里。用存儲結點間的位置關系表述數據元素之間的邏輯關系。

2. 鏈式存儲方式 ：每個存儲結點不僅含有一個數據元素，還包含一組指針。每個指針指向一個與本結點有邏輯關系的結點，即用附加的指針表示邏輯關系。

3. 索引存儲方式 ：每個存儲結點只含一個數據元素，所有存儲結點連續存放。此外增設一個索引表，索引指示各存儲結點的存儲位置或位置區間端點。

4. 散列存儲方式 ：每個結點含一個數據元素，各個結點均勻分布在存儲區里，用散列函數指示各結點的存儲位置或位置區間端點。

1.3.2 運算實現

運算只描述處理功能，不包括處理步驟和方法;運算實現的核心是處理步驟的規定，即算法設計。

算法：算法規定了求解給定問題所需的所有處理步驟及其執行順序，使得給定類型的任何問題能在有限時間內被機械的求解。

算法分類：

1：運行終止的程序可執行部分：又稱為程序

2：偽語言算法 ：不可以直接在計算機上運行，但容易編寫和閱讀。

3：非形式算法 ：用自然語言，同時可能還使用了程序設計語言或偽語言描述的算法。

1.4 算法分析

算法質量評價指標：

1. 正確性 ：能夠正確實現處理要求

2. 易讀性 ：易于閱讀和理解，便于調試，修改和擴充

3. 健壯性 ：當環境發生變化，算法能夠適當做出反應或處理，不會產生不需要的運行結果

4. 高效率 ：達到所需要的時空性能。

如何確定一個算法的時空性能，稱為算法分析

一個算法的時空性能是指該算法的時間性能和空間性能， 前者是算法包含的計算量， 后者是算法需要的存儲量。

算法在給定輸入下的計算量：

1. 根據該問題的特點選擇一種或幾種操作作為“標準操作” 。

2. 確定每個算法在給定輸入下共執行了多少次標準操作，并將此次數規定為該算法在給定輸入下的計算量。若無特殊說明，將默認以賦值語句作為標準操作。

最壞情況時間復雜性：算法在所有輸入下的計算量的最大值作為算法的計算量

平均時間復雜性：算法在所有輸入下的計算量的加權平均值作為算法的計算量。

附件：自考02142數據結構導論串講筆記(完整版).pdf