1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Queue]

2
00:00:02,000 --> 00:00:05,000
[Chris Gerber, Universitatea Harvard]

3
00:00:05,000 --> 00:00:07,000
Acest lucru este CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Un utile structura de date pentru stocarea o colecție ordonată de elemente este o listă de așteptare.

5
00:00:11,000 --> 00:00:14,000
Acesta este utilizat atunci când elementele trebuie să fie eliminate

6
00:00:14,000 --> 00:00:16,000
în aceeași ordine în care au fost adăugate.

7
00:00:16,000 --> 00:00:20,000
Acest concept este menționată ca FIFO, care este un acronim pentru primul, primul ieșit.

8
00:00:20,000 --> 00:00:23,000
Pentru a ajuta la vizualizarea acest lucru, ar putea fi util pentru a fotografia

9
00:00:23,000 --> 00:00:25,000
o linie de checkout la un magazin.

10
00:00:25,000 --> 00:00:28,000
Pe masura ce oamenii ajung, ei așteaptă de la partea din spate a liniei.

11
00:00:28,000 --> 00:00:31,000
Casierul ia apoi se servește clienților în față,

12
00:00:31,000 --> 00:00:34,000
care apoi ieșiți o linie la un moment dat.

13
00:00:34,000 --> 00:00:37,000
În informatică, ne referim la partea din față a cozii drept cap

14
00:00:37,000 --> 00:00:39,000
și înapoi ca coada.

15
00:00:39,000 --> 00:00:41,000
Un exemplu de când ne-am putea folosi această într-o cerere

16
00:00:41,000 --> 00:00:44,000
este o lista de așteptare pentru inscrieri clasa.

17
00:00:44,000 --> 00:00:46,000
Ca scaune devin disponibile în clasă,

18
00:00:46,000 --> 00:00:50,000
persoana în fruntea listei de așteptare este oferit oportunitatea de a se inscrie in clasa.

19
00:00:50,000 --> 00:00:53,000
>> O coada poate fi construit folosind orice colecție

20
00:00:53,000 --> 00:00:57,000
care stochează datele în ordine, cum ar fi o matrice sau o listă de legat.

21
00:00:57,000 --> 00:01:00,000
Alături de colectare pentru a stoca elemente în coada de așteptare,

22
00:01:00,000 --> 00:01:02,000
avem nevoie, de asemenea, o metodă de a adăuga elemente la sfârșitul cozii de așteptare,

23
00:01:02,000 --> 00:01:04,000
care se numește enqueuing,

24
00:01:04,000 --> 00:01:07,000
și altul pentru a elimina un element din capul cozii,

25
00:01:07,000 --> 00:01:09,000
care se numește dequeuing.

26
00:01:09,000 --> 00:01:14,000
Acesta este adesea util să includă o altă metodă pentru a reveni la lungimea curentă a cozii

27
00:01:14,000 --> 00:01:17,000
precum și o metodă de a verifica dacă coada este goală.

28
00:01:17,000 --> 00:01:20,000
Să ne uităm la cum putem să pună în aplicare o coada de intregi în C,

29
00:01:20,000 --> 00:01:23,000
folosind o matrice pentru colectarea de elemente.

30
00:01:23,000 --> 00:01:27,000
În primul rând, vom crea o structura numita coadă să dețină variabile noastre.

31
00:01:27,000 --> 00:01:30,000
Vom folosi un fix-dimensiune matrice de intregi index 0

32
00:01:30,000 --> 00:01:33,000
pentru a stoca elemente.

33
00:01:33,000 --> 00:01:35,000
Vom include, de asemenea, o variabilă numită cap

34
00:01:35,000 --> 00:01:39,000
care stochează indicele elementului care este în prezent în fruntea cozii.

35
00:01:39,000 --> 00:01:42,000
O variabilă treilea, numit lungime, vor fi utilizate

36
00:01:42,000 --> 00:01:45,000
pentru a ține evidența numărului de elemente din matrice.

37
00:01:45,000 --> 00:01:48,000
Ca o alternativă, puteți lua în considerare utilizarea o coada variabilă numită

