Embedded Files
Laborator 2: Stive si Cozi
Laborator 2: Stive si Cozi
Stive
Cozi
Cozi cu liste (inserare la final, stergere de la inceput):
Sursa:
Sursa:
#include <iostream>using namespace std; struct stiva_cu_vector{ int elemente[200]; int varf=0; void push(int x){ elemente[varf]=x; varf++; } int pop(){ if (varf==0) return -1; varf--; return elemente[varf]; } void afisare(){ int i; cout<<"[BAZA> "; for(i=0;i<varf;i++) cout<<elemente[i]; cout<<" [VARF>"<<endl; }}; struct nod{ int info; nod* next;}; struct lista{ nod* primul_element;//pointer la primul element nod* ultimul_element;//pointer la ultimul element lista(){ primul_element=NULL;//initializare ultimul_element=NULL;//initializare } void insert_la_inceput(int x){ nod* nou = new nod;//alocam spatiu nou->info =x;//punem x in campul intreg nou->next = primul_element; // punem adresa din primul_element in campul adresa next // legam nou de primul_element primul_element = nou; // actualizam care este adresa noului nod de la inceput if (ultimul_element==NULL) // daca lista era goala -> acum extista 1 nod ultimul_element=nou; //ultimul_element trebuie sa-l indice pe acel nod } int delete_de_la_inceput(){ if (primul_element==NULL)//sa nu crape stergerea in lista vida return -1;//sa intoarcem o valoare speciala int ce_intorc=primul_element->info;//salvam valoarea ca sa o putem intoarce nod* ce_sterg=primul_element; //salvam adresa nodului pe care dorim sa-l dezalocam primul_element=primul_element->next; // primul_element il indica pe urmatorul if (primul_element==NULL) //daca prin stergere am vidat lista, ultimul_element=NULL; //trebuie sa actualizam si celalalt pointer delete ce_sterg; //dezalocam nodul folosind adresa salvata return ce_intorc; } void insert_la_final(int x){ nod* nou = new nod; //alocam nou->info =x; //info nou->next = NULL; //punem NULL in adresa pentru ca acest nod va fi ultimul if (ultimul_element==NULL) //daca lista era vida primul_element=ultimul_element=nou; //atunci ambii pointeri indica noul nod else{ ultimul_element->next=nou; //legam ultimul de nou ultimul_element=nou; //ultimul nod trebuie actualizat, stocam adresa lui in ultimul_element } } void afisare(){ nod* pointer; for (pointer = primul_element; pointer !=NULL;pointer = pointer->next) cout<<pointer->info<< " -> "; cout<<endl; }}; struct stiva_cu_lista{ lista L; void push(int x){ L.insert_la_inceput(x); } int pop(){ return L.delete_de_la_inceput(); } void afisare(){ cout<<"<VARF] "; L.afisare(); }}; struct coada_cu_lista{ lista L; void enqueue(int x){ L.insert_la_final(x); } int dequeue(){ return L.delete_de_la_inceput(); } void afisare(){ cout<<"<OUT] "; L.afisare(); }}; int main(){ lista L; L.insert_la_inceput(1); L.afisare(); L.insert_la_inceput(2); L.afisare(); L.insert_la_inceput(3); L.afisare(); cout<<endl; stiva_cu_lista S; S.push(1); S.afisare(); S.push(2); S.afisare(); S.push(3); S.afisare(); cout<<"Am extras elementul "<<S.pop(); S.afisare(); cout<<"Am extras elementul "<<S.pop(); S.afisare(); cout<<"Am extras elementul "<<S.pop(); S.afisare(); cout<<"Am extras elementul "<<S.pop(); S.afisare(); S.push(4); S.afisare(); cout<<endl; coada_cu_lista C; C.enqueue(1); C.afisare(); C.enqueue(2); C.afisare(); C.enqueue(3); C.afisare(); cout<<"Am extras elementul "<<C.dequeue(); C.afisare(); cout<<"Am extras elementul "<<C.dequeue(); C.afisare(); cout<<"Am extras elementul "<<C.dequeue(); C.afisare(); cout<<"Am extras elementul "<<C.dequeue(); C.afisare(); C.enqueue(4); C.afisare();
//Problema inchiderii parantezelor: //dat un sir de paranteze sa se determine daca se inchid corect char* sir="((()())())"; int len =10; int i; stiva_cu_lista my_stack; int prea_multe_paranteze_inchise=0; for (i=0;i<len;i++) if (sir[i]=='(') my_stack.push(123); else if (sir[i]==')') if (my_stack.pop()<0){ prea_multe_paranteze_inchise=1; break; } cout<<endl; if (!prea_multe_paranteze_inchise && my_stack.L.primul_element==NULL) cout<<"STIVA-I VIDA, TOTU-I BINE"; else if (prea_multe_paranteze_inchise) cout<<"PREA MULTE PARANTEZE INCHISE"; else cout<<"PREA MULTE PARANTEZE DESCHISE"; return 0;}
//Problema inchiderii parantezelor: //dat un sir de paranteze sa se determine daca se inchid corect char* sir="((()())())"; int len =10; int i; stiva_cu_lista my_stack; int prea_multe_paranteze_inchise=0; for (i=0;i<len;i++) if (sir[i]=='(') my_stack.push(123); else if (sir[i]==')') if (my_stack.pop()<0){ prea_multe_paranteze_inchise=1; break; } cout<<endl; if (!prea_multe_paranteze_inchise && my_stack.L.primul_element==NULL) cout<<"STIVA-I VIDA, TOTU-I BINE"; else if (prea_multe_paranteze_inchise) cout<<"PREA MULTE PARANTEZE INCHISE"; else cout<<"PREA MULTE PARANTEZE DESCHISE"; return 0;}
MAXIM ~3 STUDENTI PER GRUPA LA ACEEASI TEMA
🙂 Sortati o lista folosind selectia minimului.
Se poate implementa in mai multe feluri, de exemplu:
La fiecare pas caut minimul, il extrag din lista si il inserez in alta lista.
🙂 Implementati polinoame rare (reprezentate prin perechea coeficient, exponent) folosind o lista.
Este o lista rara ordonata dupa exponent (presupunem ca se citesc in ordine exponentii, nu sortam).
Exemplu: 7x^123 + 8x^22 + 15 ar putea fi (0,15)->(22,8)->(123,7)
Calculati suma a doua polinoame prin interclasarea listelor ce retin termenii.
🙂 Creati o lista dublu inlantuita (cu pointeri prev, next) cu doua operatii insert si extract care insereaza sau sterg aceeasi cheie (cu semn schimbat) la ambele capete de fiecare data: insert 1,2,3: ... -3 -2 -1 1 2 3 ...
🙂 Implementati o coada de prioritati in care cheile sunt perechi (valoare, prioritate). Coada trebuie mentinuta sortata dupa prioritate. Implementati insertia si extragerea. (Pentru a insera se parcurge lista pana la pozitia pe care trebuie inserat elementul in asa fel incat lista sa fie sortata) Elementele cu aceeasi prioritate sunt extrase in ordinea in care au venit.
🙂 Algoritmul lui Josephus implementat cu o lista circulara simplu inlantuita.
Se initializeaza o lista cu valorile de la 1 la n, se extrag elemente din k in k si se afiseaza ordinea extragerilor pana cand ramane unul. Sa se determine elementul ramas la final in lista.
🙂🔨👑 (Vector dinamic) Implementati un vector dinamic ca fiind o lista de vectori mai mici de dimensiune fixata k (de exemplu k=20). Fiecare nod de lista contine un tablou de k intregi. Vrem sa avem operatie pentru updatat o pozitie v[123] = 15; Pentru k=20 se aloca 7 noduri si in al 7 lea nod pe pozitia a patra scriem 15. In rest in vectorii mici se gasesc zerouri daca nu am facut update. Implementati suma a doi astfel de vectori.
🙂🔨👑 Spunem ca o imagine digitala binară M este o matrice de m x m elemente (pixeli) 0 sau 1. Un element a al matricei este adiacent cu b, daca b se afla deasupra, la dreapta, dedesubtul, sau la stanga lui a in imaginea M.
Spunem ca doi pixeli 1 adiacenti apartin aceleiasi componente. Problema va cere sa etichetati pixelii imaginii astfel incat doi pixeli primesc aceeasi eticheta daca si numai daca apartin aceleiasi componente.
Folositi o stivă sau o pereche de stive ca să introduceți coordonatele i și j ale primei apariții de 1. După care, câtă vreme sitva nu e vidă scoateți coordonatele, colorați și puneți toți vecinii care au 1 în coadă. Repetare pentru fiecare 1 rămas în matrice.
🙂🔨👑 Probleme pentru smecheri:
A. (3p) Rezolvati problema 7 cu păduri de multimi disjuncte (disjoint set forest - sau structura union-find), structura descrisa in Cormen. Explicatii in laborator.
B. (3p) Implementati Skip list. Explicatii pe wikipedia.
CD) Implementati Matrice rara.
C. (3p) Implementati Suma pe matrici rare.
D. (4p) Implementati Produs pe matrici rare.
Google Sites
Report abuse