SPEAKER 1: Id-dritt, hekk aħna lura. Merħba għall CS50. Dan huwa l-aħħar ta 'seba' ġimgħa. Allura ifakkar li l-aħħar darba, bdejna tħares lejn ftit aktar sofistikati strutturi ta 'dejta. Peress sa issa, kollha kellna verament għad-dispożizzjoni tagħna kienet din, firxa. 

Iżda qabel we jarmi l-array li ma dak kollu li interessanti, li tabilħaqq attwalment hija, liema huma wħud mill- pluses ta 'din id-data sempliċi istruttura s'issa? X'hemm tajba fi? S'issa kif aħna stajt tidher? What do inti ltqajna? Xejn. 

STUDENT: [inaudible]. 

SPEAKER 1: X'hemm li? 

STUDENT: [inaudible]. 

SPEAKER 1: Daqs fiss. OK, hekk għaliex huwa d-daqs fiss tajba għalkemm? 

STUDENT: [inaudible]. 

SPEAKER 1: OK, dan huwa effiċjenti fl -sens li inti tista 'talloka ammont fiss ta 'l-ispazju, li nisperaw huwa preċiżament kemm ispazju kif tixtieq. Allura li tista 'tkun assolutament plus. 

X'hemm ieħor ġenb minn firxa? Yeah? 

STUDENT: [inaudible]. 

SPEAKER 1: L-- sorry? 

STUDENT: [inaudible]. 

SPEAKER 1: Il-kaxxi fil-memorja jew ħdejn xulxin. U hu utli - għaliex? Li pjuttost veru. Iżda kif nistgħu jisfruttaw li l-verità? 

STUDENT: [inaudible]. 

SPEAKER 1: Eżattament, nistgħu jżommu rekord ta ' fejn kollox huwa biss billi jkun jaf indirizz wieħed, jiġifieri l-indirizz tal- ewwel byte ta 'dik blokki ta' memorja. Jew fil-każ tas-sekwenza, l-indirizz ta 'l-ewwel char f'dak sekwenza. U minn hemm, nistgħu nsibu l-aħħar tas-sekwenza. Nistgħu nsibu t-tieni element, l- tielet element, u oħrajn. 

U għalhekk l-mod fancy ta 'jiddeskrivi dik karatteristika hija li arrays tagħtina aċċess bl-addoċċ. Biss bl-użu tal-parentesi kwadri notazzjoni u numru, inti tista 'tiżdied għal element speċifiku fil-firxa fil-ħin kostanti, big O ta 'wieħed, biex ngħidu hekk. 

Iżda hemm kien xi effetti negattivi. Liema firxa ma tagħmel faċilment? X'hemm mhux tajba fil? 

STUDENT: [inaudible]. 

SPEAKER 1: X'hemm li? 

STUDENT: [inaudible]. 

SPEAKER 1: Espansjoni fid-daqs. Allura l-aspetti negattivi tal-firxa huma preċiżament l-oppost ta 'dak l- upsides huma. Allura wieħed mill-aspetti negattivi huwa li huwa daqs fiss. Allura inti ma tistax verament jikbru. Tista 'jalloka mill-ġdid ta' blokki akbar ta ' memorja, u mbagħad jimxu l-elementi qodma fil-firxa ġdida. U allura free-firxa qodma, għal Pereżempju, bl-użu malloc jew simili funzjoni msejħa realloc, li reallocates memorja. 

Realloc, bħala twarrib, tipprova li jtik memorja li jmiss għall-firxa li diġà għandek. Iżda jista affarijiet jimxu madwar għal kollox. Iżda fil-qosor, li għali, id-dritt? Għaliex jekk għandek blokki ta 'memorja ta' dan id-daqs, iżda inti verament irridu wieħed ta 'dan id-daqs, u inti tixtieq li jippreservaw l-elementi oriġinali, għandek bejn wieħed u ieħor ta 'proċess lineari ikkupjar ħin li jeħtieġ li jiġri minn array qadima lill ġdida. U r-realtà qed titlob lill operattiva sistema għal darb'oħra u għal darb'oħra u għal darb'oħra għal biċċiet kbar ta 'memorja tista' tibda jiswik xi żmien ukoll. Allura huwa kemm barka u curse fl jaħbi, il-fatt li dawn arrays huma ta 'daqs fiss. Imma jekk aħna jintroduċu minflok xi ħaġa bħal dan, li aħna imsejħa linked lista, irridu jiksbu upsides u ftit ftit negattivi hawnhekk ukoll. 

Allura lista marbut huwa sempliċement data struttura ffurmata minn structs C f'dan każ, fejn Struct, recall, huwa biss kontenitur għal wieħed jew aktar speċifiċi tipi ta 'varjabbli. F'dan il-każ, liema do tip ta 'data jidhru li huma ġewwa tal-Struct li aħħar darba aħna tissejjaħ node? Kull wieħed minn dawn rettangoli huwa node. U kull wieħed mill-rettangoli iżgħar ġewwa ta 'dan huwa tip ta' data. Liema tipi aħna ma jgħidu kienu nhar it-Tnejn? Yeah? 

STUDENT: [inaudible]. 

SPEAKER 1: A varjabbli u werrej, jew b'mod aktar speċifiku, l-int, għal n, u werrej fil-qiegħ. Kemm ta 'dawk jinzertaw 32 bits, fil inqas fuq il-kompjuter bħal dan CS50 Appliance, u allura jkunu mfassla ugwalment fid-daqs. 

Allura dak qed jużaw il-pointer għalkemm għal apparentement? Għaliex żid din vleġġa issa meta arrays kienu hekk sbieħ u nodfa u sempliċi? X'inhu l-pointer tagħmel għal us f'kull wieħed minn dawn lymph? 

STUDENT: [inaudible]. 

SPEAKER 1: Eżattament. Huwa javżak fejn inti il-wieħed li jmiss huwa. So I sort tal-użu l-analoġija ta ' użu ta 'ħajt li sort ta' ħajt dawn lymph flimkien. U dan huwa eżattament dak li aħna qed tagħmel mal- pointers għax kull wieħed minn dawn biċċiet ta 'memorja tista' jew ma jistgħux ikunu kontigwa, lura lura lura ġewwa ta 'RAM, minħabba li kull darba li inti sejħa malloc qal, agħti lili biżżejjed bytes għal node ġdid, dan jista 'jkun jkun hawn jew jista 'jkun hawn. Jista 'jkun hawn. Jista 'jkun hawn. Inti biss ma nafx. 

Iżda bl-użu pointers fl-indirizzi ta ' ta'dawk il-lymph, inti tista stitch minnhom flimkien b'mod li jistenna viżwalment bħal lista anke jekk dawn l-affarijiet huma kollha mifruxa matul wieħed tiegħek jew tnejn tiegħek jew erba gigabytes ta 'RAM tiegħek ġewwa tal-kompjuter tiegħek. 

Allura l-tnaqqis, allura, lista marbut huwa dak? X'hemm prezz aħna qed apparentement ħlas? 

STUDENT: [inaudible]. 

SPEAKER 1: aktar spazju, id-dritt? Imxejna, f'dan il-każ, rdoppja l-ammont ta 'spazju għax konna marret minn 32 bits għal kull node, għal kull int, hekk issa 64 bits għaliex għandna biex iżommu madwar pointer ukoll. Ikollok aktar effiċjenza jekk Struct tiegħek hija akbar minn dan il-ħaġa sempliċi. Jekk inti fil-fatt ikollhom student ġewwa tagħhom huwa ftit kordi għall isem u d-dar, forsi numru ta 'ID, forsi xi oqsma oħra għal kollox. 

Mela jekk għandek Struct kbir biżżejjed, allura forsi l-ispiża ta 'l-pointer huwa mhux tali big deal. Dan huwa daqsxejn ta 'każ kantuniera f'dak aħna qed jaħżnu tali sempliċi primitive ġewwa tal-lista marbuta. Imma l-punt huwa l-istess. Int żgur infiq aktar memorja, imma int jkollna flessibilità. Għaliex issa jekk irrid li jiżdied element fil-bidu ta din il-lista, I jridu jallokaw node ġdid. U I għandhom jaġġornaw biss dawk vleġeġ b'xi bi ftit li jiċċaqalqu xi indikazzjonijiet madwar. 

Jekk irrid li daħħal xi ħaġa fil- nofs tal-lista, I ma jkollhom imbotta kulħadd aside bħal għamilna fl passat ġimgħat ma 'voluntiera tagħna li rrappreżentaw firxa. I tista 'biss jalloka node ġdid u allura biss il-punt l-vleġeġ fil direzzjonijiet differenti minħabba li ma għandhom jibqgħu fl attwali memorja linja vera bħal stajt mfassla dan hawn fuq l-iskrin. 

U mbagħad fl-aħħar, jekk inti tixtieq li daħħal xi ħaġa fl-aħħar tal-lista, huwa anke eħfef. Dan huwa tip ta 'notazzjoni arbitrarja, iżda 34 ta pointer, tieħu raden. X'inhu l-valur tal-pointer tagħha aktar probabbli tip mislut ta qisni antik antenna iskola hemmhekk? 

STUDENT: [inaudible]. 

SPEAKER 1: Huwa probabbilment null. U fil-fatt li hija awtur wieħed rappreżentazzjoni ta null. U huwa null għaliex inti assolutament bżonn tkun taf fejn it-tmiem ta 'linked lista hija, lest inti żżomm ġejjin u wara u wara dawn vleġeġ li xi valur żibel. Allura null ikun ifisser li hemm l-ebda aktar lymph għad-dritt ta numru 34, f'dan il-każ. 

