1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Eilės]

2
00:00:02,000 --> 00:00:05,000
[Chris Gerber, Harvardo universiteto]

3
00:00:05,000 --> 00:00:07,000
Tai CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Vienas iš naudingiausių duomenų struktūra saugoti tvarkingas elementų kolekciją eilė.

5
00:00:11,000 --> 00:00:14,000
Jis naudojamas, kai reikia pašalinti elementai

6
00:00:14,000 --> 00:00:16,000
ta pačia tvarka, kaip jie buvo įtraukti.

7
00:00:16,000 --> 00:00:20,000
Ši koncepcija yra nurodytas kaip FIFO, kuris pirmą santrumpa in, first out.

8
00:00:20,000 --> 00:00:23,000
Norėdami padėti vizualizuoti tai, ji gali būti naudinga į paveikslėlį

9
00:00:23,000 --> 00:00:25,000
patikros linija parduotuvėje.

10
00:00:25,000 --> 00:00:28,000
Kaip žmonės atvyksta, jie laukia nugaros linijos.

11
00:00:28,000 --> 00:00:31,000
Kasininkas, tada paeiliui aptarnauti klientus priekyje,

12
00:00:31,000 --> 00:00:34,000
kurie paskui išeiti iš linijos vienu metu,.

13
00:00:34,000 --> 00:00:37,000
Informatikos, mes vadiname eilės priekyje, galvos

14
00:00:37,000 --> 00:00:39,000
ir uodegos atgal.

15
00:00:39,000 --> 00:00:41,000
Pavyzdžiui, kai mes galime naudoti šią paraiškos

16
00:00:41,000 --> 00:00:44,000
yra, klasės mokinių waitlist.

17
00:00:44,000 --> 00:00:46,000
Kadangi vietų tampa prieinamos klasėje,

18
00:00:46,000 --> 00:00:50,000
laukiančiųjų sąraše galvos asmuo suteikė galimybę stoti į klasę.

19
00:00:50,000 --> 00:00:53,000
>> Eilė gali būti formuojama naudojant jokios kolekcijos

20
00:00:53,000 --> 00:00:57,000
, kuris saugo duomenis, kad, pavyzdžiui, masyvo ar susietą sąrašą.

21
00:00:57,000 --> 00:01:00,000
, Kartu su surinkimo saugoti elementus eilėje,

22
00:01:00,000 --> 00:01:02,000
mes taip pat turime metodą įtraukti klausimus į eilės galą,

23
00:01:02,000 --> 00:01:04,000
kuris yra vadinamas enqueuing

24
00:01:04,000 --> 00:01:07,000
o kita pašalinti elementą iš eilės galvą,

25
00:01:07,000 --> 00:01:09,000
kuris yra vadinamas dequeuing.

26
00:01:09,000 --> 00:01:14,000
Ji dažnai yra naudinga įtraukti kitą būdą grįžti dabartinę ilgis eilėje

27
00:01:14,000 --> 00:01:17,000
taip pat metodą, siekiant patikrinti, ar eilė tuščia.

28
00:01:17,000 --> 00:01:20,000
Pažvelkime, kaip mes galime įgyvendinti sveikųjų skaičių eilę, C,

29
00:01:20,000 --> 00:01:23,000
naudojant įvairių elementų surinkimo.

30
00:01:23,000 --> 00:01:27,000
Pirma, mes sukurti struktūrą, vadinamas eilė laikyti savo kintamuosius.

31
00:01:27,000 --> 00:01:30,000
Mes naudosime fiksuoto dydžio 0 indekso masyvas sveikųjų skaičių

32
00:01:30,000 --> 00:01:33,000
saugoti elementus.

33
00:01:33,000 --> 00:01:35,000
Mes taip pat bus kintamasis vadinamas galvą

34
00:01:35,000 --> 00:01:39,000
, kuris saugo elemento, kuris šiuo metu yra eilės vadovo indeksą.

35
00:01:39,000 --> 00:01:42,000
Trečioji kintamasis, vadinamas ilgio, bus naudojama

36
00:01:42,000 --> 00:01:45,000
sekti masyvo elementų skaičių.

