轉(zhuǎn)載請注明出處：http://www.reibang.com/p/9f23c9604a2e
數(shù)據(jù)結(jié)構(gòu)學(xué)了有一年的時(shí)間了锈颗，但是一直沒有好好的總結(jié)一下，現(xiàn)在回想起來是辕，感覺好像都不怎么記得了。所以接下來一段時(shí)間我將重新學(xué)習(xí)一下，算是溫故而知新了。本著「分享是一種美德」的精神慰于，我將把我的學(xué)習(xí)總結(jié)記錄下來，并與大家分享唤衫。
本節(jié)的主要內(nèi)容有：
- 一婆赠、數(shù)據(jù)結(jié)構(gòu)
- 1、定義
- 2佳励、關(guān)于數(shù)據(jù)結(jié)構(gòu)的幾個術(shù)語
- 3休里、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
- 二、抽象數(shù)據(jù)類型
- 三植兰、算法
- 四份帐、算法的復(fù)雜度
- 1、時(shí)間復(fù)雜度
- 2楣导、空間復(fù)雜度
一废境、數(shù)據(jù)結(jié)構(gòu)
1、定義
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲筒繁、組織數(shù)據(jù)的方式噩凹。在現(xiàn)實(shí)世界中，不同數(shù)據(jù)元素之間不是獨(dú)立的毡咏，而是存在特定關(guān)系的驮宴，我們將這些關(guān)系稱為結(jié)構(gòu)。同樣在計(jì)算機(jī)中呕缭，數(shù)據(jù)元素也不是孤立堵泽、雜亂無序的，而是具有內(nèi)在聯(lián)系的數(shù)據(jù)集合恢总。
數(shù)據(jù)元素之間存在的一種或多種特定關(guān)系迎罗，也就是數(shù)據(jù)的組織形式，叫數(shù)據(jù)結(jié)構(gòu)片仿。也可以說纹安，數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
通常情況下砂豌，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲效率厢岂。程序設(shè)計(jì)的實(shí)質(zhì)就是數(shù)據(jù)結(jié)構(gòu)和算法是設(shè)計(jì)，因此我們說程序設(shè)計(jì) = 數(shù)據(jù)結(jié)構(gòu) + 算法阳距。
2塔粒、關(guān)于數(shù)據(jù)結(jié)構(gòu)的幾個術(shù)語
-
數(shù)據(jù)：是描述客觀事物的符號，是計(jì)算機(jī)中可以操作的對象筐摘，是能被計(jì)算機(jī)識別卒茬，并輸入給計(jì)算機(jī)處理的符號集合映跟。它不僅包括整型等數(shù)值類型，還包括字符扬虚、聲音、圖像等非數(shù)值類型球恤。這些類型都具備兩個特征：
- 可以輸入計(jì)算機(jī)
- 能被計(jì)算機(jī)程序處理
數(shù)據(jù)元素：是組成數(shù)據(jù)的辜昵、有一定意義的基本單位，在計(jì)算機(jī)中通常作為整體處理咽斧。也被稱為記錄堪置。
數(shù)據(jù)項(xiàng)：一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是A數(shù)據(jù)的不可分割的最小單位张惹。舀锨。
數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集宛逗。
例如：一本書的書目信息為一個數(shù)據(jù)元素坎匿，而書目信息的每一項(xiàng)（如書名、作者名等）為一個數(shù)據(jù)項(xiàng)雷激。
3替蔬、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
按照不同的角度，數(shù)據(jù)結(jié)構(gòu)可分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)屎暇。其中邏輯結(jié)構(gòu)是面向問題的承桥，而物理結(jié)構(gòu)是面向計(jì)算機(jī)的，它們的基本目標(biāo)都是將數(shù)據(jù)及其邏輯關(guān)系存儲到計(jì)算機(jī)內(nèi)存中根悼。
- 邏輯結(jié)構(gòu)：是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系凶异。分為四種：集合結(jié)構(gòu)、線性結(jié)構(gòu)挤巡、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)剩彬。
- 物理（存儲）結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲形式。數(shù)據(jù)的存儲結(jié)構(gòu)應(yīng)正確反映數(shù)據(jù)元素之間的邏輯關(guān)系玄柏，這是關(guān)鍵襟衰。數(shù)據(jù)元素的存儲結(jié)構(gòu)可分為兩種：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。
- 順序存儲結(jié)構(gòu)：把數(shù)據(jù)元素放在地址連續(xù)的存儲單元中粪摘，數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系一致瀑晒。如，數(shù)組徘意。
- 鏈?zhǔn)酱鎯Y(jié)構(gòu)：把數(shù)據(jù)元素放在任意的存儲單元中苔悦，數(shù)據(jù)間使用指針關(guān)聯(lián)。數(shù)據(jù)元素的存儲關(guān)系不能反映其邏輯關(guān)系椎咧。如玖详，鏈表把介。
二、抽象數(shù)據(jù)類型
數(shù)據(jù)類型是指一組性質(zhì)相同的值的集合及定義在該集合上的一些操作的總稱蟋座。而抽象是指抽象出事物具有的普遍性的本質(zhì)拗踢，它是抽出問題的特征而忽略非本質(zhì)的細(xì)節(jié)，是對具體事物的一個概括向臀。抽象隱藏了繁雜的細(xì)節(jié)巢墅，只保留實(shí)現(xiàn)目標(biāo)所必須的信息。因此抽象數(shù)據(jù)類型可以定義為：
抽象數(shù)據(jù)類型（Abstract Data Type券膀，ADT）是指一個數(shù)學(xué)模型及定義在該模型上的一組操作君纫，它是一種向用例隱藏內(nèi)部表示的數(shù)據(jù)類型。
面向?qū)ο缶幊痰奶卣髦痪褪鞘褂脭?shù)據(jù)類型的實(shí)現(xiàn)封裝數(shù)據(jù)芹彬，以簡化實(shí)現(xiàn)蓄髓、隔離用例開發(fā)、實(shí)現(xiàn)模塊化編程舒帮。抽象數(shù)據(jù)類型體現(xiàn)了程序設(shè)計(jì)中問題分解会喝、抽象和信息隱藏的特性。它將實(shí)際生活中的問題分解為多個規(guī)模小玩郊、能夠獨(dú)立開發(fā)和調(diào)試的小型模塊好乐，然后進(jìn)行獨(dú)立編程。這種方式將代碼的影響限制在局部區(qū)域瓦宜，改進(jìn)了我們的軟件質(zhì)量蔚万，促進(jìn)了代碼復(fù)用。抽象數(shù)據(jù)類型抽象的層次越高临庇，那么可復(fù)用性也越強(qiáng)反璃。比如：java中的Object是對所有對象的抽象。
java中數(shù)據(jù)類型可以分為兩類：
- 基本（原子）類型：不可以再分解的基本類型假夺，包括int淮蜈、short、long等
- 引用（結(jié)構(gòu)）類型：由其他類型組合而成已卷，可以再分解梧田。如，String侧蘸、數(shù)組等
注意：
- 對原子類型的操作不一定是原子操作裁眯，這點(diǎn)并發(fā)編程時(shí)應(yīng)特別注意。如讳癌，在32位機(jī)上對long類型的操作就不是原子操作穿稳，因?yàn)槠涓?2位和低32位是分別存儲的。
- Java中所有的基本數(shù)據(jù)類型都有固定的存儲范圍和大小晌坤，其不受具體機(jī)器和操作系統(tǒng)的影響逢艘。
三旦袋、算法
算法（Algorithm)一詞最早出現(xiàn)在波斯數(shù)學(xué)家al-Khwarizmi所寫的《印度數(shù)字算術(shù)》中。歐幾里得算法（求兩個整數(shù)的最大公約數(shù)）被認(rèn)為是史上第一個算法它改。
算法是解決特定問題求解步驟的描述疤孕，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個或多個操作央拖。
算法的基本特性：
- 輸入輸出胰柑，算法具有零個或多個輸入，至少有一個或多個輸出爬泥。
- 有窮性，算法在執(zhí)行有限步后能夠自動結(jié)束崩瓤，不會出現(xiàn)無限循環(huán)袍啡。
- 確定性，算法的每一步都具有確定的含義却桶，不會出現(xiàn)二義性境输。
- 可行性，算法的每一步都能夠通過執(zhí)行有限次操作完成颖系。
程序與算法的區(qū)別：
程序（program）是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的嗅剖、用程序設(shè)計(jì)語言描述的適合計(jì)算機(jī)執(zhí)行的指令（語句）序列。它包括「數(shù)據(jù)結(jié)構(gòu)」嘁扼、「算法」信粮、「程序設(shè)計(jì)方法」和「編程語言」。程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)趁啸。程序可以不滿足算法的有窮性强缘，比如操作系統(tǒng)也是一種程序，它可以一直運(yùn)行不傅。
算法的設(shè)計(jì)要求：
- 正確性旅掂，算法至少應(yīng)該具有輸入、輸出和加工處理無歧義访娶、能正確反映問題的需求商虐、能夠得到問題的正確答案。
- 可讀性崖疤，便于閱讀秘车、理解和交流。
- 健壯性劫哼，輸入不合法時(shí)鲫尊，算法能夠給出相應(yīng)的處理，而不是產(chǎn)生錯誤的結(jié)果沦偎。
- 高效性疫向，算法應(yīng)該盡量滿足高效率和低存儲的需求咳蔚。
四、算法的復(fù)雜度
算法復(fù)雜度分為時(shí)間復(fù)雜度和空間復(fù)雜度搔驼。其作用： 時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量谈火；而空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。
1舌涨、時(shí)間復(fù)雜度
算法的時(shí)間復(fù)雜度反映了算法執(zhí)行的時(shí)間長短糯耍，它是度量一個算法好壞的重要指標(biāo)。
一般情況下囊嘉，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)温技，用T(n)表示，若有某個輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)扭粱，T(n)/f(n)的極限值為不等于零的常數(shù)舵鳞，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度琢蛤，簡稱時(shí)間復(fù)雜度蜓堕。
度量一個算法的時(shí)間復(fù)雜度通常有兩種方式：
- 事后統(tǒng)計(jì)法
- 事前分析法(大O表示法)
算法的時(shí)間復(fù)雜度是由最深層嵌套語句的頻度決定的。
大O表示法的推導(dǎo)：
- 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)
- 在修改后的運(yùn)行次數(shù)函數(shù)中博其，只保留最高階
- 將最高階系數(shù)變?yōu)?
例1:
int i, j, temp;
for(i=0; i<n; i++) {
for(j=i, j<n; j++) {
temp++;
}
}
語句執(zhí)行的總次數(shù)：
所以其時(shí)間復(fù)雜度為O(n^2)套才。
例2:
for(i=1;i<=n;i=i*2){
System.out.println(i);
}
執(zhí)行的總次數(shù)滿足：
所以它的時(shí)間復(fù)雜度為O(logn)
例3：分析冒泡排序算法的時(shí)間復(fù)雜度
//冒泡排序算法
public static void bubbleSort(int[] data) {
if (data == null) {
return;
}
int temp = 0;
for (int i = data.length - 1; i > 0; --i){
for (int j = 0; j < i; ++j){
if (data[j + 1] < data[j]){
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}
算法分析：
- 最佳情況下（初始狀態(tài)是正序時(shí)），冒泡排序算法只需要一次掃描即可完成排序慕淡，此時(shí)比較次數(shù) C_min = n - 1背伴，移動次數(shù) M_min = 0，所以時(shí)間復(fù)雜度為 O(n)
- 最差情況下（初始狀態(tài)為逆序時(shí)）峰髓，需要進(jìn)行 n-1 次排序挂据，每次排序進(jìn)行 n-1 比較，此時(shí)比較次數(shù) C_max = n(n+1)/2儿普，移動次數(shù) M_max = 3n(n+1)/2崎逃，所以時(shí)間復(fù)雜度為 O(n^2)
常見時(shí)間復(fù)雜度大小關(guān)系：
算法的時(shí)間復(fù)雜度和兩個因素有關(guān)：算法中的最大嵌套循環(huán)層數(shù)；最大嵌套循環(huán)結(jié)構(gòu)中每次循環(huán)的次數(shù)眉孩。一般來說个绍，具有多項(xiàng)式時(shí)間復(fù)雜度的算法是可以接受的；具有指數(shù)時(shí)間復(fù)雜度的算法浪汪，只有當(dāng)n足夠小時(shí)才可以使用巴柿。一般效率較好的算法要控制在 O(N)或者O(log2 N)
2、空間復(fù)雜度
空間復(fù)雜度(Space Complexity)是對一個算法在運(yùn)行過程中臨時(shí)占用存儲空間大小的量度死遭，記做S(n)=O(f(n))广恢。其中，n為問題規(guī)模呀潭，f(n)為語句關(guān)于n所占存儲空間的函數(shù)钉迷。
算法的空間復(fù)雜度分析方法和算法的時(shí)間復(fù)雜度分析方法基本相同至非。
例如:
int i, j, temp;
for(i=0; i<n; i++) {
for(j=i, j<n; j++) {
temp++;
}
}
上方代碼中，僅需為變量 i糠聪、j荒椭、temp分配空間即可，所以空間復(fù)雜度 S(n) = O(1)舰蟆。
參考
- 《大話數(shù)據(jù)結(jié)構(gòu)》
- 《算法》第四版
- 數(shù)據(jù)結(jié)構(gòu)Java實(shí)現(xiàn)01----算法概述
