1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Седмица 6]

2
00:00:02,000 --> 00:00:04,000
[Дейвид Дж. Малан] [Харвардския университет]

3
00:00:04,000 --> 00:00:08,000
[Това е CS50. [CS50.TV]

4
00:00:08,000 --> 00:00:12,000
>> Това е CS50, и това е началото на Седмицата на 6,

5
00:00:12,000 --> 00:00:16,000
така няколко нови инструменти вече са на разположение, за да се възползват от

6
00:00:16,000 --> 00:00:19,000
първият от които се нарича CS50 Style.

7
00:00:19,000 --> 00:00:22,000
Коефициентите са, ако сте като мен или някоя от преподаването събратя,

8
00:00:22,000 --> 00:00:26,000
вие вероятно сте виждали програма, чийто стил изглежда малко нещо подобно.

9
00:00:26,000 --> 00:00:30,000
Може да започнете рязане някои ъгли, късно през нощта, или ще се справят с нея по-късно,

10
00:00:30,000 --> 00:00:32,000
и след това TF или Калифорния идва в работно време.

11
00:00:32,000 --> 00:00:34,000
След това за нас е трудно да се чете.

12
00:00:34,000 --> 00:00:38,000
Е, този код е синтактично правилно и ще се компилира и тя действително ще работи.

13
00:00:38,000 --> 00:00:40,000
Но това определено не е 5 за стил.

14
00:00:40,000 --> 00:00:45,000
>> Но сега, ако отидем в тази директория тук

15
00:00:45,000 --> 00:00:48,000
и забележите, че имам conditions2.c-

16
00:00:48,000 --> 00:00:55,000
и аз тичам тази нова команда, style50, този файл conditions2.c, Въведете,

17
00:00:55,000 --> 00:00:57,000
забележите, че той ме информира, че е стилизирана.

18
00:00:57,000 --> 00:01:00,000
Gedit забелязах, че файла е било променено на диск,

19
00:01:00,000 --> 00:01:08,000
и ако щракнете върху презареди, всичките си проблеми сега са автоматизирани.

20
00:01:08,000 --> 00:01:15,000
[Аплодисменти]

21
00:01:15,000 --> 00:01:17,000
Това е едно от нещата, които направихме през този уикенд.

22
00:01:17,000 --> 00:01:20,000
Осъзнайте, че е несъвършен, защото има някакъв код

23
00:01:20,000 --> 00:01:23,000
че тя просто не ще бъде в състояние да Stylize перфектно,

24
00:01:23,000 --> 00:01:26,000
но знайте, че сега това е инструмент, който можете да се възползвате от

25
00:01:26,000 --> 00:01:33,000
дори и само да спретнат на някои от най-errantly поставени фигурни скоби и други подобни.

26
00:01:33,000 --> 00:01:36,000
>> Но още по-убедителна в момента е CS50 Проверете.

27
00:01:36,000 --> 00:01:39,000
С CS50 Проверете, всъщност можете да изпълняват едни и същи тестове коректност

28
00:01:39,000 --> 00:01:42,000
на вашия собствен код, че преподавателските събратя са в състояние да.

29
00:01:42,000 --> 00:01:44,000
Това е помощна програма за команден ред, който идва сега в уреда

30
00:01:44,000 --> 00:01:46,000
веднага след като си направи update50 според

31
00:01:46,000 --> 00:01:49,000
pset 4 спецификации, както и да го използвате по същество по този начин.

32
00:01:49,000 --> 00:01:51,000
Изпълните командата check50.

33
00:01:51,000 --> 00:01:56,000
След това преминава в аргумент на командния ред, или по-известна като ключ или флаг.

34
00:01:56,000 --> 00:01:58,000
Като цяло, неща, които имат тирета се нарича ключ

35
00:01:58,000 --> 00:02:02,000
програма за команден ред, така че в уточнява

36
00:02:02,000 --> 00:02:04,000
проверките, които искате да изпълните.

37
00:02:04,000 --> 00:02:07,000
>> Тестове, които искате да изпълните, са идентифицирани по уникален начин чрез този низ,

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize.

39
00:02:10,000 --> 00:02:13,000
С други думи, това е просто произволно, но уникален низ

40
00:02:13,000 --> 00:02:18,000
, които ние използваме, за да може еднозначно да идентифицира коректност pset 4 тестове.

41
00:02:18,000 --> 00:02:21,000
И тогава сте задали, разделени с интервал списък на файловете, които искате да качите

42
00:02:21,000 --> 00:02:24,000
CS50 Проверка за анализ.

43
00:02:24,000 --> 00:02:29,000
Например, ако отида в моето решение тук за resize.c-

44
00:02:29,000 --> 00:02:31,000
нека се отвори по-голям терминал прозореца

45
00:02:31,000 --> 00:02:42,000
и отивам напред и тичам да се каже check50 в 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
и тогава ще отида напред и да посочи имената на файловете,

47
00:02:46,000 --> 00:02:49,000
resize.c, и след това натиснете Enter, го компресира,

48
00:02:49,000 --> 00:02:53,000
Тя качени, той проверява, и аз просто не успя цял куп тестове.

49
00:02:53,000 --> 00:02:59,000
В червено горе в ляво казва, че съществуват resize.c и BMP.

50
00:02:59,000 --> 00:03:01,000
Това беше тест. Това е въпросът, който попита.

51
00:03:01,000 --> 00:03:04,000
И това е нещастен, защото отговорът е невярна.

52
00:03:04,000 --> 00:03:08,000
Бял текст под него казва, че очаква bmp.h да съществува, и това е просто моя вина.

53
00:03:08,000 --> 00:03:11,000
Забравих да го качите, така че аз трябва да качите и двата файла,

54
00:03:11,000 --> 00:03:14,000
resize.c и bmp.h.

55
00:03:14,000 --> 00:03:17,000
Но сега да забележите, всички от другите тестове са в жълто, защото те не са работи,

56
00:03:17,000 --> 00:03:21,000
и така усмивка на лицето е вертикална, защото той не е нито щастлив, нито тъжен,

57
00:03:21,000 --> 00:03:25,000
но ние трябва да се поправи този въпрос в червено преди тези проверки ще се проведе.

58
00:03:25,000 --> 00:03:27,000
>> Позволете ми да поправя това.

59
00:03:27,000 --> 00:03:30,000
Нека я увеличите и повторение на това, този път с bmp.h

60
00:03:30,000 --> 00:03:34,000
на командния ред, Enter, и сега, ако всичко върви добре,

61
00:03:34,000 --> 00:03:38,000
е да се провери и след това се върнете в резултат на задръжте дъха си

62
00:03:38,000 --> 00:03:42,000
всичко зелено, което означава, че правя наистина и на pset 4 досега.

63
00:03:42,000 --> 00:03:44,000
Можете да видите и да се направи извод от описателен текст

64
00:03:44,000 --> 00:03:47,000
точно това, което ние тествахме.

65
00:03:47,000 --> 00:03:49,000
Ние тествахме първия файлове съществуват?

66
00:03:49,000 --> 00:03:51,000
След това се изпитват прави resize.c компилация?

67
00:03:51,000 --> 00:03:58,000
Тогава ние тествахме не го преоразмерите 1x1 пиксела BMP, когато N, преоразмеряване фактор, е една.

68
00:03:58,000 --> 00:04:01,000
Сега, ако вие нямате представа какво е N, ще след като се потопите в pset 4,

69
00:04:01,000 --> 00:04:04,000
но това е просто здрав разум проверите, за да сте сигурни, че не сте преоразмеряване

70
00:04:04,000 --> 00:04:08,000
изображение на всички, ако преоразмеряване фактор е 1.

71
00:04:08,000 --> 00:04:14,000
Ако, от друга страна, преоразмерява 1x1 точки, за да 1x1 пиксела BMP 2x2 правилно

72
00:04:14,000 --> 00:04:19,000
Когато N е два, а след това по същия начин, мина формира съответно.

73
00:04:19,000 --> 00:04:22,000
>> С една дума, това означава, един пропускателните пръстите

74
00:04:22,000 --> 00:04:25,000
от уравнението точно за вас преди да представи си pset.

75
00:04:25,000 --> 00:04:28,000
Вие ще знаете точно какво си TF скоро ще разбере

76
00:04:28,000 --> 00:04:30,000
когато отидеш за представяне на някои от тези проблемни комплекти,

77
00:04:30,000 --> 00:04:34,000
, а също и на педагогическите мотивация е наистина да се сложи

78
00:04:34,000 --> 00:04:37,000
възможност пред себе си, така че, когато знаеш априори

79
00:04:37,000 --> 00:04:39,000
, че има грешки в кода си и изпитвания, които не са преминали,

80
00:04:39,000 --> 00:04:43,000
можете да сложите по-ефективно отпред за решаване на тези проблеми

81
00:04:43,000 --> 00:04:45,000
вместо да губят точки, получаване на обратна връзка от вашия TF

82
00:04:45,000 --> 00:04:48,000
и след това си отиват, "Ааа", като трябва да са Реших, че.

83
00:04:48,000 --> 00:04:50,000
Сега поне има инструмент, който да ви помогне да намерите.

84
00:04:50,000 --> 00:04:52,000
Това не е да се отбележи, къде е бъг, но тя ще ви каже

85
00:04:52,000 --> 00:04:54,000
това, което е показателно за това.

86
00:04:54,000 --> 00:04:57,000
>> Сега осъзнавам, тестовете не са непременно изчерпателни.

87
00:04:57,000 --> 00:04:59,000
Само защото можете да получите на екрана на зелено усмихнати лица

88
00:04:59,000 --> 00:05:02,000
не означава, кода си е перфектен, но това не означава,

89
00:05:02,000 --> 00:05:06,000
че той е преминал някои от изпитванията, предписани от спец..

90
00:05:06,000 --> 00:05:08,000
Понякога ние не ще пусне проверки.

91
00:05:08,000 --> 00:05:10,000
Например, криминале, един от аспектите на pset 4,

92
00:05:10,000 --> 00:05:15,000
е вид разочароващо, ако ние ви даваме

93
00:05:15,000 --> 00:05:18,000
отговор на това, което е, и има редица начини, за да разкрие

94
00:05:18,000 --> 00:05:21,000
кой е човекът в тази червена шум.

95
00:05:21,000 --> 00:05:24,000
Спец. винаги ще определят в бъдеще за pset 5 напред

96
00:05:24,000 --> 00:05:26,000
какви проверки съществува за вас.

97
00:05:26,000 --> 00:05:28,000
Ще забележите, че има този бял URL на дъното.

98
00:05:28,000 --> 00:05:30,000
За сега, това е само диагностика изход.

99
00:05:30,000 --> 00:05:33,000
Ако посетите този адрес, вие ще получите един куп луди, шифрограми

100
00:05:33,000 --> 00:05:36,000
, което можете да търсите чрез, но това е най-вече за персонала

101
00:05:36,000 --> 00:05:41,000
, така че да могат да се диагностицират и отстраняване на грешки на грешки в check50 себе си.

102
00:05:41,000 --> 00:05:46,000
>> Без шум, нека продължим там, където бяхме.

103
00:05:46,000 --> 00:05:48,000
CS50 библиотека взехме за даденост, за няколко седмици,

104
00:05:48,000 --> 00:05:52,000
но след това миналата седмица, ние започнахме пилинг обратно един от слоевете от него.

105
00:05:52,000 --> 00:05:55,000
Ние започнахме да остави настрана низ в полза на това, което вместо?

106
00:05:55,000 --> 00:05:57,000
[Студенти] Чар.

107
00:05:57,000 --> 00:05:59,000
Чар *, което е знак * през цялото това време,

108
00:05:59,000 --> 00:06:03,000
но сега не е нужно да се преструвам, че това е действително тип данни низ.

109
00:06:03,000 --> 00:06:06,000
Напротив, той е бил синоним на видове за Чар *

110
00:06:06,000 --> 00:06:09,000
и низ е последователност от символи,

111
00:06:09,000 --> 00:06:14,000
така че защо има ли смисъл да представляват струни Чар * и?

112
00:06:14,000 --> 00:06:20,000
Какво означава Чар * в рамките на тази концепция на низ?

113
00:06:20,000 --> 00:06:23,000
Да. >> Студентски] Първият знак.

114
00:06:23,000 --> 00:06:25,000
Добре, първият знак, но не съвсем първия знак.

115
00:06:25,000 --> 00:06:27,000
Това е [Студенти] Адрес.

116
00:06:27,000 --> 00:06:29,000
Добре, адреса на първия знак.

117
00:06:29,000 --> 00:06:33,000
Всичко, което е необходимо, за да представлява низ в паметта на компютъра

118
00:06:33,000 --> 00:06:36,000
е само уникалния адрес на първия байт.

119
00:06:36,000 --> 00:06:38,000
Ти дори не трябва да се знае колко време е

120
00:06:38,000 --> 00:06:42,000
защото как може да ви разбера, че динамично?

121
00:06:42,000 --> 00:06:44,000
Студентски] Дължина на тетивата.

122
00:06:44,000 --> 00:06:48,000
Можете да се обадите низ дължина, отлично, но как работи низ дължина?

123
00:06:48,000 --> 00:06:50,000
Какво прави той? Да.

124
00:06:50,000 --> 00:06:52,000
[Student] Продължавайте, докато не получи нула характер.

125
00:06:52,000 --> 00:06:54,000
Да, точно така, той просто повтаря за цикъла, а линия,

126
00:06:54,000 --> 00:06:57,000
от * до края, а краят е представена

127
00:06:57,000 --> 00:07:01,000
от \ 0, така наречения нулев характер, NUL,

128
00:07:01,000 --> 00:07:05,000
да не се бърка с нула, което е указател,

129
00:07:05,000 --> 00:07:07,000
, която ще дойде отново в разговор днес.

130
00:07:07,000 --> 00:07:11,000
>> Отлепи назад слой на GetInt, и тогава ние се погледнете в GetString

131
00:07:11,000 --> 00:07:14,000
и припомни, че на тези функции, или наистина,

132
00:07:14,000 --> 00:07:18,000
GetString, е използване на определена функция

133
00:07:18,000 --> 00:07:21,000
действително разбор, че е четат или анализират, вход на потребителя.

134
00:07:21,000 --> 00:07:25,000
И каква е тази нова функция?

135
00:07:25,000 --> 00:07:27,000
Scanf или sscanf. То всъщност се предлага в няколко различни вкусове.

136
00:07:27,000 --> 00:07:31,000
Има scanf, има sscanf, има fscanf.

137
00:07:31,000 --> 00:07:35,000
За сега, обаче, нека се съсредоточим върху най-лесно е показано,

138
00:07:35,000 --> 00:07:38,000
и ме пусна напред и да се отворят в уреда

139
00:07:38,000 --> 00:07:41,000
файл, като това, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
Това е супер проста програма,

