SIARADWR 1: pob hawl, felly rydym yn ôl. Croeso i CS50. Mae hyn yn y diwedd yr wythnos saith. Felly, dwyn i gof bod y tro diwethaf, rydym yn dechrau edrych ar ychydig yn fwy soffistigedig strwythurau data. Ers hyd yn hyn, i gyd oedd gennym mewn gwirionedd ar gael i ni oedd hyn, arae. 

Ond cyn i ni daflu y casgliad gan nad bob un sy'n ddiddorol, sydd yn wir mae'n mewn gwirionedd yw, beth yw rhai o'r pwyntiau cadarnhaol o'r data syml strwythur hyd yn hyn? Beth yw ei dda? Cyn belled ag yr ydym wedi gweld? Beth ydych chi'n ei gael? Dim byd. 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Beth sy'n bod? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: faint sefydlog. Iawn, felly pam mae maint sefydlog da er bod? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: OK, felly mae'n effeithlon yn yr ystyr eich bod yn gallu dyrannu swm penodol o le, a gobeithio, yn union gymaint gofod ag y dymunwch. Fel y gallai fod yn hollol yn fantais. 

Beth sydd i fyny ochr arall o fyrdd? Yeah? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Mae'r holl - mae'n ddrwg gennyf? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Pob y blychau er cof neu nesaf at ei gilydd. Ac mae hynny'n ddefnyddiol - pam? Mae hynny'n hollol wir. Ond sut y gallwn fanteisio ar y gwirionedd? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Yn union, gallwn gadw golwg ar lle mae popeth yn unig trwy wybod un cyfeiriad, sef gyfeiriad y beit cyntaf y darn o gof. Neu yn achos y llinyn, cyfeiriad y cyntaf torgoch yn y llinyn. Ac oddi yno, gallwn ddod o hyd i ddiwedd y llinyn. Gallwn ddod o hyd i'r ail elfen, y drydedd elfen, ac yn y blaen. 

Ac felly y ffordd ffansi o ddisgrifio bod nodwedd yw bod araeau yn rhoi i ni mynediad ar hap. Dim ond drwy ddefnyddio'r sgwâr braced nodiant a nifer, gallwch neidio i elfen benodol yn yr arae mewn amser yn gyson, O mawr o un, fel petai. 

Ond mae wedi bod rhai anfanteision. Beth amrywiaeth beidio â gwneud yn hawdd iawn? Beth sydd ddim yn dda? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Beth sy'n bod? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Ehangu o ran maint. Felly anfanteision y rhesi yn union y gwrthwyneb i'r hyn y mae'r upsides yn cael eu. Felly, un o anfanteision yn ei fod yn faint penodol. Felly, ni allwch gynyddu. Gallwch ailddyrannu mwy darn o cof, ac yna symud yr hen elfennau yn y casgliad newydd. Ac yna ddim yr hen amrywiaeth, ar gyfer enghraifft, trwy ddefnyddio malloc neu debyg swyddogaeth o'r enw realloc, sy'n ailddyrannu cof. 

Realloc, wrth fynd heibio, yn ceisio rhoi i chi cof sy'n nesaf at y casgliad sydd gennych yn barod. Ond gallai symud pethau amgylch yn gyfan gwbl. Ond yn fyr, mae hynny'n ddrud, dde? Oherwydd os oes gennych darn o cof am maint hwn, ond ydych wir eisiau un o'r maint hwn, ac rydych am i gadw yr elfennau gwreiddiol, mae gennych fras broses copïo amser llinol sydd angen i ddigwydd o hen amrywiaeth i newydd. Ac mae'r realiti yn gofyn i'r gweithredu system eto ac eto ac eto am y gall darnau mawr o gof yn dechrau i gostio i chi rhywfaint o amser yn ogystal. Felly mae'n yn fendith ac yn felltith mewn cuddio'r, y ffaith bod arrays hyn o faint penodol. Ond os ydym yn cyflwyno rhywbeth yn lle hynny fel hyn, yr ydym yn a elwir yn gysylltiedig rhestr, rydym yn cael ychydig o upsides a ychydig o anfanteision yma hefyd. 

Felly restr cysylltiedig yn unig yw ddata strwythur sy'n cynnwys structs C yn y achos, lle mae strwythur, galw i gof, yn unig cynhwysydd ar gyfer un neu fwy penodol mathau o newidynnau. Yn yr achos hwn, beth yn gwneud y mathau o ddata ymddangos i fod y tu mewn i'r strwythur y tro diwethaf i ni a elwir yn nod? Mae pob un o'r petryalau hyn yn nod. A phob un o'r petryalau llai tu mewn iddo yn fath data. Pa fathau wnaethom ni ddweud eu bod ar ddydd Llun? Yeah? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: amrywiol a pwyntydd, neu yn fwy penodol, yn int, ar gyfer n, a pwyntydd ar y gwaelod. Mae'r ddau o'r rheiny yn digwydd i fod yn 32 darnau, yn leiaf ar gyfrifiadur fel hyn CS50 Offer, ac felly eu bod yn tynnu yn gyfartal o ran maint. 

Felly, beth yn defnyddio'r pwyntydd er bod ar gyfer pob golwg? Pam ychwanegu saeth hwn yn awr pan fydd araeau oedd mor neis ac yn lân ac yn syml? Beth yw y pwyntydd wneud dros i ni ym mhob un o'r nodau hyn? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Yn union. Mae'n dweud wrthych lle yr un nesaf. Felly yr wyf yn fath o ddefnyddio'r gyfatebiaeth o defnyddio edau i ddatrys y edafu nodau hyn gyda'i gilydd. A dyna'n union yr hyn rydym yn ei wneud gyda awgrymiadau gan fod pob un o'r rhain darnau o gof efallai na all neu fod yn cydgyffwrdd, gefn wrth gefn wrth gefn tu mewn RAM, oherwydd bod gan bob tro y byddwch yn ffoniwch malloc dweud, yn rhoi digon i mi bytes am nod newydd, y gallai fod yma neu gallai fod yma. Efallai ei fod yma. Efallai ei fod yma. Dim ond nad ydych yn gwybod. 

Ond yn defnyddio arwyddion yn y cyfeiriadau nodau hynny, gallwch pwyth iddynt at ei gilydd mewn ffordd sy'n edrych ar eu golwg fel rhestr hyd yn oed os yw'r pethau hyn yn pob gwasgaru drwy gydol eich un neu eich dau neu eich bedwar gigabeit o RAM tu mewn i'ch cyfrifiadur eich hun. 

Felly mae'r anfantais, yna, wrth restr cysylltiedig yw beth? Beth yw pris rydym yn yn ôl pob golwg yn talu? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Mwy o le, dde? Rydym wedi, yn yr achos hwn, dyblu y swm o le oherwydd ein bod wedi mynd o 32 ddarnau ar gyfer pob nod, ar gyfer pob int, felly, yn awr 64 o ddarnau oherwydd bod yn rhaid i cadw o amgylch pwyntydd hefyd. Byddwch yn cael mwy effeithlon os yw eich strwythur yn fwy na hyn peth syml. Os ydych chi mewn gwirionedd yn cael fyfyriwr y tu mewn un ohonynt yn ychydig o linynnau ar gyfer enw a thy, efallai rhif adnabod, efallai rhai meysydd eraill yn gyfan gwbl. 

Felly, os oes gennych strwythur ddigon mawr, yna efallai cost y pwyntydd yn Nid yw mor bwysig â hynny. Mae hwn yn dipyn o achos cornel yn y rydym yn storio cyntefig mor syml tu mewn i'r rhestr cysylltiedig. Ond y pwynt yw yr un fath. Rydych yn sicr yn gwario mwy cof, ond eich bod yn cael hyblygrwydd. Oherwydd erbyn hyn os ydw i eisiau ychwanegu elfen ar ddechrau'r y rhestr hon, Rhaid i mi ddyrannu nod newydd. Ac mae'n rhaid i mi jyst diweddaru rhai saethau rywsut at jyst yn symud rhai awgrymiadau o gwmpas. 

Os ydw i eisiau rhoi rhywbeth i mewn i'r nghanol y rhestr, nid oes rhaid i mi gwthio pawb o'r neilltu fel y gwnaethom yn wythnos diwethaf gyda'n gwirfoddolwyr sy'n yn cynrychioli amrywiaeth. Gall Fi jyst dyrannu nod newydd ac yna dim ond dangos y saethau mewn cyfarwyddiadau wahanol oherwydd nad yw'n rhaid i chi aros yn wirioneddol cof linell wir fy mod wedi tynnu yma ar y sgrin. 

Ac yna yn olaf, os ydych am i fewnosod rhywbeth ar ddiwedd y rhestr, mae'n hyd yn oed yn haws. Mae hyn yn fath o nodiant mympwyol, ond mae pwyntydd 34, yn cymryd dyfalu. Beth yw gwerth ei pwyntydd y rhan fwyaf o math tynnu tebygol fel hen antena ysgol yno? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Mae'n debyg null. Ac yn wir dyna un awdur cynrychiolaeth o null. Ac mae'n null oherwydd eich bod yn hollol angen i ni wybod ble ddiwedd cysylltiedig rhestr yw, rhag eich bod yn cadw canlynol ac dilyn ac yn dilyn y saethau hyn i ryw werth garbage. Felly bydd null arwydd nad oes unrhyw mwy o nodau i'r dde o'r rhif 34, yn yr achos hwn. 

Felly, rydym yn cynnig ein bod yn gallu gweithredu nod hwn mewn cod. Ac rydym wedi gweld y math hwn ar gystrawen blaen. Typedef yn unig yn diffinio math newydd ar gyfer ni, yn rhoi gyfystyr ni fel llinyn oedd torgoch *. Yn yr achos hwn, mae'n mynd i roi i ni nodiant llaw-fer fel bod strwythur nod Gellir hytrach dim ond ei ysgrifennu fel nod, sydd yn llawer glanach. Mae'n llawer llai verbose. 

