数据结构

第一章绪论

数据相关概念

数据：所有能输入到计算机中并能被程序识别和处理的符号集合

数据分类：

  • 数值数据：整数、实数等。
  • 非数值数据：图形、图像、声音、文字等

数据对象：是性质相同的数据元素的集合，是数据的一个子集。比如字符集合C={‘A’,’B’,’C’}

数据元素：数据的基本单位，在程序中作为一个整体进行考虑和处理。

数据项：构成数据元素的最小单位。又被称为属性。

！！！一个数据元素由若干个数据项组成，数据项是数据不可分割的最小单位。

数据结构即数据的组织形式，它是数据元素之间存在的一种或多种特定关系的数据元素集合

image-20240915120954543

数据结构的三要素：

  • 数据元素间的逻辑关系 —->数据的逻辑结构
  • 数据元素及其关系在计算机存储器中存储的方式 —–>数据的存储结构(或物理结构)
  • 施加在该数据上的操作 ——->数据运算。

数据结构三要素

逻辑结构

数据元素之间的关系可以是元素间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种人为定义的关系称为数据元素间的逻辑关系，相应的结构称为逻辑结构/概念结构。

数据结构从逻辑上分为四类：

集合、线性结构、树结构、图结构

集合

元素之间的关系：无。

特点：数据元素之间除了”属于同一个集合”的关系外，别无其他逻辑关系。是最松散的，不受任何制约的关系。

image-20240915145536681

线性结构

比如：线性表、栈、队列、串、数组、广义表

元素之间的关系：一对一。

特点：开始元素和终端元素都是唯一的，除此之外，其余元素都有且仅有一个前驱元素和一个后记元素

image-20240915145649697

树结构

比如：树、二叉树

元素之间的关系：一对多。

特点：开始元素唯一，终端元素不为一。除了终端元素外，每个元素有一个或多个后继元素；除开始元素外，每个元素有且仅有一个前驱元素

image-20240915145833802

图结构

比如：有向图和无向图、带权图和无权图

元素之间的关系：多对多。

特点：所有元素都可能有多个前驱元素和多个后继元素

image-20240915152650739

总结

逻辑结构（有时直接称为数据结构）

  • 线性结构：线性表、栈、队列、串、广义表
  • 非线性结构：集合、树、图。

说明：

  1. 逻辑结构与数据元素本身的形式、内容无关
  2. 逻辑结构与数据元素的相对位置无关
  3. 逻辑结构与所含结点个数无关
  4. 逻辑结构与计算机无关

数据的存储结构

顺序存储(物理上连续)

  • 定义：顺序存储是最直观的一种存储方式，它将数据元素按照一定的顺序存放在一段连续的内存空间中。
  • 特点：
    • 访问速度快，因为可以直接通过索引进行访问。
    • 插入和删除操作较慢，因为需要移动大量元素来保持顺序或腾出空间。
    • 存储密度高（存储利用率高），因为不需要额外的空间来存储元素之间的关系。
  • 适用场景：适用于频繁访问但很少修改的数据集合。

链式存储

  • 定义：链式存储使用指针来链接数据元素，每个元素（节点）包含指向下一个节点的链接。
  • 特点：
    • 插入和删除操作快，只需改变相邻节点之间的指针即可。
    • 访问速度相对较慢，因为需要遍历链表直到找到目标元素。
    • 存储密度较低，因为每个节点除了存储自身数据外还需要存储指向其他节点的指针。
  • 适用场景：适合频繁修改的数据集合，特别是当数据量不确定或经常变化时

索引存储

  • 定义：索引存储是为了解决顺序存储中插入删除效率低下的问题而提出的，它为每个数据元素创建一个索引项，索引项通常包含元素的位置信息。
  • 特点：
    • 通过索引可以快速定位到具体的数据元素。
    • 需要维护额外的索引表，这会增加存储开销。
    • 支持高效的随机访问。
  • 适用场景：适合大数据量且需要快速定位的情况。

散列存储

  • 定义：散列存储使用哈希函数将关键字映射到数组的一个位置上进行存储。
  • 特点：
    • 基于哈希函数的查找非常快速，理想情况下可以达到O(1)的时间复杂度。
    • 可能会出现哈希冲突，需要合适的解决冲突策略。
    • 散列表的空间利用效率取决于哈希函数的选择以及处理冲突的方式。
  • 适用场景：适合需要快速查找、插入和删除操作的应用场景。

数据的运算

定义：施加在数据上的运算包括运算的定义和实现。

  • 运算的定义是针对逻辑结构的，指出运算的功能。
  • 运算的实现是针对存储结构的，指出运算的具体操作步骤。

一般的操作都是创建，销毁，增删改查。

数据类型、抽象数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

