1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Раздел 6: менее комфортно]

2
00:00:02,730 --> 00:00:05,040
[Nate Хардисон] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[Это CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Хорошо. Добро пожаловать в раздел 6.

5
00:00:11,840 --> 00:00:14,690
На этой неделе мы собираемся говорить о структурах данных в разделе

6
00:00:14,690 --> 00:00:19,780
в первую очередь потому, что проблема на этой неделе установлены на spellr

7
00:00:19,780 --> 00:00:24,410
делает целый букет различных исследований структуры данных.

8
00:00:24,410 --> 00:00:26,520
Есть множество различных способов, вы можете пойти с проблемой набора,

9
00:00:26,520 --> 00:00:31,570
и более структур данных вы знаете о, тем больше интересных вещей можно сделать.

10
00:00:31,570 --> 00:00:34,990
>> Итак, давайте начнем. Сначала мы поговорим о стеки,

11
00:00:34,990 --> 00:00:37,530
стека и очереди структур данных, которые мы собираемся поговорить.

12
00:00:37,530 --> 00:00:40,560
Стеки и очереди действительно полезны, когда мы начинаем говорить о графиках,

13
00:00:40,560 --> 00:00:44,390
которые мы не собираемся делать так много сейчас.

14
00:00:44,390 --> 00:00:52,820
Но они очень хорошо понимают одной из крупных фундаментальных структур данных CS.

15
00:00:52,820 --> 00:00:54,880
Описание в спецификации поставленной задачи,

16
00:00:54,880 --> 00:00:59,260
если вы потяните его вверх, говорит о стеки сродни

17
00:00:59,260 --> 00:01:05,239
Куча столовой лотки, которые у вас есть в столовой за обеденным залам

18
00:01:05,239 --> 00:01:09,680
где, когда обеденный персонал приходит и ставит столовой лотков после они очищают их,

19
00:01:09,680 --> 00:01:12,000
они складывают их одна на другую.

20
00:01:12,000 --> 00:01:15,050
А потом, когда дети приходят, чтобы получить пищу,

21
00:01:15,050 --> 00:01:19,490
они тянут с лотков, сначала верхнюю, а затем один ниже его, то тот, что ниже.

22
00:01:19,490 --> 00:01:25,190
Так что, по сути, первый лоток, обеденный персонал положил является последней, которая получает сняты.

23
00:01:25,190 --> 00:01:32,330
Последним, что сотрудники столовой поставить на первое один, который получает сняты на ужин.

24
00:01:32,330 --> 00:01:38,100
В спецификации поставленной задачи, которые вы можете скачать, если вы этого еще не сделали,

25
00:01:38,100 --> 00:01:46,730
мы говорим о моделировании stucture стека данных с помощью такой структуры.

26
00:01:46,730 --> 00:01:51,070
>> Итак, что мы имеем здесь, это похоже на то, что была представлена ​​в лекции,

27
00:01:51,070 --> 00:01:58,120
кроме лекции мы представили это с целыми, а не символ * с.

28
00:01:58,120 --> 00:02:06,250
Это будет стек, который хранит и что?

29
00:02:06,250 --> 00:02:09,009
Дэниел? Что мы хранению в этом стеке?

30
00:02:09,009 --> 00:02:15,260
[Даниил] строк? >> Мы хранения строк в этом стеке, это точно.

31
00:02:15,260 --> 00:02:20,950
Все, что вам нужно иметь для того, чтобы создать стек представляет собой массив

32
00:02:20,950 --> 00:02:23,920
конкретной мощности, которая в данном случае,

33
00:02:23,920 --> 00:02:28,020
мощности будет во всех заглавных буквах, потому что это постоянно.

34
00:02:28,020 --> 00:02:36,340
И тогда в дополнение к массиву, все мы должны отслеживать это текущий размер массива.

35
00:02:36,340 --> 00:02:38,980
Одна вещь, чтобы отметить здесь, что это круто

36
00:02:38,980 --> 00:02:47,060
является то, что мы создаем сложены структуры данных на другую структуру данных, массив.

37
00:02:47,060 --> 00:02:50,110
Существуют различные способы реализации стеков.

38
00:02:50,110 --> 00:02:54,250
Мы не будем делать этого совсем еще, но, надеюсь, после выполнения связанного списка проблем,

39
00:02:54,250 --> 00:03:00,520
Вы увидите, как вы можете легко реализовать стек поверх связанного списка, а также.

40
00:03:00,520 --> 00:03:02,640
Но сейчас, мы будем придерживаться массивов.

41
00:03:02,640 --> 00:03:06,350
Итак, еще раз, все что нам нужно это массив, и мы просто необходимо отслеживать размер массива.

42
00:03:06,350 --> 00:03:09,850
[Сэм] Извините, почему это, что вы сказали, что стек находится на вершине строки?

43
00:03:09,850 --> 00:03:13,440
Мне кажется, что строки в стеке.

44
00:03:13,440 --> 00:03:16,790
[Хардисон] Да. Мы создаем, мы берем наш массив структуры данных -

45
00:03:16,790 --> 00:03:22,130
это большой вопрос. Таким образом, вопрос, почему, для людей, которые наблюдают за этим в Интернете,

46
00:03:22,130 --> 00:03:24,140
Поэтому мы говорим, что стек в верхней части строки,

47
00:03:24,140 --> 00:03:27,990
потому что здесь она выглядит как строки внутри стека?

48
00:03:27,990 --> 00:03:31,050
Который полностью деле.

49
00:03:31,050 --> 00:03:34,660
То, что я имел в виду, что у нас есть структуры массива данных.

50
00:03:34,660 --> 00:03:39,290
У нас есть массив символов * с, это массив строк,

51
00:03:39,290 --> 00:03:45,300
и мы собираемся добавить к этому, чтобы создать стек структуры данных.

52
00:03:45,300 --> 00:03:48,620
>> Таким образом, стек немного более сложным, чем массив.

53
00:03:48,620 --> 00:03:51,890
Мы можем использовать массив для создания стека.

54
00:03:51,890 --> 00:03:55,810
Так вот, когда мы говорим, что стек построен на вершине массива.

55
00:03:55,810 --> 00:04:02,510
Точно так же, как я сказал ранее, мы можем построить стек на начало связанного списка.

56
00:04:02,510 --> 00:04:04,960
Вместо того чтобы использовать массив для хранения наших элементы,

57
00:04:04,960 --> 00:04:10,070
мы могли бы использовать связанный список для хранения наших элементы и построить стек вокруг этого.

58
00:04:10,070 --> 00:04:12,420
Давайте рассмотрим несколько примеров, глядя на код,

59
00:04:12,420 --> 00:04:14,960
чтобы увидеть, что на самом деле здесь происходит.

60
00:04:14,960 --> 00:04:23,400
На левом, я бросил, что это стек структура будет выглядеть в памяти

61
00:04:23,400 --> 00:04:28,330
если емкость была # определяется как четыре.

62
00:04:28,330 --> 00:04:33,490
У нас есть наши четыре элемента массив символов *.

63
00:04:33,490 --> 00:04:38,110
У нас есть строки [0], строк [1], строк [2], струны [3],

64
00:04:38,110 --> 00:04:43,800
а затем, что в прошлом пространство для нашего размера целого числа.

65
00:04:43,800 --> 00:04:46,270
Имеет ли это смысл? Хорошо.

66
00:04:46,270 --> 00:04:48,790
Это то, что произойдет, если то, что я делаю на правую,

67
00:04:48,790 --> 00:04:55,790
который будет свой код, это просто объявить структуру, сложены структура называется с.

68
00:04:55,790 --> 00:05:01,270
Это то, что мы получаем. Она устанавливает этот след в памяти.

69
00:05:01,270 --> 00:05:05,590
Первый вопрос, вот то, что является содержанием этого стека структуры?

70
00:05:05,590 --> 00:05:09,250
Сейчас они ничего, но они не вполне ничего.

71
00:05:09,250 --> 00:05:13,300
Они такого мусора. Мы понятия не имеем, что в них.

72
00:05:13,300 --> 00:05:17,000
Когда мы объявляем стек S, мы просто бросали вниз, что в верхней части памяти.

73
00:05:17,000 --> 00:05:19,840
Это вроде как объявление Int я, а не его инициализации.

74
00:05:19,840 --> 00:05:21,730
Вы не знаете, что там. Вы можете прочитать, что там,

75
00:05:21,730 --> 00:05:27,690
но она не может быть супер полезным.

76
00:05:27,690 --> 00:05:32,680
Одна вещь, которую вы хотите всегда помнить, чтобы сделать это инициализировать все, что необходимо инициализировать.

77
00:05:32,680 --> 00:05:35,820
В этом случае, мы собираемся, чтобы инициализировать размер равным нулю,

78
00:05:35,820 --> 00:05:39,960
потому что это обернется очень важно для нас.

79
00:05:39,960 --> 00:05:43,450
Мы могли бы пойти дальше и инициализировать все указатели, все символ S *

80
00:05:43,450 --> 00:05:49,670
чтобы быть понятными некоторые значения, вероятно, нулевой.

81
00:05:49,670 --> 00:05:58,270
Но это не совершенно необходимо, чтобы мы это делаем.

82
00:05:58,270 --> 00:06:04,200
>> Теперь две основные операции по стеки?

83
00:06:04,200 --> 00:06:07,610
Кто-нибудь помнит из лекции, что вы делаете со стеками? Да?

84
00:06:07,610 --> 00:06:09,700
[Stella] Нажатие и хлопать? >> Именно так.

85
00:06:09,700 --> 00:06:13,810
Нажатие и появляются две основные операции по стеки.

86
00:06:13,810 --> 00:06:17,060
И что же толчок делать? >> Это ставит что-то на верхнем

87
00:06:17,060 --> 00:06:19,300
из стека, а затем хлопок снимает его.

88
00:06:19,300 --> 00:06:23,150
[Хардисон] Именно так. Таким образом, нажав толкает что-то на вершине стека.

89
00:06:23,150 --> 00:06:27,700
Это похоже на столовую персонала положить столовую поднос на столе.

90
00:06:27,700 --> 00:06:33,630
И появляются принимает столовой лоток из стека.

91
00:06:33,630 --> 00:06:36,460
Давайте рассмотрим несколько примеров того, что происходит

92
00:06:36,460 --> 00:06:39,720
Когда мы толкать вещи в стек.

93
00:06:39,720 --> 00:06:45,110
Если бы мы были нажать на строку "привет" на наш стек,

94
00:06:45,110 --> 00:06:49,760
это то, что наша схема будет выглядеть сейчас.

95
00:06:49,760 --> 00:06:53,410
Посмотрите, что происходит?

96
00:06:53,410 --> 00:06:56,530
Мы выдвинули на первый элемент нашего массива строк

97
00:06:56,530 --> 00:07:01,420
и мы увеличили количество наших размером равным 1.

98
00:07:01,420 --> 00:07:05,340
Таким образом, если мы посмотрим на разницу между двумя горками, здесь был 0, то вот перед толчком.

99
00:07:05,340 --> 00:07:08,690
Вот после толчка.

100
00:07:08,690 --> 00:07:13,460
Перед нажатием, после толчка.

101
00:07:13,460 --> 00:07:16,860
И теперь у нас есть один элемент в нашем стеке.

102
00:07:16,860 --> 00:07:20,970
Это строка "привет", и это все.

103
00:07:20,970 --> 00:07:24,440
Все остальное в массиве, на наш массив строк, еще мусор.

104
00:07:24,440 --> 00:07:27,070
Мы не инициализации.

105
00:07:27,070 --> 00:07:29,410
Скажем, мы нажимаем другую строку на наш стек.

106
00:07:29,410 --> 00:07:32,210
Мы собираемся нажать "мир" на этот раз.

107
00:07:32,210 --> 00:07:35,160
Таким образом, вы можете видеть "мир" здесь идет сверху "привет",

108
00:07:35,160 --> 00:07:40,040
и размер отсчет идет до 2.

109
00:07:40,040 --> 00:07:44,520
Теперь мы можем нажать "CS50», и что пойду на вершине снова.

110
00:07:44,520 --> 00:07:51,110
Если мы вернемся, вы можете увидеть, как мы нажатии вещи на вершине стека.

111
00:07:51,110 --> 00:07:53,320
А теперь мы перейдем к поп-музыки.

112
00:07:53,320 --> 00:07:58,910
Когда мы зашли что-то из стека, что случилось?

113
00:07:58,910 --> 00:08:01,540
Никто видите разницу? Это довольно тонкий.

114
00:08:01,540 --> 00:08:05,810
[Студент] размера. >> Да, размер изменился.

115
00:08:05,810 --> 00:08:09,040
>> Что бы вы еще ожидали изменить?

116
00:08:09,040 --> 00:08:14,280
[Студент] строк, тоже. >> Праве. Строк тоже.

117
00:08:14,280 --> 00:08:17,110
Оказывается, что, когда вы делаете это таким образом,

118
00:08:17,110 --> 00:08:21,960
потому что мы не копируя элементы в нашем стеке,

119
00:08:21,960 --> 00:08:24,670
Мы на самом деле не нужно ничего делать, мы можем просто использовать размер

120
00:08:24,670 --> 00:08:28,630
отслеживать количество вещей в нашем массиве

121
00:08:28,630 --> 00:08:33,780
так что, когда мы всплывал снова, снова, мы просто уменьшаем нашу размером до 1.

122
00:08:33,780 --> 00:08:39,440
Там нет необходимости на самом деле пойти и переписать все.

123
00:08:39,440 --> 00:08:41,710
Вид обалденный.

124
00:08:41,710 --> 00:08:46,520
Получается, что мы обычно просто оставить вещи в покое, потому что это меньше работы для нас.

125
00:08:46,520 --> 00:08:50,060
Если мы не должны вернуться и переписать что-то, то зачем это делать?

126
00:08:50,060 --> 00:08:54,150
Поэтому, когда мы дважды всплывал из стека, все, что делает уменьшения размера пару раз.

127
00:08:54,150 --> 00:08:59,120
И опять же, это только потому, что мы не копировать вещи в нашем стеке.

128
00:08:59,120 --> 00:09:01,320
Да? Идем дальше.

129
00:09:01,320 --> 00:09:04,460
[Студент, неразборчиво] >> И что происходит тогда, когда вы нажимаете опять что-то?

130
00:09:04,460 --> 00:09:08,570
Когда вы нажимаете опять что-то, где оно девается?

131
00:09:08,570 --> 00:09:12,390
Куда оно девается, Василий? >> В строки [1]? >> Праве.

132
00:09:12,390 --> 00:09:14,530
Почему они не идут в строки [3]?

133
00:09:14,530 --> 00:09:19,410
[Василий], потому что забыл, что было что-то в строке [1] и [2]?

134
00:09:19,410 --> 00:09:24,040
[Хардисон] Именно так. Наш стек, по сути, "забыл", что он держался за что-то

135
00:09:24,040 --> 00:09:29,480
в строке [1] или строк [2], поэтому, когда мы нажимаем "Woot»,

136
00:09:29,480 --> 00:09:36,670
он просто ставит, что в элемент строки [1].

137
00:09:36,670 --> 00:09:41,590
Есть ли вопросы о том, как это работает, на базовом уровне?

138
00:09:41,590 --> 00:09:45,160
[Сэм] Так что это не динамический в любом случае, с точки зрения количества

139
00:09:45,160 --> 00:09:47,620
или в терминах размера стека?

140
00:09:47,620 --> 00:09:56,750
[Хардисон] Именно так. Это - Дело в том, что это не было динамически growning стека.

141
00:09:56,750 --> 00:10:02,850
Это стека, который может содержать не более четырех символов * с, не более четырех вещей.

142
00:10:02,850 --> 00:10:07,580
Если бы мы были, чтобы попытаться подтолкнуть 1/5 вещь, что вы думаете должно произойти?

143
00:10:07,580 --> 00:10:11,870
[Студенты, неразборчиво]

144
00:10:11,870 --> 00:10:14,600
[Хардисон] Именно так. Есть целый ряд вещей, которые могут случиться.

145
00:10:14,600 --> 00:10:19,330
Это могло сегментам вина, в зависимости от того, что мы были -

146
00:10:19,330 --> 00:10:22,530
как именно мы осуществляли заднем конце.

147
00:10:22,530 --> 00:10:31,740
Это может перезаписать. Он мог бы иметь, что переполнение буфера, что мы говорили в классе.

148
00:10:31,740 --> 00:10:35,240
Что было бы наиболее очевидные вещи, которые могут быть перезаписаны

149
00:10:35,240 --> 00:10:42,370
если бы мы пытались протолкнуть лишняя вещь на нашем стеке?

150
00:10:42,370 --> 00:10:44,550
Таким образом, вы упомянули переполнения буфера.

151
00:10:44,550 --> 00:10:47,870
Что может быть то, что бы получить письменное более или растоптал

152
00:10:47,870 --> 00:10:52,320
если мы переполнены случайно, пытаясь подтолкнуть лишняя вещь?

153
00:10:52,320 --> 00:10:54,730
[Даниил, неразборчиво] >> Возможно.

154
00:10:54,730 --> 00:10:58,440
Но на начальном этапе, что может случиться? Что, если мы пытались протолкнуть 1/4 вещь?

155
00:10:58,440 --> 00:11:06,220
Это может переписать размер, по крайней мере, с этой памятью схеме, что у нас есть.

156
00:11:06,220 --> 00:11:10,880
>> В описании множества проблем, что мы и собираемся реализации сегодня,

157
00:11:10,880 --> 00:11:16,030
то, что мы хотим сделать, это просто возвращение ложным.

158
00:11:16,030 --> 00:11:20,030
Наши метода принудительной собирается вернуть логическое значение,

159
00:11:20,030 --> 00:11:22,920
и что логическое значение будет истинным, если толчок успешно

160
00:11:22,920 --> 00:11:29,730
и ложно, если мы не можем выдвинуть ничего больше, потому что стек переполнен.

161
00:11:29,730 --> 00:11:33,620
Давайте рассмотрим немного, что код прямо сейчас.

162
00:11:33,620 --> 00:11:36,400
Вот наш толчок функции.

163
00:11:36,400 --> 00:11:40,380
Наши толчок функции для стека собирается взять в строке положить на стек.

164
00:11:40,380 --> 00:11:45,820
Он собирается вернуться верно, если строка была успешно вытеснили

165
00:11:45,820 --> 00:11:51,820
в стеке, а в противном случае.

166
00:11:51,820 --> 00:11:59,740
Любые предложения о том, что может быть хорошим первое, что нужно делать здесь?

167
00:11:59,740 --> 00:12:20,630
[Сэм] Если размер равен мощностью затем вернуться ложным?

168
00:12:20,630 --> 00:12:23,320
[Хардисон] Bingo. Хорошая работа.

169
00:12:23,320 --> 00:12:26,310
Если размер имеет потенциал, мы собираемся вернуться ложным.

170
00:12:26,310 --> 00:12:29,270
Мы не можем поместить больше ничего в нашем стеке.

171
00:12:29,270 --> 00:12:36,900
В противном случае, мы хотим положить что-то на вершине стека.

172
00:12:36,900 --> 00:12:41,670
Что такое "вершину стека," изначально?

173
00:12:41,670 --> 00:12:43,650
[Даниил] Размер 0? Размер >> 0.

174
00:12:43,650 --> 00:12:49,990
Что такое вершине стека после есть одна вещь, в стеке? Мисси, вы знаете?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. >> Размер один, точно. Вы продолжайте добавлять к размеру,

176
00:12:52,720 --> 00:13:01,690
и каждый раз, когда вы помещаете в новый элемент на размер индекса в массиве.

177
00:13:01,690 --> 00:13:05,470
Мы можем сделать это с такой один-лайнер, если это имеет смысл.

178
00:13:05,470 --> 00:13:11,910
Итак, мы получили наш массив строк, мы собираемся получить к нему доступ на размер индекса,

179
00:13:11,910 --> 00:13:14,780
и мы только собираемся, чтобы сохранить наш символ * в там.

180
00:13:14,780 --> 00:13:19,340
Обратите внимание, что там нет строки копирование происходит здесь,

181
00:13:19,340 --> 00:13:29,680
нет динамического распределения памяти?

182
00:13:29,680 --> 00:13:34,440
А потом Missy воспитывали, что мы сейчас должны сделать,

183
00:13:34,440 --> 00:13:40,570
потому что мы хранить строку в соответствующее место в массиве,

184
00:13:40,570 --> 00:13:49,230
и она сказала, что мы должны были увеличивать размер одного, так что мы готовы для следующего толчка.

185
00:13:49,230 --> 00:13:53,950
Таким образом, мы можем сделать это с s.size + +.

186
00:13:53,950 --> 00:13:59,330
На данный момент, мы втолкнули в нашем массиве. Что это последнее, что мы должны делать?

187
00:13:59,330 --> 00:14:10,110
[Студент] Вернуться правда. >> Вернуться правда.

188
00:14:10,110 --> 00:14:14,690
Так что это довольно простой, очень простой код. Не слишком много.

189
00:14:14,690 --> 00:14:17,070
После того как вы обернуты вокруг головы, как стек работает,

190
00:14:17,070 --> 00:14:21,910
это довольно просто реализовать.

191
00:14:21,910 --> 00:14:26,390
>> Теперь, следующая часть этого появляются строки из стека.

192
00:14:26,390 --> 00:14:29,410
Я собираюсь дать вам, ребята некоторое время, чтобы работать над этим немного.

193
00:14:29,410 --> 00:14:34,320
Это почти по существу, обратное тому, что мы сделали здесь, в толчке.

194
00:14:34,320 --> 00:14:38,510
Что я сделал на самом деле - ой.

195
00:14:38,510 --> 00:14:48,160
Я загрузился прибора здесь, и в прибор,

196
00:14:48,160 --> 00:14:53,600
Я поднял проблемы установить 5 спецификации.

197
00:14:53,600 --> 00:15:02,560
Если мы увеличим здесь, мы можем видеть, что я нахожусь на cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Разве вы, ребята, скачал этот код, что находится здесь, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Хорошо. Если вы еще не сделали этого, сделайте это прямо сейчас, очень быстро.

200
00:15:15,030 --> 00:15:22,130
Я сделаю это в моем окне терминала.

201
00:15:22,130 --> 00:15:25,090
Я действительно сделал это здесь. Да.

202
00:15:25,090 --> 00:15:34,730
Да, Сэм? >> У меня есть вопрос о том, почему ты сказал s.string 'ы скобках размер = ул?

203
00:15:34,730 --> 00:15:42,910
Что такое СТО? Разве что определенная где-то раньше, или - о, в символ ул *?

204
00:15:42,910 --> 00:15:47,160
[Хардисон] Да, именно так. Это был аргумент. >> Ну, ладно. Извините.

205
00:15:47,160 --> 00:15:49,470
[Хардисон] Мы указанием строки нажать дюйма

206
00:15:49,470 --> 00:15:55,220
Другой вопрос, что может придумать, что мы действительно не говорим о здесь был

207
00:15:55,220 --> 00:15:58,810
Мы считали само собой разумеющимся, что у нас была эта переменная с

208
00:15:58,810 --> 00:16:02,710
, который был по своим масштабам и доступным для нас.

209
00:16:02,710 --> 00:16:06,960
Мы считали само собой разумеющимся, что было с этим стеком структуры.

210
00:16:06,960 --> 00:16:08,930
Таким образом, оглядываясь на этот толчок код,

211
00:16:08,930 --> 00:16:13,450
Вы можете видеть, что мы делаем вещи с этой строки, которые получили прошло в

212
00:16:13,450 --> 00:16:19,210
но потом все внезапно, мы доступе s.size, вроде бы, откуда ей пришел?

213
00:16:19,210 --> 00:16:23,020
В коде, который мы собираемся посмотреть в разделе Архив

214
00:16:23,020 --> 00:16:27,100
, а затем вещи, которые вы будете делать в вашей проблеме устанавливает,

215
00:16:27,100 --> 00:16:32,440
мы сделали наш стек строим глобальную переменную

216
00:16:32,440 --> 00:16:36,380
так что мы можем иметь доступ к нему во всех наших различных функций

217
00:16:36,380 --> 00:16:40,630
без необходимости вручную передавать его и передать его по ссылке,

218
00:16:40,630 --> 00:16:44,870
делать все в таком же роде к нему.

219
00:16:44,870 --> 00:16:52,280
Мы просто обманывает немного, если хотите, чтобы сделать вещи лучше.

220
00:16:52,280 --> 00:16:57,430
И это то, что мы здесь делаем, потому что это для удовольствия, это проще.

221
00:16:57,430 --> 00:17:02,800
Часто, вы увидите, люди делают это, если они имеют один большой структуры данных

222
00:17:02,800 --> 00:17:07,750
который эксплуатируется в рамках своих программ.

223
00:17:07,750 --> 00:17:09,560
>> Давайте вернемся к приборе.

224
00:17:09,560 --> 00:17:15,240
У каждого успешного получить section6.zip?

225
00:17:15,240 --> 00:17:20,440
Все распаковать его с помощью распаковать section6.zip?

226
00:17:20,440 --> 00:17:27,200
Если вы зайдете в раздел 6 каталогов -

227
00:17:27,200 --> 00:17:29,220
ааа, повсюду -

228
00:17:29,220 --> 00:17:32,840
и вы перечислите то, что здесь, вы видите, что у вас есть три разных. с файлами.

229
00:17:32,840 --> 00:17:38,350
У вас есть очереди, SLL, который является односвязный список, и стек.

230
00:17:38,350 --> 00:17:44,600
Если вы откроете stack.c,

231
00:17:44,600 --> 00:17:47,330
Вы видите, что у нас есть эта структура определена для нас,

232
00:17:47,330 --> 00:17:51,330
точные структуры, который мы только что говорили в слайдах.

233
00:17:51,330 --> 00:17:56,340
У нас есть наши глобальные переменные для стека,

234
00:17:56,340 --> 00:18:00,110
Мы получили наш толчок функции,

235
00:18:00,110 --> 00:18:04,230
а то у нас есть наша поп-функции.

236
00:18:04,230 --> 00:18:08,320
Я поставлю код отодвинуть на слайде здесь,

237
00:18:08,320 --> 00:18:10,660
но то, что я хотел бы вам, ребята, чтобы сделать это, в меру ваших возможностей,

238
00:18:10,660 --> 00:18:13,790
пойти и реализации поп-функции.

239
00:18:13,790 --> 00:18:18,480
После того как вы реализовали его, вы можете скомпилировать это с делать стек,

240
00:18:18,480 --> 00:18:22,540
, а затем запустить результирующий исполняемый стек,

241
00:18:22,540 --> 00:18:28,390
и что будет работать все это тестовый код сюда, это в основном.

242
00:18:28,390 --> 00:18:31,060
А главное заботится о деле делает толчок и поп-звонки

243
00:18:31,060 --> 00:18:33,220
и убедившись, что все идет через все в порядке.

244
00:18:33,220 --> 00:18:36,820
Он также инициализирует размер стека прямо здесь

245
00:18:36,820 --> 00:18:39,780
так что вам не придется беспокоиться о том, что инициализация.

246
00:18:39,780 --> 00:18:42,310
Можно предположить, что это было правильно инициализирован

247
00:18:42,310 --> 00:18:48,000
К тому времени, доступ к нему в поп-функции.

248
00:18:48,000 --> 00:18:53,530
Имеет ли это смысл?

249
00:18:53,530 --> 00:19:00,100
Таким образом, здесь мы идем. Там в толчок код.

250
00:19:00,100 --> 00:19:13,210
Я дам вам, ребята 5 или 10 минут.

251
00:19:13,210 --> 00:19:15,690
И если у вас есть какие-либо вопросы в промежуточном то время как вы кодирования,

252
00:19:15,690 --> 00:19:17,710
Пожалуйста, попросите их вслух.

253
00:19:17,710 --> 00:19:23,080
Так что если вы получите камень преткновения, просто спросите.

254
00:19:23,080 --> 00:19:26,030
Позвольте мне знать, пусть все остальные знают.

255
00:19:26,030 --> 00:19:28,160
Работа с вашим соседом тоже.

256
00:19:28,160 --> 00:19:30,360
[Даниил] Мы просто осуществлении поп прямо сейчас? >> Просто поп-музыки.

257
00:19:30,360 --> 00:19:34,200
Хотя Вы можете скопировать реализации толчок, если вы хотите

258
00:19:34,200 --> 00:19:37,780
так что тестирование будет работать.

259
00:19:37,780 --> 00:19:41,940
Потому что это трудно проверить вещи попасть в -

260
00:19:41,940 --> 00:19:49,030
или, трудно проверить появляться вещи из стека, если нет ничего в стек с самого начала.

261
00:19:49,030 --> 00:19:55,250
>> Что такое поп должно быть возвращение? Элемент из вершины стека.

262
00:19:55,250 --> 00:20:01,260
Он должен получить элемент с вершины стека

263
00:20:01,260 --> 00:20:05,780
, а затем уменьшать размер стека,

264
00:20:05,780 --> 00:20:07,810
и теперь вы потеряли элемент на вершине.

265
00:20:07,810 --> 00:20:11,420
И тогда вы вернетесь элемент на вершине.

266
00:20:11,420 --> 00:20:20,080
[Студент, неразборчиво]

267
00:20:20,080 --> 00:20:28,810
[Хардисон] Что случится, если вы это сделаете? [Студент, неразборчиво]

268
00:20:28,810 --> 00:20:34,000
Что в итоге происходит это вы, вероятно, доступ либо

269
00:20:34,000 --> 00:20:37,350
Элемент, который не был инициализирован, так что ваш расчет

270
00:20:37,350 --> 00:20:39,990
, где последний элемент выключен.

271
00:20:39,990 --> 00:20:46,260
Так вот, если вы заметили, в толчке, мы доступе строк в элементе s.size

272
00:20:46,260 --> 00:20:48,560
потому что это новый индекс.

273
00:20:48,560 --> 00:20:51,460
Это новая вершина стека.

274
00:20:51,460 --> 00:21:01,100
Если в поп, s.size будет следующий пространстве,

275
00:21:01,100 --> 00:21:05,210
пространство, которое находится на вершине всех элементов в стеке.

276
00:21:05,210 --> 00:21:10,050
Таким образом, самый верхний элемент не в s.size,

277
00:21:10,050 --> 00:21:14,930
но, скорее, это под ним.

278
00:21:14,930 --> 00:21:19,640
>> Другая вещь, чтобы сделать, когда вы - в поп,

279
00:21:19,640 --> 00:21:22,030
это у вас есть для уменьшения размера.

280
00:21:22,030 --> 00:21:28,750
Если вы помните, вернемся к нашей маленькой диаграмме прямо здесь,

281
00:21:28,750 --> 00:21:30,980
на самом деле, единственное, что мы видели, происходит, когда мы называли поп-

282
00:21:30,980 --> 00:21:36,150
было то, что этот размер упала, сначала в 2, то к 1.

283
00:21:36,150 --> 00:21:42,620
Потом, когда мы выдвинули новый элемент, он пойдет на на должном месте.

284
00:21:42,620 --> 00:21:49,610
[Василий] Если s.size равно 2, то не было бы перейти к элементу 2,

285
00:21:49,610 --> 00:21:54,400
и вы хотите, чтобы всплывал этот элемент прочь?

286
00:21:54,400 --> 00:21:59,510
Таким образом, если мы пошли в - >> Итак, давайте посмотрим на это еще раз.

287
00:21:59,510 --> 00:22:07,730
Если это наш стек на данный момент

288
00:22:07,730 --> 00:22:12,130
и мы называем поп,

289
00:22:12,130 --> 00:22:16,150
, при котором индекс самого верхнего элемента?

290
00:22:16,150 --> 00:22:19,300
[Василий] В 2, но это будет поп-3. >> Праве.

291
00:22:19,300 --> 00:22:24,220
Так вот, где наш размер 3, но мы хотим, чтобы совать элемент с индексом 2.

292
00:22:24,220 --> 00:22:29,900
Это очень типичный вид на единицу, что у вас с нулевой индексации массивов.

293
00:22:29,900 --> 00:22:36,430
Итак, вы хотите, чтобы совать третий элемент, а третий элемент не с индексом 3.

294
00:22:36,430 --> 00:22:39,430
И поэтому мы не должны делать это минус 1, когда мы нажатия

295
00:22:39,430 --> 00:22:44,120
происходит потому, что прямо сейчас, вы заметите, что самый верхний элемент,

296
00:22:44,120 --> 00:22:47,600
если бы мы были выдвинуть что-то еще в стек на данный момент,

297
00:22:47,600 --> 00:22:50,360
Мы хотели бы, чтобы подтолкнуть ее с индексом 3.

298
00:22:50,360 --> 00:23:03,550
И так уж случилось, что размер и индексы выстраиваются, когда вы нажимаете.

299
00:23:03,550 --> 00:23:06,960
>> У кого есть рабочая реализации стека?

300
00:23:06,960 --> 00:23:09,690
У вас есть рабочий стек один. Есть ли у вас поп рабочие еще?

301
00:23:09,690 --> 00:23:11,890
[Даниил] Да. Я так думаю.

302
00:23:11,890 --> 00:23:14,610
>> Программа работает, а не сегментам разломов, это распечатка?

303
00:23:14,610 --> 00:23:17,520
Есть ли распечатать "успех" при запуске?

304
00:23:17,520 --> 00:23:22,630
Да. Сделать стек, запустить его, если он печатает «успех» и не идет бум,

305
00:23:22,630 --> 00:23:26,000
то все хорошо.

306
00:23:26,000 --> 00:23:34,070
Хорошо. Давайте перейдем к устройству очень быстро,

307
00:23:34,070 --> 00:23:46,100
и мы пройдем через это.

308
00:23:46,100 --> 00:23:51,110
Если мы посмотрим на то, что происходит здесь с поп-

309
00:23:51,110 --> 00:23:55,220
Daniel, что было первое, что вы сделали?

310
00:23:55,220 --> 00:23:58,850
[Даниил] Если s.size больше 0.

311
00:23:58,850 --> 00:24:03,120
[Хардисон] Хорошо. А зачем вы это сделали?

312
00:24:03,120 --> 00:24:05,610
[Даниил] Чтобы убедиться в том, что что-то внутри стека.

313
00:24:05,610 --> 00:24:10,950
[Хардисон] Верно. Вы хотите, чтобы проверить, чтобы убедиться, что s.size больше 0;

314
00:24:10,950 --> 00:24:13,280
в противном случае, что вы хотите, чтобы произошло?

315
00:24:13,280 --> 00:24:16,630
[Даниил] Return нуль? >> Вернуться нулевой, это точно.

316
00:24:16,630 --> 00:24:20,740
Так что, если s.size больше 0. Тогда что же мы будем делать?

317
00:24:20,740 --> 00:24:25,890
Что мы будем делать, если стек не пуст?

318
00:24:25,890 --> 00:24:31,210
[Stella] Вы уменьшите размер? >> Вы уменьшения размера, все в порядке.

319
00:24:31,210 --> 00:24:34,440
Так как же вы это сделаете? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Хардисон] Великий. А то, что ты сделал?

