# 數(shù)據(jù)結(jié)構(gòu)是什么谋国？
對(duì)于數(shù)據(jù)結(jié)構(gòu)這個(gè)概念哨啃，至今尚未有一個(gè)被一致公認(rèn)的定義碘勉，不同的人在使用這個(gè)詞時(shí)所表達(dá)的意思有所不同巷挥。
“數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象，以及存在于該對(duì)象的實(shí)例和組成實(shí)例的數(shù)據(jù)元素之間的各種聯(lián)系验靡。這些聯(lián)系可以通過定義相關(guān)的函數(shù)來(lái)給出倍宾。”
--- Sartaj Sahni胜嗓，《數(shù)據(jù)結(jié)構(gòu)高职、算法與應(yīng)用》“數(shù)據(jù)結(jié)構(gòu)是ADT（抽象數(shù)據(jù)類型 Abstract Data Type）的物理實(shí)現(xiàn)〈侵荩”
--- Clifford A.Shaffer怔锌，《數(shù)據(jù)結(jié)構(gòu)與算法分析》“數(shù)據(jù)結(jié)構(gòu)（data structure）是計(jì)算機(jī)中存儲(chǔ)、組織數(shù)據(jù)的方式变过。通常情況下埃元，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)最優(yōu)效率的算法∶恼”
--- 中文維基百科
到底什么是數(shù)據(jù)結(jié)構(gòu)岛杀？
- 數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的組織方式，包括：
邏輯結(jié)構(gòu)
物理存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在機(jī)器的內(nèi)存里面怎么放 - 數(shù)據(jù)對(duì)象必定與一系列加在其上的操作相關(guān)聯(lián)
- 完成這些操作所用的方法就是算法
所有的數(shù)據(jù)都是由數(shù)據(jù)元素構(gòu)成崭孤，數(shù)據(jù)元素是數(shù)據(jù)的基本單位类嗤。數(shù)據(jù)元素也稱元素、結(jié)點(diǎn)辨宠、頂點(diǎn)遗锣、記錄。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)（也可稱為字段嗤形、域喉镰、屬性）組成趟据，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位我擂。
數(shù)據(jù)結(jié)構(gòu)存在的目的：
讓我們操作里面的數(shù)據(jù)嘉涌，快速。
- 方便我們?cè)黾?/li>
- 方便我們快速查找到(查是刪改的前提)
- 節(jié)省空間(存儲(chǔ))
當(dāng)然，操作的時(shí)候，不光與數(shù)據(jù)結(jié)構(gòu)有關(guān)，與算法的精妙程度也有關(guān)系斯撮。
今天主要總結(jié)一下邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。
## 抽象數(shù)據(jù)類型（Abstract Data Type）
描述數(shù)據(jù)結(jié)構(gòu)有一個(gè)很好的方法 - 抽象數(shù)據(jù)類型
兩個(gè)關(guān)鍵詞：抽象扶叉、數(shù)據(jù)類型
-
數(shù)據(jù)類型(包含兩部分內(nèi)容)
- 數(shù)據(jù)對(duì)象集
- 數(shù)據(jù)集合相關(guān)聯(lián)的操作集
C語(yǔ)言中是單獨(dú)處理的勿锅，在高級(jí)語(yǔ)言中，通常會(huì)用
類將數(shù)據(jù)集跟和它相關(guān)的操作集封裝在一起 -
抽象：描述數(shù)據(jù)類型的方法不依賴于具體實(shí)現(xiàn)
- 與存放數(shù)據(jù)的機(jī)器無(wú)關(guān)
- 與數(shù)據(jù)存儲(chǔ)的物理結(jié)構(gòu)無(wú)關(guān)
- 與實(shí)現(xiàn)操作的算法和編程語(yǔ)言均無(wú)關(guān)
只描述數(shù)據(jù)對(duì)象集和相關(guān)操作集“是什么”枣氧，并不涉及“如何做到”的問題
# 什么是邏輯結(jié)構(gòu)溢十？
簡(jiǎn)單說，邏輯結(jié)構(gòu)就是數(shù)據(jù)之間的關(guān)系达吞。
按數(shù)據(jù)之間的關(guān)系來(lái)說张弛，邏輯結(jié)構(gòu)大概可以分為兩種:
- 線性結(jié)構(gòu)
- 線性表：順序表、鏈表（線性鏈表酪劫、循環(huán)鏈表吞鸭、雙向鏈表）
- 棧（順序棧、鏈棧）
- 隊(duì)列（順序隊(duì)列覆糟、鏈隊(duì)列(循環(huán)鏈等)）
...
- 非線性結(jié)構(gòu)
- 集合
- 樹(二叉樹)
- 圖(網(wǎng))
...
## 線性結(jié)構(gòu)
有且只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)刻剥，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。它們共同的特點(diǎn)就是數(shù)據(jù)之間的線性關(guān)系滩字，除了頭結(jié)點(diǎn)和尾結(jié)點(diǎn)之外造虏，每個(gè)結(jié)點(diǎn)都有唯一的前驅(qū)和唯一的后繼，也就是所謂的一對(duì)一的關(guān)系麦箍。
不同的線性表之間的區(qū)別：
線性表在元素的關(guān)系上是一樣的漓藕，都是"線性"關(guān)系，不同的線性表區(qū)別主要體現(xiàn)在不同的特性上挟裂。
比如：隊(duì)列的先進(jìn)先出享钞、棧的后進(jìn)先出等。
以鏈棧话瞧，鏈隊(duì)列為例：
邏輯結(jié)構(gòu)同為線性表嫩与，存儲(chǔ)結(jié)構(gòu)也相同寝姿，都是鏈?zhǔn)酱鎯?chǔ)的交排，每個(gè)結(jié)點(diǎn)都是由數(shù)據(jù)域和指針域組成，每個(gè)結(jié)點(diǎn)也都有唯一的前驅(qū)和唯一的后繼（除頭尾結(jié)點(diǎn)外）饵筑。
那么它們看起來(lái)就很相似埃篓，區(qū)別呢？
區(qū)別就在于給他們定義的特殊操作根资，它們都有"出"和"入"兩種操作架专，一個(gè)是"先進(jìn)先出"同窘，而一個(gè)是"后進(jìn)先出"。
## 非線性結(jié)構(gòu)
對(duì)應(yīng)于線性結(jié)構(gòu)部脚，非線性結(jié)構(gòu)也就是每個(gè)結(jié)點(diǎn)可以有不止一個(gè)直接前驅(qū)和直接后繼想邦。
# 什么是存儲(chǔ)結(jié)構(gòu)(/物理結(jié)構(gòu))？
邏輯結(jié)構(gòu)指的是數(shù)據(jù)間的關(guān)系委刘，而存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的存儲(chǔ)映像丧没。
常見的存儲(chǔ)結(jié)構(gòu):
- 順序存儲(chǔ) -- (應(yīng)用：數(shù)組)
- 鏈?zhǔn)酱鎯?chǔ) -- (應(yīng)用：指針)
- 索引存儲(chǔ)
- 散列存儲(chǔ)（哈希表）
## 順序存儲(chǔ)
把邏輯上相鄰的節(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元中，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)锡移。由此得到的存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)結(jié)構(gòu)呕童。
通常順序存儲(chǔ)結(jié)構(gòu)是借助于數(shù)組來(lái)描述的。
優(yōu)點(diǎn)：節(jié)省空間淆珊，可以實(shí)現(xiàn)隨機(jī)存榷崴恰；
缺點(diǎn)：插入施符、刪除時(shí)需要移動(dòng)元素往声，效率低。
## 鏈?zhǔn)酱鎯?chǔ)
在計(jì)算機(jī)中用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的,也可以是不連續(xù)的)戳吝。
特點(diǎn)是
元素邏輯上相鄰烁挟，但在物理上可以不相鄰，所以每個(gè)數(shù)據(jù)元素包括了一個(gè)數(shù)據(jù)域和一個(gè)指針域骨坑，數(shù)據(jù)域用來(lái)存放數(shù)據(jù)撼嗓，而指針域用來(lái)指向其后繼結(jié)點(diǎn)的位置。
優(yōu)點(diǎn)：
- 插入欢唾、刪除靈活 (不必移動(dòng)節(jié)點(diǎn)且警，只要改變節(jié)點(diǎn)中的指針)
缺點(diǎn)：
- 不能隨機(jī)存取，查找速度慢礁遣。
- 比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小 (每個(gè)節(jié)點(diǎn)都由數(shù)據(jù)域和指針域組成斑芜，所以相同空間內(nèi)假設(shè)全存滿的話順序比鏈?zhǔn)酱鎯?chǔ)更多)。
## 索引存儲(chǔ)
除建立存儲(chǔ)結(jié)點(diǎn)信息外祟霍，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址杏头。索引表由若干索引項(xiàng)組成。
特點(diǎn)：索引存儲(chǔ)結(jié)構(gòu)是用結(jié)點(diǎn)的索引號(hào)來(lái)確定結(jié)點(diǎn)存儲(chǔ)地址沸呐，其優(yōu)點(diǎn)是檢索速度快醇王，缺點(diǎn)是增加了附加的索引表,會(huì)占用較多的存儲(chǔ)空間。
## 散列存儲(chǔ)
散列存儲(chǔ)崭添，又稱hash存儲(chǔ)寓娩，是一種力圖將數(shù)據(jù)元素的存儲(chǔ)位置與關(guān)鍵碼之間建立確定對(duì)應(yīng)關(guān)系的查找技術(shù)。
散列法存儲(chǔ)的基本思想是：由節(jié)點(diǎn)的關(guān)鍵碼值決定節(jié)點(diǎn)的存儲(chǔ)地址。散列技術(shù)除了可以用于查找外棘伴，還可以用于存儲(chǔ)寞埠。
特點(diǎn)：散列是數(shù)組存儲(chǔ)方式的一種發(fā)展，相比數(shù)組焊夸，散列的數(shù)據(jù)訪問速度要高于數(shù)組仁连，因?yàn)榭梢砸罁?jù)存儲(chǔ)數(shù)據(jù)的部分內(nèi)容找到數(shù)據(jù)在數(shù)組中的存儲(chǔ)位置，進(jìn)而能夠快速實(shí)現(xiàn)數(shù)據(jù)的訪問阱穗。
理想的散列訪問速度是非常迅速的怖糊，而不像在數(shù)組中的遍歷過程，采用存儲(chǔ)數(shù)組中內(nèi)容的部分元素作為映射函數(shù)的輸入颇象，映射函數(shù)的輸出就是存儲(chǔ)數(shù)據(jù)的位置伍伤，這樣的訪問速度就省去了遍歷數(shù)組的實(shí)現(xiàn)，因此時(shí)間復(fù)雜度可以認(rèn)為為O(1)遣钳，而數(shù)組遍歷的時(shí)間復(fù)雜度為O(n)扰魂。
# 邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的區(qū)別
- 文件的邏輯結(jié)構(gòu)：是用戶可見結(jié)構(gòu)，即從用戶觀點(diǎn)出發(fā)觀察到的文件組織蕴茴。
用途：為了描述數(shù)據(jù)之間的聯(lián)系 -
文件的物理結(jié)構(gòu)：文件的存儲(chǔ)結(jié)構(gòu)劝评，即文件在外存的存儲(chǔ)組織形式。涉及存儲(chǔ)介質(zhì)倦淀、外存分配方式蒋畜。
用途：關(guān)注于如何能使數(shù)據(jù)的增刪改查更簡(jiǎn)單快捷。
文件組織結(jié)構(gòu).png
通俗點(diǎn)說：用戶要看到的數(shù)據(jù)就是這個(gè)結(jié)構(gòu)(字符流式撞叽、記錄式等)的姻成， 而存儲(chǔ)介質(zhì)怎么存(連續(xù)、鏈?zhǔn)健?索引)愿棋，是連續(xù)存科展，還是拆開了(RAID)，用戶是不管的糠雨。