Allura aħna nipproponu li nistgħu jimplimentaw dan node fil-kodiċi. U aħna stajt tidher dan it-tip ta 'sintassi qabel. Typedef biss jiddefinixxi tip ġdid għall us, tagħtina sinonimu bħal string kien għal char *. F'dan il-każ, li għaddej biex tagħtina notazzjoni shorthand sabiex node Struct jistgħu minflok biss jinkiteb bħala node, li hija nadifa ħafna. Huwa ħafna inqas verbose. 

Ġewwa ta 'node huwa apparentement int imsejħa n, u mbagħad Struct node * li jfisser eżattament dak li ridna l- vleġeġ li jfisser, a pointer għall-ieħor node tal-istess tip data eżatta. U nipproponi li nistgħu jimplimentaw funzjoni ta 'tfittxija bħal dan, li minnhom mill- ewwel daqqa t'għajn jista 'jidher ftit kumplessi. Imma ejja tara li fil-kuntest. 

Let me go fuq l-appliance hawn. Let me jiftħu fajl imsejjaħ lista zero dot h. U li fih biss id-definizzjoni aħna biss raw mument ilu għal din id-data tip imsejħa node. Allura konna li jitqiegħdu fis-fajl h dot. 

U bħala twarrib, anke jekk din programm li int ser tara hija mhux kollha li kumplessi, huwa tabilħaqq konvenzjoni meta tikteb programm biex tpoġġi affarijiet simili tipi ta 'data, għal pull kostanti kultant, ġewwa ta 'tiegħek fajl tal-header u mhux neċessarjament fajl C tiegħek, ċertament meta tiegħek programmi tikseb akbar u akbar, sabiex inti taf fejn tfittex kemm għall dokumentazzjoni f'xi każijiet, jew għal affarijiet bażiċi bħal dan, il- definizzjoni ta 'xi tip. 

Jekk I issa jiftħu lista zero dot c, avviż ftit affarijiet. Dan jinkludi fajls header ftit, ħafna li konna rajna qabel. Dan jinkludi fajl header tagħha stess. 

U bħala twarrib, għaliex dan huwa doppju kwotazzjonijiet hawn, għall-kuntrarju l-angolu parentesi fuq il-linja li Stajt enfasizzat hemmhekk? 

STUDENT: [inaudible]. 

SPEAKER 1: Yeah dan huwa fajl lokali. Mela jekk huwa fajl lokali tal tiegħek hawn fuq il-linja 15, per eżempju, tuża il-kwotazzjonijiet doppja minflok ta 'l-parentesi angolati. 

Issa dan huwa tip ta 'interessanti. Avviż li stajt ddikjarat globali varjabbli f'dan il-programm fuq il-linja 18 imsejħa ewwel, l-idea hija li dan huwa se tkun pointer għall-ewwel node fil-lista linked tiegħi, u stajt initialized li null, għaliex stajt mhux allokat ebda attwali lymph biss s'issa. 

Allura dan jirrappreżenta, pictorially, dak li aħna raw mument ilu fl-istampa kif li pointer fuq il-bogħod xellug naħa. Allura issa dritt, li pointer ma jkollux vleġġa. Huwa minflok huwa biss null. Imma jirrappreżenta x'se jkunu l- indirizz ta 'l-ewwel attwali node f'din il-lista. Allura stajt implimentati hija globali għaliex, kif tkun taf tara, dan kollu programm ma fil-ħajja huwa implimentat lista marbuta għalija. 

Issa stajt ltqajna prototipi ftit hawn. I iddeċieda li jimplimenta karatteristiċi simili tħassir, inserzjoni, it-tiftix, u traversal - l-aħħar walk sempliċement madwar il- lista, stampar elementi tagħha. U issa hawnhekk rutina prinċipali tiegħi. U aħna mhux se jqattgħu wisq ħin fuq dawn peress li dan huwa tip ta ', wieħed jittama hat qodma minn issa. 

Jien ser tagħmel dan li ġej, filwaqt li l-utent tikkoopera. Allura wieħed, jien ser jistampaw out dan il-menu. U stajt formattjati bħala nadif kif stajt. Jekk tipi l-utent fil-wieħed, dan ifisser huma jridu li jitħassar xi ħaġa. Jekk tipi l-utent fi tnejn, li jfisser li jkunu jridu xi ħaġa daħħal. U oħrajn. Jien ser imbagħad fil-pront imbagħad għal kmand. U allura jien ser tuża GetInt. 

Allura dan huwa verament sempliċi menuing interface fejn inti sempliċiment għandek tip immappjar numru li wieħed ta 'dawk jikkmanda. U issa għandi swiċċ nadif sbieħ dikjarazzjoni li għaddej biex jaqilbu fuq ikun x'ikun l-utent ittajpjat pulzieri U jekk dawn ittajpjat waħda, I ser sejħa iħassru u break. Jekk dawn ittajpjat tnejn, I ser sejħa daħħal u kisser. 

U issa avviż stajt jitqiegħdu f'kull ta 'dawn fuq l-istess linja. Din hija biss deċiżjoni stilistiċi. Tipikament Rajna xi ħaġa bħal dan. Imma I biss iddeċieda, franchement, program tiegħi ħares aktar tinqara minħabba kien erba 'każijiet biss biss lista hija bħal dan. Użu Totally leġittimu ta 'stil. U jien se tagħmel dan sakemm il- user ma ittajpjat żero, li jiena iddeċieda se jfisser li jixtiequ jieqfu. 

Allura issa avviż dak li jien se nagħmlu hawnhekk. Jien ser tillibera l-lista apparentement. Iżda aktar fuq li fi ftit mument. Ejja ewwel run dan il-programm. So let me tagħmel terminal akbar tieqa, dot lista slash 0. Jien ser jimxi 'l quddiem u daħħal minn ittajpjar tnejn, numru bħall 50, u issa int ser tara l-lista issa huwa 50. U t-test tiegħi biss impress up a bit. Allura issa avviż-lista fiha in-numru 50. 

Ejja nagħmlu daħħal ieħor billi tieħu tnejn. Ejja tip fil-numru wieħed bħal. Lista issa huwa wieħed, segwit minn 50. Allura din hija biss rappreżentazzjoni testwali tal-lista. U ejja jdaħħal waħda aktar numru simili in-numru 42, li huwa wieħed jittama ser jispiċċaw fin-nofs, għax dan il-programm xorta partikolari li elementi kif huwa introduċa minnhom. Allura hemm aħna għandna hija. Programm sempliċi super li jistgħu assolutament użaw firxa, iżda I jiġri li tkun qed tuża lista linked biss hekk nista dinamiku jikbru u tiċkien dan. 

Mela ejja tagħti ħarsa għal tfittxija, jekk I run kmand tlieta, I trid tfittex għal, ngħidu aħna, in-numru 43. U xejn jidher li kien sab, minħabba I marret lura ebda risposta. Mela ejja jagħmlu dan mill-ġdid. Fittex. Ejja tfittxija għal 50, jew pjuttost tfittxija għal 42, li għandha sbieħ ftit tifsira sottili. U sibt it-tifsira tal-ħajja hemmhekk. Numru 42, jekk ma tafx ir-referenza, Google dan. Kull dritt. Allura dak li dan il-programm isir għalija? Huwa biss permessi me daħħal b'hekk bogħod u tfittxija għal elementi. 

Ejja fast quddiem, imbagħad, li dik il-funzjoni aħna glanced fi nhar it-Tnejn bħala teaser. Allura din il-funzjoni, nitlob, tfittxijiet għal element fil-lista b'nota ewwel waħda, li wassal lill-utent u mbagħad sejħa GetInt biex tikseb int attwali li inti trid tfittex għal. 

Imbagħad Avviż dan. Jien ser toħloq varjabbli temporanju f'konformità 188 imsejjaħ pointer - PTR - setgħet hija imsejħa xejn. U huwa pointer għal node minħabba I qal node * hemmhekk. U jien initializing li jkun ugwali għal ewwel sabiex I effettivament jkollhom tiegħi swaba ', biex ngħidu hekk, fuq il-ħafna ewwel element tal-lista. Mela jekk lemin tiegħi hawnhekk huwa PTR jien tipponta lejn l-istess ħaġa li l-ewwel hija li tipponta lejn. 

Allura issa lura fil-kodiċi, dak li jiġri li jmiss - din hija paradigma komuni meta iterazzjoni fuq struttura bħal lista marbuta. Jien ser jagħmlu dan li ġej waqt li pointer mhuwiex ugwali għal null Għalhekk, filwaqt li finger tiegħi mhix tipponta lejn uħud null valur, jekk pointer vleġġa n ugwali n. Aħna ser ikollok avviż l-ewwel li n huwa dak li l- utent ittajpjat fil kull GetInts sejħa hawn. 

U pointer vleġġa n ifisser liema? Ukoll jekk immorru lura għall-istampa hawn, jekk ikolli saba tipponta lejn li l-ewwel node fih disa ', l- vleġġa essenzjalment tfisser tmur f'dak node u grab l-valur fil-lokalità n, f'dan il-każ, il-kaxxa tad-dejta imsejħa n. 

Bħala twarrib - u aħna raw dan koppja ta 'ġimgħat ilu meta xi ħadd talab - dan sintassi huwa ġdid, iżda ma agħtina poteri li aħna ma diġà għandhom. Liema kienet din il-frażi ekwivalenti għall-użu dot notazzjoni u star koppja ta 'ġimgħat ilu meta aħna imqaxxar lura dan is-saff daqsxejn prematur? 