37
00:01:45,000 --> 00:01:48,000
Kaip alternatyva, Jūs galite apsvarstyti naudojant kintamasis vadinamas uodega

38
00:01:48,000 --> 00:01:51,000
, kad rodytų į paskutinę lauko elemento masyve.

39
00:01:51,000 --> 00:01:53,000
Prieš mes rašome, bet daugiau kodą,

40
00:01:53,000 --> 00:01:55,000
leiskite išbandyti savo dizainą.

41
00:01:55,000 --> 00:01:58,000
Pradėkime su Tuščio masyvo ilgio 0,

42
00:01:58,000 --> 00:02:02,000
su galva nustatyta į 0.

43
00:02:02,000 --> 00:02:11,000
Dabar tegul į eilę 4 vertės - 6, 2, 3, ir 1.

44
00:02:11,000 --> 00:02:14,000
Ilgis nuo šiol bus 4,

45
00:02:14,000 --> 00:02:17,000
ir galva liks 0.

46
00:02:17,000 --> 00:02:20,000
>> Kas atsitiks, jei mes dequeue vertę?

47
00:02:20,000 --> 00:02:24,000
Mes sumažinti ilgis 3,

48
00:02:24,000 --> 00:02:28,000
galvą į 1,

49
00:02:28,000 --> 00:02:33,000
ir grąžinti reikšmę 6.

50
00:02:33,000 --> 00:02:36,000
Kad kodas gali atrodyti taip.

51
00:02:36,000 --> 00:02:38,000
Čia mes turime dequeue funkciją,

52
00:02:38,000 --> 00:02:41,000
kuris trunka žymiklį į eilę - Q - ir žymiklį į elementą,

53
00:02:41,000 --> 00:02:44,000
kuris yra tipas int.

54
00:02:44,000 --> 00:02:47,000
Pirmiausia mes patikrinti ilgis eilėje, įsitikinkite, kad tai daugiau nei 0,

55
00:02:47,000 --> 00:02:50,000
siekiant užtikrinti, kad yra elementas, į kurį dequeued.

56
00:02:50,000 --> 00:02:54,000
Tada mes žiūrime į elementų masyve, galvos padėties,

57
00:02:54,000 --> 00:02:58,000
ir nustatykite elemento vertę toje vietoje vertė.

58
00:02:58,000 --> 00:03:01,000
Tada mes pakeisime galvą į kitą indeksas

59
00:03:01,000 --> 00:03:04,000
% Pajėgumų.

60
00:03:04,000 --> 00:03:07,000
Mes tada sumažinti eilės ilgis 1.

61
00:03:07,000 --> 00:03:12,000
Galiausiai, mes grįžti tiesa, nurodyti, kad dequeue buvo sėkmingas.

62
00:03:12,000 --> 00:03:19,000
, Jei mes dequeue dar kartą, ilgis bus 2,

63
00:03:19,000 --> 00:03:24,000
vadovas taip pat taps 2,

64
00:03:24,000 --> 00:03:32,000
ir grąžina vertė bus 2.

65
00:03:32,000 --> 00:03:35,000
>> Kas atsitiks, jei mes į eilę kitą vertę pvz 7?

66
00:03:35,000 --> 00:03:37,000
Kaip mes buvome į eilės galą,

67
00:03:37,000 --> 00:03:47,000
mums reikės, į kuriuos vyniojami aplink ir laikyti elementą 0 masyvo vertę.

68
00:03:47,000 --> 00:03:50,000
Matematiškai tai galima pavaizduoti pridedant ilgį

69
00:03:50,000 --> 00:03:52,000
galvos indeksas

70
00:03:52,000 --> 00:03:55,000
modulius, naudojant eilės pajėgumus ir atlikti.

71
00:03:55,000 --> 00:04:00,000
Čia, kad 2 +2, o tai yra 4% 4,

72
00:04:00,000 --> 00:04:02,000
kuris yra 0.

73
00:04:02,000 --> 00:04:05,000
Pavertus šią idėją koduoti, mes turime šią funkciją.

74
00:04:05,000 --> 00:04:08,000
Čia mes matome, kad į eilę funkciją,

75
00:04:08,000 --> 00:04:10,000
kuris trunka žymiklį į eilę - Q -

