程序設(shè)計(jì) = 數(shù)據(jù)結(jié)構(gòu)+算法

基本概念和術(shù)語

說到數(shù)據(jù)結(jié)構(gòu)是什么，我們得先來談?wù)勈裁唇袛?shù)據(jù)。

正所謂"巧婦難為無米之炊’，再?gòu)?qiáng)大的計(jì)算機(jī)，也是要有"米’下鍋才可以的，否則就是一堆破銅爛鐵 這個(gè)"米"就是數(shù)據(jù)。

數(shù)據(jù)

數(shù)據(jù)： 是描述客觀事物的符號(hào)，是計(jì)算機(jī)中可以操作的對(duì)象，是能被計(jì)算機(jī)識(shí)別，并輸入給計(jì)算機(jī)處理的符號(hào)集合。數(shù)據(jù)不僅僅包括整型、實(shí)型等數(shù)值類型，還包括字符及聲音、圖像、視頻等非數(shù)值類型。

比如我們現(xiàn)在常用的搜索引擎，一般會(huì)有網(wǎng)頁(yè)、MP3、圖片、視頻等分類。MP3就是聲音數(shù)據(jù)，圖片當(dāng)然是圖像數(shù)據(jù)，視頻就不用說了，而網(wǎng)頁(yè)其實(shí)指的就是全部數(shù)據(jù)的搜索，包括最重要的數(shù)字和字符等文字?jǐn)?shù)據(jù)。

也就是說，我們這里說的數(shù)據(jù)，其實(shí)就是符號(hào)，而且這些符號(hào)必須具備兩個(gè)前提：

■　可以輸入到計(jì)算機(jī)中。
■　能被計(jì)算機(jī)程序處理。

對(duì)于整型、實(shí)型等數(shù)值類型，可以進(jìn)行數(shù)值計(jì)算。

對(duì)于字符數(shù)據(jù)類型，就需要進(jìn)行非數(shù)值的處理。而聲音、圖像、視頻等其實(shí)是可以通過編碼的手段變成字符數(shù)據(jù)來處理的。

數(shù)據(jù)元素

數(shù)據(jù)元素：是組成數(shù)據(jù)的、有一定意義的基本單位，在計(jì)算機(jī)中通常稱為記錄。

比如，在人類中，什么是數(shù)據(jù)元素呀？當(dāng)然是人了。

畜類呢？哈，牛、馬、羊、雞、豬、狗等動(dòng)物當(dāng)然就是禽類的數(shù)據(jù)元素。

數(shù)據(jù)對(duì)象

數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。

什么叫性質(zhì)相同呢，是指數(shù)據(jù)元素具有相同數(shù)量和類型的數(shù)據(jù)項(xiàng)，比如，還是剛才的例子，人都有姓名、生日、性別等相同的數(shù)據(jù)項(xiàng)。

既然數(shù)據(jù)對(duì)象是數(shù)據(jù)的子集，在實(shí)際應(yīng)用中，處理的數(shù)據(jù)元素通常具有相同性質(zhì)，在不產(chǎn)生混淆的情況下，我們都將數(shù)據(jù)對(duì)象簡(jiǎn)稱為數(shù)據(jù)。好了，有了這些概念的鋪墊，我們的主角登場(chǎng)了。

說了數(shù)據(jù)的定義，那么數(shù)據(jù)結(jié)構(gòu)中的結(jié)構(gòu)又是什么呢？

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

結(jié)構(gòu)，簡(jiǎn)單的理解就是關(guān)系，比如分子結(jié)構(gòu)，就是說組成分子的原子之間的排列方式。嚴(yán)格點(diǎn)說，結(jié)構(gòu)是指各個(gè)組成部分相互搭配和排列的方式。

在現(xiàn)實(shí)世界中，不同數(shù)據(jù)元素之間不是獨(dú)立的，而是存在特定的關(guān)系，我們將這些關(guān)系稱為結(jié)構(gòu)。

那數(shù)據(jù)結(jié)構(gòu)是什么？數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在計(jì)算機(jī)中，數(shù)據(jù)元素并不是孤立、雜亂無序的，而是具有內(nèi)在聯(lián)系的數(shù)據(jù)集合。數(shù)據(jù)元素之間存在的一種或多種特定關(guān)系，也就是數(shù)據(jù)的組織形式。

邏輯結(jié)構(gòu)與物理結(jié)構(gòu)

按照視點(diǎn)的不同，我們把數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

