DAVID Malan: Pob hawl. Croeso yn ôl i CS50. Mae hyn yn dechrau'r wythnos 8. A dwyn i gof bod problem set 5 a ddaeth i ben gydag ychydig o her. Felly, gan dybio eich bod adennill eich holl Cymrodyr addysgu a ffotograffau CA yn yn y ffeil card.raw, rydych yn gymwys yn hyn ddod o hyd pob un o'r bobl hynny, a Bydd un enillydd lwcus cerdded adref gydag un o'r pethau hyn, y cynnig naid ddyfais y gallwch eu defnyddio ar gyfer derfynol prosiectau, er enghraifft. 

Mae hyn, bob blwyddyn, yn arwain at ychydig o creepiness. Ac felly yr hyn yr wyf yn meddwl y byddwn i'n ei wneud yw rhannu gyda chi rai o'r nodiadau sydd wedi mynd yn ôl ac ymlaen dros y rhestr staff yn ddiweddar. Er enghraifft, dim ond neithiwr, dyfyniad unquote, gan un o'r staff aelodau, "Rwyf newydd gael cnoc fyfyrwyr ar fy drws i gymryd llun gyda mi. Llech, yr wyf yn dweud wrthych. "Wedi ei eithaf disgrifiadol ac yna rydym yn symud ymlaen i, awr neu ddwy yn ddiweddarach, "Roedd gen i myfyriwr yn aros i mi ar ôl adran ac yr oedd ganddo ein holl enwau a lluniau ar rai dalennau o bapur. "Mae pob hawl. Felly, trefnu, ond nid bob un sy'n creepy eto. 

Yna, "Roeddwn yn tu allan i'r dref dros y penwythnos, a pan fyddaf yn mynd yn ôl, roedd un o bob fy ystafell wely. "[Chwerthin] DAVID Malan: dyfyniad nesaf o staff aelod, "Daeth myfyriwr i fy ty yn Somerville am 04:00 y bore. "Next staff, "Cefais i fy gwesty yn San Francisco a myfyriwr yn aros am mi yn y cyntedd gyda thri DSLRs. " Math o camera. "Dydw i ddim hyd yn oed ar staff semester hwn, ond torrodd yn fyfyriwr yn fy nhŷ hwn bore a chofnodi yr holl beth gyda Google Glass. "Ac yna yn olaf, "O leiaf 12 o bobl yn eiddgar disgwyl i mi pan fyddaf yn mynd allan o fy limo, ac yna yr ddeffro. "Mae pob hawl. Felly, ymysg y lluniau, fel y gall galw i gof, yn cyd-hyn yma, pwy ydych chi Gallai gwybod fel Milo Banana, sy'n byw gyda Lauren Carvalho, ein prif Cymrawd addysgu. Milo, Milo, dod yma bachgen. Milo. Milo. Cofiwch chi, mae'n gwisgo Google Glass, felly byddwn yn dangos i chi hyn i gyd ar ôl. Felly, mae hyn yn Milo os hoffech chi dynnu llun gydag ef wedyn. Os hoffech chi i chwilio at y gynulleidfa yno. OK. Dyna ffilm da. Wel, Milo Banana. O, peidiwch â gwneud hynny. 

[Chwerthin] 

OK. Felly gair ac yna ar yr hyn sydd o'n blaenau, oherwydd wrth i ni ddechrau pontio, yr wythnos hon yn benodol, o C mewn amgylchedd llinell gorchymyn i PHP a JavaScript a SQL ac HTML a CSS mewn amgylchedd ar y we, byddwn yn eich arfogi â'r holl mwy o wybodaeth ar gyfer prosiectau terfynol posibl. Toward perwyl hwnnw, mae'r cwrs yn traddodiad o gynnal seminarau a ar bynciau ymylol i'r cwrs. Llawer iawn yn ymwneud â rhaglenni ac i datblygu app ac yn y blaen, ond Nid yw o reidrwydd harchwilio gan maes llafur y cwrs ei hun. 

Felly, os y gallech fod â diddordeb mewn un neu fwy o'r seminarau eleni, gofrestru yn cs50.net/seminar. Mae seminarau hŷn ar cs50.net/seminars. Ac ar y rhestr hyd yn hyn ar gyfer y flwyddyn yn Apps We Amazing gyda Ruby ar Rails, a wneir yn lle'r iaith PHP. Ieithyddiaeth Chyfrifiadurol. Cyflwyniad i iOS, sef y lwyfan sy'n cael ei ddefnyddio ar gyfer iPhone a datblygiad iPad. JavaScript ar gyfer Apps We, byddwn yn ymdrin hynny, ond yn y seminar hwn, byddwch yn mynd rhoi mwy o fanylion. 

Naid Motion, felly byddwn mewn gwirionedd yn cael rhywfaint o o'n ffrindiau o Gynnig Leap, y cwmni ei hun, ymuno â ni. Yfory, mewn gwirionedd, er mwyn darparu yn ymarferol seminar, os o ddiddordeb i chi. Meteor.js, techneg arall ar gyfer defnyddio JavaScript nid mewn porwr, ond ar weinydd. Node.js, sydd yn fawr iawn yn yr un modd hefyd. 'N llyfn Android Design. Android fod yn amgen poblogaidd iawn i iOS a Ffenestri Ffôn a llwyfannau symudol eraill. Ac Web Diogelwch Defense Active. 

Felly, mewn gwirionedd, os hoffech i gymryd rhan yn hyn, gadewch i mi gwneud nodyn o hyn. Rydym yn hapus iawn i ddweud bod ein ffrindiau yn Leap Motion, sydd yn startup - ddyfais hon mewn gwirionedd dim ond daeth allan ychydig fisoedd yn ôl - wedi rhoi 30 ddyfeisiadau o'r fath rasol i'r dosbarth am gymaint o lawer o fyfyrwyr, os hoffech chi fenthyg y caledwedd tua diwedd semester a'i ddefnyddio ar gyfer prosiect terfynol gwirioneddol. Maent yn cefnogi nifer o ieithoedd. Nid oedd yr un ohonynt C, nid oes yr un ohonynt PHP, felly gwireddu un neu fwy o'r seminarau hyn gallai fod o ddiddordeb. A bydd pob un ohonynt yn cael ei ffilmio yn Os nad ydych yn gallu i fod yn bresennol yn bersonol. Mae'r amserlen yn cael eu cyhoeddi drwy e-bost wrth i ni galedu ystafelloedd. 

Ac yn olaf, os ydych yn mynd i projects.cs.50.net, mae hwn yn wefan rydym yn cynnal bob blwyddyn yr ydym yn gwahodd Folks o'r gymuned, cyfadran, adrannau, staff, ac mae'r ddau mewn y tu allan i CS50 i cynnig syniadau ar gyfer prosiectau. Pethau sydd o ddiddordeb i grwpiau myfyrwyr. Pethau sydd o ddiddordeb i adrannau. Felly, yn troi yno os ydych yn cael trafferth gydag ansicrwydd o ran yr hyn yr ydych Byddai eich hun yn hoffi i fynd i'r afael. 

Felly, y tro diwethaf a gyflwynwyd gennym yn dadlau strwythur data mwy cymhleth nag y byddem welwyd yn ystod yr wythnosau diwethaf. Roedden ni wedi bod yn defnyddio araeau 'n bert hapus yn ddefnyddiol os strwythur data syml. Yna rydym yn cyflwyno hyn, sy'n wrth gwrs, yn gysylltiedig rhestrau. A beth oedd yn un o'r cymhellion ar gyfer gyflwyno'r strwythur data? Yeah? Beth sy'n bod? 

GYNULLEIDFA: faint Dynamic. 

DAVID Malan: faint Dynamic. Felly, tra yn amrywiaeth, rhaid i chi gwybod beth yw ei faint ymlaen llaw pan byddwch yn dyrannu ei. Yn restr cysylltiedig, nad ydych yn rhaid i chi wybod hynny. Gallwch dim ond malloc, neu'n fwy cyffredinol, dyrannu ychwanegol nod, fel petai, unrhyw tro y byddwch yn eisiau i fewnosod mwy o ddata. Ac nod ddim wedi bennwyd ymlaen llaw ystyr. Dim ond yn derm generig sy'n disgrifio rhyw fath o gynhwysydd ein bod ni'n defnyddio yn ein strwythur data i storio rhywfaint o eitem o ddiddordeb, sydd yn yr achos yn digwydd bod yn cyfanrifau. 

Ond mae tradeoff bob amser. Felly, rydym yn cael meintiau deinamig y data strwythur, ond yr hyn y pris yr ydym yn talu? Beth yw'r anfanteision o restrau cysylltiedig? Yeah? 

GYNULLEIDFA: Angen mwy o gof. 

DAVID Malan: Mae angen mwy o cof, sut yn union? 

GYNULLEIDFA: [Anghlywadwy]. 

DAVID Malan: Yn union. Felly, erbyn hyn rydym wedi awgrymiadau cymryd cof ychwanegol gennym yn flaenorol nad oedd angen, gan fod y fantais o fyrdd, wrth gwrs, yw bod popeth yn cydgyffwrdd, yn ôl wrth gefn wrth gefn, sy'n yn rhoi mynediad ar hap i chi. Oherwydd dim ond drwy ddefnyddio braced sgwâr nodiant, neu yn fwy technegol pwyntydd rhifyddeg, adio syml iawn, gallwch gael mynediad i unrhyw elfennau mewn amser cyson. Ac yn wir, dyna fath o hinting ar pris arall yr ydym yn talu gyda restr cysylltiedig. 

