其他数据结构简单实现

在C++面试中，实现一些常见的数据结构是一个经典的考察点。面试官通常会通过这些题目来评估候选人对C++语言特性、内存管理、算法和数据结构的理解。以下是一些常见的需要实现的数据结构，以及它们的核心实现思路和注意事项。

---

*1. 动态数组（类似 std::vector）*

核心功能

• 动态扩容：当容量不足时，重新分配更大的内存空间。
• 支持随机访问（通过下标）。
• 提供 push_back、pop_back、size、capacity 等基本操作。

实现要点

• 使用指针管理动态内存。
• 实现扩容策略（通常是2倍扩容）。
• 注意深拷贝和析构函数的内存管理。

示例代码

template <typename T>
class MyVector {
private:
    T* data;
    size_t size;
    size_t capacity;

    void resize(size_t newCapacity) {
        T* newData = new T[newCapacity];
        for (size_t i = 0; i < size; ++i) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
    }

public:
    MyVector() : data(nullptr), size(0), capacity(0) {}

    ~MyVector() {
        delete[] data;
    }

    void push_back(const T& value) {
        if (size >= capacity) {
            resize(capacity == 0 ? 1 : capacity * 2);
        }
        data[size++] = value;
    }

    void pop_back() {
        if (size > 0) {
            --size;
        }
    }

    T& operator[](size_t index) {
        return data[index];
    }

    size_t getSize() const {
        return size;
    }

    size_t getCapacity() const {
        return capacity;
    }
};

---

*2. 链表（类似 std::list）*

核心功能

• 支持在头部和尾部插入、删除节点。
• 支持遍历。

实现要点

• 定义节点结构（包含数据和指向下一个节点的指针）。
• 注意头指针和尾指针的管理。
• 实现深拷贝和析构函数。

示例代码

template <typename T>
class MyList {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& value) : data(value), next(nullptr) {}
    };

    Node* head;
    Node* tail;

public:
    MyList() : head(nullptr), tail(nullptr) {}

    ~MyList() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    void push_back(const T& value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    void pop_front() {
        if (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
            if (!head) tail = nullptr;
        }
    }

    void print() const {
        Node* current = head;
        while (current) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

---

*3. 栈（类似 std::stack）*

核心功能

• 支持 push、pop、top 操作。
• 后进先出（LIFO）的特性。

实现要点

• 可以使用动态数组或链表实现。
• 注意边界条件（如空栈时的 pop 和 top）。

示例代码

template <typename T>
class MyStack {
private:
    MyVector<T> data;

public:
    void push(const T& value) {
        data.push_back(value);
    }

    void pop() {
        if (!data.getSize()) {
            throw std::out_of_range("Stack is empty");
        }
        data.pop_back();
    }

    T top() const {
        if (!data.getSize()) {
            throw std::out_of_range("Stack is empty");
        }
        return data[data.getSize() - 1];
    }

    bool empty() const {
        return data.getSize() == 0;
    }
};

---

*4. 队列（类似 std::queue）*

核心功能

• 支持 push、pop、front 操作。
• 先进先出（FIFO）的特性。

实现要点

• 可以使用链表实现（方便在头部删除和尾部插入）。
• 注意边界条件（如空队列时的 pop 和 front）。

示例代码

template <typename T>
class MyQueue {
private:
    MyList<T> data;

public:
    void push(const T& value) {
        data.push_back(value);
    }

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

    T front() const {
        if (data.empty()) {
            throw std::out_of_range("Queue is empty");
        }
        return data.front();
    }

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

---

5. 二叉树

核心功能

• 支持插入、删除、查找节点。
• 支持遍历（前序、中序、后序）。

实现要点

• 定义节点结构（包含数据、左子节点和右子节点指针）。
• 递归实现遍历和插入操作。

示例代码

template <typename T>
class BinaryTree {
private:
    struct Node {
        T data;
        Node* left;
        Node* right;
        Node(const T& value) : data(value), left(nullptr), right(nullptr) {}
    };

    Node* root;

    void insert(Node*& node, const T& value) {
        if (!node) {
            node = new Node(value);
        } else if (value < node->data) {
            insert(node->left, value);
        } else {
            insert(node->right, value);
        }
    }

    void inorder(Node* node) const {
        if (node) {
            inorder(node->left);
            std::cout << node->data << " ";
            inorder(node->right);
        }
    }

public:
    BinaryTree() : root(nullptr) {}

    void insert(const T& value) {
        insert(root, value);
    }

    void inorder() const {
        inorder(root);
        std::cout << std::endl;
    }
};

---

*6. 哈希表（类似 std::unordered_map）*

核心功能

• 支持插入、删除、查找键值对。
• 处理哈希冲突（如链地址法）。

实现要点

• 定义哈希函数。
• 使用数组存储桶，每个桶是一个链表（用于处理冲突）。
• 注意扩容和重新哈希。

示例代码

template <typename K, typename V>
class MyHashMap {
private:
    struct Node {
        K key;
        V value;
        Node* next;
        Node(const K& k, const V& v) : key(k), value(v), next(nullptr) {}
    };

    std::vector<Node*> buckets;
    size_t bucketSize;

    size_t hash(const K& key) const {
        return std::hash<K>{}(key) % bucketSize;
    }

public:
    MyHashMap(size_t size = 100) : bucketSize(size), buckets(size, nullptr) {}

    void insert(const K& key, const V& value) {
        size_t index = hash(key);
        Node* node = new Node(key, value);
        node->next = buckets[index];
        buckets[index] = node;
    }

    V* find(const K& key) {
        size_t index = hash(key);
        Node* current = buckets[index];
        while (current) {
            if (current->key == key) {
                return &(current->value);
            }
            current = current->next;
        }
        return nullptr;
    }
};

---

总结