举例：

  • int：值的范围：-2147483648 ~ 2147483647 ，可进⾏操作：加、减、乘、除、模运算…
  • bool：值的范围：true、false，可进⾏操作：与、或、⾮…

1）原子类型。其值不可再分的数据类型。

2）结构类型。其值可以再分解为若干成分（分量）的数据类型。

抽象数据类型（Abstract Data Type，ADT）是抽象数据组织及与之相关的操作。

  • ADT 用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关。(与存储的结构无关)

算法

算法的概念

程序 = 数据结构 + 算法

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令 表示一个或多个操作

算法的特性

  1. 有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
  2. 确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
  3. 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
  4. 输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
  5. 输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

“好”算法的特点

  1. 正确性。算法应能够正确地解决求解问题。

  2. 可读性。算法应具有良好的可读性，以帮助人们理解。

  3. 健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

  4. 高效率与低存储量需求

时间复杂度

时间复杂度：衡量时间开销和问题规模n的关系。

口诀：常对幂指阶

图示：

image-20240915174109811

上图表示为：**$O(1) < O(\log_2{n}) < O(n) < O(n\log_2{n}) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$**

在计算时间复杂度时，我们可以只考虑阶数高的部分。用大O表示法表示

在利用大O表示法表示时间复杂度时：

  • 顺序执行的代码只会影响常数项，可以忽略，
  • 只需要挑选循环中的一个基本操作分析它执行的次数x与n的关系即可。
  • 多层嵌套循环，只关注最深层次循环执行的次数。
  • x的数量级O(x)就是时间复杂度T(n)

比如：

T1(n)=3n+3 —->时间复杂度是O(n)

T2(n)=n^2+3n+1000 ——>时间复杂度是O(n^2)

T3(n)=n^3 + n^2 +9999999 ——–>时间复杂度是：O(n^3)

在比如：

image-20240915180736448

我们在考虑时间复杂度时多考虑：

  • 最坏时间复杂度
  • 平均时间复杂度

一般不考虑最好时间复杂度。

空间复杂度

空间复杂度：衡量空间大小与问题规模的关系。

程序代码所占用的空间是不变的，变得是程序中那些需要额外定义的变量所占用的空间。

遇到普通程序时：

①找到所占空间大小与问题规模相关的变量。

②分析所占空间x与问题规模n的关系 x = f(n)

③x的数量级O(x)就是算法的空间复杂度S(n) —->S指的是space空间的意思

image-20240915182758527

当遇到递归函数时：

①找到递归函数调用的次数x与问题规模n的关系x = f(n)

②x的数量级O(x)就是算法的空间复杂度S(n)

image-20240915183936274

第二章线性表

线性表的定义

线性表是计算机科学中最基本的一种数据结构，它是由n（n≥0）个类型相同的元素组成的有限序列。每个元素都有一个前驱和后继的关系，除了第一个元素没有前驱，最后一个元素没有后继。线性表的特点是每个元素都对应一个非负整数的序号，称为该元素的位置或下标，用以表示其在表中的位置。

image-20240916104736990

线性表的基本操作

  • 创建一个新的空表

  • 向表中添加元素

    • 其他元素都要向后移动

  • 删除表中的元素

    • 其他元素要向前移动

  • 查找特定元素的位置

  • 访问特定位置上的元素

  • 清空整个表

  • 获取表的长度等

顺序表的实现

顺序表是一种常见的线性表实现方式，它是通过一组地址连续的存储单元来存储数据元素的数据结构。在顺序表中，逻辑上相邻的元素，在物理存储位置上也是相邻的。顺序表通常使用数组来实现，因此也可以认为顺序表是数组的一种应用形式。

下面是使用JS代码来实现的顺序表的基本操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class SequentialList {
    constructor(capacity = 10) {
        // 初始化一个固定大小的数组
        this.  array = new Array(capacity).fill(null); 
        this.size = 0; // 当前顺序表中的元素数量
    }

    is_empty() {
        return this.size === 0;
    }

    is_full() {
        return this.size === this.array.length;
    }

    append(item) {
        if (this.is_full()) {
            console.log("顺序表已满，无法添加更多元素");
            return;
        }
        this.array[this.size] = item;
        this.size += 1;
    }

    insert(index, item) {
        if (index < 0 || index > this.size) {
            console.log("插入位置无效");
            return;
        }
        if (this.is_full()) {
            console.log("顺序表已满，无法插入元素");
            return;
        }
        for (let i = this.size - 1; i >= index; i--) {
            this.array[i + 1] = this.array[i];
        }
        this.array[index] = item;
        this.size += 1;
    }

    remove(index) {
        if (index < 0 || index >= this.size) {
            console.log("删除位置无效");
            return;
        }
        for (let i = index; i < this.size - 1; i++) {
            this.array[i] = this.array[i + 1];
        }
        this.array[this.size - 1] = null;
        this.size -= 1;
    }

    display() {
        console.log("顺序表内容为: " + this.array.slice(0, this.size));
    }
}

