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

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

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

4
00:00:07,000 --> 00:00:11,000
Jednym z przydatnych struktura danych do przechowywania uporządkowaną kolekcję elementów jest kolejka.

5
00:00:11,000 --> 00:00:14,000
To jest, gdy stosuje się elementy muszą być usunięte

6
00:00:14,000 --> 00:00:16,000
w tej samej kolejności, w jakiej zostały dodane.

7
00:00:16,000 --> 00:00:20,000
Koncepcja ta jest dalej FIFO, co jest skrótem od najpierw, pierwszy na wyjściu.

8
00:00:20,000 --> 00:00:23,000
Aby wyobrazić to może być użyteczne dla obrazu

9
00:00:23,000 --> 00:00:25,000
linia kasy w sklepie.

10
00:00:25,000 --> 00:00:28,000
Jak ludzie przybywają, czekają na końcu linii.

11
00:00:28,000 --> 00:00:31,000
Kasjer następnie bierze zakręty obsługujących klientów z przodu,

12
00:00:31,000 --> 00:00:34,000
którzy następnie opuścić jednej linii na raz.

13
00:00:34,000 --> 00:00:37,000
Informatykę, odwołujemy się do przodu, jak kolejki głowicy

14
00:00:37,000 --> 00:00:39,000
i ponownie w ogonie.

15
00:00:39,000 --> 00:00:41,000
Przykład, gdy może to wykorzystać w zastosowaniu

16
00:00:41,000 --> 00:00:44,000
liście oczekujących jest dla rejestracji klasy.

17
00:00:44,000 --> 00:00:46,000
Jak fotele będą dostępne w klasie,

18
00:00:46,000 --> 00:00:50,000
osób na czele listy oczekujących jest możliwość, aby zapisać się w klasie.

19
00:00:50,000 --> 00:00:53,000
>> Kolejka może być wykonana przy użyciu dowolnej kolekcji

20
00:00:53,000 --> 00:00:57,000
, który przechowuje dane w celu, na przykład w formie tablicy lub liście połączonej.

21
00:00:57,000 --> 00:01:00,000
Wraz z kolekcji do przechowywania elementów w kolejce,

22
00:01:00,000 --> 00:01:02,000
muszą również metodę wprowadzania pozycji na koniec kolejki

23
00:01:02,000 --> 00:01:04,000
który nazywa enqueuing,

24
00:01:04,000 --> 00:01:07,000
a co innego usunąć element z głowy kolejki,

25
00:01:07,000 --> 00:01:09,000
które nazywa się z kolejki.

26
00:01:09,000 --> 00:01:14,000
Często przydatne jest włączenie innej metody zwraca bieżącą długość kolejki

27
00:01:14,000 --> 00:01:17,000
jak również metody, aby sprawdzić, czy kolejka jest pusta.

28
00:01:17,000 --> 00:01:20,000
Przyjrzyjmy się, w jaki sposób możemy zaimplementować kolejkę liczb całkowitych w C,

29
00:01:20,000 --> 00:01:23,000
za pomocą tablicy zbierania elementów.

30
00:01:23,000 --> 00:01:27,000
Po pierwsze, stworzenie struktury o nazwie kolejka trzymać nasze zmienne.

31
00:01:27,000 --> 00:01:30,000
Użyjemy ustalony rozmiar tablicy indeksu 0 liczb całkowitych

32
00:01:30,000 --> 00:01:33,000
do przechowywania elementów.

33
00:01:33,000 --> 00:01:35,000
Zostanie również zmienną głowę

34
00:01:35,000 --> 00:01:39,000
która przechowuje indeks elementu, który jest obecnie na czele kolejki.

35
00:01:39,000 --> 00:01:42,000
Trzecia zmienna, zwany długość, stosowany będzie

36
00:01:42,000 --> 00:01:45,000
aby śledzić liczbę elementów w tablicy.

37
00:01:45,000 --> 00:01:48,000
Jako alternatywę, można rozważyć użycie zmienną ogon