Beth fydd yn digwydd i'r amser yn rhedeg o rhywbeth fel Chwilio, os wyf am ddod o hyd i werth ac y tu mewn o restr cysylltiedig? Beth mae fy amser yn rhedeg dod? O Big n. Os caiff ei datrys i? Beth os yw'r strwythur data ei datrys? A allaf wneud yn well na mawr O n ar gyfer chwilio? Na, oherwydd yn yr achos gwaethaf y gallai yn dda iawn eu datrys, ond mae nifer ydych yn chwilio am a allai fod yn fawr. Gallai fod yn y rhif 100, sy'n allai ddigwydd i fod yn holl y ffordd ar y diwedd. Ac oherwydd gallwch gael mynediad at cysylltiedig rhestr yn y gweithredu gan y ffordd ei nod cyntaf, rydych yn yn dal math o allan o lwc. Mae'n rhaid i chi deithio ar draws yr holl beth o gyntaf i bara er mwyn dod o hyd i bod gwerth mawr fel 100. Neu i benderfynu os yw'n Nid yw hyd yn oed yno. 

Felly, ni allwn wneud yr hyn algorithm mewn data strwythur sy'n edrych fel hyn? Ni allwn wneud chwiliad deuaidd, oherwydd chwiliad deuaidd ofynnol ein bod wedi mynediad ar hap. Gallai Rydym yn unig neidio o leoliad i leoliad heb orfod dilyn hyn briwsion bara yn y ffurflen yr holl awgrymiadau hyn. 

Nawr, sut oedd yn gweithredu'r hyn? Wel, os ydym yn mynd i'r sgrin yma, os gallwn reimplement data hyn yn gyflym Strwythur - Nid yw fy llawysgrifen i gyd y gwych yma, ond byddwn yn ceisio. Strwythur Felly typedef, a'r hyn a wnes i eisiau i alw y peth hyn i fyny yma? Nôd. Felly, byddaf yn cael i ni ddechrau. Ac yn awr, beth sydd angen i fod tu mewn strwythur y data ar gyfer y unigol restr cysylltiedig? Faint o feysydd? 

Felly ddau. Mae un yn eithaf hawdd. Felly int n. A gallai rydym yn galw n unrhyw beth yr ydym am ei gael, ond dylai fod yn int os ydym yn gweithredu cysylltiedig ar gyfer rhestr ints. Ac yn awr beth mae'r ail rhaid i maes i fod? Strwythur nod *. Felly, os wyf yn gwneud strwythur nod *, ac yna yr Gellir galw hyn hefyd yn beth bynnag rwyf eisiau, ond dim ond i fod yn glir 'n annhymerus' galw yn nesaf, fel yr ydym wedi bod yn ei wneud. Ac yna bydd cau fy braces cyrliog I. 

Ac yn awr, fel y tro diwethaf, Yr wyf yn rhoi nod i lawr yma. Ond os wyf yn datgan hyn fel nod, pam wnes i drafferthu fod mor verbose yma yn datgan strwythur nod * nesaf, yn hytrach na i ddim ond nod * nesaf? Yeah? 

GYNULLEIDFA: [Anghlywadwy]. 

DAVID Malan: Yn union. Yn union. Oherwydd C wir yn mynd â chi yn llythrennol ac yn Dim ond yn gweld y diffiniad o nod ffordd i lawr yma, ni allwch cyfeirio at i fyny yma. Felly, rydym yn cael y math hwn o preemptive datganiad yma, sydd yn cyfaddef mwy verbose. Strwythur nod, mae hynny'n golygu gallwn yn awr gael mynediad iddo tu mewn i'r strwythur data. 

Ac wrth fynd heibio, gan fod hyn yn dod yn ychydig yn fwy goddrychol yn awr, Gall y seren dechnegol fynd yma, gall fynd fan hyn, gall hyd yn oed fynd yn y canol. Rydym wedi mabwysiadu, yn y canllaw arddull ar gyfer y cwrs, y confensiwn o roi y seren dde nesaf at y data math, sydd, yn yr achos hwn, fyddai strwythur nod. Ond yn sylweddoli mewn llawer o werslyfrau a cyfeiriadau ar-lein, byddwch efallai yn wir weld ar yr ochr arall. Ond dim ond yn sylweddoli y bydd y ddau mewn gwirionedd gweithio a dylech yn syml fod gyson. 

Mae pob hawl. Felly dyna oedd ein datganiad o strwythur nod. Ond yna rydym yn dechrau gwneud mwy pethau soffistigedig. Er enghraifft, rydym yn penderfynu cyflwyno rhywbeth fel tabl hash. Felly dyma mae tabl hash o faint n, mynegeio o 0 ar y top chwith i'r n minws 1 ar y gwaelod ar y chwith. Gallai hyn fod yn hash bwrdd ar gyfer unrhyw beth. Ond pa fathau o bethau y gwnaethom siarad am ddefnyddio tabl hash amdano? Storio beth? 

Enwau. Gallem wneud enwau fel rydym yn gwneud y tro diwethaf. Ac yn wir, gallwch storio unrhyw beth. A byddwn yn gweld hyn eto yn PHP a JavaScript. Mae tabl hash yn fath o 'n glws Swistir Cyllell fyddin sy'n eich galluogi i storio 'n bert lawer beth bynnag yr ydych ei eisiau tu mewn iddo gan gysylltu allweddi gyda gwerthoedd. Allweddi â gwerthoedd. 

Nawr yn yr achos syml, mae ein allweddi rhifau yn unig. Rydym yn gweithredu hash bwrdd fel arae. Ac felly yr allweddi yn 0, 1, 2, ac yn y blaen. Ac felly yr ydym ni, fel bodau dynol, penderfynodd ddiwethaf eich wythnos bod yn gwybod beth, os ydym yn mynd i enwau storio, gadewch i ni yn unig fympwyol, ond 'n bert yn rhesymol, cymryd yn ganiataol bod Alice, A enw, fydd yn unig yn cael ei fynegeio i 0. A bydd Bob, enw B, yn cael ei fynegeio yn 1, ac yn y blaen. Felly cawsom mapio rhwng mewnbynnau, sydd yn llinynnau, ac mae'r hash lleoliadau, sef rhifau. 

Felly, y broses sy'n cael ei adnabod yn gyffredinol fel swyddogaeth hash, a gallwch wirioneddol gweithredu mewn cod. Os wyf yn awyddus i weithredu swyddogaeth hash sy'n gwneud yn union yr hyn yr ydym a ddisgrifir yn unig o tro diwethaf, efallai y byddaf datgan swyddogaeth sy'n digwydd, fel y mewnbwn er enghraifft - a gadewch i ni wneud hyn ar hyn sgrin dros yma. Os wyf yn awyddus i weithredu hash swyddogaeth, efallai y byddwn yn dweud rhywbeth fel hyn. 

Mae'n mynd i ddychwelyd int. Mae'n mynd i gael ei alw hash, ac mae'n mynd i dderbyn fel dadl yn llinyn, neu gallwn fod yn fwy priodol yn awr, a dweud torgoch *, byddwn yn ei alw'n s. Ac yna yr holl swyddogaeth hon wedi ei wneud, yn y pen draw, yn cael ei dychwelyd int. Nawr, sut y mae'n ei wneud a allai â bod mor glir. Rydw i'n mynd i roi hyn ar waith heb unrhyw fath o gamgymeriad gwirio ar hyn o bryd. Im 'jyst yn mynd i ddweud ddall, yn dychwelyd beth bynnag sydd yn s braced 0, minws, gadewch i ni ddweud, cyfalaf A colon. 

Torri yn llwyr. Dyw hi ddim yn berffaith, oherwydd un, beth os yw null? Pethau drwg yn mynd i ddigwydd. Dau, beth os y llythyr cyntaf yn y Nid enw yw llythyr cyfalaf? Dyw hynny ddim yn mynd i droi allan yn dda naill ai. Gallai fod yn llythyr llythrennau bach neu beidio llythyr o gwbl. Felly gwbl lle i wella yma, ond mae hyn yn syniad sylfaenol. 

Beth rydym yn disgrifio yr wythnos diwethaf ar lafar fel dim ond proses o fapio Alice i Gall 0 a Bob i 1 gael eu mynegi yn sicr yn fwy formulaically fel C gweithredu yma. A elwir eto hash, yn cymryd llinyn fel mewnbwn, ac yna rhywsut yn gwneud rhywbeth gyda'r mewnbwn i gynhyrchu allbwn. Nid annhebyg ein disgrifiad blwch du ein bod wedi ei wneud o hyd. Nid wyf yn gwybod sut y gallai hyn fod yn gweithio o dan y cwfl. 

Ar gyfer problem set 6, un o'r heriau Chi sydd i benderfynu beth Bydd eich swyddogaeth hash fod? Beth sy'n mynd i fod yn y tu mewn y du bocs, ac yn ôl pob tebyg, mae'n bydd yn ychydig yn fwy diddorol na hyn, a bendant yn fwy agored i gamgymeriadau gwirio na hyn penodol gweithredu. 

Ond gall problemau godi, dde? Os oes gennym strwythur data fel hyn un, beth un o'r problemau gallwch rhedeg i mewn dros gyfnod o amser wrth i chi fewnosod mwy a mwy o enwau i mewn i'r tabl hash? Byddwch yn cael gwrthdrawiadau, dde? Beth os oes gennych Alice ac Aaron, dau o bobl y mae eu henwau yn digwydd i ddechrau gyda A? Mae hynny'n codi'r cwestiwn, lle rydych yn rhoi'r ail fath Mae enw? 

