Требуется разработать на языке С++, без использования сторонних библиотек (стандартные…
- User
Требуется разработать на языке С++, без использования сторонних библиотек (стандартные заголовочные файлы сторонними не являются!) и библиотеки vector , фреймворков и стандартной библиотеки шаблонов следующую программу работы с кучей(элементами кучи являются различные типы данных). В классе должны быть описаны методы добавления, поиска и удаления узла.
- Assistant
Для реализации кучи без использования библиотек vector и стандартной библиотеки шаблонов можно создать класс Heap, который будет хранить данные в виде массива и иметь методы для добавления, поиска и удаления узлов.
Класс Heap будет иметь следующую структуру:
#include <iostream> // для вывода результатов class Heap { private: int* heap; // массив для хранения узлов кучи int size; // размер кучи public: Heap(); // конструктор по умолчанию ~Heap(); // деструктор void insert(int value); // добавить узел в кучу bool search(int value); // найти узел в куче bool remove(int value); // удалить узел из кучи void print(); // вывод текущего состояния кучи };Реализация каждого из методов будет выглядеть следующим образом:
Heap::Heap() { heap = new int[100]; // создаем массив из 100 элементов size = 0; // инициализируем размер кучи } Heap::~Heap() { delete[] heap; // освобождаем память, выделенную для массива } void Heap::insert(int value) { int index = size; // индекс нового узла равен текущему размеру кучи heap[index] = value; // добавляем новый узел в массив size++; // увеличиваем размер кучи // выполняем восстановление свойства кучи (например, с помощью просеивания вверх) while (index > 0 && heap[(index - 1) / 2] < heap[index]) { std::swap(heap[(index - 1) / 2], heap[index]); index = (index - 1) / 2; } } bool Heap::search(int value) { for (int i = 0; i < size; i++) { if (heap[i] == value) { return true; // значение найдено в куче } } return false; // значение не найдено } bool Heap::remove(int value) { for (int i = 0; i < size; i++) { if (heap[i] == value) { // перемещаем последний узел вместо удаляемого heap[i] = heap[size - 1]; size--; // уменьшаем размер кучи // выполняем восстановление свойства кучи (например, с помощью просеивания вниз) while (true) { int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < size && heap[left] > heap[largest]) { largest = left; } if (right < size && heap[right] > heap[largest]) { largest = right; } if (largest != i) { std::swap(heap[i], heap[largest]); i = largest; } else { break; } } return true; // узел удален из кучи } } return false; // узел не найден } void Heap::print() { for (int i = 0; i < size; i++) { std::cout << heap[i] << " "; } std::cout << std::endl; } int main() { Heap heap; heap.insert(6); heap.insert(4); heap.insert(9); heap.insert(2); heap.print(); // выводит: 9 4 6 2 std::cout << heap.search(4) << std::endl; // выводит: 1 (значение 4 найдено) std::cout << heap.search(8) << std::endl; // выводит: 0 (значение 8 не найдено) std::cout << heap.remove(4) << std::endl; // выводит: 1 (узел 4 удален) std::cout << heap.remove(8) << std::endl; // выводит: 0 (узел 8 не найден) heap.print(); // выводит: 9 2 6 return 0; }Это пример реализации кучи на языке C++ без использования библиотек vector и стандартной библиотеки шаблонов. В данном примере куча хранит целочисленные значения, но вы можете легко изменить тип данных, добавлять и удалять элементы по своему усмотрению.
- User
Приведи реаизацию кучи для двух типов данных, на основе данной программы
- Assistant
Для реализации кучи, которая может хранить два различных типа данных, необходимо модифицировать класс Heap, чтобы он был шаблонным.
Пример реализации кучи для двух различных типов данных:
#include <iostream> // для вывода результатов template<typename T, typename U> class Heap { private: struct Node { T key; // ключ узла U value; // значение узла }; Node* heap; // массив для хранения узлов кучи int size; // размер кучи public: Heap(); // конструктор по умолчанию ~Heap(); // деструктор void insert(T key, U value); // добавить узел в кучу bool search(T key); // найти узел в куче bool remove(T key); // удалить узел из кучи void print(); // вывод текущего состояния кучи }; template<typename T, typename U> Heap<T, U>::Heap() { heap = new Node[100]; // создаем массив из 100 элементов size = 0; // инициализируем размер кучи } template<typename T, typename U> Heap<T, U>::~Heap() { delete[] heap; // освобождаем память, выделенную для массива } template<typename T, typename U> void Heap<T, U>::insert(T key, U value) { int index = size; // индекс нового узла равен текущему размеру кучи heap[index].key = key; // добавляем новый узел в массив heap[index].value = value; size++; // увеличиваем размер кучи // выполняем восстановление свойства кучи (например, с помощью просеивания вверх) while (index > 0 && heap[(index - 1) / 2].key < heap[index].key) { std::swap(heap[(index - 1) / 2], heap[index]); index = (index - 1) / 2; } } template<typename T, typename U> bool Heap<T, U>::search(T key) { for (int i = 0; i < size; i++) { if (heap[i].key == key) { return true; // значение найдено в куче } } return false; // значение не найдено } template<typename T, typename U> bool Heap<T, U>::remove(T key) { for (int i = 0; i < size; i++) { if (heap[i].key == key) { // перемещаем последний узел вместо удаляемого heap[i] = heap[size - 1]; size--; // уменьшаем размер кучи // выполняем восстановление свойства кучи (например, с помощью просеивания вниз) while (true) { int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < size && heap[left].key > heap[largest].key) { largest = left; } if (right < size && heap[right].key > heap[largest].key) { largest = right; } if (largest != i) { std::swap(heap[i], heap[largest]); i = largest; } else { break; } } return true; // узел удален из кучи } } return false; // узел не найден } template<typename T, typename U> void Heap<T, U>::print() { for (int i = 0; i < size; i++) { std::cout << "(" << heap[i].key << ", " << heap[i].value << ") "; } std::cout << std::endl; } int main() { Heap<int, std::string> heap1; heap1.insert(6, "value1"); heap1.insert(4, "value2"); heap1.insert(9, "value3"); heap1.insert(2, "value4"); heap1.print(); // выводит: (9, value3) (4, value2) (6, value1) (2, value4) std::cout << heap1.search(4) << std::endl; // выводит: 1 (значение 4 найдено) std::cout << heap1.search(8) << std::endl; // выводит: 0 (значение 8 не найдено) std::cout << heap1.remove(4) << std::endl; // выводит: 1 (узел (4, value2) удален) std::cout << heap1.remove(8) << std::endl; // выводит: 0 (узел (8, ...) не найден) heap1.print(); // выводит: (9, value3) (2, value4) (6, value1) Heap<char, float> heap2; heap2.insert('a', 1.5); heap2.insert('b', 2.3); heap2.insert('c', 3.1); heap2.insert('d', 4.2); heap2.print(); // выводит: (d, 4.2) (c, 3.1) (b, 2.3) (a, 1.5) std::cout << heap2.search('b') << std::endl; // выводит: 1 (значение 'b' найдено) std::cout << heap2.search('e') << std::endl; // выводит: 0 (значение 'e' не найдено) std::cout << heap2.remove('b') << std::endl; // выводит: 1 (узел (b, 2.3) удален) std::cout << heap2.remove('e') << std::endl; // выводит: 0 (узел (e, ...) не найден) heap2.print(); // выводит: (d, 4.2) (a, 1.5) (c, 3.1) return 0; }В данном примере представлены две кучи - heap1 и heap2. Куча heap1 хранит пары (ключ, значение) с типом ключа int и типом значения std::string. Куча heap2 хранит пары (ключ, значение) с типом ключа char и типом значения float. Вы можете легко изменить типы данных и добавлять/удалять элементы по своему усмотрению.
- User
Из предыдущей программы убери 2 типа данных для кучи, оставь шаблонную кучу для одного произвольного типа данных
- Assistant
Конечно, вот пример реализации шаблонной кучи для одного произвольного типа данных:
#include <iostream> // для вывода результатов template<typename T> class Heap { private: T* heap; // массив для хранения узлов кучи int size; // размер кучи public: Heap(); // конструктор по умолчанию ~Heap(); // деструктор void insert(T value); // добавить узел в кучу bool search(T value); // найти узел в куче bool remove(T value); // удалить узел из кучи void print(); // вывод текущего состояния кучи }; template<typename T> Heap<T>::Heap() { heap = new T[100]; // создаем массив из 100 элементов size = 0; // инициализируем размер кучи } template<typename T> Heap<T>::~Heap() { delete[] heap; // освобождаем память, выделенную для массива } template<typename T> void Heap<T>::insert(T value) { int index = size; // индекс нового узла равен текущему размеру кучи heap[index] = value; // добавляем новый узел в массив size++; // увеличиваем размер кучи // выполняем восстановление свойства кучи (например, с помощью просеивания вверх) while (index > 0 && heap[(index - 1) / 2] < heap[index]) { std::swap(heap[(index - 1) / 2], heap[index]); index = (index - 1) / 2; } } template<typename T> bool Heap<T>::search(T value) { for (int i = 0; i < size; i++) { if (heap[i] == value) { return true; // значение найдено в куче } } return false; // значение не найдено } template<typename T> bool Heap<T>::remove(T value) { for (int i = 0; i < size; i++) { if (heap[i] == value) { // перемещаем последний узел вместо удаляемого heap[i] = heap[size - 1]; size--; // уменьшаем размер кучи // выполняем восстановление свойства кучи (например, с помощью просеивания вниз) while (true) { int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < size && heap[left] > heap[largest]) { largest = left; } if (right < size && heap[right] > heap[largest]) { largest = right; } if (largest != i) { std::swap(heap[i], heap[largest]); i = largest; } else { break; } } return true; // узел удален из кучи } } return false; // узел не найден } template<typename T> void Heap<T>::print() { for (int i = 0; i < size; i++) { std::cout << heap[i] << " "; } std::cout << std::endl; } int main() { Heap<int> heap; heap.insert(6); heap.insert(4); heap.insert(9); heap.insert(2); heap.print(); // выводит: 9 4 6 2 std::cout << heap.search(4) << std::endl; // выводит: 1 (значение 4 найдено) std::cout << heap.search(8) << std::endl; // выводит: 0 (значение 8 не найдено) std::cout << heap.remove(4) << std::endl; // выводит: 1 (узел 4 удален) std::cout << heap.remove(8) << std::endl; // выводит: 0 (узел 8 не найден) heap.print(); // выводит: 9 2 6 return 0; }В этом примере использован шаблонный класс Heap, который может хранить элементы любого типа. В данном случае, куча хранит элементы типа int, но вы можете легко изменить тип данных, добавлять и удалять элементы по своему усмотрению.