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

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

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

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

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

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

數(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)（具有一對一的關(guān)系，所有元素按照某種次序排列在一個序列中，元素存在直接后繼和直接前驅(qū)）、樹形結(jié)構(gòu)（集合中元素存在一對多的關(guān)系）、圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）（集合中的元素存在多對多的關(guān)系）

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

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

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

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

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

數(shù)據(jù)結(jié)構(gòu)研究的三個方面：數(shù)據(jù)間的固有關(guān)系（邏輯結(jié)構(gòu)）；數(shù)據(jù)在計算機(jī)內(nèi)部的存儲方法（存儲結(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、長整型long int-4）、字符型char-1、浮點(diǎn)型（單精度型float-4、雙精度型double-8、長雙精度型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ù)類型用戶定義用來表示實際應(yīng)用問題的數(shù)據(jù)模型

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

3.算法和算法分析

3.1算法

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

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

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

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

可讀性：易于理解

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

效率：時間和存儲空間

3.3算法效率的度量

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

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

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

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

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

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

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

1>常量型：O(1);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

實例：類所定義的一個具體對象；

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

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

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

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

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

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

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

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

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

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

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

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

C++,Java等等