Структуры данных в C++

[Intel]

Руководство по реализации основных структур данных: стек, очередь, связный список.

Реализация стека

#include <iostream>
#include <stdexcept>

template<typename T>
class Stack {
private:
    T* data;
    int top;
    int capacity;
    
public:
    Stack(int size = 100) : capacity(size), top(-1) {
        data = new T[capacity];
    }
    
    ~Stack() {
        delete[] data;
    }
    
    void push(const T& item) {
        if (top >= capacity - 1) {
            throw std::overflow_error("Stack overflow");
        }
        data[++top] = item;
    }
    
    T pop() {
        if (isEmpty()) {
            throw std::underflow_error("Stack underflow");
        }
        return data[top--];
    }
    
    T peek() const {
        if (isEmpty()) {
            throw std::underflow_error("Stack is empty");
        }
        return data[top];
    }
    
    bool isEmpty() const {
        return top == -1;
    }
    
    int size() const {
        return top + 1;
    }
};

int main() {
    Stack<int> stack;
    
    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    std::cout << "Top: " << stack.peek() << std::endl;
    std::cout << "Size: " << stack.size() << std::endl;
    
    while (!stack.isEmpty()) {
        std::cout << stack.pop() << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Реализация очереди

#include <iostream>
#include <stdexcept>

template<typename T>
class Queue {
private:
    T* data;
    int front;
    int rear;
    int capacity;
    int count;
    
public:
    Queue(int size = 100) : capacity(size), front(0), rear(-1), count(0) {
        data = new T[capacity];
    }
    
    ~Queue() {
        delete[] data;
    }
    
    void enqueue(const T& item) {
        if (count >= capacity) {
            throw std::overflow_error("Queue overflow");
        }
        rear = (rear + 1) % capacity;
        data[rear] = item;
        count++;
    }
    
    T dequeue() {
        if (isEmpty()) {
            throw std::underflow_error("Queue underflow");
        }
        T item = data[front];
        front = (front + 1) % capacity;
        count--;
        return item;
    }
    
    T peek() const {
        if (isEmpty()) {
            throw std::underflow_error("Queue is empty");
        }
        return data[front];
    }
    
    bool isEmpty() const {
        return count == 0;
    }
    
    int size() const {
        return count;
    }
};

int main() {
    Queue<int> queue;
    
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);
    
    std::cout << "Front: " << queue.peek() << std::endl;
    
    while (!queue.isEmpty()) {
        std::cout << queue.dequeue() << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Связный список

#include <iostream>

template<typename T>
class LinkedList {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& value) : data(value), next(nullptr) {}
    };
    
    Node* head;
    int size;
    
public:
    LinkedList() : head(nullptr), size(0) {}
    
    ~LinkedList() {
        clear();
    }
    
    void pushFront(const T& value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
        size++;
    }
    
    void pushBack(const T& value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = newNode;
        }
        size++;
    }
    
    void remove(const T& value) {
        if (!head) return;
        
        if (head->data == value) {
            Node* temp = head;
            head = head->next;
            delete temp;
            size--;
            return;
        }
        
        Node* current = head;
        while (current->next && current->next->data != value) {
            current = current->next;
        }
        
        if (current->next) {
            Node* temp = current->next;
            current->next = current->next->next;
            delete temp;
            size--;
        }
    }
    
    bool contains(const T& value) const {
        Node* current = head;
        while (current) {
            if (current->data == value) {
                return true;
            }
            current = current->next;
        }
        return false;
    }
    
    void clear() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
        size = 0;
    }
    
    int getSize() const {
        return size;
    }
    
    void print() const {
        Node* current = head;
        while (current) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    LinkedList<int> list;
    
    list.pushBack(10);
    list.pushBack(20);
    list.pushFront(5);
    
    list.print();
    std::cout << "Size: " << list.getSize() << std::endl;
    
    list.remove(20);
    list.print();
    
    return 0;
}

Бинарное дерево поиска

#include <iostream>

