Java数据结构与算法【快速总结与复习】（附万字总结与复习）
1.线性表
1.实现增加、删除、查找等操作，选择顺序表还是链表作为存储结构？为什么？说明各自优缺点及适用情况。
答：
- 若是实现查找操作，则运用顺序表，若是增删操作，则运用链表。
- 因为链表实现增删操作时，一旦找到了要插入或删除的位置，链表的操作只需改变指针即可完成，时间复杂度为O(1)（但找到该位置的时间复杂度可能是O(n)），但若是顺序表实现增删操作时，则为了保持元素之间的顺序性，在顺序表中插入或删除元素可能需要移动大量的元素，导致时间复杂度为O(n)，所以增删频率高的操作，选择链表作为存储结构。
- 在实现查找操作时，选择顺序表，因为顺序表中的元素是连续存储在内存中的，所以可以通过索引快速定位到任意位置的元素，但是若是链表进行查找的话会很慢，由于链表不支持直接通过索引访问元素，所以必须从头开始逐一访问直到目标位置，这使得查找操作的时间复杂度为O(n)。
- 通过上述的分析，可知，若是增删操作的频率高，则使用链表，若是查找操作的频率高，则使用顺序表。
2.时间复杂度？顺序表、单（循环）链表和双（循环）链表的存储结构的结构定义（用Java语言描述）
答：
时间复杂度：
顺序表和链表（包括单链表、循环链表、双链表和双循环链表）的时间复杂度的插入、删除、查找等基本操作。
-
顺序表:
- 查找: O(1)（通过索引直接访问）
- 插入/删除: O(n)（最坏情况下需要移动n个元素）
-
单链表:
- 查找: O(n)（需要从头节点开始遍历）
- 插入/删除: O(1)（如果已经找到了要插入或删除的位置）
-
单循环链表:
- 查找: O(n)
- 插入/删除: O(1)（如果已知位置）
-
双向链表:
- 查找: O(n)
- 插入/删除: O(1)（因为有前后指针，所以可以从两个方向接近目标节点）
-
双向循环链表:
- 查找: O(n)
- 插入/删除: O(1)
对于上述的链表而言，O(1)的时间复杂度是在假设你已经知道要操作的节点的情况下。如果不知道这个节点，还需要先进行一次O(n)的查找操作来定位到该节点。
Java语言描述的结构定义：
以下是用Java语言描述的顺序表、单链表、单循环链表、双向链表和双向循环链表的基本结构定义：
顺序表
class ArrayList{
int[] data = new int[100];
int len;
public ArrayList(){
}
}
单链表
class SingleNode {
int data;
SingleNode next;
public SingleNode(int data){
this.data = data;
}
}
双向链表
class DoubleNode{
int data;
DoubleNode pre;
DoubleNode next;
public DoubleNode(int data){
this.data = data;
}
}
单链表的增删改查方法：
class ManagerSingleList{
SingleNode head = new SingleNode(0);
public void addLast(int val){
SingleNode node = new SingleNode(val);
SingleNode cur = head;
while (cur.next!=null){
cur = cur.next;
}
cur.next = node;
}
public void insertNode(int index,int val){
SingleNode node = new SingleNode(val);
SingleNode cur = head;
while (cur.next!=null){
if (index==0){
node.next = cur.next;
cur.next = node;
return;
}
cur = cur.next;
index--;
}
}
public void updateNode(int oldVal,int newVal){
SingleNode cur = head;
while (cur.next!=null){
if (cur.next.data == oldVal){
cur.next.data = newVal;
}
cur = cur.next;
}
}
public void addFirst(int val){
SingleNode node = new SingleNode(val);
node.next = head.next;
head.next = node;
}
public void removeNode(int val){
SingleNode cur = head;
while (cur.next!=null){
if (cur.next.data == val){
cur.next = cur.next.next;
}
cur = cur.next;
}
}
public void getNode(int index){
SingleNode cur = head;
int count = 0;
while (cur.next!=null){
if (count == index){
System.out.println(cur.next.data);
}
count++;
cur = cur.next;
}
}
}
双向链表的增删改查方法：
class ManagerDoubleList{
DoubleNode head = new DoubleNode(0);
public void removeDoubleNode(int val){
DoubleNode cur = head;
while (cur.next!=null){
if (cur.next.data == val){
cur.next = cur.next.next;
if (cur.next.next!=null){
cur.next.next.pre = cur;
}
}
cur = cur.next;
}
}
public void updateDoubleNode(int oldVal,int newVal){
DoubleNode cur = head;
while (cur.next!=null){
if (cur.next.data == oldVal){
cur.next.data = newVal;
}
cur = cur.next;
}
}
public void addDoubleNodeLast(int val){
DoubleNode node = new DoubleNode(val);
DoubleNode cur = head;
while (cur.next!=null){
cur = cur.next;
}
cur.next = node;
node.pre = cur;
}
public void InsertDoubleNode(int index,int val){
DoubleNode node = new DoubleNode(val);
DoubleNode cur = head;
while (cur.next!=null){
if (index==0){
node.next = cur.next;
cur.next.pre = node;
cur.next = node;
node.pre = cur;
return;
}
cur = cur.next;
index--;
}
}
public void addDoubleNodeFirst(int val){
DoubleNode node = new DoubleNode(val);
node.next = head.next;
head.next = node;
node.pre = head;
}
public void getDoubleNode(int index){
DoubleNode cur = head;
while (cur.next!=null){
if (index==0){
System.out.println(cur.next.data);
}
cur = cur.next;
index--;
}
}
}
单向链表和双向链表的测试的总代码
/**
* Description:
* 单向链表和双向链表的测试
* @Author 陈ze
*/
public class ReviewClass {
public static void main(String[] args) {
//双向链表的测验
// ManagerDoubleList managerDoubleList = new ManagerDoubleList();
// managerDoubleList.addDoubleNodeLast(1);
// managerDoubleList.addDoubleNodeLast(2);
// managerDoubleList.addDoubleNodeLast(3);
// managerDoubleList.addDoubleNodeLast(4);
// managerDoubleList.addDoubleNodeLast(5);
// managerDoubleList.addDoubleNodeLast(6);
// managerDoubleList.addDoubleNodeLast(7);
// managerDoubleList.addDoubleNodeFirst(0);
// managerDoubleList.list();
// managerDoubleList.removeDoubleNode(3);
// managerDoubleList.list();
// managerDoubleList.updateDoubleNode(3,9);
// managerDoubleList.list();
// managerDoubleList.getDoubleNode(3);
// managerDoubleList.list();
// managerDoubleList.InsertDoubleNode(3,8);
// managerDoubleList.list();
//单向链表的测验
// ManagerSingleList managerSingleList = new ManagerSingleList();
// managerSingleList.addLast(1);
// managerSingleList.addLast(2);
// managerSingleList.addLast(3);
// managerSingleList.addLast(4);
// managerSingleList.addLast(5);
// managerSingleList.addLast(6);
// managerSingleList.addLast(7);
// managerSingleList.addLast(8);
// managerSingleList.addFirst(0);
// managerSingleList.list();
// managerSingleList.insertNode(3,9);
// managerSingleList.list();
// managerSingleList.removeNode(0);
// managerSingleList.list();
// managerSingleList.getNode(3);
// managerSingleList.updateNode(2,9);
// managerSingleList.list();
}
}
class ManagerDoubleList{
DoubleNode head = new DoubleNode(0);
public void removeDoubleNode(int val){
DoubleNode cur = head;
while (cur.next!=null){
if (cur.next.data == val){
cur.next = cur.next.next;
if (cur.next.next!=null){
cur.next.next.pre = cur;
}
}
cur = cur.next;
}
}
public void updateDoubleNode(int oldVal,int newVal){
DoubleNode cur = head;
while (cur.next!=null){
if (cur.next.data == oldVal){
cur.next.data = newVal;
}
cur = cur.next;
}
}
public void addDoubleNodeLast(int val){
DoubleNode node = new DoubleNode(val);
DoubleNode cur = head;
while (cur.next!=null){
cur = cur.next;
}
cur.next = node;
node.pre = cur;
}
public void InsertDoubleNode(int index,int val){
DoubleNode node = new DoubleNode(val);
DoubleNode cur = head;
while (cur.next!=null){
if (index==0){
node.next = cur.next;
cur.next.pre = node;
cur.next = node;
node.pre = cur;
return;
}
cur = cur.next;
index--;
}
}
public void addDoubleNodeFirst(int val){
DoubleNode node = new DoubleNode(val);
node.next = head.next;
head.next = node;
node.pre = head;
}
public void getDoubleNode(int index){
DoubleNode cur = head;
while (cur.next!=null){
if (index==0){
System.out.println(cur.next.data);
}
cur = cur.next;
index--;
}
}
public void list() {
if (head.next==null){
System.out.println("空表");
return;
}
DoubleNode cur = head;
while (cur.next!=null){
System.out.printf("%2d ",cur.next.data);
cur = cur.next;
}
System.out.println();
}
}
class ManagerSingleList{
SingleNode head = new SingleNode(0);
public void addLast(int val){
SingleNode node = new SingleNode(val);
SingleNode cur = head;
while (cur.next!=null){
cur = cur.next;
}
cur.next = node;
}
public void insertNode(int index,int val){
SingleNode node = new SingleNode(val);
SingleNode cur = head;
while (cur.next!=null){
if (index==0){
node.next = cur.next;
cur.next = node;
return;
}
cur = cur.next;
index--;
}
}
public void updateNode(int oldVal,int newVal){
SingleNode cur = head;
while (cur.next!=null){
if (cur.next.data == oldVal){
cur.next.data = newVal;
}
cur = cur.next;
}
}
public void addFirst(int val){
SingleNode node = new SingleNode(val);
node.next = head.next;
head.next = node;
}
public void removeNode(int val){
SingleNode cur = head;
while (cur.next!=null){
if (cur.next.data == val){
cur.next = cur.next.next;
}
cur = cur.next;
}
}
public void getNode(int index){
SingleNode cur = head;
int count = 0;
while (cur.next!=null){
if (count == index){
System.out.println(cur.next.data);
}
count++;
cur = cur.next;
}
}
public void list() {
if (head.next==null){
System.out.println("空表");
return;
}
SingleNode cur = head;
while (cur.next!=null){
System.out.printf("%2d ",cur.next.data);
cur = cur.next;
}
System.out.println();
}
}
class ArrayList{
int[] data = new int[100];
int len;
public ArrayList(){
}
}
class SingleNode {
int data;
SingleNode next;
public SingleNode(int data){
this.data = data;
}
}
class DoubleNode{
int data;
DoubleNode pre;
DoubleNode next;
public DoubleNode(int data){
this.data = data;
}
}
2.栈和队列
1.栈的特点、队列的特点顺序栈的定义、入栈、出栈操作。
答：
栈的特点：
- 后进先出（LIFO）：最后被压入栈中的元素最先被弹出。
- 操作受限的数据结构：仅能在一端进行插入（入栈）或删除（出栈）操作。
队列的特点：
-
先进先出（FIFO）：最早进入队列的元素最先被移除。
-
两端操作：在一端（队尾）进行插入（入队），在另一端（队头）进行删除（出队）。
顺序栈的定义：
顺序栈是使用数组实现的栈，它预先分配了一定大小的存储空间。由于其底层是数组，因此访问速度快，但容量固定，可能需要额外处理溢出问题。
-
入栈操作：
向栈中添加一个新元素的过程叫做入栈（push）。如果栈已满，则不能进行入栈操作。
-
出栈操作：
从栈中移除最顶部的元素的过程称为出栈（pop）。如果栈为空，则不能执行出栈操作。
Java代码实现：
class ArrayStack {
private int maxSize; // 栈的最大容量
private int top = -1; // 指向栈顶元素的位置
private int[] stackArray;
public ArrayStack(int size) {
this.maxSize = size;
stackArray = new int[maxSize];
}
public void push(int value) {
if (top < maxSize - 1) {
stackArray[++top] = value;
} else {
System.out.println("栈已满，无法入栈");
}
}
public int pop() {
if (top >= 0) {
return stackArray[top--];
} else {
System.out.println("栈为空，无法出栈");
return -1;
}
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == maxSize - 1;
}
}
2.循环队列：定义、队空、队满、入队、出队基本操作。
答：
循环队列的定义：
- 循环队列是一种特殊的线性数据结构，它将存储空间的第一个位置视为紧接着最后一个位置之后，从而形成逻辑上的“循环”。
队空条件：
- 当front == rear时，表示队列为空。
队满条件：
为了避免“假溢出”现象（即队列实际未满但由于front和rear指针重合而误认为满），通常采用两种策略之一：
- 预留一个位置不使用，当(rear + 1) % capacity == front时认为队满；
- 或者使用额外变量记录队列中的元素数量。
入队操作：
- 向队列添加一个新元素，并更新rear指针。
出队操作：
- 从队列移除最前面的元素，并更新front指针。
Java代码实现：
class CircularQueue {
private int front, rear, size;
private final int capacity;
private final int[] queue;
public CircularQueue(int capacity) {
this.capacity = capacity;
queue = new int[capacity];
front = this.size = 0;
rear = capacity - 1;
}
public boolean isFull() {
return (size == capacity);
}
public boolean isEmpty() {
return (size == 0);
}
public void enqueue(int item) {
if (isFull()) {
System.out.println("队列已满，无法入队");
return;
}
rear = (rear + 1) % capacity;
queue[rear] = item;
size++;
System.out.println(item + " 已成功入队");
}
public int dequeue() {
if (isEmpty()) {
System.out.println("队列为空，无法出队");
return Integer.MIN_VALUE;
}
int item = queue[front];
front = (front + 1) % capacity;
size--;
System.out.println(item + " 已成功出队");
return item;
}
}
3.队列的应用：旋转车库案例。
Java代码实现：
import java.util.LinkedList;
import java.util.Queue;
public class RotatingGarage {
private Queue<String> cars = new LinkedList<>();
public void enter(String carId) {
cars.add(carId);
System.out.println(carId + " 已进入车库");
}
public String leave(String carId) {
if (!cars.isEmpty() && cars.peek().equals(carId)) {
return cars.poll();
} else {
Queue<String> tempQueue = new LinkedList<>();
while (!cars.isEmpty() && !cars.peek().equals(carId)) {
tempQueue.add(cars.poll());
}
if (!cars.isEmpty() && cars.peek().equals(carId)) {
String leavingCar = cars.poll();
while (!tempQueue.isEmpty()) {
cars.add(tempQueue.poll());
}
System.out.println(leavingCar + " 已离开车库");
return leavingCar;
} else {
System.out.println("未找到车牌号为 " + carId + " 的车辆");
return null;
}
}
}
public static void main(String[] args) {
RotatingGarage garage = new RotatingGarage();
garage.enter("A");
garage.enter("B");
garage.enter("C");
garage.leave("B"); // B 必须先让其他车移开才能离开，然后 A 和 C 再次进入。
garage.leave("A"); // 现在 A 可以直接离开，因为它在最前面。
}
}
这段代码展示了如何用队列来模拟旋转车库的工作流程。每当有车辆需要离开时，程序会检查是否可以直接离开还是需要先移动其他车辆。
3.数组
1.二维数组存储
答：
在计算机内存中，二维数组是以线性的方式进行存储的。
有两种主要的存储顺序：行序优先（row-major order）和列序优先（column-major order）。
对于行序优先存储，先连续存储同一行的数据，然后再存储下一行的数据；对于列序优先存储，则是先连续存储同一列的数据，再存储下一列的数据。
- 在C/C++/Java中，默认使用行序优先。
- 在Fortran/MATLAB中，默认使用列序优先。
2.二维数组元素的计算，地址的计算。
答：
为了计算特定元素的存储地址，可以使用以下公式（假设索引从0开始）：
LOC(A[i][j]) = BaseAddress + [(i * Columns) + j] * ElementSize
3.学生共100人，现将5门成绩用二维数组存储，第一名学生的第一门成绩的存储基地址LOC(A[0][0])=1000，以行序为主序，每行存储一名学生成绩，每个成绩占4个存储单元。
1.数组中共有多少个元素？
解：
由题可知：学生人数为100人，每个学生有5门成绩。
因此，二维数组的大小为 100 x 5，所以数组中总共有：100 * 5 = 500 个元素
2.第15名学生第4门课的存储地址是多少？
解：
为了计算特定元素的存储地址，我们可以使用以下公式（假设索引从0开始）：
LOC(A[i][j]) = BaseAddress + [(i * Columns) + j] * ElementSize
其中：
1.BaseAddress 是数组的基地址。
2.i 是当前元素所在的行索引。
3.j 是当前元素所在的列索引。
4.Columns 是每一行中的元素数量（在这个例子中是5，因为每个学生有5门课程的成绩）。
5.ElementSize 是每个元素占用的存储单元数（在这个例子中是4个字节）。
对于第15名学生（索引从0开始，因此是14），第4门课（同样地，索引从0开始，因此是3），其存储地址可以这样计算：
LOC(A[14][3]) = 1000 + [(14 * 5) + 3] * 4
= 1000 + [70 + 3] * 4
= 1000 + 73 * 4
= 1000 + 292
= 1292
因此，第15名学生第4门课的存储地址是 1292。
答：
1.数组中共有500个元素。
2.第15名学生第4门课的存储地址是 1292。
4.树
1.树的二叉链表存储、兄弟链表存储。
答：
树的二叉链表存储
二叉链表节点结构：
+-------------------+
| Data (A) |
| |
| +-----+ +---+
| | Left|---->| Right
+---+-----+ +---+
示例二叉树：
A
/ \
B C
/ \ \
D E F
二叉链表表示：
A -> [B, C]
B -> [D, E]
C -> [null, F]
D -> [null, null]
E -> [null, null]
F -> [null, null]
树的兄弟链表存储
兄弟链表节点结构：
+-------------------+
| Data (A) |
| |
| +-----+ +---+
| |FirstChild|---->| NextSibling
+---+-----+ +---+
示例多叉树：
A
/ | \
B C D
/ \ |
E F G
兄弟链表表示：
A -> [B, C, D]
B -> [E, F, null]
C -> [null, null]
D -> [G, null]
E -> [null, null]
F -> [null, null]
G -> [null, null]
2.树转换成二叉树
答：
转换规则：
- 第一个孩子成为左子节点。
- 兄弟节点成为右子节点。
转换前的树：
A
/ | \
B C D
/ \ |
E F G
转换后的二叉树：
A
/
B
/ \
E C
/ \
F D
/
G
-
遍历二叉树（三种遍历）、算法
答：
二叉树：
A / B / \ E C / \ F D / G前序遍历（Pre-order）： A B E F C D G
中序遍历（In-order）： E B F A C G D
后序遍历（Post-order）： E F B G D C A
Java代码实现：
public class BinaryTreeDemo { public static void main(String[] args) { BinaryTree tree = new BinaryTree(); /* 构建如下二叉树 * 1 * / \ * 2 3 * / \ * 4 5 */ tree.root = new TreeNode(1); tree.root.left = new TreeNode(2); tree.root.right = new TreeNode(3); tree.root.left.left = new TreeNode(4); tree.root.left.right = new TreeNode(5); System.out.println("前序遍历:"); tree.preOrderTraversal(tree.root); System.out.println("\n中序遍历:"); tree.inOrderTraversal(tree.root); System.out.println("\n后序遍历:"); tree.postOrderTraversal(tree.root); } } class BinaryTree { // 其他成员变量和方法... // 前序遍历：根 -> 左 -> 右 void preOrderTraversal(TreeNode node) { if (node == null) return; // 访问根节点 System.out.print(node.value + " "); // 遍历左子树 preOrderTraversal(node.left); // 遍历右子树 preOrderTraversal(node.right); } // 中序遍历：左 -> 根 -> 右 void inOrderTraversal(TreeNode node) { if (node == null) return; // 遍历左子树 inOrderTraversal(node.left); // 访问根节点 System.out.print(node.value + " "); // 遍历右子树 inOrderTraversal(node.right); } // 后序遍历：左 -> 右 -> 根 void postOrderTraversal(TreeNode node) { if (node == null) return; // 遍历左子树 postOrderTraversal(node.left); // 遍历右子树 postOrderTraversal(node.right); // 访问根节点 System.out.print(node.value + " "); } } class TreeNode { int value; TreeNode left, right; public TreeNode(int item) { value = item; left = right = null; } }3.哈夫曼树（构造哈夫曼树）、哈夫曼编码、带权路径长度（WPL=）
答：
假设我们有以下字符及其频率：
Character: A B C D E Frequency : 45 13 12 16 9构造过程中的最小堆变化如下：
Step 1: MinHeap = [(E,9), (C,12), (B,13), (D,16), (A,45)] Step 2: Combine (E,9) and (C,12) -> NewNode(21) MinHeap = [(NewNode(21),21), (B,13), (D,16), (A,45)] Step 3: Combine (NewNode(21),21) and (B,13) -> NewNode(34) MinHeap = [(NewNode(34),34), (D,16), (A,45)] Step 4: Combine (NewNode(34),34) and (D,16) -> NewNode(50) MinHeap = [(NewNode(50),50), (A,45)] Step 5: Combine (NewNode(50),50) and (A,45) -> RootNode(95) MinHeap = []最终的哈夫曼树：
RootNode(95) / \ NewNode(50) A(45) / \ NewNode(34) D(16) / \ NewNode(21) B(13) / \ E(9) C(12)哈夫曼编码
根据上述哈夫曼树生成的编码如下：
左支路为1，右支路为0。
则：
A:0
B:110
C:1110
D:10
E:1111
具体过程表格：
Character Path Description Path Length A Directly the right child of the root 1 B Right, Right, Left 3 C Right, Right, Right, Right 4 D Right, Left 2 E Right, Right, Right, Left 4 带权路径长度（WPL）
带权路径长度计算公式为：
W P L = ∑ i = 1 n w i ⋅ l i WPL = \sum_{i=1}^{n} w_i \cdot l_i WPL=i=1∑nwi⋅li
对于上面的哈夫曼树，WPL 计算如下：
WPL = ( 45 × 1 ) + ( 13 × 3 ) + ( 12 × 4 ) + ( 16 × 2 ) + ( 9 × 4 ) = 45 + 39 + 48 + 32 + 36 = 200 \begin{align*} \text{WPL} & = (45 \times 1) + (13 \times 3) + (12 \times 4) + (16 \times 2) + (9 \times 4) \\ & = 45 + 39 + 48 + 32 + 36 \\ & = 200 \end{align*} WPL=(45×1)+(13×3)+(12×4)+(16×2)+(9×4)=45+39+48+32+36=200
5.图
1.图的存储（邻接矩阵、邻接表）
答：
邻接矩阵
示例图：
假设有一个有向图，包含4个顶点 {0, 1, 2, 3} 和以下边：
0 -> 1 (权重5)
0 -> 2 (权重3)
1 -> 2 (权重2)
2 -> 3 (权重7)
邻接矩阵表示：
0 1 2 3
0 [0, 5, 3, 0]
1 [0, 0, 2, 0]
2 [0, 0, 0, 7]
3 [0, 0, 0, 0]
- 每个单元格 A[i][j] 表示从顶点 i 到顶点 j 的边的权重。
- 如果没有边，则用0表示（对于无向图，可以用无穷大表示）。
邻接表
示例图：
同样的图用邻接表表示如下：
0: [(1, 5), (2, 3)]
1: [(2, 2)]
2: [(3, 7)]
3: []
每个顶点对应一个列表，记录与之相邻的所有顶点及其边的权重。
2.最小生成树（普利姆算法、克鲁斯卡尔算法）会画过程。
答：
普利姆算法（Prim’s Algorithm）
示例图：
假设我们有一个加权无向图，顶点集合为 {0, 1, 2, 3, 4}，边集合及权重如下：
0-1 (2), 0-3 (6), 1-3 (8), 1-4 (5), 1-2 (3), 3-4 (9), 2-4 (7)
步骤图解：
-
选择起始点：选择顶点 0 开始。
MST = {0} -
选择最小边：选择边 0-1（权重2），因为它是最小的边。
MST = {0, 1} -
选择下一条最小边：选择边 1-2（权重3），继续扩展。
MST = {0, 1, 2} -
选择下一条最小边：选择边 1-4（权重5），继续扩展。
MST = {0, 1, 2, 4} -
选择下一条最小边：选择边 0-3（权重6），完成最小生成树构建。
MST = {0, 1, 2, 4, 3}
最终的最小生成树包括边 {0-1, 1-2, 1-4, 0-3}，总权重为 2 + 3 + 5 + 6 = 16。
克鲁斯卡尔算法（Kruskal’s Algorithm）
示例图：
同样使用上述图：
-
排序边：按权重升序排列所有边。
(0-1, 2), (1-2, 3), (0-3, 6), (1-4, 5), (1-3, 8), (2-4, 7), (3-4, 9) -
逐步添加边：
-
添加边
(0-1)，不会形成环。MST = {(0-1)} -
添加边
(1-2)，不会形成环。MST = {(0-1), (1-2)} -
添加边
(0-3)，不会形成环。MST = {(0-1), (1-2), (0-3)} -
添加边
(1-4)，不会形成环。MST = {(0-1), (1-2), (0-3), (1-4)}
-
最终的最小生成树包括边 {0-1, 1-2, 0-3, 1-4}，总权重为 2 + 3 + 6 + 5 = 16。
3.单源点最短路径（迪杰斯特拉算法）：从一个顶点到其他各个顶点的最短路径。 能写出最短路径及路径值。
答：
示例图：
假设我们有一个加权有向图，顶点集合为 {0, 1, 2, 3}，边集合及权重如下：
0 -> 1 (权重5)
0 -> 2 (权重3)
1 -> 2 (权重2)
2 -> 3 (权重7)
步骤图解：
-
初始化距离数组：dist[] = [0, ∞, ∞, ∞]，起点 0 的距离设为0。
-
创建优先队列：将起点 0 加入队列。
-
取出顶点 0，更新相邻顶点 1 和 2 的距离：
dist[] = [0, 5, 3, ∞] -
取出顶点 2，更新相邻顶点 3 的距离：
dist[] = [0, 5, 3, 10] -
取出顶点 1，尝试更新相邻顶点 2 的距离，但不会改变，因为 5 + 2 > 3。
-
队列为空，结束。
最终最短路径及路径值如下：
- 从 0 到 1：路径 [0, 1]，路径值 5
- 从 0 到 2：路径 [0, 2]，路径值 3
- 从 0 到 3：路径 [0, 2, 3]，路径值 10
6.查找和排序
1.二分法查找：基本思想，方法，适用范围，查找过程、算法。
答：
基本思想
二分法查找是一种高效的搜索算法，适用于有序数组或列表。其核心思想是通过每次将查找范围缩小一半来快速定位目标值的位置。这种方法极大地减少了查找所需的时间，尤其是在处理大规模数据时。
方法
- 初始化边界：设定两个指针，left 指向数组的第一个元素，right 指向最后一个元素。
- 计算中间位置：找到 left 和 right 的中间位置 mid。
- 比较中间值：
- 如果目标值等于 mid 位置的值，则查找成功，返回该索引。
- 如果目标值小于 mid 位置的值，则调整 right 指针到 mid - 1，即在左半部分继续查找。
- 如果目标值大于 mid 位置的值，则调整 left 指针到 mid + 1，即在右半部分继续查找。
- 重复步骤：不断重复上述过程，直到找到目标值或 left 超过 right（即查找范围为空）。
- 查找失败：如果遍历结束仍未找到目标值，则返回未找到的信息。
适用范围
- 必须是有序的数据结构：无论是升序还是降序排列的数组、列表等都可以使用二分法查找。
- 适用于静态数据集：因为一旦数据被排序后，插入和删除操作会导致额外的成本来维持顺序性，所以对于频繁变动的数据集不太适合。
- 对数时间复杂度 O(log n)：相比于线性搜索的 O(n)，二分法查找效率更高，尤其当数据量很大时优势明显。
查找过程
假设我们有一个已经按升序排序的整数数组 [1, 3, 5, 7, 9, 11]，并且我们要查找数字 7。
- 初始状态：left = 0, right = 5 （数组长度减一）
- 第一次迭代：
- 计算 mid = (0 + 5) / 2 = 2
- 比较 array[mid] = array[2] = 5 与目标值 7，发现 7 > 5，因此更新 left = mid + 1 = 3
- 第二次迭代：
- 新的 mid = (3 + 5) / 2 = 4
- 比较 array[mid] = array[4] = 9 与目标值 7，发现 7 < 9，因此更新 right = mid - 1 = 3
- 第三次迭代：
- 新的 mid = (3 + 3) / 2 = 3
- 比较 array[mid] = array[3] = 7 与目标值 7，发现两者相等，查找成功！
算法总结
二分法查找是一种基于“分治”策略的经典算法，它通过递归或迭代的方式逐步缩小查找范围，最终确定目标值的位置或者确认不存在于给定的数据集中。
2.散列（哈希）表。
答：
散列表（Hash Table），也称为哈希表，是一种基于键值对的数据结构，它使用哈希函数将键映射到表中的特定位置来存储对应的值。散列表提供了常数时间复杂度 (O(1)) 的插入、删除和查找操作（在理想情况下）。以下是关于散列表更详细的介绍：
- 基本概念
- 键（Key）：用于唯一标识数据项的值。
- 值（Value）：与键关联的实际数据。
- 哈希函数（Hash Function）：一个数学函数，接受任意长度的输入（键），并将其转换为固定长度的输出（通常是整数索引）。一个好的哈希函数应该尽量均匀地分布键值，以减少冲突的发生。
- 桶（Bucket）：散列表中存储元素的位置，通常是一个数组或链表。
- 工作原理
当需要插入、查找或删除一个键值对时，散列表会执行以下步骤：
-
插入：
- 使用哈希函数计算给定键的哈希码。
- 根据哈希码确定该键应存放在哪个桶中。
- 如果该桶为空，则直接插入；如果存在冲突（即已经有其他键占用此桶），则根据冲突解决策略处理。
-
查找：
- 同样使用哈希函数计算给定键的哈希码。
- 定位到相应的桶，并检查是否存在匹配的键。
- 如果找到了匹配的键，则返回对应的值；否则表示未找到。
-
删除：
- 计算哈希码并定位到相应桶。
- 查找并移除指定键值对。
- 注意处理可能存在的空洞问题（即删除后留下的空位）。
- 哈希函数设计
一个好的哈希函数应当满足以下条件：
- 均匀性：不同键产生的哈希值尽可能分散在整个表空间内，避免集中于某些区域。
- 高效性：计算速度快，不会成为性能瓶颈。
- 确定性：对于相同的输入总是产生相同的输出。
- 低冲突率：尽量减少不同键产生相同哈希值的概率。
- 冲突解决方法
由于哈希函数可能会导致不同的键映射到同一个桶上，这就产生了冲突。常见的冲突解决方法包括：
- 链地址法（Separate Chaining）：每个桶实际上是一个链表或其他形式的容器，可以容纳多个键值对。当发生冲突时，新的键值对被添加到该桶的链表中。
- 开放寻址法（Open Addressing）：所有键值对都存储在一个连续的数组中，冲突通过某种方式重新定位到下一个可用位置。具体有以下几种变体：
- 线性探测（Linear Probing）：简单地向后移动一个位置直到找到空槽。
- 二次探测（Quadratic Probing）：每次跳跃的距离按平方数递增。
- 双重哈希（Double Hashing）：使用第二个哈希函数计算跳跃距离。
- 负载因子与扩容
负载因子（Load Factor）是衡量散列表满程度的一个指标，定义为已用桶数除以总桶数。为了保持高效的性能，当负载因子超过一定阈值时，散列表通常会自动扩展其容量，重新分配所有现有键值对到更大的新表中。这个过程称为“扩容”或“再哈希”。
3.排序的基本思想。每一趟（前几趟）排序的结果。选择、冒泡、快速、二路归并。
答：
1.选择排序
选择排序的基本思想是每次从未排序部分选出最小的元素，并将其放置在已排序序列的末尾。
初始状态：[5, 2, 9, 1, 5, 6]
- 第1趟：找到最小值 1，与第一个元素交换位置。
- 结果：[1, 2, 9, 5, 5, 6]
- 第2趟：在剩下的未排序部分 [2, 9, 5, 5, 6] 中找到最小值 2，它已经在正确的位置上，所以无需交换。
- 结果：[1, 2, 9, 5, 5, 6]
- 第3趟：在剩下的未排序部分 [9, 5, 5, 6] 中找到最小值 5，并与第三个元素交换。
- 结果：[1, 2, 5, 5, 9, 6]
- 第4趟：在剩下的未排序部分 [5, 5, 6] 中找到最小值 5，它已经在正确的位置上，所以无需交换。
- 结果：[1, 2, 5, 5, 9, 6]
- 第5趟：在剩下的未排序部分 [9, 6] 中找到最小值 6，并与第五个元素交换。
- 结果：[1, 2, 5, 5, 6, 9]
最终排序完成后的数组为 [1, 2, 5, 5, 6, 9]。
2.冒泡排序（改进）
冒泡排序通过反复遍历列表，比较相邻元素并在必要时交换它们的位置。改进版本会在没有发生任何交换时提前终止。
初始状态：[5, 2, 9, 1, 5, 6]
- 第1趟：
- 比较并交换 (5, 2)，得到 [2, 5, 9, 1, 5, 6]
- 比较并交换 (5, 9)，无变化
- 比较并交换 (9, 1)，得到 [2, 5, 1, 9, 5, 6]
- 比较并交换 (9, 5)，得到 [2, 5, 1, 5, 9, 6]
- 比较并交换 (9, 6)，得到 [2, 5, 1, 5, 6, 9]
- 结果：[2, 5, 1, 5, 6, 9]
- 第2趟：
- 比较并交换 (2, 5)，无变化
- 比较并交换 (5, 1)，得到 [2, 1, 5, 5, 6, 9]
- 比较并交换 (5, 5)，无变化
- 比较并交换 (5, 6)，无变化
- 结果：[2, 1, 5, 5, 6, 9]
- 第3趟：
- 比较并交换 (2, 1)，得到 [1, 2, 5, 5, 6, 9]
- 比较并交换 (2, 5)，无变化
- 比较并交换 (5, 5)，无变化
- 结果：[1, 2, 5, 5, 6, 9]
- 第4趟 和 第5趟：因为没有任何交换发生，所以可以提前结束。
最终排序完成后的数组为 [1, 2, 5, 5, 6, 9]。
3.快速排序
快速排序采用分治法策略，通过递归方式对子数组进行排序。
初始状态：[5, 2, 9, 1, 5, 6]
假设我们选择最后一个元素作为基准（pivot），并且总是从左到右扫描：
- 第1次划分：
- 将小于或等于基准 6 的所有元素移到左边，大于它的移到右边。
- 结果：[5, 2, 5, 1, 9, 6]，此时基准 6 已经位于其最终位置。
- 递归调用 对左右两边分别进行快速排序：
- 左边 [5, 2, 5, 1] 继续以同样的方式处理。
- 右边 [9] 只有一个元素，已经是有序的。
对于左边的部分，再次选取最后一个元素 1 作为基准：
- 第2次划分：
- 结果：[1, 2, 5, 5]，此时基准 1 已经位于其最终位置。
然后继续对左边 [2, 5, 5] 进行划分：
- 第3次划分：
- 结果：[2, 5, 5]，此时基准 5 已经位于其最终位置。
由于 [2] 和 [5] 都只有一个元素，它们都是有序的，因此不需要进一步操作。
最终排序完成后的数组为 [1, 2, 5, 5, 6, 9]。
4.二路归并排序
二路归并排序也是一种基于分治法的排序算法，它首先将数组分成两个相等的子数组，递归地对每个子数组进行排序，最后合并这两个有序子数组。
初始状态：[5, 2, 9, 1, 5, 6]
- 第一次分割：
- 分割成 [5, 2, 9] 和 [1, 5, 6]
- 第二次分割：
- [5, 2, 9] 分割成 [5] 和 [2, 9]
- [1, 5, 6] 分割成 [1] 和 [5, 6]
- 第三次分割：
- [2, 9] 分割成 [2] 和 [9]
- [5, 6] 分割成 [5] 和 [6]
现在所有的子数组都只包含一个元素，可以直接开始合并：
- 第一次合并：
- 合并 [2] 和 [9] 得到 [2, 9]
- 合并 [5] 和 [6] 得到 [5, 6]
- 第二次合并：
- 合并 [5] 和 [2, 9] 得到 [2, 5, 9]
- 合并 [1] 和 [5, 6] 得到 [1, 5, 6]
- 第三次合并：
- 最终合并 [2, 5, 9] 和 [1, 5, 6] 得到 [1, 2, 5, 5, 6, 9]
最终排序完成后的数组为 [1, 2, 5, 5, 6, 9]。
4.排序算法：选择、冒泡（改进）
答：
1.选择排序（Selection Sort）
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
// 遍历所有元素
for (int i = 0; i < n - 1; i++) {
// 假设当前索引是最小值的位置
int minIndex = i;
// 在未排序部分寻找最小值
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 如果找到了更小的值，则交换
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
// 打印每一趟排序后的结果
System.out.println("After pass " + (i + 1) + ": " + Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] array = {5, 2, 9, 1, 5, 6};
System.out.println("Original array: " + Arrays.toString(array));
selectionSort(array);
System.out.println("Sorted array: " + Arrays.toString(array));
}
}
2.改进版冒泡排序（Optimized Bubble Sort）
public class OptimizedBubbleSort {
public static void bubbleSortOptimized(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
// 每一轮遍历都会将最大的元素移动到正确的位置
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换相邻元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 打印每一趟排序后的结果
System.out.println("After pass " + (i + 1) + ": " + Arrays.toString(arr));
// 如果没有发生任何交换，说明数组已经有序，可以提前结束
if (!swapped) break;
}
}
public static void main(String[] args) {
int[] array = {5, 2, 9, 1, 5, 6};
System.out.println("Original array: " + Arrays.toString(array));
bubbleSortOptimized(array);
System.out.println("Sorted array: " + Arrays.toString(array));
}
}
3.代码解释
-
选择排序：selectionSort 方法实现了选择排序算法。它通过每次从未排序部分中找到最小值并与当前索引位置的元素交换，从而逐步构建已排序序列。在每轮迭代后打印当前状态。
-
改进版冒泡排序：bubbleSortOptimized 方法实现了带有优化的冒泡排序。它在每次遍历时检查是否发生了元素交换，如果没有发生交换则提前终止循环，减少不必要的比较次数。同样地，在每轮迭代后打印当前状态。
希望读者朋友们通过本章的学习，不仅能掌握数据结构与算法的基础理论知识，还能将其灵活运用到解决实际编程问题当中去。如果大家有任何疑问或想法，请随时留言交流！最后作者创作不易，若觉得还行的读者大大，请一键三连，再次感谢读者大大!
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
28
0- 0
已为社区贡献1条内容
所有评论(0)