本篇文章將簡(jiǎn)要介紹數(shù)據(jù)結(jié)構(gòu)，讓讀者了解它們?cè)谟?jì)算機(jī)中以何種結(jié)構(gòu)方式存在。那么，什么是數(shù)據(jù)結(jié)構(gòu)呢？下面我們來(lái)詳細(xì)解釋。

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

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

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率。

數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。這句話是啥意思呢？

我們舉個(gè)簡(jiǎn)單的例子。就像金庸小說(shuō)中所寫(xiě)的，武功招式就相當(dāng)于我們的算法，而數(shù)據(jù)結(jié)構(gòu)就是我們的內(nèi)功心法；而武功的高低，不僅僅是武功招式，更重要的是 學(xué)會(huì)的內(nèi)功心法。就比如張無(wú)忌在學(xué)會(huì)九陽(yáng)神功之后，就可以大戰(zhàn)六大門派。

而數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，也會(huì)讓我們事半功倍。憑借著“數(shù)據(jù)結(jié)構(gòu)+算法=程序”這句話，Pascal之父獲得了圖靈獎(jiǎng)。

總結(jié)來(lái)說(shuō)：

數(shù)據(jù)結(jié)構(gòu)就是一種是將世界上各種數(shù)據(jù)轉(zhuǎn)化為計(jì)算機(jī)可以存儲(chǔ)和操作的形式，定義了邏輯結(jié)構(gòu)如何在計(jì)算機(jī)上存儲(chǔ)，以及相關(guān)的基本操作。

算法是程序猿通過(guò)調(diào)用不同數(shù)據(jù)結(jié)構(gòu)的基本操作，從而實(shí)現(xiàn)了數(shù)據(jù)的處理。

而這兩點(diǎn)使我們作為程序開(kāi)發(fā)人員的必備基本功，不是一朝一夕就能成為絕世高手的，我們需要一步步去不斷的學(xué)習(xí)積累，積硅步以致千里。

1.2 常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)

在計(jì)算機(jī)學(xué)科中，數(shù)據(jù)結(jié)構(gòu)是一門很重要的基礎(chǔ)學(xué)科，知識(shí)點(diǎn)很多。在這里我們不講那么多，只講述我們集合中用到的幾種數(shù)據(jù)結(jié)構(gòu)，同學(xué)們可以下去自行學(xué)習(xí)更多的數(shù)據(jù)結(jié)構(gòu)的知識(shí)。常用結(jié)構(gòu)三個(gè)：數(shù)組、鏈表、紅黑樹(shù)。

我們分別來(lái)了解一下：

1）數(shù)組

數(shù)組的定義：

• 數(shù)組是相同類型數(shù)據(jù)的有序集合；
• 數(shù)組描述的是相同類型的若干個(gè)數(shù)據(jù),按照一定的先后次序排列組合而成；
• 其中，每一個(gè)數(shù)據(jù)稱作一個(gè)數(shù)組元素,每個(gè)數(shù)組元素可以通過(guò)一個(gè)下標(biāo)來(lái)訪問(wèn)它們。

存儲(chǔ)思路：

所有數(shù)據(jù)存儲(chǔ)在連續(xù)的空間中，數(shù)組中的每個(gè)元素都是一個(gè)具體的數(shù)據(jù)。

數(shù)組的特點(diǎn)：

• 使用連續(xù)分配的內(nèi)存空間；
• 一次申請(qǐng)一大段連續(xù)的空間，需要事先聲明最大可能要占的固定內(nèi)存空間。

如下圖：

• 通過(guò)索引，查詢快
• 當(dāng)給數(shù)組插入新元素時(shí)，數(shù)組中的a2,a3,a4整體后移，代價(jià)高。
• 如果插入元素時(shí)，數(shù)組長(zhǎng)度，還要重新創(chuàng)建一個(gè)數(shù)組，然后循環(huán)賦值，代價(jià)高

優(yōu)點(diǎn)：

設(shè)計(jì)簡(jiǎn)單，讀取與修改表中的任意一個(gè)元素的時(shí)間都是固定的，速度快 。

缺點(diǎn)：

容易造成內(nèi)存浪費(fèi)；刪除或者插入數(shù)據(jù)需要移動(dòng)大量數(shù)據(jù)，速度慢。

2）鏈表

每個(gè)數(shù)據(jù)單獨(dú)存在一小塊內(nèi)存中，這個(gè)單元叫做節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)知道下一個(gè)節(jié)點(diǎn)的地址，叫做單向鏈表。每個(gè)節(jié)點(diǎn)既知道下一個(gè)節(jié)點(diǎn)地址，又知道上一個(gè)節(jié)點(diǎn)地址，叫做雙向鏈表。

鏈表的特點(diǎn)：

• 使用不連續(xù)的內(nèi)存空間；
• 不需要提前聲明好指定大小的內(nèi)存空間，一次申請(qǐng)一小塊，按需申請(qǐng)。

查詢?cè)兀枰ㄟ^(guò)節(jié)點(diǎn)一次向后查找，直到查找到指定元素

增刪元素：只需修改連接節(jié)點(diǎn)的地址即可。

優(yōu)點(diǎn)： 充分節(jié)省內(nèi)存空間，數(shù)據(jù)插入和刪除方便，不需要移動(dòng)大量數(shù)據(jù)。

缺點(diǎn)： 查詢數(shù)據(jù)必須按順序找到該數(shù)據(jù)，操作麻煩。

3）紅黑樹(shù)

簡(jiǎn)單理解，就是一種類似于我們生活中樹(shù)的結(jié)構(gòu)，只不過(guò)每個(gè)節(jié)點(diǎn)最多只有兩個(gè)葉子。計(jì)算機(jī)世界的樹(shù)，剛好與我們現(xiàn)實(shí)中的樹(shù)成鏡像相反，樹(shù)根在上，樹(shù)枝在下。二叉樹(shù)如下圖：

而我們要說(shuō)的是二叉樹(shù)的一種比較有意思的叫做紅黑樹(shù)，紅黑樹(shù)本身就是一顆二叉查找樹(shù)。我們?cè)谶@里只需要記住它的特點(diǎn)就可以非常方便的對(duì)樹(shù)中的所有節(jié)點(diǎn)進(jìn)行排序和檢索。

小結(jié)

本文介紹了三種常用的數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表和紅黑樹(shù)，以及這些數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的重要意義。通過(guò)學(xué)習(xí)這些內(nèi)容，我們可以逐步深入了解計(jì)算機(jī)世界。