一、基本概念

1. 什么是数据结构

简单地说，数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。首先我们需要理解各种数据结构，才能在处理实际问题时选取最合适的数据结构。

2. 数据结构三要素

逻辑结构：数据元素之间的逻辑关系

• 线性结构（一对一关系）：线性表、栈、队列
• 非线性结构（一对多关系）：树、图、集合

存储结构（物理结构）：数据结构在计算机中的表示，是用计算机语言实现的逻辑结构

• 顺序存储
• 链式存储
• 索引存储
• 散列存储

数据的运算：施加在数据上的运算，包括运算的定义和实现。运算的定义针对逻辑结构，运算的实现针对存储结构。

3. 什么是算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列。

算法的5个重要特性：

• 有穷性：一个算法必须在执行有穷步之后结束，且每一步都在有限时间内完成
• 确定性：算法中的每条指令必须有确切的含义，不会产生二义性
• 可行性：算法中描述的操作都是通过已经实现的基本运算执行有限次来实现的
• 输入：一个算法有零个或多个输入（可以没有输入）
• 输出：一个算法有一个或多个输出（至少存在一个输出）

4. 算法效率的度量

• 时间复杂度

  一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为 T(n)，n 表示问题的规模，T(n) 是问题规模的函数。时间复杂度 = T(n) 的数量级

• 空间复杂度

  该算法耗费的存储空间

5. 数据结构和算法之间的关系

算法是对特定问题的求解步骤，在计算机中表现为指令的有穷序列。

算法 + 数据结构 = 程序。

算法只有在合适的数据结构中才能发挥作用，数据结构的不同，会影响算法的选择和效率。

二、线性表

1. 数组/顺序表和链表的区别

从逻辑结构上来看

• 数组必须实现定于固定的长度，不能适应数据动态增减的情况，即数组的大小一旦定义就不能改变。当数据增加是，可能超过原先定义的元素的个数；当数据减少时，造成内存浪费

• 链表动态进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。

从内存存储的角度看

• 数组从栈中分配空间（用new则在堆上创建），对程序员方便快速，但是自由度小；
• 链表从堆中分配空间，自由度大但是申请管理比较麻烦。

从访问方式类看

• 数组在内存中是连续的存储，逻辑上相邻，物理位置也相邻，因此可以实现随机存取，利用下标索引进行访问；
• 链表是链式存储结构，在访问元素时候只能够通过线性方式由前到后顺序的访问，所以访问效率比数组要低。

2. 相关算法题

• 顺序表相关算法
• 链表相关算法

三、栈和队列

1. 栈和队列的区别

• 队列先进先出，栈先进后出。

• 对插入和删除操作的”限定”不同。

  栈是限定只能在表的同一端进行插入和删除操作的线性表。

  队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。

• 遍历数据速度不同。

  栈只能从头部取数据，也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性。

  队列则不同，它基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多

2. 什么是队列的假上溢现象，如何解决

队列从队尾入队，从队头出队。

每次出队队头指针+1，当队头指针 = maxnum 时，出现假溢出现象。即队列中尚有足够的空间，但元素确不能入队。

解决方法：

• 建立一个足够大的存储空间以避免溢出，但这样做空间使用率低，浪费存储空间
• 移动元素：每当出队一个元素，就将移动队列中所有的已有元素向队头移动一个位置
• 循环队列：将队头和队尾看作是一个首尾相接的循环队列

3. 循环队列的优缺点

• 循环队列的优点：

  可以有效的利用资源。用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的；循环队列也是一种数组，只是它在逻辑上把数组的头和尾相连，形成循环队列，当数组尾满的时候，要判断数组头是否为空，不为空继续存放数据。

• 循环队列的缺点：

  循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front == rear来判别队列是”空”是”满”。

  解决这个问题有两个办法：

  • 增加一个参数，用来记录数组中当前元素的个数；
  • 第二个办法是，少用一个存储空间，也就是数组的最后一个存数空间不用，当（rear+1）%maxsize=front 时，队列满

  这也就是为什么循环队列的顺序表中要空一个位置（用来区分队列空和队列满）。

  

