[CHWARAE CERDDORIAETH] 

Andi Peng: Croeso i wythnos 6 o adran. Rydym yn gwyro oddi wrth ein safon amser adran dydd Mawrth prynhawn i hyn fore Sul hyfryd. Diolch yn fawr i bawb sydd Ymunodd mi heddiw, ond o ddifrif, rownd o gymeradwyaeth. 

Dyna ymdrech eithaf mawr. Nid wyf bron yn ddim hyd yn oed yn ei gwneud yn i fyny mewn amser, ond Yr oedd yn iawn. Felly yr wyf yn gwybod bod pob un ohonoch newydd ei gwneud yn i'r cwis. Yn gyntaf oll, croeso i ar ochr arall hynny. 

Yn ail, byddwn yn siarad am y peth. Byddwn yn siarad am y cwis. Byddwn yn siarad am y ffordd rydych chi'n ei wneud yn y dosbarth. Byddwch yn iawn. Mae gen i eich cwisiau am chi ar ddiwedd y fan hon, felly os ydych chi guys eisiau cymryd a edrych arno, yn hollol iawn. 

Mor gyflym cyn i ni ddechrau, mae'r agenda ar gyfer heddiw yw fel a ganlyn. Fel y gwelwch, rydym yn tanio yn y bôn cyflym drwy criw cyfan o strwythurau data iawn, iawn, yn gyflym iawn. Felly, fel y cyfryw, ni fydd yn heddiw super rhyngweithiol. Fe 'i jyst yn fi fath o gweiddi pethau y byddwch chi, ac os wyf yn drysu chi, os ydw i'n mynd yn rhy gyflym, gadewch i mi wybod. Maen nhw jyst data amrywiol strwythurau, ac fel rhan eich pset ar gyfer hyn wythnos sydd i ddod, wnewch chi helpu gofynnir i weithredu un ohonynt, efallai dwy o them-- dau ohonynt yn eich pset. Iawn, felly Im 'jyst yn mynd i yn dechrau gyda rhai cyhoeddiadau. Byddwn yn mynd dros staciau ac ciwiau mwy mewn dyfnder na'r hyn a wnaethom cyn y cwis. Byddwn yn mynd dros cysylltiedig rhestru eto, unwaith eto, mwy o ddyfnder na'r hyn oedd gennym cyn y cwis. Ac yna byddwn yn siarad am hash tablau, coed a geisiau, a oedd yn i gyd yn eithaf angenrheidiol ar gyfer eich pset. Ac yna byddwn yn mynd dros rai awgrymiadau defnyddiol ar gyfer pset5. 

Iawn, felly cwis 0. Y cyfartaledd oedd 58%. Roedd yn isel iawn, ac er mwyn i chi guys i gyd Gwnaeth iawn, yn dda iawn yn unol â hynny. 

'N bert lawer, synnwyr y fawd yw os ydych yn o fewn gwyriad safonol o'r cymedr yn enwedig gan ein bod mewn llai adran cyffyrddus, rydych yn hollol iawn. Rydych chi ar y trywydd iawn. Mae bywyd yn dda. 

Dwi'n gwybod ei fod frawychus i feddwl y Ges fel 40% ar y cwis hwn. Rydw i'n mynd i fethu y dosbarth hwn. Yr wyf yn addo i chi, nad ydych chi'n mynd i fethu y dosbarth. Rydych yn hollol iawn. 

I'r rhai ohonoch a gafodd dros y cymedr, trawiadol, trawiadol, fel, wneud yn ddifrifol yn dda. Yr wyf yn eu cael gyda mi. Mae croeso i chi ddod eu cael ar ddiwedd yr adran hon. Gadewch i mi wybod os oes gennych unrhyw materion, cwestiynau gyda nhw. Os byddwn yn ychwanegu i fyny eich sgôr anghywir, rhowch wybod i ni. 

Iawn, felly pset5, mae hwn yn 'n sylweddol wythnos rhyfedd i Iâl yn yr ystyr bod ein pset yn ddyledus Dydd Mercher am hanner dydd, gan gynnwys ddiwedd y dydd, felly mae'n mewn gwirionedd ddamcaniaethol ddyledus Mawrth am hanner dydd. Mae'n debyg nad oes neb yn gorffen yn Mawrth am hanner dydd. Mae hynny'n hollol iawn. Rydym yn mynd i gael oriau swyddfa heno yn ogystal â nos Lun. A phob un o'r adrannau wythnos hon bydd mewn gwirionedd yn cael ei droi i mewn i weithdai, felly mae croeso i chi alw mewn unrhyw adran rydych eisiau, a byddant yn fath o mini-pset gweithdai am help ar hynny. Felly, fel y cyfryw, dyma'r unig adran lle'r ydym yn ddeunydd addysgu. Bydd yr holl adrannau eraill yn canolbwyntio yn gyfan gwbl ar gymorth ar gyfer y pset. Yeah? 

GYNULLEIDFA: Ble mae'r oriau swyddfa? 

Andi Peng: Oriau swyddfa tonight-- oh, cwestiwn da. Rwy'n credu oriau swyddfa heno yn Teal neu yn y Cyffredin. Os ydych yn gwirio CS50 ar-lein a'ch bod yn mynd i oriau swyddfa, dylid cael amserlen sy'n yn dweud wrthych ble pob un ohonynt yn cael eu. 

Yr wyf yn gwybod ai heno neu yfory yn corhwyaid, ac yr wyf yn meddwl efallai y byddwn yn cael tiroedd comin ar gyfer y noson o'r blaen. Dydw i ddim yn siwr. Cwestiwn da. Gwiriwch ar CS50. 

Cool, unrhyw gwestiynau ynghylch y amserlen ar gyfer y nesaf fel tri diwrnod? Rwy'n addo i chi guys fel David Meddai, dyma ben y bryn. Rydych guys yn cael eu bron yno. Dim ond tri diwrnod yn fwy. Gyrraedd yno, ac yna byddwn i gyd yn dod i lawr. Byddwn yn cael seibiant CS-rhad ac am ddim 'n glws. Byddwn yn dod yn ôl. Byddwn yn plymio i mewn i we rhaglennu a datblygu, pethau sy'n hwyl iawn o gymharu i rai o'r psets eraill. A bydd yn cael ei oeri, ac byddwn yn cael llawer o hwyl. Bydd gennym fwy o Candy. Mae'n ddrwg gennyf am candy. Wedi anghofio Candy. Roedd yn fore garw. Felly rydych guys yn cael eu bron yno, ac rwyf yn falch iawn ohonoch guys. 

Iawn, felly staciau. Pwy caru y cwestiwn am Jack ac mae ei ddillad ar y cwis? Neb? OK, mae hynny'n iawn. 

Felly, yn y bôn ag y gallwch llun Jack, y boi yma, wrth ei bodd yn cymryd y dillad allan o ben y pentwr, ac efe yn ei roi yn ôl ar y pentwr ar ôl iddo ei wneud. Felly, yn y modd hwn, byth ymddangos i fod yn mynd yn i waelod y stac yn ei ddillad. Felly, mae hyn yn disgrifio math o y strwythur data sylfaenol o sut y pentwr yn cael ei roi ar waith. 

Yn y bôn, meddyliwch am stac fel unrhyw pentwr o wrthrychau lle rydych yn rhoi pethau ar y top, a yna rydych yn eu pop allan o'r brig. Felly LIFO yw'r acronym rydym yn hoffi i use-- Yn diwethaf, Cyntaf Allan. Ac felly yn para mewn i frig y stac yw'r un cyntaf sy'n dod allan. Ac felly y ddau dymor rydym yn awyddus i gysylltu yn cael eu galw gwthio a pop gyda hynny. Pan fyddwch yn gwthio rhywbeth ar y stac, ac i chi pop yn ôl i fyny. 

Ac felly yr wyf yn dyfalu mae hwn yn fath o cysyniad haniaethol ar gyfer y rhai ohonoch sydd am weld fel gweithrediad gwirioneddol o hyn yn y byd go iawn. Faint ohonoch chi wedi ysgrifennu traethawd efallai fel awr cyn ei bod yn ddyledus, ac yr ydych yn ddamweiniol dileu enfawr talp ohono, fel ddamweiniol? Ac yna beth rheolaeth yn ei wneud a ddefnyddiwn i roi yn ôl? Rheoli-Z, ie? Rheoli-Z, felly faint o weithiau bod Control-Z wedi achub fy mywyd, wedi achub fy ass, bob tro sydd wedi ei weithredu drwy pentwr. 

Yn y bôn yr holl wybodaeth sydd ar eich dogfen Word, mae'n mynd gwthio a popped ar ewyllys. Ac felly y bôn pryd bynnag y byddwch dileu unrhyw beth, i chi pop yn ôl i fyny. Ac yna os ydych ei angen yn ôl ar, byddwch yn wthio, sef yr hyn Rheoli-C yn ei wneud. Ac swyddogaeth byd mor real o strwythur data pa mor syml Gall helpu gyda'ch bywyd bob dydd. 

Felly mae struct yw'r ffordd y rydym mewn gwirionedd yn creu pentwr. Rydym yn teipio diffinio struct, ac yna rydym yn galw ei fod yn dal dŵr ar y gwaelod. Ac o fewn y pentwr, mae gennym ddau paramedrau y gallwn ei hanfod drin, felly rydym wedi gallu llinynnau seren char. 

Y cyfan y mae'n ei wneud yn creu amrywiaeth ein bod yn gallu storio beth bynnag y dymunwch y gallwn benderfynu ar ei allu. Gallu Ai dim ond y swm max o eitemau y gallwn roi mewn amrywiaeth hwn. maint int yw'r cownter sy'n cadw golwg ar faint o eitemau ar hyn o bryd yn y pentwr. Felly, yna gallwn gadw golwg ar, A, y ddau pa mor fawr y pentwr gwir yw, a, B, faint o'r pentwr rydym yn llenwi oherwydd nad ydym am i orlifo dros yr hyn yw ein gallu. 

Felly, er enghraifft, mae hyn yn hyfryd cwestiwn oedd ar eich cwis. Yn y bôn sut ydyn ni'n gwthio ar ben y pentwr. Pretty syml. Os ydych yn edrych arno, byddwn yn cerdded trwy hyn. Os [Anghlywadwy] size-- cofiwch, pryd bynnag y byddwch am gael mynediad i unrhyw paramedr fewn struct, byddwch yn gwneud enw'r struct.parameter. 

Yn yr achos hwn, s enw ein corn. Rydym yn awyddus i gael gafael ar y maint ohono, felly rydym yn ei wneud s.size. Felly, ar yr amod nad yw maint yw gyfartal i allu neu ar yr amod gan ei fod yn llai na gallu, naill ai y byddai'n gweithio yma. 

Rydych am gael mynediad i'r tu mewn eich simnai, felly s.strings, ac rydych yn mynd i roi y rhif newydd eich bod am i fewnosod i mewn yno. Gadewch i 'jyst dweud byddwn am mewnosod int n ar y pentwr, gallem ei wneud s.strings, cromfachau, s.size hafal n. Oherwydd bod maint yw lle rydym ar hyn o bryd yn y pentwr os ydym yn mynd i wthio ymlaen, rydym yn unig gael mynediad lle bynnag y mae maint yw, y llawnder presennol y pentwr, ac yr ydym yn gwthio'r int n arno. Ac yna rydym am wneud yn siŵr bod rydym hefyd yn incrementing maint y n, fel y gallwn gadw golwg rydym wedi Ychwanegodd beth ychwanegol i'r pentwr. Nawr rydym yn cael mwy o faint. Ydy hyn yn gwneud synnwyr yma i pawb, pa mor rhesymegol mae'n gweithio? Roedd yn fath o gyflym. GYNULLEIDFA: Allwch chi fynd dros y s.stringss.strings [s.size] eto? Andi Peng: Cadarn, felly beth sydd s.size ar hyn o bryd yn rhoi i ni? GYNULLEIDFA: Mae'n y maint presennol. Andi Peng: Yn union, felly mae'r mynegai ar hyn o bryd y mae ein maint ar, ac felly yr ydym am roi'r cyfanrif newydd ein bod am i fewnosod i mewn i s.size. A yw hynny'n gwneud synnwyr? Gan fod s.strings, y cyfan sydd yw yw enw'r y rhesi. Mae'r holl mae'n ei cael mynediad i'r amrywiaeth o fewn ein struct, ac felly os ydym eisiau rhowch n i mewn i'r mynegai, gallwn jyst gael mynediad iddo gan ddefnyddio cromfachau s.size. Cool. 

