目錄

一.線性表

二.順序表

1.概念

?2.結構

3.要實現的接口函數

三.模擬實現順序表

1.定義出順序表的基本結構

2.實現檢查擴容功能

3.實現尾插

4.實現尾刪

5.實現頭插和頭刪

6.查找

7.修改

8.遍歷

9.在指定位置插入和刪除

四.順序表的優缺點及思考

?a.順序表的弊端

---

一.線性表

? 在談順序表前，我們要先說說線性表了，線性表（linear list）是n個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列、字符串...

? 線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。

? 說白了，線性表在邏輯上就是一條線性結構，數據之間的排列是一個接一個的，盡管它們在物理上不一定是線性的；

如下圖所示兩種線性表的邏輯結構，它們的數據看起來都是首尾相連的；

二.順序表

1.概念

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

?2.結構

? ?順序表可以分為靜態順序表和動態順序表，靜態順序表采用定長數組的形式來存儲元素，而動態順序表則可以根據需要進行擴容，相對而言還是動態順序表更加實用，我們這里實現的也是動態順序表。

? 靜態與動態順序表的結構示意如下（c語言版）

? 其中，SLDataType是表示指定類型的宏定義，在c++中可以用模版來代替！size為有效元素的個數，capacity為數組的容量，不夠時可以通過realloc擴容；

3.要實現的接口函數

三.模擬實現順序表

? 模擬實現我們采用c++的方式來，因為寫起來更方便，而且初始化和銷毀都包含在構造函數和析構函數中了，無需我們手動調用；

1.定義出順序表的基本結構

#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
#include<cstdlib>
#include <assert.h>
using namespace std;
using DataType = int;
class seqList
{
public:seqList():_num(nullptr),_size(0),_capacity(0){}~seqList(){delete(_num);_size = 0;_capacity = 0;}private:DataType* _num;int _size;int _capacity;
};

2.實現檢查擴容功能

? 因為我們往數組里添加數據可能遇到數組空間不夠的情況，所以要能檢測到這種需要進行擴容的情況！

void SeqListCheckCapacity()
{if (_size == _capacity){int newcapacity = _capacity == 0 ? 4 : _capacity * 2;DataType* tmp = (DataType*)realloc(_num, sizeof(DataType) * newcapacity);if (tmp == nullptr){perror("擴容出錯：");return;}_num = tmp;_capacity = newcapacity;}
}

3.實現尾插

? 插入數據之前，要先檢查一下當前是否需要擴容了，這樣能夠確保空間足夠，插入數據之后不要忘記維護代表元素個數的_size;

void SeqListPushBack(DataType x)
{SeqListCheckCapacity();_num[_size++] = x;
}

4.實現尾刪

? 刪除數據前要先確保數組內還有剩余數據，如果有，只需要將元素個數減一即可，因為我們查找和遍歷順序表時都是通過_size來進行的！

void SeqListPopBack()
{assert(_size > 0);_size--;
}

5.實現頭插和頭刪

? ?只要是插入，就要首先判斷擴容，只要是刪除，就要先判斷是否有數據；

? ?頭插和頭刪的共同點是都要移動元素，對于頭插，我們在順序表頭部插入元素之前，必須將原來的所有數據整體往右移一位，才能給插入數據騰出空間，此時要頭插注意移動的方法，必須是從右往左進行的，每次都選取要移動到的位置，然后將左邊的數移到該位置；如果從左往右依次移動，會出現左邊值覆蓋右邊值的情況！

? 尾刪要先將數據向左集體移動一位，采用從左往右依次移動一位的方式；

void SeqListPushFront(DataType x)
{SeqListCheckCapacity();for (int i = _size; i > 0; i--){_num[i] = _num[i - 1];}_num[0] = x;_size++;
}

void SeqListPopFront()
{assert(_size > 0);for (int i = 0; i < _size - 1; i++){_num[i] = _num[i + 1];}_size--;
}

6.查找

? 沒啥好說的，就是遍歷數組找關鍵值

int SeqListFind(DataType x)
{for (int i = 0; i < _size; i++){if (_num[i] == x){return i;}}return -1;}

7.修改

void SeqListModity(int pos,DataType x)
{assert(pos >= 0 && pos < _size);_num[pos] = x;
}

8.遍歷

	void SeqListPrint(){for (int i = 0; i < _size; i++){printf("%d ", _num[i]);}}

9.在指定位置插入和刪除

要注意的地方前面都已經強調過了，就是要注意插入前的檢查擴容、元素的移動方式、size的維護、刪除前的檢查剩余數據

void SeqListInsert(int pos, DataType x)
{assert(pos >= 0 && pos < _size);SeqListCheckCapacity();for (int i = _size; i > pos; i--){_num[i] = _num[i - 1];}_num[pos] = x;_size++;
}
void SeqLIstDelete(int pos)
{assert(pos >= 0 && pos < _size);for (int i = pos; i < _size - 1; i++){_num[i] = _num[i + 1];}_size--;
}

四.順序表的優缺點及思考

?a.順序表的弊端

1. 中間/頭部的插入刪除，由于要整體移動元素，所以時間復雜度為O(N)
2. 由于realloc的特性：

1. 原地調整：如果原內存塊后有足夠的空間，realloc會直接擴展內存塊，而無需移動數據。
2. 重新分配：如果原內存塊后空間不足，realloc會分配一塊新的內存，并將原數據復制到新內存中，同時釋放原內存塊。

所以增容可能需要申請新空間，拷貝數據，釋放舊空間。會有不小的消耗。
3. 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到? 200，我們再繼續插入了5個數據，后面沒有數據插入了，那么就浪費了95個數據空間。

b.順序表的優點

? 1.隨機訪問效率高

??順序表最大的優點是支持隨機訪問，通過下標可以直接訪問任意位置的元素，時間復雜度為O(1)。這使得順序表在需要頻繁查找或按索引訪問元素的場景中表現出色，比如數組操作。

? 2.存儲密度高

? 順序表在內存中是連續存儲的，不需要額外的空間來存儲元素之間的邏輯關系，因此存儲密度高。相比鏈表等結構，順序表在存儲相同數量元素時占用的內存更少。

? 3.緩存友好

? 由于順序表在內存中是連續存儲的，訪問元素時具有良好的局部性，能夠充分利用CPU緩存機制，提高訪問速度。這一點在處理大量數據時尤為重要。