4. 堆和栈的区别

首先：讨论的堆和栈是内存中的 堆区 和 栈区，而不是数据结构中的堆和栈

C++中的内存区域分为5个区：堆区、栈区、全局/静态存储区、常量存储区、代码程序区

• 栈（stack）：存放函数的参数值、局部变量等，由编译器自动分配和释放，通常在函数执行完后就释放了，其操作方式类似于数据结构中的栈。栈内存分配运算内置于CPU的指令集，效率很高，但是分配的内存量有限。

• 堆（heap）：由程序员控制内存的分配和释放的存储区，是不连续的存储空间，堆的分配(new)和释放(delete)有程序员控制，容易造成二次删除和内存泄漏，堆的分配方式类似于链表

  1 2 3

  void fun(){ int *p = new int[5]; }

  在上述代码中就包含了堆和栈，看到new，我们就知道分配了一块堆内存，那么指针p呢，它分配的是一块栈内存。即在栈内存中存放了一个指向一块堆内存的指针p

• 静态存储区（static）：存放全局变量和静态变量的存储区，初始化的变量放在初始化区，未初始化的变量放在未初始化区。在程序结束后释放这块空间

• 常量存储区（const）：存放常量字符串的存储区，只能读不能写

• 程序代码区：存放源程序二进制代码

了解上述知识后我们再来明确堆和栈的区别：

四、树

1. 二叉树的存储方式

• 顺序存储结构：

  用一个数组来存储一颗二叉树，二叉树中的结点值按照编号依次存入一个一维数组中。 适用于完全二叉树，若用于一般的二叉树则会浪 费大量 存储空间。

• 链式存储结构：

  二叉树中的每一个结点用一个链结点来存放，拥有左右孩子结点

  

2. 什么是堆？有什么作用？

定义：

堆是一种数据结构，可以把堆看成一个完全二叉树，并且这个完全二叉树满足： 任何一个非叶节点的值都不大于（或不小于）其左右子树的结点的值。若父亲大孩子小，则为大顶堆，若 父亲小孩子大，则为小顶堆。

作用：

应用于堆排序

3. 完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

4. 完全二叉树的判定

思路： 完全二叉树的结点编码是连续的，根据层次遍历，把所有结点依次入队，包括空结点，若空结点之后还有非空结点，就不是完全二叉树

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

bool isComplete(BiTree T){
    if(!T)
        return true;
    InitQueue(Q);
    BiTNode *p = T;
    EnQueue(Q,T);
    while(!isEmpty(Q)){
        DeQueue(Q,p);
        if(p){
            EnQueue(Q,p->lchild);
            EnQueue(Q,p->rchild);
        }
        else{
            while(!isEmpty(Q)){
                DeQueue(Q,p);
                if(p)
                    return false;
            }
        }
    }
    return true;
}

5. 二叉排序树 BST

定义：

二叉排序树又称二叉搜索树，它或者是一颗空树，或者满足一下性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于根节点的值；

• 若右子树不空，则右子树上所有结点的值均大于根节点的值；

• 左右子树也分别是二叉排序树。

查找过程：

• 若根结点的关键字值等于查找的关键字，成功。
• 否则，若小于根结点的关键字值，递归查左子树。
• 若大于根结点的关键字值，递归查右子树。
• 若子树为空，查找不成功。

6. 二叉排序树的判定

思路：二叉排序树的中序遍历序列一定为递增序列

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

//利用中序遍历为递增
bool isBST(BiTree T){
    if(T==NULL)
        return true;
    else{
        bool bl = isBST(T->lchild);
        if(bl==false || pre>T->data)
            return false;
        pre = T->data;
        bool br = isBST(T->rchild);
        return br;
    }
}

7. 平衡二叉树 AVL

定义：平衡二叉树又称AVL树，是一种特殊的二叉排序树，其左右子树都是平衡二叉树，且左右子树的高度差的 绝对值不超过1.

