Διαγραφή συγκεκριμένων στοιχείων πίνακα - C++

dop · 28 Ιουνίου 2007

Says who? Όταν περνάς έναν pointer σε μια συνάρτηση, δεν ξέρεις που δείχνει (free store/stack) και άρα δεν κάνεις υποθέσεις, ΕΚΤΟΣ και αν πρόκειται για δικιά σου βιβλιοθήκη.

alkisg · 28 Ιουνίου 2007

@DirectX: η ταξινόμηση όμως κάνει το πρόβλημα Ο(n^2) [O(n*logn) για qsort] από Ο(n) που είναι... Δεν είναι overkill?

Directx · 28 Ιουνίου 2007

Δεν έχεις άδικο.. απλά μου φάνηκε ένα κάπως ιδιόρρυθμο και σχετικά εύκολο τρικ για διαγραφή & αποδέσμευση της ανάλογη μνήμης από ομαδικές εγγραφές σε ένα κοινό μπλοκ μνήμης από εκεί και πέρα βέβαια το πρόβλημα μετατίθεται στην ταχύτητα του sorting και στο reverse for-loop φυσικά (ή μόνο στο sorting αν ακολουθήσουμε την εκδοχή διαγραφής με την "μία" που έγραψα στο Υ.Γ.) ..

Μια παρόμοια εκδοχή είναι να διαγράφουμε τα προς εύρεση στοιχεία μετακινώντας την επόμενη εγγραφή που τα ακολουθεί στην θέση τους (βλ. post του dop) με την βοήθεια της memmove, οπότε απλά αποδεσμεύουμε ύστερα με μια realloc το τέλος του πίνακα που προκύπτει από την μετακίνηση των στοιχείων.

Ένα πρόβλημα στην υλοποίηση μου είναι πως το for-loop γινότανε ατέρμον αν έχουμε ίδια προς διαγραφή στοιχεία στο τέλος του πίνακα, οπότε πρόσθεσα μια do{ }while() που διαγράφει όμοια στοιχεία από το τέλος προς την αρχή.. -προφανώς υπάρχει καλύτερος τρόπος να γίνει!

Ακολουθεί ο κώδικας:

>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef __BORLANDC__
  #pragma hdrstop
#endif

/*---------------------------------------------------------------------------*/
int   DeleteAll(int *a,int n,int x);
/*---------------------------------------------------------------------------*/
int   QSRT_X;

#define  RECORDS  30

#ifdef __BORLANDC__
  #pragma argsused
#endif
int main(int argc, char* argv[])
{
  int   *ptrTable = NULL, nRecord, nNewRecord;

  if((ptrTable=calloc(RECORDS,sizeof(int)))!=NULL)
   {
     for(nRecord=0;nRecord<RECORDS;nRecord++)
      ptrTable[nRecord] = nRecord;

     ptrTable[0] = 10;
     ptrTable[1] = 10;
     ptrTable[10] = 10;
     ptrTable[11] = 10;
     ptrTable[12] = 10;
     ptrTable[28] = 10;
     ptrTable[29] = 10;

     nNewRecord = DeleteAll(ptrTable,RECORDS,10);

     for(nRecord=0;nRecord<nNewRecord;nRecord++)
      printf("[%d] = %d\n",nRecord,ptrTable[nRecord]);
   }
  free(ptrTable);

  printf(" Press Enter to quit..");
  fgetc(stdin);

  return 0;
}
/*---------------------------------------------------------------------------*/
int   DeleteAll(int *a,int n,int x)
{
  int   nRecord, nData = 0;

  /* Remove last table entry that matches else for-loop becomes infinite */
  do
   {
     nRecord = 0;
     if(a[n-1]==x)
      {
        a = realloc(a,sizeof(int)*(--n));
        nRecord = 1;
      }
   }while(nRecord && a!=NULL);

  /* Did we clean-up a serialized from the end table to NULL? */
  if(a==NULL)
   return 0;

  /* Move-out of table each non-seriali entry that match x */
  for(nRecord=0;nRecord<n;nRecord++)
   if(a[nRecord]==x)
    {
        memmove(&a[nRecord],&a[nRecord+1],sizeof(int)*((n-1)-nRecord));
        nRecord--;
        nData++;
    }

  /* New block length */
  n-=nData;

  /* Reset block length */
  a = realloc(a,sizeof(int)*n);

  return n;
}

