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

2
00:00:02,000 --> 00:00:05,000
[Chris Gerber, Chuo Kikuu cha Harvard]

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

4
00:00:07,000 --> 00:00:11,000
Moja muhimu data muundo kwa ajili ya kuhifadhi ukusanyaji kuamuru wa mambo ni foleni.

5
00:00:11,000 --> 00:00:14,000
Ni kutumika wakati mambo haja kwa kuondolewa

6
00:00:14,000 --> 00:00:16,000
katika utaratibu huo kama wao walikuwa aliongeza.

7
00:00:16,000 --> 00:00:20,000
Dhana hii inajulikana kama FIFO, ambayo ni kifupi kwa kwanza katika, kwanza nje.

8
00:00:20,000 --> 00:00:23,000
Ili kusaidia taswira hii, inaweza kuwa na manufaa kwa picha

9
00:00:23,000 --> 00:00:25,000
Checkout mstari katika kuhifadhi.

10
00:00:25,000 --> 00:00:28,000
Kama watu kufika, wao kusubiri nyuma ya mstari.

11
00:00:28,000 --> 00:00:31,000
cashier kisha anachukua zamu kuwahudumia wateja mbele,

12
00:00:31,000 --> 00:00:34,000
ambaye kisha exit mstari mmoja kwa wakati.

13
00:00:34,000 --> 00:00:37,000
Katika sayansi ya kompyuta, sisi rejea mbele ya foleni kama kichwa

14
00:00:37,000 --> 00:00:39,000
na nyuma kama mkia.

15
00:00:39,000 --> 00:00:41,000
mfano wa wakati sisi wanaweza kutumia hii katika maombi

16
00:00:41,000 --> 00:00:44,000
ni waitlist kwa uandikishaji darasa.

17
00:00:44,000 --> 00:00:46,000
Kama viti kuwa inapatikana katika darasa,

18
00:00:46,000 --> 00:00:50,000
mtu katika kichwa cha orodha ya kusubiri ni fursa ya kujiandikisha katika darasa.

19
00:00:50,000 --> 00:00:53,000
>> foleni inaweza kuwa yalijengwa kwa kutumia yoyote ukusanyaji

20
00:00:53,000 --> 00:00:57,000
kwamba maduka ya data ili, kama vile safu au orodha zilizounganishwa.

21
00:00:57,000 --> 00:01:00,000
Pamoja na ukusanyaji kuhifadhi vitu katika foleni,

22
00:01:00,000 --> 00:01:02,000
tunahitaji pia njia ya kuongeza vitu mwisho wa foleni,

23
00:01:02,000 --> 00:01:04,000
iitwayo enqueuing,

24
00:01:04,000 --> 00:01:07,000
na mwingine kuondoa bidhaa kutoka kichwa ya foleni,

25
00:01:07,000 --> 00:01:09,000
iitwayo dequeuing.

26
00:01:09,000 --> 00:01:14,000
Ni mara nyingi na manufaa kwa pamoja na mbinu nyingine ya kurudi urefu wa sasa wa foleni

27
00:01:14,000 --> 00:01:17,000
kama vile njia ya kuangalia kama foleni ni tupu.

28
00:01:17,000 --> 00:01:20,000
Hebu tuangalie jinsi sisi tupate kutekeleza na foleni ya integers katika C,

29
00:01:20,000 --> 00:01:23,000
kutumia safu kwa ajili ya ukusanyaji wa vipengele.

30
00:01:23,000 --> 00:01:27,000
Kwanza, sisi kujenga muundo kuitwa foleni kushikilia vigezo wetu.

31
00:01:27,000 --> 00:01:30,000
Tutatumia fasta-size 0 index safu ya integers

32
00:01:30,000 --> 00:01:33,000
kuhifadhi mambo.

33
00:01:33,000 --> 00:01:35,000
Sisi pia ni pamoja na kutofautiana kuitwa kichwa

34
00:01:35,000 --> 00:01:39,000
kwamba maduka index ya kipengele kwamba kwa sasa ni mkuu wa foleni.

35
00:01:39,000 --> 00:01:42,000
variable tatu, iitwayo urefu, zitatumika

36
00:01:42,000 --> 00:01:45,000
kuweka wimbo wa idadi ya vipengele katika safu.