Wel, efallai y byddwch yn ddiniwed yn unig ei roi lle mae Bob yn perthyn, ond yna Bob yn math o sgriwio os ydych yn ceisio rhowch ei enw nesaf ac does dim lle ar ei gyfer. Felly efallai y byddwch yn rhoi Bob lle Charlie yw, a gallwch ddychmygu hyn yn gyflym iawn datganoli i mewn i dipyn o lanast. Rhywbeth llinol yn y diwedd, lle rydych yn yn rhaid i chwilio'r holl beth chwilio am Alice neu Bob neu Aaron neu Charlie. 

Felly, yn lle hynny rydym yn cynnig, yn hytrach na dim ond llinol holi am fannau agored a plopping enwau yno, rydym yn cynnig dull ffansi. Mae tabl hash gweithredu'n dal i fod gyda amrywiaeth o fynegeion, ond y math data o mynegeion hynny yn awr yn awgrymiadau. Awgrymiadau ar gyfer beth? Pointers i restrau cysylltiedig. 

Gan fod galw i gof bod rhestr cysylltiedig yn gwirionedd dim ond pwyntydd i nod, a y nod Mae cae nesaf, a bod y nod Mae cae nesaf, ac yn y blaen. Felly, gallwch yn awr feddwl am amrywiaeth hwn ar yr ochr chwith tabl hash fel gan arwain at restr cysylltiedig. Y fantais o'r rhain yw os ydych yn cael gwrthdrawiad rhwng Alice ac Aaron, beth ydych chi'n ei wneud gyda'r ail berson o'r fath? Rydych yn unig atodi iddo ef neu hi i'r ben, neu hyd yn oed y dechrau ar y rhestr honno cysylltiedig. 

Ac mewn gwirionedd, dim ond gadewch i nwdls drwy hynny am ddim ond eiliad. Lle fyddai'n gwneud yr ystyr mwyaf? Os byddaf yn gosod Alice ac mae hi'n dod i ben i fyny ar y lleoliad cyntaf, yna yr wyf yn ceisio nodwch enw Aaron, ac mae amlwg yn gwrthdrawiad, dylwn i roi ef ar y dechrau y rhestr cysylltiedig? Dyna yn y lleoliad hwnnw yn gyntaf, neu ar y diwedd? 

GYNULLEIDFA: [Anghlywadwy]. 

DAVID Malan: OK. Clywais dechrau. Pam ar y dechrau? 

GYNULLEIDFA: [Anghlywadwy]. 

DAVID Malan: OK. Mae'n wyddor, felly dyna 'n glws. Dyna eiddo da. Bydd yn arbed amser o bosibl i mi. Ni fydd yn gadael i mi wneud chwiliad deuaidd, ond yr wyf yn gallai o leiaf fod yn gallu torri allan o dolen os wyf yn sylweddoli, yn dda, rwy'n ffordd Byddai gorffennol yn Aaron fod yn y datrys rhestr gysylltiedig. Nid oes yn rhaid i mi gwastraffu fy amser yn edrych yr holl ffordd at y diwedd. Felly, mae hynny'n rhesymol. Pam arall efallai y byddwch am i fewnosod yr enw gwrthdaro yn y ddechrau y rhestr? Beth sy'n bod? 

GYNULLEIDFA: [Anghlywadwy]. 

DAVID Malan: Gallai gymryd amser hir i gyrraedd y diwedd y rhestr. Ac yn wir, yn hirach ac yn hirach. Mae mwy o enwau i chi fewnosod y dechrau gyda A, po hwyaf y bydd gadwyn yn mynd i gael. Po hiraf a oedd yn cysylltu rhestr yn mynd i gael. Felly, rydych yn wirioneddol yn unig gwastraffu eich amser. Efallai eich bod yn well eich byd cynnal amser gosod yn gyson, mawr O o 1, gan bob amser roi'r enw gwrthdaro yn ddechrau'r rhestr cysylltiedig, ac nid yn poeni cymaint am didoli. 

Beth yw'r ateb gorau? Mae'n aneglur. Mae'n fath o yn dibynnu ar yr hyn y mae'r dosbarthiad yw, beth yw'r patrwm o'r enwau rydych yn mewnosod. Dyw hi ddim o reidrwydd yn ateb amlwg. Ond yma, unwaith eto, yn cyfle dylunio. 

Felly, byddwn wedyn yn edrych ar y peth hyn, a mewn gwirionedd y cyfle mawr eraill ar gyfer p-set 6. Ac yn sylweddoli, os nad ydych wedi gwneud hynny'n barod, Zamyla deifio i ddau o'r rhain, hash tablau a chais, yn fwy manwl. Ac mae'r walkthrough fideo gwreiddio yn p-set fanyleb. Roedd hyn yn trie - T-R-I-E. A beth oedd yn ddiddorol am hyn oedd bod yr amser yn rhedeg o chwilio am enw, fel Maxwell y tro diwethaf, roedd mawr O o beth? Beth sy'n bod? 

GYNULLEIDFA: Mae nifer o lythyrau. 

DAVID Malan: Nifer y llythyrau. Clywais ddau beth. Nifer o lythyrau ac amser cyson. Felly, gadewch i ni fynd â hynny yn gyntaf. Mae nifer o lythyrau. Wel, y strwythur data, galw i gof, yn fel coeden, coeden deulu, pob un y mae eu nodau wedi eu gwneud o araeau. A rhesi hynny yn arwydd o nodau eraill o'r fath, neu unrhyw eraill araeau yn y goeden. 

Felly, os oeddem am benderfynu wedyn boed Maxwell yn i mewn yma, efallai y byddwn yn mynd at y casgliad cyntaf, ar frig y y goeden, y gwraidd fel y'i gelwir, ben y trie, ac yna dilyn y m pwyntydd, yna bydd y pwyntydd yn, yna x, w, e, l, l. Ac yna pan fyddaf yn gweld rhai symbol arbennig, dynodi yma fel triongl. Mewn cod fe welwch rydym yn cynnig eich bod gweithredu fel bool, dim ond dweud ie neu ddim, gair yn dod i ben yma. 

Wel, unwaith y byddwn wedi mynd i M-A-X-W-E-L-L, teimlo fel saith, efallai wyth os ydym yn mynd un heibio iddo, wyth camau i ddod o hyd i Maxwell. Neu beth am alw K. Ond cofio ddiwethaf amser, yr wyf yn dadlau, os oes realistig o hyd ar y mwyaf ar gair, fel cymeriadau 40-rhai-od, a uchafswm hyd awgrymu gwerth cyson. Felly mewn gwirionedd, ie, 'i' O dechnegol fawr o 8 neu 7, neu O fawr iawn o K. Ond os oes cap cyfyngedig ar yr hyn Gallai K fod, mae'n gyson. Ac felly mae'n fawr O 1 yn ar ddiwedd y dydd. 

Nid yn y byd go iawn. Nid pan fyddwch mewn gwirionedd yn dechrau gwylio eich cloc yn rhedeg eich rhaglen. Mae'n gwbl yn mynd i fod ychydig yn arafach nag wirioneddol gyson amser gydag un cam. Mae'n mynd i fod yn saith neu wyth cam, ond yn dal i fod yn llawer, llawer gwell na algorithm fel mawr O n bod yn dibynnu ar faint yr hyn sydd yn y strwythur data. 

Sylwch ar y upside yma yw y gallwn osod miliwn mwy o enwau i mewn i hyn strwythur data, ond faint yn fwy o gamau mae'n mynd i fynd â ni i ddod o hyd i Maxwell yn yr achos? Dim. Mae'n effeithio. A hyd yma, nid wyf yn credu ein bod wedi gweld enghraifft o strwythur data neu algorithm a oedd yn gwbl heffeithio gan allanol ymddygiadau fel 'na. Ond ni all hyn fod yn anhygoel. Ni all hyn fod yr unig ateb ar gyfer y p-set 

Ac nid yw'n. Nid yw hyn o reidrwydd y data strwythur dylech tueddu i, oherwydd fel tablau hash, tradeoff. Beth yw'r pris a dalwch yma? Cof. Yr wyf yn golygu, mae hyn yn erchyll faint o gof. Ac ni allwch eithaf ei weld yma oherwydd awdur y darlun hwn amlwg cwtogi holl arrays, ac nid ydym yn gweld llawer o A a B a C a Q ac Y. a Z yn araeau hyn. Ond maen nhw yno. 

Mae pob un o'r nodau hyn yw amrywiaeth cyfan o ryw 26 neu fwy o bytes, pob un sy'n cynrychioli llythyr. 27 yn ein hachos ni, fel y gallwn gefnogi collnod yn y broblem a osodwyd. Felly, y strwythur data yn wirioneddol, iawn trwchus a llydan. Ac y gallai ei ben ei hun yn y pen draw arafu pethau i lawr, neu o leiaf gostio i chi llawer mwy o le. Ond unwaith eto, gallwn dynnu cymariaethau yma. 

Dwyn i gof ychydig yn ôl, rydym yn cyflawni llawer amser yn rhedeg yn fwy cyffrous i ddatrys pan fyddwn yn defnyddio uno fath, ond mae'r pris rydym yn talu i gyflawni n mewngofnodi n ar gyfer uno math sy'n ofynnol ein bod yn gwario mwy pa adnoddau? Mwy o le. Rydym angen amrywiaeth uwchradd i copïo pobl i mewn, yn union fel wnaethom yma ar y llwyfan. Felly, unwaith eto, nid oes unrhyw enillwyr clir, ond dim ond dylunio goddrychol i benderfyniadau gael eu gwneud. 