Y tu mewn o nod yn ôl pob golwg yn int n galw, ac yna strwythur nod * sy'n golygu yn union yr hyn yr ydym am i'r saethau i olygu, pwyntydd i un arall nod y math data union un fath. Ac yr wyf yn cynnig y gallem gweithredu swyddogaeth chwilio fel hyn, sydd ar hyn o Efallai yr olwg gyntaf yn ymddangos ychydig o gymhleth. Ond gadewch i ni ei weld yn y cyd-destun. 

Gadewch i mi fynd draw at y peiriant yma. Gadewch i mi agor ffeil o'r enw rhestr sero dot h. Ac mai dim ond yn cynnwys y diffiniad yr ydym jyst yn gweld funud yn ôl am y data hwn math a elwir yn nod. Felly, rydym wedi rhoi bod i mewn i ffeil h dot. 

Ac wrth fynd heibio, er bod hyn rhaglen eich bod chi ar fin ei weld yw nid bob un sy'n gymhleth, mae'n wir confensiwn wrth ysgrifennu rhaglen i rhoi pethau fel mathau o ddata, i dynnu cysonion weithiau, y tu mewn eich ffeil flaen ac nid o reidrwydd yn eich ffeil C, yn sicr pan fydd eich rhaglenni fynd yn fwy ac yn fwy, fel y eich bod yn gwybod ble i chwilio ar gyfer dogfennau mewn rhai achosion, neu ar gyfer nwyddau sylfaenol fel hyn, mae'r diffiniad o ryw fath. 

Os wyf yn awr yn agor rhestr sero dot c, sylwi ar ychydig o bethau. Mae'n cynnwys ychydig o ffeiliau pennawd, y rhan fwyaf o yr ydym wedi ei weld o'r blaen. Mae'n cynnwys ei ffeil flaen ei hun. 

Ac wrth fynd heibio, pam mae hynny'n ddwbl dyfyniadau yma, yn hytrach na'r ongl cromfachau ar y llinell sy'n Rwyf wedi tynnu sylw yno? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Yeah felly mae'n ffeil lleol. Felly, os yw'n ffeil lleol eich hunain yma on line 15, er enghraifft, byddwch yn defnyddio y dyfyniadau dwbl yn lle hynny y cromfachau onglog. 

Nawr mae hyn yn fath o ddiddorol. Hysbysu fy mod wedi datgan byd-eang amrywiol yn y rhaglen hon ar-lein 18 a elwir yn gyntaf, y syniad yw hyn yn mynd i fod yn pwyntydd i'r gyntaf nod yn fy rhestr gysylltiedig, ac rwyf wedi ymgychwyn iddo null, gan fy mod i wedi heb ei dyrannu unrhyw ostyngiad gwirioneddol nodau eto. 

Felly, mae hyn yn cynrychioli, ar ffurf lluniau, yr hyn yr ydym Gwelodd funud yn ôl yn y llun fel y pwyntydd ar y graddau y gadael ochr llaw. Felly, ar hyn o bryd, y pwyntydd Nid oes gan saeth. Mae'n lle hynny yn unig null. Ond mae'n cynrychioli beth fydd y chyfeiriad y gwir cyntaf nod yn y rhestr hon. Felly, yr wyf wedi rhoi ar waith ei fod yn fyd-eang oherwydd, fel y gwelwch, hyn i gyd mewn bywyd rhaglen yn ei wneud yw gweithredu rhestr gysylltu i mi. 

Nawr mae gen i ychydig o prototeipiau yma. Penderfynais i weithredu nodweddion fel dileu, mewnosod, chwilio, a llwybro - y daith olaf dim ond bod ar draws y rhestr, argraffu ei elfennau. Ac yn awr dyma fy mhrif arferol. Ac ni fyddwn yn treulio gormod o amser ar hyn gan fod hyn yn fath o, gobeithio hen het erbyn hyn. 

Rydw i'n mynd i wneud y canlynol, tra bod y defnyddiwr yn cydweithio. Felly un, yr wyf i'n mynd i argraffu ar y fwydlen. Ac yr wyf wedi fformatio fel lân ag y gallwn. Os mathau y defnyddiwr mewn un, mae hynny'n golygu maent am ei ddileu rhywbeth. Os mathau y defnyddiwr mewn dau, mae hynny'n golygu maent am i fewnosod rhywbeth. Ac yn y blaen. Rydw i'n mynd i wedyn yn ysgogi yna am orchymyn. Ac yna dwi'n mynd i ddefnyddio GetInt. 

Felly, mae hwn yn menuing syml iawn rhyngwynebu lle os oes gen ti i deipio rhif mapio i un o orchmynion hynny. Ac yn awr yr wyf wedi switsh glân 'n glws datganiad sy'n mynd i newid ar beth bynnag y defnyddiwr deipio i mewn Ac os ydynt yn teipio un, byddaf yn ffoniwch dileu a thorri. Os ydynt yn teipio ddau, byddaf ffoniwch mewnosod a torri. 

Ac yn awr rhybudd rwyf wedi rhoi pob y rhain ar yr un llinell. Penderfyniad arddull yn unig yw hwn. Fel arfer, rydym wedi gweld rhywbeth fel hyn. Ond Fi jyst benderfynu, a dweud y gwir, fy rhaglen edrych yn fwy darllenadwy oherwydd dim ond pedwar achos i dim ond rhestru fel hyn. Defnydd gwbl gyfreithlon o arddull. Ac yr wyf i'n mynd i wneud hyn cyhyd ag y Nid yw'r defnyddiwr wedi teipio ddim, yr wyf yn penderfynu y byddant yn golygu eu bod eisiau rhoi'r gorau iddi. 

Felly sylwi ar beth dw i'n mynd i'w wneud yma. Rydw i'n mynd i ryddhau y rhestr yn ôl pob golwg. Ond mwy am hynny mewn dim ond hyn o bryd. Gadewch i ni yn gyntaf yn rhedeg y rhaglen hon. Felly, gadewch i mi wneud mwy o derfynell ffenestr, dot rhestr slaes 0. Rydw i'n mynd i fynd yn ei flaen ac yn mewnosod gan teipio dau, mae nifer tebyg i 50, ac yn awr byddwch yn gweld y rhestr yn awr yn 50. Ac mae fy testun yn unig sgrolio i fyny ychydig. Felly, erbyn hyn yn sylwi ar y rhestr hon yn cynnwys y rhif 50. 

Gadewch i ni wneud mewnosoder arall drwy gymryd dau. Gadewch i deipio yn y nifer fel un. Rhestr bellach yn un, ac yna 50. Felly cynrychiolaeth testunol hyn yn unig y rhestr. A gadewch i ni ychwanegu un yn fwy rhif, er enghraifft y rhif 42, sy'n gobeithio yn mynd i roi diwedd ar i fyny yn y canol, gan fod rhaglen hon yn fath arbennig, elfennau y mae'n mewnosod nhw. Felly mae gennym. Rhaglen syml super a allai gwbl wedi defnyddio amrywiaeth, ond yr wyf yn digwydd bod yn defnyddio rhestr gysylltiedig yn union fel y gallaf ddeinamig tyfu ac yn crebachu ei. 

Felly, gadewch i ni edrych ar gyfer chwilio, os wyf rhedeg gorchymyn tri, yr wyf am i chwilio am, dyweder, y rhif 43. A dim byd Daethpwyd o hyd yn ôl pob golwg, oherwydd fy mod yn cael unrhyw ymateb yn ôl. Felly, gadewch i ni wneud hyn eto. Chwilio. Gadewch i ni chwilio am 50, neu yn hytrach chwilio am 42, sydd â 'n glws ychydig o ystyr cynnil. Ac yr wyf yn dod o hyd i'r ystyr bywyd yno. Rhif 42, os nad ydych yn gwybod y cyfeiriad, Google. Mae pob hawl. Felly, beth mae hyn rhaglen wneud i mi? 'I' jyst fy ngalluogi i fewnosod a thrwy hynny bell ac yn chwilio am elfennau. 

Gadewch i ni yn gyflym ymlaen, yna, er mwyn swyddogaeth honno rydym yn bwrw golwg ar ar ddydd Llun fel ymlid. Felly swyddogaeth hon, yr wyf yn gwneud cais, chwilio am elfen yn y rhestr gan gyntaf un, gan annog y defnyddiwr ac yna galw GetInt i gael int gwirioneddol eich bod am chwilio am. 

Yna sylwi ar hyn. Rydw i'n mynd i greu newidyn dros dro yn unol 188 enw pwyntydd - PTR - gallai fod wedi ei alw unrhyw beth. Ac mae'n pwyntydd i nod oherwydd dywedais nod * yno. A dwi'n ymgychwyn i fod yn hafal i yn gyntaf er mwyn i mi gael fy effeithiol bys, fel petai, ar yr union Elfen gyntaf y rhestr. Felly, os bydd fy llaw dde yma yw PTR rwy'n pwyntio at yr un peth yn gyntaf yn pwyntio at. 

Felly, bellach yn ôl mewn cod, beth sy'n digwydd nesaf - mae hwn yn batrwm cyffredin wrth ailadrodd dros strwythur fel restr cysylltiedig. Rydw i'n mynd i wneud y canlynol wrth Nid pwyntydd yn hafal i null Felly, er Nid yw fy bys yn pwyntio ar ryw null gwerth, os pwyntydd saeth n hafal n. Byddwn yn sylwi gyntaf y n yw yr hyn y mae'r defnyddiwr deipio yn y GetInts galw yma. 

Ac pwyntydd saeth n golygu beth? Wel, os ydym yn mynd yn ôl at y llun yma, os oes gen i bys bwyntio at y nod cyntaf yn cynnwys naw, y saeth yn ei hanfod yn golygu mynd i'r nod a chrafangia 'r gwerth yn y lleoliad n, yn yr achos hwn, roedd y maes data a elwir yn n. 

