1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [6 savaitė, Tęsinys]

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

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

4
00:00:08,720 --> 00:00:12,970
Tai CS50 ir tai yra 6 savaitės pabaigos.

5
00:00:12,970 --> 00:00:17,970
Taigi CS50x, vienas iš Harvardo universiteto pirmųjų kursuose dalyvaujančių EDX iniciatyva

6
00:00:17,970 --> 00:00:20,590
iš tikrųjų debiutavo praėjusį pirmadienį.

7
00:00:20,590 --> 00:00:23,460
Jei norėtumėte gauti, ką kiti žvilgsnis internete

8
00:00:23,460 --> 00:00:27,180
dabar po kartu su, jūs galite galvą į x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Kad bus nukreipti į tinkamą vietą edx.org

10
00:00:30,350 --> 00:00:34,160
kuris buvo, kai šį ir kitus kursus, iš MIT ir Berkeley dabar gyvena.

11
00:00:34,160 --> 00:00:38,140
Jūs turite užsiregistruoti sąskaitą, jūs rasite, kad medžiaga yra iš esmės tas pats

12
00:00:38,140 --> 00:00:42,170
kaip jūs jau šį pusmetį, nors per kelias savaites vėluoja, kaip mes gauti viskas paruošta.

13
00:00:42,170 --> 00:00:46,930
Bet tai, ką studentai CS50x dabar matome sąsaja labai patiko šį vieną.

14
00:00:46,930 --> 00:00:50,040
Tai, pavyzdžiui, yra Zamyla pirmaujančių 0 problemą, žingsnis po žingsnio.

15
00:00:50,040 --> 00:00:54,230
Po prisijungti į edx.org, CS50x studentas mato dalykų rūšių

16
00:00:54,230 --> 00:00:57,170
būtų galima tikėtis pamatyti kursą: pirmadienį paskaitą,

17
00:00:57,170 --> 00:01:01,650
paskaita trečiadienį, įvairių šortai, problema rinkiniai, Walkthroughs, PDF.

18
00:01:01,650 --> 00:01:04,459
Be to, kaip čia matote, mašininio vertimo

19
00:01:04,459 --> 00:01:08,390
iš anglų į kinų, japonų, ispanų, italų nuorašai,

20
00:01:08,390 --> 00:01:12,810
ir visa krūva kitų kalbų, kad tikrai bus netobulas

21
00:01:12,810 --> 00:01:15,840
kaip mes Roll juos programiškai naudojant kažką vadinama API

22
00:01:15,840 --> 00:01:18,360
arba taikomųjų programų programavimo sąsaja iš "Google"

23
00:01:18,360 --> 00:01:21,360
, kuri leidžia mums konvertuoti iš anglų į šių kalbų.

24
00:01:21,360 --> 00:01:24,100
Tačiau dėka į nuostabų dvasios maždaug šimtą plius savanorių,

25
00:01:24,100 --> 00:01:26,940
atsitiktinių žmonių internete, kurie maloniai pasiūlė įsitraukti

26
00:01:26,940 --> 00:01:30,180
šiame projekte, mes palaipsniui gerėja šių vertimų kokybę

27
00:01:30,180 --> 00:01:35,790
žmonės ištaisyti klaidas, kad padarė mūsų kompiuterius.

28
00:01:35,790 --> 00:01:42,330
>> Taigi paaiškėja, iš mes turėjo keletą daugiau studentų pasirodyti pirmadienį, nei mes iš pradžių tikėjomės.

29
00:01:42,330 --> 00:01:48,980
Iš tiesų, dabar CS50x turi 100.000 žmonių, kartu namuose.

30
00:01:48,980 --> 00:01:54,430
Taigi suprantate, jūs visi esate dalis įžanginė klasė šio kurso informatikos

31
00:01:54,430 --> 00:01:57,370
švietimo apskritai, o plačiau prieinama.

32
00:01:57,370 --> 00:02:00,130
O realybė yra dabar, su kai kuriais iš šių masinių internetinių kursų,

33
00:02:00,130 --> 00:02:04,070
jie visi pradėti su šiais labai daug, kaip mums atrodo, padarė čia.

34
00:02:04,070 --> 00:02:08,759
Bet tikslas, galų gale, CS50x tikrai gauti kuo daugiau žmonių į finišo liniją, kaip įmanoma.

35
00:02:08,759 --> 00:02:12,000
Konstrukcijos, CS50x bus siūlomi praeitą pirmadienį

36
00:02:12,000 --> 00:02:17,430
per 15 Bal 2013 būdas, kad žmonės, kurie mokyklos įsipareigojimus kitur,

37
00:02:17,430 --> 00:02:20,990
darbas, šeima, kiti konfliktai ir panašiai, turi šiek tiek daugiau lankstumo

38
00:02:20,990 --> 00:02:23,640
su kuriuo būtų galima pasinerti į šį kursą, kuris, pakanka pasakyti,

39
00:02:23,640 --> 00:02:30,540
gana ambicingai padaryti, jei tik per vos tris mėnesius per įprastą semestro metu.

40
00:02:30,540 --> 00:02:34,190
Tačiau šie studentai bus spręsti ta pati problema rinkinius, peržiūrėti tą patį turinį,

41
00:02:34,190 --> 00:02:36,350
turėti prieigą prie tų pačių šortai ir pan.

42
00:02:36,350 --> 00:02:38,990
Taigi suprasti, kad mes visi esame iš tikrųjų tai kartu.

43
00:02:38,990 --> 00:02:42,360
Ir vienas iš galutinių tikslų CS50x yra ne tik gauti kuo daugiau žmonės

44
00:02:42,360 --> 00:02:45,720
į finišo liniją ir suteikti jiems šį naujai atrastą suprasti kompiuterių mokslo

45
00:02:45,720 --> 00:02:49,000
ir programavimas, bet taip pat, kad jie turi šią dalijosi darbo patirtimi.

46
00:02:49,000 --> 00:02:52,010
Vienas iš apibūdinančių 50 miesteliu, tikimės,

47
00:02:52,010 --> 00:02:56,260
buvo tokios bendruomeninės patirties, geriau ar blogiau, kartais,

48
00:02:56,260 --> 00:02:59,480
bet šie žmonės pasukti į kairę ir į dešinę,

49
00:02:59,480 --> 00:03:01,830
ir darbo valandomis, ir hackathon ir teisingas.

50
00:03:01,830 --> 00:03:04,560
Tai šiek tiek sunkiau padaryti, kad asmeniui su žmonių internete,

51
00:03:04,560 --> 00:03:10,580
bet, CS50x bus baigtas balandžio pirmąjį CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
kuris bus interneto pritaikymas mūsų idėja teisinga

53
00:03:13,630 --> 00:03:18,250
kur šie tūkstančiai studentų, visi bus kviečiami pateikti 1 - 2 minučių trukmės vaizdo,

54
00:03:18,250 --> 00:03:22,480
arba jų galutinę projekto ar jų vaizdo Screencast garbanojimo Apie

55
00:03:22,480 --> 00:03:24,490
ir kalbėti apie savo projektą ir jį demoing

56
00:03:24,490 --> 00:03:27,610
panašiai kaip savo pirmtakų padarėme čia Campus mugėje

57
00:03:27,610 --> 00:03:31,400
kad iki semestro pabaigos, tikimasi turėti pasaulinę parodą

58
00:03:31,400 --> 00:03:37,080
studentų CS50x galutinių projektų, labai panaši į jus pasitiks šių metų gruodžio čia miesteliu.

59
00:03:37,080 --> 00:03:39,680
Taigi daugiau, kad per ateinančius mėnesius.

60
00:03:39,680 --> 00:03:43,640
>> Su 100.000 studentų, nors, ateina keletą KI.

61
00:03:43,640 --> 00:03:47,590
Atsižvelgiant į tai, kad jus vaikinai Blazing takas čia ir atsižvelgiant CS50

62
00:03:47,590 --> 00:03:51,630
kelias savaites iš anksto Ši medžiaga išleidimo žmonės dėl EDX,

63
00:03:51,630 --> 00:03:55,330
suprasti, mes norėtume įtraukti į šią iniciatyvą, nes daugelis iš mūsų pačių studentų, kaip įmanoma,

64
00:03:55,330 --> 00:03:58,720
tiek per pusmetį, taip pat šią žiemą ir šių metų pavasarį.

65
00:03:58,720 --> 00:04:01,620
Taigi, jei norite įsitraukti į CS50x,

66
00:04:01,620 --> 00:04:07,450
ypač prisijungs aptarti, CS50x CS50 aptarti EDX versija,

67
00:04:07,450 --> 00:04:10,140
kurį daugelis iš jūsų buvo naudojant miesteliu, internetinė skelbimų lenta,

68
00:04:10,140 --> 00:04:13,040
atlikite galvą į šį URL, leiskite mums žinoti, kas jūs esate,

69
00:04:13,040 --> 00:04:16,450
nes mes norėtume sukurti tiek studentų ir darbuotojų ir dėstytojų komanda

70
00:04:16,450 --> 00:04:19,630
su miesteliu, kurie tiesiog žaidžia kartu ir padėti.

71
00:04:19,630 --> 00:04:21,720
Ir kai jie mato klausimą, kad susipažinę su jų,

72
00:04:21,720 --> 00:04:25,320
išgirsite studentui apie kai kurių klaidų kažkur ten kai šalyje internete,

73
00:04:25,320 --> 00:04:27,450
ir kad žiedai varpas, nes jūs taip pat turėjo tą pačią problemą

74
00:04:27,450 --> 00:04:32,620
savo D-salėje prieš šiek tiek laiko, tikiuosi, tada galite varpelių ir pasidalinti savo patirtimi.

75
00:04:32,620 --> 00:04:37,300
Taigi, prašome dalyvauti, jei norite.

76
00:04:37,300 --> 00:04:39,360
>> Kompiuterių mokslo kursai Harvardo šiek tiek tradicija,

77
00:04:39,360 --> 00:04:44,730
CS50 tarp jų, šiek tiek drabužių, kai kurie drabužiai, kad jūs galite dėvėti išdidžiai

78
00:04:44,730 --> 00:04:49,090
semestrą pabaigoje, sakydamas gana išdidžiai, kad jūs baigėte CS50

79
00:04:49,090 --> 00:04:51,830
ir paėmė CS50 ir panašiai, ir mes visada stengiamės įtraukti studentus

80
00:04:51,830 --> 00:04:54,540
į šį procesą kaip įmanoma, pagal kurį mes kviečiame,

81
00:04:54,540 --> 00:04:56,900
apie šio semestro metu studentai turi pateikti dizainą

82
00:04:56,900 --> 00:04:59,330
naudojant Photoshop, ar kas pasirinkimo įrankis norite naudoti

83
00:04:59,330 --> 00:05:02,330
jei esate dizaineris, pateikti dizaino marškinėliai ir palaidinės

84
00:05:02,330 --> 00:05:06,100
ir skėčiai ir mažai spalvotos skarelės, šunims, dabar mes turime ir pan.

85
00:05:06,100 --> 00:05:09,370
Ir viskas tada - nugalėtojai kasmet eksponuojami

86
00:05:09,370 --> 00:05:12,700
aikštyno tinklalapyje store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Savikaina, ten viskas yra parduodama, bet svetainė tik veikia

88
00:05:15,790 --> 00:05:18,330
ir leidžia žmonėms pasirinkti spalvas ir dizainą, kad jiems patinka.

89
00:05:18,330 --> 00:05:20,420
Taigi, aš maniau, mes norime tiesiog pasidalinti kai praėjusių metų dizaino

90
00:05:20,420 --> 00:05:25,130
svetainėje be šio čia, kuris yra kasmetinė tradicija.

91
00:05:25,130 --> 00:05:29,410
"Kiekvieną dieną aš Sekundes Faultn" buvo vienas iš pateiktos pastabos ir pernai,

92
00:05:29,410 --> 00:05:32,290
kuri dar absolventai.

93
00:05:32,290 --> 00:05:35,820
Mes turėjome šį vieną, CS50, įkurta 1989 m. "

94
00:05:35,820 --> 00:05:39,010
Vienas iš mūsų Bowdens, Rob, praėjusiais metais buvo labai populiarus.

95
00:05:39,010 --> 00:05:43,480
"Komandos Bowden" gimė, šis projektas buvo pateiktas, tarp geriausių pardavėjų.

96
00:05:43,480 --> 00:05:49,040
Kaip buvo tai vienas čia. Daugelis žmonių turėjo "Bowden Fever" pagal pardavimo rąstų.

97
00:05:49,040 --> 00:05:52,650
Suprantu,, kad dabar gali būti jūsų projektas internete.

98
00:05:52,650 --> 00:05:57,510
Daugiau informacijos apie tai kitą problemą rinkiniai ateiti.

99
00:05:57,510 --> 00:06:00,330
>> Dar vienas įrankis: jūs turėjo tam tikrą poveikį ir, tikiuosi, dabar

100
00:06:00,330 --> 00:06:02,350
kai rankas ant patirtis su GDB,

101
00:06:02,350 --> 00:06:04,570
kuris, žinoma, Debugger ir leidžia manipuliuoti

102
00:06:04,570 --> 00:06:09,500
jūsų programa gana žemo lygio, daryti tai, ką rūšių dalykų?

103
00:06:09,500 --> 00:06:13,030
Ką GDB jums tai padaryti?

104
00:06:13,030 --> 00:06:15,030
Taip? Duoti man ką nors. [Studentų atsakymas, nesuprantamas]

105
00:06:15,030 --> 00:06:18,120
Geras. Žingsnis į funkciją, todėl jūs ne tik turėsite įrašyti paleisti

106
00:06:18,120 --> 00:06:22,310
ir per visą programos smūgį, spausdinimo iš dalykų, į standartinį išvedimą.

107
00:06:22,310 --> 00:06:25,190
Priešingai, jūs gali žingsnis, per jį linija, arba rašyti kitą

108
00:06:25,190 --> 00:06:30,300
eiti liniją kiekvieną eilutę po eilutės ar pakopą, pasinerti į funkciją, paprastai vienas, kad jūs rašė.

109
00:06:30,300 --> 00:06:35,240
Ką dar GDB jums tai padaryti? Taip? [Studentų atsakymas, nesuprantamas]

110
00:06:35,240 --> 00:06:38,100
Spausdinti kintamuosius. Taigi, jei norite padaryti šiek tiek savistaba viduje savo programą

111
00:06:38,100 --> 00:06:41,500
be imtis rašyti printf pareiškimus visur,

112
00:06:41,500 --> 00:06:44,600
galite tiesiog atspausdinti kintamojo arba rodyti kintamąjį.

113
00:06:44,600 --> 00:06:46,710
Ką dar galite daryti su kaip GDB debugger?

114
00:06:46,710 --> 00:06:49,170
[Studentų atsakymas, nesuprantamas]

115
00:06:49,170 --> 00:06:52,080
Tiksliai. Galite nustatyti ribines vertes; pertraukos vykdymą galite pasakyti

116
00:06:52,080 --> 00:06:54,020
pagrindinės funkcijos arba foo funkcija.

117
00:06:54,020 --> 00:06:56,800
Galite pasakyti, pertraukos vykdymą eilutėje 123.

118
00:06:56,800 --> 00:06:58,950
Ir atskaitos taškas yra tikrai galinga technika

119
00:06:58,950 --> 00:07:01,110
nes jei turite plačiąja prasme, kur jūsų problema

120
00:07:01,110 --> 00:07:05,360
tikriausiai yra, jūs neturite gaišti laiko žengia per programos visas.

121
00:07:05,360 --> 00:07:08,250
Galite iš esmės šokinėti teisę ten ir tada pradėkite rašyti

122
00:07:08,250 --> 00:07:10,970
žengia per jį žingsnis ar kitą arba panašūs.

123
00:07:10,970 --> 00:07:14,340
Bet su kažką panašaus GDB laimikis yra tai, kad jis padeda jums, žmogaus,

124
00:07:14,340 --> 00:07:16,940
rasti savo problemas ir rasti savo klaidas.

125
00:07:16,940 --> 00:07:19,470
Tai nebūtinai juos rasti tiek daug už jus.

126
00:07:19,470 --> 00:07:23,070
>> Taigi, mes pristatė kitą dieną style50, kuris yra trumpas komandų eilutės įrankis

127
00:07:23,070 --> 00:07:27,500
kad bando Stilizuoti savo kodą ir šiek tiek daugiau švariai, nei jūs, žmogaus, gali būti padaryta.

128
00:07:27,500 --> 00:07:29,530
Bet, taip pat, yra tikrai tik estetinis dalykas.

129
00:07:29,530 --> 00:07:34,110
Tačiau paaiškėja, ten tai įrankis, vadinamas Valgrind, kad yra šiek tiek daugiau paslaptingų naudoti.

130
00:07:34,110 --> 00:07:36,860
Pirmo žvilgsnio jos produkcija yra atrociously paslaptingas.

131
00:07:36,860 --> 00:07:39,420
Bet tai nuostabiai naudinga, ypač dabar, kad mes termino

132
00:07:39,420 --> 00:07:43,080
kur jūs pradedate naudoti malloc ir dinaminis atminties paskirstymas.

133
00:07:43,080 --> 00:07:45,420
Dalykai gali eiti tikrai, tikrai negerai greitai.

134
00:07:45,420 --> 00:07:49,320
Nes jei tu pamiršai išlaisvinti savo atmintį, arba šiek tiek dereference NULL žymiklį,

135
00:07:49,320 --> 00:07:55,770
ar jums dereference šiek tiek šiukšlių žymeklį, tai, kas paprastai yra simptomas, kad rezultatai?

136
00:07:55,770 --> 00:07:59,470
Seg kaltės. Ir gausite šį pagrindinį failą kai kilobaitų ir megabaitų

137
00:07:59,470 --> 00:08:02,990
, kuri atstovauja savo programos atminties būsena, kai jis sudužo,

138
00:08:02,990 --> 00:08:05,730
bet jūsų programa galiausiai seg gedimus, segmentavimo kaltės,

139
00:08:05,730 --> 00:08:08,450
, o tai reiškia, kažkas blogo atsitiko beveik visada yra susijusi

140
00:08:08,450 --> 00:08:11,750
atminties klaida, kad jūs padarėte kažkur.

