[CHWARAE CERDDORIAETH] DAVID J. Malan: pob hawl. Mae hyn yn CS50. Mae hon yn wythnos pum parhad, ac yr ydym yn gael rhywfaint o newyddion da a newyddion drwg. Felly, newyddion da yw bod CS50 lansio ddydd Gwener. Os hoffech chi ymuno â ni, mentro i'r URL arferol yma. Hyd yn oed yn well newyddion, dim darlith hyn yn dod Dydd Llun y 13eg. Ychydig yn llai yn well newyddion, cwis sero yw dydd Mercher nesaf. Mae rhagor o fanylion yn gael yn URL hwn yma. A thros y dyddiau ddwy nesaf byddwn yn llenwi'r bylchau o ran yr ystafelloedd y byddwn wedi neilltuo. Gwell newyddion yw bod chi helpu fod yn adolygu cyrsiau ar draws y sesiwn hon yn dod Dydd Llun yn y nos. Aros diwnio ar y cwrs yn gwefan y lleoliad a manylion. Adrannau, hyd yn oed er ei fod yn gwyliau, bydd hefyd yn cyfarfod hefyd. Newyddion gorau, darlith Dydd Gwener nesaf. Felly mae hwn yn draddodiad yr ydym gennych, yn unol â'r maes llafur. Just-- mae'n mynd i fod yn anhygoel. Byddwch yn gweld pethau fel strwythurau data amser cyson a thablau hash a choed a geisiau. A byddwn yn siarad am broblemau pen-blwydd. Mae criw cyfan o bethau aros Dydd Gwener nesaf. OK. Anyhow. Felly, yn cofio ein bod ni wedi ganolbwyntio ar y llun yma o'r hyn sydd tu mewn cof ein cyfrifiadur. Felly cof neu RAM yw lle mae rhaglenni bodoli tra eich bod yn eu rhedeg. Os ydych yn dwbl-gliciwch i icon i redeg rhyw raglen neu ddwbl-glicio i icon i agor rhai ffeil, caiff ei lwytho oddi wrth eich caled gyrru neu yrru cyflwr solet i mewn i RAM, Random Access Memory, lle mae'n byw nes bod y pŵer yn mynd i ffwrdd, y clawr y gliniadur yn cau, neu os ydych yn gadael y rhaglen. 

Nawr bod cof, o sydd mae'n debyg bod gennych 1 gigabeit y dyddiau hyn, 2 gigabyte, neu hyd yn oed yn llawer mwy, yn gyffredinol osod allan ar gyfer rhaglen a roddir yn y math hwn o hirsgwar model cysyniadol lle mae gennym y pentwr ar y gwaelod a bagad o bethau eraill ar y brig. Y peth ar y brig rydym wedi gweld ar y llun siarad o'r blaen ond byth am yn y segment testun fel y'u gelwir. Segment Testun yn unig yw ffordd ffansi o ddweud y sero a rhai sy'n cyfansoddi eich rhaglen a luniwyd gwirioneddol. 

Felly pan fyddwch yn dwbl-glicio Microsoft Word ar eich Mac neu PC, neu pan fyddwch yn rhedeg dot slaes Mario ar Cyfrifiadur Linux yn eich ffenestr terfynell, y seroau a rhai sy'n cyfansoddi Gair neu Mario yn cael eu storio dros dro yn RAM eich cyfrifiadur yn yr hyn a elwir yn segment testun ar gyfer rhaglen benodol. Isod sy'n mynd ymgychwyn a data uninitialized. Mae hyn yn pethau fel newidynnau byd-eang, nad ydym wedi defnyddio llawer o, ond ar adegau rydym wedi Roedd gan newidynnau byd-eang neu llinynnau a ddiffinnir statically sy'n ei godio geiriau fel "helo" anodd nad ydynt yn cael eu cymryd i mewn gan y defnyddiwr sy'n cael eu hard-coded i mewn i'ch rhaglen. 

Yn awr, i lawr ar y gwaelod i ni yn cael y pentwr fel y'u gelwir. Ac yn y pentwr, hyd yma, rydym wedi bod defnyddio ar gyfer pa fathau o ddibenion? Beth sydd y pentwr ei ddefnyddio ar gyfer? Yeah? 

CYNULLEIDFA: Swyddogaethau. 

DAVID J. Malan: Ar gyfer swyddogaethau? Ym mha ystyr gyfer swyddogaethau? 

CYNULLEIDFA: Pan fyddwch yn ffonio swyddogaeth, mae'r dadleuon yn cael eu copïo ar y pentwr. 

DAVID J. Malan: Yn union. Pan fyddwch yn ffonio swyddogaeth, ei dadleuon yn cael eu copïo ar y pentwr. Felly unrhyw X neu Y. neu A neu B eich bod yn pasio i mewn i swyddogaeth yn cael eu rhoi dros dro ar y pentwr fel y'u gelwir, yn union fel un o'r Annenberg hambyrddau neuadd fwyta, a hefyd pethau fel newidynnau lleol. Os yw eich swyddogaeth foo neu'ch gyfnewid swyddogaeth wedi newidynnau lleol, fel tymheredd, dau rhai yn y pen draw ar y pentwr. Yn awr, ni fyddwn yn siarad gormod am nhw, ond mae newidynnau amgylcheddol hyn ar y gwaelod gwelsom beth amser yn ôl pan Roeddwn yn futzing ar y bysellfwrdd un diwrnod ac yr wyf yn dechrau cael gafael ar bethau fel argv 100 neu argv 1,000, jyst elements-- rwy'n anghofio y numbers-- ond bod Nid oedd i fod i gael mynediad gan i mi. Rydym yn dechrau gweld rhai ffynci symbolau ar y sgrin. Dyna oedd hyn a elwir yn newidynnau amgylchedd fel lleoliadau byd-eang ar gyfer fy rhaglen neu am 'm chyfrifiadur, nid heb unrhyw gysylltiad â'r diweddar bug a drafodwyd, Shellshock, sydd wedi bod plaguing eithaf ychydig o gyfrifiaduron. 

Nawr yn olaf, mewn ffocws heddiw byddwn yn y pen draw ar y domen. Mae hyn yn darn arall o gof. Ac yn sylfaenol i gyd mae hyn cof yn yr un pethau. Mae yr un caledwedd. Rydym yn unig fath o thrin gwahanol glystyrau o bytes i wahanol bwrpasau. Mae'r domen hefyd yn mynd i fod yn lle newidynnau a chof yr ydych yn gofyn am oddi wrth y system weithredu yn cael ei storio dros dro. 

Ond mae fath o broblem yma, gan fod y darlun yn awgrymu. Rydym yn fath o gael dau llongau am i wrthdaro. Oherwydd fel y byddwch yn defnyddio mwy a mwy o o'r pentwr, ac fel y gwelwn heddiw ymlaen, wrth i chi ddefnyddio mwy a mwy o domen, yn sicr y gallai pethau drwg yn digwydd. Ac yn wir, gallwn gymell y fwriadol neu'n anfwriadol. Felly yr Cliffhanger diwethaf Roedd amser yn y rhaglen hon, nad oedd yn gweini unrhyw swyddogaethol ddiben ac eithrio i ddangos sut yr ydych yn fel y gall dyn drwg mewn gwirionedd yn cymryd mantais o chwilod yn rhaglen rhywun ac yn cymryd dros raglen neu hyd yn oed system gyfrifiadurol cyfan neu gweinydd. Felly, dim ond er mwyn yr olwg fyr, byddwch yn sylwi bod prif ar y gwaelod cymryd mewn llinell orchymyn dadleuon, yn unol argv. Ac mae ganddo alwad i ffwythiant f, hanfod yn ddienw swyddogaeth o'r enw f, ac mae'n pasio mewn argv [1]. 

Felly, pa bynnag air y mathau o ddefnyddwyr mewn o y brydlon ar ôl enw'r rhaglen hon, ac yna mae hyn yn swyddogaeth mympwyol i fyny top, f, yn cymryd mewn llinyn, AKA golosg *, fel yr ydym wedi dechrau trafod, a 'i jyst yn galw yn "bar." Ond gallem ei alw'n unrhyw beth. Ac yna mae'n datgan, y tu mewn o f, amrywiaeth o gymeriadau Gelwir c-- 12 o gymeriadau o'r fath. 

Yn awr, gan y stori roeddwn yn dweud funud yn ôl, lle er cof yn c, neu 12 y rhai chars mynd i roi diwedd ar i fyny? Dim ond i fod yn glir. Yeah? 

CYNULLEIDFA: Ar y pentwr. 

DAVID J. Malan: Ar y pentwr. Felly mae c yn newidyn lleol. Rydym yn gofyn am 12 chars neu 12 bytes. Mae'r rhai yn mynd i roi diwedd ar i fyny ar y pentwr fel y'u gelwir. Yn awr yn olaf mae hyn swyddogaeth arall dyna mewn gwirionedd yn eithaf defnyddiol, ond nid ydym wedi defnyddio mewn gwirionedd ein hunain, strncopy. Mae'n golygu copi llinyn, ond unig N llythyrau, n cymeriadau. Felly, bydd cymeriadau n yn copïo o far i mewn c. A faint o? Mae hyd y bar. Felly, mewn geiriau eraill, bod un llinell, strncopy, yn mynd i gopïo bar yn effeithiol i c. 

Yn awr, dim ond i fath o rhagweld mae'r moesol y stori hon, hyn a allai achosi problemau yma? Hyd yn oed er ein bod yn edrych ar y darn o bar ac yn pasio i mewn strncopy, beth sy'n eich perfedd yn dweud wrthych yn dal torri am y rhaglen hon? Yeah? 

CYNULLEIDFA: Nid yw'n cynnwys lle i'r cymeriad null. DAVID J. Malan: Nid yw'n cynnwys lle i'r cymeriad null. O bosibl, yn wahanol i arfer y gorffennol nid ydym yn ei wneud hyd yn oed yn cael cymaint fel plws 1 i ddarparu ar gyfer y cymeriad null. Ond mae hyd yn oed yn waeth na hynny. Beth arall rydym yn methu â gwneud? Yeah? 

