数据结构数组和字符串 – Fictional Oblivion Scape

1. 数组、列表和集合的区别

集合

由一个或多个确定的元素所构成的整体

集合的特性：

集合内的元素不一定相同
集合是无序的

列表

列表是一种有顺序的长度可变的集合

列表的特性：

列表是有序的
列表的长度是可变的
列表的元素地址是可以不连续的（链表）

数组

数组是列表的一种实现方式

数组的特性：

数组具有索引，用来标记数据数组中的位置
数组在内存中数据是连续的，且每个元素占相同大小的内存

2. 数组的操作

数据在内存中分散分布，而数组在内存中是连续的。在创建数组时，计算机会为数组申请一段连续的空间，并且记录下第一个元素空间的内存地址（假设为114514，且数组元素大小为1）作为数组的位置，那么当需要查询数组中第5个元素时计算机会进行以下操作：寻找到数组的位置（114514），在114514的基础上+5，就得到了第5个元素的位置，读取（114514+5）这个地址内的值。

Tips：在32位的CPU中（不考虑地址加法器），CPU的寻址范围是（0~2^32-1），内存的每一个格子是一个字节（Byte），因此CPU最多可以查询2^32个格子的内存，2^32 * 1Byte ≈ 4 GigaByte，因此最大支持4GB的内存。需要注意的是，上面的例子中为了方便把数组元素大小设为1，而在实际上，例如在C++中，int型的数组元素大小为32bit（4Byte），因此每一个元素占4个Byte，在内存中实际上占四个格子，也就是说每次遍历元素的时候，地址需要+4。

int main() {
    int arr[5];
    std::cout<<arr<<"\n";
    std::cout<<&arr[1]<<"\n";
    std::cout<<&arr[2]<<"\n";
    std::cout<<&arr[3]<<"\n";
    std::cout<<&arr[4]<<"\n";
    return 0;
}

在以上的C++程序中，创建了一个大小为5的int类型的数组，C++中int数组默认为4字节。然后打印出数组中每个元素的地址：

0x6d3cfffa40
0x6d3cfffa44
0x6d3cfffa48
0x6d3cfffa4c
0x6d3cfffa50

可以看到地址是连续的十六进制，且每个元素之间的地址相差4个位置，也就是4个字节。

读取元素

一旦知道了数组的第一个元素的地址，很快就可以通过加法得出所需要访问的元素的地址，因此获取地址的时时间复杂度是常数级O(1)。

查找元素

而在数组中寻找一个元素，则需要遍历，从一侧元素遍历到另一侧，最坏的情况是遍历n个元素，因此查询元素值的时间复杂度是O(n)。

插入元素

由于数组是连续的，当需要插入一个元素时（不包括插入到两侧），需要将插入的位置后面的原有的元素全部后移一位，因此数组的插入是十分浪费时间的。

删除元素

删除元素和插入元素相似，当在连续的数组中删除一个元素时（不包括删除两侧的元素），需要将被删除的后面的元素全部前移一位。

3. 二维数组

二维数组是一种特殊的数组，它将一维数组中的每一个元素都变成了一个数组。但是二维数组本质上还是一个一维数组，只是在逻辑上是二维的，形如矩阵。同样二维数组的第一行第一个的地址A[0][0]的地址被用来作为二维数组的地址。

4. 字符串

字符串的基本操作对象是字符串的整体或字串

通常字符串会整体或者分块操作，而不是将字符串中的每一个元素单独操作，提高了字符操作的便利性。

比较函数

在不同语言中，字符串有不同的比较方法，在C++、Python中可以使用 ”==“进行比较，但是在Java中无法使用”==“，实际上只会去比较两个对象是否是一个对象。