>> JASON Hirschhorn: Croeso i bawb i'r Adran Saith.
Yr ydym mewn wythnos saith o'r cwrs.
Ac mae hyn Dydd Iau sydd ar y gweill yw Calan Gaeaf felly rwy'n
gwisgo i fyny fel pwmpen.
Nid oeddwn yn gallu plygu drosodd a'i roi ar fy esgidiau, felly dyna pam yr wyf i'n
dim ond yn gwisgo sanau.
Hefyd yn Dydw i ddim yn gwisgo unrhyw beth o dan hwn, felly ni allaf gymryd i ffwrdd os yw'n
tynnu sylw i chi.
Rwy'n ymddiheuro ymlaen llaw am hynny.
Nid oes angen i chi ddychmygu beth sy'n mynd ymlaen.
Rydw i'n gwisgo bocswyr.
Felly mae'n cyfan yn dda.
>> Mae gen i stori hwy am pam yr wyf i'n gwisgo fel pwmpen, ond dw i'n mynd i
ac eithrio bod ar gyfer yn ddiweddarach yn yr adran hon oherwydd fy mod yn dymuno i ddechrau arni.
Mae gennym lawer o bethau cyffrous i fynd dros yr wythnos hon.
Mae'r rhan fwyaf ohonynt yn ymwneud yn uniongyrchol â hyn problem set wythnos, camsillafiadau.
Rydym yn mynd i fod yn mynd dros cysylltu rhestrau a thablau hash
ar gyfer yr adran gyfan.
Yr wyf yn rhoi rhestr hon bob wythnos, rhestr o adnoddau ar eich cyfer i'ch helpu gyda
y deunydd ar y cwrs hwn.
Os ar golled, neu os yn chwilio am rai rhagor o wybodaeth, ewch i un o
adnoddau hyn.
>> Unwaith eto, pset6 yn camsillafiadau, pset yr wythnos hon.
Ac mae hefyd yn eich annog, ac yr wyf yn eich annog, i ddefnyddio rhai eraill
adnoddau yn benodol ar gyfer pset hwn.
Yn benodol, mae'r tri rydw i wedi a restrir ar y sgrîn -
gdb, yr ydym wedi bod yn gyfarwydd â a bod yn ei ddefnyddio am sbel nawr, yn
mynd i fod yn ddefnyddiol iawn yr wythnos hon.
Felly, yr wyf yn rhoi bod hyd yma.
Ond pryd bynnag y byddwch yn gweithio gyda C, dylech bob amser fod yn defnyddio gdb i
dadfygio eich rhaglenni.
Yr wythnos hon hefyd valgrind.
A oes unrhyw un yn gwybod beth valgrind ei wneud?
>> GYNULLEIDFA: Mae'n gwirio am ollyngiadau cof?
>> JASON Hirschhorn: Valgrind gwiriadau am ollyngiadau cof.
Felly, os ydych rhywbeth malloc yn eich rhaglen, rydych yn gofyn am cof.
Ar ddiwedd eich rhaglen, mae gennych i ysgrifennu am ddim ar bopeth ydych wedi
malloced i roi'r cof yn ôl.
Os na fyddwch yn ysgrifennu am ddim yn y diwedd a eich rhaglen yn dod i ben,
popeth yn awtomatig gael ei ryddhau.
Ac ar gyfer rhaglenni bach, mae'n nad yw fawr bargen.
Ond os ydych chi'n ysgrifennu rhedeg hirach rhaglen nad yw'n rhoi'r gorau iddi,
o reidrwydd, mewn ychydig o funudau neu cwpl o eiliadau, yna cof gollwng
Gall fod yn fargen enfawr.
>> Felly, ar gyfer pset6, y disgwyliad yw y bydd gennych sero gollwng cof gyda
eich rhaglen.
I wirio am ollyngiadau cof, valgrind rhedeg a bydd yn rhoi i chi rai 'n glws
allbwn rhoi gwybod i chi a oes neu nid yw popeth yn rhad ac am ddim.
Byddwn yn ymarfer ag ef yn ddiweddarach heddiw, gobeithio.
>> Yn olaf, y gorchymyn diff.
Rydych yn defnyddio rhywbeth tebyg iddo yn pset5 gyda'r offeryn peek.
Caniateir i chi i edrych y tu mewn.
Rydych hefyd yn defnyddio diff, hefyd, fesul y broblem a osodwyd fanyleb.
Ond yn gadael i chi gymharu dwy ffeil.
Gallech gymharu'r ffeil didfap a penawdau gwybodaeth o ateb staff a
eich ateb yn pset5 os dewis i chi ei ddefnyddio.
Bydd Diff yn eich galluogi i wneud hynny, hefyd.
Gallwch gymharu yr ateb cywir ar gyfer problem yr wythnos hon yn gosod ar eich ateb
a gweld os yw'n llinellau i fyny neu i weld Lle mae gwallau yn cael eu.
>> Felly, y rhai tri offer da sy'n Dylid ei ddefnyddio ar gyfer yr wythnos hon, a
yn bendant yn edrych ar eich rhaglen â'r tri offer
cyn ei droi i mewn
Unwaith eto, fel yr wyf wedi crybwyll bob wythnos, os oes gennych unrhyw adborth i mi - yn
cadarnhaol ac adeiladol -
croeso i fod yn bennaeth ar y wefan ar waelod y sleid hon
a mewnbwn yno.
Fi 'n sylweddol yn gwerthfawrogi unrhyw a phob adborth.
Ac os byddwch yn rhoi pethau penodol mi fod Gallaf ei wneud i wella neu fy mod yn
gwneud yn dda y byddech yn hoffi i mi yn parhau, yr wyf yn cymryd hynny o ddifrif ac
wir yn ymdrechu'n galed i wrando at eich adborth.
Ni allaf addo fy mod i'n mynd i wneud popeth, fodd bynnag, fel gwisgo
pwmpen gwisg bob wythnos.
>> Felly, rydym yn mynd i dreulio y rhan fwyaf o'r adran hon, fel y soniais, yn siarad am
rhestrau cysylltiedig a thablau hash, a oedd yn Bydd yn uniongyrchol berthnasol i'r
broblem a osodwyd yr wythnos hon.
Rhestrau cysylltiedig byddwn yn mynd dros gymharol yn gyflym oherwydd ein bod wedi treulio cryn dipyn
o amser yn mynd dros yn adran.
Ac felly byddwn yn mynd yn syth i mewn i'r codio problemau ar gyfer rhestrau cysylltiedig.
Ac yna ar y diwedd byddwn yn siarad am hash tablau a sut maent yn berthnasol i hyn
problem yr wythnos yn gosod.
>> Rydych chi wedi gweld y cod hwn o'r blaen.
Mae hwn yn strwythur, ac mae'n cael ei diffinio rhywbeth o'r enw newydd yn nod.
Ac y tu mewn nod mae gyfanrif i'r dde yma ac mae pwyntydd i
nod arall.
Rydym wedi gweld hyn o'r blaen.
Mae hyn wedi bod yn dod i fyny ar gyfer ychydig o wythnosau bellach.
Mae'n cyfuno awgrymiadau, yr ydym wedi bod yn gweithio gyda, a structs, sy'n caniatáu
ni i gyfuno dau wahanol pethau i mewn i un math data.
>> Mae llawer yn digwydd ar ar y sgrîn.
Ond dylai pob un fod yn gymharol gyfarwydd gyda chi.
Ar y llinell gyntaf, yr ydym yn datgan nod newydd.
Ac yna y tu mewn i'r nod newydd, yr wyf yn gosod y cyfanrif yn y nod i un.
Rydym yn gweld ar y llinell nesaf rwyf yn gwneud printf gorchymyn, ond rwyf wedi llwyd
y gorchymyn printf oherwydd bod y gwirionedd rhan bwysig yn y llinell hon yma -
new_node.n.
Beth yw ystyr y dot?
>> GYNULLEIDFA: Ewch i'r nod a asesu gwerth n ar ei gyfer.
>> JASON Hirschhorn: Mae hynny'n yn union gywir.
Dot yn golygu mynediad at y n rhan y nod newydd.
Mae'r llinell nesaf sy'n gwneud beth?
Michael.
>> GYNULLEIDFA: Mae'n creu nod arall a fydd yn tynnu sylw at y nod newydd.
>> JASON Hirschhorn: Felly nid yw'n creu nod newydd.
Mae'n creu beth?
>> GYNULLEIDFA: A pwyntydd.
>> JASON Hirschhorn: A pwyntydd i nod, fel y nodir gan nod hwn * yma.
Felly, mae'n creu pwyntydd i nod.
A pha nod y mae'n pwyntio i, Michael?
>> GYNULLEIDFA: nod sy'n Newydd?
>> JASON Hirschhorn: nod Newydd.
Ac mae'n pwyntio yno oherwydd rydym wedi ystyried ei gyfeiriad nod newydd.
Ac yn awr yn y llinell hon rydym yn gweld dwy ffordd wahanol o
mynegi yr un peth.
Ac yr wyf yn awyddus i dynnu sylw at sut mae'r rhain yn dau beth yr un fath.
Yn y llinell gyntaf, rydym yn dereference y pwyntydd.
Felly, rydym yn mynd i'r nod.
Dyna beth seren mae hyn yn golygu.
Rydym wedi gweld bod o'r blaen gyda awgrymiadau.
Ewch i'r nod.
Dyna mewn cromfachau.
Ac yna cael mynediad drwy'r gweithredwr dot yr elfen n y nod.
>> Felly, mae hynny'n cymryd y gystrawen gwelsom yn iawn yma ac yn awr
ddefnyddio gyda pwyntydd.
Wrth gwrs, mae'n mynd yn fath o brysur os rydych yn ysgrifennu cromfachau hynny -
y seren a bod y dot.
Mae'n cael ychydig yn brysur.
Felly, mae gennym ychydig o siwgr cystrawennol.
Ac mae hyn yn llinell iawn yma -
ptr_node-> n.
Mae hynny'n gwneud yr un peth yn union.
Felly, y rhai dwy linell o god yn cyfatebol a bydd yn gwneud
yr un peth yn union.
>> Ond yr wyf yn awyddus i dynnu sylw at hynny cyn rydym yn mynd ymhellach, felly eich bod yn deall
y peth hyn yn iawn yma wir yn dim ond siwgr cystrawennol ar gyfer dereferencing
y pwyntydd ac yna yn mynd i y n rhan o'r strwythur.
Unrhyw gwestiynau am y sleid hon?
OK.
>> Felly, rydym yn mynd i fynd drwy un neu ddau o weithrediadau y gallwch ei wneud ar
rhestrau cysylltiedig.
Mae rhestr cysylltiedig, galw i gof, yn gyfres o nodau sy'n cyfeirio at ei gilydd.
Ac rydym yn gyffredinol yn dechrau gyda pwyntydd a elwir yn pen, yn gyffredinol, sy'n awgrymu
y peth cyntaf yn y rhestr.
Felly, ar y llinell gyntaf yma, rydym yn wedi ein L gwreiddiol yn gyntaf.
Er mwyn i beth gallwch chi feddwl - mae hyn yn testun i'r dde yma gallwch chi feddwl fel
dim ond y pwyntydd rydym wedi storio bod pwyntiau rhywle
at yr elfen gyntaf.
Ac yn y rhestr gysylltiedig mae gennym bedwar nodau.
Mae pob nod yw bocs mawr.
Mae'r blwch mwy o faint y tu mewn i'r mawr blwch yn y rhan gyfanrif.
Ac yna mae gennym ran pwyntydd.
>> Nid yw'r blychau yn cael eu tynnu i eu maint, oherwydd pa mor fawr yn
cyfanrif mewn bytes?
Pa mor fawr nawr?
Pedwar.
A pha mor fawr yn pwyntydd?
Pedwar.
Felly mewn gwirionedd, pe baem yn tynnu hyn i raddfa y ddau flwch
Byddai fod yr un maint.
Yn yr achos hwn, rydym am i fewnosod rhywbeth yn y rhestr gysylltiedig.
Fel y gallwch weld i lawr yma rydym yn gosod pump Rydym yn croesi drwy'r
rhestr gysylltiedig, dod o hyd lle mae pump mynd, ac yna rhowch ef.
>> Gadewch i ni dorri'r i lawr ac yn mynd ychydig yn fwy araf.
Rydw i'n mynd i dynnu sylw at y bwrdd.
Felly, rydym wedi ein nod pum sydd rydym wedi creu yn mallocs.
Pam mae pawb yn chwerthin?
Dim ond kidding.
OK.
Felly, rydym wedi malloced pump.
Rydym wedi creu nod hwn rhywle arall.
Yr ydym wedi ei barod i fynd.
Rydym yn dechrau ar flaen y ein rhestr gyda dau.
Ac rydym am i fewnosod mewn modd ddidoli.
>> Felly, os byddwn yn gweld dau ac rydym yn awyddus i roi mewn pump, beth ydym yn ei wneud pan fyddwn yn gweld
rhywbeth llai na ni?
Beth?
Rydym am i fewnosod bump i mewn i hyn rhestr gysylltiedig, gan ei gadw datrys.
Rydym yn gweld rhif dau.
Felly, beth ydym yn ei wneud?
Marcus?
>> GYNULLEIDFA: Ffoniwch y pwyntydd i'r nod nesaf.
>> JASON Hirschhorn: A pham mae rydym yn mynd i'r un nesaf?
>> GYNULLEIDFA: Oherwydd ei fod yn y nod nesaf yn y rhestr.
A dim ond yn gwybod bod lleoliad arall.
>> JASON Hirschhorn: A phump yn fwy na dau, yn arbennig.
Oherwydd ein bod am ei gadw eu sortio.
Felly, pump yn fwy na dau.
Felly, rydym yn symud ymlaen at yr un nesaf.
Ac yn awr rydym yn cyrraedd pedwar.
A beth fydd yn digwydd pan fyddwn yn cyrraedd pedwar?
>> Pump yn fwy na phedwar.
Felly rydym yn cadw i fynd.
Ac yn awr ein bod ni'n ar chwech.
A beth ydym yn ei weld o chwech?
Ie, Carlos?
>> GYNULLEIDFA: Chwech yn fwy na phump.
>> JASON Hirschhorn: Chwech yn fwy na phump.
Felly, dyna lle rydym am i fewnosod bump.
Fodd bynnag, yn cadw mewn cof bod os ydym Dim ond un pwyntydd yma -
mae hyn yn ein pwyntydd ychwanegol sy'n croesi drwy'r rhestr.
Ac rydym yn pwyntio i chwech.
Rydym wedi colli golwg ar yr hyn yn dod cyn chwech.
Felly, os ydym am i fewnosod rhywbeth yn rhestr hon gadw'n didoli, yr ydym yn
Mae'n debyg bod angen sawl awgrymiadau?
>> GYNULLEIDFA: Dau.
>> JASON HIRSCHORN: Dau.
Un i gadw golwg ar y presennol un ac un i gadw golwg ar
yr un blaenorol.
Dim ond rhestr gysylltiedig yn unigol ydyw.
Dim ond yn mynd i un cyfeiriad.
Pe bai gennym rhestr gysylltiedig ddwbl, lle popeth yn pwyntio at y peth
ar ôl iddo a'r peth cyn iddo, yna Ni fyddai angen i ni wneud hynny.
Ond yn yr achos hwn nid ydym am golli golwg ar yr hyn a ddaeth ger ein bron rhag ofn
mae angen i fewnosod pum rhywle yn y canol.
Dywedwch ein bod yn gosod naw.
Beth fyddai'n digwydd pan rydym yn cael i wyth?
>> GYNULLEIDFA: Byddwn yn rhaid i chi cael y pwynt null.
Yn hytrach na chael pwynt null byddech yn cael i ychwanegu elfen ac wedyn yn cael
bwyntio at naw.
>> JASON HIRSCHORN: Yn union.
Felly, rydym yn cael wyth.
Rydym yn cyrraedd diwedd y rhestr oherwydd mae hyn yn pwyntio i null.
Ac yn awr, yn hytrach na chael ei gyfeirio at null yr ydym wedi ei gyfeirio at ein nod newydd.
Ac rydym yn gosod y pwyntydd yn ein nod newydd null.
A oes unrhyw un gennych unrhyw gwestiynau am fewnosod?
Beth os nad wyf yn poeni am cadw'r rhestr datrys?
>> GYNULLEIDFA: Stick hynny ar y dechrau neu'r diwedd.
>> JASON HIRSCHORN: Stick ei yn ddechrau neu y diwedd.
Pa un ddylem ni ei wneud?
Bobi?
Pam y diwedd?
>> GYNULLEIDFA: Oherwydd bod y dechrau eisoes yn llenwi.
>> JASON HIRSCHORN: OK.
Mae dechrau eisoes yn cael ei lenwi.
Pwy sydd eisiau i ddadlau yn erbyn Bobby.
Marcus.
>> GYNULLEIDFA: Wel, eich bod eisiau lynu ar y dechrau oherwydd
fel arall, os ydych yn ei roi ar diwedd y byddai'n rhaid i chi
groesi'r rhestr gyfan.
>> JASON HIRSCHORN: Yn union.
Felly, os ydym yn meddwl am runtime, y Rhedeg o mewnosod ar y diwedd
fyddai n, maint y.
Beth yw'r O Rhedeg mawr o mewnosod ar y dechrau?
Amser yn gyson.
Felly, os nad ydych yn poeni am gadw rhywbeth didoli, llawer gwell i ddim ond
mewnosoder ar y dechrau y rhestr hon.
A gall ei wneud mewn amser cyson.
>> OK.
Gweithredu nesaf yn dod o hyd i, a eraill - rydym wedi geirio hyn fel chwilio.
Ond rydym yn mynd i edrych drwy'r rhestr gysylltiedig ar gyfer rhai gwrthrych.
Rydych guys wedi gweld cod ar gyfer chwilio o'r blaen yn ddarlith.
Ond rydym yn fath o yn unig yn gwneud hynny gyda mewnosoder, neu o leiaf fewnosod
rhywbeth didoli.
Byddwch yn edrych drwy, nod mynd gan nod, nes i chi ddod o hyd i'r rhif eich bod yn
chwilio amdano.
Beth fydd yn digwydd os byddwch yn cyrraedd ddiwedd y rhestr?
Dweud fy mod i'n chwilio am naw ac yr wyf yn cyrraedd diwedd y rhestr.
Beth ydym ni'n ei wneud?
>> GYNULLEIDFA: Dychwelyd ffug?
>> JASON HIRSCHORN: Dychwelyd ffug.
Nid ydym yn ei chael yn.
Os byddwch yn cyrraedd diwedd y rhestr a nad ydych yn dod o hyd i'r rhif ydych chi'n
chwilio amdano, nid yw'n mewn 'na.
Unrhyw gwestiynau am ddod o hyd i?
Pe bai hwn yn rhestr ddidoli, beth fyddai fod yn wahanol ar gyfer ein chwilio?
Yeah.
>> GYNULLEIDFA: Byddai'n dod o hyd i'r gwerth cyntaf mae hynny'n fwy na'r un
ydych yn chwilio am a wedyn yn dychwelyd ffug.
>> JASON HIRSCHORN: Yn union.
Felly, os yw'n rhestr ddidoli, os ydym yn cael i rhywbeth sy'n fwy na'r hyn
rydym yn chwilio am, nid oes angen i ni gadw i fynd at ddiwedd y rhestr.
Gallwn ar y pwynt hwnnw yn dychwelyd ffug oherwydd nad ydym yn mynd i ddod o hyd iddo.
Mae'r cwestiwn yn awr, rydym wedi trafod cadw rhestrau cysylltiedig didoli,
cadw'n heb eu didoli.
Mae hynny'n mynd i fod yn rhywbeth yr ydych yn na thebyg yn mynd i gael i feddwl am
wrth codio problem yn gosod pump os ydych yn dewis tabl hash â ar wahân
gadwyno dull, a oedd yn byddwn yn siarad am hynny yn ddiweddarach.
>> Ond a yw'n werth yr ymdrech i gadw'r rhestr datrys hynny ac wedyn yn gallu efallai wedi
chwiliadau cyflymach?
Neu a yw'n well i fewnosod yn gyflym rhywbeth yn Rhedeg cyson ond wedyn
wedi chwilio yn hirach?
Dyna tradeoff iawn yno eich bod yn cael penderfynu beth yn fwy priodol
ar gyfer eich problem benodol.
Ac nid oes o reidrwydd yn un ateb hollol gywir.
Ond mae'n sicr yn benderfyniad byddwch yn cael i'w wneud, ac mae'n debyg da i amddiffyn
hynny mewn, dyweder, sylw neu ddau pam byddwch yn dewis un dros y llall.
>> Yn olaf, dileu.
Rydym wedi gweld dileu.
Mae'n debyg i chwilio.
Rydym yn edrych am yr elfen.
Dweud ein bod yn ceisio dileu chwech.
Felly, rydym yn dod o hyd i chwech yma.
Y peth y mae'n rhaid i ni wneud yn siwr ein bod wneud yw bod beth bynnag yn pwyntio i
chwech - fel y gwelwn yn gam dau i lawr yma -
beth bynnag sy'n pwyntio i chwe hanghenion er mwyn skip chwe awr ac yn cael ei newid i
beth bynnag chwech yn pwyntio i.
Nid ydym am i erioed amddifad gweddill ein rhestr drwy anghofio i osod y
pwyntydd flaenorol.
Ac yna weithiau, yn dibynnu ar y rhaglen, maent yn annhymerus 'yn unig
dileu nod hwn yn llwyr.
Weithiau, byddwch am ddychwelyd y gwerth sydd yn nod hwn.
Felly dyna sut y bydd dileu yn gweithio.
Unrhyw gwestiynau am ddileu?
>> GYNULLEIDFA: Felly, os ydych yn mynd i ddileu hynny, y byddech yn jyst arfer am ddim oherwydd
yn ôl pob tebyg cafodd ei malloced?
>> JASON HIRSCHORN: Os ydych am i ryddhau rhywbeth sy'n union iawn ac rydych yn
malloced ei.
Dywedwch ein bod eisiau dychwelyd y gwerth hwn.
Efallai y byddwn yn dychwelyd chwech ac wedyn yn rhydd nod hwn a ffoniwch am ddim ar ei.
Neu byddem yn ôl pob tebyg ffoniwch am ddim yn gyntaf ac yna'n dychwelyd chwech.
>> OK.
Felly, gadewch i ni symud ymlaen i ymarfer codio.
Rydym yn mynd i cod tair swyddogaeth.
Gelwir Mae'r un cyntaf wedi'i insert_node.
Felly, mae gennych cod fy mod yn e-bostio i chi, a os ydych yn gwylio hyn yn nes ymlaen ar
gallwch gael mynediad i'r cod yn linked.c ar y wefan CS50.
Ond yn linked.c, mae rhywfaint cod sgerbwd sydd eisoes
cael ei ysgrifennu i chi.
Ac yna mae 'na swyddogaethau cwpl angen i chi ysgrifennu.
>> Yn gyntaf rydym yn mynd i ysgrifennu insert_node.
A beth insert_node yn ei wneud yw mewnosod yn gyfanrif.
Ac rydych yn rhoi'r cyfanrif i mewn i restr cysylltiedig.
Ac yn benodol, mae angen i chi i gadw'r rhestr didoli
o'r lleiaf i'r mwyaf.
Hefyd, os nad ydych am i rhowch unrhyw dyblygu.
Yn olaf, fel y gallwch weld insert_node dychwelyd bool.
Felly, rydych yn fod i adael i'r defnyddiwr wybod a oedd y mewnosodiad oedd neu beidio
llwyddiannus trwy ddychwelyd gywir neu'n anghywir.
Ar ddiwedd y rhaglen hon -
ac ar gyfer y cam hwn nid oes angen i chi i chi boeni am unrhyw beth rhyddhau.
Felly, i gyd rydych chi'n ei wneud yn cymryd yn gyfanrif a mewnosod i mewn i restr.
>> Dyna beth rwy'n gofyn i chi wneud yn awr.
Unwaith eto, yn y linked.c, yr ydych yn i gyd yn cael, yw'r cod sgerbwd.
A dylech weld tuag at y gwaelod y datganiad swyddogaeth sampl.
Fodd bynnag, cyn mynd i mewn i godio ei yn C, yr wyf yn gryf eich annog i fynd
drwy'r camau yr ydym wedi bod yn ymarfer bob wythnos.
Rydym eisoes wedi mynd trwy llun o hyn.
Felly, dylech chi gael rhywfaint o ddealltwriaeth o sut mae hyn yn gweithio.
Ond byddwn yn eich annog i ysgrifennu rhywfaint o pseudocode cyn plymio i mewn
Ac rydym yn mynd i fynd dros pseudocode fel grŵp.
Ac yna unwaith y byddwch wedi ysgrifennu eich pseudocode, ac unwaith y byddwn wedi ysgrifennu ein
pseudocode fel grŵp, gallwch mynd i mewn i godio yn C.
>> Fel pennau i fyny, y swyddogaeth insert_node Mae'n debyg mai dyma'r dyrys o
y tri rydyn ni'n mynd i ysgrifennu am fy mod yn ychwanegu rhai cyfyngiadau ychwanegol i
eich rhaglennu, yn arbennig nad ydych yn mynd i osod unrhyw
dyblygu a bod y rhestr dylai aros eu sortio.
Felly, mae hyn yn rhaglen heb fod yn ddibwys bod angen i chi i cod.
A pham nad ydych yn cymryd 5-7 cofnodion yn unig i gael gweithio ar y
pseudocode a'r cod.
Ac yna byddwn yn dechrau mynd fel grŵp.
Unwaith eto, os oes gennych unrhyw gwestiynau yn unig yn codwch eich llaw a byddaf yn dod o gwmpas.
.
>> Rydym hefyd yn gyffredinol yn gwneud hyn -
neu os nad wyf yn dweud i chi yn benodol gallu gweithio gyda phobl.
Ond yn amlwg, yr wyf yn gryf eich annog, os oes gennych gwestiynau, i ofyn i'r
cymydog yn eistedd nesaf i chi neu hyd yn oed yn gweithio gyda rhywun
arall os ydych yn dymuno.
Nid oes rhaid i hyn fod yn unigolyn gweithgaredd dawel.
>> Gadewch i ni ddechrau gyda ysgrifennu rhai pseudocode ar y bwrdd.
Pwy all roi llinell gyntaf i mi pseudocode gyfer y rhaglen hon?
Gyfer y swyddogaeth hon, yn hytrach - insert_node.
Alden?
>> GYNULLEIDFA: Felly, y peth cyntaf wnes i oedd creu pwyntydd newydd i'r nod ac yr wyf yn
hymgychwyn mae'n pwyntio at yr un peth y rhestr yn pwyntio i.
>> JASON HIRSCHORN: OK.
Felly rydych yn creu pwyntydd newydd at y rhestr, nid i'r nod.
>> GYNULLEIDFA: Iawn.
Yeah.
>> JASON HIRSCHORN: OK.
Ac yna beth ydym ni eisiau ei wneud?
Beth sydd ar ôl hynny?
Beth am y nod?
Nid oes gennym nod.
Rydym yn unig o werth.
Os ydym am i fewnosod nod, beth ydyn ni angen iddynt ei wneud yn gyntaf cyn y gallwn hyd yn oed
meddwl am ei roi i mewn?
>> GYNULLEIDFA: O, mae'n ddrwg gennyf.
mae angen i ni malloc lle ar gyfer nod.
>> JASON HIRSCHORN: Ardderchog.
Gadewch i ni ei wneud -
OK.
Methu cyrraedd mor uchel.
OK.
Rydym yn mynd i fynd i lawr, ac yna rydym yn defnyddio dwy golofn.
Ni allaf fynd hynny -
OK.
Creu nod newydd.
Gallwch greu pwyntydd arall i restru neu gallwch jyst arfer y rhestr fel y mae.
Nid oes angen mewn gwirionedd i chi wneud hynny.
>> Felly, rydym yn creu nod newydd.
Great.
Dyna beth rydym yn ei wneud yn gyntaf.
Beth nesaf?
>> GYNULLEIDFA: Aros.
Dylem greu nod newydd nawr neu dylem aros i wneud yn siŵr bod
does dim dyblygu y nod ar y rhestr cyn i ni greu?
>> JASON HIRSCHORN: Cwestiwn da.
Gadewch i ni dal y ar gyfer yn ddiweddarach oherwydd bod y y rhan fwyaf o'r amser byddwn yn creu
yn nod newydd.
Felly, byddwn yn cadw hynny yma.
Ond mae hynny'n gwestiwn da.
Os ydym yn creu ac rydym yn dod o hyd ddyblyg, dylai pa
rydym yn ei wneud cyn dychwelyd?
>> GYNULLEIDFA: Am ddim ei.
>> JASON HIRSCHORN: Yeah.
Mae'n debyg ei rhyddhau.
OK.
Beth rydym yn ei wneud ar ôl i ni creu nod newydd?
Annie?
>> GYNULLEIDFA: Rydym yn rhoi rhif yn y nod?
>> JASON HIRSCHORN: Yn union.
Rydym yn rhoi y nifer - rydym malloc gofod.
Rydw i'n mynd i adael y i gyd fel un llinell.
Ond rydych chi'n iawn.
Rydym yn malloc gofod, ac yna rydym yn gosod y nifer mewn
Gallwn hyd yn oed yn gosod y pwyntydd ran ohono i null.
Dyna'n union gywir.
Ac yna beth am ar ôl hynny?
Rydym Tynnodd y llun ar y bwrdd.
Felly, beth ydym yn ei wneud?
>> GYNULLEIDFA: Rydym yn mynd drwy'r rhestr.
>> JASON HIRSCHORN: Ewch drwy'r rhestr.
OK.
A beth ydym yn gwirio am o bob nod.
Kurt, beth ydym yn gwirio am o bob nod?
>> GYNULLEIDFA: Gweler a yw gwerth n o y nod yn fwy na gwerth n
ein nod.
>> JASON HIRSCHORN: OK.
Rydw i'n mynd i wneud -
yeah, OK.
Felly mae'n n -
Rydw i'n mynd i ddweud os gwerth yn fwy na nod hwn, yna beth ydym yn ei wneud?
>> GYNULLEIDFA: Wel, yna rydym yn mewnosod y peth iawn cyn hynny.
>> JASON HIRSCHORN: OK.
Felly, os yw'n fwy na hyn, yna rydym eisiau i fewnosod.
Ond rydym eisiau i fewnosod yn iawn cyn oherwydd byddai angen i ni hefyd fod yn
cadw golwg, yna, o'r hyn oedd o'r blaen.
Felly rhowch blaen.
Felly, mae'n debyg ein bod yn colli rhywbeth yn gynharach.
Rydym yn debyg y bydd angen i gael eu cadw golwg ar yr hyn sy'n digwydd.
Ond fe ddown yn ôl yno.
Felly, pa werth yn llai na?
Kurt, beth ydym yn ei wneud os gwerth yn llai na?
>> GYNULLEIDFA: Yna, 'ch jyst cadw i fynd oni bai ei fod yn y cafodd yr un olaf.
>> JASON HIRSCHORN: Rwy'n hoffi hynny.
Felly, yn mynd i'r nod nesaf.
Oni bai ei fod yn y cafodd yr un olaf -
yn ôl pob tebyg, rydym yn chwilio am y yn nhelerau'r amod.
Ond yeah, nod nesaf.
Ac mae hynny'n mynd yn rhy isel, felly byddwn yn symud dros yma.
Ond os -
Gall pawb yn gweld hyn?
Os ydym yn gyfartal beth ydym yn ei wneud?
Os yw gwerth yr ydym yn ceisio i fewnosod yn hafal i werth nod hwn?
Yeah?
>> GYNULLEIDFA: [Anghlywadwy].
>> JASON HIRSCHORN: Yeah.
O ystyried hyn -
Marcus yn iawn.
Gallem fod wedi gwneud efallai rhywbeth gwahanol.
Ond o ystyried ein bod wedi creu ei, dyma dylem am ddim ac yna'n dychwelyd.
Oh bachgen.
A yw hynny'n well?
Sut mae bod?
OK.
Rhad ac am ddim ac yna beth yr ydym yn dychwelyd, [Anghlywadwy]?
OK.
A ydym yn colli unrhyw beth?
Felly, lle yr ydym yn cadw golwg y nod blaenorol?
>> GYNULLEIDFA: Yr wyf yn meddwl y byddai'n mynd ar ôl creu nod newydd.
>> JASON HIRSCHORN: OK.
Felly, ar y dechrau byddwn ni yn ôl pob tebyg -
yeah, gallwn greu pwyntydd i newydd nod, fel pwyntydd nod blaenorol a
pwyntydd nod ar hyn o bryd.
Felly, gadewch i ni rhowch hynny yma.
Creu cyfredol a blaenorol awgrymiadau i'r nodau.
Ond pan ydyn ni'n addasu awgrymiadau hynny?
Ble rydym yn gwneud hynny yn y cod?
Jeff?
>> GYNULLEIDFA: - amodau gwerth?
>> JASON HIRSCHORN: Pa un yn benodol?
>> GYNULLEIDFA: Rwy'n drysu.
Os yw gwerth yn fwy na nod hwn, Nid yw hynny'n golygu eich bod am fynd
i'r nod nesaf?
>> JASON Hirschhorn: Felly, os ein gwerth yn fwy na gwerth y nod hwn.
>> GYNULLEIDFA: Yeah, yna byddech eisiau fynd ymhellach i lawr y lein, dde?
>> JASON Hirschhorn: Iawn.
Felly, nid ydym yn mewnosod yma.
Os yw gwerth yn llai na nod hwn, yna rydym yn mynd i'r nod nesaf - neu yna rydym yn
mewnosod o'r blaen.
>> GYNULLEIDFA: Arhoswch, sef a yw hyn nod ac sydd yn werth?
>> JASON Hirschhorn: Cwestiwn da.
Gwerth y diffiniad swyddogaeth hon yr hyn yr ydym yn ei roi.
Felly gwerth yn y nifer rydym yn ei roi.
Felly, os yw'r gwerth yn llai na hyn nod, mae angen amser i fewnosod.
Os yw gwerth yn fwy na nod hwn, rydym yn mynd i'r nod nesaf.
Ac yn ôl at y cwestiwn gwreiddiol, fodd bynnag, lle mae -
>> GYNULLEIDFA: Os yw gwerth yn fwy na nod hwn.
>> JASON Hirschhorn: Ac felly beth ydym yn ei wneud yma?
Melys.
Mae hynny'n gywir.
Im 'jyst yn mynd i ysgrifennu Diweddariad awgrymiadau.
Ond ie, gyda'r un presennol byddech yn ei ddiweddaru i
pwyntio i'r un nesaf.
Unrhyw beth arall rydym yn ar goll?
Felly, yr wyf i'n mynd i deipio hwn cod i mewn i gedit.
Ac er fy mod yn gwneud hyn, gallwch gael ychydig mwy o funudau i weithio ar godio
hyn mewn C.
>> Felly, yr wyf yn cael mewnbwn y pseudocode.
Nodyn sydyn cyn i ni ddechrau arni.
Efallai na fyddwn yn gallu i llwyr gorffen hyn ym mhob
tri o'r swyddogaethau hyn.
Mae atebion cywir iddyn nhw y byddaf yn e-bostio i chi guys
ar ôl adran, a bydd yn yn cael eu postio ar CS50.net.
Felly, nid wyf yn eich annog i mynd yn edrych ar yr adrannau.
Yr wyf yn eich annog i roi cynnig ar y rhain ar eich yn berchen ar, ac yna defnyddio'r arfer
problemau i wirio eich atebion.
Mae'r rhain i gyd wedi eu cynllunio i agos ymwneud â, a chadw at yr hyn
rhaid i chi wneud ar y broblem a osodwyd.
Felly, yr wyf yn eich annog i ymarfer hyn ar eich pen eich hun ac yna defnyddiwch y cod i
wirio eich atebion.
Gan fy mod yn dymuno symud ymlaen i hash tablau ar ryw bwynt yn yr adran.
Felly, efallai na fyddwn yn cael drwy'r cyfan.
Ond byddwn yn gwneud cymaint y gallwn yn awr.
>> OK.
Gadewch i ni ddechrau.
Asam, sut rydym yn creu nod newydd?
>> GYNULLEIDFA: ydych yn strwythur *.
>> JASON Hirschhorn: Felly, rydym yn cael bod hyd yma.
O, mae'n ddrwg gennyf.
Oeddech yn ei ddweud strwythur *.
>> GYNULLEIDFA: Ac yna [? fath?] nod neu c nod.
>> JASON Hirschhorn: OK.
Rydw i'n mynd i alw new_node er mwyn i ni aros yn gyson.
>> GYNULLEIDFA: A ydych am osod y i fod yn bennaeth, y nod cyntaf.
>> JASON Hirschhorn: OK.
Felly nawr pwyntio hon i - felly mae hyn yn nid yw wedi creu nod newydd eto.
Mae hyn yn unig yw pwyntio at y nod cyntaf yn y rhestr.
Sut ydw i'n creu nod newydd?
Os oes angen lle i greu nod newydd.
Malloc.
A pha mor fawr?
>> GYNULLEIDFA: Mae maint y strwythur.
>> JASON Hirschhorn: Y maint y strwythur.
A beth yw'r strwythur a elwir yn?
>> GYNULLEIDFA: Nôd?
>> JASON Hirschhorn: Nôd.
Felly malloc (sizeof (nod)); yn rhoi lle i ni.
Ac a yw hyn lein -
un peth yn anghywir ar y llinell hon.
A new_node pwyntydd i strwythur?
Dyna enw generig.
Beth ydyw -
nod, yn union.
Mae'n nod *.
A beth ydym yn ei wneud i'r dde ar ôl rydym yn malloc rhywbeth, Asan?
Beth yw'r peth cyntaf rydym yn ei wneud?
Beth os nad yw'n gweithio?
>> GYNULLEIDFA: O, gwiriwch os yw'n cyfeirio at y nod?
>> JASON Hirschhorn: Yn union.
Felly, os ydych new_node hafal hafal null, beth ydym yn ei wneud?
Mae hyn yn dychwelyd bool, swyddogaeth hon.
Yn union.
Yn edrych yn dda.
Unrhyw beth i'w ychwanegu yno?
Byddwn yn ychwanegu pethau ar y diwedd.
Ond bod hyd yn hyn yn edrych yn dda.
Creu awgrymiadau presennol a blaenorol.
Michael, sut ydw i'n gwneud hyn?
>> GYNULLEIDFA: Byddai gennych i wneud nod *.
Byddai'n rhaid i chi beidio â gwneud un ar gyfer new_node ond ar gyfer y
nodau sydd gennym yn barod.
>> JASON Hirschhorn: OK.
Felly, y nod ar hyn o bryd rydym yn ar.
'N annhymerus' galw hynny'n CURR.
Mae pob hawl.
Rydym wedi penderfynu ein bod am gadw dau oherwydd mae angen i ni wybod
beth sydd ger ei fron.
Beth maent yn cael ymgychwyn i?
>> GYNULLEIDFA: Mae eu gwerth yn ein rhestr.
>> JASON Hirschhorn: Felly beth yw'r peth cyntaf ar ein rhestr?
Neu sut rydym yn gwybod ble mae'r ddechrau ein rhestr yw?
>> GYNULLEIDFA: Onid yw'n pasio i mewn i'r swyddogaeth?
>> JASON Hirschhorn: Iawn.
Cafodd ei basio yn y dde yma.
Felly, os caiff ei basio i mewn i'r swyddogaeth, y ar ddechrau'r rhestr, yr hyn y dylem
gosod ar hyn o bryd yn hafal i?
>> GYNULLEIDFA: Rhestr.
>> JASON Hirschhorn: Rhestr.
Dyna'n union gywir.
Nawr mae wedi y cyfeiriad y dechrau ein rhestr.
A beth am blaenorol?
>> GYNULLEIDFA: Rhestr llai un?
>> JASON Hirschhorn: Mae dim ger ei fron.
Felly, beth allwn ni ei wneud i ddynodi dim byd?
>> GYNULLEIDFA: Null.
>> JASON Hirschhorn: Yeah.
Mae hynny'n swnio fel syniad da.
Perffaith.
Diolch yn fawr.
Ewch drwy'r rhestr.
Constantine, pa mor hir yr ydym yn mynd i fynd drwy'r rhestr?
>> GYNULLEIDFA: Nes Rydym yn cyrraedd null.
>> JASON Hirschhorn: OK.
Felly, os, er, ar gyfer dolen.
Beth rydym yn ei wneud?
>> GYNULLEIDFA: Efallai yn ar gyfer dolen?
>> JASON Hirschhorn: Gadewch i ni wneud yn ar gyfer dolen.
OK.
>> GYNULLEIDFA: Ac yr ydym yn dweud am -
nes bod y pwyntydd ar hyn o bryd Nid yn hafal i null.
>> JASON Hirschhorn: Felly, os ydym yn gwybod y cyflwr, sut y gallwn ysgrifennu dolen
seiliedig oddi cyflwr hwnnw.
Pa fath o dolen y dylem eu defnyddio?
>> GYNULLEIDFA: Er.
>> JASON Hirschhorn: Yeah.
Mae hynny'n gwneud mwy o synnwyr yn seiliedig ar oddi ar yr hyn a ddywedasoch.
Os ydym yn unig am fynd i mewn i ni y byddai jyst yn gwybod y peth, byddai'n gwneud
synnwyr i wneud dolen gyfnod.
Er bod ar hyn o bryd yn null nid gyfartal, os gwerth yn llai na nod hwn.
AKSHAR, yn rhoi y llinell hon i mi.
>> GYNULLEIDFA: Os ar hyn o bryd-> n n yn llai na gwerth.
Neu wrthdroi hynny.
Symud y braced.
>> JASON Hirschhorn: Mae'n ddrwg gennyf.
>> GYNULLEIDFA: Newid y braced.
>> JASON Hirschhorn: Felly, os yw'n yn fwy na gwerth.
Oherwydd dyna ddryslyd gyda'r sylwadau uchod, dw i'n mynd i wneud hynny.
Ond ie.
Os yw ein gwerth yn llai na hyn nod, beth ydym yn ei wneud?
Oh.
Mae gen i yn iawn yma.
Mewnosod blaen.
OK.
Sut ydym yn gwneud hynny?
>> GYNULLEIDFA: A yw'n dal i mi?
>> JASON Hirschhorn: Yeah.
>> GYNULLEIDFA: Chi -
new_node-> nesaf.
>> JASON Hirschhorn: Felly beth sydd bod yn mynd i fod yn gyfartal?
>> GYNULLEIDFA: Mae'n mynd i ar hyn o bryd cyfartal.
>> JASON Hirschhorn: Yn union.
Ac felly y llall -
beth arall y mae angen i ni i ddiweddaru?
>> GYNULLEIDFA: Gwiriwch a oes yn y gorffennol yn dychwelyd null.
>> JASON Hirschhorn: Os prev -
felly os prev hafal null.
>> GYNULLEIDFA: Mae hynny'n golygu ei fod yn mynd i ddod yn pen.
>> JASON Hirschhorn: Mae hynny'n golygu mae wedi dod yn y pen.
Felly, yna beth ydym yn ei wneud?
>> GYNULLEIDFA: Rydym yn gwneud pen hafal new_node.
>> JASON Hirschhorn: Pennaeth yn hafal i new_node.
A pham pen yma, nid rhestru?
>> GYNULLEIDFA: Oherwydd bod pen yn fyd-eang amrywiol, sef y man cychwyn.
>> JASON Hirschhorn: Sweet.
OK.
A -
>> GYNULLEIDFA: Yna byddwch yn arall prev-> nesaf yn dychwelyd new_node.
Ac yna byddwch yn dychwelyd yn wir.
>> JASON Hirschhorn: O ble rydym yn gosod pen new_node?
>> GYNULLEIDFA: Hoffwn -
Yr wyf yn sefydlu hynny ar y dechrau.
>> JASON Hirschhorn: Felly pa llinell?
>> GYNULLEIDFA: Ar ôl y datganiad os gwirio os yw'n hysbys.
>> JASON Hirschhorn: Yma?
>> GYNULLEIDFA: byddwn i'n ei wneud new_node-> n yn dychwelyd gwerth.
>> JASON Hirschhorn: Swnio'n dda.
Mae'n debyg ei fod yn gwneud synnwyr - nid ydym yn ei wneud angen i ni wybod pa rhestr rydym ar
oherwydd ein bod yn delio yn unig gydag un rhestr.
Felly datganiad swyddogaeth gwell ar gyfer yn unig yw hwn i gael gwared ar y
yn gyfan gwbl a dim ond rhowch gwerth i ben.
Nid oes hyd yn oed angen i ni wybod pa rhestr rydym yn ynddo
Ond byddaf yn ei gadw am y tro a yna newid ar diweddaru
y sleidiau a chod.
Felly mae hynny'n edrych yn dda ar hyn o bryd.
Os yw gwerth - pwy all wneud y llinell hon?
Pe bai -
beth ydym yn ei wneud yma, Noa.
>> GYNULLEIDFA: Os yw gwerth yn fwy na CURR-> n -
>> JASON Hirschhorn: Sut mae rydym yn mynd i'r nod nesaf?
>> GYNULLEIDFA: CURR-> n yn cyfartal i new_node.
>> JASON Hirschhorn: Felly n yw pa ran o'r strwythur?
Mae'r cyfanrif.
Ac new_node yn pwyntydd i nod.
Felly pa ran o CURR dylem diweddaru?
Os na n, yna beth yw'r rhan arall?
Noah, beth y rhan arall.
>> GYNULLEIDFA: O, nesaf.
>> JASON Hirschhorn: Nesaf, yn union.
Yn union.
Nesaf yw'r un cywir.
A beth arall y mae angen i ni i ddiweddaru, Noa?
>> GYNULLEIDFA: Y pwyntiau.
>> JASON Hirschhorn: Felly gwnaethom ddiweddaru ar hyn o bryd.
>> GYNULLEIDFA: Blaenorol-> nesaf.
>> JASON Hirschhorn: Yeah.
OK, byddwn yn oedi.
Pwy all ein helpu allan yma?
Manu, beth ddylem ei wneud?
>> GYNULLEIDFA: Mae'n rhaid i chi osod mae'n cyfartal i CURR-> nesaf.
Ond gwneud hynny cyn i'r llinell flaenorol.
>> JASON Hirschhorn: OK.
Unrhyw beth arall?
AKSHAR.
>> GYNULLEIDFA: Nid wyf yn meddwl eich bod yn i fod i newid CURR-> nesaf.
Rwy'n credu eich bod i fod i'w wneud hafal CURR CURR-> nesaf i fynd i'r nod nesaf.
>> JASON Hirschhorn: Felly ddrwg gennym, ble?
Ar ba lein?
Mae'r llinell hon?
>> GYNULLEIDFA: Yeah.
Gwneud CURR hafal CURR-> nesaf.
>> JASON Hirschhorn: Felly dyna gywir oherwydd ar hyn o bryd yn
Pwyntydd at nod.
Ac rydym am iddo i dynnu sylw at y nesaf nod yr hyn sy'n mynd ar hyn o bryd
yn tynnu sylw at.
CURR ei hun yn nesaf.
Ond os ydym yn i ddiweddaru curr.next, rydym yn Byddai yn diweddaru'r nodyn gwirioneddol
ei hun, nid lle mae hyn yn Roedd pwyntydd yn pwyntio.
Beth am y llinell hon, er.
Avi?
>> GYNULLEIDFA: Blaenorol-> nesaf hafal CURR.
>> JASON Hirschhorn: Felly eto, os prev yn pwyntydd i nod, prev-> nesaf yw'r
pwyntydd gwirioneddol yn y nod.
Felly byddai hyn yn cael ei diweddaru pwyntydd mewn nod i CURR.
Nid ydym am i ddiweddaru pwyntydd mewn nod.
Rydym eisiau i ddiweddaru blaenorol.
Felly, sut rydym yn gwneud hynny?
>> GYNULLEIDFA: Byddai'n fater syml o'u prev.
>> JASON Hirschhorn: Iawn.
Prev rhoi syniad i nod.
Nawr rydym yn ei newid i pwyntydd newydd i nod.
OK Gadewch i ni symud i lawr.
Yn olaf, amod olaf hwn.
Jeff, beth ydym yn ei wneud yma?
>> GYNULLEIDFA: Os yw gwerth yn cyfartal i CURR-> n.
>> JASON Hirschhorn: Mae'n ddrwg gennyf.
Oh fy daioni.
Beth?
Gwerth == CURR-> n.
Beth ydym ni'n ei wneud?
>> GYNULLEIDFA: Byddech yn rhad ac am ddim ein new_node, ac yna byddech yn dychwelyd ffug.
>> JASON Hirschhorn: Dyma beth rydym wedi ysgrifennu hyd yn hyn.
A oes unrhyw un yn cael unrhyw beth i ychwanegu cyn i ni ei wneud?
OK.
Gadewch i ni roi cynnig arni.
Gall rheolaeth gyrraedd y diwedd swyddogaeth heb fod yn ddi-rym.
Avi, beth sy'n mynd ymlaen?
>> GYNULLEIDFA: A ydych yn fod i roi dychwelyd yn wir y tu allan i'r ddolen tra?
>> JASON Hirschhorn: Nid wyf yn gwybod.
Ydych chi am i mi?
>> GYNULLEIDFA: Peidiwch byth â meddwl.
Rhif
>> JASON Hirschhorn: AKSHAR?
>> GYNULLEIDFA: Yr wyf yn meddwl eich bod i fod i rhoi ffug yn dychwelyd ar ddiwedd y
o'r ddolen tra.
>> JASON Hirschhorn: Felly, lle ydych chi eisiau iddo fynd?
>> GYNULLEIDFA: Fel y tu allan i'r ddolen tra.
Felly, os ydych yn gadael y ddolen tra mae hynny'n ei olygu eich bod wedi cyrraedd y diwedd a
dim byd wedi digwydd.
>> JASON Hirschhorn: OK.
Felly, beth ydym yn ei wneud yma?
>> GYNULLEIDFA: Yr ydych yn dychwelyd ffug yno yn ogystal.
>> JASON Hirschhorn: O, rydym yn yn ei wneud yn y ddau le?
>> GYNULLEIDFA: Yeah.
>> JASON Hirschhorn: OK.
Dylem fynd?
Oh fy daioni.
Mae'n ddrwg gen i.
Rwy'n ymddiheuro am y sgrin.
Mae'n fath o ei freaking allan ar ni.
Felly dewiswch opsiwn.
Zero, fesul y cod, ymddiswyddo y rhaglen.
Un mewnosod rhywbeth.
Gadewch i ni mewnosod tri.
Nid y mewnosodiad yn llwyddiannus.
Rydw i'n mynd i'w hargraffu.
Nid oes gennyf unrhyw beth.
OK.
Efallai dyna yn unig oedd llyngyr.
Mewnosod un.
Ddim yn llwyddiannus.
OK.
Gadewch i ni redeg drwy GDB yn gyflym iawn i weld beth sy'n digwydd.
>> Cofiwch gdb. / Enw eich rhaglen yn cael ni i GDB.
Yw bod llawer i drin?
Mae'r fflachio?
Yn ôl pob tebyg.
Caewch eich llygaid a chymryd rhai dwfn anadliadau os ydych yn cael blino
o edrych arno.
Im 'i mewn GDB.
Beth yw'r peth cyntaf i mi ei wneud yn GDB?
Mae gennym i chyfrif i maes beth sy'n digwydd yma.
Gadewch i ni weld.
Mae gennym chwe munud i ffigur gwybod beth sy'n mynd ymlaen.
Egwyl prif.
Ac yna beth ddylwn i ei wneud?
Carlos?
Rhedeg.
OK.
Gadewch i ni ddewis opsiwn.
A beth mae'n N ei wneud?
Nesaf.
Yeah.
>> GYNULLEIDFA: Heb chi sôn -
nad oeddech yn dweud bod y pennaeth, yr oedd yn ymgychwyn i null ar y dechrau.
Ond yr wyf yn meddwl eich dweud hynny yn iawn.
>> JASON Hirschhorn: Gadewch i ni fynd - gadewch i ni edrych yn GDB, ac yna byddwn yn mynd yn ôl.
Ond mae'n swnio fel chi eisoes wedi rhai syniadau am yr hyn sy'n digwydd.
Felly, rydym am i fewnosod rhywbeth.
OK.
Rydym wedi mewnosod.
Os gwelwch yn dda gofnodi int.
Byddwn yn mewnosod tri.
Ac yna dwi ar y llinell hon.
Sut ydw i'n mynd dechrau debugging y mewnosodiad yn hysbys swyddogaeth?
Oh fy daioni.
Mae hynny'n llawer.
A yw hynny'n freaking allan llawer?
>> GYNULLEIDFA: O, mae'n farw.
>> JASON Hirschhorn: Fi jyst tynnu allan.
OK.
>> GYNULLEIDFA: Efallai ei fod yn y ben arall y wifren.
>> JASON Hirschhorn: Wow.
Felly y llinell waelod -
beth wnaethoch chi ei ddweud?
>> GYNULLEIDFA: Dywedais yr eironi o technegol anawsterau yn y dosbarth hwn.
>> JASON Hirschhorn: Yr wyf yn gwybod.
Os mai dim ond bu'n rhaid i mi reolaeth dros y rhan honno.
[Anghlywadwy]
Mae hynny'n swnio'n wych.
Pam na wnewch chi guys yn dechrau meddwl am yr hyn y gallem fod wedi ei wneud yn anghywir,
a byddwn yn ôl mewn 90 eiliad.
>> Avica, dw i'n mynd i ofyn i chi sut i fynd insert_node y tu mewn i debug iddo.
Felly, mae hyn yw pan diwethaf rydym yn gadael i ffwrdd.
Sut ydw i'n mynd y tu mewn insert_node, Avica, i edrych ar beth sy'n mynd ymlaen?
Pa gorchymyn GDB?
Ni fyddai seibiant mynd â fi tu mewn.
Ydy Marquise gwybod?
>> GYNULLEIDFA: Beth?
>> JASON Hirschhorn: Beth GDB gorchymyn Rwy'n defnyddio i fynd i mewn y swyddogaeth hon?
>> GYNULLEIDFA: Cam?
>> JASON Hirschhorn: Camu drwy S. Mae hynny'n mynd â mi y tu mewn.
OK.
New_node mallocing rhywfaint o le.
Bod yr holl edrych fel ei mynd.
Gadewch i ni edrych new_node.
Mae'n cael rhai cyfeiriad cof.
Gadewch i ni wirio -
bod i gyd yn gywir.
Felly popeth yma yn ymddangos i yn gweithio yn gywir.
>> GYNULLEIDFA: Beth yw'r gwahaniaeth rhwng P ac arddangos?
>> JASON Hirschhorn: P sefyll am argraffu.
Ac felly ydych yn gofyn beth yw'r gwahaniaeth rhwng hynny a'r hyn?
Yn yr achos hwn, dim byd.
Ond yn gyffredinol mae rhai gwahaniaethau.
A dylech edrych yn y llawlyfr GDB.
Ond yn yr achos hwn, dim byd.
Rydym yn tueddu i ddefnyddio print, fodd bynnag, oherwydd Nid oes angen inni wneud llawer mwy na
argraffu gwerth sengl.
>> OK.
Felly rydym yn ar-lein 80 o'n cod, gosod nod * CURR cyfartal i rhestr.
Gadewch i ni argraffu CURR.
Mae'n yn dychwelyd rhestr.
Melys.
Aros.
Mae'n yn dychwelyd rhywbeth.
Nid yw hynny'n ymddangos yn iawn.
Dyna ni fynd.
Mae'n oherwydd yn GDB, ar y dde, os 'i' y llinell ydych chi ar ei
nid yw wedi cyflawni eto.
Felly mae angen i chi deipio mewn gwirionedd yn nesaf i gyflawni'r llinell
cyn gweld ei ganlyniadau.
Felly dyma ni.
Rydym yn unig yn cyflawni y llinell hon, yn hafal blaenorol null.
Felly eto, os ydym argraffu blaenorol ni fyddwn yn gweld unrhyw beth od.
Ond os ydym mewn gwirionedd yn gweithredu y llinell, yna byddwn yn gweld
bod y llinell yn gweithio.
>> Felly, rydym wedi CURR.
Y rhai yn dda.
Iawn?
Nawr ein bod ar y llinell hon iawn yma.
Er nad CURR yn null cyfartal.
Wel, beth mae CURR cyfartal?
Rydym yn unig yn gweld ei fod yn gyfystyr null.
Rydym hargraffu arni.
'N annhymerus' ei hargraffu eto.
Felly y mae, er bod dolen mynd i weithredu?
>> GYNULLEIDFA: Na
>> JASON Hirschhorn: Felly, pan fyddaf deipio bod lein, byddwch yn gweld ein bod yn neidio yr holl ffordd
i lawr i waelod, yn dychwelyd ffug.
Ac yna rydym yn mynd i ddychwelyd ffug a mynd yn ôl at ein rhaglen a
yn y pen draw argraffu, fel y gwelsom, Nid y mewnosodiad yn llwyddiannus.
Felly, unrhyw un gennych unrhyw syniadau ar yr hyn mae angen i ni ei wneud i atgyweiria hon?
Rydw i'n mynd i aros hyd nes i mi weld un neu ddau o ddwylo yn mynd i fyny.
Doedden ni ddim yn gweithredu hyn.
Cadwch mewn cof, dyma oedd y cyntaf beth yr ydym yn ei wneud.
Dydw i ddim yn mynd i wneud cwpl.
Rydw i'n mynd i wneud ychydig.
Gan fod cwpl yn golygu dau.
'N annhymerus' aros am fwy na dwy.
>> Gosod cyntaf, CURR, yn ddiofyn yn dychwelyd null.
Ac mae dolen hyn ond yn executes os nad CURR yn null.
Felly, sut galla i fynd o gwmpas hyn?
Rwy'n gweld tair llaw.
'N annhymerus' aros am fwy na thri.
Marcus, beth yn eich barn chi?
>> GYNULLEIDFA: Wel, os bydd ei angen arnoch i gweithredu mwy nag unwaith, 'ch jyst
newid i ddolen do-tra.
>> JASON Hirschhorn: OK.
A fydd yn datrys ein problem, er bod?
>> GYNULLEIDFA: Yn yr achos hwn ni oherwydd y ffaith bod y rhestr yn wag.
Felly, yna mae'n debyg, ond mae angen i ychwanegu datganiad, os bydd y allanfeydd ddolen
Yna, rhaid i chi fod ar ddiwedd y y rhestr, a phryd ydych
gall dim ond rhowch ei.
>> JASON Hirschhorn: Rwy'n hoffi hynny.
Mae hynny'n gwneud synnwyr.
Os yw'r ddolen allanfeydd -
oherwydd bydd yn dychwelyd ffug yma.
Felly, os bydd y allanfeydd ddolen, yna rydym ni mewn ddiwedd y rhestr, neu efallai y
dechrau o restr os nad oes unrhyw beth yn iddo, sef yr un fath ag y diwedd.
Felly, nawr rydym am i fewnosod rhywbeth yma.
Felly sut mae hynny'n cod edrych, Marcus?
>> GYNULLEIDFA: Os ydych eisoes yn cael y nod malloced, fe allech chi ddweud
new_node-> hafal nesaf null oherwydd mae'n rhaid iddo fod ar y diwedd.
Neu new_node-> nesaf hafal null.
>> JASON Hirschhorn: OK.
Mae'n ddrwg gennym.
New_node-> hafal null nesaf oherwydd ein bod ar y diwedd.
Nid yw hynny'n rhoi i mewn
Sut yr ydym yn ei roi yn y rhestr?
Iawn.
Dyna dim ond ei osod hafal i.
Na sut mae mewn gwirionedd roi yn y rhestr?
Beth sy'n pwyntio at y ddiwedd y rhestr?
>> GYNULLEIDFA: Head.
>> JASON Hirschhorn: Mae'n ddrwg gennyf?
>> GYNULLEIDFA: Pennaeth yn pwyntio at ddiwedd y rhestr.
>> JASON Hirschhorn: Os oes unrhyw beth yn y rhestr, pen yn pwyntio at y
ddiwedd y rhestr.
Felly bydd yn gweithio ar gyfer yr gosod cyntaf.
Beth am os oes gwpl pethau yn y rhestr?
Nag nad ydym am i osod pen cyfartal i new_node.
Beth ydym ni eisiau ei wneud yno?
Yeah?
Yn ôl pob tebyg blaenorol.
A fydd yn gweithio?
Dwyn i gof bod blaenorol yn unig pwyntydd i nod.
A blaenorol yn newidyn lleol.
Felly, bydd y llinell hon yn gosod newidyn lleol, blaenorol, yn hafal i neu'n
gan dynnu sylw at y nod newydd.
Ni fydd hynny mewn gwirionedd yn ei roi yn ein rhestr, er.
Sut yr ydym yn ei roi yn ein rhestr?
Akchar?
>> GYNULLEIDFA: Yr wyf yn meddwl eich wneud ar hyn o bryd-> nesaf.
>> JASON Hirschhorn: OK.
CURR-> nesaf.
Felly eto, yr unig reswm rydym yn i lawr yma yw, beth mae ar hyn o bryd yn gyfartal?
>> GYNULLEIDFA: Equals null.
>> JASON Hirschhorn: Ac felly beth digwydd os ydym yn ei wneud null-> nesaf?
Beth ydym yn mynd i gael?
Byddwn yn cael wall.
>> GYNULLEIDFA: Do CURR hafal null.
>> JASON Hirschhorn: Dyna'r un peth fel cynt, fodd bynnag, oherwydd mae
newidyn lleol rydym yn gosod gyfartal i'r nod newydd.
Gadewch i ni fynd yn ôl at ein llun o mewnosod rhywbeth.
Dweud ein bod yn gosod ar y diwedd y rhestr, felly dde yma.
Mae gennym pwyntydd cyfredol sy'n pwyntio at null a phwynt blaenorol
mae hynny'n pwyntio i 8.
Felly, beth sydd angen i ni ei diweddaru, Avi?
>> GYNULLEIDFA: Blaenorol-> nesaf?
>> JASON Hirschhorn: Blaenorol-> nesaf yw beth rydym am i ddiweddaru oherwydd dyna
mewn gwirionedd fewnosod yn ddiwedd y rhestr.
Rydym yn dal i gael un nam, fodd bynnag, ein bod yn mynd i redeg i mewn.
Beth sy'n bod bug?
Yeah?
>> GYNULLEIDFA: Mae'n mynd i ddychwelyd ffug yn yr achos hwn?
>> JASON Hirschhorn: O, yn cael ei mynd i ddychwelyd ffug.
Ond mae nam arall.
Felly bydd angen i ni roi yn gyfnewid wir.
>> GYNULLEIDFA: A oes blaenorol cyfartal yn dal i null ar frig y rhestr?
>> JASON Hirschhorn: dal Felly blaenorol yn hafal null ar y dechrau.
Felly, sut y gallwn ddod dros hynny?
Yeah?
>> GYNULLEIDFA: Yr wyf yn meddwl y gallwch chi wneud siec cyn y ddolen amser i weld os yw'n
rhestr wag.
>> JASON Hirschhorn: OK.
Felly, gadewch i ni fynd yma.
Gwnewch siec.
Pe bai -
>> GYNULLEIDFA: Felly, os pen yn hafal hafal null.
>> JASON Hirschhorn: Os pen hafal hafal null -
bydd yn dweud wrthym os yw'n rhestr wag.
>> GYNULLEIDFA: Ac yna i chi gwneud pennaeth yn dychwelyd newydd.
>> JASON Hirschhorn: Pennaeth yn hafal i new_node?
A beth arall y mae angen i ni ei wneud?
>> GYNULLEIDFA: Ac yna byddwch yn dychwelyd yn wir.
>> JASON Hirschhorn: Ddim yn eithaf.
Ein bod ar goll yn un cam.
>> GYNULLEIDFA: New_node nesaf wedi i bwyntio at null.
>> JASON Hirschhorn: Yn union, Alden.
Ac yna gallwn ddychwelyd wir.
OK.
Ond mae'n dal i fod yn syniad da i wneud pethau ar ddiwedd y rhestr, dde?
Mae pob hawl.
Rydym efallai yn dal i gael mewn gwirionedd at ddiwedd y rhestr.
Felly yn y cod hwn dirwy os ydym yn y yn dod i ben y rhestr ac mae rhai
pethau yn y rhestr?
Iawn?
Oherwydd ein bod yn dal i gael syniad Marcus yn.
Efallai y byddwn yn gadael dolen hwn oherwydd rydym yn ar ddiwedd y rhestr.
Felly, yr ydym yn dal i fod eisiau hwn cod i lawr yma?
>> GYNULLEIDFA: Ydw.
>> JASON Hirschhorn: Yeah.
A beth mae angen i ni newid hyn i?
Gwir.
A yw hynny'n da cadarn i bawb hyd yn hyn?
Unrhyw un yn cael unrhyw -
Avi, a oes gennych rywbeth i'w ychwanegu?
>> GYNULLEIDFA: Na
>> JASON Hirschhorn: OK.
Felly, rydym wedi gwneud un neu ddau o newidiadau.
Rydym wedi gwneud y gwiriad hwn cyn i ni aeth i mewn am restr wag.
Felly, rydym wedi cymryd gofal o restr wag.
A dyma ni yn cymryd gofal o mewnosod rhywbeth ar ddiwedd y rhestr.
Felly, mae'n ymddangos fel hyn gymryd dolen tra gofalu am bethau yn y canol,
rhywle yn y rhestr os oes yn bethau yn y rhestr.
>> OK.
Gadewch i ni redeg y rhaglen hon eto.
Ddim yn llwyddiannus.
>> GYNULLEIDFA: Nid ydych yn gwneud hynny.
>> JASON Hirschhorn: O, Doeddwn i ddim yn gwneud hynny.
Bwynt da, Michael.
Gadewch i ni ychwanegu gwneud cysylltiedig.
Llinell 87 mae gwall.
Llinell 87.
Alden, dyma oedd y llinell roesoch i mi.
Beth sydd o'i le?
>> GYNULLEIDFA: Mae'n rhaid iddo fod i null.
>> JASON Hirschhorn: Ardderchog.
Yn union i'r dde.
Dylai fod yn nwl.
Gadewch i ni wneud eto.
Llunio.
OK.
Gadewch i ni mewnosod tri.
Y mewnosodiad yn llwyddiannus.
Gadewch i ni ei hargraffu.
Oh, os mai dim ond gallem edrych ar.
Ond nid ydym wedi gwneud y argraffu swyddogaeth eto.
Gadewch i ni fynd i mewn rhywbeth arall.
Beth ddylem ni fynd i mewn?
>> GYNULLEIDFA: Saith.
>> JASON Hirschhorn: Saith?
>> GYNULLEIDFA: Ydw.
>> JASON Hirschhorn: Mae gennym nam SEG.
Felly, rydym yn cael un, ond mae'n amlwg bod Ni allwch gael dau.
Mae'n 05:07.
Felly, gallem dadfygio hwn am dri munud.
Ond dw i'n mynd i adael ni yma a symud ymlaen i hash byrddau.
Ond unwaith eto, yr atebion ar gyfer y cod hwn Byddaf yn e-bostio i chi mewn ychydig.
Rydym yn agos iawn ato.
Fi 'n dal eich annog i chyfrif i maes beth sy'n digwydd yma ac yn atgyweiria '.
Felly, 'n annhymerus' e-bost y cod hwn i chi fel yn dda yn ogystal â'r ateb -
yn ôl pob tebyg yr ateb yn nes ymlaen.
Gyntaf y cod hwn.
>> Y peth arall yr wyf am ei wneud cyn i ni gorffeniad yn nad ydym wedi rhyddhau unrhyw beth.
Felly, yr wyf yn awyddus i ddangos i chi beth valgrind edrych fel.
Os byddwn yn cynnal ffiniau valgrind ar ein rhaglen,. / cysylltiedig.
Unwaith eto, yn ôl i'r sleid hwn, rydym Dylai redeg valgrind gyda rhyw fath o
opsiwn, yn yr achos hwn - Gollwng-siec = llawn.
Felly, gadewch i ni ysgrifennu valgrind - Gollwng-siec = llawn.
Felly, bydd hyn yn rhedeg valgrind ar ein rhaglen.
Ac yn awr y rhaglen mewn gwirionedd yn rhedeg.
Felly, rydym yn mynd i redeg yn union fel blaen, rhoi rhywbeth i mewn
Rydw i'n mynd i roi mewn tri.
Sy'n gweithio.
Dydw i ddim yn mynd i geisio rhoi rhywbeth arall oherwydd ein bod yn mynd i
gael ffug seg yn yr achos hwnnw.
Felly, Im 'jyst yn mynd i roi'r gorau iddi.
>> Ac yn awr byddwch yn gweld i lawr yma gollwng a chrynodeb domen.
Mae'r rhain yn y pethau da sy'n ydych am weld allan.
Felly, y crynodeb domen - mae'n ei ddweud, yn cael eu defnyddio wrth ymadael - wyth bytes mewn un bloc.
Dyna un bloc yn y nod yr ydym yn malloced.
Michael, dywedasoch cyn nod yw wyth brathiadau oherwydd ei fod wedi cyfanrif
a'r pwyntydd.
Felly dyna ein nod.
Ac yna mae'n dweud rydym yn defnyddio malloc saith gwaith ac rydym yn rhyddhau
rhywbeth chwe gwaith.
Ond ni fyddwn byth a elwir yn rhad ac am ddim, felly nid oes gennyf syniad beth mae hyn yn sôn am.
>> Ond digon yw dweud bod pan fydd eich yn rhedeg y rhaglen, malloc yn cael ei alw'n
mewn rhai mannau eraill yr ydym Nid oes angen i chi boeni am.
Felly, yn ôl pob tebyg malloc ei alw mewn rhai mannau.
Nid oes angen i ni boeni ble.
Ond mae hyn yn wir i ni.
Mae'r llinell gyntaf yn ni.
Rydym yn gadael y bloc hwnnw.
A gallwch weld bod yma yn y crynodeb gollyngiad.
Still gyraeddadwy -
wyth bytes mewn un bloc.
Mae hynny'n golygu y cof -
rydym wedi gollwng y cof.
Colli Yn bendant -
rhywbeth yn cael ei golli am byth.
Yn gyffredinol, ni fyddwch yn gweld dim yno.
Still gyraeddadwy yn gyffredinol lle byddwch yn gweld pethau, lle byddwch chi eisiau
i edrych i weld pa cod dylech wedi rhyddhau ond ydych wedi anghofio am ddim.
>> Ac yna os nad oedd hyn yn wir, pe baem yn gwneud popeth yn rhad ac am ddim,
gallwn gadarnhau hynny.
Gadewch i jyst yn rhedeg y rhaglen peidio â rhoi mewn unrhyw beth.
Byddwch yn gweld i lawr yma yn cael eu defnyddio wrth ymadael -
sero bytes yn sero blociau.
Mae hynny'n golygu ein bod wedi dim ar ôl pan wedi gadael y rhaglen hon.
Felly, cyn troi yn pset6, rhedeg valgrind a gwneud yn siŵr nad oes gennych
unrhyw cof gollyngiadau yn eich rhaglen.
Os oes gennych unrhyw gwestiynau valgrind, croeso i estyn allan.
Ond mae hyn yn sut yr ydych yn ei ddefnyddio.
Syml iawn - weld os ydych yn cael eu defnyddio ar hyn allanfa -
unrhyw bytes mewn unrhyw blociau.
>> Felly, rydym yn gweithio ar nodwch y nod.
Cefais ddau swyddogaethau eraill yma - argraffu nodau a nodau rhad ac am ddim.
Unwaith eto, mae'r rhain yn swyddogaethau sy'n cael eu mynd i fod yn dda i chi i ymarfer
oherwydd y byddant yn eich helpu nid yn unig gyda hyn ymarferion sampl, ond hefyd
ar y broblem a osodwyd.
Maent yn y map ar 'n bert agos i bethau eich bod yn mynd i gael ei wneud yn y
broblem a osodwyd.
Ond yr wyf am wneud yn siŵr rydym yn cyffwrdd ar bopeth.
A tablau hash hefyd yn hanfodol i yr hyn rydym yn ei wneud yn yr adran hon
wythnos - neu yn y broblem a osodwyd.
>> Felly, rydym yn mynd i orffen yr adran siarad am tablau hash.
Os ydych yn sylwi fy mod wedi gwneud ychydig o dabl hash.
Nid yw bod yr hyn yr ydym yn sôn am, fodd bynnag.
Yr ydym yn sôn am wahanol math o dablau hash.
Ac wrth ei graidd, tabl hash yn ddim mwy na
amrywiaeth yn ogystal â swyddogaeth hash.
Rydym yn mynd i siarad am ychydig yn unig i sicrhau bod pawb yn deall beth yw
swyddogaeth hash yn.
A dwi'n dweud wrthych yn awr ei fod yn dim mwy na dau beth -
yn swyddogaeth hash amrywiaeth a.
A dyma yw'r camau drwy mae hyn yn gweithredu.
>> Mae ein amrywiaeth.
Mae ein swyddogaeth.
Yn benodol, mae angen i swyddogaethau hash gwneud un neu ddau o bethau gyda hyn.
Rydw i'n mynd i siarad yn benodol am y broblem hon a osodwyd.
Yn ôl pob tebyg fod yn mynd i cymryd mewn llinyn.
A beth rwyt ti'n mynd i'w dychwelyd?
Pa fath data?
Alden?
Eich swyddogaeth hash dychwelyd?
Yn gyfanrif.
Felly, mae hyn yn yr hyn y mae'r hash tabl cynnwys -
tabl ar ffurf amrywiaeth a swyddogaeth hash.
Sut mae'n gweithio?
Mae'n gweithio mewn tri cham.
Rydym yn rhoi ei fod yn allweddol.
Yn yr achos hwn, byddwn yn rhoi ei fod yn llinyn.
Rydym yn galw y swyddogaeth hash fesul cam un ar yr allwedd ac rydym yn cael gwerth.
>> Yn benodol, byddwn yn dweud rydym yn cael yn gyfanrif.
Mae hynny'n cyfanrif, mae yn benodol iawn cyfyngiadau ar yr hyn y gellir cyfanrif fod.
Yn yr enghraifft hon, mae ein amrywiaeth o faint tri.
Felly, pa rifau y gellir cyfanrif fod.
Beth yw ystod o werthoedd dilys ar gyfer y cyfanrif, y math dychwelyd hwn
hash swyddogaeth?
Sero, un a dau.
Y pwynt y swyddogaeth hash yw chyfrif i maes y lle yn yr arae
lle mae ein allwedd yn mynd.
Dim ond tri bosibl lleoedd yma -
sero, un, neu ddau.
Felly, swyddogaeth hyn yn well dychwelyd sero, un, neu ddau.
Mae rhai indice dilys amrywiaeth hwn.
>> Ac yna yn dibynnu ar ble mae'n dychwelyd, gallwch weld yno amrywiaeth agored
braced gwerth.
Dyna lle rydym yn rhoi'r allweddol.
Felly rydym yn ei daflu yn y bwmpen, rydym yn mynd allan sero.
Ar braced array 0, rydym yn rhoi pwmpen.
Rydym yn taflu mewn cathod, rydym yn cael allan un.
Rydym yn rhoi cath yn un.
Rydym yn rhoi mewn pry cop.
Rydym yn cael dau.
Rydym yn rhoi pry cop yn y braced arae dau.
Byddai'n mor braf pe yn gweithio fel 'na.
Ond yn anffodus, fel y byddwn yn gweld, mae'n ychydig yn fwy cymhleth.
>> Cyn i ni fynd yno, unrhyw gwestiynau am hyn sylfaenol
sefydlu tabl hash?
Mae hyn yn ddelwedd yn union yr hyn yr ydym yn tynnu ar y bwrdd.
Ond ers i ni dynnu ar y bwrdd, yr wyf yn Nid wyf yn mynd i fynd i mewn iddo ymhellach.
Allweddi Yn y bôn, y blwch du hud - neu yn yr achos hwn, blwch corhwyaid - o
swyddogaeth hash yn eu rhoi mewn bwcedi.
Ac yn yr enghraifft hon rydym yn beidio â rhoi yr enw.
Rydym yn rhoi'r ffôn cysylltiedig nifer yr enw yn y bwced.
Ond fe allech chi yn dda iawn yn unig rhoi'r enw yn y bwced.
>> Mae hyn yn unig yw darlun o'r hyn rydym yn tynnu ar y bwrdd.
Mae gennym peryglon posibl, er.
Ac mae dau yn arbennig sleidiau fy mod eisiau mynd drosodd.
Mae'r un cyntaf yn ymwneud â swyddogaeth hash.
Felly gofynnais y cwestiwn, beth yn gwneud swyddogaeth hash da?
Yr wyf yn rhoi dau ateb.
Y cyntaf yw ei fod yn benderfynedig.
Yng nghyd-destun swyddogaethau hash, beth mae hyn yn ei olygu?
Ie?
>> GYNULLEIDFA: Gall dod o hyd i'r mynegai mewn amser yn gyson?
>> JASON Hirschhorn: Bod Nid yw yr hyn y mae'n ei olygu.
Ond mae hynny'n dyfalu da.
Unrhyw un arall yn cael dyfalu i beth mae hyn yn ei olygu?
Bod swyddogaeth hash da yn benderfynedig?
Annie?
>> GYNULLEIDFA: Bod gall allweddol yn unig eu mapio i un lle yn y tabl hash.
>> JASON Hirschhorn: Mae hynny'n yn union gywir.
Bob tro y byddwch yn rhoi mewn pwmpen, mae bob amser yn dychwelyd sero.
Os ydych yn rhoi mewn pwmpen a bod eich hash yn dychwelyd sero ond mae ganddo
tebygolrwydd o ddychwelyd rhywbeth arall yn fwy na sero -
felly efallai y gall ddychwelyd un weithiau neu ddau adegau eraill -
nid yw hynny'n swyddogaeth hash da.
Rydych chi'n union gywir.
Dylai eich swyddogaeth hash dychwelyd y yr un union cyfanrif, yn yr achos hwn, er
yr un peth union llinyn.
>> Efallai ei fod yn dychwelyd yr un peth union cyfanrif ar gyfer yr un union llinyn
waeth beth yw cyfalafu.
Ond yn yr achos hwnnw mae'n dal i fod penderfynedig fod pethau lluosog
eu mapio ar yr un gwerth.
Mae hynny'n iawn.
Cyn belled â bod un dim ond allbwn ar gyfer mewnbwn a roddir.
>> OK.
Yr ail beth yw ei fod yn dychwelyd mynegeion dilys.
Rydym yn dod i fyny hynny'n gynharach.
Mae'r swyddogaeth hash -
oh bachgen -
Dylai swyddogaeth hash dychwelyd mynegeion dilys.
Felly, yn dweud -
gadewch i ni fynd yn ôl at yr enghraifft hon.
Fy swyddogaeth hash yn cyfrif i fyny y llythrennau yn y gair.
Dyna swyddogaeth hash.
Ac yn dychwelyd y cyfanrif.
Felly os wyf yn cael y gair A, mae'n mynd i ddychwelyd un.
Ac mae'n mynd i roi Hawl yma.
Beth os byddaf yn ei roi yn y gair ystlumod?
Mae'n mynd i ddychwelyd tri.
Ble mae ystlumod yn mynd?
>> Nid yw'n addas.
Ond mae angen iddo fynd i rywle.
Mae hyn yn fy mwrdd hash wedi'r cyfan, a Mae angen popeth i fynd i rywle.
Felly, lle y dylai ystlumod fynd?
Unrhyw syniadau?
Dyfalu?
Dyfaliadau Da?
>> GYNULLEIDFA: Zero.
>> JASON Hirschhorn: Pam sero?
>> GYNULLEIDFA: Gan fod tri modwlo tri yn sero?
>> JASON Hirschhorn: Tri modwlo tri yw sero.
Mae hynny'n dyfalu mawr, ac mae hynny'n gywir.
Felly, yn yr achos hwn dylai yn ôl pob tebyg yn mynd ar sero.
Felly, yn ffordd dda o sicrhau bod y hash hwn swyddogaeth yn unig yn dychwelyd mynegeion dilys
i modwlo iddo gan faint y tabl.
Os ydych yn modwlo beth bynnag mae hyn yn dychwelyd gan tri, eich bod yn bob amser yn mynd i gael
rhywbeth rhwng sero, un, a dau.
Ac os yw hyn bob amser yn dychwelyd saith, a chi bob amser yn modwlo gan dri, rydych yn
bob amser yn mynd i gael yr un peth.
>> Felly, mae'n dal i fod penderfynedig os ydych yn modwlo.
Ond a fydd yn sicrhau eich bod yn byth yn cael rhywbeth -
diwydiant annilys.
Yn gyffredinol, dylai fod modwlo ddigwydd y tu mewn i'ch swyddogaeth hash.
Felly nid oes angen i chi boeni am hyn.
Gallwch dim ond sicrhau bod mae hwn yn indice dilys.
Unrhyw gwestiynau am hyn maen tramgwydd posibl?
>> OK.
Ac dyna ni.
Maen tramgwydd posibl nesaf, a mae hyn yn yr un mawr.
Beth os bydd map dau allweddi at yr un gwerth?
Felly, mae dwy ffordd o ymdrin â hyn.
Gelwir Mae'r un cyntaf wedi'i llinol stilio, ac rwy'n
ddim yn mynd i fynd dros.
Ond dylech fod yn gyfarwydd â sut sy'n gweithio a beth yw hynny.
>> Mae'r ail un yr wyf yn mynd i fynd dros oherwydd dyna yw'r un y mae llawer o
Mae'n debyg y bydd pobl yn y pen draw benderfynu i'w defnyddio yn eu set problem.
Wrth gwrs, nid oes rhaid i chi.
Ond ar gyfer y broblem a osodwyd, mae llawer o bobl yn tueddu i ddewis creu tabl hash
gyda gadwyno ar wahân i weithredu eu geiriadur.
Felly, rydym yn mynd i fynd dros yr hyn y mae'n ei olygu i greu tabl hash gyda
gadwyno ar wahân.
>> Felly, yr wyf yn rhoi pwmpen.
Mae'n dychwelyd sero.
Ac yr wyf yn rhoi pwmpen yma.
Yna, yr wyf yn rhoi i mewn -
beth sy'n beth arall Calan Gaeaf-thema?
>> GYNULLEIDFA: Candy.
>> JASON Hirschhorn: Candy!
Dyna un mawr.
Rwy'n rhoi mewn Candy, a candy hefyd yn rhoi sero mi.
Beth ddylwn i ei wneud?
Unrhyw syniadau?
Oherwydd chi i gyd math o yn gwybod pa gadwyno ar wahân.
Felly, unrhyw syniadau beth i'w wneud?
Yeah.
>> GYNULLEIDFA: Rhoi'r llinyn mewn gwirionedd yn y tabl hash.
>> JASON Hirschhorn: Felly, rydym yn mynd i tynnu syniad da dros yma.
OK.
>> GYNULLEIDFA: Cael y hashtable [Anghlywadwy]
y pwyntydd sy'n pwyntio at ddechrau rhestr.
Ac yna wedi pwmpen fydd gwerth cyntaf yn y rhestr a candy cysylltiedig yn
yr ail gwerth yn y rhestr gysylltiedig.
>> JASON Hirschhorn: OK.
Marcus, a oedd yn rhagorol.
Rydw i'n mynd i dorri'r hynny i lawr.
Marcus yn ei ddweud peidiwch â trosysgrifo pwmpen.
Byddai hynny'n ddrwg.
Peidiwch â rhoi Candy rhywle arall.
Rydym yn mynd i roi iddynt y ddau ar sero.
Ond rydym yn mynd i ddelio â eu rhoi ar sero gan
creu rhestr ar sero.
Ac rydym yn mynd i greu rhestr o popeth a mapio i sero.
A'r ffordd orau rydym yn dysgu i greu rhestr sy'n gallu tyfu ac yn crebachu
ddeinamig nid yw o fewn amrywiaeth arall.
Felly nid yw amrywiaeth aml-ddimensiwn.
Ond i ddim ond creu rhestr cysylltiedig.
>> Felly, yr hyn a gynigiwyd -
Rydw i'n mynd i gael newydd -
yn creu amrywiaeth gyda awgrymiadau, amrywiaeth o awgrymiadau.
OK.
Unrhyw syniad neu awgrym yr hyn y math Dylai hyn awgrymiadau fod?
Marcus?
>> GYNULLEIDFA: Awgrymiadau i -
>> JASON Hirschhorn: Oherwydd eich bod dywedodd rhestr gysylltiedig, felly -
>> GYNULLEIDFA: awgrymiadau Nôd?
>> JASON Hirschhorn: awgrymiadau Nôd.
Os yw'r bethau yn ein cysylltu rhestr yn nodau yna maent
Dylai fod yn ddangosyddion nod.
A beth maen nhw'n gyfartal i ddechrau?
>> GYNULLEIDFA: Null.
>> JASON Hirschhorn: Null.
Felly, mae ein beth wag.
Ffurflenni pwmpen sero.
Beth ydym ni'n ei wneud?
Mi gerdded drwyddo?
A dweud y gwir, Marcus eisoes roddodd i mi.
Rhywun arall yn cerdded i mi drwyddo.
Beth rydym yn ei wneud pan fyddwn yn -
hyn yn edrych yn debyg iawn i hyn yr oeddem yn dim ond gwneud.
Avi.
>> GYNULLEIDFA: Rydw i'n mynd i gymryd dyfalu.
Felly, pan fyddwch yn cael Candy.
>> JASON Hirschhorn: Yeah.
Wel, rydym yn cael pwmpen.
Gadewch i ni gael ein un cyntaf.
Rydym yn cael pwmpen.
>> GYNULLEIDFA: OK.
Ffurflenni pwmpen sero.
Felly rydych yn ei roi yn hynny.
Neu mewn gwirionedd, yr ydych yn ei roi yn y rhestr cysylltiedig.
>> JASON Hirschhorn: Sut ydym ni'n roi yn y rhestr gysylltiedig?
>> GYNULLEIDFA: O, mae'r gystrawen gwirioneddol?
>> JASON Hirschhorn: Dim ond cerdded -
dweud mwy.
Beth ydym ni'n ei wneud?
>> GYNULLEIDFA: Yr ydych rhowch fel y nod cyntaf.
>> JASON Hirschhorn: OK.
Felly, rydym wedi ein nod, pwmpen.
Ac yn awr sut ydw i'n mewnosod?
>> GYNULLEIDFA: Rydych yn neilltuo i'r pwyntydd.
>> JASON Hirschhorn: Pa pwyntydd?
>> GYNULLEIDFA: Y pwyntydd ar sero.
>> JASON Hirschhorn: Felly, lle yn gwneud y pwynt hwn?
>> GYNULLEIDFA: I null ar hyn o bryd.
>> JASON Hirschhorn: Wel, mae'n cyfeirio at null.
Ond dw i'n rhoi pwmpen.
Felly, lle y dylai bwyntio?
>> GYNULLEIDFA: I pwmpen.
>> JASON Hirschhorn: I pwmpen.
Yn union.
Felly, mae hyn yn cyfeirio at pwmpen.
A ble mae'r pwyntydd hwn ym mhwynt pwmpen?
I
>> GYNULLEIDFA: Null.
>> JASON Hirschhorn: I null.
Yn union.
Felly, rydym yn unig fewnosod rhywbeth i mewn i'r rhestr gysylltiedig.
Rydym newydd ei ysgrifennu y cod hwn i wneud hyn.
Mae bron rydym yn bron got it cracio yn gyfan gwbl.
Nawr rydym yn mewnosod Candy.
Mae ein Candy hefyd yn mynd i sero.
Felly, beth ydym yn ei wneud â Candy?
>> GYNULLEIDFA: Mae'n dibynnu ar p'un a nid ydym yn ceisio datrys hynny.
>> JASON Hirschhorn: Mae hynny'n yn union gywir.
Mae'n dibynnu ar p'un a yw rydym yn ceisio datrys hynny.
Gadewch i ni dybio nad ydym yn mynd i ddatrys y broblem.
>> GYNULLEIDFA: Wel, yna, fel y trafodwyd o'r blaen, mae'n symlaf dim ond i roi
i'r dde ar y dechrau felly mae'r pwyntydd o sero pwynt i Candy.
>> JASON Hirschhorn: OK.
Dal ar.
Gadewch i mi greu Candy hawl yma.
Felly pwyntydd hyn -
>> GYNULLEIDFA: Yeah, dylai bellach yn cael ei bwyntio at Candy.
Yna, rhaid i'r pwyntydd o pwynt Candy i pwmpen.
>> JASON Hirschhorn: Fel hynny?
A dweud rydym yn cael un arall beth i fapio i sero?
>> GYNULLEIDFA: Wel, 'ch jyst gwneud yr un peth?
>> JASON Hirschhorn: Gwnewch yr un peth.
Felly, yn yr achos hwn, os nad ydym yn ei wneud am ei gadw'n datrys ei
swnio braidd yn syml.
Rydym yn cymryd y pwyntydd yn y indice a roddir gan ein swyddogaeth hash.
Mae gennym y pwynt hwnnw at ein nod newydd.
Ac yna beth bynnag yr oedd yn pwyntio yn flaenorol -
yn yr null achos hwn, yn y ail pwmpen achos -
hynny, beth bynnag mae'n pwyntio at yn flaenorol, rydym yn ychwanegu i mewn i'r nesaf
ein nod newydd.
Rydym yn gosod rhywbeth yn y dechrau.
Mewn gwirionedd mae hyn yn llawer symlach na ceisio cadw'r rhestr didoli.
Ond unwaith eto, bydd chwilio fod yn gymhleth ar fwy yma.
Byddwn bob amser yn rhaid i ni fynd hyd y diwedd.
>> OK.
Unrhyw gwestiynau am gadwyno ar wahân?
Sut mae hynny'n gweithio?
Gofynnwch iddynt yn awr.
Rwy'n awyddus iawn i wneud yn siŵr bob un ohonoch deall hyn cyn i ni pen allan.
>> GYNULLEIDFA: Pam ydych yn ei roi pwmpen ac Candy i mewn i'r un
rhan o'r tabl hash?
>> JASON Hirschhorn: Cwestiwn da.
Pam rydym yn eu rhoi yn yr un rhan o'r tabl hash?
Wel, yn yr achos hwn ein swyddogaeth hash ffurflenni sero ar gyfer y ddau ohonynt.
Felly mae angen iddynt fynd ar sero indice oherwydd dyna lle'r ydym yn mynd i
chwilio amdanynt os ydym erioed am edrych i fyny.
Unwaith eto, gydag agwedd linellol treiddgar ni fyddem yn eu rhoi ar lefel sero.
Ond yn y dull gadwyn ar wahân, rydym yn mynd i roi nhw ar lefel sero
ac yna creu rhestr oddi ar sero.
>> Ac nid ydym am ysgrifennu dros pwmpen yn syml am hynny oherwydd wedyn byddwn ni
cymryd yn ganiataol bod pwmpen yn byth yn mewnosod.
Os ydym yn unig yn cadw un peth yn y lleoliad a fyddai'n ddrwg.
Yna, ni fyddai unrhyw cyfle ohonom erioed -
os ydym erioed wedi cael dyblyg, yna rydym yn fyddai dim ond dileu ein gwerth cychwynnol.
Felly dyna pam rydym yn gwneud y dull hwn.
Neu dyna pam rydym yn dewis - ond eto, yr ydym dewisodd y dull gadwyno ar wahân,
y mae llawer o ddulliau eraill gallai un ei ddewis.
A yw hynny'n ateb eich cwestiwn?
>> OK.
Carlos.
Byddai Llinellol treiddgar yn golygu -
os byddwn yn dod o hyd i gwrthdrawiad ar sero, rydym yn yn edrych yn y fan a'r lle nesaf i weld os
ei fod yn agored ac yn ei roi yno.
Ac yna rydym yn edrych yn y gamp nesaf ac weld a oedd yn agored a'i roi yno.
Felly, rydym yn dod o hyd i'r nesaf sydd ar gael fan a'r lle agored a'i roi yno.
Unrhyw gwestiynau eraill?
Yeah, Avi.
>> GYNULLEIDFA: Fel dilyniant i hynny, beth ydych chi'n ei olygu wrth fan a'r lle nesaf?
Yn y tabl hash neu mewn rhestr gysylltiedig.
>> JASON Hirschhorn: Ar gyfer llinol rhaglennu, dim rhestrau cysylltiedig.
Y fan a'r lle nesaf ar y bwrdd hash.
>> GYNULLEIDFA: OK.
Felly, byddai'r tabl hash yn ymgychwyn i faint -
fel y nifer o dannau eich bod yn mewnosod?
>> JASON Hirschhorn: Byddech am iddo fod yn fawr iawn.
Ie.
Dyma lun o'r hyn yr ydym dim ond tynnu ar y bwrdd.
Unwaith eto, mae gennym gwrthdrawiad yma.
ar 152.
A byddwch yn gweld ein creu rhestr cysylltiedig oddi ar hynny.
Unwaith eto, mae'r tabl hash gadwyno ar wahân Nid yw dull yw'r un rydych
rhaid iddynt gymryd ar gyfer problemau a osodwyd chwech ond yn un y mae llawer o
myfyrwyr yn tueddu i gymryd.
Felly, ar y nodyn hwnnw, gadewch i ni siarad yn fyr cyn i ni pen allan am broblem chwech,
ac yna byddaf yn rhannu stori gyda chi.
Mae gennym dri munud.
>> Problem gosod chwech.
Mae gennych pedair swyddogaeth -
llwyth, siec, maint, a dadlwytho.
Llwytho -
yn dda, rydym wedi bod yn mynd dros llwyth yn unig nawr.
Rydym yn tynnu llwyth ar y bwrdd.
Ac rydym hyd yn oed yn dechrau godio llawer o mewnosod i mewn i restr cysylltiedig.
Felly nid llwyth yn llawer mwy na hyn yr ydym wedi bod yn ei wneud yn unig.
>> Siec yn unwaith y byddwch wedi rhywbeth lwytho.
Mae yr un broses â hyn.
Mae'r un peth yn ddwy ran gyntaf lle rydych yn taflu rhywbeth yn y swyddogaeth hash
a chael ei werth.
Ond yn awr nid ydym yn ei roi i mewn.
Nawr rydym yn chwilio amdano.
Yr wyf wedi Cod sampl ysgrifenedig ar gyfer dod o hyd i rhywbeth mewn rhestr gysylltiedig.
Yr wyf yn eich annog i ymarfer hynny.
Ond yn reddfol dod o hyd i rhywbeth yn cael ei 'n bert debyg i fewnosod rhywbeth.
Yn wir, tynnwyd llun o ddod o hyd rhywbeth mewn rhestr gysylltiedig, gan symud
trwy nes i chi gyrraedd y diwedd.
Ac os ydych yn cael hyd y diwedd, ac ni allai yn ei chael yn, yna nid yw'n yno.
Felly dyna siec, yn y bôn.
>> Nesaf yw maint.
Gadewch i sgip maint.
Yn olaf, yr ydych wedi dadlwytho.
Dadlwytho yn un nad ydym wedi tynnu ar y bwrdd neu codio eto.
Ond yr wyf yn eich annog i roi cynnig codio ei yn ein sampl enghraifft rhestr gysylltiedig.
Ond dadlwytho reddfol yn debyg i rhad ac am ddim -
neu yr wyf yn golygu yn debyg i wirio.
Heblaw am hyn bob tro rydych chi'n mynd drwy, nad ydych yn unig gwirio i
weld a oes gennych eich gwerth chi yno.
Ond eich bod yn cymryd y nod a rhyddhau ei, yn y bôn.
Dyna beth dadlwytho yn gofyn i chi ei wneud.
Popeth am ddim i chi wedi malloced.
Felly, rydych yn mynd drwy'r rhestr gyfan unwaith eto, yn mynd drwy'r hash cyfan
tabl eto.
Nid yw'r amser yn gwirio i weld beth sydd yno.
Dim ond am ddim beth sydd yno.
>> Ac yn olaf maint.
Dylai maint yn cael ei rhoi ar waith.
Os nad ydych yn gweithredu maint -
'N annhymerus' yn dweud ei fod fel hyn.
Os nad ydych yn gweithredu maint yn yr union un llinell o god, gan gynnwys y
dychwelyd datganiad, yr ydych yn gwneud maint anghywir.
Felly gwnewch yn siwr faint, ar gyfer dylunio llawn pwyntiau, rydych chi'n ei wneud yn union yr un
llinell o god, gan gynnwys y datganiad dychwelyd.
>> Ac nid ydynt yn pecyn i fyny eto, Akchar.
Afanc Awyddus.
Roeddwn i eisiau dweud diolch guys am ddod i'r adran hon.
Cael Calan Gaeaf Hapus.
Mae hyn yn fy ngwisg.
Byddaf yn gwisgo hon ar ddydd Iau os wyf yn eich gweld yn ystod oriau swyddfa.
Ac os ydych yn chwilfrydig am rai mwy cefndir o ran gwisg hwn, yn teimlo
rhad ac am ddim i edrych ar adran 2011 am stori ar y rheswm pam rwy'n
gwisgo y wisg pwmpen.
Ac mae'n stori drist.
Felly, gwnewch yn siŵr eich bod wedi rhai meinweoedd cyfagos.
Ond ar hynny, os oes gennych unrhyw cwestiynau 'n annhymerus' ffon o gwmpas
y tu allan ar ôl adran hon.
Pob lwc ar y broblem a osodwyd chwech.
Ac fel bob amser, os oes gennych unrhyw cwestiynau, gadewch i mi wybod.