CYNULLEIDFA: [Anghlywadwy] DAVID J. Malan: Perffaith. Rydym wedi codio galed 12 'n bert yn fympwyol. Nid yw hynny'n gymaint y broblem, ond y ffaith nad ydym yn hyd yn oed wirio os hyd y bar yn llai na 12, ac os felly mae'n mynd i fod yn ddiogel i'w roi yn y cof Gelwir c yr ydym wedi dyrannu. Yn wir, os yw'r bar yn debyg 20 nod o hyd, Ymddengys swyddogaeth hon gael ei gopïo 20 cymeriadau o far i mewn c, a thrwy hynny cymryd o leiaf 8 bytes na ddylai fod. Dyna goblygiadau yma. 

Felly, yn rhaglen fer, torri. Nid yw o'r fath yn beth mawr. Efallai chi'n cael nam segmentu. Rydym wedi cael yr holl bugs mewn rhaglenni. Efallai y byddwn i gyd yn cael bugs mewn rhaglenni ar hyn o bryd. Ond beth yw'r goblygiadau? Wel, dyma fersiwn chwyddo i mewn o y darlun o gof fy cyfrifiadur. Mae hyn yn y waelod fy pentwr. Ac yn wir, ar yr union gwaelod yw beth sy'n Gelwir stac arferol rhiant, ffordd ffansi o ddweud hynny'n brif. Fel bod pwy bynnag a elwir yn y swyddogaeth dd yr ydym yn sôn amdano. Felly, mae hyn yn y waelod y pentwr. Cyfeiriad dychwelyd yn rhywbeth newydd. Mae bob amser wedi bod yno, wedi bod bob amser yn y llun. Rydym yn unig byth alw sylw ato. Oherwydd ei fod yn troi allan y ffordd y c gweithio yw pan fydd un yn galw swyddogaeth arall, nid yn unig yn gwneud y dadleuon i hynny swyddogaeth yn cael eu gwthio ar y pentwr, nid yn unig yn gwneud lleol y swyddogaeth yn newidynnau yn cael eu gwthio ar y pentwr, rhywbeth a elwir yn gyfeiriad dychwelyd hefyd yn cael ei roi ar y pentwr. Yn benodol, os yw prif alwadau foo, prif yn gyfeiriad ei hun mewn cof, ych rhywbeth, effeithiol yn cael ei roi ar y pentwr felly pan f yn cael ei wneud cyflawni ei gwybod ble i neidio yn ôl i yn y testun segment er mwyn parhau gweithredu. 

Felly, os ydym ni yma yn gysyniadol, yn y prif, yna f yn cael ei alw. Sut mae f yn gwybod pwy i reoli â llaw yn ôl? Wel, mae hyn ychydig briwsion bara mewn coch yma, Gelwir y cyfeiriad dychwelyd, 'i jyst sieciau, beth yw bod cyfeiriad dychwelyd? O, gadewch i mi neidio yn ôl i brif yma. Ac mae hynny'n ychydig o gorsymleiddio, oherwydd bod y seroau a rhai ar gyfer y prif yn dechnegol i fyny yma yn y segment dechnoleg. Ond dyna y syniad. f jyst wedi i wybod beth i lle mae rheolaeth yn y pen draw yn mynd yn ôl. 

Ond mae'r ffordd y cyfrifiaduron wedi gosod hir allan bethau fel newidynnau lleol ac dadleuon yn debyg i hyn. Felly, yn y frig y llun yn glas yw'r ffrâm pentwr ar gyfer f, felly mae'r holl o'r cof bod f yn benodol gan ddefnyddio. Felly yn unol â hynny, yn sylwi bod bar sydd yn y llun. Bar oedd ei ddadl. Ac rydym yn honni bod dadleuon i swyddogaethau yn cael eu gwthio ar y pentwr. A c, wrth gwrs, yw Hefyd yn y llun. 

A dim ond ar gyfer dibenion nodiannol, sylwi ar y gornel chwith uchaf yn beth fyddai c braced 0 a Yna, ychydig i lawr ar y dde yn c braced 11. Felly, mewn geiriau eraill, gallwch ddychmygu fod yna grid o bytes yno, cyntaf ohonynt yw top chwith, gwaelod ohonynt yw'r olaf o'r rhai 12 bytes. 

Ond yn awr yn ceisio gyflym ymlaen. Yr hyn sydd ar fin digwydd os byddwn yn pasio mewn bar llinyn sy'n hwy nag c? Ac nid ydym yn gwirio os mae'n wir yn hwy na 12. Pa ran o'r darlun hwn yn mynd i cael overwritten gan bytes 0, 1, 2, 3, dot dot dot, 11, ac yna ddrwg, 12, 13 drwy 19? Beth sy'n mynd i ddigwydd yma, os ydych yn casglu o'r archebu bod c braced 0 yw ar y top a c braced 11 yn fath o lawr ar y dde? Yeah? 

CYNULLEIDFA: Wel, mae'n mynd i ysgrifennu dros y bar torgoch *. 

DAVID J. Malan: Yeah, mae'n edrych fel ydych yn mynd i ysgrifennu dros torgoch bar *. Ac yn waeth, os ydych yn anfon mewn 'n sylweddol hir llinyn, efallai y byddwch hyd yn oed yn throsysgrifo beth? Mae'r cyfeiriad dychwelyd. Sydd unwaith eto, yn union fel briwsion bara i ddweud wrth y rhaglen ble i fynd yn ôl i'r adeg pan f cael ei wneud yn cael ei alw. 

Felly pa ddrwg guys fel arfer yn ei wneud yw os ydynt yn dod ar draws rhaglen eu bod yn chwilfrydig a oes yn ecsploetio'n, bygi yn y fath fodd y gall ef neu hi eu cymryd manteisio ar hynny byg, gyffredinol, nid ydynt yn cael hawl hon y tro cyntaf. Maent yn unig yn dechrau anfon, er enghraifft, llinynnau ar hap i mewn i'ch rhaglen, boed ar y bysellfwrdd, neu'n dweud y gwir mae'n debyg ysgrifennu ychydig o raglen i ddim ond cynhyrchu llinynnau yn awtomatig, a dechrau curo ar eich rhaglen gan anfon mewn llawer o wahanol fewnbynnau yn wahanol hyd. 

Cyn gynted ag y bydd eich dyrfau rhaglen, mae hynny'n beth anhygoel. Oherwydd mae'n golygu ei fod neu hi wedi darganfod yr hyn sydd yn ôl pob tebyg yn wir a bug. Ac yna gallant gael mwy clyfar a dechrau canolbwyntio fwy cul ar sut i fanteisio ar y nam. Yn benodol, yr hyn y gallai ef neu hi wneud yw anfon, yn yr achos gorau, helo. Nid oes llawer mawr. Mae'n llinyn sy'n ddigon byr. Ond beth os yw ef neu hi yn anfon, a byddwn yn cyffredinoli fel, ymosodiad code-- felly zeros a rhai sy'n gwneud pethau fel rm-RF, sy'n tynnu popeth o'r ddisg galed neu anfon spam neu rhywsut ymosod ar y peiriant? 

Felly, os bydd pob un o'r rhain llythrennau A dim ond yn cynrychioli, gysyniadol, ymosodiad, ymosodiad, ymosodiad, ymosodiad, mae rhai cod gwael bod rhywun arall yn ysgrifennu, ond os yw'r person yn ddigon smart i nid yn unig yn cynnwys yr holl o'r rhai rm-RFS, ond hefyd Bod ei ychydig beit diwethaf fod yn rhif sy'n cyfateb at y cyfeiriad ei neu hi cod ymosodiad ei hun ei fod wedi pasio mewn dim ond trwy ddarparu ei wrth yr anogwr, gallwch castia y cyfrifiadur yn effeithiol i sylwi pan f yn cael ei wneud cyflawni, oh, mae'n amser i mi i neidio yn ôl i'r cyfeiriad dychwelyd coch. Ond, oherwydd ei fod wedi rywsut gorgyffwrdd y cyfeiriad dychwelyd gyda eu rhif eu hunain, ac eu bod yn ddigon craff i wedi ffurfweddu bod rhif i gyfeirio, fel y weld yn y top super gornel chwith yno, y cyfeiriad gwirioneddol yn y cyfrifiadur cof am rai o'u cod ymosodiad, gall dyn drwg castia y cyfrifiadur i mewn i weithredu ei god ei hun. 

A bod y cod, unwaith eto, gall fod yn unrhyw beth. Mae'n cael ei alw yn gyffredinol cod cregyn, sydd ychydig ffordd o ddweud nad yw'n gyffredinol yn rhywbeth mor syml â rm-RF. Mae'n mewn gwirionedd yn rhywbeth fel Bash, neu'r rhaglen wirioneddol sy'n rhoi iddo i reolaeth y rhaglennol i weithredu unrhyw beth arall y maent yn dymuno. Felly, yn fyr, mae hyn i gyd yn deillio o'r ffaith syml bod nam yma dan sylw beidio gwirio ffiniau eich arae. Ac oherwydd y ffordd cyfrifiaduron gwaith yw eu bod yn defnyddiwch y pentwr o effeithiol, yn gysyniadol, gwaelod ar i fyny, ond yna yr elfennau chi wthio ar y pentwr tyfu brig i lawr, mae hyn yn hynod broblematig. Yn awr, mae yna ffyrdd i weithio o amgylch hyn. Ac yn dweud y gwir, mae yna ieithoedd â hwy i weithio o amgylch hyn. Java yn imiwnedd, er enghraifft, at y mater penodol hwn. Oherwydd nad ydynt yn rhoi awgrymiadau i chi. Nid ydynt yn rhoi i chi cyfeiriadau cof uniongyrchol. Felly, gyda pŵer hwn sydd gennym i gyffwrdd ag unrhyw beth mewn cof rydym eisiau dod, rhaid cyfaddef, risg mawr. 

