Școala Româno-Britanică
Modulul 2 Clasa a X-a | C++

Ora 6: Compararea șirurilor - ordinea lexicografică

Ce vei învăța astăzi: Ce este ordinea lexicografică (ordinea din dicționar, în care cuvintele se compară literă cu literă, de la stânga la dreapta), cum comparăm șiruri cu strcmp (funcție care compară două șiruri și întoarce 0 dacă sunt identice) și cum ordonăm cuvinte alfabetic

Rezultat practic: Scrii programe C++ care compară cuvinte după ordinea lexicografică, cu strcmp sau manual, și le afișează în ordine alfabetică (Competența 4.2).

Competența 4.2 Săptămâna 7

Înainte de a începe

De ce contează? Sortarea alfabetică, dicționarele de cuvinte și listele ordonate se bazează toate pe comparație: fără un răspuns corect la întrebarea „care vine primul?" nu poți ordona nimic, iar strcmp este piesa din mijloc a oricărei sortări.

Ce știi deja?

La ora 5 ai căutat caractere într-un șir. Decide fără calculator: care cuvânt vine primul în dicționar, „carte" sau „casa"? Pe ce literă se face diferența și cum ai formula regula generală?

Ideea-cheie: strcmp(a, b) întoarce un număr negativ dacă a este alfabetic înaintea lui b, 0 dacă șirurile sunt identice și pozitiv în caz contrar; egalitatea se testează cu strcmp(a, b) == 0, niciodată cu a == b.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei înțelege ordinea lexicografică (ordinea din dicționar), vei ști să compari două șiruri cu strcmp și să ordonzi cuvinte în ordine alfabetică.

Ordinea lexicografică
Compararea cu strcmp
Compararea manuală
Cuvinte în ordine alfabetică

Ordinea lexicografică

Definiție: Ordinea lexicografică este ordinea din dicționar: comparăm cuvintele caracter cu caracter; la prima diferență, cuvântul al cărui caracter este „mai mic" (are cod ASCII mai mic) vine înainte. Dacă un cuvânt este prefix al celuilalt (adică este chiar începutul lui, de exemplu bac este prefix al lui bacalaureat), cel mai scurt vine înainte.

Analogia: dicționarul

Când cauți „mar" în dicționar, treci prin paginile cu „ma": mai întâi găsești „mac", apoi „mal", apoi „mar". Comparațiile se fac pe litere, de la prima la ultima, exact ca la dicționar.

Cuvântul A Cuvântul B Cine vine primul?
ana are ana (a = a, n < r)
bac baschet bac (bac este prefix)
mar mal mal (m = m, a = a, l < r)

Compararea cu strcmp

Definiție: strcmp(a, b) returnează: o valoare negativă dacă a vine înaintea lui b, 0 dacă sunt identice și o valoare pozitivă dacă a vine după b.

C++ - care cuvânt vine primul alfabetic?
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char a[101], b[101];

    cin >> a >> b;

    int rez = strcmp(a, b);

    if (rez < 0)
    {
        cout << a << " este primul in ordine alfabetica";
    }
    else if (rez > 0)
    {
        cout << b << " este primul in ordine alfabetica";
    }
    else
    {
        cout << "Cuvintele sunt identice";
    }

    return 0;
}

Ce învățăm: semnul valorii returnate de strcmp ne spune ordinea; valoarea exactă nu contează, contează semnul.

Compararea manuală, caracter cu caracter

Compararea manuală reproduce regula dicționarului: parcurgem simultan cele două șiruri, cât timp caracterele sunt egale. Ne oprim la prima pereche diferită și o comparăm.

Algoritm comparareManuală citește a, b i = 0 cât timp a[i] != '\0' și b[i] != '\0' și a[i] = b[i] execută i = i + 1 sfârșit cât timp dacă a[i] = b[i] atunci scrie "Cuvintele sunt egale" altfel dacă a[i] < b[i] atunci scrie "a vine înaintea lui b" altfel scrie "b vine înaintea lui a" sfârșit dacă Sfârșit algoritm
C++ - compararea manuală a două cuvinte
#include <iostream>
using namespace std;

int main()
{
    char a[101], b[101];

    cin >> a >> b;

    int i = 0;
    while (a[i] != '\0' && b[i] != '\0' && a[i] == b[i])
    {
        i++;
    }

    if (a[i] < b[i])
    {
        cout << a << " este primul";
    }
    else if (a[i] > b[i])
    {
        cout << b << " este primul";
    }
    else
    {
        cout << "Cuvintele sunt identice";
    }

    return 0;
}

Ce învățăm: terminatorul '\0' are codul 0, mai mic decât orice literă; de aceea, un prefix (de exemplu bac) este automat „mai mic" decât un cuvânt care începe cu el (bacalaureat).

Cuvintele în ordine alfabetică

