1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Недела 6, Продолжува]

2
00:00:02,520 --> 00:00:04,160
[Дејвид Џ Malan] [Универзитетот Харвард]

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 водечки Walkthrough за проблемот сет 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
Предавање за среда, разни шорцеви, проблемот сетови, walkthroughs, 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
или снимањето на нивниот завршен проект или видео од нив мавтајќи здраво

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 ученици, сепак, доаѓа потребата за уште неколку CAS.

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
и чадори и малку bandanas за кучиња сега имаме и слично.

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
"Секој ден јас сум СКГ 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
"Тимот Бауден" е роден, овој дизајн е поднесено, меѓу врвот продавачи.

96
00:05:43,480 --> 00:05:49,040
Како што беше овој овде. Многу луѓе кои имале "Бауден треска" по продажбата на логови.

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
Да? Дај ми нешто. [Студентски одговор, неразбирливо]

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 да го направите? Да? [Студентски одговор, неразбирливо]

110
00:06:35,240 --> 00:06:38,100
Печати променливи. Значи, ако сакате да направите малку интроспекција во внатрешноста на вашата програма

111
00:06:38,100 --> 00:06:41,500
без да се впуштат во пишување printf изјави насекаде,

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
[Студентски одговор, неразбирливо]

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
која се обидува да стилизирам вашиот код малку повеќе чисто од вас, човечки, би можеле да имаат направено.

128
00:07:27,500 --> 00:07:29,530
Но, тоа, исто така, е навистина само естетска работа.

129
00:07:29,530 --> 00:07:34,110
Но излегува дека е тоа друга алатка наречена Valgrind што е малку повеќе arcane да го користите.

130
00:07:34,110 --> 00:07:36,860
Своето производство е atrociously криптичната на прв поглед.

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
Затоа што ако заборавите да се ослободи вашата меморија, или можете Dereference некои NULL покажувач,

135
00:07:49,320 --> 00:07:55,770
или можете Dereference некои ѓубре покажувач, што е обично симптом дека резултатите?

136
00:07:55,770 --> 00:07:59,470
Секунда грешка. И ќе го добиете ова јадро датотека на одреден број на килобајти или мегабајти

137
00:07:59,470 --> 00:08:02,990
што претставува состојба на меморија вашата програма кога се урнал,

138
00:08:02,990 --> 00:08:05,730
но вашата програма крајот секунда грешки, сегментација на вина,

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
грешки што може да се направи. Ова, исто така, е честа парадигма со Линукс програми.

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
Да? [Студентски одговор, неразбирливо] предалеку.

172
00:10:15,050 --> 00:10:17,060
Значи ти ја читаш на десната страна на знак за еднаквост.

173
00:10:17,060 --> 00:10:20,290
Ајде да се фокусираат само на левата страна, само на int * x.

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
[Студентски одговор, неразбирливо]

177
00:10:31,940 --> 00:10:35,090
Во ред. Тоа е се подготвува да го спаси адреса во меморијата.

178
00:10:35,090 --> 00:10:40,680
Добро. И ајде да ја искористам оваа чекор понатаму, тоа е прогласување на променлива, x, тоа е 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
Случајно тоа што тоа е една и иста со int,

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
На повеќе современи хардвер како на најновите Macs, најновите компјутери, може да имаат 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
Тоа е во ред движи напред за поедноставување на светот и само велат прогласи покажувач кој се нарекува x.

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
[Студентски одговор, неразбирливо]

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
Кога користите Примерок? [Студентски одговор, неразбирливо] Во ред.

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
или оваа специјална НУБ карактер, НУБ, на крајот од стрингот.

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
Ерго, кој е покажувачот. Значи линија 21, за жал, беше грешка.

218
00:13:11,140 --> 00:13:16,110
Но, прво, она што го прави тоа? Тоа е велејќи продавница на 10 место, 0 индексирани,

219
00:13:16,110 --> 00:13:19,480
на дел од меморија се нарекува х вредност 0.

220
00:13:19,480 --> 00:13:21,510
>> Значи забележите неколку работи се случува.

221
00:13:21,510 --> 00:13:25,420
Иако x е покажувач, да се потсетиме од пред неколку недели

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
каде што ќе се направи нешто како ова: Земете адреса x, се движи 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
x е на адреса не, низа, сама за себе.

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
[Студентски одговор, неразбирливо] Токму така.