// 使用顺序表的例子
const seq_list = new SequentialList(5);
seq_list.append(1);
seq_list.append(2);
seq_list.append(3);
seq_list.display(); // 输出: 顺序表内容为: 1,2,3

seq_list.insert(1, 10); // 在索引1处插入10
seq_list.display(); // 输出: 顺序表内容为: 1,10,2,3

seq_list.remove(2); // 删除索引2处的元素
seq_list.display(); // 输出: 顺序表内容为: 1,10,3

链表的实现

单链表

定义：单链表是一种数据结构，它由一系列节点组成，每个节点包含两部分：一部分是存储的数据元素，另一部分是一个指向列表中下一个节点的引用（或指针）。单链表中的最后一个节点的下一个节点引用通常为 null，表示链表的结束。单链表的特点是只向一个方向链接，即只能从一个节点访问到其后继节点，而不能反过来从前一个节点访问到后一个节点。

通常我们使用带头结点的单链表 - 如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// 定义链表节点类 Node
public class Node {
    int value; // 节点存储的值
    Node next; // 指向下一个节点的引用

    // 构造函数初始化节点的值，并设置下一个节点为 null
    public Node(int value) {
        this.value = value;
        this.next = null;
    }
}

// 定义单链表类 LinkedList
public class LinkedList {
    private Node head; // 链表的头节点

    // 构造函数初始化头节点为 null
    public LinkedList() {
        head = null;
    }

    // 在链表末尾添加一个新节点
    public void append(int value) {
        Node newNode = new Node(value); // 创建一个新节点

        // 如果链表为空，则让头节点指向新节点
        if (head == null) {
            head = newNode;
        } else {
            // 否则，遍历链表直到找到最后一个节点
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            // 将最后一个节点的下一个引用指向新节点
            last.next = newNode;
        }
    }

    // 在链表头部添加一个新节点
    public void prepend(int value) {
        Node newNode = new Node(value); // 创建一个新节点
        // 将新节点的下一个引用指向原来的头节点，并让头节点指向新节点
        newNode.next = head;
        head = newNode;
    }

    // 删除链表中的某个值
    public void delete(int value) {
        Node current = head; // 当前节点
        Node previous = null; // 前一个节点

        // 遍历链表直到找到要删除的节点
        while (current != null) {
            if (current.value == value) {
                // 如果是头结点，则更新头结点
                if (previous == null) {
                    head = current.next;
                } else {
                    // 否则，将前一个节点的下一个引用跳过当前节点
                    previous.next = current.next;
                }
                return; // 删除后立即返回
            }
            previous = current; // 更新前一个节点
            current = current.next; // 移动到下一个节点
        }
    }

    // 打印链表的所有元素
    public void printList() {
        Node current = head; // 当前节点
        // 遍历链表并打印每个节点的值
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println(); // 换行
    }

    // 主函数用于测试
    public static void main(String[] args) {
        LinkedList list = new LinkedList(); // 创建一个新的链表实例
        list.append(1); // 在链表末尾添加一个值为 1 的节点
        list.append(2); // 在链表末尾添加一个值为 2 的节点
        list.prepend(0); // 在链表头部添加一个值为 0 的节点
        list.printList(); // 输出: 0 1 2
        list.delete(1); // 删除值为 1 的节点
        list.printList(); // 输出: 0 2
    }
}

单链表的插入

实现后插操作：按位序插入

图示：

image-20240916151351868

如何实现给定的节点p进行前插操作？

①手动传入头指针，在循环查找p的前驱节点q，再q之后插入新节点

②在p节点之后插入一个节点s，之后s节点中的数据和p节点进行交换操作。

单链表的删除

实现删除节点：按位序删除

首先要明白，删除一个节点要修改该节点前一个节点的next指针。

image-20240916170134615

如何实现给定的节点p进行删除操作？

首先要明白，删除一个节点要修改该节点前一个节点的next指针。

①传入头指针，循环寻找 p 的前驱结点

②建一个新的指针q指向p节点的后继节点，再把后继节点的数据域和p节点的数据域进行交换，最后另节点p的next指针指向q的next即可。

image-20240916171048920

单链表的查找

按位查找

image-20240916173612814

按值查找

image-20240916174004523

单链表的建立

  • 尾插法：适用于需要在链表末尾添加元素的情况。每次插入都需要遍历整个链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class Node {
    int value;
    Node next;

    public Node(int value) {
        this.value = value;
        this.next = null;
    }
}

public class LinkedList {
    private Node head;

    public LinkedList() {
        head = null;
    }

