[MUSIC Playing] Gjuha 1: Në rregull. Gjithkush mirëpritur përsëri në seksion. Unë shpresoj që ju të gjithë janë të suksesshme mbulohen nga quiz tuaj nga java e kaluar. Unë e di se është pak i çmendur në kohë. Si unë isha duke thënë para, në qoftë se ju jeni në devijimin standard, vërtetë nuk shqetësohen për këtë, sidomos për një seksion më pak të rehatshme. Kjo është në lidhje ku ju duhet të jetë. Në qoftë se ju e bëri të madh, atëherë awesome. Kudos për ju. Dhe në qoftë se ju ndjeheni si ju keni nevojë për pak më shumë ndihmë, ju lutem të ndjehen të lirë për të arritur jashtë tek ndonjë nga TFS. Ne të gjithë jemi këtu për të ndihmuar. 

Kjo është arsyeja pse ne mësojmë. Kjo është arsyeja pse unë jam këtu çdo të hënë për ju djema dhe në zyrën orë në enjteve. Pra ju lutem mos ngurroni të më lejoni të dini në qoftë se ju jeni të shqetësuar në lidhje me ndonjë gjë ose në qoftë se ka ndonjë gjë në quiz që ju të vërtetë do të doja të adresuar. 

Kështu që rendi i ditës për sot është të gjitha në lidhje me strukturat e të dhënave. Disa nga këto janë vetëm do të jetë vetëm për të marrë ju familjarizuar me këto. Ju nuk mund kurrë të zbatojë ata në këtë klasë. Disa prej tyre ju do të, si për pset tuaj diktim. 

Ju do të keni zgjedhjen tuaj në mes të tabelave hash dhe përpiqet. Pra, ne patjetër do të shkojnë mbi ata. Ajo do të jetë patjetër më shumë e llojit e një seksioni të nivelit të lartë sot, megjithatë, sepse ka shumë prej tyre, dhe nëse shkuam në detajet e zbatimit në të gjitha këto, ne nuk do të merrni edhe përmes listave të lidhura dhe ndoshta pak e tabelave hash. 

Pra, të kesh durim me mua. Ne nuk jemi duke shkuar për të bërë aq sa coding këtë kohë. Nëse keni ndonjë pyetje në lidhje me të apo ju doni të shihni të zbatuar ose të përpiqen atë për veten tuaj, Unë patjetër të rekomandojë do të study.cs50.net, e cila ka shembuj të gjitha këto. Ajo do të ketë PowerPoints mia me shënimet që kemi kanë tendencë për të përdorur, si dhe disa programe ushtrime, sidomos për gjërat si listat e lidhura dhe binar pemët oxhaqet dhe cues. Pra, pak më shumë të nivelit të lartë, i cili mund të jetë mirë për ju djema. 

Pra, me këtë, ne do të merrni filluar. Dhe gjithashtu, kuize yes--. Unë mendoj se shumica prej jush të cilët janë në Pjesa ime kanë kuize tuaj, por dikush vjen në apo ndonjë arsye ju nuk e bëjnë, ata janë të drejtë këtu në para. 

Pra lidhura listat. Unë e di këtë lloj shkon për të mbështetur para quiz tuaj. Kjo ishte java e parë që kemi mësuar në lidhje me këtë. Por në këtë rast, ne do të vetëm shkoni pak më në thellësi. 

Pra, pse mund të kemi zgjedhur a lidhur listë mbi një grup? Çfarë e dallon ato? Po? 

AUDIENCA: Ju mund të zgjerohet a lidhur lista kundrejt madhësinë e caktuar një grup të. Gjuha 1: E drejta. Një grup ka caktuar madhësinë ndërsa a listë e lidhur ka një madhësi të ndryshueshme. Pra, nëse ne nuk e dimë se si shumë ne duam të ruajtur, një listë e lidhur na jep një të madhe mënyrë për të bërë këtë, sepse ne mund vetëm të shtoni në një nyje dhe shtoni për një nyje dhe të shtoni në një tjetër nyje. Por çfarë mund të jetë një tregti-off? A ka dikush kujtohet tregtisë-off midis vargjeve dhe listat lidhura? Mmhmm? 

AUDIENCA: Ju duhet të të kalojnë nëpër të gjithë rrugën përmes lista lidhur të gjejnë një element në një listë. Në një grup, ju mund të vetëm të gjejnë një element. 

Gjuha 1: E drejta. Pra me arrays-- 

Audienca: [padëgjueshme]. 

Gjuha 1: Me vargjeve, ne kemi ajo quhet e gjallë. Do të thotë se në qoftë se ne duam atë që është e ndonjëherë pika e pestë e një liste ose pika e pestë e tonë array, ne vetëm mund të rrëmbej atë. Në qoftë se kjo është një listë e lidhur, ne kemi për të iterate nëpër, e drejtë? Pra, qasja në një element në një koleksion është koha konstante, ndërsa me një listë e lidhur kjo do të ka shumë të ngjarë të jetë koha linear, sepse ndoshta element ynë është të gjithë rrugën në fund. Ne kemi për të kërkuar me çdo gjë. Pra, me të gjitha këto të dhëna Strukturat ne jemi duke shkuar që të ketë kaluar një kohë pak më tutje, Cilat janë pluses dhe negative. Kur mund të duam të përdorni një lidhje të tjera? Dhe kjo është lloj i Gjëja më e madhe për të marrë larg. 

Kështu që ne kemi këtu Përkufizimi i një nyje. Është si një element në listën tonë të lidhur, e drejtë? Pra, ne të gjithë jemi të njohur me structs tona typedef, të cilat ne kaloi në shqyrtim për herë të fundit. Ajo ishte në thelb vetëm duke krijuar një lloj të dhënave që ne mund të përdorim. 

Dhe në këtë rast, është një nyjë se do të mbajë një numër të plotë në. Dhe pastaj çfarë është pjesa e dytë këtu? Çdokush? 

Audienca: [padëgjueshme]. 

Gjuha 1: Po. Kjo është një tregues për nyjen e ardhshëm. Pra, kjo duhet të jetë në fakt deri këtu. Ky është një tregues i tipit nyje për gjë tjetër. Dhe kjo është ajo që ata përfshin nyje tonë. Ftohtë. 

Të gjithë të drejtë, kështu që me kërkimin, siç ishim vetëm duke thënë se para se të dorës, në qoftë se ju jeni do të kërkoni përmes, ju duhet të vërtetë iterate nëpër listën tuaj të lidhura. Pra, në qoftë se ne jemi duke kërkuar për numrin 9, ne do të fillojë në kokën tonë dhe që na tregon në fillim e listës sonë të lidhura, e drejtë? Dhe ne themi, OK, e bën këtë nyje të përmbajë numrin 9? Nuk ka? 

Të gjitha të drejtat, të shkojnë në një tjetër. Ndiqni atë. A do të përmbajë numrin 9? Jo. Ndiqni një tjetër. 

Pra, ne duhet të vërtetë të iterate përmes listën tonë të lidhura. Ne nuk mund të shkoni direkt aty ku është 9. Dhe në qoftë se ju djema të vërtetë duan të të shihni disa pseudo-kod deri atje. Ne kemi një funksion kërkimi këtu që merr in-- çfarë do të marrë në? Çfarë mendoni ju? Një mënyrë të lehtë. Çfarë është kjo? Audienca: [padëgjueshme]. Gjuha 1: Numri që ne jemi duke kërkuar për të. E drejtë? Dhe çfarë kjo do të korrespondojnë me? Kjo është një tregues për të? 

AUDIENCA: Një nyjë. 

Gjuha 1: Një nyjë në listën që ne jemi duke kërkuar në, e drejtë? Pra, ne kemi disa nyjet janë akrep këtu. Kjo është një pikë që do të në fakt iterate nëpër listën tonë. Ne kemi vendosur të barabartë me lista sepse kjo është vetëm vendosjen ajo barabartë tek fillimin e listën tonë të lidhura. 

Dhe ndërsa ajo nuk është NULL, ndërsa ne ende kemi gjëra në listën tonë, kontrolloni për të parë nëse kjo nyjë ka numri ne jemi duke kërkuar për të. Kthimi vërtetë. Përndryshe, të rinovuar atë, e drejtë? 

Nëse kjo është NULL, ne dalje tonë ndërsa loop dhe kthimit të rreme sepse kjo do të thotë që ne nuk kemi gjetur atë. Ka marrë të gjithë se si punon kjo? OK. 

Pra, me futje, ju kanë tre mënyra të ndryshme. Ju mund të prepend, ju mund të append dhe ju mund të futni në të ndryshme. Në këtë rast, ne jemi do të bëjë një prepend. A di ndokush se si ato tre raste mund të ndryshojnë? 

Pra prepend do të thotë se ju vendosni atë në frontin e listës suaj. Kështu që do të thotë se nuk ka rëndësi çfarë nyje juaj, pa marrë parasysh çfarë vlera është, ju do të jeni për ta vënë atë të drejtë këtu para, OK? Ajo do të jetë i pari element në listën tuaj. 

