sâmbătă, 1 decembrie 2012

Tutorial C++: Input / Output cu CIN şi COUT

Output cu COUT

Am văzut că pentru a putea folosi obiectele cout (console output) şi cin avem nevoie de biblioteca (library) iostream. Ca să putem folosi această bibliotecă trebuie să includem următoarele linii la începutul programului:

#include <iostream>
using namespace std;
Afişarea numerelor sau stringurilor pe ecran (consolă) se face cu obiectul cout şi operatorul de inserţie <<. De exemplu:
cout << "Quick wafting zephyrs vex bold Jim\n"
     << "The five boxing wizards jump quickly.\n";
cout afişează datele aşa cum le daţi. cout nu formatează nimic, nu adaugă spaţii între cuvinte, nu adaugă new line, etc. Exemplu:
cout << "Quick" << "wafting" << "zephyrs";
Se va afişa:
Quickwaftingzephyrs
Dacă vrem spaţii între cuvinte atunci adăugăm şi spaţii:
cout << "Quick" << " " << "wafting" << " " << "zephyrs";
Lanţul cout poate fi oricât de lung vreţi. Nu e obligatoriu să-l aveţi pe un singur rând (vezi primul exemplu). Trebuie să se termine cu punct şi virgulă.
Puteţi, de asemenea, să aveţi expresii într-o instrucţiune cout:
cout << "Aria cercului este:" << (PI * raza * raza);
Practic orice obiect care are o reprezentare string poate fi afişat pe ecran cu cout.
Aţi văzut că un rând nou se inserează cu secvenţa escape '\n'. Ei bine, mai este o metodă cu endl. De exemplu:
cout << "Quick wafting zephyrs vex bold Jim" << endl << "The five boxing wizards jump quickly.\n";
Atunci când vreţi să afişaţi numere double s-ar putea să nu obţineţi ceea ce vreţi.
double phi = 4.893654;
cout << phi;
Se va afişa 4.893654. Dar poate vreţi să afişaţi doar primele două zecimale. Cum faceţi asta? Cu următoarele instrucţiuni:
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
Prima instrucţiune ne permite să folosim funcţia precision doar pentru partea fracţionară (de după punct); altfel ar fi luat în considerare tot numărul.
A doua instrucţiune afişează punctul zecimal de fiecare dată - chiar şi pentru numere întregi.
A treia instrucţiune setează precizia numărului la 2 zecimale. Se fac rotunjiri! Argumentul funcţiei trebuie să fie pozitiv şi număr întreg sau o expresie evaluată la int.
După aceste instrucţiuni puteţi folosi cout normal ca să afişaţi numerele reale în noul format:
cout << phi; // 4.89
Puteţi folosi opţiunea ios::scientific ca să afişaţi în notaţie ştiinţifică:
double phi = 0.0000123;
cout.setf(ios::scientific);
cout.setf(ios::showpoint);
cout.precision(2);
cout << phi; // 1.23e-005

Input cu CIN

Similar putem folosi cin (console input) pentru operaţii de input, adică de obţinere a datelor de la tastatură (de la user). Se foloseşte cu operatorul de extracţie >>.
int a, b;
cout << "Introduceti doua numere: ";
cin >> a >> b; 
cout << "Suma lor este: " << (a + b);
Atunci când întâlneşte instrucţiunea cin, programul aşteaptă inputul de la user. Atribuie prima valoare primei variabile, a doua valoare variabilei a doua, etc.
Programul nu citeşte datele de intrare decât după ce utilizatorul apasă ENTER la tastatură. În acest fel userul se poate corecta folosind backspace.
Obiectul cin foloseşte spaţiile albe (space, enter, tab, etc.) ca delimitatoare. Asta înseamnă că datele de intrare trebuie despărţite prin câte un spaţiu sau rând nou (new line).
cin ignoră - şi elimină din fluxul (stream) de intrare - toate spaţiile albe până întâlneşte un input valid.
Deoarece ignoră spaţiile albe, nu puteţi citi propoziţii de cuvinte cu cin. Trebuie să folosiţi funcţia getline (care citeşte până când întâlneşte un caracter new line pe care îl extrage din stream şi-l ignoră). Se foloseşte cu tipul string:
string fullname;
getline(cin, fullname);
cout << "\nNumele tau este: \n" 
     << fullname << endl;
Primul parametru trebuie să fie cin pentru că citiţi de la tastatură.
Al doilea parametru este o variabilă string în care va fi salvat şirul.
Streamul (fluxul) de intrare (input stream) reprezintă şirul datelor de intrare. Imaginaţi-vă un flux de informaţii care curge către calculator. Aceste date vin nu numai de la tastatură, ci şi de la alte dispozitive de intrare: mouse, scanner, mircofon, etc.
cin se ocupă numai de tastatură.
Similar, cout scrie în streamul de ieşire (output stream) care este afişat pe ecran.
Exemplu: Se citesc de la tastatură trei numere naturale. Să se afişeze suma lor.
Pentru datele de intrare: 14 89 99 se va afişa 202.
#include <iostream>
using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    cout << a + b + c;  // parantezele pot lipsi

    system("PAUSE"); 
    return 0;
}
Cu cin puteţi citi numere întregi şi reale, stringuri şi caractere, etc.

Tutorial C++: Constante - Operatori Aritmetici - Atribuire compusă - Type Casting

Constante

O constantă, sau constantă literală, este o reprezentare a unei valori fixe în program. O parte din constante le-aţi folosit în tutorialul anterior la iniţializarea variabilelor.
Constantele de tip int sunt numere întregi: 45, -123, 0, 8965 etc.
Constantele de tip double (floating-point - virgulă mobilă) sunt numere reale: 3.14, 1.6867, 0.0001, 7.0 etc. Numerele reale mai pot fi exprimate şi prin notaţia ştiinţifică.
De exemplu, numărul 1.5 * 104 poate fi reprezentat în C++ prin constanta 1.5e4, unde e înseamnă 10 la puterea.
Numărul de după e reprezintă exponentul şi, deci, nu poate conţine punct zecimal. Poate fi negativ.
Atenţie! În C++ numerele fracţionare nu pot conţine virgulă, ci doar punct zecimal.
Constantele de tip caracter (char) sunt de forma: 'caracter', unde caracter reprezintă un singur caracter ASCII.
De exemplu, 'a', 'x', 'G', 'P'. Caracterele se pun întotdeauna între două apostrofuri.
Stringurile, şirurile de caractere, se pun între ghilimele. Exemplu: "Sunt un string.".
Atenţie! Simbolul "B" este un string, nu un caracter de tip char. Următoarea atribuire este ilegală: char s = "F"; // Gresit.
Secvenţele formate din backslash \ şi un singur caracter se numesc secvenţe escape. Sunt folosite pentru a exprima caracterele imposibil de reprezentat printr-un singur simbol. Acestea sunt cele mai folosite şi utile secvenţe escape:

Secvenţă escapeSemnificaţie
\nRând nou - new line
\tTab orizontal
\\Backslash
\'Apostrof
\"Ghilimele
\aAlertă (Sunet)
Secvenţele escape sunt tratate ca un singur caracter (deşi au două), deci se pun între apostrofuri. Pot fi incluse în stringuri.
De exemplu, următoarea secvenţă de cod afişează textul pe două rânduri:
cout << "Acesta este\n" << "un exemplu.";
Stringurile sunt memorate fie în vectori de caractere, fie în obiecte de tip string (aceste tipuri vor fi prezentate în tutorialele viitoare).
Constantele booleane sunt true şi false. Reprezintă cele două valori pentru tipul bool.
C++ ne permite să declarăm variabile constante (constante declarate) cu ajutorul modificatorului const. Exemplu:
const int MAX_PLAYERS = 500;
const double PI = 3.14159;
După ce au fost definite, aceste constante declarate nu pot fi modificate de nimic în timpul execuţiei programului, nici măcar de o atribuire ulterioară (acest lucru va genera o eroare de compilare).
Acest mod de a defini constante în program este foarte util. Dacă folosiţi o valoare de mai multe ori în program este bine să-i daţi un nume şi să folosiţi numele în loc de valoarea fixă propriu-zisă. Astfel veţi putea modifica mai uşor valoarea constantei în program.
Modificatorul const poate fi folosit cu orice tip. Se numeşte modificator deoarece modifică (restricţionează) variabila declarată.
Deşi C++ nu impune acest lucru, prin convenţie constantele declarate se scriu cu litere mari şi cuvintele ce le alcătuiesc se despart prin underscore (_).
#include <iostream>
#include <string>  // Necesar pentru tipul string
using namespace std;

