Inserarea în vector la BAC: indici și program C++

Inserarea unui element într-un vector cere eliberarea unei poziții prin deplasarea elementelor din dreapta cu un loc spre dreapta. Deplasarea începe de la final, pentru a nu suprascrie valori care încă trebuie mutate. După copierea elementului nou, lungimea logică crește cu unu.

La BAC, trebuie să clarifici dacă poziția este numerotată de la zero sau de la unu și dacă inserarea se face înaintea sau după un anumit element. Vom folosi un indice de inserare de la zero, care arată poziția ocupată de noua valoare în rezultatul final. Această convenție se poate adapta cerințelor din subiectele de BAC.

Ce poziții de inserare sunt posibile

Un vector cu trei elemente are patru locuri posibile pentru inserare: înaintea primului, între primul și al doilea, între al doilea și al treilea, după ultimul. În convenția indicilor de la zero, poziția nouă poate fi între zero și lungimea veche inclusiv.

Această limită diferă de limita unui indice de element existent. Înainte de inserare, indicele egal cu lungimea nu desemnează un element valid. El desemnează însă locul în care poate fi adăugat un element la sfârșit, dacă există capacitate disponibilă.

Pentru vectorul patru, nouă, doi, inserarea lui șapte la indicele unu produce patru, șapte, nouă, doi. Inserarea la indicele zero pune șapte la început. Inserarea la indicele trei îl adaugă după doi.

Capacitatea trebuie să permită încă un element

Dacă tabloul poate memora cel mult o mie de valori și deja folosești toate cele o mie de poziții, nu poți insera încă un element în același tablou. Lungimea logică și capacitatea trebuie verificate separat.

În programul acestei lecții, citim cel mult o mie de elemente, dar rezervăm 1001 de celule. Astfel, există întotdeauna spațiu pentru inserarea unică cerută. Pentru mai multe inserări, capacitatea trebuie aleasă după lungimea maximă posibilă a rezultatului.

Nu te baza pe faptul că programul pare să ruleze când scrii după capătul tabloului. Un acces în afara capacității nu este o metodă de extindere a vectorului. Rezolvarea trebuie să respecte explicit limitele memoriei rezervate.

Deplasarea se face de la dreapta spre stânga

Luăm vectorul patru, nouă, doi și inserăm șapte la indicele unu. Mai întâi mutăm doi în celula liberă de la final. Apoi mutăm nouă în locul vechi al lui doi. Abia după aceea putem scrie șapte la indicele unu.

Etapă	Primele patru celule relevante
Înaintea deplasării	4, 9, 2, liber
Mutăm ultimul element	4, 9, 2, 2
Mutăm elementul de la inserare	4, 9, 9, 2
Scriem valoarea nouă	4, 7, 9, 2

Dacă ai începe mutarea de la stânga, ai copia nouă peste doi înainte să salvezi valoarea doi. Următoarea copiere ar putea propaga nouă mai departe. Direcția descrescătoare protejează fiecare sursă până când este folosită.

Program C++ complet

Programul citește lungimea, elementele, apoi indicele de inserare și valoarea nouă. Lungimea inițială este între zero și o mie, iar indicele este între zero și lungimea inițială inclusiv. Afișează vectorul obținut.

#include <iostream>
using namespace std;

int main() {
    int n, v[1001];
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> v[i];
    int p, x;
    cin >> p >> x;

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

    for (int i = 0; i < n; ++i) {
        if (i > 0) cout << ' ';
        cout << v[i];
    }
    return 0;
}

Prima destinație a deplasării este celula de indice egal cu lungimea veche. Aceasta este liberă logic, dar există în tabloul rezervat. Ultima destinație este cu o poziție la dreapta locului de inserare. Celula de inserare rămâne apoi disponibilă pentru valoarea nouă.

Pentru inserarea la final, condiția buclei este falsă de la început. Nu se mută nimic: scrii valoarea nouă în prima celulă liberă și mărești lungimea. Pentru un vector inițial vid, singura poziție permisă este zero, iar aceeași schemă funcționează.

Cum traduci cerința „înainte” sau „după”

Dacă un element existent are indicele curent și trebuie să inserezi înaintea lui, folosești acel indice ca poziție de inserare. Dacă trebuie să inserezi după el, folosești indicele mărit cu unu.

