為什么說數據結構很重要1

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

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

數據結構則是指數據的組織形式?？纯匆韵麓a。

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

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

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

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

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

基礎數據結構：數組

數組是計算機科學中最基本的數據結構之一。如果你用過數組，那么應該知道它就是一個含有數據的列表。它有多種用途，適用于各種場景，下面就舉個簡單的例子。

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

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

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

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

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

若想了解某個數據結構（例如數組）的性能，得分析程序怎樣操作這一數據結構。

一般數據結構都有以下4 種操作（或者說用法）。

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

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

為什么呢？

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

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

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

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

1. 讀取

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

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

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

計算機的內存可以被看成一堆格子。下圖是一片網格，其中有些格子有數據，有些則是空白。

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

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

購物清單數組的索引和內存地址，如下圖所示。

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

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

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

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

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

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

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

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

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

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

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

2.查找

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

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

對于我們人來說，可以一眼就看到這個購物清單上的"dates"，并數出它的索引為3。但是，計算機并沒有眼睛，它只能一步一步地檢查整個數組。

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

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

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

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

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

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

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

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

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

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

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

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

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

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