321
00:24:37,030 --> 00:24:44,140
[Stella] И тогда я сказал возвращения s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Хардисон] Великий.

323
00:24:48,560 --> 00:24:51,940
В противном случае вы вернетесь нулевой. Да, Сэм?

324
00:24:51,940 --> 00:24:55,510
[Сэм] Почему она не должна быть s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Хардисон] плюс 1? >> Да. >> Есть.

326
00:24:58,430 --> 00:25:00,980
[Сэм] Я думал, потому что вы принимаете 1 из,

327
00:25:00,980 --> 00:25:04,290
то вы будете возвращаться не тот, что они просили.

328
00:25:04,290 --> 00:25:09,400
[Хардисон] И это было именно то, что мы говорим о целом с этим вопросом от 0 индексов.

329
00:25:09,400 --> 00:25:11,380
Поэтому, если мы масштаб здесь.

330
00:25:11,380 --> 00:25:15,650
Если мы посмотрим на этого парня прямо здесь, вы можете увидеть, что когда мы поп,

331
00:25:15,650 --> 00:25:19,340
Мы появляться элемент с индексом 2.

332
00:25:19,340 --> 00:25:25,200
>> Таким образом, мы снижаем наш размер, а затем наш размер соответствует нашему индексу.

333
00:25:25,200 --> 00:25:39,650
Если мы не уменьшаем размер, а затем мы должны сделать размер -1, а затем декремента.

