為什么說數(shù)據(jù)結(jié)構(gòu)很重要1

哪怕只寫過幾行代碼的人都會發(fā)現(xiàn)，編程基本上就是在跟數(shù)據(jù)打交道。計算機程序總是在接收數(shù)據(jù)、操作數(shù)據(jù)或返回數(shù)據(jù)。不管是求兩數(shù)之和的小程序，還是管理公司的企業(yè)級軟件，都運行在數(shù)據(jù)之上。

數(shù)據(jù)是一個廣義的術(shù)語，可以指代各種類型的信息，包括最基本的數(shù)字和字符串。在經(jīng)典的“Hello World!”這個簡單程序中，字符串"Hello World!"就是一條數(shù)據(jù)。事實上，無論是多么復(fù)雜的數(shù)據(jù)，我們都可以將其拆成一堆數(shù)字和字符串來看待。

數(shù)據(jù)結(jié)構(gòu)則是指數(shù)據(jù)的組織形式?？纯匆韵麓a。

x = "Hello!"y = "How are you"z = "today?"
print x + y + z

這個非常簡單的程序把3 條數(shù)據(jù)串成了一句連貫的話。如果要描述該程序中的數(shù)據(jù)結(jié)構(gòu)，我們會說，這里有3 個獨立的變量，分別引用著3 個獨立的字符串。

在這里，你將學(xué)到，數(shù)據(jù)結(jié)構(gòu)不只是用于組織數(shù)據(jù)，它還極大地影響著代碼的運行速度。因為數(shù)據(jù)結(jié)構(gòu)不同，程序的運行速度可能相差多個數(shù)量級。如果你寫的程序要處理大量的數(shù)據(jù)，或者要讓數(shù)千人同時使用，那么你采用何種數(shù)據(jù)結(jié)構(gòu)，將決定它是能夠運行，還是會因為不堪重負而崩潰。

一旦對各種數(shù)據(jù)結(jié)構(gòu)有了深刻的理解，并明白它們對程序性能方面的影響，你就能寫出快速而優(yōu)雅的代碼，從而使軟件運行得快速且流暢。當然，你的編程技能也會更上一層樓。

接下來我們將會分析兩種比較相似的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和集合。它們從表面上看好像差不多，但通過即將介紹的分析工具，你將會觀察到它們在性能上的差異。

基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)：數(shù)組

數(shù)組是計算機科學(xué)中最基本的數(shù)據(jù)結(jié)構(gòu)之一。如果你用過數(shù)組，那么應(yīng)該知道它就是一個含有數(shù)據(jù)的列表。它有多種用途，適用于各種場景，下面就舉個簡單的例子。

一個允許用戶創(chuàng)建和使用購物清單的食雜店應(yīng)用軟件，其源代碼可能會包含以下的片段。

array = ["apples", "bananas", "cucumbers", "dates", "elderberries"]

這就是一個數(shù)組，它剛好包含5 個字符串，每個代表我會從超市買的食物。

此外，我們會用一些名為索引的數(shù)字來標識每項數(shù)據(jù)在數(shù)組中的位置。

在大多數(shù)的編程語言中，索引是從0 算起的，因此在這個例子中，"apples"的索引為0，"elderberries"的索引為4，如下所示。

若想了解某個數(shù)據(jù)結(jié)構(gòu)（例如數(shù)組）的性能，得分析程序怎樣操作這一數(shù)據(jù)結(jié)構(gòu)。

一般數(shù)據(jù)結(jié)構(gòu)都有以下4 種操作（或者說用法）。

• 讀?。翰榭磾?shù)據(jù)結(jié)構(gòu)中某一位置上的數(shù)據(jù)。對于數(shù)組來說，這意味著查看某個索引所指的數(shù)據(jù)值。例如，查看索引2 上有什么食品，就是一種讀取。
• 查找：從數(shù)據(jù)結(jié)構(gòu)中找出某個數(shù)據(jù)值的所在。對于數(shù)組來說，這意味著檢查其是否包含某個值，如果包含，那么還得給出其索引。例如，檢查"dates"是否存在于食品清單之中，給出其對應(yīng)的索引，就是一種查找。
• 插入：給數(shù)據(jù)結(jié)構(gòu)增加一個數(shù)據(jù)值。對于數(shù)組來說，這意味著多加一個格子并填入一個值。例如，往購物清單中多加一項"figs"，就是一種插入。
• 刪除：從數(shù)據(jù)結(jié)構(gòu)中移走一個數(shù)據(jù)值。對于數(shù)組來說，這意味著把數(shù)組中的某個數(shù)據(jù)項移走。例如，把購物清單中的"bananas"移走，就是一種刪除。

接下來我們將會研究這些操作在數(shù)組上的運行速度。同時，我們也將學(xué)到第一個重要理論：操作的速度，并不按時間計算，而是按步數(shù)計算。

為什么呢？

因為，你不可能很絕對地說，某項操作要花5 秒。它在某臺機器上要跑5 秒，但換到一臺舊一點的機器，可能就要多于5 秒，而換到一臺未來的超級計算機，運行時間又將顯著縮短。所以，受硬件影響的計時方法，非常不可靠。

