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]