了解C++的數據結構和算法實現

一、什麼是數據結構和算法

在計算機科學中，數據結構是硬件和軟件組合在一起，用於組織和存儲數據的方式。算法則是指解決問題的一系列清晰指令集合，也常被稱為邏輯或過程。數據結構和算法是計算機科學的基礎，幾乎在所有領域都有應用。

數據結構可分為線性數據結構和非線性數據結構，線性數據結構包括數組、鏈表、棧和隊列等，非線性數據結構包括樹和圖等。算法方面則可分為查找算法、排序算法和字符串匹配算法等。

二、常見的數據結構實現

在C++中，常見的數據結構實現方式有數組，鏈表和樹等。

1、數組

#include <iostream>
#include <array>
using namespace std;

void printArray(array<int, 5> arr) {
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    array<int, 5> arr = {1, 2, 3, 4, 5};
    printArray(arr);

    arr.fill(0); // 將數組所有元素賦值為0
    printArray(arr);

    arr.swap(array<int, 5> {5, 4, 3, 2, 1}); // 交換數組的元素
    printArray(arr);

    return 0;
}

上述代碼實現了一個數組的創建，遍歷和修改操作。

2、鏈表

#include <iostream>
using namespace std;

class Node {
public:
    int val;
    Node *next;

    Node(int data) {
        val = data;
        next = nullptr;
    }
};

void printLinkedList(Node *head) {
    Node *p = head;
    while (p != nullptr) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    Node *head = new Node(1);
    Node *node1 = new Node(2);
    Node *node2 = new Node(3);
    head->next = node1;
    node1->next = node2;
    printLinkedList(head);
    return 0;
}

上述代碼實現了一個鏈表的創建和遍歷操作。

3、樹

#include <iostream>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int data) {
        val = data;
        left = nullptr;
        right = nullptr;
    }
};

void preorder(TreeNode *root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

void inorder(TreeNode *root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

void postorder(TreeNode *root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    cout << "preorder traversal: ";
    preorder(root);
    cout << endl;

    cout << "inorder traversal: ";
    inorder(root);
    cout << endl;

    cout << "postorder traversal: ";
    postorder(root);
    cout << endl;

    return 0;
}

上述代碼實現了一個二叉樹的創建和三種不同的遍歷方式。

三、常見的算法實現

在C++中，常見的算法實現方式有搜索，排序和字符串匹配等。

1、搜索

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {1, 5, 3, 7, 4};
    int target = 7;
    sort(nums.begin(), nums.end()); // 搜索前需要先排序
    if (binary_search(nums.begin(), nums.end(), target)) {
        cout << "found" << endl;
    } else {
        cout << "not found" << endl;
    }
    return 0;
}

上述代碼實現了一個二分查找的功能。

2、排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {1, 5, 3, 7, 4};
    sort(nums.begin(), nums.end()); // 使用默認的升序排序
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

上述代碼實現了一個排序的功能。

3、字符串匹配

#include <iostream>
#include <string>
#include <regex>
using namespace std;

int main() {
    string str = "hello, world";
    regex pattern("world"); // 定義需要匹配的字符串
    if (regex_search(str, pattern)) {
        cout << "found" << endl;
    } else {
        cout << "not found" << endl;
    }
    return 0;
}

上述代碼實現了一個字符串匹配的功能。