順序表實現代碼解析與學習筆記

一、順序表基礎概念

順序表是線性表的一種順序存儲結構，它使用一段連續的內存空間（數組）存儲數據元素，通過下標直接訪問元素，具有隨機訪問的特性。其核心特點是：元素在內存中連續存放，邏輯順序與物理順序一致。

二、代碼結構說明

本次實現包含 3 個文件，分工如下：

• arraylist.h：定義順序表結構體及相關操作函數的聲明

• arraylist.c：實現順序表的核心操作函數

• main.c：測試順序表的各項功能

三、核心結構體解析

在arraylist.h中定義了順序表的結構體：

typedef struct{?int capacity; ?  // 順序表的容量（最大可存儲元素數）?int last; ? ? ?  // 最后一個元素的下標（-1表示空表）?int \*data; ? ? ? // 指向存儲元素的數組（堆內存）?} ArrayList;

• capacity：記錄當前順序表的最大容量（數組長度）

• last：通過下標管理實際元素數量（元素個數 = last + 1）

• data：動態數組指針，實際存儲元素的內存空間

四、核心函數實現解析

1. 初始化函數 init_list

?ArrayList \*init\_list(int cap) {?if (cap <= 0) return NULL;  // 容量必須為正數?ArrayList \*list = malloc(sizeof(ArrayList));?if (list) {?list->data = calloc(cap, sizeof(int));  // 分配數組內存并初始化為0?if (list->data == NULL) {?free(list);  // 數組內存分配失敗時，釋放結構體?return NULL;?}?list->capacity = cap;?list->last = -1;  // 初始化為空表?return list;?}?return NULL;?}

• 功能：創建并初始化順序表，分配結構體和數組內存

• 關鍵：參數校驗（容量 > 0）、內存分配失敗的容錯處理

2. 插入函數 insert（頭插法）

?bool insert(ArrayList \*list, int data) {?if (list == NULL) return false;?// 滿表時擴容（2倍擴容）?if (is\_full(list) && !expand\_list(list)) return false;?// 元素后移（從最后一個元素開始）?for (int i = list->last; i >= 0; i--) {?list->data\[i+1] = list->data\[i];?}?// 插入新元素到表頭（下標0）?list->data\[0] = data;?list->last++;  // 更新最后元素下標?return true;?}

• 特點：采用頭插法（新元素插入到表頭位置）

• 擴容邏輯：當表滿時調用expand_list擴容為原容量的 2 倍

• 時間復雜度：O (n)（需要移動所有現有元素）

3. 擴容函數 expand_list（靜態輔助函數）

?static bool expand\_list(ArrayList \*list) {?if (list == NULL) return false;?int new\_cap = list->capacity \* 2;  // 2倍擴容策略?int \*new\_data = realloc(list->data, sizeof(int) \* new\_cap);?if (new\_data == NULL) return false;?list->data = new\_data;?list->capacity = new\_cap;?// 初始化新增內存（可選操作）?for (int i = list->last + 1; i < new\_cap; i++) {?list->data\[i] = 0;?}?return true;?}

• 關鍵：使用realloc重新分配內存，避免內存泄漏

• 擴容策略：簡單采用 2 倍擴容（實際應用中可根據需求優化，如 1.5 倍擴容減少內存浪費）

4. 刪除函數 remove_data

?bool remove\_data(ArrayList \*list, int data) {?if (!list || is\_empty(list)) return false;?// 查找第一個匹配元素的位置?int pos = -1;?for (int i = 0; i <= list->last; i++) {?if (list->data\[i] == data) {?pos = i;?break;?}?}?if (pos == -1) return false;  // 未找到元素?// 元素前移（覆蓋被刪除元素）?for (int i = pos; i < list->last; i++) {?list->data\[i] = list->data\[i+1];?}?list->last--;  // 更新最后元素下標?return true;?}

• 功能：刪除第一個匹配的元素

• 步驟：查找位置 → 元素前移 → 更新下標

• 時間復雜度：O (n)（最壞情況需要移動 n-1 個元素）

5. 銷毀函數 destroy

?void destroy(ArrayList \*list) {?if (list == NULL) return;?if (list->data != NULL) {?free(list->data);  // 先釋放數組內存?list->data = NULL;  // 避免懸掛指針?}?free(list);  // 再釋放結構體內存?list = NULL;?}

• 關鍵：先釋放內部動態數組，再釋放結構體，避免內存泄漏

• 注意：置空指針（list->data = NULL）防止后續誤操作

五、測試流程解析（main.c）

1. 初始化順序表：創建容量為 3 的順序表

2. 測試插入功能：插入 5 個數據（10、20、30、40、50）

• 插入前 3 個數據時，容量為 3（未擴容）

• 插入第 4 個數據時，表滿觸發擴容（容量變為 6）

1. 遍歷輸出：打印當前順序表的所有元素（頭插法下，元素順序為 50、40、30、20、10）

2. 測試刪除功能：依次刪除 30、10、50、12（12 不存在）

3. 銷毀順序表：釋放所有分配的內存

六、學習筆記總結

1. 順序表優缺點

• 優點：隨機訪問（通過下標直接訪問，時間復雜度 O (1)）

• 缺點：插入 / 刪除中間元素時需要移動大量元素（時間復雜度 O (n)）；容量固定（需手動擴容）

1. 頭插法特點

• 新元素始終插入到表頭，插入順序與元素存儲順序相反（如插入 10→20→30，存儲為 30、20、10）

• 每次插入都需移動所有現有元素，適合元素數量少的場景

1. 擴容策略思考

• 2 倍擴容：減少擴容次數，但可能浪費內存

• 1.5 倍擴容：平衡擴容次數和內存浪費，更適合實際應用

• 擴容時使用realloc，可能觸發內存拷貝（原有內存不足時）

1. 內存管理要點

• 動態內存分配后必須檢查是否成功（NULL判斷）

• 釋放內存時需先釋放內部資源（如data數組），再釋放外部結構體

• 釋放后指針置空，避免懸掛指針導致的野指針操作

通過以上代碼實現，可以清晰理解順序表的基本操作原理及內存管理細節，為學習更復雜的數據結構奠定基礎。