Fel o'r neilltu - ac yr ydym yn gweld hyn cwpl o wythnosau yn ôl pan ofynnir i rywun - chystrawen hyn yn newydd, ond nid yw'n yn rhoi pwerau i ni ein bod yn Nid oedd wedi gwneud hynny'n barod. Beth oedd hyn yn ymadrodd sy'n cyfateb i ddefnyddio dot nodiant a seren cwpl o wythnosau yn ôl pan fyddwn yn plicio yn ôl haen hwn ychydig cyn pryd? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Yn union, roedd yn seren, ac yna roedd seren dot n, gyda cromfachau yma, sy'n edrych, dweud y gwir, yr wyf yn credu bod llawer mwy cryptig i ddarllen. Ond seren pwyntydd, fel bob amser, modd mynd yno. Ac unwaith y byddwch chi yno, pa ddata maes yn ydych chi am gael mynediad? Dda yr ydych yn defnyddio'r nodiant dot i gael mynediad at maes data structs, ac yr wyf yn benodol eisiau n. 

Dweud y gwir, byddwn yn dadlau hyn yn unig yn fwy anodd i'w darllen. Mae'n anoddach i gofio lle yn y cromfachau mynd, y seren a hynny i gyd. Felly, yn y byd mabwysiadu rhai cystrawennol siwgr, fel petai. Dim ond ffordd sexy o ddweud, mae hyn yn gyfwerth, a efallai yn fwy 'n athrylithgar. Os pwyntydd yn wir yn pwyntydd, y arrow nodiant yn golygu mynd yno ac yn dod o hyd i maes yn yr achos hwn a elwir yn n. 

Felly os wyf yn ei chael yn, sylwi ar yr hyn yr wyf yn ei wneud. Yr wyf yn syml argraffu, yr wyf yn dod o hyd cant i, llenwi yn y gwerth ar gyfer y int. Galwaf cysgu am un eiliad yn unig i fath o bethau oedi ar y sgrin i rhoi'r defnyddiwr yn ail i amsugno beth yn union ddigwyddodd. Ac yna mi dorri. Fel arall, beth ddylwn i ei wneud? Byddaf yn diweddaru'r pwyntydd i gyfleoedd cyfartal arrow pwyntydd nesaf. 

Felly, dim ond i fod yn glir, mae hyn yn golygu mynd yno, gan ddefnyddio fy hen nodiant-ysgol. Felly mae hyn yn unig yn golygu i fynd i ba bynnag eich bod yn tynnu sylw at, sydd yn yr union achos cyntaf yw i ddim yn pwyntio at y strwythur gyda naw ynddo. Felly, yr wyf wedi mynd yno. Ac yna y nodiant dot yn golygu, cael y gwerth arno nesaf. 

Ond mae'r werth, hyd yn oed er ei fod yn tynnu fel gul, yn unig yw rhif. Mae'n cyfeiriad rhifol. Felly, un llinell o god hwn, p'un a ysgrifenedig fel hyn, y mwyaf cryptig ffordd, neu fel hyn, mae ychydig yn fwy ffordd sythweledol, yn unig yn golygu symud fy llaw oddi wrth y nod cyntaf i'r un nesaf, ac yna yr un nesaf, ac yna un nesaf, ac yn y blaen. 

Felly, ni fyddwn yn trigo ar y llaw arall gweithrediadau o mewnosod a dileu a llwybro, y ddau gyntaf sydd yn ymwneud yn deg. Ac yr wyf yn meddwl ei fod yn eithaf hawdd i gael colli wrth wneud hynny ar lafar. Ond beth y gallwn ei wneud yma yw ceisio penderfynu sut orau o wneud hyn ar eu golwg. Oherwydd byddwn yn cynnig, os ydym yn eisiau i fewnosod elfennau i mewn i hyn rhestr bresennol, sy'n Mae pum elfen - 9, 17, 22, 26, a 33 - os wyf yn mynd i roi hyn ar waith yn cod, angen i mi ystyried sut i fynd am wneud hyn. 

A byddwn yn cynnig cymryd camau babi lle, yn yr achos hwn yr wyf yn golygu, beth yw'r y senarios posibl ein bod yn allai ddod ar eu traws yn gyffredinol? Wrth weithredu mewnosoder ar gyfer cysylltiedig rhestr, mae hyn yn unig fydd yn digwydd i fod yn enghraifft benodol o faint bump. Wel, os ydych am osod nifer, yn hoffi dweud y rhif un, ac cadw trefn didoli, lle amlwg â nifer angen un mynd yn yr enghraifft benodol? Fel ar y dechrau. 

Ond yr hyn sy'n ddiddorol yw bod yna os ydych am i fewnosod un i mewn i hyn rhestr, mae angen yr hyn y pwyntydd arbennig i gael ei diweddaru yn ôl pob golwg? Yn gyntaf. Felly, byddwn yn dadlau, mae hyn yn yr achos cyntaf y byddem efallai am ystyried, a senario sy'n cynnwys mewnosod ar ddechrau'r rhestr. 

Gadewch i ni tyn i ffwrdd efallai mae mor hawdd neu hyd yn oed achos yn haws, yn gymharol siarad. Gadewch i ni dybio Yr wyf am i mewnosoder y rhif 35 er mwyn didoli. Mae'n amlwg yn perthyn dros yno. Felly, yr hyn y pwyntydd yn amlwg yn mynd i rhaid ei ddiweddaru yn y sefyllfa honno? Pwyntydd 34 yn dod yn Nid null ond y cyfeiriad y strwythur yn cynnwys y rhif 35. Felly dyna achos dau. Hynny eisoes, rwy'n fath o quantizing faint o waith rhaid i mi ei wneud yma. 

Ac yn olaf, yr achos canol amlwg yw yn wir, yn y canol, os wyf am mewnosod rhywbeth fel dweud 23, sy'n mynd rhwng y 23 a'r 26, ond nawr pethau'n mynd ychydig yn fwy cymryd rhan oherwydd yr hyn angen newid awgrymiadau? Felly 22 yn amlwg angen ei newid oherwydd ni all bwyntio at 26 anymore. Mae angen i dynnu sylw at y nod newydd sy'n Bydd rhaid i mi ddyrannu drwy ffonio malloc neu ryw cyfwerth. 

Ond yna yr wyf hefyd angen i nod newydd, 23 yn yr achos hwn, i gael ei pwyntydd pwyntio at bwy? 26. Ac mae mynd i fod yn trefn y gweithrediadau yma. Oherwydd os wyf yn gwneud hyn yn ffôl, ac yr wyf yn er enghraifft, cychwyn ar ddechrau y rhestr, a fy nod yw gosod 23. Ac yr wyf yn gwirio, a yw'n perthyn yma, ger naw? Rhif A yw'n perthyn yma, y ​​drws nesaf i 17? Rhif A yw'n perthyn yma nesaf i 22? Ydw. 

Nawr, os ydw i'n ffôl yma, ac nid meddwl hyn drwy, efallai y byddaf ddyrannu fy nod newydd ar gyfer 23. Efallai fy mod yn diweddaru'r pwyntydd o y nod a elwir yn 22, pwyntio hynny ar y nod newydd. Ac yna beth sy'n rhaid i mi ei ddiweddaru pwyntydd y nod newydd i fod? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Yn union. Pwyntio at 26. Ond dammit os nad oeddwn yn diweddaru eisoes Pwyntydd 22 i bwyntio at y boi, a nawr mae gen i blant amddifad, y gweddill y rhestr, fel petai. Felly, trefn y gweithrediadau yma yn mynd i fod yn bwysig. 

I wneud hyn y gallwn ddwyn, dyweder, chwe gwirfoddolwr. A gadewch i ni weld os na allwn wneud hyn weledol yn hytrach na cod-ddoeth. Ac mae gennym rai straen hyfryd peli i chi heddiw. OK, beth am un, dau, yn y yn ôl - ar y diwedd. tri, pedwar, y ddau ohonoch guys ar y diwedd. Ac pump, chwech. Cadarn. Pump a chwech. Mae pob hawl a byddwn yn dod i chi guys tro nesaf. Mae pob hawl, yn dod ar i fyny. 

Mae pob hawl, gan eich bod hyd yma yn gyntaf, yr hoffech i fod yn un lletchwith yn Google Gwydr yma? Mae pob hawl, felly, OK, Gwydr, recordio fideo. OK, rydych yn dda i fynd. 

Mae pob hawl, felly os gallwch chi guys ddod draw yma, yr wyf wedi paratoi ymlaen llaw rhai rhifau. Mae pob hawl, dewch draw yma. A pham nad ydych chi'n mynd ychydig ymhellach y ffordd honno. A gadewch i ni weld, beth yw eich enw, gyda'r Glass Google? 

MYFYRWYR: Ben. 

SIARADWR 1: Ben? OK, Ben, byddwch yn gyntaf, yn llythrennol. Felly, rydym yn mynd i anfon at ddiwedd y cyfnod. Mae pob hawl, a bod eich enw? 

MYFYRWYR: Jason. 

SIARADWR 1: Jason, OK wnewch chi helpu fod yn rhif naw. Felly, os ydych am ddilyn Ben y ffordd honno. 

MYFYRWYR: Jill. 

SIARADWR 1: Jill, rydych yn mynd i fod yn 17, ac os byddwn i'n gwneud hyn yn fwy ddeallus, byddai gennyf ddechrau yn y pen arall. Rydych yn mynd y ffordd honno. 22. A ydych chi? 

MYFYRWYR: Mary. 

SIARADWR 1: Mary, byddwch yn 22. A yw eich enw? 

MYFYRWYR: Chris. 

SIARADWR 1: Chris, byddwch yn 26. Ac yna yn olaf. 

MYFYRWYR: Diana. 

SIARADWR 1: Diana, byddwch yn 34. Felly, byddwch yn dod ar dros yma. 