37
00:01:45,000 --> 00:01:48,000
Kama mbadala, unaweza kufikiria kutumia variable kuitwa mkia

38
00:01:48,000 --> 00:01:51,000
kwa uhakika na kipengele mwisho shamba katika safu.

39
00:01:51,000 --> 00:01:53,000
Kabla ya sisi kuandika yoyote zaidi ya kificho,

40
00:01:53,000 --> 00:01:55,000
hebu jaribu nje kubuni yetu.

41
00:01:55,000 --> 00:01:58,000
Hebu kuanza na safu ya tupu urefu 0,

42
00:01:58,000 --> 00:02:02,000
pamoja na kichwa kuweka 0.

43
00:02:02,000 --> 00:02:11,000
Sasa hebu enqueue 4 maadili - 6, 2, 3, na 1.

44
00:02:11,000 --> 00:02:14,000
urefu sasa kuwa 4,

45
00:02:14,000 --> 00:02:17,000
na kichwa kukaa katika 0.

46
00:02:17,000 --> 00:02:20,000
>> Nini kinatokea kama sisi dequeue thamani?

47
00:02:20,000 --> 00:02:24,000
Sisi kupunguza urefu wa 3,

48
00:02:24,000 --> 00:02:28,000
kuweka kichwa kwa 1,

49
00:02:28,000 --> 00:02:33,000
na kurudi thamani 6.

50
00:02:33,000 --> 00:02:36,000
Kificho kwamba ili kuangalia kama hii.

51
00:02:36,000 --> 00:02:38,000
Hapa tuna kazi dequeue,

52
00:02:38,000 --> 00:02:41,000
ambayo inachukua pointer foleni - q - na pointer kipengele,

53
00:02:41,000 --> 00:02:44,000
ambayo ni int aina.

54
00:02:44,000 --> 00:02:47,000
Kwanza sisi kuangalia urefu wa foleni kwa kuhakikisha ni zaidi kuliko 0,

55
00:02:47,000 --> 00:02:50,000
kuhakikisha kuwa kuna kipengele kuwa dequeued.

56
00:02:50,000 --> 00:02:54,000
Kisha sisi kuangalia katika safu vipengele katika kichwa nafasi,

57
00:02:54,000 --> 00:02:58,000
na kuweka thamani ya kipengele kuwa thamani katika nafasi hiyo.

58
00:02:58,000 --> 00:03:01,000
Kisha sisi kubadilisha kichwa kuwa index ijayo

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

60
00:03:04,000 --> 00:03:07,000
Sisi basi kupunguza urefu wa foleni kwa 1.

61
00:03:07,000 --> 00:03:12,000
Hatimaye, sisi kurudi kweli zinaonyesha kwamba dequeue ilikuwa na mafanikio.

62
00:03:12,000 --> 00:03:19,000
Kama sisi dequeue tena, urefu watakuwa 2,

63
00:03:19,000 --> 00:03:24,000
kichwa pia kuwa 2,

64
00:03:24,000 --> 00:03:32,000
na thamani ya kurudi itakuwa 2.

65
00:03:32,000 --> 00:03:35,000
>> Nini kinatokea kama sisi enqueue thamani nyingine kama vile 7?

66
00:03:35,000 --> 00:03:37,000
Kama sisi walikuwa katika mwisho wa foleni,

67
00:03:37,000 --> 00:03:47,000
tutahitaji wrap karibu na kuhifadhi thamani katika kipengele 0 wa safu.

68
00:03:47,000 --> 00:03:50,000
Kihisabati, hii inaweza kuwakilishwa na kuongeza urefu

69
00:03:50,000 --> 00:03:52,000
index ya kichwa

70
00:03:52,000 --> 00:03:55,000
na kutekeleza modulus kutumia uwezo foleni.

71
00:03:55,000 --> 00:04:00,000
Hapa kwamba ni 2 2, ambayo ni 4% 4,

72
00:04:00,000 --> 00:04:02,000
ambayo ni 0.

73
00:04:02,000 --> 00:04:05,000
Kutafsiri wazo hili na Kanuni tuna kazi huu.

74
00:04:05,000 --> 00:04:08,000
Hapa tunaona kazi enqueue,

75
00:04:08,000 --> 00:04:10,000
ambayo inachukua pointer foleni - q -