Felly cadwch lygad allan. Os, dweud y gwir, yn y misoedd neu flynyddoedd i ddod, unrhyw bryd eich bod yn darllen am rai ecsbloetio o raglen neu weinydd, os ydych chi erioed yn gweld awgrym o rywbeth fel trawiad ar y gorlif byffer, neu Gorlif stac yn fath arall o ymosodiad, debyg o ran ysbryd, gymaint ag ysbrydoli y wefan enw, os ydych yn ei wybod, 'i' i gyd yn siarad am yn unig gorlifo maint rhai gymeriad amrywiaeth neu ryw amrywiaeth yn fwy cyffredinol. Unrhyw gwestiynau, yna, ar hyn? Peidiwch â cheisio hyn yn y cartref. 

Mae pob hawl. Hyd yn malloc hyd yn hyn wedi bod yn ein newydd cyfaill yn y gallwn ddyrannu cof nad ydym o reidrwydd yn gwybod yn ymlaen llaw ein bod am felly nid oes gennym i cod caled i mewn i'n nifer y rhaglen fel 12. Unwaith y bydd y defnyddiwr yn dweud wrthym faint o data ef neu hi eisiau mewnbwn, gallwn malloc bod llawer o gof. 

Felly malloc mae'n troi allan, i'r raddau rydym wedi bod yn ei ddefnyddio, benodol tro diwethaf, ac wedyn chi guys wedi bod yn defnyddio ei gyfer getstring ddiarwybod i sawl wythnos, pob un o gof malloc yn dod o'r domen hyn a elwir yn. A dyma pam getstring, er enghraifft, Gellir neilltuo cof ddynamig heb wybod beth rydych chi'n mynd i deipio o flaen llaw, llaw i chi yn ôl pwyntydd i'r cof, a bod y cof yn dal i chi i gadw, hyd yn oed ar ôl getstring ffurflenni. Gan fod galw i gof ar ôl yr holl bod y pentwr yn mynd yn gyson i fyny ac i lawr, fyny ac i lawr. A chyn gynted ag y mae'n mynd i lawr, mae hynny'n golygu unrhyw cof swyddogaeth hon a ddefnyddir dylai Nid yw yn cael ei ddefnyddio gan unrhyw un arall. Mae'n gwerthoedd garbage nawr. 

Ond mae'r domen i fyny fan hyn. A beth sy'n neis am malloc yw bod pan malloc yn dyrannu cof i fyny fan hyn, nad yw'n cael effaith, ar gyfer y rhan fwyaf, gan y pentwr. Ac felly gall unrhyw swyddogaeth gael mynediad cof sydd wedi'i malloc'd, hyd yn oed gan swyddogaeth fel getstring, hyd yn oed ar ôl iddo gael ei ddychwelyd. 

Yn awr, mae'r gwrthwyneb o malloc yn rhad ac am ddim. Ac yn wir, y rheol i chi angen iddynt ddechrau mabwysiadu yn unrhyw, unrhyw, unrhyw tro y byddwch yn defnyddio malloc mae'n rhaid i chi eich hun yn ei ddefnyddio am ddim, yn y pen draw, ar yr un pwyntydd. Pob yr amser hwn, rydym wedi bod yn ysgrifennu bygi, cod bygi, am nifer o resymau. Ond un o'r rhain wedi bod yn defnyddio'r llyfrgell CS50, a oedd yn ei hun yn fwriadol buggy, mae'n gollwng cof. Unrhyw bryd y byddwch wedi galw getstring dros yr ychydig wythnosau diwethaf rydym yn gofyn i'r gweithredu system, Linux, er cof. Ac yr ydych wedi erioed unwaith a roddwyd yn ôl. Ac nid yw hyn yn, yn ymarfer, yn beth da. 

Ac Valgrind, un o'r arfau a gyflwynwyd yn Pset 4, yn ymwneud â chi helpu bellach yn dod o hyd i chwilod fel 'na. Ond diolch byth am Pset 4 Nid oes angen i chi i ddefnyddio'r llyfrgell CS50 neu'r getstring. Felly mae unrhyw namau yn ymwneud â cof yn y pen draw yn mynd i fod yn eich pen eich hun. 

Felly malloc yn fwy na dim ond gyfleus ar gyfer y diben hwn. Gallwn yn awr mewn gwirionedd yn datrys sylfaenol wahanol broblemau, a datrys problemau sylfaenol yn fwy effeithiol fel yr addewid wythnos sero ar. Hyd yma mae hyn yw'r sexiest strwythur data rydym wedi cael. A thrwy strwythur data Fi jyst yn ei olygu ffordd o conceptualizing cof mewn ffordd sy'n mynd y tu hwnt dim ond dweud, mae hwn yn int, mae hwn yn torgoch. Gallwn ddechrau clwstwr pethau at ei gilydd. 

Felly amrywiaeth yn edrych fel hyn. A beth yn allweddol mewn tua amrywiaeth yw ei fod yn rhoi i chi darnau o gefn-wrth-gefn cof, pob un ohonynt yn mynd i fod o'r un math, int, int, int, int, neu torgoch, cols, torgoch, torgoch. Ond mae ychydig o anfanteision. Mae hyn er enghraifft, yn amrywiaeth o maint chwech. Gadewch i ni dybio eich llenwi arae hwn gyda chwech rhifau ac yna, am ba bynnag reswm, eich defnyddiwr eisiau rhoi chi seithfed rif. Ble ydych chi'n ei roi? 

Beth yw'r ateb os oes gennych greu amrywiaeth ar y corn, er enghraifft, dim ond yn yr wythnos dau nodiant a gyflwynwyd gennym, o gromfachau sgwâr gyda nifer y tu mewn? Wel, oes gennych chi chwe rhifau yn y blychau hyn. Beth fyddai eich greddf fod? Ble fyddech chi eisiau ei roi? 

CYNULLEIDFA: [Anghlywadwy] 

DAVID J. Malan: Mae'n ddrwg gennyf? 

CYNULLEIDFA: Rhowch ef ar y diwedd. 

DAVID J. Malan: Rhowch ef ar y diwedd. Felly, ychydig dros ar y dde, y tu allan i'r bocs. Pa yn neis, ond mae'n troi allan na allwch wneud hynny. Oherwydd os nad ydych wedi gofyn ar gyfer darn hwn o gof, gallai fod gan gyd-ddigwyddiad bod hyn yn cael ei ddefnyddio gan rai newidyn arall yn gyfan gwbl. Meddyliwch yn ôl rhyw wythnos pan fyddwn yn gosodwyd allan enwau Zamyla a Davin a Gabe yn mewn cof. Roeddent yn llythrennol gefn wrth gefn wrth gefn. Felly, na allwn o reidrwydd ymddiried bod beth bynnag ei dros yma ar gael i mi ei ddefnyddio. 

Felly, beth arall y gallech ei wneud? Wel, ar ôl sylweddoli i chi Mae angen amrywiaeth o faint saith, fe allech chi jyst greu amrywiaeth o faint saith yna defnyddiwch a ar gyfer dolen neu dolen tra, gopïo i mewn i'r amrywiaeth newydd, ac yna rhywsut dim ond cael gwared o amrywiaeth hwn neu dim ond rhoi'r gorau i'w defnyddio. Ond nid yw hynny'n arbennig o effeithlon. Yn fyr, nid yw araeau yn gadael chi ddeinamig newid maint. 

Felly, ar y naill law a gewch mynediad ar hap, sydd yn anhygoel. Oherwydd ei fod yn gadael i ni wneud pethau fel rhaniad a goncro, chwiliad deuaidd, pob un ohonynt rydym wedi yn siarad am ar y sgrin yma. Ond byddwch yn peintio eich hun i mewn i gornel. Cyn gynted ag y byddwch yn taro diwedd eich array, rhaid i chi wneud yn iawn llawdriniaeth yn ddrud neu ysgrifennu criw cyfan o god yn hyn ymdrin â'r broblem. 

Felly beth os yn lle hynny oedd gennym rhywbeth a elwir yn rhestr, neu restr sy'n gysylltiedig yn benodol? Beth os hytrach na gorfod petryalau yn ôl i yn ôl i'r cefn, mae gennym petryalau sy'n gadael ychydig ychydig o ystafell wiggle mewn rhyngddynt? A hyd yn oed er fy mod i wedi tynnu hyn llun neu ei addasu y llun o un o'r testunau yma i fod yn ôl i gefn wrth gefn drefnus iawn, mewn gwirionedd, un o'r petryalau rhai Gallai fod hyd yma mewn cof. Gallai un ohonynt fod hyd yma. Gallai un ohonynt fod hyd yma, dros yma, ac yn y blaen. 

Ond beth os ydym yn tynnu, yn yr achos hwn, saethau hynny rywsut yn cysylltu'r rhain petryal gyda'i gilydd? Yn wir, rydym wedi gweld technegol ymgnawdoliad saeth. Beth rydym wedi ei ddefnyddio mewn diweddar dyddiau hynny, o dan y cwfl, yn cynrychioli saeth? Mae pwyntydd, dde? 

Felly beth os, yn hytrach na dim ond storio y rhifau, fel 9, 17, 22, 26, 34, beth os nad ydym yn storio dim ond nifer ond pwyntydd nesaf i bob rhif o'r fath? Fel bod cymaint fel y byddech yn edau a nodwydd drwy criw cyfan o ffabrig, pethau rhywsut clymu gyda'i gilydd, gall yr un modd rydym gydag awgrymiadau, fel y incarnated gan saethau yma, fath o wau petryalau unigol hyn drwy effeithiol gan ddefnyddio pwyntydd nesaf i bob rhif sy'n yn cyfeirio at ryw rhif nesaf, y tynnu sylw at, yn ei dro, mae rhai rhif nesaf? Felly, mewn geiriau eraill, yr hyn os ydym eisiau mewn gwirionedd i weithredu rhywbeth fel hyn? Wel yn anffodus, petryalau hyn, o leiaf yr un gyda 9, 17, 22, ac yn y blaen, bellach mae'r rhain yn sgwariau braf gyda rhifau sengl. Y gwaelod, petryal o dan 9, er enghraifft, cynrychioli'r hyn y dylai fod yn pwyntydd, 32 darnau. Nawr, dydw i ddim yn ymwybodol o unrhyw fath ddata eto yn C sy'n rhoi nid yn unig yn int chi ond mae pwyntydd yn gyfan gwbl. 

Felly beth yw'r ateb os ydym am i ddyfeisio ateb ein hunain i hyn? Yeah? 