334
00:25:39,650 --> 00:25:45,270
Великий. Все хорошо?

335
00:25:45,270 --> 00:25:47,530
Есть вопросы по этому поводу?

336
00:25:47,530 --> 00:25:54,050
Есть много разных способов, чтобы написать это, а также.

337
00:25:54,050 --> 00:26:03,290
В самом деле, мы можем сделать что-то еще - мы можем сделать один-лайнер.

338
00:26:03,290 --> 00:26:05,770
Мы можем сделать одну линию возврата.

339
00:26:05,770 --> 00:26:12,980
Таким образом, мы действительно можем уменьшать прежде чем мы вернемся на этом.

340
00:26:12,980 --> 00:26:18,320
Таким образом, положив - до s.size.

341
00:26:18,320 --> 00:26:22,060
Это делает линию очень плотный.

342
00:26:22,060 --> 00:26:30,940
Где разница между -. С размером и s.size--

343
00:26:30,940 --> 00:26:40,130
что это постфикс - они называют это постфикс, потому что - приходит после s.size--

344
00:26:40,130 --> 00:26:47,430
означает, что s.size оценивается для целей нахождения индекса

345
00:26:47,430 --> 00:26:50,410
как в настоящее время, когда эта линия будет выполнена,

346
00:26:50,410 --> 00:26:54,290
и тогда это - происходит после строки запускается на выполнение.

347
00:26:54,290 --> 00:27:00,340
После того, как элемент s.size индекс доступен.

348
00:27:00,340 --> 00:27:07,260
И это не то, что мы хотим, потому что мы хотим декремент произойдет в первую очередь.

349
00:27:07,260 --> 00:27:10,990
Othewise, мы будем получать доступ к массиву, по сути, вне закона.

350
00:27:10,990 --> 00:27:16,850
Мы собираемся получать доступ к элементу выше той, что мы на самом деле хотим получить доступ.

351
00:27:16,850 --> 00:27:23,840
Да, Сэм? >> Это быстрее и использует меньше памяти, чтобы в одной строке или нет?

352
00:27:23,840 --> 00:27:29,620
[Хардисон] Честно говоря, это действительно зависит.

353
00:27:29,620 --> 00:27:34,220
[Сэм, неразборчиво] >> Да, это зависит от обстоятельств. Вы можете сделать компилятор трюки

354
00:27:34,220 --> 00:27:41,580
чтобы получить компилятор признать, что, как правило, я полагаю.

355
00:27:41,580 --> 00:27:44,840
>> Таким образом, мы уже говорили немного об этой вещи оптимизации компиляторов

356
00:27:44,840 --> 00:27:47,400
что вы можете сделать в сборе,

