数据结构&&算法 面经

常用数据结构的相关知识

1、数组：最基本的数据结构，用连续内存存储数字。创建数组时，我们需要首先指定数组的容量大小，然后根据大小分配内存。即使我们只在数组中存储一个数字，也需要为所有的数据预先分配内存。因此数组的空间效率不是很好，经常会有空闲的区域没有得到充分的利用。(可动态分配内存来解决上述问题)由于数组中的内存是连续的，于是可以根据数组下标O(1)时间读/写任何元素，因此它的时间效率是很高的。

2、字符串：最基本的数据结构，用连续内存存储字符。C/C++中每个字符串都以字符’\0’作为结尾，这样我们就能很方便地找到字符串的最后尾部。

3、链表：链表的结构很简单，由指针把若干个节点连接成链状结构，并且链表是一种动态的数据结构，其需要对指针进行操作，因此链表很灵活。在创建链表时，我们无须知到链表的长度。当插入一个节点时，我们只需要为新节点分配内存，然后调整指针的指向来确保新节点被链接到链表中。内存分配不是在创建链表时一次性完成的，而是每添加一个节点分配一次内存。由于没有闲置的内存，链表的空间效率比数组高。

4、树：除根节点之外每个节点只有一个父节点，根节点没有父节点;除叶节点之外所有节点都有一个或多个子节点，叶节点没有子节点。父节点和子节点之间用指针链接。二叉树：是树的一种特殊结构，在二叉树中每个节点最多只能有两个子节点。二叉搜索树：左子节点总是小于或者等于根节点，而右子节点总是大于或者等于根节点。我么可以平均在O(logn)的时间内根据数值在二叉搜索树中找到一个结点。堆：分为最大堆和最小堆。在最大堆中根节点的值最大，在最小堆中根节点的值最小。

5、栈：栈是一个与递归紧密相关的数据结构，它在计算机领域被广泛应用，比如操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址及临时变量等。栈的特点是先进后出，即最后被压入(push)栈的元素会第一个被弹出(pop)。通常栈是一个不考虑排序的数据结构，我们需要O(n)时间才能找到栈中的最大值或最小值。

6、队列：队列与广度优先遍历算法紧密相关，队列的特点是先进先出。

不同排序算法的异同？