數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)郁季、組織數(shù)據(jù)的方式美侦，同時(shí)也泛指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合镜会。通常情況下虑稼，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的算法執(zhí)行或者數(shù)據(jù)存儲(chǔ)效率脆丁。數(shù)據(jù)結(jié)構(gòu)往往同高效的算法和索引技術(shù)有很強(qiáng)的關(guān)聯(lián)性和依賴性。
在計(jì)算機(jī)程序設(shè)計(jì)中动雹，我們可以用數(shù)據(jù)結(jié)構(gòu)來(lái)表示特定的對(duì)象數(shù)據(jù)，這些數(shù)據(jù)往往是多樣化的且擁有不同的數(shù)據(jù)結(jié)構(gòu)跟压，諸如數(shù)組胰蝠、接口、類和枚舉等等震蒋。不同的數(shù)據(jù)結(jié)構(gòu)所采用的處理方法不同茸塞，計(jì)算復(fù)雜度也不同，因此查剖，算法往往依賴于某種數(shù)據(jù)結(jié)構(gòu)钾虐，即數(shù)據(jù)結(jié)構(gòu)是算法實(shí)現(xiàn)的基礎(chǔ)。難怪計(jì)算機(jī)科學(xué)家尼古拉斯·沃斯（Nicklaus Wirth）提出了著名公式“ 算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序 ”笋庄，化繁為簡(jiǎn)地展示出了計(jì)算機(jī)程序的本質(zhì)效扫。對(duì)初學(xué)者來(lái)講，僅僅依靠觀察這個(gè)公式直砂，我們也會(huì)發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)和算法一定是如影相隨難分難舍的菌仁。
1、數(shù)據(jù)結(jié)構(gòu)定義
隨著計(jì)算機(jī)科學(xué)與技術(shù)的飛速發(fā)展静暂，計(jì)算機(jī)的應(yīng)用領(lǐng)域已不再局限于科學(xué)計(jì)算济丘，而更多地應(yīng)用于控制、管理洽蛀、生活和娛樂(lè)等非數(shù)值處理領(lǐng)域摹迷。與此相應(yīng)，計(jì)算機(jī)程序處理的數(shù)據(jù)也由純粹的數(shù)值擴(kuò)充到字符郊供、表格峡碉、圖形、圖表颂碘、圖象异赫、聲音椅挣、位置等等，且數(shù)據(jù)量也越來(lái)越大塔拳，數(shù)據(jù)處理頻次也越來(lái)越高鼠证。
由此可見(jiàn)，數(shù)據(jù)結(jié)構(gòu)起源于計(jì)算機(jī)程序設(shè)計(jì)靠抑，并隨之發(fā)展而發(fā)展量九，它們互為伴生物。雖然當(dāng)下各種計(jì)算機(jī)以及程序已是家喻戶曉觸手可用颂碧，但遺憾的是荠列，迄今為止，數(shù)據(jù)結(jié)構(gòu)在業(yè)界還沒(méi)有一個(gè)統(tǒng)一的定義载城，不同的專家肌似，對(duì)數(shù)據(jù)結(jié)構(gòu)有不同的闡述，以下便是幾種典型的定義诉瓦。
美國(guó)佛羅里達(dá)大學(xué)的計(jì)算機(jī)信息科學(xué)與工程杰出教授Sartaj Sahni在其經(jīng)典著作《數(shù)據(jù)結(jié)構(gòu)川队、算法和應(yīng)用》中說(shuō)：“數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象、存在于該對(duì)象的實(shí)例以及組成實(shí)例的數(shù)據(jù)元素之間的各種關(guān)系睬澡，并且這種關(guān)系可以通過(guò)定義相關(guān)的函數(shù)來(lái)給出固额。”
“數(shù)據(jù)結(jié)構(gòu)是抽象數(shù)據(jù)類型ADT的物理實(shí)現(xiàn)煞聪《孵铮”這是美國(guó)弗吉尼亞理工大學(xué)計(jì)算機(jī)科學(xué)系教授Clifford A.Shaffer在其《數(shù)據(jù)結(jié)構(gòu)與算法分析》一書(shū)中的定義。ADT昔脯，英文全稱Abstract Data Type啄糙，意為抽象數(shù)據(jù)類型。此概念在后續(xù)章節(jié)詳述栅干。
Lobert L.Kruse在《數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)》一書(shū)中將一個(gè)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)過(guò)程分成抽象層迈套、數(shù)據(jù)結(jié)構(gòu)層和實(shí)現(xiàn)層。其中碱鳞，抽象層是指抽象數(shù)據(jù)類型層桑李，即ADT層，它討論數(shù)據(jù)的邏輯結(jié)構(gòu)及其運(yùn)算窿给，數(shù)據(jù)結(jié)構(gòu)層討論一個(gè)數(shù)據(jù)結(jié)構(gòu)的表示贵白，實(shí)現(xiàn)層討論數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的存儲(chǔ)細(xì)節(jié)以及運(yùn)算的實(shí)現(xiàn)。
雖然沒(méi)有一個(gè)統(tǒng)一的定義崩泡，未來(lái)可能也不會(huì)有統(tǒng)一的定義禁荒，畢竟仁者見(jiàn)仁智者見(jiàn)智，但是定義謂何不是我們真正關(guān)注的目標(biāo)角撞。此處呛伴，我們只需要領(lǐng)會(huì)貫通其基本含義勃痴，構(gòu)建基本的與此相關(guān)的概念知識(shí)系統(tǒng)，未來(lái)能夠用其靈活解決實(shí)際場(chǎng)景中的問(wèn)題即可热康。因此沛申，我們根據(jù)專家們的不同闡述，重點(diǎn)關(guān)注如下三點(diǎn)：數(shù)據(jù)的邏輯結(jié)構(gòu)姐军，數(shù)據(jù)的物理存儲(chǔ)铁材，數(shù)據(jù)的運(yùn)算。
另外奕锌，數(shù)據(jù)結(jié)構(gòu)不但是一切算法的基礎(chǔ)著觉，而且還是程序設(shè)計(jì)語(yǔ)言的基礎(chǔ)。諸如Java惊暴，C++饼丘，C，C#辽话，Python等等葬毫，其語(yǔ)言特性都是建立在一定的數(shù)據(jù)結(jié)構(gòu)之上。因此屡穗，深入學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，也是掌握語(yǔ)言特性并能夠高效解決實(shí)際程序設(shè)計(jì)問(wèn)題的正確開(kāi)始忽肛。
2村砂、數(shù)據(jù)結(jié)構(gòu)的基本概念
數(shù)據(jù)（Data）
數(shù)據(jù)元素（Data Element）
數(shù)據(jù)結(jié)構(gòu)（Data Structure）
3、數(shù)據(jù)結(jié)構(gòu)的內(nèi)容
數(shù)據(jù)的邏輯結(jié)構(gòu)
數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
數(shù)據(jù)的運(yùn)算
4屹逛、數(shù)據(jù)結(jié)構(gòu)的分類
- 線性結(jié)構(gòu)
數(shù)組础废、隊(duì)列、鏈表罕模、棧
- 非線性結(jié)構(gòu)
樹(shù)评腺、圖、堆淑掌、散列表
5蒿讥、數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式
順序存儲(chǔ)方式
鏈接存儲(chǔ)方式
索引存儲(chǔ)方式
散列存儲(chǔ)方式
6、數(shù)據(jù)類型
每種程序設(shè)計(jì)語(yǔ)言都有自己的數(shù)據(jù)類型抛腕。簡(jiǎn)單來(lái)說(shuō)芋绸，數(shù)據(jù)類型就是值的集合，以及在值上定義的一系列操作的總稱担敌。比如摔敛，Java語(yǔ)言中的字節(jié)類型byte ，其范圍是 -128 ~ 127 全封，長(zhǎng)度為1字節(jié)（8bit）马昙，我們可以對(duì)其進(jìn)行加法桃犬、減法、乘法行楞、除法和取模等操作攒暇。
6.1、基本數(shù)據(jù)類型
其值不可分解敢伸，是程序設(shè)計(jì)語(yǔ)言自身定義的一些數(shù)據(jù)類型扯饶。比如，Java語(yǔ)言中有8種基本類型：byte池颈，short尾序，int，long躯砰，float每币，double ，char琢歇，boolean兰怠。
6.2、聚合數(shù)據(jù)類型
其值可以進(jìn)一步分解為若干分量李茫，一般是由用戶自定義的數(shù)據(jù)類型揭保。比如，Java語(yǔ)言中的數(shù)組魄宏、類和接口等秸侣。
6.3、抽象數(shù)據(jù)類型
抽象數(shù)據(jù)類型（Abstract Data Type宠互，ADT）描述了數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上定義的操作味榛。形式定義如下：
ADT 抽象數(shù)據(jù)類型名
{
數(shù)據(jù)對(duì)象：（數(shù)據(jù)元素集合）
數(shù)據(jù)關(guān)系：（數(shù)據(jù)關(guān)系二元組結(jié)合）
基本操作：（操作函數(shù)的羅列）
} ADT 抽象數(shù)據(jù)類型名;
抽象數(shù)據(jù)類型ADT一般具有兩個(gè)重要特征：
數(shù)據(jù)抽象
關(guān)注實(shí)體的本質(zhì)性特征，應(yīng)具備的功能予跌，以及針對(duì)外部用戶的接口搏色。數(shù)據(jù)封裝
實(shí)體的外部特性和內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)券册。
抽象數(shù)據(jù)類型ADT是描述問(wèn)題的模型频轿，它獨(dú)立于具體實(shí)現(xiàn)，并且把數(shù)據(jù)和操作封裝在一起烁焙，使得用戶程序只能通過(guò)在ADT中定義的某些操作來(lái)訪問(wèn)其中的數(shù)據(jù)略吨，從而實(shí)現(xiàn)信息的隱藏。
在Java語(yǔ)言中考阱，使用接口來(lái)表示抽象數(shù)據(jù)類型ADT翠忠，用接口實(shí)現(xiàn)類來(lái)實(shí)現(xiàn)ADT。比如List接口和其實(shí)現(xiàn)類ArrayList 與 LinkedList 乞榨。
如此設(shè)計(jì)秽之，很好地體現(xiàn)了程序設(shè)計(jì)中的兩層抽象思想当娱。ADT是概念上的抽象，而接口則屬于實(shí)現(xiàn)層上的抽象考榨。
7跨细、常用數(shù)據(jù)結(jié)構(gòu)
7.1、數(shù)組（Array）
數(shù)組是一種特殊的聚合數(shù)據(jù)類型河质，是將具有相同類型的若干變量有序地組織在一起的集合冀惭。數(shù)據(jù)是最基本的數(shù)據(jù)結(jié)構(gòu)，在各種編程語(yǔ)言中都自帶該類型掀鹅。一個(gè)數(shù)組可以被分解為多個(gè)數(shù)組元素散休，按照數(shù)據(jù)元素的類型，數(shù)組又被分為整型數(shù)組乐尊、字符數(shù)組戚丸、字節(jié)數(shù)組、對(duì)象數(shù)組等等扔嵌。數(shù)組還可以有一維數(shù)組限府、二維及多維等表現(xiàn)形式。
7.2痢缎、隊(duì)列（Queue）
隊(duì)列是一種特殊的線性表胁勺。隊(duì)列只允許在表的一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作独旷。一般來(lái)說(shuō)姻几，進(jìn)行插入操作的一端成為隊(duì)尾，進(jìn)行刪除操作的一端成為隊(duì)頭势告。隊(duì)列中沒(méi)有元素時(shí)，被稱為空隊(duì)列抚恒。
7.3咱台、鏈表（Linked List）
鏈接是一種數(shù)據(jù)元素按照鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)在物理上具有非連續(xù)的特點(diǎn)俭驮。鏈表是有一系列數(shù)據(jù)結(jié)點(diǎn)構(gòu)成回溺，每個(gè)數(shù)據(jù)結(jié)點(diǎn)包括數(shù)據(jù)域和引用域兩部分。其中混萝，引用域保存了數(shù)據(jù)結(jié)構(gòu)中下一個(gè)元素存放的地址遗遵。鏈接結(jié)構(gòu)中數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的引用鏈接次序?qū)崿F(xiàn)的。
7.4逸嘀、棧（Stack）
棧是一種特殊的線性表车要，只能在表的一個(gè)固定端進(jìn)行數(shù)據(jù)元素的插入和刪除操作。棧按照后進(jìn)先出的原則來(lái)存儲(chǔ)數(shù)據(jù)崭倘，也就是說(shuō)翼岁，先插入的數(shù)據(jù)被壓入棧底类垫，最后插入的數(shù)據(jù)在棧頂，讀出數(shù)據(jù)時(shí)琅坡，從棧頂開(kāi)式逐個(gè)讀出悉患。棧在匯編語(yǔ)言程序中經(jīng)常用于重要數(shù)據(jù)的現(xiàn)場(chǎng)保護(hù)。棧中沒(méi)有數(shù)據(jù)時(shí)榆俺，成為空棧售躁。
7.5、樹(shù)（Tree）
樹(shù)是典型的非線性結(jié)構(gòu)茴晋，它是包括n個(gè)結(jié)點(diǎn)的有窮集合K陪捷。在樹(shù)結(jié)構(gòu)中，有且只有一個(gè)根節(jié)點(diǎn)晃跺，該結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)揩局。在樹(shù)結(jié)構(gòu)中的其它結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)，而且可以有m個(gè)后繼結(jié)點(diǎn)掀虎，m >= 0凌盯。
7.6、堆（Heap）
堆是一種特殊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)烹玉。一般討論的堆都是二叉堆驰怎。堆的特點(diǎn)是其根節(jié)點(diǎn)的值是所有結(jié)點(diǎn)中最大的或者最小的，并且根節(jié)點(diǎn)的兩個(gè)子樹(shù)也是一個(gè)堆結(jié)構(gòu)二打。
7.7县忌、圖（Graph）
圖是另外一種非線性數(shù)據(jù)結(jié)構(gòu)。在圖結(jié)構(gòu)中继效，數(shù)據(jù)結(jié)點(diǎn)一般稱為頂點(diǎn)症杏，而邊是頂點(diǎn)的有序偶對(duì)。如果兩個(gè)頂點(diǎn)之間存在一條邊瑞信，那么這就表示這兩個(gè)頂點(diǎn)有相鄰關(guān)系厉颤。
7.8、散列表（Hash）
散列表源于散列函數(shù)（Hash Function）凡简，其思想是如果在結(jié)構(gòu)中存在關(guān)鍵字和T相等的記錄逼友，那么必定在F（T）的存儲(chǔ)位置可以找到該記錄，這樣就不用進(jìn)行比較而直接取得所查記錄秤涩。
8帜乞、計(jì)算問(wèn)題
計(jì)算機(jī)能處理的問(wèn)題包括：
數(shù)值計(jì)算問(wèn)題
非數(shù)值計(jì)算問(wèn)題
參考地址：