Exemplu ghidat: trei cuvinte în ordine alfabetică

C++ - ordonarea a trei cuvinte
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char a[101], b[101], c[101];
    char aux[101];

    cin >> a >> b >> c;

    if (strcmp(a, b) > 0)
    {
        strcpy(aux, a);
        strcpy(a, b);
        strcpy(b, aux);
    }
    if (strcmp(b, c) > 0)
    {
        strcpy(aux, b);
        strcpy(b, c);
        strcpy(c, aux);
    }
    if (strcmp(a, b) > 0)
    {
        strcpy(aux, a);
        strcpy(a, b);
        strcpy(b, aux);
    }

    cout << a << " " << b << " " << c;

    return 0;
}

Observă: interschimbăm șiruri cu strcpy printr-un șir auxiliar aux, exact ca la numere. Pentru intrarea bac mar ana se afișează ana bac mar.

Exercițiu de completare

Completează enunțul despre compararea șirurilor:

Compararea a două șiruri se face cu funcția ______. Ea returnează o valoare negativă dacă primul șir este ______ în ordinea lexicografică, 0 dacă șirurile sunt ______ și o valoare pozitivă în caz contrar.

Bancă de cuvinte:
strcmp înainte identice

Exercițiu de completare a codului

Completează programul care afișează primul cuvânt alfabetic:
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    char a[101], b[101];
    cin >> a >> b;
    int rez = ______(a, b);
    if (rez < 0)
    {
        cout << ______;
    }
    else
    {
        cout << ______;
    }
    return 0;
}
Bancă de cuvinte:
strcmp a b

Test de înțelegere

Test rapid - compararea șirurilor:

1. Dacă strcmp(a, b) < 0, atunci:

2. Ordinea lexicografică este asemănătoare cu:

3. Ce returnează strcmp("abc", "abd")?

Ai grijă la: semnul rezultatului lui strcmp contează — strcmp(a, b) < 0 înseamnă că a vine înaintea lui b, nu „egalitate". Iar a == b compară adresele șirurilor, nu conținutul lor, deci nu sesizează niciodată două cuvinte identice.

Aprofundare

Cazuri particulare și detalii avansate:

  • Contează semnul, nu valoarea. strcmp(a, b) returnează un număr negativ dacă a e înaintea lui b, 0 dacă sunt egale, pozitiv dacă a e după b. Valoarea exactă depinde de implementare și nu contează.
  • Cazul unui șir prefix al celuilalt: la comparare, dacă toate caracterele coincid dar un șir se termină mai devreme, cel mai scurt vine primul. De exemplu ana < ananas, pentru că '\0' are codul 0, mai mic decât orice literă.
  • Compararea se face după codurile ASCII. Literele mari (65–90) vin înaintea celor mici (97–122), deci "BAC" < "bac". La BAC se lucrează de regulă cu litere mici.
  • Compararea manuală reproduce exact regula dicționarului: parcurgem simultan până la prima diferență sau până la sfârșitul unuia dintre șiruri.
  • Sortarea cuvintelor folosește strcmp în interiorul unei bucle de sortare (interclasare, selecție): comparăm două cuvinte pentru a decide ordinea lor.

Compararea lexicografică este exact regula din dicționar sau din lista de contacte a telefonului: cuvintele se ordonează după prima literă diferită, iar un prefix vine întotdeauna înaintea șirului complet.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Cel mai mic cuvânt

Enunț:

Cerință: Se citesc două cuvinte a și b, formate din litere mici. Să se afișeze cuvântul care este primul în ordine alfabetică.

Date de intrare:

Programul citește de la tastatură cele două cuvinte, separate printr-un spațiu.

Date de ieșire:

Programul va afișa cuvântul mai mic lexicografic.

Restricții și precizări:

Cuvintele au cel mult 100 de caractere și sunt distincte.

Exemplu:

Intrare:

mar cai

Ieșire:

cai
Cum gândim soluția:
  1. Citim cuvintele cu cin
  2. Comparăm cu strcmp(a, b)
  3. Afișăm cuvântul corespunzător semnului rezultatului
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char a[101], b[101];

    cin >> a >> b;

    if (strcmp(a, b) < 0)
    {
        cout << a;
    }
    else
    {
        cout << b;
    }

    return 0;
}

Ce învățăm: pentru două cuvinte distincte, semnul lui strcmp decide imediat răspunsul, fără alte calcule.

PbInfo - Cuvinte în ordine alfabetică

Enunț:

Cerință: Se citesc trei cuvinte. Să se afișeze cele trei cuvinte în ordine alfabetică, separate prin spații.

Date de intrare:

Programul citește de la tastatură cele trei cuvinte, separate prin spații.

Date de ieșire:

Programul va afișa cuvintele sortate lexicografic.

Restricții și precizări:

Cuvintele au cel mult 100 de caractere și sunt distincte.

Exemplu:

