1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Tjedan 6, Nastavak]

2
00:00:02,520 --> 00:00:04,160
[David J. Malan] [Sveučilište Harvard]

3
00:00:04,160 --> 00:00:08,720
[Ovo je CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Ovo je CS50 i to je kraj tjedna 6.

5
00:00:12,970 --> 00:00:17,970
Dakle CS50x, jedan od Harvard prvih tečajeva uključeni u inicijativu EDX

6
00:00:17,970 --> 00:00:20,590
Doista je debitirao prošlog ponedjeljka.

7
00:00:20,590 --> 00:00:23,460
Ako želite dobiti uvid u ono što drugima na internetu

8
00:00:23,460 --> 00:00:27,180
sada slijedi uz, možete krenuti na x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
To će vas preusmjeriti na odgovarajuće mjesto na edx.org,

10
00:00:30,350 --> 00:00:34,160
koji je bio gdje je to i drugi predmeti iz MIT-a i Berkeley sada živi.

11
00:00:34,160 --> 00:00:38,140
Morat ćete se prijavili za račun; vidjet ćete da je materijal uglavnom isti

12
00:00:38,140 --> 00:00:42,170
kao što ste imali ovaj semestar, ali nekoliko tjedana kasniti, kao što smo dobili sve spremno.

13
00:00:42,170 --> 00:00:46,930
No, ono što studenti u CS50x sada će se vidjeti je sučelje prilično kao što je ovaj jedan.

14
00:00:46,930 --> 00:00:50,040
To je, na primjer, je Zamyla vodeći prohod za problematiku set 0.

15
00:00:50,040 --> 00:00:54,230
Nakon prijave na edx.org, CS50x učenik vidi i svašta

16
00:00:54,230 --> 00:00:57,170
što bi se očekivati ​​da vidite u tijeku: predavanje za ponedjeljak,

17
00:00:57,170 --> 00:01:01,650
Predavanje za srijedu, razne gaćice, problem setovi, Walkthroughs, PDF-ova.

18
00:01:01,650 --> 00:01:04,459
Osim toga, kao što ste vidjeli ovdje, stroj prijevodi

19
00:01:04,459 --> 00:01:08,390
engleskih transkripata u kineski, japanski, španjolski, talijanski,

20
00:01:08,390 --> 00:01:12,810
i cijela hrpa drugih jezika koje će sigurno biti nesavršen

21
00:01:12,810 --> 00:01:15,840
kao što smo ih razvaljati programski koristeći nešto što se zove API

22
00:01:15,840 --> 00:01:18,360
ili sučelje za programiranje aplikacija, iz Googlea

23
00:01:18,360 --> 00:01:21,360
koji nam omogućava da pretvoriti Engleski ovim drugim jezicima.

24
00:01:21,360 --> 00:01:24,100
No, zahvaljujući prekrasnom duhu nekih sto-plus volontera,

25
00:01:24,100 --> 00:01:26,940
slučajnih ljudi na internetu koji su ljubazno ponudio da se uključe

26
00:01:26,940 --> 00:01:30,180
u ovom projektu, postupno će se poboljšanje kvalitete tih prijevoda

27
00:01:30,180 --> 00:01:35,790
tako da ljudi ispraviti pogreške koje su naši računala napravili.

28
00:01:35,790 --> 00:01:42,330
>> Tako ispada da je još nekoliko studenata pojavio se u ponedjeljak nego što smo prvobitno očekivali.

29
00:01:42,330 --> 00:01:48,980
U stvari, sada CS50x ima 100.000 ljudi sljedeće zajedno kod kuće.

30
00:01:48,980 --> 00:01:54,430
Dakle, shvatili ste svi dio toga nastupni klase izrade ovaj tečaj u informatici

31
00:01:54,430 --> 00:01:57,370
obrazovanje općenito, šire, dostupni.

32
00:01:57,370 --> 00:02:00,130
A realnost je sada, s nekim od tih masivnih online tečajeva,

33
00:02:00,130 --> 00:02:04,070
svi oni početi s tim vrlo visokim brojevima, kao mi se čini da su to učinili ovdje.

34
00:02:04,070 --> 00:02:08,759
No, cilj, u konačnici, za CS50x stvarno dobiti što mnoge ljude do cilja što je više moguće.

35
00:02:08,759 --> 00:02:12,000
Po dizajnu, CS50x će biti ponuđen na ovom prošlom ponedjeljak

36
00:02:12,000 --> 00:02:17,430
sve put kroz 15. travnja 2013, tako da ljudi koji imaju školske obveze drugdje,

37
00:02:17,430 --> 00:02:20,990
posao, obitelj, ostali sukobi i slično, imaju malo više fleksibilnosti

38
00:02:20,990 --> 00:02:23,640
s kojima zaroniti u ovaj tečaj, koji, dovoljno je reći,

39
00:02:23,640 --> 00:02:30,540
je prilično ambiciozno radi samo ako tijekom samo tri mjeseca tijekom uobičajenog semestra.

40
00:02:30,540 --> 00:02:34,190
Ali ti studenti će biti rješavanju istog problema seta, gledanje isti sadržaj,

41
00:02:34,190 --> 00:02:36,350
imaju pristup istim gaćice i slično.

42
00:02:36,350 --> 00:02:38,990
Dakle, shvatili da smo svi doista u to zajedno.

43
00:02:38,990 --> 00:02:42,360
A jedan od krajnjih ciljeva CS50x je ne samo da se što više ljudi

44
00:02:42,360 --> 00:02:45,720
do cilja i dati im ovaj novootkriveni razumijevanje računalnih znanosti

45
00:02:45,720 --> 00:02:49,000
i programiranje, ali i da ih se ovaj zajednički doživljaj.

46
00:02:49,000 --> 00:02:52,010
Jedan od definiranja karakteristika 50 na kampusu, nadamo se,

47
00:02:52,010 --> 00:02:56,260
je ova vrsta komunalne iskustva, za bolje ili za lošije, ponekad,

48
00:02:56,260 --> 00:02:59,480
ali da ti ljudi da se okrenu na lijevoj i na desnoj strani,

49
00:02:59,480 --> 00:03:01,830
i radno vrijeme i hackathon i pošteno.

50
00:03:01,830 --> 00:03:04,560
To je malo teže to učiniti u osobi s ljudi online,

51
00:03:04,560 --> 00:03:10,580
ali CS50x će zaključiti u travnju prvi ikad CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
koji će biti online adaptacija našoj ideji fer

53
00:03:13,630 --> 00:03:18,250
gdje ti tisuće studenata sve će biti pozvani da dostave 1 - do 2-minutnog videa,

54
00:03:18,250 --> 00:03:22,480
bilo Screencast svog konačnog projekta ili video od njih maše pozdraviti

55
00:03:22,480 --> 00:03:24,490
i govori o svojim projektima i to demoing,

56
00:03:24,490 --> 00:03:27,610
baš kao i vaši prethodnici su učinili ovdje na kampusu na sajmu,

57
00:03:27,610 --> 00:03:31,400
tako da po semestru kraja, nada se da imaju globalnu izložbu

58
00:03:31,400 --> 00:03:37,080
od CS50x učeničkih finalnih projekata, slično kao što čeka vas ovaj prosinac ovdje na kampusu.

59
00:03:37,080 --> 00:03:39,680
Dakle, više o tome u mjesecima koji dolaze.

60
00:03:39,680 --> 00:03:43,640
>> Sa 100.000 studenata, ipak, dolazi potreba za još nekoliko CA.

61
00:03:43,640 --> 00:03:47,590
S obzirom da su ti dečki plamen trag ovdje i uzimanje CS50

62
00:03:47,590 --> 00:03:51,630
Nekoliko tjedana prije ovog materijala je puštanje na narod na EDX,

63
00:03:51,630 --> 00:03:55,330
shvatiti voljeli bismo uključiti što veći broj naših studenata što je više moguće u ovoj inicijativi,

64
00:03:55,330 --> 00:03:58,720
kako tijekom semestra, kao i ove zime, a ovaj dolazak proljeća.

65
00:03:58,720 --> 00:04:01,620
Dakle, ako želite da se uključe u CS50x,

66
00:04:01,620 --> 00:04:07,450
Posebno se pridružio u na CS50x raspravljati, EDX verzija CS50 raspravljati,

67
00:04:07,450 --> 00:04:10,140
koji su mnogi od vas su pomoću na kampusu, online oglasne ploče,

68
00:04:10,140 --> 00:04:13,040
molimo učinite glavu na tom URL-u, javite nam tko ste,

69
00:04:13,040 --> 00:04:16,450
jer bismo voljeli da podigne ekipu studenata i osoblja i fakultet podjednako

70
00:04:16,450 --> 00:04:19,630
na kampusu koji jednostavno igraju zajedno i pomaže.

71
00:04:19,630 --> 00:04:21,720
A kad su vidjeli pitanje koji je upoznat s njima,

72
00:04:21,720 --> 00:04:25,320
čujete student izvještavanja neki bug negdje vani u nekoj zemlji na Internetu,

73
00:04:25,320 --> 00:04:27,450
i da zvoni zvono, jer vi imali taj isti problem

74
00:04:27,450 --> 00:04:32,620
u d-dvorani prije nekog vremena, nadam se onda može zvoniti i podijeliti svoje iskustvo.

75
00:04:32,620 --> 00:04:37,300
Dakle, nemojte sudjelovati ako želite.

76
00:04:37,300 --> 00:04:39,360
>> Računalna znanost tečajevi na Harvardu imaju malo tradicije,

77
00:04:39,360 --> 00:04:44,730
CS50 među njima, vlasništvo neke odjeće, nešto odjeće, koje možete nositi s ponosom

78
00:04:44,730 --> 00:04:49,090
u semestru kraja, rekavši prilično ponosno da ste završili CS50

79
00:04:49,090 --> 00:04:51,830
i uzeo CS50 i slično, a mi uvijek pokušati uključiti studente

80
00:04:51,830 --> 00:04:54,540
u tom procesu koliko god je to moguće, pri čemu mi pozivamo,

81
00:04:54,540 --> 00:04:56,900
oko tog vremena semestra, studenti podnijeti dizajna

82
00:04:56,900 --> 00:04:59,330
koristeći Photoshop, ili što god alat izbora želite koristiti

83
00:04:59,330 --> 00:05:02,330
ako ste dizajner, podnijeti dizajna za majice i veste

84
00:05:02,330 --> 00:05:06,100
i suncobrani i malo bandanas za pse sada imamo i slično.

85
00:05:06,100 --> 00:05:09,370
I sve je onda - pobjednici svake godine onda su izloženi

86
00:05:09,370 --> 00:05:12,700
na stazi web stranici store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Sve se prodaje po cijeni tamo, ali samo se radi web stranica

88
00:05:15,790 --> 00:05:18,330
i omogućava ljudima da odaberete boje i dizajna koji im se sviđaju.

89
00:05:18,330 --> 00:05:20,420
Pomislio sam da bih samo podijeliti neke od prošlogodišnjih dizajna

90
00:05:20,420 --> 00:05:25,130
da su na internetskoj stranici osim ove jedne ovdje, što je godišnja tradicija.

91
00:05:25,130 --> 00:05:29,410
"Svaki dan sam SEG Faultn" je bio jedan od podnesaka prošle godine,

92
00:05:29,410 --> 00:05:32,290
koji je još uvijek na raspolaganju ima za alumni.

93
00:05:32,290 --> 00:05:35,820
Imali smo taj jedan, "CS50, osnovana 1989."

94
00:05:35,820 --> 00:05:39,010
Jedan od naših Razmaci, Rob je bio vrlo popularan prošle godine.

95
00:05:39,010 --> 00:05:43,480
"Tim Bowden" rođen, ovaj dizajn je podnesen, među najboljih prodavača.

96
00:05:43,480 --> 00:05:49,040
Kao što je bio ovaj ovdje. Mnogi su ljudi imali "Bowden Fever" prema prodaji trupaca.

97
00:05:49,040 --> 00:05:52,650
Shvatite da je sada mogao biti vaš dizajn tamo, na internetu.

98
00:05:52,650 --> 00:05:57,510
Više pojedinosti o tome u sljedećem problemu postavlja doći.

99
00:05:57,510 --> 00:06:00,330
>> Još jedan alat: vi ste imali neke izloženost i nadamo sada

100
00:06:00,330 --> 00:06:02,350
neki kazaljka-na iskustvo sa GDB,

101
00:06:02,350 --> 00:06:04,570
koji je, naravno, debugger i omogućuje vam da manipuliraju

102
00:06:04,570 --> 00:06:09,500
vaš program na prilično niskoj razini, radi ono što vrste stvari?

103
00:06:09,500 --> 00:06:13,030
Što GDB neka vam je činiti?

104
00:06:13,030 --> 00:06:15,030
Da? Daj mi nešto. [Studentski odgovor, nerazumljivo]

105
00:06:15,030 --> 00:06:18,120
Dobro. Korak u funkciji, tako da ne samo da upišite pokrenuti

106
00:06:18,120 --> 00:06:22,310
i imaju program udarac kroz cijelosti, ispis stvari na standardni izlaz.

107
00:06:22,310 --> 00:06:25,190
Umjesto toga, možete korak kroz to liniju po liniju, ili upisivanjem sljedeće

108
00:06:25,190 --> 00:06:30,300
ići redak po redak po redak ili korak da se upuste u funkciji, obično onaj koji ti napisao.

109
00:06:30,300 --> 00:06:35,240
Što drugo ne GDB neka vam je činiti? Da? [Studentski odgovor, nerazumljivo]

110
00:06:35,240 --> 00:06:38,100
Ispis varijable. Dakle, ako želite napraviti malo introspekcije unutar svog programa

111
00:06:38,100 --> 00:06:41,500
bez posezanja za pisanje printf izjave sve više mjesta,

112
00:06:41,500 --> 00:06:44,600
možete jednostavno ispisati varijablu ili prikazati varijablu.

113
00:06:44,600 --> 00:06:46,710
Što još možete učiniti s debugger poput GDB?

114
00:06:46,710 --> 00:06:49,170
[Studentski odgovor, nerazumljivo]

115
00:06:49,170 --> 00:06:52,080
Točno. Možete postaviti prijelomnih točaka, možete reći prijelom izvršenje

116
00:06:52,080 --> 00:06:54,020
na glavna funkcija ili foo funkciju.

117
00:06:54,020 --> 00:06:56,800
Možete reći prijelom izvršenje na liniji 123.

118
00:06:56,800 --> 00:06:58,950
I prijelomnih točaka su jako moćna tehnika

119
00:06:58,950 --> 00:07:01,110
jer ako imate opći osjećaj gdje je vaš problem

120
00:07:01,110 --> 00:07:05,360
Vjerojatno je, da ne moraju gubiti vrijeme koračni kroz program cijelosti.

121
00:07:05,360 --> 00:07:08,250
Vi zapravo možete skočiti tamo i onda počnite tipkati -

122
00:07:08,250 --> 00:07:10,970
koračni kroz nju s korak ili neposredno ili slično.

123
00:07:10,970 --> 00:07:14,340
No, kvaka s nešto poput GDB je da vam pomaže, ljudsko,

124
00:07:14,340 --> 00:07:16,940
pronaći svoje probleme i naći svoje greške.

125
00:07:16,940 --> 00:07:19,470
To ne mora nužno ih naći toliko za vas.

126
00:07:19,470 --> 00:07:23,070
>> Tako smo uveli drugi dan style50, koji je kratko alat naredbenog retka

127
00:07:23,070 --> 00:07:27,500
koji pokušava stilizovati kôd malo više čisto od vas, čovjek, možda učinio.

128
00:07:27,500 --> 00:07:29,530
Ali to je, također, je zapravo samo estetski stvar.

129
00:07:29,530 --> 00:07:34,110
No, ispostavilo se da je ovo drugi alat zove Valgrind da je malo više kompliciranih koristiti.

130
00:07:34,110 --> 00:07:36,860
Njegova proizvodnja je atrociously grobni na prvi pogled.

131
00:07:36,860 --> 00:07:39,420
Ali to je predivno korisna, pogotovo sada kada smo u dijelu mandata

132
00:07:39,420 --> 00:07:43,080
gdje ste počinju koristiti malloc i dinamička dodjela memorije.

133
00:07:43,080 --> 00:07:45,420
Stvari mogu ići jako, jako krivo brzo.

134
00:07:45,420 --> 00:07:49,320
Jer, ako ste zaboravili osloboditi svoju memoriju, ili ste dereference neke NULL pokazivač,

135
00:07:49,320 --> 00:07:55,770
ili ste dereference neke smeće pokazivač, što je obično simptom koji rezultati?

136
00:07:55,770 --> 00:07:59,470
SEG kvar. A ti ovaj core datoteku nekog broja kilobajta ili megabajtima

137
00:07:59,470 --> 00:08:02,990
koji predstavlja stanje svoga programa memorije kada se srušio,

138
00:08:02,990 --> 00:08:05,730
ali vaš program konačnici SEG mane, segmentacije grešku,

139
00:08:05,730 --> 00:08:08,450
što znači da se nešto loše dogodilo gotovo uvijek povezana

140
00:08:08,450 --> 00:08:11,750
do memorije vezane greške koje ste napravili negdje.

141
00:08:11,750 --> 00:08:14,100
Dakle Valgrind pomaže vam stvari kao što je ovaj.

142
00:08:14,100 --> 00:08:17,720
To je alat koji naiđete, poput GDB, nakon što ste sastavili svoj program,

143
00:08:17,720 --> 00:08:20,330
ali umjesto da pokrenete svoj program izravno, naiđete Valgrind

144
00:08:20,330 --> 00:08:23,960
i da prođe na njega svoj program, baš kao što učiniti s GDB.

145
00:08:23,960 --> 00:08:26,220
Sada, korištenje, kako bi dobili najbolju vrstu proizvodnje,

146
00:08:26,220 --> 00:08:30,410
je malo dugo, pa tamo na vrhu na ekranu ćete vidjeti Valgrind-V.

147
00:08:30,410 --> 00:08:35,350
"-V" gotovo univerzalno znači verbose kada koristite programe na Linux računalu.

148
00:08:35,350 --> 00:08:38,770
Dakle, to znači ispljunuti više podataka nego što bi po defaultu.

149
00:08:38,770 --> 00:08:45,510
"- Curenja provjerite = puni." To samo govori provjeru svih mogućih memorijskih curenja,

150
00:08:45,510 --> 00:08:49,430
greške koje sam možda napravio. To je, također, je čest paradigma s Linux programa.

151
00:08:49,430 --> 00:08:52,710
Općenito, ako imate argument naredbenog retka da je "prekidač",

152
00:08:52,710 --> 00:08:55,830
koji je trebao promijeniti program ponašanje, a to je slovo,

153
00:08:55,830 --> 00:09:00,310
to je-v, ali ako to je uključen, samo po dizajnu programera,

154
00:09:00,310 --> 00:09:05,150
je punu riječ ili niz riječi, argument naredbenog retka počinje s -.

155
00:09:05,150 --> 00:09:08,190
Ovo su samo ljudska konvencija, ali vidjet ćete ih sve.

156
00:09:08,190 --> 00:09:12,410
I onda, konačno, "a.out" je proizvoljan naziv za program u ovom konkretnom primjeru.

157
00:09:12,410 --> 00:09:14,640
I ovdje je neki predstavnik izlaz.

158
00:09:14,640 --> 00:09:22,890
>> Prije nego što pogledamo što bi to moglo značiti, da me pusti preko na isječku koda ovamo.

159
00:09:22,890 --> 00:09:26,390
I neka mi premjestiti ovu zabit, uskoro,

160
00:09:26,390 --> 00:09:32,120
i neka je pogledati memory.c, koji je ovaj kratki primjer ovdje.

161
00:09:32,120 --> 00:09:36,290
Dakle, u ovom programu, neka mi povećali na funkcijama i pitanja.

162
00:09:36,290 --> 00:09:39,430
Imamo funkciju glavnog koji poziva funkciju, F,

163
00:09:39,430 --> 00:09:45,590
i što onda ne ž nastaviti raditi, u nešto tehničkoj engleskom?

164
00:09:45,590 --> 00:09:49,760
Što ž nastaviti raditi?

165
00:09:49,760 --> 00:09:53,680
Kako o Ja ću početi s linije 20, a zvijezde lokacija ne smeta,

166
00:09:53,680 --> 00:09:56,720
ali samo ću biti u skladu s ovdje zadnjem predavanju.

167
00:09:56,720 --> 00:09:59,910
Što je linija 20 ne za nas? Na lijevoj strani. Mi ćemo ga razbiti dalje.

168
00:09:59,910 --> 00:10:02,410
Interesi * x: Što to učiniti?

169
00:10:02,410 --> 00:10:04,940
Ok. To je proglašenje pokazivač, a sada budimo još tehnički.

170
00:10:04,940 --> 00:10:10,230
Što to znači, vrlo konkretno, da proglasi pokazivač? Netko drugi?

171
00:10:10,230 --> 00:10:15,050
Da? [Studentski odgovor, nerazumljivo] predaleko.

172
00:10:15,050 --> 00:10:17,060
Pa što čitate na desnoj strani znaka jednakosti.

173
00:10:17,060 --> 00:10:20,290
Neka se usredotočiti samo na lijevoj, samo na int * x.

174
00:10:20,290 --> 00:10:24,700
To znači "proglasi" pokazivač, ali sada neka je roniti u dublje toj definiciji.

175
00:10:24,700 --> 00:10:28,330
Što to konkretno, tehnički znači? Da?

176
00:10:28,330 --> 00:10:31,940
[Studentski odgovor, nerazumljivo]

177
00:10:31,940 --> 00:10:35,090
Ok. To je priprema za spremanje adresu u memoriji.

178
00:10:35,090 --> 00:10:40,680
Dobro. I neka se ovaj jedan korak dalje, to je deklariranje varijabli, X, koji je 32 bita.

179
00:10:40,680 --> 00:10:44,440
I znam da je 32 bita, jer -?

180
00:10:44,440 --> 00:10:47,390
To nije zato što je int, jer je pokazivač u ovom slučaju.

181
00:10:47,390 --> 00:10:49,650
Slučajnost da je jedan te isti s int,

182
00:10:49,650 --> 00:10:51,970
ali je činjenica da postoji zvijezda tamo znači ovo je pokazivač

183
00:10:51,970 --> 00:10:57,300
i uređaja, kao i sa mnogim računalima, ali ne i sve, pokazivači su 32 bita.

184
00:10:57,300 --> 00:11:01,850
Na više modernom hardveru poput najnovijih Mac, najnovije PC, možda ćete imati 64-bitne naputke,

185
00:11:01,850 --> 00:11:04,160
ali u aparatu, te stvari su 32 bita.

186
00:11:04,160 --> 00:11:08,380
Tako ćemo standardizirati na to. Konkretnije, priča ide kako slijedi:

187
00:11:08,380 --> 00:11:10,820
Mi "proglasiti" pokazivač, što to znači?

188
00:11:10,820 --> 00:11:12,810
Mi pripremiti za pohranu memorijsku adresu.

189
00:11:12,810 --> 00:11:15,530
Što to znači?

190
00:11:15,530 --> 00:11:19,810
Mi stvaramo varijablu x koja traje do 32 bita

191
00:11:19,810 --> 00:11:23,810
da će uskoro pohraniti adresu cijeli broj.

192
00:11:23,810 --> 00:11:26,470
I to je vjerojatno oko kao precizan kao što možete dobiti.

193
00:11:26,470 --> 00:11:31,810
To je u redu kreće naprijed pojednostaviti svijet i samo reći proglasiti pokazivač zove x.

194
00:11:31,810 --> 00:11:35,380
Objavite pokazivač, ali shvatite i razumjeti što se zapravo događa na

195
00:11:35,380 --> 00:11:38,490
čak iu samo tih nekoliko likova.

196
00:11:38,490 --> 00:11:42,040
>> Sada, ovo je gotovo malo lakše, iako je to više izraz.

197
00:11:42,040 --> 00:11:48,160
Pa što je ovo događaj, koji je istaknuo sada: "malloc (10 * sizeof (int));" Da?

198
00:11:48,160 --> 00:11:52,350
[Studentski odgovor, nerazumljivo]

199
00:11:52,350 --> 00:11:58,250
Dobro. I ja ću ga odvesti tamo. To je dodjelom komad memorije za deset brojeva.

200
00:11:58,250 --> 00:12:02,190
A sada idemo roniti u nešto dublje, to je dodjelom komad memorije za deset brojeva.

201
00:12:02,190 --> 00:12:05,390
Što je malloc zatim se vraćaju?

202
00:12:05,390 --> 00:12:10,390
Adresa tog komad, ili, konkretnije, adresa prvom bajtu tom komad.

203
00:12:10,390 --> 00:12:14,080
Kako onda sam ja, programer, da znam gdje da komad memorije krajevima?

204
00:12:14,080 --> 00:12:18,340
Znam da je to granično. Malloc, po definiciji, će vam dati granični komad memorije.

205
00:12:18,340 --> 00:12:21,240
Nema praznine u njemu. Imate pristup svakom bajtu u tom komad,

206
00:12:21,240 --> 00:12:26,760
natrag na natrag na leđa, ali kako da znam gdje je kraj ovoj komad memorije je?

207
00:12:26,760 --> 00:12:28,850
Kada koristite malloc? [Studentski odgovor, nerazumljivo] Dobro.

208
00:12:28,850 --> 00:12:30,670
Vi ne. Morate zapamtiti.

209
00:12:30,670 --> 00:12:35,960
Moram se sjetiti da sam koristio vrijednost 10, a ja čak i ne čini se da su to učinili ovdje.

210
00:12:35,960 --> 00:12:41,000
No, teret je u potpunosti na mene. Strlen, koji smo postali malo oslanja na za gudače,

211
00:12:41,000 --> 00:12:45,860
radi samo zbog ove konvencije da \ 0

212
00:12:45,860 --> 00:12:48,840
ili je ovo posebna NUL znak, NSK, na kraju niza.

213
00:12:48,840 --> 00:12:51,740
To ne vrijedi za samo proizvoljnim komade memorije.

214
00:12:51,740 --> 00:12:58,590
To je do vas. Dakle liniji 20, dakle, izdvaja komad memorije

215
00:12:58,590 --> 00:13:02,590
koji se može pohraniti deset cijelih brojeva, i to pohranjuje adresu prvog byte

216
00:13:02,590 --> 00:13:05,610
te komad memorije u varijablu x..

217
00:13:05,610 --> 00:13:11,140
Ergo, što je pokazivač. Dakle liniji 21, na žalost, bio pogreška.

218
00:13:11,140 --> 00:13:16,110
Ali prvo, što se to radi? To govori dućan na lokaciji 10, 0 indeksirane,

219
00:13:16,110 --> 00:13:19,480
o komad memorije zove x vrijednost 0.

220
00:13:19,480 --> 00:13:21,510
>> Dakle primijetiti par stvari se događa.

221
00:13:21,510 --> 00:13:25,420
Iako je x pokazivač, podsjećaju iz prije par tjedana

222
00:13:25,420 --> 00:13:29,440
da još uvijek možete koristiti niz stilu zapis nosača kvadrata.

223
00:13:29,440 --> 00:13:36,180
Jer to je zapravo kratki ruka notacija za više zagonetan izgleda pokazivač aritmetike.

224
00:13:36,180 --> 00:13:40,320
gdje bismo učiniti nešto ovako: Uzmite adresu x, premjestiti 10 mjesta više,

225
00:13:40,320 --> 00:13:44,550
onda ići tamo bez obzira adresa je pohranjena na toj lokaciji.

226
00:13:44,550 --> 00:13:48,090
Ali iskreno, to je samo zločest pročitati i dobiti udoban sa.

227
00:13:48,090 --> 00:13:52,900
Dakle, svijet se obično koristi uglate zagrade samo zato što je tako mnogo više ljudskih-friendly čitati.

228
00:13:52,900 --> 00:13:55,140
Ali to je ono što se stvarno događa ispod haube;

229
00:13:55,140 --> 00:13:58,190
x je adresa, a ne niz, po sebi.

230
00:13:58,190 --> 00:14:02,410
Dakle, ovo je spremanje 0 na mjestu 10 u x..

231
00:14:02,410 --> 00:14:06,120
Zašto je to loše? Da?

232
00:14:06,120 --> 00:14:17,370
[Studentski odgovor, nerazumljivo] Točno.

233
00:14:17,370 --> 00:14:21,100
Mi samo izdvojila deset Ints, ali možemo računati od 0 kada programiranje u C,

234
00:14:21,100 --> 00:14:25,690
tako da imate pristup 0 1 2 3 4 5 6 7 8 9, ali ne i 10.

235
00:14:25,690 --> 00:14:30,270
Dakle, ili program će SEG kriv ili nije.

236
00:14:30,270 --> 00:14:32,900
Ali mi stvarno ne znam, a to je vrsta nedeterminističkim ponašanja.

237
00:14:32,900 --> 00:14:35,600
To stvarno ovisi o tome hoće li nam se posreći.

238
00:14:35,600 --> 00:14:40,650
Ako se ispostavi da je operativni sustav ne smeta ako sam koristiti taj dodatni byte,

239
00:14:40,650 --> 00:14:43,360
iako ga nije dao za mene, moj program ne može srušiti.

240
00:14:43,360 --> 00:14:46,780
To je sirovi, to je lud, ali nije mogao vidjeti da je simptom,

241
00:14:46,780 --> 00:14:48,960
ili možda ćete ga vidjeti samo jednom u neko vrijeme.

242
00:14:48,960 --> 00:14:51,230
No, stvarnost je da je bug je, u stvari, ima.

243
00:14:51,230 --> 00:14:54,320
I to je stvarno problematično ako ste napisali program koji želite biti točni,

244
00:14:54,320 --> 00:14:58,840
da ste prodali program koji ljudi koriste da svaki jednom u neko vrijeme ruši

245
00:14:58,840 --> 00:15:02,450
jer, naravno, to nije dobro. U stvari, ako imate Android telefon ili iPhone

246
00:15:02,450 --> 00:15:05,550
i preuzimanje aplikacije ovih dana, ako ste ikada imali app samo prestati,

247
00:15:05,550 --> 00:15:10,040
sve odjednom nestane, to je gotovo uvijek rezultat neke memorije povezane pitanju,

248
00:15:10,040 --> 00:15:12,830
pri čemu programer zeznuo i dereferenced pokazivač

249
00:15:12,830 --> 00:15:18,670
da on ili ona ne bi trebala imati, a rezultat iOS ili Android je ubijati program uopce

250
00:15:18,670 --> 00:15:23,080
umjesto rizika nedefinirano ponašanje ili neku vrstu sigurnosti kompromisa.

251
00:15:23,080 --> 00:15:25,950
>> Tu je još jedan bug u tom programu, osim ovog jednog.

252
00:15:25,950 --> 00:15:30,180
Što drugo sam zeznuo u ovom programu?

253
00:15:30,180 --> 00:15:32,740
Nisam trenirao ono što sam propovijedao. Da?

254
00:15:32,740 --> 00:15:34,760
[Studentski odgovor, nerazumljivo] Dobro.

255
00:15:34,760 --> 00:15:36,880
Nisam oslobodio memoriju. Dakle, pravilo sada

256
00:15:36,880 --> 00:15:43,150
mora biti u bilo koje vrijeme nazvati malloc, morate nazvati besplatno kada se obavlja pomoću tog memorije.

257
00:15:43,150 --> 00:15:45,610
Sada, kad bih htjela osloboditi tu memoriju?

258
00:15:45,610 --> 00:15:49,780
Vjerojatno, pod pretpostavkom da je ovo prva linija bila točna, ja bi htio to učiniti ovdje.

259
00:15:49,780 --> 00:15:55,710
Budući da nisam mogao, na primjer, to ovdje dolje. Zašto?

260
00:15:55,710 --> 00:15:57,860
Samo iz djelokruga. Dakle, iako govorimo o pokazivače,

261
00:15:57,860 --> 00:16:04,830
ovo je tjedan 2 ili 3 pitanje, gdje je x samo u okviru unutar vitičastih zagrada gdje je proglašen.

262
00:16:04,830 --> 00:16:11,000
Tako da definitivno ne može ga osloboditi tamo. Moja jedina šansa da ga oslobodi je otprilike nakon linije 21.

263
00:16:11,000 --> 00:16:15,170
To je prilično jednostavan program, to je prilično lako nakon što vrsta omotan svoj um

264
00:16:15,170 --> 00:16:17,870
oko čega se program radi, gdje su greške bile.

265
00:16:17,870 --> 00:16:20,500
A čak i ako to nismo vidjeli na početku, nadamo se da je malo očito sada

266
00:16:20,500 --> 00:16:23,870
da ove greške su prilično lako riješiti i jednostavno napravio.

267
00:16:23,870 --> 00:16:28,720
No, kada je program i više od 12 linija dugo, to je 50 redaka dugo, 100 linija dugo,

268
00:16:28,720 --> 00:16:31,150
hodanje kroz koda liniju po liniju, razmišljanja kroz njega logično,

269
00:16:31,150 --> 00:16:35,110
je moguće, ali nije osobito zabavno raditi, stalno u potrazi za bubama,

270
00:16:35,110 --> 00:16:38,340
i to je također teško učiniti, i to je razlog zašto alat poput Valgrind postoji.

271
00:16:38,340 --> 00:16:40,900
Pusti me naprijed i to: neka mi otvoriti moj prozor terminala,

272
00:16:40,900 --> 00:16:45,400
i neka mi ne samo pokrenuti pamćenje, jer memorije čini se da je u redu.

273
00:16:45,400 --> 00:16:49,180
Ja sam uzimajući sretan. Odlazak na tom pomoćnom bajtu na kraju niza

274
00:16:49,180 --> 00:16:51,060
ne čini se previše problematično.

275
00:16:51,060 --> 00:16:56,370
Ali neka mi, ipak, učiniti razum ček, što samo znači da biste provjerili

276
00:16:56,370 --> 00:16:58,320
hoće li ili ne to je zapravo točno.

277
00:16:58,320 --> 00:17:04,690
>> Tako ćemo učiniti valgrind-V - curenja provjerite = puni,

278
00:17:04,690 --> 00:17:07,520
, a zatim naziv programa u ovom slučaju je memorija, a ne a.out.

279
00:17:07,520 --> 00:17:10,760
Pa neka mi ići naprijed i učiniti. Hit Enter.

280
00:17:10,760 --> 00:17:14,109
Dragi Bože. To je njegov izlaz, a to je ono što sam aludirala na ranije.

281
00:17:14,109 --> 00:17:17,550
Ali, ako ste saznali da pročitate kroz sve gluposti ovdje,

282
00:17:17,550 --> 00:17:20,760
većina to je samo dijagnostički izlaz da nije tako zanimljivo.

283
00:17:20,760 --> 00:17:24,829
Što vaše oči stvarno želi biti u potrazi za bilo kakav spomen pogreške ili neispravne.

284
00:17:24,829 --> 00:17:26,800
Riječi koje sugeriraju probleme.

285
00:17:26,800 --> 00:17:29,340
I doista, neka je vidjeti što se događa u krivu ovdje dolje.

286
00:17:29,340 --> 00:17:35,230
Imam sažetak o nekakvoj ", u uporabi na izlazu:. 40 bajtova u jednom blokova"

287
00:17:35,230 --> 00:17:38,750
Nisam siguran što je blok, no 40 bajtova

288
00:17:38,750 --> 00:17:41,260
zapravo osjeća kao što sam mogao shvatiti gdje da dolazi iz.

289
00:17:41,260 --> 00:17:45,030
40 bajtova. Zašto su 40 bajtova u uporabi na izlazu?

290
00:17:45,030 --> 00:17:48,780
I točnije, ako mi dođite ovamo,

291
00:17:48,780 --> 00:17:54,520
Zato sam definitivno izgubio 40 bajtova? Da?

292
00:17:54,520 --> 00:17:59,520
[Studentski odgovor, nerazumljivo] Savršeno. Da, točno.

293
00:17:59,520 --> 00:18:03,540
Bilo je deset cijelih brojeva, a svaki od njih je veličina 4, ili 32 bita,

294
00:18:03,540 --> 00:18:08,300
tako da sam izgubio upravo 40 bajtova jer, kao što ste predložili, nisam pozvan besplatno.

295
00:18:08,300 --> 00:18:13,460
To je jedan bug, a sada pogledajmo što se razbije malo dalje i vidjeti pored toga,

296
00:18:13,460 --> 00:18:16,900
"Nevažeći pisati o veličini četiri." Sada što je to?

297
00:18:16,900 --> 00:18:21,150
Ova adresa je izrazio što osnovni zapis, očito?

298
00:18:21,150 --> 00:18:23,640
Ovo je heksadecimalni, i svaki put kad vidi broj počevši s 0x,

299
00:18:23,640 --> 00:18:29,410
to znači heksadecimalni, što smo radili davne, mislim, pset 0 u dijelu pitanja,

300
00:18:29,410 --> 00:18:34,090
koji je bio samo napraviti vježbe zagrijavanja, pretvaranje decimalnog hex u binarni i tako dalje.

301
00:18:34,090 --> 00:18:39,220
Heksadecimalni, samo ljudske konvenciji, obično se koristi za predstavljanje pokazivače

302
00:18:39,220 --> 00:18:41,570
ili, općenito, obraća. To je samo konvencija,

303
00:18:41,570 --> 00:18:45,340
jer to je malo lakše čitati, to je malo više kompaktan nego nešto poput decimale,

304
00:18:45,340 --> 00:18:47,720
i binarni je beskoristan za većinu ljudi koristiti.

305
00:18:47,720 --> 00:18:50,840
Pa sad, što to znači? Pa, to izgleda kao da je nevažeća zapisivanja

306
00:18:50,840 --> 00:18:54,480
veličine 4 na liniji 21 memory.c.

307
00:18:54,480 --> 00:18:59,180
Dakle, vratimo se na liniji 21, i doista, ovdje je to valjan pisati.

308
00:18:59,180 --> 00:19:02,640
Dakle Valgrind ne ide u potpunosti držite ruku i reći mi ono što je popraviti,

309
00:19:02,640 --> 00:19:05,520
ali to je otkrivanje da radim nevažeći pisati.

310
00:19:05,520 --> 00:19:08,800
Ja sam dira 4 bajta da ne bih trebao biti, i očito da je to zato,

311
00:19:08,800 --> 00:19:13,960
kao što je istaknuo, radim [10] umjesto [9] maksimalno

312
00:19:13,960 --> 00:19:16,660
ili [0] ili nešto između.

313
00:19:16,660 --> 00:19:19,690
S Valgrind, ostvariti bilo koje vrijeme sada pišete program

314
00:19:19,690 --> 00:19:24,190
koji koristi pokazivače i koristi memoriju, i malloc točnije,

315
00:19:24,190 --> 00:19:27,080
definitivno ući u naviku trčanje ovako dugo

316
00:19:27,080 --> 00:19:30,890
ali vrlo jednostavno kopirati i zalijepiti naredbu Valgrind

317
00:19:30,890 --> 00:19:32,650
vidjeti ako ima neke pogreške u tamo.

318
00:19:32,650 --> 00:19:34,820
I to će biti neodoljiv svaki put kad vidim izlaz,

319
00:19:34,820 --> 00:19:39,430
ali samo analizirati kroz vizualno sve snage i vidjeti ako vidite spominje pogrešaka

320
00:19:39,430 --> 00:19:43,190
ili upozorenja ili nevažeći ili izgubljeni.

321
00:19:43,190 --> 00:19:46,200
Bilo riječi koje zvuče kao tobom pijan negdje.

322
00:19:46,200 --> 00:19:48,580
Dakle, shvatite da je novi alat u kompletu.

323
00:19:48,580 --> 00:19:51,270
>> Sada je u ponedjeljak, imali smo hrpu ljudi dolaze ovamo

324
00:19:51,270 --> 00:19:53,150
i predstavljaju pojam povezane liste.

325
00:19:53,150 --> 00:20:00,970
A uveli smo povezani popis kao rješenje ono problem?

326
00:20:00,970 --> 00:20:04,590
Da? [Studentski odgovor, nerazumljivo] Dobro.

327
00:20:04,590 --> 00:20:06,530
Polja ne može imati memorije dodan na njih.

328
00:20:06,530 --> 00:20:09,440
Ako izdvojiti niz veličine 10, to je sve što ste dobili.

329
00:20:09,440 --> 00:20:13,690
Možete nazvati funkciju kao realloc ako u početku zove malloc,

330
00:20:13,690 --> 00:20:17,580
i da mogu pokušati rasti niz ako postoji prostor prema kraju njega

331
00:20:17,580 --> 00:20:21,610
da nitko drugi ne koristi, a ako ne postoji, to je samo naći će vam veći komad negdje drugdje.

332
00:20:21,610 --> 00:20:25,040
Ali onda će kopirati sve one bajtova u novom polju.

333
00:20:25,040 --> 00:20:28,310
To zvuči kao vrlo ispravnom rješenju.

334
00:20:28,310 --> 00:20:34,790
Zašto je to neprivlačan?

335
00:20:34,790 --> 00:20:36,940
Mislim da radi, ljudi su taj problem riješili.

336
00:20:36,940 --> 00:20:40,710
Zašto moramo ga riješiti u ponedjeljak s povezanim listama? Da?

337
00:20:40,710 --> 00:20:44,060
[Odgovor Student, nerazumljivo] To bi moglo potrajati dugo vremena.

338
00:20:44,060 --> 00:20:49,260
U stvari, svaki put kada zovete malloc ili realloc ili calloc, što je još jedan,

339
00:20:49,260 --> 00:20:52,470
bilo koje vrijeme, program se govori u operacijskom sustavu,

340
00:20:52,470 --> 00:20:54,310
imaju tendenciju da se usporiti program prema dolje.

341
00:20:54,310 --> 00:20:57,470
A ako radite ovakve stvari u petlji, ste stvarno usporava stvari dolje.

342
00:20:57,470 --> 00:21:00,740
Nećeš primjetiti ovo najjednostavniji "Hello World" tipa programa,

343
00:21:00,740 --> 00:21:04,300
ali u puno većim programima, tražeći operativni sustav i opet za pamćenje

344
00:21:04,300 --> 00:21:07,520
ili ga vraćam i opet teži ne biti dobra stvar.

345
00:21:07,520 --> 00:21:11,210
Plus, to je samo vrsta intelektualno - to je potpuni gubitak vremena.

346
00:21:11,210 --> 00:21:16,490
Zašto izdvajati više i više memorije, rizik kopiranje sve u novom ruhu

347
00:21:16,490 --> 00:21:21,980
ako imate alternativu koja vam omogućuje da dodijeliti samo koliko memorije kao što je zapravo potrebno?

348
00:21:21,980 --> 00:21:24,130
Dakle, tu je pluses i minusa u ovdje.

349
00:21:24,130 --> 00:21:26,730
Jedan od pluses sada je da imamo dinamizam.

350
00:21:26,730 --> 00:21:29,100
Nije bitno gdje su komadi memorije su da su slobodni,

351
00:21:29,100 --> 00:21:32,070
Ja samo mogu sortirati u stvaranje tih mrvice kruha preko pokazivače

352
00:21:32,070 --> 00:21:34,470
string cijeli moj povezanog popisa zajedno.

353
00:21:34,470 --> 00:21:36,470
Ali ja platiti barem jednu cijenu.

354
00:21:36,470 --> 00:21:40,060
>> Što moram odreći dobivanjem vezane liste?

355
00:21:40,060 --> 00:21:42,470
Da? [Studentski odgovor, nerazumljivo] Dobro.

356
00:21:42,470 --> 00:21:45,650
Trebate više memorije. Sada trebam prostor za ove naputke,

357
00:21:45,650 --> 00:21:47,900
te u slučaju ovog super jednostavnog povezanoj popisu

358
00:21:47,900 --> 00:21:51,410
da samo pokušava pohraniti prirodna broja, koji su četiri bajta, držimo rekavši

359
00:21:51,410 --> 00:21:54,240
dobro, pokazivač je 4 bajta, tako da sada Doslovce sam udvostručila

360
00:21:54,240 --> 00:21:57,290
količina memorije trebam samo za pohranu ovaj popis.

361
00:21:57,290 --> 00:21:59,680
Ali opet, to je konstanta tradeoff u informatici

362
00:21:59,680 --> 00:22:03,440
između vremena i prostora i razvoja, truda i drugih resursa.

363
00:22:03,440 --> 00:22:06,630
Što je još jedan downside korištenja povezan popis? Da?

364
00:22:06,630 --> 00:22:10,150
[Studentski odgovor, nerazumljivo]

365
00:22:10,150 --> 00:22:12,600
Dobro. Nije tako lako pristupiti. Mi više ne mogu utjecati

366
00:22:12,600 --> 00:22:15,530
tjedan 0 načela poput podijeli pa vladaj.

367
00:22:15,530 --> 00:22:18,220
I točnije, binarno pretraživanje. Jer iako mi ljudi

368
00:22:18,220 --> 00:22:20,400
možete vidjeti gdje otprilike sredinom ovog popisa je,

369
00:22:20,400 --> 00:22:25,840
računalo samo zna da je to povezano popis počinje na adresi zove prvi.

370
00:22:25,840 --> 00:22:28,250
I to je 0x123 ili nešto slično.

371
00:22:28,250 --> 00:22:30,990
A jedini način program može pronaći srednji elementa

372
00:22:30,990 --> 00:22:33,350
je zapravo traži cijeli popis.

373
00:22:33,350 --> 00:22:35,500
A čak i tada, to je doslovno za pretraživanje cijeli popis, jer

374
00:22:35,500 --> 00:22:38,950
čak i nakon što dođete na srednju elementa slijedeći naputke,

375
00:22:38,950 --> 00:22:42,380
ti, program, nemam pojma koliko dugo ovaj popis je, potencijalno,

376
00:22:42,380 --> 00:22:45,250
dok ne pogoditi kraj njega, a kako znate programski

377
00:22:45,250 --> 00:22:48,600
da si na kraju povezane popisu?

378
00:22:48,600 --> 00:22:51,120
Tu je posebna NULL pokazivač, pa opet, konvencija.

379
00:22:51,120 --> 00:22:53,870
Umjesto da koristite ovaj pokazivač, definitivno ne želim da to bude neko smeće vrijednost

380
00:22:53,870 --> 00:22:57,750
pokazujući s pozornice negdje, želimo da se ruka dolje, NULL,

381
00:22:57,750 --> 00:23:01,530
tako da imamo ovu terminalla u ovom strukture podataka, tako da znamo gdje to završava.

382
00:23:01,530 --> 00:23:03,410
>> Što ako želimo manipulirati to?

383
00:23:03,410 --> 00:23:05,980
Napravili smo većinu ovom vizualno, i sa ljudima,

384
00:23:05,980 --> 00:23:07,630
ali što ako želimo napraviti umetanje?

385
00:23:07,630 --> 00:23:12,360
Dakle, izvorni popis bio 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Što ako smo tada htjeli malloc prostora za broj 55, čvor za njega,

387
00:23:16,730 --> 00:23:20,730
i onda želimo umetnuti 55 u popisu kao što smo učinili u ponedjeljak?

388
00:23:20,730 --> 00:23:23,690
Kako ćemo to učiniti? Pa, Anita je došao i ona je u suštini hodao popis.

389
00:23:23,690 --> 00:23:27,500
Počela je na prvi element, onda je sljedeći, sljedeći, sljedeći, sljedeći, sljedeći.

390
00:23:27,500 --> 00:23:29,500
Konačno pogodio lijevi skroz

391
00:23:29,500 --> 00:23:34,480
i shvatio oh, ovo je NULL. Dakle, ono što pokazivač manipulacije potrebni da se radi?

392
00:23:34,480 --> 00:23:37,980
Osoba koja je na kraju, broj 34, potrebna mu je lijeva ruka podignuta

393
00:23:37,980 --> 00:23:46,220
ukazati na 55, 55 potrebno svoju lijevu ruku prema dolje da bude novi NULL Terminator. Gotovo.

394
00:23:46,220 --> 00:23:49,540
Prilično lako umetanje 55 u sortirani popis.

395
00:23:49,540 --> 00:23:51,800
I kako bi to moglo izgledati?

396
00:23:51,800 --> 00:23:55,690
>> Pusti me naprijed i otvoriti neke koda primjer ovdje.

397
00:23:55,690 --> 00:23:58,120
Ja ću otvoriti gedit, i neka mi otvoriti dvije datoteke prvi.

398
00:23:58,120 --> 00:24:02,050
Jedan je list1.h, i neka mi samo podsjetiti da je to komad koda

399
00:24:02,050 --> 00:24:04,920
da smo se predstavljaju čvor.

400
00:24:04,920 --> 00:24:13,040
Čvor ima i int n zove i upustvo zove sljedeći koji samo ukazuje na sljedeću stvar na popisu.

401
00:24:13,040 --> 00:24:15,450
To je sada u. H datoteci. Zašto?

402
00:24:15,450 --> 00:24:19,090
Tu je ta konvencija, a nismo iskoristili ovo ogroman sami,

403
00:24:19,090 --> 00:24:22,220
ali osoba koja je napisao printf i druge funkcije

404
00:24:22,220 --> 00:24:27,150
dao kao dar na svijetu svih tih funkcija pišući datoteku pod nazivom stdio.h.

405
00:24:27,150 --> 00:24:30,950
A onda je tu string.h, a zatim tu je map.h, a tu je sve ove h slika

406
00:24:30,950 --> 00:24:34,410
koje ste možda vidjeli ili koristili tijekom trajanja pisanog od strane drugih ljudi.

407
00:24:34,410 --> 00:24:38,470
Obično u tim. H datoteke su samo stvari poput typedefs

408
00:24:38,470 --> 00:24:42,310
ili deklaracije prilagođene vrste ili prijavljivanjem konstanti.

409
00:24:42,310 --> 00:24:47,890
Vi ne stavi funkcije 'implementacije u zaglavlju datoteke.

410
00:24:47,890 --> 00:24:50,570
Možete staviti, umjesto toga, samo svoje prototipove.

411
00:24:50,570 --> 00:24:53,050
Možete staviti stvari koje želite podijeliti sa svijetom ono što im je potrebno

412
00:24:53,050 --> 00:24:55,640
kako bi se sastaviti svoj kod. Dakle, samo da se u ovu naviku,

413
00:24:55,640 --> 00:24:59,110
odlučili smo napraviti istu stvar. Ne postoji puno u list1.h,

414
00:24:59,110 --> 00:25:02,070
ali mi smo stavili nešto što bi moglo biti od interesa za ljude u svijetu

415
00:25:02,070 --> 00:25:05,030
koji žele koristiti naše povezanu popis provedbu.

416
00:25:05,030 --> 00:25:08,040
Sada, u list1.c, neću ići kroz ovaj cijelu stvar

417
00:25:08,040 --> 00:25:11,390
jer to je malo dugo, ovaj program, ali ajmo pokrenuti to pravi brzo na provjeru.

418
00:25:11,390 --> 00:25:15,720
Dopustite mi sastaviti List1, neka mi onda pokrenuti List1, a ono što ćete vidjeti je

419
00:25:15,720 --> 00:25:18,070
mi smo simulirani jednostavan mali program ovdje

420
00:25:18,070 --> 00:25:20,990
da će mi dopustiti da dodavanje i uklanjanje brojeva na popisu.

421
00:25:20,990 --> 00:25:24,310
Pa neka mi ići naprijed i upišite 3 za tri izbornika opcija.

422
00:25:24,310 --> 00:25:27,880
Želim umetnuti broj - ajmo napraviti prvi broj, koji je bio 9,

423
00:25:27,880 --> 00:25:30,550
i sada sam rekla popis je sada devet.

424
00:25:30,550 --> 00:25:33,760
Dopustite mi ići naprijed i učiniti još jedan umetanje, pa sam udario izbornika tri.

425
00:25:33,760 --> 00:25:36,760
Koji broj želim umetnuti? 17.

426
00:25:36,760 --> 00:25:39,220
Upišite. I ja ću to učiniti samo još jedan.

427
00:25:39,220 --> 00:25:41,720
Dopustite mi da stavite broj 22.

428
00:25:41,720 --> 00:25:45,850
Dakle, imamo početke povezanog popisa koji smo imali u slide obliku trenutak prije.

429
00:25:45,850 --> 00:25:48,740
Kako je to umetanje zapravo događa?

430
00:25:48,740 --> 00:25:52,000
Doista, 22 je sada na kraju popisa.

431
00:25:52,000 --> 00:25:55,050
Dakle, priča mi je rekao na pozornici u ponedjeljak i recapped upravo sada

432
00:25:55,050 --> 00:25:57,460
mora biti zapravo događa u kodu.

433
00:25:57,460 --> 00:25:59,700
Idemo pogledati. Dopustite mi da se pomaknite prema dolje u ovoj datoteci.

434
00:25:59,700 --> 00:26:01,720
Mi ćemo prijeći preko neke od funkcija,

435
00:26:01,720 --> 00:26:05,630
ali ćemo ići prema dolje, recimo, funkcija umetak.

436
00:26:05,630 --> 00:26:11,720
>> Idemo vidjeti kako ćemo ići o umetanja novog čvora u ovom povezane liste.

437
00:26:11,720 --> 00:26:14,550
Gdje je popis proglašen? Pa, neka je pomicanje skroz gore na vrhu,

438
00:26:14,550 --> 00:26:19,970
i primijetiti da moj povezani popis bitno je proglašen kao jedan pokazivač koji je u početku NULL.

439
00:26:19,970 --> 00:26:23,180
Dakle, ja sam koristeći globalnu varijablu ovdje, što općenito smo propovijedali protiv

440
00:26:23,180 --> 00:26:25,280
jer se čini koda malo neuredan za održavanje,

441
00:26:25,280 --> 00:26:29,080
to je vrsta lijen, obično, ali to nije lijen i to nije u redu i to nije loše

442
00:26:29,080 --> 00:26:33,660
Ako je vaš program je jedina svrha u životu je da simulira jedan povezanu listu.

443
00:26:33,660 --> 00:26:35,460
Koji je točno ono što mi radimo.

444
00:26:35,460 --> 00:26:39,100
Dakle, umjesto da proglasi to glavna, a zatim su ga prođe na svakom funkciji

445
00:26:39,100 --> 00:26:42,640
smo zapisano u ovom programu, umjesto toga shvatiti, oh, neka je samo da je to globalna

446
00:26:42,640 --> 00:26:47,060
jer cijela svrha ovog programa je pokazati jedan i samo jedan vezan popis.

447
00:26:47,060 --> 00:26:50,700
Dakle, da se osjeća dobro. Ovdje su moji prototipovi, a mi nećemo proći kroz sve to,

448
00:26:50,700 --> 00:26:55,800
ali sam napisao brisanje funkciju, a pronaći funkciju, umetnuti funkciju, i poprijeko funkciju.

449
00:26:55,800 --> 00:26:59,080
Ali ajmo sad vratiti dolje priložene funkciji

450
00:26:59,080 --> 00:27:01,490
i vidjeti kako je to netko radi ovdje.

451
00:27:01,490 --> 00:27:09,940
Insert je na liniji - ovdje mi ići.

452
00:27:09,940 --> 00:27:12,850
Umetnite. Dakle, to ne poduzimati nikakve argumente, jer ćemo pitati

453
00:27:12,850 --> 00:27:15,930
korisnik unutar ove funkcije za broj ih želite umetnuti.

454
00:27:15,930 --> 00:27:19,410
Ali prvo, mi pripremamo da im daju neki prostor.

455
00:27:19,410 --> 00:27:22,050
To je vrsta kopirati i zalijepiti iz druge primjer.

456
00:27:22,050 --> 00:27:25,110
U tom slučaju, mi smo bili dodjele int; ovaj put smo dodjele čvor.

457
00:27:25,110 --> 00:27:27,910
Ja stvarno ne sjećam koliko bajtova čvor je, ali to je u redu.

458
00:27:27,910 --> 00:27:30,460
Sizeof mogu shvatiti da se za mene.

459
00:27:30,460 --> 00:27:33,340
A zašto sam ja provjere NULL u skladu 120?

460
00:27:33,340 --> 00:27:37,530
Što bi moglo poći po zlu u skladu 119? Da?

461
00:27:37,530 --> 00:27:40,530
[Studentski odgovor, nerazumljivo]

462
00:27:40,530 --> 00:27:43,440
Dobro. Samo bi mogao biti slučaj da sam pitao za previše memorije

463
00:27:43,440 --> 00:27:47,020
ili nešto nije u redu, a operativni sustav nema dovoljno bajtova da me daju,

464
00:27:47,020 --> 00:27:50,640
tako da signalizira koliko po povratku NULL, a ako ja ne provjerite da

465
00:27:50,640 --> 00:27:54,710
a ja samo slijepo nastaviti koristiti adresa se vratio, to bi mogao biti NULL.

466
00:27:54,710 --> 00:27:58,400
To bi mogao biti neki nepoznati vrijednost; nije dobra stvar ako ja -

467
00:27:58,400 --> 00:28:00,590
zapravo neće biti nepoznata vrijednost. To bi mogla biti NULL, tako da ja ne želim

468
00:28:00,590 --> 00:28:02,550
da ga zlostavljati i riskirati ga dereferencing.

469
00:28:02,550 --> 00:28:07,410
Ako se to dogodi, samo sam se vratiti, a mi ćemo se pretvarati kao da nisam dobila natrag bilo sjećanje na sve.

470
00:28:07,410 --> 00:28:12,270
>> Inače, kažem korisnik će mi dati broj za umetanje, pozivam naše stare prijatelju GetInt,

471
00:28:12,270 --> 00:28:15,530
i onda je to nova sintaksa uveli smo u ponedjeljak.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n' znači uzeti adresu koju je dao malloc

473
00:28:20,320 --> 00:28:23,490
što predstavlja prvi byte novog čvora objekta,

474
00:28:23,490 --> 00:28:26,860
, a zatim otići na području zvanom n.

475
00:28:26,860 --> 00:28:35,270
Malo trivijalnost pitanje: To je ekvivalent za ono što više grobni liniju koda?

476
00:28:35,270 --> 00:28:38,110
Kako bi inače ja sam napisao ovo? Želite li se ubosti?

477
00:28:38,110 --> 00:28:41,480
[Studentski odgovor, nerazumljivo]

478
00:28:41,480 --> 00:28:44,870
Dobro. Koristeći. N, ali to nije sasvim jednostavno kao ovo.

479
00:28:44,870 --> 00:28:47,090
Što mi je prvo trebate učiniti? [Studentski odgovor, nerazumljivo]

480
00:28:47,090 --> 00:28:52,730
Dobro. Trebam napraviti * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Dakle, ovo je rekao novi pokazivač je očito adresa. Zašto?

482
00:28:55,610 --> 00:28:59,520
Budući da je vraćen od strane malloc. * Newptr rekavši "tamo"

483
00:28:59,520 --> 00:29:02,970
i onda kad ste tamo, onda možete koristiti više poznato. N,

484
00:29:02,970 --> 00:29:05,730
ali to samo izgleda malo ružno, pogotovo ako mi ljudi idu na

485
00:29:05,730 --> 00:29:10,360
privući pokazivače sa strelicama svih vremena, svijet ima standardizirani na ovom strelice zapis,

486
00:29:10,360 --> 00:29:12,320
koji ne točno istu stvar.

487
00:29:12,320 --> 00:29:16,070
Dakle, samo koristiti -> notaciju kada je stvar na lijevoj strani je pokazivač.

488
00:29:16,070 --> 00:29:18,790
Inače, ako je to stvarna struct, koristiti. N.

489
00:29:18,790 --> 00:29:25,800
I onda ovo: Zašto sam inicijalizirati newptr-> uz NULL?

490
00:29:25,800 --> 00:29:28,610
Mi ne želimo visećim lijevu ruku off kraja pozornice.

491
00:29:28,610 --> 00:29:31,630
Želimo to pokazuje ravno dolje, što znači kraj ovom popisu

492
00:29:31,630 --> 00:29:34,980
mogao potencijalno biti na tom čvoru, pa smo bolje bi bili sigurni da je NULL.

493
00:29:34,980 --> 00:29:38,460
I, općenito, inicijalizacije svoje varijable ili podatkovne članove i tvorevina

494
00:29:38,460 --> 00:29:40,470
nešto je samo dobra praksa.

495
00:29:40,470 --> 00:29:45,170
Samo ostavljajući smeće postoje i dalje postojati općenito dobiva u nevolji

496
00:29:45,170 --> 00:29:48,650
ako ste zaboravili učiniti nešto kasnije.

497
00:29:48,650 --> 00:29:51,590
>> Evo nekoliko slučajeva. To je, opet, je umetak funkcija,

498
00:29:51,590 --> 00:29:54,930
i prva stvar koju sam provjeriti je li varijabla zove prvi,

499
00:29:54,930 --> 00:29:58,240
da je globalna varijabla je NULL, to znači da ne postoji povezani popis.

500
00:29:58,240 --> 00:30:02,460
Nismo umetnuta nikakve brojeve, tako da je trivijalno umetnuti ovaj trenutni broj

501
00:30:02,460 --> 00:30:05,240
u popis, jer to jednostavno spada na početku popisa.

502
00:30:05,240 --> 00:30:08,100
Dakle, ovo je bio kad Anita samo stajao ovdje sam, praveći

503
00:30:08,100 --> 00:30:11,390
nitko drugi nije bio ovdje na bini dok smo dodijeljen čvor,

504
00:30:11,390 --> 00:30:13,940
onda je ona mogla podići ruku po prvi put,

505
00:30:13,940 --> 00:30:17,420
ako su svi ostali došli na pozornicu nakon nje u ponedjeljak.

506
00:30:17,420 --> 00:30:22,900
Sada ovdje, ovo je malo provjeriti gdje moram reći da ako je nova čvora vrijednost n

507
00:30:22,900 --> 00:30:27,370
je <vrijednost n u trenutnoj prvi čvor,

508
00:30:27,370 --> 00:30:29,930
to znači da postoji linked popis koji je počeo.

509
00:30:29,930 --> 00:30:32,330
Tu je barem jedan čvor na popisu, ali ovaj novi dečko

510
00:30:32,330 --> 00:30:37,230
pripada prije, tako da ćemo morati premjestiti stvari oko.

511
00:30:37,230 --> 00:30:43,450
Drugim riječima, ako je popis započeo sa samo, recimo,

512
00:30:43,450 --> 00:30:48,100
samo broj 17, koji je - zapravo, možemo to učiniti jasnije.

513
00:30:48,100 --> 00:30:56,010
Ako počnemo našu priču s pokazivačem ovdje zove prvi,

514
00:30:56,010 --> 00:30:59,870
iu početku je NULL, a mi umetnuti broj 9,

515
00:30:59,870 --> 00:31:02,510
broj 9 je jasno pripada na početku popisa.

516
00:31:02,510 --> 00:31:07,400
Dakle, ajmo se pretvarati samo mi malloced adresu ili broj 9 i staviti ga ovdje.

517
00:31:07,400 --> 00:31:13,170
Ako prvi je 9 po defaultu, prvi scenarij smo razgovarali samo znači ajmo točku Ovaj momak ovdje,

518
00:31:13,170 --> 00:31:15,790
ovo ostaviti kao NULL, sada imamo broj 9.

519
00:31:15,790 --> 00:31:18,280
Sljedeći broj želimo umetnuti je 17.

520
00:31:18,280 --> 00:31:22,420
17 pripada ovdje, tako da ćemo morati napraviti neke logičke koračanju kroz to.

521
00:31:22,420 --> 00:31:26,060
Tako ćemo umjesto toga, prije nego što smo to učinili, ajmo se pretvarati da smo htjeli umetnuti broj 8.

522
00:31:26,060 --> 00:31:28,650
>> Dakle, samo za praktičnost miloga, ja ću se izvući ovdje.

523
00:31:28,650 --> 00:31:30,760
Ali zapamtite, malloc može staviti najviše bilo gdje.

524
00:31:30,760 --> 00:31:33,460
No, za crtanje miloga, ja ću ga staviti ovdje.

525
00:31:33,460 --> 00:31:38,440
Dakle pretvarati Upravo sam izdvojila čvor za broj 8, a to je NULL po defaultu.

526
00:31:38,440 --> 00:31:42,800
Što sada ima dogoditi? Par stvari.

527
00:31:42,800 --> 00:31:47,090
Mi smo napravili ovu grešku na pozornici u ponedjeljak gdje smo ažurirani pokazivač ovako,

528
00:31:47,090 --> 00:31:51,890
onda je to učinio, a onda smo tvrdili - mi siročad svi ostali na pozornici.

529
00:31:51,890 --> 00:31:54,350
Budući da can't - kako operacija ovdje je važno,

530
00:31:54,350 --> 00:31:58,760
jer sada smo izgubili ovu čvor 9 koji je samo vrsta lebdi u prostoru.

531
00:31:58,760 --> 00:32:01,150
Dakle, to nije pravi pristup u ponedjeljak.

532
00:32:01,150 --> 00:32:03,330
Mi prvo moramo učiniti nešto drugo.

533
00:32:03,330 --> 00:32:06,280
Država svijeta izgleda ovako. U početku, 8 je dodijeljeno.

534
00:32:06,280 --> 00:32:10,550
Što će biti bolji način umetanja 8?

535
00:32:10,550 --> 00:32:14,720
Umjesto ažuriranja ovaj pokazivač prvi, samo ažurirati ovaj jedan ovdje umjesto.

536
00:32:14,720 --> 00:32:17,720
Dakle, trebamo liniju koda koji će pretvoriti ovu NULL karakter

537
00:32:17,720 --> 00:32:22,020
u stvarni pokazivač koji je upućuju na čvoru 9,

538
00:32:22,020 --> 00:32:27,970
i onda smo sigurno možete promijeniti prvi ukazati na ovog momka ovdje.

539
00:32:27,970 --> 00:32:31,330
Sada imamo popis, povezana lista, od dva elementa.

540
00:32:31,330 --> 00:32:33,580
A što to zapravo izgledaju ovdje?

541
00:32:33,580 --> 00:32:36,900
Ako gledamo koda, primijetiti da sam učinio upravo to.

542
00:32:36,900 --> 00:32:41,970
Ja sam rekao newptr, iu ovoj priči, newptr je pokazujući na ovim tipom.

543
00:32:41,970 --> 00:32:45,520
>> Pa neka mi izvući još jednu stvar, a ja sam trebao napustiti malo više prostora za to.

544
00:32:45,520 --> 00:32:48,540
Dakle, oprosti maleni malo crtež.

545
00:32:48,540 --> 00:32:52,140
Ovaj momak se zove newptr.

546
00:32:52,140 --> 00:32:57,940
To je varijabla smo proglasili nekoliko redaka ranije, u skladu - samo iznad 25 godina.

547
00:32:57,940 --> 00:33:03,430
I to pokazuje da osam. Dakle, kada kažem newptr-> next, to znači ići na struct

548
00:33:03,430 --> 00:33:07,910
koja se ukazao na po newptr, pa ovdje smo, otići tamo.

549
00:33:07,910 --> 00:33:13,990
Tada se strelica rekavši dobiti sljedeći polje, a zatim = govori staviti ono vrijednost tamo?

550
00:33:13,990 --> 00:33:17,280
Vrijednost koja je u prvi, što je vrijednost bila u prvom?

551
00:33:17,280 --> 00:33:21,930
Prvo je pokazujući na ovom čvoru, pa to znači da je sada treba ukazati na ovom čvoru.

552
00:33:21,930 --> 00:33:25,660
Drugim riječima, ono što izgleda iako smiješnom zabrljati sa mojim rukopisom,

553
00:33:25,660 --> 00:33:28,620
što je jednostavna ideja samo pomicanjem ove strelice oko

554
00:33:28,620 --> 00:33:31,560
prevodi na kodu samo s tom jednom brod.

555
00:33:31,560 --> 00:33:38,110
Čuvajte ono što je u prvi u sljedećem polju, a zatim ažurirati ono prvi zapravo jest.

556
00:33:38,110 --> 00:33:40,900
Idemo naprijed i brzo naprijed kroz neke od toga,

557
00:33:40,900 --> 00:33:44,220
i gledati samo na ovom repa za sada.

558
00:33:44,220 --> 00:33:51,210
Pretpostavimo da sam doći do točke gdje sam naći da je sljedeće polje nekog čvora je NULL.

559
00:33:51,210 --> 00:33:53,410
I u ovom trenutku u priči, detaljno da sam prešućuju

560
00:33:53,410 --> 00:33:58,170
je da sam upoznao još pokazivač ovdje u skladu 142, prethodnik ciljnikom.

561
00:33:58,170 --> 00:34:01,320
U suštini, u ovom trenutku u priči, jednom je popis gets dugo,

562
00:34:01,320 --> 00:34:04,800
Nekako mi je potrebno da ga hodati s dva prsta jer ako odem predaleko,

563
00:34:04,800 --> 00:34:08,219
sjećam u jednom duljine popisu, ne možete ići unatrag.

564
00:34:08,219 --> 00:34:13,659
Dakle, ova ideja predptr je moj lijevo prst, a newptr - ne newptr.

565
00:34:13,659 --> 00:34:17,199
Drugi pokazivač koji je ovdje je moj drugi prst, a ja sam samo vrsta hodanja popis.

566
00:34:17,199 --> 00:34:22,179
Zato što postoji. Ali ajmo uzeti u obzir samo jedan od jednostavnijih slučajeva ovdje.

567
00:34:22,179 --> 00:34:26,620
Ako te pokazivača sljedeće polje je NULL, što je logična implikacija?

568
00:34:26,620 --> 00:34:30,840
Ako ste prešli taj popis i pogodio NULL pokazivač?

569
00:34:30,840 --> 00:34:35,780
Vi ste na kraju popisa, i tako kod onda dodati ovaj jedan dodatni element

570
00:34:35,780 --> 00:34:41,230
je vrsta intuitivno će se taj čvor čija sljedeći pokazivač je NULL,

571
00:34:41,230 --> 00:34:46,120
tako da je ovo trenutno NULL, i to promijeniti, ipak, biti adresa novi čvor.

572
00:34:46,120 --> 00:34:52,260
Dakle, mi smo samo crtanje u kodu strelicu da mi je nacrtao na pozornici podizanje nečiju lijevu ruku.

573
00:34:52,260 --> 00:34:54,070
>> I slučaj da ću mahati moje ruke na za sada,

574
00:34:54,070 --> 00:34:58,020
Upravo zato mislim da je lako izgubiti kada ćemo to učiniti u ovom vrstom okoliš,

575
00:34:58,020 --> 00:35:00,600
je provjera za ubacivanje na popisu je sredini.

576
00:35:00,600 --> 00:35:03,220
No, samo intuitivno, ono što se treba dogoditi, ako želite shvatiti

577
00:35:03,220 --> 00:35:06,600
gdje neki broj pripada u sredini je što moram ga hodati

578
00:35:06,600 --> 00:35:09,510
s više od jednog prsta, više od jedne pokazivač,

579
00:35:09,510 --> 00:35:12,920
shvatiti gdje joj je i mjesto po provjeri je element <sadašnjeg,

580
00:35:12,920 --> 00:35:15,450
> Struja jednom, i jednom naći to mjesto,

581
00:35:15,450 --> 00:35:20,400
onda morate učiniti ovu vrstu ljuska igra u kojoj se krećete na naputke oko vrlo pažljivo.

582
00:35:20,400 --> 00:35:23,850
I da odgovor, ako želite razloga kroz to kod kuće na svoje,

583
00:35:23,850 --> 00:35:28,340
svodi samo na ove dvije linije koda, ali bi od tih linija je super važno.

584
00:35:28,340 --> 00:35:31,390
Jer ako ispadne nečiju ruku i podići netko drugi u pogrešnom redoslijedu,

585
00:35:31,390 --> 00:35:34,580
opet, mogli završiti orphaning popis.

586
00:35:34,580 --> 00:35:39,500
Da sumiramo više konceptualno, umetanja na začelju je relativno jednostavan.

587
00:35:39,500 --> 00:35:42,940
Umetanja na glavi je također relativno jednostavan,

588
00:35:42,940 --> 00:35:45,580
ali morate ažurirati Dodatne pokazivač ovaj put

589
00:35:45,580 --> 00:35:47,930
ugurati broj 5 u popis ovdje,

590
00:35:47,930 --> 00:35:51,560
a zatim umetanje u sredini uključuje još više truda,

591
00:35:51,560 --> 00:35:56,130
do vrlo pažljivo umetnite broj 20 u svom pravom mjestu,

592
00:35:56,130 --> 00:35:58,350
koja je između 17 i 22 godine.

593
00:35:58,350 --> 00:36:02,700
Dakle, što trebate učiniti nešto poput imaju novi čvor 20 točku 22,

594
00:36:02,700 --> 00:36:08,470
a zatim, koji čvora pokazivač treba biti obnovljeno zadnji?

595
00:36:08,470 --> 00:36:10,630
To je 17, zapravo ga umetnite.

596
00:36:10,630 --> 00:36:14,080
Pa opet, ja ću odgoditi stvarni kod za tu određenu primjenu.

597
00:36:14,080 --> 00:36:17,280
>> Na prvi pogled, to je malo neodoljiv, ali to je zapravo samo beskonačna petlja

598
00:36:17,280 --> 00:36:21,770
koji je petlje, petlje, petlje, petlje, i razbijanje čim pogodio NULL pokazivač,

599
00:36:21,770 --> 00:36:24,590
U tom trenutku možete učiniti potrebnu umetanje.

600
00:36:24,590 --> 00:36:30,960
To je, dakle, prikazuje povezani popis umetanje koda.

601
00:36:30,960 --> 00:36:34,590
To je vrsta puno, i da se osjeća kao da smo riješili jedan problem,

602
00:36:34,590 --> 00:36:36,940
ali uveli smo cijeli drugi. Iskreno, mi smo proveli cijelo ovo vrijeme

603
00:36:36,940 --> 00:36:40,540
na velikom O i Ω i trčanje vremena, pokušava riješiti probleme brže,

604
00:36:40,540 --> 00:36:43,270
i ovdje smo uzimanje veliki korak unatrag, to se osjeća.

605
00:36:43,270 --> 00:36:45,380
A opet, ako je cilj za pohranu podataka,

606
00:36:45,380 --> 00:36:48,010
ona se osjeća kao Svetim Gralom, kao što smo rekli u ponedjeljak, stvarno bi bilo

607
00:36:48,010 --> 00:36:50,470
za pohranu stvari odmah.

608
00:36:50,470 --> 00:36:53,930
>> U stvari, pretpostavljam da smo stavili na stranu povezan popis za trenutak

609
00:36:53,930 --> 00:36:56,000
a mi umjesto da uvodi pojam tablici.

610
00:36:56,000 --> 00:36:59,110
I neka je samo misliti na stolu za trenutak kao niz.

611
00:36:59,110 --> 00:37:03,790
Ovo polje i to ovdje slučaj ima neke elemente 26, 0 do 25,

612
00:37:03,790 --> 00:37:07,940
i pretpostavimo da vam je potreban neki komad za pohranu za imena:

613
00:37:07,940 --> 00:37:10,350
Alice i Bob i Charlie i slično.

614
00:37:10,350 --> 00:37:12,880
I vi trebate neke strukturu podataka za pohranu ta imena.

615
00:37:12,880 --> 00:37:15,000
Pa, što bi moglo koristiti nešto poput povezane liste

616
00:37:15,000 --> 00:37:20,260
i ti mogao hodati popis umetanjem Alisa prije Bobom i Charlie nakon Bob i tako dalje.

617
00:37:20,260 --> 00:37:23,850
A, u stvari, ako želite vidjeti kod kao što je to, kao na stranu,

618
00:37:23,850 --> 00:37:27,230
znam da je u list2.h, radimo upravo to.

619
00:37:27,230 --> 00:37:30,610
Nećemo ići preko ovog koda, ali to je varijanta prvom primjeru

620
00:37:30,610 --> 00:37:34,640
koji uvodi jedan drugi struct smo vidjeli prije tzv učenika,

621
00:37:34,640 --> 00:37:40,330
i onda što to zapravo sprema u povezanoj listi je pointer na studentskoj strukturi

622
00:37:40,330 --> 00:37:44,520
nego jednostavno malo broj, n.

623
00:37:44,520 --> 00:37:46,900
Dakle, shvaćam da je kod tu koja uključuje stvarne konce,

624
00:37:46,900 --> 00:37:49,940
ali ako je cilj na dohvat ruke stvarno sada je za rješavanje problema učinkovitost,

625
00:37:49,940 --> 00:37:53,380
Ne bi li bilo lijepo da smo s obzirom na objekt zove Alice,

626
00:37:53,380 --> 00:37:56,020
želimo joj staviti u pravo mjesto u bogatu strukturu,

627
00:37:56,020 --> 00:37:58,860
ona se osjeća kao da bi bilo jako lijepo da samo stavite Alisa,

628
00:37:58,860 --> 00:38:01,180
čije ime počinje s, u prvom položaju.

629
00:38:01,180 --> 00:38:05,270
I Bob, čije ime počinje sa B, u drugom mjestu.

630
00:38:05,270 --> 00:38:09,580
Uz niz, ili počnimo nazivajući ga stol, hash tablice u to,

631
00:38:09,580 --> 00:38:13,650
možemo učiniti upravo to. Ako smo dati ime poput Alice,

632
00:38:13,650 --> 00:38:16,700
Niz poput Alice, gdje ste stavili A-L-I-c-e?

633
00:38:16,700 --> 00:38:20,540
Trebamo hueristic. Trebamo funkciju uzeti neki ulaz poput Alice

634
00:38:20,540 --> 00:38:24,610
i vratiti odgovor, "Put Alisa u ovom mjestu."

635
00:38:24,610 --> 00:38:28,720
I ova funkcija, ova crna kutija, koja će se zvati hash funkcija.

636
00:38:28,720 --> 00:38:32,330
>> Hash funkcija je nešto što traje ulaz, kao što je "Alice",

637
00:38:32,330 --> 00:38:38,080
i vraća se u vama, obično, numerička mjesto u nekom strukture podataka gdje je Alice pripada.

638
00:38:38,080 --> 00:38:40,830
U ovom slučaju, naša hash funkcija trebala biti relativno jednostavan.

639
00:38:40,830 --> 00:38:47,510
Naš hash funkcija treba reći, ako ste dati "Alice", koji lik trebam stalo?

640
00:38:47,510 --> 00:38:55,660
Prvi. Dakle, gledam [0], a onda sam rekao, ako [0] Lik je, vratiti broj 0.

641
00:38:55,660 --> 00:39:01,130
Ako je B, vratiti jedan. Ako je to C, vratiti dva, i tako dalje.

642
00:39:01,130 --> 00:39:05,940
Sve 0 indeks, te da će dopustiti mene za umetanje Alice, a zatim Bob i onda Charlie i tako dalje

643
00:39:05,940 --> 00:39:10,960
u ovom strukturom podataka. No, tu je problem.

644
00:39:10,960 --> 00:39:13,060
Što ako Anita dolazi zajedno opet?

645
00:39:13,060 --> 00:39:17,510
Kamo ćemo staviti Anita? Njezino ime je, također, počinje slovom A,

646
00:39:17,510 --> 00:39:20,330
i da se osjeća kao da smo napravili još veći nered ovom problemu.

647
00:39:20,330 --> 00:39:24,380
Mi sada imamo izravan umetanje, konstantna vrijeme unosa, u strukture podataka

648
00:39:24,380 --> 00:39:27,100
nego gore-slučaju linearno,

649
00:39:27,100 --> 00:39:29,510
ali ono što možemo učiniti s Anita u ovom slučaju?

650
00:39:29,510 --> 00:39:34,110
Koje su dvije opcije, stvarno? Da?

651
00:39:34,110 --> 00:39:37,410
[Studentski odgovor, nerazumljivo] Ok, tako da smo mogli imati još jednu dimenziju.

652
00:39:37,410 --> 00:39:42,320
To je dobro. Dakle, možemo izgraditi stvari u 3D kao što smo razgovarali o verbalno ponedjeljak.

653
00:39:42,320 --> 00:39:46,700
Mogli bismo dodati još jedan pristup ovdje, ali pretpostavljam da ne, ja pokušavam zadržati ovaj jednostavan.

654
00:39:46,700 --> 00:39:50,160
Cijeli cilj je da se ovdje imaju neposredne konstanta-time pristup,

655
00:39:50,160 --> 00:39:52,170
tako da se dodavanjem previše složenosti.

656
00:39:52,170 --> 00:39:55,970
Koje su druge mogućnosti kada pokušava ubaciti Anita u ovom strukture podataka? Da?

657
00:39:55,970 --> 00:39:58,610
[Studentski odgovor, nerazumljivo] Dobro. Tako smo mogli kretati svi drugi dolje,

658
00:39:58,610 --> 00:40:03,040
kao Charlie nudges dolje Bob i Alice, a onda smo stavili Anita gdje ona stvarno želi biti.

659
00:40:03,040 --> 00:40:05,660
>> Naravno, sada, tu je nuspojava toga.

660
00:40:05,660 --> 00:40:09,000
Ova struktura podataka je vjerojatno korisno ne zato što želimo umetnuti ljudi odjednom

661
00:40:09,000 --> 00:40:11,250
ali zato želimo provjeriti da li su oni tamo kasnije

662
00:40:11,250 --> 00:40:13,600
ako želimo ispisati sva imena u strukture podataka.

663
00:40:13,600 --> 00:40:15,850
Mi ćemo učiniti nešto s tim podacima na kraju.

664
00:40:15,850 --> 00:40:20,810
Tako sada imamo takav pijan nad Alice, koji više nije gdje je ona trebala biti.

665
00:40:20,810 --> 00:40:23,880
Niti je Bob, niti je Charlie.

666
00:40:23,880 --> 00:40:26,060
Dakle, možda to i nije tako dobra ideja.

667
00:40:26,060 --> 00:40:28,830
Ali doista, to je jedna od opcija. Mi smo mogli prebaciti sve dolje,

668
00:40:28,830 --> 00:40:32,240
ili pakao, Anita je došao kasno u igri, zašto ne bismo stavili Anita

669
00:40:32,240 --> 00:40:35,870
Ne ovdje, ne ovdje, ne ovdje, neka je samo stavi malo niže na popisu.

670
00:40:35,870 --> 00:40:38,680
No, tada taj problem počne dopasti opet.

671
00:40:38,680 --> 00:40:41,630
Možda ćete biti u mogućnosti pronaći Alice odmah, na temelju njezina imena.

672
00:40:41,630 --> 00:40:44,320
I Bob odmah, a Charlie. Ali onda tražiti Anita,

673
00:40:44,320 --> 00:40:46,360
i vidjet ćete, hm, Alice je na putu.

674
00:40:46,360 --> 00:40:48,770
Pa, dopustite mi da provjerite u nastavku Alice. Bob je nije Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie nije Anita. Oh, tamo je Anita.

676
00:40:51,850 --> 00:40:54,720
A ako ste i dalje taj vlak logike skroz,

677
00:40:54,720 --> 00:41:00,690
što je najgore slučaj trčanje vrijeme pronalaženje ili umetanjem Anita u ovom novom strukturom podataka?

678
00:41:00,690 --> 00:41:03,280
To je O (n), zar ne?

679
00:41:03,280 --> 00:41:06,280
Budući da je u najgorem slučaju, tu je Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
skroz nekome pod nazivom "Y", tako da je samo jedno mjesto ulijevo.

681
00:41:10,150 --> 00:41:13,950
Srećom, mi nemamo jedan pod nazivom "Z", pa smo stavili Anita na samom dnu.

682
00:41:13,950 --> 00:41:16,040
>> Nismo stvarno riješiti taj problem.

683
00:41:16,040 --> 00:41:19,890
Dakle, možda trebamo uvesti ovu treću dimenziju.

684
00:41:19,890 --> 00:41:22,230
I to ispada, ako ne možemo predstaviti ovu treću dimenziju,

685
00:41:22,230 --> 00:41:25,240
ne možemo to učiniti savršeno, ali Sveti Gral će biti uzimajući

686
00:41:25,240 --> 00:41:28,370
konstantnog vrijeme umetanja i dinamičke ubacivanja, tako da

687
00:41:28,370 --> 00:41:30,960
mi nemamo na hard-code niz veličine 26.

688
00:41:30,960 --> 00:41:34,400
Možemo umetnuti kao mnogim imenima kao što smo željeli, ali neka se naš 5-minutni predah ovdje

689
00:41:34,400 --> 00:41:38,790
i onda to ispravno.

690
00:41:38,790 --> 00:41:46,020
U redu. Postavio sam priču se prilično umjetno postoji

691
00:41:46,020 --> 00:41:48,670
odabirom Alice, a zatim Bob i onda Charlie, a zatim Anita,

692
00:41:48,670 --> 00:41:51,000
čije ime je očito ide sudariti s Alice.

693
00:41:51,000 --> 00:41:54,120
No, pitanje koje je završio u ponedjeljak je koliko je to vjerojatno

694
00:41:54,120 --> 00:41:56,370
da bi dobili ove vrste sudara? Drugim riječima,

695
00:41:56,370 --> 00:42:00,490
ako ćemo početi koristiti ovaj tablični strukturu, što je zapravo samo niz,

696
00:42:00,490 --> 00:42:02,460
u ovom slučaju 26 lokacija,

697
00:42:02,460 --> 00:42:05,740
što ako su naši ulazi umjesto toga su ravnomjerno raspoređena?

698
00:42:05,740 --> 00:42:09,620
To nije umjetno Alice i Bob i Charlie i David i tako dalje abecednim redom,

699
00:42:09,620 --> 00:42:12,380
to ravnomjerno je raspoređen kroz Z.

700
00:42:12,380 --> 00:42:15,220
>> Možda ćemo samo dobiti sretan i nećemo imati dvije-a ili dva B-a

701
00:42:15,220 --> 00:42:17,640
s vrlo visokom vjerojatnošću, ali kao što je netko istaknuo,

702
00:42:17,640 --> 00:42:20,730
ako ćemo generalizirati taj problem, a ne raditi 0-25

703
00:42:20,730 --> 00:42:26,060
ali, kažu, od 0 do 364 ili 65, često broj dana u tipičnom godine,

704
00:42:26,060 --> 00:42:31,170
i postavio pitanje: "Što je vjerojatnost da su dva od nas u ovoj sobi imaju isti rođendan?"

705
00:42:31,170 --> 00:42:34,600
Stavite to na drugi način, što je vjerojatnost da nas dvoje imaju ime počinje s?

706
00:42:34,600 --> 00:42:37,190
Vrsta pitanje je ista, ali ovaj adresni prostor,

707
00:42:37,190 --> 00:42:39,940
to traži prostor, je veći u slučaju rođendane,

708
00:42:39,940 --> 00:42:42,820
zato što imamo toliko mnogo više dana u godini nego slova u abecedi.

709
00:42:42,820 --> 00:42:44,910
Što je vjerojatnost sudara?

710
00:42:44,910 --> 00:42:48,410
Pa, možemo razmišljati o tome koje figuring out matematike na suprotan način.

711
00:42:48,410 --> 00:42:50,580
Što je vjerojatnost bez sudara?

712
00:42:50,580 --> 00:42:53,970
Pa, ovaj izraz ovdje kaže da je ono što je vjerojatnost

713
00:42:53,970 --> 00:42:58,770
ako postoji samo jedna osoba u ovoj sobi, da oni imaju jedinstvenu rođendan?

714
00:42:58,770 --> 00:43:01,190
To je 100%. Jer, ako postoji samo jedna osoba u sobi,

715
00:43:01,190 --> 00:43:03,940
njegov ili njezin rođendan može biti bilo koji od 365 dana u godini.

716
00:43:03,940 --> 00:43:08,650
Dakle, 365/365 opcija mi daje vrijednost 1.

717
00:43:08,650 --> 00:43:11,250
Dakle vjerojatnost u pitanju u ovom trenutku je samo jedan.

718
00:43:11,250 --> 00:43:13,270
Ali ako postoji druga osoba u sobi,

719
00:43:13,270 --> 00:43:16,490
što je vjerojatnost da je njihov rođendan je drugačiji?

720
00:43:16,490 --> 00:43:20,680
Tu je samo 364 mogućih dana, ignoriranje prijestupnih godina,

721
00:43:20,680 --> 00:43:23,580
za rođendan ne sudaraju s drugim osobama.

722
00:43:23,580 --> 00:43:31,920
Dakle, 364/365. Ako treća osoba dolazi u, to je 363/365, i tako dalje.

723
00:43:31,920 --> 00:43:35,790
Tako smo zadržati množenjem zajedno ove frakcije, koje su sve manji i manji,

724
00:43:35,790 --> 00:43:40,720
shvatiti kolika je vjerojatnost da su svi od nas imaju jedinstvene rođendane?

725
00:43:40,720 --> 00:43:43,570
No, tada možemo, naravno, samo se taj odgovor i okretanje oko

726
00:43:43,570 --> 00:43:47,210
i to jedan minus sve to, izraz kraju smo ćete dobiti

727
00:43:47,210 --> 00:43:51,250
ako se sjećate leđa svojim matematičkim knjigama, to izgleda malo ovako nešto,

728
00:43:51,250 --> 00:43:54,590
koji je mnogo lakše protumačiti grafički.

729
00:43:54,590 --> 00:43:57,820
I ovaj grafički ovdje ima na x osi broj rođendane,

730
00:43:57,820 --> 00:44:02,030
ili broj ljudi s rođendane, i na y osi je vjerojatnost utakmici.

731
00:44:02,030 --> 00:44:06,060
A što je to rekao je da ako imate, recimo, čak,

732
00:44:06,060 --> 00:44:10,860
ajmo izabrati nešto poput 22, 23.

733
00:44:10,860 --> 00:44:13,160
Ako je 22 ili 23 ljudi u sobi,

734
00:44:13,160 --> 00:44:17,100
vjerojatnost da su dva od tih rijetkih ljudi će imati isti rođendan

735
00:44:17,100 --> 00:44:19,560
je zapravo super visoka, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% šanse da je u klasi od samo 22 ljudi, seminarskih, praktički,

737
00:44:23,450 --> 00:44:25,790
2 od tih ljudi će imati isti rođendan.

738
00:44:25,790 --> 00:44:28,520
Budući da je toliko mnogo načina na koje možete imati isti rođendan.

739
00:44:28,520 --> 00:44:31,110
Još gore, ako pogledate na desnoj strani ljestvice,

740
00:44:31,110 --> 00:44:34,040
u trenutku imate klasu sa 58 učenika u njega,

741
00:44:34,040 --> 00:44:39,270
vjerojatnost dvije osobe imaju rođendan je super, super visoke, gotovo 100%.

742
00:44:39,270 --> 00:44:41,880
Sada, to je neka vrsta zabave činjenice o stvarnom životu.

743
00:44:41,880 --> 00:44:45,850
>> Ali implikacije, sada, za strukture podataka i pohranu podataka

744
00:44:45,850 --> 00:44:51,100
znači da samo pod pretpostavkom da imate lijepu, čistu, ujednačenu distribuciju podataka

745
00:44:51,100 --> 00:44:53,650
i imate dovoljno veliki niz stane hrpa stvari

746
00:44:53,650 --> 00:44:59,360
ne znači da ćeš dobiti ljude u jedinstvenim lokacijama.

747
00:44:59,360 --> 00:45:03,810
Ti ćeš imati sudara. Dakle, ovaj pojam hashing, kao što se zove,

748
00:45:03,810 --> 00:45:07,450
uzimanje ulaz kao "Alice" i masirati na neki način

749
00:45:07,450 --> 00:45:10,190
, a zatim vratiti odgovor kao što je 0 ili 1 ili 2.

750
00:45:10,190 --> 00:45:17,500
Vratimo neki izlaz iz te funkcije je udario po ovom vjerojatnost sudara.

751
00:45:17,500 --> 00:45:19,530
Pa kako možemo nositi one sudara?

752
00:45:19,530 --> 00:45:21,940
Pa, na jednom slučaju, možemo uzeti ideju da je predložen.

753
00:45:21,940 --> 00:45:25,100
Mi samo možemo prebaciti sve dolje, ili možda, malo više jednostavno,

754
00:45:25,100 --> 00:45:29,870
nego potez i svi drugi, neka je samo premjestiti Anita na dnu dostupnih mjesta.

755
00:45:29,870 --> 00:45:32,810
Dakle, ako Alice je u 0, svaki je u 1, Charlie je u 2,

756
00:45:32,810 --> 00:45:35,260
samo ćemo staviti Anita na lokaciji tri.

757
00:45:35,260 --> 00:45:38,860
A to je tehnika u strukturama podataka zove linearni sondiranja.

758
00:45:38,860 --> 00:45:41,310
Linearni jer ste samo hodanje ovu liniju, a vi ste vrsta sondiranja

759
00:45:41,310 --> 00:45:43,640
dostupnih mjesta u strukture podataka.

760
00:45:43,640 --> 00:45:46,210
Naravno, to prerasta u O (n).

761
00:45:46,210 --> 00:45:49,590
Ako struktura podataka je jako puno, tu je 25 ljudi u njemu, već

762
00:45:49,590 --> 00:45:54,120
a zatim Anita dolazi zajedno, ona završi u što će biti mjesto Z, i to je u redu.

763
00:45:54,120 --> 00:45:56,540
Ona je još uvijek odgovara, a možemo ju pronaći kasnije.

764
00:45:56,540 --> 00:46:00,100
>> Ali to je bilo u suprotnosti s ciljem ubrzanja njegovih stvari.

765
00:46:00,100 --> 00:46:02,530
Pa što ako smo umjesto uveo ovu treću dimenziju?

766
00:46:02,530 --> 00:46:06,400
To tehnika općenito se zove odvojen ulančavanje, ili imaju lance.

767
00:46:06,400 --> 00:46:10,030
A što hash tablicu je sada, ovaj tablični struktura,

768
00:46:10,030 --> 00:46:13,450
Vaš stol je samo niz pokazivača.

769
00:46:13,450 --> 00:46:18,230
No, ono što ti pokazivače ukazati je pogodite što?

770
00:46:18,230 --> 00:46:21,970
Povezani popis. Pa što ako uzmemo najbolje od oba svijeta?

771
00:46:21,970 --> 00:46:26,500
Mi koristimo polja za prvih indeksa

772
00:46:26,500 --> 00:46:32,070
u strukturu podataka, tako da odmah mogu ići na [0] [1], [30] ili slično,

773
00:46:32,070 --> 00:46:36,480
ali tako da imamo neke fleksibilnost i možemo stati Anita i Alice i Adam

774
00:46:36,480 --> 00:46:38,630
i bilo koje drugo ime,

775
00:46:38,630 --> 00:46:43,470
smo umjesto neka druga os rastu proizvoljno.

776
00:46:43,470 --> 00:46:47,340
I napokon smo, od ponedjeljka, ima tu izražajnu sposobnost s povezanom popisu.

777
00:46:47,340 --> 00:46:49,530
Možemo rasti strukturu podataka samovoljno.

778
00:46:49,530 --> 00:46:52,450
Alternativno, samo smo mogli napraviti veliki 2-dimenzionalni niz,

779
00:46:52,450 --> 00:46:57,190
ali to će biti strašno ako se situacija jedan od redaka u 2-dimenzionalni niz

780
00:46:57,190 --> 00:47:01,280
nije dovoljno velik za dodatnu osobu čije ime se događa početi s A.

781
00:47:01,280 --> 00:47:04,200
Ne daj Bože moramo preusmjeriti veliki 2-dimenzionalnu strukturu

782
00:47:04,200 --> 00:47:06,600
samo zato što je toliko ljudi zove,

783
00:47:06,600 --> 00:47:09,480
pogotovo kad je tako malo ljudi zove Z nešto.

784
00:47:09,480 --> 00:47:12,170
Upravo će to biti vrlo rijetka struktura podataka.

785
00:47:12,170 --> 00:47:15,400
Dakle, to nije savršeno na bilo koji način, ali sada smo barem imaju sposobnost

786
00:47:15,400 --> 00:47:19,090
da odmah pronaći gdje je Alice ili Anita pripada,

787
00:47:19,090 --> 00:47:21,090
barem u smislu vertikalne osi,

788
00:47:21,090 --> 00:47:25,850
i onda mi samo morati odlučiti gdje staviti Anita ili Alice u ovom povezan popisu.

789
00:47:25,850 --> 00:47:32,480
Ako mi ne stalo sortiranje stvari, kako brzo bismo mogli umetnuti Alisa u strukturi kao što je ovaj?

790
00:47:32,480 --> 00:47:35,370
To je konstanta vrijeme. Mi indeks u [0], a ako nitko ne dođe,

791
00:47:35,370 --> 00:47:37,550
Alice ide na početku tog povezanog popisa.

792
00:47:37,550 --> 00:47:40,000
No, to nije velika stvar. Jer ako Anita onda dolazi zajedno

793
00:47:40,000 --> 00:47:42,160
neki broj koraka kasnije, gdje se Anita pripadaju?

794
00:47:42,160 --> 00:47:45,140
Pa, [0]. OOP. Alice je već u tom povezane liste.

795
00:47:45,140 --> 00:47:47,760
>> Ali ako mi nije stalo sortiranje tih imena,

796
00:47:47,760 --> 00:47:53,580
mi samo možemo premjestiti Alice više, umetak Anita, ali čak i da je konstantna vrijeme.

797
00:47:53,580 --> 00:47:57,010
Čak i ako postoji Alice i Adam i svi ovi ostali A imena,

798
00:47:57,010 --> 00:47:59,410
to nije stvarno ih prebacuje fizički. Zašto?

799
00:47:59,410 --> 00:48:04,090
Budući da smo upravo učinio ovdje s povezanog popisa, tko zna bili ti čvorovi su ionako?

800
00:48:04,090 --> 00:48:06,550
Sve što morate učiniti je premjestiti mrvice kruha.

801
00:48:06,550 --> 00:48:10,930
Pomicanje strelice oko, vi ne morate fizički premjestiti sve podatke okolo.

802
00:48:10,930 --> 00:48:14,610
Dakle, možemo ubaciti Anita, u tom slučaju, odmah. Konstantna vrijeme.

803
00:48:14,610 --> 00:48:20,250
Dakle, imamo stalni vremenu lookup, i stalno vremenu umetanje netko poput Anita.

804
00:48:20,250 --> 00:48:22,740
Ali vrsta pretjeranog pojednostavljivanja svijet.

805
00:48:22,740 --> 00:48:28,510
Što ako kasnije želite pronaći Alice?

806
00:48:28,510 --> 00:48:31,050
Što ako kasnije želite pronaći Alice?

807
00:48:31,050 --> 00:48:35,690
Koliko koraka je da će to trajati?

808
00:48:35,690 --> 00:48:37,850
[Studentski odgovor, nerazumljivo]

809
00:48:37,850 --> 00:48:40,950
Točno. Broj osoba prije Alisa u zemlji povezanog popisa.

810
00:48:40,950 --> 00:48:45,420
Dakle, to nije sasvim savršen, jer je naša struktura podataka, opet, ima tu vertikalnu pristup

811
00:48:45,420 --> 00:48:50,240
i onda ima ove povezane liste visi - zapravo, nemojmo izvući ga polje.

812
00:48:50,240 --> 00:48:56,020
To je ta povezani popisi visi od nje da izgleda malo nešto ovako.

813
00:48:56,020 --> 00:48:59,110
No, problem je ako su Alice i Adam i svi ovi ostali A imena

814
00:48:59,110 --> 00:49:01,720
završiti sve više i više postoji,

815
00:49:01,720 --> 00:49:04,810
pronalaženje netko mogao završiti uzimanje hrpa koraka,

816
00:49:04,810 --> 00:49:06,670
bcause morate proći povezanu listu,

817
00:49:06,670 --> 00:49:08,090
koja je linearna operacija.

818
00:49:08,090 --> 00:49:14,270
Pa stvarno, a zatim, umetanja vrijeme konačnici je O (n), gdje je n broj elemenata u popisu.

819
00:49:14,270 --> 00:49:21,780
Podijeljen, ajmo proizvoljno ga zovu m, gdje je m broj linkova popisima

820
00:49:21,780 --> 00:49:24,500
da smo u tom vertikalnoj osi.

821
00:49:24,500 --> 00:49:27,180
Drugim riječima, ako smo doista pretpostaviti jedinstvenu raspodjelu imena,

822
00:49:27,180 --> 00:49:30,150
potpuno nerealno. Tu je očito više od nekih pisama od drugih.

823
00:49:30,150 --> 00:49:32,580
>> Ali ako pretpostavimo za trenutak uniformu distribucije,

824
00:49:32,580 --> 00:49:37,350
i mi smo n ukupno ljude i M ukupne lance

825
00:49:37,350 --> 00:49:40,630
dostupni nama, onda je duljina svake od ovih lanaca

826
00:49:40,630 --> 00:49:44,380
prilično jednostavno će biti ukupno, n podijeljena po broju lanaca.

827
00:49:44,380 --> 00:49:48,900
Dakle, n / m. No, ovdje je mjesto gdje možemo biti svi matematički pametan.

828
00:49:48,900 --> 00:49:53,030
m je konstantna, jer postoji određeni broj njih.

829
00:49:53,030 --> 00:49:54,620
Ideš proglasiti svoj niz na početku,

830
00:49:54,620 --> 00:49:58,450
i nismo resize vertikalnoj osi. Po definiciji, koja ostaje fiksna.

831
00:49:58,450 --> 00:50:01,220
To je samo horizontalna os, da tako kažemo, da se mijenja.

832
00:50:01,220 --> 00:50:04,760
Dakle, tehnički, to je konstanta. Tako sada, umetanja vrijeme

833
00:50:04,760 --> 00:50:09,700
je prilično O (n).

834
00:50:09,700 --> 00:50:12,410
Tako da se ne osjeća sve što je puno bolje.

835
00:50:12,410 --> 00:50:14,940
No, ono što je istina ovdje? Pa, sve ovo vrijeme, za nekoliko tjedana,

836
00:50:14,940 --> 00:50:20,640
mi smo bili rekavši O (n ²). O (n), 2 x n ², - n, podijeljen 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
To je samo n ². Ali sada, u ovom dijelu semestra,

838
00:50:23,580 --> 00:50:25,560
možemo početi govoriti o stvarnom svijetu ponovno.

839
00:50:25,560 --> 00:50:31,520
I n / m je apsolutno brže nego samo n sami.

840
00:50:31,520 --> 00:50:35,170
Ako imate tisuću imena, a vi ih razbiti u više ćelija

841
00:50:35,170 --> 00:50:37,820
tako da imate samo deset imena u svakom od tih lanaca,

842
00:50:37,820 --> 00:50:41,670
Apsolutno potrazi deset stvari će biti brži od tisuću stvari.

843
00:50:41,670 --> 00:50:43,740
I tako jedan od nadolazećih problema setovima će vam izazov

844
00:50:43,740 --> 00:50:46,100
razmišljati o točno da je, iako, da,

845
00:50:46,100 --> 00:50:49,520
asimptotski i matematički, to je još uvijek samo linearno,

846
00:50:49,520 --> 00:50:51,700
koje sranje općenito kada pokušavate pronaći stvari.

847
00:50:51,700 --> 00:50:54,530
U stvarnosti, to će biti brži od toga

848
00:50:54,530 --> 00:50:56,520
zbog toga djelitelj.

849
00:50:56,520 --> 00:50:58,310
I tako se ponovno će biti ovaj trade-off

850
00:50:58,310 --> 00:51:01,390
i ovaj sukob između teorije i stvarnosti,

851
00:51:01,390 --> 00:51:03,550
i jedan od ručice će početi okretati u ovom trenutku u semestru

852
00:51:03,550 --> 00:51:07,510
je više od stvarnosti kao što smo jedna vrsta pripreme za semster kraja,

853
00:51:07,510 --> 00:51:09,280
kao što smo uvesti u svijet web programiranje,

854
00:51:09,280 --> 00:51:11,530
gdje je stvarno, nastup će se računati jer su vaši korisnici će

855
00:51:11,530 --> 00:51:14,880
početi osjećati i cijeniti loše dizajnerske odluke.

856
00:51:14,880 --> 00:51:19,950
>> Pa kako idete o provedbi linked - hash tablicu s 31 elemenata?

857
00:51:19,950 --> 00:51:22,600
I prethodna primjer je samovoljno o rođendanima.

858
00:51:22,600 --> 00:51:26,190
Ako netko ima rođendan 1. siječnja ili 1. veljače, mi ćemo ih u ovom kantu.

859
00:51:26,190 --> 00:51:28,960
Ako je 2. siječnja, 2. veljače, 2. ožujka, mi ćemo ih u ovom kantu.

860
00:51:28,960 --> 00:51:32,220
To je razlog zašto je 31. Kako proglasiti hash tablicu?

861
00:51:32,220 --> 00:51:37,480
To može biti prilično jednostavna, čvor * tablica je moja proizvoljna ime za njega, [31].

862
00:51:37,480 --> 00:51:42,400
To mi daje 31 upućuje na čvorove,

863
00:51:42,400 --> 00:51:45,370
i da mi omogućuje da imaju 31 upućuje na povezane liste

864
00:51:45,370 --> 00:51:48,800
čak i ako ti lanci su u početku NULL.

865
00:51:48,800 --> 00:51:54,860
Što želim staviti ako želim spremiti "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Pa, moramo završiti te stvari u strukturi

867
00:51:57,010 --> 00:52:00,530
jer moramo Alice ukazati na Boba, ukazati na Charlie, i tako dalje.

868
00:52:00,530 --> 00:52:04,940
Ne možemo samo imati imena sama, tako da sam mogao stvoriti novu strukturu zove čvor ovdje.

869
00:52:04,940 --> 00:52:08,310
>> Što je stvarni čvor? Što je čvor u ovom novom povezan popisu?

870
00:52:08,310 --> 00:52:11,840
Prva stvar, zove riječ, je za ime osobe.

871
00:52:11,840 --> 00:52:14,340
DULJINA, vjerojatno, odnosi na maksimalnu duljinu ljudskog ime,

872
00:52:14,340 --> 00:52:18,210
što god da je, 20, 30, 40 znakova u ludim kutak slučajevima,

873
00:52:18,210 --> 00:52:22,680
i jedan je za što? To je samo dodatni NULL karakter, \ 0.

874
00:52:22,680 --> 00:52:27,410
Dakle, ovo je čvor wrapping "nešto" iznutra sebi,

875
00:52:27,410 --> 00:52:29,640
ali također izjavljuje pokazivač zove sljedeći

876
00:52:29,640 --> 00:52:32,580
tako da možemo lanac Alisa se Bob Charlieju i tako dalje.

877
00:52:32,580 --> 00:52:36,700
Može biti NULL, ali ne mora nužno biti.

878
00:52:36,700 --> 00:52:40,110
Sva pitanja o tim hash tablice? Da?

879
00:52:40,110 --> 00:52:46,190
[Studentski molba pitanje, nerazumljivo] array - dobro pitanje.

880
00:52:46,190 --> 00:52:50,120
Zašto je to char riječ u polje, nego samo char *?

881
00:52:50,120 --> 00:52:53,830
U ovom pomalo proizvoljnom primjer, ja ne želim morati posegnuti

882
00:52:53,830 --> 00:52:56,190
da malloc za svaki od originalnih imena.

883
00:52:56,190 --> 00:52:59,530
Htjela sam da proglasi maksimalnu količinu memorije za string

884
00:52:59,530 --> 00:53:06,020
tako da sam mogao kopirati u strukturi Alice \ 0, a ne moraju nositi s malloc i free i slično.

885
00:53:06,020 --> 00:53:11,710
Ali ja mogao učiniti da ako sam htjela biti više svjesni korištenja prostora. Dobro pitanje.

886
00:53:11,710 --> 00:53:14,780
Tako ćemo pokušati generalizirati daleko od toga

887
00:53:14,780 --> 00:53:18,350
i usredotočiti se ostatak danas na podatkovnim strukturama općenito

888
00:53:18,350 --> 00:53:21,170
i drugi problemi koje možemo riješiti pomoću iste osnove

889
00:53:21,170 --> 00:53:24,590
iako su strukture podataka i sami mogu razlikovati u svojim pojedinostima.

890
00:53:24,590 --> 00:53:27,910
>> Tako ispada u informatici, stabla su vrlo česte.

891
00:53:27,910 --> 00:53:29,760
A možete misliti stabla vrste poput obiteljskog stabla,

892
00:53:29,760 --> 00:53:31,830
tamo gdje je neki korijeni, neki matriarch ili patrijarha,

893
00:53:31,830 --> 00:53:34,540
baka ili djed ili ranije vratiti,

894
00:53:34,540 --> 00:53:38,880
ispod kojeg su mama i tata ili razne braća ili slično.

895
00:53:38,880 --> 00:53:42,500
Dakle, struktura stabla ima čvorove i ima djecu,

896
00:53:42,500 --> 00:53:45,260
obično 0 ili više djece za svaki čvor.

897
00:53:45,260 --> 00:53:47,320
A neki od žargona koje vidite na ovoj slici ovdje

898
00:53:47,320 --> 00:53:50,630
je bilo od male djece ili grandkids na rubovima

899
00:53:50,630 --> 00:53:52,330
koji nemaju strelice proizlaze iz njih,

900
00:53:52,330 --> 00:53:55,070
one su tzv lišće, i svatko na unutrašnjost

901
00:53:55,070 --> 00:53:58,790
je unutarnji čvor, možete ga nazvati ništa duž tih linija.

902
00:53:58,790 --> 00:54:01,430
No, ova struktura je prilično čest. Ovo je malo proizvoljna.

903
00:54:01,430 --> 00:54:04,930
Imamo jedno dijete na lijevoj strani, imamo troje djece na desno,

904
00:54:04,930 --> 00:54:06,830
dvoje djece na dnu lijevo.

905
00:54:06,830 --> 00:54:10,740
Dakle, možemo imati različite veličine stabla, ali ako počnemo standardizirati stvari,

906
00:54:10,740 --> 00:54:15,330
a možda podsjetiti ovo od Patrika video na binarnom traženju iz prethodnog kratkog

907
00:54:15,330 --> 00:54:19,490
online, binarno pretraživanje ne moraju se provoditi s nizom

908
00:54:19,490 --> 00:54:21,410
ili komada papira na ploči.

909
00:54:21,410 --> 00:54:25,490
Pretpostavimo da ste željeli pohraniti svoje brojeve u više sofisticirane strukture podataka.

910
00:54:25,490 --> 00:54:27,680
Ti bi mogao stvoriti stablo ovako.

911
00:54:27,680 --> 00:54:35,290
Ti bi mogao imati čvor deklariranih u C, i da čvor može imati najmanje dva elementa unutar njega.

912
00:54:35,290 --> 00:54:39,470
Jedan je broj koji želite pohraniti, a drugi je - dobro, moramo još jednom.

913
00:54:39,470 --> 00:54:41,540
Druga je njegova djeca.

914
00:54:41,540 --> 00:54:45,150
Dakle, ovdje je još jedan struktura podataka. Ovaj put, čvor je definirana kao čuvanje broj n

915
00:54:45,150 --> 00:54:49,060
i onda dva upućuje; lijevo i desno dijete dijete.

916
00:54:49,060 --> 00:54:52,100
A oni nisu proizvoljni. Što je zanimljivo o ovom stablu?

917
00:54:52,100 --> 00:55:00,550
>> Što je uzorak u tome što smo položili ovo van ili kako Patrick ga iznio u svom videu?

918
00:55:00,550 --> 00:55:02,790
To je vrsta očito da postoji neki sortiranje se ovdje događa,

919
00:55:02,790 --> 00:55:04,460
ali ono što je jednostavno pravilo? Da?

920
00:55:04,460 --> 00:55:08,350
[Studentski odgovor, nerazumljivo]

921
00:55:08,350 --> 00:55:12,040
Savršeno. Ako pogled na to, vidjet ćete male brojeve na lijevoj strani,

922
00:55:12,040 --> 00:55:14,690
veliki brojevi na lijevoj strani, ali to je istina za svaki čvor.

923
00:55:14,690 --> 00:55:20,370
Za svaki čvor, njegova lijeva dijete manje od njega, a njegovo pravo dijete veće od njega.

924
00:55:20,370 --> 00:55:25,210
Što to znači sada je, ako želim tražiti ovu strukturu podataka za, recimo, broj 44,

925
00:55:25,210 --> 00:55:29,320
Moram početi u korijenu, jer kao i sa svim tim složenijih struktura podataka sada,

926
00:55:29,320 --> 00:55:31,910
imamo samo pokazivač na jednu stvar, početak.

927
00:55:31,910 --> 00:55:35,010
I u ovom slučaju, početak je korijen. To nije lijevi kraj,

928
00:55:35,010 --> 00:55:39,530
to je korijen ove strukture. Dakle, vidim ovdje je 55, a ja sam u potrazi za 44.

929
00:55:39,530 --> 00:55:41,430
U kojem smjeru želim ići?

930
00:55:41,430 --> 00:55:45,680
Pa, ja želim ići na lijevoj strani, jer očito, na desnoj strani će biti prevelika.

931
00:55:45,680 --> 00:55:49,050
Dakle primijetiti, ti si vrsta konceptualno cijepanje stablo na pola

932
00:55:49,050 --> 00:55:51,700
jer nikad ne ide dolje na desnoj strani.

933
00:55:51,700 --> 00:55:55,410
Dakle, sada idem iz 55 do 33. To je premala broja.

934
00:55:55,410 --> 00:56:01,590
Ja sam u potrazi za 44, ali sada znam da je 44 u tom stablu, mogu otići očito desno.

935
00:56:01,590 --> 00:56:04,460
Pa opet, ja sam orezivanje stabala na pola.

936
00:56:04,460 --> 00:56:06,780
To je prilično puno identičan koncepcijski u telefonski imenik.

937
00:56:06,780 --> 00:56:09,510
To je identičan onome što smo učinili s radovima na ploči,

938
00:56:09,510 --> 00:56:13,940
ali to je više sofisticiran struktura koja omogućuje nam da se zapravo ne

939
00:56:13,940 --> 00:56:16,880
to podijeli pa vladaj po dizajnu algoritma,

940
00:56:16,880 --> 00:56:19,420
i zapravo, poprijeko strukturu ovako - ups.

941
00:56:19,420 --> 00:56:22,870
Prolaskom strukturu ovako, gdje je samo "ići ovaj put ili ići na taj način,"

942
00:56:22,870 --> 00:56:26,870
znači sav taj kod koji Bent svoj um na prvi kada ga provodi u odjeljku

943
00:56:26,870 --> 00:56:31,270
ili šetnju kroz njega kod kuće, za binarnog pretraživanja, koristite rekurzija ili iteraciji

944
00:56:31,270 --> 00:56:35,060
to je bol u vratu. Nađi srednji element, zatim raditi svoj zaokruživanje gore ili dolje.

945
00:56:35,060 --> 00:56:39,230
>> Tu je ljepota na to, jer sada možemo koristiti rekurziju opet,

946
00:56:39,230 --> 00:56:43,760
ali mnogo više čisto. Doista, ako si na broju 55, a vi želite pronaći 44,

947
00:56:43,760 --> 00:56:48,450
idete lijevo, u ovom slučaju, onda što ćete učiniti? Možete pokrenuti isti algoritam.

948
00:56:48,450 --> 00:56:51,560
Možete provjeriti vrijednost čvora, onda idete lijevo ili desno.

949
00:56:51,560 --> 00:56:53,670
Onda ste provjeriti vrijednost čvora, ići lijevo ili desno.

950
00:56:53,670 --> 00:56:56,710
To je savršeno pogodna za rekurzije.

951
00:56:56,710 --> 00:57:00,920
Dakle, iako je u prošlosti smo napravili neke prilično proizvoljnih primjera uključuju rekurziju

952
00:57:00,920 --> 00:57:03,430
da nije potrebno da se rekurzivna, s podacima struktura tamo,

953
00:57:03,430 --> 00:57:07,820
osobito drveće, to je savršena primjena ove ideje uzimanja problem,

954
00:57:07,820 --> 00:57:12,920
ga smanjuje, a zatim rješavanje isti tip, ali manji, program.

955
00:57:12,920 --> 00:57:14,590
>> Dakle, postoji još jedna struktura podataka da možemo uvesti.

956
00:57:14,590 --> 00:57:18,760
To je osmišljen na prvi pogled izgleda zagonetan, ali ovo je nevjerojatno.

957
00:57:18,760 --> 00:57:25,090
Dakle, ovo je struktura podataka zove trie, trie, koji je naslijedio od riječi dohvat,

958
00:57:25,090 --> 00:57:30,210
koji se ne izgovara ponovno probati-Val, ali to je ono što svijet naziva te stvari. Pokušava. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
To je stablo struktura neke vrste, ali svaki od čvorova u trie

960
00:57:35,190 --> 00:57:41,280
Čini se da je ono što? A to je malo zabludu, jer to je vrsta skraćeno.

961
00:57:41,280 --> 00:57:45,960
No, izgleda da svaki čvor u ovom trie je zapravo niz.

962
00:57:45,960 --> 00:57:48,840
I iako autor ovog dijagrama ga nije pokazala,

963
00:57:48,840 --> 00:57:54,130
u ovom slučaju, to trie je struktura podataka čija je svrha u životu je pohraniti riječi

964
00:57:54,130 --> 00:57:57,330
Poput-l-I-c-e ili B-O-B.

965
00:57:57,330 --> 00:58:02,480
A način na koji je taj podatak pohranjuje Alice i Bob i Charlie i Anita i tako dalje

966
00:58:02,480 --> 00:58:06,970
se koristi niz kojim se pohraniti Alisa u trie,

967
00:58:06,970 --> 00:58:09,820
možemo početi na korijen čvor koji izgleda kao niz,

968
00:58:09,820 --> 00:58:12,080
i to je bio napisan u stenogram notaciji.

969
00:58:12,080 --> 00:58:15,070
Autor izostavljen abcdefg jer nije bilo imena s tim.

970
00:58:15,070 --> 00:58:19,150
Oni su samo pokazali M i P i T, ali u ovom slučaju,

971
00:58:19,150 --> 00:58:22,780
krenimo od Alice i Bob i Charlie nekim imenima koja su ovdje.

972
00:58:22,780 --> 00:58:25,670
Maxwell je zapravo u ovom dijagramu.

973
00:58:25,670 --> 00:58:29,570
Pa kako je autora dućan M--x-w-e-l-ja?

974
00:58:29,570 --> 00:58:36,990
On ili ona je počela na korijen čvor, te je otišao na [M], tako otprilike 13, 13. mjesto u polju.

975
00:58:36,990 --> 00:58:40,750
Onda od tamo, tu je pokazivač.

976
00:58:40,750 --> 00:58:42,760
Pokazivač dovodi do drugog niza.

977
00:58:42,760 --> 00:58:47,880
Od tamo autor indeksirane u tom polju na lokaciji A, kao što je prikazano tamo na gornjem lijevom kutu,

978
00:58:47,880 --> 00:58:52,250
i onda on ili ona je slijedila taj pokazivač na drugo polje,

979
00:58:52,250 --> 00:58:55,460
i otišao na pokazivač na mjesto X.

980
00:58:55,460 --> 00:58:59,840
Zatim u sljedećem polja lokacije W, E, L, L, i tako dalje,

981
00:58:59,840 --> 00:59:03,090
i na kraju, neka je zapravo pokušati staviti sliku na ovo.

982
00:59:03,090 --> 00:59:05,380
Što čvor izgleda u kodu?

983
00:59:05,380 --> 00:59:11,820
Čvor u trie sadrži niz upućuje na daljnje čvorova.

984
00:59:11,820 --> 00:59:16,090
No, tu je također dobio biti neka vrsta Boolean vrijednosti, barem u ovom provedbu.

985
00:59:16,090 --> 00:59:18,770
Ja se dogoditi da ga zovu is_word. Zašto?

986
00:59:18,770 --> 00:59:22,670
Jer kad ste umetanja Maxwell, niste umetanja

987
00:59:22,670 --> 00:59:25,300
ništa u ovom strukturom podataka.

988
00:59:25,300 --> 00:59:27,480
Vi ne pišeš M. Vi ne pišeš X.

989
00:59:27,480 --> 00:59:30,240
Sve što radite je nakon pokazivače.

990
00:59:30,240 --> 00:59:33,360
Pokazivač koji predstavlja m, zatim pokazivač koji predstavlja,

991
00:59:33,360 --> 00:59:36,310
zatim pokazivač koji predstavlja X, zatim W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
ali ono što vam je potrebno učiniti na kraju je nekako ide, provjerite, došao sam do ovu lokaciju.

993
00:59:41,950 --> 00:59:45,560
Tu je riječ koja završava ovdje u strukture podataka.

994
00:59:45,560 --> 00:59:48,190
>> Dakle, ono što trie stvarno je ispunjen, a autor je izabrao da predstavljaju

995
00:59:48,190 --> 00:59:51,880
ove terminuses s malim trokutima.

996
00:59:51,880 --> 00:59:56,470
To samo znači da je činjenica to trokut je ovdje, to boolean vrijednost istina

997
00:59:56,470 --> 00:59:59,200
znači, ako idete natrag u stablu,

998
00:59:59,200 --> 01:00:02,420
to znači da je riječ zove Maxwell je u tome.

999
01:00:02,420 --> 01:00:04,870
No, riječ foo, na primjer,

1000
01:00:04,870 --> 01:00:07,970
nije u stablu, jer ako krenem na korijen čvor se ovdje na vrhu,

1001
01:00:07,970 --> 01:00:14,030
Nema ž pokazivač, ne o pokazivač, ne o pokazivač. Foo nije ime u ovom rječniku.

1002
01:00:14,030 --> 01:00:22,460
No s druge strane, Turing, t-u-r-i-n-g. Opet, nisam pohraniti t ili u ili R ili ja ili n ili g.

1003
01:00:22,460 --> 01:00:29,820
Ali sam dućan u ovom strukture podataka vrijednost istinske putu prema dolje, ovdje u ovom čvoru - u stablo

1004
01:00:29,820 --> 01:00:33,030
postavljanjem ovog boolean vrijednost is_word na true.

1005
01:00:33,030 --> 01:00:35,740
Dakle trie je vrsta ovog vrlo zanimljivog meta strukture,

1006
01:00:35,740 --> 01:00:39,810
gdje niste stvarno spremanje riječi se za ovu vrstu rječniku.

1007
01:00:39,810 --> 01:00:45,100
Da bude jasno, vi ste samo čuvanje da ili ne, tu je riječ koja završava ovdje.

1008
01:00:45,100 --> 01:00:46,430
>> Sada ono što je implikacija?

1009
01:00:46,430 --> 01:00:51,120
Ako imate 150.000 riječi u rječniku da ste pokušavate spremiti u memoriju

1010
01:00:51,120 --> 01:00:53,400
koristite nešto poput povezane liste,

1011
01:00:53,400 --> 01:00:56,870
ćete imati 150.000 čvorova u vašem povezane liste.

1012
01:00:56,870 --> 01:01:00,250
I pronalaženje jednog od tih riječi po abecednom redu moglo potrajati O (n) vremena.

1013
01:01:00,250 --> 01:01:04,370
Linearno vrijeme. No, u slučaju ovdje od trie,

1014
01:01:04,370 --> 01:01:09,210
što je trčanje vrijeme pronalaženje riječ?

1015
01:01:09,210 --> 01:01:17,390
Ispada ljepotu ovdje je da, čak i ako imate 149.999 riječi već u ovom rječniku,

1016
01:01:17,390 --> 01:01:20,170
kao proveden s ovom strukturom podataka,

1017
01:01:20,170 --> 01:01:25,560
koliko vremena je potrebno pronaći ili umetnuti još jednu osobu na to, kao i Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Pa, to je samo pet, možda šest koraka za prateći karaktera.

1019
01:01:30,640 --> 01:01:32,880
Zbog presense drugih imena u strukturi

1020
01:01:32,880 --> 01:01:35,340
ne dobiti na način umetanja Alice.

1021
01:01:35,340 --> 01:01:39,640
Štoviše, pronalaženje Alice kada postoji 150.000 riječi u ovom rječniku

1022
01:01:39,640 --> 01:01:41,960
ne dobiti u svoj način pronalaženja Alisa uopće,

1023
01:01:41,960 --> 01:01:46,880
jer je Alice. . . . . ovdje, jer sam pronašao boolean vrijednost.

1024
01:01:46,880 --> 01:01:50,920
A ako nema boolean istina, onda je Alice nije u ovom podataka strukturi riječi.

1025
01:01:50,920 --> 01:01:56,220
Drugim riječima, radi vrijeme pronalaženje stvari i umetanjem stvari u ovaj novi

1026
01:01:56,220 --> 01:02:01,920
podaci struktura trie je O od - to nije n.

1027
01:02:01,920 --> 01:02:05,730
Zbog presense od 150.000 ljudi nema nikakvog utjecaja na Alice, čini se.

1028
01:02:05,730 --> 01:02:11,560
Dakle, nazovimo ga k, gdje je k Maksimalna duljina riječi u engleskom jeziku

1029
01:02:11,560 --> 01:02:14,050
koji je obično ne više od 20 i nešto znakova.

1030
01:02:14,050 --> 01:02:17,940
Tako je k konstanta. Dakle, Sveti Gral mi se čini da su našli sada

1031
01:02:17,940 --> 01:02:26,000
je da je trie, stalnom vremena za umetaka za dohvate, za brisanje.

1032
01:02:26,000 --> 01:02:29,170
Zbog nekoliko stvari koje su već u strukturi,

1033
01:02:29,170 --> 01:02:32,600
koji nisu ni fizički tamo. Opet, oni su samo vrsta provjeravaju off, da ili ne,

1034
01:02:32,600 --> 01:02:35,050
nema utjecaja na njezino buduće vrijeme rada.

1035
01:02:35,050 --> 01:02:37,940
>> No, tu je dobio biti kvaka, inače ne bismo izgubiti toliko vremena

1036
01:02:37,940 --> 01:02:41,460
na svim tim drugim strukturama podataka samo konačno doći do tajnog onaj koji je nevjerojatna.

1037
01:02:41,460 --> 01:02:46,410
Dakle, ono što cijena plaćamo da bi se postigao ovaj veličinu ovdje? Prostor.

1038
01:02:46,410 --> 01:02:49,010
Ova stvar je masivan. A razlog da autor

1039
01:02:49,010 --> 01:02:52,400
nije ga predstaviti ovdje, primijetiti da sve ove stvari koje izgledaju kao polja,

1040
01:02:52,400 --> 01:02:55,400
nije izvući ostatak stabla, ostatak trie,

1041
01:02:55,400 --> 01:02:58,060
jer oni samo nisu relevantni za priču.

1042
01:02:58,060 --> 01:03:01,870
No, sve ove čvorove su super široka, a svaki čvor u stablu zauzima

1043
01:03:01,870 --> 01:03:07,780
26 ili zapravo, mogao biti 27 znakova, jer je u ovom slučaju bio sam uključujući prostor za apostrofa

1044
01:03:07,780 --> 01:03:09,980
tako da smo mogli imati apostrophized riječi.

1045
01:03:09,980 --> 01:03:14,450
U ovom slučaju, to su široke polja. Dakle, iako oni ne picutured,

1046
01:03:14,450 --> 01:03:18,190
to traje do masivan iznos od RAM-a.

1047
01:03:18,190 --> 01:03:20,670
Koji bi moglo biti u redu, especilly u modernom hardveru,

1048
01:03:20,670 --> 01:03:25,650
ali to je tradeoff. Mi smo dobili manje vrijeme trošiti više prostora.

1049
01:03:25,650 --> 01:03:28,580
Dakle, gdje je sve ovo ide?

1050
01:03:28,580 --> 01:03:32,640
Pa, hajdemo napraviti - ajmo vidjeti ovdje.

1051
01:03:32,640 --> 01:03:39,510
Ajmo napraviti skok s ovim tipom ovdje.

1052
01:03:39,510 --> 01:03:43,450
>> Vjerovali ili ne, koliko zabavno kao C je za neko vrijeme sada,

1053
01:03:43,450 --> 01:03:48,130
mi smo dostizanje točke u semestru u kojem je vrijeme za prijelaz na stvari više modernih.

1054
01:03:48,130 --> 01:03:50,950
Stvari su na višoj razini. I iako za narednih nekoliko tjedana

1055
01:03:50,950 --> 01:03:54,580
svejedno ćemo nastaviti da se uroniti u svijetu upućuje i memorije upravljanje

1056
01:03:54,580 --> 01:03:57,210
da biste dobili taj komfor s kojima smo tada može graditi na,

1057
01:03:57,210 --> 01:04:01,270
Kraj igra je konačno uvesti, ironično, nije taj jezik.

1058
01:04:01,270 --> 01:04:03,330
Prespavat ćemo, kao i 10 minuta govori o HTML-u.

1059
01:04:03,330 --> 01:04:05,950
Sve HTML je jezik za označavanje, a ono što je jezik za označavanje

1060
01:04:05,950 --> 01:04:10,220
je to niz otvorenih i zatvorenih zagrada zagrade da kažu "da je ovo podebljano '

1061
01:04:10,220 --> 01:04:12,000
'Čine ovaj kurziv' 'čine ovaj centered. "

1062
01:04:12,000 --> 01:04:14,250
To nije sve što je intelektualno zanimljiv, ali to je super korisno.

1063
01:04:14,250 --> 01:04:16,650
I to je sigurno sveprisutni ovih dana.

1064
01:04:16,650 --> 01:04:19,450
No, ono što je snažan o svijetu HTML i web programiranje općenito,

1065
01:04:19,450 --> 01:04:25,910
gradi dinamične stvari; pisanja koda u jezicima kao što su PHP ili Python ili Ruby ili Jave ili C #.

1066
01:04:25,910 --> 01:04:30,360
Stvarno, bez obzira na vaš jezik izbora je, i generira HTML dinamički.

1067
01:04:30,360 --> 01:04:32,960
Generiranje nešto što se zove CSS dinamički.

1068
01:04:32,960 --> 01:04:35,810
Cascading Style Sheets, što je također o estetici.

1069
01:04:35,810 --> 01:04:41,360
I tako, iako, danas, ako odem na neku web stranicu kao što je poznato Google.com,

1070
01:04:41,360 --> 01:04:46,100
i idem na pregled, programer, pogled izvor, koji možda ste učinili prije,

1071
01:04:46,100 --> 01:04:49,800
ali ide na pregled izvora, ova stvar vjerojatno izgleda prilično zagonetan.

1072
01:04:49,800 --> 01:04:55,320
No, to je temeljni kod koji implementira Google.com.

1073
01:04:55,320 --> 01:04:57,940
Na prednjem kraju. A zapravo sve je to pahuljasto estetika stvari.

1074
01:04:57,940 --> 01:05:01,740
Ovo je CSS ovdje. Ako držim pomicanje dolje ćemo dobiti neki color-coded stvari.

1075
01:05:01,740 --> 01:05:06,890
Ovo je HTML. Googleov kod izgleda kao nered, ali ako sam zapravo otvoriti drugu prozor,

1076
01:05:06,890 --> 01:05:09,380
možemo vidjeti neke strukture za to.

1077
01:05:09,380 --> 01:05:12,640
Ako sam otvoriti ovaj gore, primjetiti ovdje, to je malo više čitati.

1078
01:05:12,640 --> 01:05:16,850
Idemo vidjeti prije dugo tu oznaku, [riječ] je oznaka,

1079
01:05:16,850 --> 01:05:23,520
HTML, glava, tijelo, div, skripta, tekst područje, opseg, usmjeren, div.

1080
01:05:23,520 --> 01:05:26,770
I to je također vrsta zagonetna izgleda na prvi pogled,

1081
01:05:26,770 --> 01:05:30,890
ali sve ove nered slijedi određene obrasce i ponovljive uzorke,

1082
01:05:30,890 --> 01:05:33,850
tako da nakon što smo dobili osnove dolje, vi ćete biti u mogućnosti pisati kod ovako

1083
01:05:33,850 --> 01:05:37,550
i onda manipulirati kod ovako pomoću još jedan jezik, zove JavaScripta.

1084
01:05:37,550 --> 01:05:40,440
A JavaScript je jezik koji se izvodi unutar pregledniku

1085
01:05:40,440 --> 01:05:44,380
danas da mi koristimo na Harvard tečajeva, za alat kolegija trgovačkog da Google maps koristi

1086
01:05:44,380 --> 01:05:48,660
da vam cijela hrpa dinamike, Facebook vam daje pokazati trenutak ažuriranja statusa,

1087
01:05:48,660 --> 01:05:51,430
Twitter koristi ga da vam pokazati tweets odmah.

1088
01:05:51,430 --> 01:05:53,820
Sve to ćemo početi da se uroniti u.

1089
01:05:53,820 --> 01:05:57,190
Ali doći, moramo shvatiti nešto o internetu.

1090
01:05:57,190 --> 01:06:01,130
Ovaj isječak ovdje je samo minutu, i pretpostavimo za sada je to, u stvari,

1091
01:06:01,130 --> 01:06:08,380
kako internet funkcionira kao teaser za ono što je oko doći. Dajem vam "Ratnici na Netu."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Sporo refren glazba ♫]

1093
01:06:14,720 --> 01:06:20,450
[Muško pripovjedač] On je došao s porukom.

1094
01:06:20,450 --> 01:06:23,770
Uz protokola sve njegove vlastite.

1095
01:06:23,770 --> 01:06:37,270
[♫ brže elektronske glazbe ♫]

1096
01:06:37,270 --> 01:06:41,330
On je došao na svijet cool firewall, uncaring routera,

1097
01:06:41,330 --> 01:06:45,690
i opasnosti daleko gorih od smrti.

1098
01:06:45,690 --> 01:06:55,400
On je brzo. On je jak. On je TCP / IP, a on je dobio svoju adresu.

1099
01:06:55,400 --> 01:06:59,250
Ratnici Net.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Sljedeći tjedan, onda. Internet. Web programiranje. Ovo je CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]