357
00:27:47,400 --> 00:27:50,580
и это такая вещь, что компилятор может быть в состоянии выяснить,

358
00:27:50,580 --> 00:27:54,710
как Эй, может быть, я могу сделать это все в одной операции,

359
00:27:54,710 --> 00:27:59,420
в отличие от загрузки размер переменной из оперативной памяти,

360
00:27:59,420 --> 00:28:03,770
его уменьшения, хранение его обратно, а затем загрузку его снова

361
00:28:03,770 --> 00:28:08,000
Для обработки остальной части этой работы.

362
00:28:08,000 --> 00:28:10,710
Но, как правило, нет, это не та вещь,

363
00:28:10,710 --> 00:28:20,770
что собирается сделать программу значительно быстрее.

364
00:28:20,770 --> 00:28:26,000
Есть еще вопросы по стеков?

365
00:28:26,000 --> 00:28:31,360
>> Таким образом, толкаясь и появляются. Если вы, ребята, хотите попробовать хакером издание,

366
00:28:31,360 --> 00:28:33,660
то, что мы сделали в хакером издание фактически пошел

367
00:28:33,660 --> 00:28:37,670
и сделал это стек динамично расти.

368
00:28:37,670 --> 00:28:43,190
Проблема есть в первую очередь здесь, в толчок функции,

369
00:28:43,190 --> 00:28:48,820
чтобы выяснить, как сделать этот массив расти

370
00:28:48,820 --> 00:28:52,450
как вы продолжать настаивать больше и больше элементов в стек.

371
00:28:52,450 --> 00:28:56,000
Это на самом деле не так уж много дополнительного кода.

372
00:28:56,000 --> 00:29:00,080
Просто вызов - вы должны помнить, чтобы получить звонки на таНос там должным образом,

373
00:29:00,080 --> 00:29:03,310
, а затем выяснить, когда вы собираетесь звонить перераспределить.

374
00:29:03,310 --> 00:29:06,090
Это весело проблемой, если вы заинтересованы.

375
00:29:06,090 --> 00:29:11,550
>> Но на данный момент, давайте двигаться дальше, и давайте поговорим об очередях.

376
00:29:11,550 --> 00:29:15,680
Прокрутите здесь.

377
00:29:15,680 --> 00:29:19,340
Очередь близко родственный стека.

378
00:29:19,340 --> 00:29:25,380
Таким образом, в стеке, вещи, которые были введены в последнем

379
00:29:25,380 --> 00:29:28,810
были первыми вещами, чтобы потом быть восстановлена.

380
00:29:28,810 --> 00:29:33,600
У нас есть последний вошел, первый вышел, или ЛИФО, заказа.

381
00:29:33,600 --> 00:29:38,390
В то время как в очереди, как вы ожидали бы от того, когда вы стоите в очереди,

382
00:29:38,390 --> 00:29:41,980
Первым человеком, встать в очередь, первым делом, чтобы попасть в очередь,

383
00:29:41,980 --> 00:29:47,630
это первое, что получает извлекается из очереди.

384
00:29:47,630 --> 00:29:51,490
Очереди также часто используется, когда мы имеем дело с графиками,

385
00:29:51,490 --> 00:29:55,560
о которой мы говорили кратко стеки,

386
00:29:55,560 --> 00:30:00,260
и очередей также удобны для кучу других вещей.

387
00:30:00,260 --> 00:30:06,180
Одна вещь, которая приходит часто пытается поддерживать, например,

388
00:30:06,180 --> 00:30:12,310
отсортированный список элементов.

389
00:30:12,310 --> 00:30:17,650
И вы можете сделать это с помощью массива. Вы можете поддерживать отсортированный список вещей в массиве,

390
00:30:17,650 --> 00:30:20,650
однако там, где становится сложно тогда у вас всегда есть, чтобы найти

391
00:30:20,650 --> 00:30:26,160
соответствующее место, чтобы вставить следующую вещь.

392
00:30:26,160 --> 00:30:28,250
Так что если у вас есть массив чисел, от 1 до 10,

393
00:30:28,250 --> 00:30:31,630
и вы хотите расширить, что для всех чисел от 1 до 100,

394
00:30:31,630 --> 00:30:33,670
и вы получаете этих цифр в произвольном порядке и пытались держать все

395
00:30:33,670 --> 00:30:40,650
отсортировано как вы идете через, вы в конечном итоге приходится делать много передач.

396
00:30:40,650 --> 00:30:43,910
При некоторых типах очередей и некоторых видов базовых структур данных

397
00:30:43,910 --> 00:30:46,670
Вы можете фактически держать его довольно просто.

398
00:30:46,670 --> 00:30:50,640
Вы не имеете что-то добавить, а затем перераспределит все это каждый раз.

399
00:30:50,640 --> 00:30:56,770
Также вы должны сделать много смещение внутренних элементов вокруг.

400
00:30:56,770 --> 00:31:02,990
Когда мы смотрим на очереди, вы видите, что - и в queue.c в разделе кода -

401
00:31:02,990 --> 00:31:10,950
Структура, которую мы дали вам действительно похожа на структуру, которую мы дали вам за стека.

402
00:31:10,950 --> 00:31:13,770
>> Там в одно исключение из этого, и что за одним исключением

403
00:31:13,770 --> 00:31:21,700
является то, что у нас есть это дополнительные целое число, называемое головой,

404
00:31:21,700 --> 00:31:28,120
и голова здесь для отслеживания голове очереди,

405
00:31:28,120 --> 00:31:32,160
или первый элемент в очереди.

406
00:31:32,160 --> 00:31:37,470
С стек, мы смогли отслеживать элемент, который мы собирались получить,

407
00:31:37,470 --> 00:31:40,800
или на вершине стека, используя только размер,

408
00:31:40,800 --> 00:31:44,220
в то время как с очередью, мы иметь дело с противоположных концов.

409
00:31:44,220 --> 00:31:49,000
Мы пытаемся трека вещи на конце, а затем вернуть вещи с фронта.

410
00:31:49,000 --> 00:31:54,640
Таким образом, эффективно, с головой, у нас есть индекс начала очереди,

411
00:31:54,640 --> 00:31:58,920
и размер дает нам индекс конца очереди

412
00:31:58,920 --> 00:32:03,730
так что мы можем получить вещи из головы и добавить вещи на хвосте.

413
00:32:03,730 --> 00:32:06,890
В то время как со стеком, мы были только когда-либо дело с вершины стека.

414
00:32:06,890 --> 00:32:08,900
Мы никогда не имели доступа к нижней части стека.

415
00:32:08,900 --> 00:32:12,220
Мы только добавили вещи на верхние и взял вещи с верхней

416
00:32:12,220 --> 00:32:17,470
так что нам не нужно, что дополнительные поля внутри нашей структуры.

417
00:32:17,470 --> 00:32:20,590
Значит ли это вообще смысл?

418
00:32:20,590 --> 00:32:27,670
Хорошо. Да, Шарлотта? [Charlotte, неразборчиво]

419
00:32:27,670 --> 00:32:32,660
[Хардисон] Это большой вопрос, а что было одно, что пришли в лекции.

420
00:32:32,660 --> 00:32:36,290
Может быть, идя через несколько примеров проиллюстрировать, почему

421
00:32:36,290 --> 00:32:41,400
Мы не хотим, чтобы использовать строки [0] в качестве главы очереди.

422
00:32:41,400 --> 00:32:46,770
>> Итак, представьте, что у нас есть очередь, мы будем называть его очередь.

423
00:32:46,770 --> 00:32:49,210
В начале, когда мы только что создан он,

424
00:32:49,210 --> 00:32:53,330
когда мы только объявили его, мы не инициализирован ничего.

425
00:32:53,330 --> 00:32:56,790
Это все фигня. Поэтому, конечно, мы хотим убедиться, что мы инициализируем

426
00:32:56,790 --> 00:33:00,950
и размер, и глава поля равно 0, то разумно.

427
00:33:00,950 --> 00:33:05,770
Мы также могли бы пойти дальше и обнулять элементы в нашей очереди.

428
00:33:05,770 --> 00:33:09,930
А чтобы эта схема подходит, заметил, что теперь наша очередь может иметь только трех элементов;

429
00:33:09,930 --> 00:33:13,150
в то время как наш стек может провести четыре, наша очередь может иметь только три.

430
00:33:13,150 --> 00:33:18,680
И это только чтобы сделать схему нужным.

431
00:33:18,680 --> 00:33:26,150
Первое, что здесь происходит, что мы постановки в очередь строки "привет".

432
00:33:26,150 --> 00:33:30,380
И так же, как мы это делали со стеком, ничего не страшно здесь по-другому,

433
00:33:30,380 --> 00:33:39,230
мы бросаем строки, по крайней строки [0] и увеличиваем наш размер на 1.

434
00:33:39,230 --> 00:33:42,720
Мы постановки в очередь "до свидания", она будет надеть.

435
00:33:42,720 --> 00:33:45,870
Так это выглядит как стопка по большей части.

436
00:33:45,870 --> 00:33:53,230
Мы начали здесь, новый элемент, новый элемент, размером продолжает идти вверх.

437
00:33:53,230 --> 00:33:56,330
Что происходит в этот момент, когда мы хотим что-то из очереди?

438
00:33:56,330 --> 00:34:01,280
Когда мы хотим из очереди, которая является элементом, который мы хотим из очереди?

439
00:34:01,280 --> 00:34:04,110
[Василий] струнных [0]. >> Zero. Совершенно верно, Василий.

440
00:34:04,110 --> 00:34:10,960
Мы хотим, чтобы избавиться от первой строки, на этот раз, "привет".

441
00:34:10,960 --> 00:34:13,170
Так что же другая вещь, которая изменилась?

442
00:34:13,170 --> 00:34:17,010
Обратите внимание, когда мы что-то выскочил из стека, мы просто изменили размер,

443
00:34:17,010 --> 00:34:22,080
но здесь, у нас есть пара вещей, которые меняются.

444
00:34:22,080 --> 00:34:27,440
Не только изменить размер, но глава изменений.

445
00:34:27,440 --> 00:34:31,020
Это возвращаясь к точке Шарлотты ранее:

446
00:34:31,020 --> 00:34:38,699
почему мы должны это голова, а?

447
00:34:38,699 --> 00:34:42,110
Имеет ли смысл сейчас, Шарлотта? >> Вроде того.

448
00:34:42,110 --> 00:34:47,500
[Хардисон] Вид? Так что же произошло, когда мы из очереди?

449
00:34:47,500 --> 00:34:54,340
Что же глава сделать это сейчас интересно?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] О, потому что она изменилась - все в порядке. Понимаю.

451
00:34:56,449 --> 00:35:02,090
Потому что голова - где голова указывает на изменения в плане расположения.

452
00:35:02,090 --> 00:35:07,200
Это уже не всегда нулевого индекса. >> Да, именно так.

453
00:35:07,200 --> 00:35:17,660
То, что произошло, если dequeueing высокого элемента

454
00:35:17,660 --> 00:35:20,590
было сделано, и у нас не было этой главы поля

455
00:35:20,590 --> 00:35:26,880
потому что мы всегда называл эту строку в 0 индекс глава нашей очереди,

456
00:35:26,880 --> 00:35:30,170
тогда мы должны перейти остальные очереди вниз.

457
00:35:30,170 --> 00:35:36,010
Мы должны перейти "до свидания" из из строк [1] ​​строки [0].

458
00:35:36,010 --> 00:35:38,760
И строк [2] вплоть до строки [1].

459
00:35:38,760 --> 00:35:43,050
И мы должны сделать это, чтобы весь список элементов,

460
00:35:43,050 --> 00:35:45,110
Весь массив элементов.

461
00:35:45,110 --> 00:35:50,490
И когда мы делаем это с помощью массива, который получает очень дорого.

462
00:35:50,490 --> 00:35:53,340
Так вот, это не имеет большого значения. Мы просто должны трех элементов в массиве.

463
00:35:53,340 --> 00:35:57,230
Но если у нас была очередь из тысяч элементов или миллион элементов,

464
00:35:57,230 --> 00:36:00,060
а затем все внезапно, мы начинаем делать кучу из очереди называет все в цикле,

465
00:36:00,060 --> 00:36:03,930
вещи действительно собирается замедляться, как он перекладывает все вниз постоянно.

466
00:36:03,930 --> 00:36:07,320
Вы знаете, переложить на 1, сдвиг на 1, сдвиг на 1, сдвиг на 1.

467
00:36:07,320 --> 00:36:13,650
Вместо этого, мы используем эту голову, мы называем это "указатель", хотя это не совсем указатель

468
00:36:13,650 --> 00:36:16,430
В строгом смысле, это не тип указателя.

469
00:36:16,430 --> 00:36:19,410
Это не Int * или символ * или что-нибудь подобное.

470
00:36:19,410 --> 00:36:28,930
Но это указания или с указанием главы нашей очереди. Да?

471
00:36:28,930 --> 00:36:38,800
>> [Студент] Как йедиеие знать, чтобы просто палить все, что в голову?

472
00:36:38,800 --> 00:36:43,620
[Хардисон] Как йедиеие знаю, как палить все это в голове? >> Да, да.

