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

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

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

第一張概論

1.1 引言

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

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

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

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

處理要求 -----基本運(yùn)算和運(yùn)算 -------算法

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

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

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

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

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 集合：任何兩個(gè)結(jié)點(diǎn)間沒(méi)有邏輯關(guān)系，組織形式松散

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

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

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

注意點(diǎn) :

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

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

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

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

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

引用型運(yùn)算 :不改變?cè)壿嫿Y(jié)構(gòu)個(gè)數(shù)和值，只從中提取某些信息作為運(yùn)算的結(jié)果。

引用：查找，讀取

加工：插入，刪除，更新

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

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

1.3 存儲(chǔ)實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)

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

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

1. 存儲(chǔ)結(jié)點(diǎn) ，每個(gè)存儲(chǔ)結(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素。

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

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

四種基本存儲(chǔ)方式：

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

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

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

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

1.3.2 運(yùn)算實(shí)現(xiàn)

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

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

算法分類：

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

2：偽語(yǔ)言算法 ：不可以直接在計(jì)算機(jī)上運(yùn)行，但容易編寫(xiě)和閱讀。

3：非形式算法 ：用自然語(yǔ)言，同時(shí)可能還使用了程序設(shè)計(jì)語(yǔ)言或偽語(yǔ)言描述的算法。

1.4 算法分析

算法質(zhì)量評(píng)價(jià)指標(biāo)：

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

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

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

4. 高效率 ：達(dá)到所需要的時(shí)空性能。

如何確定一個(gè)算法的時(shí)空性能，稱為算法分析

一個(gè)算法的時(shí)空性能是指該算法的時(shí)間性能和空間性能， 前者是算法包含的計(jì)算量， 后者是算法需要的存儲(chǔ)量。

算法在給定輸入下的計(jì)算量：

1. 根據(jù)該問(wèn)題的特點(diǎn)選擇一種或幾種操作作為“標(biāo)準(zhǔn)操作” 。

2. 確定每個(gè)算法在給定輸入下共執(zhí)行了多少次標(biāo)準(zhǔn)操作，并將此次數(shù)規(guī)定為該算法在給定輸入下的計(jì)算量。若無(wú)特殊說(shuō)明，將默認(rèn)以賦值語(yǔ)句作為標(biāo)準(zhǔn)操作。

最壞情況時(shí)間復(fù)雜性：算法在所有輸入下的計(jì)算量的最大值作為算法的計(jì)算量

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

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