int main()
{
    const double PI = 3.14159;
    double raza;
    string mesaj = "Introduceti raza cercului: ";

    // cin este folosit pentru a obtine date de la user
    cout << mesaj << '\n'; cin >> raza;

    double aria = PI * raza * raza;

    cout << "Aria cercului este: " << aria;
    cout << '\n';

    system("PAUSE"); // PAUZA
    return 0;
}
Executaţi acest program.

Operatorii aritmetici

O expresie este formată din variabile, constante, operatori şi apeluri de funcţii.
Operatorii aritmetici definiţi în C++ sunt: + (adunare), - (scădere), * (înmuţire), / (împărţire) şi % (modulo).
Modulo este operaţia prin care se obţine restul împărţirii unui număr la alt număr. Exemplu: 5 % 2 returnează 1.
Ambii operanzi pentru operatorul % trebuie să fie de tip întreg.
Tipul rezultatului returnat de operatorii aritmetici depinde de tipul operanzilor.
Dacă ambii operanzi sunt de tip int atunci şi rezultatul va fi tot de tip int.

int result = 8 / 5; // 1
Dar dacă unul dintre operanzi este de tip double atunci rezultatul va fi de tip double.
8.0 / 5 // 1.6
Regulile de evaluare sunt ca la matematică. Operatorii de înmulţire şi împărţire au prioritate.
Puteţi altera ordinea evaluării folosind paranteze.
Operanzii nu trebuie să fie neapărat numere, pot fi de asemenea subexpresii:
double res = (3 + 2) / 2.0 * 3; // 7.5
Dacă nu sunteţi siguri de ordinea în care vor fi evaluate expresiile, vă recomand să folosiţi parantezele. Nu strică şi nu scad performanţa programului.
Operatorul ++ creşte valoarea variabilei cu 1, iar operatorul -- scade valoarea variabilei cu 1.
Când sunt folosiţi ca prefix, operatorii returnează noua valoare a variabilei, iar când sunt folosiţi ca sufix operatorii returnează valoarea curentă a variabilei. În ambele cazuri variabila este modificată, diferenţa constă în valoarea returnată. Exemplu:
int a = 2, b = 2;
int x = a++;  // sufix: se returneaza 2
int y = ++b;  // prefix: se returneaza 3

cout << x << ' ' << y << '\n';  // 2 3
cout << a << ' ' << b;  // 3 3
Aceşti operatori vor fi folosiţi cel mai des în structurile iterative (for, while etc.). Au prioritatea mai mare ca înmulţirea şi împărţirea!
Tabelul cu prioritatea operatorilor.

Atribuire compusă | Type casting

Atunci când vrem să actualizăm valoarea unei variabile vom folosi probabil această expresie a = a + b, unde a creşte cu valoarea lui b.
Există totuşi o notaţie prescurtată pentru acest tip de atribuire:

variabila operator= expresie;
De exemplu:
int a = 4, b = 2;
a += b + 1; // echivalent cu: a = a + (b + 1);
a *= b - 2; // echivalent cu: a = a * (b - 2);
a %= (b - 1) + 5; // echivalent cu: a = a % ((b - 1) + 5);
Type casting sau conversia de tip este metoda prin care puteţi converti o valoare de un tip într-un alt tip. Se realizează cu operatorul static_cast. De exemplu, dacă avem un int şi vrem să-l convertim în double, folosim:
int a = 7; double x;
x = static_cast<double>(a);
Sintaxa generală:
static_cast<tip>(expresie);
Acest operator nu modifică valoarea variabilei convertite, ci o returnează ca o valoare nouă convertită în tipul specificat. Folosind conversia puteţi afla valoarea ASCII a unui char:
int val; char p = 'A';
val = static_cast<int>(p); // 65
Metoda învechită, aproximativ echivalentă cu cea de sus, este următoarea:
int val; char p = 'A';
val = (int)p;
// sau
val = int(p);
Atunci când convertiţi din double (sau float) într-un tip întreg (int, short, long etc.) veţi pierde partea fracţionară (de după punctul zecimal). Nu se fac rotunjiri! Exemplu:
double epsilon = 4.9565;
int alpha = static_cast<int>(epsilon); // 4
Sfat: Oriunde puteţi avea o constantă literală în program, puteţi avea şi o expresie, deoarece expresia, în cele din urmă, va fi evaluată la o singură valoare.

vineri, 16 noiembrie 2012

Tutorial C++: Identificatori - Variabile - Atribuire

Identificatori

Identificatorii reprezintă numele dat entităţilor dintr-un program C++.
Identificatorii pot începe cu literă sau underscore (_) şi pot continua numai cu litere, cifre sau underscore. Exemplu:

Apple, _mCount, startDownload1
Exemplu de identificatori nevalizi:
1apple, _mCount.20, 123
Aceştia vor fi respinşi de compilator. Nu sunt identificatori valizi deoarece: primul începe cu o cifră, al doilea conţine un caracter nepermis (punct), iar ultimul este un număr.
C++ este case-sensitive, deci Home este diferit de HoMe.
Nu folosiţi ca identificatori cuvintele rezervate - reserved keywords - şi identificatorii predefiniţi (de exemplu cout).
Deşi este posibil să redefiniţi aceşti identificatori, nu recomand asta deoarece fac parte din bibliotecile standard C++, şi cu siguranţă veţi avea nevoie de acestea.
De cele mai multe ori, IDE-urile colorează cuvintele rezervate în albastru, deci nu trebuie să le învăţaţi.
Nu există limită pentru numărul de caractere pe care-l poate avea un identificator. Unele compilatoare vor lua în considerare doar un anumit număr de caractere. Este un număr mare deci nu vă faceţi griji.
O convenţie populară (care a devenit universală în OOP) de numire este camelCase. În notaţia camelCase, literele mari sunt folosite pentru a delimita cuvintele dintr-un identificator. De exemplu:
bigApple, getName, setCount, estePrim
Prima literă poate fi mare, dar asta de obicei când numiţi clase (tipuri definite de programator).

Variabile

De cele mai multe ori programele lucrează cu informaţii. Aceste informaţii trebuie salvate undeva. Acest undeva este memoria.
Pentru a putea manipula informaţia în program, folosim variabile. Variabilele trebuie declarate înainte de a putea fi folosite. A declara o variabilă înseamnă:

  • Să specifici ce fel de valori vei memora în respectiva variabilă
  • Să-i dai un nume