473
00:36:43,620 --> 00:36:49,050
>> Что она смотрит на только что голова поле установлено.

474
00:36:49,050 --> 00:36:52,710
Таким образом, в первом случае, если мы посмотрим прямо здесь,

475
00:36:52,710 --> 00:36:55,690
наши головы равна 0, индекс 0. >> Праве.

476
00:36:55,690 --> 00:37:00,500
[Хардисон] Так что это просто говорит, хорошо, хорошо, элемент с индексом 0, строка "привет",

477
00:37:00,500 --> 00:37:03,050
является элементом во главе нашей очереди.

478
00:37:03,050 --> 00:37:05,570
Таким образом, мы собираемся из очереди этого парня.

479
00:37:05,570 --> 00:37:09,800
И это будет элемент, который получает вернулись к абоненту.

480
00:37:09,800 --> 00:37:14,540
Да, Саад? >> Так глава в основном задает - где вы собираетесь индексировать?

481
00:37:14,540 --> 00:37:17,750
Вот начало этого? >> Да. >> Хорошо.

482
00:37:17,750 --> 00:37:22,900
[Хардисон] Это становится новым началом для нашего массива.

483
00:37:22,900 --> 00:37:28,930
Итак, когда вы что-то из очереди, все что вам нужно сделать, это получить доступ к элементу по индексу q.head,

484
00:37:28,930 --> 00:37:32,240
и это будет элемент, который вы хотите из очереди.

485
00:37:32,240 --> 00:37:34,930
Вы также должны уменьшать размер.

486
00:37:34,930 --> 00:37:39,430
Мы увидим в бит, где все становится немного сложнее с этим.

487
00:37:39,430 --> 00:37:46,520
Мы из очереди, и теперь, если мы вновь поставить в очередь,

488
00:37:46,520 --> 00:37:51,300
где же мы поставить в очередь?

489
00:37:51,300 --> 00:37:55,000
Где следующего элемента пойти в нашей очереди?

490
00:37:55,000 --> 00:37:57,980
Скажем, мы хотим поставить в очередь строки "CS".

491
00:37:57,980 --> 00:38:02,240
В какой индекс он пойдет? [Студенты] струнных [2]. Два >>.

492
00:38:02,240 --> 00:38:04,980
Почему 2, а не 0?

493
00:38:04,980 --> 00:38:13,570
[Василий] Потому что сейчас голова 1, так что похоже на начало списка?

494
00:38:13,570 --> 00:38:21,220
[Хардисон] Верно. А что обозначает конец списка?

495
00:38:21,220 --> 00:38:23,290
Что мы используем для обозначения конца нашей очереди?

496
00:38:23,290 --> 00:38:25,970
Голова глава нашей очереди, в начале нашей очереди.

497
00:38:25,970 --> 00:38:29,530
Что в конце нашей очереди? [Студенты] Size. >> Размер, точно.

498
00:38:29,530 --> 00:38:36,360
Таким образом, наши новые элементы пойти, по крайней размер, и элементы, которые мы взлетаем оторваться на голову.

499
00:38:36,360 --> 00:38:45,390
Когда мы постановки в очередь на следующий элемент, мы помещаем его в в размерах.

500
00:38:45,390 --> 00:38:48,530
[Студент] Перед тем, как положить, что в, хотя, размер составлял 1, верно?

501
00:38:48,530 --> 00:38:55,690
[Хардисон] Верно. Так что не совсем по размеру. Размер +, а не +1, но + голова.

502
00:38:55,690 --> 00:38:59,990
Потому что мы перешли все по голове суммы.

503
00:38:59,990 --> 00:39:14,270
Так вот, теперь у нас есть очереди размером 1, который начинается с индексом 1.

504
00:39:14,270 --> 00:39:20,730
Хвост индекс 2. Да?

505
00:39:20,730 --> 00:39:25,780
>> [Студент] Что происходит, когда вы из очереди строки [0], и строки 'слотов памяти

506
00:39:25,780 --> 00:39:29,420
просто получить опустели, в основном, или просто забыли?

507
00:39:29,420 --> 00:39:34,700
[Хардисон] Да. В этом смысле, мы просто забыли их.

508
00:39:34,700 --> 00:39:42,640
Если бы мы были хранения копий их -

509
00:39:42,640 --> 00:39:46,310
многие структуры данных часто хранят свои собственные копии элементов

510
00:39:46,310 --> 00:39:51,760
так что человек управляет структурой данных не нужно беспокоиться

511
00:39:51,760 --> 00:39:53,650
о том, где все эти указатели собираются.

512
00:39:53,650 --> 00:39:56,000
Структура данных выполняется на всем, проводит на всех копиях,

513
00:39:56,000 --> 00:39:59,580
чтобы убедиться, что все сохраняется должным образом.

514
00:39:59,580 --> 00:40:03,140
Тем не менее, в данном случае, эти структуры данных только для простоты,

515
00:40:03,140 --> 00:40:05,580
не делаем копии всего, что мы хранении в них.

516
00:40:05,580 --> 00:40:08,630
[Студент] Так это непрерывный массив -? >> Да.

517
00:40:08,630 --> 00:40:14,350
Если мы оглянемся на то, что определение было этой структуры, это так.

518
00:40:14,350 --> 00:40:19,110
Это всего лишь стандартный набор, как вы видели,

519
00:40:19,110 --> 00:40:24,280
массив символов S *.

520
00:40:24,280 --> 00:40:26,340
Значит ли это -? >> Да, мне было просто интересно

521
00:40:26,340 --> 00:40:29,130
если вы в конечном итоге запустить из памяти, в определенной степени,

522
00:40:29,130 --> 00:40:32,330
если у вас есть все эти пустые места в вашем массиве?

523
00:40:32,330 --> 00:40:36,390
[Хардисон] Да, это хорошая точка.

524
00:40:36,390 --> 00:40:41,530
>> Если мы посмотрим на то, что произошло сейчас в этой точке,

525
00:40:41,530 --> 00:40:46,350
мы заполнили наши очереди, как он выглядит.

526
00:40:46,350 --> 00:40:50,390
Но мы действительно не заполнены нашими очереди

527
00:40:50,390 --> 00:40:57,710
потому что у нас очередь это размер 2, но он начинается с индекса 1,

528
00:40:57,710 --> 00:41:02,160
потому что там наши головы указатель.

529
00:41:02,160 --> 00:41:08,400
Как вы говорили, что элемент строки [0], индекс 0, на самом деле не существует.

530
00:41:08,400 --> 00:41:10,450
Это не в нашей очереди больше.

531
00:41:10,450 --> 00:41:16,460
Мы просто не потрудились пойти и переписать его, когда мы его из очереди.

532
00:41:16,460 --> 00:41:18,700
Поэтому, даже если это выглядит как мы запускаем из памяти, мы на самом деле не имеют.

533
00:41:18,700 --> 00:41:23,270
Это место доступно для нас, чтобы использовать.

534
00:41:23,270 --> 00:41:29,310
Соответствующее поведение, если бы мы пытались и первый из очереди что-то

535
00:41:29,310 --> 00:41:34,420
нравится "до свидания", что бы поп свидания с.

536
00:41:34,420 --> 00:41:38,460
Теперь наша очередь начинается с индексом 2 и имеет размер 1.

537
00:41:38,460 --> 00:41:42,240
И теперь, если мы будем пытаться поставить в очередь опять что-то, скажем, 50,

538
00:41:42,240 --> 00:41:47,880
50 должны идти в это место с индексом 0

539
00:41:47,880 --> 00:41:51,270
потому что он по-прежнему доступны для нас. Да, Саад?

540
00:41:51,270 --> 00:41:53,630
[Саад] Значит ли это происходить автоматически?

541
00:41:53,630 --> 00:41:56,150
[Хардисон] Это не происходит совершенно автоматически. Вы должны сделать математику

542
00:41:56,150 --> 00:42:00,380
чтобы заставить его работать, но по сути то, что мы сделали, мы только обернутый вокруг.

543
00:42:00,380 --> 00:42:04,070
[Саад] И это хорошо, если это имеет отверстие в середине этого?

544
00:42:04,070 --> 00:42:08,720
[Хардисон] Это если мы можем сделать математику работать должным образом.

545
00:42:08,720 --> 00:42:15,470
>> И оказывается, что это на самом деле не так уж трудно сделать с модом оператора.

546
00:42:15,470 --> 00:42:20,040
Так же, как мы это делали с Цезарем и материал крипто,

547
00:42:20,040 --> 00:42:25,190
использование мода, мы можем добиться, чтобы обернуть вокруг и продолжать идти

548
00:42:25,190 --> 00:42:28,090
вокруг да около и вокруг нашей очереди,

549
00:42:28,090 --> 00:42:32,180
поддержанию, что голова указатель передвигаться.

550
00:42:32,180 --> 00:42:38,840
Обратите внимание, что размер всегда уважении количество элементов на самом деле в очереди.

551
00:42:38,840 --> 00:42:43,110
И это только голова указатель, который держит велосипеде через.

552
00:42:43,110 --> 00:42:49,660
Если мы посмотрим на то, что произошло здесь, если мы вернемся к началу,

553
00:42:49,660 --> 00:42:55,020
и вы только посмотрите, что происходит в голове

554
00:42:55,020 --> 00:42:58,240
Когда мы что-то поставить в очередь, ничего не случилось с головой.

555
00:42:58,240 --> 00:43:00,970
Когда мы в очереди что-то еще, ничего не случилось с головой.

556
00:43:00,970 --> 00:43:04,130
Как только мы что-то из очереди, голова идет вверх на одну.

557
00:43:04,130 --> 00:43:06,600
Мы в очереди что-то, ничего не происходит в голове.

558
00:43:06,600 --> 00:43:11,060
Когда мы что-то из очереди, вдруг голова получает приращение.

559
00:43:11,060 --> 00:43:14,660
Когда мы что-то поставить в очередь, ничего не происходит в голове.

560
00:43:14,660 --> 00:43:20,240
>> Что произойдет в этот момент, если бы мы из очереди опять что-то?

561
00:43:20,240 --> 00:43:23,240
Любые мысли? Что будет с головой?

562
00:43:23,240 --> 00:43:27,190
Что должно произойти в голову

563
00:43:27,190 --> 00:43:32,990
если бы мы из очереди что-то еще?

564
00:43:32,990 --> 00:43:35,400
Голова прямо сейчас с индексом 2,

565
00:43:35,400 --> 00:43:38,920
Это означает, что глава очередь строк [2].

566
00:43:38,920 --> 00:43:44,280
[Студент] Какой возвращает 0? >> Она должна возвращать 0. Следует обернуть вокруг спины, точно.

567
00:43:44,280 --> 00:43:48,440
До сих пор, каждый раз, когда мы звонили из очереди, мы были добавив к нему один в голову,

568
00:43:48,440 --> 00:43:50,960
добавить к голове, добавьте один в голову, добавьте один в голову.

569
00:43:50,960 --> 00:43:58,400
Как только что голова указатель попадает на последний индекс в массиве,

570
00:43:58,400 --> 00:44:05,650
Затем мы должны обернуть его обратно к началу, вернитесь к 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Что определяет способность очереди в стеке?

572
00:44:09,900 --> 00:44:13,120
[Хардисон] В этом случае, мы просто использовали # определена постоянная. >> Хорошо.

573
00:44:13,120 --> 00:44:19,590
[Хардисон] В реальной. Файл C, вы можете пойти и сбросить с нее немного

574
00:44:19,590 --> 00:44:21,710
и сделать это как большой или как мало, как вы хотите.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Итак, когда вы делаете это очереди, как вы делаете компьютеру знаю

576
00:44:25,310 --> 00:44:29,120
насколько большой Вы хотите, чтобы стек быть?

577
00:44:29,120 --> 00:44:31,700
[Хардисон] Это большой вопрос.

578
00:44:31,700 --> 00:44:34,800
Есть несколько способов. Одним из них является просто определить его передняя

579
00:44:34,800 --> 00:44:42,050
и сказать, что это будет очереди, которая имеет 4 элемента или 50 элементов или 10.000.

580
00:44:42,050 --> 00:44:45,430
Другой способ сделать то, что люди, хакер издание делает

581
00:44:45,430 --> 00:44:52,310
и создать функции, чтобы ваша очередь динамично расти, как другие вещи добавляются дюйма

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Так, чтобы пойти с первым вариантом, какой синтаксис вы используете

583
00:44:54,740 --> 00:44:57,830
указать программе, что размер очереди?

584
00:44:57,830 --> 00:45:04,780
[Хардисон] Ah. Итак, давайте из этого.

585
00:45:04,780 --> 00:45:12,650
Я все еще в stack.c здесь, так что я просто хочу, чтобы прокрутить до самого верха здесь.

586
00:45:12,650 --> 00:45:17,920
Вы можете увидеть это прямо здесь? Это # определить емкость 10.

587
00:45:17,920 --> 00:45:24,600
И это почти точно такой же синтаксис, который мы имеем для очереди.

588
00:45:24,600 --> 00:45:28,390
За исключением очередь, мы получили, что дополнительное поле структуры здесь.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] О, я думал, что мощность означает способность к строке.