CYNULLEIDFA: [Anghlywadwy] 

DAVID J. Malan: Beth sy'n bod? 

CYNULLEIDFA: Strwythur newydd. 

DAVID J. Malan: Yeah, felly pam peidiwch â ni greu strwythur newydd, neu yn C, mae struct? Rydym wedi gweld structs o'r blaen, os yn fyr, lle rydym yn ymdrin â strwythur i fyfyrwyr fel hyn, a gafodd enw a thŷ. Yn Pset 3 breakout ddefnyddiwyd gennych yn ei gyfanrwydd criw o GRect a GOvals structs-- bod Stanford a grëwyd i Gwybodaeth clwstwr gyda'i gilydd. Felly beth os ydym yn cymryd hyn un syniad o y geiriau allweddol "typedef" a "struct," ac yna mae rhai pethau penodol i fyfyrwyr-, ac esblygu hyn i mewn i'r canlynol: typedef struct node-- a'r nod yw dim ond gwyddoniaeth gyfrifiadurol generig iawn dymor am rywbeth mewn strwythur data, cynhwysydd mewn strwythur data. Mae nod allaf hawlio yn mynd i gael mae n int, yn hollol syml, ac yna ychydig yn fwy gryptig, yr ail linell, nod struct * nesaf. Ond mewn termau llai technegol, beth yw bod ail linell o god y tu mewn i'r braces cyrliog? Yeah? 

CYNULLEIDFA: [Anghlywadwy] DAVID J. Malan: A pwyntydd i'r nôd arall. Felly rhaid cyfaddef, cystrawen ychydig yn cryptig. Ond os ydych yn darllen yn llythrennol, nesaf yw enw'r newidyn. Beth yw ei fath ddata? Mae'n ychydig o verbose y tro hwn, ond mae'n y math nôd struct *. Unrhyw amser yr ydym wedi gweld seren rywbeth, bod yn golygu ei fod yn pwyntydd i'r math data. Felly nesaf yn ôl pob golwg yn bwyntydd at nod struct. 

Yn awr, beth yw nod struct? Wel, yn sylwi ydych yn gweld rhai un geiriau ar gornel dde uchaf. Ac yn wir, yr ydych hefyd yn gweld y gair "Nod" i lawr yma ar waelod chwith. Ac mae hyn yn mewn gwirionedd yn unig yw hwylustod. Sylwch fod yn ein diffiniad myfyrwyr mae y gair "myfyriwr" unwaith yn unig. Ac mae hynny oherwydd myfyriwr Nid yw gwrthrych yn hunan-cyfeiriadol. Does dim byd y tu mewn o fyfyriwr y mae angen i bwyntio i fyfyriwr arall, persay. Byddai hynny'n fath o rhyfedd yn y byd go iawn. 

Ond gyda nod mewn cysylltiedig rhestr, rydym yn ei wneud am gael nod i fod yn cyfeiriadol i wrthrych tebyg. Ac felly yn sylwi na fydd y newid yma yw union beth sydd y tu mewn i'r braces cyrliog. Ond rydym yn ychwanegu y gair "nod" ar y brig yn ogystal ag ychwanegu at y gwaelod yn lle "myfyrwyr." Ac mae hyn yn unig yw manylion technegol fel eu bod, unwaith eto, eich strwythur data Gall fod yn hunan-cyfeiriadol, fel bod Gall nod bwyntio at nod o'r fath arall. 

Felly beth mae hyn yn y pen draw mynd i olygu i ni? Wel, un, y pethau y tu mewn yn cynnwys ein nod. Mae hyn yn beth i fyny yma, dde uchaf, yn unig yw hynny hynny, unwaith eto, gallwn gyfeirio at ein hunain. Ac yna y stwff pellaf, er bod nod yn derm newydd, efallai, mae'n dal i fod yr un fath â myfyrwyr a beth oedd o dan y cwfl yn SPL. 

Felly, os ydym yn awr yn awyddus i ddechrau weithredu'r rhestr cysylltiedig, sut y gallem cyfieithu rhywbeth fel hyn i cod? Wel, gadewch i ni weld enghraifft o raglen sy'n mewn gwirionedd yn defnyddio rhestr gysylltiedig. Ymhlith cod dosbarthu heddiw yn rhaglen o'r enw Rhestr Zero. Ac os wyf yn rhedeg hyn yr wyf yn creu super GUI syml, Rhyngwyneb Defnyddiwr Graffigol, ond mae'n wirioneddol yn unig printf. Ac yn awr yr wyf wedi rhoi fy hun ychydig o fwydlen options-- Ddilea, Mewnosod, Chwilio, a Traverse. Ac Ymadael. Mae'r rhain yn weithrediadau unig gyffredin ar strwythur data a elwir yn rhestr gyswllt. 

Yn awr, Dileu yn mynd i dileu nifer o'r rhestr. Mewnosod yn mynd i ychwanegu mae nifer at y rhestr. Chwilio yn mynd i edrych am rif yn y rhestr. Ac Traverse yn unig yw ffordd ffansi o ddweud, cerdded drwy'r rhestr, ei hargraffu, ond dyna ni. Peidiwch â newid mewn unrhyw ffordd. 

Felly gadewch i ni roi cynnig ar hyn. Gadewch i ni fynd yn ei flaen a math 2. Ac yna yr wyf i'n mynd i rhowch y rhif, dywedwch 9. Enter. Ac yn awr fy rhaglen yn unig raglennu i ddweud, rhestr yn awr 9. Yn awr, os wyf yn mynd yn ei flaen a yn Mewnosod eto, gadewch i mi fynd yn ei flaen ac yn chwyddo allan a theipiwch yn 17. Nawr mae fy rhestr yw 9, ac yna 17. Os byddaf yn gwneud mewnosoder eto, gadewch i hepgor un. Yn hytrach na 22, yn unol â'r darlun rydym wedi bod yn edrych ar fan hyn, gadewch i mi neidio ymlaen a rhowch yn ei le 26 nesaf. Felly dw i'n mynd i deipio 26. Mae'r rhestr fel yr wyf yn disgwyl. Ond yn awr, dim ond i weld os y cod hwn yn mynd i fod yn hyblyg, gadewch i mi yn awr math 22, a oedd o leiaf yn gysyniadol, os ydym yn gan gadw i'r hyn didoli, sydd yn wir mynd i fod yn gôl arall ar hyn o bryd, Dylai fynd i mewn rhwng 17 a 26. Felly, yr wyf daro Chofnoda. Yn wir, mae hynny'n gweithio. Ac felly yn awr gadewch i mi mewnosoder y diwethaf, fesul y llun, 34. 

Mae pob hawl. Felly, am y tro, gadewch i mi nodi y Dileu a Traverse a Chwilio yn ei wneud, mewn gwirionedd, yn gweithio. Yn wir, os wyf yn Chwilio rhedeg, gadewch i ni chwilio am y rhif 22, Enter. Canfu 22. Felly dyna beth y mae hyn rhaglen Rhestr Zero yn ei wneud. 

Ond beth sy'n digwydd mewn gwirionedd ar hynny yn gweithredu hyn? Wel, yn gyntaf efallai y byddwn wedi, ac yn wir Oes gennyf, ffeil o'r enw list0.h. Ac yn rhywle yn mae hyn yn llinell, typedef, nod struct, Yna, yr wyf wedi fy braces cyrliog, int n, ac Yna struct-- beth oedd y diffiniad? Nod Struct nesaf. Felly mae angen i'r seren. Nawr yn dechnegol rydym yn cael i mewn i yr arfer o dynnu hynny yma. Efallai y byddwch yn gweld gwerslyfrau a cyfeiriadau ar-lein yn ei wneud yno. Mae'n swyddogaethol cyfwerth. Mewn gwirionedd, mae hyn yn ychydig yn fwy nodweddiadol. Ond byddaf yn gyson â'r hyn gwnaethom y tro diwethaf a gwneud hyn. Ac yna yn olaf, yr wyf i'n mynd i wneud hyn. 

Felly, mewn ffeil header rhywle, mewn list0.h heddiw yw diffiniad struct hwn, ac efallai rhai pethau eraill. Yn y cyfamser yn list0c mae mynd i fod ychydig o bethau. Ond rydym ni'n mynd i ddim ond cychwyn ac nid gorffen hyn. List0.h yn ffeil yr wyf am i gynnwys yn fy ffeil C. Ac yna ar ryw adeg rwy'n mynd i gael int, prif, annilys. Ac yna yr wyf i'n mynd i cael rhywfaint o i-wneud yn fan hyn. Rwyf hefyd yn mynd i gael prototeip, fel ddi-rym, chwilio, int, n, y mae eu pwrpas mewn bywyd yw i chwilio am elfen. Ac yna i lawr yma i'n hawlio yn cod heddiw, yn ddi-rym, chwilio, int, n, dim hanner colon ond braces cyrliog agored. Ac yn awr yr wyf am i chwilio rhywsut ar gyfer elfen yn y rhestr hon. Ond nid oes gennym ddigon o gwybodaeth ar y sgrin eto. Mae gen i nad yw mewn gwirionedd yn cynrychioli y rhestr ei hun. Felly, un ffordd y gallem gweithredu rhestr gysylltiedig mewn rhaglen yw wyf yn fath o eisiau gwneud rhywbeth fel ddatgan rhestr gysylltiedig fyny yma. Er hwylustod, dw i'n mynd i wneud hyn yn fyd-eang, er bod yn ein bod yn gyffredinol Ni ddylai wneud hyn gormod. Ond bydd yn symleiddio'r yr enghraifft hon. Felly, yr wyf am ddatgan restr cysylltu fan hyn. Nawr, sut y gallwn wneud hynny? 

