写在前面：

本博客基于学校提供的教材书《数据结构——Java语言描述（第2版）》编写。原意是用于学校期末考的复习整理，也希望能对大家有所帮助！

此次整理是针对学校给出的考点，而不是针对数据结构整个课程的知识点整理。

博客中的页码为教材相关内容的对应页码。图片为原书的照片，代码基本为书上的原版代码，仅供参考。

一、填空题

度数与边数的关系

无向图和有向图

判空判满

连通图的点与边的关系

等等

二、程序填空

2.1 顺序表插入运算

public void insert(int i, Object x) throws Exception {if (curLen == listElem.length) {// 顺序表已满throw new Eception("顺序表已满");}if (i < 0 || i > curLen) {throw new Exception("插入位置不合法");}for (int j = curLen; j>i; j--) {// 元素后移listElem[j] = listElem[j - 1];}// 插入listElem[i] = x;curLen++;}

2.2 统计二叉树中结点个数

public int countNode(BiTreeNode tree) {int count = 0;if (tree != null) {LinkQuene quene = new LinkQuene();// 根结点入队quene.offer(tree);while (!L.isEmpty()) {tree = (BiTreeNode) quene.poll();count++;if (T.lchild != null) {quene.offer(tree.lchild);}if (T.rchild != null) {quene.offer(tree.rchild);}}}return count;}

2.3 顺序查找

public int seqSearch(Comparable key) {int i = 0, n = length();while (i<n && r[i].pareTo(key)!=0) {i++;}// 如果找到了那么会在i<n停下if (i < n) {return i;} else {// 如果一直找不到，那么最后会i>=n而退出循环return -1;}}

2.4 堆排序调整堆算法

public void sift(int low, int high) {int i = low;int j = 2 * i + 1;Record temp = r[i];while (j < high) {// 如果右子结点小于左子结点，则对右子结点进行操作// 升序大顶堆，降序小顶堆。此处为小顶堆，小的在上大的在下if (j < high - 1 && r[j].pareTo(r[j + 1].key > 0)) {// j++换到右子结点j++;}if (pareTo(rp[i].key) > 0) {r[i] = r[j];i = j;j = 2 * i + 1;} else {j = high + 1;}}r[i] = temp;}

public void heapSort() {int n =this.curLen;RecordNode temp;// 创建堆for (int i = n/2-1; i>=0; i--) {sift(i, n);}/*将堆顶元素（最小的元素）与末尾元素交换，将最小元素"沉"到数组末端;重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。这里做的工作就是下面示意图表示的*/for (int i = n - 1; i > 0; i--) {// 交换无序序列两端的元素temp = r[0];r[0] = r[i];r[i] = temp;// 剩余未排序的部分元素再次构建堆sift(0 ,i);}}

三、问答题

3.1 排序

3.1.1 时间复杂度和空间复杂度

p241-262 四大排序算法，比较长，写在最后面

3.2 最小生成树

p215-220 克鲁斯卡尔算法 普里姆算法

构造最小生成树一定有下面两个特点：

1、尽量选取最小的权值的边，并且不能有回路

2、n个顶点只选取n-1条边。

3.2.1 克鲁斯卡尔算法

根据边的权值递增的方式，一次找出权值尽可能最小的边建立最小生成树。并且规定每次新增的边不能使生成树形成回路。直到找到n-1条边为止。

最小生成树不是唯一的。

3.2.2 普里姆（Prime）算法

不知道怎么说，看图好懂一些。

普里姆算法不同于克鲁斯卡尔算法，它更像是一棵树的生长过程，适合结点数量多的树构建最小生成树。

3.3 建立二叉排序树

p294 292-299

3.3.1 二叉排序树定义

若左子树不为空，则左子树上所有结点的值均小于根结点的值。若右子树不为空，则右子树上所有结点的值均大于根结点的值。根结点的左右子树也都是二叉排序树。

3.4 哈希表处理冲突的方法：开放定址法的线性探测

p317

开放定址法是哈希表处理冲突的一种方法，它的基本思想是：当冲突发生时，形成一个地址序列，沿着这个序列逐个探测，知道找到一个“空”的开放地址，就将发生冲突的关键字存放在该地址。

开放定址法的一般形式为：

Hi=(H(key)+di)%m,(i=1,2,…,k(k≤m−1))H_i=(H(key)+d_i)\%m,(i=1,2,\dots,k(k\le m-1)) Hi​=(H(key)+di​)%m,(i=1,2,…,k(k≤m−1))

其中，H(key)是关键字的哈希函数，%是取模，m为哈希表长，di为每次再探测时的地址增量。

线性探测法即地址增量为di=1,2,…,m−1d_i=1,2,\dots,m-1di​=1,2,…,m−1的开放定址法，其中i为探测次数。这种方法在解决冲突的时候一，依次探测下一个地址，直到有空的地址后插入。若整个空间都找不到空余的地址，则产生溢出。

线性探测法很容易造成数据元素的“聚集”现象，即多个哈希地址不同的关键字都在争夺同一个后继哈希地址，这种现象对查找不利。

其根本原因是查找序列过分集中在发生冲突的存储单元后面，而没有在整个哈希表空间上分散开来。

3.5 BFS DFS

p208-209

3.5.1 广度优先搜索BFS

从图中的某个顶点V开始，先访问该顶点，在依次访问该顶点的每一个未被访问的邻接点w1,w2,…w_1,w_2,\dotsw1​,w2​,…。然后按照邻接点的访问顺序访问w1,w2,…w_1,w_2,\dotsw1​,w2​,…未被访问的子邻接点。

重复上述过程知道图中所有顶点都被访问为止。

3.5.2 深度优先搜索DFS

从图的某个顶点V开始访问，然后访问它的任意一个邻接点w1w_1w1​，再从w1w_1w1​出发，访问与w1w_1w1​相邻且为被访问过的顶点w2w_2w2​，再从w2w_2w2​出发进行类似访问。如此进行下去，知道所有子结点的邻接点都被访问过。

之后，退回一步，回到上一个被访问的顶点（递归），看看是否还有其他未被访问的邻接点，如果有，则访问此结点，然后再次从该子结点出发，进行类似的访问操作。

重复以上操作，直到图中所有结点均被访问。

3.6 哈夫曼树的构造

哈夫曼算法：

假设nnn个叶结点的权值分别为w1,w2,…,wn{w_1,w_2,\dots,w_n}w1​,w2​,…,wn​，则

由已知给定的nnn个权值w1,w2,…,wn{w_1,w_2,\dots,w_n}w1​,w2​,…,wn​，构造一个由nnn棵二叉树构成的森林FFF，森林中每一个结点单独作为一棵树（即每棵树仅有一个结点，就是根结点）。每棵树的权值分别为w1,w2,…,wn{w_1,w_2,\dots,w_n}w1​,w2​,…,wn​。在森林中选择根结点的权值最小和次小的两棵树，分部把它们作为左子树和右子树，构建一颗新的二叉树。该新二叉树的根结点权值为左右孩子的权值之和。将新二叉树的左右子树从森林中移除，将新产生的二叉树加入森林中重复上述两点，直到森林中只剩下一颗二叉树为之，这棵树就是哈弗曼树。

四、综合题

4.1 根据前中序遍历建立二叉树、森林

4.1.1根据前中序遍历建立二叉树

思路

取先根遍历序列中第一个结点作为根结点在中根遍历序列中寻找根结点，确定根结点在中根遍历序列中的位置，设为i(0≤i≤count)i(0 \le i \le count)i(0≤i≤count)，其中countcountcount为二叉树遍历序列的结点个数在中根遍历序列中确定： 根结点之前的 iii 个结点序列构成左子树的中根遍历序列根结点之后的 count−i−1count-i-1count−i−1 个结点序列构成右子树的中根遍历序列 在先跟遍历序列中确定： 根结点之后 iii 个结点序列构成左子树的先跟遍历序列剩下的 count−i−1count-i-1count−i−1 个结点序列构成右子树的先跟遍历序列 由上述3、4两个步骤又确定了左右子树的先根和中根遍历序列，递归构建完整的二叉树

图解

代码实现

/*** 通过前序遍历序列和中序遍历序列构建子树* @param preOrder 前序遍历序列* @param inOrder 中序遍历序列* @param preIndex 前序遍历序列索引* @param inIndex 中序遍历序列索引* @param count 当前子树的结点数*/public BinaryTreeNode(List<T> preOrder, List<T> inOrder, int preIndex, int inIndex, int count) {if (count > 0) {// 先获取根结点T r = preOrder.get(preIndex);// 寻找根结点在中根遍历序列中根的位置int i = 0;while (i < count) {if (r == inOrder.get(i + inIndex)) {break;}i++;}// 循环结束后，i就是根结点在中序遍历序列中的位置data = r;BinaryTreeNode<T> leftNode = new BinaryTreeNode<>(preOrder, inOrder, preIndex + 1, inIndex, i);if (leftNode.data != null) {left = leftNode;}BinaryTreeNode<T> rightNode = new BinaryTreeNode<>(preOrder, inOrder, preIndex + i + 1, inIndex + i + 1, count - i - 1);if (rightNode.data != null) {right = rightNode;}}}

4.1.2 森林与二叉树之间的转换

树 ⇒\Rightarrow⇒ 二叉树

p180

加线删线旋转

根据算法可得，任何一棵树对应的二叉树的根节点右子树一定为空。

二叉树 ⇒\Rightarrow⇒ 树

p180-181

逆过程

加线删线旋转

二叉树 ⇒\Rightarrow⇒ 森林

先把二叉树切分成子二叉树，再分别转为树

设BBB是一颗二叉树，rootrootroot是BBB的根节点，LLL是BBB的左子树，RRR是右子树。并且BBB对应的森林F(B)F(B)F(B)中含有nnn棵树：T1,T2,…,TnT_1,T_2,\dots,T_{n}T1​,T2​,…,Tn​，则二叉树BBB可按照如下规则转换成森林B(F)B(F)B(F)：

若BBB为空，则F(B)F(B)F(B)为空森林若BBB不为空，则F(B)F(B)F(B)中第一棵树T1T_1T1​的根节点为二叉树BBB中的根节点，T1T_1T1​中根节点的子树森林由B的左子树LLL转换而成，即F(L)={T11,T12,…,T1m}F(L)=\{T_{11},T_{12},\dots,T_{1m}\}F(L)={T11​,T12​,…,T1m​}，B的右子树R转换成F(B)中其余树组成的森林，即F(R)={T2,…,Tn}F(R)=\{T_2,\dots,T_n\}F(R)={T2​,…,Tn​}

4.2 将两个带头结点的循环链表合成一个循环链表

p50-51

五、排序算法

5.1 冒泡排序

时间复杂度：O(n2)O(n^2)O(n2)空间复杂度：O(1)O(1)O(1)稳定

public static void bubbleSort(int[] arr) {for(int i = 0; i < arr.length -1; i++) {for(int j = 0; j < arr.length - 1 - i; j++) {if(arr[j] > arr[j+1]) {//开始进行比较，如果arr[j]比arr[j+1]的值大，那就交换位置//保证大的数在后，小的数在前int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}

5.2 选择排序

每一次都查询余下区间的极值并插入到有序序列的末端

时间复杂度：O(n2)O(n^2)O(n2)空间复杂度：O(1)O(1)O(1)不稳定

public static void selectSort(int[] arr) {for (int i = 0; i < arr.length; i++) {// 查找获取剩下区间的最小值下标int minIndex = i;for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 下标发生改变则调换元素，// 否则说明当前元素在正确的位置上，不用调换if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}

5.3 直接插入排序

每一次将记录直接插入到有序序列的适当位置

时间复杂度：O(n2)O(n^2)O(n2)空间复杂度：O(1)O(1)O(1)稳定

不带监视哨

/*** 插入排序* @param arr*/public static void insertSort(int[] arr) {// 默认第一个数已经排序好，从下标1开始for (int i = 1; i < arr.length; i++) {// 将要插入的第i条记录暂存在temp中int insertValue = arr[i];// 将有序序列中比temp大的记录后移int j = i - 1;while ((j >= 0) && (insertValue < arr[j])) {arr[j+1] = arr[j];j--;}// 因为最后还有j--才退出循环，所以要j++arr[j+1] = insertValue;}}

带监视哨

每一次都将要插入的数据放在arr[0]处

遍历到最后一轮时，j==0，则arr[0]==arr[k]，自动退出循环，省去判断下标越界的操作

/*** 直接插入排序-带监视哨* @param arr*/public static void insertSortWithGuard(int[] arr) {for (int i = 1; i < arr.length; i++) {// 将要插入的第i条记录暂存在arr[0]中，arr[0]作为监视哨arr[0] = arr[i];// 将有序序列中比temp大的记录后移int j = i - 1;// 遍历到最后一轮时，j\==0，则arr[0]\==arr[k]，自动退出循环// 省去判断下标越界的操作while (arr[0] < arr[j]) {arr[j+1] = arr[j];j--;}arr[j+1] = arr[0];}}

5.4 希尔排序

又称缩小增量排序。每一次选择不同的增量，将数据划分成不同的组，每一次对单个组进行插入排序，并不断缩小增量，直到有序

时间复杂度：取决于增量的选择，区间：[O(n1.3),O(n2.0)][~O(n^{1.3}),~O(n^{2.0})~][O(n1.3),O(n2.0)]空间复杂度：O(1)O(1)O(1)不稳定

/*** 希尔排序* @param arr* @param incres 增量数组increments*/public static void shellSort(int[] arr, int[] incres) {// 因为用得多所以不在循环内定义int temp;// 遍历增量数组，interval为间隔for (int interval : incres) {// 分组，进行插入排序for (int i = interval; i < arr.length; i++) {temp = arr[i];// 后移int j;for (j = i - interval; j >= 0 && temp < arr[j]; j -= interval) {arr[j + interval] = arr[j];}// 插入arr[j + interval] = temp;}}}

5.5 快速排序

是冒泡排序的改进

通过一趟排序将要排序的数据分割成两部分，其中一部分的所有数据都比另一部分的所有数据小，然后再以同样的方法对两个子部分的数据进行快速排序，最终得到有序序列

时间复杂度：平均O(nlog⁡2n)O(n\log_2n)O(nlog2​n)空间复杂度：递归O(log⁡2n)O(\log_2n)O(log2​n)不稳定

public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);}/*** @param arr 排序数组* @param left 左哨兵* @param right 右哨兵*/public static void quickSort(int[] arr, int left, int right) {// 如果两个哨兵相遇，则结束循环if (left < right) {// 以最左边的数作为中心点(pivot)int i = left, j = right, pivot = arr[left];while (i < j) {// 从右向左找第一个小于x的数while (i < j && arr[j] >= pivot) {j--;}if (i < j) {// 退出循环有两种情况，i > j 或者 arr[j] < pivot// 如果能够进入该if语句说明是arr[j] < pivot，可以交换arr[i++] = arr[j];}// 从左向右找第一个大于等于pivot的数while (i < j && arr[i] < pivot) {i++;}if (i < j) {arr[j--] = arr[i];}}arr[i] = pivot;/*至此完成了一次移位调换int pivot = arr[i];arr[i++] = arr[j];arr[j--] = arr[i];......arr[i] = pivot;*/// 递归调用quickSort(arr, left, i - 1);quickSort(arr, i + 1, right);}}