141
00:07:43,000 --> 00:07:46,000
но това не нещо, което никога не съм правил

142
00:07:46,000 --> 00:07:48,000
без помощта на библиотеката CS50.

143
00:07:48,000 --> 00:07:51,000
Това стана Int от потребителя. Как действа тя?

144
00:07:51,000 --> 00:07:53,000
Е, в ред 16 има,

145
00:07:53,000 --> 00:07:56,000
забележите, че ние заявяваме INT нарича X, и в този момент в историята,

146
00:07:56,000 --> 00:07:58,000
каква е стойността на х?

147
00:07:58,000 --> 00:08:00,000
[Чува студент отговор]

148
00:08:00,000 --> 00:08:02,000
[David M.] Право, кой знае, някаква стойност боклук потенциално, така че в 17, ние просто кажете на потребителя

149
00:08:02,000 --> 00:08:06,000
дайте ми номер, моля, и 18 е мястото, където става интересно.

150
00:08:06,000 --> 00:08:11,000
Scanf изглежда да заеме една идея от ФОРМАТ в това, че използва тези формат кодове в кавички.

151
00:08:11,000 --> 00:08:13,000
% D, разбира се десетично число.

152
00:08:13,000 --> 00:08:21,000
Но защо съм преминава в и х а не само х?

153
00:08:21,000 --> 00:08:24,000
Първият от тях е правилен. Да.

154
00:08:24,000 --> 00:08:26,000
[Чува студент отговор]

155
00:08:26,000 --> 00:08:31,000
Точно така, ако целта на тази програма, като функцията GetInt,

156
00:08:31,000 --> 00:08:34,000
е да се получи едно цяло число от потребителя могат да преминат функции

157
00:08:34,000 --> 00:08:38,000
всички променливи, което искам, но ако не ги предаде чрез позоваване

158
00:08:38,000 --> 00:08:41,000
или по адрес или от показалеца, всички синоним за целите на днешните

159
00:08:41,000 --> 00:08:46,000
тогава тази функция няма възможност да променя съдържанието на тази променлива.

160
00:08:46,000 --> 00:08:49,000
Това ще премине в копие, точно като бъги версия на суап

161
00:08:49,000 --> 00:08:51,000
, че сме говорили за няколко пъти.

162
00:08:51,000 --> 00:08:54,000
>> Но вместо това, чрез правене & X, аз съм буквално минава в какво?

163
00:08:54,000 --> 00:08:57,000
[Student адрес. >> Адрес на х.

164
00:08:57,000 --> 00:09:01,000
Това е като изготвяне на карта за функцията, наречена scanf и казва тук,

165
00:09:01,000 --> 00:09:04,000
това са посоки парче на паметта в компютъра

166
00:09:04,000 --> 00:09:07,000
че можете да отидете съхранява някои цяло число.

167
00:09:07,000 --> 00:09:10,000
За sscanf сега правя, че

168
00:09:10,000 --> 00:09:13,000
какво оператор, какво парче на синтаксиса, ще трябва да използвате

169
00:09:13,000 --> 00:09:19,000
въпреки че ние не може да го види, защото някой друг е написал тази функция?

170
00:09:19,000 --> 00:09:21,000
С други думи - какво е това?

171
00:09:21,000 --> 00:09:23,000
[Student] X чете.

172
00:09:23,000 --> 00:09:27,000
Ще има някои четене, но само по отношение на х.

173
00:09:27,000 --> 00:09:30,000
Ако scanf се предава на адреса на х,

174
00:09:30,000 --> 00:09:35,000
синтактично, какво оператор е длъжен да съществуват някъде

175
00:09:35,000 --> 00:09:38,000
в рамките на изпълнението scanf, така че scanf

176
00:09:38,000 --> 00:09:42,000
всъщност може да напишете номер 2 на този адрес?

177
00:09:42,000 --> 00:09:44,000
Да, така *.

178
00:09:44,000 --> 00:09:47,000
Спомнете си, че * е сочен оператор, което по същество означава отида там.

179
00:09:47,000 --> 00:09:50,000
>> След като сте били предадени на един адрес, какъвто е случаят тук,

180
00:09:50,000 --> 00:09:53,000
scanf вероятно е, ако ние всъщност огледа изходния код

181
00:09:53,000 --> 00:09:59,000
прави * х или еквивалент, да отида на този адрес и да има някаква стойност.

182
00:09:59,000 --> 00:10:02,000
Сега, като за това как scanf получава вход от клавиатурата,

183
00:10:02,000 --> 00:10:04,000
ние ще размахва ръцете ни за днес.

184
00:10:04,000 --> 00:10:07,000
Просто се предположи, че операционната система позволява sscanf да говори

185
00:10:07,000 --> 00:10:11,000
клавиатурата на потребителя, но в този момент сега на ред 19,

186
00:10:11,000 --> 00:10:14,000
когато ние просто отпечатате X, тя изглежда да е случаят

187
00:10:14,000 --> 00:10:17,000
scanf е едно цяло число в х.

188
00:10:17,000 --> 00:10:19,000
Това е точно как scanf работи, и припомни миналата седмица

189
00:10:19,000 --> 00:10:25,000
това е точно как GetString и GetInt и другото си семейство от функции

190
00:10:25,000 --> 00:10:28,000
в крайна сметка работи, макар и с леко отклонението като sscanf

191
00:10:28,000 --> 00:10:31,000
което означава, сканирате низ вместо на клавиатурата.

192
00:10:31,000 --> 00:10:33,000
Но нека да разгледаме най-малко разсейването на това.

193
00:10:33,000 --> 00:10:37,000
В scanf2, че всъщност се е провалил.

194
00:10:37,000 --> 00:10:42,000
Какво не е наред и аз ще се скрия коментар, който обяснява като много по-

195
00:10:42,000 --> 00:10:47,000
какво не е наред с тази програма, версия 2?

196
00:10:47,000 --> 00:10:55,000
Бъдете като технически е възможно по това време.

197
00:10:55,000 --> 00:10:57,000
Изглежда доста добре.

198
00:10:57,000 --> 00:11:03,000
Това е добре разчленен, но

199
00:11:03,000 --> 00:11:07,000
Добре, какво ще кажеш да го режеш по-кратки въпроси?

200
00:11:07,000 --> 00:11:17,000
Линия 16. Какво е линия 16 правиш в прецизен, но технически английски език?

201
00:11:17,000 --> 00:11:20,000
Да се ​​малко неловко. Да, Майкъл.

202
00:11:20,000 --> 00:11:25,000
Студентски] Това сочи първата буква на низ.

203
00:11:25,000 --> 00:11:27,000
>> Добре, в близост. Нека ощипвам, че малко.

204
00:11:27,000 --> 00:11:33,000
Посочването на първата буква на низ, за ​​обявяване на променлива наречена буфер

205
00:11:33,000 --> 00:11:36,000
, който ще се отбележи първият адрес на низ

206
00:11:36,000 --> 00:11:39,000
или по-скоро, че ще посочи по-конкретно на знака.

207
00:11:39,000 --> 00:11:42,000
Забележете, че всъщност не е насочена навсякъде, защото няма оператор за присвояване.

208
00:11:42,000 --> 00:11:46,000
Не е знак за равенство, така че всичко, което правим е разпределяне на променлива наречена буфер.

209
00:11:46,000 --> 00:11:49,000
Това се случва на 32 бита, защото това е показалеца,

210
00:11:49,000 --> 00:11:52,000
и съдържанието на буфера вероятно в крайна сметка

211
00:11:52,000 --> 00:11:57,000
ще съдържа адреса на Чар, но за сега, какво буфер съдържа?

212
00:11:57,000 --> 00:11:59,000
Просто някои фалшив, кой знае, някои боклук стойност,

213
00:11:59,000 --> 00:12:03,000
защото не сме изрично го инициализира, така че ние не трябва да поеме нищо.

214
00:12:03,000 --> 00:12:06,000
Добре, сега линия 17-какво линия 17?

215
00:12:06,000 --> 00:12:08,000
Може би това ще се затопли всичко.

216
00:12:08,000 --> 00:12:10,000
Той отпечатва низ, нали?

217
00:12:10,000 --> 00:12:12,000
Той отпечатва String моля.

218
00:12:12,000 --> 00:12:15,000
>> Линия 18 е вид познат с това, че току-що видяхме вариацията на това

219
00:12:15,000 --> 00:12:18,000
но с различен код формат, така и в ред 18,

220
00:12:18,000 --> 00:12:23,000
ние казваме scanf тук е адреса на парче на паметта.

221
00:12:23,000 --> 00:12:27,000
Искам да звъни в низ, както се подразбира от% S,

222
00:12:27,000 --> 00:12:32,000
но проблемът е, че не сме направили няколко неща тук.

223
00:12:32,000 --> 00:12:35,000
Какво е един от проблемите?

224
00:12:35,000 --> 00:12:38,000
[Студентски] се опитва да сочен с нулев указател.

225
00:12:38,000 --> 00:12:41,000
Добри, NULL или просто в противен случай неизвестен указатели.

226
00:12:41,000 --> 00:12:45,000
Вие предаването scanf адрес, но току-що казахте преди малко

227
00:12:45,000 --> 00:12:49,000
че това е адресът е някакъв боклук стойност, защото ние не всъщност го възложи на нещо,

228
00:12:49,000 --> 00:12:53,000
и така казваш scanf ефективно сложи низ тук,

229
00:12:53,000 --> 00:12:56,000
но ние не знаем къде тук е,

230
00:12:56,000 --> 00:12:59,000
така че ние всъщност не са разпределени памет за буфер.

231
00:12:59,000 --> 00:13:03,000
Освен това, това, което сте и дори не казва scanf?

232
00:13:03,000 --> 00:13:06,000
Да предположим, че това е парче от паметта, и то не е боклук стойност,

233
00:13:06,000 --> 00:13:09,000
но все още не казваш scanf нещо важно.

234
00:13:09,000 --> 00:13:12,000
[Student] Къде всъщност е, амперсанд.

235
00:13:12,000 --> 00:13:15,000
Ampersand, така че в този случай, това е добре.

236
00:13:15,000 --> 00:13:18,000
Тъй като буфер се вече декларирани като показалка

237
00:13:18,000 --> 00:13:22,000
* парче на синтаксиса, ние не трябва да използвате амперсанд

238
00:13:22,000 --> 00:13:25,000
, защото това е вече един адрес, но мисля, че аз го чух тук.

239
00:13:25,000 --> 00:13:27,000
[Student] Колко голяма е тя?

240
00:13:27,000 --> 00:13:29,000
Добре, ние не казваш scanf колко голям е този буфер,

241
00:13:29,000 --> 00:13:32,000
което означава, че дори ако буфер указател,

242
00:13:32,000 --> 00:13:35,000
Казваш, scanf, сложи низ тук,

243
00:13:35,000 --> 00:13:38,000
но тук може да бъде два байта, може да е 10 байта, тя може да бъде един мегабайт.

244
00:13:38,000 --> 00:13:41,000
Scanf не е идея, а защото това е парче от паметта

245
00:13:41,000 --> 00:13:43,000
Предполага се, че това не е низ все още.

246
00:13:43,000 --> 00:13:48,000
Това е само низ, след като пишете символи и \ 0 до това парче на паметта.

247
00:13:48,000 --> 00:13:51,000
Сега е само някои парче на паметта.

248
00:13:51,000 --> 00:13:55,000
Scanf няма да знае кога да спре да пише на този адрес.

249
00:13:55,000 --> 00:13:59,000
>> Ако си спомняте някои примери в миналото, когато случайно, въвеждани от клавиатурата

250
00:13:59,000 --> 00:14:03,000
се опитва да препълване на буфер, и ние говорихме в петък за точно това.

251
00:14:03,000 --> 00:14:07,000
Ако противник някак си инжектира във вашата програма много по-голяма дума

252
00:14:07,000 --> 00:14:10,000
или изречение или фраза и след това сте очаквали можете да се превърти

253
00:14:10,000 --> 00:14:13,000
парче на памет, която може да има лоши последствия,

254
00:14:13,000 --> 00:14:15,000
като поема цялата самата програма.

255
00:14:15,000 --> 00:14:17,000
Ние трябва да се определи това по някакъв начин.

256
00:14:17,000 --> 00:14:20,000
Нека я увеличите и във версия 3 на тази програма.

257
00:14:20,000 --> 00:14:22,000
Това е малко по-добре.

258
00:14:22,000 --> 00:14:24,000
В тази версия, забележите разликата.

259
00:14:24,000 --> 00:14:27,000
В съответствие 16, аз съм отново за обявяване на променлива наречена буфер,

260
00:14:27,000 --> 00:14:29,000
но това, което е сега?

261
00:14:29,000 --> 00:14:33,000
Това е масив от 16 символа.

262
00:14:33,000 --> 00:14:36,000
Това е добре, защото това означава, сега мога да кажа, scanf

263
00:14:36,000 --> 00:14:39,000
тук е действително парче на паметта.

264
00:14:39,000 --> 00:14:42,000
Почти можеш да мисля, че на масиви като указатели сега,

265
00:14:42,000 --> 00:14:44,000
въпреки че всъщност те не са еквивалентни.

266
00:14:44,000 --> 00:14:47,000
Те ще се държат по различен начин в различни контексти.

267
00:14:47,000 --> 00:14:50,000
Но със сигурност това е случай, че буфер се съотнасяне

268
00:14:50,000 --> 00:14:53,000
16 съседни символа, защото това е масив е

269
00:14:53,000 --> 00:14:55,000
и е бил за няколко седмици.

270
00:14:55,000 --> 00:14:59,000
>> Ето, казвам scanf тук е парче на паметта.

271
00:14:59,000 --> 00:15:01,000
Този път, това е всъщност парче от паметта,

272
00:15:01,000 --> 00:15:07,000
но защо е тази програма все още експлоатация?

273
00:15:07,000 --> 00:15:11,000
Какво се е случило все още?

274
00:15:11,000 --> 00:15:14,000
Казах да ми даде 16 байта, но-

275
00:15:14,000 --> 00:15:16,000
[Student] Какво ще стане, ако напишете в повече от 16?

276
00:15:16,000 --> 00:15:20,000
Точно така, какво ще стане, ако на потребителя видове в 17 знака или 1700 знака?

277
00:15:20,000 --> 00:15:23,000
В действителност, нека да видим, ако ние не можем пътуване през тази грешка сега.

278
00:15:23,000 --> 00:15:25,000
Това е по-добре, но не е съвършен.

279
00:15:25,000 --> 00:15:28,000
Нека вървим напред и тичам да scanf3 за съставяне на тази програма.

280
00:15:28,000 --> 00:15:34,000
Нека да scanf3, String моля: Здравейте, и ние като че ли се оправи.

281
00:15:34,000 --> 00:15:37,000
Нека се опитам малко по-дълъг, здравей там.

