Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Coada - Care este utilitatea unei cozi?

c

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Else-If
Coada - Care este utilitatea unei cozi?
Instructiunea For
Bucle - While si For
PROGRAMAREA STRUCTURILOR DE DATE IN C++
Switch
Operatori relationali si logici
Variabile si aritmetica
FUNCTII SI STRUCTURA PROGRAMULUI
Struct (inregistrarea)

TERMENI importanti pentru acest document

Coada

Aspecte teoretice




Coada e tot un tip special de lista in care elementele sunt inserate la un capat ( spate ) si sunt suprimate la celalalt ( fata ); se mai numesc liste FIFO ( First In First Out ), adica de tip primul venit, primul servit.

Cele mai uzuale implementari ale cozii sunt cu ajutorul tipului pointer si al tablourilor circulare.

Coada bazata pe prioritate e strucutra de date abstracta care permite insertia unui nou element si suprimarea celui mai mare element dintre cele existente. Structura difera de coada (din care se suprima primul venit, deci elementul cel mai vechi ) si de stiva ( din care se suprima ultimul venit, deci cel mai nou ).

Asupra acestei structuri de date, ale carei elemente sunt articole cu chei ( sau prioritati ), se definesc operatiile :

GENEREAZA - o coada bazata pe prioritati, pornind de la N elemente ( succesiune de insertii )

INSEREAZA - un nou element

EXTRAGE - cel mai mare element

INLOCUIRE - a celui mai mare element cu unul nou, mai putin prioritar ( insertie + suprimare )

SCHIMBA - prioritatea unui element ( suprimare + insertie )

SUPRIMA - un element oarecare, precizat

REUNESTE - doua cozi in una singura.

Ca implementari a acestei structuri de date, sunt mai uzuale cele ce folosesc liste neordonate, liste ordonate dupa prioritate, ansamble.

Coada este o strucutra de date abstracta pentru care operatia de inserare a unui element se realizeaza la un capat, in timp ce operatia de extragere a unui element se realizeaza la celalalt capat.

Singurul element din coada la care avem acces direct este cel de la inceput.


Operatii caracteristice[1]

Singurele operatii ce pot fi executate cu o coada sunt:

crearea unei cozi vide;



inserarea unui element in coada;

extragerea unui element din coada;

accesarea unui element.

Executarea acestor operatii asupra unei cozi presupune cunoasterea inceputului cozii (notat Inc) si a sfarsitului acesteia(notat Sf).

Datorita faptului ca intotdeauna este extras (“servit”) primul element din coada, iar inserarea oricarui nou element se face la sfarsit (“la coada”), coada este definita ca o strucutra de date care functioneaza dupa principiul FIFO[2].

Care este utilitatea unei cozi?

Utilitatea structurii de tip coada reiese din modul sau de functionare – este necesara utilizarea unei cozi atunci cand informatiile trebuie prelucrate exact in ordinea in care „au sosit” si ele sunt retinute in coada pana cand pot fi prelucrate. In informatica, cozile sunt utilizate frecvent.

De exemplu, sa consideram ca avem o retea de calculatoare si o singura imprimanta. Cand utilizatorii retelei vor da comenzi de tiparire, imprimanta nu poate raspunde tuturor comenzilor in acelasi timp. Prin urmare, comenzile de tiparire primite sunt inregistrate intr-o coada (Print Queue – coada de tiparire). Imprimanta va tipari documentele pe rand, in ordinea in care au fost inregistrate in coada. Un alt exemplu: pentru a mari viteza de executie, microprocesoarele utilizeaza o coada de instructiuni in care sunt memorate instructiunile ce urmeaza a fi executate.

Cum implementam o coada?

Coada este o strucutra de date abstracta care poate fi implementata in diferite moduri. Un exemplu ar fi implementata statica a unei cozi, retinand elementele sale intr-un vector.

Exemplul urmator reprezinta declararea unei cozi cu elemente de tip int alocata static:

#define DimMax 100    //numarul maxim de elemente din coada typedef int Coada [DimMax]; //tipul Coada implementat ca vector

Coada C;    //coada

int inc,Sf;    //inceputul si sfarsitul cozii

Elementele cozii sunt memorate in vector de la pozitia Inc pana la pozitia Sf, deci numarul lor este Sf – Inc + 1.



Modul de functionare a unei cozi este usor de intuit: toata lumea a stat la coada”. Orice situatie in care sunt mai multe cereri de acces la o resursa unica (mai multi clienti si o singura vanzatoare; o singura pompa de benzina si mai multe masini etc.) necesita formarea unei “linii de asteptare”. Daca nu apar alte prioritati, cererile sunt satisfacute in ordinea sosirii.

First In First Out - primul intrat primul iesit








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 645
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2020 . All rights reserved

Distribuie URL

Adauga cod HTML in site