Mae pob hawl, pop, yr wyf yn pseudocode 'ii maes i chi guys, ond cysyniad tebyg. A yw hynny'n gwneud synnwyr? Os yw maint yn fwy na sero, yna rydych yn gwybod eich bod am gymryd rhywbeth allan oherwydd os nad yw maint yw mwy na sero, yna rydych ganddynt unrhyw beth yn y pentwr. 

Felly dim ond eisiau gweithredu cod hwn, y gall dim ond pop os oes rhywbeth i pop. Felly, os yw maint yn fwy na 0, rydym minws maint. Rydym yn lleihau a maint ac yna dychwelyd beth bynnag sydd tu mewn iddo oherwydd drwy popping, rydym am mynediad beth bynnag yn cael ei storio yn y mynegai ben y pentwr. Mae popeth yn gwneud synnwyr? Os byddaf yn gwneud i chi guys ysgrifennu hyn allan, fyddech chi guys yn gallu ysgrifennu allan? OK, gallwch chi guys chwarae o gwmpas ag ef. Dim pryderon os nad ydych yn ei gael. Nid oes gennym amser i cod allan heddiw oherwydd rydym wedi cael llawer o strwythurau hyn i fynd drwy'r, ond yn ei hanfod pseudocode, iawn, yn debyg iawn i wthio. Dilynwch ar hyd y rhesymeg. Gwnewch yn siŵr eich bod yn cael mynediad at yr holl nodweddion eich struct yn gywir. Yeah? 

GYNULLEIDFA: A wnaiff y sleidiau hyn a mae hyn holl beth fod hyd heddiw-ish? Andi Peng: Bob amser, yep. Rydw i'n mynd i geisio rhoi hyn i fyny fel awr ar ôl. 'N annhymerus' anfon e-bost David, bydd David yn ceisio ei roi i fyny fel awr ar ôl hyn. 

Iawn, felly yna rydym yn symud i mewn i hyn eraill strwythur data hyfryd o'r enw ciw. Fel y gallwch weld guys yma, mae ciw, ar gyfer y British yn ein plith, i gyd mae'n llinell. Felly, yn groes i'r hyn yn eich barn chi pentwr yw, ciw yn union yr hyn yn rhesymegol credwch ei fod yn. Mae'n cael ei dal gan y rheolau FIFO, sef First Mewn, Cyntaf Allan. Os mai chi yw'r cyntaf un yn y llinell, rydych yn yr un cyntaf i yn dod allan y llinell. 

Felly, yr hyn yr ydym yn hoffi i alw hyn yn dequeueing a enqueueing. Os ydym am ychwanegu rhywbeth at ein ciw, rydym yn enqueue. Os ydym am dequeue, neu gymryd rhywbeth i ffwrdd, rydym yn dequeue. 

Felly un synnwyr ein bod fath o creu elfennau-maint sefydlog yr ydym Gall storio penodol pethau, ond allwn hefyd newid lle'r ydym yn gosod paramedrau y tu mewn ohonynt yn seiliedig ar y math o functionality yr ydym ei eisiau. Felly staciau, roeddem am yr olaf un, N i fod yr un allan gyntaf. Ciw yw ein bod am y peth cyntaf yn i fod y peth cyntaf allan. 

Felly mae'r struct-math ddiffinio, fel y gwelwch, mae'n ychydig yn wahanol o'r hyn y mae'r pentwr oedd oherwydd nid yn unig y mae yn rhaid i ni gadw trac o gyflwr lle mae'r maint ar hyn o bryd yw, rydym hefyd yn awyddus i gadw golwg ar y pen yn ogystal â lle yr ydym ar hyn o bryd yn cael eu. Felly yr wyf yn credu ei fod yn haws os wyf yn tynnu hyn i fyny. Felly gadewch i ni ddychmygu mae gennym ciw, felly gadewch i ni ddweud y pen yn iawn yma. Mae pennaeth y llinell, gadewch i ni dim ond dweud dyna bryd yno, ac rydym am i fewnosod rhywbeth i mewn i'r ciw. Rydw i'n mynd i alw maint y bôn yr un peth â gynffon, diwedd lle bynnag y bo eich ciw yw. Gadewch i 'jyst dweud faint yn iawn yma. 

Felly sut mae un yn ymarferol mewnosod rhywbeth i mewn ciw? Pa mynegai ydym ni eisiau gosod lle yr ydym am i fewnosod i mewn. Os yw hyn yn ddechrau eich ciw ac mae hyn yn y diwedd neu faint ohono, lle yr ydym yn eisiau ychwanegu y gwrthrych nesaf? 

GYNULLEIDFA: [Anghlywadwy] Andi Peng: Yn union, ydych am ychwanegu mae'n dibynnu ar a ydych wedi ei ysgrifennu. Naill ai mae hyn yn wag, neu fod yn wag. Felly rydych eisiau ei ychwanegu yn ôl pob tebyg yma oherwydd os bydd y maint yw-- os yw'r rhain i gyd yn llawn, yr ydych am ychwanegu yn iawn yma, dde? 

Ac felly dyna, tra iawn, iawn syml, ddim yn hollol bob amser yn gywir oherwydd bod y prif wahaniaeth rhwng ciw a stac yw y gall y ciw mewn gwirionedd yn cael eu trin fel bod y pen newidiadau yn dibynnu ar ble rydych am ddechrau eich ciw i ddechrau. Ac o ganlyniad, bydd eich cynffon hefyd yn mynd i newid. Ac felly cymerwch olwg ar cod hwn ar hyn o bryd. Fel gofynnwyd i chi guys hefyd i ysgrifennu ar y cwis, enqueue. Efallai byddwn yn siarad drwy pam yr ateb oedd yr hyn yr oedd. 

Allwn i ddim eithaf ffitio llinell hon ar un, ond yn ei hanfod darn hwn o god Dylai fod ar un llinell. Gwario fel 30 eiliad. Cymerwch olwg, ac yn gweld pam mae hyn yw'r ffordd y mae. 

Iawn, struct debyg iawn, iawn, iawn strwythur tebyg i'r blaenorol pentwr yma ond efallai un llinell o god. A bod un llinell o god penderfynu ar y swyddogaeth. Ac mae'n wir yn gwahaniaethu ciw o bentwr. 

Dylai unrhyw un eisiau cymryd drywanu yn egluro pam eich bod wedi got hyn beth cymhleth yn fan hyn? Rydym yn gweld dychweliad ein ffrind modwlws gwych. Fel y byddwch yn guys yn fuan yn dod i gydnabod mewn rhaglenni, bron unrhyw adeg rydych angen rhywbeth i lapio o gwmpas unrhyw beth, modwlws yn mynd i fod ar y ffordd i wneud hynny. Felly gan wybod bod, oes rhywun eisiau i roi cynnig ar egluro bod llinell o god? Yeah, pob atebion yn derbyniol a chroeso. GYNULLEIDFA: A ydych yn siarad â mi? Andi Peng: Yeah. GYNULLEIDFA: O, na sori. Andi Peng: OK, felly gadewch i ni cerdded drwy y cod hwn. Felly, pan fyddwch yn ceisio ychwanegu rhywbeth ar ciw, yn yr achos hyfryd bod y pen yn digwydd i fod yn iawn yma, mae'n hawdd iawn i ni i jyst yn mynd i ben mewnosod rhywbeth, dde? Ond holl bwynt ciw yw bod y pennaeth yn gallu mewn gwirionedd yn ddynamig newid yn dibynnu ar lle rydym eisiau dechrau ein q i fod, ac fel y cyfryw, y gynffon hefyd yn mynd i newid. 

Ac felly dychmygwch nad oedd y oedd hyn yn ciw, ond yn hytrach hwn oedd y ciw. Lets 'ddeud y pen yn iawn yma. Lets 'ddeud ein ciw yn edrych fel hyn. Os ydym yn awyddus i symud lle cychwyn y llinell yw, gadewch i ni ddweud ein bod yn symud pen y ffordd hon a maint yma. 

Nawr rydym am i ychwanegu rhywbeth at ciw hwn, ond fel y gallwch weld guys, nid yw mor syml ag i ychydig ychwanegu beth bynnag sydd ar ôl y maint oherwydd wedyn rydym yn rhedeg allan o terfynau ein amrywiaeth gwirioneddol. Ble rydym ni eisiau mewn gwirionedd ychwanegu yma. Dyna harddwch ciw yw hynny i ni, yn weledol iddo edrych fel y llinell yn mynd fel hyn, ond pan storio mewn strwythur data, maent yn rhoi fel fel cylch. Mae'n fath o lapio o gwmpas i flaen yr un ffordd y gall llinell hefyd lapio o gwmpas yn dibynnu ar ble bynnag yr ydych eisiau gychwyn y llinell i fod. Ac felly os ydym yn cymryd edrych i lawr yma, gadewch i ni dweud ein bod eisiau creu swyddogaeth a elwir yn enqueue. Roeddem yn awyddus i ychwanegu int n i mewn i'r q. Os q.size q-- byddwn yn galw bod ein data structure-- os nad yw ein queue.size yn gyfartal i allu neu os mae'n llai na gallu, q.strings yn yr amrywiaeth o fewn ein q. Rydym yn mynd i osod hynny hafal i q.heads, sydd yn iawn yma, yn ogystal â q.size modwlws gan y gallu, a oedd yn lapio ni yn ôl o gwmpas yma. 

Felly, yn yr enghraifft hon, mynegai o pen yn 1, dde? Mae'r mynegai o faint yn 0, 1, 2, 3, 4. Felly, gallwn wneud 1 ynghyd â 4 modwlws gan ein capasiti sydd 5. Beth mae hynny'n ei roi i ni? Beth yw'r mynegai sy'n yn dod allan o hyn? 

GYNULLEIDFA: 0. 

Andi Peng: 0, a oedd yn digwydd bod yn iawn yma, ac felly yr ydym am fod yn gallu i fewnosod i mewn i dde yma. Ac felly hafaliad hwn yma garedig o jyst yn gweithio gydag unrhyw rifau gan ddibynnu ar ble mae eich pen a'ch maint yn cael eu. Os ydych yn gwybod beth y rhai pethau, eich bod yn gwybod yn union ble yr hoffech ei fewnosod beth bynnag sydd ar ôl eich ciw. A yw hynny'n gwneud synnwyr i bawb? 

Yr wyf yn gwybod fath o ymennydd teaser yn enwedig gan fod hwn Daeth yn dilyn eich cwis. Ond gobeithio pawb yn awr yn gallu deall pam ateb hwn neu hon swyddogaeth yw'r ffordd y mae. Dylai unrhyw un ychydig yn aneglur ar hynny? IAWN. 

Ac felly yn awr, os ydych yn awyddus i dequeue, mae hyn yn yw lle y byddai ein pen yn symud oherwydd pe baem yn dequeue, nid ydym yn cymryd oddi ar ddiwedd y q. Rydym yn awyddus i gymryd oddi ar y pen, dde? Felly, o ganlyniad, pen yn mynd i newid, a dyna pam pan fyddwch yn enqueue, mae'n rhaid i chi gadw golwg ar lle eich pen a'ch maint yn mynd i fod yn gallu mewnosod i mewn i'r safle cywir. 

