常见数据结构

数据结构

数据结构一直是面试重点，大多数面试都是围绕着数组、字符串、链表、树、栈和队列这几种常见的数据结构展开的，需要熟练的掌握这几种数据结构

数组和字符串是两种基本的数据结构，它们用连续内存分别存储数字和字符
链表和树是面试中出现频率最高的数据结构，操作链表和树需要操作大量的指针，在解决相关问题时要注意代码的鲁棒性，防止出现程序崩溃的问题
栈是一个与递归紧密相关的数据结构
队列与广度优先遍历算法紧密相关

数组

数组可以说是最简单的一种数据结构，数组占据一块连续的内存并按照顺序存储数据

创建数组时，需要先指定数组的容量大小，根据大小分配内存

即使只在数组中存储一个数字，也需要为所有的数据预先分配内存，因此数组的空间效率不是很好，经常有空闲的区域没有得到充分利用
由于数组中的内存是连续的，可以根据下标在 O(1) 时间读/写任何元素，因此它的时间效率很高

可以根据数组时间效率高的优点，实现简单的哈希表

把数组的下标设为哈希表的键值 Key ，数组中的每一个数字设为哈希表的值 Value ，这样每一个下标及对应的数字就组成了一个 “键值-值” 的配对
有了这样的哈希表，就能在 O(1) 时间内实现查找

为了解决数组空间效率不高的问题，人们又设计实现了多种动态数组，例如 C++ 的 STL 中的 vector

为了避免浪费，先为数组开辟较小的空间，然后再往数组中添加数据，当数据的数目超过数组的容量时，再重新分配一块更大的空间，把之前的数据复制到新的数组中，再把之前的内存释放

STL 中的 vector 每次扩充容量时，新的容量都是前一次的两倍
每一次扩充容量时都有大量的额外操作，对时间效率有负面的影响，因此使用动态数组的时候应该尽量减少改变数组容量大小的次数

在 C/C++ 中，数组和指针是既相互关联又有区别的两个概念 当我们声明一个数组时，其数组的名字也是一个指针，该指针指向数组的第一个元素，我们可以使用一个指针来访问数组

值得注意的是，C/C++ 没有记录数组的大小，在用指针访问数组中的元素时，要确保没有超出数组的边界
通过一个例子来了解数组和指针的区别

运行下面的代码，请问输出什么

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

int _tmain(int argc, _TCHAR *argv[]){
    int data1[] = {1, 2, 3, 4, 5};
    int size1 = sizeof(data1);

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

    int size3 = getSize(data1);

    printf("%d, %d, %d", size1, size2, size3);
}

答案输出是 "20, 4, 4"

sizeof(data1) 是求数组的大小，这个数组包含5个整数，每个整数占4个字节，因此共占用20字节
data2 是一指针，虽然它指向数组 data1 的第一个数字，但本质仍是一个指针，在32位系统上，对任意指针求 sizeof 结果都是4
在 C/C++ 中，当数组作为函数的参数进行传递时，会自动退化成同类型的指针，所以 size3 的结果为4

数据结构​

数组​

数据结构

数组