76
00:04:10,000 --> 00:04:14,000
ir trunka būti enqueued elementas, kuris yra sveikasis skaičius.

77
00:04:14,000 --> 00:04:18,000
Mums kitą kartą įsitikinkite, kad eilėje pajėgumas

78
00:04:18,000 --> 00:04:21,000
vis dar yra didesnis nei dabartinio ilgio eilės.

79
00:04:21,000 --> 00:04:24,000
Be to, mes saugome elementų masyvo elementas

80
00:04:24,000 --> 00:04:30,000
indekso, kuris yra nustatomas pagal galvos + ilgis% eilėje talpa.

81
00:04:30,000 --> 00:04:33,000
Mes tada padidinti ilgio eilės į 1,

82
00:04:33,000 --> 00:04:39,000
ir tada grįžti tiesa rodo, kad į eilę funkcija buvo sėkmingas.

83
00:04:39,000 --> 00:04:42,000
>> Be to, mes minėtų dviejų funkcijų,

84
00:04:42,000 --> 00:04:44,000
yra dvi papildomos funkcijos.

85
00:04:44,000 --> 00:04:46,000
Pirmasis yra funkcija isEmpty,

86
00:04:46,000 --> 00:04:48,000
, kuris trunka žymeklį į eilę

87
00:04:48,000 --> 00:04:51,000
ir tikrina, kad ilgis yra 0.

88
00:04:51,000 --> 00:04:53,000
Antrasis yra ilgis, funkcija,

89
00:04:53,000 --> 00:04:55,000
, kuri taip pat atsižvelgiama žymiklį į eilę

90
00:04:55,000 --> 00:04:58,000
ir grąžina dabartinį ilgis nuo struct.

91
00:04:58,000 --> 00:05:03,000
Ši trumpa parodė vieną galimybę įgyvendinti eilę.

92
00:05:03,000 --> 00:05:06,000
Vienas iš šio įgyvendinimo apribojimų

93
00:05:06,000 --> 00:05:08,000
yra tai, kad eilė turi nustatytą maksimalų dydį.

94
00:05:08,000 --> 00:05:11,000
Jei mes stengiamės pridėti daugiau elementų, nei eilė gali turėti,

95
00:05:11,000 --> 00:05:14,000
mums gali reikėti prašymą ignoruoti ir upuść elementą,

96
00:05:14,000 --> 00:05:17,000
arba mes galime nori grįžti šiek tiek klaidų.

97
00:05:17,000 --> 00:05:20,000
Naudojant susietą sąrašą, o ne masyvo

98
00:05:20,000 --> 00:05:22,000
būtų lengviau dinamiškai dydžio eilės.

99
00:05:22,000 --> 00:05:26,000
Tačiau, kadangi mes ne turėti tiesioginę prieigą prie susietą sąrašo elementų,

100
00:05:26,000 --> 00:05:28,000
jei mes neturime sekti uodegos,

101
00:05:28,000 --> 00:05:32,000
gauti iki galo, kiekvieną kartą, mes turėtume nuskaityti visą susietą sąrašą.

102
00:05:32,000 --> 00:05:35,000
Mes taip pat galėtų apsvarstyti galimybę naudoti kitą duomenų tipą, masyvo,

103
00:05:35,000 --> 00:05:39,000
pavyzdžiui kaip structs, sukurti daugiau sudėtingų elementų eiles.

104
00:05:39,000 --> 00:05:42,000
Mintys atgal mūsų klasės waitlist pavyzdys,

105
00:05:42,000 --> 00:05:45,000
šios struktūros galėtų atstovauti atskirus studentus.

106
00:05:45,000 --> 00:05:48,000
>> Mano vardas yra Chris Gerber, ir tai yra CS50.

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

108
00:05:51,000 --> 00:05:55,000
Ir grįžta -> One More Time.

109
00:05:55,000 --> 00:06:00,000
Ir grįžti tiesa, kad rodo, kad eilė buvo sėkmingas.

110
00:06:00,000 --> 00:06:03,000
-% Eilėje talpa -

111
00:06:03,000 --> 00:06:06,000
Jis bus įdomus redaguoti. [Juokas]