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

2
00:00:02,000 --> 00:00:05,000
[Chris Gerber, Universiteti i Harvardit]

3
00:00:05,000 --> 00:00:07,000
Kjo është CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Një strukturë e dobishme për ruajtjen e të dhënave një koleksion urdhëruar të elementeve është një radhë.

5
00:00:11,000 --> 00:00:14,000
Ajo është përdorur kur elemente duhet të hiqen

6
00:00:14,000 --> 00:00:16,000
në të njëjtën mënyrë si ata janë shtuar.

7
00:00:16,000 --> 00:00:20,000
Ky koncept është përmendur si FIFO, e cila është një akronim për të parë në, së pari jashtë.

8
00:00:20,000 --> 00:00:23,000
Për të ndihmuar kujtoj këtë, ajo mund të jetë e dobishme për fotografinë

9
00:00:23,000 --> 00:00:25,000
një linjë arka në një dyqan.

10
00:00:25,000 --> 00:00:28,000
Ndërsa njerëzit arrijnë, ata presin në pjesën e pasme të linjës.

11
00:00:28,000 --> 00:00:31,000
Me turp pastaj merr kthehet duke shërbyer klientëve në pjesën e përparme,

12
00:00:31,000 --> 00:00:34,000
të cilët pastaj të dalë nga një linjë në një kohë.

13
00:00:34,000 --> 00:00:37,000
Në shkenca kompjuterike, ne i referohemi frontin e radhës si kryetar

14
00:00:37,000 --> 00:00:39,000
dhe prapa si bisht.

15
00:00:39,000 --> 00:00:41,000
Një shembull i kur ne mund të përdorin këtë në një aplikim

16
00:00:41,000 --> 00:00:44,000
është një waitlist për regjistruarve klasës.

17
00:00:44,000 --> 00:00:46,000
Si vende të bëhen të disponueshme në klasë,

18
00:00:46,000 --> 00:00:50,000
personi në krye të listës së pritjes është dhënë mundësia të regjistrohen në klasë.

19
00:00:50,000 --> 00:00:53,000
>> Një radhë mund të ndërtohet duke përdorur ndonjë koleksion

20
00:00:53,000 --> 00:00:57,000
që ruan të dhënat në mënyrë, të tilla si një grup ose një listë të lidhura.

21
00:00:57,000 --> 00:01:00,000
Së bashku me mbledhjen për të ruajtur sendet në radhë,

22
00:01:00,000 --> 00:01:02,000
ne gjithashtu nevojë për një metodë për të shtuar artikuj në fund të rreshtit,

23
00:01:02,000 --> 00:01:04,000
cila është e quajtur enqueuing,

24
00:01:04,000 --> 00:01:07,000
dhe një tjetër për të hequr një artikull nga kreu i radhës,

25
00:01:07,000 --> 00:01:09,000
cila është e quajtur dequeuing.

26
00:01:09,000 --> 00:01:14,000
Kjo është shpesh e dobishme për të përfshirë një tjetër metodë për të kthyer gjatësinë aktuale të radhës

27
00:01:14,000 --> 00:01:17,000
si një metodë për të kontrolluar nëse queue është bosh.

28
00:01:17,000 --> 00:01:20,000
Le të shohim se si ne mund të zbatojë një radhë të integers në C,

29
00:01:20,000 --> 00:01:23,000
duke përdorur një rrjet për mbledhjen e elementeve.

30
00:01:23,000 --> 00:01:27,000
Së pari, ne kemi krijuar një strukturë të quajtur radhë për të mbajtur variablave tona.

31
00:01:27,000 --> 00:01:30,000
Ne do të përdorë një fikse-size index grup i integers 0

32
00:01:30,000 --> 00:01:33,000
për të ruajtur elementet.

33
00:01:33,000 --> 00:01:35,000
Ne gjithashtu do të përfshijë një kokë ndryshueshme quajtur

34
00:01:35,000 --> 00:01:39,000
që ruan indeksin e elementit që është aktualisht në krye të rreshtit.

35
00:01:39,000 --> 00:01:42,000
Një variabël i tretë, të quajtur gjatësia, do të përdoret

36
00:01:42,000 --> 00:01:45,000
të mbajnë gjurmët e numrit të elementeve në array.

