1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Седмица 6 Продължава]

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

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

4
00:00:08,720 --> 00:00:12,970
Това е CS50 и това е края на седмица 6.

5
00:00:12,970 --> 00:00:17,970
Така CS50x, един от първите курсове в Харвард, участващи в инициативата EDX

6
00:00:17,970 --> 00:00:20,590
наистина дебютира миналия понеделник.

7
00:00:20,590 --> 00:00:23,460
Ако искате да получите един поглед на това, което другите в Интернет

8
00:00:23,460 --> 00:00:27,180
сега след заедно с, можете да се отправите на x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Това ще ви пренасочи към съответното място на edx.org

10
00:00:30,350 --> 00:00:34,160
което е, когато този и други курсове от Масачузетския технологичен институт и Бъркли сега живеят.

11
00:00:34,160 --> 00:00:38,140
Ще трябва да се запишете за една сметка, ще откриете, че материалът е до голяма степен същото

12
00:00:38,140 --> 00:00:42,170
както сте имали този семестър, макар и забавени няколко седмици, като вземем всичко готово.

13
00:00:42,170 --> 00:00:46,930
Но това, което студентите в CS50x Сега ще видите, е интерфейс, доста подобна на тази.

14
00:00:46,930 --> 00:00:50,040
Това, например, е Zamyla водещ на репетиция за проблем набор 0.

15
00:00:50,040 --> 00:00:54,230
При влезете в edx.org, CS50x студентът вижда различни неща

16
00:00:54,230 --> 00:00:57,170
бихте очаквали да видите в курс: на лекция за понеделник,

17
00:00:57,170 --> 00:01:01,650
лекция за сряда, различни шорти, проблемът комплекти, сваляне, PDF файлове.

18
00:01:01,650 --> 00:01:04,459
Освен това, както виждате тук, машинен превод

19
00:01:04,459 --> 00:01:08,390
на английски транскрипция на китайски, японски, испански, италиански,

20
00:01:08,390 --> 00:01:12,810
и цял куп други езици, които със сигурност ще бъде несъвършен

21
00:01:12,810 --> 00:01:15,840
, тъй като ние ги оваляйте програмно чрез нещо, наречено API,

22
00:01:15,840 --> 00:01:18,360
или интерфейс за програмиране на приложения от Google

23
00:01:18,360 --> 00:01:21,360
, която ни позволява да конвертирате от английски на други езици.

24
00:01:21,360 --> 00:01:24,100
Но благодарение на прекрасния дух на някои сто плюс доброволци,

25
00:01:24,100 --> 00:01:26,940
случайни хора в Интернет, които са любезно предложи да се включат

26
00:01:26,940 --> 00:01:30,180
в този проект, ние постепенно ще се подобрява качеството на тези преводи

27
00:01:30,180 --> 00:01:35,790
, като хората коригират грешки, които нашите компютри са направили.

28
00:01:35,790 --> 00:01:42,330
>> Така се оказва, че сме имали още няколко студенти показват в понеделник, отколкото първоначално се очакваше.

29
00:01:42,330 --> 00:01:48,980
Всъщност, сега CS50x има 100 000 души, след заедно у дома.

30
00:01:48,980 --> 00:01:54,430
Така че осъзнаваш, че са част от встъпителната класа на този курс по компютърни науки

31
00:01:54,430 --> 00:01:57,370
образование като цяло, по-широко достъпен.

32
00:01:57,370 --> 00:02:00,130
А реалността е сега, с някои от тези масивни онлайн курсове,

33
00:02:00,130 --> 00:02:04,070
всички те започват с тези на много голям брой, както изглежда вече сме направили тук.

34
00:02:04,070 --> 00:02:08,759
Но целта, в крайна сметка, за CS50x е наистина да получите най-много хора до финалната линия, е възможно.

35
00:02:08,759 --> 00:02:12,000
По проект, CS50x ще се предлага от миналия понеделник

36
00:02:12,000 --> 00:02:17,430
по целия път до 15 април, 2013, така че хора, които имат училищни ангажименти другаде,

37
00:02:17,430 --> 00:02:20,990
работата, семейството, други конфликти и други подобни, имат малко по-голяма гъвкавост

38
00:02:20,990 --> 00:02:23,640
с които да се потопите в този курс, който, достатъчно е да се каже,

39
00:02:23,640 --> 00:02:30,540
е доста амбициозно стане само ако в течение на само три месеца по време на обичайния семестър.

40
00:02:30,540 --> 00:02:34,190
Но тези ученици ще бъдат решаването на същите проблеми, смятайки, че едно и също съдържание,

41
00:02:34,190 --> 00:02:36,350
като достъп до същите шорти и други подобни.

42
00:02:36,350 --> 00:02:38,990
Така че осъзнават, че всички ние сме наистина заедно в това.

43
00:02:38,990 --> 00:02:42,360
И една от крайните цели на CS50x не е само за да получите колкото се може повече хора

44
00:02:42,360 --> 00:02:45,720
до финалната линия и да им даде тази нова разбиране на компютърните науки

45
00:02:45,720 --> 00:02:49,000
и програмиране, но също така и да ги имат този споделен опит.

46
00:02:49,000 --> 00:02:52,010
Една от определящите характеристики на 50 на територията на колежа, ние се надяваме,

47
00:02:52,010 --> 00:02:56,260
е този вид на комуналната опит, за добро или за лошо, а понякога и

48
00:02:56,260 --> 00:02:59,480
но се налага тези хора да се обърнат към наляво и надясно,

49
00:02:59,480 --> 00:03:01,830
и офис часа и hackathon и справедливата.

50
00:03:01,830 --> 00:03:04,560
Това е малко трудно да се направи, че в лице с хора онлайн,

51
00:03:04,560 --> 00:03:10,580
но CS50x ще приключи през април с първата по рода си CS50 Експо

52
00:03:10,580 --> 00:03:13,630
, което ще бъде онлайн адаптиране на нашата идея на панаира

53
00:03:13,630 --> 00:03:18,250
когато тези хиляди студенти ще бъдат поканени да представят 1 - 2-минутно видео,

54
00:03:18,250 --> 00:03:22,480
или Screencast на последния им проект или видео от тях размахваше Здравейте

55
00:03:22,480 --> 00:03:24,490
и говори за проекта си и го demoing,

56
00:03:24,490 --> 00:03:27,610
много прилича вашите предшественици са направили тук на територията на колежа в справедливата

57
00:03:27,610 --> 00:03:31,400
така че до края на семестъра, надеждата е да има глобален изложба

58
00:03:31,400 --> 00:03:37,080
на крайните проекти CS50x студенти, много подобен на този, който ви очаква декември тази година на територията на колежа.

59
00:03:37,080 --> 00:03:39,680
Така повече, че в идните месеци.

60
00:03:39,680 --> 00:03:43,640
>> С 100 000 студенти, обаче, идва нужда от още няколко компетентни.

61
00:03:43,640 --> 00:03:47,590
Като се има предвид, че вие ​​пламнал пътека тук и като CS50

62
00:03:47,590 --> 00:03:51,630
няколко седмици преди освобождаването на този материал хора в EDX,

63
00:03:51,630 --> 00:03:55,330
осъзнаваме, че ще се радва да се включат колкото се може повече от нашите собствени ученици е възможно в тази инициатива,

64
00:03:55,330 --> 00:03:58,720
както по време на семестъра, както и тази зима и идната пролет.

65
00:03:58,720 --> 00:04:01,620
Така че, ако бихте искали да се включат в CS50x,

66
00:04:01,620 --> 00:04:07,450
особено присъединяването на CS50x обсъждане, EDX версия на CS50 Обсъждане

67
00:04:07,450 --> 00:04:10,140
която мнозина от вас са били на територията на колежа, онлайн бюлетин борд,

68
00:04:10,140 --> 00:04:13,040
моля, направете главата към този адрес, нека да знаят кой сте вие,

69
00:04:13,040 --> 00:04:16,450
защото ще се радваме да се изгради екип от студенти и преподаватели, така и факултета

70
00:04:16,450 --> 00:04:19,630
на територията на колежа, които просто играят заедно и да помагат.

71
00:04:19,630 --> 00:04:21,720
И когато те виждат един въпрос, който е запознат с тях,

72
00:04:21,720 --> 00:04:25,320
чуете студент отчитане на някои бъг някъде там в някои страни в Интернет,

73
00:04:25,320 --> 00:04:27,450
и че звъни звънец, защото вие също имаше същият проблем

74
00:04:27,450 --> 00:04:32,620
в г-зала преди известно време, надявам се след това можете да се намеся в разговора и да споделят собствения си опит.

75
00:04:32,620 --> 00:04:37,300
Така че моля не участва, ако искате.

76
00:04:37,300 --> 00:04:39,360
>> Курсове по компютърни науки в Харвард са малко на една традиция,

77
00:04:39,360 --> 00:04:44,730
CS50 сред тях, като някои дрехи, някои дрехи, които можете да носите гордо

78
00:04:44,730 --> 00:04:49,090
в края на семестъра, като каза доста гордо, че сте готови CS50

79
00:04:49,090 --> 00:04:51,830
и взе CS50 и други подобни, и ние винаги се опитваме да се включат студенти

80
00:04:51,830 --> 00:04:54,540
в този процес, доколкото е възможно, чрез което покани,

81
00:04:54,540 --> 00:04:56,900
по това време на семестъра, студентите да представят проекти

82
00:04:56,900 --> 00:04:59,330
използвате Photoshop, или каквото и средство на избор, който искате да използвате

83
00:04:59,330 --> 00:05:02,330
ако сте дизайнер, да представят проекти за тениски и суитчъри

84
00:05:02,330 --> 00:05:06,100
и чадъри, както и малки КЪРПИ за кучета, сега ние имаме и други подобни.

85
00:05:06,100 --> 00:05:09,370
И всичко е след това - победителите всяка година са изложени

86
00:05:09,370 --> 00:05:12,700
на сайта на курса store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Всичко се продава по себестойност там, но там само по себе си работи

88
00:05:15,790 --> 00:05:18,330
и позволява на хората да избират цветове и дизайн, които те харесват.

89
00:05:18,330 --> 00:05:20,420
Така си мислех, ние просто щяхме да споделя някои от дизайни на миналата година

90
00:05:20,420 --> 00:05:25,130
, които са били на уебсайта, освен това тук, което е ежегодна традиция.

91
00:05:25,130 --> 00:05:29,410
"Всеки ден съм Seg Faultn" е един от представените миналата година,

92
00:05:29,410 --> 00:05:32,290
която все още е на разположение за възпитаници.

93
00:05:32,290 --> 00:05:35,820
Имахме ", CS50, създадена 1989 година."

94
00:05:35,820 --> 00:05:39,010
Един от нашите Bowdens, Роб, беше много популярна през миналата година.

95
00:05:39,010 --> 00:05:43,480
"Team Боудън" е роден, този дизайн е представена, сред най-продаваните.

96
00:05:43,480 --> 00:05:49,040
Както и този тук. Bowden Fever "Много хора според продажбите трупи.

97
00:05:49,040 --> 00:05:52,650
Осъзнайте, че вече може да бъде вашия проект там, в интернет.

98
00:05:52,650 --> 00:05:57,510
Повече подробности по този въпрос в следващия проблем, да дойде.

99
00:05:57,510 --> 00:06:00,330
>> Още един инструмент, сте имали някои експозиция, и да се надяваме сега

100
00:06:00,330 --> 00:06:02,350
някои практически опит с GDB,

101
00:06:02,350 --> 00:06:04,570
, което е, разбира се, дебъгер и ви позволява да манипулирате

102
00:06:04,570 --> 00:06:09,500
програмата си на доста ниско ниво, без да прави какви неща?

103
00:06:09,500 --> 00:06:13,030
Какво GDB ви позволи да направите?

104
00:06:13,030 --> 00:06:15,030
Да? Дай ми нещо. [Student отговор, неразбираем]

105
00:06:15,030 --> 00:06:18,120
Добре. Стъпка на функциите си, така че не само трябва да въведете работи

106
00:06:18,120 --> 00:06:22,310
и имат програма за удар през своята цялост, извеждаща неща на стандартния изход.

107
00:06:22,310 --> 00:06:25,190
, По-скоро може да се намеси чрез нея линия по ред, или да пишете следващата

108
00:06:25,190 --> 00:06:30,300
ред по ред по ред или стъпка, за да се потопите в една функция, обикновено този, който пише.

109
00:06:30,300 --> 00:06:35,240
Какво друго GDB ви позволи да направите? Да? [Student отговор, неразбираем]

110
00:06:35,240 --> 00:06:38,100
Печат променливи. Така че, ако искате да направите малко интроспекция, в рамките на програмата си

111
00:06:38,100 --> 00:06:41,500
, без да се налага да прибягват до писмено ФОРМАТ отчети навсякъде,

112
00:06:41,500 --> 00:06:44,600
може просто да отпечатате променлива или да покаже променлива.

113
00:06:44,600 --> 00:06:46,710
Какво друго мога да правя с дебъгер като GDB?

114
00:06:46,710 --> 00:06:49,170
[Student отговор, неразбираем]

115
00:06:49,170 --> 00:06:52,080
Точно така. Можете да задавате точки на прекъсване, може да се каже изпълнение почивка

116
00:06:52,080 --> 00:06:54,020
основната функция или функция на Foo.

117
00:06:54,020 --> 00:06:56,800
Може да се каже изпълнение на прекъсване на линията 123.

118
00:06:56,800 --> 00:06:58,950
И гранични точки са наистина мощна техника

119
00:06:58,950 --> 00:07:01,110
защото, ако имате най-общ смисъл от това, къде ти е проблема

120
00:07:01,110 --> 00:07:05,360
вероятно е, не е нужно да губите време се повишават през цялост на програмата.

121
00:07:05,360 --> 00:07:08,250
Можете същество скочи точно там и след това да започнете да пишете -

122
00:07:08,250 --> 00:07:10,970
засилване през него със стъпка или следващата или подобни.

123
00:07:10,970 --> 00:07:14,340
Но улов с нещо като GDB е, че тя ви помага, човека,

124
00:07:14,340 --> 00:07:16,940
проблемите си и да намерят вашите грешки.

125
00:07:16,940 --> 00:07:19,470
Не е задължително да ги намерите толкова много за вас.

126
00:07:19,470 --> 00:07:23,070
>> Така че ние въведохме друга style50 ден, който е на кратко командния ред инструмент

127
00:07:23,070 --> 00:07:27,500
която се опитва да Stylize кода си малко по-чисто от вас, човек, би могло да се направи.

128
00:07:27,500 --> 00:07:29,530
Но това също е наистина просто естетически нещо.

129
00:07:29,530 --> 00:07:34,110
Но се оказва, че този друг инструмент наречен Valgrind, че е малко по-тайнствена да използвате.

130
00:07:34,110 --> 00:07:36,860
Неговата продукция е отвратително загадъчен на пръв поглед.

131
00:07:36,860 --> 00:07:39,420
Но това е чудесно полезно, особено сега, когато сме част от срока

132
00:07:39,420 --> 00:07:43,080
, където можете да започнете да използвате изчистване и динамично разпределение на паметта.

133
00:07:43,080 --> 00:07:45,420
Нещата могат да тръгнат много, много погрешно бързо.

134
00:07:45,420 --> 00:07:49,320
Защото, ако сте пропуснали да освободите памет, или сочените от някои NULL показалеца,

135
00:07:49,320 --> 00:07:55,770
или сочените от някои боклук показалеца, това, което обикновено е симптом, че резултатите?

136
00:07:55,770 --> 00:07:59,470
Seg вина. И да получите този основен файл на известен брой килобайта или мегабайта

137
00:07:59,470 --> 00:08:02,990
, която представлява състоянието на паметта на вашата програма, когато тя се разби,