282
00:15:37,000 --> 00:15:42,000
Добре, нека да Здравейте как сте днес, Enter.

283
00:15:42,000 --> 00:15:54,000
Първи вид на щастлив тук, нека кажа здрасти как сте.

284
00:15:54,000 --> 00:15:56,000
Дявол да го вземе.

285
00:15:56,000 --> 00:16:03,000
Добре, така че ние сме късметлии. Нека видим дали не можем да поправя това.

286
00:16:03,000 --> 00:16:06,000
Не, това няма да ми позволи да копирате.

287
00:16:06,000 --> 00:16:09,000
Нека опитаме отново.

288
00:16:09,000 --> 00:16:12,000
Добре, да се изправя.

289
00:16:12,000 --> 00:16:20,000
Ще видим колко дълго мога да се преструвам да фокусира, докато все още се прави това.

290
00:16:20,000 --> 00:16:23,000
Дявол да го вземе. Това е доста подходящо, всъщност.

291
00:16:23,000 --> 00:16:26,000
Точно така.

292
00:16:26,000 --> 00:16:30,000
Точка.

293
00:16:30,000 --> 00:16:34,000
>> Това неудобно, въпреки че също е, това е също един от източниците на голямо объркване

294
00:16:34,000 --> 00:16:38,000
при писане на програми, които имат грешки, защото те се проявяват

295
00:16:38,000 --> 00:16:40,000
само веднъж в последно време понякога.

296
00:16:40,000 --> 00:16:43,000
Истината е, че дори ако вашият код е напълно разбити,

297
00:16:43,000 --> 00:16:46,000
той може само да бъде напълно разбити от време на време

298
00:16:46,000 --> 00:16:49,000
защото понякога по същество това, което се случва, е, разпределя операционни системи

299
00:16:49,000 --> 00:16:52,000
малко повече памет, отколкото сте в действителност се нуждаят, независимо от причината,

300
00:16:52,000 --> 00:16:57,000
и така никой друг не се използва паметта веднага след парче 16 знака,

301
00:16:57,000 --> 00:17:01,000
така че ако отидете до 17, 18, 19, каквото и да е, това не е толкова голям проблем.

302
00:17:01,000 --> 00:17:04,000
Сега, на компютъра, дори и да не се срине в този момент,

303
00:17:04,000 --> 00:17:09,000
евентуално може да използвате байт номер 17 или 18 или 19 за нещо друго,

304
00:17:09,000 --> 00:17:14,000
, при които сочат данните ви, което е сложил там, макар и прекалено дълго,

305
00:17:14,000 --> 00:17:18,000
ще се получи, презаписани евентуално от някои други функции.

306
00:17:18,000 --> 00:17:21,000
Това не е задължително да останат непокътнати,

307
00:17:21,000 --> 00:17:23,000
но това не е задължително да доведе до сегмента вина.

308
00:17:23,000 --> 00:17:26,000
Но в този случай, най-накрая достатъчно знаци

309
00:17:26,000 --> 00:17:29,000
че по същество надхвърля сегмент на паметта, и бам,

310
00:17:29,000 --> 00:17:33,000
операционната система, каза: "Съжалявам, това не е добре, сегментация вина."

311
00:17:33,000 --> 00:17:38,000
>> И нека да видим сега, ако това, което остава тук, в моята директория

312
00:17:38,000 --> 00:17:40,000
забележите, че имам този файл тук, ядро.

313
00:17:40,000 --> 00:17:42,000
Забележете, че това е отново призова основен сметището.

314
00:17:42,000 --> 00:17:46,000
Това е по същество файл, който съдържа съдържанието на паметта на вашата програма

315
00:17:46,000 --> 00:17:48,000
в точката, в която се разби,

316
00:17:48,000 --> 00:17:51,000
и просто да опитате един малък пример тук ме пусна тук

317
00:17:51,000 --> 00:17:57,000
и стартирате GDB на scanf3 и след това определете третия аргумент, наречена ядро,

318
00:17:57,000 --> 00:18:01,000
и да забележите, че ако списък на кода,

319
00:18:01,000 --> 00:18:06,000
ние ще бъдем в състояние както обикновено, с GDB да започне ходене чрез тази програма,

320
00:18:06,000 --> 00:18:10,000
и мога да го стартирате и веднага след като удари с стъпка команда в GDB

321
00:18:10,000 --> 00:18:13,000
веднага след като се удари потенциално бъги линия, след като въведете в огромен низ,

322
00:18:13,000 --> 00:18:16,000
Аз ще бъда в състояние да го идентифицира тук.

323
00:18:16,000 --> 00:18:19,000
Повече за това, обаче, в раздел по отношение на ключови сметища

324
00:18:19,000 --> 00:18:22,000
и други подобни, така че да може действително да мушкам около вътрешността на ядрото сметището

325
00:18:22,000 --> 00:18:27,000
и да видим каква линия на програмата, която не успя.

326
00:18:27,000 --> 00:18:32,000
Всички въпроси на указатели, както и на адреси?

327
00:18:32,000 --> 00:18:36,000
Защото днес на, отиваме да започнете да приемате за даденост, че тези неща съществуват

328
00:18:36,000 --> 00:18:40,000
и ние знаем точно какви са те.

329
00:18:40,000 --> 00:18:42,000
Да.

330
00:18:42,000 --> 00:18:46,000
>> [Student] Как така не трябва да се сложи амперсанд до частта

331
00:18:46,000 --> 00:18:48,000
Добър въпрос.

332
00:18:48,000 --> 00:18:51,000
Как дойда не трябва да се сложи амперсанд до характера масив, както направих аз преди

333
00:18:51,000 --> 00:18:53,000
с повечето от нашите примери?

334
00:18:53,000 --> 00:18:55,000
Краткият отговор е масиви са малко по-специален.

335
00:18:55,000 --> 00:18:59,000
Почти можеш да мисля, че буфер за реално адрес,

336
00:18:59,000 --> 00:19:03,000
и то просто така се случва да бъде случай, че на площада нотация на конзолата

337
00:19:03,000 --> 00:19:06,000
е удобство, така че можем да отидем в конзола 0, скоба 1,

338
00:19:06,000 --> 00:19:10,000
скоба 2, без да се налага да се използва нотацията *.

339
00:19:10,000 --> 00:19:13,000
Това е малко на бяла лъжа, тъй като масиви и указатели

340
00:19:13,000 --> 00:19:17,000
, в действителност са малко по-различно, но те могат да често, но не винаги се използват взаимозаменяемо.

341
00:19:17,000 --> 00:19:21,000
Накратко, когато функцията се очаква указател към парче от паметта,

342
00:19:21,000 --> 00:19:24,000
можете да го давате адрес, който бе върнат от изчистване,

343
00:19:24,000 --> 00:19:29,000
и ще видим изчистване отново след дълго, или може да го предаде на името на масива.

344
00:19:29,000 --> 00:19:32,000
Не е нужно да правите амперсанд с масиви, тъй като те вече са

345
00:19:32,000 --> 00:19:34,000
по същество като адреси.

346
00:19:34,000 --> 00:19:36,000
Това е едно изключение.

347
00:19:36,000 --> 00:19:39,000
Квадратни скоби ги правят специален.

348
00:19:39,000 --> 00:19:41,000
>> Може ли да сложите амперсанд до буфера?

349
00:19:41,000 --> 00:19:43,000
Не и в този случай.

350
00:19:43,000 --> 00:19:46,000
Това няма да работи, защото, отново, този ъгъл случай

351
00:19:46,000 --> 00:19:49,000
където масиви не всъщност са доста адреси.

352
00:19:49,000 --> 00:19:54,000
Но може би ние ще се върна, че не след дълго с други примери.

353
00:19:54,000 --> 00:19:56,000
Нека се опитаме да решим проблем тук.

354
00:19:56,000 --> 00:20:00,000
Ние имаме структурата на данните, че ние сме били като за известно време, известен като масив.

355
00:20:00,000 --> 00:20:02,000
Дело в точка, това е, което ние просто трябваше.

356
00:20:02,000 --> 00:20:04,000
Но масиви имат някои добри и лоши страни.

357
00:20:04,000 --> 00:20:06,000
Масивите са хубави защо?

358
00:20:06,000 --> 00:20:11,000
Какво е едно нещо, което ви харесва на степента, в която искате масиви за масиви?

359
00:20:11,000 --> 00:20:13,000
Какво е удобно за тях? Какво е убедителна?

360
00:20:13,000 --> 00:20:18,000
Защо не сме ги представим на първо място?

361
00:20:18,000 --> 00:20:20,000
Да.

362
00:20:20,000 --> 00:20:27,000
Студентски Те могат да съхраняват много данни, и не е нужно да използвате цялото нещо.

363
00:20:27,000 --> 00:20:29,000
Можете да използвате раздел.

364
00:20:29,000 --> 00:20:32,000
Добре, с множество можете да съхранявате много данни,

365
00:20:32,000 --> 00:20:35,000
и не е нужно непременно трябва да използвате всичко това, така че можете да overallocate,

366
00:20:35,000 --> 00:20:39,000
която може да бъде удобно, ако не знае предварително колко от нещо, което да се очаква.

367
00:20:39,000 --> 00:20:41,000
>> GetString е идеален пример.

368
00:20:41,000 --> 00:20:44,000
GetString, написани от нас, няма представа колко символа да се очаква,

369
00:20:44,000 --> 00:20:48,000
така че фактът, че можем да разпределят парчета непрекъсната памет е добро.

370
00:20:48,000 --> 00:20:51,000
Масивите също решаване на проблема видяхме преди няколко седмици

371
00:20:51,000 --> 00:20:54,000
код започва да се прехвърли в нещо много лошо проектирани.

372
00:20:54,000 --> 00:20:57,000
Спомнете си, че съм създал студент структура, наречена Дейвид,

373
00:20:57,000 --> 00:21:00,000
и това всъщност е алтернатива, въпреки че,

374
00:21:00,000 --> 00:21:04,000
да има променлива наречена име и друга променлива, мисля, къща,

375
00:21:04,000 --> 00:21:08,000
и друга променлива ID, защото в тази история съм искал да въведе нещо друго

376
00:21:08,000 --> 00:21:11,000
като Роб в програмата, така че след това реших, чакай малко,

377
00:21:11,000 --> 00:21:13,000
Трябва да преименувате тези променливи.

378
00:21:13,000 --> 00:21:16,000
Нека наричаме мина NAME1, ID1, house1.

379
00:21:16,000 --> 00:21:20,000
Нека наречем Роб NAME2, house2, ID2.

380
00:21:20,000 --> 00:21:22,000
Но тогава чакай малко, какво да кажем за Томи?

381
00:21:22,000 --> 00:21:24,000
Тогава имахме още три променливи.

382
00:21:24,000 --> 00:21:27,000
Ние въведохме някой друг, четири набори от променливи.

383
00:21:27,000 --> 00:21:30,000
Светът започна да се разхвърлян много бързо,

384
00:21:30,000 --> 00:21:33,000
така че ние въведохме structs, и какво е завладяваща около една структура?

385
00:21:33,000 --> 00:21:39,000
Какво означава структура C ви позволи да направите?

386
00:21:39,000 --> 00:21:42,000
Това е наистина неловко днес.

387
00:21:42,000 --> 00:21:44,000
Какво? >> Чува студент отговор]

388
00:21:44,000 --> 00:21:47,000
Да, по-специално, typedef ви позволява да създадете нов тип данни,

389
00:21:47,000 --> 00:21:51,000
и структура, структура на ключова дума, ви позволява да капсулират

390
00:21:51,000 --> 00:21:54,000
концептуално свързани парчета на данните заедно

391
00:21:54,000 --> 00:21:56,000
и след това да ги наречем нещо като ученик.

392
00:21:56,000 --> 00:21:58,000
>> Това беше добре, защото сега ние можем да проектираме

393
00:21:58,000 --> 00:22:03,000
много повече вид на концептуално съответствие идеята на един студент в променлива

394
00:22:03,000 --> 00:22:07,000
, а не произволно като един низ, за ​​лична, и така нататък.

395
00:22:07,000 --> 00:22:10,000
Масивите са приятни, защото те ни позволяват да започне почистване на нашия код.

396
00:22:10,000 --> 00:22:13,000
Но това, което е недостатък на масив?

397
00:22:13,000 --> 00:22:15,000
Какво може нали? Да.

398
00:22:15,000 --> 00:22:17,000
Студентски Трябва да знаете, колко е голям.

399
00:22:17,000 --> 00:22:19,000
Трябва да знаете, колко е голям, така че това е вид болка.

400
00:22:19,000 --> 00:22:21,000
Тези от вас, с предварително програмиране опит знам, че в много езици,

401
00:22:21,000 --> 00:22:24,000
като Java, можете да поискате парче на паметта, по-специално масив,

402
00:22:24,000 --> 00:22:28,000
колко големи са, с дължина, имущество, така да се каже, и това е наистина удобно.

403
00:22:28,000 --> 00:22:32,000
В C, не може дори да се нарека strlen на родово масив

404
00:22:32,000 --> 00:22:35,000
защото strlen, като думата предполага, е само за струнни,

405
00:22:35,000 --> 00:22:39,000
и можете да разбера дължината на низ, защото на тази човешка конвенция

406
00:22:39,000 --> 00:22:43,000
\ 0, но масив, по-родово, е само парче от паметта.

407
00:22:43,000 --> 00:22:46,000
Ако това е масив от цели числа, не ще да има някакъв специален символ

408
00:22:46,000 --> 00:22:48,000
в края те чака.

409
00:22:48,000 --> 00:22:50,000
Трябва да се помни дължината на масива.

410
00:22:50,000 --> 00:22:54,000
Друг недостатък на масив надигна глава по себе си GetString.

411
00:22:54,000 --> 00:22:59,000
Какво е друг недостатък на масив?

412
00:22:59,000 --> 00:23:01,000
Господине, само ти и аз днес.

413
00:23:01,000 --> 00:23:04,000
[Чува студент отговор] >> Това е какво?

414
00:23:04,000 --> 00:23:06,000
Той е обявен на стека.

415
00:23:06,000 --> 00:23:09,000
Добре, декларирани в стека. Защо не ти харесва?

416
00:23:09,000 --> 00:23:13,000
[Student], защото той се използва повторно.

417
00:23:13,000 --> 00:23:15,000
То се използва повторно.

418
00:23:15,000 --> 00:23:18,000
Добре, ако използвате масив да бъде заделена памет,

419
00:23:18,000 --> 00:23:21,000
например, не можете да го върнете, защото това е в стека.

420
00:23:21,000 --> 00:23:23,000
Добре, това е недостатък.

421
00:23:23,000 --> 00:23:25,000
А какво ще кажеш за един друг с масив?

