數據結構
一. 數據結構分類
1.線性結構
非空集、僅有一個開始個終端結點、只有一個直接前趨和後趨結點
典型：
棧、隊列、串、一維數組
2.非線性結構
非空集、結點可能有多個直接前趨和後趨結點
典型：
多維數組、廣義表、樹結構和圖結構
二. 數據結構的幾種存儲方式
1.順序存儲方式（Sequential Storage Structure）
1.在一塊連續的存儲區域一個接著一個地存放數據。
2.把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元，結點間邏輯關係由鄰接關係來體現
主要用於線性結構的數據存放（如：順序表等）
2.鏈接存儲方式(Linked Storage Structure)
不要求邏輯上相鄰的結點在物理位置相鄰，結點間邏輯關係由附加的引用字段表示。
一般在原數據中增加引用類型來表示結點之間的位置關係
3.索引存儲方式
1.採用附加的索引表的方式存儲結點信息。索引表由若干索引項組成。
2.索引項的一般形式為：（關鍵字、地址）。其中關鍵字是唯一標識一個結點
索引存儲方式細分兩類：
稠密索引：每個節點在索引表中都有一個索引項，索引項地址指示結點的存儲位置
稀疏索引：一組結點對應一個索引項，索引項的地址指示一組結點的起始存儲位置
4.散列存儲方式
根據節點的關鍵字直接計算出該結點的存儲地址的一種存儲方式。
三. 常用數據結構
1.數組（Array）
聚合數據類型，將相同類型變量有序地組織在一起的集合。
2.棧（Stack）
特殊線性表，只能在一個表的一個固定端進行數據結點的插入刪除操作
棧按照後進先出的原則存儲數據
3.隊列（Queue）
特殊線性表，隊列只允許在表的一端進行插入操作，另一端刪除操作
一般插入操作一端稱為隊尾，刪除一端隊頭
隊列是先進先出
4.堆（Heap）
特殊的樹型結構，特點：根結點的值是所有結點中最小的或者最大的，並且根結點的兩個子樹也是一個堆結構
5.鏈表（Linked List）
鏈式存儲，由一系列結點構成，結點（數據域 + 引用域），引用域保存下個元素的存放地址
鏈表結構中數據元素的邏輯順序是通過鏈表中的引用鏈接次序來實現的。
6.樹（Tree）
非線性結構，包括 n 個結點的有窮集合 k。有且僅有一個根結點，沒有前趨結點，其他結點僅有一個前趨結點，可以有 m 個後趨結點
7.圖（Graph）
非線性結構，數據結點稱為頂點，而邊是頂點的有序偶對。
如果兩個頂點之間存在一條邊，那麼就表示這兩個頂點具有相鄰關係
8.散列表（Hash）
源自散列函數，思想是，如果在結構中存在關鍵字和 T 相等的記錄，那麼必定在F( T ) 的存儲位置可以找到該記錄，這樣就可以不用進行比較而直接取得所查記錄。
四. 常用結構
1.1 線性表
1）. 有且僅有一個開始結點，一個後趨結點。
2）. 有且僅有一個終結結點，沒有後趨結點。只有一個前趨結點
3）. 同一線性表，各數據元素必須具有相同的數據結點，即同一線性表中各數據元素具有相同的類型，每個數據元素的長度相同。
基本操作：
初始化（InitList）、計算長度（ListLength）、獲取結點（GetNode）、查找結點（LocateNode）、插入結點（InsertList）、刪除結點（DeleteList）
1.2 順序表結構
按照邏輯次序依次存放在計算機的一組連續的存儲單元中
優點：操作簡單，查詢速度較快
缺點：
1.插入或者刪除結點的時候，需要移動大量數據。
2.如果表比較大，比較難分配足夠的連續存儲空間
順序表操作實例：
SequenceTable類 ；
1.3 鏈表結構
包括：
數據部分：該結點的實際數據
地址部分：保存下一個結點的地址
鏈表結構是由許多這種結點構成的。在進行鏈表操作時，首先需要定義一個“頭引用”變量（head），該變量指向鏈表的第一個結點，... 最後一個結點不指向其他結點（“表尾”），地址部分“ null ”。
鏈表細分為：
單鏈表、雙向鏈表、單循環鏈表、多重鏈的循環鏈表
鏈表實現：
LinkedTable 類 ；
1.4 棧結構
棧結構具有特殊的運算規則、只在一端進行操作 。線性結構：
順序棧結構：
使用連續的內存單元依次保存棧中的數據。
鏈式棧結構：
使用鏈表形式保存棧中各元素的值。
閱讀更多 給我一杯溫開水 的文章