38
00:01:48,000 --> 00:01:51,000
zwrócić się do ostatniego elementu pola w tablicy.

39
00:01:51,000 --> 00:01:53,000
Zanim napiszemy dowolną więcej kodu,

40
00:01:53,000 --> 00:01:55,000
Spróbujmy nasz projekt.

41
00:01:55,000 --> 00:01:58,000
Zacznijmy pustą tablicę o długości 0,

42
00:01:58,000 --> 00:02:02,000
z głową ustawić na 0.

43
00:02:02,000 --> 00:02:11,000
Teraz enqueue 4 wartości - 6, 2, 3, i 1.

44
00:02:11,000 --> 00:02:14,000
Długość będzie teraz 4

45
00:02:14,000 --> 00:02:17,000
i głowa pozostanie na 0.

46
00:02:17,000 --> 00:02:20,000
>> Co się stanie, jeśli usunie z niej wartość?

47
00:02:20,000 --> 00:02:24,000
Będziemy skrócenia do 3,

48
00:02:24,000 --> 00:02:28,000
ustawić głowicę na 1,

49
00:02:28,000 --> 00:02:33,000
i zwrócić wartość 6.

50
00:02:33,000 --> 00:02:36,000
Ten kod może wyglądać tak.

51
00:02:36,000 --> 00:02:38,000
Tutaj mamy rozkolejkowania funkcji

52
00:02:38,000 --> 00:02:41,000
która przyjmuje wskaźnik do kolejki - q - oraz wskaźnik do elementu,

53
00:02:41,000 --> 00:02:44,000
która jest typu int.

54
00:02:44,000 --> 00:02:47,000
Najpierw musimy sprawdzić długość kolejki, aby upewnić się, że to więcej niż 0,

55
00:02:47,000 --> 00:02:50,000
w celu zapewnienia, że ​​jest to element do rozkolejkowywana.

56
00:02:50,000 --> 00:02:54,000
Następnie szukamy w tablicy pierwiastków, na czele pozycji,

57
00:02:54,000 --> 00:02:58,000
i ustawić wartość elementu jest napięcie w tej pozycji.

58
00:02:58,000 --> 00:03:01,000
Następnie zmienić głowę być następnym index

59
00:03:01,000 --> 00:03:04,000
% Pojemności.

60
00:03:04,000 --> 00:03:07,000
Następnie zmniejsza długość kolejki do 1.

61
00:03:07,000 --> 00:03:12,000
Wreszcie, zwraca true wskazuje, że Dequeue pomyślnie.

62
00:03:12,000 --> 00:03:19,000
Jeśli z kolejki ponownie będzie długość 2

63
00:03:19,000 --> 00:03:24,000
głowa stanie się również 2,

64
00:03:24,000 --> 00:03:32,000
zwracana wartość będzie 2.

65
00:03:32,000 --> 00:03:35,000
>> Co się stanie, jeśli enqueue innej wartości takie jak 7?

66
00:03:35,000 --> 00:03:37,000
Jak było na końcu kolejki,

67
00:03:37,000 --> 00:03:47,000
musimy owinąć wokół i przechowywać wartość w 0 element tablicy.

68
00:03:47,000 --> 00:03:50,000
Matematycznie można to reprezentowane przez dodanie długość

69
00:03:50,000 --> 00:03:52,000
wskaźnikowi głowy

70
00:03:52,000 --> 00:03:55,000
i wykonując moduł używając zdolności kolejki.

71
00:03:55,000 --> 00:04:00,000
Tutaj jest 2 +2, która jest o 4% 4

72
00:04:00,000 --> 00:04:02,000
które jest 0.

73
00:04:02,000 --> 00:04:05,000
Przełożenie tego pomysłu do kodu mamy tę funkcję.

74
00:04:05,000 --> 00:04:08,000
Tutaj widzimy Dodaje funkcję,

75
00:04:08,000 --> 00:04:10,000
która przyjmuje wskaźnik do kolejki - Q -