Ac felly pan fyddwch yn dequeue, Rwyf hefyd yn pseudocode 'ii maes. Mae croeso i chi os ydych am i geisio codio hyn allan. Rydych chi eisiau symud y pen, dde? Os Roeddwn i eisiau dequeue, yr wyf yn Byddai symud y pen drosodd. Byddai hyn yn y pen. 

A byddai ein maint presennol tynnu oherwydd ein bod bellach yn cael pedair elfen yn y rhesi. Dim ond tri, ac yna rydym eisiau i ddychwelyd beth bynnag ei ​​storio y tu mewn y pen gan ein bod am gymryd hyn Gwerth allan mor debyg iawn i'r pentwr. Dim ond eich bod yn cymryd o le gwahanol, a rhaid i chi ail-neilltuo i'ch pwyntydd i le gwahanol o ganlyniad. Yn rhesymegol, pawb ddilyn? Great. 

Iawn, felly rydym yn mynd i siarad ychydig fwy manwl am restrau cysylltiedig oherwydd fe wna nhw fod yn iawn, yn werthfawr iawn ar eich cyfer yn ystod yr wythnos hon yn psets. Rhestrau cysylltiedig, wrth i chi guys gallu cofio, pob eu bod yn yn nodau sy'n cael eu nodau penodol gwerthoedd y ddau gwerth a pwyntydd sydd wedi eu cysylltu â'i gilydd gan awgrymiadau hynny. Ac felly y struct ar sut rydym yn creu nod yma yw ein bod cael int n, sydd yn beth bynnag gwerth mewn siop neu linyn n neu beth bynnag yr ydych eisiau ei alw, y seren torgoch n. Seren nôd Struct, sef y pwyntydd eich bod am gael ym mhob nod, ydych yn mynd i gael y pwynt pwyntydd tuag nesaf. Byddwch yn cael y pen o restr cysylltiedig sy'n mynd i bwyntio at weddill gwerthoedd yn y blaen ac yn y blaen hyd nes y byddwch yn y pen draw yn cyrraedd y diwedd. Ac mae hyn nod olaf yn unig mynd i oes rhaid pwyntydd. Mae'n mynd i bwyntio at null, a dyna pryd eich bod yn gwybod eich bod wedi cyrraedd y diwedd eich rhestr cysylltiedig yw pan fydd eich pwyntydd ddiwethaf nid yw'n cyfeirio at unrhyw beth. 

Felly rydym yn mynd i fynd ychydig yn fwy mewn ddyfnder ynglŷn â sut y byddai un o bosibl chwilio rhestr cysylltiedig. Cofiwch yr hyn yw rhai o'r anfanteision y rhestrau cysylltiedig penillion amrywiaeth o ran chwiliadau. Amrywiaeth gallwch chwilio deuaidd, ond pam na allwch chi wneud hynny mewn rhestr cysylltiedig? 

GYNULLEIDFA: Oherwydd eu bod i gyd yn gysylltiedig, ond nid ydych yn hollol yn gwybod ble [Anghlywadwy]. 

Andi Peng: Yeah, yn union felly cofiwch bod y disgleirdeb amrywiaeth oedd y ffaith ein bod wedi cael cof hapgyrch lle os oeddwn i eisiau i'r gwerth o fynegai chwech, gallwn i jyst ddweud mynegai chwech, rhoi'r gwerth mi. Ac mae hynny oherwydd araeau yn cael eu datrys mewn gofod cydgyffwrdd o gof mewn un lle, tra bod fath o restrau cysylltiedig yn frith ar hap o gwmpas, a'r unig ffordd y gallwch ddod o hyd i un yw drwy pwyntydd sy'n dweud wrthych cyfeiriad y lle y nod nesaf yw. 

Ac felly, o ganlyniad, yr unig ffordd i chwilio drwy restr cysylltiedig yn chwilio llinol. Gan nad wyf yn gwybod yn union lle mae'r gwerth 12fed yn y rhestr cysylltiedig yw, Mae'n rhaid i mi groesi'r chyfanrwydd o'r rhestr honno un cysylltiedig gan un o'r pen i'r nod cyntaf, at yr ail nod, i'r trydydd nod, holl ffordd i lawr nes i mi o'r diwedd yn cael i ble y nod dwi'n chwilio amdano yw. Ac felly yn yr ystyr hwn, chwilio ar restr cysylltiedig yw n bob amser. Mae'n n bob amser. Mae bob amser mewn amser llinol. 

Ac felly y cod lle yr ydym yn gweithredu hyn, ac mae hyn yn ychydig yn newydd i chi guys ers i chi Nid yw guys wedi siarad mewn gwirionedd am neu erioed awgrymiadau a welir yn sut i chwilio drwy awgrymiadau, felly byddwn yn cerdded trwy mae hyn iawn, yn araf iawn. Felly Chwilio bool, ar y dde, gadewch i ni ddychmygu rydym am i greu swyddogaeth o'r enw chwilio sy'n dychwelyd gwir os ydych yn dod o hyd i werth y tu mewn i'r cysylltiedig rhestru, ac mae'n dychwelyd ffug fel arall. Rhestr seren nôd yn Ar hyn o bryd dim ond y pwyntydd at yr eitem gyntaf yn eich rhestr cysylltiedig. int n yw'r gwerth eich bod yn chwilio am yn y rhestr honno. 

Felly pwyntydd seren nôd hafal rhestr. Mae hynny'n golygu ein bod yn pennu a chreu pwyntydd at y nod cyntaf tu mewn i'r rhestr. Mae pawb gyda mi? Felly, pe baem yn mynd yn yn ôl yma, byddai gennyf ymgychwyn pwyntydd sy'n cyfeirio at y pennaeth beth bynnag y rhestr yn. 

Ac yna ar ôl i chi fynd i lawr fan hyn, er nad pwyntydd yn null cyfartal, felly mae hynny'n ddolen yr ydym yn mynd i fod wedyn yn croesi'r gweddill ein rhestr oherwydd mae'r hyn yn digwydd pan fydd pwyntydd hafal null? Rydym yn gwybod ein bod yn have-- 

GYNULLEIDFA: [Anghlywadwy] 

Andi Peng: Yn union, felly rydym yn gwybod bod rydym wedi dod i ddiwedd rhestr, dde? Os byddwch yn mynd yn ôl yma, mae pob nod Dylid pwyntio at nod arall ac yn y blaen ac yn y blaen hyd nes y byddwch yn taro yn y pen draw y gynffon eich rhestr cysylltiedig, sydd â pwyntydd mai dim ond Nid yw pwyntio yn unrhyw le heblaw dim. Ac felly eich bod yn gwybod bod y bôn eich rhestr mae dal i fyny hyd nes y pwyntydd nid yw'n gyfartal null oherwydd unwaith y bydd hafal null, eich bod yn gwybod nad oes dim mwy o stwff. 

Felly dyna'r ddolen yr ydym ni'n mynd i gael y chwiliad gwirioneddol. Ac os y pointer-- ydych chi'n gweld y math hwnnw o swyddogaeth saeth yno? Felly, os bwyntiau pwyntydd i n, os pwyntydd yn n hafal hafal n, fel eu bod yn golygu os pwyntydd eich bod yn chwilio am ar ddiwedd pob nod mewn gwirionedd cyfateb i werth ydych yn chwilio amdano, yna ydych am ddychwelyd wir. Felly y bôn, os ydych yn nod sy'n Mae gan y gwerth y rydych yn chwilio amdano, eich bod yn gwybod eich bod wedi bod gallu chwilio yn llwyddiannus. 

Fel arall, yr ydych am osod eich pwyntydd i'r nod nesaf. Dyna beth y llinell yma yn ei wneud. Pointer hafal pwyntydd nesaf. Mae pawb yn gweld sut mae hynny'n gweithio? 

Ac yn ei hanfod ydych yn mynd i jyst groesi'r gyfanrwydd y rhestr, ailosod eich pwyntydd bob tro hyd nes chi yn y pen draw yn cyrraedd y diwedd y rhestr. A ydych yn gwybod nad oes unrhyw mwy o nodau i chwilio drwy, ac yna gallwch ddychwelyd ffug oherwydd eich bod yn gwybod bod, oh, wel, os ydw i wedi llwyddo i chwilio drwy gydol y rhestr. Os yn yr enghraifft hon, os oeddwn i eisiau i chwilio am werth o 10, ac yr wyf yn dechrau yn y pen, ac Rwy'n chwilio holl ffordd i lawr, ac yr wyf yn y pen draw rhaid i hwn, sy'n pwyntydd sy'n pwyntio at null, Gwn fod, sothach, yr wyf yn dyfalu 10 Nid yw mewn rhestr hon oherwydd ni allwn ddod o hyd iddo. A dwi'n ar ddiwedd y rhestr. Ac yn yr achos eich bod yn gwybod Rydw i'n mynd i ddychwelyd ffug. 

Gadewch bod socian mewn am ychydig bach. Bydd hyn yn 'n bert pwysig ar gyfer eich pset. Mae rhesymeg mae'n syml iawn, efallai syntactically jyst roi ar waith. Rydych guys am wneud yn siŵr eich bod yn deall. Cool. 

Iawn, felly sut y byddem yn mewnosod nodau, ar y dde, i mewn i rhestr oherwydd cofio beth yw beth am y budd-daliadau o gael rhestr gysylltiedig yn erbyn amrywiaeth o ran storio? 

GYNULLEIDFA: Mae'n ddeinamig, felly mae'n haws i'r canlynol-- 

Andi Peng: Yn union, felly mae'n deinamig, sy'n yn golygu ei fod yn gallu ehangu a crebachu yn dibynnu ar anghenion y defnyddiwr. Ac felly, yn yr ystyr hwn, nid oes angen i ni i wastraff cof diangen oherwydd fy mod yn os nad wyf yn gwybod faint o werthoedd yr wyf am i storio, nid yw'n gwneud synnwyr i mi i greu amrywiaeth oherwydd os wyf am i storio 10 o werthoedd ac yr wyf yn creu amrywiaeth o 1,000, dyna llawer o wastraffu cof, penodedig. Dyna pam ein bod am ddefnyddio cysylltiedig rhestr i allu ddeinamig newid neu crebachu ein maint. 

Ac felly sy'n gwneud mewnosod ychydig yn fwy cymhleth. Gan na allwn gael mynediad elfennau ar hap y modd y byddem yn o amrywiaeth. Os ydw i eisiau i fewnosod elfen i mewn i'r seithfed fynegai, Gallaf jyst rhowch ei i mewn i'r seithfed mynegai. Ar restr cysylltiedig, nid yw'n gwneud eithaf yn gweithio mor hawdd, ac felly os oeddem am i fewnosod yr un yma yn y rhestr cysylltiedig, ar eu golwg, mae'n hawdd iawn i'w weld. Rydym yn unig yn awyddus i fewnosod pethau'n iawn yno, i'r dde ar ddechrau'r rhestr, dde ar ôl pen. 

Ond mae'r ffordd y mae'n rhaid i ni ail-neilltuo mae'r arwyddion yn ychydig yn ddryslyd fel neu, yn rhesymegol, mae'n gwneud synnwyr, ond ydych am wneud yn siŵr eich bod wedi ei yn gyfan gwbl i lawr oherwydd y peth olaf rydych am yw ail-neilltuo pwyntydd y ffordd yr ydym yn ei wneud yma. Os ydych dereference y Pointer o ben i 1, yna yn yr sydyn weddill eich rhestr cysylltiedig cael ei golli oherwydd bod gennych beidio mewn gwirionedd creu unrhyw beth dros dro. Mae hynny wedi tynnu sylw at y 2. Os ydych yn ail-neilltuo pwyntydd, yna bydd y weddill eich rhestr yn cael ei golli yn llwyr. Felly rydych eisiau bod iawn, yn ofalus iawn yma i neilltuo gyntaf y pwyntydd o beth bynnag yr ydych eisiau i fewnosod i mewn i lle bynnag y bo rydych eisiau, ac yna rydych gall dereference weddill eich rhestr. 