590
00:45:32,760 --> 00:45:36,770
[Хардисон] Ah. >> Что это максимальная длина слова. >> Есть.

591
00:45:36,770 --> 00:45:41,180
Да. Емкость здесь - это отличная точка.

592
00:45:41,180 --> 00:45:44,000
И это нечто, что сложно

593
00:45:44,000 --> 00:45:49,480
потому что мы объявили здесь массив символов S *.

594
00:45:49,480 --> 00:45:52,770
Массив указателей.

595
00:45:52,770 --> 00:45:56,690
Это массив символов.

596
00:45:56,690 --> 00:46:01,690
Это, наверное, то, что вы видели, когда вы были ваши объявления буферов для файлового ввода / вывода,

597
00:46:01,690 --> 00:46:06,840
когда вы создавали строки вручную в стеке.

598
00:46:06,840 --> 00:46:09,090
Однако то, что мы имеем здесь представляет собой массив символов S *.

599
00:46:09,090 --> 00:46:13,400
Так что это массив указателей.

600
00:46:13,400 --> 00:46:18,350
На самом деле, если мы масштаб, и мы посмотрим, что тут происходит

601
00:46:18,350 --> 00:46:23,140
В презентации, вы видите, что фактические элементы, характер данных

602
00:46:23,140 --> 00:46:26,180
не хранится в массиве себя.

603
00:46:26,180 --> 00:46:42,690
Что хранится в нашем массиве здесь являются указателями на символьные данные.

604
00:46:42,690 --> 00:46:52,560
Хорошо. Таким образом, мы видели, как размер очереди такой же, как со стеком,

605
00:46:52,560 --> 00:46:58,670
Размер всегда с уважением относится к числу элементов в настоящее время в очереди.

606
00:46:58,670 --> 00:47:02,720
После того, как 2 ставит в очередь, размер 2.

607
00:47:02,720 --> 00:47:07,110
После того, как из очереди размере Сейчас 1.

608
00:47:07,110 --> 00:47:09,330
После того, как другой постановки в очередь Размер обратно до 2.

609
00:47:09,330 --> 00:47:12,340
Так что размер, безусловно уважает число элементов в очереди,

610
00:47:12,340 --> 00:47:15,580
, а затем голову просто держит на велосипеде.

611
00:47:15,580 --> 00:47:20,210
Это идет от 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
И каждый раз, когда мы называем из очереди, руководитель получает указатель увеличится к следующему индексу.

613
00:47:25,620 --> 00:47:29,930
И если голова собирается переходить, он возвращается назад около 0.

614
00:47:29,930 --> 00:47:34,870
Так с этим, мы можем написать функцию из очереди.

615
00:47:34,870 --> 00:47:40,200
И мы собираемся оставить функцию постановки в очередь для вас, ребята, а не для реализации.

616
00:47:40,200 --> 00:47:45,880
>> Когда мы из очереди элемента из нашей очереди,

617
00:47:45,880 --> 00:47:55,490
то, что было первое, что сделал Даниил, когда мы начали писать поп-функции для стеков?

618
00:47:55,490 --> 00:48:00,490
Дай мне услышать от кого-то, кто не говорил еще.

619
00:48:00,490 --> 00:48:06,710
Давайте посмотрим, Саад, ты помнишь, что Даниэль сделал так, как первое, что когда он писал поп?

620
00:48:06,710 --> 00:48:08,860
[Саад] Там было, это было - >> Он испытал что-то.

621
00:48:08,860 --> 00:48:12,140
[Саад] Если размер больше, чем 0. >> Именно так.

622
00:48:12,140 --> 00:48:14,390
И то, что было, что тестирование на?

623
00:48:14,390 --> 00:48:19,090
[Саад] Это было испытание, чтобы посмотреть, есть ли что-нибудь внутри массива.

624
00:48:19,090 --> 00:48:23,210
[Хардисон] Да. Именно так. Таким образом, вы не можете поп что-нибудь из стека, если она пуста.

625
00:48:23,210 --> 00:48:26,510
Кроме того, вы не можете ничего из очереди из очереди, если она пуста.

626
00:48:26,510 --> 00:48:30,420
Что такое первое, что мы должны сделать в нашей йедиеие функции здесь, как вы думаете?

627
00:48:30,420 --> 00:48:33,860
[Саад] Если размер больше 0? >> Да.

628
00:48:33,860 --> 00:48:37,710
В этом случае, я на самом деле просто проверял, чтобы увидеть, если она равна 0.

629
00:48:37,710 --> 00:48:42,240
Если он равен 0, мы можем вернуться нулевой.

630
00:48:42,240 --> 00:48:45,280
Но точно такая же логика.

631
00:48:45,280 --> 00:48:49,110
И давайте продолжим с этим.

632
00:48:49,110 --> 00:48:54,600
Если размер не равен 0, где находится элемент, который мы хотим из очереди?

633
00:48:54,600 --> 00:48:58,550
[Саад] В голове? >> Именно так.

634
00:48:58,550 --> 00:49:01,720
Мы можем просто взять и вынуть первый элемент в нашей очереди

635
00:49:01,720 --> 00:49:07,040
при обращении к элементу в голову.

636
00:49:07,040 --> 00:49:14,630
Ничего не сумасшедший.

637
00:49:14,630 --> 00:49:19,620
После этого, что мы должны делать? Что должно произойти?

638
00:49:19,620 --> 00:49:23,740
Какова была другая вещь, о которых мы говорили в йедиеие?

639
00:49:23,740 --> 00:49:28,130
Две вещи должны произойти, потому что наша очередь изменился.

640
00:49:28,130 --> 00:49:35,640
[Даниил] Уменьшение размера. >> Мы должны уменьшить размер и увеличить голову? Именно так.

641
00:49:35,640 --> 00:49:40,600
Для увеличения головы, мы не можем слепо увеличить голову, помню.

642
00:49:40,600 --> 00:49:45,080
Мы не можем просто сделать queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Мы должны также включать этот мод по мощности.

644
00:49:51,630 --> 00:49:54,740
И почему мы мода на мощность, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Потому что он имеет, чтобы обернуть вокруг. >> Именно так.

646
00:49:58,680 --> 00:50:04,750
Мы мод по мощности, поскольку она имеет обернуть обратно к 0.

647
00:50:04,750 --> 00:50:07,400
Так вот, на данный момент, мы можем делать то, что сказал Дэниел.

648
00:50:07,400 --> 00:50:12,700
Мы можем уменьшать размер.

649
00:50:12,700 --> 00:50:29,170
И тогда мы можем просто вернуть элемент, который был в начале очереди.

650
00:50:29,170 --> 00:50:34,000
Это выглядит рода угловатый на первый взгляд. Вы можете есть вопрос. Простите?

651
00:50:34,000 --> 00:50:37,260
>> [Сэм] Почему это сначала в начало очереди? Где это пойти?

652
00:50:37,260 --> 00:50:42,480
[Хардисон] Оно происходит от четвертой строке снизу.

653
00:50:42,480 --> 00:50:46,060
После того как мы проверить, чтобы убедиться, что наша очередь не пуста,

654
00:50:46,060 --> 00:50:54,100
Мы вытащить символ * Во-первых, мы вытащить элемент, который сидит во главе индекса

655
00:50:54,100 --> 00:50:58,680
нашего массива, наши строк массива, >> и вызов, который в первую очередь?

656
00:50:58,680 --> 00:51:04,500
[Хардисон] И мы называем это в первую очередь. Да.

657
00:51:04,500 --> 00:51:09,850
Просто следить за что, почему вы думаете, мы должны были это сделать?

658
00:51:09,850 --> 00:51:18,270
[Сэм] Каждый первый просто возвращение q.strings [q.head]? >> Да.

659
00:51:18,270 --> 00:51:23,830
>> Потому что мы делаем это изменение q.head с модом функции,

660
00:51:23,830 --> 00:51:27,810
и нет никакого способа сделать это в обратной линии тоже.

661
00:51:27,810 --> 00:51:31,640
[Хардисон] Именно так. Ты пятно на. Сэм совершенно местом на.

662
00:51:31,640 --> 00:51:36,800
Причина мы должны были вытащить первый элемент в нашей очереди и сохранить его в переменную

663
00:51:36,800 --> 00:51:43,030
потому, что это линия, где мы только что q.head,

664
00:51:43,030 --> 00:51:47,030
есть мод оператора там не то, что мы можем сделать

665
00:51:47,030 --> 00:51:51,230
и она вступит в силу на голове без - в одну линию.

666
00:51:51,230 --> 00:51:54,480
Таким образом, мы на самом деле нужно вытащить первый элемент, а затем настроить голову,

667
00:51:54,480 --> 00:52:00,430
изменить размер, а затем вернуть элемент, который мы вытащили.

668
00:52:00,430 --> 00:52:02,680
И это то, что мы увидим придумали позже

669
00:52:02,680 --> 00:52:04,920
связанные списки, как мы поиграть с ними.

670
00:52:04,920 --> 00:52:08,410
Часто, когда вы освобождении или утилизации связанные списки

671
00:52:08,410 --> 00:52:13,500
Вы должны помнить, следующий элемент, следующий указатель связанный список

672
00:52:13,500 --> 00:52:16,330
Перед утилизацией текущего.

673
00:52:16,330 --> 00:52:23,580
Потому что в противном случае вы выбросите информацию о том, что осталось в списке.

674
00:52:23,580 --> 00:52:34,160
Теперь, если вы идете в прибор, вы откроете queue.c--х из этого.

675
00:52:34,160 --> 00:52:39,390
Так что, если я открываю queue.c, позвольте мне увеличить здесь,

676
00:52:39,390 --> 00:52:44,970
Вы увидите, что у вас есть подобный вид файла.

677
00:52:44,970 --> 00:52:49,200
Похожие вид файла, что мы имели раньше с stack.c.

678
00:52:49,200 --> 00:52:54,690
У нас есть наша структура для очереди определяется так же, как мы видели на слайдах.

679
00:52:54,690 --> 00:52:59,870
>> У нас есть поставить в очередь функцию, которая для вас сделать.

680
00:52:59,870 --> 00:53:04,340
А у нас из очереди функций здесь.

681
00:53:04,340 --> 00:53:06,870
Йедиеие функции в файле невыполненными,

682
00:53:06,870 --> 00:53:13,230
Но я положу его обратно на PowerPoint, так что вы можете ввести его, если вы хотите.

683
00:53:13,230 --> 00:53:16,690
Таким образом, в течение следующих 5 минут или около того, вы, ребята работают на постановки в очередь

684
00:53:16,690 --> 00:53:22,570
которая почти прямо противоположна из очереди.

685
00:53:22,570 --> 00:53:29,560
Вы не должны регулировать голову, когда вы enqueueing, но то, что вы должны настроить?

686
00:53:29,560 --> 00:53:38,920
Размер. Итак, когда вы постановки в очередь, голова остается нетронутой, размер не меняется.

687
00:53:38,920 --> 00:53:46,920
Но для этого надо немного - вам придется поиграть с этим мод

688
00:53:46,920 --> 00:53:57,560
, чтобы выяснить точно, что индекс нового элемента должно быть вставлен в.

689
00:53:57,560 --> 00:54:03,080
Поэтому я дам вам, ребята немного, положил обратно из очереди на слайде,

690
00:54:03,080 --> 00:54:05,200
и как вы, ребята, есть вопросы, кричать их, так что мы можем

691
00:54:05,200 --> 00:54:09,220
все разговоры о них как о группе.

692
00:54:09,220 --> 00:54:13,960
Кроме того, с размером вы не - при настройке размера, вы всегда можете просто -

693
00:54:13,960 --> 00:54:18,720
Вы должны мода размер когда-либо? [Даниил] Нет >> Вы не должны мода размера, правы.

694
00:54:18,720 --> 00:54:24,260
Поскольку размер будет всегда, если вы - предполагается, что вы все правильно управлять,

695
00:54:24,260 --> 00:54:30,840
Размер всегда будет между 0 и 3.

696
00:54:30,840 --> 00:54:38,680
Где вы должны мода, когда вы делаете постановки в очередь?

697
00:54:38,680 --> 00:54:41,060
[Студент] Только для головы. >> Только за голову, точно.

698
00:54:41,060 --> 00:54:44,620
И почему вы должны мода на все постановки в очередь?

699
00:54:44,620 --> 00:54:48,830
Когда ситуация, в которой вам придется мода?

700
00:54:48,830 --> 00:54:53,630
[Студент] Если у вас есть вещи в пространстве, как на пространствах 1 и 2,

701
00:54:53,630 --> 00:54:55,950
, а затем вам нужно добавить что-то в 0.

702
00:54:55,950 --> 00:55:02,570
[Хардисон] Да, именно так. Таким образом, если ваша голова указатель находится в самом конце,

703
00:55:02,570 --> 00:55:14,210
или если ваш размер плюс ваша голова больше, или, скорее, будет обернуть вокруг очереди.

704
00:55:14,210 --> 00:55:17,830
>> Таким образом, в этой ситуации, что мы получили здесь, на слайде прямо сейчас,

705
00:55:17,830 --> 00:55:24,370
если я хочу что-то поставить в очередь прямо сейчас,