37
00:01:45,000 --> 00:01:48,000
Si një alternativë, ju mund të konsideroni përdorimin e një bisht ndryshueshme quajtur

38
00:01:48,000 --> 00:01:51,000
për pikë në elementin e fundit në terren në rrjet.

39
00:01:51,000 --> 00:01:53,000
Para se të shkruani kodin më,

40
00:01:53,000 --> 00:01:55,000
le të provoni dizajn tonë.

41
00:01:55,000 --> 00:01:58,000
Le të fillojmë me një grup të zbrazët gjatësi 0,

42
00:01:58,000 --> 00:02:02,000
me kokë të vendosur për të 0.

43
00:02:02,000 --> 00:02:11,000
Tani le të enqueue 4 - 6 vlerat, 2, 3, dhe 1.

44
00:02:11,000 --> 00:02:14,000
Gjatësia tani do të jetë 4,

45
00:02:14,000 --> 00:02:17,000
dhe koka do të qëndrojë në 0.

46
00:02:17,000 --> 00:02:20,000
>> Çfarë ndodh nëse ne dequeue një vlerë?

47
00:02:20,000 --> 00:02:24,000
Ne do të reduktojë kohëzgjatjen deri në 3,

48
00:02:24,000 --> 00:02:28,000
vendosur kokën në 1,

49
00:02:28,000 --> 00:02:33,000
dhe kthimin e vlerës 6.

50
00:02:33,000 --> 00:02:36,000
Se kodi mund të duket si kjo.

51
00:02:36,000 --> 00:02:38,000
Këtu kemi funksionin dequeue,

52
00:02:38,000 --> 00:02:41,000
e cila merr një tregues për radhë - Q - dhe një tregues për elementin,

53
00:02:41,000 --> 00:02:44,000
cila është një int lloj.

54
00:02:44,000 --> 00:02:47,000
Së pari ne kontrolloni kohëzgjatjen e radhës për t'u siguruar se është më shumë se 0,

55
00:02:47,000 --> 00:02:50,000
për të siguruar se ka një element të dequeued.

56
00:02:50,000 --> 00:02:54,000
Pastaj ne shikojmë në grup elementesh, në krye pozicion,

57
00:02:54,000 --> 00:02:58,000
dhe vendosur vlerën e elementit të jetë vlera në atë pozitë.

58
00:02:58,000 --> 00:03:01,000
Pastaj ne të ndryshojë kokën të jetë indeksi tjetër

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

60
00:03:04,000 --> 00:03:07,000
Ne pastaj të zvogëlojë kohëzgjatjen e radhës nga 1.

61
00:03:07,000 --> 00:03:12,000
Së fundi, ne kthim i vërtetë për të treguar se dequeue ishte i suksesshëm.

62
00:03:12,000 --> 00:03:19,000
Nëse ne dequeue përsëri, gjatësia do të bëhet 2,

63
00:03:19,000 --> 00:03:24,000
kreu gjithashtu do të bëhen 2,

64
00:03:24,000 --> 00:03:32,000
dhe vlera e kthimit do të jetë 2.

65
00:03:32,000 --> 00:03:35,000
>> Çfarë ndodh nëse ne enqueue një tjetër vlerë të tilla si një 7?

66
00:03:35,000 --> 00:03:37,000
Si ne ishin në fund të rreshtit,

67
00:03:37,000 --> 00:03:47,000
ne do të duhet për të përfunduar rreth dhe ruajtur vlerën në 0 element të vektorit.

68
00:03:47,000 --> 00:03:50,000
Matematikisht, kjo mund të përfaqësohet nga shtuar gjatësinë

69
00:03:50,000 --> 00:03:52,000
me indeksin e kokës

70
00:03:52,000 --> 00:03:55,000
dhe kryerjen e një modulus duke përdorur kapacitetin radhë.

71
00:03:55,000 --> 00:04:00,000
Këtu që është 2 2, e cila është 4% 4,

72
00:04:00,000 --> 00:04:02,000
cila është 0.

73
00:04:02,000 --> 00:04:05,000
Përkthimi këtë ide të kodit ne kemi këtë funksion.

74
00:04:05,000 --> 00:04:08,000
Këtu ne shohim funksionin enqueue,

75
00:04:08,000 --> 00:04:10,000
e cila merr një tregues për radhë - Q -

