Functii pentru operatii cu siruri de caractere C++

Become a Patron!

Functiile pentru operatii cu siruri se gasesc in header-ul <string.h>.

Functia strlen : int strlen(nume_sir);  – returneaza lungimea efectiva a unui sir (fara a numara terminatorul de sir)

Exemplu:

char a[50] = “ora de informatica”; -> strlen(a) = 18

Functia strcpy : strcpy(sir_destinatie, sir_sursa); – copiaza sirul sir_sursa in sir_destinatie (se simuleaza atribuirea a = b).

ATENTIE!! Nu este permisa atribuirea intre doua siruri de caractere folosind operatorul =. Atribuirea se face folosind functia strcpy .

Exemplu:

Functia strcat : strcat(dest,sursa); – adauga sirului dest sirul sursa. Sirul sursa ramane nemodificat. Operatia se numeste concatenare si nu este comutativa.

Exemplu:

Functia strncat : strncat(dest,sursa,nr); – adauga sirului dest primele nr caractere din sirul sursa. Sirul sursa ramane nemodificat.

Exemplu:

Functia strchr : strchr(sir,c); – are rolul de a cauta caracterul c in sirul sir. Cautarea se face de la stanga la dreapta, iar functia intoarce adresa subsirului care incepe cu prima aparitie a caracterului c. Daca nu este gasit caracterul, functia returneaza NULL (adresa goala). Diferenta dintre adresa sirului initial si cea a subsirului returnat reprezinta chiar pozitia caracterului cautat in sirul dat.

Exemplu:

Functia strrchr : strrchr(sir,c); – are acelasi rol cu strchr , cu deosebirea ca returneaza adresa ultimei aparitii a caracterului (cautarea se face de la dreapta spre stanga; r = right)

Functia strcmp : int strcmp(sir1,sir2); – are rolul de a compara doua siruri de caractere. Valoarea returnata este <0 (daca sir1 < sir2 ), =0 (daca sir1 = sir2 ) si >0 (daca sir1 > sir2 ). Functia strcmp face distinctie intre literele mari si cele mici ale alfabetului. Observatie : Functia strcmp returneaza diferenta dintre codurile ASCII ale primelor caractere care nu coincid.

Functia stricmp : int stricmp(sir1,sir2);  – are acelasi rol cu strcmp , cu deosebirea ca nu face distinctie intre literele mari si cele mici ale alfabetului(i = ignore).

Functia strstr : strstr(sir1,sir2); – are rolul de a identifica daca sirul sir2 este subsir al sirului sir1. Daca este, functia returneaza adresa de inceput a subsirului sir2 in sirul sir1 , altfel returneaza adresa 0. In cazul in care sir2 apare de mai multe ori in sir1 , se returneaza adresa de inceput a primei aparitii. Cautarea se face de la stanga la dreapta.

Functia strtok : strtok(sir1,sir2); –  are rolul de a separa sirul sir1 in mai multe siruri (cuvinte) separate intre ele prin unul sau mai multe caractere cu rol de separator. Sirul sir2 este alcatuit din unul sau mai multe caractere cu rol de separator.

Functia strtok actioneaza in felul urmator:
o Primul apel trebuie sa fie de forma strtok(sir1,sir2); Functia intoarce adresa primului caracter al primei entitati. Dupa prima entitate, separatorul este inlocuit automat prin caracterul nul.
o Urmatoarele apeluri sunt de forma strtok(NULL,sir2); De fiecare data, functia intoarce adresa de inceput a urmatoarei entitati, adaugand automat dupa ea caracterul nul.
o Cand sirul nu mai contine entitati, functia returneaza adresa nula (NULL).

Exemplu:

Functia strspn : int strspn(sir1,sir2); – are rolul de a returna numarul de caractere ale sirului sir1 (caractere consecutive care incep obligatoriu cu primul caracter) care se gasesc in sirul sir2 .

Exemplu:

strspn(“AB2def”,”1B3AQW”); – returneaza 2, pentru ca primele 2 caractere „A‟ si „B‟ din sir1 se gasesc in sir2 .

strspn(“FAB2def”,”16A32BF”); – returneaza 0, deoarece caracterul „F‟ cu care incepe sir1 nu se gaseste in sir2.