邏輯結(jié)構(gòu)

邏輯結(jié)構(gòu)：是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的相互關(guān)系。邏輯結(jié)構(gòu)分為以下四種：

1．集合結(jié)構(gòu)

集合結(jié)構(gòu)：集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外，它們之間沒有其他關(guān)系。各個(gè)數(shù)據(jù)元素是“平等”的，它們的共同屬性是“同屬于一個(gè)集合”。數(shù)據(jù)結(jié)構(gòu)中的集合關(guān)系就類似于數(shù)學(xué)中的集合。

2．線性結(jié)構(gòu)線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系

3．樹形結(jié)構(gòu)樹形結(jié)構(gòu)：樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對(duì)多的層次關(guān)系

4．圖形結(jié)構(gòu)圖形結(jié)構(gòu)：圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對(duì)多的關(guān)系

物理結(jié)構(gòu)

物理結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式。

數(shù)據(jù)是數(shù)據(jù)元素的集合，那么根據(jù)物理結(jié)構(gòu)的定義，實(shí)際上就是如何把數(shù)據(jù)元素存儲(chǔ)到計(jì)算機(jī)的存儲(chǔ)器中。

數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)形式有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

1．順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)：

是把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的

這種存儲(chǔ)結(jié)構(gòu)其實(shí)很簡(jiǎn)單，說白了，就是排隊(duì)占位。大家都按順序排好，每個(gè)人占一小段空間，大家誰也別插誰的隊(duì)。我們之前學(xué)計(jì)算機(jī)語言時(shí)，數(shù)組就是這樣的順序存儲(chǔ)結(jié)構(gòu)。當(dāng)你告訴計(jì)算機(jī)，你要建立一個(gè)有9個(gè)整型數(shù)據(jù)的數(shù)組時(shí)，計(jì)算機(jī)就在內(nèi)存中找了片空地，按照一個(gè)整型所占位置的大小乘以9，開辟一段連續(xù)的空間，于是第一個(gè)數(shù)組數(shù)據(jù)就放在第一個(gè)位置，第二個(gè)數(shù)據(jù)放在第二個(gè)，這樣依次擺放。

2．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

如果就是這么簡(jiǎn)單和有規(guī)律，一切就好辦了。可實(shí)際上，總會(huì)有人插隊(duì)，也會(huì)有人要上廁所、有人會(huì)放棄排隊(duì)。所以這個(gè)隊(duì)伍當(dāng)中會(huì)添加新成員，也有可能會(huì)去掉老元素，整個(gè)結(jié)構(gòu)時(shí)刻都處于變化中。顯然，面對(duì)這樣時(shí)常要變化的結(jié)構(gòu)，順序存儲(chǔ)是不科學(xué)的。那怎么辦呢？

現(xiàn)在如銀行、醫(yī)院等地方，設(shè)置了排隊(duì)系統(tǒng)，也就是每個(gè)人去了，先領(lǐng)一個(gè)號(hào)，等著叫號(hào)，叫到時(shí)去辦理業(yè)務(wù)或看病。在等待的時(shí)候，你愛在哪在哪，可以坐著、站著或者走動(dòng)，甚至出去逛一圈，只要及時(shí)回來就行。你關(guān)注的是前一個(gè)號(hào)有沒有被叫到，叫到了，下一個(gè)就輪到了。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。數(shù)據(jù)元素的存儲(chǔ)關(guān)系并不能反映其邏輯關(guān)系，因此需要用一個(gè)指針存放數(shù)據(jù)元素的地址，這樣通過地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置

顯然，鏈?zhǔn)酱鎯?chǔ)就靈活多了，數(shù)據(jù)存在哪里不重要，只要有一個(gè)指針存放了相應(yīng)的地址就能找到它了。

邏輯結(jié)構(gòu)是面向問題的，而物理結(jié)構(gòu)就是面向計(jì)算機(jī)的，其基本的目標(biāo)就是將數(shù)據(jù)及其邏輯關(guān)系存儲(chǔ)到計(jì)算機(jī)的內(nèi)存中。

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。同樣是結(jié)構(gòu)，從不同的角度來討論，會(huì)有不同的分類

算法

大家都已經(jīng)學(xué)過一門計(jì)算機(jī)語言，不管學(xué)的是哪一種，學(xué)得好不好，好歹是可以寫點(diǎn)小程序了?，F(xiàn)在我要求你寫一個(gè)求1+2+3+……+100結(jié)果的程序，你應(yīng)該怎么寫呢？

    int i, sum = 0, n = 100;
    for（i = 1; i < = n; i++）
    {
        sum = sum + i;
    }
    System.out.println（sum）;

