[Daqq ta mużika] SPEAKER 1: Kull dritt. Kulħadd merħba lura għat-taqsima. Nispera li intom kollha huma b'suċċess rkuprati minn kwizz tiegħek mill-aħħar ġimgħa. Naf huwa ftit crazy f'ħinijiet. Kif I kien qal qabel, jekk int fi ħdan id-devjazzjoni standard, ma verament tinkwieta dwar dan, speċjalment għal taqsima inqas komdi. Dan huwa madwar fejn inti għandek tkun. Jekk inti għamilt kbir, imbagħad biża. Kudos lilek. U jekk inti tħoss bħal għandek bżonn ftit aktar għajnuna, jekk jogħġbok tħossok liberu li jilħqu out għal xi TFS. Aħna lkoll hawn biex jgħinu. C'est pourquoi aħna jgħallmu. C'est pourquoi jien hawn kull Tnejn għalik guys u fl-uffiċċju sigħat nhar ta 'Ħamis. Allura jekk jogħġbok tħossok liberu li let me know jekk int inkwetat dwar xi ħaġa jew jekk hemm xi ħaġa fuq l-kwizz li youd verament tixtieq tindirizza. Għalhekk l-aġenda għal-lum huwa kollha dwar strutturi ta 'dejta. Uħud minn dawn huma biss ser tkun biss biex inti tikseb familiarized ma 'dawn. Inti tista 'ma qatt jimplimentaw minnhom f'din il-klassi. Xi wħud minnhom inti se, bħal per pset speller tiegħek. Inti ser ikollok l-għażla tiegħek bejn tabelli hash u tipprova. Allura aħna ser definittivament jkunu għaddejjin fuq dawk. Li għaddej biex tkun definittivament aktar ta 'tip ta 'sezzjoni livellata għoli llum, għalkemm, minħabba li hemm ħafna minnhom, u jekk aħna marru fis-dettalji ta 'implimentazzjoni fuq kollha ta 'dawn, aħna se le anki nikseb permezz ta 'listi marbuta u forsi xi ftit ta 'tabelli hash. Allura jkollhom miegħi. Aħna mhux se tkun qed twettaq daqshekk kodifikazzjoni dan iż-żmien. Jekk għandek xi mistoqsijiet dwar dan jew inti tixtieq li tara implimentata jew jippruvaw hija għalik innifsek, I definitely jirrakkomandaw ser study.cs50.net, li għandha eżempji ta 'dawn kollha. Hija ser ikollhom powerpoints tiegħi man-noti li aħna għandhom tendenza li jużaw kif ukoll xi programmazzjoni eżerċizzji, speċjalment għall-affarijiet bħal listi konnessi u binarja stacks siġar u cues. Allura ftit aktar livell għoli, li jista 'jkun sbieħ għall inti guys. Allura ma 'dan, aħna ser tibda. U wkoll, kwizzijiet yes--. Naħseb li ħafna minnkom li huma fil- taqsima tiegħi jkollhom kwizzijiet tiegħek, iżda xi ħadd jiġi fl jew xi raġuni inti ma, dawn qed dritt hawn fl-quddiem. Hekk listi marbuta. Naf li dan it-tip ta 'tmur li back qabel kwizz tiegħek. Dan kien l-ġimgħa qabel li aħna tgħallmu dwar dan. Iżda f'dan il-każ, aħna ser biss jmorru ftit aktar fil-fond. Allura għaliex jista nagħżlu marbut lista fuq firxa? Dak li jiddistingwihom minnhom? Iva? UDJENZA: Inti tista 'tespandi a marbut lista versus daqs fiss ta 'firxa. SPEAKER 1: Dritt. Firxa ffissat daqs billi lista marbuta għandu daqs varjabbli. Hekk jekk ma nafux kif kemm aħna tixtieq li taħżen, lista marbuta jagħtina kbir mod biex tagħmel dan għaliex nistgħu biss żid fuq node ieħor u żid fuq node u ieħor żid fuq node ieħor. Imma dak li jista 'jkun kompromess? Ħadd ma tiftakar il-kompromess bejn arrays u listi marbuta? Mmhmm? UDJENZA: Inti għandek biex jgħaddu-triq kollha permezz tal-lista marbuta isibu element f'lista. Fil-firxa, inti tista biss issib element. SPEAKER 1: Dritt. Allura ma arrays-- UDJENZA: [inaudible]. SPEAKER 1: Bil arrays, għandna dak li sejjaħ aċċess bl-addoċċ. Ifisser li jekk irridu dak li huwa qatt il-ħames punt ta 'lista jew il-ħames punt ta 'tagħna firxa, nistgħu biss grab dan. Jekk huwa lista marbuta, għandna li jtenni permezz, id-dritt? Allura aċċess element fil firxa huwa żmien kostanti, billi ma 'lista marbuta li kieku jkun x'aktarx ħin lineari għaliex forsi element tagħna huwa l-triq kollha fl-aħħar. Irridu tfittxija permezz kollox. Allura ma 'dawn id-data kollha istrutturi aħna qed tmur li tkun infiq ftit aktar ħin fuq, liema huma l-pluses u negattivi. Meta tista irridu tuża wieħed fuq l-ieħor? U dak l-tip ta 'l- ħaġa akbar għal take away. Allura għandna hawnhekk l- definizzjoni ta 'node. Huwa simili element wieħed fl lista marbuta tagħna, id-dritt? Allura aħna qed kollha familjari mal structs typedef tagħna, li aħna marru fuq fl-analiżi aħħar darba. Kien bażikament biss joħolqu tip ieħor data li nistgħu jużaw. U f'dan il-każ, huwa xi node li ser ikollu xi numru sħiħ fil. U allura x'inhu l-tieni parti hawn? Xi ħadd? UDJENZA: [inaudible]. SPEAKER 1: Yeah. Huwa pointer għall-node li jmiss. Allura dan għandu attwalment ikun up here. Din hija pointer tat-tip node għall-ħaġa li jmiss. U dan huwa dak li jinkludi node tagħna. Kessaħ. Kull dritt, hekk bil-tfittxija, kif konna biss qal qabel l-idejn, jekk int ser tfittex permezz, inti għandek attwalment jtenni permezz lista marbuta tiegħek. Hekk jekk aħna qed tfittex għan-numru 9, aħna se tibda fil-kap tagħna u li l-punti magħna fil-bidu tal-lista marbuta tagħna, id-dritt? U aħna ngħidu, OK, ma dan node fih in-numru 9? No? Kull dritt, mur l-wieħed li jmiss. Segwi dan. Ma fiha n-numru 9? No Segwi l-wieħed li jmiss. Allura aħna għandna biex effettivament jtenni permezz lista marbuta tagħna. Ma nistgħux sempliċement tmur direttament lejn fejn 9 hu. U jekk inti guys fil-fatt tixtieq li tara xi psewdo-kodiċi up hemm. Għandna xi funzjoni ta 'tfittxija hawn li jieħu in-- dak li ma jieħdu fil-? What do you think? Wieħed daqshekk faċli. X'inhu dan? UDJENZA: [inaudible]. SPEAKER 1: L-għadd aħna qed tfittex. Dritt? U dak li dan jikkorrispondi għall? Huwa pointer li? UDJENZA: A node. SPEAKER 1: A node għal-lista li aħna qed tħares lejn, id-dritt? Allura aħna għandna xi glandoli huma pointer hawn. Dan huwa punt li għaddej biex attwalment jtenni permezz lista tagħna. Waqqafna din ugwali għall-lista għaliex dan huwa biss dan ikun iffissat ugwali għall- bidu tal-lista marbuta tagħna. U filwaqt li huwa ma NULL, filwaqt li aħna xorta jkollhom affarijiet fil-lista tagħna, tikkontrolla biex tara jekk dik node għandha in-numru aħna qed tfittex. Ritorn vera. Inkella, jaġġornah, id-dritt? Jekk huwa NULL, aħna ħruġ tagħna filwaqt loop u r-ritorn foloz għaliex dan ifisser li aħna ma sabu dan. Does kulħadd nikseb kif din taħdem? OK. Allura ma inserzjoni, inti għandhom tliet modi differenti. Tista prepend, inti tista 'tehmeż u inti tista 'daħħal fis assortiti. F'dan il-każ, aħna qed se tagħmel prepend. Ħadd ma jaf kif dawk tliet każijiet jistgħu jvarjaw? Allura prepend ifisser li inti tpoġġi huwa fuq quddiem tal-lista tiegħek. Allura dan ikun ifisser li l-ebda kwistjoni dak node tiegħek huwa, irrelevanti dak il-valur huwa, int ser li tqiegħed lilha dritt hawn fuq quddiem, OK? Li għaddej biex tkun l-ewwel element fil-lista tiegħek. Jekk inti tehmeż dan, li għaddej biex tmur fil-dahar tal-lista tiegħek. U daħħal fis assortiti ifisser li int ser jitqiegħdu fil-fatt fil-post fejn iżomm lista marbuta tiegħek magħżula. Għal darb'oħra, kif tuża dawn u meta tuża minnhom se jvarjaw skond il-każ tiegħek. Jekk ma bżonn jiġu magħżula, prepend tendenza li jkun dak li ħafna nies jużaw għaliex inti ma għandhom jgħaddu l-lista sħiħa biex isibu l-aħħar iżżidhiex fuq, id-dritt? Inti tista 'biss stick dan id-dritt fil-. Allura aħna se jmorru permezz ta ' inserzjoni 1 id-dritt issa. Ħaġa Allura wieħed li jien ser jirrakkomanda ħafna fuq dan pset huwa li tiġbed l-affarijiet out, bħal dejjem. Huwa importanti ħafna li inti aġġornament pointers tiegħek fl-ordni korretta għaliex jekk inti taġġornahom ftit out of order, int ser jispiċċaw jitilfu partijiet tal-lista tiegħek. Hekk per eżempju, f'dan il-każ, aħna qed javżak-ras għal ftit punt 1. Jekk aħna biss tagħmel dan mingħajr iffrankar dan 1, aħna għandna ebda idea dak li 1 għandu jindika li issa għaliex aħna tilfu dak il-kap indikat. Allura ħaġa waħda li tiftakar meta int tagħmel prepend hu li jsalva dak li l- punti Head sa l-ewwel, imbagħad jassenja mill-ġdid, u mbagħad taġġorna dak node ġdid tiegħek għandu jindika. F'dan il-każ, dan huwa mod wieħed biex tagħmel dan. Hekk jekk aħna kienu għamlu dan il-mod fejn aħna biss assenjati mill-ġdid tar-ras, aħna jitilfu bażikament tagħna lista sħiħa, id-dritt? Mod wieħed biex tagħmel dan huwa li jkollhom 1 punt li jmiss, u mbagħad ikollhom punt ras għal 1. Jew inti tista 'tagħmel it-tip ta bħall- ħażna temporanja, li jiena tkellem dwar. Iżda jassenjaw mill-ġdid tiegħek pointers fl-ordni korretta se tkun ħafna, ħafna importanti għal din pset. Inkella, int se jkollhom hash mejda jew jipprova li jinsab biss se tkun parti biss tal-kliem li inti tixtieq u mbagħad mmhmm you're--? UDJENZA: Liema kienet l-temporanja Ħaġa ħażna inti kienu jitkellem dwar? SPEAKER 1: Il-ħażna temporanja. Allura bażikament ieħor mod inti tista 'tagħmel dan huwa jaħżen il-kap ta 'xi ħaġa, bħal jaħżnuh il-varjabbli temporanju. Tassenja din għal 1 u imbagħad jaġġornaw 1 punt għal dak kollu ras użati għall-punt li. Dan il-mod huwa ovvjament aktar eleganti għaliex inti m'għandhomx bżonn valur temporanju, iżda ftit joffru mod ieħor biex tagħmel dan. U għandna attwalment do jkollhom xi kodiċi għal dan. Allura għal-lista marbuta, aħna attwalment ikollhom xi kodiċi. Allura daħħal hawn, dan huwa prepending. Allura dan jidħol dan fil-ras. Allura l-ewwel ħaġa, għandek bżonn li joħolqu node ġdid tiegħek, naturalment, u ċċekkja għall NULL. Dejjem tajjeb. U allura inti għandek bżonn biex tassenja l-valuri. Kull meta inti toħloq node ġdid, inti ma jafux liema huwa tipponta lejn jmiss, sabiex inti tixtieq li initialize li NULL. Jekk ma jispiċċaw tipponta lejn xi ħaġa inkella, jiġrilha riassenjata u huwa multa. Jekk huwa l-ewwel ħaġa fil-lista, jeħtieġ għall-punt li NULL għaliex dak l-aħħar tal-lista. Hekk allura li daħħalha, naraw hawnhekk aħna jassenjaw il-valur li jmiss ta 'node tagħna li jkun x'ikun ras hija, li huwa dak li kellna hawn. Dak hu li aħna biss għamlet. U allura aħna qed jassenjaw ras il-punt biex node ġdid tagħna, għaliex ftakar, ġdid hija xi pointer għal node, u dan huwa eżattament dak li ras hija. Dan huwa eżattament għaliex aħna jkollhom din vleġġa accessor. Kessaħ? Mmhmm? UDJENZA: Do irridu initialize jmiss ġdid għall NULL ewwel, jew nistgħu sempliċement initialize dan li ras? SPEAKER 1: li jmiss New jeħtieġ li jkun NULL biex tibda għaliex inti ma tafx fejn huwa għaddej biex tkun. Ukoll, dan huwa tip ta ' bħad paradigma. Int tkun qed tissettja ugwali għal NULL biss li tagħmel żgur li bażijiet kollha tiegħek huma koperti qabel ma tagħmel xi assenjar sabiex int dejjem garantit li se tkun tipponta lejn valur speċifiku versus bħal valur żibel. Minħabba, yeah, aħna tassenja awtomatikament ġdid li jmiss, iżda huwa aktar biss bħal prattika tajba li initialize dan b'dak il-mod u mbagħad jassenja mill-ġdid. OK, listi marbuta hekk doppjament issa. What do naħsbu? X'hemm differenti ma listi marbuta doppjament? Allura fil-listi marbuta tagħna, nistgħu biss jimxu f'direzzjoni waħda, id-dritt? Aħna biss li jmiss. Nistgħu biss jimxu 'l quddiem. Ma 'lista marbuta doppjament, nistgħu wkoll jimxu lura. Allura aħna għandna mhux biss il- Numru li aħna tixtieq li taħżen, għandna fejn hija tirreferi għall jmiss u fejn aħna biss ġew minn. Allura dan jippermetti xi traversal aħjar. Lymph hekk doppjament marbuta, simili ħafna, id-dritt? Differenza Biss issa hija aħna ikollhom jmiss u preċedenti. Hu l-unika differenza. Hekk jekk konna biex prepend jew append-- aħna ma jkollhom ebda kodiċi għall dan up here-- imma jekk ġejt biex jippruvaw u daħħalha, il-ħaġa importanti huwa inti bżonn tagħmel żgur li int qed assenjazzjoni kemm preċedenti tiegħek u tiegħek pointer jmiss korrett. Allura f'dan il-każ, inti mhux biss initialize jmiss, inti initialize preċedenti. Jekk aħna qed fil-kap tal-lista, aħna mhux biss tagħmel ras ugwali ġdid, iżda għandha preċedenti ġdida tagħna punt għall-ras, id-dritt? Dik hija l-unika differenza. U jekk inti tixtieq aktar prattika ma dawn ma 'listi marbuta, bil ddaħħal, ma tħassar, ma daħħal fis lista assortiti, jekk jogħġbok iċċekkja study.cs50.net. Hemm mazz ta 'eżerċizzji kbira. I jirrakkomanda ħafna minnhom. Nixtieq kellna ħin biex tmur permezz tagħhom imma hemm ħafna ta 'strutturi ta' dejta li tinkiseb permezz. OK, hekk tabelli hash. Din hija probabbilment l-aktar bit utli għall pset tiegħek hawnhekk għaliex int ser tkun implimentazzjoni waħda minn dawn, jew jipprova. I really simili tabelli hash. Huma qed pretty jibred. Allura bażikament dak jiġri huwa tabella hash huwa meta aħna verament bżonn ta 'malajr inserzjoni, tħassir, u Lookup. Dawk huma l-affarijiet li aħna qed prijoritizzazzjoni f'tabella hash. Huma jistgħu jiksbu pretty big, imma kif aħna ser tara mal tentattivi, hemm affarijiet li huma ħafna akbar. Imma bażikament, kollha hash tabella hija funzjoni hash li jgħidlek liema barmil tpoġġi kull tad-data tiegħek, kull wieħed mill-elementi tiegħek fil. A mod sempliċi biex jaħsbu ta 'tabella hash hija li huwa biss bramel ta 'affarijiet, dritt? Allura meta inti qed issortjar affarijiet minn bħall-ewwel ittra ta 'isem tagħhom, thats tip simili ta 'tabella hash. Mela jekk jien kienu li grupp inti guys huwa fi gruppi ta 'min jibda l-isem tal- mal A hawn fuq, jew min birthday hija f'Jannar, Frar, Marzu, tkun xi tkun, li tkun effettivament ħolqien ta 'tabella hash. Huwa biss joħolqu bramel li inti sort elementi tiegħek fis sabiex inti tista 'issibhom aktar faċli. Allura dan il-mod meta I ħtieġa biex isibu waħda minnkom, I ma jkollhomx biex tfittex permezz ta 'kull ta' ismijiet tiegħek. I jistgħu jkunu simili, oh, naf li Birthday Danielle hija in-- UDJENZA: --April. SPEAKER 1: April. So I ħarsa f'April tiegħi barmil, u ma 'kwalunkwe Xorti, hi ser tkun l-unika waħda fil hemm u ħin tiegħi kien kostanti f'dan is-sens, billi jekk I jkollha tħares permezz mazz sħiħ ta 'persuni, li għaddej biex jieħu ħafna aktar. Allura tabelli hash huma verament biss bramel. Mod faċli biex jaħsbu minnhom. Allura ħaġa importanti ħafna dwar tabella hash hija funzjoni hash. Allura l-affarijiet I biss tkellmu dwar, bħal ewwel ittra tiegħek ta 'l-ewwel isem tiegħek jew xahar birthday tiegħek, dawn huma ideat li verament jikkorrelataw għal funzjoni hash. Huwa biss mod biex tiddeċiedi liema barmil inti element qed tmur fi, OK? Allura għal dan pset, inti tista 'tfittex up pretty ħafna xi funzjoni hash tixtieq. Ma għandhom ikunu tiegħek stess. Hemm xi dawk verament jibred out hemmhekk li jagħmlu kull tip ta matematika crazy. U jekk inti tixtieq li tagħmel tiegħek spellchecker super fast, Nixtieq definittivament tħares lejn wieħed minn dawn. Imma hemm ukoll l- dawk sempliċi, bħal jikkomputa is-somma tal-kliem, bħal kull ittra għandha numru. Kkalkulata l-ammont. Li jiddetermina l-barmil. Huma għandhom ukoll dawk faċli li huma biss simili kollha tal-li A hawn, kollha tal-B hawnhekk. Kwalunkwe wieħed minn dawk. Bażikament, hija biss jgħidlek liema indiċi array element tiegħek għandhom imorru fis. Just tiddeċiedi l-bucket-- dan kollu funzjoni hash huwa. Allura hawnhekk għandna eżempju li hija biss l-ewwel ittra tas-sekwenza li I kien biss jitkellem dwar. Hekk ikollok xi hash li jinsab biss l- ewwel ittra ta 'sekwenza tiegħek minus A, li se jagħtuk xi numru bejn 0 u 25. U dak li trid tagħmel hu li kun żgur li dan jirrappreżenta id-daqs tal-hash tiegħek table-- kemm bramel hemm. Ma 'ħafna minn dawn funzjonijiet hash, dawn qed ser ikunu valuri jirritorna li tista ikun ferm ogħla mill-għadd ta 'bramel li inti fil-fatt ikollhom fit-tabella hash tiegħek, sabiex inti għandek bżonn tagħmel żgur u MoD minn dawk. Inkella, li għaddej biex jgħidu, oh, għandha tkun fil-barmil 5,000 imma inti biss għandek 30 bramel fit-tabella hash tiegħek. U ovvjament, aħna lkoll nafu li l- se jirriżulta xi żbalji crazy. Sabiex tagħmel ċert li Mod mill- daqs tal-mejda hash tiegħek. Kessaħ. Hekk kolliżjonijiet. Huwa kulħadd tajba s'issa? Mmhmm? UDJENZA: Għaliex kieku dan ritorn ta 'tali valur enormi? SPEAKER 1: Jiddependi fuq l-algoritmu dik il-funzjoni hash tiegħek juża. Xi wħud minnhom se do multiplikazzjoni crazy. U dan kollu dwar jkollna distribuzzjoni li, sabiex ikunu jagħmlu xi verament affarijiet crazy kultant. Li kollox. Xi ħaġa oħra? OK. Hekk kolliżjonijiet. Bażikament, kif għidt qabel, fix-xenarju aħjar każ, kwalunkwe barmil I tħares lejn huwa se jkollhom ħaġa waħda, so I ma jkollhom ħarsa fil-livelli kollha, id-dritt? I jew taf huwa hemmhekk jew huwa mhux, u dak hu li aħna verament irridu. Imma jekk ikollna għexieren ta 'eluf ta' punti tad-data u inqas minn dak in-numru ta 'bramel, aħna qed tmur biex ikollhom kolliżjonijiet fejn eventwalment xi ħaġa se jkollhom jispiċċaw fil- barmil li diġà għandu element. Għalhekk il-kwistjoni hija, dak nagħmlu f'dak il-każ? X'nagħmlu? Aħna diġà għandhom xi ħaġa hemmhekk? Do we biss tarmi it out? No Għandna biex iżommu tnejn minnhom. Allura l-mod li aħna tipikament tagħmel dan huwa dak? X'inhu l-istruttura tad-data aħna biss tkellem dwar? UDJENZA: lista Marbuta. SPEAKER 1: Lista marbuta. Allura issa, minflok ta 'kull wieħed minn dawn bramel biss li element wieħed, li għaddej biex jkun fih lista marbuta ta ' l-elementi li ġew hashed fis dan. OK, ma kulħadd tip ta 'nikseb dik l-idea? Għaliex aħna ma jista 'jkollha firxa għaliex aħna ma jafux kif ħafna affarijiet ser ikunu fil hemmhekk. Lista marbuta jippermetti li għadek in-numru eżatt li huma hashed f'dak barmil, id-dritt? Allura lineari probing huwa bażikament dan idea-- huwa mod wieħed biex jittrattaw ħabta. X'tista 'tagħmel hija jekk, f'dan il- każ, berry kien hashed fis 1 u diġà għandna xi ħaġa hemmhekk, inti biss iżommu għaddejjin isfel sakemm issib slot vojta. C'est mod wieħed biex jimmaniġġaw dan. Il-mod ieħor biex jimmaniġġaw huwa ma dak li aħna biss called-- il marbut lista tissejjaħ chaining. Allura din l-idea xogħlijiet jekk tabella hash tiegħek taħseb huwa ħafna ikbar minn data tiegħek sett jew jekk inti jridu jippruvaw u jimminimizzaw ikkatenar sakemm huwa assolutament neċessarju. Allura ħaġa waħda hija lineari probing ovvjament ifisser dik il-funzjoni hash tiegħek mhux daqshekk utli għaliex int ser jispiċċaw jużaw funzjoni hash tiegħek, jkollna sa punt, inti lineari sonda isfel sa xi post li hija disponibbli. Imma issa, naturalment, xejn inkella li jispiċċa hemm, int ser ikollhom tfittxija anke aktar 'l isfel. U hemm ħafna aktar spejjeż tat-tiftix li tmur fil inputjar element fit-tabella hash tiegħek issa, id-dritt? U issa meta inti tmur u jippruvaw isibu berry darb'oħra, int ser issir hash lilha, u li għaddej biex jgħidu, oh, ħarsa fil barmil 1, u mhuwiex ser ikun fil-barmil 1, hekk int ser ikollhom travers permezz tal-bqija ta 'dawn. Allura huwa kultant utli, iżda f'ħafna każijiet, aħna qed tmur biex ngħid li chaining huwa dak li inti trid tagħmel. Allura aħna tkellimna dwar dan qabel. I ltqajna l quddiem ftit ta 'myself. Iżda chaining huwa bażikament dak kull barmil fit-tabella hash tiegħek huwa biss lista marbuta. Allura mod ieħor, jew aktar tekniċi mod, biex jaħsbu ta 'tabella hash hija li huwa biss firxa ta 'listi marbuta, li meta int bil-miktub dizzjunarju tiegħek u inti qed tipprova tagħbija, ħsieb ta 'dan bħala firxa ta 'listi marbuta se tagħmilha aktar faċli għalik biex initialize. UDJENZA: Allura tabella hash għandu daqs predeterminat, bħal [inaudible] tal bramel? SPEAKER 1: Dritt. Għalhekk għandha numru sett ta ' bramel li inti determine-- li inti guys għandhom tħossok liberu li jilagħbu bil. Jista 'jkun pjuttost jibred biex tara x'jiġri kif int bdilt numru tiegħek ta 'bramel. Iżda yeah, hija għandha sett numru ta 'bramel. Dak li jippermetti li inti tajbin bħala ħafna elementi kif għandek bżonn huwa fejn dan chaining separata inti jkunu marbuta listi f'kull barmil. Dan ifisser tabella hash tiegħek se tkun eżattament id-daqs li inti jeħtieġ li tkun, id-dritt? Dik hija l-punt kollu ta 'listi marbuta. Kessaħ. Allura kulħadd OK hemmhekk? Kull dritt. Ah. Dak li ġara biss? Verament issa. Aqta 'xi ħadd qtil lili. OK aħna qed tmur biex jmorru fil tentattivi, li huma ftit crazy. I simili tabelli hash. Jien naħseb li qed verament jibred. Jipprova huma jibred, wisq. Sabiex ħadd ma tiftakar dak jipprova hu? Għandek mxew fuq fil-qosor fil-lecture? Do you remember-tip ta 'kif taħdem? UDJENZA: Jien biss nodding li aħna ma jmorru fuq dan. SPEAKER 1: We do jmorru fuq dan. OK, aħna qed verament se jmorru fuq issa huwa dak li aħna qed tgħid. UDJENZA: Li għal siġra irkupru. SPEAKER 1: Yeah. Huwa siġra irkupru. Biża. Allura ħaġa waħda li l-avviż hawnhekk hija li aħna qed iħarsu lejn karattri individwali hawn, id-dritt? Allura qabel b'funzjoni hash tagħna, aħna kienu qed ifittxu fil-kliem kollha kemm hi, u issa aħna qed tfittex aktar fil-karattri, right? Allura aħna għandna Maxwell hawn fuq u Mendel. Allura bażikament try-- mod biex jaħsbu dwar dan hija li kull livell hawn firxa ta 'ittri. Allura dan huwa node għerq tiegħek hawn, id-dritt? Dan għandu l-karattri tal- alfabett għall-bidu ta 'kull kelma. U dak li trid tagħmel hu li jiġifieri, OK, aħna għandna xi kelma M. Aħna qed tmur biex tfittex Maxwell, hekk immorru 'M. u M-punti lill-impjegati whole oħra firxa fejn kull kelma, sakemm ikun hemm hija kelma li għandha bħala t-tieni ittra, sakemm hemm kelma li għandha B bħala t-tieni ittra, din se jkollha pointer jmorru għal xi firxa li jmiss. Hemm probabilment mhux kelma li xi ħaġa MP, hekk fil-pożizzjoni P f'dan firxa, ikun biss NULL. Hija ngħid, OK, m'hemm l-ebda kelma li M segwit minn P, OK? Allura jekk aħna taħseb dwarha, kull wieħed minn dawn l-affarijiet iżgħar huwa attwalment wieħed minn dawn arrays kbar mill A permezz Z. Allura dak li jista 'jkun waħda mill-affarijiet li huwa tip ta 'żvantaġġ ta jipprova? UDJENZA: A lott ta 'memorja. SPEAKER 1: Huwa ton ta 'memorja, id-dritt? Kull waħda minn dawn il-blokok hawn jirrappreżenta 26 spazji, 26 element array. Allura tipprova tikseb oerhört tqil ispazju. Iżda huma malajr ħafna. Allura oerhört mgħaġġel iżda verament ispazju ineffiċjenti. Tip ta 'għandek figura out liema waħda tixtieq. Dawn huma verament jiksaħ għal pset tiegħek, iżda dawn ma jieħdu ħafna ta 'memorja, sabiex inti kummerċ off. Yeah? UDJENZA: Ikun possibbli li jitwaqqaf jipprova u mbagħad ladarba inti għandek l- data fiha li inti need-- I do not know jekk dan jagħmel sens. I kien jwarrbu l- Karattri NULL, iżda mbagħad inti ma tkunx kapaċi indiċi them-- SPEAKER 1: Inti xorta jkollok bżonn lilhom. UDJENZA: - bl-istess mod kull darba. SPEAKER 1: Yeah. Ikollok bżonn l-karattri NULL let inti taf jekk hemm Ma kelma hemmhekk. Ben kellek xi ħaġa li trid? OK. Kull dritt, hekk aħna qed tmur li jmorru ftit aktar fil-dettalji tekniċi wara jipprova u joperaw permezz ta 'eżempju. OK, għalhekk dan huwa l-istess ħaġa. Billi fil-lista marbuta, prinċipali tagħna tip of-- x'inhu l-kelma Irrid? - bħall-bini blokk kien node. Fil jipprova, aħna għandna wkoll node, imma hija definita b'mod differenti. Allura aħna għandna xi BOOL li tirrappreżenta jekk kelma attwalment jeżisti dan il-post, u mbagħad għandna xi firxa here-- jew pjuttost, dan huwa pointer għal firxa ta '27 karattri. U dan huwa għal, f'dan il-każ, din 27-- Jien ċert kollha inti simili, stenna, hemm 26-ittri fil-alfabett. Għalfejn għandna 27? Allura jiddependi fuq il- mod inti jimplimentaw din, dan huwa minn pset li permessi għall apostrophes. Allura hu għalhekk li l-waħda żejda. Int ser ikollok wkoll f'xi wħud każijiet il-terminatur null hija nkluża bħala waħda mill- karattri li huwa permess li jkun, u li kif jivverifikaw li tara jekk huwa l-aħħar tal-kelma. Jekk int interessat, check out Video Kevin dwar study.cs50, kif ukoll Wikipedija għandha xi riżorsi tajbin hemmhekk. Iżda aħna qed tmur biex jgħaddu biss tip ta 'kif inti tista' taħdem permezz jipprova jekk int tingħata waħda. Allura aħna għandna waħda super sempliċi hawnhekk li għandha l-kliem "BAT" u "zoom" fihom. U kif naraw up here, dan l-ispazju ftit hawn jirrappreżenta BOOL tagħna li jgħid, iva, dan huwa kelma. U allura dan għandu tagħna arrays ta 'karattri, id-dritt? Allura aħna se jmorru permezz sejba "BAT" f'dan jipprova. Allura tibda fil-quċċata, id-dritt? U aħna nafu li b jikkorrispondi għal it-tieni indiċi, it-tieni element f'dan array, għaliex u b. Allura madwar it-tieni wieħed. U jgħid, OK, berred, segwi dan in l-array li jmiss, għaliex jekk aħna niftakru, mhuwiex li kull wieħed minn dawn attwalment fiha l-element. Kull wieħed minn dawn arrays fih pointer, id-dritt? Huwa distinzjoni importanti biex jagħmlu. Naf li dan se be-- jipprova huma verament diffiċli biex jiksbu fuq l-ewwel darba, hekk anke jekk dan huwa l- tieni jew it-tielet darba u huwa għadu tip ta seeming diffiċli, I wegħda jekk inti tmur watch l-qasir għal darb'oħra għada, inneħħu probabbilment jagħmlu sens ħafna aktar. Huwa jieħu ħafna biex diġestiva. I still kultant am simili, stenna, dak li huwa jipprova? Kif nista jużaw dan? Allura għandna b f'dan il-każ, li hija t-tieni indiċi tagħna. Jekk kellna, jiġifieri, C jew d jew kull ittra oħra, għandna bżonn li Mappa li lura għall-indiċi ta 'firxa tagħna li dan jikkorrispondi għal. Allura aħna se tieħu bħal rchar u aħna biss naqqas off biex iħażżu fis 0-25. Kulħadd tajba kif aħna Mappa karattri tagħna? OK. Allura immorru għat-tieni waħda u aħna tara li, iva, huwa ma NULL. Aħna tista 'timxi fuq dan array li jmiss. Allura aħna jmorru fuq għal din array li jmiss hawn. U aħna ngħidu, OK, issa aħna bżonn biex tara jekk huwa hawnhekk. Huwa A null jew ma dan attwalment jimxu 'l quddiem? Allura fil-fatt jiċċaqlaq jgħaddi f'din firxa. U aħna ngħidu, OK, t hija l-aħħar ittra tagħna. Allura immorru l-t fil-indiċi. U allura aħna nimxu 'l quddiem għaliex hemm wieħed ieħor. U dan wieħed jgħid bażikament li, iva, jgħid li hemm kelma here-- li jekk inti ssegwi dan triq, inti jkunu waslu fi ftit kliem, li nafu huwa "BAT." Iva? UDJENZA: Huwa standard li jkollhom dik bħala indiċi 0 u mbagħad ikollhom tip ta '1 jew li jkollu fl-aħħar? SPEAKER 1: No Mela jekk inħarsu lura lejn tagħna dikjarazzjoni hawn, huwa BOOL, dan huwa element tagħha stess fil node tiegħek. Dan mhuwiex parti mill-firxa. Kessaħ. Allura meta aħna finitura kelma tagħna u aħna qed f'dan array, dak li rridu nagħmlu hija tagħmel verifika għal dan huwa kelma. U f'dan il-każ, ikun ritorn iva. Allura fuq din in-nota, aħna nafu li "zoo" - nafu bħala bnedmin li "zoo" hija kelma, dritt? Iżda huma jippruvaw hawnhekk jgħidu, l-ebda, mhuwiex. U ngħid li għaliex aħna ma jkunux ħatru bħala kelma hawn. Anki jekk nistgħu travers permezz ta 'dan array, dan jipprova ngħid li, no, zoo ma jkunx dizzjunarju tiegħek għaliex għandna ma nnominata bħala tali. Allura mod wieħed biex tagħmel that-- oh, sorry, dan wieħed. Allura f'dan il-każ, "zoo" mhijiex kelma, imma huwa fl jipprova tagħna. Iżda f'dan il-wieħed, ngħidu aħna jriduhom jintroduċu l-kelma "banju," dak li jiġri hija aħna isegwu through-- b, a, t. Aħna f'dan array, u immorru tiftix għal h. F'dan il-każ, meta aħna tħares lejn il-pointer fuq h, huwa tipponta lejn NULL, OK? Allura sakemm huwa espliċitament tipponta lejn firxa ieħor, għandek tassumi li l-pointers f'dan array huma tipponta lejn nulla. Allura f'dan il-każ, h hija li tipponta biex nulla hekk aħna ma tistax tagħmel xejn, għalhekk ikun ukoll ritorn falza, "banju" mhijiex fil hawn. Allura issa aħna qed attwalment se jmorru permezz kif kieku għandna attwalment ngħid li "zoo" hija fil jippruvaw tagħna. Kif nistgħu daħħal "zoo" fis jipprova tagħna? Allura bl-istess mod li bdejna ma ' lista marbuta tagħna, aħna tibda fil-għerq. Meta fid-dubju, tibda fil l-għerq ta 'dawn l-affarijiet. U aħna ser ngħidu, OK, z. z teżisti f'dan, u ma. Allura inti qed jimxu fuq firxa jmiss tiegħek, OK? U mbagħad fuq il-wieħed li jmiss, ngħidu, OK, ma o jeżistu? Hija ma. Dan jerġa. U hekk dak li jmiss tagħna, konna qal, OK, "zoo" diġà jeżisti hawnhekk. Kollha għandna bżonn tagħmel huwa stabbilit dan ugwali li veru, li hemm kelma hemmhekk. Jekk inti kienu segwiti kollox sa qabel dak il-punt, huwa kelma, hekk biss huwa stabbilit ugwali għal tali. Iva? UDJENZA: Mela allura ma li jfisser li "BA" hija kelma wkoll? SPEAKER 1: No Allura f'dan il-każ, "ba" aħna se tikseb hawnhekk, aħna ngħid huwa kelma, u xorta jkun hemm ebda. OK? Mmhmm? UDJENZA: Allura ladarba inti ma hija kelma u inti tgħidli iva, allura huwa se jkun fihom biex tmur m? SPEAKER 1: Allura dan għandu ma with-- int tagħbija dan fil. You say "zoo" hija kelma. Meta inti tmur check-- bħal, ngħidu li inti trid tgħid, ma "zoo" jeżistu f'dan dizzjunarju? Int biss tmur biex tfittex għal "zoo," u mbagħad tiċċekkja biex tara jekk huwa kelma. Inti qatt ma ser jiċċaqalqu permezz ta 'm għaliex li mhux dak li qed tfittex. Hekk jekk aħna fil-fatt riedu żid "banju" fis dan jipprova, aħna se nagħmlu l-istess ħaġa kif għamilna ma "zoo," ħlief aħna se tara li meta aħna tipprova u tikseb sabiex h, dan ma jeżistix. Allura inti tista 'taħseb ta' dan bħala jippruvaw li żżid node ġdid ġo lista marbuta, hekk aħna se bżonn li żżid ieħor waħda minn dawn arrays, bħal hekk. U allura dak li nagħmlu huwa aħna biss stabbiliti l-h element ta 'dan array li tipponta lejn dan. U allura dak li rridu nagħmlu hawn? Iżżidhiex ugwali għal veru għaliex dan huwa kelma. Kessaħ. I know. Tipprova mhumiex l-aktar eċċitanti. Trust me, I know. Allura ħaġa waħda li tirrealizza ma tentattivi, I said, dawn qed effiċjenti ħafna. Allura aħna stajt tidher li jieħdu ton ta 'spazju. Huma qed tip ta 'konfużjoni. Allura għaliex kieku aħna qatt tuża dawn? Aħna nużaw dawn għaliex qed oerhört effiċjenti. Mela jekk inti qed tfittex qatt up kelma, inti biss li tmiss mit-tul tal-kelma. Mela jekk inti qed tfittex għal kelma li huwa ta 'tul ħamsa, int biss qatt ser ikollhom jagħmlu iktar ħames paraguni, OK? Hekk jagħmilha bażikament kostanti. Bħal inserzjoni u Lookup huma bażikament ta 'żmien kostanti. Hekk jekk inti tista 'qatt tikseb xi ħaġa fil-ħin kostanti, li bħala tajba kif jiġrilha. Inti ma tistax tikseb aħjar minn ħin kostanti għal dawn l-affarijiet. Allura dan huwa wieħed mill- pluses kbar ta 'jipprova. Iżda huwa ħafna spazju. Allura inti tip ta 'għandek tiddeċiedi x'hemm aktar importanti għalik. U fuq il-kompjuters tal-lum, il- ispazju li jipprova jista 'jieħu forsi ma jaffettwax inti li ħafna, imma forsi int jittrattaw ma 'xi ħaġa li għandha ħafna, ferm aktar affarijiet, u jipprova biss mhuwiex raġonevoli. Iva? UDJENZA: Stenna, hekk ikollok 26 ittri f'kull wieħed wieħed? SPEAKER 1: Mmhmm. Yeah, inti għandek 26. Inti għandek xi hija markatur kelma u mbagħad għandek 26 pointers f'kull wieħed. U dawn qed point-- UDJENZA: U kull 26, ma għandhom kull wieħed ikollhom 26? SPEAKER 1: Iva. U hu għalhekk li, kif inti tista ' tara, hija tespandi pjuttost malajr. Kull dritt. Allura aħna qed tmur biex tikseb fis-siġar, li Inħoss bħal huwa aktar faċli u probabbilment se jkun reprieve ftit sbieħ minn jipprova hemmhekk. Hekk nisperaw ħafna minnkom raw siġra qabel. Mhux bħall-pretty dawk barra, li jiena ma nafx jekk xi ħadd marru barra reċentement. I marru tuffieħ picking dan il-weekend, u oh gosh tiegħi, kien sbieħ. Ma kontx naf weraq tista 'tfittex li pretty. Allura din hija biss siġra, id-dritt? Huwa biss xi node, u punti li mazz ta 'punti strateġiċi oħrajn. Kif qed taraw hawn, dan huwa tip ta 'tema rikorrenti. Lymph tipponta lejn lymph huwa tip ta ' l-essenza ta 'strutturi ta' dejta ħafna. Hija biss tiddependi fuq kif aħna jkollhom magħhom jippuntaw lejn xulxin u kif aħna travers permezz tagħhom u kif aħna daħħal affarijiet li jiddetermina karatteristiċi differenti tagħhom. Hekk biss xi terminoloġija, li stajt użati qabel. Allura għeruq huwa dak kollu li huwa fil-quċċata ħafna. huwa fejn aħna dejjem tibda. Inti tista 'taħseb li bħala l-kap wkoll. Iżda għas-siġar, għandna t-tendenza li jirreferu għaliha bħala l-għerq. Xejn fil-here-- qiegħ fil-ħafna, ħafna bottom-- huma weraq kkunsidrati. Għalhekk tmur flimkien mal- ħaġa sħiħa siġra, id-dritt? Weraq huma fit-truf tal siġra tiegħek. U allura aħna wkoll jkollhom koppja ta ' termini li jitkellmu dwar lymph fir-rigward lil xulxin. Allura aħna għandna ġenitur, tfal, u l-aħwa. Allura f'dan il-każ, 3 huwa l- ġenitur ta '5, 6, u 7. Allura l-ġenitur huwa dak kollu li huwa pass wieħed hawn fuq x'ikun int jirreferu għal, hekk biss bħal siġra tal-familja. Nisperaw, din hija kollha ftit ftit aktar intuwittivi mill-jipprova. Aħwa huma xi li jkollhom l-istess ġenitur, id-dritt? Huma qed fuq l-istess livell hawn. U mbagħad, kif kien qal, tfal huma biss dak kollu li huwa pass wieħed taħt l-node in kwistjoni, OK? Kessaħ. Allura siġra binarju. Jista 'xi ħadd periklu raden fuq waħda mill il-karatteristiċi tas-siġra binarju? UDJENZA: Max żewġ werqiet. SPEAKER 1: Dritt. Allura max ta 'żewġ werqiet. Allura f'dan il-wieħed qabel, kellna dan wieħed li kellhom tlieta, iżda fil-siġra binarju, għandek max ta 'żewġ tfal għal kull ġenitur, id-dritt? Hemm ieħor karatteristika interessanti. Ħadd ma jaf li? Siġra binarju. Allura siġra binarju se jkollhom kollox fuq the-- dan huwa wieħed mhux sorted-- iżda fil-siġra binarju magħżula, kollox fuq il-lemin huwa akbar mill-ġenitur, u kollox fuq ix-xellug huwa inqas mill-ġenitur. U li kien kwizz kwistjoni qabel, hekk tajjeb li tkun taf. Allura l-mod kif aħna jiddefinixxu dan, għal darb'oħra, għandna node ieħor. Dan jidher simili ħafna għal dak? Doppjament Udjenza: Marbuta listi SPEAKER 1: Lista marbuta doppja, id-dritt? Hekk jekk aħna nissostitiwxxu din ma preċedenti u li jmiss, dan ikun lista marbuta doppjament. Iżda f'dan il-każ, aħna fil-fatt jkollhom xellug u lemin u li hu. Inkella, huwa eżattament l-istess. Aħna xorta jkollhom l-element inti qed tfittex, u inti biss għandek żewġ pointers ser ikun x'ikun jmiss. Yeah, siġra tfittxija hekk binarju. Jekk aħna Avviż, kollox fuq il- dritt hawnhekk hija than-- akbar jew kollox immedjatament lejn il-lemin hawn huwa akbar minn, dak kollu hawnhekk huwa inqas minn. Hekk jekk konna biex tfittex permezz, dan għandha tfittex qrib ħafna tfittxija binarju hawn, id-dritt? Ħlief minflok tfittex fuq nofs il-firxa, aħna qed biss tħares lejn jew ix-xellug ġenb jew il-lemin tas-siġra. Hekk jiġrilha ftit aktar sempliċi, I think. Hekk jekk għerq tiegħek huwa NULL, ovvjament huwa biss falza. U jekk huwa hemmhekk, ovvjament huwa veru. Jekk huwa inqas minn, aħna tfittxija ix-xellug. Jekk huwa akbar minn, aħna tfittxija fuq il-lemin. Huwa eżattament bħall tfittxija binarja, biss struttura differenti data li aħna qed jużaw. Minflok firxa, huwa biss siġra binarju. OK, stacks. U wkoll, jidher qisu aħna jista 'jkollhom xi ftit ta' żmien. Jekk nagħmlu, jien kuntent li jmorru fuq kwalunkwe ta 'dan mill-ġdid. OK, hekk stacks. Hawn xi ħadd ftakar dak stacks-- kwalunkwe karatteristika ta 'ċumnija? OK, hekk ħafna minna, I think, jieklu fil-dining halls-- kemm aħna ma tista 'tixtieq li. Imma ovvjament, inti tista 'taħseb ta' munzell litteralment biss bħala munzell ta 'dixxijiet jew munzell ta 'affarijiet. U x'hemm importanti li tirrealizza hija li huwa something-- il-karatteristika li aħna sejħa hija by-- huwa LIFO. Hawn xi ħadd jaf liema li stands għall? Mmhmm? UDJENZA: L-aħħar fl-ewwel out. SPEAKER 1: Dritt, l-aħħar fl-ewwel out. Hekk jekk nafu, jekk aħna qed istivar affarijiet up, l-eħfef ħaġa li grab off-- u forsi l-unika ħaġa li nistgħu grab off jekk munzell tagħna huwa enough-- big huwa dak l-element top. Sabiex ikun x'ikun tpoġġa fuq last-- kif naraw hawn, ikun x'ikun kien imbuttat fuq l-aktar recently-- huwa se tkun l-ewwel ħaġa li aħna pop off, OK? Allura dak li għandna hawnhekk huwa Struct typedef ieħor. Dan huwa verament biss bħal crash kors fl-istruttura tad-data, hekk hemm ħafna jintefgħu fil int guys. I know. Allura għadhom Struct ieħor. Yay għal strutturi. U f'dan il-każ, huwa xi pointer għal firxa li għandha xi kapaċità. Allura dan jirrappreżenta munzell tagħna hawn, bħal firxa attwali tagħna thats azjenda elementi tagħna. U allura hawnhekk għandna xi daqs. U tipikament, inti tixtieq li żżomm rekord ta 'kemm hu kbir munzell tiegħek huwa għaliex dak li għaddej biex jippermettu inti tagħmel hija jekk inti taf l-daqs, din tippermetti li inti tgħid, OK, I am fil-kapaċità? Nista żid xejn aktar? U wkoll jgħidlek fejn il-quċċata tal-munzell tiegħek huwa sabiex inti tkun taf dak li inti jistgħu attwalment tluq. U li fil-fatt se jkun ftit aktar ċara hawn. Allura għal push, ħaġa waħda, jekk inti kienu qatt biex jimplimentaw timbotta, kif I kien biss qal, tiegħek munzell għandu daqs limitat, id-dritt? Firxa tagħna kellhom xi kapaċità. Huwa ta 'firxa. Huwa daqs fiss, għalhekk għandna bżonn li kun żgur li aħna mhux qed tqegħid aktar fis firxa tagħna minn aħna attwalment ikollhom spazju għall. Allura meta int ħolqien push funzjoni, l-ewwel ħaġa li għandek tagħmel hu ngħidu aħna, OK, għandi spazju fil munzell tiegħi? Għaliex jekk jien ma, sorry, I ma jista 'jaħżen element tiegħek. Jekk I do, imbagħad inti tixtieq li taħżen huwa fil-quċċata tal-munzell, id-dritt? U dan huwa għaliex għandna li jżommu rekord ta 'daqs tagħna. Jekk aħna ma jżommu rekord ta 'daqs tagħna, ma nafux fejn li tqiegħed lilha. Aħna ma nafx kif ħafna affarijiet huma fil-firxa tagħna diġà. Bħal ovvjament hemm modi li forsi inti tista 'tagħmel dan. Inti tista initialize kollox biex NULL u mbagħad tiċċekkja għall-aħħar NULL, imma ħaġa ferm aktar faċli huwa biss ngħid, OK, jżommu rekord ta 'daqs. Like I know I jkollhom erba 'elementi fil-firxa tiegħi, sabiex il-ħaġa li jmiss li nitfgħu fuq, aħna qed ser taħżen bl-indiċi 4. U allura, ovvjament, dan ifisser li inti stajt imbuttat b'suċċess xi ħaġa fuq munzell tiegħek, inti tixtieq li jiżdied id-daqs sabiex tkun taf fejn inti hekk li inti tista timbotta aktar affarijiet fuq. Hekk jekk aħna qed jippruvaw pop xi ħaġa off-munzell, x'jista 'jkun l-ewwel ħaġa li aħna rridu li jikkontrolla għal? Inti qed tipprova tieħu xi ħaġa off munzell tiegħek. Inti żgur hemm xi ħaġa fil munzell tiegħek? No Allura dak li jista rridu li jivverifika? UDJENZA: [inaudible]. SPEAKER 1: Iċċekkja għad-daqs? Daqs. Hekk irridu tikkontrolla biex tara jekk Daqs tagħna huwa akbar minn 0, OK? U jekk huwa, allura aħna rridu li jonqos Daqs tagħna ta '0 u ritorn dak. Għaliex? Fl-ewwel waħda konna imbuttar, aħna imbuttat dan fuq id-daqs u d-daqs mbagħad aġġornati. F'dan il-każ, aħna qed decrementing daqs u mbagħad tieħu off, qlugħ minn firxa tagħna. Għaliex jista nagħmlu dan? Mela jekk ikolli ħaġa waħda fuq munzell tiegħi, dak li jkun daqs tiegħi f'dak il-punt? 1. U fejn tkun element 1 maħżuna? Fuq liema indiċi? UDJENZA: 0. SPEAKER 1: 0. Allura f'dan il-każ, aħna dejjem bżonn tagħmel sure-- minflok jirritornaw daqs minus 1, għaliex aħna jafu li l-element tagħna huwa ser jiġi maħżun fl-1 inqas irrispettivament mid-daqs tagħna huwa, dan biss jieħu kura ta 'dan. Huwa mod ftit aktar eleganti. U aħna biss decrement tagħna daqs u mbagħad daqs jirritornaw. Mmhmm? UDJENZA: I raden biss b'mod ġenerali, għaliex kieku din l-istruttura tad-data tkun ta 'benefiċċju? SPEAKER 1: Hija tiddependi fuq il-kuntest tiegħek. Allura għal xi wħud mill-teorija, jekk inti qed jaħdmu with-- OK, let me ara jekk ikun hemm wieħed benefiċċju li huwa ta 'benefiċċju għal aktar minn barra ta 'CS. Bil stacks, kwalunkwe ħin għandek bżonn li jżommu rekord ta 'xi ħaġa li huwa l-aktar reċentement miżjud huwa meta int ser jridu jużaw munzell. U ma nistax think ta 'tajba Eżempju ta 'dan id-dritt issa. Imma kull darba li l-aktar reċenti ħaġa hija aktar importanti għalik, li meta munzell se tkun utli. Jien jippruvaw biex jaħsbu jekk hemm waħda tajba għal dan. Jekk I think ta 'eżempju tajjeb fil-li jmiss 20 minuta, I definittivament se jgħidlek. Iżda b'mod ġenerali, jekk hemm xi ħaġa, bħal I said aktar, fejn l-aktar reċenti huwa l-aktar importanti, thats fejn munzell tidħol fis-play. Billi kjuwijiet huma tip ta 'l-oppost. U l-klieb ftit. Huwa ma 'dan kbira, id-dritt? Inħoss bħal I għandhom biss ikollhom video bunny lemin fin-nofs ta ' taqsima għalik guys minħabba li din hija sezzjoni intensa. Hekk kju. Bażikament kju huwa bħal linja. You guys jien użu ċert li din ta 'kuljum, eżatt bħal fil swali dining tagħna. Allura aħna għandna biex tmur fil- u jiksbu trejs tagħna, jien żgur inti għandek tistenna fil-linja swipe jew tikseb l-ikel tiegħek. Allura l-differenza hawn hija li dan huwa FIFO. Hekk jekk LIFO kienet l-aħħar fl-ewwel out, FIFO huwa l-ewwel fl-ewwel out. Allura dan huwa fejn kwalunkwe inti tpoġġi fuq l-ewwel huwa tiegħek aktar importanti. Mela jekk inti kienu qed jistennew fil line-- tista 'inti jimmaġina jekk inti marru biex mur jiksbu l-iPhone ġodda u kien munzell fejn il- aħħar persuna fil-linja ltqajna ewwel, nies se joqtlu lil xulxin. Allura FIFO, aħna qed kollha familjari ħafna mal fid-dinja reali hawnhekk, u dan kollu għandu ma 'attwalment tip ta 'recreating din il-linja kollu u queuing istruttura. Allura billi mal-munzell, għandna push u pop. Bil-kju, għandna enqueue u dequeue. Allura enqueue bażikament ifisser poġġih fuq id-dahar, u mezzi dequeue tieħu off minn quddiem. Allura istruttura tad-data tagħna huwa ftit aktar ikkumplikata. Għandna t-tieni ħaġa li jżommu rekord ta. Allura mingħajr ir-ras, din huwa eżattament munzell, id-dritt? Dan huwa l-istess struttura bħal munzell. L-unika ħaġa differenti issa hija aħna jkollhom dan il-kap, li x'taħseb se jżommu rekord ta '? UDJENZA: L-ewwel wieħed. SPEAKER 1: Dritt, il- ewwel ħaġa li nitfgħu fl. Il-kap tal-kju tagħna. Kulmin huwa l-ewwel fil-linja. Kull dritt, hekk jekk nagħmlu enqueue. Għal darb'oħra, ma 'xi dawn l-istrutturi tad-data, peress li aħna qed jittrattaw ma 'firxa, għandna bżonn li jiċċekkja jekk ikollna spazju. Dan huwa tip simili me javżak inti guys, jekk inti tiftaħ fajl, għandek bżonn sabiex jikkontrolla għal null. Ma 'kwalunkwe minn dawn stacks u kjuwijiet, inti għandek bżonn biex tara jekk hemm spazju għax aħna qed jittrattaw ma 'firxa daqs fiss, kif naraw here-- 0, 1 kollha sa 5. Allura dak li nagħmlu fil-każ hija verifika biex tara jekk aħna xorta jkollhom spazju. Huwa d-daqs tagħna inqas minn kapaċità? Jekk iva, għandna bżonn li jaħżinha bir il-denb u aħna aġġornament daqs tagħna. Allura dak li jista 'jkun l-denb f'dan il-każ? Mhuwiex espliċitament miktub. Kif aħna taħżen dan? Liema jkun l-denb tkun? Mela ejja jimxu permezz ta dan l-eżempju. Allura dan huwa firxa ta 'daqs 6, id-dritt? U għandna d-dritt issa, id-daqs tagħna hija ta '5. U meta aħna poġġih fil, li għaddej li jmorru fil-ħames indiċi, id-dritt? Allura jaħżen fil denb. Mod ieħor biex jiktbu denb kien biss jkun array tagħna fuq indiċi tad-daqs, id-dritt? Dan huwa d-daqs 5. Ħaġa li jmiss se jmorru fil-5. Kessaħ? OK. Jiġrilha ftit aktar kumplikata meta nibdew messing mal-kap. Iva? UDJENZA: Dan ifisser li aħna kien iddikjara firxa li kien ta 'ħames elementi twil u allura aħna qed żżid fuq dan? SPEAKER 1: No Allura f'dan il-każ, dan huwa munzell. Dan ikun dikjarat bħala firxa ta 'daqs 6. U f'dan il-każ, aħna biss ikollhom spazju wieħed xellug. OK, hekk ħaġa waħda hija f'din każ, jekk ewlieni tagħna huwa ta '0, allura aħna biss tista 'żżid fil-daqs. Iżda jiġrilha ftit delikati għaliex fil-fatt, huma ma jkollhomx slide għal dan, hekk jien ser tiġbed waħda għaliex mhuwiex pjuttost li sempliċi ladarba inti tibda jwarrbu ta 'affarijiet. Allura billi ma munzell inti biss qatt biex joqogħdu jinkwetaw dwar dak id-daqs huwa meta int żżid xi ħaġa fuq, bil kju għandek bżonn ukoll li tagħmel żgur li l-kap tiegħek hi ġġustifikata, għaliex ħaġa jibred dwar kjuwijiet hija li jekk int ma fil-kapaċità, inti tista 'attwalment jagħmilha around. OK, hekk wieħed thing-- oh, dan huwa ġibs terribbli. Ħaġa waħda li wieħed għandu jikkonsidra huwa l-każ. Aħna ser biss tagħmel ħamsa. OK, hekk aħna qed tmur biex jiġifieri l-ras hija hawnhekk. Dan huwa ta '0, 1, 2, 3, 4. Il-kap hemm, u jekk jogħġbok jkollhom affarijiet fihom. U rridu li żżid xi ħaġa fil, id-dritt? Allura l-ħaġa li għandna bżonn li jafu hu li l-kap huwa dejjem ser jiċċaqalqu b'dan il-mod u imbagħad loop lura madwar, OK? Allura dan kju għandha l-ispazju, id-dritt? Hija għandha spazju fil-bidu nett, tip ta 'l-oppost ta' dan. Allura dak li għandna bżonn tagħmel hu li aħna bżonn jikkalkulaw il-denb. Jekk taf li tiegħek ras ma mxietx, denb huwa biss array tiegħek l-indiċi tad-daqs. Iżda fir-realtà, jekk inti qed tuża kju, kap tiegħek huwa probabbilment qed tiġi aġġornata. Allura dak li għandek bżonn tagħmel huwa attwalment tikkalkula l-denb. Allura dak li nagħmlu hu din il-formula hawn, li jien ser tavżak guys jaħsbu dwar, u allura aħna ser nitkellmu dwar dan. Allura dan huwa kapaċità. Allura dan se attwalment jagħtuk mod biex tagħmel dan. Għaliex f'dan il-każ, liema? Ewlieni tagħna huwa fl-1, id-daqs tagħna huwa ta '4. Jekk aħna MOD dik b'5, aħna nikseb 0, li huwa fejn għandna input. Hekk allura fil-każ li jmiss, jekk konna biex jagħmlu dan, ngħidu, OK, ejja dequeue xi ħaġa. Aħna dequeue dan. Nieħdu out dan l-element, id-dritt? U issa ras tagħna hija li tipponta hawn, u aħna tixtieq iżżid fil ħaġa oħra. Dan huwa bażikament l- dahar tal-linja tagħna, id-dritt? Kjuwijiet tista wrap madwar il-firxa. Din kienet waħda mir-differenzi ewlenin. Stacks, inti ma tistax tagħmel dan. Bil kjuwijiet, inti tista minħabba li l-kwistjonijiet hija li inti taf liema ġie miżjud l-aktar reċentement. Peress li kollox se jiġi miżjud fil- id-direzzjoni leftward, f'dan il-każ, u mbagħad wrap madwar, inti tista ' tkompli tqegħid fl-elementi ġodda fuq quddiem tal-firxa għaliex mhuwiex verament quddiem tal-firxa jibqgħalu. Inti tista 'taħseb l-bidu tal- array fejn ras tiegħek fil-fatt hu. Allura din il-formula huwa kif inti tikkalkula denb tiegħek. Does li jagħmel sens? OK. OK, dequeue, u mbagħad inti guys jkollhom 10 minuti li jistaqsu lili xi mistoqsijiet li tiċċara trid, għaliex naf huwa crazy. Kull dritt, hekk fl-istess way-- I do not know jekk inti guys ndunat, iżda CS hija kollha dwar ix-xejriet. Affarijiet huma pjuttost l- istess, biss ma tweaks ċkejkna. Allura istess ħaġa hawn. Għandna bżonn biex tikkontrolla biex tara jekk aħna fil-fatt ikollhom xi ħaġa fil-kju tagħna, id-dritt? Say, OK, huwa d-daqs tagħna akbar minn 0? Kessaħ. Jekk nagħmlu, allura nimxu ras tagħna, li huwa dak I biss murija hawn. Aħna aġġornament ras tagħna tkun waħda aktar. U allura aħna decrement tagħna daqs u jirritorna l-element. Hemm ħafna aktar konkret kodiċi fuq study.cs50.net, u I jirrakkomanda ħafna li jmorru permezz ta 'dan jekk ikollok ħin, anki jekk huwa biss a-kodiċi psewdo. U jekk inti guys trid titkellem permezz li miegħi waħda fuq waħda, jekk jogħġbok let me jafu. I d jkunu kuntenti li. Strutturi ta 'dejta, jekk tieħu CS 124, inti ser jafu li l-istrutturi tad-data jiksbu ħafna gost u dan huwa biss bidu. So I know huwa diffiċli. Huwa OK. Aħna jissieltu. I still do. Sabiex ma joqogħdu jinkwetaw wisq dwar dan. Iżda li hija bażikament tiegħek crash kors fl-istrutturi tad-data. Naf huwa ħafna. Hemm xi ħaġa li aħna tixtieq li tmur aktar mill-ġdid? Xejn rridu nitkellmu permezz? Iva? UDJENZA: Għal dak eżempju, hekk il-denb ġdida hija ta '0 fuq dak? SPEAKER 1: Iva. UDJENZA: OK. Mela allura għaddejjin, youd għandek 1 plus 4 or-- SPEAKER 1: Allura inti kienu jgħidu, meta irridu imorru tagħmel dan mill-ġdid? UDJENZA: Yeah. Mela jekk inti kienu jidhru out-- fejn huma inti kalkolu tal-denb minn fil-li? SPEAKER 1: Allura l-denb kien in-- I mibdula din. Allura f'dan l-eżempju hawn, dan kien l-array aħna qed tħares lejn, OK? Allura aħna għandna affarijiet fil-1, 2, 3, u 4. Allura aħna għandna ewlieni tagħna huwa ugwali għal 1 fil- dan il-punt, u d-daqs tagħna huwa ugwali għal 4 f'dan il-punt, id-dritt? Inti kollha jaqblu li huwa l-każ? Allura nagħmlu l-kap plus-daqs, li jagħtina 5, u allura aħna Mod b'5. Nikbru 0, li tgħidilna li huwa 0 fejn huwa denb tagħna, fejn għandna l-ispazju. UDJENZA: X'hemm għatu? SPEAKER 1: Il-kapaċità. Jiddispjacini. Allura li huwa d-daqs ta 'firxa tiegħek. Iva? UDJENZA: [inaudible] qabel nerġgħu lura l-element? SPEAKER 1: Allura aħna nimxu l- ras jew jirritornaw il-mument? Hekk jekk nimxu wieħed, decrement-daqs? Żomm fuq. I definitely nesa ieħor. Qatt f'moħħhom. Ma jkunx hemm formula ieħor. Yeah, inti tixtieq li jirritornaw ir-ras u mbagħad jimxu lura. UDJENZA: OK, għaliex Fuq dan punt, il-kap kien ta '0, u allura inti tixtieq li jirritornaw indiċi 0 u mbagħad jagħmlu ras 1? SPEAKER 1: Dritt. Naħseb li hemm ieħor formula tip ta 'bħal dan. I ma jkollhomx dan fuq il-quċċata tar-ras tiegħi bħala Ma rridx li jtik l-waħda ħażina. Imma naħseb li huwa perfettament valida biex jiġifieri, OK, taħżen din element-- x'ikun element ras is-- decrement tiegħek daqs, jimxu ras tiegħek fuq, u r-ritorn kwalunkwe li element huwa. C'est perfettament valida. OK. Inħoss bħal dan mhuwiex bħall-most-- int ma ser jimxu minn hawn simili, iva, naf jipprova. I ltqajna kollha. C'est OK. I wegħda. Imma l-istrutturi tad-data huma xi ħaġa li hija tieħu ħafna ħin biex jidraw. Probabilment waħda mill-agħar affarijiet, I think, fil-kors. Allura huwa definittivament tieħu ripetizzjoni u tfittex at-- I ma verament jafu listi marbuta sal I għamilt bogħod wisq magħhom, bl-istess mod li għamilt ma verament jifhem pointers sal I kellna biex jgħallmu għal żewġ snin u tagħmel psets tiegħi stess magħha. Huwa jieħu ħafna ta 'tennija u l-ħin. U eventwalment, se tip ta 'ikklikkja. Iżda fil-frattemp, jekk għandek tip ta 'fehim livell għoli ta' liema dawn jagħmlu, punti favur u cons-- li huwa dak aħna verament tendenza li jenfasizzaw, speċjalment fil-kors intro. Bħal, għaliex kieku nużaw jipprova fuq firxa? Bħal, liema huma l-pożittivi u negattivi ta 'kull wieħed minn dawk? U jifhmu l-kompromessi bejn kull wieħed minn dawn l-istrutturi huwa dak ħafna aktar importanti dritt issa. Jista 'jkun hemm wieħed crazy kwistjoni jew tnejn li l- ser jgħidlek biex jimplimentaw push jew jimplimentaw pop jew enqueue u dequeue. Iżda għall-parti l-kbira, li dak fehim livell ogħla u aktar ta 'ħakma intuwittivi huwa aktar importanti milli fil-fatt jkunu jistgħu jimplimentawha. Huwa d jkun verament tal-biża jekk lilkom kollha tista 'tmur out u jmorru jimplimentaw jipprova, iżda aħna nifhmu mhuwiex neċessarjament l-aktar ħaġa raġonevoli dritt issa. Imma inti tista 'fil pset tiegħek, jekk inti tixtieq għal, u allura inti ser tingħata prattika, u mbagħad forsi inti taf verament jifhmu dan. Iva? UDJENZA: OK, iva, liema huma aħna maħsuba biex jużaw fil-pset? Do I bżonn tuża wieħed minnhom? SPEAKER 1: Iva. Hekk ikollok l-għażla tiegħek. I raden f'dan il-każ, nistgħu jitkellmu dwar il-pset ftit minħabba I dam permezz ta 'dawn. Hekk fil pset tiegħek, inti għandek tiegħek għażla ta 'tipprova jew tabelli hash. Xi nies se jippruvaw u jintużaw filtri blanzun, iżda dawk teknikament mhumiex korretti. Minħabba n-natura probabilistic tagħhom, dawn jagħtu pożittivi foloz kultant. Huma qed tfittex jibred fi, għalkemm. Jirrakkomanda ħafna tfittex lejn lilhom mill-inqas. Imma għandek l-għażla tiegħek bejn tabella hash u jipprova. U li għaddej biex jkun fejn inti tagħbija fil tiegħek dizzjunarju. U ikollok bzonn li jagħżlu funzjoni hash tiegħek, ikollok bzonn li jagħżlu kif ħafna Bramel għandek, u se jvarjaw. Bħal jekk għandek aktar bramel, forsi inneħħu run aktar mgħaġġla. Imma forsi int wasting lott ta 'spazju li mod, għalkemm. Int għandek figura hija out. Mmhmm? UDJENZA: Inti qal qabel li nistgħu nużaw funzjonijiet oħra hash, li aħna ma jkollhom toħloq funzjoni hash? SPEAKER 1: Iva, id-dritt. Allura litteralment għall-funzjoni hash tiegħek, bħal google "funzjoni hash" u tfittex xi dawk jibred. Inti mhux mistennija li jibnu funzjonijiet hash tiegħek stess. Nies iqattgħu tagħhom teżijiet fuq dawn l-affarijiet. Allura ma joqogħdu jinkwetaw dwar il-bini tiegħek stess. Isibu waħda online biex tibda bil. Xi wħud minnhom inti għandek jimmanipulaw ftit biex jagħmlu tipi ritorn żgur jaqblu u whatnot, hekk fil-bidu, I jirrakkomanda jużaw xi ħaġa verament faċli li forsi ftit hashes fuq l-ewwel ittra. U mbagħad darba inti għandek li xogħol, jinkorporaw funzjoni hash cooler. Mmhmm? UDJENZA: Would jipprova jkun jew effiċjenti iżda biss diffiċli biex, like-- SPEAKER 1: Allura jipprova, I think, huwa intuwittivament diffiċli biex jiġu implimentati iżda huwa mgħaġġel ħafna. Madankollu, jieħu aktar spazju. Għal darb'oħra, inti tista jottimizzaw kemm ta 'dawk fil- modi differenti u hemm modi to-- UDJENZA: Kif aħna gradat fuq dan? Ma matter-- SPEAKER 1: Allura inti qed gradati mod normali. Inti qed tmur biex jiġi ggradat fuq disinn. Liema mod inti tagħmel, inti tixtieq li kun ċert li huwa kif eleganti kemm jista 'jkun u effiċjenti kemm jista 'jkun. Imma jekk inti tagħżel jipprova jew hash tabella, sakemm taħdem, aħna kuntenti ma 'dak. U jekk inti tuża xi ħaġa li hashes fuq l-ewwel ittra, li l-multa, bħal forsi bħall-disinn għaqli. Aħna wkoll qed jilħaq il- punt f'dan semester-- I do not know jekk inti guys noticed-- jekk int gradi pset jonqsu ftit minħabba d-disinn u whatnot, li perfettament multa. Huwa jkollna sa punt fejn tiegħek programmi huma jkollna aktar ikkumplikata. Hemm aktar postijiet inti tista 'ttejjeb fuq. Allura huwa perfettament normali. Mhuwiex li int tagħmel agħar fuq pset tiegħek. Huwa biss aħna qed qed diffiċli fuqek issa. Allura kulħadd tħossok. I biss gradati psets kollha tiegħek. Naf kulħadd qed tħossok. Allura ma tkun inkwetat dwar dan. U jekk għandek xi mistoqsijiet dwar psets qabel jew modi inti tista 'ttejjeb, I jippruvaw u jikkummentaw il speċifika postijiet, imma xi kultant huwa tard u niġi għajjien. Hemm xi affarijiet oħra dwar strutturi ta 'dejta? Jien ċert li inti guys ma verament trid titkellem dwarhom aktar, imma jekk ikun hemm, jien kuntent li jmorru fuqhom, kif ukoll xi ħaġa minn lecture dan passat ġimgħa jew ġimgħa li għaddiet. Naf aħħar ġimgħa kienet kollha ta 'reviżjoni, hekk aħna jista 'jkollhom skipped fuq xi reviżjoni minn lecture. Kwalunkwe mistoqsijiet oħra I jistgħu jwieġbu? OK, id-dritt. Ukoll, inti guys toħroġ 15 minuta kmieni. Nispera li din kienet semi-utli għall-inqas, u jien se tara inti guys ġimgħa d-dieħla, jew ħinijiet tal-uffiċċju Ħamis. Hemm talbiet għal snacks għall-ġimgħa d-dieħla, huwa l-ħaġa? Minħabba I nesa kandju illum. U I miġjuba kandju aħħar ġimgħa, iżda kienet Jum Columbus, għaldaqstant kien hemm bħal sitt persuni li kellu erba 'boroż ta' kandju lilhom infushom. I tista 'ġġib starbursts ġdid jekk inti tixtieq. Starbursts? OK, ħsejjes tajba. Have jum kbir, guys.