422
00:23:25,000 --> 00:23:28,000
След като го разпределят, вие сте някак прецакани, ако имате нужда от повече пространство

423
00:23:28,000 --> 00:23:30,000
от този масив.

424
00:23:30,000 --> 00:23:34,000
>> След това ние въведохме, изземване, изчистване, което ни даде възможност за динамично разпределяне на паметта.

425
00:23:34,000 --> 00:23:37,000
Но какво би станало, ако ние се опитахме съвсем различен свят?

426
00:23:37,000 --> 00:23:40,000
Какво става, ако искаме да се решат няколко от тези проблеми

427
00:23:40,000 --> 00:23:45,000
така че ние вместо моята писалка е заспал тук

428
00:23:45,000 --> 00:23:51,000
какво би станало, ако вместо това исках главно в създаване на един свят, който вече не е така?

429
00:23:51,000 --> 00:23:56,000
Това е масив, и, разбира се, този вид се влошава, след като удари в края на масива,

430
00:23:56,000 --> 00:24:00,000
и аз сега вече не са място за друго цяло число или друг характер.

431
00:24:00,000 --> 00:24:03,000
Какво ще стане, ако ние вид изпреварващо да се каже, добре, защо не сме се отпуснете

432
00:24:03,000 --> 00:24:07,000
това изискване, че всички тези блокове памет да граничат успоредно,

433
00:24:07,000 --> 00:24:10,000
и защо не, когато имам нужда от едно цяло число или Чар,

434
00:24:10,000 --> 00:24:12,000
току-що ми даде пространство за един от тях?

435
00:24:12,000 --> 00:24:14,000
И когато имам нужда от друг, дай ми друг свят,

436
00:24:14,000 --> 00:24:16,000
и когато имам нужда от друг, дай ми друго място.

437
00:24:16,000 --> 00:24:19,000
Предимството на които сега е, че ако някой друг

438
00:24:19,000 --> 00:24:21,000
заема памет тук, не е голяма работа.

439
00:24:21,000 --> 00:24:25,000
Аз ще взема това допълнително парче на паметта тук и след това.

440
00:24:25,000 --> 00:24:28,000
>> Сега, само за улов тук е, че почти се чувства като имам

441
00:24:28,000 --> 00:24:30,000
цял куп различни променливи.

442
00:24:30,000 --> 00:24:33,000
Това изглежда като пет различни променливи потенциално.

443
00:24:33,000 --> 00:24:36,000
Но какво, ако открадне идеята от струни

444
00:24:36,000 --> 00:24:41,000
, чрез който ние по някакъв начин връзка между тези неща заедно концептуално, и какво ако го направя това?

445
00:24:41,000 --> 00:24:44,000
Това ми е много зле съставен стрелка.

446
00:24:44,000 --> 00:24:46,000
Но да предположим, че всеки един от тези блокове памет

447
00:24:46,000 --> 00:24:52,000
посочи към другия, и този човек, който няма братя и сестри от дясната му страна,

448
00:24:52,000 --> 00:24:54,000
няма такава стрелка.

449
00:24:54,000 --> 00:24:56,000
Това е всъщност това, което се нарича свързан списък.

450
00:24:56,000 --> 00:25:00,000
Това е нова структура на данните, която ни позволява да се разпределят парче от паметта,

451
00:25:00,000 --> 00:25:03,000
после още една, после още една, после още една, по всяко време искаме

452
00:25:03,000 --> 00:25:07,000
по време на програмата, и ние си спомняме, че всички те са свързани по някакъв начин

453
00:25:07,000 --> 00:25:11,000
като буквално верижното заедно, и ние сме го направили картинки тук със стрелка.

454
00:25:11,000 --> 00:25:15,000
Но в кода, какво ще бъде механизмът, чрез които бихте могли по някакъв начин да се свърже,

455
00:25:15,000 --> 00:25:20,000
почти като Scratch, едно парче на друг парче?

456
00:25:20,000 --> 00:25:22,000
Бихме могли да се използва показалка, нали?

457
00:25:22,000 --> 00:25:25,000
Защото наистина стрелката, която става от горния ляв квадрат,

458
00:25:25,000 --> 00:25:31,000
този човек тук това биха могли да съдържат в рамките на този площад

459
00:25:31,000 --> 00:25:34,000
не само някои цели числа, а не само някои Чар, но какво ще стане, ако аз действително разпределени

460
00:25:34,000 --> 00:25:37,000
малко допълнително пространство, така че сега,

461
00:25:37,000 --> 00:25:41,000
всеки от моите парчета памет, въпреки че това ще ми струва,

462
00:25:41,000 --> 00:25:45,000
сега изглежда малко по-правоъгълна, когато едно от парчета на паметта

463
00:25:45,000 --> 00:25:47,000
се използва за брой, като номер 1,

464
00:25:47,000 --> 00:25:50,000
и след това, ако този човек съхранява номер 2,

465
00:25:50,000 --> 00:25:52,000
това друго парче от паметта се използва за стрела,

466
00:25:52,000 --> 00:25:54,000
или по-конкретно, показалка.

467
00:25:54,000 --> 00:25:59,000
И предполагам, че се съхранява под номер 3 тук, докато аз използвам това да се посочи, че човек,

468
00:25:59,000 --> 00:26:02,000
и сега този човек, нека предположим, Искам само три такива блокове памет.

469
00:26:02,000 --> 00:26:05,000
Ще начертаете линия през това, което показва нула.

470
00:26:05,000 --> 00:26:07,000
Няма допълнителна характер.

471
00:26:07,000 --> 00:26:10,000
>> В действителност, това е как можем да отида за прилагане на

472
00:26:10,000 --> 00:26:12,000
нещо, което се нарича свързан списък.

473
00:26:12,000 --> 00:26:18,000
A свързан списък е нова структура на данните, и това е трамплин към

474
00:26:18,000 --> 00:26:21,000
много красиви структури от данни, които започват да решават проблеми

475
00:26:21,000 --> 00:26:23,000
по подобие на Facebook тип проблеми и Google тип проблеми

476
00:26:23,000 --> 00:26:26,000
когато имате огромни набори от данни, и тя вече не го реже

477
00:26:26,000 --> 00:26:29,000
да съхранява всичко Последователно и нещо като линейно търсене

478
00:26:29,000 --> 00:26:31,000
или дори нещо като двоично търсене.

479
00:26:31,000 --> 00:26:33,000
Искате още по-добри текущи пъти.

480
00:26:33,000 --> 00:26:37,000
В действителност, един от светите Grails ние ще говорим за по-късно тази седмица или следващата

481
00:26:37,000 --> 00:26:41,000
е един алгоритъм, чието изпълнение е постоянна.

482
00:26:41,000 --> 00:26:44,000
С други думи, тя винаги е на същия период от време, без значение

483
00:26:44,000 --> 00:26:47,000
колко голям вход е, и че наистина ще бъде неудържим,

484
00:26:47,000 --> 00:26:49,000
дори повече, отколкото нещо логаритмична.

485
00:26:49,000 --> 00:26:51,000
Какво е това на екрана?

486
00:26:51,000 --> 00:26:55,000
Всеки един от правоъгълниците е точно това, което аз просто обърна с ръка.

487
00:26:55,000 --> 00:26:59,000
Но нещо по целия път от ляво е специална променлива.

488
00:26:59,000 --> 00:27:02,000
Това ще бъде един показалеца, защото една Gotcha

489
00:27:02,000 --> 00:27:04,000
свързан списък, тъй като тези неща се наричат,

490
00:27:04,000 --> 00:27:09,000
е, че трябва да се мотае в единия край на свързан списък.

491
00:27:09,000 --> 00:27:13,000
>> Точно както с низ, вие трябва да знаете адреса на първо Чар.

492
00:27:13,000 --> 00:27:15,000
Същата сделка за свързани списъци.

493
00:27:15,000 --> 00:27:19,000
Трябва да знаете адреса на първото парче на паметта

494
00:27:19,000 --> 00:27:25,000
, тъй като от там можете да достигнете до всяка друга.

495
00:27:25,000 --> 00:27:27,000
Недостатъкът.

496
00:27:27,000 --> 00:27:30,000
Каква цена плащаме за тази гъвкавост на динамично

497
00:27:30,000 --> 00:27:34,000
доста голям структурата на данните, че ако някога се нуждаят от повече памет, добре,

498
00:27:34,000 --> 00:27:37,000
просто разпределят още едно парче и да показалец от

499
00:27:37,000 --> 00:27:39,000
старата към новата опашката на списъка?

500
00:27:39,000 --> 00:27:41,000
Да.

501
00:27:41,000 --> 00:27:43,000
[Student] Това отнема около два пъти по-голямо пространство.

502
00:27:43,000 --> 00:27:45,000
Това отнема два пъти повече пространство, така че определено е недостатък, а ние сме виждали това

503
00:27:45,000 --> 00:27:48,000
компромис преди между времето и пространството и гъвкавост

504
00:27:48,000 --> 00:27:51,000
където до сега, ние не трябва 32 бита за всеки един от тези номера.

505
00:27:51,000 --> 00:27:57,000
Ние наистина се нуждаят от 64, 32 за брой и 32 за показалеца.

506
00:27:57,000 --> 00:27:59,000
Но, хей, имам 2 гигабайта RAM.

507
00:27:59,000 --> 00:28:02,000
Добавянето на още 32 бита, тук и тук не изглежда, че голяма сделка.

508
00:28:02,000 --> 00:28:05,000
Но за големи масиви от данни, то определено добавя буквално два пъти повече.

509
00:28:05,000 --> 00:28:09,000
Какво е друг недостатък сега, или каква функция да даваме,

510
00:28:09,000 --> 00:28:12,000
ако ние представляваме списъци на неща със свързан списък, а не масив?

511
00:28:12,000 --> 00:28:14,000
Студентски] не могат да преминават назад.

512
00:28:14,000 --> 00:28:16,000
Вие не можете да преминават назад, така че вие ​​сте вид прецакани, ако сте пеша

513
00:28:16,000 --> 00:28:19,000
от ляво на дясно с помощта на линия или цикъл, докато

514
00:28:19,000 --> 00:28:21,000
и после си даваш сметка, "О, аз искам да се върна към началото на списъка."

515
00:28:21,000 --> 00:28:26,000
Вие не можете, защото тези насоки само от ляво на дясно, като стрелките показват.

516
00:28:26,000 --> 00:28:29,000
>> Сега, вие може да си спомни началото на списъка с друга променлива,

517
00:28:29,000 --> 00:28:31,000
но това е сложността да се има предвид.

518
00:28:31,000 --> 00:28:35,000
Масив, без значение колко далеч да отидете, вие винаги може да направи минус, минус, минус, минус

519
00:28:35,000 --> 00:28:37,000
и да се върнете, откъдето сте дошли.

520
00:28:37,000 --> 00:28:40,000
Какво е друг недостатък тук? Да.

521
00:28:40,000 --> 00:28:43,000
[Чува студент въпрос]

522
00:28:43,000 --> 00:28:47,000
, Така че Вие може да сте всъщност предложи данните структура, наречена двойно свързан списък,

523
00:28:47,000 --> 00:28:50,000
и наистина, ще се добавят още показалеца на всеки един от тези правоъгълници

524
00:28:50,000 --> 00:28:53,000
, които отиват в друга посока, нагоре, от които

525
00:28:53,000 --> 00:28:55,000
сега можете да преминават напред и назад,

526
00:28:55,000 --> 00:28:59,000
Недостатъкът на които сега сте с помощта на три пъти повече памет, както сме свикнали да

527
00:28:59,000 --> 00:29:04,000
, а също и добавяне на сложност в условията на Кодекса, Вие трябва да напишете, за да го направим.

528
00:29:04,000 --> 00:29:08,000
Но всички те са може би много разумни компромиси, ако възстановяването е по-важно.

529
00:29:08,000 --> 00:29:10,000
Да.

530
00:29:10,000 --> 00:29:12,000
Студентски] също не може да има 2D свързан списък.

531
00:29:12,000 --> 00:29:16,000
Добре, че не може наистина да има 2D свързан списък.

532
00:29:16,000 --> 00:29:18,000
Би могъл. Това не е толкова лесно, колкото масив.

533
00:29:18,000 --> 00:29:21,000
Както масив, нали отворена скоба, затворена скоба, отворена скоба, затворена скоба,

534
00:29:21,000 --> 00:29:23,000
и ще получите около 2 триизмерна структура.

535
00:29:23,000 --> 00:29:26,000
Може да се приложи 2-измерна свързан списък

536
00:29:26,000 --> 00:29:29,000
ако го направите добавка, както ти предложи 1/3 показалеца на всяка от тези неща,

537
00:29:29,000 --> 00:29:34,000
и ако си мислиш за друг списък идват при вас 3D стил

538
00:29:34,000 --> 00:29:40,000
от екрана на всички нас, което е просто друга верига от някакъв вид.

539
00:29:40,000 --> 00:29:45,000
Можем да го направим, но това не е толкова просто, колкото да пишете отворена скоба, квадратна скоба. Да.

540
00:29:45,000 --> 00:29:48,000
[Чува студент въпрос]

541
00:29:48,000 --> 00:29:50,000
Добър, така че това е истински кикър.

542
00:29:50,000 --> 00:29:54,000
>> Тези алгоритми, които сме pined, като о, двоично търсене,

543
00:29:54,000 --> 00:29:57,000
масив от числа можете да търсите на борда

544
00:29:57,000 --> 00:30:01,000
или телефонния указател, така много по-бързо, ако използвате разделяй и владей

545
00:30:01,000 --> 00:30:05,000
и двоичен алгоритъм на търсене, но търсене двоичен изисква две предположения.

546
00:30:05,000 --> 00:30:09,000
Едно, че данните са подредени.

547
00:30:09,000 --> 00:30:11,000
Сега, ние можем да се предполага това подредени,

548
00:30:11,000 --> 00:30:14,000
така че може би това не е причина за безпокойство, но двоично търсене също така се приема

549
00:30:14,000 --> 00:30:18,000
че сте имали произволен достъп до списъка с номера,

550
00:30:18,000 --> 00:30:21,000
и масив ви позволява да имате случаен достъп, както и от случаен достъп,

551
00:30:21,000 --> 00:30:24,000
Искам да кажа, ако вие сте даден масив, колко време ви отнема

552
00:30:24,000 --> 00:30:26,000
да се получи да скоба 0?

553
00:30:26,000 --> 00:30:29,000
Една операция, можете просто да използвате [0] и вие сте точно там.

554
00:30:29,000 --> 00:30:33,000
Колко стъпки се предприемат, за да стигнем до място 10?

555
00:30:33,000 --> 00:30:36,000
Една стъпка, просто отидете [10] и сте там.

556
00:30:36,000 --> 00:30:40,000
За разлика от това, как се стигна до 10-о число в свързан списък?

