數(shù)據(jù)結(jié)構(gòu)之基本概念
我們不論作為計算機專業(yè)的同學(xué)還是已經(jīng)工作的程序猿/媛嘲恍，都繞不開數(shù)據(jù)結(jié)構(gòu)這個技術(shù)點，今天我們來聊一聊它市埋。
1. 數(shù)據(jù)結(jié)構(gòu)在學(xué)什么
如何用程序代碼把現(xiàn)實世界的問題信息化
如何用計算機高效地處理這些信息從而創(chuàng)造價值
人類社會的發(fā)展王带，迄今經(jīng)歷了和經(jīng)歷著三個浪潮：第一次浪潮為農(nóng)業(yè)階段享言，從約1萬年前開始；第二次浪潮為工業(yè)階段纫事，從17世紀(jì)末開始勘畔；第三次浪潮為正在到來的信息化階段。 ----《第三次浪潮（1980版）》丽惶，阿爾文·托夫勒
信息化的例子：
以上種種炫七，已經(jīng)包含了我們?nèi)粘Ｉ畹姆椒矫婷妗?/p>
唯一可以確定的是，明天會使我們所有人大吃一驚钾唬。
——阿爾文·托夫勒
2. 數(shù)據(jù)結(jié)構(gòu)的一些基本概念
1）基本概念
-
數(shù)據(jù)：
數(shù)據(jù)是信息的載體万哪，是描述客觀事物屬性的數(shù)、字符及所有能輸入到計算機中并被計算機程序識別和處理的符號的集合抡秆。數(shù)據(jù)是計算機程序加工的原料奕巍。
image-20210121191732522
計算機可以識別的是 0 和 1 的二進制數(shù)。
-
數(shù)據(jù)元素琅轧、數(shù)據(jù)項：
數(shù)據(jù)元素是數(shù)據(jù)的基本單位伍绳，通常作為一個整體進行考慮和處理。
一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成乍桂，數(shù)據(jù)項是構(gòu)成數(shù)據(jù)元素的不可分割的最小單位冲杀。
-
結(jié)構(gòu)
各個元素之間的關(guān)系。
-
數(shù)據(jù)結(jié)構(gòu)睹酌、數(shù)據(jù)對象
數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合权谁。
數(shù)據(jù)對象：是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集憋沿。
向上面的海底撈的例子：
數(shù)據(jù)結(jié)構(gòu)：某個特定門店的排隊顧客信息和它們之間的關(guān)系
image-20210121193458588數(shù)據(jù)對象：全國所有門店的排隊顧客信息
image-20210121193541772
下面以一張圖來顯示這些概念之間的關(guān)系：
-
數(shù)據(jù)類型
數(shù)據(jù)類型是一個值的集合和定義在此集合上的一組操作的總稱旺芽。
- 原子類型：其值不可再分的數(shù)據(jù)類型。
image-20210121194401094- 結(jié)構(gòu)類型：其值可以再分解為若干成分（分量）的數(shù)據(jù)類型辐啄。
-
抽象數(shù)據(jù)類型(ADT)
抽象數(shù)據(jù)類型是抽象數(shù)據(jù)組織及與之相關(guān)的操作采章。
2）數(shù)據(jù)結(jié)構(gòu)的三要素
-
邏輯結(jié)構(gòu)
數(shù)據(jù)元素之間的邏輯關(guān)系。
image-20210121195058057
-
集合
各個元素同屬一個集合壶辜，別無其他關(guān)系悯舟。
image-20210121195226858 -
線性結(jié)構(gòu)
數(shù)據(jù)元素之間是一對一的關(guān)系，除了第一個元素砸民，所有元素都有唯一前驅(qū)抵怎；除了最后一個元素奋救，所有元素都有唯一后繼。
-
樹形結(jié)構(gòu)
數(shù)據(jù)元素之間是一對多的關(guān)系反惕。
image-20210121195710117
-
圖結(jié)構(gòu)
數(shù)據(jù)元素之間是多對多的關(guān)系尝艘。
image-20210121195859714
-
物理結(jié)構(gòu)（存儲結(jié)構(gòu)）
計算機表示數(shù)據(jù)元素之間邏輯關(guān)系的結(jié)構(gòu)。
image-20210121202305032
-
順序存儲
把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中姿染，元素之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)背亥。
image-20210121200639304
-
鏈?zhǔn)酱鎯?/p>
邏輯上相鄰的元素在物理位置上可以不相鄰，借助指示元素存儲地址的指針來表示元素之間的邏輯關(guān)系盔粹。
image-20210121201123292
-
索引存儲
在存儲元素信息的同時隘梨，還建立附加的索引表。索引表中的每項稱為索引項舷嗡，索引項的一般形式是（關(guān)鍵字轴猎，地址）。
image-20210121201651198
-
散列存儲
根據(jù)元素的關(guān)鍵字直接計算出該元素的存儲地址进萄，又稱為哈希（Hash）存儲捻脖。
后面將介紹計算哈希值的方法
再來理解一波，花開??
1）若采用順序存儲中鼠，則各個數(shù)據(jù)元素在物理上必須是連續(xù)的可婶；若采用非順序存儲，則各個數(shù)據(jù)元素在物理上可以是離散的援雇。
2）數(shù)據(jù)的存儲結(jié)構(gòu)會影響存儲空間分配的方便程度矛渴。（比如，有人想插隊）
3）數(shù)據(jù)的存儲結(jié)構(gòu)會影響對數(shù)據(jù)運算的速度惫搏。（比如具温，想找到某個人）
-
數(shù)據(jù)的運算
施加在數(shù)據(jù)上的運算包括運算的定義和實現(xiàn)。運算的定義是針對邏輯結(jié)構(gòu)的筐赔，指出運算的功能铣猩；運算的實現(xiàn)是針對存儲結(jié)構(gòu)的，指出運算的具體操作步驟茴丰。
后面會學(xué)習(xí)具體的數(shù)據(jù)結(jié)構(gòu)類型达皿，就會學(xué)習(xí)定義和實現(xiàn)。
大家如果想了解更多內(nèi)容贿肩，可以關(guān)注一下公眾號：程序員應(yīng)如是峦椰，里面有更多的技術(shù)分享