Mae pob hawl. Felly beth am hyn? Gall unrhyw un adnabod pa D-Hall? OK. Felly tri ohonom yn ei wneud. Mather House. Felly mae hyn yn ar gyfer bwyta Mather yn. 'N annhymerus' bet holl neuaddau bwyta wedi pentyrrau o hambyrddau fel hyn. Ac mae hyn mewn gwirionedd yn cynrychioli o rywbeth rydym wedi yn amlwg yn gweld yn barod. Byddem ni'n ei alw yn llythrennol pentwr. Ac y simnai, o ran eich cof cyfrifiadur, yw lle mae data yn mynd tra bod swyddogaethau yn cael eu galw. 

Er enghraifft, pa fathau o bethau yn mynd ar y pentwr o ran y cynllun cof rydym wedi trafod yn yr wythnosau diwethaf? Beth sy'n bod? 

GYNULLEIDFA: galwadau i swyddogaethau. 

DAVID Malan: Mae'n ddrwg gen i. 

GYNULLEIDFA: galwadau i swyddogaethau. 

DAVID Malan: galwadau i swyddogaethau, ond yn benodol, beth sydd y tu mewn o bob un o'r fframiau hynny? Pa fath o bethau? Yeah. Felly newidynnau lleol. Anytime rydym angen rhywfaint o storio lleol, fel dadl, neu int I, neu int dros dro, neu beth bynnag y leol amrywiol yw, rydym wedi bod yn rhoi hwnnw ar y pentwr. Ac rydym yn galw ei fod yn pentwr oherwydd o'r syniad haenu. Dim ond math o gemau i fyny â realiti, y cysyniad ohono. 

Ond mae'n troi allan y gall pentwr hefyd ei weld fel strwythur data, mae amgen i amrywiaeth, dewis arall i restr cysylltiedig. Rhywbeth gysyniadol yn fwy diddorol y gall pethau fod gweithredu gan ddefnyddio naill neu'r llall o'r bethau, ond mae'n fath gwahanol o strwythur data ategol, mewn gwirionedd, dim ond dau gweithrediadau. Ond gallwch ychwanegu ffansi nodweddion na'r rhai hyn. Ond mae'r rhain yn y pethau sylfaenol - gwthio a pop. 

Ac mae'r syniad gyda stac yw os wyf yn gennym yma, gyda neu heb Annenberg gwybod, hambwrdd o ddrws nesaf gyda'r rhif 9 arno. Felly, dim ond int. Ac yr wyf yn awyddus i wthio hyn ar y data strwythur, sydd ar hyn o bryd yn wag. Ystyriwch hyn ar waelod y pentwr. Byddwn yn gwthio nifer hwn 9 ar y stacio, ac yn awr ei fod yn iawn yno. 

Ond y peth diddorol am pentwr yw os wyf yn awr am wthio rhywfaint o werth arall, fel 17, ac yr wyf yn gwthio hyn ar y pentwr, dw i'n mynd i wneud yr unig beth 'n athrylithgar, Im' jyst yn mynd i unioni'r sefyllfa lle rydym yn bodau dynol yn cael eu tueddu i roi, ar ei ben. Ond yr hyn sy'n ddiddorol yn awr yw, sut ydw i'n gael o 9? Rydych yn gwybod, nid wyf yn ei wneud heb rhywfaint o ymdrech. 

Felly, yr hyn sy'n ddiddorol am pentwr yw y dylunio, mae'n strwythur data LIFO. Silly ffordd o ddisgrifio olaf i mewn, cyntaf allan. Felly, y rhif olaf yn ar hyn o bryd oedd 17. Felly, os wyf am i pop rhywbeth oddi ar o'r pentwr, gall dim ond 17. Felly mae yna orchymyn mandadol gweithrediadau yma, lle yr eitem olaf yn rhaid iddo fod yn yr un cyntaf allan. Felly, mae'r acronym, LIFO. 

Felly, pam y gallai hyn fod yn ddefnyddiol? A yw eu cyd-destunau lle byddech eisiau strwythur data fel hyn? Wel, mae wedi bod yn ddefnyddiol yn sicr tu mewn i gyfrifiadur. Felly systemau gweithredu ddefnyddio hyn yn glir math o strwythur data ar gyfer staciau. Byddwn hefyd yn gweld yr un syniad pan ddaw i dudalennau gwe. Felly, yr wythnos hon a'r wythnos nesaf a thu hwnt, ac wrth i chi ddechrau gweithredu ar y we tudalennau mewn iaith o'r enw HTML, gallwch mewn gwirionedd yn defnyddio strwythur data fel hwn i benderfynu a yw'r dudalen wedi'i fformadu'n gywir. Oherwydd byddwn yn gweld yr holl dudalennau gwe yn dilyn rhyw fath o hierarchaeth, yn bant a fydd, ar ddiwedd y dydd, fod yn strwythur coeden o dan y cwfl. Felly mwy am hynny mewn dim ond ychydig. 

Ond am y tro, gadewch i ni yn cynnig am hyn o bryd, sut y gallem fynd ati i gynrychioli beth yw pentwr yw? Gadewch i mi cynnig ein bod yn gweithredu stac â'r cod fel hyn. Felly pentwr yn mynd i gael y tu mewn ohono ddau beth, amrywiaeth, a elwir yn hambyrddau, dim ond i fod yn gyson â'r demo. A phob un o'r eitemau yn y casgliad yn mynd i fod yn int fath. A gallu yn ôl pob tebyg beth? Gan nad wyf wedi ysgrifennu y diffiniad llawn yma. 

Mae'n debyg mai dyma'r mwyaf maint y rhesi. Ac mae'n debyg datgan fel miniog diffinio ar ben y ffeil, rhai math o gyson fel yr awgrymir gan y cyfalafu yn unig. Felly rhywle gallu ei ddiffinio fel y maint mwyaf posibl. Yn y cyfamser, y tu mewn i'r strwythur data a elwir yn pentwr bydd yna fod yn gyfanrif hysbys yn unig syml fel maint. 

Felly, pe bawn i gynrychioli'r hyn yn awr lluniau, gadewch i ni dybio bod hyn yn blwch du cyfan yn cynrychioli fy pentwr. Tu mewn iddo yw dau newidyn. Felly, yr wyf i'n mynd i dynnu un cyntaf fel maint. A'r ail un yr wyf i'n mynd i dynnu fel arae. 

Ond dim ond er mwyn cadw pethau'n drefnus, Fel arfer, byddwn yn tynnu amrywiaeth fel hyn, ond ei fod yn fath o 'n glws os ydym yn cyd-fynd â realiti, neu cyd-fynd â'r model meddwl. Felly, gadewch i mi yn lle tynnu amrywiaeth fertigol, sydd ychydig, unwaith eto, rendition artist. Nid yw'n wir bwys yr hyn y mae'n yw o dan y cwfl. A byddwn yn dweud bod, yn ddiofyn, gallu yn mynd i fod yn dri. Felly, bydd hyn yn lleoliad 0, mae hyn yn Bydd yn lleoliad 1, mae hyn yn Bydd yn lleoliad 2. 

Os byddaf yn llwgrwobrwyo gyda phêl straen, byddai rhywun yn hoffi i ddod i fyny ac yn rhedeg y bwrdd yma am ddim ond hyn o bryd? OK, gwelodd eich llaw yn gyntaf. Dewch ar i fyny. Mae pob hawl. Felly yr wyf yn credu ei fod yn Steven. Dewch ar i fyny. Mae pob hawl. 

Ond Tybiwch nawr rydym ailddirwyn i'r gychwynnol cyflwr y byd lle rwyf newydd datgan pentwr, ac mae'n yn mynd i fod o gapasiti tri. Ond nid yw maint wedi ei benderfynu eto. Nid yw hambyrddau wedi ei benderfynu eto. Felly, ychydig o gwestiynau yn gyntaf. A gadewch i mi yn rhoi meic i chi fel y gallwch cymryd rhan fwy gweithredol yn hyn. 

Felly, beth sydd y tu mewn o faint ar hyn o bryd mewn pryd os bydd yr holl wyf wedi ei wneud yw datgan stac gyda un llinell o god? 

STEVEN: Dim llawer. 

DAVID Malan: OK, dim llawer. A ydym yn gwybod beth sydd y tu mewn maint, ydym yn gwybod beth sydd y tu mewn y casgliad yma? 

STEVEN: Dim ond cod ar hap, dde? Just - 

DAVID Malan: Yeah, yr wyf i'n mynd i alw cod, ond ar hap - 

STEVEN: Pethau. 

DAVID Malan: Pethau fel hap 

STEVEN: darnau. 

DAVID Malan: darnau, dde? Felly gwerthoedd garbage, dde? Felly gyfnewidiadau o 0 ac 1 yn. Mae olion o usages blaenorol y cof hwn. Ac nid ydym yn wir yn gwybod beth yw'r gwerthoedd yn cael eu, felly rydym fel arfer yn tynnu eu fel marciau cwestiwn. 

Felly, y peth cyntaf i ni yn ôl pob tebyg mynd i eisiau ei wneud yma - a gadewch i mi roi y maes hwn y tu mewn o yna enw - hambyrddau. Beth ddylem ni yn ôl pob tebyg ymgychwyn maint os ydym am dechrau defnyddio pentwr hwn? 