557
00:30:40,000 --> 00:30:42,000
Трябва да започнем от самото начало, защото си спомняш само

558
00:30:42,000 --> 00:30:45,000
началото на свързан списък, просто като низ се помни

559
00:30:45,000 --> 00:30:48,000
от адреса на първата Чар, и да откриете, че 10 вътр

560
00:30:48,000 --> 00:30:53,000
или, че 10-ия знак в низ, трябва да се търси цялото проклето нещо.

561
00:30:53,000 --> 00:30:55,000
>> Отново, ние не сме решаването на всичките ни проблеми.

562
00:30:55,000 --> 00:31:00,000
Ние сме за въвеждане на нови такива, но това наистина зависи от това, което се опитваме да проектираме.

563
00:31:00,000 --> 00:31:04,000
По отношение на прилагането на настоящия, ние може да заеме една идея от този студент структура.

564
00:31:04,000 --> 00:31:07,000
Синтаксис е много близък, с изключение на сега, идеята е малко по-абстрактно

565
00:31:07,000 --> 00:31:09,000
от къщата и името и ID.

566
00:31:09,000 --> 00:31:13,000
Но аз предлагам да имаме структура от данни в C

567
00:31:13,000 --> 00:31:17,000
, който се нарича възел, тъй като последната дума на слайд показва,

568
00:31:17,000 --> 00:31:21,000
вътрешността на възел и възел е само родово контейнер в областта на компютърните науки.

569
00:31:21,000 --> 00:31:25,000
Това обикновено се съставя като кръг или квадрат или правоъгълник, както сме правили.

570
00:31:25,000 --> 00:31:27,000
И в този структурата на данните, ние имаме едно цяло число, N,

571
00:31:27,000 --> 00:31:29,000
така че това е номер, който искате да съхраните.

572
00:31:29,000 --> 00:31:36,000
Но какъв е този втори ред, структура възел * следващия?

573
00:31:36,000 --> 00:31:40,000
Защо това е правилно, или каква роля играе това нещо игра,

574
00:31:40,000 --> 00:31:42,000
въпреки че е малко загадъчен на пръв поглед?

575
00:31:42,000 --> 00:31:44,000
Да.

576
00:31:44,000 --> 00:31:46,000
[Чува студент отговор]

577
00:31:46,000 --> 00:31:50,000
Точно така, така * нещо от плячката, че е показалеца на някакъв вид.

578
00:31:50,000 --> 00:31:53,000
Името на този указател е произволно следващия,

579
00:31:53,000 --> 00:32:00,000
но бихме могли да го нарича всичко, което искаме, но какво прави този указател точка за?

