Implementar matriz circular en C++
Este artículo describirá cómo implementar una estructura de datos de array circular en C++.
Implementación de array de usuario para implementación de búfer circular en C++
un array circular es una estructura de datos comúnmente utilizada para implementar una colección de datos similar a una cola. También se conoce con nombres alternativos, como cola circular o búfer en anillo, pero nos referiremos a él como un array circular a lo largo de este artículo.
el array circular tiene un mecanismo FIFO (First In, First Out) para las operaciones de inserción y eliminación de elementos. Por lo general, el búfer tendrá una longitud fija. Si se alcanza la capacidad máxima, el búfer puede rechazar nuevas operaciones de inserción o comenzar a sobrescribir los elementos más antiguos. La última característica es una elección de diseño, y los beneficios deben considerarse para el problema respectivo en cuestión.
En los siguientes ejemplos, implementamos un array circular usando un array de estilo C y construimos una función de inserción para que el búfer completo no comience a sobrescribir datos antiguos.
La clase CircularArray incluye 5 miembros de datos, tres de los cuales tienen el tipo T*, y estos se utilizan para almacenar las direcciones del primero. Los últimos elementos (head y tail respectivamente). El miembro arr sólo se utiliza para facilitar la desasignación de memoria mediante el operador remove. Los dos miembros de datos restantes son tipos integrales que almacenan la capacidad y el tamaño actual del array circular.
El constructor inicializa automáticamente el miembro size a 0, mientras que el valor cap se acepta como parámetro de función y, en consecuencia, se utiliza para asignar la región de memoria requerida. En este punto, los punteros tail y head apuntan a la misma ubicación, que es el primer elemento del array. Sin embargo, recuerde que estos punteros pueden moverse circularmente durante la vida útil del objeto, por lo que debemos controlar las modificaciones correctas cuando se llaman las operaciones de inserción y eliminación.
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
template <typename T>
class CircularArray {
public:
explicit CircularArray(const size_t elems) {
cap = elems;
arr = new T[elems];
tail = head = arr;
size = 0;
};
int enqueue(const T &data);
T *dequeue();
size_t getSize();
~CircularArray();
private:
T *arr = nullptr;
T *head = nullptr;
T *tail = nullptr;
size_t cap;
size_t size;
};
template <typename T>
CircularArray<T>::~CircularArray() {
delete[] arr;
}
template <typename T>
int CircularArray<T>::enqueue(const T &data) {
if (size < cap) {
if (size == 0) {
head = tail = arr;
*tail = data;
size++;
return 0;
}
if (tail == &arr[cap]) {
tail = arr;
*tail = data;
size++;
} else {
tail = tail + 1;
*tail = data;
size++;
}
return 0;
} else {
return -1;
}
}
template <typename T>
T *CircularArray<T>::dequeue() {
if (size != 0) {
auto ret = head;
if (head == &arr[cap]) {
head = arr;
} else {
head = head + 1;
}
size--;
return ret;
} else {
cout << "Array is empty !" << endl;
return nullptr;
}
}
template <typename T>
size_t CircularArray<T>::getSize() {
return size;
}
struct MyClass {
int num;
double num2;
};
int main() {
CircularArray<MyClass> m1(4);
m1.enqueue({1, 1.1});
m1.enqueue({1, 1.2});
m1.enqueue({1, 1.3});
m1.enqueue({1, 1.4});
m1.enqueue({1, 1.5});
m1.enqueue({1, 1.6});
auto size = m1.getSize();
for (size_t i = 0; i < size; ++i) {
auto elem = m1.dequeue();
cout << elem->num << "," << elem->num2 << endl;
}
return EXIT_SUCCESS;
}
Producción :
1,1.1
1,1.2
1,1.3
1,1.4
Para agregar nuevos elementos en el array circular, se debe llamar a la función miembro enqueue. Esta función toma una referencia al objeto genérico y la almacena en la tail del búfer.
La función enqueue devuelve un valor distinto de cero si la inserción no tiene éxito, y el programador es responsable de verificar el valor de retorno correspondiente.
Por otro lado, la función dequeue maneja la operación de eliminación de elementos del head del búfer. Está diseñado para devolver el puntero al elemento eliminado. Se debe comprobar el puntero de retorno antes de acceder a él (desreferenciar) ya que puede tener el valor nullptr. Se devuelve nullptr para indicar que el búfer está vacío y no se pueden eliminar elementos.
Mientras tanto, uno puede acceder de forma segura al número actual de elementos en el búfer usando la función getSize y usar el valor devuelto para iterar sobre la estructura. Aunque no es probable que la iteración se utilice en escenarios del mundo real, el miembro size puede ser un dato importante para implementar funciones de miembro adicionales.
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
template <typename T>
class CircularArray {
public:
explicit CircularArray(const size_t elems) {
cap = elems;
arr = new T[elems];
tail = head = arr;
size = 0;
};
int enqueue(const T &data);
T *dequeue();
size_t getSize();
~CircularArray();
private:
T *arr = nullptr;
T *head = nullptr;
T *tail = nullptr;
size_t cap;
size_t size;
};
template <typename T>
CircularArray<T>::~CircularArray() {
delete[] arr;
}
template <typename T>
int CircularArray<T>::enqueue(const T &data) {
if (size < cap) {
if (size == 0) {
head = tail = arr;
*tail = data;
size++;
return 0;
}
if (tail == &arr[cap]) {
tail = arr;
*tail = data;
size++;
} else {
tail = tail + 1;
*tail = data;
size++;
}
return 0;
} else {
return -1;
}
}
template <typename T>
T *CircularArray<T>::dequeue() {
if (size != 0) {
auto ret = head;
if (head == &arr[cap]) {
head = arr;
} else {
head = head + 1;
}
size--;
return ret;
} else {
cout << "Array is empty !" << endl;
return nullptr;
}
}
template <typename T>
size_t CircularArray<T>::getSize() {
return size;
}
struct MyClass {
int num;
double num2;
};
int main() {
CircularArray<MyClass> m1(4);
m1.dequeue();
m1.enqueue({1, 1.9});
auto elem = m1.dequeue();
if (elem) cout << elem->num << "," << elem->num2 << endl;
return EXIT_SUCCESS;
}
Producción :
Array is empty !
1,1.9
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn FacebookArtículo relacionado - C++ Data Structure
- Destructor de árbol de búsqueda binaria de C++
- Eliminar un nodo del árbol binario de búsqueda en C++
- Estructura de datos de pila usando una lista enlazada en C++
- Implementar Inorder Traversal para el árbol binario de búsqueda en C++
- Implementar una estructura de datos de cola usando una lista vinculada en C++