76
00:04:10,000 --> 00:04:14,000
na inachukua kipengele kuwa enqueued, ambayo ni integer.

77
00:04:14,000 --> 00:04:18,000
Sisi ijayo kuangalia kuhakikisha kwamba uwezo wa foleni

78
00:04:18,000 --> 00:04:21,000
bado ni zaidi ya urefu wa sasa wa foleni.

79
00:04:21,000 --> 00:04:24,000
Next, sisi kuhifadhi kipengele katika safu vipengele

80
00:04:24,000 --> 00:04:30,000
katika index ambayo imedhamiria kwa kichwa + urefu% uwezo wa kupanga foleni.

81
00:04:30,000 --> 00:04:33,000
Sisi basi kuongeza urefu foleni kwa 1,

82
00:04:33,000 --> 00:04:39,000
na kisha kurudi kweli zinaonyesha kwamba kazi enqueue ilikuwa na mafanikio.

83
00:04:39,000 --> 00:04:42,000
>> Mbali na kazi mbili tumekuwa zilizotajwa,

84
00:04:42,000 --> 00:04:44,000
kuna kazi mbili za ziada.

85
00:04:44,000 --> 00:04:46,000
Kwanza ni kazi isempty,

86
00:04:46,000 --> 00:04:48,000
ambayo inachukua pointer foleni

87
00:04:48,000 --> 00:04:51,000
na inathibitisha kwamba urefu ni 0.

88
00:04:51,000 --> 00:04:53,000
pili ni kazi urefu,

89
00:04:53,000 --> 00:04:55,000
ambayo pia inachukua pointer foleni

90
00:04:55,000 --> 00:04:58,000
na anarudi urefu wa sasa kutoka struct.

91
00:04:58,000 --> 00:05:03,000
Hii overview mfupi ameonyesha moja iwezekanavyo utekelezaji wa foleni.

92
00:05:03,000 --> 00:05:06,000
Moja ya mapungufu katika utekelezaji huu

93
00:05:06,000 --> 00:05:08,000
ni kwamba foleni ana fasta upeo wa ukubwa.

94
00:05:08,000 --> 00:05:11,000
Kama sisi kujaribu kuongeza vipengele zaidi ya foleni wanaweza kushikilia,

95
00:05:11,000 --> 00:05:14,000
tunaweza kuhitaji kupuuza ombi na kuacha kipengele,

96
00:05:14,000 --> 00:05:17,000
au sisi wanaweza kupendelea kurudi baadhi ya aina ya makosa.

97
00:05:17,000 --> 00:05:20,000
Kutumia orodha wanaohusishwa badala ya safu

98
00:05:20,000 --> 00:05:22,000
ingekuwa rahisi kufanya ukubwa dynamically foleni.

99
00:05:22,000 --> 00:05:26,000
Hata hivyo, tangu hatuna moja kwa moja kupata mambo ya orodha wanaohusishwa,

100
00:05:26,000 --> 00:05:28,000
kama hatuwezi kuweka wimbo wa mkia,

101
00:05:28,000 --> 00:05:32,000
sisi ingekuwa Scan nzima wanaohusishwa orodha ya kupata mwisho kila wakati.

102
00:05:32,000 --> 00:05:35,000
Tunaweza pia kufikiria kutumia safu ya aina nyingine data,

103
00:05:35,000 --> 00:05:39,000
vile kama structs, ili kujenga foleni ya vipengele ngumu zaidi.

104
00:05:39,000 --> 00:05:42,000
Kufikiri nyuma mfano wetu wa waitlist darasa,

105
00:05:42,000 --> 00:05:45,000
miundo hii inaweza kuwakilisha wanafunzi binafsi.

106
00:05:45,000 --> 00:05:48,000
>> Jina langu ni Chris Gerber, na hii ni CS50.

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

108
00:05:51,000 --> 00:05:55,000
Na anarudi - >> Moja muda zaidi.

109
00:05:55,000 --> 00:06:00,000
Na kurudi kweli zinaonyesha kwamba - foleni ilikuwa na mafanikio.

110
00:06:00,000 --> 00:06:03,000
-% Uwezo wa foleni -

111
00:06:03,000 --> 00:06:06,000
Ni kwenda kuwa na furaha katika hariri. [Kicheko]