STEVEN: Hambwrdd yn is 3. 

DAVID Malan: Felly, OK. I fod yn glir, gallu cael ei ddatgan mewn mannau eraill â thri. A dyna beth rwyf wedi defnyddio i ddyrannu y rhesi. Maint yn mynd i gyfeirio at faint o hambyrddau ar hyn o bryd ar y pentwr. 

STEVEN: Zero. 

DAVID Malan: Felly dylai fod yn sero. Felly, mynd yn ei flaen, a gydag unrhyw bys, tynnu sero o ran maint. Mae pob hawl. Felly nawr, beth sydd y tu mewn o hyn yma, nid ydym yn gwybod. Mae'r rhain yn wir werthoedd garbage yn unig. Felly, gallem dynnu marciau cwestiwn, ond gadewch i ni gadw'r bwrdd yn lân ar hyn o bryd am nad yw o bwys beth sydd yno. Nid oes angen inni i ymgychwyn y rhesi i unrhyw beth, oherwydd os ydym yn gwybod bod maint y pentwr yn sero, yn dda, rydym yn Ni ddylid edrych ar unrhyw beth yn amrywiaeth hwn beth bynnag yn hyn o bryd. 

Felly nawr mae'n debyg fy mod yn gwthio y rhif 9 ar y pentwr. Sut ddylem ni ddiweddaru'r strwythur data tu mewn y blwch du? Pa werthoedd angen newid? 

STEVEN: O fewn - maint? 

DAVID Malan: OK. Dylai maint yn dod yn beth? 

STEVEN: Byddai maint fod yn un. 

DAVID Malan: OK. Felly dylai maint ddod yn un. Felly, gallwch wneud hyn mewn cwpl o ffyrdd. Gadewch i mi roi i chi, nawr eich bys yn rhwbiwr. Mae pob hawl. Yna, nawr eich bys yn brwsh. Mae pob hawl. Ac yn awr beth arall wedi newid, yn amlwg, yn y strwythur data? 

STEVEN: Rydym yn mynd o gwaelod i fyny i 9. 

DAVID Malan: 9. Iawn, Da. Felly, yn dal yn ots beth sydd yn y lleoliad un neu ddau oherwydd eu bod yn gwerthoedd garbage, ond ni ddylem drafferthu edrych yno oherwydd maint yn dweud wrthym mai dim ond yr elfen gyntaf mewn gwirionedd yn gyfreithlon. Felly, yn awr yr wyf wthio 17 ar y rhestr. Beth sy'n digwydd i'r darlun hwn? 

STEVEN: Felly faint yn mynd i fynd i ddau. 

DAVID Malan: OK. Rydych yn rhwbiwr - wps. Rydych chi'n rwber. 

STEVEN: Eraser. 

DAVID Malan: Rydych chi'n brwsh. 

STEVEN: Brush. 

DAVID Malan: OK. A beth arall? 

STEVEN: Ac yna rydym yn - 

DAVID Malan: Yr ydym yn gwthio 17. 

STEVEN: Rydym yn cadw 17 ar ben, felly - 

DAVID Malan: OK, yn dda. 

STEVEN: - gollwng i lawr. 

DAVID Malan: Pob hawl. Mae'n mynd yn hawdd. Dydw i ddim yn mynd i helpu chi y tro hwn. Gwthiwch 22. 

STEVEN: Done. Dod yn rhwbiwr. Rwy'n dod yn brwsh. Ac yna yr wyf yn rhoi 22. 

DAVID Malan: 22. Ardderchog. Felly, un yn fwy o amser. Rwyf nawr yn mynd i wthio ar y pentwr 26. 

STEVEN: Ooh. Oh diar. Rydych yn wir yn dal fi oddi ar wyliadwrus. 

DAVID Malan: Nid ydych yn gwneud gweld hyn yn dod? 

STEVEN: Doeddwn i ddim yn gweld hyn yn dod. Gallem gallu ail-cychwynnol? 

DAVID Malan: Mae hynny'n gwestiwn da. Felly, rydym wedi math o beintio ein hunain mewn cornel yma. Yn wir, dim allan da i Steven oherwydd ein bod wedi dyrannu amrywiaeth hwn llonydd, fel petai, y tu mewn y strwythur data. Ac rydym wedi codio hanfod galed ei fod o faint tri. Felly, ni allwn mewn gwirionedd ei ailddyrannu. 

Gallem os ydym yn mynd yn ôl i mewn, rydym yn ailddiffinio hambyrddau i fod yn pwyntydd y Yna, rydym yn defnyddio malloc i gof llaw i. Oherwydd os ydym yn cael y cof o'r y domen drwy malloc, rydym yn yna gellid rhyddhau ei. Ond cyn ei ryddhau, gallem ailddyrannu fwy darn o gof, diweddaru'r pwyntydd, ac yn y blaen. Ond ar hyn o bryd, mae hyn yn wir y gorau y gallwn ei wneud. Gwthio a pop yn mynd yn ôl pob tebyg i gael i ddangos rhyw wall. 

Felly, er enghraifft, mae ein gweithredu o Gallai gwthio dychwelyd bool sy'n dychwelyd yn flaenorol yn wir, yn wir, yn wir. Ond y pedwerydd tro, mae'n mynd i gael dychwelyd ffug, er enghraifft. Mae pob hawl. Gwneud yn dda iawn. Llongyfarchiadau. Rydych chi wedi ennill eich pêl straen heddiw. 

[Cymeradwyaeth] 

STEVEN: Diolch yn fawr. 

DAVID Malan: Diolch yn fawr. Iawn, felly mae hyn yn ymddangos i fod dim llawer o yn gam ymlaen, dde? Rydym yn disgrifio hyn strwythur data. Mae wedi bod yn gymhellol, dde? Systemau gweithredu ei hoffi. Mae'n debyg y gall y we yn gwneud defnydd o hyn, a cheisiadau eraill yn dal. Ond beth yw cyfyngiad dwp ein bod ni'n yn ôl i'r math o wythnos dau terfynau lle rydym wedi sefydlog araeau maint. 

Felly, mae yna wir un neu ddau o ffyrdd y gallem ddatrys hyn. Gallai ddynamig yn dyrannu'r amrywiaeth, nid gan codio galed gan fy mod i wedi wneud yma, ond yn hytrach ail-ddatgan hyn, dim ond i fod yn glir, fel y rhywbeth fel hyn. * Hambyrddau int, nid penderfynu ar y gallu eto. Ond pan fyddaf yn datgan bod y pentwr mewn man arall yn fy cod, gallwn wedyn alw malloc, gael y cyfeiriad o darn o cof, a gallwn neilltuo y cyfeiriad hwnnw i hambyrddau. 

Ac yna, oherwydd mai dim ond darn o cof, gallwn barhau i ddefnyddio sgwâr nodiant braced yn y ffordd arferol. Oherwydd unwaith eto, mae hyn yn fath o cyfateb swyddogaethol araeau a darnau o gof sy'n dod yn ôl o malloc. Gallwn drin un fel y llall defnyddio rhifyddeg pwyntydd neu nodiant braced sgwâr. Felly, dyna un dull o weithredu. 

Ond sut arall y gallwn roi hyn ar waith strwythur data un fath, o bosibl? Iawn? Rwy'n teimlo fel ni ond datrys hyn problem fel wythnos yn ôl. Beth oedd yr ateb i'r broblem hon Steven bod yn rhedeg i mewn? Rhestrau Felly cysylltiedig, ar y dde. 

Os yw'r broblem yn ein bod yn paentio ein hunain i mewn i gornel trwy ddyrannu ymlaen llaw yn rhy fach cof ein bod yn Yna, wedi i rhywsut ddelio â nhw, yn dda, pam na dim ond osgoi hynny cyhoeddi yn gyfan gwbl? Pam nid dim ond datgan hambyrddau i fod yn pwyntydd i nod, ergo restr cysylltiedig, ac yna dim ond dyrannu nodau newydd bob amser sydd ei angen Steven i osod nifer yn y strwythur data. 

Felly, byddai'n rhaid i'r llun i newid. Dyw hi ddim yn mynd i fod mor lân ac fel syml â dim ond casgliad o dri ints. Nawr, mae'n mynd i fod yn pwyntydd i strwythur, a bod y strwythur yn mynd i cael int a pwyntydd nesaf. Mae'n mynd i arwain trwy gyfrwng y pwyntydd i strwythur arall o'r fath i strwythur arall o'r fath. Felly, byddai'r darlun mewn gwirionedd cael braidd yn anniben. A byddem yn wedi saethau glymu popeth at ei gilydd. 

Ond mae hynny'n iawn, iawn, oherwydd rydym wedi gweld sut i wneud hyn. Ac unwaith y byddwch yn gyfforddus weithredu rhywbeth fel cysylltiedig rhestr, a bydd rhaid i chi ei wneud os ydych yn ddewis gweithredu tabl hash gyda gadwyno ar wahân ar gyfer p-set 6, gallwch ei ddefnyddio fel bloc adeiladu, neu cynhwysyn, neu mewn Scratch siarad, a weithdrefn, rhywbeth yr ydych yn ei roi, i chi creu eich darn pos eich hun y gallwch wedyn ailddefnyddio. Cyfaddawdu hynny, ond atebion posibl yr ydym wedi gweld mewn gwirionedd o'r blaen. 