Nëse ju append atë, ajo do për të shkuar në pjesën e prapme të listës suaj. Dhe të futur në të ndryshme do të thotë që ju jeni do të vënë vërtetë në vend ku ajo mban lista juaj lidhura renditura. Përsëri, si ju përdorni ata dhe kur ju përdorni ata do të ndryshojnë në varësi të rastit tuaj. Në qoftë se kjo nuk ka nevojë të të ndahen, prepend tenton të jetë ajo që shumica e njerëzve përdorin për shkak se ju nuk e bëni duhet të kalojnë nëpër të gjithë listën për të gjetur në fund për të shtuar atë, e drejtë? Ju vetëm mund të rrinë atë të drejtë në. 

Pra, ne do të shkojnë përmes një futje 1 tani. Pra, një gjë që unë jam duke shkuar për highly recomend në këtë pset është për të nxjerrë gjërat jashtë, si gjithmonë. Është shumë e rëndësishme që ju update në mënyrë korrekte pointers tuaj sepse në qoftë se ju update ato pak nga e rendit, ju jeni do të përfundojë deri në humbur pjesë të listës suaj. 

Kështu për shembull, në këtë rast, ne jemi duke i thënë kreu në vetëm pikën 1. Nëse ne vetëm të bëjë atë pa kursim këtë 1, ne nuk kemi ide se çfarë 1 duhet të tregojnë tani sepse ne kemi humbur atë kreu vuri në dukje. Pra, një gjë për të kujtuar kur ju jeni duke bërë një prepend është për të shpëtuar çfarë të Pikat e kreu për të parë, pastaj reassign atë, dhe pastaj update çfarë nyje tuaj të re duhet të tregojë. Në këtë rast, kjo është një mënyrë për të bërë atë. 

Pra, nëse ne e kishte bërë atë në këtë mënyrë ku ne vetëm ricaktuar kokën, kemi humbur thelb tonë gjithë listën, e drejtë? Një mënyrë për ta bërë këtë është që të ketë 1 pikë për ardhshëm, dhe pastaj kanë pikë qendrore në 1. Ose ju mund të bëni një lloj si magazinimi i përkohshëm, të cilin kam biseduar rreth. 

Por ricaktuar tuaj së pointers në mënyrë korrekte do të jetë shumë, shumë e rëndësishme për këtë pset. Përndryshe, ju jeni do të ketë një hash tavolinë ose një provoni që është vetëm do të jetë vetëm një pjesë e fjalëve që doni dhe pastaj mmhmm you're--? AUDIENCA: Cili ishte i përkohshëm Gjëja e magazinimit ju jeni duke folur për? Gjuha 1: magazinimi i përkohshëm. Pra, në thelb një tjetër mënyrë ju mund të bëni këtë është ruajtur kokën e diçka, si ruajtur atë ndryshore të përkohshme. Të caktojë atë për 1 dhe pastaj update 1 për pikë të çfarëdo kreu përdoret për pikë për të. Kjo mënyrë është e qartë më elegante, sepse ti nuk kanë nevojë për një vlerë të përkohshme, por vetëm duke ofruar një tjetër mënyrë për të bërë atë. Dhe ne fakt nuk kemi disa Kodi për këtë. Pra, për listën e lidhura, ne në të vërtetë kanë disa kodin. Pra futur këtu, kjo është prepending. Pra, kjo hyn atë në kokë. 

Gjëja Pra, së pari, ju duhet të krijuar nyje tuaj të re, natyrisht, dhe kontrolloni për NULL. Gjithmonë i mirë. Dhe atëherë ju duhet të caktojë vlerat. Kurdo që ju të krijoni një nyje të re, ju nuk e di se çfarë ajo është duke treguar të ardhshëm, kështu që ju doni të nisja atë të pavlefshëm. Në qoftë se nuk përfundojnë duke treguar për diçka tjetër, ajo merr jepej dhe kjo është në rregull. Në qoftë se kjo është gjëja e parë në listë, ajo ka nevojë për të tregojnë për pavlefshëm, sepse kjo është fundi i listës. 

Kështu, pra, për të futur atë, ne shohim këtu janë caktuar vlerën e ardhshëm të nyjen tonë të çfarëdo kreu, e cila është ajo që kemi pasur këtu. Kjo është ajo që ne vetëm e bëri. Dhe pastaj ne jemi të caktuar kreu në pikën në nyje tonë të ri, sepse mos harroni, e re është një tregues për një nyje, dhe kjo është pikërisht ajo që kreu. Kjo është arsyeja pse ne kanë këtë shigjetë aksesor. Ftohtë? Mmhmm? 

AUDIENCA: A kemi të nisja tjetër e re për të pavlefshëm të parë, ose mund ne vetëm iniciojnë atë në kokë? 

Gjuha 1: New ardhshëm duhet të jetë NULL për të filluar sepse ju nuk e dini ku ajo do të jetë. Gjithashtu, kjo është lloj i ashtu si një paradigmë. Keni vendosur të barabartë me NULL vetëm për të bërë Sigurohuni që të gjitha bazat e tuaja janë të mbuluara para se të bëni ndonjë ripërcaktimin mënyrë që ju jeni gjithmonë duke garantuar se ai do të të treguar një vlerë të veçantë kundrejt si një vlerë plehrash. Sepse, vërtet, ne të caktojë re ardhshëm automatikisht, por kjo është më shumë vetëm si një praktikë e mirë për të nisja atë në këtë mënyrë dhe pastaj reassign. 

OK, kështu që lidhet dyfish listat tani. Çka ne mendojmë? Çfarë është e ndryshme me lidhur dyfish listat? 

Pra, në listat tona të lidhura, ne mund të vetëm lëvizin në një drejtim, e drejtë? Ne kemi vetëm ardhshëm. Ne mund të shkojnë vetëm përpara. 

Me një listë e lidhur dyfish, ne mund të lëvizin prapa. Pra, ne kemi jo vetëm Numri që ne duam për të ruajtur, ne kemi ku tregon të ardhshëm dhe ku ne sapo ardhur nga. Pra, kjo lejon për disa traversal mirë. 

Nyjet Pra lidhur dyfish, shumë të ngjashme, e drejtë? Dallimi i vetëm është tani ne kanë një tjetër dhe një mëparshme. Është i vetmi ndryshim. 

Pra, në qoftë se ne ishim të prepend ose append-- ne nuk kanë asnjë kod për këtë ide here-- por në qoftë se keni qenë për të përpiqen dhe të futur atë, gjë e rëndësishme është që ju duhet të bëni Sigurohuni që ju jeni caktimin e si tuaj të mëparshme dhe tuaj tregues tjetër të saktë. Pra, në këtë rast, ju do të jo vetëm nisja e ardhshëm, ju nisja e mëparshme. Nëse ne jemi në krye të listës, ne jo vetëm që do të bëjë kreu i barabartë i ri, por duhet të ri previous tonë pikë në kokë, e drejtë? 

Kjo është i vetmi ndryshim. Dhe në qoftë se ju doni më shumë praktikë me këto me listat e lidhura, me futur, me fshirjes, me insert në një listë të ndryshme, ju lutem shikoni study.cs50.net. Ka një bandë e ushtrimeve të mëdha. I highly recomend tyre. Unë uroj që kishim kohë për të shkuar nëpërmjet tyre por ka një shumë të strukturave të të dhënave të depërtonte. 

OK, kështu tavolina hash. Kjo është ndoshta më e bit të dobishme për pset tuaj këtu sepse ju jeni do të jetë zbatimin e një nga këto, ose një provoni. I really like tavolina hash. Ata janë pretty cool. 

Pra, në thelb ajo që ndodh është një tabelë hash është kur ne duhet të vërtetë të shpejtë futje, fshirje, dhe lookup. Këto janë gjërat që ne jemi prioritet në një tabelë hash. Ata mund të merrni mjaft të mëdha, por si ne do të shohim me të përpiqet, ka gjëra që janë shumë më të mëdha. 

Por në thelb, e gjitha një hash Tabela është një funksion hash që ju tregon se cilat kovë për të vënë çdo të të dhënave tuaja, secili prej elementeve tuaja në. Një mënyrë e thjeshtë për të menduar për një tabelë hash është se kjo është vetëm kova e gjërave, e drejtë? Pra, kur ju jeni zgjidhja gjëra nga si shkronjës së parë të emrit të tyre, kjo është lloj i si një tabelë hash. 

Pra, nëse unë do të grup ju djema është në grupe të kushdo që emri fillon me një mbi këtu, ose kushdo që është ditëlindjen është në janar, shkurt, mars, çdo gjë, që është në mënyrë efektive duke krijuar një tabelë hash. Është thjesht krijimin e kova se ju lloj elemente tuaj në në mënyrë që ju mund ta gjeni lehtë. Pra, këtë mënyrë, kur kam nevojë për të gjetur një prej jush, Unë nuk kam për të kërkuar me secilin nga emrat tuaj. Unë mund të jetë si, oh, unë e di se Ditëlindjen Danielle është in-- AUDIENCA: --April. Gjuha 1: April. Kështu që unë shoh në prill mia kovë, dhe me çdo fat, ajo do të jetë vetëm një në atje dhe Koha ime ishte konstante në këtë kuptim, kurse në qoftë se unë duhet të shikoni përmes një bandë e tërë e njerëzve, ajo do të marrë shumë më të gjatë. Pra, tabelat hash janë me të vërtetë vetëm kova. Mënyra më e lehtë për të menduar prej tyre. 