Felly, mae hyn yn gwneud cais am ble bynnag ydych yn ceisio ei fewnosod i mewn. Os ydych am i fewnosod yn y ben, os ydych am ei ateb yma, os ydych am mewnosoder ar y diwedd, yn dda, diwedd yr wyf yn dyfalu y byddech yn unig yn cael unrhyw pwyntydd, ond rydych yn eisiau gwneud yn siŵr nad ydych yn ei wneud colli gweddill eich rhestr. Rydych chi bob amser yn awyddus i wneud yn siŵr eich nod newydd yn pwyntio tuag at beth bynnag yr ydych eisiau i fewnosod i mewn i, ac yna gallwch ychwanegu'r gadwyno ymlaen. Mae pawb yn glir? 

Mae hyn yn mynd i fod un o'r materion go iawn. Un o'r rhan fwyaf o faterion o bwys rydych yn mynd i gael ar eich pset yw eich bod yn mynd i geisio creu rhestr cysylltiedig a phethau mewnosoder ond yna dim ond yn colli'r weddill eich rhestr cysylltiedig. A ydych yn mynd i fod fel, yr wyf yn ddim yn gwybod pam fod hyn yn digwydd? Ac mae'n boen i fynd drwy'r a chwilio pob un o'ch awgrymiadau. 

Ac yr wyf yn eich sicrhau ar pset hwn, ysgrifennu a thynnu nodau hyn allan yn iawn, yn ddefnyddiol iawn. Fel y gallwch llwyr gadw golwg o ble mae eich holl awgrymiadau chi, beth sy'n mynd o'i le, lle mae eich holl nodau chi, beth sydd angen i chi ei wneud i gael mynediad neu mewnosod neu ddileu neu unrhyw un ohonynt. Mae pawb yn dda â hynny? Cool. 

Felly, os ydym am edrych ar y cod? O, nid wyf yn gwybod a ydym Gall weld the-- Iawn, felly ar y brig i gyd, mae'n yn swyddogaeth mewnosod a enwir lle rydym eisiau i fewnosod int n i mewn i'r rhestr cysylltiedig. Rydym yn mynd i gerdded drwy'r hyn. Mae'n llawer o god, mae llawer o gystrawennau newydd. Byddwn yn iawn. 

Felly, i fyny ar y brig, pryd bynnag y rydym eisiau creu unrhyw beth beth sydd angen i ni ei wneud, yn enwedig os ydych am iddo beidio cael ei storio ar y pentwr ond yn y domen? Rydym yn mynd i malloc, dde? Felly rydym yn mynd i greu pwyntydd. Nôd, pwyntydd, gyfartal newydd malloc yr un maint â nôd oherwydd yr ydym am y nod i gael eu creu. Rydym am faint o cof bod nod yn cymryd i fyny i gael eu glustnodwyd ar gyfer y creu y nôd newydd. 

Ac yna rydym yn mynd i edrych i weld os hafal newydd yn hafal null. Cofiwch yr hyn a ddywedodd yr ydym? Beth bynnag y byddwch malloc, yr hyn y mae'n rhaid i chi bob amser yn ei wneud? Rhaid i chi bob amser yn edrych i weld a yw hynny'n null. 

Er enghraifft, os yw eich gweithredu system yn hollol lawn, os oedd gennych ddim mwy gof yn i gyd ac ydych yn ceisio malloc, byddai'n dychwelyd null i chi. Ac felly os ydych yn ceisio ei ddefnyddio pan oedd yn pwyntio at null, Nid ydych yn mynd i allu i gael gafael ar y wybodaeth honno. Ac felly fel y cyfryw, roeddem am wneud yn siwr bod pryd bynnag y byddwch chi'n mallocing, eich bod bob amser yn edrych i weld a oes y gof a roddwyd i chi yn null. Ac os nad yw'n, yna gallwn symud ymlaen gyda gweddill ein cod. 

Felly rydym yn mynd i ymgychwyn y nôd newydd. Rydym yn mynd i wneud n newydd hafal n. Ac yna rydym yn mynd i wneud gosod newydd y pwyntydd ar newydd i null oherwydd ar hyn o bryd nid ydym yn ei wneud eisiau dim byd iddo cyfeirio at. Nid oes gennym unrhyw syniad lle mae'n mynd i roi i chi, ac yna os ydym eisiau mewnosoder hynny ar y pen, yna gallwn ail-neilltuo pwyntydd i'r pen. Ydy pawb yn dilyn y rhesymeg o gyflwr lle mae hynny'n digwydd? 

Y cyfan yr ydym yn ei wneud yn creu newydd nod, gan osod y pwyntydd i null, ac yna ailgyfeirio i'r pen os ydym yn gwybod ein bod am i fewnosod hynny ar y pen. Ac yna y pennaeth yn mynd i pwyntio tuag at y nod newydd. Mae pawb yn iawn gyda hynny? 

Felly mae'n broses dau gam. Mae'n rhaid i chi aseinio cyntaf beth bynnag rydych yn ei greu. Gosodwch y pwyntydd i'r cyfeirio, ac yna rydych gall fath o dereference pwyntydd cyntaf ac yn pwyntio tuag at y nod newydd. Ble bynnag yr ydych eisiau ei fewnosod, y rhesymeg yn mynd i dal yn wir. 

Mae'n fath o fel aseinio newidynnau dros dro. Cofiwch, mae gennych i wneud yn siŵr eich bod yn peidiwch â cholli golwg ar os ydych yn cyfnewid. Y byddwch am wneud yn siŵr eich bod yn cael newidyn dros dro y math hwnnw o yn cadw cofnod o ble y peth yn cael ei storio er mwyn i chi peidiwch â cholli unrhyw werth yn y cwrs o fel chwarae o gwmpas ag ef. 

Iawn, felly bydd cod fod yma. Rydych guys gymryd golwg ar ôl adran. Bydd yn yno. 

Felly, yr wyf yn dyfalu sut mae mae hyn yn wahanol os ydym eisiau i fewnosod i mewn i'r canol neu'r diwedd? A oes unrhyw un gennych syniad o'r hyn sydd y pseudocode gan fod y cyfeiriad rhesymegol y byddem yn eu cymryd os oeddem am i fewnosod yn y canol? Felly, os oeddem am i fewnosod hynny ar y pen, popeth a wnawn yn creu nod newydd. Rydym yn gosod y pwyntydd y nod newydd i beth bynnag y pennaeth, ac yna rydym yn gosod y pen at y nod newydd, dde? Os ydym yn awyddus i fewnosod yn y canol y rhestr, yr hyn byddai'n rhaid i ni ei wneud? 

GYNULLEIDFA: Byddai'n dal fod yn broses debyg o fel pennu pwyntydd a Yna aseinio y pwyntydd, ond byddai'n rhaid i ni ddod o hyd yno. 

Andi Peng: Yn union, felly yn union yr un broses ac eithrio chi rhaid i leoli ble yn union rydych eisiau bod pwyntydd newydd i fynd i mewn, felly os wyf am i fewnosod i mewn i canol cysylltiedig list-- OK, gadewch i ni ddweud dyna ein rhestr cysylltiedig. Os ydym am i fewnosod yn iawn fan hyn, rydym yn mynd i greu nod newydd. Rydym yn mynd i malloc. Rydym yn mynd i greu nod newydd. Rydym yn mynd i aseinio'r pwyntydd y nôd hwn yma. 

Ond y broblem sy'n wahanol o ble mae'r pennaeth yn yw ein bod yn gwybod yn union lle mae'r pen yn. Yr oedd yn iawn ar y cyntaf, dde? Ond yma mae'n rhaid i gadw golwg o ble rydym yn gosod i mewn. Os ydym yn mewnosod ein nod yma, rydym wedi cael i wneud yn siŵr bod y un blaenorol i nod hwn yw'r un sy'n reassigns pwyntydd. Felly, yna rhaid i chi math o gadw golwg ar ddau beth. Os ydych yn cadw golwg ar ble hwn nôd o bryd yn gosod i mewn. Hefyd, rhaid i chi gadw cofnod o ble y nôd blaenorol a ydych yn edrych ar Roedd hefyd yno. Mae pawb yn dda â hynny? IAWN. 

Beth am fewnosod yn y diwedd? Os oeddwn i eisiau ei ychwanegu Yma-- os oeddwn i eisiau i ychwanegu nod newydd ar ddiwedd y rhestr, sut y gallwn fynd ati i wneud hynny? GYNULLEIDFA: Felly ar hyn o bryd, mae'r Nododd un olaf i null. Andi Peng: Yeah. Yn union, felly mae hyn yn un hyn o bryd yn tynnu sylw at ei wybod, ac felly yr wyf yn dyfalu, yn yr ystyr hwn, mae'n hawdd iawn i ychwanegu at ddiwedd y rhestr. Y cyfan sydd raid i chi ei wneud yw gosod cyfartal i null ac yna ffyniant. Iawn yno, yn hawdd iawn. Syml iawn. 

Debyg iawn i'r pen, ond yn rhesymegol chi eisiau gwneud yn siŵr bod y camau byddwch yn eu cymryd tuag at wneud unrhyw ran o hyn, eich bod yn dilyn ar hyd. Mae'n hawdd iawn i, yn y canol eich cod, yn cael eu dal i fyny ar, oh, mae gen i gymaint o awgrymiadau. Nid wyf yn gwybod ble unrhyw beth yn pwyntio i. Dydw i ddim hyd yn oed yn gwybod pa nod dwi ar. Beth sy'n Digwydd? 

Ymlaciwch, ymdawelu, gymryd anadl ddofn. Tynnwch allan eich rhestr cysylltiedig. Os ydych yn dweud, yr wyf yn gwybod ble yn union Mae angen i mi mewnosod hyn i ac yr wyf yn gwybod yn union sut i ail-neilltuo fy awgrymiadau, llawer, llawer haws i'w llun out-- llawer, llawer haws i beidio mynd ar goll yn y bygiau eich cod. Mae pawb yn iawn gyda hynny? IAWN. 

Felly, yr wyf yn dyfalu yn gysyniad nad ydym wedi Siaradodd wir am cyn hyn, ac yr wyf yn dyfalu mae'n debyg Ni fydd yn dod ar draws llawer yet-- mae'n fath o concept-- uwch yw ein bod mewn gwirionedd yn cael data strwythur a elwir yn rhestr gysylltiedig ddwbl. Felly, fel y gallwch weld guys, cyfan yr ydym yn ei wneud yw creu gwerth gwirioneddol, ychwanegol pwyntydd ar bob un o'n nodau hynny hefyd yn cyfeirio at y nôd blaenorol. Felly, nid yn unig yr ydym wedi ein nodau pwyntio i'r un nesaf. Maent hefyd yn cyfeirio at yr un blaenorol. Rydw i'n mynd i anwybyddu'r ddau yma ar hyn o bryd. 

Felly, yna mae gennych gadwyn sy'n gallu symud y ddwy ffordd, ac yna mae'n ychydig yn haws i ddilyn ar hyd rhesymegol. Fel yma, yn hytrach na cadw golwg ar, oh, yr wyf yn rhaid i gwybod bod nod hwn yr un sydd rhaid i mi ei ail-neilltuo, Gallaf fynd yma ac dim ond tynnu y blaenorol. Yna mi yn gwybod yn union lle hynny yw, ac yna rydych Nid oes rhaid i groesi'r gyfanrwydd y rhestr cysylltiedig. Mae'n ychydig yn haws. 

Ond fel y cyfryw, mae gennych ddwbl faint o awgrymiadau, dyna ddwbl y swm o gof. Mae'n llawer o awgrymiadau i gadw golwg ar. Mae'n ychydig yn fwy cymhleth, ond mae'n ychydig yn fwy cyfeillgar i'r defnyddiwr, yn dibynnu ar yr hyn yr ydych yn ceisio ei gyflawni. 

