摘要：數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)構(gòu)成可認(rèn)為是一個(gè)對(duì)象或者是數(shù)據(jù)庫的一條記錄。抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是一個(gè)實(shí)現(xiàn)包括儲(chǔ)存數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)以及實(shí)現(xiàn)基本操作的算法。

重要性

數(shù)據(jù)結(jié)構(gòu)與算法是程序員內(nèi)功體現(xiàn)的重要標(biāo)準(zhǔn)之一，而數(shù)據(jù)結(jié)構(gòu)的也應(yīng)用在各個(gè)方面，更有程序=數(shù)據(jù)結(jié)構(gòu)+算法這個(gè)等式存在。各個(gè)中間件開發(fā)者，架構(gòu)師。他們都在努力的優(yōu)化中間件、項(xiàng)目結(jié)構(gòu)以及算法提高運(yùn)行效率降低內(nèi)存占用。并且數(shù)據(jù)結(jié)構(gòu)中也是蘊(yùn)含模型以及面向?qū)ο蟮乃枷耄莆諗?shù)據(jù)結(jié)構(gòu)對(duì)邏輯思維處理抽象能力有很大提升。。

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲(chǔ)效率。

簡(jiǎn)言之，數(shù)據(jù)結(jié)構(gòu)是一系列的存儲(chǔ)結(jié)構(gòu)按照一定執(zhí)行規(guī)則、配合一定執(zhí)行算法所形成的高效的存儲(chǔ)結(jié)構(gòu)。在我們所熟知的關(guān)系數(shù)據(jù)庫、非關(guān)系數(shù)據(jù)庫、搜索引擎存儲(chǔ)、消息隊(duì)列等都是比較牛的大型數(shù)據(jù)結(jié)構(gòu)良好的運(yùn)用。這些數(shù)據(jù)結(jié)構(gòu)應(yīng)用不僅僅考慮到內(nèi)存范圍結(jié)構(gòu)設(shè)計(jì)。還考慮實(shí)際os、網(wǎng)絡(luò)等其他因素。

而對(duì)于數(shù)據(jù)結(jié)構(gòu)與算法這個(gè)專欄。我們程序員更改掌握的首先是在內(nèi)存中運(yùn)行的抽象的數(shù)據(jù)結(jié)構(gòu)。是一個(gè)相對(duì)比較單一的數(shù)據(jù)結(jié)構(gòu)類型，比如線性結(jié)構(gòu)、樹、圖等等.

用戶信息表users

users的pojo對(duì)象

class users
{ 
     //略
     int id;
     String name;
     String sex;
}
//list和woman是數(shù)據(jù)
Listlist;//數(shù)據(jù)對(duì)象list
Listwoman;//數(shù)據(jù)對(duì)象woman
list.add(new users(001,"bigsai","man"));//添加數(shù)據(jù)元素 一個(gè)users由（001，bigsai，man）三個(gè)數(shù)據(jù)項(xiàng)組成 
list.add(new users(002,"smallsai","man"));//數(shù)據(jù)元素
list.add(new users(003,"菜虛鯤","woman"));//數(shù)據(jù)元素
woman.add(list.get(2));//003,"菜虛鯤","woman"三個(gè)數(shù)據(jù)項(xiàng)構(gòu)成的一個(gè)數(shù)據(jù)元素

數(shù)據(jù)：對(duì)客觀事物的符號(hào)表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合總稱。

上述表中的三條用戶信息的記錄就是數(shù)據(jù)(也可能多表多集合)。這些數(shù)據(jù)一般都是用戶輸入或者是自定義構(gòu)造完成。當(dāng)然，還有一些圖像、聲音也是數(shù)據(jù)。

數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)構(gòu)成！可認(rèn)為是一個(gè)pojo對(duì)象、或者是數(shù)據(jù)庫的一條記錄。比如菜虛鯤那條記錄就是一個(gè)數(shù)據(jù)元素。

數(shù)據(jù)項(xiàng)： 而構(gòu)成用戶字段/屬性的有id、name、sex等，這些就是數(shù)據(jù)項(xiàng).數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)元素的最小不可分割字段?？梢钥醋饕粋€(gè)pojo對(duì)象或者一張表(people)的一個(gè)屬性/字段的值。

數(shù)據(jù)對(duì)象：是相同性質(zhì)數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。比如上面的users表、list集合、woman集合都是數(shù)據(jù)對(duì)象。多帶帶一張表，一個(gè)集合都可以是一個(gè)數(shù)據(jù)對(duì)象。

數(shù)據(jù)類型

原子類型：其值不可再分的類型。比如int，char，double，float等。

結(jié)構(gòu)類型：其值可以再分為若干成分的數(shù)據(jù)類型。比如結(jié)構(gòu)體構(gòu)造的各種結(jié)構(gòu)等。

