一卧蜓、數(shù)據(jù)結(jié)構(gòu)的基本概念
（1）數(shù)據(jù)：人們利用文字符號妓蛮、數(shù)字符號以及其他規(guī)定的符號，對現(xiàn)實(shí)世界的事物及其活動所做的抽象描述殿衰。
（2）數(shù)據(jù)元素：數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的一個個體盛泡。
（3）數(shù)據(jù)項(xiàng)：一個數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成闷祥，具有獨(dú)立含義的最小單位。
元素之間的關(guān)系稱為結(jié)構(gòu)傲诵。數(shù)據(jù)結(jié)構(gòu)凯砍，簡單地說，就是 數(shù)據(jù)元素的集合加上數(shù)據(jù)元素之間的相互關(guān)系的集合拴竹，可形式化描述為一個二元組：Data Structure = ( D, S)悟衩，其中，D：數(shù)據(jù)元素的集合栓拜，S：D上關(guān)系（結(jié)構(gòu)）的集合座泳。
數(shù)據(jù)結(jié)構(gòu) ＝ 數(shù)據(jù)的邏輯結(jié)構(gòu)∧挥搿＋ 數(shù)據(jù)的存儲結(jié)構(gòu)√羰啤＋ 數(shù)據(jù)的運(yùn)算
（４）抽象數(shù)據(jù)元素：沒有實(shí)際含義的數(shù)據(jù)元素
（５）抽象數(shù)據(jù)元素類型：沒有確切定義的數(shù)據(jù)類型
（６）數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的相互聯(lián)系方式
（７）數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)元素在計算機(jī)中的存儲方式
（８）數(shù)據(jù)的操作：對一種數(shù)據(jù)類型的數(shù)據(jù)進(jìn)行的某種處理
（９）數(shù)據(jù)的操作集合：對一種數(shù)據(jù)類型的數(shù)據(jù)進(jìn)行的所有操作
數(shù)據(jù)的邏輯結(jié)構(gòu)：
１、線性結(jié)構(gòu)：除第一個和最后一個數(shù)據(jù)元素外啦鸣，每個數(shù)據(jù)元素只有一個前驅(qū)和一個后繼數(shù)據(jù)元素
２潮饱、樹結(jié)構(gòu)：除根節(jié)點(diǎn)外，每個數(shù)據(jù)元素只有一個前驅(qū)數(shù)據(jù)元素诫给，可由０個或若干個后繼數(shù)據(jù)元素
３香拉、圖結(jié)構(gòu)：每個數(shù)據(jù)元素可有０個或若干個前驅(qū)數(shù)據(jù)元素和０個或若干個后繼數(shù)據(jù)元素
數(shù)據(jù)的存儲結(jié)構(gòu)：
１、順序存儲結(jié)構(gòu)：把數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存中中狂，其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上也相鄰凫碌，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在數(shù)據(jù)存儲位置關(guān)系上
２、鏈?zhǔn)酱鎯Y(jié)構(gòu)：使用指針把相互直接關(guān)聯(lián)的結(jié)點(diǎn)（即直接前驅(qū)結(jié)點(diǎn)或直接后繼節(jié)點(diǎn)）鏈接起來吃型，其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰证鸥，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在結(jié)點(diǎn)的鏈接關(guān)系上
（指針：是指向物理存儲單元地址的變量。由數(shù)據(jù)元素域和指針域組成的一個結(jié)構(gòu)體稱為結(jié)點(diǎn)）
邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的區(qū)別：
１.邏輯結(jié)構(gòu)定義了數(shù)據(jù)元素之間的邏輯關(guān)系
２.存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機(jī)中實(shí)現(xiàn)
３.一種邏輯結(jié)構(gòu)可以采用不同的存儲方式（順序，鏈?zhǔn)剑┐娣旁谟嬎銠C(jī)中枉层，但都必須反映出要求的邏輯關(guān)系
一個具體問題的軟件設(shè)計通常包含三個步驟：
１泉褐、分析和確定問題的邏輯結(jié)構(gòu)和邏輯操作
２、設(shè)計該問題的具體存儲結(jié)構(gòu)
３鸟蜡、設(shè)計該問題在具體存儲結(jié)構(gòu)下的操作實(shí)現(xiàn)算法
二膜赃、抽象數(shù)據(jù)類型和軟件構(gòu)造的方法
類型是一組值得集合
數(shù)據(jù)類型是指一個類型和定義在這個類型上的操作的集合
抽象數(shù)據(jù)類型（ADT）是指一個邏輯概念上的類型和這個類型上的操作的集合
ＡＤＴ定義包含三部分
１、數(shù)據(jù)元素
２揉忘、數(shù)據(jù)元素之間的相互關(guān)系（結(jié)構(gòu)）
３跳座、定義在數(shù)據(jù)結(jié)構(gòu)上的一組邏輯操作
三、算法及其時間復(fù)雜度
算法是描述求解問題方法的操作步驟集合
算法的設(shè)計
１泣矛、結(jié)構(gòu)化程序設(shè)計方法：“自頂向下疲眷，逐步以模塊的形式細(xì)化”原則
２、面向?qū)ο蟪绦蛟O(shè)計方法
描述算法的語言形式：
１您朽、文字形式
２狂丝、偽代碼形式
３、程序設(shè)計語言形式
算法分析：
評價算法好壞的標(biāo)準(zhǔn)哗总，除算法應(yīng)該是正確的外几颜，還應(yīng)考慮：
１.該算法是易讀、易編碼讯屈、可調(diào)試
２.該算法能有效利用計算機(jī)資源蛋哭，歸結(jié)為ｃｐｕ執(zhí)行指令數(shù)和占用內(nèi)存存儲單元數(shù)
評價方法：
１.實(shí)驗(yàn)方法（運(yùn)行程序）
２.算法的漸進(jìn)分析，簡稱算法分析
′棠浮（１）分析算法消耗時間資源——時間復(fù)雜度
∽恢骸（２）分析算法使用的空間資源——空間復(fù)雜度
問題的規(guī)模
例如， “求1到100的所有素數(shù)之和“ 與 “求1到1000的所有素數(shù)之和” 是同一類型的問題叛本，但問題的規(guī)模不同棺妓。
設(shè)n表示問題的規(guī)模（或算法的輸入量），則該類問題可抽象地表示為：
“求1到n的所有素數(shù)之和”炮赦。
解決同樣類型的問題有多種算法怜跑，我們需要一種方法來對不同的算法來進(jìn)行比較
算法滿足以下性質(zhì)：
輸入性、輸出性吠勘、有限性性芬、確定性、可執(zhí)行性
算法設(shè)計滿足以下目標(biāo)：
正確性剧防、可讀性植锉、健壯性、高時間效率峭拘、高空間效率
算法的時間復(fù)雜度還與初始輸入集有關(guān)
平均時間復(fù)雜度是指所有可能的輸入數(shù)據(jù)集均以等概率出現(xiàn)的情況下俊庇，算法的平均運(yùn)行時間狮暑。
最壞輸入數(shù)據(jù)集情況下的時間復(fù)雜度稱最壞時間復(fù)雜度。一般若無特定說明辉饱，討論的時間復(fù)雜度均指的是最壞情況下的運(yùn)行時間搬男。
空間復(fù)雜度
數(shù)據(jù)結(jié)構(gòu)所需空間和算法在處理過程中所需額外空間的總和
它同樣是問題規(guī)模n的函數(shù)，也可以實(shí)行類似的漸進(jìn)分析方法彭沼。
大多數(shù)靜態(tài)數(shù)據(jù)結(jié)構(gòu)（即存儲空間在執(zhí)行過程中不發(fā)生變化）缔逛，空間開銷與問題的規(guī)模成正比（為線性增長），或者不隨問題規(guī)模而增大（為常數(shù)）姓惑。
最后算法應(yīng)具有可讀性褐奴，主要體現(xiàn)在算法的符號命名和書寫規(guī)范上