Pra, një gjë shumë e rëndësishme në lidhje me një tabelë hash është një funksion hash. Pra, gjërat që unë vetëm biseduar rreth, si Letra e parë e emrit tuaj të parë apo muaj ditëlindjen tuaj, këto janë ide që me të vërtetë lidhen me një funksion hash. Kjo është vetëm një mënyrë për të vendosur se cilat ju kovë element jeni shkon në, OK? Pra, për këtë pset, ju mund të kërkoni pretty much çdo funksion hash që ju dëshironi. 

Nuk duhet të jenë tuajat. Ka disa ato me të vërtetë ftohtë jashtë ka që të bëjmë të gjitha llojet e matematikë çmendur. Dhe në qoftë se ju doni të bëni tuaj së spellchecker super të shpejtë, Unë do patjetër shikoni në një nga ato. 

Por ka edhe njerëz të thjeshtë, si llogaritin shuma e fjalëve, si çdo letër ka një numër. Të llogaritur shumën. Që përcakton kovë. Ata gjithashtu kanë ato lehtë që janë vetëm si të gjithë të A-së këtu, të gjithë B është këtu. Çdo njëri nga ata. 

Në thelb, ajo vetëm ju tregon se cilat Indeksi array element juaj duhet të shkoni në. Vetëm të vendosë për bucket-- kjo është e gjitha një funksion hash është. Pra, këtu kemi një shembull që është vetëm shkronja e parë e vargut që unë isha vetëm duke folur për të. 

Pra, ju keni disa hash që është vetëm Letra e parë e zbritur tuaj string A, e cila do të ju jap disa numër midis 0 dhe 25. Dhe atë që ju doni të bëni është të sigurohuni që kjo paraqet madhësia e hash tuaj table-- sa kova ka. Me shumë prej tyre funksionet hash, ata janë do të jetë vlera kthehen se mund të jetë shumë më e lartë në numrin e kova që në fakt ju keni në tryezën tuaj hash, kështu që ju duhet të bëni sigurt dhe mod nga ata. Përndryshe, ajo do të thonë, oh, ajo duhet të jetë në kovë 5,000 por ju keni vetem 30 kova në tryezën tuaj të hash. Dhe sigurisht, ne të gjithë e dimë se është e do të rezultojë në disa gabime çmendur. Pra, sigurohuni që të mod nga madhësia e tryezën tuaj hash. Ftohtë. Pra goditjet. Është e të gjithë të mirë deri më tani? Mmhmm? 

AUDIENCA: Pse do të kthehen një vlerë të tillë masiv? 

Gjuha 1: Varësisht nga algorithm se funksioni juaj hash përdor. Disa prej tyre do të bëjmë shumëzimit çmendur. Dhe kjo është e gjitha në lidhje me marrjen a shpërndarje, në mënyrë që ata të bëjnë një të vërtetë gjëra të çmendur nganjëherë. Kjo është e gjitha. Çdo gjë tjetër? OK. 

Pra goditjet. Në thelb, siç kam thënë më parë, në rastin më të mirë, çdo kovë I shikoni në është do të ketë një gjë, kështu që unë nuk duhet të shikoni në të gjitha, apo jo? Unë e di se është ose nuk ka ose ka jo, dhe kjo është ajo që ne të vërtetë duan. Por në qoftë se ne kemi dhjetëra mijëra pika e të dhënave dhe më pak se ky numër e kova, ne do të kemi goditjet ku përfundimisht diçka do të duhet të përfundojë deri në një kovë që tashmë ka një element. 

Pra, pyetja është, çfarë do të bëjmë në këtë rast? Çfarë bëjmë ne? Ne tashmë kemi diçka atje? A kemi vetëm të hedhin atë? 

Jo. Ne kemi për të mbajtur të dy prej tyre. Pra, mënyra që ne zakonisht bëjnë që çfarë? Cila është struktura e të dhënave ne vetëm biseduar rreth? AUDIENCA: Lista Linked. Gjuha 1: Një listë të lidhura. Deri tani, në vend të secilit prej këtyre kova vetëm duke pasur një element, ajo do të përmbajë një listë të lidhur elementet që janë sheshuar në të. OK, ka të gjithë llojet e merrni këtë ide? Sepse ne nuk mund të kemi një rrjet sepse ne nuk e dimë se sa shumë gjëra do të jetë në atje. Një listë e lidhur na lejon të kanë vetëm numrin e saktë se janë sheshuar në atë kovë, e drejtë? 

Pra, kjo ndërhyrje është linear në thelb kjo idea-- kjo është një mënyrë për t'u marrë me një përplasje. Çfarë ju mund të bëni është nëse, në këtë rast, Berry u sheshuar në 1 dhe ne tashmë kemi diçka atje, ju vetëm do të mbajë poshtë deri ju të gjeni një slot bosh. Kjo është një mënyrë për të trajtuar atë. Mënyra të tjera për të trajtuar ajo është me atë që ne vetëm called-- lidhur Lista quhet chaining. 

Pra, kjo ide funksionon, nëse Tabela e juaj hash mendoni është shumë më i madh se Të dhënat tuaja caktuar ose në qoftë se ju doni të provoni dhe të minimizuar chaining derisa kjo është absolutisht e nevojshme. Pra, një gjë është linear probing padyshim do të thotë që funksionin tuaj hash nuk është mjaft aq e dobishme për shkak se ju jeni do të përfundojë duke përdorur funksion tuaj hash, duke arritur në një pikë, ju lineare hetimin poshtë ndonjë vend që është në dispozicion. Por tani, natyrisht, asgjë tjetër që përfundon atje, ju jeni do të duhet të kërkoni edhe më tej poshtë. 

Dhe ka shumë më tepër shpenzim kërkimi që shkon në inputting një element në tryezën tuaj hash tani, apo jo? Dhe tani, kur ju shkoni dhe të provoni dhe për të gjetur kokrra të kuqe përsëri, ju jeni do të hash atë, dhe ajo do të thonë, oh, shikoni në kovë 1, dhe kjo nuk do të jetë në kovë 1, kështu që ju jeni do të duhet të kaloj me pjesën tjetër të tyre. Pra, kjo është nganjëherë e dobishme, por në shumicën e rasteve, ne jemi duke shkuar për të thënë se chaining është ajo që ju doni të bëni. 

Pra, kemi biseduar në lidhje me këtë më herët. Unë kam një miratimin pak nga vetja ime. Por chaining në thelb është se çdo kovë në tryezën tuaj hash është vetëm një listë të lidhura. 

Pra një mënyrë tjetër, ose më shumë teknik mënyrë, të mendojnë për një tabelë hash është se ajo është vetëm një koleksion e listave të lidhura, të cilat kur ju jeni me shkrim fjalorin tuaj dhe ju jeni duke u përpjekur për të ngarkuar atë, duke menduar për atë si një Grup i listave të lidhura do ta bëjë më të lehtë për ju për të nisja. 

Audienca: Pra tabelë hash ka një madhësi të paracaktuar, si një [padëgjueshme] e kova? 

Gjuha 1: E drejta. Pra, ajo ka një numër të caktuar të kova që ju determine-- Cili ju djema duhet të ndjehen të lirë për të luajtur me të. Ajo mund të jetë shumë i ftohtë për të parë se çfarë ndodh si ju të ndryshojë numrin tuaj të kova. Por, vërtet, ajo ka një Numri i vendosur i kova. Çfarë ju lejon të përshtatet si shumë elemente si ju duhet është kjo chaining të veçantë ku ju kanë lidhur listat në çdo kovë. Kjo do të thotë tryezën tuaj hash do të jetë pikërisht madhësia se ju duhet që ajo të jetë, e drejtë? Kjo është pika e tërë e listave të lidhura. Ftohtë. 

Pra, të gjithë OK atje? Dakord. Ah. Çfarë ka ndodhur vetëm? Really tani. Guess dikush është vrarë mua. 

OK, ne jemi duke shkuar për të shkuar në Ekzekutimet, të cilat janë pak të çmendur. I pëlqen tavolina hash. Unë mendoj se ata janë me të vërtetë cool. Ekzekutimet janë cool, too. 

Pra, ka njeri të mbani mend se çfarë një provoni është? Ju duhet të përfundoni ai shkurtimisht në leksion? A ju kujtohet lloj si funksionon? AUDIENCA: Unë jam vetëm nodding që nuk shkojnë mbi të. Gjuha 1: Ne do të shkojnë mbi të. OK, ne jemi me të vërtetë do të shkojnë mbi tani është ajo që ne jemi duke thënë. 

AUDIENCA: Kjo është një pemë rikthim. 

Gjuha 1: Po. Kjo është një pemë rikthim. Awesome. Pra, një gjë të re këtu është se ne janë duke kërkuar në karaktere të veçanta këtu, apo jo? 

Pra, para se me funksionin tonë të hash, ne ishin në kërkim në fjalë, si një e tërë, dhe tani ne jemi duke kërkuar më shumë në karaktere, e drejtë? Pra, ne kemi Maxwell mbi këtu dhe Mendel. Pra, në thelb një try-- një mënyrë për të menduar në lidhje me këtë është se çdo niveli këtu është një koleksion i letrave. Pra, kjo është nyja juaj rrënjë këtu, apo jo? Kjo ka të gjitha karakteret e alfabet për fillimin e çdo fjalë. 

