1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Раздел 6: по-малко удобни]

2
00:00:02,730 --> 00:00:05,040
[Нейт Hardison] [Харвардския университет]

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
Но те са наистина добре да се разбират един от големите основните структури от данни на КС.

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
говорим за моделиране удържат стека данни, използването на този вид структура.

26
00:01:46,730 --> 00:01:51,070
>> Така че това, което имаме тук, това е подобно на това, което беше представено в лекцията,

27
00:01:51,070 --> 00:01:58,120
освен в лекция ние представихме това с цели числа, за разлика от Чар * S.

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
[Даниел] Strings? >> Ние съхранявате конците в тази стека, точно така.

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
[Hardison] Да. Ние създаваме, ние сме като нашата масив структурата на данните -

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
, който ще бъде моя код, е просто да обяви структура, подредени структура, наречена S.

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
Той е нещо като обявяване вътр аз и да не го инициализиране.

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
[Стела] бутане и мак? >> Точно така.

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
[Hardison] Точно така. Така бутане избутва нещо на върха на стека.

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
[Student] размер. >> Да, променя размера.

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
[Student, неразбираем] >> И какво се случва тогава, когато натиснете нещо отново?

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
[Hardison] Точно така. Нашата комин, по същество, "забравил", че тя се държеше с нищо

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
[Hardison] Точно така. Това е - въпросът е, че това не е динамично growning стека.

141
00:09:56,750 --> 00:10:02,850
Това е комин, който може да побере най-много четири Чар * и, най-много четири неща.

142
00:10:02,850 --> 00:10:07,580
Ако бяхме да се опита да прокара Петото нещо, какво смятате, че трябва да се случи?

143
00:10:07,580 --> 00:10:11,870
[Студенти, неразбираеми]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Точно така. Има редица неща, които могат да се случат.

145
00:10:14,600 --> 00:10:19,330
Това би могло да Seg вина, в зависимост от това, което бяхме -

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
[Hardison Бинго. Хубава работа.

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]. >> Размер е един, точно така. Поддържа добавянето на размера,

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
[Student] Назад вярно. >> Назад вярно.

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
[Hardison] Да, точно така. Това е аргумент. >> О, добре. Извинете.

205
00:15:47,160 --> 00:15:49,470
[Hardison Ние сме посочва низ да прокара.

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
[Student, неразбираем]

267
00:20:20,080 --> 00:20:28,810
[Hardison] И така, какво се случва, ако направите това? [Student, неразбираем]

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
е, че този размер е намалял, от първо до две, след това на 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
>> Програмата работи и не Seg Faulting, отпечатване?

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
Даниел, какво е първото нещо, което си направил?

310
00:23:55,220 --> 00:23:58,850
Даниел] Ако s.size е по-голяма от 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison Добре. И защо го направи?

312
00:24:03,120 --> 00:24:05,610
Даниел] За да сте сигурни, че има нещо вътре в комина.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Точно така. Вие искате да тествате за да се уверите, че s.size е по-голяма от 0;

314
00:24:10,950 --> 00:24:13,280
по друг начин, какво искаш да се случи?

315
00:24:13,280 --> 00:24:16,630
Даниел Върни нула? >> Връщане нула, точно.

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
Стела] снижаване на размера? >> Снижаване на размера, добре.

319
00:24:31,210 --> 00:24:34,440
И така, как го направи? >> S.size -