706
00:55:24,370 --> 00:55:31,110
Мы хотим поставить в очередь что-то по индексу 0.

707
00:55:31,110 --> 00:55:35,450
Так что если вы посмотрите, где в 50 идет, и я призываю епдиеие 50,

708
00:55:35,450 --> 00:55:40,840
она идет там на дне. Он идет в индекс 0.

709
00:55:40,840 --> 00:55:44,160
Он заменяет «привет», которая уже была удалена из очереди.

710
00:55:44,160 --> 00:55:46,210
[Даниил] Не вы заботитесь о том, что в йедиеие уже?

711
00:55:46,210 --> 00:55:50,550
Почему он ничего сделать с головой постановки в очередь?

712
00:55:50,550 --> 00:55:55,770
[Хардисон] Ах, так вы не изменив головой, извините.

713
00:55:55,770 --> 00:56:02,310
Но вы должны использовать мод оператора, когда вы обращаетесь

714
00:56:02,310 --> 00:56:04,250
элемент, который вы хотите поставить в очередь, когда вы обращаетесь

715
00:56:04,250 --> 00:56:06,960
Следующий элемент в очереди.

716
00:56:06,960 --> 00:56:10,960
[Василий] я этого не сделал, и я получил "Успех" там.

717
00:56:10,960 --> 00:56:13,370
[Даниил] О, я понимаю, что вы говорите.

718
00:56:13,370 --> 00:56:16,240
[Хардисон] Таким образом, вы didn't - вы только что сделали в q.size?

719
00:56:16,240 --> 00:56:20,670
[Василий] Да. Я просто перешла на другую сторону, я ничего не делал с головой.

720
00:56:20,670 --> 00:56:24,300
[Хардисон] Вы на самом деле не имеют для сброса головой быть что угодно,

721
00:56:24,300 --> 00:56:31,650
но когда вы индекс в массиве строк,

722
00:56:31,650 --> 00:56:39,500
Вы на самом деле нужно идти вперед и вычислить, где следующий элемент,

723
00:56:39,500 --> 00:56:44,230
потому что лоза стека, следующий элемент в стеке всегда была

724
00:56:44,230 --> 00:56:48,740
на индекс, соответствующий размер.

725
00:56:48,740 --> 00:56:55,850
Если мы оглянемся назад в нашем функцией нажатия стека,

726
00:56:55,850 --> 00:57:03,100
Мы всегда мог швырнуть в нашем новом элементе права на размер индекса.

727
00:57:03,100 --> 00:57:06,710
В то время как с очередью, мы не можем сделать это

728
00:57:06,710 --> 00:57:10,340
потому что, если мы в этой ситуации,

729
00:57:10,340 --> 00:57:18,130
если мы в очереди 50 наших новая строка будет идти прямо на строки [1]

730
00:57:18,130 --> 00:57:20,540
которые мы не хотим делать.

731
00:57:20,540 --> 00:57:41,200
Мы хотим, чтобы новая строка пойти на индекс 0.

732
00:57:41,200 --> 00:57:44,320
>> Кто-нибудь - да? [Студент] У меня есть вопрос, но это на самом деле не связаны между собой.

733
00:57:44,320 --> 00:57:48,160
Что это значит, когда кто-то просто вызывает что-то вроде PRED указатель?

734
00:57:48,160 --> 00:57:51,260
Что это название сокращенно? Я знаю, это просто название.

735
00:57:51,260 --> 00:57:59,110
[Хардисон] Pred указатель? Давайте посмотрим. В каком контексте?

736
00:57:59,110 --> 00:58:01,790
[Студент] Это было для вставки. Я могу задать вам позже, если вы хотите

737
00:58:01,790 --> 00:58:03,920
потому что это на самом деле не связаны, но я просто -

738
00:58:03,920 --> 00:58:07,300
[Хардисон] Из вставки кода Давид из лекции?

739
00:58:07,300 --> 00:58:10,860
Мы можем тянуть, что и говорить об этом.

740
00:58:10,860 --> 00:58:15,550
Мы поговорим об этом в следующий, как только мы доберемся до связанных списков.

741
00:58:15,550 --> 00:58:21,440
>> Так что давайте действительно быстро взглянуть на то, что функция постановки в очередь выглядит.

742
00:58:21,440 --> 00:58:26,530
Какой была первая вещь, которую люди пытались сделать в вашей постановки в очередь строки? В этой очереди?

743
00:58:26,530 --> 00:58:29,960
Как и то, что вы сделали для стека нажатием.

744
00:58:29,960 --> 00:58:32,080
Что вы делали, Стелла?

745
00:58:32,080 --> 00:58:35,050
[Stella, неразборчиво]

746
00:58:35,050 --> 00:58:45,700
[Хардисон] Именно так. Если (q.size == вместимости) -

747
00:58:45,700 --> 00:58:54,720
Мне нужно поставить мою скобки в нужном месте - вернуться ложным.

748
00:58:54,720 --> 00:59:01,370
Увеличить немного. Хорошо.

749
00:59:01,370 --> 00:59:03,800
Теперь то, что следующая вещь, которую мы должны были сделать?

750
00:59:03,800 --> 00:59:11,370
Так же, как со стеком, и вставляется в нужное место.

751
00:59:11,370 --> 00:59:16,010
И то, что было в нужном месте, чтобы вставить это?

752
00:59:16,010 --> 00:59:23,170
С стек это был размер индекса, с этим не совсем так.

753
00:59:23,170 --> 00:59:30,210
[Даниил] У меня есть q.head--или - q.strings? >> >> Да.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size мод качестве]?

755
00:59:40,470 --> 00:59:42,740
[Хардисон] Мы, вероятно, хотят поставить скобки вокруг этого

756
00:59:42,740 --> 00:59:48,830
так что мы получаем соответствующий приоритет и так вот cleart для всех.

757
00:59:48,830 --> 00:59:55,800
И установлено, что равны? Чтобы >> ул? Чтобы >> ул. Великий.

758
00:59:55,800 --> 01:00:00,160
А теперь то, что последняя вещь, которую мы должны сделать?

759
01:00:00,160 --> 01:00:06,780
Так же, как мы это делали в стеке. >> Приращение размера? >> Приращение размера.

760
01:00:06,780 --> 01:00:13,830
Boom. А затем, поскольку стартовый код только что вернулся ложной по умолчанию,

761
01:00:13,830 --> 01:00:27,460
Мы хотим изменить это верно, если все проходит и все идет хорошо.

762
01:00:27,460 --> 01:00:33,050
Хорошо. Это очень много информации для раздела.

763
01:00:33,050 --> 01:00:39,480
Мы не совсем закончена. Мы хотим говорить о действительно быстро односвязный списки.

764
01:00:39,480 --> 01:00:44,010
Я положу это так, мы можем вернуться к нему позже.

765
01:00:44,010 --> 01:00:50,850
Но давайте вернемся к нашей презентации всего за несколько слайдов.

766
01:00:50,850 --> 01:00:53,790
Так епдиеие является TODO, теперь мы сделали это.

767
01:00:53,790 --> 01:00:57,430
>> Теперь давайте взглянем на односвязный списки.

768
01:00:57,430 --> 01:01:00,040
Мы говорили об этом немного больше в лекции.

769
01:01:00,040 --> 01:01:02,540
Как многие из вас, ребята увидели демо, где у нас были люди

770
01:01:02,540 --> 01:01:08,220
неловко указывая друг к другу и проведение цифры? >> Я была в этом.

771
01:01:08,220 --> 01:01:16,620
>> Что вы думаете, ребята? Разве что, как мы надеемся прояснить это немного?

772
01:01:16,620 --> 01:01:25,990
В списке, то получается, что мы имеем дело с этим типом, который мы будем называть узлом.

773
01:01:25,990 --> 01:01:32,520
В то время как с очередью и стеком у нас были структуры, которые мы назвали бы очереди в стеке,

774
01:01:32,520 --> 01:01:34,860
у нас были эти новые очереди в стеке типа,

775
01:01:34,860 --> 01:01:39,240
Здесь список на самом деле просто состоит из кучу узлов.

776
01:01:39,240 --> 01:01:45,920
Таким же образом, что строки просто набор символов все выстроились рядом друг с другом.

777
01:01:45,920 --> 01:01:50,650
Связанный список всего узла и другой узел, а другой узел, а другой узел.

778
01:01:50,650 --> 01:01:55,080
И вместо того, разбив все узлы вместе, и хранить их непрерывно

779
01:01:55,080 --> 01:01:58,090
все рядом друг с другом в памяти,

780
01:01:58,090 --> 01:02:04,470
с этой следующий указатель позволяет хранить узлах, где, в случайном порядке.

781
01:02:04,470 --> 01:02:10,500
А потом вроде проводов их все вместе, чтобы указать от одного к другому.

782
01:02:10,500 --> 01:02:15,850
>> И то, что было большим преимуществом, что это было более чем массив?

783
01:02:15,850 --> 01:02:21,680
За хранение все непрерывно просто застрял рядом друг с другом?

784
01:02:21,680 --> 01:02:24,190
Вы помните? Да? >> Динамическое распределение памяти?

785
01:02:24,190 --> 01:02:27,220
>> Динамическое распределение памяти в каком смысле?

786
01:02:27,220 --> 01:02:31,780
[Студент], что вы можете сделать его еще больше, и вы не должны переместить весь массив?

787
01:02:31,780 --> 01:02:40,940
[Хардисон] Именно так. Таким образом, с массивом, когда вы хотите поставить новый элемент в середине,

788
01:02:40,940 --> 01:02:45,320
Вы должны перейти все, чтобы освободить место.

789
01:02:45,320 --> 01:02:47,880
И, как мы говорили с очередью,

790
01:02:47,880 --> 01:02:50,080
Вот почему мы держим голову, что указатель,

791
01:02:50,080 --> 01:02:52,050
так что мы не постоянно меняются вещи.

792
01:02:52,050 --> 01:02:54,520
Потому что становится дорогим, если у вас есть большой массив

793
01:02:54,520 --> 01:02:57,130
и вы постоянно делаете эти случайные вставки.

794
01:02:57,130 --> 01:03:00,820
В то время как со списком, все что вам нужно сделать, это выбросить его на новый узел,

795
01:03:00,820 --> 01:03:06,330
настроить указатели, и вы сделали.

796
01:03:06,330 --> 01:03:10,940
Что сосет по этому поводу?

797
01:03:10,940 --> 01:03:16,830
Помимо того, что это не так просто, как работать с массивом? Да?

798
01:03:16,830 --> 01:03:22,980
[Даниил] Ну, я думаю, это гораздо труднее получить доступ к определенному элементу в связанном списке?

799
01:03:22,980 --> 01:03:30,470
[Хардисон] Вы не можете просто перейти к произвольному элементу в середине вашего связанного списка.

800
01:03:30,470 --> 01:03:33,800
Как вы должны это сделать вместо этого? >> Вы должны пошагово всю вещь.

801
01:03:33,800 --> 01:03:35,660
[Хардисон] Да. Вы должны пройти по одному, по одному за раз.

802
01:03:35,660 --> 01:03:38,480
Это огромная - это боль.

803
01:03:38,480 --> 01:03:41,550
Что с другой - есть еще один крушение к этому.

804
01:03:41,550 --> 01:03:45,340
[Василий] Вы не можете пойти вперед и назад? Вы должны идти в одном направлении?

805
01:03:45,340 --> 01:03:48,570
[Хардисон] Да. Так как же нам решить, что иногда?

806
01:03:48,570 --> 01:03:53,370
[Василий] двунаправленного списков? >> Именно так. Есть дважды связанные списки.

807
01:03:53,370 --> 01:03:55,540
Есть также - жаль?

808
01:03:55,540 --> 01:03:57,620
>> [Сэм] Это то же самое, что и использование PRED то, что -

809
01:03:57,620 --> 01:04:01,090
Я только что вспомнил, это не то, что PRED вещь, это?

810
01:04:01,090 --> 01:04:05,850
Разве это не между двух-и поодиночке?

811
01:04:05,850 --> 01:04:10,020
[Хардисон] Давайте посмотрим, что именно он делает.

812
01:04:10,020 --> 01:04:15,760
Таким образом, здесь мы идем. Вот список кода.

813
01:04:15,760 --> 01:04:25,620
Здесь мы имеем predptr, здесь. Это то, что вы говорите?

814
01:04:25,620 --> 01:04:30,750
Так что это было - он освобождая список, и он пытается сохранить указатель на него.

815
01:04:30,750 --> 01:04:35,000
Это не дважды, отдельно связанные списки.

816
01:04:35,000 --> 01:04:40,090
Мы можем поговорить об этом позже, так как это говорит об освобождении список

817
01:04:40,090 --> 01:04:42,900
и я хочу показать некоторые другие вещи первой.

818
01:04:42,900 --> 01:04:51,480
но это просто - это помнить значение PTR

819
01:04:51,480 --> 01:04:54,170
[Студент] О, это предыдущей указатель? >> Да.

820
01:04:54,170 --> 01:05:04,070
Так что мы можем увеличить PTR себя, прежде чем мы тогда бесплатно, что является predptr.