Dhe atë që ju doni të bëni është të të themi, OK, ne kemi disa fjalë M. Ne jemi duke shkuar për të kërkuar Maxwell, kështu ne do të shkojmë për të M. Dhe M pikëve në një të tërë tjetri një grup ku çdo fjalë, për aq kohë sa ekziston është një fjalë që ka një si letër të dytë, për aq kohë sa nuk ka një fjalë që ka B si letrën e dytë, ajo do të ketë një akrep shkuar në një grup tjetër. 

Ka ndoshta nuk është një fjalë që MP diçka, kështu që në pozicionin P në këtë array, ajo vetëm do të jetë NULL. Kjo do të thotë, OK, nuk ka asnjë fjalë që ka M pasuar nga një P, në rregull? Pra, nëse ne mendojmë për këtë, çdo një nga këto gjëra të vogla është në fakt një nga këto vargjeve të mëdha nga A nëpërmjet Z. Pra, çfarë mund të jetë një nga gjërat kjo është lloj i një pengesë e një provoni? 

AUDIENCA: Një shumë e kujtesës. 

Gjuha 1: Kjo është një ton të kujtesës, e drejtë? Secili prej këtyre blloqeve këtu përfaqëson 26 hapësira, 26 element array. Pra, përpiqet të marrë tepër të rënda hapësirë. 

Por ata janë shumë të shpejtë. Pra, tepër të shpejtë, por vërtetë hapësirë ​​joefikase. Lloji i duhet të kuptoj se cilat një që ju dëshironi. Këto janë me të vërtetë të ftohtë për pset tuaj, por ata do të marrë një shumë të kujtesës, kështu që ju të tregtisë off. Vërtet? 

AUDIENCA: A do të jetë e mundur për të ngritur një provoni dhe pastaj një herë ju keni të gjithë Të dhënat në atë që ju need-- Unë nuk e di nëse kjo do të kishte kuptim. Unë kam qenë duke u shpëtoj të gjithë Karaktere NULL, por pastaj ju nuk do të jetë në gjendje të indeksit them-- 

Gjuha 1: Ju ende nevojë për to. 

AUDIENCA: - të njëjtën mënyrë çdo herë. Gjuha 1: Po. Ju duhet personazhet NULL për të lejuar ju e dini se në qoftë se nuk është një fjalë atje. Ben nuk keni diçka që ju doni? OK. Në rregull, kështu që ne jemi duke shkuar për të shkuar pak më të në hollësi teknike prapa a përpiqen dhe të punojnë me një shembull. 

OK, kështu që kjo është e njëjta gjë. Ndërsa në një listë lidhur, kryesore ynë lloj of-- çfarë është fjala që unë dua? - si ndërtimin e bllokut ishte një nyje. Në një përpjekje, ne gjithashtu kemi një nyje, por kjo është e përcaktuar ndryshe. 

Pra, ne kemi disa bool se përfaqëson qoftë një fjalë të vërtetë ekziston në këtë vend, dhe pastaj ne kemi një rrjet të here-- ose më mirë, ky është një tregues për një Grup i 27 karaktere. Dhe kjo është për të, në këtë rast, ky 27-- Unë jam i sigurt se të gjithë ju jeni si, prisni, ka 26 shkronja në alfabetin. Pse nuk kemi 27? 

Pra, në varësi të Mënyrë që ju të zbatuar këtë, kjo është nga një pset që lejuar për apostrofat. Pra, kjo është arsyeja pse një shtesë. Ju gjithashtu do të keni në disa rastet Terminator null përfshihet si një prej karaktere të cilat është e lejuar që të jetë, dhe kjo është se si ata të kontrolloni për të shohim nëse ajo është fundi i fjalës. Nëse jeni të interesuar, shikoni Video Kevin mbi study.cs50, si dhe Wikipedia ka disa burime të mira atje. 

Por ne jemi duke shkuar për të shkuar nëpër thjesht lloj se si ju mund të punoni me një përpjekje në qoftë se ju jeni duke i dhënë një të tillë. Pra, ne kemi një të super të thjeshtë këtu ka fjalët "bat" dhe "zoom" në to. Dhe si ne shohim këtu, kjo hapësirë ​​pak këtu përfaqëson bool tonë se thotë, po, kjo është një fjalë. Dhe pastaj kjo ka tonë vargjeve të karaktereve, e drejtë? 

Pra, ne do të shkojnë nëpër gjetur "shkop" në këtë provoni. Pra, fillojë në krye, e drejtë? Dhe ne e dimë se b korrespondon me indeksi i dytë, elementi i dytë në këtë grup, sepse a dhe b. Pra, afërsisht një të dytë. 

Dhe ai thotë, OK, cool, ndiqni atë në array tjetër, sepse në qoftë se ne kujtojmë, nuk është se secili prej tyre në fakt përmban elementin. Secili prej këtyre vargjeve përmban një akrep, e drejtë? Kjo është një dallim i rëndësishëm për të bërë. 

Unë e di se kjo do të be-- mundohet të të vërtetë e vështirë për të marrë në kohën e parë, kështu që edhe në qoftë se kjo është herën e dytë apo të tretë dhe kjo është ende lloji i gjoja e vështirë, Unë premtoj, nëse ju shkoni shikojnë nesër shkurtër përsëri, ajo ndoshta do të bëjë shumë më tepër kuptim. Ajo merr një shumë për të tretet. Unë ende nganjëherë jam si, prisni, çfarë është një provoni? Si mund ta përdor këtë? 

Pra, ne kemi b në këtë rast, i cili është indeksi ynë i dytë. Nëse do të kishim, të themi, c ose d apo ndonjë letër tjetër, ne kemi nevojë për të hartë atë përsëri në indeksin e grup tonë se kjo korrespondon me. Pra, ne do të marrë si rchar dhe ne vetëm zbres off një për të hartë atë në 0-25. Të gjithë të mirë sa ne Harta e karaktereve tona? OK. 

Pra, ne do të shkojmë në një të dytë dhe ne shohim se, po, kjo nuk është NULL. Ne mund të lëvizin në këtë grup tjetër. Pra, ne do të shkojmë në këtë grup tjetër këtu. 

Dhe ne themi, OK, tani ne nevojë për të parë nëse një është këtu. Është një null apo e bën atë në të vërtetë të ecur përpara? Pra, a në fakt lëviz përpara në këtë rrjet. Dhe ne themi, OK, t është letra jonë e fundit. Pra, ne do të shkojmë në t në indeksin. Dhe pastaj ne të ecim përpara sepse nuk ka tjetër. Dhe kjo, thotë në thelb se, po, ajo thotë se ka një fjalë here-- se në qoftë se ju ndiqni këtë rruga, ju keni ardhur në një fjalë, të cilat ne e dimë është "bat". Po? 

AUDIENCA: A është standardi që të ketë atë si indeksin 0 dhe pastaj të ketë një lloj në 1 ose të kenë në fund? 

Gjuha 1: Nr Pra, nëse ne shikojmë prapa në tonë Deklarata këtu, kjo është një bool, kështu që është element vet në nyje tuaj. Pra, kjo nuk është pjesë e vektorit. Ftohtë. Pra, kur ne fund fjalën tonë dhe ne jemi në këtë grup, ajo që ne duam të bëjmë është të bëjë një kontroll për të është kjo një fjalë. Dhe në këtë rast, ai do të kthehej po. 

Pra, në këtë shënim, ne e dimë se "kopshtin zoologjik" - ne e dimë si njerëzit i se "kopshtit zoologjik" është një fjalë, e drejtë? Por po përpiqemi këtu do të thonë, jo, kjo nuk është. Dhe kjo do të thotë se, sepse ne nuk e kanë përcaktuar atë si një fjalë këtu. Edhe pse ne mund të kaloj deri në këtë grup, kjo provoni do të thotë se, nuk ka, kopsht zoologjik nuk është në fjalor tuaj sepse ne nuk kemi përcaktuar atë si të tillë. 

Pra, një mënyrë për të bërë that-- oh, sorry, kjo. Pra, në këtë rast, "kopshtin zoologjik", nuk është e një fjalë, por ajo është në përpjekjen tonë. Por në këtë, thonë se ne e duam atë futur fjalën "dush", çfarë ndodh është që ne ndjekim through-- b, a, t. Ne jemi në këtë grup, dhe ne do të shkojmë për të kërkuar për h. 

Në këtë rast, kur ne shikoni në treguesin në h, ajo është duke treguar NULL, OK? Pra, nëse kjo është në mënyrë eksplicite duke treguar një tjetër grup, ju supozojmë se të gjitha pointers në këtë grup janë treguar null. Pra, në këtë rast, h është vënë të null kështu që ne nuk mund të bëjmë asgjë, kështu që do të kthehen false, "dush" nuk është këtu. Pra, tani ne jemi në të vërtetë do të kalojnë nëpër si do ne fakt themi se "kopshtin zoologjik" është në përpjekjen tonë. Si nuk kemi të futur "kopshtin zoologjik", në përpjekjen tonë? Pra, në të njëjtën mënyrë që ne të filluar me listën tonë të lidhura, ne të fillojë në rrënjë. Kur në dyshim, të fillojë në rrënja e këtyre gjërave. 

Dhe ne do të themi, OK, z. z ekziston në këtë, dhe kjo e bën. Pra, ju jeni duke shkuar për në array tuaj të ardhshëm, OK? Dhe pastaj në një tjetër, themi, OK, nuk ekziston o? Ai e bën. Kjo përsëri. 

