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

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

1.數(shù)據(jù)結(jié)構(gòu)的基本功能

(1)如何插入一條新的數(shù)據(jù)項(xiàng)

(2)如何尋找某一特定的數(shù)據(jù)項(xiàng)

(3)如何刪除某一特定的數(shù)據(jù)項(xiàng)

(4)如何迭代的訪問各個(gè)數(shù)據(jù)項(xiàng)，以便進(jìn)行顯示或其他操作

2.常用的數(shù)據(jù)結(jié)構(gòu)

數(shù)組Array、棧Stack、隊(duì)列Queue，鏈表 linked List、樹Tree、哈希表Hash、堆Heap、圖Graph

算法

算法簡單來說就是解決問題的步驟。

在Java中，算法通常都是由類的方法來實(shí)現(xiàn)的。前面的數(shù)據(jù)結(jié)構(gòu)，比如鏈表為啥插入、刪除快，而查找慢，平衡的二叉樹插入、刪除、查找都快，這都是實(shí)現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)的算法所造成的。后面我們講的各種排序?qū)崿F(xiàn)也是算法范疇的重要領(lǐng)域。

1.算法的五個(gè)特征

(1)有窮性：對于任意一組合法輸入值，在執(zhí)行又窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。

(2)確定性：在每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑。

(3)可行性：算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。

(4)有輸入：作為算法加工對象的量值，通常體現(xiàn)在算法當(dāng)中的一組變量。有些輸入量需要在算法執(zhí)行的過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中。

(5)有輸出：它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法功能。

2.算法的設(shè)計(jì)原則

(1)正確性：首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)則說明”方式給出的需求。其次，對算法是否“正確”的理解可以有以下四個(gè)層次：

1)程序語法錯(cuò)誤。

2)程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足需要的結(jié)果。

3)程序?qū)τ诰倪x擇的、典型、苛刻切帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果。

4)程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得到滿足要求的結(jié)果。

PS：通常以第 三 層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。

(2)可讀性：算法為了人的閱讀與交流，其次才是計(jì)算機(jī)執(zhí)行。因此算法應(yīng)該易于人的理解;另一方面，晦澀難懂的程序易于隱藏較多的錯(cuò)誤而難以調(diào)試。

(3)健壯性：當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)淖龀龇磻?yīng)或進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名其妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序執(zhí)行，而是應(yīng)當(dāng)返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。

(4)高效率與低存儲(chǔ)量需求：通常算法效率值得是算法執(zhí)行時(shí)間;存儲(chǔ)量是指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間，兩者都與問題的規(guī)模有關(guān)。

前面三點(diǎn) 正確性，可讀性和健壯性相信都好理解。對于第四點(diǎn)算法的執(zhí)行效率和存儲(chǔ)量，我們知道比較算法的時(shí)候，可能會(huì)說“A算法比B算法快兩倍”之類的話，但實(shí)際上這種說法沒有任何意義。因?yàn)楫?dāng)數(shù)據(jù)項(xiàng)個(gè)數(shù)發(fā)生變化時(shí)，A算法和B算法的效率比例也會(huì)發(fā)生變化，比如數(shù)據(jù)項(xiàng)增加了50%，可能A算法比B算法快三倍，但是如果數(shù)據(jù)項(xiàng)減少了50%，可能A算法和B算法速度一樣。所以描述算法的速度必須要和數(shù)據(jù)項(xiàng)的個(gè)數(shù)聯(lián)系起來。也就是“大O”表示法，它是一種算法復(fù)雜度的相對表示方式，這里我簡單介紹一下，后面會(huì)根據(jù)具體的算法來描述。

相對(relative)：你只能比較相同的事物。你不能把一個(gè)做算數(shù)乘法的算法和排序整數(shù)列表的算法進(jìn)行比較。但是，比較2個(gè)算法所做的算術(shù)操作(一個(gè)做乘法，一個(gè)做加法)將會(huì)告訴你一些有意義的東西;

表示(representation)：大O(用它最簡單的形式)把算法間的比較簡化為了一個(gè)單一變量。這個(gè)變量的選擇基于觀察或假設(shè)。例如，排序算法之間的對比通常是基于比較操作(比較2個(gè)結(jié)點(diǎn)來決定這2個(gè)結(jié)點(diǎn)的相對順序)。這里面就假設(shè)了比較操作的計(jì)算開銷很大。但是，如果比較操作的計(jì)算開銷不大，而交換操作的計(jì)算開銷很大，又會(huì)怎么樣呢?這就改變了先前的比較方式;