233
00:14:17,370 --> 00:14:21,100
Ние само распределени десет ints, но ние сметаме од 0 кога програмирање во C,

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
бидејќи, се разбира, ова не е добро. Всушност, ако имате телефон Андроид или 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 или Андроид е само да го убие програма целосно

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
[Студентски одговор, неразбирливо] Во ред.

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
ова е една недела 2 или 3 прашањето, каде x е само во обем внатрешноста на тркалезните загради каде што било објавено.

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
[Студентски одговор, неразбирливо] Совршен. Да, точно.

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
која беше само да се направи warmup вежба, конвертирање децимална да хексадецимален на бинарни и така натаму.

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
Да? [Студентски одговор, неразбирливо] Во ред.

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
Можете да се јавите на функција како realloc ако првично наречен Примерок,

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
[Студентски одговор, неразбирливо] Тоа би можело да трае долго време.

338
00:20:44,060 --> 00:20:49,260
Всушност, во секое време ви се повикуваат Примерок или realloc или 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
Значи има предности и minuses тука.

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
Да? [Студентски одговор, неразбирливо] Во ред.

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
[Студентски одговор, неразбирливо]

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
А јазол има и int нарекува n и покажувач наречен следниот што само укажува на следното нешто во листата.

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
но лицето кое го напиша printf и други функции

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
Во тој случај, бевме доделување на int, овој пат ние сме распределба на еден јазол.

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
[Студентски одговор, неразбирливо]

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
Тоа може да биде некоја непозната вредност; не е добра работа ако јас -

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
А малку Trivia прашање: Ова е еквивалентно на она повеќе криптичната линија код?

476
00:28:35,270 --> 00:28:38,110
Како инаку би можеле да имам напишано ова? Сакате да земе прободе?

477
00:28:38,110 --> 00:28:41,480
[Студентски одговор, неразбирливо]

478
00:28:41,480 --> 00:28:44,870
Добро. Користење на. N, но тоа не е толку едноставно како ова.

479
00:28:44,870 --> 00:28:47,090
Што ми прво треба да се направи? [Студентски одговор, неразбирливо]

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
а потоа еднаш сте таму, тогаш можете да го користите на повеќе познати. n,

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
Инаку, ако тоа е вистински struct, користете. Н.

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
Сега тука, ова е малку проверка, каде што имаат да кажат дали новиот јазол вредноста на n

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-> следниот, тоа значи дека оди на struct

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
И во овој момент во приказната, детаљ што сум glossing над

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
Ако сте traversing оваа листа и го погоди NULL покажувачот?

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
да се притисне број 5 во листата тука,

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
која е looping, looping, looping, looping, и кршење штом ќе го погоди NULL покажувач,

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
на големите 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
која се воведува една друга struct видовме пред т.н. студент,

621
00:37:34,640 --> 00:37:40,330
а потоа она што всушност продавници во поврзаните листа е покажувач кон студентот структура

622
00:37:40,330 --> 00:37:44,520
наместо просто малку број, n.

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
жиците како Алис, каде да се стави А-л-и-в-е?

633
00:38:16,700 --> 00:38:20,540
Ние треба hueristic. Ние треба во функција да се преземат некои влез како Alice

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, вратете 2, и така натаму.

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
[Студентски одговор, неразбирливо] Океј, па ние би можеле да имаат друга димензија.

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
[Студентски одговор, неразбирливо] Во ред. Значи, ние би можеле да се движат сите други надолу,