580
00:32:00,000 --> 00:32:03,000
[Student друг възел. >> Точно, посочва друг такъв възел.

581
00:32:03,000 --> 00:32:05,000
>> Сега, това е вид любопитството на C.

582
00:32:05,000 --> 00:32:09,000
Спомнете си, че C се чете от компилатор горе до долу, от ляво на дясно,

583
00:32:09,000 --> 00:32:13,000
което означава, че ако-това е малко по-различна от това, което направихме със студента.

584
00:32:13,000 --> 00:32:16,000
Когато се определя студент, ние всъщност не тури дума.

585
00:32:16,000 --> 00:32:18,000
Тя току-що каза typedef.

586
00:32:18,000 --> 00:32:20,000
Тогава имахме INT номер, низ име, струнен къща,

587
00:32:20,000 --> 00:32:23,000
и тогава студент в долната част на структурата.

588
00:32:23,000 --> 00:32:26,000
Тази декларация е малко по-различно, защото,

589
00:32:26,000 --> 00:32:28,000
отново компилатор е малко тъпо.

590
00:32:28,000 --> 00:32:30,000
Това е само да се чете отгоре надолу,

591
00:32:30,000 --> 00:32:33,000
така че ако се стигне до 2-ра линия

592
00:32:33,000 --> 00:32:37,000
където следващият е обявен и вижда, о, тук е променлива, наречена следващия.

593
00:32:37,000 --> 00:32:39,000
Това е указател към структура възел.

594
00:32:39,000 --> 00:32:42,000
Компилаторът ще разберем, каква е структурата на възел?

595
00:32:42,000 --> 00:32:44,000
Никога не съм чувал за това нещо преди,

596
00:32:44,000 --> 00:32:47,000
защото думата възел в противен случай може да не се появи

597
00:32:47,000 --> 00:32:49,000
до дъното, така че това е съкращение.

598
00:32:49,000 --> 00:32:53,000
Трябва да кажеш възел структура, която можете да съкрати по-късно

599
00:32:53,000 --> 00:32:56,000
благодарение на typedef тук, но това е защото

600
00:32:56,000 --> 00:33:02,000
съотнасяне на самата структура в рамките на структурата.

601
00:33:02,000 --> 00:33:05,000
Това е единственото нещо, за което има.

602
00:33:05,000 --> 00:33:07,000
>> Някои интересни проблеми ще възникнат.

603
00:33:07,000 --> 00:33:09,000
Имаме списък от числа. Как да вмъкнете в него?

604
00:33:09,000 --> 00:33:11,000
Как да го търся? Как да изтрия от него?

605
00:33:11,000 --> 00:33:13,000
Особено сега, че ние трябва да се справят всички тези насоки.

606
00:33:13,000 --> 00:33:15,000
Указатели бяха нещо на ума огъване

607
00:33:15,000 --> 00:33:17,000
, когато сте имали един от тях просто се опитвам да прочетете вътр.

608
00:33:17,000 --> 00:33:20,000
Сега ние трябва да манипулира струва целия списък.

609
00:33:20,000 --> 00:33:22,000
Защо не ни вземат 5-минутна почивка, а след това ще съживим

610
00:33:22,000 --> 00:33:34,000
някои хора на сцената, за да направят точно това.

611
00:33:34,000 --> 00:33:36,000
>> С е много по-забавно, когато е действал.

612
00:33:36,000 --> 00:33:39,000
Кой буквално би искал да бъде първи?

613
00:33:39,000 --> 00:33:41,000
Добре, хайде нагоре. Вие сте първи.

614
00:33:41,000 --> 00:33:44,000
Кой би искал да бъде 9? Добре, 9.

615
00:33:44,000 --> 00:33:46,000
Как около 9? 17?

616
00:33:46,000 --> 00:33:51,000
Малка групичка тук. 22 и 26, че предния ред.

617
00:33:51,000 --> 00:33:53,000
И тогава какво ще кажеш за някой там се посочи.

618
00:33:53,000 --> 00:33:57,000
Вие сте 34. Добре, 34, качвай се.

619
00:33:57,000 --> 00:33:59,000
На първо място е там. Добре, четирима от вас, момчета.

620
00:33:59,000 --> 00:34:01,000
И които не кажем за 9?

621
00:34:01,000 --> 00:34:04,000
Кой е 9?

622
00:34:04,000 --> 00:34:07,000
Кой наистина иска да бъде 9? Добре, хайде, 9.

623
00:34:07,000 --> 00:34:10,000
Ето ни.

624
00:34:10,000 --> 00:34:13,000
34, ние ще се срещнем там.

625
00:34:13,000 --> 00:34:17,000
Първата част е направи себе си изглежда така.

626
00:34:17,000 --> 00:34:21,000
26, 22, 17, добро.

627
00:34:21,000 --> 00:34:25,000
Ако може да стои встрани, защото ние ще ви изчистване в момента.

628
00:34:25,000 --> 00:34:29,000
>> Добре, добре.

629
00:34:29,000 --> 00:34:32,000
Добре, отлично, така че нека да задам няколко въпроса тук.

630
00:34:32,000 --> 00:34:34,000
И всъщност, какво е вашето име? >> Анита.

631
00:34:34,000 --> 00:34:37,000
Анита, добре, хайде тук.

632
00:34:37,000 --> 00:34:41,000
Анита ще ни помогне някак се реши сравнително прост въпрос в първата,

633
00:34:41,000 --> 00:34:44,000
което е как да разберете дали има или няма стойност е в списъка?

634
00:34:44,000 --> 00:34:48,000
Сега, забележете, че първо, представени тук от Лукас,

635
00:34:48,000 --> 00:34:52,000
е малко по-различно, и така си на парче хартия е умишлено странично

636
00:34:52,000 --> 00:34:55,000
, защото тя не е толкова висока и не взема колкото се може повече битове,

637
00:34:55,000 --> 00:34:58,000
въпреки че технически той има същия размер на хартията, просто се завърта.

638
00:34:58,000 --> 00:35:01,000
Но той е малко по-различна в това, че той е само на 32 бита за указател,

639
00:35:01,000 --> 00:35:05,000
и всички тези момчета са 64 бита, половината от която е номер, половината от които е указател.

640
00:35:05,000 --> 00:35:08,000
Но не е изобразен показалеца, така че ако вие може донякъде неловко

641
00:35:08,000 --> 00:35:12,000
използва лявата си ръка, за да посочи на човека до вас.

642
00:35:12,000 --> 00:35:14,000
А ти си номер 34. Как ти е името?

643
00:35:14,000 --> 00:35:16,000
Ари.

644
00:35:16,000 --> 00:35:19,000
Ари, така че всъщност, задръжте хартия в дясната си ръка, а лявата ръка отива право надолу.

645
00:35:19,000 --> 00:35:21,000
Вие декларирате нула на ляво.

646
00:35:21,000 --> 00:35:24,000
>> Сега нашата човешка картината е много последователен.

647
00:35:24,000 --> 00:35:26,000
Това е всъщност как указатели.

648
00:35:26,000 --> 00:35:29,000
И ако можете да смачквам малко по този начин, така че не съм във вашия начин.

649
00:35:29,000 --> 00:35:34,000
Анита тук, ме намерите номера 22,

650
00:35:34,000 --> 00:35:40,000
но поема ограничение не хората листчета,

651
00:35:40,000 --> 00:35:43,000
но това е списък, а имате само Лукас да започнем с

652
00:35:43,000 --> 00:35:46,000
защото той е буквално първият показалеца.

653
00:35:46,000 --> 00:35:51,000
Да предположим, че вие ​​самите сте показалеца, и така вие също имате възможността да се насоча към нещо.

654
00:35:51,000 --> 00:35:56,000
Защо не започнеш като посочи какво точно Лукас се посочи?

655
00:35:56,000 --> 00:35:58,000
Добър, и нека да приемат това тук.

656
00:35:58,000 --> 00:36:04,000
Само в името на дискусията, остави ме да извадя празна страница тук.

657
00:36:04,000 --> 00:36:06,000
Как се пише името ти? >> Анита.

658
00:36:06,000 --> 00:36:08,000
Добре, Анита.

659
00:36:08,000 --> 00:36:18,000
Да кажем, възел * Анита = Лукас.

660
00:36:18,000 --> 00:36:22,000
Е, ние не трябва да ти се обадя Лукас. Трябва да ти се обадя първо.

661
00:36:22,000 --> 00:36:25,000
Защо е това в действителност в съответствие с реалността тук?

662
00:36:25,000 --> 00:36:27,000
Едно, първата вече съществува.

663
00:36:27,000 --> 00:36:30,000
Първо е била разпределена вероятно някъде тук.

664
00:36:30,000 --> 00:36:35,000
Node * първо, и е бил предоставен списък по някакъв начин.

665
00:36:35,000 --> 00:36:37,000
Не знам как е станало това. Това се случи преди клас започва.

666
00:36:37,000 --> 00:36:40,000
Това свързан списък на хората е бил създаден.

667
00:36:40,000 --> 00:36:44,000
И сега, в този момент в историята - това е всичко, става Facebook очевидно по-късно

668
00:36:44,000 --> 00:36:49,000
в този момент в историята, Анита е инициализирана да бъде равна на първата,

669
00:36:49,000 --> 00:36:51,000
което не означава,, че Анита точки Лукас.

670
00:36:51,000 --> 00:36:53,000
Вместо това, тя посочва това, което той посочва

671
00:36:53,000 --> 00:36:57,000
защото един и същ адрес, който е в рамките на 32 бита Лукас - 1, 2, 3

672
00:36:57,000 --> 00:37:01,000
сега също е в рамките на 32 бита на Анита - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Сега намерете 22. Как ще го направите?

674
00:37:05,000 --> 00:37:07,000
Какво е това? >> Point какъвто и да е.

675
00:37:07,000 --> 00:37:11,000
Посочете какъвто и да е, така че давай напред и да действа възможно най-добре тук.

676
00:37:11,000 --> 00:37:15,000
Добре, добре, а сега сте посочите какво е вашето име с 22?

677
00:37:15,000 --> 00:37:18,000
Рамон. >> Рамон, така че Рамон се държи 22.

678
00:37:18,000 --> 00:37:20,000
Вече сте направили проверка.

679
00:37:20,000 --> 00:37:24,000
Ли Рамон == 22, и ако е така, например, ние може да се върне вярно.

680
00:37:24,000 --> 00:37:26,000
Нека, докато тези момчета стоя тук донякъде неловко

681
00:37:26,000 --> 00:37:32,000
позволете ми да направя нещо бързо като булев намери.

682
00:37:32,000 --> 00:37:37,000
Отивам да вървим напред и да кажем (възел * списък, вътр N).

683
00:37:37,000 --> 00:37:39,000
Аз ще се върна с вас. Аз просто трябва да напишете някакъв код.

684
00:37:39,000 --> 00:37:45,000
И сега отивам да вървим напред и да направите това, възел * Анита = списък.

685
00:37:45,000 --> 00:37:51,000
И аз ще отида напред и да се каже, докато (Анита! = NULL).

686
00:37:51,000 --> 00:37:57,000
>> Метафората тук става малко опъната, но докато (Анита! = NULL), какво искам да направя?

687
00:37:57,000 --> 00:38:03,000
Аз трябва по някакъв начин на съотнасяне

688
00:38:03,000 --> 00:38:05,000
цяло число, че Анита е насочена.

689
00:38:05,000 --> 00:38:08,000
В миналото, когато имахме структури, които възел е,

690
00:38:08,000 --> 00:38:11,000
използва нотация точка, и бихме казали нещо подобно

691
00:38:11,000 --> 00:38:15,000
anita.n, но проблемът тук е, че Анита не е структура на себе си.

692
00:38:15,000 --> 00:38:17,000
Какво е тя?

693
00:38:17,000 --> 00:38:21,000
Тя е показалеца, така че наистина, ако искаме да използваме тази точкова нотация

694
00:38:21,000 --> 00:38:23,000
и това ще изглежда умишлено малко загадъчен

695
00:38:23,000 --> 00:38:28,000
ние трябва да направим нещо като отидете на лявата ръка на каквото и Анита сочи към

696
00:38:28,000 --> 00:38:31,000
и след това получи областта н.

697
00:38:31,000 --> 00:38:35,000
Анита е указател, но какво е * Анита?

698
00:38:35,000 --> 00:38:38,000
Какво ли, че когато отидеш на това, което Анита е насочена?

699
00:38:38,000 --> 00:38:42,000
Структура, един възел, и възел, изземване, има поле, наречено н

700
00:38:42,000 --> 00:38:47,000
, защото, спомняте, тези две области, в непосредствена близост и N,

701
00:38:47,000 --> 00:38:50,000
, които видяхме преди малко тук.

702
00:38:50,000 --> 00:38:53,000
>> За да имитират това в кода,

703
00:38:53,000 --> 00:39:02,000
можем да направим това и казват, че ако ((* Анита) N ==), N, че гледам.

704
00:39:02,000 --> 00:39:04,000
Забележете, че функцията е приет в брой, което ме интересува.

705
00:39:04,000 --> 00:39:10,000
Тогава да вървим напред и да направим нещо подобно връщане вярно.

706
00:39:10,000 --> 00:39:12,000
Иначе, ако това не е така, какво искам да направя?

707
00:39:12,000 --> 00:39:19,000
Как мога да преведат код Какво Анита толкова интуитивно, като се разхождах из списъка?

708
00:39:19,000 --> 00:39:26,000
Какво трябва да направя тук, за да симулира Анита да предприемем тази стъпка на ляво, тази стъпка на ляво?

709
00:39:26,000 --> 00:39:28,000
[Чува студент отговор] >> Какво е това?

710
00:39:28,000 --> 00:39:30,000
[Чува студент отговор]

711
00:39:30,000 --> 00:39:34,000
Добър, не е лоша идея, но в миналото, когато сме направили това, ние сме направили Анита + +

712
00:39:34,000 --> 00:39:37,000
защото това щяло да добавите номера от 1 до Анита,

713
00:39:37,000 --> 00:39:40,000
които обикновено точка на следващото лице, като Рамон

714
00:39:40,000 --> 00:39:44,000
или лицето, до него или до него лице за установяване на ред.

715
00:39:44,000 --> 00:39:49,000
Но това не е съвсем добре тук, защото какво означава това нещо, което изглежда в паметта?

716
00:39:49,000 --> 00:39:54,000
Не е това. Ние трябва да изключите.

717
00:39:54,000 --> 00:40:00,000
Той изглежда така в паметта, и въпреки че съм 1 и 2 и 3 близо една до друга,

718
00:40:00,000 --> 00:40:03,000
ако наистина симулира това може момчета, докато все още сочи едни и същи хора,

719
00:40:03,000 --> 00:40:07,000
може някои от вас да вземе случаен стъпка назад, някои от вас случаен крачка напред?

720
00:40:07,000 --> 00:40:10,000
>> Тази бъркотия е все още свързан списък,

721
00:40:10,000 --> 00:40:13,000
но тези момчета може да е навсякъде в паметта,

722
00:40:13,000 --> 00:40:15,000
така Анита + + не се ходи на работа, защо?

723
00:40:15,000 --> 00:40:19,000
Какъв е място Анита + +?

724
00:40:19,000 --> 00:40:21,000
Кой знае.

725
00:40:21,000 --> 00:40:24,000
Това е някаква друга стойност, която просто така се случва да се намеси

726
00:40:24,000 --> 00:40:28,000
сред всички тези възли по случайност, защото ние не сме масив.

727
00:40:28,000 --> 00:40:30,000
Разпределят на всеки един от тези възли поотделно.

728
00:40:30,000 --> 00:40:32,000
Добре, ако вие сами можете да почистите обратно.

729
00:40:32,000 --> 00:40:37,000
Позволете ми предложи вместо на Анита + +, вместо това Анита стане

730
00:40:37,000 --> 00:40:42,000
добре, защо не отидем какъвто и да е Анита е насочена и след това направете следваща?

731
00:40:42,000 --> 00:40:45,000
С други думи, ние се връщаме към Рамон, който е номер 22,

732
00:40:45,000 --> 00:40:51,000
и след това следващата е като че Анита ще бъдат копиране лявата си ръка показалеца.

733
00:40:51,000 --> 00:40:54,000
Но тя не искаше отидат по-далеч от Рамон, защото открихме 22.

734
00:40:54,000 --> 00:40:56,000
Но това би било идеята. Сега, това е бог ужасна бъркотия.

735
00:40:56,000 --> 00:40:59,000
Честно казано, никой няма да си спомня този синтаксис и толкова щастие,

736
00:40:59,000 --> 00:41:04,000
това е всъщност малко съзнателно-о, не всъщност да видим какво съм написал.

737
00:41:04,000 --> 00:41:08,000
Това ще бъде по-убедителен, ако можеш. Voila!

738
00:41:08,000 --> 00:41:10,000
>> Зад кулисите бях решаване на проблема по този начин.

739
00:41:10,000 --> 00:41:14,000
Анита, да предприемат тази стъпка на ляво,

740
00:41:14,000 --> 00:41:18,000
първо място, ние трябва да излизат на адреса, който Анита сочи към

741
00:41:18,000 --> 00:41:23,000
и където ще намерите не само N, който току-що проверих за сравнение,

742
00:41:23,000 --> 00:41:25,000
но вие също ще намери следващото - в този случай,

743
00:41:25,000 --> 00:41:28,000
Лявата ръка на Рамон сочи към следващия възел в списъка.

744
00:41:28,000 --> 00:41:32,000
Но това е бог-ужасната бъркотия, в която по-горе споменах,

745
00:41:32,000 --> 00:41:34,000
но се оказва, C ни позволява да се опрости тази процедура.

746
00:41:34,000 --> 00:41:40,000
Вместо да пишете (* Анита), може вместо това просто напишете Анита->

747
00:41:40,000 --> 00:41:45,000
и това е точно същото нещо функционално, но това е много по-интуитивен,

748
00:41:45,000 --> 00:41:48,000
и това е много повече в съответствие с картината, която ние сме били изготвяне

749
00:41:48,000 --> 00:41:50,000
през цялото това време с помощта на стрелките.

750
00:41:50,000 --> 00:41:57,000
>> И накрая, какво трябва да се направи в края на тази програма?

751
00:41:57,000 --> 00:42:00,000
Има един ред код останалите.

752
00:42:00,000 --> 00:42:02,000
Връщане какво?

753
00:42:02,000 --> 00:42:05,000
False, защото ако ние се през цялата линия, докато

754
00:42:05,000 --> 00:42:10,000
и Анита, в действителност, е нула, това означава, че тя отиде по целия път до края на списъка

755
00:42:10,000 --> 00:42:12,000
където тя е била посочите какво е вашето име?

756
00:42:12,000 --> 00:42:15,000
Лявата Ари. >> Ари ръка, което е нищожна.

757
00:42:15,000 --> 00:42:18,000
Анита е нула, и разбирам, че сте просто стоя тук неловко в състояние на неопределеност

758
00:42:18,000 --> 00:42:21,000
защото аз отивам на монолог тук,

759
00:42:21,000 --> 00:42:23,000
но ние ще ви включва отново само за миг.

760
00:42:23,000 --> 00:42:27,000
Анита е нищожна в този момент в историята, така линия, докато се прекратява,

761
00:42:27,000 --> 00:42:30,000
и ние трябва да върнем невярно, защото ако тя има целия път до нулев указател на Ари

762
00:42:30,000 --> 00:42:34,000
тогава не е имало номер, който търсеше в списъка.

763
00:42:34,000 --> 00:42:39,000
Да почистите прекалено, но това е доста добро изпълнение

764
00:42:39,000 --> 00:42:43,000
на функция прекосява, функция за свързан списък.

765
00:42:43,000 --> 00:42:48,000
Тя все още е линейна търсене, но това не е толкова просто, колкото + + указател

766
00:42:48,000 --> 00:42:52,000
или + + променлива и защото сега не можем да се досетите

767
00:42:52,000 --> 00:42:54,000
, където всеки един от тези възли са в паметта.

768
00:42:54,000 --> 00:42:57,000
Ние трябва буквално да се проследи пътя на галета или по-точно,

769
00:42:57,000 --> 00:43:00,000
указатели, за да получите от един възел към друг.

770
00:43:00,000 --> 00:43:02,000
>> Сега нека се опитаме друг. Анита, искам да се върна тук?

771
00:43:02,000 --> 00:43:06,000
Защо не отидем напред и да предостави още един човек от публиката?

772
00:43:06,000 --> 00:43:08,000
Изчистване какво е вашето име? >> Ребека.

773
00:43:08,000 --> 00:43:10,000
Ребека. Ребека е malloced от публиката,

774
00:43:10,000 --> 00:43:13,000
и тя се съхранява на номер 55.

775
00:43:13,000 --> 00:43:17,000
А целта на ръка в момента е Анита да вмъкнете

776
00:43:17,000 --> 00:43:22,000
Ребека в свързан списък в съответното място.

777
00:43:22,000 --> 00:43:24,000
Хайде тук за момент.

778
00:43:24,000 --> 00:43:28,000
Съм правил нещо подобно.

779
00:43:28,000 --> 00:43:32,000
Съм направил възел *. И какво е вашето име?

780
00:43:32,000 --> 00:43:34,000
Rebecca. >> Ребека, добре.

781
00:43:34,000 --> 00:43:41,000
Ребека получава изчистване (sizeof (възел)).

782
00:43:41,000 --> 00:43:44,000
Точно както се разпределят като студенти и какво ли още не неща в миналото,

783
00:43:44,000 --> 00:43:46,000
ние се нуждаем от размера на възела, така че сега Ребека

784
00:43:46,000 --> 00:43:49,000
сочи в какво?

785
00:43:49,000 --> 00:43:52,000
Ребека има две полета вътре в нея, единият от които е 55.

786
00:43:52,000 --> 00:43:55,000
Нека да направим това, което Ребека> = 55.

787
00:43:55,000 --> 00:44:00,000
Но тогава Ребека-> следващия трябва да бъде както сега, нейната ръка е нещо кой знае?

788
00:44:00,000 --> 00:44:03,000
Това сочи някои боклук стойност, така че защо да не направим за добра мярка

789
00:44:03,000 --> 00:44:07,000
ние поне правим това, така че лявата ръка е в нея.

790
00:44:07,000 --> 00:44:09,000
Сега Анита, вземете я от тук.

791
00:44:09,000 --> 00:44:11,000
Имате Ребека които са били разпределени.

792
00:44:11,000 --> 00:44:20,000
Давай напред и да откриете къде трябва да сложим Ребека.

793
00:44:20,000 --> 00:44:25,000
Добре, много добре.

794
00:44:25,000 --> 00:44:28,000
Добре, хубаво, а сега ние трябва да предостави малко на посоката,

795
00:44:28,000 --> 00:44:30,000
така че сте достигнали Ари.

796
00:44:30,000 --> 00:44:33,000
Лявата му ръка е нулев, но Ребека ясно принадлежи към правото,

797
00:44:33,000 --> 00:44:36,000
така че как ние трябва да се промени този свързан списък

798
00:44:36,000 --> 00:44:38,000
за да вмъкнете Ребека в подходящо място?

799
00:44:38,000 --> 00:44:42,000
Ако може буквално да се движи наляво ръцете на хората наоколо, ако е необходимо,

800
00:44:42,000 --> 00:44:48,000
ще отстраните проблема по този начин.

801
00:44:48,000 --> 00:44:52,000
Добре, добре, а междувременно, лявата ръка Ребека сега е до нея.

802
00:44:52,000 --> 00:44:54,000
>> Това е твърде лесно.

803
00:44:54,000 --> 00:44:57,000
Нека се опитаме разпределяне сме почти готови, 20.

804
00:44:57,000 --> 00:44:59,000
Добре, хайде нагоре.

805
00:44:59,000 --> 00:45:04,000
20 са разпределени, така че нека да вървим напред и да кажа отново тук

806
00:45:04,000 --> 00:45:07,000
ние току-що направихте възел * Саад.

807
00:45:07,000 --> 00:45:11,000
Имаме изчистване (sizeof (възел)).

808
00:45:11,000 --> 00:45:16,000
След това направете същото точния синтаксис, както направихме преди 20,

809
00:45:16,000 --> 00:45:20,000
и аз ще направя следващия = NULL, и сега той е до Анита

810
00:45:20,000 --> 00:45:23,000
да поставите в свързан списък, ако бихте могли да играят точно същата роля.

811
00:45:23,000 --> 00:45:30,000
Execute.

812
00:45:30,000 --> 00:45:32,000
Добре, добре.

813
00:45:32,000 --> 00:45:38,000
Сега помислете внимателно, преди да започнете да се движите левите си ръце около.

814
00:45:38,000 --> 00:45:46,000
Далеч най-неловко роля днес.

815
00:45:46,000 --> 00:45:59,000
Чиято ръка трябва да се премести първо?

816
00:45:59,000 --> 00:46:02,000
Добре, чакай, аз чувам някои не.

817
00:46:02,000 --> 00:46:07,000
Ако някои хора учтиво искали да помогнат за решаването неловка ситуация тук.

818
00:46:07,000 --> 00:46:11,000
Първия може би трябва да се актуализира, чиято лява ръка? Да.

819
00:46:11,000 --> 00:46:13,000
Студентски] Саад.

820
00:46:13,000 --> 00:46:15,000
Добре, Саад, защо, нали?

821
00:46:15,000 --> 00:46:17,000
[Чува студент отговор]

822
00:46:17,000 --> 00:46:19,000
Добре, защото ако се движим какво е вашето име? >> Маршал.

823
00:46:19,000 --> 00:46:22,000
Маршал, ако се движим ръката си пръв до нула,

824
00:46:22,000 --> 00:46:25,000
сега сме буквално сираци четирима души в този списък

825
00:46:25,000 --> 00:46:29,000
защото той е единственото нещо, което сочи на Рамон и всеки наляво,

826
00:46:29,000 --> 00:46:31,000
така актуализиране че показалеца първият беше лошо.

827
00:46:31,000 --> 00:46:33,000
Да отмените че.

828
00:46:33,000 --> 00:46:37,000
Хубаво, а сега вървим напред и да се премести подходяща лявата ръка посочи Рамон.

829
00:46:37,000 --> 00:46:39,000
Това се чувства малко излишно.

830
00:46:39,000 --> 00:46:41,000
Сега вече има двама души, сочещи към Рамон, но това е добре

831
00:46:41,000 --> 00:46:43,000
защото сега как по друг начин да актуализира списъка?

832
00:46:43,000 --> 00:46:48,000
Каква друга страна, трябва да се движат?

833
00:46:48,000 --> 00:46:53,000
Отлично, сега имаме загуби на паметта?

834
00:46:53,000 --> 00:46:57,000
Не, по-добре, нека да видим дали не можем да се разбие още веднъж.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing за последен път, номер 5.

836
00:47:00,000 --> 00:47:04,000
Начина, по гърба, хайде надолу.