Dyma y llun o restr cysylltiedig. Ac nid wyf yn ei wneud mewn gwirionedd yn gwybod ar hyn o bryd sut y Rydw i'n mynd i fynd ati i gynrychioli cymaint o bethau ag un yn unig amrywiol yn y cof. Ond yn meddwl yn ôl eiliad. Mae hyn i gyd o amser rydym wedi cael llinynnau, yr ydym wedyn yn datgelu i fod yn araeau o cymeriadau, yr ydym wedyn yn datgelu i ddim ond fod yn pwyntydd i gymeriad cyntaf mewn amrywiaeth o gymeriadau sy'n cael ei derfynu nwl. Felly, gan y rhesymeg, a gyda hyn llun math o hadu eich meddyliau, yr hyn y mae angen i ni mewn gwirionedd yn ysgrifennu yn ein cod i gynrychioli rhestr cysylltiedig? Faint o'r wybodaeth hon a oes angen i ddal yn y cod C, fyddech chi'n ei ddweud? Yeah? 

CYNULLEIDFA: Mae arnom angen pwyntydd i nod. DAVID J. Malan: A pwyntydd at nod. Yn arbennig, a oedd yn nod y byddai eich greddfau fod i gadw pwyntydd i? 

CYNULLEIDFA: Y nôd cyntaf. 

DAVID J. Malan: Yeah, yn ôl pob tebyg dim ond y cyntaf. Ac yn sylwi, y cyntaf nod yn siâp gwahanol. Mae'n dim ond hanner maint y struct, am ei fod yn wir, dim ond pwyntydd. Felly, beth allwch chi wir yn ei wneud yw datgan rhestr cysylltiedig i fod o fath nôd *. A gadewch i ni jyst alw yn gyntaf ac yn ymgychwyn i null. Felly null, unwaith eto, yn dod i mewn i'r darlun yma. Nid yn unig yn cael ei ddefnyddio null fel fel arbennig Gwerth gyfnewid am bethau fel getstring a malloc, null hefyd y sero bwyntydd, mae'r diffyg pwyntydd, os mynnwch. 'I jyst yn golygu dim byd eto fan hyn. Yn awr gyntaf, gallwn i wedi Gelwir unrhyw beth hwn. Gallwn fod wedi ei alw "rhestr" neu unrhyw nifer o bethau eraill. Ond dw i'n galw yn "gyntaf" fel bod mae llinellau i fyny ar y darlun hwn. Felly, yn union fel llinyn yn gallu cael eu cynrychioli gyda chyfeiriad ei beit cyntaf, felly gall rhestr cysylltiedig. A byddwn yn gweld data arall strwythurau yn cael eu cynrychioli gyda dim ond un pwyntydd, 32-bit saeth, pwyntio yn y nod cyntaf un yn y strwythur. 

Ond yn awr gadewch i ni rhagweld problem. Os ydw i'n cofio yn unig yn fy rhaglen y cyfeiriad y nod cyntaf, y cyntaf Petryal yn y strwythur data, yr hyn a oedd gan fod yn wir am y gwell gweithrediad y gweddill fy rhestr? Beth yw manylion allweddol sy'n mynd er mwyn sicrhau bod hyn yn gweithio mewn gwirionedd? A thrwy "mewn gwirionedd yn gweithio" Rwy'n yn golygu, yn debyg iawn i llinyn, gadael i ni fynd o gymeriad cyntaf yn enw'r Davin i'r ail, i'r trydydd, i'r bedwerydd, at y diwedd un, sut rydym yn gwybod pan fyddwn ni'n ar y diwedd o restr cysylltiedig sy'n edrych fel hyn? Pan mae'n null. Ac yr wyf wedi cynrychioli y math hwn o fel fel gallai peiriannydd trydan, gyda'r sylfaen bach symbol, o ryw fath. Ond mae hynny'n ei olygu yw null yn yr achos hwn. Gallwch dynnu unrhyw nifer o ffyrdd, ond mae awdur hwn ddigwyddodd i ddefnyddio'r symbol hwn yma. 

Ar yr amod ein bod yn stringing pob un o'r nodau hyn at ei gilydd, Dim ond cofio ble yr un cyntaf yw, cyn belled wrth i ni rhoi symbol arbennig yn y nôd olaf un yn y rhestr, a byddwn yn defnyddio null, oherwydd dyna hyn sydd gennym ar gael i ni, rhestr hon yn gyflawn. A hyd yn oed os mai dim ond rhoi i chi pwyntydd yr elfen gyntaf, chi, y rhaglennydd, yn sicr gael mynediad at y gweddill ohono. Ond gadewch i ni gadael i'ch meddyliau crwydro ychydig bach, os nad ydynt yn barod eithaf wandered-- beth sydd mynd i fod yr amser yn rhedeg o dod o hyd i unrhyw beth yn y rhestr hon? Damn ei, 'i' O fawr o n, sydd ddim yn ddrwg, i fod yn deg. Ond mae'n llinol. Yr ydym wedi rhoi'r gorau pa nodwedd o araeau drwy symud mwy tuag at y llun yma o ddeinamig gwehyddu gyda'i gilydd neu nodau cysylltiedig? Rydym wedi rhoi'r gorau mynediad ar hap. Amrywiaeth yn braf oherwydd popeth yn fathemategol yn gefn wrth gefn wrth gefn wrth gefn. Er bod y darlun hwn edrych yn bert, a hyd yn oed er ei fod yn edrych fel nodau hyn yn cael eu gwasgaru'n 'n glws ar wahân, mewn gwirionedd gallent fod yn unrhyw le. OX1, Ox50, Ox123, Ox99, mae'r rhain Gallai nodau fod unrhyw le. Oherwydd bod malloc yn dyrannu cof oddi wrth y domen, ond yn unrhyw le yn y domen. Dydych chi ddim o reidrwydd yn gwybod ei fod yn mynd i fod yn gefn wrth gefn wrth gefn. Ac felly y llun hwn mewn gwirionedd yn ddim yn mynd i fod yn eithaf hon 'n bert. 

Felly, mae'n mynd i gymryd ychydig o yn gweithio i weithredu'r swyddogaeth hon. Felly gadewch i ni weithredu nawr chwiliad. A byddwn yn gweld y math o ffordd glyfar o wneud hyn. Felly, os wyf yn swyddogaeth chwilio a Rydw i'n rhoi amrywiol, cyfanrif n i chwilio am, mae angen i mi wybod y cystrawen newydd i edrych y tu mewn strwythur sy'n tynnu sylw at, i ddod o hyd n. Felly gadewch i ni wneud hyn. 

Felly, cyntaf i mi i'n mynd i fynd ymlaen a datgan nod *. Ac yr wyf i'n mynd i alw yn pwyntydd, dim ond drwy confensiwn. Ac yr wyf i'n mynd i ymgychwyn i gyntaf. Ac yn awr y gallaf wneud hyn mewn nifer o ffyrdd. Ond dw i'n mynd i gymryd ymagwedd gyffredin. Er nad pwyntydd yn hafal i null, ac mae hynny'n cystrawen dilys. A 'i jyst yn golygu gwneud y canlynol, felly ar yr amod nad ydych yn pwyntio at ddim byd. Beth ydw i am ei wneud? 

Os yw n pwyntydd dot, gadewch i mi ddod yn ôl at hynny, equals-- hafal beth? Pa werth ydw i'n chwilio? Y n union a basiwyd mewn. Felly dyma nodwedd arall o C a llawer o ieithoedd. Er bod y strwythur a elwir yn nod Mae gan werth a n, hollol gyfreithlon hefyd i gael dadl lleol neu amrywiol o'r enw n. Oherwydd hyd yn oed yr ydym, gyda llygaid dynol, yn gallu gwahaniaethu n bod hyn yn ôl pob tebyg wahanol i n hwn. Oherwydd bod y gystrawen yn wahanol. Rydych chi wedi got a dot ac pwyntydd, tra bod yr un yma Nid oes y fath beth. Felly, mae hyn yn iawn. Hynny'n iawn eu galw yr un pethau. 

Os wyf yn ydych yn dod o hyd i hyn, rwy'n mynd i eisiau i wneud rhywbeth hoffi gyhoeddi ein bod yn dod o hyd n. A byddwn yn gadael hynny fel sylwadau neu cod pseudocode. Else, a dyma y rhan ddiddorol, beth ydw i am ei wneud os bydd y nôd presennol Nid yw cynnwys n fy mod yn poeni am? Sut ydw i'n cyrraedd y canlynol? Os yw fy mys yn y hyn o bryd yw PTR, ac mae'n pwyntio at ba bynnag cyntaf yn pwyntio at, sut ydw i'n symud fy mys at y nod nesaf yn y cod? Wel, beth yw'r briwsion bara rydym yn mynd i ddilyn yn yr achos hwn? CYNULLEIDFA: [Anghlywadwy]. DAVID J. Malan: Yeah, felly nesaf. Felly, os byddaf yn mynd yn ôl at fy cod yma, yn wir, rwy'n mynd i fynd yn ei flaen a dweud pwyntydd, a oedd yn yn unig yw variable-- dros dro 'i' enw rhyfedd, ptr, ond 'i' yn union fel temp-- Rydw i'n mynd i osod pwyntydd gyfartal i ba bynnag pwyntydd yw-- ac unwaith eto, mae hyn yn mynd i fod yn ychydig bygi ar gyfer dot moment-- nesaf. Mewn geiriau eraill, yr wyf i'n mynd i gymryd fy bys sydd wedi pwyntio at nod hwn yma ac yr wyf i'n mynd i ddweud, eich bod yn gwybod yr hyn, cymerwch olwg ar y cae nesaf ac yn symud eich bys i beth bynnag mae'n pwyntio at. Ac mae hyn yn mynd i ailadrodd, ailadrodd, dro ar ôl tro. Ond pan mae fy mys rhoi'r gorau i wneud unrhyw beth o gwbl? Cyn gynted ag yr hyn y llinell o god yn cychwyn? CYNULLEIDFA: [Anghlywadwy] DAVID J. Malan: Os yw pwynt tra Nid pwyntydd yn hafal i null. Ar ryw adeg fy mys yn mynd i fod yn pwyntio at null ac yr wyf i'n mynd i wireddu dyna ddiwedd y rhestr hon. Yn awr, mae hyn yn ychydig yn gorwedd gwyn ar gyfer symlrwydd. Mae'n ymddangos bod hyd yn oed er ein bod newydd eu dysgu nodiant hwn dot gyfer strwythurau, nid pwyntydd yn struct. ptr yw beth? Dim ond i fod yn fwy nitpicky. Mae'n pwyntydd i nod. Dyw hi ddim yn nod ynddo'i hun. Os oedd gen i ddim seren yma, pwyntydd absolutely-- ei fod yn nod. Mae hyn yn debyg i un wythnos datganiad o newidyn, er bod y gair "nod" yn newydd. 

