數據結構的一些基本概念
數據結構之基本概念
我們不論作為電腦專業的同學還是已經工作的程式猿/媛，都繞不開數據結構這個技術點，今天我們來聊一聊它。
1. 數據結構在學什麼
- 如何用程式程式碼把現實世界的問題資訊化
- 如何用電腦高效地處理這些資訊從而創造價值
人類社會的發展，迄今經歷了和經歷著三個浪潮：第一次浪潮為農業階段，從約1萬年前開始；第二次浪潮為工業階段，從17世紀末開始；第三次浪潮為正在到來的資訊化階段。 —-《第三次浪潮（1980版）》，阿爾文·托夫勒
資訊化的例子：
以上種種，已經包含了我們日常生活的方方面面。
唯一可以確定的是，明天會使我們所有人大吃一驚。
——阿爾文·托夫勒
2. 數據結構的一些基本概念
1）基本概念
-
數據：
數據是資訊的載體，是描述客觀事物屬性的數、字元及所有能輸入到電腦中並被電腦程式識別和處理的符號的集合。數據是電腦程式加工的原料。
電腦可以識別的是 0 和 1 的二進位數。
-
數據元素、數據項：
數據元素是數據的基本單位，通常作為一個整體進行考慮和處理。
一個數據元素可由若干數據項組成，數據項是構成數據元素的不可分割的最小單位。
-
結構
各個元素之間的關係。
-
數據結構、數據對象
數據結構：是相互之間存在一種或多種特定關係的數據元素的集合。
數據對象：是具有相同性質的數據元素的集合，是數據的一個子集。
向上面的海底撈的例子：
數據結構：某個特定門店的排隊顧客資訊和它們之間的關係
數據對象：全國所有門店的排隊顧客資訊
下面以一張圖來顯示這些概念之間的關係：
-
數據類型
數據類型是一個值的集合和定義在此集合上的一組操作的總稱。
- 原子類型：其值不可再分的數據類型。
- 結構類型：其值可以再分解為若干成分（分量）的數據類型。
-
抽象數據類型(ADT)
抽象數據類型是抽象數據組織及與之相關的操作。
2）數據結構的三要素
-
邏輯結構
數據元素之間的邏輯關係。
-
集合
各個元素同屬一個集合，別無其他關係。
-
線性結構
數據元素之間是一對一的關係，除了第一個元素，所有元素都有唯一前驅；除了最後一個元素，所有元素都有唯一後繼。
-
樹形結構
數據元素之間是一對多的關係。
-
圖結構
數據元素之間是多對多的關係。
-
物理結構（存儲結構）
電腦表示數據元素之間邏輯關係的結構。
-
順序存儲
把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關係由存儲單元的鄰接關係來體現。
-
鏈式存儲
邏輯上相鄰的元素在物理位置上可以不相鄰，藉助指示元素存儲地址的指針來表示元素之間的邏輯關係。
-
索引存儲
在存儲元素資訊的同時，還建立附加的索引表。索引表中的每項稱為索引項，索引項的一般形式是（關鍵字，地址）。
-
散列存儲
根據元素的關鍵字直接計算出該元素的存儲地址，又稱為哈希（Hash）存儲。
後面將介紹計算哈希值的方法
再來理解一波，花開😎
1）若採用順序存儲，則各個數據元素在物理上必須是連續的；若採用非順序存儲，則各個數據元素在物理上可以是離散的。
2）數據的存儲結構會影響存儲空間分配的方便程度。（比如，有人想插隊）
3）數據的存儲結構會影響對數據運算的速度。（比如，想找到某個人）
-
數據的運算
施加在數據上的運算包括運算的定義和實現。運算的定義是針對邏輯結構的，指出運算的功能；運算的實現是針對存儲結構的，指出運算的具體操作步驟。
後面會學習具體的數據結構類型，就會學習定義和實現。
如果大家想了解更多，可以關注一下微信公眾號：程式設計師應如是，獲取更多優質內容。