141
00:08:11,750 --> 00:08:14,100
Taigi Valgrind padeda jums rasti dalykų, pavyzdžiui,.

142
00:08:14,100 --> 00:08:17,720
Tai priemonė, kuri leidžia paleisti, kaip GDB, kai jūs parengė savo programą,

143
00:08:17,720 --> 00:08:20,330
o kaip paleisti programą tiesiai, paleidus Valgrind

144
00:08:20,330 --> 00:08:23,960
ir jums pereiti į savo programą, kaip ir jūs su GDB.

145
00:08:23,960 --> 00:08:26,220
Dabar, naudojimas, siekiant gauti geriausią rūšies produkcijos,

146
00:08:26,220 --> 00:08:30,410
yra šiek tiek ilgai, todėl teisę ten ant ekrano jums pamatyti Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" reiškia beveik visuotinai vedant, kai jūs naudojate programas "Linux" kompiuteryje.

148
00:08:35,350 --> 00:08:38,770
Taigi, tai reiškia, kad išspjauti daugiau duomenų, nei galite pagal nutylėjimą.

149
00:08:38,770 --> 00:08:45,510
"- Nuotėkio = visas." Tai tiesiog pasakyti patikrinti visų galimų atminties nutekėjimas,

150
00:08:45,510 --> 00:08:49,430
klaidų, kad aš galėjo padaryti. Tai taip pat yra paplitusi paradigma su Linux programų.

151
00:08:49,430 --> 00:08:52,710
Apskritai, jei turite komandinės eilutės argumentas, kad "jungiklis"

152
00:08:52,710 --> 00:08:55,830
tai turėtų pakeisti programos elgesį, ir tai vienos raidės,

153
00:08:55,830 --> 00:09:00,310
tai-v, bet jei, įjungiama, tiesiog dizaino programuotojas,

154
00:09:00,310 --> 00:09:05,150
yra visą žodį arba žodžių seka, komandinės eilutės argumentas prasideda.

155
00:09:05,150 --> 00:09:08,190
Tai tik žmogaus konvencijas, bet pamatysite juos vis labiau.

156
00:09:08,190 --> 00:09:12,410
Ir tada, pagaliau, "a.out" yra savavališkai Šiame konkrečiame pavyzdyje programos pavadinimas.

157
00:09:12,410 --> 00:09:14,640
Ir štai kai atstovas produkcija.

158
00:09:14,640 --> 00:09:22,890
>> Prieš mes pažvelgsime, ką tai gali reikšti, kad, leiskite man pereiti prie kodo fragmentą, per čia.

159
00:09:22,890 --> 00:09:26,390
Ir leiskite man perkelti šią iš kelio, netrukus

160
00:09:26,390 --> 00:09:32,120
ir galime imtis kambarį memory.c, kuri yra tai trumpas pavyzdys čia atrodo.

161
00:09:32,120 --> 00:09:36,290
Taigi, leiskite man šioje programoje priartinti funkcijų ir klausimus.

162
00:09:36,290 --> 00:09:39,430
Mes turime pagrindinę funkciją, kad vadina funkciją, f,

163
00:09:39,430 --> 00:09:45,590
ir kas tada f tęsti padaryti, šiek tiek techninės anglų?

164
00:09:45,590 --> 00:09:49,760
Ką f pradėti daryti?

165
00:09:49,760 --> 00:09:53,680
Kaip apie pradėsite su 20 eilutėje, ir žvaigždės vieta nesvarbu,

166
00:09:53,680 --> 00:09:56,720
bet aš tiesiog būti suderintos su praėjusiais paskaitą.

167
00:09:56,720 --> 00:09:59,910
, Kas 20 eilutėje už mus? Kairėje pusėje. Mes ją padalyti toliau.

168
00:09:59,910 --> 00:10:02,410
Int * x: ką daryti?

169
00:10:02,410 --> 00:10:04,940
Gerai. Tai skelbiantis žymeklis, ir dabar galime būti dar labiau techninio pobūdžio.

170
00:10:04,940 --> 00:10:10,230
Ką tai reiškia, labai konkrečiai, paskelbti rodyklę? Kažkas kitas?

171
00:10:10,230 --> 00:10:15,050
Taip? [Studento atsakymas, nesuprantamas] per toli.

172
00:10:15,050 --> 00:10:17,060
Taigi jūs skaitote dešinėje lygybės ženklą.

173
00:10:17,060 --> 00:10:20,290
Sutelkime tik kairėje pusėje, tiesiog int * x.

174
00:10:20,290 --> 00:10:24,700
Tai reiškia "paskelbti" rodyklę, bet dabar galime pasinerti giliau į šį apibrėžimą.

175
00:10:24,700 --> 00:10:28,330
Ką tai konkrečiai, techniškai reiškia? Taip?

176
00:10:28,330 --> 00:10:31,940
[Studentų atsakymas, nesuprantamas]

177
00:10:31,940 --> 00:10:35,090
Gerai. Jis ruošiasi įrašyti adresą atmintyje.

178
00:10:35,090 --> 00:10:40,680
Geras. Ir Paimkime vieną žingsnį toliau, tai deklaruojant kintamąjį x, tai 32 bitai.

179
00:10:40,680 --> 00:10:44,440
Ir aš žinau, tai 32 bitų, nes?

180
00:10:44,440 --> 00:10:47,390
Tai ne todėl, kad int, nes tai, kad šiuo atveju rodyklė.

181
00:10:47,390 --> 00:10:49,650
Sutapimas, kad tai vienas ir tas pats su int

182
00:10:49,650 --> 00:10:51,970
bet faktas, kad yra žvaigždė reiškia, kad tai rodyklė

183
00:10:51,970 --> 00:10:57,300
ir į prietaisą, su daug kompiuterių, bet ne visi, patarimų yra 32 bitai.

184
00:10:57,300 --> 00:11:01,850
Moderni įranga, pavyzdžiui, naujausias "Mac", naujausi kompiuteriai, jūs galite turėti 64-bitų patarimų,

185
00:11:01,850 --> 00:11:04,160
bet į prietaisą, šie dalykai yra 32 bitai.

186
00:11:04,160 --> 00:11:08,380
Taigi mes standartizuoti, kad. Konkrečiau, sakoma taip:

187
00:11:08,380 --> 00:11:10,820
Mes "paskelbti" rodyklę, ką tai reiškia?

188
00:11:10,820 --> 00:11:12,810
Mes ruošiame saugoti atminties adresą.

189
00:11:12,810 --> 00:11:15,530
Ką tai reiškia?

190
00:11:15,530 --> 00:11:19,810
Mes sukurti kintamą vadinama X, kuri užima 32 bitus

191
00:11:19,810 --> 00:11:23,810
kad netrukus saugoti sveikasis skaičius adresą.

192
00:11:23,810 --> 00:11:26,470
Ir tai tikriausiai taip tiksliai, kaip mes galime gauti.

193
00:11:26,470 --> 00:11:31,810
Tai gerai, judėti į priekį supaprastinti pasaulį ir tiesiog pasakyti paskelbti žymeklį vadinama X.

194
00:11:31,810 --> 00:11:35,380
Paskelbti žymeklį, tačiau suvokti ir suprasti, kas iš tikrųjų vyksta

195
00:11:35,380 --> 00:11:38,490
net tik tuos keletą simbolių.

196
00:11:38,490 --> 00:11:42,040
>> Dabar, tai vienas beveik šiek tiek lengviau, nors tai ilgiau išraiška.

197
00:11:42,040 --> 00:11:48,160
Taigi, kas tai daro, kad dabar bus paryškinta: "malloc (10 * sizeof (int));" Taip?

198
00:11:48,160 --> 00:11:52,350
[Studentų atsakymas, nesuprantamas]

199
00:11:52,350 --> 00:11:58,250
Geras. Imsiu jį ten. Tai skiriant dešimt sveikųjų skaičių iš atminties riekė.

200
00:11:58,250 --> 00:12:02,190
O dabar leisk pasinerti šiek tiek giliau, tai skiriant dešimt sveikųjų skaičių atminties riekė.

201
00:12:02,190 --> 00:12:05,390
Kas yra malloc tada grįžti?

202
00:12:05,390 --> 00:12:10,390
Tos riekė adresas, arba, konkrečiau, tos riekė pirmojo baito adresas.

203
00:12:10,390 --> 00:12:14,080
Kaip tada aš, programuotojas, žinoti, kur riekė, kad atminties baigiasi?

204
00:12:14,080 --> 00:12:18,340
Žinau, kad tai gretutinė. Malloc, pagal apibrėžimą, duos jums vientisą atminties riekė.

205
00:12:18,340 --> 00:12:21,240
Nėra spragų. Jūs turite prieigą prie kiekvieno toje riekė baitas,

206
00:12:21,240 --> 00:12:26,760
atgal atgal atgal, bet kaip man žinoti, kur šios atminties riekė pabaiga?

207
00:12:26,760 --> 00:12:28,850
Kai naudojate malloc? [Studento atsakymas, nesuprantamas] Geras.

208
00:12:28,850 --> 00:12:30,670
Jūs neturite. Jūs turite prisiminti.

209
00:12:30,670 --> 00:12:35,960
Turiu prisiminti, kad aš vertę 10, o aš net atrodo, padarė, kad čia.

210
00:12:35,960 --> 00:12:41,000
Bet pareiga yra tik ant manęs. Strlen, kurį mes jau šiek tiek priklauso nuo stygos,

211
00:12:41,000 --> 00:12:45,860
veikia tik todėl, kad šios konvencijos \ 0

212
00:12:45,860 --> 00:12:48,840
ar šis specialus nul charakteris, NUL, eilutės pabaigoje.

213
00:12:48,840 --> 00:12:51,740
Kad neturi tik savavališkai gabaliukus atmintimi.

214
00:12:51,740 --> 00:12:58,590
Tai priklauso nuo jūsų. Taigi, 20 eilutėje, tada skiria atminties riekė

215
00:12:58,590 --> 00:13:02,590
kad galima laikyti dešimt sveikieji skaičiai, ir ji saugo pirmojo baito adresas

216
00:13:02,590 --> 00:13:05,610
tos atminties kintamojo vadinama X riekė.

217
00:13:05,610 --> 00:13:11,140
Ergo, kuris yra rodyklė. Taigi eilutę 21, deja, buvo klaida.

218
00:13:11,140 --> 00:13:16,110
Bet pirmiausia, kas tai daro? Tai sakydamas, 10, 0 indeksuojami buvimo vietos parduotuvėje,

219
00:13:16,110 --> 00:13:19,480
atminties riekė, x vertė 0.

220
00:13:19,480 --> 00:13:21,510
>> Taigi pastebėti keletą dalykų vyksta.

221
00:13:21,510 --> 00:13:25,420
Net jei x yra rodyklė, prisiminti iš prieš porą savaičių

222
00:13:25,420 --> 00:13:29,440
, kad jūs vis dar galite naudoti masyvo stiliaus kvadratinių laikiklis žymėjimą.

223
00:13:29,440 --> 00:13:36,180
, Nes tai iš tikrųjų labiau paslaptingas orientuotą rodyklių aritmetinis trumpas ranka notacijos.

224
00:13:36,180 --> 00:13:40,320
kur mes padaryti kažką panašaus į tai: Paimkite adresų x perkelti 10 Dėmelės

225
00:13:40,320 --> 00:13:44,550
tada ten kokia adresas yra saugomas toje vietoje.

226
00:13:44,550 --> 00:13:48,090
Bet atvirai, tai tik žiaurią skaityti ir gauti patogiai.

227
00:13:48,090 --> 00:13:52,900
Taigi pasaulis paprastai naudoja skliaustus, tik todėl, kad tiek daug daugiau žmonių draugiškas.

228
00:13:52,900 --> 00:13:55,140
Bet tai, kas iš tikrųjų vyksta po gaubtu;

229
00:13:55,140 --> 00:13:58,190
x yra adresas, masyvas, per se.

230
00:13:58,190 --> 00:14:02,410
Todėl tai saugoti 0 x 10 vietą.

231
00:14:02,410 --> 00:14:06,120
Kodėl tai yra blogai? Taip?

232
00:14:06,120 --> 00:14:17,370
[Studento atsakymas, nesuprantamas] Būtent.

233
00:14:17,370 --> 00:14:21,100
Mes tik skyrė dešimt int, bet mes skaičiuojame nuo 0, kai Programming in C,

234
00:14:21,100 --> 00:14:25,690
todėl jūs turite prieigą prie 0 1 2 3 4 5 6 7 8 9, bet ne 10.

235
00:14:25,690 --> 00:14:30,270
Taigi, arba programa seg kaltės ar tai ne.

236
00:14:30,270 --> 00:14:32,900
Bet mes ne tikrai žinote, tai yra tarsi iš niezdeterminowane elgesį.

237
00:14:32,900 --> 00:14:35,600
Tai tikrai priklauso nuo to, ar mes pasisekė.

238
00:14:35,600 --> 00:14:40,650
Jei paaiškėja, kad operacinė sistema neturi proto, jei aš naudoju, kad papildomų baitas,

239
00:14:40,650 --> 00:14:43,360
, nors ji nedavė man, mano programa gali strigti.

240
00:14:43,360 --> 00:14:46,780
Tai žalias, tai Buggy, bet jūs negalite matyti, kad simptomas,

241
00:14:46,780 --> 00:14:48,960
arba jūs galite pamatyti tik vieną kartą, o.

242
00:14:48,960 --> 00:14:51,230
Tačiau tikrovė yra tokia, kad problema yra, iš tikrųjų, yra.

243
00:14:51,230 --> 00:14:54,320
Ir tai tikrai problema, jei jūs parašiau programą, kurią norite būti teisinga,

244
00:14:54,320 --> 00:14:58,840
kad jūs pardavė programą, kad žmonės naudojasi, kad kiekvieną kartą, o sugenda

245
00:14:58,840 --> 00:15:02,450
nes, žinoma, tai nėra gerai. Iš tiesų, jei turite "Android" telefoną ar "iPhone"

246
00:15:02,450 --> 00:15:05,550
ir jums atsisiųsti programas šių dienų, jei jūs kada nors turėjo app tiesiog mesti,

247
00:15:05,550 --> 00:15:10,040
visi staiga ji išnyksta, tai beveik visada kai kurių atminties susijusiu klausimu,

248
00:15:10,040 --> 00:15:12,830
, kurią programuotojas įsukus ir dereferenced rodyklę

249
00:15:12,830 --> 00:15:18,670
, kad jis neturėtų, ir iOS arba Android rezultatas yra tiesiog viso nužudyti programą

250
00:15:18,670 --> 00:15:23,080
o ne rizikos neapibrėžtas elgesio ar kažkokia Įsibrovimo.

251
00:15:23,080 --> 00:15:25,950
>> Yra viena kita klaida šioje programoje, ne tik šį vieną.

252
00:15:25,950 --> 00:15:30,180
Ką dar aš įsukus šioje programoje?

253
00:15:30,180 --> 00:15:32,740
Aš ne praktikuojama, ką aš pamokslavo. Taip?

254
00:15:32,740 --> 00:15:34,760
[Studento atsakymas, nesuprantamas] Geras.

255
00:15:34,760 --> 00:15:36,880
Aš ne išlaisvino atmintį. Taigi nykščio taisykle dabar

256
00:15:36,880 --> 00:15:43,150
turi būti, kada jūs vadinate malloc, turite skambinti nemokamai, kai baigsite, naudojant šią atmintį.

257
00:15:43,150 --> 00:15:45,610
Dabar, kai aš noriu išlaisvinti šią atmintį?

258
00:15:45,610 --> 00:15:49,780
Tikriausiai, darant prielaidą, kad pirmoji eilutė buvo teisinga, aš norėtų tai padaryti čia.

259
00:15:49,780 --> 00:15:55,710
Nes aš negalėjau, pavyzdžiui, padaryti jį žemyn. Kodėl?

260
00:15:55,710 --> 00:15:57,860
Tik iš taikymo srities. Taigi, nors mes kalbame apie rodykles,

261
00:15:57,860 --> 00:16:04,830
tai per savaitę, 2 ar 3 klausimas, kur x yra tik savo apimtimi, viduje, kur ji buvo paskelbta Garbanotasis petnešos.

262
00:16:04,830 --> 00:16:11,000
Taigi, jūs tikrai negali išlaisvinti jį ten. Mano vienintelis šansas išlaisvinti yra maždaug po eilutę 21.

263
00:16:11,000 --> 00:16:15,170
Tai yra gana paprasta programa, tai buvo gana lengva, kai jūs rūšies suvynioti savo mintis

264
00:16:15,170 --> 00:16:17,870
apie tai, ką programa daro, kur klaidas.

265
00:16:17,870 --> 00:16:20,500
Ir net jei jums nebuvo matyti ne pirmas, tikiuosi, ji šiek tiek akivaizdu dabar

266
00:16:20,500 --> 00:16:23,870
kad šios klaidos yra gana lengvai išsprendžiama ir lengvai.

267
00:16:23,870 --> 00:16:28,720
Bet, kai programa yra daugiau nei 12 eilučių ilgio, tai 50 eilučių ilgio, 100 eilučių ilgio,

268
00:16:28,720 --> 00:16:31,150
vaikščioti per savo kodo eilutę po eilutės, galvoju per ją logiškai,

269
00:16:31,150 --> 00:16:35,110
yra įmanoma, tačiau ne itin smagu daryti, nuolat ieško už klaidas,

270
00:16:35,110 --> 00:16:38,340
ir tai taip pat sunku padaryti, ir tai, kodėl, kaip Valgrind įrankis.

271
00:16:38,340 --> 00:16:40,900
Leiskite man eiti į priekį ir tai padaryti: leiskite man atidaryti savo terminalo langą,

272
00:16:40,900 --> 00:16:45,400
ir neleisk man tiesiog paleisti atminties, nes visa atmintis atrodo gerai.

273
00:16:45,400 --> 00:16:49,180
Gaunu pasisekė. Ėjimas į tą papildomą baitą masyvo pabaigos

274
00:16:49,180 --> 00:16:51,060
neatrodo, kad pernelyg sudėtinga.

275
00:16:51,060 --> 00:16:56,370
Bet vis dėlto, leiskite man padaryti normalumas patikrinti, kuris tiesiog reiškia, patikrinti