Mae pob hawl, felly berffaith datrys archebu eisoes. A gadewch i ni fynd yn ei flaen ac yn gwneud hyn fel ein bod yn gallu mewn gwirionedd - Ben ydych ond yn fath o edrych allan i'r unman yno. Iawn, felly gadewch i ni fynd yn ei flaen ac yn darlunio hyn ddefnyddio breichiau, yn debyg iawn oeddwn i, yn union, beth sy'n mynd ymlaen. Felly, mynd yn ei flaen ac yn rhoi eich hunain a droed neu ddau rhwng eich gilydd. Ac yn mynd yn ei flaen ac yn pwyntio gydag un llaw i pwy bynnag dylech fod yn pwyntio at yn seiliedig ar hyn. Ac os ydych yn null dim ond tynnu sylw yn syth i lawr i'r llawr. Iawn, felly da. 

Felly nawr mae gennym restr cysylltiedig, a gadewch i mi cynnig y byddaf yn chwarae rôl y PTR, felly nid wyf am drafferthu cario o gwmpas hyn. Ac yna - rhywun confensiwn dwp - gallwch ffonio unrhyw beth rydych am yma - pwyntydd rhagflaenydd, pwyntydd pred - dim ond y llysenw roddasom yn ein cod enghreifftiol at fy llaw chwith. Y llaw arall fod yn mynd i gael eu cadw olrhain pwy yw pwy yn y dilyn senarios. 

Felly, mae'n debyg, yn gyntaf, yr wyf am tyn i ffwrdd yr enghraifft gyntaf o mewnosod, yn dweud 20, i mewn i'r rhestr. Felly, yr wyf i'n mynd i angen rhywun i ymgorffori'r rhif 20 i ni. Felly mae angen i malloc rhywun rwy'n gan y gynulleidfa. Dewch ar i fyny. Beth yw eich enw? 

MYFYRWYR: Brian. 

SIARADWR 1: Brian, popeth yn iawn, er mwyn i chi fydd y nod sy'n cynnwys 20. Mae pob hawl, dewch draw yma. Ac yn amlwg, lle mae Brian yn perthyn? Felly, yng nghanol - mewn gwirionedd, arhoswch funud. Rydym yn gwneud hyn allan o drefn. Rydym yn gwneud hyn yn llawer anoddach nag y mae angen iddo fod ar y dechrau. OK, rydym yn mynd i ddim Brian a realloc Brian â phump. 

Iawn, felly nawr rydym am i fewnosod Brian â phump. Felly dewch ar dros yma nesaf i Ben am ddim ond ennyd. A allwch ddweud yn ôl pob tebyg lle y stori hon yn mynd. Ond gadewch i ni feddwl yn ofalus am trefn y gweithrediadau. Ac mae'n union hyn yn weledol sy'n mynd i linell i fyny â'r cod enghreifftiol. Felly dyma rwyf wedi PTR pwyntio i ddechrau nid ar Ben, fel y cyfryw, ond ar ba bynnag gwerthfawrogi ei fod yn cynnwys, sydd, yn yr achos hwn yw - beth yw eich enw eto? 

MYFYRWYR: Jason. 

SIARADWR 1: Jason, felly mae Ben a minnau yn pwyntio at Jason ar hyn o bryd. Felly, yn awr mae'n rhaid i mi benderfynu, ble mae Brian yn perthyn? Felly, yr unig beth yr wyf yn cael mynediad at ar hyn o bryd yw ei n eitem ddata. Felly, yr wyf i'n mynd i wirio, yn cael ei Brian llai na Jason? Yr ateb yn wir. 

Felly beth sydd angen digwydd yn awr, yn y drefn gywir? Mae angen i mi ddiweddaru faint o arwyddion i gyd yn y stori hon? Lle mae fy llaw yn dal i bwyntio at Jason, a bod eich llaw - os ydych am rhowch eich llaw fel, math o, yr wyf yn ddim yn gwybod, marc cwestiwn. OK, yn dda. 

Mae pob hawl, felly mae gennych ychydig o ymgeiswyr. Naill ai Ben neu I neu Brian neu Jason neu bawb arall, a Mae angen awgrymiadau i newid? Sawl cyfanswm o? 

Iawn, felly dau. Nid yw fy pwyntydd oes ots anymore oherwydd fy mod yn unig dros dro. Felly mae'n y ddau guys, yn ôl pob tebyg, ddau Ben a Brian. Felly, gadewch i mi cynnig ein bod yn diweddaru Ben, gan ei fod yn gyntaf. Yr elfen gyntaf y rhestr yn awr yn mynd i fod Brian. Felly Ben pwynt Brian. OK, yn awr beth? 

Pwy sy'n cael sylw ar bwy? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Iawn felly Brian wedi bwyntio at Jason. Ond yr wyf wedi colli golwg ar y pwyntydd? Ydw i'n gwybod ble mae Jason yn? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Yr wyf yn ei wneud, gan fy mod i'n y pwyntydd dros dro. Ac yn ôl pob tebyg, nid wyf wedi newid bwyntio at y nod newydd. Felly, gallwn ni gael Brian bwynt ar bwy bynnag Rwy'n bwyntio at. Ac rydym yn ei wneud. Felly un achos, gosod yn y ddechrau'r rhestr. Roedd dau gam allweddol. Un, mae'n rhaid i ni ddiweddaru Ben, ac yna rydym hefyd wedi diweddaru Brian. Ac yna nid oes rhaid i mi drafferthu troedio trwy weddill y rhestr, gan ein bod eisoes o hyd i'w lleoliad, oherwydd ei fod yn perthyn i'r Gadawodd yr elfen gyntaf. 

Mae pob hawl, mor bert syml. Yn wir, yn teimlo fel ein bod bron gwneud hyn yn rhy gymhleth. Felly, gadewch i ni yn awr dynnaf oddi ar y diwedd y rhestr, a gweld lle cymhlethdod yn dechrau. Felly os awr, yr wyf Dyraniad gan y gynulleidfa. Dylai unrhyw un sydd eisiau chwarae 55? Mae pob hawl, gwelais eich llaw yn gyntaf. Dewch ar i fyny. Yeah. Beth yw eich enw? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Habata. OK, yn dod ar i fyny. Byddwch yn rhif 55. Felly chi, wrth gwrs, yn perthyn ar ddiwedd y rhestr. Felly, gadewch i ni ail-chwarae yr efelychiad gyda mi sef y PTR am ddim ond ennyd. Felly, yr wyf i'n gyntaf yn mynd i bwyntio at beth bynnag Ben sy'n pwyntio at. Rydym yn ddau pwyntio nawr ar Brian. Felly 55 heb fod yn llai na phump. Felly, yr wyf i'n mynd i ddiweddaru fy hun gan pwyntio at pwyntydd nesaf Brian, a oedd yn awr yw, wrth gwrs, Jason. 55 heb fod yn llai na naw, felly Rydw i'n mynd i ddiweddaru PTR. Rydw i'n mynd i ddiweddaru PTR. Rydw i'n mynd i roi'r wybodaeth ddiweddaraf PTR I'n mynd i ddiweddaru PTR. Ac yr wyf i'n mynd i - hmm, beth eich enw eto? 

MYFYRWYR: Diana. 

SIARADWR 1: Diana yn pwyntio, wrth gwrs, yn null â'i llaw chwith. Felly, lle mae Habata mewn gwirionedd perthyn yn glir? I'r chwith, yma. Felly, sut ydw i'n gwybod i roi ei Yma Rwy'n credu fy mod i wedi sgriwio i fyny. Oherwydd mae'r hyn sy'n PTR celf hyn o bryd? NULL. Felly, hyd yn oed er, yn weledol, gallwn yn amlwg yn gweld pob un o'r rhain guys yma ar y llwyfan. Nid wyf wedi cadw golwg ar y flwyddyn flaenorol person yn y rhestr. Nid oes gennyf bys yn pwyntio allan, yn yr achos hwn, mae nifer nôd 34. 

Felly, gadewch i ni mewn gwirionedd yn dechrau dros y. Felly, yn awr yr wyf ei angen mewn gwirionedd ail newidyn lleol. Ac mae hyn yn yr hyn y byddwch yn ei weld yn y gwirioneddol côd sampl C, lle fel yr wyf yn mynd, pan fyddaf yn diweddaru fy llaw dde i bwynt Jason, gan adael y tu ôl i Brian, yr wyf yn well dechrau defnyddio fy llaw chwith i diweddaru lle'r oeddwn, fel bod gan fy mod yn mynd drwy'r rhestr hon - yn fwy lletchwith nag yr oeddwn yn bwriadu bellach yma ar eu golwg - Rydw i'n mynd i gyrraedd y ddiwedd y rhestr. 

Mae'r llaw yn dal yn null, sydd yn eithaf ddiwerth, ac eithrio i nodi Rwy'n glir ar ddiwedd y rhestr, ond erbyn hyn o leiaf yr wyf wedi hyn pwyntydd rhagflaenydd pwyntio yma, felly dwylo yn awr beth a beth sydd angen awgrymiadau i gael ei diweddaru? Ei law ydych chi eisiau i ad-drefnu cyntaf? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: OK, felly Diana. Ble ydych chi eisiau i bwynt Pwyntydd chwith Diana ar? Yn 55, yn ôl pob tebyg, fel bod rydym wedi gosod yno. A lle y dylid 55 pwyntydd fynd? Down, yn cynrychioli null. Ac yn fy nwylo, ar y pwynt hwn, peidiwch bwysig oherwydd eu bod yn unig oedd newidynnau dros dro. Felly, yn awr rydym yn ei wneud. 

Felly, y cymhlethdod ychwanegol yno - ac nid yw mor galed i weithredu, ond mae angen newidyn eilaidd i wneud yn siwr bod cyn i mi symud fy hawl llaw, yr wyf yn diweddaru'r gwerth fy chwith llaw, pwyntydd pred yn yr achos hwn, fel y fod gennyf pwyntydd trailing i gadw cofnod o ble roeddwn. Nawr wrth fynd heibio, os ydych yn ystyried hyn drwy, mae hyn yn teimlo fel ei fod yn ychydig yn blino o gael i gadw golwg ar y llaw chwith. 