Tipul de dată specifică ce valori poate memora o variabilă şi cât spaţiu va ocupa în memorie.
Calculatorul trebuie să cunoască tipul de dată al variabilei deoarece pe baza acestuia stabileşte cât spaţiu rezervă variabilei respective şi stabileşte algoritmii de codificare şi decodificare ai informaţiei.
De exemplu, caracterul 'a' în memorie este 1100001, dar acest şir de 1 şi 0 este de fapt numărul 97 scris în binar. Deoarece calculatorul ştie (datorită tipului de date) că lucrează cu un caracter, acesta va afişa (atunci când îi cerem) pe ecran caracterul a în loc de numărul 97.
Calculatorul ştie permanent adresa de memorie a fiecărei variabile. Astfel poate să actualizeze informaţia stocată în respectiva locaţie.
Puteţi afla adresa de memorie a variabilei folosind operatorul & (voi discuta mai multe despre asta în tutorialul despre pointeri).
int numar;
double pi, epsilon;
Prima linie declară o variabilă de tip int care poate memora numai numere întregi (integer).
A doua linie declară două variabile de tip double care pot memora numere reale (floating-point).
Observaţi că puteţi declara mai multe variabile de acelaşi tip pe aceeaşi linie despărţite prin virgulă. De asemenea, instrucţiunea de declarare se termină cu punct şi virgulă.
Pe lângă int şi double mai există tipurile char, float, bool, short, long. Toate acestea se numesc tipuri fundamentale (tipuri primitive).
Tabelul cu tipurile fundamentale îl găsiţi aici. NU trebuie să-l memoraţi!
Trebuie doar să ştiţi că int ocupă de obicei 4 bytes şi este folosit pentru numere întregi, double ocupă 8 bytes şi este folosit pentru numere reale, iar char ocupă 1 byte şi este folosit pentru caractere ASCII.
Tipurile întregi sunt: short (2 bytes), int, long (8 bytes). Puteţi trata char ca pe un tip întreg - deoarece fiecărui caracter ASCII îi corespunde un număr întreg - dar nu recomand acest lucru.
Tipurile reale sunt: float (4 bytes) şi double.
Tipul bool ocupă 1 byte şi memorează doar două valori: true şi false.
// Sintaxa de declarare
tip_data variabila1, variabila2, variabila3, ..., variabilaN;

// Exemple
int x, y, z;
char litera; bool ok;
double alfa, theta;
Fiecare din tipurile întregi pot fi unsigned, însemnând că reprezintă doar numere întregi pozitive. Evident că mulţimea de valori va fi mai mare.
De exemplu, dacă int ia valori din intervalul [-2,147,483,647 până la 2,147,483,647] atunci unsigned int va lua valori din intervalul [0 la 4,294,967,295]. Dacă vreţi să ştiţi cum sunt reprezentate numerele negative într-un calculator, intraţi aici.

Atribuirea

Atribuirea (asignarea) în C++ se face cu operatorul = (operatorul de atribuire). Atribuirea este operaţia prin care puteţi schimba valoarea unei variabile în mod direct.

int a = 40;
Mai sus am atribuit variabilei a valoarea 40. Observaţi că am făcut acest lucru imediat după ce am declarat variabila. Se citeşte a ia valoarea 40. (NU vă gândiţi la noţiunea de egalitate din matematică. Pentru asta avem operatorul ==).
Atunci când sunt declarate, variabilele nu au o valoare bine definită. De aceea este important să iniţializaţi o variabilă înainte de a o folosi.
Variabilele declarate global (în afara oricărei funcţii şi clase) sunt iniţializate automat cu valoarea implicită. Pentru tipurile întregi aceasta este 0, pentru bool este false, iar pentru char este '\0'.
Se zice că o variabilă este iniţializată atunci când îi atribuiţi o valoare pentru prima dată.
Mecanismul de asignare funcţionează în felul următor:
Partea din dreapta operatorului = (rvalue), care poate fi o variabilă, o constantă, sau o expresie, este evaluată, şi rezultatul evaluării este memorat în partea din stânga operatorului = (lvalue), care trebuie să fie o variabilă.
int x;
x = 45 + 32;
Variabila x are valoarea 77.
Deoarece operatorul = returnează valoarea atribuită variabilei, este posibil să-l folosim în felul următor:
int a, b;
a = b = 5;
Atenţie! Operaţia de atribuire este evaluată de la dreapta la stânga!!
În exemplu, b ia valoarea 5, iar apoi a ia valoarea returnată de operatorul = din subexpresia b = 5, adică a ia valoarea 5.
Fie următorul exemplu:
int a = 4, b;
b = a = 3;
Atât a cât şi b vor fi 3.
Atunci când daţi valori variabilelor încercaţi să nu amestecaţi tipurile. De exemplu unei variabile de tip int nu-i daţi valoarea 5.678 (double). Bineînţeles că în variabila int va fi memorat doar 5 (partea întreagă a lui 5.678), deoarece compilatorul face conversia automat. Dar aceste conversii automate, chiar dacă nu generează erori, pot duce la buguri în program.

Rulaţi următorul program:

#include <iostream>
using namespace std;

int main()
{
    int a, b = 10;
    double x, z, pi = 3.14;
    
    a = b = 30;
    x = pi;     // x este initializat
    z = x * pi; // * - inmultire
    b = (a + b) - 2 * b;
    
    // cout afiseaza pe ecran
    cout << a << ' ' << b << ' ' << x << ' ' << z;
    system("PAUSE"); // PAUZA
    return 0;
}

vineri, 9 noiembrie 2012

Tutorial C++: Structura unui program C++

#include <iostream>
using namespace std;

int main()
{
    // Afiseaza pe ecran Hello World
    cout << "Hello World";
    return 0;
}

Directivele preprocesor

#include <iostream>
Această linie se numeşte directivă preprocesor sau simplu directivă. Se deosebeşte de celelalte linii de cod prin faptul că începe cu #.
Rolul acestor linii este multiplu. Aici, directiva #include are rolul de a preciza compilatorului faptul că vom folosi în program entităţile (funcţii, clase, constante, etc.) din fişierul iostream (cout este un obiect definit în namespace-ul std din iostream).
În acest mod putem scrie programe pornind de la altele existente, fără a rescrie conţinutul lor în noul program. E un mod de a salva timp, spaţiu şi bani.
Fişierul iostream face parte din standardul C++ (compilatorul ştie unde se află, de aceea nu trebuie să precizăm întreg path-ul).
Directivele nu se termină cu punct şi virgulă (Reţineţi asta!).
Următoarea linie using namespace std; spune că vom folosi toate numele (denumirile entităţilor) din secţiunea (această secţiune se numeşte de fapt namespace; veţi afla mai târziu ce este acesta) std din iostream.
Majoritatea programelor C++ vor începe cu aceste două linii. Fără ele nu veţi putea afişa pe ecran şi nu veţi putea citi date de la user.

Funcţia main

Un program C++ constă practic doar din funcţia main. Atunci când rulaţi programul, sistemul de operare invocă automat funcţia numită main.
Funcţiile - alte denumiri pentru conceptul de funcţie sunt: procedură, subprogram, metodă (în OOP) - sunt entităţi ce grupează sub un singur nume o porţiune de cod din program.
Funcţiile pot fi apelate (invocate) precizând numele acestora. Atunci când o funcţie este invocată, codul funcţiei - se află între acolade - va fi executat.
Observaţi că o funcţie permite executarea aceluiaşi cod de mai multe ori fără a scrie respectivul cod de mai multe ori în program.
Main este entry-pointul (punctul de intrare) programului. Aproape toate limbajele de programare necesită definirea unei funcţii main. Fiecare program trebuie să aibă un punct de start, iar acest punct este funcţia main.
Linia int main() se numeşte antetul sau header-ul funcţiei. În antet apar: tipul valorii returnate de funcţie (aici int), numele funcţiei (aici main), parametrii între paranteze (dacă există).
Corpul funcţiei (function body) constă din cele două acolade şi codul definit între ele.
Instrucţiunea return 0; returnează valoarea 0 şi totodată opreşte execuţia funcţiei. Deoarece sistemul de operare a apelat funcţia, tot el este acela care va primi valoarea returnată de main. Codul 0 semnifică faptul că programul a rulat fără probleme.

Instrucţiuni şi comentarii

Instrucţiunile (statements) reprezintă comenzi către calculator; sarcinile pe care acesta trebuie să le îndeplinească.
Toate instrucţiunile trebuie să se termine cu punct şi virgulă ; (Reţineţi asta!).
Puteţi avea mai multe instrucţiuni pe aceeaşi linie atâta timp cât le separaţi prin punct şi virgulă.
În programul de mai sus, instrucţiuni sunt:

