使用C++实现常用数据结构

一、线性数据结构

线性数据结构是指数据元素之间存在一对一的相邻关系的数据结构。常见的线性数据结构包括数组、链表和栈。

1. 数组

template <class T>
class Array {
public:
    explicit Array(int size): size_(size) {
        data_ = new T[size];
    }
    
    ~Array() {
        delete [] data_;
    }
    
    T& operator[](int idx) {
        if (idx >= size_) {
            throw std::out_of_range("Out of range");
        }
        return data_[idx];
    }
    
    int size() const {
        return size_;
    }
    
private:
    T* data_;
    int size_;
};

数组是一组具有相同数据类型的数据元素按照一定的顺序排列而成，并使用一个名字命名。数组有一个重要的特点就是随机访问，而且访问速度非常快。

2. 链表

template<class T>
struct Node {
    T val;
    Node<T>* next;
    Node(T val):val(val), next(nullptr) {
        // Constructor
    }
};
template<class T>
class LinkedList {
public:
    LinkedList(): head(nullptr) {

    }

    ~LinkedList() {
        while (head) {
            Node<T>* next = head->next;
            delete head;
            head = next;
        }
    }

    void insert(T val) {
        Node<T>* node = new Node<T>(val);
        if (!head) {
            head = node;
            return;
        }

        Node<T>* tmp = head;
        while (tmp->next) {
            tmp = tmp->next;
        }
        tmp->next = node;
    }

    bool deleteNode(T val) {
        if (!head) {
            return false;
        }

        if (head->val == val) {
            Node<T>* tmp = head->next;
            delete head;
            head = tmp;
            return true;
        }

        Node<T>* cur = head;
        while (cur->next) {
            if (cur->next->val == val) {
                Node<T>* tmp = cur->next->next;
                delete cur->next;
                cur->next = tmp;
                return true;
            }
            cur = cur->next;
        }
        return false;
    }

    void print() {
        Node<T>* cur = head;
        while (cur) {
            std::cout << cur->val << " ";
            cur = cur->next;
        }
    }

private:
    Node<T>* head;
};

链表是由多个节点组成，每个节点包含了一个元素和一个指向下一个节点的指针。链表的优点在于可以任意增加或删除节点，但缺点在于不能像数组那样快速的随机访问。

3. 栈

template<class T>
class Stack {
public:
    Stack() {

    }

    ~Stack() {
        while (!data.empty()) {
            data.pop();
        }
    }

    bool empty() const {
        return data.empty();
    }

    T top() const {
        return data.top();
    }

    void push(T value) {
        data.push(value);
    }

    void pop() {
        data.pop();
    }

private:
    std::stack<T> data;
};

栈是一种后进先出的数据结构，由于后加入的元素最先被访问到，所以只允许在末尾进行插入和删除操作。

二、非线性数据结构

非线性数据结构是指元素之间存在一对多、多对一或多对多的关系，常见的非线性数据结构包括二叉树、堆和图。

1. 二叉树

template<class T>
struct TreeNode {
    T val;
    TreeNode<T>* left;
    TreeNode<T>* right;
    TreeNode(T val): val(val), left(nullptr), right(nullptr) {

    }
};

template<class T>
class BinaryTree {
public:
    BinaryTree(): root(nullptr) {

    }

    void insert(T val) {
        insert(root, val);
    }

    bool find(T val) {
        return find(root, val);
    }

    void preOrder() {
        preOrder(root);
    }

    void inOrder() {
        inOrder(root);
    }

    void postOrder() {
        postOrder(root);
    }

private:
    void insert(TreeNode<T>*& node, T val) {
        if (!node) {
            node = new TreeNode<T>(val);
            return;
        }
        if (val < node->val) {
            insert(node->left, val);
        } else if (val > node->val) {
            insert(node->right, val);
        }
    }

    bool find(TreeNode<T>* node, T val) {
        if (!node) {
            return false;
        }
        if (node->val == val) {
            return true;
        }
        if (val < node->val) {
            return find(node->left, val);
        } else {
            return find(node->right, val);
        }
    }

    void preOrder(TreeNode<T>* node) {
        if (!node) {
            return;
        }
        std::cout << node->val << " ";
        preOrder(node->left);
        preOrder(node->right);
    }

    void inOrder(TreeNode<T>* node) {
        if (!node) {
            return;
        }
        inOrder(node->left);
        std::cout << node->val << " ";
        inOrder(node->right);
    }

    void postOrder(TreeNode<T>* node) {
        if (!node) {
            return;
        }
        postOrder(node->left);
        postOrder(node->right);
        std::cout << node->val << " ";
    }

private:
    TreeNode<T>* root;
};

二叉树是一种每个节点最多有两个子节点的树结构，其中一个节点是其左子节点，另一个是其右子节点。二叉树的遍历方法包括前序遍历(pre-order)、中序遍历(in-order)和后序遍历(post-order)。

2. 堆

template <class T>
class Heap {
public:
    explicit Heap(int capacity) : capacity_(capacity), size_(0) {
        data_ = new T[capacity_];
    }

    ~Heap() {
        delete [] data_;
    }

    void insert(T element) {
        if (size_ == capacity_) {
            throw std::out_of_range("Full heap");
        }

        int i = size_;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (data_[parent] <= element) {
                break;
            }
            data_[i] = data_[parent];
            i = parent;
        }
        data_[i] = element;
        size_++;
    }

    T min() const {
        if (size_ == 0) {
            throw std::out_of_range("Heap is empty");
        }
        return data_[0];
    }

    void deleteMin() {
        if (size_ == 0) {
            throw std::out_of_range("Heap is empty");
        }

        size_--;
        T last = data_[size_];
        int i = 0;
        int child = 1;
        while (child <= size_) {
            if (child < size_ && data_[child] > data_[child + 1]) {
                child++;
            }
            if (last <= data_[child]) {
                break;
            }
            data_[i] = data_[child];
            i = child;
            child = 2 * i + 1;
        }
        data_[i] = last;
    }

private:
    T* data_;
    int capacity_;
    int size_;
};

堆是一个具有特殊性质的完全二叉树，堆的根节点的元素是所有元素中最小的或最大的。

3. 图

template<class T>
class Graph {
public:
    void addVertex(T val) {
        if (adjList_.find(val) == adjList_.end()) {
            adjList_[val] = std::vector<T>();
        }
    }

    void addEdge(T from, T to) {
        if (adjList_.find(from) == adjList_.end() || adjList_.find(to) == adjList_.end()) {
            return;
        }
        adjList_[from].push_back(to);
    }

    void bfs(T startVertex) const {
        std::unordered_set<T> visited;
        std::queue<T> q;
        visited.insert(startVertex);
        q.push(startVertex);

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

            for (const auto& neighbor : adjList_.at(vertex)) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
    }

    void dfs(T startVertex) const {
        std::unordered_set<T> visited;
        dfs(startVertex, visited);
    }

private:
    std::unordered_map<T, std::vector<T>> adjList_;

    void dfs(T vertex, std::unordered_set<T>& visited) const {
        visited.insert(vertex);
        std::cout << vertex << " ";

        for (const auto& neighbor : adjList_.at(vertex)) {
            if (visited.find(neighbor) == visited.end()) {
                dfs(neighbor, visited);
            }
        }
    }
};

图是由多个顶点（vertex）和边（edge）连接起来而成的，边代表两个顶点之间的关系。图有两种可能性：有向图（directed graph）和无向图（undirected graph），其中有向图的边是有顺序的。