（一）數(shù)據(jù)結(jié)構(gòu)的基本概念

1.相關(guān)名詞

【1】數(shù)據(jù)

1.信息的載體，描述客觀事物

2.能被輸入到計(jì)算機(jī)中

3.能被計(jì)算機(jī)程序識(shí)別和處理的符號的集合。

【2】數(shù)據(jù)元素

1.數(shù)據(jù)的一個(gè)“個(gè)體”

2.數(shù)據(jù)的基本單位

3.有時(shí)候也被稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等，這時(shí)候用于完整描述一個(gè)對象。ex：一條學(xué)生記錄

【3】數(shù)據(jù)項(xiàng)

1.組成數(shù)據(jù)元素具有特定意義不可分割的最小單位

2.數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合

3.比如說在學(xué)生信息表中的一條學(xué)生記錄（數(shù)據(jù)元素）中這個(gè)學(xué)生的學(xué)號或者性別這些都是數(shù)據(jù)項(xiàng)

【4】數(shù)據(jù)對象

1.具有相同性質(zhì)的數(shù)據(jù)元素的集合

2.是數(shù)據(jù)的一個(gè)子集

【5】數(shù)據(jù)結(jié)構(gòu)：通過抽象方法研究一組具有特定關(guān)系的數(shù)據(jù)的存儲(chǔ)和處理，主要研究三個(gè)方面（三要素）：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算。

2.數(shù)據(jù)結(jié)構(gòu)的三要素=邏輯結(jié)構(gòu)+存儲(chǔ)結(jié)構(gòu)+數(shù)據(jù)運(yùn)算

【1】邏輯結(jié)構(gòu)

? 有2種劃分方式:1.按照線性和非線性分 2.按照結(jié)構(gòu)分

1.線性和非線性

（1）線性：線性表、棧和隊(duì)列、字符串、數(shù)組和廣義表

（2）非線性：樹和圖

2.結(jié)構(gòu)分（4種）

（1）集合結(jié)構(gòu)：在同一個(gè)集合中，它們之間無關(guān)系

（2）線性結(jié)構(gòu)：任意一個(gè)元素之間有且僅有一個(gè)前驅(qū)和后繼，1對1

（3）樹形結(jié)構(gòu)：有一個(gè)前驅(qū)多個(gè)后繼，1對多

（4）圖形結(jié)構(gòu)：有多個(gè)前驅(qū)多個(gè)后繼，多對多

【2】存儲(chǔ)結(jié)構(gòu)（存儲(chǔ)的邏輯結(jié)構(gòu)4種）：順序、鏈?zhǔn)健⑺饕?、散?#xff08;哈希）

*索引：類似課本目錄，每頁都有頁碼i，檢索時(shí)利用結(jié)點(diǎn)（頁）的順序號i確定位置

*散列：也稱哈希存儲(chǔ)，用哈希函數(shù)將數(shù)據(jù)元素按照關(guān)鍵字和唯一的存儲(chǔ)位置關(guān)聯(lián)

【3】數(shù)據(jù)運(yùn)算：插入、刪除、查找、修改、排序等

（二）算法和算法分析

1.算法的基本概念

1.指令的有限序列

2.可以用自然語言描述

3.算法具有5個(gè)重要特性：有窮、確定、可行、輸入輸出

*有窮：步驟和執(zhí)行時(shí)間有限

*確定：有確切含義、無二義、只有唯一的一條執(zhí)行路徑（對于相同的輸入有唯一的執(zhí)行結(jié)果）

*可行：執(zhí)行有限次實(shí)現(xiàn)

*輸入：0或多個(gè)

*輸出：1或多個(gè)（最少1個(gè)結(jié)果）

4.算法和程序是兩個(gè)不同的概念（區(qū)別）

*執(zhí)行時(shí)間：算法步驟有限（有窮性），程序無限次執(zhí)行

*語言描述：程序必須用規(guī)定語言，算法無限制可自然語言。

5.算法的基本目標(biāo)：正確、易讀、健壯、高效率

*健壯：當(dāng)環(huán)境發(fā)生變化（非法輸入）時(shí)候可以適當(dāng)做出反應(yīng)或者處理，不會(huì)產(chǎn)生不正確的結(jié)果

*高效率：較高的時(shí)間（用時(shí)少）和空間性能（占用空間少）

6.算法的評價(jià)方法：事前分析、事后統(tǒng)計(jì)

2.算法的時(shí)間和空間性能分析

【1】時(shí)間復(fù)雜度

1.T（N）表示該算法時(shí)間耗費(fèi)，N為求解問題的規(guī)模

2.當(dāng)N趨向于無窮時(shí)候，僅考慮數(shù)量級（階），就是算法的漸進(jìn)時(shí)間復(fù)雜度，用大o表示法

3.大o表示法就是忽略系數(shù)，類似數(shù)學(xué)的“抓大頭”

4.語句頻度：重復(fù)執(zhí)行的次數(shù)

【2】用大o表示法求解算法的漸進(jìn)時(shí)間復(fù)雜度（有6類）

1. 常量階 O(1)：算法的執(zhí)行時(shí)間不隨輸入數(shù)據(jù)的規(guī)模n變化，即無論輸入數(shù)據(jù)有多大，算法的執(zhí)行時(shí)間都是固定的。這類算法通常只包含基本操作，如賦值、比較等。

2. 對數(shù)階 O（log n)：算法的執(zhí)行時(shí)間隨輸入數(shù)據(jù)的規(guī)模n的對數(shù)增長。這類算法通常涉及到二分搜索或樹結(jié)構(gòu)的深度遍歷。

3. 線性階 O(n)：算法的執(zhí)行時(shí)間隨輸入數(shù)據(jù)的規(guī)模n線性增長。這類算法通常涉及到對數(shù)據(jù)的順序訪問，如數(shù)組或列表的遍歷。

4. 平方階 O(n^2)：算法的執(zhí)行時(shí)間隨輸入數(shù)據(jù)的規(guī)模n的平方增長。這類算法通常涉及到兩層嵌套循環(huán)，如矩陣的乘法或?qū)?shù)組的每個(gè)元素進(jìn)行比較。

5. 線性對數(shù)階 O(n log n)：算法的執(zhí)行時(shí)間是輸入數(shù)據(jù)的規(guī)模n與對數(shù)的乘積。這類算法通常涉及到排序操作，如快速排序或歸并排序。

6. 立方階 O(n^3)：算法的執(zhí)行時(shí)間隨輸入數(shù)據(jù)的規(guī)模n的立方增長。這類算法通常涉及到三層嵌套循環(huán)，如矩陣乘法的直接實(shí)現(xiàn)。