Όπως πάντα μπορεί να έχει bugs ...

alkisg · 28 Ιουνίου 2007

Εντωμεταξύ η realloc πιθανώς να αλλάξει την τιμή του pointer, οπότε το νέο a θα πρέπει να επιστραφεί στο κυρίως πρόγραμμα.

Άρα η

int DeleteAll(int *a,int n,int x)

θα έπρεπε να είναι

int DeleteAll(int **a,int n,int x)

ή

int DeleteAll((int *)&a,int n,int x)

Εκτός από αυτό, αν υπάρχουν στο κυρίως πρόγραμμα κι άλλοι pointer που να δείχνουν στην ίδια θέση με το a, θα πρέπει να ενημερωθούν κι αυτοί...

Directx · 29 Ιουνίου 2007

Εντωμεταξύ η realloc πιθανώς να αλλάξει την τιμή του pointer, οπότε το νέο a θα πρέπει να επιστραφεί στο κυρίως πρόγραμμα.

Άρα η

int DeleteAll(int *a,int n,int x)

θα έπρεπε να είναι

int DeleteAll(int **a,int n,int x)

ή

int DeleteAll((int *)&a,int n,int x)

Μπα.. προτίμησα κάτι πιο κλασσικό : Η ρουτίνα επιστρέφει ως return τον ανανεωμένο πίνακα και ως *int τον νέο αριθμό στοιχείων του:

>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef __BORLANDC__
  #pragma hdrstop
#endif

/*---------------------------------------------------------------------------*/
int*  DeleteAll(int *a,int *n,int x);
/*---------------------------------------------------------------------------*/

#define  RECORDS  30

#ifdef __BORLANDC__
  #pragma argsused
#endif
int main(int argc, char* argv[])
{
  int   *ptrTable = NULL, nRecord, 
         nTableSize = RECORDS;

  if((ptrTable=calloc(RECORDS,sizeof(int)))!=NULL)
   {
     for(nRecord=0;nRecord<RECORDS;nRecord++)
      ptrTable[nRecord] = nRecord;

     ptrTable[0] = 10;
     ptrTable[1] = 10;
     ptrTable[10] = 10;
     ptrTable[11] = 10;
     ptrTable[12] = 10;
     ptrTable[27] = 10;
     ptrTable[29] = 10;

     ptrTable = DeleteAll(ptrTable,&nTableSize,10);

     for(nRecord=0;nRecord<nTableSize;nRecord++)
      printf("[%d] = %d\n",nRecord,ptrTable[nRecord]);
   }
  free(ptrTable);

  printf(" Press Enter to quit..");
  fgetc(stdin);

  return 0;
}
/*---------------------------------------------------------------------------*/
int* DeleteAll(int *a,int *n,int x)
{
  /* Remove last table entry that matches else for-loop becomes infinite */
  int   nRecord, nData = 0;

  do
   {
     nRecord = 0;
     if(a[*(int*)n-1]==x)
      {
        a = realloc(a,sizeof(int)*(--*(int*)n));
        nRecord = 1;
      }
   }while(nRecord && a!=NULL);


  /* Did we clean-up a serialized from the end table to NULL? */
  if(a==NULL)
   return a;

  /* Move-out of table each non-serial non-trailing entry that match x */
  for(nRecord=0;nRecord<*(int*)n;nRecord++)
   if(a[nRecord]==x)
    {
        memmove(&a[nRecord],&a[nRecord+1],sizeof(int)*((*(int*)n-1)-nRecord));
        nRecord--;
        nData++;
    }

  /* New block length */
  *(int*)n-=nData;
  a = realloc(a,sizeof(int)*(*(int*)n));

  return a;
}