138
00:08:02,990 --> 00:08:05,730
но вашата програма в крайна сметка Seg грешки, сегментация вина,

139
00:08:05,730 --> 00:08:08,450
което означава, че нещо лошо се е случило почти винаги са свързани

140
00:08:08,450 --> 00:08:11,750
на паметта, свързана с грешка, която сте направили някъде.

141
00:08:11,750 --> 00:08:14,100
Така Valgrind ви помага да намерите неща като това.

142
00:08:14,100 --> 00:08:17,720
Това е инструмент, който ви тече, като GDB, след като компилирате вашата програма,

143
00:08:17,720 --> 00:08:20,330
но вместо да стартирате програмата директно, вие поемате Valgrind

144
00:08:20,330 --> 00:08:23,960
и преминава към вашата програма, точно както правите с GDB.

145
00:08:23,960 --> 00:08:26,220
Сега, използването, за да получите най-добрия вид на продукцията,

146
00:08:26,220 --> 00:08:30,410
е малко дълго, така че точно там на върха на екрана ще видите Valgrind-V.

147
00:08:30,410 --> 00:08:35,350
"V" почти навсякъде означава многословно, когато използвате програми на Linux компютър.

148
00:08:35,350 --> 00:08:38,770
А това означава, плюе повече данни, отколкото може да по подразбиране.

149
00:08:38,770 --> 00:08:45,510
"- Течове = пълно." Това е просто, че проверка за всички възможни течове на памет,

150
00:08:45,510 --> 00:08:49,430
грешки, които може да са направили. Това също е обща парадигма с Linux програми.

151
00:08:49,430 --> 00:08:52,710
По принцип, ако имате аргумент на командния ред, че е "ключ",

152
00:08:52,710 --> 00:08:55,830
, които е трябвало да промените поведението на програмата, и това е една буква,

153
00:08:55,830 --> 00:09:00,310
е-V, но ако това е включено, само с дизайна на програмиста,

154
00:09:00,310 --> 00:09:05,150
е пълна дума или поредица от думи, аргумент на командния ред започва с -

155
00:09:05,150 --> 00:09:08,190
Това са само човешки конвенции, но ще ги видите все по-често.

156
00:09:08,190 --> 00:09:12,410
И най-накрая, "a.out" е произволно име за програмата в този конкретен пример.

157
00:09:12,410 --> 00:09:14,640
И тук е някои представител изход.

158
00:09:14,640 --> 00:09:22,890
>> Преди да погледнем какво може да означава, нека преминем към фрагмент от кода тук.

159
00:09:22,890 --> 00:09:26,390
И нека ми се премести от пътя, идва скоро,

160
00:09:26,390 --> 00:09:32,120
и нека да погледнем в memory.c, който е този кратък пример тук.

161
00:09:32,120 --> 00:09:36,290
Така че в тази програма, позволете ми да се фокусирам върху функциите и въпроси.

162
00:09:36,290 --> 00:09:39,430
Имаме функция основната, която призовава функция, е,

163
00:09:39,430 --> 00:09:45,590
и после какво се е пристъпя да направя, леко технически английски език?

164
00:09:45,590 --> 00:09:49,760
Какво е пристъпя да направя?

165
00:09:49,760 --> 00:09:53,680
Какво ще кажеш аз ще започне с линия 20, както и местоположението на звездата не е от значение,

166
00:09:53,680 --> 00:09:56,720
но аз просто ще бъдат съвместими тук с последната лекция.

167
00:09:56,720 --> 00:09:59,910
Какво е линия 20, за нас? От лявата страна. Ние ще го съборят допълнително.

168
00:09:59,910 --> 00:10:02,410
Int * X: какво правим?

169
00:10:02,410 --> 00:10:04,940
Добре. Това е обявяване на показалеца, а сега нека да бъдем още по-технически.

170
00:10:04,940 --> 00:10:10,230
Какво означава това, много конкретно, да декларира указател? Някой друг?

171
00:10:10,230 --> 00:10:15,050
Да? [Student отговор, неразбираем] Твърде далеч.

172
00:10:15,050 --> 00:10:17,060
Така че четете на дясната страна на знака за равенство.

173
00:10:17,060 --> 00:10:20,290
Нека се съсредоточим само отляво, само на Int * х.

174
00:10:20,290 --> 00:10:24,700
Това означава "обяви" показалка, но сега нека се гмуркат по-дълбоко към това определение.

175
00:10:24,700 --> 00:10:28,330
Какво значи това конкретно, технически кажеш? Да?

176
00:10:28,330 --> 00:10:31,940
[Student отговор, неразбираем]

177
00:10:31,940 --> 00:10:35,090
Добре. Да запишете един адрес в паметта.

178
00:10:35,090 --> 00:10:40,680
Добре. И нека вземем тази една стъпка напред, то е за обявяване на променлива, х, това е 32 бита.

179
00:10:40,680 --> 00:10:44,440
И аз знам, че е 32 бита, защото -

180
00:10:44,440 --> 00:10:47,390
Това не е, защото това е ПНА, защото това е един показалеца в този случай.

181
00:10:47,390 --> 00:10:49,650
Съвпадение, че това е една и съща с вътр,

182
00:10:49,650 --> 00:10:51,970
но факта, че е звезда означава, че това е указател

183
00:10:51,970 --> 00:10:57,300
и в уреда, с много компютри, но не всички, указатели са 32 бита.

184
00:10:57,300 --> 00:11:01,850
На по-модерен хардуер като най-новите Mac-ове, най-новите персонални компютри, може да имате 64-битови указатели,

185
00:11:01,850 --> 00:11:04,160
но в уреда, тези неща са 32 бита.

186
00:11:04,160 --> 00:11:08,380
Така че ние ще стандартизира за това. По-конкретно, историята продължава, както следва:

187
00:11:08,380 --> 00:11:10,820
Ние "обявяват" показалеца, какво означава това?

188
00:11:10,820 --> 00:11:12,810
Ние се подготвяме да съхранявате адрес от паметта.

189
00:11:12,810 --> 00:11:15,530
Какво означава това?

190
00:11:15,530 --> 00:11:19,810
Ние създаваме променлива, наречена X, който заема 32 бита

191
00:11:19,810 --> 00:11:23,810
, които скоро ще се съхранява адреса на цяло число.

192
00:11:23,810 --> 00:11:26,470
И това е може би почти толкова точно, колкото можем да получим.

193
00:11:26,470 --> 00:11:31,810
Това е добре, движи напред, за да се опрости света и просто да кажа обяви показалеца нарича х.

194
00:11:31,810 --> 00:11:35,380
Обяви показалеца, но осъзнаят и да разберат какво всъщност се случва

195
00:11:35,380 --> 00:11:38,490
дори и само тези няколко знака.

196
00:11:38,490 --> 00:11:42,040
>> Сега, това е почти една малко по-лесно, въпреки че това е по-дълъг израз.

197
00:11:42,040 --> 00:11:48,160
И така, какво е това прави, че сега се откроява: "изчистване (10 * sizeof (INT));" Да?

198
00:11:48,160 --> 00:11:52,350
[Student отговор, неразбираем]

199
00:11:52,350 --> 00:11:58,250
Добре. И аз ще го отведе там. Разпределяне на парче на паметта в продължение на десет числа.

200
00:11:58,250 --> 00:12:02,190
А сега нека се потопите в малко по-дълбоко, то е за разпределяне на парче на паметта в продължение на десет цели числа.

201
00:12:02,190 --> 00:12:05,390
Какво е изчистване след това се връщат?

202
00:12:05,390 --> 00:12:10,390
Адрес на това парче, или, по-конкретно, на адреса на първия байт на това парче.

203
00:12:10,390 --> 00:12:14,080
Как тогава съм аз, програмист, за да знам къде е това парче на паметта краищата?

204
00:12:14,080 --> 00:12:18,340
Знам, че това е в съседство. Изчистване, по дефиниция, ще ви дам свързано парче от паметта.

205
00:12:18,340 --> 00:12:21,240
Без пропуски в него. Вие имате достъп до всеки байт в това парче,

206
00:12:21,240 --> 00:12:26,760
обратно към гръб до гръб, но как мога да знам къде е края на това парче на паметта?

207
00:12:26,760 --> 00:12:28,850
Когато използвате изчистване? [Student отговор, неразбираем] Добре.

208
00:12:28,850 --> 00:12:30,670
Не. Трябва да се помни.

209
00:12:30,670 --> 00:12:35,960
Трябва да се помни, че използва стойност 10, а аз дори не изглежда да са направили, че тук.

210
00:12:35,960 --> 00:12:41,000
Но тежестта е изцяло върху мен. Strlen, за които сме слабо зависима от струни,

211
00:12:41,000 --> 00:12:45,860
работи само, защото на тази конвенция на \ 0

212
00:12:45,860 --> 00:12:48,840
или този специален нулев характер, NUL, в края на низ.

213
00:12:48,840 --> 00:12:51,740
Това не важи само за произволни блокове памет.

214
00:12:51,740 --> 00:12:58,590
Това е до вас. Така линия 20, а след това разпределя парче на паметта

215
00:12:58,590 --> 00:13:02,590
който може да съхранява десет числа, и го съхранява адреса на първия байт

216
00:13:02,590 --> 00:13:05,610
на това парче на паметта в променлива наречена х.

217
00:13:05,610 --> 00:13:11,140
Ergo, който е указател. Така линия 21, за съжаление, е било грешка.

218
00:13:11,140 --> 00:13:16,110
Но първо, какво е да го прави? Той казва магазин на място при 10, индексирани от 0,

219
00:13:16,110 --> 00:13:19,480
на парче памет, наречена X стойност 0.

220
00:13:19,480 --> 00:13:21,510
>> Така че забележите няколко неща ще.

221
00:13:21,510 --> 00:13:25,420
Въпреки че х е указател, припомнят от преди няколко седмици

222
00:13:25,420 --> 00:13:29,440
че все още можете да използвате масив стил нотация скоба площад.

223
00:13:29,440 --> 00:13:36,180
Защото това е всъщност ръка нотация за по-загадъчен изглеждащи показалеца аритметика.

224
00:13:36,180 --> 00:13:40,320
, където ние ще направим нещо като това: х адрес, преместване 10 места,

225
00:13:40,320 --> 00:13:44,550
след това да има какъвто и да е адрес се съхранява на това място.

226
00:13:44,550 --> 00:13:48,090
Но честно казано, това е просто отвратителен, да четат и да получите комфортно.

227
00:13:48,090 --> 00:13:52,900
Така светът обикновено използва квадратните скоби, само защото тя е много повече за човека да се чете.

228
00:13:52,900 --> 00:13:55,140
Но това е, което наистина се случва под предния капак;

229
00:13:55,140 --> 00:13:58,190
х е адрес, а не масив, сам по себе си.

230
00:13:58,190 --> 00:14:02,410
Така че това е съхраняване 0 на място при 10 в х.

231
00:14:02,410 --> 00:14:06,120
Защо това е лошо? Да?

232
00:14:06,120 --> 00:14:17,370
[Student отговор, неразбираем] Точно така.

233
00:14:17,370 --> 00:14:21,100
Ние само разпределят десет цели числа, но ние броим от 0 при програмирането на С,

234
00:14:21,100 --> 00:14:25,690
така че да имате достъп до 0 1 2 3 4 5 6 7 8 9, но не и 10.

235
00:14:25,690 --> 00:14:30,270
Така че или програмата ще сегмента вина или не е така.

236
00:14:30,270 --> 00:14:32,900
Но ние не наистина знаят; това е нещо на nondeterministic поведение.

237
00:14:32,900 --> 00:14:35,600
Това наистина зависи от това дали имаме късмет.

238
00:14:35,600 --> 00:14:40,650
Ако се окаже, че операционната система няма нищо против, ако използвам тази екстра байт,

239
00:14:40,650 --> 00:14:43,360
макар и да не го даде на мен, моята програма не може да се срине.

240
00:14:43,360 --> 00:14:46,780
Това е сурова, това е бъги, но може да не се види, че симптом,

241
00:14:46,780 --> 00:14:48,960
или може да го види само веднъж в последно време.

242
00:14:48,960 --> 00:14:51,230
Но реалността е, че грешката не е в действителност, има.

243
00:14:51,230 --> 00:14:54,320
И това е наистина проблем, ако сте написали програма, която искате да бъде вярна,

244
00:14:54,320 --> 00:14:58,840
, че сте продали на програмата, която хората използват, че всеки от време на време се срива

245
00:14:58,840 --> 00:15:02,450
защото, разбира се, това не е добре. В действителност, ако имате телефон с Android или iPhone

246
00:15:02,450 --> 00:15:05,550
и да изтеглите приложения тези дни, ако някога сте имали един апартамент, просто напуснете,

247
00:15:05,550 --> 00:15:10,040
изведнъж изчезва, това е почти винаги в резултат на някои въпроси, свързани с паметта,

248
00:15:10,040 --> 00:15:12,830
като програмист прецаках и dereferenced указател

249
00:15:12,830 --> 00:15:18,670
, че той или тя не трябва да има, и в резултат на IOS или Android е просто да убие изцяло програмата

250
00:15:18,670 --> 00:15:23,080
отколкото риск неопределено поведение или някакъв вид компромис за сигурност.

251
00:15:23,080 --> 00:15:25,950
>> Има една друга грешка в тази програма освен тази.

252
00:15:25,950 --> 00:15:30,180
Какво друго се издъних в тази програма?

253
00:15:30,180 --> 00:15:32,740
Аз не съм се практикува това, което съм проповядвал. Да?

254
00:15:32,740 --> 00:15:34,760
[Student отговор, неразбираем] Добре.

255
00:15:34,760 --> 00:15:36,880
Не съм освободен паметта. Така правилото сега

256
00:15:36,880 --> 00:15:43,150
трябва да бъде по всяко време ти се обадя изчистване, трябва да се обаждате безплатно, когато сте готови с тази памет.

257
00:15:43,150 --> 00:15:45,610
Сега, когато бих искал да се освободи тази памет?

258
00:15:45,610 --> 00:15:49,780
Вероятно, ако приемем, че тази първа линия е правилно, аз бих искал да го правя тук.

259
00:15:49,780 --> 00:15:55,710
Защото не можех, например, да го направя тук. Защо?

260
00:15:55,710 --> 00:15:57,860
Просто извън обхвата. Така че дори и ние не говорим за указатели,

261
00:15:57,860 --> 00:16:04,830
Това е една седмица два или три въпроса, където х е само в обхвата вътрешността на фигурни скоби, когато е декларирана.

262
00:16:04,830 --> 00:16:11,000
Така че определено не може да го освободи. Единственият ми шанс да го освободи е приблизително след линия 21.

263
00:16:11,000 --> 00:16:15,170
Това е доста проста програма, тя е доста лесно, след като вид увит ума си

264
00:16:15,170 --> 00:16:17,870
около това, което програмата прави, когато грешките са.

265
00:16:17,870 --> 00:16:20,500
А дори и да не го видим в първия, се надяваме, че е малко очевидно сега

266
00:16:20,500 --> 00:16:23,870
, че тези грешки са доста лесно се решава и лесно.

267
00:16:23,870 --> 00:16:28,720
Но когато програмата е повече от 12 реда, 50 линии, 100 линии,

268
00:16:28,720 --> 00:16:31,150
разхождах из вашия код линия по ред, мислейки, то логично,

269
00:16:31,150 --> 00:16:35,110
е възможно, но не е особено забавно да се направи, непрекъснато търси за грешки,

270
00:16:35,110 --> 00:16:38,340
и тя също е трудно да се направи, и това е защо съществува като инструмент Valgrind.

271
00:16:38,340 --> 00:16:40,900
Позволете ми да отида напред и да направите това: нека си отворя терминален прозорец,

272
00:16:40,900 --> 00:16:45,400
и нека не просто стартирате памет, защото паметта изглежда да се оправи.

