?自考02142數(shù)據(jù)結(jié)構(gòu)導論串講筆記(完整版)

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

自考02142數(shù)據(jù)結(jié)構(gòu)導論串講筆記(完整版)

第一張概論

1.1 引言

兩項基本任務：數(shù)據(jù)表示，數(shù)據(jù)處理

軟件系統(tǒng)生存期：軟件計劃，需求分析，軟件設計，軟件編碼，軟件測試，軟件維護由一種邏輯結(jié)構(gòu)和一組基本運算構(gòu)成的整體是實際問題的一種數(shù)學模型，這種數(shù)學模型的建立，選擇和實現(xiàn)是

數(shù)據(jù)結(jié)構(gòu)的核心問題。

機外表示 ------邏輯結(jié)構(gòu) ------存儲結(jié)構(gòu)

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

1.2.1 數(shù)據(jù)，邏輯結(jié)構(gòu)和運算

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

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

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

1.2.2 數(shù)據(jù)的邏輯結(jié)構(gòu)

邏輯關(guān)系：是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式，又稱“鄰接關(guān)系”

邏輯結(jié)構(gòu) :數(shù)據(jù)元素之間邏輯關(guān)系的整體稱為邏輯結(jié)構(gòu)。即數(shù)據(jù)的組織形式。

四種基本邏輯結(jié)構(gòu)：

1 集合：任何兩個結(jié)點間沒有邏輯關(guān)系，組織形式松散

2 線性結(jié)構(gòu)：結(jié)點按邏輯關(guān)系依次排列成一條“鎖鏈”

3 樹形結(jié)構(gòu)：具有分支，層次特性，形態(tài)像自然界中的樹

4. 圖狀結(jié)構(gòu)：各個結(jié)點按邏輯關(guān)系互相纏繞，任何兩個結(jié)點都可以鄰接。

注意點 :

1. 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式，內(nèi)容無關(guān)。

2. 邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對位置無關(guān)

3. 邏輯結(jié)構(gòu)與所含結(jié)點個數(shù)無關(guān)。

運算：運算是指在任何邏輯結(jié)構(gòu)上施加的操作，即對邏輯結(jié)構(gòu)的加工。

加工型運算：改變了原邏輯結(jié)構(gòu)的“值” ，如結(jié)點個數(shù)，結(jié)點內(nèi)容等。

引用型運算 :不改變原邏輯結(jié)構(gòu)個數(shù)和值，只從中提取某些信息作為運算的結(jié)果。

引用：查找，讀取

加工：插入，刪除，更新

同一邏輯結(jié)構(gòu) S 上的兩個運算 A 和 B, A 的實現(xiàn)需要或可以利用 B，而 B 的實現(xiàn)不需要利用 A，則稱 A 可以歸約為 B。

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

1.3 存儲實現(xiàn)和運算實現(xiàn)

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

存儲結(jié)構(gòu)包括三部分：

1. 存儲結(jié)點 ，每個存儲結(jié)點存放一個數(shù)據(jù)元素。

2. 數(shù)據(jù)元素之間關(guān)聯(lián)方式的表示， 也就是邏輯結(jié)構(gòu)的機內(nèi)表示。

3. 附加設施 ，如方便運算實現(xiàn)而設置的“啞結(jié)點”等。

四種基本存儲方式：

1. 順序存儲方式 ：每個存儲結(jié)點只含一個數(shù)據(jù)元素。所有存儲結(jié)點相繼存放在一個連續(xù)的存儲區(qū)里。用存儲結(jié)點間的位置關(guān)系表述數(shù)據(jù)元素之間的邏輯關(guān)系。

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

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

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

1.3.2 運算實現(xiàn)

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

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

算法分類：

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

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

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

1.4 算法分析

算法質(zhì)量評價指標：

1. 正確性 ：能夠正確實現(xiàn)處理要求

2. 易讀性 ：易于閱讀和理解，便于調(diào)試，修改和擴充

3. 健壯性 ：當環(huán)境發(fā)生變化，算法能夠適當做出反應或處理，不會產(chǎn)生不需要的運行結(jié)果

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

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

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

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

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

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

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

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

附件：自考02142數(shù)據(jù)結(jié)構(gòu)導論串講筆記(完整版).pdf