目錄

一. 線性表

二. 順序表的概念與結構

2.1 核心概念

2.2 兩種常見結構

靜態順序表

動態順序表

2.3 核心區別對比

四. 順序表的實現

4.1 順序表的定義

4.2 順序表初始化

4.3 動態順序表容量檢查與擴容

4.4 動態順序表插入數據

4.4.1 頭插

4.4.2 尾插

4.4.3 指定位置插入

4.5 動態順序表的刪除數據

4.5.1 頭刪

4.5.2 尾刪

4.5.3 刪除指定位置的數據

4.5.4 刪除指定的數據

4.6 查找指定數據

4.6?動態順序表銷毀

五. 優缺點分析

六. 適用場景選擇

七. 總結

---

在學習順序表之前 我們需要有一定的基礎知識 首先我們需要了解線性表

一. 線性表

線性表是具有 “一對一” 邏輯關系的有限數據元素序列，是數據結構中最基礎、最常用的結構之一，廣泛應用于數組、鏈表等底層實現，也是棧、隊列等復雜結構的基礎。

核心定義與邏輯特征

線性表由?n（n≥0）?個相同數據類型的元素構成，記為?L = (a?, a?, ..., a?)，其中：

• a??是首元素（無前驅），a??是尾元素（無后繼）；

• 除?a??和?a??外，每個元素?a?（2≤i≤n-1）?有且僅有一個前驅（a???）和一個后繼（a???）；

• n=0?時稱為空表（無任何元素）。

兩種核心存儲結構( 暫時只做了解 )

線性表的存儲結構決定了其操作效率，核心分為 “順序存儲” 和 “鏈式存儲” 兩類，二者各有優劣：

對比維度	順序存儲結構（順序表）	鏈式存儲結構（鏈表）
存儲方式	用連續的存儲單元依次存儲元素	用任意存儲單元存儲元素，通過指針 / 引用鏈接邏輯關系
邏輯與物理關系	邏輯順序 ≡ 物理順序	邏輯順序 ≠ 物理順序（靠指針維護）
訪問效率	支持隨機訪問（通過索引?O(1)?定位）	僅支持順序訪問（需從表頭遍歷，O(n)）
插入 / 刪除效率	中間 / 頭部操作需移動元素（O(n)），尾部插入?O(1)	僅需修改指針（O(1)，前提是找到目標位置）
空間利用率	可能存在 “內存碎片”（預分配空間未用完）	無碎片，但需額外存儲指針（空間開銷略大）
典型實現	數組（如 C 語言數組、Java ArrayList）	單鏈表、雙向鏈表、循環鏈表（如 Java LinkedList）

二. 順序表的概念與結構

順序表是線性表的順序存儲結構，核心是用一段地址連續的物理存儲單元依次存儲線性表中的元素，使得元素的 “邏輯順序” 與 “物理存儲順序完全一致”（即第 1 個元素存在第 1 個物理位置，第 2 個元素存在第 2 個物理位置，以此類推）。

2.1 核心概念

順序表本質是 “基于數組的線性表實現”，但相比普通數組，它會額外記錄當前元素個數（避免越界）和數組容量（方便擴容），是對數組的 “結構化封裝”，確保符合線性表的邏輯特征（一對一前驅 / 后繼關系）。

例如：存儲?[1,3,5,7]?的順序表，物理存儲上元素在內存中連續排列，邏輯上?1?的后繼是?3、3?的后繼是?5，與物理位置順序完全匹配。

2.2 兩種常見結構

根據數組空間的分配方式，順序表分為 “靜態順序表” 和 “動態順序表”，實際開發中動態順序表更常用（避免空間浪費或不足）。

靜態順序表

• 特點：使用固定大小的數組存儲元素，容量在定義時確定，無法動態調整。
• 結構定義：

  #define MAX_SIZE 100  // 固定容量
  typedef int SLDataType;  // 元素類型（可替換為其他類型）// 靜態順序表結構
  typedef struct SeqList {SLDataType arr[MAX_SIZE];  // 固定大小的數組，存儲元素int size;                  // 當前元素個數（關鍵：記錄有效元素數量）
  } SeqList;
  

