一、線性表順序存儲詳解
（一）線性表核心概念
1. 結構定義
// 數據元素類型
typedef struct person {char name[32];char sex;int age;int score;
} DATATYPE;// 順序表結構
typedef struct list {DATATYPE *head; // 存儲空間基地址int tlen; // 表總長度int clen; // 當前元素個數
} SeqList;
2. 核心特性
- 有限性：元素個數n ≥ 0
- 有序性：元素位置由序號確定（a?~a?）
- 同類型：所有元素屬于同一數據類
（二）基本操作接口
1. 創建/銷毀
// 創建順序表
SeqList *CreateSeqList(int len) {SeqList *list = (SeqList *)malloc(sizeof(SeqList));list->head = (DATATYPE *)malloc(len * sizeof(DATATYPE));list->tlen = len;list->clen = 0;return list;
}// 銷毀順序表
int DestroySeqList(SeqList *list) {free(list->head);free(list);return 0;
}
2. 狀態判斷
// 判斷表滿
int IsFullSeqList(SeqList *list) {return list->clen >= list->tlen;
}// 判斷表空
int IsEmptySeqList(SeqList *list) {return list->clen == 0;
}
（三）核心操作實現
1. 插入操作
// 尾部插入
int InsertTailSeqList(SeqList *list, DATATYPE data) {if (IsFullSeqList(list)) return -1;list->head[list->clen++] = data;return 0;
}// 指定位置插入
int InsertPosSeqList(SeqList *list, DATATYPE data, int pos) {if (pos < 0 || pos > list->clen) return -1;if (IsFullSeqList(list)) return -1;// 移動后續元素for(int i = list->clen; i > pos; i--) {list->head[i] = list->head[i-1];}list->head[pos] = data;list->clen++;return 0;
}
2. 刪除操作
// 按姓名刪除
int DeleteSeqList(SeqList *list, char *name) {for(int i = 0; i < list->clen; i++) {if(strcmp(list->head[i].name, name) == 0) {// 前移后續元素for(int j = i; j < list->clen-1; j++) {list->head[j] = list->head[j+1];}list->clen--;return 0;}}return -1;
}
（四）性能分析
1. 時間復雜度對比
| 操作 | 最好情況 | 最壞情況 | 平均情況 |
|---|
| 隨機訪問 | O(1) | O(1) | O(1) |
| 插入/刪除 | O(1) | O(n) | O(n) |
| 查找 | O(1) | O(n) | O(n) |
2. 空間復雜度
（五）內存管理實踐
1. 內存管理要點
- malloc/free配對：確保每個分配都有釋放
- 越界訪問檢查：嚴格驗證索引范圍
- 野指針處理：釋放后置空指針
free(list->head);
list->head = NULL; // 重要！
（六）順序存儲優劣分析
1. 優勢場景
- 高頻隨機訪問：學生成績快速查詢
- 數據規模穩定：固定長度的傳感器數據緩存
- 內存敏感場景：無額外指針開銷
2. 局限場景
- 動態數據管理：實時消息隊列
- 高頻插入刪除：聊天記錄管理
- 超大稀疏數據：地圖坐標存儲
)