276
00:16:56,370 --> 00:16:58,320
, ar iš tikrųjų tai yra teisinga.

277
00:16:58,320 --> 00:17:04,690
>> Taigi darykime Valgrind-v - nuotėkio patikrinti = visas,

278
00:17:04,690 --> 00:17:07,520
ir tada šiuo atveju programos pavadinimas yra atmintyje, o ne a.out.

279
00:17:07,520 --> 00:17:10,760
Taigi leiskite man eiti į priekį ir tai padaryti. Paspauskite Enter.

280
00:17:10,760 --> 00:17:14,109
Brangus Dieve. Tai jos produkcija, ir tai, ką aš užsiminiau anksčiau.

281
00:17:14,109 --> 00:17:17,550
Tačiau, jei jūs išmoksite skaityti čia per nesąmonė,

282
00:17:17,550 --> 00:17:20,760
dažniausiai tai yra tiesiog diagnostikos produkcija, tai ne, kad įdomu.

283
00:17:20,760 --> 00:17:24,829
Kokios reikia jūsų akiai tikrai nori būti ieškote yra kokia nors klaida arba neteisingas paminėti.

284
00:17:24,829 --> 00:17:26,800
Žodžiai, rodančių problemas.

285
00:17:26,800 --> 00:17:29,340
Ir iš tiesų, galime pamatyti, kas vyksta neteisingai žemyn čia.

286
00:17:29,340 --> 00:17:35,230
Turiu tam tikros rūšies santrauką, "naudojant išvežimo. 40 baitų 1 blokus"

287
00:17:35,230 --> 00:17:38,750
Aš tikrai ne tikras, ką blokas dar, bet 40 baitų

288
00:17:38,750 --> 00:17:41,260
iš tikrųjų mano, kaip aš galėtų išsiaiškinti, kur, kad ateina iš.

289
00:17:41,260 --> 00:17:45,030
40 baitų. Kodėl 40 baitų išvežimo naudojimui?

290
00:17:45,030 --> 00:17:48,780
O tiksliau, jei mes slinkti žemyn čia,

291
00:17:48,780 --> 00:17:54,520
kodėl aš tikrai prarado 40 baitų? Taip?

292
00:17:54,520 --> 00:17:59,520
[Studento atsakymas, nesuprantamas] Perfect. Taip, tiksliai.

293
00:17:59,520 --> 00:18:03,540
Ten buvo dešimt sveikieji skaičiai, o kiekvienas iš jų yra dydis 4, arba 32 bitų,

294
00:18:03,540 --> 00:18:08,300
todėl Pamečiau arba neatsimenu tiksliai 40 baitų, nes, kaip siūloma, aš ne vadinamų laisvaisiais.

295
00:18:08,300 --> 00:18:13,460
Kad viena klaida, o dabar pažvelkime šiek tiek žemyn, toliau ir pamatyti šalia,

296
00:18:13,460 --> 00:18:16,900
"Negalioja rašyti 4 dydžio." Dabar kas tai yra?

297
00:18:16,900 --> 00:18:21,150
Šis adresas yra išreiškiamas kokie atskaitos notacijos, matyt?

298
00:18:21,150 --> 00:18:23,640
Tai yra šešioliktainis, ir, bet kuriuo metu galite pamatyti skaičių pradedant 0x,

299
00:18:23,640 --> 00:18:29,410
tai reiškia, šešioliktainis, kuriems mes radome kelią atgal, manau, klausimų pset 0 skyriuje,

300
00:18:29,410 --> 00:18:34,090
kuris buvo tiesiog padaryti WarmUp naudotis, konvertuoti dešimtainės į šešioliktainį į dvejetainį ir pan.

301
00:18:34,090 --> 00:18:39,220
Šešioliktainis, tiesiog žmogaus konvencijos, paprastai naudojamas atstovauti patarimų

302
00:18:39,220 --> 00:18:41,570
arba, apskritai, adresus. Tai tik konvencija,

303
00:18:41,570 --> 00:18:45,340
, nes tai šiek tiek lengviau skaityti, tai šiek tiek daugiau kompaktiškas nei kažką panašaus dešimtosios,

304
00:18:45,340 --> 00:18:47,720
ir dvejetainiai dauguma žmonių yra nenaudingas naudoti.

305
00:18:47,720 --> 00:18:50,840
Taigi, dabar, ką tai reiškia? Na, atrodo, kad yra neteisingas rašyti

306
00:18:50,840 --> 00:18:54,480
dėl memory.c 21 eilutėje 4 dydžio.

307
00:18:54,480 --> 00:18:59,180
Taigi, grįžkime į eilutę 21, ir iš tikrųjų, čia yra tai, kad neteisingas rašyti.

308
00:18:59,180 --> 00:19:02,640
Taigi Valgrind nesiruošia turėti savo ranką ir pasakykite man, ką nustatyti yra

309
00:19:02,640 --> 00:19:05,520
tačiau ji aptinka, kad aš darau neteisingą rašyti.

310
00:19:05,520 --> 00:19:08,800
Aš neliesti 4 baitai, kad aš ne, ir, matyt, tai todėl, kad,

311
00:19:08,800 --> 00:19:13,960
kaip Jūs nurodėte, aš darau, o ne [9] [10] maksimaliai

312
00:19:13,960 --> 00:19:16,660
[0] ar kažkas tarp.

313
00:19:16,660 --> 00:19:19,690
Su Valgrind, supranta, kad bet kuriuo metu, jūs dabar rašymo programą

314
00:19:19,690 --> 00:19:24,190
, kuri naudoja patarimų ir naudoja atmintį ir malloc tiksliau,

315
00:19:24,190 --> 00:19:27,080
tikrai gauti į įpročiai veikia ši ilgai

316
00:19:27,080 --> 00:19:30,890
bet labai lengvai nukopijuoti ir įklijuoti vadovavimą Valgrind

317
00:19:30,890 --> 00:19:32,650
norėdami pamatyti, jei yra keletas klaidų, ten.

318
00:19:32,650 --> 00:19:34,820
Ir tai bus didele kiekvieną kartą pamatysite produkcijos,

319
00:19:34,820 --> 00:19:39,430
bet tik išanalizuoti per vizualiai visos produkcijos, ir pamatyti, jei jūs matote mini klaidų

320
00:19:39,430 --> 00:19:43,190
ar įspėjimus arba neteisingas arba prarasti.

321
00:19:43,190 --> 00:19:46,200
Bet kurie žodžiai atrodykite, kad jūs įsukus kažkur.

322
00:19:46,200 --> 00:19:48,580
Taip suprasti, kad yra nauja priemonė, savo priemonių rinkinį.

323
00:19:48,580 --> 00:19:51,270
>> Dabar pirmadienį, mes turėjome visa krūva žmonių sugalvoti čia

324
00:19:51,270 --> 00:19:53,150
ir atstovauja susietą sąrašą sąvoką.

325
00:19:53,150 --> 00:20:00,970
Ir mes pristatė susietą sąrašą kaip išspręsti kokia problema?

326
00:20:00,970 --> 00:20:04,590
Taip? [Studento atsakymas, nesuprantamas] Geras.

327
00:20:04,590 --> 00:20:06,530
Matricos negali turėti atminties prie jų pridėti.

328
00:20:06,530 --> 00:20:09,440
Jei jums skirti, dydis 10, tai visi jums masyvo.

329
00:20:09,440 --> 00:20:13,690
Galite skambinti, jei jūs iš pradžių malloc kaip realloc funkciją,

330
00:20:13,690 --> 00:20:17,580
ir kad gali bandyti augti masyvas, jei yra vietos link jo pabaigos

331
00:20:17,580 --> 00:20:21,610
, kad niekas kitas naudoja, o jei jų nėra, tai bus tiesiog rasti jums didesnį gabalą kažkur kitur.

332
00:20:21,610 --> 00:20:25,040
Bet tada ji bus nukopijuoti visi iš tų baitų į naują masyvą.

333
00:20:25,040 --> 00:20:28,310
Tai skamba kaip labai teisingą sprendimą.

334
00:20:28,310 --> 00:20:34,790
Kodėl tai yra nepatraukli?

335
00:20:34,790 --> 00:20:36,940
Aš turiu galvoje, tai veikia, žmonės išsprendė šią problemą.

336
00:20:36,940 --> 00:20:40,710
Kodėl mes turime ją išspręsti Pirmadienį, susijusius sąrašus? Taip?

337
00:20:40,710 --> 00:20:44,060
[Studentų atsakymas, nesuprantamas] Tai gali užtrukti ilgą laiką.

338
00:20:44,060 --> 00:20:49,260
Iš tiesų, bet kuriuo metu, jūs skambinate malloc arba realloc arba calloc, kuris yra dar vienas,

339
00:20:49,260 --> 00:20:52,470
bet kada, programa, kalbame su operacine sistema,

340
00:20:52,470 --> 00:20:54,310
jūs linkę sulėtinti programą.

341
00:20:54,310 --> 00:20:57,470
Ir jei jūs darote šių dalykų kilpų rūšių, jūs tikrai lėtėja dalykų žemyn.

342
00:20:57,470 --> 00:21:00,740
Jūs esate nesiruošia pastebėti tai paprasčiausias "Hello World" tipo programomis,

343
00:21:00,740 --> 00:21:04,300
bet daug didesnių programų, prašydami operacinę sistemą iš naujo ir vėl iš atminties

344
00:21:04,300 --> 00:21:07,520
arba suteikiant jai vėl ir vėl, paprastai negali būti geras dalykas.

345
00:21:07,520 --> 00:21:11,210
Be to, tai tiesiog tarsi intelekto - tai visiškas laiko švaistymas.

346
00:21:11,210 --> 00:21:16,490
Kodėl reikia skirti vis daugiau ir daugiau atminties, rizikos kopijuoti viską į naują masyvo,

347
00:21:16,490 --> 00:21:21,980
jei turite alternatyvą, kuri leidžia jums skiria tik tiek, kiek atminties, kaip jūs iš tikrųjų reikia?

348
00:21:21,980 --> 00:21:24,130
Todėl nėra čia pliusų ir minusų.

349
00:21:24,130 --> 00:21:26,730
Vienas iš pliusų yra tai, kad mes turime dinamiškumą.

350
00:21:26,730 --> 00:21:29,100
Nesvarbu, kur atminties gabaliukus, kurie yra laisvi,

351
00:21:29,100 --> 00:21:32,070
Aš galiu tik rūšiuoti sukurti šių duonos trupinius per rodykles

352
00:21:32,070 --> 00:21:34,470
styginių visą mano susietą sąrašą kartu.

353
00:21:34,470 --> 00:21:36,470
Bet aš mokėti bent vieną kainą.

354
00:21:36,470 --> 00:21:40,060
>> Ką aš turiu mesti įgyti, susijusius sąrašus?

355
00:21:40,060 --> 00:21:42,470
Taip? [Studento atsakymas, nesuprantamas] Geras.

356
00:21:42,470 --> 00:21:45,650
Jums reikia daugiau atminties. Dabar man reikia erdvės šiuos patarimus,

357
00:21:45,650 --> 00:21:47,900
ir šio super paprasta susijęs sąrašą

358
00:21:47,900 --> 00:21:51,410
kad tik bando laikyti sveikieji skaičiai, kurie yra 4 baitų, mes nuolat sako

359
00:21:51,410 --> 00:21:54,240
gerai, rodyklė yra 4 baitų, todėl dabar aš tiesiog dvigubai

360
00:21:54,240 --> 00:21:57,290
atminties kiekis man reikia tiesiog išsaugoti šį sąrašą.

361
00:21:57,290 --> 00:21:59,680
Bet vėl, tai yra nuolatinis kompromisas kompiuterių mokslo

362
00:21:59,680 --> 00:22:03,440
tarp laiko ir erdvės požiūriu plėtros, pastangų ir kitų išteklių.

363
00:22:03,440 --> 00:22:06,630
Kaip dar naudojant susietą sąrašą neigiama? Taip?

364
00:22:06,630 --> 00:22:10,150
[Studentų atsakymas, nesuprantamas]

365
00:22:10,150 --> 00:22:12,600
Geras. Ne taip lengva naudotis. Mes nebegalime sverto

366
00:22:12,600 --> 00:22:15,530
savaitę 0 principus kaip skaldyk ir valdyk.

367
00:22:15,530 --> 00:22:18,220
O tiksliau, dvejetainis paieškos. Nes, nors mes, žmonės

368
00:22:18,220 --> 00:22:20,400
galite pamatyti maždaug, kur šio sąrašo viduryje yra,

369
00:22:20,400 --> 00:22:25,840
kompiuteris tik žino, kad šis sąrašas prasideda adresu vadinama pirmoji.

370
00:22:25,840 --> 00:22:28,250
Ir kad 0x123 ar kažkas panašaus.

371
00:22:28,250 --> 00:22:30,990
Ir vienintelis būdas programa gali rasti vidurinį elementą

372
00:22:30,990 --> 00:22:33,350
yra iš tikrųjų ieškoti visą sąrašą.

373
00:22:33,350 --> 00:22:35,500
Ir net tada, jis tiesiog turi ieškoti visą sąrašą, nes

374
00:22:35,500 --> 00:22:38,950
net kai jūs pasieksite vidurinįjį elementą, po patarimų,

375
00:22:38,950 --> 00:22:42,380
jūs, programa, neįsivaizduoju, kiek laiko šis sąrašas, gali,

376
00:22:42,380 --> 00:22:45,250
kol paspausite jo pabaigoje, ir kaip jūs žinote, programiškai

377
00:22:45,250 --> 00:22:48,600
, kad esate tuo susietą sąrašo pabaigoje?

378
00:22:48,600 --> 00:22:51,120
NULL pointeris yra speciali, todėl vėl konvencija.

379
00:22:51,120 --> 00:22:53,870
O ne naudoti šį žymeklį, mes tikrai nenori būti šiek tiek šiukšlių vertė

380
00:22:53,870 --> 00:22:57,750
nukreipta nuo scenos kažkur, mes norime, kad ji būtų ranka žemyn, NULL,

381
00:22:57,750 --> 00:23:01,530
kad mes turime šį terminus šios duomenų struktūros, todėl mes žinome, kur jis baigiasi.

382
00:23:01,530 --> 00:23:03,410
>> Ką daryti, jei norime valdyti?

383
00:23:03,410 --> 00:23:05,980
Šį vizualiai mes padarėme, ir su žmonėmis,

384
00:23:05,980 --> 00:23:07,630
bet ką daryti, jei mes norime padaryti įterpties?

385
00:23:07,630 --> 00:23:12,360
Taigi pradinis sąrašas buvo 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Ką daryti, jei po to mes norėjome malloc erdvėje skaičius 55, už tai mazgo,

387
00:23:16,730 --> 00:23:20,730
, tai mes norime įterpti į sąrašą, tiesiog, kaip mes padarėme, pirmadienį 55?

388
00:23:20,730 --> 00:23:23,690
Kaip mes tai darome? Na, Anita atėjo ir ji iš esmės vaikščiojo sąrašą.

389
00:23:23,690 --> 00:23:27,500
Ji pradėjo pirmąjį elementą, tada kitas, kitas, kitas, kitas, kitas.

390
00:23:27,500 --> 00:23:29,500
Pagaliau paspauskite kairįjį visą kelią žemyn

391
00:23:29,500 --> 00:23:34,480
ir supratau, oh, tai yra NULL. Taigi, kas rodyklė manipuliacija reikia padaryti?

392
00:23:34,480 --> 00:23:37,980
Asmuo, kuris buvo pabaigos, tačiau skaičius 34, reikia jo kaire ranka iškėlė

393
00:23:37,980 --> 00:23:46,220
taško, esančio 55, 55 reikia savo kairę ranką žemyn nukreiptą bus naujas NULL terminatorius. Atlikta.

394
00:23:46,220 --> 00:23:49,540
Gana lengva įterpti 55 į rūšiuotų sąrašą.

395
00:23:49,540 --> 00:23:51,800
Ir kaip tai galėtų atrodyti?

396
00:23:51,800 --> 00:23:55,690
>> Leiskite man eiti į priekį ir atverti šiek tiek kodo pavyzdį čia.

397
00:23:55,690 --> 00:23:58,120
Aš atverti gedit ir leiskite man atidaryti du failus pirmą kartą.

398
00:23:58,120 --> 00:24:02,050
Vienas iš jų yra list1.h, ir leiskite man tiesiog priminti, kad tai buvo kodo riekė

399
00:24:02,050 --> 00:24:04,920
kad mes naudojamas atstovauti mazgas.

400
00:24:04,920 --> 00:24:13,040
Mazgas turi tiek int vadinamos N ir rodyklę, pavadintą kitą, kad tik taškai į kitą dalyką sąraše.

401
00:24:13,040 --> 00:24:15,450
Kad dabar yra H failo. Kodėl?

402
00:24:15,450 --> 00:24:19,090
Ši konvencija, ir mes iki šiol nepasinaudojo tai didžiulis patys,

403
00:24:19,090 --> 00:24:22,220
bet tas, kas rašė printf ir kitas funkcijas

404
00:24:22,220 --> 00:24:27,150
davė kaip dovaną į pasaulį iš šių funkcijų raštu failą pavadinimu stdio.h.

405
00:24:27,150 --> 00:24:30,950
Ir tada ten string.h ir tada ten map.h, ir ten visi šie h failai

406
00:24:30,950 --> 00:24:34,410
, kad jūs galėjote pastebėti ar per kitų žmonių termino raštu.

407
00:24:34,410 --> 00:24:38,470
Paprastai tie h failai yra tik tai, kas, pavyzdžiui, tikrų tipų

408
00:24:38,470 --> 00:24:42,310
arba pareiškimai nestandartinių tipų ar konstantų deklaracijų.

409
00:24:42,310 --> 00:24:47,890
Jums nereikia įdėti funkcijų "įgyvendinančius header files.

410
00:24:47,890 --> 00:24:50,570
Jūs galėsite įdėti, o ne tik savo prototipus.

411
00:24:50,570 --> 00:24:53,050
Jūs įdedate ką norite pasidalinti su pasauliu, tai, ko jiems reikia

