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

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

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

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

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

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

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

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

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

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

算法

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

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

1.算法的五個特征

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

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

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

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

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

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

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

1)程序語法錯誤。

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

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

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

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

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

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

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

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

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

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

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

算法的存儲量，包括：

程序本身所占空間;

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

輔助變量所占空間;

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

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

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

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

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

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

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

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

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

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

棧的基本概念

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

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

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

隊列：

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

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

隊列分為：

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

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

隊列中新增一個數(shù)據(jù)時，隊尾的指針rear 會向上移動，也就是向下標(biāo)大的方向。移除數(shù)據(jù)項時，隊頭指針 front 向上移動。

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

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

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

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

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

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

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

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

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

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

(1)查找

(2)插入一個新元素

(3)刪除

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

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

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

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

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

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

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

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

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