這是最簡(jiǎn)單的計(jì)算機(jī)程序之一，它就是一種算法

高斯這樣算：

用程序來實(shí)現(xiàn)如下：

    int i, sum = 0,n = 100;
    sum = （1 + n） * n / 2;
    System.out.println（sum）;

高斯用的方法相當(dāng)于另一種求等差數(shù)列的算法，不僅僅可以用于1加到100，就是加到一千、一萬、一億（需要更改整型變量類型為長(zhǎng)整型，否則會(huì)溢出），也就是瞬間之事。但如果用剛才的程序，顯然計(jì)算機(jī)要循環(huán)一千、一萬、一億次的加法運(yùn)算

算法是描述解決問題的方法。

算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。

算法的特性

算法具有五個(gè)基本特性：輸入、輸出、有窮性、確定性和可行性。

輸入輸出

輸入和輸出特性比較容易理解，算法具有零個(gè)或多個(gè)輸入。盡管對(duì)于絕大多數(shù)算法來說，輸入?yún)?shù)都是必要的，但對(duì)于個(gè)別情況，如打印“hello world！”這樣的代碼，不需要任何輸入?yún)?shù)，因此算法的輸入可以是零個(gè)。算法至少有一個(gè)或多個(gè)輸出，算法是一定需要輸出的，不需要輸出，你用這個(gè)算法干嗎？輸出的形式可以是打印輸出，也可以是返回一個(gè)或多個(gè)值等。

有窮性

有窮性：指算法在執(zhí)行有限的步驟之后，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無限循環(huán)，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成。現(xiàn)實(shí)中經(jīng)常會(huì)寫出死循環(huán)的代碼，這就是不滿足有窮性。當(dāng)然這里有窮的概念并不是純數(shù)學(xué)意義的，而是在實(shí)際應(yīng)用當(dāng)中合理的、可以接受的“有邊界”。你說你寫一個(gè)算法，計(jì)算機(jī)需要算上個(gè)二十年，一定會(huì)結(jié)束，它在數(shù)學(xué)意義上是有窮了，可是媳婦都熬成婆了，算法的意義也不就大了。

確定性

確定性：算法的每一步驟都具有確定的含義，不會(huì)出現(xiàn)二義性。算法在一定條件下，只有一條執(zhí)行路徑，相同的輸入只能有唯一的輸出結(jié)果。算法的每個(gè)步驟被精確定義而無歧義。

可行性

可行性：算法的每一步都必須是可行的，也就是說，每一步都能夠通過執(zhí)行有限次數(shù)完成?？尚行砸馕吨惴梢赞D(zhuǎn)換為程序上機(jī)運(yùn)行，并得到正確的結(jié)果。盡管在目前計(jì)算機(jī)界也存在那種沒有實(shí)現(xiàn)的極為復(fù)雜的算法，不是說理論上不能實(shí)現(xiàn)，而是因?yàn)檫^于復(fù)雜，我們當(dāng)前的編程方法、工具和大腦限制了這個(gè)工作，不過這都是理論研究領(lǐng)域的問題，不屬于我們現(xiàn)在要考慮的范圍。

算法設(shè)計(jì)的要求

剛才我們談到了，算法不是唯一的。也就是說，同一個(gè)問題，可以有多種解決問題的算法。這可能讓那些常年只做有標(biāo)準(zhǔn)答案題目的同學(xué)失望了，他們多么希望存在標(biāo)準(zhǔn)答案，只有一個(gè)是正確的，把它背下來，需要的時(shí)候套用就可以了。不過話說回來，盡管算法不唯一，相對(duì)好的算法還是存在的。掌握好的算法，對(duì)我們解決問題很有幫助，否則前人的智慧我們不能利用，就都得自己從頭研究了。那么什么才叫好的算法呢？

嗯，沒錯(cuò)，有同學(xué)說，好的算法，起碼要是正確的，連正確都談不上，還談什么別的要求？

正確性

正確性：算法的正確性是指算法至少應(yīng)該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需求、能夠得到問題的正確答案。

但是算法的“正確”通常在用法上有很大的差別，大體分為以下四個(gè)層次。

1．算法程序沒有語法錯(cuò)誤。

2．算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果。

3．算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果。