Felly, yn aml iawn, byddwch yn gweld hyn bob blwyddyn neu ddau pan Datganiadau Apple rhywbeth newydd, a'r holl bobl crazy llinell i fyny y tu allan i'r Apple storio i brynu eu ymylol uwchraddio ar galedwedd. Yr wyf yn dweud hyn, mae'n iawn, gan fod Yr wyf yn un o'r bobl hynny. Felly, pa fath o strwythur data allai gynrychioli realiti hwn? 

Wel, gadewch i ni ei alw yn ciw, llinell. Felly, byddai Prydain yn galw fel arfer yn ciw beth bynnag, felly mae'n enw 'n glws. A'r ddau gweithrediadau y ciw Bydd cefnogi byddwn yn galw enqueue gweithredu a gweithrediad dequeue, sy'n debyg o ran ysbryd i gwthio a pop. 'I' jyst fath o wahanol confensiwn, yr hyn rydym yn galw hyn. Ond i enqueue rhywbeth olygu i ychwanegu neu rhowch i'r strwythur data. I dequeue olygu i symud oddi yno. Ond tra bod pentwr oedd data LIFO strwythur, ciw yn i mewn yn gyntaf, cyntaf allan strwythur data. 

Os mai chi yw'r person cyntaf yn unol, chi fydd y person cyntaf i gael allan o linell a phrynu eich dyfais newydd. Dychmygwch pa mor ofidus fyddai'r bobl hyn yn os Apple yn hytrach na defnyddio stac, er enghraifft, i weithredu'r casglu cynnwys eich tegan newydd. Felly ciwiau yn gwneud synnwyr, yn sicr, a gallwn ni feddwl am bob math o ceisiadau, yn ôl pob tebyg, ar gyfer ciwiau, yn enwedig pan ydych eisiau tegwch. Felly, sut y byddwn yn gweithredu'r fel strwythur data? 

Wel, yr wyf yn cynnig ein bod yn gallai angen iddynt ei wneud fel hyn. Felly, yr wyf i'n mynd i awr rhifau. Felly, byddwn yn ei gadw'n syml ac nid reidrwydd yn siarad yn nhermau hambyrddau. Dim ond nifer fod pobl o gotten. Gallu yn mynd i, unwaith eto, atgyweiria 'r cyfanswm nifer y bobl sy'n gallu fod mewn y llinell hon, fel tri neu beth bynnag werth arall. 

Ond yr wyf yn cynnig bod angen i mi gadw golwg nid yn unig o faint y ciw, faint o bethau o blaid hyn. Felly, faint yw maint, capasiti cyfredol yn uchafswm maint. Dim ond eto, enwau drwy gonfensiwn. Pam mae angen int ychwanegol y tu mewn i o ciw i gadw cofnod o bwy sydd yn flaen y llinell? Pam mae angen i mi wneud hynny yn yr achos hwn? 

Wel, sut mae hyn ddarlun mynd i newid? Mae'n debyg y gallaf ailddefnyddio fwyaf y darlun hwn. Gadewch i mi fynd yn ei flaen ac yn dileu yr hyn sydd yma. Byddwn yn rhoi hyn ychydig yn enw gwahanol i fyny yma. Gadewch i ni gael gwared ar y 17, gadewch i ni gael gwared o'r 9, gadewch i ni gael gwared ar y 3. A gadewch i ni ychwanegu un peth arall. Cynigiaf fod angen i mi gadw golwg ar flaen y rhestr, sydd ychydig mynd i fod yn int hefyd. Ac rydym yn mynd i gadw pethau'n syml. Dim rhestr gysylltu am y tro. 

Byddwn yn cyfaddef ein bod yn mynd i daro i fyny yn erbyn y terfyn hwn. Ond beth ydw i eisiau gweld digwydd y tro hwn? Felly, mae'n debyg i fynd ymlaen a'r cyntaf person yn dod i fyny yn unol, ac 'i' y rhif 9. Oes gennym peli straen. A allaf ddwyn, dyweder, dau neu dri o bobl? Un, dau, tri? Dewch ar i fyny. O'r blaen, oherwydd byddwn yn gwneud hyn yn un cyflym. 

Mae pob un ohonoch yn awr yn mynd i fod yn bachgen fan yn unol yn Apple. Ni fyddwch yn derbyn Apple caledwedd ar ddiwedd y er. Mae pob hawl. Felly rydych yn rhif 9, rydych yn rhif 17, rhif 22. Mae'r rhain yn niferoedd fympwyol, fel myfyriwr IDs neu whatnot. Ac mewn dim ond hyn o bryd, gadewch i ni ddechrau i ddechrau ychwanegu pethau. A byddaf yn rhedeg y bwrdd yma y tro hwn. 

Felly, yn yr achos hwn, rwyf wedi ymgychwyn y blaen i fod - Nid wyf mewn gwirionedd yn wir yn poeni beth y blaen yw, oherwydd bod y maint yn sero. Felly, efallai yn ogystal dim ond hyn fod yn farc cwestiwn. Mae'r rhain i gyd yn farciau cwestiwn. Felly nawr byddwn yn dechrau mewn gwirionedd yn gweld rhai pobl yn leinin i fyny yn y siop. 

Felly, os rhif 9, chi yw'r un cyntaf yno am 05:00, mynd yn ei flaen ac yn llinell i fyny, neu y noson cynt. OK. Felly nawr 9 yma. Felly 9 yn y flaen y rhestr. Felly, yr wyf i'n mynd i fynd yn ei flaen a diweddaru maint y data cyfredol strwythur i beidio â fod yn 0 anymore, ond i fod yn 1. Rydw i'n mynd i roi 9 yn y flaen y rhestr. Gadewch i mi fynd yn ei flaen ac yn toggle y sgrin fel y gallwn weld y gorffennol ni yma. 

Ac yn awr beth ddylwn i ei eisiau i roi o flaen? Rydw i'n mynd i gadw golwg ar y flaen y ciw ar hyn o bryd ar leoliad 0. Oherwydd yr hyn sy'n nesaf yn mynd i ddigwydd? Wel, mae'n debyg yn awr yr wyf enqueue 17 hefyd. Felly hop yn unol yno. Ac eto, y math o ddrws i siop yn mynd i fod yma. Felly, yn awr yr wyf wedi ychwanegu 17. A hyd yn oed er bod guys hyn yn cael eu blocio y sgrin, mae hynny'n iawn, oherwydd gallwn weld i fyny yma. Mae'n ddrwg gennym. 

GYNULLEIDFA: Gallwn symud - 

DAVID Malan: Na, mae hynny'n iawn. Mae'n enfawr i fyny yno. Felly 17 yn bellach y tu mewn y ciw. Angen i mi ddiweddaru a caeau nawr er bod? OK, yn bendant faint. A beth am flaen? OK, dim. Ni ddylai Front newid, oherwydd yn wahanol i stac, rydym yn am gynnal tegwch. Felly, os 9 yn dod i mewn yn gyntaf, yr ydym am 9 i fod y cyntaf allan o'r llinell ac i mewn i'r siop. 

Yn wir, gadewch i ni weld hynny. Cyn i ni ychwanegu 22, gadewch i ni mynd yn ei flaen a dequeue 9. Beth yw eich enw eto? 

GYNULLEIDFA: Jake. 

DAVID Malan: Jake yn mynd i gael dequeued awr. Felly, byddwch yn cael i gerdded i mewn i'r siop. Ac yn esgus bod y siop wedi dod i ben yno. Felly nawr beth sydd angen - dit-dit-dit! Beth sydd angen digwydd yn awr? Penderfyniad dylunio. Felly nid yw greddf drwg, ond - beth yw eich enw eto? 

GYNULLEIDFA: David. 

DAVID Malan: David. Felly, yr hyn a wnaeth Dafydd yn ei wneud? Roedd yn ceisio datrys o ddatrys y data strwythur a symud oddi wrth ei leoliad i mewn i hen leoliad Jake. Ac mae hynny'n iawn os ydym yn barod i dderbyn hynny fel manylion gweithredu. Ond yn gyntaf, gadewch i ni roi'r wybodaeth ddiweddaraf i'r data strwythur cyn i ni wneud hynny. Oherwydd Dydw i ddim yn hoffi'r syniad o holl y bobl symud yn y llinell hon. 

Does dim llawer mawr os bydd David yn gwneud 'i ag un cam, ond unwaith eto, yn meddwl yn ôl i pan fyddwn wedi cael wyth o wirfoddolwyr ar y llwyfan ac rydym wedi gwneud fel gosod fath, lle y bu'n rhaid i ni ddechrau symud pawb o gwmpas. A gafodd ddrud, dde? Mae hynny'n gwneud i mi cringe am O mawr n, mawr O n sgwâr eto. Dyw hi ddim yn teimlo fel canlyniad delfrydol. 

Felly, gadewch i ni ddiweddaru'r. Felly, maint y ciw bellach 2. Mae'n awr yn unig 1. Ond gallaf nawr ddiweddaru rhywbeth Doeddwn i ddim yn diweddaru o'r blaen, mae'r flaen y rhestr. Caf fi ddweud, yw bod lleoliad 1? Felly, erbyn hyn mae gennym werth garbage yma, gwerth garbage yma, a David yn y canol y garbage hwn. Ond mae'r strwythur data yn dal yn gyfan. 

Ac yn wir, nid oes angen hyd yn oed i mi newid cyn-nifer Jake 9, oherwydd pwy a gofalu. Mae gen i ddigon o wybodaeth bellach yn y maint fy mod yn gwybod oes un person yn ciw hwn. Ac yr wyf yn gwybod bod y person hwnnw yn y lleoliad 1, nid 0. Dydw i ddim yn cyfrif. Felly, 1 hefyd. Felly, y strwythur data yn dal i fod yn iawn. 

