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

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

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

4
00:00:07,000 --> 00:00:11,000
En nyttig datastruktur til at lagre en ordnet samling af elementer er en kø.

5
00:00:11,000 --> 00:00:14,000
Det anvendes, når elementerne skal fjernes

6
00:00:14,000 --> 00:00:16,000
i samme rækkefølge, som de blev tilsat.

7
00:00:16,000 --> 00:00:20,000
Dette koncept betegnes FIFO, som er en forkortelse for først ind, først ud.

8
00:00:20,000 --> 00:00:23,000
For at hjælpe visualisere dette, kan det være nyttigt at billede

9
00:00:23,000 --> 00:00:25,000
en checkout linje i en butik.

10
00:00:25,000 --> 00:00:28,000
Som folk ankommer, de venter på bagsiden af ​​linjen.

11
00:00:28,000 --> 00:00:31,000
Kassereren tager derefter skiftes betjener kunderne ved fronten,

12
00:00:31,000 --> 00:00:34,000
der derefter afslutte linien én ad gangen.

13
00:00:34,000 --> 00:00:37,000
I datalogi, henviser vi til den forrest i køen som leder

14
00:00:37,000 --> 00:00:39,000
og tilbage som halen.

15
00:00:39,000 --> 00:00:41,000
Et eksempel på, hvornår vi kan bruge dette i en ansøgning

16
00:00:41,000 --> 00:00:44,000
er en venteliste for klasse tilmeldinger.

17
00:00:44,000 --> 00:00:46,000
Som pladser bliver tilgængelige i klassen,

18
00:00:46,000 --> 00:00:50,000
personen i spidsen for ventelisten gives mulighed for at tilmelde dig i klassen.

19
00:00:50,000 --> 00:00:53,000
>> En kø kan konstrueres ved hjælp af en samling

20
00:00:53,000 --> 00:00:57,000
der gemmer data for, såsom en matrix eller en forbundet liste.

21
00:00:57,000 --> 00:01:00,000
Sammen med indsamlingen til at gemme elementerne i køen,

22
00:01:00,000 --> 00:01:02,000
vi også brug for en metode til at tilføje elementer i slutningen af ​​køen,

23
00:01:02,000 --> 00:01:04,000
som kaldes enqueuing,

24
00:01:04,000 --> 00:01:07,000
og en anden for at fjerne et element fra forrest i køen,

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

26
00:01:09,000 --> 00:01:14,000
Er det ofte nyttigt at inkludere en anden metode til at returnere den aktuelle længde af køen

27
00:01:14,000 --> 00:01:17,000
såvel som en metode til at kontrollere, om køen er tom.

28
00:01:17,000 --> 00:01:20,000
Lad os se på, hvordan vi kan gennemføre en kø af heltal i C,

29
00:01:20,000 --> 00:01:23,000
anvendelse af et array til indsamling af elementer.

30
00:01:23,000 --> 00:01:27,000
Først skaber vi en struktur kaldet kø for at holde vores variabler.

31
00:01:27,000 --> 00:01:30,000
Vi vil bruge en fast størrelse 0 indeks vifte af heltal

32
00:01:30,000 --> 00:01:33,000
at lagre elementerne.

33
00:01:33,000 --> 00:01:35,000
Vi vil også indeholde en variabel kaldet hoved

34
00:01:35,000 --> 00:01:39,000
der gemmer indekset for det element, der er i øjeblikket i spidsen af ​​køen.

35
00:01:39,000 --> 00:01:42,000
En tredje variabel, benævnt længde, blive anvendt

36
00:01:42,000 --> 00:01:45,000
at holde styr på antallet af elementer i arrayet.

37
00:01:45,000 --> 00:01:48,000
Som et alternativ, kan du overveje at bruge en variabel kaldet hale

38
00:01:48,000 --> 00:01:51,000
at pege på det sidste felt element i grupperingen.

39
00:01:51,000 --> 00:01:53,000
Før vi skrive noget mere kode,

40
00:01:53,000 --> 00:01:55,000
lad os prøve vores design.

41
00:01:55,000 --> 00:01:58,000
Lad os starte med et tomt array af længde 0,

42
00:01:58,000 --> 00:02:02,000
med hovedet på 0.

43
00:02:02,000 --> 00:02:11,000
Lad os nu enqueue 4 værdier - 6, 2, 3 og 1.

44
00:02:11,000 --> 00:02:14,000
Længden vil nu være 4,

45
00:02:14,000 --> 00:02:17,000
og hovedet vil bo på 0.

46
00:02:17,000 --> 00:02:20,000
>> Hvad sker der, hvis vi dequeue en værdi?

47
00:02:20,000 --> 00:02:24,000
Vi vil reducere længden til 3,

48
00:02:24,000 --> 00:02:28,000
indstille dyr til 1,

49
00:02:28,000 --> 00:02:33,000
og returnere værdien 6.

50
00:02:33,000 --> 00:02:36,000
Denne kode kan se sådan ud.

51
00:02:36,000 --> 00:02:38,000
Her har vi den dequeue funktion,

52
00:02:38,000 --> 00:02:41,000
som tager en pointer til køen - q - og en pointer til elementet,

53
00:02:41,000 --> 00:02:44,000
som er en type int.

54
00:02:44,000 --> 00:02:47,000
Først skal vi kontrollere længden af ​​køen til at sikre, at det er mere end 0,

55
00:02:47,000 --> 00:02:50,000
at sikre, at der er et element, der skal dequeued.

56
00:02:50,000 --> 00:02:54,000
Så vi ser i elementerne array, ved positionen hoved,