4．算法程序?qū)τ诰倪x擇的，甚至刁難的測(cè)試數(shù)據(jù)都有滿足要求的輸出結(jié)果。

對(duì)于這四層含義，層次1要求最低，但是僅僅沒有語法錯(cuò)誤實(shí)在談不上是好算法。這就如同僅僅解決溫飽，不能算是生活幸福一樣。而層次4是最困難的，我們幾乎不可能逐一驗(yàn)證所有的輸入都得到正確的結(jié)果。

可讀性

可讀性：算法設(shè)計(jì)的另一目的是為了便于閱讀、理解和交流。

可讀性高有助于人們理解算法，晦澀難懂的算法往往隱含錯(cuò)誤，不易被發(fā)現(xiàn)，并且難于調(diào)試和修改。

我在很久以前曾經(jīng)看到過一個(gè)網(wǎng)友寫的代碼，他號(hào)稱這程序是“用史上最少代碼實(shí)現(xiàn)俄羅斯方塊”。因?yàn)槲易约阂矊戇^類似的小游戲程序，所以想研究一下他是如何寫的。由于他追求的是“最少代碼”這樣的極致，使得他的代碼真的不好理解。也許除了計(jì)算機(jī)和他自己，絕大多數(shù)人是看不懂他的代碼的。

我們寫代碼的目的，一方面是為了讓計(jì)算機(jī)執(zhí)行，但還有一個(gè)重要的目的是為了便于他人閱讀，讓人理解和交流，自己將來也可能閱讀，如果可讀性不好，時(shí)間長(zhǎng)了自己都不知道寫了些什么。

健壯性

一個(gè)好的算法還應(yīng)該能對(duì)輸入數(shù)據(jù)不合法的情況做合適的處理。比如輸入的時(shí)間或者距離不應(yīng)該是負(fù)數(shù)等。

健壯性：當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出相關(guān)處理，而不是產(chǎn)生異?；蚰涿畹慕Y(jié)果。

時(shí)間效率高和存儲(chǔ)量低

最后，好的算法還應(yīng)該具備時(shí)間效率高和存儲(chǔ)量低的特點(diǎn)。

時(shí)間效率指的是算法的執(zhí)行時(shí)間，對(duì)于同一個(gè)問題，如果有多個(gè)算法能夠解決，執(zhí)行時(shí)間短的算法效率高，執(zhí)行時(shí)間長(zhǎng)的效率低。存儲(chǔ)量需求指的是算法在執(zhí)行過程中需要的最大存儲(chǔ)空間，主要指算法程序運(yùn)行時(shí)所占用的內(nèi)存或外部硬盤存儲(chǔ)空間。設(shè)計(jì)算法應(yīng)該盡量滿足時(shí)間效率高和存儲(chǔ)量低的需求。在生活中，人們都希望花最少的錢，用最短的時(shí)間，辦最大的事，算法也是一樣的思想，最好用最少的存儲(chǔ)空間，花最少的時(shí)間，辦成同樣的事就是好的算法。求100個(gè)人的高考成績(jī)平均分，與求全省的所有考生的成績(jī)平均分在占用時(shí)間和內(nèi)存存儲(chǔ)上是有非常大的差異的，我們自然是追求可以高效率和低存儲(chǔ)量的算法來解決問題。

綜上，好的算法，應(yīng)該具有正確性、可讀性、健壯性、高效率和低存儲(chǔ)量的特征。

算法效率的度量方法

設(shè)計(jì)算法要提高效率。這里效率大都指算法的執(zhí)行時(shí)間。那么我們?nèi)绾味攘恳粋€(gè)算法的執(zhí)行時(shí)間呢？

正所謂“是騾子是馬，拉出來遛遛”。比較容易想到的方法就是，我們通過對(duì)算法的數(shù)據(jù)測(cè)試，利用計(jì)算機(jī)的計(jì)時(shí)功能，來計(jì)算不同算法的效率是高還是低。

數(shù)組

線性表（數(shù)組）的定義

線性表，從名字上你就能感覺到，是具有像線一樣的性質(zhì)的表。一個(gè)班級(jí)的小朋友，一個(gè)跟著一個(gè)排著隊(duì)，有一個(gè)打頭，有一個(gè)收尾，當(dāng)中的小朋友每一個(gè)都知道他前面一個(gè)是誰，他后面一個(gè)是誰，這樣如同有一根線把他們串聯(lián)起來了。就可以稱之為線性表。