Beth fyddai ateb arall i'r broblem hon wedi bod? Os ydych yn cael i ailgynllunio'r data strwythur rydym yn sôn trwy hyn o bryd? Os yw hyn yn unig fath o teimlo ychydig blino i gael, fel, dau awgrymiadau mynd drwy'r rhestr, pwy arall a allai wedi, mewn byd delfrydol, a gynhelir wybodaeth sydd ei hangen ni? Yeah? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Yn union. Iawn felly mae mewn gwirionedd yn ddiddorol germ o syniad. Ac mae syniad hwn o pwyntydd blaenorol, pwyntio at yr elfen blaenorol. Beth os wyf yn unig ymgorfforodd yr tu mewn i'r rhestr ei hun? Ac mae'n mynd i fod yn anodd i ddelweddu hyn heb yr holl bapur syrthio i'r llawr. Ond mae'n debyg bod y rhain guys yn defnyddio'r ddwy o'u dwylo i gael blaenorol pwyntydd, a pwyntydd nesaf, a thrwy hynny gweithredu'r hyn y byddwn yn ei alw'n ddwbl restr cysylltiedig. Byddai hynny'n caniatáu i mi i ddatrys y rewind, llawer mwy hawdd heb mi, y rhaglennydd, ar ôl i gadw olrhain â llaw - wirioneddol llaw - o ble oeddwn wedi bod o'r blaen yn y rhestr. Felly, ni fyddwn yn gwneud hynny. Byddwn yn cadw pethau'n syml oherwydd dyna mynd i ddod am bris, ddwywaith yn llawer o le ar gyfer y pwyntiau, os ydych chi am gael ail un. Ond mae hynny'n wir yn gyffredin strwythur data a elwir yn rhestr gysylltiedig ddwbl. 

Gadewch i ni wneud yr enghraifft derfynol yma ac yn rhoi guys hyn allan o'u diflastod. Felly malloc 20. Dewch ar i fyny o'r eil yno. Mae pob hawl, beth yw eich enw? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Mae'n ddrwg gennyf? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Demeron? OK dod ar i fyny. Rhaid i chi fod yn 20. Mae'n amlwg eich bod yn mynd i perthyn rhwng 17 a 22. Felly, gadewch i mi ddysgu fy ngwers. Dwi'n mynd i ddechrau pwyntydd pwyntio at Brian. Ac yr wyf i'n mynd i gael fy llaw chwith dim ond diweddaru i Brian fel yr wyf yn symud i Jason, gwirio yn 20 yn llai na naw? Rhif Yn 20 yn llai na 17? Rhif Yn 20 yn llai na 22? Ydw. Felly mae angen i pa awgrymiadau neu dwylo i newid lle maent yn pwyntio nawr? 

Felly, gallwn wneud 17 pwyntio at 20. Felly, mae hynny'n iawn. Ble ydym ni eisiau i bwynt eich pwyntydd nawr? Yn 22. Ac rydym yn gwybod lle 22, unwaith eto diolch i fy pwyntydd dros dro. Felly, rydym yn iawn yno. Felly, oherwydd storio dros dro hwn Rwyf wedi cadw golwg ar lle mae pawb yn. Ac yn awr y gallwch chi fynd ar eu golwg i mewn lle ydych yn perthyn, ac yn awr rydym angen 1, 2, 3, 4, 5, 6, 7, 8, 9 peli straen, a rownd o gymeradwyaeth ar gyfer guys hyn, os gallem. Gwneud 'N glws. 

[Cymeradwyaeth] 

SIARADWR 1: Pob hawl. Ac efallai y byddwch yn cadw'r darnau o bapur fel cofroddion. 

Mae pob hawl, felly, ymddiried ynof mae'n llawer yn haws i gerdded drwy hynny gyda bobl nag y mae gyda chod gwirioneddol. Ond yr hyn y byddwch yn dod o hyd yn ychydig funudau'n erbyn hyn, yw bod un fath - oh, diolch yn fawr. Diolch i chi - yw y byddwch yn dod o hyd bod yr un data strwythur, rhestr cysylltiedig, gall mewn gwirionedd yn cael ei ddefnyddio fel bloc adeiladu hyd yn oed yn fwy strwythurau data soffistigedig. 

Ac yn sylweddoli hefyd y thema yma yw bod rydym wedi cyflwyno gwbl yn fwy cymhlethdod ati i weithredu o algorithm hwn. Gosod, ac os ydym yn mynd drwyddi, dileu a chwilio, ychydig yn fwy cymhleth nag y mae'n ei oedd gydag amrywiaeth. Ond rydym yn ennill rhywfaint o egni. Rydym yn cael strwythur data addasol. 

Ond unwaith eto, rydym yn talu pris o gael rhywfaint o cymhlethdod ychwanegol, yn weithredu. Ac rydym yn rhoi'r gorau mynediad ar hap. Ac i fod yn onest, nid oes rhai 'n glws glân sleid gallaf ei roi i chi yn dweud dyma pam restr cysylltiedig yn well na arae. A'i adael ar hynny. Oherwydd bod y thema ddigwydd eto yn awr, hyd yn oed yn fwy felly yn yr wythnosau nesaf, yn nad oes o reidrwydd ateb cywir. 

Dyma pam y mae gennym yr echelin ar wahân o ddylunio ar gyfer setiau broblem. Bydd yn y cyd-destun sensitif iawn p'un a ydych am ddefnyddio'r data hwn strwythur neu bod un, a bydd yn yn dibynnu ar yr hyn sy'n bwysig i chi o ran o adnoddau a chymhlethdod. 

Ond gadewch i mi yn cynnig bod y data delfrydol strwythur, y greal sanctaidd, yn rhywbeth sy'n cysonyn amser, waeth faint o bethau yn y tu mewn iddo, ni fyddai'n wych pe bai strwythur data a ddychwelwyd atebion yn cysonyn amser. Ydw. Mae'r gair yn eich geiriadur enfawr. Neu ddim, nid yw'r gair hwn yw. Neu unrhyw broblem o'r fath yno. Wel, gadewch i ni weld os na allwn o leiaf cymryd cam tuag at hynny. 

Gadewch i mi yn cynnig strwythur data newydd sy'n Gellir ei ddefnyddio ar gyfer gwahanol bethau, yn yr achos hwn a elwir tabl hash. Ac felly rydym yn mewn gwirionedd yn ôl i glancing mewn amrywiaeth, yn yr achos hwn, ac braidd yn fympwyol, rwyf wedi tynnu hwn tabl hash fel amrywiaeth gyda'r math o arae dau ddimensiwn - neu yn hytrach ei fod yn darlunio yma fel dwy amrywiaeth dimensiwn - ond mae hyn yn unig yw amrywiaeth o faint 26, fel bod os ydym ffoniwch y bwrdd amrywiaeth, braced tabl sero yn y petryal ar y brig. Tabl braced 25 yw'r petryal ar y gwaelod. A dyma sut y gallwn dynnu data strwythur lle rwyf am i storio bobl enwau. 

Felly, er enghraifft, ac ni fyddaf yn tynnu'r holl beth yma ar y uwchben, os wyf yn Roedd amrywiaeth hon, ac yr wyf i'n awr yn mynd i ffoniwch tabl hash, ac mae hyn eto leoliad sero. Mae hyn dyma yw lleoliad un, ac yn y blaen. Yr wyf yn honni fy mod am ddefnyddio'r data hwn strwythur, er mwyn trafod, i storio enwau pobl, Alice a Bob a Charlie ac enwau eraill o'r fath. Felly, meddwl am hyn yn awr fel egin o, dyweder, geiriadur gyda llawer o eiriau. Maent yn digwydd i fod yn enwau yn ein enghraifft yma. Ac mae hyn i gyd yn rhy germane, efallai, i gweithredu gwirydd sillafu, wrth i ni Efallai ar gyfer problem gosod chwech. 

Felly, os oes gennym amrywiaeth o gyfanswm maint 26 fel bod hwn yn lleoliad 25ain ar y gwaelod, ac yr wyf yn honni bod Alice yn y gair cyntaf yn y geiriadur o enwau yr wyf am i fewnosod i mewn i RAM, yn y strwythur data, ble greddf yn dweud eich bod yn Alice yn Dylai enw fynd amrywiaeth hwn? 

Mae gennym 26 o opsiynau. Lle rydym am i roi ei? Rydym am iddi yn braced sero, dde? A i Alice, gadewch i ni alw y sero. A fydd B yn un, ac C yn ddau. Felly, rydym yn mynd i ysgrifennu Enw Alice i fyny yma. Os byddwn wedyn yn mewnosod Bob, ei Bydd enw ewch yma. Bydd Charlie ewch yma. Ac yn y blaen i lawr drwy y strwythur data. 

Mae hwn yn strwythur data gwych. Pam? Wel beth yw'r amser rhedeg mewnosod enw dynol i mewn i hyn data strwythur ar hyn o bryd? O ystyried bod y tabl hwn yn cael ei weithredu, yn wir, fel arae. Wel, mae'n amser cyson. Mae'n drefn un. Pam? 

Wel sut yr ydych yn penderfynu ar lle mae Alice yn perthyn? Byddwch yn edrych ar pa lythyren ei enw? Y cyntaf. A gallwch gael yno, os yw'n llinyn, at jyst yn edrych ar linyn braced sero. Felly, y cymeriad 0 y llinyn. Mae hynny'n hawdd. Gwnaethom hynny yn y crypto wythnosau aseiniad yn ôl. Ac yna unwaith y byddwch yn gwybod bod Alice llythyr CYFALAF A, gallwn dynnu oddi ar 65 oed neu gyfalaf A ei hun, sy'n rhoi i ni sero. Felly, rydym yn gwybod bod Alice yn perthyn yn y lleoliad sero. 

