1.數(shù)據(jù)結(jié)構(gòu)的概念和術(shù)語(yǔ)

數(shù)據(jù)(Data)：是對(duì)客觀事物的符號(hào)表示，是指所有能夠輸入到計(jì)算機(jī)并被計(jì)算機(jī)處理的符號(hào)的總稱；

2大類數(shù)據(jù)：數(shù)值數(shù)據(jù)（整數(shù)、浮點(diǎn)數(shù)、復(fù)數(shù)）與非數(shù)值數(shù)據(jù)（字符、字符串、圖像、聲音）；

數(shù)據(jù)元素(Data Element)：數(shù)據(jù)的基本單位，在程序中作為一個(gè)整體進(jìn)行考慮和處理；

數(shù)據(jù)項(xiàng)：數(shù)據(jù)元素可以由多個(gè)數(shù)據(jù)項(xiàng)組成，是數(shù)據(jù)操作中不可分割的最小單位；

數(shù)據(jù)對(duì)象：是性質(zhì)相同的所有元素的集合，是數(shù)據(jù)的一個(gè)子集；

數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素組成的集合，這種關(guān)系被稱為結(jié)構(gòu)；

四類基本結(jié)構(gòu)：集合（數(shù)據(jù)元素?zé)o序也沒有重復(fù)）、線形結(jié)構(gòu)（具有一對(duì)一的關(guān)系，所有元素按照某種次序排列在一個(gè)序列中，元素存在直接后繼和直接前驅(qū)）、樹形結(jié)構(gòu)（集合中元素存在一對(duì)多的關(guān)系）、圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）（集合中的元素存在多對(duì)多的關(guān)系）

直接后繼與直接前驅(qū)：線形結(jié)構(gòu)中僅有第一個(gè)元素沒有直接前驅(qū)，僅有最后一個(gè)元素沒有直接后繼

邏輯結(jié)構(gòu)：Data_Structure = (D, S)

物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示和數(shù)據(jù)關(guān)系的表示

位、元素（節(jié)點(diǎn)）、數(shù)據(jù)域：位是數(shù)據(jù)在計(jì)算機(jī)中的二進(jìn)制表示最小單位的一位位，若干位組合形成的一個(gè)位串來(lái)表示一個(gè)完整，又被稱為一個(gè)節(jié)點(diǎn)，數(shù)據(jù)項(xiàng)對(duì)應(yīng)為數(shù)據(jù)域；

映像、順序映像和非順序映像：元素節(jié)點(diǎn)是數(shù)據(jù)在計(jì)算機(jī)中的映像，其中借助元素在計(jì)算機(jī)存儲(chǔ)中的相對(duì)位置表示數(shù)據(jù)的關(guān)系稱為順序映像，借助元素存儲(chǔ)地址的指針來(lái)表示數(shù)據(jù)的關(guān)系稱為非順序映像。分別對(duì)應(yīng)于順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面：數(shù)據(jù)間的固有關(guān)系（邏輯結(jié)構(gòu)）；數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)方法（存儲(chǔ)結(jié)構(gòu)）；數(shù)據(jù)在不同結(jié)構(gòu)上的操作與處理（算法）。

2.抽象數(shù)據(jù)類型

2.1數(shù)據(jù)類型

5種數(shù)據(jù)類型：基本類型、構(gòu)造類型、指針類型pointer、引用類型reference、空類型void

4種基本類型：整型（短整型shaort int-2、整型int-4、長(zhǎng)整型long int-4）、字符型char-1、浮點(diǎn)型（單精度型float-4、雙精度型double-8、長(zhǎng)雙精度型long double-8）、布爾類型bool

5種構(gòu)造類型：枚舉類型enum、數(shù)組類型srray、結(jié)構(gòu)體類型struct、聯(lián)合類型union、類類型class

2.2數(shù)據(jù)抽象與抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型用戶定義用來(lái)表示實(shí)際應(yīng)用問題的數(shù)據(jù)模型

特點(diǎn)：使用與實(shí)現(xiàn)分離，實(shí)現(xiàn)封裝和信息隱蔽

3.算法和算法分析

3.1算法

算法：是對(duì)特定問題求解步驟的一種描述，是指令的有限序列

五個(gè)特征：有窮性（有限的步驟與運(yùn)行時(shí)間）、確定性（指令的無(wú)疑義）、可行性（可以通過有限次運(yùn)算得到結(jié)果）、輸入（0個(gè)或多個(gè)）、輸出（一個(gè)或多個(gè)）

3.2算法設(shè)計(jì)的要求

正確性：不含語(yǔ)法錯(cuò)誤；程序在輸入數(shù)據(jù)后可以得到滿意的結(jié)果；精心選擇的、典型的、苛刻的數(shù)據(jù)輸入可以得到滿意的結(jié)果；一切合法的輸入可以得到滿意的結(jié)果

可讀性：易于理解

健壯性：使對(duì)非法數(shù)據(jù)的處理也可以得到一定的結(jié)果

效率：時(shí)間和存儲(chǔ)空間

3.3算法效率的度量

時(shí)間復(fù)雜度：程序在計(jì)算機(jī)上運(yùn)行時(shí)間的度量；

2種方法：事后統(tǒng)計(jì)方法和事前分析估算方法；

事后統(tǒng)計(jì)方法的2個(gè)缺陷：一是必須提前運(yùn)行程序，二是受到計(jì)算機(jī)硬件和軟件因素影響；

