數(shù)據(jù)結(jié)構(gòu)（回顧）

回顧

緩存利用率

這里的緩存利用率給大家簡單講一下就是存儲也是分結(jié)構(gòu)的：

然后順序表由于它在存儲的時(shí)候物理空間一定是連續(xù)的，在高速緩存的時(shí)候會命中率更高。這個(gè)緩存其實(shí)大概就是我加載一個(gè)數(shù)據(jù)，我連帶著這個(gè)數(shù)據(jù)后面的數(shù)據(jù)也一起加載了，后面被使用的時(shí)候直接用就好了，不用重新加載一次。然后這個(gè)連著后面的數(shù)據(jù)一起加載是按照存儲的物理空間連續(xù)的，線性的來的。就好比如有一組數(shù)據(jù)12345，現(xiàn)在要用1就加載了1，系統(tǒng)考慮到你后面可能會用到后面的數(shù)據(jù)，就把2345也給你加載緩存好了。這樣后面你再去用這些數(shù)據(jù)的時(shí)候就會快很多。

但是鏈表就沒有這個(gè)優(yōu)點(diǎn)。為什么？因?yàn)殒湵硎沁壿嬌线B續(xù)，但是存儲的時(shí)候物理空間是不連續(xù)的，可能那邊一個(gè)數(shù)據(jù)，這邊一個(gè)數(shù)據(jù)，然后村門口一個(gè)數(shù)據(jù)，山頭一個(gè)數(shù)據(jù)。但是緩存不會管你連不連續(xù)，它就只是幫你連續(xù)的加載好后面的數(shù)據(jù)，后面的數(shù)據(jù)和你這個(gè)項(xiàng)目本身有沒有關(guān)系，不管你，所以就涉及到了一個(gè)命中率的問題。

順序表因?yàn)樗俏锢砜臻g連續(xù)的，所以緩存的時(shí)候，緩存得到的數(shù)據(jù)就大部分都是和本項(xiàng)目，本問題有關(guān)的，所以命中率就高。就是緩存的后續(xù)數(shù)據(jù)和我的目標(biāo)數(shù)據(jù)是否重合，重合度越高，那么命中率越高。鏈表反之。

對比

那么通過上面表格順序表和鏈表的對比，其實(shí)大家可以發(fā)現(xiàn)，這兩種數(shù)據(jù)結(jié)構(gòu)其實(shí)有種互補(bǔ)的關(guān)系，有沒有。好比如，順序表適合干隨機(jī)訪問數(shù)據(jù)，鏈表不適合，順序表不適合頻繁的插入數(shù)據(jù)（因?yàn)樯婕暗脚矂訑?shù)據(jù)問題），但是鏈表合適。等等。

總結(jié)

還有我們后續(xù)用數(shù)組或者鏈表實(shí)現(xiàn)的棧和隊(duì)列，也是順序表的一種，不過操作比較特殊。那么大家也能察覺，這類數(shù)據(jù)結(jié)構(gòu)其實(shí)比較基礎(chǔ)，能具體解決的問題其實(shí)不算多。它們在結(jié)構(gòu)中都是1對1的關(guān)系，只有一個(gè)直接前驅(qū)或后繼。但是等會講到的樹，就不是這么簡單的結(jié)構(gòu)了，已經(jīng)開始是1對多了。說這么多，都是為了讓大家更明白我們前面學(xué)的大概是什么東西，也為了和后續(xù)學(xué)的東西有個(gè)區(qū)別。

再總結(jié)

這里給大家做個(gè)比喻，我們最開始學(xué)的數(shù)組，就其實(shí)像是大米，小麥。然后簡單的操作一下，把大米煮一下就變成了粥（順序表），粥改良了一下，有的人不愛喝粥，那就變成米飯（鏈表）。如果有人手法精巧，加上一些雞蛋，米飯就可以變成蛋炒飯（隊(duì)列），粥放點(diǎn)豬肉，就變成了豬肉粥（棧）。然后還有把米整成淀粉，加點(diǎn)青菜，加點(diǎn)豬肉，玉米煮一下就變成了餃子（哈希表、堆、樹…）。大概的意思就是后面的很多復(fù)雜結(jié)構(gòu)都是基于前面的簡單結(jié)構(gòu)，通過一些操作的改動，或者再加上一些佐料，就變成了復(fù)雜結(jié)構(gòu)，這樣也可以更好的去解決更多問題。就是想讓大家也有一個(gè)這樣的理解。