正文

上學(xué)時候?qū)W過相關(guān)數(shù)據(jù)結(jié)構(gòu)和算法的課程，工作中也沒有很多用到的時候。很多知識點都已經(jīng)還給老師了，最近又整理學(xué)習(xí)下相關(guān)的知識點。后續(xù)會持續(xù)更新記錄每個知識點的具體情況，歡迎指正相互學(xué)習(xí)。

image.png

1.1相關(guān)術(shù)語

數(shù)據(jù)

數(shù)據(jù)（Data）是能被計算機(jī)處理的符號或符號集合，含義廣泛，可理解為“原材料”。
如字符、圖片、音視頻等

數(shù)據(jù)元素

數(shù)據(jù)元素（data element）是數(shù)據(jù)的基本單位。例如一張學(xué)生統(tǒng)計表。

數(shù)據(jù)項

數(shù)據(jù)項（data item）組成數(shù)據(jù)元素的最小單位。例如一張學(xué)生統(tǒng)計表，有編號、姓名、性別、籍貫等數(shù)據(jù)項
可以理解為數(shù)據(jù)庫表中的字段值

數(shù)據(jù)對象

數(shù)據(jù)對象（data object）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如正整數(shù)N={1，2，3，····}。

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

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

1.2 邏輯結(jié)構(gòu)

邏輯結(jié)構(gòu)（logical structure）是指在數(shù)據(jù)中數(shù)據(jù)元素之間的相互關(guān)系。數(shù)據(jù)元素之間存在不同的邏輯關(guān)系構(gòu)成了以下4種結(jié)構(gòu)類型。

（1）集合結(jié)構(gòu)：集合的數(shù)據(jù)元素沒有其他關(guān)系，僅僅是因為他們擠在一個被稱作“集合”的盒子里。

（2）線性結(jié)構(gòu)：線性的數(shù)據(jù)元素結(jié)構(gòu)關(guān)系是一對一的，并且是一種先后的次序，就像a-b-c-d-e-f-g·····被一根線穿連起來。

（3）樹形結(jié)構(gòu)：樹形的數(shù)據(jù)元素結(jié)構(gòu)關(guān)系是一對多的，這就像公司的部門級別，董事長-CEO\CTO-技術(shù)部\人事部\市場部.....。

（4）圖結(jié)構(gòu)：圖的數(shù)據(jù)元素結(jié)構(gòu)關(guān)系是多對多的。就是我們常見的各大城市的鐵路圖，一個城市有很多線路連接不同城市。

1.3物理結(jié)構(gòu)(存儲結(jié)構(gòu))

存儲結(jié)構(gòu)（storage structure）也稱為物理結(jié)構(gòu)（physical structure），指的是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的存儲形式。數(shù)據(jù)的存儲結(jié)構(gòu)一般可以反映數(shù)據(jù)元素之間的邏輯關(guān)系。分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

（1）順序存儲結(jié)構(gòu)：是把數(shù)據(jù)元素存放在一組存儲地址連續(xù)的存儲單元里，其數(shù)據(jù)元素間的邏輯關(guān)系和物理關(guān)系是一致的。
    常用的實現(xiàn)方式如:順序表,數(shù)組

（2）鏈?zhǔn)酱鎯Y(jié)果：是把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。
    數(shù)據(jù)元素的存儲關(guān)系并不能反映其邏輯關(guān)系，因此需要借助指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

1.4算法

算法可以理解為解決問題的方法。有一種說法是 程序=數(shù)據(jù)結(jié)構(gòu)+算法。算法的操作對象是數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)關(guān)注的是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，而算法則是在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上來解決問題。
算法是編程思想，數(shù)據(jù)結(jié)構(gòu)是思想的基礎(chǔ)。

算法的5大特性

1.有窮性，是指算法在執(zhí)行有限的步驟之后，自動結(jié)束而不是出現(xiàn)無限循環(huán)，并且每一個步驟在可接受的時間內(nèi)完成。

2.確定性，是指算法執(zhí)行的每一步驟在一定條件下只有一條執(zhí)行路徑，也就是相同輸入只能有一個唯一的輸出結(jié)果。

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

4.輸入，是指算法具有零個或多個輸入。

5.輸出，是指算法至少有一個或多個輸出。

1.5算法的優(yōu)劣

同一問題可用不同算法解決，而一個算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個算法的評價主要從[時間復(fù)雜度]和[空間復(fù)雜度]來考慮

1.5.1時間復(fù)雜度

image.png

時間復(fù)雜度的優(yōu)劣順序:

image.png

1.5.2空間復(fù)雜度

算法運行需要消耗的內(nèi)存空間

1.6常用的經(jīng)典算法

• 遞推法
• 遞歸法
• 窮舉法
• 貪心算法
• 分治法
• 動態(tài)規(guī)劃法
• 迭代法
• 分支界限法
• 回溯法

總結(jié)：

以上是數(shù)據(jù)結(jié)構(gòu)和算法的相關(guān)概念的基礎(chǔ)知識筆記，后續(xù)會繼續(xù)記錄，相關(guān)常用數(shù)據(jù)結(jié)構(gòu)的算法實現(xiàn)。歡迎相互習(xí)。