412
00:24:53,050 --> 00:24:55,640
siekiant sudaryti savo kodą. Taigi, tiesiog patekti į šio įpročio,

413
00:24:55,640 --> 00:24:59,110
mes nusprendėme padaryti tą patį. Yra ne daug list1.h

414
00:24:59,110 --> 00:25:02,070
bet mes įdėti kažką, kad gali būti įdomūs žmonėms pasaulyje

415
00:25:02,070 --> 00:25:05,030
kurie nori naudotis mūsų susietą sąrašo įgyvendinimu.

416
00:25:05,030 --> 00:25:08,040
Dabar, list1.c aš ne eiti per visas šis dalykas

417
00:25:08,040 --> 00:25:11,390
, nes jis šiek tiek per ilgas, ši programa, bet tegul ją paleisti realus greitai greitai.

418
00:25:11,390 --> 00:25:15,720
Leiskite man sudaryti List1, leiskite man paleiskite List1 ir ką jūs pamatysite

419
00:25:15,720 --> 00:25:18,070
Mes imituoti paprastą maža programa Čia

420
00:25:18,070 --> 00:25:20,990
kad vyksta leiskite man pridėti ir pašalinti numerius į sąrašą.

421
00:25:20,990 --> 00:25:24,310
Taigi leiskite man eiti į priekį ir 3 tipo meniu 3 variantas.

422
00:25:24,310 --> 00:25:27,880
Norite įterpti skaičių - darykime Pirmasis numeris, kuris buvo 9,

423
00:25:27,880 --> 00:25:30,550
ir dabar aš sakė, sąrašas dabar yra 9.

424
00:25:30,550 --> 00:25:33,760
Leiskite man eiti į priekį ir padaryti kitą įterpti, kad aš paspauskite meniu 3.

425
00:25:33,760 --> 00:25:36,760
Ką skaičių aš noriu įterpti? (17)

426
00:25:36,760 --> 00:25:39,220
Įveskite. Ir aš padarysiu tik dar vienas.

427
00:25:39,220 --> 00:25:41,720
Leiskite man įrašyti skaičių 22.

428
00:25:41,720 --> 00:25:45,850
Taigi mes turime iš susietų sąrašą, kad mes turėjome prieš skaidrių forma momentas pradžia.

429
00:25:45,850 --> 00:25:48,740
Kaip tai įterpimas iš tikrųjų vyksta?

430
00:25:48,740 --> 00:25:52,000
Iš tiesų, 22 šiuo metu yra sąrašo pabaigoje.

431
00:25:52,000 --> 00:25:55,050
Taigi istorija papasakojo apie pirmadienį etape ir recapped tik dabar

432
00:25:55,050 --> 00:25:57,460
turi būti iš tikrųjų vyksta kodą.

433
00:25:57,460 --> 00:25:59,700
Leiskite pažvelgti. Leiskite man slinkti žemyn į šį failą.

434
00:25:59,700 --> 00:26:01,720
Mes Koloryzować kai kurių funkcijų,

435
00:26:01,720 --> 00:26:05,630
bet mes eiti, tarkim, įterpti funkciją.

436
00:26:05,630 --> 00:26:11,720
>> Pažiūrėkime, kaip mes einame apie Į šią susietą sąrašą įtraukti naują mazgas.

437
00:26:11,720 --> 00:26:14,550
Kur yra sąrašas paskelbė? Ką gi, pereikite visą kelią iki viršuje

438
00:26:14,550 --> 00:26:19,970
ir pastebiu, kad mano susijęs sąrašas iš esmės yra deklaruojamas kaip vienas žymeklis, kad iš pradžių NULL.

439
00:26:19,970 --> 00:26:23,180
Taigi, aš naudojant pasaulinį kintamąjį,, kurias paprastai mes pamokslavo prieš

440
00:26:23,180 --> 00:26:25,280
nes ji daro jūsų kodas šiek tiek nepatogus, išlaikyti,

441
00:26:25,280 --> 00:26:29,080
tai tarsi tingus, paprastai, bet tai ne tingus ir tai nėra blogai ir tai nėra blogai

442
00:26:29,080 --> 00:26:33,660
jei jūsų programa vienintelis gyvenimo tikslas yra imituoti vieną susijusią sąrašą.

443
00:26:33,660 --> 00:26:35,460
Būtent tai, ką mes darome.

444
00:26:35,460 --> 00:26:39,100
Taip, o ne pranešti apie tai pagrindinis ir tada turi perduoti jį į kiekvieną funkciją

445
00:26:39,100 --> 00:26:42,640
mes parašiau šioje programoje, mes, o ne suprasti, oh, galime tiesiog padaryti jį pasaulio

446
00:26:42,640 --> 00:26:47,060
nes visa šios programos tikslas yra parodyti, vienas ir tik vienas susijęs sąrašą.

447
00:26:47,060 --> 00:26:50,700
Taigi, kad jaučiasi gerai. Čia yra mano prototipus, ir mes negalime eiti per visą šių

448
00:26:50,700 --> 00:26:55,800
bet aš parašiau "Delete funkcija, rasti funkcijos, įterpti funkciją, ir skersiniu funkciją.

449
00:26:55,800 --> 00:26:59,080
Bet tegul dabar eiti atgal įterpti funkciją

450
00:26:59,080 --> 00:27:01,490
ir pamatyti, kaip tai vienas čia dirba.

451
00:27:01,490 --> 00:27:09,940
Intarpas yra on-line - čia mes einame.

452
00:27:09,940 --> 00:27:12,850
Įterpti. Todėl ji neturi imtis jokių argumentų, nes mes ketiname paklausti

453
00:27:12,850 --> 00:27:15,930
vartotojo viduje šio telefono numeris, kurį norite įterpti funkciją.

454
00:27:15,930 --> 00:27:19,410
Bet pirmiausia, mes ruošiamės suteikti jiems šiek tiek vietos.

455
00:27:19,410 --> 00:27:22,050
Tai tarsi kopijuoti ir įklijuoti iš kitos, pavyzdžiui.

456
00:27:22,050 --> 00:27:25,110
Tokiu atveju, mes buvo skirti int Šiuo metu mes skirti mazgas.

457
00:27:25,110 --> 00:27:27,910
Aš tikrai ne prisiminti, kiek baitų mazgas, bet tai gerai.

458
00:27:27,910 --> 00:27:30,460
Sizeof gali suprasti, kad už mane.

459
00:27:30,460 --> 00:27:33,340
Ir kodėl aš patikrinti for null linija 120?

460
00:27:33,340 --> 00:27:37,530
Kas galėtų suklysti 119 atitinka? Taip?

461
00:27:37,530 --> 00:27:40,530
[Studentų atsakymas, nesuprantamas]

462
00:27:40,530 --> 00:27:43,440
Geras. Tik galėtų būti atvejis, kad aš paprašė per daug atminties

463
00:27:43,440 --> 00:27:47,020
arba kažkas negerai ir operacinė sistema neturi pakankamai baitų duoti man,

464
00:27:47,020 --> 00:27:50,640
todėl nurodo, kiek grąžinant NULL, ir jei aš ne patikrinti, ar

465
00:27:50,640 --> 00:27:54,710
ir aš tiesiog aklai tęsti naudoti, adresas grįžo, tai gali būti NULL.

466
00:27:54,710 --> 00:27:58,400
Tai gali būti kai nežinoma vertė, nėra geras dalykas, nebent aš -

467
00:27:58,400 --> 00:28:00,590
iš tikrųjų nebus nežinoma vertė. Ji gali būti lygi NULL, todėl aš nenoriu

468
00:28:00,590 --> 00:28:02,550
ja piktnaudžiauti ir rizikos dereferencing jį.

469
00:28:02,550 --> 00:28:07,410
Jei tai atsitiks, aš tiesiog grįžti ir mes apsimesti, kaip aš ne grįžti jokios atminties.

470
00:28:07,410 --> 00:28:12,270
>> Kitaip, sakau vartotojui man duoti numerį norite įterpti, aš vadinu Mūsų senas draugas GetInt,

471
00:28:12,270 --> 00:28:15,530
ir tada tai buvo nauja sintaksė, mes pristatė pirmadienį.

472
00:28:15,530 --> 00:28:20,320
"Newptr-> n 'reiškia, adresą, kurį buvo suteikta malloc

473
00:28:20,320 --> 00:28:23,490
kuris yra pirmas baitas naujas mazgas objekto,

474
00:28:23,490 --> 00:28:26,860
ir tada eiti į lauką, vadinamas n.

475
00:28:26,860 --> 00:28:35,270
Mažai smulkmenos klausimas: Tai atitinka, ką dar paslaptingas eilutę kodo?

476
00:28:35,270 --> 00:28:38,110
Kaip kitaip galėčiau tai parašiau? Nori imtis Pabandyti?

477
00:28:38,110 --> 00:28:41,480
[Studentų atsakymas, nesuprantamas]

478
00:28:41,480 --> 00:28:44,870
Geras. Naudojant N, bet tai ne visai taip paprasta, kaip šis.

479
00:28:44,870 --> 00:28:47,090
Ką aš pirmiausia reikia daryti? [Studentų atsakymas, nesuprantamas]

480
00:28:47,090 --> 00:28:52,730
Geras. Man reikia daryti * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Taigi tai sako nauja rodyklė akivaizdžiai adresas. Kodėl?

482
00:28:55,610 --> 00:28:59,520
Nes jis buvo grąžintas malloc. * Newptr sako: "ten,"

483
00:28:59,520 --> 00:29:02,970
ir tada, kai jūs ten, tada jūs galite naudoti daugiau susipažinę N,

484
00:29:02,970 --> 00:29:05,730
bet tai tik atrodo šiek tiek negraži, mes, žmonės, ypač jei ketinate

485
00:29:05,730 --> 00:29:10,360
atkreipti patarimų su rodyklėmis visą laiką, pasaulis turi būti standartizuotas pagal šią rodyklę, notacijos,

486
00:29:10,360 --> 00:29:12,320
kuris daro lygiai tą patį.

487
00:29:12,320 --> 00:29:16,070
Taigi jums reikia tik naudoti -> žymėjimą, kai kairėje dalykas yra rodyklė.

488
00:29:16,070 --> 00:29:18,790
Kitaip, jei tai tikrasis struct, naudokite n.

489
00:29:18,790 --> 00:29:25,800
Ir tada tai: Kodėl aš inicijuoti newptr-> Kitas NULL?

490
00:29:25,800 --> 00:29:28,610
Mes nenorime, kabančios kairę ranką etapo pabaigoje.

491
00:29:28,610 --> 00:29:31,630
Mes norime, kad ji nukreipta tiesiai žemyn, o tai reiškia šio sąrašo pabaigą

492
00:29:31,630 --> 00:29:34,980
potencialiai gali būti mazgo, todėl mes geriau įsitikinti, ar jis yra NULL.

493
00:29:34,980 --> 00:29:38,460
Ir apskritai, Inicijuojama kintamuosius arba savo duomenų nariai ir structs

494
00:29:38,460 --> 00:29:40,470
kažkas yra tiesiog gera praktika.

495
00:29:40,470 --> 00:29:45,170
Tik nuomos šiukšlių egzistuoja ir toliau egzistuoja paprastai pasireiškia jums į bėdą

496
00:29:45,170 --> 00:29:48,650
jei pamiršote kažką daryti vėliau.

497
00:29:48,650 --> 00:29:51,590
>> Štai keletas atvejų. Tai, vėlgi, yra įterpti funkciją,

498
00:29:51,590 --> 00:29:54,930
ir pirmas dalykas, aš patikrinti, jei kintamasis vadinamas

499
00:29:54,930 --> 00:29:58,240
pasaulio kintamasis yra NULL, tai reiškia, kad nėra susijęs sąrašas.

500
00:29:58,240 --> 00:30:02,460
Mes neįdėta jokių numerius, todėl trivialus įterpti šį numerį

501
00:30:02,460 --> 00:30:05,240
į sąrašą, nes jis tiesiog priklauso sąrašo pradžioje.

502
00:30:05,240 --> 00:30:08,100
Taigi tai buvo Anita tik atsistojus čia vienas, apsimesdami

503
00:30:08,100 --> 00:30:11,390
niekas kitas čia ant scenos, kol skyrėme mazgas,

504
00:30:11,390 --> 00:30:13,940
tada ji galėtų pakelti ranką pirmą kartą,

505
00:30:13,940 --> 00:30:17,420
jei visi kiti atėjo į sceną po jos pirmadienį.

506
00:30:17,420 --> 00:30:22,900
Dabar čia, tai yra šiek tiek patikrinti, kur aš turiu pasakyti, jei naujas mazgas vertė n

507
00:30:22,900 --> 00:30:27,370
<n vertę dabartinėje pirmojo mazgo,

508
00:30:27,370 --> 00:30:29,930
tai reiškia, kad yra susijusi sąrašas, kurį pradėjo.

509
00:30:29,930 --> 00:30:32,330
Yra bent vienas mazgas sąraše, tačiau šis naujas vaikinas

510
00:30:32,330 --> 00:30:37,230
priklauso prieš jį, todėl mes turime judėti dalykų aplink.

511
00:30:37,230 --> 00:30:43,450
Kitaip tariant, jei tik sąrašas pradėjo su, tarkim,

512
00:30:43,450 --> 00:30:48,100
tik numeris 17, tai - iš tiesų, mes galime tai padaryti aiškiai.

513
00:30:48,100 --> 00:30:56,010
Jei pradėsime savo istoriją su rodykle čia vadinama pirmoji,

514
00:30:56,010 --> 00:30:59,870
ir iš pradžių tai NULL, ir mes įterpti skaičių "9",

515
00:30:59,870 --> 00:31:02,510
numeris 9 aiškiai priklauso sąrašo pradžioje.

516
00:31:02,510 --> 00:31:07,400
Todėl galime apsimesti, mes tiesiog malloced adresą ar numerį 9 ir įdėti jį čia.

517
00:31:07,400 --> 00:31:13,170
Jei pirmasis yra 9 pagal nutylėjimą, Pirmasis scenarijus aptarėme tiesiog reiškia, tegul tašką Šis vaikinas,

518
00:31:13,170 --> 00:31:15,790
palikti tai kaip yra NULL, dabar mes turime numeris 9.

519
00:31:15,790 --> 00:31:18,280
Kitas numeris norime įterpti yra 17.

520
00:31:18,280 --> 00:31:22,420
17 priklauso per čia, todėl mes ketiname padaryti tam tikrą loginį žingsninis per šį.

521
00:31:22,420 --> 00:31:26,060
Taigi, tegul vietoj to, prieš tai darome, galime apsimesti, kad mes norime įterpti skaičių 8.

522
00:31:26,060 --> 00:31:28,650
>> Taigi tik patogumo dėlei, aš ruošiuosi padaryti čia.

523
00:31:28,650 --> 00:31:30,760
Tačiau nepamirškite, kad malloc galite įdėti ją labiausiai bet kur.

524
00:31:30,760 --> 00:31:33,460
Bet Brėžinys dėlei, aš įdėti jį čia.

525
00:31:33,460 --> 00:31:38,440
Taip apsimesti, aš ką tik skyrė skaičius 8 mazgas, tai pagal nutylėjimą yra NULL.

526
00:31:38,440 --> 00:31:42,800
Tai, ką dabar turi įvykti? Pora dalykų.

527
00:31:42,800 --> 00:31:47,090
Mes padarėme šią klaidą scenoje pirmadienį, kai mes atnaujinome žymiklį, kaip šis,

528
00:31:47,090 --> 00:31:51,890
tada tai padarė, ir tada mes tvirtino mes našlaičiai visi kiti ant scenos.

529
00:31:51,890 --> 00:31:54,350
, Nes jūs Negaliu - čia operacijų tvarka yra svarbi,

530
00:31:54,350 --> 00:31:58,760
nes dabar mes praradome šį mazgas 9, kuris yra tiesiog tarsi plaukiojantieji erdvėje.

531
00:31:58,760 --> 00:32:01,150
Taigi tai buvo ne teisingas požiūris pirmadienį.

532
00:32:01,150 --> 00:32:03,330
Pirmiausiai mes turime daryti kažką kita.

533
00:32:03,330 --> 00:32:06,280
Pasaulio valstybė atrodo taip. Iš pradžių, 8 buvo skirta.

534
00:32:06,280 --> 00:32:10,550
Kokia turėtų būti geresnis būdas įterpti 8?

535
00:32:10,550 --> 00:32:14,720
O ne atnaujinti šį žymeklį, tiesiog atnaujinti šį vieną čia vietoj.

536
00:32:14,720 --> 00:32:17,720
Taigi, mums reikia kodo eilutę, kad ketinate išjungti šią NULL pobūdžio

537
00:32:17,720 --> 00:32:22,020
į faktinė rodyklę, kad nukreipta mazgas 9,

538
00:32:22,020 --> 00:32:27,970
ir tada mes galime saugiai pakeisti pirmiausia reikia priminti čia šis vaikinas.

539
00:32:27,970 --> 00:32:31,330
Dabar mes turime sąrašą, susijęs su dviejų elementų sąrašą,.

540
00:32:31,330 --> 00:32:33,580
O ką tai iš tikrųjų atrodo kaip čia?

541
00:32:33,580 --> 00:32:36,900
Jei pažvelgsime į kodą, pastebėsite, kad aš padariau lygiai taip pat.

542
00:32:36,900 --> 00:32:41,970
Jau sakiau, ir šioje istorijoje, newptr newptr buvo nukreipta ne šis vaikinas.

543
00:32:41,970 --> 00:32:45,520
>> Taigi, leiskite man padaryti vieną dalyką, ir aš turėjo palikti šiek tiek daugiau erdvės.

544
00:32:45,520 --> 00:32:48,540
Taigi atleisk Rasito piešinį.

545
00:32:48,540 --> 00:32:52,140
Šis vaikinas yra vadinamas newptr.

546
00:32:52,140 --> 00:32:57,940
Tai yra kintamasis, paskelbė keletą eilučių anksčiau, atsižvelgiant - šiek tiek virš 25.

547
00:32:57,940 --> 00:33:03,430
Ir ji nukreipta į 8. Taigi, kai aš sakau, newptr-> Kitas, tai reiškia, kad eiti į struct

