Laborator 6 - Algoritmi ce utilizeaza stive sau cozi

1. Radix Sort

Algoritmul de Radix Sort este un algoritm de sortare ce se foloseste de 10 cozi, fiecare coada reprezentand o cifra. La fiecare pas al algoritmului se analizeaza cifra de pe o anumita pozitie pentru toate elementele vectorului, se plaseaza fiecare numar in coada corespunzatoare si mai apoi noul vector este compus de elementele celor 10 cozi parcurse de la coada 0 la coada 9. Procedeul se executa de n ori, n fiind numarul maxim de cifre pe care-l poate avea un element din vector. Pentru o mai buna intelegere a algoritmului, urmariti exemplul de mai jos. In acest exemplu pentru reprezentarea cozii consideram ca adaugarea se face prin capatul din dreapta si scoaterea prin capatul din stanga.

Exemplu

Vector initial : {12, 22, 101, 89, 23, 70 , 1 , 45, 77, 905}

Pas 1 (cifra unitatilor):Coada 0 : 70Coada 1 : 101, 1Coada 2 : 12, 22Coada 3 : 23Coada 4 :Coada 5 : 45, 905Coada 6 : Coada 7 : 77Coada 8 :Coada 9 : 89

Vectorul dupa pasul 1 : {70, 101, 1, 12, 22, 23, 45, 905, 77, 89}

Pas 2 (cifra zecilor):Coada 0 : 101, 1, 905Coada 1 : 12Coada 2 : 22, 23Coada 3 : Coada 4 : 45Coada 5 : Coada 6 : Coada 7 : 70, 77Coada 8 : 89Coada 9 :

Vectorul dupa pasul 2 : {101, 1, 905, 12, 22, 23, 45, 70, 77, 89}

Pas 2 (cifra sutelor):Coada 0 : 1, 12, 22, 23, 45, 70, 77, 89Coada 1 : 101Coada 2 : Coada 3 : Coada 4 : Coada 5 : Coada 6 : Coada 7 :Coada 8 : Coada 9 : 905

Vectorul dupa pasul 3 : {1, 12, 22, 23, 45, 70, 77, 89, 101, 905}

Vectorul final : {1, 12, 22, 23, 45, 70, 77, 89, 101, 905}

Urmarind TO DO 1 - 4 din fisierul lab6.c implementati algoritmul Radix Sort.

2. Problema celebritatilor

Intr-o incapere cu N oameni exista o persoana ce este cunoscuta de toata lumea. Acea persoana este o celebritate si ea nu cunoaste pe nimeni. Cine este celebritatea din incapere stiind ca putem pune (de cate ori vrem) intrebarea "A il cunoaste pe B?" ?. Pentru rezolvarea problemei implementati TO DO 5 - 6 din fisierul lab6.c .

Hint : Folositi o stiva in care sunt toate persoanele din incapere.

3. Conversia unei expresii matematice din scrierea infixata in scrierea postfixata (forma poloneza inversa)

Avantajele scrierii postfixate fata de scrierea infixata :a. Parantezele pentru fortarea prioritatii de aplicare a operatorului nu

mai sunt necesare.b. Evaluarile sunt usor de efectuat cu ajutorul calculului.c. Evidentierea clara a ordinii de efectuare a operatiilor.

Pentru realizarea acestei conversii vom avea nevoie de o stiva in care vom retine operatorii si ii vom scoate in functie de un set de reguli definite pe baza prioritatilor urmatoare :

Prioritate 1 : ([{Prioritate 2 : )]}Prioritate 3 : +-Prioritate 4 : */

Algoritm :cat timp (!sfarsit expresie infixata)

citire tokendaca token este numar

adauga la expresia rezultatdaca token este o paranteza deschisa

adauga token in stivadaca token este )]}

cat timp varful stivei este diferit de ([{scoate element din stivaadaugare element la expresia rezultat

scoate paranteza deschisa din stivadaca token este un operator

1. cat timp varful stivei nu are o prioritate mai

mica decat operatorul curent se trece operatorul

din varful stivei in expresia rezultat 2. se introduce token in stiva

cat timp stiva nu este vidascoate element din stivaadaugare element la expresia rezultat

Exemplu:

Expresie infixata : 3 + 4 * 1 + ( 2 - 3 )

expresie infixata : + 4 * 1 + ( 2 - 3 )operatori :

expresie posfixata : 3

expresie infixata : 4 * 1 + ( 2 - 3 )operatori : +expresie posfixata : 3

expresie infixata : * 1 + ( 2 - 3 )operatori : + expresie posfixata : 3 4

expresie infixata : 1 + ( 2 - 3 )operatori : + *expresie posfixata : 3 4

expresie infixata : + ( 2 - 3 )operatori : + *expresie posfixata : 3 4 1

+ are o priotitate mai mica decat * => scoate pana gasim un op cu prioritate strict mai micadecat prioritatea lui +

expresie infixata : + ( 2 - 3 )operatori : expresie posfixata : 3 4 1 * +

expresie infixata : ( 2 - 3 )operatori : +expresie posfixata : 3 4 1 * +

expresie infixata : 2 - 3 )operatori : + (expresie posfixata : 3 4 1 * +

expresie infixata : - 3 )operatori : + ( expresie postfixata : 3 4 1 * + 2

expresie infixata : 3 )operatori : + ( -expresie postfixata : 3 4 1 * + 2

expresie infixata )operatori : + ( - expresie postfixata : 3 4 1 * + 2 3

gasim paranteza inchisa => scoatem tot ce avem in stiva pana la o paranteza deschisa si paranteza deschisa

expresie infixata :operatori : +expresie postfixata : 3 4 * + 2 3 -

expresie postfixata : 3 4 1 * + 2 3 - +

4. Evaluarea unei expresii matematice in scriere postfixata

Algoritm :cat timp (!sfarsit expresie postfixata)

citire tokentoken este numar

adaugare token pe stivatoken este operator

se extrage y din varful stiveise extrage x din varful stiveise evalueaza x operator yse adauga rezultatul pe stiva

rezultat = valoarea ramasa in stiva