【數據結構】順序表的應用

一.引言? ? ? ??

二.順序表概念

三.順序表的實現

1.定義順序表

2.順序表初始化

?編輯

3.檢查空間，如果滿了，進行增容

4.順序表尾插

5.順序表尾刪

6.順序表頭插

7.順序表頭刪

?編輯

8.順序表查找

9.順序表在pos位置插入x

10.順序表刪除pos位置的值

11.順序表銷毀

12.順序表打印

一.引言? ? ? ??

????????在計算機科學中，數據結構是計算機存儲、組織數據的方式。順序表作為一種線性表，以其簡單、易用的特點，成為了許多高級數據結構的基礎。了解順序表的工作原理和實現方法，對于我們更好地理解計算機科學具有重要意義。

二.順序表概念

????????順序表（Sequential List）是一種線性表，它的特點是數據元素在物理存儲上連續，且元素之間的邏輯順序與物理順序相同。在順序表中，數據元素按照一定的順序排列，每個元素都有一個確定的位置，可以通過索引（或稱為下標）直接訪問。

以下是順序表的基本概念和特性：

數據元素：順序表中的每一個對象稱為數據元素，可以是整數、浮點數、字符或者更復雜的記錄類型。
索引（下標）：順序表中的每個數據元素都有一個索引，通常從0開始計數，用于指示元素在表中的位置。
長度：順序表的長度是指表中數據元素的個數，長度可以根據需要進行動態調整，但通常有一個最大容量限制。
存儲空間：順序表通常在計算機內存中占用一段連續的存儲空間，以便于通過索引快速訪問元素。
隨機訪問：順序表支持隨機訪問，即可以在O(1)的時間復雜度內直接訪問到任意位置的元素。
順序性：順序表中的元素按照一定的順序排列，元素之間的順序關系是相鄰的，即第一個元素緊鄰第二個元素，以此類推。

順序表的主要操作包括：

初始化：創建一個空的順序表。
插入：在順序表的指定位置插入一個新的數據元素。
刪除：從順序表中刪除指定的數據元素。
查找：根據特定條件在順序表中查找數據元素。
排序：對順序表中的元素進行排序。
清空：將順序表中的所有元素刪除，使其變為空表。
遍歷：按照順序訪問順序表中的每一個元素。

順序表的優缺點如下：

優點：

訪問效率高：隨機訪問能力強，訪問任意元素的時間復雜度為O(1)。
存儲密度高：順序表的數據元素緊密排列，不需要額外的空間存儲元素間的關系。

缺點：

插入和刪除操作效率低：在順序表的中間或頭部插入或刪除元素時，可能需要移動大量元素，時間復雜度為O(n)。
固定容量：通常順序表的容量是固定的，若存儲空間不足，需要進行擴容操作，這可能會導致性能下降。

順序表是實現其他復雜數據結構（如棧、隊列等）的基礎，它在算法設計和實際應用中有著廣泛的使用。? （后續也會發布用順序表來實現棧和隊列）

三.順序表的實現

????????靜態順序表只適用于確定知道需要存多少數據的場景。靜態順序表的定長數組導致N定大了，空間開多了浪費，開少了不夠用。所以現實中基本都是使用動態順序表，根據需要動態的分配空間大小，所以下面我們實現動態順序表。

1.定義順序表

????????這里使用typedef函數來講重命名為SLDateType是因為插入順序表的數據不會是固定不變的，這么做也是為了方便后續管理和更新。

2.順序表初始化

? ? ? ? 將結構體里的array指向空指針，防止其變為野指針。

3.檢查空間，如果滿了，進行增容

? ? ? ? 結構體里的capacity的主要功能就在這一板塊實現，主要是為了檢查順序表內數據是否存滿。如果滿了就使用realloc函數來再次開辟空間。（這里使用了三目操作符，不懂的小伙伴可以點擊三目操作符）

4.順序表尾插

5.順序表尾刪

? ? ? ? 此操作簡單易懂，需要注意的是這里的刪除并不是真正物理上刪除了數據，而是邏輯上減小了size的值，使print讀取不到他，來做到刪除的效果。