548
00:33:03,430 --> 00:33:07,910
kad nurodė pagal newptr, todėl čia mes esame, ten eiti.

549
00:33:07,910 --> 00:33:13,990
Tada rodyklė sako gauti kitą lauką, ir tada = sako įdėti, kas vertė?

550
00:33:13,990 --> 00:33:17,280
Vertę, kuri buvo pirmą kartą, kas vertė buvo pirmas?

551
00:33:17,280 --> 00:33:21,930
Pirmasis buvo nukreipta į šiame mazge, todėl tai reiškia, kad tai dabar turėtų atkreipti dėmesį šiame mazge.

552
00:33:21,930 --> 00:33:25,660
Kitaip tariant, tai, kas atrodo, nors ir juokinga netvarka su mano ranka,

553
00:33:25,660 --> 00:33:28,620
tai, kas paprasta idėja tiesiog perkelti šias rodykles aplink

554
00:33:28,620 --> 00:33:31,560
tik su šiuo one liner kodas išsiverčia į.

555
00:33:31,560 --> 00:33:38,110
Laikyti, kas yra pirmoji į kitą lauką ir tada atnaujinti, ką 1. iš tikrųjų yra.

556
00:33:38,110 --> 00:33:40,900
Eikime į priekį ir pirmyn per kai tai,

557
00:33:40,900 --> 00:33:44,220
ir tik šiuo uodegos įterpimą dabar.

558
00:33:44,220 --> 00:33:51,210
Tarkime, aš gauti iki taško, kur aš suprato, kad kitas sritis kai mazgas yra NULL.

559
00:33:51,210 --> 00:33:53,410
Ir į istoriją, išsamiai šiuo klausimu, kad aš įvardinant

560
00:33:53,410 --> 00:33:58,170
yra tai, kad aš pristatė dar vieną žymiklį čia 142 eilutėje "pirmtakas rodykle.

561
00:33:58,170 --> 00:34:01,320
Iš esmės, Šiuo istorija, kai sąrašas gauna ilgas,

562
00:34:01,320 --> 00:34:04,800
I rūšies reikia eiti su dviem pirštais, nes jei aš einu per toli,

563
00:34:04,800 --> 00:34:08,219
Prisimenu vieno ilgio sąrašą, jūs negalite eiti atgal.

564
00:34:08,219 --> 00:34:13,659
Taigi šis predptr idėja yra mano kairėje pirštu, ir newptr - ne newptr.

565
00:34:13,659 --> 00:34:17,199
Kitas rodyklė, kad čia yra mano pirštas, ir aš tiesiog malonu vaikščioti sąrašą.

566
00:34:17,199 --> 00:34:22,179
Štai kodėl tai egzistuoja. Bet galime svarstyti tik vieną iš paprastesnių atvejų čia.

567
00:34:22,179 --> 00:34:26,620
Jei tos POINTER Kitas laukas yra NULL, kas logiška potekstė?

568
00:34:26,620 --> 00:34:30,840
Jei esate važiuojantiems šį sąrašą ir jūs nukentėjo NULL žymiklį?

569
00:34:30,840 --> 00:34:35,780
Esate ne sąrašo pabaigoje, ir taip kodas pridėti šį vieną papildomą elementą

570
00:34:35,780 --> 00:34:41,230
yra tarsi intuityvus imtis, kad mazgas, kurio žymeklis yra NULL,

571
00:34:41,230 --> 00:34:46,120
todėl tai yra šiuo metu NULL, ir jį pakeisti, nors, naujas mazgas adresas.

572
00:34:46,120 --> 00:34:52,260
Taigi mes tiesiog piešimo kodas rodyklę, kad mes rėmėsi kažkieno kairę ranką didinant etape.

573
00:34:52,260 --> 00:34:54,070
>> Ir, kad aš pamojuoti savo rankas dabar,

574
00:34:54,070 --> 00:34:58,020
tik todėl, kad aš manau, kad lengva pasiklysti, kai mes tai darome šioje aplinkoje rūšiuoti,

575
00:34:58,020 --> 00:35:00,600
tikrinti įterpimą ne sąrašo viduryje.

576
00:35:00,600 --> 00:35:03,220
Bet tiesiog intuityviai, kas turi atsitikti, jei norite išsiaiškinti,

577
00:35:03,220 --> 00:35:06,600
kai kurie numeris priklauso viduryje yra jūs turite vaikščioti

578
00:35:06,600 --> 00:35:09,510
su daugiau nei vienu pirštu daugiau nei vieną rodyklę,

579
00:35:09,510 --> 00:35:12,920
išsiaiškinti, kur ji priklauso tikrinimo elementas <dabartinė

580
00:35:12,920 --> 00:35:15,450
> Vienas, ir kai jums rasti tą vietą,

581
00:35:15,450 --> 00:35:20,400
tada jūs turite tai padaryti, Shell žaidimas rūšiuoti, kur jums judėti patarimų apie labai atsargiai.

582
00:35:20,400 --> 00:35:23,850
Ir kad atsakymas, jei norite prie priežasties, per šį savo namuose,

583
00:35:23,850 --> 00:35:28,340
suvesta tik šių dviejų eilučių kodo, bet šių eilučių, kad yra super svarbu.

584
00:35:28,340 --> 00:35:31,390
Nes jei jūs lašas kažkieno ranką ir kelti kažkieno neteisinga tvarka,

585
00:35:31,390 --> 00:35:34,580
dar kartą, jums gali baigtis sąrašą orphaning.

586
00:35:34,580 --> 00:35:39,500
Apibendrinti konceptualiai uodegos įterpimas yra gana paprasta.

587
00:35:39,500 --> 00:35:42,940
Galvos įterpimas yra taip pat gana paprasta,

588
00:35:42,940 --> 00:35:45,580
bet jums reikia atnaujinti papildomą POINTER šį kartą

589
00:35:45,580 --> 00:35:47,930
išspausti į sąrašą 5,

590
00:35:47,930 --> 00:35:51,560
ir tada viduryje įterpimo reikia dar daugiau pastangų,

591
00:35:51,560 --> 00:35:56,130
labai atsargiai įkiškite į teisingą vietą, kurios numeris 20

592
00:35:56,130 --> 00:35:58,350
kuris yra tarp 17 ir 22.

593
00:35:58,350 --> 00:36:02,700
Taigi, ką jums reikia padaryti kažką panašaus į naują mazgas 20 punkte iki 22,

594
00:36:02,700 --> 00:36:08,470
ir tada, Kuris mazgas rodyklė turi būti atnaujintas paskutinis?

595
00:36:08,470 --> 00:36:10,630
Tai 17, faktiškai įdėkite jį.

596
00:36:10,630 --> 00:36:14,080
Taigi dar kartą, aš atidėti faktinį tos konkrečios įgyvendinimo kodą.

597
00:36:14,080 --> 00:36:17,280
>> Iš pirmo žvilgsnio, tai šiek tiek absoliuti, bet tai tikrai tik begalinis ciklas

598
00:36:17,280 --> 00:36:21,770
ciklais, kilpų, kilpų, kilpų, ir trūkimo, kai tik paspausite NULL žymiklį,

599
00:36:21,770 --> 00:36:24,590
, kuriame jūs galite padaryti, reikalingą įterpti.

600
00:36:24,590 --> 00:36:30,960
Tai, tada, yra atstovas susijęs sąrašas įterpimo kodas.

601
00:36:30,960 --> 00:36:34,590
Tai buvo natūra partijos, ir ji mano, kaip mes išspręsti vieną problemą,

602
00:36:34,590 --> 00:36:36,940
bet mes įdiegėme visą kitą. Atvirai kalbant, mes praleido visą šį laiką

603
00:36:36,940 --> 00:36:40,540
didelis O ir Ω ir važiavimo laiką, bando išspręsti problemas greičiau,

604
00:36:40,540 --> 00:36:43,270
ir čia mes žengiame didelį žingsnį atgal, jis jaučiasi.

605
00:36:43,270 --> 00:36:45,380
Ir dar, jei tikslas yra saugoti duomenis,

606
00:36:45,380 --> 00:36:48,010
jis jaučiasi Šventojo Gralio, kaip sakėme, pirmadienį, būtų tikrai

607
00:36:48,010 --> 00:36:50,470
laikyti dalykų iš karto.

608
00:36:50,470 --> 00:36:53,930
>> Iš tikrųjų, tarkime, kad mes tai padarėme atidėti susietą sąrašą for a moment,

609
00:36:53,930 --> 00:36:56,000
ir mes vietoj pristatė stalo sąvoką.

610
00:36:56,000 --> 00:36:59,110
Ir tegul tiesiog manau, kad lentelės kaip masyvo metu.

611
00:36:59,110 --> 00:37:03,790
Šis masyvas ir šiuo atveju čia yra apie 26 elementų, nuo 0 iki 25,

612
00:37:03,790 --> 00:37:07,940
ir manyti, kad jums reikia šiek tiek saugojimo riekė pavadinimų:

613
00:37:07,940 --> 00:37:10,350
Alisa ir Bobas ir Čarlis ir kaip.

614
00:37:10,350 --> 00:37:12,880
Ir jums reikia tam tikrą duomenų struktūrą laikyti tuos pavadinimus.

615
00:37:12,880 --> 00:37:15,000
Na, galite naudoti kažką panašaus į susietą sąrašą

616
00:37:15,000 --> 00:37:20,260
ir tu gali vaikščioti sąrašą įdėti Alice prieš po Bob Bob ir Charlie ir kt.

617
00:37:20,260 --> 00:37:23,850
Ir iš tiesų, jeigu norite pamatyti kodą, kaip kad panaikinti,

618
00:37:23,850 --> 00:37:27,230
žinoti, kad list2.h, mes lygiai taip pat.

619
00:37:27,230 --> 00:37:30,610
Mes negalime eiti per šio kodekso, bet tai yra ir pirmajame pavyzdyje variantas

620
00:37:30,610 --> 00:37:34,640
kad pristato vieną kitą struct mes matėme prieš vadinamosios studentų,

621
00:37:34,640 --> 00:37:40,330
ir kas tada ji iš tikrųjų saugo į susietą sąrašą, yra rodyklė į studentų struktūrą

622
00:37:40,330 --> 00:37:44,520
o ne paprastas mažas sveikasis skaičius, n.

623
00:37:44,520 --> 00:37:46,900
Taigi, suprantate, kodas, apima faktines eilutes,

624
00:37:46,900 --> 00:37:49,940
bet jei po ranka tikslas tikrai dabar spręsti efektyvumo problema,

625
00:37:49,940 --> 00:37:53,380
ar nebūtų malonu, jei mes suteikiama objektas, vadinamas Alisa,

626
00:37:53,380 --> 00:37:56,020
mes norime įdėti ją į tinkamą vietą, duomenų struktūros,

627
00:37:56,020 --> 00:37:58,860
jis jaučiasi, kad būčiau tikrai gražus, tiesiog įdėti Alice,

628
00:37:58,860 --> 00:38:01,180
kurio pavadinimas prasideda pirmoje vietoje.

629
00:38:01,180 --> 00:38:05,270
Ir Bobas, kurio vardas prasideda su B, antroje vietoje.

630
00:38:05,270 --> 00:38:09,580
Masyvo, arba leisti pradėti skambinti lentelę, maišos lentelė tuo,

631
00:38:09,580 --> 00:38:13,650
mes galime daryti būtent tai. Jei mes kaip Alisa pavadinimą,

632
00:38:13,650 --> 00:38:16,700
kaip Alice eilutę, kur jūs įtraukėte A-L-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Mums reikia hueristic. Mes turime funkciją, šiek tiek kaip Alisa indėlį

634
00:38:20,540 --> 00:38:24,610
ir grąžina atsakymą: "Kišk Alice šioje vietoje."

635
00:38:24,610 --> 00:38:28,720
Ir ši funkcija, tai black box ", bus vadinamas maišos funkcija.

636
00:38:28,720 --> 00:38:32,330
>> Maišos funkcija yra kažkas, kad mano indėlį, pavyzdžiui, "Alisa",

637
00:38:32,330 --> 00:38:38,080
ir grįžta į jus, paprastai, skaitmeninis vieta kai duomenų struktūra, kurioje Alisa priklauso.

638
00:38:38,080 --> 00:38:40,830
Šiuo atveju, mūsų maišos funkcija turėtų būti gana paprasta.

639
00:38:40,830 --> 00:38:47,510
Mūsų maišos funkcija turėtų pasakyti, jei jums būtų suteikta "Alice", kuris personažas man rūpi?

640
00:38:47,510 --> 00:38:55,660
Pirmasis. Taigi aš žiūriu [0], ir tada aš sakau jei [0] charakteris yra, grįžti skaičių 0.

641
00:38:55,660 --> 00:39:01,130
Jei tai B grąžinti 1. Jei tai C, grįžkite 2, ir taip toliau.

642
00:39:01,130 --> 00:39:05,940
Visi 0 indeksą, ir kad leistų man įterpti Alisa ir tada Bob ir tada Charlie ir tt

643
00:39:05,940 --> 00:39:10,960
į šią duomenų struktūros. Bet yra problema.

644
00:39:10,960 --> 00:39:13,060
Ką daryti, jei Anita vėl ateina kartu?

645
00:39:13,060 --> 00:39:17,510
Kur mes įdėti Anita? Jos vardas irgi prasideda raide A,

646
00:39:17,510 --> 00:39:20,330
ir jis jaučiasi, kaip mes padarėme dar didesnę netvarką šios problemos.

647
00:39:20,330 --> 00:39:24,380
Dabar mes turime nedelsiant įterpimą, nuolatinio laiko, furnitūra, į duomenų struktūros

648
00:39:24,380 --> 00:39:27,100
o ne blogiausiam atvejui, linijinė,

649
00:39:27,100 --> 00:39:29,510
bet ką mes galime padaryti su Anita šiuo atveju?

650
00:39:29,510 --> 00:39:34,110
Kokie yra du variantai, tikrai? Taip?

651
00:39:34,110 --> 00:39:37,410
[Studentų atsakymas, nesuprantamas] Gerai, kad galėtume turėti dar vieną aspektą.

652
00:39:37,410 --> 00:39:42,320
Tai gerai. Taigi, mes galime kurti daiktus iš 3D, kaip mes kalbėjome apie tai žodžiu pirmadienį.

653
00:39:42,320 --> 00:39:46,700
Mes galime pridėti dar vieną prieigą, bet manyti, kad ne, aš bando išlaikyti tai paprasta.

654
00:39:46,700 --> 00:39:50,160
Visa tikslas čia yra nedelsiant pastovaus laiko susipažinti,

655
00:39:50,160 --> 00:39:52,170
kad pridedant per daug sud ÷ tingumą.

656
00:39:52,170 --> 00:39:55,970
Kas yra ir kitų variantų, bandant įterpti Anita į šią duomenų struktūros? Taip?

657
00:39:55,970 --> 00:39:58,610
[Studento atsakymas, nesuprantamas] Geras. Taigi, mes galime judėti žemyn, visi kiti

658
00:39:58,610 --> 00:40:03,040
kaip Charlie nudges žemyn Bob ir Alisa, ir tada mes įdėti Anita, kur ji tikrai nori būti.

659
00:40:03,040 --> 00:40:05,660
>> Žinoma, dabar, yra šalutinis poveikis.

660
00:40:05,660 --> 00:40:09,000
Ši duomenų struktūra yra turbūt naudinga, ne todėl, kad norite įterpti žmonių kartą

661
00:40:09,000 --> 00:40:11,250
bet todėl, kad mes norime patikrinti, jei jie ten vėliau

662
00:40:11,250 --> 00:40:13,600
, jei norime atspausdinti visų pavadinimų duomenų struktūros.

663
00:40:13,600 --> 00:40:15,850
Mes ketiname kažką daryti su šiais duomenimis galiausiai.

664
00:40:15,850 --> 00:40:20,810
Taigi dabar mes rūšies prisukamas per Alice, kuris nebėra, kur ji turėtų būti.

665
00:40:20,810 --> 00:40:23,880
Be to, Bobas, nei Čarlis.

666
00:40:23,880 --> 00:40:26,060
Taigi, galbūt tai nėra tokia gera idėja.

667
00:40:26,060 --> 00:40:28,830
Bet iš tikrųjų, tai yra viena iš galimybių. Mes galime pereiti visus žemyn,

668
00:40:28,830 --> 00:40:32,240
ar gi Anita atėjo vėlai į žaidimą, kodėl ne mes tiesiog įdėti Anita

669
00:40:32,240 --> 00:40:35,870
ne čia, ne čia, ne čia, tegul tiesiog įdėti ją šiek tiek mažesnis sąraše.

670
00:40:35,870 --> 00:40:38,680
Bet tada ši problema vėl pradeda išsigimti.

671
00:40:38,680 --> 00:40:41,630
Jums gali būti suteikta rasti Alice akimirksniu, remiantis savo vardą.

672
00:40:41,630 --> 00:40:44,320
Ir Bob iš karto, ir Charlie. Bet tada jums atrodo Anita

673
00:40:44,320 --> 00:40:46,360
ir pamatysite, hmm, Alice yra kelyje.

674
00:40:46,360 --> 00:40:48,770
Na, leiskite man patikrinti žemiau Alisa. Bob nėra Anita.

675
00:40:48,770 --> 00:40:51,850
Čarlis Anita. O, aš Anita.

676
00:40:51,850 --> 00:40:54,720
Ir jei jūs ir toliau tos pačios logikos traukinys visą kelią,

677
00:40:54,720 --> 00:41:00,690
kas blogiausio atvejo veikimo laikas surasti arba įdėti į šią naują duomenų struktūros Anita?

678
00:41:00,690 --> 00:41:03,280
O (n), tiesa?

679
00:41:03,280 --> 00:41:06,280
Nes blogiausiu atveju, yra Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
paliko visą kelią žemyn kažkas pavadino "Y", todėl yra tik vienoje vietoje.

681
00:41:10,150 --> 00:41:13,950
Laimei, mes turime niekas vadinamas "Z", todėl mes įdėti Anita pačioje apačioje.

682
00:41:13,950 --> 00:41:16,040
>> Mes tikrai ne išspręsti šią problemą.

683
00:41:16,040 --> 00:41:19,890
Taigi, gal mes reikia pristatyti šį trečiąjį aspektą.

