定義
- 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是對(duì)計(jì)算機(jī)內(nèi)存，有時(shí)候是磁盤中-數(shù)據(jù)的一種安排
- 數(shù)據(jù)結(jié)構(gòu)的種類
- 數(shù)組、鏈表、棧、二叉樹、哈希表 etc
- 算法：算法是對(duì)這些數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行各種各樣的處理，如CRUD
- 數(shù)據(jù)結(jié)構(gòu)由某個(gè)類進(jìn)行封裝，更泛化的講，任何一個(gè)類都可稱為數(shù)據(jù)結(jié)構(gòu)，因?yàn)槠渲邪藬?shù)據(jù)的安排
掌握這些知識(shí)的好處
- 解決如何用計(jì)算機(jī)存儲(chǔ)現(xiàn)實(shí)世界的數(shù)據(jù)
- 如，如何用計(jì)算機(jī)表示一個(gè) 倉(cāng)庫(kù)貨物清單，訂單記錄等
- 簡(jiǎn)單來(lái)講，可以用 List 存放 這些清單，List也是一種數(shù)據(jù)結(jié)構(gòu)
- 進(jìn)而提煉出在此 數(shù)據(jù)結(jié)構(gòu)中查找你想要信息即算法的問題
- 這些結(jié)構(gòu)可以作為程序員日常工作的輔助工具
- 建模，提供對(duì)復(fù)雜問題的抽象建模
- 最重要的數(shù)據(jù)結(jié)構(gòu)是圖
數(shù)據(jù)結(jié)構(gòu)概述
注意：
查找：即針對(duì)特定元素進(jìn)行搜索的過(guò)程
刪除 有幾種操作：
- 本身的刪除操作，如鏈表前后指針的操作 VS 數(shù)組后面所有元素向前移動(dòng)
- 刪除特定位置對(duì)象的區(qū)別，如隊(duì)頭、棧頂?shù)鹊龋瑢?duì)其他數(shù)據(jù)操作則不同
- 對(duì)指定元素的刪除，這樣就加入了 查找的復(fù)雜度
| 數(shù)據(jù)結(jié)構(gòu) | 優(yōu)點(diǎn) | 缺點(diǎn) |
|---|---|---|
| 數(shù)組 | 插入塊，如果知道下標(biāo)，存入/取出很快 | 查找/刪除慢，因?yàn)椴檎乙灰粚?duì)比，刪除要移動(dòng)后續(xù)所有元素大小固定 |
| 有序數(shù)組 | 比無(wú)序數(shù)組查找快，可以用二分查找 | 插入比無(wú)序數(shù)組慢，刪除比無(wú)序略快，可以用二分先找，但也要一一對(duì)比，大小固定 |
| 棧 | 提供后進(jìn)先出方式的存取，對(duì)棧頂元素 取/刪 很快 | 存取 除棧頂外的元素 慢 |
| 隊(duì)列 | 提供先進(jìn)先出方式的存取 | 存取除隊(duì)頭隊(duì)尾元素外慢 |
| 鏈表 | 插入快、刪除快 | 查找慢，一一對(duì)比 |
| 二叉樹 | 查找、插入、刪除都快 | 刪除算法復(fù)雜 |
| 紅黑樹 | 查找、插入、刪除都快 | 算法復(fù)雜 |
| 哈希表 | 如果關(guān)鍵字已知 則存、取極快，插入快 | 刪除慢，若不知關(guān)鍵字則存取慢，空間利用不均勻 |
| 堆 | 插入、刪除快，對(duì)最值存取快 | 其他數(shù)據(jù)項(xiàng) 存取慢 |
| 圖 | 對(duì)現(xiàn)實(shí)世界的建模 | 算法復(fù)雜慢 |
算法
- insert
- select 某特定數(shù)據(jù)項(xiàng)
- remove 某特定數(shù)據(jù)項(xiàng)
- 遍歷
- 排序
- 遞歸-
面向?qū)ο骎S面向過(guò)程
- 即 行為與數(shù)據(jù)地位的問題
- 數(shù)據(jù)與行為并列同等重要；
- 還是 數(shù)據(jù)作為輔助單獨(dú)存在方法里
- 面向過(guò)程：未重視數(shù)據(jù)，局部變量還可以，但全局變量，所有方法共同使用的數(shù)據(jù)就無(wú)能為力了
面向?qū)ο?/h4>
- 對(duì)象
- 關(guān)鍵思想：對(duì)象是方法和數(shù)據(jù)的共同存在
- 與現(xiàn)實(shí)世界對(duì)象更好的映射
- 全局變量 public、私有變量 private 的處理
- 類
- 針對(duì)單一對(duì)象定義數(shù)據(jù)/行為，還是抽象提升一個(gè)層次
- 除了單一的對(duì)象，有可能需要若干個(gè)對(duì)象同時(shí)處理
- 類是針對(duì)一個(gè)或多個(gè)對(duì)象的說(shuō)明、藍(lán)圖
- 由類可以得到任意個(gè)具有相同數(shù)據(jù)、行為的對(duì)象
- 關(guān)鍵思想：對(duì)象是方法和數(shù)據(jù)的共同存在
- 與現(xiàn)實(shí)世界對(duì)象更好的映射
- 全局變量 public、私有變量 private 的處理
- 針對(duì)單一對(duì)象定義數(shù)據(jù)/行為，還是抽象提升一個(gè)層次
- 除了單一的對(duì)象，有可能需要若干個(gè)對(duì)象同時(shí)處理
- 類是針對(duì)一個(gè)或多個(gè)對(duì)象的說(shuō)明、藍(lán)圖
- 由類可以得到任意個(gè)具有相同數(shù)據(jù)、行為的對(duì)象