76
00:04:10,000 --> 00:04:14,000
dhe merr elementi të enqueued, e cila është një numër i plotë.

77
00:04:14,000 --> 00:04:18,000
Ne ardhshëm kontrolloni për t'u siguruar se kapaciteti i radhës

78
00:04:18,000 --> 00:04:21,000
është ende më e madhe se gjatësia e tanishme e radhës.

79
00:04:21,000 --> 00:04:24,000
Tjetra, ne dyqan elementin në rrjet elementeve

80
00:04:24,000 --> 00:04:30,000
në indeksin e cila është përcaktuar nga kreu +% gjatësia kapaciteti i radhë.

81
00:04:30,000 --> 00:04:33,000
Ne pastaj të rritur gjatësinë radhë me 1,

82
00:04:33,000 --> 00:04:39,000
dhe pastaj kthehen e vërtetë për të treguar se funksioni enqueue ishte i suksesshëm.

83
00:04:39,000 --> 00:04:42,000
>> Përveç këtyre dy funksioneve që kemi përmendur,

84
00:04:42,000 --> 00:04:44,000
ka dy funksione shtesë.

85
00:04:44,000 --> 00:04:46,000
Së pari është funksioni isempty,

86
00:04:46,000 --> 00:04:48,000
cili merr nje tregues te radhë

87
00:04:48,000 --> 00:04:51,000
dhe verifikon se gjatësia është 0.

88
00:04:51,000 --> 00:04:53,000
E dyta është funksioni gjatësi,

89
00:04:53,000 --> 00:04:55,000
i cili gjithashtu merr një tregues për radhë

90
00:04:55,000 --> 00:04:58,000
dhe kthen gjatësinë aktuale nga struct.

91
00:04:58,000 --> 00:05:03,000
Kjo pasqyrë e shkurtër e ka demonstruar një implementimin e mundshëm të një radhë.

92
00:05:03,000 --> 00:05:06,000
Një nga kufizimet në zbatim të këtij

93
00:05:06,000 --> 00:05:08,000
është se radhë ka një madhësi të caktuar maksimale.

94
00:05:08,000 --> 00:05:11,000
Nëse ne përpiqemi për të shtuar elementet më shumë se sa mund të mbajë radhë,

95
00:05:11,000 --> 00:05:14,000
ne mund të kenë nevojë të injorojë kërkesën dhe të heqë elementin,

96
00:05:14,000 --> 00:05:17,000
ose ne mund të preferojnë të kthehen disa lloj të gabimit.

97
00:05:17,000 --> 00:05:20,000
Duke përdorur një listë e lidhur më tepër se një grup

98
00:05:20,000 --> 00:05:22,000
do ta bënte më të lehtë për madhësi dinamike radhë.

99
00:05:22,000 --> 00:05:26,000
Megjithatë, pasi ne nuk kemi qasje të drejtpërdrejtë në elementet e një liste të lidhura,

100
00:05:26,000 --> 00:05:28,000
në qoftë se ne nuk i mbajnë gjurmët e bisht,

101
00:05:28,000 --> 00:05:32,000
ne do të duhet të scan të gjithë listën lidhur për të marrë në fund çdo kohë.

102
00:05:32,000 --> 00:05:35,000
Ne gjithashtu mund të konsiderojnë duke përdorur një rrjet të një lloji tjetër të të dhënave,

103
00:05:35,000 --> 00:05:39,000
të tilla si structs, për të krijuar rradhë të elementeve më komplekse.

104
00:05:39,000 --> 00:05:42,000
Duke menduar përsëri në shembullin tonë të waitlist klasës,

105
00:05:42,000 --> 00:05:45,000
këto struktura mund të përfaqësojnë studentët individuale.

106
00:05:45,000 --> 00:05:48,000
>> Emri im është Chris Gerber, dhe kjo është CS50.

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

108
00:05:51,000 --> 00:05:55,000
Dhe kthimit - >> Njëri më shumë kohë.

109
00:05:55,000 --> 00:06:00,000
Dhe kthimin e vërtetë për të treguar se - queue ishte i suksesshëm.

110
00:06:00,000 --> 00:06:03,000
-% Kapaciteti i radhës -

111
00:06:03,000 --> 00:06:06,000
Ajo do të jetë kënaqësi në redaktim. [Qeshura]