837
00:47:04,000 --> 00:47:08,000
Това е много вълнуващо.

838
00:47:08,000 --> 00:47:15,000
[Аплодисменти]

839
00:47:15,000 --> 00:47:17,000
Как ти е името? >> Рон.

840
00:47:17,000 --> 00:47:19,000
Рон, добре, ти се malloced като номер 5.

841
00:47:19,000 --> 00:47:23,000
Ние току-що се извършват код, който е почти идентичен с тези

842
00:47:23,000 --> 00:47:26,000
само с различно име.

843
00:47:26,000 --> 00:47:28,000
Отлично.

844
00:47:28,000 --> 00:47:38,000
Сега, Анита, късмет вмъкване на номер пет в списъка.

845
00:47:38,000 --> 00:47:43,000
Добър, и?

846
00:47:43,000 --> 00:47:47,000
Отличен, така че това наистина е трета от три общия брой случаи.

847
00:47:47,000 --> 00:47:49,000
За първи път има някой, който в края, Ребека.

848
00:47:49,000 --> 00:47:51,000
След това имаше някой в ​​средата.

849
00:47:51,000 --> 00:47:53,000
Сега имаме някой в ​​началото, и в този пример,

850
00:47:53,000 --> 00:47:56,000
ние сега трябваше да актуализира Лукас за първи път

851
00:47:56,000 --> 00:48:00,000
защото първият елемент в списъка сега трябва да посочи нов възел,

852
00:48:00,000 --> 00:48:03,000
, които, от своя страна, е насочена на възела номер 9.

853
00:48:03,000 --> 00:48:06,000
>> Това беше изключително неудобно демонстрация, аз съм сигурен,

854
00:48:06,000 --> 00:48:08,000
толкова голям аплодисменти за тези момчета, ако можеш.

855
00:48:08,000 --> 00:48:11,000
Добре направено.

856
00:48:11,000 --> 00:48:17,000
Това е всичко. Може да си парчета хартия като малко памет.

857
00:48:17,000 --> 00:48:22,000
Оказва се, че правят това в код

858
00:48:22,000 --> 00:48:26,000
не е толкова просто, колкото просто се движат ръцете си около

859
00:48:26,000 --> 00:48:28,000
и да посочи указатели най-различни неща.

860
00:48:28,000 --> 00:48:31,000
Но осъзнават, че когато дойде време да приложи нещо подобно

861
00:48:31,000 --> 00:48:34,000
свързан списък или вариант от него, ако се съсредоточи върху наистина

862
00:48:34,000 --> 00:48:38,000
тези основни основните проблеми, хапят по размер, аз трябва да разбера,

863
00:48:38,000 --> 00:48:43,000
е тази ръка или тази ръка, да разбере, че това, което иначе е доста сложна програма

864
00:48:43,000 --> 00:48:47,000
, в действителност, може да бъде намалена до сравнително прости градивни елементи, като този.

865
00:48:47,000 --> 00:48:51,000
>> Нека погледнем на нещата в по-сложна посока все още.

866
00:48:51,000 --> 00:48:53,000
Ние вече имаме понятието за свързан списък.

867
00:48:53,000 --> 00:48:57,000
Ние също имаме благодарение на предложение има двойно свързан списък,

868
00:48:57,000 --> 00:49:01,000
който изглежда почти същата, но сега имаме две указатели в рамките на структурата на

869
00:49:01,000 --> 00:49:05,000
вместо един, и ние вероятно биха могли да наречем тези указатели предишен и следващ

870
00:49:05,000 --> 00:49:08,000
или наляво или надясно, но ние, всъщност, се нуждаят от две от тях.

871
00:49:08,000 --> 00:49:10,000
Кодът ще бъде малко по-сложен.

872
00:49:10,000 --> 00:49:12,000
Анита би трябвало да свърши повече работа тук, на сцената.

873
00:49:12,000 --> 00:49:15,000
Но ние със сигурност може да изпълнява този вид структура.

874
00:49:15,000 --> 00:49:19,000
По отношение на времето за работа, обаче, какво ще бъде времето за работа

875
00:49:19,000 --> 00:49:24,000
за Анита за намиране на редица N в свързан списък?

876
00:49:24,000 --> 00:49:27,000
Все още голяма O N, така че не е по-добре, отколкото линейно търсене.

877
00:49:27,000 --> 00:49:29,000
Не можем да направим двоично търсене, обаче, отново.

878
00:49:29,000 --> 00:49:34,000
Защо бе, че делото? Вие не можете да скачат.

879
00:49:34,000 --> 00:49:36,000
Въпреки, че очевидно всички хора на сцената,

880
00:49:36,000 --> 00:49:39,000
и Анита да го eyeballed и каза: "Ето средата на списъка"

881
00:49:39,000 --> 00:49:42,000
тя няма да знаят, че ако тя беше компютърна програма

882
00:49:42,000 --> 00:49:47,000
защото единственото, което тя трябваше да засуче в началото на сценария

883
00:49:47,000 --> 00:49:50,000
Лукас, който е първият показалеца.

884
00:49:50,000 --> 00:49:53,000
Тя непременно ще трябва да се следват тези връзки,

885
00:49:53,000 --> 00:49:56,000
преброяване по пътя си, докато намери около средата,

886
00:49:56,000 --> 00:49:58,000
и дори тогава тя не ще да знае кога е достигнал средата

887
00:49:58,000 --> 00:50:01,000
освен ако тя отива по целия път до края, за да разбера колко са,

888
00:50:01,000 --> 00:50:05,000
след това backtracks, което също би било трудно, ако не беше

889
00:50:05,000 --> 00:50:07,000
двойно свързан списък от някакъв вид.

890
00:50:07,000 --> 00:50:10,000
>> Решаването на някои проблеми днес, но въвеждането на другите.

891
00:50:10,000 --> 00:50:12,000
Ами съвсем различна структура от данни?

892
00:50:12,000 --> 00:50:15,000
Това е снимка от тавите в Mather House,

893
00:50:15,000 --> 00:50:19,000
и в този случай, ние имаме структурата на данните сме също вид вече се говори за.

894
00:50:19,000 --> 00:50:22,000
Ние говорихме за комин в контекста на паметта,

895
00:50:22,000 --> 00:50:26,000
и това е един вид умишлено име, защото стак в условията на паметта

896
00:50:26,000 --> 00:50:31,000
е ефективно структурата на данните, че има все повече и повече неща, наслоени върху нея.

897
00:50:31,000 --> 00:50:35,000
Но интересното нещо за комин, какъвто е случаят в действителност,

898
00:50:35,000 --> 00:50:38,000
е, че той е специален вид на структурата на данните.

899
00:50:38,000 --> 00:50:42,000
Това е структурата на данните, при която първият елемент в

900
00:50:42,000 --> 00:50:46,000
е последният елемент.

901
00:50:46,000 --> 00:50:50,000
Ако вие сте първата тава, за да бъдат поставени върху стека,

902
00:50:50,000 --> 00:50:53,000
ти започваш да бъде за съжаление последната тава, за да се вземат стека,

903
00:50:53,000 --> 00:50:55,000
и това не е непременно нещо добро.

904
00:50:55,000 --> 00:50:58,000
От друга страна, можеш да се сетиш за него по друг начин,

905
00:50:58,000 --> 00:51:02,000
последната е на първо навън.

906
00:51:02,000 --> 00:51:05,000
>> Сега, всички сценарии идват на ум, когато като комин

907
00:51:05,000 --> 00:51:08,000
структурата на данните, където имате този имот

908
00:51:08,000 --> 00:51:13,000
на последния, първи излязъл, всъщност е убедителна?

909
00:51:13,000 --> 00:51:16,000
Че нещо добро? Че нещо лошо?

910
00:51:16,000 --> 00:51:19,000
Това определено е нещо лошо, ако тава не са идентични

911
00:51:19,000 --> 00:51:21,000
и всички те са били специални различни цветове или какво ли не,

912
00:51:21,000 --> 00:51:24,000
и желания от вас цвят е чак в дъното.

913
00:51:24,000 --> 00:51:26,000
Разбира се, не може да се получи, че без много усилия.

914
00:51:26,000 --> 00:51:28,000
Вие трябва да започнете от върха и да си проправите път надолу.

915
00:51:28,000 --> 00:51:31,000
Също така, какво ще стане, ако вие бяхте един от тези фен момчета

916
00:51:31,000 --> 00:51:34,000
, който чака цяла нощ, опитвайки се да се сдобиете с iPhone и линии до

917
00:51:34,000 --> 00:51:36,000
на място като това?

918
00:51:36,000 --> 00:51:40,000
Не би ли било хубаво, ако в магазина Apple

919
00:51:40,000 --> 00:51:42,000
структура стека данни?

920
00:51:42,000 --> 00:51:44,000
Yay? Най?

921
00:51:44,000 --> 00:51:47,000
Това е само добро за хората, които се показват в последната възможна минута

922
00:51:47,000 --> 00:51:50,000
и след това се изуваше на опашката.

923
00:51:50,000 --> 00:51:52,000
И всъщност, факта, че съм бил толкова склонен да кажа на опашката

924
00:51:52,000 --> 00:51:56,000
всъщност е в съответствие с това, което бихме могли да наречем този вид на структурата на данните,

925
00:51:56,000 --> 00:51:59,000
в действителност, когато заповедта е от значение,

926
00:51:59,000 --> 00:52:02,000
и искате първата, за да бъде първият

927
00:52:02,000 --> 00:52:04,000
ако само в името на човешката справедливост.

928
00:52:04,000 --> 00:52:07,000
Ще се обадя, че опашката структура на данните.

929
00:52:07,000 --> 00:52:11,000
>> Оказва се, че освен свързани списъци, да започнете да използвате тези едни и същи идеи

930
00:52:11,000 --> 00:52:15,000
и започнете да създавате нови и различни видове решения на проблемите.

931
00:52:15,000 --> 00:52:19,000
Например, в случай на комин, бихме могли да представляват комин

932
00:52:19,000 --> 00:52:22,000
с помощта на структурата на данните по този начин, бих предложила.

933
00:52:22,000 --> 00:52:26,000
В този случай, съм обявен за структура, и аз съм казал в рамките на тази структура

934
00:52:26,000 --> 00:52:30,000
е масив от числа и след това променлива наречена размер,

935
00:52:30,000 --> 00:52:33,000
и аз отивам да се обадя това нещо комин.

936
00:52:33,000 --> 00:52:35,000
Сега, защо това действително работят?

937
00:52:35,000 --> 00:52:43,000
В случай на комин, може да се направи това ефективно на екрана като масив.

938
00:52:43,000 --> 00:52:47,000
Тук е моят стак. Това са моите номера.

939
00:52:47,000 --> 00:52:50,000
И ще ги привлече, тъй като това, това, това, това, това.

940
00:52:50,000 --> 00:52:53,000
И тогава някой друг член на данни,

941
00:52:53,000 --> 00:52:58,000
който се нарича размер, така че това е размер, и това е номера,

942
00:52:58,000 --> 00:53:02,000
и колективно, цялата IPAD тук представлява една купчина структура.

943
00:53:02,000 --> 00:53:07,000
Сега, по подразбиране, размер вероятно трябва да се инициализира с 0,

944
00:53:07,000 --> 00:53:11,000
и това, което е вътре на масив от числа първоначално

945
00:53:11,000 --> 00:53:14,000
, когато за пръв път разпределят масив?

946
00:53:14,000 --> 00:53:16,000
Garbage. Кой знае? И това всъщност не е от значение.

947
00:53:16,000 --> 00:53:20,000
Няма значение дали това е 1, 2, 3, 4, 5, напълно случайно

948
00:53:20,000 --> 00:53:25,000
от лош късмет, съхранявани в моята структура, защото доколкото аз знам, че размера на стека

949
00:53:25,000 --> 00:53:29,000
е 0, тогава знам, програмно, не изглежда във всеки един от елементите в масива.

950
00:53:29,000 --> 00:53:31,000
Няма значение какво е там.

951
00:53:31,000 --> 00:53:34,000
Не гледайте на тях, тъй като ще бъде отражение на размера на 0.

952
00:53:34,000 --> 00:53:38,000
>> Но да предположим, сега отивам напред и поставете нещо в стека.

953
00:53:38,000 --> 00:53:42,000
Искам да въведете номера 5, така че сложих номер 5 тук,

954
00:53:42,000 --> 00:53:45,000
и после какво мога да остави тук?

955
00:53:45,000 --> 00:53:48,000
Сега всъщност ще милион за размера,

956
00:53:48,000 --> 00:53:50,000
и сега стека е с размер 1.

957
00:53:50,000 --> 00:53:53,000
Какво ще стане, ако отида напред и да въведете номера, нека кажем, 7 следващия?

958
00:53:53,000 --> 00:53:57,000
След това се обновява на 2, а след това ние ще направим 9,

959
00:53:57,000 --> 00:54:02,000
и след това получава актуализирана до 3.

960
00:54:02,000 --> 00:54:05,000
Но интересна особеност на тази стека е, че

961
00:54:05,000 --> 00:54:09,000
Аз трябва да премахнете елемент, ако искам да се появи

962
00:54:09,000 --> 00:54:12,000
нещо на комина, така да се каже?

963
00:54:12,000 --> 00:54:14,000
9 ще бъде първото нещо, което трябва да отида.

964
00:54:14,000 --> 00:54:18,000
Как трябва картината се промени, ако искам да се появи елемент на разстояние от стека,

965
00:54:18,000 --> 00:54:20,000
много прилича на тавата в Mather?

966
00:54:20,000 --> 00:54:22,000
Да. >> Студентски] Set размер на 2.

967
00:54:22,000 --> 00:54:27,000
Точно така, всичко, което правя, е определен размер на 2, и какво да правя с масива?

968
00:54:27,000 --> 00:54:29,000
Не е нужно да правите нищо.

969
00:54:29,000 --> 00:54:32,000
Можех, само за да бъде анален, сложи 0 или -1 или нещо, което да покаже,

970
00:54:32,000 --> 00:54:34,000
че това не е легитимен стойност, но това няма значение, защото

971
00:54:34,000 --> 00:54:37,000
Може да записва извън самия масив, колко е дълго

972
00:54:37,000 --> 00:54:41,000
така че аз знам само погледнете първите два елемента в този масив.

973
00:54:41,000 --> 00:54:47,000
Сега, ако отида и добавете номер 8 до този масив, как картината се промени след това?

974
00:54:47,000 --> 00:54:50,000
Това става 8, и това става 3.

975
00:54:50,000 --> 00:54:52,000
Аз съм рязане на няколко ъгли.

976
00:54:52,000 --> 00:54:56,000
Сега имаме 5, 7, 8, и ние сме обратно в размер на 3.

977
00:54:56,000 --> 00:54:58,000
Това е доста лесно да се осъществи,