using namespace std;
cout << "Hello World";
return 0;
Directivele sunt instrucţiuni - speciale - pentru preprocesor. Preprocesorul este executat de compilator înainte ca procesul de compilare să aibă loc.
Linia // Afiseaza pe ecran Hello World reprezintă un comentariu (comment). Comentariile nu fac nimic (nu sunt instrucţiuni). Sunt de 2 feluri:
- comentariile întinse pe un rând (încep cu //);
- comentariile întinse pe mai multe rânduri (încep cu /* şi se termină cu */). Exemplu:
/* Grumpy wizards make toxic brew 
for the evil Queen and Jack. */
Comentariile sunt ignorate de compilator. Comentariile sunt folosite, în general, pentru a explica anumite părţi ale programului.
Instrucţiunea cout << "Hello World"; afişează pe ecran textul Hello World.

Instrucţiunile din program sunt executate secvenţial (una după alta) de la început până la sfârşit. După ce toate instrucţiunile au fost executate, programul îşi încetează execuţia.
Şi compilatorul scanează secvenţial codul sursă atunci când îl translatează în cod maşină.
Motivul pentru care browserul - pe care-l folosiţi acum - nu se opreşte este că acesta aşteaptă comenzi de la user. Dacă userul apasă pe X, atunci browserul se va opri, deoarece comanda de terminare va fi ultima de îndeplinit.
Este posibil să alterăm execuţia secvenţială a programului folosind structurile de control (for, if, while, etc.). Acestea modifică flow-ul execuţiei programului în funcţie de anumite condiţii. Voi discuta despre aceste lucruri mai târziu.

miercuri, 7 noiembrie 2012

Tutorial C++: Introducere

Limbajul C++

C++, denumit iniţial C++ cu clase, este o extensie a limbajului C, inventat de Dennis Ritchie la AT&T Bell Laboratories pe la începutul anilor 1970.
Ritchie a folosit acest limbaj pentru a crea şi întreţine sistemul de operare UNIX.
La începutul anilor 1980, Bjarne Stroustrup (tot la AT&T Bell Laboratories) a inventat C++, având ca subset limbajul C. Motivul pentru care a făcut asta a fost că, deşi C era un limbaj popular (şi astăzi continuă să fie) nu avea caracteristicile unui limbaj OOP; C este un limbaj procedural.
OOP (Programarea Obiect-Orientată) este cea mai populară şi puternică tehnică (paradigmă) de programare. Ideea de bază a OOP este că datele pot fi organizate în obiecte, fiecare cu atributele şi acţiunile specifice. Cele trei caracterisitici ale OOP sunt: încapsularea (encapsulation), moştenirea (inheritance) şi polimorfismul (polymorphism). Momentan nu vă bateţi capul cu OOP. Le voi aborda în alte lecţii.
Pe lângă OOP, C++ oferă suport şi pentru programarea generică (cu template-uri), tratarea excepţiilor, are propria sintaxă pentru managementul memoriei (C++ nu dispune de garbage collection), şi altele.

Memoria

Trebuie să ştiţi că toate aplicaţiile pe care le rulaţi pe calculator (inclusiv elementele necesare funcţionării sistemului de operare) sunt încărcate în memoria RAM (Random Access Memory). Această memorie are caracter volatil (adică conţinutul său se poate schimba).
Deci şi aplicaţiile care le veţi crea în C++ vor rula în memoria RAM, sau pe scurt, memorie. Atunci când o aplicaţie este închisă, sistemul de operare poate dispune de curăţarea zonei de memorie ocupată de acea aplicaţie.
Atunci când opriţi calculatorul conţinutul memoriei RAM este pierdut, spre deosebire de hard-disk al cărui conţinut se păstrează. Capacitatea memoriei se măsoară în bytes. Un byte are 8 biţi, iar un bit reprezintă cantitatea de bază a informaţiei din sitemele informatice şi din telecomunicaţii. (0 şi 1).
Fizic un bit este reprezentat în memoria RAM de o pereche formată dintr-un tranzistor şi un capacitor numită celulă de memorie. O celulă de memorie reprezintă 1 bit.
Dacă capacitorul este încărcat (stochează electroni), înseamnă că bitul este 1, iar dacă este descărcat (nu are electroni) înseamnă că bitul este 0.
Celulele de memorie sunt aranjate într-o matrice bidimensională, iar intersecţia dintre linia şi coloana celulei de memorie reprezintă adresa acesteia.
Cunoscând adresa de memorie procesorul, poate cere conţinutul (informaţia) celulei de memorie respective.
Dacă vreţi să ştiţi mai multe despre memoria RAM intraţi pe http://www.howstuffworks.com/ram.htm.

Codul sursă, compilator, IDE

Codul sursă este codul C++ (sau alt limbaj) folosit la scrierea unui program într-un fişier cu extensia - pentru C++ - .cpp sau .cc.
Înainte de a deveni executabil, acest fişier ce conţine codul sursă trebuie translatat într-un limbaj înţeles de calculator (codul maşină sau codul obiect). C++ este un limbaj de nivel înalt, adică este mai apropiat limbajului uman decât limbajului înţeles de calculator.
Compilatorul este un program special care traduce codul sursă în cod maşină (binar).
Mai multe detalii despre compilator: http://whatis.techtarget.com/definition/compiler.
Rezultatul procesului de compilare (şi linkeditare; vezi linkul de mai sus) este fişierul executabil.
Un IDE (Integrated Development Environment) este un program ce cuprinde un editor de text, un compilator, debugger şi builder. Veţi folosi un IDE ca să creaţi programe C++.
Pentru aceste tutoriale vă recomand să folosiţi Visual Studio Express. Puteţi folosi de asemenea şi CodeBlocks.
Sau puteţi folosi IDE-ul online IDEONE.

Tutorial creare proiect C++ în Visual Studio

miercuri, 13 iunie 2012

Bacalaureat 2011 - Problema 4 - Subiectul 3 (Sesiunea iunie-iulie)

Se citesc de la tastatură două numere naturale s1 si s2 (0<s1≤18, 0≤s2≤18) si se cere scrierea în fisierul BAC.TXT, fiecare pe câte o linie, în ordine strict crescătoare, a tuturor numerelor naturale cu exact 5 cifre, pentru care suma primelor două cifre este egală cu s1, iar suma ultimelor două cifre este egală cu s2. Pentru determinarea numerelor indicate se utilizează un algoritm eficient din punct de vedere al timpului de executare.

Exemplu: dacă s1=8, iar s2=7, atunci 35725 este unul dintre numerele care respectă proprietatea cerută (3+5=8 si 2+5=7).

Arată Soluţia

Bacalaureat 2011 - Problema 3 - Subiectul 3 (Sesiunea iunie-iulie)

Subprogramul inserare are doi parametri:
  • n, prin care primeste un număr natural (2≤n≤20);
  • a, prin care primeste un tablou unidimensional care memorează un sir de n numere naturale, fiecare cu cel mult 4 cifre. Cel puţin un element al tabloului este număr par.
Subprogramul modifică tabloul astfel încât după fiecare termen par al sirului inserează valoarea 2011 si furnizează, tot prin parametrii n si a, valorile actualizate ale datelor primite.
Scrieţi în limbajul C/C++ definiţia completă a subprogramului.

Exemplu: dacă n=7 si a=(1,4,5,3,82,6,2) atunci, după apel,
n=11 si a=(1,4,2011,5,3,82,2011,6,2011,2,2011).

Arată Soluţia

Bacalaureat 2011 - Problema 5 - Subiectul 2 (Sesiunea iunie-iulie)

Scrieţi un program C/C++ care citeşte de la tastatură un număr natural n (2≤n≤20) si apoi n cuvinte distincte, fiecare fiind format din cel mult 20 de caractere, numai litere mici ale alfabetului englez. La introducerea datelor, după fiecare cuvânt se tastează Enter. Programul afişează pe ecran numărul de cuvinte dintre ultimele n-1 citite, care încep cu primul cuvânt citit.

Exemplu: dacă n=5 şi cuvintele citite sunt:
bun
buncar
bunici
abundent
bunavoie
pe ecran se afişează 3 (deoarece numai cuvintele buncar, bunici şi bunavoie încep cu bun).

Arată Soluţia

marți, 12 iunie 2012

Bacalaureat 2012 - Problema 4 - Subiectul 3 (Sesiunea speciala)

Fişierul bac.txt conţine pe prima linie un număr natural par n cu cel mult patru cifre, iar pe următoarea linie un şir de n numere naturale cu cel mult nouă cifre. Numerele din şir sunt în ordine crescătoare şi sunt separate prin câte un spaţiu. Se cere să se afişeze pe ecran cel mai mare număr din prima jumătate a şirului care să fie strict mai mic decât oricare număr din a doua jumătate a şirului. Dacă în fişier nu se află o astfel de valoare, pe ecran se afişează mesajul Nu exista. Pentru determinarea numărului cerut se utilizează un algoritm eficient din punctul de vedere al memoriei şi al timpului de executare.

Exemplu: dacă fişierul bac.txt are conţinutul
30
1 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 7 10
atunci pe ecran se afişează 3, iar dacă fişierul are conţinutul
6
3 3 3 3 9 15
atunci pe ecran se afişează Nu exista.

Arată Soluţia

luni, 11 iunie 2012

Bacalaureat 2012 - Problema 3 - Subiectul 3 (Sesiunea speciala)

Se consideră subprogramul minus, cu doi parametri:
  • n, prin care primeşte o valoare naturală 2 < n < 50;
  • v, prin care primeşte un tablou unidimensional cu n elemente, numere întregi cu cel mult 4 cifre.
Cel puţin unul dintre elementele tabloului este nenul.
După fiecare element nenul din tablou, subprogramul inserează câte un nou element, cu aceeaşi valoare absolută, dar cu semn opus, ca în exemplu. Tabloul modificat, precum şi valoarea actualizată a lui n, sunt furnizate tot prin parametrii v, respectiv n. Scrieţi în limbajul C/C++ definiţia completă a subprogramului.

Exemplu: dacă n=5 şi v=(4, -5, 0, 9, 0), atunci după apel n=8, iar v=(4, -4, -5, 5, 0, 9, -9, 0).

Arată Soluţia

Bacalaureat 2012 - Problema 5 - Subiectul 2 (Sesiunea speciala)

Scrieţi un program C/C++ care citeşte de la tastatură două cuvinte distincte, fiecare fiind format din cel mult 30 de caractere, numai litere mici ale alfabetului englez. După primul cuvânt se tastează Enter. Programul verifică dacă prin eliminarea unor litere din cel de al doilea cuvânt se poate obţine primul cuvânt. În caz afirmativ programul afişează pe ecran mesajul DA, altfel mesajul NU.
Exemple: dacă se citesc, în această ordine, cuvintele:

calut
bacalaureat
pe ecran se afişează mesajul DA
iar dacă se citesc, în această ordine, cuvintele:
calut
lacatus
pe ecran se afişează mesajul NU.

Arată Soluţia

miercuri, 4 aprilie 2012

C++ Quiz 2

Start Quiz!

Fiecare întrebare valorează 5 puncte. În total sunt 20 de întrebări.

Aveţi la dispoziţie câte 10 (sau 20) secunde pentru fiecare întrebare. În total aveţi 3 minute şi 40 de secunde timp pentru a termina quizul!

Timp Rămas:

luni, 2 aprilie 2012

C++ Quiz 1

Start Quiz!

Fiecare întrebare valorează 5 puncte. În total sunt 20 de întrebări.

Aveţi la dispoziţie câte 10 secunde pentru fiecare întrebare. În total aveţi 3 minute şi 20 de secunde timp pentru a termina quizul!

Timp Rămas:

sâmbătă, 17 martie 2012

Algoritmi: Metoda bisecţiei

Să zicem că avem funcţia \(f(x) = 3{x} + 3\) şi vrem să găsim acel \(x\) pentru care ecuaţia \(f(x) = 0\) este adevărată, adică vrem să-i găsim rădăcina.
O primă metodă ar fi să alegem un interval unde credem că s-ar afla acest \(x\), să luăm pe rând toate valorile din interval şi să vedem pentru care valoare \(f(x) = 0\) este adevărată. Acest algoritm necesită \(O(n)\) timp de execuţie. Îl putem face şi mai rapid. Cum? Prin metoda bisecţiei.
Metoda bisecţiei constă în reducerea intervalului de căutare prin înjumătăţirea repetată şi selectarea subintervalului în care se găseşte rădăcina. Din acest motiv algoritmul este logaritmic \(O(\log{n})\). Algoritmul este similar cu căutarea binară.
Ca metoda să funcţioneze trebuie ca funcţia, căreia vrem să-i găsim rădăcina, să fie continuă.
Conform teoremei Cauchy-Bolzano (teorema valorii intermediare) dacă \(f\) (o funcţie oarecare) este continuă pe intervalul \([a, b]\) şi \(f(a)\) şi \(f(b)\) au semne opuse, adică \(f(a) * f(b) < 0\), atunci există o valoare \(c\) din intervalul \((a, b)\) pentru care \(f(c) = 0\).
Este evident, deoarece dacă la extremităţi funcţia are semne opuse atunci undeva graficul intersectează axa \(Ox\). Graficul funcţiei \(f(x) = 3{x} + 3\) este următorul:

Observaţi că intersectează axa \(Ox\) în punctul -1.
Pentru această funcţie voi alege intervalul \([a, b]\) - \(a, b\) numere reale. Intervalul va fi împărţit în două subintervale: \([a, c]\) şi \([c, b]\), unde \(c = \frac{(a + b)}{2}\). Căutarea rădăcinii se va face în subintervalul în care funcţia \(f(x) = 3{x} + 3\) îşi schimbă semnul, astfel:
  • Dacă \(f(a) * f(c) < 0\), atunci căutarea continuă în intervalul \([a, c]\);
  • Altfel căutarea continuă în intervalul \([c, b]\).
Procesul se termină atunci când se ajunge la intervalul \([a, b]\) pentru care \(b-a < sigma\), unde \(sigma\) este eroarea acceptată pentru o precizie de 5 zecimale şi are valoarea 0.00001. Nu uitaţi că calculele cu float şi double nu sunt foarte precise, de aceea trebuie să luăm în considerare o marjă de eroare.
#include <iostream>
using namespace std;

// Functia f
double f(double x) 
{
    return 3*x + 3;
}

double sigma = 0.00001;

// Metoda bisectiei
double getRoot(double a, double b)
{
    double c;
    if(b-a < sigma) return (a+b) / 2.0; // S-a gasit radacina, o returnez
    else
    {
        c = (a+b) / 2.0; 
        if(f(a) * f(c) < 0) return getRoot(a, c);
        else return getRoot(c, b);
    }
}

int main()
{
    // Se va afisa -0.999999 care este foarte aproape de -1
    cout << getRoot(-10, 10);
    system("PAUSE");
    return 0;
}

vineri, 9 martie 2012

Algoritmi: Căutarea Binară

Căutarea binară (Binary Search) este un algoritm care caută poziţia unei valori într-o colecţie de date, sau vector, sortată. La fiecare pas, algoritmul compară valoarea căutată cu valoarea din mijlocul vectorului. Dacă se potrivesc atunci indicele sau poziţia valorii în vector este returnată. În caz contrar se caută în subvectorul din stânga valorii din mijloc, dacă valoarea căutată este mai mică decât cea din mijloc, sau în subvectorul din dreapta, dacă este mai mare. Algoritmul repetă aceiaşi paşi pentru fiecare subvector. Dacă nu se găseşte valoarea se va returna valoarea -1.
Complexitatea algoritmului este \(O(\log{n})\) (logaritmic) deoarece la fiecare pas vectorul este înjumătăţit.

Implementare în C++

// *** Binary Search *** //
// d (dreapta) - limita inferioara 
// s (stanga) - limita superioara
int cauta(int d, int s, int key, int * v)
{
    if(s < d) return -1; // Nu s-a gasit nicio valoare
    int m = (d + s) / 2; // Elementul din mijloc
    if(key < v[m]) return cauta(d, m-1, key, v); // Cauta in subvectorul din stanga
    else if(key > v[m]) return cauta(m+1, s, key, v); // Cauta in subvectorul din dreapta
    else return m; // Gasit!
}
Exemplu:
#include <iostream>
using namespace std;

// *** Binary Search *** //
// d (dreapta) - limita inferioara 
// s (stanga) - limita superioara
int cauta(int d, int s, int key, int * v)
{
    if(s < d) return -1; // Nu s-a gasit nicio valoare
    int m = (d + s) / 2; // Elementul din mijloc
    if(key < v[m]) return cauta(d, m-1, key, v); // Cauta in subvectorul din stanga
    else if(key > v[m]) return cauta(m+1, s, key, v); // Cauta in subvectorul din dreapta
    else return m; // Gasit!
}

int main()
{
    int iteme[] = {2, 9, 11, 15, 28, 33, 40, 47, 51, 64, 76, 77, 82, 85, 94}; // 15 elemente
    int indice = cauta(0, 14, 76, iteme);
    cout << indice; // 10; iteme[10] == 76;
    
    system("PAUSE");
    return 0;
}

luni, 20 februarie 2012

[Tutorial] Cheat Engine [Minesweeper] #1

Intraţi pe acest site şi descărcaţi Cheat Engine (Versiunea curentă în acest moment este 6.1).
Instalaţi şi porniţi Cheat Engine.
Deschideţi Minesweeper.

În Cheat Engine, click pe iconul Select a process to open (se află sub meniul file; vezi imaginea de sus) şi selectaţi procesul jocului Minesweeper. Click Open.

Porniţi Minesweeper. Click pe unul din pătrăţele. Cronometrul va porni.
În Cheat Engine, la Value Type selectaţi Float, apoi sub Value scrieţi 25.

Când cronometrul din Minesweeper ajunge la 25, click pe First Scan. Ar trebui să obţineţi ceva similar cu aceasta:

Acum scrieţi 34 sau 55 sau orice şi când cronometrul ajunge la respectiva valoare click pe Next Scan. Dacă aţi urmat paşii întocmai, veţi obţine adresa valorii cronometrului în lista adreselor găsite şi veţi vedea că valoarea se schimbă o dată cu valoarea din Minesweeper.

Dublu-click pe adresa valorii cronometrului găsită. Va fi adăugată în lista de adrese de mai jos.

Dublu-click pe valoarea de sub Value şi o fereastă cu un textbox va apărea cerându-vă noua valoare care va fi memorată la această adresă. Introduceţi ceva foarte mic: -9999999. Click OK.


Asta este tot! Tocmai aţi hack-uit un joc.

miercuri, 25 ianuarie 2012

Coada (Queue)

Coada (Queue) este un container (la fel ca şi Stiva) bazat pe principiul first-in first-out (FIFO). Adică elementele pot fi adăugate în coadă în orice moment, dar numai cel mai vechi (cel de la bază) element poate fi eliminat în orice moment (se extrage cea mai veche informaţie adăugată). Mai simplu, elementele sunt adăugate în spate şi eliminate din faţă. Intraţi pe http://courses.cs.vt.edu/csonline/DataStructures/Lessons/QueuesImplementationView/applet.html sau http://www.concentric.net/~ttwang/java/QueueDemo.html (aveţi nevoie de Java) pentru a înţelege mai bine. Folosiţi Enqueue pentru a adăuga obiecte şi Dequeue pentru a elimina obiectul din faţă (front). Acum că aveţi o idee despre cozi, să trecem la operaţiile pe care coada le implementează. Coada este o structură de date care suportă următoarele operaţii:
  • enqueue(ob): adaugă un obiect la sârşitul cozii (baza).
  • dequeue(): elimină obiectul din faţa cozii (cap).
  • front(): returnează o referinţă către cap fără a elimina obiectul.
  • back(): returnează o referinţă către baza fără a elimina obiectul.
  • size(): returnează numărul obiectelor din coadă.
  • isEmpty(): returnează true dacă coada este vidă, altfel false.
Deoarece am zis că coada este un container de obiecte, acest lucru înseamnă că ar trebui să pot declara cozi de orice tip: int, char, bool, etc. sau un tip definit de utilizator. Deci voi implementa o clasă generică Coada, cu parametrul generic T.
template<typename T>
class Coada
{
public:
    Coada(); // Constructor
    ~Coada(); // Destructor
    void enqueue(const T& ob); // Adaug un element in coada
    void dequeue(); // Elimin obiectul din fata
    const T& front() const; // Returnez o referinta catre cap
    const T& back() const; // Returnez o referinta catre baza
    int size() const; // Returnez numarul de elemente
    bool isEmpty() const; // Este coada vida?
private:
    struct Element
    {
        T data;
        Element * next;
    };
    Element * cap;
    Element * baza;
    int count; // Numar elementele
};

Observaţi că la unele funcţii apare referinţa constantă. De ce fac asta? De ce nu returnez pur şi simplu un obiect T şi nu o referinţă? Datorită eficienţei. Atunci când returnez o referinţă nu se mai alocă, temporar (deci va fi dealocat; un overhead suplimentar), spaţiu pentru obiectul returnat sau pentru parametrul formal, deoarece pot accesa direct variabila referită. Referinţa este constantă tocmai pentru că nu vreau să modific din greşeală argumentul sau obiectul returnat, plus că nu aş putea transmite valori concrete (de ex: 1, 2, 'c', 4.6, etc.) funcţiei enqueue(), dacă referinţa nu ar fi constantă.

Iniţializarea Cozii

Iniţializarea cozii presupune crearea cozii vide, adică elementele cap şi baza indică NULL (nullptr). Pentru cei care folosiţi compilatoare noi, cum ar fi cel din Visual Studio, folosiţi nullptr în loc de NULL, deoarece NULL este doar un simplu macro, este 0, este un întreg şi nu reprezintă concret o adresă inexistentă. Coada este iniţializată în constructor:
template<typename T> Coada<T>::Coada()
{
    cap = baza = nullptr; // coada vida
    count = 0; // niciun element
}

Coada Vidă

Coada este vidă atunci când cap este NULL, deci algoritmul va fi următorul:
template<typename T> bool Coada<T>::isEmpty() const
{
    return cap == nullptr;
}

Calificatorul const informează compilatorul că respectiva funcţie nu modifcă obiectele stivei, nu le modifica datele membre.

Numărul de elemente dintr-o Coadă

Pur şi simplu returnăm valoarea membrului count.
template<typename T> int Coada<T>::size() const
{
    return count;
}

Adăugarea unui element în Coadă

Algoritmul este simplu. Aloc memorie pentru un obiect de tip Element -> Scriu informaţia în obiect -> Succesorul acestui obiect este baza -> Noul element devine baza. Se incrementează count. Funcţia enqueue() va implementa această operaţie.
template<typename T> void Coada<T>::enqueue(const T& ob)
{
    if(isEmpty()) // Daca coada este vida
    {
        cap = new Element;
        cap->data = ob;
        cap->next = nullptr; // Fiind singurul element, succesorul este NULL
        baza = cap;
        count = 1;
    }
    else
    {
        Element * p = new Element;
        p->data = ob;
        p->next = nullptr; // Devine noul element baza
        baza->next = p; // Fosta baza se leaga de noua baza
        baza = p; // p devine baza
        ++count;  // S-a mai adaugat un element
    }
}

Eliminarea unui element din Coadă

Se poate elimina numai elementul din faţă. Se salvează adresa capului -> Elementul următor devine cap -> Se eliberează memoria fostului cap. Se decrementează count. Funcţia dequeue() va implementa această operaţie.
template<typename T> void Coada<T>::dequeue()
{
    if(isEmpty()) throw "Eroare! Coada Vida!";
    Element * q = cap; // Salvez elementul din cap
    cap = cap->next; // Elementul urmator devine cap
    delete q;
    --count;
}

Obţinerea elementului din capul Cozii

Se returnează o referinţă constantă către cap->data.
template<typename T> const T& Coada<T>::front() const
{
    if(isEmpty()) throw "Eroare! Coada Vida!";
    return cap->data;
}

Obţinerea elementului din baza Cozii

Se returnează o referinţă constantă către baza->data.
template<typename T> const T& Coada<T>::back() const
{
    if(isEmpty()) throw "Eroare! Coada Vida!";
    return baza->data;
}

Eliberarea spaţiului de memorie ocupat de Coadă

Se distruge pe rând fiecare element al cozii. De asta se va ocupa destructorul clasei.
template<typename T> Coada<T>::~Coada()
{
    while(cap != nullptr)
    {
        Element * q = cap;
        cap = cap->next;
        delete q;
    }
}

Dacă aveţi probleme cu nullptr, atunci folosiţi NULL. De asemenea vă recomand să folosiţi Visual Studio.
În continuare vă propun să creaţi un nou fişier Coada.h (header) şi să-l adăugaţi la proiectul vostru, după care în fişierul main (unde aveţi funcţia main) să adăugaţi, la început, directiva: #include "Coada.h". Adăugaţi următorul cod în Coada.h:

template<typename T>
class Coada
{
public:
    Coada() { // Constructor
        cap = baza = nullptr; // coada vida
        count = 0; // niciun element
    }
    ~Coada(); // Destructor
    void enqueue(const T& ob); // Adaug un element in coada
    void dequeue(); // Elimin obiectul din fata
    const T& front() const { // Returnez o referinta catre cap
        if(isEmpty()) throw "Eroare! Coada Vida!";
        return cap->data;
    }
    const T& back() const { // Returnez o referinta catre baza
        if(isEmpty()) throw "Eroare! Coada Vida!";
        return baza->data;
    }
    int size() const { return count; } // Returnez numarul de elemente
    bool isEmpty() const { return cap == nullptr; } // Este coada vida?
private:
    struct Element
    {
        T data;
        Element * next;
    };
    Element * cap;
    Element * baza;
    int count; // Numar elementele
};

template<typename T> Coada<T>::~Coada()
{
    while(cap != nullptr)
    {
        Element * q = cap;
        cap = cap->next;
        delete q;
    }
}

template<typename T> void Coada<T>::enqueue(const T& ob)
{
    if(isEmpty()) // Daca coada este vida
    {
        cap = new Element;
        cap->data = ob;
        cap->next = nullptr; // Fiind singurul element, succesorul este NULL
        baza = cap;
        count = 1;
    }
    else
    {
        Element * p = new Element;
        p->data = ob;
        p->next = nullptr; // Devine noul element baza
        baza->next = p; // Fosta baza se leaga de noua baza
        baza = p; // p devine baza
        ++count;  // S-a mai adaugat un element
    }
}

template<typename T> void Coada<T>::dequeue()
{
    if(isEmpty()) throw "Eroare! Coada Vida!";
    Element * q = cap; // Salvez elementul din cap
    cap = cap->next; // Elementul urmator devine cap
    delete q;
    --count;
}

PROBLEMĂ: Într-o coadă sunt memorate numere din intervalul \([1, 10]\). Să se elimine numerele pare.
Deoarece numai informaţia din cap poate fi extrasă, pentru a ajunge la un anumit element trebuie eliminate toate elementele până la acel element. În acest caz, pentru a nu pierde informaţia din celelalte elemente (aici, numerele impare), voi descărca elementele impare într-o coadă de rezervă (temp), iar după ce voi scăpa de numerele pare, voi încărca numerele impare din coada de rezervă înapoi în coada iniţială.

#include <iostream>
#include "Coada.h"
using namespace std;

int main()
{
    Coada<int> qu, temp; 

    for(int i = 1; i <= 10; i++) // Adaug 10 numere [1, 10]
        qu.enqueue(i);

    while(!qu.isEmpty()) // Cat timp coada nu este vida
    {
        if(qu.front() % 2 == 0)
            qu.dequeue(); // Daca este par, il elimin
        else
        {
            temp.enqueue(qu.front()); // Salvez numarul impar
            qu.dequeue();
        }
    }

    // Incarc numerele impare inapoi in coada qu
    while(!temp.isEmpty())
    {
        qu.enqueue(temp.front());
        temp.dequeue();
    }

    // Afisez rezultatul
    while (!qu.isEmpty())
    {
        cout << qu.front() << ' ';
        qu.dequeue();
    }

    system("PAUSE");
    return 0;
}
Output:
1 3 5 7 9

Trebuie să ştiţi că Standard Template Library (STL) implementează o structură de tip coadă în clasa queue, ce se găseşte în headerul queue. Are aceeiaşi membri (isEmpty() este empty(), enqueue() este push(), dequeue() este pop()) ca şi clasa definită de mine, singura diferenţa fiind că operaţiile front(), back() şi pop() pentru o coadă vidă sunt nedefinite, adică nu se generează o excepţie (aşa cum am făcut eu). Deci este responsabilitatea programatorului pentru a se asigura că nu aplică acele operaţii pe o coadă vidă.

#include <queue>
using std::queue; 
queue<float> myQueue;

Stiva (Stack)

Stiva (Stack) este un container (sau colecţie) de obiecte bazat pe principiul last-in-first-out (LIFO). Adică obiectele (numere, caractere, etc.) pot fi adăugate în stivă în orice moment, dar numai cel mai recent (cel din vârf) poate fi eliminat în orice moment. Imaginaţi-vă stiva ca un turn de obiecte, cel mai recent adăugat aflându-se în vârf, iar cel mai vechi la bază. Intraţi pe http://www.cosc.canterbury.ac.nz/mukundan/dsal/StackAppl.html (aveţi nevoie de Java) sau http://acc6.its.brooklyn.cuny.edu/~cis22/animations/tsang/html/STACK/stack640.html pentru a înţelege mai bine. Folosiţi Push pentru a adăuga obiecte şi Pop pentru a elimina obiectul din vârf (top), iar butonul Top afişează valoarea vârfului. Stivele sunt folosite în multe aplicaţii cum ar fi: browser-ele web care memorează adresele site-urilor recent vizitate, opţiunea undo din editoarele de text, ş.a. Acum că aveţi o idee despre stive, să trecem la operaţiile pe care stiva le implementează. Stiva este o structură de date care suportă următoarele operaţii:
  • push(ob): adaugă un obiect în vârful stivei.
  • pop(): elimină obiectul din vârful stivei.
  • top(): returnează o referinţă către vârful stivei fără a elimina obiectul.
  • size(): returnează numărul obiectelor din stivă.
  • isEmpty(): returnează true dacă stiva este vidă, altfel false.
Deoarece am zis că stiva este un container de obiecte, acest lucru înseamnă că ar trebui să pot declara stive de orice tip: int, char, bool, etc. sau un tip definit de utilizator. Să definesc câte o stivă pentru fiecare tip ar însemna să fiu nebun, de aceea voi implementa o clasă generică Stiva, cu parametrul generic T.
template<typename T>
class Stiva
{
public:
    Stiva(); // Constructor | Initializarea stivei
    ~Stiva(); // Destructor
    int size() const; // Returneaza numarul elementelor din stiva
    bool isEmpty() const; // Este stiva vida?
    const T& top() const; // Returneaza o referinta constanta catre varf
    void push(const T& ob); // Adauga un element
    void pop(); // Elimina elementul din varf
private:
    struct Element // Implementeaza un element de stiva
    {
        T data; // Informatia memorata in elementul stivei
        Element * below; // Elementul anterior / dedesubt
    };
    Element * varf; // Varful stivei
    int count; // Data membra cu care numar elementele stivei
};

Observaţi că la unele funcţii apare referinţa constantă. De ce fac asta? De ce nu returnez pur şi simplu un obiect T şi nu o referinţă? Datorită eficienţei. Atunci când returnez o referinţă nu se mai alocă, temporar (deci va fi dealocat; un overhead suplimentar), spaţiu pentru obiectul returnat sau pentru parametrul formal, deoarece pot accesa direct variabila referită. Referinţa este constantă tocmai pentru că nu vreau să modific din greşeală argumentul sau obiectul returnat, plus că nu aş putea transmite valori concrete (de ex: 1, 2, 'c', 4.6, etc.) funcţiei push(), dacă referinţa nu ar fi constantă.

Iniţializarea Stivei

Iniţializarea stivei presupune crearea stivei vide, adică elementul varf indică NULL (nullptr). Pentru cei care folosiţi compilatoare noi, cum ar fi cel din Visual Studio, folosiţi nullptr în loc de NULL, deoarece NULL este doar un simplu macro, este 0, este un întreg şi nu reprezintă concret o adresă inexistentă. Stiva este iniţializată în constructor:
template<typename T> Stiva<T>::Stiva()
{
    varf = nullptr; // stiva vida
    count = 0; // zero elemente
}

Stiva Vidă

Stiva este vidă atunci când varf este NULL, deci algoritmul va fi următorul:
template<typename T> bool Stiva<T>::isEmpty() const
{
    return varf == nullptr;
}

Calificatorul const informează compilatorul că respectiva funcţie nu modifcă obiectele stivei, nu le modifica datele membre.

Numărul de elemente dintr-o Stivă

Pur şi simplu returnăm valoarea membrului count.
template<typename T> int Stiva<T>::size() const
{
    return count;
}

Adăugarea unui element în Stivă

Algoritmul este simplu. Aloc memorie pentru un obiect de tip Element -> Scriu informaţia în obiect -> Predecesorul acestui obiect este varf -> Noul element devine varf. Se incrementează count. Funcţia push() va implementa această operaţie.
template<typename T> void Stiva<T>::push(const T& ob)
{
    if(isEmpty()) // Daca stiva este vida
    {
        varf = new Element;
        varf->data = ob;
        varf->below = nullptr; // Este baza! Primul element adaugat
        count = 1; 
    }
    else
    {
        Element * p = new Element;
        p->data = ob;
        p->below = varf; // Dedesubt se afla fostul varf
        varf = p; // p devine noul varf
        ++count;  // S-a mai adaugat un element
    }
}

Eliminarea unui element din Stivă

Se poate elimina numai elementul din vârf. Se salvează adresa vârfului -> Elementul dedesubt devine vârf -> Se eliberează memoria fostului vârf. Se decrementează count. Funcţia pop() va implementa această operaţie.
template<typename T> void Stiva<T>::pop()
{
    // Daca stiva este vida, genereaza o exceptie
    if(isEmpty()) throw "Eroare! Stiva Vida!";
    Element * q = varf; // Salvez varful
    varf = varf->below; // Elementul anterior devine noul varf
    delete q;
    --count; // S-a mai eliminat un element
}

Obţinerea elementului din vârful Stivei

Se returnează o referinţă constantă către varf->data.
template<typename T> const T& Stiva<T>::top() const
{
    if(isEmpty()) throw "Eroare! Stiva Vida!";
    return varf->data;
}

Eliberarea spaţiului de memorie ocupat de Stivă

Se distruge pe rând fiecare element al stivei. De asta se va ocupa destructorul clasei.
template<typename T> Stiva<T>::~Stiva()
{
    while(varf != nullptr)
    {
        Element * q = varf;
        varf = varf->below;
        delete q;
    }
}

Dacă aveţi probleme cu nullptr, atunci folosiţi NULL. De asemenea vă recomand să folosiţi Visual Studio.
În continuare vă propun să creaţi un nou fişier Stiva.h (header) şi să-l adăugaţi la proiectul vostru, după care în fişierul main (unde aveţi funcţia main) să adăugaţi, la început, directiva: #include "Stiva.h". Adăugaţi următorul cod în Stiva.h:

template<typename T>
class Stiva
{
public:
    // Constructor | Initializarea stivei
    Stiva() {
        varf = nullptr; // stiva vida
        count = 0; // zero elemente
    }
    ~Stiva(); // Destructor
    int size() const { return count; } // Returneaza numarul elementelor din stiva
    bool isEmpty() const { return varf == nullptr; } // Este stiva vida?
    const T& top() const { // Returneaza o referinta constanta catre varf
        if(isEmpty()) throw "Eroare! Stiva Vida!"; 
        return varf->data; 
    } 
    void push(const T& ob); // Adauga un element
    void pop(); // Elimina elementul din varf
private:
    struct Element // Implementeaza un element de stiva
    {
        T data; // Informatia memorata in elementul stivei
        Element * below; // Elementul anterior / dedesubt
    };
    Element * varf; // Varful stivei
    int count; // Data membra cu care numar elementele stivei
};

template<typename T> void Stiva<T>::push(const T& ob)
{
    if(isEmpty()) // Daca stiva este vida
    {
        varf = new Element;
        varf->data = ob;
        varf->below = nullptr; // Este baza! Primul element adaugat
        count = 1; 
    }
    else
    {
        Element * p = new Element;
        p->data = ob;
        p->below = varf; // Dedesubt se afla fostul varf
        varf = p; // p devine noul varf
        ++count;  // S-a mai adaugat un element
    }
}

template<typename T> void Stiva<T>::pop()
{
    // Daca stiva este vida, genereaza o exceptie
    if(isEmpty()) throw "Eroare! Stiva Vida!";
    Element * q = varf; // Salvez varful
    varf = varf->below; // Elementul anterior devine noul varf
    delete q;
    --count; // S-a mai eliminat un element
}

template<typename T> Stiva<T>::~Stiva()
{
    while(varf != nullptr)
    {
        Element * q = varf;
        varf = varf->below;
        delete q;
    }
}

PROBLEMĂ: Într-o stivă sunt memorate numere din intervalul \([1, 10]\). Să se elimine numerele pare.
Deoarece numai informaţia din vârf poate fi prelucrată, pentru a ajunge la un anumit element trebuie eliminate toate elementele până la acel element. În acest caz, pentru a nu pierde informaţia din celelalte elemente (aici, numerele impare), voi descărca elementele impare într-o stivă de rezervă (temp), iar după ce voi scăpa de numerele pare, voi încărca numerele impare din stiva de rezervă înapoi în stiva iniţială.

#include <iostream>
#include "Stiva.h"
using namespace std;

int main()
{
    Stiva<int> st; // Voi memora intregi | int
    Stiva<int> temp; // Stiva de rezerva in care voi memora numerele impare
 
    for(int i = 1; i <= 10; i++)
    st.push(i); // Adaug cele zece numere

    while(!st.isEmpty()) // Cat timp stiva nu este vida
    {
        if(st.top() % 2 == 0)
        st.pop(); // Daca este par, il elimin
        else
        {
            temp.push(st.top()); // Salvez numarul impar
            st.pop();
        }
    }

    // Acum incarc numerele impare inapoi in stiva st
    while(!temp.isEmpty())
    {
        st.push(temp.top());
        temp.pop();
    }

    // Acum afisez stiva st
    while(!st.isEmpty())
    {
        cout << st.top() << '\n';
        st.pop();
    }

    system("PAUSE");
    return 0;
}
Output:
9
7
5
3
1

Trebuie să ştiţi că Standard Template Library (STL) implementează o structură de tip stivă în clasa stack, ce se găseşte în headerul stack. Are aceeiaşi membri (isEmpty() este empty()) ca şi clasa definită de mine, singura diferenţa fiind că operaţiile top() şi pop() pentru o stivă vidă sunt nedefinite, adică nu se generează o excepţie (aşa cum am făcut eu). Deci este responsabilitatea programatorului pentru a se asigura că nu aplică acele operaţii pe o stivă vidă.

#include <stack>
using std::stack; 
stack<int> myStack;