408前置學習C語言基礎也可以看如下專欄：打怪升級之路——C語言之路_ankleless的博客-CSDN博客

目錄

1.? 基本概念

1.1 數據

1.2 數據元素

1.3 數據項

1.4 組合項

1.5 數據對象

1.6 數據類型

2. 數據結構

2.1 邏輯結構

2.2 存儲結構

2.3 數據的運算

---

在學習之前，我們可以思考一個問題，數據結構在學什么呢？

隨著時代的進步，越來越多的問題需要從現實轉為信息化，而數據結構就是為了解決如何把現實問題信息化以及怎么高效存儲和處理信息這兩大問題。

先簡單看如下的思維導圖：

1.? 基本概念

1.1 數據

數據是信息的載體，是描述客觀實物屬性的數、字符以及所有能輸入到計算機中并能被計算機程序識別和處理的符號的集合。數據是計算機程序加工的原料。

個人理解:?在現代計算機體系中，所有數據的底層存儲形式都是二進制

1.2 數據元素

數據元素是數據的基本單位，通常作為一個整體進行考慮和處理。一個數據元素可由若干個數據項組成。

1.3 數據項

數據項是構成數據元素的不可分割的最小單位。

1.4 組合項

組合項是由多個數據項或者其他組合項按照一定邏輯關聯組合而成的數據單元，也稱為“組合字段”或“數據組”。

他們的具體關系示例如下圖：

A、B、C為三個數據元素，名字、學號、年齡、數學成績、語文成績和英語成績為數據項，成績為組合項，他由數學成績、語文成績和英語成績三個數據項共同組成。

1.5 數據對象

數據對象是具有相同性質的數據元素的集合，他是數據的一個子集。例如，成績單（數據對象）含有所有學生成績明細（數據元素）。因此我們可以得到：

數據（全集）包含 數據對象（子集，同類數據元素的集合）；

數據對象 包含 數據元素（個體，可拆分為數據項）。

1.6 數據類型

數據類型是一個值的集合和定義在此集合上的一組操作的總稱：

這里的值代表類型包含的數據內容

1. 原子類型：其值不可再分的數據類型，如整型int、浮點型float等

2. 結構類型：其值可以再分解為若干成分（分量）的數據類型

3. 抽象數據類型：一個數學模型及定義在該數學模型上的一系列操作。他通過對數據的某種抽象，定義了數據的取值范圍和結構形式，以及對數據操作的集合。可以理解為對實際問題數據關系和操作需求的抽象化描述。

原子類型和結構類型側重“是什么”（數據的構成方式），抽象數據類型側重“做什么”（數據的行為能力）

原子類型==“樂高積木塊”，結構類型==“用積木塊組成的組件”，抽象數據類型==“玩具車的功能說明書”

2. 數據結構

數據結構是相互之間存在一種或多種特別關系的數據元素的集合。（可以類比漢字的結構：上下結構，左右結構）在任何問題中，數據元素都不是獨立存在的，他們之間存在某種關系，這種數據元素相互之間的關系稱為結構。

數據結構包括三方面的內容：邏輯結構、存儲結構（物理結構）和數據的運算。

邏輯結構是抽象的關系定義，獨立于具體存儲方式；存儲結構需適配邏輯結構的特性，但最終選擇還受實際應用需求（如操作效率、空間占用）影響?，二者相互制約又共同支撐數據的處理邏輯。

一個算法的設計取決于所選定的邏輯結構，而算法的實現依賴于所采用的存儲結構。?

2.1 邏輯結構

邏輯結構是指數據元素之間的邏輯關系，即從邏輯關系上描述數據。它與數據的存儲無關，是獨立于計算機的。數據的邏輯結構分為線性結構和非線性結構，線性表是典型的線性結構；集合、樹和圖是典型的非線性結構。

?如下圖所示：

?

線性結構：結構中的數據元素之間只存在一對一的關系；

集合：結構中的數據元素除“同屬于一個集合”外，別無其他關系；

樹狀結構：結構中的數據元素之間存在一對多的關系；

網狀結構或圖狀結構：結構中的數據元素之間存在多對多的關系。

2.2 存儲結構

存儲結構是指數據結構在計算機中的表示（又稱映像），也稱物理結構。它包括數據元素的表示和關系的表示（數據元素本身和數據元素之間的關系）。數據的存儲結構是用計算機語言實現的邏輯結構，它依賴于計算機語言。數據的存儲結構主要有順序存儲、鏈式存儲、索引存儲和散列存儲。

1. 順序存儲：把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關系由存儲單元的鄰接關系來體現。其優點是可以實現隨機存取，每個元素占用最少得存儲空間；缺點是只能使用相鄰的一整塊存儲單元，因此可能產生較多的外部碎片；

2.鏈式存儲：不要求邏輯上相鄰的元素在物理位置上也相鄰，借助指示元素存儲地址的指針來表示元素之間的邏輯關系。其優點是不會出現碎片現象，能充分利用所有存儲單元；缺點是每個元素因存儲指針而占用額外的存儲空間，且只能實現順序存取。

3.索引存儲：在存儲元素信息的同時，還建立附加的索引表。索引表中的每項稱為索引項，索引項的一般形式是（關鍵字，地址）。其優點是檢索速度快；缺點是附加的索引表額外占用存儲空間。另外，增加和刪除數據時也要修改索引表，因而會花費較多的時間。

4.散列存儲：根據元素的關鍵字直接計算出該元素的存儲地址，又稱哈希存儲。其優點是檢索、增加和刪除結點的操作都很快；缺點是若散列函數不好，則可能出現元素存儲單元的沖突，而解決沖突會增加時間和空間開銷。

存儲結構中的碎片分為內部碎片和外部碎片，內部碎片是指已經分配給程序的內存空間無法被實際使用的“內部空隙”，外部碎片是指未被分配的空閑內存，由于太零散（不連續），無法滿足程序的“連續大內存需求”

2.3 數據的運算

施加在數據上的運算包括運算的定義和實現。運算的定義是針對邏輯結構，指出運算的功能（要進行什么樣的運算）；運算的實現是針對存儲結構，指出運算的具體操作步驟（怎么進行計算）。

本章都是一些基礎概念的內容，讀者不必鉆牛角尖，有個大概印象通過做題彌補，有表述不當的地方敬請指正。