STUDENT: [inaudible]. 

SPEAKER 1: Eżattament, kien star, u mela kien star dot n, ma parentesi hawn, li jistenna, franchement, I think ħafna aktar cryptic biex jinqara. Iżda star pointer, bħal dejjem, mezzi jmorru hemm. U ladarba int hemm, liema data qasam tridu taċċessaha? Well inti tuża l-notazzjoni dot għall-aċċess qasam ta 'data structs, u I tixtieq speċifikament n. 

Franchement, nixtieq jargumentaw li dan huwa biss aktar diffiċli biex jinqara. Huwa diffiċli li tiftakar fejn jagħmlu l-parentesi go, l- star u kollha ta 'dak. Allura l-dinja adottata xi sintattika zokkor, biex ngħidu hekk. Biss mod ta 'tgħid sexy, dan huwa ekwivalenti, u forsi aktar intuwittivi. Jekk pointer huwa tabilħaqq pointer, l- vleġġa mezzi notazzjoni jmorru hemm u jsibu il-qasam f'dan il-każ imsejjaħ n. 

Mela jekk jien jsibuha, avviż dak I do. I sempliċiment jistampa, sibt fil-mija i, fejn jitwaħħal fil-valur għal dak int. I call irqad għat-tieni waħda biss biex tip ta 'affarijiet nieqaf fuq l-iskrin biex jagħti lill-utent t-tieni biex jassorbu dak li ġara biss. U mbagħad I break. Inkella, x'għandi nagħmel? I taġġorna pointer li ugwali pointer vleġġa li jmiss. 

Hekk biss li jkun ċar, dan ifisser go hemm, bl-użu notazzjoni qodma l-iskola tiegħi. Allura dan ifisser biss li jmorru għal dak kollu li int tipponta lejn, li fil-ħafna ewwel każ huwa jien li tipponta lejn l Struct b'disa fiha. Allura stajt marret hemmhekk. U allura l-notazzjoni dot jfisser, jiksbu l-valur li jmiss. 

Iżda l-valur, anki jekk huwa mfassal bħala dejqa, huwa biss numru. Huwa indirizz numeriku. Allura din il-linja waħda tal-kodiċi, jekk bil-miktub bħal dan, l-aktar cryptic mod, jew bħal dan, il-ftit aktar mod intuwittivi, ifisser biss jiċċaqalqu naħa tiegħi mill-ewwel node għal dak li jmiss, u allura l-waħda li jmiss, u mbagħad l- jmiss waħda, u ibqa 'sejjer hekk. 

Allura aħna mhux se nitkellem fuq l-oħra implimentazzjonijiet tal daħħal u ħassar u traversal, l-ewwel tnejn li huma involuti b'mod ġust. U naħseb huwa pjuttost faċli li tinkiseb mitluf meta tagħmel dan verbalment. Imma dak li nistgħu nagħmlu hawnhekk huwa jippruvaw jiddeterminaw kif aħjar li tagħmel dan viżwalment. Minħabba Nixtieq nipproponi li jekk irridu tixtieq li daħħal elementi fis dan elenku eżistenti, li għandha ħames elementi - 9, 17, 22, 26, u 33 - jekk jien kienu se jimplimentaw dan kodiċi, I bżonn li jiġi kkunsidrat kif imorru dwar kif isir dan. 

U jiena nipproponi tieħu passi tarbija fejn, f'dan il-każ I mean, liema huma ix-xenarji possibbli li aħna tista 'tiltaqa b'mod ġenerali? Meta jimplimentaw daħħal għal linked lista, dan jiġri biss li jkun eżempju speċifiku ta 'daqs ħamsa. Ukoll jekk inti tixtieq li daħħal numru, bħall jgħidu n-numru wieħed, u żamma tal-ordni magħżula, fejn ovvjament ma l-numru wieħed jeħtieġ li jmorru f'dan l-eżempju speċifiku? Bħal fil-bidu. 

Imma x'hemm interessanti hemm li jekk inti tixtieq li daħħal wieħed fis dan lista, liema pointer speċjali jeħtieġ li jiġu aġġornati apparentement? Ewwel. Hekk nixtieq jargumentaw, dan huwa l-ewwel każ li aħna tista 'tixtieq li jikkunsidraw, għal xenarju li jinvolvi ddaħħal fil il-bidu tal-lista. 

Ejja ġewwieni off forsi bħala faċli jew saħansitra każ aktar faċli, relattivament speaking. Jissoponi Irrid li daħħal il- numru 35 sabiex magħżula. Ovvjament jappartjeni hemmhekk. Allura dak pointer ovvjament se għandhom jiġu aġġornati f'dak ix-xenarju? 34 ta pointer ssir mhux null iżda l-indirizz tal-Struct bin-numru 35. Allura dak il-każ tnejn. Allura diġà, jien tip ta 'quantizing kemm ix-xogħol li nagħmel hawn. 

U fl-aħħarnett, il-każ tan-nofs huwa ovvju tabilħaqq, fin-nofs, jekk irrid daħħal xi ħaġa simili jgħidu 23, li tmur bejn il-23 u l-26, iżda issa l-affarijiet jiksbu ftit aktar involuti għaliex dak pointers jeħtieġ li jinbidlu? Allura ovvjament 22 teħtieġ li tinbidel għaliex ma jista 'jiġbed l-26 jibqgħalu. Hu għandu bżonn biex jindikaw il-node ġdida li I ser ikollhom jallokaw billi ċċempel malloc jew xi ekwivalenti. 

Imma mbagħad I wkoll bżonn li node ġdid, 23 f'dan il-każ, li jkollha pointer tagħha tipponta lejn min? 26. U hemm għaddej biex tkun ordni ta 'operazzjonijiet hawn. Għaliex jekk nagħmel dan foolishly, u I per eżempju bidu fil-bidu ta ' il-lista, u l-għan tiegħi huwa li daħħal 23. And I check, ma jappartjenix hawn, ħdejn disa? No Ma jagħmlu parti minn hawn, li jmiss 17? No Ma jappartjeni hawn jmiss 22? Iva. 

Issa jekk jien foolish hawn, u mhux ħsieb dan permezz, I jista jallokaw node ġdida tiegħi għal 23. I tista 'taġġorna l-pointer minn l-node imsejħa 22, tipponta huwa fil-node ġdid. U allura dak li għandi jkollhom jaġġornaw pointer l-node ġdid li jkun? 

STUDENT: [inaudible]. 

SPEAKER 1: Eżattament. Tipponta lejn 26. Imma Dammit jekk I ma diġà taġġorna Pointer 22 għall-punt fuq dan Guy, u issa għandi orfni, l-bqija tal-lista, biex ngħidu hekk. Allura ordni ta 'operazzjonijiet hawn se tkun importanti. 

Biex tagħmel dan jista I steal, jiġifieri, sitt voluntiera. U ejja ara jekk aħna ma tistax tagħmel dan viżwalment minflok kodiċi għaqli. U aħna għandna xi stress sabiħ blalen għalik illum. OK, kif madwar wieħed, tnejn, fil- lura - fuq l-aħħar hemmhekk. tlieta, erba, tnejn inti guys fuq l-aħħar. U ħamsa, sitta. Sure. Ħames u sitt. Kull dritt u aħna ser jiġu lilek guys ħin li jmiss. Kull dritt, come fuq up. 

Kull dritt, peress li int up here ewwel, kieku inti tixtieq li jkun il-wieħed awkwardly fil-Google Glass hawn? Kull dritt, hekk, OK, ħġieġ, jirreġistra video. OK, int tajba biex tmur. 

Kull dritt, hekk jekk inti guys jista 'jidħol fuq hawn, I ippreparat bil-quddiem xi numri. Kull dritt, come fuq matul hawn. U għaliex ma inti tmur ftit wkoll li mod. U ejja ara, x'hemm isem tiegħek, mal-Google Glass? 

STUDENT: Ben. 

SPEAKER 1: Ben? OK, Ben, inti ser tkun l-ewwel, litteralment. Allura aħna qed tmur biex inti tibgħat sat-tmiem tal-istadju. Kull dritt, u l-isem tiegħek? 

STUDENT: Jason. 

SPEAKER 1: Jason, OK inti ser jkun in-numru disgħa. Mela jekk inti tixtieq li ssegwi Ben mod. 

STUDENT: Jill. 

SPEAKER 1: Jill, int ser tkun 17, li jekk I d ​​jsir dan aktar intelliġenti, I jkollhom bdiet fl-aħħar oħra. Inti tmur il-mod. 22. U inti? 

STUDENT: Mary. 

SPEAKER 1: Mary, inti ser tkun ta '22. U l-isem tiegħek huwa? 

STUDENT: Chris. 

SPEAKER 1: Chris, inti ser tkun 26. U mbagħad fl-aħħar. 

STUDENT: Diana. 

SPEAKER 1: Diana, inti ser tkun 34. Allura inti come fuq matul hawn. 

Kull dritt, hekk perfetta magħżula tordna diġà. U ejja imorru quddiem u tagħmel dan sabiex inkunu nistgħu verament - Ben int biss tip ta 'tħares barra fil mkien hemmhekk. OK, so ejja imorru quddiem u juru dan użu l-armi, simili ħafna I kien, eżattament, x'inhu għaddej. Allura aqbad u jagħtu yourselves a sieq jew tnejn bejn yourselves. U jimxi 'l quddiem u l-punt b'id waħda biex min inti għandek tkun tipponta lejn ibbażata fuq dan. U jekk int null biss il-punt straight isfel sa l-art. OK, hekk tajjeb. 