    // 使用尾插法添加节点
    public void append(int value) {
        Node newNode = new Node(value); // 创建新节点

        // 如果链表为空，让头节点指向新节点
        if (head == null) {
            head = newNode;
        } else {
            // 遍历链表直到找到最后一个节点
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            // 将最后一个节点的下一个引用指向新节点
            current.next = newNode;
        }
    }

    // 打印链表
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.append(1); // 尾插法添加节点
        list.append(2);
        list.printList(); // 输出: 1 2
    }
}
  • 头插法：适用于需要快速在链表头部添加元素的情况。插入操作非常快，因为不需要遍历链表。
    • 可以用头插法实现单链表的逆置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class LinkedList {
    //初始化头结点
    private Node head;

    public LinkedList() {
        head = null;
    }

    // 使用头插法添加节点
    public void prepend(int value) {
        Node newNode = new Node(value); // 创建新节点
        // 将新节点的下一个引用指向原来的头节点，并让头节点指向新节点
        newNode.next = head;
        head = newNode;
    }

    // 打印链表
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.prepend(2); // 头插法添加节点
        list.prepend(1);
        list.printList(); // 输出: 1 2
    }
}

双链表

双链表（Doubly Linked List）是一种更加灵活的数据结构，它在单链表的基础上增加了对前一个节点的引用。这意味着，在双链表中，每个节点不仅包含一个指向下一个节点的指针，还有一个指向前一个节点的指针。这样的设计使得双链表支持双向遍历，并且在插入和删除节点时更为方便。

以下是一份关于双链表的学习笔记，包括基本概念、优缺点以及实现示例。

双链表的基本概念

  • 节点结构：每个节点包含三个部分：存储的数据元素、指向前一个节点的指针（prev）和指向下一个节点的指针（next）。
  • 头节点（Head）：链表的第一个节点。
  • 尾节点（Tail）：链表的最后一个节点。

双链表的优缺点

优点：

  1. 双向遍历：可以从前向后或从后向前遍历链表。
  2. 插入和删除操作：相比于单链表，在插入和删除节点时，双链表只需要修改前后的指针，不需要额外的遍历来查找前一个节点。

缺点：

  1. 空间开销较大：每个节点需要额外的指针来存储前一个节点的信息。
  2. 实现相对复杂：相对于单链表，双链表的实现需要处理更多的指针操作。

双链表的基本操作

  1. 插入节点：在指定位置插入新节点。
  2. 删除节点：删除指定位置的节点。
  3. 遍历链表：从前向后或从后向前遍历链表。
  4. 反转链表：将链表的方向反转。

Java 实现示例

以下是一个简单的双链表实现，包括插入、删除、遍历等功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public class DoublyLinkedList {
    // 头节点，表示链表的起始节点
    private DoublyNode head;

    // 尾节点，表示链表的最后一个节点
    private DoublyNode tail;

    // 构造函数，初始化空的双链表
    public DoublyLinkedList() {
        head = null; // 初始时头节点为 null
        tail = null; // 初始时尾节点为 null
    }

    // 在链表末尾添加一个新节点
    public void append(int value) {
        DoublyNode newNode = new DoublyNode(value); // 创建新的 DoublyNode 实例

        if (head == null) {
            head = newNode; // 如果链表为空，头节点指向新节点
            tail = newNode; // 尾节点也指向新节点
        } else {
            tail.next = newNode; // 更新尾节点的 next 指向新节点
            newNode.prev = tail; // 新节点的 prev 指向旧的尾节点
            tail = newNode; // 更新尾节点为新节点
        }
    }

    // 在链表头部添加一个新节点
    public void prepend(int value) {
        DoublyNode newNode = new DoublyNode(value); // 创建新的 DoublyNode 实例

        if (head == null) {
            head = newNode; // 如果链表为空，头节点指向新节点
            tail = newNode; // 尾节点也指向新节点
        } else {
            newNode.next = head; // 新节点的 next 指向旧的头节点
            head.prev = newNode; // 旧头节点的 prev 指向新节点
            head = newNode; // 更新头节点为新节点
        }
    }

    // 删除链表中的某个节点
    public void delete(int value) {
        DoublyNode current = head;

        while (current != null) {
            if (current.value == value) {
                if (current.prev != null) {
                    current.prev.next = current.next; // 更新前一个节点的 next
                } else {
                    head = current.next; // 如果删除的是头节点，更新头节点
                }

                if (current.next != null) {
                    current.next.prev = current.prev; // 更新后一个节点的 prev
                } else {
                    tail = current.prev; // 如果删除的是尾节点，更新尾节点
                }
                return;
            }
            current = current.next; // 移动到下一个节点
        }
    }

    // 打印链表
    public void printList() {
        DoublyNode current = head;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.append(1); // 在链表末尾添加一个值为 1 的节点
        list.append(2); // 在链表末尾添加一个值为 2 的节点
        list.prepend(0); // 在链表头部添加一个值为 0 的节点
        list.printList(); // 输出: 0 1 2
        list.delete(1); // 删除值为 1 的节点
        list.printList(); // 输出: 0 2
    }
}