Ond, cyn gynted ag y byddwn yn cyflwyno seren, 'i' bellach yn pwyntydd i nod. Ac yn anffodus ni allwch ddefnyddio'r y dot nodiant ar gyfer pwyntydd. Mae'n rhaid i chi ddefnyddio'r saeth nodiant, sydd, yn drawiadol, yw unrhyw ddarn y tro cyntaf cystrawen yn edrych 'n athrylithgar. Mae hyn yn llythrennol yn edrych fel saeth. Ac felly mae hynny'n beth da. Ac i lawr fan hyn yn llythrennol edrych fel saeth. Felly yr wyf yn credu mai dyna'r la-- Nid wyf yn ei wneud meddwl fy mod yn or-ymrwymo Yma-- wyf credu mai dyna'r darn newydd ddiwethaf cystrawen rydyn ni'n mynd i weld. Ac diolch byth, mae'n wir ychydig yn fwy 'n athrylithgar. 

Yn awr, ar gyfer y rhai ohonoch sydd Efallai y byddai'n well yn yr hen ffordd, gallwch barhau i ddefnyddio'r dot nodiant. Ond, fel y dydd Llun sgwrs, rydym yn gyntaf angen i chi fynd yno, ewch i hynny mynd i'r afael, ac yna gael mynediad i'r cae. Felly, mae hyn hefyd yn gywir. A dweud y gwir, mae hyn yn ychydig yn fwy bedantig. Rydych yn ei ddweud yn llythrennol, Dadgyfeirio y pwyntydd ac yn mynd yno. Yna cydio .n, y cae a elwir yn n. Ond dweud y gwir, does neb eisiau i deipio neu ddarllen hwn. Ac felly y byd dyfeisio y nodiant saeth, a oedd yn yn gyfwerth, union yr un fath, 'i' jyst siwgr cystrawennol. Felly, yn ffordd ffansi o ddweud hyn edrych yn well, neu'n edrych yn symlach. 

Felly, yn awr yr wyf i'n mynd i wneud un peth arall. Dw i'n mynd i ddweud "egwyl" unwaith dwi wedi ddarganfuwyd ei fod felly nid wyf yn cadw yn chwilio amdano. Ond mae hyn yn hanfod o swyddogaeth chwilio. Ond mae'n llawer haws, yn y pen draw, nid i gerdded drwy'r cod. Mae hyn yn wir yn y gweithredu ffurfiol o chwilio yn y cod dosbarthu heddiw. Mae'n siŵr gen i nad yw mewnosodiad yn arbennig o hwyl i gerdded trwy ar eu golwg, ac nid yw dileu, hyd yn oed ond ar ddiwedd y dydd maent yn berwi i lawr i deg heuristics syml. 

Felly gadewch i ni wneud hyn. Os wnewch chi helpu hiwmor mi yma, i ddim dod â criw o beli straen. Yr wyf yn dod â criw o rifau. A gallem gael dim ond ychydig o wirfoddolwyr i gynrychioli 9, 17, 20, 22, 29, a 34? Felly, yn y bôn mae pawb pwy sydd yma heddiw. Dyna oedd un, dau, tri, pedwar, pump, chwech o bobl. Ac yr wyf wedi cael cais i go-- weld, dim un yn y cefn yn codi eu dwylo. OK, un, dau, tri, pedwar, five-- gadewch i mi llwytho balance-- chwech. OK, byddwch chwech yn dod ymlaen i fyny. Bydd angen pobl eraill arnom. Rydym yn dod â peli straen ychwanegol. Ac os ydych yn allai, am dim ond hyn o bryd, llinell eich hunain i fyny yn unig fel hyn llun yma. 

Mae pob hawl. Gadewch i ni weld, beth yw eich enw? 

CYNULLEIDFA: Andrew. 

DAVID J. Malan: Andrew, rydych yn rhif 9. Neis i gwrdd â chi. Yma byddwch yn mynd. CYNULLEIDFA: Jen. DAVID J. Malan: Jen. Dafydd. Rhif 17. Ie? 

CYNULLEIDFA: Rwy'n Julia. 

DAVID J. Malan: Julia, David. Rhif 20. CYNULLEIDFA: Cristnogol. DAVID J. Malan: Cristnogol, David. Rhif 22. A? 

CYNULLEIDFA: JP. DAVID J. Malan: JP. Rhif 29. Felly, mynd yn ei flaen a chael in-- Uh oh. Uh oh. Standby. 20. Oes gan unrhyw un marciwr? CYNULLEIDFA: Mae gen i Sharpie. DAVID J. Malan: Rydych yn cael Sharpie? OK. Ac oes unrhyw un yn cael darn o bapur? Achub y ddarlith. Dewch ar. CYNULLEIDFA: Rydym wedi got it. DAVID J. Malan: Rydym yn cael ei? Mae pob hawl, diolch i chi. Yma rydym yn mynd. A oedd hyn yn oddi wrthych? Yr ydych newydd achub y dydd. Felly 29. Mae pob hawl. Yr wyf gamsillafu 29, ond yn OK. Fynd yn ei flaen. Mae pob hawl, byddaf yn rhoi i chi eich pen yn ôl am ennyd. Felly, rydym wedi Folks hyn yma. Gadewch i ni gael un arall. Gabe, ydych chi eisiau i chwarae yr elfen gyntaf yma? Bydd angen i chi Rydym i bwynt ar y rhain Folks ddirwy. Felly 9, 17, 20, 22, didoli o 29, ac yna 34. A wnaethom ni colli rhywun? Mae gen i 34. Lle did-- OK, sydd eisiau bod yn 34? OK, yn dod ar i fyny, 34. Mae pob hawl, bydd hyn yn yn werth y uchafbwynt. Beth yw eich enw? 

CYNULLEIDFA: Peter. 

DAVID J. Malan: Peter, yn dod ar i fyny. Mae pob hawl, felly dyma criw cyfan o nodau. Mae pob un ohonoch guys yn cynrychioli un o'r petryalau hyn. Ac Gabe, mae'r ychydig yn od dyn allan, yn cynrychioli gyntaf. Felly ei pwyntydd ychydig yn llai ar y sgrin na phawb arall. Ac yn yr achos hwn, bob un o'ch chwith dwylo yn mynd i naill ai dynnu i lawr, a thrwy hynny yn cynrychioli null, felly dim ond absenoldeb pwyntydd, neu mae'n mynd i gael ei bwyntio ar nod nesaf i chi. 

Felly, ar hyn o bryd os ydych yn addurno eich hunain fel y llun yma, mynd yn ei flaen a phwynt ar ei gilydd, gyda Gabe yn pwyntio penodol ar rhif 9 i gynrychioli'r rhestr. OK, a rhif 34, eich llaw chwith ond dylid ei bwyntio at y llawr. 

Iawn, felly mae hwn yn rhestr cysylltiedig. Felly, mae hyn yn y senario dan sylw. Ac yn wir, mae hyn yn gynrychioliadol o ddosbarth o broblemau y gallai byddwch yn ceisio datrys â chod. Byddwch am mewnosod yn y pen draw elfen newydd i mewn i'r rhestr. Yn yr achos hwn, rydym yn mynd i ceisiwch osod y rhif 55. Ond mae mynd i fod achosion gwahanol i'w hystyried. Ac yn wir, mae hyn yn mynd i fod yn un o'r darlun mawr-fwyd parod yma, yw, beth yw'r gwahanol achosion. Beth yw'r gwahanol os bydd amodau neu canghennau y gallai eich rhaglen yn cael? 

Wel, mae nifer yr ydych yn ceisio ei mewnosoder, yr ydym yn gwybod yn awr i fod yn 55, ond os nad oeddech yn gwybod o flaen llaw, mae'n debygol iawn disgyn i o leiaf dri sefyllfaoedd posibl. Lle y gallai elfen newydd fod? CYNULLEIDFA: A'r pen neu'r canol. DAVID J. Malan: Ar y diwedd, yn y canol, neu ar y dechrau. Felly yr wyf yn honni mae o leiaf dair problem y mae angen i ddatrys. Gadewch i ddewis beth sy'n bosibl gellid dadlau y symlaf un, lle mae'r elfen newydd yn perthyn ar y dechrau. Felly dw i'n mynd i gael cod eithaf fel chwilio, yr wyf newydd ei ysgrifennu. Ac yr wyf i'n mynd i gael ptr, sy'n 'N annhymerus' yn cynrychioli yma gyda fy mys, fel arfer. 

A chofiwch, pa werth wnaethom ni ymgychwyn ptr i? Felly, rydym yn ymgychwyn iddo null lle cyntaf. Ond yna yr hyn a wnaethom ni ar ôl i ni Roedd y tu mewn i'n swyddogaeth chwilio? Rydym yn gosod ei bod yn hafal i yn gyntaf, nad yw'n golygu gwneud hyn. Os byddaf yn gosod ptr cyfartal i yn gyntaf, beth Dylai fy llaw mewn gwirionedd yn pwyntio at? Hawl. Felly os Gabe ac yr wyf yn mynd i fod gwerthoedd cyfartal yma, mae angen i ddau bwynt yn rhif 9. 

Felly, roedd hyn yn ddechrau ein stori. Ac yn awr mae hyn yn unig yw syml, er bod y gystrawen yn newydd. Gysyniadol dyma chwiliad llinol yn unig. Yw 55 sy'n hafal i 9? Neu yn hytrach, gadewch i ni ddweud yn llai na 9. Gan fy mod i'n ceisio chyfrif i maes ble i roi 55. Llai na 9, yn llai na 17, llai na 20, yn llai na 22, yn llai na 29, llai na 34, dim. Felly nawr rydym yn rhag ofn un o leiaf dri. 