684
00:41:19,890 --> 00:41:22,230
Ir it turns out, jei mes pristatyti šį trečiąjį aspektą,

685
00:41:22,230 --> 00:41:25,240
mes negalime padaryti, tai puikiai, bet šventasis Gralis bus gauti

686
00:41:25,240 --> 00:41:28,370
pastovaus laiko įterpimas ir dinaminės intarpai, kad

687
00:41:28,370 --> 00:41:30,960
mes neturime sunkiai kodas 26 dydžio masyvas.

688
00:41:30,960 --> 00:41:34,400
Mes galime įterpti kaip daug pavadinimų, kaip mes norime, tačiau galime imtis mūsų 5-minučių pertrauką

689
00:41:34,400 --> 00:41:38,790
ir tada padaryti, kad tinkamai.

690
00:41:38,790 --> 00:41:46,020
Gerai. Aš nustačiau istorija gana dirbtinai ten

691
00:41:46,020 --> 00:41:48,670
pasirenkant Alice ir Bob ir tada tada Charlie ir tada Anita,

692
00:41:48,670 --> 00:41:51,000
kurio vardas buvo akivaizdžiai susiduria su Alice.

693
00:41:51,000 --> 00:41:54,120
Bet klausimas, mes galų Pirmadienį tik kaip tikėtina, yra

694
00:41:54,120 --> 00:41:56,370
, kad galėtumėte gauti šių rūšių susidūrimų? Kitaip tariant,

695
00:41:56,370 --> 00:42:00,490
jei mes pradėsime naudoti šį lentelių struktūrą, kuri yra tikrai tik matrica,

696
00:42:00,490 --> 00:42:02,460
šiuo atveju yra 26 vietų,

697
00:42:02,460 --> 00:42:05,740
ką daryti, jei mūsų įėjimai, o ne tolygiai paskirstyta?

698
00:42:05,740 --> 00:42:09,620
Tai ne dirbtinai Alisa ir Bobas ir Charlie ir Davidas ir tt pagal abėcėlę

699
00:42:09,620 --> 00:42:12,380
jis tolygiai paskirstytą nuo A iki Z.

700
00:42:12,380 --> 00:42:15,220
>> Gal mes tiesiog gauti pasisekė ir mes neketiname turėti du ar du b

701
00:42:15,220 --> 00:42:17,640
su labai didele tikimybe, bet kaip kažkas atkreipė dėmesį,

702
00:42:17,640 --> 00:42:20,730
jei mes apibendrintas tai problema, o ne 0-25

703
00:42:20,730 --> 00:42:26,060
bet, tarkim, nuo 0 iki 364 arba 65, dažnai dienų skaičius tipiškas metais,

704
00:42:26,060 --> 00:42:31,170
ir paprašė klausimą: "Kokia tikimybė, kad du iš mūsų šiame kambaryje turi tą patį gimtadienį?"

705
00:42:31,170 --> 00:42:34,600
Kitaip tariant, kas yra tikimybė, kad du iš mūsų turi vardą, pradedant?

706
00:42:34,600 --> 00:42:37,190
Klausimo rūšiuoti yra tas pats, tačiau šis adresas erdvė,

707
00:42:37,190 --> 00:42:39,940
šią paiešką erdvė, yra didesnis gimtadienius atveju,

708
00:42:39,940 --> 00:42:42,820
nes mes turime tiek daug daugiau dienų per metus, nei abėcėlės raidėmis.

709
00:42:42,820 --> 00:42:44,910
Kas yra susidūrimo tikimybė?

710
00:42:44,910 --> 00:42:48,410
Na, mes galime galvoti apie tai suprasti, matematikos priešinga kryptimi.

711
00:42:48,410 --> 00:42:50,580
, Kas be susidūrimų tikimybė?

712
00:42:50,580 --> 00:42:53,970
Na, tai sąvoka čia sako, kad tai, kas yra tikimybė,

713
00:42:53,970 --> 00:42:58,770
jei yra tik vienas asmuo šiame kambaryje, kad jie turi unikalią gimtadienį?

714
00:42:58,770 --> 00:43:01,190
Tai 100%. Nes jei yra tik vienas asmuo, į kambarį,

715
00:43:01,190 --> 00:43:03,940
jo arba jos gimtadienis gali būti bet koks 365 dienų iš metų.

716
00:43:03,940 --> 00:43:08,650
Taigi 365/365 variantų suteikia man vertę 1.

717
00:43:08,650 --> 00:43:11,250
Taigi atitinkamas tikimybė šiuo metu yra tik 1.

718
00:43:11,250 --> 00:43:13,270
Bet jei ten antras žmogus į kambarį,

719
00:43:13,270 --> 00:43:16,490
kas yra tikimybė, kad jų gimtadienis yra kitoks?

720
00:43:16,490 --> 00:43:20,680
Yra tik 364 galimi dienų, ignoruodama keliamaisiais metais,

721
00:43:20,680 --> 00:43:23,580
jų gimimo nesikirstų su kitų asmenų.

722
00:43:23,580 --> 00:43:31,920
Taigi 364/365. Jei trečiasis asmuo ateina, tai 363/365 ir kt.

723
00:43:31,920 --> 00:43:35,790
Todėl mes nuolat dauginant šias frakcijas, kurios vis mažesni ir mažesni,

724
00:43:35,790 --> 00:43:40,720
išsiaiškinti, kokia yra tikimybė, kad visi mes turime unikalius gimtadienius?

725
00:43:40,720 --> 00:43:43,570
Bet tada mes galime, žinoma, tik šį atsakymą ir apversti jį aplink

726
00:43:43,570 --> 00:43:47,210
ir padaryti 1 atėmus visus, išraiška, mes galų gale gauti

727
00:43:47,210 --> 00:43:51,250
Jei prisimenate savo matematikos knygose atgal, atrodo, šiek tiek kažką panašaus į tai,

728
00:43:51,250 --> 00:43:54,590
kuris yra daug lengviau interpretuojamos grafiškai.

729
00:43:54,590 --> 00:43:57,820
Ir tai grafinis čia yra x ašyje gimimo dienų skaičių,

730
00:43:57,820 --> 00:44:02,030
arba skaičius žmonių, kurių gimtadieniai, ir ant y ašies yra rungtynių tikimybė.

731
00:44:02,030 --> 00:44:06,060
Ir ką tai sako, kad jei turite, tarkim, net,

732
00:44:06,060 --> 00:44:10,860
galime pasirinkti kažką panašaus į 22, 23.

733
00:44:10,860 --> 00:44:13,160
Jei yra 22 arba 23 žmonių kambaryje,

734
00:44:13,160 --> 00:44:17,100
tikimybė, kad du iš tų nedaugelio žmonių ketinate turėti tą patį gimtadienį

735
00:44:17,100 --> 00:44:19,560
iš tikrųjų yra super didelis, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% tikimybė, kad vos 22 žmonių, seminaras, praktiškai klasei,

737
00:44:23,450 --> 00:44:25,790
2 iš tų žmonių, kurie ketinate turėti tą patį gimtadienį.

738
00:44:25,790 --> 00:44:28,520
, Nes ten yra tiek daug būdų, kuriais jūs galite turėti tą patį gimtadienį.

739
00:44:28,520 --> 00:44:31,110
Dar blogiau, jei peržvelgsite dešinėje diagramos pusėje,

740
00:44:31,110 --> 00:44:34,040
iki to laiko turite klasėje su 58 studentų,

741
00:44:34,040 --> 00:44:39,270
iš 2 žmonių, turinčių gimtadienį tikimybė yra super, super didelė, beveik 100%.

742
00:44:39,270 --> 00:44:41,880
Dabar, tai tarsi įdomus faktas apie realiame gyvenime.

743
00:44:41,880 --> 00:44:45,850
>> Tačiau pasekmės, dabar duomenų struktūrų ir saugoti informaciją

744
00:44:45,850 --> 00:44:51,100
reiškia, kad tik jei turite gražią, švarią, vienodą duomenų platinimą

745
00:44:51,100 --> 00:44:53,650
ir jūs turite pakankamai didelė matrica, kad tilptų krūva dalykų

746
00:44:53,650 --> 00:44:59,360
nereiškia, kad jūs ketinate gauti žmonių unikalių vietų.

747
00:44:59,360 --> 00:45:03,810
Jūs ketinate turėti susidūrimų. Taigi šis maišos sąvoka, kaip ji vadinama,

748
00:45:03,810 --> 00:45:07,450
atsižvelgiant, pavyzdžiui, "Alisa" indėlį ir masažuojant ją tam tikru būdu

749
00:45:07,450 --> 00:45:10,190
ir tada gauti atsakymą kaip 0 arba 1 arba 2.

750
00:45:10,190 --> 00:45:17,500
Kamuoja šio susidūrimo tikimybės gauti atgal kai išėjimo iš šios funkcijos.

751
00:45:17,500 --> 00:45:19,530
Taigi, kaip mes galime tvarkyti šiuos susidūrimų?

752
00:45:19,530 --> 00:45:21,940
Na, vienu atveju, mes galime imtis buvo pasiūlyta idėja, kad.

753
00:45:21,940 --> 00:45:25,100
Mes galime tiesiog perkelti visus žemyn, arba gal, šiek tiek daugiau tiesiog,

754
00:45:25,100 --> 00:45:29,870
, o visi kiti ne perkelti, tegul tiesiog perkelti Anita turima vietoje apačioje.

755
00:45:29,870 --> 00:45:32,810
Taigi, jei Alice yra 0, Bobas yra 1, Charlie yra 2

756
00:45:32,810 --> 00:45:35,260
mes tiesiog įdėti Anita buvimo vietos 3.

757
00:45:35,260 --> 00:45:38,860
Ir tai yra technika vadinama linijinis zondavimo duomenų struktūrų.

758
00:45:38,860 --> 00:45:41,310
Linijinis, nes jūs tiesiog vaikščioti šią eilutę, ir jūs tarsi zondavimo

759
00:45:41,310 --> 00:45:43,640
įmanomų vietovių duomenų struktūros.

760
00:45:43,640 --> 00:45:46,210
Žinoma, tai pereina į O (n).

761
00:45:46,210 --> 00:45:49,590
Jei tikrai pilna duomenų struktūra, yra jau 25 žmonių,

762
00:45:49,590 --> 00:45:54,120
ir tada Anita ateina kartu, ji galų gale, kas būtų vieta Z, ir to pakanka.

763
00:45:54,120 --> 00:45:56,540
Ji vis dar tinka, ir mes galime rasti ją vėliau.

764
00:45:56,540 --> 00:46:00,100
>> Bet tai buvo priešingai spartumo dalykų tikslo.

765
00:46:00,100 --> 00:46:02,530
Taigi ką daryti, jei mes vietoj pristatė šią trečiąją dimensiją?

766
00:46:02,530 --> 00:46:06,400
Šis metodas yra paprastai vadinamas atskiras Grupavimo, arba turintys grandines.

767
00:46:06,400 --> 00:46:10,030
Ir kas maišos lentelė yra dabar, tai Tabular struktūra

768
00:46:10,030 --> 00:46:13,450
jūsų stalo yra tiesiog patarimų masyvo.

769
00:46:13,450 --> 00:46:18,230
Bet kokios rodykles rodo, kad yra atspėti, ką?

770
00:46:18,230 --> 00:46:21,970
Susijęs sąrašas. Taigi ką daryti, jei mes priimame tiek iš šitų pasaulių geriausias?

771
00:46:21,970 --> 00:46:26,500
Mes naudojame masyvų pradinių rodiklių

772
00:46:26,500 --> 00:46:32,070
į duomenų struktūrą, todėl mes galime iš karto eiti į [0] [1] [30] arba taip toliau,

773
00:46:32,070 --> 00:46:36,480
bet taip, kad mes turime tam tikrą lankstumą ir mes galime pritaikyti Anita ir Alice ir Adomas

774
00:46:36,480 --> 00:46:38,630
ir bet kuris kitas vardas,

775
00:46:38,630 --> 00:46:43,470
mes o ne tegul kitą ašį augti savavališkai.

776
00:46:43,470 --> 00:46:47,340
Ir mes pagaliau, kaip nuo pirmadienio, kad išraiškingą galimybes su susietą sąrašą.

777
00:46:47,340 --> 00:46:49,530
Duomenų struktūrą mes galime augti savavališkai.

778
00:46:49,530 --> 00:46:52,450
Kita vertus, mes galime tiesiog padaryti didelį 2-dimensional array,

779
00:46:52,450 --> 00:46:57,190
bet tai bus baisu situacija, jei vienas iš 2-dimensional array eilučių

780
00:46:57,190 --> 00:47:01,280
nėra pakankamai didelis, už papildomą asmuo, kurio vardas atsitinka pradėti su A.

781
00:47:01,280 --> 00:47:04,200
Neduok Dieve, mes turime perskirstyti tam tikrą didžiulį 2-dimensijų struktūrą

782
00:47:04,200 --> 00:47:06,600
tik todėl, kad yra tiek daug žmonių, pavadintas,

783
00:47:06,600 --> 00:47:09,480
ypač kai yra tiek mažai žmonių, pavadintas Z kažkas.

784
00:47:09,480 --> 00:47:12,170
Tai tiesiog bus labai nedaug duomenų struktūra.

785
00:47:12,170 --> 00:47:15,400
Taigi, tai nėra tobula, bet kokiomis priemonėmis, tačiau dabar mes bent jau turi galimybę

786
00:47:15,400 --> 00:47:19,090
iš karto rasti, kur Alisa ar Anita priklauso,

787
00:47:19,090 --> 00:47:21,090
bent jau kalbant apie vertikalią ašį,

788
00:47:21,090 --> 00:47:25,850
ir tada mes tiesiog turite nuspręsti, kur įdėti Anita arba Alice šiame susietą sąrašą.

789
00:47:25,850 --> 00:47:32,480
Jei mes neturime rūpintis apie rūšiavimas dalykų, kaip greitai mes galime įterpti Alice į kaip šis struktūrą?

790
00:47:32,480 --> 00:47:35,370
Tai nuolatinio laiko. Mūsų rodyklę į [0], ir jei ten niekas,

791
00:47:35,370 --> 00:47:37,550
Alisa eina šios susijusios sąrašo pradžioje.

792
00:47:37,550 --> 00:47:40,000
Bet tai nėra didžiulis spręsti. Nes jei Anita tada ateina kartu

793
00:47:40,000 --> 00:47:42,160
vėliau kai kurių žingsnių, kur Anita priklauso?

794
00:47:42,160 --> 00:47:45,140
Na, [0]. OOP. Alice yra jau šios susijusios sąraše.

795
00:47:45,140 --> 00:47:47,760
>> Bet jei mes nerūpi rūšiavimo šiuos pavadinimus,

796
00:47:47,760 --> 00:47:53,580
mes galime tiesiog perkelti Alice daugiau, įterpti Anita, tačiau net ir tai yra pastovi laiko.

797
00:47:53,580 --> 00:47:57,010
Net jei yra Ieva ir Adomas ir visi tie kiti pavadinimai,

798
00:47:57,010 --> 00:47:59,410
tai nėra labai perkelia jas fiziškai. Kodėl?

799
00:47:59,410 --> 00:48:04,090
Nes mes tiesiog padarė čia susijęs sąrašą, kuris žino, šie centrai yra bet kokiu atveju?

800
00:48:04,090 --> 00:48:06,550
Viskas, ką jums reikia padaryti, tai perkelti duonos trupinius.

801
00:48:06,550 --> 00:48:10,930
Perkelti rodykles aplink, jums nereikia fiziškai perkelti visus duomenis, aplink.

802
00:48:10,930 --> 00:48:14,610
Taigi, mes galime įterpti Anita, tokiu atveju iš karto. Nuolatinio laiko.

803
00:48:14,610 --> 00:48:20,250
Taigi, mes turime pastovios laiko paieškos, ir nuolatinis laiko kažkas panašaus Anita įterpimo.

804
00:48:20,250 --> 00:48:22,740
Bet rūšies oversimplifying pasaulį.

805
00:48:22,740 --> 00:48:28,510
Ką daryti, jei mes vėliau norite rasti Alice?

806
00:48:28,510 --> 00:48:31,050
Ką daryti, jei mes vėliau norite rasti Alice?

807
00:48:31,050 --> 00:48:35,690
Kiek žingsnių yra tai, kad ketinate imtis?

808
00:48:35,690 --> 00:48:37,850
[Studentų atsakymas, nesuprantamas]

809
00:48:37,850 --> 00:48:40,950
Tiksliai. Žmonių skaičius prieš Alisa į susietą sąrašą.

810
00:48:40,950 --> 00:48:45,420
Taigi tai ne visai tobulas, nes, vėlgi, yra mūsų duomenų struktūra Ši vertikali prieigos

811
00:48:45,420 --> 00:48:50,240
ir tada ji turi šių susijusių sąrašus kabinti - iš tiesų, tegul ne atkreipti masyvo.

812
00:48:50,240 --> 00:48:56,020
Ji šie susiję sąrašai kabo ne apie tai, kad atrodo šiek tiek kažką panašaus į tai.

813
00:48:56,020 --> 00:48:59,110
Bet problema yra, jei Alisa ir Adomas ir visi tie kiti pavadinimai

814
00:48:59,110 --> 00:49:01,720
galų gale, vis daugiau ir daugiau ten,

815
00:49:01,720 --> 00:49:04,810
rasti kas nors galėtų galų gale imtis tam tikrų veiksmų krūva,

816
00:49:04,810 --> 00:49:06,670
Bcause turite feed susietą sąrašą,

817
00:49:06,670 --> 00:49:08,090
kuri yra tiesinė operacija.

818
00:49:08,090 --> 00:49:14,270
Taigi tikrai, tada, įterpimo laikas galiausiai yra O (n), kur n yra sąrašo elementų skaičius.

819
00:49:14,270 --> 00:49:21,780
Padalinta iš, galime savavališkai m, kur m yra sujungtų sąrašų skaičius

820
00:49:21,780 --> 00:49:24,500
kad mes turime šios vertikalios ašies.

821
00:49:24,500 --> 00:49:27,180
Kitaip tariant, jei mes iš tiesų prisiimti vienodą paskirstymo pavadinimų,

