數(shù)據(jù)結(jié)構(gòu)中常見容器原理分析

舒尹

摘 要：當(dāng)今的網(wǎng)絡(luò)世界中，數(shù)據(jù)日益增多，對數(shù)據(jù)的處理成為了至關(guān)重要的一環(huán)。各種各樣的數(shù)據(jù)結(jié)構(gòu)為數(shù)據(jù)處理提供了方便，而容器是其中用來緩存數(shù)據(jù)的重要工具，容器實(shí)現(xiàn)了對重復(fù)問題的固定解決方案。本文從數(shù)據(jù)結(jié)構(gòu)入手介紹了線性表，散列表和樹幾種常用的數(shù)據(jù)結(jié)構(gòu)。再對容器的概念做了詳細(xì)說明，又對比了list，map等各式容器，最終給出了在不同情景下選擇不同容器的建議。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu);容器;散列表;map

中圖分類號：R446 文獻(xiàn)標(biāo)識碼：A 文章編號：1671-2064（2019）02-0036-02

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

存儲在計(jì)算機(jī)中的數(shù)據(jù)之間存在一定的聯(lián)系，這種聯(lián)系體現(xiàn)在數(shù)據(jù)之間所具備的邏輯關(guān)系，同時對應(yīng)著數(shù)據(jù)在計(jì)算機(jī)中的存儲結(jié)構(gòu)。以上所述的數(shù)據(jù)間的聯(lián)系就被稱為數(shù)據(jù)結(jié)構(gòu)。它包含：數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲（物理）結(jié)構(gòu)。

邏輯結(jié)構(gòu)描述了數(shù)據(jù)元素間的邏輯關(guān)系，大致分為：線性結(jié)構(gòu)和非線性結(jié)構(gòu)[1]。線性結(jié)構(gòu)是指數(shù)據(jù)元素之間存在一對一的關(guān)系，非線性結(jié)構(gòu)則包含了一對多，多對多等關(guān)系。

數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的具體表示（又稱映像），其有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種類型。數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)，與數(shù)據(jù)的存儲方式無關(guān)。而存儲結(jié)構(gòu)是在計(jì)算機(jī)內(nèi)存中對邏輯結(jié)構(gòu)的實(shí)現(xiàn)，是計(jì)算機(jī)用于處理數(shù)據(jù)的邏輯。

此外，數(shù)據(jù)操作也是數(shù)據(jù)結(jié)構(gòu)的研究對象，不同的邏輯結(jié)構(gòu)對應(yīng)有不同的操作，這是由于數(shù)據(jù)的操作是定義在邏輯結(jié)構(gòu)之上的。常用的操作主要有：訪問元素，更新元素，插入元素，刪除元素和排序元素等等。

數(shù)據(jù)結(jié)構(gòu)的概念興于上世紀(jì)七十年代，是隨程序的結(jié)構(gòu)設(shè)計(jì)而一起提出的。在設(shè)計(jì)程序時，先確定了數(shù)據(jù)結(jié)構(gòu)后，往往算法也就隨之確定了。或是反過來由特定的算法來確定合適的數(shù)據(jù)結(jié)構(gòu)。前種情況中，數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)的關(guān)鍵，而不是算法，這種想法也包括了面向?qū)ο蟮某绦蛟O(shè)計(jì)思想。

下面介紹一些基本的數(shù)據(jù)結(jié)構(gòu)：

線性表是數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的結(jié)構(gòu)，它按存儲結(jié)構(gòu)的不同分為順序表和鏈表兩類[2]。

順序表和鏈表都是順序存放的數(shù)據(jù)元素的有限序列。不同的是，兩者的線性邏輯結(jié)構(gòu)是以不同存儲結(jié)構(gòu)來實(shí)現(xiàn)的。

