Ștergere și inserare de caractere la BAC: C++

Ștergerea și inserarea caracterelor într-un șir modifică lungimea textului și poziția terminatorului. La BAC, alegerea sensului de deplasare este esențială: la ștergere aduci caracterele spre stânga, iar la inserare le muți spre dreapta pornind de la final. În caz contrar, poți suprascrie informația înainte să o folosești.

Lecția aparține conținuturilor despre șiruri de caractere de la matematică-informatică. Vom lucra cu texte ASCII scurte, memorate în tablouri de caractere. Schema poate fi folosită în exercițiile de BAC numai după ce adaptezi pozițiile, capacitatea și regula de transformare la enunțul concret.

Ștergerea unui caracter de pe o poziție dată

Pentru a șterge caracterul de la o anumită poziție, copiezi peste el caracterul următor. Continui spre dreapta, aducând fiecare succesor cu o poziție la stânga. Ultima copiere trebuie să aducă și terminatorul la noul sfârșit.

În textul carte, ștergerea caracterului de la indicele doi elimină litera r. Litera t îi ia locul, apoi e se mută pe poziția următoare, iar terminatorul încheie rezultatul cate.

Dacă uiți terminatorul, textul afișat poate conține un caracter suplimentar rămas din vechea organizare. Lungimea logică și marcajul fizic de final trebuie să fie sincronizate. Nu este suficient să scazi o variabilă care păstrează lungimea.

Inserarea fără suprascriere

Pentru inserare, mai întâi faci loc caracterului nou. Muți terminatorul cu o poziție la dreapta, apoi ultimul caracter, penultimul și așa mai departe până la poziția cerută. Abia după aceste deplasări scrii caracterul inserat.

Dacă începi deplasarea din stânga, primul caracter mutat îl poate suprascrie pe următorul înainte ca acesta să fie salvat. Repetarea operației propagă aceeași valoare și distruge secvența inițială.

Operație	Sensul deplasării	Ce se întâmplă cu lungimea
Ștergere	Spre stânga, de la poziție către final	Scade cu unu
Inserare	Spre dreapta, începând cu finalul	Crește cu unu
Înlocuire	Fără deplasare	Rămâne aceeași

Înlocuirea unei litere nu este inserare. Dacă scrii un caracter nou peste unul existent, nu ai creat o poziție suplimentară și ai pierdut caracterul anterior.

Mai multe ștergeri: metoda compactării

Când elimini toate caracterele care respectă o proprietate, deplasarea întregului sufix după fiecare ștergere poate repeta multă muncă. O metodă mai clară folosește un indice de citire și unul de scriere.

Indicele de citire vizitează fiecare caracter inițial. Dacă păstrezi caracterul, îl copiezi la poziția de scriere și avansezi acea poziție. Dacă îl elimini, avansezi doar citirea. La final, scrii terminatorul după ultimul caracter păstrat.

Poziția de scriere nu depășește poziția de citire, deoarece în această etapă doar eliminăm caractere. Prin urmare, nu suprascriem un caracter viitor înainte să îl analizăm. Ordinea caracterelor păstrate rămâne neschimbată.

Program C++ cu ștergere și inserare

Programul citește o linie de cel mult o sută de caractere ASCII. Elimină toate cifrele, apoi inserează caracterul diez la începutul textului rezultat. Tabloul are loc pentru lungimea inițială maximă, caracterul nou și terminator.

#include <iostream>
using namespace std;

int main() {
    char s[102];
    cin.getline(s, 101);
    int k = 0;
    for (int i = 0; s[i] != '\0'; ++i) {
        bool cifra = s[i] >= '0' && s[i] <= '9';
        if (!cifra) {
            s[k] = s[i];
            ++k;
        }
    }
    s[k] = '\0';
    for (int j = k; j >= 0; --j)
        s[j + 1] = s[j];
    s[0] = '#';
    cout << s;
    return 0;
}

La inserare, bucla pornește chiar de la terminator. Dacă textul rămas este vid, terminatorul este mutat de pe poziția zero pe poziția unu, iar caracterul nou ocupă poziția zero. Același algoritm tratează cazul fără o ramură specială.