Allura issa għandna lista marbuta, u let me jipproponi li jien ser jkollhom rwol ta ' PTR, so I mhux se jolqot jġorru dan madwar. U mbagħad - konvenzjoni stupid xi ħadd - inti tista 'sejħa dan xi ħaġa li trid - predeċessur pointer, pointer Pred - huwa biss l-laqam aħna taw fl kodiċi kampjun tagħna biex naħa tax-xellug tiegħi. Naħa l-oħra li se tkun żamma kont ta 'min huwa min fil- wara xenarji. 

Allura suppose, l-ewwel, nixtieq li ġewwieni off li l-ewwel eżempju ta 'ddaħħal, jgħidu 20, fil-lista. Hekk jien ser bżonn xi ħadd li titlaħħam in-numru 20 għalina. So I bżonn xi ħadd malloc mill-udjenza. Come fuq up. X'hemm isem tiegħek? 

STUDENT: Brian. 

SPEAKER 1: Brian, id-dritt, sabiex inti għandu jkun l-node li jkun fiha 20. Kull dritt, come fuq matul hawn. U ovvjament, fejn ma Brian jappartjenu? Għalhekk, fin-nofs ta '- fil-fatt, stenna minuta. Aħna qed tagħmel dan out of order. Aħna qed jagħmlu dan ħafna aktar diffiċli milli jeħtieġ li jkun fl-ewwel. OK, aħna qed tmur biex ħielsa Brian u realloc Brian bħala ħamsa. 

OK, hekk issa irridu li daħħal Brian bħala ħamsa. Allura ġejjin fuq matul hawn jmiss Ben għal ftit mument. U inti tista 'tgħid preżumibbilment fejn din l-istorja huwa għaddej. Imma ejja jaħseb sew dwar l-ordni ta 'operazzjonijiet. U huwa preċiżament dan viżwali li għaddej biex line up ma dan il-kodiċi tal-kampjun. So here I PTR tipponta inizjalment mhux fil Ben, per se, iżda fi kwalunkwe valur huwa fih, li f'dan il-każ hu - dak l-isem tiegħek mill-ġdid? 

STUDENT: Jason. 

SPEAKER 1: Jason, hekk kemm Ben u I huma tipponta lejn Jason f'dan il-mument. Allura issa għandi biex jiddeterminaw, fejn ma Brian jappartjenu? Allura l-unika ħaġa I jkollhom aċċess għal dritt issa huwa tiegħu partita data n. Hekk jien ser jiċċekkja, huwa Brian inqas minn Jason? It-tweġiba hija veru. 

Allura dak li issa jeħtieġ li jiġri, fl-ordni korretta? I bżonn jaġġornaw kemm pointers b'kollox f'din l-istorja? Fejn naħa tiegħi għadu tipponta lejn Jason, u l-idejn tiegħek - jekk inti tixtieq li idek simili, tip ta ', I ma jafux, kwistjoni mark. OK, tajba. 

Kull dritt, hekk ikollok xi kandidati ftit. Jew Ben jew I jew Brian jew Jason jew kulħadd, li pointers bżonn għall-bidla? Kemm b'kollox? 

OK, hekk tnejn. Pointer My ma verament kwistjoni jibqgħalu għaliex jien biss temporanju. Allura huwa dawn iż-żewġ guys, preżumibbilment, kemm Ben u Brian. So let me tipproponi li aħna aġġornament Ben, peress li huwa l-ewwel. L-ewwel element ta 'din il-lista issa se tkun Brian. Allura punt Ben fuq Brian. OK, issa liema? 

Min gets mfakkar fil min? 

STUDENT: [inaudible]. 

SPEAKER 1: OK hekk Brian għandha jindikaw lejn Jason. Imma I tilfu rekord ta 'dak pointer? Inkun naf fejn Jason hu? 

STUDENT: [inaudible]. 

SPEAKER 1: I do, peress li jien il-pointer temporanju. U preżumibbilment, I ma nbidlux għall-punt fil-node ġdid. Allura nistgħu sempliċiment punt Brian fil min jien tipponta lejn. U aħna qed isir. Allura f'każ wieħed, inserzjoni fil- bidu tal-lista. Kien hemm żewġ passi. Wieħed, għandna biex jaġġornaw Ben, u mbagħad irridu wkoll biex taġġorna Brian. U allura jien ma għandekx li jolqot traipsing permezz tal-bqija tal- lista, għaliex aħna diġà sabet tiegħu post, minħabba li jappartjeni lill- xellug tal-ewwel element. 

Kull dritt, hekk pjuttost sempliċi. Fil-fatt, iħoss bħal aħna qed kważi jagħmlu dan wisq ikkumplikat. Mela ejja issa ġewwieni off-aħħar tal-lista, u ara fejn il-kumplessità jibda. Mela jekk issa, I alloc mill-udjenza. Kull min jixtiequ li jilagħbu 55? Kull dritt, I raw idejn tiegħek l-ewwel. Come fuq up. Yeah. X'hemm isem tiegħek? 

STUDENT: [inaudible]. 

SPEAKER 1: Habata. OK, come fuq up. Int ser tkun in-numru 55. Allura inti, naturalment, jappartjenu fl-aħħar tal-lista. Mela ejja replay-simulazzjoni miegħi huwa l-PTR għal ftit mument. Hekk jien ser ewwel punt fuq kwalunkwe Ben tipponta lejn. Aħna kemm tipponta issa fil Brian. Allura 55 ma jkunx inqas minn ħamsa. Hekk jien ser taġġorna myself mill tipponta lejn pointer li jmiss Brian, li issa huwa ta 'kors Jason. 55 ma jkunx inqas minn disa ', sabiex Jien ser taġġorna PTR. Jien ser taġġorna PTR. Jien ser taġġorna PTR I ser taġġorna PTR. U jien ser - hmm, x'hemm isem tiegħek mill-ġdid? 

STUDENT: Diana. 

SPEAKER 1: Diana hija li tipponta, naturalment, fil null mal-xellug tagħha. Għalhekk, fejn ma Habata attwalment jappartjenu b'mod ċar? Biex ix-xellug, hawnhekk. Allura kif inkun naf li jitqiegħdu tagħha Here I think stajt invitat up. Għaliex dak li hu PTR art dan il-mument fil-ħin? Null. Allura anke jekk, viżwalment, nistgħu ovvjament tara kollha ta 'dawn guys hawn fuq il-palk. Stajt ma żammitx rekord ta 'qabel persuna fil-lista. I ma jkollhom finger tipponta out, f'dan il-każ, in-numru node 34. 

Mela ejja attwalment jibdew dan fuq. Allura issa I attwalment do bżonn varjabbli lokali tieni. U dan huwa dak li inti ser tara fil- kampjun kodiċi attwali C, fejn kif mmur, meta I taġġorna lemin tiegħi għall-punt Jason, b'hekk tħalli Brian lura, I aħjar tibda tuża naħa tax-xellug tiegħi biex jaġġornaw fejn I kien, tant li bħala mmur permezz din il-lista - aktar awkwardly minn I maħsuba issa hawn viżwalment - Jien ser tikseb l- aħħar tal-lista. 

Dan idejn għadu null, li huwa pjuttost inutli, jekk mhux biex tindika Jien b'mod ċar fl-aħħar tal-lista, iżda issa mill-inqas I jkollhom din predeċessur pointer tipponta hawn, so issa dak idejn u dak pointers bżonn li jiġu aġġornati? Li naħa tridu jikkonfiguraw mill-ewwel? 

STUDENT: [inaudible]. 

SPEAKER 1: OK, so tal Diana. Fejn tridu punt Pointer xellug Diana fi? Fil-55, preżumibbilment, b'tali mod li konna jiddaħħal hemmhekk. U fejn għandhom 55 pointer tmur? Down, li jirrappreżentaw null. U l-idejn tiegħi, f'dan il-punt, ma jimpurtax għax kienu biss varjabbli temporanji. Allura issa aħna qed isir. 

Allura l-kumplessità addizzjonali hemmhekk - u mhuwiex li diffiċli biex tiġi implimentata, imma għandna bżonn varjabbli sekondarji li jagħmlu żgur li qabel I jiċċaqalqu lemin tiegħi idejn, I taġġorna l-valur tal tax-xellug tiegħi idejn, pointer Pred f'dan il-każ, hekk li għandi pointer batuta li jżommu rekord ta 'fejn I kien. Issa bħala aside, jekk inti qed jaħsbu dan permezz, dan iħoss bħal din hija ftit annoying li jkollhom biex iżommu track ta 'din id ix-xellugija. 

X'għandu soluzzjoni oħra li din il-problema kienu? Jekk inti ltqajna biex disinn mill-ġdid l-informazzjoni istruttura aħna qed jitkellem permezz dritt issa? Jekk dan it-tip biss ta iħoss ftit annoying li jkollhom, bħal, żewġ pointers għaddejjin mill-lista, li inkella jista ' jkunu, f'dinja ideali, miżmuma informazzjoni li għandna bżonn? Yeah? 

STUDENT: [inaudible]. 

