数据结构与算法

, ,

数据结构与算法

复杂度分析

时间复杂度

时间复杂度是衡量算法执行时间随输入规模增长的变化趋势。常用大 O 符号表示，忽略常数项和低阶项。

常见时间复杂度：

  • O(1)：常数时间
  • O(log n)：对数时间
  • O(n)：线性时间
  • O(n log n)：线性对数时间
  • O(n²)：平方时间
  • O(n³)：立方时间
  • O(2ⁿ)：指数时间
  • O(n!)：阶乘时间

示例：

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
// O(1) - 常数时间
int getFirstElement(int arr[]) {
    return arr[0];
}

// O(n) - 线性时间
int sum(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += arr[i];
    }
    return total;
}

// O(n²) - 平方时间
int bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

空间复杂度

空间复杂度是衡量算法执行过程中所需额外空间随输入规模增长的变化趋势。

常见空间复杂度：

  • O(1)：常数空间
  • O(n)：线性空间
  • O(n²)：平方空间

示例：

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
// O(1) - 常数空间
int sum(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += arr[i];
    }
    return total;
}

// O(n) - 线性空间
int* copyArray(int arr[], int n) {
    int* newArr = new int[n];
    for (int i = 0; i < n; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

// O(n²) - 平方空间
int** createMatrix(int n) {
    int** matrix = new int*[n];
    for (int i = 0; i < n; i++) {
        matrix[i] = new int[n];
    }
    return matrix;
}

数据结构

线性数据结构

数组

数组是一种线性数据结构，每个元素在内存中都是连续存储的。

优点：

  • 访问操作效率高，时间复杂度为 O(1)

缺点：

  • 插入和删除操作效率低，时间复杂度为 O(n)

操作实现：

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
class Array {
private:
    int* data;
    int size;
    int capacity;

public:
    // 初始化
    Array(int initCapacity = 10) {
        capacity = initCapacity;
        size = 0;
        data = new int[capacity];
    }

    // 访问
    int get(int index) {
        if (index < 0 || index >= size) {
            throw "Index out of range";
        }
        return data[index];
    }

    // 插入
    void insert(int index, int value) {
        if (index < 0 || index > size) {
            throw "Index out of range";
        }
        if (size == capacity) {
            resize(capacity * 2);
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = value;
        size++;
    }

    // 删除
    void remove(int index) {
        if (index < 0 || index >= size) {
            throw "Index out of range";
        }
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        if (size <= capacity / 4 && capacity / 2 > 0) {
            resize(capacity / 2);
        }
    }

    // 扩容
    void resize(int newCapacity) {
        int* newData = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
    }

    // 获取大小
    int getSize() {
        return size;
    }

    // 析构函数
    ~Array() {
        delete[] data;
    }
};

链表

链表是一种线性数据结构，每个节点元素包括数据域和指针域。

优点：

  • 动态分配内存，不需要提前分配内存空间
  • 插入和删除操作效率高，时间复杂度为 O(1)

缺点：

  • 访问操作效率低，时间复杂度为 O(n)

分类：

  • 单链表
  • 双链表
  • 循环链表

单链表实现：

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
class ListNode {
public:
    int val;
    ListNode* next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class LinkedList {
private:
    ListNode* head;
    int size;

public:
    // 初始化
    LinkedList() {
        head = new ListNode(0); // 虚拟头节点
        size = 0;
    }

    // 插入
    void insert(int index, int value) {
        if (index < 0 || index > size) {
            throw "Index out of range";
        }
        ListNode* prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
        ListNode* newNode = new ListNode(value);
        newNode->next = prev->next;
        prev->next = newNode;
        size++;
    }

    // 删除
    void remove(int index) {
        if (index < 0 || index >= size) {
            throw "Index out of range";
        }
        ListNode* prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
        ListNode* delNode = prev->next;
        prev->next = delNode->next;
        delete delNode;
        size--;
    }

    // 查找
    int get(int index) {
        if (index < 0 || index >= size) {
            throw "Index out of range";
        }
        ListNode* curr = head->next;
        for (int i = 0; i < index; i++) {
            curr = curr->next;
        }
        return curr->val;
    }

    // 遍历
    void traverse() {
        ListNode* curr = head->next;
        while (curr != nullptr) {
            cout << curr->val << " ";
            curr = curr->next;
        }
        cout << endl;
    }

    // 获取大小
    int getSize() {
        return size;
    }

    // 析构函数
    ~LinkedList() {
        while (head != nullptr) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

栈

栈是一种线性数据结构，遵循后进先出（LIFO）的原则。

实现方式：

  • 基于数组实现
  • 基于链表实现

基于数组的栈实现：

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
class Stack {
private:
    int* data;
    int top;
    int capacity;

public:
    // 初始化
    Stack(int initCapacity = 10) {
        capacity = initCapacity;
        data = new int[capacity];
        top = -1;
    }

    // 入栈
    void push(int value) {
        if (top == capacity - 1) {
            resize(capacity * 2);
        }
        data[++top] = value;
    }

    // 出栈
    int pop() {
        if (isEmpty()) {
            throw "Stack is empty";
        }
        int value = data[top--];
        if (top < capacity / 4 && capacity / 2 > 0) {
            resize(capacity / 2);
        }
        return value;
    }

    // 访问栈顶元素
    int peek() {
        if (isEmpty()) {
            throw "Stack is empty";
        }
        return data[top];
    }

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

    // 获取大小
    int getSize() {
        return top + 1;
    }

    // 扩容
    void resize(int newCapacity) {
        int* newData = new int[newCapacity];
        for (int i = 0; i <= top; i++) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
    }

    // 析构函数
    ~Stack() {
        delete[] data;
    }
};

队列

队列是一种线性数据结构，遵循先进先出（FIFO）的原则。

实现方式：

  • 基于数组实现
  • 基于链表实现

基于数组的循环队列实现：

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
class Queue {
private:
    int* data;
    int front;
    int rear;
    int capacity;

public:
    // 初始化
    Queue(int initCapacity = 10) {
        capacity = initCapacity + 1; // 浪费一个空间
        data = new int[capacity];
        front = 0;
        rear = 0;
    }

    // 入队
    void enqueue(int value) {
        if ((rear + 1) % capacity == front) {
            resize(capacity * 2 - 1); // 保持capacity = newCapacity + 1
        }
        data[rear] = value;
        rear = (rear + 1) % capacity;
    }

    // 出队
    int dequeue() {
        if (isEmpty()) {
            throw "Queue is empty";
        }
        int value = data[front];
        front = (front + 1) % capacity;
        if (getSize() < (capacity - 1) / 4 && (capacity - 1) / 2 > 0) {
            resize((capacity - 1) / 2 + 1);
        }
        return value;
    }

    // 访问队头元素
    int getFront() {
        if (isEmpty()) {
            throw "Queue is empty";
        }
        return data[front];
    }

    // 检查队列是否为空
    bool isEmpty() {
        return front == rear;
    }

    // 获取大小
    int getSize() {
        return (rear - front + capacity) % capacity;
    }

    // 扩容
    void resize(int newCapacity) {
        int* newData = new int[newCapacity];
        int size = getSize();
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % capacity];
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
        front = 0;
        rear = size;
    }

    // 析构函数
    ~Queue() {
        delete[] data;
    }
};

非线性数据结构

树

树是一种非线性数据结构，由节点和边组成，具有层次结构。

二叉树

二叉树是每个节点最多有两个子节点的树结构。

遍历方式：

  • 前序遍历（根-左-右）
  • 中序遍历（左-根-右）
  • 后序遍历（左-右-根）
  • 层序遍历（广度优先）

实现与遍历：

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BinaryTree {
private:
    TreeNode* root;

    // 前序遍历
    void preOrderTraversal(TreeNode* node) {
        if (node == nullptr) {
            return;
        }
        cout << node->val << " ";
        preOrderTraversal(node->left);
        preOrderTraversal(node->right);
    }

    // 中序遍历
    void inOrderTraversal(TreeNode* node) {
        if (node == nullptr) {
            return;
        }
        inOrderTraversal(node->left);
        cout << node->val << " ";
        inOrderTraversal(node->right);
    }

    // 后序遍历
    void postOrderTraversal(TreeNode* node) {
        if (node == nullptr) {
            return;
        }
        postOrderTraversal(node->left);
        postOrderTraversal(node->right);
        cout << node->val << " ";
    }

public:
    // 初始化
    BinaryTree() : root(nullptr) {}

    // 插入节点（简单实现）
    void insert(int value) {
        if (root == nullptr) {
            root = new TreeNode(value);
            return;
        }
        Queue queue;
        queue.enqueue(reinterpret_cast<int>(root));
        while (!queue.isEmpty()) {
            TreeNode* node = reinterpret_cast<TreeNode*>(queue.dequeue());
            if (node->left == nullptr) {
                node->left = new TreeNode(value);
                return;
            } else {
                queue.enqueue(reinterpret_cast<int>(node->left));
            }
            if (node->right == nullptr) {
                node->right = new TreeNode(value);
                return;
            } else {
                queue.enqueue(reinterpret_cast<int>(node->right));
            }
        }
    }

    // 前序遍历
    void preOrder() {
        preOrderTraversal(root);
        cout << endl;
    }

    // 中序遍历
    void inOrder() {
        inOrderTraversal(root);
        cout << endl;
    }

    // 后序遍历
    void postOrder() {
        postOrderTraversal(root);
        cout << endl;
    }

    // 层序遍历
    void levelOrder() {
        if (root == nullptr) {
            return;
        }
        Queue queue;
        queue.enqueue(reinterpret_cast<int>(root));
        while (!queue.isEmpty()) {
            TreeNode* node = reinterpret_cast<TreeNode*>(queue.dequeue());
            cout << node->val << " ";
            if (node->left != nullptr) {
                queue.enqueue(reinterpret_cast<int>(node->left));
            }
            if (node->right != nullptr) {
                queue.enqueue(reinterpret_cast<int>(node->right));
            }
        }
        cout << endl;
    }

    // 析构函数（简化实现）
    ~BinaryTree() {
        // 实际应用中需要实现完整的析构逻辑
    }
};
二叉搜索树

二叉搜索树（BST）是一种特殊的二叉树，满足：

  • 左子树所有节点的值都小于根节点的值
  • 右子树所有节点的值都大于根节点的值
  • 左右子树也都是二叉搜索树

基本操作：

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
class BST {
private:
    TreeNode* root;

    // 搜索
    TreeNode* search(TreeNode* node, int value) {
        if (node == nullptr || node->val == value) {
            return node;
        }
        if (value < node->val) {
            return search(node->left, value);
        } else {
            return search(node->right, value);
        }
    }

    // 插入
    TreeNode* insert(TreeNode* node, int value) {
        if (node == nullptr) {
            return new TreeNode(value);
        }
        if (value < node->val) {
            node->left = insert(node->left, value);
        } else if (value > node->val) {
            node->right = insert(node->right, value);
        }
        return node;
    }

    // 找到最小节点
    TreeNode* findMin(TreeNode* node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }

    // 删除
    TreeNode* remove(TreeNode* node, int value) {
        if (node == nullptr) {
            return nullptr;
        }
        if (value < node->val) {
            node->left = remove(node->left, value);
        } else if (value > node->val) {
            node->right = remove(node->right, value);
        } else {
            // 叶子节点或只有一个子节点
            if (node->left == nullptr) {
                TreeNode* temp = node->right;
                delete node;
                return temp;
            } else if (node->right == nullptr) {
                TreeNode* temp = node->left;
                delete node;
                return temp;
            }
            // 有两个子节点
            TreeNode* temp = findMin(node->right);
            node->val = temp->val;
            node->right = remove(node->right, temp->val);
        }
        return node;
    }

public:
    // 初始化
    BST() : root(nullptr) {}

    // 搜索
    bool search(int value) {
        return search(root, value) != nullptr;
    }

    // 插入
    void insert(int value) {
        root = insert(root, value);
    }

    // 删除
    void remove(int value) {
        root = remove(root, value);
    }
};

堆

堆是一种特殊的完全二叉树，分为两种类型：

  • 小顶堆：任意节点的值<=其子节点的值
  • 大顶堆：任意节点的值>=其子节点的值

基于数组的堆实现（大顶堆）：

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
class MaxHeap {
private:
    int* data;
    int size;
    int capacity;

    // 向上调整
    void shiftUp(int index) {
        while (index > 0 && data[index] > data[(index - 1) / 2]) {
            swap(data[index], data[(index - 1) / 2]);
            index = (index - 1) / 2;
        }
    }

    // 向下调整
    void shiftDown(int index) {
        while (2 * index + 1 < size) {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int maxIndex = left;
            if (right < size && data[right] > data[left]) {
                maxIndex = right;
            }
            if (data[index] >= data[maxIndex]) {
                break;
            }
            swap(data[index], data[maxIndex]);
            index = maxIndex;
        }
    }

public:
    // 初始化
    MaxHeap(int initCapacity = 10) {
        capacity = initCapacity;
        data = new int[capacity];
        size = 0;
    }

    // 入堆
    void push(int value) {
        if (size == capacity) {
            resize(capacity * 2);
        }
        data[size] = value;
        shiftUp(size);
        size++;
    }

    // 出堆
    int pop() {
        if (isEmpty()) {
            throw "Heap is empty";
        }
        int value = data[0];
        swap(data[0], data[size - 1]);
        size--;
        shiftDown(0);
        return value;
    }

    // 访问堆顶元素
    int peek() {
        if (isEmpty()) {
            throw "Heap is empty";
        }
        return data[0];
    }

    // 获取大小
    int getSize() {
        return size;
    }

    // 判断是否为空
    bool isEmpty() {
        return size == 0;
    }

    // 扩容
    void resize(int newCapacity) {
        int* newData = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
    }

    // 析构函数
    ~MaxHeap() {
        delete[] data;
    }
};

哈希表

哈希表（Hash Table）是一种基于哈希函数实现的键值对存储结构，通过将键映射到一个唯一的索引位置来存储和检索值。

哈希冲突解决方法：

  • 链地址法（拉链法）
  • 开放地址法
    • 线性探测法
    • 平方探测法
    • 双哈希法

基于链地址法的哈希表实现：

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
class HashNode {
public:
    int key;
    int value;
    HashNode* next;

    HashNode(int k, int v) : key(k), value(v), next(nullptr) {}
};

class HashTable {
private:
    HashNode** table;
    int size;
    int capacity;

    // 哈希函数
    int hash(int key) {
        return key % capacity;
    }

    // 扩容
    void resize() {
        int newCapacity = capacity * 2;
        HashNode** newTable = new HashNode*[newCapacity];
        for (int i = 0; i < newCapacity; i++) {
            newTable[i] = nullptr;
        }

        // 重新哈希所有元素
        for (int i = 0; i < capacity; i++) {
            HashNode* node = table[i];
            while (node != nullptr) {
                HashNode* next = node->next;
                int newIndex = node->key % newCapacity;
                node->next = newTable[newIndex];
                newTable[newIndex] = node;
                node = next;
            }
        }

        delete[] table;
        table = newTable;
        capacity = newCapacity;
    }

public:
    // 初始化
    HashTable(int initCapacity = 10) {
        capacity = initCapacity;
        size = 0;
        table = new HashNode*[capacity];
        for (int i = 0; i < capacity; i++) {
            table[i] = nullptr;
        }
    }

    // 添加键值对
    void put(int key, int value) {
        if (size >= capacity * 0.75) {
            resize();
        }

        int index = hash(key);
        HashNode* node = table[index];

        // 检查键是否已存在
        while (node != nullptr) {
            if (node->key == key) {
                node->value = value;
                return;
            }
            node = node->next;
        }

        // 键不存在，添加新节点
        HashNode* newNode = new HashNode(key, value);
        newNode->next = table[index];
        table[index] = newNode;
        size++;
    }

    // 获取值
    int get(int key) {
        int index = hash(key);
        HashNode* node = table[index];

        while (node != nullptr) {
            if (node->key == key) {
                return node->value;
            }
            node = node->next;
        }

        throw "Key not found";
    }

    // 删除键值对
    void remove(int key) {
        int index = hash(key);
        HashNode* prev = nullptr;
        HashNode* node = table[index];

        while (node != nullptr) {
            if (node->key == key) {
                if (prev == nullptr) {
                    table[index] = node->next;
                } else {
                    prev->next = node->next;
                }
                delete node;
                size--;
                return;
            }
            prev = node;
            node = node->next;
        }

        throw "Key not found";
    }

    // 获取大小
    int getSize() {
        return size;
    }

    // 析构函数
    ~HashTable() {
        for (int i = 0; i < capacity; i++) {
            HashNode* node = table[i];
            while (node != nullptr) {
                HashNode* next = node->next;
                delete node;
                node = next;
            }
        }
        delete[] table;
    }
};

图

图是一种非线性数据结构，由节点（vertex）和边（edge）组成。

图的表示方法：

  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
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
class Graph {
private:
    int numVertices;
    vector<vector<int>> adjList;

public:
    // 初始化
    Graph(int vertices) {
        numVertices = vertices;
        adjList.resize(vertices);
    }

    // 添加边（无向图）
    void addEdge(int src, int dest) {
        if (src < 0 || src >= numVertices || dest < 0 || dest >= numVertices) {
            throw "Vertex out of range";
        }
        adjList[src].push_back(dest);
        adjList[dest].push_back(src);
    }

    // 添加边（有向图）
    void addDirectedEdge(int src, int dest) {
        if (src < 0 || src >= numVertices || dest < 0 || dest >= numVertices) {
            throw "Vertex out of range";
        }
        adjList[src].push_back(dest);
    }

    // 广度优先遍历
    void BFS(int startVertex) {
        vector<bool> visited(numVertices, false);
        queue<int> q;

        visited[startVertex] = true;
        q.push(startVertex);

        while (!q.empty()) {
            int vertex = q.front();
            q.pop();
            cout << vertex << " ";

            for (int neighbor : adjList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }

    // 深度优先遍历
    void DFSUtil(int vertex, vector<bool>& visited) {
        visited[vertex] = true;
        cout << vertex << " ";

        for (int neighbor : adjList[vertex]) {
            if (!visited[neighbor]) {
                DFSUtil(neighbor, visited);
            }
        }
    }

    void DFS(int startVertex) {
        vector<bool> visited(numVertices, false);
        DFSUtil(startVertex, visited);
        cout << endl;
    }
};

算法

排序算法

冒泡排序

冒泡排序是一种简单的排序算法，通过重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

时间复杂度：O(n²)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        bool swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break; // 优化：如果没有交换，说明已经有序
        }
    }
}

快速排序

快速排序是一种分治排序算法，通过选择一个基准元素，将数组分为两部分，小于基准的元素放在左边，大于基准的元素放在右边，然后递归地对左右两部分进行排序。

时间复杂度：平均 O(n log n)，最坏 O(n²)
空间复杂度：O(log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[high]);
    return i+1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}

归并排序

归并排序是一种分治排序算法，将数组分为两半，分别排序，然后将排序好的两半合并在一起。

时间复杂度：O(n log n)
空间复杂度：O(n)

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
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    int* L = new int[n1];
    int* R = new int[n2];

    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    // 合并临时数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    delete[] L;
    delete[] R;
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

搜索算法

二分搜索

二分搜索是一种在有序数组中查找特定元素的搜索算法，通过不断将搜索范围缩小一半来实现。

时间复杂度：O(log n)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 未找到
}

图算法

广度优先搜索（BFS）

广度优先搜索是一种图遍历算法，从起始节点开始，先访问所有邻居节点，然后再访问邻居的邻居，以此类推。

时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void BFS(Graph& graph, int startVertex) {
    int numVertices = graph.getNumVertices();
    vector<bool> visited(numVertices, false);
    queue<int> q;

    visited[startVertex] = true;
    q.push(startVertex);

    while (!q.empty()) {
        int vertex = q.front();
        q.pop();
        cout << vertex << " ";

        vector<int> neighbors = graph.getNeighbors(vertex);
        for (int neighbor : neighbors) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    cout << endl;
}

深度优先搜索（DFS）

深度优先搜索是一种图遍历算法，从起始节点开始，尽可能深地访问图的节点，直到无法继续，然后回溯。

时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void DFSUtil(Graph& graph, int vertex, vector<bool>& visited) {
    visited[vertex] = true;
    cout << vertex << " ";

    vector<int> neighbors = graph.getNeighbors(vertex);
    for (int neighbor : neighbors) {
        if (!visited[neighbor]) {
            DFSUtil(graph, neighbor, visited);
        }
    }
}

void DFS(Graph& graph, int startVertex) {
    int numVertices = graph.getNumVertices();
    vector<bool> visited(numVertices, false);
    DFSUtil(graph, startVertex, visited);
    cout << endl;
}

动态规划

动态规划是一种解决复杂问题的方法，通过将问题分解为子问题，存储子问题的解，避免重复计算。

斐波那契数列

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
// 递归实现（效率低）
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}

// 动态规划实现
int fibonacciDP(int n) {
    if (n <= 1) {
        return n;
    }
    vector<int> dp(n+1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// 优化空间复杂度
int fibonacciOpt(int n) {
    if (n <= 1) {
        return n;
    }
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length();
    int n = text2.length();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    return dp[m][n];
}

总结

数据结构与算法是计算机科学的核心基础，掌握它们对于编写高效、可靠的代码至关重要。本笔记涵盖了常见的数据结构（数组、链表、栈、队列、树、堆、哈希表、图）和算法（排序、搜索、图算法、动态规划），并提供了详细的实现示例。

学习数据结构与算法的最佳方法是：

  1. 理解基本概念和原理
  2. 学习经典实现
  3. 做大量练习题（如 LeetCode）
  4. 在实际项目中应用

通过不断学习和实践，你将能够熟练掌握数据结构与算法，并在解决实际问题时选择合适的方法。