Inserarea elementelor

A insera un element într-un vector înseamnă a adăuga o valoare nouă pe o poziție din interiorul lui, fără a pierde valorile existente. Spre deosebire de adăugarea la sfârșit, inserarea în interior cere puțină atenție: trebuie mai întâi să facem loc pentru noua valoare.

Să presupunem că vrem să introducem o valoare între elementele de pe pozițiile 3 și 4:

Pașii sunt următorii:

1. alegem poziția pe care va sta noua valoare;
2. deplasăm cu o poziție „la dreapta” toate elementele de la acea poziție până la sfârșit, eliberând astfel un loc gol (vectorul trebuie declarat suficient de mare ca să încapă elementul în plus, altfel am pierde ultima valoare);
3. punem valoarea în locul eliberat și creștem cu 1 numărul total de elemente.

Deplasarea elementelor se face de la coadă spre cap (de la ultimul element spre poziția de inserare). Dacă le-am muta în ordine inversă, am suprascrie valorile înainte să apucăm să le copiem și am umple vectorul cu o singură valoare.

Notăm cu v vectorul, cu n numărul de elemente, cu k poziția pe care inserăm și cu x valoarea de inserat:

int v[1001], n, k, x;
// ...
for (int i = n - 1; i >= k; --i)
    v[i + 1] = v[i];   // eliberam pozitia k
v[k] = x;              // punem valoarea noua
n++;                   // avem un element in plus

Bucla for parcurge vectorul de la ultimul element spre poziția k și copiază fiecare element pe poziția imediat următoare. După ce poziția k a rămas liberă, scriem acolo valoarea x și actualizăm numărul de elemente.

Enunț. Se citește un număr n, $n \in (0, 10^3]$, urmat de n numere întregi, elementele unui vector. Să se insereze între oricare două elemente alăturate media lor aritmetică și să se afișeze vectorul obținut, cu elementele separate printr-un spațiu.

#include <iostream>
using namespace std;
int n;
float v[2001];
int main() {
    int i, j;
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (i = 1; i < n; i += 2) {
        for (j = n - 1; j >= i; j--) {
            v[j + 1] = v[j];
        }
        v[i] = (v[i - 1] + v[i + 1]) / 2;
        n++;
    }
    for (i = 0; i < n; i++) {
        cout << v[i] << ' ';
    }
    return 0;
}

> 4
> 2 5 7 9
2 3.5 5 6 7 8 9

> 5
> 0 5 1 33 10
0 2.5 5 3 1 17 33 21.5 10

Pentru intrarea 4 și vectorul 2 5 7 9 se obține 2 3.5 5 6 7 8 9, iar pentru 5 și 0 5 1 33 10 se obține 0 2.5 5 3 1 17 33 21.5 10.

Parcurgem vectorul oprindu-ne pe pozițiile impare, acolo unde vrem să apară mediile. Pe fiecare astfel de poziție i aplicăm exact schema de inserare: bucla interioară cu indicele j deplasează elementele la dreapta, după care scriem media aritmetică a vecinilor, (v[i-1] + v[i+1]) / 2, și creștem numărul de elemente. Pentru că între fiecare două valori inițiale apare una nouă, pasul de parcurgere este 2 (i += 2).

Vectorul a fost declarat de tip float pentru că media aritmetică poate fi un număr zecimal. Dimensiunea 2001 acoperă cazul în care, după toate inserările, vectorul ajunge la aproape dublul lungimii inițiale.

Inserarea pe o poziție interioară se bazează pe o singură idee: eliberăm locul deplasând la dreapta, de la coadă spre cap, elementele de după poziția aleasă, apoi punem valoarea nouă și creștem numărul de elemente. Operația complementară, prin care eliminăm o valoare și „strângem” golul rămas, este ștergerea elementelor.