SPEAKER 1: Eżattament. Dritt hekk hemm attwalment interessanti nibbieta ta 'idea. U din l-idea ta 'pointer preċedenti, tipponta lejn l-element ta 'qabel. X'jiġri jekk I biss inkorporati li ġewwa tal-lista nfisha? U li għaddej biex tkun diffiċli biex Ħares dan mingħajr il-karta jaqgħu l-art. Iżda jissoponi li dawn guys użat kemm ta 'l-idejn tagħhom li jkollhom preċedenti pointer, u werrej li jmiss, u b'hekk implimentazzjoni dak li aħna inneħħu sejħa doppjament lista marbuta. Dan jippermetti me biex issolvi ta kontrina, ħafna aktar faċilment mingħajr me, il- programmer, li jżommu track manwalment - verament manwalment - ta 'fejn I kien qabel fil-lista. Allura aħna mhux se tagħmel dan. Aħna ser jżommha sempliċi minħabba li l se jaqgħu fil-prezz, darbtejn ħafna spazju għall-pointers, jekk inti tixtieq tieni waħda. Imma dak li tassew komuni struttura tad-data magħrufa bħala doppjament marbuta lista. 

Ejja nagħmlu l-eżempju finali hawn u mqiegħda dawn guys 'miżerja tagħhom. Allura malloc 20. Come fuq up mill-aisle hemm. Kull dritt, x'hemm isem tiegħek? 

STUDENT: [inaudible]. 

SPEAKER 1: Jiddispjacini? 

STUDENT: [inaudible]. 

SPEAKER 1: Demeron? OK come fuq up. You għandhom ikunu 20. Inti ovvjament tmur jappartjenu bejn 17 u 22. So let me jitgħallmu lezzjoni tiegħi. Jien ser tibda pointer tipponta lejn Brian. U jien ser ikollhom naħa tax-xellug tiegħi jaġġornaw biss Brian bħala I jiċċaqalqu lejn Jason, verifika ma 20 inqas minn disa? No Hija 20 inqas minn 17? No Huwa inqas minn 20 22? Iva. Allura dak pointers jew idejn bżonn għall-bidla fejn dawn qed tipponta issa? 

Allura nistgħu nagħmlu 17 tipponta lejn 20. Allura li l-multa. Fejn irridu punt pointer tiegħek issa? Fuq 22. U nafu fejn 22 hija, għal darb'oħra grazzi biex pointer temporanju tiegħi. Allura aħna qed OK hemmhekk. Allura minħabba din il-ħażna temporanja Stajt jinżammu kont ta 'fejn kulħadd huwa. U issa inti tista 'viżwalment tmur fis fejn inti jappartjenu, u issa għandna bżonn 1, 2, 3, 4, 5, 6, 7, 8, 9 blalen stress, u rawnd ta 'applause għall dawn guys, jekk nistgħu. Nicely jsir. 

[Applause] 

SPEAKER 1: Id-dritt. U inti tista 'żżomm il-biċċiet ta 'karta kif mementos. 

Kull dritt, hekk, trust me huwa ħafna aktar faċli biex jimxu permezz li ma bnedmin milli huwa bil-kodiċi attwali. Imma dak li inti ser issib fi ftit mument issa, huwa l-istess - oh, nirringrazzjak. Grazzi - hija li inti ser issib li l-istess data istruttura, il-lista marbuta, jistgħu attwalment jintuża bħala element fil-bini biex saħansitra aktar strutturi ta 'dejta sofistikati. 

U jirrealizzaw wisq it-tema hawnhekk hija li konna assolutament introdotti aktar kumplessità fl-implimentazzjoni ta 'dan algoritmu. Inserzjoni, u jekk aħna marru permezz tagħha, tħassir u tiftix, huwa xi ftit aktar ikkumplikata milli kien ma 'firxa. Iżda aħna jiksbu xi dinamiżmu. Nikbru struttura data adattivi. 

Iżda għal darb'oħra, li nħallsu prezz ta 'wara xi kumplessità addizzjonali, kemm fl- implimentazzjoni tiegħu. U aħna qed jingħataw l-aċċess bl-addoċċ. U biex ikunu onesti, hemm mhux xi sbieħ nadif slide I jistgħu jagħtuk li jgħid hawnhekk huwa għaliex lista marbuta huwa aħjar minn firxa. U jitilqu minnu f'dik. Minħabba li l-tema reoccurring issa, anke iktar hekk fil-ġimgħat li ġejjin, huwa li hemm mhux neċessarjament risposta korretta. 

Dan huwa għaliex għandna l-assi separata ta 'disinn għal settijiet problema. Dan se jkun ferm kuntest sensittivi jekk inti tixtieq li tuża din id-data struttura jew li wieħed, u se jiddependu fuq liema materji lilek f'termini ta 'riżorsi u l-kumplessità. 

Iżda let me jipproponi li d-data ideali istruttura, l-Grail qaddis, ikun xi ħaġa li wasal iż-żmien kostanti, irrispettivament ta 'kemm għalf huwa ġewwa fih, ma kienx ikun aqwa jekk struttura tad-data lura tweġibiet fil- żmien kostanti. Iva. Din il-kelma hija fil enormi dizzjunarju tiegħek. Jew l-ebda, din il-kelma mhix. Jew kull problema simili hemmhekk. Well ejja ara jekk ma nistgħux inqas tieħu pass lejn dan. 

Let me tipproponi struttura ġdida data li jista 'jintuża għal affarijiet differenti, f'dan il-każ jissejjaħ tabella hash. U hekk aħna qed attwalment lura għall glancing fi array, f'dan il-każ, u kemmxejn arbitrarju, stajt mfassla dan tabella hash bħala firxa ma tip ta ' firxa żewġ dimensjonijiet - jew pjuttost huwa mpinġi hawn bħala żewġ firxa tridimensjonali - iżda dan huwa biss firxa ta 'daqs 26, b'tali mod li jekk aħna sejħa tal-mejda array, parentesi tabella żero hija l-rettangolu fil-quċċata. Bracket Tabella 25 hija l-rettangolu fil-qiegħ. U dan huwa kif I jista 'jiġbed data istruttura li nixtieq li jaħżen tan-nies ismijiet. 

Allura per eżempju, u jien mhux ser jiġbed l- ħaġa sħiħa hawn fuq il-overhead, jekk I kellha din array, li jien issa ser sejħa tabella hash, u dan huwa għal darb'oħra post żero. Dan hawnhekk huwa post waħda, u ibqa 'sejjer hekk. I jsostnu li nixtieq li jużaw din id-data istruttura, għall-fini ta 'diskussjoni, li jaħżen ismijiet tan-nies, Alice u Bob u Charlie u ismijiet oħra bħal dawn. Allura taħseb ta 'dan issa bħala l-bidu ta ', ngħidu aħna, dizzjunarju ma 'lottijiet ta' kliem. Ikunu jinzertaw ismijiet fl-eżempju tagħna hawn. U dan huwa wisq germane, forsi, li implimentazzjoni jespliċitaw kontrollur, kif aħna tista għal problema stabbiliti sitt. 

Hekk jekk għandna firxa ta 'daqs totali 26 għalhekk dan huwa l-post 25 fil-qiegħ, u I jsostnu li Alice huwa l-ewwel kelma fid-dizzjunarju ta ' ismijiet li nixtieq li daħħal fis RAM, fis din l-istruttura tad-data, fejn huma instincts tghidlek li Alice isem għandhom imorru f'dan firxa? 

Għandna 26 għażliet. Fejn irridu jitqiegħdu tagħha? Aħna tixtieq tagħha fil-bracket żero, id-dritt? A għall Alice, ejja sejħa li żero. U B se tkun waħda, u C se jkun tnejn. Allura aħna qed tmur biex jiktbu Isem Alice up here. Jekk aħna imbagħad daħħal Bob, tiegħu isem se jmorru hawn. Charlie se jmorru hawn. U oħrajn stabbiliti permezz din l-istruttura tad-data. 

Din hija struttura data wunderbare. Għaliex? Ukoll dak huwa l-ħin tmexxija ta ' ddaħħal l-isem ta 'bniedem fis dan data istruttura dritt issa? Peress li din it-tabella tiġi implimentata, verament, bħala firxa. Ukoll huwa żmien kostanti. Huwa ordni ta 'wieħed. Għaliex? 

Well kif taħseb li jiddeterminaw fejn Alice jappartjeni? Inti tħares lejn liema ittra ta 'isem tagħha? L-ewwel. U inti tista 'tikseb hemm, jekk huwa string, billi biss tħares lejn string bracket żero. Allura l-karattru 0 tas-sekwenza. Li faċli. Aħna ma li fil-kripto ġimgħat ilu assenjazzjoni. U allura ladarba inti taf li l-Alice ittra huwa l-kapital A, nistgħu naqqas off 65 jew kapital A innifsu, li jagħtina żero. Allura aħna issa jkunu jafu li Alice jappartjeni fil-post żero. 

U jingħataw pointer li din id-data istruttura, ta 'xi tip, kemm ma jieħdu me biex isibu post żero fil-firxa? Just pass wieħed, dritt Wasal iż-żmien kostanti minħabba l-aċċess bl-addoċċ aħna proposta kienet karatteristika ta 'firxa. Għalhekk fil-qosor, jidhru dak l-indiċi ta 'isem Alice huwa, li huwa, fil- F'dan il-każ, huwa A, jew ejja biss issolvi li għal żero, fejn B hija waħda u C hija tnejn, jidhru li minn huwa żmien kostanti. I sempliċiment għandek tfittex fl-ewwel ittra tagħha, jidhru fl fejn żero huwa array huwa wkoll żmien kostanti. Allura teknikament li l- bħal żewġ passi issa. Imma dak li għadu kostanti. Allura aħna sejħa li O kbir ta 'wieħed, hekk aħna ħadthom mdaħħal Alice fis din it-tabella fl żmien kostanti. 