Ac o ystyried pwyntydd i'r data hwn strwythur, o ryw fath, pa mor hir y ei gymryd i mi ddod o hyd i leoliad sero mewn amrywiaeth? Dim ond un cam, i'r dde Mae'n amser cyson oherwydd y mynediad ar hap ydym yn Roedd arfaethedig yn nodwedd o fyrdd. Felly, yn fyr, figuring allan yr hyn y mae'r mynegai enw Alice yw, sydd, yn yr achos hwn, yn A, neu adael i ni dim ond datrys hynny i sero, os yw B yn un a C yn dau, figuring bod allan yw cysonyn amser. Fi jyst yn rhaid i ni edrych ar ei llythyr cyntaf, figuring gwybod ble sero yn amrywiaeth yn cysonyn amser hefyd. Felly dechnegol dyna fel dau gam yn awr. Ond mae hynny'n dal i fod yn gyson. Felly, rydym yn galw bod O fawr o un, felly rydym wedi mewnosod Alice yn y tabl hwn yn cysonyn amser. 

Ond wrth gwrs, fy mod yn cael naïf yma, dde? Beth os oes 'na Aaron yn y dosbarth? Neu Alicia? Neu unrhyw enwau eraill gan ddechrau gyda A. Os ydym yn mynd i roi y person hwnnw, dde? Yr wyf yn golygu, ar hyn o bryd does dim ond tri bobl ar y bwrdd, felly efallai ni Dylai roi Aaron yn y lleoliad sero un dau tri. 

Iawn, gallwn roi A yma. Ond yna, os ydym yn ceisio mewnosod David yn y rhestr hon, ble mae David yn mynd? Nawr ein system yn dechrau torri i lawr, dde? Oherwydd erbyn hyn yn dod i ben i fyny David yma os Aaron mewn gwirionedd yma. Ac felly yn awr, y cyfan syniad o gael strwythur data glân sy'n rhoi i ni mewnosodiadau cysonyn amser bellach yn cysonyn amser, gan fod rhaid i mi gwirio, oh, Damnit, rhywun yn barod yn y lleoliad Alice. 

Gadewch i mi ymchwilio i weddill y data hwn strwythur, yn chwilio am fan a'r lle i roi rhywun fel enw Aaron. Ac felly hynny hefyd yn dechrau i gymryd amser llinol. Ar ben hynny, os ydych yn awr am ddod o hyd i'r Aaron yn y strwythur data, a'ch bod yn gwirio, ac nid enw Aaron yma. Yn ddelfrydol, byddech yn dweud Aaron nid yn y strwythur data. Ond os ydych chi'n dechrau gwneud lle i Aaron lle y dylai fod wedi bod yn D neu E, gallwch chi, achos gwaethaf, mae'n rhaid i wirio y strwythur data cyfan, yn ac os felly ei bod yn datganoli i fod yn rhywbeth llinellol ym maint y tabl. 

Felly, iawn, 'n annhymerus' atgyweiria hon. Y broblem yma yw fy mod wedi 26 elfen yn y casgliad hwn. Gadewch i mi ei newid. Wps. Gadewch i mi newid fel bod yn hytrach lles maint 26 i gyd, yn sylwi ar y gwaelod mynegai yn mynd i newid i n minws 1. Os yw 26 yn amlwg yn rhy fach ar gyfer pobl ' enwau, oherwydd mae miloedd o enwau'r byd, gadewch i ni dim ond gwneud mewn 100 neu 1,000 neu 10,000. Gadewch i 'jyst dyrannu llawer mwy o le. 

Wel, nid yw hynny o reidrwydd yn gostwng y tebygolrwydd na fydd gennym ddwy pobl ag enwau gan ddechrau gyda A, a felly, yr ydych yn mynd i geisio rhoi A enwau ar sero lleoliad hyd. Maent yn dal i fynd i wrthdaro, a golygu ein bod yn dal angen ateb i roi Alice ac Aaron a Alicia ac eraill enwau gan ddechrau gyda A mewn mannau eraill. Ond faint o broblem yw hyn? Beth yw'r tebygolrwydd y bydd eich cael gwrthdrawiadau mewn data strwythur fel hyn? 

Wel, gadewch i mi - byddwn yn dod yn ôl i'r cwestiwn yma. Ac edrych ar sut y gallem datrys yn gyntaf. Gadewch i mi dynnu i fyny y cynnig hwn yma. Yr hyn yr ydym newydd ei ddisgrifio yn algorithm, a hewristig enw llinellol treiddgar sy'n golygu, os ydych yn ceisio rhoi'r rhywbeth yma yn y data hwn strwythur, a elwir tabl hash, ac nad oes lle yno, byddwch wirioneddol ymchwilio i'r strwythur data gwirio, a yw hyn ar gael? A yw hyn ar gael yw hyn ar gael? A yw hyn ar gael? A phan yn olaf yw, eich mewnosoder y enwi eich bod fwriadwyd yn wreiddiol mewn mannau eraill yn y lleoliad hwnnw. Ond yn yr achos gwaethaf, yr unig fan a'r lle a allai fod yn y waelod y data strwythur, y diwedd y rhesi. 

Felly llinol stilio, yn yr achos gwaethaf, yn datganoli i mewn i algorithm llinol lle Aaron, os yw'n digwydd i gael eu mewnosod ddiwethaf yn y strwythur data, fe allai gwrthdaro â'r lleoliad cyntaf, ond wedyn ben erbyn anlwc ar ddiwedd. Felly, nid yw hyn yn gyson greal sanctaidd o amser i ni. Mae'r dull hwn o elfennau mewnosod i mewn i strwythur data a elwir yn hash Nid yw'n ymddangos bod y tabl yn cysonyn amser o leiaf nid yn yr achos cyffredinol. Gall ddatganoli i fod yn rhywbeth llinol. 

Felly beth os ydym yn datrys gwrthdrawiadau ychydig yn wahanol? Felly dyma fwy soffistigedig tuag at yr hyn sy'n dal i fod a elwir yn tabl hash. A thrwy hash, wrth fynd heibio, yr hyn Yr wyf yn golygu y mynegai a Cyfeiriais ato yn gynharach. Gall I hash rhywbeth yn ystyried fel berf. 

Felly, os ydych hash Alice 'na enw, swyddogaeth hash, fel petai, Dylid dychwelyd rhif. Yn yr achos hwn yn sero os yw'n perthyn yn Lleoliad sero, un os y mae yn perthyn yn leoliad yn un, ac yn y blaen. Felly, fy swyddogaeth hash hyd yn hyn wedi bod yn super syml, dim ond yn edrych ar y llythyren gyntaf yn enw'r rhywun. Ond mae swyddogaeth hash yn cymryd fel mewnbwn rhyw darn o ddata, a llinyn, yn int, beth bynnag. Ac mae'n poeri allan fel arfer yn rhif. Ac mae'r nifer yn lle bod data elfen yn perthyn mewn strwythur data a elwir yma fel tabl hash. 

Felly, dim ond yn reddfol, mae hwn yn cyd-destun ychydig yn wahanol. Mae hyn mewn gwirionedd yn cyfeirio at enghraifft cynnwys penblwyddi, lle gallai fod cymaint â 31 diwrnod yn y mis. Ond beth oedd y person hwn benderfynu ei wneud mewn achos o wrthdrawiad? Cyd-destun yn awr, ac nid yn gwrthdrawiad o enwau, ond mae gwrthdrawiad pen-blwydd, os oes dau o bobl yr un pen-blwydd ar y 2 Hydref, er enghraifft. 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Yeah, felly dyma ni wedi y leveraging rhestrau cysylltiedig. Felly, mae'n edrych ychydig yn wahanol nag i ni dynnu yn gynharach. Ond mae'n ymddangos ein bod yn rhaid i arae ar yr ochr chwith. Dyna un mynegai, nid ar gyfer unrhyw rheswm penodol. Ond mae'n dal i fod yn arae. Mae'n amrywiaeth o awgrymiadau. A phob un o'r elfennau hynny, pob un y cylchoedd neu slaes - y slaes cynrychioli null - pob un o'r rhain awgrymiadau yn ymddangos yn pwyntio i pa strwythur data? Mae rhestr cysylltiedig. 

Felly, erbyn hyn mae gennym y gallu i cod caled yn ein rhaglen maint y tabl. Yn yr achos hwn, rydym yn gwybod bod hi byth mwy na 31 diwrnod mewn mis. Mor galed codio gwerth fel 31 yn rhesymol yn y cyd-destun. Yng nghyd-destun enwau, caled codio 26 nid yw'n afresymol yw'n bobl enwau ond yn dechrau gydag, er enghraifft, yr wyddor yn ymwneud A drwy Z. 

Gall Rydym yn gwthio i gyd i mewn i'r data strwythur ar yr amod, pan fyddwn yn cael gwrthdrawiad, nid ydym yn rhoi'r enwau yma, rydym yn hytrach na meddwl am y celloedd hyn nid fel llinynnau eu hunain, ond fel y awgrymiadau, er enghraifft, Alice. Ac yna gall Alice gael pwyntydd arall i enw arall gan ddechrau gyda A. Ac Bob mewn gwirionedd yn mynd dros yma. 

Ac os oes enw arall dechrau gyda B, ei fod yn dod i ben i fyny dros yma. Ac felly mae pob un o'r elfennau hyn tabl dau, os rydym yn cynllunio hyn a ychydig yn fwy deallus - yn dod ar - os ydym yn cynllunio hyn ychydig yn fwy gelfydd, yn awr yn dod yn ddata addasol strwythur, lle nid oes terfyn caled ar faint o elfennau gallwch osod i mewn iddo oherwydd os oes gennych gwrthdrawiad, mae hynny'n iawn. Dim ond mynd yn ei flaen ac yn ei atodi i yr hyn a welsom ychydig yn ôl oedd a elwir yn restr cysylltiedig. 

