1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Tydzień 6, ciąg dalszy]

2
00:00:02,520 --> 00:00:04,160
[David J. Malan] [Harvard University]

3
00:00:04,160 --> 00:00:08,720
[To jest CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
To, co jest CS50 koniec 6 tygodnia.

5
00:00:12,970 --> 00:00:17,970
Więc CS50x, jeden z kursów 1-ci Harvardu zaangażowanych w inicjatywy EDX

6
00:00:17,970 --> 00:00:20,590
rzeczywiście zadebiutował ten miniony poniedziałek.

7
00:00:20,590 --> 00:00:23,460
Jeśli chcieliby Państwo uzyskać wgląd w to, co inni w Internecie

8
00:00:23,460 --> 00:00:27,180
teraz stosując się, możesz udać się do x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Który przekieruje Cię do odpowiedniego miejsca na edx.org,

10
00:00:30,350 --> 00:00:34,160
co było, gdzie to i inne kursy z MIT i Berkeley teraz żyć.

11
00:00:34,160 --> 00:00:38,140
Musisz zarejestrować się na konto, przekonasz się, że materiał jest w dużym stopniu same

12
00:00:38,140 --> 00:00:42,170
jak miałem w tym semestrze, choć kilka tygodni opóźnione, ponieważ mamy wszystko gotowe.

13
00:00:42,170 --> 00:00:46,930
Ale to, co uczniowie w CS50x będzie teraz zobaczyć, to interfejs bardzo podobny do tego.

14
00:00:46,930 --> 00:00:50,040
To, na przykład, jest Zamyla prowadząc solucję do zbioru problemowego 0.

15
00:00:50,040 --> 00:00:54,230
Po zalogowaniu się do edx.org, CS50x uczeń widzi różne rzeczy

16
00:00:54,230 --> 00:00:57,170
można oczekiwać, aby zobaczyć w przedmiotu: wykład dla poniedziałku,

17
00:00:57,170 --> 00:01:01,650
Wykład na środę, różne spodenkami, zestawy problem, solucje, pliki PDF.

18
00:01:01,650 --> 00:01:04,459
Ponadto, jak można zobaczyć tutaj, tłumaczenia maszynowe

19
00:01:04,459 --> 00:01:08,390
angielskich transkrypcji na język chiński, japoński, hiszpański, włoski,

20
00:01:08,390 --> 00:01:12,810
i cała masa innych języków, które z pewnością będą niedoskonałe

21
00:01:12,810 --> 00:01:15,840
jak rzucić je programowo przy użyciu coś, co nazywa API,

22
00:01:15,840 --> 00:01:18,360
lub interfejs programowania aplikacji, od Google

23
00:01:18,360 --> 00:01:21,360
która pozwala nam konwertować polski do tych innych językach.

24
00:01:21,360 --> 00:01:24,100
Ale dzięki wspaniałym duchu niektórych ochotników sto-Plus,

25
00:01:24,100 --> 00:01:26,940
przypadkowych ludzi w Internecie, którzy uprzejmie oferowane do angażowania

26
00:01:26,940 --> 00:01:30,180
w ramach tego projektu, będziemy stopniowo ulegać poprawie jakości tych tłumaczeń

27
00:01:30,180 --> 00:01:35,790
poprzez ludzi naprawić błędy, że nasze komputery wykonane.

28
00:01:35,790 --> 00:01:42,330
>> Tak więc okazuje się, że mieliśmy kilka więcej studentów pokazać się w poniedziałek, niż początkowo oczekiwano.

29
00:01:42,330 --> 00:01:48,980
W rzeczywistości, teraz ma 100.000 ludzi CS50x następujące razem w domu.

30
00:01:48,980 --> 00:01:54,430
Więc sobie sprawę, że są częścią tego inauguracyjny klasa co ten kurs w informatyce

31
00:01:54,430 --> 00:01:57,370
edukacja bardziej ogólnie, szerzej dostępne.

32
00:01:57,370 --> 00:02:00,130
A rzeczywistość jest teraz, a niektóre z tych masowych kursów online,

33
00:02:00,130 --> 00:02:04,070
wszyscy zaczynają się tych liczb bardzo dużych, jak wydaje się, że skończyliśmy.

34
00:02:04,070 --> 00:02:08,759
Ale cel ostatecznie, CS50x jest naprawdę, aby uzyskać jak wielu ludzi do mety jak to możliwe.

35
00:02:08,759 --> 00:02:12,000
Zgodnie z projektem, CS50x ma być oferowane z tym ostatnim poniedziałek

36
00:02:12,000 --> 00:02:17,430
przez całą drogę 15 kwietnia 2013, tak, że ludzie, którzy mają zobowiązania szkoły w innym miejscu,

37
00:02:17,430 --> 00:02:20,990
praca, rodzina, inne konflikty i podobne, mają nieco większą elastyczność

38
00:02:20,990 --> 00:02:23,640
z którym do nurkowania w tym kursie, co wystarczy powiedzieć,

39
00:02:23,640 --> 00:02:30,540
jest dość ambitnie zrobić, jeśli tylko w ciągu zaledwie trzech miesięcy w trakcie zwykłego semestru.

40
00:02:30,540 --> 00:02:34,190
Ale te studenci będą walki te same zestawy problemowe, sprawdzające tę samą treść,

41
00:02:34,190 --> 00:02:36,350
dostępu do tych samych, jak spodenki i.

42
00:02:36,350 --> 00:02:38,990
Więc sobie sprawę, że tak naprawdę wszyscy jesteśmy w tym razem.

43
00:02:38,990 --> 00:02:42,360
A jednym z celów końcowych CS50x jest nie tylko, aby jak najwięcej ludzi

44
00:02:42,360 --> 00:02:45,720
do mety i dać im w szał zrozumienie informatyki

45
00:02:45,720 --> 00:02:49,000
i programowania, ale także, aby je mieć to wspólne doświadczenie.

46
00:02:49,000 --> 00:02:52,010
Jedną z cech charakterystycznych 50 na terenie kampusu, mamy nadzieję,

47
00:02:52,010 --> 00:02:56,260
było to coś w rodzaju wspólnym doświadczeniem, na lepsze lub gorsze, czasami,

48
00:02:56,260 --> 00:02:59,480
ale o tych ludzi, aby włączyć się w lewo i prawo,

49
00:02:59,480 --> 00:03:01,830
i godziny biurowe i hackathon i uczciwe.

50
00:03:01,830 --> 00:03:04,560
Jest to trochę trudniejsze, że osoby z ludzi online,

51
00:03:04,560 --> 00:03:10,580
ale CS50x zakończy się w kwietniu z pierwszego w historii CS50 Expo

52
00:03:10,580 --> 00:03:13,630
który będzie online na dostosowanie naszej idei fair

53
00:03:13,630 --> 00:03:18,250
gdzie te tysiące studentów będzie być zaproszeni do złożenia 1 - do 2-minutowego filmu,

54
00:03:18,250 --> 00:03:22,480
albo screencast ich ostatecznego projektu lub wideo z nich macha komentarzy

55
00:03:22,480 --> 00:03:24,490
i mówić o ich projektu i demoing go,

56
00:03:24,490 --> 00:03:27,610
podobnie jak waszych poprzedników zrobić tutaj na kampusie w targach,

57
00:03:27,610 --> 00:03:31,400
tak, że przez koniec semestru, jest nadzieja na uzyskanie globalnego wystawę

58
00:03:31,400 --> 00:03:37,080
końcowych przez CS50x studenckich projektów, podobnie jak to, co czeka Cię w grudniu tego roku tu, na terenie kampusu.

59
00:03:37,080 --> 00:03:39,680
Więc więcej o tym w najbliższych miesiącach.

60
00:03:39,680 --> 00:03:43,640
>> Z 100.000 studentów, choć przychodzi konieczność kilku urzędów więcej.

61
00:03:43,640 --> 00:03:47,590
Biorąc pod uwagę, że chłopaki są płonący ślad tutaj i biorąc CS50

62
00:03:47,590 --> 00:03:51,630
kilka tygodni przed premierą tego materiału dla ludzi na EDX,

63
00:03:51,630 --> 00:03:55,330
zrealizować chcielibyśmy zaangażować jak wielu naszych studentów, jak to możliwe w tej inicjatywie,

64
00:03:55,330 --> 00:03:58,720
zarówno w trakcie semestru, jak i tej zimy i wiosną tego roku nadchodzi.

65
00:03:58,720 --> 00:04:01,620
Więc jeśli chcesz się zaangażować w CS50x,

66
00:04:01,620 --> 00:04:07,450
szczególnie łączącą w sprawie CS50x dyskutować, Wersja EDX z CS50 dyskutować,

67
00:04:07,450 --> 00:04:10,140
które wielu z was używał na kampusie, online tablicy ogłoszeń,

68
00:04:10,140 --> 00:04:13,040
proszę głowa do tego adresu URL, daj nam znać, kim jesteś,

69
00:04:13,040 --> 00:04:16,450
bo chcielibyśmy budować zespół studentów i pracowników i wykładowców zarówno

70
00:04:16,450 --> 00:04:19,630
na uczelni, którzy są po prostu grać dalej i pomagać.

71
00:04:19,630 --> 00:04:21,720
A gdy zobaczysz pytanie, jest im bliskie,

72
00:04:21,720 --> 00:04:25,320
usłyszysz studenta raportowania jakiś błąd gdzieś tam w jakimś kraju w Internecie,

73
00:04:25,320 --> 00:04:27,450
i że pierścienie dzwon, bo też miałem ten sam problem

74
00:04:27,450 --> 00:04:32,620
w d-sali jakiś czas temu, mam nadzieję, że wtedy można dostroić się i podziel się swoim doświadczeniem.

75
00:04:32,620 --> 00:04:37,300
Więc proszę wziąć udział, jeśli chcesz.

76
00:04:37,300 --> 00:04:39,360
>> Kursy informatyki na Harvardzie mieć trochę tradycji,

77
00:04:39,360 --> 00:04:44,730
CS50 wśród nich, z konieczności trochę odzieży, niektóre ubrania, które można nosić z dumą

78
00:04:44,730 --> 00:04:49,090
na koniec semestru, mówiąc dość dumnie, że skończyłeś CS50

79
00:04:49,090 --> 00:04:51,830
i wziął CS50 i tym podobne, i zawsze staramy się zaangażować uczniów

80
00:04:51,830 --> 00:04:54,540
w tym procesie, jak najwięcej, w którym możemy zaprosić,

81
00:04:54,540 --> 00:04:56,900
W tym czasie w semestrze, studenci do składania projektów

82
00:04:56,900 --> 00:04:59,330
użyciu Photoshopa, czy cokolwiek narzędziem wyboru chcesz używać

83
00:04:59,330 --> 00:05:02,330
jeśli jesteś projektantem, przedłożyć projekty na T-shirty i bluzy

84
00:05:02,330 --> 00:05:06,100
i parasole i małe bandany dla psów mamy i tym podobne.

85
00:05:06,100 --> 00:05:09,370
I wszystko jest wtedy - zwycięzcy każdego roku są następnie wystawiane

86
00:05:09,370 --> 00:05:12,700
na kursie na stronie internetowej store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Wszystko jest sprzedawane w cenie tam, ale na stronie internetowej po prostu uruchamia się

88
00:05:15,790 --> 00:05:18,330
i pozwala ludziom wybór kolorów i wzorów, które im się podobają.

89
00:05:18,330 --> 00:05:20,420
Więc pomyślałem, że po prostu podzielić się z zeszłorocznych projektów

90
00:05:20,420 --> 00:05:25,130
które były na stronie internetowej poza tym tutaj, który jest coroczną tradycją.

91
00:05:25,130 --> 00:05:29,410
"Każdego dnia jestem Seg Faultn" był jednym z udzielonych w ubiegłym roku,

92
00:05:29,410 --> 00:05:32,290
która jest nadal dostępna jest dla absolwentów.

93
00:05:32,290 --> 00:05:35,820
Mieliśmy ten jeden, "CS50, założona 1989."

94
00:05:35,820 --> 00:05:39,010
Jeden z naszych Bowdens, Rob, był bardzo popularny w zeszłym roku.

95
00:05:39,010 --> 00:05:43,480
"Team Bowden" urodził się, aby ten projekt został przedłożony wśród najlepszych sprzedawców.

96
00:05:43,480 --> 00:05:49,040
Jak to było tu nikogo. Wielu ludzi ma "Fever Bowdena" Według sprzedaży dzienników.

97
00:05:49,040 --> 00:05:52,650
Sobie sprawę, że może być teraz Twój projekt tam się w Internecie.

98
00:05:52,650 --> 00:05:57,510
Więcej szczegółów na ten temat w następnym problemu ustawia przyjść.

99
00:05:57,510 --> 00:06:00,330
>> Jeszcze jedno narzędzie: miałeś kilka ekspozycji i mam nadzieję teraz

100
00:06:00,330 --> 00:06:02,350
pewne praktyczne doświadczenie z GDB,

101
00:06:02,350 --> 00:06:04,570
co, oczywiście, debugger i pozwala manipulować

102
00:06:04,570 --> 00:06:09,500
Twój program na poziomie dość niskim poziomie, co robi różne rzeczy?

103
00:06:09,500 --> 00:06:13,030
Co GDB pozwala zrobić?

104
00:06:13,030 --> 00:06:15,030
Tak? Daj mi coś. [Odpowiedź Student, niezrozumiały]

105
00:06:15,030 --> 00:06:18,120
Good. Krok do funkcji, więc nie wystarczy wpisać słowo

106
00:06:18,120 --> 00:06:22,310
i mieć cios programu dzięki całości, drukowanie rzeczy do standardowego wyjścia.

107
00:06:22,310 --> 00:06:25,190
Przeciwnie, można wejść przez to linia po linii, albo wpisując obok

108
00:06:25,190 --> 00:06:30,300
iść linia po linii po linii lub stopniu do nurkowania w funkcji, zazwyczaj jeden, który napisał.

109
00:06:30,300 --> 00:06:35,240
Co jeszcze robi GDB pozwala zrobić? Tak? [Odpowiedź Student, niezrozumiały]

110
00:06:35,240 --> 00:06:38,100
Wydrukuj zmienne. Więc jeśli chcesz zrobić trochę introspekcji wewnątrz programu

111
00:06:38,100 --> 00:06:41,500
bez konieczności uciekania się do pisania printf na miejsce,

112
00:06:41,500 --> 00:06:44,600
można po prostu wydrukować zmiennej lub wyświetlić zmienną.

113
00:06:44,600 --> 00:06:46,710
Co jeszcze można zrobić z debugera jak GDB?

114
00:06:46,710 --> 00:06:49,170
[Odpowiedź Student, niezrozumiały]

115
00:06:49,170 --> 00:06:52,080
Dokładnie. Możesz ustawić punkty przerwania, można powiedzieć, wykonanie przerwy

116
00:06:52,080 --> 00:06:54,020
w głównej funkcji lub funkcji foo.

117
00:06:54,020 --> 00:06:56,800
Można powiedzieć, że wykonanie przerwy w linii 123.

118
00:06:56,800 --> 00:06:58,950
I pułapki są naprawdę potężna technika

119
00:06:58,950 --> 00:07:01,110
bo jeśli masz ogólne poczucie, gdzie Twój problem

120
00:07:01,110 --> 00:07:05,360
zapewne, nie trzeba tracić czasu na przejście przez programu całości.

121
00:07:05,360 --> 00:07:08,250
Można zasadniczo wskoczyć tam i wtedy zacznij pisać -

122
00:07:08,250 --> 00:07:10,970
przejście przez niego lub następnego kroku lub podobne.

123
00:07:10,970 --> 00:07:14,340
Ale jest haczyk z czymś GDB jest to, że pomaga, człowiek,

124
00:07:14,340 --> 00:07:16,940
odnaleźć swoje problemy i znaleźć błędy.

125
00:07:16,940 --> 00:07:19,470
To nie koniecznie znaleźć ich tak wiele dla Ciebie.

126
00:07:19,470 --> 00:07:23,070
>> Więc wprowadzono inne style50 dzień, który jest krótki narzędziem wiersza poleceń

127
00:07:23,070 --> 00:07:27,500
który stara się stylizować kod trochę bardziej czysty niż ty, człowiek, może mieć zrobione.

128
00:07:27,500 --> 00:07:29,530
Ale to też jest naprawdę estetyczne rzeczą.

129
00:07:29,530 --> 00:07:34,110
Ale okazuje się, że to jest inne narzędzie nazywa Valgrind, że jest trochę bardziej złożoną w użyciu.

130
00:07:34,110 --> 00:07:36,860
Jego produkcja jest potwornie cryptic na pierwszy rzut oka.

131
00:07:36,860 --> 00:07:39,420
Ale to cudownie przydatne, zwłaszcza teraz, kiedy jesteśmy w części kadencji

132
00:07:39,420 --> 00:07:43,080
gdy zaczynasz używać malloc i dynamicznej alokacji pamięci.

133
00:07:43,080 --> 00:07:45,420
Rzeczy może pójść nie tak naprawdę, naprawdę źle szybko.

134
00:07:45,420 --> 00:07:49,320
Bo jeśli zapomnimy zwolnić pamięć, lub nieprawidłowego trochę wskaźniku NULL,

135
00:07:49,320 --> 00:07:55,770
lub nieprawidłowego jakiś wskaźnik śmieci, co jest zazwyczaj objawem, że wyniki?

136
00:07:55,770 --> 00:07:59,470
Seg winy. I masz ten plik rdzenia pewnej liczby kilobajtach lub megabajtach

137
00:07:59,470 --> 00:08:02,990
który reprezentuje stan pamięci Twojego programu, kiedy rozbił się,

138
00:08:02,990 --> 00:08:05,730
ale twój program ostatecznie seg wady, winy segmentacji,

139
00:08:05,730 --> 00:08:08,450
co oznacza, że ​​coś złego się stało niemal zawsze związane

140
00:08:08,450 --> 00:08:11,750
do pamięci związanych pomyłkę, że dokonane gdzieś.

141
00:08:11,750 --> 00:08:14,100
Więc Valgrind pomaga znaleźć takie rzeczy.

142
00:08:14,100 --> 00:08:17,720
Jest to narzędzie, które można uruchomić, jak GDB, kiedy już skompilowany program,

143
00:08:17,720 --> 00:08:20,330
ale zamiast uruchomić program bezpośrednio, uruchomić Valgrind

144
00:08:20,330 --> 00:08:23,960
i do niej przekazywać swój program, tak jak robisz z GDB.

145
00:08:23,960 --> 00:08:26,220
Teraz, użytkowania, aby uzyskać najlepszy rodzaj produkcji,

146
00:08:26,220 --> 00:08:30,410
jest trochę długi, więc tam na szczycie ekranu zobaczysz Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" niemal powszechnie oznacza verbose gdy używasz programów na komputerze z systemem Linux.

148
00:08:35,350 --> 00:08:38,770
Więc oznacza to wypluć więcej danych niż możesz być domyślnie.

149
00:08:38,770 --> 00:08:45,510
"- Wyciek-check = full." To jest po prostu mówiąc czek na wszystkich możliwych wycieków pamięci,

150
00:08:45,510 --> 00:08:49,430
błędy, które mógłbym wykonane. To też jest wspólny paradygmat z programami Linux.

151
00:08:49,430 --> 00:08:52,710
Generalnie, jeśli masz argument wiersza polecenia to "switch",

152
00:08:52,710 --> 00:08:55,830
, który powinien zmienić program zachowania, a to jedna litera,

153
00:08:55,830 --> 00:09:00,310
to-v, ale jeśli jest to włączone, po prostu projekt programatora,

154
00:09:00,310 --> 00:09:05,150
jest pełne słowo lub szereg słów, argument linii poleceń zaczyna się od -.

155
00:09:05,150 --> 00:09:08,190
Są to tylko ludzkie konwencje, ale zobaczysz je coraz bardziej.

156
00:09:08,190 --> 00:09:12,410
, A następnie, na koniec, "a.out" jest dowolną nazwę programu w tym konkretnym przykładzie.

157
00:09:12,410 --> 00:09:14,640
A tu jakiś przedstawiciel wyjście.

158
00:09:14,640 --> 00:09:22,890
>> Zanim przyjrzymy się, co to może oznaczać, pozwól mi przejść do fragmentu kodu tutaj.

159
00:09:22,890 --> 00:09:26,390
I pozwól mi przenieść ten z drogi, wkrótce,

160
00:09:26,390 --> 00:09:32,120
i rzućmy okiem na memory.c, co jest to krótki przykład tutaj.

161
00:09:32,120 --> 00:09:36,290
Więc w tym programie, pozwól mi przybliżyć funkcje i pytania.

162
00:09:36,290 --> 00:09:39,430
Mamy funkcję głównego, który wywołuje funkcję, F,

163
00:09:39,430 --> 00:09:45,590
i co ma zrobić, przejdź do f, w języku angielskim nieco techniczną?

164
00:09:45,590 --> 00:09:49,760
Co f postępować zrobić?

165
00:09:49,760 --> 00:09:53,680
Jak o Zacznę linii 20, a gwiazda jest lokalizacja nie ma znaczenia,

166
00:09:53,680 --> 00:09:56,720
ale ja po prostu być zgodne tu z ostatniego wykładu.

167
00:09:56,720 --> 00:09:59,910
Co znajduje się linia 20 nie dla nas? Na lewej stronie. Będziemy rozbicie go dalej.

168
00:09:59,910 --> 00:10:02,410
Int * x: co to robić?

169
00:10:02,410 --> 00:10:04,940
Okay. To stwierdzenie jest wskaźnik, a teraz niech się jeszcze bardziej techniczny.

170
00:10:04,940 --> 00:10:10,230
Co to znaczy, bardzo konkretnie, aby zadeklarować wskaźnik? Ktoś jeszcze?

171
00:10:10,230 --> 00:10:15,050
Tak? [Odpowiedź Student, niezrozumiały] za daleko.

172
00:10:15,050 --> 00:10:17,060
Więc czytasz na prawej stronie znaku równości.

173
00:10:17,060 --> 00:10:20,290
Skupmy się tylko na lewo, tylko na int * x.

174
00:10:20,290 --> 00:10:24,700
To nie "deklarują" wskaźnik, ale teraz niech nurkować głębiej do tej definicji.

175
00:10:24,700 --> 00:10:28,330
Co to konkretnie, technicznie oznacza? Tak?

176
00:10:28,330 --> 00:10:31,940
[Odpowiedź Student, niezrozumiały]

177
00:10:31,940 --> 00:10:35,090
Okay. Jest to przygotowanie do zapisania adresu w pamięci.

178
00:10:35,090 --> 00:10:40,680
Good. I zróbmy krok dalej, to deklarowanie zmiennej, x, to jest 32 bitów.

179
00:10:40,680 --> 00:10:44,440
I wiem, że to jest 32 bitów, ponieważ -

180
00:10:44,440 --> 00:10:47,390
To nie dlatego, że to int, ponieważ jest to wskaźnik w tym przypadku.

181
00:10:47,390 --> 00:10:49,650
Zbieg okoliczności, że to jedno i to samo z int,

182
00:10:49,650 --> 00:10:51,970
ale fakt, że jest gwiazdą nie oznacza, że ​​jest to wskaźnik

183
00:10:51,970 --> 00:10:57,300
i urządzenia, jak w wielu komputerach, ale nie wszystkie, wskaźniki są 32 bity.

184
00:10:57,300 --> 00:11:01,850
Na więcej nowoczesnego sprzętu, jak najnowsze komputery Mac, komputery najnowsze, może być 64-bitowych,

185
00:11:01,850 --> 00:11:04,160
ale w urządzeniu, te rzeczy są 32 bity.

186
00:11:04,160 --> 00:11:08,380
Będziemy więc ujednolicić tego. Bardziej konkretnie, historia wygląda następująco:

187
00:11:08,380 --> 00:11:10,820
We "deklarują" wskaźnik, co to oznacza?

188
00:11:10,820 --> 00:11:12,810
Przygotowujemy do przechowywania adresu pamięci.

189
00:11:12,810 --> 00:11:15,530
Co to znaczy?

190
00:11:15,530 --> 00:11:19,810
Tworzymy zmienną o nazwie x, która zajmuje 32 bity

191
00:11:19,810 --> 00:11:23,810
które wkrótce zapisać adres całkowitej.

192
00:11:23,810 --> 00:11:26,470
I to jest prawdopodobnie tak precyzyjny, jak możemy.

193
00:11:26,470 --> 00:11:31,810
Jest dobrze naprzód uprościć świat i po prostu powiedzieć zadeklarować wskaźnik o nazwie x.

194
00:11:31,810 --> 00:11:35,380
Deklaracja wskaźnika, ale uświadomić sobie i zrozumieć, co się dzieje

195
00:11:35,380 --> 00:11:38,490
nawet w ciągu zaledwie kilku tych znaków.

196
00:11:38,490 --> 00:11:42,040
>> Teraz, ten jest prawie trochę łatwiej, choć to już wyraz.

197
00:11:42,040 --> 00:11:48,160
Więc co to robi, że jest podświetlona teraz: "malloc (10 * sizeof (int));" Tak?

198
00:11:48,160 --> 00:11:52,350
[Odpowiedź Student, niezrozumiały]

199
00:11:52,350 --> 00:11:58,250
Good. A ja wezmę go tam. To przydzielenie kawałek pamięci dziesięciu liczb całkowitych.

200
00:11:58,250 --> 00:12:02,190
A teraz zanurkować nieco głębiej, to przydzielenie kawałek pamięci dziesięciu liczb całkowitych.

201
00:12:02,190 --> 00:12:05,390
Co to jest malloc następnie powrót?

202
00:12:05,390 --> 00:12:10,390
Adres tego kawałka, lub, bardziej konkretnie, adres pierwszego bajtu tym kawałku.

203
00:12:10,390 --> 00:12:14,080
Jak więc jestem, programista, aby wiedzieć, gdzie kończy się, że fragment pamięci?

204
00:12:14,080 --> 00:12:18,340
Wiem, że to jest ciągłe. Malloc, z definicji, daje ciągły fragment pamięci.

205
00:12:18,340 --> 00:12:21,240
Żadnych przerw w nim. Masz dostęp do każdego bajtu w tym kawałku,

206
00:12:21,240 --> 00:12:26,760
z powrotem do tyłu do tyłu, ale skąd mam wiedzieć, gdzie koniec tego kawałka pamięci jest?

207
00:12:26,760 --> 00:12:28,850
Podczas korzystania z funkcji malloc? [Odpowiedź Student, niezrozumiały] Dobra.

208
00:12:28,850 --> 00:12:30,670
Nie masz. Musisz pamiętać.

209
00:12:30,670 --> 00:12:35,960
I trzeba pamiętać, że użyłem wartości 10, a ja nawet nie wydają się tego robić tutaj.

210
00:12:35,960 --> 00:12:41,000
Ale spoczywa wyłącznie na mnie. Strlen, którego staliśmy się nieco zależne od ciągów,

211
00:12:41,000 --> 00:12:45,860
działa tylko z powodu tej konwencji o \ 0

212
00:12:45,860 --> 00:12:48,840
czy ta specjalna nul charakter, NUL, na końcu łańcucha.

213
00:12:48,840 --> 00:12:51,740
Że nie posiada za zaledwie dowolnych fragmentów pamięci.

214
00:12:51,740 --> 00:12:58,590
To zależy od Ciebie. Tak linii 20, a następnie, przydziela ilość pamięci

215
00:12:58,590 --> 00:13:02,590
, który może przechowywać dziesięć liczby całkowite, i zapisuje się adres pierwszego bajtu

216
00:13:02,590 --> 00:13:05,610
tego fragmentu pamięci w zmiennej x wywołana.

217
00:13:05,610 --> 00:13:11,140
Ergo, które jest wskaźnik. Więc linii 21, niestety, było błędem.

218
00:13:11,140 --> 00:13:16,110
Ale najpierw, co on robi? To mówiąc, sklep na miejscu 10, 0 indeksowane,

219
00:13:16,110 --> 00:13:19,480
z kawałka pamięci o nazwie x 0 wartość.

220
00:13:19,480 --> 00:13:21,510
>> Więc zauważyć kilka rzeczy są dzieje.

221
00:13:21,510 --> 00:13:25,420
Nawet jeśli x jest wskaźnik, wycofanie się z kilka tygodni temu

222
00:13:25,420 --> 00:13:29,440
że można jeszcze użyć tablicy stylu notacji nawias prostokątny.

223
00:13:29,440 --> 00:13:36,180
Bo to rzeczywiście krótki ręka notacja dla bardziej tajemnicze wyglądającej arytmetycznej wskaźnika.

224
00:13:36,180 --> 00:13:40,320
gdzie chcemy zrobić coś takiego: Weź x adresowej, przenieść 10 punktów nad,

225
00:13:40,320 --> 00:13:44,550
następnie przejść do tego, co tam jest adres zapisany w tej lokalizacji.

226
00:13:44,550 --> 00:13:48,090
Ale szczerze mówiąc, to jest po prostu okropne czytać i dostać się komfortowo.

227
00:13:48,090 --> 00:13:52,900
Więc świat zazwyczaj wykorzystuje nawiasy kwadratowe tylko dlatego, że jest o wiele bardziej przyjazny dla ludzi do czytania.

228
00:13:52,900 --> 00:13:55,140
Ale to, co naprawdę dzieje się pod maską;

229
00:13:55,140 --> 00:13:58,190
x to adres nie, tablica, per se.

230
00:13:58,190 --> 00:14:02,410
Więc to jest przechowywanie 0 w miejscu 10 w x.

231
00:14:02,410 --> 00:14:06,120
Dlaczego to jest złe? Tak?

232
00:14:06,120 --> 00:14:17,370
[Odpowiedź Student, niezrozumiały] Dokładnie.

233
00:14:17,370 --> 00:14:21,100
Mamy tylko przydzielone dziesięć wskazówki, ale liczymy od 0 przy programowaniu w C,

234
00:14:21,100 --> 00:14:25,690
aby mieć dostęp do 0 1 2 3 4 5 6 7 8 9, 10, lecz nie.

235
00:14:25,690 --> 00:14:30,270
Więc albo program będzie seg winy lub nie.

236
00:14:30,270 --> 00:14:32,900
Ale naprawdę nie wiem, to jest coś w rodzaju niedeterministycznych zachowania.

237
00:14:32,900 --> 00:14:35,600
To naprawdę zależy od tego, czy nam się poszczęści.

238
00:14:35,600 --> 00:14:40,650
Jeśli okaże się, że system operacyjny nie ma nic przeciwko, jeśli mogę użyć tego dodatkowy bajt,

239
00:14:40,650 --> 00:14:43,360
mimo, że nie dał mi to, mój program nie może upaść.

240
00:14:43,360 --> 00:14:46,780
To surowe, wadliwa, ale nie może zobaczyć, że objaw,

241
00:14:46,780 --> 00:14:48,960
lub można go zobaczyć tylko raz na jakiś czas.

242
00:14:48,960 --> 00:14:51,230
Rzeczywistość jest jednak, że błąd jest w rzeczywistości, tam.

243
00:14:51,230 --> 00:14:54,320
I to jest naprawdę kłopotliwe, jeśli napisałeś program, który ma być poprawne,

244
00:14:54,320 --> 00:14:58,840
, które zostały sprzedane program, ludzie korzystają, że każdy raz na jakiś czas wywala

245
00:14:58,840 --> 00:15:02,450
, ponieważ, oczywiście, nie jest dobry. W rzeczywistości, jeśli masz telefon z systemem Android lub iPhone

246
00:15:02,450 --> 00:15:05,550
i pobrać aplikacje te dni, jeśli kiedykolwiek miał aplikacja po prostu zamknąć,

247
00:15:05,550 --> 00:15:10,040
nagle znika, to jest prawie zawsze wynikiem jakiegoś problemu związanego z pamięci,

248
00:15:10,040 --> 00:15:12,830
której programista spieprzył i dereferencjonowane wskaźnik

249
00:15:12,830 --> 00:15:18,670
, że on lub ona nie powinna mieć, a wynik iOS lub Android jest po prostu zabić program całkowicie

250
00:15:18,670 --> 00:15:23,080
zamiast ryzyka zachowanie niezdefiniowane lub jakiegoś kompromisu bezpieczeństwa.

251
00:15:23,080 --> 00:15:25,950
>> Jest jeszcze jeden błąd w programie, oprócz tej jednej.

252
00:15:25,950 --> 00:15:30,180
Co jeszcze schrzaniłem w tym programie?

253
00:15:30,180 --> 00:15:32,740
I już nie praktykuje tego, co już głosił. Tak?

254
00:15:32,740 --> 00:15:34,760
[Odpowiedź Student, niezrozumiały] Dobra.

255
00:15:34,760 --> 00:15:36,880
Nie uwalnia pamięć. Więc zasada teraz

256
00:15:36,880 --> 00:15:43,150
musi być w każdej chwili zadzwonić malloc, należy zadzwonić za darmo, kiedy są wykonywane przy użyciu tej pamięci.

257
00:15:43,150 --> 00:15:45,610
Teraz, kiedy chciałbym zwolnić tę pamięć?

258
00:15:45,610 --> 00:15:49,780
Prawdopodobnie, zakładając, że pierwsza linia była poprawna, chciałbym to zrobić tutaj.

259
00:15:49,780 --> 00:15:55,710
Bo nie może, na przykład, to zrobić tutaj. Dlaczego?

260
00:15:55,710 --> 00:15:57,860
Tylko z zakresu. Więc nawet jeśli mówimy o wskaźniki,

261
00:15:57,860 --> 00:16:04,830
jest to 2 lub 3 tygodni problem, gdzie x jest tylko w zakresie wewnątrz nawiasy, gdzie została zadeklarowana.

262
00:16:04,830 --> 00:16:11,000
Więc na pewno nie może uwolnić go tam. Moja jedyna szansa, aby uwolnić ją mniej więcej po linii 21.

263
00:16:11,000 --> 00:16:15,170
Jest to dość prosty program, to było dość proste, gdy rodzaj owinięty swój umysł

264
00:16:15,170 --> 00:16:17,870
wokół tego, co program robi, gdzie błędy były.

265
00:16:17,870 --> 00:16:20,500
I nawet jeśli nie widzimy na pierwszy, miejmy nadzieję, że to trochę oczywiste teraz

266
00:16:20,500 --> 00:16:23,870
że te błędy są dość łatwo rozwiązać i łatwo wykonane.

267
00:16:23,870 --> 00:16:28,720
Ale gdy program jest więcej niż 12 linijek, to 50 linijek, 100 linijek,

268
00:16:28,720 --> 00:16:31,150
chodzenie po linii kodu po linii, myśląc przez to logicznie,

269
00:16:31,150 --> 00:16:35,110
jest możliwe, ale nie jest szczególnie do zabawy, ciągle szuka błędów,

270
00:16:35,110 --> 00:16:38,340
i to także trudne, i dlatego narzędzia takie jak Valgrind istnieje.

271
00:16:38,340 --> 00:16:40,900
Pozwólcie mi iść do przodu i zrobić to: pozwól mi otworzyć okno terminala,

272
00:16:40,900 --> 00:16:45,400
i niech mi nie wystarczy uruchomić pamięć, bo pamięć wydaje się być w porządku.

273
00:16:45,400 --> 00:16:49,180
Dostaję szczęście. Tego dodatkowego będzie bajtu na koniec tablicy

274
00:16:49,180 --> 00:16:51,060
, nie wydaje się być zbyt skomplikowane.

275
00:16:51,060 --> 00:16:56,370
Ale niech mnie, mimo wszystko, zrobić test poczytalności co oznacza po prostu, aby sprawdzić

276
00:16:56,370 --> 00:16:58,320
, czy też nie jest to rzeczywiście prawidłowe.

277
00:16:58,320 --> 00:17:04,690
>> Więc zróbmy Valgrind-V - wyciek-check = full,

278
00:17:04,690 --> 00:17:07,520
a następnie nazwę programu w tym przypadku pamięć nie a.out.

279
00:17:07,520 --> 00:17:10,760
Więc pozwól mi iść do przodu i robić. Naciśnij klawisz Enter.

280
00:17:10,760 --> 00:17:14,109
Drogi Boże. To jest jego wyjście, i to, co wspomniałem wcześniej.

281
00:17:14,109 --> 00:17:17,550
Ale, jeśli uczą się czytać przez wszystkie bzdury tutaj

282
00:17:17,550 --> 00:17:20,760
większości jest to tylko wyjście diagnostyczne, które nie jest tak interesujące.

283
00:17:20,760 --> 00:17:24,829
Co twoje oko naprawdę chce się szukać jakakolwiek wzmianka błędu lub nieprawidłowych.

284
00:17:24,829 --> 00:17:26,800
Słowa, które sugerują problemy.

285
00:17:26,800 --> 00:17:29,340
I rzeczywiście, zobaczymy, co się dzieje źle tutaj.

286
00:17:29,340 --> 00:17:35,230
Mam podsumowanie pewnego rodzaju ", stosowany w wyjścia:. 40 bajtów 1 bloków"

287
00:17:35,230 --> 00:17:38,750
Nie jestem pewien, co blok to jeszcze, ale 40 bajtów

288
00:17:38,750 --> 00:17:41,260
faktycznie czuje się jak mogę dowiedzieć się, gdzie który jest pochodzi.

289
00:17:41,260 --> 00:17:45,030
40 bajtów. Dlaczego 40 bajtów wykorzystania na wyjeździe?

290
00:17:45,030 --> 00:17:48,780
A dokładniej, jeśli przewiń tutaj

291
00:17:48,780 --> 00:17:54,520
dlaczego na pewno stracił 40 bajtów? Tak?

292
00:17:54,520 --> 00:17:59,520
[Odpowiedź Student, niezrozumiały] Perfect. Tak, dokładnie.

293
00:17:59,520 --> 00:18:03,540
Było dziesięć liczbami całkowitymi, a każdy z nich jest wielkości 4 lub 32 bitów,

294
00:18:03,540 --> 00:18:08,300
tak straciłam dokładnie 40 bajtów, ponieważ, jak to zaproponował, nie nazywa się free.

295
00:18:08,300 --> 00:18:13,460
To jeden błąd, a teraz spójrzmy w dół nieco dalej i zobaczyć obok tego,

296
00:18:13,460 --> 00:18:16,900
"Nieprawidłowy zapis wielkości 4". Teraz to, co to jest?

297
00:18:16,900 --> 00:18:21,150
Adres ten jest wyrażony co notacji podstawowej, najwyraźniej?

298
00:18:21,150 --> 00:18:23,640
To jest szesnastkowy, a za każdym razem można zobaczyć numer zaczynający się od 0x,

299
00:18:23,640 --> 00:18:29,410
oznacza to, szesnastkowy, co zrobiliśmy w drodze powrotnej w, myślę, w sekcji Pset 0 pytań,

300
00:18:29,410 --> 00:18:34,090
co było po prostu zrobić ćwiczenia rozgrzewki, konwersja hex na dziesiętny na binarny i tak dalej.

301
00:18:34,090 --> 00:18:39,220
Szesnastkowy, tylko przez ludzi z konwencją, jest zwykle używany do reprezentowania wskaźników

302
00:18:39,220 --> 00:18:41,570
lub, bardziej ogólnie, adresów. To jest po prostu konwencja,

303
00:18:41,570 --> 00:18:45,340
bo to trochę łatwiejsze do odczytania, jest to trochę bardziej kompaktowy niż coś po przecinku,

304
00:18:45,340 --> 00:18:47,720
i binarne jest bezużyteczne dla większości ludzi, aby użyć.

305
00:18:47,720 --> 00:18:50,840
Więc teraz, co to znaczy? Cóż, wygląda na to, że znajduje się nieprawidłowy zapis

306
00:18:50,840 --> 00:18:54,480
wielkości 4 na linii 21 z memory.c.

307
00:18:54,480 --> 00:18:59,180
Więc wróćmy do linii 21, i rzeczywiście, jest to, że nieprawidłowy zapis.

308
00:18:59,180 --> 00:19:02,640
Więc Valgrind nie będzie całkowicie weź mnie za rękę i powiedz, co na to jest,

309
00:19:02,640 --> 00:19:05,520
ale wykrywa, że ​​robię nieprawidłowy zapis.

310
00:19:05,520 --> 00:19:08,800
Dotykam 4 bajty, że nie powinno być, a podobno to dlatego,

311
00:19:08,800 --> 00:19:13,960
jak pan zauważył, robię [10] zamiast [9] maksymalnie

312
00:19:13,960 --> 00:19:16,660
lub [0] lub coś pomiędzy.

313
00:19:16,660 --> 00:19:19,690
Z Valgrind, realizować czasu jesteś teraz pisze program

314
00:19:19,690 --> 00:19:24,190
wykorzystujący wskaźniki i wykorzystuje pamięć i malloc Dokładniej,

315
00:19:24,190 --> 00:19:27,080
na pewno dostać się do nawyku jazdy tak długo

316
00:19:27,080 --> 00:19:30,890
ale bardzo łatwo kopiować i wklejać dowództwo Valgrind

317
00:19:30,890 --> 00:19:32,650
aby sprawdzić, czy znajduje się kilka błędów w tam.

318
00:19:32,650 --> 00:19:34,820
I to będzie ogromna każdym zobaczyć wyjście,

319
00:19:34,820 --> 00:19:39,430
ale po prostu analizować przez wizualnie wszystkie wyjścia i zobacz czy widzisz wspomina błędów

320
00:19:39,430 --> 00:19:43,190
lub ostrzeżenia lub nieprawidłowe lub utracone.

321
00:19:43,190 --> 00:19:46,200
Wszelkie słowa, które brzmią jak ty skręcane gdzieś.

322
00:19:46,200 --> 00:19:48,580
Więc sobie sprawę, że jest to nowe narzędzie w zestawie narzędzi.

323
00:19:48,580 --> 00:19:51,270
>> Teraz w poniedziałek, mieliśmy całą masę ludzi przychodzą tu

324
00:19:51,270 --> 00:19:53,150
i reprezentują pojęcia połączonej listy.

325
00:19:53,150 --> 00:20:00,970
I wprowadził połączonej listy jako rozwiązanie do tego, co problem?

326
00:20:00,970 --> 00:20:04,590
Tak? [Odpowiedź Student, niezrozumiały] Dobra.

327
00:20:04,590 --> 00:20:06,530
Tablice nie są dodane do nich pamięci.

328
00:20:06,530 --> 00:20:09,440
Jeśli przydzielić tablicy rozmiaru 10, to wszystko masz.

329
00:20:09,440 --> 00:20:13,690
Możesz zadzwonić do funkcji takich jak realloc jeśli początkowo nazywany malloc,

330
00:20:13,690 --> 00:20:17,580
i można spróbować rosnąć tablicy jeśli jest miejsce pod koniec tego

331
00:20:17,580 --> 00:20:21,610
że nikt inny nie używa, a jeśli nie, to po prostu znaleźć ci większy kawałek gdzieś indziej.

332
00:20:21,610 --> 00:20:25,040
Ale to będzie skopiować wszystkie te bajty do nowej tablicy.

333
00:20:25,040 --> 00:20:28,310
To brzmi jak rozwiązanie bardzo poprawny.

334
00:20:28,310 --> 00:20:34,790
Dlaczego to jest nieatrakcyjna?

335
00:20:34,790 --> 00:20:36,940
Myślę, że to działa, ludzie rozwiązać ten problem.

336
00:20:36,940 --> 00:20:40,710
Dlaczego musimy się go rozwiązać w poniedziałek powiązanych list? Tak?

337
00:20:40,710 --> 00:20:44,060
[Odpowiedź Student, niezrozumiały] To może zająć dużo czasu.

338
00:20:44,060 --> 00:20:49,260
W rzeczywistości, za każdym razem dzwonisz malloc lub realloc lub calloc, co jest jeszcze jeden,

339
00:20:49,260 --> 00:20:52,470
każdym razem, gdy program, mówisz do systemu operacyjnego,

340
00:20:52,470 --> 00:20:54,310
masz tendencję do spowolnić program dół.

341
00:20:54,310 --> 00:20:57,470
A jeśli robisz tego typu rzeczy w pętli, jesteś naprawdę spowalnia rzeczy.

342
00:20:57,470 --> 00:21:00,740
Nie zamierzamy to zauważyć na najprostszych "Hello World" programów typu,

343
00:21:00,740 --> 00:21:04,300
ale w znacznie większych programów, zwracając się do systemu operacyjnego ponownie i ponownie do pamięci

344
00:21:04,300 --> 00:21:07,520
lub podając go znowu i znowu raczej nie będzie dobrze.

345
00:21:07,520 --> 00:21:11,210
Plus, to jest po prostu swego rodzaju intelektualnym - to kompletna strata czasu.

346
00:21:11,210 --> 00:21:16,490
Dlaczego przeznaczyć coraz więcej pamięci, ryzyko kopiując wszystko do nowej tablicy,

347
00:21:16,490 --> 00:21:21,980
jeśli masz alternatywę, która pozwala przydzielić tylko tyle pamięci, jak rzeczywiście potrzebne?

348
00:21:21,980 --> 00:21:24,130
Więc nie ma plusy i minusy w tutaj.

349
00:21:24,130 --> 00:21:26,730
Jednym z plusów jest to, że teraz mamy dynamikę.

350
00:21:26,730 --> 00:21:29,100
Nie ma znaczenia, gdzie kawałki pamięci jest to, że są wolne,

351
00:21:29,100 --> 00:21:32,070
Mogę jakoś stworzyć te okruszki chleba poprzez wskaźniki

352
00:21:32,070 --> 00:21:34,470
do string całe połączonej listy razem.

353
00:21:34,470 --> 00:21:36,470
Ale zapłacić co najmniej jedną cenę.

354
00:21:36,470 --> 00:21:40,060
>> Co muszę oddać w uzyskaniu związane życzeń?

355
00:21:40,060 --> 00:21:42,470
Tak? [Odpowiedź Student, niezrozumiały] Dobra.

356
00:21:42,470 --> 00:21:45,650
Potrzebujesz więcej pamięci. Teraz potrzebuję miejsca dla tych wskaźników,

357
00:21:45,650 --> 00:21:47,900
w tym przypadku połączony super proste liście

358
00:21:47,900 --> 00:21:51,410
że jest tylko próbuje przechowywać liczby całkowite, które są 4 bajty, wciąż mówią

359
00:21:51,410 --> 00:21:54,240
dobrze, wskaźnik jest 4 bajty, więc teraz mam dosłownie podwoiła

360
00:21:54,240 --> 00:21:57,290
Ilość pamięci, muszę tylko zapisać tę listę.

361
00:21:57,290 --> 00:21:59,680
Ale znowu, jest to stały kompromis w informatyce

362
00:21:59,680 --> 00:22:03,440
między czasie i przestrzeni i rozwoju, wysiłku i innych zasobów.

363
00:22:03,440 --> 00:22:06,630
Co innego Minusem korzystania z połączonej listy? Tak?

364
00:22:06,630 --> 00:22:10,150
[Odpowiedź Student, niezrozumiały]

365
00:22:10,150 --> 00:22:12,600
Good. Nie tak łatwo dostępne. Nie możemy już wykorzystać

366
00:22:12,600 --> 00:22:15,530
tydzień 0 zasady jak dziel i rządź.

367
00:22:15,530 --> 00:22:18,220
A dokładniej, binarne wyszukiwanie. Bo choć my ludzie

368
00:22:18,220 --> 00:22:20,400
można zobaczyć w przybliżeniu, gdzie środek tej listy jest

369
00:22:20,400 --> 00:22:25,840
komputer wie, że ten powiązany Lista zaczyna się od adresu o nazwie pierwszy.

370
00:22:25,840 --> 00:22:28,250
I to jest 0x123 lub coś w tym stylu.

371
00:22:28,250 --> 00:22:30,990
A jedynym sposobem Program można znaleźć środkowego elementu

372
00:22:30,990 --> 00:22:33,350
jest faktycznie przeszukać całą listę.

373
00:22:33,350 --> 00:22:35,500
I nawet wtedy, dosłownie musi przeszukać całą listę, bo

374
00:22:35,500 --> 00:22:38,950
nawet po osiągnięciu środkowego elementu wykonując wskaźniki,

375
00:22:38,950 --> 00:22:42,380
ty program, nie mają pojęcia, jak długo ta lista jest, potencjalnie,

376
00:22:42,380 --> 00:22:45,250
aż dojdziesz do końca to, i jak wiesz, programowo

377
00:22:45,250 --> 00:22:48,600
że jesteś na koniec listy połączony?

378
00:22:48,600 --> 00:22:51,120
Jest specjalny wskaźnik NULL, więc ponownie, konwencja.

379
00:22:51,120 --> 00:22:53,870
Zamiast korzystać z tego wskaźnika, na pewno nie ma to być jakaś wartość śmieci

380
00:22:53,870 --> 00:22:57,750
wskazując na scenie gdzieś, chcemy go za rękę w dół, null,

381
00:22:57,750 --> 00:23:01,530
tak, że mamy tę terminus w tej strukturze danych, tak wiemy, gdzie się kończy.

382
00:23:01,530 --> 00:23:03,410
>> Co jeśli chcemy manipulować tym?

383
00:23:03,410 --> 00:23:05,980
Zrobiliśmy większość tego wizualnie, a także z ludźmi,

384
00:23:05,980 --> 00:23:07,630
ale co jeśli chcemy zrobić wstawiania?

385
00:23:07,630 --> 00:23:12,360
Więc oryginalna lista była 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Co jeśli potem chciał przestrzeni malloc na numer 55, za to, węzła

387
00:23:16,730 --> 00:23:20,730
a następnie chcemy wstawić 55 na liście, tak jak to zrobiliśmy w poniedziałek?

388
00:23:20,730 --> 00:23:23,690
W jaki sposób możemy to zrobić? Cóż, Anita podszedł i ona zasadniczo chodził listę.

389
00:23:23,690 --> 00:23:27,500
Rozpoczęła się pierwszego elementu, a następnie dalej, następne, następne, następne, następne.

390
00:23:27,500 --> 00:23:29,500
Wreszcie uderzył lewą w dół

391
00:23:29,500 --> 00:23:34,480
i zrealizowane oh, to jest NULL. Więc co manipulacja wskaźnik należy zrobić?

392
00:23:34,480 --> 00:23:37,980
Osoba, która była na końcu, numer 34, potrzebował jego lewa ręka podniesiona

393
00:23:37,980 --> 00:23:46,220
do punktu na 55, 55 potrzebował ich lewą rękę skierowaną w dół, aby mieć nowy NULL terminator. Gotowe.

394
00:23:46,220 --> 00:23:49,540
Dość łatwo wstawić 55 do posortowanej listy.

395
00:23:49,540 --> 00:23:51,800
I jak może to wyglądać?

396
00:23:51,800 --> 00:23:55,690
>> Pozwólcie mi iść do przodu i otworzyć jakiś przykład kodu tutaj.

397
00:23:55,690 --> 00:23:58,120
Ja otwarcie gedit i pozwól mi otworzyć dwa pliki pierwszy.

398
00:23:58,120 --> 00:24:02,050
Jednym z nich jest list1.h, i daj mi tylko przypomnieć, że jest to fragment kodu,

399
00:24:02,050 --> 00:24:04,920
że stosowany do reprezentowania węzeł.

400
00:24:04,920 --> 00:24:13,040
Węzeł ma zarówno int o nazwie n i wskaźnik zwany dalej, że tylko punkty do następnej rzeczy z listy.

401
00:24:13,040 --> 00:24:15,450
To jest teraz w pliku. Godz. Dlaczego?

402
00:24:15,450 --> 00:24:19,090
Jest to konwencja, a nie skorzystało z tego ogromną ilość sami,

403
00:24:19,090 --> 00:24:22,220
ale człowiek, który napisał i innych funkcji printf

404
00:24:22,220 --> 00:24:27,150
dał jako dar dla świata te wszystkie funkcje, pisząc plik o nazwie stdio.h.

405
00:24:27,150 --> 00:24:30,950
A wtedy nie string.h, a następnie tam map.h, a tam wszystkie te pliki h

406
00:24:30,950 --> 00:24:34,410
że może widzieliście lub używane w okresie napisane przez innych ludzi.

407
00:24:34,410 --> 00:24:38,470
Zazwyczaj w tych. Pliki h są tylko takie rzeczy jak typedef

408
00:24:38,470 --> 00:24:42,310
lub deklaracje niestandardowych lub deklaracje stałych.

409
00:24:42,310 --> 00:24:47,890
Nie umieścić implementacje funkcji "w plikach nagłówkowych.

410
00:24:47,890 --> 00:24:50,570
Umieścić, zamiast tylko ich prototypy.

411
00:24:50,570 --> 00:24:53,050
Można umieścić rzeczy, które chcesz podzielić się ze światem, co trzeba

412
00:24:53,050 --> 00:24:55,640
aby skompilować kod. Więc po prostu dostać się do tego zwyczaju,

413
00:24:55,640 --> 00:24:59,110
zdecydowaliśmy się zrobić to samo. Nie ma wiele w list1.h,

414
00:24:59,110 --> 00:25:02,070
ale mamy już coś, co może być interesujące dla ludzi na świecie

415
00:25:02,070 --> 00:25:05,030
, którzy chcą skorzystać z naszej połączonej realizację listy.

416
00:25:05,030 --> 00:25:08,040
Teraz, w list1.c, nie będzie przejść przez te wszystkie rzeczy

417
00:25:08,040 --> 00:25:11,390
bo to trochę długo, ten program, ale niech to naprawdę szybko biegać na polecenia.

418
00:25:11,390 --> 00:25:15,720
Pozwól mi skompilować Lista1, niech następnie uruchomić Lista1 i co zobaczysz jest

419
00:25:15,720 --> 00:25:18,070
mamy symulowane prosty mały program tutaj

420
00:25:18,070 --> 00:25:20,990
że się dzieje, żebym mógł dodawać i usuwać numery do listy.

421
00:25:20,990 --> 00:25:24,310
Więc pozwól mi iść dalej i wpisz 3 na 3 opcji menu.

422
00:25:24,310 --> 00:25:27,880
Chcę wstawić numer - zróbmy pierwszy numer, który był 9,

423
00:25:27,880 --> 00:25:30,550
a teraz mi powiedziano lista jest teraz 9.

424
00:25:30,550 --> 00:25:33,760
Pozwól mi iść dalej i zrobić kolejny wkładanie, więc uderzyłem opcji menu 3.

425
00:25:33,760 --> 00:25:36,760
Jaki numer chcę wstawić? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. I zrobię tylko jeden.

427
00:25:39,220 --> 00:25:41,720
Pozwól mi wstawić numer 22.

428
00:25:41,720 --> 00:25:45,850
Więc mamy początki połączonej listy, że mieliśmy w formie slajdów chwilą.

429
00:25:45,850 --> 00:25:48,740
Jak to jest wprowadzenie właściwie się dzieje?

430
00:25:48,740 --> 00:25:52,000
Rzeczywiście, 22 znajduje się teraz w koniec listy.

431
00:25:52,000 --> 00:25:55,050
Więc opowieści powiedzieliśmy na scenie w poniedziałek i recapped właśnie

432
00:25:55,050 --> 00:25:57,460
muszą być rzeczywiście dzieje się w kodzie.

433
00:25:57,460 --> 00:25:59,700
Rzućmy okiem. Pozwól, przewiń w tym pliku.

434
00:25:59,700 --> 00:26:01,720
Będziemy tuszować niektóre z funkcji,

435
00:26:01,720 --> 00:26:05,630
ale będziemy iść w dół do, powiedzmy, funkcja insert.

436
00:26:05,630 --> 00:26:11,720
>> Zobaczmy, w jaki sposób go o wstawienie nowego węzła w tej połączonej listy.

437
00:26:11,720 --> 00:26:14,550
Gdzie jest lista zadeklarowanych? Cóż, przejść całą drogę w górę na górze,

438
00:26:14,550 --> 00:26:19,970
i zauważ, że moja lista jest zasadniczo związany zgłoszone jako jeden wskaźnik, który jest początkowo NULL.

439
00:26:19,970 --> 00:26:23,180
Więc używam zmienną globalną tutaj, co w ogóle mamy głosił przeciw

440
00:26:23,180 --> 00:26:25,280
ponieważ czyni Twój kod trochę bałagan w utrzymaniu,

441
00:26:25,280 --> 00:26:29,080
To trochę leniwy, zazwyczaj, ale to nie jest leniwy i nie jest źle i nie jest źle

442
00:26:29,080 --> 00:26:33,660
Jeśli twój program jest jedynym celem w życiu jest symulacja jeden połączonej listy.

443
00:26:33,660 --> 00:26:35,460
Która jest dokładnie to, co robimy.

444
00:26:35,460 --> 00:26:39,100
Więc zamiast zgłoszenia tego w głównym, następnie trzeba przekazać go do każdej funkcji

445
00:26:39,100 --> 00:26:42,640
pisaliśmy w tym programie, zamiast realizować oh, po prostu sprawiają, że globalne

446
00:26:42,640 --> 00:26:47,060
ponieważ cały Celem tego programu jest pokazanie jednej i tylko jednej połączonej listy.

447
00:26:47,060 --> 00:26:50,700
Tak, że czuje się dobrze. Oto moje prototypy, i nie przejdzie przez wszystkie te,

448
00:26:50,700 --> 00:26:55,800
ale napisałem funkcję usuwania, w funkcji wyszukiwania, funkcję insert oraz funkcji trawersu.

449
00:26:55,800 --> 00:26:59,080
Ale bądźmy teraz wrócić w dół do funkcji płytek

450
00:26:59,080 --> 00:27:01,490
i zobaczyć, jak ten jeden działa tutaj.

451
00:27:01,490 --> 00:27:09,940
Insert jest na linii - jedziemy.

452
00:27:09,940 --> 00:27:12,850
Wstaw. Tak więc nie trzeba żadnych argumentów, bo będziemy prosić

453
00:27:12,850 --> 00:27:15,930
wewnątrz użytkownik tej funkcji dla liczby chcą wstawić.

454
00:27:15,930 --> 00:27:19,410
Ale najpierw przygotować, aby dać im trochę miejsca.

455
00:27:19,410 --> 00:27:22,050
Jest to rodzaj kopiowania i wklejania z innego przykładu.

456
00:27:22,050 --> 00:27:25,110
W tym przypadku, byliśmy przydzielania int, tym razem mamy do podziału węzła.

457
00:27:25,110 --> 00:27:27,910
Naprawdę nie pamiętam, jak wiele bajtów węzeł jest, ale to jest w porządku.

458
00:27:27,910 --> 00:27:30,460
Sizeof mogę zrozumieć, że dla mnie.

459
00:27:30,460 --> 00:27:33,340
I dlaczego ja sprawdzanie NULL w wierszu 120?

460
00:27:33,340 --> 00:27:37,530
Co może pójść źle w linii 119? Tak?

461
00:27:37,530 --> 00:27:40,530
[Odpowiedź Student, niezrozumiały]

462
00:27:40,530 --> 00:27:43,440
Good. Po prostu może być tak, że poprosiłem o pamięć zbyt dużo

463
00:27:43,440 --> 00:27:47,020
czy coś jest nie tak, a system operacyjny nie ma wystarczającej ilości bajtów do daj mi,

464
00:27:47,020 --> 00:27:50,640
tak to sygnalizuje tyle powracając NULL, a jeśli nie sprawdzić, że

465
00:27:50,640 --> 00:27:54,710
a ja po prostu ślepo przystąpić do korzystania adres zwrócony, to może być NULL.

466
00:27:54,710 --> 00:27:58,400
To może być jakaś nieznana wartość; nie jest dobrą rzeczą, chyba że -

467
00:27:58,400 --> 00:28:00,590
rzeczywiście nie będzie wartość nieznana. To może być NULL, więc nie chcę

468
00:28:00,590 --> 00:28:02,550
do nadużywania go i ryzykować dereferencji go.

469
00:28:02,550 --> 00:28:07,410
Jeśli tak się stanie, po prostu wrócić i będziemy udawać, że nie wrócę wszelkich pamięci w ogóle.

470
00:28:07,410 --> 00:28:12,270
>> W przeciwnym razie, mówię użytkownik daj mi numer do wstawienia, wzywam naszego starego getInt przyjacielu,

471
00:28:12,270 --> 00:28:15,530
a potem to nowa składnia wprowadziliśmy w poniedziałek.

472
00:28:15,530 --> 00:28:20,320
"Newptr-> n" oznacza mieć adres, który podano przez malloc

473
00:28:20,320 --> 00:28:23,490
co stanowi pierwszy bajt nowego obiektu węzła

474
00:28:23,490 --> 00:28:26,860
a następnie przejść do pola o nazwie n.

475
00:28:26,860 --> 00:28:35,270
Trochę trivia pytanie: Jest to odpowiednik tego, co bardziej tajemniczych linii kodu?

476
00:28:35,270 --> 00:28:38,110
Jak inaczej mógłbym napisać to? Chcesz wziąć ukłucie?

477
00:28:38,110 --> 00:28:41,480
[Odpowiedź Student, niezrozumiały]

478
00:28:41,480 --> 00:28:44,870
Good. Pomocą. N, ale to nie jest tak proste, jak to.

479
00:28:44,870 --> 00:28:47,090
Co mam najpierw zrobić? [Odpowiedź Student, niezrozumiały]

480
00:28:47,090 --> 00:28:52,730
Good. Muszę zrobić newptr.n *.

481
00:28:52,730 --> 00:28:55,610
Więc to mówi nowy wskaźnik jest oczywiście adres. Dlaczego?

482
00:28:55,610 --> 00:28:59,520
Ponieważ został zwrócony przez malloc. Newptr * mówiąc "tam"

483
00:28:59,520 --> 00:29:02,970
, a następnie, gdy jesteś tam, a następnie można użyć bardziej znajomy. n,

484
00:29:02,970 --> 00:29:05,730
ale to po prostu wygląda trochę brzydki, zwłaszcza jeśli my, ludzie będą

485
00:29:05,730 --> 00:29:10,360
narysować wskaźniki ze strzałkami cały czas, świat ma znormalizowane na tym zapisie strzałki

486
00:29:10,360 --> 00:29:12,320
który robi dokładnie to samo.

487
00:29:12,320 --> 00:29:16,070
Więc używać tylko -> notacji gdy coś po lewej stronie jest wskaźnik.

488
00:29:16,070 --> 00:29:18,790
W przeciwnym razie, jeśli jest rzeczywista struktura, użyj. N.

489
00:29:18,790 --> 00:29:25,800
A potem to: Dlaczego zainicjować newptr-> next NULL?

490
00:29:25,800 --> 00:29:28,610
Nie chcemy wiszącym lewą rękę off koniec etapu.

491
00:29:28,610 --> 00:29:31,630
Chcemy, skierowane w dół, co oznacza koniec tej listy

492
00:29:31,630 --> 00:29:34,980
potencjalnie może być w tym węźle, więc lepiej upewnić się, że jest NULL.

493
00:29:34,980 --> 00:29:38,460
A w ogóle, inicjowanie zmienne i danych członków i strukturach

494
00:29:38,460 --> 00:29:40,470
coś jest po prostu dobra praktyka.

495
00:29:40,470 --> 00:29:45,170
Wystarczy pozwolić śmieci istnieją i będą istnieć ogół dostaje w tarapatach

496
00:29:45,170 --> 00:29:48,650
jeśli zapomnisz zrobić coś później.

497
00:29:48,650 --> 00:29:51,590
>> Oto kilka przypadków. To również jest funkcja wkładka,

498
00:29:51,590 --> 00:29:54,930
i pierwsze co mam sprawdzić, czy zmienna jest nazywana pierwszym,

499
00:29:54,930 --> 00:29:58,240
że globalna zmienna jest NULL, co oznacza, że ​​nie jest związana lista.

500
00:29:58,240 --> 00:30:02,460
Nie dodaje się żadnych liczb, więc to jest trywialne, aby wstawić ten numer bieżącego

501
00:30:02,460 --> 00:30:05,240
na liście, po prostu dlatego, że należy na początku listy.

502
00:30:05,240 --> 00:30:08,100
Tak to było, kiedy Anita została po prostu stoję tu sam, udając

503
00:30:08,100 --> 00:30:11,390
nikt inny nie był tu na scenie, dopóki nie przydzielono węzła

504
00:30:11,390 --> 00:30:13,940
to może ona zwiększyć rękę po raz pierwszy,

505
00:30:13,940 --> 00:30:17,420
gdyby wszyscy przyszli na scenę po niej w poniedziałek.

506
00:30:17,420 --> 00:30:22,900
Teraz tutaj jest to trochę sprawdzić, gdzie mam do powiedzenia jeśli nowy węzła wartość n

507
00:30:22,900 --> 00:30:27,370
jest <wartość n w bieżącym węźle pierwszy

508
00:30:27,370 --> 00:30:29,930
to oznacza, że ​​jest połączona lista, która się rozpoczęła.

509
00:30:29,930 --> 00:30:32,330
Jest co najmniej jeden węzeł na liście, ale ten nowy facet

510
00:30:32,330 --> 00:30:37,230
należy przed nim, więc musimy przenieść rzeczy wokół.

511
00:30:37,230 --> 00:30:43,450
Innymi słowy, jeśli lista rozpoczął się tylko, powiedzmy,

512
00:30:43,450 --> 00:30:48,100
tylko numer 17, to - faktycznie, możemy to zrobić bardziej wyraźnie.

513
00:30:48,100 --> 00:30:56,010
Jeśli zaczniemy naszą historię ze wskaźnikiem tutaj nazywa pierwsze,

514
00:30:56,010 --> 00:30:59,870
i początkowo to NULL, i wstawić numer 9,

515
00:30:59,870 --> 00:31:02,510
nr 9 wyraźnie należy na początku na liście.

516
00:31:02,510 --> 00:31:07,400
Warto więc udawać, że tylko malloced adres lub numer 9 i umieścić go tutaj.

517
00:31:07,400 --> 00:31:13,170
Jeśli pierwsze 9 domyślnie pierwszy scenariusz dyskutowaliśmy tylko oznacza punkt Miejmy ten facet tutaj

518
00:31:13,170 --> 00:31:15,790
zostawić to jako NULL; teraz mamy numer 9.

519
00:31:15,790 --> 00:31:18,280
Następny numer chcemy wstawić jest 17.

520
00:31:18,280 --> 00:31:22,420
17 należy tu, więc będziemy musieli zrobić jakiś logiczny Zaostrzenie przez to.

521
00:31:22,420 --> 00:31:26,060
Więc zamiast tego, zanim to zrobimy, udawajmy, że chcemy wstawić numer 8.

522
00:31:26,060 --> 00:31:28,650
>> Więc po prostu dla wygody, idę wyciągnąć tutaj.

523
00:31:28,650 --> 00:31:30,760
Ale pamiętaj, malloc można go umieścić niemal wszędzie.

524
00:31:30,760 --> 00:31:33,460
Ale na rysunku dobra, włożę go tutaj.

525
00:31:33,460 --> 00:31:38,440
Więc udawać Właśnie przydzielono węzeł numer 8, jest to NULL domyślnie.

526
00:31:38,440 --> 00:31:42,800
Co teraz się stanie? Kilka rzeczy.

527
00:31:42,800 --> 00:31:47,090
Zrobiliśmy ten błąd w poniedziałek na scenie, gdzie aktualizacja wskaźnik jak ten,

528
00:31:47,090 --> 00:31:51,890
potem zrobił to, a potem twierdził - mamy osierocony wszyscy inni na scenie.

529
00:31:51,890 --> 00:31:54,350
Bo nie mogę się - kolejność operacji jest tu ważne,

530
00:31:54,350 --> 00:31:58,760
bo teraz straciliśmy tego węzła 9, który jest po prostu rodzaj pływających w przestrzeni.

531
00:31:58,760 --> 00:32:01,150
Więc to nie było właściwe podejście w poniedziałek.

532
00:32:01,150 --> 00:32:03,330
Najpierw musisz zrobić coś innego.

533
00:32:03,330 --> 00:32:06,280
Stan świata wygląda tak. Początkowo, 8 jest przeznaczone.

534
00:32:06,280 --> 00:32:10,550
Jaki byłby lepszy sposób wkładania 8?

535
00:32:10,550 --> 00:32:14,720
Zamiast aktualizować ten wskaźnik pierwszy, po prostu zaktualizować Ten tutaj zamiast.

536
00:32:14,720 --> 00:32:17,720
Więc potrzebujemy linii kodu, który zamierza przekształcić ten znak null

537
00:32:17,720 --> 00:32:22,020
do rzeczywistego wskaźnika, która jest skierowana na węźle 9,

538
00:32:22,020 --> 00:32:27,970
i wtedy możemy bezpiecznie zmienić pierwszy punkt na tego faceta tutaj.

539
00:32:27,970 --> 00:32:31,330
Teraz mamy listę, listę, z dwóch elementów.

540
00:32:31,330 --> 00:32:33,580
I co to faktycznie wygląda jak tutaj?

541
00:32:33,580 --> 00:32:36,900
Jeśli spojrzeć na kod, zauważysz, że zrobiłem dokładnie to.

542
00:32:36,900 --> 00:32:41,970
Powiedziałem newptr, w tej historii, newptr wskazywał na tego faceta.

543
00:32:41,970 --> 00:32:45,520
>> Więc pozwól mi wyciągnąć jeszcze jedną rzecz i należy mi zostało trochę więcej miejsca na to.

544
00:32:45,520 --> 00:32:48,540
Więc wybacz maleńki rysunek.

545
00:32:48,540 --> 00:32:52,140
Ten facet nazywa newptr.

546
00:32:52,140 --> 00:32:57,940
To jest zmienna zadeklarowaliśmy kilka linijek wcześniej, w linii - tuż powyżej 25.

547
00:32:57,940 --> 00:33:03,430
I to wskazuje na 8. Więc kiedy mówię newptr-> next, czyli udać się do struktury

548
00:33:03,430 --> 00:33:07,910
który jest ich wskazał przez newptr, więc jesteśmy, tam.

549
00:33:07,910 --> 00:33:13,990
Potem strzałka mówiąc dostać następne pole, a następnie = mówi umieścić jaką wartość tam?

550
00:33:13,990 --> 00:33:17,280
Wartości, który był w pierwszej kolejności; jakie wartości było w pierwszej kolejności?

551
00:33:17,280 --> 00:33:21,930
Pierwszy wskazywał na tym węźle, więc oznacza to powinien teraz wskazywać na tym węźle.

552
00:33:21,930 --> 00:33:25,660
Innymi słowy, to, co wygląda choć śmieszne bałagan z mojego pisma,

553
00:33:25,660 --> 00:33:28,620
co jest prosty pomysł właśnie przenoszenie tych strzałek wokół

554
00:33:28,620 --> 00:33:31,560
przekłada się na kodzie z tylko tego jednego liniowca.

555
00:33:31,560 --> 00:33:38,110
Przechowywania, co jest w pierwszy w następnym polu, a następnie zaktualizować co najpierw faktycznie jest.

556
00:33:38,110 --> 00:33:40,900
Idziemy do przodu i do przodu przez niektóre z tych,

557
00:33:40,900 --> 00:33:44,220
i patrzeć tylko na tym założeniu ogonowej teraz.

558
00:33:44,220 --> 00:33:51,210
Załóżmy, że dostać się do punktu, gdzie uważam, że następne pole jakiegoś węzła jest NULL.

559
00:33:51,210 --> 00:33:53,410
I w tym momencie w historii, szczegółowo, że jestem zapominając o

560
00:33:53,410 --> 00:33:58,170
jest to, że wprowadziliśmy kolejny wskaźnik tutaj w linii 142, wskaźnik poprzednika.

561
00:33:58,170 --> 00:34:01,320
Zasadniczo, w tym momencie w historii, gdy lista jest długa,

562
00:34:01,320 --> 00:34:04,800
I rodzaju muszą chodzić z dwoma palcami, bo jeśli za daleko,

563
00:34:04,800 --> 00:34:08,219
Pamiętam, że w liście single-length, nie można cofnąć.

564
00:34:08,219 --> 00:34:13,659
Więc ten pomysł predptr jest mój lewy palec i newptr - nie newptr.

565
00:34:13,659 --> 00:34:17,199
Kolejna wskazówka, że ​​to tu jest mój drugi palec, a ja jestem po prostu rodzaj spaceru listę.

566
00:34:17,199 --> 00:34:22,179
To dlatego, że istnieje. Ale niech tylko za jeden z prostszych przypadkach tutaj.

567
00:34:22,179 --> 00:34:26,620
Jeśli tego wskaźnika na następne pole jest NULL, co jest logiczną implikacją?

568
00:34:26,620 --> 00:34:30,840
Jeśli przemierzając tę ​​listę i trafisz wskaźniku NULL?

569
00:34:30,840 --> 00:34:35,780
Jesteś na końcu listy, a więc kod następnie dołącz ten jeden dodatkowy element

570
00:34:35,780 --> 00:34:41,230
jest swego rodzaju intuicyjna weźmie tego węzła, którego następny wskaźnik jest NULL,

571
00:34:41,230 --> 00:34:46,120
więc jest to obecnie NULL, i zmienić go, choć, być adres nowego węzła.

572
00:34:46,120 --> 00:34:52,260
Więc jesteśmy po prostu rysunek w kodzie strzałkę, że zwrócił na scenie przez podniesienie czyjąś lewą dłoń.

573
00:34:52,260 --> 00:34:54,070
>> I tak, że będę machać rękami na teraz,

574
00:34:54,070 --> 00:34:58,020
tylko dlatego, że myślę, że łatwo się pogubić, gdy robimy to w tego typu środowiska,

575
00:34:58,020 --> 00:35:00,600
sprawdza do wstawienia na listę w środku.

576
00:35:00,600 --> 00:35:03,220
Ale tylko intuicyjnie, co musi się zdarzyć, jeśli chcesz dowiedzieć się,

577
00:35:03,220 --> 00:35:06,600
gdzie niektóre numer należy w środku jest to trzeba chodzić

578
00:35:06,600 --> 00:35:09,510
więcej niż jednym palcem, więcej niż jeden wskaźnik,

579
00:35:09,510 --> 00:35:12,920
dowiedzieć się, gdzie należy, poprzez sprawdzenie jest element <obecnym,

580
00:35:12,920 --> 00:35:15,450
> Prąd jeden, a jak już znajdziesz to miejsce,

581
00:35:15,450 --> 00:35:20,400
następnie musisz zrobić ten rodzaj gry powłoki gdzie przenieść wskaźniki wokół bardzo ostrożnie.

582
00:35:20,400 --> 00:35:23,850
A to odpowiedź, jeśli chcesz do rozumu przez to w domu na własną rękę,

583
00:35:23,850 --> 00:35:28,340
sprowadza się tylko do tych dwóch linii kodu, ale aby z tych wierszy jest super ważne.

584
00:35:28,340 --> 00:35:31,390
Bo jeśli spadnie czyjąś rękę i podnieść kogoś innego w niewłaściwej kolejności,

585
00:35:31,390 --> 00:35:34,580
ponownie, może skończyć się osierocenia listę.

586
00:35:34,580 --> 00:35:39,500
Podsumowując bardziej konceptualnie, wstawiania na ogonie jest stosunkowo proste.

587
00:35:39,500 --> 00:35:42,940
Wprowadzenie na głowę jest stosunkowo proste,

588
00:35:42,940 --> 00:35:45,580
ale trzeba zaktualizować dodatkowy wskaźnik ten czas

589
00:35:45,580 --> 00:35:47,930
wycisnąć numer 5 na liście tutaj

590
00:35:47,930 --> 00:35:51,560
a następnie umieszczenie w środku wymaga jeszcze więcej wysiłku,

591
00:35:51,560 --> 00:35:56,130
bardzo ostrożnie wstawić numer 20 w odpowiednim miejscu,

592
00:35:56,130 --> 00:35:58,350
która znajduje się pomiędzy 17 i 22.

593
00:35:58,350 --> 00:36:02,700
Więc trzeba zrobić coś jak mają nowego węzła 20 pkt do 22,

594
00:36:02,700 --> 00:36:08,470
, a następnie, który węzeł jest wskaźnik musi być aktualizowany ostatni?

595
00:36:08,470 --> 00:36:10,630
Jest 17, faktycznie go wstawić.

596
00:36:10,630 --> 00:36:14,080
Więc jeszcze raz, ja wstrzymuje rzeczywisty kod dla tej konkretnej realizacji.

597
00:36:14,080 --> 00:36:17,280
>> Na pierwszy rzut oka, że ​​to trochę przytłaczające, ale tak naprawde to pętla nieskończona

598
00:36:17,280 --> 00:36:21,770
który jest zapętlenie, pętli, pętli, pętli, a łamiąc jak najszybciej trafić wskaźniku NULL,

599
00:36:21,770 --> 00:36:24,590
w którym momencie można zrobić wymaganą wstawiania.

600
00:36:24,590 --> 00:36:30,960
To zatem jest reprezentatywna związany kod wstawiania lista.

601
00:36:30,960 --> 00:36:34,590
To był rodzaj partii, i jest to jak mamy rozwiązać jeden problem,

602
00:36:34,590 --> 00:36:36,940
ale my wprowadziliśmy całą drugą. Szczerze mówiąc, spędziliśmy cały ten czas

603
00:36:36,940 --> 00:36:40,540
na duże O i Ω i czasu pracy, starając się rozwiązać problemy szybciej,

604
00:36:40,540 --> 00:36:43,270
i tutaj robimy duży krok do tyłu, to jest.

605
00:36:43,270 --> 00:36:45,380
I jeszcze, jeśli celem jest do przechowywania danych,

606
00:36:45,380 --> 00:36:48,010
czuje się jak Święty Graal, jak powiedział w poniedziałek, że naprawdę

607
00:36:48,010 --> 00:36:50,470
do przechowywania rzeczy natychmiast.

608
00:36:50,470 --> 00:36:53,930
>> Istotnie, przypuśćmy, że zrobiliśmy odłożyć połączonej listy na chwilę

609
00:36:53,930 --> 00:36:56,000
a my zamiast wprowadził pojęcie tabeli.

610
00:36:56,000 --> 00:36:59,110
I niech tylko myśleć o stole na chwilę jako tablicę.

611
00:36:59,110 --> 00:37:03,790
Ta tablica i ta sprawa ma tu jakieś 26 elementów, 0 do 25,

612
00:37:03,790 --> 00:37:07,940
i załóżmy, że trzeba jakiś kawałek składowania nazwami:

613
00:37:07,940 --> 00:37:10,350
Alicja i Bob i Charlie i jak.

614
00:37:10,350 --> 00:37:12,880
I trzeba trochę strukturę danych do przechowywania tych nazw.

615
00:37:12,880 --> 00:37:15,000
Cóż, można użyć coś jak połączonej listy

616
00:37:15,000 --> 00:37:20,260
i można było iść listę wkładanie Alice przed Bob i Charlie po Boba i tak dalej.

617
00:37:20,260 --> 00:37:23,850
A w rzeczywistości, jeśli chcesz zobaczyć kod takiego jak bok,

618
00:37:23,850 --> 00:37:27,230
Wiadomo, że w list2.h, robimy dokładnie to.

619
00:37:27,230 --> 00:37:30,610
Nie przechodzi przez ten kod, ale jest to wariant pierwszego przykładu

620
00:37:30,610 --> 00:37:34,640
która wprowadza jeden inny struct widzieliśmy przed zwanego studenta,

621
00:37:34,640 --> 00:37:40,330
a co to właściwie przechowywane w połączonej listy jest wskaźnikiem do struktury studentów

622
00:37:40,330 --> 00:37:44,520
niż proste trochę całkowitą, n.

623
00:37:44,520 --> 00:37:46,900
Więc sobie sprawę, że znajduje się tam kod, który obejmuje rzeczywiste ciągi,

624
00:37:46,900 --> 00:37:49,940
ale jeśli celem w ręku naprawdę teraz jest rozwiązanie problemu wydajności,

625
00:37:49,940 --> 00:37:53,380
Czy nie byłoby miło, jeśli mamy dany obiekt o nazwie Alice,

626
00:37:53,380 --> 00:37:56,020
chcemy umieścić ją w odpowiednim miejscu w strukturze danych,

627
00:37:56,020 --> 00:37:58,860
czuje się, że to będzie naprawdę miło po prostu umieścić Alice,

628
00:37:58,860 --> 00:38:01,180
, którego nazwa zaczyna się w pierwszym miejscu.

629
00:38:01,180 --> 00:38:05,270
I Bob, którego nazwa zaczyna się na literę B, w drugiej lokalizacji.

630
00:38:05,270 --> 00:38:09,580
Z tablicy lub zacznijmy nazywając to tabeli, tabeli mieszania na to,

631
00:38:09,580 --> 00:38:13,650
możemy zrobić dokładnie to. Jeśli podano nazwę jak Alice,

632
00:38:13,650 --> 00:38:16,700
łańcuch jak Alicja, gdzie można umieścić A-L-i-C-E?

633
00:38:16,700 --> 00:38:20,540
Potrzebujemy hueristic. Potrzebujemy funkcji, aby robić jakieś wejście jak Alicja

634
00:38:20,540 --> 00:38:24,610
i odesłać odpowiedź, "Put Alice w tym miejscu."

635
00:38:24,610 --> 00:38:28,720
I ta funkcja, ta czarna skrzynka, będzie się nazywać funkcją skrótu.

636
00:38:28,720 --> 00:38:32,330
>> Funkcja skrótu jest coś, co ma wejście, jak "Alice",

637
00:38:32,330 --> 00:38:38,080
i wraca do ciebie, zazwyczaj w jakiś numeryczny lokalizacja struktury danych, w którym Alice należy.

638
00:38:38,080 --> 00:38:40,830
W tym przypadku, funkcja mieszania nasz powinny być stosunkowo proste.

639
00:38:40,830 --> 00:38:47,510
Nasza funkcja skrótu powinna powiedzieć, jeśli są podane "Alice", który znak powinien mnie obchodzi?

640
00:38:47,510 --> 00:38:55,660
Pierwszy. Więc patrzę na [0], a potem powiedzieć, że jeśli [0] postać jest, zwraca liczbę 0.

641
00:38:55,660 --> 00:39:01,130
Jeśli jest to B, powrót 1. Jeśli jest to C, zwróci 2, i tak dalej.

642
00:39:01,130 --> 00:39:05,940
Wszystkie 0 index, i że pozwoli mi wstawić Alice, a potem Bob i potem Charlie i tak dalej

643
00:39:05,940 --> 00:39:10,960
do tej struktury danych. Ale jest problem.

644
00:39:10,960 --> 00:39:13,060
Co jeśli Anita przychodzi ponownie?

645
00:39:13,060 --> 00:39:17,510
Gdzie stawiamy Anita? Jej imię, też zaczyna się na literę A,

646
00:39:17,510 --> 00:39:20,330
i wydaje się, zrobiliśmy jeszcze większy bałagan tym problemem.

647
00:39:20,330 --> 00:39:24,380
Mamy teraz natychmiastowe umieszczenie, stały czas wstawiania, w strukturze danych

648
00:39:24,380 --> 00:39:27,100
zamiast gorszego przypadku liniowym,

649
00:39:27,100 --> 00:39:29,510
ale co możemy zrobić z Anitą w tym przypadku?

650
00:39:29,510 --> 00:39:34,110
Jakie są dwie opcje, naprawdę? Tak?

651
00:39:34,110 --> 00:39:37,410
[Odpowiedź Student, niezrozumiały] Okay, więc możemy mieć inny wymiar.

652
00:39:37,410 --> 00:39:42,320
To dobrze. Tak więc możemy budować rzeczy w 3D jak rozmawialiśmy werbalnie w poniedziałek.

653
00:39:42,320 --> 00:39:46,700
Możemy dodać kolejną dostęp tutaj, ale przypuszczam, że nie, staram się zachować to proste.

654
00:39:46,700 --> 00:39:50,160
Cały celem jest, aby mieć natychmiastowy dostęp w czasie stałym,

655
00:39:50,160 --> 00:39:52,170
więc to dodanie zbyt dużej złożoności.

656
00:39:52,170 --> 00:39:55,970
Jakie są inne opcje, gdy próbujesz wstawić Anitę do tej struktury danych? Tak?

657
00:39:55,970 --> 00:39:58,610
[Odpowiedź Student, niezrozumiały] Dobra. Więc możemy przenieść wszystkich innych w dół,

658
00:39:58,610 --> 00:40:03,040
jak Charlie trąca dół Bob i Alice, a następnie kładziemy Anita gdzie ona naprawdę chce być.

659
00:40:03,040 --> 00:40:05,660
>> Oczywiście, teraz, jest efektem ubocznym tego.

660
00:40:05,660 --> 00:40:09,000
Ta struktura danych prawdopodobnie jest przydatne nie dlatego, że chcemy wstawić ludziom raz

661
00:40:09,000 --> 00:40:11,250
ale dlatego, że chcemy, aby sprawdzić, czy są tam później

662
00:40:11,250 --> 00:40:13,600
jeśli chcemy wydrukować wszystkie nazwy w strukturze danych.

663
00:40:13,600 --> 00:40:15,850
Mamy zamiar zrobić coś z tymi danymi w końcu.

664
00:40:15,850 --> 00:40:20,810
Więc teraz mamy rodzaj skręcane na Alice, która już nie jest, gdzie ona ma być.

665
00:40:20,810 --> 00:40:23,880
Ani Bob ani Charlie.

666
00:40:23,880 --> 00:40:26,060
Więc może to nie jest taki dobry pomysł.

667
00:40:26,060 --> 00:40:28,830
Ale rzeczywiście, to jest jedna z opcji. Możemy przenieść każdego w dół,

668
00:40:28,830 --> 00:40:32,240
lub cholery, Anita przyszedł późno do gry, dlaczego nie możemy po prostu umieścić Anita

669
00:40:32,240 --> 00:40:35,870
nie tutaj, nie tutaj, nie tutaj, po prostu umieścić ją trochę niżej na liście.

670
00:40:35,870 --> 00:40:38,680
Ale wtedy ten problem zaczyna przechodzą ponownie.

671
00:40:38,680 --> 00:40:41,630
Możesz być w stanie znaleźć Alice natychmiast, na podstawie jej imienia.

672
00:40:41,630 --> 00:40:44,320
I Bob natychmiast, a Charlie. Ale potem szukać Anita,

673
00:40:44,320 --> 00:40:46,360
i widzisz, hmm, Alice jest w drodze.

674
00:40:46,360 --> 00:40:48,770
Cóż, pozwól mi sprawdzić poniżej Alice. Bob nie jest Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie nie jest Anita. Och, jest Anita.

676
00:40:51,850 --> 00:40:54,720
A jeśli nadal tego pociągu logiki całą drogę,

677
00:40:54,720 --> 00:41:00,690
, co jest najgorszym przypadku czas jazdy na znalezienie lub włożeniu Anitę do tej nowej struktury danych?

678
00:41:00,690 --> 00:41:03,280
To jest O (n), prawda?

679
00:41:03,280 --> 00:41:06,280
Bo w najgorszym przypadku, nie Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
w dół do niejakiego "Y", więc jest tylko jedno miejsce w lewo.

681
00:41:10,150 --> 00:41:13,950
Na szczęście, nie mamy jeden o nazwie "Z", więc umieścić Anitę na samym dole.

682
00:41:13,950 --> 00:41:16,040
>> Tak naprawdę nie rozwiązuje tego problemu.

683
00:41:16,040 --> 00:41:19,890
Więc może trzeba wprowadzić ten trzeci wymiar.

684
00:41:19,890 --> 00:41:22,230
I okazuje się, jeśli nie wprowadzi tego trzeciego wymiaru,

685
00:41:22,230 --> 00:41:25,240
nie możemy zrobić to doskonale, ale Święty Graal ma być coraz

686
00:41:25,240 --> 00:41:28,370
stała w czasie wkładania i dynamiczne wstawki, tak aby

687
00:41:28,370 --> 00:41:30,960
nie mamy do hard-code tablica wielkości 26.

688
00:41:30,960 --> 00:41:34,400
Możemy wstawić tyle nazw, jak chcemy, ale weźmy naszą 5-minutową przerwę tutaj

689
00:41:34,400 --> 00:41:38,790
a następnie zrobić prawidłowo.

690
00:41:38,790 --> 00:41:46,020
Dobrze. Ustawić się dość sztucznie historię tam

691
00:41:46,020 --> 00:41:48,670
wybierając Alice, a potem Bob, a potem Charlie i następnie Anita,

692
00:41:48,670 --> 00:41:51,000
którego nazwa została oczywiście będzie kolidować z Alice.

693
00:41:51,000 --> 00:41:54,120
Ale pytanie skończyło w poniedziałek jest tylko jak to jest prawdopodobne

694
00:41:54,120 --> 00:41:56,370
że można dostać tego rodzaju kolizji? Innymi słowy,

695
00:41:56,370 --> 00:42:00,490
jeśli zaczniemy używać tego tabelarycznego strukturę, która jest tak naprawdę tablicą,

696
00:42:00,490 --> 00:42:02,460
w tym przypadku, 26 miejsc,

697
00:42:02,460 --> 00:42:05,740
co jeśli nasze środki są zamiast równomiernie rozłożone?

698
00:42:05,740 --> 00:42:09,620
To nie jest sztucznie Alicja i Bob i Charlie i David, i tak dalej alfabetycznie

699
00:42:09,620 --> 00:42:12,380
to jest równomiernie rozłożony do Z.

700
00:42:12,380 --> 00:42:15,220
>> Może po prostu miał szczęście, a my nie będziemy mieć dwa męskie lub dwa przez B

701
00:42:15,220 --> 00:42:17,640
z prawdopodobieństwem bardzo wysokim poziomie, ale jak ktoś zauważył,

702
00:42:17,640 --> 00:42:20,730
Jeśli się tego problemu i uogólnione nie 0 do 25

703
00:42:20,730 --> 00:42:26,060
, ale, na przykład, 0 do 364 lub 65, często wiele dni w typowych roku

704
00:42:26,060 --> 00:42:31,170
i zapytał, na pytanie: "Jakie jest prawdopodobieństwo, że dwóch z nas w tym pokoju mają urodziny tego samego?"

705
00:42:31,170 --> 00:42:34,600
Innymi słowy, co jest prawdopodobieństwo, że dwóch z nas ma imię zaczynając?

706
00:42:34,600 --> 00:42:37,190
Rodzaj pytanie jest taka sama, ale przestrzeni adresowej,

707
00:42:37,190 --> 00:42:39,940
miejsce to search, jest większe w przypadku urodzin,

708
00:42:39,940 --> 00:42:42,820
ponieważ mamy tak wiele więcej dni w roku niż liter w alfabecie.

709
00:42:42,820 --> 00:42:44,910
Jakie jest prawdopodobieństwo kolizji?

710
00:42:44,910 --> 00:42:48,410
Cóż, możemy myśleć o tym by dowiedzieć się matematyki w przeciwną stronę.

711
00:42:48,410 --> 00:42:50,580
Jakie jest prawdopodobieństwo bez kolizji?

712
00:42:50,580 --> 00:42:53,970
Cóż, to wyrażenie tutaj mówi, że to, co jest prawdopodobieństwo

713
00:42:53,970 --> 00:42:58,770
jeśli jest tylko jedna osoba w tym pokoju, że mają wyjątkową urodziny?

714
00:42:58,770 --> 00:43:01,190
Jest w 100%. Bo jeśli jest tylko jedna osoba w pokoju,

715
00:43:01,190 --> 00:43:03,940
jego lub jej urodzin może być dowolny z 365 dni z roku.

716
00:43:03,940 --> 00:43:08,650
Więc 365/365 opcji daje mi wartość 1.

717
00:43:08,650 --> 00:43:11,250
Więc prawdopodobieństwo mowa w tej chwili jest tylko 1.

718
00:43:11,250 --> 00:43:13,270
Ale jeśli jest druga osoba w pokoju,

719
00:43:13,270 --> 00:43:16,490
Jakie jest prawdopodobieństwo, że ich urodziny jest inny?

720
00:43:16,490 --> 00:43:20,680
Jest tylko 364 możliwych dni, pomijając lata przestępne,

721
00:43:20,680 --> 00:43:23,580
ich urodzin nie zderzają się z innych osób.

722
00:43:23,580 --> 00:43:31,920
Więc 364/365. Jeśli osoba trzecia jest w, to 363/365, i tak dalej.

723
00:43:31,920 --> 00:43:35,790
Więc trzymamy pomnożenie razem te frakcje, które są coraz mniejsze,

724
00:43:35,790 --> 00:43:40,720
dowiedzieć się, jakie jest prawdopodobieństwo, że każdy z nas posiada unikalne urodziny?

725
00:43:40,720 --> 00:43:43,570
Ale wtedy możemy, oczywiście, po prostu weź tę odpowiedź i przerzucić go wokół

726
00:43:43,570 --> 00:43:47,210
i zrobić 1 minus to wszystko, ekspresyjny my ostatecznie dostać

727
00:43:47,210 --> 00:43:51,250
jeśli pamiętasz z tyłu książek matematycznych, to wygląda trochę coś takiego,

728
00:43:51,250 --> 00:43:54,590
które jest znacznie łatwiej interpretować graficznie.

729
00:43:54,590 --> 00:43:57,820
A ta grafika ma tu na osi x liczbę urodzin,

730
00:43:57,820 --> 00:44:02,030
lub liczba osób z urodzin, a na osi Y jest prawdopodobieństwo meczu.

731
00:44:02,030 --> 00:44:06,060
A co to jest o to, że jeśli masz, powiedzmy, nawet,

732
00:44:06,060 --> 00:44:10,860
Wybierzmy coś jak 22, 23 lat.

733
00:44:10,860 --> 00:44:13,160
Jeśli jest 22 lub 23 osób w pokoju,

734
00:44:13,160 --> 00:44:17,100
prawdopodobieństwo, że dwa z tych bardzo niewielu ludzi będzie mieć urodziny tego samego

735
00:44:17,100 --> 00:44:19,560
jest rzeczywiście bardzo wysokie, kombinatorycznie.

736
00:44:19,560 --> 00:44:23,450
50% prawdopodobieństwo, że w klasie liczącej zaledwie 22 osób, w seminarium, praktycznie

737
00:44:23,450 --> 00:44:25,790
2 z tych osób będzie mieć taki sam urodziny.

738
00:44:25,790 --> 00:44:28,520
Ponieważ istnieje tak wiele sposobów, w którym można mieć urodziny tego samego.

739
00:44:28,520 --> 00:44:31,110
Jeszcze gorzej, jeśli spojrzeć na prawej stronie wykresu,

740
00:44:31,110 --> 00:44:34,040
do czasu masz klasę z 58 uczniów w tym,

741
00:44:34,040 --> 00:44:39,270
prawdopodobieństwo 2 osób mających urodziny jest super, super wysoka, prawie 100%.

742
00:44:39,270 --> 00:44:41,880
Teraz, to jest coś w rodzaju zabawy rzeczywistości o prawdziwym życiu.

743
00:44:41,880 --> 00:44:45,850
>> Ale implikacje, teraz, struktur danych i przechowywania informacji

744
00:44:45,850 --> 00:44:51,100
Oznacza to, że tylko przy założeniu, że masz ładne, czyste, równomierny rozkład danych

745
00:44:51,100 --> 00:44:53,650
i masz na tyle duże, aby dopasować tablicy kilka rzeczy

746
00:44:53,650 --> 00:44:59,360
nie znaczy, że będziemy się ludzi w unikalnych lokalizacjach.

747
00:44:59,360 --> 00:45:03,810
Będziesz mieć kolizji. Więc to pojęcie mieszania, jak to się nazywa,

748
00:45:03,810 --> 00:45:07,450
biorąc wejście jak "Alice" i masuje go w jakiś sposób

749
00:45:07,450 --> 00:45:10,190
a następnie powrót odpowiedź jak 0 lub 1 lub 2.

750
00:45:10,190 --> 00:45:17,500
Wracając jakieś wyjście z tej funkcji jest nękane przez to prawdopodobieństwo kolizji.

751
00:45:17,500 --> 00:45:19,530
Więc jak możemy obsłużyć te kolizje?

752
00:45:19,530 --> 00:45:21,940
Cóż, w jednym przypadku możemy mieć pojęcia, że ​​został zaproponowany.

753
00:45:21,940 --> 00:45:25,100
Możemy po prostu przenieść każdego w dół, czy może, trochę więcej po prostu,

754
00:45:25,100 --> 00:45:29,870
niż każdy inny ruch, po prostu przenieść Anitę do końca dostępnego miejsca.

755
00:45:29,870 --> 00:45:32,810
Więc jeśli Alice jest w 0, Bob jest w 1, Charlie jest w 2,

756
00:45:32,810 --> 00:45:35,260
my po prostu umieścić Anitę w miejscu 3.

757
00:45:35,260 --> 00:45:38,860
I to jest technika, w strukturach danych nazywa adresowania liniowego.

758
00:45:38,860 --> 00:45:41,310
Liniowy, ponieważ jesteś tylko w odległości tej linii, i jesteś rodzaju sondowania

759
00:45:41,310 --> 00:45:43,640
dostępnych miejsc w strukturze danych.

760
00:45:43,640 --> 00:45:46,210
Oczywiście, nakładanych w O (n).

761
00:45:46,210 --> 00:45:49,590
Jeśli struktura danych jest naprawdę pełna, jest 25 osób, w nim już

762
00:45:49,590 --> 00:45:54,120
a następnie Anita przychodzi, ona kończy się na to, co będzie lokalizacja Z, i to jest w porządku.

763
00:45:54,120 --> 00:45:56,540
Ona nadal pasuje, i możemy ją znaleźć później.

764
00:45:56,540 --> 00:46:00,100
>> Ale to było sprzeczne z celem przyspieszenia rzeczy.

765
00:46:00,100 --> 00:46:02,530
Więc co, jeśli zamiast tego wprowadził trzeci wymiar?

766
00:46:02,530 --> 00:46:06,400
Ta technika jest powszechnie nazywany oddzielny łańcuchowym lub posiadanie łańcuchów.

767
00:46:06,400 --> 00:46:10,030
A co teraz jest hash table to tabelaryczne struktura,

768
00:46:10,030 --> 00:46:13,450
Twoja tabela jest tylko tablica wskaźników.

769
00:46:13,450 --> 00:46:18,230
Ale co te wskaźniki wskazują na to wiecie co?

770
00:46:18,230 --> 00:46:21,970
Połączonej listy. Więc co, jeśli weźmiemy najlepsze z obu tych światów?

771
00:46:21,970 --> 00:46:26,500
Używamy tablice dla początkowych indeksów

772
00:46:26,500 --> 00:46:32,070
do struktury danych, dzięki czemu możemy od razu przejść do [0] [1], [30], lub tak dalej,

773
00:46:32,070 --> 00:46:36,480
ale tak, że mamy pewną elastyczność i możemy dopasować Anita i Alice i Adam

774
00:46:36,480 --> 00:46:38,630
oraz wszelkie inne imię,

775
00:46:38,630 --> 00:46:43,470
my zamiast pozwolić drugiej osi rosnąć dowolnie.

776
00:46:43,470 --> 00:46:47,340
I wreszcie, jak w poniedziałek, że ma zdolność wyrazu z połączonej listy.

777
00:46:47,340 --> 00:46:49,530
Możemy rozwijać strukturę danych arbitralnie.

778
00:46:49,530 --> 00:46:52,450
Alternatywnie, można po prostu zrobić ogromny 2-wymiarowej tablicy,

779
00:46:52,450 --> 00:46:57,190
ale że będzie okropna sytuacja, gdy jeden z wierszy w tablicy 2-wymiarowej

780
00:46:57,190 --> 00:47:01,280
nie jest wystarczająco duży dla dodatkowej osoby, której nazwisko dzieje zacząć A.

781
00:47:01,280 --> 00:47:04,200
Boże broń mamy do realokacji ogromny 2-wymiarową strukturę

782
00:47:04,200 --> 00:47:06,600
tylko dlatego, że jest tak wielu ludzi, nazwanych

783
00:47:06,600 --> 00:47:09,480
zwłaszcza gdy jest tak mało ludzi nazwanych coś Z.

784
00:47:09,480 --> 00:47:12,170
To jest po prostu będzie bardzo rzadki struktura danych.

785
00:47:12,170 --> 00:47:15,400
Więc to nie jest idealne w jakikolwiek sposób, ale teraz przynajmniej mają możliwość

786
00:47:15,400 --> 00:47:19,090
aby natychmiast znaleźć gdzie Alice lub Anita należy,

787
00:47:19,090 --> 00:47:21,090
co najmniej w odniesieniu do osi pionowej,

788
00:47:21,090 --> 00:47:25,850
i wtedy tylko zdecydować, gdzie umieścić Anita lub Alice w tej połączonej listy.

789
00:47:25,850 --> 00:47:32,480
Jeśli nie dbamy o sortowaniu rzeczy, jak szybko możemy wstawić Alicję w strukturze jak ta?

790
00:47:32,480 --> 00:47:35,370
To jest stała czasowa. Mamy indeks do [0], a jeśli nikt nie jest tam,

791
00:47:35,370 --> 00:47:37,550
Alicja idzie na początku związaną listy.

792
00:47:37,550 --> 00:47:40,000
Ale to nie jest wielka sprawa. Bo jeśli Anita potem przychodzi

793
00:47:40,000 --> 00:47:42,160
pewna liczba kroków później, skąd Anita należą?

794
00:47:42,160 --> 00:47:45,140
Cóż, [0]. OOP. Alicja jest już w tym związane listy.

795
00:47:45,140 --> 00:47:47,760
>> Ale jeśli nie dbamy o sortowaniu te nazwy,

796
00:47:47,760 --> 00:47:53,580
możemy po prostu przejść nad, Alice insert Anita, ale nawet to jest stała czasowa.

797
00:47:53,580 --> 00:47:57,010
Nawet jeśli jest Alice i Adam i wszystkie te inne A imiona,

798
00:47:57,010 --> 00:47:59,410
To naprawdę nie jest przesunięcie ich fizycznie. Dlaczego?

799
00:47:59,410 --> 00:48:04,090
Bo po prostu nie tutaj z połączonej listy, kto wie były węzły te są tak?

800
00:48:04,090 --> 00:48:06,550
Wszystko co musisz zrobić, to przenieść bułkę tartą.

801
00:48:06,550 --> 00:48:10,930
Przesuń strzałki wokół, nie trzeba fizycznie przenieść żadnych danych wokół.

802
00:48:10,930 --> 00:48:14,610
Więc możemy wstawić Anita, w tym przypadku, natychmiast. Stała czas.

803
00:48:14,610 --> 00:48:20,250
Więc mamy stałej czasowej i stałej odnośnika czasie wkładanie kogoś takiego jak Anita.

804
00:48:20,250 --> 00:48:22,740
Ale rodzaj upraszczasz świat.

805
00:48:22,740 --> 00:48:28,510
Co jeśli później chcesz znaleźć Alice?

806
00:48:28,510 --> 00:48:31,050
Co jeśli później chcesz znaleźć Alice?

807
00:48:31,050 --> 00:48:35,690
Ile kroków jest to, że zajmie?

808
00:48:35,690 --> 00:48:37,850
[Odpowiedź Student, niezrozumiały]

809
00:48:37,850 --> 00:48:40,950
Dokładnie. Liczba osób, przed Alicją w połączonej listy.

810
00:48:40,950 --> 00:48:45,420
Więc to nie jest całkiem doskonały, bo nasza struktura danych, ponownie, ma ten pionowy dostęp

811
00:48:45,420 --> 00:48:50,240
i wtedy ma te połączone życzeń wiszące - faktycznie, niech nie rysować tablicy.

812
00:48:50,240 --> 00:48:56,020
Ma te związane Listy zawieszony z tego, że wygląda trochę coś takiego.

813
00:48:56,020 --> 00:48:59,110
Ale problemem jest to, czy Alice i Adam i wszystkie te inne nazwy A

814
00:48:59,110 --> 00:49:01,720
skończyć się coraz więcej tam,

815
00:49:01,720 --> 00:49:04,810
znalezienie kogoś może skończyć biorąc kilka kroków,

816
00:49:04,810 --> 00:49:06,670
bcause trzeba przemierzać listę,

817
00:49:06,670 --> 00:49:08,090
które jest liniowa praca.

818
00:49:08,090 --> 00:49:14,270
Tak bardzo, to czas jest ostatecznie wstawiania O (n), gdzie n jest liczbą elementów listy.

819
00:49:14,270 --> 00:49:21,780
Podzielone przez, powiedzmy dowolnie nazwać m, gdzie m jest liczbą połączonych list

820
00:49:21,780 --> 00:49:24,500
, że ma w osi pionowej.

821
00:49:24,500 --> 00:49:27,180
Innymi słowy, jeśli rzeczywiście przyjąć równomierne nazw,

822
00:49:27,180 --> 00:49:30,150
całkowicie nierealne. Jest oczywiście bardziej niektórych literami od innych.

823
00:49:30,150 --> 00:49:32,580
>> Ale jeśli założymy na moment dystrybucji jednolity,

824
00:49:32,580 --> 00:49:37,350
i mamy n osób, a ogółem m Łączna łańcuchy

825
00:49:37,350 --> 00:49:40,630
nas dostępne, to długość każdego z tych łańcuchów

826
00:49:40,630 --> 00:49:44,380
raczej tylko będzie łączna, podzielone przez n liczbę łańcuchów.

827
00:49:44,380 --> 00:49:48,900
Więc n / m. Ale tu, gdzie możemy być wszystko matematycznie sprytny.

828
00:49:48,900 --> 00:49:53,030
m jest stała, bo jest ustalona liczba tych.

829
00:49:53,030 --> 00:49:54,620
Masz zamiar zadeklarować tablicę na początku,

830
00:49:54,620 --> 00:49:58,450
i nie jesteśmy rozmiaru pionową. Zgodnie z definicją, która pozostaje stała.

831
00:49:58,450 --> 00:50:01,220
To tylko oś pozioma, że ​​tak powiem, to się zmienia.

832
00:50:01,220 --> 00:50:04,760
Więc technicznie, to jest stała. Więc teraz, czas wstawiania

833
00:50:04,760 --> 00:50:09,700
jest dość dużo, O (n).

834
00:50:09,700 --> 00:50:12,410
Tak, że nie czuje się aż tak dużo lepiej.

835
00:50:12,410 --> 00:50:14,940
Ale co prawda, tutaj? Cóż, przez cały ten czas, na tydzień,

836
00:50:14,940 --> 00:50:20,640
byliśmy mówiąc O (n ²). O (n), 2 x N ², - N, podzielona przez 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
To jest po prostu n ². Ale teraz, w tej części semestru,

838
00:50:23,580 --> 00:50:25,560
możemy zacząć mówić o prawdziwym świecie ponownie.

839
00:50:25,560 --> 00:50:31,520
I N / m jest absolutnie szybciej niż sama tylko n.

840
00:50:31,520 --> 00:50:35,170
Jeśli masz tysiąc nazwisk i złamać je na kilka wiader

841
00:50:35,170 --> 00:50:37,820
tak, że masz tylko dziesięć nazwisk w każdej z tych łańcuchów,

842
00:50:37,820 --> 00:50:41,670
absolutnie szukają dziesięć rzeczy będzie szybszy niż tysiąc rzeczy.

843
00:50:41,670 --> 00:50:43,740
I tak jeden z najbliższych zbiorów problemowych będzie wyzwanie

844
00:50:43,740 --> 00:50:46,100
myśleć o tym dokładnie, że nawet jeśli tak,

845
00:50:46,100 --> 00:50:49,520
asymptotycznie i matematycznie, to nadal jest tylko liniowe,

846
00:50:49,520 --> 00:50:51,700
który ssie w ogóle, gdy próbuje znaleźć rzeczy.

847
00:50:51,700 --> 00:50:54,530
W rzeczywistości, to będzie szybciej niż

848
00:50:54,530 --> 00:50:56,520
z powodu tego dzielnik.

849
00:50:56,520 --> 00:50:58,310
A więc znowu będzie to kompromis

850
00:50:58,310 --> 00:51:01,390
i ten konflikt między teorią a rzeczywistością,

851
00:51:01,390 --> 00:51:03,550
i jeden z haczyków rozpocznie obracanie w tym momencie w połowie

852
00:51:03,550 --> 00:51:07,510
jest bardziej rzeczywistości jeden jak rodzaj przygotowania do końca semster się,

853
00:51:07,510 --> 00:51:09,280
jak wprowadzenie w świat programowania WWW,

854
00:51:09,280 --> 00:51:11,530
gdzie naprawdę wydajność będzie się liczyć, ponieważ użytkownicy będą

855
00:51:11,530 --> 00:51:14,880
zaczynam czuć i docenić błędne decyzje projektowe.

856
00:51:14,880 --> 00:51:19,950
>> Więc w jaki sposób przejść o implementowaniu linked - hash tabeli z 31 elementów?

857
00:51:19,950 --> 00:51:22,600
I poprzedni przykład był arbitralnie o urodzinach.

858
00:51:22,600 --> 00:51:26,190
Jeśli ktoś ma urodziny 01 stycznia i 01 lutego, będziemy je w tym wiadrze.

859
00:51:26,190 --> 00:51:28,960
Jeśli to 2 stycznia, 2 lutego, 2 marca, będziemy je w tym wiadrze.

860
00:51:28,960 --> 00:51:32,220
Dlatego to było 31. Jak można zadeklarować tabeli mieszania?

861
00:51:32,220 --> 00:51:37,480
To może być całkiem proste, node * Tabela jest mój arbitralny dla niego nazwy, [31].

862
00:51:37,480 --> 00:51:42,400
To daje mi 31 wskaźniki do węzłów

863
00:51:42,400 --> 00:51:45,370
i to pozwala mi mieć 31 odnośniki do powiązanych list

864
00:51:45,370 --> 00:51:48,800
nawet jeśli te łańcuchy są początkowo NULL.

865
00:51:48,800 --> 00:51:54,860
Czego chcę postawić, jeśli chcę zapisać "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Cóż, musimy otoczyć te rzeczy w strukturze

867
00:51:57,010 --> 00:52:00,530
ponieważ trzeba Alice wskazać Boba wskazać Charlie, i tak dalej.

868
00:52:00,530 --> 00:52:04,940
Nie możemy po prostu nazwy sam, więc mogłem stworzyć nową strukturę o nazwie węzła tutaj.

869
00:52:04,940 --> 00:52:08,310
>> Jaki jest rzeczywisty węzeł? Co to jest węzeł w nowej listy powiązane?

870
00:52:08,310 --> 00:52:11,840
Pierwszą rzeczą, o nazwie słowo jest nazwisko osoby.

871
00:52:11,840 --> 00:52:14,340
DŁUGOŚĆ przypuszczalnie odnosi się do maksymalnej długości ludzkiego imienia,

872
00:52:14,340 --> 00:52:18,210
co, który jest, 20, 30, 40 w postaci szalonych przypadkach narożnych

873
00:52:18,210 --> 00:52:22,680
i +1 to za co? To jest po prostu dodatkowy znak NULL, \ 0.

874
00:52:22,680 --> 00:52:27,410
Więc to jest węzeł pakowania "coś" wewnątrz siebie,

875
00:52:27,410 --> 00:52:29,640
ale również deklaruje wskaźnik o nazwie obok

876
00:52:29,640 --> 00:52:32,580
tak, że możemy łańcuch Alice do Boba do Charliego i tak dalej.

877
00:52:32,580 --> 00:52:36,700
Może mieć wartość NULL, ale nie musi być.

878
00:52:36,700 --> 00:52:40,110
Wszelkie pytania dotyczące tych tabel hash? Tak?

879
00:52:40,110 --> 00:52:46,190
[Student pyta pytanie, niezrozumiały] array - dobre pytanie.

880
00:52:46,190 --> 00:52:50,120
Dlaczego jest to char słowo w tablicy, a nie tylko char *?

881
00:52:50,120 --> 00:52:53,830
W tym przykładzie nieco arbitralny, nie chce mieć do uciekania

882
00:52:53,830 --> 00:52:56,190
malloc dla każdego z oryginalnymi nazwami.

883
00:52:56,190 --> 00:52:59,530
Chciałem zadeklarować maksymalną ilość pamięci dla ciągu

884
00:52:59,530 --> 00:53:06,020
abym mógł skopiować do struktury Alice \ 0 i nie mieć do czynienia z malloc, wolnych i jak.

885
00:53:06,020 --> 00:53:11,710
Ale mogę to zrobić, jeśli chcę być bardziej świadomi wykorzystania przestrzeni. Dobre pytanie.

886
00:53:11,710 --> 00:53:14,780
Więc spróbujmy generalizować z dala od tego

887
00:53:14,780 --> 00:53:18,350
i skupić resztę dzisiaj na strukturach danych ogólnie

888
00:53:18,350 --> 00:53:21,170
i inne problemy, które można rozwiązać za pomocą tych samych podstaw

889
00:53:21,170 --> 00:53:24,590
chociaż struktury danych może się różnić w swoich szczegółowych.

890
00:53:24,590 --> 00:53:27,910
>> Okazuje się w informatyce, drzewa są bardzo powszechne.

891
00:53:27,910 --> 00:53:29,760
A może myślisz o jakimś drzewie jak drzewa genealogicznego,

892
00:53:29,760 --> 00:53:31,830
gdzie jest jakieś korzenie, niektóre matriarch lub patriarcha,

893
00:53:31,830 --> 00:53:34,540
babcia lub dziadek lub wcześniej z powrotem,

894
00:53:34,540 --> 00:53:38,880
pod które mama i tata lub różne rodzeństwo lub podobne.

895
00:53:38,880 --> 00:53:42,500
Tak więc struktura drzewa ma węzły i ma dzieci,

896
00:53:42,500 --> 00:53:45,260
zazwyczaj 0 lub więcej dzieci, dla każdego węzła.

897
00:53:45,260 --> 00:53:47,320
A niektóre z żargonu, który widzisz na obrazku tutaj

898
00:53:47,320 --> 00:53:50,630
jest każdy z tych małych dzieci lub wnuków na krawędziach

899
00:53:50,630 --> 00:53:52,330
którzy nie mają strzałki emanujące od nich,

900
00:53:52,330 --> 00:53:55,070
są to tzw liście i każdy w środku

901
00:53:55,070 --> 00:53:58,790
jest wewnętrzny węzeł, można nazwać to coś wzdłuż tych linii.

902
00:53:58,790 --> 00:54:01,430
Jednak struktura ta jest dość powszechne. Ten jest trochę przypadkowe.

903
00:54:01,430 --> 00:54:04,930
Mamy jedno dziecko, po lewej stronie, mamy troje dzieci, po prawej stronie,

904
00:54:04,930 --> 00:54:06,830
dwoje dzieci, na dole po lewej stronie.

905
00:54:06,830 --> 00:54:10,740
Tak więc możemy mieć różne wielkości drzewa, ale jeśli zaczniemy do ujednolicenia rzeczy,

906
00:54:10,740 --> 00:54:15,330
i może pamiętacie to z filmu Patryka binarnego wyszukiwania z ostatnich krótki

907
00:54:15,330 --> 00:54:19,490
online, binary search nie musi być realizowane z tablicy

908
00:54:19,490 --> 00:54:21,410
lub kawałki papieru na tablicy.

909
00:54:21,410 --> 00:54:25,490
Załóżmy, że chcesz przechowywać liczb w bardziej wyrafinowane struktury danych.

910
00:54:25,490 --> 00:54:27,680
Można utworzyć drzewo takiego.

911
00:54:27,680 --> 00:54:35,290
Można mieć węzeł zadeklarowanych w C, i że węzeł może mieć co najmniej dwa elementy w jej wnętrzu.

912
00:54:35,290 --> 00:54:39,470
Jednym z nich jest numer, który chcesz zapisać, a drugi jest - dobrze, potrzebujemy jeszcze jednego.

913
00:54:39,470 --> 00:54:41,540
Drugi to jego dzieci.

914
00:54:41,540 --> 00:54:45,150
Tak tu jest inna struktura danych. Tym razem, jest zdefiniowany jako węzła przechowywania liczbę n

915
00:54:45,150 --> 00:54:49,060
a następnie dwa wskaźniki, lewy i prawy, dziecko, dziecko.

916
00:54:49,060 --> 00:54:52,100
I nie są arbitralne. Co ciekawe o tym drzewie?

917
00:54:52,100 --> 00:55:00,550
>> Co znajduje się wzór, w jaki sposób mamy określić ten limit lub jak Patrick położył go w swoim filmie?

918
00:55:00,550 --> 00:55:02,790
Jest raczej oczywiste, że istnieje pewne sortowania dzieje,

919
00:55:02,790 --> 00:55:04,460
ale co to jest prosta zasada? Tak?

920
00:55:04,460 --> 00:55:08,350
[Odpowiedź Student, niezrozumiały]

921
00:55:08,350 --> 00:55:12,040
Perfect. Jeśli spojrzeć na to, można zobaczyć małe numery na lewej stronie,

922
00:55:12,040 --> 00:55:14,690
duże cyfry na lewo, ale to jest prawdziwe dla każdego węzła.

923
00:55:14,690 --> 00:55:20,370
Dla każdego węzła, jego lewa dziecko poniżej niego, a jego prawo dziecko powyżej niego.

924
00:55:20,370 --> 00:55:25,210
Co to oznacza to, jeśli chcę szukać tej strukturze danych, powiedzmy, numer 44,

925
00:55:25,210 --> 00:55:29,320
Muszę zacząć od podstaw, bo jak z tych wszystkich bardziej złożonych struktur danych teraz,

926
00:55:29,320 --> 00:55:31,910
mamy tylko wskaźnik do jednej rzeczy, początek.

927
00:55:31,910 --> 00:55:35,010
I w tym przypadku, jest to początek główny. Nie lewy koniec jest,

928
00:55:35,010 --> 00:55:39,530
to jest korzeń tej struktury. Widzę tu jest 55, a ja szukam 44.

929
00:55:39,530 --> 00:55:41,430
W jakim kierunku chcę iść?

930
00:55:41,430 --> 00:55:45,680
Cóż, chcę iść na lewo, bo oczywiście, na prawo będzie zbyt duży.

931
00:55:45,680 --> 00:55:49,050
Więc tutaj odnotować, że jesteś rodzaju koncepcyjnie rąbanie drzewa w pół

932
00:55:49,050 --> 00:55:51,700
bo nigdy nie będziemy w dół do prawej strony.

933
00:55:51,700 --> 00:55:55,410
Więc teraz przejść od 55 do 33. Jest zbyt mały liczby.

934
00:55:55,410 --> 00:56:01,590
Szukam 44, ale teraz wiem, czy 44 jest w tym drzewie, mogę oczywiście prawo.

935
00:56:01,590 --> 00:56:04,460
Więc jeszcze raz, jestem cięcia drzewa w pół.

936
00:56:04,460 --> 00:56:06,780
To jest prawie identyczne koncepcyjnie do książki telefonicznej.

937
00:56:06,780 --> 00:56:09,510
To jest identyczna, co zrobiliśmy z papierami na tablicy,

938
00:56:09,510 --> 00:56:13,940
ale jest to bardziej skomplikowane struktury, która pozwala nam na faktycznie

939
00:56:13,940 --> 00:56:16,880
to dziel i rządź o konstrukcji algorytmu,

940
00:56:16,880 --> 00:56:19,420
i faktycznie, przemierzając strukturę tak - ups.

941
00:56:19,420 --> 00:56:22,870
Przejazd strukturę jak ten, gdzie jest to tylko "iść tą drogą lub przejść w ten sposób"

942
00:56:22,870 --> 00:56:26,870
Oznacza to, cały ten kod pochyliła swój umysł najpierw podczas jej wdrażania w sekcji

943
00:56:26,870 --> 00:56:31,270
lub przechodzenia przez nią w domu, dla binarnego wyszukiwania, używając rekursji lub iteracji,

944
00:56:31,270 --> 00:56:35,060
to jest ból w szyi. Znajdź środkowy element, a następnie wykonać zaokrąglenie w górę lub w dół.

945
00:56:35,060 --> 00:56:39,230
>> Jest piękno na to, ponieważ możemy teraz używać rekursji ponownie

946
00:56:39,230 --> 00:56:43,760
ale o wiele bardziej czysto. Rzeczywiście, jeśli jesteś pod numerem 55, a chcesz znaleźć 44,

947
00:56:43,760 --> 00:56:48,450
idziesz w lewo w tym przypadku, to co robisz? Uruchomić dokładnie ten sam algorytm.

948
00:56:48,450 --> 00:56:51,560
Sprawdzić wartość węzła, a następnie przejść w lewo lub w prawo.

949
00:56:51,560 --> 00:56:53,670
Następnie sprawdzić wartość węzła, przejdź w lewo lub w prawo.

950
00:56:53,670 --> 00:56:56,710
Jest to doskonale nadaje się do rekurencji.

951
00:56:56,710 --> 00:57:00,920
Więc nawet jeśli w przeszłości zrobiliśmy kilka dość dowolne przykłady obejmujące rekursji

952
00:57:00,920 --> 00:57:03,430
że nie trzeba być rekurencyjne, z Konstrukcje danych,

953
00:57:03,430 --> 00:57:07,820
szczególnie drzewa, jest to idealne zastosowanie tego pomysłu biorąc wątpliwości

954
00:57:07,820 --> 00:57:12,920
kurczy, a następnie rozwiązywanie tego samego rodzaju, ale mniejsze, program.

955
00:57:12,920 --> 00:57:14,590
>> Więc nie ma innej struktury danych, które możemy wprowadzić.

956
00:57:14,590 --> 00:57:18,760
Ten przeznaczony jest na pierwszy rzut oka wyglądają tajemnicze, ale to jest niesamowite.

957
00:57:18,760 --> 00:57:25,090
Więc jest to struktura danych o nazwie trie, trie, która jest dziedziczona z wyszukiwania tekstu,

958
00:57:25,090 --> 00:57:30,210
który nie jest wymawiane ponowić-Val, ale to, co świat nazywa te rzeczy. Próbuje. T-i-R-E.

959
00:57:30,210 --> 00:57:35,190
Jest to struktura, drzewo, pewnego rodzaju, ale każdego z węzłów w Trie

960
00:57:35,190 --> 00:57:41,280
Wydaje się, że co? I to jest nieco mylące, ponieważ jest to rodzaj skróconej.

961
00:57:41,280 --> 00:57:45,960
Ale wygląda na to, każdy węzeł w Trie jest rzeczywiście tablicą.

962
00:57:45,960 --> 00:57:48,840
I mimo, że autor tego schematu nie wykazał go,

963
00:57:48,840 --> 00:57:54,130
w tym przypadku, to trie to struktura danych, którego celem w życiu jest do przechowywania słowa

964
00:57:54,130 --> 00:57:57,330
jak l-i-C-E-lub o-B-B.

965
00:57:57,330 --> 00:58:02,480
A sposób, w jaki te dane przechowuje Alicja i Bob i Charlie i Anita i tak dalej

966
00:58:02,480 --> 00:58:06,970
jest wykorzystuje tablicę której przechowywać Alicję w Trie,

967
00:58:06,970 --> 00:58:09,820
zaczniemy od korzenia, który wygląda jak tablica,

968
00:58:09,820 --> 00:58:12,080
i to zostało napisane w notacji skróconej.

969
00:58:12,080 --> 00:58:15,070
Autor pomija abcdefg, ponieważ nie było nazwiska z tym.

970
00:58:15,070 --> 00:58:19,150
Oni tylko pokazał M i P i T, ale w tym przypadku,

971
00:58:19,150 --> 00:58:22,780
Przejdźmy od Alice i Bob i Charlie do niektórych nazwisk, które są tutaj.

972
00:58:22,780 --> 00:58:25,670
Maxwell jest rzeczywiście w tym schemacie.

973
00:58:25,670 --> 00:58:29,570
Jak więc magazyn autor M--x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
On lub ona rozpocząć od korzenia, i udał się do [M], więc mniej więcej 13, 13 miejsce w tablicy.

975
00:58:36,990 --> 00:58:40,750
Następnie stamtąd, jest wskaźnik.

976
00:58:40,750 --> 00:58:42,760
Pointer prowadzi do innej tablicy.

977
00:58:42,760 --> 00:58:47,880
Stamtąd autor indeksowane do tej tablicy w miejscu A, jak pokazano tam na górze po lewej stronie,

978
00:58:47,880 --> 00:58:52,250
a następnie on lub ona następnie, że wskaźnik do innej tablicy,

979
00:58:52,250 --> 00:58:55,460
i udał się do wskaźnika w miejscu X.

980
00:58:55,460 --> 00:58:59,840
Potem w następnym położeniu W tablicy, E, L, L, i tak dalej,

981
00:58:59,840 --> 00:59:03,090
i wreszcie, niech faktycznie spróbować umieścić zdjęcie tego.

982
00:59:03,090 --> 00:59:05,380
Co robi węzeł wygląda w kodzie?

983
00:59:05,380 --> 00:59:11,820
Węzeł w Trie zawiera tablicę wskaźników do innych węzłów.

984
00:59:11,820 --> 00:59:16,090
Ale jest też, że musi być jakaś wartość logiczna, przynajmniej w tej implementacji.

985
00:59:16,090 --> 00:59:18,770
Tak się nazywają to is_word. Dlaczego?

986
00:59:18,770 --> 00:59:22,670
Bo kiedy wstawiasz Maxwell, nie jesteś włożeniem

987
00:59:22,670 --> 00:59:25,300
nic do tej struktury danych.

988
00:59:25,300 --> 00:59:27,480
Nie piszesz M. nie piszesz X.

989
00:59:27,480 --> 00:59:30,240
Wszystko co robisz jest po wskazówki.

990
00:59:30,240 --> 00:59:33,360
Wskaźnik, który reprezentuje m, to wskaźnik, który reprezentuje,

991
00:59:33,360 --> 00:59:36,310
Następnie wskaźnik, który reprezentuje X, a następnie W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
ale to, co trzeba zrobić, w końcu to rodzaj przejść, sprawdzić, dotarłem tej lokalizacji.

993
00:59:41,950 --> 00:59:45,560
Nie było słowa, które kończy się tutaj w strukturze danych.

994
00:59:45,560 --> 00:59:48,190
>> Więc co trie naprawdę wypełnione i autor wybrał do reprezentowania

995
00:59:48,190 --> 00:59:51,880
te terminuses z niewielką trójkątów.

996
00:59:51,880 --> 00:59:56,470
To po prostu oznacza, że ​​fakt ten trójkąt jest tutaj, to wartość logiczna true

997
00:59:56,470 --> 00:59:59,200
Oznacza to, jeśli pójdziesz tyłem w drzewo,

998
00:59:59,200 --> 01:00:02,420
co oznacza, że ​​słowo o nazwie Maxwell jest w tym.

999
01:00:02,420 --> 01:00:04,870
Lecz słowo foo, np.

1000
01:00:04,870 --> 01:00:07,970
nie jest w drzewie, bo jeśli zaczynają się korzenia tu na górze,

1001
01:00:07,970 --> 01:00:14,030
Nie ma wskaźnik f, nie wskaźnik o, nie wskaźnik o. Foo nie nazwa tego słownika jest.

1002
01:00:14,030 --> 01:00:22,460
Ale w przeciwieństwie, Turing, U-T-I-R-N-G. Znowu, nie przechowuj T lub U lub R lub I lub N lub G.

1003
01:00:22,460 --> 01:00:29,820
Ale zrobiłem sklep w tej struktury danych wartość prawdziwej drogi w tym miejscu węzła - w drzewie

1004
01:00:29,820 --> 01:00:33,030
poprzez ustawienie tej wartości is_word logiczną true.

1005
01:00:33,030 --> 01:00:35,740
Więc trie jest rodzaj tej bardzo ciekawej strukturze meta

1006
01:00:35,740 --> 01:00:39,810
jeżeli nie jesteś naprawdę przechowywania samych słów dla tego rodzaju słownika.

1007
01:00:39,810 --> 01:00:45,100
Aby być jasne, jesteś po prostu przechowywanie tak lub nie, nie jest to słowo, które kończy się tutaj.

1008
01:00:45,100 --> 01:00:46,430
>> Teraz, co jest implikacja?

1009
01:00:46,430 --> 01:00:51,120
Jeśli masz 150.000 słowa w słowniku, który próbujesz zapisać w pamięci

1010
01:00:51,120 --> 01:00:53,400
używając coś jak połączonej listy,

1011
01:00:53,400 --> 01:00:56,870
będziesz mieć 150.000 węzły w połączonej listy.

1012
01:00:56,870 --> 01:01:00,250
I znalezienie jednego z tych słów alfabetycznie może potrwać O (n) czasu.

1013
01:01:00,250 --> 01:01:04,370
Czas liniowy. Ale w tym przypadku o Trie,

1014
01:01:04,370 --> 01:01:09,210
co czas pracy na znalezienie słowa?

1015
01:01:09,210 --> 01:01:17,390
Okazuje się, że piękno jest to, że nawet jeśli masz 149.999 słowa już w tym słowniku,

1016
01:01:17,390 --> 01:01:20,170
wykonanego z tej struktury danych,

1017
01:01:20,170 --> 01:01:25,560
ile czasu potrzeba, aby znaleźć lub wstawić jeszcze jedną osobę do, że tak jak Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Cóż, to tylko 5, może 6 kroków do charakteru spływu.

1019
01:01:30,640 --> 01:01:32,880
Ponieważ presense innych nazw w strukturze

1020
01:01:32,880 --> 01:01:35,340
nie dostać w sposób wkładania Alice.

1021
01:01:35,340 --> 01:01:39,640
Ponadto uzyskanie Alice raz jest 150.000 słów w tym słowniku

1022
01:01:39,640 --> 01:01:41,960
nie wchodzić w drogę znalezienia Alice w ogóle,

1023
01:01:41,960 --> 01:01:46,880
bo Alice jest. . . . . tutaj, ponieważ uważam, że wartość logiczną.

1024
01:01:46,880 --> 01:01:50,920
A jeśli nie jest logiczna prawda, Alice nie jest w tej strukturze danych słów.

1025
01:01:50,920 --> 01:01:56,220
Innymi słowy, czas pracy znalezienia rzeczy i wkładając rzeczy do tego nowego

1026
01:01:56,220 --> 01:02:01,920
Struktura danych Trie jest O z - to nie jest n.

1027
01:02:01,920 --> 01:02:05,730
Ponieważ presense 150.000 ludzi nie ma wpływu na Alice wydaje.

1028
01:02:05,730 --> 01:02:11,560
Więc nazwijmy to k, gdzie k jest maksymalna długość słowa w języku angielskim

1029
01:02:11,560 --> 01:02:14,050
które jest zazwyczaj nie więcej niż 20-coś znaków.

1030
01:02:14,050 --> 01:02:17,940
Tak k jest stałą. Więc Święty Graal wydaje się, znalazłem teraz

1031
01:02:17,940 --> 01:02:26,000
jest to, że z trie stałą czasową, wkładki, do wyszukiwania, na delecji.

1032
01:02:26,000 --> 01:02:29,170
Ponieważ liczba rzeczy już struktury,

1033
01:02:29,170 --> 01:02:32,600
, które nie są jeszcze tam fizycznie. Ponownie, oni jakoś zaznaczone, tak lub nie,

1034
01:02:32,600 --> 01:02:35,050
nie ma wpływu na jej przyszłego czasu pracy.

1035
01:02:35,050 --> 01:02:37,940
>> Ale tam musi być jakiś haczyk, w przeciwnym razie nie mielibyśmy tyle czasu zmarnowane

1036
01:02:37,940 --> 01:02:41,460
na wszystkich tych struktur innych danych po prostu się w końcu dostać do tajnego jeden, który jest niesamowity.

1037
01:02:41,460 --> 01:02:46,410
Więc co mamy płacić cenę, aby osiągnąć tę wielkość tutaj? Space.

1038
01:02:46,410 --> 01:02:49,010
Ta rzecz jest ogromny. I dlatego, że autor

1039
01:02:49,010 --> 01:02:52,400
nie przedstawił go tutaj zauważyć, że wszystkie te rzeczy, które wyglądają jak tablice,

1040
01:02:52,400 --> 01:02:55,400
on nie wyciągnął resztę drzewa, reszta Trie,

1041
01:02:55,400 --> 01:02:58,060
ponieważ są one nie tylko istotne dla historii.

1042
01:02:58,060 --> 01:03:01,870
Ale wszystkie te węzły są bardzo szerokie, a każdy węzeł w drzewie zajmuje

1043
01:03:01,870 --> 01:03:07,780
26 lub faktycznie, może być 27 znaków, ponieważ w tym przypadku byłem w tym miejsca dla apostrofu

1044
01:03:07,780 --> 01:03:09,980
tak, że możemy mieć apostrophized słowa.

1045
01:03:09,980 --> 01:03:14,450
W tym przypadku, są szerokie tablice. Więc nawet jeśli nie są one picutured,

1046
01:03:14,450 --> 01:03:18,190
ta zajmuje ogromną ilość pamięci RAM.

1047
01:03:18,190 --> 01:03:20,670
Które mogą być w porządku, especilly w nowoczesnym sprzęcie,

1048
01:03:20,670 --> 01:03:25,650
ale jest to kompromis. Mamy mniej czasu, by spędzać więcej miejsca.

1049
01:03:25,650 --> 01:03:28,580
Więc gdzie jest to wszystko idzie?

1050
01:03:28,580 --> 01:03:32,640
Cóż, zrobić - zobaczymy tutaj.

1051
01:03:32,640 --> 01:03:39,510
Zróbmy skok do tego faceta tutaj.

1052
01:03:39,510 --> 01:03:43,450
>> Wierzcie lub nie, tak zabawne, jak C był już od jakiegoś czasu,

1053
01:03:43,450 --> 01:03:48,130
docieramy do punktu w semestrze, gdzie jest czas na przejście do rzeczy bardziej nowoczesne.

1054
01:03:48,130 --> 01:03:50,950
Rzeczy na wyższym poziomie. I mimo, że przez kilka następnych tygodni

1055
01:03:50,950 --> 01:03:54,580
będziemy nadal, aby zanurzyć się w świecie wskaźników i zarządzanie pamięcią

1056
01:03:54,580 --> 01:03:57,210
aby uzyskać komfort, który możemy następnie budować na,

1057
01:03:57,210 --> 01:04:01,270
rozgrywka jest ostatecznie do wprowadzenia, jak na ironię, nie ten język.

1058
01:04:01,270 --> 01:04:03,330
Spędzimy, jak 10 minut rozmowy na temat języka HTML.

1059
01:04:03,330 --> 01:04:05,950
Wszystkie HTML jest to język znaczników, a co język znaczników jest

1060
01:04:05,950 --> 01:04:10,220
Jest to cykl otwartych uchwytów i wsporników zamkniętych, które mówią, "aby ten bold"

1061
01:04:10,220 --> 01:04:12,000
"Make to kursywa" make to na środku. "

1062
01:04:12,000 --> 01:04:14,250
To nie wszystko, co intelektualnie ciekawa, ale jest to bardzo przydatne.

1063
01:04:14,250 --> 01:04:16,650
I to jest na pewno wszechobecne w tych dniach.

1064
01:04:16,650 --> 01:04:19,450
Ale co jest potężne o świecie HTML i programowania WWW bardziej ogólnie,

1065
01:04:19,450 --> 01:04:25,910
jest budowanie dynamicznych rzeczy, pisania kodu w językach takich jak PHP lub Python lub Ruby lub Java lub C #.

1066
01:04:25,910 --> 01:04:30,360
Naprawdę, bez względu na język z wyboru jest i generowania HTML dynamicznie.

1067
01:04:30,360 --> 01:04:32,960
Generowanie coś o nazwie CSS dynamicznie.

1068
01:04:32,960 --> 01:04:35,810
Kaskadowe arkusze stylów, która jest także o estetyce.

1069
01:04:35,810 --> 01:04:41,360
A więc nawet jeśli dzisiaj, jeśli pójdę do jakiejś witryny, jak znanego Google.com,

1070
01:04:41,360 --> 01:04:46,100
i idę zobaczyć, Developer, pokaż źródło, które może zrobiłeś wcześniej,

1071
01:04:46,100 --> 01:04:49,800
ale się do widoku Source, to rzeczy prawdopodobnie wygląda dość zagadkowych.

1072
01:04:49,800 --> 01:04:55,320
Ale to jest podstawowy kod, który implementuje Google.com.

1073
01:04:55,320 --> 01:04:57,940
Na przednim końcu. I właściwie to wszystko jest puszysty stuff estetyka.

1074
01:04:57,940 --> 01:05:01,740
To jest CSS tutaj. Jeśli będę się przesuwać w dół będziemy trochę kolorami rzeczy.

1075
01:05:01,740 --> 01:05:06,890
To jest HTML. Kod Google wygląda jak bałagan, ale jeśli faktycznie otwarcie innego okna,

1076
01:05:06,890 --> 01:05:09,380
widzimy pewną strukturę tego.

1077
01:05:09,380 --> 01:05:12,640
Jeśli otworzyć tę górę, tutaj odnotować, że to trochę bardziej czytelne.

1078
01:05:12,640 --> 01:05:16,850
Idziemy zobaczyć niedługo ten tag, [słowo] jest tag,

1079
01:05:16,850 --> 01:05:23,520
HTML, głowy, ciała, div, skrypt, obszar tekstu, span, wyśrodkowany div.

1080
01:05:23,520 --> 01:05:26,770
I to jest też coś w rodzaju tajemnicze wyglądający na pierwszy rzut oka

1081
01:05:26,770 --> 01:05:30,890
ale z tego bałaganu następuje pewne wzorce i powtarzalne wzory,

1082
01:05:30,890 --> 01:05:33,850
tak, że gdy mamy podstawy w dół, będziesz mógł napisać kod jak to

1083
01:05:33,850 --> 01:05:37,550
a następnie manipulować kod jak to za pomocą kolejnego języka, zwany JavaScript.

1084
01:05:37,550 --> 01:05:40,440
I JavaScript to język, który działa wewnątrz przeglądarki

1085
01:05:40,440 --> 01:05:44,380
dziś, że używamy na Harvard kursów, dla narzędzia handlowego oczywiście, że używa Google maps

1086
01:05:44,380 --> 01:05:48,660
dać ci całą masę dynamizmu, Facebook daje pokazać natychmiastowe aktualizacje statusu,

1087
01:05:48,660 --> 01:05:51,430
Twitter używa go pokazać tweets natychmiast.

1088
01:05:51,430 --> 01:05:53,820
Wszystko to zaczniemy zanurzyć się w.

1089
01:05:53,820 --> 01:05:57,190
Ale żeby się tam dostać, trzeba zrozumieć co nieco o Internecie.

1090
01:05:57,190 --> 01:06:01,130
Ten klip jest tu po prostu minut długości, a załóżmy, teraz to jest w rzeczywistości,

1091
01:06:01,130 --> 01:06:08,380
jak działa Internet jako teaser tego, co znajduje się przed nami. Daję wam "Warriors of the Net".

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Wolna muzyka chór ♫]

1093
01:06:14,720 --> 01:06:20,450
[Mężczyzna narrator] On przyszedł z wiadomością.

1094
01:06:20,450 --> 01:06:23,770
Z protokołem wszystkie jego własne.

1095
01:06:23,770 --> 01:06:37,270
[♫ Szybciej electronic music ♫]

1096
01:06:37,270 --> 01:06:41,330
On przyszedł na świat chłodnych zapór, niedbały routerów

1097
01:06:41,330 --> 01:06:45,690
i zagrożenia o wiele gorsze niż śmierć.

1098
01:06:45,690 --> 01:06:55,400
Jest szybki. On jest silny. On jest TCP / IP, a on ma swój adres.

1099
01:06:55,400 --> 01:06:59,250
Wojownicy netto.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Następne tygodnie, a następnie. Internet. Programowanie Web. To CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]