Iżda naturalment, jien qed naive hawn, id-dritt? X'jiġri jekk hemm xi Aaron fil-klassi? Jew Alicia? Jew xi ismijiet oħra li tibda bil A. Fejn huma aħna se tpoġġi dik il-persuna, id-dritt? I mean, id-dritt issa hemm biss tlieta nies fuq il-mejda, hekk forsi aħna għandhom ipoġġu Aaron fuq post zero wieħed tnejn tlieta. 

Dritt, I tista 'tpoġġi A hawn. Iżda mbagħad, jekk nippruvaw li daħħal fis David din il-lista, fejn ma David imorru? Issa sistema tagħna jibda tkissir isfel, id-dritt? Minħabba li issa David jispiċċa here jekk Aaron huwa attwalment hawn. U hekk issa din l-idea kollu li jkun hemm struttura tad-data nadif li jagħtina inserzjonijiet ħin kostanti m'għadux ħin kostanti, minħabba I jkollhom jivverifikaw, oh, damnit, xi ħadd li diġà fil-post Alice. 

Let me sonda il-bqija ta 'din id-data istruttura, tfittex għal post biex xi ħadd bħall-isem Aaron. U għalhekk li wisq qed tibda li tieħu ħin lineari. Barra minn hekk, jekk inti issa tixtieq li ssib l- Aaron f'din l-istruttura tad-data, u inti jivverifikaw, u l-isem Aaron mhix hawn. Idealment, inti biss jgħidu li Aaron mhux fl-istruttura tad-data. Imma jekk inti tagħmel tibda tagħmel spazju għall- Aaron fejn kellu jkun hemm a D jew E, inti, agħar każ, għandhom jiċċekkjaw l-istruttura tad-data sħiħ, f'liema każ jaqa 'xi ħaġa lineari fid-daqs tat-tabella. 

Allura kull dritt, jien ser jiffissaw dan. Il-problema hawn hija li kelli 26 Elementi f'dan array. Let me jibdlu. Whoops. Let me bidla hekk li pjuttost li jkunu ta ' daqs 26 b'kollox, avviż-qiegħ indiċi huwa se jibdlu għal n minus 1. Jekk 26 huwa ċertament limitat wisq għall-bnedmin " ismijiet, għaliex hemm eluf ta ' ismijiet tad-dinja, ejja biss tagħmel f'100 jew 1,000 jew 10,000. Ejja biss jallokaw spazju ħafna aktar. 

Ukoll li ma mhux neċessarjament jonqsu il-probabbiltà li aħna mhux se jkollhom żewġ nies bl-ismijiet li jibda bl A, u hekk, inti kienu se tipprova tpoġġi A ismijiet fuq post żero għadhom. Dawn għadhom qed tmur biex jikkonfliġġu, li ifisser għad għandna bżonn soluzzjoni biex Alice u Aaron u Alicia u oħrajn ismijiet li jibda bl A x'imkien ieħor. Imma kemm ta 'problema hija din? X'hemm-probabbiltà li inti jkollhom kolliżjonijiet f'sett ta 'data istruttura bħal din? 

Well, let me - aħna ser terga 'lura għal din id-domanda hawn. U ħarsa lejn kif nistgħu issolvi l-ewwel. Let me pull up din il-proposta hawn. Dak li aħna biss deskritt huwa algoritmu, a heuristic imsejjaħ lineari probing fejn, jekk inti ppruvaw daħħal xi ħaġa hawn f'dan data istruttura, li tissejjaħ tabella hash, u hemm ebda kamra hemm, inti verament sonda tal-istruttura tad-data verifika, hija din disponibbli? Huwa dan Disponibbli huwa dan disponibbli? Huwa dan disponibbli? U meta finalment huwa, inti daħħal il- isem li inti oriġinarjament maħsub x'imkien ieħor f'dak il-post. Iżda fl-agħar każ, l-uniku post jista 'jkun il-qiegħ ħafna tad-dejta istruttura, l-aħħar nett tal-firxa. 

Allura lineari probing, fl-agħar każ, jaqa 'fi algoritmu lineari fejn Aaron, jekk jiġri li jiddaħħal aħħar f'din l-istruttura tad-data, huwa jista jikkonfliġġu ma 'dan l-ewwel post, imma mbagħad jispiċċaw minn xortih ħażina fl-aħħar ħafna. Allura dan mhux kostanti żmien qaddis grail għalina. Dan l-approċċ ta 'elementi li jdaħħlu fis struttura data msejħa hash it-tabella ma jidhirx li jkun żmien kostanti inqas mhux fil-każ ġenerali. Hija tista jaqgħu fis xi ħaġa lineari. 

Allura dak jekk aħna isolvu kolliżjonijiet kemmxejn differenti? Allura hawnhekk aktar sofistikati approċċ għall x'hemm għadu imsejħa tabella hash. U billi hash, bħala twarrib, liema I medja hija l-indiċi li I imsemmi qabel. Għal xi ħaġa hash jistgħu jkunu meqjusa bħala verb. 

Mela jekk inti hash Alice l-isem, funzjoni hash, biex ngħidu hekk, għandhom imorru lura numru. F'dan il-każ huwa żero jekk hi jappartjeni fil post żero, wieħed jekk hi jappartjeni fil post wieħed, u oħrajn. Allura funzjoni hash tiegħi s'issa kien super sempliċi, tħares biss lejn l- ewwel ittra fl-isem ta 'xi ħadd. Iżda funzjoni hash jieħu bħala input xi biċċa ta 'data, ta' string, l-int, ikun x'ikun. U spits out numru tipikament. U dak in-numru huwa fejn dik id-data element jappartjeni fi struttura data magħrufa hawnhekk bħala tabella hash. 

Hekk biss intuwittivament, dan huwa kuntest kemmxejn differenti. Dan fil-fatt hija tirreferi għal eżempju jinvolvu għeluq, fejn jista 'jkun hemm kemm 31 jum fix-xahar. Imma dak li ma din il-persuna tiddeċiedi li jagħmlu fil-każ ta 'ħabta? Kuntest issa qed, mhux ħabta ta ' ismijiet, iżda ħabta ta 'għeluq is-snin, jekk żewġ persuni jkollhom l-istess birthday fuq -2 ta 'Ottubru, per eżempju. 

STUDENT: [inaudible]. 

SPEAKER 1: Yeah, hekk hawn għandna l-lieva ta 'listi marbuta. Allura jidher ftit differenti milli fassalna qabel. Iżda aħna jidhru li jkollhom firxa fuq in-naħa tax-xellug. C'est indiċi waħda, għall-ebda partikolari raġuni. Iżda huwa għadu firxa. Huwa ta 'firxa ta' indikaturi. U kull wieħed minn dawk l-elementi, kull wieħed dawn ċrieki jew slashes - l-mmejla jirrappreżenta null - kull wieħed minn dawn pointers li apparentament huwa tipponta lejn liema struttura tad-data? Lista marbuta. 

Allura issa għandna l-ħila li kodiċi hard fil-programm tagħna id-daqs tat-tabella. F'dan il-każ, nafu hemm qatt aktar minn 31 jum fix-xahar. Tant diffiċli kodifikazzjoni valur bħal 31 huwa raġonevoli f'dak il-kuntest. Fil-kuntest ta 'ismijiet, iebsa kodifikazzjoni 26 mhuwiex irraġonevoli huwa poplu ismijiet tibda biss ma ', pereżempju, l-alfabett li jinvolvi A permezz Z. 

Nistgħu CRAM lilhom kollha fis li d-data istruttura sakemm, meta irridu jiksbu kolliżjoni, aħna ma tpoġġi l-ismijiet hawn, aħna minflok jaħsbu dawn iċ-ċelluli mhux bħala kordi nfushom, iżda bħala pointers għal, per eżempju, Alice. U allura Alice tista 'jkollha pointer ieħor għal isem ieħor li tibda bil A. U Bob fatt tmur minn hawn. 

U jekk hemm isem ieħor li jibda ma B, huwa jispiċċa hawn fuq. U għalhekk kull wieħed mill-elementi ta 'din tabella tnejn, jekk aħna ddisinjati dan ftit aktar cleverly - come fuq - jekk aħna mfassla dan aktar ftit cleverly, issa isir data adattivi struttura, fejn hemm ebda limitu hard fuq kemm elementi tista 'daħħal fis dan għaliex jekk inti do jkollhom ħabta, li l-multa. Just jimxi 'l quddiem u tehmeż lill dak rajna daqsxejn ilu kien magħrufa bħala lista marbuta. 

Well ejja nieqaf għal ftit mument. X'inhu l-probabbiltà ta 'ħabta fl-ewwel post? Dritt, forsi jien fuq ħsieb, forsi Jien fuq inġinerija din il-problema, għaliex inti taf liema? Iva, I tista 'toħroġ bi arbitrarja eżempji off-quċċata tar-ras tiegħi bħal Allison u Aaron, iżda fir-realtà, mogħtija distribuzzjoni uniformi ta ' inputs, jiġifieri xi inserzjonijiet każwali fi struttura tad-data, dak li huwa verament il-probabbiltà ta 'ħabta? Ukoll jirriżulta, huwa attwalment super għolja. Let me jiġġeneralizza din problema hija kif dan. 