978
00:54:58,000 --> 00:55:06,000
но когато отиваме да съжалявам за това дизайнерско решение?

979
00:55:06,000 --> 00:55:09,000
Когато нещата започват да отиде много, много грешно? Да.

980
00:55:09,000 --> 00:55:11,000
[Чува студент отговор]

981
00:55:11,000 --> 00:55:13,000
Когато искате да се върнете и да получите първи елемент, който инча

982
00:55:13,000 --> 00:55:18,000
>> Оказва се, че тук, макар и комин е масив под капака,

983
00:55:18,000 --> 00:55:21,000
тези структури от данни, които сме започнали да говорим за известна като

984
00:55:21,000 --> 00:55:25,000
абстрактни структури от данни, как те се изпълняват

985
00:55:25,000 --> 00:55:27,000
е напълно освен точка.

986
00:55:27,000 --> 00:55:31,000
Структурата на данните като комин е трябвало да добави поддръжка

987
00:55:31,000 --> 00:55:35,000
операции, като тласък, който настоява поднос върху стека,

988
00:55:35,000 --> 00:55:39,000
и поп, която премахва елемент от стека, и това е всичко.

989
00:55:39,000 --> 00:55:43,000
Ако ви се налага да свалите някой друг код, който вече се прилага

990
00:55:43,000 --> 00:55:46,000
това нещо, наречено комин, че човек би написал

991
00:55:46,000 --> 00:55:49,000
само две функции за вас, натиснете и поп, чиято единствена цел в живота

992
00:55:49,000 --> 00:55:51,000
би било да се направи точно това.

993
00:55:51,000 --> 00:55:54,000
Вие или него или нея, които изпълняват тази програма

994
00:55:54,000 --> 00:55:58,000
би било напълно да се реши как да се прилагат

995
00:55:58,000 --> 00:56:00,000
семантиката на бутане и мак под капака

996
00:56:00,000 --> 00:56:03,000
или функционалността на бутане и мак.

997
00:56:03,000 --> 00:56:07,000
И аз съм малко недалновидно решение тук

998
00:56:07,000 --> 00:56:10,000
чрез прилагане на стака ми с тази проста структура на данните, защо?

999
00:56:10,000 --> 00:56:12,000
Кога този структурата на данните почивка?

1000
00:56:12,000 --> 00:56:18,000
В кой момент трябва да върне грешка, когато потребителят изисква натискане, например?

1001
00:56:18,000 --> 00:56:20,000
[Student] Ако няма повече място.

1002
00:56:20,000 --> 00:56:23,000
Точно така, ако няма повече пространство, ако съм надвишаването на капацитета,

1003
00:56:23,000 --> 00:56:27,000
, което е с главни букви, защото предполага, че това е някакъв вид на глобалната константа.

1004
00:56:27,000 --> 00:56:30,000
Е, тогава аз просто ще трябва да го кажа: "Съжалявам, не мога да прокара друга стойност

1005
00:56:30,000 --> 00:56:32,000
върху стека, "много искал в Mather.

1006
00:56:32,000 --> 00:56:36,000
>> В един момент, те ще продължават да се удари в горната част на този малък кабинет.

1007
00:56:36,000 --> 00:56:39,000
Няма повече пространство или капацитет в стека, при което има някаква грешка.

1008
00:56:39,000 --> 00:56:42,000
Те трябва да сложите елемента някъде другаде, тавата някъде другаде,

1009
00:56:42,000 --> 00:56:44,000
или никъде.

1010
00:56:44,000 --> 00:56:47,000
Сега, с опашка, бихме могли да го приложи малко по-различно.

1011
00:56:47,000 --> 00:56:50,000
Опашката е малко по-различна в това, че под предния капак, може да се прилага

1012
00:56:50,000 --> 00:56:54,000
като масив, но защо, в този случай, аз предлага

1013
00:56:54,000 --> 00:56:59,000
да има елемент, представляващ глава начело на списъка,

1014
00:56:59,000 --> 00:57:06,000
предната част на списъка, първият човек, на опашка в магазина на Apple, в допълнение към размера?

1015
00:57:06,000 --> 00:57:14,000
Защо ми е необходим допълнителен част от данните тук?

1016
00:57:14,000 --> 00:57:16,000
Помислете за какви номера

1017
00:57:16,000 --> 00:57:18,000
ако съм съставянето му, както следва.

1018
00:57:18,000 --> 00:57:21,000
Да предположим, че това сега е опашката вместо комин,

1019
00:57:21,000 --> 00:57:24,000
разликата е точно като Apple магазин опашката е честно.

1020
00:57:24,000 --> 00:57:27,000
Първият човек, на опашка в началото на списъка, номер 5 в този случай,

1021
00:57:27,000 --> 00:57:30,000
той или тя ще бъде пуснат в магазина първо.

1022
00:57:30,000 --> 00:57:32,000
Нека го направим.

1023
00:57:32,000 --> 00:57:35,000
Да предположим, че това е състоянието на опашката ми в този момент във времето, и сега в магазина на Apple

1024
00:57:35,000 --> 00:57:39,000
се отваря и се води от първо лице, номер 5, в магазина.

1025
00:57:39,000 --> 00:57:43,000
Как мога да променя картината сега, че съм-опашка от първо лице

1026
00:57:43,000 --> 00:57:47,000
в предната част на линията?

1027
00:57:47,000 --> 00:57:50,000
Какво е това? >> Студентски] Промяна на опашката.

1028
00:57:50,000 --> 00:57:52,000
Промяна на главата, така че 5 изчезва.

1029
00:57:52,000 --> 00:57:56,000
В действителност, това е като че най-добрия начин да направите това?

1030
00:57:56,000 --> 00:58:00,000
В действителност, това е като че ли този човек изчезва.

1031
00:58:00,000 --> 00:58:03,000
Какво би номер 7 в реален магазин?

1032
00:58:03,000 --> 00:58:05,000
Те ще направят голяма крачка напред.

1033
00:58:05,000 --> 00:58:08,000
>> Но това, което сме дошли да оценят, когато става въпрос за масиви

1034
00:58:08,000 --> 00:58:10,000
и движещи се неща наоколо?

1035
00:58:10,000 --> 00:58:12,000
Това е вид на загуба на време, нали?

1036
00:58:12,000 --> 00:58:16,000
Защо трябва да бъде толкова анален, за да има първо лице

1037
00:58:16,000 --> 00:58:21,000
в началото на линията на физически началото на парчето на паметта?

1038
00:58:21,000 --> 00:58:23,000
Това е напълно ненужно. Защо?

1039
00:58:23,000 --> 00:58:26,000
Какво би могло Помня само, а? >> Чува студент отговор]

1040
00:58:26,000 --> 00:58:30,000
Точно така, аз просто не забравяйте главата с този допълнителен член данни

1041
00:58:30,000 --> 00:58:34,000
че сега начело на списъка вече не е 0, което беше преди малко.

1042
00:58:34,000 --> 00:58:39,000
Сега е всъщност номер 1. По този начин, аз се леко оптимизация.

1043
00:58:39,000 --> 00:58:44,000
Само защото съм де-опашка някой от ред в началото на линията на Apple магазин

1044
00:58:44,000 --> 00:58:47,000
не означава, че всеки трябва да се смени, които изземване е линейна операция.

1045
00:58:47,000 --> 00:58:50,000
Вместо това мога да прекарат константно време само

1046
00:58:50,000 --> 00:58:53,000
и да се постигне много по-бърз отговор.

1047
00:58:53,000 --> 00:58:56,000
Но цената си плащам, какво да получат тази допълнителна производителност

1048
00:58:56,000 --> 00:58:58,000
и не се налага да се прехвърлят на всички?

1049
00:58:58,000 --> 00:59:01,000
Да. >> Чува студент отговор]

1050
00:59:01,000 --> 00:59:04,000
Може да добавите още хора, добре, че проблемът е ортогонална

1051
00:59:04,000 --> 00:59:07,000
на факта, че ние не измества хората около.

1052
00:59:07,000 --> 00:59:11,000
Тя все още е масив, така че дали трябва или не прехвърли всички или не

1053
00:59:11,000 --> 00:59:13,000
О, разбирам какво искаш да кажеш, добре.

1054
00:59:13,000 --> 00:59:16,000
Всъщност, съгласен съм с това, което казваш, че това е почти като че

1055
00:59:16,000 --> 00:59:19,000
сега ние никога няма да използват вече началото на този масив

1056
00:59:19,000 --> 00:59:22,000
защото ако премахна 5, след това премахна 7.

1057
00:59:22,000 --> 00:59:24,000
Но аз само поставят хората в дясно.

1058
00:59:24,000 --> 00:59:28,000
>> Имам чувството, че си губя пространство, и в крайна сметка ми опашката се разпада в нищо,

1059
00:59:28,000 --> 00:59:31,000
така бихме могли просто да има хора, обгръщащ,

1060
00:59:31,000 --> 00:59:35,000
и ние наистина можеше да мисли за този масив като някакъв вид на кръгова структура,

1061
00:59:35,000 --> 00:59:38,000
но ние използваме това, което оператор в C, за да се направи този вид обвивка?

1062
00:59:38,000 --> 00:59:40,000
[Чува студент отговор] >> оператор модул.

1063
00:59:40,000 --> 00:59:43,000
Това би било малко досадно да мислят как да направят обгръщащ,

1064
00:59:43,000 --> 00:59:46,000
но можем да го направим, и ние може да започне поставянето на хората в това, което се използва за да бъде предната част на линията,

1065
00:59:46,000 --> 00:59:52,000
но ние просто си спомнят с променлива тази глава, който всъщност е действителното главата на линията.

1066
00:59:52,000 --> 00:59:57,000
Какво ще стане, ако вместо това, в крайна сметка, нашата цел обаче,

1067
00:59:57,000 --> 01:00:00,000
да погледнеш номера, както направихме тук на сцената с Анита,

1068
01:00:00,000 --> 01:00:02,000
но ние наистина искаме най-доброто от всички тези светове?

1069
01:00:02,000 --> 01:00:05,000
Искаме повече изтънченост от масив позволява

1070
01:00:05,000 --> 01:00:09,000
, защото искаме способността да нарастват динамично, структурата на данните.

1071
01:00:09,000 --> 01:00:12,000
Но ние не искаме да се налага да прибягват към нещо, което ние посочихме

1072
01:00:12,000 --> 01:00:15,000
в първата лекция не е оптимален алгоритъм,

1073
01:00:15,000 --> 01:00:17,000
на линейно търсене.

1074
01:00:17,000 --> 01:00:21,000
Оказва се, че в действителност, можете да се постигне

1075
01:00:21,000 --> 01:00:24,000
или поне близо до константно време, с което някой като Анита,

1076
01:00:24,000 --> 01:00:27,000
ако тя конфигурира структурата на данните не е свързан списък,

1077
01:00:27,000 --> 01:00:30,000
да не се комин, за да не бъде на опашка, може в действителност,

1078
01:00:30,000 --> 01:00:33,000
излезе с данни, структура, която позволява да гледа на нещата,

1079
01:00:33,000 --> 01:00:37,000
дори думи, а не само номера, в това, което ще се обадя константно време.

1080
01:00:37,000 --> 01:00:40,000
>> И в действителност, гледайки напред, един от psets в този клас е почти винаги

1081
01:00:40,000 --> 01:00:43,000
за изпълнение на проверка на правописа, с което

1082
01:00:43,000 --> 01:00:46,000
ние ви даваме отново около 150 000 английски думи и целта е да се

1083
01:00:46,000 --> 01:00:51,000
зареди в паметта и бързо да бъде в състояние да отговори на въпросите на формуляра

1084
01:00:51,000 --> 01:00:54,000
е тази дума написани правилно?

1085
01:00:54,000 --> 01:00:58,000
И това наистина ще суче, ако сте имали, за да превъртите през всички 150 000 думи, за да се отговори на този.

1086
01:00:58,000 --> 01:01:02,000
Но, в действителност, ще видим, че можем да го направим в много, много бърз време.

1087
01:01:02,000 --> 01:01:06,000
И това ще включва изпълнението на нещо, наречено хеш таблица,

1088
01:01:06,000 --> 01:01:09,000
и въпреки, че на пръв поглед това нещо, наречено хеш таблица ще

1089
01:01:09,000 --> 01:01:12,000
нека постигане на тези супер бързи времена за реакция,

1090
01:01:12,000 --> 01:01:18,000
се оказва, че действително има проблем.

1091
01:01:18,000 --> 01:01:23,000
Когато дойде време за изпълнение на това нещо, наречено - отново, аз го правя отново.

1092
01:01:23,000 --> 01:01:25,000
Аз съм само един тук.

1093
01:01:25,000 --> 01:01:28,000
Когато дойде време за изпълнение на това нещо, наречено хеш таблица,

1094
01:01:28,000 --> 01:01:30,000
ние ще трябва да вземе решение.

1095
01:01:30,000 --> 01:01:32,000
Колко голям трябва това нещо всъщност?

1096
01:01:32,000 --> 01:01:36,000
И когато започнем вмъкване на номера в тази хеш таблица,

1097
01:01:36,000 --> 01:01:38,000
как ще да ги съхранява по такъв начин,

1098
01:01:38,000 --> 01:01:42,000
, че можем да ги получите обратно толкова бързо, колкото ги има в?

1099
01:01:42,000 --> 01:01:45,000
Но ще видим след дълго, че този въпрос

1100
01:01:45,000 --> 01:01:48,000
когато настана рожденият ден на всички в класа ще бъде доста уместен.

1101
01:01:48,000 --> 01:01:51,000
Оказва се, че в тази зала, имаме няколко души,

1102
01:01:51,000 --> 01:01:56,000
така че шансовете, че двама от нас имат същия рожден ден е вероятно доста висока.

1103
01:01:56,000 --> 01:01:58,000
Какво става, ако имаше само 40 от нас в тази стая?

1104
01:01:58,000 --> 01:02:02,000
Какви са шансовете на двама души, които имат същия рожден ден?

1105
01:02:02,000 --> 01:02:04,000
[Студенти] Над 50%.

1106
01:02:04,000 --> 01:02:06,000
Да, над 50%. Всъщност, аз дори донесе диаграма.

1107
01:02:06,000 --> 01:02:08,000
Оказва се, че и това е наистина само една закрита прожекция

1108
01:02:08,000 --> 01:02:12,000
ако има само 58 от нас в тази зала, вероятността от две от нас

1109
01:02:12,000 --> 01:02:16,000
със същия рожден ден е изключително високо, почти 100%,

1110
01:02:16,000 --> 01:02:20,000
и че ще предизвика цял куп боли за нас в сряда.

1111
01:02:20,000 --> 01:02:24,000
>> С това каза, нека да отложи тук. Ще се видим в сряда.

1112
01:02:24,000 --> 01:02:28,000
[Аплодисменти]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]