Functia strcspn : int strcspn(sir1,sir2); – are rolul de a returna numarul de caractere ale sirului sir1 (caractere consecutive care incep obligatoriu cu primul caracter) care nu se gasesc in sirul sir2 .

Exemplu:

strcspn(“AB2def”,”123”); – returneaza 2, pentru ca primele 2 caractere din sir1 nu se gasesc in sir2

Functia strlwr : strlwr(sir) – are rolul de a converti toate literele mari din sir in litere mici. Restul caracterelor raman neschimbate.

Functia strupr : strupr(sir) – are rolul de a converti toate literele mici din sir in litere mari. Restul caracterelor raman neschimbate.

Functia strbrk : strbrk(sir1,sir2); – actioneaza in felul urmator:

o Cauta primul caracter al sirului sir1 in sir2 . Daca este gasit, returneaza adresa sa din cadrul sirului sir1 si executia se termina. Altfel, se trece la pasul urmator.
o Cauta al doilea caracter al sirului sir1 in sir2 . Daca este gasit, returneaza adresa sa din cadrul sirului sir1 si executia se termina. Altfel, se trece la pasul urmator.
o …
o Daca nici un caracter al sirului sir1 nu apartine sirului sir2 , functia returneaza adresa nula.

Functia atof : double atof(sir); –  converteste un sir catre tipul double. Daca aceasta conversie esueaza (se intalneste un caracter nenumeric), valoarea intoarsa este 0. Aceasta functie (ca si cele similare) necesita includerea librariei stdlib.h.

Functia _atold : double _atold(sir); – converteste un sir catre tipul long double. Daca aceasta conversie esueaza, valoarea intoarsa este 0.

Functia atoi : int atoi(sir); – converteste un sir catre tipul int. Daca aceasta conversie esueaza (se intalneste un caracter nenumeric), valoarea intoarsa este 0.

Functia atol : long atol(sir); – converteste un sir catre tipul long.Daca aceasta conversie esueaza (se intalneste un caracter nenumeric), valoarea intoarsa este 0.

Functia itoa : itoa(int valoare,sir,int baza); – converteste o valoare de tip int in sir, care este memorat in variabila sir . Baza retine baza de numeratie catre care sa se faca conversia. In cazul bazei 10, sirul retine si eventualul semn -.

 Functia ltoa : ltoa(long valoare,sir,int baza); – converteste o valoare de tip long int in sir, care este memorat in variabila sir.

Functia ultoa : ultoa(unsigned long valoare, sir,int baza); – converteste o valoare de tip unsigned long in sir, care este memorat in variabila sir.

Teorie grafuri neorientate C++

Become a Patron!

Un graf neorientat este o pereche ordonată de mulţimi G = ( V , E ).

Multimea V este o multime nevida si finita de elemente denumite varfurile grafului.

Multimea E este o multime de perechi formate cu ajutorul varfurilor din graf.

In cazul grafurilor neorientate, perechile de varfuri din multimea E sunt neordonate si se numesc muchii. Ele nu au directie. Muchia formata de varfurile x si y se noteaza cu [x,y], varfurile x si y fiind denumite extremitatile muchiei.

Daca exista o muchie determinata de varfurile x si y atunci, varfurile x si y se numesc adiacente. De asemenea, varfurile x si y sunt considerate incidente cu muchia pe care o formeaza. Fiecare extremitate a unei muchii este considerata incidenta cu muchia respectiva.

Intre varfurile oricarui graf neorientat poate exista cel mult o muchie.

1. Reprezentarea vizuala a grafurilor neorientate:

  1. Pentru a usura reprezentarea acestora, pentru fiecare varf al grafului se deseneaza un cerc si in interiorul cercului se trece numarul varfului.
  2. Vom reprezenta fiecare muchie ca fiind o linie dreapta care pleaca de la un varf si ajunge la celalalt.

Exemplu:

2.Gradul unui varf

Se numeste grad al unui varf x numarul de muchii incidente cu varful respectiv. Graful unui varf x se noteaza cu d(x).

Astfel apar 2 notiuni noi:

Varful izolat = un varf care are gradul 0.

Varful terminal un varf care are gradul 1.

x 1 2 3 4 5 6
d(x) 3 2 1 1 3 0

Observam din tabelul de mai sus faptul ca varful 6 este un varf izolat si ca varfurile 3 si 4 sunt varfuri terminale.