Allura fil-kamra ta 'n CS50 istudenti, x'hemm il-probabbiltà li mill-inqas żewġ studenti fil-kamra jkollhom l-istess birthday? Allura hemm dak. a hund ftit - 200, 300 nies hawn u diversi mijiet ta 'nies fid-dar illum. Mela jekk int riedu li jistaqsu lilna nfusna x'hemm il-probabbiltà ta 'żewġ persuni f'din il-kamra li l-istess birthday, nistgħu figura dan. U nitlob attwalment hemm żewġ nies bl-istess birthday. 

Per eżempju, ħadd ma jkollhom birthday illum? Bieraħ? Għada? Kull dritt, hekk jħoss simili jien ser ikollhom jagħmlu dan 363 jew hekk aktar drabi biex attwalment insemmu jekk għandna ħabta. Jew nistgħu biss tagħmel dan matematikament minflok tediously tagħmel dan. U tipproponi dan li ġej. 

So nipproponi li nistgħu mudell l- probabbiltà ta 'żewġ persuni li jkollhom l- birthday istess bħall-probabbiltà ta '1 nieqes l-probabbiltà ta 'ebda wieħed li jkollu l-istess birthday. Allura biex tikseb dan, u dan huwa biss l- mod fancy ta 'din il-kitba, għall- ewwel persuna fil-kamra, hu jew hi jista 'jkollhom kwalunkwe waħda mill-possibbli għeluq ta 'snin jekk wieħed jassumi 365 jum fis-sena, ma apologies għal persuni il-birthday 29 Frar. 

Allura l-ewwel persuna f'din il-kamra huwa b'xejn li jkollha kwalunkwe numru ta 'għeluq ta' snin barra mill-365 possibiltajiet kollha sabiex aħna ser tagħmel dan 365 diviża 365, li hija waħda. Il-persuna li jmiss fil-kamra, jekk l-għan huwa biex tevita kolliżjoni, tista 'biss jkollhom birthday tiegħu jew tagħha dwar kif ħafna ġranet differenti possibbli? 364. Allura it-tieni terminu fil din l-espressjoni hija tagħmel essenzjalment li matematika għalina billi jitnaqqas off jum wieħed possibbli. U allura l-jum li jmiss, il-jum li jmiss, il- jum li jmiss sa l-għadd totali ta 'nies fil-kamra. 

U jekk aħna mbagħad tikkunsidra, liema allura huwa il-probabbiltà mhux ta 'kulħadd li għeluq uniku, iżda għal darb'oħra 1 nieqes li, dak li nagħmlu huwa espressjoni li jistgħu ħafna fancifully teżamina bħal dan. Iżda huwa aktar interessanti li tħares lejn viżwalment. Din hija chart fejn fuq l-assi x hu in-numru ta 'nies fil-kamra, l- numru ta 'għeluq ta' snin. Fuq il-y-axis hija l-probabilità ta 'ħabta, żewġ persuni jkollhom l-istess birthday. 

U l-takeaway minn din il-kurva huwa li hekk kif ikollok biex simili 40 istudenti, int up fuq probabbiltà 90% combinatorically ta 'żewġ persuni jew aktar li jkollhom l-istess birthday. U ladarba ikollok biex simili '58 persuni huwa kważi 100% ta 'opportunità it-tnejn nies fil-kamra huma se jkollhom l- birthday istess, għalkemm hemm 365 jew 366 bramel possibbli, u biss 58 nies fil-kamra. Just statistikament int x'aktarx li tikseb kolliżjonijiet, li fil-qosor jimmotiva din id-diskussjoni. Li anke jekk irridu jiksbu fancy hawn, u tibda jkollhom dawn il-ktajjen, aħna qed għadhom ser ikollhom kolliżjonijiet. 

Allura li iqajjem il-kwistjoni, liema huwa l- ispiża biex tagħmel inserzjonijiet u tħassir fi struttura data bħal din? Well let me tipproponi - u let me jmorru lura għall-iskrin fuq hawn - jekk għandna n-elementi fil- lista, hekk jekk aħna qed tipprova daħħal Elementi n, u għandna kemm bramel totali? Ejja ngħidu 31 bramel totali fil-każ ta 'għeluq ta' snin. X'hemm-tul massimu ta ' ta 'dawn il-ktajjen potenzjalment? 

Jekk darb'oħra hemm 31 possibbli għeluq fi żmien xahar partikolari. U aħna qed biss tagħqid kulħadd - attwalment li huwa eżempju stupid. Ejja nagħmlu 26 minflok. Mela jekk fil-fatt ikollhom nies li isimhom tibda bil A permezz Z, biex b'hekk us 26 possibbiltajiet. U aħna qed tuża struttura tad-data bħal l-waħda aħna biss raw, fejn għandna firxa ta 'pointers, li kull wieħed minnhom jindika lista linked fejn il- ewwel lista hija kulħadd bl-isem Alice. It-tieni lista hija kull ma 'l- isem li tibda bil A, li jibda ma B, u oħrajn. 

X'hemm-tul probabbli ta 'kull dawn il-listi jekk nassumu nadif sbieħ distribuzzjoni ta 'ismijiet A sa Z madwar l-istruttura kollha tad-data? Hemm nies fl-istruttura n data diviż b'26, jekk dawn qed nicely mifruxa fuq il-sħiħ struttura tad-data. Allura l-tul ta 'kull wieħed minn dawn ktajjen huwa n diviż bil 26. Iżda fil notazzjoni O big, dak huwa li? X'inhu li verament? Allura huwa verament ftit n, id-dritt? Għaliex aħna stajt qal fil-passat, li ugh inti iddividi 26. Iva, fir-realtà huwa aktar mgħaġġel. Iżda fit-teorija, mhuwiex fondamentalment dak kollu li aktar mgħaġġel. 

Allura aħna ma jidhirx li tkun kollha li ħafna eqreb lejn dan Grail qaddis. Fil-fatt, dan huwa biss darba lineari. Heck, f'dan il-punt, għaliex ma we biss użu wieħed lista enormi marbuta? Għaliex ma aħna biss użu wieħed enormi array biex jaħżnu l-ismijiet ta ' kulħadd fil-kamra? Ukoll, għad hemm xi ħaġa konvinċenti dwar tabella hash? Għad hemm xi ħaġa konvinċenti dwar struttura data li tidher bħal dan? Dan. 

STUDENT: [inaudible]. 

SPEAKER 1: Dritt, u għal darb'oħra jekk huwa biss żmien algoritmu lineari, u struttura tad-data ħin lineari, għaliex ma I biss taħżen isem kulħadd fit big array, jew lista kbir marbut? U tieqaf tagħmel CS tant diffiċli milli jeħtieġ li jkun? X'inhu konvinċenti dwar dan, anke għalkemm I scratched it out? 

STUDENT: [inaudible]. 

SPEAKER 1: inserzjonijiet mhumiex? Għaljin aktar. Allura inserzjonijiet potenzjalment setgħet ukoll jkun żmien kostanti, anki jekk id-data tiegħek istruttura tidher bħal dan, firxa ta ' pointers, kull wieħed minnhom huwa li tipponta lejn potenzjalment lista linked. Kif tista 'tikseb kostanti inserzjoni ħin ta 'ismijiet? Stick fl-quddiem, id-dritt? 

Jekk aħna sagrifiċċju għan disinn mill qabel, fejn aħna riedu jżommu isem ta 'kulħadd, per eżempju, magħżula, jew kollha tal-numri fuq il-palk magħżula, jissoponi li għandna lista marbuta mhux magħżul. Hija biss l-ispejjeż us stadju wieħed inkella tnejn, bħal fil-każ ta 'Ben u Brian qabel, li daħħal element fil il-bidu tal-lista. Allura jekk aħna ma jimpurtahom dwar issortjar kollha ta 'l-ismijiet li jibda bl A jew kollha l-ismijiet li jibda bl B, nistgħu xorta jinkiseb inserzjoni ta 'żmien kostanti. Issa qed ifittxu up Alice jew Bob jew kull isem b'mod aktar ġenerali għadu dak? Huwa big O ta 'n diviż b'26, fil- każ ideali fejn kulħadd huwa uniformi mqassma, fejn hemm kif ħafna A tal kif hemm tal Z, li huwa probabbilment realistika. Imma dak li għadu lineari. 

Iżda hawnhekk, aħna jerġgħu lura għall-punt ta 'notazzjoni asintotiku jkunu teoretikament veru. Iżda fid-dinja reali, jekk I jsostnu li programm tiegħi tista 'tagħmel xi ħaġa 26 darba aktar mgħaġġel minn tiegħek, li programm inti se jippreferu jużaw? Dejjem jew mini, li huwa 26 darbiet aktar mgħaġġla? Realistikament, il-persuna li hija s-26 darbiet aktar mgħaġġla, anke jekk teoretikament algoritmi tagħna jimxu fl-istess asintotiku running time. 

Let me tipproponi differenti soluzzjoni għal kollox. U jekk dan ma blow moħħok, aħna qed barra ta 'strutturi ta' dejta. Allura dan huwa minnu a trie - tip ta 'isem stupid. Dan ġej mill retrievals, u l-kelma spjegat trie, t-r-i-e, minħabba irkupru kors ħsejjes simili trie. Iżda li l-istorja tal-trie kelma. 