Dhe kështu në një tonë të ardhshëm, ne kemi thënë, OK, "kopshtin zoologjik", tashmë ekziston këtu. Të gjithë ne duhet të bëni është të vendosur këtë barabartë në të vërtetë, se është një fjalë atje. Nëse ju ka ndjekur gjithçka deri në atë pikë përpara, kjo është një fjalë, kështu që vetëm vendosur ajo barabartë tek tillë. Po? 

AUDIENCA: Pra, atëherë e bën atë thotë se "BA" është një fjalë edhe të brendshmen? 

Gjuha 1: Nr Pra, në këtë rast, "ba", ne do të merrni këtu, ne do të thonë se është një fjalë, dhe kjo do të vazhdojë të jetë nr. OK? Mmhmm? 

Audienca: Pra, një herë ju është një fjalë dhe ju thoni po, atëherë ajo do të përmbajë të shkojë në m? 

Gjuha 1: Pra, kjo ka të bëjë with-- jeni ngarkimit këtë. Ju thoni "kopshtit zoologjik" është një fjalë. Kur ju shkoni në check-- si, thonë se ju doni të thoni, ka "kopshtin zoologjik", ekziston në këtë fjalor? Ju jeni vetëm duke shkuar për të kërkuar për "kopshtin zoologjik" dhe pastaj kontrolloni për të parë nëse ajo është një fjalë. Ju kurrë nuk do të jeni për të lëvizur deri m, sepse kjo nuk është atë që ju po kërkoni. 

Pra, në qoftë se ne të vërtetë të kërkuar për të shtoni "dush" në këtë provoni, ne do të bëjmë të njëjtën gjë siç bëmë me "kopshtin zoologjik" përveç, ne do të shohim se kur ne përpiqen dhe të marrin të h, ajo nuk ekziston. Kështu që ju mund të mendoni për këtë si duke u përpjekur për të shtuar një nyje të re në një listë të lidhura, kështu që ne do të duhet të shtoni një tjetër një prej këtyre vargjeve, si kështu. Dhe pastaj ajo që ne nuk po kemi vetëm vendosur h element i kësaj grup treguar për këtë. 

Dhe pastaj çfarë do që ne duam të bëjmë këtu? Shto ajo barabartë me të vërtetë sepse kjo është një fjalë. Ftohtë. Unë e di. Ekzekutimet nuk janë më emocionuese. Trust mua, unë e di. 

Pra, një gjë për të realizuar me përpiqet, Unë i thashë, se ata janë shumë të efektshme. Pra, ne kemi parë ata të marrë një ton të hapësirës. Ata janë lloj i konfuze. Pra, pse do të kemi ndonjëherë të përdorni këto? Ne përdorim këto, sepse ata janë tepër efikase. 

Pra, nëse ju jeni ndonjëherë në kërkim up një fjalë, ju jeni vetëm kufizohet nga gjatësia e fjale. Pra, nëse ju jeni duke kërkuar për a fjalë që është e gjatësisë pesë, ju jeni vetëm ndonjëherë do të ketë të të bëjë më së shumti pesë krahasime, OK? Pra, kjo e bën atë në thelb një konstante. Ashtu si futje dhe lookup janë në thelb kohë konstante. 

Kështu që nëse ju mund të merrni ndonjëherë diçka në kohë të vazhdueshme, kjo është aq i mirë sa ajo merr. Ju nuk mund të merrni më të mirë se Koha konstante për këto gjëra. Kështu që është një nga pluses e mëdha të përpiqet. 

Por kjo është një shumë hapësirë. Kështu që ju lloj i duhet të vendosë çfarë është më e rëndësishme për ju. Dhe në kompjuterat e sotëm, hapësirë ​​që një provoni mund të zgjasë deri ndoshta nuk do të ndikojë në ju se shumë, por ndoshta ju jeni që kanë të bëjnë me diçka se ka shumë, shumë më tepër gjëra, dhe një provoni vetëm nuk është e arsyeshme. Po? 

AUDIENCA: Prisni, kështu që ju duhet 26 letra në çdo një të vetme? 

Gjuha 1: Mmhmm. Yeah, ju keni 26. Ju keni disa është shënues fjalë dhe më pas ju keni në çdo një 26 pointers. Dhe ata janë point-- 

AUDIENCA: Dhe çdo 26, ata çdo kanë 26? 

Gjuha 1: Po. Dhe kjo është arsyeja pse, si ju mund të shih, ajo zgjerohet shumë shpejt. Dakord. Pra, ne jemi duke shkuar për të marrë në pemë, të cilat Unë ndjehem si është më e lehtë dhe ndoshta do të të jetë një pushim bukur pak nga vende atje. Kështu që shpresojmë se shumica prej jush kanë parë një pemë më parë. Jo si goxha ato jashtë, të cilat unë nuk e di nëse dikush shkoi jashtë kohët e fundit. Unë shkova mollë picking këtë fundjavë, dhe oh my gosh, ajo ishte e bukur. Unë nuk e di se lë mund të shikoni se goxha. 

Pra, kjo është vetëm një pemë, e drejtë? Kjo është vetëm disa nyje, dhe kjo tregon për një bandë e nyje të tjera. Siç e shihni këtu, kjo është e lloj i një temë e përsëritur. Nyje treguar në nyjet është lloj i thelbi i shumë strukturave të të dhënave. Ajo thjesht varet se si ne ato kanë pikë të njëri tjetrit dhe se si ne kundërvënie përmes tyre dhe se si ne futur gjëra që përcakton karakteristikat e tyre të ndryshme. 

Pra, vetëm disa terminologjia, që unë e kam përdorur më parë. Pra rrënjë është çdo gjë që është në krye. kjo është ku ne gjithmonë të fillojë. Ju mund të mendoni për atë si kokë gjithashtu. Por për pemët, ne priren të i referohen asaj si rrënjë. 

Çdo gjë në here-- fund në shumë, shumë bottom-- janë konsideruar lë. Pra, ajo shkon së bashku me Gjithë gjë pemë, e drejtë? Gjethet janë në skajet e pemës tuaj. 

Dhe pastaj ne gjithashtu kemi një çift të Kushtet për të folur për nyjet në lidhje me njëri tjetrin. Pra, ne kemi prind, fëmijët, dhe vëllezërit e motrat. Pra, në këtë rast, 3 është prind prej 5, 6, dhe 7. Pra, prindi është çdo gjë që është një hap më lart çdo gjë që ju jeni duke iu referuar, në mënyrë të drejtë si një pemë familjare. Shpresojmë, kjo është e gjitha një pak të pak më intuitive se përpiqet. 

Vëllai dhe motra janë ndonjë që të ketë njëjti prind, e drejtë? Ata janë në të njëjtin nivel këtu. Dhe pastaj, siç isha duke thënë, fëmijët janë vetëm çdo gjë që është një hap poshtë nyje në fjalë, OK? Ftohtë. Pra, një pemë binare. Mund dikush të vë në rrezik një guess në një nga karakteristikat e pemës binar? 

AUDIENCA: Max dy kanate. 

Gjuha 1: E drejta. Pra, max e dy gjethe. Pra, në këtë para, kemi pasur këtë se kishte tre, por në një pemë binare, ju keni një maksimum prej dy fëmijë për prindin, e drejtë? Ka një tjetër karakteristikë interesante. Does anyone know se? Pemë binare. 

Pra, një pemë binare do të keni gjithçka në the-- kjo nuk është sorted-- por në një pemë renditura binar, çdo gjë në të djathtë është më e madhe se prind, dhe çdo gjë në të majtë është më pak se prindi. Dhe kjo ka qenë një quiz Pyetja më parë, në mënyrë të mirë për të dini. Pra, mënyra se si të përcaktojë këtë, përsëri, ne kemi një tjetër nyje. Kjo duket shumë e ngjashme me çfarë? Dyfish 

Audienca: Linked listat 

Gjuha 1: Një listë e dyfishtë e lidhur, e drejtë? Pra, në qoftë se ne të zëvendësojë këtë me mëparshëm dhe të ardhshëm, kjo do të jetë një listë e lidhur dyfish. Por në këtë rast, ne fakt kanë majtë dhe të djathtë dhe kjo është ajo. Përndryshe, kjo është saktësisht e njëjtë. Ne ende kemi elementin ju jeni në kërkim për të, dhe ju vetëm keni dy pointers do të çdo gjë që është e ardhshëm. Yeah, pemë kërko kështu binar. Nëse vërejmë, çdo gjë në këtu është than-- madh ose gjithçka menjëherë të drejtë këtu është më e madhe se, çdo gjë here është më pak se. 

Pra, në qoftë se ne ishim të kërkoni përmes, atë duhet të duken shumë afër kërkim binar këtu, apo jo? Përveç në vend që të kërkoni në gjysmën e array, ne jemi vetëm duke kërkuar në qoftë majtë anë apo anën e djathtë të pemës. Pra, ajo merr një pak më të thjeshtë, unë mendoj. 