273
00:16:45,400 --> 00:16:49,180
Аз съм късметлия. Отивате на този допълнителен байт в края на масива

274
00:16:49,180 --> 00:16:51,060
не изглежда да е твърде проблематично.

275
00:16:51,060 --> 00:16:56,370
Но нека, все пак, направи проверка на здрав разум, което просто означава, че за да се провери

276
00:16:56,370 --> 00:16:58,320
дали това всъщност е правилно.

277
00:16:58,320 --> 00:17:04,690
>> Така че нека да направим valgrind-V - изтичане на проверка = пълно,

278
00:17:04,690 --> 00:17:07,520
и след това името на програмата в този случай е паметта не a.out.

279
00:17:07,520 --> 00:17:10,760
Така че нека да вървим напред и да направите това. Хит Enter.

280
00:17:10,760 --> 00:17:14,109
Мили Боже. Това е изход, и това е, което споменах по-рано.

281
00:17:14,109 --> 00:17:17,550
Но, ако се научите да прочетете всички глупости тук,

282
00:17:17,550 --> 00:17:20,760
голямата част от това е просто диагностичен изход, който не е толкова интересен.

283
00:17:20,760 --> 00:17:24,829
Какво си око наистина иска да се търси, е всяко споменаване на грешка или невалиден.

284
00:17:24,829 --> 00:17:26,800
Думи, които предполагат проблеми.

285
00:17:26,800 --> 00:17:29,340
И наистина, нека да видим какво не е наред тук.

286
00:17:29,340 --> 00:17:35,230
Имам резюме от някакъв вид ", в употреба на излизане: 40 байта в 1 блокове"

287
00:17:35,230 --> 00:17:38,750
Аз наистина не съм сигурен какво блок все още, но 40 байта

288
00:17:38,750 --> 00:17:41,260
всъщност се чувства, че мога да разбера, когато това идва от.

289
00:17:41,260 --> 00:17:45,030
40 байта. Защо 40 байта, които се използват при излизане?

290
00:17:45,030 --> 00:17:48,780
И по-специално, ако ние превъртете надолу,

291
00:17:48,780 --> 00:17:54,520
защо съм загубил окончателно 40 байта? Да?

292
00:17:54,520 --> 00:17:59,520
[Student отговор, неразбираем] Perfect. Да, точно така.

293
00:17:59,520 --> 00:18:03,540
Имаше десет числа, и всеки от тях е размер на 4, или 32 бита,

294
00:18:03,540 --> 00:18:08,300
така че съм загубил точно 40 байта, защото, както предложи, не са наречени свободни.

295
00:18:08,300 --> 00:18:13,460
Това е един бъг, а сега нека разгледаме малко по-нататък и да видим до това,

296
00:18:13,460 --> 00:18:16,900
"Невалиден пиша с размер 4". Сега какво е това?

297
00:18:16,900 --> 00:18:21,150
Този адрес се изразява каква база нотация, очевидно?

298
00:18:21,150 --> 00:18:23,640
Това е в шестнадесетичен вид, и всеки път, когато видите номер, започващ с 0x,

299
00:18:23,640 --> 00:18:29,410
това означава, шестнадесетичен, което ние направихме, мисля, раздел pset 0 от въпроси,

300
00:18:29,410 --> 00:18:34,090
което е просто да се направи упражнение за загрявка, Конвертиране на десетични шестнадесетичен двоичен и така нататък.

301
00:18:34,090 --> 00:18:39,220
Шестнадесетичен само от човешката конвенция, обикновено се използва за представяне на указатели

302
00:18:39,220 --> 00:18:41,570
или, по-общо, се занимава. Това е просто една конвенция,

303
00:18:41,570 --> 00:18:45,340
, защото това е малко по-лесно да се чете, това е малко по-компактен от нещо като знак след десетичната

304
00:18:45,340 --> 00:18:47,720
и бинарни е безполезен за повечето хора, които да се използват.

305
00:18:47,720 --> 00:18:50,840
Така че сега, какво означава това? Е, изглежда, че има невалиден запис

306
00:18:50,840 --> 00:18:54,480
на размер 4 по линия 21 на memory.c.

307
00:18:54,480 --> 00:18:59,180
Така че нека да се върнем към 21, и наистина, тук е, че невалиден запис.

308
00:18:59,180 --> 00:19:02,640
Така Valgrind няма да напълно да държи ръката ми и ми кажи какво е поправката,

309
00:19:02,640 --> 00:19:05,520
но това е откриване, че правя невалиден запис.

310
00:19:05,520 --> 00:19:08,800
Аз докосвате 4 байта, че не трябва да бъде, и очевидно това е така, защото,

311
00:19:08,800 --> 00:19:13,960
като посочи, правя [10] вместо [9] максимално

312
00:19:13,960 --> 00:19:16,660
или [0], или нещо по средата.

313
00:19:16,660 --> 00:19:19,690
С Valgrind, реализира всеки път, когато сте написването на програмата

314
00:19:19,690 --> 00:19:24,190
който използва указатели и използва памет и изчистване по-специално,

315
00:19:24,190 --> 00:19:27,080
определено ще получите в навик да работи толкова дълго

316
00:19:27,080 --> 00:19:30,890
, но много лесно се копира и командването на Valgrind

317
00:19:30,890 --> 00:19:32,650
да видим дали има някои грешки в там.

318
00:19:32,650 --> 00:19:34,820
И това ще бъде непоносимо всеки път, когато виждаш изхода,

319
00:19:34,820 --> 00:19:39,430
но просто разбор чрез визуално цялото производство и да видим, ако видите споменава на грешки

320
00:19:39,430 --> 00:19:43,190
или предупреждения или невалидна или изгубени.

321
00:19:43,190 --> 00:19:46,200
Която и да е от думите, които звучат като теб винтови някъде.

322
00:19:46,200 --> 00:19:48,580
Така че осъзнават, че е нов инструмент във вашата инструментариум.

323
00:19:48,580 --> 00:19:51,270
>> Сега в понеделник, имахме цял куп хора идват тук

324
00:19:51,270 --> 00:19:53,150
и представляват идеята на свързан списък.

325
00:19:53,150 --> 00:20:00,970
И ние въведохме свързан списък, като решение за какъв проблем?

326
00:20:00,970 --> 00:20:04,590
Да? [Student отговор, неразбираем] Добре.

327
00:20:04,590 --> 00:20:06,530
Масивите не могат да имат памет, добавени към тях.

328
00:20:06,530 --> 00:20:09,440
Ако разпределят масив с размер 10, това е всичко, което се.

329
00:20:09,440 --> 00:20:13,690
Можете да се обадите функция като презаделяне ако първоначално наречена изчистване,

330
00:20:13,690 --> 00:20:17,580
и които могат да се опитват да растат масива, ако има място към края на

331
00:20:17,580 --> 00:20:21,610
че никой друг не се използва, и ако няма, просто ще ви намери по-голямо парче някъде другаде.

332
00:20:21,610 --> 00:20:25,040
Но тогава ще го копира всички тези байта в нов масив.

333
00:20:25,040 --> 00:20:28,310
Това звучи като много правилно решение.

334
00:20:28,310 --> 00:20:34,790
Защо това е непривлекателна?

335
00:20:34,790 --> 00:20:36,940
Искам да кажа, че работи, хората са решили този проблем.

336
00:20:36,940 --> 00:20:40,710
Защо ние трябва да го решим в понеделник със свързани списъци? Да?

337
00:20:40,710 --> 00:20:44,060
[Отговор Student, неразбираем] може да отнеме дълго време.

338
00:20:44,060 --> 00:20:49,260
В действителност, всеки път, когато се обаждате изчистване или презаделяне или calloc, което е още една,

339
00:20:49,260 --> 00:20:52,470
всеки път, когато програмата се говори за операционната система,

340
00:20:52,470 --> 00:20:54,310
сте склонни да се забави програмата.

341
00:20:54,310 --> 00:20:57,470
И ако правиш тези неща в цикли, сте наистина забавят нещата.

342
00:20:57,470 --> 00:21:00,740
Ти няма да забележи този за най-простите на "Hello World" програми от типа,

343
00:21:00,740 --> 00:21:04,300
но в много по-големи програми, задаване на операционната система отново и отново за паметта

344
00:21:04,300 --> 00:21:07,520
или да го върнат отново и отново не е склонна да бъде нещо добро.

345
00:21:07,520 --> 00:21:11,210
Плюс това, тя е просто вид интелектуално - това е пълна загуба на време.

346
00:21:11,210 --> 00:21:16,490
Защо да отделят все повече и повече памет, всичко за копиране на риска в нов масив,

347
00:21:16,490 --> 00:21:21,980
ако имате алтернатива, която ви позволява да разпределят само толкова памет, колкото действително се нуждаят?

348
00:21:21,980 --> 00:21:24,130
Така че има плюсове и минуси тук.

349
00:21:24,130 --> 00:21:26,730
Един от плюсовете е, че имаме динамика.

350
00:21:26,730 --> 00:21:29,100
Не значение къде парчета на паметта, които са свободни,

351
00:21:29,100 --> 00:21:32,070
Мога само да сортирате за създаването на тези галета чрез указатели

352
00:21:32,070 --> 00:21:34,470
низ цялото ми свързан списък.

353
00:21:34,470 --> 00:21:36,470
Но аз плащат най-малко една цена.

354
00:21:36,470 --> 00:21:40,060
>> Какво трябва да се даде при получаването на свързани списъци?

355
00:21:40,060 --> 00:21:42,470
Да? [Student отговор, неразбираем] Добре.

356
00:21:42,470 --> 00:21:45,650
Имате нужда от повече памет. Сега имам нужда от пространство за тези насоки,

357
00:21:45,650 --> 00:21:47,900
и в случай на този супер прост свързан списък

358
00:21:47,900 --> 00:21:51,410
че само се опитва да съхранява числа, които са 4 байта, продължават да твърдят,

359
00:21:51,410 --> 00:21:54,240
добре, показалеца е 4 байта, така че сега съм буквално се удвои

360
00:21:54,240 --> 00:21:57,290
размера на паметта, трябва само да се съхранява този списък.

361
00:21:57,290 --> 00:21:59,680
Но отново, това е постоянен компромис по компютърни науки

362
00:21:59,680 --> 00:22:03,440
между времето и пространството и развитие, усилия и други ресурси.

363
00:22:03,440 --> 00:22:06,630
Какво е друг недостатък на използването на свързан списък? Да?

364
00:22:06,630 --> 00:22:10,150
[Student отговор, неразбираем]

365
00:22:10,150 --> 00:22:12,600
Добре. Не е толкова лесно за достъп. Вече не можем да ливъридж

366
00:22:12,600 --> 00:22:15,530
седмица 0 принципи като разделяй и владей.

367
00:22:15,530 --> 00:22:18,220
И по-конкретно, двоично търсене. Защото, въпреки че ние, хората,

368
00:22:18,220 --> 00:22:20,400
могат да видят около средата на този списък е,

369
00:22:20,400 --> 00:22:25,840
компютъра само се знае, че този свързан списък започва на адрес нарича първата.

370
00:22:25,840 --> 00:22:28,250
И това е 0x123 или нещо подобно.

371
00:22:28,250 --> 00:22:30,990
И единственият начин програмата може да намери средата елемент

372
00:22:30,990 --> 00:22:33,350
е действително да търсим в целия списък.

373
00:22:33,350 --> 00:22:35,500
И дори тогава, той буквално трябва да търсим в целия списък, защото

374
00:22:35,500 --> 00:22:38,950
дори и след като достигне средата елемент след указатели,

375
00:22:38,950 --> 00:22:42,380
, програмата, нямате представа колко е дълъг този списък е, потенциално

376
00:22:42,380 --> 00:22:45,250
докато не удари края на това, и как знаеш програмно

377
00:22:45,250 --> 00:22:48,600
че сте в края на свързан списък?

378
00:22:48,600 --> 00:22:51,120
Има специален NULL показалеца, така че отново конвенция.

379
00:22:51,120 --> 00:22:53,870
Вместо да използвате този указател, ние определено не искам тя да бъде някаква стойност боклук

380
00:22:53,870 --> 00:22:57,750
сочи етап някъде, ние искаме тя да бъде страна, NULL,

381
00:22:57,750 --> 00:23:01,530
, така че ние имаме това крайната точка в този структурата на данните, така че ние знаем къде свършва.

382
00:23:01,530 --> 00:23:03,410
>> Какво ще стане, ако искаме да манипулира това?

383
00:23:03,410 --> 00:23:05,980
Ние направихме-голямата част от тази визуално, и с хората,

384
00:23:05,980 --> 00:23:07,630
но какво ще стане, ако искаме да направим на вмъкване?

385
00:23:07,630 --> 00:23:12,360
Така първоначалния списък беше 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Какво ще стане ако след това исках да изчистване пространство за номер 55, възел за

387
00:23:16,730 --> 00:23:20,730
и след това искаме да вмъкнем 55 в списъка, точно както направихме в понеделник?

388
00:23:20,730 --> 00:23:23,690
Как да постигнем това? Е, Анита дойде и тя ходеше по същество списък.

389
00:23:23,690 --> 00:23:27,500
Тя започна в първия елемент, а след това на следващото, следващото, следващото, следващото, следващото.

390
00:23:27,500 --> 00:23:29,500
Накрая се удари в лявата целия път надолу

391
00:23:29,500 --> 00:23:34,480
и осъзнах, о, това е NULL. Така че това, което показалеца манипулация трябва да се направи?

392
00:23:34,480 --> 00:23:37,980
Човек, който е на края, номер 34, е необходимо лявата си ръка вдигна

393
00:23:37,980 --> 00:23:46,220
да се отбележи в 55, 55 нужда от лявата им ръка сочи надолу, за да бъде новата NULL терминатор. Готово.

394
00:23:46,220 --> 00:23:49,540
Доста лесно да вмъкнете 55 в сортиран списък.

395
00:23:49,540 --> 00:23:51,800
И как това може да изглежда?

396
00:23:51,800 --> 00:23:55,690
>> Нека вървим напред и да се отворят някои например код.

397
00:23:55,690 --> 00:23:58,120
Ще отворя Gedit и нека се отворят два файла първото.

398
00:23:58,120 --> 00:24:02,050
Един от тях е list1.h, и нека само да напомня, че това е парче код

399
00:24:02,050 --> 00:24:04,920
че сме свикнали да представлява възел.

400
00:24:04,920 --> 00:24:13,040
Възел има както едно цяло число, наречено н и указател следва, че само точки към следващото нещо в списъка.

401
00:24:13,040 --> 00:24:15,450
Това вече е в файл з. Защо?

402
00:24:15,450 --> 00:24:19,090
Тази конвенция, и не сме се възползвали от тази огромна себе си сума,

403
00:24:19,090 --> 00:24:22,220
но човек, който пише ФОРМАТ и други функции

404
00:24:22,220 --> 00:24:27,150
даде като дар за света на тези функции чрез написването на файл, наречен stdio.h.

405
00:24:27,150 --> 00:24:30,950
И тогава там е string.h, и след това има map.h, и има всички тези ч файлове

406
00:24:30,950 --> 00:24:34,410
, че може да са видели или използвани по време на срока, написани от други хора.

407
00:24:34,410 --> 00:24:38,470
Обикновено в тези з файлове са единствените неща, като typedefs

408
00:24:38,470 --> 00:24:42,310
или декларации на потребителски типове или декларации на константи.

409
00:24:42,310 --> 00:24:47,890
Не слагайте реализации функции в заглавните файлове.

410
00:24:47,890 --> 00:24:50,570
, Вместо, само прототипи.

411
00:24:50,570 --> 00:24:53,050
Неща, които искате да споделите със света, това, което те имат нужда

412
00:24:53,050 --> 00:24:55,640
За да компилирате кода си. Така че просто трябва да влязат в този навик,

