一、數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)：計算機(jī)存儲、組織數(shù)據(jù)的方式。是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

1 、概念術(shù)語：

?數(shù)據(jù)：是可以被自算計處理的符號或符號集合

?數(shù)據(jù)對象: 性質(zhì)相同的數(shù)據(jù)元素的集合

數(shù)據(jù)元素: 數(shù)據(jù)的基本單位

數(shù)據(jù)項: 組成數(shù)據(jù)元素的最小單位

他們之間的關(guān)系如下圖：

數(shù)據(jù)結(jié)構(gòu)

代碼：

2、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

2.1、邏輯結(jié)構(gòu)：數(shù)據(jù)對象中的數(shù)據(jù)元素之間的相互關(guān)系。邏輯結(jié)構(gòu)分為四種：集合結(jié)構(gòu),線性結(jié)構(gòu),樹形結(jié)構(gòu),圖形結(jié)構(gòu).

集合結(jié)構(gòu): 集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個集合外,它們之間沒有其他關(guān)系. 各個數(shù)據(jù)元素是"平等"的. 它們的共同屬性是:"同屬于一個集合".

線性結(jié)構(gòu): 線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對一的關(guān)系.常用的線性結(jié)構(gòu)有：線性表，棧，隊列，雙隊列，數(shù)組，串

樹型結(jié)構(gòu): 重要的非線性數(shù)據(jù)結(jié)構(gòu)。樹形數(shù)據(jù)結(jié)構(gòu)可以表示數(shù)據(jù)表素之間一對多的關(guān)系.樹型結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對多的層次關(guān)系.?常見的樹形結(jié)構(gòu): 二叉樹,B樹,哈夫曼樹,紅黑樹等.

圖形結(jié)構(gòu): 圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對多的關(guān)系.?常見的圖形結(jié)構(gòu): 鄰近矩陣,鄰接表.

2.2、物理結(jié)構(gòu)：別稱"存儲結(jié)構(gòu)". 顧名思義,指的是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)的存儲形式.包含：順序存儲和鏈?zhǔn)酱鎯?

順序存儲：是指把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里,其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的.

順序存儲

鏈?zhǔn)酱鎯Γ菏前褦?shù)據(jù)元素放在任意的存儲單元里,這組存儲單元可以是連續(xù)的,也可以是不連續(xù)的. 數(shù)據(jù)元素的存儲關(guān)系并不能反映邏輯關(guān)系,因此需要用一個指針存放數(shù)據(jù)元素的地址,這樣通過地址就可以找到相關(guān)關(guān)聯(lián)數(shù)據(jù)元素的位置.

鏈?zhǔn)酱鎯?/div>

二者優(yōu)劣：順序存儲方便查找數(shù)據(jù)，鏈?zhǔn)酱鎯Ρ阌趧h除和增加數(shù)據(jù)

二、算法

算法：是解決特定問題求解步驟的描述,在計算機(jī)中表現(xiàn)為指令的有限序列,并且每條指令表示一個或多個操作.

1、算法特性

輸入:? 算法具有零個或多個輸入

輸出:? 算法至少有一個或多個輸出

有窮行: 算法可以在某一個條件下自動結(jié)束而不是出現(xiàn)無限循環(huán)

確定性: 算法執(zhí)行的每一步驟在一定條件下只有一條執(zhí)行路徑，一個相同的輸入對應(yīng)相同的一個輸出

可行性: 算法每一步驟都必須可行，能夠通過有限的執(zhí)行次數(shù)完成

2、算法需求

正確性

可讀性

健壯性

時間效率高和存儲量低

2.1、時間效率的判斷方法（大O表示法）

時間復(fù)雜度

代碼示例：

1、常數(shù)階：

常數(shù)階

2、線性階：

線性階

3、對數(shù)階：

對數(shù)階

4、平方階：

平方階

5、立方階：

立方階

2.2、程序空間復(fù)雜度判斷：主要考慮算法執(zhí)行是所需的輔助空間