# 數據結構與算法
## 1. 什么是數據結構
~~~
官方解釋:
數據結構是一門研究非數值計算的程序設計問題中的操作對象，以及他們之間的關系和操作等相關問題的學科。
大白話:
數據結構就是把數據元素按照一定的關系組織起來的集合，用來組織和存儲數據
~~~
## 2. 數據結構分類
**傳統上，我們可以把數據結構分為邏輯結構和物理結構兩大類。**
### 2.1邏輯結構分類：
邏輯結構是從具體問題中抽象出來的模型，是抽象意義上的結構，按照對象中數據元素之間的相互關系分類，也是
我們后面課題中需要關注和討論的問題。
**a.集合結構:集合結構中數據元素除了屬于同一個集合外，他們之間沒有任何其他的關系。**
**b.線性結構:線性結構中的數據元素之間存在一對一的關系**
**c.樹形結構:樹形結構中的數據元素之間存在一對多的層次關系**
**d.圖形結構:圖形結構的數據元素是多對多的關系**
### 2.2物理結構分類:
邏輯結構在計算機中真正的表示方式(又稱為映像)稱為物理結構，也可以叫做存儲結構。常見的物理結構有順序
存儲結構、鏈式存儲結構。
**順序存儲結構:**
把數據元素放到地址連續的存儲單元里面，其數據間的邏輯關系和物理關系是一致的 ，比如我們常用的數組就是 順序存儲結構。
**鏈式存儲結構:**
順序存儲結構存在一定的弊端，就像生活中排時也會有人插隊也可能有人有特殊情況突然離開，這時候整個結構都
處于變化中，此時就需要鏈式存儲結構。
鏈式存儲結構是把數據元素存放在任意的存儲單元里面，這組存儲單元可以是連續的也可以是不連續的。此時，數據元素之間并
不能反映元素間的邏輯關系，因此在鏈式存儲結構中引進了一個指針存放數據元素的地址，這樣通過地址就可以找
到相關聯數據元素的位置
## 3. 什么是算法
**官方解釋:**
算法是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法解決問題的策略
機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。
**大白話:**
根據一定的條件，對一些數據進行計算，得到需要的結果。
### 3.1算法初體驗
在生活中，我們如果遇到某個問題，常常解決方案不是唯一的。
~~~
例如從西安到北京，如何去?會有不同的解決方案，我們可以坐飛機，可以坐火車，可以坐汽車，甚至可以步行，
不同的解決方案帶來的時間成本和金錢成本是不一樣的，比如坐飛機用的時間最少，但是費用最高，步行費用最
低，但時間最長。
~~~
~~~
再例如在北京二環內買一套四合院，如何付款?也會有不同的解決方案，可以一次性現金付清，也可以通過銀行做 按揭。
這兩種解決方案帶來的成本也不一樣，一次性付清，雖然當時出的錢多，壓力大，但是沒有利息，按揭雖然 當時出的錢少，
壓力比較小，但是會有利息，而且30年的總利息幾乎是貸款額度的一倍，需要多付錢。
~~~
在程序中，我們也可以用不同的算法解決相同的問題，而不同的算法的成本也是不相同的。總體上，一個優秀的算
法追求以下兩個目標:
1. 花最少的時間完成需求;
2. 占用最少的內存空間完成需求;
### 3.2算法實踐
**需求1:計算1到100的和**
解法1：
```
public function get100Sum(){
$sum=0;
$n=100;
for ($i=1; $i<$n ; $i++) {
$sum+=$i;
}
echo "1到100的和是：".$sum;
}
```
解法2：
```
public function getSum100(){
$sum=0;
$n=100;
$sum = ($n+1)*$n/2
echo "1到100的和是：".$sum;
}
```
第一種解法要完成需求，要完成以下幾個動作: 1.定義兩個整型變量;
2.執行100次加法運算;
3.打印結果到控制臺;
第二種解法要完成需求，要完成以下幾個動作:
1.定義兩個整型變量; 2.執行1次加法運算，1次乘法運算，一次除法運算，總共3次運算; 3.打印結果到控制臺;
很明顯，第二種算法完成需求，花費的時間更少一些。
**需求2: 計算10的階乘**
解法1：
```
static function fun1($n){
if($n==1){
return 1;
}
return $n*self::fun1($n-1);
}
```
解法2：
```
static function fun1($n){
$res=1;
for ($i=1; $i<=$n ; $i++) {
$res*=$i;
}
return $res;
}
```
第一種解法，使用遞歸完成需求，fun1方法會執行10次，并且第一次執行未完畢，調用第二次執行，第二次執行 未完畢，調用第三次執行...最終，最多的時候，需要在棧內存同時開辟10塊內存分別執行10個fun1方法。
第二種解法，使用for循環完成需求，fun2方法只會執行一次，最終，只需要在棧內存開辟一塊內存執行fun2方法 即可。
很明顯，第二種算法完成需求，占用的內存空間更小。
## 4.總結
以上就是數據結構與算法的概述，我悶在實際開發中，使用不同的算法，不同的數據結構會對我們的查詢速度產生很大的影響，后續會給大家介紹如何選擇數據結構以及算法。