413
00:24:55,640 --> 00:24:59,110
ние решихме да направим едно и също нещо. Там не е много в list1.h,

414
00:24:59,110 --> 00:25:02,070
но ние сме поставени нещо, което може да представлява интерес за хората в света

415
00:25:02,070 --> 00:25:05,030
които искат да използват нашата свързан изпълнението списък.

416
00:25:05,030 --> 00:25:08,040
Сега в list1.c, аз няма да мине през цялото това нещо

417
00:25:08,040 --> 00:25:11,390
защото това е малко дълго, тази програма, но нека го изпълним реална бързо в командния ред.

418
00:25:11,390 --> 00:25:15,720
Нека ми съставят list1, нека след това пуснете list1, и това, което ще видите е

419
00:25:15,720 --> 00:25:18,070
сме симулирани просто малка програма тук

420
00:25:18,070 --> 00:25:20,990
че няма да ми позволи да добавяте и премахвате номера на списък.

421
00:25:20,990 --> 00:25:24,310
Така че нека да вървим напред и Тип 3 за 3 опция от менюто.

422
00:25:24,310 --> 00:25:27,880
Искам да въведете номера - нека да направим първото число, което е 9,

423
00:25:27,880 --> 00:25:30,550
и сега съм казал списъка сега е 9.

424
00:25:30,550 --> 00:25:33,760
Нека вървим напред и да направя друг вмъкване, така че удари опция от менюто 3.

425
00:25:33,760 --> 00:25:36,760
Какъв брой искам да вмъкнете? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. И аз ще направя само още един.

427
00:25:39,220 --> 00:25:41,720
Позволете ми да въведете номера 22.

428
00:25:41,720 --> 00:25:45,850
Така че ние имаме начало на свързан списък, който имахме в слайд форма преди малко.

429
00:25:45,850 --> 00:25:48,740
Как става това вмъкване всъщност се случва?

430
00:25:48,740 --> 00:25:52,000
В действителност, 22 вече е в края на списъка.

431
00:25:52,000 --> 00:25:55,050
Така че историята, която разказа на сцената в понеделник и обобщи точно сега

432
00:25:55,050 --> 00:25:57,460
трябва действително да се случва в кода.

433
00:25:57,460 --> 00:25:59,700
Нека да разгледаме. Нека превъртете надолу в този файл.

434
00:25:59,700 --> 00:26:01,720
Ние ще замазват някои от функциите,

435
00:26:01,720 --> 00:26:05,630
но ние ще отидем да се каже, добавя функцията.

436
00:26:05,630 --> 00:26:11,720
>> Нека видим как можем отида за поставяне на нов възел в тази свързан списък.

437
00:26:11,720 --> 00:26:14,550
Когато се обявява списъка? Ами, нека да превъртите целия път до върха,

438
00:26:14,550 --> 00:26:19,970
и забележите, че ми свързан списък по същество е обявен като един указател, който първоначално е NULL.

439
00:26:19,970 --> 00:26:23,180
Така че аз съм с глобална променлива, която в общи линии сме проповядвал срещу

440
00:26:23,180 --> 00:26:25,280
защото го прави кода си малко разхвърлян да се поддържа,

441
00:26:25,280 --> 00:26:29,080
това е вид мързеливи, обикновено, но това не е мързелив и не е наред и не е зле

442
00:26:29,080 --> 00:26:33,660
ако единствената цел на програмата в живота е да се симулира един свързан списък.

443
00:26:33,660 --> 00:26:35,460
Което е точно това, което правим.

444
00:26:35,460 --> 00:26:39,100
Така че вместо да декларира това в основни и след това трябва да го предаде на всяка функция

445
00:26:39,100 --> 00:26:42,640
съм писал в тази програма, вместо да осъзнае, о, нека просто да я направите глобална

446
00:26:42,640 --> 00:26:47,060
защото целта на тази програма е да се демонстрира един и само един свързан списък.

447
00:26:47,060 --> 00:26:50,700
Така, че се чувства добре. Тук са моите прототипи, и ние няма да мине през всички тези,

448
00:26:50,700 --> 00:26:55,800
но аз написах функцията за изтриване, функция за търсене, добавя функция, както и функция, траверса.

449
00:26:55,800 --> 00:26:59,080
Но нека сега се връщаме надолу Вмъкване на функция

450
00:26:59,080 --> 00:27:01,490
и да видим как това работи тук.

451
00:27:01,490 --> 00:27:09,940
Вмъкни е на линия - да го направим.

452
00:27:09,940 --> 00:27:12,850
Поставете. Така че не предприемат никакви аргументи, защото отиваме да попитам

453
00:27:12,850 --> 00:27:15,930
потребителя вътрешността на тази функция за броя искат да вмъкнете.

454
00:27:15,930 --> 00:27:19,410
Но първо, ние подготвяме да им даде някои пространство.

455
00:27:19,410 --> 00:27:22,050
Това е нещо като копиране и поставяне от друг пример.

456
00:27:22,050 --> 00:27:25,110
В този случай, ние разпределяне на вътр, този път сме разпределяне на възел.

457
00:27:25,110 --> 00:27:27,910
Аз наистина не помня колко байта възел, но това е добре.

458
00:27:27,910 --> 00:27:30,460
Sizeof мога да разбера, че за мен.

459
00:27:30,460 --> 00:27:33,340
И защо съм проверка за NULL в линия 120?

460
00:27:33,340 --> 00:27:37,530
Какво може да се обърка в съответствие 119? Да?

461
00:27:37,530 --> 00:27:40,530
[Student отговор, неразбираем]

462
00:27:40,530 --> 00:27:43,440
Добре. Просто може да е случаят, че съм поискал прекалено много памет

463
00:27:43,440 --> 00:27:47,020
или нещо не е наред и операционната система не разполага с достатъчно байта да ми даде,

464
00:27:47,020 --> 00:27:50,640
така че сигнали, тъй като много от връщане NULL, и ако не се прави проверка за това

465
00:27:50,640 --> 00:27:54,710
и аз просто сляпо продължи да използвате адреса върна, тя може да бъде NULL.

466
00:27:54,710 --> 00:27:58,400
Тя може да бъде някаква неизвестна стойност, не е нещо добро, освен ако I -

467
00:27:58,400 --> 00:28:00,590
всъщност няма да е неизвестна стойност. Тя може да бъде NULL, така че аз не искам

468
00:28:00,590 --> 00:28:02,550
да злоупотребяват с нея и рискуват dereferencing.

469
00:28:02,550 --> 00:28:07,410
Ако това се случи, аз просто се върне и ние ще се преструвам, като аз не се върна на паметта на всички.

470
00:28:07,410 --> 00:28:12,270
>> В противен случай, аз съобщите на потребителя, да ми даде номер, за да вмъкнете, аз ви призовавам нашия стар приятел GetInt,

471
00:28:12,270 --> 00:28:15,530
и след това е новия синтаксис ние въведохме в понеделник.

472
00:28:15,530 --> 00:28:20,320
"Newptr-> N" означава адреса, който бяха дадени от изчистване

473
00:28:20,320 --> 00:28:23,490
която представлява първия байт на нов обект възел,

474
00:28:23,490 --> 00:28:26,860
и след това да отиде на полето, наречено н.

475
00:28:26,860 --> 00:28:35,270
Малко любопитни факти въпрос: Това е еквивалентно на това, което по-загадъчен линия на код?

476
00:28:35,270 --> 00:28:38,110
Как иначе може да съм написал това? Искате ли да хладно оръжие?

477
00:28:38,110 --> 00:28:41,480
[Student отговор, неразбираем]

478
00:28:41,480 --> 00:28:44,870
Добре. Използване на N, но това не е толкова проста, тъй като това.

479
00:28:44,870 --> 00:28:47,090
Какво първо трябва да направя? [Student отговор, неразбираем]

480
00:28:47,090 --> 00:28:52,730
Добре. Имам нужда от да направя * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Така че това е, че новата показалеца очевидно адрес. Защо?

482
00:28:55,610 --> 00:28:59,520
Тъй като това бе върнат от изчистване. * Newptr каза: "отидем там"

483
00:28:59,520 --> 00:29:02,970
а след това веднъж сте там, а след това можете да използвате по-познато. н,

484
00:29:02,970 --> 00:29:05,730
но това просто изглежда малко грозно, особено ако ние, хората, ще

485
00:29:05,730 --> 00:29:10,360
изготвя указатели със стрелки през цялото време, в света има стандартизирани в тази стрелка нотация,

486
00:29:10,360 --> 00:29:12,320
което прави точно същото нещо.

487
00:29:12,320 --> 00:29:16,070
Така че можете да използвате само -> нотация, когато нещо в ляво е показалеца.

488
00:29:16,070 --> 00:29:18,790
В противен случай, ако това е действително структура. Н.

489
00:29:18,790 --> 00:29:25,800
И после това: Защо се инициализира newptr-> следващия NULL?

490
00:29:25,800 --> 00:29:28,610
Ние не искаме висящи лявата ръка разстояние от края на сцената.

491
00:29:28,610 --> 00:29:31,630
Ние искаме да го сочи право надолу, което означава края на този списък

492
00:29:31,630 --> 00:29:34,980
би могло да бъде в този възел, така че по-добре да се уверите, че е NULL.

493
00:29:34,980 --> 00:29:38,460
И като цяло, инициализиране на променливи или членове на вашите данни и structs

494
00:29:38,460 --> 00:29:40,470
нещо е просто добра практика.

495
00:29:40,470 --> 00:29:45,170
Просто отдаване под наем боклук съществуват и продължават да съществуват като цяло попадне в беда

496
00:29:45,170 --> 00:29:48,650
ако сте пропуснали да направим нещо по-късно.

497
00:29:48,650 --> 00:29:51,590
>> Ето няколко случая. Това отново е Вмъкване на функция,

498
00:29:51,590 --> 00:29:54,930
и първото нещо, което проверява за е, ако променлива наречена първата,

499
00:29:54,930 --> 00:29:58,240
, че глобалната променлива е NULL, това означава, че там не е свързан списък.

500
00:29:58,240 --> 00:30:02,460
Не сме написали номера, така че това е тривиално да поставите този номер

501
00:30:02,460 --> 00:30:05,240
в списъка, защото тя просто принадлежи в началото на списъка.

502
00:30:05,240 --> 00:30:08,100
Така че това беше, когато Анита е просто стои тук сам, преструвайки се, че

503
00:30:08,100 --> 00:30:11,390
никой друг не е тук на сцената, докато не разпределят възел,

504
00:30:11,390 --> 00:30:13,940
тогава тя може да вдигне ръка, за първи път,

505
00:30:13,940 --> 00:30:17,420
ако всички останали излезе на сцената след нея в понеделник.

506
00:30:17,420 --> 00:30:22,900
Сега тук, това е малко по проверка, където аз трябва да кажа, ако стойността на нов възел на н

507
00:30:22,900 --> 00:30:27,370
<стойността на N в първия възел,

508
00:30:27,370 --> 00:30:29,930
това означава, че е свързан списък, който е започнал.

509
00:30:29,930 --> 00:30:32,330
Има най-малко един възел в списъка, но този нов човек

510
00:30:32,330 --> 00:30:37,230
принадлежи преди това, така че ние трябва да се движат нещата около.

511
00:30:37,230 --> 00:30:43,450
С други думи, ако списъкът е започнал само с, да речем,

512
00:30:43,450 --> 00:30:48,100
само номер 17, това е - всъщност, ние можем да направим това по-ясно.

513
00:30:48,100 --> 00:30:56,010
Ако започнем нашата история с показалеца нарича първият,

514
00:30:56,010 --> 00:30:59,870
и първоначално е NULL, и въведете номера 9,

515
00:30:59,870 --> 00:31:02,510
номер 9 ясно принадлежи в началото на списъка.

516
00:31:02,510 --> 00:31:07,400
Така че нека се престорим, че ние просто malloced адреса или номера 9 и го сложи тук.

517
00:31:07,400 --> 00:31:13,170
Ако първото е 9 по подразбиране, първият сценарий, ние обсъдихме тук просто означава, точка нека този човек,

518
00:31:13,170 --> 00:31:15,790
оставите това NULL, сега имаме номер 9.

519
00:31:15,790 --> 00:31:18,280
Следващият брой искаме да вмъкнем е 17.

520
00:31:18,280 --> 00:31:22,420
17 принадлежи тук, така че ние ще трябва да се направят някои логично засилване през това.

521
00:31:22,420 --> 00:31:26,060
Така че нека вместо това, преди да направим това, нека се престорим, че искаме да въведете номера 8.

522
00:31:26,060 --> 00:31:28,650
>> Така че просто за удобство, аз отивам да изготвят тук.

523
00:31:28,650 --> 00:31:30,760
Но помнете, изчистване може да го сложи най-навсякъде.

524
00:31:30,760 --> 00:31:33,460
Но заради чертежа, аз ще го слагам тук.

525
00:31:33,460 --> 00:31:38,440
Така че се преструвам, че току-що сте разпределени възел за номер 8, това е NULL по подразбиране.

526
00:31:38,440 --> 00:31:42,800
И сега какво трябва да се случи? Няколко неща.

527
00:31:42,800 --> 00:31:47,090
Ние направихме тази грешка на сцената в понеделник, когато сме актуализирали указател така,

528
00:31:47,090 --> 00:31:51,890
тогава това, и след това твърдеше - сираци всеки друг на сцената.

529
00:31:51,890 --> 00:31:54,350
Защото ти Не можеш - от порядъка на дейностите тук е важно,

530
00:31:54,350 --> 00:31:58,760
защото сега сме загубили този възел 9, който е просто на плаващи в пространството.

531
00:31:58,760 --> 00:32:01,150
Така че това не е правилният подход в понеделник.

532
00:32:01,150 --> 00:32:03,330
Ние първо трябва да се направи нещо друго.

533
00:32:03,330 --> 00:32:06,280
Състоянието на света изглежда така. Първоначално 8 е бил разпределен.

534
00:32:06,280 --> 00:32:10,550
Какво ще бъде по-добър начин за вмъкване 8?

535
00:32:10,550 --> 00:32:14,720
Вместо първото актуализиране на този указател се актуализира този тук.

536
00:32:14,720 --> 00:32:17,720
Така че ние се нуждаят от ред на кода, който ще се обърне тази NULL характер

537
00:32:17,720 --> 00:32:22,020
в истински указател, който сочи възел 9,

538
00:32:22,020 --> 00:32:27,970
и след това можем да безопасно да промените първата да посочи този тук.

539
00:32:27,970 --> 00:32:31,330
Сега имаме списък, свързан списък, от два елемента.

540
00:32:31,330 --> 00:32:33,580
И какво означава това всъщност изглежда като тук?

541
00:32:33,580 --> 00:32:36,900
Ако се вгледаме в кода, обърнете внимание, че съм направил точно това.

542
00:32:36,900 --> 00:32:41,970
Казах newptr, и в тази история, newptr сочеше този човек.

543
00:32:41,970 --> 00:32:45,520
>> Така че нека да се направи още едно нещо, а аз трябваше да остави малко повече място за това.

544
00:32:45,520 --> 00:32:48,540
Така че прости малка рисунка.

545
00:32:48,540 --> 00:32:52,140
Този човек се нарича newptr.

546
00:32:52,140 --> 00:32:57,940
Това е променлива, ние декларирахме няколко реда по-рано, в съответствие - малко над 25.

547
00:32:57,940 --> 00:33:03,430
И сочи към 8. Така че, когато казвам newptr-> следващия, това означава, че отидете на структурата

548
00:33:03,430 --> 00:33:07,910
, което е насочено към от newptr, така че ние сме тук, отидете там.

549
00:33:07,910 --> 00:33:13,990
Тогава стрелката казва получите следващото поле, и след това = казва сложи каква стойност има?