658
00:39:58,610 --> 00:40:03,040
како Чарли nudges надолу Боб и Алис, а потоа ќе стави Анита каде што таа навистина сака да биде.

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
Тоа е О (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
тоа е рамномерно распределени во текот на еден преку З

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
Па веројатноста во прашање во моментов е само 1.

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
И оваа графичка тука има на x оската на бројот на родендени,

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
веројатноста од 2 луѓе кои имаат роденден е супер, супер висока, речиси 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
Ви се случува да имаат судири. Значи ова сфаќање на hashing, како што се вика,

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, Боб е во 1, Чарли е во 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
Линеарна затоа што ти си само одење оваа линија, а ти си вид на љубопитство

759
00:45:41,310 --> 00:45:43,640
за достапни места во податочна структура.

760
00:45:43,640 --> 00:45:46,210
Се разбира, ова devolves во О (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
Alice оди на почетокот на таа врска листата.

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]. OOP. Алис е веќе во кој поврзани листа.

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
Што ако подоцна сакате да го најдете Alice?

806
00:48:28,510 --> 00:48:31,050
Што ако подоцна сакате да го најдете Alice?

807
00:48:31,050 --> 00:48:35,690
Колку чекори се што се случува да се земе?

808
00:48:35,690 --> 00:48:37,850
[Студентски одговор, неразбирливо]

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
Значи, навистина, тогаш, вметнување време конечно е О (n), каде n е бројот на елементи во листата.

819
00:49:14,270 --> 00:49:21,780
Поделено со, нека произволно го нарекуваат м, каде 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
е доста О (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
ние сме биле велејќи О (n ²). О (n), 2 x n ², - 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
Што сакам да се стави ако сакате да го зачувате "Алиса", "Боб", "Чарли"?

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
и 1 е за што? Тоа е само екстра 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
Може да биде NULL, но не мора нужно да биде.

878
00:52:36,700 --> 00:52:40,110
Било какви прашања во врска со овие хаш маси? Да?

879
00:52:40,110 --> 00:52:46,190
[Студентски прашува прашање, неразбирливо] Низа - добро прашање.

880
00:52:46,190 --> 00:52:50,120
Зошто е ова знак збор во низа, а не само char *?

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
е која било од мали деца или grandkids на рабовите

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
[Студентски одговор, неразбирливо]

921
00:55:08,350 --> 00:55:12,040
Совршена. Ако се загледувам во ова, можете да го видите мал број на левата страна,

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
Значи забележите тука, ти си вид на концептуално сечкање дрвото на половина

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
и всушност, traversing структура вака - Whoops.

941
00:56:19,420 --> 00:56:22,870
Traversing структура како оваа, каде што тоа е само "одат овој начин или да одат на тој начин"

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
кој не му е изречена повторно пробајте-вредност, но тоа е она што светот го нарекува овие работи. Се обидува. Т-R-i-e.

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
како А-л-и-в-е или Б-о-б.

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
ние започнуваме на root јазол кој изгледа како низа,

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 и T, но во овој случај,

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
Па, како помина на авторот продавница М-на-x-w-е-л-л?

974
00:58:29,570 --> 00:58:36,990
Тој или таа започна на root јазол, и отиде во [М], па околу 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
Покажувачот кој претставува М, тогаш покажувачот што претставува,

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
не е во дрво, бидејќи ако почнам на root јазол се тука на врвот,

1001
01:00:07,970 --> 01:00:14,030
Нема ѓ покажувач, без покажувачот o, без покажувачот о. Foo не е име во овој речник.

1002
01:00:14,030 --> 01:00:22,460
Но, од друга страна, Тјуринг, т-у-р-и-н-г. Повторно, јас не чувајте т или u или r или јас или n или е.

1003
01:00:22,460 --> 01:00:29,820
Но јас не продавница во оваа податочна структура вредност на вистинскиот пат овде во овој јазол - во дрво

1004
01:00:29,820 --> 01:00:33,030
поставете ја оваа логичка вредност на is_word на true.

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
И наоѓање една од овие зборови по азбучен ред може да потрае О (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
Па, тоа е само 5, можеби 6 чекори за коса карактер.

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
не се во вашиот начин на наоѓање на Alice на сите,

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
Значи, да го наречеме k, каде k е максималната должина на зборот на англиски јазик

1029
01:02:11,560 --> 01:02:14,050
која е обично не повеќе од 20-нешто карактери.

1030
01:02:14,050 --> 01:02:17,940
So k е константа. Значи Светиот Грал ни изгледа да се најде сега

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
Значи она што цена сме ние плаќаат за да се постигне оваа величина тука? Простор.

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 или Пајтон или Руби или 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
денес дека ние ги користиме на Харвард курсеви, за текот шопинг алатка која мапи користи

1086
01:05:44,380 --> 01:05:48,660
да ви даде еден куп на динамизам, Фејсбук ти дава да се покаже инстант ажурирање на статусот,

1087
01:05:48,660 --> 01:05:51,430
Твитер го користи за да ви покаже твитови веднаш.

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
>> [♫ бавна хор музика ♫]

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
Тој дојде во светот на кул firewalls, незасегнатата рутери,

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
[Malan] Следната недела, тогаш. Интернет. Веб програмирање. Ова е CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]