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, Harvard University]

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

4
00:00:07,000 --> 00:00:11,000
Egy hasznos adatstruktúra tárolására rendezett gyűjteménye elemek a sorban.

5
00:00:11,000 --> 00:00:14,000
Akkor használják, ha az elemeket el kell oszlatni

6
00:00:14,000 --> 00:00:16,000
abban a sorrendben, ahogy adunk.

7
00:00:16,000 --> 00:00:20,000
Ez a koncepció nevezik FIFO, ami egy mozaikszó az első be, első ki.

8
00:00:20,000 --> 00:00:23,000
Annak érdekében, hogy láthatóvá E, hasznos lehet a kép

9
00:00:23,000 --> 00:00:25,000
a pénztárnál sorban egy boltban.

10
00:00:25,000 --> 00:00:28,000
Mivel az emberek érkeznek, hogy várjon a hátsó sorban.

11
00:00:28,000 --> 00:00:31,000
A pénztáros ezután felváltva szolgálja az ügyfelek az első,

12
00:00:31,000 --> 00:00:34,000
aki aztán kilép a vonalon egy időben.

13
00:00:34,000 --> 00:00:37,000
A számítógép-tudomány, utalunk az első a sorban, mint a fej

14
00:00:37,000 --> 00:00:39,000
és a hátsó, mint a farok.

15
00:00:39,000 --> 00:00:41,000
Egy példa, amikor talán ezt egy alkalmazásban

16
00:00:41,000 --> 00:00:44,000
a várólista osztály beiratkozást.

17
00:00:44,000 --> 00:00:46,000
Mivel a helyek válnak elérhetővé az osztályban,

18
00:00:46,000 --> 00:00:50,000
az a személy, az élén a várakozási lista lehetőséget biztosított, hogy beiratkozik az osztályban.

19
00:00:50,000 --> 00:00:53,000
>> A sort lehet kialakítani bármilyen gyűjtemény

20
00:00:53,000 --> 00:00:57,000
hogy tárolja az adatokat annak érdekében, mint például a tömb vagy egy láncolt lista.

21
00:00:57,000 --> 00:01:00,000
Együtt a gyűjtemény tárolni az elemeket a sorban,

22
00:01:00,000 --> 00:01:02,000
azt is meg kell egy módszert hozzá elem a végén a sor,

23
00:01:02,000 --> 00:01:04,000
amely az úgynevezett enqueuing,

24
00:01:04,000 --> 00:01:07,000
és egy másik, hogy távolítsa el egy elemet a fejét a sorban,

25
00:01:07,000 --> 00:01:09,000
amely az úgynevezett dequeuing.

26
00:01:09,000 --> 00:01:14,000
Gyakran hasznos fel más módszert, hogy visszatérjen a jelenlegi hossza a sorban

27
00:01:14,000 --> 00:01:17,000
valamint egy módszer annak ellenőrzésére, a sor üres.

28
00:01:17,000 --> 00:01:20,000
Nézzük meg, hogyan lehet végrehajtani a sorban Egész számok C,

29
00:01:20,000 --> 00:01:23,000
használ egy tömböt gyűjtésére elemeket.

30
00:01:23,000 --> 00:01:27,000
Először is, hozzon létre egy struktúrát nevű sorban, hogy tartsa meg a változókat.

31
00:01:27,000 --> 00:01:30,000
Fogjuk használni egy fix méretű tömb indexe 0 egészek

32
00:01:30,000 --> 00:01:33,000
tárolni az elemeknek.

33
00:01:33,000 --> 00:01:35,000
Mi is egy változó nevű fej

34
00:01:35,000 --> 00:01:39,000
amely tárolja az index az elem, hogy a jelenleg a fejét a sorban.

35
00:01:39,000 --> 00:01:42,000
Egy harmadik változó, úgynevezett hosszúságú, lesz használva

36
00:01:42,000 --> 00:01:45,000
nyomon követni az elemek száma a tömbben.

