一、數(shù)據(jù)結(jié)構(gòu)的基本概念
（1）數(shù)據(jù)：人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定的符號(hào)，對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的抽象描述。
（2）數(shù)據(jù)元素：數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的一個(gè)個(gè)體。
（3）數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成，具有獨(dú)立含義的最小單位。
元素之間的關(guān)系稱為結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)，簡單地說，就是 數(shù)據(jù)元素的集合加上數(shù)據(jù)元素之間的相互關(guān)系的集合，可形式化描述為一個(gè)二元組：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ù)的存儲(chǔ)結(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ù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)方式
（８）數(shù)據(jù)的操作：對(duì)一種數(shù)據(jù)類型的數(shù)據(jù)進(jìn)行的某種處理
（９）數(shù)據(jù)的操作集合：對(duì)一種數(shù)據(jù)類型的數(shù)據(jù)進(jìn)行的所有操作
數(shù)據(jù)的邏輯結(jié)構(gòu)：
１、線性結(jié)構(gòu)：除第一個(gè)和最后一個(gè)數(shù)據(jù)元素外，每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)和一個(gè)后繼數(shù)據(jù)元素
２、樹結(jié)構(gòu)：除根節(jié)點(diǎn)外，每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素，可由０個(gè)或若干個(gè)后繼數(shù)據(jù)元素
３、圖結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素可有０個(gè)或若干個(gè)前驅(qū)數(shù)據(jù)元素和０個(gè)或若干個(gè)后繼數(shù)據(jù)元素
數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：
１、順序存儲(chǔ)結(jié)構(gòu)：把數(shù)據(jù)元素存儲(chǔ)在一塊連續(xù)地址空間的內(nèi)存中，其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上也相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在數(shù)據(jù)存儲(chǔ)位置關(guān)系上
２、鏈?zhǔn)酱鎯?chǔ)結(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)系上
（指針：是指向物理存儲(chǔ)單元地址的變量。由數(shù)據(jù)元素域和指針域組成的一個(gè)結(jié)構(gòu)體稱為結(jié)點(diǎn)）
邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的區(qū)別：
１.邏輯結(jié)構(gòu)定義了數(shù)據(jù)元素之間的邏輯關(guān)系
２.存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中實(shí)現(xiàn)
３.一種邏輯結(jié)構(gòu)可以采用不同的存儲(chǔ)方式（順序，鏈?zhǔn)剑┐娣旁谟?jì)算機(jī)中，但都必須反映出要求的邏輯關(guān)系
一個(gè)具體問題的軟件設(shè)計(jì)通常包含三個(gè)步驟：
１、分析和確定問題的邏輯結(jié)構(gòu)和邏輯操作
２、設(shè)計(jì)該問題的具體存儲(chǔ)結(jié)構(gòu)
３、設(shè)計(jì)該問題在具體存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)算法
二、抽象數(shù)據(jù)類型和軟件構(gòu)造的方法
類型是一組值得集合
數(shù)據(jù)類型是指一個(gè)類型和定義在這個(gè)類型上的操作的集合
抽象數(shù)據(jù)類型（ADT）是指一個(gè)邏輯概念上的類型和這個(gè)類型上的操作的集合
ＡＤＴ定義包含三部分
１、數(shù)據(jù)元素
２、數(shù)據(jù)元素之間的相互關(guān)系（結(jié)構(gòu)）
３、定義在數(shù)據(jù)結(jié)構(gòu)上的一組邏輯操作
三、算法及其時(shí)間復(fù)雜度
算法是描述求解問題方法的操作步驟集合
算法的設(shè)計(jì)
１、結(jié)構(gòu)化程序設(shè)計(jì)方法：“自頂向下，逐步以模塊的形式細(xì)化”原則
２、面向?qū)ο蟪绦蛟O(shè)計(jì)方法
描述算法的語言形式：
１、文字形式
２、偽代碼形式
３、程序設(shè)計(jì)語言形式
算法分析：
評(píng)價(jià)算法好壞的標(biāo)準(zhǔn)，除算法應(yīng)該是正確的外，還應(yīng)考慮：
１.該算法是易讀、易編碼、可調(diào)試
２.該算法能有效利用計(jì)算機(jī)資源，歸結(jié)為ｃｐｕ執(zhí)行指令數(shù)和占用內(nèi)存存儲(chǔ)單元數(shù)
評(píng)價(jià)方法：
１.實(shí)驗(yàn)方法（運(yùn)行程序）
２.算法的漸進(jìn)分析，簡稱算法分析
?。ǎ保┓治鏊惴ㄏ臅r(shí)間資源——時(shí)間復(fù)雜度
?。ǎ玻┓治鏊惴ㄊ褂玫目臻g資源——空間復(fù)雜度
問題的規(guī)模
例如， “求1到100的所有素?cái)?shù)之和“ 與 “求1到1000的所有素?cái)?shù)之和” 是同一類型的問題，但問題的規(guī)模不同。
設(shè)n表示問題的規(guī)模（或算法的輸入量），則該類問題可抽象地表示為：
“求1到n的所有素?cái)?shù)之和”。
解決同樣類型的問題有多種算法，我們需要一種方法來對(duì)不同的算法來進(jìn)行比較
算法滿足以下性質(zhì)：
輸入性、輸出性、有限性、確定性、可執(zhí)行性
算法設(shè)計(jì)滿足以下目標(biāo)：
正確性、可讀性、健壯性、高時(shí)間效率、高空間效率
算法的時(shí)間復(fù)雜度還與初始輸入集有關(guān)
平均時(shí)間復(fù)雜度是指所有可能的輸入數(shù)據(jù)集均以等概率出現(xiàn)的情況下，算法的平均運(yùn)行時(shí)間。
最壞輸入數(shù)據(jù)集情況下的時(shí)間復(fù)雜度稱最壞時(shí)間復(fù)雜度。一般若無特定說明，討論的時(shí)間復(fù)雜度均指的是最壞情況下的運(yùn)行時(shí)間。
空間復(fù)雜度
數(shù)據(jù)結(jié)構(gòu)所需空間和算法在處理過程中所需額外空間的總和
它同樣是問題規(guī)模n的函數(shù)，也可以實(shí)行類似的漸進(jìn)分析方法。
大多數(shù)靜態(tài)數(shù)據(jù)結(jié)構(gòu)（即存儲(chǔ)空間在執(zhí)行過程中不發(fā)生變化），空間開銷與問題的規(guī)模成正比（為線性增長），或者不隨問題規(guī)模而增大（為常數(shù)）。
最后算法應(yīng)具有可讀性，主要體現(xiàn)在算法的符號(hào)命名和書寫規(guī)范上