然而，若按步數(shù)來算，則確切得多。如果A 操作要5 步，B 操作要500 步，那么我們可以很肯定地說，無論是在什么樣的硬件上對比，A 都快過B。因此，衡量步數(shù)是分析速度的關(guān)鍵。

此外，操作的速度，也常被稱為時間復(fù)雜度。本文中，我們提到速度、時間復(fù)雜度、效率、性能，它們其實指的都是步數(shù)。

事不宜遲，我們現(xiàn)在就來探索上述4 種操作方式在數(shù)組上要花多少步。

1. 讀取

首先看看讀取，即查看數(shù)組中某個索引所指的數(shù)據(jù)值。

這只要一步就夠了，因為計算機本身就有跳到任一索引位置的能力。在["apples","bananas", "cucumbers", "dates", "elderberries"]的例子中，如果要查看索引2 的值，那么計算機就會直接跳到索引2，并告訴你那里有"cucumbers"。

計算機為什么能一步到位呢？原因如下。

計算機的內(nèi)存可以被看成一堆格子。下圖是一片網(wǎng)格，其中有些格子有數(shù)據(jù)，有些則是空白。

當程序聲明一個數(shù)組時，它會先劃分出一些連續(xù)的空格子以備使用。換句話說，如果你想創(chuàng)建一個包含5 個元素的數(shù)組，計算機就會找出5 個排成一行的空格子，將其當成數(shù)組。

內(nèi)存中的每個格子都有各自的地址，就像街道地址，例如大街123 號。不過內(nèi)存地址就只用一個普通的數(shù)字來表示。而且，每個格子的內(nèi)存地址都比前一個大1，如下圖所示。

購物清單數(shù)組的索引和內(nèi)存地址，如下圖所示。

計算機之所以在讀取數(shù)組中某個索引所指的值時，能直接跳到那個位置上，是因為它具備以下條件。

(1) 計算機可以一步就跳到任意一個內(nèi)存地址上。（就好比，要是你知道大街123 號在哪兒，那么就可以直奔過去。）

(2) 數(shù)組本身會記有第一個格子的內(nèi)存地址，因此，計算機知道這個數(shù)組的開頭在哪里。

(3) 數(shù)組的索引從0 算起。

回到剛才的例子，當我們叫計算機讀取索引3 的值時，它會做以下演算。

(1) 該數(shù)組的索引從0 算起，其開頭的內(nèi)存地址為1010。

(2) 索引3 在索引0 后的第3 個格子上。

(3) 于是索引3 的內(nèi)存地址為1013，因為1010 + 3 = 1013。

當計算機一步跳到1013 時，我們就能獲取到"dates"這個值了。

所以，數(shù)組的讀取是一種非常高效的操作，因為它只要一步就好。一步自然也是最快的速度。這種一步讀取任意索引的能力，也是數(shù)組好用的原因之一。

如果我們問的不是“索引3 有什么值”，而是“"dates"在不在數(shù)組里”，那么這就需要進行查找操作了。下面我們就來看看。

2.查找

如前所述，對于數(shù)組來說，查找就是檢查它是否包含某個值，如果包含，還得給出其索引。

那么，我們就試試在數(shù)組中查找"dates"要用多少步。

對于我們?nèi)藖碚f，可以一眼就看到這個購物清單上的"dates"，并數(shù)出它的索引為3。但是，計算機并沒有眼睛，它只能一步一步地檢查整個數(shù)組。

想要查找數(shù)組中是否存在某個值，計算機會先從索引0 開始，檢查其值，如果不匹配，則繼續(xù)下一個索引，以此類推，直至找到為止。

我們用以下圖來演示計算機如何從購物清單中查找"dates"。

首先，計算機檢查索引0。

因為索引0 的值是"apples"，并非我們所要的"dates"，所以計算機跳到下一個索引上。

索引1 也不是"dates"，于是計算機再跳到索引2。

但索引2 的值仍不匹配，計算機只好再跳到下一格。

啊，真是千辛萬苦，我們找到"dates"了，它就在索引3 那里。自此，計算機不用再往后跳了，因為結(jié)果已經(jīng)得到。

在這個例子中，因為我們檢查了4 個格子才找到想要的值，所以這次操作總計是4 步。

這種逐個格子去檢查的做法，就是最基本的查找方法——線性查找。當然還可以學(xué)習其他查找方法，但在那之前，我們再思考一下，在數(shù)組上進行線性查找最多要多少步呢？

如果我們要找的值剛好在數(shù)組的最后一個格子里（如本例的elderberries），那么計算機從頭到尾檢查每個格子，會在最后才找到。同樣，如果我們要找的值并不存在于數(shù)組中，那么計算機也還是得查遍每個格子，才能確定這個值不在數(shù)組中。

于是，一個5 格的數(shù)組，其線性查找的步數(shù)最大值是5，而對于一個500 格的數(shù)組，則是500。

以此類推，一個N 格的數(shù)組，其線性查找的最多步數(shù)是N（N 可以是任何自然數(shù)）。

可見，無論是多長的數(shù)組，查找都比讀取要慢，因為讀取永遠都只需要一步，而查找卻可能需要多步。

接下來，我們再研究一下插入，準確地說，是插入一個新值到數(shù)組之中。