Ș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:

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

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: