>> SIARADWR 1: pob hawl, felly rydym yn ôl.
Croeso i CS50.
Mae hyn yn y diwedd yr wythnos saith.
Felly, dwyn i gof bod y tro diwethaf, rydym yn dechrau edrych ar ychydig yn fwy soffistigedig
strwythurau data.
Ers hyd yn hyn, i gyd oedd gennym mewn gwirionedd ar gael i ni oedd hyn, arae.
>> Ond cyn i ni daflu y casgliad gan nad bob un sy'n ddiddorol, sydd yn wir mae'n
mewn gwirionedd yw, beth yw rhai o'r pwyntiau cadarnhaol o'r data syml
strwythur hyd yn hyn?
Beth yw ei dda?
Cyn belled ag yr ydym wedi gweld?
Beth ydych chi'n ei gael?
Dim byd.
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Beth sy'n bod?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: faint sefydlog.
Iawn, felly pam mae maint sefydlog da er bod?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: OK, felly mae'n effeithlon yn yr ystyr eich bod yn gallu dyrannu
swm penodol o le, a gobeithio, yn union gymaint
gofod ag y dymunwch.
Fel y gallai fod yn hollol yn fantais.
>> Beth sydd i fyny ochr arall o fyrdd?
Yeah?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Mae'r holl - mae'n ddrwg gennyf?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Pob y blychau er cof neu nesaf at ei gilydd.
Ac mae hynny'n ddefnyddiol - pam?
Mae hynny'n hollol wir.
Ond sut y gallwn fanteisio ar y gwirionedd?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Yn union, gallwn gadw golwg ar lle mae popeth yn unig trwy wybod
un cyfeiriad, sef gyfeiriad y beit cyntaf y darn o gof.
Neu yn achos y llinyn, cyfeiriad y cyntaf
torgoch yn y llinyn.
Ac oddi yno, gallwn ddod o hyd i ddiwedd y llinyn.
Gallwn ddod o hyd i'r ail elfen, y drydedd elfen, ac yn y blaen.
>> Ac felly y ffordd ffansi o ddisgrifio bod nodwedd yw bod araeau yn rhoi i ni
mynediad ar hap.
Dim ond drwy ddefnyddio'r sgwâr braced nodiant a nifer, gallwch neidio i
elfen benodol yn yr arae mewn amser yn gyson, O mawr
o un, fel petai.
>> Ond mae wedi bod rhai anfanteision.
Beth amrywiaeth beidio â gwneud yn hawdd iawn?
Beth sydd ddim yn dda?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Beth sy'n bod?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Ehangu o ran maint.
Felly anfanteision y rhesi yn union y gwrthwyneb i'r hyn y mae'r
upsides yn cael eu.
Felly, un o anfanteision yn ei fod yn faint penodol.
Felly, ni allwch gynyddu.
Gallwch ailddyrannu mwy darn o cof, ac yna symud yr hen elfennau
yn y casgliad newydd.
Ac yna ddim yr hen amrywiaeth, ar gyfer enghraifft, trwy ddefnyddio malloc neu debyg
swyddogaeth o'r enw realloc, sy'n ailddyrannu cof.
>> Realloc, wrth fynd heibio, yn ceisio rhoi i chi cof sy'n nesaf at y casgliad
sydd gennych yn barod.
Ond gallai symud pethau amgylch yn gyfan gwbl.
Ond yn fyr, mae hynny'n ddrud, dde?
Oherwydd os oes gennych darn o cof am maint hwn, ond ydych wir eisiau un
o'r maint hwn, ac rydych am i gadw yr elfennau gwreiddiol, mae gennych
fras broses copïo amser llinol sydd angen i ddigwydd o
hen amrywiaeth i newydd.
Ac mae'r realiti yn gofyn i'r gweithredu system eto ac eto ac
eto am y gall darnau mawr o gof yn dechrau i gostio i chi rhywfaint o amser yn ogystal.
Felly mae'n yn fendith ac yn felltith mewn cuddio'r, y ffaith bod arrays hyn
o faint penodol.
Ond os ydym yn cyflwyno rhywbeth yn lle hynny fel hyn, yr ydym yn a elwir yn gysylltiedig
rhestr, rydym yn cael ychydig o upsides a ychydig o anfanteision yma hefyd.
>> Felly restr cysylltiedig yn unig yw ddata strwythur sy'n cynnwys structs C yn y
achos, lle mae strwythur, galw i gof, yn unig cynhwysydd ar gyfer un neu fwy penodol
mathau o newidynnau.
Yn yr achos hwn, beth yn gwneud y mathau o ddata ymddangos i fod y tu mewn i'r strwythur y
tro diwethaf i ni a elwir yn nod?
Mae pob un o'r petryalau hyn yn nod.
A phob un o'r petryalau llai tu mewn iddo yn fath data.
Pa fathau wnaethom ni ddweud eu bod ar ddydd Llun?
Yeah?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: amrywiol a pwyntydd, neu yn fwy penodol, yn int, ar gyfer n,
a pwyntydd ar y gwaelod.
Mae'r ddau o'r rheiny yn digwydd i fod yn 32 darnau, yn leiaf ar gyfrifiadur fel hyn CS50
Offer, ac felly eu bod yn tynnu yn gyfartal o ran maint.
>> Felly, beth yn defnyddio'r pwyntydd er bod ar gyfer pob golwg?
Pam ychwanegu saeth hwn yn awr pan fydd araeau oedd mor neis ac yn lân ac yn syml?
Beth yw y pwyntydd wneud dros i ni ym mhob un o'r nodau hyn?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Yn union.
Mae'n dweud wrthych lle yr un nesaf.
Felly yr wyf yn fath o ddefnyddio'r gyfatebiaeth o defnyddio edau i ddatrys y
edafu nodau hyn gyda'i gilydd.
A dyna'n union yr hyn rydym yn ei wneud gyda awgrymiadau gan fod pob un o'r rhain
darnau o gof efallai na all neu fod yn cydgyffwrdd, gefn wrth gefn wrth gefn
tu mewn RAM, oherwydd bod gan bob tro y byddwch yn ffoniwch malloc dweud, yn rhoi digon i mi
bytes am nod newydd, y gallai fod yma neu gallai fod yma.
Efallai ei fod yma.
Dim ond nad ydych yn gwybod.
>> Ond yn defnyddio arwyddion yn y cyfeiriadau nodau hynny, gallwch pwyth iddynt
at ei gilydd mewn ffordd sy'n edrych ar eu golwg fel rhestr hyd yn oed os yw'r pethau hyn yn
pob gwasgaru drwy gydol eich un neu eich dau neu eich bedwar gigabeit o RAM
tu mewn i'ch cyfrifiadur eich hun.
>> Felly mae'r anfantais, yna, wrth restr cysylltiedig yw beth?
Beth yw pris rydym yn yn ôl pob golwg yn talu?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Mwy o le, dde?
Rydym wedi, yn yr achos hwn, dyblu y swm o le oherwydd ein bod wedi mynd
o 32 ddarnau ar gyfer pob nod, ar gyfer pob int, felly, yn awr 64 o ddarnau oherwydd bod yn rhaid i
cadw o amgylch pwyntydd hefyd.
Byddwch yn cael mwy effeithlon os yw eich strwythur yn fwy na hyn peth syml.
Os ydych chi mewn gwirionedd yn cael fyfyriwr y tu mewn un ohonynt yn ychydig o linynnau ar gyfer
enw a thy, efallai rhif adnabod, efallai rhai meysydd eraill yn gyfan gwbl.
>> Felly, os oes gennych strwythur ddigon mawr, yna efallai cost y pwyntydd yn
Nid yw mor bwysig â hynny.
Mae hwn yn dipyn o achos cornel yn y rydym yn storio cyntefig mor syml
tu mewn i'r rhestr cysylltiedig.
Ond y pwynt yw yr un fath.
Rydych yn sicr yn gwario mwy cof, ond eich bod yn cael
hyblygrwydd.
Oherwydd erbyn hyn os ydw i eisiau ychwanegu elfen ar ddechrau'r y rhestr hon,
Rhaid i mi ddyrannu nod newydd.
Ac mae'n rhaid i mi jyst diweddaru rhai saethau rywsut at jyst yn symud
rhai awgrymiadau o gwmpas.
>> Os ydw i eisiau rhoi rhywbeth i mewn i'r nghanol y rhestr, nid oes rhaid i mi
gwthio pawb o'r neilltu fel y gwnaethom yn wythnos diwethaf gyda'n gwirfoddolwyr sy'n
yn cynrychioli amrywiaeth.
Gall Fi jyst dyrannu nod newydd ac yna dim ond dangos y saethau mewn
cyfarwyddiadau wahanol oherwydd nad yw'n rhaid i chi aros yn wirioneddol
cof linell wir fy mod wedi tynnu yma ar y sgrin.
>> Ac yna yn olaf, os ydych am i fewnosod rhywbeth ar ddiwedd y rhestr, mae'n
hyd yn oed yn haws.
Mae hyn yn fath o nodiant mympwyol, ond mae pwyntydd 34, yn cymryd dyfalu.
Beth yw gwerth ei pwyntydd y rhan fwyaf o math tynnu tebygol fel hen
antena ysgol yno?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Mae'n debyg null.
Ac yn wir dyna un awdur cynrychiolaeth o null.
Ac mae'n null oherwydd eich bod yn hollol angen i ni wybod ble ddiwedd cysylltiedig
rhestr yw, rhag eich bod yn cadw canlynol ac dilyn ac yn dilyn y saethau hyn
i ryw werth garbage.
Felly bydd null arwydd nad oes unrhyw mwy o nodau i'r dde o'r rhif 34,
yn yr achos hwn.
>> Felly, rydym yn cynnig ein bod yn gallu gweithredu nod hwn mewn cod.
Ac rydym wedi gweld y math hwn ar gystrawen blaen.
Typedef yn unig yn diffinio math newydd ar gyfer ni, yn rhoi gyfystyr ni fel
llinyn oedd torgoch *.
Yn yr achos hwn, mae'n mynd i roi i ni nodiant llaw-fer fel bod strwythur nod
Gellir hytrach dim ond ei ysgrifennu fel nod, sydd yn llawer glanach.
Mae'n llawer llai verbose.
>> Y tu mewn o nod yn ôl pob golwg yn int n galw, ac yna strwythur nod *
sy'n golygu yn union yr hyn yr ydym am i'r saethau i olygu, pwyntydd i un arall
nod y math data union un fath.
Ac yr wyf yn cynnig y gallem gweithredu swyddogaeth chwilio fel hyn, sydd ar hyn o
Efallai yr olwg gyntaf yn ymddangos ychydig o gymhleth.
Ond gadewch i ni ei weld yn y cyd-destun.
>> Gadewch i mi fynd draw at y peiriant yma.
Gadewch i mi agor ffeil o'r enw rhestr sero dot h.
Ac mai dim ond yn cynnwys y diffiniad yr ydym jyst yn gweld funud yn ôl am y data hwn
math a elwir yn nod.
Felly, rydym wedi rhoi bod i mewn i ffeil h dot.
>> Ac wrth fynd heibio, er bod hyn rhaglen eich bod chi ar fin ei weld yw
nid bob un sy'n gymhleth, mae'n wir confensiwn wrth ysgrifennu rhaglen i
rhoi pethau fel mathau o ddata, i dynnu cysonion weithiau, y tu mewn eich
ffeil flaen ac nid o reidrwydd yn eich ffeil C, yn sicr pan fydd eich
rhaglenni fynd yn fwy ac yn fwy, fel y eich bod yn gwybod ble i chwilio ar gyfer
dogfennau mewn rhai achosion, neu ar gyfer nwyddau sylfaenol fel hyn, mae'r
diffiniad o ryw fath.
>> Os wyf yn awr yn agor rhestr sero dot c, sylwi ar ychydig o bethau.
Mae'n cynnwys ychydig o ffeiliau pennawd, y rhan fwyaf o yr ydym wedi ei weld o'r blaen.
Mae'n cynnwys ei ffeil flaen ei hun.
>> Ac wrth fynd heibio, pam mae hynny'n ddwbl dyfyniadau yma, yn hytrach na'r ongl
cromfachau ar y llinell sy'n Rwyf wedi tynnu sylw yno?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Yeah felly mae'n ffeil lleol.
Felly, os yw'n ffeil lleol eich hunain yma on line 15, er enghraifft, byddwch yn defnyddio
y dyfyniadau dwbl yn lle hynny y cromfachau onglog.
>> Nawr mae hyn yn fath o ddiddorol.
Hysbysu fy mod wedi datgan byd-eang amrywiol yn y rhaglen hon ar-lein 18
a elwir yn gyntaf, y syniad yw hyn yn mynd i fod yn pwyntydd i'r gyntaf
nod yn fy rhestr gysylltiedig, ac rwyf wedi ymgychwyn iddo null, gan fy mod i wedi
heb ei dyrannu unrhyw ostyngiad gwirioneddol nodau eto.
>> Felly, mae hyn yn cynrychioli, ar ffurf lluniau, yr hyn yr ydym Gwelodd funud yn ôl yn y llun fel
y pwyntydd ar y graddau y gadael ochr llaw.
Felly, ar hyn o bryd, y pwyntydd Nid oes gan saeth.
Mae'n lle hynny yn unig null.
Ond mae'n cynrychioli beth fydd y chyfeiriad y gwir cyntaf
nod yn y rhestr hon.
Felly, yr wyf wedi rhoi ar waith ei fod yn fyd-eang oherwydd, fel y gwelwch, hyn i gyd
mewn bywyd rhaglen yn ei wneud yw gweithredu rhestr gysylltu i mi.
>> Nawr mae gen i ychydig o prototeipiau yma.
Penderfynais i weithredu nodweddion fel dileu, mewnosod, chwilio, a
llwybro -
y daith olaf dim ond bod ar draws y rhestr, argraffu ei elfennau.
Ac yn awr dyma fy mhrif arferol.
Ac ni fyddwn yn treulio gormod o amser ar hyn gan fod hyn yn fath o, gobeithio
hen het erbyn hyn.
>> Rydw i'n mynd i wneud y canlynol, tra bod y defnyddiwr yn cydweithio.
Felly un, yr wyf i'n mynd i argraffu ar y fwydlen.
Ac yr wyf wedi fformatio fel lân ag y gallwn.
Os mathau y defnyddiwr mewn un, mae hynny'n golygu maent am ei ddileu rhywbeth.
Os mathau y defnyddiwr mewn dau, mae hynny'n golygu maent am i fewnosod rhywbeth.
Ac yn y blaen.
Rydw i'n mynd i wedyn yn ysgogi yna am orchymyn.
Ac yna dwi'n mynd i ddefnyddio GetInt.
>> Felly, mae hwn yn menuing syml iawn rhyngwynebu lle os oes gen ti i deipio
rhif mapio i un o orchmynion hynny.
Ac yn awr yr wyf wedi switsh glân 'n glws datganiad sy'n mynd i newid ar
beth bynnag y defnyddiwr deipio i mewn
Ac os ydynt yn teipio un, byddaf yn ffoniwch dileu a thorri.
Os ydynt yn teipio ddau, byddaf ffoniwch mewnosod a torri.
>> Ac yn awr rhybudd rwyf wedi rhoi pob y rhain ar yr un llinell.
Penderfyniad arddull yn unig yw hwn.
Fel arfer, rydym wedi gweld rhywbeth fel hyn.
Ond Fi jyst benderfynu, a dweud y gwir, fy rhaglen edrych yn fwy darllenadwy oherwydd
dim ond pedwar achos i dim ond rhestru fel hyn.
Defnydd gwbl gyfreithlon o arddull.
Ac yr wyf i'n mynd i wneud hyn cyhyd ag y Nid yw'r defnyddiwr wedi teipio ddim, yr wyf yn
penderfynu y byddant yn golygu eu bod eisiau rhoi'r gorau iddi.
>> Felly sylwi ar beth dw i'n mynd i'w wneud yma.
Rydw i'n mynd i ryddhau y rhestr yn ôl pob golwg.
Ond mwy am hynny mewn dim ond hyn o bryd.
Gadewch i ni yn gyntaf yn rhedeg y rhaglen hon.
Felly, gadewch i mi wneud mwy o derfynell ffenestr, dot rhestr slaes 0.
Rydw i'n mynd i fynd yn ei flaen ac yn mewnosod gan teipio dau, mae nifer tebyg i 50, ac yn awr
byddwch yn gweld y rhestr yn awr yn 50.
Ac mae fy testun yn unig sgrolio i fyny ychydig.
Felly, erbyn hyn yn sylwi ar y rhestr hon yn cynnwys y rhif 50.
>> Gadewch i ni wneud mewnosoder arall drwy gymryd dau.
Gadewch i deipio yn y nifer fel un.
Rhestr bellach yn un, ac yna 50.
Felly cynrychiolaeth testunol hyn yn unig y rhestr.
A gadewch i ni ychwanegu un yn fwy rhif, er enghraifft y rhif 42, sy'n gobeithio
yn mynd i roi diwedd ar i fyny yn y canol, gan fod rhaglen hon yn fath arbennig,
elfennau y mae'n mewnosod nhw.
Felly mae gennym.
Rhaglen syml super a allai gwbl wedi defnyddio amrywiaeth, ond yr wyf yn
digwydd bod yn defnyddio rhestr gysylltiedig yn union fel y gallaf ddeinamig
tyfu ac yn crebachu ei.
>> Felly, gadewch i ni edrych ar gyfer chwilio, os wyf rhedeg gorchymyn tri, yr wyf am i chwilio
am, dyweder, y rhif 43.
A dim byd Daethpwyd o hyd yn ôl pob golwg, oherwydd fy mod yn cael unrhyw ymateb yn ôl.
Felly, gadewch i ni wneud hyn eto.
Chwilio.
Gadewch i ni chwilio am 50, neu yn hytrach chwilio am 42, sydd â 'n glws
ychydig o ystyr cynnil.
Ac yr wyf yn dod o hyd i'r ystyr bywyd yno.
Rhif 42, os nad ydych yn gwybod y cyfeiriad, Google.
Mae pob hawl.
Felly, beth mae hyn rhaglen wneud i mi?
'I' jyst fy ngalluogi i fewnosod a thrwy hynny bell ac yn chwilio am elfennau.
>> Gadewch i ni yn gyflym ymlaen, yna, er mwyn swyddogaeth honno rydym yn bwrw golwg ar
ar ddydd Llun fel ymlid.
Felly swyddogaeth hon, yr wyf yn gwneud cais, chwilio am elfen yn y rhestr gan gyntaf
un, gan annog y defnyddiwr ac yna galw GetInt i gael int gwirioneddol
eich bod am chwilio am.
>> Yna sylwi ar hyn.
Rydw i'n mynd i greu newidyn dros dro yn unol 188 enw pwyntydd -
PTR -
gallai fod wedi ei alw unrhyw beth.
Ac mae'n pwyntydd i nod oherwydd dywedais nod * yno.
A dwi'n ymgychwyn i fod yn hafal i yn gyntaf er mwyn i mi gael fy effeithiol
bys, fel petai, ar yr union Elfen gyntaf y rhestr.
Felly, os bydd fy llaw dde yma yw PTR rwy'n pwyntio at yr un peth yn gyntaf
yn pwyntio at.
>> Felly, bellach yn ôl mewn cod, beth sy'n digwydd nesaf -
mae hwn yn batrwm cyffredin wrth ailadrodd dros strwythur fel
restr cysylltiedig.
Rydw i'n mynd i wneud y canlynol wrth Nid pwyntydd yn hafal i null Felly, er
Nid yw fy bys yn pwyntio ar ryw null gwerth, os pwyntydd saeth n hafal n.
Byddwn yn sylwi gyntaf y n yw yr hyn y mae'r defnyddiwr deipio yn y GetInts galw yma.
>> Ac pwyntydd saeth n golygu beth?
Wel, os ydym yn mynd yn ôl at y llun yma, os oes gen i bys bwyntio at
y nod cyntaf yn cynnwys naw, y saeth yn ei hanfod yn golygu mynd i'r
nod a chrafangia 'r gwerth yn y lleoliad n, yn yr achos hwn, roedd y maes data a elwir yn n.
>> Fel o'r neilltu - ac yr ydym yn gweld hyn cwpl o wythnosau yn ôl pan ofynnir i rywun -
chystrawen hyn yn newydd, ond nid yw'n yn rhoi pwerau i ni ein bod yn
Nid oedd wedi gwneud hynny'n barod.
Beth oedd hyn yn ymadrodd sy'n cyfateb i ddefnyddio dot nodiant a seren cwpl
o wythnosau yn ôl pan fyddwn yn plicio yn ôl haen hwn ychydig cyn pryd?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Yn union, roedd yn seren, ac yna roedd seren dot n, gyda
cromfachau yma, sy'n edrych, dweud y gwir, yr wyf yn credu bod llawer
mwy cryptig i ddarllen.
Ond seren pwyntydd, fel bob amser, modd mynd yno.
Ac unwaith y byddwch chi yno, pa ddata maes yn ydych chi am gael mynediad?
Dda yr ydych yn defnyddio'r nodiant dot i gael mynediad at maes data structs, ac yr wyf yn
benodol eisiau n.
>> Dweud y gwir, byddwn yn dadlau hyn yn unig yn fwy anodd i'w darllen.
Mae'n anoddach i gofio lle yn y cromfachau mynd, y
seren a hynny i gyd.
Felly, yn y byd mabwysiadu rhai cystrawennol siwgr, fel petai.
Dim ond ffordd sexy o ddweud, mae hyn yn gyfwerth, a
efallai yn fwy 'n athrylithgar.
Os pwyntydd yn wir yn pwyntydd, y arrow nodiant yn golygu mynd yno ac yn dod o hyd i
maes yn yr achos hwn a elwir yn n.
>> Felly os wyf yn ei chael yn, sylwi ar yr hyn yr wyf yn ei wneud.
Yr wyf yn syml argraffu, yr wyf yn dod o hyd cant i, llenwi yn y gwerth ar gyfer y int.
Galwaf cysgu am un eiliad yn unig i fath o bethau oedi ar y sgrin i
rhoi'r defnyddiwr yn ail i amsugno beth yn union ddigwyddodd.
Ac yna mi dorri.
Fel arall, beth ddylwn i ei wneud?
Byddaf yn diweddaru'r pwyntydd i gyfleoedd cyfartal arrow pwyntydd nesaf.
>> Felly, dim ond i fod yn glir, mae hyn yn golygu mynd yno, gan ddefnyddio fy hen nodiant-ysgol.
Felly mae hyn yn unig yn golygu i fynd i ba bynnag eich bod yn tynnu sylw at, sydd yn yr union
achos cyntaf yw i ddim yn pwyntio at y strwythur gyda naw ynddo.
Felly, yr wyf wedi mynd yno.
Ac yna y nodiant dot yn golygu, cael y gwerth arno nesaf.
>> Ond mae'r werth, hyd yn oed er ei fod yn tynnu fel gul, yn unig yw rhif.
Mae'n cyfeiriad rhifol.
Felly, un llinell o god hwn, p'un a ysgrifenedig fel hyn, y mwyaf cryptig
ffordd, neu fel hyn, mae ychydig yn fwy ffordd sythweledol, yn unig yn golygu symud fy llaw
oddi wrth y nod cyntaf i'r un nesaf, ac yna yr un nesaf, ac yna
un nesaf, ac yn y blaen.
>> Felly, ni fyddwn yn trigo ar y llaw arall gweithrediadau o mewnosod a dileu
a llwybro, y ddau gyntaf sydd yn ymwneud yn deg.
Ac yr wyf yn meddwl ei fod yn eithaf hawdd i gael colli wrth wneud hynny ar lafar.
Ond beth y gallwn ei wneud yma yw ceisio penderfynu sut
orau o wneud hyn ar eu golwg.
Oherwydd byddwn yn cynnig, os ydym yn eisiau i fewnosod elfennau i mewn i hyn
rhestr bresennol, sy'n Mae pum elfen -
9, 17, 22, 26, a 33 -
os wyf yn mynd i roi hyn ar waith yn cod, angen i mi ystyried sut i fynd
am wneud hyn.
>> A byddwn yn cynnig cymryd camau babi lle, yn yr achos hwn yr wyf yn golygu, beth yw'r
y senarios posibl ein bod yn allai ddod ar eu traws yn gyffredinol?
Wrth weithredu mewnosoder ar gyfer cysylltiedig rhestr, mae hyn yn unig fydd yn digwydd i fod yn
enghraifft benodol o faint bump.
Wel, os ydych am osod nifer, yn hoffi dweud y rhif un, ac
cadw trefn didoli, lle amlwg â nifer angen un
mynd yn yr enghraifft benodol?
Fel ar y dechrau.
>> Ond yr hyn sy'n ddiddorol yw bod yna os ydych am i fewnosod un i mewn i hyn
rhestr, mae angen yr hyn y pwyntydd arbennig i gael ei diweddaru yn ôl pob golwg?
Yn gyntaf.
Felly, byddwn yn dadlau, mae hyn yn yr achos cyntaf y byddem efallai am ystyried, a
senario sy'n cynnwys mewnosod ar ddechrau'r rhestr.
>> Gadewch i ni tyn i ffwrdd efallai mae mor hawdd neu hyd yn oed achos yn haws, yn gymharol siarad.
Gadewch i ni dybio Yr wyf am i mewnosoder y rhif 35 er mwyn didoli.
Mae'n amlwg yn perthyn dros yno.
Felly, yr hyn y pwyntydd yn amlwg yn mynd i rhaid ei ddiweddaru yn y sefyllfa honno?
Pwyntydd 34 yn dod yn Nid null ond y cyfeiriad y strwythur
yn cynnwys y rhif 35.
Felly dyna achos dau.
Hynny eisoes, rwy'n fath o quantizing faint o waith rhaid i mi ei wneud yma.
>> Ac yn olaf, yr achos canol amlwg yw yn wir, yn y canol, os wyf am
mewnosod rhywbeth fel dweud 23, sy'n mynd rhwng y 23 a'r 26, ond
nawr pethau'n mynd ychydig yn fwy cymryd rhan oherwydd yr hyn
angen newid awgrymiadau?
Felly 22 yn amlwg angen ei newid oherwydd ni all bwyntio at 26 anymore.
Mae angen i dynnu sylw at y nod newydd sy'n Bydd rhaid i mi ddyrannu drwy ffonio
malloc neu ryw cyfwerth.
>> Ond yna yr wyf hefyd angen i nod newydd, 23 yn yr achos hwn, i gael ei pwyntydd
pwyntio at bwy?
26.
Ac mae mynd i fod yn trefn y gweithrediadau yma.
Oherwydd os wyf yn gwneud hyn yn ffôl, ac yr wyf yn er enghraifft, cychwyn ar ddechrau
y rhestr, a fy nod yw gosod 23.
Ac yr wyf yn gwirio, a yw'n perthyn yma, ger naw?
Rhif
A yw'n perthyn yma, y ​​drws nesaf i 17?
Rhif
A yw'n perthyn yma nesaf i 22?
Ydw.
>> Nawr, os ydw i'n ffôl yma, ac nid meddwl hyn drwy, efallai y byddaf
ddyrannu fy nod newydd ar gyfer 23.
Efallai fy mod yn diweddaru'r pwyntydd o y nod a elwir yn 22, pwyntio
hynny ar y nod newydd.
Ac yna beth sy'n rhaid i mi ei ddiweddaru pwyntydd y nod newydd i fod?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Yn union.
Pwyntio at 26.
Ond dammit os nad oeddwn yn diweddaru eisoes Pwyntydd 22 i bwyntio at y boi, a
nawr mae gen i blant amddifad, y gweddill y rhestr, fel petai.
Felly, trefn y gweithrediadau yma yn mynd i fod yn bwysig.
>> I wneud hyn y gallwn ddwyn, dyweder, chwe gwirfoddolwr.
A gadewch i ni weld os na allwn wneud hyn weledol yn hytrach na cod-ddoeth.
Ac mae gennym rai straen hyfryd peli i chi heddiw.
OK, beth am un, dau, yn y yn ôl - ar y diwedd.
tri, pedwar, y ddau ohonoch guys ar y diwedd.
Ac pump, chwech.
Cadarn.
Pump a chwech.
Mae pob hawl a byddwn yn dod i chi guys tro nesaf.
Mae pob hawl, yn dod ar i fyny.
>> Mae pob hawl, gan eich bod hyd yma yn gyntaf, yr hoffech i fod yn un lletchwith
yn Google Gwydr yma?
Mae pob hawl, felly, OK, Gwydr, recordio fideo.
OK, rydych yn dda i fynd.
>> Mae pob hawl, felly os gallwch chi guys ddod draw yma, yr wyf wedi paratoi ymlaen llaw
rhai rhifau.
Mae pob hawl, dewch draw yma.
A pham nad ydych chi'n mynd ychydig ymhellach y ffordd honno.
A gadewch i ni weld, beth yw eich enw, gyda'r Glass Google?
>> MYFYRWYR: Ben.
>> SIARADWR 1: Ben?
OK, Ben, byddwch yn gyntaf, yn llythrennol.
Felly, rydym yn mynd i anfon at ddiwedd y cyfnod.
Mae pob hawl, a bod eich enw?
>> MYFYRWYR: Jason.
>> SIARADWR 1: Jason, OK wnewch chi helpu fod yn rhif naw.
Felly, os ydych am ddilyn Ben y ffordd honno.
>> MYFYRWYR: Jill.
>> SIARADWR 1: Jill, rydych yn mynd i fod yn 17, ac os byddwn i'n gwneud hyn yn fwy
ddeallus, byddai gennyf ddechrau yn y pen arall.
Rydych yn mynd y ffordd honno.
22.
A ydych chi?
>> MYFYRWYR: Mary.
>> SIARADWR 1: Mary, byddwch yn 22.
A yw eich enw?
>> MYFYRWYR: Chris.
>> SIARADWR 1: Chris, byddwch yn 26.
Ac yna yn olaf.
>> MYFYRWYR: Diana.
>> SIARADWR 1: Diana, byddwch yn 34.
Felly, byddwch yn dod ar dros yma.
>> Mae pob hawl, felly berffaith datrys archebu eisoes.
A gadewch i ni fynd yn ei flaen ac yn gwneud hyn fel ein bod yn gallu mewn gwirionedd -
Ben ydych ond yn fath o edrych allan i'r unman yno.
Iawn, felly gadewch i ni fynd yn ei flaen ac yn darlunio hyn ddefnyddio breichiau, yn debyg iawn oeddwn i, yn union,
beth sy'n mynd ymlaen.
Felly, mynd yn ei flaen ac yn rhoi eich hunain a droed neu ddau rhwng eich gilydd.
Ac yn mynd yn ei flaen ac yn pwyntio gydag un llaw i pwy bynnag dylech fod yn pwyntio at
yn seiliedig ar hyn.
Ac os ydych yn null dim ond tynnu sylw yn syth i lawr i'r llawr.
Iawn, felly da.
>> Felly nawr mae gennym restr cysylltiedig, a gadewch i mi cynnig y byddaf yn chwarae rôl y
PTR, felly nid wyf am drafferthu cario o gwmpas hyn.
Ac yna - rhywun confensiwn dwp - gallwch ffonio unrhyw beth rydych am yma -
pwyntydd rhagflaenydd, pwyntydd pred -
dim ond y llysenw roddasom yn ein cod enghreifftiol at fy llaw chwith.
Y llaw arall fod yn mynd i gael eu cadw olrhain pwy yw pwy yn y
dilyn senarios.
>> Felly, mae'n debyg, yn gyntaf, yr wyf am tyn i ffwrdd yr enghraifft gyntaf o mewnosod, yn dweud
20, i mewn i'r rhestr.
Felly, yr wyf i'n mynd i angen rhywun i ymgorffori'r rhif 20 i ni.
Felly mae angen i malloc rhywun rwy'n gan y gynulleidfa.
Dewch ar i fyny.
Beth yw eich enw?
>> MYFYRWYR: Brian.
>> SIARADWR 1: Brian, popeth yn iawn, er mwyn i chi fydd y nod sy'n cynnwys 20.
Mae pob hawl, dewch draw yma.
Ac yn amlwg, lle mae Brian yn perthyn?
Felly, yng nghanol - mewn gwirionedd, arhoswch funud.
Rydym yn gwneud hyn allan o drefn.
Rydym yn gwneud hyn yn llawer anoddach nag y mae angen iddo fod ar y dechrau.
OK, rydym yn mynd i ddim Brian a realloc Brian â phump.
>> Iawn, felly nawr rydym am i fewnosod Brian â phump.
Felly dewch ar dros yma nesaf i Ben am ddim ond ennyd.
A allwch ddweud yn ôl pob tebyg lle y stori hon yn mynd.
Ond gadewch i ni feddwl yn ofalus am trefn y gweithrediadau.
Ac mae'n union hyn yn weledol sy'n mynd i linell i fyny
â'r cod enghreifftiol.
Felly dyma rwyf wedi PTR pwyntio i ddechrau nid ar Ben, fel y cyfryw, ond ar ba bynnag
gwerthfawrogi ei fod yn cynnwys, sydd, yn yr achos hwn yw - beth yw eich enw eto?
>> MYFYRWYR: Jason.
>> SIARADWR 1: Jason, felly mae Ben a minnau yn pwyntio at Jason ar hyn o bryd.
Felly, yn awr mae'n rhaid i mi benderfynu, ble mae Brian yn perthyn?
Felly, yr unig beth yr wyf yn cael mynediad at ar hyn o bryd yw ei n eitem ddata.
Felly, yr wyf i'n mynd i wirio, yn cael ei Brian llai na Jason?
Yr ateb yn wir.
>> Felly beth sydd angen digwydd yn awr, yn y drefn gywir?
Mae angen i mi ddiweddaru faint o arwyddion i gyd yn y stori hon?
Lle mae fy llaw yn dal i bwyntio at Jason, a bod eich llaw - os ydych am
rhowch eich llaw fel, math o, yr wyf yn ddim yn gwybod, marc cwestiwn.
OK, yn dda.
>> Mae pob hawl, felly mae gennych ychydig o ymgeiswyr.
Naill ai Ben neu I neu Brian neu Jason neu bawb arall, a
Mae angen awgrymiadau i newid?
Sawl cyfanswm o?
>> Iawn, felly dau.
Nid yw fy pwyntydd oes ots anymore oherwydd fy mod yn unig dros dro.
Felly mae'n y ddau guys, yn ôl pob tebyg, ddau Ben a Brian.
Felly, gadewch i mi cynnig ein bod yn diweddaru Ben, gan ei fod yn gyntaf.
Yr elfen gyntaf y rhestr yn awr yn mynd i fod Brian.
Felly Ben pwynt Brian.
OK, yn awr beth?
>> Pwy sy'n cael sylw ar bwy?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Iawn felly Brian wedi bwyntio at Jason.
Ond yr wyf wedi colli golwg ar y pwyntydd?
Ydw i'n gwybod ble mae Jason yn?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Yr wyf yn ei wneud, gan fy mod i'n y pwyntydd dros dro.
Ac yn ôl pob tebyg, nid wyf wedi newid bwyntio at y nod newydd.
Felly, gallwn ni gael Brian bwynt ar bwy bynnag Rwy'n bwyntio at.
Ac rydym yn ei wneud.
Felly un achos, gosod yn y ddechrau'r rhestr.
Roedd dau gam allweddol.
Un, mae'n rhaid i ni ddiweddaru Ben, ac yna rydym hefyd wedi diweddaru Brian.
Ac yna nid oes rhaid i mi drafferthu troedio trwy weddill y
rhestr, gan ein bod eisoes o hyd i'w lleoliad, oherwydd ei fod yn perthyn i'r
Gadawodd yr elfen gyntaf.
>> Mae pob hawl, mor bert syml.
Yn wir, yn teimlo fel ein bod bron gwneud hyn yn rhy gymhleth.
Felly, gadewch i ni yn awr dynnaf oddi ar y diwedd y rhestr, a gweld lle
cymhlethdod yn dechrau.
Felly os awr, yr wyf Dyraniad gan y gynulleidfa.
Dylai unrhyw un sydd eisiau chwarae 55?
Mae pob hawl, gwelais eich llaw yn gyntaf.
Dewch ar i fyny.
Yeah.
Beth yw eich enw?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Habata.
OK, yn dod ar i fyny.
Byddwch yn rhif 55.
Felly chi, wrth gwrs, yn perthyn ar ddiwedd y rhestr.
Felly, gadewch i ni ail-chwarae yr efelychiad gyda mi sef y PTR am ddim ond ennyd.
Felly, yr wyf i'n gyntaf yn mynd i bwyntio at beth bynnag Ben sy'n pwyntio at.
Rydym yn ddau pwyntio nawr ar Brian.
Felly 55 heb fod yn llai na phump.
Felly, yr wyf i'n mynd i ddiweddaru fy hun gan pwyntio at pwyntydd nesaf Brian, a oedd
yn awr yw, wrth gwrs, Jason.
55 heb fod yn llai na naw, felly Rydw i'n mynd i ddiweddaru PTR.
Rydw i'n mynd i roi'r wybodaeth ddiweddaraf PTR I'n mynd i ddiweddaru PTR.
Ac yr wyf i'n mynd i - hmm, beth eich enw eto?
>> MYFYRWYR: Diana.
>> SIARADWR 1: Diana yn pwyntio, wrth gwrs, yn null â'i llaw chwith.
Felly, lle mae Habata mewn gwirionedd perthyn yn glir?
I'r chwith, yma.
Felly, sut ydw i'n gwybod i roi ei Yma Rwy'n credu fy mod i wedi sgriwio i fyny.
Oherwydd mae'r hyn sy'n PTR celf hyn o bryd?
NULL.
Felly, hyd yn oed er, yn weledol, gallwn yn amlwg yn gweld pob un o'r rhain
guys yma ar y llwyfan.
Nid wyf wedi cadw golwg ar y flwyddyn flaenorol person yn y rhestr.
Nid oes gennyf bys yn pwyntio allan, yn yr achos hwn, mae nifer nôd 34.
>> Felly, gadewch i ni mewn gwirionedd yn dechrau dros y.
Felly, yn awr yr wyf ei angen mewn gwirionedd ail newidyn lleol.
Ac mae hyn yn yr hyn y byddwch yn ei weld yn y gwirioneddol côd sampl C, lle fel yr wyf yn mynd,
pan fyddaf yn diweddaru fy llaw dde i bwynt Jason, gan adael y tu ôl i Brian, yr wyf yn
well dechrau defnyddio fy llaw chwith i diweddaru lle'r oeddwn, fel bod gan fy mod yn mynd
drwy'r rhestr hon -
yn fwy lletchwith nag yr oeddwn yn bwriadu bellach yma ar eu golwg -
Rydw i'n mynd i gyrraedd y ddiwedd y rhestr.
>> Mae'r llaw yn dal yn null, sydd yn eithaf ddiwerth, ac eithrio i nodi
Rwy'n glir ar ddiwedd y rhestr, ond erbyn hyn o leiaf yr wyf wedi hyn
pwyntydd rhagflaenydd pwyntio yma, felly dwylo yn awr beth a beth sydd angen awgrymiadau
i gael ei diweddaru?
Ei law ydych chi eisiau i ad-drefnu cyntaf?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: OK, felly Diana.
Ble ydych chi eisiau i bwynt Pwyntydd chwith Diana ar?
Yn 55, yn ôl pob tebyg, fel bod rydym wedi gosod yno.
A lle y dylid 55 pwyntydd fynd?
Down, yn cynrychioli null.
Ac yn fy nwylo, ar y pwynt hwn, peidiwch bwysig oherwydd eu bod yn unig oedd
newidynnau dros dro.
Felly, yn awr rydym yn ei wneud.
>> Felly, y cymhlethdod ychwanegol yno - ac nid yw mor galed i weithredu,
ond mae angen newidyn eilaidd i wneud yn siwr bod cyn i mi symud fy hawl
llaw, yr wyf yn diweddaru'r gwerth fy chwith llaw, pwyntydd pred yn yr achos hwn, fel y
fod gennyf pwyntydd trailing i gadw cofnod o ble roeddwn.
Nawr wrth fynd heibio, os ydych yn ystyried hyn drwy, mae hyn yn teimlo fel ei fod yn
ychydig yn blino o gael i gadw golwg ar y llaw chwith.
>> Beth fyddai ateb arall i'r broblem hon wedi bod?
Os ydych yn cael i ailgynllunio'r data strwythur rydym yn sôn
trwy hyn o bryd?
Os yw hyn yn unig fath o teimlo ychydig blino i gael, fel, dau awgrymiadau
mynd drwy'r rhestr, pwy arall a allai wedi, mewn byd delfrydol, a gynhelir
wybodaeth sydd ei hangen ni?
Yeah?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Yn union.
Iawn felly mae mewn gwirionedd yn ddiddorol germ o syniad.
Ac mae syniad hwn o pwyntydd blaenorol, pwyntio at yr elfen blaenorol.
Beth os wyf yn unig ymgorfforodd yr tu mewn i'r rhestr ei hun?
Ac mae'n mynd i fod yn anodd i ddelweddu hyn heb yr holl bapur
syrthio i'r llawr.
Ond mae'n debyg bod y rhain guys yn defnyddio'r ddwy o'u dwylo i gael blaenorol
pwyntydd, a pwyntydd nesaf, a thrwy hynny gweithredu'r hyn y byddwn yn ei alw'n ddwbl
restr cysylltiedig.
Byddai hynny'n caniatáu i mi i ddatrys y rewind, llawer mwy hawdd heb mi, y
rhaglennydd, ar ôl i gadw olrhain â llaw -
wirioneddol llaw -
o ble oeddwn wedi bod o'r blaen yn y rhestr.
Felly, ni fyddwn yn gwneud hynny.
Byddwn yn cadw pethau'n syml oherwydd dyna mynd i ddod am bris, ddwywaith yn
llawer o le ar gyfer y pwyntiau, os ydych chi am gael ail un.
Ond mae hynny'n wir yn gyffredin strwythur data a elwir yn
rhestr gysylltiedig ddwbl.
>> Gadewch i ni wneud yr enghraifft derfynol yma ac yn rhoi guys hyn allan o'u diflastod.
Felly malloc 20.
Dewch ar i fyny o'r eil yno.
Mae pob hawl, beth yw eich enw?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Mae'n ddrwg gennyf?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Demeron?
OK dod ar i fyny.
Rhaid i chi fod yn 20.
Mae'n amlwg eich bod yn mynd i perthyn rhwng 17 a 22.
Felly, gadewch i mi ddysgu fy ngwers.
Dwi'n mynd i ddechrau pwyntydd pwyntio at Brian.
Ac yr wyf i'n mynd i gael fy llaw chwith dim ond diweddaru i Brian fel yr wyf yn symud i
Jason, gwirio yn 20 yn llai na naw?
Rhif
Yn 20 yn llai na 17?
Rhif
Yn 20 yn llai na 22?
Ydw.
Felly mae angen i pa awgrymiadau neu dwylo i newid lle maent yn pwyntio nawr?
>> Felly, gallwn wneud 17 pwyntio at 20.
Felly, mae hynny'n iawn.
Ble ydym ni eisiau i bwynt eich pwyntydd nawr?
Yn 22.
Ac rydym yn gwybod lle 22, unwaith eto diolch i fy pwyntydd dros dro.
Felly, rydym yn iawn yno.
Felly, oherwydd storio dros dro hwn Rwyf wedi cadw golwg ar lle mae pawb yn.
Ac yn awr y gallwch chi fynd ar eu golwg i mewn lle ydych yn perthyn, ac yn awr rydym angen 1, 2, 3,
4, 5, 6, 7, 8, 9 peli straen, a rownd o gymeradwyaeth ar gyfer
guys hyn, os gallem.
Gwneud 'N glws.
>> [Cymeradwyaeth]
>> SIARADWR 1: Pob hawl.
Ac efallai y byddwch yn cadw'r darnau o bapur fel cofroddion.
>> Mae pob hawl, felly, ymddiried ynof mae'n llawer yn haws i gerdded drwy hynny gyda
bobl nag y mae gyda chod gwirioneddol.
Ond yr hyn y byddwch yn dod o hyd yn ychydig funudau'n erbyn hyn, yw bod un fath - oh, diolch yn fawr.
Diolch i chi -
yw y byddwch yn dod o hyd bod yr un data strwythur, rhestr cysylltiedig, gall mewn gwirionedd
yn cael ei ddefnyddio fel bloc adeiladu hyd yn oed yn fwy strwythurau data soffistigedig.
>> Ac yn sylweddoli hefyd y thema yma yw bod rydym wedi cyflwyno gwbl yn fwy
cymhlethdod ati i weithredu o algorithm hwn.
Gosod, ac os ydym yn mynd drwyddi, dileu a chwilio, ychydig
yn fwy cymhleth nag y mae'n ei oedd gydag amrywiaeth.
Ond rydym yn ennill rhywfaint o egni.
Rydym yn cael strwythur data addasol.
>> Ond unwaith eto, rydym yn talu pris o gael rhywfaint o cymhlethdod ychwanegol, yn
weithredu.
Ac rydym yn rhoi'r gorau mynediad ar hap.
Ac i fod yn onest, nid oes rhai 'n glws glân sleid gallaf ei roi i chi
yn dweud dyma pam restr cysylltiedig yn well na arae.
A'i adael ar hynny.
Oherwydd bod y thema ddigwydd eto yn awr, hyd yn oed yn fwy felly yn yr wythnosau nesaf, yn
nad oes o reidrwydd ateb cywir.
>> Dyma pam y mae gennym yr echelin ar wahân o ddylunio ar gyfer setiau broblem.
Bydd yn y cyd-destun sensitif iawn p'un a ydych am ddefnyddio'r data hwn
strwythur neu bod un, a bydd yn yn dibynnu ar yr hyn sy'n bwysig i chi o ran
o adnoddau a chymhlethdod.
>> Ond gadewch i mi yn cynnig bod y data delfrydol strwythur, y greal sanctaidd, yn
rhywbeth sy'n cysonyn amser, waeth faint o bethau yn
y tu mewn iddo, ni fyddai'n wych pe bai strwythur data a ddychwelwyd atebion yn
cysonyn amser.
Ydw.
Mae'r gair yn eich geiriadur enfawr.
Neu ddim, nid yw'r gair hwn yw.
Neu unrhyw broblem o'r fath yno.
Wel, gadewch i ni weld os na allwn o leiaf cymryd cam tuag at hynny.
>> Gadewch i mi yn cynnig strwythur data newydd sy'n Gellir ei ddefnyddio ar gyfer gwahanol bethau,
yn yr achos hwn a elwir tabl hash.
Ac felly rydym yn mewn gwirionedd yn ôl i glancing mewn amrywiaeth, yn yr achos hwn, ac
braidd yn fympwyol, rwyf wedi tynnu hwn tabl hash fel amrywiaeth gyda'r math o
arae dau ddimensiwn -
neu yn hytrach ei fod yn darlunio yma fel dwy amrywiaeth dimensiwn - ond mae hyn yn unig yw
amrywiaeth o faint 26, fel bod os ydym ffoniwch y bwrdd amrywiaeth, braced tabl
sero yn y petryal ar y brig.
Tabl braced 25 yw'r petryal ar y gwaelod.
A dyma sut y gallwn dynnu data strwythur lle rwyf am i storio
bobl enwau.
>> Felly, er enghraifft, ac ni fyddaf yn tynnu'r holl beth yma ar y uwchben, os wyf yn
Roedd amrywiaeth hon, ac yr wyf i'n awr yn mynd i ffoniwch tabl hash, ac mae hyn eto
leoliad sero.
Mae hyn dyma yw lleoliad un, ac yn y blaen.
Yr wyf yn honni fy mod am ddefnyddio'r data hwn strwythur, er mwyn trafod,
i storio enwau pobl, Alice a Bob a Charlie ac enwau eraill o'r fath.
Felly, meddwl am hyn yn awr fel egin o, dyweder, geiriadur
gyda llawer o eiriau.
Maent yn digwydd i fod yn enwau yn ein enghraifft yma.
Ac mae hyn i gyd yn rhy germane, efallai, i gweithredu gwirydd sillafu, wrth i ni
Efallai ar gyfer problem gosod chwech.
>> Felly, os oes gennym amrywiaeth o gyfanswm maint 26 fel bod hwn yn lleoliad 25ain
ar y gwaelod, ac yr wyf yn honni bod Alice yn y gair cyntaf yn y geiriadur o
enwau yr wyf am i fewnosod i mewn i RAM, yn y strwythur data, ble
greddf yn dweud eich bod yn Alice yn Dylai enw fynd amrywiaeth hwn?
>> Mae gennym 26 o opsiynau.
Lle rydym am i roi ei?
Rydym am iddi yn braced sero, dde?
A i Alice, gadewch i ni alw y sero.
A fydd B yn un, ac C yn ddau.
Felly, rydym yn mynd i ysgrifennu Enw Alice i fyny yma.
Os byddwn wedyn yn mewnosod Bob, ei Bydd enw ewch yma.
Bydd Charlie ewch yma.
Ac yn y blaen i lawr drwy y strwythur data.
>> Mae hwn yn strwythur data gwych.
Pam?
Wel beth yw'r amser rhedeg mewnosod enw dynol i mewn i hyn
data strwythur ar hyn o bryd?
O ystyried bod y tabl hwn yn cael ei weithredu, yn wir, fel arae.
Wel, mae'n amser cyson.
Mae'n drefn un.
Pam?
>> Wel sut yr ydych yn penderfynu ar lle mae Alice yn perthyn?
Byddwch yn edrych ar pa lythyren ei enw?
Y cyntaf.
A gallwch gael yno, os yw'n llinyn, at jyst yn edrych ar linyn
braced sero.
Felly, y cymeriad 0 y llinyn.
Mae hynny'n hawdd.
Gwnaethom hynny yn y crypto wythnosau aseiniad yn ôl.
Ac yna unwaith y byddwch yn gwybod bod Alice llythyr CYFALAF A, gallwn dynnu
oddi ar 65 oed neu gyfalaf A ei hun, sy'n rhoi i ni sero.
Felly, rydym yn gwybod bod Alice yn perthyn yn y lleoliad sero.
>> Ac o ystyried pwyntydd i'r data hwn strwythur, o ryw fath, pa mor hir y
ei gymryd i mi ddod o hyd i leoliad sero mewn amrywiaeth?
Dim ond un cam, i'r dde Mae'n amser cyson oherwydd y mynediad ar hap ydym yn
Roedd arfaethedig yn nodwedd o fyrdd.
Felly, yn fyr, figuring allan yr hyn y mae'r mynegai enw Alice yw, sydd, yn
yr achos hwn, yn A, neu adael i ni dim ond datrys hynny i sero, os yw B yn un a C yn
dau, figuring bod allan yw cysonyn amser.
Fi jyst yn rhaid i ni edrych ar ei llythyr cyntaf, figuring gwybod ble sero yn
amrywiaeth yn cysonyn amser hefyd.
Felly dechnegol dyna fel dau gam yn awr.
Ond mae hynny'n dal i fod yn gyson.
Felly, rydym yn galw bod O fawr o un, felly rydym wedi mewnosod Alice yn y tabl hwn yn
cysonyn amser.
>> Ond wrth gwrs, fy mod yn cael naïf yma, dde?
Beth os oes 'na Aaron yn y dosbarth?
Neu Alicia?
Neu unrhyw enwau eraill gan ddechrau gyda A. Os ydym yn mynd i roi
y person hwnnw, dde?
Yr wyf yn golygu, ar hyn o bryd does dim ond tri bobl ar y bwrdd, felly efallai ni
Dylai roi Aaron yn y lleoliad sero un dau tri.
>> Iawn, gallwn roi A yma.
Ond yna, os ydym yn ceisio mewnosod David yn y rhestr hon, ble mae David yn mynd?
Nawr ein system yn dechrau torri i lawr, dde?
Oherwydd erbyn hyn yn dod i ben i fyny David yma os Aaron mewn gwirionedd yma.
Ac felly yn awr, y cyfan syniad o gael strwythur data glân sy'n rhoi i ni
mewnosodiadau cysonyn amser bellach yn cysonyn amser, gan fod rhaid i mi
gwirio, oh, Damnit, rhywun yn barod yn y lleoliad Alice.
>> Gadewch i mi ymchwilio i weddill y data hwn strwythur, yn chwilio am fan a'r lle i roi
rhywun fel enw Aaron.
Ac felly hynny hefyd yn dechrau i gymryd amser llinol.
Ar ben hynny, os ydych yn awr am ddod o hyd i'r Aaron yn y strwythur data, a'ch bod yn
gwirio, ac nid enw Aaron yma.
Yn ddelfrydol, byddech yn dweud Aaron nid yn y strwythur data.
Ond os ydych chi'n dechrau gwneud lle i Aaron lle y dylai fod wedi bod yn D
neu E, gallwch chi, achos gwaethaf, mae'n rhaid i wirio y strwythur data cyfan, yn
ac os felly ei bod yn datganoli i fod yn rhywbeth llinellol ym maint y tabl.
>> Felly, iawn, 'n annhymerus' atgyweiria hon.
Y broblem yma yw fy mod wedi 26 elfen yn y casgliad hwn.
Gadewch i mi ei newid.
Wps.
Gadewch i mi newid fel bod yn hytrach lles maint 26 i gyd, yn sylwi ar y gwaelod
mynegai yn mynd i newid i n minws 1.
Os yw 26 yn amlwg yn rhy fach ar gyfer pobl ' enwau, oherwydd mae miloedd o
enwau'r byd, gadewch i ni dim ond gwneud mewn 100 neu 1,000 neu 10,000.
Gadewch i 'jyst dyrannu llawer mwy o le.
>> Wel, nid yw hynny o reidrwydd yn gostwng y tebygolrwydd na fydd gennym ddwy
pobl ag enwau gan ddechrau gyda A, a felly, yr ydych yn mynd i geisio rhoi A
enwau ar sero lleoliad hyd.
Maent yn dal i fynd i wrthdaro, a golygu ein bod yn dal angen ateb i roi
Alice ac Aaron a Alicia ac eraill enwau gan ddechrau gyda A mewn mannau eraill.
Ond faint o broblem yw hyn?
Beth yw'r tebygolrwydd y bydd eich cael gwrthdrawiadau mewn data
strwythur fel hyn?
>> Wel, gadewch i mi - byddwn yn dod yn ôl i'r cwestiwn yma.
Ac edrych ar sut y gallem datrys yn gyntaf.
Gadewch i mi dynnu i fyny y cynnig hwn yma.
Yr hyn yr ydym newydd ei ddisgrifio yn algorithm, a hewristig enw llinellol
treiddgar sy'n golygu, os ydych yn ceisio rhoi'r rhywbeth yma yn y data hwn
strwythur, a elwir tabl hash, ac nad oes lle yno, byddwch
wirioneddol ymchwilio i'r strwythur data gwirio, a yw hyn ar gael?
A yw hyn ar gael yw hyn ar gael?
A yw hyn ar gael?
A phan yn olaf yw, eich mewnosoder y enwi eich bod fwriadwyd yn wreiddiol
mewn mannau eraill yn y lleoliad hwnnw.
Ond yn yr achos gwaethaf, yr unig fan a'r lle a allai fod yn y waelod y data
strwythur, y diwedd y rhesi.
>> Felly llinol stilio, yn yr achos gwaethaf, yn datganoli i mewn i algorithm llinol lle
Aaron, os yw'n digwydd i gael eu mewnosod ddiwethaf yn y strwythur data, fe allai
gwrthdaro â'r lleoliad cyntaf, ond wedyn ben erbyn anlwc ar ddiwedd.
Felly, nid yw hyn yn gyson greal sanctaidd o amser i ni.
Mae'r dull hwn o elfennau mewnosod i mewn i strwythur data a elwir yn hash
Nid yw'n ymddangos bod y tabl yn cysonyn amser o leiaf nid yn yr achos cyffredinol.
Gall ddatganoli i fod yn rhywbeth llinol.
>> Felly beth os ydym yn datrys gwrthdrawiadau ychydig yn wahanol?
Felly dyma fwy soffistigedig tuag at yr hyn sy'n dal i fod
a elwir yn tabl hash.
A thrwy hash, wrth fynd heibio, yr hyn Yr wyf yn golygu y mynegai a
Cyfeiriais ato yn gynharach.
Gall I hash rhywbeth yn ystyried fel berf.
>> Felly, os ydych hash Alice 'na enw, swyddogaeth hash, fel petai,
Dylid dychwelyd rhif.
Yn yr achos hwn yn sero os yw'n perthyn yn Lleoliad sero, un os y mae yn perthyn yn
leoliad yn un, ac yn y blaen.
Felly, fy swyddogaeth hash hyd yn hyn wedi bod yn super syml, dim ond yn edrych ar y
llythyren gyntaf yn enw'r rhywun.
Ond mae swyddogaeth hash yn cymryd fel mewnbwn rhyw darn o ddata, a
llinyn, yn int, beth bynnag.
Ac mae'n poeri allan fel arfer yn rhif.
Ac mae'r nifer yn lle bod data elfen yn perthyn mewn strwythur data
a elwir yma fel tabl hash.
>> Felly, dim ond yn reddfol, mae hwn yn cyd-destun ychydig yn wahanol.
Mae hyn mewn gwirionedd yn cyfeirio at enghraifft cynnwys penblwyddi, lle
gallai fod cymaint â 31 diwrnod yn y mis.
Ond beth oedd y person hwn benderfynu ei wneud mewn achos o wrthdrawiad?
Cyd-destun yn awr, ac nid yn gwrthdrawiad o enwau, ond mae gwrthdrawiad pen-blwydd,
os oes dau o bobl yr un pen-blwydd ar y 2 Hydref, er enghraifft.
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Yeah, felly dyma ni wedi y leveraging rhestrau cysylltiedig.
Felly, mae'n edrych ychydig yn wahanol nag i ni dynnu yn gynharach.
Ond mae'n ymddangos ein bod yn rhaid i arae ar yr ochr chwith.
Dyna un mynegai, nid ar gyfer unrhyw rheswm penodol.
Ond mae'n dal i fod yn arae.
Mae'n amrywiaeth o awgrymiadau.
A phob un o'r elfennau hynny, pob un y cylchoedd neu slaes - y slaes
cynrychioli null - pob un o'r rhain awgrymiadau yn ymddangos yn pwyntio i
pa strwythur data?
Mae rhestr cysylltiedig.
>> Felly, erbyn hyn mae gennym y gallu i cod caled yn ein rhaglen
maint y tabl.
Yn yr achos hwn, rydym yn gwybod bod hi byth mwy na 31 diwrnod mewn mis.
Mor galed codio gwerth fel 31 yn rhesymol yn y cyd-destun.
Yng nghyd-destun enwau, caled codio 26 nid yw'n afresymol yw'n bobl
enwau ond yn dechrau gydag, er enghraifft, yr wyddor yn ymwneud A drwy Z.
>> Gall Rydym yn gwthio i gyd i mewn i'r data strwythur ar yr amod, pan fyddwn yn cael
gwrthdrawiad, nid ydym yn rhoi'r enwau yma, rydym yn hytrach na meddwl am y celloedd hyn
nid fel llinynnau eu hunain, ond fel y awgrymiadau, er enghraifft, Alice.
Ac yna gall Alice gael pwyntydd arall i enw arall gan ddechrau gyda
A. Ac Bob mewn gwirionedd yn mynd dros yma.
>> Ac os oes enw arall dechrau gyda B, ei fod yn dod i ben i fyny dros yma.
Ac felly mae pob un o'r elfennau hyn tabl dau, os rydym yn cynllunio hyn a
ychydig yn fwy deallus -
yn dod ar -
os ydym yn cynllunio hyn ychydig yn fwy gelfydd, yn awr yn dod yn ddata addasol
strwythur, lle nid oes terfyn caled ar faint o elfennau gallwch osod
i mewn iddo oherwydd os oes gennych gwrthdrawiad, mae hynny'n iawn.
Dim ond mynd yn ei flaen ac yn ei atodi i yr hyn a welsom ychydig yn ôl oedd
a elwir yn restr cysylltiedig.
>> Wel, gadewch i ni oedi am ychydig funud.
Beth yw'r tebygolrwydd o gwrthdrawiad yn y lle cyntaf?
Iawn, efallai fy mod yn meddwl dros, efallai Rydw i wrth fy peirianneg broblem hon,
oherwydd eich bod yn gwybod beth?
Oes, gallaf ddod o hyd mympwyol enghreifftiau oddi ar ben fy mhen fel
Allison ac Aaron, ond mewn gwirionedd, o ystyried dosbarthiad unffurf o
mewnbynnau, hynny yw rhai mewnosodiadau ar hap i mewn i strwythur data, beth mewn gwirionedd yw
y tebygolrwydd o gwrthdrawiad?
Wel yn troi allan, mae'n mewn gwirionedd yn super uchel.
Gadewch i mi cyffredinoli hyn problem fel hyn.
>> Felly, mewn ystafell o n CS50 fyfyrwyr, beth y tebygolrwydd bod o leiaf
dau fyfyriwr yn yr ystafell cael yr un pen-blwydd?
Felly mae beth. ychydig o hund -
200, 300 o bobl yma a nifer o cant o bobl yn y cartref heddiw.
Felly, os ydych yn awyddus i ofyn i ni'n hunain beth sydd y tebygolrwydd o ddau o bobl
yn yr ystafell hon yn cael yr un pen-blwydd, gallwn ffigur hyn.
Ac yr wyf yn gwneud cais mewn gwirionedd mae dau bobl sydd â'r un pen-blwydd.
>> Er enghraifft, a oes unrhyw un wedi pen-blwydd heddiw?
Ddoe?
Yfory?
Mae pob hawl, felly mae'n teimlo fel mod i'n mynd i gael i wneud hyn 363, neu fel bod mwy
amser i mewn gwirionedd yn chyfrif i maes os oes gennych gwrthdrawiad.
Neu gallem dim ond gwneud hyn yn fathemategol yn hytrach na tediously
wneud hyn.
Ac yn cynnig y canlynol.
>> Felly, yr wyf yn cynnig y gallem fodelu'r tebygolrwydd o ddau o bobl gael y
un pen-blwydd fel y tebygolrwydd o 1 minws y tebygolrwydd o unrhyw un â
yr un pen-blwydd.
Felly, i gael hyn, ac mae hyn yn dim ond y ffordd ffansi o ysgrifennu hwn, er y
person cyntaf yn yr ystafell, bydd ef neu hi Gall unrhyw un o'r posibl
pen-blwydd gan dybio 365 diwrnod yn y flwyddyn, gydag ymddiheuriadau i bobl ag
pen-blwydd 29 Chwefror.
>> Felly, y person cyntaf yn yr ystafell hon yn rhad ac am ddim i gael unrhyw nifer o pen-blwydd
allan o'r posibiliadau 365 fel bod byddwn yn gwneud hynny 365 wedi'i rannu â 365,
sy'n un.
Mae'r person nesaf yn yr ystafell, os yw'r nod yw osgoi gwrthdrawiad, dim ond
yn cael ei ben-blwydd ar sut llawer o wahanol ddyddiau posibl?
364.
Felly, yr ail dymor yn ymadrodd hwn yn hanfod wneud hynny cwestiwn i ni
trwy dynnu oddi ar un diwrnod posibl.
Ac yna y diwrnod nesaf, y diwrnod nesaf, y diwrnod nesaf i lawr at gyfanswm nifer
o bobl yn yr ystafell.
>> Ac os ydym yn ystyried, beth felly yw y tebygolrwydd nid pawb yn cael
pen-blwydd unigryw, ond unwaith eto 1 llai hynny, yr hyn a gawn yn fynegiant
y gall fancifully iawn edrych fel hyn.
Ond mae'n fwy diddorol i edrych ar eu golwg.
Mae hwn yn siart lle ar yr echelin-x yn y nifer o bobl yn yr ystafell, y
nifer y pen-blwydd.
Ar y y-echelin yw'r tebygolrwydd o wrthdrawiad, dau o bobl
cael yr un pen-blwydd.
>> Ac mae'r prydau parod o'r gromlin hon yn cyn gynted ag y byddwch yn dod i hoffi 40
fyfyrwyr, rydych yn i fyny at 90% o debygolrwydd combinatorically o ddau
bobl neu fwy yn cael yr un pen-blwydd.
Ac ar ôl i chi ddod i hoffi 58 o bobl ei fod yn bron i 100% o gyfle y ddwy
bobl yn yr ystafell yn mynd i gael y un pen-blwydd, er bod yna
365 neu 366 bwcedi posibl, a dim ond 58 o bobl yn yr ystafell.
Dim ond ystadegol rydych yn debygol o cael gwrthdrawiadau, sydd yn fyr
cymell y drafodaeth hon.
Hyd yn oed os ydym yn cael ffansi yma, ac dechrau cael cadwyni hyn, rydym yn dal i
mynd i gael gwrthdrawiadau.
>> Felly mae hynny'n codi'r cwestiwn, beth yw'r gost o wneud fewnosodiadau a dileadau
i mewn i strwythur data fel hyn?
Wel gadewch i mi gynnig -
a gadewch i mi fynd yn ôl i'r sgrin dros yma - os ydym wedi n elfennau yn y
rhestr, felly os ydym yn ceisio ei fewnosod n elfennau, ac mae gennym
faint o gyfanswm bwcedi?
Gadewch i ni ddweud 31 gyfanswm bwcedi yn achos pen-blwydd.
Beth sydd hyd uchafswm o o gadwyni hyn yn bosibl?
>> Os unwaith eto mae 31 posibl pen-blwydd mewn mis a roddir.
Ac rydym yn unig clumping pawb -
mewn gwirionedd mae hynny'n enghraifft dwp.
Gadewch i ni wneud 26 yn lle hynny.
Felly, os mewn gwirionedd yn rhaid i bobl y mae eu henwau dechrau gyda A drwy Z, gan roi
ni 26 o bosibiliadau.
Ac rydym yn defnyddio strwythur data fel yr un yr ydym jyst yn gweld, lle yr ydym wedi
amrywiaeth o awgrymiadau, pob un ohonynt yn cyfeirio at restr cysylltiedig lle y
rhestr cyntaf yw pawb gydag enw Alice.
Mae'r ail restr yn bob â'r enwi gan ddechrau gyda A, gan ddechrau
gyda B, ac yn y blaen.
>> Beth sydd hyd tebygol pob un o'r rhestrau hynny os ydym yn tybio amgylchedd glân 'n glws
dosbarthu enwau A drwy Z ar draws y strwythur data cyfan?
Mae pobl n yn y strwythur data wedi'i rannu â 26, os ydynt yn 'n glws
gwasgaru dros y cyfan strwythur data.
Felly, hyd pob un o'r rhain cadwyni yn n rannu â 26.
Ond yn O mawr nodiant, beth yw hynny?
Beth yw hynny mewn gwirionedd?
Felly mae'n wirioneddol dim ond n, dde?
Oherwydd ein bod wedi dweud yn y gorffennol, bod Ych chi rannu â 26.
Ie, mewn gwirionedd yn gyflymach.
Ond mewn egwyddor, nid yw'n sylfaenol i gyd yn gyflymach.
>> Felly, nid yw'n ymddangos i ni fod yr holl bod llawer yn agosach at y greal sanctaidd.
Mewn gwirionedd, mae hyn yn unig yw amser llinol.
Heck, ar y pwynt hwn, pam nad ydym dim ond yn defnyddio un rhestr cysylltiedig enfawr?
Pam nad ydym yn unig yn defnyddio un enfawr amrywiaeth i storio enwau
pawb yn yr ystafell?
Wel, a oes rhywbeth o hyd grymus am dabl hash?
A oes yn dal rhywbeth cymhellol am strwythur data
sy'n edrych fel hyn?
Hwn.
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Iawn, ac eto os mai dim ond algorithm amser llinol, ac mae
strwythur data amser llinol, pam nad ydw i'n dim ond storio enw pawb mewn mawr
amrywiaeth, neu mewn rhestr cysylltiedig mawr?
Ac yn rhoi'r gorau i wneud CS mor llawer anoddach nag y mae angen iddo fod?
Beth yn rymus am hyn, hyd yn oed er fy mod yn crafu allan?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Nid yw mewnosodiadau chi?
Drud anymore.
Felly mewnosodiadau bosibl y gallai dal i o amser yn gyson, hyd yn oed os yw eich data
strwythur yn edrych fel hyn, mae amrywiaeth o awgrymiadau, pob un ohonynt yn pwyntio at
potensial i fod yn rhestr gysylltiedig.
Sut y gallech ei chyrraedd yn gyson amser gosod enwau?
Lynu yn y blaen, dde?
>> Os byddwn yn aberthu nod dylunio o yn gynharach, lle rydym yn awyddus i gadw
enw pawb, er enghraifft, didoli, neu bob un o'r rhifau ar y llwyfan didoli,
Mae'n debyg bod gennym restr cysylltiedig heb eu didoli.
Dim ond yn costio i ni yn un neu ddau gam, fel yn achos Ben a Brian
yn gynharach, i fewnosod elfen yn ddechrau'r rhestr.
Felly, os nad ydym yn poeni am ddatrys yr holl o enwau gan ddechrau gyda A neu bob
yr enwau gan ddechrau gyda B, gallwn yn dal i cyflawni osod cysonyn amser.
Awr yn edrych i fyny Alice neu Bob neu unrhyw enw yn fwy cyffredinol yn dal i beth?
Mae'n fawr O n rannu gan 26, yn y achos delfrydol lle mae pawb yn unffurf
dosbarthu, lle mae cymaint o A gan fod Z, ac mae'n debyg mai
afrealistig.
Ond mae hynny'n dal i fod yn llinol.
>> Ond yma, rydym yn dod yn ôl at y pwynt o nodiant asymptotic yn
ddamcaniaethol wir.
Ond yn y byd go iawn, os wyf yn honni bod Gall fy rhaglen wneud rhywbeth 26 gwaith
gyflymach na chi, y mae eu rhaglen ydych chi'n mynd i well defnyddio?
Chi neu fy un i, a yw 26 gwaith yn gyflymach?
Yn realistig, bydd y person y mae ei 26 gwaith yn gyflymach, hyd yn oed os ddamcaniaethol
ein algorithmau yn rhedeg yn yr un asymptotic amser yn rhedeg.
>> Gadewch i mi yn cynnig gwahanol ateb yn gyfan gwbl.
Ac os nad yw hyn yn chwythu eich meddwl, rydym yn allan o strwythurau data.
Felly mae hyn yn ei fod yn trie -
math o enw dwp.
Mae'n dod o adalwadau, a'r gair ei sillafu trie, t-r-i-e, oherwydd
adalw cwrs yn swnio fel trie.
Ond dyna hanes y gair trie.
>> Felly trie yn wir rhyw fath o goeden, ac mae hefyd yn chwarae ar y gair hwnnw.
A hyd yn oed er na allwch ei weld yn eithaf gyda delweddu hon, mae trie yn
coeden strwythuro, fel coeden teulu gyda un hynafiad ar y brig a llawer
o wyrion ac wyrion mawr fel yn gadael ar y gwaelod.
Ond mae pob nod mewn trie yn arae.
Ac mae'n mewn amrywiaeth - a gadewch i gorsymleiddio'r am eiliad - ei fod yn
amrywiaeth, yn yr achos hwn, o faint 26, lle bob nod unwaith eto mae amrywiaeth o faint
26, lle mae'r elfen 0 yn y amrywiaeth cynrychioli A, a'r olaf
ym mhob elfen o'r fath amrywiaeth cynrychioli Z.
>> Felly, yr wyf yn cynnig, felly, bod y data hwn Gall strwythur, a elwir yn trie, yn
defnyddio hefyd i storio geiriau.
Gwelsom funud yn ôl sut y gallem storio geiriau, neu yn yr enwau achos hwn, ac rydym yn
welsom yn gynharach sut y gallwn storio rhifau, ond os ydym yn canolbwyntio ar enwau neu linynnau
yma, yn sylwi ar yr hyn sy'n ddiddorol.
Yr wyf yn honni bod yr enw Maxwell yw tu mewn y strwythur data.
Lle ydych chi'n gweld Maxwell?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Ar y chwith.
Felly, yr hyn sy'n ddiddorol gyda data hwn strwythur yn hytrach na siop y
llinyn M-A-X-W-E-L-L slaes sero, pob contiguously, yr hyn yr ydych yn ei wneud yn lle hynny
yn dilyn.
Os yw hyn yn trie fel strwythur data, mae pob un o'i nodau yw eto arae,
ac rydych am i storio Maxwell, i chi yn gyntaf mynegai ac felly nod y gwraidd, fel
i siarad, y nod topmost, yn y lleoliad M, ar y dde, felly
fras yn y canol.
Ac yna oddi yno, byddwch yn dilyn pwyntydd i blentyn nodau, fel petai.
Felly, yn yr ystyr coeden deulu, ei ddilyn i lawr.
Ac mae hynny'n eich arwain at nod arall ar y chwith yno, sydd yn
dim ond amrywiaeth arall.
>> Ac yna os ydych am storio Maxwell, ddod o hyd i'r pwyntydd sy'n cynrychioli
A, sydd yn yr un yma yma.
Yna byddwch yn mynd at y nod nesaf.
A rhybudd - dyma pam y darlun yn ychydig yn twyllo -
nod hwn yn edrych super bach.
Ond i'r dde o hyn yw Y a Z. Mai dim ond yr awdur wedi cwtogi y
llun er mwyn i chi mewn gwirionedd yn gweld pethau.
Fel arall y llun byddai'n hynod o eang.
Felly, yn awr yr ydych mynegai i mewn i leoliad X, yna W, Yna E, yna i'r Ch, yna L. Yna beth sydd
chwilfrydedd hwn?
>> Wel, os ydym yn defnyddio y math hwn o newydd cymryd ar sut i storio llinyn mewn
strwythur data, mae angen i chi yn dal i hanfod gwirio i ffwrdd yn y data
strwythur y gair yn dod i ben yma.
Mewn geiriau eraill, pob un o'r nodau hyn rhywsut wedi i gofio ein bod yn
dilyn mewn gwirionedd yr holl awgrymiadau hyn ac yn gadael ychydig
bara briwsion ar waelod yma o hyn strwythur i ddangos M-A-X-W-E-L-L yn
yn wir yn y strwythur data.
>> Felly, efallai y byddwn yn gwneud hyn fel a ganlyn.
Mae pob un o'r nodau yn y llun rydym yn unig gwelodd un, amrywiaeth o faint 27.
Ac mae'n awr yn 27, oherwydd yn p gosod chwech, byddwn mewn gwirionedd yn rhoi collnod i chi,
er mwyn i ni gael enwau fel O'Reilly ac eraill sydd â collnod.
Ond mae un syniad.
Mae pob un o'r elfennau hynny yn y pwyntiau amrywiaeth i strwythur
nod, felly dim ond nod.
Felly, mae hyn yn ein hatgoffa iawn o'n rhestr gysylltiedig.
>> Ac yna mae gen i Boole, a byddaf ffoniwch gair, sydd yn unig yn mynd i fod yn
yn wir os yw gair yn dod i ben ar hyn o nod yn y goeden.
Mae'n effeithiol cynrychioli'r bach triongl gwelsom funud yn ôl.
Felly, os yw gair yn dod i ben ar y nod yn y coed, bydd y gair hwnnw maes fod yn wir,
sydd yn gysyniadol gwirio i ffwrdd, neu rydym yn tynnu triongl hwn, ie yno
yn air yma.
>> Felly, mae hwn yn trie.
Ac yn awr y cwestiwn yw, beth yn ei rhedeg amser?
A yw'n fawr o O n?
A yw'n rhywbeth arall?
Wel, os ydych wedi n enwau yn y data hwn strwythur, Maxwell yn un o
iddynt, beth yw'r amser rhedeg mewnosod neu ddod o hyd Maxwell?
Beth yw'r amser yn rhedeg o mewnosod Maxwell?
Os oes n enwau eraill eisoes yn y tabl?
Yeah?
>> MYFYRIWR: [Anghlywadwy].
>> SIARADWR 1: Yeah, 'i' hyd yr enw, dde?
Felly M-a-x-w-e-l-l felly mae'n teimlo fel hyn algorithm yn fawr O o saith.
Yn awr, wrth gwrs, yr enw yn amrywio o ran hyd.
Efallai ei fod yn enw byr.
Efallai ei fod yn enw hirach.
Ond yr hyn sy'n allweddol yma yw bod mae'n nifer cyson.
Ac efallai nid yw'n wir yn gyson, ond duw, os realistig, mewn
geiriadur, mae debyg bod rhai terfyn ar y nifer o lythyrau mewn
enw'r person hwnnw mewn gwlad benodol.
>> Ac felly gallwn gymryd yn ganiataol y gwerth yn gyson.
Nid wyf yn gwybod beth ydyw.
Mae'n debyg yn fwy na'r rydym yn meddwl ei fod yn.
Oherwydd bod bob amser yn rhyw gornel achos gydag enw hir crazy.
Felly, gadewch i ni ei alw'n k, ond mae'n dal i fod yn gyson yn ôl pob tebyg, oherwydd y mae pob
enwi yn y byd, o leiaf mewn gwlad arbennig, yw bod hyd neu
byrrach, felly mae'n gyson.
Ond pan fyddwn wedi dweud rhywbeth yn fawr O o werth cyson, beth sy'n bod
sy'n cyfateb mewn gwirionedd i?
Mae hynny'n wir yr un peth yn dweud cysonyn amser.
>> Nawr rydym yn fath o dwyllo, dde?
Rydym yn fath o ddylanwad rhywfaint o theori yma i ddweud bod trefn k yn dda, yn
mewn gwirionedd ond yn archebu o un, ac mae'n amser cyson.
Ond mae mewn gwirionedd.
Oherwydd bod y mewnwelediad allweddol yma yw bod os ydym wedi n enwau eisoes yn hyn o
strwythur data, ac yr ydym mewnosoder Maxwell, yw faint o amser mae'n ei gymryd i ni
mewnosoder Maxwell o gwbl yr effeithir arnynt gan faint o bobl eraill
yn y strwythur data?
Nid yw'n ymddangos i fod.
Os bu'n rhaid i mi yn fwy o biliwn elfen i hyn trie, ac yna rhowch Maxwell, yn cael ei
ef yn mhob heffeithio?
Rhif
A dyna wahanol i unrhyw o'r data diwrnod strwythurau rydym wedi gweld hyd yn hyn, lle
yr amser yn rhedeg eich algorithm yn gwbl annibynnol ar faint o
pethau ai peidio eisoes yn y strwythur data.
>> Ac felly gyda hyn yn ei roi i chi yn awr yn cyfle i p set chwech, a fydd yn
unwaith eto yn golygu gweithredu eich hun gwiriwr sillafu, darllen yn 150,000
geiriau, y ffordd orau i storio'r Nid yw o reidrwydd yn amlwg.
Ac er fy mod i wedi dyheu am ddod o hyd i y greal sanctaidd, nid wyf yn
honni bod trie yn.
Yn wir, efallai y tabl hash yn dda iawn yn profi i fod yn llawer mwy effeithlon.
Ond y rhai yn unig -
mai dim ond un o'r penderfyniadau dylunio bydd yn rhaid i chi ei wneud.
>> Ond yn cau gadewch i ni gymryd 50 neu lai eiliad i gymryd cipolwg ar yr hyn sydd
blaen yr wythnos nesaf a thu hwnt yn pontio o'r llinell orchymyn
os yw rhaglenni byd C i bethau ar y we yn seiliedig ac ieithoedd fel PHP a
JavaScript a'r rhyngrwyd ei hun, protocolau fel HTTP, a ydych wedi
gymryd yn ganiataol ar gyfer y blynyddoedd nawr, ac yn y rhan fwyaf o teipio pob
dydd, efallai, neu weld.
A byddwn yn dechrau croen yn ôl y haenau o'r hyn sydd ar y rhyngrwyd.
A beth yw'r cod y wrth wraidd offer heddiw.
Felly, 50 eiliad o ymlid hwn yma.
Rwy'n rhoi Warriors o'r Net i chi.
>> [VIDEO Playback]
>> -Daeth gyda neges.
Gyda protocol ei holl hun.
Daeth i fyd o waliau tân creulon, llwybryddion di-hid, a pheryglon yn hyn
yn waeth na marwolaeth.
Mae'n gyflym.
Mae'n gryf.
Mae'n TCPIP.
Ac mae wedi cael eich cyfeiriad.
Rhyfelwyr y Net.
>> [VIDEO END Playback]
>> SIARADWR 1: Dyna sut y rhyngrwyd Bydd gweithio fel yr wythnos nesaf.