抽象數(shù)據(jù)類型(ADT)：抽象數(shù)據(jù)類型（ADT）是一個(gè)實(shí)現(xiàn)包括儲(chǔ)存數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)以及實(shí)現(xiàn)基本操作的算法。使得只研究和使用它的結(jié)構(gòu)而不用考慮它的實(shí)現(xiàn)細(xì)節(jié)成為可能。比如我們使用Arraylist。二叉樹等等只需要new 一個(gè)而不需要去具體考慮他的內(nèi)部實(shí)現(xiàn)方式。只需要了解他的api和性質(zhì)即可。其實(shí)各個(gè)框架的思想也是這樣，對(duì)數(shù)據(jù)、接口進(jìn)行封裝、繼承使得我們只需要會(huì)用而不需要弄清楚它的具體實(shí)現(xiàn)細(xì)節(jié)。

邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)就是順序表、鏈表之類。而非線性就是集合、樹、圖這些結(jié)構(gòu)。

存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(又稱映像，也稱物理結(jié)構(gòu))，存儲(chǔ)結(jié)構(gòu)主要分為順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列(哈希)存儲(chǔ)。

數(shù)據(jù)的運(yùn)算：施加在數(shù)據(jù)上的運(yùn)算包括運(yùn)算的定義和實(shí)現(xiàn),運(yùn)算的定義基于邏輯結(jié)構(gòu)，運(yùn)算的實(shí)現(xiàn)基于存儲(chǔ)結(jié)構(gòu)。

在這里容易混淆的是邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的概念。對(duì)于邏輯結(jié)構(gòu)，不難看得出邏輯二字。邏輯關(guān)系也就是兩者存在數(shù)據(jù)上的關(guān)系而不考慮物理地址的關(guān)系。比如線性結(jié)構(gòu)和非線性結(jié)構(gòu)，它描述的是一組數(shù)據(jù)中的聯(lián)系方式和形式，他針對(duì)的是數(shù)據(jù)。而存儲(chǔ)結(jié)構(gòu)就是跟物理地址掛鉤的。比如同樣是線性表,可能有多種存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)方式。比如順序表和鏈表(Arraylist,Linkedlist)它們的存儲(chǔ)結(jié)構(gòu)就不同并且采用不同存儲(chǔ)結(jié)構(gòu)在不同場(chǎng)景計(jì)算機(jī)運(yùn)算次數(shù)和效率不同。它關(guān)注的是計(jì)算機(jī)物理地址與運(yùn)行具體實(shí)現(xiàn)方式。

至于算法的概念，傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)介紹都會(huì)有：有窮性、確定性、可行性、輸入、輸出。這些從字面意思即可理解。

而一個(gè)好的算法，通常更要著重考慮的是效率和空間資源占用。

通常復(fù)雜度更多描述的是一個(gè)量級(jí)程度而很少用具體數(shù)字描述。

概念：是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度，記做S(n)=O(f(n))

空間復(fù)雜度其實(shí)在算法的衡量占比是比較低的，但是不能忽視空間復(fù)雜度中重要性。無論在刷題還是實(shí)際項(xiàng)目生產(chǎn)內(nèi)存都是一個(gè)極大額指標(biāo)。對(duì)于java而言更是如此。本身內(nèi)存就大，如果采用的存儲(chǔ)邏輯不太好會(huì)占用更多的系統(tǒng)資源，對(duì)服務(wù)造成壓力。

而算法很多情況都是犧牲空間換取時(shí)間(效率)。就比如我們熟知的字符串匹配String.contains()方法，我們都知道他是暴力破解，時(shí)間復(fù)雜度為O(n^2^),不需要借助額外內(nèi)存。而KMP算法在效率和速度上都原生暴力方法，但是KMP要借助其他數(shù)組(next[])進(jìn)行標(biāo)記儲(chǔ)存運(yùn)算。就用到了空間開銷。再比如歸并排序也會(huì)借助新數(shù)組在遞歸分冶的適合進(jìn)行逐級(jí)計(jì)算。提高效率，而增加內(nèi)存開銷。

當(dāng)然，你的時(shí)間算法的空間花銷最大不能超過jvm設(shè)置的最大值，一般為2G.(2147483645)如果開二維數(shù)組多種多維數(shù)據(jù)不要開的太大，可能會(huì)導(dǎo)致heap OutOfMemoryError。

概念：計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定性描述了該算法的運(yùn)行時(shí)間。這是一個(gè)關(guān)于代表算法輸入值的字符串的長(zhǎng)度的函數(shù)。時(shí)間復(fù)雜度常用大O符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，它考察當(dāng)輸入值大小趨近無窮時(shí)的情況。

時(shí)間復(fù)雜度的排序：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2^) < O(n^3^) < O(2^n^)

常見時(shí)間復(fù)雜度：對(duì)于時(shí)間復(fù)雜度，很多人的概念是比較模糊的。下面舉例子說明一些時(shí)間復(fù)雜度。

O(1): 常數(shù)函數(shù)

a=15

O(logn): 對(duì)數(shù)函數(shù)

for(int i=1;i