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

[Wise_One]

Η άσκηση είναι σχετικά απλή. Βρήκα πώς να τη λύσω, όμως φοβάμαι ότι ο τρόπος μου είναι αρκετά περίπλοκος και ίσως χαζός. Λογικά αυτό που θέλω γίνεται και με λιγότερο κώδικα.

 

Φτιάχνω μέθοδο

>
void removeAll(int a[], int &n, int x)

Αυτή η μέθοδος διαγράφει όλα τα στοιχεία του πίνακα τα οποία είναι ίσα με το χ. Τέλος, επιστρέφει TRUE αν έγινε η διαγραφή και FALSE αν δεν έγινε.

 

Τί σκέφτηκα να κάνω: Φτιάχνω μέθοδο counter() η οποία μετράει πόσες φορές εμφανίζεται ο χ στον πίνακα.

 

Μετά με άλλη μέθοδο hold() κρατάω τις διευθύνσεις μνήμης των α[ι]==χ σε άλλο πίνακα.

 

Η removeAll() καλεί τις υπόλοιπες και διαγράφει τις θέσεις μνήμης ή απλά μηδενίζει τις τιμές. Επιστρέφει true/false ανάλογα με το αποτέλεσμα.

 

Το θέμα με όλο αυτό είναι ότι χρησιμοποιώ πολλές άλλες μεθόδους και η removeAll() δεν κάνει ακριβώς αυτό που πρέπει. Επιπλέον, είναι λίγο μπελάς γιατί κι εγώ κουράστηκα να το σκεφτώ, πόσο μάλλον ο καθηγητής μου που θα το ελέγξει.

 

Ρωτάω λοιπόν αν υπάρχει (που θα υπάρχει) άλλος τρόπος, να κάνω όλη αυτή τη διαδικασία.

 

Μη προτείνετε τίποτα τρελό, πρώτο εξάμηνο είναι που κάνω C++

[parsifal]

Πώς επιστρέφει TRUE/FALSE η μέθοδος, αφού τη δηλώνεις void; Μήπως, εννοείς ότι αποδίδει αυτήν την τιμή στη μεταβλητή n; Γιατί να μην τη δηλώσεις ως εξής:

>int removeAll(int a[], int x)

που είναι και πιο βολικό;

 

Επίσης, πώς ορίζεις ακριβώς τη διαγραφή του στοιχείου με τιμή x; Παίρνει τιμή 0 ή γίνεται μετατόπιση των επομένων στοιχείων κατά μία θέση αριστερά;

[bilco]

Μετά με άλλη μέθοδο hold() κρατάω τις διευθύνσεις μνήμης των α[ι]==χ σε άλλο πίνακα.

 

Η removeAll() καλεί τις υπόλοιπες και διαγράφει τις θέσεις μνήμης ή απλά μηδενίζει τις τιμές. Επιστρέφει true/false ανάλογα με το αποτέλεσμα.

Παρότι δεν πολυκαταλαβαίνω τι εννοείς, αυτό που βρίσκω πιο λογικό είναι να δημιουργείς μέσα στην removeAll έναν προσωρινό πίνακα ίσου μεγέθους με τον a και να αντιγράφεις σε αυτόν τα στοιχεία != x. Κατόπιν τον αντιγράφεις στον a και βάζεις το n ίσο με τον αριθμό των στοιχείων του προσωρινου πίνακα.

[dop]

Αν θέλεις να είναι in-place, θυσιάζεις επεξεργαστική ισχύ για να γλυτώσεις μνήμη (δηλ. δεν κάνεις προσωρινό πίνακα).

 

Αν θέλεις να γίνεται με copy, τότε κάνεις ότι λέει ο bilco.

 

Η πιο απλή λύση είναι η εξής: ψάχνεις τον πίνακα μέχρι να βρεις το στοιχείο και μετά αντιγράφεις τον υπόλοιπο πίνακα από πάνω, κάνοντας ουσιαστικά ολίσθηση κατά ένα.

[chiossif]

Η λύση που προτείνει ο φίλος dop γράφεται κάπως έτσι:

 

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

int removex(int*,int*,int);

int main(){
   int a[10],i,n;
   n=10;
   for (i=0;i<n;i++)
       a[i]=i;
   printf("\nBefore:\n");
   for (i=0;i<n;i++)
       printf("%4d",a[i]);;
   removex(a,&n,6);
   printf("\nAfter:\n");
   for (i=0;i<n;i++)
       printf("%4d",a[i]);;

return 0;
}

int removex(int *a, int *n, int x){
   int retval, i, j;

   retval=0;
   for (i=0;i<*n;i++)
       if (a[i]==x){
           for (j=i+1;j<*n;j++)
               a[j-1]=a[j];
           *n--;
           retval=1;
       }
   return retval;
}

 

1. Όπως κάθε φορά έχει ένα μικρό λαθάκι. Ελπίζω να μην σας δυσκολέψει.

2. Νομίζω ότι μπορεί να γραφτεί καλύτερα (ταχύτερα). Καμιά ιδέα;

 

Παρακαλώ κάθε λύση ας είναι ANSI...

 

(Η λύση είναι σε C και όχι σε C++.)

[Wise_One]

Η αλήθεια είναι πως έγραψα και κάτι παραπάνω βλέποντας την προηγούμενη άσκηση. ΔΕΝ επιστρέφει τίποτα. Και ναι, διαγράφει εκείνο το στοιχείο και μετακινεί όλα τα επόμενα μία θέση κάτω. Αρα την δηλώνω κανονικά void.

 