Felly y math hwn o ddata strwythur yn bodoli yn llwyr, ac mae'r strwythur ar gyfer yn iawn, iawn syml ac eithrio yr holl ydych chi'n cael yw, hytrach na dim ond pwyntydd i'r nesaf, byddwch hefyd yn cael pwyntydd i blaenorol. Dyna i gyd y gwahaniaeth yn. Mae pawb yn dda â hynny? Cool. 

Mae pob hawl, felly nawr rwy'n i 'n sylweddol yn gwario yn ôl pob tebyg fel 15 i 20 munud neu y rhan fwyaf o weddill yr amser yn adran siarad am tablau hash. Faint ohonoch chi guys wedi darllen spec pset5? Mae pob hawl, yn dda. Dyna uwch na'r 50% o fel arfer. Mae'n iawn. 

Felly, fel y byddwch yn guys yn gweld, eich bod yn her mewn pset5 Bydd yn gweithredu geiriadur lle rydych yn llwytho mwy na 140,000 o eiriau ein bod yn rhoi ac yn gwirio sillafu i chi yn erbyn pob un o'r testun. Byddwn yn rhoi i chi ar hap darnau o lenyddiaeth. Byddwn yn rhoi Mae'r Odyssey chi. Byddwn yn rhoi The Iliad i chi. Byddwn yn rhoi Austin Powers i chi. 

Ac yn eich her fydd cywirydd sillafu pob gair yn yr holl o eiriaduron rhai yn y bôn â'n gwiriwr sillafu. Ac felly mae ychydig o rannau o greu pset hwn, yn gyntaf eich bod am fod gallu llwytho mewn gwirionedd yr holl eiriau i mewn i'ch geiriadur, ac yna rydych am fod yn gallu i gwirio sillafu pob un ohonynt. Ac felly fel y cyfryw, rydych yn mynd i'w gwneud yn ofynnol strwythur data y gellir gwneud hyn yn gyflym ac yn effeithlon ac yn ddeinamig. 

Felly, mae'n debyg yr hawsaf ffordd o wneud hyn, byddwch yn mae'n debyg y byddai creu amrywiaeth, dde? Y ffordd hawsaf o storfa yw eich Gall creu amrywiaeth o 140,000 o eiriau a dim ond nhw i gyd yn gosod yno ac yna eu croesi drwy chwilio deuaidd neu drwy dewisiadau neu not-- Mae'n ddrwg sy'n didoli. Gallwch eu didoli ac yna eu croesi trwy chwilio deuaidd neu chwilio yn unig llinellol a dim ond terfynol y geiriau, ond bod yn cymryd llawer iawn o gof, ac nid yw'n effeithlon iawn. 

Ac felly rydym yn mynd i ddechrau siarad am ffyrdd o wneud ein hamser yn rhedeg yn fwy effeithlon. Ac mae ein nod yw cael amser cyson lle 'i' bron fel araeau, lle mae gennych fynediad y pryd. Os wyf yn awyddus i chwilio am unrhyw beth, Rwyf am fod yn gallu gyfiawn, ffyniant, yn ei chael yn union, a thynnu allan. Ac felly strwythur lle byddwn yn dod yn agos iawn i allu cael mynediad cyson amser, mae hyn greal sanctaidd mewn rhaglenni o cyson Gelwir amser tabl hash. Ac felly soniodd David eisoes y [Anghlywadwy] ychydig yn y ddarlith, ond rydyn ni'n mynd i 'n sylweddol plymio yn y dwfn yr wythnos hon ar ddarn sy'n ynglŷn â sut tabl hash yn gweithio. 

Felly, y ffordd y mae hash gwaith bwrdd, er enghraifft, os oeddwn i eisiau i storio bagad o eiriau, a criw o eiriau yn yr iaith Saesneg, Gallwn roi ddamcaniaethol banana, afal, kiwi, mango, pâr, a cantaloupe i gyd ar ddim ond arae. Gallai Maent i gyd yn ffitio i mewn a bod yn dod o hyd. Byddai'n fath o boen i chwilio drwy a mynediad, ond y ffordd haws o wneud hyn yw y gallwn greu mewn gwirionedd strwythur Gelwir tabl hash lle rydym hash. Rydym yn rhedeg ein holl allweddi drwy swyddogaeth hash, hafaliad, bod nhw i gyd yn troi i mewn rhyw fath o werth bod yna gallwn storio ar ei hanfod amrywiaeth o rhestr gysylltiedig. 

Ac felly yma, os oeddem am i storio geiriau Saesneg, gallem o bosibl yn unig, nid wyf yn ei wneud gwybod, trowch holl lythyrau cyntaf i mewn i ryw fath o nifer. Ac felly, er enghraifft, os oeddwn i eisiau A i yn gyfystyr â apple-- neu gyda mynegai o 0, a B i fod yn gyfystyr â 1, gallwn gael 26 o geisiadau Gall mai dim ond storio pob un o'r lythrennau'r wyddor y byddwn yn dechrau gyda. Ac yna gallwn gael afal yn y mynegai 0. Gallwn gael banana yn y mynegai 1, cantaloupe ar y mynegai o 2, ac yn y blaen ac yn y blaen. Ac felly os oeddwn i eisiau i chwilio fy mwrdd a mynediad afal hash, Rwy'n gwybod afal yn dechrau gyda A, ac yr wyf yn gwybod yn union bod rhaid iddo fod a hash tabl ar fynegai 0 oherwydd y swyddogaeth a bennwyd yn flaenorol. 

Felly, nid wyf yn gwybod, yr ydym yn rhaglen defnyddiwr lle byddwch yn cael eich cyhuddo o arbitrarily-- nid yn fympwyol, â cheisio feddylgar meddwl o hafaliadau da i allu lledaenu allan pob un o'ch gwerthoedd mewn ffordd y gallant gael mynediad hawdd yn nes ymlaen â thebyg hafaliad eich bod chi, eich hun, yn gwybod. Felly, yn yr ystyr os wyf eisiau mynd i mango, yr wyf yn gwybod, o, mae'n dechrau gyda m. Rhaid iddo fod yn y mynegai 12. Nid oes rhaid i mi chwilio drwy unrhyw beth. Rwy'n gwybod exactly-- gallwn i jyst yn mynd i y mynegai 12 a thynnu hynny allan. 

Mae pawb yn glir ynglŷn â sut mae swyddogaeth tabl hash yn gweithio? Mae'n fath o ychydig amrywiaeth fwy cymhleth. Dyna i gyd y mae. IAWN. 

Felly, yr wyf yn dyfalu rydym yn rhedeg i mewn i rhifyn hwn o beth fydd yn digwydd os oes gennych bethau lluosog sy'n rhoi yr un mynegai i chi? Felly, yn dweud ein swyddogaeth, popeth o fewn ei wnaeth oedd cymryd y llythyr cyntaf a throi i mewn i hynny priod 0 trwy 25 mynegai. Mae hynny'n hollol iawn os mai dim ond un o bob un. Ond mae'r ail i chi ddechrau cael mwy, rydych yn mynd i gael hyn a elwir yn gwrthdrawiad. 

Felly, os wyf yn ceisio i fewnosod claddu i mewn i hash tabl sydd banana yn barod arno, beth sy'n mynd i ddigwydd pan byddwch yn ceisio mewnosod hynny? Pethau drwg oherwydd banana yn bodoli eisoes o fewn y mynegai eich bod am ei storio mewn. Berry fath o yn debyg, AH, beth ddylwn i ei wneud? Nid wyf yn gwybod ble i fynd. Sut mae datrys hyn? 

Ac felly byddwch yn guys fath o gweld byddwn yn gwneud hyn beth anodd lle y gallwn fath o mewn gwirionedd creu rhestr gysylltiedig yn ein arae. Ac felly y ffordd hawsaf i feddwl am hyn, pob tabl hash yn amrywiaeth o restrau cysylltiedig. Ac felly, yn yr ystyr hwnnw, mae gennych mae hyn amrywiaeth hardd o awgrymiadau, ac yna mae pob pwyntydd yn sy'n gwerthfawrogi, yn y mynegai, Gall mewn gwirionedd yn cyfeirio at bethau eraill. Ac er mwyn i chi gael y rhain i gyd ar wahân cadwyni dod oddi ar un amrywiaeth mawr. 

Ac felly yma, os wyf yn eisiau i fewnosod aeron, Yr wyf yn gwybod, OK, dw i'n mynd i fewnbynnu drwy fy swyddogaeth hash. Rydw i'n mynd i roi diwedd ar i fyny gyda y mynegai 1, ac yna dwi'n mynd i fod yn gallu cael dim ond is-set lai o hyn Geiriadur 140,000 o eiriau mawr. Ac yna gallaf dim ond yn edrych trwy 1/26 o hynny. 

Ac felly yna gallaf jyst rhowch aeron naill ai cyn neu ar ôl banana yn yr achos hwn? Ar ôl, dde? Ac felly rydych yn mynd i eisiau mewnosod nod hwn ar ôl banana, ac felly rydych yn mynd i fewnosod yn y gynffon y rhestr cysylltiedig. Rydw i'n mynd i fynd yn ôl at y sleid blaenorol, er mwyn i chi guys weld sut swyddogaeth hash yn gweithio. 

Felly swyddogaeth hash yw hafaliad hwn eich bod yn rhedeg y math o eich mewnbwn trwy i gael beth bynnag mynegai rydych am ei aseinio iddo tuag at. Ac felly, yn yr enghraifft hon, pob oeddem am ei wneud oedd cymryd y llythyr cyntaf, trowch hynny i mewn i fynegai, yna rydym yn Gall storio hynny yn ein swyddogaeth hash. Y cyfan yr ydym yn ei wneud yma yw ein bod trosi llythyren gyntaf. Felly keykey [0] yn unig y llythyr cyntaf o ba bynnag llinyn ein bod yn cael, rydym yn pasio i mewn. Rydym yn trosi hynny i'r uchaf, ac rydym yn tynnu yn ôl priflythyren A, felly bob un sy'n ei wneud yn rhoi nifer ni y gallwn hash ein gwerthoedd ar. 

Ac yna rydym yn mynd i dychwelyd MAINT modwlws hash. Byddwch yn iawn, yn ofalus iawn oherwydd, yn ddamcaniaethol, dyma Gallai eich gwerth hash yn ddiddiwedd. Gallai dim ond yn mynd ymlaen ac ymlaen ac ymlaen. Gallai fod yn rhai gwirioneddol, 'n sylweddol gwerth mawr, ond oherwydd bod eich bwrdd hash sy'n eich bod wedi creu dim ond ganddi 26 mynegeion, ydych am wneud yn siŵr bod eich modulusing er mwyn i chi peidiwch â run-- 'i' yr un fath beth fel eich queue-- fel nad ydych yn rhedeg oddi ar y waelod eich swyddogaeth hash. 

Rydych am i lapio yn ôl o gwmpas yr un ffordd yn [Anghlywadwy] pan oedd gennych fel iawn, llythyr mawr iawn, yr ydych Nid oedd am i hynny jyst yn rhedeg oddi ar y diwedd. Yr un peth yma, yr ydych am wneud yn siŵr nid yw'n rhedeg oddi ar y diwedd drwy lapio o gwmpas i frig y tabl. Felly, mae hyn yn unig yw iawn swyddogaeth hash syml. Y cyfan a wnaeth oedd cymryd y cyntaf llythyr o ba bynnag ein mewnbwn yn a throi i mewn i hynny fynegai sy'n gallem roi yn ein tabl hash. 

Yeah, ac felly fel y dywedais o'r blaen, y modd yr ydym yn datrys gwrthdrawiadau yn ein hash tablau yn cael, yr hyn a alwn, gadwyno. Felly, os ydych yn ceisio i fewnosod lluosog eiriau sy'n dechrau gyda'r un peth, rydych yn mynd i gael un gwerth hash. Afocados ac afal, os ydych chi wedi rhedeg trwy ein swyddogaeth hash, yn mynd i roi i chi y un nifer, mae nifer y 0. Ac felly y ffordd yr ydym yn datrys hynny yw ein bod yn gallu mewn gwirionedd yn fath o yn eu cysylltu ynghyd drwy restrau cysylltiedig. 