821
01:05:04,070 --> 01:05:09,130
Поскольку мы не можем бесплатно PTR, а затем вызвать PTR = PTR дальше, не так ли?

822
01:05:09,130 --> 01:05:11,260
Это было бы плохо.

823
01:05:11,260 --> 01:05:20,940
Итак, давайте посмотрим, вернемся к этому парню.

824
01:05:20,940 --> 01:05:23,900
>> Другие плохие вещи о списках является то, что в то время как с массивом

825
01:05:23,900 --> 01:05:26,520
мы просто должны все сами элементы уложены рядом друг с другом,

826
01:05:26,520 --> 01:05:29,050
Здесь мы также ввели этот указатель.

827
01:05:29,050 --> 01:05:34,060
Так что есть дополнительный блок памяти, что мы прибегая к использованию

828
01:05:34,060 --> 01:05:37,910
для каждого элемента, что мы хранении в нашем списке.

829
01:05:37,910 --> 01:05:40,030
Мы получаем гибкость, но это связано с определенными затратами.

830
01:05:40,030 --> 01:05:42,230
Он поставляется с этим затраты времени,

831
01:05:42,230 --> 01:05:45,270
и он приходит с этой памятью стоимость тоже.

832
01:05:45,270 --> 01:05:47,800
Время в том смысле, что мы теперь должны пройти через каждый элемент массива

833
01:05:47,800 --> 01:05:58,670
чтобы найти тот, с индексом 10, или, что было бы индекс 10 в массиве.

834
01:05:58,670 --> 01:06:01,230
>> Просто очень быстро, когда мы диаграмму из этих списков,

835
01:06:01,230 --> 01:06:05,980
Обычно мы проводим на голову списка или первый указатель списка

836
01:06:05,980 --> 01:06:08,010
и отметить, что это является истинным указателем.

837
01:06:08,010 --> 01:06:11,100
Это просто 4 байт. Это не самого узла.

838
01:06:11,100 --> 01:06:17,120
Таким образом, вы видите, что он не имеет целочисленное значение в ней, не следующего указателя в нем.

839
01:06:17,120 --> 01:06:20,790
Это буквально указатель.

840
01:06:20,790 --> 01:06:23,550
Это будет указывать на то, что фактическая структура узла.

841
01:06:23,550 --> 01:06:28,480
[Сэм] указатель называется узел? >> Это - нет. Это указатель на что-то типа узла.

842
01:06:28,480 --> 01:06:32,540
Это указатель на узел структуры. >> Ну, ладно.

843
01:06:32,540 --> 01:06:36,870
Диаграмма слева, код справа.

844
01:06:36,870 --> 01:06:42,190
Мы можем установить его в нуль, который является хорошим способом для начала.

845
01:06:42,190 --> 01:06:49,850
При схеме, вы либо написать его в качестве нулевого или вы положите линии, проходящей через это так.

846
01:06:49,850 --> 01:06:53,910
>> Один из самых простых способов работы со списками,

847
01:06:53,910 --> 01:06:57,430
и мы просим Вас как добавляем и добавляем увидеть различия между ними,

848
01:06:57,430 --> 01:07:01,320
но добавляя, безусловно, легче.

849
01:07:01,320 --> 01:07:05,790
Когда вы предварять, это, где вы - когда вы добавляем (7),

850
01:07:05,790 --> 01:07:10,050
Вы идете и создать узел структуры

851
01:07:10,050 --> 01:07:13,870
и вы установили первым указал на это, потому что сейчас, так как мы добавляется его,

852
01:07:13,870 --> 01:07:17,240
это будет в начале списка.

853
01:07:17,240 --> 01:07:22,540
Если мы добавляем (3), что создает еще один узел, но теперь 3 идет до 7.

854
01:07:22,540 --> 01:07:31,130
Таким образом, мы существенно нажатием вещи на нашем списке.

855
01:07:31,130 --> 01:07:34,720
Теперь вы можете видеть, что начало, конец, иногда люди называют его толкать,

856
01:07:34,720 --> 01:07:39,600
потому что вы нажимаете новый элемент на вашем списке.

857
01:07:39,600 --> 01:07:43,270
Это также легко удалить в передней части списка.

858
01:07:43,270 --> 01:07:45,650
Таким образом, люди часто называют это поп-музыки.

859
01:07:45,650 --> 01:07:52,200
И в этом случае, вы можете эмулировать стек с помощью связанного списка.

860
01:07:52,200 --> 01:07:57,880
Возгласы. К сожалению, сейчас мы входим в добавление. И вот мы добавляется (7), теперь мы добавляем (3).

861
01:07:57,880 --> 01:08:02,600
Если добавляется что-то еще на этот список, если мы добавляется (4),

862
01:08:02,600 --> 01:08:06,540
Затем мы должны были бы 4, а затем 3, а затем 7.

863
01:08:06,540 --> 01:08:14,220
И тогда мы могли бы поп-и удалить 4, удалить 3, удалить 7.

864
01:08:14,220 --> 01:08:16,500
Часто более интуитивный способ думать об это с добавление.

865
01:08:16,500 --> 01:08:20,310
Так что я диаграмме, что она будет выглядеть с добавить здесь.

866
01:08:20,310 --> 01:08:23,380
Здесь прилагается (7) не выглядит по-другому

867
01:08:23,380 --> 01:08:25,160
потому что есть только один элемент в списке.

868
01:08:25,160 --> 01:08:28,620
И добавления (3) ставит его в конце.

869
01:08:28,620 --> 01:08:31,020
Может быть, вы можете увидеть прямо сейчас трюк с добавление

870
01:08:31,020 --> 01:08:36,600
является то, что, так как мы только знаем, где в начале списка,

871
01:08:36,600 --> 01:08:39,450
добавить в список, нужно пройти весь путь до конца списка

872
01:08:39,450 --> 01:08:46,500
чтобы добраться до конца, остановить, а затем построить свой узел и бухнуть все вниз.

873
01:08:46,500 --> 01:08:50,590
Соедините все вещи вверх.

874
01:08:50,590 --> 01:08:55,170
Так что с начало, конец, как мы только что разорвал это действительно быстро,

875
01:08:55,170 --> 01:08:58,170
При предварять в список, это довольно просто.

876
01:08:58,170 --> 01:09:02,960
>> Вы делаете свой новый узел, включают некоторые динамического распределения памяти.

877
01:09:02,960 --> 01:09:09,830
Итак, вот что мы делаем узел структуры использованием таНос.

878
01:09:09,830 --> 01:09:14,710
Так таНос мы используем, потому что будет выделено памяти для нас, для последующего

879
01:09:14,710 --> 01:09:20,350
потому что мы не хотим этого - мы хотим, чтобы эта память сохранится в течение длительного времени.

880
01:09:20,350 --> 01:09:25,350
И мы получаем указатель на место в памяти, что мы просто выделены.

881
01:09:25,350 --> 01:09:29,260
Мы используем размер узла, мы не подвести поля.

882
01:09:29,260 --> 01:09:31,899
Мы не вручную генерировать количество байтов,

883
01:09:31,899 --> 01:09:39,750
вместо этого мы используем SizeOf, так что мы знаем, мы получаем соответствующее количество байтов.

884
01:09:39,750 --> 01:09:43,660
Мы заботимся о том, чтобы проверить, что наш таНос вызова удалось.

885
01:09:43,660 --> 01:09:47,939
Это то, что вы хотите сделать в целом.

886
01:09:47,939 --> 01:09:52,590
На современных машинах, уходит из памяти это не то, что легко

887
01:09:52,590 --> 01:09:56,610
если вы выделении тонны материала и вносят огромный список,

888
01:09:56,610 --> 01:10:02,220
Но если вы строите вещи, скажем, как iPhone или Android,

889
01:10:02,220 --> 01:10:05,230
у вас есть ограниченность ресурсов памяти, особенно если вы делаете что-то интенсивно.

890
01:10:05,230 --> 01:10:08,300
Так что это хорошо, чтобы получить на практике.

891
01:10:08,300 --> 01:10:10,510
>> Обратите внимание, что я использовал несколько различных функций здесь

892
01:10:10,510 --> 01:10:12,880
что вы видели, что это своего рода новое.

893
01:10:12,880 --> 01:10:15,870
Так Fprintf такой же, как Printf

894
01:10:15,870 --> 01:10:21,320
кроме ее первый аргумент является поток, в который вы хотите напечатать.

895
01:10:21,320 --> 01:10:23,900
В этом случае, мы хотим, чтобы печатать на стандартную строку ошибки

896
01:10:23,900 --> 01:10:29,410
, который отличается от стандартного outstream.

897
01:10:29,410 --> 01:10:31,620
По умолчанию она появляется в том же месте.

898
01:10:31,620 --> 01:10:34,600
Она также выводит на терминал, а можно -

899
01:10:34,600 --> 01:10:38,790
с помощью этих команд вы узнали о, методы перенаправления

900
01:10:38,790 --> 01:10:42,290
Вы узнали о в видео Томми проблемой для множества 4, Вы можете направлять ее

901
01:10:42,290 --> 01:10:47,900
в различных областях, а затем выйти, прямо здесь, выходит вашу программу.

902
01:10:47,900 --> 01:10:50,440
Это, по существу, как возвращался из главных,

903
01:10:50,440 --> 01:10:53,600
за исключением мы используем выход, потому что здесь возвращение не будет ничего делать.

904
01:10:53,600 --> 01:10:57,140
Мы не в основной, так что возвращаться не выйти из программы, как мы хотим.

905
01:10:57,140 --> 01:11:03,020
Поэтому мы используем функцию выхода и дать ему код ошибки.

906
01:11:03,020 --> 01:11:11,890
Тогда здесь мы устанавливаем значение нового узла поля, его я поля равным я, а потом подключить его.

907
01:11:11,890 --> 01:11:15,530
Мы установили следующий указатель нового узла, чтобы указать на первый,

908
01:11:15,530 --> 01:11:20,460
, а затем первым будет указывать на новый узел.

909
01:11:20,460 --> 01:11:25,120
Эти первые строки кода, мы фактически строительство нового узла.

910
01:11:25,120 --> 01:11:27,280
Не две последние строки этой функции, но первый из них.

911
01:11:27,280 --> 01:11:30,290
Вы действительно можете выйти в функцию, во вспомогательную функцию.

912
01:11:30,290 --> 01:11:32,560
Это часто, что я делаю, я вытащить его в функцию,

913
01:11:32,560 --> 01:11:36,040
Я называю это что-то вроде узла сборки,

914
01:11:36,040 --> 01:11:40,410
и что держит добавляем функцию довольно небольшой, это просто 3 линии тогда.

915
01:11:40,410 --> 01:11:48,710
Я делаю вызов моей функции узла сборки, а потом я провода все вверх.

916
01:11:48,710 --> 01:11:51,970
>> Последнее, что я хочу показать вам,

917
01:11:51,970 --> 01:11:54,030
и я дам вам сделать добавление и все, что на свой собственный,

918
01:11:54,030 --> 01:11:57,500
как для перебора списка.

919
01:11:57,500 --> 01:12:00,780
Есть множество различных способов для перебора списка.

920
01:12:00,780 --> 01:12:03,140
В этом случае, мы собираемся, чтобы найти длину списка.

921
01:12:03,140 --> 01:12:06,570
Итак, мы начинаем с длиной = 0.

922
01:12:06,570 --> 01:12:11,580
Это очень похоже на написание StrLen для строки.

923
01:12:11,580 --> 01:12:17,780
Это то, что я хочу показать вам, это цикл прямо здесь.

924
01:12:17,780 --> 01:12:23,530
Это выглядит своего рода фанк, это не обычная Int я = 0, <что угодно, я + +.

925
01:12:23,530 --> 01:12:34,920
Вместо этого он инициализацию нашей переменной п будет в начале списка.

926
01:12:34,920 --> 01:12:40,620
И потом, когда наш итератор переменной не является нулевым, мы продолжаем.

927
01:12:40,620 --> 01:12:46,340
Это потому, что, по соглашению, в конце нашего списка будет нулевым.

928
01:12:46,340 --> 01:12:48,770
И тогда, чтобы увеличить, а не делать + +,

929
01:12:48,770 --> 01:12:57,010
Связанный список эквиваленте + + п = п-> дальше.

930
01:12:57,010 --> 01:13:00,410
>> Я дам вам заполнить пробелы здесь, потому что мы находимся вне времени.

931
01:13:00,410 --> 01:13:09,300
Но имейте это в виду, как вы работаете на psets spellr.

932
01:13:09,300 --> 01:13:11,650
Связанные списки, если вы реализуете хэш-таблицы,

933
01:13:11,650 --> 01:13:14,010
, безусловно, очень удобен.

934
01:13:14,010 --> 01:13:21,780
И с этой идиомой цикл над вещами сделает жизнь намного проще, надеюсь.

935
01:13:21,780 --> 01:13:25,910
Любые вопросы, быстро?

936
01:13:25,910 --> 01:13:28,920
[Сэм] Будете ли вы отправить заполненную SLL и ПК?

937
01:13:28,920 --> 01:13:38,360
[Хардисон] Да. Я буду посылать завершена слайды и завершил стек SLL и queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]