數據結構基石：線性表順序存儲結構深度解析與 C 語言實現

數據結構基石：線性表順序存儲結構深度解析與 C 語言實現

順序存儲結構將邏輯相鄰元素存放在物理相鄰的內存單元中，利用數組的隨機存取特性實現 O(1) 按位序訪問。本文系統講解順序表的邏輯定義、結構體設計、初始化、插入、刪除、查找定位刪除核心算法，並進行嚴格的時間複雜度數學期望分析，附帶完整 C 語言代碼實現。

一、線性表邏輯結構定義

線性表是 n (n≥0) 個數據元素組成的有限序列：

• 唯一的「第一個」元素（無前驅）。
• 唯一的「最後一個」元素（無後繼）。
• 除首尾外，每個元素有且僅有一個直接前驅和直接後繼。
• 元素類型相同（屬於同一數據對象）。

表示為 (a1, a2, ..., an)，a1 為首節點，an 為尾節點。n=0 為空表。

二、順序存儲結構與結構體設計

借助 C 語言數組實現，需動態分配內存並記錄長度：

#define MAX_SIZE 100
#define OK 1
#define ERROR -1
typedef int Status;
typedef int ElemType;

typedef struct {
    ElemType *elem;  // 動態數組基址
    int length;      // 當前長度
} SqList;

三、核心操作算法實現

1. 初始化 InitList

Status InitList(SqList *L) {
    L->elem = (ElemType*)malloc(MAX_SIZE * sizeof(ElemType));
    if (!L->elem) return ERROR; // 分配失敗
    L->length = 0;
    return OK;
}

2. 插入操作 ListInsert

在第 i 位置插入 e，需將第 i 至第 n 個元素後移。

Status ListInsert(SqList *L, int i, ElemType e) {
    if (i < 1 || i > L->length + 1) return ERROR; // 位置非法
    if (L->length >= MAX_SIZE) return ERROR;      // 滿溢出

    for (int j = L->length - 1; j >= i - 1; --j)
        L->elem[j + 1] = L->elem[j]; // 後移
    L->elem[i - 1] = e;              // 插入
    ++L->length;
    return OK;
}

3. 刪除操作 ListDelete

刪除第 i 個元素，將第 i+1 至 n 個元素前移。

Status ListDelete(SqList *L, int i, ElemType *e) {
    if (L->length == 0) return ERROR;             // 空表
    if (i < 1 || i > L->length) return ERROR;     // 位置非法

    *e = L->elem[i - 1];                          // 保存被刪值
    for (int k = i; k < L->length; ++k)
        L->elem[k - 1] = L->elem[k];              // 前移
    --L->length;
    return OK;
}

4. 查找定位刪除 LocateDelete

刪除值為 x 的第一個節點：先查找，找到後前移後續元素。

Status LocateDelete(SqList *L, ElemType x) {
    int i = 0;
    while (i < L->length && L->elem[i] != x) ++i; // 查找
    if (i == L->length) return ERROR;             // 未找到

    for (int k = i + 1; k < L->length; ++k)
        L->elem[k - 1] = L->elem[k];              // 前移
    --L->length;
    return OK;
}

四、時間複雜度數學期望分析

假設操作位置均勻分佈。

1. 插入操作

• 移動次數：第 i 位置插入移動 n - i + 1 次。
• i=1 移動 n 次（最壞 O(n)）；i=n+1 移動 0 次（最好 O(1)）。
• 平均移動次數：Σ (1/(n+1)) * (n-i+1) = n/2 → O(n)。

2. 刪除操作

• 移動次數：第 i 位置刪除移動 n - i 次。
• i=n 移動 0 次；i=1 移動 n-1 次。
• 平均移動次數：Σ (1/n) * (n-i) = (n-1)/2 → O(n)。

3. 查找定位刪除

• 平均比較次數：(n+1)/2。
• 平均移動次數：(n-1)/2。
• 總平均操作次數：n → O(n)。

五、順序表 vs 鏈表 核心對比

六、總結

順序表以「空間換時間」換取 O(1) 隨機訪問，代價是插刪 O(n) 的數據搬移。工程中常作為靜態查找表、堆棧、小規模高頻訪問緩存的底層結構。掌握「邊界檢查（i 合法性）」、「元素後移/前移循環邊界（j>=i-1 / k