5月安卓手機(jī)好評(píng)榜：魅族20 Pro奪冠
性能榜和性?xún)r(jià)比榜之后，我們來(lái)看最后的安卓手機(jī)好評(píng)榜，數(shù)據(jù)來(lái)源安兔兔評(píng)測(cè)，收集時(shí)間2023年5月1日至5月31日，僅限國(guó)內(nèi)市場(chǎng)。第一名：魅族20 Pro好評(píng)率：97.50%不得不感慨魅族老品牌還
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。在工作中，我們通常會(huì)直接使用已經(jīng)封裝好的集合API，這樣可以更高效地完成任務(wù)。但是作為一名程序員，掌握數(shù)據(jù)結(jié)構(gòu)是非常重要的，因?yàn)樗梢詭椭覀兏玫乩斫夂驮O(shè)計(jì)算法，從而提高程序的效率和可靠性。本文將對(duì)常見(jiàn)的幾種數(shù)據(jù)結(jié)構(gòu)進(jìn)行介紹，通過(guò)了解這些數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)和優(yōu)勢(shì)，可以更好地在不同場(chǎng)景下選擇合適的數(shù)據(jù)結(jié)構(gòu)。
常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)大體分為兩種類(lèi)型：線(xiàn)性和非線(xiàn)性。
線(xiàn)性數(shù)據(jù)結(jié)構(gòu)見(jiàn)名思義，整體結(jié)構(gòu)的圖像是一條直線(xiàn)。包括數(shù)組、鏈表、棧、隊(duì)列等。
非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)包括，樹(shù)、堆、圖等。
數(shù)組是由多個(gè)元素組成的一個(gè)集合，表現(xiàn)形式如下圖
在內(nèi)存中存儲(chǔ)數(shù)組的空間是連續(xù)的，每個(gè)元素占據(jù)一定的內(nèi)存空間，這也是為什么在聲明數(shù)組時(shí)要指定長(zhǎng)度，不然不知道要占用多少空間。以 Java 語(yǔ)言為例，當(dāng)聲明一個(gè)數(shù)組后，數(shù)組變量會(huì)指向數(shù)組對(duì)象的起始地址，也就是第一個(gè)元素的位置，如下圖
以此看來(lái)，當(dāng)查詢(xún)數(shù)組中的某個(gè)元素時(shí)，通過(guò)下標(biāo)就可以計(jì)算出這個(gè)元素的內(nèi)存地址，比如想查找下標(biāo)為2的元素，那么arr[2]的內(nèi)存地址 = arr的內(nèi)存地址 + 2 * 元素大小，也就可以直接通過(guò)內(nèi)存地址訪(fǎng)問(wèn)元素，時(shí)間復(fù)雜度為O(1)。
但是，數(shù)組也會(huì)帶來(lái)一個(gè)問(wèn)題：由于數(shù)組長(zhǎng)度是固定的，所以在添加或刪除元素時(shí)會(huì)涉及到創(chuàng)建新的數(shù)組來(lái)替換原數(shù)組，導(dǎo)致復(fù)雜度較高。例如，下面的代碼演示了如何在數(shù)組末尾添加一個(gè)元素：
int[] arr = {1, 2, 3, 4, 5}; arr[arr.length] = 6; // 將要添加的元素放到數(shù)組的最后一個(gè)位置 int[] newArr = new int[arr.length + 1]; // 創(chuàng)建一個(gè)新的數(shù)組，長(zhǎng)度加1 for (int i = 0; i < newArr.length; i++) { newArr[i] = arr[i]; // 將原數(shù)組中的元素復(fù)制到新數(shù)組中 } arr = newArr; // 使用新數(shù)組替換原數(shù)組示例代碼在內(nèi)存中的活動(dòng)如下圖
在 Java 中有很多集合的底層實(shí)現(xiàn)都是基于數(shù)組，例如大家常用的 ArrayList、Vector、HashMap、ArrayBlockingQueue等等。
鏈表由一系列結(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)節(jié)點(diǎn)地址的指針域。以 Java 為例，一個(gè)節(jié)點(diǎn)的結(jié)構(gòu)是這樣表示的：
public class Node<T> { //存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域 private T value; //下一個(gè)節(jié)點(diǎn)地址的指針域 private Node next;}每個(gè)元素的指針指向下一個(gè)元素，從而形成鏈表，表現(xiàn)形式如下圖。
與數(shù)組不同，鏈表在內(nèi)存中是非連續(xù)的空間，可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理，解決了數(shù)組需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)。其在內(nèi)存中的存儲(chǔ)如下圖
相比于數(shù)組，鏈表的插入和刪除操作可以達(dá)到O(1)的復(fù)雜度（只需要將鏈尾的指針指向下個(gè)節(jié)點(diǎn)或者指向null即可），但是查找一個(gè)節(jié)點(diǎn)或者訪(fǎng)問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間。
上面介紹的是單向鏈表，單向鏈表有個(gè)缺點(diǎn)：只能只能從頭到尾遍歷。如果要?jiǎng)h除倒數(shù)第二個(gè)節(jié)點(diǎn)，只能從頭遍歷。為了更加靈活的操作和更高的效率，就有了雙向鏈表，其結(jié)構(gòu)表示如下圖
如果結(jié)構(gòu)為雙向鏈表，要?jiǎng)h除倒數(shù)第二個(gè)節(jié)點(diǎn)，只用找到尾節(jié)點(diǎn)的前面一個(gè)節(jié)點(diǎn)并刪除即可。Java 中的 LinkedList 就是一個(gè)雙向鏈表的實(shí)現(xiàn)。
數(shù)組和鏈表的關(guān)注點(diǎn)主要聚焦于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和訪(fǎng)問(wèn)方式，而隊(duì)列和棧關(guān)注的則是數(shù)據(jù)的處理順序和邏輯，有自己的特點(diǎn)。
隊(duì)列的特點(diǎn)是先進(jìn)先出（FIFO）：第一個(gè)進(jìn)入隊(duì)列的元素會(huì)第一個(gè)被訪(fǎng)問(wèn)或取出，或者說(shuō)在添加元素時(shí)在隊(duì)尾排隊(duì)依次入隊(duì)，在隊(duì)頭依次出隊(duì)。其表現(xiàn)形式如下圖
棧的特點(diǎn)是先進(jìn)后出（FILO）：第一個(gè)入棧的元素最后一個(gè)被訪(fǎng)問(wèn)或被取出，或者說(shuō)最后一個(gè)入棧的元素會(huì)第一個(gè)被訪(fǎng)問(wèn)或被取出。棧只允許在棧頂進(jìn)行插入和刪除操作。
有一個(gè)很形象的描述就是：可以將棧想象成一個(gè)彈夾，最先裝入的子彈會(huì)被壓入底部，而射出時(shí)則是從頂部彈出。
兩者的底層實(shí)現(xiàn)可以根據(jù)具體需求和場(chǎng)景選擇數(shù)組或鏈表作為底層數(shù)據(jù)結(jié)構(gòu)。例如 Java 中的 ArrayBlockingQueue 是通過(guò)數(shù)組實(shí)現(xiàn)的阻塞隊(duì)列，LinkedBlockingQueue 通過(guò)隊(duì)列實(shí)現(xiàn)的非阻塞隊(duì)列。
樹(shù)是一種非線(xiàn)性結(jié)構(gòu)，是由n個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。樹(shù)也有很多類(lèi)型，比如二叉樹(shù)、平衡樹(shù)、2-3-4樹(shù)、紅黑樹(shù)、B樹(shù)、B+樹(shù)。
二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)，通常用于實(shí)現(xiàn)二叉查找樹(shù)，其特點(diǎn)為：左子節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值，右子節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值。以 Java 為例，一個(gè)二叉查找樹(shù)的結(jié)構(gòu)是這樣表示的：
public class Node { //當(dāng)前節(jié)點(diǎn)的值 private int value; //父節(jié)點(diǎn)、左子節(jié)點(diǎn)、右子節(jié)點(diǎn) private Node parent,left,right;}表現(xiàn)形式如下圖：
其查詢(xún)的時(shí)間復(fù)雜度為O(log n)，相對(duì)于鏈表，查詢(xún)效率大大提升。但是在最壞情況下可能會(huì)退化成O(n)，比如下面這種情況
為了避免這種情況，誕生了AVL樹(shù)。AVL樹(shù)是一種自平衡的二叉查找樹(shù)，在進(jìn)行插入和刪除操作時(shí)，會(huì)通過(guò)左旋或者右旋自動(dòng)調(diào)整自身的結(jié)構(gòu)，確保每個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度差不超過(guò)1，從而保持樹(shù)的平衡，也保障了查詢(xún)的時(shí)間復(fù)雜度為O(log n)。
以下圖為例，當(dāng)插入節(jié)點(diǎn)5時(shí)，節(jié)點(diǎn)7左右子樹(shù)的高度差為2，這時(shí)候節(jié)點(diǎn)7就需要進(jìn)行右旋保持樹(shù)的平衡。
右旋就是：以某個(gè)節(jié)點(diǎn)為旋轉(zhuǎn)點(diǎn)，其左子節(jié)點(diǎn)變?yōu)槠涓腹?jié)點(diǎn)，左子節(jié)點(diǎn)的右子節(jié)點(diǎn)變?yōu)槠渥笞庸?jié)點(diǎn)，右子節(jié)點(diǎn)不變。
同理，左旋就是：以某個(gè)節(jié)點(diǎn)為旋轉(zhuǎn)點(diǎn)，其右子節(jié)點(diǎn)變?yōu)槠涓腹?jié)點(diǎn)，右子節(jié)點(diǎn)的左子節(jié)點(diǎn)變?yōu)槠溆易庸?jié)點(diǎn)，左子節(jié)點(diǎn)不變。
雖然AVL通過(guò)旋轉(zhuǎn)保持樹(shù)的平衡，但是在插入和刪除頻繁的場(chǎng)景中，頻繁的旋轉(zhuǎn)會(huì)導(dǎo)致性能下降，為解決此問(wèn)題紅黑樹(shù)被提出。
紅黑樹(shù)大家應(yīng)該都比較耳熟，面試的時(shí)候應(yīng)該經(jīng)常會(huì)被問(wèn)到，但是理不理解是另一回事。
紅黑樹(shù)也是自平衡的二叉查找樹(shù)，它是通過(guò)節(jié)點(diǎn)顏色來(lái)保證樹(shù)的平衡的。相對(duì)AVL，紅黑樹(shù)較難被理解，第一疑惑就是：“不也是左旋右旋嗎？還這么麻煩，節(jié)點(diǎn)顏色變來(lái)變?nèi)ィ曰笳l(shuí)呢？”。
紅黑樹(shù)后面專(zhuān)門(mén)寫(xiě)一篇文章介紹，這里先給結(jié)論：紅黑樹(shù)的旋轉(zhuǎn)次數(shù)相對(duì)于AVL樹(shù)來(lái)說(shuō)較少，因此在插入、刪除等操作較多的情況下，通常使用紅黑樹(shù)，比如大家都知道的HashMap。下圖顯示的是按順序插入9, 7, 6, 10, 5, 8, 4, 2, 1, 0的AVL樹(shù)和紅黑樹(shù)，可以看到兩者在結(jié)構(gòu)上存在一定的差異。
上面說(shuō)的幾種樹(shù)都是二叉樹(shù)，即每個(gè)節(jié)點(diǎn)只有兩個(gè)分支，并且都都是有序的。因?yàn)橹挥袃蓚€(gè)分支，所以這也是二叉樹(shù)的通病，當(dāng)數(shù)據(jù)越來(lái)越多的時(shí)候，樹(shù)的高度也會(huì)越高，這種情況就不適合數(shù)據(jù)庫(kù)和文件系統(tǒng)這種場(chǎng)景了。
上面提到的幾種樹(shù)結(jié)構(gòu)都是二叉樹(shù)，每個(gè)節(jié)點(diǎn)只有兩個(gè)子節(jié)點(diǎn)，并且都是有序的。當(dāng)數(shù)據(jù)量不斷增加時(shí)，二叉樹(shù)的高度也會(huì)逐漸增加，從而導(dǎo)致查詢(xún)效率降低，并且在有磁盤(pán)I/O操作的場(chǎng)景下，樹(shù)越高越不利于查詢(xún)。
為了解決上述問(wèn)題，采用多叉樹(shù)結(jié)構(gòu)，可以有效地降低樹(shù)的高度，提高查詢(xún)效率。
常見(jiàn)的多叉樹(shù)有2-3-4樹(shù)、B樹(shù)和B+樹(shù)，通常在數(shù)據(jù)庫(kù)和文件系統(tǒng)中會(huì)使用到，其表現(xiàn)形式如下圖。
B+樹(shù)是B樹(shù)的一種擴(kuò)展，它更適合用于磁盤(pán)或其他存儲(chǔ)設(shè)備中。在B+樹(shù)中，非葉子節(jié)點(diǎn)不保存數(shù)據(jù)信息，只保存關(guān)鍵字和子節(jié)點(diǎn)指針，這樣會(huì)存儲(chǔ)更多有效數(shù)據(jù)，比如索引。同時(shí)，每個(gè)葉子節(jié)點(diǎn)都指向相鄰葉子節(jié)點(diǎn)的指針，這樣的話(huà)在數(shù)據(jù)庫(kù)范圍查詢(xún)會(huì)變得非常高效。
堆是一種特殊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，其特點(diǎn)為：每個(gè)節(jié)點(diǎn)都大于或等于（小于或等于）其每個(gè)子節(jié)點(diǎn)。
常見(jiàn)的堆有二叉堆、斐波那契堆等，二叉堆是一種完全二叉樹(shù)，可以分為最大堆和最小堆，最大堆中的每個(gè)節(jié)點(diǎn)都大于或等于其子節(jié)點(diǎn)，最小堆中的每個(gè)節(jié)點(diǎn)都小于或等于其子節(jié)點(diǎn)。下圖左為最大堆的表示，右不符合為一個(gè)完全二叉樹(shù)（依次從左到右插入的節(jié)點(diǎn)為完全二叉樹(shù)）。
堆通常被用作優(yōu)先隊(duì)列，因?yàn)槎训母?jié)點(diǎn)總是最大的或最小的。
很多編程語(yǔ)言都提供了不同類(lèi)型的集合類(lèi)，以 Java 為例，我們常用的集合有List、Set、Queue、Map，其底層的實(shí)現(xiàn)就是數(shù)組、鏈表或樹(shù)這幾種數(shù)據(jù)結(jié)構(gòu)。所以通過(guò)了解數(shù)據(jù)結(jié)構(gòu)，我們可以更好地選擇和使用這些集合，甚至可以自行設(shè)計(jì)更高效的數(shù)據(jù)結(jié)構(gòu)來(lái)解決問(wèn)題。
本文鏈接：http://www.www897cc.com/showinfo-26-51823-0.html14張圖巧妙的理解數(shù)據(jù)結(jié)構(gòu)
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)