Pra, nëse root juaj është NULL, padyshim kjo është vetëm false. Dhe në qoftë se ajo është atje, padyshim është e vërtetë. Në qoftë se kjo është më pak se, ne kërkim të majtë. Në qoftë se kjo është më e madhe se, ne kërko të drejtën. Është tamam si kërkim binar, vetëm një strukturë të ndryshme të dhënave që ne jemi duke përdorur. Në vend të një grup, kjo është vetëm një pemë binare. 

OK, oxhaqet. Dhe gjithashtu, duket sikur ne mund të ketë pak kohë. Nëse ne bëjmë, unë jam i lumtur për të shkuar mbi ndonjë nga këto përsëri. OK, kështu oxhaqet. A mbani mend dikush se çfarë stacks-- Çdo karakteristikat e një pirg? 

OK, kështu që shumica prej nesh, unë mendoj, hani në ngrënie halls-- sa më shumë që ne nuk mund të dëshironi të. Por natyrisht, ju mund të mendoni për një pirg fjalë për fjalë vetëm si një pirg e tabaka apo një pirg të gjërave. Dhe çfarë është e rëndësishme të kuptojnë është se ajo është something-- karakteristike që ne e quajmë atë by-- është LIFO. Does anyone know çfarë që qëndron për? Mmhmm? 

AUDIENCA: fundit në, e parë jashtë. 

Gjuha 1: E drejta, e fundit në, e parë jashtë. Pra, në qoftë se ne e dimë, në qoftë se ne jemi stacking gjëra up, gjëja më e lehtë për të rrëmbyer off-- dhe ndoshta e vetmja gjë që mund të rrëmbej off nëse rafte ynë është enough-- madh është se element lartë. Pra, çdo gjë që është vënë në last-- si ne shohim këtu, çdo gjë është shtyrë në shumicën recently-- është do të jetë i pari gjë që pop jashtë, OK? 

Pra, ajo që ne kemi këtu është një struct typedef. Kjo është me të vërtetë vetëm si a përplasje kurs në strukturën e të dhënave, kështu që nuk ka shumë hedhur në ju djema. Unë e di. Pra, edhe një struct. Yay për strukturat. 

Dhe në këtë rast, është një akrep në një grup që ka disa kapacitete. Pra, kjo paraqet pirg tonë këtu, si grup tone aktuale që e mban elementet tona. Dhe atëherë këtu kemi disa madhësi. 

Dhe zakonisht, ju doni të mbani gjurmët e sa e madhe rafte juaj sepse ajo që do të lejojë që ju të bëni është nëse ju e dini madhësinë, kjo ju mundëson për të thënë, OK, unë jam në kapacitet? Mund të shtoj asgjë më shumë? Dhe gjithashtu ju tregon ku në krye të rafte tuaj është kështu që ju e dini se çfarë ju në fakt mund të marrë off. Dhe kjo është në të vërtetë do të të jetë pak më i qartë këtu. 

Pra, për një shtytje, një gjë, në qoftë se ju qenë ndonjëherë për të zbatuar shtytje, pasi unë isha vetëm duke thënë, tuaj rafte ka një madhësi të kufizuar, e drejtë? Array jonë kishte disa kapacitete. Kjo është një koleksion. Kjo është një madhësi të caktuar, kështu që ne kemi nevojë për të të sigurt se ne nuk jemi vënë më shumë në grup tonë se sa ne në fakt kanë hapësirë ​​për të. 

Pra, kur ju jeni duke krijuar një shtytje funksion, gjëja e parë që bëni është të themi, OK, nuk kam hapësirë ​​në rafte e mia? Sepse në qoftë se unë nuk e bëj, sorry, Unë nuk mund të ruajë elementin tuaj. Në qoftë se unë bëj, atëherë ju doni të ruajtur ai në krye të rafte, e drejtë? 

Dhe kjo është arsyeja pse ne kemi për të mbajtur gjurmët e madhësisë tonë. Nëse ne nuk i mbajnë gjurmët e madhësisë tonë, ne nuk e dimë se ku për të vënë atë. Ne nuk e dimë se sa shumë gjëra janë në grup tonë tashmë. Ashtu si padyshim ka mënyra se ndoshta ju mund të bëni atë. Ju mund të nisja gjithçka për të null dhe pastaj kontrolloni për NULL fundit, por një gjë shumë më e lehtë është vetëm për të thënë, OK, mbajnë gjurmët e madhësisë. Ashtu si unë e di unë kam katër elemente në grup tim, kështu që gjëja e ardhshme që ne kemi vënë në, ne jemi shkuar për të ruajtur në indeksin 4. Dhe pastaj, sigurisht, kjo do të thotë se ju keni shtyrë me sukses diçka mbi rafte tuaj, ju duan për të rritur madhësinë në mënyrë që ju e dini se ku jeni kaq që ju mund të shtyjë më shumë gjëra në. 

Pra, në qoftë se ne jemi duke u përpjekur për të pop diçka off rafte, çfarë mund të jetë gjëja e parë që ne duam të kontrolloni për të? Ju jeni duke u përpjekur për të marrë diçka off rafte tuaj. Jeni te sigurte ka diçka në rafte tuaj? Jo. Pra, çfarë mund të duam të shikoni? 

Audienca: [padëgjueshme]. Gjuha 1: Kontrollo për madhësinë? Size. Pra, ne duam të kontrolloni për të parë nëse Madhësia e jonë është më e madhe se 0, OK? Dhe në qoftë se ajo është, atëherë ne duam që të ulet Madhësia tonë me 0 dhe të kthehet kjo. Pse? 

Në rastin e parë ne ishim shtyrë, ne e shtyu atë mbi përmasat dhe madhësia pastaj përditësuar. Në këtë rast, ne jemi decrementing madhësinë dhe pastaj të marrë atë jashtë, plucking atë nga array tonë. Pse mund të bëjmë atë? Pra, nëse unë kam një gjë në rafte e mia, çfarë do të jetë madhësia e mia në atë moment? 1. 

Dhe ku është element 1 ruajtur? Në çfarë Indeksi? AUDIENCA: 0. Gjuha 1: 0. Pra, në këtë rast, ne gjithmonë duhet të bëni sure-- në vend të kthimit Madhësia minus 1, sepse ne e di se element ynë është do të ruhet në 1 më pak pavarësisht nga madhësia ynë është, kjo vetëm kujdeset për atë. Kjo është një mënyrë pak më elegante. Dhe ne vetëm pakësim tonë Madhësia dhe pastaj të kthehen madhësinë. Mmhmm? 

AUDIENCA: Unë mendoj vetëm në përgjithësi, pse do të këtë strukturë e të dhënave të jenë të dobishme? 

Gjuha 1: Kjo varet nga konteksti tuaj. Pra, për disa i teorisë, në qoftë se ju jeni duke punuar with-- OK, më lejoni të shohim nëse ka një dobishme që është e dobishme për më shumë se jashtë e CS. Me oxhaqet, në çdo kohë që ju nevojitet për të mbajtur gjurmët e diçkaje që është shtuar kohët e fundit është kur ju jeni do të dëshironi të përdorni një pirg. 

Dhe unë nuk mund të mendoj për një të mire shembull që tani. Por sa herë më të fundit gjë është më e rëndësishme për ju, kjo është kur një pirg do të jenë të dobishme. Unë jam duke u përpjekur për të menduar nëse ka një të mirë për këtë. Nëse unë mendoj për një shembull të mirë në botën tjetër 20 minuta, unë patjetër do të ju them. 

Por në përgjithësi, nëse ka ndonjë gjë, si kam thënë më, ku më të fundit është më e rëndësishme, që është ku një pirg vjen në lojë. Ndërsa radhët e gjata janë lloj i kundërt. Dhe të gjithë qentë e pak. A nuk është kjo e madhe, e drejtë? Ndjehem si unë duhet vetëm kanë një video lepur të drejtë në mes të Seksioni për ju djema sepse kjo është një seksion intensive. 

Pra, a radhë. Në thelb një radhë është si një linjë. Ju djema Unë jam i sigurt përdorimi i kësaj të përditshme, ashtu si në sallat tona ngrënie. Pra, ne duhet të shkojnë në dhe për të marrë tabaka tona, unë jam që ju duhet të presin në linjë të shpullë ose të merrni ushqimin tuaj. 

Pra, diferenca këtu është se kjo është FIFO. Pra, nëse LIFO i fundit në, e parë out, FIFO është i pari në, jashtë e parë. Pra, kjo është ajo ku çdo gjë që ju vendosni më së pari është e juaj më e rëndësishme. Pra, nëse ju jeni duke pritur në një line-- mund t'ju imagjinoni nëse ju shkoi për të shkoni merrni iPhone i ri dhe kjo ishte një pirg ku personi i fundit në linjë mori atë për herë të parë, njerëzit do të vrasin njëri-tjetrin. 

Pra FIFO, ne jemi të gjithë shumë të njohur me të në botën e vërtetë këtu, dhe gjithçka ka të bëjë me të vërtetë lloj rikrijimin këtë linjë të tërë dhe queuing strukturën. Pra, ndërsa me rafte, ne kemi shtytje dhe pop. Me radhë, ne kemi enqueue dhe dequeue. Pra, do të thotë në thelb enqueue vënë atë mbi shpinë, dhe mjetet dequeue marrë off nga e para. Pra, struktura e të dhënave jonë është një pak më e komplikuar. Ne kemi një gjë të dytë për të mbajtur gjurmët e. 