平衡因子： 左子树高度减去右子树高度的差。

平衡调整： 先找到失去平衡的最小子树，即以距离插入结点最近，且平衡因子绝对值大于 1 的结点作为为根节点的子树，分为LL,LR,RL,RR四种调节方式。

8. 平衡二叉树的判定

思路：平衡二叉树的每一个结点都是平衡的，利用后序遍历按照左右根的次序依次判断是否平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int isAVL(BiTree T,int &h,int &balance){
    int bl,br,hl,hr; //左右子树的高度和平衡性
    if(T==NULL){
        balance = 1;
        h = 0;
    }
    else if(!T->lchild && !T->rchild){ //左右孩子均不存在
        balance = 1;
        h = 1;
    }
    else{
        isAVL(T->lchild,hl,bl); //判定左子树
        isAVL(T->rchild,hr,br); //判定右子树
        h = hl>hr?hl:hr;
        if(bl&&br && abs(hl-hr)<2) //若左右子树均平衡且高度差小于等于1
            balance = 1;
        else
            balance = 0;
    }
}

9. 哈夫曼树（最优二叉树）

定义：

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

构造方法：

假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设为 w1、w2、…、wn，则哈夫 曼树的构造规则为：

• 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

• 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其 左、右子树根结点权值之和；

• 从森林中删除选取的两棵树，并将新树加入森林；

• 重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

特点：

• 权值越大的结点，距离根节点越近；

• 树中没有度为一的结点。

应用：

哈夫曼编码，减少编码的长度。哈夫曼编码就是长度最短的前缀编码

五、图

1. 图的相关概念

• 图：由结点的有穷集合V和边的集合E组成。

• 类别：有向图和无向图。

• 顶点的度：出度和入度。

• 有向完全图和无向完全图：

  若有向图有n个顶点，则最多有 n(n-1) 条边，则称为有向完全图

  无向图有n个顶点，则最多有 n(n-1)/2 条边，则称为无向完全图。

• 路径：相邻顶点序偶所构成的序列。

• 简单路径：序列中的顶点不重复出现的路径。

• 回路：路径中第一个顶点和最后一个顶点相同的路径。

• 连通：

  无向图中，如果Vi到Vj有路径，则称这两个顶点连通。如果图中任意两个顶点之间都连通，则称该图为连通图。

  有向图中，如果 Vi 到 Vj 有路径，且反过来 Vj 到 Vi 也有路径，则称这两个顶点强连通。如果图中每一对顶点 Vi 和 Vj，从 Vi到 Vj 和 Vj 到 Vi 都有路径，则称该图为强连通图。

2. 图的存储方式

• 邻接矩阵：是图的顺序存储结构，用两个数组分别存储数据元素（顶点）信息和数据元素之间的关系（边/弧）的信息。一维数组存储顶点集，二维数组存储边集。图的邻接矩阵表示是唯一的，无向图的邻接矩阵是对称 的。
• 邻接表：是图的链式存储结构，一个单链表表示该顶点的边表；各个单链表的头指针和顶点采用顺序存储连接起来表示顶点表
• 十字链表：有向图的另一种链式存储结构。
• 邻接多重表：无向图的链式存储结构。

3. 邻接矩阵和邻接表对比

4. 深度优先搜索遍历和广度优先搜索遍历的过程

BFS: 类似于层次遍历

基本思想 ：利用 队列 实现。

• 首先访问起始顶点 V 并将其入队
• V出队，并遍历V的所有邻接点 w1，w2，….，wn并依次入队
• w1出队，并遍历 w1 的全部邻接点(不包括已经被访问的点)
• w2出队，并遍历w2的全部邻接点(不包括已经被访问的点)
• ……. 以此类推

DFS: 类似于先序遍历

基本思想：利用 递归/栈 实现。当不能继续向下访问时，依次回退到最近的被访问结点

