Ștergeri și inserări de elemente

Operațiile de ștergere a unui element dintr-un vector, sau de inserare a unui element nou într-un vector sunt frecvente în practică: avem o listă cu elevii dintr-o clasă și un elev pleacă, sau un alt elev vine. Cum actualizăm lista?

Ștergerea

Să considerăm următoarea problemă:

Se dă un șir X cu n elemente întregi și un număr p. Să se șteargă din șirul X elementul aflat pe poziția p.

Să considerăm următorul vector cu n=10 elemente și p=4.

Dorim să eliminăm din vector elementul de indice 4, cel cu valoarea X[4] = 34. În urma eliminării vectorul trebuie să arate astfel:

Cum procedăm?

• elementele cu indici p+1, p+2, …, n-1 se mută spre stânga cu o poziție
• dimensiunea n a tabloului se micșorează cu 1

Ștergerea se face astfel (elemntele tabloului sunt indexate de la 0):

for(int i = p ; i < n - 1; i ++)
    X[i] = X[i+1];
n --;

Ștergerea mai multor valori din șir

Considerăm următoarea problemă:

Considerăm un șir X cu n elemente întregi. Să se elimine din șir toate elementele pare.

Rezolvare:

• parcurgem șirul și analizăm elementul curent X[p];
• dacă elementul X[p] este par, aplicăm algoritmul de mai sus pentru ștergerea elementului cu indicele p.

Este necesar să realizăm cu atenție parcurgerea. Următoarea secvență:

for (int p = 0 ; p < n ; p ++)
    if(X[p] % 2 == 0) {
        for(int i = p ; i < n - 1; i ++)
            X[i] = X[i+1];
        n --;
    }

nu funcționează corect dacă în șir sunt elemente consecutive cu proprietatea dorită (de a fi pare), deoarece al doilea element par nu va fi analizat, deci nu va fi eliminat din șir. O soluție bună este să parcurgem elementele în ordine inversă:

for (int p = n - 1 ; p >= 0 ; p --)
    if(X[p] % 2 == 0) {
        for(int i = p ; i < n - 1; i ++)
            X[i] = X[i+1];
        n --;
    }

Adăugarea unui element într-un vector

Adăugarea unui element într-un vector înseamnă mărirea dimensiunii logice n a vectorului și memorarea în ultimul element a noii valori. Următoarele secvențe adaugă o valoare într-un vector indexat de la 0.

X[n] = val;
n ++;

sau, mai condensat:

X[n++] = val;

Următoarele secvențe adaugă o valoare într-un vector indexat de la 1.

n ++;
X[n] = val;

sau, mai condensat:

X[++n] = val;

Inserarea unui element într-un vector

Considerăm următoarea problemă:

Se dă un șir X cu n elemente întregi, o valoare întreagă val și un număr p. Să se insereze pe poziția p în șir valoarea val.

Similar cu algoritmul de ștergere a unui element dintr-un vector, și cel de inserare presupune modificarea elementelor din dreapta lui X[p]. De data aceasta elementele vor fi mutate spre dreapta, începând cu ultimul. Elementul X[p] se înlocuiește cu noua valoare, iar dimensiunea logică a vectorului crește, fără a depăși însă dimensiunea fizică.

for(int i = n - 1 ; i >= p ; i --)
    X[i+1] = X[i];
X[p] = val;
n ++;

Inserarea mai multor valori în șir

Considerăm următoarea problemă:

Se dă un vector cu n elemente naturale. Să se insereze după fiecare element par, jumătatea sa.

Principial, procedăm astfel:

• parcurgem șirul
• dacă elementul curent X[p] este par
  • inserăm pe poziția p+1 valoarea X[p]/2

Dacă parcurgerea se face de la stânga spre dreapta, există riscul unor inserări suplimentare, ca în acest exemplu:

După 12 se inserează 6. Se trece mai departe, ajungând la elementul inserat, care este par, iar după el se inserează 3, ceea ce este greșit. Următoarea secvență, greșită, are acest comportament:

for(int p = 1 ; p <= n ; p ++)
	if(a[p] % 2 == 0){
        for(int i = n ; i >= p ; i --)
            a[i+1] = a[i];
        n ++;
        a[p+1] = 2*a[p];
	}

La fel ca în cazul ștergerii, rezultatul este corect dacă facem parcurgerea tabloului în ordine inversă. Următoarea secvență este corectă:

for(int p = n ; p >= 1 ; p --)
	if(a[p] % 2 == 0){
        for(int i = n ; i >= p ; -- i)
            a[i+1] = a[i];
        n ++;
        a[p+1] = 2*a[p];
	}