Pra, pa kokë, kjo është pikërisht një pirg, e drejtë? Kjo është e njëjta strukturë si një pirg. E vetmja gjë që ndryshon tani është që ne kanë këtë kokë, të cilën çfarë mendoni do të mbajnë gjurmët e? 

AUDIENCA: I pari. 

Gjuha 1: E drejta, Gjëja e parë që ne kemi vënë në. Kreu i radhë tonë. Kushdo që është i pari në linjë. Në rregull, kështu që nëse bëjmë enqueue. Përsëri, me ndonjë nga këto struktura e të dhënave, pasi ne jemi që kanë të bëjnë me një grup, ne kemi nevojë për të kontrolluar nëse kemi hapësirë. 

Kjo është lloj i si me thënë ju djema, nëse ju hapni një skedar, ju duhet të kontrolloni për të null. Me ndonjë prej këtyre kollonat dhe radhët e gjata, ju duhet për të parë nëse ka hapësirë ​​për shkak se ne jemi që kanë të bëjnë me një grup madhësi të caktuar, si ne e shohim here-- 0, 1 të gjitha deri në 5. Pra, çfarë të bëjmë në këtë rast është të kontrolloni për të parë nëse ne ende kemi hapësirë. Është madhësia tonë më pak se kapaciteti? 

Nëse është kështu, ne kemi nevojë për të ruajtur atë në bisht dhe ne update madhësinë tonë. Pra, çfarë mund bisht të jetë në këtë rast? Kjo nuk është shkruar shprehimisht. Si do të ruajtur atë? Çfarë do të jetë bisht? 

Pra, le të ecin nëpër këtë shembull. Pra, kjo është një grup i madhësisë 6, e drejtë? Dhe ne kemi të drejtë tani, madhësia tonë është 5. Dhe kur ne kemi vënë atë në, ajo do për të shkuar në indeksin e pestë, e drejtë? Pra, dyqan në bisht. 

Një tjetër mënyrë për të shkruar bisht vetëm do të të jetë array tonë në indeksin e madhësisë, e drejtë? Kjo është madhësia 5. Tjetër gjë do të shkojë në 5. Ftohtë? OK. Ajo merr pak më e komplikuar kur ne fillojmë messing me kokë. Po? 

AUDIENCA: A do të thotë kjo se ne do të kishte deklaruar një grup që ishte pesë elemente të gjatë dhe të atëherë ne jemi duke shtuar mbi atë? 

Gjuha 1: Nr Pra, në këtë rast, ky është një pirg. Kjo do të shpallet si një grup të madhësisë 6. Dhe në këtë rast, ne të ketë vetëm një të majtë hapësirë. 

OK, kështu që një gjë është në këtë rast, në qoftë se kreu ynë është në 0, atëherë ne vetëm mund të shtoni atë në madhësi. Por ajo merr pak e komplikuar sepse në të vërtetë, ata nuk kanë një rrëshqitje për këtë, kështu që unë jam duke shkuar për të nxjerrë një, sepse ajo nuk është fare e thjeshtë një herë ju filloni duke u shpëtoj prej gjërave. Pra, ndërsa me një pirg ju vetëm ndonjëherë keni për t'u shqetësuar në lidhje me atë që madhësia është kur ju jeni duke shtuar diçka në, me një radhë ju gjithashtu duhet të bëni i sigurt se kreu i juaj është në rregull, sepse një gjë e ftohtë në lidhje me rradhë është se në qoftë se ju nuk jeni në kapacitet, ju mund të bëjë në fakt atë të përfundojë rreth. 

OK, kështu që një thing-- oh, kjo është shkumës tmerrshme. Një gjë për t'u marrë parasysh është rasti. Ne do të bëjmë vetëm pesë. OK, kështu që ne jemi duke shkuar për thonë se kreu është këtu. Kjo eshte 0, 1, 2, 3, 4. 

Kreu është atje, dhe ju lutem keni gjëra në to. Dhe ne duam që të shtoni diçka në, e drejtë? Pra, gjë që ne kemi nevojë për të e di se koka është gjithmonë do të lëvizin në këtë mënyrë dhe pastaj loop kthehet rreth, OK? 

Pra, kjo radhë ka hapësirë, të drejtë? Ajo ka hapësirë ​​në fillim, lloj të kundërtën e kësaj. Pra, ajo që ne duhet të bëjmë është që ne nevojë për të llogaritur bishtin. Nëse ju e dini se juaj Kreu nuk ka lëvizur, bisht është vetëm koleksion juaj në indeksi i madhësisë. 

Por në realitet, në qoftë se ju jeni duke përdorur një radhë, kreu i juaj është ndoshta duke u përditësuar. Pra, çfarë ju duhet të bëni është të në fakt llogaritur bishtin. Pra, ajo që ne bëjmë është kjo formulë këtu, të cilën unë jam duke shkuar për të ju lejojnë djema mendoni për, dhe atëherë ne do të flasim për këtë. Pra, kjo është kapaciteti. 

Pra, kjo do të vërtetë ju jap një mënyrë për të bërë atë. Sepse në këtë rast, çfarë? Kreu ynë është në 1, madhësia tonë është 4. Nëse ne mod se me 5, ne kemi marrë 0, i cili është ku ne duhet të input atë. 

Kështu, pra, në rastin e ardhshëm, në qoftë se ne do të bëjmë këtë, themi, OK, le të dequeue diçka. Ne dequeue këtë. Ne kemi marrë këtë element, e drejtë? 

Dhe tani koka jonë është treguar këtu, dhe ne duam që të shtoni në një tjetër gjë. Kjo është në thelb e pasme të linjës sonë, e drejtë? Rradhë të mund të përfundojë rreth vargut. Kjo është një nga dallimet kryesore. Oxhaqet, ju nuk mund ta bëjë këtë. 

Me rradhë, ju mund të sepse gjithçka që ka rëndësi është se ju e dini se çfarë u shtua kohët e fundit. Që çdo gjë është duke shkuar për të shtuar në këtë drejtim nga e majta, në këtë rast, dhe pastaj të përfundojë rreth, ju mund të vazhdojnë të vënë në elemente të reja në pjesën e përparme të vektorit sepse kjo nuk është e vërtetë front i array më. Ju mund të mendoni për fillimin e array si kur koka juaj të vërtetë është. 

Pra, kjo formulë është se si ju llogaritni bisht tuaj. A kjo ka kuptim? OK. OK, dequeue, dhe pastaj ju djema keni 10 minuta të më pyesni ndonjë pyetje qartësimin ju doni, sepse unë e di se është i çmendur. 

Të gjithë të drejtë, kështu që në të njëjtën way-- Unë nuk e di nëse ju djema vënë re, por CS është mbi të gjitha modelet. Gjërat janë pretty much njëjtë, vetëm me tweaks të vogla. Kështu që e njëjta gjë këtu. Ne duhet të kontrolloni për të parë nëse ne fakt kanë diçka në radhë tonë, e drejtë? Thuaj, OK, është madhësia ynë më i madh se 0? Ftohtë. 

Nëse ne bëjmë, atëherë ne të lëvizë kokën tonë, e cila është ajo që unë vetëm demonstruar këtu. Ne update kokën tonë të jetë një më shumë. Dhe pastaj ne pakësim tonë Madhësia dhe kthimin elementin. 

Nuk është shumë më konkrete Kodi për study.cs50.net, dhe I highly recommend shkuar nëpërmjet saj në qoftë se ju keni kohë, edhe nëse kjo është vetëm një pseudo-kod. Dhe në qoftë se ju djema doni të flisni me se me mua një mbi një, ju lutem më lejoni e di. Unë do të jenë të lumtur për të. Strukturat e të dhënave, nëse ju merrni CS 124, ju do të e di se strukturat e të dhënave të merrni shumë fun dhe ky është vetëm fillimi. 

Kështu që unë e di se është e vështirë. Kjo është OK. Ne luftojnë. Unë ende nuk. Pra, mos u shqetësoni shumë për këtë. 

Por kjo është në thelb tuaj së përplasje kurs në strukturat e të dhënave. Unë e di se është një shumë. A ka ndonjë gjë që ne do të donte për të shkuar përsëri? Çdo gjë që ne duam të flasim me? Po? 

AUDIENCA: Për këtë shembull, në mënyrë bisht i ri është në 0 mbi atë? Gjuha 1: Po. AUDIENCA: OK. Pra, pastaj duke shkuar nëpër, ju do të keni 1 plus 4 or-- 

Gjuha 1: Pra, ju jeni duke thënë, kur ne duam të shkojnë bëni këtë përsëri? AUDIENCA: Po. Pra, nëse ju jeni duke parafytyruar out-- ku janë ju llogaritur bishtin nga në atë? 

Gjuha 1: Pra bisht ishte in-- I ndryshuar këtë. Pra, në këtë shembull këtu, kjo ishte array ne jemi duke kërkuar në, OK? Pra, ne kemi gjëra në 1, 2, 3, dhe 4. Pra, ne kemi kokën tonë është e barabartë me 1 në kjo pikë, dhe madhësia tonë është e barabartë me 4 në këtë pikë, e drejtë? 

Ju të gjithë janë dakord se është e rastit? Pra, ne bëjmë kreu plus size, e cila na jep 5, dhe pastaj ne mod me 5. Ne kemi marrë 0, e cila na tregon se 0 është ku është bisht tonë, ku ne kemi hapësirë. 