• 首先访问顶点V，并将其标记为已访问
• 然后访问与顶点V的其中一个未被访问的邻接点W，并将其标记为已访问
• 再访问W的其中一个未被访问的邻接点，并将其标记为已访问
• 依次类推….. 当一个顶点所有的邻接顶点都被访问过时，则依次退回最近被访问过的顶点

图的深度遍历是否唯一

不一定唯一。因为我们可以取图中任一顶点进行深度遍历。

5. 最小生成树及相关算法

最小生成树的定义：

一个包含原图中所有结点的连通图的生成树就是原图的极小连通子图，并且拥有保持图连通的最少的边。如果在最小生成树中添加一条边，必定成一个环。

N个结点的最小生成树有 N 个结点，N-1 条边。

相关算法：

• Prim 算法

  每次都在互相连通的基础上选取相对最小的边。需保证无环

• Kruscal 算法

  每次选取最小的边，无须保证此过程是否连通。需保证无环

5. 最短路径及相关算法

① Dijkstra 算法

该算法可以求得某一顶点到其余各顶点的最短路径。

算法思想：

• 设有两个顶点集合 S 和 T，其中集合 S 中存放的是图中已找到最短路径的顶点，集合 T 中存放 的是图中的剩余顶点。

• 初始状态时，集合 S 中只包含源点 V0，然后不断从集合 T 中选取到顶点 V0 路径最短的顶点 Vu 并加入集合 S 中，之后的路径可通过该结点

• 集合 S 每加入一个新的顶点 Vu，都要修改 V0 到集合 T 中各个顶点的最短路径的长度值。

• 不断重 复这个过程，直至集合T中的顶点全部并入到 S 中为止。

  

② Floyd算法

每次都试图在路径上添加新的中间结点

7. 拓扑排序

什么图可以进行拓扑排序？ 有向无环图

基本思想 ：每次去除一个入度为0的结点和该与顶结点相连的边

若图中存在一条A——>B的路径，则在拓扑排序中表示B事件在A事件的后面

六、查找

1. 总览

• 顺序结构
  • 顺序查找
  • 折半查找：仅适用于有序的顺序表
  • 分块查找：索引顺序查找
• 树形结构
  • 二叉排序树
  • 平衡二叉树
  • B / B+ 树
  • 红黑树
• 散列结构
  • 散列表
• 字符串模式匹配
  • KMP 算法

1. 常见的哈希函数构造方法

• 直接定址法

  H(key) = a*key + b

• 数字分析法

• 平方取中法

• 除留余数法

  H(key) = key % p (p为不大于m的最大质数)

2. 什么是哈希冲突？处理冲突的方法

散列（哈希）表： 根据关键码值(Key value)而直接进行访问的数据结构。根据给定的关键字来计算出关键字在表中的地址，以加快查找的速度。

哈希冲突：指的是多个关键字映射同一个地址的情况。

解决办法：

• 开放定址法

  • ① 线性探查法（产生堆积问题）：冲突发生时顺序查找下一个位置
  • ② 平方探查法（不能探查到哈希表上所有的地址，但至少能探查到一半的地址）

• 链地址法

  所有的同义词都存储在一个线性链表中。

3. KMP 算法

在一个字符串中查找是否包含目标的匹配字符串。其主要思想是每趟比较过程让子串先后滑动一个合适的位置。当发生不匹配的情况时，不是右移一位，而是移动（当前匹配的长度– 当前匹配子串的部分匹配值）位。使用一个next数组维护每个字符对应的移动位数。

4. M阶B树和M阶B+树的主要区别

B/B+树一种平衡的多路查找树，一般被用在文件系统（我们常说的B树其实是叫 B- 树）

下图为 B+ 树

七、排序

1. 排序算法总览

① 插入排序：O(n^2)

• 直接插入 稳定

  边查边移动。把待排序的记录按照关键字的大小逐个插入到已经排好序的有序序列中，直到所有的记录都插入完为止

  

• 折半插入 稳定

  先查后移。将直接插入排序中 寻找待排记录在有序序列中的位置的方法 改为采用折半查找。

  仅仅减少了查找排序的比较次数，元素的移动次数并未改变