Ac felly yn yr ystyr hwn, allwch chi guys weld garedig o sut mae strwythurau data sy'n rydym wedi bod yn gosod yn flaenorol fel rhesins cysylltiedig rhestr caredig Gall y dod at ei gilydd i mewn i un. Ac yna gallwch greu bell strwythurau data yn fwy effeithlon a all drin symiau mwy o data, hynny ddeinamig newid maint yn dibynnu ar eich anghenion. Mae pawb yn glir? Mae pawb fath o clir ar yr hyn sy'n digwydd yma? 

Os wyf yn awyddus i insert-- beth 'na ffrwythau sy'n dechrau gyda, nid wyf yn gwybod, B, ac eithrio aeron, banana. 

GYNULLEIDFA: Blackberry. 

Andi Peng: Blackberry, mwyar duon. Ble mae mwyar duon fynd yma? Wel, nid ydym mewn gwirionedd wedi datrys mae hyn eto, ond yn ddamcaniaethol os ydym am gael hyn yn nhrefn yr wyddor, lle dylai mwyar duon fynd? 

GYNULLEIDFA: [Anghlywadwy] 

Andi Peng: Yn union, ar ôl fan hyn, dde? Ond gan ei fod yn anodd iawn reorder-- Mae'n debyg mae i fyny i chi guys. Gallwch guys yn llwyr gweithredu beth bynnag y dymunwch. Y ffordd fwy effeithlon o wneud hyn efallai fyddai i roi trefn ar eich cysylltiedig Rhestrwch mewn trefn yr wyddor, ac felly pan fyddwch yn mewnosod pethau, yr ydych am i fod yn sicr i fewnosod nhw i mewn i nhrefn yr wyddor fel bod yna pan fyddwch yn ceisio chwilio iddynt, Nid oes rhaid i chi dramwy popeth. Rydych yn gwybod yn union lle y mae, ac mae'n haws. 

Ond os ydych yn fath o gael pethau gymysg ar hap, ydych yn dal yn mynd i gael i groesi ei anyways. Ac felly os oeddwn i eisiau i ddim ond mewnosod mwyar duon yma ac roeddwn i eisiau i chwilio am y peth, yr wyf yn gwybod, o, mwyar duon Mae'n rhaid i ni ddechrau gyda'r mynegai o 1, felly yr wyf yn gwybod ar unwaith yn unig yn chwilio am 1. Ac yna gallaf math o croesi y rhestr cysylltiedig nes i mi ddod i mwyar, a then-- yeah? 

GYNULLEIDFA: Os ydych yn ceisio create-- Amcana fel hyn yn hash syml iawn swyddogaeth. Ac os ydym am ei wneud haenau lluosog o hynny fel, OK, rydym am i wahanu i mewn fel yr holl lythyrau yn nhrefn yr wyddor ac yna eto i hoffi set arall o lythyrau yn nhrefn yr wyddor o fewn hynny, rydym yn rhoi fel hash tabl o fewn tabl hash, neu fel swyddogaeth o fewn swyddogaeth? Neu a yw that-- 

Andi Peng: Felly eich hash function-- eich bwrdd hash Gall fod mor fawr ag y dymunwch iddo. Felly, yn yr ystyr hwn, yr wyf yn meddwl roedd yn hawdd iawn, iawn syml i mi yn seiliedig yn unig fath ar lythyrau y gair cyntaf. Ac felly does dim ond 26 opsiwn. Ni allaf ond ei gael 26 opsiwn o 0 i 25 oed oherwydd eu bod dim ond cychwyn o A i Z. Ond Os ydych eisiau i ychwanegu, efallai, yn fwy cymhleth neu redeg amser i gyflymach eich tabl hash, yr ydych yn hollol yn gallu gwneud pob math o bethau. Gallwch wneud eich hun hafaliad sy'n rhoi i chi mwy dosbarthu yn eich geiriau, yna pan fyddwch yn chwilio, mae'n mynd i fod yn gyflymach. 

Mae'n hollol i fyny i chi guys sut yr ydych am i weithredu'r hynny. Meddyliwch amdano fel dim ond bwcedi. Os wyf yn awyddus i gael 26 bwcedi, dw i'n mynd i ddatrys pethau i mewn i bwcedi hynny. Ond dw i'n mynd i gael bagad o bethau ym mhob bwced, felly os ydych am ei gwneud yn gyflymach ac yn fwy effeithlon, gadewch i mi fod â chant o fwcedi. 

Ond yna mae'n rhaid i chi chyfrif i maes ffordd i ddatrys pethau fel eu bod yn yn y bwced priodol dylent fod yn. Ond yna pan fyddwch mewn gwirionedd am edrych ar y bwced, mae'n llawer cyflymach oherwydd bod llai o stwff ym mhob bwced. Ac felly, ie, dyna mewn gwirionedd y tric i chi guys yn pset5 yw y byddwch yn herio i ddim ond creu beth bynnag yw'r mwyaf effeithlon swyddogaeth y gallwch feddwl i fod yn gallu i storio a gwirio gwerthoedd hyn. 

Hollol fyny i chi guys Fodd bynnag, yr ydych am ei wneud, ond mae hynny'n bwynt da iawn. Bod y math o rhesymeg chi am ddechrau meddwl am yn, wel, pam nad ydw i'n gwneud mwy o bwcedi. Ac yna mae'n rhaid i mi chwilio llai o bethau, ac yna efallai yr wyf yn â swyddogaeth hash gwahanol. 

Yeah, mae llawer o ffyrdd o wneud hyn pset, mae rhai yn gyflymach nag eraill. Rydw i'n llwyr yn mynd i jyst gweld sut cyflym oedd y cyflymaf rydych guys fydd yn gallu cael eich swyddogaethau i'r gwaith. OK, mae pawb ar da tablau gadwyno a hash? Mae'n mewn gwirionedd fel syml iawn cysyniad os ydych yn meddwl am y peth. Mae'r holl mae'n ei gwahanu beth bynnag eich mewnbwn yn cael i mewn bwcedi, eu didoli, ac wedyn chwilio yn rhestru bod wedi gysylltiedig â. 

Cool. Mae pob hawl, erbyn hyn mae gennym fath gwahanol o strwythur data sy'n cael ei alw coeden. Gadewch i ni fynd ymlaen ac yn siarad am geisiau sydd yn amlwg yn wahanol, ond yn yr un categori. Yn y bôn, pob coeden yn lle hynny o trefnu data yn y ffordd linellol fod tabl hash does-- chi yn gwybod, 'i' got top a gwaelod ac yna rydych fath o gysylltu i ffwrdd o iddo-- yn coeden Mae top y byddwch yn ffonio'r gwraidd, ac yna mae'n ganddo ddail o amgylch iddo. 

Ac felly yr holl ydych wedi yma Dim ond y nod uchaf sy'n tynnu sylw at nodau eraill, bod pwyntiau i fwy nodau, ac yn y blaen ac yn y blaen. Ac felly os oes gen ti canghennau hollti. 'I' jyst ffordd wahanol o drefnu data, ac oherwydd rydym yn galw ei goeden, 'ch guys just-- mai dim ond modelu allan i edrych fel coeden. Dyna pam rydym yn galw ei goed. 

Tabl Hash edrych yn debyg i dabl. Mae coeden unig yn edrych fel coeden. Mae'r holl mae'n yn ar wahân ffordd o drefnu nodau yn dibynnu ar beth yw eich anghenion. 

Felly, mae gennych gwraidd a yna mae gennych dail. Mae'r ffordd y gallwn arbennig meddwl am y peth yn goeden ddeuaidd, goeden ddeuaidd yn unig yw math penodol o goeden lle mai dim ond pwyntiau pob nod i, yn max, dau nodau eraill. Ac felly dyma oes gennych wahanol cymesuredd yn eich coeden sy'n ei gwneud yn haws i fath o edrych ar yr hyn gwerthfawrogi eich bod am fod yna rydych bob amser yn chwith neu i'r dde. Mae yna byth fel un rhan o dair o chwith y chwith neu bedwerydd o'r chwith. 'I' jyst bod gennych chwith a hawl a gallwch chwilio naill neu'r llall o'r ddau hynny. Ac felly pam mae hon yn ddefnyddiol? Mae'r ffordd y mae hyn yn ddefnyddiol yw os ydych yn chwilio i chwilio drwy werthoedd, dde? Yn hytrach na gweithredu deuaidd chwilio mewn amrywiaeth camgymeriad, os ydych chi eisiau gallu i fewnosod nodau ac yn cymryd i ffwrdd nodau yn ewyllys, a hefyd cadw'r chwiliad galluoedd chwilio deuaidd. Felly, yn y modd hwn, rydym yn fath o tricking-- cofio pan fyddwn yn Dywedodd na all rhestrau cysylltiedig chwiliad deuaidd? Rydym yn fath o greu strwythur data bod driciau hynny i mewn i weithio. 

A rhestrau hynny oherwydd cysylltiedig yn llinol, eu bod ond yn cysylltu un ar ôl y llall. Gallwn fath o gael gwahanol fath o awgrymiadau y pwynt hwnnw i wahanol nodau a all ein helpu i chwilio. Ac felly yma, os oeddwn i eisiau gennych goeden chwiliad deuaidd, Gwn fod fy canol, os 55. Im 'jyst yn mynd i greu'r fel fy canol, fel fy gwraidd, ac yna dwi'n mynd i gael Gwerthoedd throelli oddi ar hynny. 

Felly dyma, os ydw i'n mynd i chwilio am werth o 66, gallaf dechrau am 55. Mae'n fwy na 66 55? Ydi mae, felly yr wyf yn gwybod fy mod Mus chwilio ff n pwyntydd cywir y goeden hon. Rwy'n mynd i 77. OK, yn 66 yn llai na neu'n fwy na 77? Mae'n llai na, felly eich bod yn gwybod, oh, rhaid i hynny fod y nôd chwith. 

Ac felly dyma rydym yn fath o gadw pob un o'r pethau gwych am araeau, felly fel newid maint deinamig o wrthrychau, sef gallu mewnosod a dileu fel y myn, heb orfod poeni am y sefydlog faint o le. Rydym yn dal i gadw pob un pethau gwych y rhai tra hefyd yn gallu i warchod y log a chwilio adeg chwiliad deuaidd ein bod dim ond yn flaenorol gallu cael ymadrodd. 

Strwythur data Cool, math o gymhleth i'w weithredu, y nôd. Fel y gwelwch, popeth o fewn ei yw struct y nôd yw bod gennych chwith ac pwyntydd i'r dde. Dyna i gyd y mae. Felly yn hytrach na dim ond cael x neu flaenorol. Mae gennych chwith neu i'r dde, ac yna gallwch fath o eu cysylltu â'i gilydd Fodd bynnag, byddwch yn dewis gwneud hynny. 

OK, rydym yn mynd mewn gwirionedd dim ond yn cymryd ychydig funudau. Felly rydym yn mynd i fynd yn ôl yma. Fel y dywedais eisoes, Yr wyf yn fath o esboniodd y rhesymeg y tu ôl i sut yr ydym Byddai chwilio drwy hyn. Rydym yn mynd i roi cynnig ar pseudocoding allan hwn i weld os gallwn fath o gymhwyso'r un rhesymeg chwilio deuaidd i fath gwahanol o strwythur data. Os ydych chi guys eisiau cymryd fel cwpl munud i jyst yn meddwl am hyn. IAWN. Mae pob hawl, dw i'n mynd i mewn gwirionedd dim ond rhoi i chi the-- dim, byddwn yn siarad am y pseudocode yn gyntaf. Felly mae unrhyw un am i roi drywanu ar yr hyn y peth cyntaf rydych am ei wneud pan ydych yn dechrau allan yn chwilio? Os rydym yn chwilio am werth o 66, beth sydd y peth cyntaf yr ydym am ei wneud os rydym am deuaidd chwilio goeden hon? 

