数据结构之数组

# 1 数组

数组空间效率不高，需要预先分配内存，且经常会有空闲区域得不到利用。

数组时间效率较高，根据下标可以在 O(1) 时间内完成读写。

可以利用数组时间效率高的特点来实现简单的哈希表。

为了解决数组空间效率不高的问题，有人设计了动态数组，当数据数目超过容量时，扩容，把数据复制到新内存并释放之前的内存，但这会影响时间效率，因此使用动态数组时应尽量减少改变数组容量的次数。

指针与数组：

• 数组名是指针，指针指向数组的第一个元素。
• C/C++ 中不不记录数组大小，程序员要自行确保访问没有越界。
• C/C++ 中数组作为函数参数传递时，自动退化为同类型指针。

下面是一个代码示例，用以说明指针与数组的特性。

int getSize(int data[])
{
    return sizeof(data);
}

int main()
{
    int data1[] = {1, 2, 3, 4, 5};
    int size1 = sizeof(data1);  // size1 = 20

    int* data2 = data1;
    int size2 = sizeof(data2);  // size2 = 4

    int size3 = getSize(data1); // size3 = 4
}