双链表的其他应用场景

双链表还可以用于实现更高级的数据结构，如双向队列（Deque）、LRU 缓存等。由于双链表支持双向遍历和快速插入删除，因此在实际应用中非常有用。

希望这份学习笔记对你理解和掌握双链表有所帮助！如果有任何进一步的问题，请随时提问。

循环链表

把最后一个节点的next指针指向头结点即可。

循环链表（Circular Linked List）是一种特殊的链表结构，其中最后一个节点的下一个节点指针指向链表的第一个节点（头节点），形成了一个闭环。这种结构使得从任何一个节点出发都可以遍历整个链表。

循环链表的一个主要特点是，没有明确的“尾节点”，因为最后一个节点的 next 指针指向的是头节点。此外，循环链表也没有明确的“末尾”，因为链表形成了一个环形结构。

循环链表的基本操作

  1. 插入节点：可以在链表的任意位置插入节点。
  2. 删除节点：可以从链表中删除指定位置的节点。
  3. 遍历链表：可以从任意节点开始遍历整个链表。

循环链表的实现

下面是一个简单的 Java 实现示例，包括单向循环链表的基本操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class Node {
    int value;
    Node next;

    public Node(int value) {
        this.value = value;
        this.next = null; // 初始时下一个节点为 null
    }
}

public class CircularLinkedList {
    private Node head; // 头节点

    public CircularLinkedList() {
        head = null;
    }

    // 在链表末尾添加一个新节点
    public void append(int value) {
        Node newNode = new Node(value); // 创建新的 Node 实例

        if (head == null) {
            head = newNode; // 如果链表为空，头节点指向新节点
            head.next = head; // 形成闭环
        } else {
            Node last = head;
            while (last.next != head) {
                last = last.next;
            }
            last.next = newNode; // 更新尾节点的 next 指向新节点
            newNode.next = head; // 新节点的 next 指向头节点
        }
    }

    // 在链表头部添加一个新节点
    public void prepend(int value) {
        Node newNode = new Node(value); // 创建新的 Node 实例

        if (head == null) {
            head = newNode; // 如果链表为空，头节点指向新节点
            head.next = head; // 形成闭环
        } else {
            newNode.next = head; // 新节点的 next 指向旧的头节点
            Node last = head;
            while (last.next != head) {
                last = last.next;
            }
            last.next = newNode; // 更新尾节点的 next 指向新节点
            head = newNode; // 更新头节点为新节点
        }
    }

    // 删除链表中的某个节点
    public void delete(int value) {
        if (head == null) {
            return; // 链表为空，无法删除
        }

        Node current = head;
        Node prev = null;

        do {
            if (current.value == value) {
                if (prev == null) {
                    head = current.next; // 如果删除的是头节点，更新头节点
                } else {
                    prev.next = current.next; // 更新前一个节点的 next
                }
                break;
            }
            prev = current;
            current = current.next;
        } while (current != head);
    }

    // 打印链表
    public void printList() {
        if (head == null) {
            System.out.println("链表为空");
            return;
        }

        Node current = head;
        do {
            System.out.print(current.value + " ");
            current = current.next;
        } while (current != head);
        System.out.println();
    }

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();
        list.append(1); // 在链表末尾添加一个值为 1 的节点
        list.append(2); // 在链表末尾添加一个值为 2 的节点
        list.prepend(0); // 在链表头部添加一个值为 0 的节点
        list.printList(); // 输出: 0 1 2
        list.delete(1); // 删除值为 1 的节点
        list.printList(); // 输出: 0 2
    }
}

代码解析

  1. **节点类 Node**：

    • 包含一个整数值 value 和一个指向下一个节点的引用 next。

  2. **循环链表类 CircularLinkedList**：

    • 包含一个头节点引用 head。
    • 构造函数初始化 head 为 null。
    • append 方法用于在链表末尾添加一个新节点。
    • prepend 方法用于在链表头部添加一个新节点。
    • delete 方法用于删除链表中的某个节点。
    • printList 方法用于打印链表中的所有节点。

特点

  • 闭环结构：最后一个节点的 next 指向头节点。
  • 遍历：从任意节点开始，通过 next 指针可以遍历整个链表，直到回到起点。
  • 删除操作：需要注意处理头节点的特殊情况。

image-20240916182256146

静态链表

静态链表（Static Linked List）是一种在编译时就确定了大小和结构的链表实现方式。它利用数组来存储链表的节点，并使用索引来模拟链表中的指针关系。这种方式结合了数组的固定大小特性和链表的动态访问特性，可以在某些情况下提供更好的性能和管理。