Urmărirea textului cu cifre consecutive

Pentru textul a12b3, citirea păstrează litera a și avansează scrierea la poziția unu. Cifrele unu și doi sunt ignorate, astfel încât poziția de scriere nu se schimbă. Litera b este apoi copiată pe poziția unu.

Cifra trei este eliminată, iar terminatorul este scris la poziția doi. Rezultatul intermediar este ab. După inserarea marcajului la început, rezultatul final este #ab.

Acest exemplu verifică tocmai situația care pune probleme ștergerii repetate: două caractere eliminabile consecutive. Dacă deplasezi textul și apoi incrementezi automat indicele, poți sări peste al doilea caracter, ajuns între timp pe aceeași poziție.

Limitele poziției și capacității

Într-un text de lungime n, o poziție de ștergere validă este între zero și n minus unu. Nu poți șterge un caracter vizibil de la poziția n, deoarece acolo se află terminatorul.

Pentru inserare, poziția poate fi și n, ceea ce înseamnă adăugare la final. Poziția zero înseamnă adăugare la început. Numărul locurilor posibile de inserare este astfel cu unu mai mare decât numărul caracterelor existente.

Capacitatea trebuie să permită noul text și terminatorul său. Dacă un tablou are capacitatea o sută unu și textul are deja o sută de caractere, nu mai există loc pentru o inserare. Faptul că ultimul caracter vizibil se află înaintea ultimului element al tabloului nu înseamnă că acel element este liber: el păstrează terminatorul.

Ordinea operațiilor schimbă rezultatul

Eliminarea cifrelor urmată de inserarea unui marcaj nu este întotdeauna echivalentă cu ordinea inversă. Dacă marcajul ar fi el însuși o cifră, inserarea înaintea eliminării l-ar șterge. Inserarea după eliminare l-ar păstra.

Și pozițiile se schimbă după ștergeri. O cerință de inserare la o poziție din textul inițial diferă de una referitoare la textul deja compactat. Enunțul trebuie citit ca o succesiune de transformări cu stări intermediare clare.

Scrie rezultatul intermediar pe hârtie înainte să aplici a doua operație. Această practică sprijină înțelegerea pașilor algoritmului și face mai ușoară localizarea unei erori.

Timpul de execuție

Compactarea parcurge textul o singură dată. Inserarea de la început deplasează fiecare caracter rămas și terminatorul o singură dată. Împreună, cele două etape au timp proporțional cu lungimea inițială.

Ștergerea individuală repetată poate avea timp pătratic atunci când fiecare eliminare mută o mare parte din text. Diferența nu se vede neapărat într-un exemplu cu cinci caractere, dar devine evidentă când numeri totalul copierilor.

Memoria auxiliară a programului este constantă în afara tabloului textului. Nu construim un al doilea șir. Pentru o transformare care mărește textul la fiecare caracter, cum ar fi dublarea vocalelor, trebuie analizată separat capacitatea și ordinea de scriere.

Exerciții cu răspunsuri

Textul este 123. După eliminare rămâne șirul vid, iar rezultatul final este #.

Textul este bac. Nu se elimină nimic. Rezultatul este #bac, cu o lungime mai mare cu unu.

Textul este 1 a2 b3. Spațiile se păstrează. Rezultatul este # a b, deoarece cerința elimină doar cifrele.

Întrebări frecvente

Pot muta caracterele spre dreapta de la început?

Nu prin copiere directă în același tablou fără protejarea datelor. Copierea de la final păstrează fiecare caracter până în momentul în care este mutat.

De ce copiez terminatorul la inserare?

El trebuie să ajungă după noul ultim caracter. Altfel, afișarea se poate opri prea devreme sau poate continua dincolo de textul dorit, în funcție de modificările făcute.

Cum aleg între ștergeri repetate și compactare?

Pentru eliminarea tuturor caracterelor cu o proprietate, compactarea este de obicei mai simplu de justificat și verificat. Poți compara cele două variante pe același exemplu cu un profesor de informatică.