順序表中的數(shù)據(jù)元素存放在一組連續(xù)的內(nèi)存中。而鏈表中的數(shù)據(jù)存儲在內(nèi)存上不連續(xù)的節(jié)點(diǎn)中，而每個節(jié)點(diǎn)都存在表示邏輯關(guān)系的標(biāo)志，這種標(biāo)志叫作指針[3]。由兩者的存儲特點(diǎn)可以看出：順序表可以很方便地進(jìn)行數(shù)據(jù)檢索，而鏈表更加適應(yīng)于數(shù)據(jù)的插入和刪除，因?yàn)樵诓迦牖騽h除元素時，實(shí)質(zhì)上是在操作元素的指針。

樹結(jié)構(gòu)是一種非線性結(jié)構(gòu)，它是數(shù)據(jù)元素（在樹中稱為節(jié)點(diǎn)）按分支關(guān)系組織起來的結(jié)構(gòu)，一棵樹只有一個根節(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)，其余每個節(jié)點(diǎn)有且只有一個前驅(qū)節(jié)點(diǎn)。大部分節(jié)點(diǎn)可以有一個或多個后繼節(jié)點(diǎn)，而我們將沒有后繼節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)。

散列表是一種映射結(jié)構(gòu)。它可以根據(jù)鍵碼（key）直接找到對應(yīng)的值，從而進(jìn)行訪問[4]。這種以鍵一值的方式存儲數(shù)據(jù)的結(jié)構(gòu)，十分適用于數(shù)據(jù)的查找。用于查找的映射關(guān)系稱為散列函數(shù)，用于存放值的順序表稱為散列表。其實(shí)，完全可以用字典來說明這種結(jié)構(gòu)。比如，當(dāng)我們用音節(jié)或偏旁去查找“中”字時，實(shí)際就是用一種鍵值映射去完成查找。“中”的字形或讀音就是key，查閱的過程就是在索引，而最終查詢到的頁數(shù)以及“中”字的具體解釋就是對應(yīng)的值。

2 容器

容器仍是來源于數(shù)據(jù)結(jié)構(gòu)的，某個特定容器的底層原理可能是由某種相關(guān)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。由此可見，容器就是由數(shù)據(jù)結(jié)構(gòu)提煉而來的產(chǎn)物，一個容器就是一種數(shù)據(jù)結(jié)構(gòu)的實(shí)例。容器可以存儲對象，而它自身仍是一個可被操作的對象，它被認(rèn)為是一類對象的集合。簡單來講，容器就是存放對象的對象。但是，它自身包含處理其他對象的一類方法，實(shí)現(xiàn)了對重復(fù)問題的固定解決方案。

容器的一大優(yōu)點(diǎn)是它可以自動擴(kuò)展。可以自行管理和分配內(nèi)存空間的容器能解決這樣的問題，設(shè)置對象時，我們不需要預(yù)先知道對象占用內(nèi)存的大小，只需要創(chuàng)建一個合適的容器對象，調(diào)用對應(yīng)的操作方法，容器會自行考慮完成其中的處理細(xì)節(jié)。也就是說，當(dāng)你發(fā)出指令時，容器會自動申請內(nèi)存，并采用最優(yōu)化的算法去執(zhí)行指令。

在說到容器時，更容易想到的是生活中各種實(shí)體。比如裝水的杯子，放雜物的收納盒等等。一個旅行箱中可以放置許多衣物，衣物視作對象，那么旅行箱也可視作對象。更極端一點(diǎn)，大旅行箱中放一個小旅行箱的情況即容器之中存放容器的情況也是存在的。

在書寫程序時，不同的場景下選擇不同的容器對數(shù)據(jù)進(jìn)行緩存，很大程度上影響著程序運(yùn)行的時間和性能。按容器中元素的組織方式，可把容器分為順序容器和關(guān)聯(lián)容器兩大類。