550
00:33:13,990 --> 00:33:17,280
Стойност, която е в първо каква стойност е в първи?

551
00:33:17,280 --> 00:33:21,930
Първо сочеше този възел, така че това означава, че сега трябва да се насочи към този възел.

552
00:33:21,930 --> 00:33:25,660
С други думи, това, което изглежда макар и нелепо каша с моя почерк,

553
00:33:25,660 --> 00:33:28,620
какво е проста идея просто се движат тези стрелки около

554
00:33:28,620 --> 00:33:31,560
превежда код само с този лайнер.

555
00:33:31,560 --> 00:33:38,110
Съхранява това, което е на първо място в следващото поле и след това да се актуализира какво всъщност е първа.

556
00:33:38,110 --> 00:33:40,900
Нека вървим напред и бързо напред чрез някои от това,

557
00:33:40,900 --> 00:33:44,220
и гледам само в тази опашка на вмъкване за сега.

558
00:33:44,220 --> 00:33:51,210
Да предположим, че стигнем до точката, в която аз намирам, че следващото поле на някои възел е NULL.

559
00:33:51,210 --> 00:33:53,410
И в този момент в историята, една подробност, че аз съм специфичността

560
00:33:53,410 --> 00:33:58,170
е, че въведохме друг показалеца тук в линия 142, предшественик на показалеца.

561
00:33:58,170 --> 00:34:01,320
По същество, в този момент в историята, след като в списъка получава дълго,

562
00:34:01,320 --> 00:34:04,800
Някак си трябва да го извърви с два пръста, защото ако отида твърде далеч,

563
00:34:04,800 --> 00:34:08,219
помня в една единствена дължина, не можете да се върнете назад.

564
00:34:08,219 --> 00:34:13,659
Така че тази идея на predptr е лявата ми пръст, и newptr - не newptr.

565
00:34:13,659 --> 00:34:17,199
Друго основание е, че е тук е другият ми пръст, а аз съм просто вид на ходене на списъка.

566
00:34:17,199 --> 00:34:22,179
Ето защо, който съществува. Но нека разглеждаме само един от по-простите случаи тук.

567
00:34:22,179 --> 00:34:26,620
Ако е NULL, че следващото поле на показалеца, това, което е логично отражение?

568
00:34:26,620 --> 00:34:30,840
Ако се пресичат този списък и да ви удари с нулев указател?

569
00:34:30,840 --> 00:34:35,780
Ти си в края на списъка, така че код, за да добавите това един допълнителен елемент

570
00:34:35,780 --> 00:34:41,230
е нещо от интуитивен ще вземе този възел, чието следващия показалецът е NULL,

571
00:34:41,230 --> 00:34:46,120
така че това в момента е NULL, и да я промените, макар и да е адресът на новия възел.

572
00:34:46,120 --> 00:34:52,260
Така че ние просто привличане на код върху стрелката, която направихме на сцената чрез повишаване на лявата ръка на някого.

573
00:34:52,260 --> 00:34:54,070
>> И случай, че аз ще размахва ръцете ми за сега,

574
00:34:54,070 --> 00:34:58,020
просто защото мисля, че е лесно да се загубиш, когато ние го правим в този вид на околната среда,

575
00:34:58,020 --> 00:35:00,600
проверка за вмъкване в средата на списъка.

576
00:35:00,600 --> 00:35:03,220
Но просто интуитивно, какво трябва да се случи, ако искате да разберете

577
00:35:03,220 --> 00:35:06,600
когато известен брой принадлежи в средата е, че е нужно да се разхождате

578
00:35:06,600 --> 00:35:09,510
с повече от един пръст, повече от една показалка,

579
00:35:09,510 --> 00:35:12,920
разбера къде принадлежи чрез проверка е елемент <настоящата,

580
00:35:12,920 --> 00:35:15,450
> Една страна, и след като се намери това място,

581
00:35:15,450 --> 00:35:20,400
тогава ще трябва да направи този вид на черупката игра, когато се движите указатели около много внимателно.

582
00:35:20,400 --> 00:35:23,850
И този отговор, ако искате да причина през това у дома на собствения си,

583
00:35:23,850 --> 00:35:28,340
свежда само до тези два реда код, но от порядъка на тези линии е супер важно.

584
00:35:28,340 --> 00:35:31,390
Защото, ако пуснете ръката на някого и да се повиши някой друг е в грешен ред,

585
00:35:31,390 --> 00:35:34,580
отново, може да се окажете orphaning списъка.

586
00:35:34,580 --> 00:35:39,500
За да обобщим по-концептуално, вмъкване в опашката е сравнително лесно.

587
00:35:39,500 --> 00:35:42,940
Вмъкване в главата също е относително ясно,

588
00:35:42,940 --> 00:35:45,580
но трябва да се актуализират допълнително показалеца този път

589
00:35:45,580 --> 00:35:47,930
да изтръгне номер пет в списъка,

590
00:35:47,930 --> 00:35:51,560
и след това поставяне в средата включва още повече усилия,

591
00:35:51,560 --> 00:35:56,130
много внимателно поставете номер 20 на правилното му място,

592
00:35:56,130 --> 00:35:58,350
, която е между 17 и 22.

593
00:35:58,350 --> 00:36:02,700
Така че ще трябва да направя нещо подобно има нов възел 20, точка 22,

594
00:36:02,700 --> 00:36:08,470
и след това, показалецът които възел трябва да бъде актуализиран за последен път?

595
00:36:08,470 --> 00:36:10,630
Тя е на 17, за да я поставете.

596
00:36:10,630 --> 00:36:14,080
Така че отново, аз ще отложи действителният код за това конкретно изпълнение.

597
00:36:14,080 --> 00:36:17,280
>> На пръв поглед това е малко в повече, но това е наистина само един безкраен цикъл

598
00:36:17,280 --> 00:36:21,770
, която е примка, примка, примка, примка и се счупи, веднага след като удари нулев указател,

599
00:36:21,770 --> 00:36:24,590
, при която можете да направите необходимата вмъкване.

600
00:36:24,590 --> 00:36:30,960
Това, тогава, е представител свързана код за вмъкване на списък.

601
00:36:30,960 --> 00:36:34,590
Това е нещо много, и тя се чувства като сме решили един проблем,

602
00:36:34,590 --> 00:36:36,940
но ние въведохме съвсем друга. Честно казано, ние Прекарах цялото това време

603
00:36:36,940 --> 00:36:40,540
на Big O и Ω и време на работа, се опитват да решават проблеми по-бързо,

604
00:36:40,540 --> 00:36:43,270
и тук ние сме като една голяма крачка назад, тя се чувства.

605
00:36:43,270 --> 00:36:45,380
И все пак, ако целта е да се съхраняват данните,

606
00:36:45,380 --> 00:36:48,010
тя се чувства като Светия Граал, както казахме в понеделник, наистина ще бъде

607
00:36:48,010 --> 00:36:50,470
да съхранявате нещата веднага.

608
00:36:50,470 --> 00:36:53,930
>> В действителност, да предположим, че сме направили оставим настрана свързан списък за миг

609
00:36:53,930 --> 00:36:56,000
и ние вместо да въведе понятието за маса.

610
00:36:56,000 --> 00:36:59,110
И нека просто мисля, че на масата за миг като масив.

611
00:36:59,110 --> 00:37:03,790
Този масив и този случай тук има около 26 елемента, от 0 до 25,

612
00:37:03,790 --> 00:37:07,940
и предполагам, че ви е необходимо някакво парче за съхранение на имена:

613
00:37:07,940 --> 00:37:10,350
Алис и Боб и Чарли и подобни.

614
00:37:10,350 --> 00:37:12,880
И трябва някои данни структура за съхранение на тези имена.

615
00:37:12,880 --> 00:37:15,000
Е, можете да използвате нещо като свързан списък

616
00:37:15,000 --> 00:37:20,260
и може да ходи списъка вмъкване на Алис пред Боб и Чарли след Боб и така нататък.

617
00:37:20,260 --> 00:37:23,850
И в действителност, ако искате да видите код, като това настрана,

618
00:37:23,850 --> 00:37:27,230
знаете, че в list2.h, ние правим точно това.

619
00:37:27,230 --> 00:37:30,610
Ние няма да мине през този код, но това е вариант на първия пример

620
00:37:30,610 --> 00:37:34,640
, която въвежда една друга структура, сме виждали преди нар. студентски,

621
00:37:34,640 --> 00:37:40,330
и след това какво всъщност се съхранява в свързан списък е указател към структура студент

622
00:37:40,330 --> 00:37:44,520
а не просто малко цяло число, бр.

623
00:37:44,520 --> 00:37:46,900
Така разбирам, че е код, който включва действителните струни,

624
00:37:46,900 --> 00:37:49,940
но ако целта на ръка наистина сега е за решаване на проблема за ефективност,

625
00:37:49,940 --> 00:37:53,380
не би ли било хубаво, ако сме обект наречен Алис,

626
00:37:53,380 --> 00:37:56,020
искаме да я постави на мястото му в структурата на данните,

627
00:37:56,020 --> 00:37:58,860
тя се чувства като тя ще бъде наистина хубаво да съм сложил Алис,

628
00:37:58,860 --> 00:38:01,180
, чието име започва с А, в първото място.

629
00:38:01,180 --> 00:38:05,270
И Боб, чието име започва с Б, във второто място.

630
00:38:05,270 --> 00:38:09,580
С масив, или да започнете да го наричаш маса, хеш таблица в това,

631
00:38:09,580 --> 00:38:13,650
можем да направим точно това. Ако ни е дадено име като Алис,

632
00:38:13,650 --> 00:38:16,700
низ като Алиса, където се слага A-л-и-в-е?

633
00:38:16,700 --> 00:38:20,540
Имаме нужда от hueristic. Имаме нужда от функция да отнеме известно входа като Алиса

634
00:38:20,540 --> 00:38:24,610
и да се върне отговор "Поставете Алис на това място."

635
00:38:24,610 --> 00:38:28,720
И тази функция, тази черна кутия, ще се нарича хеш функция.

636
00:38:28,720 --> 00:38:32,330
>> А хеш функция е нещо, което се вход, като "Алиса",

637
00:38:32,330 --> 00:38:38,080
и се връща към вас, обикновено цифровата място в структурата някои данни, когато Алис принадлежи.

638
00:38:38,080 --> 00:38:40,830
В този случай, нашата хеш функция трябва да бъде сравнително проста.

639
00:38:40,830 --> 00:38:47,510
Нашата хеш функция трябва да кажа, че ако ви се предоставя "Алиса", чийто характер трябва да се грижи за?

640
00:38:47,510 --> 00:38:55,660
Първия. Така че гледам [0], и тогава аз бих казал, ако [0] герой е, върнете номер 0.

641
00:38:55,660 --> 00:39:01,130
Ако това е Б, върнете 1. Ако това е C, върнете два, и така нататък.

642
00:39:01,130 --> 00:39:05,940
Всички 0 индекс, и това ще ми позволи да вмъкнете Алис и след това Боб и след това Чарли и т.н.

643
00:39:05,940 --> 00:39:10,960
в тази структура на данните. Но има един проблем.

644
00:39:10,960 --> 00:39:13,060
Какво ще стане, ако Анита идва заедно отново?

645
00:39:13,060 --> 00:39:17,510
Къде да вложим Анита? Нейното име също започва с буквата А,

646
00:39:17,510 --> 00:39:20,330
и тя се чувства като ние сме направили още по-голяма бъркотия на този проблем.

647
00:39:20,330 --> 00:39:24,380
Сега имат незабавен вмъкване, постоянно вмъкване в структурата на данните

648
00:39:24,380 --> 00:39:27,100
отколкото по-лош случай линейни,

649
00:39:27,100 --> 00:39:29,510
но какво можем да направим с Анита в този случай?

650
00:39:29,510 --> 00:39:34,110
Какви са двата варианта, наистина ли? Да?