Teorema: Suma gradelor unui varf neorientat este egala cu dublul numarului de muchii din graf.

Σd(x) = 2n

3. Notiunile de lant si ciclu

Intr-un graf neorientat, se numeste lant o secventa de varfuri cu proprietatea ca oricare doua varfuri consecutive din secventa sunt adiacente. De exemplu, pentru graful dat, [3,1,2,5,1,3,1] este un lant cu lungimea 6.

Lungimea unui lant = numarul de muchii pe care acesta le are in componenta.

Un lant este elementar atunci cand nu contine acelasi varf de mai multe ori. De exemplu, pentru graful dat, [1,2,5] este un lant elementar cu lungimea 2.

Un lant este simplu daca nu contine de mai multe ori aceeasi muchie. De exemplu, pentru graful dat, [3,1,2,5,4] este un lant simplu cu lungimea 4.

Se numeste ciclu, un lant simplu in care varful initial coincide cu varful final. In alte cuvinte lantul pleaca din varful x si ajunge tot in varful x. De exemplu, pentru graful dat, [1,2,5,1,2,5,1] este un ciclu.

Un ciclu este elementar daca nu contine de mai multe ori acelasi varf (cu exceptia extremitatilor). De exemplu, pentru graful dat [5,1,2,5], este un ciclu elementar.

Teoreme:

Un lant/ciclu elementar se numeste hamiltonian daca el trece prin toate varfurile grafului.

Un lant/ciclu elementar se numeste eulerian daca el trece prin fiecare muchie al grafului o singura data.

4. Grafuri asociate unui graf dat

Fie G = (V,E) un graf orientat.

Graful G’=(V,E’) se numeste un graf partial al lui G daca E’ ⊂ E.

Un graf partial al lui G se obtine eliminand muchii din graful G.

Graful partial de mai sus a fost obtinut prin eliminarea muchiilor [1,3], [1,5] din graful initial.

Un subgraf al lui G se obtine eliminand un varf si toate muchiile incidente cu acesta.

Subgraful de mai sus a fost obtinut prin eliminare din graful initial a varfului 5 si a tuturor muchiilor incidente cu acesta: [1,5], [2,5], [4,5].

Un subgraf partial al lui G se obtine eliminand varfuri din graful G, muchiile incidente cu varfurile eliminate, precum si alte muchii din graful G.

Subgraful partial de mai sus a fost obtinut prin eliminare din graful initial a varfului 5 si a muchiilor [1,3], [1,5], [2,5], [4,5].

Teoreme:

Fie G un graf neorientat cu n varfuri si m muchii:

a) Numarul de grafuri partiale ale lui G este 2m-1.

b) Numarul de subgrafuri ale lui G este 2n-1.

5. Tipuri speciale de grafuri

Un graf neorientat se numeste complet daca oricare 2 varfuri ale acestuia sunt adiacente.

Graful neorientat complet cu n varfuri se numeste Kn si contine [n(n-1)]/2 muchii.

Exemplu:

Un graf neorientat G = (V,E) se numeste bipartit daca multimea varfurilor sale poate fi partitionata in doua submultimi A si B nevid ( A ∪ B = V ; A ∩ B = Ø) astfel incat orice muchie sa aia o extremitate in A si una in B.

In graful de mai sus, multimea A = {1,2,3} si multimea B = {4,5,6,7}.

Un graf neorientat se numeste regulat daca toate varfurile sale au acelasi grad.

 Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

Citirea/afisarea sirurilor de caractere – C++

Become a Patron!

Sirurile de caractere pot fi initializate inca de la declarare sau citite pe parcursul programului.

a) Citirea unui sir de caractere se poate face ca citirea oricarui tablou, intr-un for, caracter cu caracter (desi nu este recomandata). In acest caz, terminatorul de sir nu este memorat automat, el trebuie pus explicit dupa ultimul caracter din sir.

b) Se poate face pur si simplu, folosind ‘cin>>’ . Caracterul nul este adaugat automat. Dezavantajul este ca in acest fel nu se pot citi siruri care contin mai multe cuvinte separate prin spatii. Citirea sirului se sfarseste la intalnirea primului caracter blank (de ex, daca se citeste “ora de informatica”, variabila c va retine numai “ora”).