38
00:01:48,000 --> 00:01:51,000
pentru a indica elementul ultimul câmp în matrice.

39
00:01:51,000 --> 00:01:53,000
Înainte de a scrie cod nici mai mult,

40
00:01:53,000 --> 00:01:55,000
Să încercați noastre de design.

41
00:01:55,000 --> 00:01:58,000
Să începem cu un array gol de lungime 0,

42
00:01:58,000 --> 00:02:02,000
cu capul setat la 0.

43
00:02:02,000 --> 00:02:11,000
Acum, haideți să redați 4 valori - 6, 2, 3, si 1.

44
00:02:11,000 --> 00:02:14,000
Lungimea va fi de acum 4,

45
00:02:14,000 --> 00:02:17,000
si capul va sta la 0.

46
00:02:17,000 --> 00:02:20,000
>> Ce se întâmplă dacă am dequeue o valoare?

47
00:02:20,000 --> 00:02:24,000
Vom reduce lungimea la 3,

48
00:02:24,000 --> 00:02:28,000
setat la 1 cap,

49
00:02:28,000 --> 00:02:33,000
și returnează valoarea 6.

50
00:02:33,000 --> 00:02:36,000
Acest cod ar putea arata ca acest lucru.

51
00:02:36,000 --> 00:02:38,000
Aici avem funcția dequeue,

52
00:02:38,000 --> 00:02:41,000
care are un pointer la coada - Q - și un pointer la elementul,

53
00:02:41,000 --> 00:02:44,000
care este un tip int.

54
00:02:44,000 --> 00:02:47,000
Mai întâi vom verifica lungimea cozii pentru a vă asigura că e mai mare de 0,

55
00:02:47,000 --> 00:02:50,000
pentru a se asigura că există un element care urmează să fie dequeued.

56
00:02:50,000 --> 00:02:54,000
Apoi, ne uităm în matrice elemente, de la poziția capului,

57
00:02:54,000 --> 00:02:58,000
și setați valoarea de element să fie valoarea în acea poziție.

58
00:02:58,000 --> 00:03:01,000
Apoi ne-am schimba capul pentru a fi indicele următor

59
00:03:01,000 --> 00:03:04,000
% Capacitate.

60
00:03:04,000 --> 00:03:07,000
Noi apoi reduceti lungimea cozii de 1.

61
00:03:07,000 --> 00:03:12,000
În cele din urmă, ne întoarcem adevărat pentru a indica faptul că a fost un succes dequeue.

62
00:03:12,000 --> 00:03:19,000
Dacă ne dequeue din nou, lungimea va deveni 2,

63
00:03:19,000 --> 00:03:24,000
Capul va deveni, de asemenea, 2,

64
00:03:24,000 --> 00:03:32,000
și valoarea returnata va fi de 2.

65
00:03:32,000 --> 00:03:35,000
>> Ce se întâmplă dacă am redați o altă valoare, cum ar fi un 7?

66
00:03:35,000 --> 00:03:37,000
Așa cum am fost la sfârșitul cozii de așteptare,

67
00:03:37,000 --> 00:03:47,000
va trebui să încheie în jurul valorii de și stoca valoarea 0, în elementul de matrice.

68
00:03:47,000 --> 00:03:50,000
Matematic, acest lucru poate fi reprezentat prin adăugarea lungimea

69
00:03:50,000 --> 00:03:52,000
la indicele de cap

70
00:03:52,000 --> 00:03:55,000
și efectuarea unui modul folosind capacitatea de coada.

71
00:03:55,000 --> 00:04:00,000
Aici este că 2 +2, care este de 4% 4,

72
00:04:00,000 --> 00:04:02,000
care este 0.

73
00:04:02,000 --> 00:04:05,000
Traducerea această idee pentru a coda avem această funcție.

74
00:04:05,000 --> 00:04:08,000
Aici vom vedea funcția Puneți în coadă,

75
00:04:08,000 --> 00:04:10,000
care are un pointer la coada - Q -