651
00:39:34,110 --> 00:39:37,410
[Student отговор, неразбираем Добре, така че бихме могли да имат друго измерение.

652
00:39:37,410 --> 00:39:42,320
Това е добре. Така че ние можем да изградим нещата в 3D, като говорихме за устно в понеделник.

653
00:39:42,320 --> 00:39:46,700
Бихме могли да добавите друг достъп тук, но предполагам, че не, аз се опитвам да се запази тази проста.

654
00:39:46,700 --> 00:39:50,160
Целта тук е да има непосредствена постоянна време достъп,

655
00:39:50,160 --> 00:39:52,170
така че добавянето на твърде много сложност.

656
00:39:52,170 --> 00:39:55,970
Какви са другите варианти, когато се опитват да вмъкнете Анита в тази структура на данните? Да?

657
00:39:55,970 --> 00:39:58,610
[Student отговор, неразбираем] Добре. Така че ние може да се движи всеки друг,

658
00:39:58,610 --> 00:40:03,040
като Чарли побутвания надолу Боб и Алис, и след това ще се постави Анита, когато тя наистина иска да бъде.

659
00:40:03,040 --> 00:40:05,660
>> Разбира се, сега, има един страничен ефект от това.

660
00:40:05,660 --> 00:40:09,000
Структурата на тези данни вероятно е полезна не защото искаме да вмъкнем хора веднъж

661
00:40:09,000 --> 00:40:11,250
, а защото искаме да се провери дали те са там по-късно

662
00:40:11,250 --> 00:40:13,600
ако искаме да изкарваме всички имена в структурата на данните.

663
00:40:13,600 --> 00:40:15,850
Отиваме да направим нещо с тези данни в крайна сметка.

664
00:40:15,850 --> 00:40:20,810
Така че сега ние сме вид прецака Алис, който вече не е, където тя е трябвало да бъде.

665
00:40:20,810 --> 00:40:23,880
Не е Боб, нито е Чарли.

666
00:40:23,880 --> 00:40:26,060
Така че може би това не е толкова добра идея.

667
00:40:26,060 --> 00:40:28,830
Но наистина, това е една опция. Ние може да прехвърли всички,

668
00:40:28,830 --> 00:40:32,240
или дяволите, Анита дойде късно в играта, защо не можем просто да Anita

669
00:40:32,240 --> 00:40:35,870
не е тук, а не тук, а не тук, нека просто я малко по-ниско в списъка.

670
00:40:35,870 --> 00:40:38,680
Но тогава този проблем започва да се прехвърлят отново.

671
00:40:38,680 --> 00:40:41,630
Може да бъде в състояние да намери Алис незабавно, въз основа на първото си име.

672
00:40:41,630 --> 00:40:44,320
И Боб незабавно, и Чарли. Но след това търсят Анита,

673
00:40:44,320 --> 00:40:46,360
и ще видите, хм, Алис е на пътя.

674
00:40:46,360 --> 00:40:48,770
Ами, нека да ме проверите по-долу Алис. Боб не е Анита.

675
00:40:48,770 --> 00:40:51,850
Чарли не е Анита. О, има Анита.

676
00:40:51,850 --> 00:40:54,720
И ако продължи този влак на логиката по целия път,

677
00:40:54,720 --> 00:41:00,690
това, което е най-лошия случай времето за работа на намирането или поставяне на Анита в тази нова структура на данните?

678
00:41:00,690 --> 00:41:03,280
Това е O (N), нали?

679
00:41:03,280 --> 00:41:06,280
Защото в най-лошия случай, е Алис, Боб, Чарли. . .

680
00:41:06,280 --> 00:41:10,150
по целия път до някой на име "Y", така че има само едно място наляво.

681
00:41:10,150 --> 00:41:13,950
За щастие, имаме не една, наречена "Z", така че ние Анита на самото дъно.

682
00:41:13,950 --> 00:41:16,040
>> Ние не сме наистина решен този проблем.

683
00:41:16,040 --> 00:41:19,890
Така че може би ние трябва да се въведе този трето измерение.

684
00:41:19,890 --> 00:41:22,230
И се оказва, ако се въведе този третото измерение,

685
00:41:22,230 --> 00:41:25,240
не можем да направим това перфектно, но Светия Граал ще бъдат намалени

686
00:41:25,240 --> 00:41:28,370
постоянно вмъкване и динамични вмъквания, така че

687
00:41:28,370 --> 00:41:30,960
ние не трябва да трудно код масив на площ от 26.

688
00:41:30,960 --> 00:41:34,400
Ние можем да вкарвате толкова много имена, както ние искаме, но ще вземем 5-минутна почивка тук

689
00:41:34,400 --> 00:41:38,790
и след това да го направя правилно.

690
00:41:38,790 --> 00:41:46,020
Добре. Историята доста изкуствено там

691
00:41:46,020 --> 00:41:48,670
чрез избора на Алис и след това Боб и след това Чарли и тогава Анита,

692
00:41:48,670 --> 00:41:51,000
чието име е очевидно ще се сблъскат с Алис.

693
00:41:51,000 --> 00:41:54,120
Но въпросът, който завърши в понеделник с колко вероятно е

694
00:41:54,120 --> 00:41:56,370
, че ще получите тези видове сблъсъци? С други думи,

695
00:41:56,370 --> 00:42:00,490
ако започнем да използвате тази таблична структура, която е наистина само един масив,

696
00:42:00,490 --> 00:42:02,460
в този случай от 26 места,

697
00:42:02,460 --> 00:42:05,740
какво ще стане, ако нашите входове са, вместо да се разпределя равномерно?

698
00:42:05,740 --> 00:42:09,620
Това не е изкуствено Алис и Боб и Чарли и Дейвид и т.н. по азбучен ред,

699
00:42:09,620 --> 00:42:12,380
е равномерно разпределена А до Z.

700
00:42:12,380 --> 00:42:15,220
>> Може би ще получите късмет и ние няма да имат две или две Б

701
00:42:15,220 --> 00:42:17,640
с много висока степен на вероятност, но както някой посочи,

702
00:42:17,640 --> 00:42:20,730
ако ние генерализирана този проблем и не 0-25

703
00:42:20,730 --> 00:42:26,060
но, да речем, от 0 до 364 или 65, по-често броя на дните в една типична година,

704
00:42:26,060 --> 00:42:31,170
и зададе въпроса: "Каква е вероятността, че двама от нас в тази зала имат същия рожден ден?"

705
00:42:31,170 --> 00:42:34,600
Казано по друг начин, каква е вероятността, че двама от нас имат име започва с А?

706
00:42:34,600 --> 00:42:37,190
Въпросният вид е същата, но това адресно пространство,

707
00:42:37,190 --> 00:42:39,940
пространство, това търсене е по-голям в случай на рождени дни,

708
00:42:39,940 --> 00:42:42,820
защото имаме толкова много повече дни в годината, отколкото буквите в азбуката.

709
00:42:42,820 --> 00:42:44,910
Каква е вероятността от сблъсък?

710
00:42:44,910 --> 00:42:48,410
Е, можем да мислим за това, като разберете по математика по обратния начин.

711
00:42:48,410 --> 00:42:50,580
Каква е вероятността не сблъсъци?

712
00:42:50,580 --> 00:42:53,970
Е, този израз тук казва, че това е вероятността

713
00:42:53,970 --> 00:42:58,770
ако има само един човек в тази зала, че те имат уникален рожден ден?

714
00:42:58,770 --> 00:43:01,190
Това е 100%. Защото, ако има само един човек в стаята,

715
00:43:01,190 --> 00:43:03,940
неговия или нейния рожден ден може да бъде някоя от 365-те дни на годината.

716
00:43:03,940 --> 00:43:08,650
Така че 365/365 опции ми дава стойност на 1.

717
00:43:08,650 --> 00:43:11,250
Така че вероятността въпрос в момента е само един.

718
00:43:11,250 --> 00:43:13,270
Но ако има втори човек в стаята,

719
00:43:13,270 --> 00:43:16,490
каква е вероятността, че си рожден ден е различен?

720
00:43:16,490 --> 00:43:20,680
Има само 364 възможни дни, игнорирайки високосна година,

721
00:43:20,680 --> 00:43:23,580
за рождения си ден да не се сблъскат с други лица.

722
00:43:23,580 --> 00:43:31,920
Така че 364/365. Ако трето лице, е 363/365, и така нататък.

723
00:43:31,920 --> 00:43:35,790
Така че ние продължаваме умножаване на тези фракции, които са все по-малки и по-малки,

724
00:43:35,790 --> 00:43:40,720
да разбера каква е вероятността, че всички ние имаме уникални рождени дни?

725
00:43:40,720 --> 00:43:43,570
Но тогава можем да, разбира се, просто приемете този отговор и го обърнете наоколо

726
00:43:43,570 --> 00:43:47,210
и 1 минус всичко това, израз в крайна сметка ще се

727
00:43:47,210 --> 00:43:51,250
ако си спомняте, на гърба на математически книги, изглежда малко нещо като това,

728
00:43:51,250 --> 00:43:54,590
, което е много по-лесно тълкува графично.

729
00:43:54,590 --> 00:43:57,820
И този графичен тук има по оста х броя на рождени дни,

730
00:43:57,820 --> 00:44:02,030
или броят на хората с рождени дни, както и на оста Y е вероятността по време на мач.

731
00:44:02,030 --> 00:44:06,060
И това, което казва, е, че, ако имате, да речем, дори,

732
00:44:06,060 --> 00:44:10,860
да изберете нещо като 22, 23.

733
00:44:10,860 --> 00:44:13,160
Ако има 22 или 23 души в една стая,

734
00:44:13,160 --> 00:44:17,100
вероятността, че две от тези много малко хора ще имат същия рожден ден

735
00:44:17,100 --> 00:44:19,560
всъщност е супер висока, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% относително, че в един клас от 22 души, семинар, на практика,

737
00:44:23,450 --> 00:44:25,790
2 от тези хора ще имат същия рожден ден.

738
00:44:25,790 --> 00:44:28,520
Тъй като има толкова много начини, по които могат да имат същия рожден ден.

739
00:44:28,520 --> 00:44:31,110
Дори по-лошо, ако се вгледате в дясната страна на графиката,

740
00:44:31,110 --> 00:44:34,040
от времето, когато имат клас с 58 ученици в него,

741
00:44:34,040 --> 00:44:39,270
вероятността от два хора, които имат рожден ден е супер, супер високо, почти 100%.

742
00:44:39,270 --> 00:44:41,880
Сега, това е нещо забавно факта за реалния живот.

743
00:44:41,880 --> 00:44:45,850
>> Но последствията, сега, за структури от данни и съхранение на информация

744
00:44:45,850 --> 00:44:51,100
означава, че само ако приемем, че имат хубав, чист, равномерно разпределение на данни

745
00:44:51,100 --> 00:44:53,650
и имате достатъчно голям масив, за да се поберат на един куп неща

746
00:44:53,650 --> 00:44:59,360
не означава ли, че ще накараме хората в уникални места.

747
00:44:59,360 --> 00:45:03,810
Отиваш да има сблъсъци. Така че това понятие на хеширане, както се нарича,

748
00:45:03,810 --> 00:45:07,450
входен като "Алиса" и го масажирате по някакъв начин

749
00:45:07,450 --> 00:45:10,190
и след това да се върна отговор, като 0 или 1 или 2.

750
00:45:10,190 --> 00:45:17,500
Връщайки се някакъв изход от тази функция е измъчван от тази вероятност от сблъсък.

751
00:45:17,500 --> 00:45:19,530
И така, как можем да се справят с тези сблъсъци?

752
00:45:19,530 --> 00:45:21,940
Е, в единия случай, ние можем да се идеята, че беше предложено.

753
00:45:21,940 --> 00:45:25,100
Ние можем само да прехвърля всички, или може би малко по-просто,

754
00:45:25,100 --> 00:45:29,870
, а от движение всички останали, нека просто се движат Анита до дъното на достъпно място.

755
00:45:29,870 --> 00:45:32,810
Така че, ако Алис е 0, Боб е в една, Чарли е в 2,

756
00:45:32,810 --> 00:45:35,260
ние просто ще сложи Анита на място 3.

757
00:45:35,260 --> 00:45:38,860
И това е техника по структури от данни, наречена линейна сондиране.

758
00:45:38,860 --> 00:45:41,310
Linear защото сте просто ходене тази линия, и вие сте вид сондиране

759
00:45:41,310 --> 00:45:43,640
за наличните места в структурата на данните.

760
00:45:43,640 --> 00:45:46,210
Разбира се, това преминава в O (N).

761
00:45:46,210 --> 00:45:49,590
Ако структурата на данните е наистина пълен, има 25 души в него вече

762
00:45:49,590 --> 00:45:54,120
и след това Анита идва заедно, тя се озовава в какво ще бъде място Z, и това е добре.

763
00:45:54,120 --> 00:45:56,540
Тя все още се вписва, и ние можем да я намерим по-късно.

764
00:45:56,540 --> 00:46:00,100
>> Но това е в противоречие с целта за ускоряване на нещата.

765
00:46:00,100 --> 00:46:02,530
И какво, ако вместо това въведоха този третото измерение?

766
00:46:02,530 --> 00:46:06,400
Тази техника е обикновено се нарича отделна верижното, или с вериги.

767
00:46:06,400 --> 00:46:10,030
И какво е хеш таблица е, че това таблична структура,

768
00:46:10,030 --> 00:46:13,450
масата ви е само масив от указатели.

769
00:46:13,450 --> 00:46:18,230
Но какви са тези указатели сочат познайте какво?

770
00:46:18,230 --> 00:46:21,970
Свързан списък. И какво, ако вземем най-доброто от двете тези светове?

771
00:46:21,970 --> 00:46:26,500
Ние използваме масиви за първоначалните индекси

772
00:46:26,500 --> 00:46:32,070
в структурата на данните, така ние можем веднага да отидете на [0] [1], [30] или т.н.,

773
00:46:32,070 --> 00:46:36,480
но така, че ние имаме известна гъвкавост и ние може да се побере Анита и Алис и Адам

774
00:46:36,480 --> 00:46:38,630
и всяко друго име,

775
00:46:38,630 --> 00:46:43,470
вместо това нека другата ос расте произволно.

776
00:46:43,470 --> 00:46:47,340
И най-накрая, в понеделник, че изразителни възможности с свързан списък.

777
00:46:47,340 --> 00:46:49,530
Структура на данните могат да растат произволно.

778
00:46:49,530 --> 00:46:52,450
Освен това, бихме могли просто да направи огромна 2-мерен масив,

779
00:46:52,450 --> 00:46:57,190
но това ще бъде ужасна ситуация, ако един от редовете в 2-мерен масив

780
00:46:57,190 --> 00:47:01,280
не е достатъчно голям, за допълнителен човек, чието име се случва да започне с А.

781
00:47:01,280 --> 00:47:04,200
Дай Боже, ние трябва да се преразпределят огромна 2-измерна структура

782
00:47:04,200 --> 00:47:06,600
просто защото има толкова много хора, обявен за

783
00:47:06,600 --> 00:47:09,480
особено когато има толкова малко хора, наречени Z нещо.

784
00:47:09,480 --> 00:47:12,170
Това е просто ще бъде много рядка структурата на данните.

785
00:47:12,170 --> 00:47:15,400
Така че това не е добра от какъвто и да е начин, но сега най-малкото имат способността

786
00:47:15,400 --> 00:47:19,090
веднага да намерите, когато Алис или Анита принадлежи,

787
00:47:19,090 --> 00:47:21,090
най-малко по отношение на вертикалната ос,

788
00:47:21,090 --> 00:47:25,850
и тогава ние просто трябва да решите къде да поставите Анита или Алиса в страната на този свързан списък.

789
00:47:25,850 --> 00:47:32,480
Ако не ни пука за сортиране на нещата, колко бързо можем да вмъкнете Алиса в структура като тази?

790
00:47:32,480 --> 00:47:35,370
Това е константно време. Ние индекс в [0], и ако никой не е там,

791
00:47:35,370 --> 00:47:37,550
Алис отива в началото на тази свързан списък.

792
00:47:37,550 --> 00:47:40,000
Но това не е огромна сделка. Защото, ако Анита след това идва заедно

793
00:47:40,000 --> 00:47:42,160
известен брой стъпки по-късно, когато Анита принадлежат?

794
00:47:42,160 --> 00:47:45,140
[0]. Обектно-ориентиран. Алис е вече в тази свързан списък.

795
00:47:45,140 --> 00:47:47,760
>> Но ако ние не им пука за сортиране на тези имена,

796
00:47:47,760 --> 00:47:53,580
можем просто да се движат Алис свърши, посочете Анита, но дори и това е константно време.

797
00:47:53,580 --> 00:47:57,010
Дори ако има Алис и Адам и всички тези други имена,

798
00:47:57,010 --> 00:47:59,410
това не е наистина пренасочването им към физически. Защо?

799
00:47:59,410 --> 00:48:04,090
Защото ние просто тук с свързан списък, кой знае тези възли са все пак?

800
00:48:04,090 --> 00:48:06,550
Всичко, което трябва да направите, е да преместите галета.

801
00:48:06,550 --> 00:48:10,930
Преместване на стрелките; не трябва физически да се местят данни около.

802
00:48:10,930 --> 00:48:14,610
Така че можем да вмъкнете Анита, в този случай незабавно. Константно време.

803
00:48:14,610 --> 00:48:20,250
Така че ние имаме постоянно търсене, и постоянно поставяне на някой като Анита.

804
00:48:20,250 --> 00:48:22,740
Но вид oversimplifying света.

805
00:48:22,740 --> 00:48:28,510
Какво ще стане, ако по-късно искате да намерите Алис?

806
00:48:28,510 --> 00:48:31,050
Какво ще стане, ако по-късно искате да намерите Алис?

807
00:48:31,050 --> 00:48:35,690
Колко стъпки е, че ще отнеме?

808
00:48:35,690 --> 00:48:37,850
[Student отговор, неразбираем]

809
00:48:37,850 --> 00:48:40,950
Точно така. Броят на хората, преди Алис в свързан списък.

810
00:48:40,950 --> 00:48:45,420
Така че това не е съвсем перфектна, защото нашата структурата на данните, отново, тази вертикална достъп

811
00:48:45,420 --> 00:48:50,240
и след това го има тези свързани списъци висящи - всъщност, да не се съставя един масив.

812
00:48:50,240 --> 00:48:56,020
Той има тези свързани списъци виси от това, че изглежда малко нещо подобно.

813
00:48:56,020 --> 00:48:59,110
Но проблемът е, че ако Алис и Адам и всички тези други имена

814
00:48:59,110 --> 00:49:01,720
в крайна сметка все повече и повече там,

815
00:49:01,720 --> 00:49:04,810
намиране на някой може да свърши куп стъпки,

816
00:49:04,810 --> 00:49:06,670
bcause имате да прекосяват свързан списък,

817
00:49:06,670 --> 00:49:08,090
което е линейна операция.

818
00:49:08,090 --> 00:49:14,270
Така че наистина, тогава времето, вмъкване в крайна сметка е O (N), където N е броят на елементите в списъка.

819
00:49:14,270 --> 00:49:21,780
Разделена, нека произволно го наричат ​​m, където m е броят на свързаните списъци

820
00:49:21,780 --> 00:49:24,500
, която имаме в тази вертикална ос.

821
00:49:24,500 --> 00:49:27,180
С други думи, ако наистина поеме равномерно разпределение на имена,

822
00:49:27,180 --> 00:49:30,150
напълно нереалистично. Има очевидно повече на някои писма от други.

823
00:49:30,150 --> 00:49:32,580
>> Но ако приемем за момента, в който равномерно разпределение,

824
00:49:32,580 --> 00:49:37,350
и ние сме N общия брой на хората, и м общо вериги

825
00:49:37,350 --> 00:49:40,630
достъпни за нас, тогава дължината на всяка една от тези вериги

826
00:49:40,630 --> 00:49:44,380
много просто ще бъде общо, N, разделен на броя на вериги.

827
00:49:44,380 --> 00:49:48,900
Така N / m. Но тук е мястото, където можем да бъдем всички математически умен.

828
00:49:48,900 --> 00:49:53,030
m е константа, защото има фиксиран брой от тях.

829
00:49:53,030 --> 00:49:54,620
Ти ще обяви своя масив в началото,

830
00:49:54,620 --> 00:49:58,450
и ние не сме преоразмеряване на вертикалната ос. По дефиниция, която остава фиксирана.

831
00:49:58,450 --> 00:50:01,220
Това е само хоризонталната ос, така да се каже, че се променя.

832
00:50:01,220 --> 00:50:04,760
Така че, технически погледнато, това е константа. Така че сега времето, вмъкване

833
00:50:04,760 --> 00:50:09,700
е почти O (N).

834
00:50:09,700 --> 00:50:12,410
Така че това не чувстват всички, че много по-добре.

835
00:50:12,410 --> 00:50:14,940
Но каква е истината? Е, през цялото това време, в продължение на седмици,

836
00:50:14,940 --> 00:50:20,640
ние сме били казват O (N ²). O (N), 2 х н ² - N, разделена на 2. . . ECH.

837
00:50:20,640 --> 00:50:23,580
Това е просто N ². Но сега, в тази част на семестъра,

838
00:50:23,580 --> 00:50:25,560
можем да започнем отново да говорим за реалния свят.

839
00:50:25,560 --> 00:50:31,520
И N / m е абсолютно по-бързо, отколкото просто N сам.

840
00:50:31,520 --> 00:50:35,170
Ако имате хиляди имена и да ги разделите на няколко кофи

841
00:50:35,170 --> 00:50:37,820
, така че имате само десет имена във всяка една от тези вериги,

842
00:50:37,820 --> 00:50:41,670
абсолютно търсене десет неща, ще бъде по-бързо, отколкото хиляда неща.

843
00:50:41,670 --> 00:50:43,740
И така, един от предстоящите проблемни комплекти ще ви предизвикателство

844
00:50:43,740 --> 00:50:46,100
да се мисли за точно това, въпреки че, да,

845
00:50:46,100 --> 00:50:49,520
асимптотично и математически, това е все още само линейно,

846
00:50:49,520 --> 00:50:51,700
което е гадно по принцип, когато се опитвате да намерите неща.

847
00:50:51,700 --> 00:50:54,530
В действителност, това ще бъде по-бързо, отколкото това

848
00:50:54,530 --> 00:50:56,520
защото на този делител.

849
00:50:56,520 --> 00:50:58,310
И така отново ще бъде този компромис

850
00:50:58,310 --> 00:51:01,390
и този конфликт между теория и реалност,

851
00:51:01,390 --> 00:51:03,550
и едно от копчетата ще почне да се върти в този момент в семестър

852
00:51:03,550 --> 00:51:07,510
е повече от една реалност, тъй като ние някак се подготвят за края semster

853
00:51:07,510 --> 00:51:09,280
, тъй като ще се въведе в света на уеб програмирането,

854
00:51:09,280 --> 00:51:11,530
където наистина, изпълнението ще се броят, защото вашите потребители ще

855
00:51:11,530 --> 00:51:14,880
започнете да се чувствате и да ги оценят лоши дизайнерски решения.

856
00:51:14,880 --> 00:51:19,950
>> Е, как да отида за изпълнението на свързания - хеш таблица с 31 елемента?

857
00:51:19,950 --> 00:51:22,600
И предишния пример е произволно за рождени дни.

858
00:51:22,600 --> 00:51:26,190
Ако някой има рожден ден от 1 януари или февруари 1, ние ще ги постави в тази кофа.

859
00:51:26,190 --> 00:51:28,960
Ако това е януари 2, 2 февруари, 2 март, ще ги поставя в тази кофа.

860
00:51:28,960 --> 00:51:32,220
Ето защо е било 31. Как се обяви хеш таблица?

861
00:51:32,220 --> 00:51:37,480
Тя може да бъде доста проста, възел * Таблицата е произволно име за него, [31].

862
00:51:37,480 --> 00:51:42,400
Това ми дава 31 указатели към възли,

863
00:51:42,400 --> 00:51:45,370
и това ми позволява да имам 31 указатели към свързани списъци

864
00:51:45,370 --> 00:51:48,800
дори ако тези вериги са първоначално NULL.

865
00:51:48,800 --> 00:51:54,860
Какво искам да се сложи, ако искам да се запази "Alice", "Боб", "Чарли"?

866
00:51:54,860 --> 00:51:57,010
Е, ние трябва да приключи тези неща в структура

867
00:51:57,010 --> 00:52:00,530
защото имаме нужда от Алис да се отбележи Боб, да сочи към Чарли, и така нататък.

868
00:52:00,530 --> 00:52:04,940
Не можем просто да имат само имената, така че може да се създаде нова структура, наречена възел тук.

869
00:52:04,940 --> 00:52:08,310
>> Какво е действителното възел? Какво е възел в тази нова свързан списък?

870
00:52:08,310 --> 00:52:11,840
Първото нещо, наречено дума, е за името на лицето.

871
00:52:11,840 --> 00:52:14,340
Дължина, вероятно, се отнася до максималната дължина на името на човека,

872
00:52:14,340 --> 00:52:18,210
каквото и да е, 20, 30, 40 знака в луди случаи ъглови,

873
00:52:18,210 --> 00:52:22,680
и едно е за какво? Това е просто допълнително характер NULL, \ 0.

874
00:52:22,680 --> 00:52:27,410
Така че този възел опаковане "нещо" вътре в себе си,

875
00:52:27,410 --> 00:52:29,640
но също така декларира указател, наречен следващия

876
00:52:29,640 --> 00:52:32,580
така че можем верига Алис на Боб с Чарли и така нататък.

877
00:52:32,580 --> 00:52:36,700
Може да бъде нула, но не е задължително да бъде.

878
00:52:36,700 --> 00:52:40,110
Всички въпроси по тези хеш-таблици? Да?

879
00:52:40,110 --> 00:52:46,190
[Student питам въпрос, неразбираем] масив - добър въпрос.

880
00:52:46,190 --> 00:52:50,120
Защо това е Чар дума в масив, а не просто Чар *?

881
00:52:50,120 --> 00:52:53,830
В тази донякъде произволен пример, аз не искам да се налага да прибягват

882
00:52:53,830 --> 00:52:56,190
изчистване за всеки един от оригиналните имена.

883
00:52:56,190 --> 00:52:59,530
Исках да обяви максималното количество памет за низ

884
00:52:59,530 --> 00:53:06,020
така че мога да копирате в структурата Алис \ 0 и не трябва да се справят с изчистване и свободен и подобни.

885
00:53:06,020 --> 00:53:11,710
Но бих могъл да направя, че ако исках да бъда по-съзнателно използване на пространството. Добър въпрос.

886
00:53:11,710 --> 00:53:14,780
Така че нека се опитаме да обобщим далеч от това

887
00:53:14,780 --> 00:53:18,350
и се фокусира върху остатъка от днес на структури от данни, в по-общ план

888
00:53:18,350 --> 00:53:21,170
и други проблеми, които можем да решим, като се използват същите основи

889
00:53:21,170 --> 00:53:24,590
въпреки че самите структури от данни може да се различават в данните.

890
00:53:24,590 --> 00:53:27,910
>> Така се оказва, по компютърни науки, дърветата са много чести.

891
00:53:27,910 --> 00:53:29,760
И можеш да се сетиш на едно дърво нещо като родословно дърво,

892
00:53:29,760 --> 00:53:31,830
там, където има някои корени, някои матриарх или патриарх,

893
00:53:31,830 --> 00:53:34,540
баба или дядо или по-рано, обратно,

894
00:53:34,540 --> 00:53:38,880
под който са мама и татко или различни братя и сестри или нещо подобно.

895
00:53:38,880 --> 00:53:42,500
Така дървовидна структура има възли и има деца,

896
00:53:42,500 --> 00:53:45,260
обикновено 0 или повече деца за всеки възел.

897
00:53:45,260 --> 00:53:47,320
И някои от жаргона, който виждате на тази снимка тук

898
00:53:47,320 --> 00:53:50,630
е някоя от малки деца или внуци по краищата

899
00:53:50,630 --> 00:53:52,330
които нямат стрелки, произтичащи от тях,

900
00:53:52,330 --> 00:53:55,070
това са така наречените листа, и всеки от вътрешната страна

901
00:53:55,070 --> 00:53:58,790
е вътрешен възел, може да се нарече нещо по тези линии.

902
00:53:58,790 --> 00:54:01,430
Но тази структура е доста често срещано. Това е малко произволно.

903
00:54:01,430 --> 00:54:04,930
Ние имаме едно дете в ляво, имаме три деца в дясно,

904
00:54:04,930 --> 00:54:06,830
две деца в долния ляв ъгъл.

905
00:54:06,830 --> 00:54:10,740
Така че ние може да има различни по големина дървета, но ако започнем да се стандартизират нещата,

906
00:54:10,740 --> 00:54:15,330
и можете да си спомните от видео Патрик двоично търсене от предишна кратко

907
00:54:15,330 --> 00:54:19,490
онлайн, двоично търсене не трябва да бъдат изпълнени с множество

908
00:54:19,490 --> 00:54:21,410
или парчета хартия върху дъската.

909
00:54:21,410 --> 00:54:25,490
Да предположим, че искате да съхранявате вашите номера в по-сложна структура на данните.

910
00:54:25,490 --> 00:54:27,680
Можете да създадете едно дърво като този.

911
00:54:27,680 --> 00:54:35,290
Може да имате възел, декларирани в C, и този възел може да има най-малко два елемента вътре в нея.

912
00:54:35,290 --> 00:54:39,470
Един от тях е номер, който искате да съхранявате, а другият е - добре, ние трябва още един.

913
00:54:39,470 --> 00:54:41,540
Другият е своите деца.

914
00:54:41,540 --> 00:54:45,150
Така че тук е друга структурата на данните. Този път, възел се определя като съхраняване на номер N

915
00:54:45,150 --> 00:54:49,060
и след това две указатели; ляво на детето и право дете.

916
00:54:49,060 --> 00:54:52,100
И те не са произволни. Какво е интересно за това дърво?

917
00:54:52,100 --> 00:55:00,550
>> Каква е модел как сме, това или как Патрик изложи в своето видео?

918
00:55:00,550 --> 00:55:02,790
Това е нещо очевидно, че има някакъв сортиране става тук,

919
00:55:02,790 --> 00:55:04,460
но това, което е просто правило? Да?

920
00:55:04,460 --> 00:55:08,350
[Student отговор, неразбираем]

921
00:55:08,350 --> 00:55:12,040
Perfect. Ако погледне, ще видите малък брой от ляво,

922
00:55:12,040 --> 00:55:14,690
големите цифри отляво, но това е вярно за всеки възел.

923
00:55:14,690 --> 00:55:20,370
За всеки възел, лявата му дете по-малко от него, и правото си дете по-голяма от него.

924
00:55:20,370 --> 00:55:25,210
Какво означава това сега е, ако искам да потърся тази структура на данните, да речем, брой 44,

925
00:55:25,210 --> 00:55:29,320
Трябва да започне в основата, защото, както с всички тези по-сложни структури от данни,

926
00:55:29,320 --> 00:55:31,910
имаме само указател към едно нещо, от самото начало.

927
00:55:31,910 --> 00:55:35,010
И в този случай, началото е коренът. Това не е в левия край,

928
00:55:35,010 --> 00:55:39,530
това е коренът на тази структура. Така че виждате тук, е 55, а аз търся 44.

929
00:55:39,530 --> 00:55:41,430
Коя посока да искате да отидете?

930
00:55:41,430 --> 00:55:45,680
Е, аз искам да отида на ляво, защото очевидно, в дясно ще бъде твърде голям.

931
00:55:45,680 --> 00:55:49,050
Така че забележите тук, ти си вид концептуално кълцане на дърво в 1/2

932
00:55:49,050 --> 00:55:51,700
защото никога не отиваме към дясната страна.

933
00:55:51,700 --> 00:55:55,410
Така че сега отивам от 55 до 33. Това е твърде малко на брой.

934
00:55:55,410 --> 00:56:01,590
Търся 44, но сега знам, ако 44 е в това дърво, мога да отида очевидно надясно.

935
00:56:01,590 --> 00:56:04,460
Така че отново, аз съм подрязване на дървото наполовина.

936
00:56:04,460 --> 00:56:06,780
Това е почти идентичен концептуално до телефонния указател.

937
00:56:06,780 --> 00:56:09,510
Това е идентично с това, което направихме с документите на дъската,

938
00:56:09,510 --> 00:56:13,940
но това е по-сложна структура, която ни позволява да се прави

939
00:56:13,940 --> 00:56:16,880
това разделяй и владей по проект на алгоритъма,

940
00:56:16,880 --> 00:56:19,420
и в действителност, пресичащо структура като тази - ОПА.

941
00:56:19,420 --> 00:56:22,870
Присичайки структура като тази, където това е само "отиде по този начин или да отидете по този начин",

942
00:56:22,870 --> 00:56:26,870
означава, че кода, който се наведе ума си първи при реализирането му в раздел

943
00:56:26,870 --> 00:56:31,270
или пеша през него у дома, за двоично търсене, използване на рекурсия или итерация

944
00:56:31,270 --> 00:56:35,060
това е болка в областта на шията. Среда елемент, след това направете закръгляне нагоре или надолу.

945
00:56:35,060 --> 00:56:39,230
>> Има красотата на това, защото сега можем да използва рекурсия отново,

946
00:56:39,230 --> 00:56:43,760
но много по-чисто. В действителност, ако сте на 55 броя и искате да намерите 44,

947
00:56:43,760 --> 00:56:48,450
отиди наляво в този случай, тогава какво правиш? Вие изпълнявате точно същия алгоритъм.

948
00:56:48,450 --> 00:56:51,560
Можете да проверите стойността на възела, а след това да отидете наляво или надясно.

949
00:56:51,560 --> 00:56:53,670
Тогава да проверите стойността на възела, наляво или надясно.

950
00:56:53,670 --> 00:56:56,710
Това е напълно подходящ за рекурсия.

951
00:56:56,710 --> 00:57:00,920
Така че дори и в миналото сме направили някои доста произволни примери, свързани с рекурсия

952
00:57:00,920 --> 00:57:03,430
, които не трябва да бъдат рекурсивен, с данни stuctures,

953
00:57:03,430 --> 00:57:07,820
особено дървета, това е перфектното прилагането на тази идея за проблем,

954
00:57:07,820 --> 00:57:12,920
свива, и след това решаването на един и същ вид, но по-малка програма.

955
00:57:12,920 --> 00:57:14,590
>> Така че има друга структура на данните, че можем да представим.

956
00:57:14,590 --> 00:57:18,760
Това е проектирана на пръв поглед да изглежда загадъчно, но това е невероятно.

957
00:57:18,760 --> 00:57:25,090
Така че това е структура, наречена Trie, Trie, който е наследил от думата извличане на данни,

958
00:57:25,090 --> 00:57:30,210
които не се произнася повторно опит-вал, но това е, което светът нарича тези неща. Опитва. T-R-и-д.

959
00:57:30,210 --> 00:57:35,190
Това е дървовидна структура от някакъв вид, но всеки един от възлите в Trie

960
00:57:35,190 --> 00:57:41,280
се появява за да бъде това? И това е малко подвеждащо, защото това е вид съкратено.

961
00:57:41,280 --> 00:57:45,960
Но изглежда, че всеки възел в тази Trie е всъщност масив.

962
00:57:45,960 --> 00:57:48,840
И въпреки че авторът на тази схема не е показано,

963
00:57:48,840 --> 00:57:54,130
в този случай, това Trie е структура от данни, чиято цел в живота е да съхранява думи

964
00:57:54,130 --> 00:57:57,330
като A-л-и-в-д или B-о-б.

965
00:57:57,330 --> 00:58:02,480
И начина, по който тези данни магазини Алис и Боб и Чарли и Анита и т.н.

966
00:58:02,480 --> 00:58:06,970
се използва масив за съхранение на Алиса в страната на Trie

967
00:58:06,970 --> 00:58:09,820
да започнем коренът, който изглежда като масив,

968
00:58:09,820 --> 00:58:12,080
и това е било написано в съкратена нотация.

969
00:58:12,080 --> 00:58:15,070
Авторът пропусне abcdefg, защото нямаше никакви имена с това.

970
00:58:15,070 --> 00:58:19,150
Те показват само М и P и Т, но в този случай,

971
00:58:19,150 --> 00:58:22,780
нека да се отдалечи от Алис и Боб и Чарли някои имена, които са тук.

972
00:58:22,780 --> 00:58:25,670
Максуел е действително в тази схема.

973
00:58:25,670 --> 00:58:29,570
Как автора магазин М-х-w-е-л-л?

974
00:58:29,570 --> 00:58:36,990
Той или тя започна в основата възел и отиде да [M], така че около 13, на 13-то място в масива.

975
00:58:36,990 --> 00:58:40,750
Тогава от там, има показалка.

976
00:58:40,750 --> 00:58:42,760
Показалеца, което води до друг масив.

977
00:58:42,760 --> 00:58:47,880
От там авторът индексират в този масив на място А, както е показано в горния ляв

978
00:58:47,880 --> 00:58:52,250
и тогава той или тя следва, че показалецът да друг масив,

979
00:58:52,250 --> 00:58:55,460
и отиде на показалеца на място при X.

980
00:58:55,460 --> 00:58:59,840
Тогава в следващото място масив W, E, L, L, и т.н.,

981
00:58:59,840 --> 00:59:03,090
и накрая, нека се опитаме да сложите снимка на това.

982
00:59:03,090 --> 00:59:05,380
Какво прави един възел изглежда като код?

983
00:59:05,380 --> 00:59:11,820
Възел в Trie съдържа масив от указатели към повече възли.

984
00:59:11,820 --> 00:59:16,090
Но има и трябва да има някакъв вид на булева стойност, поне в това изпълнение.

985
00:59:16,090 --> 00:59:18,770
Аз се случи да го наричат ​​is_word. Защо?

986
00:59:18,770 --> 00:59:22,670
Защото, когато вие поставяте Максуел, вие не поставяте

987
00:59:22,670 --> 00:59:25,300
нищо в тази структура на данните.

988
00:59:25,300 --> 00:59:27,480
Вие не пишат М. не пишат X.

989
00:59:27,480 --> 00:59:30,240
Всичко, което правим, е след указатели.

990
00:59:30,240 --> 00:59:33,360
Указател, който представлява M, показалеца, която представлява,

991
00:59:33,360 --> 00:59:36,310
показалеца, който представлява X, W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
но това, което трябва да направите, в края е нещо отидете, проверете, стигнах до това място.

993
00:59:41,950 --> 00:59:45,560
Имаше дума, която завършва тук, в структурата на данните.

994
00:59:45,560 --> 00:59:48,190
>> Така че това, което Trie е наистина изпълнен с автора избра да представлява

995
00:59:48,190 --> 00:59:51,880
тези terminuses с малки триъгълници.

996
00:59:51,880 --> 00:59:56,470
Това просто означава, че всъщност този триъгълник е тук, това булева стойност на истинската

997
00:59:56,470 --> 00:59:59,200
означава, че ако се върнете назад в дървото,

998
00:59:59,200 --> 01:00:02,420
това означава, че една дума, име Максуел е в това.

999
01:00:02,420 --> 01:00:04,870
Но думата Foo, например,

1000
01:00:04,870 --> 01:00:07,970
не е в дървото, защото ако започна коренът тук най-отгоре,

1001
01:00:07,970 --> 01:00:14,030
Има показалеца не е, няма показалеца о, не показалеца о. Foo не е име в този речник.

1002
01:00:14,030 --> 01:00:22,460
Но за разлика от Тюринг, т-у-р-и-н-гр. Отново, аз не съхранявате тона или U или R или аз или н или г.

1003
01:00:22,460 --> 01:00:29,820
Но аз направих магазин в структурата на данни стойността на верния път тук, в този възел - в дърво

1004
01:00:29,820 --> 01:00:33,030
чрез създаването на тази булева стойност на is_word да е истина.

1005
01:00:33,030 --> 01:00:35,740
Trie е вид на този много интересен мета структура,

1006
01:00:35,740 --> 01:00:39,810
, където не сте наистина съхранение на думи за себе си този вид на речника.

1007
01:00:39,810 --> 01:00:45,100
Да бъде ясно, просто съхранение "да" или "не", има дума, която свършва тук.

1008
01:00:45,100 --> 01:00:46,430
>> Сега, какъв е изводът?

1009
01:00:46,430 --> 01:00:51,120
Ако имате 150 000 думи в речника, че се опитвате да се съхранява в паметта

1010
01:00:51,120 --> 01:00:53,400
използвате нещо като свързан списък,

1011
01:00:53,400 --> 01:00:56,870
ще имат 150 000 възли в свързали списък.

1012
01:00:56,870 --> 01:01:00,250
И намирането на една от тези думи по азбучен ред може да отнеме O (N) време.

1013
01:01:00,250 --> 01:01:04,370
Линейно време. Но в случай на Trie,

1014
01:01:04,370 --> 01:01:09,210
какво е времето на работа на намирането на думата?

1015
01:01:09,210 --> 01:01:17,390
Оказва се, че красотата тук е, че дори и ако имате 149 999 думи, които вече са в този речник,

1016
01:01:17,390 --> 01:01:20,170
, както се прилага с тази структура на данните,

1017
01:01:20,170 --> 01:01:25,560
колко време отнема да се намери или да вмъкнете още един човек в това, като Алис, Алис?

1018
01:01:25,560 --> 01:01:30,640
Е, това е само пет, може би шест стъпки за задния характер.

1019
01:01:30,640 --> 01:01:32,880
Тъй като presense на други имена в структурата

1020
01:01:32,880 --> 01:01:35,340
не в начина на поставяне на Алис.

1021
01:01:35,340 --> 01:01:39,640
Освен това намирането на Алис, след като има 150 000 думи в този речник

1022
01:01:39,640 --> 01:01:41,960
не получите във вашия начин за намиране на Алис,

1023
01:01:41,960 --> 01:01:46,880
защото е Алис. . . . . тук, защото открих булева стойност.

1024
01:01:46,880 --> 01:01:50,920
И ако няма булев вярно, тогава Алис не е в това структурата на данните на думи.

1025
01:01:50,920 --> 01:01:56,220
С други думи, време за намиране на неща и да поставите нещата в тази нова

1026
01:01:56,220 --> 01:02:01,920
структурата на данните на Trie O - това не е N.

1027
01:02:01,920 --> 01:02:05,730
Тъй като presense на 150 000 души има никакъв ефект върху Алис, както изглежда.

1028
01:02:05,730 --> 01:02:11,560
Така че нека да го наречем к, където к е максималната дължина на думата на английски език

1029
01:02:11,560 --> 01:02:14,050
който обикновено е не повече от 20-тина символи.

1030
01:02:14,050 --> 01:02:17,940
Така че к е константа. Така че Светия Граал изглежда вече сме в момента

1031
01:02:17,940 --> 01:02:26,000
е, че на Trie, константно време за вложки за заявки, за изтриване.

1032
01:02:26,000 --> 01:02:29,170
Тъй като броят на неща, които вече са в структурата,

1033
01:02:29,170 --> 01:02:32,600
, които дори не са физически там. Отново, те просто някак отметка, "да" или "не",

1034
01:02:32,600 --> 01:02:35,050
не оказва влияние на нейното бъдещо време на работа.

1035
01:02:35,050 --> 01:02:37,940
>> Но там трябва да е уловка, защото в противен случай не би да губи толкова много време

1036
01:02:37,940 --> 01:02:41,460
по всички тези други структури от данни най-накрая да стигнем до тайната, това е невероятно.

1037
01:02:41,460 --> 01:02:46,410
Така че каква цена се плаща за да се постигне това величие тук? Space.

1038
01:02:46,410 --> 01:02:49,010
Това нещо е огромно. И причината, че авторът

1039
01:02:49,010 --> 01:02:52,400
не го представя тук, забележете, че всички тези неща, които приличат на масиви,

1040
01:02:52,400 --> 01:02:55,400
той не изтегли останалата част от дървото, а останалата част на Trie

1041
01:02:55,400 --> 01:02:58,060
защото те просто не са свързани с историята.

1042
01:02:58,060 --> 01:03:01,870
Но всички тези възли са супер широк, и всеки възел в дървото заема

1043
01:03:01,870 --> 01:03:07,780
26 или всъщност, може да бъде 27 знака, защото в този случай, включително място за апостроф

1044
01:03:07,780 --> 01:03:09,980
, така че бихме могли да има apostrophized думи.

1045
01:03:09,980 --> 01:03:14,450
В този случай, те големи масиви. Така че, въпреки че те не са picutured,

1046
01:03:14,450 --> 01:03:18,190
това отнема огромно количество RAM.

1047
01:03:18,190 --> 01:03:20,670
Което може да се оправи, especilly в съвременния хардуер,

1048
01:03:20,670 --> 01:03:25,650
но това е компромис. Ставаме по-малко време, като прекарат повече пространство.

1049
01:03:25,650 --> 01:03:28,580
Е, къде е всичко това отиваш?

1050
01:03:28,580 --> 01:03:32,640
Е, нека да направим - нека видим тук.

1051
01:03:32,640 --> 01:03:39,510
Нека да направим скок на този човек тук.

1052
01:03:39,510 --> 01:03:43,450
>> Вярвате или не, колкото и забавно като C е бил за известно време сега,

1053
01:03:43,450 --> 01:03:48,130
ние сме достига точката на семестъра, когато е време за преход към по-модерни неща.

1054
01:03:48,130 --> 01:03:50,950
Неща на по-високо ниво. И въпреки, че за следващите няколко седмици

1055
01:03:50,950 --> 01:03:54,580
ние все пак ще продължи да се потопим в света на указатели и управление на паметта

1056
01:03:54,580 --> 01:03:57,210
за да получите този утехата, с която може да се гради върху,

1057
01:03:57,210 --> 01:04:01,270
края на играта е в крайна сметка да се въведе, по ирония на съдбата не, този език.

1058
01:04:01,270 --> 01:04:03,330
Ние ще отделим, както и 10 включени минути за разговори за HTML.

1059
01:04:03,330 --> 01:04:05,950
HTML е език за маркиране и какво е език за маркиране е

1060
01:04:05,950 --> 01:04:10,220
е тези серии на отворени скоби и затворени скоби, които казват "това смело"

1061
01:04:10,220 --> 01:04:12,000
- Това курсив "направи това в центъра на.

1062
01:04:12,000 --> 01:04:14,250
Това не е всичко, което интелектуално интересно, но това е супер полезно.

1063
01:04:14,250 --> 01:04:16,650
И със сигурност това е вездесъщ тези дни.

1064
01:04:16,650 --> 01:04:19,450
Но това, което е мощен за света на HTML и уеб програмиране в по-общ план,

1065
01:04:19,450 --> 01:04:25,910
изграждането на динамични неща, писане на код в езици като PHP или Python или Ruby или Java или C #.

1066
01:04:25,910 --> 01:04:30,360
Наистина, независимо от езика си на избор, и генериране на HTML динамично.

1067
01:04:30,360 --> 01:04:32,960
Генериране на нещо, наречено CSS динамично.

1068
01:04:32,960 --> 01:04:35,810
На Cascading Style Sheets, което също е за естетиката.

1069
01:04:35,810 --> 01:04:41,360
И така, въпреки че днес, ако отида на някои сайт като познатия Google.com

1070
01:04:41,360 --> 01:04:46,100
и отивам да ги видите, разработчик, изглед източник, който може би не съм правил преди,

1071
01:04:46,100 --> 01:04:49,800
но ще видите източник, тези неща вероятно изглежда доста загадъчно.

1072
01:04:49,800 --> 01:04:55,320
Но това е основният код, който изпълнява Google.com.

1073
01:04:55,320 --> 01:04:57,940
На предния край. И всъщност всичко това е пухкав естетика неща.

1074
01:04:57,940 --> 01:05:01,740
Това е CSS тук. Ако продължавате да превъртате надолу ще получите някои оцветени неща.

1075
01:05:01,740 --> 01:05:06,890
Това е HTML. Код на Google изглежда като каша, но ако действително се отвори друг прозорец,

1076
01:05:06,890 --> 01:05:09,380
можем да видим някаква структура за това.

1077
01:05:09,380 --> 01:05:12,640
Ако отворя тази на, забележете, тук, това е малко по-разбираеми.

1078
01:05:12,640 --> 01:05:16,850
Отиваме да видите след дълго този етикет, [думата] е етикет,

1079
01:05:16,850 --> 01:05:23,520
HTML, главата, тялото, DIV, скрипт, текстовото поле, педя, центриран, Div.

1080
01:05:23,520 --> 01:05:26,770
И това също е някак загадъчен изглеждащи на пръв поглед,

1081
01:05:26,770 --> 01:05:30,890
но цялата тази бъркотия следва определени модели, и повтарящи се модели,

1082
01:05:30,890 --> 01:05:33,850
така че след като получите основите надолу, вие ще бъдете в състояние да напише код, като този

1083
01:05:33,850 --> 01:05:37,550
и манипулира код, като се използва още един език, наречен JavaScript.

1084
01:05:37,550 --> 01:05:40,440
И JavaScript е език, който се движи вътре в браузъра

1085
01:05:40,440 --> 01:05:44,380
днес, че ние използваме на Харвард курсове, за търговски инструмент Разбира се, че Google Карти използва

1086
01:05:44,380 --> 01:05:48,660
да ви дам един куп на динамика, Facebook ви дава мигновени актуализации за състоянието,

1087
01:05:48,660 --> 01:05:51,430
Twitter се използва, за да ви покажа туитове незабавно.

1088
01:05:51,430 --> 01:05:53,820
Всичко това ще започнем да се потопим.

1089
01:05:53,820 --> 01:05:57,190
Но за да стигнем до там, ние трябва да разберем нещо за интернет.

1090
01:05:57,190 --> 01:06:01,130
Този клип тук е само за една минута дълго, и нека да приемем, за сега това е, в действителност,

1091
01:06:01,130 --> 01:06:08,380
как интернет работи като закачка за това, което е на път да дойде. Аз ви давам "Войни на мрежата".

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Slow музика хор ♫]

1093
01:06:14,720 --> 01:06:20,450
[Мъж] Той дойде с послание.

1094
01:06:20,450 --> 01:06:23,770
С протокол собствения си.

1095
01:06:23,770 --> 01:06:37,270
[♫ бързо електронната музика ♫]

1096
01:06:37,270 --> 01:06:41,330
Той дойде в един свят на готини защитни стени, незаинтересовани рутери,

1097
01:06:41,330 --> 01:06:45,690
и опасностите далеч по-лоши от смъртта.

1098
01:06:45,690 --> 01:06:55,400
Той е бърз. Той е силен. Той е TCP / IP, и той има адреса си.

1099
01:06:55,400 --> 01:06:59,250
Войни на мрежата.

1100
01:06:59,250 --> 01:07:05,290
[Малан] Следваща седмица, тогава. Интернет. Уеб програмиране. Това е CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]