---
title: 顺序表
date: 2024-06-06T23:50:41Z
tags: []
---

## 储存结构

逻辑上相邻的数据元素物理上也相邻

## 实现方式

### 静态分配

1. 使用静态数据实现
2. 大小一旦确定就无法改变

### 动态分配

1. 使用"动态数组"实现
2. 用 malloc 实现
3. 顺序表存满时,可以再用 malloc 动态扩展顺序表的最大容量
4. 将元素复制到新的储存区域,并用 free 释放原区域

## 特点

1. 随机访问
   能在 O(1)时间内找到第 i 个元素
2. 存储密度高
3. 扩容不方便
4. 插入,删除元素数据不方便

## 基本操作

### 插入

1. 插入元素应该往后移
2. 时间复杂度
   最好 O(1)
   最坏 O(n)
   平均 O(n)

### 删除

1. 删除位置之后的位置都要往后移
2. 时间复杂度
   最好 O(1)
   最坏 O(n)
   平均 O(n)

### 代码要点

1. 注意位序 i 和数组下标的区别
2. 算法要有健壮性,注意判断 i 的合法性

## 按位查找

1. 查找表中某一个位置的元素值
   用数组下标
2. 时间复杂度
   最好/最坏/平均时间复杂度都是 O(1)

## 按照值查找

1. 查找某一个值
   从第一个元素依次往后检索
2. 时间复杂度
   - 最好 O(1):目标元素在第一个位置
   - 最坏 O(n):目标元素在最后一个位置
   - 平均 O(n):目标元素在每一个位置概率都相同
