數據的邏輯結構：

數據的邏輯結構指數據元素之間的邏輯關系（和實現無關）。

分類1：線性結構和非線性結構

線性結構：

有且隻有一個開始結點和一個終端結點，并且所有結點都最多隻有一個直接前驅和一個直接後繼。

線性表就是一個典型的線性結構，它有四個基本特征：

• ​集合中必存在唯一的一個"第一個元素"；
• 集合中必存在唯一的一個"最後的元素"；
• 除最後元素之外，其它數據元素均有唯一的"直接後繼"；
• 除第一元素之外，其它數據元素均有唯一的"直接前驅"。

生活案例：冰糖葫蘆、 排隊上地鐵

相對應于線性結構，非線性結構的邏輯特征是一個節點元素可能對應多個直接前驅和多個直接後繼。

常見的非線性結構有：樹(二叉樹等)，圖(網等)。

樹：

生活案例：單位組織架構、族譜

技術案例：文件系統。

圖：

生活案例：交通線路圖，地鐵圖

分類2：集合結構 線性結構 樹狀結構 網絡結構

邏輯結構有四種基本類型：集合結構、線性結構、樹狀結構和網絡結構。

表和樹是最常用的兩種高效數據結構，許多高效的算法能夠用這兩種數據結構來設計實現。

集合結構：

就是數學中所學習的集合。集合中的元素有三個特征：

• 确定性（集合中的元素必須是确定的）
• 唯一性（集合中的元素互不相同。例如：集合A={1，a}，則a不能等于1）
• 無序性（集合中的元素沒有先後之分），如集合{3,4,5}和{3,5,4}算作同一個集合

該結構的數據元素間的關系是“屬于同一個集合”，别無其它關系。

因為集合中元素關系很弱，數據結構中不對該結構進行研究

線性結構：

數據結構中線性結構指的是數據元素之間存在着“一對一”的線性關系的數據結構。

樹狀結構：除了一個數據元素（元素 01）以外每個數據元素有且僅有一個直接前驅元素，但是可以有多個直接後續元素。

特點是數據元素之間是 1 對 多的聯系

網絡結構：

每個數據元素可以有多個直接前驅元素，也可以有多個直接後續元素。特點是數據元素之間是多對 多 的聯系

問題：1個班的學生是什麼邏輯結構呢？

數據的存儲結構

數據的存儲結構主要包括數據元素本身的存儲以及數據元素之間關系表示，是數據的邏輯結構在計算機中的表示。

常見的存儲結構有順序存儲，鍊式存儲，索引存儲，以及散列存儲。

順序存儲結構：

把邏輯上相鄰的節點存儲在物理位置上相鄰的存儲單元中，節點之間的邏輯關系由存儲單元的鄰接關系來體現。

由此得到的存儲結構為順序存儲結構，通常順序存儲結構是借助于計算機程序設計語言（例如C/C ）的數組來描述的。

（數據元素的存儲對應于一塊連續的存儲空間，數據元素之間的前驅和後續關系通過數據元素，在存儲器中的相對位置來反映）

優點：

• 節省存儲空間，因為分配給數據的存儲單元全用存放結點的數據（不考慮c/c 語言中數組需指定大小的情況），結點之間的邏輯關系沒有占用額外的存儲空間。
• 采用這種方法時，可實現對結點的随機存取，即每一個結點對應一個序号，由該序号可以直接計算出來結點的存儲地址。

缺點：

• 插入和删除操作需要移動元素，效率較低。
• 必須提前分配固定數量的空間，如果存儲元素少，可能導緻空閑浪費。

鍊式存儲結構：

數據元素的存儲對應的是不連續的存儲空間，每個存儲節點對應一個需要存儲的數據元素。

每個結點是由數據域和指針域組成。元素之間的邏輯關系通過存儲節點之間的鍊接關系反映出來。

邏輯上相鄰的節點物理上不必相鄰。

缺點：

• 比順序存儲結構的存儲密度小 (每個節點都由數據域和指針域組成，所以相同空間内假設全存滿的話順序比鍊式存儲更多)。
• 查找結點時鍊式存儲要比順序存儲慢。

優點：

• 插入、删除靈活 (不必移動節點，隻要改變節點中的指針)。
• 有元素才會分配結點空間，不會有閑置的結點。

索引存儲結構：

除建立存儲結點信息外，還建立附加的索引表來标識結點的地址。

比如圖書、字典的目錄

散列存儲結構：

根據結點的關鍵字直接計算出該結點的存儲地址 HashSet HashMap

一種神奇的結構，添加、查詢速度快。

舉例：

線性表的邏輯結構如圖所示：

線性表邏輯結構對應的順序存儲結構為順序表，對應的鍊式存儲結構為鍊表。

順序表

鍊表

• 同一邏輯結構可以對應多種存儲結構。
• 同樣的運算，在不同的存儲結構中，其實現過程是不同的