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

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

3
00:00:04,160 --> 00:00:08,720
[Mae hyn yn CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Mae hyn yn CS50, a dyma'r diwedd wythnos 6.

5
00:00:12,970 --> 00:00:17,970
Felly CS50x, un o Harvard gyrsiau gyntaf yn cynnwys yn y fenter EDX

6
00:00:17,970 --> 00:00:20,590
yn wir debuted Ddydd Llun yma yn y gorffennol.

7
00:00:20,590 --> 00:00:23,460
Os hoffech chi i gael cipolwg ar beth mae pobl eraill ar y Rhyngrwyd

8
00:00:23,460 --> 00:00:27,180
yn awr yn dilyn ynghyd â, gallwch pen i x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Bydd hynny'n eich ailgyfeirio at y lle priodol ar edx.org,

10
00:00:30,350 --> 00:00:34,160
lle yr oedd hyn a chyrsiau eraill o MIT a Berkeley yn byw.

11
00:00:34,160 --> 00:00:38,140
Bydd rhaid i chi gofrestru ar gyfer cyfrif; fe welwch fod y deunydd i raddau helaeth yr un fath

12
00:00:38,140 --> 00:00:42,170
fel eich bod wedi cael y semester, er ychydig wythnosau oedi, gan ein bod yn cael popeth yn barod.

13
00:00:42,170 --> 00:00:46,930
Ond beth fydd myfyrwyr yn CS50x awr yn gweld yn rhyngwyneb yn eithaf fel yr un yma.

14
00:00:46,930 --> 00:00:50,040
Hyn, er enghraifft, yn Zamyla arwain y walkthrough ar gyfer plant 0 set problem.

15
00:00:50,040 --> 00:00:54,230
Ar ôl logio i mewn i edx.org, myfyriwr CS50x yn gweld y math o bethau

16
00:00:54,230 --> 00:00:57,170
byddech yn disgwyl eu gweld mewn cwrs: y ddarlith am y dydd Llun,

17
00:00:57,170 --> 00:01:01,650
darlith ar gyfer dydd Mercher, siorts amrywiol, bydd y setiau broblem, y walkthroughs, ffeiliau PDF.

18
00:01:01,650 --> 00:01:04,459
Yn ogystal, fel y gwelwch yma cyfieithiadau peiriant,

19
00:01:04,459 --> 00:01:08,390
o drawsgrifiadau Saesneg i Tseineaidd, Siapanaeg, Sbaeneg, Eidaleg,

20
00:01:08,390 --> 00:01:12,810
a bagad cyfan o ieithoedd eraill a fydd yn sicr o fod yn amherffaith

21
00:01:12,810 --> 00:01:15,840
wrth i ni gyflwyno mesuryddion deallus programmatically gan ddefnyddio rhywbeth o'r enw API,

22
00:01:15,840 --> 00:01:18,360
neu gais, rhyngwyneb rhaglennu o Google

23
00:01:18,360 --> 00:01:21,360
sy'n ein galluogi i drosi Saesneg i'r ieithoedd eraill.

24
00:01:21,360 --> 00:01:24,100
Ond diolch i ysbryd gwych gan rai gwirfoddolwyr can a throsodd,

25
00:01:24,100 --> 00:01:26,940
pobl ar hap ar y Rhyngrwyd sydd wedi cynnig yn garedig i gymryd rhan

26
00:01:26,940 --> 00:01:30,180
yn y prosiect hwn, byddwn yn raddol wella ansawdd y cyfieithiadau

27
00:01:30,180 --> 00:01:35,790
drwy gael pobl gywiro'r camgymeriadau fod ein cyfrifiaduron wedi eu gwneud.

28
00:01:35,790 --> 00:01:42,330
>> Felly, mae'n troi allan ein bod wedi ychydig o fyfyrwyr yn fwy dangos i fyny ar ddydd Llun nag oeddem yn ei ddisgwyl i ddechrau.

29
00:01:42,330 --> 00:01:48,980
Yn wir, erbyn hyn CS50x mae 100,000 o bobl yn dilyn ar hyd yn y cartref.

30
00:01:48,980 --> 00:01:54,430
Felly, yn sylweddoli eich bod yn i gyd yn rhan o'r dosbarth hwn gyntaf o wneud y cwrs hwn mewn gwyddoniaeth gyfrifiadurol

31
00:01:54,430 --> 00:01:57,370
addysg yn fwy cyffredinol, yn fwy cyffredinol, hygyrch.

32
00:01:57,370 --> 00:02:00,130
A'r gwir amdani yw yn awr, gyda rhai o'r cyrsiau hyn enfawr ar-lein,

33
00:02:00,130 --> 00:02:04,070
maent i gyd yn dechrau gyda'r rhifau hyn yn uchel iawn, gan ein bod yn ymddangos i wedi ei wneud yma.

34
00:02:04,070 --> 00:02:08,759
Ond y nod, yn y pen draw, ar gyfer CS50x yw ein bod yn cael cymaint o bobl at y llinell derfyn ag y bo modd.

35
00:02:08,759 --> 00:02:12,000
Erbyn dylunio, CS50x yn mynd i gael eu cynnig o ddydd Llun gorffennol mae hyn

36
00:02:12,000 --> 00:02:17,430
yr holl ffordd drwy 15 Ebrill, 2013, fel bod Folks sydd ag ymrwymiadau ysgol mewn mannau eraill,

37
00:02:17,430 --> 00:02:20,990
gwaith, teulu, gwrthdaro eraill ac yn y blaen, hyblygrwydd ychydig yn fwy

38
00:02:20,990 --> 00:02:23,640
â hwy i ddeifio i mewn i'r cwrs, sydd, digon yw dweud,

39
00:02:23,640 --> 00:02:30,540
yn eithaf uchelgeisiol ei wneud os mai dim ond dros gyfnod o dri mis yn unig yn ystod semester arferol.

40
00:02:30,540 --> 00:02:34,190
Ond bydd y myfyrwyr yn mynd i'r afael â'r setiau un broblem, edrych ar yr un cynnwys,

41
00:02:34,190 --> 00:02:36,350
cael mynediad i'r un trowsus byr ac yn y blaen.

42
00:02:36,350 --> 00:02:38,990
Felly, yn sylweddoli ein bod i gyd yn wir yn hyn gyda'n gilydd.

43
00:02:38,990 --> 00:02:42,360
Ac nid yw un o nodau diwedd CS50x yw dim ond i gael Folks cymaint

44
00:02:42,360 --> 00:02:45,720
at y llinell derfyn ac yn rhoi iddynt ddealltwriaeth hon newfound o wyddoniaeth gyfrifiadurol

45
00:02:45,720 --> 00:02:49,000
a rhaglennu, ond hefyd i gael eu cael y profiad a rennir.

46
00:02:49,000 --> 00:02:52,010
Un o nodweddion diffiniol o 50 ar y campws, rydym yn gobeithio,

47
00:02:52,010 --> 00:02:56,260
wedi bod yn y math hwn o brofiad cymunedol, er gwell neu er gwaeth, weithiau,

48
00:02:56,260 --> 00:02:59,480
ond yn cael y bobl i droi at y chwith ac i'r dde,

49
00:02:59,480 --> 00:03:01,830
oriau swyddfa a hackathon a'r ffair.

50
00:03:01,830 --> 00:03:04,560
Mae'n ychydig yn galetach i wneud hynny yn bersonol gyda Folks ar-lein,

51
00:03:04,560 --> 00:03:10,580
ond bydd CS50x ben ym mis Ebrill gyda'r cyntaf erioed CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
a fydd addasiad ar-lein o'n syniad y ffair

53
00:03:13,630 --> 00:03:18,250
lle bydd y miloedd o fyfyrwyr i gyd yn cael eu gwahodd i gyflwyno 1 - 2-funud fideo,

54
00:03:18,250 --> 00:03:22,480
naill ai screencast eu prosiect terfynol neu fideo ohonynt yn chwifio hello

55
00:03:22,480 --> 00:03:24,490
a siarad am eu prosiect a demoing iddo,

56
00:03:24,490 --> 00:03:27,610
lawer fel eich rhagflaenwyr wedi ei wneud yma ar y campws yn y ffair,

57
00:03:27,610 --> 00:03:31,400
fel, erbyn diwedd semester, y gobaith yw cael arddangosfa fyd-eang

58
00:03:31,400 --> 00:03:37,080
o brosiectau y myfyrwyr CS50x 'terfynol, yn debyg iawn yr hyn sy'n eich disgwyl ym mis Rhagfyr eleni yma ar y campws.

59
00:03:37,080 --> 00:03:39,680
Felly mwy am hynny yn y misoedd i ddod.

60
00:03:39,680 --> 00:03:43,640
>> Gyda 100,000 o fyfyrwyr, fodd bynnag, daw angen am MD ychydig mwy.

61
00:03:43,640 --> 00:03:47,590
O ystyried eich bod guys yn torri y llwybr yma a chymryd CS50

62
00:03:47,590 --> 00:03:51,630
sawl wythnos cyn rhyddhau deunydd hwn i'r Folks ar EDX,

63
00:03:51,630 --> 00:03:55,330
sylweddoli byddem wrth ein bodd i gynnwys cymaint o'n myfyrwyr hunain ag y bo modd yn y fenter hon,

64
00:03:55,330 --> 00:03:58,720
yn ystod y semester yn ogystal â'r gaeaf a gwanwyn hwn sydd i ddod.

65
00:03:58,720 --> 00:04:01,620
Felly os hoffech chi gymryd rhan mewn CS50x,

66
00:04:01,620 --> 00:04:07,450
yn arbennig yn ymuno i mewn ar CS50x Trafod, y fersiwn EDX o CS50 Trafod,

67
00:04:07,450 --> 00:04:10,140
y mae llawer ohonoch wedi bod yn defnyddio ar y campws, y bwrdd bwletin ar-lein,

68
00:04:10,140 --> 00:04:13,040
croeso i chi wneud pen i'r URL, rhowch wybod i ni pwy ydych chi,

69
00:04:13,040 --> 00:04:16,450
oherwydd byddem wrth ein bodd i adeiladu tîm o fyfyrwyr a staff fel ei gilydd a chyfadran

70
00:04:16,450 --> 00:04:19,630
ar y campws sydd ond yn chwarae ar hyd a helpu allan.

71
00:04:19,630 --> 00:04:21,720
A phan fyddant yn gweld cwestiwn sy'n gyfarwydd iddynt,

72
00:04:21,720 --> 00:04:25,320
byddwch yn clywed yn fyfyriwr yn sôn am ryw nam yn rhywle allan yn rhyw wlad ar y Rhyngrwyd,

73
00:04:25,320 --> 00:04:27,450
ac sy'n taro cloch oherwydd eich bod hefyd wedi bod un mater

74
00:04:27,450 --> 00:04:32,620
yn eich d-hall beth amser yn ôl, gobeithio, yna gallwch chi yn cyd-daro i mewn a rhannu eich profiad eich hun.

75
00:04:32,620 --> 00:04:37,300
Felly, os gwelwch yn dda peidiwch cymryd rhan os hoffech chi.

76
00:04:37,300 --> 00:04:39,360
>> Cyrsiau gwyddoniaeth cyfrifiadurol yn Harvard gael ychydig o draddodiad,

77
00:04:39,360 --> 00:04:44,730
CS50 yn eu plith, o gael rhywfaint o ddillad, dillad, y gellir eu gwisgo gyda balchder

78
00:04:44,730 --> 00:04:49,090
ar ddiwedd y semester, gan ddweud yn eithaf falch eich bod yn gorffen CS50

79
00:04:49,090 --> 00:04:51,830
ac a gymerodd CS50 ac yn y blaen, ac rydym bob amser yn ceisio i gynnwys myfyrwyr

80
00:04:51,830 --> 00:04:54,540
yn y broses hon gymaint ag y bo modd, lle rydym yn gwahodd,

81
00:04:54,540 --> 00:04:56,900
tua'r adeg hon y semester, bydd myfyrwyr i gyflwyno cynlluniau

82
00:04:56,900 --> 00:04:59,330
gan ddefnyddio Photoshop, neu beth bynnag offeryn o ddewis yr hoffech ei ddefnyddio

83
00:04:59,330 --> 00:05:02,330
os ydych yn ddylunydd, i gyflwyno cynlluniau ar gyfer crysau-T a chrysau chwys

84
00:05:02,330 --> 00:05:06,100
a ymbarel a bandanas bach ar gyfer cŵn gennym bellach ac yn y blaen.

85
00:05:06,100 --> 00:05:09,370
Ac mae popeth yn hynny - yr enillwyr bob blwyddyn yn cael eu harddangos yna

86
00:05:09,370 --> 00:05:12,700
ar wefan y cwrs yn store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Mae popeth yn cael ei werthu ar gost yno, ond mae'r wefan yn unig yn rhedeg ei hun

88
00:05:15,790 --> 00:05:18,330
ac yn caniatáu pobl i ddewis y lliwiau a dyluniadau maent yn eu hoffi.

89
00:05:18,330 --> 00:05:20,420
Felly, yr wyf yn meddwl y byddwn ni ond yn rhannu rhai o ddyluniadau y llynedd

90
00:05:20,420 --> 00:05:25,130
a oedd ar y wefan ar wahân yr un yma, sydd yn draddodiad blynyddol.

91
00:05:25,130 --> 00:05:29,410
"Bob dydd rwy'n SEG Faultn" oedd un o'r cyflwyniadau flwyddyn ddiwethaf,

92
00:05:29,410 --> 00:05:32,290
sydd yn dal ar gael yno ar gyfer cyn-fyfyrwyr.

93
00:05:32,290 --> 00:05:35,820
Cawsom yr un yma, "CS50, Sefydlwyd 1989."

94
00:05:35,820 --> 00:05:39,010
Un o'n Bowdens, Rob, roedd yn boblogaidd iawn y llynedd.

95
00:05:39,010 --> 00:05:43,480
"Tîm Bowden" ei eni, y cynllun hwn ei gyflwyno, ymhlith y gwerthwyr gorau.

96
00:05:43,480 --> 00:05:49,040
Fel yr oedd yr un yma. Mae llawer o bobl wedi "Bowden Fever" yn ôl y cofnodion gwerthiant.

97
00:05:49,040 --> 00:05:52,650
Sylweddoli y gallai fod yn awr yn eich dyluniad yno, i fyny ar y Rhyngrwyd.

98
00:05:52,650 --> 00:05:57,510
Mwy o fanylion ar hyn yn y broblem nesaf yn gosod i ddod.

99
00:05:57,510 --> 00:06:00,330
>> Un dull mwy: eich bod wedi cael rhywfaint o amlygiad a gobeithio nawr

100
00:06:00,330 --> 00:06:02,350
rhywfaint o brofiad ymarferol â GDB,

101
00:06:02,350 --> 00:06:04,570
sydd, wrth gwrs, yn debugger ac yn caniatáu i chi drin

102
00:06:04,570 --> 00:06:09,500
eich rhaglen ar lefel weddol isel, yn gwneud pa fathau o bethau?

103
00:06:09,500 --> 00:06:13,030
Beth mae GDB gadael i chi ei wneud?

104
00:06:13,030 --> 00:06:15,030
Yeah? Rhowch i mi rhywbeth. [Ateb Myfyrwyr, annealladwy]

105
00:06:15,030 --> 00:06:18,120
Da. Camu i mewn i swyddogaeth, felly nid oes yn rhaid i deipio rhedeg

106
00:06:18,120 --> 00:06:22,310
ac mae ganddynt yr ergyd rhaglen drwy ei gyfanrwydd, argraffu pethau i'r allbwn safonol.

107
00:06:22,310 --> 00:06:25,190
Yn hytrach, gallwch gamu trwyddo fesul llinell, naill ai deipio nesaf

108
00:06:25,190 --> 00:06:30,300
i fynd linell wrth linell wrth linell neu gam i ddeifio i mewn i swyddogaeth, fel arfer un yr ydych yn ysgrifennu.

109
00:06:30,300 --> 00:06:35,240
Beth arall y mae GDB gadael i chi ei wneud? Yeah? [Ateb Myfyrwyr, annealladwy]

110
00:06:35,240 --> 00:06:38,100
Argraffu newidynnau. Felly, os ydych am wneud introspection bach tu mewn i'ch rhaglen

111
00:06:38,100 --> 00:06:41,500
heb orfod troi at ysgrifennu datganiadau printf i gyd dros y lle,

112
00:06:41,500 --> 00:06:44,600
gallwch argraffu neu arddangos newidyn newidyn.

113
00:06:44,600 --> 00:06:46,710
Beth arall allwch chi ei wneud gyda debugger fel GDB?

114
00:06:46,710 --> 00:06:49,170
[Ateb Myfyrwyr, annealladwy]

115
00:06:49,170 --> 00:06:52,080
Yn union. Gallwch osod breakpoints; allwch ddweud gweithredu egwyl

116
00:06:52,080 --> 00:06:54,020
yn y prif swyddogaeth nac yn y swyddogaeth foo.

117
00:06:54,020 --> 00:06:56,800
Gallwch ddweud gweithredu toriad yn llinell 123.

118
00:06:56,800 --> 00:06:58,950
Ac breakpoints yn dechneg bwerus iawn

119
00:06:58,950 --> 00:07:01,110
oherwydd os oes gennych ymdeimlad cyffredinol o ble mae eich problem

120
00:07:01,110 --> 00:07:05,360
yn ôl pob tebyg yw, nid oes rhaid i wastraff amser camu trwy cyfanrwydd y rhaglen.

121
00:07:05,360 --> 00:07:08,250
Gallwch hanfod neidio i'r dde y fan a'r lle yn dechrau teipio -

122
00:07:08,250 --> 00:07:10,970
camu drwyddi â cham neu nesaf neu yn y blaen.

123
00:07:10,970 --> 00:07:14,340
Ond y ddalfa gyda rhywbeth fel GDB yw ei fod yn helpu i chi, y dynol,

124
00:07:14,340 --> 00:07:16,940
dod o hyd i'ch problemau a dod o hyd i'ch bugs.

125
00:07:16,940 --> 00:07:19,470
Nid yw o reidrwydd yn dod o hyd iddynt gymaint i chi.

126
00:07:19,470 --> 00:07:23,070
>> Felly, rydym yn cyflwyno y style50 diwrnod o'r blaen, sydd yn arf gorchymyn llinell fer yn

127
00:07:23,070 --> 00:07:27,500
sy'n ceisio stylize eich cod ychydig yn fwy lân na chi, y bobl, ei chael ei wneud.

128
00:07:27,500 --> 00:07:29,530
Ond, hefyd, mewn gwirionedd yn unig yn beth esthetig.

129
00:07:29,530 --> 00:07:34,110
Ond mae'n troi allan yna yr offeryn eraill o'r enw Valgrind sydd ychydig yn fwy dirgel i'w defnyddio.

130
00:07:34,110 --> 00:07:36,860
Mae'r allbwn yn atrociously cryptig ar yr olwg gyntaf.

131
00:07:36,860 --> 00:07:39,420
Ond mae'n rhyfeddol o ddefnyddiol, yn enwedig nawr ein bod ni'n ar y rhan o'r term

132
00:07:39,420 --> 00:07:43,080
lle rydych chi'n dechrau defnyddio malloc a dyrannu cof deinamig.

133
00:07:43,080 --> 00:07:45,420
Gall pethau fynd yn iawn, iawn o'i le yn gyflym.

134
00:07:45,420 --> 00:07:49,320
Oherwydd os byddwch yn anghofio i ryddhau eich cof, neu os ydych dereference rhywfaint o pwyntydd NULL,

135
00:07:49,320 --> 00:07:55,770
neu os ydych dereference rhywfaint o pwyntydd garbage, beth yw fel arfer y symptom bod y canlyniadau?

136
00:07:55,770 --> 00:07:59,470
SEG fai. A ydych yn cael y ffeil ganolog i rai nifer o kilobytes neu megabeit

137
00:07:59,470 --> 00:08:02,990
sy'n cynrychioli cyflwr cof eich rhaglen pan chwalodd,

138
00:08:02,990 --> 00:08:05,730
ond mae eich rhaglen yn y pen draw SEG diffygion, wall,

139
00:08:05,730 --> 00:08:08,450
sy'n golygu rhywbeth drwg yn digwydd bron bob amser yn gysylltiedig

140
00:08:08,450 --> 00:08:11,750
at gamgymeriad cof-gysylltiedig a wnaethoch yn rhywle.

141
00:08:11,750 --> 00:08:14,100
Felly Valgrind yn eich helpu i ddod o hyd i bethau fel hyn.

142
00:08:14,100 --> 00:08:17,720
Mae'n arf eich bod yn rhedeg, fel GDB, ar ôl i chi wedi llunio eich rhaglen,

143
00:08:17,720 --> 00:08:20,330
ond yn hytrach na rhedeg eich rhaglen yn uniongyrchol, rydych yn rhedeg Valgrind

144
00:08:20,330 --> 00:08:23,960
ac rydych yn trosglwyddo iddo eich rhaglen, yn union fel chi ei wneud gyda GDB.

145
00:08:23,960 --> 00:08:26,220
Yn awr, y defnydd, er mwyn cael y math gorau o allbwn,

146
00:08:26,220 --> 00:08:30,410
yn ychydig yn hir, felly iawn yno ar ben y sgrin byddwch yn gweld Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" bron yn ddieithriad yn golygu verbose pan fyddwch yn defnyddio rhaglenni ar gyfrifiadur Linux.

148
00:08:35,350 --> 00:08:38,770
Felly, mae'n golygu boeri allan mwy o ddata nag y gallai yn ddiofyn.

149
00:08:38,770 --> 00:08:45,510
"- Gollwng-wirio = llawn." Mae hyn yn unig yw dweud siec am yr holl ollyngiadau cof posibl,

150
00:08:45,510 --> 00:08:49,430
camgymeriadau y gallai fy mod wedi gwneud. Mae hyn, hefyd, yn batrwm cyffredin gyda rhaglenni Linux.

151
00:08:49,430 --> 00:08:52,710
Yn gyffredinol, os oes gennych ymresymiad llinell orchymyn hynny'n "newid",

152
00:08:52,710 --> 00:08:55,830
bod i fod i newid ymddygiad y rhaglen, ac mae'n un llythyren,

153
00:08:55,830 --> 00:09:00,310
mae'n-v, ond os nad yw newid, dim ond drwy ddyluniad y rhaglennydd,

154
00:09:00,310 --> 00:09:05,150
yn air llawn neu gyfres o eiriau, y gorchymyn ymresymiad llinell yn dechrau gyda -.

155
00:09:05,150 --> 00:09:08,190
Yn unig yw'r rhain confensiynau dynol, ond byddwch yn eu gweld yn gynyddol.

156
00:09:08,190 --> 00:09:12,410
Ac yna, yn olaf, "a.out" yw'r enw mympwyol ar gyfer y rhaglen yn yr enghraifft hon.

157
00:09:12,410 --> 00:09:14,640
A dyma rhywfaint o allbwn cynrychioliadol.

158
00:09:14,640 --> 00:09:22,890
>> Cyn i ni edrych ar yr hyn a allai hynny ei olygu, gadewch i mi fynd drosodd i snippet o god dros yma.

159
00:09:22,890 --> 00:09:26,390
A gadewch i mi symud y tu allan o'r ffordd, yn dod yn fuan,

160
00:09:26,390 --> 00:09:32,120
a gadewch i ni edrych ar memory.c, sef yr enghraifft hon byr yma.

161
00:09:32,120 --> 00:09:36,290
Felly, yn y rhaglen hon, gadewch i mi ganolbwyntio ar y swyddogaethau a chwestiynau.

162
00:09:36,290 --> 00:09:39,430
Mae gennym swyddogaeth prif sy'n galw swyddogaeth, f,

163
00:09:39,430 --> 00:09:45,590
ac yna beth mae f myned rhagof i wneuthur, yn Saesneg ychydig yn dechnegol?

164
00:09:45,590 --> 00:09:49,760
Beth mae f symud ymlaen i wneud?

165
00:09:49,760 --> 00:09:53,680
Beth am Byddaf yn dechrau gyda llinell 20, ac nad yw lleoliad y seren yw o bwys,

166
00:09:53,680 --> 00:09:56,720
ond byddaf yn unig fod yn gyson yma gyda darlith diwethaf.

167
00:09:56,720 --> 00:09:59,910
Beth yw llinell 20 yn i ni? Ar yr ochr chwith. Byddwn yn torri i lawr ymhellach.

168
00:09:59,910 --> 00:10:02,410
Int * x: beth mae hynny'n ei wneud?

169
00:10:02,410 --> 00:10:04,940
Iawn. Mae'n datgan pwyntydd, a nawr gadewch i ni fod hyd yn oed yn fwy technegol.

170
00:10:04,940 --> 00:10:10,230
Beth mae'n ei olygu, yn concretely, i ddatgan pwyntydd? Rhywun arall?

171
00:10:10,230 --> 00:10:15,050
Yeah? [Ateb Myfyrwyr, annealladwy] Rhy bell.

172
00:10:15,050 --> 00:10:17,060
Felly, rydych chi'n darllen ar yr ochr dde-law yr arwydd cyfartal.

173
00:10:17,060 --> 00:10:20,290
Gadewch i ni ganolbwyntio yn unig ar y chwith, yn union ar int * x.

174
00:10:20,290 --> 00:10:24,700
Hyn yn "datgan" pwyntydd, ond yn awr gadewch i ni neidio yn ddyfnach i diffiniad hwnnw.

175
00:10:24,700 --> 00:10:28,330
Beth mae hynny'n ei concretely, yn dechnegol yn ei olygu? Yeah?

176
00:10:28,330 --> 00:10:31,940
[Ateb Myfyrwyr, annealladwy]

177
00:10:31,940 --> 00:10:35,090
Iawn. Mae'n paratoi i arbed gyfeiriad yn y cof.

178
00:10:35,090 --> 00:10:40,680
Da. A gadewch i ni gymryd hyn un cam ymhellach; mae'n datgan amrywiol, x, dyna 32 catiau.

179
00:10:40,680 --> 00:10:44,440
Ac yr wyf yn gwybod ei fod yn 32 catiau oherwydd -?

180
00:10:44,440 --> 00:10:47,390
Dyw hi ddim oherwydd ei fod yn int, am ei fod yn pwyntydd yn yr achos hwn.

181
00:10:47,390 --> 00:10:49,650
Gyd-ddigwyddiad ei fod yn yr un peth gyda int,

182
00:10:49,650 --> 00:10:51,970
ond y ffaith fod yna seren mae golygu bod hwn yn pwyntydd

183
00:10:51,970 --> 00:10:57,300
ac yn y peiriant, fel gyda llawer o gyfrifiaduron, ond nid pob un, awgrymiadau 32 ddarnau.

184
00:10:57,300 --> 00:11:01,850
Ar fwy caledwedd modern fel y Macs diweddaraf, cyfrifiaduron diweddaraf, a allai fod gennych 64-bit awgrymiadau,

185
00:11:01,850 --> 00:11:04,160
ond yn y peiriant, y pethau hyn 32 ddarnau.

186
00:11:04,160 --> 00:11:08,380
Felly, byddwn yn safoni ar hynny. Mwy concretely, mae'r stori yn mynd fel a ganlyn:

187
00:11:08,380 --> 00:11:10,820
Rydym yn "datgan" pwyntydd, beth mae hynny'n ei olygu?

188
00:11:10,820 --> 00:11:12,810
Rydym yn paratoi i storio cyfeiriad cof.

189
00:11:12,810 --> 00:11:15,530
Beth mae hynny'n ei olygu?

190
00:11:15,530 --> 00:11:19,810
Rydym yn creu x elwir yn newidyn sy'n cymryd 32 catiau

191
00:11:19,810 --> 00:11:23,810
a fydd yn fuan storio cyfeiriad yn gyfanrif.

192
00:11:23,810 --> 00:11:26,470
A dyna mae'n debyg tua mor fanwl ag y gallwn ei gael.

193
00:11:26,470 --> 00:11:31,810
Mae'n iawn symud ymlaen i symleiddio'r byd a dim ond dweud datgan pwyntydd o'r enw x.

194
00:11:31,810 --> 00:11:35,380
Datgan pwyntydd, ond yn sylweddoli ac yn deall beth sy'n digwydd mewn gwirionedd ar

195
00:11:35,380 --> 00:11:38,490
hyd yn oed dim ond y rhai cymeriadau ychydig.

196
00:11:38,490 --> 00:11:42,040
>> Yn awr, hyn yn un 'bron yn ychydig yn haws, hyd yn oed er ei fod yn fynegiant hirach.

197
00:11:42,040 --> 00:11:48,160
Felly beth mae hyn yn ei wneud, sydd wedi tynnu sylw at awr: "malloc (10 * sizeof (canolradd));" Ie?

198
00:11:48,160 --> 00:11:52,350
[Ateb Myfyrwyr, annealladwy]

199
00:11:52,350 --> 00:11:58,250
Da. A byddaf yn mynd ag ef yno. Mae'n dyrannu darn o gof am ddeng gyfanrifau.

200
00:11:58,250 --> 00:12:02,190
Ac yn awr gadewch i ni deifio mewn ychydig dyfnach, mae'n dyrannu cyfran o gof am ddeng gyfanrifau.

201
00:12:02,190 --> 00:12:05,390
Beth yw malloc yna dychwelyd?

202
00:12:05,390 --> 00:12:10,390
Y cyfeiriad y darn, neu, yn fwy concretely, cyfeiriad y beit gyntaf y darn.

203
00:12:10,390 --> 00:12:14,080
Sut felly ydw i, y rhaglennydd, i wybod ble y darn yn dod i ben cof?

204
00:12:14,080 --> 00:12:18,340
Rwy'n gwybod ei bod yn cydgyffwrdd. Malloc, drwy ddiffiniad, yn rhoi i chi darn cyffiniol o gof.

205
00:12:18,340 --> 00:12:21,240
Dim bylchau ynddo. Mae gennych fynediad i bob beit yn y darn,

206
00:12:21,240 --> 00:12:26,760
gefn wrth gefn wrth gefn, ond sut ydw i'n gwybod ble ddiwedd y darn o gof yw?

207
00:12:26,760 --> 00:12:28,850
Pan fyddwch yn defnyddio malloc? [Ateb Myfyrwyr, annealladwy] Da.

208
00:12:28,850 --> 00:12:30,670
Nid ydych yn ei wneud. Mae'n rhaid i chi gofio.

209
00:12:30,670 --> 00:12:35,960
Rhaid i mi gofio fy mod yn defnyddio'r gwerth 10, ac nid wyf yn hyd yn oed yn ymddangos i wedi gwneud hynny yma.

210
00:12:35,960 --> 00:12:41,000
Ond mae'r cyfrifoldeb yn gyfan gwbl ar mi. Strlen, yr ydym wedi dod yn ychydig yn ddibynnol ar gyfer llinynnau,

211
00:12:41,000 --> 00:12:45,860
yn gweithio yn unig oherwydd y confensiwn hwn o gael \ 0

212
00:12:45,860 --> 00:12:48,840
neu y cymeriad NUL arbennig, NUL, ar ddiwedd y llinyn.

213
00:12:48,840 --> 00:12:51,740
Nid yw hynny'n dal am ychydig ddarnau mympwyol o gof.

214
00:12:51,740 --> 00:12:58,590
Mae i fyny i chi. Felly llinell 20, yna, yn dyrannu cyfran o gof

215
00:12:58,590 --> 00:13:02,590
sy'n gallu storio 10 cyfanrifau, ac mae'n storio cyfeiriad y beit 1

216
00:13:02,590 --> 00:13:05,610
y darn o gof yn y newidyn x a elwir yn.

217
00:13:05,610 --> 00:13:11,140
Ergo, sy'n rhoi syniad. Felly llinell 21, yn anffodus, roedd camgymeriad.

218
00:13:11,140 --> 00:13:16,110
Ond yn gyntaf, beth y mae'n ei wneud? Mae'n dweud siop ar leoliad 10, 0 mynegeio,

219
00:13:16,110 --> 00:13:19,480
o darn o gof a elwir yn y 0 x gwerth.

220
00:13:19,480 --> 00:13:21,510
>> Felly, yn sylwi ar ychydig o bethau yn mynd ymlaen.

221
00:13:21,510 --> 00:13:25,420
Er bod x yn pwyntydd, yn cofio o'r cwpl o wythnosau yn ôl

222
00:13:25,420 --> 00:13:29,440
y gallwch barhau i ddefnyddio'r nodiant sgwâr array-arddull braced.

223
00:13:29,440 --> 00:13:36,180
Oherwydd dyna mewn gwirionedd law-fer nodiant ar gyfer y rhifyddeg pwyntydd yn fwy cryptic-edrych.

224
00:13:36,180 --> 00:13:40,320
lle y byddem yn gwneud rhywbeth fel hyn: Cymerwch y x cyfeiriad, yn symud 10 man drosodd,

225
00:13:40,320 --> 00:13:44,550
wedyn yn mynd yno i ba bynnag gyfeiriad yn cael ei storio yn y lleoliad hwnnw.

226
00:13:44,550 --> 00:13:48,090
Ond a dweud y gwir, mae hyn yn erchyll i ddarllen a chael gyfforddus ag ef.

227
00:13:48,090 --> 00:13:52,900
Felly, yn y byd fel arfer yn defnyddio y cromfachau sgwâr yn unig oherwydd ei fod gymaint yn fwy dynol-gyfeillgar i ddarllen.

228
00:13:52,900 --> 00:13:55,140
Ond dyna beth sy'n wir yn mynd ymlaen o dan y cwfl;

229
00:13:55,140 --> 00:13:58,190
x Nid yw cyfeiriad, amrywiaeth, fel y cyfryw.

230
00:13:58,190 --> 00:14:02,410
Felly, mae hyn yn storio 0 ar leoliad 10 yn x.

231
00:14:02,410 --> 00:14:06,120
Pam mae hyn yn ddrwg? Yeah?

232
00:14:06,120 --> 00:14:17,370
[Ateb Myfyrwyr, annealladwy] Yn union.

233
00:14:17,370 --> 00:14:21,100
Byddwn ond yn dyrannu 10 ints, ond rydym yn cyfrif o 0 wrth raglennu yn C,

234
00:14:21,100 --> 00:14:25,690
felly mae gennych fynediad i 0 10 1 2 3 4 5 6 7 8 9, ond peidio.

235
00:14:25,690 --> 00:14:30,270
Felly naill ai'r rhaglen yn mynd i fai seg neu nid yw'n.

236
00:14:30,270 --> 00:14:32,900
Ond dydyn ni ddim yn gwybod, mae hyn yn fath o ymddygiad nondeterministic.

237
00:14:32,900 --> 00:14:35,600
Mae'n dibynnu ar p'un a ydym yn cael lwcus.

238
00:14:35,600 --> 00:14:40,650
Os yw'n troi allan nad yw'r system weithredu oes ots os byddaf yn defnyddio y beit ychwanegol,

239
00:14:40,650 --> 00:14:43,360
er nad yw wedi rhoi i mi, efallai na fydd fy rhaglen damwain.

240
00:14:43,360 --> 00:14:46,780
Mae'n amrwd, mae'n buggy, ond efallai nad ydych yn gweld y symptom,

241
00:14:46,780 --> 00:14:48,960
neu efallai y byddwch yn ei weld unwaith yn unig mewn blwc.

242
00:14:48,960 --> 00:14:51,230
Ond y gwir amdani yw bod y nam yn, mewn gwirionedd, yno.

243
00:14:51,230 --> 00:14:54,320
Ac mae'n wir yn anodd os ydych wedi ysgrifennu rhaglen yr ydych am ei fod yn gywir,

244
00:14:54,320 --> 00:14:58,840
eich bod wedi gwerthu y rhaglen fod pobl yn defnyddio bod pob siwrnai mewn blwc damweiniau

245
00:14:58,840 --> 00:15:02,450
oherwydd, wrth gwrs, nid yw hyn yn dda. Yn wir, os oes gennych ffôn Android neu iPhone

246
00:15:02,450 --> 00:15:05,550
ac rydych yn llwytho i lawr apps y dyddiau hyn, os ydych chi erioed wedi cael app yn unig roi'r gorau iddi,

247
00:15:05,550 --> 00:15:10,040
yn sydyn yn diflannu, sef bron bob amser o ganlyniad i ryw fater y cof-gysylltiedig,

248
00:15:10,040 --> 00:15:12,830
lle y rhaglennydd sgriwio i fyny ac i dereferenced pwyntydd

249
00:15:12,830 --> 00:15:18,670
ei fod ef neu na ddylai hi gael, a chanlyniad iOS neu Android ydy at jyst ladd y rhaglen yn gyfan gwbl

250
00:15:18,670 --> 00:15:23,080
yn hytrach nag ymddygiad risg undefined neu ryw fath o gyfaddawd diogelwch.

251
00:15:23,080 --> 00:15:25,950
>> Mae un bug eraill yn y rhaglen ar wahân yr un yma.

252
00:15:25,950 --> 00:15:30,180
Beth arall ydw i wedi sgriwio i fyny yn y rhaglen hon?

253
00:15:30,180 --> 00:15:32,740
Nid wyf wedi ymarfer yr hyn yr wyf wedi pregethu. Yeah?

254
00:15:32,740 --> 00:15:34,760
[Ateb Myfyrwyr, annealladwy] Da.

255
00:15:34,760 --> 00:15:36,880
Nid wyf wedi rhyddhau y cof. Felly, y rheol y fawd yn awr

256
00:15:36,880 --> 00:15:43,150
rhaid iddo fod ar unrhyw adeg rydych yn galw malloc, rhaid i chi ffonio am ddim pan fyddwch yn gwneud defnyddio'r cof.

257
00:15:43,150 --> 00:15:45,610
Yn awr, byddai pan rwyf eisiau i ryddhau y cof?

258
00:15:45,610 --> 00:15:49,780
Yn ôl pob tebyg, gan dybio y llinell gyntaf yn gywir, byddai arnaf eisiau ei wneud yma.

259
00:15:49,780 --> 00:15:55,710
Gan nad allwn, er enghraifft, yn ei wneud i lawr yma. Pam?

260
00:15:55,710 --> 00:15:57,860
Yn unig allan o gwmpas. Felly, er ein bod yn sôn am awgrymiadau,

261
00:15:57,860 --> 00:16:04,830
mae hwn yn wythnos 2 neu 3 mater, lle mae x yn unig o ran cwmpas y tu mewn i'r braces cyrliog lle cafodd ei ddatgan.

262
00:16:04,830 --> 00:16:11,000
Felly, ni allwch bendant rhyddhau yno. Fy unig gyfle i ryddhau ei fod yn fras ar ôl llinell 21.

263
00:16:11,000 --> 00:16:15,170
Mae hon yn rhaglen weddol syml; roedd yn eithaf hawdd ar ôl i chi fath o lapio eich meddwl

264
00:16:15,170 --> 00:16:17,870
o gwmpas yr hyn y mae'r rhaglen yn ei wneud, lle mae'r camgymeriadau yn.

265
00:16:17,870 --> 00:16:20,500
A hyd yn oed os nad ydych yn ei weld ar y cyntaf, gobeithio ei fod yn ychydig yn amlwg yn awr

266
00:16:20,500 --> 00:16:23,870
bod y camgymeriadau yn cael eu 'n bert haws datrys y problemau a gwneud yn hawdd.

267
00:16:23,870 --> 00:16:28,720
Ond pan fydd rhaglen yn fwy na 12 llinellau hir, mae'n 50 llinell o hyd, 100 llinellau hir,

268
00:16:28,720 --> 00:16:31,150
cerdded drwy eich llinell wrth linell cod, gan feddwl drwyddo yn rhesymegol,

269
00:16:31,150 --> 00:16:35,110
yn bosibl ond nid yn arbennig o hwyl i'w gwneud, yn gyson yn chwilio am bryfed,

270
00:16:35,110 --> 00:16:38,340
ac mae hefyd yn anodd i'w wneud, a dyna pam yn offeryn fel Valgrind yn bodoli.

271
00:16:38,340 --> 00:16:40,900
Gadewch i mi fynd yn ei flaen ac yn gwneud hyn: gadewch i mi agor fy ffenest terfynell,

272
00:16:40,900 --> 00:16:45,400
a gadewch i mi nid yn unig yn rhedeg cof, oherwydd cof yn ymddangos i fod yn iawn.

273
00:16:45,400 --> 00:16:49,180
Im 'yn cael lwcus. Mynd at y beit ychwanegol ar ddiwedd y rhesi

274
00:16:49,180 --> 00:16:51,060
nid yw'n ymddangos i fod gormod o broblemau.

275
00:16:51,060 --> 00:16:56,370
Ond gadewch i mi, serch hynny, yn gwneud, gwiriad pwyll a dim ond olygu i wirio

276
00:16:56,370 --> 00:16:58,320
a yw hyn mewn gwirionedd yn gywir.

277
00:16:58,320 --> 00:17:04,690
>> Felly, gadewch i ni wneud valgrind-v - gollwng-wirio = llawn,

278
00:17:04,690 --> 00:17:07,520
ac yna enw'r rhaglen yn yr achos hwn nid yw cof, a.out.

279
00:17:07,520 --> 00:17:10,760
Felly, gadewch i mi fynd ymlaen a gwneud hyn. Hit Enter.

280
00:17:10,760 --> 00:17:14,109
Annwyl Dduw. Mae hyn yn ei allbwn, a dyma'r hyn y crybwyllais yn gynharach.

281
00:17:14,109 --> 00:17:17,550
Ond, os ydych yn dysgu darllen drwy bob un o'r lol yma,

282
00:17:17,550 --> 00:17:20,760
rhan fwyaf o hyn yn unig yw cynnyrch diagnostig nad ddim yn bod ddiddorol.

283
00:17:20,760 --> 00:17:24,829
Beth yw eich llygad yn awyddus iawn i fod yn edrych amdano yw unrhyw sôn am wall neu yn annilys.

284
00:17:24,829 --> 00:17:26,800
Geiriau sy'n awgrymu problemau.

285
00:17:26,800 --> 00:17:29,340
Ac yn wir, gadewch i ni weld beth sy'n mynd o'i le i lawr yma.

286
00:17:29,340 --> 00:17:35,230
Mae gen i grynodeb o ryw fath, "a ddefnyddir yn ymadael:. 40 bytes mewn 1 bloc"

287
00:17:35,230 --> 00:17:38,750
Dydw i ddim yn siŵr iawn beth yw bloc eto, ond 40 bytes

288
00:17:38,750 --> 00:17:41,260
mewn gwirionedd yn teimlo fel y gallwn i chyfrif i maes ble mae hynny'n dod.

289
00:17:41,260 --> 00:17:45,030
40 bytes. Pam yn 40 bytes cael eu defnyddio ar ymadael?

290
00:17:45,030 --> 00:17:48,780
Ac yn fwy penodol, os ydym yn sgrolio i lawr yma,

291
00:17:48,780 --> 00:17:54,520
pam fy mod wedi bendant colli 40 bytes? Yeah?

292
00:17:54,520 --> 00:17:59,520
[Ateb Myfyrwyr, annealladwy] Perfect. Yeah, yn union.

293
00:17:59,520 --> 00:18:03,540
Roedd deg cyfanrifau, a phob un o'r rheiny yw faint o 4, neu 32 darnau,

294
00:18:03,540 --> 00:18:08,300
felly rydw i wedi colli yn union 40 bytes oherwydd, fel y cynigiwyd, nid wyf wedi galw am ddim.

295
00:18:08,300 --> 00:18:13,460
Dyna un bug, ac yn awr gad i ni edrych i lawr ychydig ymhellach a gweld nesaf at hyn,

296
00:18:13,460 --> 00:18:16,900
"Annilys ysgrifennu maint 4." Nawr beth yw hwn?

297
00:18:16,900 --> 00:18:21,150
Mae'r cyfeiriad yn cael ei fynegi nodiant sylfaenol beth, mae'n debyg?

298
00:18:21,150 --> 00:18:23,640
Mae hyn yn hecsadegol, ac unrhyw tro y byddwch yn gweld nifer dechrau gyda 0x,

299
00:18:23,640 --> 00:18:29,410
mae'n golygu hecsadegol, a gwnaethom hynny mewn ffordd yn ôl, yr wyf yn meddwl, pset 0 yn adran o gwestiynau,

300
00:18:29,410 --> 00:18:34,090
a oedd dim ond i wneud ymarfer warmup, trosi degol i'r hecs i ddeuaidd ac yn y blaen.

301
00:18:34,090 --> 00:18:39,220
Hecsadegol, dim ond drwy gonfensiwn dynol, yn cael ei ddefnyddio fel arfer i gynrychioli awgrymiadau

302
00:18:39,220 --> 00:18:41,570
neu, yn fwy cyffredinol, yn mynd i'r afael. Mae'n dim ond confensiwn,

303
00:18:41,570 --> 00:18:45,340
oherwydd ei fod ychydig yn haws i'w ddarllen, mae'n ychydig yn fwy cryno na rhywbeth fel degol,

304
00:18:45,340 --> 00:18:47,720
ac deuaidd yn ddiwerth ar gyfer rhan fwyaf o bobl i'w defnyddio.

305
00:18:47,720 --> 00:18:50,840
Felly, yn awr beth yw ystyr hyn? Wel, mae'n edrych fel mae 'na ysgrifennu annilys

306
00:18:50,840 --> 00:18:54,480
maint 4 ar linell 21 o memory.c.

307
00:18:54,480 --> 00:18:59,180
Felly, gadewch i ni fynd yn ôl i linell 21, ac yn wir, dyma yw bod ysgrifennu annilys.

308
00:18:59,180 --> 00:19:02,640
Felly nid Valgrind yn mynd yn llwyr dal fy llaw a dweud wrthyf beth yw'r ateb yw,

309
00:19:02,640 --> 00:19:05,520
ond mae'n canfod fy mod yn gwneud yn ysgrifennu annilys.

310
00:19:05,520 --> 00:19:08,800
Rwy'n cyffwrdd 4 bytes na ddylwn fod, ac i bob golwg mae hynny oherwydd,

311
00:19:08,800 --> 00:19:13,960
fel y nodwyd gennych, yr wyf i'n ei wneud [10] yn lle [9] maximally

312
00:19:13,960 --> 00:19:16,660
neu [0] neu rywbeth yn y canol.

313
00:19:16,660 --> 00:19:19,690
Gyda Valgrind, yn sylweddoli unrhyw tro y byddwch yn yn awr yn ysgrifennu rhaglen

314
00:19:19,690 --> 00:19:24,190
sy'n defnyddio pwyntyddion a defnyddio cof, a malloc yn fwy penodol,

315
00:19:24,190 --> 00:19:27,080
sicr yn mynd i'r arfer o redeg yma o hyd

316
00:19:27,080 --> 00:19:30,890
ond yn hawdd iawn copïo a gludo gorchymyn Valgrind

317
00:19:30,890 --> 00:19:32,650
i weld os oes rhai camgymeriadau i mewn 'na.

318
00:19:32,650 --> 00:19:34,820
A bydd yn cael ei llethol bob tro y byddwch yn gweld y cynnyrch,

319
00:19:34,820 --> 00:19:39,430
ond dim ond gramadegu drwy weledol yr holl allbwn a gweld os ydych yn gweld yn sôn o wallau

320
00:19:39,430 --> 00:19:43,190
neu rybuddion neu annilys neu ar goll.

321
00:19:43,190 --> 00:19:46,200
Unrhyw eiriau sy'n swnio'n fel chi sgriwio i fyny yn rhywle.

322
00:19:46,200 --> 00:19:48,580
Felly sylweddoli bod yn offeryn newydd yn eich pecyn cymorth.

323
00:19:48,580 --> 00:19:51,270
>> Nawr ar ddydd Llun, cawsom criw cyfan o Folks dod i fyny yma

324
00:19:51,270 --> 00:19:53,150
ac maent yn cynrychioli'r syniad o restr cysylltiedig.

325
00:19:53,150 --> 00:20:00,970
Ac rydym yn cyflwyno rhestr sy'n gysylltiedig fel ateb i ba broblem?

326
00:20:00,970 --> 00:20:04,590
Yeah? [Ateb Myfyrwyr, annealladwy] Da.

327
00:20:04,590 --> 00:20:06,530
Ni all araeau gael cof ychwanegu atynt.

328
00:20:06,530 --> 00:20:09,440
Os byddwch yn dyrannu amrywiaeth o maint 10, dyna i gyd a gewch.

329
00:20:09,440 --> 00:20:13,690
Gallwch ffonio swyddogaeth fel realloc os ydych yn dechrau o'r enw malloc,

330
00:20:13,690 --> 00:20:17,580
a gall geisio tyfu ar y rhesi os oes lle tuag at y diwedd

331
00:20:17,580 --> 00:20:21,610
nad oes neb arall yn ei ddefnyddio, ac os nad oes, bydd yn unig ddod o hyd i ddarn mwy rhywle arall.

332
00:20:21,610 --> 00:20:25,040
Ond yna bydd yn anfon copi o bob o'r rhai bytes i'r casgliad newydd.

333
00:20:25,040 --> 00:20:28,310
Mae hyn yn swnio fel ateb gywir iawn.

334
00:20:28,310 --> 00:20:34,790
Pam mae hyn yn anneniadol?

335
00:20:34,790 --> 00:20:36,940
Yr wyf yn golygu ei fod yn gweithio, mae pobl wedi datrys y broblem hon.

336
00:20:36,940 --> 00:20:40,710
Pam mae angen i ni ddatrys ddydd Llun gyda rhestrau cysylltiedig? Yeah?

337
00:20:40,710 --> 00:20:44,060
[Ateb Myfyrwyr, annealladwy] Gallai gymryd amser hir.

338
00:20:44,060 --> 00:20:49,260
Yn wir, unrhyw adeg ydych yn ffonio malloc neu realloc neu calloc, sydd eto un arall,

339
00:20:49,260 --> 00:20:52,470
unrhyw adeg i chi, y rhaglen, yn siarad â'r system weithredu,

340
00:20:52,470 --> 00:20:54,310
rydych yn tueddu i arafu'r rhaglen i lawr.

341
00:20:54,310 --> 00:20:57,470
Ac os ydych chi'n gwneud y mathau hyn o bethau mewn dolenni, ydych wirioneddol yn arafu pethau i lawr.

342
00:20:57,470 --> 00:21:00,740
Nid ydych yn mynd i sylwi ar hyn ar gyfer y symlaf o "helo byd" rhaglenni fath,

343
00:21:00,740 --> 00:21:04,300
ond mewn rhaglenni llawer mwy, yn gofyn i'r system weithredu eto ac eto ar gyfer cof

344
00:21:04,300 --> 00:21:07,520
neu roi yn ôl dro ar ôl tro yn tueddu i beidio â bod yn beth da.

345
00:21:07,520 --> 00:21:11,210
Byd Gwaith, 'i' jyst fath o ddeallusol - mae'n wastraff llwyr o amser.

346
00:21:11,210 --> 00:21:16,490
Pam dyrannu cof mwy a mwy o, risg copïo popeth yn y casgliad newydd,

347
00:21:16,490 --> 00:21:21,980
os oes gennych ddewis arall sy'n gadael i chi dyrannu cof yn unig cymaint ag y byddwch ei angen mewn gwirionedd?

348
00:21:21,980 --> 00:21:24,130
Felly, mae pwyntiau cadarnhaol a negyddol i mewn yma.

349
00:21:24,130 --> 00:21:26,730
Un o'r pwyntiau cadarnhaol yn awr yw bod gennym egni.

350
00:21:26,730 --> 00:21:29,100
Nid yw'n fater lle y darnau o gof yw bod yn rhad ac am ddim,

351
00:21:29,100 --> 00:21:32,070
Gallaf ddidoli o greu'r friwsion bara trwy awgrymiadau

352
00:21:32,070 --> 00:21:34,470
i linyn fy rhestr cysylltiedig cyfan at ei gilydd.

353
00:21:34,470 --> 00:21:36,470
Ond yr wyf yn talu o leiaf un pris.

354
00:21:36,470 --> 00:21:40,060
>> Beth sydd rhaid i mi roi'r gorau i gael rhestrau cysylltiedig?

355
00:21:40,060 --> 00:21:42,470
Yeah? [Ateb Myfyrwyr, annealladwy] Da.

356
00:21:42,470 --> 00:21:45,650
Mae angen mwy o gof. Nawr mae angen lle ar gyfer hyn awgrymiadau,

357
00:21:45,650 --> 00:21:47,900
ac yn achos y rhestr hon super cysylltiedig syml

358
00:21:47,900 --> 00:21:51,410
nad yw ond yn ceisio i storio cyfanrifau, sydd 4 bytes, rydym yn dal i ddweud

359
00:21:51,410 --> 00:21:54,240
yn dda, pwyntydd yw 4 bytes, felly rwyf bellach wedi dyblu yn llythrennol

360
00:21:54,240 --> 00:21:57,290
faint o gof ei angen arnaf yn unig i storio y rhestr hon.

361
00:21:57,290 --> 00:21:59,680
Ond unwaith eto, mae hwn yn tradeoff cyson mewn gwyddoniaeth gyfrifiadurol

362
00:21:59,680 --> 00:22:03,440
rhwng amser a gofod a datblygu, ymdrech ac adnoddau eraill.

363
00:22:03,440 --> 00:22:06,630
Beth arall anfantais o ddefnyddio rhestr sy'n gysylltiedig? Yeah?

364
00:22:06,630 --> 00:22:10,150
[Ateb Myfyrwyr, annealladwy]

365
00:22:10,150 --> 00:22:12,600
Da. Nid yw mor hawdd i gael mynediad. Gallwn bellach trosoledd

366
00:22:12,600 --> 00:22:15,530
wythnos 0 egwyddorion megis rhannu a gorchfygu.

367
00:22:15,530 --> 00:22:18,220
Ac yn fwy penodol, chwiliad deuaidd. Oherwydd hyd yn oed er ein bod yn fodau dynol

368
00:22:18,220 --> 00:22:20,400
gallu gweld yn fras lle mae canol y rhestr hon,

369
00:22:20,400 --> 00:22:25,840
y cyfrifiadur yn unig yn gwybod bod y rhestr hon cysylltiedig yn dechrau yn y cyfeiriad a elwir yn gyntaf.

370
00:22:25,840 --> 00:22:28,250
A dyna 0x123 neu rywbeth fel 'na.

371
00:22:28,250 --> 00:22:30,990
A gall yr unig ffordd y rhaglen yn dod o hyd i'r elfen canol

372
00:22:30,990 --> 00:22:33,350
yw mewn gwirionedd yn chwilio'r rhestr gyfan.

373
00:22:33,350 --> 00:22:35,500
Ac hyd yn oed wedyn, yn llythrennol rhaid i chwilio'r rhestr gyfan oherwydd

374
00:22:35,500 --> 00:22:38,950
hyd yn oed ar ôl i chi gyrraedd yr elfen ganol trwy ddilyn yr awgrymiadau,

375
00:22:38,950 --> 00:22:42,380
chi, y rhaglen, yn cael unrhyw syniad am faint y rhestr hon, o bosibl,

376
00:22:42,380 --> 00:22:45,250
nes i chi gyrraedd y diwedd, a sut ydych chi'n gwybod programmatically

377
00:22:45,250 --> 00:22:48,600
eich bod ar ddiwedd y rhestr sy'n gysylltiedig?

378
00:22:48,600 --> 00:22:51,120
Mae yna pwyntydd NULL arbennig, felly unwaith eto, mae confensiwn.

379
00:22:51,120 --> 00:22:53,870
Yn hytrach na defnyddio'r pwyntydd, nid ydym yn sicr am iddo fod rhywfaint o werth garbage

380
00:22:53,870 --> 00:22:57,750
pwyntio oddi ar y llwyfan yn rhywle, rydym am iddo fod â llaw i lawr, NULL,

381
00:22:57,750 --> 00:23:01,530
er mwyn i ni gael y derfynfa yn y strwythur data felly rydym yn gwybod o ble mae'n dod i ben.

382
00:23:01,530 --> 00:23:03,410
>> Beth os ydym am i drin hyn?

383
00:23:03,410 --> 00:23:05,980
Rydym yn gwneud y rhan fwyaf o hyn yn weledol, ac â phobl,

384
00:23:05,980 --> 00:23:07,630
ond beth os ydym am wneud yn mewnosod?

385
00:23:07,630 --> 00:23:12,360
Felly y rhestr wreiddiol oedd 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Beth os ydym wedyn am ofod ar gyfer nifer malloc 55, yn nod ar ei gyfer,

387
00:23:16,730 --> 00:23:20,730
ac yna rydym am i fewnosod 55 yn y rhestr yn union fel y gwnaethom ar ddydd Llun?

388
00:23:20,730 --> 00:23:23,690
Sut rydym yn gwneud hyn? Wel, Anita ddaeth i fyny ac mae hi yn y bôn cerdded ar y rhestr.

389
00:23:23,690 --> 00:23:27,500
Dechreuodd ar yr elfen gyntaf, yna bydd y nesaf, a'r nesaf, a'r nesaf, a'r nesaf, a'r nesaf.

390
00:23:27,500 --> 00:23:29,500
Yn olaf daro yr ochr chwith yr holl ffordd i lawr

391
00:23:29,500 --> 00:23:34,480
a gwireddu oh, mae hyn yn NULL. Felly, trin pwyntydd beth oedd angen ei wneud?

392
00:23:34,480 --> 00:23:37,980
Roedd y person a oedd ar y diwedd, rhif 34, sydd ei angen ei law chwith a godir

393
00:23:37,980 --> 00:23:46,220
i bwynt yn 55, 55 angen eu braich chwith yn pwyntio i lawr i fod yn newydd NULL Terminator. Done.

394
00:23:46,220 --> 00:23:49,540
Eithaf hawdd i fewnosod 55 i mewn i restr datrys.

395
00:23:49,540 --> 00:23:51,800
A sut gallai hyn edrych?

396
00:23:51,800 --> 00:23:55,690
>> Gadewch i mi fynd yn ei flaen ac agor rhai enghraifft cod yma.

397
00:23:55,690 --> 00:23:58,120
'N annhymerus' agor i fyny gedit, a gadewch i mi agor dwy ffeil yn gyntaf.

398
00:23:58,120 --> 00:24:02,050
Mae un yn list1.h, a gadewch i mi dim ond atgoffa mai hwn oedd y darn o god

399
00:24:02,050 --> 00:24:04,920
ein bod yn eu defnyddio i gynrychioli nod.

400
00:24:04,920 --> 00:24:13,040
Mae nod wedi ddau yn int o'r enw n, a elwir yn pwyntydd nesaf mai dim ond yn cyfeirio at y peth nesaf yn y rhestr.

401
00:24:13,040 --> 00:24:15,450
Mae hynny bellach yn a. Ffeil h. Pam?

402
00:24:15,450 --> 00:24:19,090
Mae confensiwn hwn, ac nid ydym wedi manteisio ar hyn yn swm enfawr ein hunain,

403
00:24:19,090 --> 00:24:22,220
ond y person a ysgrifennodd swyddogaethau printf ac eraill

404
00:24:22,220 --> 00:24:27,150
rhoi fel rhodd i'r byd holl swyddogaethau hynny drwy ysgrifennu ffeil o'r enw stdio.h.

405
00:24:27,150 --> 00:24:30,950
Ac yna mae string.h, ac yna mae map.h, ac mae hyn i gyd ffeil h

406
00:24:30,950 --> 00:24:34,410
y gallech fod wedi gweld neu eu defnyddio yn ystod y tymor a ysgrifennwyd gan bobl eraill.

407
00:24:34,410 --> 00:24:38,470
Fel arfer yn y. Ffeiliau h yn unig bethau fel typedefs

408
00:24:38,470 --> 00:24:42,310
neu ddatganiadau o fathau arfer neu ddatganiadau o cysonion.

409
00:24:42,310 --> 00:24:47,890
Nid ydych yn rhoi gweithrediadau swyddogaethau 'mewn ffeiliau header.

410
00:24:47,890 --> 00:24:50,570
Yn eich rhoi chi, yn hytrach, dim ond eu prototeipiau.

411
00:24:50,570 --> 00:24:53,050
Rydych yn rhoi pethau yr hoffech ei rhannu gyda'r byd beth sydd ei angen arnynt

412
00:24:53,050 --> 00:24:55,640
er mwyn llunio eu cod. Felly, dim ond i gael i mewn i'r arfer,

413
00:24:55,640 --> 00:24:59,110
rydym yn penderfynu gwneud yr un peth. Does dim llawer yn list1.h,

414
00:24:59,110 --> 00:25:02,070
ond rydym wedi rhoi rhywbeth a allai fod o ddiddordeb i bobl yn y byd

415
00:25:02,070 --> 00:25:05,030
sydd am ddefnyddio ein gweithrediad rhestr cysylltiedig.

416
00:25:05,030 --> 00:25:08,040
Yn awr, yn list1.c, ni fyddaf yn mynd trwy'r holl beth

417
00:25:08,040 --> 00:25:11,390
oherwydd ei fod braidd yn hir, y rhaglen hon, ond gadewch i ni redeg go iawn yn gyflym wrth yr anogwr.

418
00:25:11,390 --> 00:25:15,720
Gadewch i mi lunio Rhestr1, gadewch i mi wedyn yn rhedeg Rhestr1, a'r hyn y byddwch yn gweld ei

419
00:25:15,720 --> 00:25:18,070
rydym wedi efelychu Rhaglen fechan syml yma

420
00:25:18,070 --> 00:25:20,990
mae hynny'n mynd i fy ngalluogi i ychwanegu a dileu rhifau i restr.

421
00:25:20,990 --> 00:25:24,310
Felly, gadewch i mi fynd yn ei flaen a theipiwch 3 ar gyfer y ddewislen 3.

422
00:25:24,310 --> 00:25:27,880
Wyf i am osod y rhif - gadewch i ni wneud y rhif cyntaf, a oedd yn 9,

423
00:25:27,880 --> 00:25:30,550
ac erbyn hyn rwy'n gwybod y rhestr bellach yn 9.

424
00:25:30,550 --> 00:25:33,760
Gadewch i mi fynd yn ei flaen ac yn gwneud rhywbeth arall fewnosod, felly yr wyf gyrraedd 3 opsiwn ddewislen.

425
00:25:33,760 --> 00:25:36,760
Pa rif ydw i am ei fewnosod? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. A byddaf yn gwneud dim ond un yn fwy.

427
00:25:39,220 --> 00:25:41,720
Gadewch i mi rhowch y rhif 22.

428
00:25:41,720 --> 00:25:45,850
Felly, mae gennym y dechreuad y rhestr cysylltiedig a oedd gennym yn ffurf sleidiau funud yn ôl.

429
00:25:45,850 --> 00:25:48,740
Sut mae hyn yn gosod mewn gwirionedd yn digwydd?

430
00:25:48,740 --> 00:25:52,000
Yn wir, mae 22 yn awr ar ddiwedd y rhestr.

431
00:25:52,000 --> 00:25:55,050
Felly, yr ydym yn dweud stori ar y llwyfan ar ddydd Llun a recapped unig yn awr

432
00:25:55,050 --> 00:25:57,460
Mae'n rhaid i mewn gwirionedd yn digwydd yn y cod.

433
00:25:57,460 --> 00:25:59,700
Gadewch i ni edrych. Gadewch i mi sgroliwch i lawr yn y ffeil hon.

434
00:25:59,700 --> 00:26:01,720
Byddwn yn fach dros rai o'r swyddogaethau,

435
00:26:01,720 --> 00:26:05,630
ond byddwn yn mynd i lawr i, dyweder, y swyddogaeth rhowch.

436
00:26:05,630 --> 00:26:11,720
>> Gadewch i ni weld sut yr ydym yn mynd ati i fewnosod nod newydd i'r rhestr hon cysylltiedig.

437
00:26:11,720 --> 00:26:14,550
Ble mae'r rhestr datgan? Wel, gadewch i sgrolio holl ffordd i fyny ar y brig,

438
00:26:14,550 --> 00:26:19,970
ac yn sylwi bod fy rhestr cysylltiedig yn cael ei datgan yn ei hanfod fel pwyntydd sengl sy'n dechrau NULL.

439
00:26:19,970 --> 00:26:23,180
Felly rwy'n defnyddio newidyn byd-eang yma, sydd yn gyffredinol rydym wedi pregethu yn erbyn

440
00:26:23,180 --> 00:26:25,280
oherwydd ei fod yn gwneud eich cod yn flêr ychydig i gynnal,

441
00:26:25,280 --> 00:26:29,080
mae'n fath o ddiog, fel arfer, ond nid yw'n ddiog ac nid ei fod yn anghywir ac nid yw'n ddrwg

442
00:26:29,080 --> 00:26:33,660
os pwrpas eich rhaglen unig mewn bywyd yw i efelychu un rhestr cysylltiedig.

443
00:26:33,660 --> 00:26:35,460
Sef yr union beth rydym yn ei wneud.

444
00:26:35,460 --> 00:26:39,100
Felly, yn hytrach na ddatgan hyn yn y brif ac yna rhaid i ni ei drosglwyddo bob swyddogaeth

445
00:26:39,100 --> 00:26:42,640
rydym wedi ysgrifennu yn y rhaglen hon, rydym yn hytrach yn sylweddoli oh, gadewch i ni dim ond yn ei gwneud yn fyd-eang

446
00:26:42,640 --> 00:26:47,060
oherwydd holl bwrpas y rhaglen hon yw dangos un a dim ond un rhestr cysylltiedig.

447
00:26:47,060 --> 00:26:50,700
Felly sy'n teimlo'n iawn. Dyma fy prototeipiau, ac ni fyddwn yn mynd drwy'r rhain i gyd,

448
00:26:50,700 --> 00:26:55,800
ond yr wyf yn ysgrifennu, swyddogaeth dileu swyddogaeth ddod o hyd i, swyddogaeth mewnosoder, a swyddogaeth daith.

449
00:26:55,800 --> 00:26:59,080
Ond gadewch i ni nawr fynd yn ôl i lawr i'r swyddogaeth nodwch

450
00:26:59,080 --> 00:27:01,490
a gweld sut mae hyn yn un yn gweithio yma.

451
00:27:01,490 --> 00:27:09,940
Mewnosod ar-lein - yma rydym yn mynd.

452
00:27:09,940 --> 00:27:12,850
Mewnosod. Felly nid yw'n cymryd unrhyw ddadleuon, oherwydd ein bod ni'n mynd i ofyn i

453
00:27:12,850 --> 00:27:15,930
y tu mewn defnyddiwr y swyddogaeth hon ar gyfer y rhif y maent am i fewnosod.

454
00:27:15,930 --> 00:27:19,410
Ond yn gyntaf, rydym yn paratoi i roi rhywfaint o le.

455
00:27:19,410 --> 00:27:22,050
Mae hyn yn fath o gopi a gludo o'r enghraifft arall.

456
00:27:22,050 --> 00:27:25,110
Yn yr achos hwn, rydym yn dyrannu int; y tro hwn rydym yn ddyrannu nod.

457
00:27:25,110 --> 00:27:27,910
Dwi ddim yn cofio faint o bytes yn nod yw, ond mae hynny'n iawn.

458
00:27:27,910 --> 00:27:30,460
Gall Sizeof ffigur fod allan i mi.

459
00:27:30,460 --> 00:27:33,340
A pham ydw i'n gwirio NULL yn unol 120?

460
00:27:33,340 --> 00:27:37,530
Beth allai fynd o'i le yn unol 119? Yeah?

461
00:27:37,530 --> 00:27:40,530
[Ateb Myfyrwyr, annealladwy]

462
00:27:40,530 --> 00:27:43,440
Da. Gallai Dim ond yn achos yr wyf wedi gofyn am lawer o gof lawer

463
00:27:43,440 --> 00:27:47,020
neu nad yw rhywbeth yn anghywir a bod y system weithredu oes bytes ddigon i roi i mi,

464
00:27:47,020 --> 00:27:50,640
felly mae'n arwydd cymaint drwy ddychwelyd NULL, ac os nad wyf yn gwirio ar gyfer y

465
00:27:50,640 --> 00:27:54,710
a Fi jyst blindly mynd ymlaen i ddefnyddio'r cyfeiriad a gyfyd, gallai fod yn null.

466
00:27:54,710 --> 00:27:58,400
Gallai fod rhywfaint o werth anhysbys, nid yn beth da oni bai fy mod -

467
00:27:58,400 --> 00:28:00,590
Ni fydd mewn gwirionedd yn werth anhysbys. Gallai fod yn NULL, felly nid wyf am

468
00:28:00,590 --> 00:28:02,550
i gam-drin ac risg dereferencing hynny.

469
00:28:02,550 --> 00:28:07,410
Os digwydd hynny, Fi jyst yn dychwelyd a byddwn yn esgus fel doeddwn i ddim yn mynd yn ôl unrhyw cof o gwbl.

470
00:28:07,410 --> 00:28:12,270
>> Fel arall, yr wyf yn dweud wrth y defnyddiwr rif imi ac i fewnosod, galwaf ein GetInt hen ffrind,

471
00:28:12,270 --> 00:28:15,530
ac yna mae hyn oedd y gystrawen newydd yr ydym cyflwyno ar ddydd Llun.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n' yn golygu cymryd y cyfeiriad a roddwyd i chi gan malloc

473
00:28:20,320 --> 00:28:23,490
sy'n cynrychioli beit cyntaf o wrthrych nod newydd,

474
00:28:23,490 --> 00:28:26,860
ac yna mynd i'r cae o'r enw n.

475
00:28:26,860 --> 00:28:35,270
Mae cwestiwn trivia bach: Mae hyn yn cyfateb i'r hyn a llinell yn fwy cryptic o god?

476
00:28:35,270 --> 00:28:38,110
Sut arall yr wyf wedi ysgrifennu hyn? Eisiau cymryd stab?

477
00:28:38,110 --> 00:28:41,480
[Ateb Myfyrwyr, annealladwy]

478
00:28:41,480 --> 00:28:44,870
Da. Gan ddefnyddio'r n., Ond nid yw'n mor syml â hyn.

479
00:28:44,870 --> 00:28:47,090
Beth ydw i'n gyntaf bydd angen i ei wneud? [Ateb Myfyrwyr, annealladwy]

480
00:28:47,090 --> 00:28:52,730
Da. Angen i mi ei wneud * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Felly, mae hyn yn ei ddweud pwyntydd newydd yn amlwg yn gyfeiriad. Pam?

482
00:28:55,610 --> 00:28:59,520
Oherwydd ei fod yn cael ei ddychwelyd gan malloc. Mae'r newptr * yn dweud "mynd yno,"

483
00:28:59,520 --> 00:29:02,970
ac yna unwaith y byddwch chi yno, yna gallwch ddefnyddio'r mwy cyfarwydd. n,

484
00:29:02,970 --> 00:29:05,730
ond mae hyn dim ond yn edrych ychydig yn hyll, yn enwedig os ydym bodau dynol yn mynd i

485
00:29:05,730 --> 00:29:10,360
tynnu awgrymiadau gyda saethau drwy'r amser, y byd wedi safoni ar y saeth nodiant,

486
00:29:10,360 --> 00:29:12,320
sy'n gwneud yn union yr un peth.

487
00:29:12,320 --> 00:29:16,070
Felly, dim ond defnyddiwch y -> nodiant pan fydd y peth ar y chwith mae pwyntydd.

488
00:29:16,070 --> 00:29:18,790
Fel arall, os ei fod yn strwythur go iawn, defnyddiwch y n..

489
00:29:18,790 --> 00:29:25,800
Ac yna mae hyn: Pam ydw i'n ymgychwyn newptr-> nesaf i NULL?

490
00:29:25,800 --> 00:29:28,610
Nid ydym eisiau llaw chwith yn hongian oddi ar y diwedd y cyfnod.

491
00:29:28,610 --> 00:29:31,630
Rydym am ei pwyntio yn syth i lawr, sy'n golygu diwedd y rhestr

492
00:29:31,630 --> 00:29:34,980
gallai fod ar hyn o nod, felly rydym yn well gwneud yn siŵr ei fod yn null.

493
00:29:34,980 --> 00:29:38,460
Ac, yn gyffredinol, ymgychwyn eich newidynnau neu eich aelodau data a structs

494
00:29:38,460 --> 00:29:40,470
i rywbeth yn unig arfer da.

495
00:29:40,470 --> 00:29:45,170
Dim ond gosod garbage yn bodoli ac yn parhau i fodoli yn gyffredinol yn cael chi mewn trafferth

496
00:29:45,170 --> 00:29:48,650
os byddwch yn anghofio i wneud rhywbeth yn nes ymlaen.

497
00:29:48,650 --> 00:29:51,590
>> Dyma ychydig o achosion. Mae hyn, eto, yw swyddogaeth mewnosod,

498
00:29:51,590 --> 00:29:54,930
a'r peth cyntaf i mi chwilio am yw os y newidyn a elwir yn gyntaf,

499
00:29:54,930 --> 00:29:58,240
y newidyn fyd-eang yn NULL, mae hynny'n golygu nid oes rhestr cysylltiedig.

500
00:29:58,240 --> 00:30:02,460
Nid ydym wedi gosod unrhyw rifau, felly mae'n ddibwys i fewnosod y nifer hwn ar hyn o bryd

501
00:30:02,460 --> 00:30:05,240
yn y rhestr, oherwydd mae'n perthyn ar ddechrau'r rhestr.

502
00:30:05,240 --> 00:30:08,100
Felly, mae hyn oedd pan Anita yn unig oedd yn sefyll i fyny yma yn unig, esgus

503
00:30:08,100 --> 00:30:11,390
nad oes neb arall i fyny yma ar y llwyfan nes i ni ddyrannu nod,

504
00:30:11,390 --> 00:30:13,940
yna gallai godi ei llaw am y tro cyntaf,

505
00:30:13,940 --> 00:30:17,420
os yw pawb arall wedi dod i fyny ar y llwyfan ar ei hôl hi ar ddydd Llun.

506
00:30:17,420 --> 00:30:22,900
Nawr yma, dyma ychydig o gwiriad lle mae'n rhaid i mi ddweud os yw gwerth y nod newydd o n

507
00:30:22,900 --> 00:30:27,370
yn <gwerth n yn y nod cyntaf cyfredol,

508
00:30:27,370 --> 00:30:29,930
mae hynny'n golygu bod yn rhestr cysylltiedig sydd wedi dechrau.

509
00:30:29,930 --> 00:30:32,330
Mae o leiaf un nod yn y rhestr, ond mae hyn yn guy newydd

510
00:30:32,330 --> 00:30:37,230
perthyn ger ei fron, felly mae angen i symud pethau o gwmpas.

511
00:30:37,230 --> 00:30:43,450
Mewn geiriau eraill, os bydd y rhestr wedi dechrau gyda dim ond, gadewch i ni ddweud,

512
00:30:43,450 --> 00:30:48,100
dim ond y rhif 17, dyna'r - mewn gwirionedd, gallwn wneud hyn yn fwy clir.

513
00:30:48,100 --> 00:30:56,010
Os rydym yn dechrau ein stori gyda pwyntydd yma a elwir yn gyntaf,

514
00:30:56,010 --> 00:30:59,870
ac i ddechrau mae'n NULL, ac rydym yn rhowch y rhif 9,

515
00:30:59,870 --> 00:31:02,510
y rhif 9 yn amlwg yn perthyn ar ddechrau'r rhestr.

516
00:31:02,510 --> 00:31:07,400
Felly, gadewch i esgus rydym yn unig malloced y cyfeiriad neu'r rhif 9 ac yn ei roi yma.

517
00:31:07,400 --> 00:31:13,170
Os gyntaf yw 9 gan ddiofyn, y senario cyntaf i ni drafod yn unig yn golygu gadewch i bwynt y boi yma,

518
00:31:13,170 --> 00:31:15,790
gadael hyn fel NULL, yn awr mae gennym y rhif 9.

519
00:31:15,790 --> 00:31:18,280
Y rhif nesaf rydym am i fewnosod yn 17 oed.

520
00:31:18,280 --> 00:31:22,420
17 yn perthyn dros yma, felly rydym yn mynd i gael i wneud ychydig o sarn rhesymegol drwy hyn.

521
00:31:22,420 --> 00:31:26,060
Felly, gadewch i ni yn lle hynny, cyn i ni wneud hynny, gadewch i ni esgus ein bod am i fewnosod y rhif 8.

522
00:31:26,060 --> 00:31:28,650
>> Felly, dim ond ar gyfer mwyn hwylustod, rwy'n i'n mynd i dynnu yma.

523
00:31:28,650 --> 00:31:30,760
Ond cofiwch, gall malloc roi fwyaf yn unrhyw le.

524
00:31:30,760 --> 00:31:33,460
Ond ar gyfer mwyn tynnu ar, byddaf yn rhoi yma.

525
00:31:33,460 --> 00:31:38,440
Felly esgus Rwyf wedi neilltuo yn unig nod ar gyfer y nifer 8; mae hyn yn NULL yn ddiofyn.

526
00:31:38,440 --> 00:31:42,800
Beth nawr rhaid i hyn ddigwydd? Mae cwpl o bethau.

527
00:31:42,800 --> 00:31:47,090
Rydym yn gwneud y camgymeriad ar y llwyfan ddydd Llun lle y gwnaethom ddiweddaru pwyntydd fel hyn,

528
00:31:47,090 --> 00:31:51,890
Yna, yn gwneud hyn, ac yna rydym yn hawlio - rydym yn amddifad pawb arall ar y llwyfan.

529
00:31:51,890 --> 00:31:54,350
Oherwydd eich bod Methu â - trefn y gweithrediadau yma yn bwysig,

530
00:31:54,350 --> 00:31:58,760
oherwydd erbyn hyn rydym wedi colli hyn 9 nod yn unig yw hynny fath o fel y bo'r angen yn y gofod.

531
00:31:58,760 --> 00:32:01,150
Felly, nid oedd hyn yn y dull cywir ar ddydd Llun.

532
00:32:01,150 --> 00:32:03,330
Rydym yn gyntaf rhaid i ni wneud rhywbeth arall.

533
00:32:03,330 --> 00:32:06,280
Mae cyflwr y byd yn edrych fel hyn. I ddechrau, 8 wedi cael ei ddyrannu.

534
00:32:06,280 --> 00:32:10,550
Beth fyddai'r ffordd well o mewnosod 8?

535
00:32:10,550 --> 00:32:14,720
Yn hytrach na ddiweddaru'r pwyntydd yn gyntaf, dim ond ddiweddaru'r un yma yn lle hynny.

536
00:32:14,720 --> 00:32:17,720
Felly mae angen llinell o god sy'n mynd i droi y cymeriad NULL

537
00:32:17,720 --> 00:32:22,020
i mewn i pwyntydd go iawn sydd wedi tynnu sylw at nod 9,

538
00:32:22,020 --> 00:32:27,970
ac yna gallwn yn ddiogel newid cyntaf i bwyntio at y boi yma.

539
00:32:27,970 --> 00:32:31,330
Nawr mae gennym restr, rhestr cysylltiedig, o ddwy elfen.

540
00:32:31,330 --> 00:32:33,580
A beth mae hyn mewn gwirionedd yn edrych fel yma?

541
00:32:33,580 --> 00:32:36,900
Os ydym yn edrych ar y cod, yn sylwi fy mod i wedi gwneud yn union hynny.

542
00:32:36,900 --> 00:32:41,970
Yr wyf wedi dweud newptr, ac yn y stori hon, newptr yn tynnu sylw at y boi.

543
00:32:41,970 --> 00:32:45,520
>> Felly, gadewch i mi dynnu un peth arall, a dylwn fod wedi gadael ystafell ychydig yn fwy ar gyfer hyn.

544
00:32:45,520 --> 00:32:48,540
Felly, maddau y darlun ychydig bach.

545
00:32:48,540 --> 00:32:52,140
Mae hyn yn guy cael ei alw'n newptr.

546
00:32:52,140 --> 00:32:57,940
Dyna'r ydym yn datgan newidyn ychydig linellau yn gynharach, yn unol - dim ond uwch na 25.

547
00:32:57,940 --> 00:33:03,430
Ac mae'n pwyntio i 8. Felly, pan fyddaf yn dweud newptr-> nesaf, mae hynny'n golygu mynd i'r strwythur

548
00:33:03,430 --> 00:33:07,910
sy'n cael ei sylw at y newptr, felly dyma ni, yn mynd yno.

549
00:33:07,910 --> 00:33:13,990
Yna y saeth yn ei ddweud yn cael y cae nesaf, ac yna caiff y = yn ei ddweud roi pa werth yno?

550
00:33:13,990 --> 00:33:17,280
Y gwerth a oedd yn gyntaf; pa werth oedd yn gyntaf?

551
00:33:17,280 --> 00:33:21,930
Weinidog yn tynnu sylw at y nod yma, felly mae hynny'n golygu y dylai hyn bellach yn pwyntio at y nod.

552
00:33:21,930 --> 00:33:25,660
Mewn geiriau eraill, yr hyn yn edrych er ei fod yn llanast chwerthinllyd gyda fy llawysgrifen,

553
00:33:25,660 --> 00:33:28,620
beth syniad syml o ddim ond symud y saethau o amgylch

554
00:33:28,620 --> 00:33:31,560
yn cyfateb i cod gyda dim ond y leinin un.

555
00:33:31,560 --> 00:33:38,110
Storiwch beth sydd yn gyntaf yn y cae nesaf ac yna diweddaru beth gyntaf mewn gwirionedd yn ei.

556
00:33:38,110 --> 00:33:40,900
Gadewch i ni fynd yn ei flaen ac yn gyflym ymlaen drwy rai o hyn,

557
00:33:40,900 --> 00:33:44,220
ac yn edrych yn unig ar hyn gosod cynffon ar hyn o bryd.

558
00:33:44,220 --> 00:33:51,210
Gadewch i ni dybio cyrraedd y pwynt lle yr wyf yn canfod bod y cae nesaf o ryw nod yn null.

559
00:33:51,210 --> 00:33:53,410
Ac ar y pwynt hwn yn y stori, a manylion fy mod yn glossing dros

560
00:33:53,410 --> 00:33:58,170
yw fy mod wedi cyflwyno arall pwyntydd i fyny yma yn unol 142, pwyntydd rhagflaenydd.

561
00:33:58,170 --> 00:34:01,320
Yn y bôn, ar y pwynt hwn yn y stori, unwaith y bydd y rhestr yn cael hir,

562
00:34:01,320 --> 00:34:04,800
Yr wyf yn fath o angen i gerdded gyda dau bysedd oherwydd os byddaf yn mynd yn rhy bell,

563
00:34:04,800 --> 00:34:08,219
cofio yn un rhestr hir, ni allwch fynd yn ôl.

564
00:34:08,219 --> 00:34:13,659
Felly, y syniad o predptr yw fy mys ar y chwith, ac newptr - nid newptr.

565
00:34:13,659 --> 00:34:17,199
Arall pwyntydd sy'n dyma yw fy mys eraill, a Im 'jyst fath o gerdded y rhestr.

566
00:34:17,199 --> 00:34:22,179
Dyna pam sy'n bodoli. Ond gadewch i ni dim ond ystyried un o'r achosion symlach yma.

567
00:34:22,179 --> 00:34:26,620
Os faes y pwyntydd nesaf yn NULL, beth yw'r goblygiadau rhesymegol?

568
00:34:26,620 --> 00:34:30,840
Os ydych yn croesi y rhestr hon ac rydych yn taro pwyntydd NULL?

569
00:34:30,840 --> 00:34:35,780
Rydych chi ar ddiwedd y rhestr, ac felly mae'r cod wedyn i atodi elfen hon un ychwanegol

570
00:34:35,780 --> 00:34:41,230
yw y bydd rhyw fath o 'n athrylithgar gymryd y nod y mae ei pwyntydd nesaf NULL,

571
00:34:41,230 --> 00:34:46,120
felly mae hyn yn ar hyn o bryd NULL, a'i newid, fodd bynnag, i fod yn gyfeiriad y nod newydd.

572
00:34:46,120 --> 00:34:52,260
Felly, rydym yn unig yn tynnu mewn cod y saeth ein bod yn tynnu ar y llwyfan gan godi llaw rhywun chwith.

573
00:34:52,260 --> 00:34:54,070
>> A bod yr achos y byddaf yn chwifio fy nwylo ar gyfer yn awr,

574
00:34:54,070 --> 00:34:58,020
dim ond am fy mod yn meddwl ei fod yn hawdd mynd ar goll pan fyddwn yn ei wneud yn y math hwn o amgylchedd,

575
00:34:58,020 --> 00:35:00,600
yn gwirio ar gyfer gosod ar ganol y rhestr yn.

576
00:35:00,600 --> 00:35:03,220
Ond yn reddfol, beth sydd angen i ddigwydd os ydych am i chyfrif i maes

577
00:35:03,220 --> 00:35:06,600
lle mae rhai yn perthyn rhif yn y canol yn oes rhaid i chi gerdded

578
00:35:06,600 --> 00:35:09,510
gyda mwy nag un bys, yn fwy nag un pwyntydd,

579
00:35:09,510 --> 00:35:12,920
chyfrif i maes ble mae'n perthyn trwy wirio yw'r elfen <yr un bresennol,

580
00:35:12,920 --> 00:35:15,450
> Yr un bresennol, ac ar ôl i chi ddod o hyd y lle hwnnw,

581
00:35:15,450 --> 00:35:20,400
yna rhaid i chi wneud y math hwn o gêm cragen lle byddwch yn symud o gwmpas y pwyntiau yn ofalus iawn.

582
00:35:20,400 --> 00:35:23,850
Ac yr ateb hwnnw, os hoffech i reswm drwy hyn yn y cartref ar eich pen eich hun,

583
00:35:23,850 --> 00:35:28,340
boils i lawr yn unig i'r ddwy linell o god, ond bod trefn y llinellau hynny yn hynod bwysig.

584
00:35:28,340 --> 00:35:31,390
Oherwydd os ydych yn gollwng llaw rhywun ac yn codi rhywun arall yn y drefn anghywir,

585
00:35:31,390 --> 00:35:34,580
unwaith eto, gallech fod yn orphaning y rhestr.

586
00:35:34,580 --> 00:35:39,500
I grynhoi fwy gysyniadol, gosod yn y gynffon yn gymharol syml.

587
00:35:39,500 --> 00:35:42,940
Mae'r mewnosod yn y pen hefyd yn gymharol syml,

588
00:35:42,940 --> 00:35:45,580
ond mae angen i chi ddiweddaru pwyntydd ychwanegol y tro hwn

589
00:35:45,580 --> 00:35:47,930
i wasgu rhif 5 yn y rhestr yma,

590
00:35:47,930 --> 00:35:51,560
ac yna gosod yn y canol yn golygu ymdrech hyd yn oed mwy,

591
00:35:51,560 --> 00:35:56,130
i yn ofalus iawn rhowch y rhif 20 yn ei lleoliad cywir,

592
00:35:56,130 --> 00:35:58,350
sydd rhwng 17 a 22.

593
00:35:58,350 --> 00:36:02,700
Felly, mae angen i chi wneud rhywbeth fel cael y 20 nod newydd pwynt i 22,

594
00:36:02,700 --> 00:36:08,470
ac yna, pwyntydd y nod yn angen ei diweddaru ddiwethaf?

595
00:36:08,470 --> 00:36:10,630
Mae'n 17, i mewn gwirionedd yn mewnosod hynny.

596
00:36:10,630 --> 00:36:14,080
Felly eto, byddaf yn gohirio y cod gwirioneddol ar gyfer y gweithredu penodol.

597
00:36:14,080 --> 00:36:17,280
>> Ar yr olwg gyntaf, mae ychydig yn llethol, ond mae'n wirioneddol dim ond dolen ddiddiwedd

598
00:36:17,280 --> 00:36:21,770
mae hynny'n dolennu, dolennu, dolennu, dolennu, ac yn torri cyn gynted ag y byddwch yn taro y pwyntydd NULL,

599
00:36:21,770 --> 00:36:24,590
ac ar y pwynt y gallwch ei wneud gosod gofynnol.

600
00:36:24,590 --> 00:36:30,960
Mae hyn, felly, yw cod cynrychiolydd rhestr cysylltiedig gosod.

601
00:36:30,960 --> 00:36:34,590
Dyna oedd math o lawer, ac mae'n teimlo fel ein bod wedi datrys un broblem,

602
00:36:34,590 --> 00:36:36,940
ond rydym wedi cyflwyno un arall yn llwyr. A dweud y gwir, rydym wedi treulio holl amser

603
00:36:36,940 --> 00:36:40,540
ar fawr O a Ω a rhedeg amser, yn ceisio datrys problemau yn gynt,

604
00:36:40,540 --> 00:36:43,270
ac yma yr ydym yn cymryd cam mawr yn ôl, mae'n teimlo.

605
00:36:43,270 --> 00:36:45,380
Ac eto, os yw'r nod yw i storio data,

606
00:36:45,380 --> 00:36:48,010
mae'n teimlo fel y Greal Sanctaidd, fel y dywedwyd ar ddydd Llun y byddai, mewn gwirionedd yn

607
00:36:48,010 --> 00:36:50,470
i storio pethau yn syth.

608
00:36:50,470 --> 00:36:53,930
>> Yn wir, mae'n debyg ein bod yn gwneud yn rhoi rhestr sy'n gysylltiedig o'r neilltu am eiliad

609
00:36:53,930 --> 00:36:56,000
ac rydym yn lle hynny cyflwynwyd y syniad o dabl.

610
00:36:56,000 --> 00:36:59,110
A gadewch i ni dim ond meddwl am bwrdd ar gyfer hyn o bryd fel arae.

611
00:36:59,110 --> 00:37:03,790
Mae hyn yn amrywiaeth ac mae hyn yn achos yma mae tua 26 elfen, 0 drwy 25,

612
00:37:03,790 --> 00:37:07,940
ac yn debyg eich bod angen rhyw darn o storio ar gyfer enwau:

613
00:37:07,940 --> 00:37:10,350
Alice a Bob a Charlie ac yn y blaen.

614
00:37:10,350 --> 00:37:12,880
A ydych angen rhywfaint o strwythur data i storio yr enwau hynny.

615
00:37:12,880 --> 00:37:15,000
Wel, fe allech chi ddefnyddio rhywbeth fel rhestr cysylltiedig

616
00:37:15,000 --> 00:37:20,260
a gallech gerdded y rhestr mewnosod Alice cyn Bob a Charlie ar ôl Bob ac yn y blaen.

617
00:37:20,260 --> 00:37:23,850
Ac, yn wir, os ydych am weld cod fel 'na fel o'r neilltu,

618
00:37:23,850 --> 00:37:27,230
gwybod bod yn list2.h, rydym yn gwneud yn union hynny.

619
00:37:27,230 --> 00:37:30,610
Ni fyddwn yn mynd drwy y cod hwn, ond mae hyn yn amrywiad ar yr enghraifft gyntaf

620
00:37:30,610 --> 00:37:34,640
sy'n cyflwyno un strwythur arall yr ydym wedi gweld o'r blaen fyfyrwyr gelwir,

621
00:37:34,640 --> 00:37:40,330
ac yna beth yn union mae'n storio'r yn y rhestr cysylltiedig yn pwyntydd i strwythur i fyfyrwyr

622
00:37:40,330 --> 00:37:44,520
yn hytrach na cyfanrif ychydig yn syml, n.

623
00:37:44,520 --> 00:37:46,900
Felly, yn sylweddoli mae cod yno sy'n cynnwys llinynnau gwirioneddol,

624
00:37:46,900 --> 00:37:49,940
ond os bydd y gôl wrth law mewn gwirionedd yn awr yw mynd i'r afael â'r broblem effeithlonrwydd,

625
00:37:49,940 --> 00:37:53,380
ni fyddai'n braf pe ydym yn rhoi gwrthrych o'r enw Alice,

626
00:37:53,380 --> 00:37:56,020
rydym am ei rhoi yn y lleoliad cywir mewn strwythur data,

627
00:37:56,020 --> 00:37:58,860
mae'n teimlo fel petai braf iawn i ddim ond rhoi Alice,

628
00:37:58,860 --> 00:38:01,180
y mae ei enw yn dechrau gyda A, yn y lleoliad cyntaf.

629
00:38:01,180 --> 00:38:05,270
Ac Bob, y mae ei enw yn dechrau gyda B, yn yr ail leoliad.

630
00:38:05,270 --> 00:38:09,580
Gyda array, neu gadewch i ni ddechrau galw ei fod yn dabl, tabl hash ar hynny,

631
00:38:09,580 --> 00:38:13,650
y gallwn ei wneud yn union hynny. Os ydym yn cael enw fel Alice,

632
00:38:13,650 --> 00:38:16,700
llinyn fel Alice, ble yr ydych yn rhoi A-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Rydym angen hueristic. Mae angen swyddogaeth i gymryd rhywfaint o fewnbwn fel Alice

634
00:38:20,540 --> 00:38:24,610
a dychwelyd ateb, "Rhowch Alice yn y lleoliad hwn."

635
00:38:24,610 --> 00:38:28,720
Ac mae hyn swyddogaeth, y blwch du, yn mynd i gael ei alw yn swyddogaeth hash.

636
00:38:28,720 --> 00:38:32,330
>> Mae swyddogaeth hash yn rhywbeth sy'n cymryd mewnbwn, fel "Alice",

637
00:38:32,330 --> 00:38:38,080
a ffurflenni i chi, fel arfer, y lleoliad rhifol mewn rhywfaint o strwythur data lle mae Alice yn perthyn.

638
00:38:38,080 --> 00:38:40,830
Yn yr achos hwn, dylai ein swyddogaeth hash fod yn gymharol syml.

639
00:38:40,830 --> 00:38:47,510
Dylai ein swyddogaeth hash yn dweud, os ydych yn cael "Alice", a ddylai cymeriad wyf yn poeni am?

640
00:38:47,510 --> 00:38:55,660
Mae'r un cyntaf. Felly, yr wyf yn edrych ar [0], ac yna yr wyf yn dweud os cymeriad [0] yn A, dychwelyd y rhif 0.

641
00:38:55,660 --> 00:39:01,130
Os yw'n B, yn dychwelyd 1. Os yw'n C, yn dychwelyd 2, ac yn y blaen.

642
00:39:01,130 --> 00:39:05,940
Byddai pob mynegai 0, ac yn caniatáu i mi i fewnosod Alice ac yna Bob ac yna Charlie ac yn y blaen

643
00:39:05,940 --> 00:39:10,960
i'r strwythur hwn data. Ond mae 'na broblem.

644
00:39:10,960 --> 00:39:13,060
Beth os yw Anita yn dod ar hyd eto?

645
00:39:13,060 --> 00:39:17,510
Ble rydym yn rhoi Anita? Mae ei enw, hefyd, yn dechrau gyda'r llythyren A,

646
00:39:17,510 --> 00:39:20,330
ac mae'n teimlo fel ein bod wedi gwneud mwy fyth o anhrefn y broblem hon.

647
00:39:20,330 --> 00:39:24,380
Erbyn hyn mae gennym gosod ar unwaith, mewnosod cysonyn amser, i mewn i strwythur data

648
00:39:24,380 --> 00:39:27,100
hytrach nag yn waeth-achos llinol,

649
00:39:27,100 --> 00:39:29,510
ond beth allwn ni ei wneud gyda Anita yn yr achos hwn?

650
00:39:29,510 --> 00:39:34,110
Beth yw'r ddau ddewis, mewn gwirionedd? Yeah?

651
00:39:34,110 --> 00:39:37,410
[Ateb Myfyrwyr, annealladwy] Iawn, felly gallwn gael dimensiwn arall.

652
00:39:37,410 --> 00:39:42,320
Mae hynny'n dda. Felly, gallwn adeiladu pethau allan mewn 3D fel yr ydym yn siarad am ar lafar ar ddydd Llun.

653
00:39:42,320 --> 00:39:46,700
Gallem ychwanegu un arall fynediad yma, ond mae'n debyg nad oes, Im 'yn ceisio cadw hyn yn syml.

654
00:39:46,700 --> 00:39:50,160
Y nod cyfan yma yw cael ar unwaith cyson-amser mynediad,

655
00:39:50,160 --> 00:39:52,170
fel bod wedi ychwanegu gormod o gymhlethdod.

656
00:39:52,170 --> 00:39:55,970
Beth yw opsiynau eraill wrth geisio i fewnosod Anita i'r strwythur hwn data? Yeah?

657
00:39:55,970 --> 00:39:58,610
[Ateb Myfyrwyr, annealladwy] Da. Felly, gallem symud pawb arall i lawr,

658
00:39:58,610 --> 00:40:03,040
fel Charlie wthio i lawr Bob ac Alice, ac yna rydym yn rhoi Anita lle mae hi'n wir eisiau bod.

659
00:40:03,040 --> 00:40:05,660
>> Wrth gwrs, erbyn hyn, mae 'na sgil effeithiau hyn.

660
00:40:05,660 --> 00:40:09,000
Mae'r strwythur data yn ôl pob tebyg yn ddefnyddiol nid am ein bod eisiau i fewnosod pobl unwaith

661
00:40:09,000 --> 00:40:11,250
ond oherwydd ein bod eisiau i wirio os maen nhw yno yn ddiweddarach

662
00:40:11,250 --> 00:40:13,600
os ydym eisiau argraffu ar yr holl enwau yn y strwythur data.

663
00:40:13,600 --> 00:40:15,850
Rydym yn mynd i wneud rhywbeth gyda data hwn yn y pen draw.

664
00:40:15,850 --> 00:40:20,810
Felly nawr rydym wedi fath o sgriwio dros Alice, sy'n ddim hwy lle mae hi i fod.

665
00:40:20,810 --> 00:40:23,880
Nid yw Bob, ac nid yw Charlie.

666
00:40:23,880 --> 00:40:26,060
Felly, efallai nad yw hyn yn syniad da.

667
00:40:26,060 --> 00:40:28,830
Ond yn wir, mae hyn yn un opsiwn. Gallem symud pawb i lawr,

668
00:40:28,830 --> 00:40:32,240
neu Heck, Anita yn hwyr i'r gêm, pam nad ydym yn unig yn rhoi Anita

669
00:40:32,240 --> 00:40:35,870
nid yw yma, nid yma, nid yma, gadewch i ni dim ond rhoi hi ychydig yn is yn y rhestr.

670
00:40:35,870 --> 00:40:38,680
Ond yna broblem hon yn dechrau datganoli eto.

671
00:40:38,680 --> 00:40:41,630
Efallai y byddwch yn gallu dod o hyd i Alice yn syth, yn seiliedig ar ei enw cyntaf.

672
00:40:41,630 --> 00:40:44,320
Ac Bob yn syth, a Charlie. Ond yna byddwch yn chwilio am Anita,

673
00:40:44,320 --> 00:40:46,360
a byddwch yn gweld, hmm, Alice yn y ffordd.

674
00:40:46,360 --> 00:40:48,770
Wel, gadewch i mi wirio isod Alice. Nid yw Bob yn Anita.

675
00:40:48,770 --> 00:40:51,850
Nid yw Charlie yw Anita. O, mae Anita.

676
00:40:51,850 --> 00:40:54,720
Ac os ydych yn parhau y trên o resymeg yr holl ffordd,

677
00:40:54,720 --> 00:41:00,690
beth yw'r amser gwaethaf-achos yn rhedeg o ddod o hyd neu fewnosod Anita i'r strwythur hwn data newydd?

678
00:41:00,690 --> 00:41:03,280
Mae'n O (n), dde?

679
00:41:03,280 --> 00:41:06,280
Oherwydd yn yr achos gwaethaf, mae Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
yr holl ffordd i lawr i rywun o'r enw "Y", felly dim ond un man ar ôl.

681
00:41:10,150 --> 00:41:13,950
Diolch byth, nid oes gennym un o'r enw "Z", felly rydym yn rhoi Anita ar y gwaelod iawn.

682
00:41:13,950 --> 00:41:16,040
>> Nid ydym wedi datrys y broblem honno mewn gwirionedd.

683
00:41:16,040 --> 00:41:19,890
Felly, efallai oes angen i ni gyflwyno'r trydydd dimensiwn.

684
00:41:19,890 --> 00:41:22,230
Ac mae'n troi allan, os ydym yn cyflwyno'r trydydd dimensiwn,

685
00:41:22,230 --> 00:41:25,240
Ni allwn wneud hyn yn berffaith, ond y Greal Sanctaidd yn mynd i fod yn mynd

686
00:41:25,240 --> 00:41:28,370
cyson-amser mewnosod a mewnosodiadau deinamig er mwyn i

687
00:41:28,370 --> 00:41:30,960
Nid oes raid i ni galed-god amrywiaeth o faint 26.

688
00:41:30,960 --> 00:41:34,400
Gallwn ychwanegu fel enwau llawer ag y dymunwn, ond gadewch i ni gymryd ein 5-munud egwyl yma

689
00:41:34,400 --> 00:41:38,790
ac yna gwneud hynny yn iawn.

690
00:41:38,790 --> 00:41:46,020
Mae pob hawl. I osod y stori fyny 'n bert artiffisial yno

691
00:41:46,020 --> 00:41:48,670
drwy ddewis Alice ac yna Bob ac yna Charlie ac yna Anita,

692
00:41:48,670 --> 00:41:51,000
y mae ei enw yn amlwg yn mynd i wrthdaro ag Alice.

693
00:41:51,000 --> 00:41:54,120
Ond y cwestiwn rydym yn dod i ben ddydd Llun gyda yn unig pa mor debygol yw hi

694
00:41:54,120 --> 00:41:56,370
y byddech yn cael y mathau hyn o wrthdrawiadau? Mewn geiriau eraill,

695
00:41:56,370 --> 00:42:00,490
os ydym yn dechrau defnyddio'r strwythur hwn tablau, sydd mewn gwirionedd yn unig array,

696
00:42:00,490 --> 00:42:02,460
yn yr achos hwn o 26 o leoliadau,

697
00:42:02,460 --> 00:42:05,740
beth os yw ein mewnbwn yn hytrach na dosbarthu unffurf?

698
00:42:05,740 --> 00:42:09,620
Nid yw'n artiffisial Alice a Bob a Charlie a David ac yn y blaen yn nhrefn yr wyddor,

699
00:42:09,620 --> 00:42:12,380
ei ddosbarthu unffurf dros A drwy'r Z.

700
00:42:12,380 --> 00:42:15,220
>> Efallai byddwn yn unig yn cael lwcus ac nid ydym yn mynd i gael dau A neu ddau B

701
00:42:15,220 --> 00:42:17,640
gyda thebygolrwydd uchel iawn, ond fel rhywun sylw at y ffaith,

702
00:42:17,640 --> 00:42:20,730
os ydym yn gyffredinol y broblem hon a pheidio â gwneud 0-25

703
00:42:20,730 --> 00:42:26,060
ond, yn dweud, 0 364 neu drwy 65 oed, yn aml y nifer o ddyddiau mewn blwyddyn nodweddiadol,

704
00:42:26,060 --> 00:42:31,170
a gofyn y cwestiwn, "Beth yw'r tebygolrwydd y ddau ohonom yn yr ystafell hon yn cael pen-blwydd un fath?"

705
00:42:31,170 --> 00:42:34,600
Roi mewn ffordd arall, beth yw'r tebygolrwydd y ddau ohonom yn cael enw gan ddechrau gyda A?

706
00:42:34,600 --> 00:42:37,190
Y math o gwestiwn yw yr un fath, ond y gofod cyfeiriad,

707
00:42:37,190 --> 00:42:39,940
y gofod chwilio, yn fwy yn achos pen-blwydd,

708
00:42:39,940 --> 00:42:42,820
am fod gennym fwy o ddiwrnodau cymaint yn ystod y flwyddyn na llythyrau yn y wyddor.

709
00:42:42,820 --> 00:42:44,910
Beth yw'r tebygolrwydd o wrthdrawiad?

710
00:42:44,910 --> 00:42:48,410
Wel, gallwn feddwl am hyn drwy figuring allan y math y ffordd gyferbyn.

711
00:42:48,410 --> 00:42:50,580
Beth yw'r tebygolrwydd o unrhyw wrthdrawiadau?

712
00:42:50,580 --> 00:42:53,970
Wel, mae hyn yn fynegiant yma yn dweud bod yr hyn yw'r tebygolrwydd

713
00:42:53,970 --> 00:42:58,770
os oes dim ond un person yn yr ystafell hon, bod ganddynt pen-blwydd unigryw?

714
00:42:58,770 --> 00:43:01,190
Mae'n 100%. Oherwydd os oes dim ond un person yn yr ystafell,

715
00:43:01,190 --> 00:43:03,940
Gall ei ben-blwydd yn unrhyw un o'r 365 diwrnod o'r flwyddyn.

716
00:43:03,940 --> 00:43:08,650
Felly opsiynau 365/365 yn rhoi i mi werth o 1.

717
00:43:08,650 --> 00:43:11,250
Felly, y tebygolrwydd o dan sylw ar hyn o bryd yn unig 1.

718
00:43:11,250 --> 00:43:13,270
Ond os oes ail berson yn yr ystafell,

719
00:43:13,270 --> 00:43:16,490
beth yw'r tebygolrwydd bod eu pen-blwydd yn wahanol?

720
00:43:16,490 --> 00:43:20,680
Dim ond 364 diwrnod posibl, blynyddoedd naid anwybyddu,

721
00:43:20,680 --> 00:43:23,580
am eu pen-blwydd i beidio â gwrthdaro â'r personau eraill.

722
00:43:23,580 --> 00:43:31,920
Felly, 364/365. Os yw trydydd person yn dod i mewn, mae'n 363/365, ac yn y blaen.

723
00:43:31,920 --> 00:43:35,790
Felly, byddwn yn cadw lluosi ffracsiynau hyn at ei gilydd, sy'n mynd yn llai ac yn llai,

724
00:43:35,790 --> 00:43:40,720
at chyfrif i maes beth yw'r tebygolrwydd bod pob un ohonom yn cael pen-blwydd unigryw?

725
00:43:40,720 --> 00:43:43,570
Ond fe allwn wedyn, wrth gwrs, dim ond yn cymryd yr ateb hwnnw ac yn troi o gwmpas

726
00:43:43,570 --> 00:43:47,210
ac yn ei wneud 1 minws hynny i gyd, mynegiant byddwn yn y pen draw yn cael

727
00:43:47,210 --> 00:43:51,250
os ydych yn cofio gefn eich llyfrau mathemateg, mae'n edrych yn rhywbeth bach fel hyn,

728
00:43:51,250 --> 00:43:54,590
sydd yn llawer haws dehongli graffigol.

729
00:43:54,590 --> 00:43:57,820
A llun hon yma yn ei gael ar yr echelin x nifer y pen-blwydd,

730
00:43:57,820 --> 00:44:02,030
neu nifer y bobl ag pen-blwydd, ac ar yr echelin y yw y tebygolrwydd o gêm.

731
00:44:02,030 --> 00:44:06,060
A beth mae hyn yn ei ddweud yw os oes gennych chi, gadewch i ni ddweud, hyd yn oed,

732
00:44:06,060 --> 00:44:10,860
gadewch i ni ddewis rhywbeth fel 22, 23.

733
00:44:10,860 --> 00:44:13,160
Os oes 22 neu 23 o bobl yn yr ystafell,

734
00:44:13,160 --> 00:44:17,100
y tebygolrwydd bod dau o'r rhai ychydig iawn o bobl yn mynd i gael yr un pen-blwydd

735
00:44:17,100 --> 00:44:19,560
mewn gwirionedd yn uchel super, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% y groes mewn dosbarth o ddim ond 22 o bobl, yn seminar, yn ymarferol,

737
00:44:23,450 --> 00:44:25,790
2 o bobl yn mynd i gael yr un pen-blwydd.

738
00:44:25,790 --> 00:44:28,520
Oherwydd mae cymaint o ffyrdd y gallwch chi gael yr un pen-blwydd.

739
00:44:28,520 --> 00:44:31,110
Hyd yn oed yn waeth, os edrychwch ar yr ochr dde y siart,

740
00:44:31,110 --> 00:44:34,040
erbyn yr amser sydd gennych dosbarth gyda 58 o fyfyrwyr ynddo,

741
00:44:34,040 --> 00:44:39,270
y tebygolrwydd o 2 o bobl yn cael pen-blwydd yn super, uchel super, bron i 100%.

742
00:44:39,270 --> 00:44:41,880
Nawr, mae hynny'n fath o ffaith hwyl am fywyd go iawn.

743
00:44:41,880 --> 00:44:45,850
>> Ond y goblygiadau, yn awr, ar gyfer strwythurau data a storio gwybodaeth

744
00:44:45,850 --> 00:44:51,100
yn golygu mai dim ond gan dybio eich bod yn cael 'n glws, yn lân, dosbarthu unffurf o ddata

745
00:44:51,100 --> 00:44:53,650
a bod gennych ddigon o amrywiaeth fawr i ffitio bagad o bethau

746
00:44:53,650 --> 00:44:59,360
nid yw'n golygu eich bod yn mynd i gael pobl mewn lleoliadau unigryw.

747
00:44:59,360 --> 00:45:03,810
Rydych yn mynd i gael gwrthdrawiadau. Felly, mae hyn syniad o stwnsio, gan ei fod yn cael ei alw,

748
00:45:03,810 --> 00:45:07,450
cymryd mewnbwn fel "Alice" a massaging mewn rhyw ffordd

749
00:45:07,450 --> 00:45:10,190
ac yna mynd yn ôl ateb fel 0 neu 1 neu 2.

750
00:45:10,190 --> 00:45:17,500
Cael yn ôl rhywfaint o allbwn o'r swyddogaeth honno yn cael ei blagio gan y tebygolrwydd o gael gwrthdrawiad.

751
00:45:17,500 --> 00:45:19,530
Felly, sut rydym yn trin y gwrthdrawiadau?

752
00:45:19,530 --> 00:45:21,940
Wel, ar yr un achos, gallwn gymryd y syniad a awgrymwyd.

753
00:45:21,940 --> 00:45:25,100
Gall Rydym yn unig yn symud pawb i lawr, neu efallai, ychydig yn fwy syml,

754
00:45:25,100 --> 00:45:29,870
yn hytrach na phawb arall symud, gadewch i ni dim ond symud Anita i waelod y fan a'r lle sydd ar gael.

755
00:45:29,870 --> 00:45:32,810
Felly, os Alice yn 0, Bob yn 1, Charlie yn 2,

756
00:45:32,810 --> 00:45:35,260
byddwn yn unig yn rhoi Anita yn lleoliad 3.

757
00:45:35,260 --> 00:45:38,860
Ac mae hyn yn dechneg mewn strwythurau data a elwir yn llinol dreiddgar.

758
00:45:38,860 --> 00:45:41,310
Llinellol oherwydd eich bod yn cerdded y llinell hon, ac rydych yn fath o ymchwilio

759
00:45:41,310 --> 00:45:43,640
am fannau sydd ar gael yn y strwythur data.

760
00:45:43,640 --> 00:45:46,210
Wrth gwrs, mae hyn yn datganoli i mewn i O (n).

761
00:45:46,210 --> 00:45:49,590
Os yw'r strwythur data wir yn llawn, mae 25 o bobl ynddo eisoes,

762
00:45:49,590 --> 00:45:54,120
ac yna Anita yn dod ar hyd, mae hi'n dod i ben i fyny ar yr hyn a fyddai'n Z lleoliad, ac mae hynny'n iawn.

763
00:45:54,120 --> 00:45:56,540
Mae hi'n dal i ffitio, a gallwn ddod o hyd iddi yn ddiweddarach.

764
00:45:56,540 --> 00:46:00,100
>> Ond mae hyn yn groes i'r nod o gyflymu pethau i fyny.

765
00:46:00,100 --> 00:46:02,530
Felly beth os ydym yn hytrach gyflwyno y trydydd dimensiwn?

766
00:46:02,530 --> 00:46:06,400
Y dechneg a elwir yn gyffredinol gadwyno ar wahân, neu gael cadwyni.

767
00:46:06,400 --> 00:46:10,030
A beth tabl hash yn awr yw, y strwythur tabl,

768
00:46:10,030 --> 00:46:13,450
eich bwrdd yn unig yw amrywiaeth o awgrymiadau.

769
00:46:13,450 --> 00:46:18,230
Ond beth yw'r arwyddion yn cyfeirio ato yw'r dyfalu beth?

770
00:46:18,230 --> 00:46:21,970
Mae rhestr cysylltiedig. Felly beth os ydym yn cymryd y gorau o'r ddau fyd?

771
00:46:21,970 --> 00:46:26,500
Rydym yn defnyddio araeau ar gyfer y mynegeion cychwynnol

772
00:46:26,500 --> 00:46:32,070
i mewn i'r strwythur data er mwyn i ni ar unwaith yn mynd i [0] [1], [30] neu yn y blaen,

773
00:46:32,070 --> 00:46:36,480
ond er mwyn gennym rywfaint o hyblygrwydd a gallwn ffitio Anita a Alice ac Adam

774
00:46:36,480 --> 00:46:38,630
ac unrhyw un arall Mae enw,

775
00:46:38,630 --> 00:46:43,470
rydym yn hytrach gadael i'r echelin eraill yn tyfu yn fympwyol.

776
00:46:43,470 --> 00:46:47,340
Ac rydym yn olaf, o ddydd Llun, yn cael y gallu mynegiannol gyda rhestr cysylltiedig.

777
00:46:47,340 --> 00:46:49,530
Gallwn dyfu strwythur data fympwyol.

778
00:46:49,530 --> 00:46:52,450
Fel arall, gallem wneud enfawr 2-ddimensiwn array,

779
00:46:52,450 --> 00:46:57,190
ond mae hynny'n mynd i fod yn sefyllfa ofnadwy os yw un o'r rhesi mewn amrywiaeth 2-ddimensiwn

780
00:46:57,190 --> 00:47:01,280
yn ddigon mawr ar gyfer y person ychwanegol y mae ei enw yn digwydd i ddechrau A.

781
00:47:01,280 --> 00:47:04,200
Duw a'n gwaredo rhag mae'n rhaid i ni ail-ddyrannu enfawr 2-ddimensiwn strwythur

782
00:47:04,200 --> 00:47:06,600
dim ond oherwydd bod cymaint o bobl a enwir A,

783
00:47:06,600 --> 00:47:09,480
yn enwedig pan fo cyn lleied o bobl a enwir Z rhywbeth.

784
00:47:09,480 --> 00:47:12,170
Mae'n dim ond yn mynd i fod yn strwythur data yn brin iawn.

785
00:47:12,170 --> 00:47:15,400
Felly, nid yw'n berffaith o bell ffordd, ond yn awr mae gennym o leiaf y gallu

786
00:47:15,400 --> 00:47:19,090
i yn syth ddod o hyd lle mae Alice neu Anita yn perthyn iddi,

787
00:47:19,090 --> 00:47:21,090
o leiaf o ran yr echelin fertigol,

788
00:47:21,090 --> 00:47:25,850
ac yna rydym yn unig rhaid i ni benderfynu lle i roi Anita neu Alice yn y rhestr hon cysylltiedig.

789
00:47:25,850 --> 00:47:32,480
Os nad ydym yn poeni am drefnu pethau, gallai pa mor gyflym rydym yn ychwanegu Alice i mewn i strwythur fel hyn?

790
00:47:32,480 --> 00:47:35,370
Mae'n amser yn gyson. Byddwn yn mynegeio'r i [0], ac os oes unrhyw un yn,

791
00:47:35,370 --> 00:47:37,550
Alice yn mynd ar ddechrau'r rhestr honno cysylltiedig.

792
00:47:37,550 --> 00:47:40,000
Ond dyw hynny ddim yn golygu cryn dipyn. Oherwydd os Anita wedyn yn dod ynghyd

793
00:47:40,000 --> 00:47:42,160
ryw nifer o gamau yn ddiweddarach, ble mae Anita yn perthyn?

794
00:47:42,160 --> 00:47:45,140
Wel, [0]. OOP. Alice eisoes yn y rhestr honno cysylltiedig.

795
00:47:45,140 --> 00:47:47,760
>> Ond os nad ydym yn poeni am ddatrys yr enwau hyn,

796
00:47:47,760 --> 00:47:53,580
gallwn dim ond symud Alice dros, mewnosoder Anita, ond hyd yn oed hynny yw cysonyn amser.

797
00:47:53,580 --> 00:47:57,010
Hyd yn oed os oes Alice ac Adam a hyn i gyd A eraill enwau,

798
00:47:57,010 --> 00:47:59,410
Nid yw hi go symud yn gorfforol. Pam?

799
00:47:59,410 --> 00:48:04,090
Oherwydd ein bod yn unig oedd yma gyda rhestr cysylltiedig, pwy a ŵyr yn y nodau yn beth bynnag?

800
00:48:04,090 --> 00:48:06,550
Y cyfan sydd raid i chi ei wneud yw symud y briwsion bara.

801
00:48:06,550 --> 00:48:10,930
Symudwch y saethau o amgylch, nid oes rhaid i chi symud yn gorfforol unrhyw ddata o gwmpas.

802
00:48:10,930 --> 00:48:14,610
Felly, gallwn ychwanegu Anita, yn yr achos hwnnw, ar unwaith. Cysonyn amser.

803
00:48:14,610 --> 00:48:20,250
Felly mae gennym cyson-amser am-edrych, ac yn gyson-amser gosod rhywun fel Anita.

804
00:48:20,250 --> 00:48:22,740
Ond math o gorsymleiddio y byd.

805
00:48:22,740 --> 00:48:28,510
Beth os ydym yn ddiweddarach am ddod o hyd Alice?

806
00:48:28,510 --> 00:48:31,050
Beth os ydym yn ddiweddarach am ddod o hyd Alice?

807
00:48:31,050 --> 00:48:35,690
Faint o gamau yw bod mynd i gymryd?

808
00:48:35,690 --> 00:48:37,850
[Ateb Myfyrwyr, annealladwy]

809
00:48:37,850 --> 00:48:40,950
Yn union. Mae nifer y bobl cyn Alice yn y rhestr cysylltiedig.

810
00:48:40,950 --> 00:48:45,420
Felly nid yw'n hollol berffaith, oherwydd bod ein strwythur data, unwaith eto, mae hyn yn fynediad fertigol

811
00:48:45,420 --> 00:48:50,240
ac yna rhaid rhestrau hyn cysylltiedig hongian - yn wir, gadewch i ni dynnu arae yn.

812
00:48:50,240 --> 00:48:56,020
Mae wedi hyn rhestrau cysylltiedig yn hongian oddi ar ei sy'n edrych rhywbeth bach fel hyn.

813
00:48:56,020 --> 00:48:59,110
Ond y broblem yw os Alice ac Adam a hyn i gyd A eraill enwau

814
00:48:59,110 --> 00:49:01,720
yn y pen draw yn fwy a mwy dros yno,

815
00:49:01,720 --> 00:49:04,810
dod o hyd y gallai rhywun yn y pen draw yn cymryd criw o gamau,

816
00:49:04,810 --> 00:49:06,670
bcause yn rhaid i chi deithio ar draws y rhestr cysylltiedig,

817
00:49:06,670 --> 00:49:08,090
sydd yn llawdriniaeth llinol.

818
00:49:08,090 --> 00:49:14,270
Felly mewn gwirionedd, yna, yr amser mewnosod yn y pen draw yn O (n), lle mae n yn nifer o elfennau yn y rhestr.

819
00:49:14,270 --> 00:49:21,780
Rannu gan, gadewch i ni fympwyol ei alw m, lle m yw nifer y rhestrau cysylltiedig

820
00:49:21,780 --> 00:49:24,500
bod gennym yn y echelin fertigol.

821
00:49:24,500 --> 00:49:27,180
Mewn geiriau eraill, os ydym yn wirioneddol yn tybio dosbarthiad unffurf o enwau,

822
00:49:27,180 --> 00:49:30,150
hollol afrealistig. Mae amlwg yn fwy o rai llythyrau nag eraill.

823
00:49:30,150 --> 00:49:32,580
>> Ond os ydym yn cymryd yn ganiataol ar hyn o bryd a dosbarthiad unffurf,

824
00:49:32,580 --> 00:49:37,350
ac rydym wedi n pobl cyfanswm, a chadwyni chyfanswm m

825
00:49:37,350 --> 00:49:40,630
ar gael i ni, yna ar hyd pob un o'r cadwyni

826
00:49:40,630 --> 00:49:44,380
weddol syml, yn mynd i fod y cyfanswm, n rannu gan y nifer o gadwyni.

827
00:49:44,380 --> 00:49:48,900
Felly n / m. Ond dyma lle y gallwn fod pawb yn fathemategol glyfar.

828
00:49:48,900 --> 00:49:53,030
m yn gysonyn, oherwydd mae 'na nifer penodedig o'r rhain.

829
00:49:53,030 --> 00:49:54,620
Rydych yn mynd i ddatgan eich amrywiaeth ar y dechrau,

830
00:49:54,620 --> 00:49:58,450
ac nid ydym yn newid maint yr echelin fertigol. Drwy ddiffiniad, sy'n sefydlog yn aros.

831
00:49:58,450 --> 00:50:01,220
Dim ond yr echelin lorweddol, fel petai, mae hynny'n newid.

832
00:50:01,220 --> 00:50:04,760
Felly, yn dechnegol, mae hyn yn gyson. Felly yn awr, yr amser gosod

833
00:50:04,760 --> 00:50:09,700
yn O 'n bert lawer (n).

834
00:50:09,700 --> 00:50:12,410
Felly, nid yw'n teimlo i gyd bod llawer gwell.

835
00:50:12,410 --> 00:50:14,940
Ond beth yw'r gwirionedd yma? Wel, i gyd y tro hwn, am wythnosau,

836
00:50:14,940 --> 00:50:20,640
rydym wedi bod yn ei ddweud O (n ²). O (n), 2 x n ², - n, wedi'i rannu â 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
Dim ond ² n. Ond yn awr, yn y rhan hon o'r semester,

838
00:50:23,580 --> 00:50:25,560
gallwn ddechrau siarad am y byd go iawn unwaith eto.

839
00:50:25,560 --> 00:50:31,520
Ac n / m yn gwbl gyflymach na dim ond n unig.

840
00:50:31,520 --> 00:50:35,170
Os oes gennych fil o enwau, ac rydych yn eu torri i fyny i mewn bwcedi lluosog

841
00:50:35,170 --> 00:50:37,820
fel bod gennych dim ond deg enw ym mhob un o'r cadwyni,

842
00:50:37,820 --> 00:50:41,670
gwbl chwilio deg peth yn mynd i fod yn gyflymach na mil o bethau.

843
00:50:41,670 --> 00:50:43,740
Ac felly un o'r setiau problem sydd ar y gweill yn mynd i herio eich

844
00:50:43,740 --> 00:50:46,100
i feddwl am yr union hyd yn oed er, yeah,

845
00:50:46,100 --> 00:50:49,520
asymptotically ac yn fathemategol, mae hyn yn dal i fod ychydig llinol,

846
00:50:49,520 --> 00:50:51,700
sy'n sucks yn gyffredinol wrth geisio dod o hyd i bethau.

847
00:50:51,700 --> 00:50:54,530
Mewn gwirionedd, mae'n mynd i fod yn gyflymach na'r hyn a

848
00:50:54,530 --> 00:50:56,520
oherwydd y rhannydd.

849
00:50:56,520 --> 00:50:58,310
Ac felly mae 'unwaith eto yn mynd i fod y fasnach-off

850
00:50:58,310 --> 00:51:01,390
ac mae hyn yn gwrthdaro rhwng theori a realiti,

851
00:51:01,390 --> 00:51:03,550
a bydd un o'r knobs yn dechrau troi ar y pwynt hwn yn y semester

852
00:51:03,550 --> 00:51:07,510
yn fwy o realiti un fel yr ydym math o baratoi ar gyfer semster y diwedd,

853
00:51:07,510 --> 00:51:09,280
wrth i ni gyflwyno y byd o raglenni ar y we,

854
00:51:09,280 --> 00:51:11,530
lle mewn gwirionedd, mae perfformiad yn mynd i gyfrif am fod eich defnyddwyr yn mynd i

855
00:51:11,530 --> 00:51:14,880
dechrau teimlo'n a gwerthfawrogi benderfyniadau dylunio gwael.

856
00:51:14,880 --> 00:51:19,950
>> Felly sut mae mynd ati i weithredu cysylltiedig - tabl hash gyda 31 o elfennau?

857
00:51:19,950 --> 00:51:22,600
Ac yr enghraifft flaenorol yn fympwyol am pen-blwydd.

858
00:51:22,600 --> 00:51:26,190
Os bydd rhywun yn cael pen-blwydd o Ionawr 1 neu 1 Chwefror, byddwn yn eu rhoi yn y bwced.

859
00:51:26,190 --> 00:51:28,960
Os yw'n Ionawr 2, Chwefror 2, 2 Mawrth, byddwn yn eu rhoi yn y bwced.

860
00:51:28,960 --> 00:51:32,220
Dyna pam yr oedd 31. Sut ydych chi'n datgan tabl hash?

861
00:51:32,220 --> 00:51:37,480
Gall fod yn eithaf syml, tabl * nod yw fy enw mympwyol ar ei gyfer, [31].

862
00:51:37,480 --> 00:51:42,400
Mae hyn yn rhoi i mi 31 awgrymiadau i nodau,

863
00:51:42,400 --> 00:51:45,370
ac mae hynny'n caniatáu i mi i 31 o awgrymiadau i restrau cysylltiedig

864
00:51:45,370 --> 00:51:48,800
hyd yn oed os yw'r cadwyni yn dechrau NULL.

865
00:51:48,800 --> 00:51:54,860
Beth ydw i am ei roi os ydw i eisiau i storio 'Alice, "" Bob, "" Charlie "?

866
00:51:54,860 --> 00:51:57,010
Wel, mae angen i lapio pethau hynny mewn strwythur

867
00:51:57,010 --> 00:52:00,530
oherwydd mae arnom angen Alice i bwyntio at Bob, i bwyntio at Charlie, ac yn y blaen.

868
00:52:00,530 --> 00:52:04,940
Ni allwn gael yr enwau yn unig, er mwyn i mi greu strwythur newydd o'r enw nôd yma.

869
00:52:04,940 --> 00:52:08,310
>> Beth yw nod go iawn? Beth yw nod yn y rhestr hon newydd sy'n gysylltiedig?

870
00:52:08,310 --> 00:52:11,840
Y peth cyntaf, a elwir gair, ar gyfer enw'r person.

871
00:52:11,840 --> 00:52:14,340
HYD, yn ôl pob tebyg, yn ymwneud â'r uchafswm hyd o enw dynol,

872
00:52:14,340 --> 00:52:18,210
beth bynnag hynny yw, 20, 30, 40 gymeriadau mewn achosion cornel crazy,

873
00:52:18,210 --> 00:52:22,680
a +1 ar gyfer beth? Mae'n dim ond y nod NULL ychwanegol, \ 0.

874
00:52:22,680 --> 00:52:27,410
Felly, mae hyn yn nod lapio "rhywbeth" tu mewn ei hun,

875
00:52:27,410 --> 00:52:29,640
ond mae hefyd yn datgan pwyntydd o'r enw nesaf

876
00:52:29,640 --> 00:52:32,580
fel y gallwn cadwyn Alice i Bob i Charlie ac yn y blaen.

877
00:52:32,580 --> 00:52:36,700
Gall fod yn NULL, ond nid yw o reidrwydd yn rhaid i fod.

878
00:52:36,700 --> 00:52:40,110
Unrhyw gwestiynau ar y tablau hash? Yeah?

879
00:52:40,110 --> 00:52:46,190
[Myfyrwyr yn gofyn cwestiwn, annealladwy] Mae amrywiaeth - cwestiwn da.

880
00:52:46,190 --> 00:52:50,120
Pam fod y gair torgoch mewn arae yn hytrach na dim ond * torgoch?

881
00:52:50,120 --> 00:52:53,830
Yn yr enghraifft hon braidd yn fympwyol, doeddwn i ddim eisiau gorfod troi

882
00:52:53,830 --> 00:52:56,190
i malloc gyfer pob un o'r enwau gwreiddiol.

883
00:52:56,190 --> 00:52:59,530
Roeddwn i eisiau datgan uchafswm o gof ar gyfer y llinyn

884
00:52:59,530 --> 00:53:06,020
er mwyn i mi gopïo i mewn i'r strwythur Alice \ 0 ac nid rhaid i chi ddelio â malloc ac am ddim ac yn y blaen.

885
00:53:06,020 --> 00:53:11,710
Ond roeddwn yn gallu gwneud hynny os oeddwn i eisiau i fod yn fwy ymwybodol o ddefnydd gofod. Da cwestiwn.

886
00:53:11,710 --> 00:53:14,780
Felly, gadewch i ni geisio gyffredinoli i ffwrdd o'r

887
00:53:14,780 --> 00:53:18,350
ac yn canolbwyntio gweddill heddiw ar strwythurau data yn fwy cyffredinol

888
00:53:18,350 --> 00:53:21,170
a phroblemau eraill y gallwn ddatrys defnyddio'r hanfodion un

889
00:53:21,170 --> 00:53:24,590
er bod y strwythurau data y gallai eu hunain yn wahanol o ran eu manylion.

890
00:53:24,590 --> 00:53:27,910
>> Felly, mae'n troi allan mewn gwyddoniaeth gyfrifiadurol, coed yn gyffredin iawn.

891
00:53:27,910 --> 00:53:29,760
A allwch chi feddwl am fath o fel coeden coeden deulu,

892
00:53:29,760 --> 00:53:31,830
lle mae rhywfaint o wreiddiau, mae rhai matriarch neu patriarch,

893
00:53:31,830 --> 00:53:34,540
nain neu grandpa neu'n gynharach yn ôl,

894
00:53:34,540 --> 00:53:38,880
o dan ohonynt yn mom a dad neu frodyr a chwiorydd wahanol neu debyg.

895
00:53:38,880 --> 00:53:42,500
Felly strwythur goeden nodau ac mae ganddo blant,

896
00:53:42,500 --> 00:53:45,260
fel arfer yn 0 neu fwy o blant ar gyfer pob nod.

897
00:53:45,260 --> 00:53:47,320
Ac mae rhai o'r jargon a welwch yn y llun yma

898
00:53:47,320 --> 00:53:50,630
yw unrhyw un o'r plant ychydig neu grandkids ar yr ymylon

899
00:53:50,630 --> 00:53:52,330
sydd heb unrhyw saethau sy'n deillio ohonynt,

900
00:53:52,330 --> 00:53:55,070
dyna'r dail fel y'i gelwir, ac unrhyw un ar y tu mewn

901
00:53:55,070 --> 00:53:58,790
yn nod mewnol, gallwch alw yn unrhyw beth hyd y llinellau hynny.

902
00:53:58,790 --> 00:54:01,430
Ond y strwythur hwn yn eithaf cyffredin. Hyn yn un 'ychydig yn fympwyol.

903
00:54:01,430 --> 00:54:04,930
Mae gennym un plentyn ar y chwith, mae gennym dri o blant ar y dde,

904
00:54:04,930 --> 00:54:06,830
dau o blant ar y gwaelod ar y chwith.

905
00:54:06,830 --> 00:54:10,740
Felly, gallwn gael o wahanol faint coed, ond os ydym yn dechrau i safoni pethau,

906
00:54:10,740 --> 00:54:15,330
ac efallai y byddwch yn cofio hyn Patrick fideo ar chwiliad deuaidd o fer blaenorol

907
00:54:15,330 --> 00:54:19,490
nid ar lein, chwiliad deuaidd yn gorfod cael ei weithredu gydag amrywiaeth

908
00:54:19,490 --> 00:54:21,410
neu ddarnau o bapur ar fwrdd du.

909
00:54:21,410 --> 00:54:25,490
Tybiwch eich bod yn dymuno i storio eich rhifau mewn strwythur data mwy soffistigedig.

910
00:54:25,490 --> 00:54:27,680
Gallech greu coeden fel hyn.

911
00:54:27,680 --> 00:54:35,290
Gallech gael nod ddatgan yn C, a gall y nod fod ag o leiaf dwy elfen y tu mewn ohono.

912
00:54:35,290 --> 00:54:39,470
Un yw y rhif yr ydych am ei gadw, ac mae'r llall yn - wel, mae angen un yn fwy.

913
00:54:39,470 --> 00:54:41,540
Y llall yw ei phlant.

914
00:54:41,540 --> 00:54:45,150
Felly dyma un arall strwythur data. Y tro hwn, mae nod yn cael ei ddiffinio fel storio nifer n

915
00:54:45,150 --> 00:54:49,060
ac yna dau awgrymiadau; plentyn chwith a dde phlentyn.

916
00:54:49,060 --> 00:54:52,100
Ac nid ydynt yn fympwyol. Beth sy'n ddiddorol am y goeden?

917
00:54:52,100 --> 00:55:00,550
>> Beth yw'r patrwm o ran sut yr ydym wedi gosod hyn neu sut Patrick gosod allan yn ei fideo?

918
00:55:00,550 --> 00:55:02,790
Mae'n fath o amlwg fod yna peth gwaith didoli yn digwydd yma,

919
00:55:02,790 --> 00:55:04,460
ond beth yw'r rheol syml? Yeah?

920
00:55:04,460 --> 00:55:08,350
[Ateb Myfyrwyr, annealladwy]

921
00:55:08,350 --> 00:55:12,040
Perfect. Os ydych yn gipolwg ar hyn, byddwch yn gweld y niferoedd bach ar y chwith,

922
00:55:12,040 --> 00:55:14,690
rhifau mawr ar y chwith, ond mae hynny'n wir am bob nod.

923
00:55:14,690 --> 00:55:20,370
Ar gyfer pob nod, ei blentyn chwith llai nag y mae'n ei, ac mae ei phlentyn gywir yn fwy nag ef.

924
00:55:20,370 --> 00:55:25,210
Beth mae hyn yn golygu yn awr yw os wyf am i chwilio y strwythur data ar gyfer, dyweder, rhif 44,

925
00:55:25,210 --> 00:55:29,320
Rhaid i mi ddechrau ar y gwraidd, oherwydd fel gyda phob un o'r rhain yn fwy cymhleth strwythurau data yn awr,

926
00:55:29,320 --> 00:55:31,910
yn unig sydd gennym pwyntydd i un peth, y dechrau.

927
00:55:31,910 --> 00:55:35,010
Ac yn yr achos hwn, y dechrau yw gwraidd. Dyw hi ddim yn ddiwedd y chwith,

928
00:55:35,010 --> 00:55:39,530
ei fod yn wraidd y strwythur hwn. Felly, yr wyf yn gweld yma yn 55 oed, ac rwy'n edrych am 44.

929
00:55:39,530 --> 00:55:41,430
Pa gyfeiriad ydw i am fynd?

930
00:55:41,430 --> 00:55:45,680
Wel, dw i eisiau mynd i'r chwith, oherwydd yn amlwg, ar y dde yn mynd i fod yn rhy fawr.

931
00:55:45,680 --> 00:55:49,050
Felly sylwi yma, rydych yn fath o gysyniadol torri y goeden yn ei hanner

932
00:55:49,050 --> 00:55:51,700
oherwydd nad ydych yn mynd i lawr i'r ochr dde.

933
00:55:51,700 --> 00:55:55,410
Felly nawr rwy'n mynd o 55 i 33. Mae'n rhy fach o nifer.

934
00:55:55,410 --> 00:56:01,590
Dwi'n chwilio am 44, ond yn awr yr wyf yn gwybod os yn 44 yn y goeden hon, gallaf fynd yn amlwg ar y dde.

935
00:56:01,590 --> 00:56:04,460
Felly, unwaith eto, rwy'n docio y goeden yn ei hanner.

936
00:56:04,460 --> 00:56:06,780
Mae'n 'n bert lawer yn union yr gysyniadol at y llyfr ffôn.

937
00:56:06,780 --> 00:56:09,510
Mae'n union yr un fath beth a wnaethom gyda'r papurau ar y bwrdd du,

938
00:56:09,510 --> 00:56:13,940
ond mae'n strwythur mwy soffistigedig sy'n caniatáu i ni ei wneud mewn gwirionedd

939
00:56:13,940 --> 00:56:16,880
hyn yn rhannu a gorchfygu gan dyluniad y algorithm,

940
00:56:16,880 --> 00:56:19,420
ac yn wir, groesi strwythur fel hyn - Wps.

941
00:56:19,420 --> 00:56:22,870
Croesi strwythur fel hyn, lle mai dim ond "yn mynd y ffordd neu'n mynd y ffordd honno,"

942
00:56:22,870 --> 00:56:26,870
yn golygu yr holl y cod sy'n plygu eich meddwl ar y dechrau wrth roi ar waith yn adran

943
00:56:26,870 --> 00:56:31,270
neu gerdded drwyddo yn y cartref, ar gyfer chwiliad deuaidd, gan ddefnyddio dychweliad neu ailadrodd,

944
00:56:31,270 --> 00:56:35,060
mae'n boen yn y gwddf. Dewch o hyd i'r elfen canol, yna gwnewch eich talgrynnu i fyny neu i lawr.

945
00:56:35,060 --> 00:56:39,230
>> Mae yna harddwch i hyn oherwydd gallwn yn awr ddefnyddio dychweliad eto,

946
00:56:39,230 --> 00:56:43,760
ond yn llawer mwy lân. Yn wir, os ydych chi yn y rhif 55 a ydych am ddod o hyd i 44,

947
00:56:43,760 --> 00:56:48,450
byddwch yn mynd ar ôl yn yr achos hwn, yna beth ydych chi'n ei wneud? Rydych yn rhedeg yr un algorithm union.

948
00:56:48,450 --> 00:56:51,560
Chi wirio gwerth y nod, yna byddwch yn mynd i'r chwith neu i'r dde.

949
00:56:51,560 --> 00:56:53,670
Yna byddwch yn edrych ar y gwerth y nod, ewch i'r chwith neu i'r dde.

950
00:56:53,670 --> 00:56:56,710
Mae hyn yn berffaith ar gyfer dychweliad.

951
00:56:56,710 --> 00:57:00,920
Felly hyd yn oed er, yn y gorffennol rydym wedi gwneud rhai enghreifftiau yn eithaf mympwyol yn cynnwys dychweliad

952
00:57:00,920 --> 00:57:03,430
nad oedd angen i fod yn ailadroddus, gyda stuctures data,

953
00:57:03,430 --> 00:57:07,820
yn enwedig coed, mae'n gais berffaith o hyn syniad o gymryd problem,

954
00:57:07,820 --> 00:57:12,920
crebachu, ac yna datrys yr un math o, ond yn llai, rhaglen.

955
00:57:12,920 --> 00:57:14,590
>> Felly, mae adeiledd arall yn ddata y gallwn eu cyflwyno.

956
00:57:14,590 --> 00:57:18,760
Mae hyn yn un wedi ei gynllunio ar yr olwg gyntaf i edrych cryptic, ond mae hyn yn un 'anhygoel.

957
00:57:18,760 --> 00:57:25,090
Felly, mae hwn yn strwythur data a elwir yn trie, trie, sy'n cael ei etifeddu o fedru adalw geiriau,

958
00:57:25,090 --> 00:57:30,210
nad yw wedi'i amlwg ail-cais-Val, ond dyna beth y byd yn galw y pethau hyn. Ceisiau. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
Mae'n strwythur coeden o ryw fath, ond mae pob un o'r nodau mewn trie

960
00:57:35,190 --> 00:57:41,280
ymddangos i fod yr hyn? Ac mae hyn yn ychydig yn gamarweiniol oherwydd ei fod yn fath o cryno.

961
00:57:41,280 --> 00:57:45,960
Ond mae'n edrych yn debyg bob nod yn y trie mewn gwirionedd yn arae.

962
00:57:45,960 --> 00:57:48,840
A hyd yn oed er nad yw'r awdur y diagram wedi dangos ei fod,

963
00:57:48,840 --> 00:57:54,130
yn yr achos hwn, mae'r trie yn strwythur data y mae ei bwrpas mewn bywyd yw storio geiriau

964
00:57:54,130 --> 00:57:57,330
fel A-l-i-c-e neu B-o-b.

965
00:57:57,330 --> 00:58:02,480
A'r ffordd y mae'r siopau data Alice a Bob a Charlie a Anita ac yn y blaen

966
00:58:02,480 --> 00:58:06,970
mae'n cael ei defnyddio amrywiaeth lle i storio Alice mewn trie,

967
00:58:06,970 --> 00:58:09,820
rydym yn dechrau ar y nod gwraidd sy'n edrych fel arae,

968
00:58:09,820 --> 00:58:12,080
ac mae wedi ei ysgrifennu mewn nodiant llaw-fer.

969
00:58:12,080 --> 00:58:15,070
Mae'r awdur yn hepgor ABCDEFG am nad oedd unrhyw enwau â hynny.

970
00:58:15,070 --> 00:58:19,150
Maent yn unig yn dangos M a P a T, ond yn yr achos hwn,

971
00:58:19,150 --> 00:58:22,780
gadewch i ni symud i ffwrdd oddi wrth Alice a Bob a Charlie i rai enwau sydd yma.

972
00:58:22,780 --> 00:58:25,670
Maxwell mewn gwirionedd yn y diagram.

973
00:58:25,670 --> 00:58:29,570
Felly sut wnaeth y siop awdur M-a-x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Ef neu hi ddechrau yn y nod gwraidd, ac aeth i [M], felly yn fras 13, y lleoliad 13eg yn y rhesi.

975
00:58:36,990 --> 00:58:40,750
Yna oddi yno, mae pwyntydd.

976
00:58:40,750 --> 00:58:42,760
Mae pwyntydd yn arwain i un arall amrywiaeth.

977
00:58:42,760 --> 00:58:47,880
Oddi yno yr awdur mynegeio i mewn i'r amrywiaeth yn y lleoliad A, fel y darluniwyd yno ar y chwith uchaf,

978
00:58:47,880 --> 00:58:52,250
ac yna ef neu hi yn dilyn y pwyntydd i'r llall array,

979
00:58:52,250 --> 00:58:55,460
ac aeth at y pwyntydd yn y lleoliad X.

980
00:58:55,460 --> 00:58:59,840
Yna, yn yr amrywiaeth nesaf lleoliad, W E, L, L, ac yn y blaen,

981
00:58:59,840 --> 00:59:03,090
ac yn olaf, gadewch i ni mewn gwirionedd yn ceisio rhoi darlun i hyn.

982
00:59:03,090 --> 00:59:05,380
Beth yw edrych yn nod fel mewn cod?

983
00:59:05,380 --> 00:59:11,820
Mae nod mewn trie yn cynnwys amrywiaeth o awgrymiadau i nodau mwy.

984
00:59:11,820 --> 00:59:16,090
Ond mae 'na hefyd i fod yn rhyw fath o werth boolean, o leiaf yn y gweithredu.

985
00:59:16,090 --> 00:59:18,770
Yr wyf yn digwydd i alw ei is_word. Pam?

986
00:59:18,770 --> 00:59:22,670
Oherwydd pan fyddwch chi'n gosod Maxwell, nad ydych yn gosod

987
00:59:22,670 --> 00:59:25,300
unrhyw beth i mewn i'r strwythur data.

988
00:59:25,300 --> 00:59:27,480
Nid ydych yn ysgrifennu M. Nid ydych yn ysgrifennu X.

989
00:59:27,480 --> 00:59:30,240
Mae pob ydych yn ei wneud yn dilyn awgrymiadau.

990
00:59:30,240 --> 00:59:33,360
Y pwyntydd sy'n cynrychioli M, yna bydd y pwyntydd sy'n cynrychioli A,

991
00:59:33,360 --> 00:59:36,310
yna bydd y pwyntydd sy'n cynrychioli X, yna C, E, L, L,

992
00:59:36,310 --> 00:59:41,950
ond yr hyn y mae angen i chi ei wneud ar y diwedd yn fath o fynd, gwirio, yr wyf yn cyrraedd y lleoliad hwn.

993
00:59:41,950 --> 00:59:45,560
Roedd gair sy'n dod i ben yma yn y strwythur data.

994
00:59:45,560 --> 00:59:48,190
>> Felly beth yw trie yn cael ei llenwi iawn gyda'r awdur a'r dewis i gynrychioli

995
00:59:48,190 --> 00:59:51,880
hyn terminuses â thrionglau bach.

996
00:59:51,880 --> 00:59:56,470
Mae hyn yn unig yn golygu bod y ffaith y triongl sydd yma, y ​​gwerth boolaidd o wir

997
00:59:56,470 --> 00:59:59,200
yn golygu os ydych yn mynd yn ôl yn y goeden,

998
00:59:59,200 --> 01:00:02,420
mae hynny'n golygu gair a enwir Maxwell yn hyn o beth.

999
01:00:02,420 --> 01:00:04,870
Ond y gair, foo er enghraifft,

1000
01:00:04,870 --> 01:00:07,970
Nid yw yn y goeden, oherwydd os byddaf yn dechrau ar y nod gwraidd i fyny yma ar ben,

1001
01:00:07,970 --> 01:00:14,030
Does dim, pwyntydd f dim pwyntydd o, dim pwyntydd o. Nid yw Foo yn enw yn y geiriadur.

1002
01:00:14,030 --> 01:00:22,460
Ond ar y llaw arall, weledol, t-u-r-i-n-g. Unwaith eto, doeddwn i ddim yn storio t neu u neu r neu i neu n neu g.

1003
01:00:22,460 --> 01:00:29,820
Ond wnes i storio yn y strwythur data gwerth tramwy wir i lawr yma yn y nod - yn y goeden

1004
01:00:29,820 --> 01:00:33,030
drwy osod y gwerth boolaidd o is_word i gwir.

1005
01:00:33,030 --> 01:00:35,740
Felly trie yn fath o strwythur hwn meta ddiddorol iawn,

1006
01:00:35,740 --> 01:00:39,810
lle nad ydych wirioneddol yn storio'r geiriau eu hunain ar gyfer y math hwn o geiriadur.

1007
01:00:39,810 --> 01:00:45,100
I fod yn glir, eich bod newydd storio ie neu na, oes air sy'n dod i ben yma.

1008
01:00:45,100 --> 01:00:46,430
>> Nawr beth yw'r goblygiadau?

1009
01:00:46,430 --> 01:00:51,120
Os oes gennych 150,000 o eiriau mewn geiriadur eich bod yn ceisio i'w cadw mewn cof

1010
01:00:51,120 --> 01:00:53,400
defnyddio rhywbeth fel rhestr cysylltiedig,

1011
01:00:53,400 --> 01:00:56,870
ydych yn mynd i gael 150,000 nodau yn eich rhestr cysylltiedig.

1012
01:00:56,870 --> 01:01:00,250
A gallai dod o hyd i un o'r geiriau hynny yn nhrefn yr wyddor yn cymryd O (n) amser.

1013
01:01:00,250 --> 01:01:04,370
Amser llinol. Ond yn yr achos yma o trie,

1014
01:01:04,370 --> 01:01:09,210
beth amser yn rhedeg o ddod o hyd i air?

1015
01:01:09,210 --> 01:01:17,390
Mae'n troi allan y harddwch yma yw bod hyd yn oed os oes gennych 149,999 o eiriau sydd eisoes yn y geiriadur,

1016
01:01:17,390 --> 01:01:20,170
rhoi ar waith fel gyda'r strwythur data,

1017
01:01:20,170 --> 01:01:25,560
faint o amser mae'n ei gymryd i ddod o hyd i neu rhowch un person yn fwy i mewn i hynny, fel Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Wel, dim ond 5, efallai 6 cham ar gyfer y cymeriad llusgo.

1019
01:01:30,640 --> 01:01:32,880
Oherwydd bod y presense o enwau eraill yn y strwythur

1020
01:01:32,880 --> 01:01:35,340
nad yw'n cael yn y ffordd o mewnosod Alice.

1021
01:01:35,340 --> 01:01:39,640
Ar ben hynny, dod o hyd i Alice unwaith y mae 150,000 o eiriau yn y geiriadur

1022
01:01:39,640 --> 01:01:41,960
nad yw'n cael yn eich ffordd o ddod o hyd Alice o gwbl,

1023
01:01:41,960 --> 01:01:46,880
oherwydd Alice yn. . . . . yma, oherwydd fy mod yn dod o hyd i werth boolaidd.

1024
01:01:46,880 --> 01:01:50,920
Ac nid os nad oes boolean wir, yna Alice yn y strwythur data o eiriau.

1025
01:01:50,920 --> 01:01:56,220
Mewn geiriau eraill, yr amser yn rhedeg o ddod o hyd pethau a gosod pethau i mewn i'r newydd

1026
01:01:56,220 --> 01:02:01,920
data strwythur trie yw O o - nid yw'n n.

1027
01:02:01,920 --> 01:02:05,730
Oherwydd bod y presense o 150,000 o bobl yn cael unrhyw effaith ar Alice, mae'n ymddangos.

1028
01:02:05,730 --> 01:02:11,560
Felly, gadewch i ni ei alw k, lle mae k yn uchafswm hyd y gair yn Saesneg

1029
01:02:11,560 --> 01:02:14,050
sef, yn nodweddiadol dim mwy na 20-rhywbeth cymeriadau.

1030
01:02:14,050 --> 01:02:17,940
Felly k yn gysonyn. Felly, y Greal Sanctaidd rydym yn ymddangos i wedi dod o hyd yn awr

1031
01:02:17,940 --> 01:02:26,000
yw bod o trie, cysonyn amser ar gyfer mewnosod, ar gyfer lookups, ar gyfer dileadau.

1032
01:02:26,000 --> 01:02:29,170
Oherwydd bod y nifer o bethau eisoes yn y strwythur,

1033
01:02:29,170 --> 01:02:32,600
nad ydynt yn hyd yn oed yn gorfforol yno. Unwaith eto, maen nhw jyst yn trefnu o gwirio, ie neu ddim,

1034
01:02:32,600 --> 01:02:35,050
yn cael unrhyw effaith ar ei amser rhedeg yn y dyfodol.

1035
01:02:35,050 --> 01:02:37,940
>> Ond mae rhaid i fod yn dal, fel arall ni fyddem wedi gwastraffu cymaint o amser

1036
01:02:37,940 --> 01:02:41,460
ar yr holl strwythurau data arall yn unig i pen draw yn cael yr un gyfrinach sy'n anhygoel.

1037
01:02:41,460 --> 01:02:46,410
Felly, pa bris yr ydym yn talu i gyflawni hyn fawredd yma? Space.

1038
01:02:46,410 --> 01:02:49,010
Mae hyn yn peth yn enfawr. A'r rheswm fod yr awdur

1039
01:02:49,010 --> 01:02:52,400
nid oedd yn bresennol yma, yn sylwi bod yr holl bethau hyn sy'n edrych fel arrays,

1040
01:02:52,400 --> 01:02:55,400
nad oedd yn tynnu gweddill y goeden, gweddill y trie,

1041
01:02:55,400 --> 01:02:58,060
oherwydd eu bod nid yn unig yn berthnasol i'r stori.

1042
01:02:58,060 --> 01:03:01,870
Ond mae pob un o'r nodau eang yn super, a phob nod yn y goeden yn cymryd i fyny

1043
01:03:01,870 --> 01:03:07,780
26 neu mewn gwirionedd, gallai fydd 27 gymeriadau oherwydd yn yr achos hwn roeddwn yn cynnwys lle ar gyfer y collnod

1044
01:03:07,780 --> 01:03:09,980
fel y gallem gael geiriau apostrophized.

1045
01:03:09,980 --> 01:03:14,450
Yn yr achos hwn, mae'r rhain yn araeau eang. Felly hyd yn oed er nad ydynt yn picutured,

1046
01:03:14,450 --> 01:03:18,190
mae hyn yn cymryd i fyny swm enfawr o RAM.

1047
01:03:18,190 --> 01:03:20,670
A allai fod yn iawn, yn enwedig ar mewn caledwedd modern,

1048
01:03:20,670 --> 01:03:25,650
ond dyna'r tradeoff. Rydym yn cael llai o amser drwy wario mwy o le.

1049
01:03:25,650 --> 01:03:28,580
Felly, lle mae hyn i gyd yn mynd?

1050
01:03:28,580 --> 01:03:32,640
Wel, gadewch i ni wneud - gadewch i ni weld yma.

1051
01:03:32,640 --> 01:03:39,510
Gadewch i ni wneud naid i'r guy yma.

1052
01:03:39,510 --> 01:03:43,450
>> Credwch neu beidio, hwyl gymaint ag y C wedi bod ers peth amser bellach,

1053
01:03:43,450 --> 01:03:48,130
rydym yn cyrraedd y pwynt yn y semester lle mae'n amser i newid i bethau mwy modern.

1054
01:03:48,130 --> 01:03:50,950
Pethau ar lefel uwch. A hyd yn oed pe bai ar gyfer yr ychydig wythnosau nesaf

1055
01:03:50,950 --> 01:03:54,580
byddwn yn parhau i drochi ein hunain yn y byd o awgrymiadau a rheoli cof

1056
01:03:54,580 --> 01:03:57,210
i gael y cysur ag y gallwn adeiladu arni,

1057
01:03:57,210 --> 01:04:01,270
diwedd y gêm yn y pen draw i gyflwyno, nid yn eironig, yr iaith hon.

1058
01:04:01,270 --> 01:04:03,330
Byddwn yn gwario, fel 10 munud yn siarad am HTML.

1059
01:04:03,330 --> 01:04:05,950
Mae'r holl HTML yn yn iaith markup, a beth yw iaith markup yn

1060
01:04:05,950 --> 01:04:10,220
Dyma'r gyfres o gromfachau agored a bracedi caeedig sy'n dweud 'wneud cam eofn hwn'

1061
01:04:10,220 --> 01:04:12,000
'Gwneud hyn yn italig' 'gwneud hyn yn ganolog.'

1062
01:04:12,000 --> 01:04:14,250
Nid yw popeth sy'n ddeallusol ddiddorol, ond mae'n super defnyddiol.

1063
01:04:14,250 --> 01:04:16,650
Ac mae'n sicr yn hollbresennol y dyddiau hyn.

1064
01:04:16,650 --> 01:04:19,450
Ond beth sy'n bwerus am y byd o HTML, a rhaglennu ar y we yn fwy cyffredinol,

1065
01:04:19,450 --> 01:04:25,910
yn adeiladu pethau deinamig; ysgrifennu cod mewn ieithoedd fel PHP neu Python neu Ruby neu Java neu C #.

1066
01:04:25,910 --> 01:04:30,360
Really, beth bynnag yw eich dewis iaith yw, a chynhyrchu HTML ddynamig.

1067
01:04:30,360 --> 01:04:32,960
Cynhyrchu rywbeth o'r enw CSS ddynamig.

1068
01:04:32,960 --> 01:04:35,810
Defnyddiwyd taflenni arddull rhaeadrol, sydd hefyd am estheteg.

1069
01:04:35,810 --> 01:04:41,360
Ac felly hyd yn oed er, heddiw, os byddaf yn mynd i ryw wefan fel y Google.com cyfarwydd,

1070
01:04:41,360 --> 01:04:46,100
ac rwy'n mynd i weld, datblygwr, ffynhonnell marn i, sydd efallai eich bod wedi gwneud o'r blaen,

1071
01:04:46,100 --> 01:04:49,800
ond yn mynd i weld y ffynhonnell, y pethau yn ôl pob tebyg yn edrych yn eithaf cryptig.

1072
01:04:49,800 --> 01:04:55,320
Ond mae hyn yn y cod sylfaenol sy'n gweithredu Google.com.

1073
01:04:55,320 --> 01:04:57,940
Ar y pen blaen. Ac mewn gwirionedd yn hyn oll yw estheteg pethau blewog.

1074
01:04:57,940 --> 01:05:01,740
Mae hyn yn CSS i fyny yma. Os byddaf yn cadw sgrolio i lawr y byddwn yn cael rhywfaint o stwff lliw-godio.

1075
01:05:01,740 --> 01:05:06,890
Mae hyn yn HTML. Google cod yn edrych fel baw, ond os wyf mewn gwirionedd yn agor ffenestr wahanol,

1076
01:05:06,890 --> 01:05:09,380
gallwn weld peth strwythur i hyn.

1077
01:05:09,380 --> 01:05:12,640
Os byddaf yn agor y fyny, sylwi yma, mae ychydig yn fwy darllenadwy.

1078
01:05:12,640 --> 01:05:16,850
Rydym yn mynd i weld cyn bo hir tag hwn, [word] yn tag,

1079
01:05:16,850 --> 01:05:23,520
HTML, pennaeth, corff, div, sgript, ardal testun, rhychwant, sy'n canolbwyntio ar, div.

1080
01:05:23,520 --> 01:05:26,770
Ac mae hyn hefyd yn trefnu o cryptic-edrych ar yr olwg gyntaf,

1081
01:05:26,770 --> 01:05:30,890
ond mae pob o'r llanastr hwn yn dilyn patrymau penodol, a phatrymau eu hailadrodd,

1082
01:05:30,890 --> 01:05:33,850
felly unwaith i ni gael y pethau sylfaenol i lawr, byddwch yn gallu ysgrifennu cod fel hyn

1083
01:05:33,850 --> 01:05:37,550
ac yna trin cod fel hyn drwy ddefnyddio eto iaith arall, a elwir yn JavaScript.

1084
01:05:37,550 --> 01:05:40,440
Ac JavaScript yn iaith sy'n rhedeg tu mewn i borwr

1085
01:05:40,440 --> 01:05:44,380
heddiw yr ydym yn eu defnyddio ar gyrsiau Harvard, ar gyfer y cwrs siopa offeryn sy'n fapiau Google yn defnyddio

1086
01:05:44,380 --> 01:05:48,660
i roi criw cyfan o egni, Facebook yn rhoi i chi ddangos diweddariadau statws amrantiad,

1087
01:05:48,660 --> 01:05:51,430
Twitter yn ei defnyddio i ddangos i chi tweets yn syth.

1088
01:05:51,430 --> 01:05:53,820
Mae hyn i gyd byddwn yn dechrau i drochi ein hunain ynddo

1089
01:05:53,820 --> 01:05:57,190
Ond i gyrraedd yno, mae angen i ni ddeall rhywbeth bach am y Rhyngrwyd.

1090
01:05:57,190 --> 01:06:01,130
Mae'r clip yma yn unig munud o hyd, a gadewch i ni gymryd yn ganiataol ar hyn o bryd mae hyn yn, mewn gwirionedd,

1091
01:06:01,130 --> 01:06:08,380
sut y mae'r Rhyngrwyd yn gweithio fel teaser ar gyfer yr hyn sydd ar fin dod. Yr wyf yn rhoi i chi "Warriors y Net."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ cerddoriaeth corws Araf ♫]

1093
01:06:14,720 --> 01:06:20,450
[Adroddwr Gwryw] Daeth gyda neges.

1094
01:06:20,450 --> 01:06:23,770
Gyda protocol ei holl hun.

1095
01:06:23,770 --> 01:06:37,270
[♫ cerddoriaeth electronig yn gyflymach ♫]

1096
01:06:37,270 --> 01:06:41,330
Daeth i fyd o waliau tân oer, yn ddidaro llwybryddion,

1097
01:06:41,330 --> 01:06:45,690
a'r peryglon llawer gwaeth na marwolaeth.

1098
01:06:45,690 --> 01:06:55,400
Mae'n gyflym. Mae'n gryf. Mae'n TCP / IP, ac mae wedi cael eich cyfeiriad.

1099
01:06:55,400 --> 01:06:59,250
Rhyfelwyr y Net.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Yr wythnos nesaf, yna. Y Rhyngrwyd. Rhaglennu ar y we. Mae hyn yn CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]