静态链表的基本概念

在静态链表中，每个数组元素代表一个节点，数组元素中包含数据和一个指向“下一个”节点的索引（即“指针”）。这种实现方式允许在不改变数组大小的情况下，通过索引来模拟链表的插入和删除操作。

图示：image-20240916183439811

第三章栈、队列和数组

栈

基本概念

  1. 定义：

    • 栈是一种线性数据结构，是一种线性表，它遵循特定的访问模式：后进先出（LIFO）。这意味着最后进入栈的元素将是最先被移除的。

  2. 用途：

    • 栈用于解决很多问题，如括号匹配、后缀表达式计算（逆波兰表达式）、撤销功能实现等。

  3. 操作：栈的操作全部在栈顶进行。这是由于它的访问模型决定的

栈的操作

  1. 压栈（Push）：

    • 向栈中添加元素。
    • 如果栈满了，则不能再进行压栈操作，此时会发生“栈溢出”。

  2. 弹栈（Pop）：

    • 移除栈顶元素。
    • 如果栈是空的，则不能进行弹栈操作，此时会发生“栈下溢”。

  3. 查看栈顶（Peek/Top）：

    • 查看栈顶元素但不移除它。

  4. 清空栈（Clear）：

    • 移除所有元素，使栈为空。

  5. 检查是否为空（IsEmpty）：

    • 返回一个布尔值，指示栈是否为空。

  6. 获取栈大小（Size）：

    • 返回栈中元素的数量。

实现方式

  1. **数组实现(顺序存储方式)**：
    • 使用固定大小的数组来实现栈，需要管理栈顶指针。
    • 缺点是当栈满时需要处理栈溢出的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
public class ArrayStack {
    private int maxSize; // 栈的最大容量
    private int top;     // 栈顶位置的索引
    private int[] stackArray;

    // 构造函数初始化栈
    public ArrayStack(int size) {
        maxSize = size;
        stackArray = new int[maxSize]; // 创建数组
        top = -1; // 栈初始为空，top设置为-1
    }

    // 压栈操作
    public void push(int value) {
        if (top < maxSize - 1) { // 检查是否栈满
            stackArray[++top] = value; // 先递增top再插入
        } else {
            System.out.println("Stack is full. Cannot push " + value);
        }
    }

    // 弹栈操作
    public int pop() {
        if (top > -1) { // 检查是否栈空
            return stackArray[top--]; // 先取出再递减top
        } else {
            System.out.println("Stack is empty.");
            return -1; // 假设-1代表错误值或无值
        }
    }

    // 查看栈顶元素
    public int peek() {
        if (top > -1) {
            return stackArray[top];
        } else {
            System.out.println("Stack is empty.");
            return -1; // 假设-1代表错误值或无值
        }
    }

    // 检查栈是否为空
    public boolean isEmpty() {
        return (top == -1);
    }

    // 获取栈中元素个数
    public int size() {
        return top + 1;
    }

    // 主函数，用于测试
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(5); // 创建最大容量为5的栈

        // 测试压栈操作
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);

        // 尝试超出容量压栈
        stack.push(60); // 这应该提示栈已满

        // 测试弹栈操作
        System.out.println(stack.pop()); // 输出: 50
        System.out.println(stack.pop()); // 输出: 40

        // 查看栈顶元素
        System.out.println(stack.peek()); // 输出: 30

        // 检查栈是否为空
        System.out.println(stack.isEmpty()); // 输出: false

        // 获取栈的大小
        System.out.println(stack.size()); // 输出: 3
    }
}
  1. 链表实现(链式存储方式)：
    • 使用链表来实现栈，可以动态调整栈的大小。
    • 需要维护指向栈顶节点的指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// 定义链表节点类
class Node {
    int data;       // 节点存储的数据
    Node next;      // 指向下一个节点的引用

    // 构造函数
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// 定义栈类
public class LinkedListStack {
    private Node top; // 栈顶节点引用

    // 构造函数
    public LinkedListStack() {
        top = null; // 初始化为空栈
    }

    // 压栈操作
    public void push(int data) {
        // 创建新节点
        Node newNode = new Node(data);
        
        // 新节点成为新的栈顶
        newNode.next = top;
        top = newNode;
    }

    // 弹栈操作
    public int pop() {
        if (top == null) {
            System.out.println("Stack is empty. Cannot perform pop.");
            return Integer.MIN_VALUE; // 返回最小值作为错误标识
        }
        
        // 保存栈顶数据
        int poppedData = top.data;
        
        // 移动栈顶到下一个节点
        top = top.next;
        
        return poppedData;
    }

    // 查看栈顶元素
    public int peek() {
        if (top == null) {
            System.out.println("Stack is empty.");
            return Integer.MIN_VALUE; // 返回最小值作为错误标识
        }
        
        return top.data;
    }