c) Se poate folosi o functie speciala pentru citirea sirurilor de caractere, inclusa in biblioteca <string.h> (varianta recomandata).

Exemplu:

        Functia ‘cin.get’ citeste un sir de caractere sau pana cand au fost citite nr-1 caractere, sau daca s-a intalnit caracterul x. Al treilea parametru poate lipsi, caz in care el este implicit caracterul ‟\n‟ (new line). Sunt citite si caracterele albe, caracterul nul este inserat automat iar caracterul transmis ca ultim parametru nu este inserat in sir.

Functia cin.get( ) fara parametri are rolul de a citi un caracter (alb sau nu).
Functia cin.get(char c) are rolul de a citi un caracter (alb sau nu) pe care il incarca in variabila c.
Observatie: In cazul utilizarii repetate a functiei cin.get(a,nr,x), dupa fiecare folosire trebuie citit caracterul de la sfarsitul fiecarui sir , adica ‟\n‟ (in caz contrar, acest caracter va fi incarcat la inceputul urmatorului sir, a carui citire se termina la caracterul Enter, deci citirea celui de-al doilea sir se termina inainte de a incepe, iar al doilea sir va fi sirul vid). Aceasta citire a caracterului ‟\n‟ se realizeaza folosind cin.get() fara parametri.

Siruri de caractere C++ – notiuni introductive

Become a Patron!

O constanta de tip sir de caractere de declara intre doua caractere “. In memoria interna, o constanta de acest tip este retinuta sub forma unui vector de caractere. Fiecare componenta a sirului (incepand cu cea de indice 0) retine codul ASCII al caracterului pe care il memoreaza. Conventia este ca ultimul octet sa retina 0 (codul caracterului nul). Caracterul nul este memorat automat. Trebuie rezervate lungimea_sirului+1 caractere char (+1
pentru caracterul nul). Limbajul C/C++ permite initializarea unui tablou de caractere printr-o constanta sir, care include automat caracterul null.

Exemplu :

  1. char vect[11]=”calculator”;
  2. char vect[]=”calculator”; (compilatorul face calculul numarului de octeti necesari)
  3. char vect[100]=”calculator”; (s-au rezervat mai multi octeti decat era necesar)

Sirurile de caractere sunt de fapt tablouri de caractere, care au ca ultim element un terminator de sir, caracterul null.

Exemplu:

De asemenea, sirurile de caractere pot fi declarate folosind pointeri.ATENTIE!! Unui sir astfel initializat nu i se poate modifica valoarea. El este retinut in memorie ca un sir constant. Pe langa aceasta, un sir declarat cu char *p nu poate fi citit normal, cu cin sau cin.get. Nu se recomanda folosirea lor decat la apelul functiilor strtok, strchr,strstr sau in momentul declararii unor siruri constante.

Exemplu: char *p = “sir constant”.

Pointerii retin informatia de la o anumita adresa. Astfel, stiind ca functiile strtok, strchr si strstr returneaza adresa unor elemente, pentru accesa informatia de la acea adresa este recomandat sa folosim un char * (pointer catre un element de tip char).

 

Vectorul frecventa – afisarea elementului cu cel mai mare numar de aparitii C++

Become a Patron!

Se citeste un numar foarte mare de elemente cu doua cifre de la tastatura (retinerea lor intr-un vector devine imposibila din cauza spatiului ocupat). Se doreste afisarea elementului care apare de cele mai multe ori in sir. Stiind ca numerele citite sunt intre 10 si 99, putem folosi vectorul frecventa, pentru a retine numarul de aparitii al fiecarui numar – frecv[a] retine de cate ori apare numarul a in sir.

Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

Cel mai mic multiplu comun (cmmmc) al unui vector C++

Become a Patron!

Fiind dat un vector v de N elemente intregi, se afiseaza cel mai mic multiplu comun al elementelor vectorului.

Cel mai mic multiplu comun (cmmmc) al unui vector:

Exemplu:

cel mai mic multiplu comun

La fiecare pas am folosit functia de cmmmc apelata pentru cmmmc-ul elementelor anterioare si elementul curent. Cmmc-ul nou este cel mai mic multiplu comun al cmmmc-ului vechi si al elementului curent. Functia de cmmmc dintre doua numere poate fi vazuta si aici.

Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