復(fù)雜度(complexity)：復(fù)雜度就是相對其他東西的度量結(jié)果。

算法的存儲(chǔ)量，包括：

程序本身所占空間;

輸入數(shù)據(jù)所占空間;

輔助變量所占空間;

數(shù)據(jù)結(jié)構(gòu)必須具有以下基本功能：

(1)如何插入一條新的數(shù)據(jù)項(xiàng)

(2)如何尋找某一特定的數(shù)據(jù)項(xiàng)

(3)如何刪除某一特定的數(shù)據(jù)項(xiàng)

(4)如何迭代的訪問各個(gè)數(shù)據(jù)項(xiàng)，以便進(jìn)行顯示或其他操作

數(shù)組的局限性分析：

(1)插入快，對于無序數(shù)組，上面我們實(shí)現(xiàn)的數(shù)組就是無序的，即元素沒有按照從大到小或者某個(gè)特定的順序排列，只是按照插入的順序排列。無序數(shù)組增加一個(gè)元素很簡單，只需要在數(shù)組末尾添加元素即可，但是有序數(shù)組卻不一定了，它需要在指定的位置插入。

(2)查找慢，當(dāng)然如果根據(jù)下標(biāo)來查找是很快的。但是通常我們都是根據(jù)元素值來查找，給定一個(gè)元素值，對于無序數(shù)組，我們需要從數(shù)組第一個(gè)元素開始遍歷，直到找到那個(gè)元素。有序數(shù)組通過特定的算法查找的速度會(huì)比無需數(shù)組快，后面我們會(huì)講各種排序算法。

(3)刪除慢，根據(jù)元素值刪除，我們要先找到該元素所處的位置，然后將元素后面的值整體向前面移動(dòng)一個(gè)位置。也需要比較多的時(shí)間。

(4)數(shù)組一旦創(chuàng)建后，大小就固定了，不能動(dòng)態(tài)擴(kuò)展數(shù)組的元素個(gè)數(shù)。如果初始化你給一個(gè)很大的數(shù)組大小，那會(huì)白白浪費(fèi)內(nèi)存空間，如果給小了，后面數(shù)據(jù)個(gè)數(shù)增加了又添加不進(jìn)去了。

棧的基本概念

棧(英語：stack)又稱為堆?；蚨询B，棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表。它按照先進(jìn)后出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開始彈出數(shù)據(jù)(最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來)。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。

棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom);棧底固定，而棧頂浮動(dòng);棧中元素個(gè)數(shù)為零時(shí)稱為空棧。插入一般稱為進(jìn)棧(PUSH)，刪除則稱為退棧(POP)。

由于堆疊數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出(LIFO, Last In First Out)的原理運(yùn)作。棧也稱為后進(jìn)先出表。

隊(duì)列：

隊(duì)列(queue)是一種特殊的線性表，特殊之處在于它只允許在表的前端(front)進(jìn)行刪除操作，而在表的后端(rear)進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。

隊(duì)列的數(shù)據(jù)元素又稱為隊(duì)列元素。在隊(duì)列中插入一個(gè)隊(duì)列元素稱為入隊(duì)，從隊(duì)列中刪除一個(gè)隊(duì)列元素稱為出隊(duì)。因?yàn)殛?duì)列只允許在一端插入，在另一端刪除，所以只有最早進(jìn)入隊(duì)列的元素才能最先從隊(duì)列中刪除，故隊(duì)列又稱為先進(jìn)先出(FIFO—first in first out)線性表。

隊(duì)列分為：

1.單向隊(duì)列(Queue)：只能在一端插入數(shù)據(jù)，另一端刪除數(shù)據(jù)。

與棧不同的是，隊(duì)列中的數(shù)據(jù)不總是從數(shù)組的0下標(biāo)開始的，移除一些隊(duì)頭front的數(shù)據(jù)后，隊(duì)頭指針會(huì)指向一個(gè)較高的下標(biāo)位置

隊(duì)列中新增一個(gè)數(shù)據(jù)時(shí)，隊(duì)尾的指針rear 會(huì)向上移動(dòng)，也就是向下標(biāo)大的方向。移除數(shù)據(jù)項(xiàng)時(shí)，隊(duì)頭指針 front 向上移動(dòng)。

在計(jì)算機(jī)中也可以在隊(duì)列中刪除一個(gè)數(shù)之后，隊(duì)列整體向前移動(dòng)，但是這樣做效率很差。我們選擇的做法是移動(dòng)隊(duì)頭和隊(duì)尾的指針。