    // 检查栈是否为空
    public boolean isEmpty() {
        return top == null;
    }

    // 获取栈的大小
    public int size() {
        int count = 0;
        Node current = top;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

    // 主函数，用于测试
    public static void main(String[] args) {
        LinkedListStack stack = new LinkedListStack(); // 创建一个空栈
        
        // 测试压栈操作
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);
        
        // 测试弹栈操作
        System.out.println("Popped: " + stack.pop()); // 输出: Popped: 50
        System.out.println("Popped: " + stack.pop()); // 输出: Popped: 40
        
        // 查看栈顶元素
        System.out.println("Peek: " + stack.peek()); // 输出: Peek: 30
        
        // 检查栈是否为空
        System.out.println("Empty: " + stack.isEmpty()); // 输出: Empty: false
        
        // 获取栈的大小
        System.out.println("Size: " + stack.size()); // 输出: Size: 3
    }
}

应用实例

  1. 括号匹配：

    • 利用栈可以检查字符串中的括号是否正确配对。
      • 左括号入栈，扫描到右括号时，就弹出一个左括号与其匹配
      • 匹配失败情况：左括号未匹配到，右括号未匹配到，左右括号未匹配到

  2. 表达式求值：

    • 表达式分类：
      • 前缀表达式：运算符位于两个操作数之间。
      • 中缀表达式：所有运算符都放在它们的操作数之前。
      • 后缀表达式：所有运算符都放在它们的操作数之后。
    • 中缀转后缀：1.确定运算顺序 2.找到下一个运算符按照[左操作数 右操作数 运算符] 组合成一个新的操作数。
    • 中缀转前缀：

注意事项

  1. 性能考量：

    • 栈的插入和删除操作通常非常快，因为它们只涉及修改几个指针。

  2. 内存管理：

    • 动态分配内存的栈需要注意释放不再使用的空间，以防止内存泄漏。

  3. 异常处理：

    • 当尝试从空栈中弹出元素时，应妥善处理异常情况。

队列

队列是只允许在一端进行插入，在另一端删除的线性表

当然可以帮助你整理关于队列的数据结构的学习笔记。下面是一个简洁的总结，包括队列的基本概念、类型以及一些常见的操作等：

队列定义

  • 定义：队列是一种特殊的线性表，它只允许在表的一端进行插入操作，在另一端进行删除操作。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。
  • 特性：遵循先进先出（FIFO, First In First Out）原则，即最先加入队列的元素总是最先被移除。

常见操作

  • 入队（Enqueue）：在队尾添加一个新元素。
  • 出队（Dequeue）：从队头移除一个元素。
  • 查看队头（Front）：返回队头元素，但不移除。
  • 查看队尾（Rear）：返回队尾元素，但不移除。
  • 是否为空（IsEmpty）：检查队列是否为空。
  • 队列大小（Size）：返回队列中元素的数量。

常见操作的实现

队列的顺序存储实现

让我们来看一下如何使用顺序存储（即数组）来实现队列的基本操作。顺序存储的队列通常被称为数组队列或循环队列。下面是一个基于数组实现的顺序队列的基本操作的 Java 代码示例。

队列中元素个数的计算（取余数）：(rear + capacity - front) % capacity

！！！！！！！当我们的队列的队尾指针在队尾元素的下一个位置时：

下面是几种判断队列空满的方法：

方法①：

队空的条件是：队列中队头索引和队尾索引相等。

队满条件是：队尾指针的在下一个位置是队头指针

方法②：

引入变量size：队列中当前元素的个数。初始化为0

添加一个元素size++，删除一个元素size–

队空条件：size == 0

队满条件：size == capacity

方法③：

引入标志变量比如tag，tag的值只有0/1。值为0时进行了删除操作，值为1时进行了添加操作。

一次操作中，进行删除操作可能让队列为空

一次操作中，进行添加操作可能让队列为满

队空条件：队头指针等于队尾指针且tag的值等于0

队满条件：队头指针等于队尾指针且tag的值等于1

java代码示例：这是队尾索引指向下一个位置的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
public class ArrayQueue<T> {
    private T[] elements; // 存储队列元素的数组
    private int front; // 队头索引
    private int rear; // 队尾索引（指向队尾元素的下一个位置）
    private final int capacity; // 队列的最大容量

    @SuppressWarnings("unchecked")
    public ArrayQueue(int capacity) {
        this.capacity = capacity; // 设置队列的最大容量
        elements = (T[]) new Object[capacity]; // 创建一个指定大小的对象数组
        front = 0; // 初始化队头索引为 0
        rear = 0; // 初始化队尾索引为 0，表示队列为空
    }