順序容器是一種線性表，它將相同類型的元素以嚴(yán)格的順序關(guān)系進(jìn)行組織。順序容器中的元素有固定的位置，這個位置不因元素的改變而改變，除非用插入或刪除的操作來改變這個位置。在操作元素時，操作的邏輯順序直接成為元素的存儲順序，即兩者之間是相互對應(yīng)的。

關(guān)聯(lián)容器屬于一種非線性的樹結(jié)構(gòu)。元素存入不會保留操作時的邏輯順序，但關(guān)聯(lián)容器可以根據(jù)元素的特點(diǎn)對元素進(jìn)行排序。此外，關(guān)聯(lián)容器的顯著特點(diǎn)是它以鍵值形式進(jìn)行存儲，在這一點(diǎn)上，可以認(rèn)為順序容器只保留鍵或值的一種。

List的底層是由線性表實(shí)現(xiàn)的。比如在由鏈表實(shí)現(xiàn)的list中，數(shù)據(jù)是以節(jié)點(diǎn)的形式構(gòu)成的，一個節(jié)點(diǎn)包括實(shí)際存儲的數(shù)據(jù)，一個前驅(qū)和后驅(qū)指針。因?yàn)樵谖锢韮?nèi)存中，其存儲是不連續(xù)的，所以list不需要給它分配特定大小的內(nèi)存，它可以任意的進(jìn)行擴(kuò)展。由于其結(jié)構(gòu)特點(diǎn)，list進(jìn)行數(shù)據(jù)的檢索時需要對其進(jìn)行順序訪問，那么當(dāng)數(shù)據(jù)量很大時，隨機(jī)檢索的性能就變得很差了，越是在list中靠后的數(shù)據(jù)將要進(jìn)行檢索的時間就越長。雖然檢索的性能不高，但鏈表結(jié)構(gòu)的list適用于數(shù)據(jù)的插入和刪除。在插入或刪除節(jié)點(diǎn)時，指僅僅最多對三個元素有影響，提高了操作的效率。

Vector相當(dāng)于一個數(shù)組，但又不只是一個數(shù)組。數(shù)組是靜態(tài)的，數(shù)組的空間在分配之后一般不能改變，如果原有的空間滿足不了需求，就只能重新申請更大的數(shù)組，然后把原數(shù)據(jù)拷貝到新的數(shù)組之中。而Vector是一個動態(tài)數(shù)組，它會自行分配內(nèi)存空間，也就是說，Vector自行完成了上述在面對空間不夠時，重新申請空間然后拷貝數(shù)據(jù)的過程。容器自動擴(kuò)展的特點(diǎn)得以體現(xiàn)。但這并不意味著在數(shù)據(jù)量很大時，自行擴(kuò)展的Vector效率就高，它的性能仍是很糟糕的，所以它通常會預(yù)留一部分空間，且預(yù)留空間是以一定比例增長的。另一方面，Vector中的數(shù)據(jù)是連續(xù)存儲在內(nèi)存中的，它可以方便的進(jìn)行隨機(jī)訪問。同時由于Vector底層是由順序表實(shí)現(xiàn)的，一般只能在Vector的尾部進(jìn)行追加和刪除。

Vector和list同為順序容器，將兩者進(jìn)行對比是很有必要的;

Vector是一段連續(xù)存儲數(shù)據(jù)，而鏈表實(shí)現(xiàn)的list是將所有的元素分開進(jìn)行保存的，在使用時，用Vector進(jìn)行隨機(jī)檢索的性能很好，在Vector尾部追加數(shù)據(jù)的性能也不錯，除非需要重新申請內(nèi)存。而鏈表list中元素可以不連續(xù)，使用指針使它適用于插入，刪除元素而不適合進(jìn)行查詢。

所以，如果需要高效率的任意存取，就選擇Vector，如果需要頻繁的插入或刪除元素而隨機(jī)存取不那么重要時，就選擇list。