• 希尔排序 不稳定

  又称缩小增量排序。把记录按照下标的一定增量进行分组，对每组使用直接插入排序算法进行排序。

  随着增量的减少，每组包含的关键字越来越多，当增量减为 1 时，整个序列被分为一组，算法便终止。

② 交换排序

• 冒泡排序 O(n^2) 稳定

  从前往后（从后往前）两两比较相邻的元素，若为逆序，则交换，直到序列比较完，最小（大）的元素浮现在末端（顶端）称为一组冒泡。

  下一趟冒泡时，前一趟已经确定的最小（大）元素不再参加冒泡排序，待排序列减少一个元素。

  

  冒泡排序在数列有序时最快，数列反序时最慢

• 快速排序 O(nlog2n) 不稳定

  1）从数列中选取一个元素作为基准 pivot，一般选取第一个元素；

  2）重新排序，比基准小的数都在基准的前面，比基准大的数都在基准的后面。一趟排序完成后，这个基准元素就位于他的最终位置了；

  3）然后对基准前面子序列和后面子序列使用相同地方法进行递归排序，每趟排序都能确定一个元素的最终位置。

  

③ 选择排序：不稳定

• 简单选择 O(n^2)

  每次排序都从未排序列中选取最小元素放在相应位置，第 i 次排序即从 i - n 中选取最小元素与 A[i] 交换，一共循环 i - 1 次。

  每次排序后数列都是局部有序的。

  

  选择排序是最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

• 堆排序 O(nlog2n)

  1）构造堆：将无序序列构建成一个堆，根据升序降序需求决定转换成大根堆还是小根堆。（从最后一个非叶结点开始，调整该结点和他的孩子结点，然后依次从下往上进行调整，直到这个堆的父结点都大（小）于它们的孩子结点）；

  2）堆排序：将堆顶元素和最后一个叶子结点进行交换，将最大（小）元素沉到数组末端，然后重新构造堆。重复这个过程直到整个序列有序

  

④ 归并排序：O(nlog2n) 稳定

归并的含义是将两个或两个以上的有序表合并成一个新的有序表

和选择排序一样，归并排序不受输入数据的影响，时间复杂度始终是 O(nlog2n)

⑤ 基数排序：稳定

基数排序可用于比较整数。原理是将整数按照位数切割成不同的数字，然后按每个位数分别进行比较（个位数和个位数比较，十位数和十位数比较）

2. 各类排序算法对比

3. 如何选择排序算法

选择排序算法准则：

一般而言，需要考虑的因素有以下四点：

设待排序元素的个数为n.

• 当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

• 当n较大，内存空间允许，且要求稳定性：归并排序

• 当n较小，可采用直接插入或直接选择排序。

  直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。

  简单选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序

• 一般不使用或不直接使用传统的冒泡排序。

• 基数排序：它是一种稳定的排序算法，但有一定的局限性

  • 关键字可分解。
  • 记录的关键字位数较少，如果密集更好
  • 如果是数字时，最好是无符号的

4. 冒泡排序算法的改进

设置一个 flag 位，用于标识这趟排序有没有发生交换，如果本趟遍历后没有发生交换，则说明元素已经有序了，则退出排序过程。

5. 快排、堆排、归并排序对比

• 时间复杂度：这三个排序算法平均时间复杂度都是O(nlog2n)，快排在数据有序的情况下最坏时间复杂度可达到O(n^2)

• 空间复杂度：归并排序需要额外的数组开销，因为需要一个辅助数组对数据进行归并排序

• 稳定性：快排和堆排是不稳定的，归并排序稳定

6. 堆和二叉排序树的区别

堆的特点是双亲结点的关键字必然大于（小于）该孩子结点的关键字，但这两个孩子结点的关键字没有次序规定。

中序遍历二叉树得到的结果为有序序列，而堆不一定能得到一个有序的序列。

7. 排序相关算法题

• 排序的相关算法