37
00:01:45,000 --> 00:01:48,000
Ennek alternatívájaként, akkor fontolja meg a változó nevű farok

38
00:01:48,000 --> 00:01:51,000
pont az utolsó field elem a tömbben.

39
00:01:51,000 --> 00:01:53,000
Mielőtt írni többé kódot,

40
00:01:53,000 --> 00:01:55,000
próbáljuk ki a design.

41
00:01:55,000 --> 00:01:58,000
Kezdjük egy üres tömb hossza 0,

42
00:01:58,000 --> 00:02:02,000
a fej 0-ra.

43
00:02:02,000 --> 00:02:11,000
Most sorba állítása 4 értéke - 6, 2, 3, és 1.

44
00:02:11,000 --> 00:02:14,000
A hossza most már 4,

45
00:02:14,000 --> 00:02:17,000
és a fej marad 0 °.

46
00:02:17,000 --> 00:02:20,000
>> Mi történik, ha dequeue érték?

47
00:02:20,000 --> 00:02:24,000
Csökkenteni fogjuk a hossza 3,

48
00:02:24,000 --> 00:02:28,000
állítsa be a fejét, hogy 1,

49
00:02:28,000 --> 00:02:33,000
és vissza az érték 6.

50
00:02:33,000 --> 00:02:36,000
Ez a kód ilyesmi.

51
00:02:36,000 --> 00:02:38,000
Itt van a dequeue funkciót,

52
00:02:38,000 --> 00:02:41,000
amely úgy a mutatót a sorban - q -, és a mutatót az elem,

53
00:02:41,000 --> 00:02:44,000
amely egyfajta int.

54
00:02:44,000 --> 00:02:47,000
Először is ellenőrizze a hossza a sorban, hogy megbizonyosodjon arról, hogy ez több, mint 0,

55
00:02:47,000 --> 00:02:50,000
annak érdekében, hogy van egy elemét lehessen úgy dequeued.

56
00:02:50,000 --> 00:02:54,000
Akkor nézze meg a tömb elemeit, a helyzet fejét,

57
00:02:54,000 --> 00:02:58,000
és állítsa be az értéket az elem, hogy az érték az adott helyzetben.

58
00:02:58,000 --> 00:03:01,000
Ezután módosítsa a fejét, hogy a következő index

59
00:03:01,000 --> 00:03:04,000
%-A kapacitás.

60
00:03:04,000 --> 00:03:07,000
Ezután csökkenti a hosszát a sor 1-gyel.

61
00:03:07,000 --> 00:03:12,000
Végül vissza, jelezve, hogy igaz az dequeue volt sikeres.

62
00:03:12,000 --> 00:03:19,000
Ha dequeue ismét, a hossz válik 2,

63
00:03:19,000 --> 00:03:24,000
a fej is lesz 2,

64
00:03:24,000 --> 00:03:32,000
és a visszatérési érték lesz 2.

65
00:03:32,000 --> 00:03:35,000
>> Mi történik, ha sorba állításához más érték, mint a 7?

66
00:03:35,000 --> 00:03:37,000
Mint voltunk végén a sor,

67
00:03:37,000 --> 00:03:47,000
meg kell köré és tárolja az értéket 0 elem a tömbben.

68
00:03:47,000 --> 00:03:50,000
Matematikailag ez képviseli hozzáadásával hossz

69
00:03:50,000 --> 00:03:52,000
Az index a fej

70
00:03:52,000 --> 00:03:55,000
végző és modulus segítségével queue kapacitást.

71
00:03:55,000 --> 00:04:00,000
Itt, hogy a 2 +2, ami 4% 4,

72
00:04:00,000 --> 00:04:02,000
amely jelentése 0.

73
00:04:02,000 --> 00:04:05,000
Fordítás ezt a gondolatot kódot, rendelkezik ezzel a funkcióval.

74
00:04:05,000 --> 00:04:08,000
Itt látjuk a sorba állítása funkció

75
00:04:08,000 --> 00:04:10,000
amely úgy a mutatót a sorban - q -