Wel, beth sy'n digwydd nesaf? Gadewch i ni enqueue - beth yw eich enw? 

GYNULLEIDFA: Callen. 

DAVID Malan: Callen. Gadewch i ni enqueue a Callen, a 22 yn awr yn y ciw. Felly, yn awr yr hyn sydd wedi ei newid yma? Nid yw blaen yn mynd i newid, yn amlwg. Maint yn mynd i newid i fod yn 2 eto. A 22 yn dod i ben i fyny yma, 9 yn dal yn bresennol, ond mae'n effeithiol yn gwerth garbage awr. Dim ond yn weddill Jake gorffennol. 

Felly, yn awr beth fydd yn digwydd os Yr wyf dequeue David? Un gweithrediad diwethaf, dequeue David. Gallem newid, ond yr wyf yn cynnig gadewch i gwneud cyn lleied o waith ag y bo modd. Nawr fy strwythur data yn mynd gefn o ran maint 2-1. Ond flaen y ciw nawr yn 2. Nid oes angen i mi newid y rhifau hyn eto, am eu bod yn gwerthoedd garbage yn unig. 

Ond yn awr beth sy'n digwydd? Gadewch i ni dybio wyf enqueue fy hun, 26? Rwy'n teimlo fy mod yn perthyn dros yma. Felly rwy'n cael enqueued. Felly, yr wyf yn fath o yn perthyn yma. A hyd yn oed er eich bod yn ei wneud ddim yn hollol gwerthfawrogi hyn weledol ar y llwyfan, gan fod gennym ddigon o le, dylwn Nid yn sefyll yma, pam? 

GYNULLEIDFA: Rydych chi allan o nerth. 

DAVID Malan: Iawn. Rwy'n yn waharddedig. Rwyf wedi mynegeio y tu hwnt i'r ffiniau amrywiaeth hwn. Fi 'n sylweddol dylai fod yn un o'r tri lleoliad posibl. Nawr, ble mae'r rhan fwyaf naturiol i fynd? Cynigiaf ein ysgogi yr wythnos un tric. Mae'r gweithredwr mod, canran. Gan fy mod i'n dechnegol sefyll yn lleoliad 3, ond yr wyf yn 3 capasiti mod, hynny 3, arwydd y cant, 3 - capasiti yn 3. Beth sy'n bod? Beth yw'r gweddill pan rydych rhannu 3 erbyn 3? 0. 

Er mwyn i mi eu rhoi oedd Jake, sy'n beth da mewn gwirionedd. Felly, yn awr y gweithrediad y peth yn mynd i fod yn dipyn o gur pen. Mae'n wir yn un llinell yn unig o cur pen, o god. Ond o leiaf yn awr mae garbage gwerth yma, ond mae dau ints cyfreithlon yma. Ac yr wyf yn honni bod yn awr rydym wedi gwneud yn union beth sydd angen i wneud hynny cyhyd ag rydym yn newid yr hyn Jake werth oedd i fod yn 26. 

Erbyn hyn mae gennym ddigon o wybodaeth yn dal i i gynnal dilysrwydd y strwythur data. Rydym yn dal math o allan o lwc pan fyddwn yn eisiau i fewnosod pedwar neu fwy o gyfanswm elfennau, ond gallaf o leiaf yn gwneud 'n bert defnydd effeithlon o hyn cyson amser, mewn gwirionedd. Nid oes yn rhaid i mi boeni am newid bawb, fel awydd David oedd. 

Unrhyw gwestiynau ar staciau, neu ciw hwn? 

GYNULLEIDFA: A yw'r rheswm pam bydd angen maint er mwyn i chi wybod ble i gael person? 

DAVID Malan: Yn union. Angen i mi wybod y maint y rhesi oherwydd mae angen i mi wybod yn union sut y llawer o'r gwerthoedd hyn yn gyfreithlon, ac fel y gallaf ddod o hyd i ble i roi y person nesaf. Yn union. Mae maint yw - mewn gwirionedd, nid ydym yn diweddaru'r hyn eto. I ychwanegu fy hun yn 26. Mae'r maint yn awr, nid 1, ond 2. Felly, yn awr mae hyn yn wir yn fy helpu i ddod o hyd i'r pennaeth y rhestr, nad yw'n 0, nid 1, ond yw 2. Mae blaen y rhestr yn wir rhif 22. Oherwydd efe a ddaeth i mewn yn gyntaf, felly dylai ef yn cael ei ganiatáu i mewn i'r siop ger fy mron, hyd yn oed er eu golwg Dwi'n sefyll yn agosach at y siop. 

Mae pob hawl? Mae rownd o gymeradwyaeth ar gyfer guys hyn a byddwn yn gadael iddynt oddi yno. 

[Cymeradwyaeth] 

DAVID Malan: Gallwn roi eich bod yn cadw yr hambwrdd. Gallem weld beth sy'n digwydd os ydych ei eisiau, ond efallai na. Mae pob hawl. Felly beth nawr mae hynny'n gadael ni? Wel, gadewch i mi cynnig bod yna ychydig o strwythurau data arall gallem dechrau ychwanegu at ein pecyn cymorth a fydd yn mewn gwirionedd fod yn eithaf, yn eithaf perthnasol fel rydym yn plymio i mewn i we stwff. Sydd unwaith eto, mae rhyw fath o gysylltiad i goed ar ffurf rhywbeth o'r enw DOM, dogfen model gwrthrych. Ond byddwn yn gweld mwy o hynny cyn bo hir. 

Gadewch i mi gynnig definitionally ein bod yn ffoniwch goeden yn awr yr hyn y gallai gwybod i chi cyn mwy o goeden deulu, lle rydych yn cael rhywfaint o hynafiad yn y gwreiddiau'r goeden. A batriarchaidd neu matriarch yn frig y goeden. Heb ei briod, yn yr achos hwn. Ond mae gennym yn awr yr hyn y byddwn yn galw plant, sef nodau sy'n hongian oddi ar y plentyn chwith neu i'r plentyn iawn, saethau fel y dangosir yma. 

Mewn geiriau eraill, mewn strwythur data coeden mewn cyfrifiadur, coeden wedi sero neu fwy o nodau. Os oes o leiaf un nod, sy'n cael ei alw y gwraidd. Mae'n y pethau weledol y rydym yn tynnu ar y brig. A dyna nod, fel unrhyw nod arall, gall gael sero, un, neu ddau, neu dri, neu faint bynnag o blant y strwythur data yn cefnogi. Yn yr achos hwn, y gwraidd, storio gwerth un, mae dau o blant, 2 a 3, felly rydym yn gyffredinol ffoniwch 2 y chwith plentyn a 3 y plentyn cywir. 

Ac yna pan fyddwn yn mynd i lawr i 5, 6, a Efallai 7, 6 yn cael ei alw y plentyn canol. Os oes gennych bedwar o blant, mae'n mynd yn ddryslyd. Felly, rydym yn rhoi'r gorau i ddefnyddio math hwnnw o'r llwybr byr ar lafar. Ond mewn gwirionedd dim ond coeden deulu. Ac mae'r dail yma y nodau y eu hunain heb blant. Maent yn hongian oddi ar waelod y goeden. 

Felly, sut y gallem weithredu coeden sy'n wedi dim ond dau o blant maximally? Byddwn yn galw ei fod yn goeden ddeuol. Bi eto yn golygu dau, yn yr achos, fel gyda deuaidd. Ac felly gall gael sero, un, neu ddau o blant maximally. 

'N annhymerus' cynnig ein bod yn gweithredu'r nod am y strwythur gyda n int, ac yna dau awgrymiadau, un o'r enw chwith, un o'r enw gywir. Ond y rhai yn unig 'n glws confensiynau mympwyol. A beth braf yn awr, yn enwedig os ydych yn fath o drafferth gysyniadol gyda recursion, neu yn meddwl nad oedd yn mewn gwirionedd yn ateb i unrhyw beth, yn enwedig os gallech rhedeg allan o gof. Nawr ein bod yn sôn am ddata strwythurau ac algorithmau sy'n caniatáu ni i groesi a thrin nhw, ymddangos bod recursion yn dod yn ôl yn llawer mwy cymhellol os nad yw ffordd hardd. 

Felly, mae hyn Cynigiaf yw'r gweithredu o swyddogaeth Chwilio. O ystyried dau fewnbwn - felly meddyliwch am hyn fel blwch du. O ystyried dau fewnbwn, n, yn int, a pwyntydd i goeden, pwyntydd i nod, neu, mewn gwirionedd wraidd coeden, yr wyf yn honni y gall swyddogaeth hon ddychwelyd gwir neu ffug, sy'n gwerthfawrogi n tu mewn y goeden hon. 

Beth sydd y tu mewn y blwch du? Wel, pedair cangen. Y cyfiawn gyntaf yn gwirio. Os yw coeden yn null, dim ond dychwelyd ffug. Os nad oes nod, does dim n, does dim rhif, dim ond dychwelyd ffug. Os, fodd bynnag, n, mae'r gwerth rydych yn chwilio amdano, yn llai na goeden saeth n, ac dim ond i fod yn glir, beth mae'n ei olygu pan Rwy'n ysgrifennu goeden ac yna y saeth nodiant, n? Yn union. Mae'n golygu bod dereference pwyntydd enw coeden. Ewch yno, ac yna yn cael y tu mewn o hynny nod a chael ei faes a elwir yn n. Ac yna cymharu'r n gwirioneddol a oedd yn pasio i mewn i Chwilio yn ei erbyn. 

