线性表顺序存储结构全解析，第十四篇：Python异步IO编程（asyncio）核心原理解析。

线性表的顺序存储结构

顺序存储结构是线性表最基础的物理实现方式之一，其核心思想是通过一段连续的存储空间依次存放线性表中的数据元素。这种结构利用数组的物理地址连续性，使得逻辑上相邻的元素在物理存储上也相邻。

存储方式与特点

顺序存储结构通常使用一维数组实现，数组的下标对应线性表中元素的位序。假设线性表的最大容量为MAXSIZE，元素的类型为ElemType，则可定义如下结构体：

#define MAXSIZE 100 // 线性表的最大长度 typedef struct { ElemType data[MAXSIZE]; // 存储数据元素的数组 int length; // 当前线性表长度 } SqList;

特点：

• 随机访问效率高：通过下标可直接访问任意位置元素，时间复杂度为 $O(1)$。
• 存储密度高：仅需存储数据元素，无需额外空间维护逻辑关系。
• 插入删除效率低：平均需要移动半数元素，时间复杂度为 $O(n)$。

基本操作实现

初始化操作创建一个空的顺序表，并将长度字段初始化为0：

void InitList(SqList *L) { L->length = 0; }

插入操作在位置i（1 ≤ i ≤ length+1）插入新元素e：

int ListInsert(SqList *L, int i, ElemType e) { if (i < 1 || i > L->length + 1) return 0; // 非法位置 if (L->length >= MAXSIZE) return 0; // 存储空间已满 for (int j = L->length; j >= i; j--) L->data[j] = L->data[j-1]; // 元素后移 L->data[i-1] = e; L->length++; return 1; }

删除操作删除位置i（1 ≤ i ≤ length）的元素，并通过e返回其值：

int ListDelete(SqList *L, int i, ElemType *e) { if (i < 1 || i > L->length) return 0; // 非法位置 *e = L->data[i-1]; for (int j = i; j < L->length; j++) L->data[j-1] = L->data[j]; // 元素前移 L->length--; return 1; }

性能分析

时间效率

• 查找操作：按位查找 $O(1)$，按值查找 $O(n)$。
• 插入/删除操作：最好情况 $O(1)$（尾端操作），最坏情况 $O(n)$（首端操作），平均 $O(n)$。

空间效率

• 预分配固定大小的存储空间，可能造成空间浪费或溢出。

动态扩容机制

为克服静态分配的空间限制，可采用动态扩容策略：

typedef struct { ElemType *data; // 动态分配数组指针 int length; // 当前长度 int capacity; // 当前容量 } SeqList; void InitDynamicList(SeqList *L, int initSize) { L->data = (ElemType*)malloc(initSize * sizeof(ElemType)); L->length = 0; L->capacity = initSize; } int DynamicInsert(SeqList *L, int i, ElemType e) { if (i < 1 || i > L->length + 1) return 0; if (L->length >= L->capacity) { // 空间不足时扩容 ElemType *newBase = (ElemType*)realloc(L->data, (L->capacity + 10) * sizeof(ElemType)); if (!newBase) return 0; L->data = newBase; L->capacity += 10; } /* 插入逻辑与静态顺序表相同 */ }

应用场景

顺序存储结构适合以下场景：

• 数据量相对稳定，查询操作远多于插入/删除操作。
• 需要高频随机访问元素的场景。
• 对存储空间利用率要求较高的环境。

典型应用：

• 操作系统中的进程优先级队列。
• 图像处理中的像素矩阵存储。
• 科学计算中的向量/矩阵实现。

https://raw.githubusercontent.com/ry-cp/eyr_qdv0/main/README.md
https://github.com/cbar1239/27m_76a1
https://github.com/cbar1239/27m_76a1/blob/main/README.md
https://raw.githubusercontent.com/cbar1239/27m_76a1/main/README.md
https://github.com/pjongfreemen/zaq_ocya