第一章 緒論
1.1 計算機研究的問題
數(shù)值計算： 解決數(shù)學(xué)問題
-
非數(shù)值計算：管理系統(tǒng)（數(shù)據(jù)結(jié)構(gòu)）
DS（Data structure）:是一門非數(shù)值計算程序的操作對象厉颤，以及這些對象之間關(guān)系和操作的學(xué)科（增刪改查）美旧。
1.2 數(shù)據(jù)、數(shù)據(jù)元素渔肩、數(shù)據(jù)項和數(shù)據(jù)對象
- 數(shù)據(jù)：客觀事物的符號表示 因俐，能輸入到計算里面的，并能被計算機識別處理的總稱周偎。（一整張學(xué)生表都是數(shù)據(jù)）
- 數(shù)據(jù)元素：數(shù)據(jù)的基本單位抹剩。（如一條記錄）完整的描述。
- 數(shù)據(jù)項：組成數(shù)據(jù)元素栏饮、獨立吧兔、不可分割的最小單位。
- 數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合袍嬉，數(shù)據(jù)的子集倦炒。
數(shù)據(jù)結(jié)構(gòu)（DR）(DS)：
- 數(shù)據(jù)元素的集合
- 數(shù)據(jù)元素之間存在一種或者多種關(guān)系的集合
數(shù)據(jù)元素+結(jié)構(gòu)
結(jié)構(gòu)（邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)）
-
邏輯結(jié)構(gòu)（給人看） 從邏輯上描述數(shù)據(jù)幢竹，與數(shù)據(jù)存儲無關(guān)，是獨立于計算機的。
線性結(jié)構(gòu) O---O----O----O O元素 ----關(guān)系 （1對1）
樹結(jié)構(gòu)（一對多）
圖結(jié)構(gòu)或者網(wǎng)狀結(jié)構(gòu)（多對多）
集合結(jié)構(gòu) （0對0）
邏輯 分成兩大類
線性結(jié)構(gòu) 棧劫笙、隊列贯吓，線性表，串?dāng)?shù)組沟堡，廣義表
非線性結(jié)構(gòu)：樹矢空，二叉樹，圖粥血，有向圖，無向圖复亏，集合
<img src="https://i.loli.net/2020/05/22/2IwURqcBiFulQma.jpg" />
-
存儲結(jié)構(gòu)（物理結(jié)構(gòu)）（給機器看） 數(shù)據(jù)對象在計算機的存儲表示
- 順序存儲
- 鏈?zhǔn)酱鎯?/li>
數(shù)據(jù)類型
- 基本類型
- 自定義（結(jié)構(gòu)體）
抽象數(shù)據(jù)類型
1數(shù)據(jù)對象：集合D
2數(shù)據(jù)關(guān)系：S
3基本操作：P
舉例 ADT（abstract data type）=(DSP) studentList
D數(shù)據(jù)對象{a,b,c,d}
S數(shù)據(jù)關(guān)系{<a,b><b,c><a,d>}
P基本操作
- 實例化操作
- 添加學(xué)生
- 刪除學(xué)生
- 修改學(xué)生
- 查找學(xué)生
算法
- 解決問題的有限操作序列（操作步驟）
算法的重要特征：
- 有窮性：每一步都在有窮時間內(nèi)完成
- 確定性：確切的規(guī)定缔御，不產(chǎn)生二義性
- 可行性：要由可實現(xiàn)的基本操作執(zhí)行運算有限次來實現(xiàn)
- 輸入：0或者多個輸入
- 輸出：1個或者多個輸出
評價算法的基本標(biāo)準(zhǔn)
- 正確性
- 可讀性
- 健壯性
- 高效性：時間快------- 空間內(nèi)存少
評價算法的時間復(fù)雜度
- 算法的執(zhí)行時間大致等于所有語句執(zhí)行時間的總和
- 事前統(tǒng)計法
- 事后統(tǒng)計
語句頻度：一條語句重復(fù)的次數(shù)
-
常量階：語句頻度是固定的.
a=1; b=2;c=3; //或者 for(int i=0;i<100;i++) { x++; a++; } //時間復(fù)雜度 = O(1);
2.線性階：
for(int i=0;i<n;i++)
{
x++;
}
//時間復(fù)雜度 = O(n); 線性階
- 平方階
for(int i=0;i<n;i++)
{
for(int j=0;j<n;i++)
{
x++;
}
}
//時間復(fù)雜度 = O(n^2);
- 立方階
for(int i=0;i<n;i++)
{
for(int j=0;j<n;i++)
{
for(int j=0;j<n;i++)
{
x++;
}
}
}
//時間復(fù)雜度 = O(n^3);
- 對數(shù)階
for(int i=0;i<n;i=i*2)
{
x++;
}
對數(shù)階的時間復(fù)雜度為
空間復(fù)雜度
- 用到多少輔助空間
例如將數(shù)組a 進(jìn)行倒序
算法1 a 給b 再給a 用到了輔助空間b -------- 空間復(fù)雜度 O(n)
算法2 a中 首尾交換 只用了一個輔助空間temp ------- 空間復(fù)雜度O(1)