822
00:49:27,180 --> 00:49:30,150
visiškai nerealu. Yra akivaizdžiai daugiau kai kurių raidžių, nei kiti.

823
00:49:30,150 --> 00:49:32,580
>> Bet jei mes manome, šiuo metu vienodas platinimo,

824
00:49:32,580 --> 00:49:37,350
ir mes n Iš viso žmonių, ir m Bendras tinklai

825
00:49:37,350 --> 00:49:40,630
mums prieinama, tada kiekvieną iš šių tinklų ilgis

826
00:49:40,630 --> 00:49:44,380
gana tiesiog bus iš viso, n padalintas iš grandinių.

827
00:49:44,380 --> 00:49:48,900
Taigi n / m. Bet čia, kur mes galime būti visi matematiškai protingas.

828
00:49:48,900 --> 00:49:53,030
m yra konstanta, nes ten yra nustatytas jų skaičius.

829
00:49:53,030 --> 00:49:54,620
Jūs ketinate paskelbti savo komplekta pradžioje,

830
00:49:54,620 --> 00:49:58,450
ir mes ne dydžio keitimas vertikalią ašį. , Pagal apibrėžimą, lieka nustatyta.

831
00:49:58,450 --> 00:50:01,220
Tai tik horizontalioji ašis, taip sakant, kad keičiasi.

832
00:50:01,220 --> 00:50:04,760
Techniškai, tai yra konstanta. Taigi dabar, įterpimo laikas

833
00:50:04,760 --> 00:50:09,700
yra gana daug O (n).

834
00:50:09,700 --> 00:50:12,410
Taip, kad visi, kad daug geriau nesijaučia.

835
00:50:12,410 --> 00:50:14,940
Bet kas tiesa čia? Na, visą šį laiką, savaites,

836
00:50:14,940 --> 00:50:20,640
mes buvo sakydamas O (n ²). O (n), 2 x n ² - n, padalintas iš 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
Tai tiesiog n ². Bet dabar, šį semestrą,

838
00:50:23,580 --> 00:50:25,560
mes galime pradėti kalbėti apie realiame pasaulyje vėl.

839
00:50:25,560 --> 00:50:31,520
Ir n / m yra neabejotinai greičiau nei tiesiog n vien.

840
00:50:31,520 --> 00:50:35,170
Jei turite tūkstančių pavadinimų, o jūs pertrauka juos į kelis kibirus

841
00:50:35,170 --> 00:50:37,820
, kad jūs turite tik dešimt kiekvieną iš šių tinklų pavadinimus,

842
00:50:37,820 --> 00:50:41,670
visiškai ieško dešimt dalykų bus greičiau nei tūkstantis dalykų.

843
00:50:41,670 --> 00:50:43,740
Ir taip vienas iš artėjančių problema rinkinių ketina iššūkis jums

844
00:50:43,740 --> 00:50:46,100
galvoti apie tai tiksliai, kad net jei, taip,

845
00:50:46,100 --> 00:50:49,520
asimptotiškai ir matematiškai, tai dar tik linijinis,

846
00:50:49,520 --> 00:50:51,700
kuris sucks apskritai, kai bando rasti ką.

847
00:50:51,700 --> 00:50:54,530
Iš tikrųjų, tai bus greičiau nei

848
00:50:54,530 --> 00:50:56,520
nes daliklis.

849
00:50:56,520 --> 00:50:58,310
Ir taip ten vėl bus šis kompromisas

850
00:50:58,310 --> 00:51:01,390
ir tai tarp teorijos ir realybės konfliktas,

851
00:51:01,390 --> 00:51:03,550
ir viena iš rankenėlių pradėti tekinimo šiuo metu į tą semestrą,

852
00:51:03,550 --> 00:51:07,510
yra daugiau tikrovės, vienas, kaip mes tarsi pasirengti semster pabaigoje,

853
00:51:07,510 --> 00:51:09,280
mes pristatome interneto programavimo pasaulį

854
00:51:09,280 --> 00:51:11,530
kur tikrai, veiklos ketina skaičiuoti, nes jūsų naudotojai

855
00:51:11,530 --> 00:51:14,880
pradeda pajusti ir įvertinti prastos dizaino sprendimus.

856
00:51:14,880 --> 00:51:19,950
>> Taigi, kaip jums eiti apie įgyvendinimo susietą maišos lentelę su 31 elementų?

857
00:51:19,950 --> 00:51:22,600
Ir ankstesniame pavyzdyje buvo savavališkai apie gimtadienius.

858
00:51:22,600 --> 00:51:26,190
Jei kas nors turi sausio 1 ir vasario 1 gimtadienį, mes juos šiame kibirą.

859
00:51:26,190 --> 00:51:28,960
Jei tai sausio 2 vasaris 2, kovo 2, mes juos šiame kibirą.

860
00:51:28,960 --> 00:51:32,220
Štai kodėl ji buvo 31 metų. Kaip jūs deklaruojate maišos lentelę?

861
00:51:32,220 --> 00:51:37,480
Tai gali būti gana paprasta, mazgas * Lentelėje yra mano savavališkai pavadinimas [31].

862
00:51:37,480 --> 00:51:42,400
Tai suteikia man 31 patarimų mazgams,

863
00:51:42,400 --> 00:51:45,370
ir kad leidžia man daryti 31 patarimų, kad, susijusius sąrašus

864
00:51:45,370 --> 00:51:48,800
net jei tie tinklai yra iš pradžių NULL.

865
00:51:48,800 --> 00:51:54,860
Ką aš noriu daryti, jei noriu laikyti "Alice", "Bobas", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Na, mes turime tuos dalykus, į kuriuos vyniojami konstrukcija,

867
00:51:57,010 --> 00:52:00,530
nes mes turime Alice Bob, kad rodytų į Charlie, ir kt.

868
00:52:00,530 --> 00:52:04,940
Mes negalime tiesiog vien tik vardus, kad galėčiau sukurti naują struktūrą, pavadintą mazgas čia.

869
00:52:04,940 --> 00:52:08,310
>> Kas yra tikrasis mazgas? Kas yra šioje naujoje susijęs sąrašo mazgas?

870
00:52:08,310 --> 00:52:11,840
Pirmas dalykas, vadinamas žodis, yra asmens vardą.

871
00:52:11,840 --> 00:52:14,340
ILGIS, matyt, susijęs su žmogaus vardą maksimalus ilgis,

872
00:52:14,340 --> 00:52:18,210
kas tai bebūtų, 20, 30, 40 simbolių Crazy kampe atvejais,

873
00:52:18,210 --> 00:52:22,680
+1 yra už ką? Tai tiesiog papildomai NULL personažas, \ 0.

874
00:52:22,680 --> 00:52:27,410
Taigi šis mazgas vyniojimo viduje "kažkas" apie save,

875
00:52:27,410 --> 00:52:29,640
tačiau ji taip pat pareiškia, žymeklį vadinamas Kitas

876
00:52:29,640 --> 00:52:32,580
, kad mes galėtume grandinės Alice Bob su Charlie ir pan.

877
00:52:32,580 --> 00:52:36,700
Gali būti lygus NULL, tačiau nebūtinai turi būti.

878
00:52:36,700 --> 00:52:40,110
Kokių nors klausimų dėl šių maišos lenteles? Taip?

879
00:52:40,110 --> 00:52:46,190
[Studentų klausia klausimą, neįskaitomai] masyvas - geras klausimas.

880
00:52:46,190 --> 00:52:50,120
Kodėl tai char žodis masyvo, o ne tik char *?

881
00:52:50,120 --> 00:52:53,830
Šioje šiek tiek savavališka Pavyzdžiui, aš nenoriu turėti imtis

882
00:52:53,830 --> 00:52:56,190
malloc kiekvienam originalius vardus.

883
00:52:56,190 --> 00:52:59,530
Aš norėjau paskelbti, kad maksimaliai atminties eilutę

884
00:52:59,530 --> 00:53:06,020
, kad galėčiau nukopijuoti į struktūrą Alice \ 0, o ne kovoti su malloc ir laisvo ir panašios.

885
00:53:06,020 --> 00:53:11,710
Bet aš galėtų padaryti, kad jei aš norėjau būti labiau suvokia erdv ÷ je naudoti. Geras klausimas.

886
00:53:11,710 --> 00:53:14,780
Taigi, pabandykime apibendrinti atokiau nuo

887
00:53:14,780 --> 00:53:18,350
ir sutelkti šiandien likusią duomenų struktūrų apskritai

888
00:53:18,350 --> 00:53:21,170
ir kitas problemas, kad mes galime išspręsti naudojant tuos pačius pagrindus

889
00:53:21,170 --> 00:53:24,590
nors duomenų struktūros gali skirtis patys savo duomenis.

890
00:53:24,590 --> 00:53:27,910
>> Taigi paaiškėja, informatikos, medžių yra labai dažnas.

891
00:53:27,910 --> 00:53:29,760
Ir jūs galite galvoti kaip šeimos medį, iš medžio rūšies

892
00:53:29,760 --> 00:53:31,830
kur yra kai kurie šakniavaisiai, kai matriarch arba patriarchas,

893
00:53:31,830 --> 00:53:34,540
močiutė ar senelis ar anksčiau atgal

894
00:53:34,540 --> 00:53:38,880
žemiau kurios yra mama ir tėtis ar įvairios broliai ir seserys ar pan.

895
00:53:38,880 --> 00:53:42,500
Taigi medžio struktūra mazgus ir ji turi vaikų,

896
00:53:42,500 --> 00:53:45,260
paprastai 0 arba daugiau vaikų, kiekvieno mazgo.

897
00:53:45,260 --> 00:53:47,320
Ir kai kurie iš žargono, kad jūs matote šioje nuotraukoje čia

898
00:53:47,320 --> 00:53:50,630
yra mažų vaikų ar grandkids kraštų

899
00:53:50,630 --> 00:53:52,330
kurie neturi rodykles, sklindančius iš jų,

900
00:53:52,330 --> 00:53:55,070
tie vadinamieji lapai, ir visiems į vidų

901
00:53:55,070 --> 00:53:58,790
yra vidinis mazgas, galite skambinti ji kažką išilgai šių linijų.

902
00:53:58,790 --> 00:54:01,430
Tačiau ši struktūra yra gana dažnas. Tai vienas šiek tiek savavališkas.

903
00:54:01,430 --> 00:54:04,930
Mes turime vieną vaiką, turime tris vaikus dešinėje, kairėje

904
00:54:04,930 --> 00:54:06,830
liko du vaikai ant dugno.

905
00:54:06,830 --> 00:54:10,740
Taigi, mes galime turėti skirtingo dydžio medžius, tačiau jei mes pradėsime ką standartizuoti,

906
00:54:10,740 --> 00:54:15,330
ir jūs tikriausiai pamenate, kad tai iš Patriko vaizdo ankstesnis trumpas dvejetainis paieškos

907
00:54:15,330 --> 00:54:19,490
internete, dvejetainis paieškos neturi būti įgyvendintos masyvo

908
00:54:19,490 --> 00:54:21,410
ar popieriaus lapų ant lentos.

909
00:54:21,410 --> 00:54:25,490
Tarkime, kad jūs norėjote saugoti savo numerius į tobulesnę duomenų struktūros.

910
00:54:25,490 --> 00:54:27,680
Jūs galite sukurti tokį medį.

911
00:54:27,680 --> 00:54:35,290
Jūs galite turėti mazgas deklaruotas C, ir kad mazgas gali turėti bent du elementus viduje ji.

912
00:54:35,290 --> 00:54:39,470
Vienas yra skaičius, kurį norite išsaugoti, ir kita yra - gerai, mes turime dar vieną.

913
00:54:39,470 --> 00:54:41,540
Kitas yra jo vaikai.

914
00:54:41,540 --> 00:54:45,150
Taigi čia jau kita duomenų struktūra. Šį kartą mazgas yra apibrėžiamas kaip saugoti skaičių n

915
00:54:45,150 --> 00:54:49,060
ir tada du patarimų, kairėje vaikų ir teisė vaikas.

916
00:54:49,060 --> 00:54:52,100
Ir jie nėra savavališkas. Kas įdomu apie šio medžio?

917
00:54:52,100 --> 00:55:00,550
>> Kas yra modelis, kaip mes nustatyti tai ar kaip Patrick paguldė jį iš savo vaizdo?

918
00:55:00,550 --> 00:55:02,790
Tai tipo akivaizdu, kad kai rūšiavimas vyksta čia,

919
00:55:02,790 --> 00:55:04,460
bet tai, kas paprasta taisyklė? Taip?

920
00:55:04,460 --> 00:55:08,350
[Studentų atsakymas, nesuprantamas]

921
00:55:08,350 --> 00:55:12,040
Tobula. Jei jums pažvelgti į tai, kaip matote kairėje nurodytas nedidelis skaičius,

922
00:55:12,040 --> 00:55:14,690
didelis skaičius kairėje, bet tai tiesa kiekvieno mazgo.

923
00:55:14,690 --> 00:55:20,370
Kiekvieno mazgo, jos kairysis vaikas mažiau nei jis, ir jo teisė vaikas didesnis, nei ji.

924
00:55:20,370 --> 00:55:25,210
Ką tai reiškia dabar, jei noriu ieškote šio duomenų struktūrą, tarkim, numeris 44,

925
00:55:25,210 --> 00:55:29,320
Turiu pradėti ne šaknis, nes, kaip su visais iš šių sudėtingų duomenų struktūrų,

926
00:55:29,320 --> 00:55:31,910
turime tik rodyklę į vieną dalyką, pradžia.

927
00:55:31,910 --> 00:55:35,010
Ir šiuo atveju, pradžia yra šaknis. Tai ne kairėje pusėje,

928
00:55:35,010 --> 00:55:39,530
tai šios struktūros šaknis. Taigi, matau, čia yra 55, ir aš ieškau už 44.

929
00:55:39,530 --> 00:55:41,430
Aš noriu, kuria kryptimi eiti?

930
00:55:41,430 --> 00:55:45,680
Na, aš noriu eiti į kairę, nes akivaizdu, į dešinę bus per didelis.

931
00:55:45,680 --> 00:55:49,050
Taigi pastebėsite čia, jūs tarsi konceptualiai kapojimo per pusę medis

932
00:55:49,050 --> 00:55:51,700
nes jūs niekada į dešinėje pusėje.

933
00:55:51,700 --> 00:55:55,410
Todėl dabar aš einu iš 55 į 33. Tai per mažas skaičius,.

934
00:55:55,410 --> 00:56:01,590
Aš ieškau 44, bet dabar aš žinau, jei 44 yra šio medžio, žinoma, aš galiu eiti į dešinę.

935
00:56:01,590 --> 00:56:04,460
Taigi dar kartą, aš per pusę genėjimo medžių.

936
00:56:04,460 --> 00:56:06,780
Tai beveik identiškas konceptualiai į telefonų knygą.

937
00:56:06,780 --> 00:56:09,510
Tai identiška tai, ką mes padarėme su lentos dokumentus,

938
00:56:09,510 --> 00:56:13,940
bet tai vis sudėtingesnės struktūros, kuri leidžia mums iš tikrųjų

939
00:56:13,940 --> 00:56:16,880
tai skaldyk ir valdyk dizaino algoritmo,

940
00:56:16,880 --> 00:56:19,420
ir iš tiesų, važiuojantiems struktūrą panašaus į tai - šūksniais.

941
00:56:19,420 --> 00:56:22,870
Važiuojantiems struktūra panašaus į tai, kur jis yra tik "eiti tokiu būdu, arba eiti, kad taip"

942
00:56:22,870 --> 00:56:26,870
- visą tą kodą, kad sulenkta savo mintis ją įgyvendinant skyriuje

943
00:56:26,870 --> 00:56:31,270
ar vaikščioti per ją namuose, dvejetainis paieškos, naudojant rekursija arba iteracija,

944
00:56:31,270 --> 00:56:35,060
kaklo skausmas. Rasti vidurinį elementą, tada padaryti savo apvalinimas iki didesnio ar.

945
00:56:35,060 --> 00:56:39,230
>> Yra grožio, nes dabar mes galime naudoti rekursija vėl,

946
00:56:39,230 --> 00:56:43,760
bet daug daugiau švariai. Iš tiesų, jei jūs esate, kurios numeris 55, ir norite rasti 44,

947
00:56:43,760 --> 00:56:48,450
jūs einate į kairę šiuo atveju, tada, ką jūs darote? Paleisti tą patį algoritmą.

948
00:56:48,450 --> 00:56:51,560
Galite patikrinti mazgo vertę, tada pereikite į kairę arba į dešinę.

949
00:56:51,560 --> 00:56:53,670
Tada galite patikrinti mazgo vertę, eikite į kairę arba į dešinę.

950
00:56:53,670 --> 00:56:56,710
Tai puikiai tinka rekursijos.

951
00:56:56,710 --> 00:57:00,920
Taigi, nors mes padarėme praeityje keletas gana savavališkai pavyzdžius, susijusius su rekursija

952
00:57:00,920 --> 00:57:03,430
kad nereikėjo rekursinis su duomenų stuctures

953
00:57:03,430 --> 00:57:07,820
ypač medžių, tai puikus taikant šią problemą idėja,

954
00:57:07,820 --> 00:57:12,920
mažėja jį, o tada spręsti tos pačios rūšies, bet mažesnis, programą.

955
00:57:12,920 --> 00:57:14,590
>> Taigi yra kita duomenų struktūra, kad mes galime pristatyti.

956
00:57:14,590 --> 00:57:18,760
Tai vienas iš pirmo žvilgsnio atrodo paslaptingas, bet tai vienas nuostabus.

957
00:57:18,760 --> 00:57:25,090
Taigi tai yra duomenų struktūra, vadinama trie, trie, kuris yra paveldėtas iš žodžio paieškos,

958
00:57:25,090 --> 00:57:30,210
tariamos naujo pabandyti-VAL, bet tai, ką pasaulis vadina šie dalykai. Šalyse. T-r-i el.

959
00:57:30,210 --> 00:57:35,190
Tai yra medis, struktūra, tam tikros rūšies, bet kiekvienas iš mazgų yra trie

960
00:57:35,190 --> 00:57:41,280
atrodo, kad tai, ką? Ir tai yra šiek tiek klaidinantis, nes tai tipo sutrumpintų.

