1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Teden 6, Nadaljevanje]

2
00:00:02,520 --> 00:00:04,160
[David J. Malan] [Harvard University]

3
00:00:04,160 --> 00:00:08,720
[To je CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
To je CS50 in to je konec 6. tednu.

5
00:00:12,970 --> 00:00:17,970
Torej CS50x, eden od prvih programov Harvarda, vključenih v pobudo EDX

6
00:00:17,970 --> 00:00:20,590
celo debitiral v preteklem ponedeljek.

7
00:00:20,590 --> 00:00:23,460
Če bi želeli, da bi dobili vpogled, kaj drugi na internetu

8
00:00:23,460 --> 00:00:27,180
Zdaj spremljate skupaj z lahko glavo, da x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
To vas bo preusmeril na ustrezno mesto na edx.org,

10
00:00:30,350 --> 00:00:34,160
ki je bil po tem in drugih tečaje iz MIT in Berkeley zdaj živi.

11
00:00:34,160 --> 00:00:38,140
Boste morali, da se prijavite za račun, boste ugotovili, da je material v veliki meri enaki

12
00:00:38,140 --> 00:00:42,170
kot ste imeli ta semester, čeprav z zamudo v nekaj tednih, saj smo dobili vse pripravljeno.

13
00:00:42,170 --> 00:00:46,930
Toda kaj študenti CS50x bodo zdaj videli, je vmesnik precej, kot je ta.

14
00:00:46,930 --> 00:00:50,040
To, na primer, je Zamyla vodi walkthrough za postavitev problema 0.

15
00:00:50,040 --> 00:00:54,230
Ob prijavi na edx.org, CS50x študent vidi marsikaj

16
00:00:54,230 --> 00:00:57,170
, ki bi jih pričakujejo v času: predavanje za ponedeljek,

17
00:00:57,170 --> 00:01:01,650
predavanje v sredo, različne kratke hlače, problem sprejemnikov, walkthroughs, datotek PDF.

18
00:01:01,650 --> 00:01:04,459
Poleg tega, kot jih vidite tukaj, strojni prevodi

19
00:01:04,459 --> 00:01:08,390
angleških transkriptov v kitajski, japonski, španski, italijanski,

20
00:01:08,390 --> 00:01:12,810
in cel kup drugih jezikov, ki bo zagotovo nepopolna

21
00:01:12,810 --> 00:01:15,840
kot smo jih razvaljamo načrtno uporabo nekaj, kar ti API,

22
00:01:15,840 --> 00:01:18,360
ali programski vmesnik, iz Googla

23
00:01:18,360 --> 00:01:21,360
ki nam omogoča, da pretvorite angleškem teh drugih jezikih.

24
00:01:21,360 --> 00:01:24,100
Ampak hvala za čudovito duhu nekaj sto in nekaj prostovoljcev,

25
00:01:24,100 --> 00:01:26,940
naključnih ljudi na internetu, ki so se prijazno ponudili, da se vključijo

26
00:01:26,940 --> 00:01:30,180
v tem projektu, bomo postopno izboljšanje kakovosti teh prevodov

27
00:01:30,180 --> 00:01:35,790
ki jih imajo ljudje popraviti napake, ki so naši računalniki naredili.

28
00:01:35,790 --> 00:01:42,330
>> Tako se izkaže, da je nekaj več študentov pokažejo v ponedeljek, kot smo sprva pričakovali.

29
00:01:42,330 --> 00:01:48,980
Pravzaprav, zdaj CS50x ima 100.000 ljudi po skupaj doma.

30
00:01:48,980 --> 00:01:54,430
Tako ugotoviš, da so vsi del tega Uvodno razred da se ta tečaj računalništva

31
00:01:54,430 --> 00:01:57,370
izobraževanja bolj na splošno, širše dostopen.

32
00:01:57,370 --> 00:02:00,130
In v resnici je zdaj, z nekaterimi od teh velikih spletnih tečajev,

33
00:02:00,130 --> 00:02:04,070
vsi so začeli s temi zelo visokih številk, kot se zdi, da so tukaj končali.

34
00:02:04,070 --> 00:02:08,759
Vendar pa je cilj, v končni fazi, CS50x je res, da bi dobili čim več ljudi do ciljne črte, kot je mogoče.

35
00:02:08,759 --> 00:02:12,000
Z zasnovo CS50x se bo ponujena od tega preteklo ponedeljek

36
00:02:12,000 --> 00:02:17,430
vse tja do 15. april 2013, tako da ljudje, ki imajo šolske obveznosti drugje,

37
00:02:17,430 --> 00:02:20,990
delo, družina, drugi konflikti in podobno, imajo malo več prožnosti

38
00:02:20,990 --> 00:02:23,640
s katerimi se potopite v tem tečaju, ki je dovolj opozoriti na to,

39
00:02:23,640 --> 00:02:30,540
je zelo ambiciozno le v primeru, če v teku samo treh mesecih med običajni semester.

40
00:02:30,540 --> 00:02:34,190
Vendar pa se bodo ti študenti reševanje istega problema sklopov, si isto vsebino,

41
00:02:34,190 --> 00:02:36,350
ki imajo dostop do istih hlačah in podobno.

42
00:02:36,350 --> 00:02:38,990
Tako spoznamo, da smo vsi res v tem skupaj.

43
00:02:38,990 --> 00:02:42,360
In eden od končnih ciljev CS50x ne samo da bi dobili čim več ljudje

44
00:02:42,360 --> 00:02:45,720
do ciljne črte, in jim to na novo odkrito razumevanje računalništva

45
00:02:45,720 --> 00:02:49,000
in programiranje, ampak tudi, da so jih imeli te skupne izkušnje.

46
00:02:49,000 --> 00:02:52,010
Ena od pomembnih značilnosti 50 na kampusu, upamo,

47
00:02:52,010 --> 00:02:56,260
je bila ta vrsta komunalne izkušenj, za boljše ali slabše, včasih,

48
00:02:56,260 --> 00:02:59,480
vendar imajo ti ljudje obrnejo na levo in desno,

49
00:02:59,480 --> 00:03:01,830
in uradne ure in hackathon in pošteno.

50
00:03:01,830 --> 00:03:04,560
To je malo težje narediti, da osebe z ljudje na spletu,

51
00:03:04,560 --> 00:03:10,580
vendar bo CS50x sklene aprila s prvim vedno CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
ki bo dosegljiv prilagoditev naši ideji sejma

53
00:03:13,630 --> 00:03:18,250
ko bodo ti na tisoče študentov, vsi povabljeni k oddaji 1 - do 2-minutni video,

54
00:03:18,250 --> 00:03:22,480
bodisi screencast njihovega zadnjega projekta ali video njimi mahal zdravo

55
00:03:22,480 --> 00:03:24,490
in govori o svojem projektu in ga demoing,

56
00:03:24,490 --> 00:03:27,610
podobno kot vaša predhodnika tu naredil na univerzi na sejmu,

57
00:03:27,610 --> 00:03:31,400
tako da do konca semester, upanje je, da so na svetovni razstavi

58
00:03:31,400 --> 00:03:37,080
iz velikih CS50x učencev končnih projektov, podobno kot je to, kar vas čaka v decembru tukaj na kampusu.

59
00:03:37,080 --> 00:03:39,680
Torej, več o tem v prihodnjih mesecih.

60
00:03:39,680 --> 00:03:43,640
>> S 100.000 študentov, čeprav gre za potrebo po še nekaj CA.

61
00:03:43,640 --> 00:03:47,590
Glede na to, da so fantje neverjetno pot tukaj, in ob CS50

62
00:03:47,590 --> 00:03:51,630
nekaj tednov pred objavo tega materiala je na ljudi, na EDX,

63
00:03:51,630 --> 00:03:55,330
zavedate, da bi rad, da gre čim več naših študentov, kot je to mogoče pri tej pobudi,

64
00:03:55,330 --> 00:03:58,720
tako v polletju, kot tudi to zimo, in to prihaja pomlad.

65
00:03:58,720 --> 00:04:01,620
Torej, če bi želeli, da se vključijo v CS50x,

66
00:04:01,620 --> 00:04:07,450
zlasti pridružil na CS50x razpravljajo je različica z EDX CS50 razpravljajo,

67
00:04:07,450 --> 00:04:10,140
ki ga mnogi od vas so bili z uporabo na univerzi, online oglasna deska,

68
00:04:10,140 --> 00:04:13,040
prosim, od glave do tega URL-ja, nam to sporočite, kdo ste,

69
00:04:13,040 --> 00:04:16,450
zato, ker bi radi, da zgraditi ekipo študentov in osebja in Fakulteta enako

70
00:04:16,450 --> 00:04:19,630
na kampusu, ki so preprosto igrajo skupaj in pomoč.

71
00:04:19,630 --> 00:04:21,720
In ko bodo videli, vprašanje, ki je seznanjeni,

72
00:04:21,720 --> 00:04:25,320
slišite študenta poročanja nekaj bug nekje v neki državi, na internetu,

73
00:04:25,320 --> 00:04:27,450
in da so obroči zvon, ker tudi vi imeli ta isti problem

74
00:04:27,450 --> 00:04:32,620
v vašem d dvorani nekaj časa nazaj, upam, da potem lahko trobili v en rog in delite svoje izkušnje.

75
00:04:32,620 --> 00:04:37,300
Zato vas prosimo, da sodelujete, če bi želeli.

76
00:04:37,300 --> 00:04:39,360
>> Tečaje računalništva na Harvardu imajo malo tradicije,

77
00:04:39,360 --> 00:04:44,730
CS50 med njimi, da ima nekaj oblačil, nekaj oblačil, ki jih lahko nosite s ponosom

78
00:04:44,730 --> 00:04:49,090
na koncu semester, ki pravijo, zelo ponosno, da končate CS50

79
00:04:49,090 --> 00:04:51,830
in je CS50 in podobno, in smo vedno poskušali vključiti učence

80
00:04:51,830 --> 00:04:54,540
v tem procesu, kolikor je to mogoče, pri čemer vas vabimo,

81
00:04:54,540 --> 00:04:56,900
po tem času semestra študenti predložiti načrte

82
00:04:56,900 --> 00:04:59,330
uporabljate Photoshop, ali karkoli orodje želite uporabljati

83
00:04:59,330 --> 00:05:02,330
Če ste oblikovalec, naj predložijo načrte za majice in jopice

84
00:05:02,330 --> 00:05:06,100
in dežniki in malo bandanas za pse imamo in podobno.

85
00:05:06,100 --> 00:05:09,370
In vse, kar je nato - zmagovalci vsako leto, se nato razstavil

86
00:05:09,370 --> 00:05:12,700
na spletni strani Seveda je pri store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Vse se prodaja po ceni, toda le spletna stran se zažene

88
00:05:15,790 --> 00:05:18,330
in omogoča ljudem, da izberete barve in modele, ki so jim všeč.

89
00:05:18,330 --> 00:05:20,420
Pa sem mislil, da bova samo deliti nekaj modelov lanskoletnih

90
00:05:20,420 --> 00:05:25,130
da so na spletni strani poleg tega je ta v tej zadevi, ki je letno tradicijo.

91
00:05:25,130 --> 00:05:29,410
"Vsak dan sem SEG Faultn" je bila ena od vlog v lanskem letu,

92
00:05:29,410 --> 00:05:32,290
ki je še vedno tam na voljo za diplomantom.

93
00:05:32,290 --> 00:05:35,820
Imeli smo enega, "CS50, ustanovljena 1989."

94
00:05:35,820 --> 00:05:39,010
Eden od naših Bowdens Rob, je bil zelo priljubljen lani.

95
00:05:39,010 --> 00:05:43,480
"Ekipa Bowden" se je rodil, je bila ta oblika vpisali med najboljših prodajalcev.

96
00:05:43,480 --> 00:05:49,040
Ker je bila to ena tukaj. Veliko ljudi je bilo "Bowden Fever" v skladu s prodajnimi hlodov.

97
00:05:49,040 --> 00:05:52,650
Zavedaj se, da bi zdaj lahko vaš model tam gor na internetu.

98
00:05:52,650 --> 00:05:57,510
Več podrobnosti o tem v naslednjem problemu določa, da pridejo.

99
00:05:57,510 --> 00:06:00,330
>> Še eno orodje: ste imeli nekaj izpostavljenosti in upam, da zdaj

100
00:06:00,330 --> 00:06:02,350
nekatere praktične izkušnje z gdb,

101
00:06:02,350 --> 00:06:04,570
ki je, seveda, razhroščevalnik in vam omogoča, da manipulira

102
00:06:04,570 --> 00:06:09,500
vaš program na razmeroma nizki ravni, gre za kakšne stvari?

103
00:06:09,500 --> 00:06:13,030
Kaj GDB kaj si naredil?

104
00:06:13,030 --> 00:06:15,030
Ja? Daj mi nekaj. [Student odgovor, nerazumljiv]

105
00:06:15,030 --> 00:06:18,120
Dobro. Korak v funkcijo, tako da ne boste morali vnesti zagon

106
00:06:18,120 --> 00:06:22,310
in imajo program udarec skozi celoti, tiskanje stvari na standardni izhod.

107
00:06:22,310 --> 00:06:25,190
Namesto tega lahko stopite skozi to vrstico po vrstico, ali vnesete naslednjo

108
00:06:25,190 --> 00:06:30,300
iti po vrsticah z vrvico ali stopnjo, da se potopite v funkciji, ponavadi tisti, ki si napisal.

109
00:06:30,300 --> 00:06:35,240
Kaj drugega GDB kaj si naredil? Ja? [Student odgovor, nerazumljiv]

110
00:06:35,240 --> 00:06:38,100
Natisni spremenljivk. Torej, če želite, da to malo introspekcijo znotraj vašega programa

111
00:06:38,100 --> 00:06:41,500
ne bilo treba zateči k pisanju printf izjave po vsem mestu,

112
00:06:41,500 --> 00:06:44,600
lahko samo natisniti spremenljivko ali prikazati spremenljivko.

113
00:06:44,600 --> 00:06:46,710
Kaj še lahko narediš z razhroščevalnik gdb podobnega?

114
00:06:46,710 --> 00:06:49,170
[Student odgovor, nerazumljiv]

115
00:06:49,170 --> 00:06:52,080
Točno tako. Nastavite lahko prelomnih točk, ki jih lahko rekli prekinitvijo izvajanja

116
00:06:52,080 --> 00:06:54,020
Na glavno funkcijo ali funkcije foo.

117
00:06:54,020 --> 00:06:56,800
Lahko rečemo prekinitvijo izvajanja v vrstici 123.

118
00:06:56,800 --> 00:06:58,950
In Prelomne točke so zelo močna tehnika

119
00:06:58,950 --> 00:07:01,110
ker če imate splošno občutek, kje je vaš problem

120
00:07:01,110 --> 00:07:05,360
Verjetno je, da vam ni treba izgubljati časa z poglobitvi celoti programa.

121
00:07:05,360 --> 00:07:08,250
Lahko skočite v bistvu tam in začnite tipkati -

122
00:07:08,250 --> 00:07:10,970
Vmesni skozi, korak ali dostavo ali podobno.

123
00:07:10,970 --> 00:07:14,340
Ampak ulov z nekaj podobnega gdb je, da vam pomaga, človeški,

124
00:07:14,340 --> 00:07:16,940
našli svoje težave in najti svoje napake.

125
00:07:16,940 --> 00:07:19,470
Ni nujno, da je bil toliko jih za vas.

126
00:07:19,470 --> 00:07:23,070
>> Tako smo uvedli drugi dan style50, ki je kratek ukazni vrstici orodje

127
00:07:23,070 --> 00:07:27,500
da poskuša Stilizovati kodo malo bolj čisto kot ti, bi lahko človek, ki so ga opravili.

128
00:07:27,500 --> 00:07:29,530
Ampak tudi to je res samo estetska stvar.

129
00:07:29,530 --> 00:07:34,110
Izkaže pa se, da je to drugo orodje, imenovano Valgrind, da je malo bolj skrivnostno za uporabo.

130
00:07:34,110 --> 00:07:36,860
Njena moč je atrociously skrivnosten na prvi pogled.

131
00:07:36,860 --> 00:07:39,420
Ampak to je čudovito koristno, še posebej zdaj, ko smo na delu mandata

132
00:07:39,420 --> 00:07:43,080
če ste začeli uporabljati malloc in dinamično dodeljevanje pomnilnika.

133
00:07:43,080 --> 00:07:45,420
Stvari lahko gredo zelo zelo narobe hitro.

134
00:07:45,420 --> 00:07:49,320
Ker, če ste pozabili, da sprostite svoj spomin, ali pa dereference nekaj NULL kazalec,

135
00:07:49,320 --> 00:07:55,770
ali pa dereference nekaj smeti kazalec, kar je običajno znak, da so rezultati?

136
00:07:55,770 --> 00:07:59,470
SEG napake. In dobiš te glavne datoteke z nekaj več kilobajtov ali megabajtih

137
00:07:59,470 --> 00:08:02,990
, ki predstavlja stanje pomnilnika programa, ko je strmoglavilo,

138
00:08:02,990 --> 00:08:05,730
ampak vaš program na koncu seg napake, segmentacijo napako

139
00:08:05,730 --> 00:08:08,450
kar pomeni, da je nekaj slabega zgodilo skoraj vedno

140
00:08:08,450 --> 00:08:11,750
v spomin povezane napake, ki ste jih naredili nekje.

141
00:08:11,750 --> 00:08:14,100
Torej Valgrind pomaga najti stvari, kot je ta.

142
00:08:14,100 --> 00:08:17,720
To je orodje, ki ga vodijo, kot gdb, ko ste zbrati svoj program,

143
00:08:17,720 --> 00:08:20,330
ampak kot zaženete program za neposredno zaženete Valgrind

144
00:08:20,330 --> 00:08:23,960
in hodite za njim svoj program, tako kot ste storili z gdb.

145
00:08:23,960 --> 00:08:26,220
Zdaj, uporaba, da bi dobili najboljše vrste proizvodnje,

146
00:08:26,220 --> 00:08:30,410
je malo dolgo, tako da tam na vrhu strani zaslona boste videli Valgrind-V.

147
00:08:30,410 --> 00:08:35,350
"-V" skoraj povsod pomeni, verbose, ko boste uporabljali programe na Linux računalniku.

148
00:08:35,350 --> 00:08:38,770
Torej to pomeni, izpljuni več podatkov, kot si morda privzeto.

149
00:08:38,770 --> 00:08:45,510
"- Puščanja preverite = polna." To je samo rekel, prijave za vse možne spomin pušča,

150
00:08:45,510 --> 00:08:49,430
Napake, ki so morda sem naredila. Tudi to je pogost vzorec z Linux programov.

151
00:08:49,430 --> 00:08:52,710
Na splošno, če imate argument v ukazni vrstici, da je "stikalo",

152
00:08:52,710 --> 00:08:55,830
to naj bi spremenili programa ravnanja, in to je ena črka,

153
00:08:55,830 --> 00:09:00,310
to je, proti, če pa je vklopljen, samo z zasnovo programer,

154
00:09:00,310 --> 00:09:05,150
je celotno besedo ali zaporedje besed, je argument v ukazni vrstici se začne z -.

155
00:09:05,150 --> 00:09:08,190
To so le področja človekovih, pa boste videli vse.

156
00:09:08,190 --> 00:09:12,410
In potem, na koncu, "a.out" je poljubno ime za program v tem konkretnem primeru.

157
00:09:12,410 --> 00:09:14,640
In tukaj je nekaj predstavnik izhod.

158
00:09:14,640 --> 00:09:22,890
>> Preden pogledamo, kaj naj bi to pomenilo, naj grem več na odrezek kode tam.

159
00:09:22,890 --> 00:09:26,390
In mi umaknete s poti kmalu,

160
00:09:26,390 --> 00:09:32,120
in naj si na memory.c, ki je ta kratek primer tukaj.

161
00:09:32,120 --> 00:09:36,290
Torej, v tem programu, mi povečate naloge in vprašanja.

162
00:09:36,290 --> 00:09:39,430
Imamo funkcijo main, ki kliče funkcijo, f,

163
00:09:39,430 --> 00:09:45,590
in potem kaj storiti f nadaljuje v nekoliko strokovne angleščine?

164
00:09:45,590 --> 00:09:49,760
Kaj f nadaljuje narediti?

165
00:09:49,760 --> 00:09:53,680
Kaj pa bom začela z linijo 20 in zvezde lokacija ni pomembna,

166
00:09:53,680 --> 00:09:56,720
ampak bom samo biti v skladu z zadnjim predavanjem tukaj.

167
00:09:56,720 --> 00:09:59,910
Kaj je linija 20 pa za nas? Na levi strani zaslona. Bomo razčleniti naprej.

168
00:09:59,910 --> 00:10:02,410
Int * x: kaj to storiti?

169
00:10:02,410 --> 00:10:04,940
Ok. To razglasitvi kazalec, zdaj pa bodimo še bolj tehnične narave.

170
00:10:04,940 --> 00:10:10,230
Kaj to pomeni, zelo konkretno, naj razglasi kazalec? Nekdo drug?

171
00:10:10,230 --> 00:10:15,050
Ja? [Student odgovor, nerazumljiv] predolga.

172
00:10:15,050 --> 00:10:17,060
Torej berete na desni strani enačaja.

173
00:10:17,060 --> 00:10:20,290
Osredotočimo se le na levi strani, samo na int * x.

174
00:10:20,290 --> 00:10:24,700
To pomeni "razglasi" kazalec, ampak zdaj pa si se potopite globlje v to definicijo.

175
00:10:24,700 --> 00:10:28,330
Kaj to konkretno pomeni tehnično? Ja?

176
00:10:28,330 --> 00:10:31,940
[Student odgovor, nerazumljiv]

177
00:10:31,940 --> 00:10:35,090
Ok. To je priprava za shranjevanje naslov v pomnilniku.

178
00:10:35,090 --> 00:10:40,680
Dobro. In naj bo to en korak naprej, to je razglasitev spremenljivko x, ki je 32 bitov.

179
00:10:40,680 --> 00:10:44,440
In vem, da je 32 bitov, ker -?

180
00:10:44,440 --> 00:10:47,390
To ni zato, ker je int, ker je kazalec v tej zadevi.

181
00:10:47,390 --> 00:10:49,650
Naključje, da je to eno in isto s notr,

182
00:10:49,650 --> 00:10:51,970
vendar je dejstvo, da je zvezda pa pomeni, da je to kazalec

183
00:10:51,970 --> 00:10:57,300
in naprave, tako kot pri mnogih računalnikih, vendar ne vse, kazalci so 32 bitov.

184
00:10:57,300 --> 00:11:01,850
Na več moderno strojno opremo, kot so najnovejše Mac, najnovejši računalniki, morda imate 64-bitne kazalce,

185
00:11:01,850 --> 00:11:04,160
vendar v napravi, te stvari so 32 bitov.

186
00:11:04,160 --> 00:11:08,380
Torej bomo standardizirali na to. Bolj konkretno, zgodba gre takole:

187
00:11:08,380 --> 00:11:10,820
Mi "razglasi" kazalec, kaj to pomeni?

188
00:11:10,820 --> 00:11:12,810
Pripravljamo za shranjevanje naslov pomnilnika.

189
00:11:12,810 --> 00:11:15,530
Kaj to pomeni?

190
00:11:15,530 --> 00:11:19,810
Ustvarjamo spremenljivo imenom X, ki traja do 32 bitov

191
00:11:19,810 --> 00:11:23,810
da bo kmalu shranjevanje naslov celo število.

192
00:11:23,810 --> 00:11:26,470
In to je verjetno približno tako natančni, kot smo lahko dobili.

193
00:11:26,470 --> 00:11:31,810
Je že v redu napreduje poenostaviti svet, samo povem, razglasi kazalec imenovan x.

194
00:11:31,810 --> 00:11:35,380
Ugotovi kazalec, toda zavedati in razumeti, kaj se pravzaprav dogaja

195
00:11:35,380 --> 00:11:38,490
celo v samo tistih nekaj znakov.

196
00:11:38,490 --> 00:11:42,040
>> No, ta je skoraj malo lažje, čeprav je več izraz.

197
00:11:42,040 --> 00:11:48,160
Torej, kaj je to početje, ki je danes poudaril: "malloc (10 * sizeof (int));" Ja?

198
00:11:48,160 --> 00:11:52,350
[Student odgovor, nerazumljiv]

199
00:11:52,350 --> 00:11:58,250
Dobro. In ga bom odpeljal tja. To je razporejanju kos pomnilnika za 10 celih števil.

200
00:11:58,250 --> 00:12:02,190
In zdaj pa se potopite v nekoliko globlje, to je dodelitvijo kos pomnilnika za 10 števil.

201
00:12:02,190 --> 00:12:05,390
Kaj je malloc potem vrnil?

202
00:12:05,390 --> 00:12:10,390
Naslov tega kos, ali bolj konkretno, naslov prvega bajta te bloku.

203
00:12:10,390 --> 00:12:14,080
Kako potem sem jaz, programer, da vem, če je ta kos pomnilnika koncih?

204
00:12:14,080 --> 00:12:18,340
Vem, da je to stikata. Malloc, po definiciji, vam sosednje kos pomnilnika.

205
00:12:18,340 --> 00:12:21,240
Ni razlike v njej. Imate dostop do vseh bajt v tem bloku,

206
00:12:21,240 --> 00:12:26,760
back to back to back, ampak kako naj vem, kje je konec tega kos pomnilnika?

207
00:12:26,760 --> 00:12:28,850
Ko uporabljate malloc? [Student odgovor, nerazumljiv] Dobro.

208
00:12:28,850 --> 00:12:30,670
Saj ne. Moraš vedeti.

209
00:12:30,670 --> 00:12:35,960
Moram vedeti, da sem uporabil vrednost 10, in mi sploh ne zdi, da so to storili tukaj.

210
00:12:35,960 --> 00:12:41,000
Toda breme je v celoti na mene. Strlen, ki ste postali smo nekoliko odvisen od nizov,

211
00:12:41,000 --> 00:12:45,860
deluje samo zaradi tega dogovora, ki imajo \ 0

212
00:12:45,860 --> 00:12:48,840
ali ta posebni znak NUL, NUK, na koncu niza.

213
00:12:48,840 --> 00:12:51,740
To ne drži za samo samovoljno kose pomnilnika.

214
00:12:51,740 --> 00:12:58,590
To je odvisno od vas. Torej linije 20, nato pa namenja kos pomnilnika

215
00:12:58,590 --> 00:13:02,590
da lahko shranite 10 celih števil, in ga shrani naslov prvega bajta

216
00:13:02,590 --> 00:13:05,610
navedene kos pomnilnika v spremenljivko, imenovano x.

217
00:13:05,610 --> 00:13:11,140
Ergo, ki je kazalec. Torej linije 21, na žalost, je bila napaka.

218
00:13:11,140 --> 00:13:16,110
Ampak najprej, kaj počne? To je rekel trgovino na lokaciji, 10 indeksirajo 0,

219
00:13:16,110 --> 00:13:19,480
za kos pomnilnika, imenovano x vrednost 0.

220
00:13:19,480 --> 00:13:21,510
>> Torej, opazil nekaj stvari, ki se dogajajo.

221
00:13:21,510 --> 00:13:25,420
Čeprav je x kazalec odpokliče nekaj tednov nazaj

222
00:13:25,420 --> 00:13:29,440
da lahko še vedno uporabljate niz slogu zapis oglati oklepaj.

223
00:13:29,440 --> 00:13:36,180
Ker je to pravzaprav kratki roki zapis za bolj skrivnosten usmerjene aritmetične kazalec.

224
00:13:36,180 --> 00:13:40,320
če bi to naredili nekako takole: Vzemi naslov x, premaknite 10 mest več,

225
00:13:40,320 --> 00:13:44,550
potem pa je, da ne glede naslov je shranjena na tem mestu.

226
00:13:44,550 --> 00:13:48,090
Ampak odkrito povedano, to je samo za branje krute in se udobno.

227
00:13:48,090 --> 00:13:52,900
Tako svet običajno uporablja oglate oklepaje samo zato, ker je tako veliko bolj človeku prijazen brati.

228
00:13:52,900 --> 00:13:55,140
Ampak to je tisto, kar se v resnici dogaja pod pokrovom;

229
00:13:55,140 --> 00:13:58,190
x je naslov, ni matrika, sama po sebi.

230
00:13:58,190 --> 00:14:02,410
Torej, to je shranjevanje 0 na lokaciji v 10 x.

231
00:14:02,410 --> 00:14:06,120
Zakaj je to slabo? Ja?

232
00:14:06,120 --> 00:14:17,370
[Student odgovor, nerazumljiv] Točno tako.

233
00:14:17,370 --> 00:14:21,100
Mi samo dodeljenih 10 ints, vendar računamo od 0 pri programiranju v C,

234
00:14:21,100 --> 00:14:25,690
tako imate dostop do 0 1 2 3 4 5 6 7 8 9, ne pa 10.

235
00:14:25,690 --> 00:14:30,270
Torej, ali je program SEG bo kriv ali ni.

236
00:14:30,270 --> 00:14:32,900
Ampak res ne vem, to je neke vrste nondeterministic vedenja.

237
00:14:32,900 --> 00:14:35,600
Res je odvisno od tega, ali bomo imeli srečo.

238
00:14:35,600 --> 00:14:40,650
Če se izkaže, da operacijski sistem ne moti, če uporabim ta dodatni zlog,

239
00:14:40,650 --> 00:14:43,360
kljub temu, da ni dal meni, moj program morda ne bo sesul.

240
00:14:43,360 --> 00:14:46,780
To je surov, je Otroški voziček, vendar morda ne boste videli, da je simptom,

241
00:14:46,780 --> 00:14:48,960
ali bi lahko vidiš le enkrat v nekaj časa.

242
00:14:48,960 --> 00:14:51,230
Ampak dejstvo je, da je hrošč, v resnici obstaja.

243
00:14:51,230 --> 00:14:54,320
In to je res problematično, če ste napisali program, ki ga želite, da so pravilne,

244
00:14:54,320 --> 00:14:58,840
da ste prodali program, ki jih ljudje uporabljajo, da vsake toliko časa sesuje

245
00:14:58,840 --> 00:15:02,450
ker, seveda, to ni dobro. V bistvu, če imate telefon Android ali iPhone

246
00:15:02,450 --> 00:15:05,550
in si prenesete apps v teh dneh, če ste kdaj imeli app kar odnehati,

247
00:15:05,550 --> 00:15:10,040
kar naenkrat izgine, to je skoraj vedno posledica nekaterih spomin povezano vprašanje,

248
00:15:10,040 --> 00:15:12,830
pri čemer programer zamočil in dereferenced kazalec

249
00:15:12,830 --> 00:15:18,670
da je on ali ona ne sme imeti, in posledica iOS ali Android je samo ubil program v celoti

250
00:15:18,670 --> 00:15:23,080
namesto tveganja nedoločen vedenja ali nekakšen kompromis varnosti.

251
00:15:23,080 --> 00:15:25,950
>> Še ena napaka v tem programu, poleg tega.

252
00:15:25,950 --> 00:15:30,180
Kaj vse sem zamočil pri tem programu?

253
00:15:30,180 --> 00:15:32,740
Nisem vadili, kar sem pridigal. Ja?

254
00:15:32,740 --> 00:15:34,760
[Student odgovor, nerazumljiv] Dobro.

255
00:15:34,760 --> 00:15:36,880
Nisem osvobodili pomnilnik. Tako pravilo zdaj

256
00:15:36,880 --> 00:15:43,150
mora biti kadarkoli pokličete malloc, morate poklicati brezplačno, ko ste končali z uporabo te spomin.

257
00:15:43,150 --> 00:15:45,610
Zdaj, ko bi želel osvoboditi ta spomin?

258
00:15:45,610 --> 00:15:49,780
Verjetno, ob predpostavki, da je to prva vrstica je bila pravilna, bi rad, da to storite tukaj.

259
00:15:49,780 --> 00:15:55,710
Ker nisem mogla, na primer, to storite tukaj. Zakaj?

260
00:15:55,710 --> 00:15:57,860
Samo zunaj obsega. Torej, čeprav govorimo o kazalci,

261
00:15:57,860 --> 00:16:04,830
To je teden, 2 ali 3 izdaje, kjer je x le v obsegu od znotraj zavitih oklepajih, kjer je navedeno, da.

262
00:16:04,830 --> 00:16:11,000
Torej, zagotovo ne more osvoboditi tam. Moja edina možnost, da se sprostite, je približno po liniji 21.

263
00:16:11,000 --> 00:16:15,170
To je dokaj preprost program, bilo je precej enostavno, ko si nekako zaviti vaš um

264
00:16:15,170 --> 00:16:17,870
okoli kaj počne program, kjer so bile napake.

265
00:16:17,870 --> 00:16:20,500
In tudi če ga niste videli na prvi, upam, da je to malo očitno zdaj

266
00:16:20,500 --> 00:16:23,870
da se te napake zelo enostavno rešiti in enostavno je.

267
00:16:23,870 --> 00:16:28,720
Toda, ko je program več kot 12 vrstic, to je 50 vrstic, 100 vrstic,

268
00:16:28,720 --> 00:16:31,150
hoja skozi kodo po vrsticah, misleč, da s tem logično,

269
00:16:31,150 --> 00:16:35,110
je možno, vendar ni posebno zabavno delati, nenehno iščejo napake,

270
00:16:35,110 --> 00:16:38,340
in to je tudi težko narediti, in da je, zakaj orodje, kot Valgrind obstaja.

271
00:16:38,340 --> 00:16:40,900
Naj gredo naprej in to je to: Naj odprem okno terminala,

272
00:16:40,900 --> 00:16:45,400
in mi ne zaženete, le spomin, ker je pomnilnik zdi, da je v redu.

273
00:16:45,400 --> 00:16:49,180
Grem srečo. Going to dodatno bajt na koncu matrike

274
00:16:49,180 --> 00:16:51,060
ne zdi preveč težavno.

275
00:16:51,060 --> 00:16:56,370
Vendar mi dovolite, kljub temu narediti pregled duševnega zdravja, kar pomeni samo, da preveri

276
00:16:56,370 --> 00:16:58,320
ali je to dejansko pravilna.

277
00:16:58,320 --> 00:17:04,690
>> Torej, kaj je naredil valgrind-V - puščanja preverite = celoti,

278
00:17:04,690 --> 00:17:07,520
in nato ime programa v tem primeru je spomin, ne a.out.

279
00:17:07,520 --> 00:17:10,760
Torej, naj gredo naprej in to je to. Pritisnite tipko Enter.

280
00:17:10,760 --> 00:17:14,109
Dragi Bog. To je njena proizvodnja, in to je tisto, kar sem že prej omenili.

281
00:17:14,109 --> 00:17:17,550
Ampak, če boste izvedeli, da se glasi skozi vse neumnosti tukaj,

282
00:17:17,550 --> 00:17:20,760
večina je to samo diagnostični izhod, da to ni tako zanimivo.

283
00:17:20,760 --> 00:17:24,829
Kaj vaše oči resnično želi, da se iščejo, je vsaka omemba napake ali neveljavna.

284
00:17:24,829 --> 00:17:26,800
Besede, ki kažejo na težave.

285
00:17:26,800 --> 00:17:29,340
In res, da vidimo, kaj je narobe tukaj.

286
00:17:29,340 --> 00:17:35,230
Imam povzetek neke vrste ", ki se uporablja v izhodu:. 40 bajti v blokih 1"

287
00:17:35,230 --> 00:17:38,750
Nisem ravno prepričan, kaj blok je še, ampak 40 bytes

288
00:17:38,750 --> 00:17:41,260
dejansko počuti, kot sem lahko, da ugotovimo, kje prihaja.

289
00:17:41,260 --> 00:17:45,030
40 bajtov. Zakaj je 40 bajtov uporabo na izhodu?

290
00:17:45,030 --> 00:17:48,780
In še posebej, če se pomaknite dol,

291
00:17:48,780 --> 00:17:54,520
Zato sem se dokončno izgubil 40 zlogi? Ja?

292
00:17:54,520 --> 00:17:59,520
[Student odgovor, nerazumljiv] Perfect. Ja, točno tako.

293
00:17:59,520 --> 00:18:03,540
Bilo je 10 cela števila, in vsak od njih je velikost 4 ali 32 bitov,

294
00:18:03,540 --> 00:18:08,300
Tako sem izgubil natanko 40 bajte, ker, kot ste predlagali, nisem se imenuje brezplačno.

295
00:18:08,300 --> 00:18:13,460
To je ena napaka, sedaj pa si poglejmo še malo dol in videli, poleg tega,

296
00:18:13,460 --> 00:18:16,900
"Neveljavno napišite velikosti 4". Zdaj, kaj je to?

297
00:18:16,900 --> 00:18:21,150
Ta naslov se izraža izhodiščno zapis, očitno?

298
00:18:21,150 --> 00:18:23,640
To je šestnajstiški in kadarkoli vidite število začne z 0x,

299
00:18:23,640 --> 00:18:29,410
to pomeni, šestnajstiški, ki smo davnega leta, mislim, da je oddelek pset 0 vprašanj,

300
00:18:29,410 --> 00:18:34,090
, ki je bila le, da to warmup izvajanje, spreminjanje decimalno za hex za dvokomponentne in tako naprej.

301
00:18:34,090 --> 00:18:39,220
Šestnajstiški, samo zaradi človeške konvencije, se običajno uporablja za predstavitev kazalcev

302
00:18:39,220 --> 00:18:41,570
ali, bolj splošno, obravnava. To je samo dogovor,

303
00:18:41,570 --> 00:18:45,340
ker je malo lažje brati, da je malo bolj kompakten kot nekaj podobnega decimalko,

304
00:18:45,340 --> 00:18:47,720
binarni in je neuporabna za večino ljudi za uporabo.

305
00:18:47,720 --> 00:18:50,840
Torej, kaj zdaj to pomeni? No, izgleda, kot da je neveljavna pisanje

306
00:18:50,840 --> 00:18:54,480
velikosti 4 on line 21 memory.c.

307
00:18:54,480 --> 00:18:59,180
Torej pojdimo nazaj na liniji 21 in seveda v tem, da neveljavni pisanje.

308
00:18:59,180 --> 00:19:02,640
Torej Valgrind ne bo popolnoma držal za roko in mi povej, kaj popraviti, je,

309
00:19:02,640 --> 00:19:05,520
vendar je odkrivanje, da delam neveljaven zapis.

310
00:19:05,520 --> 00:19:08,800
Jaz sem se dotika 4 bajte, da ne smem biti, in očitno je to zato, ker

311
00:19:08,800 --> 00:19:13,960
kot ste poudarili, da delam [10] namesto [9] maksimalno

312
00:19:13,960 --> 00:19:16,660
ali [0] ali nekaj vmes.

313
00:19:16,660 --> 00:19:19,690
Z Valgrind, spoznali koli ste zdaj pisanje programa

314
00:19:19,690 --> 00:19:24,190
ki uporablja napotke in uporablja pomnilnik, in malloc natančneje,

315
00:19:24,190 --> 00:19:27,080
zagotovo dobili v navado teče tako dolgo

316
00:19:27,080 --> 00:19:30,890
vendar zelo preprosto kopirate in prilepite ukaz Valgrind

317
00:19:30,890 --> 00:19:32,650
da vidim, če obstaja nekaj napak notri.

318
00:19:32,650 --> 00:19:34,820
In to bo velika vsakič, ko vidiš izhoda,

319
00:19:34,820 --> 00:19:39,430
ampak razčleniti skozi vizualno vse učinke, in videli, če boste videli omenja napak

320
00:19:39,430 --> 00:19:43,190
ali opozorila ali neveljavno ali izgubljen.

321
00:19:43,190 --> 00:19:46,200
Vse besede, ki zveni kot ste zajebali nekje.

322
00:19:46,200 --> 00:19:48,580
Torej zavedaš, da je novo orodje v vašem orodij.

323
00:19:48,580 --> 00:19:51,270
>> Zdaj v ponedeljek smo imeli cel kup ljudje pridejo sem gor

324
00:19:51,270 --> 00:19:53,150
in predstavlja pojem povezan seznam.

325
00:19:53,150 --> 00:20:00,970
In smo uvedli povezan seznam kot rešitev za problem, kaj?

326
00:20:00,970 --> 00:20:04,590
Ja? [Student odgovor, nerazumljiv] Dobro.

327
00:20:04,590 --> 00:20:06,530
Polja ne more imeti spomin jim dodane.

328
00:20:06,530 --> 00:20:09,440
Če dodelijo paleto velikosti 10, to je vse, kar dobiš.

329
00:20:09,440 --> 00:20:13,690
Lahko pokličete funkcijo kot realloc, če jo na začetku poimenovali malloc,

330
00:20:13,690 --> 00:20:17,580
in da se lahko poskusite rastejo niz, če je prostor proti koncu tega

331
00:20:17,580 --> 00:20:21,610
da nihče drug ne uporablja, in če ne, bo to samo poiskati večji kos nekje drugje.

332
00:20:21,610 --> 00:20:25,040
Ampak potem se bo kopiranje vseh teh bajtov v novo polje.

333
00:20:25,040 --> 00:20:28,310
To zveni kot zelo pravilna rešitev.

334
00:20:28,310 --> 00:20:34,790
Zakaj je to neprivlačno?

335
00:20:34,790 --> 00:20:36,940
Mislim, da deluje, ljudje so rešili ta problem.

336
00:20:36,940 --> 00:20:40,710
Zakaj ga moramo rešiti v ponedeljek, povezanih s seznamov? Ja?

337
00:20:40,710 --> 00:20:44,060
[Student odgovor, nerazumljiv] To lahko traja dolgo časa.

338
00:20:44,060 --> 00:20:49,260
V bistvu, vsakič, ko kličeš malloc ali realloc ali calloc, kar je še ena,

339
00:20:49,260 --> 00:20:52,470
vsakič, ko je program, v pogovoru z operacijskim sistemom,

340
00:20:52,470 --> 00:20:54,310
ste nagnjeni k upočasni programa navzdol.

341
00:20:54,310 --> 00:20:57,470
In če delaš te vrste stvari zank, ste res upočasnjuje stvari navzdol.

342
00:20:57,470 --> 00:21:00,740
Ne boš opazil tole najenostavnejši "Hello World" tipa programov,

343
00:21:00,740 --> 00:21:04,300
vendar v veliko večjih programov, ki prosi za operacijski sistem znova in znova, za spomin

344
00:21:04,300 --> 00:21:07,520
ali daje znova in znova kaže, da ni dobra stvar.

345
00:21:07,520 --> 00:21:11,210
Plus, to je nekako intelektualno - to je popolna izguba časa.

346
00:21:11,210 --> 00:21:16,490
Zakaj dodeli več in več pomnilnika, tveganje kopiranje vse v novo polje,

347
00:21:16,490 --> 00:21:21,980
Če imate možnost, ki vam omogoča, da dodeli le toliko pomnilnika, kot ga dejansko potrebujejo?

348
00:21:21,980 --> 00:21:24,130
Torej je v pluse in minuse tukaj.

349
00:21:24,130 --> 00:21:26,730
Eden od pluse zdaj, je, da imamo dinamiko.

350
00:21:26,730 --> 00:21:29,100
Ni važno, če so kosi spomin so, da so svobodne,

351
00:21:29,100 --> 00:21:32,070
Lahko samo nekako ustvarili te krušnih drobtin prek kazalcev

352
00:21:32,070 --> 00:21:34,470
za niz ves moj povezani seznam skupaj.

353
00:21:34,470 --> 00:21:36,470
Ampak plačam vsaj eno ceno.

354
00:21:36,470 --> 00:21:40,060
>> Kaj moram storiti, da bi se pri pridobivanju povezane sezname?

355
00:21:40,060 --> 00:21:42,470
Ja? [Student odgovor, nerazumljiv] Dobro.

356
00:21:42,470 --> 00:21:45,650
Če potrebujete več pomnilnika. Zdaj rabim prostor za te napotke,

357
00:21:45,650 --> 00:21:47,900
in v primeru te super navadno povezan seznam

358
00:21:47,900 --> 00:21:51,410
da je le poskušal shraniti celih, ki so 4 bajte, da ponavljate

359
00:21:51,410 --> 00:21:54,240
No, kazalec je 4 bajte, tako da zdaj sem dobesedno podvojilo

360
00:21:54,240 --> 00:21:57,290
količino pomnilnika, rabim samo za shranjevanje ta seznam.

361
00:21:57,290 --> 00:21:59,680
Ampak spet, to je stalna kompromis v računalništvu

362
00:21:59,680 --> 00:22:03,440
med časom in prostorom in razvoj, trud in drugih virov.

363
00:22:03,440 --> 00:22:06,630
Kaj je druga negativna uporabo povezani seznam? Ja?

364
00:22:06,630 --> 00:22:10,150
[Student odgovor, nerazumljiv]

365
00:22:10,150 --> 00:22:12,600
Dobro. Ni tako enostavno dostopna. Mi ne more več vzvoda

366
00:22:12,600 --> 00:22:15,530
teden 0 načela, kot so deli in vladaj.

367
00:22:15,530 --> 00:22:18,220
In še posebej, binarno iskanje. Ker čeprav smo ljudje

368
00:22:18,220 --> 00:22:20,400
grobo videti, kje je sredi tega seznama je

369
00:22:20,400 --> 00:22:25,840
računalnik ve, da je to povezano Seznam se začne na naslovu imenovani prvi.

370
00:22:25,840 --> 00:22:28,250
In to je 0x123 ali kaj podobnega.

371
00:22:28,250 --> 00:22:30,990
In edini način, da se program je bil srednji element

372
00:22:30,990 --> 00:22:33,350
je pravzaprav iskanje celoten seznam.

373
00:22:33,350 --> 00:22:35,500
In tudi takrat, dobesedno mora poiskati celoten seznam, ker

374
00:22:35,500 --> 00:22:38,950
Niti enkrat pridete v srednji element z upoštevanjem nasvetov,

375
00:22:38,950 --> 00:22:42,380
ti, program, ne vem, kako dolgo ta seznam, potencialno

376
00:22:42,380 --> 00:22:45,250
dokler si udaril konec njej, in kako veš programsko

377
00:22:45,250 --> 00:22:48,600
da si na koncu povezan seznam?

378
00:22:48,600 --> 00:22:51,120
Obstaja posebna NULL kazalec, tako da spet konvencije.

379
00:22:51,120 --> 00:22:53,870
Namesto tega uporabite kazalec, da zagotovo ne želite, da bi bilo nekaj smeti vrednost

380
00:22:53,870 --> 00:22:57,750
kaže odra nekje, želimo, da bi bilo z roko navzdol, NULL,

381
00:22:57,750 --> 00:23:01,530
tako da imamo to postajo v tej strukturo podatkov, da vemo, kje se konča.

382
00:23:01,530 --> 00:23:03,410
>> Kaj pa, če želimo, da manipulira to?

383
00:23:03,410 --> 00:23:05,980
Naredili smo večino tega vizualno in z ljudmi,

384
00:23:05,980 --> 00:23:07,630
kaj pa, če želimo narediti vstavljanje?

385
00:23:07,630 --> 00:23:12,360
Tako je bil prvotni seznam 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Kaj, če bi potem želel prostora malloc za številko 55, vozlišča za to,

387
00:23:16,730 --> 00:23:20,730
in potem želimo vstaviti na seznam 55 tako kot smo storili v ponedeljek?

388
00:23:20,730 --> 00:23:23,690
Kako to storiti? No, Anita prišel gor in je v bistvu hodil seznam.

389
00:23:23,690 --> 00:23:27,500
Začela je pri prvem elementu, nato pa je naslednji, naslednji, naslednji, naslednji, naslednji.

390
00:23:27,500 --> 00:23:29,500
Končno je zadel na levi strani vse do konca

391
00:23:29,500 --> 00:23:34,480
in ugotovil, oh, to je NULL. Torej, kaj je kazalec manipulacijo je treba storiti?

392
00:23:34,480 --> 00:23:37,980
Oseba, ki je bil na koncu, številka 34, je potrebno njegovo levo roko dvigne

393
00:23:37,980 --> 00:23:46,220
točko na 55, 55 potrebna svojo levo roko obrnjeno navzdol, da je novi terminator NULL. Končano.

394
00:23:46,220 --> 00:23:49,540
Precej enostavno vstavljanje 55 v seznamu razvrščeni.

395
00:23:49,540 --> 00:23:51,800
In kako bi to izgledalo?

396
00:23:51,800 --> 00:23:55,690
>> Naj gredo naprej in odprla nekaj kode primer tukaj.

397
00:23:55,690 --> 00:23:58,120
Jaz bom odprl gedit, in mi odprla dve datoteki prvi.

398
00:23:58,120 --> 00:24:02,050
Eden od njih je list1.h, in dovolite mi, spomnil, da je bil to kos kode

399
00:24:02,050 --> 00:24:04,920
ki smo jo uporabili, da predstavlja vozlišče.

400
00:24:04,920 --> 00:24:13,040
Vozlišče ima tako imenovano int n in kazalec se imenuje naslednji, ki le opozarja na naslednje stvari na seznamu.

401
00:24:13,040 --> 00:24:15,450
To je zdaj v datoteko. H. Zakaj?

402
00:24:15,450 --> 00:24:19,090
Tam je ta konvencija, in nismo izkoristili te ogromne količine sami,

403
00:24:19,090 --> 00:24:22,220
ampak oseba, ki je napisal printf in druge naloge

404
00:24:22,220 --> 00:24:27,150
je kot darilo na svetu vseh teh funkcij, s pisanjem datoteko z imenom stdio.h.

405
00:24:27,150 --> 00:24:30,950
In potem je tukaj še string.h, in potem je tukaj še map.h, in tam je vse te datoteke h

406
00:24:30,950 --> 00:24:34,410
da ste morda videli ali se uporabljajo v času pisnega drugih ljudi.

407
00:24:34,410 --> 00:24:38,470
Običajno pri njih. H datoteke so samo stvari, kot typedefs

408
00:24:38,470 --> 00:24:42,310
ali izjave po meri, vrste ali izjav konstant.

409
00:24:42,310 --> 00:24:47,890
Vi ne dajo funkcijo "izvedb v glavi datoteke.

410
00:24:47,890 --> 00:24:50,570
Ti pa, namesto, le svoje prototipe.

411
00:24:50,570 --> 00:24:53,050
Si dal stvari, ki jih želite deliti s svetom, kar potrebujejo

412
00:24:53,050 --> 00:24:55,640
da se pripravijo svojo kodo. Torej, samo priti v to navado,

413
00:24:55,640 --> 00:24:59,110
smo se odločili, da storijo enako stvar. Ni veliko list1.h,

414
00:24:59,110 --> 00:25:02,070
pa smo pripravili nekaj, kar bi lahko v interesu ljudi v svetu

415
00:25:02,070 --> 00:25:05,030
ki želijo uporabljati svoj povezano izvajanje seznam.

416
00:25:05,030 --> 00:25:08,040
Zdaj, v list1.c, ne bo šel skozi vso to stvar

417
00:25:08,040 --> 00:25:11,390
ker je nekoliko predolg, je ta program, vendar naj vodijo to resnično hitro na poziv.

418
00:25:11,390 --> 00:25:15,720
Naj pripravijo List1, dovolite mi, torej prost List1, in kar boste videli se

419
00:25:15,720 --> 00:25:18,070
Mi smo simulirano preprost program za malo tukaj

420
00:25:18,070 --> 00:25:20,990
da se dogaja, da mi dovolite, da dodate in odstranite številke na seznamu.

421
00:25:20,990 --> 00:25:24,310
Torej, naj gredo naprej in tip 3 za 3 menija.

422
00:25:24,310 --> 00:25:27,880
Želim vstavite številko - naredimo prva številka, ki je bila 9,

423
00:25:27,880 --> 00:25:30,550
in zdaj sem povedal, je seznam zdaj 9.

424
00:25:30,550 --> 00:25:33,760
Naj gredo naprej in eno vstavljanje, tako da sem zadel menija 3.

425
00:25:33,760 --> 00:25:36,760
Kaj več ne želim vstaviti? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. In jaz bom samo še eno.

427
00:25:39,220 --> 00:25:41,720
Naj vstavite številko 22.

428
00:25:41,720 --> 00:25:45,850
Torej imamo začetke povezan seznam, ki smo jih imeli v obliki diapozitiva pred nekaj trenutki.

429
00:25:45,850 --> 00:25:48,740
Kako se to dejansko dogaja vstavljanje?

430
00:25:48,740 --> 00:25:52,000
Seveda, 22 je zdaj na koncu seznama.

431
00:25:52,000 --> 00:25:55,050
Torej zgodbe nam povedali na odru v ponedeljek in recapped pravkar

432
00:25:55,050 --> 00:25:57,460
treba dejansko dogaja v kodi.

433
00:25:57,460 --> 00:25:59,700
Oglejmo si. Dovolite mi, da se pomaknete navzdol v tej datoteki.

434
00:25:59,700 --> 00:26:01,720
Mi bomo zatajili nekatere funkcije,

435
00:26:01,720 --> 00:26:05,630
ampak bomo šli dol na, recimo, vstaviti funkcijo.

436
00:26:05,630 --> 00:26:11,720
>> Poglejmo, kako bomo šli o vstavljanju novo vozlišče v tem povezan seznam.

437
00:26:11,720 --> 00:26:14,550
Če je seznam prijavljena? No, pa se pomaknite vso pot navzgor na vrhu,

438
00:26:14,550 --> 00:26:19,970
in opazil, da je moj povezani seznam bistvu je deklariran kot en sam kazalec, ki je sprva NULL.

439
00:26:19,970 --> 00:26:23,180
Torej, jaz sem z globalno spremenljivko tukaj, ki na splošno smo pridigal proti

440
00:26:23,180 --> 00:26:25,280
ker je tako kodo malo grdo, da ohranjajo,

441
00:26:25,280 --> 00:26:29,080
to je nekako leni, običajno, ampak ne leni in ni narobe in to ni slabo

442
00:26:29,080 --> 00:26:33,660
Če je vaš program je edini cilj v življenju je, da simulira eno povezano seznam.

443
00:26:33,660 --> 00:26:35,460
Kar je točno to, kar delamo.

444
00:26:35,460 --> 00:26:39,100
Torej, namesto navesti v glavni nato pa so ga posredovati v vsaki funkciji

445
00:26:39,100 --> 00:26:42,640
smo napisana v tem programu, smo namesto tega zavedaš, oh, kaj je samo, da je svetovna

446
00:26:42,640 --> 00:26:47,060
ker je glavni namen tega programa je pokazati eno in samo eno povezani seznam.

447
00:26:47,060 --> 00:26:50,700
Tako, da se počuti v redu. Tukaj so moji prototipi, in ne bomo šli skozi vse to,

448
00:26:50,700 --> 00:26:55,800
vendar sem napisal funkcijo za brisanje, je najti funkcijo, je vstaviti funkcijo in funkcijo premikanja.

449
00:26:55,800 --> 00:26:59,080
Ampak kaj je zdaj šel nazaj na vstaviti funkcijo

450
00:26:59,080 --> 00:27:01,490
in videli, kako se dela tukaj.

451
00:27:01,490 --> 00:27:09,940
Vstavi se na spletu - gremo.

452
00:27:09,940 --> 00:27:12,850
Vstavi. Torej, da ne bo nobenih argumentov, ker bomo to ask

453
00:27:12,850 --> 00:27:15,930
uporabnik znotraj te funkcije za številko, ki jih želite vstaviti.

454
00:27:15,930 --> 00:27:19,410
Ampak najprej moramo pripraviti, da jim nekaj prostora.

455
00:27:19,410 --> 00:27:22,050
To je neke vrste kopiraj in prilepi iz drugega npr.

456
00:27:22,050 --> 00:27:25,110
V tem primeru smo dodeljevanja int, tokrat bomo dodelitvi vozlišče.

457
00:27:25,110 --> 00:27:27,910
Ne spomnim se, koliko bajtov vozlišče je, ampak to je v redu.

458
00:27:27,910 --> 00:27:30,460
Sizeof lahko ugotovimo, da je zame.

459
00:27:30,460 --> 00:27:33,340
In zakaj sem iskal v skladu NULL 120?

460
00:27:33,340 --> 00:27:37,530
Kaj bi lahko šlo narobe v skladu 119? Ja?

461
00:27:37,530 --> 00:27:40,530
[Student odgovor, nerazumljiv]

462
00:27:40,530 --> 00:27:43,440
Dobro. Tako bi se lahko zgodilo, da sem prosila za preveč pomnilnika

463
00:27:43,440 --> 00:27:47,020
ali je nekaj narobe, in operacijski sistem nima dovolj bajte, da bi me dali,

464
00:27:47,020 --> 00:27:50,640
tako da kaže, kolikor ga vrne NULL, in če ne bom preveriti, da

465
00:27:50,640 --> 00:27:54,710
in sem slepo nadaljuje z uporabo naslov vrnil, bi bilo NULL.

466
00:27:54,710 --> 00:27:58,400
Lahko bi bilo nekaj neznanega vrednost, ni dobro, če ne -

467
00:27:58,400 --> 00:28:00,590
dejansko ne bo neznano vrednost. To je lahko NULL, zato ne želim,

468
00:28:00,590 --> 00:28:02,550
da ga zlorabljajo in tveganja, ki ga Dereferenciranje.

469
00:28:02,550 --> 00:28:07,410
Če se to zgodi, sem vrnil in pretvarjali se bomo, tako kot nisem dobil nazaj vsako spomin na vse.

470
00:28:07,410 --> 00:28:12,270
>> Sicer pa vem, da si mi nekaj, da vstavite kličem, naš stari prijatelj GetInt,

471
00:28:12,270 --> 00:28:15,530
in potem je bila to nova skladnja smo predstavili v ponedeljek.

472
00:28:15,530 --> 00:28:20,320
"Newptr-> n 'pomeni imeti naslov, ki ste bili, ki jo knjižnične funkcije malloc

473
00:28:20,320 --> 00:28:23,490
ki predstavlja prvi bajt nov objekt vozlišča,

474
00:28:23,490 --> 00:28:26,860
nato pa pojdite na polje, imenovano n.

475
00:28:26,860 --> 00:28:35,270
Malo trivia vprašanje: To je enako, v kakšnem bolj Grobni vrstico kode?

476
00:28:35,270 --> 00:28:38,110
Kako bi drugače sem napisal to? Želite, da bi zabodel?

477
00:28:38,110 --> 00:28:41,480
[Student odgovor, nerazumljiv]

478
00:28:41,480 --> 00:28:44,870
Dobro. Uporaba n., Vendar to ni tako preprosto, kot je ta.

479
00:28:44,870 --> 00:28:47,090
Kaj morali najprej narediti? [Student odgovor, nerazumljiv]

480
00:28:47,090 --> 00:28:52,730
Dobro. Moram narediti * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Torej, to je rekel nov kazalec, je očitno naslov. Zakaj?

482
00:28:55,610 --> 00:28:59,520
Ker se je vrnila knjižnične funkcije malloc. Znak * newptr rekel "pojdi tja"

483
00:28:59,520 --> 00:29:02,970
in potem, ko si tam, potem lahko uporabite bolje pozna. n,

484
00:29:02,970 --> 00:29:05,730
vendar je to samo izgleda malce grdo, še posebej, če smo ljudje bodo

485
00:29:05,730 --> 00:29:10,360
pripravi nasvetov s puščicami ves čas, svet je standardiziran na tem arrow zapisu

486
00:29:10,360 --> 00:29:12,320
ki ima natanko isto stvar.

487
00:29:12,320 --> 00:29:16,070
Torej, uporabite le -> zapis, ko je stvar na levi strani je kazalec.

488
00:29:16,070 --> 00:29:18,790
Sicer pa, če je to dejansko struct uporabite. N.

489
00:29:18,790 --> 00:29:25,800
In potem je to: Zakaj se zažene newptr-> naslednji na NULL?

490
00:29:25,800 --> 00:29:28,610
Ne želimo, da binglja levo roko off na koncu stopnje.

491
00:29:28,610 --> 00:29:31,630
Želimo, da usmerjena naravnost navzdol, kar pomeni konec tega seznama

492
00:29:31,630 --> 00:29:34,980
bi lahko bilo v tem vozlišču, zato smo se raje prepričajte, da je NULL.

493
00:29:34,980 --> 00:29:38,460
In na splošno inicializacijo spremenljivk ali vaše podatkovne članov in konstrukti

494
00:29:38,460 --> 00:29:40,470
za nekaj, kar je le dobra praksa.

495
00:29:40,470 --> 00:29:45,170
Samo da smeti obstajajo in še naprej obstajati tudi ti zaide v težave

496
00:29:45,170 --> 00:29:48,650
če ste pozabili, da narediš nekaj kasneje.

497
00:29:48,650 --> 00:29:51,590
>> Tukaj je nekaj primerov. To pa ponovno je vstaviti funkcijo,

498
00:29:51,590 --> 00:29:54,930
in prva stvar, ki sem preveriti, če je spremenljivka imenovan prvi,

499
00:29:54,930 --> 00:29:58,240
da je globalna spremenljivka je NULL, kar pomeni, da ni povezan seznam.

500
00:29:58,240 --> 00:30:02,460
Nismo vstavi vse številke, tako da je nepomembno, da vstavite to trenutno število

501
00:30:02,460 --> 00:30:05,240
na seznam, ker samo sodi na začetku seznama.

502
00:30:05,240 --> 00:30:08,100
Torej, to je bilo, ko Anita sem samo stal tu sam pretvarja

503
00:30:08,100 --> 00:30:11,390
nihče drug je bil tu gor na oder, dokler ne bomo namenili vozlišče,

504
00:30:11,390 --> 00:30:13,940
potem bi ona dvignila roko, prvič,

505
00:30:13,940 --> 00:30:17,420
če bi vsi ostali prišli na oder za njo v ponedeljek.

506
00:30:17,420 --> 00:30:22,900
Zdaj je tu, to je malo pregled, kjer moram reči, če je novo vozlišče je vrednost n

507
00:30:22,900 --> 00:30:27,370
je <vrednost n v sedanji prvega vozla,

508
00:30:27,370 --> 00:30:29,930
to pomeni, da je povezani seznam, ki je začela.

509
00:30:29,930 --> 00:30:32,330
Tam je vsaj en vozel v seznamu, vendar je ta novi tip

510
00:30:32,330 --> 00:30:37,230
Spada pred, zato moramo premakniti stvari na bolje.

511
00:30:37,230 --> 00:30:43,450
Z drugimi besedami, če je seznam začelo s preprosto, recimo,

512
00:30:43,450 --> 00:30:48,100
samo številka 17, ki je - pravzaprav, lahko to bolj jasno.

513
00:30:48,100 --> 00:30:56,010
Če začnemo našo zgodbo s kazalcem tu imenuje prvi,

514
00:30:56,010 --> 00:30:59,870
in na začetku je NULL, in smo vstavite številko 9,

515
00:30:59,870 --> 00:31:02,510
številka 9, očitno pripada na začetku seznama.

516
00:31:02,510 --> 00:31:07,400
Torej, kaj je pretvarjal smo samo malloced naslov ali številko 9 in ga tukaj.

517
00:31:07,400 --> 00:31:13,170
Če Prvi je 9 privzeto, prvi scenarij smo se pogovarjali samo pomeni točko, dajmo ta tip tukaj,

518
00:31:13,170 --> 00:31:15,790
pustite, da je to NULL, zdaj imamo številko 9.

519
00:31:15,790 --> 00:31:18,280
Naslednja številka želimo vstaviti je 17.

520
00:31:18,280 --> 00:31:22,420
17 spada sem, da bomo morali narediti nekaj logičnih korakih skozi to.

521
00:31:22,420 --> 00:31:26,060
Torej, namesto, preden bomo to storili, dajmo se pretvarjamo, da smo želeli vstaviti številko 8.

522
00:31:26,060 --> 00:31:28,650
>> Torej samo zaradi priročnosti je, da bom tu izvlekli.

523
00:31:28,650 --> 00:31:30,760
Ampak zapomni si, lahko malloc dal najbolj kjerkoli.

524
00:31:30,760 --> 00:31:33,460
Ampak za božjo risba je, ga bom dal sem.

525
00:31:33,460 --> 00:31:38,440
Tako se pretvarjamo, da sem pravkar dodeljen vozlišče za številko 8, kar je NULL privzeto.

526
00:31:38,440 --> 00:31:42,800
Kaj je zdaj zgodilo? Nekaj ​​stvari.

527
00:31:42,800 --> 00:31:47,090
Naredili smo to napako na odru v ponedeljek, ko smo posodobili kazalec, kot je ta,

528
00:31:47,090 --> 00:31:51,890
potem je to storil, nato pa smo trdili - smo vsi ostali brez staršev na odru.

529
00:31:51,890 --> 00:31:54,350
Ker si moreš - vrstni red operacij tu je pomembno,

530
00:31:54,350 --> 00:31:58,760
ker zdaj smo izgubili to vozlišče 9, ki je nekako lebdi v prostoru.

531
00:31:58,760 --> 00:32:01,150
Torej to ni pravi pristop v ponedeljek.

532
00:32:01,150 --> 00:32:03,330
Najprej smo morali narediti nekaj drugega.

533
00:32:03,330 --> 00:32:06,280
Stanje na svetu videti takole. Sprva je bil dodeljen 8.

534
00:32:06,280 --> 00:32:10,550
Kaj bi lahko bil boljši način za vstavljanje 8?

535
00:32:10,550 --> 00:32:14,720
Namesto posodabljanje tega kazalca prvič, samo posodobite tole tukaj namesto tega.

536
00:32:14,720 --> 00:32:17,720
Zato moramo vrstico kode, ki se dogaja, da želite to NULL značaja

537
00:32:17,720 --> 00:32:22,020
v dejanski kazalec, ki je obrnjena na vozlišču 9,

538
00:32:22,020 --> 00:32:27,970
in potem bomo lahko varno spremeniti najprej opozoriti na ta tip tukaj.

539
00:32:27,970 --> 00:32:31,330
Zdaj imamo seznam, povezani seznam, dveh elementov.

540
00:32:31,330 --> 00:32:33,580
In kaj to dejansko videti tukaj?

541
00:32:33,580 --> 00:32:36,900
Če pogledamo kodo, opazil, da sem storil prav to.

542
00:32:36,900 --> 00:32:41,970
Rekel sem newptr, in v tej zgodbi, newptr je kazal tega tipa.

543
00:32:41,970 --> 00:32:45,520
>> Torej, naj pripravi še eno stvar, in jaz bi pustil malo več prostora za to.

544
00:32:45,520 --> 00:32:48,540
Torej, odpusti mali risbo.

545
00:32:48,540 --> 00:32:52,140
Ta tip se imenuje newptr.

546
00:32:52,140 --> 00:32:57,940
To je spremenljivka smo objavili nekaj vrstic prej, v skladu - malo nad 25 let.

547
00:32:57,940 --> 00:33:03,430
In to je obrnjena na 8. Torej, ko rečem newptr-> naslednji, kar pomeni, da gre za struct

548
00:33:03,430 --> 00:33:07,910
da se je opozoril na po newptr, zato pa smo tukaj, pojdi tja.

549
00:33:07,910 --> 00:33:13,990
Potem je rekel arrow dobili naslednje polje in nato = pravi dal kakšno vrednost tam?

550
00:33:13,990 --> 00:33:17,280
Vrednost, ki je bil v prvi, kakšno vrednost je bila v prvi?

551
00:33:17,280 --> 00:33:21,930
Najprej je pokazal na tem vozlišču, da to pomeni, da mora to zdaj opozoriti na to vozlišče.

552
00:33:21,930 --> 00:33:25,660
Z drugimi besedami, kar je videti smešno, čeprav igraš z mojo pisavo,

553
00:33:25,660 --> 00:33:28,620
Kaj je preprosta ideja samo premika puščici, okoli

554
00:33:28,620 --> 00:33:31,560
prevaja kodo s samo te ene plasti.

555
00:33:31,560 --> 00:33:38,110
Shranite, kar je v prvi na naslednje polje in nato posodobite kaj 1. dejansko je.

556
00:33:38,110 --> 00:33:40,900
Pojdimo in hitro naprej skozi nekaj tega,

557
00:33:40,900 --> 00:33:44,220
in poglej samo na tej rep vstavitve, za zdaj.

558
00:33:44,220 --> 00:33:51,210
Recimo, da sem prišel do točke, ko sem ugotovila, da je naslednje polje nekega vozlišča NULL.

559
00:33:51,210 --> 00:33:53,410
In na tej točki v zgodbo, podrobnosti, ki sem preskakujem

560
00:33:53,410 --> 00:33:58,170
to, da sem uvedli še kazalec gor v skladu 142, predhodnik kazalca.

561
00:33:58,170 --> 00:34:01,320
V bistvu, v tem trenutku v zgodbi, ko dobi seznam dolg,

562
00:34:01,320 --> 00:34:04,800
Nekako morate hoditi z dvema prstoma, ker če grem predaleč,

563
00:34:04,800 --> 00:34:08,219
spomnim na eno dolžino seznamu, ne morete iti nazaj.

564
00:34:08,219 --> 00:34:13,659
Torej ta ideja predptr je moja leva prst in newptr - ne newptr.

565
00:34:13,659 --> 00:34:17,199
Še en namig, da je tu je moj drugi prst, in sem nekako hoje seznam.

566
00:34:17,199 --> 00:34:22,179
Zato, da obstaja. No, pa upoštevamo samo eno od enostavnejših primerov tukaj.

567
00:34:22,179 --> 00:34:26,620
Če tega kazalca se naslednje polje NULL, kaj je logično posledice?

568
00:34:26,620 --> 00:34:30,840
Če ste vozili ta seznam in ga zadel NULL kazalec?

569
00:34:30,840 --> 00:34:35,780
Ste na koncu seznama, in tako kodo, nato priložiti 1 dodaten element

570
00:34:35,780 --> 00:34:41,230
se bo nekako intuitivno sprejeti, da vozlišče, katerega naslednji kazalec NULL,

571
00:34:41,230 --> 00:34:46,120
tako da je to trenutno NULL, in ga spremenil, da je naslov novega vozlišča.

572
00:34:46,120 --> 00:34:52,260
Torej smo samo risbo v kodi puščico, ki smo potegnil na odru z dvigom nekoga levo roko.

573
00:34:52,260 --> 00:34:54,070
>> In v primeru, da bom pomahal roke na za zdaj,

574
00:34:54,070 --> 00:34:58,020
samo zato, ker mislim, da je enostavno se izgubiš, ko to počnemo v to vrsto okolja,

575
00:34:58,020 --> 00:35:00,600
preverja za vključitev v sredini poštnega spiska.

576
00:35:00,600 --> 00:35:03,220
Ampak samo intuitivno, kaj bi se zgodilo, če hočeš, da ugotovimo,

577
00:35:03,220 --> 00:35:06,600
kjer je nekaj več, spada v sredini pa morate, da jo peš

578
00:35:06,600 --> 00:35:09,510
z več kot enim prstom, več kot en kazalec,

579
00:35:09,510 --> 00:35:12,920
ugotovimo, kamor spada s preverjanjem je element, <se bo sedanji,

580
00:35:12,920 --> 00:35:15,450
> Trenutni 1, in ko ste našli to mesto,

581
00:35:15,450 --> 00:35:20,400
potem moraš to storiti vrste divjadi lupine, kjer ste premakniti kazalcev po zelo previdno.

582
00:35:20,400 --> 00:35:23,850
In to je odgovor, če želite, da zato s tega doma sami,

583
00:35:23,850 --> 00:35:28,340
izvira prav na teh dveh vrstic kode, vendar je zaradi teh vrstic je zelo pomembno.

584
00:35:28,340 --> 00:35:31,390
Ker, če nekdo spusti roko in dvig nekdo drug v napačnem vrstnem redu,

585
00:35:31,390 --> 00:35:34,580
še enkrat, bi lahko na koncu orphaning seznam.

586
00:35:34,580 --> 00:35:39,500
Če povzamemo bolj konceptualno, vstavljanja na repu je dokaj preprosta.

587
00:35:39,500 --> 00:35:42,940
Vključitev na čelu je tudi relativno enostavna,

588
00:35:42,940 --> 00:35:45,580
vendar pa boste morali posodobiti dodaten kazalec, tokrat

589
00:35:45,580 --> 00:35:47,930
stisniti številko 5 na seznam tukaj,

590
00:35:47,930 --> 00:35:51,560
in potem vključitev v sredini vključuje še več truda,

591
00:35:51,560 --> 00:35:56,130
zelo previdno vstavite številko 20 v svojem pravem mestu,

592
00:35:56,130 --> 00:35:58,350
, ki je med 17 in 22.

593
00:35:58,350 --> 00:36:02,700
Tako da boste morali narediti nekaj podobnega imajo novo vozlišče točko 20 do 22,

594
00:36:02,700 --> 00:36:08,470
in potem, ki je vozlišče je kazalec je treba posodobiti nazadnje?

595
00:36:08,470 --> 00:36:10,630
To je 17, v resnici ga vstavite.

596
00:36:10,630 --> 00:36:14,080
Torej, še enkrat, bom odloži dejansko kodo za posamezno izvedbo.

597
00:36:14,080 --> 00:36:17,280
>> Na prvi pogled je to malo veliko, ampak to je res samo neskončno zanko

598
00:36:17,280 --> 00:36:21,770
da je zanka, zanka, zanka, zanka, in zlom takoj, ko hit kazalec NULL,

599
00:36:21,770 --> 00:36:24,590
Takrat lahko narediš potrebno vstavljati.

600
00:36:24,590 --> 00:36:30,960
To je torej zastopnik povezani seznam vstavljanje kode.

601
00:36:30,960 --> 00:36:34,590
To je neke vrste veliko, in se počuti kot smo rešili eno težavo,

602
00:36:34,590 --> 00:36:36,940
pa smo uvedli celo drugo. Odkrito povedano, smo porabili ves ta čas

603
00:36:36,940 --> 00:36:40,540
na velikem O in Ω in teče čas, poskuša reševati probleme hitreje,

604
00:36:40,540 --> 00:36:43,270
in tukaj smo naredili velik korak nazaj, se mu zdi.

605
00:36:43,270 --> 00:36:45,380
In še to, če je cilj za shranjevanje podatkov,

606
00:36:45,380 --> 00:36:48,010
se zdi, kot sveti gral, kot smo rekli v ponedeljek, bi bilo res

607
00:36:48,010 --> 00:36:50,470
Shranjevanje stvari takoj.

608
00:36:50,470 --> 00:36:53,930
>> Dejstvo je, denimo, da smo odložili povezani seznam za trenutek

609
00:36:53,930 --> 00:36:56,000
in smo namesto tega uvedel pojem mizo.

610
00:36:56,000 --> 00:36:59,110
In kaj je samo pomislite na mizi za trenutek kot matriko.

611
00:36:59,110 --> 00:37:03,790
Ta pestrost in ta primer tukaj je nekaj 26 elementov, od 0 do 25,

612
00:37:03,790 --> 00:37:07,940
in predvidevam, da je potrebno nekaj kos shranjevanje imen:

613
00:37:07,940 --> 00:37:10,350
Alice in Bob in Charlie in podobno.

614
00:37:10,350 --> 00:37:12,880
In boste potrebovali nekaj podatkovno strukturo za shranjevanje teh imen.

615
00:37:12,880 --> 00:37:15,000
No, lahko uporabite nekaj podobnega povezan seznam

616
00:37:15,000 --> 00:37:20,260
in lahko hodiš seznam vstavljanje Alice pred Bob in Charlie po Bobu in tako naprej.

617
00:37:20,260 --> 00:37:23,850
In v resnici, če želite videti kodo, kot je ta v prahi,

618
00:37:23,850 --> 00:37:27,230
vem, da je v list2.h, delamo točno to.

619
00:37:27,230 --> 00:37:30,610
Mi ne bo šel skozi to kodo, ampak to je varianta prvi primer

620
00:37:30,610 --> 00:37:34,640
, ki uvaja še eno struct, ki smo jih videli, preden ti študenta,

621
00:37:34,640 --> 00:37:40,330
in kaj potem dejansko shrani v povezano seznamu je kazalec na strukturo študentov

622
00:37:40,330 --> 00:37:44,520
namesto da preprosto malo celo število, n.

623
00:37:44,520 --> 00:37:46,900
Torej zavedaš, da je oznaka, ki vključuje dejansko obstaja niti,

624
00:37:46,900 --> 00:37:49,940
če pa je cilj na strani res zdaj je reševanje problema učinkovitosti,

625
00:37:49,940 --> 00:37:53,380
Ne bi bilo lepo, če smo glede na predmet z imenom Alice,

626
00:37:53,380 --> 00:37:56,020
želimo, da bi jo dal v pravo mesto v strukturo podatkov,

627
00:37:56,020 --> 00:37:58,860
se zdi, kot bi bilo res lepo, samo da Alice,

628
00:37:58,860 --> 00:38:01,180
katerih ime se začne z, na prvem mestu.

629
00:38:01,180 --> 00:38:05,270
In Bob, katerih ime se začne z B, v drugem mestu.

630
00:38:05,270 --> 00:38:09,580
Z matriko, ali pa začnimo kliče to tabelo, hash tabele pri tem,

631
00:38:09,580 --> 00:38:13,650
ne moremo storiti prav to. Če smo dobili takšno ime Alice,

632
00:38:13,650 --> 00:38:16,700
Niz kot Alice, kje si dal a-L-i-C-e?

633
00:38:16,700 --> 00:38:20,540
Potrebujemo hueristic. Potrebujemo funkcijo, da sprejmejo nekatere prispevke, kot Alice

634
00:38:20,540 --> 00:38:24,610
in vrne odgovor, "Put Alice na tej lokaciji."

635
00:38:24,610 --> 00:38:28,720
In to funkcijo, to črno polje, se bo imenovano funkcijo razpršitve.

636
00:38:28,720 --> 00:38:32,330
>> Razpršilna funkcija je nekaj, kar se vnosa, kot je "Alice",

637
00:38:32,330 --> 00:38:38,080
in se vrne v vas, ponavadi, številčna lokacijo v nekaterih strukture podatkov, kadar Alice pripada.

638
00:38:38,080 --> 00:38:40,830
V tem primeru bi morala biti naša hash funkcija je dokaj preprost.

639
00:38:40,830 --> 00:38:47,510
Naša hash funkcijo je treba povedati, če ste dobili "Alice", ki je znak naj skrbi?

640
00:38:47,510 --> 00:38:55,660
Prvi. Torej gledam [0], potem pa sem rekel, če [0] znak je, vrne število 0.

641
00:38:55,660 --> 00:39:01,130
Če je B, vrne 1. Če je C, vrne 2, in tako naprej.

642
00:39:01,130 --> 00:39:05,940
Vse indeks 0, in da bi mi dovolite, da vstavite Alice in nato Bob in nato Charlie in tako naprej

643
00:39:05,940 --> 00:39:10,960
V to strukturo podatkov. Vendar obstaja problem.

644
00:39:10,960 --> 00:39:13,060
Kaj pa, če Anita prihaja skupaj spet?

645
00:39:13,060 --> 00:39:17,510
Kam smo pripravili Anita? Njeno ime je tudi, začne s črko A,

646
00:39:17,510 --> 00:39:20,330
in se počuti kot smo naredili še večjo zmešnjavo tega problema.

647
00:39:20,330 --> 00:39:24,380
Zdaj imamo takojšnjo vključitev, konstantna čas vnosa, v strukturo podatkov

648
00:39:24,380 --> 00:39:27,100
kot najslabšo linearna,

649
00:39:27,100 --> 00:39:29,510
ampak kaj lahko storimo z Anito v tem primeru?

650
00:39:29,510 --> 00:39:34,110
Kakšne so dve možnosti, res? Ja?

651
00:39:34,110 --> 00:39:37,410
[Student odgovor, nerazumljiv] Ok, tako da bi lahko dobili novo razsežnost.

652
00:39:37,410 --> 00:39:42,320
To je dobro. Tako lahko gradimo stvari v 3D tehniki, kot smo govorili v ponedeljek ustno.

653
00:39:42,320 --> 00:39:46,700
Lahko bi dodali še en dostop do tu, ampak predvidevam, da ne, sem poskušal ohraniti to preprosto.

654
00:39:46,700 --> 00:39:50,160
Celoten cilj tukaj je, da imajo takojšen stalen dostop času,

655
00:39:50,160 --> 00:39:52,170
tako, da je dodal preveč kompleksnosti.

656
00:39:52,170 --> 00:39:55,970
Kakšne so druge možnosti, ko skušajo vstaviti Anita v tej strukturi podatkov? Ja?

657
00:39:55,970 --> 00:39:58,610
[Student odgovor, nerazumljiv] Dobro. Torej lahko gremo vsi ostali navzdol

658
00:39:58,610 --> 00:40:03,040
kot Charlie dregne navzdol Bob in Alice, nato pa smo se Anita, če res želi biti.

659
00:40:03,040 --> 00:40:05,660
>> Seveda, zdaj pa je stranski učinek tega.

660
00:40:05,660 --> 00:40:09,000
Ta struktura podatkov, je verjetno koristno, ne zato, ker želimo vstaviti ljudi, ko

661
00:40:09,000 --> 00:40:11,250
ampak zato, ker smo želeli preveriti, če so tam kasneje

662
00:40:11,250 --> 00:40:13,600
če želimo izpisati vsa imena v strukturi podatkov.

663
00:40:13,600 --> 00:40:15,850
Bomo nekaj storiti s temi podatki na koncu.

664
00:40:15,850 --> 00:40:20,810
Zdaj smo že vrsto privili v Alice, ki je ni več kje je moral biti.

665
00:40:20,810 --> 00:40:23,880
Prav tako je Bob, prav tako je Charlie.

666
00:40:23,880 --> 00:40:26,060
Mogoče to ni tako dobra ideja.

667
00:40:26,060 --> 00:40:28,830
Ampak seveda, to je ena od možnosti. Mi lahko premakne vse navzdol,

668
00:40:28,830 --> 00:40:32,240
ali pekel, Anita prišla prepozno v igro, zakaj ne bi raje dal Anita

669
00:40:32,240 --> 00:40:35,870
ne tukaj, ne tukaj, ne tukaj, kaj je pravkar jo dal malo nižje na seznamu.

670
00:40:35,870 --> 00:40:38,680
Ampak potem je to problem se začne znova prenesti.

671
00:40:38,680 --> 00:40:41,630
Morda boste lahko našli Alice takoj, na podlagi njenega imena.

672
00:40:41,630 --> 00:40:44,320
In Bob takoj in Charlie. Ampak potem iskati Anita,

673
00:40:44,320 --> 00:40:46,360
in vidite, hmm, Alice je v napoto.

674
00:40:46,360 --> 00:40:48,770
No, naj preverim pod Alice. Bob ni Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie ni Anita. Oh, je Anita.

676
00:40:51,850 --> 00:40:54,720
In če boste še naprej vlak logike vso pot,

677
00:40:54,720 --> 00:41:00,690
kaj je najslabši čas vožnje za iskanje in vstavljanje Anita v novo strukturo podatkov?

678
00:41:00,690 --> 00:41:03,280
To je O (n), kajne?

679
00:41:03,280 --> 00:41:06,280
Ker v najslabšem primeru pa je Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
vso pot navzdol, da nekdo z imenom "Y", tako da je le eno mesto levo.

681
00:41:10,150 --> 00:41:13,950
K sreči smo imeli nikogar, imenovano "Z", zato smo se Anita na samem dnu.

682
00:41:13,950 --> 00:41:16,040
>> Nismo zares rešil ta problem.

683
00:41:16,040 --> 00:41:19,890
Mogoče pa je treba uvesti to tretjo dimenzijo.

684
00:41:19,890 --> 00:41:22,230
In izkazalo se je, če ne bomo uvesti to tretjo dimenzijo,

685
00:41:22,230 --> 00:41:25,240
ne moremo narediti odlično, vendar je sveti gral se bo pridobivanje

686
00:41:25,240 --> 00:41:28,370
stalen čas vstavitve in dinamične vstavljanja, tako da

687
00:41:28,370 --> 00:41:30,960
nimamo na trdo koda matrika velikosti 26.

688
00:41:30,960 --> 00:41:34,400
Mi lahko vstavite toliko imen, kot smo želeli, vendar pa si vzamemo 5-minutni odmor tukaj

689
00:41:34,400 --> 00:41:38,790
in potem to naredil pravilno.

690
00:41:38,790 --> 00:41:46,020
V redu. Sem nastavil zgodbo precej umetno tam

691
00:41:46,020 --> 00:41:48,670
z izbiro Alice in nato Bob in nato Charlie in nato Anita,

692
00:41:48,670 --> 00:41:51,000
čigar ime je bilo očitno bo trčijo z Alice.

693
00:41:51,000 --> 00:41:54,120
Toda vprašanje, ki se je končalo v ponedeljek, z le tem, kako verjetno je, da

694
00:41:54,120 --> 00:41:56,370
da bi dobili te vrste trčenj? Z drugimi besedami,

695
00:41:56,370 --> 00:42:00,490
če začnemo uporabljati to tabelarične strukture, ki je res samo matrika,

696
00:42:00,490 --> 00:42:02,460
v tem primeru 26 lokacijah,

697
00:42:02,460 --> 00:42:05,740
Kaj pa, če so naši vložki namesto enakomerno porazdeljeno?

698
00:42:05,740 --> 00:42:09,620
To ni umetno Alice in Bob in Charlie in David in tako naprej po abecedi

699
00:42:09,620 --> 00:42:12,380
to je enakomerno porazdeljeno po Z.

700
00:42:12,380 --> 00:42:15,220
>> Mogoče bomo le srečo in mi ne bo treba 2 je B-jev ali dva

701
00:42:15,220 --> 00:42:17,640
z zelo veliko verjetnostjo, ampak kot nekdo opozoril,

702
00:42:17,640 --> 00:42:20,730
če posplošena ta problem in ne storiti 0-25

703
00:42:20,730 --> 00:42:26,060
ampak, recimo, od 0 do 364 in 65, se je število dni, v običajnem letu,

704
00:42:26,060 --> 00:42:31,170
in vprašala: "Kaj pa je verjetnost, da sta dva od nas v tej sobi imajo isti rojstni dan?"

705
00:42:31,170 --> 00:42:34,600
Povedano drugače, v čem je verjetnost, da naju imajo ime se začne z?

706
00:42:34,600 --> 00:42:37,190
Neke vrste vprašanje je enak, vendar je ta naslovni prostor,

707
00:42:37,190 --> 00:42:39,940
to iskanje prostora, je večja pri rojstnih dnevih,

708
00:42:39,940 --> 00:42:42,820
ker imamo toliko več dni v letu, od črk v abecedi.

709
00:42:42,820 --> 00:42:44,910
Kakšna je verjetnost trka?

710
00:42:44,910 --> 00:42:48,410
No, lahko razmišljamo o tem, ki jih poskušal ugotoviti, matematika v nasprotno smer.

711
00:42:48,410 --> 00:42:50,580
Kakšna je verjetnost, da brez trkov?

712
00:42:50,580 --> 00:42:53,970
No, ta izraz pravi, da tisto, kar je verjetnost

713
00:42:53,970 --> 00:42:58,770
če je samo ena oseba v tej sobi, da imajo edinstveno rojstni dan?

714
00:42:58,770 --> 00:43:01,190
To je 100%. Ker če je samo ena oseba v sobi,

715
00:43:01,190 --> 00:43:03,940
njegov ali njen rojstni dan je lahko katera koli od 365 dni v letu.

716
00:43:03,940 --> 00:43:08,650
Torej 365/365 možnosti mi daje vrednost 1.

717
00:43:08,650 --> 00:43:11,250
Zato je verjetnost, zadevni v tem trenutku je le 1.

718
00:43:11,250 --> 00:43:13,270
Ampak, če obstaja druga oseba v sobi,

719
00:43:13,270 --> 00:43:16,490
kaj je verjetnost, da je njihov rojstni dan drugačen?

720
00:43:16,490 --> 00:43:20,680
Tukaj je le mogoče, 364 dni, če izvzamemo prestopna leta,

721
00:43:20,680 --> 00:43:23,580
za rojstni dan niso v nasprotju z drugimi osebami.

722
00:43:23,580 --> 00:43:31,920
Torej 364/365. Če tretja oseba prihaja, to je 363/365 in tako naprej.

723
00:43:31,920 --> 00:43:35,790
Tako smo ostali zmnožku teh frakcij, ki so vse manjši in manjši,

724
00:43:35,790 --> 00:43:40,720
da ugotovimo, kaj je verjetnost, da imamo vsi edinstvene rojstne dneve?

725
00:43:40,720 --> 00:43:43,570
Ampak potem bomo lahko, seveda, samo da ta odgovor in ga flip okoli

726
00:43:43,570 --> 00:43:47,210
in še 1 minus vse to, izraz, da bomo na koncu dobili

727
00:43:47,210 --> 00:43:51,250
če se spomnite na zadnjo stran vaših matematičnih knjig, izgleda malo kaj takega,

728
00:43:51,250 --> 00:43:54,590
ki je veliko lažje razumeti grafično.

729
00:43:54,590 --> 00:43:57,820
In tukaj je ta grafični na os x število rojstni dan,

730
00:43:57,820 --> 00:44:02,030
ali število ljudi s rojstni dan, in na osi y, je verjetnost, da bo tekmo.

731
00:44:02,030 --> 00:44:06,060
In kaj je rekel je, da če imate, recimo, tudi,

732
00:44:06,060 --> 00:44:10,860
kaj je izbrati nekaj podobnega 22, 23 let.

733
00:44:10,860 --> 00:44:13,160
Če je 22 ali 23 ljudi v sobi,

734
00:44:13,160 --> 00:44:17,100
je verjetnost, da sta dva od teh zelo malo ljudi, ki bodo imeli enako rojstni dan

735
00:44:17,100 --> 00:44:19,560
je pravzaprav zelo visoka, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% verjetnost, da je v razredu le 22 ljudi, seminar, praktično,

737
00:44:23,450 --> 00:44:25,790
2 od teh ljudi se dogaja, da imajo enako rojstni dan.

738
00:44:25,790 --> 00:44:28,520
Ker obstaja toliko načinov, na katere lahko imajo isti rojstni dan.

739
00:44:28,520 --> 00:44:31,110
Še huje, če pogledaš na desni strani grafikona,

740
00:44:31,110 --> 00:44:34,040
čas, ki ga imajo v razredu z 58 učenci v njem,

741
00:44:34,040 --> 00:44:39,270
verjetnost 2 ljudi, ki imajo rojstni dan je super, super visoka, skoraj 100%.

742
00:44:39,270 --> 00:44:41,880
No, to je neke vrste zabavna dejstva o resničnem življenju.

743
00:44:41,880 --> 00:44:45,850
>> Toda posledice, zdaj, podatkovnih struktur in shranjevanje informacij

744
00:44:45,850 --> 00:44:51,100
pomeni, da le ob predpostavki, da imate lepo, čisto in enakomerno porazdelitev podatkov

745
00:44:51,100 --> 00:44:53,650
in imate dovolj velik spekter, da se prilega kup stvari

746
00:44:53,650 --> 00:44:59,360
ne pomeni, da boš dobil ljudi v različnih lokacij.

747
00:44:59,360 --> 00:45:03,810
Ti boš moral trčenja. Torej ta pojem hašiš, kot se imenuje,

748
00:45:03,810 --> 00:45:07,450
ob vnosa, kot je "Alice" in ga vmasirajte na nek način

749
00:45:07,450 --> 00:45:10,190
in potem dobili nazaj odgovor, kot 0 ali 1 ali 2.

750
00:45:10,190 --> 00:45:17,500
Vrnil nekaj izhod iz te funkcije je pestile ta verjetnost trka.

751
00:45:17,500 --> 00:45:19,530
Torej, kako lahko obravnavo teh trkov?

752
00:45:19,530 --> 00:45:21,940
No, na enem primeru, da bomo lahko idejo, da je bil predlagan.

753
00:45:21,940 --> 00:45:25,100
Mi lahko samo premakniti vse navzdol, ali morda, malo bolj enostavno,

754
00:45:25,100 --> 00:45:29,870
kot vsi ostali move, kaj je samo premakniti Anita na dnu voljo kraju samem.

755
00:45:29,870 --> 00:45:32,810
Torej, če je v Alice 0, Bob je 1, Charlie je v 2,

756
00:45:32,810 --> 00:45:35,260
bomo samo da Anita na lokaciji 3.

757
00:45:35,260 --> 00:45:38,860
In to je tehnika, pri podatkovne strukture imenujemo linearna sondiranje.

758
00:45:38,860 --> 00:45:41,310
Linearni saj ste samo peš to vrstico in si nekako sondiranje

759
00:45:41,310 --> 00:45:43,640
razpoložljive mestih v strukturi podatkov.

760
00:45:43,640 --> 00:45:46,210
Seveda, to je naloga v O (n).

761
00:45:46,210 --> 00:45:49,590
Če podatkovna struktura je zelo polno, tam je 25 ljudi je v njem že

762
00:45:49,590 --> 00:45:54,120
in potem Anita prihaja skupaj, ona konča, kaj bi mesto Z, in to je v redu.

763
00:45:54,120 --> 00:45:56,540
Še vedno paše, in smo jo lahko našli kasneje.

764
00:45:56,540 --> 00:46:00,100
>> Ampak to je bilo v nasprotju s ciljem pospešiti stvari.

765
00:46:00,100 --> 00:46:02,530
Pa kaj, če smo namesto tega uvedli tretjo dimenzijo?

766
00:46:02,530 --> 00:46:06,400
Ta tehnika je navadno imenujemo Veriženje, ali ima verige.

767
00:46:06,400 --> 00:46:10,030
In kaj je sedaj razpršena tabela, to tabelarični struktura,

768
00:46:10,030 --> 00:46:13,450
vaša miza je le niz kazalcev.

769
00:46:13,450 --> 00:46:18,230
Ampak kaj so ti kazalci kažejo, da je ugibanje, kaj?

770
00:46:18,230 --> 00:46:21,970
Povezani seznam. Pa kaj, če bomo najboljše obeh svetov?

771
00:46:21,970 --> 00:46:26,500
Mi uporabljamo nize za začetne indekse

772
00:46:26,500 --> 00:46:32,070
v strukturo podatkov, da bomo lahko takoj pojdite na [0] [1], [30] ali tako dalje,

773
00:46:32,070 --> 00:46:36,480
vendar tako, da imamo nekaj prožnosti, da lahko fit Anita in Alice in Adam

774
00:46:36,480 --> 00:46:38,630
in katero koli drugo ime,

775
00:46:38,630 --> 00:46:43,470
smo namesto tega kaj druga os rastejo samovoljno.

776
00:46:43,470 --> 00:46:47,340
In končno, kot v ponedeljek, so, da izrazno zmogljivost z povezanem seznamu.

777
00:46:47,340 --> 00:46:49,530
Mi lahko raste podatkovno strukturo samovoljno.

778
00:46:49,530 --> 00:46:52,450
Druga možnost je, lahko bi le, da veliko 2-dimenzionalni array,

779
00:46:52,450 --> 00:46:57,190
ampak to se dogaja, da je grozno stanje, če ena od vrstic v 2-dimenzionalni array

780
00:46:57,190 --> 00:47:01,280
ni dovolj velika za dodatno osebo, katere ime se zgodi, da začnete z A.

781
00:47:01,280 --> 00:47:04,200
Bog ne daj, da bomo morali prerazporediti velik 2-dimenzionalno strukturo

782
00:47:04,200 --> 00:47:06,600
Samo zato, ker je toliko ljudi z imenom,

783
00:47:06,600 --> 00:47:09,480
še posebej, ko je tako malo ljudi, imenovana Z nekaj.

784
00:47:09,480 --> 00:47:12,170
To je le, da bo treba zelo redka strukturo podatkov.

785
00:47:12,170 --> 00:47:15,400
Torej, to ni popoln na kakršen koli način, zdaj pa smo vsaj imeli možnost

786
00:47:15,400 --> 00:47:19,090
da takoj našli, če Alice in Anita pripada,

787
00:47:19,090 --> 00:47:21,090
vsaj z vidika navpične osi

788
00:47:21,090 --> 00:47:25,850
in potem bomo morali odločiti, kam Anita ali Alice v tem povezan seznam.

789
00:47:25,850 --> 00:47:32,480
Če nam ni mar za urejanje stvari, kako hitro smo lahko vstavite Alice v strukturo, kot je ta?

790
00:47:32,480 --> 00:47:35,370
To je stalen čas. Mi indeks v [0], in če je nihče ni tam,

791
00:47:35,370 --> 00:47:37,550
Alice gre na začetku tega povezanega seznama.

792
00:47:37,550 --> 00:47:40,000
Ampak to ni velik posel. Ker če Anita potem pride skupaj

793
00:47:40,000 --> 00:47:42,160
nekaj več korakov pozneje, če ne pripada Anita?

794
00:47:42,160 --> 00:47:45,140
No, [0]. OOP. Alice je že v tem povezan seznam.

795
00:47:45,140 --> 00:47:47,760
>> Toda, če ne skrbi za urejanje teh imen,

796
00:47:47,760 --> 00:47:53,580
lahko samo premaknete Alice več, Anita vložek, ampak tudi, da je konstantna čas.

797
00:47:53,580 --> 00:47:57,010
Tudi če obstaja Alice in Adama in vsi ti A imena,

798
00:47:57,010 --> 00:47:59,410
to ni res jih prestavljajo fizično. Zakaj?

799
00:47:59,410 --> 00:48:04,090
Ker smo pravkar naredil sem z povezanega seznama, ki ve, so ta vozlišča so anyway?

800
00:48:04,090 --> 00:48:06,550
Vse kar morate storiti je, da se premaknete na krušnih drobtin.

801
00:48:06,550 --> 00:48:10,930
Move okrog s puščicami, zato vam ni treba fizično premakniti nobenih podatkov naokoli.

802
00:48:10,930 --> 00:48:14,610
Tako bomo lahko vstavite Anita, v tem primeru takoj. Stalno čas.

803
00:48:14,610 --> 00:48:20,250
Torej imamo konstantno času lookup in konstantno času vstavitev nekoga, kot je Anita.

804
00:48:20,250 --> 00:48:22,740
Ampak nekako oversimplifying svet.

805
00:48:22,740 --> 00:48:28,510
Kaj, če bi kasneje želeli, da bi našli Alice?

806
00:48:28,510 --> 00:48:31,050
Kaj, če bi kasneje želeli, da bi našli Alice?

807
00:48:31,050 --> 00:48:35,690
Koliko korakov je, da bo trajalo?

808
00:48:35,690 --> 00:48:37,850
[Student odgovor, nerazumljiv]

809
00:48:37,850 --> 00:48:40,950
Točno tako. Število ljudi, pred Alica v povezanem seznamu.

810
00:48:40,950 --> 00:48:45,420
Torej, to ni čisto popoln, saj je naša podatkovna struktura, še enkrat, je to navpično dostop

811
00:48:45,420 --> 00:48:50,240
in potem je ta povezana sezname visi - pravzaprav naj ne pripravi ga niza.

812
00:48:50,240 --> 00:48:56,020
To je ti povezani seznam visi za to, da izgleda malo kaj takega.

813
00:48:56,020 --> 00:48:59,110
Ampak problem je, če se Alice in Adama in vsi ti A imena

814
00:48:59,110 --> 00:49:01,720
na koncu bolj in bolj tam,

815
00:49:01,720 --> 00:49:04,810
iskanje nekdo lahko na koncu ob kup korakov,

816
00:49:04,810 --> 00:49:06,670
bcause morate prečkati povezani seznam,

817
00:49:06,670 --> 00:49:08,090
ki je linearna operacija.

818
00:49:08,090 --> 00:49:14,270
Torej res, potem, ko je navsezadnje vstavljanje O (n), kjer je n število elementov v seznamu.

819
00:49:14,270 --> 00:49:21,780
Delimo jih, kaj je samovoljno imenujejo m, kjer je m število povezanih seznamov

820
00:49:21,780 --> 00:49:24,500
da imamo v tem navpične osi.

821
00:49:24,500 --> 00:49:27,180
Z drugimi besedami, če bomo resnično prevzeti enakomerno porazdelitev imen,

822
00:49:27,180 --> 00:49:30,150
popolnoma nerealen. Tu je seveda še nekaterih pisem od drugih.

823
00:49:30,150 --> 00:49:32,580
>> Ampak, če predpostavimo, zaenkrat enotno distribucijsko

824
00:49:32,580 --> 00:49:37,350
in smo N skupaj ljudi in celotne verige m

825
00:49:37,350 --> 00:49:40,630
imamo na voljo, potem dolžina vsakega od teh verig

826
00:49:40,630 --> 00:49:44,380
dokaj preprosto se bo skupna, n deljen s številom verig.

827
00:49:44,380 --> 00:49:48,900
Torej n / m. Ampak tukaj kjer smo lahko vsi matematično pameten.

828
00:49:48,900 --> 00:49:53,030
m je konstantna, ker je določeno število teh.

829
00:49:53,030 --> 00:49:54,620
Ti boš razglasila svojo paleto na začetku,

830
00:49:54,620 --> 00:49:58,450
in nismo spreminjanje velikosti navpične osi. Po definiciji, ki je določena ostane.

831
00:49:58,450 --> 00:50:01,220
To je samo horizontalna os, če se tako izrazim, ki se spreminja.

832
00:50:01,220 --> 00:50:04,760
Torej, tehnično, to je konstanta. Torej, zdaj, vstavljanje čas

833
00:50:04,760 --> 00:50:09,700
je precej O (n).

834
00:50:09,700 --> 00:50:12,410
Tako, da ne čuti vse, da je veliko bolje.

835
00:50:12,410 --> 00:50:14,940
Toda kaj je resnica tukaj? No, ves ta čas, za tedne,

836
00:50:14,940 --> 00:50:20,640
smo bili pravi O (n ²). O (n), 2 x n ², - n, deljeno z 2. . . ECH.

837
00:50:20,640 --> 00:50:23,580
To je samo n ². Toda zdaj, v tem delu semestra,

838
00:50:23,580 --> 00:50:25,560
lahko začnemo govoriti o resničnem svetu znova.

839
00:50:25,560 --> 00:50:31,520
In n / m je popolnoma hitreje kot le n sam.

840
00:50:31,520 --> 00:50:35,170
Če imate več kot tisoč imen, in jih razbije na več segmentov

841
00:50:35,170 --> 00:50:37,820
tako da imate samo 10 imen v vsaki od teh verig,

842
00:50:37,820 --> 00:50:41,670
Popolnoma iskati deset stvari, se bo hitreje kot tisoč stvari.

843
00:50:41,670 --> 00:50:43,740
In tako eno od naslednjih problemskih sklopov vas bo izpodbijala

844
00:50:43,740 --> 00:50:46,100
razmišljati o točno to, čeprav, ja,

845
00:50:46,100 --> 00:50:49,520
asimptotično in matematično, je to še vedno samo linearna,

846
00:50:49,520 --> 00:50:51,700
, ki je zanič na splošno, ko poskušajo najti stvari.

847
00:50:51,700 --> 00:50:54,530
V resnici pa se dogaja, da se hitreje, kot je

848
00:50:54,530 --> 00:50:56,520
zaradi tega delitelj.

849
00:50:56,520 --> 00:50:58,310
In tako se je spet bo ta kompromis

850
00:50:58,310 --> 00:51:01,390
in ta konflikt med teorijo in realnostjo,

851
00:51:01,390 --> 00:51:03,550
in bo eden izmed gumbov začela vrteti v tem trenutku v semestru

852
00:51:03,550 --> 00:51:07,510
je bolj za realnost 1, kot smo nekako pripraviti na koncu semster je,

853
00:51:07,510 --> 00:51:09,280
kot uvajamo v svet programiranja spletnih strani,

854
00:51:09,280 --> 00:51:11,530
če res, uspešnost štelo bo, ker uporabniki se bodo

855
00:51:11,530 --> 00:51:14,880
začnete počutiti in cenijo slabe odločitve design.

856
00:51:14,880 --> 00:51:19,950
>> Torej, kako si šel o izvajanju povezano - razpršitve tabelo z 31 elementi?

857
00:51:19,950 --> 00:51:22,600
In prejšnji primer je samovoljno o rojstnih dnevih.

858
00:51:22,600 --> 00:51:26,190
Če ima nekdo rojstni dan 1. januar ali februar 1, jih bomo dal v ta segment.

859
00:51:26,190 --> 00:51:28,960
Če je 2. januar, 2. februar, marec 2, jih bomo dal v ta segment.

860
00:51:28,960 --> 00:51:32,220
Zato je bil 31. Kako se razglasi razpršene tabele?

861
00:51:32,220 --> 00:51:37,480
To je lahko zelo enostavno, vozlišče * miza je moje poljubno ime za to, [31].

862
00:51:37,480 --> 00:51:42,400
To mi daje napotke za 31 vozlišč,

863
00:51:42,400 --> 00:51:45,370
in ki mi omogoča, da imajo 31 nasvetov za povezane sezname

864
00:51:45,370 --> 00:51:48,800
tudi če te verige so sprva NULL.

865
00:51:48,800 --> 00:51:54,860
Kaj hočem dati, če želim shraniti "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
No, moramo zaviti tiste stvari, v strukturi

867
00:51:57,010 --> 00:52:00,530
ker moramo opozoriti, da Alice Bob, ki kaže na Charlie, in tako naprej.

868
00:52:00,530 --> 00:52:04,940
Ne moremo imeti imena sami, tako da sem lahko zgradili novo strukturo, imenovano vozlišče tukaj.

869
00:52:04,940 --> 00:52:08,310
>> Kaj je dejansko vozel? Kaj je vozlišče v tem novem povezana seznamu?

870
00:52:08,310 --> 00:52:11,840
Prva stvar, ki se imenuje beseda, je za ime osebe.

871
00:52:11,840 --> 00:52:14,340
DOLŽINA, domnevno nanaša na največjo dolžino imena človekova je,

872
00:52:14,340 --> 00:52:18,210
karkoli že to je, 20, 30, 40 znakov v norih primerih kotiček,

873
00:52:18,210 --> 00:52:22,680
in 1 je za kaj? To je samo dodatno NULL znak, \ 0.

874
00:52:22,680 --> 00:52:27,410
Torej, to vozlišče je zavijanje "nekaj" znotraj samega sebe,

875
00:52:27,410 --> 00:52:29,640
pa tudi izjavlja, kazalec, imenovan Naslednja

876
00:52:29,640 --> 00:52:32,580
tako da bomo lahko veriga Alice, da Bob s Charlijem in tako naprej.

877
00:52:32,580 --> 00:52:36,700
More biti nič, vendar ni nujno, da je.

878
00:52:36,700 --> 00:52:40,110
Vsa vprašanja v zvezi s temi hash tabele? Ja?

879
00:52:40,110 --> 00:52:46,190
[Student sprašuje vprašanje, nerazumljiv] matrika - dobro vprašanje.

880
00:52:46,190 --> 00:52:50,120
Zakaj je to znak beseda v polju in ne samo char *?

881
00:52:50,120 --> 00:52:53,830
V tem primeru nekoliko arbitrarno, nisem hotel, da zateči

882
00:52:53,830 --> 00:52:56,190
za knjižnične funkcije malloc za izvirnih imen.

883
00:52:56,190 --> 00:52:59,530
Želel sem jo razglaša za največjo količino pomnilnika za niz

884
00:52:59,530 --> 00:53:06,020
tako da sem lahko kopirate v strukturi Alice \ 0 in ni treba ukvarjati z knjižnične funkcije malloc in brezplačno in podobnega.

885
00:53:06,020 --> 00:53:11,710
Vendar pa bi to naredil, če sem hotel biti bolj dovzetni za uporabo prostora. Dobro vprašanje.

886
00:53:11,710 --> 00:53:14,780
Torej poskusimo posploševati od tega

887
00:53:14,780 --> 00:53:18,350
in se osredotočiti na preostalem danes na podatkovne strukture bolj na splošno

888
00:53:18,350 --> 00:53:21,170
in druge težave, ki jih lahko rešujemo z uporabo istih temeljih

889
00:53:21,170 --> 00:53:24,590
čeprav so podatkovne strukture lahko sami razlikujejo v svojih podatkov.

890
00:53:24,590 --> 00:53:27,910
>> Tako se izkaže, računalništva, drevesa so zelo pogosti.

891
00:53:27,910 --> 00:53:29,760
In lahko si misliš drevesa vrste kot družinsko drevo,

892
00:53:29,760 --> 00:53:31,830
kjer je nekaj korenine, nekatere matriarch ali patriarh,

893
00:53:31,830 --> 00:53:34,540
babica ali dedek ali prej nazaj,

894
00:53:34,540 --> 00:53:38,880
pod katero se mama in oče ali različne bratje in sestre ali podobno.

895
00:53:38,880 --> 00:53:42,500
Tako drevo struktura vozlišč in ima otroke,

896
00:53:42,500 --> 00:53:45,260
ponavadi 0 ali več otrok, za vsako vozlišče.

897
00:53:45,260 --> 00:53:47,320
In nekaj žargona, ki jih vidite na sliki here

898
00:53:47,320 --> 00:53:50,630
je katera koli majhni otroci ali vnuki, na obrobju

899
00:53:50,630 --> 00:53:52,330
ki nima puščice, ki izhajajo iz njih,

900
00:53:52,330 --> 00:53:55,070
to so tako imenovane liste, in kdorkoli v notranjosti

901
00:53:55,070 --> 00:53:58,790
je notranja vozlišča, ki jih lahko imenujemo tudi kaj podobnega.

902
00:53:58,790 --> 00:54:01,430
Toda ta struktura je precej pogosta. Ta je malce arbitraren.

903
00:54:01,430 --> 00:54:04,930
Imamo enega otroka na levi, imamo tri otroke na desni strani,

904
00:54:04,930 --> 00:54:06,830
dva otroka na dnu levo.

905
00:54:06,830 --> 00:54:10,740
Tako imamo lahko različnih velikosti drevesa, ampak če bomo začeli standardizirati stvari,

906
00:54:10,740 --> 00:54:15,330
in morda spomnite iz tega videa Patrika na binarnem iskanju od prejšnje kratek

907
00:54:15,330 --> 00:54:19,490
spletu, binarno iskanje ni treba izvajati z vrsto

908
00:54:19,490 --> 00:54:21,410
ali kos papirja na tabli.

909
00:54:21,410 --> 00:54:25,490
Recimo, da ste želeli za shranjevanje številk na bolj prefinjeno strukturo podatkov.

910
00:54:25,490 --> 00:54:27,680
Lahko ustvarite drevo, kot je ta.

911
00:54:27,680 --> 00:54:35,290
Lahko bi vozlišče prijavljeni v C, in da vozlišče lahko vsaj dva elementa v njej.

912
00:54:35,290 --> 00:54:39,470
Eno je številka, ki jo želite shraniti, in drugi je - no, potrebujemo še eno.

913
00:54:39,470 --> 00:54:41,540
Drugi so njeni otroci.

914
00:54:41,540 --> 00:54:45,150
Torej, tukaj je še en struktura podatkov. Tokrat je vozlišče opredeljena kot shranjevanje število n

915
00:54:45,150 --> 00:54:49,060
in potem 2 kazalci, levo in desno otrok otrok.

916
00:54:49,060 --> 00:54:52,100
In oni ne samovoljno. Kaj je zanimivo to drevo?

917
00:54:52,100 --> 00:55:00,550
>> Kaj je vzorec, kako smo iz tega, oziroma kako Patrick je določeno v svojem videu?

918
00:55:00,550 --> 00:55:02,790
To je nekako jasno, da obstaja nekaj sortiranje dogaja,

919
00:55:02,790 --> 00:55:04,460
kaj pa je preprosto pravilo? Ja?

920
00:55:04,460 --> 00:55:08,350
[Student odgovor, nerazumljiv]

921
00:55:08,350 --> 00:55:12,040
Popolno. Če pogledam v to, boste videli majhno število na levi strani,

922
00:55:12,040 --> 00:55:14,690
velike številke na levi strani, ampak to velja za vsako vozlišče.

923
00:55:14,690 --> 00:55:20,370
Za vsako vozlišče, njena leva otrok, mlajši od nje, in njena pravica otrok večji od njega.

924
00:55:20,370 --> 00:55:25,210
Kaj to pomeni, je zdaj, če želim iskati to podatkovno strukturo, na primer, je število 44,

925
00:55:25,210 --> 00:55:29,320
Moram začeti pri korenu, saj je pri vseh teh bolj kompleksnih podatkovnih struktur zdaj,

926
00:55:29,320 --> 00:55:31,910
imamo le kazalec na eno stvar, začetek.

927
00:55:31,910 --> 00:55:35,010
In v tem primeru, je začetek korenine. Ne levi konec,

928
00:55:35,010 --> 00:55:39,530
da je vzrok za to strukturo. Vidim, tukaj je 55, in iščem 44.

929
00:55:39,530 --> 00:55:41,430
V katero smer ne želim iti?

930
00:55:41,430 --> 00:55:45,680
No, rad bi šel na levo, saj je očitno, da pravica se bo prevelika.

931
00:55:45,680 --> 00:55:49,050
Torej, opazil sem, da si nekako konceptualno sekanje drevesa na pol

932
00:55:49,050 --> 00:55:51,700
ker nikoli ne boš dol na desni strani.

933
00:55:51,700 --> 00:55:55,410
Zdaj sem šel od 55 do 33 let. To je premajhen števila.

934
00:55:55,410 --> 00:56:01,590
Iščem 44, zdaj pa vem, če je 44 je v tem drevesu, grem lahko seveda na desni.

935
00:56:01,590 --> 00:56:04,460
Torej, še enkrat, jaz sem obrezovanje drevo na polovico.

936
00:56:04,460 --> 00:56:06,780
To je precej enak pojmovni v imenik.

937
00:56:06,780 --> 00:56:09,510
To je enako, kar smo naredili z dokumenti na tabli,

938
00:56:09,510 --> 00:56:13,940
ampak to je bolj prefinjena struktura, ki nam omogoča, da dejansko ne

939
00:56:13,940 --> 00:56:16,880
To deli in vladaj z zasnovo algoritma,

940
00:56:16,880 --> 00:56:19,420
in v resnici, vozijo strukturo, kot je ta - Ops.

941
00:56:19,420 --> 00:56:22,870
Vozijo strukturo, kot je ta, če je to le "gredo v to smer, ali iti v to smer,"

942
00:56:22,870 --> 00:56:26,870
pomeni vse to kodo, ki sklonil vaš um najprej pri njenem izvajanju v oddelku

943
00:56:26,870 --> 00:56:31,270
ali hojo po njej doma, za binarno iskanje, z uporabo rekurzije ali ponovitvi

944
00:56:31,270 --> 00:56:35,060
to je bolečina v vratu. Najdi srednji element, naredite svojo zaokroži navzgor ali navzdol.

945
00:56:35,060 --> 00:56:39,230
>> Tukaj je lepota tega, ker se lahko sedaj uporablja rekurzijo spet,

946
00:56:39,230 --> 00:56:43,760
vendar veliko bolj čisto. Pravzaprav, če ste na številko 55 in si želim, da bi našli 44,

947
00:56:43,760 --> 00:56:48,450
greš levo v tem primeru, kaj bi vi naredili? Ti vodijo natančno enak algoritem.

948
00:56:48,450 --> 00:56:51,560
Ti preveri vrednost vozlišča, potem greš levo ali desno.

949
00:56:51,560 --> 00:56:53,670
Potem pa preveri vrednost vozlišča, pojdite levo ali desno.

950
00:56:53,670 --> 00:56:56,710
To je idealno za rekurzije.

951
00:56:56,710 --> 00:57:00,920
Torej, čeprav je v preteklosti smo naredili nekaj precej samovoljno primere, ki vključujejo rekurzijo

952
00:57:00,920 --> 00:57:03,430
da ni treba rekurzivno s podatki stuctures,

953
00:57:03,430 --> 00:57:07,820
predvsem drevesa, to je popolna uporaba te ideje ob težave,

954
00:57:07,820 --> 00:57:12,920
to zmanjšuje, nato pa reševanje iste vrste, vendar manjše, program.

955
00:57:12,920 --> 00:57:14,590
>> Torej obstaja še druga struktura podatkov, ki jih lahko predstavimo.

956
00:57:14,590 --> 00:57:18,760
Ta je zasnovan na prvi pogled videti, da skrivnosten, ampak tale je neverjetno.

957
00:57:18,760 --> 00:57:25,090
Torej, to je struktura podatkov, ki se imenuje Trie, Trie, ki se deduje iz besede nalaganju

958
00:57:25,090 --> 00:57:30,210
ki se ne izgovarja ponovno poskusite-val, ampak to je tisto, kar svet imenuje te stvari. Poskuša. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
To je drevesna struktura neke vrste, ampak vsak od vozlišč v Trie

960
00:57:35,190 --> 00:57:41,280
Zdi se, da kaj? In to je malce zavajajoče, ker je vrsta krajša.

961
00:57:41,280 --> 00:57:45,960
Ampak izgleda, da vsako vozlišče v tem Trie je pravzaprav polje.

962
00:57:45,960 --> 00:57:48,840
In čeprav je avtor tega diagrama ne prikaže,

963
00:57:48,840 --> 00:57:54,130
v tem primeru je to Trie je podatkovna struktura, katere namen v življenju je, da shranite besede

964
00:57:54,130 --> 00:57:57,330
kot a-L-i-C-E ali B-o-b.

965
00:57:57,330 --> 00:58:02,480
In način, na katerega so ti podatki prodajalne Alice in Bob in Charlie in Anita in tako naprej

966
00:58:02,480 --> 00:58:06,970
se uporablja za shranjevanje niz, s katerim Alice v Trie,

967
00:58:06,970 --> 00:58:09,820
začnemo na korenski vozel, ki izgleda kot matriko,

968
00:58:09,820 --> 00:58:12,080
in je bilo napisano v zapisu bljižnica.

969
00:58:12,080 --> 00:58:15,070
Avtor izpusti ABCDEFG, ker ni bilo imen s tem.

970
00:58:15,070 --> 00:58:19,150
So pokazali le, M in P in T, vendar v tem primeru,

971
00:58:19,150 --> 00:58:22,780
pojdimo stran od Alice in Bob in Charlija nekaterih imen, ki so tukaj.

972
00:58:22,780 --> 00:58:25,670
Maxwell je pravzaprav v tem diagramu.

973
00:58:25,670 --> 00:58:29,570
Torej, kako si avtorja trgovino M--x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
On ali ona se je začela v korensko vozlišče, in odšel v [M], tako da približno 13, 13. mesto v polje.

975
00:58:36,990 --> 00:58:40,750
Potem od tam, tam je kazalec.

976
00:58:40,750 --> 00:58:42,760
Kazalec vodi v drugo polje.

977
00:58:42,760 --> 00:58:47,880
Od tam avtor indeksirana v tem polju na lokaciji A, kot je prikazano tam zgoraj levo,

978
00:58:47,880 --> 00:58:52,250
in potem on ali ona sledi, da je kazalec na drugo polje,

979
00:58:52,250 --> 00:58:55,460
in odšel na kazalec na lokaciji X.

980
00:58:55,460 --> 00:58:59,840
Potem pa v naslednjem mestu matrike W, E, L, L, in tako naprej,

981
00:58:59,840 --> 00:59:03,090
in končno, kaj je dejansko poskuša postaviti sliko na to.

982
00:59:03,090 --> 00:59:05,380
Kaj vozlišče izgledal v kodi?

983
00:59:05,380 --> 00:59:11,820
Vozlišče v Trie vsebuje niz kazalcev za več vozlišč.

984
00:59:11,820 --> 00:59:16,090
Vendar pa je tudi dobil, da je neke vrste logično vrednost, vsaj v tem izvajanju.

985
00:59:16,090 --> 00:59:18,770
Jaz mislim, da ga pokličete is_word. Zakaj?

986
00:59:18,770 --> 00:59:22,670
Ker, ko ste vstavljanju Maxwell, ti ne vstavite

987
00:59:22,670 --> 00:59:25,300
kaj v to strukturo podatkov.

988
00:59:25,300 --> 00:59:27,480
Saj ne bi pisal M. Saj ne bi pisal X.

989
00:59:27,480 --> 00:59:30,240
Vse kar počnete, je po kazalca.

990
00:59:30,240 --> 00:59:33,360
Kazalec, ki predstavlja M, potem je kazalec, ki predstavlja,

991
00:59:33,360 --> 00:59:36,310
Nato kazalec, ki predstavlja X, nato W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
ampak kaj morate storiti, na koncu je nekako gre, preverite, sem dosegel to mesto.

993
00:59:41,950 --> 00:59:45,560
Prišlo je beseda, ki se konča tukaj v podatkovni strukturi.

994
00:59:45,560 --> 00:59:48,190
>> Torej, kaj je res poln Trie in je avtor odločil za zastopanje

995
00:59:48,190 --> 00:59:51,880
ti terminuses z malo trikotnikov.

996
00:59:51,880 --> 00:59:56,470
To samo pomeni, da je dejstvo, ta trikotnik je tu, ta logična vrednost velja

997
00:59:56,470 --> 00:59:59,200
pomeni, da če greš nazaj v drevesu

998
00:59:59,200 --> 01:00:02,420
to pomeni, da besede, imenovano Maxwell je v tem.

999
01:00:02,420 --> 01:00:04,870
Toda beseda foo, na primer,

1000
01:00:04,870 --> 01:00:07,970
ni v drevesu, ker če začnem na korenski vozel gor na vrhu,

1001
01:00:07,970 --> 01:00:14,030
Ni f kazalec, kazalec ne o, ne o kazalec. Foo ni ime na tem slovarju.

1002
01:00:14,030 --> 01:00:22,460
Toda po drugi strani prestrukturiranje, t-u-r-i-n-g. Še enkrat, nisem shranjevanje t ali u ali R ali I ali N ali g.

1003
01:00:22,460 --> 01:00:29,820
Ampak sem trgovino v to strukturo podatkov vrednost prave poti navzdol tu v tem vozlišču - v drevesu

1004
01:00:29,820 --> 01:00:33,030
z nastavitvijo tega boolean vrednost is_word, da res.

1005
01:00:33,030 --> 01:00:35,740
Torej, Trie je nekako to zelo zanimivo strukturo meta,

1006
01:00:35,740 --> 01:00:39,810
če niste zares shranjevanje besede, se za tovrstno slovarju.

1007
01:00:39,810 --> 01:00:45,100
Da bo jasno, da si samo hranjenje z da ali ne, je beseda, ki se konča tukaj.

1008
01:00:45,100 --> 01:00:46,430
>> Zdaj, kaj je posledice?

1009
01:00:46,430 --> 01:00:51,120
Če imate 150.000 besed iz slovarja, ki ga poskušate shraniti v pomnilnik

1010
01:00:51,120 --> 01:00:53,400
nekako takole: povezan seznam,

1011
01:00:53,400 --> 01:00:56,870
boste imeli 150.000 vozlišč v vašem povezani seznam.

1012
01:00:56,870 --> 01:01:00,250
In lahko najti eno od teh besed po abecedi, da O (n) časa.

1013
01:01:00,250 --> 01:01:04,370
Linearni čas. Toda v tem primeru za Trie,

1014
01:01:04,370 --> 01:01:09,210
kaj teče čas za iskanje besedo?

1015
01:01:09,210 --> 01:01:17,390
Izkazalo se je, lepoto, tukaj je, da tudi, če imate 149.999 besed, ki so že v tem slovarju,

1016
01:01:17,390 --> 01:01:20,170
kot je bil izveden s to strukturo podatkov,

1017
01:01:20,170 --> 01:01:25,560
koliko časa traja, da najdejo ali vstavite še eno osebo, ki v to, kot je Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
No, to je le 5, morda 6 korakov za zaključnimi značaja.

1019
01:01:30,640 --> 01:01:32,880
Ker presense drugih imen v strukturi

1020
01:01:32,880 --> 01:01:35,340
ne v napoto, da vstavite Alice.

1021
01:01:35,340 --> 01:01:39,640
Poleg tega je ugotovil, Alice, ko je 150.000 besed v tem slovarju

1022
01:01:39,640 --> 01:01:41,960
ne v napoto pri iskanju Alice sploh,

1023
01:01:41,960 --> 01:01:46,880
ker je Alice. . . . . tukaj, ker sem ugotovila, boolean vrednost.

1024
01:01:46,880 --> 01:01:50,920
In če ni logična res, potem Alice ni v tem strukturo podatkov besed.

1025
01:01:50,920 --> 01:01:56,220
Z drugimi besedami, čas delovanja za odkrivanje stvari in vstavljanje stvari v novi

1026
01:01:56,220 --> 01:02:01,920
Podatki struktura Trie je od O - to ni n.

1027
01:02:01,920 --> 01:02:05,730
Ker presense 150.000 ljudi nima vpliva na Alice, se mi zdi.

1028
01:02:05,730 --> 01:02:11,560
Torej, recimo, da k, kjer je k največja dolžina v angleškem jeziku

1029
01:02:11,560 --> 01:02:14,050
ki je ponavadi ni več kot 20-nekaj znakov.

1030
01:02:14,050 --> 01:02:17,940
Torej, k je konstanta. Torej svetega grala zdi, da smo zdaj ugotovljeno,

1031
01:02:17,940 --> 01:02:26,000
je, da je za Trie, stalno časa za vložke, za poizvedbe za brisanje.

1032
01:02:26,000 --> 01:02:29,170
Ker je število stvari, ki so že v strukturi,

1033
01:02:29,170 --> 01:02:32,600
ki sploh niso fizično tam. Še enkrat, ti si samo nekako odkljukali, da ali ne,

1034
01:02:32,600 --> 01:02:35,050
nima nobenega vpliva na prihodnji teče čas.

1035
01:02:35,050 --> 01:02:37,940
>> Vendar pa ima za ulov, sicer se ne bi zapravili toliko časa

1036
01:02:37,940 --> 01:02:41,460
o vseh teh drugih podatkovnih struktur, samo da na koncu pridemo do tajnih eno, ki je neverjetno.

1037
01:02:41,460 --> 01:02:46,410
Torej, kakšno ceno plačujemo za dosego tega veličino tukaj? Vesolje.

1038
01:02:46,410 --> 01:02:49,010
Ta stvar je ogromen. In razlog, da avtor

1039
01:02:49,010 --> 01:02:52,400
ni ga tukaj predstavljamo, opazili, da se vse te stvari, ki izgledajo kot nizi,

1040
01:02:52,400 --> 01:02:55,400
da ni sprejela ostalo na drevesu, ostali v Trie,

1041
01:02:55,400 --> 01:02:58,060
ker oni niso pomembni le za zgodbo.

1042
01:02:58,060 --> 01:03:01,870
Toda vse te vozle so super širok in vsak vozlišče v drevesu prevzame

1043
01:03:01,870 --> 01:03:07,780
26 ali dejansko, je lahko 27 znakov, ker v tem primeru sem bil tudi prostor za opuščajem

1044
01:03:07,780 --> 01:03:09,980
Tako bi lahko, da imamo apostrophized besede.

1045
01:03:09,980 --> 01:03:14,450
V tem primeru gre za velike nizi. Torej, čeprav oni ne picutured,

1046
01:03:14,450 --> 01:03:18,190
To zavzema ogromno količino RAM-a.

1047
01:03:18,190 --> 01:03:20,670
Ki bi bilo v redu, especilly v sodobni strojni opremi,

1048
01:03:20,670 --> 01:03:25,650
ampak to je kompromis. Smo dobili manj časa, ki ga porabi več prostora.

1049
01:03:25,650 --> 01:03:28,580
Torej, če je vse to dogaja?

1050
01:03:28,580 --> 01:03:32,640
No, dajmo narediti - kaj je tu za videti.

1051
01:03:32,640 --> 01:03:39,510
Naredimo skok tega tipa tukaj.

1052
01:03:39,510 --> 01:03:43,450
>> Verjeli ali ne, tako zabavno kot je C že nekaj časa,

1053
01:03:43,450 --> 01:03:48,130
smo dosegli točko, na polovici, kjer je čas za prehod na bolj modernih stvari.

1054
01:03:48,130 --> 01:03:50,950
Stvari na višji ravni. In čeprav za naslednjih nekaj tednov

1055
01:03:50,950 --> 01:03:54,580
bomo še naprej se bomo potopite v svet kazalcev in upravljanje pomnilnika

1056
01:03:54,580 --> 01:03:57,210
da se da udobno, s katerimi bomo lahko potem gradi naprej,

1057
01:03:57,210 --> 01:04:01,270
Konec igre je končno uvesti, ironično, ne ta jezik.

1058
01:04:01,270 --> 01:04:03,330
Bomo preživeli kot 10 minut govorijo o HTML.

1059
01:04:03,330 --> 01:04:05,950
Vse HTML je označevalni jezik, in kaj je označevalni jezik

1060
01:04:05,950 --> 01:04:10,220
je ta vrsta odprtih in zaprtih nosilci nosilci, ki pravijo, da "bi to krepko"

1061
01:04:10,220 --> 01:04:12,000
"Naj bo to poševnem tisku" "bo to sredino."

1062
01:04:12,000 --> 01:04:14,250
To pa še ni vse, da je intelektualno zanimiva, vendar je to zelo koristno.

1063
01:04:14,250 --> 01:04:16,650
In to je zagotovo povsod prisoten v teh dneh.

1064
01:04:16,650 --> 01:04:19,450
Toda kaj je močna o svetu HTML in spletno programiranje na splošno

1065
01:04:19,450 --> 01:04:25,910
gradi dinamične stvari, pisanje kode v jezikih, kot so PHP ali Python ali Ruby in Java ali C #.

1066
01:04:25,910 --> 01:04:30,360
Res, ne glede na vaš jezik izbire je in ustvarja HTML dinamično.

1067
01:04:30,360 --> 01:04:32,960
Ustvarjanje nekaj, kar ti CSS dinamično.

1068
01:04:32,960 --> 01:04:35,810
Cascading Style Sheets, ki je prav tako stvar estetike.

1069
01:04:35,810 --> 01:04:41,360
In tako, čeprav je danes, če grem na neki spletni strani, kot je znano Google.com,

1070
01:04:41,360 --> 01:04:46,100
in grem na ogled, razvijalec, pogled na vir, ki ste morda storili prej,

1071
01:04:46,100 --> 01:04:49,800
vendar pa bo za ogled vira, te stvari najbrž izgleda precej skrivnosten.

1072
01:04:49,800 --> 01:04:55,320
Ampak to je osnovno kodo, ki izvaja Google.com.

1073
01:04:55,320 --> 01:04:57,940
Na sprednjem koncu. In dejansko je vse to puhasto estetika stvari.

1074
01:04:57,940 --> 01:05:01,740
To je CSS tukaj. Če sem pomikajo navzdol bomo dobili nekaj barvnih kod stvari.

1075
01:05:01,740 --> 01:05:06,890
To je HTML. Koda Googlov izgleda kot zmešnjavo, ampak če bi dejansko odprl drugo okno,

1076
01:05:06,890 --> 01:05:09,380
smo lahko videli nekaj strukturo za to.

1077
01:05:09,380 --> 01:05:12,640
Če odprem tole, opazil sem, da je malo bolj berljiva.

1078
01:05:12,640 --> 01:05:16,850
Bomo videli kmalu to oznako, [beseda] je oznaka,

1079
01:05:16,850 --> 01:05:23,520
HTML, glava, telo, div, scenarij, besedilo območja, razpon, sredina, div.

1080
01:05:23,520 --> 01:05:26,770
In to je tudi nekako skrivnosten usmerjena na prvi pogled

1081
01:05:26,770 --> 01:05:30,890
ampak vse to zmešnjavo sledi določenim vzorcem in ponovljive vzorce,

1082
01:05:30,890 --> 01:05:33,850
tako da, ko smo dobili osnove navzdol, boste lahko, da napišete kodo, kot je ta

1083
01:05:33,850 --> 01:05:37,550
in potem manipulirati kodo, kot je ta z uporabo še enega jezika, ki se imenuje JavaScript.

1084
01:05:37,550 --> 01:05:40,440
In JavaScript je jezik, ki deluje znotraj brskalnika

1085
01:05:40,440 --> 01:05:44,380
danes, da bomo uporabili na Harvard tečajev, za orodje seveda nakupovanje, da Google maps uporablja

1086
01:05:44,380 --> 01:05:48,660
da vam cel kup dinamiko, Facebook vam daje prikaz takojšnje podatke o stanju,

1087
01:05:48,660 --> 01:05:51,430
Twitter ga uporablja, da vam pokažem tweets takoj.

1088
01:05:51,430 --> 01:05:53,820
Vse to bomo začeli sami potopi palca

1089
01:05:53,820 --> 01:05:57,190
Ampak do tja, moramo razumeti nekaj o internetu.

1090
01:05:57,190 --> 01:06:01,130
Ta posnetek sem le minuto časa, in predpostavimo, za zdaj je to v resnici,

1091
01:06:01,130 --> 01:06:08,380
kako internet deluje kot teaser za kaj kmalu prišel. Dam ti "Warriors mreže."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ ♫ Slow zbor glasbene]

1093
01:06:14,720 --> 01:06:20,450
[Moški pripovedovalec] je prišel s sporočilom.

1094
01:06:20,450 --> 01:06:23,770
S protokolom vse svoje lastne.

1095
01:06:23,770 --> 01:06:37,270
[♫ ♫ Hitrejše elektronske glasbe]

1096
01:06:37,270 --> 01:06:41,330
Prišel je na svet kul požarni zidovi, usmerjevalniki neskrbni,

1097
01:06:41,330 --> 01:06:45,690
in nevarnosti, če huje kot smrt.

1098
01:06:45,690 --> 01:06:55,400
On je hiter. On je močan. On je TCP / IP, in je dobil svoj naslov.

1099
01:06:55,400 --> 01:06:59,250
Bojevniki mreže.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Naslednji teden, potem. Internet. Spletno programiranje. To je CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]