Inserarea și ștergerea unui element dintr-un vector

Un vector în C++ nu are „găuri” și nici spațiu liber între elemente. Ca să inserezi o valoare la mijloc, trebuie să muți elementele de după ea cu o poziție la dreapta; ca să ștergi una, le muți cu o poziție la stânga. La BAC informatică, aceste operații apar la problemele cu tablouri de la Subiectul III, de exemplu: „inserați după fiecare element par dublul lui” sau „eliminați toate elementele egale cu x”. Ordinea în care faci deplasările decide dacă programul e corect sau îți suprascrie datele.

În toate exemplele, elementele sunt v[1], …, v[n], iar vectorul e declarat suficient de mare ca să încapă și elementele inserate.

Inserarea unei valori pe poziția k

Vrem ca x să ajungă pe poziția k, iar elementele de la k la n să se mute cu un pas la dreapta. Deplasarea se face de la coadă spre poziția k:

for (int i = n; i >= k; i--)
    v[i + 1] = v[i];
v[k] = x;
n++;

De ce de la coadă? Dacă ai porni de la k, ai scrie v[k + 1] = v[k] și ai pierde valoarea veche din v[k + 1] înainte s-o muți mai departe. Rezultatul ar fi un vector în care v[k] e copiat peste tot până la final.

Exemplu: v = 4 7 1 9 (n = 4), inserăm x = 5 pe poziția k = 2.

Cazuri particulare: pentru k = n + 1 bucla nu se execută și x se adaugă la final; pentru k = 1 se mută tot vectorul. Nu uita n++ — fără el, ultimul element „dispare” la afișare.

Ștergerea elementului de pe poziția k

Aici direcția e inversă: elementele de după k vin cu un pas la stânga, de la k spre coadă:

for (int i = k; i < n; i++)
    v[i] = v[i + 1];
n--;

Pentru v = 4 5 7 1 9 și k = 3: v[3] ← 1, v[4] ← 9, n devine 4, deci vectorul e 4 5 1 9. Ultima valoare rămâne fizic în v[5], dar nu mai contează, pentru că n spune că vectorul are 4 elemente.

Ștergerea tuturor aparițiilor unei valori: capcana

Prima idee e să parcurgi vectorul și să ștergi fiecare element egal cu x. Scrisă naiv, are o eroare:

for (int i = 1; i <= n; i++)        // GREȘIT pentru apariții consecutive
    if (v[i] == x)
    {
        for (int j = i; j < n; j++) v[j] = v[j + 1];
        n--;
    }

Ia v = 5 2 7 2 2 9 și x = 2. La i = 2 se șterge primul 2 și vectorul devine 5 7 2 2 9. La i = 3 se șterge 2-ul de pe poziția 3: 5 7 2 9. Dar acum un alt 2 a venit pe poziția 3, iar i trece la 4 și nu-l mai verifică. Rezultat: 5 7 2 9, greșit. După o ștergere, pe poziția i a sosit un element nou, care trebuie verificat. Corecția minimă e să avansezi doar când nu ștergi:

int i = 1;
while (i <= n)
    if (v[i] == x)
    {
        for (int j = i; j < n; j++) v[j] = v[j + 1];
        n--;                         // nu creștem i
    }
    else
        i++;

Varianta e corectă, dar face o deplasare pentru fiecare apariție, deci în cel mai rău caz aproximativ n² operații.

Ștergerea eficientă, într-o singură parcurgere

Metoda mai bună folosește doi indici: i citește fiecare element, iar k arată unde scriem următorul element păstrat. Elementele diferite de x se „strâng” la începutul vectorului:

#include <iostream>
using namespace std;

int v[101], n, x;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i];
    cin >> x;

    int k = 0;
    for (int i = 1; i <= n; i++)
        if (v[i] != x)
        {
            k++;
            v[k] = v[i];
        }
    n = k;

    for (int i = 1; i <= n; i++) cout << v[i] << " ";
    return 0;
}

Pentru 5 2 7 2 2 9 și x = 2 se obține 5 7 9. Fiecare element e citit și eventual mutat o singură dată, deci complexitatea e O(n). Funcționează pentru că k ≤ i tot timpul: nu scriem niciodată peste un element pe care nu l-am citit încă.

Inserări multiple: după fiecare element par, dublul lui

Exemplu: din 1 4 3 6 trebuie să obții 1 4 8 3 6 12. Dacă parcurgi de la stânga la dreapta pe același vector, după ce inserezi 8 vei da peste el și vei insera 16, și tot așa. Soluția e să parcurgi de la dreapta la stânga: elementele inserate ajung mereu în partea deja prelucrată.

for (int i = n; i >= 1; i--)
    if (v[i] % 2 == 0)
    {
        for (int j = n; j > i; j--)     // mutăm v[i+1..n] cu un pas la dreapta
            v[j + 1] = v[j];
        v[i + 1] = 2 * v[i];
        n++;
    }

Urmărire pe 1 4 3 6: la i = 4 (6, par) se adaugă 12 la final: 1 4 3 6 12. La i = 3 (3) nimic. La i = 2 (4, par) se mută 3, 6, 12 la dreapta și se pune 8 pe poziția 3: 1 4 8 3 6 12. La i = 1 (1) nimic. Atenție la dimensiunea vectorului: în cel mai rău caz (toate pare) se dublează numărul de elemente, deci pentru n ≤ 100 declari cel puțin 201 de elemente.

Varianta eficientă, dacă enunțul nu cere modificarea pe loc, e un vector nou w, în care copiezi fiecare element și, după cele pare, adaugi dublul lor — tot O(n).