• 缺點：容量固定，若元素個數超過?MAX_SIZE?會溢出；若元素少則浪費內存。

動態順序表

• 特點：使用動態內存分配的數組（如?malloc/realloc?分配），容量可根據元素個數動態擴容 / 縮容，靈活性更高。
• 結構定義：

  typedef int SLDataType;// 動態順序表結構
  typedef struct SeqList {SLDataType* arr;  // 指向動態分配數組的指針（存儲元素）int size;         // 當前元素個數（有效元素數）int capacity;     // 當前數組的容量（最大可存儲元素數）
  } SeqList;
  

• 核心優勢：容量按需調整，避免靜態順序表的空間浪費或溢出問題，是實際開發中的主流選擇。

2.3 核心區別對比

對比維度	靜態順序表	動態順序表
存儲空間分配	編譯時固定分配（棧上或全局區）	運行時動態分配（堆內存）
容量特性	容量固定，不可改變	容量可變，可動態擴容 / 縮容
空間利用率	可能浪費（容量大于實際需求）	利用率高（按需分配）
溢出風險	有（元素數超過最大容量時）	無（可動態擴容避免溢出）
內存管理復雜度	簡單（自動分配和釋放）	復雜（需手動分配、擴容和釋放）
實現難度	簡單	稍復雜（需實現擴容邏輯）

四. 順序表的實現

4.1 順序表的定義

靜態順序表:

#define MAX_SIZE 100  // 固定容量
typedef int SLDataType;  // 元素類型（可替換為其他類型）// 靜態順序表結構
typedef struct SeqList {SLDataType arr[MAX_SIZE];  // 固定大小的數組，存儲元素int size;                  // 當前元素個數（關鍵：記錄有效元素數量）
} SeqList;

動態順序表:

typedef int SLDataType;// 動態順序表結構
typedef struct SeqList {SLDataType* arr;  // 指向動態分配數組的指針（存儲元素）int size;         // 當前元素個數（有效元素數）int capacity;     // 當前數組的容量（最大可存儲元素數）
} SeqList;

4.2 順序表初始化

靜態順序表初始化：

void StaticSeqListInit(StaticSeqList* ssl) {ssl->size = 0;  // 只需初始化元素個數為0，數組空間已固定分配
}

動態順序表初始化：

void DynamicSeqListInit(DynamicSeqList* dsl) {dsl->data = NULL;dsl->size = 0;dsl->capacity = 0;  // 初始容量為0，或可分配默認初始容量

4.3 動態順序表容量檢查與擴容

// 檢查容量，不足則擴容
void CheckCapacity(DynamicSeqList* dsl) {if (dsl->size == dsl->capacity) {// 計算新容量，初始容量為0則設為4，否則翻倍int newCapacity = dsl->capacity == 0 ? 4 : dsl->capacity * 2;// 重新分配內存SLDataType* newData = (SLDataType*)realloc(dsl->data, newCapacity * sizeof(SLDataType));if (newData == NULL) {perror("realloc failed");exit(EXIT_FAILURE);}dsl->data = newData;dsl->capacity = newCapacity;}
}

4.4 動態順序表插入數據

4.4.1 頭插

//頭插
void SLPushFront(SL* ps, SLdatatype x)
{assert(ps);//ps！=NULL//檢查空間是否足夠SLCheckCapacity(ps);//空間足夠for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}

4.4.2 尾插

//尾插
void SLPushBack(SL* ps, SLTDataType x)
{//空間不夠if (ps->size == ps->capacity){//增容int newCapacity = ps->capacity ==0 ? 4 : 2 * ps->capacity;SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity*sizeof(SLTDataType));if (tmp = NULL){perror("realloc");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空間足夠ps->arr[ps->size++] = x;//插入完后，size往后走
}

4.4.3 指定位置插入

// 在pos位置插入元素value
int DynamicSeqListInsert(DynamicSeqList* dsl, int pos, SLDataType value) {if (pos < 0 || pos > dsl->size) return -1;CheckCapacity(dsl);  // 自動檢查并擴容// 移動元素for (int i = dsl->size; i > pos; i--) {dsl->data[i] = dsl->data[i-1];}// 插入新元素dsl->data[pos] = value;dsl->size++;return 0;
}

4.5 動態順序表的刪除數據

4.5.1 頭刪

//尾刪
void SLPopBack(SL* ps)
{assert(ps && ps->size);ps->size--;
}

4.5.2 尾刪

//尾刪
void SLPopBack(SL* ps)
{assert(ps && ps->size);ps->size--;
}

4.5.3 刪除指定位置的數據

void  SQdelete(SL* ps, int pos) //刪除第x個數據 這個x是數組的下標
{assert(ps->size > 0 && ps->size > pos);while (ps->size-pos>0){ps->arr[pos] = ps->arr[pos + 1];pos++;}ps->size--;
}

4.5.4 刪除指定的數據

void SQLdex(SL* ps, int x) //刪除查找到的所有x
{int i = 0;while (i < ps->size){if (ps->arr[i] == x){// 元素前移覆蓋要刪除的元素for (int j = i; j < ps->size - 1; j++){ps->arr[j] = ps->arr[j + 1];}ps->size--; // 元素數量減1// 不執行i++，因為下一個元素移動到了當前位置}else{i++; // 只有當沒有刪除元素時，才移動到下一個位置}}
}

4.6 查找指定數據

void SLFind(SL* ps, SLdate x)
{for (int i = 0;i < ps->size;i++){if (ps->arr[i] == x){printf("找到了 順序表第%d個",i+1);printf("\n");}}
}

4.6?動態順序表銷毀

// 必須手動釋放動態分配的內存，避免內存泄漏
void DynamicSeqListDestroy(DynamicSeqList* dsl) {free(dsl->data);dsl->data = NULL;dsl->size = 0;dsl->capacity = 0;
}

示例運行結果如下:

五. 優缺點分析

靜態順序表

• 優點：

  • 實現簡單，無需處理復雜的內存分配邏輯

  • 訪問速度快，無需額外的指針操作

  • 棧上分配內存，自動釋放，不會造成內存泄漏

• 缺點：

  • 容量固定，無法適應數據量動態變化的場景

  • 可能造成內存空間浪費（當實際元素遠少于最大容量時）

  • 存在溢出風險（當元素數量超過最大容量時）

動態順序表

• 優點：

  • 容量可動態調整，能靈活適應數據量變化

  • 內存利用率高，按需分配空間

  • 不存在固定容量導致的溢出問題

• 缺點：

  • 實現相對復雜，需要處理擴容、內存分配等問題

  • 擴容時可能產生內存碎片

  • 需手動管理內存，若操作不當易造成內存泄漏

  • 擴容過程中需要拷貝數據，可能影響性能

六. 適用場景選擇

1. 靜態順序表適用場景：

   • 數據量已知且固定不變的情況

   • 對內存管理要求簡單，不希望手動處理內存分配的場景

   • 嵌入式系統、單片機等內存資源受限且數據量固定的環境

2. 動態順序表適用場景：

   • 數據量不確定，需要動態增減的情況

   • 對內存利用率要求較高的場景

   • 大部分通用編程場景，如實現動態數組、列表等數據結構

七. 總結

靜態順序表和動態順序表都是基于數組的線性表實現，核心區別在于存儲空間是否可動態調整。靜態順序表簡單直接但缺乏靈活性，動態順序表靈活高效但實現稍復雜。

在實際開發中，動態順序表應用更為廣泛，因為它能更好地適應數據量動態變化的需求。了解兩者的特點和差異，有助于根據具體場景選擇合適的實現方式，從而優化程序性能和內存使用。