一、线性表

最基本的数据结构之一
根据线性表的实际存储方式，分为两种实现模型
顺序表、链表

1.1 顺序表

将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示

一个顺序表完整的信息包括两个部分：
(1) 为实现正确的操作而需记录的信息
有关表的整体情况的信息
主要包括元素存储区的容量和当前表中已有的元素个数两项
(2) 表中的元素集合

1.1.1 顺序表的完整信息

1. 顺序表的表头信息

存放顺序表的基本信息

2. 顺序表的元素信息

基本形式：

相同数据元素类型的列表
元素内置

不相同的数据元素类型的列表
元素外置

物理地址 = 起始物理地址 + 逻辑地址*偏移量

1.1.2 顺序表的两种基本实现方式

结构描述

一体式结构元素存储区替换

分离式结构支持元素存储区扩充的顺序表称为动态顺序表

扩充策略：

1. 每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略称为线性增长——特点：节省空间，但是扩充操作频繁，操作次数多

2. 每次扩充容量加倍，如每次扩充增加一倍的存储空间——特点：减少了扩充操作的执行次数，但是会浪费空间资源，以空间换时间推荐

结构	描述
一体式结构	元素存储区替换
分离式结构	支持元素存储区扩充的顺序表称为动态顺序表扩充策略： 1. 每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略称为线性增长——特点：节省空间，但是扩充操作频繁，操作次数多 2. 每次扩充容量加倍，如每次扩充增加一倍的存储空间——特点：减少了扩充操作的执行次数，但是会浪费空间资源，以空间换时间`推荐`