GYNULLEIDFA: byddwch am edrych yn iawn ac yn edrych i'r chwith a gweld [Anghlywadwy] nifer fwyaf. 

Andi Peng: Yeah, yn union. Felly, rydych yn mynd i edrych ar eich gwreiddiau. Mae llawer o ffyrdd y gallwch ffonio y peth, eich rhiant gwgn pobl yn dweud. Rwy'n hoffi dweud gwraidd oherwydd dyna fel gwraidd y goeden. Rydych yn mynd i edrych ar eich nod gwraidd, ac rydych yn mynd i weld yw 66 mwy na neu'n llai na 55. Ac os yw'n fwy na, wel, mae'n fwy na, ble rydym yn awyddus i edrych? Ble ydym ni eisiau i chwilio nawr, dde? Rydym yn awyddus i chwilio'r hanner dde goeden hon. 

Felly, rydym wedi, yn gyfleus, mae pwyntydd sy'n pwyntio i'r dde. Ac felly yna gallwn osod ein gwreiddiau newydd fod yn 77. Gallwn jyst yn mynd i ble bynnag pwyntydd yn pwyntio. Wel, o, dyma ni yn dechrau yn 77, ac a allwn yn unig gwneud hyn recursively dro ar ôl tro. Yn y modd hwn, byddwch yn garedig o fod â swyddogaeth. Mae gennych ffordd o chwilio eich bod yn gall dim ond ailadrodd drosodd a throsodd a throsodd, yn dibynnu ar ble rydych am edrych hyd nes y byddwch yn y pen draw gyrraedd y gwerth eich bod yn chwilio am. Gwneud synnwyr? 

Rwy'n am i ddangos i chi y gwir cod, ac mae'n llawer o god. Nid oes angen i freak allan. Byddwn yn siarad drwyddo. 

A dweud y gwir, dim. Dyna oedd dim ond pseudocode. OK, dyna oedd dim ond y pseudocode, sydd yn braidd yn gymhleth, ond mae'n hollol iawn. Mae pawb yn dilyn ar hyd yma? Os bydd y gwraidd yn null, yn dychwelyd ffug oherwydd y ffordd nad ydych yn hyd yn oed gael unrhyw beth yno. 

Os yw n gwraidd yw gwerth, felly os yw'n digwydd i fod yr un yr ydych yn edrych ar, yna rydych chi'n mynd i ddychwelyd yn wir oherwydd eich bod yn gwybod eich chael hi'n. Ond os bydd y gwerth yn llai na gwraidd n, rydych yn mynd i chwilio'r chwith plentyn neu y ddeilen chwith, beth bynnag yr ydych am ei alw. Ac os yw gwerth yn fwy na gwraidd, ydych yn mynd i chwilio'r goeden gywir, yna dim ond yn rhedeg y swyddogaeth drwy chwilio eto. 

Ac os gwraidd yn null, bod hynny yn golygu eich bod wedi cyrraedd diwedd? Mae hynny'n golygu nad oes gennych unrhyw mwy mwy ddail i chwilio, yna rydych yn gwybod, oh, yr wyf yn dyfalu nid yw'n mewn yma oherwydd ar ôl i mi edrych drwy yr holl beth ac nid yw'n fan hyn, 'i jyst Ni allai fod yn fan hyn. 

A yw hynny'n gwneud synnwyr i bawb? Felly mae fel chwiliad deuaidd cadw galluoedd rhestrau cysylltiedig. Cool, ac felly mae'r ail fath o strwythur data chi guys Gall roi cynnig gweithredu ar eich pset, Dim ond rhaid i chi ddewis un dull. Ond efallai ddull arall i mae'r tabl hash yw'r hyn a alwn yn trie. 

Mae'r holl mae trie yn yn math penodol o goed sy'n Mae gwerthoedd sy'n mynd i werthoedd eraill. Felly, yn lle cael deuaidd coeden yn yr ystyr mai dim ond un Gall peth bwyntio at ddau, gallwch gael pwynt un peth i lawer, mae llawer o bethau. Yn y bôn yn rhaid i chi araeau tu mewn yr ydych yn storio awgrymiadau sy'n cyfeirio at araeau eraill. 

Felly, y nôd o sut yr ydym Byddai diffinio trie yn yr ydym am ei gael Boole, c gair, dde? Felly 'r nôd yn Boole fel gwir neu gau, yn gyntaf oll ar ben hynny array, a yw hyn yn air? Yn ail, yr ydych am gael awgrymiadau i ba bynnag gweddill ohonynt. Ychydig yn gymhleth, braidd yn haniaethol, ond Byddaf yn egluro beth bod pob modd. 

Felly dyma, ar y brig, os ydych yn cael amrywiaeth datgan eisoes, cainc lle mae gennych Boolean gwerth ei storio yn y tu blaen sy'n dweud wrthych a yw hyn yn air? A yw hyn nid gair? Ac yna mae gennych yr weddill eich arae sy'n storio mewn gwirionedd holl posibiliadau o'r hyn y gallai fod. Felly, er enghraifft, fel ar y brig sydd gennych y peth cyntaf sy'n dweud wir neu ffug, ie neu ddim, mae hwn yn air. 

Ac yna mae gennych 0 trwy 26 o y llythrennau y gallwch storio. Os wyf yn awyddus i chwilio yma ar gyfer ystlumod, yr wyf yn mynd i'r top ac yr wyf yn edrych am B. gallaf ddod o hyd B yn fy array, ac felly yr wyf yn gwybod, OK, mae B yn air? Nid yw B yn air, felly a thrwy hynny Mae'n rhaid i mi gadw chwilio. Rwy'n mynd o B, ac edrychaf at y pwyntydd y B pwyntiau tuag at ac yr wyf yn gweld amrywiaeth arall o wybodaeth, yr un strwythur a oedd gennym o'r blaen. 

Ac yn Yma-- oh, y nesaf llythyr yn [Anghlywadwy] yw A. Felly rydym yn edrych yn y rhesi. Rydym yn dod o hyd i'r gwerth wythfed, ac yna rydym yn edrych i weld, oh, hey, yw bod gair, yn B-A gair? Nid yw'n air. Mae'n rhaid i ni gadw chwilio. 

Ac felly, yna rydym yn edrych i ble pwyntydd y pwyntiau A, ac mae'n cyfeirio at ffordd arall mewn yr ydym yn cael mwy o werth ei storio. Ac yn y pen draw, rydym yn cael B-A-T, sydd yn air. Ac felly y tro nesaf ydych yn edrych, rydych yn mynd i gael y gwiriad o'r, ie, y swyddogaeth Boolean yn wir. Ac felly yn yr ystyr ein bod garedig o gael coeden gyda arrays. 

Felly, yna gallwch chi fath o chwilio i lawr. Yn hytrach na stwnsio swyddogaeth a aseinio gwerthoedd rhestr gysylltiedig, gallwch weithredu trie sy'n chwiliadau downwords. Really, cymhleth pethau mewn gwirionedd. Ddim yn hawdd i feddwl am oherwydd fy mod yn hoffi poeri cymaint o strwythurau data allan ar chi, ond mae pawb yn fath o deall sut y rhesymeg hyn yn gweithio? 

OK, oer. Felly B-A-T, ac yna ydych yn mynd i chwilio. Y tro nesaf y byddwch chi'n mynd i weld, oh, hey, mae'n wir, felly yr wyf yn gwybod rhaid i hyn fod yn air. 

Yr un peth dros sw. Felly dyma y peth iawn yn awr, os ydym yn awyddus i chwilio am sw, ar hyn o bryd, Ar hyn o bryd nid yw sw yn gair yn ein geiriadur oherwydd, fel y gallwch weld guys, yr lle cyntaf bod gennym Boolean dychwelyd yn wir yw ar ddiwedd y chwyddo. Rydym wedi Z-O-O-M. 

Ac felly dyma, nid ydym mewn gwirionedd y gair, sw, yn ein geiriadur oherwydd nad yw hyn blwch gwirio yn cael ei wirio. Felly nid y cyfrifiadur yn ei wneud gwybod bod sw yn air oherwydd bod y ffordd yr ydym i wedi storio iddo, dim ond chwyddo yma mewn gwirionedd yn werth Boole sydd wedi bod yn troi yn wir. Felly os ydym am mewnosoder y gair, sw, i mewn ein geiriadur, sut y byddem yn mynd ati i wneud hynny? Beth sy'n rhaid i ni ei wneud i sicrhau bod ein cyfrifiadur yn gwybod bod Z-O-O yn air ac nid y gair cyntaf yw Z-O-O-M? 

GYNULLEIDFA: [Anghlywadwy] 

Andi Peng: Yn union, rydym yn eisiau gwneud yn siŵr bod hyn yn yma, y ​​gwerth Boole yn gwirio i ffwrdd ei fod yn wir. Z-O-O, yna rydym yn mynd i wirio bod, felly rydym yn gwybod yn union, hey, sw yn air. Rydw i'n mynd i ddweud wrth y cyfrifiadur ei fod yn air felly pan fydd y gwiriadau cyfrifiadur, mae'n gwybod bod sw yn air. 

Gan fod cofiwch holl ddata hyn strwythurau, mae'n hawdd iawn i ni i ddweud, oh, ystlum 'na air. Sw 'na air. Zoom 'na air. Ond pan fyddwch yn adeiladu arno, Mae gan y cyfrifiadur ddim syniad. 

Felly, rhaid i chi ddweud yn union ar ba bwynt yw hyn yn air? Ar ba bwynt nad yw'n air? Ac ar ba bwynt yn ei wneud i mi Mae angen i chwilio pethau, ac ar ba bwynt sydd angen i mi fynd nesaf? Mae pawb yn glir o hynny? Cool. 

Ac felly, yna daw'r broblem o sut y byddem yn mynd ati i fewnosod rhywbeth dyna mewn gwirionedd does? Felly gadewch i ni dim ond dweud ein bod am i fewnosod y gair, bath, i mewn i'n trie. Fel y gallwch weld guys fel ar hyn o bryd i gyd sydd gennym yn awr yw B-A-T, ac mae hyn yn strwythur data newydd bu beint sy'n tynnu sylw at null oherwydd ein bod yn cymryd yn ganiataol hynny, oh, does dim geiriau ar ôl B-A-T, pam mae angen i ni gadw cael pethau ar ôl y T. 

Ond mae'r broblem yn codi os byddwn ydych yn ei wneud am gael gair sy'n dod ar ôl y T. Os oes gennych bath, rydych yn mynd i eisiau hawl H. Ac felly y ffordd yr ydym yn mynd i wneud hynny yw rydym yn mynd i greu nod ar wahân. Nid ydym yn allot pa bynnag swm o gof ar gyfer y casgliad newydd, ac rydym yn mynd i ail-neilltuo awgrymiadau. 

Rydym yn mynd i aseinio'r H, Yn gyntaf oll, null hon, rydym yn mynd i gael gwared. Rydym yn mynd i gael mae'r tuag i lawr pwynt H. Os byddwn yn gweld H, yr ydym am iddo i fynd i rywle arall. 

Yn fan hyn, yna gallwn wirio i ffwrdd ie. Os byddwn yn taro H ar ôl y T, oh, Yna, rydym yn gwybod bod hwn yn air. Mae'r Boolean yn mynd i ddychwelyd wir. Mae pawb yn glir ynghylch sut y digwyddodd? IAWN. 

Felly y bôn, i gyd y strwythurau data ein bod wedi mynd dros heddiw, rwyf wedi mynd drostynt iawn, iawn yn gyflym ac nid mewn i lawer fanwl, ac mae hynny'n iawn. Unwaith y byddwch yn dechrau cyboli ag ef, byddwch yn cadw golwg ar ble yr holl awgrymiadau yn cael eu, beth sy'n digwydd yn eich strwythurau data, et cetera. Byddant yn ddefnyddiol iawn, ac mae i fyny i chi guys at chyfrif i maes sut llwyr ydych am weithredu pethau. 