57
00:02:54,000 --> 00:02:58,000
og sætte værdien af ​​elementet at være værdien på denne position.

58
00:02:58,000 --> 00:03:01,000
Så skifter vi hovedet til at være den næste indeks

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

60
00:03:04,000 --> 00:03:07,000
Vi derefter reducere længden af ​​køen med 1.

61
00:03:07,000 --> 00:03:12,000
Endelig vi vender tilbage korrekt at angive, at dequeue lykkedes.

62
00:03:12,000 --> 00:03:19,000
Hvis vi dequeue igen, vil længden blive 2,

63
00:03:19,000 --> 00:03:24,000
Hovedet vil også blive 2,

64
00:03:24,000 --> 00:03:32,000
og afkastet værdi vil være 2.

65
00:03:32,000 --> 00:03:35,000
>> Hvad sker der, hvis vi sætte mellemlager anden værdi, såsom en 7?

66
00:03:35,000 --> 00:03:37,000
Da vi var i slutningen af ​​køen,

67
00:03:37,000 --> 00:03:47,000
vi bliver nødt til at vikle rundt og gemme værdien i element 0 i arrayet.

68
00:03:47,000 --> 00:03:50,000
Matematisk kan dette repræsenteres ved tilsætning af længden

69
00:03:50,000 --> 00:03:52,000
til indekset af hovedet

70
00:03:52,000 --> 00:03:55,000
og udførelse af en modul ved hjælp af køen kapacitet.

71
00:03:55,000 --> 00:04:00,000
Her, er 2 +2, hvilket er 4% 4,

72
00:04:00,000 --> 00:04:02,000
som er 0.

73
00:04:02,000 --> 00:04:05,000
Omsætte denne idé til at kode vi har denne funktion.

74
00:04:05,000 --> 00:04:08,000
Her ser vi den enqueue funktion,

75
00:04:08,000 --> 00:04:10,000
som tager en pointer til køen - q -

76
00:04:10,000 --> 00:04:14,000
og tager elementet, der skal enqueued, hvilket er et helt tal.

77
00:04:14,000 --> 00:04:18,000
Vi næste tjek for at sikre, at kapaciteten af ​​køen

78
00:04:18,000 --> 00:04:21,000
stadig større end den aktuelle længde af køen.

79
00:04:21,000 --> 00:04:24,000
Næste, vi gemmer elementet i elementerne arrayet

80
00:04:24,000 --> 00:04:30,000
ved indeks, der bestemmes af hovedet + længde% kapacitet køen.

81
00:04:30,000 --> 00:04:33,000
Vi derefter øge kølængde med 1,

82
00:04:33,000 --> 00:04:39,000
og derefter returnere rigtigt at angive, at enqueue funktion var vellykket.

83
00:04:39,000 --> 00:04:42,000
>> Ud over de to funktioner vi har nævnt,

84
00:04:42,000 --> 00:04:44,000
der er to ekstra funktioner.

85
00:04:44,000 --> 00:04:46,000
Først er det isempty funktion,

86
00:04:46,000 --> 00:04:48,000
som tager en pointer til køen

87
00:04:48,000 --> 00:04:51,000
og kontrollerer, at længden er 0.

88
00:04:51,000 --> 00:04:53,000
Det andet er længden funktion,

89
00:04:53,000 --> 00:04:55,000
som også tager en pointer til køen

90
00:04:55,000 --> 00:04:58,000
og returnerer den aktuelle længde fra struct.

91
00:04:58,000 --> 00:05:03,000
Denne korte oversigt har vist en mulig implementering af en kø.

92
00:05:03,000 --> 00:05:06,000
En af begrænsningerne for denne implementering

93
00:05:06,000 --> 00:05:08,000
er, at køen har en fast maksimal størrelse.

94
00:05:08,000 --> 00:05:11,000
Hvis vi forsøger at tilføje flere elementer end køen kan rumme,

95
00:05:11,000 --> 00:05:14,000
vi måske nødt til at ignorere anmodningen og slip elementet,

96
00:05:14,000 --> 00:05:17,000
eller vi måske foretrækker at returnere nogle type fejl.

97
00:05:17,000 --> 00:05:20,000
Ved hjælp af en sammenkædet liste ikke et array

98
00:05:20,000 --> 00:05:22,000
ville gøre det nemmere at dynamisk størrelse køen.

99
00:05:22,000 --> 00:05:26,000
Men da vi ikke har direkte adgang til elementerne i en linket liste,

100
00:05:26,000 --> 00:05:28,000
hvis vi ikke holde styr på halen,

101
00:05:28,000 --> 00:05:32,000
vi ville have til at scanne hele linkede liste for at komme til slutningen hver gang.

102
00:05:32,000 --> 00:05:35,000
Vi kunne også overveje at bruge et array af en anden datatype,

103
00:05:35,000 --> 00:05:39,000
såsom struct, at skabe køer af mere komplekse dele.

104
00:05:39,000 --> 00:05:42,000
Tænker tilbage til vores eksempel på en klasse venteliste

105
00:05:42,000 --> 00:05:45,000
disse strukturer kunne repræsentere den enkelte studerende.

106
00:05:45,000 --> 00:05:48,000
>> Mit navn er Chris Gerber, og dette er CS50.

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

108
00:05:51,000 --> 00:05:55,000
Og afkast - >> en gang mere.

109
00:05:55,000 --> 00:06:00,000
Og returnere sandt at indikere, at - køen var vellykket.

110
00:06:00,000 --> 00:06:03,000
-% Kapacitet køen -

111
00:06:03,000 --> 00:06:06,000
Det bliver sjovt i redigeringstilstand. [Latter]