数组

本部分将述数组的基本概念以及数组的使用、数组的内存结构、动态数组的实现等内容。在大部分的数据结构教材中对数组是没有单独章节来讲述的。并且需要注意的是，数组与线性表（也称顺序表或有序表）并不是一回事。我们可以说线性表可以使用数组来实现，但是不能说数组就是线性表。因为有很多线性表的特性，数组是没有的。关于线性表的 ADT 可以在线性表章节中看到。

一些英文术语对应

• 线性表：Linear List
• 有序表：Ordered List
• 顺序表：Sequential List

如果熟悉 C/C++，学习数组时，建议用其中一门语言来练习。因为通过数组与指针的关系能够更加深刻的体会到数组在内存中的结构。Java 中的数组不够纯粹，在 Java 中，数组是一个对象，除了有元素信息外，还有其他附加的信息，如数组的长度，对象头等内容。而 C/C++ 数组变量（实际是一个指针）是直接指向数组内存的。

---

📄️ 数组概述

数组（Array）是一种线性数据结构，它由相同类型的元素按顺序排列组成。每个元素在数组中占据一个固定的位置，这些位置由索引（也称为下标）标识。数组的索引通常从零开始，这意味着第一个元素的索引是 $0$，第二个元素的索引是 $1$，以此类推。

📄️ 动态数组及其实现

动态数组或者叫可变长数组（Variable-Length Array, VLA），有两种解释。