Intrare:

bac mar ana

Ieșire:

ana bac mar
Cum gândim soluția:
  1. Comparăm a cu b și le interschimbăm dacă nu sunt în ordine
  2. Comparăm b cu c și le interschimbăm dacă trebuie
  3. Repetăm compararea a cu b și afișăm
  4. Interschimbarea se face cu strcpy printr-un șir auxiliar
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char a[101], b[101], c[101];
    char aux[101];

    cin >> a >> b >> c;

    if (strcmp(a, b) > 0)
    {
        strcpy(aux, a);
        strcpy(a, b);
        strcpy(b, aux);
    }
    if (strcmp(b, c) > 0)
    {
        strcpy(aux, b);
        strcpy(b, c);
        strcpy(c, aux);
    }
    if (strcmp(a, b) > 0)
    {
        strcpy(aux, a);
        strcpy(a, b);
        strcpy(b, aux);
    }

    cout << a << " " << b << " " << c;

    return 0;
}

Ce învățăm: ordonarea a trei valori se face prin trei comparații; metoda se generalizează la oricâte valori.

EXERCIȚII PRACTICE

Exercițiul Practic: compararea cuvintelor

Sarcini de lucru

Completează următoarele sarcini pentru a exersa ordinea lexicografică

Sarcina 1: Comparare manuală

Cerință: Scrie un program C++ complet care citește două cuvinte și afișează DA dacă sunt identice sau NU în caz contrar, folosind compararea manuală (fără strcmp).

Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;

int main()
{
    char a[101], b[101];
    cin >> a >> b;

    int i = 0;
    while (a[i] != '\0' && b[i] != '\0' && a[i] == b[i])
    {
        i++;
    }

    if (a[i] == '\0' && b[i] == '\0')
    {
        cout << "DA";
    }
    else
    {
        cout << "NU";
    }

    return 0;
}

Verifică: cuvintele sunt identice doar dacă ambele s-au terminat simultan, adică ambele au terminator pe poziția i.

Sarcina 2: Cel mai mare cuvânt

Cerință: Scrie un program C++ complet care citește două cuvinte și afișează cuvântul care vine ultimul în ordine alfabetică (cel mai mare lexicografic), folosind strcmp.

Soluție pentru Sarcina 2:
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char a[101], b[101];
    cin >> a >> b;

    if (strcmp(a, b) > 0)
    {
        cout << a;
    }
    else
    {
        cout << b;
    }

    return 0;
}

Verifică: pentru intrarea ana mar, programul afișează mar.

Scrie pe caiet - De reținut

Titlul lecției

Ora 6: Compararea șirurilor - ordinea lexicografică

Definiția lecției

Ordinea lexicografică este ordinea din dicționar: cuvintele se compară caracter cu caracter, de la stânga la dreapta. La prima pereche de caractere diferite, cuvântul al cărui caracter are codul ASCII mai mic vine înainte. Dacă un cuvânt este prefix al celuilalt, cel mai scurt vine înainte. Compararea cu strcmp(a, b) întoarce o valoare negativă dacă a vine înaintea lui b, 0 dacă șirurile sunt identice și o valoare pozitivă în caz contrar. Egalitatea se testează întotdeauna cu strcmp(a, b) == 0, niciodată cu a == b. Compararea manuală parcurge cele două șiruri simultan, până la prima pereche diferită. Compararea stă la baza sortării alfabetice și a lucrului cu dicționare.

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritm comparareManuală citește a, b i = 0 cât timp a[i] != '\0' și b[i] != '\0' și a[i] = b[i] execută i = i + 1 sfârșit cât timp dacă a[i] = b[i] atunci scrie "egale" altfel dacă a[i] < b[i] atunci scrie "a < b" altfel scrie "a > b" sfârșit dacă Sfârșit algoritm

Algoritmul cheie - cod C++

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char a[101], b[101];
    cin.getline(a, 101);
    cin.getline(b, 101);

    int rezultat = strcmp(a, b);

    if (rezultat < 0)
    {
        cout << a << " vine inaintea lui " << b << endl;
    }
    else if (rezultat == 0)
    {
        cout << "Cuvintele sunt egale" << endl;
    }
    else
    {
        cout << b << " vine inaintea lui " << a << endl;
    }

    return 0;
}

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic

Scrie un program care citește două cuvinte și afișează care dintre ele vine primul în dicționar. Pentru cuvintele mar și mal, programul afișează: mal vine înaintea lui mar.

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char a[101], b[101];
    cin >> a;
    cin >> b;

    if (strcmp(a, b) < 0)
    {
        cout << a << " vine inaintea lui " << b << endl;
    }
    else if (strcmp(a, b) > 0)
    {
        cout << b << " vine inaintea lui " << a << endl;
    }
    else
    {
        cout << "Cuvintele sunt egale" << endl;
    }

    return 0;
}