数据结构之数组

# 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15