320
00:24:34,440 --> 00:24:37,030
[Hardison Велики. И после какво си направил?

321
00:24:37,030 --> 00:24:44,140
[Stella] И тогава казах връщане s.string s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison Велики.

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
[Hardison] Plus 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
[Hardison И това е точно това, което ние говорим за това с целия този въпрос от 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
е, че това Postfix - те го наричат ​​Postfix, защото идва след 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
Да, Сам? >> Е по-бързо или да използвате по-малко RAM да се направи в един ред или не?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Честно казано, това наистина зависи.

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
за разлика от зареждане на размера променлива от RAM,

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
Имаме тази последна, първа, или LIFO, поръчване.

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
Добре. Да, Шарлот? Шарлот, неразбираем]

419
00:32:27,670 --> 00:32:32,660
[Hardison Това е чудесен въпрос, и това е този, който идва в лекция.

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
Ние enqueue "чао", той се облече.

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
Какво се случва в този момент, когато искаме да dequeue нещо?

438
00:33:56,330 --> 00:34:01,280
Когато искаме да dequeue, която е елемент, който искаме да dequeue?

439
00:34:01,280 --> 00:34:04,110
[Василий] Strings [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
[Hardison] Вид? Така че това, което се е случило, когато dequeued?

449
00:34:47,500 --> 00:34:54,340
Какво главата, че сега е интересен?

450
00:34:54,340 --> 00:34:56,449
[Шарлот] О, защото го променя - добре. Разбирам.

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
и след това изведнъж, ние започнем да правим един куп dequeue призовава всички в една линия,

465
00:36:00,060 --> 00:36:03,930
нещата наистина ще се забави, защото измества всичко постоянно.

466
00:36:03,930 --> 00:36:07,320
Знаеш ли, превключете от 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
>> Студентски] Как dequeue знам само поп всичко, което е в главата?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Как dequeue знаят как да гърмя, каквото е в главата? >> Точно така, да.

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
[Hardison] Така тя просто казва, добре, добре, елементът с индекс 0, низ "здрасти",

477
00:37:00,500 --> 00:37:03,050
е елемент начело на нашата опашка.

478
00:37:03,050 --> 00:37:05,570
Така че ние ще да dequeue този човек.

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
[Hardison Това се превръща в ново начало за нашия масив.

483
00:37:22,900 --> 00:37:28,930
Така че, когато dequeue нещо, всичко, което трябва да направите, е достъп до елемент в индекса q.head

484
00:37:28,930 --> 00:37:32,240
и това ще бъде елемент, който искате да dequeue.

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
Ние dequeue, и сега, ако ние enqueue отново,

488
00:37:46,520 --> 00:37:51,300
къде ние enqueue?

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
, В която индексът ще отиде? [Студенти] Strings [2]. >> Втора.

492
00:38:02,240 --> 00:38:04,980
Защо две, а не 0?

493
00:38:04,980 --> 00:38:13,570
[Василий] Защото сега на главата е едно, така че това е като в началото на списъка?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Точно така. И какво обозначава края на списъка?

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
Какво е края на нашия опашката? Студентите] Размер. >> Размер, точно така.

498
00:38:29,530 --> 00:38:36,360
Така че нашите нови елементи в размер, както и елементите, които ние приемаме изключване идват в главата.

499
00:38:36,360 --> 00:38:45,390
Когато enqueue следващия елемент, ние сме го поставя в размер.

500
00:38:45,390 --> 00:38:48,530
[Студентски] Преди да поставите, че макар размер е един, нали?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Точно така. Така че не е съвсем размер. Размер + не една, но + на главата.

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
>> [Student] Какво се случва, когато dequeue струни [0], и струнни слотове в паметта

506
00:39:25,780 --> 00:39:29,420
просто се изпразва, основно, или просто забравени?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Да. В този смисъл, ние просто ги забравя.

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
[Student] Така че това е един непрекъснат масив - >> Да.

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
[Hardison] Да, това е добра отправна точка.

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
Ние просто не се притеснява да ида и да го презапише, когато го dequeued.

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
Подходящото поведение, ако бяхме да се опитаме и първата dequeue нещо

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
И сега, ако ние се опитваме и enqueue нещо отново, да речем 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
[Hardison] Това не се случва автоматично. Вие трябва да направите по математика

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
[Hardison] е, ако можем да направим по математика работят правилно.

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
, когато ние enqueue нещо, нищо не се е случило в главата.

555
00:42:58,240 --> 00:43:00,970
Когато enqueued нещо друго, нищо не се е случило в главата.

556
00:43:00,970 --> 00:43:04,130
Веднага след като dequeued нещо, главата отива по един.

557
00:43:04,130 --> 00:43:06,600
Ние enqueued нещо, нищо не се случва в главата.

558
00:43:06,600 --> 00:43:11,060
, Когато dequeue нещо, изведнъж главата получава увеличава.

559
00:43:11,060 --> 00:43:14,660
, Когато enqueue нещо, нищо не се случва в главата.

560
00:43:14,660 --> 00:43:20,240
>> Какво ще се случи в този момент, ако бяхме да dequeue нещо отново?

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
ако бяхме да dequeue нещо друго?

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
Досега всеки път, когато се обадихме dequeue, ние сме били добавянето на един в главата,

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
Шарлот] Какво определя капацитета на опашката в комин?

572
00:44:09,900 --> 00:44:13,120
[Hardison] В този случай, ние току-що използва # дефинирана константа. >> Добре.

573
00:44:13,120 --> 00:44:19,590
[Hardison] В действителния файл в можете да отидете и мръсотия с малко

574
00:44:19,590 --> 00:44:21,710
и да я направи по-голям или малко, колкото искате.

575
00:44:21,710 --> 00:44:25,310
Шарлот] Така че, когато сте го прави на опашка, как да направите компютъра знам