線性表（List）：零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列。

數(shù)組存儲(chǔ)原理

舉個(gè)簡(jiǎn)單的例子。一個(gè)允許用戶創(chuàng)建和使用購(gòu)物清單的食雜店應(yīng)用軟件，其源代碼可能會(huì)包含以下的片段。

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

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

此外，我們會(huì)用一些名為索引的數(shù)字來標(biāo)識(shí)每項(xiàng)數(shù)據(jù)在數(shù)組中的位置。

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

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

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

? 讀?。翰榭磾?shù)據(jù)結(jié)構(gòu)中某一位置上的數(shù)據(jù)。對(duì)于數(shù)組來說，這意味著查看某個(gè)索引所指的數(shù)據(jù)值。例如，查看索引2上有什么食品，就是一種讀取。

? 查找：從數(shù)據(jù)結(jié)構(gòu)中找出某個(gè)數(shù)據(jù)值的所在。對(duì)于數(shù)組來說，這意味著檢查其是否包含某個(gè)值，如果包含，那么還得給出其索引。例如，檢查"dates"是否存在于食品清單之中，給出其對(duì)應(yīng)的索引，就是一種查找。

? 插入：給數(shù)據(jù)結(jié)構(gòu)增加一個(gè)數(shù)據(jù)值。對(duì)于數(shù)組來說，這意味著多加一個(gè)格子并填入一個(gè)值。例如，往購(gòu)物清單中多加一項(xiàng)"figs"，就是一種插入。

? 刪除：從數(shù)據(jù)結(jié)構(gòu)中移走一個(gè)數(shù)據(jù)值。對(duì)于數(shù)組來說，這意味著把數(shù)組中的某個(gè)數(shù)據(jù)項(xiàng)移走。例如，把購(gòu)物清單中的"bananas"移走，就是一種刪除。

我們將會(huì)研究這些操作在數(shù)組上的運(yùn)行速度。

同時(shí)，我們也將學(xué)到本書的第一個(gè)重要理論：操作的速度，并不按時(shí)間計(jì)算，而是按步數(shù)計(jì)算。

為什么呢？

因?yàn)?，你不可能很絕對(duì)地說，某項(xiàng)操作要花5秒。它在某臺(tái)機(jī)器上要跑5秒，但換到一臺(tái)舊一點(diǎn)的機(jī)器，可能就要多于5秒，而換到一臺(tái)未來的超級(jí)計(jì)算機(jī)，運(yùn)行時(shí)間又將顯著縮短。所以，受硬件影響的計(jì)時(shí)方法，非常不可靠。

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

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

讀取

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

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

計(jì)算機(jī)為什么能一步到位呢？原因如下。

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

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

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

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

計(jì)算機(jī)之所以在讀取數(shù)組中某個(gè)索引所指的值時(shí)，能直接跳到那個(gè)位置上，是因?yàn)樗邆湟韵聴l件。

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

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

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

回到剛才的例子，當(dāng)我們叫計(jì)算機(jī)讀取索引3的值時(shí)，它會(huì)做以下演算。

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

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

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

當(dāng)計(jì)算機(jī)一步跳到1013時(shí)，我們就能獲取到"dates"這個(gè)值了。

所以，數(shù)組的讀取是一種非常高效的操作，因?yàn)樗灰徊骄秃?。一步自然也是最快的速度。這種一步讀取任意索引的能力，也是數(shù)組好用的原因之一。

查找

對(duì)于數(shù)組來說，查找就是檢查它是否包含某個(gè)值，如果包含，還得給出其索引。那么，我們就試試在數(shù)組中查找"dates"要用多少步。

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

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

我們用以下圖來演示計(jì)算機(jī)如何從購(gòu)物清單中查找"dates"。

首先，計(jì)算機(jī)檢查索引0。

因?yàn)樗饕?的值是"apples"，并非我們所要的"dates"，所以計(jì)算機(jī)跳到下一個(gè)索引上。

索引1也不是"dates"，于是計(jì)算機(jī)再跳到索引2。

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

我們找到"dates"了，它就在索引3那里。自此，計(jì)算機(jī)不用再往后跳了，因?yàn)榻Y(jié)果已經(jīng)得到。

在這個(gè)例子中，因?yàn)槲覀儥z查了4個(gè)格子才找到想要的值，所以這次操作總計(jì)是4步。

這種逐個(gè)格子去檢查的做法，就是最基本的查找方法——線性查找。

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

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

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

