STRUCTURI DE DATE (Note de curs) 2024 PDF

Ana-Maria MOŞNEAGU STRUCTURI DE DATE Note de curs 2024 Cuprins Introducere 2 1 Alocarea dinamică a...

Ana-Maria MOŞNEAGU STRUCTURI DE DATE Note de curs 2024 Cuprins Introducere 2 1 Alocarea dinamică a memoriei. Tipuri specifice 4 1.1 Operatorul adresă (”&”).......................................... 4 1.2 Pointeri................................................... 5 1.2.1 Declararea pointerilor....................................... 5 1.2.2 Iniţializarea pointerilor....................................... 6 1.2.3 Operatorul ţintă (”*”)....................................... 7 1.2.4 Pointeri către tipuri definite de utilizator............................ 8 1.2.5 Aritmetica pointerilor....................................... 8 1.2.6 Pointeri şi modificatorul const.................................. 9 1.2.7 Pointeri şi tablouri......................................... 9 1.3 Referinţe.................................................. 13 1.3.1 Declararea şi iniţializarea referinţelor............................... 13 1.4 Pointeri, referinţe şi funcţii........................................ 14 1.4.1 Apelul funcţiilor.......................................... 14 1.4.2 Pointeri şi funcţii.......................................... 15 1.4.3 Referinţe şi funcţii......................................... 17 1.5 Alocarea dinamică a memoriei....................................... 18 2 Tablouri 23 2.1 Tablouri unidimensionale......................................... 23 2.2 Tablouri bidimensionale.......................................... 29 3 Liste 35 3.1 Liste liniare simplu ı̂nlănţuite....................................... 36 3.1.1 Cazuri particulare: stiva şi coada................................. 36 3.1.2 Cazul general............................................ 41 3.2 Liste liniare dublu ı̂nlănţuite....................................... 48 3.3 Liste circulare simplu ı̂nlănţuite...................................... 58 3.4 Liste circulare dublu ı̂nlănţuite...................................... 64 Bibliografie 71 1 Introducere În informatică, datele reprezintă modalităţi de a reprezenta ı̂n memoria calculatorului sau pe suport extern a informaţiilor furnizate de problema propusă spre rezolvare. După modul ı̂n care sunt organizate, datele se ı̂mpart ı̂n: ˆ date elementare, simple, indivizibile, cum sunt datele numerice sau pointerii; ˆ date structurate, grupate, compuse, cum sunt tablourile, listele sau fişierele. Gruparea unor date sub un singur nume a fost necesară ı̂ncă de la ı̂nceputurile programării calculatoarelor, pentru a facilita prelucrarea acestora (de exemplu, pentru a se realiza sortări sau căutări ı̂n colecţii de date). Studiul structurilor de date se ocupă cu definirea acestora (stabilirea elementelor constituene, legăturilor dintre acestea şi a operaţiilor posibile), cu identificarea modalităţilor de reprezentare ı̂n memoria calculatorului a datelor şi apoi de accesare a acestora ı̂n scopul prelucrărilor ulterioare. Scopul este ca datele să fie utilizate ı̂ntr-un mod cât mai eficient. Clasificarea structurilor de date are la bază mai multe criterii. Datele structurate sau structurile de date conţin mai multe date de acelaşi tip sau de tipuri diferite, grupate sub un singur nume. Aşadar, o structură de date poate fi: ˆ omogenă, dacă toate elementele componenete au acelaşi tip (tablouri); ˆ neomogenă, dacă elementele componenete ale structurii pot avea tipuri diferite (structuri, ı̂nregistrări). O structură de date poate fi privită: ˆ din punctul de vedere al definiţiei formale a acesteia, atunci când elementele posibile, legăturile dintre acestea şi operaţiile posibile sunt specificate fără detalii de reprezentare/implementare (structură logică); ˆ din punctul de vedere al stocării acesteia ı̂n memorie (structură fizică). După numărul elementelor unei structuri de date, aceasta poate fi: ˆ statică, atunci când numărul de componente este fixat la compilare; ˆ dinamică, dacă numărul de componente este variabil, dar cunoscut ı̂n momentul execuţiei programului. Această clasificare se referă strict la modul de implementare a structurii de date. Să observăm că o structură de date logică ar putea fi implementată atât ca structură statică, cât şi ca structură dinamică (stive, cozi etc.). Dar clasificarea unei structuri ı̂n statică/dinamică, poate fi făcută şi la nivel logic, când o considerăm a fi: ˆ statică, dacă nu permite actualizări de tip adăugări/ştergeri de elemente; ˆ dinamică, altfel. După modul de reprezentare a relaţiilor dintre elementele sale, o structură de date poate fi: ˆ explicită, dacă pe lângă componentele structurii se memorează şi alte date suplimentare prin care se specifică relaţia de ordine a componentelor; ˆ implicită, ı̂n caz contrar. De exemplu, structura de date de tip tablou este o structură implicită de date, iar structura de date de tip listă este o structură explicită de date. 2 Structuri de date Note de curs După modul cum se realizează accesul la elementele unei structuri, aceasta poate fi: ˆ cu acces direct, dacă accesul la o anumită componentă a acesteia se poate face fără a ţine seama de celelalte componente (tablouri); ˆ cu acces secvenţial, când accesul la o componentă a structurii de date se poate face numai ţinând cont de alte câmpuri ale structurii, printr-un proces de parcurgere a elementelor componente (liste). Dacă luăm ı̂n calcul relaţiile existente ı̂ntre elementele unei structuri de date, aceasta poate fi: ˆ liniară, dacă fiecare element poate să aibă cel mult un succesor şi cel mult un predecesor (tablouri, liste liniare); ˆ neliniară, dacă un element poate avea mai mulţi succesori şi mai multi predecesori (grafuri) sau un element poate avea mai mulţi succesori, dar un singur predecesor (arbori). Operaţiile standard ce se pot efectua asupra unei structuri de date sunt: ˆ crearea structurii de date; ˆ consultarea/interogarea structurii de date, ce constă ı̂n accesarea elementelor structurii ı̂n vederea prelucrării acestora – parcurgere, căutare, sortare etc.; ˆ actualizarea structurii de date, ce constă ı̂n adăugarea de noi elemente, eliminarea unor elemente care nu mai sunt necesare sau modificarea valorilor unor componente ale structurii. Sunt posibile şi alte operaţii pe structurile de date, ce depind de specificul acestora (de exemplu, interclasarea, concatenarea sau copierea). Atunci când ne propunem să rezolvăm o problemă concretă, ı̂n etapa de proiectare vom stabili structurile de date logice (abstracte) cele mai potrivite ı̂n funcţie de specificul aplicaţiei şi, de asemenea, algoritmii de prelucrare a acestora. Apoi, etapa de implementare presupune precizarea modalităţilor adecvate de reprezentare ı̂n memorie a structurilor de date alese, scrierea de cod, eventual utilizarea unor anumite funcţii specifice limbajului de pro- gramare folosit. Aşadar, prima etapă, cea de proiectare, ar trebui să fie independentă de limbajul de programare utilizat. Alegerea corectă a unei structuri de date sporeşte eficienţa algoritmilor utilizaţi, prin reducerea memoriei ocupate şi a timpului de execuţie. Structurile de date de interes pentru acest curs sunt: tablourile, listele, grafurile, arborii şi tabelele de dispersie. 3  Capitolul 1 Alocarea dinamică a memoriei. Tipuri specifice 1.1 Operatorul adresă (”&”) Orice program operează cu date. Acestea sunt stocate ı̂n memoria RAM a calculatorului s, i pot fi constante (date care nu ı̂şi modifică valoarea pe parcursul execuţiei programului) sau variabile (date care ı̂şi pot modifica valoarea pe parcursul execuţiei programului). Memoria RAM a calculatorului este constituită din locat, ii de memorie, fiecare dintre acestea ocupând un octet (byte) s, i având atribuită o adresă unică. Astfel, fiecare locat, ie de memorie are asociat un număr de ordine, ı̂ncepând cu 0, ce reprezintă adresa acelui byte (implicit, aceasta este afis, ată ı̂n baza 16). Din acest motiv spunem că memoria RAM este adresată. Orice variabilă/constantă este caracterizată prin: ˆ nume (identificator); ˆ tip de date (indică valorile posibile pentru variabilă precum s, i operat, iile permise cu aceasta); ˆ adresă de memorie (adresa de ı̂nceput a zonei de memorie unde este stocată variabila); ˆ domeniul de vizibilitate (zona din program ı̂n care variabila există s, i poate fi utilizată – variabile globale sau locale). În C/C++, este obligatoriu ca variabilele să fie declarate, precizând tipul s, i numele lor. Astfel, orice dată elementară sau structurată declarată (sau alte obiecte declarate, cum sunt funcţiile) va ocupa o zonă de memorie formată din una sau mai multe locaţii de memorie ı̂n funcţie de tipul acesteia şi de compilator. Adresa unui obiect este adresa de ı̂nceput a zonei de memorie alocată obiectului de compilator (alocare statică) sau de programator (alocare dinamică), adică adresa primului octet al acestei zone. Operatorul unar adresă (”&”), numit şi operator de referenţiere, ı̂ntoarce adresa operandului său. Operandul operatorului adresă trebuie să fie un obiect declarat. În exemplul de mai jos, i este o variabilă de tip int, căreia, i s-a alocat de către compilator un spaţiu de memorie capabil să memoreze o dată de acest tip. Să presupunem că adresa de ı̂nceput a zonei alocate este 2005 (ı̂n sistem zecimal) şi că tipul int este reprezentat pe 4 octeţi. Expresia &i va returna adresa primului octet al zonei alocate. 1 int i ; 2 cout < < " Adresa lui i , & i : " < ” şi operatorul de indexare ”[ ]” au nivelul de prioritate mai ı̂nalt decât operatorul unar ”*”. Astfel, un pointer către un tablou de 10 ı̂ntregi, deci către tipul int, se va declara corect astfel: 1 int (* p ) ; iar declararea unui tablou de 10 pointeri către tipul int se realizează prin sintaxa 1 int * p ; Declarăm un pointer cu numele p către tipul oarecare , predefinit sau definit de utilizator: 1 * p ; Pentru că un pointer este o variabilă şi deci i se alocă un spaţiu de memorie ı̂n momentul ı̂n care compilatorul ı̂ntâlneşte declaraţia sa, adresa de ı̂nceput a acestei zone de memorie poate fi reţinută ı̂ntr-un alt pointer. În această situaţie, vom declara un pointer ”dublu” prin sintaxa: 1 ** nume_pointer ; unde * este tipul ţintei, adică a pointerului a cărui adresă este reţinută de pointerul dublu. Continuând accelaşi raţionament, poineterului dublu i se alocă o zonă de memorie de către compilator, deci adresa sa poate fi stocată ı̂ntr-un pointer ”triplu”, declarat astfel: 1 *** nume_pointer ; 1.2.2 Iniţializarea pointerilor După ce au fost declaraţi, pointerii nu pot fi utilizaţi fără a fi iniţializaţi (la fel ca oricare altă variabilă). Utilizarea unui pointer declarat, dar neiniţializat conduce la erori de compilare. Iniţializarea unui pointer se poate face prin una dintre următoarele trei metode: 1. prin atribuirea adresei unei variabile deja definite. De exemplu, dacă x este o variabilă de tip int, adresa sa o vom memora ı̂ntr-un pointer către int: 1 int x ; 2 int * px ; 3 px = & x ; // sau int * px = & x ; 4 x = 5; 5 cout < < " Valoarea lui x : " next ) 79 cout < elem.i < < " " elem. valoare ; 96 a da ug ar e Sf ar si t ( vt , st , elemN ) ; 97 p = p - > next ; 98 } 99 } 100 101 // concataenarea a doua liste 102 void c o n c a t e n a r e L i s t e ( LISTA v1 , LISTA v2 , LISTA & vsum , LISTA & ssum ) 103 { 104 vsum = nullptr ; 105 ssum = nullptr ; 106 LISTA q ; 107 for ( q = v1 ; q != nullptr ; q = q - > next ) 108 a da ug ar e Sf ar si t ( vsum , ssum , q - > elem ) ; 109 for ( q = v2 ; q != nullptr ; q = q - > next ) 110 a da ug ar e Sf ar si t ( vsum , ssum , q - > elem ) ; 111 } 112 113 114 void actualizare ( LISTA vf ) 115 { 116 LISTA p , q ; 117 for ( p = vf ; p != nullptr ; p = p - > next ) 118 for ( q = p - > next ; q != nullptr ; q = q - > next ) 119 if (p - > elem. i == q - > elem. i && p - > elem. j == q - > elem. j ) 120 { 121 p - > elem. valoare = p - > elem. valoare + q - > elem. valoare ; 122 q - > elem. valoare = 0; 123 } 124 } 125 126 // sterge din lista toate nodurile de valoare nula 127 void stergereNod ( LISTA & vf , LISTA & sf ) 128 { 129 LISTA q , r ; 130 if ( vf == nullptr ) 131 { 132 cout < < " Lista este vida ! " elem. valoare == 0) 137 { 138 q = vf ; 139 if ( q != sf ) 140 { 141 vf = vf - > next ; 142 vf - > back = nullptr ; 143 delete q ; 144 } 145 else 146 { 147 vf = nullptr ; 148 sf = nullptr ; 149 delete q ; 56  Structuri de date Note de curs 150 } 151 } 152 if ( vf != nullptr ) 153 { 154 q = vf ; 155 while (q - > next != nullptr ) 156 if (q - > next - > elem. valoare == 0) 157 { 158 r = q - > next ; // nodul de sters 159 // se leaga q de q - > next - > next 160 if ( r != sf ) 161 { 162 q - > next = r - > next ; 163 r - > next - > back = q ; 164 } 165 else 166 { 167 sf = sf - > back ; 168 sf - > next = nullptr ; 169 } 170 delete r ; 171 } 172 else q = q - > next ; 173 } 174 } 175 176 void stergereLista ( LISTA & vf , LISTA & sf ) 177 { } 178 179 int main () 180 181 { 182 int mA , nA , mB , nB ; 183 int nrElem ; 184 LISTA firstA , lastA , firstB , lastB , firstT , lastT ; 185 LISTA firstS , lastS ; 186 cout < < " Numar de linii ale matricei A : " ; 187 cin > > mA ; 188 cout < < " Numar de coloane ale matricei A : " ; 189 cin > > nA ; 190 cout < < " Numarul de elemente nenule ale matricei A : " ; 191 cin > > nrElem ; 192 firstA = creareSfarsit ( lastA , mA , nA , nrElem ) ; 193 cout < < " Numar de linii ale matricei B : " ; 194 cin > > mB ; 195 cout < < " Numar de coloane ale matricei B : " ; 196 cin > > nB ; 197 cout < < " Numarul de elemente nenule ale matricei A : " ; 198 cin > > nrElem ; 199 firstB = creareSfarsit ( lastB , mB , nB , nrElem ) ; 200 if ( firstA != nullptr ) 201 { 202 cout < < " Lista continand matricea rara A : " next ; 75 } while ( p != crt ) ; 76 } 77 return nullptr ; 78 } 79 80 void i ns er ar e In ai nt e ( LISTA & crt , int infoc , int infon ) 81 { 82 // inserarea unui nod nou , de informatie infon , inaintea nodului de informatie infoc 83 if ( crt == nullptr ) 84 { 85 cout < < " LISTA este vida ! " next ; 96 if (q - > info == infoc ) break ; 97 } while ( q != crt ) ; 60  Structuri de date Note de curs 98 // se insereaza nodul nou 99 if (q - > info == infoc ) 100 { 101 // se insereaza intre p si q 102 LISTA nou = new ( nothrow ) NOD ; 103 if ( nou == nullptr ) 104 error ( " Spatiu insuficient ! " ) ; 105 nou - > info = infon ; 106 nou - > next = q ; 107 p - > next = nou ; 108 if ( crt == p ) 109 crt = nou ; 110 } 111 else 112 cout < < " Informatia cautata " info == infoc ) 133 { 134 // se insereaza intre q si q - > next 135 LISTA nou = new ( nothrow ) NOD ; 136 if ( nou == nullptr ) 137 error ( " Spatiu insuficient ! " ) ; 138 nou - > info = infon ; 139 nou - > next = q - > next ; 140 q - > next = nou ; 141 if ( crt == q ) 142 crt = nou ; 143 } 144 else 145 cout < < " Informatia cautata " next = q - > next ; 172 if ( q == crt ) crt = p ; 173 } 174 delete q ; 175 } 176 else 177 cout < < " Informatia cautata " next ) crt = nullptr ; // lista devine vida 187 else 188 crt - > next = crt - > next - > next ; 189 delete p ; 190 } 191 } 192 193 LISTA copieLista ( LISTA crt ) 194 { 195 if ( crt == nullptr ) 196 { 197 cout < < " LISTA este vida ! " next ; 201 203 do 204 { 205 adaugare ( crt_copy , p - > info ) ; 206 p = p - > next ; 207 } while ( p != crt - > next ) ; 208 return crt_copy ; 209 } Exemplul 3.5. Simulăm următorului joc: un grup de n copii se aşează ı̂n cerc, fiind numerotaţi cu indicativele 1, 2,... , n, ı̂n sensul acelor de ceasornic. Începând cu o anumită poziţie, se numără copiii ı̂n sens orar. Jocul are două variante: a) Fiecare al n-lea copil este eliminat din cerc. b) Fiecare al m-lea copil spune un număr de la 1 la 10. Se continuă număratul, iar copilul cu numărul precizat iese din joc. Câştigătorul jocului este declarat ultimul copil rămas ı̂n joc. Se cere afişarea copilul câştigător pentru cele două variante de joc. Vom crea o lista circulară simplu ı̂nlănţuită ı̂n care vom plasa ı̂n zona de informaţie a nodurilor, numerele 1, 2,... , n, indicativele copiilor. 1 struct NOD 2 { 3 int info ; 4 NOD * next ; 5 }; 6 typedef NOD * LISTA ; 7 8 void error ( const char msg []) 9 { } 10 62  Structuri de date Note de curs 11 void adaugare ( LISTA & crt , int infon ) 12 { } 13 14 LISTA creareLista ( int & n ) 15 { 16 LISTA crt = nullptr ; 17 do 18 { 19 cout < < " Numarul de copii ( cel putin 2) : " ; 20 cin >>n ; 21 } while ( n < 2) ; 22 for ( int i = 1; i next ; 34 do 35 { 36 cout < info < < " " ; 37 p = p - > next ; 38 } while ( p != crt - > next ) ; 39 cout < < endl ; 40 } 41 else 42 cout < < " Lista este vida ! " > poz ; 58 } while ( poz n ) ; 59 LISTA p = nullptr , q = cautareNod ( crt , poz ) ; 60 int k = n ; 61 do 62 { 63 for ( int i = 1; i < n ; i ++) 64 { 65 p = q; 66 q = q - > next ; 67 } 68 // nodul de sters are adresa pastrata in q , iar precedentul , in p 69 cout < < " Copilul eliminat din joc este " next = q - > next ; // legatura noua 71 if ( q == crt ) crt = p ; 72 delete q ; // se sterge nodul spre care tinteste q 73 // afisareLista ( crt ) ; 74 // se trece la urmatorul copil de dupa cel sters 75 q = p - > next ; 76 k - -; // se decrementeaza numarul de copii 77 } while ( k > 1) ; 78 } 79 80 // a doua varianta a jocului 63  Structuri de date Note de curs 81 void joc2 ( LISTA & crt , int n , int & poz , int & m ) 82 { 83 int nr ; 84 do 85 { 86 cout < < " Pozitia de start : " ; 87 cin > > poz ; 88 } while ( poz n ) ; 89 do 90 { 91 cout < < " m : " ; 92 cin > > m ; 93 } while ( m < 2) ; 94 LISTA p = nullptr , q = cautareNod ( crt , poz ) ; 95 do 96 { 97 for ( int i = 1; i < m ; i ++) 98 { 99 p = q; 100 q = q - > next ; 101 } 102 cout < < " Copilul care trebuie sa spuna un numar de la 1 la 10 este " > nr ; 107 } while ( nr 10) ; 108 for ( int i = 1; i next ; 112 } 113 cout < < " Copilul eliminat din joc este " next = q - > next ; 115 if ( q == crt ) crt = p ; 116 delete q ; 117 // afisareLista ( crt ) ; 118 q = p - > next ; 119 n - -; 120 } while ( n > 1) ; 121 } 122 123 int main () 124 { 125 int nr , poz , m ; 126 LISTA curent = creareLista ( nr ) ; 127 // relizam o copie a listei initiale 128 LISTA curent_copy = copieLista ( curent ) ; 129 cout < < " Lista circulara initiala. " next este adresa primului nod al listei, iar crt şi crt->next->back reprezintă adresa ultimului nod al acesteia. Toate elementele listei pot fi accesate secvenţial plecând de la nodul de adresă crt. Pentru lista circulară dublu ı̂nlănţuită din figura de mai jos, nodul curent, ţintit de pointerul crt, este nodul de informaţie utilă infoN. Figura 3.11: Listă circulară dublu ı̂nlănţuită Operaţiile pe care le vom implementa asupra listelor circulare dublu ı̂nlănţuite sunt cele obişnuite: ˆ crearea listei vide (necesită iniţializarea crt = nullptr); ˆ inserarea unui element nou ı̂n listă; ˆ eliminarea unui nod al listei; ˆ parcurgerea listei pentru a realiza diverse operaţii asupra informaţiilor din noduri. Pentru a crea o listă circulară dublu ı̂nlănţuită, plecând de la lista vidă, vom adăuga ı̂n mod repetat noduri după nodul ţintit de pointerul crt. Pentru inserarea unui nod nou sunt două situaţii: ˆ inserarea nodului nou ı̂naintea unui nod de informaţie dată; ˆ inserarea nodului nou după un nod de informaţie dată. În ambele cazuri, se parcurg următoarele etape: 1. se caută nodul ı̂naintea căruia sau după care se realizează inserarea (dacă există, adresa sa se va reţine ı̂n pointerul q); 2. se alocă memorie pentru nodul nou; 3. se ı̂ncarcă zona de informaţie a acestuia; 4. se crează legăturile noi; 5. se şterg vechile legături. Pentru cazul inserării unui nod nou ı̂naintea nodului ţintit de pointerul q, acesta se inserează ı̂ntre nodurile ţintite de q->back şi q, iar ı̂n cazul adăugării unui nod nou după nodul ţintit de q, acesta se inserează ı̂ntre nodurile ţintite q şi q->next. Atenţie deosebită se va acorda pointerului crt, ce trebuie actualizat corespunzător atunci când este cazul. Pentru a şterge un nod de informaţie dată: 1. se caută nodul ı̂n listă; 2. se crează legaturile noi; 3. se eliberează spaţiul de memorie aferent. Dacă q este adresa nodului ce va fi şters, atunci nodul ţintit de q->back se va lega de nodul ţintit de q->next. Dacă nodul de şters este cel ţintit de crt, atunci crt va pointa spre nodul precedent. 65  Structuri de date Note de curs 1 struct NOD 2 { 3 int info ; 4 NOD * next ; // pointer catre succesor 5 NOD * back ; // pointer catre predecesor 6 }; 7 typedef NOD * LISTA ; 8 9 void error ( const char msg []) 10 { } 11 12 void adaugare ( LISTA & crt , int infon ) 13 { 14 // adaugarea unui nod nou dupa nodul tintit de crt 15 LISTA nou = new ( nothrow ) NOD ; 16 if ( nou == nullptr ) 17 error ( " Spatiu insuficient ! " ) ; 18 nou - > info = infon ; 19 if ( crt == nullptr ) // lista este vida 20 { 21 crt = nou ; // crt contine adresa " ultimului " nod , nodul curent 22 crt - > next = nou ; // crt - > next este adresa " primului " nod 23 crt - > back = nou ; 24 } 25 else 26 { 27 // adaugare dupa crt , deci intre crt si crt - > next 28 // legaturile noi 29 nou - > next = crt - > next ; 30 nou - > back = crt ; 31 // legaturile vechi 32 crt - > next - > back = nou ; 33 crt - > next = nou ; 34 crt = nou ; 35 } 36 } 37 38 LISTA creareLista () 39 { 40 int nr_noduri , info ; 41 LISTA crt = nullptr ; // lista vida 42 cout < < " Numarul de noduri initiale : " ; 43 cin > > nr_noduri ; 44 for ( int i = 1; i next ; 62 } while ( p != crt ) ; 63 cout < < endl ; 64 } 65 else 66 cout < < " Lista este vida ! " back ; 78 } while ( p != crt ) ; 79 cout < < endl ; 80 } 81 else 82 cout < < " Lista este vida ! " info == infoc ) 93 return p ; // se returneaza adresa nodului de informatie infoc 94 p = p - > next ; 95 } while ( p != crt ) ; 96 } 97 return nullptr ; 98 } 99 100 void i ns er ar e In ai nt e ( LISTA & crt , int infoc , int infon ) 101 { 102 if ( crt == nullptr ) 103 { 104 cout < < " LISTA este vida ! " back si q 113 LISTA nou = new ( nothrow ) NOD ; 114 if ( nou == nullptr ) 115 error ( " Spatiu insuficient ! " ) ; 116 nou - > info = infon ; 117 // legaturile noi 118 nou - > next = q ; 119 nou - > back = q - > back ; 120 // legaturile vechi 121 q - > back - > next = nou ; 122 q - > back = nou ; 123 if (q - > back == crt ) 124 crt = nou ; 125 } 126 else 127 cout < < " Informatia cautata " next = q - > next ; 148 nou - > back = q ; 149 // legaturile vechi 150 q - > next - > back = nou ; 151 q - > next = nou ; 152 if ( q == crt ) 153 crt = nou ; 154 } 155 else 156 cout < < " Informatia cautata " back de q - > next 175 q - > back - > next = q - > next ; 176 q - > next - > back = q - > back ; 177 if ( q == crt ) crt = q - > back ; 178 } 179 delete q ; 180 } 181 else 182 cout < < " Informatia cautata " > n ; 23 for ( int i = 1; i x ; 38 do 39 { 40 cout < < " Sensul (1 - sens orar , 2 - sens antiorar ) : " ; 41 cin > > y ; 42 } while ( y != 1 && y != 2) ; 43 m = 0; 44 A [ m ] = x ; 45 A [ m ] = y ; 46 cout < < " Mai introduceti o mutare ? [ D / N ]: " ; 47 cin > > ch ; 48 while ( ch == ’d ’ || ch == ’D ’) 49 { 50 m = m + 1; 51 cout < < " Mutarea " > y ; 58 } while ( y != 1 && y != 2) ; 59 A [ m ] = x ; 60 A [ m ] = y ; 61 if ( m >= dim -1) break ; 62 cout < < " Mai introduceti o mutare ? [ D / N ]: " ; 63 cin > > ch ; 64 } 65 } 66 67 void cifru ( LISTA crt , int A [ dim ] , int m ) 68 { 69 // nr. mutari = m + 1 70 LISTA q = crt - > next ; 71 for ( int i = 0; i