Usuwanie elementów z tablicy w C

Question

mam tylko proste pytanie o tablice w C

Jaki jest najlepszy sposób, aby usunąć elementy z tablicy oraz w procesie zrobić tablica mniejsza.

to znaczy, że tablica ma rozmiar n, wtedy biorę elementy z tablicy, a wtedy tablica rośnie mniej o kwotę, z której ją usunąłem.

zasadniczo traktuję tablicę jak talię kart, a kiedy wyjmę kartę z wierzchu talii, nie powinno już tam być.

EDYCJA: Mam zamiar doprowadzać się do szału przed końcem dnia, dziękuję za wszelką pomoc, próbuję wymieniać wartości, ale to nie działa poprawnie.

#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

Naprawdę nie chcesz przenosić pamięci za każdym razem, gdy coś usuniesz. Jeśli znasz grubszy rozmiar swojej talii , wybierz odpowiedni rozmiar dla swojej tablicy i utrzymuj wskaźnik na bieżącym końcu z listy. To jest stack.

Jeśli nie znasz rozmiaru swojej talii i myślisz, że może ona stać się naprawdę duża, a także ciągle zmienia się rozmiar, to musisz zrobić coś nieco bardziej skomplikowanego i wdrożyć linked-list.

W języku C masz dwa proste sposoby na zadeklarowanie tablicy.

1. na stos, a statyczny tablicy

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

2. na hałdy jako dynamicznie przydzielonej tablicy

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

standardowe C nie pozwalają macierze albo rozmiar tych typów można zmienić. Możesz utworzyć nową tablicę o określonym rozmiarze, a następnie skopiować zawartość starej tablicy do nowej, lub możesz zastosować jedną z powyższych sugestii dla innego abstrakcyjnego typu danych (np .: lista powiązana, stos, kolejka, itp).

Answer 2

Istnieją naprawdę dwa oddzielne problemy. Pierwszy polega na utrzymaniu elementów tablicy we właściwej kolejności, tak aby po usunięciu elementu nie było "dziur". Drugi to zmiana rozmiaru samej tablicy.

Tablice w C są przydzielane jako stała liczba sąsiednich elementów. Nie ma sposobu, aby faktycznie usunąć pamięć używaną przez indywidualny element w tablicy, ale elementy można przesuwać w celu wypełnienia otworu wykonanego przez usunięcie elementu. Na przykład:

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]; 
} 

Statycznie przydzielone tablice nie mogą być zmieniane. Dynamicznie przydzielane tablice można zmieniać za pomocą funkcji realloc(). To potencjalnie przeniesie całą tablicę do innej lokalizacji w pamięci, więc wszystkie wskaźniki do tablicy lub jej elementów będą musiały zostać zaktualizowane. Na przykład:

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 zwróci NULL wskaźnik, jeśli żądany rozmiar wynosi 0 lub jeśli wystąpił błąd. W przeciwnym razie zwraca wskaźnik do ponownie przydzielonej tablicy.Wskaźnik tymczasowy służy do wykrywania błędów podczas wywoływania realloc, ponieważ zamiast wychodzić z niego można po prostu pozostawić oryginalną tablicę taką, jaka była. Kiedy realloc nie może ponownie przydzielić tablicy, nie zmienia oryginalnej tablicy.

Należy zauważyć, że obie te operacje będą dość powolne, jeśli macierz jest duża lub jeśli usunięto wiele elementów. Istnieją inne struktury danych, takie jak połączone listy i skróty, które mogą być używane, jeśli efektywne wstawianie i usuwanie jest priorytetem.

Answer 3

Co ciekawe tablica jest losowo dostępna w indeksie. A usunięcie losowego elementu może również wpłynąć na indeksy innych elementów.

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 
    } 

Zauważ, że memcpy nie zadziała w tym przypadku ze względu na pamięć zakładkowym.

Jednym ze skutecznych sposobów (lepszego niż przeniesienie pamięci) do usunięcia jednego elementu losowego jest zamiana z ostatnim elementem.

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 
    } 

Ale kolejność jest zmieniana po usunięciu.

Ponownie, jeśli usuwanie zostanie wykonane w pętli, zmiana kolejności może wpłynąć na przetwarzanie. Przenoszenie pamięci jest jedną z drogich alternatyw dla zachowania porządku przy usuwaniu elementu tablicy. Innym sposobem utrzymania porządku w pętli jest odroczenie usunięcia. Można to zrobić za pomocą tablicy poprawności tego samego rozmiaru.

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

Spowoduje to utworzenie rzadkiej tablicy. Na koniec, rzadka tablica może być zwarta (nie zawiera dwóch ważnych elementów, które zawierają między nimi nieprawidłowy element), wykonując pewne zmiany kolejności.

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 
    }