另外還有一種介于兩者之間的容器--deque，它兼顧了兩者的優(yōu)點(diǎn)，它的查詢和插入/刪除的性能是介于兩者之間的，適用于即需要隨機(jī)存取又有較頻繁的插入，刪除的情況。

Map和Set屬于關(guān)聯(lián)容器，都為非線性的樹結(jié)構(gòu)。

Set又稱集合，為一組元素的集合，但儲存的元素的值是唯一的，且元素是有一定的順序的，同時也把集合中的一個元素叫做集合的實(shí)例。Map（映射）提供了”鍵-值“關(guān)系儲存數(shù)據(jù)的方式。Map的每一個元素都由兩部分組成，其中的鍵（key）在容器中不允許重復(fù)，且是經(jīng)過排序的。

以下為更具體的說明：

Set，Map封裝了一種二叉樹的結(jié)構(gòu)，它的插入刪除效率一般較高，它們中的數(shù)據(jù)以節(jié)點(diǎn)存儲，與鏈表相似，插入時只需將指針指向新的節(jié)點(diǎn)，而不需要移動和拷貝內(nèi)存。另外，Set和Map的查找效率是較高的，它們采用的是二分查找的方式，當(dāng)數(shù)據(jù)元素增加時，查找的效率并不會大幅的降低，要解釋這個現(xiàn)象就需要理解其中具體的實(shí)現(xiàn)原理。簡單來講，查找的效率同以2為底的對數(shù)函數(shù)，即使數(shù)據(jù)量（自變量）增加的幅度很大，查找的時間（函數(shù)值）并不明顯增加。

3 容器總結(jié)

在插入和刪除元素時，關(guān)聯(lián)容器是快于Vector而慢于list的。Vector是順序結(jié)構(gòu)而關(guān)聯(lián)容器與list同為鏈?zhǔn)浇Y(jié)構(gòu)，但list是線性的。在改變元素時，關(guān)聯(lián)容器涉及更多元素的改變，且還需對改變后的元素進(jìn)行排序，這使其性能降低。

關(guān)聯(lián)容器的查找比Vector慢，但比list快很多。Vector采用順序結(jié)構(gòu)，關(guān)聯(lián)容器自然無法相比，但二分查找的方式又是大大優(yōu)于list的，且數(shù)據(jù)越多，優(yōu)越性越明顯。

Map提供了一種重要的存儲數(shù)據(jù)的方式，即以“鍵-值”關(guān)系進(jìn)行存儲。索引元素時，它用字符型的關(guān)鍵字進(jìn)行索引，類似于數(shù)組中以下標(biāo)的方式來索引元素，這是其他容器無法取代的。

在不同的情況下，要選擇適合的容器。一般而言，list適用于大量插入和刪除元素的情況，vector更適合用于大量數(shù)據(jù)的隨機(jī)讀取，map提供了“鍵—值”映射，十分適用于數(shù)據(jù)的查詢。

4 結(jié)語

通過以上的探究，不難看出，容器的選擇對編程的效率有著長遠(yuǎn)的影響。容器相當(dāng)于處理一類事物的方法，方法選對后，后續(xù)的工作才會事半功倍。生活需面臨的各種問題也是這樣，以一個好的方法開始，往往結(jié)果才會以我們想要的方式出現(xiàn)。

參考文獻(xiàn)

[1] 王立柱，王春枝.C/C++與數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社，2016.

[2] 歐建圣.線性表在《數(shù)據(jù)結(jié)構(gòu)》中重要性分析[J].武漢工程職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2001，13（1）：64-66.

[3] 趙玉勇，劉鳳亮.VB中用類模塊實(shí)現(xiàn)棧和鏈表數(shù)據(jù)結(jié)構(gòu)[J].中文信息，2002（5）：64-66.

[4] 馬如林，蔣華，張慶霞.一種哈希表快速查找的改進(jìn)方法[J].計(jì)算機(jī)工程與科學(xué)，2008，30（9）：66-68.