576
00:44:25,310 --> 00:44:29,120
колко големи искате да стека?

577
00:44:29,120 --> 00:44:31,700
[Hardison Това е чудесен въпрос.

578
00:44:31,700 --> 00:44:34,800
Има няколко начина. Един от тях е просто да го определят отпред

579
00:44:34,800 --> 00:44:42,050
и да кажа това ще бъде опашка, която има четири елементи или 50 елементи или 10000.

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
>> Шарлот], така да отида с първия вариант, какъв синтаксис използвате

583
00:44:54,740 --> 00:44:57,830
да кажете на програмата, какъв е размерът на опашката?

584
00:44:57,830 --> 00:45:04,780
[Hardison 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
[Шарлот] О, помислих си аз капацитет означава капацитет за низ.

590
00:45:32,760 --> 00:45:36,770
[Hardison 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
Това е може би това, което сте виждали, когато сте били обявяване буфери за файла I / O,

597
00:46:01,690 --> 00:46:06,840
, когато сте били създаване струни ръчно на стека.

598
00:46:06,840 --> 00:46:09,090
Но това, което имаме тук е масив от Чар *.

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
След като две enqueues, размерът е 2.

607
00:47:02,720 --> 00:47:07,110
След вземане на dequeue размер е 1.

608
00:47:07,110 --> 00:47:09,330
След като направи още enqueue размер е до 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
И всеки път ние наричаме dequeue, показалеца на главата ще увеличи на следващия индекс.

613
00:47:25,620 --> 00:47:29,930
И ако главата е на път да премине, контури около 0.

614
00:47:29,930 --> 00:47:34,870
Така че с това, ние можем да напишем dequeue функция.

615
00:47:34,870 --> 00:47:40,200
И отиваме да напусне enqueue функция за вас, момчета да прилагат вместо.

616
00:47:40,200 --> 00:47:45,880
>> Когато dequeue елемент на нашата опашка,

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
[Hardison] Да. Точно така. Така че не може да изскочи нещо на комина, ако е празно.

625
00:48:23,210 --> 00:48:26,510
Също така, не може да dequeue нищо от опашката, ако тя е празна.

626
00:48:26,510 --> 00:48:30,420
Какво е първото нещо, което трябва да направите в нашата dequeue функция тук, не мислиш ли?

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, където е елемент, който искаме да dequeue?

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
Какво е другото нещо, което ние говорихме за dequeue?

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
И защо Министерството на отбраната от капацитета, Стела?

645
00:49:54,740 --> 00:49:58,680
Стела, защото тя трябва да обгърне. >> Точно така.

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
[Hardison Той идва от четвъртия ред отдолу.

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
[Hardison И ние го наричаме първа. Да.

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
[Hardison] Точно така. Ти си на място. Сам е напълно на място.

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
>> Ние имаме enqueue функция, която е да направя за вас.

680
00:52:59,870 --> 00:53:04,340
И ние имаме dequeue функция тук.

681
00:53:04,340 --> 00:53:06,870
Се dequeue функция във файла се прилагат,

682
00:53:06,870 --> 00:53:13,230
но аз ще го пуснат обратно на PowerPoint, така че можете да го напишете, ако искате.

683
00:53:13,230 --> 00:53:16,690
Така че за следващите 5 минути, или така, момчета работят по enqueue

684
00:53:16,690 --> 00:53:22,570
което е почти само обратното на dequeue.

685
00:53:22,570 --> 00:53:29,560
Вие не трябва да се коригира главата, когато сте enqueueing, но какво трябва да се коригира?

686
00:53:29,560 --> 00:53:38,920
Size. Така че, когато enqueue, главата остава недокосната, размерът се сменя.

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
Така че аз ще ви дам момчета малко, dequeue резервно копие на слайда,

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
Къде трябва да моден когато правиш enqueue?

697
00:54:38,680 --> 00:54:41,060
[Студент] Само за главата. >> Само за главата, точно така.

698
00:54:41,060 --> 00:54:44,620
И защо трябва да моден в enqueue?

699
00:54:44,620 --> 00:54:48,830
Кога е ситуация, в която ще трябва да мод?

700
00:54:48,830 --> 00:54:53,630
[Student] Ако имате неща в пространства, като в пространства 1 и 2,

701
00:54:53,630 --> 00:54:55,950
и след това ви е необходимо да се добави нещо на 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison Да, точно така. Така че, ако главата ти е позициониран в самия край,

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
ако искам да enqueue нещо точно сега,

706
00:55:24,370 --> 00:55:31,110
искаме да enqueue нещо с индекс 0.

707
00:55:31,110 --> 00:55:35,450
Така че, ако търсите къде 50 отива и аз наричам enqueue 50,

708
00:55:35,450 --> 00:55:40,840
той отива там на дъното. То върви индекс 0.

709
00:55:40,840 --> 00:55:44,160
Той замества "здрасти", която вече е била dequeued.

710
00:55:44,160 --> 00:55:46,210
Даниел] Да не можеш да се погрижи за това през dequeue вече?

711
00:55:46,210 --> 00:55:50,550
Защо го направя нещо с глава в enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] О, така че не сте модифициране на главата, съжалявам.

713
00:55:55,770 --> 00:56:02,310
Но вие трябва да използвате оператора на Министерството на отбраната, когато сте отворили

714
00:56:02,310 --> 00:56:04,250
елемент, който искате да enqueue при достъп

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
[Hardison] Значи ... ти направи в q.size?

719
00:56:16,240 --> 00:56:20,670
[Василий] Да. Току-що промених страни, аз не съм направил нищо с главата.

720
00:56:20,670 --> 00:56:24,300
[Hardison] не всъщност трябва да рестартирате главата, за да бъде нещо,

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
защото withe стека, следващият елемент в стака си винаги е бил

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
ако enqueued 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
[Hardison] Pred показалеца? Да видим. В какъв контекст?

736
00:57:59,110 --> 00:58:01,790
[Student] Това беше за вмъкване. Мога да ви попитам късно, ако искате

737
00:58:01,790 --> 00:58:03,920
, защото не е свързана, но аз просто -

738
00:58:03,920 --> 00:58:07,300
[Hardison] От въведете кода от лекция на Дейвид?

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
>> Така че нека наистина бързо погледнете какво прилича enqueue функция.

742
00:58:21,440 --> 00:58:26,530
Какво беше първото нещо, което хората се опитах да направя в enqueue си линия? В тази опашка?

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
Стела, неразбираем]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Точно така. Ако (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
[Hardison Вероятно искат да поставят скоби около

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
Така enqueue е 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
Като има предвид, че с опашката и стека имахме structs, че ние ще се обади опашка в стека,

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
[Student] В това можете да поддържате което го прави по-големи и не е нужно да преместите целия масив?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Точно така. Така че с масив, когато искате да поставите нов елемент в средата на

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
[Hardison] Не може просто да скочи до произволен елемент в средата на свързаното вашия списък.

800
01:03:30,470 --> 01:03:33,800
Как ли трябва да го направи вместо? >> Трябва да преминете през цялото нещо.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Да. Трябва да се мине през един по един, един по един.

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
[Hardison] Да. Е, как да решим, че понякога?

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
[Hardison] Нека да разгледаме какво точно е правил.

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
но това е просто - това е запомняне на стойността на паметта

819
01:04:51,480 --> 01:04:54,170
Студентски] О, това е предходната показалеца? >> Да.

820
01:04:54,170 --> 01:05:04,070
Така че тогава ще можем да увеличите паметта себе си, преди да сме свободни, какво predptr.

821
01:05:04,070 --> 01:05:09,130
Защото ние не можем безплатно паметта и след това се обадете 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
Така че тогава ще можем да се появи и премахване на четири, извадете 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 е точно като ФОРМАТ

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
Тогава ние стойност областта на нов възел, I областта да бъде равен да съм, и тогава ние го преведете.

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, I <каквото, аз + +.

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
свързан списък еквивалент на + + N = N-> Next.

930
01:12:57,010 --> 01:13:00,410
>> Аз ще ви позволи да попълнят пропуските тук, защото ние сме извън времето.

931
01:13:00,410 --> 01:13:09,300
Но имайте това предвид, докато работите върху вашите spellr psets.

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 и SC?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Да. Ще изпратя попълнени пързалки и SLL стека и queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]