Felly, os n yn llai na, mae'r gwerth n yn y nod goeden ei hun, yn dda, beth mae hynny'n ei olygu? Mae hynny'n golygu dim byd ar yr olwg gyntaf. Iawn? Yn union fel pan fydd gennych amrywiaeth o gwerthoedd, efallai yr hoffech wneud cais deuaidd chwilio fel math o raniad a gorchfygu. Ond beth dybiaeth oedd angen i ni wneud ar gyfer chwiliad deuaidd i weithio o gwbl yn y llyfr ffôn ac enghreifftiau cynharach? 

Sut i gael eu datrys. Felly, gadewch i ni fireinio'r diffiniad o goeden yma nid yn i fod yr un goeden, a all cael unrhyw nifer o blant. Nid dim ond coeden ddeuaidd, a all cael 0, 1, neu 2 maximally. Ond fel coeden chwiliad deuaidd, neu BST, sydd ychydig yn ffordd ffansi o ddweud goeden ddeuol fel bod pob nod yn chwith plentyn, os yw'n bresennol, yn llai na'r nod. A'r plentyn hawl pob nod, yn os yw'n bresennol, yn fwy na'r nod ei hun. 

Felly, mewn geiriau eraill, os ydych yn tynnu y tu allan i goeden, yr holl niferoedd yn gydbwyso yn ofalus fel hyn felly os mae gennych 55 fel y gwraidd, gall 33 fynd ar yr ochr chwith am ei fod yn llai na 55. 77 Gall mynd i'r dde oherwydd ei fod yn fwy na 55. Ond yn awr yn sylwi, yr un diffiniad, mae'n ddiffiniad ailadroddus ar lafar, wedi gwneud cais am 33. Mae'n rhaid i 33 o blant ar y chwith fod yn llai na hynny, a rhaid plentyn iawn 33, a 44, yn yn fwy nag ef. 

Felly, mae hyn yn goeden chwiliad deuaidd, a Yr wyf yn cynnig, gan ddefnyddio ychydig o recursion, gallwn yn awr ddod o hyd i n. Felly, os n yn llai na gwerth n sy'n nod ar hyn o bryd, dw i'n mynd i fynd ymlaen a punt, fel petai, a dim ond dychwelyd beth bynnag yw'r ateb o chwilio am n ar y plentyn chwith goeden. Hysbysiad eto, swyddogaeth hon dim ond disgwyl yn seren nod, a pwyntydd i nod. Felly, yn sicr y gallaf wneud coeden saeth ar y chwith, a fydd yn arwain mi nod arall. Ond beth yw y nod? 

Wel, yn ôl y datganiad hwn, chwith yn unig yw pwyntydd, er mai dim ond golygu fy mod i'n mynd at y swyddogaeth chwilio pwyntydd gwahanol, sef yr un sy'n cynrychioli coeden fy mhlentyn chwith yn. Felly, yn yr achos hwn, y pwyntydd i 33, os mae hyn yn ein cyfraniad sampl y cyfamser, os n yn fwy na gwerth n yn y nod ar hyn o bryd yn y goeden, yna rwy'n mynd i fynd yn ei flaen ac punt yn y llall cyfeiriad a dim ond dweud, nid wyf yn gwybod os y gwerth hwn yw n yn y goeden, ond yr wyf yn gwybod os yw, ei fod yn i lawr fy cangen iawn, fel petai. Felly, gadewch i mi alwad chwilio recursively, pasio n eto, ond pasio mewn pwyntydd i fy mhlentyn dde. 

Mewn geiriau eraill, os ydw i'n ar hyn o bryd yn 55 ac rwy'n edrych am 99, yr wyf yn gwybod bod 99 yn fwy na 55, felly dim ond fel yr wyf yn rhwygo y ffôn llyfr wythnosau yn ôl ac rydym aeth yn iawn, yn yr un modd rydym ni mynd i fynd i'r dde yma. Ac nid wyf yn gwybod os yw'n ar fy hawl plentyn, ac nid yw'n, 77 yno, ond Dwi'n gwybod ei fod yn y cyfeiriad hwnnw. Felly, yr wyf yn galw chwilio am fy mhlentyn dde, 77, a gadewch ffigur chwilio allan o yno os 99 yn yr fympwyol enghraifft o hyn yw mewn gwirionedd yno. 

Else, beth yw'r achos terfynol? Os yw coeden yn null un achos. Os yw n yn llai na'r nod ar hyn o bryd yn gwerth yn achos arall. Os yw n yn fwy na'r presennol gwerth nod yw trydydd achos. Beth yw'r achos bedwaredd a'r olaf? Yr wyf yn meddwl ein bod allan o achosion, dde? Rhaid iddo fod yn bod n yn y nod ar hyn o bryd a dwi ar. 

Felly, os ydw i'n chwilio am 55 ar hyn o bryd yn y stori, y gangen o byddai coeden yn dychwelyd yn wir. Felly, yr hyn sy'n ddiddorol yma yw ein bod yn mewn gwirionedd, yn wahanol wythnosau diwethaf, rydym fath o'r gennym ddau achos sylfaenol. Ac nid oes rhaid iddynt cael ei gyd ar y brig. Mae pen uchaf yn achos sylfaenol oherwydd os bydd y goeden yn null, does dim byd i'w wneud. Dim ond dychwelyd codio galed gwerth o ffug. 

Mae'r gangen gwaelod yn fath o diofyn, lle os ydym wedi gwirio ar gyfer null, rydym wedi gwirio os dylai fod yn chwith, ond ni ddylai fod yn, rydym wedi gwirio a ddylai fod yn iawn, ond mae'n Ni ddylai fod, yn amlwg mae'n rhaid iddo fod iawn lle yr ydym. Dyna achos sylfaenol. Felly, mae dau achos recursive gwasgu yno yn y canol. Ond gallwn fod wedi ysgrifennu hyn mewn unrhyw drefn. Fi jyst yn meddwl ei fath o teimlo'n naturiol i wirio yn gyntaf am gamgymeriad posibl, ac yna gwirio'r i'r chwith, ac yna gwirio'r dde, ac yna cymryd yn ganiataol eich bod chi yn y nod rydych yn chwilio amdano mewn gwirionedd. 

Felly, pam y gallai hyn fod yn ddefnyddiol? Felly, mae'n troi allan - a gadewch i mi neidio i ymlid dyma sydd yn y we. Rydym yn mynd i ddechrau defnyddio nid iaith raglennu ar y dechrau, ond mae iaith markup. A markup iaith yn un sy'n debyg o ran ysbryd i'r rhaglenni iaith, ond nid yw'n rhoi i chi y gallu i fynegi eich hun yn rhesymegol. Mae'n yn unig yn rhoi i chi y gallu i mynegi eich hun strwythurol. 

Ble ydych chi eisiau rhoi rhywbeth ar y dudalen, mae'r dudalen ar y we? Pa liw ydych chi eisiau ei wneud? Pa faint ffont ydych chi eisiau ei wneud? Pa eiriau ydych chi mewn gwirionedd yn chwilio amdanynt ar y dudalen we? Felly dyna iaith markup. Ond yna byddwn yn cyflwyno yn gyflym iawn JavaScript, sydd yn llawn-fledged rhaglennu iaith. Debyg iawn o ran golwg syntactically i C, ond bydd yn cael rhywfaint o 'n glws, yn fwy pwerus, yn fwy nodweddion cyfeillgar i'r defnyddiwr. 

Ac un o'r rhwystredigaethau ar hyn o pwynt yn y semester yw ein bod yn chi helpu fuan gweithredu sillafu yn llawer llai llinellau o god ddefnyddio ieithoedd eraill na C ei hun yn caniatáu, ond am reswm yn byddwn yn deall yn fuan. Hwn fydd y dudalen we cyntaf o'r fath. Bydd yn gwbl underwhelming, yr un cyntaf a wnawn. Bydd yn dweud yn syml, helo byd. Ond os nad ydych erioed wedi ei weld o'r blaen, mae hyn yn HTML, HyperText Markup Iaith. 

Os ydych yn mynd i ddewis penodol ddewislen rhan fwyaf o unrhyw borwr, ar unrhyw dudalen ar y we ar y rhyngrwyd, gallwch weld y HTML a ysgrifennodd rai pobl creu y dudalen we. Ac mae'n debyg nad yw'n edrych fel byr neu mor daclus â hyn. Ond bydd yn dilyn y patrwm o'r rhain cromfachau agored a slaes a llythrennau ac o bosibl rhifau. 

Rwy'n meddwl y byddwn i'n rhoi teaser i chi o'r hyn y byddwch yn gallu gwneud ar ôl cymryd CS50. Gadewch i mi fynd i cs.harvard.edu / ddwyn, hafan ein hunain Rob Bowden. Gwnaeth hyn i ni. Felly byddwch yn fuan yn gallu gwneud hynny. A hefyd, yr hyn yr ydych wedi clywed y bore yma - yr hyn yr ydych wedi clywed y bore yma - 

[Bochdew DAWNS CERDDORIAETH] 

- You'll yn gallu gwneud hyn. Mae hynny'n ein disgwyl ar ddydd Mercher. Byddwn yn eich gweld bryd hynny. 

[Bochdew DAWNS CERDDORIAETH] DAVID Malan: Yn y CS50 nesaf -