1. 數(shù)據(jù)結(jié)構(gòu)+算法=程序設(shè)計
程序設(shè)計：為計算機(jī)處理問題編制一組指令集
算法：處理問題的策略
數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型
2.基本概念
- 數(shù)據(jù)結(jié)構(gòu)包括：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)
- 邏輯結(jié)構(gòu)：(1). 集合 (2)線性結(jié)構(gòu) (3)樹形結(jié)構(gòu) (4)網(wǎng)狀結(jié)構(gòu)
++集合++：結(jié)構(gòu)中除了“同屬于一個集合”外沒有別的關(guān)系
++線性結(jié)構(gòu)++：數(shù)據(jù)元素之間存在一對一的關(guān)系
++樹形結(jié)構(gòu)++：數(shù)據(jù)元素存在一對多的關(guān)系
++網(wǎng)狀結(jié)構(gòu)++：數(shù)據(jù)元素一對多的關(guān)系
- 物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的儲存方式
(1)順序儲存結(jié)構(gòu)(2)鏈?zhǔn)絻Υ娼Y(jié)構(gòu)
++順序儲存結(jié)構(gòu)++
++鏈?zhǔn)絻Υ娼Y(jié)構(gòu)++
數(shù)據(jù)類型：體格值的集合和定義在這個值集上的一組操作
抽象數(shù)據(jù)類型(ADT)：指一個數(shù)學(xué)模型以及定義在該模型上的一組操作
ADT的定義格式
**ADT抽象數(shù)據(jù)類型名**{
**數(shù)據(jù)對象**：<數(shù)據(jù)對象的定義>
**數(shù)據(jù)關(guān)系**：<數(shù)據(jù)關(guān)系的定義>
**基本操作**：<數(shù)據(jù)對象的定義>
}
基本操作名（參數(shù)表）{
初始條件（初始條件的描述）
操作結(jié)果（操作結(jié)果的描述）
}
3.算法和算法分析
-
算法的5個特性
（1）有窮性：有窮步結(jié)束而且每一步時間合理
（2）確定性：指令要有確切的含義露该，只有唯一的一條執(zhí)行路徑
（3）可行性：足夠基本
（4）輸入：有0個或者多個輸入
（5）輸出：有一個或者多個輸出
-
算法的4個設(shè)計要求
（1）正確性
四個層次：a.程序不含語法錯誤b.程序?qū)τ趲捉M輸入數(shù)據(jù)能得到滿足規(guī)格的結(jié)果c.程序?qū)τ谝恍┑箅y苛刻的輸入能得出滿足規(guī)格結(jié)果d.程序?qū)τ谝磺泻戏ㄝ斎攵寄艿玫綕M足規(guī)格的結(jié)果（2）可讀性
（3）健壯性
（4）效率與低存儲性
-
算法效率的度量--------- ==++時間復(fù)雜度++==
（1）事后統(tǒng)計方法
（2）事前統(tǒng)計方法
a.依據(jù)算法選用何種策略
b.問題規(guī)模 -
算法儲存空間需求-------- ==++空間復(fù)雜度++==
（1）輸入數(shù)據(jù)所需空間
（2）程序本身所占空間
（3）輔助變量所占空間
