1、数据结构和算法是什么

• 数据结构是指数据在计算机内存空间或者磁盘中的组织形式

• 正确的选择数据结构可以提升程序的效率

• 数据结构包含 数、链表、栈等

• 算法是完成特定任务的过程，经常通过类的方法来实现

2、数据结构-数组

• 无序数组插入快，但是查找和删除慢

• 有序数组可以采用二分查找提升查询效率

3、数据结构-栈和队列

• 栈、队列和优先级队列，经常用来优化某些程序操作的额数据结构

• 栈和队列只允许一个数据项被访问。栈后进先出，队列先进先出。

• 栈和队列可以基于数组实现循环队列，也可以通过链表实现

4、数据结构-链表

• 链表包含一个linkedlist对象和很多link对象

• 每个link对象都包含一个引用，通常叫next，即指向链表的下一个节点

• 向链表插入数据，需要修改其节点的指向，若队尾插入，只需修改末尾的指向即可，其他位置同理

• 删除节点同上，链表允许重复节点和不允许重复节点，删除方法有些许不同

• 双端链表需要额外维护一个字段，从头节点指向尾节点的引用，所以支持在尾端插入而不遍历整个链表

• 双向链表允许反向遍历，并且允许从表尾删除

• 双向链表中，每个节点都包含了前后两个节点的引用，在插入和删除的时候，需要同步修改前后最多三个节点的引用

• 迭代器是一个引用，这个引用主席昂关联的链表中的链节点

• 可以通过迭代器遍历链表，在选定的节点上执行某些操作

5、数据结构-二叉树

• 树由边链接的节点组成，根是树最顶端的节点，且没有父节点

• 二叉树中，节点最多只有两个子节点

• 二叉搜索树中，根节点左边的节点的关键字均小于它，右边的子节点均大于它

• 树查询、插入、删除的时间复杂度都是O(logN)

• 遍历树是按照某种顺序访问节点，包括先序、中序、后序，其中中序和后续可以唯一确定一棵树

• 树分为平衡树和非平衡树

• 查找节点就是比较节点关键字和目标关键字，根据结果选择走向左侧或者右侧

• 插入节点需要找到新节点的位置，并改变其父节点的指向

• 删除节点很复杂，如果节点不存在子节点，将其父节点置为null即可，如果存在，则需要添加一个从其父节点指向其子节点或者子树的引用，或者从其右节点或者右树指向其左节点或者左树的引用

• 哈夫曼树是二叉树但不是二叉搜索树，用于数据压缩算法，根据权值来排序，权值越高，越接近根节点

6、数据结构-红黑树

• 二叉搜索树的平衡很重要，这影响了查找的效率

• 插入的数据有序，将创建一颗不平衡的树，时间复杂度为O(N)，结构和单向链表类似

• 红黑树遵循红黑规则：

  • 每个节点不是黑色就是红色

  • 根节点总是黑色

  • 如果节点是红色，子节点必定是黑色，节点是黑色，子节点未必是红色

  • 从根节点到叶子节点或者空节点的每条路径，必须包含同样数量的黑色节点

• 每次插入或者删除节点都会校验上述规则，例如将一个节点从黑色改为红色，根据规则3需要将其子节点全部改成黑色

• 红黑树的自平衡需要旋转根节点，需要指定一个节点作为根节点，左旋即将左子节点作为新的根节点，而原来的根节点作为新的根节点的右节点；右旋同理。

• 旋转之后需要在旧根节点添加指向新根节点原来子树或者子节点的引用。

• 旋转往往伴随着颜色改变，这些调整使得树大致平衡

• 在二叉树中引入红黑平衡，增加了内存的开支，因为需要额外的空间存储是否是红色节点，但是对于性能有着不小的提升，能够避免顺序或者逆序插入时最坏的性能

7、数据结构-哈希表

• 哈希表基于数组实现

• 关键字的值一般大于数组的长度，数组的下标由关键字经过哈希函数映射得到

• 不同关键字经过哈希函数映射到同一个下标称为哈希冲突。解决冲突采用开放地址法和链地址法

  • 开放地址中将冲突的关键字放到别的地方。开放地址法包括：线性探测、二次探测、再哈希

    • 线性探测中保持步长为1，当产生哈希冲突时，将一次探寻下一位是否能插入数据。线性探测会产生首次聚集。

    • 二次探测中补偿为探测次数的平方，即第一次下标+1，第二次+4，第三次+9。二次探测会产生二次聚集，消除首次聚集，但总体性能优于线性探测

    • 再哈希性能和二次探测类似，通过多个哈希函数来确定最终位置。第二个哈希函数返回一个值s，冲突时将转向下一个地址即+s，+2s，+3s...

  • 链地址中，每个数组包含一个链表，冲突的函数值将放到同一个链表中