    // 入队操作
    public void enqueue(T element) {
        // 检查队列是否已满
        if ((rear + 1) % capacity == front) {
            throw new IllegalStateException("Queue is full.");
        }
        // 将元素存入当前队尾位置
        elements[rear] = element;
        // 更新队尾索引到下一个位置
        rear = (rear + 1) % capacity;
    }

    // 出队操作
    public T dequeue() {
        // 检查队列是否为空
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        // 获取队头元素
        T element = elements[front];
        // 清除引用以允许垃圾回收
        elements[front] = null;
        // 更新队头索引到下一个位置
        front = (front + 1) % capacity;
        return element; // 返回移除的元素
    }

    // 查看队头元素
    public T front() {
        // 检查队列是否为空
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        return elements[front]; // 返回队头元素
    }

    // 查看队尾元素
    public T rearElement() {
        // 检查队列是否为空
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        // 计算队尾元素的索引
        return elements[(rear - 1 + capacity) % capacity]; 
    }

    // 检查队列是否为空
    public boolean isEmpty() {
        return front == rear; // 如果队头和队尾相同，则队列为空
    }

    // 获取队列的大小
    public int size() {
        // 计算队头和队尾之间的距离
        if (front <= rear) {
            return rear - front; // 如果队尾大于等于队头，则直接计算差值
        } else {
            return capacity - (front - rear); // 否则，考虑到循环队列的特点，计算实际大小
        }
    }

    public static void main(String[] args) {
        // 创建一个容量为 5 的队列
        ArrayQueue<Integer> queue = new ArrayQueue<>(5);

        // 入队操作
        queue.enqueue(1); // 入队元素 1
        queue.enqueue(2); // 入队元素 2
        queue.enqueue(3); // 入队元素 3

        // 查看队头
        System.out.println("Front element: " + queue.front()); // 输出 Front element: 1

        // 查看队尾
        System.out.println("Rear element: " + queue.rearElement()); // 输出 Rear element: 3

        // 出队操作
        System.out.println("Dequeued element: " + queue.dequeue()); // 输出 Dequeued element: 1

        // 队列大小
        System.out.println("Queue size: " + queue.size()); // 输出 Queue size: 2
    }
}

Java 代码示例

下面这段代码示例，是队尾指针指向队尾元素的情况，注意和上述情况甄别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class ArrayQueue<T> {
    private T[] elements;
    private int front; // 队头索引
    private int rear; // 队尾索引
    private int size; // 当前队列中元素的数量
    private final int capacity; // 队列的最大容量

    @SuppressWarnings("unchecked")
    public ArrayQueue(int capacity) {
        //对队列进行初始化
        this.capacity = capacity;
        elements = (T[]) new Object[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    // 入队操作
    public void enqueue(T element) {
        if (size == capacity) {
            throw new IllegalStateException("Queue is full.");
        }
        if (rear == capacity - 1) { // 循环队列
            rear = 0;
        } else {
            rear++;
        }
        elements[rear] = element;
        if (front == -1) { // 如果是第一个元素，则更新 front
            front = 0;
        }
        size++;
    }

    // 出队操作
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        T element = elements[front];
        elements[front] = null; // 清除引用以允许垃圾回收
        if (front == rear) { // 清空队列
            front = 0;
            rear = -1;
        } else if (front == capacity - 1) { // 循环队列
            front = 0;
        } else {
            front++;
        }
        size--;
        return element;
    }

    // 查看队头元素
    public T front() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        return elements[front];
    }

    // 查看队尾元素
    public T rear() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        return elements[rear];
    }

    // 检查队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 获取队列的大小
    public int size() {
        return size;
    }

    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>(5);

        // 入队操作
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        // 查看队头
        System.out.println("Front element: " + queue.front()); // 输出 Front element: 1

        // 查看队尾
        System.out.println("Rear element: " + queue.rear()); // 输出 Rear element: 3

        // 出队操作
        System.out.println("Dequeued element: " + queue.dequeue()); // 输出 Dequeued element: 1

        // 队列大小
        System.out.println("Queue size: " + queue.size()); // 输出 Queue size: 2
    }
}

队列的链式存储实现

图示：有带头节点和不带头节点两种情况

image-20240917163214386

带头节点情况

初始化：

image-20240917164059921

队尾入队

image-20240917164153776

出队操作：

image-20240917164925237

3.

不带头节点情况

初始化：

image-20240917164111489

队尾入队：

image-20240917164555636

队头出队

image-20240917165201189

数组

数组理论基础

  • 数组是存放在连续内存空间上的相同类型数据的集合。

image-20240912215950111

  • 数组下标都是从0开始的。

  • 数组内存空间的地址是连续的

  • 正是因为数组在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

  • 数组的元素是不能删的，只能覆盖。

  • 针对二维数组：

    image-20240912220041734

结论：

  • C++中二维数组在地址空间上是连续的。