AUDIENCA: Çfarë është një kapak? 

Gjuha 1: Kapaciteti. Më vjen keq. Pra, kjo është madhësia e array tuaj. Po? 

Audienca: [padëgjueshme] më parë kthehemi elementin? 

Gjuha 1: Pra ne shkojmë kreu ose kthimin e momentit? Pra, nëse ne shkojmë një, pakësim madhësinë? Të mbajë në. Unë patjetër harruar tjetër. Never mind. Nuk është një tjetër formulë. Yeah, ju do të duan të kthehen kokë dhe pastaj të lëvizin atë përsëri. 

AUDIENCA: OK, sepse në këtë pika, kreu ishte në 0, dhe pastaj ju doni të ktheheni Indeksi 0 dhe pastaj të bëjë kokë 1? 

Gjuha 1: E drejta. Unë mendoj se ka një tjetër lloj formula e si kjo. Unë nuk e kanë atë në krye kokën time si Unë nuk dua të ju jap një të gabuar. Por unë mendoj se është krejtësisht e vlefshme për të themi, OK, ruajtur këtë element-- çfarëdo element kreu i is-- pakësim tuaj Madhësia, lëvizin kokën tuaj mbi, dhe kthimi çfarëdo që është element. Kjo është krejtësisht e vlefshme. OK. Unë ndjehem si kjo nuk është e si most-- ju nuk jeni do të largohet nga këtu si, po, unë e di përpiqet. I mori të gjitha. Kjo është OK. I premtoj. Por strukturat e të dhënave janë diçka që ajo merr shumë kohë për të marrë të përdoret për të. Ndoshta një nga më të vështira gjëra, unë mendoj se, në këtë kurs. 

Pra, kjo definitivisht merr përsëritje dhe kërkim at-- I me të vërtetë nuk e di se listat e lidhura deri sa unë e bëri shumë më shumë me ta, në të njëjtën mënyrë që unë nuk e kam me të vërtetë kuptojnë pointers deri sa unë kam pasur për të mësuar atë për dy vjet dhe të bëjë psets e mia me të. Ajo merr një shumë të përsëritjes dhe kohë. Dhe në fund, kjo lloj do të klikoni. 

Por, në ndërkohë, në qoftë se ju keni lloj e të kuptuarit të nivelit të lartë të asaj këto bëjnë, pro tyre dhe cons-- cila është ajo ne me të vërtetë kanë tendencë për të theksuar, sidomos në kurs intro. Si, pse do të përdorim a provoni mbi një grup? Ashtu si, çfarë janë pozitive dhe negative të secilës prej atyre? 

Dhe të kuptuarit e tregtisë të humbura midis secili prej ketyre strukturave është ajo që është shumë më e rëndësishme tani. Nuk mund të jetë një i çmendur pyetje ose dy që është do të ju pyes për të zbatuar shtytje ose zbatuar pop apo enqueue dhe dequeue. Por, për pjesën më të madhe, atë që ka Kuptimi më i lartë niveli dhe më shumë e një rrokje intuitive është më e rëndësishme se në të vërtetë qenë në gjendje për ta zbatuar atë. 

Ajo do të jetë me të vërtetë awesome nëse të gjithë ju mund të shkojë jashtë dhe të shkojë të zbatojë një përpjekje, por ne e kuptojmë se kjo nuk është domosdoshmërisht gjëja më e arsyeshme të drejtë tani. Por ju mund të në pset tuaj, në qoftë se ju dëshironi për të, dhe pastaj ju do të merrni praktikë, dhe pastaj ndoshta ju do të të vërtetë e kuptojnë atë. Po? 

AUDIENCA: OK, kështu që ato janë ne do të thotë për të përdorur në pset? A kam nevojë për të përdorur një prej tyre? Gjuha 1: Po. Pra, ju keni zgjedhjen tuaj. I guess në këtë rast, ne mund të flasim për pset pak sepse unë u zhvillua nëpër këto. Pra, në pset tuaj, ju keni tuaj Zgjedhja e përpjekjeve apo tabelave hash. Disa njerëz do të përpiqet dhe të përdorin filtra Bloom, por ata që teknikisht nuk janë të sakta. Për shkak të natyrës së tyre probabilistic, ata japin false positives ndonjëherë. Ata janë vështrim të ftohtë në, edhe pse. Highly recomend kërkim të tyre të paktën. Por ju keni zgjedhjen tuaj në mes të një tavolinë hash dhe një provoni. Dhe kjo do të jetë aty ku ju ngarkesës në fjalorin tuaj. 

Dhe ju do të duhet të zgjidhni funksion tuaj hash, ju do të duhet të zgjidhni se sa kova që ju keni, dhe kjo do të ndryshojnë. Ashtu si në qoftë se ju keni më shumë kova, ndoshta ai do të kandidojë më të shpejtë. Por ndoshta ju jeni të humbur një shumë hapësirë ​​në këtë mënyrë, edhe pse. Ju duhet të kuptoj atë. Mmhmm? 

AUDIENCA: Ju thatë më parë se ne mund të përdorni funksione të tjera hash, se ne nuk duhet të të krijojë një funksion hash? 

Gjuha 1: Po, e drejtë. Kështu që fjalë për fjalë për funksionin tuaj të hash, si google "Funksioni hash" dhe të kërkoni për disa të ftohtë. Ju nuk pritet të ndërtuar funksionet e veta tuaj hash. Njerëzit shpenzojnë tyre Tezat mbi këto gjëra. 

Pra, mos u bëni merak për ndërtimin tuaj. Gjeni një online për të filluar me. Disa prej tyre ju duhet të manipuluar pak për të bërë lloje të siguruar kthim ndeshje deri dhe gjësend, kështu që në fillim, Unë do të rekomandojë duke përdorur diçka të vërtetë e lehtë që ndoshta vetëm hashes në letrën e parë. Dhe pastaj një herë ju keni atë pune, përfshirë një funksion frigorifer hash. Mmhmm? 

AUDIENCA: A do të përpiqet të jetë ose efikas, por vetëm e vështirë për të, like-- 

Gjuha 1: Pra a try, unë mendoj, është intuitivisht e vështirë për të zbatuar por është shumë e shpejtë. Megjithatë, merr më shumë hapësirë. Përsëri, ju mund të zgjedh dy nga ata në mënyra të ndryshme dhe ka mënyra to-- AUDIENCA: Sa jemi të vlerësohet për këtë? A do të matter-- 

Gjuha 1: Pra, ju jeni vlerësohen mënyrë normale. Ju do të jeni të vlerësohet në dizajn. Cilado mënyrë që ju bëni, ju dëshironi të sigurohuni që ajo është aq elegante sa ajo mund të jetë dhe aq efikas sa ajo mund të jetë. Por në qoftë se ju zgjidhni një provoni ose të hash tavolinë, për aq kohë sa ajo punon, ne jemi të kënaqur me atë. Dhe në qoftë se ju përdorni diçka që hashes në letrën e parë, kjo është në rregull, si ndoshta si design-i mençur. Ne gjithashtu jemi duke arritur pikë në këtë semester-- Unë nuk e di nëse ju djema noticed-- në qoftë se ju jeni notat pset bjerë pak për shkak të dizajnit dhe gjësend, kjo është e përkryer gjobë. Është duke arritur në një pikë ku tuaj Programet janë duke marrë më të komplikuar. Ka shumë vende ju mund të përmirësuar. 

Pra, kjo është krejtësisht normale. Kjo nuk është se ju jeni bërë keq në pset tuaj. Është thjesht ne jemi duke u vështirë për ju tani. Pra, të gjithë është ndjenjë atë. Unë vetëm të vlerësohet gjitha psets tuaja. Unë e di se të gjithë është ndjenjë atë. 

Pra, nuk do të jenë të shqetësuar në lidhje me atë. Dhe në qoftë se ju keni ndonjë pyetje në lidhje me psets mëparshme ose mënyra që ju mund të përmirësojë, Unë të përpiqet dhe të komentojë specifike vende, por nganjëherë është vonë dhe unë lodhem. A ka ndonjë gjëra të tjera për strukturat e të dhënave? Unë jam i sigurt që ju djema të vërtetë nuk duan të flasin rreth tyre më, por nëse ka, unë jam i lumtur për shko mbi to, si dhe çdo gjë nga leksioni kjo e kaluar javë ose javën e kaluar. 

Unë e di se javën e kaluar ishte e gjitha shqyrtim, kështu ne mund të kemi anashkaluar një shqyrtim nga leksioni. Çdo pyetje të tjera unë mund të përgjigjem? OK, të gjithë të drejtë. Well, ju djema merrni nga 15 minuta në fillim. 

Unë shpresoj se kjo ishte gjysmë-dobishme të paktën, dhe unë do t'ju shoh djema javën e ardhshme, ose zyra orë të enjten. A ka kërkesa për snacks për javën e ardhshme, kjo është gjë? Sepse kam harruar karamele sot. Dhe unë solli karamele fundit javë, por ajo ishte Dita Columbus, kështu që nuk ishin si gjashtë njerëz që kishte katër çanta të karamele për veten e tyre. Unë mund të sjellë Starbursts përsëri në qoftë se ju pëlqen. Starbursts? OK, tingëllon mirë. Kanë një ditë e madhe, djema.