Θα μελετήσω και τον κώδικα του chiossif. Εύκολα μπορεί να μετατραπεί σε C++.

 

Αν έχετε επιπλέον σχόλια τώρα που διευκρίνισα κάποια πράγματα....

[alkisg]

Η ταχύτερη λύση που μπορώ να σκεφτώ, με ένα μόνο for. Δεν έκανα compile, μπορεί να υπάρχουν λάθη.

 

>
int removeAll(int a[], int &n, int x)
{
 int i, j=0;
 int retval;

 for (i = 0; i < n; i++)
   if (a[i] != x])
     a[j++] = a[i];
 
//Επιστροφή του αριθμού των αντικαταστάσεων.
//Μπορεί να χρησιμοποιηθεί και ως true/false,
//αφού είναι false για 0 αντικαταστάσεις.
 retval = n - j;
 n = j;

 return retval;
}

[m1cRo]

μήπως θέλεις να μικραίνει και ο πινακας τότε ρίξε μια ματια στην memcpy(...).Κανεις ένα temp buffer όταν βρείς έναν αριθμό που θες μεγέθους iso με το προηγούμενο-1 η-1 δηλαδή και κανεις αντιγραφή πρώτα η στοιχεια από πρώτο και μετά στον tmpbuf+η+1 το

υπόloipo.

[dop]

Η ταχύτερη βέβαια λύση για την αντιγραφή θα ήταν η χρήση της memmove() - μια και πρόκειται για επικαλυπτόμενα κομμάτια μνήμης - ή αν παίζεις με STL η std::copy().

[m1cRo]

dld

 

temp=new int[n-1];

memcpy(temp,a,i*sizeof(int));

memcpy(temp+i*sizeof(int),a+(i+1)*sizeof(int),(n-i-1)*sizeof(int));

delete a;

a=temp;

 

 

Kapos etc.

[m1cRo]

Kai pws to kanw delete?

[dop]

@m1cRo: και αν ο αρχικός πίνακας είναι στο stack;

[Directx]

Μια ιδιόρρυθμη σκέψη που μου ήρθε (αν δεν μας ενδιαφέρει η διατήρηση της αρχικής θέσης των στοιχείων) -μπορεί να είναι και ανοησία - όσον αφορά την ομαδική διαγραφή δεδομένων από δυναμικά δεσμευμένους πίνακες είναι να ταξινομήσουμε τα δεδομένα κατά τέτοιο τρόπο ώστε να μεταφέρουμε εκείνα τα οποία θέλουμε να διαγράψουμε στο τέλος του πίνακα και ύστερα να τα αποδεσμεύσουμε με την βοήθεια της realloc όπως παρακάτω:

 

>
#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[10] = 10;
     ptrTable[11] = 10;
     ptrTable[12] = 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;
}
/*---------------------------------------------------------------------------*/

  /* Sort X to the end of Table 
  int nA = *(int*)A, nB = *(int*)B;

  if(nA>nB || nA<nB)
   if(nA==QSRT_X) return(1); else return(-1);

  return 0;
}

int   DeleteAll(int *a,int n,int x)
{
  /* Delete X from A */
  int nData = n;

  if(n>1)
   {
     /* Reverse sort on X */
     QSRT_X = x; qsort(a,n,sizeof(int),QSRT);

     /* Delete X and free memory as you go ... */
     for(;n>0;n--)
      if(a[n-1]==x)
       {
         a = realloc(a,sizeof(int)*n-1);
         nData--;
       }

     return nData;
   }
  else
   if(a[0]==x)
    {
      free(a);
      return 0;
    }
}

 

Όπως πάντα, ο κώδικας έχει αναπτυχθεί σε CodeGear C/C++ Builder 6 (ως ANSI-C compliant -ελπίζω..) και μπορεί να περιέχει bugs ...

 

Υ.Γ.

Εναλλακτικά θα μπορούσαμε να υπολογίσουμε με την βοήθεια πχ. της lfind (non ANSI-C) την έναρξη του μπλοκ των δεδομένων που θέλουμε να σβήσουμε και ύστερα υπολογίζοντας τις διαστάσεις από την αρχή του σειριακά δεσμευμένου πίνακα μας (πχ. &a[0]) να υπολογίσουμε εκ νέου τις διαστάσεις του πίνακα δίχως το προς διαγραφή μπλοκ περνώντας το ξανά στην realloc –αυτή η λύση αφαιρεί εντελώς την ανάγκη για for-loops αφού η διαγραφή γίνεται σε μια φάση..

[Wise_One]

ΟΚ, τώρα είναι σα να μιλάτε για πυρηνική φυσική... Πρώτο εξάμηνο είμαι C++ ρε :ΡΡΡΡ

 

Νομίζω πάντως πως το έλυσα το θέμα. Μένει να το υλοποιήσω τώρα και να δώ αν δουλεύει. Θα ποστάρω τον κώδικα μήπως κι έχετε τίποτα βελτιώσεις να μου προτείνετε... Σας ευχαριστώ όλους...

[m1cRo]

An einai sto stack den prokeite gia diagrafh alla gia mia prosomoiosh isos. To buffer tha yparxei oso yparxei to programma

sthn mnimh kai to size einai stathero.