目錄

1.順序表的概念及結構

2.動態順序表的實現

2.1創建新項目

2.2動態順序表的創建

2.3接口的實現及測其功能

2.3.1初始化

2.3.2尾插

2.3.3頭插

2.3.4尾刪&頭刪

2.3.5打印&從任意位置插入

2.3.6刪除任意位置的數據

2.3.7查找

2.3.8銷毀順序表

3.結語

---

Hello everybody!今天打算跟大家聊聊動態順序表。順序表是最基礎的數據結構，也是最實用的數據結構。在今后學習棧和隊列時，會基于順序表去實現它們。動態順序表顧名思義，就是容量可變的順序表。我們可以隨意在該順序表中插入數值，并且會自動擴容，十分具有實際應用的價值。那廢話不多說，讓我們開始叭！

1.順序表的概念及結構

順序表是用一段物理地址連續的存儲單元一次存儲數據元素的線性結構，一般情況下采用數值存儲。在數值上完成數據的增刪查改。

順序表一般可以分為：

1.靜態順序表：使用定長數組存儲元素

2.動態順序表：使用動態開辟的數組存儲

由于靜態順序表實用價值極低，實現思路上不如動態順序表，且會實現動態順序表的話實現靜態順序表也沒有太大的問題。因此在這里只給大家詳細講解一下動態順序表的實現！

2.動態順序表的實現

2.1創建新項目

進入數據結構，我們要寫的代碼量會有十分明顯的增加。例如今天的動態順序表，代碼量將會輕輕松松突破100行。所以我建議創建三個文件。這樣便于理清代碼邏輯以及后期代碼的維護。我在上一篇文章和上上篇文章中有更詳細的介紹，如果有疑問可以參考棧詳解或隊列詳解。

2.2動態順序表的創建

首先我們要把需要用到的頭文件包含進來，下面的結構體就是咱們的順序表。其中各個變量的作用我已經注釋出來。結構體的下面是順序表的各種接口。

2.3接口的實現及測其功能

2.3.1初始化

首先我們來解釋一下為什么要傳結構體指針而不是結構體：要知道，函數傳參是對實際參數的拷貝。如果傳結構體的話，在函數體內部的一切操作都不會對函數外部的結構體有任何改變，所以我們需要傳指針。

這里將順序表的各個變量給一個起始值就算是完成初始化了。

2.3.2尾插

這兩個接口實現完成后我們來看看它們的功能如何：

在測試功能中，我們首先初始化，然后依次尾插了1，2，3，4，5，五個數據。該動態順序表應該會擴容兩次，因此容積是8，有效數據有5個，size為5。測試結果符合預期，這兩個接口功能正常。

2.3.3頭插

由于頭插依然會涉及到順序表容量不夠用從而自動擴容的情況，那么這個接口會有相當一部分代碼和尾插一模一樣。考慮到代碼的簡潔性，我們把自動擴容功能單獨拎出來形成一個函數：

有了這個函數，頭插和尾插直接調用它就ok了！

在頭插中，我們需要移動數據。在while循環中把所有的數據向后移動一位，再把要插入的數據把順序表中的第一個數據覆蓋掉。移動數據的時間復雜度是O(n)，效率不高。由此可見順序表并不適合頭插。同樣的，也不適合頭刪。

測試功能正常。

2.3.4尾刪&頭刪

尾刪和頭刪的邏輯就比較簡單了。但是要特別說明一下，尾刪和頭刪并不是正在意義上的和數據刪除了，對于尾刪，只需把size減小一個就可以了，以后插入數據的話自然會把原數據覆蓋掉。頭刪就是用后面的數據向前覆蓋，也是同樣的道理。

2.3.5打印&從任意位置插入

如果上面的接口搞懂了的話，這兩個接口就沒什么難度啦！

2.3.6刪除任意位置的數據

2.3.7查找

2.3.8銷毀順序表

3.結語

好啦，關于動態順序表的討論就到這里嘍。看完這篇文章依然沒有搞懂的寶子可以把自己的疑惑發在評論區呦！

順序表是數據結構的基礎，大家一定要熟悉它！