76
00:04:10,000 --> 00:04:14,000
i ma element do kolejkowane, która jest liczbą całkowitą.

77
00:04:14,000 --> 00:04:18,000
Kolejnym upewnij się, że pojemność kolejki

78
00:04:18,000 --> 00:04:21,000
jest w dalszym ciągu większe niż aktualna długość kolejki.

79
00:04:21,000 --> 00:04:24,000
Następnie element przechowywane w tablicy elementów

80
00:04:24,000 --> 00:04:30,000
w którym indeks jest określona przez długość głowicy +% ilość kolejki.

81
00:04:30,000 --> 00:04:33,000
Następnie zwiększyć długość kolejki, 1,

82
00:04:33,000 --> 00:04:39,000
, a następnie powrót do wskazania, że ​​prawdziwe enqueue funkcja zakończyła się pomyślnie.

83
00:04:39,000 --> 00:04:42,000
>> Oprócz tych dwóch funkcji już wspomnieliśmy,

84
00:04:42,000 --> 00:04:44,000
istnieją dwie dodatkowe funkcje.

85
00:04:44,000 --> 00:04:46,000
Pierwszym jest funkcja isempty,

86
00:04:46,000 --> 00:04:48,000
która przyjmuje wskaźnik do kolejki

87
00:04:48,000 --> 00:04:51,000
i sprawdza, czy jest 0 długości.

88
00:04:51,000 --> 00:04:53,000
Drugi jest funkcją długości,

89
00:04:53,000 --> 00:04:55,000
która również ma wskaźnik do kolejki

90
00:04:55,000 --> 00:04:58,000
i zwraca bieżącą długość od struktury.

91
00:04:58,000 --> 00:05:03,000
Ten krótki przegląd wykazał, jedną z możliwych realizacji kolejce.

92
00:05:03,000 --> 00:05:06,000
Jednym z ograniczeń tej realizacji

93
00:05:06,000 --> 00:05:08,000
że kolejka ma stały rozmiar maksymalną.

94
00:05:08,000 --> 00:05:11,000
Jeśli staramy się dodać więcej elementów niż kolejka może pomieścić,

95
00:05:11,000 --> 00:05:14,000
może musimy zignorować żądanie i upuścić element,

96
00:05:14,000 --> 00:05:17,000
lub może wolimy wrócić jakiś rodzaj błędu.

97
00:05:17,000 --> 00:05:20,000
Korzystanie z połączonej listy zamiast tablicy

98
00:05:20,000 --> 00:05:22,000
byłoby łatwiej dynamicznie rozmiaru kolejki.

99
00:05:22,000 --> 00:05:26,000
Jednak, ponieważ nie mamy bezpośredniego dostępu do elementów połączonej listy,

100
00:05:26,000 --> 00:05:28,000
jeśli nie będziemy śledzić ogona,

101
00:05:28,000 --> 00:05:32,000
musielibyśmy skanowanie całego połączonej listy, aby dostać się do końca za każdym razem.

102
00:05:32,000 --> 00:05:35,000
Możemy również rozważyć użycie tablicy inny typ danych,

103
00:05:35,000 --> 00:05:39,000
np. elemencie, do tworzenia elementów kolejki bardziej złożonych.

104
00:05:39,000 --> 00:05:42,000
Wracając do naszego przykładu z listy oczekujących klasy,

105
00:05:42,000 --> 00:05:45,000
Struktury te mogą reprezentować poszczególne studentów.

106
00:05:45,000 --> 00:05:48,000
>> Nazywam się Chris Gerber, i to jest CS50.

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

108
00:05:51,000 --> 00:05:55,000
I powraca - >> Jeszcze raz.

109
00:05:55,000 --> 00:06:00,000
I powrót do wskazania, że ​​prawdziwe - kolejka była sukcesem.

110
00:06:00,000 --> 00:06:03,000
-% Ilość kolejki -

111
00:06:03,000 --> 00:06:06,000
To będzie zabawa w edycji. [Śmiech]