template<typename T>
class BinarySearchTree {
private:
    struct Node {
        T data;
        Node* left;
        Node* right;
        Node(const T& value) : data(value), left(nullptr), right(nullptr) {}
    };
    
    Node* root;
    
    Node* insert(Node* node, const T& value) {
        if (!node) {
            return new Node(value);
        }
        
        if (value < node->data) {
            node->left = insert(node->left, value);
        } else if (value > node->data) {
            node->right = insert(node->right, value);
        }
        
        return node;
    }
    
    bool search(Node* node, const T& value) const {
        if (!node) {
            return false;
        }
        
        if (value == node->data) {
            return true;
        } else if (value < node->data) {
            return search(node->left, value);
        } else {
            return search(node->right, value);
        }
    }
    
    void inorder(Node* node) const {
        if (node) {
            inorder(node->left);
            std::cout << node->data << " ";
            inorder(node->right);
        }
    }
    
    void clear(Node* node) {
        if (node) {
            clear(node->left);
            clear(node->right);
            delete node;
        }
    }
    
public:
    BinarySearchTree() : root(nullptr) {}
    
    ~BinarySearchTree() {
        clear(root);
    }
    
    void insert(const T& value) {
        root = insert(root, value);
    }
    
    bool search(const T& value) const {
        return search(root, value);
    }
    
    void print() const {
        inorder(root);
        std::cout << std::endl;
    }
};

int main() {
    BinarySearchTree<int> bst;
    
    bst.insert(50);
    bst.insert(30);
    bst.insert(70);
    bst.insert(20);
    bst.insert(40);
    
    bst.print();
    
    std::cout << "Search 30: " << (bst.search(30) ? "Found" : "Not found") << std::endl;
    std::cout << "Search 100: " << (bst.search(100) ? "Found" : "Not found") << std::endl;
    
    return 0;
}

Хеш-таблица

#include <iostream>
#include <list>
#include <vector>

template<typename K, typename V>
class HashTable {
private:
    struct Entry {
        K key;
        V value;
        Entry(const K& k, const V& v) : key(k), value(v) {}
    };
    
    std::vector<std::list<Entry>> buckets;
    int capacity;
    int size;
    
    int hash(const K& key) const {
        return std::hash<K>{}(key) % capacity;
    }
    
public:
    HashTable(int cap = 16) : capacity(cap), size(0) {
        buckets.resize(capacity);
    }
    
    void put(const K& key, const V& value) {
        int index = hash(key);
        for (auto& entry : buckets[index]) {
            if (entry.key == key) {
                entry.value = value;
                return;
            }
        }
        buckets[index].emplace_back(key, value);
        size++;
    }
    
    bool get(const K& key, V& value) const {
        int index = hash(key);
        for (const auto& entry : buckets[index]) {
            if (entry.key == key) {
                value = entry.value;
                return true;
            }
        }
        return false;
    }
    
    bool remove(const K& key) {
        int index = hash(key);
        for (auto it = buckets[index].begin(); it != buckets[index].end(); ++it) {
            if (it->key == key) {
                buckets[index].erase(it);
                size--;
                return true;
            }
        }
        return false;
    }
    
    int getSize() const {
        return size;
    }
};

int main() {
    HashTable<std::string, int> map;
    
    map.put("one", 1);
    map.put("two", 2);
    map.put("three", 3);
    
    int value;
    if (map.get("two", value)) {
        std::cout << "two = " << value << std::endl;
    }
    
    std::cout << "Size: " << map.getSize() << std::endl;
    
    return 0;
}

Понимание структур данных - основа эффективного программирования. Эти реализации помогут понять принципы работы основных структур.

 

[Fernando]

Зачем пометка "VIP" если нету скрытого хайда

 

[Intel]

Зачем пометка "VIP" если нету скрытого хайда

Затем что тут в тот момент нельзя было создать тему без префикса

 

[Fernando]

Затем что тут в тот момент нельзя было создать тему без префикса

Понятно