[Powered by Google Translate] [Wythnos 6, Parhad] [David J. Malan] [Harvard University] [Mae hyn yn CS50.] [CS50.TV] Mae hyn yn CS50, a dyma'r diwedd wythnos 6. Felly CS50x, un o Harvard gyrsiau gyntaf yn cynnwys yn y fenter EDX yn wir debuted Ddydd Llun yma yn y gorffennol. Os hoffech chi i gael cipolwg ar beth mae pobl eraill ar y Rhyngrwyd yn awr yn dilyn ynghyd â, gallwch pen i x.cs50.net. Bydd hynny'n eich ailgyfeirio at y lle priodol ar edx.org, lle yr oedd hyn a chyrsiau eraill o MIT a Berkeley yn byw. Bydd rhaid i chi gofrestru ar gyfer cyfrif; fe welwch fod y deunydd i raddau helaeth yr un fath fel eich bod wedi cael y semester, er ychydig wythnosau oedi, gan ein bod yn cael popeth yn barod. Ond beth fydd myfyrwyr yn CS50x awr yn gweld yn rhyngwyneb yn eithaf fel yr un yma. Hyn, er enghraifft, yn Zamyla arwain y walkthrough ar gyfer plant 0 set problem. Ar ôl logio i mewn i edx.org, myfyriwr CS50x yn gweld y math o bethau byddech yn disgwyl eu gweld mewn cwrs: y ddarlith am y dydd Llun, darlith ar gyfer dydd Mercher, siorts amrywiol, bydd y setiau broblem, y walkthroughs, ffeiliau PDF. Yn ogystal, fel y gwelwch yma cyfieithiadau peiriant, o drawsgrifiadau Saesneg i Tseineaidd, Siapanaeg, Sbaeneg, Eidaleg, a bagad cyfan o ieithoedd eraill a fydd yn sicr o fod yn amherffaith wrth i ni gyflwyno mesuryddion deallus programmatically gan ddefnyddio rhywbeth o'r enw API, neu gais, rhyngwyneb rhaglennu o Google sy'n ein galluogi i drosi Saesneg i'r ieithoedd eraill. Ond diolch i ysbryd gwych gan rai gwirfoddolwyr can a throsodd, pobl ar hap ar y Rhyngrwyd sydd wedi cynnig yn garedig i gymryd rhan yn y prosiect hwn, byddwn yn raddol wella ansawdd y cyfieithiadau drwy gael pobl gywiro'r camgymeriadau fod ein cyfrifiaduron wedi eu gwneud. Felly, mae'n troi allan ein bod wedi ychydig o fyfyrwyr yn fwy dangos i fyny ar ddydd Llun nag oeddem yn ei ddisgwyl i ddechrau. Yn wir, erbyn hyn CS50x mae 100,000 o bobl yn dilyn ar hyd yn y cartref. Felly, yn sylweddoli eich bod yn i gyd yn rhan o'r dosbarth hwn gyntaf o wneud y cwrs hwn mewn gwyddoniaeth gyfrifiadurol addysg yn fwy cyffredinol, yn fwy cyffredinol, hygyrch. A'r gwir amdani yw yn awr, gyda rhai o'r cyrsiau hyn enfawr ar-lein, maent i gyd yn dechrau gyda'r rhifau hyn yn uchel iawn, gan ein bod yn ymddangos i wedi ei wneud yma. Ond y nod, yn y pen draw, ar gyfer CS50x yw ein bod yn cael cymaint o bobl at y llinell derfyn ag y bo modd. Erbyn dylunio, CS50x yn mynd i gael eu cynnig o ddydd Llun gorffennol mae hyn yr holl ffordd drwy 15 Ebrill, 2013, fel bod Folks sydd ag ymrwymiadau ysgol mewn mannau eraill, gwaith, teulu, gwrthdaro eraill ac yn y blaen, hyblygrwydd ychydig yn fwy â hwy i ddeifio i mewn i'r cwrs, sydd, digon yw dweud, yn eithaf uchelgeisiol ei wneud os mai dim ond dros gyfnod o dri mis yn unig yn ystod semester arferol. Ond bydd y myfyrwyr yn mynd i'r afael â'r setiau un broblem, edrych ar yr un cynnwys, cael mynediad i'r un trowsus byr ac yn y blaen. Felly, yn sylweddoli ein bod i gyd yn wir yn hyn gyda'n gilydd. Ac nid yw un o nodau diwedd CS50x yw dim ond i gael Folks cymaint at y llinell derfyn ac yn rhoi iddynt ddealltwriaeth hon newfound o wyddoniaeth gyfrifiadurol a rhaglennu, ond hefyd i gael eu cael y profiad a rennir. Un o nodweddion diffiniol o 50 ar y campws, rydym yn gobeithio, wedi bod yn y math hwn o brofiad cymunedol, er gwell neu er gwaeth, weithiau, ond yn cael y bobl i droi at y chwith ac i'r dde, oriau swyddfa a hackathon a'r ffair. Mae'n ychydig yn galetach i wneud hynny yn bersonol gyda Folks ar-lein, ond bydd CS50x ben ym mis Ebrill gyda'r cyntaf erioed CS50 Expo, a fydd addasiad ar-lein o'n syniad y ffair lle bydd y miloedd o fyfyrwyr i gyd yn cael eu gwahodd i gyflwyno 1 - 2-funud fideo, naill ai screencast eu prosiect terfynol neu fideo ohonynt yn chwifio hello a siarad am eu prosiect a demoing iddo, lawer fel eich rhagflaenwyr wedi ei wneud yma ar y campws yn y ffair, fel, erbyn diwedd semester, y gobaith yw cael arddangosfa fyd-eang o brosiectau y myfyrwyr CS50x 'terfynol, yn debyg iawn yr hyn sy'n eich disgwyl ym mis Rhagfyr eleni yma ar y campws. Felly mwy am hynny yn y misoedd i ddod. Gyda 100,000 o fyfyrwyr, fodd bynnag, daw angen am MD ychydig mwy. O ystyried eich bod guys yn torri y llwybr yma a chymryd CS50 sawl wythnos cyn rhyddhau deunydd hwn i'r Folks ar EDX, sylweddoli byddem wrth ein bodd i gynnwys cymaint o'n myfyrwyr hunain ag y bo modd yn y fenter hon, yn ystod y semester yn ogystal â'r gaeaf a gwanwyn hwn sydd i ddod. Felly os hoffech chi gymryd rhan mewn CS50x, yn arbennig yn ymuno i mewn ar CS50x Trafod, y fersiwn EDX o CS50 Trafod, y mae llawer ohonoch wedi bod yn defnyddio ar y campws, y bwrdd bwletin ar-lein, croeso i chi wneud pen i'r URL, rhowch wybod i ni pwy ydych chi, oherwydd byddem wrth ein bodd i adeiladu tîm o fyfyrwyr a staff fel ei gilydd a chyfadran ar y campws sydd ond yn chwarae ar hyd a helpu allan. A phan fyddant yn gweld cwestiwn sy'n gyfarwydd iddynt, byddwch yn clywed yn fyfyriwr yn sôn am ryw nam yn rhywle allan yn rhyw wlad ar y Rhyngrwyd, ac sy'n taro cloch oherwydd eich bod hefyd wedi bod un mater yn eich d-hall beth amser yn ôl, gobeithio, yna gallwch chi yn cyd-daro i mewn a rhannu eich profiad eich hun. Felly, os gwelwch yn dda peidiwch cymryd rhan os hoffech chi. Cyrsiau gwyddoniaeth cyfrifiadurol yn Harvard gael ychydig o draddodiad, CS50 yn eu plith, o gael rhywfaint o ddillad, dillad, y gellir eu gwisgo gyda balchder ar ddiwedd y semester, gan ddweud yn eithaf falch eich bod yn gorffen CS50 ac a gymerodd CS50 ac yn y blaen, ac rydym bob amser yn ceisio i gynnwys myfyrwyr yn y broses hon gymaint ag y bo modd, lle rydym yn gwahodd, tua'r adeg hon y semester, bydd myfyrwyr i gyflwyno cynlluniau gan ddefnyddio Photoshop, neu beth bynnag offeryn o ddewis yr hoffech ei ddefnyddio os ydych yn ddylunydd, i gyflwyno cynlluniau ar gyfer crysau-T a chrysau chwys a ymbarel a bandanas bach ar gyfer cŵn gennym bellach ac yn y blaen. Ac mae popeth yn hynny - yr enillwyr bob blwyddyn yn cael eu harddangos yna ar wefan y cwrs yn store.cs50.net. Mae popeth yn cael ei werthu ar gost yno, ond mae'r wefan yn unig yn rhedeg ei hun ac yn caniatáu pobl i ddewis y lliwiau a dyluniadau maent yn eu hoffi. Felly, yr wyf yn meddwl y byddwn ni ond yn rhannu rhai o ddyluniadau y llynedd a oedd ar y wefan ar wahân yr un yma, sydd yn draddodiad blynyddol. "Bob dydd rwy'n SEG Faultn" oedd un o'r cyflwyniadau flwyddyn ddiwethaf, sydd yn dal ar gael yno ar gyfer cyn-fyfyrwyr. Cawsom yr un yma, "CS50, Sefydlwyd 1989." Un o'n Bowdens, Rob, roedd yn boblogaidd iawn y llynedd. "Tîm Bowden" ei eni, y cynllun hwn ei gyflwyno, ymhlith y gwerthwyr gorau. Fel yr oedd yr un yma. Mae llawer o bobl wedi "Bowden Fever" yn ôl y cofnodion gwerthiant. Sylweddoli y gallai fod yn awr yn eich dyluniad yno, i fyny ar y Rhyngrwyd. Mwy o fanylion ar hyn yn y broblem nesaf yn gosod i ddod. Un dull mwy: eich bod wedi cael rhywfaint o amlygiad a gobeithio nawr rhywfaint o brofiad ymarferol â GDB, sydd, wrth gwrs, yn debugger ac yn caniatáu i chi drin eich rhaglen ar lefel weddol isel, yn gwneud pa fathau o bethau? Beth mae GDB gadael i chi ei wneud? Yeah? Rhowch i mi rhywbeth. [Ateb Myfyrwyr, annealladwy] Da. Camu i mewn i swyddogaeth, felly nid oes yn rhaid i deipio rhedeg ac mae ganddynt yr ergyd rhaglen drwy ei gyfanrwydd, argraffu pethau i'r allbwn safonol. Yn hytrach, gallwch gamu trwyddo fesul llinell, naill ai deipio nesaf i fynd linell wrth linell wrth linell neu gam i ddeifio i mewn i swyddogaeth, fel arfer un yr ydych yn ysgrifennu. Beth arall y mae GDB gadael i chi ei wneud? Yeah? [Ateb Myfyrwyr, annealladwy] Argraffu newidynnau. Felly, os ydych am wneud introspection bach tu mewn i'ch rhaglen heb orfod troi at ysgrifennu datganiadau printf i gyd dros y lle, gallwch argraffu neu arddangos newidyn newidyn. Beth arall allwch chi ei wneud gyda debugger fel GDB? [Ateb Myfyrwyr, annealladwy] Yn union. Gallwch osod breakpoints; allwch ddweud gweithredu egwyl yn y prif swyddogaeth nac yn y swyddogaeth foo. Gallwch ddweud gweithredu toriad yn llinell 123. Ac breakpoints yn dechneg bwerus iawn oherwydd os oes gennych ymdeimlad cyffredinol o ble mae eich problem yn ôl pob tebyg yw, nid oes rhaid i wastraff amser camu trwy cyfanrwydd y rhaglen. Gallwch hanfod neidio i'r dde y fan a'r lle yn dechrau teipio - camu drwyddi â cham neu nesaf neu yn y blaen. Ond y ddalfa gyda rhywbeth fel GDB yw ei fod yn helpu i chi, y dynol, dod o hyd i'ch problemau a dod o hyd i'ch bugs. Nid yw o reidrwydd yn dod o hyd iddynt gymaint i chi. Felly, rydym yn cyflwyno y style50 diwrnod o'r blaen, sydd yn arf gorchymyn llinell fer yn sy'n ceisio stylize eich cod ychydig yn fwy lân na chi, y bobl, ei chael ei wneud. Ond, hefyd, mewn gwirionedd yn unig yn beth esthetig. Ond mae'n troi allan yna yr offeryn eraill o'r enw Valgrind sydd ychydig yn fwy dirgel i'w defnyddio. Mae'r allbwn yn atrociously cryptig ar yr olwg gyntaf. Ond mae'n rhyfeddol o ddefnyddiol, yn enwedig nawr ein bod ni'n ar y rhan o'r term lle rydych chi'n dechrau defnyddio malloc a dyrannu cof deinamig. Gall pethau fynd yn iawn, iawn o'i le yn gyflym. Oherwydd os byddwch yn anghofio i ryddhau eich cof, neu os ydych dereference rhywfaint o pwyntydd NULL, neu os ydych dereference rhywfaint o pwyntydd garbage, beth yw fel arfer y symptom bod y canlyniadau? SEG fai. A ydych yn cael y ffeil ganolog i rai nifer o kilobytes neu megabeit sy'n cynrychioli cyflwr cof eich rhaglen pan chwalodd, ond mae eich rhaglen yn y pen draw SEG diffygion, wall, sy'n golygu rhywbeth drwg yn digwydd bron bob amser yn gysylltiedig at gamgymeriad cof-gysylltiedig a wnaethoch yn rhywle. Felly Valgrind yn eich helpu i ddod o hyd i bethau fel hyn. Mae'n arf eich bod yn rhedeg, fel GDB, ar ôl i chi wedi llunio eich rhaglen, ond yn hytrach na rhedeg eich rhaglen yn uniongyrchol, rydych yn rhedeg Valgrind ac rydych yn trosglwyddo iddo eich rhaglen, yn union fel chi ei wneud gyda GDB. Yn awr, y defnydd, er mwyn cael y math gorau o allbwn, yn ychydig yn hir, felly iawn yno ar ben y sgrin byddwch yn gweld Valgrind-v. "-V" bron yn ddieithriad yn golygu verbose pan fyddwch yn defnyddio rhaglenni ar gyfrifiadur Linux. Felly, mae'n golygu boeri allan mwy o ddata nag y gallai yn ddiofyn. "- Gollwng-wirio = llawn." Mae hyn yn unig yw dweud siec am yr holl ollyngiadau cof posibl, camgymeriadau y gallai fy mod wedi gwneud. Mae hyn, hefyd, yn batrwm cyffredin gyda rhaglenni Linux. Yn gyffredinol, os oes gennych ymresymiad llinell orchymyn hynny'n "newid", bod i fod i newid ymddygiad y rhaglen, ac mae'n un llythyren, mae'n-v, ond os nad yw newid, dim ond drwy ddyluniad y rhaglennydd, yn air llawn neu gyfres o eiriau, y gorchymyn ymresymiad llinell yn dechrau gyda -. Yn unig yw'r rhain confensiynau dynol, ond byddwch yn eu gweld yn gynyddol. Ac yna, yn olaf, "a.out" yw'r enw mympwyol ar gyfer y rhaglen yn yr enghraifft hon. A dyma rhywfaint o allbwn cynrychioliadol. Cyn i ni edrych ar yr hyn a allai hynny ei olygu, gadewch i mi fynd drosodd i snippet o god dros yma. A gadewch i mi symud y tu allan o'r ffordd, yn dod yn fuan, a gadewch i ni edrych ar memory.c, sef yr enghraifft hon byr yma. Felly, yn y rhaglen hon, gadewch i mi ganolbwyntio ar y swyddogaethau a chwestiynau. Mae gennym swyddogaeth prif sy'n galw swyddogaeth, f, ac yna beth mae f myned rhagof i wneuthur, yn Saesneg ychydig yn dechnegol? Beth mae f symud ymlaen i wneud? Beth am Byddaf yn dechrau gyda llinell 20, ac nad yw lleoliad y seren yw o bwys, ond byddaf yn unig fod yn gyson yma gyda darlith diwethaf. Beth yw llinell 20 yn i ni? Ar yr ochr chwith. Byddwn yn torri i lawr ymhellach. Int * x: beth mae hynny'n ei wneud? Iawn. Mae'n datgan pwyntydd, a nawr gadewch i ni fod hyd yn oed yn fwy technegol. Beth mae'n ei olygu, yn concretely, i ddatgan pwyntydd? Rhywun arall? Yeah? [Ateb Myfyrwyr, annealladwy] Rhy bell. Felly, rydych chi'n darllen ar yr ochr dde-law yr arwydd cyfartal. Gadewch i ni ganolbwyntio yn unig ar y chwith, yn union ar int * x. Hyn yn "datgan" pwyntydd, ond yn awr gadewch i ni neidio yn ddyfnach i diffiniad hwnnw. Beth mae hynny'n ei concretely, yn dechnegol yn ei olygu? Yeah? [Ateb Myfyrwyr, annealladwy] Iawn. Mae'n paratoi i arbed gyfeiriad yn y cof. Da. A gadewch i ni gymryd hyn un cam ymhellach; mae'n datgan amrywiol, x, dyna 32 catiau. Ac yr wyf yn gwybod ei fod yn 32 catiau oherwydd -? Dyw hi ddim oherwydd ei fod yn int, am ei fod yn pwyntydd yn yr achos hwn. Gyd-ddigwyddiad ei fod yn yr un peth gyda int, ond y ffaith fod yna seren mae golygu bod hwn yn pwyntydd ac yn y peiriant, fel gyda llawer o gyfrifiaduron, ond nid pob un, awgrymiadau 32 ddarnau. Ar fwy caledwedd modern fel y Macs diweddaraf, cyfrifiaduron diweddaraf, a allai fod gennych 64-bit awgrymiadau, ond yn y peiriant, y pethau hyn 32 ddarnau. Felly, byddwn yn safoni ar hynny. Mwy concretely, mae'r stori yn mynd fel a ganlyn: Rydym yn "datgan" pwyntydd, beth mae hynny'n ei olygu? Rydym yn paratoi i storio cyfeiriad cof. Beth mae hynny'n ei olygu? Rydym yn creu x elwir yn newidyn sy'n cymryd 32 catiau a fydd yn fuan storio cyfeiriad yn gyfanrif. A dyna mae'n debyg tua mor fanwl ag y gallwn ei gael. Mae'n iawn symud ymlaen i symleiddio'r byd a dim ond dweud datgan pwyntydd o'r enw x. Datgan pwyntydd, ond yn sylweddoli ac yn deall beth sy'n digwydd mewn gwirionedd ar hyd yn oed dim ond y rhai cymeriadau ychydig. Yn awr, hyn yn un 'bron yn ychydig yn haws, hyd yn oed er ei fod yn fynegiant hirach. Felly beth mae hyn yn ei wneud, sydd wedi tynnu sylw at awr: "malloc (10 * sizeof (canolradd));" Ie? [Ateb Myfyrwyr, annealladwy] Da. A byddaf yn mynd ag ef yno. Mae'n dyrannu darn o gof am ddeng gyfanrifau. Ac yn awr gadewch i ni deifio mewn ychydig dyfnach, mae'n dyrannu cyfran o gof am ddeng gyfanrifau. Beth yw malloc yna dychwelyd? Y cyfeiriad y darn, neu, yn fwy concretely, cyfeiriad y beit gyntaf y darn. Sut felly ydw i, y rhaglennydd, i wybod ble y darn yn dod i ben cof? Rwy'n gwybod ei bod yn cydgyffwrdd. Malloc, drwy ddiffiniad, yn rhoi i chi darn cyffiniol o gof. Dim bylchau ynddo. Mae gennych fynediad i bob beit yn y darn, gefn wrth gefn wrth gefn, ond sut ydw i'n gwybod ble ddiwedd y darn o gof yw? Pan fyddwch yn defnyddio malloc? [Ateb Myfyrwyr, annealladwy] Da. Nid ydych yn ei wneud. Mae'n rhaid i chi gofio. Rhaid i mi gofio fy mod yn defnyddio'r gwerth 10, ac nid wyf yn hyd yn oed yn ymddangos i wedi gwneud hynny yma. Ond mae'r cyfrifoldeb yn gyfan gwbl ar mi. Strlen, yr ydym wedi dod yn ychydig yn ddibynnol ar gyfer llinynnau, yn gweithio yn unig oherwydd y confensiwn hwn o gael \ 0 neu y cymeriad NUL arbennig, NUL, ar ddiwedd y llinyn. Nid yw hynny'n dal am ychydig ddarnau mympwyol o gof. Mae i fyny i chi. Felly llinell 20, yna, yn dyrannu cyfran o gof sy'n gallu storio 10 cyfanrifau, ac mae'n storio cyfeiriad y beit 1 y darn o gof yn y newidyn x a elwir yn. Ergo, sy'n rhoi syniad. Felly llinell 21, yn anffodus, roedd camgymeriad. Ond yn gyntaf, beth y mae'n ei wneud? Mae'n dweud siop ar leoliad 10, 0 mynegeio, o darn o gof a elwir yn y 0 x gwerth. Felly, yn sylwi ar ychydig o bethau yn mynd ymlaen. Er bod x yn pwyntydd, yn cofio o'r cwpl o wythnosau yn ôl y gallwch barhau i ddefnyddio'r nodiant sgwâr array-arddull braced. Oherwydd dyna mewn gwirionedd law-fer nodiant ar gyfer y rhifyddeg pwyntydd yn fwy cryptic-edrych. lle y byddem yn gwneud rhywbeth fel hyn: Cymerwch y x cyfeiriad, yn symud 10 man drosodd, wedyn yn mynd yno i ba bynnag gyfeiriad yn cael ei storio yn y lleoliad hwnnw. Ond a dweud y gwir, mae hyn yn erchyll i ddarllen a chael gyfforddus ag ef. Felly, yn y byd fel arfer yn defnyddio y cromfachau sgwâr yn unig oherwydd ei fod gymaint yn fwy dynol-gyfeillgar i ddarllen. Ond dyna beth sy'n wir yn mynd ymlaen o dan y cwfl; x Nid yw cyfeiriad, amrywiaeth, fel y cyfryw. Felly, mae hyn yn storio 0 ar leoliad 10 yn x. Pam mae hyn yn ddrwg? Yeah? [Ateb Myfyrwyr, annealladwy] Yn union. Byddwn ond yn dyrannu 10 ints, ond rydym yn cyfrif o 0 wrth raglennu yn C, felly mae gennych fynediad i 0 10 1 2 3 4 5 6 7 8 9, ond peidio. Felly naill ai'r rhaglen yn mynd i fai seg neu nid yw'n. Ond dydyn ni ddim yn gwybod, mae hyn yn fath o ymddygiad nondeterministic. Mae'n dibynnu ar p'un a ydym yn cael lwcus. Os yw'n troi allan nad yw'r system weithredu oes ots os byddaf yn defnyddio y beit ychwanegol, er nad yw wedi rhoi i mi, efallai na fydd fy rhaglen damwain. Mae'n amrwd, mae'n buggy, ond efallai nad ydych yn gweld y symptom, neu efallai y byddwch yn ei weld unwaith yn unig mewn blwc. Ond y gwir amdani yw bod y nam yn, mewn gwirionedd, yno. Ac mae'n wir yn anodd os ydych wedi ysgrifennu rhaglen yr ydych am ei fod yn gywir, eich bod wedi gwerthu y rhaglen fod pobl yn defnyddio bod pob siwrnai mewn blwc damweiniau oherwydd, wrth gwrs, nid yw hyn yn dda. Yn wir, os oes gennych ffôn Android neu iPhone ac rydych yn llwytho i lawr apps y dyddiau hyn, os ydych chi erioed wedi cael app yn unig roi'r gorau iddi, yn sydyn yn diflannu, sef bron bob amser o ganlyniad i ryw fater y cof-gysylltiedig, lle y rhaglennydd sgriwio i fyny ac i dereferenced pwyntydd ei fod ef neu na ddylai hi gael, a chanlyniad iOS neu Android ydy at jyst ladd y rhaglen yn gyfan gwbl yn hytrach nag ymddygiad risg undefined neu ryw fath o gyfaddawd diogelwch. Mae un bug eraill yn y rhaglen ar wahân yr un yma. Beth arall ydw i wedi sgriwio i fyny yn y rhaglen hon? Nid wyf wedi ymarfer yr hyn yr wyf wedi pregethu. Yeah? [Ateb Myfyrwyr, annealladwy] Da. Nid wyf wedi rhyddhau y cof. Felly, y rheol y fawd yn awr rhaid iddo fod ar unrhyw adeg rydych yn galw malloc, rhaid i chi ffonio am ddim pan fyddwch yn gwneud defnyddio'r cof. Yn awr, byddai pan rwyf eisiau i ryddhau y cof? Yn ôl pob tebyg, gan dybio y llinell gyntaf yn gywir, byddai arnaf eisiau ei wneud yma. Gan nad allwn, er enghraifft, yn ei wneud i lawr yma. Pam? Yn unig allan o gwmpas. Felly, er ein bod yn sôn am awgrymiadau, mae hwn yn wythnos 2 neu 3 mater, lle mae x yn unig o ran cwmpas y tu mewn i'r braces cyrliog lle cafodd ei ddatgan. Felly, ni allwch bendant rhyddhau yno. Fy unig gyfle i ryddhau ei fod yn fras ar ôl llinell 21. Mae hon yn rhaglen weddol syml; roedd yn eithaf hawdd ar ôl i chi fath o lapio eich meddwl o gwmpas yr hyn y mae'r rhaglen yn ei wneud, lle mae'r camgymeriadau yn. A hyd yn oed os nad ydych yn ei weld ar y cyntaf, gobeithio ei fod yn ychydig yn amlwg yn awr bod y camgymeriadau yn cael eu 'n bert haws datrys y problemau a gwneud yn hawdd. Ond pan fydd rhaglen yn fwy na 12 llinellau hir, mae'n 50 llinell o hyd, 100 llinellau hir, cerdded drwy eich llinell wrth linell cod, gan feddwl drwyddo yn rhesymegol, yn bosibl ond nid yn arbennig o hwyl i'w gwneud, yn gyson yn chwilio am bryfed, ac mae hefyd yn anodd i'w wneud, a dyna pam yn offeryn fel Valgrind yn bodoli. Gadewch i mi fynd yn ei flaen ac yn gwneud hyn: gadewch i mi agor fy ffenest terfynell, a gadewch i mi nid yn unig yn rhedeg cof, oherwydd cof yn ymddangos i fod yn iawn. Im 'yn cael lwcus. Mynd at y beit ychwanegol ar ddiwedd y rhesi nid yw'n ymddangos i fod gormod o broblemau. Ond gadewch i mi, serch hynny, yn gwneud, gwiriad pwyll a dim ond olygu i wirio a yw hyn mewn gwirionedd yn gywir. Felly, gadewch i ni wneud valgrind-v - gollwng-wirio = llawn, ac yna enw'r rhaglen yn yr achos hwn nid yw cof, a.out. Felly, gadewch i mi fynd ymlaen a gwneud hyn. Hit Enter. Annwyl Dduw. Mae hyn yn ei allbwn, a dyma'r hyn y crybwyllais yn gynharach. Ond, os ydych yn dysgu darllen drwy bob un o'r lol yma, rhan fwyaf o hyn yn unig yw cynnyrch diagnostig nad ddim yn bod ddiddorol. Beth yw eich llygad yn awyddus iawn i fod yn edrych amdano yw unrhyw sôn am wall neu yn annilys. Geiriau sy'n awgrymu problemau. Ac yn wir, gadewch i ni weld beth sy'n mynd o'i le i lawr yma. Mae gen i grynodeb o ryw fath, "a ddefnyddir yn ymadael:. 40 bytes mewn 1 bloc" Dydw i ddim yn siŵr iawn beth yw bloc eto, ond 40 bytes mewn gwirionedd yn teimlo fel y gallwn i chyfrif i maes ble mae hynny'n dod. 40 bytes. Pam yn 40 bytes cael eu defnyddio ar ymadael? Ac yn fwy penodol, os ydym yn sgrolio i lawr yma, pam fy mod wedi bendant colli 40 bytes? Yeah? [Ateb Myfyrwyr, annealladwy] Perfect. Yeah, yn union. Roedd deg cyfanrifau, a phob un o'r rheiny yw faint o 4, neu 32 darnau, felly rydw i wedi colli yn union 40 bytes oherwydd, fel y cynigiwyd, nid wyf wedi galw am ddim. Dyna un bug, ac yn awr gad i ni edrych i lawr ychydig ymhellach a gweld nesaf at hyn, "Annilys ysgrifennu maint 4." Nawr beth yw hwn? Mae'r cyfeiriad yn cael ei fynegi nodiant sylfaenol beth, mae'n debyg? Mae hyn yn hecsadegol, ac unrhyw tro y byddwch yn gweld nifer dechrau gyda 0x, mae'n golygu hecsadegol, a gwnaethom hynny mewn ffordd yn ôl, yr wyf yn meddwl, pset 0 yn adran o gwestiynau, a oedd dim ond i wneud ymarfer warmup, trosi degol i'r hecs i ddeuaidd ac yn y blaen. Hecsadegol, dim ond drwy gonfensiwn dynol, yn cael ei ddefnyddio fel arfer i gynrychioli awgrymiadau neu, yn fwy cyffredinol, yn mynd i'r afael. Mae'n dim ond confensiwn, oherwydd ei fod ychydig yn haws i'w ddarllen, mae'n ychydig yn fwy cryno na rhywbeth fel degol, ac deuaidd yn ddiwerth ar gyfer rhan fwyaf o bobl i'w defnyddio. Felly, yn awr beth yw ystyr hyn? Wel, mae'n edrych fel mae 'na ysgrifennu annilys maint 4 ar linell 21 o memory.c. Felly, gadewch i ni fynd yn ôl i linell 21, ac yn wir, dyma yw bod ysgrifennu annilys. Felly nid Valgrind yn mynd yn llwyr dal fy llaw a dweud wrthyf beth yw'r ateb yw, ond mae'n canfod fy mod yn gwneud yn ysgrifennu annilys. Rwy'n cyffwrdd 4 bytes na ddylwn fod, ac i bob golwg mae hynny oherwydd, fel y nodwyd gennych, yr wyf i'n ei wneud [10] yn lle [9] maximally neu [0] neu rywbeth yn y canol. Gyda Valgrind, yn sylweddoli unrhyw tro y byddwch yn yn awr yn ysgrifennu rhaglen sy'n defnyddio pwyntyddion a defnyddio cof, a malloc yn fwy penodol, sicr yn mynd i'r arfer o redeg yma o hyd ond yn hawdd iawn copïo a gludo gorchymyn Valgrind i weld os oes rhai camgymeriadau i mewn 'na. A bydd yn cael ei llethol bob tro y byddwch yn gweld y cynnyrch, ond dim ond gramadegu drwy weledol yr holl allbwn a gweld os ydych yn gweld yn sôn o wallau neu rybuddion neu annilys neu ar goll. Unrhyw eiriau sy'n swnio'n fel chi sgriwio i fyny yn rhywle. Felly sylweddoli bod yn offeryn newydd yn eich pecyn cymorth. Nawr ar ddydd Llun, cawsom criw cyfan o Folks dod i fyny yma ac maent yn cynrychioli'r syniad o restr cysylltiedig. Ac rydym yn cyflwyno rhestr sy'n gysylltiedig fel ateb i ba broblem? Yeah? [Ateb Myfyrwyr, annealladwy] Da. Ni all araeau gael cof ychwanegu atynt. Os byddwch yn dyrannu amrywiaeth o maint 10, dyna i gyd a gewch. Gallwch ffonio swyddogaeth fel realloc os ydych yn dechrau o'r enw malloc, a gall geisio tyfu ar y rhesi os oes lle tuag at y diwedd nad oes neb arall yn ei ddefnyddio, ac os nad oes, bydd yn unig ddod o hyd i ddarn mwy rhywle arall. Ond yna bydd yn anfon copi o bob o'r rhai bytes i'r casgliad newydd. Mae hyn yn swnio fel ateb gywir iawn. Pam mae hyn yn anneniadol? Yr wyf yn golygu ei fod yn gweithio, mae pobl wedi datrys y broblem hon. Pam mae angen i ni ddatrys ddydd Llun gyda rhestrau cysylltiedig? Yeah? [Ateb Myfyrwyr, annealladwy] Gallai gymryd amser hir. Yn wir, unrhyw adeg ydych yn ffonio malloc neu realloc neu calloc, sydd eto un arall, unrhyw adeg i chi, y rhaglen, yn siarad â'r system weithredu, rydych yn tueddu i arafu'r rhaglen i lawr. Ac os ydych chi'n gwneud y mathau hyn o bethau mewn dolenni, ydych wirioneddol yn arafu pethau i lawr. Nid ydych yn mynd i sylwi ar hyn ar gyfer y symlaf o "helo byd" rhaglenni fath, ond mewn rhaglenni llawer mwy, yn gofyn i'r system weithredu eto ac eto ar gyfer cof neu roi yn ôl dro ar ôl tro yn tueddu i beidio â bod yn beth da. Byd Gwaith, 'i' jyst fath o ddeallusol - mae'n wastraff llwyr o amser. Pam dyrannu cof mwy a mwy o, risg copïo popeth yn y casgliad newydd, os oes gennych ddewis arall sy'n gadael i chi dyrannu cof yn unig cymaint ag y byddwch ei angen mewn gwirionedd? Felly, mae pwyntiau cadarnhaol a negyddol i mewn yma. Un o'r pwyntiau cadarnhaol yn awr yw bod gennym egni. Nid yw'n fater lle y darnau o gof yw bod yn rhad ac am ddim, Gallaf ddidoli o greu'r friwsion bara trwy awgrymiadau i linyn fy rhestr cysylltiedig cyfan at ei gilydd. Ond yr wyf yn talu o leiaf un pris. Beth sydd rhaid i mi roi'r gorau i gael rhestrau cysylltiedig? Yeah? [Ateb Myfyrwyr, annealladwy] Da. Mae angen mwy o gof. Nawr mae angen lle ar gyfer hyn awgrymiadau, ac yn achos y rhestr hon super cysylltiedig syml nad yw ond yn ceisio i storio cyfanrifau, sydd 4 bytes, rydym yn dal i ddweud yn dda, pwyntydd yw 4 bytes, felly rwyf bellach wedi dyblu yn llythrennol faint o gof ei angen arnaf yn unig i storio y rhestr hon. Ond unwaith eto, mae hwn yn tradeoff cyson mewn gwyddoniaeth gyfrifiadurol rhwng amser a gofod a datblygu, ymdrech ac adnoddau eraill. Beth arall anfantais o ddefnyddio rhestr sy'n gysylltiedig? Yeah? [Ateb Myfyrwyr, annealladwy] Da. Nid yw mor hawdd i gael mynediad. Gallwn bellach trosoledd wythnos 0 egwyddorion megis rhannu a gorchfygu. Ac yn fwy penodol, chwiliad deuaidd. Oherwydd hyd yn oed er ein bod yn fodau dynol gallu gweld yn fras lle mae canol y rhestr hon, y cyfrifiadur yn unig yn gwybod bod y rhestr hon cysylltiedig yn dechrau yn y cyfeiriad a elwir yn gyntaf. A dyna 0x123 neu rywbeth fel 'na. A gall yr unig ffordd y rhaglen yn dod o hyd i'r elfen canol yw mewn gwirionedd yn chwilio'r rhestr gyfan. Ac hyd yn oed wedyn, yn llythrennol rhaid i chwilio'r rhestr gyfan oherwydd hyd yn oed ar ôl i chi gyrraedd yr elfen ganol trwy ddilyn yr awgrymiadau, chi, y rhaglen, yn cael unrhyw syniad am faint y rhestr hon, o bosibl, nes i chi gyrraedd y diwedd, a sut ydych chi'n gwybod programmatically eich bod ar ddiwedd y rhestr sy'n gysylltiedig? Mae yna pwyntydd NULL arbennig, felly unwaith eto, mae confensiwn. Yn hytrach na defnyddio'r pwyntydd, nid ydym yn sicr am iddo fod rhywfaint o werth garbage pwyntio oddi ar y llwyfan yn rhywle, rydym am iddo fod â llaw i lawr, NULL, er mwyn i ni gael y derfynfa yn y strwythur data felly rydym yn gwybod o ble mae'n dod i ben. Beth os ydym am i drin hyn? Rydym yn gwneud y rhan fwyaf o hyn yn weledol, ac â phobl, ond beth os ydym am wneud yn mewnosod? Felly y rhestr wreiddiol oedd 9, 17, 20, 22, 29, 34. Beth os ydym wedyn am ofod ar gyfer nifer malloc 55, yn nod ar ei gyfer, ac yna rydym am i fewnosod 55 yn y rhestr yn union fel y gwnaethom ar ddydd Llun? Sut rydym yn gwneud hyn? Wel, Anita ddaeth i fyny ac mae hi yn y bôn cerdded ar y rhestr. Dechreuodd ar yr elfen gyntaf, yna bydd y nesaf, a'r nesaf, a'r nesaf, a'r nesaf, a'r nesaf. Yn olaf daro yr ochr chwith yr holl ffordd i lawr a gwireddu oh, mae hyn yn NULL. Felly, trin pwyntydd beth oedd angen ei wneud? Roedd y person a oedd ar y diwedd, rhif 34, sydd ei angen ei law chwith a godir i bwynt yn 55, 55 angen eu braich chwith yn pwyntio i lawr i fod yn newydd NULL Terminator. Done. Eithaf hawdd i fewnosod 55 i mewn i restr datrys. A sut gallai hyn edrych? Gadewch i mi fynd yn ei flaen ac agor rhai enghraifft cod yma. 'N annhymerus' agor i fyny gedit, a gadewch i mi agor dwy ffeil yn gyntaf. Mae un yn list1.h, a gadewch i mi dim ond atgoffa mai hwn oedd y darn o god ein bod yn eu defnyddio i gynrychioli nod. Mae nod wedi ddau yn int o'r enw n, a elwir yn pwyntydd nesaf mai dim ond yn cyfeirio at y peth nesaf yn y rhestr. Mae hynny bellach yn a. Ffeil h. Pam? Mae confensiwn hwn, ac nid ydym wedi manteisio ar hyn yn swm enfawr ein hunain, ond y person a ysgrifennodd swyddogaethau printf ac eraill rhoi fel rhodd i'r byd holl swyddogaethau hynny drwy ysgrifennu ffeil o'r enw stdio.h. Ac yna mae string.h, ac yna mae map.h, ac mae hyn i gyd ffeil h y gallech fod wedi gweld neu eu defnyddio yn ystod y tymor a ysgrifennwyd gan bobl eraill. Fel arfer yn y. Ffeiliau h yn unig bethau fel typedefs neu ddatganiadau o fathau arfer neu ddatganiadau o cysonion. Nid ydych yn rhoi gweithrediadau swyddogaethau 'mewn ffeiliau header. Yn eich rhoi chi, yn hytrach, dim ond eu prototeipiau. Rydych yn rhoi pethau yr hoffech ei rhannu gyda'r byd beth sydd ei angen arnynt er mwyn llunio eu cod. Felly, dim ond i gael i mewn i'r arfer, rydym yn penderfynu gwneud yr un peth. Does dim llawer yn list1.h, ond rydym wedi rhoi rhywbeth a allai fod o ddiddordeb i bobl yn y byd sydd am ddefnyddio ein gweithrediad rhestr cysylltiedig. Yn awr, yn list1.c, ni fyddaf yn mynd trwy'r holl beth oherwydd ei fod braidd yn hir, y rhaglen hon, ond gadewch i ni redeg go iawn yn gyflym wrth yr anogwr. Gadewch i mi lunio Rhestr1, gadewch i mi wedyn yn rhedeg Rhestr1, a'r hyn y byddwch yn gweld ei rydym wedi efelychu Rhaglen fechan syml yma mae hynny'n mynd i fy ngalluogi i ychwanegu a dileu rhifau i restr. Felly, gadewch i mi fynd yn ei flaen a theipiwch 3 ar gyfer y ddewislen 3. Wyf i am osod y rhif - gadewch i ni wneud y rhif cyntaf, a oedd yn 9, ac erbyn hyn rwy'n gwybod y rhestr bellach yn 9. Gadewch i mi fynd yn ei flaen ac yn gwneud rhywbeth arall fewnosod, felly yr wyf gyrraedd 3 opsiwn ddewislen. Pa rif ydw i am ei fewnosod? 17. Enter. A byddaf yn gwneud dim ond un yn fwy. Gadewch i mi rhowch y rhif 22. Felly, mae gennym y dechreuad y rhestr cysylltiedig a oedd gennym yn ffurf sleidiau funud yn ôl. Sut mae hyn yn gosod mewn gwirionedd yn digwydd? Yn wir, mae 22 yn awr ar ddiwedd y rhestr. Felly, yr ydym yn dweud stori ar y llwyfan ar ddydd Llun a recapped unig yn awr Mae'n rhaid i mewn gwirionedd yn digwydd yn y cod. Gadewch i ni edrych. Gadewch i mi sgroliwch i lawr yn y ffeil hon. Byddwn yn fach dros rai o'r swyddogaethau, ond byddwn yn mynd i lawr i, dyweder, y swyddogaeth rhowch. Gadewch i ni weld sut yr ydym yn mynd ati i fewnosod nod newydd i'r rhestr hon cysylltiedig. Ble mae'r rhestr datgan? Wel, gadewch i sgrolio holl ffordd i fyny ar y brig, ac yn sylwi bod fy rhestr cysylltiedig yn cael ei datgan yn ei hanfod fel pwyntydd sengl sy'n dechrau NULL. Felly rwy'n defnyddio newidyn byd-eang yma, sydd yn gyffredinol rydym wedi pregethu yn erbyn oherwydd ei fod yn gwneud eich cod yn flêr ychydig i gynnal, mae'n fath o ddiog, fel arfer, ond nid yw'n ddiog ac nid ei fod yn anghywir ac nid yw'n ddrwg os pwrpas eich rhaglen unig mewn bywyd yw i efelychu un rhestr cysylltiedig. Sef yr union beth rydym yn ei wneud. Felly, yn hytrach na ddatgan hyn yn y brif ac yna rhaid i ni ei drosglwyddo bob swyddogaeth rydym wedi ysgrifennu yn y rhaglen hon, rydym yn hytrach yn sylweddoli oh, gadewch i ni dim ond yn ei gwneud yn fyd-eang oherwydd holl bwrpas y rhaglen hon yw dangos un a dim ond un rhestr cysylltiedig. Felly sy'n teimlo'n iawn. Dyma fy prototeipiau, ac ni fyddwn yn mynd drwy'r rhain i gyd, ond yr wyf yn ysgrifennu, swyddogaeth dileu swyddogaeth ddod o hyd i, swyddogaeth mewnosoder, a swyddogaeth daith. Ond gadewch i ni nawr fynd yn ôl i lawr i'r swyddogaeth nodwch a gweld sut mae hyn yn un yn gweithio yma. Mewnosod ar-lein - yma rydym yn mynd. Mewnosod. Felly nid yw'n cymryd unrhyw ddadleuon, oherwydd ein bod ni'n mynd i ofyn i y tu mewn defnyddiwr y swyddogaeth hon ar gyfer y rhif y maent am i fewnosod. Ond yn gyntaf, rydym yn paratoi i roi rhywfaint o le. Mae hyn yn fath o gopi a gludo o'r enghraifft arall. Yn yr achos hwn, rydym yn dyrannu int; y tro hwn rydym yn ddyrannu nod. Dwi ddim yn cofio faint o bytes yn nod yw, ond mae hynny'n iawn. Gall Sizeof ffigur fod allan i mi. A pham ydw i'n gwirio NULL yn unol 120? Beth allai fynd o'i le yn unol 119? Yeah? [Ateb Myfyrwyr, annealladwy] Da. Gallai Dim ond yn achos yr wyf wedi gofyn am lawer o gof lawer neu nad yw rhywbeth yn anghywir a bod y system weithredu oes bytes ddigon i roi i mi, felly mae'n arwydd cymaint drwy ddychwelyd NULL, ac os nad wyf yn gwirio ar gyfer y a Fi jyst blindly mynd ymlaen i ddefnyddio'r cyfeiriad a gyfyd, gallai fod yn null. Gallai fod rhywfaint o werth anhysbys, nid yn beth da oni bai fy mod - Ni fydd mewn gwirionedd yn werth anhysbys. Gallai fod yn NULL, felly nid wyf am i gam-drin ac risg dereferencing hynny. Os digwydd hynny, Fi jyst yn dychwelyd a byddwn yn esgus fel doeddwn i ddim yn mynd yn ôl unrhyw cof o gwbl. Fel arall, yr wyf yn dweud wrth y defnyddiwr rif imi ac i fewnosod, galwaf ein GetInt hen ffrind, ac yna mae hyn oedd y gystrawen newydd yr ydym cyflwyno ar ddydd Llun. 'Newptr-> n' yn golygu cymryd y cyfeiriad a roddwyd i chi gan malloc sy'n cynrychioli beit cyntaf o wrthrych nod newydd, ac yna mynd i'r cae o'r enw n. Mae cwestiwn trivia bach: Mae hyn yn cyfateb i'r hyn a llinell yn fwy cryptic o god? Sut arall yr wyf wedi ysgrifennu hyn? Eisiau cymryd stab? [Ateb Myfyrwyr, annealladwy] Da. Gan ddefnyddio'r n., Ond nid yw'n mor syml â hyn. Beth ydw i'n gyntaf bydd angen i ei wneud? [Ateb Myfyrwyr, annealladwy] Da. Angen i mi ei wneud * newptr.n. Felly, mae hyn yn ei ddweud pwyntydd newydd yn amlwg yn gyfeiriad. Pam? Oherwydd ei fod yn cael ei ddychwelyd gan malloc. Mae'r newptr * yn dweud "mynd yno," ac yna unwaith y byddwch chi yno, yna gallwch ddefnyddio'r mwy cyfarwydd. n, ond mae hyn dim ond yn edrych ychydig yn hyll, yn enwedig os ydym bodau dynol yn mynd i tynnu awgrymiadau gyda saethau drwy'r amser, y byd wedi safoni ar y saeth nodiant, sy'n gwneud yn union yr un peth. Felly, dim ond defnyddiwch y -> nodiant pan fydd y peth ar y chwith mae pwyntydd. Fel arall, os ei fod yn strwythur go iawn, defnyddiwch y n.. Ac yna mae hyn: Pam ydw i'n ymgychwyn newptr-> nesaf i NULL? Nid ydym eisiau llaw chwith yn hongian oddi ar y diwedd y cyfnod. Rydym am ei pwyntio yn syth i lawr, sy'n golygu diwedd y rhestr gallai fod ar hyn o nod, felly rydym yn well gwneud yn siŵr ei fod yn null. Ac, yn gyffredinol, ymgychwyn eich newidynnau neu eich aelodau data a structs i rywbeth yn unig arfer da. Dim ond gosod garbage yn bodoli ac yn parhau i fodoli yn gyffredinol yn cael chi mewn trafferth os byddwch yn anghofio i wneud rhywbeth yn nes ymlaen. Dyma ychydig o achosion. Mae hyn, eto, yw swyddogaeth mewnosod, a'r peth cyntaf i mi chwilio am yw os y newidyn a elwir yn gyntaf, y newidyn fyd-eang yn NULL, mae hynny'n golygu nid oes rhestr cysylltiedig. Nid ydym wedi gosod unrhyw rifau, felly mae'n ddibwys i fewnosod y nifer hwn ar hyn o bryd yn y rhestr, oherwydd mae'n perthyn ar ddechrau'r rhestr. Felly, mae hyn oedd pan Anita yn unig oedd yn sefyll i fyny yma yn unig, esgus nad oes neb arall i fyny yma ar y llwyfan nes i ni ddyrannu nod, yna gallai godi ei llaw am y tro cyntaf, os yw pawb arall wedi dod i fyny ar y llwyfan ar ei hôl hi ar ddydd Llun. Nawr yma, dyma ychydig o gwiriad lle mae'n rhaid i mi ddweud os yw gwerth y nod newydd o n yn nesaf, mae hynny'n golygu mynd i'r strwythur sy'n cael ei sylw at y newptr, felly dyma ni, yn mynd yno. Yna y saeth yn ei ddweud yn cael y cae nesaf, ac yna caiff y = yn ei ddweud roi pa werth yno? Y gwerth a oedd yn gyntaf; pa werth oedd yn gyntaf? Weinidog yn tynnu sylw at y nod yma, felly mae hynny'n golygu y dylai hyn bellach yn pwyntio at y nod. Mewn geiriau eraill, yr hyn yn edrych er ei fod yn llanast chwerthinllyd gyda fy llawysgrifen, beth syniad syml o ddim ond symud y saethau o amgylch yn cyfateb i cod gyda dim ond y leinin un. Storiwch beth sydd yn gyntaf yn y cae nesaf ac yna diweddaru beth gyntaf mewn gwirionedd yn ei. Gadewch i ni fynd yn ei flaen ac yn gyflym ymlaen drwy rai o hyn, ac yn edrych yn unig ar hyn gosod cynffon ar hyn o bryd. Gadewch i ni dybio cyrraedd y pwynt lle yr wyf yn canfod bod y cae nesaf o ryw nod yn null. Ac ar y pwynt hwn yn y stori, a manylion fy mod yn glossing dros yw fy mod wedi cyflwyno arall pwyntydd i fyny yma yn unol 142, pwyntydd rhagflaenydd. Yn y bôn, ar y pwynt hwn yn y stori, unwaith y bydd y rhestr yn cael hir, Yr wyf yn fath o angen i gerdded gyda dau bysedd oherwydd os byddaf yn mynd yn rhy bell, cofio yn un rhestr hir, ni allwch fynd yn ôl. Felly, y syniad o predptr yw fy mys ar y chwith, ac newptr - nid newptr. Arall pwyntydd sy'n dyma yw fy mys eraill, a Im 'jyst fath o gerdded y rhestr. Dyna pam sy'n bodoli. Ond gadewch i ni dim ond ystyried un o'r achosion symlach yma. Os faes y pwyntydd nesaf yn NULL, beth yw'r goblygiadau rhesymegol? Os ydych yn croesi y rhestr hon ac rydych yn taro pwyntydd NULL? Rydych chi ar ddiwedd y rhestr, ac felly mae'r cod wedyn i atodi elfen hon un ychwanegol yw y bydd rhyw fath o 'n athrylithgar gymryd y nod y mae ei pwyntydd nesaf NULL, felly mae hyn yn ar hyn o bryd NULL, a'i newid, fodd bynnag, i fod yn gyfeiriad y nod newydd. Felly, rydym yn unig yn tynnu mewn cod y saeth ein bod yn tynnu ar y llwyfan gan godi llaw rhywun chwith. A bod yr achos y byddaf yn chwifio fy nwylo ar gyfer yn awr, dim ond am fy mod yn meddwl ei fod yn hawdd mynd ar goll pan fyddwn yn ei wneud yn y math hwn o amgylchedd, yn gwirio ar gyfer gosod ar ganol y rhestr yn. Ond yn reddfol, beth sydd angen i ddigwydd os ydych am i chyfrif i maes lle mae rhai yn perthyn rhif yn y canol yn oes rhaid i chi gerdded gyda mwy nag un bys, yn fwy nag un pwyntydd, chyfrif i maes ble mae'n perthyn trwy wirio yw'r elfen Yr un bresennol, ac ar ôl i chi ddod o hyd y lle hwnnw, yna rhaid i chi wneud y math hwn o gêm cragen lle byddwch yn symud o gwmpas y pwyntiau yn ofalus iawn. Ac yr ateb hwnnw, os hoffech i reswm drwy hyn yn y cartref ar eich pen eich hun, boils i lawr yn unig i'r ddwy linell o god, ond bod trefn y llinellau hynny yn hynod bwysig. Oherwydd os ydych yn gollwng llaw rhywun ac yn codi rhywun arall yn y drefn anghywir, unwaith eto, gallech fod yn orphaning y rhestr. I grynhoi fwy gysyniadol, gosod yn y gynffon yn gymharol syml. Mae'r mewnosod yn y pen hefyd yn gymharol syml, ond mae angen i chi ddiweddaru pwyntydd ychwanegol y tro hwn i wasgu rhif 5 yn y rhestr yma, ac yna gosod yn y canol yn golygu ymdrech hyd yn oed mwy, i yn ofalus iawn rhowch y rhif 20 yn ei lleoliad cywir, sydd rhwng 17 a 22. Felly, mae angen i chi wneud rhywbeth fel cael y 20 nod newydd pwynt i 22, ac yna, pwyntydd y nod yn angen ei diweddaru ddiwethaf? Mae'n 17, i mewn gwirionedd yn mewnosod hynny. Felly eto, byddaf yn gohirio y cod gwirioneddol ar gyfer y gweithredu penodol. Ar yr olwg gyntaf, mae ychydig yn llethol, ond mae'n wirioneddol dim ond dolen ddiddiwedd mae hynny'n dolennu, dolennu, dolennu, dolennu, ac yn torri cyn gynted ag y byddwch yn taro y pwyntydd NULL, ac ar y pwynt y gallwch ei wneud gosod gofynnol. Mae hyn, felly, yw cod cynrychiolydd rhestr cysylltiedig gosod. Dyna oedd math o lawer, ac mae'n teimlo fel ein bod wedi datrys un broblem, ond rydym wedi cyflwyno un arall yn llwyr. A dweud y gwir, rydym wedi treulio holl amser ar fawr O a Ω a rhedeg amser, yn ceisio datrys problemau yn gynt, ac yma yr ydym yn cymryd cam mawr yn ôl, mae'n teimlo. Ac eto, os yw'r nod yw i storio data, mae'n teimlo fel y Greal Sanctaidd, fel y dywedwyd ar ddydd Llun y byddai, mewn gwirionedd yn i storio pethau yn syth. Yn wir, mae'n debyg ein bod yn gwneud yn rhoi rhestr sy'n gysylltiedig o'r neilltu am eiliad ac rydym yn lle hynny cyflwynwyd y syniad o dabl. A gadewch i ni dim ond meddwl am bwrdd ar gyfer hyn o bryd fel arae. Mae hyn yn amrywiaeth ac mae hyn yn achos yma mae tua 26 elfen, 0 drwy 25, ac yn debyg eich bod angen rhyw darn o storio ar gyfer enwau: Alice a Bob a Charlie ac yn y blaen. A ydych angen rhywfaint o strwythur data i storio yr enwau hynny. Wel, fe allech chi ddefnyddio rhywbeth fel rhestr cysylltiedig a gallech gerdded y rhestr mewnosod Alice cyn Bob a Charlie ar ôl Bob ac yn y blaen. Ac, yn wir, os ydych am weld cod fel 'na fel o'r neilltu, gwybod bod yn list2.h, rydym yn gwneud yn union hynny. Ni fyddwn yn mynd drwy y cod hwn, ond mae hyn yn amrywiad ar yr enghraifft gyntaf sy'n cyflwyno un strwythur arall yr ydym wedi gweld o'r blaen fyfyrwyr gelwir, ac yna beth yn union mae'n storio'r yn y rhestr cysylltiedig yn pwyntydd i strwythur i fyfyrwyr yn hytrach na cyfanrif ychydig yn syml, n. Felly, yn sylweddoli mae cod yno sy'n cynnwys llinynnau gwirioneddol, ond os bydd y gôl wrth law mewn gwirionedd yn awr yw mynd i'r afael â'r broblem effeithlonrwydd, ni fyddai'n braf pe ydym yn rhoi gwrthrych o'r enw Alice, rydym am ei rhoi yn y lleoliad cywir mewn strwythur data, mae'n teimlo fel petai braf iawn i ddim ond rhoi Alice, y mae ei enw yn dechrau gyda A, yn y lleoliad cyntaf. Ac Bob, y mae ei enw yn dechrau gyda B, yn yr ail leoliad. Gyda array, neu gadewch i ni ddechrau galw ei fod yn dabl, tabl hash ar hynny, y gallwn ei wneud yn union hynny. Os ydym yn cael enw fel Alice, llinyn fel Alice, ble yr ydych yn rhoi A-l-i-c-e? Rydym angen hueristic. Mae angen swyddogaeth i gymryd rhywfaint o fewnbwn fel Alice a dychwelyd ateb, "Rhowch Alice yn y lleoliad hwn." Ac mae hyn swyddogaeth, y blwch du, yn mynd i gael ei alw yn swyddogaeth hash. Mae swyddogaeth hash yn rhywbeth sy'n cymryd mewnbwn, fel "Alice", a ffurflenni i chi, fel arfer, y lleoliad rhifol mewn rhywfaint o strwythur data lle mae Alice yn perthyn. Yn yr achos hwn, dylai ein swyddogaeth hash fod yn gymharol syml. Dylai ein swyddogaeth hash yn dweud, os ydych yn cael "Alice", a ddylai cymeriad wyf yn poeni am? Mae'r un cyntaf. Felly, yr wyf yn edrych ar [0], ac yna yr wyf yn dweud os cymeriad [0] yn A, dychwelyd y rhif 0. Os yw'n B, yn dychwelyd 1. Os yw'n C, yn dychwelyd 2, ac yn y blaen. Byddai pob mynegai 0, ac yn caniatáu i mi i fewnosod Alice ac yna Bob ac yna Charlie ac yn y blaen i'r strwythur hwn data. Ond mae 'na broblem. Beth os yw Anita yn dod ar hyd eto? Ble rydym yn rhoi Anita? Mae ei enw, hefyd, yn dechrau gyda'r llythyren A, ac mae'n teimlo fel ein bod wedi gwneud mwy fyth o anhrefn y broblem hon. Erbyn hyn mae gennym gosod ar unwaith, mewnosod cysonyn amser, i mewn i strwythur data hytrach nag yn waeth-achos llinol, ond beth allwn ni ei wneud gyda Anita yn yr achos hwn? Beth yw'r ddau ddewis, mewn gwirionedd? Yeah? [Ateb Myfyrwyr, annealladwy] Iawn, felly gallwn gael dimensiwn arall. Mae hynny'n dda. Felly, gallwn adeiladu pethau allan mewn 3D fel yr ydym yn siarad am ar lafar ar ddydd Llun. Gallem ychwanegu un arall fynediad yma, ond mae'n debyg nad oes, Im 'yn ceisio cadw hyn yn syml. Y nod cyfan yma yw cael ar unwaith cyson-amser mynediad, fel bod wedi ychwanegu gormod o gymhlethdod. Beth yw opsiynau eraill wrth geisio i fewnosod Anita i'r strwythur hwn data? Yeah? [Ateb Myfyrwyr, annealladwy] Da. Felly, gallem symud pawb arall i lawr, fel Charlie wthio i lawr Bob ac Alice, ac yna rydym yn rhoi Anita lle mae hi'n wir eisiau bod. Wrth gwrs, erbyn hyn, mae 'na sgil effeithiau hyn. Mae'r strwythur data yn ôl pob tebyg yn ddefnyddiol nid am ein bod eisiau i fewnosod pobl unwaith ond oherwydd ein bod eisiau i wirio os maen nhw yno yn ddiweddarach os ydym eisiau argraffu ar yr holl enwau yn y strwythur data. Rydym yn mynd i wneud rhywbeth gyda data hwn yn y pen draw. Felly nawr rydym wedi fath o sgriwio dros Alice, sy'n ddim hwy lle mae hi i fod. Nid yw Bob, ac nid yw Charlie. Felly, efallai nad yw hyn yn syniad da. Ond yn wir, mae hyn yn un opsiwn. Gallem symud pawb i lawr, neu Heck, Anita yn hwyr i'r gêm, pam nad ydym yn unig yn rhoi Anita nid yw yma, nid yma, nid yma, gadewch i ni dim ond rhoi hi ychydig yn is yn y rhestr. Ond yna broblem hon yn dechrau datganoli eto. Efallai y byddwch yn gallu dod o hyd i Alice yn syth, yn seiliedig ar ei enw cyntaf. Ac Bob yn syth, a Charlie. Ond yna byddwch yn chwilio am Anita, a byddwch yn gweld, hmm, Alice yn y ffordd. Wel, gadewch i mi wirio isod Alice. Nid yw Bob yn Anita. Nid yw Charlie yw Anita. O, mae Anita. Ac os ydych yn parhau y trên o resymeg yr holl ffordd, beth yw'r amser gwaethaf-achos yn rhedeg o ddod o hyd neu fewnosod Anita i'r strwythur hwn data newydd? Mae'n O (n), dde? Oherwydd yn yr achos gwaethaf, mae Alice, Bob, Charlie. . . yr holl ffordd i lawr i rywun o'r enw "Y", felly dim ond un man ar ôl. Diolch byth, nid oes gennym un o'r enw "Z", felly rydym yn rhoi Anita ar y gwaelod iawn. Nid ydym wedi datrys y broblem honno mewn gwirionedd. Felly, efallai oes angen i ni gyflwyno'r trydydd dimensiwn. Ac mae'n troi allan, os ydym yn cyflwyno'r trydydd dimensiwn, Ni allwn wneud hyn yn berffaith, ond y Greal Sanctaidd yn mynd i fod yn mynd cyson-amser mewnosod a mewnosodiadau deinamig er mwyn i Nid oes raid i ni galed-god amrywiaeth o faint 26. Gallwn ychwanegu fel enwau llawer ag y dymunwn, ond gadewch i ni gymryd ein 5-munud egwyl yma ac yna gwneud hynny yn iawn. Mae pob hawl. I osod y stori fyny 'n bert artiffisial yno drwy ddewis Alice ac yna Bob ac yna Charlie ac yna Anita, y mae ei enw yn amlwg yn mynd i wrthdaro ag Alice. Ond y cwestiwn rydym yn dod i ben ddydd Llun gyda yn unig pa mor debygol yw hi y byddech yn cael y mathau hyn o wrthdrawiadau? Mewn geiriau eraill, os ydym yn dechrau defnyddio'r strwythur hwn tablau, sydd mewn gwirionedd yn unig array, yn yr achos hwn o 26 o leoliadau, beth os yw ein mewnbwn yn hytrach na dosbarthu unffurf? Nid yw'n artiffisial Alice a Bob a Charlie a David ac yn y blaen yn nhrefn yr wyddor, ei ddosbarthu unffurf dros A drwy'r Z. Efallai byddwn yn unig yn cael lwcus ac nid ydym yn mynd i gael dau A neu ddau B gyda thebygolrwydd uchel iawn, ond fel rhywun sylw at y ffaith, os ydym yn gyffredinol y broblem hon a pheidio â gwneud 0-25 ond, yn dweud, 0 364 neu drwy 65 oed, yn aml y nifer o ddyddiau mewn blwyddyn nodweddiadol, a gofyn y cwestiwn, "Beth yw'r tebygolrwydd y ddau ohonom yn yr ystafell hon yn cael pen-blwydd un fath?" Roi mewn ffordd arall, beth yw'r tebygolrwydd y ddau ohonom yn cael enw gan ddechrau gyda A? Y math o gwestiwn yw yr un fath, ond y gofod cyfeiriad, y gofod chwilio, yn fwy yn achos pen-blwydd, am fod gennym fwy o ddiwrnodau cymaint yn ystod y flwyddyn na llythyrau yn y wyddor. Beth yw'r tebygolrwydd o wrthdrawiad? Wel, gallwn feddwl am hyn drwy figuring allan y math y ffordd gyferbyn. Beth yw'r tebygolrwydd o unrhyw wrthdrawiadau? Wel, mae hyn yn fynegiant yma yn dweud bod yr hyn yw'r tebygolrwydd os oes dim ond un person yn yr ystafell hon, bod ganddynt pen-blwydd unigryw? Mae'n 100%. Oherwydd os oes dim ond un person yn yr ystafell, Gall ei ben-blwydd yn unrhyw un o'r 365 diwrnod o'r flwyddyn. Felly opsiynau 365/365 yn rhoi i mi werth o 1. Felly, y tebygolrwydd o dan sylw ar hyn o bryd yn unig 1. Ond os oes ail berson yn yr ystafell, beth yw'r tebygolrwydd bod eu pen-blwydd yn wahanol? Dim ond 364 diwrnod posibl, blynyddoedd naid anwybyddu, am eu pen-blwydd i beidio â gwrthdaro â'r personau eraill. Felly, 364/365. Os yw trydydd person yn dod i mewn, mae'n 363/365, ac yn y blaen. Felly, byddwn yn cadw lluosi ffracsiynau hyn at ei gilydd, sy'n mynd yn llai ac yn llai, at chyfrif i maes beth yw'r tebygolrwydd bod pob un ohonom yn cael pen-blwydd unigryw? Ond fe allwn wedyn, wrth gwrs, dim ond yn cymryd yr ateb hwnnw ac yn troi o gwmpas ac yn ei wneud 1 minws hynny i gyd, mynegiant byddwn yn y pen draw yn cael os ydych yn cofio gefn eich llyfrau mathemateg, mae'n edrych yn rhywbeth bach fel hyn, sydd yn llawer haws dehongli graffigol. A llun hon yma yn ei gael ar yr echelin x nifer y pen-blwydd, neu nifer y bobl ag pen-blwydd, ac ar yr echelin y yw y tebygolrwydd o gêm. A beth mae hyn yn ei ddweud yw os oes gennych chi, gadewch i ni ddweud, hyd yn oed, gadewch i ni ddewis rhywbeth fel 22, 23. Os oes 22 neu 23 o bobl yn yr ystafell, y tebygolrwydd bod dau o'r rhai ychydig iawn o bobl yn mynd i gael yr un pen-blwydd mewn gwirionedd yn uchel super, combinatorially. 50% y groes mewn dosbarth o ddim ond 22 o bobl, yn seminar, yn ymarferol, 2 o bobl yn mynd i gael yr un pen-blwydd. Oherwydd mae cymaint o ffyrdd y gallwch chi gael yr un pen-blwydd. Hyd yn oed yn waeth, os edrychwch ar yr ochr dde y siart, erbyn yr amser sydd gennych dosbarth gyda 58 o fyfyrwyr ynddo, y tebygolrwydd o 2 o bobl yn cael pen-blwydd yn super, uchel super, bron i 100%. Nawr, mae hynny'n fath o ffaith hwyl am fywyd go iawn. Ond y goblygiadau, yn awr, ar gyfer strwythurau data a storio gwybodaeth yn golygu mai dim ond gan dybio eich bod yn cael 'n glws, yn lân, dosbarthu unffurf o ddata a bod gennych ddigon o amrywiaeth fawr i ffitio bagad o bethau nid yw'n golygu eich bod yn mynd i gael pobl mewn lleoliadau unigryw. Rydych yn mynd i gael gwrthdrawiadau. Felly, mae hyn syniad o stwnsio, gan ei fod yn cael ei alw, cymryd mewnbwn fel "Alice" a massaging mewn rhyw ffordd ac yna mynd yn ôl ateb fel 0 neu 1 neu 2. Cael yn ôl rhywfaint o allbwn o'r swyddogaeth honno yn cael ei blagio gan y tebygolrwydd o gael gwrthdrawiad. Felly, sut rydym yn trin y gwrthdrawiadau? Wel, ar yr un achos, gallwn gymryd y syniad a awgrymwyd. Gall Rydym yn unig yn symud pawb i lawr, neu efallai, ychydig yn fwy syml, yn hytrach na phawb arall symud, gadewch i ni dim ond symud Anita i waelod y fan a'r lle sydd ar gael. Felly, os Alice yn 0, Bob yn 1, Charlie yn 2, byddwn yn unig yn rhoi Anita yn lleoliad 3. Ac mae hyn yn dechneg mewn strwythurau data a elwir yn llinol dreiddgar. Llinellol oherwydd eich bod yn cerdded y llinell hon, ac rydych yn fath o ymchwilio am fannau sydd ar gael yn y strwythur data. Wrth gwrs, mae hyn yn datganoli i mewn i O (n). Os yw'r strwythur data wir yn llawn, mae 25 o bobl ynddo eisoes, ac yna Anita yn dod ar hyd, mae hi'n dod i ben i fyny ar yr hyn a fyddai'n Z lleoliad, ac mae hynny'n iawn. Mae hi'n dal i ffitio, a gallwn ddod o hyd iddi yn ddiweddarach. Ond mae hyn yn groes i'r nod o gyflymu pethau i fyny. Felly beth os ydym yn hytrach gyflwyno y trydydd dimensiwn? Y dechneg a elwir yn gyffredinol gadwyno ar wahân, neu gael cadwyni. A beth tabl hash yn awr yw, y strwythur tabl, eich bwrdd yn unig yw amrywiaeth o awgrymiadau. Ond beth yw'r arwyddion yn cyfeirio ato yw'r dyfalu beth? Mae rhestr cysylltiedig. Felly beth os ydym yn cymryd y gorau o'r ddau fyd? Rydym yn defnyddio araeau ar gyfer y mynegeion cychwynnol i mewn i'r strwythur data er mwyn i ni ar unwaith yn mynd i [0] [1], [30] neu yn y blaen, ond er mwyn gennym rywfaint o hyblygrwydd a gallwn ffitio Anita a Alice ac Adam ac unrhyw un arall Mae enw, rydym yn hytrach gadael i'r echelin eraill yn tyfu yn fympwyol. Ac rydym yn olaf, o ddydd Llun, yn cael y gallu mynegiannol gyda rhestr cysylltiedig. Gallwn dyfu strwythur data fympwyol. Fel arall, gallem wneud enfawr 2-ddimensiwn array, ond mae hynny'n mynd i fod yn sefyllfa ofnadwy os yw un o'r rhesi mewn amrywiaeth 2-ddimensiwn yn ddigon mawr ar gyfer y person ychwanegol y mae ei enw yn digwydd i ddechrau A. Duw a'n gwaredo rhag mae'n rhaid i ni ail-ddyrannu enfawr 2-ddimensiwn strwythur dim ond oherwydd bod cymaint o bobl a enwir A, yn enwedig pan fo cyn lleied o bobl a enwir Z rhywbeth. Mae'n dim ond yn mynd i fod yn strwythur data yn brin iawn. Felly, nid yw'n berffaith o bell ffordd, ond yn awr mae gennym o leiaf y gallu i yn syth ddod o hyd lle mae Alice neu Anita yn perthyn iddi, o leiaf o ran yr echelin fertigol, ac yna rydym yn unig rhaid i ni benderfynu lle i roi Anita neu Alice yn y rhestr hon cysylltiedig. Os nad ydym yn poeni am drefnu pethau, gallai pa mor gyflym rydym yn ychwanegu Alice i mewn i strwythur fel hyn? Mae'n amser yn gyson. Byddwn yn mynegeio'r i [0], ac os oes unrhyw un yn, Alice yn mynd ar ddechrau'r rhestr honno cysylltiedig. Ond dyw hynny ddim yn golygu cryn dipyn. Oherwydd os Anita wedyn yn dod ynghyd ryw nifer o gamau yn ddiweddarach, ble mae Anita yn perthyn? Wel, [0]. OOP. Alice eisoes yn y rhestr honno cysylltiedig. Ond os nad ydym yn poeni am ddatrys yr enwau hyn, gallwn dim ond symud Alice dros, mewnosoder Anita, ond hyd yn oed hynny yw cysonyn amser. Hyd yn oed os oes Alice ac Adam a hyn i gyd A eraill enwau, Nid yw hi go symud yn gorfforol. Pam? Oherwydd ein bod yn unig oedd yma gyda rhestr cysylltiedig, pwy a ŵyr yn y nodau yn beth bynnag? Y cyfan sydd raid i chi ei wneud yw symud y briwsion bara. Symudwch y saethau o amgylch, nid oes rhaid i chi symud yn gorfforol unrhyw ddata o gwmpas. Felly, gallwn ychwanegu Anita, yn yr achos hwnnw, ar unwaith. Cysonyn amser. Felly mae gennym cyson-amser am-edrych, ac yn gyson-amser gosod rhywun fel Anita. Ond math o gorsymleiddio y byd. Beth os ydym yn ddiweddarach am ddod o hyd Alice? Beth os ydym yn ddiweddarach am ddod o hyd Alice? Faint o gamau yw bod mynd i gymryd? [Ateb Myfyrwyr, annealladwy] Yn union. Mae nifer y bobl cyn Alice yn y rhestr cysylltiedig. Felly nid yw'n hollol berffaith, oherwydd bod ein strwythur data, unwaith eto, mae hyn yn fynediad fertigol ac yna rhaid rhestrau hyn cysylltiedig hongian - yn wir, gadewch i ni dynnu arae yn. Mae wedi hyn rhestrau cysylltiedig yn hongian oddi ar ei sy'n edrych rhywbeth bach fel hyn. Ond y broblem yw os Alice ac Adam a hyn i gyd A eraill enwau yn y pen draw yn fwy a mwy dros yno, dod o hyd y gallai rhywun yn y pen draw yn cymryd criw o gamau, bcause yn rhaid i chi deithio ar draws y rhestr cysylltiedig, sydd yn llawdriniaeth llinol. Felly mewn gwirionedd, yna, yr amser mewnosod yn y pen draw yn O (n), lle mae n yn nifer o elfennau yn y rhestr. Rannu gan, gadewch i ni fympwyol ei alw m, lle m yw nifer y rhestrau cysylltiedig bod gennym yn y echelin fertigol. Mewn geiriau eraill, os ydym yn wirioneddol yn tybio dosbarthiad unffurf o enwau, hollol afrealistig. Mae amlwg yn fwy o rai llythyrau nag eraill. Ond os ydym yn cymryd yn ganiataol ar hyn o bryd a dosbarthiad unffurf, ac rydym wedi n pobl cyfanswm, a chadwyni chyfanswm m ar gael i ni, yna ar hyd pob un o'r cadwyni weddol syml, yn mynd i fod y cyfanswm, n rannu gan y nifer o gadwyni. Felly n / m. Ond dyma lle y gallwn fod pawb yn fathemategol glyfar. m yn gysonyn, oherwydd mae 'na nifer penodedig o'r rhain. Rydych yn mynd i ddatgan eich amrywiaeth ar y dechrau, ac nid ydym yn newid maint yr echelin fertigol. Drwy ddiffiniad, sy'n sefydlog yn aros. Dim ond yr echelin lorweddol, fel petai, mae hynny'n newid. Felly, yn dechnegol, mae hyn yn gyson. Felly yn awr, yr amser gosod yn O 'n bert lawer (n). Felly, nid yw'n teimlo i gyd bod llawer gwell. Ond beth yw'r gwirionedd yma? Wel, i gyd y tro hwn, am wythnosau, rydym wedi bod yn ei ddweud O (n ²). O (n), 2 x n ², - n, wedi'i rannu â 2. . . ech. Dim ond ² n. Ond yn awr, yn y rhan hon o'r semester, gallwn ddechrau siarad am y byd go iawn unwaith eto. Ac n / m yn gwbl gyflymach na dim ond n unig. Os oes gennych fil o enwau, ac rydych yn eu torri i fyny i mewn bwcedi lluosog fel bod gennych dim ond deg enw ym mhob un o'r cadwyni, gwbl chwilio deg peth yn mynd i fod yn gyflymach na mil o bethau. Ac felly un o'r setiau problem sydd ar y gweill yn mynd i herio eich i feddwl am yr union hyd yn oed er, yeah, asymptotically ac yn fathemategol, mae hyn yn dal i fod ychydig llinol, sy'n sucks yn gyffredinol wrth geisio dod o hyd i bethau. Mewn gwirionedd, mae'n mynd i fod yn gyflymach na'r hyn a oherwydd y rhannydd. Ac felly mae 'unwaith eto yn mynd i fod y fasnach-off ac mae hyn yn gwrthdaro rhwng theori a realiti, a bydd un o'r knobs yn dechrau troi ar y pwynt hwn yn y semester yn fwy o realiti un fel yr ydym math o baratoi ar gyfer semster y diwedd, wrth i ni gyflwyno y byd o raglenni ar y we, lle mewn gwirionedd, mae perfformiad yn mynd i gyfrif am fod eich defnyddwyr yn mynd i dechrau teimlo'n a gwerthfawrogi benderfyniadau dylunio gwael. Felly sut mae mynd ati i weithredu cysylltiedig - tabl hash gyda 31 o elfennau? Ac yr enghraifft flaenorol yn fympwyol am pen-blwydd. Os bydd rhywun yn cael pen-blwydd o Ionawr 1 neu 1 Chwefror, byddwn yn eu rhoi yn y bwced. Os yw'n Ionawr 2, Chwefror 2, 2 Mawrth, byddwn yn eu rhoi yn y bwced. Dyna pam yr oedd 31. Sut ydych chi'n datgan tabl hash? Gall fod yn eithaf syml, tabl * nod yw fy enw mympwyol ar ei gyfer, [31]. Mae hyn yn rhoi i mi 31 awgrymiadau i nodau, ac mae hynny'n caniatáu i mi i 31 o awgrymiadau i restrau cysylltiedig hyd yn oed os yw'r cadwyni yn dechrau NULL. Beth ydw i am ei roi os ydw i eisiau i storio 'Alice, "" Bob, "" Charlie "? Wel, mae angen i lapio pethau hynny mewn strwythur oherwydd mae arnom angen Alice i bwyntio at Bob, i bwyntio at Charlie, ac yn y blaen. Ni allwn gael yr enwau yn unig, er mwyn i mi greu strwythur newydd o'r enw nôd yma. Beth yw nod go iawn? Beth yw nod yn y rhestr hon newydd sy'n gysylltiedig? Y peth cyntaf, a elwir gair, ar gyfer enw'r person. HYD, yn ôl pob tebyg, yn ymwneud â'r uchafswm hyd o enw dynol, beth bynnag hynny yw, 20, 30, 40 gymeriadau mewn achosion cornel crazy, a +1 ar gyfer beth? Mae'n dim ond y nod NULL ychwanegol, \ 0. Felly, mae hyn yn nod lapio "rhywbeth" tu mewn ei hun, ond mae hefyd yn datgan pwyntydd o'r enw nesaf fel y gallwn cadwyn Alice i Bob i Charlie ac yn y blaen. Gall fod yn NULL, ond nid yw o reidrwydd yn rhaid i fod. Unrhyw gwestiynau ar y tablau hash? Yeah? [Myfyrwyr yn gofyn cwestiwn, annealladwy] Mae amrywiaeth - cwestiwn da. Pam fod y gair torgoch mewn arae yn hytrach na dim ond * torgoch? Yn yr enghraifft hon braidd yn fympwyol, doeddwn i ddim eisiau gorfod troi i malloc gyfer pob un o'r enwau gwreiddiol. Roeddwn i eisiau datgan uchafswm o gof ar gyfer y llinyn er mwyn i mi gopïo i mewn i'r strwythur Alice \ 0 ac nid rhaid i chi ddelio â malloc ac am ddim ac yn y blaen. Ond roeddwn yn gallu gwneud hynny os oeddwn i eisiau i fod yn fwy ymwybodol o ddefnydd gofod. Da cwestiwn. Felly, gadewch i ni geisio gyffredinoli i ffwrdd o'r ac yn canolbwyntio gweddill heddiw ar strwythurau data yn fwy cyffredinol a phroblemau eraill y gallwn ddatrys defnyddio'r hanfodion un er bod y strwythurau data y gallai eu hunain yn wahanol o ran eu manylion. Felly, mae'n troi allan mewn gwyddoniaeth gyfrifiadurol, coed yn gyffredin iawn. A allwch chi feddwl am fath o fel coeden coeden deulu, lle mae rhywfaint o wreiddiau, mae rhai matriarch neu patriarch, nain neu grandpa neu'n gynharach yn ôl, o dan ohonynt yn mom a dad neu frodyr a chwiorydd wahanol neu debyg. Felly strwythur goeden nodau ac mae ganddo blant, fel arfer yn 0 neu fwy o blant ar gyfer pob nod. Ac mae rhai o'r jargon a welwch yn y llun yma yw unrhyw un o'r plant ychydig neu grandkids ar yr ymylon sydd heb unrhyw saethau sy'n deillio ohonynt, dyna'r dail fel y'i gelwir, ac unrhyw un ar y tu mewn yn nod mewnol, gallwch alw yn unrhyw beth hyd y llinellau hynny. Ond y strwythur hwn yn eithaf cyffredin. Hyn yn un 'ychydig yn fympwyol. Mae gennym un plentyn ar y chwith, mae gennym dri o blant ar y dde, dau o blant ar y gwaelod ar y chwith. Felly, gallwn gael o wahanol faint coed, ond os ydym yn dechrau i safoni pethau, ac efallai y byddwch yn cofio hyn Patrick fideo ar chwiliad deuaidd o fer blaenorol nid ar lein, chwiliad deuaidd yn gorfod cael ei weithredu gydag amrywiaeth neu ddarnau o bapur ar fwrdd du. Tybiwch eich bod yn dymuno i storio eich rhifau mewn strwythur data mwy soffistigedig. Gallech greu coeden fel hyn. Gallech gael nod ddatgan yn C, a gall y nod fod ag o leiaf dwy elfen y tu mewn ohono. Un yw y rhif yr ydych am ei gadw, ac mae'r llall yn - wel, mae angen un yn fwy. Y llall yw ei phlant. Felly dyma un arall strwythur data. Y tro hwn, mae nod yn cael ei ddiffinio fel storio nifer n ac yna dau awgrymiadau; plentyn chwith a dde phlentyn. Ac nid ydynt yn fympwyol. Beth sy'n ddiddorol am y goeden? Beth yw'r patrwm o ran sut yr ydym wedi gosod hyn neu sut Patrick gosod allan yn ei fideo? Mae'n fath o amlwg fod yna peth gwaith didoli yn digwydd yma, ond beth yw'r rheol syml? Yeah? [Ateb Myfyrwyr, annealladwy] Perfect. Os ydych yn gipolwg ar hyn, byddwch yn gweld y niferoedd bach ar y chwith, rhifau mawr ar y chwith, ond mae hynny'n wir am bob nod. Ar gyfer pob nod, ei blentyn chwith llai nag y mae'n ei, ac mae ei phlentyn gywir yn fwy nag ef. Beth mae hyn yn golygu yn awr yw os wyf am i chwilio y strwythur data ar gyfer, dyweder, rhif 44, Rhaid i mi ddechrau ar y gwraidd, oherwydd fel gyda phob un o'r rhain yn fwy cymhleth strwythurau data yn awr, yn unig sydd gennym pwyntydd i un peth, y dechrau. Ac yn yr achos hwn, y dechrau yw gwraidd. Dyw hi ddim yn ddiwedd y chwith, ei fod yn wraidd y strwythur hwn. Felly, yr wyf yn gweld yma yn 55 oed, ac rwy'n edrych am 44. Pa gyfeiriad ydw i am fynd? Wel, dw i eisiau mynd i'r chwith, oherwydd yn amlwg, ar y dde yn mynd i fod yn rhy fawr. Felly sylwi yma, rydych yn fath o gysyniadol torri y goeden yn ei hanner oherwydd nad ydych yn mynd i lawr i'r ochr dde. Felly nawr rwy'n mynd o 55 i 33. Mae'n rhy fach o nifer. Dwi'n chwilio am 44, ond yn awr yr wyf yn gwybod os yn 44 yn y goeden hon, gallaf fynd yn amlwg ar y dde. Felly, unwaith eto, rwy'n docio y goeden yn ei hanner. Mae'n 'n bert lawer yn union yr gysyniadol at y llyfr ffôn. Mae'n union yr un fath beth a wnaethom gyda'r papurau ar y bwrdd du, ond mae'n strwythur mwy soffistigedig sy'n caniatáu i ni ei wneud mewn gwirionedd hyn yn rhannu a gorchfygu gan dyluniad y algorithm, ac yn wir, groesi strwythur fel hyn - Wps. Croesi strwythur fel hyn, lle mai dim ond "yn mynd y ffordd neu'n mynd y ffordd honno," yn golygu yr holl y cod sy'n plygu eich meddwl ar y dechrau wrth roi ar waith yn adran neu gerdded drwyddo yn y cartref, ar gyfer chwiliad deuaidd, gan ddefnyddio dychweliad neu ailadrodd, mae'n boen yn y gwddf. Dewch o hyd i'r elfen canol, yna gwnewch eich talgrynnu i fyny neu i lawr. Mae yna harddwch i hyn oherwydd gallwn yn awr ddefnyddio dychweliad eto, ond yn llawer mwy lân. Yn wir, os ydych chi yn y rhif 55 a ydych am ddod o hyd i 44, byddwch yn mynd ar ôl yn yr achos hwn, yna beth ydych chi'n ei wneud? Rydych yn rhedeg yr un algorithm union. Chi wirio gwerth y nod, yna byddwch yn mynd i'r chwith neu i'r dde. Yna byddwch yn edrych ar y gwerth y nod, ewch i'r chwith neu i'r dde. Mae hyn yn berffaith ar gyfer dychweliad. Felly hyd yn oed er, yn y gorffennol rydym wedi gwneud rhai enghreifftiau yn eithaf mympwyol yn cynnwys dychweliad nad oedd angen i fod yn ailadroddus, gyda stuctures data, yn enwedig coed, mae'n gais berffaith o hyn syniad o gymryd problem, crebachu, ac yna datrys yr un math o, ond yn llai, rhaglen. Felly, mae adeiledd arall yn ddata y gallwn eu cyflwyno. Mae hyn yn un wedi ei gynllunio ar yr olwg gyntaf i edrych cryptic, ond mae hyn yn un 'anhygoel. Felly, mae hwn yn strwythur data a elwir yn trie, trie, sy'n cael ei etifeddu o fedru adalw geiriau, nad yw wedi'i amlwg ail-cais-Val, ond dyna beth y byd yn galw y pethau hyn. Ceisiau. T-r-i-e. Mae'n strwythur coeden o ryw fath, ond mae pob un o'r nodau mewn trie ymddangos i fod yr hyn? Ac mae hyn yn ychydig yn gamarweiniol oherwydd ei fod yn fath o cryno. Ond mae'n edrych yn debyg bob nod yn y trie mewn gwirionedd yn arae. A hyd yn oed er nad yw'r awdur y diagram wedi dangos ei fod, yn yr achos hwn, mae'r trie yn strwythur data y mae ei bwrpas mewn bywyd yw storio geiriau fel A-l-i-c-e neu B-o-b. A'r ffordd y mae'r siopau data Alice a Bob a Charlie a Anita ac yn y blaen mae'n cael ei defnyddio amrywiaeth lle i storio Alice mewn trie, rydym yn dechrau ar y nod gwraidd sy'n edrych fel arae, ac mae wedi ei ysgrifennu mewn nodiant llaw-fer. Mae'r awdur yn hepgor ABCDEFG am nad oedd unrhyw enwau â hynny. Maent yn unig yn dangos M a P a T, ond yn yr achos hwn, gadewch i ni symud i ffwrdd oddi wrth Alice a Bob a Charlie i rai enwau sydd yma. Maxwell mewn gwirionedd yn y diagram. Felly sut wnaeth y siop awdur M-a-x-w-e-l-l? Ef neu hi ddechrau yn y nod gwraidd, ac aeth i [M], felly yn fras 13, y lleoliad 13eg yn y rhesi. Yna oddi yno, mae pwyntydd. Mae pwyntydd yn arwain i un arall amrywiaeth. Oddi yno yr awdur mynegeio i mewn i'r amrywiaeth yn y lleoliad A, fel y darluniwyd yno ar y chwith uchaf, ac yna ef neu hi yn dilyn y pwyntydd i'r llall array, ac aeth at y pwyntydd yn y lleoliad X. Yna, yn yr amrywiaeth nesaf lleoliad, W E, L, L, ac yn y blaen, ac yn olaf, gadewch i ni mewn gwirionedd yn ceisio rhoi darlun i hyn. Beth yw edrych yn nod fel mewn cod? Mae nod mewn trie yn cynnwys amrywiaeth o awgrymiadau i nodau mwy. Ond mae 'na hefyd i fod yn rhyw fath o werth boolean, o leiaf yn y gweithredu. Yr wyf yn digwydd i alw ei is_word. Pam? Oherwydd pan fyddwch chi'n gosod Maxwell, nad ydych yn gosod unrhyw beth i mewn i'r strwythur data. Nid ydych yn ysgrifennu M. Nid ydych yn ysgrifennu X. Mae pob ydych yn ei wneud yn dilyn awgrymiadau. Y pwyntydd sy'n cynrychioli M, yna bydd y pwyntydd sy'n cynrychioli A, yna bydd y pwyntydd sy'n cynrychioli X, yna C, E, L, L, ond yr hyn y mae angen i chi ei wneud ar y diwedd yn fath o fynd, gwirio, yr wyf yn cyrraedd y lleoliad hwn. Roedd gair sy'n dod i ben yma yn y strwythur data. Felly beth yw trie yn cael ei llenwi iawn gyda'r awdur a'r dewis i gynrychioli hyn terminuses â thrionglau bach. Mae hyn yn unig yn golygu bod y ffaith y triongl sydd yma, y ​​gwerth boolaidd o wir yn golygu os ydych yn mynd yn ôl yn y goeden, mae hynny'n golygu gair a enwir Maxwell yn hyn o beth. Ond y gair, foo er enghraifft, Nid yw yn y goeden, oherwydd os byddaf yn dechrau ar y nod gwraidd i fyny yma ar ben, Does dim, pwyntydd f dim pwyntydd o, dim pwyntydd o. Nid yw Foo yn enw yn y geiriadur. Ond ar y llaw arall, weledol, t-u-r-i-n-g. Unwaith eto, doeddwn i ddim yn storio t neu u neu r neu i neu n neu g. Ond wnes i storio yn y strwythur data gwerth tramwy wir i lawr yma yn y nod - yn y goeden drwy osod y gwerth boolaidd o is_word i gwir. Felly trie yn fath o strwythur hwn meta ddiddorol iawn, lle nad ydych wirioneddol yn storio'r geiriau eu hunain ar gyfer y math hwn o geiriadur. I fod yn glir, eich bod newydd storio ie neu na, oes air sy'n dod i ben yma. Nawr beth yw'r goblygiadau? Os oes gennych 150,000 o eiriau mewn geiriadur eich bod yn ceisio i'w cadw mewn cof defnyddio rhywbeth fel rhestr cysylltiedig, ydych yn mynd i gael 150,000 nodau yn eich rhestr cysylltiedig. A gallai dod o hyd i un o'r geiriau hynny yn nhrefn yr wyddor yn cymryd O (n) amser. Amser llinol. Ond yn yr achos yma o trie, beth amser yn rhedeg o ddod o hyd i air? Mae'n troi allan y harddwch yma yw bod hyd yn oed os oes gennych 149,999 o eiriau sydd eisoes yn y geiriadur, rhoi ar waith fel gyda'r strwythur data, faint o amser mae'n ei gymryd i ddod o hyd i neu rhowch un person yn fwy i mewn i hynny, fel Alice, Alice? Wel, dim ond 5, efallai 6 cham ar gyfer y cymeriad llusgo. Oherwydd bod y presense o enwau eraill yn y strwythur nad yw'n cael yn y ffordd o mewnosod Alice. Ar ben hynny, dod o hyd i Alice unwaith y mae 150,000 o eiriau yn y geiriadur nad yw'n cael yn eich ffordd o ddod o hyd Alice o gwbl, oherwydd Alice yn. . . . . yma, oherwydd fy mod yn dod o hyd i werth boolaidd. Ac nid os nad oes boolean wir, yna Alice yn y strwythur data o eiriau. Mewn geiriau eraill, yr amser yn rhedeg o ddod o hyd pethau a gosod pethau i mewn i'r newydd data strwythur trie yw O o - nid yw'n n. Oherwydd bod y presense o 150,000 o bobl yn cael unrhyw effaith ar Alice, mae'n ymddangos. Felly, gadewch i ni ei alw k, lle mae k yn uchafswm hyd y gair yn Saesneg sef, yn nodweddiadol dim mwy na 20-rhywbeth cymeriadau. Felly k yn gysonyn. Felly, y Greal Sanctaidd rydym yn ymddangos i wedi dod o hyd yn awr yw bod o trie, cysonyn amser ar gyfer mewnosod, ar gyfer lookups, ar gyfer dileadau. Oherwydd bod y nifer o bethau eisoes yn y strwythur, nad ydynt yn hyd yn oed yn gorfforol yno. Unwaith eto, maen nhw jyst yn trefnu o gwirio, ie neu ddim, yn cael unrhyw effaith ar ei amser rhedeg yn y dyfodol. Ond mae rhaid i fod yn dal, fel arall ni fyddem wedi gwastraffu cymaint o amser ar yr holl strwythurau data arall yn unig i pen draw yn cael yr un gyfrinach sy'n anhygoel. Felly, pa bris yr ydym yn talu i gyflawni hyn fawredd yma? Space. Mae hyn yn peth yn enfawr. A'r rheswm fod yr awdur nid oedd yn bresennol yma, yn sylwi bod yr holl bethau hyn sy'n edrych fel arrays, nad oedd yn tynnu gweddill y goeden, gweddill y trie, oherwydd eu bod nid yn unig yn berthnasol i'r stori. Ond mae pob un o'r nodau eang yn super, a phob nod yn y goeden yn cymryd i fyny 26 neu mewn gwirionedd, gallai fydd 27 gymeriadau oherwydd yn yr achos hwn roeddwn yn cynnwys lle ar gyfer y collnod fel y gallem gael geiriau apostrophized. Yn yr achos hwn, mae'r rhain yn araeau eang. Felly hyd yn oed er nad ydynt yn picutured, mae hyn yn cymryd i fyny swm enfawr o RAM. A allai fod yn iawn, yn enwedig ar mewn caledwedd modern, ond dyna'r tradeoff. Rydym yn cael llai o amser drwy wario mwy o le. Felly, lle mae hyn i gyd yn mynd? Wel, gadewch i ni wneud - gadewch i ni weld yma. Gadewch i ni wneud naid i'r guy yma. Credwch neu beidio, hwyl gymaint ag y C wedi bod ers peth amser bellach, rydym yn cyrraedd y pwynt yn y semester lle mae'n amser i newid i bethau mwy modern. Pethau ar lefel uwch. A hyd yn oed pe bai ar gyfer yr ychydig wythnosau nesaf byddwn yn parhau i drochi ein hunain yn y byd o awgrymiadau a rheoli cof i gael y cysur ag y gallwn adeiladu arni, diwedd y gêm yn y pen draw i gyflwyno, nid yn eironig, yr iaith hon. Byddwn yn gwario, fel 10 munud yn siarad am HTML. Mae'r holl HTML yn yn iaith markup, a beth yw iaith markup yn Dyma'r gyfres o gromfachau agored a bracedi caeedig sy'n dweud 'wneud cam eofn hwn' 'Gwneud hyn yn italig' 'gwneud hyn yn ganolog.' Nid yw popeth sy'n ddeallusol ddiddorol, ond mae'n super defnyddiol. Ac mae'n sicr yn hollbresennol y dyddiau hyn. Ond beth sy'n bwerus am y byd o HTML, a rhaglennu ar y we yn fwy cyffredinol, yn adeiladu pethau deinamig; ysgrifennu cod mewn ieithoedd fel PHP neu Python neu Ruby neu Java neu C #. Really, beth bynnag yw eich dewis iaith yw, a chynhyrchu HTML ddynamig. Cynhyrchu rywbeth o'r enw CSS ddynamig. Defnyddiwyd taflenni arddull rhaeadrol, sydd hefyd am estheteg. Ac felly hyd yn oed er, heddiw, os byddaf yn mynd i ryw wefan fel y Google.com cyfarwydd, ac rwy'n mynd i weld, datblygwr, ffynhonnell marn i, sydd efallai eich bod wedi gwneud o'r blaen, ond yn mynd i weld y ffynhonnell, y pethau yn ôl pob tebyg yn edrych yn eithaf cryptig. Ond mae hyn yn y cod sylfaenol sy'n gweithredu Google.com. Ar y pen blaen. Ac mewn gwirionedd yn hyn oll yw estheteg pethau blewog. Mae hyn yn CSS i fyny yma. Os byddaf yn cadw sgrolio i lawr y byddwn yn cael rhywfaint o stwff lliw-godio. Mae hyn yn HTML. Google cod yn edrych fel baw, ond os wyf mewn gwirionedd yn agor ffenestr wahanol, gallwn weld peth strwythur i hyn. Os byddaf yn agor y fyny, sylwi yma, mae ychydig yn fwy darllenadwy. Rydym yn mynd i weld cyn bo hir tag hwn, [word] yn tag, HTML, pennaeth, corff, div, sgript, ardal testun, rhychwant, sy'n canolbwyntio ar, div. Ac mae hyn hefyd yn trefnu o cryptic-edrych ar yr olwg gyntaf, ond mae pob o'r llanastr hwn yn dilyn patrymau penodol, a phatrymau eu hailadrodd, felly unwaith i ni gael y pethau sylfaenol i lawr, byddwch yn gallu ysgrifennu cod fel hyn ac yna trin cod fel hyn drwy ddefnyddio eto iaith arall, a elwir yn JavaScript. Ac JavaScript yn iaith sy'n rhedeg tu mewn i borwr heddiw yr ydym yn eu defnyddio ar gyrsiau Harvard, ar gyfer y cwrs siopa offeryn sy'n fapiau Google yn defnyddio i roi criw cyfan o egni, Facebook yn rhoi i chi ddangos diweddariadau statws amrantiad, Twitter yn ei defnyddio i ddangos i chi tweets yn syth. Mae hyn i gyd byddwn yn dechrau i drochi ein hunain ynddo Ond i gyrraedd yno, mae angen i ni ddeall rhywbeth bach am y Rhyngrwyd. Mae'r clip yma yn unig munud o hyd, a gadewch i ni gymryd yn ganiataol ar hyn o bryd mae hyn yn, mewn gwirionedd, sut y mae'r Rhyngrwyd yn gweithio fel teaser ar gyfer yr hyn sydd ar fin dod. Yr wyf yn rhoi i chi "Warriors y Net." [♫ cerddoriaeth corws Araf ♫] [Adroddwr Gwryw] Daeth gyda neges. Gyda protocol ei holl hun. [♫ cerddoriaeth electronig yn gyflymach ♫] Daeth i fyd o waliau tân oer, yn ddidaro llwybryddion, a'r peryglon llawer gwaeth na marwolaeth. Mae'n gyflym. Mae'n gryf. Mae'n TCP / IP, ac mae wedi cael eich cyfeiriad. Rhyfelwyr y Net. [Malan] Yr wythnos nesaf, yna. Y Rhyngrwyd. Rhaglennu ar y we. Mae hyn yn CS50. [CS50.TV]