Allura trie huwa tabilħaqq xi tip ta 'siġra, u huwa wkoll play fuq din il-kelma. U anki jekk inti ma tistax pjuttost tara ma 'dan viżwalizzazzjoni, a trie huwa siġra strutturat, bħal siġra tal-familja ma ' antenat wieħed fil-quċċata u l-lottijiet ta 'neputijiet u neputijiet kbira bħala tħalli fuq il-qiegħ. Iżda kull node fil trie huwa array. U huwa fil-firxa - u ejja oversimplify għal mument - huwa ta ' array, f'dan il-każ, ta 'daqs 26, fejn kull node darb'oħra huwa firxa ta 'daqs 26, fejn l-element 0 f'dik array jirrappreżenta A, u l-aħħar element f'kull tali firxa tirrappreżenta Z. 

So nipproponi, allura, li din id-data istruttura, magħrufa bħala trie, jista 'jkun jintuża wkoll biex jaħżnu kliem. Rajna mument ilu kif nistgħu taħżen kliem, jew f'dan il-każ ismijiet, u aħna raw qabel kif nistgħu taħżen numri, imma jekk aħna niffukaw fuq ismijiet jew kordi hawn, avviż x'hemm interessanti. I jsostnu li l-isem huwa Maxwell ġewwa ta 'din l-istruttura tad-data. Fejn tara Maxwell? 

STUDENT: [inaudible]. 

SPEAKER 1: Fuq ix-xellug. Allura x'hemm interessanti ma din id-data istruttura hija pjuttost milli maħżen tal- string backslash zero M-A-X-W-E-L-L, kollha contiguously, dak li inti minflok tagħmel qed isegwi. Jekk dan huwa trie bħall-istruttura tad-data, kull lymph li hija għal darb'oħra firxa, u inti tixtieq li taħżen Maxwell, inti l-ewwel indiċi u għalhekk node l-għerq tal-hekk biex jitkellmu, l-node topmost, fil-post M, tajjeb, sabiex bejn wieħed u ieħor fis-nofs. U mbagħad minn hemm, inti ssegwi pointer lil lymph tfal, biex ngħidu hekk. Allura fis-sens siġra tal-familja, inti ssegwi dan l isfel. U li inti twassal għal ieħor node fuq ix-xellug hemm, li hija biss array ieħor. 

U mbagħad jekk inti tixtieq li taħżen Maxwell, issib il-pointer li tirrappreżenta A, li huwa dan wieħed hawn. Imbagħad inti tmur għall-node li jmiss. U avviż - dan huwa għaliex l-istampa tal- iqarraq ftit - dan node ħarsa super ċkejkna. Iżda għad-dritt ta 'dan huwa Y u Z. Huwa biss l-awtur maqtugħ il- stampa sabiex inti fil-fatt jara l-affarijiet. Inkella din l-istampa tkun immensament wiesgħa. Allura issa inti indiċi fis lokazzjoni X, imbagħad W, Imbagħad E, allura L, imbagħad L. Imbagħad x'hemm dan kurżità? 

Ukoll, jekk aħna qed jużaw dan it-tip ta 'ġodda tieħu dwar kif taħżen string fil- struttura tad-data, inti xorta jkollok bżonn li essenzjalment check off fid-dejta istruttura li kelma tispiċċa hawnhekk. Fi kliem ieħor, kull wieħed minn dawn in-nodi b'xi mod irid jiftakar li aħna jseħħx kollha ta 'dawn pointers u huma jitilqu ftit Frak tal-ħobż fil-qiegħ hawn 'din istruttura li jindika M-A-X-W-E-L-L huwa tabilħaqq f'din l-istruttura tad-data. 

Allura nistgħu nagħmlu dan kif ġej. Kull wieħed mill-lymph fl-istampa aħna biss serrieq għandha wieħed, firxa ta 'daqs 27. U huwa issa 27, għaliex p stabbiliti sitt, aħna ser attwalment jagħtuk apostrophe, hekk aħna jista 'jkollhom ismijiet bħal O'Reilly u oħrajn bi apostrophes. Iżda istess idea. Kull waħda minn dawn l-elementi fil- punti firxa għal Struct node, hekk biss node. Allura dan huwa ħafna reminixxenti tal-lista marbuta tagħna. 

U mbagħad I jkollhom Boolean, li jiena ser sejħa kelma, li huwa biss se jkun minnu jekk kelma jintemm dan node fil-siġra. Hija effettivament jirrappreżenta l-ftit trijangolu rajna mument ilu. Mela jekk kelma tispiċċa f'dak node fil- siġra, dak il-qasam se kelma ikunu vera, li hija kunċettwalment iċċekkjar off, jew aħna qed tpinġija dan il-trijanglu, iva hemm hija kelma hawn. 

Allura dan huwa trie. U issa l-kwistjoni hija, dak huwa running time tiegħu? Huwa big O ta 'n? Huwa xi ħaġa oħra? Ukoll, jekk għandek n ismijiet f'dan data istruttura, Maxwell huwa biss wieħed ta ' minnhom, dak li huwa l-ħin tmexxija ta ' ddaħħal jew sejba Maxwell? X'hemm-running time ta 'ddaħħal Maxwell? Jekk hemm ismijiet oħra n diġà fit-tabella? Yeah? 

STUDENT: [inaudible]. 

SPEAKER 1: Yeah, huwa t-tul l-isem, id-dritt? Allura M-a-x-w-e-l-l għalhekk iħoss bħal dan algoritmu huwa kbir O ta 'seba. Issa, naturalment, l-isem se ivarjaw fit-tul. Forsi huwa l-isem qasir. Forsi huwa l-isem itwal. Imma x'hemm prinċipali hawnhekk hija li huwa numru kostanti. U forsi mhuwiex verament kostanti, imma alla, jekk realistikament, b'mod dizzjunarju, hemm probabilment xi limitu fuq in-numru ta 'ittri fil- isem persuna f'pajjiż partikolari. 

U hekk nistgħu nassumu li valur huwa kostanti. I do not know dak li hu. Huwa probabbilment akbar minn aħna naħsbu li hu. Għaliex hemm dejjem xi kantuniera każ ma 'isem twil crazy. Mela ejja sejħa hija k, iżda huwa għadu kostanti preżumibbilment, għaliex kull isem fid-dinja, mill-inqas fil- pajjiż partikolari, huwa li tul jew iqsar, dan huwa kostanti. Imma meta aħna ħadthom qal xi ħaġa hija kbira O ta 'valur kostanti, x'hemm li verament ekwivalenti għal? Dik hija verament l-istess ħaġa kif qal ħin kostanti. 

Issa aħna qed tip ta 'qerq, right? Aħna tip ta 'lieva xi teorija hawn biex ngħid li tajjeb, ordni ta 'k huwa verament ftit ordni ta 'wieħed, u wasal iż-żmien kostanti. Imma verament huwa. Minħabba l-għarfien prinċipali hawnhekk hija li jekk aħna n ismijiet diġà f'dan struttura tad-data, u aħna daħħal Maxwell, huwa l-ammont ta 'ħin li tieħu magħna biex daħħal Maxwell fil-livelli kollha affettwati minn kif in-nies ħafna oħrajn huma fl-istruttura tad-data? Ma jidhirx li jkun. Jekk I kellhom biljun aktar elementi ta 'dan trie, u mbagħad daħħal Maxwell, hija hu fil-livelli kollha affettwati? No U li b'differenza kwalunkwe data kuljum istrutturi Rajna s'issa, fejn l-running time ta 'algoritmu tiegħek huwa kompletament indipendenti ta 'kemm għalf huwa jew ma jkunx diġà f'dak istruttura tad-data. 

U hekk ma 'dan joffri inti issa huwa opportunità għal p sett sitt, li se darb'oħra jinvolvu implimentazzjoni tiegħek jespliċitaw kontrollur, qari 150,000 kliem, kif l-aħjar biex jaħżnu dik mhuwiex neċessarjament ovvja. U għalkemm stajt jaspira biex isibu l-Grail qaddis, jien ma jsostnu li trie hu. Fil-fatt, tabella hash jistgħu tajjeb ħafna juru li huma ħafna aktar effiċjenti. Iżda dawn huma biss - li jinsab biss waħda mid-deċiżjonijiet tad-disinn inti se jkollu jagħmel. 

Iżda fl-għeluq ejja ħu 50 jew hekk sekondi biex tieħu Peek fuq dak li jinsab quddiem ġimgħa d-dieħla u lil hinn aħna transizzjoni minn din il-linja ta 'kmand dinja jekk C-programmi għall-affarijiet web ibbażata u lingwi bħal PHP u JavaScript u l-internet innifsu, protokolli bħal HTTP, li inti stajt meħuda għall mogħtija għas-snin issa, u ittajpjat aktar minn darba kull jum, forsi, jew li jidhru. U aħna ser tibda titqaxxar lura l- saffi ta 'dak li huwa l-internet. U dak huwa l-kodiċi li huwa l-bażi għodod tal-lum. Allura 50 sekondi ta 'dan teaser hawn. I jagħtuk Warriors tal-Net. 

[Daqq video] 

-Huwa daħal bil-messaġġ. Bil-protokoll kollu tiegħu stess. Huwa daħal għal dinja ta 'firewalls krudili, routers uncaring, u l-perikli ferm agħar minn mewt. Huwa mgħaġġel. Hu b'saħħtu. Hu TCPIP. U hu ltqajna indirizz tiegħek. Ġellieda tal-Net. 

[Daqq video END] 

SPEAKER 1: Din hija kif l-internet għandhom jaħdmu mill-ġimgħa d-dieħla.