數(shù)據(jù)結(jié)構(gòu)是軟件開(kāi)發(fā)的關(guān)鍵部分,也是開(kāi)發(fā)人員面試經(jīng)常遇到的問(wèn)題,它們通常以專(zhuān)用的格式進(jìn)行數(shù)據(jù)組織和存儲(chǔ)。本文我們將會(huì)介紹十種典型的數(shù)據(jù)結(jié)構(gòu)及其特性。需要注意的是,雖然一些數(shù)據(jù)結(jié)構(gòu)包含了時(shí)間復(fù)雜度O,但不完全都有因?yàn)闀r(shí)間復(fù)雜度很多時(shí)候與你的代碼書(shū)寫(xiě)有關(guān)。實(shí)際使用時(shí),大多數(shù)的數(shù)學(xué)結(jié)構(gòu)都不需要你自己實(shí)現(xiàn)它們,除非像C語(yǔ)言這樣的底層語(yǔ)言。雖然大多數(shù)高級(jí)語(yǔ)言一般都會(huì)內(nèi)置這些數(shù)據(jù)結(jié)構(gòu),但如果你知道如何實(shí)現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)將會(huì)為你在開(kāi)發(fā)工作中帶來(lái)巨大優(yōu)勢(shì),說(shuō)不定當(dāng)你嘗試編寫(xiě)高性能代碼時(shí)就會(huì)派上用場(chǎng)。
1. 鏈表
鏈表屬于最基本的數(shù)據(jù)結(jié)構(gòu)。由于許多數(shù)據(jù)結(jié)構(gòu)既可以用數(shù)組也可以用鏈表來(lái)實(shí)現(xiàn),所以通常會(huì)與數(shù)組進(jìn)行比較,但它們各有優(yōu)缺點(diǎn)。
鏈表通常由一組代表一個(gè)序列的節(jié)點(diǎn)組成。 每個(gè)節(jié)點(diǎn)包含存儲(chǔ)的任意類(lèi)型實(shí)際數(shù)據(jù)以及指向序列中下一個(gè)節(jié)點(diǎn)的指針。特殊的,還有雙向鏈表,其中每個(gè)節(jié)點(diǎn)都有兩個(gè)指針,分別起到承前啟后的作用。
鏈表中最基本的操作是插入鏈表、刪除鏈表以及查詢(xún)鏈表。下表為鏈表的時(shí)間復(fù)雜度:
2. 堆棧
堆棧屬于一種基本的數(shù)據(jù)結(jié)構(gòu),你只能在堆棧的頂部插入或刪除項(xiàng)目。這有點(diǎn)像一堆書(shū), 如果你想看堆棧中間的一本書(shū),你必須先將它上面上面的所有書(shū)移走。
堆棧遵循后進(jìn)先出,也就是說(shuō)你最后放入堆棧的項(xiàng)目是第一個(gè)出棧的項(xiàng)目。
對(duì)堆棧主要有三種操作:push,即插入新內(nèi)容到堆棧;pop,從堆棧中刪除一項(xiàng)內(nèi)容;pip,顯示堆棧的內(nèi)容。
堆棧時(shí)間復(fù)雜度:
3.隊(duì)列
你可以把隊(duì)列想象成一家雜貨店里排隊(duì)買(mǎi)單的人,隊(duì)伍中第一個(gè)人先被服務(wù)。
隊(duì)列遵循先進(jìn)先出,也就是說(shuō)一旦你想添加了新元素,你要想刪除它,必須先刪除它前面的的所有元素。隊(duì)列只有兩個(gè)主要操作:入隊(duì)和出隊(duì)。 入隊(duì),就是將新的內(nèi)容插入隊(duì)列后面,而出隊(duì)就是前面所有的內(nèi)容。
隊(duì)列時(shí)間復(fù)雜度:
4.集合
以集合形式存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)中不存在任何特定的順序,也不存在重復(fù)的值。除了向集合中添加新元素或者刪除元素之外,還有一些重要的集合函數(shù)可以進(jìn)行兩組集合的處理。
并集,將來(lái)自?xún)蓚€(gè)不同集合的所有元素結(jié)合起來(lái)作為新集合返回(不重復(fù)).
交集,給定兩個(gè)集合,此函數(shù)返回另一個(gè)集合,包含屬于兩個(gè)集合的共同部分。
差集,給定兩個(gè)集合,此函數(shù)返回另一個(gè)集合,其中各個(gè)元素屬于一個(gè)集合,但不屬于另一個(gè)集合。
子集 ,返回一個(gè)布爾值,顯示一個(gè)集合中的所有元素是否包含在不同的集合中。
5. MAP
Map是容器的一種,也屬于一種數(shù)據(jù)結(jié)構(gòu),它將數(shù)據(jù)存儲(chǔ)在鍵/值對(duì)中,且每個(gè)鍵是唯一的。 map有時(shí)也稱(chēng)為關(guān)聯(lián)數(shù)組或字典,通常被用于快速查找數(shù)據(jù)。 Map可以進(jìn)行以下操作:
在集合中增加一對(duì)
從集合中刪除一對(duì)
修改現(xiàn)有的一對(duì)
查找與特定鍵相關(guān)聯(lián)的值
6.哈希表
哈希表是包含鍵/值對(duì)的地圖數(shù)據(jù)結(jié)構(gòu),使用散列函數(shù)來(lái)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄,以加快查找的速度。散列函數(shù)通常將一個(gè)字符串作為輸入,并輸出一個(gè)數(shù)值。散列函數(shù)對(duì)相同的輸入提供相同的輸出編號(hào)。 當(dāng)兩個(gè)輸入哈希得到相同的數(shù)字輸出時(shí),稱(chēng)為碰撞。
我們的目標(biāo)是沒(méi)有碰撞。所以當(dāng)你將一個(gè)鍵/值對(duì)輸入到一個(gè)散列表中時(shí),這個(gè)鍵將通過(guò)散列函數(shù)映射到一個(gè)數(shù)字,用作值存儲(chǔ)的實(shí)際鍵。 當(dāng)你嘗試再次訪(fǎng)問(wèn)相同的密鑰時(shí),哈希函數(shù)將處理該密鑰并返回相同的數(shù)字結(jié)果,用于查找關(guān)聯(lián)的值。 算法速度非常快,查找的時(shí)間復(fù)雜度僅為O(1)。
Hash table 時(shí)間復(fù)雜度:
7.二叉搜索樹(shù)
樹(shù)是由節(jié)點(diǎn)組成的數(shù)據(jù)結(jié)構(gòu),它具有以下特征:
每棵樹(shù)都有一個(gè)根節(jié)點(diǎn)(位于頂部)。
根節(jié)點(diǎn)具有零個(gè)或多個(gè)子節(jié)點(diǎn)。
每個(gè)子節(jié)點(diǎn)都有零個(gè)或多個(gè)子節(jié)點(diǎn)。
二叉搜索樹(shù)還具有額外的兩個(gè)特征:
每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn).
對(duì)于每個(gè)節(jié)點(diǎn),它左邊的子節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn),而右邊的子節(jié)點(diǎn)則大于當(dāng)前節(jié)點(diǎn)。
每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。
二叉搜索樹(shù)允許快速查找、添加和刪除內(nèi)容。 從它的設(shè)計(jì)結(jié)構(gòu)來(lái)看,每次比較后都會(huì)跳過(guò)樹(shù)的大約一半內(nèi)容,因此每次查找、插入或刪除需要的操作時(shí)間與存儲(chǔ)在樹(shù)中的內(nèi)容數(shù)量的對(duì)數(shù)成比例。
二叉樹(shù)時(shí)間復(fù)雜度:
8. 前綴樹(shù)或字典樹(shù)
前綴樹(shù)或字典樹(shù),是一種搜索樹(shù)。 前綴樹(shù)中存儲(chǔ)數(shù)據(jù)的每個(gè)步驟其實(shí)就是操作一個(gè)節(jié)點(diǎn),它通常被用來(lái)存儲(chǔ)單詞,可以進(jìn)行快速查找,例如單詞自動(dòng)構(gòu)成功能。
語(yǔ)言字典樹(shù)中的每個(gè)節(jié)點(diǎn)都包含一個(gè)單詞的一個(gè)字母。 你可以按照樹(shù)狀結(jié)構(gòu)的一條分支拼寫(xiě)出一個(gè)單詞。 當(dāng)字母的順序與字典中的其他單詞不同或者一個(gè)單詞完成時(shí),開(kāi)始分支。每個(gè)節(jié)點(diǎn)都包含一個(gè)字母(數(shù)據(jù))和一個(gè)布爾值(用于指示該節(jié)點(diǎn)是否是單詞中的最后一個(gè)節(jié)點(diǎn))。
看看上面的圖像,你可以構(gòu)成很多單詞。從頂部的根節(jié)點(diǎn)開(kāi)始并往下,這個(gè)字典樹(shù)包含了ball, bat, doll, do, dork, dorm, send, sense這些單詞。
9.二叉堆
二叉堆是特殊的樹(shù)數(shù)據(jù)結(jié)構(gòu)。形式上看,它從頂點(diǎn)開(kāi)始,每個(gè)節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn),每個(gè)子節(jié)點(diǎn)又各自有自己的兩個(gè)子節(jié)點(diǎn);數(shù)值上看,每個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都比它大或小。
二叉堆有兩種:最大堆和最小堆。最大堆:父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值;最小堆:父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值。
在二叉堆上可以進(jìn)行插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)、取出值最小的節(jié)點(diǎn)、減小節(jié)點(diǎn)的值等基本操作。不同層之間的順序很重要,但同一層上節(jié)點(diǎn)的順序無(wú)關(guān)緊要。 如圖所示,你可以看到最小堆的第三層的值是10,6和12,這些數(shù)字并不是按照順序排列的。
二叉堆時(shí)間復(fù)雜度:
10. 圖
圖是由節(jié)點(diǎn)(也稱(chēng)為頂點(diǎn))與它們之間的連接(稱(chēng)為邊)構(gòu)成的集合。圖也被稱(chēng)為網(wǎng)絡(luò)。
社交網(wǎng)絡(luò)是典型的圖的例子,節(jié)點(diǎn)是人,邊代表他們互相認(rèn)識(shí)的關(guān)系。
主要有兩種類(lèi)型的圖:有向和無(wú)向。無(wú)向圖是指在節(jié)點(diǎn)之間的邊上沒(méi)有任何方向的圖。相反,有向圖表示每條邊上都有方向的圖。
表示圖的兩種常用方式是鄰接表和鄰接矩陣:
鄰接列表,表示一個(gè)列表的左側(cè)是節(jié)點(diǎn),右側(cè)列出了它所連接的所有其他節(jié)點(diǎn)。
鄰接矩陣,則是一個(gè)數(shù)字網(wǎng)格。其中每個(gè)行或列表示圖中的不同節(jié)點(diǎn)。每一行和一列的交點(diǎn)是一個(gè)表示關(guān)系的數(shù)字。0表示沒(méi)有邊或沒(méi)有關(guān)系,1表示有一種關(guān)系,而大于1的數(shù)字則可表示不同的權(quán)重。
通過(guò)遍歷算法可以遍歷或訪(fǎng)問(wèn)圖中的節(jié)點(diǎn)。遍歷算法的主要類(lèi)型有廣度優(yōu)先搜索和深度優(yōu)先搜索,可以被用于確定節(jié)點(diǎn)與根節(jié)點(diǎn)的接近程度。觀看下面的視頻你可以學(xué)習(xí)到如何在JavaScript中實(shí)現(xiàn)廣度優(yōu)先搜索。
鄰接列表的時(shí)間復(fù)雜度:
-
數(shù)據(jù)結(jié)構(gòu)
+關(guān)注
關(guān)注
3文章
573瀏覽量
40123 -
鏈表
+關(guān)注
關(guān)注
0文章
80瀏覽量
10558
原文標(biāo)題:盤(pán)點(diǎn) | 如何組織你的數(shù)據(jù)?這里有十種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)解讀
文章出處:【微信號(hào):thejiangmen,微信公眾號(hào):將門(mén)創(chuàng)投】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論