Ștergerea elementelor

  Ștergerea unui element dintr-un tablou unidimensional este un procedeu ușor de înțeles și este descris în figura următoare:

Stergerea unui element
  1. Dorim să eliminăm elementul din poziția 3;
  2. Vom muta toate elementele următoare cu o poziție inferioară (memorăm peste elementul ce trebuie șters);
  3. Scădem din numărul total de elemente secvența ștearsă.

Ștergerea elementului din poziția k

  • v este tabloul în care efectuăm ștergerea;
  • n este numărul de elemente al tabloului;
  • k este poziția elementului pe care îl eliminăm;
int n, v[1001], k;
...
for(int i=k+1; i<n; i++) v[i-1]=v[i]; /* mutăm elementele de după k cu o poziție la stânga */
n--; // scădem numărul de elemente
 

  Vom muta toate elementele cu o poziție mai la stânga, astfel suprapunând secvența de după k peste acesta.


Exemplu - problemă rezolvată

Enunț: Se citește un număr n, n∈(0,103], urmat de n numere întregi nenule elemente ale unui vector. Să se elimine din șir toate elementele divizibile cu 12 și să se afișeze tabloul prelucrat.

  Putem aborda două metode de rezolvare:
1. Varianta clasică

#include <iostream>
using namespace std;
int n, v[1000];
int main(){
  int i,j;
  cin>>n;
  for(i=0; i<n; i++) cin>>v[i];
  for(i=0; i<n; i++)
    if(v[i]%3==0 && v[i]%4==0){
      for(j=i+1; j<n; j++) v[j-1]=v[j];
      n--;
    }
  for(i=0; i<n; i++) cout<<v[i]<<' ';
  return 0;
}
10
23 3 24 16 12 30 144 74 541 43
23 3 16 30 74 541 43
5
12 24 36 72 60
 

  Parcurgem tabloul și de fiecare dată când vom găsi un număr divizibil cu 12 (atât divizibil cu 4, cât și cu 3) îl vom elimina.

2. Varianta optimizată (mai eficientă)

#include <iostream>
using namespace std;
int n, v[1000];
int main(){
  int k=0,i;
  cin>>n;
  for(i=0; i<n; i++) cin>>v[i];
  for(i=0; i<n; i++)
    if(v[i]%3==0 && v[i]%4==0) k++;
    else v[i-k]=v[i];
  n-=k;
  for(i=0; i<n; i++) cout<<v[i]<<' ';
  return 0;
}
7
25 7 30 156 32 24 120
25 7 30 32 120
3
12 24 33
33

  De această dată, când găsim un număr divizibil cu 12 vom crește un contor k care va conține la un moment dat peste câte numere divizibile cu 12 am trecut. Când găsim un număr nedivizibil, îl vom copia în poziția i-k (poziția curentă minus numărul de elemente care trebuie eliminate până atunci).
  După finalizarea ștergerii, vom actualiza și numărul de elemente n.
  Această variantă de rezolvare ne ferește de executarea ineficientă a multor structuri for și poate fi mult mai eficientă d.p.d.v. al timpului de executare.