数据结构——线性表（顺序表）

一、线性表顺序存储详解

（一）线性表核心概念

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 时间复杂度对比

2 空间复杂度

• 存储空间：O(n)
• 额外空间：O(1)

（五）内存管理实践

1 内存管理要点

1. malloc/free配对 ：确保每个分配都有释放
2. 越界访问检查 ：严格验证索引范围
3. 野指针处理 ：释放后置空指针 free(list->head); list->head = NULL; // 重要！

（六）顺序存储优劣分析

1 优势场景

• 高频随机访问 ：学生成绩快速查询
• 数据规模稳定 ：固定长度的传感器数据缓存
• 内存敏感场景 ：无额外指针开销

2 局限场景

• 动态数据管理 ：实时消息队列
• 高频插入删除 ：聊天记录管理
• 超大稀疏数据 ：地图坐标存储