目錄
1.線性表
2.順序表
1.線性表
線性表（linear list）是n個具有相同特性的數據元素的有限序列。線性表是一種在實際中廣泛使用
的數據結構，常見的線性表：順序表、鏈表、棧、隊列、字符串…
線性表在邏輯上是線性結構，也就是說是連續的一條直線。但是在物理結構上并不一定是連續的，
線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。
線性表在數據結構中有著重要的作用, 線性表在數據結構里，是搭建知識體系的“基石”，也是解決
實際線性數據問題的“實用工具箱”，學好它對掌握更深入的數據結構和算法知識，有著“牽一發而動
全身”的關鍵價值。
而本篇我們將要學習存儲數據的第一種結構，也就是線性表中的順序表:
2.順序表
2.1 概念和結構
概念：順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數
組存儲。
它的結構如下:
2.2 分類
2.2.1 靜態順序表
-靜態順序表：使用定長數組來存儲數據元素的順序表。在C語言中，一般通過預先定義好長度的數
組來實現，并且會用一個變量記錄當前已存儲的有效數據個數 。例如：
2.2.2 動態順序表
動態順序表：基于動態內存分配（如C語言中的 malloc 和 free ）來管理存儲空間的順序表。它包
含一個指向動態分配內存空間的指針，同時會記錄當前已存儲的數據個數以及整個順序表的容量。
當數據元素增加導致空間不足時，可以通過重新分配內存（如 realloc ）來擴大存儲空間。示例代
碼如下
區別:
存儲空間分配:
- 靜態順序表：在編譯時就確定了數組的大小，其占用的內存空間是固定的。一旦定義，在程序運
行過程中無法改變數組的長度。
- 動態順序表：初始時分配一定大小的內存空間，在使用過程中，根據實際需求（如插入元素時發
現空間不足），通過動態內存分配函數來增加或減少內存空間，具有更好的靈活性。
空間利用率:
- 靜態順序表：如果預先分配的空間過大，會造成內存浪費；若分配空間過小，在數據量超出時又
無法存儲更多數據，容易導致溢出錯誤 。例如定義了長度為100的靜態順序表，但實際只存儲10個
數據，就浪費了90個數據單元的空間。
- 動態順序表：根據實際數據量動態調整內存空間，能更合理地利用內存資源。不過，動態內存分
配和重新分配操作也會帶來一定的額外開銷（如頻繁調用?realloc?）。
插入和刪除操作的復雜度（涉及擴容情況）:
- 靜態順序表：插入和刪除操作時，如果不涉及數組越界，時間復雜度主要是移動元素的開銷，平
均時間復雜度為 O(n) 。但如果在插入時數組已滿，就無法完成操作，需要提前預估足夠大的空
間。
- 動態順序表: 在空間足夠的情況下，插入和刪除操作與靜態順序表類似，平均時間復雜度為 O(n)
。而當空間不足需要擴容時，除了移動元素的開銷，還需要進行動態內存分配（如用?realloc?），
雖然單次擴容操作時間復雜度較高，但均攤到每次插入操作上，平均時間復雜度仍接近 O(1) （采
用均攤分析） 。
實現復雜度:
- 靜態順序表：實現相對簡單，不需要處理動態內存分配、釋放以及擴容等復雜邏輯，代碼編寫和
理解起來相對容易。
- 動態順序表：需要處理動態內存的申請、釋放以及在空間不足時的擴容操作，實現過程相對復
雜，同時還要注意內存泄漏等問題（如忘記釋放不再使用的內存）。
綜上所述，通過靜態表和動態表的對比區別，我們可以得出動態表更加全面，在寫代碼的過程中也
更加復雜。所以我們下面學習的順序表是圍繞著動態順序表展開的。
感謝大家的觀看,? 下篇文章，我們將講述關于順序表的實現，也是關于順序表最重要的內容。
