[Powered by Google Translate] [Queue]
[Chris Gerber, Universitatea Harvard]
Acest lucru este CS50, CS50.TV]
Un utile structura de date pentru stocarea o colecție ordonată de elemente este o listă de așteptare.
Acesta este utilizat atunci când elementele trebuie să fie eliminate
în aceeași ordine în care au fost adăugate.
Acest concept este menționată ca FIFO, care este un acronim pentru primul, primul ieșit.
Pentru a ajuta la vizualizarea acest lucru, ar putea fi util pentru a fotografia
o linie de checkout la un magazin.
Pe masura ce oamenii ajung, ei așteaptă de la partea din spate a liniei.
Casierul ia apoi se servește clienților în față,
care apoi ieșiți o linie la un moment dat.
În informatică, ne referim la partea din față a cozii drept cap
și înapoi ca coada.
Un exemplu de când ne-am putea folosi această într-o cerere
este o lista de așteptare pentru inscrieri clasa.
Ca scaune devin disponibile în clasă,
persoana în fruntea listei de așteptare este oferit oportunitatea de a se inscrie in clasa.
>> O coada poate fi construit folosind orice colecție
care stochează datele în ordine, cum ar fi o matrice sau o listă de legat.
Alături de colectare pentru a stoca elemente în coada de așteptare,
avem nevoie, de asemenea, o metodă de a adăuga elemente la sfârșitul cozii de așteptare,
care se numește enqueuing,
și altul pentru a elimina un element din capul cozii,
care se numește dequeuing.
Acesta este adesea util să includă o altă metodă pentru a reveni la lungimea curentă a cozii
precum și o metodă de a verifica dacă coada este goală.
Să ne uităm la cum putem să pună în aplicare o coada de intregi în C,
folosind o matrice pentru colectarea de elemente.
În primul rând, vom crea o structura numita coadă să dețină variabile noastre.
Vom folosi un fix-dimensiune matrice de intregi index 0
pentru a stoca elemente.
Vom include, de asemenea, o variabilă numită cap
care stochează indicele elementului care este în prezent în fruntea cozii.
O variabilă treilea, numit lungime, vor fi utilizate
pentru a ține evidența numărului de elemente din matrice.
Ca o alternativă, puteți lua în considerare utilizarea o coada variabilă numită
pentru a indica elementul ultimul câmp în matrice.
Înainte de a scrie cod nici mai mult,
Să încercați noastre de design.
Să începem cu un array gol de lungime 0,
cu capul setat la 0.
Acum, haideți să redați 4 valori - 6, 2, 3, si 1.
Lungimea va fi de acum 4,
si capul va sta la 0.
>> Ce se întâmplă dacă am dequeue o valoare?
Vom reduce lungimea la 3,
setat la 1 cap,
și returnează valoarea 6.
Acest cod ar putea arata ca acest lucru.
Aici avem funcția dequeue,
care are un pointer la coada - Q - și un pointer la elementul,
care este un tip int.
Mai întâi vom verifica lungimea cozii pentru a vă asigura că e mai mare de 0,
pentru a se asigura că există un element care urmează să fie dequeued.
Apoi, ne uităm în matrice elemente, de la poziția capului,
și setați valoarea de element să fie valoarea în acea poziție.
Apoi ne-am schimba capul pentru a fi indicele următor
% Capacitate.
Noi apoi reduceti lungimea cozii de 1.
În cele din urmă, ne întoarcem adevărat pentru a indica faptul că a fost un succes dequeue.
Dacă ne dequeue din nou, lungimea va deveni 2,
Capul va deveni, de asemenea, 2,
și valoarea returnata va fi de 2.
>> Ce se întâmplă dacă am redați o altă valoare, cum ar fi un 7?
Așa cum am fost la sfârșitul cozii de așteptare,
va trebui să încheie în jurul valorii de și stoca valoarea 0, în elementul de matrice.
Matematic, acest lucru poate fi reprezentat prin adăugarea lungimea
la indicele de cap
și efectuarea unui modul folosind capacitatea de coada.
Aici este că 2 +2, care este de 4% 4,
care este 0.
Traducerea această idee pentru a coda avem această funcție.
Aici vom vedea funcția Puneți în coadă,
care are un pointer la coada - Q -
și ia elementul care urmează să fie enqueued, care este un număr întreg.
Noi verificam lângă a vă asigura că capacitatea de coadă
este încă mai mare decât lungimea actuala a cozii.
În continuare, vom păstra elementul din matrice elementele
la indicele, care este determinat de cap +% lungimea capacitatea de a cozii.
Am crește atunci lungimea cozii de 1,
și a reveni apoi pentru a indica faptul că adevărata funcția Puneți în coadă a fost un succes.
>> În plus față de cele două funcții care le-am menționat,
există două funcții suplimentare.
În primul rând este funcția isEmpty,
care are un pointer la coada
și verifică faptul că lungimea este 0.
A doua este funcția lungime,
care are, de asemenea, un pointer la coada
și returnează lungimea curentă din struct.
Această scurtă trecere în revistă a demonstrat o posibilă punerea în aplicare a unei cozi.
Una dintre limitările la această punere în aplicare
este faptul că coada are o dimensiune maximă fixă.
Dacă vom incerca sa adaugam mai multe elemente decât coada poate deține,
am putea avea nevoie pentru a ignora cererea și fixați elementul,
sau am putea prefera să se întoarcă un anumit tip de eroare.
Folosind o listă legată mai degrabă decât o matrice
ar face mai ușor de dimensiunea dinamic coada.
Cu toate acestea, din moment ce nu au acces direct la elementele unei liste legate,
dacă nu urmări coada,
ne-ar trebui pentru a scana întreaga listă legată pentru a ajunge la sfârșitul fiecare dată.
Am putea lua în considerare, de asemenea, folosind o serie de alt tip de date,
cum ar fi struct, pentru a crea cozi de mai multe elemente complexe.
Gândindu-mă la exemplul nostru de lista de așteptare clasa,
aceste structuri ar putea reprezenta studenții individuale.
>> Numele meu este Chris Gerber, iar acest lucru este CS50.
[CS50.TV]
Și se întoarce - >> Unul mai mult timp.
Și să se întoarcă adevărat pentru a indica faptul că - coada a fost un succes.
- Capacitatea% din coadă -
O să fie distractiv în editare. [Râsete]