事前分析估算方法的5個(gè)取決因素：?jiǎn)栴}規(guī)模；算法策略；程序編寫的語(yǔ)言；編譯產(chǎn)生機(jī)器代碼的質(zhì)量；機(jī)器執(zhí)行指令的速度；

漸進(jìn)時(shí)間復(fù)雜度：T(N) = O(F(N))

2種表示形式（對(duì)于隨問題規(guī)模變化算法的時(shí)間復(fù)雜度計(jì)算）：一種是平均算法時(shí)間復(fù)雜度，另一種是最壞情況時(shí)間復(fù)雜度（一般使用這個(gè)）

常見的時(shí)間復(fù)雜度:

1>常量型：O(1);

2>多項(xiàng)式型：O(n)、O(n²)、...、O(n^k)

3>對(duì)數(shù)型：O(log₂ⁿ)、O(2log₂ⁿ)

4>指數(shù)型：O(2ⁿ)、O(eⁿ)

常用的時(shí)間復(fù)雜度比較：

時(shí)間復(fù)雜度計(jì)算：只估算到F（n）的最高項(xiàng)的階，既不考慮低階項(xiàng)，也不考慮常系數(shù)。

空間復(fù)雜度：算法運(yùn)行使用存儲(chǔ)空間的描述S(n)；

原地工作：算法使用的對(duì)輸入數(shù)據(jù)和程序所占之外的額外空間為常數(shù)；

4.面向?qū)ο蟾攀?/h2>

4.1面向?qū)ο蟮乃枷?/h4>

基本思想：盡可能運(yùn)用人類的自然思維方式來(lái)建立問題空間的模型，構(gòu)造盡可能直觀、自然的表達(dá)方法求解問題的軟件系統(tǒng)；

面向?qū)ο?/strong>=對(duì)象+分類+繼承+消息通信；

4.2面向?qū)ο蟮幕靖拍?/h4>

對(duì)象：現(xiàn)實(shí)世界存在的具體事物，可以是有形物體，也可以是無(wú)形的事物或概念；

對(duì)象=數(shù)據(jù)+動(dòng)作（方法、操作）；

對(duì)象的2個(gè)內(nèi)容：屬性和行為；

對(duì)象的3個(gè)特征：一個(gè)區(qū)別于其他對(duì)象的名字；一組描述它屬性的狀態(tài)；一組決定其功能或行為的操作；

對(duì)象3個(gè)特性：模塊的獨(dú)立性、動(dòng)態(tài)的連接性、易維護(hù)性；

 

消息：對(duì)象間交互過程所傳遞的通信信息；

3個(gè)性質(zhì)：同一對(duì)象可以接收不同的消息；相同形式的消息可以發(fā)送給不同的對(duì)象產(chǎn)生不同的響應(yīng)；消息發(fā)送時(shí)不考慮接收者，接受者可以響應(yīng)消息也可以不響應(yīng)；

消息序列：向同一個(gè)對(duì)象發(fā)送的多個(gè)信息或者一個(gè)對(duì)象向外發(fā)出多個(gè)消息；

共有消息：由外界對(duì)象向其發(fā)送的消息稱為共有消息；

私有消息：由對(duì)象向其自身發(fā)送的消息；

3種類型（按功能劃分）：返回對(duì)象內(nèi)部狀態(tài)的消息；改變對(duì)象內(nèi)部狀態(tài)的消息；完成特定操作改變系統(tǒng)狀態(tài)的消息；

類：具有相同屬性和系統(tǒng)操作的對(duì)象集合的抽象；

實(shí)例：類所定義的一個(gè)具體對(duì)象；

模板：類可以看做是對(duì)象的模板，抽象地描述了屬于該類的全部對(duì)象的屬性和操作；

4.3面向?qū)ο蟮幕咎卣?/h4>

封裝性：將一段代碼“包裝”起來(lái)，應(yīng)用時(shí)只知道這段代碼所能完成的功能，而不必知道該段代碼的具體實(shí)現(xiàn)細(xì)節(jié)；

3個(gè)條件：清楚的邊界+預(yù)留的對(duì)外接口+良好的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)隱蔽性

繼承性：子類可以自動(dòng)擁有或共享父類的全部屬性和方法；

4個(gè)優(yōu)點(diǎn)：類間清晰的層次關(guān)系；自動(dòng)的屬性和方法共享，提高代碼的復(fù)用性；減少接口，程序更加易于維護(hù)；具體功能的擴(kuò)充，細(xì)節(jié)的完善；

多態(tài)性：同一個(gè)名字（函數(shù)或運(yùn)算符）在不同場(chǎng)合具有不同的意義（重載）；同一個(gè)界面有多重不同的實(shí)現(xiàn)（虛函數(shù)）。分別對(duì)應(yīng)于編譯時(shí)的多態(tài)性和運(yùn)行時(shí)的多態(tài)性。

4.4面向?qū)ο蟪绦蛟O(shè)計(jì)

面對(duì)過程的程序設(shè)計(jì)：程序=數(shù)據(jù)結(jié)構(gòu)+算法，數(shù)據(jù)結(jié)構(gòu)與算法單獨(dú)設(shè)計(jì)

面對(duì)對(duì)象的程序設(shè)計(jì)：對(duì)象=數(shù)據(jù)結(jié)構(gòu)+算法，將數(shù)據(jù)結(jié)構(gòu)和算法封裝到對(duì)象內(nèi)部

4.5面向?qū)ο蟮恼Z(yǔ)言

早期：LISP語(yǔ)言，Simula67語(yǔ)言，SmallTal語(yǔ)言，逐漸引入面向?qū)ο蟮囊恍└拍?/p>

C++,Java等等