În numerotarea pozițiilor de la unu, traducerea cere un pas suplimentar. Pentru inserare înaintea poziției a treia, indicele de inserare este doi. Pentru inserare după poziția a treia, indicele de inserare este trei.

Scrie un exemplu cu litere sau valori distincte înainte să formulezi limitele buclei. Valorile egale pot ascunde o inserare făcută cu o poziție prea devreme sau prea târziu. Un exemplu vizual clar este mai util decât memorarea unei expresii fără convenție.

Inserarea într-un vector deja ordonat

Dacă vectorul este crescător și vrei să păstrezi ordinea, trebuie mai întâi să găsești poziția potrivită. Poți alege primul element strict mai mare decât valoarea nouă și să inserezi înaintea lui. Dacă nu există, inserezi la final.

Această alegere plasează valoarea nouă după aparițiile egale existente. Dacă alegi primul element mai mare sau egal, o vei plasa înaintea lor. Ambele rezultate sunt ordonate, dar pot avea semnificații diferite dacă elementele au și alte informații asociate.

Căutarea poziției și deplasarea sunt două etape diferite. Chiar dacă poziția ar fi găsită mai repede printr-o metodă potrivită, deplasarea elementelor într-un tablou obișnuit poate necesita în continuare un număr liniar de copieri.

Inserări repetate fără a prelucra din nou elementele adăugate

O cerință precum „inserează zero după fiecare element negativ inițial” cere atenție la cuvântul „inițial”. Dacă mărești lungimea în timpul parcurgerii, elementele adăugate intră și ele în porțiunea validă. Trebuie să decizi explicit ce element urmează să verifici.

O metodă clară este să construiești un vector rezultat: copiezi fiecare element inițial și, dacă îndeplinește condiția, adaugi imediat și noua valoare. Rezervi capacitate pentru cazul în care fiecare element inițial produce o inserare.

Se poate lucra și în același tablou cu o strategie atentă de la dreapta spre stânga, după calcularea lungimii finale. Nu folosi însă automat bucla pentru o singură inserare fără să analizezi cum se schimbă indicii. Explicația pas cu pas este un exemplu de învățare prin înțelegere.

Timpul de execuție și numărul copierilor

Pentru o inserare la indicele ales, se mută toate elementele aflate de la acel indice până la finalul vechi. Numărul copierilor este lungimea veche minus indicele de inserare. Inserarea la început este cea mai costisitoare, iar inserarea la final nu cere deplasări.

În cel mai nefavorabil caz, timpul este liniar în lungimea vectorului. Memoria suplimentară a deplasării este constantă, dacă spațiul necesar exista deja în tablou. Această afirmație nu înseamnă că întregul tablou ocupă memorie constantă față de dimensiunea problemei.

Exerciții cu răspunsuri

Inserează cinci la începutul vectorului opt, doi. Rezultatul este cinci, opt, doi. Ambele valori vechi se deplasează cu o poziție, începând cu ultima.

Inserează șapte după poziția a doua din unu, patru, nouă. Pozițiile sunt numerotate de la unu, deci indicele de inserare este doi. Rezultatul este unu, patru, șapte, nouă.

Inserează trei în vectorul ordonat unu, trei, trei, opt. Dacă alegi primul element strict mai mare, noul trei este plasat înaintea lui opt, după cele două apariții egale. Lista valorilor rămâne unu, trei, trei, trei, opt.

Inserează nouă într-un vector vid. Poziția este zero, nu există deplasări, iar lungimea finală este unu. Rezultatul conține doar nouă.

Întrebări frecvente

De ce măresc lungimea după deplasare?

În schema prezentată, limitele folosesc lungimea veche. După ce ai mutat elementele și ai scris valoarea nouă, mărești lungimea. Alte variante pot fi corecte, dar trebuie să adapteze consecvent limitele.

Inserarea și înlocuirea sunt același lucru?

Nu. Înlocuirea schimbă valoarea unui element existent și păstrează lungimea. Inserarea adaugă un element și mărește lungimea, deplasând valorile necesare.

Ce teste verifică cel mai bine programul?

Folosește inserarea la început, la mijloc, la final și într-un vector vid, cu valori distincte. Dacă ai erori de indici, poți urmări fiecare copiere împreună cu un profesor de informatică.