了解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;
}

上述代码实现了一个字符串匹配的功能。