Ac felly pset4, o 5-- oh, hynny yw anghywir. Pset5 yw gamsillafu. Fel y dywedais o'r blaen, rydych chi'n mynd i, unwaith eto, lawrlwytho cod ffynhonnell oddi wrthym. Mae mynd i fod yn dri phrif pethau y byddwch yn eu llwytho i lawr. Byddwch lawrlwytho geiriaduron, Kers, a thestunau. 

Mae'r holl bethau hynny yn cael eu naill ai geiriaduron o eiriau ein bod am i chi wirio neu brawf o wybodaeth ein bod am i chi cywirydd sillafu. Ac felly mae'r geiriaduron rydym yn rhoi eich bod yn mynd i roi union eiriau yr ydym am i chi chi storio rhywsut mewn ffordd sy'n yn fwy effeithlon na arae. Ac yna y testunau yn cael eu mynd i fod yr hyn rydym yn gofyn i chi sillafu gwirio i wneud yn siŵr i gyd o'r geiriau mae geiriau go iawn. 

Ac felly y tri bloc o rhaglenni y byddwn yn rhoi i chi yn cael eu galw'n dictionary.c, dictionary.h, a speller.c. Ac felly yr holl dictionary.c yn ei wneud yn cael ei hyn yr ydych yn gofyn am gael rhoi ar waith. Mae'n llwythi geiriau. Mae'n sillafu sieciau iddynt, ac mae'n gwneud yn siwr bod popeth yn cael ei fewnosod yn iawn. 

diction.h yn unig yw ffeil llyfrgell sy'n datgan yr holl swyddogaethau hynny. Ac speller.c, rydym yn mynd i roi i chi. Nid oes angen i chi addasu unrhyw ohono. Mae'r holl speller.c yn ei wneud yw cymryd hynny, llwythi iddo, yn gwirio cyflymder ohono, profion y meincnod o fel sut gyflym rydych chi'n gallu gwneud pethau. 

Mae'n sillafu. Dim ond peidiwch â llanast ag ef, ond gwnewch yn siŵr eich bod yn deall yr hyn y mae'n ei wneud. Rydym yn defnyddio swyddogaeth o'r enw getrusage sy'n profion perfformiad eich sillafu gwirydd. Mae'r holl mae'n ei wneud yn y bôn yn profi'r amser o bopeth yn eich geiriadur, felly gwnewch yn siŵr eich bod yn deall hynny. Byddwch yn ofalus i beidio llanast ag ef neu Ni fydd arall yn bethau redeg yn briodol. 

Ac mae'r rhan fwyaf o'r her hon yw i chi guys i wir addasu dictionary.c. Rydym yn mynd i roi i chi 140,000 o eiriau mewn geiriadur. Rydym yn mynd i roi i chi destun ffeil sydd â geiriau hynny, ac rydym am i chi fod yn gallu trefnu i mewn i dabl hash neu trie oherwydd pan fyddwn yn gofyn i chi i sillafu check-- dychmygwch os ydych yn sillafu gwirio fel Odyssey Homer. Mae fel y prawf enfawr, enfawr. 

Dychmygwch pe byddai pob un gair bu'n rhaid i chi edrych drwy amrywiaeth o 140,000 gwerthoedd. Byddai hynny'n cymryd am byth ar gyfer eich peiriant i redeg. Dyna pam yr ydym yn awyddus i drefnu ein data i mewn i strwythurau data yn fwy effeithlon megis tabl hash neu trie. Ac yna gallwch chi guys caredig o pan fyddwch yn chwilio mynediad pethau yn haws ac yn gyflymach. 

Ac felly byddwch yn ofalus i ddatrys gwrthdrawiadau. Rydych yn mynd i gael criw y geiriau yn y dechrau gydag A. Rydych yn mynd i gael criw o eiriau sy'n dechrau gyda B. Hyd at chi guys sut yr ydych am ei datrys. Efallai mae mwy swyddogaeth hash effeithlon na dim ond y llythyren gyntaf rhywbeth, ac fel eu bod i fyny i chi guys i fath o wneud beth bynnag yr ydych ei eisiau. 

Efallai eich bod am ychwanegu holl lythyrau at ei gilydd. Efallai eich bod am hoffi gwneud pethau rhyfedd i gyfrif y nifer o lythrennau, Beth bynnag. I fyny i chi guys sut yr ydych am ei wneud. Os ydych am wneud tabl hash, os ydych yn am roi cynnig ar trie, yn hollol i fyny i chi. Byddaf yn eich rhybuddio o flaen amser y mae'r trie yn nodweddiadol ychydig yn fwy anodd dim ond oherwydd mae yna lawer mwy o awgrymiadau i gadw golwg ar. Ond hollol i fyny i chi guys. Mae'n llawer mwy effeithlon yn y rhan fwyaf o achosion. Rydych chi eisiau mewn gwirionedd yn gallu cadw golwg ar eich holl awgrymiadau. Fel yn gwneud yr un peth fy mod yn ei wneud yma. Pan fyddwch yn ceisio ei fewnosod gwerthoedd mewn tabl hash neu ddileu, gwnewch yn siŵr eich bod yn 'n sylweddol cadw golwg o lle mae popeth yn oherwydd bod 'i' 'n sylweddol hawdd i os ydw i'n ceisio mewnosod fel y gair, andy. Gadewch i 'jyst yn dweud bod' na gair go iawn, y gair, andy, i mewn i restr enfawr o A eiriau. 

Os Fi jyst yn digwydd i ail-neilltuo yn anghywir pwyntydd, wps, mae mynd y cyfan o'r weddill fy rhestr cysylltiedig. Nawr bod yr unig air i mi wedi yw andy, ac yn awr pob un o'r geiriau eraill yn y Geiriadur wedi eu colli. Ac felly eich bod eisiau gwneud yn siŵr eich bod cadw golwg ar eich holl awgrymiadau neu arall rydych yn mynd i gael problemau anferth yn eich cod. Tynnwch pethau allan yn ofalus gam wrth gam. Mae'n ei gwneud yn llawer haws i feddwl am. 

Ac yn olaf, yr ydych am fod yn gallu brofi eich perfformiad eich rhaglen ar y bwrdd mawr. Os ydych yn guys yn cymryd edrych ar CS50 ar hyn o bryd, yr ydym wedi hyn a elwir y bwrdd mawr. Dyma'r daflen sgorio y cyflymaf sillafu amseroedd gwirio ar draws yr holl CS50 ar hyn o bryd, rwy'n meddwl bod y brig fel 10 gwaith yr wyf yn meddwl wyth ohonynt yn staff. Rydyn ni eisiau i chi guys i guro ni. 

Mae pob un ohonom yn ceisio gweithredu y cod cyflymaf ag y bo modd. Rydym am i chi guys i geisio herio ni a rhoi ar waith yn gyflymach nag pob un ohonom yn gallu. Ac felly mae hyn yn wir y tro cyntaf ein bod yn gofyn i chi guys i wneud hynny pset gallwch chi wir yn ei wneud ym mha bynnag ddull ydych ei eisiau. 

Rwyf bob amser yn dweud, mae hyn yn debycach i ateb go iawn, dde? Yr wyf yn ei ddweud, hey, mae angen i mi i chi wneud hyn. Adeiladu rhaglen sy'n gwneud hyn i mi. Ei wneud ar y bynnag y dymunwch. Fi jyst yn gwybod fy mod am ymprydio. Dyna eich her ar gyfer yr wythnos hon. Rydych guys, rydym yn mynd i roi tasg i chi. Rydym yn mynd i roi her i chi. Ac yna mae i fyny i chi guys i yn gyfan gwbl yn unig chyfrif i maes beth yw'r cyflymaf a mwyaf ffordd effeithlon i weithredu hyn. Yeah? 

GYNULLEIDFA: A ydym yn caniatáu i os Yn eisiau i ymchwilio i ffyrdd cyflymach i wneud tablau hash ar-lein, gallwn wneud hynny a dyfynnu cod rhywun arall? Andi Peng: Yeah, yn hollol iawn. Felly, os ydych guys yn darllen y spec, mae 'na linell yn y fanyleb sy'n dweud i chi guys yn gwbl rhad ac am ddim i ymchwilio i hash swyddogaethau ar beth yw rhai o swyddogaethau hash gyflymach i redeg pethau drwodd fel belled ag y byddwch yn nodi bod cod. Felly, mae rhai pobl yn barod cyfrifedig allan ffyrdd cyflym o wneud gwirwyr sillafu, o cyflym dulliau o storio gwybodaeth. Hollol i fyny i chi guys os ydych yn eisiau dim ond yn cymryd hynny, dde? Gwnewch yn siŵr eich bod yn nodi. Yr her yma 'n sylweddol ein bod yn ceisio ei brofi yn gwneud yn siŵr eich bod yn gwybod eich ffordd o gwmpas awgrymiadau. Cyn belled ag y byddwch yn gweithredu y swyddogaeth hash gwirioneddol ac yn dod i fyny gyda tebyg y math i wneud hynny, gallwch chi guys ymchwilio beth bynnag dulliau ar-lein i chi guys eisiau. Yeah? 

GYNULLEIDFA: Allwn ni sôn am ddim ond trwy ddefnyddio'r [Anghlywadwy]? 

Andi Peng: Yeah. Gallwch gyfiawn, yn eich sylwadau, gallwch ddyfynnu fel, o, a gymerwyd o yada, yada, yada, swyddogaeth hash. Dylai unrhyw un gennych unrhyw gwestiynau? Rydym breezed mewn gwirionedd drwy adran heddiw. Byddaf fod hyd yma i ateb cwestiynau hefyd. 

Hefyd, fel y dywedais, swyddfa Oriau heno ac yfory. Mae'r spec yr wythnos hon mewn gwirionedd super hawdd ac super byr i ddarllen. Byddwn yn awgrymu yn edrych, dim ond ddarllen drwy'r chyfanrwydd ohono. 

Ac Zamyla mewn gwirionedd yn cerdded i chi drwy bob un o'r swyddogaethau mae angen i chi weithredu, ac felly mae'n iawn, yn glir iawn sut i wneud popeth. Dim ond i wneud yn siŵr eich bod yn cadw golwg ar awgrymiadau. Mae hwn yn pset heriol iawn. 

Dyw hi ddim yn heriol oherwydd fel, oh, mae'r cysyniadau yn llawer mwy anodd, neu rhaid i chi ddysgu cymaint o gystrawen newydd y ffordd chi a wnaeth gyfer y pset diwethaf. Mae'r pset yn anodd oherwydd mae cymaint o awgrymiadau, ac yna mae'n iawn, yn hawdd iawn i'w unwaith gennych nam yn eich cod na fyddant yn gallu i ddod o hyd lle y byg yn. 

Ac felly yn gyflawn a ffydd llwyr ynoch chi guys i allu i guro ein [Anghlywadwy] sillafiadau. Fi 'n weithredol wedi nid unrhyw mwynglawdd ysgrifenedig eto, ond rwy'n ar fin i ysgrifennu pwll. Felly, tra eich bod yn ysgrifennu eich un chi, byddaf yn ysgrifennu pwll. Rydw i'n mynd i geisio gwneud mwynglawdd yn gyflymach na chi. Cawn weld pwy sydd â'r un cyflymaf. 

Ac ie, byddaf yn gweld pob un chi guys yma ar ddydd Mawrth. Byddaf yn rhedeg tebyg gweithdy pset. Mae pob un o'r adrannau hyn wythnos yn weithdai pset, er mwyn i chi guys yn cael llawer o gyfleoedd am gymorth, oriau swyddfa fel bob amser, ac Fi 'n sylweddol yn edrych ymlaen at darllen pob un cod eich guys '. Mae gen i cwisiau i fyny yma os ydych guys eisiau dod gael hynny. Dyna i gyd.