Όποια άλλη παρατήρηση δεκτή!

bokarinho · 29 Ιουνίου 2007

Ήρθα και εγώ να ταράξω τα ήρεμα καλοκαιρινά νερά με την σειρά μου.

Λοιπόν το κάτωθεν πρόγραμμα κάνει την δουλειά που θέλουμε χωρίς την χρήση realloc, memmove οι οποίες δίνουν ένα κομψό αποτέλεσμα όπως στην περίπτωση του προγράμματος του άνωθεν δημιουργού. Είναι κάτι απλούστερο και νομίζω ότι δουλεύει δίχως λαθάκια.

>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

//Functions.

int *CreateArray(int Asize)
{
   if(Asize > 0)
   {
        int *A = (int *)calloc(Asize, sizeof(int));
        if(A)
             return A;
        else
            return NULL;
   }
   else
   {
       perror("Asize");
       return NULL;
   }
}

void FillRandom(int *A, int Asize, int bottom, int high)
{
    if(A)
    {
         int i = 0;
         int width = high - bottom;
         
         //Check for negative result, we only care for the width.
         
         if(width < 0)
                  width = - width;
                  
         for(i = 0; i < Asize; i++)
               A[i] = (rand() / (double)RAND_MAX) * width + bottom;
    }
}
void FillFromUser(int *A, int Asize)
{
    if(A)
    {
         int i;
         for(i = 0; i < Asize && scanf("%d", &A[i]); i++);
    }
}
void PrintArray(int *A, int Asize)
{
    if(A)
    {
         int i;
         for(i = 0; i < Asize && printf(i != Asize - 1 ? "%d " : "%d\n", A[i]);  i++);
    }
}

int *EraseFromArray(int *A, int Asize, int *n, int *size)
{
   if(A)
   {
        int i = 0;
        int j = 0;
        int *B = NULL;
        int count = 0;
        
        //Count how many times you found n.
        
        for(i = 0; i < Asize; i++)
        {
              if(A[i] == *n)
                      count += 1;
        }
        
        //Create a new array to hold the data.
        if(count != Asize)
        {
        
                 B = (int *)calloc(Asize - count, sizeof(int));
           if(
           {
                 for(i = 0; i < Asize; i++)
                 {
                       if(A[i] == *n)
                            continue;
                       else
                           B[j++] = A[i];
                 }
                 if(j == Asize - count)
                 {
                   *size = j;
                   return B;
                 }
                 else
                 {
                    perror("count");
                    return NULL;
                 }
           }
           else
           {
             perror("calloc");
             return NULL;
           }
       }
       else
       {   
           B = (int *)calloc(count, sizeof(int));
           *size = count;
           return B;
       }
   }
   else
   {
       printf("Array is NULL.\n");
       return NULL;
   }
}
                                          
//Main.

int main(int argc, char *argv[])
{
   int n = 0;
   int size = 0;
   int *BArray = NULL;
   int *Array = CreateArray(10);
   //FillRandom(Array, 10, 0 , 10);
   FillFromUser(Array, 10);
   printf("Give me the element to delete:\n");
   scanf("%d", &n);
   BArray = EraseFromArray(Array , 10, &n, &size);
   PrintArray(Array, 10);
   PrintArray(BArray, size);
   free(Array);
   free(BArray);
 system("PAUSE");	
 return 0;
}

Οτιδήποτε σχόλιο, είναι ευπρόσδεκτο, ευχαριστώ έναν φίλο insomniac για την παρατήρηση του.

Φιλικά, Bokarinho!!

Σύνδεση

Διαγραφή συγκεκριμένων στοιχείων πίνακα - C++

Προτεινόμενες αναρτήσεις

dop

alkisg

Directx

alkisg

Directx

bokarinho

Αρχειοθετημένο

Σύνδεση