可見，無論是多長(zhǎng)的數(shù)組，查找都比讀取要慢，因?yàn)樽x取永遠(yuǎn)都只需要一步，而查找卻可能需要多步。

插入

往數(shù)組里插入一個(gè)新元素的速度，取決于你想把它插入到哪個(gè)位置上。

假設(shè)我們想要在購(gòu)物清單的末尾插入"figs"。那么只需一步。因?yàn)橹罢f過了，計(jì)算機(jī)知道數(shù)組開頭的內(nèi)存地址，也知道數(shù)組包含多少個(gè)元素，所以可以算出要插入的內(nèi)存地址，然后一步跳到那里插入就行了。圖示如下。

但在數(shù)組開頭或中間插入，就另當(dāng)別論了。這種情況下，我們需要移動(dòng)其他元素以騰出空間，于是得花費(fèi)額外的步數(shù)。

例如往索引2處插入"figs"，如下所示。

為了達(dá)到目的，我們必須先把"cucumbers"、“dates"和"elderberries"往右移，以便空出索引2。而這也不是一步就能移好，因?yàn)槲覀兪紫纫獙?elderberries"右移一格，以空出位置給"dates”，然后再將"dates"右移，以空出位置給"cucumbers"，下面來演示這個(gè)過程。

第1步："elderberries"右移。

第2步："date"右移。

第3步："cucembers"右移。

第4步：至此，可以在索引2處插入"figs"了。

如上所示，整個(gè)過程有4步，開始3步都是在移動(dòng)數(shù)據(jù)，剩下1步才是真正的插入數(shù)據(jù)。

最低效（花費(fèi)最多步數(shù)）的插入是插入在數(shù)組開頭。因?yàn)檫@時(shí)候需要把數(shù)組所有的元素都往右移。

于是，一個(gè)含有N個(gè)元素的數(shù)組，其插入數(shù)據(jù)的最壞情況會(huì)花費(fèi)N + 1步。即插入在數(shù)組開頭，導(dǎo)致N次移動(dòng)，加上一次插入。

刪除

數(shù)組的刪除就是消掉其某個(gè)索引上的數(shù)據(jù)。

我們找回最開始的那個(gè)數(shù)組，刪除索引2上的值，即"cucumbers"。

第1步：刪除"cucumbers"。

雖然刪除"cucumbers"好像一步就搞定了，但這帶來了新的問題：數(shù)組中間空出了一個(gè)格子。因?yàn)閿?shù)組中間是不應(yīng)該有空格的，所以，我們得把"dates"和"elderberries"往左移。

第2步：將"dates"左移。

第3步：將"elderberries"左移。
結(jié)果，整個(gè)刪除操作花了3步。其中第1步是真正的刪除，剩下的2步是移數(shù)據(jù)去填空格。

所以，刪除本身只需要1步，但接下來需要額外的步驟將數(shù)據(jù)左移以填補(bǔ)刪除所帶來的空隙。

跟插入一樣，刪除的最壞情況就是刪掉數(shù)組的第一個(gè)元素。因?yàn)閿?shù)組不允許空元素，當(dāng)索引0空出，那么剩下的所有元素都要往左移去填空。

對(duì)于含有5個(gè)元素的數(shù)組，刪除第一個(gè)元素需要1步，左移剩余的元素需要4步。而對(duì)于500個(gè)元素的數(shù)組，刪除第一個(gè)元素需要1步，左移剩余的元素需要499步?？梢酝瞥?，對(duì)于含有N個(gè)元素的數(shù)組，刪除操作最多需要N步。

既然學(xué)會(huì)了如何分析數(shù)據(jù)結(jié)構(gòu)的時(shí)間復(fù)雜度，那就可以開始探索各種數(shù)據(jù)結(jié)構(gòu)的性能差異了。了解這些非常重要，因?yàn)閿?shù)據(jù)結(jié)構(gòu)的性能差異會(huì)直接造成程序的性能差異。

數(shù)組在以下標(biāo)隨機(jī)讀取的速度是很快的，但是查找、刪除、插入相對(duì)是很慢的，數(shù)組越長(zhǎng)越慢！

所以數(shù)組適合放數(shù)據(jù)以下標(biāo)方式讀取，不適合做查找、刪除、插入操作。文章來源地址http://www.zghlxwxcb.cn/news/detail-680346.html

到了這里，關(guān)于基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)：數(shù)組介紹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！