一、數(shù)據(jù)結(jié)構(gòu)和算法概述

1.1什么是數(shù)據(jù)結(jié)構(gòu)？

官方解釋：
數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中的操作對象，以及他們之間的關(guān)系和操作等相關(guān)問題的學(xué)科。
大白話：
數(shù)據(jù)結(jié)構(gòu)就是把數(shù)據(jù)元素按照一定的關(guān)系組織起來的集合，用來組織和存儲數(shù)據(jù)

1.2數(shù)據(jù)結(jié)構(gòu)分類
傳統(tǒng)上，我們可以把數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩大類。
邏輯結(jié)構(gòu)分類：
邏輯結(jié)構(gòu)是從具體問題中抽象出來的模型，是抽象意義上的結(jié)構(gòu)，按照對象中數(shù)據(jù)元素之間的相互關(guān)系分類，也是
我們后面課題中需要關(guān)注和討論的問題。
a.集合結(jié)構(gòu)：集合結(jié)構(gòu)中數(shù)據(jù)元素除了屬于同一個(gè)集合外，他們之間沒有任何其他的關(guān)系。

b.線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系
?

?

?c.樹形結(jié)構(gòu)：樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的層次關(guān)系

d.圖形結(jié)構(gòu)：圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對多的關(guān)系

物理結(jié)構(gòu)分類：?

邏輯結(jié)構(gòu)在計(jì)算機(jī)中真正的表示方式（又稱為映像）稱為物理結(jié)構(gòu)，也可以叫做存儲結(jié)構(gòu)。常見的物理結(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ù)組就是順序存儲結(jié)構(gòu)。

順序存儲結(jié)構(gòu)存在一定的弊端，就像生活中排時(shí)也會有人插隊(duì)也可能有人有特殊情況突然離開，這時(shí)候整個(gè)結(jié)構(gòu)都處于變化中，此時(shí)就需要鏈?zhǔn)酱鎯Y(jié)構(gòu)。
鏈?zhǔn)酱鎯Y(jié)構(gòu)：
是把數(shù)據(jù)元素存放在任意的存儲單元里面，這組存儲單元可以是連續(xù)的也可以是不連續(xù)的。此時(shí)，數(shù)據(jù)元素之間并
不能反映元素間的邏輯關(guān)系，因此在鏈?zhǔn)酱鎯Y(jié)構(gòu)中引進(jìn)了一個(gè)指針存放數(shù)據(jù)元素的地址，這樣通過地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置?

什么是算法？?

官方解釋：
算法是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法解決問題的策略
機(jī)制。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。
大白話：根據(jù)一定的條件，對一些數(shù)據(jù)進(jìn)行計(jì)算，得到需要的結(jié)果。

算法初體驗(yàn)

在生活中，我們?nèi)绻龅侥硞€(gè)問題，常常解決方案不是唯一的。
例如從西安到北京，如何去？會有不同的解決方案，我們可以坐飛機(jī)，可以坐火車，可以坐汽車，甚至可以步行，不同的解決方案帶來的時(shí)間成本和金錢成本是不一樣的，比如坐飛機(jī)用的時(shí)間最少，但是費(fèi)用最高，步行費(fèi)用最低，但時(shí)間最長。

再例如在北京二環(huán)內(nèi)買一套四合院，如何付款？也會有不同的解決方案，可以一次性現(xiàn)金付清，也可以通過銀行做按揭。這兩種解決方案帶來的成本也不一樣，一次性付清，雖然當(dāng)時(shí)出的錢多，壓力大，但是沒有利息，按揭雖然當(dāng)時(shí)出的錢少，壓力比較小，但是會有利息，而且30年的總利息幾乎是貸款額度的一倍，需要多付錢。在程序中，我們也可以用不同的算法解決相同的問題，而不同的算法的成本也是不相同的。

總體上，一個(gè)優(yōu)秀的算法追求以下兩個(gè)目標(biāo)：
1.花最少的時(shí)間完成需求；
2.占用最少的內(nèi)存空間完成需求；
下面我們用一些實(shí)際案例體驗(yàn)一些算法。
需求1：
計(jì)算1到100的和。
第一種解法：

public static void main(String[] args) {
int sum = 0;
int n=100;
for (int i = 1; i <= n; i++) {
sum += i;
}
System.out.println("sum=" + sum);
}

第二種解法：

public static void main(String[] args) {
int sum = 0;
int n=100;
sum = (n+1)*n/2;
System.out.println("sum="+sum);
}

第一種解法要完成需求，要完成以下幾個(gè)動作：
1.定義兩個(gè)整型變量；
2.執(zhí)行100次加法運(yùn)算；
3.打印結(jié)果到控制臺；

第二種解法要完成需求，要完成以下幾個(gè)動作：
1.定義兩個(gè)整型變量；
2.執(zhí)行1次加法運(yùn)算，1次乘法運(yùn)算，一次除法運(yùn)算，總共3次運(yùn)算；
3.打印結(jié)果到控制臺；
很明顯，第二種算法完成需求，花費(fèi)的時(shí)間更少一些。
需求2：
計(jì)算10的階乘
第一種解法：

public class Test {
public static void main(String[] args) {
//測試，計(jì)算10的階乘
long result = fun1(10);
System.out.println(result);
}
//計(jì)算n的階乘
public static long fun1(long n){
if (n==1){
return 1;
}
return n*fun1(n-1);
}
}

第二種解法：

public class Test {
public static void main(String[] args) {
//測試，計(jì)算10的階乘
long result = fun2(10);
System.out.println(result);
}
//計(jì)算n的階乘
public static long fun2(long n){
int result=1;
for (long i = 1; i <= n; i++) {
result*=i;
}
return result;
}
}

第一種解法，使用遞歸完成需求，fun1方法會執(zhí)行10次，并且第一次執(zhí)行未完畢，調(diào)用第二次執(zhí)行，第二次執(zhí)行未完畢，調(diào)用第三次執(zhí)行...最終，最多的時(shí)候，需要在棧內(nèi)存同時(shí)開辟10塊內(nèi)存分別執(zhí)行10個(gè)fun1方法。

第二種解法，使用for循環(huán)完成需求，fun2方法只會執(zhí)行一次，最終，只需要在棧內(nèi)存開辟一塊內(nèi)存執(zhí)行fun2方法即可。很明顯，第二種算法完成需求，占用的內(nèi)存空間更小。

黑馬程序員Java數(shù)據(jù)結(jié)構(gòu)與java算法全套教程，數(shù)據(jù)結(jié)構(gòu)+算法教程全資料發(fā)布，包含154張java數(shù)據(jù)結(jié)構(gòu)圖_嗶哩嗶哩_bilibili