Wel, gadewch i ni oedi am ychydig funud. Beth yw'r tebygolrwydd o gwrthdrawiad yn y lle cyntaf? Iawn, efallai fy mod yn meddwl dros, efallai Rydw i wrth fy peirianneg broblem hon, oherwydd eich bod yn gwybod beth? Oes, gallaf ddod o hyd mympwyol enghreifftiau oddi ar ben fy mhen fel Allison ac Aaron, ond mewn gwirionedd, o ystyried dosbarthiad unffurf o mewnbynnau, hynny yw rhai mewnosodiadau ar hap i mewn i strwythur data, beth mewn gwirionedd yw y tebygolrwydd o gwrthdrawiad? Wel yn troi allan, mae'n mewn gwirionedd yn super uchel. Gadewch i mi cyffredinoli hyn problem fel hyn. 

Felly, mewn ystafell o n CS50 fyfyrwyr, beth y tebygolrwydd bod o leiaf dau fyfyriwr yn yr ystafell cael yr un pen-blwydd? Felly mae beth. ychydig o hund - 200, 300 o bobl yma a nifer o cant o bobl yn y cartref heddiw. Felly, os ydych yn awyddus i ofyn i ni'n hunain beth sydd y tebygolrwydd o ddau o bobl yn yr ystafell hon yn cael yr un pen-blwydd, gallwn ffigur hyn. Ac yr wyf yn gwneud cais mewn gwirionedd mae dau bobl sydd â'r un pen-blwydd. 

Er enghraifft, a oes unrhyw un wedi pen-blwydd heddiw? Ddoe? Yfory? Mae pob hawl, felly mae'n teimlo fel mod i'n mynd i gael i wneud hyn 363, neu fel bod mwy amser i mewn gwirionedd yn chyfrif i maes os oes gennych gwrthdrawiad. Neu gallem dim ond gwneud hyn yn fathemategol yn hytrach na tediously wneud hyn. Ac yn cynnig y canlynol. 

Felly, yr wyf yn cynnig y gallem fodelu'r tebygolrwydd o ddau o bobl gael y un pen-blwydd fel y tebygolrwydd o 1 minws y tebygolrwydd o unrhyw un â yr un pen-blwydd. Felly, i gael hyn, ac mae hyn yn dim ond y ffordd ffansi o ysgrifennu hwn, er y person cyntaf yn yr ystafell, bydd ef neu hi Gall unrhyw un o'r posibl pen-blwydd gan dybio 365 diwrnod yn y flwyddyn, gydag ymddiheuriadau i bobl ag pen-blwydd 29 Chwefror. 

Felly, y person cyntaf yn yr ystafell hon yn rhad ac am ddim i gael unrhyw nifer o pen-blwydd allan o'r posibiliadau 365 fel bod byddwn yn gwneud hynny 365 wedi'i rannu â 365, sy'n un. Mae'r person nesaf yn yr ystafell, os yw'r nod yw osgoi gwrthdrawiad, dim ond yn cael ei ben-blwydd ar sut llawer o wahanol ddyddiau posibl? 364. Felly, yr ail dymor yn ymadrodd hwn yn hanfod wneud hynny cwestiwn i ni trwy dynnu oddi ar un diwrnod posibl. Ac yna y diwrnod nesaf, y diwrnod nesaf, y diwrnod nesaf i lawr at gyfanswm nifer o bobl yn yr ystafell. 

Ac os ydym yn ystyried, beth felly yw y tebygolrwydd nid pawb yn cael pen-blwydd unigryw, ond unwaith eto 1 llai hynny, yr hyn a gawn yn fynegiant y gall fancifully iawn edrych fel hyn. Ond mae'n fwy diddorol i edrych ar eu golwg. Mae hwn yn siart lle ar yr echelin-x yn y nifer o bobl yn yr ystafell, y nifer y pen-blwydd. Ar y y-echelin yw'r tebygolrwydd o wrthdrawiad, dau o bobl cael yr un pen-blwydd. 

Ac mae'r prydau parod o'r gromlin hon yn cyn gynted ag y byddwch yn dod i hoffi 40 fyfyrwyr, rydych yn i fyny at 90% o debygolrwydd combinatorically o ddau bobl neu fwy yn cael yr un pen-blwydd. Ac ar ôl i chi ddod i hoffi 58 o bobl ei fod yn bron i 100% o gyfle y ddwy bobl yn yr ystafell yn mynd i gael y un pen-blwydd, er bod yna 365 neu 366 bwcedi posibl, a dim ond 58 o bobl yn yr ystafell. Dim ond ystadegol rydych yn debygol o cael gwrthdrawiadau, sydd yn fyr cymell y drafodaeth hon. Hyd yn oed os ydym yn cael ffansi yma, ac dechrau cael cadwyni hyn, rydym yn dal i mynd i gael gwrthdrawiadau. 

Felly mae hynny'n codi'r cwestiwn, beth yw'r gost o wneud fewnosodiadau a dileadau i mewn i strwythur data fel hyn? Wel gadewch i mi gynnig - a gadewch i mi fynd yn ôl i'r sgrin dros yma - os ydym wedi n elfennau yn y rhestr, felly os ydym yn ceisio ei fewnosod n elfennau, ac mae gennym faint o gyfanswm bwcedi? Gadewch i ni ddweud 31 gyfanswm bwcedi yn achos pen-blwydd. Beth sydd hyd uchafswm o o gadwyni hyn yn bosibl? 

Os unwaith eto mae 31 posibl pen-blwydd mewn mis a roddir. Ac rydym yn unig clumping pawb - mewn gwirionedd mae hynny'n enghraifft dwp. Gadewch i ni wneud 26 yn lle hynny. Felly, os mewn gwirionedd yn rhaid i bobl y mae eu henwau dechrau gyda A drwy Z, gan roi ni 26 o bosibiliadau. Ac rydym yn defnyddio strwythur data fel yr un yr ydym jyst yn gweld, lle yr ydym wedi amrywiaeth o awgrymiadau, pob un ohonynt yn cyfeirio at restr cysylltiedig lle y rhestr cyntaf yw pawb gydag enw Alice. Mae'r ail restr yn bob â'r enwi gan ddechrau gyda A, gan ddechrau gyda B, ac yn y blaen. 

Beth sydd hyd tebygol pob un o'r rhestrau hynny os ydym yn tybio amgylchedd glân 'n glws dosbarthu enwau A drwy Z ar draws y strwythur data cyfan? Mae pobl n yn y strwythur data wedi'i rannu â 26, os ydynt yn 'n glws gwasgaru dros y cyfan strwythur data. Felly, hyd pob un o'r rhain cadwyni yn n rannu â 26. Ond yn O mawr nodiant, beth yw hynny? Beth yw hynny mewn gwirionedd? Felly mae'n wirioneddol dim ond n, dde? Oherwydd ein bod wedi dweud yn y gorffennol, bod Ych chi rannu â 26. Ie, mewn gwirionedd yn gyflymach. Ond mewn egwyddor, nid yw'n sylfaenol i gyd yn gyflymach. 

Felly, nid yw'n ymddangos i ni fod yr holl bod llawer yn agosach at y greal sanctaidd. Mewn gwirionedd, mae hyn yn unig yw amser llinol. Heck, ar y pwynt hwn, pam nad ydym dim ond yn defnyddio un rhestr cysylltiedig enfawr? Pam nad ydym yn unig yn defnyddio un enfawr amrywiaeth i storio enwau pawb yn yr ystafell? Wel, a oes rhywbeth o hyd grymus am dabl hash? A oes yn dal rhywbeth cymhellol am strwythur data sy'n edrych fel hyn? Hwn. 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Iawn, ac eto os mai dim ond algorithm amser llinol, ac mae strwythur data amser llinol, pam nad ydw i'n dim ond storio enw pawb mewn mawr amrywiaeth, neu mewn rhestr cysylltiedig mawr? Ac yn rhoi'r gorau i wneud CS mor llawer anoddach nag y mae angen iddo fod? Beth yn rymus am hyn, hyd yn oed er fy mod yn crafu allan? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Nid yw mewnosodiadau chi? Drud anymore. Felly mewnosodiadau bosibl y gallai dal i o amser yn gyson, hyd yn oed os yw eich data strwythur yn edrych fel hyn, mae amrywiaeth o awgrymiadau, pob un ohonynt yn pwyntio at potensial i fod yn rhestr gysylltiedig. Sut y gallech ei chyrraedd yn gyson amser gosod enwau? Lynu yn y blaen, dde? 

Os byddwn yn aberthu nod dylunio o yn gynharach, lle rydym yn awyddus i gadw enw pawb, er enghraifft, didoli, neu bob un o'r rhifau ar y llwyfan didoli, Mae'n debyg bod gennym restr cysylltiedig heb eu didoli. Dim ond yn costio i ni yn un neu ddau gam, fel yn achos Ben a Brian yn gynharach, i fewnosod elfen yn ddechrau'r rhestr. Felly, os nad ydym yn poeni am ddatrys yr holl o enwau gan ddechrau gyda A neu bob yr enwau gan ddechrau gyda B, gallwn yn dal i cyflawni osod cysonyn amser. Awr yn edrych i fyny Alice neu Bob neu unrhyw enw yn fwy cyffredinol yn dal i beth? Mae'n fawr O n rannu gan 26, yn y achos delfrydol lle mae pawb yn unffurf dosbarthu, lle mae cymaint o A gan fod Z, ac mae'n debyg mai afrealistig. Ond mae hynny'n dal i fod yn llinol. 

Ond yma, rydym yn dod yn ôl at y pwynt o nodiant asymptotic yn ddamcaniaethol wir. Ond yn y byd go iawn, os wyf yn honni bod Gall fy rhaglen wneud rhywbeth 26 gwaith gyflymach na chi, y mae eu rhaglen ydych chi'n mynd i well defnyddio? Chi neu fy un i, a yw 26 gwaith yn gyflymach? Yn realistig, bydd y person y mae ei 26 gwaith yn gyflymach, hyd yn oed os ddamcaniaethol ein algorithmau yn rhedeg yn yr un asymptotic amser yn rhedeg. 

Gadewch i mi yn cynnig gwahanol ateb yn gyfan gwbl. Ac os nad yw hyn yn chwythu eich meddwl, rydym yn allan o strwythurau data. Felly mae hyn yn ei fod yn trie - math o enw dwp. Mae'n dod o adalwadau, a'r gair ei sillafu trie, t-r-i-e, oherwydd adalw cwrs yn swnio fel trie. Ond dyna hanes y gair trie. 