961
00:57:41,280 --> 00:57:45,960
Bet atrodo, kad kiekvienas šiame trie mazgas yra masyvas.

962
00:57:45,960 --> 00:57:48,840
Ir nors šioje diagramoje autorius neįrodė, tai,

963
00:57:48,840 --> 00:57:54,130
Šiuo atveju, tai trie yra duomenų struktūra, kurių gyvenimo tikslas yra saugoti žodžius

964
00:57:54,130 --> 00:57:57,330
kaip A-L-i-c-e arba B-o-B.

965
00:57:57,330 --> 00:58:02,480
Ir tai, kaip šie duomenys parduotuvės Alice ir Bob ir Charlie ir Anita ir tt

966
00:58:02,480 --> 00:58:06,970
jis naudoja masyvą, pagal kurią saugoti yra trie Alisa,

967
00:58:06,970 --> 00:58:09,820
mes pradedame šakninis mazgas, kuris atrodo kaip masyvo,

968
00:58:09,820 --> 00:58:12,080
ir tai buvo parašyta sutrumpinimą notacijos.

969
00:58:12,080 --> 00:58:15,070
Autorius praleisti abcdefg nes nebuvo su tuo, kuris pavadinimai.

970
00:58:15,070 --> 00:58:19,150
Jie tik parodė, M ir P ir T, tačiau šiuo atveju,

971
00:58:19,150 --> 00:58:22,780
tegul tolti Alisa ir Bobas ir Charlie kai kurių pavadinimų, kad esate čia.

972
00:58:22,780 --> 00:58:25,670
Maksvelo yra iš tikrųjų šioje diagramoje.

973
00:58:25,670 --> 00:58:29,570
Taigi, kaip padarė autorius parduotuvė M--x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Jis ar ji pradėjo šakninis mazgas ir nuėjo į [M], kad maždaug 13, 13 vieta masyve.

975
00:58:36,990 --> 00:58:40,750
Iš ten, yra rodyklė.

976
00:58:40,750 --> 00:58:42,760
Rodyklė į kitą masyvą.

977
00:58:42,760 --> 00:58:47,880
Iš ten indeksuoti į tą masyvo A buvimo vietos, kaip parodyta viršutiniame kairiajame kampe,

978
00:58:47,880 --> 00:58:52,250
ir tada jis ar ji po to, kad žymeklį į kitą masyvą,

979
00:58:52,250 --> 00:58:55,460
ir nuėjo rodyklė vietą X

980
00:58:55,460 --> 00:58:59,840
Tada kitą masyvo vietą W, E, L, L, ir taip toliau,

981
00:58:59,840 --> 00:59:03,090
ir, pagaliau, galime iš tikrųjų bando įdėti paveikslėlį.

982
00:59:03,090 --> 00:59:05,380
Ką mazgas atrodo kaip kodą?

983
00:59:05,380 --> 00:59:11,820
Į trie mazgas yra masyvas rodykles į daugiau mazgų.

984
00:59:11,820 --> 00:59:16,090
Tačiau taip pat turite būti kažkoks Būlio vertė, bent jau šį įgyvendinimą.

985
00:59:16,090 --> 00:59:18,770
Aš atsitikti jį vadinti is_word. Kodėl?

986
00:59:18,770 --> 00:59:22,670
Kadangi, kai jūs įterpiant Maxwell, jūs ne įterpiant

987
00:59:22,670 --> 00:59:25,300
Niekada nieko neduokite į šią duomenų struktūros.

988
00:59:25,300 --> 00:59:27,480
Jūs nesate raštu M. Jūs nesate raštu X

989
00:59:27,480 --> 00:59:30,240
Darote po rodykles.

990
00:59:30,240 --> 00:59:33,360
Rodyklę, kad atstovauja m, rodyklė, kuri atstovauja,

991
00:59:33,360 --> 00:59:36,310
tada rodyklę, kad atstovauja X, tada W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
tačiau tai, ką jums reikia padaryti, pabaigoje yra tarsi eiti, patikrinti, aš pasiekė šią vietą.

993
00:59:41,950 --> 00:59:45,560
Ten buvo žodis, kuris baigiasi čia, duomenų struktūros.

994
00:59:45,560 --> 00:59:48,190
>> Taigi, kas trie tikrai alsuoja ir autorius pasirinko atstovauti

995
00:59:48,190 --> 00:59:51,880
šių mažai trikampių terminuses.

996
00:59:51,880 --> 00:59:56,470
Tai tiesiog reiškia, kad tai, šis trikampis yra čia, tai Būlio vertė tiesa

997
00:59:56,470 --> 00:59:59,200
reiškia, kad, jei jūs einate atgal į medį,

998
00:59:59,200 --> 01:00:02,420
tai reiškia, kad žodį "Maxwell yra.

999
01:00:02,420 --> 01:00:04,870
Tačiau žodis rūšys, pavyzdžiui,

1000
01:00:04,870 --> 01:00:07,970
ne į medį, nes jei aš čia prasideda šakninis mazgas viršuje

1001
01:00:07,970 --> 01:00:14,030
Yra ne f rodyklė, ne o rodyklė, ne o rodyklė. Foo yra ne šiame žodyne vardas.

1002
01:00:14,030 --> 01:00:22,460
Tačiau priešingai, restruktūrizavimo, T-U-R-i-n g. Vėlgi, aš ne aukštesnėje t arba u arba R arba I arba N arba g.

1003
01:00:22,460 --> 01:00:29,820
Bet aš šio duomenų struktūros parduotuvę tikrąjį kelią žemyn čia, šiame mazge vertė - į medį

1004
01:00:29,820 --> 01:00:33,030
nustatant šį boolean vertę is_word tiesa.

1005
01:00:33,030 --> 01:00:35,740
Taigi trie yra šioje labai įdomus meta struktūros rūšies,

1006
01:00:35,740 --> 01:00:39,810
kur jūs tikrai ne saugoti patys žodžiai tokio žodyno.

1007
01:00:39,810 --> 01:00:45,100
Būti aiškus, jūs tiesiog saugoti "taip" arba "ne", yra žodis, kuris baigiasi čia.

1008
01:00:45,100 --> 01:00:46,430
>> Dabar, kas potekstė?

1009
01:00:46,430 --> 01:00:51,120
Jei turite 150.000 žodžių žodyne, kad jūs bandote laikyti atmintyje

1010
01:00:51,120 --> 01:00:53,400
naudojant kažką panašaus į susietą sąrašą,

1011
01:00:53,400 --> 01:00:56,870
jūs ketinate turėti 150.000 mazgų susieta "sąrašą.

1012
01:00:56,870 --> 01:01:00,250
Ir rasti vieną šių žodžių abėcėlės O (n) laiko.

1013
01:01:00,250 --> 01:01:04,370
Linijinis laikas. Bet čia tuo atveju, kai trie,

1014
01:01:04,370 --> 01:01:09,210
kas veikimo laikas rasti žodį?

1015
01:01:09,210 --> 01:01:17,390
Pasirodo grožį čia yra tai, kad net jei turite 149.999 žodžių žodyne jau šiame,

1016
01:01:17,390 --> 01:01:20,170
kaip įgyvendinamos šios duomenų struktūros,

1017
01:01:20,170 --> 01:01:25,560
kiek laiko reikia, kad rasti arba įterpti dar vieną asmenį, į, kad, kaip Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Na, tai tik 5, gal 6 žingsniai užpakalinės pobūdžio.

1019
01:01:30,640 --> 01:01:32,880
Nes kitų pavadinimų struktūros presense

1020
01:01:32,880 --> 01:01:35,340
negauna įterpiant Alisa.

1021
01:01:35,340 --> 01:01:39,640
Be to, surandant Alice, kai yra 150.000 žodžių žodyno

1022
01:01:39,640 --> 01:01:41,960
negauna į savo kelią rasti Alice ne visi,

1023
01:01:41,960 --> 01:01:46,880
nes Alice yra. . . . . čia, nes aš rasiu vertė logiška.

1024
01:01:46,880 --> 01:01:50,920
Ir, jei yra ne boolean true, tada Alisa nėra šio duomenų struktūra, žodžiais.

1025
01:01:50,920 --> 01:01:56,220
Kitaip tariant, veikimo laikas rasti dalykų, ir įterpiant dalykų, į šią naują

1026
01:01:56,220 --> 01:02:01,920
duomenų struktūrą trie O - tai ne n.

1027
01:02:01,920 --> 01:02:05,730
Nes neturi apie Alice 150.000 žmonių presense, atrodo.

1028
01:02:05,730 --> 01:02:11,560
Todėl galime jį vadiname k, kur k yra Ilgiausias anglų kalbos žodis

1029
01:02:11,560 --> 01:02:14,050
kuris paprastai yra ne daugiau kaip 20-kažkas simbolių.

1030
01:02:14,050 --> 01:02:17,940
Taigi k konstanta. Taigi Šventasis Gralis, mes, atrodo, kad rado dabar

1031
01:02:17,940 --> 01:02:26,000
trie nuolat laiko įdėklais, paieška, norint ištrinti.

1032
01:02:26,000 --> 01:02:29,170
Kadangi dalykų jau struktūrą,

1033
01:02:29,170 --> 01:02:32,600
kurie nėra net fiziškai ten. Vėlgi, jie tiesiog tarsi tikrinama ne, "taip" arba "ne",

1034
01:02:32,600 --> 01:02:35,050
neturi įtakos būsimiems jos veikimo laiką.

1035
01:02:35,050 --> 01:02:37,940
>> Bet ten turi būti sugauti, nes kitaip mes būtume ne veltui tiek daug laiko

1036
01:02:37,940 --> 01:02:41,460
nuo visų šių kitų duomenų struktūrų tiesiog pagaliau gauti slaptą Tai nuostabu.

1037
01:02:41,460 --> 01:02:46,410
Taigi, kokia kaina mes mokame pasiekti šitą didybę? Erdvė.

1038
01:02:46,410 --> 01:02:49,010
Šis dalykas yra milžiniška. Ir todėl, kad autorius

1039
01:02:49,010 --> 01:02:52,400
nepateikė čia, pastebėsite, kad visų šių dalykų, kad atrodo kaip masyvai,

1040
01:02:52,400 --> 01:02:55,400
jis nepadarė pailsėti, medžio trie poilsio,

1041
01:02:55,400 --> 01:02:58,060
nes jie tiesiog nėra susiję su istorija.

1042
01:02:58,060 --> 01:03:01,870
Tačiau visų šių mazgų yra super platus, ir kiekvienas medžio mazgas užima

1043
01:03:01,870 --> 01:03:07,780
26 arba iš tikrųjų, gali būti 27 simboliai, nes šiuo atveju aš įskaitant vietos į kabutes

1044
01:03:07,780 --> 01:03:09,980
kad mes galėtume turėti apostrophized žodžius.

1045
01:03:09,980 --> 01:03:14,450
Šiuo atveju, tai yra dideli matricos. Taigi, net jei jie nėra picutured

1046
01:03:14,450 --> 01:03:18,190
tai užima didžiulės RAM.

1047
01:03:18,190 --> 01:03:20,670
Kuris gali būti gerai, especilly moderni įranga,

1048
01:03:20,670 --> 01:03:25,650
bet tai kompromisas. Mes gauname mažiau laiko praleisti daugiau vietos.

1049
01:03:25,650 --> 01:03:28,580
Taigi, kur visa tai vyksta?

1050
01:03:28,580 --> 01:03:32,640
Na, galime daryti - pažiūrėkime čia.

1051
01:03:32,640 --> 01:03:39,510
Darykime šuolis šis vaikinas.

1052
01:03:39,510 --> 01:03:43,450
>> Tikėkite arba ne, taip smagu, kaip C buvo tam tikrą laiką dabar,

1053
01:03:43,450 --> 01:03:48,130
mes pasiekti tašką semestrą, kai atėjo laikas pereiti į ką daugiau modernių.

1054
01:03:48,130 --> 01:03:50,950
Dalykų, dėl aukštesnio lygio. Ir nors per ateinančius porą savaičių

1055
01:03:50,950 --> 01:03:54,580
mes vis dar toliau pasineriame į nurodymus ir atminties valdymas pasaulyje

1056
01:03:54,580 --> 01:03:57,210
gauti, kad komfortą, su kuria mes galime remtis,

1057
01:03:57,210 --> 01:04:01,270
pabaigoje žaidimas galiausiai pristatyti, ironiškai, tai ne kalba.

1058
01:04:01,270 --> 01:04:03,330
Mes praleisti, pavyzdžiui, 10 minučių kalbėti apie HTML.

1059
01:04:03,330 --> 01:04:05,950
HTML yra žymėjimo kalba, ir kokia žymėjimo kalba

1060
01:04:05,950 --> 01:04:10,220
yra šių atvirų skliausteliuose ir uždarų skliausteliuose, kurie sako, kad "šis drąsus" serijos

1061
01:04:10,220 --> 01:04:12,000
"Šis kursyvu" Taip buvo ".

1062
01:04:12,000 --> 01:04:14,250
Tai dar ne viskas, kad intelektualiai įdomu, bet tai super naudingas.

1063
01:04:14,250 --> 01:04:16,650
Ir tai tikrai visur šių dienų.

1064
01:04:16,650 --> 01:04:19,450
Bet kas yra galingas apie HTML pasaulyje ir web programavimas apskritai,

1065
01:04:19,450 --> 01:04:25,910
kurti dinaminius dalykus, rašyti kodą kalbomis, pavyzdžiui, PHP ar Python arba Ruby ar Java ar C #.

1066
01:04:25,910 --> 01:04:30,360
Tikrai, kokia jūsų pasirinkta kalba, ir generuoti HTML dinamiškai.

1067
01:04:30,360 --> 01:04:32,960
Kurti kažką vadinama CSS dinamiškai.

1068
01:04:32,960 --> 01:04:35,810
Cascading Style Sheets, kuris taip pat apie estetika.

1069
01:04:35,810 --> 01:04:41,360
Ir todėl, nors šiandien, jei aš einu Some Like pažįstamas Google.com svetainėje,

1070
01:04:41,360 --> 01:04:46,100
ir aš einu, kūrėjas, vaizdas šaltinis, kuris gal padarei prieš, kad galėtumėte peržiūrėti

1071
01:04:46,100 --> 01:04:49,800
tačiau ketina peržiūrėti šaltinį, ši medžiaga tikriausiai atrodo gana paslaptingas.

1072
01:04:49,800 --> 01:04:55,320
Bet tai yra pagrindinis kodas, kuris įgyvendina Google.com.

1073
01:04:55,320 --> 01:04:57,940
Ant priekio. Ir iš tikrųjų visa tai yra purus estetika stuff.

1074
01:04:57,940 --> 01:05:01,740
Tai yra CSS čia. Jei aš judame žemyn, mes gauti šiek tiek spalvomis stuff.

1075
01:05:01,740 --> 01:05:06,890
Tai yra HTML. "Google" kodas atrodo netvarka, bet jei aš iš tikrųjų atverti kitą langą,

1076
01:05:06,890 --> 01:05:09,380
mes galime pamatyti šiek tiek struktūrą.

1077
01:05:09,380 --> 01:05:12,640
Jei aš atidarau tai padaryti, pastebėsite čia, tai šiek tiek lengviau skaityti.

1078
01:05:12,640 --> 01:05:16,850
Mes ketiname pamatyti iki kol šią žymę, [žodis] yra žymė,

1079
01:05:16,850 --> 01:05:23,520
HTML, galvos, kūno, div, scenarijus, teksto sritį, trukmę, orientuotą, div.

1080
01:05:23,520 --> 01:05:26,770
Ir tai taip pat rūšiuoti paslaptingas išvaizdos, iš pirmo žvilgsnio,

1081
01:05:26,770 --> 01:05:30,890
bet visa tai netvarka taip tam tikrus modelius, ir pakartoti modelius,

1082
01:05:30,890 --> 01:05:33,850
taip, kad, kai mes gauname pagrindai, galėsite rašyti kodą, kaip šis

1083
01:05:33,850 --> 01:05:37,550
ir tada manipuliuoti kaip dar vieną kalbą, vadinamą "JavaScript" kodą.

1084
01:05:37,550 --> 01:05:40,440
Ir JavaScript kalba, kuri veikia viduje naršyklėje

1085
01:05:40,440 --> 01:05:44,380
šiandien, kad mes naudojame Harvardo kursus, kursui prekybos priemonė, kuri "Google Maps" naudoja

1086
01:05:44,380 --> 01:05:48,660
suteiks jums visa krūva dinamikos, "Facebook" suteikia jums parodyti tiesioginius būsenos atnaujinimus,

1087
01:05:48,660 --> 01:05:51,430
"Twitter" naudoja jį parodyti jums tweets iš karto.

1088
01:05:51,430 --> 01:05:53,820
Visa tai mes pradėsime pasineriame.

1089
01:05:53,820 --> 01:05:57,190
Bet ten nuvykti, mes turime suprasti, truputį kažką apie interneto.

1090
01:05:57,190 --> 01:06:01,130
Šis klipas čia yra tik minučių trukmės, ir Tarkime, dabar tai yra, iš tikrųjų,

1091
01:06:01,130 --> 01:06:08,380
kaip internetas veikia kaip kibinimas už tai, kas apie ateiti. Aš tau "Warriors" Net ".

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Lėtas choras muzika ♫]

1093
01:06:14,720 --> 01:06:20,450
[Vyras pasakotojas] Jis atėjo su pranešimu.

1094
01:06:20,450 --> 01:06:23,770
Visi jo paties protokolo.

1095
01:06:23,770 --> 01:06:37,270
[♫ greičiau elektroninės muzikos ♫]

1096
01:06:37,270 --> 01:06:41,330
Jis atėjo į cool ugniasienes pasaulyje, uncaring maršrutizatoriai,

1097
01:06:41,330 --> 01:06:45,690
pavojaus ir kur kas blogiau, nei mirties.

1098
01:06:45,690 --> 01:06:55,400
Jis greitai. Jis stiprus. Jis TCP / IP, ir jis gavo savo adresą.

1099
01:06:55,400 --> 01:06:59,250
Net kariai.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Kitą savaitę, tada. Internetas. Web programavimas. Tai CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]