76
00:04:10,000 --> 00:04:14,000
și ia elementul care urmează să fie enqueued, care este un număr întreg.

77
00:04:14,000 --> 00:04:18,000
Noi verificam lângă a vă asigura că capacitatea de coadă

78
00:04:18,000 --> 00:04:21,000
este încă mai mare decât lungimea actuala a cozii.

79
00:04:21,000 --> 00:04:24,000
În continuare, vom păstra elementul din matrice elementele

80
00:04:24,000 --> 00:04:30,000
la indicele, care este determinat de cap +% lungimea capacitatea de a cozii.

81
00:04:30,000 --> 00:04:33,000
Am crește atunci lungimea cozii de 1,

82
00:04:33,000 --> 00:04:39,000
și a reveni apoi pentru a indica faptul că adevărata funcția Puneți în coadă a fost un succes.

83
00:04:39,000 --> 00:04:42,000
>> În plus față de cele două funcții care le-am menționat,

84
00:04:42,000 --> 00:04:44,000
există două funcții suplimentare.

85
00:04:44,000 --> 00:04:46,000
În primul rând este funcția isEmpty,

86
00:04:46,000 --> 00:04:48,000
care are un pointer la coada

87
00:04:48,000 --> 00:04:51,000
și verifică faptul că lungimea este 0.

88
00:04:51,000 --> 00:04:53,000
A doua este funcția lungime,

89
00:04:53,000 --> 00:04:55,000
care are, de asemenea, un pointer la coada

90
00:04:55,000 --> 00:04:58,000
și returnează lungimea curentă din struct.

91
00:04:58,000 --> 00:05:03,000
Această scurtă trecere în revistă a demonstrat o posibilă punerea în aplicare a unei cozi.

92
00:05:03,000 --> 00:05:06,000
Una dintre limitările la această punere în aplicare

93
00:05:06,000 --> 00:05:08,000
este faptul că coada are o dimensiune maximă fixă.

94
00:05:08,000 --> 00:05:11,000
Dacă vom incerca sa adaugam mai multe elemente decât coada poate deține,

95
00:05:11,000 --> 00:05:14,000
am putea avea nevoie pentru a ignora cererea și fixați elementul,

96
00:05:14,000 --> 00:05:17,000
sau am putea prefera să se întoarcă un anumit tip de eroare.

97
00:05:17,000 --> 00:05:20,000
Folosind o listă legată mai degrabă decât o matrice

98
00:05:20,000 --> 00:05:22,000
ar face mai ușor de dimensiunea dinamic coada.

99
00:05:22,000 --> 00:05:26,000
Cu toate acestea, din moment ce nu au acces direct la elementele unei liste legate,

100
00:05:26,000 --> 00:05:28,000
dacă nu urmări coada,

101
00:05:28,000 --> 00:05:32,000
ne-ar trebui pentru a scana întreaga listă legată pentru a ajunge la sfârșitul fiecare dată.

102
00:05:32,000 --> 00:05:35,000
Am putea lua în considerare, de asemenea, folosind o serie de alt tip de date,

103
00:05:35,000 --> 00:05:39,000
cum ar fi struct, pentru a crea cozi de mai multe elemente complexe.

104
00:05:39,000 --> 00:05:42,000
Gândindu-mă la exemplul nostru de lista de așteptare clasa,

105
00:05:42,000 --> 00:05:45,000
aceste structuri ar putea reprezenta studenții individuale.

106
00:05:45,000 --> 00:05:48,000
>> Numele meu este Chris Gerber, iar acest lucru este CS50.

107
00:05:48,000 --> 00:05:51,000
[CS50.TV]

108
00:05:51,000 --> 00:05:55,000
Și se întoarce - >> Unul mai mult timp.

109
00:05:55,000 --> 00:06:00,000
Și să se întoarcă adevărat pentru a indica faptul că - coada a fost un succes.

110
00:06:00,000 --> 00:06:03,000
- Capacitatea% din coadă -

111
00:06:03,000 --> 00:06:06,000
O să fie distractiv în editare. [Râsete]