一、基本概念和術語

1.數據

數據是描述客觀事物的符號，是計算機可以操作的對象，是能被計算機識別，并輸入到計算機處理的符號集合。

（數據不僅僅包括整型、實型等數值型，還有字符、聲音、圖像、視頻等非數值類型）

2.數據元素

數據元素是組成數據的、有一定意義的基本單位，在計算機中通常作為整體處理，也稱為記錄（元組、結點、頂點）。

3.數據項（屬性、字段）

一個數據元素可以由若干個數據項組成。

數據項是數據不可分割的最小單位。

4.數據對象

數據對象是性質相同的數據元素的集合，是數據的子集。

5.數據結構

在現實世界中，不同數據元素之間不是獨立的，而是存在特定的關系，這些關系稱為結構。

數據結構是相互之間存在一種或多種特定關系的數據元素的集合。

數據結構包括三方面的內容：邏輯結構、存儲結構和數據的運算。數據的邏輯結構和存儲結構是密不可分的兩個方面，一個算法的設計取決于所選定的邏輯結構，而算法的實現依賴于所采用的存儲結構。

二、邏輯結構和物理結構（存儲結構）

1.邏輯結構

1）定義

邏輯結構是指數據對象中數據元素之間相互關系（邏輯關系），即從邏輯關系上描述數據。它與數據的存儲無關，是獨立于計算機存儲器的。

2）分類（線性結構和非線性結構）

根據數據元素之間關系的不同特征，通常有下列4類基本結構，復雜程度依次遞進。

①集合：結構中的數據元素之間除了同屬于一個集合外，沒有其他的關系。

②線性結構：線性結構中的數據元素之間是一對一的關系。

③樹形結構：樹形結構中的數據元素之間是一對多的關系。

④圖狀結構或網狀結構：結構中的元素之間是多對多的關系。

2.物理結構（存儲結構）

1）定義

數據的物理結構是指數據的邏輯結構在計算機中的存儲方式。又稱存儲結構。

它研究的是數據結構在計算機中的實現方法，包括數據元素的表示和元素之間的關系。

數據元素的存儲結構形式主要有兩種：順序存儲和鏈式存儲

2）順序存儲和鏈式存儲

①順序存儲結構

是利用數據元素在存儲器中的相對位置來表示數據元素之間的邏輯順序。

順序存儲結構是把數據元素放在地址連續的存儲單元中，程序設計中使用數組類型來實現。（邏輯相鄰物理相鄰）

②鏈式存儲結構

利用結點中指針來表示數據元素之間的關系。

把數據元素存儲在任意的存儲單元里，這組存儲單元可以是連續的，也可以是連續的，程序設計中使用指針類型來實現。（邏輯相鄰物理不一定相鄰）

3）其他存儲方式

索引存儲：類似于目錄，以后可以聯系操作系統的文件系統章節來理解。

散列存儲：通過關鍵字直接計算出元素的物理地址。

三、抽象數據類型

定義

①數據類型：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。

例如：C語言中數據類型分為基本類型和構造類型

基本類型：整型、浮點型、字符型等

構造類型：數組、結構、聯合、指針、枚舉型、自定義類型等

②抽象數據類型（abstract data type，ADT）：是指一個數學模型及定義在該模型上的一組操作。

延伸閱讀：

四、線性表的鏈式表示和實現

用一組任意的存儲單元（可能不連續）存儲線性表的數據元素。

在鏈式存儲結構中，每個存儲結點不僅包含數據元素本身的信息，還必須包含每個元素之間邏輯關系的信息，即包含直接后繼結點的地址信息（指針域）。

邏輯順序與物理順序有可能不一致；屬順序存取的存儲結構，即存取每個元素必須從名列前茅個元素開始遍歷，直到找到需要訪問的元素，所以所花時間不一定相等。