repetidos - Eliminando elementos de una matriz en C

eliminar un elemento de un arreglo en java

Question

Acabo de tener una pregunta sencilla sobre matrices en C

¿Cuál es la mejor manera de eliminar elementos de una matriz y, en el proceso, hacer que la matriz sea más pequeña?

es decir, la matriz es de tamaño n, luego saco elementos de la matriz y luego la matriz se hace más pequeña por la cantidad de la que la eliminé.

Básicamente, trato el conjunto como un mazo de cartas y una vez que saque una carta de la parte superior del mazo, ya no debería estar allí.

EDITAR: Me voy a volver loco antes de que termine el día, gracias por toda la ayuda que estoy tratando de cambiar de valor pero no está funcionando bien.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
enum faces{Ace = 0, Jack = 10, Queen, King};
char * facecheck(int d);
int draw(int deck, int i);
int main()
{
int deck[52], i, n;
char suits[4][9] =
{
"Hearts",
"Diamonds",
"Clubs",
"Spades"};
n = 0;
for(i = 0; i<52; i++)
{
deck[i] = n;
n++;
};
for(i=0; i<52; i++)
{
if(i%13 == 0 || i%13 == 10 || i%13 == 11 || i%13 == 12)
printf("%s ", facecheck(i%13) );
else printf("%d ", i%13+1);
printf("of %s /n", suits[i/13]);
}
draw(deck, i);
return 0;
}
char * facecheck(int d)
{
static char * face[] =
{
"Ace",
"Jack",
"Queen",
"King" };
if(d == Ace)
return face[0];
else
{
if(d == Jack)
return face[1];
else
{
if(d == Queen)
return face[2];
else
{
if(d == King)
return face[3];
}
}
}
}
int draw(int deck,int i )
{
int hand[5], j, temp[j];
for(i=0; i<52; i++)
{
j = i
};
for(i = 0; i < 5; i++)
{
deck[i] = hand[];
printf("A card has been drawn /n");
deck[i] = temp[j-1];
temp[j] = deck[i];
};
return deck;
}

Answer 1

Curiosamente, la matriz es accesible al azar por el índice. Y la eliminación aleatoria de un elemento puede afectar también a los índices de otros elementos.

 int remove_element(int*from, int total, int index) {
if((total - index - 1) > 0) {
memmove(from+i, from+i+1, sizeof(int)*(total-index-1));
}
return total-1; // return the new array size
}

Tenga en cuenta que memcpy no funcionará en este caso debido a la superposición de memoria.

Una de las formas eficientes (mejor que el movimiento de memoria) para eliminar un elemento aleatorio es intercambiar con el último elemento.

 int remove_element(int*from, int total, int index) {
if(index != (total-1))
from[index] = from[total-1];
return total; // **DO NOT DECREASE** the total here
}

Pero el orden se cambia después de la eliminación.

Nuevamente, si la eliminación se realiza en una operación de bucle, la reordenación puede afectar el procesamiento. El movimiento de memoria es una alternativa costosa para mantener el orden mientras se elimina un elemento de matriz. Otra de las formas de mantener el orden mientras está en un bucle es aplazar la eliminación. Se puede hacer mediante una matriz de validez del mismo tamaño.

 int remove_element(int*from, int total, int*is_valid, int index) {
is_valid[index] = 0;
return total-1; // return the number of elements
}

Se creará una matriz dispersa. Finalmente, la matriz dispersa se puede hacer compacta (que no contiene dos elementos válidos que contengan elementos no válidos entre ellos) haciendo un reordenamiento.

 int sparse_to_compact(int*arr, int total, int*is_valid) {
int i = 0;
int last = total - 1;
// trim the last invalid elements
for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements from last
// now we keep swapping the invalid with last valid element
for(i=0; i < last; i++) {
if(is_valid[i])
continue;
arr[i] = arr[last]; // swap invalid with the last valid
last--;
for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements
}
return last+1; // return the compact length of the array
}

Answer 2

Realmente hay dos cuestiones separadas. El primero es mantener los elementos de la matriz en el orden correcto para que no haya "agujeros" después de eliminar un elemento. El segundo es realmente cambiar el tamaño de la matriz en sí.

Las matrices en C se asignan como un número fijo de elementos contiguos. No hay manera de eliminar realmente la memoria utilizada por un elemento individual en la matriz, pero los elementos se pueden desplazar para rellenar el orificio creado al eliminar un elemento. Por ejemplo:

void remove_element(array_type *array, int index, int array_length)
{
int i;
for(i = index; i < array_length - 1; i++) array[i] = array[i + 1];
}

Las matrices asignadas estáticamente no se pueden redimensionar. Las matrices asignadas dinámicamente se pueden redimensionar con realloc (). Esto potencialmente moverá la matriz completa a otra ubicación en la memoria, por lo que todos los punteros a la matriz o a sus elementos deberán actualizarse. Por ejemplo:

remove_element(array, index, array_length); /* First shift the elements, then reallocate */
array_type *tmp = realloc(array, (array_length - 1) * sizeof(array_type) );
if (tmp == NULL && array_length > 1) {
/* No memory available */
exit(EXIT_FAILURE);
}
array_length = array_length - 1;
array = tmp;

realloc devolverá un puntero NULO si el tamaño solicitado es 0, o si hay un error. De lo contrario, devuelve un puntero a la matriz reasignada. El puntero temporal se usa para detectar errores al llamar a realloc porque, en lugar de salir, también es posible dejar la matriz original como estaba. Cuando realloc no puede reasignar una matriz, no altera la matriz original.

Tenga en cuenta que ambas operaciones serán bastante lentas si la matriz es grande o si se eliminan muchos elementos. Existen otras estructuras de datos, como listas vinculadas y hashes, que pueden usarse si la inserción y eliminación eficientes es una prioridad.

Answer 3

Realmente no desea reasignar la memoria cada vez que elimine algo. Si conoce el tamaño aproximado de su plataforma , elija un tamaño apropiado para su matriz y mantenga un puntero al final actual de la lista. Esta es una stack .

Si no sabes el tamaño de tu mazo y crees que podría volverse muy grande y cambiar de tamaño, entonces tendrás que hacer algo un poco más complejo e implementar una linked-list .

En C, tienes dos formas simples de declarar una matriz.

1. En la pila, como una matriz estática.

   int myArray[16]; // Static array of 16 integers

2. En el montón, como una matriz asignada dinámicamente

   // Dynamically allocated array of 16 integers
   int* myArray = calloc(16, sizeof(int));

El estándar C no permite cambiar el tamaño de las matrices de ninguno de estos tipos. Puede crear una nueva matriz de un tamaño específico, luego copiar el contenido de la matriz anterior a la nueva, o puede seguir una de las sugerencias anteriores para un tipo de datos abstracto diferente (por ejemplo: lista vinculada, pila, cola, etc).