76
00:04:10,000 --> 00:04:14,000
és úgy az elemét lehessen úgy enqueued, ami egy egész szám.

77
00:04:14,000 --> 00:04:18,000
Mi mellett ellenőrizze, hogy győződjön meg arról, hogy a kapacitás a sor

78
00:04:18,000 --> 00:04:21,000
még mindig nagyobb, mint a jelenlegi hossza a sorban.

79
00:04:21,000 --> 00:04:24,000
Következő, tárolunk az elem elemeiben tömb

80
00:04:24,000 --> 00:04:30,000
az index határozza meg a fej + hossz%-kapacitása a sorban.

81
00:04:30,000 --> 00:04:33,000
Ezután növelje a queue hossza 1,

82
00:04:33,000 --> 00:04:39,000
majd a return true, jelezve, hogy a sorba állítása funkció sikeres volt.

83
00:04:39,000 --> 00:04:42,000
>> Amellett, hogy a két funkció általunk említettük,

84
00:04:42,000 --> 00:04:44,000
két további funkciókat.

85
00:04:44,000 --> 00:04:46,000
Először is a IsEmpty funkció,

86
00:04:46,000 --> 00:04:48,000
amely úgy a mutatót a sorban

87
00:04:48,000 --> 00:04:51,000
és ellenőrzi, hogy a hossza 0.

88
00:04:51,000 --> 00:04:53,000
A második a hossz funkció,

89
00:04:53,000 --> 00:04:55,000
is vesz egy mutatót a sorban

90
00:04:55,000 --> 00:04:58,000
és visszaadja az aktuális hossza a struct.

91
00:04:58,000 --> 00:05:03,000
Ez a rövid áttekintés bebizonyította egyik lehetséges megvalósítása sorban.

92
00:05:03,000 --> 00:05:06,000
Az egyik a korlátait, a végrehajtás

93
00:05:06,000 --> 00:05:08,000
az, hogy a sorban van egy rögzített maximális méretet.

94
00:05:08,000 --> 00:05:11,000
Ha megpróbáljuk, hogy adjunk több elem, mint a sorba fér,

95
00:05:11,000 --> 00:05:14,000
szükség lehet arra, hogy figyelmen kívül hagyja a kérést, és dobja az elemet,

96
00:05:14,000 --> 00:05:17,000
vagy talán inkább vissza valamilyen hiba.

97
00:05:17,000 --> 00:05:20,000
Egy láncolt lista helyett egy tömböt

98
00:05:20,000 --> 00:05:22,000
lehetővé tenné, hogy dinamikusan méret a sorban.

99
00:05:22,000 --> 00:05:26,000
Azonban, mivel nem rendelkeznek közvetlen hozzáféréssel a elemeit láncolt lista,

100
00:05:26,000 --> 00:05:28,000
ha nem tartjuk számon a farok,

101
00:05:28,000 --> 00:05:32,000
mi lett volna, hogy átvizsgálja a teljes láncolt lista, hogy a végén minden alkalommal.

102
00:05:32,000 --> 00:05:35,000
Azt is fontolja meg egy sor más adattípusok,

103
00:05:35,000 --> 00:05:39,000
mint például a struktúrákat, hogy hozzon létre sorok bonyolultabb elemeket.

104
00:05:39,000 --> 00:05:42,000
Gondolkodás vissza az például egy osztály várólista,

105
00:05:42,000 --> 00:05:45,000
ezek a struktúrák jelenthet az egyéni versenyző.

106
00:05:45,000 --> 00:05:48,000
>> A nevem Chris Gerber, és ez CS50.

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

108
00:05:51,000 --> 00:05:55,000
És visszatér - >> Mégegyszer.

109
00:05:55,000 --> 00:06:00,000
És return true azt jelzi, hogy - a sorban sikeres volt.

110
00:06:00,000 --> 00:06:03,000
-% A kapacitás a sor -

111
00:06:03,000 --> 00:06:06,000
Ez lesz szórakoztató a szerkesztés. [Nevetés]