學數(shù)據(jù)結(jié)構(gòu)之前必備基礎知識列表
（部分摘抄自《大話數(shù)據(jù)結(jié)構(gòu)》如果有不清楚的地方可以參看原書第一章）
-
數(shù)據(jù)：描述客觀事物的符號，是計算機中可以操作的對象，是能被計算機識別并輸入給計算機處理的符號集合。
- 可以輸入到計算機中
- 能被計算機程序處理
數(shù)據(jù)元素：是組成數(shù)據(jù)的，有一定意義的基本代為，在計算機中通常作為整體處理，也被稱為記錄，如雞，鴨，人，都是數(shù)據(jù)元素
數(shù)據(jù)項： 一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是數(shù)據(jù)結(jié)構(gòu)中不可分割的最小單位， 如眼，耳，鼻等。
數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集，有時也簡稱數(shù)據(jù)或等同于數(shù)據(jù)
數(shù)據(jù)結(jié)構(gòu):是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合，在計算機中，數(shù)據(jù)元素并不是孤立，雜亂無序的，而是具有內(nèi)在聯(lián)系的數(shù)據(jù)集合，數(shù)據(jù)元素之間存在的一種或多種特定的關系，也是數(shù)據(jù)的組織形式。
-
邏輯結(jié)構(gòu)：數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關系，種類如下
- 集合結(jié)構(gòu)：處于同一個集合中
- 線性結(jié)構(gòu)：一對一線性結(jié)構(gòu)（列表等 ）
- 樹形結(jié)構(gòu)：二叉樹等一對多關系
- 圖形結(jié)構(gòu)：多對多結(jié)構(gòu)（有向圖）
-
物理結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲形式，種類如下：
- 順序存儲結(jié)構(gòu)： 是吧數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里，其數(shù)據(jù)的邏輯關系核物理關系是一致的
- 鏈式存儲結(jié)構(gòu)： 把數(shù)據(jù)存儲在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的，這就需要一個指針指向存放的地址，通過地址找到相應的元素
算法的定義： 解決特定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列，并且每條指令表示一個或多個操作
算法的簡單案例 1-100求和：
- 算法一：
int sum = 0,n=100;
for(int i=1;i<=n;i++){
sum += i;
}
print("%d",sum); //5050
- 算法二：
int sum=0,n=100;
sum = (1 + n) * n / 2;
print("%d",sum);
從簡單的案例可以看出兩種算法結(jié)果雖然是一樣的，可是算法一執(zhí)行了n次， 算法二卻只執(zhí)行了三句，不同的算法之間的效率顯而易見，算法二極大提高了效率，減少了計算機資源的消耗，讓程序更加精簡，高效。這也是我們學習數(shù)據(jù)結(jié)構(gòu)與算法最直接的目的。
- 算法的特性：
- 輸入：輸入零個，一個或多個
- 輸出：一定要有一個或多個輸出
- 有窮性：指算法在執(zhí)行有限的步驟之后自動結(jié)束而不會出現(xiàn)無限循環(huán)
- 確定性：算法的每一步都具有確定含義
- 可行性:算法的每一步必須是可行的
- 算法的設計要求：
- 正確性：沒有語法錯誤，對于正確的輸入數(shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果，對非法的輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果
- 可讀性：便于閱讀，理解和交流
- 健壯性：當輸入數(shù)據(jù)不合法時，算法也能做出相關處理，而不是產(chǎn)生異?；蚰涿畹慕Y(jié)果
- 時間效率高和存儲量低：及花費時間越少，占用空間越少
-
算法效率的度量方法(重點)：時間復雜度
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