為了避免隊(duì)列不滿卻不能插入新的數(shù)據(jù)，我們可以讓隊(duì)尾指針繞回到數(shù)組開始的位置，這也稱為“循環(huán)隊(duì)列”。

2.雙向隊(duì)列(Deque)：每一端都可以進(jìn)行插入數(shù)據(jù)和刪除數(shù)據(jù)操作。

雙端隊(duì)列就是一個(gè)兩端都是結(jié)尾或者開頭的隊(duì)列， 隊(duì)列的每一端都可以進(jìn)行插入數(shù)據(jù)項(xiàng)和移除數(shù)據(jù)項(xiàng)，這些方法可以叫做：

insertRight()、insertLeft()、removeLeft()、removeRight()

如果嚴(yán)格禁止調(diào)用insertLeft()和removeLeft()(或禁用右端操作)，那么雙端隊(duì)列的功能就和前面講的棧功能一樣。

如果嚴(yán)格禁止調(diào)用insertLeft()和removeRight(或相反的另一對方法)，那么雙端隊(duì)列的功能就和單向隊(duì)列一樣了。

3.優(yōu)先級隊(duì)列，優(yōu)先級隊(duì)列是比棧和隊(duì)列更專用的數(shù)據(jù)結(jié)構(gòu)，在優(yōu)先級隊(duì)列中，數(shù)據(jù)項(xiàng)按照關(guān)鍵字進(jìn)行排序，關(guān)鍵字最小(或者最大)的數(shù)據(jù)項(xiàng)往往在隊(duì)列的最前面，而數(shù)據(jù)項(xiàng)在插入的時(shí)候都會(huì)插入到合適的位置以確保隊(duì)列的有序。

優(yōu)先級隊(duì)列(priority queue)是比棧和隊(duì)列更專用的數(shù)據(jù)結(jié)構(gòu)，在優(yōu)先級隊(duì)列中，數(shù)據(jù)項(xiàng)按照關(guān)鍵字進(jìn)行排序，關(guān)鍵字最小(或者最大)的數(shù)據(jù)項(xiàng)往往在隊(duì)列的最前面，而數(shù)據(jù)項(xiàng)在插入的時(shí)候都會(huì)插入到合適的位置以確保隊(duì)列的有序。

優(yōu)先級隊(duì)列 是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)，對優(yōu)先級隊(duì)列執(zhí)行的操作有：

(1)查找

(2)插入一個(gè)新元素

(3)刪除

一般情況下，查找操作用來搜索優(yōu)先權(quán)最大的元素，刪除操作用來刪除該元素 。對于優(yōu)先權(quán)相同的元素，可按先進(jìn)先出次序處理或按任意優(yōu)先權(quán)進(jìn)行。

棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)，總結(jié)一下：

1.棧、隊(duì)列(單向隊(duì)列)、優(yōu)先級隊(duì)列通常是用來簡化某些程序操作的數(shù)據(jù)結(jié)構(gòu)，而不是主要作為存儲(chǔ)數(shù)據(jù)的。

2.在這些數(shù)據(jù)結(jié)構(gòu)中，只有一個(gè)數(shù)據(jù)項(xiàng)可以被訪問。

3.棧允許在棧頂壓入(插入)數(shù)據(jù)，在棧頂彈出(移除)數(shù)據(jù)，但是只能訪問最后一個(gè)插入的數(shù)據(jù)項(xiàng)，也就是棧頂元素。

4.隊(duì)列(單向隊(duì)列)只能在隊(duì)尾插入數(shù)據(jù)，對頭刪除數(shù)據(jù)，并且只能訪問對頭的數(shù)據(jù)。而且隊(duì)列還可以實(shí)現(xiàn)循環(huán)隊(duì)列，它基于數(shù)組，數(shù)組下標(biāo)可以從數(shù)組末端繞回到數(shù)組的開始位置。

5.優(yōu)先級隊(duì)列是有序的插入數(shù)據(jù)，并且只能訪問當(dāng)前元素中優(yōu)先級別最大(或最小)的元素。

6.這些數(shù)據(jù)結(jié)構(gòu)都能由數(shù)組實(shí)現(xiàn)，但是可以用別的機(jī)制(鏈表、堆等數(shù)據(jù)結(jié)構(gòu))實(shí)現(xiàn)。

以上就是動(dòng)力節(jié)點(diǎn)小編介紹的"數(shù)據(jù)結(jié)構(gòu)與算法分析"，希望對大家有幫助，如有疑問，請?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為您服務(wù)。