8、数据结构-堆

• 堆是优先级队列ADT的有效实现方式。提供了插入和移除最大数据项的方法，其时间复杂度均为O(logN)

• 堆中最大数据项总是位于根，堆不能遍历所有数据项，堆不能找到特定关键字项，也不能移除特定关键字项

• 堆通常用数组实现，表现为一颗完全二叉树，根节点的下标为0，最后一个节点的下标为N-1，每个节点的关键字都小于他的父节点，大于他的根节点

• 数据的插入，是将插入项放到第一个空节点，再逐步向上筛选，直到找到合适的位置

• 数据的删除，是删除根节点数据，再将最后一个节点的数据放入根节点，再逐步向下筛选，直到找到合适的位置

• 向上和向下筛选是一系列的交换

• 堆也可以基于二叉树，映射的堆称为树堆

• 堆排序的时间复杂度为O(N*logN)，概念上堆排序是先将无序数组插入到堆中，再遍历删除元素，可以使用同一个数组来存放，初始无序数组、堆、有序数组，所以不需要额外空间

9、数据结构-图

• 图包含由边连接的顶点，有向图中，边有方向

• 图能够表示很多现实世界的情况，例如飞机航线、电子线路、工作调度等

• 搜索算法以一种系统的方式，访问图的每一个顶点，搜索是其他行为的基础

• 两个主要的搜索算法，深度优先(DFS)、广度优先(BFS)

  • DFS通过栈实现，BFS通过队列实现

• 最小生成树MST包含连接图中所有顶点需要的最少数量的边，在不带权的图中，通过修改深度优先算法，可以生成其最小生成树

• 拓扑排序算法，创建一个定点排列列表：如果有一条从A到B的边，那么在列表中顶点A在顶点B前面

• 拓扑排序只能在DAG中执行，DAG表示有向无环图，拓扑排序的典型应用是复杂项目的调度，包含了任务和任务之间的前后关系

• Warshall算法能找到任意顶点和另外的顶点之间是否有连接，不管是一步到达还是任意步到达

• 带权图中，边带有一个数字，叫做权，可以是距离、价格等意义

• 带权图得做小生成树中包含所有顶点和连接他们必要的边，且这些边的权值之和最小

• 优先级队列的算法可以用来寻找带权图中的最小生成树

10、算法-排序算法

• 排序算法包括比较数组中数据项的关键字和移动相应的数据项，直到排好顺序为止

• 不变性是算法运行过程中保持不变的条件

• 稳定性是指相同关键字的顺序，在经历了排序后相对顺序不发生变化，即排序是稳定的

• 简单算法

  • 冒泡排序利用循环将大(小)的关键字逐步上升到头部，其时间复杂度为O(N²)

  • 选择排序利用循环每次选取关键字中最大(小)的和”头部“关键字交换，这里的头部是除去最左侧已经排序的部分，最终实现排序，时间复杂度也是O(N²)

  • 插入排序是利用循环从第二位关键字开始依次与前面所有关键字相比，直到到达正确位置，时间复杂度也是O(N^2)

• 复杂算法

  • 希尔排序是将增量应用到插入排序，然后逐渐缩小增量

    • n-增量排序表示间隔n个元素排序

    • 间隔序列或间距序列决定了希尔排序的排序间隔

    • 希尔排序的间隔序列通过h=3h+1计算得，初始h=1

    • 希尔排序的时间复杂度大致是O(N*(log₂N)²)，优于插入，慢于快排

  • 划分数组是将数组分为两个子数组，一组关键字均小于某个关键字，另一组均大于某个关键字

    • 划分数组的思想是通过两个循环+两个指针，核心是比较并交换，和特定关键字比较，和另一个数组的关键字交换

    • 划分数组的一个应用就是快速排序

    • 快速排序是对一个数组多次应用划分算法，这个过程可以用递归实现，递归的退出条件是数组只有一个关键字，或者当数组容量小于一定值时通过插入排序实现有序也是可行的

    • 划分的过程中，特定关键字是作为子数组的边界，不归属于任何子数组

    • 快速排序对于已经有序的数组时间复杂度是O(N²)

  • 基数排序

    • 基数排序是对所有数高位补零，然后从低位到高位依次排序，每次排序不改变原有的相对顺序，最终就能实现排序

    • 基数排序的时间复杂度和快排一样，都是O(N*logN)

    • 具体的实现可以通过维护一个队列，在遍历数组时，将符合条件的插入对应的队列中，再通过pop向临另一个数组添加数据

    • 基数排序的一个缺点是需要两倍的空间来存放排序过程中的数组