Felly trie yn wir rhyw fath o goeden, ac mae hefyd yn chwarae ar y gair hwnnw. A hyd yn oed er na allwch ei weld yn eithaf gyda delweddu hon, mae trie yn coeden strwythuro, fel coeden teulu gyda un hynafiad ar y brig a llawer o wyrion ac wyrion mawr fel yn gadael ar y gwaelod. Ond mae pob nod mewn trie yn arae. Ac mae'n mewn amrywiaeth - a gadewch i gorsymleiddio'r am eiliad - ei fod yn amrywiaeth, yn yr achos hwn, o faint 26, lle bob nod unwaith eto mae amrywiaeth o faint 26, lle mae'r elfen 0 yn y amrywiaeth cynrychioli A, a'r olaf ym mhob elfen o'r fath amrywiaeth cynrychioli Z. 

Felly, yr wyf yn cynnig, felly, bod y data hwn Gall strwythur, a elwir yn trie, yn defnyddio hefyd i storio geiriau. Gwelsom funud yn ôl sut y gallem storio geiriau, neu yn yr enwau achos hwn, ac rydym yn welsom yn gynharach sut y gallwn storio rhifau, ond os ydym yn canolbwyntio ar enwau neu linynnau yma, yn sylwi ar yr hyn sy'n ddiddorol. Yr wyf yn honni bod yr enw Maxwell yw tu mewn y strwythur data. Lle ydych chi'n gweld Maxwell? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Ar y chwith. Felly, yr hyn sy'n ddiddorol gyda data hwn strwythur yn hytrach na siop y llinyn M-A-X-W-E-L-L slaes sero, pob contiguously, yr hyn yr ydych yn ei wneud yn lle hynny yn dilyn. Os yw hyn yn trie fel strwythur data, mae pob un o'i nodau yw eto arae, ac rydych am i storio Maxwell, i chi yn gyntaf mynegai ac felly nod y gwraidd, fel i siarad, y nod topmost, yn y lleoliad M, ar y dde, felly fras yn y canol. Ac yna oddi yno, byddwch yn dilyn pwyntydd i blentyn nodau, fel petai. Felly, yn yr ystyr coeden deulu, ei ddilyn i lawr. Ac mae hynny'n eich arwain at nod arall ar y chwith yno, sydd yn dim ond amrywiaeth arall. 

Ac yna os ydych am storio Maxwell, ddod o hyd i'r pwyntydd sy'n cynrychioli A, sydd yn yr un yma yma. Yna byddwch yn mynd at y nod nesaf. A rhybudd - dyma pam y darlun yn ychydig yn twyllo - nod hwn yn edrych super bach. Ond i'r dde o hyn yw Y a Z. Mai dim ond yr awdur wedi cwtogi y llun er mwyn i chi mewn gwirionedd yn gweld pethau. Fel arall y llun byddai'n hynod o eang. Felly, yn awr yr ydych mynegai i mewn i leoliad X, yna W, Yna E, yna i'r Ch, yna L. Yna beth sydd chwilfrydedd hwn? 

Wel, os ydym yn defnyddio y math hwn o newydd cymryd ar sut i storio llinyn mewn strwythur data, mae angen i chi yn dal i hanfod gwirio i ffwrdd yn y data strwythur y gair yn dod i ben yma. Mewn geiriau eraill, pob un o'r nodau hyn rhywsut wedi i gofio ein bod yn dilyn mewn gwirionedd yr holl awgrymiadau hyn ac yn gadael ychydig bara briwsion ar waelod yma o hyn strwythur i ddangos M-A-X-W-E-L-L yn yn wir yn y strwythur data. 

Felly, efallai y byddwn yn gwneud hyn fel a ganlyn. Mae pob un o'r nodau yn y llun rydym yn unig gwelodd un, amrywiaeth o faint 27. Ac mae'n awr yn 27, oherwydd yn p gosod chwech, byddwn mewn gwirionedd yn rhoi collnod i chi, er mwyn i ni gael enwau fel O'Reilly ac eraill sydd â collnod. Ond mae un syniad. Mae pob un o'r elfennau hynny yn y pwyntiau amrywiaeth i strwythur nod, felly dim ond nod. Felly, mae hyn yn ein hatgoffa iawn o'n rhestr gysylltiedig. 

Ac yna mae gen i Boole, a byddaf ffoniwch gair, sydd yn unig yn mynd i fod yn yn wir os yw gair yn dod i ben ar hyn o nod yn y goeden. Mae'n effeithiol cynrychioli'r bach triongl gwelsom funud yn ôl. Felly, os yw gair yn dod i ben ar y nod yn y coed, bydd y gair hwnnw maes fod yn wir, sydd yn gysyniadol gwirio i ffwrdd, neu rydym yn tynnu triongl hwn, ie yno yn air yma. 

Felly, mae hwn yn trie. Ac yn awr y cwestiwn yw, beth yn ei rhedeg amser? A yw'n fawr o O n? A yw'n rhywbeth arall? Wel, os ydych wedi n enwau yn y data hwn strwythur, Maxwell yn un o iddynt, beth yw'r amser rhedeg mewnosod neu ddod o hyd Maxwell? Beth yw'r amser yn rhedeg o mewnosod Maxwell? Os oes n enwau eraill eisoes yn y tabl? Yeah? 

MYFYRIWR: [Anghlywadwy]. 

SIARADWR 1: Yeah, 'i' hyd yr enw, dde? Felly M-a-x-w-e-l-l felly mae'n teimlo fel hyn algorithm yn fawr O o saith. Yn awr, wrth gwrs, yr enw yn amrywio o ran hyd. Efallai ei fod yn enw byr. Efallai ei fod yn enw hirach. Ond yr hyn sy'n allweddol yma yw bod mae'n nifer cyson. Ac efallai nid yw'n wir yn gyson, ond duw, os realistig, mewn geiriadur, mae debyg bod rhai terfyn ar y nifer o lythyrau mewn enw'r person hwnnw mewn gwlad benodol. 

Ac felly gallwn gymryd yn ganiataol y gwerth yn gyson. Nid wyf yn gwybod beth ydyw. Mae'n debyg yn fwy na'r rydym yn meddwl ei fod yn. Oherwydd bod bob amser yn rhyw gornel achos gydag enw hir crazy. Felly, gadewch i ni ei alw'n k, ond mae'n dal i fod yn gyson yn ôl pob tebyg, oherwydd y mae pob enwi yn y byd, o leiaf mewn gwlad arbennig, yw bod hyd neu byrrach, felly mae'n gyson. Ond pan fyddwn wedi dweud rhywbeth yn fawr O o werth cyson, beth sy'n bod sy'n cyfateb mewn gwirionedd i? Mae hynny'n wir yr un peth yn dweud cysonyn amser. 

Nawr rydym yn fath o dwyllo, dde? Rydym yn fath o ddylanwad rhywfaint o theori yma i ddweud bod trefn k yn dda, yn mewn gwirionedd ond yn archebu o un, ac mae'n amser cyson. Ond mae mewn gwirionedd. Oherwydd bod y mewnwelediad allweddol yma yw bod os ydym wedi n enwau eisoes yn hyn o strwythur data, ac yr ydym mewnosoder Maxwell, yw faint o amser mae'n ei gymryd i ni mewnosoder Maxwell o gwbl yr effeithir arnynt gan faint o bobl eraill yn y strwythur data? Nid yw'n ymddangos i fod. Os bu'n rhaid i mi yn fwy o biliwn elfen i hyn trie, ac yna rhowch Maxwell, yn cael ei ef yn mhob heffeithio? Rhif A dyna wahanol i unrhyw o'r data diwrnod strwythurau rydym wedi gweld hyd yn hyn, lle yr amser yn rhedeg eich algorithm yn gwbl annibynnol ar faint o pethau ai peidio eisoes yn y strwythur data. 

Ac felly gyda hyn yn ei roi i chi yn awr yn cyfle i p set chwech, a fydd yn unwaith eto yn golygu gweithredu eich hun gwiriwr sillafu, darllen yn 150,000 geiriau, y ffordd orau i storio'r Nid yw o reidrwydd yn amlwg. Ac er fy mod i wedi dyheu am ddod o hyd i y greal sanctaidd, nid wyf yn honni bod trie yn. Yn wir, efallai y tabl hash yn dda iawn yn profi i fod yn llawer mwy effeithlon. Ond y rhai yn unig - mai dim ond un o'r penderfyniadau dylunio bydd yn rhaid i chi ei wneud. 

Ond yn cau gadewch i ni gymryd 50 neu lai eiliad i gymryd cipolwg ar yr hyn sydd blaen yr wythnos nesaf a thu hwnt yn pontio o'r llinell orchymyn os yw rhaglenni byd C i bethau ar y we yn seiliedig ac ieithoedd fel PHP a JavaScript a'r rhyngrwyd ei hun, protocolau fel HTTP, a ydych wedi gymryd yn ganiataol ar gyfer y blynyddoedd nawr, ac yn y rhan fwyaf o teipio pob dydd, efallai, neu weld. A byddwn yn dechrau croen yn ôl y haenau o'r hyn sydd ar y rhyngrwyd. A beth yw'r cod y wrth wraidd offer heddiw. Felly, 50 eiliad o ymlid hwn yma. Rwy'n rhoi Warriors o'r Net i chi. 

[VIDEO Playback] 

-Daeth gyda neges. Gyda protocol ei holl hun. Daeth i fyd o waliau tân creulon, llwybryddion di-hid, a pheryglon yn hyn yn waeth na marwolaeth. Mae'n gyflym. Mae'n gryf. Mae'n TCPIP. Ac mae wedi cael eich cyfeiriad. Rhyfelwyr y Net. 

[VIDEO END Playback] 

SIARADWR 1: Dyna sut y rhyngrwyd Bydd gweithio fel yr wythnos nesaf.