Os ydw i eisiau i fewnosod 55 dros fan hyn, beth llinellau o angen cod i gael eu gweithredu? Sut mae llun hwn o Mae angen i bobl newid? Beth ddylwn i ei wneud gyda fy llaw chwith? Dylai hyn fod yn null y cychwyn, oherwydd fy mod ar ddiwedd y rhestr. A beth ddylai ddigwydd yma gyda Pedr, oedd hi? Yn amlwg mae'n mynd i dynnu sylw i mi. Felly yr wyf yn honni mae o leiaf dwy linell o god yn y cod sampl o heddiw mae hynny'n mynd i weithredu hyn senario o ychwanegu 55 yn y gynffon. A gallwn gael rhywun hop i fyny a dim ond yn cynrychioli 55? Mae pob hawl, chi yw'r 55 newydd. 

Felly nawr beth os yw'r nesaf senario yn dod ar hyd, ac rydym am mewnosoder ar y dechrau neu bennaeth rhestr hon? A beth yw eich enw, rhif 55? 

CYNULLEIDFA: Jack. 

DAVID J. Malan: Jack? OK, neis i gwrdd â chi. Croeso ar fwrdd. Felly nawr rydym yn mynd i mewnosoder, dyweder, mae'r rhif 5. Dyma yr ail achos yr tri rydym yn dod i fyny gyda blaen. Felly os 5 yn perthyn ar y dechrau, gadewch i ni weld sut yr ydym yn canfod bod allan. Rwy'n ymgychwyn fy ptr pwyntydd i rif 9 eto. Ac yr wyf yn sylweddoli, oh, 5 yn llai na 9. Felly atgyweiria y llun hwn ar ein rhan. Eu dwylo, Gabe neu Dewi or-- beth yw enw'r rhif 9 yn? 

CYNULLEIDFA: Jen. 

DAVID J. Malan: hands-- Jen yn pa rai o'n dwylo angen newid? Iawn, felly Gabe pwyntio at yr hyn nawr? Arnaf. Fi yw'r nod newydd. Felly, 'n annhymerus' jyst fath o symud yma i weld ei fod yn weledol. Ac yn y cyfamser beth ddylwn i dynnu sylw at hynny? Still lle dwi'n pwyntio. Felly dyna ni. Felly dim ond mewn gwirionedd un llinell o chyfyngderau cod y mater arbennig hwn, byddai'n ymddangos. Mae pob hawl, felly dyna dda. A gall rhywun fod yn dalfan ar gyfer 5? Dewch ar i fyny. Byddwn yn cael y tro nesaf i chi. 

Mae pob hawl, felly now-- a wrth fynd heibio, yr enwau Dydw i ddim yn gwneud cyfeiriad penodol at hawl yn awr, pwyntydd pred, pwyntydd rhagflaenydd a pwyntydd newydd, dyna dim ond yr enwau a roddir yn y cod sampl i'r awgrymiadau neu fy nwylo sydd wedi fath o bwyntio gwmpas. Beth yw eich enw? 

CYNULLEIDFA: Christine. 

DAVID J. Malan: Christine. Croeso ar fwrdd. Mae pob hawl, felly gadewch i ni ystyried nawr senario ychydig yn fwy blino, lle yr wyf am i fewnosod rhywbeth fel 26 i mewn i hyn. 20? Beth? Mae'r rhain yw-- beth da rydym wedi pen hwn. Mae pob hawl, 20. Pe gallai rhywun gael darn arall o papur yn barod, rhag achos-- pob hawl. O, diddorol. Wel mae hyn yn enghraifft o nam darlith. Iawn felly beth yw eich enw eto? CYNULLEIDFA: Julia. DAVID J. Malan: Julia, allwch chi pop allan ac yn esgus eich bod byth yno? OK, byth yn digwydd yma. Diolch yn fawr. Felly, mae'n debyg ein bod eisiau mewnosod Julia i mewn i'r rhestr gysylltiedig. Hi yw nifer 20. Ac wrth gwrs mae hi'n mynd i berthyn yn y begin-- nid ydynt yn pwyntio at unrhyw beth eto. Fel y gall eich llaw math o fod yn lawr null neu ryw werth garbage. Gadewch i ni ddweud y stori gyflym. Im 'yn pwyntio at rif 5 y tro hwn. Yna, yr wyf yn gwirio 9. Yna, yr wyf yn gwirio 17. Yna, yr wyf yn gwirio 22. Ac yr wyf yn sylweddoli, ooh, Julia Mae angen i fynd cyn 22. Felly beth sydd angen digwydd? Mae angen eu dwylo i newid? Julia, fy, or-- beth yw eich enw eto? 

CYNULLEIDFA: Cristnogol. 

DAVID J. Malan: Cristnogol neu? 

CYNULLEIDFA: Andy. 

DAVID J. Malan: Andy. Christian neu Andy? Mae angen Andy i bwynt ar? Julia. Mae pob hawl. Felly Andy, ydych chi eisiau i bwyntio at Julia? Ond arhoswch funud. Yn y stori hyd yn hyn, Fi yw'r math o un â gofal, yn yr ystyr bod pwyntydd yw'r peth sy'n symud drwy'r rhestr. Efallai gennym enw ar gyfer Andy, ond does dim o'r enw Andy newidyn. Yr unig newidyn arall gennym yw yn gyntaf, sydd wedi ei gynrychioli gan Gabe. 

Felly, mae hyn mewn gwirionedd pam felly yn hyn nid ydym wedi ei angen hwn. Ond yn awr ar y sgrin mae sôn eto o pwyntydd pred. Felly, gadewch i mi fod yn fwy eglur. Os yw hyn yn pwyntydd, gwell imi cael ychydig yn fwy deallus am fy iteriad. Os nad ydych yn meddwl fy mynd drwy fan hyn eto, gan dynnu sylw yma, pwyntio yma. Ond gadewch i mi fod â pwyntydd pred, pwyntydd rhagflaenydd, dyna math o pwyntio at y elfen Roeddwn yn unig yn. Felly, pan fyddaf yn mynd yma, yn awr fy diweddariadau llaw chwith. Pan fyddaf yn mynd fan hyn fy diweddariadau llaw chwith. Ac yn awr yr wyf wedi nid yn unig pwyntydd i yr elfen sy'n mynd ar ôl Julia, Yr wyf yn dal i gael pwyntydd i Andy, yr elfen o'r blaen. Felly, rydych yn cael mynediad, yn y bôn, briwsion bara, os mynnwch, i bob un o'r pwyntiau angenrheidiol. 

Felly, os ydw i'n pwyntio at Andy, a dwi hefyd bwyntio yn Cristnogol, y mae eu dwylo Dylech yn awr gael ei sylw at y ffaith yn rhywle arall? Felly Andy bellach yn gallu pwyntio at Julia. Gall Julia bellach yn pwyntio at Christian. Oherwydd y gall hi gopïo fy pwyntydd llaw dde yn. A bod yn effeithiol yn rhoi i chi yn ôl i'r lle hwn yma. Felly, yn fyr, er bod hyn yn cymryd i ni fath o am byth i ddiweddaru gwirionedd yn rhestr gysylltiedig, yn sylweddoli bod y gweithrediadau yn gymharol syml. Mae'n o un, dau, tri llinellau o god yn y pen draw. Ond lapio o amgylch y rhai llinellau o god yn ôl pob tebyg yn dipyn o resymeg sydd yn effeithiol gofyn y cwestiwn, ble rydym ni? A ydym ar y dechrau, y canol, neu y diwedd? 

Yn awr, mae yn sicr rhyw arall gweithrediadau gallem gweithredu. A lluniau hyn yma yn unig darlunio hyn yr ydym yn unig oedd â phobl. Beth am symud? Os ydw i eisiau, er enghraifft, gwared ar y rhif 34 neu 55, Efallai fy mod yn cael yr un math o god, ond dw i'n mynd i angen un neu ddau gam. Oherwydd beth sy'n newydd? Os byddaf yn symud rhywun ar y diwedd, fel rhif 55 ac yna 34, hyn sydd hefyd yn rhaid i hyn newid gan fy mod yn gwneud hynny? Mae'n rhaid i mi beidio evict-- beth yw eich enw eto? 

CYNULLEIDFA: Jack. 

DAVID J. Malan: Jack. Rhaid i nid yn unig evict-- Jack rhad ac am ddim i mi, felly yn llythrennol yn galw Jack rhad ac am ddim, neu o leiaf y pwyntydd yno hefyd, ond erbyn hyn beth sydd angen newid gyda Peter? Mae ei law yn well dechrau pwyntio i lawr. Oherwydd cyn gynted ag yr wyf ffoniwch am ddim ar Jack, os yw Pedr yn dal pwyntio at Jack ac felly yr wyf yn cadw croesi y rhestr a mynediad pwyntydd hwn, dyna pryd mae ein cyfaill hen segmentu Efallai fai mewn gwirionedd yn cicio i mewn. Oherwydd ein bod wedi cael y cof yn ôl i Jack. 

Gallwch aros yno lletchwith am ddim ond ennyd. Oherwydd ein bod wedi dim ond cwpl gweithrediadau terfynol i'w hystyried. Cael gwared ar y pennaeth y rhestr, neu'r beginning-- ac mae hyn yn un o ychydig yn blino. Oherwydd bod yn rhaid i gwybod bod Gabe yn fath o arbennig yn y rhaglen hon. Oherwydd yn wir, mae wedi ei pwyntydd hun. Dyw e ddim yn unig yn cael ei sylw at y ffaith yn, fel y mae bron pawb arall yma. 

Felly pan fydd y pennaeth y rhestr yn dileu, y mae eu dwylo angen newid nawr? Beth yw eich enw eto? 

CYNULLEIDFA: Christine. 

DAVID J. Malan: Rwy'n ofnadwy mewn enwau, yn ôl pob golwg. Felly, Christine a Gabe, y mae eu dwylo angen ei newid pan fyddwn yn ceisio cael gwared Christine, rhif 5, oddi wrth y llun? Iawn, felly gadewch i ni wneud Gabe. Gabe yn mynd i bwynt, yn ôl pob tebyg, yn rhif 9. Ond beth ddylai ddigwydd nesaf? CYNULLEIDFA: Christine dylai yn null [Anghlywadwy]. DAVID J. Malan: Iawn, dylem yn ôl pob tebyg make-- Clywais "null" rhywle. CYNULLEIDFA: Null ac yn rhydd iddi. DAVID J. Malan: nwl beth? CYNULLEIDFA: Null ac yn rhydd iddi. DAVID J. Malan: Null ac yn rhydd iddi. Felly, mae hyn yn hawdd iawn. Ac mae'n berffaith eich bod yn awr yn fath o sefyll yno, nad ydynt yn perthyn. Oherwydd eich bod wedi bod ddatgysylltu oddi ar y rhestr. Rydych chi wedi bod yn effeithiol amddifad o'r rhestr. Ac felly rydym yn well wedi ffoniwch am ddim yn awr ar Christine i roi'r cof ôl. Fel arall, bob tro yr ydym yn dileu nod o'r rhestr efallai y byddwn yn gwneud y rhestr byrrach, ond nid mewn gwirionedd yn gostwng maint yn y cof. Ac felly os ydym yn cadw adio a gan ychwanegu, gan ychwanegu pethau at y rhestr, Efallai fy cyfrifiadur yn cael arafach ac yn arafach ac yn arafach, oherwydd fy mod yn rhedeg allan o cof, hyd yn oed os nad wyf mewn gwirionedd yn ddefnyddio bytes Christine yn o gof anymore. 

Felly, yn y diwedd, mae eraill senarios, o dynnu course-- yn y canol, cael gwared ar y diwedd, fel y gwelsom. Ond y mwyaf diddorol her yn awr yw mynd i fod i ystyried yn union beth yw'r amser yn rhedeg yn. Felly, nid yn unig y gallwch chi gadw eich darnau o bapur, os, Gabe, Ni fyddech yn meddwl rhoi pawb pêl straen. Diolch yn fawr i'n rhestr cysylltiedig chi o wirfoddolwyr yma, os ydych yn gallu. 

[Cymeradwyaeth] 

DAVID J. Malan: pob hawl. Felly, ychydig o dadansoddol cwestiynau hynny, pe gallwn. Rydym wedi gweld nodiant hwn o'r blaen, O a omega mawr, arffiniau uchaf i nerth is ar y rhedeg amser o ryw algorithm. Felly, gadewch i ni ystyried yn unig un neu ddau o gwestiynau. 

Un, ac yr ydym yn dweud ei o'r blaen, beth yw'r rhedeg amser o chwilio am Rhestr o ran O mawr? Beth sydd uchaf yn rhwymo ar y gwaith o redeg amser o chwilio rhestr cysylltiedig fel y gweithredu gan ein gwirfoddolwyr yma? Mae'n O fawr o n, llinol. Oherwydd yn yr achos gwaethaf, yr elfen, fel 55, efallai y byddwn yn chwilio am y gallai fod lle Roedd Jack, yr holl ffordd ar y diwedd. Ac yn anffodus, yn wahanol arae ni allwn gael ffansi y tro hwn. Er bod pob un o'n pobl yn datrys o elfennau bach, 5, holl ffordd i fyny at yr elfen mwy, 55, mae hynny'n beth da fel arfer. Ond beth mae hynny'n dybiaeth bellach yn caniatáu i ni ei wneud? CYNULLEIDFA: [Anghlywadwy] DAVID J. Malan: Dweud eto? CYNULLEIDFA: Mynediad ar hap. DAVID J. Malan: mynediad ar hap. Ac yn ei dro mae hyn yn golygu y gallwn ni defnyddio zeros gwan, greddf yn hwy, a obviousness o ddefnyddio deuaidd chwilio a rhannu a gorchfygu. Oherwydd er ein Gallai pobl yn amlwg gweld a oedd Andy neu Christian yn fras yng nghanol y rhestr, byddwn ond yn gwybod bod fel cyfrifiadur drwy sgimio y rhestr o'r cychwyn cyntaf. Felly, rydym wedi rhoi'r gorau bod mynediad ar hap. 

O mor fawr o n nawr yw'r uchaf rhwymo ar ein hamser chwilio. Beth am omega ein chwiliad? Beth yw'r isaf rhwymo ar chwilio am ryw nifer yn y rhestr hon? CYNULLEIDFA: [Anghlywadwy] DAVID J. Malan: Dweud eto? CYNULLEIDFA: Un. DAVID J. Malan: Un. Amser mor gyson. Yn yr achos gorau, Christine yn yn wir, ar ddechrau'r y rhestr. Ac rydym yn chwilio am rhif 5, felly rydym yn dod o hyd iddi. Felly nid oes llawer mawr. Ond mae hi 'got i fod yn yr gan ddechrau o'r rhestr yn yr achos hwn. Beth am rywbeth fel Dileu? Beth os ydych chi am ddileu elfen? Beth sydd uchaf y rhwymo ac isaf rhwymo ar ddileu rhywbeth o cysylltiedig rhestru? CYNULLEIDFA: [Anghlywadwy] DAVID J. Malan: Dweud eto? CYNULLEIDFA: n. DAVID J. Malan: n yn yn wir y uchaf rhwymo. Oherwydd yn yr achos gwaethaf rydym yn ceisio i ddileu Jack, fel rydym yn unig oedd. Mae'n holl ffordd ar y diwedd. Cymryd ni am byth, neu n camau i ddod o hyd iddo. Felly dyna uchaf yn rhwymo. Dyna llinol, yn sicr. A bod yr achos gorau yn rhedeg amser, neu y terfynau is yn yr achos gorau fyddai amser yn gyson. Oherwydd efallai rydym yn ceisio dileu Christine, ac rydym yn unig yn cael lwcus hi ar y dechrau. Nawr arhoswch funud. Gabe Roedd hefyd ar y dechrau, ac roedd gennym hefyd i ddiweddaru Gabe. Felly nid oedd mai dim ond un cam. Felly a yw'n wir gyson amser, yn yr achos gorau, i gael gwared ar yr elfen lleiaf? Y mae, hyd yn oed er y gallai fod yn ddau, tri, neu hyd yn oed 100 o linellau o god, os yw'n yr un nifer o llinellau, nid mewn rhyw dolen, ac yn annibynnol o faint o'r rhestr, yn hollol. Dileu yr elfen yn ddechrau'r rhestr, hyd yn oed os oes rhaid inni ddelio â Gabe, yn dal i fod amser yn gyson. 

Felly, mae hyn yn ymddangos fel gam enfawr yn ôl. A beth yn wastraff amser os, mewn un wythnos a'r wythnos sero oedd gennym, nid yn unig cod pseudocode ond cod gwirioneddol i weithredu rhywbeth sy'n log sylfaen n, neu log, yn hytrach, o n, sylfaen 2, o ran ei amser rhedeg. Felly, pam y byddai'r heck ydym am ddechrau defnyddio rhywbeth fel rhestr cysylltiedig? Yeah. 

CYNULLEIDFA: Felly, gallwch ychwanegu elfen i'r casgliad. DAVID J. Malan: Felly, gallwch ychwanegu elfennau at y rhesi. Ac mae hyn hefyd yn thematig. A byddwn yn parhau i weld hyn, mae hyn yn fasnach-off, llawer fel rydym wedi gweld cyfaddawd gyda'r math uno. Gallem mewn gwirionedd gyflymu'r chwilio neu'n didoli, yn hytrach, os byddwn yn gwario ychydig yn fwy o ofod a cael darn ychwanegol o cof neu arae ar gyfer math uno. Ond rydym yn gwario mwy gofod, ond yr ydym yn arbed amser. Yn yr achos hwn, rydym yn rhoi'r gorau i amser, ond rydym yn cael hyblygrwydd, ddynamiaeth os mynnwch, sydd yn dadlau yn nodwedd gadarnhaol. 

Rydym ni hefyd yn gwario gofod. Ym mha ystyr yw cysylltu rhestru yn ddrutach yn nhermau gofod na'r arae? Ble mae'r lle ychwanegol yn dod o? Yeah? 

CYNULLEIDFA: [Anghlywadwy] pwyntydd. 

DAVID J. Malan: Yeah, rydym yn hefyd yn cael y pwyntydd. Felly mae hyn yn minorly blino yn nad yw bellach mod Yr wyf yn storio unig int i gynrychioli int. Im 'yn storio yn int ac mae pwyntydd, sydd hefyd yn 32 ddarnau. Felly dw i'n llythrennol dyblu faint o le dan sylw. Felly dyna cyfaddawd, ond dyna yn achos int. Tybiwch nad ydych yn storio int, ond mae'n debyg pob un o'r petryalau hyn neu bob un o'r bobl hyn yn cynrychioli gair, gair Saesneg sy'n allai fod pum cymeriad, 10 cymeriadau, efallai hyd yn oed yn fwy. Yna, dim ond 32 gan ychwanegu mwy o darnau Gallai fod yn llai o dipyn o beth. 

Beth os bydd pob un o'r myfyrwyr yn yn yr arddangosiad Roedd yn llythrennol structs fyfyrwyr sy'n enwau a thai ac efallai rhifau ffôn a Twitter ymdrin ac yn y blaen. Felly yr holl o'r meysydd rydym yn dechrau siarad am y diwrnod o'r blaen, llawer llai o llawer fawr fel ein nodau yn cael mwy diddorol a mawr i wario, eh, yn ychwanegol bwyntydd dim ond er mwyn eu cysylltu â'i gilydd. Ond yn wir, mae'n cyfaddawd. Ac yn wir, mae'r cod yn mwy cymhleth, fel y wnewch chi helpu gweld drwy sgimio drwy yr enghraifft benodol. Ond beth os oedd rhywfaint greal sanctaidd yma. Beth os nad ydym yn cymryd cam tuag yn ôl, ond yn gam enfawr ymlaen a gweithredu data strwythur trwy yr ydym yn Gellir dod o hyd i elfennau megis Jack neu Christine neu unrhyw elfennau eraill yn y casgliad hwn mewn gwir amser yn gyson? Chwilio yn gyson. Dileu yn gyson. Mewnosod yn gyson. Mae pob un o'r gweithrediadau hyn yn gyson. Byddai hynny'n ein greal sanctaidd. A dyna lle'r ydym yn Bydd codi tro nesaf. Welwn ni chi wedyn.