Kryetari 1: Të gjithë të drejtë, kështu që ne jemi prapa. Mirë se vini në CS50. Ky është fundi i javës së shtatë. Pra, kujtojnë se herën e fundit, kemi filluar në kërkim të pak më të sofistikuar Strukturat e të dhënave. Që nga viti deri më tani, të gjithë kemi pasur me të vërtetë në dispozicionin tonë ishte kjo, një koleksion. 

Por, para se të hidhni array si jo të gjitha që interesante, e cila në të vërtetë ajo në fakt është, cilat janë disa nga pluses e këtyre të dhënave të thjeshta Struktura e deritanishme? Çfarë është ajo e mirë në? Deri më tani si kemi parë? Çfarë keni? Asgjë. 

STUDENT: [padëgjueshme]. 

Kryetari 1: Çfarë është ajo? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Madhësia fikse. OK, kështu që pse është madhësia fiks mirë edhe pse? 

STUDENT: [padëgjueshme]. 

Kryetari 1: OK, prandaj është efikas në Ndjenja që ju mund të ndajë një Shuma fikse e hapësirës, ​​të cilat shpresojmë se është pikërisht aq sa hapësirë ​​si ju dëshironi. Kështu që mund të jetë absolutisht një plus. 

Çfarë është një anë tjetër nga një grup? Po? 

STUDENT: [padëgjueshme]. 

Kryetari 1: All - keq? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Të gjitha kutitë në kujtesën ose pranë njëri-tjetrit. Dhe kjo është e dobishme - pse? Kjo është mjaft e vërtetë. Por si mund ta shfrytëzojnë këtë të vërtetë? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Pikërisht, ne mund të ruaj gjurmët e ku çdo gjë është vetëm duke e ditur një adresë, pra adresën e bajt i parë i asaj copë e kujtesës. Ose në rastin e vargut, adresa e parë char në atë varg. Dhe nga atje, ne mund të gjeni fundi i vargut. Ne mund të gjejmë elementin e dytë, Elementi i tretë, dhe kështu me radhë. 

Dhe kështu mënyrë e sofistikuar për të përshkruar se Tipar është se vargjeve të na japë qasje të rastit. Vetëm duke përdorur kllapa katrore simbol dhe një numër, ju mund të kërcejnë për të një element specifik në rrjet në kohë të vazhdueshme, Big O nga një, në mënyrë që të flasin. 

Por ka pasur disa dobësi. Çfarë nuk të bëjë një koleksion shumë e lehtë? Çfarë ajo nuk është e mirë në? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Çfarë është ajo? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Zgjerimi në madhësi. Pra, dobësi e vargut janë pikërisht e kundërta e asaj që upsides janë. Kështu një nga dobësi eshte se kjo është një madhësi të caktuar. Pra, ju nuk mund të vërtetë rritet ajo. Ju mund të rialokuar një copë të madhe të kujtesës, dhe pastaj të lëvizë elementet e vjetra në rrjet të ri. Dhe pastaj pa array vjetër, për shembull, duke përdorur malloc ose një të ngjashme funksion të quajtur realloc, e cila rialokim kujtesës. 

Realloc, si një mënjanë, përpiqet të japë ty kujtesës që më tej të array që ju tashmë keni. Por kjo mund të lëvizin gjërat rreth krejt. Por në të shkurtër, kjo është e shtrenjtë, e drejtë? Sepse në qoftë se ju keni një copë e kujtesës së këtë madhësi, por ju me të vërtetë duan një i kësaj madhësie, dhe ju doni për të ruajtur elementet origjinale, ju keni afërsisht një proces linear kopjimi koha që ka nevojë të ndodhë nga array vjetra në të reja. Dhe realiteti është kërkuar që veprojnë Sistemi përsëri dhe përsëri dhe përsëri për chunks të mëdha të kujtesës mund të fillojnë të ju kushtojë disa kohë si. Pra, kjo është si një bekim dhe një mallkim në fsheh, faktin se këto vargjeve janë të madhësisë fikse. Por në qoftë se ne kemi prezantuar diçka në vend si kjo, të cilën ne e quajti një linked lista, ne kemi marrë një upsides pak dhe disa dobësi si edhe këtu. 

Pra, një listë e lidhur është thjesht një të dhënave Struktura e përbërë nga structs C në këtë rasti, ku një struct, risjell, është vetëm një enë për një ose më shumë specifik Llojet e variablave. Në këtë rast, çfarë bëni llojet e të dhënave duket te jenë brendësi të struct që hera e fundit që kemi quajtur një nyje? Secila prej këtyre rectangles është një nyje. Dhe secili prej rectangles vogla në brendësi të saj është një lloj i të dhënave. Çfarë lloje e themi ata ishin të hënën? Po? 

STUDENT: [padëgjueshme]. 

FOLËSI 1: Një variabël dhe një akrep, ose më konkretisht, një int, për n, dhe një akrep në pjesën e poshtme. Dy prej atyre të ndodhë që të jetë 32 bit, at paktën në një kompjuter si kjo CS50 Appliance, dhe kështu ata janë tërhequr në mënyrë të barabartë në madhësi. 

Pra, çfarë jeni duke përdorur treguesin edhe pse me sa duket për? Pse shtoni këtë shigjetën tani kur vargjeve ishin aq e bukur dhe të pastër dhe të thjeshtë? Çfarë është bërë për treguesin na në secilin prej këtyre nyjeve? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Pikërisht. Është thënë se ku një tjetër është. Kështu që unë lloj përdorur analogjinë e duke përdorur një fije të lloj thread këto nyje së bashku. Dhe kjo është pikërisht ajo që ne jemi duke bërë me pointers sepse secili prej këtyre chunks e kujtesës mund ose nuk mund të jetë puqur, të kthehet prapa për të mbështetur brenda RAM, sepse çdo herë që telefononi malloc thënë, më jepni të mjaftueshme bytes për një nyje të re, ajo mund të jetë këtu ose ajo mund të jetë këtu. Ajo mund të jetë këtu. Ajo mund të jetë këtu. Ju thjesht nuk e di. 

Por duke përdorur pointers në adresat e ato nyjet, ju mund të thur ato bashku në një mënyrë që duket me sy si një listë edhe në qoftë se këto gjëra janë të gjithë të shtrirë në të gjithë ose një tuaj dy tuaj ose katër gigabajt të RAM tuaj brenda e kompjuterit tuaj. 

Pra downside, pastaj, një listë e lidhur është ajo? Çfarë është një çmim që ne jemi me sa duket duke paguar? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Më shumë hapësirë, e drejtë? Ne kemi, në këtë rast, dyfishuar shumën e hapësirës, ​​sepse ne kemi shkuar nga 32 bit për çdo nyje, për secilin int, kështu që tani e 64 bit, sepse ne kemi për të të mbajë rreth një pointer si. Ju merrni më shumë efikasitet nëse struct juaj është më e madhe se sa kjo gjë e thjeshtë. Nëse jeni të vërtetë kanë një student brenda i cili eshte nje çift i gradët Emri dhe shtëpi, ndoshta një numër ID, ndoshta disa fusha të tjera krejt. 

Pra, nëse ju keni një struct mjaft i madh, atëherë ndoshta kostoja e treguesin është nuk është e tillë një punë e madhe. Kjo është pak e një qoshe në rast se ne jemi ruajtjen tillë primitive e thjeshtë brendësi të lista lidhura. Por pikë është e njëjtë. Ju jeni patjetër të shpenzojnë më shumë kujtesës, por ju jeni duke marrë fleksibilitet. Sepse tani në qoftë se unë dua të shtoj një element në fillim të kësaj liste, Unë duhet të akordojë një nyje të re. Dhe unë duhet të vetëm update ata Shigjetat disi nga vetëm duke lëvizur disa pointers rreth. 

Nëse unë dua të futur diçka në mesi i listës, unë nuk kam për të shtyjë të gjithëve mënjanë si ne e bëmë në kaluarën javësh me vullnetarët tanë të cilët përfaqësuar një rrjet. Unë vetëm mund të ndajë një nyje të re dhe atëherë vetëm pikë shigjetat në drejtimet e ndryshme, sepse ajo nuk duhet të mbetet në aktuale kujtim një linjë të vërtetë si unë kam tërhequr kjo këtu në ekran. 

Dhe pastaj së fundi, në qoftë se ju doni të futur diçka në fund të listës, kjo është edhe më e lehtë. Kjo është lloj i simbol arbitrare, por akrep 34-së, të marrë një guess. Cila është vlera e treguesin e saj më të lloj të ngjarë të tërhequr si një i vjetër antenë shkollë atje? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Kjo është ndoshta null. Dhe me të vërtetë që është një autor të përfaqësimi i null. Dhe kjo është për shkak se ju absolutisht të pavlefshëm duhet të dinë se ku fundi i një linked Lista është, që të mos ju mbani poshtë dhe ndjekur dhe duke ndjekur këto shigjeta për disa vlera mbeturinave. Pra, do null ditur se nuk ka asnjë nyjet më shumë për të drejtën e numrit 34, në këtë rast. 

Pra, ne propozojmë që ne mund të zbatojë kjo nyje në kodin. Dhe ne kemi parë këtë lloj të sintaksës e para. Typedef thjesht përcakton një lloj të ri për na, na jep një sinonim si string ishte për * char. Në këtë rast, ajo do të na japë simbol stenografi në mënyrë që nyjen struct në vend të vetëm mund të shkruhet si nyjeve, e cila eshte nje pastruese shumë. Kjo është një shumë më pak fjalëshumë. 

Brenda një nyje është me sa duket një int n quajtur, dhe pastaj një nyje struct * që do të thotë saktësisht se çfarë ne kemi dashur shigjeta për të do të thotë, një tregues për një tjetër Nyja e llojit të njëjtë e saktë të të dhënave. Dhe unë propozoj që ne mund të zbatojë një kërko funksion si kjo, e cila në shikim të parë mund të duket një kompleks pak. Por le të shohim atë në kontekst. 

Më lejoni të kalojmë në aplikim këtu. Më lejoni të hapur një skedar të quajtur Lista zero dot h. Dhe që përmban vetëm përkufizimi pashë vetëm një moment më parë për këto të dhëna Lloji quhet nyje. Pra, ne kemi vënë në një skedar h dot. 

Dhe si një mënjanë, edhe pse kjo program që ju jeni gati për të parë është jo të gjithë se komplekse, ajo është me të vërtetë Konventa kur shkruhet një program për vënë gjëra të tilla si lloje të të dhënave, për të tërhequr konstanta ndonjëherë, brenda tuaj fotografi header dhe jo domosdoshmërisht në C fotografinë tuaj, sigurisht kur tuaj Programet merrni më të mëdha dhe më të mëdha, në mënyrë që ju e dini ku mund të shikoni për të dyja Dokumentacioni në disa raste, apo për bazat si kjo, Përkufizimi i disa lloj. 

Nëse unë tashmë e hapur deri list zero dot c, vini re disa gjëra. Ai përfshin një fotografi pak më Header, nga të cilat ne kemi parë më parë. Ai përfshin vetë dosjen e saj header. 

Dhe si një mënjanë, pse kjo është e dyfishtë citon këtu, në krahasim me kënd kllapa në linjën që Unë e kam theksuar atje? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Po kështu kjo është një skedar lokal. Pra, në qoftë se ajo është një fotografi lokale nga mesi juaj ketu on line 15, për shembull, ju përdorni kuotat e dyfishtë në vend i kllapave angled. 

Tani kjo është lloj i interesante. Vini re se unë kam deklaruar një global ndryshueshme në këtë program on line 18 thirrur së pari, ideja e të qenit kjo është do të jetë një kursori te pare Nyja në listën time të lidhura, dhe unë kam initialized atë të pavlefshëm, sepse unë kam nuk ndahen asnjë aktuale nyjet vetëm ende. 

Pra, kjo përfaqëson, në pikturë, ajo që ne pashë një moment më parë në foto si se pointer on tani anën e majtë. Deri tani, që pointer nuk kanë një shigjetë. Ajo në vend është vetëm null. Por, ajo përfaqëson atë që do të jetë adresa aktuale e parë Nyja në këtë listë. Kështu që unë kam zbatuar ajo është një global sepse, si ju do të shihni, e gjithë kjo Programi bën në jetë është të zbatojë një listë e lidhur për mua. 

Tani unë kam një prototipe disa këtu. I vendosur për të zbatuar karakteristika si , fshirjen e futje, kërkim, dhe traversal - shëtitje nëpër fundit vetëm duke u lista, shtypje nga elementet e saj. Dhe tani këtu është rutinë im kryesor. Dhe ne nuk do të shpenzojnë shumë kohë në këto që kjo është lloj i, me shpresë hat e vjetër deri tani. 

Unë jam duke shkuar për të bërë në vijim, ndërsa përdoruesit bashkëpunon. Pra një, unë jam duke shkuar për të shtypur nga kjo menu. Dhe unë kam formatuar atë si pastër si unë mund. Nëse përdoruesi lloje në njërën, që do të thotë ata duan për të fshirë diçka. Nëse përdorues në dy lloje, që do të thotë ata duan për të futur diçka. Dhe kështu me radhë. Unë jam duke shkuar për të pastaj të menjëhershëm pastaj për një komandë. Dhe atëherë unë jam duke shkuar për të përdorur GetInt. 

Pra, kjo është një të vërtetë të thjeshtë menuing kryesh ku ju vetëm duhet të shkruani një hartë me një numër e këtyre komandave. Dhe tani kam një kaloni bukur të pastër deklaratë që do të kaloni në çfarëdo përdoruesi typed in Dhe nëse ata shtypen një, unë do telefononi fshini dhe pushim. Nëse ata shtypen dy, unë do të telefononi futur dhe pushim. 

Dhe Tani vini re unë kam vënë çdo nga këto në të njëjtën linjë. Kjo është vetëm një vendim stilistik. Zakonisht ne kemi parë diçka të si kjo. Por unë thjesht vendosi, sinqerisht, programin tim dukej më i lexueshëm për shkak ajo ishte vetëm katër raste për të vetëm lista atë si kjo. Përdorimi Krejtësisht legjitime e stilit. Dhe unë jam duke shkuar për të bërë këtë për aq kohë sa përdoruesi nuk ka shtypur zero, të cilat unë vendosur do të thotë se ata duan të lënë. 

Deri tani njoftim se çfarë unë jam duke shkuar për të bërë këtu. Unë jam duke shkuar për të liruar listën me sa duket. Por më shumë se në një moment të vetëm. Le të parë të drejtuar këtë program. Pra më lejoni të bëjë një terminal të madhe dritare, dot lista slash 0. Unë jam duke shkuar për të shkuar përpara dhe të futur nga typing dy, një numër si 50, dhe tani ju do të shihni listë është tani 50. Dhe teksti time vetëm scrolled deri pak. Deri tani njoftim listë përmban numër 50. 

Le të bëni një tjetër insert duke marrë dy. Le të shkruani në numrin si një. Lista e tani është një, e ndjekur nga 50. Pra, kjo është vetëm një përfaqësim tekstuale nga lista. Dhe le të futni numrin një më shumë si numër 42, e cila është shpresë do të përfundojë deri në mes, sepse ky program në terezi ajo veçanta elemente si ajo fut ato. Kështu që nuk kemi atë. Super program i thjeshtë që mund të absolutisht kanë përdorur një rrjet, por unë ndodhë të jetë duke përdorur një listë të lidhur vetëm kështu unë mund të dinamike rritet dhe tkurret atë. 

Pra, le të marrin një vështrim për kërkimin, në qoftë se unë drejtuar komandën tre, unë dua për të kërkuar për, të themi, me numrin 43. Dhe asgjë nuk u gjet me sa duket, sepse unë kam kthyer asnjë përgjigje. Pra, le ta bëjmë këtë përsëri. Kërko. Kërko për 50 Le të, ose në vend të kërkoni per 42, i cili ka nje mirë Kuptimi pak delikate. Dhe kam gjetur kuptimin e jetës atje. Numri 42, në qoftë se ju nuk e dini referenca, Google atë. Dakord. Pra, çfarë e ka këtë program bërë për mua? Ajo është e lejuar vetëm mua për të futur kështu larg dhe kërkimit të elementeve. 

Le të shpejtë përpara, pastaj, për të se funksioni ne lëshoi ​​në hënën si një ngacmues. Pra këtë funksion, unë pretendojnë, kërkimet për një element në lista duke parë një, duke bërë që përdoruesit dhe pastaj duke e quajtur GetInt për të marrë një int aktuale që ju doni të kërkoni për të. 

Pastaj këtë njoftim. Unë jam duke shkuar për të krijuar një ndryshore të përkohshme në përputhje quajtur 188 pointer - PTR - mund të ketë e quajti atë gjë. Dhe kjo është një tregues për një nyje sepse unë thashë: * nyje atje. Dhe unë jam Initializing që ajo të jetë e barabartë me parë në mënyrë që unë efektivisht kanë mia gisht, kështu që të flasin, më shumë elementi i parë i lista. Pra, në qoftë se dora ime e djathtë këtu është PTR unë jam duke treguar në të njëjtën gjë që së pari është vënë në. 

Pra, tani është kthyer në kod, çfarë ndodh ardhshëm - kjo është një paradigmë e zakonshme kur iterating mbi një strukturë si një lista e lidhura. Unë jam duke shkuar për të bërë në vijim, ndërsa akrep nuk është e barabartë me null Kështu, ndërsa Gishti im nuk është treguar në disa null vlera, nëse akrep shigjeta n barabartë me n. Ne do të vëreni parë që është ajo n përdorues shtypen në GetInts për të thirrur këtu. 

Dhe akrep shigjeta n do të thotë çfarë? E pra, nëse ne do të shkojmë përsëri në foto këtu, në qoftë se unë kam një gisht duke treguar në se nyja e parë që përmban nëntë, e shigjetë në thelb do të thotë se të shkojnë në Nyja dhe kap vlerën në lokacionin n, në këtë rast, fusha të dhënave të quajtur n. 

Si një mënjanë - dhe ne e pamë këtë çift një javë më parë, kur dikush e pyeti - kjo Sintaksa është e re, por kjo nuk e bën na japin kompetenca që ne nuk ka tashmë kanë. Cila ishte kjo frazë e barabartë për të përdorur dot simbol yll dhe një çift javë më parë, kur ne peeled mbrapa kjo shtresë pak kohe? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Pikërisht, ajo ishte ylli, dhe atëherë ajo ishte yll dot n, me kllapat këtu, e cila duket, sinqerisht, unë mendoj se një shumë më të fshehtë për të lexuar. Por pointer yll, si gjithmonë, do të thotë të shkojnë atje. Dhe një herë ju jeni atje, çfarë të dhëna fushë nuk ju duan të hyni? E pra ju përdorni për të hyrë në simbol dot një structs dhënat fushë, dhe unë veçanërisht dua n. 

Sinqerisht, unë do të argumentojnë këtë është vetëm e vështirë për të lexuar. Është e vështirë për të kujtuar ku bëni kllapat shkojnë, ylli dhe të gjithë se. Pra bota miratuar disa sintaktik sheqer, mënyrë që të flasin. Vetëm një mënyrë për të thënë sexy, kjo është ekuivalente, dhe ndoshta më shumë intuitiv. Në qoftë se është me të vërtetë një akrep akrep, Mjetet simbol shigjetë shkoni atje dhe për të gjetur fushë në këtë rast quhet n. 

Pra, nëse unë gjej atë, njoftim se çfarë bëj unë. Unë thjesht të shtypura jashtë, unë kam gjetur për qind, mbylljen në vlerë për atë int. Unë e quaj fle për një të dytë vetëm për të llojit i gjërave pauzë në ekran për të dhënë përdoruesit një të dytë për të absorbuar çfarë ka ndodhur vetëm. Dhe pastaj kam thyer. Përndryshe, çfarë të bëj? I update pointer të barabartë shigjetë pointer ardhshëm. 

Pra, vetëm të jetë i qartë, kjo do të thotë të shkojnë atje, duke përdorur simbol i vjetër-shkollën time. Pra, kjo do të thotë vetëm për të shkuar në çfarëdo ju jeni duke treguar, e cila në shumë Rasti i parë është që unë jam vënë në struct me nëntë në të. Kështu që unë kam shkuar atje. Dhe pastaj dot simbol do të thotë, marrë në vlerën e ardhshëm. 

Por vlera, edhe pse ajo është tërhequr si një të ngushtë, është vetëm një numër. Kjo është një adresë numerike. Pra, kjo një linjë e kodit, nëse shkruar si kjo, më e fshehtë mënyra, ose si kjo, pak më shumë mënyrë intuitive, thjesht do të thotë të lëvizë dorën time nga e nyjes së parë me një tjetër, dhe pastaj një tjetër, dhe pastaj një tjetër, dhe kështu me radhë. 

Pra, ne nuk do të banojë në tjetrin Implementimi i futur dhe fshini dhe traversal, dy të parë të të cilat janë të përfshira në mënyrë të drejtë. Dhe unë mendoj se është mjaft e lehtë për të marrë kur humbi bërë atë verbalisht. Por çfarë mund të bëjmë këtu është përpiqen për të përcaktuar se si mirë për të bërë këtë visually. Sepse unë do të propozojë që në qoftë se ne doni të futur elemente në këtë listë ekzistuese, e cila ka pesë elemente - 9, 17, 22, 26, dhe 33 - në qoftë se unë ishin duke shkuar për të zbatuar këtë në Kodi, kam nevojë të marrin në konsideratë se si të shkojë për ta bërë këtë. 

Dhe unë do të propozojë marrjen hapa të fëmijës ku, në këtë rast unë do të thotë, se çfarë janë skenarët e mundshme që ne mund të hasni në përgjithësi? Kur zbatimin insert për një linked listë, kjo thjesht ndodh të jetë një shembull specifik i madhësisë pesë. E pra në qoftë se ju doni të futur një numër, si thonë numrin një, dhe mbajtjen e rendit të renditura, ku padyshim bën numër një nevojë për të shkoni në këtë shembull të veçantë? Ashtu si në fillim. 

Por ajo që është interesante është se ka në qoftë se ju doni të futur një në këtë listë, çfarë akrep veçantë duhet të freskohen me sa duket? Së pari. Kështu që unë do të argumentojnë, ky është rasti i parë që ne mund të dëshirojnë të marrin në konsideratë, një skenar që përfshin futur në fillimi i lista. 

Le të hiqni ndoshta një aq e lehtë apo edhe Rasti lehtë, relativisht të folur. Supozoni se unë dua të futur Numri 35 në mënyrë renditura. Ajo padyshim i takon atje. Pra, çfarë akrep padyshim do të duhet të jenë të përditësuar në këtë skenar? Akrep 34 e duke u bërë jo null por adresa e struct përmbajnë numrin 35. Pra, kjo është rasti dy. Pra tashmë, unë jam lloj i quantizing se sa shumë punë duhet të bëj këtu. 

Dhe së fundi, çështja e mesme është e qartë në të vërtetë, në mes, në qoftë se unë dua të futur diçka si thonë 23, që shkon në mes të 23 dhe 26, por tani gjërat merrni pak më shumë përfshirë për shkak se çfarë pointers duhet të ndryshohet? 22 Pra, padyshim duhet të ndryshohet sepse ai nuk mund të tregojnë për 26 anymore. Ai ka nevojë për pikë në nyjen e re që Unë do të duhet të ndajë duke telefonuar malloc ose disa ekuivalent. 

Por atëherë unë gjithashtu duhet se Nyja e re, 23 në këtë rast, që të ketë treguesin e saj duke vënë në kë? 26. Dhe atje do të jetë një Urdhri i operacioneve këtu. Sepse në qoftë se unë bëj këtë si një budalla dhe kam për fillimin e shkallës në fillim të lista, dhe qëllimi im është për të futur 23. Dhe unë kontrolloni, ajo nuk i përkasin këtu, afër nëntë? Jo. A është i përkasin këtu, pranë 17? Jo. A ajo i takon këtu ardhshme për 22? Po. 

Tani, nëse unë jam budalla këtu, dhe nuk duke menduar këtë anë, unë mund ndajë nyje tim të ri për 23. Unë mund të rinovuar në treguesin nga nyjen quajtur 22, duke treguar ajo në nyjen e re. Dhe pastaj çfarë kam për të rinovuar akrep nyjen e ri të jetë? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Pikërisht. Duke treguar në 26. Por dammit qoftë se unë nuk tashmë të rinovuar Akrep 22 për pikë në këtë djalë, dhe tani kam jetimëve, pjesa tjetër i listës, kështu që të flasin. Pra, rendi i operacioneve këtu do të jetë e rëndësishme. 

Për ta bërë këtë mund ta vjedhin, thonë, gjashtë vullnetarë. Dhe le të shohim nëse ne nuk mund ta bëjmë këtë vizualisht në vend të kodit-mençur. Dhe ne kemi disa stres bukuroshe topa për ju sot. Rregull, si rreth një, dy, ne back - në fund atje. tre, katër, dy prej jush djemtë në fund. Dhe pesë, gjashtë. Sigurt. Pesë dhe gjashtë. Të gjithë të drejtë dhe ne do të vijnë për ju djema herën tjetër. Të gjithë të drejtë, vijnë më lart. 

Të gjithë të drejtë, pasi ju jeni këtu të parë, do të ju pëlqen të jetë një dyluftimi në ajër në xham Google këtu? Të gjithë të drejtë, kështu që, OK, qelqi, regjistroni një video. Ok, ju jeni të mirë për të shkuar. 

Të gjithë të drejtë, kështu që nëse ju djema mund të vijnë gjatë këtu, unë kam përgatitur paraprakisht disa numra. Të gjithë të drejtë, eja mbi këtu. Dhe pse nuk shkoni pak më tej në këtë mënyrë. Dhe le të shohim, çfarë është emri juaj, Glass me Google? 

STUDENT: Ben. 

Kryetari 1: Ben? OK, Ben, ju do të jetë i pari, fjalë për fjalë. Pra, ne jemi duke shkuar për të ju dërgojnë deri në fund të fazës. ? Gjithë të drejtë, dhe emri juaj 

STUDENT: Jason. 

Kryetari 1: Jason, OK ju do të të jetë numër nëntë. Pra, nëse ju doni të ndiqni rrugën e ben atë. 

STUDENT: Jill. 

Kryetari 1: Jill, ju jeni do të jetë 17, e cila në qoftë se unë do të bëhet kjo më shumë inteligjente, unë do të ketë filloi në fund të tjera. Ju shkoni në këtë mënyrë. 22. Dhe ju jeni? 

STUDENT: Mary. 

Kryetari 1: Mary, ju do të jetë 22. Dhe emri juaj është? 

STUDENT: Chris. 

Kryetari 1: Chris, ju do të jetë 26. Dhe pastaj së fundi. 

STUDENT: Diana. 

Kryetari 1: Diana, ju do të jetë 34. Kështu që ju vijnë më gjatë këtu. 

Të gjithë të drejtë, të renditura në mënyrë të përsosur urdhërojë tashmë. Dhe le të shkojë përpara dhe të bëjë këtë kështu që ne mund të vërtetë - Ben ju jeni vetëm në kërkim të lloj jashtë në askund atje. OK, kështu që le të shkojnë përpara dhe të përshkruaj këtë përdorimin e armëve, ashtu si unë ishte pikërisht,, çfarë po ndodh. Pra shkoni përpara dhe të japë vetes një këmbë ose dy në mes vete. Dhe të shkojnë përpara dhe pikë me një dorë të kushdo që ju duhet të vënë në bazuar në këtë. Dhe në qoftë se ju jeni vetëm pika null drejt poshtë në dysheme. OK, në mënyrë të mirë. 

Pra, tani ne kemi një listë të lidhura, dhe më lejoni propozojë që unë do të luajnë rolin e PTR, kështu që unë nuk do të shqetësojë mbante këtë rreth. Dhe pastaj - Konventa dikush budalla - ju mund të telefononi këtë gjë që ju dëshironi - Paraardhësi akrep, akrep pred - kjo është vetëm Mbyll kemi dhënë në Kodi tonë mostër në dorën time të majtë. Dora tjetër që do të jetë mbajtur gjurmët e kush është kush në pas skenarë. 

Pra, mendoj, së pari, unë dua të këpus off se shembulli i parë i futur, thonë 20 në listë. Kështu që unë jam duke shkuar për nevojë për dikë që mishërojnë numrin 20 për ne. Kështu që kam nevojë për dikë malloc nga audienca. Come on up. Cili është emri juaj? 

STUDENT: Brian. 

Kryetari 1: Brian, të gjithë të drejtë, kështu që ju do të jetë nyja që përmbajnë 20. Të gjithë të drejtë, eja mbi këtu. Dhe natyrisht, ku Brian nuk i përkasin? Kështu, ne mes te - vërtetë, prisni një minutë. Ne jemi duke e bërë këtë nga e rendit. Ne jemi duke e bërë këtë një shumë e vështirë sesa ajo ka nevojë të jetë në të parë. OK, ne jemi duke shkuar për të lirë Brian dhe realloc Brian si pesë. 

OK, kështu që tani që ne duam të futur Brian si pesë. Pra, të vijë në mbi këtu ardhshëm për Ben për vetëm një moment. Dhe ju mund të tregoni sa duket ku kjo histori është e shkuar. Por le të mendoni me kujdes për Urdhri i operacioneve. Dhe kjo është pikërisht kjo vizuale që do të vijë deri me atë kod mostër. Kështu që këtu unë kam treguar fillimisht PTR jo me Ben, në vetvete, por në çfarëdo ai përmban vlera, e cila në këtë rast është - çfarë është emri juaj përsëri? 

STUDENT: Jason. 

Kryetari 1: Jason, kështu që të dy Ben dhe unë jemi duke vënë në Jason në këtë moment. Deri tani unë kam për të përcaktuar, ku do Brian përkasin? Pra, e vetmja gjë që unë kam qasje në tani është n e tij dhënave artikull. Kështu që unë jam duke shkuar për të kontrolluar, është e Brian pak se Jason? Përgjigja është e vërtetë. 

Pra, çfarë duhet të ndodhë tani, në mënyrë korrekte? Unë kam nevojë për të rinovuar sa pointers në total në këtë histori? Ku dora ime është ende duke treguar në Jason, dhe dora jote - në qoftë se ju doni të vëre dorën tënde si, lloj, unë nuk e di, një pikëpyetje. OK, i mirë. 

Të gjithë të drejtë, kështu që ju keni disa kandidatë. Ose ben ose unë ose Brian apo Jason ose secili tjetër, e cila pointers duhet të ndryshojë? Sa në total? 

OK, kështu që dy. Akrep ime nuk ka të vërtetë rëndësi më sepse unë jam vetëm i përkohshëm. Pra, kjo është këto dy guys, me sa duket, Ben si dhe Brian. Pra më lejoni të propozojnë që ne update Ben, pasi ai është i pari. Elementi i parë i kësaj liste tani do të jetë Brian. Pra, pika e ben at Brian. OK, tani çka? 

Kush merr vuri në kë? 

STUDENT: [padëgjueshme]. 

Kryetari 1: OK kështu Brian ka për pikë në Jason. Por kam humbur gjurmët e asaj akrep? A e di se ku Jason është? 

STUDENT: [padëgjueshme]. 

Kryetari 1: bëj, pasi që unë jam pointer përkohshme. Dhe me sa duket, unë nuk kanë ndryshuar për pikë në nyjen e re. Pra, ne thjesht mund të ketë pikë Brian në kushdo që unë jam vënë në. Dhe ne jemi duke bërë. Pra një rast, futje në fillim të listës. Kishte dy hapa kyçe. Një, ne kemi për të rinovuar Ben, dhe pastaj ne gjithashtu kemi Brian për të rinovuar. Dhe atëherë unë nuk duhet të shqetësojë traipsing nëpër pjesën tjetër të listë, sepse ne tashmë gjetur rrugën e tij vend, sepse ai i përkiste la e elementit të parë. 

Të gjithë të drejtë, kështu që shumë i thjeshtë. Në fakt, ndihet si ne jemi gati duke e bërë këtë shumë e komplikuar. Pra, le të tani nxirre jashtë fundin i listës, dhe shiko ku Kompleksiteti fillon. Pra, në qoftë se tani unë shenjat e nga publiku. Çdokush duan të luajnë 55? Të gjithë të drejtë, unë pashë dorën tuaj të parë. Come on up. Po. Cili është emri juaj? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Habata. OK, eja lart. Ju do të jetë numër 55. Pra, ju, natyrisht, i përkasin ne fund te lista. Pra, le sërish simulimin me mua duke qenë PTR për vetëm një moment. Kështu që unë jam duke shkuar për të parë pikë në çfarëdo Ben është vënë në. Ne jemi të dy vënë tani në Brian. Pra, 55 është jo më pak se pesë. Kështu që unë jam duke shkuar për të rinovuar veten nga duke treguar për treguesin e ardhshëm Brian, i cili tani është sigurisht Jason. 55 A nuk është më pak se nëntë, në mënyrë Unë jam duke shkuar për të rinovuar ptr. Unë jam duke shkuar për të rinovuar ptr. Unë jam duke shkuar për të rinovuar ptr Unë do të rinovuar ptr. Dhe unë jam duke shkuar për - hmm, çfarë është emri juaj përsëri? 

STUDENT: Diana. 

Kryetari 1: Diana është vënë, natyrisht, at null me dorën e saj të majtë. Pra, ku e bën në fakt Habata i përkasin në mënyrë të qartë? Në të majtë, këtu. Pra, si mund ta di për të vënë e saj këtu Unë mendoj se kam dehur. Sepse ajo është PTR art ky moment në kohë? NULL. Pra, edhe pse, vizualisht, ne mund të padyshim shohim të gjitha këto djema këtu në skenë. Unë nuk kam mbajtur gjurmët e mëparshme person në listë. Unë nuk kam një gisht duke treguar jashtë, në këtë rast, numri 34 nyje. 

Pra, le të vërtetë të fillojë mbi këtë. Deri tani unë në fakt nuk kanë nevojë për një variabël e dytë lokal. Dhe kjo është ajo që ju do të shihni në Kodi aktuale mostër C, ku si shkoj unë, kur unë Përditëso dorën e djathtë të pikës Jason, duke lënë prapa Brian, unë më mirë të fillojë duke përdorur dorën e majtë për Përditëso ku isha, në mënyrë që sa të shkoj nëpërmjet kësaj liste - më shumë ajër se unë për qëllim Tani këtu vizualisht - Unë jam duke shkuar për të marrë në fundi i lista. 

Kjo dorë është ende null, e cila është shumë e padobishme, përveç për të treguar Unë jam në mënyrë të qartë në fund të listës, por tani të paktën unë kam këtë akrep paraardhësi i treguar këtu, kështu që tani ajo që duart dhe çfarë pointers duhet të freskohen? Dorën e të cilit nuk ju duan për të rikonfiguruar të parë? 

STUDENT: [padëgjueshme]. 

Kryetari 1: OK, kështu që së Dianës. Ku ju doni të theksoj Treguesin e majtë Dianës në? Në 55, me sa duket, në mënyrë që ne kemi futur atje. Dhe ku duhet të shkojnë 55 akrep? Down, përfaqëson null. Dhe duart e mia, në këtë pikë, nuk rëndësi, sepse ata ishin vetëm ndryshore të përkohshme. Pra, tani që ne jemi duke bërë. 

Pra, kompleksiteti shtesë atje - dhe kjo nuk është se e vështirë për të zbatuar, por ne kemi nevojë për një ndryshore mesme për të bërë Sigurohuni që para unë të lëvizin të drejtën time dorë, unë update vlerën e majtë ime , dora akrep pred në këtë rast, kështu që se unë kam një pointer prapa vetes të mbajnë gjurmët e ku isha. Tani si një mënjanë, në qoftë se jeni duke menduar këtë anë, kjo ndjehet si ajo është një pak i bezdisshëm që të ketë për të mbajtur gjurmët e këtij dorën e majtë. 

Çfarë do një tjetër zgjidhje për këtë problem kanë qene? Nëse ju mori për të redesign e të dhënave Struktura ne jemi duke folur nëpërmjet tani? Nëse ky lloj i ndjen vetëm pak i bezdisshëm që të ketë, si, dy pointers duke shkuar nëpër lista, kush tjetër mund të kanë, në botën ideale, mirëmbahen Informacioni që kemi nevojë? Po? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Pikërisht. Drejtë kështu që nuk ka të vërtetë interesante embrion i një ideje. Dhe kjo ideja e një akrep mëparshëm, duke vënë në elementin e mëparshëm. Çka nëse unë mishëruar vetëm se brenda të listës vetë? Dhe kjo do të jetë e vështirë për të parashikoj kjo pa të gjitha në letër duke rënë në katin e. Por mendoj se këta djem përdoret edhe e duarve të tyre që të ketë një paraardhëse kursori, dhe një akrep tej, në këtë mënyrë zbatimin e asaj që ne do të thërrasë një dyfish lista e lidhura. Kjo do të lejoni që lloj i Rewind, shumë më lehtë pa mua, programues, që ka për të mbajtur ndjekur dorë - me të vërtetë dorë - prej ku kisha qenë më parë ne lista. Pra, ne nuk do të bëjë këtë. Ne do të mbani atë të thjeshtë, sepse kjo është do të vijnë me një çmim, dy herë më shumë hapësirë ​​për pointers, në qoftë se ju doni një të dytë. Por kjo është me të vërtetë një të përbashkët Të dhënat Struktura e njohur si një lidhur dyfish listë. 

Le të bëjmë shembullin përfundimtare këtu dhe vënë këta njerëz nga mjerimi e tyre. Pra malloc 20. Come on deri nga atje rresht. Të gjithë të drejtë, çfarë është emri juaj? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Na vjen keq? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Demeron? OK vijnë më lart. Ju do të jetë 20. Ju padyshim do të përkasin në mes të 17 dhe 22. Pra më lejoni të mësuar mësimin tim. Unë jam duke shkuar për të filluar treguesin duke treguar në Brian. Dhe unë jam duke shkuar të ketë dorën time të majtë vetëm update për Brian si unë për të lëvizur Jason, kontrolluar e bën 20 më pak se nëntë? Jo. 20 është më pak se 17? Jo. 20 është më pak se 22? Po. Pra, çfarë pointers ose duart duhet të ndryshojë ku ata janë treguar tani? 

Pra, ne mund të bëjmë vënë 17 në 20. Pra, kjo është në rregull. Ku duam të theksoj treguesin tuaj tani? Në 22. Dhe ne e dimë se ku është 22, përsëri falë për treguesin tim të përkohshëm. Pra, ne jemi OK atje. Pra, për shkak të këtij magazinimit të përkohshëm Unë kam mbajtur gjurmët e ku të gjithë është. Dhe tani ju mund të shikimi të shkojnë në ku ju i përkisni, dhe tani ne kemi nevojë për 1, 2, 3, 4, 5, 6, 7, 8, 9 topa stresi, dhe një raund i duartrokitje për këta njerëz, nëse ne mund të. Nicely done. 

[Duartrokitje] 

Kryetari 1: Në rregull. Dhe ju mund të mbani copa i letrës si mementos. 

Të gjithë të drejtë, kështu që, besoni mua kjo është një shumë më të lehtë të ecin nëpër se me njerëzit se ajo është me kodin aktual. Por ajo që ju do të gjeni në një moment të vetëm tani, është se njëjtë - oh, thank you. Faleminderit - është se ju do të gjeni se të njëjtat të dhëna Struktura, një listë të lidhura, në fakt mund të të përdoret si një bllok ndërtimi për edhe më shumë Strukturat e të dhënave të sofistikuara. 

Dhe të kuptojë too temë e këtu është se ne kemi prezantuar absolutisht më shumë Kompleksiteti në zbatimin i këtij algoritmi. Futje, dhe në qoftë se ne kemi shkuar nëpërmjet saj, fshirjen dhe kërkimin, është pak më e komplikuar se ajo ishte me një rrjet. Por ne kemi fituar disa dinamizëm. Ne kemi marrë një strukturë adaptive të dhënave. 

Por përsëri, ne të paguajë një çmim për të pasur disa Kompleksiteti shtesë, si në zbatimin e tij. Dhe ne jemi të dhënë up qasje të rastit. Dhe të jetë i sinqertë, nuk është disa bukur pastruar rrëshqitje unë mund të ju jap se thotë se këtu është arsyeja pse një listë e lidhur është më mirë se një rrjet. Dhe të lënë atë në atë. Sepse temë reoccurring tani, madje edhe aq më tepër në javët e ardhshme, është se nuk është domosdoshmërisht një përgjigje të saktë. 

Kjo është arsyeja pse ne kemi aksin veçantë e projektimit për grupe problem. Ajo do të jetë shumë e ndjeshme konteksti nëse ju doni të përdorni këto të dhëna strukturë ose se një, dhe kjo do varet nga ajo që ka rëndësi për ju në aspektin e burimeve dhe kompleksitet. 

Por më lejoni të propozojnë se të dhënat ideale Struktura, Grail shenjtë, do të jetë diçka që është koha konstante, pavarësisht nga sa shumë gjëra është brenda saj, nuk do të ishte e mahnitshme në qoftë se një Struktura e të dhënave u kthye përgjigje në Ora konstante. Po. Kjo fjalë është në fjalorin tuaj të madh. Apo jo, kjo fjalë nuk është. Ose ndonjë problem i tillë atje. E pra le të shohim nëse ne nuk mundemi të paktën të marrë një hap drejt se. 

Më lejoni të propozojë një strukturë të re të të dhënave që mund të përdoret për gjëra të ndryshme, në këtë rast quhet një tabelë hash. Dhe kështu që ne jemi në të vërtetë kthehet në glancing me një rrjet, në këtë rast, dhe disi arbitrare, unë kam tërhequr këtë tabelë hash si një grup me një lloj të dy-dimensional array - ose më mirë ajo është përshkruar këtu si dy array dimensionale - por kjo është vetëm një grup i madhësisë 26, të tilla që në qoftë se ne telefononi tabelën e vektorit, parantezë tavolinë zero eshte drejtkëndësh në majë. Kllapa Tabela 25 është drejtkëndësh në fund. Dhe kjo është se si unë mund të tërheqë një të dhënave strukturë në të cilën I duam të ruajtur njerëzit e emra. 

Kështu për shembull, dhe unë nuk do të tërheqë Gjithë gjë këtu më lart, në qoftë se unë kishte këtë koleksion, të cilën unë jam tani do të thërrasë një tryezë të hash, dhe kjo është përsëri Vendndodhja zero. Kjo këtu është vend një, dhe kështu me radhë. Unë pretendojnë se unë dua që të përdorin këto të dhëna struktura, per shkak te diskutimit, për të ruajtur emrat e njerëzve, Alice dhe Bob dhe Charlie dhe emra të tjera të tilla. Pra, mendoj se kjo tani si në fillimet e, të themi, një fjalor me shumë fjalë. Ata ndodhë që të jetë emrat në shembullin tonë këtu. Dhe kjo është e gjitha shumë i përshtatshëm, ndoshta, për të zbatimin e një spell checker, si ne mund të për problemin e ngritur gjashtë. 

Pra, nëse ne kemi një rrjet të madhësisë totale 26 në mënyrë që ky vend është 25 në të poshtme, dhe pohoj se Alice është fjala pare ne fjalorin e Emrat që unë dua për të futur në RAM, në këtë strukturë të dhënash, ku janë Instinktet ju thënë se Alice emri duhet të shkoni në këtë grup? 

Ne kemi 26 opsione. Ku duam të vënë e saj? Ne duam atë në kllapa zero, e drejtë? Një për të Alice, le të thërrasë atë zero. Dhe do të jetë një B, dhe C do të jetë dy. Pra, ne jemi duke shkuar për të shkruar Emri Alice deri këtu. Nëse ne pastaj futni Bob tij, Emri do të shkojnë këtu. Charlie do të shkojnë këtu. Dhe kështu me radhë poshtë nëpër kjo Struktura e të dhënave. 

Kjo është një strukturë e mrekullueshme të dhënave. Pse? E pra çfarë është koha drejtimin e futur emrin e një qenie njerëzore e në këtë Struktura e të dhënave tani? Duke pasur parasysh se kjo tabelë është zbatuar, me të vërtetë, si një rrjet. E pra kjo është koha konstante. Kjo është mënyrë e njërit. Pse? 

E pra si mendoni ju të përcaktojë ku Alice takon? Ju shikoni në të cilën letër e emrit të saj? Parë. Dhe ju mund të merrni atje, nëse kjo është një string, vetëm duke shikuar në varg kllapa zero. Pra karakterit 0 të vargut. Kjo është e lehtë. Ne e bëmë që në kripto caktimit javë më parë. Dhe pastaj një herë ju e dini se së Alice Letra është kryeqyteti A, ne mund të zbres off 65 ose një kapital të vetë, që na jep zero. Pra, ne tani e dimë se Alice takon në lokacionin zero. 

Dhe duke pasur parasysh një tregues për këtyre të dhënave Struktura, e disa lloj, sa kohë bën ajo merr mua për të gjetur vendndodhjen zero në një grup? Vetëm një hap, e drejta Është koha konstante për shkak të qasjes rastit ne propozuar ishte një tipar i një rrjet. Pra me pak fjalë, duke parafytyruar se çfarë indeksi Emri i Alice është, i cili eshte, ne Në këtë rast, është Një, ose le të vetëm të zgjidhur qe te zero, ku B është një dhe C eshte dy, duke parafytyruar se nga është koha konstante. Unë vetëm duhet të shikoni në letrën e saj të parë, zbulimin ku zero eshte nje array është edhe koha konstante. Pra, teknikisht kjo është si dy hapa tani. Por kjo është ende konstante. Pra, ne e quajmë atë O e madhe e një, kështu që ne kemi Alice futur në këtë tabelë në Ora konstante. 

Por sigurisht, unë jam duke u naive këtu, e drejtë? Çka nëse nuk ka një Aaroni në klasë? Apo Alicia? Ose ndonjë emra të tjerë duke filluar me A. Ku jemi duke shkuar për të vënë se personi, e drejtë? Unë do të thotë, tani për tani ka vetëm tre njerëzit në tabelë, kështu që ndoshta ne duhet të vënë Aaronin në lokacionin zero një dy tre. 

Drejtë, unë mund të vendos një këtu. Por pastaj, nëse ne përpiqemi për të futur Davidin në kjo listë, ku do shkojnë Davidi? Tani sistemi ynë fillon thyer poshtë, të drejtë? Sepse tani David përfundon këtu nëse Aaron është në të vërtetë këtu. Dhe kështu që tani ky tërë ideja e të paturit e një pastër të dhënave strukturë që na jep insertions konstante koha nuk është më e Ora konstante, sepse unë kam për kontrolloni, oh, damnit, dikush është tashmë Alice në vend. 

Më lejoni të shqyrtojmë pjesën tjetër të këtyre të dhënave , struktura duke kërkuar për një vend për të vënë dikush si emrin e Aaronit. Dhe kështu që edhe është filluar të marrë kohën lineare. Për më tepër, në qoftë se ju doni të gjeni tani Aaroni në këtë strukturë të dhënave, dhe ju kontrolloni, dhe emri i Aaronit nuk është këtu. Idealisht, ju do të them vetëm për Aaronin jo në strukturën dhënave. Por në qoftë se ju bëni filloni duke e bërë hapësirë ​​për Aaroni ku nuk duhet të ketë qenë një D ose një, E ju, rasti më i keq, duhet të kontrolloni gjithë struktura të dhënave, në të cilin rast ai bie në diçka linear në madhësinë e tabelës. 

Pra, të gjithë të drejtë, unë do të rregullojmë këtë. Problemi këtu është se kam pasur 26 elemente në këtë grup. Më lejoni të ndryshojë atë. Uh. Më lejoni të ndryshojë atë në mënyrë që në vend të qenit i Madhësia e 26 në total, njoftim pjesën e poshtme indeksi do të ndryshojë për të n minus 1. 26 Në qoftë se është e qartë shumë e vogël për 'njerëzit emrat, sepse ka mijëra Emrat e botës, le të vetëm të bëjë në 100 apo 1000 apo 10000. Le të vetëm të ndajë një hapësirë ​​shumë më tepër. 

E pra kjo nuk domosdoshmërisht ulet probabiliteti që ne nuk do të ketë dy njerëzit me emra duke filluar me A, dhe Pra, ju u do të përpiqet për të vënë një Emrat në zero ende e lokacionit. Ata janë ende duke shkuar për të përplasjes, e cila do të thotë që ne ende nevojë për një zgjidhje për të vënë Alice dhe Aaroni dhe Alicia dhe të tjera emra duke filluar me një tjetërkund. Por si shumë e një problemi është ky? Cili është probabiliteti që ju kanë goditjet në një të dhënave Struktura si kjo? 

E pra, më lejoni - ne do të kthehemi për këtë pyetje këtu. Dhe shikoni se si ne mund të zgjidhur atë së pari. Më lejoni të tërheq lart këtë propozim këtu. Ajo që ne vetëm të përshkruar një algoritmi, një orientues i quajtur linear probing ku, nëse jeni përpjekur për të futur diçka që këtu në këto të dhëna strukturë, e cila është quajtur një tabelë hash, dhe nuk ka hapësirë ​​atje, ju vërtetë hetuar strukturën e të dhënave kontrolluar, kjo është në dispozicion? A është kjo në dispozicion është në dispozicion kjo? A është kjo në dispozicion? Dhe kur më në fund ajo është, ju futur përmendur që ju menduar fillimisht diku tjetër në atë vend. Por në rastin më të keq, i vetmi vend mund të jetë shumë e poshtme e të dhënave struktura, skaj shumë e vektorit. 

Pra linear probing, në rastin më të keq, bie në një algoritmi linear ku Aaroni, nëse ai ndodh të jetë futur fundit në këtë strukturë të dhënave, ai mund të bien ndesh me këtë vend të parë, por pastaj të përfundojë me fat të keq në fund. Pra, kjo nuk është një konstante Ora Grail shenjtë për ne. Kjo qasje e elementeve të futur në një strukturë e të dhënave e quajtur hash Tabela nuk duket të jetë kohë konstante të paktën jo në rastin e përgjithshme. Ajo mund të bie në diçka lineare. 

Pra, çfarë nëse ne të zgjidhur goditjet disi ndryshe? Pra, këtu është një më i sofistikuar qasje në atë që është ende quajtur një tavolinë hash. Dhe duke hash, Si një mënjanë, çfarë Unë do të thotë është se indeksi I përmendur më herët. Për të hash diçka mund të jetë menduar si një folje. 

Pra, nëse ju Alice hash është një emër, një funksion hash, kështu që të flasin, duhet të kthejë një numër. Në këtë rast është zero, nëse ajo i takon në Vendndodhja zero, një, nëse ajo i takon në Vendndodhja një, dhe kështu me radhë. Pra, funksioni im hash deri tani ka qenë super e thjeshtë, vetëm duke kërkuar në shkronja e parë në emër të dikujt. Por një funksion hash merr si input disa pjesë të të dhënave, një string, int një, çfarëdo. Dhe kjo pështyn në mënyrë tipike nga një numër. Dhe ky numër është se ku të dhënat e element i takon në strukturën e të dhënave e njohur këtu si një tryezë hash. 

Pra, vetëm intuitive, kjo është një kontekst pak më ndryshe. Kjo në fakt është duke iu referuar një shembull ditëlindjet përfshijnë, ku nuk mund të jetë aq sa 31 ditë në muaj. Por çfarë ka ky person të vendosë për bëni në rast të një përplasjeje? Konteksti tani të qenit, jo një përplasje të emra, por një përplasje e ditëlindje, në qoftë se dy njerëz kanë të njëjtën ditëlindje në 2 tetor, për shembull. 

STUDENT: [padëgjueshme]. 

Kryetari 1: Yeah, kështu që këtu kemi leveraging e listave të lidhura. Pra, kjo duket pak ndryshe se sa ne tërhoqi atë më parë. Por ne duket se kanë një koleksion të në anën e majtë. Kjo është një indeksi, për asnjë Arsyeja veçanti. Por kjo është ende një array. Është një grup i pointers. Dhe secili prej këtyre elementeve, secila prej këto qarqe ose ul - zvogëlojë null përfaqësojnë - secila nga këto pointers është me sa duket duke treguar për çfarë Struktura e të dhënave? Një listë e lidhur. 

Pra, tani ne kemi aftësinë për të Kodi vështirë në programin tonë madhësia e tabelës. Në këtë rast, ne e dimë se kurrë nuk ka më shumë se 31 ditë në një muaj. Pra vështirë coding si një vlerë 31 është arsyeshme në atë kontekst. Në kontekstin e emrave, e vështirë coding 26 nuk është e paarsyeshme që njerëzit e emra të fillojë vetëm me të, për shembull, Alfabeti përfshin një anë të Z. 

Ne mund të mbushur të gjitha ato në të cilat të dhënat Struktura aq kohë sa, kur ne të merrni një Përplasja, ne nuk e vënë emrat këtu, ne mendojmë në vend të këtyre qelizave jo si vargjet vetë, por si pointers, për shembull, Alice. Dhe pastaj Alice mund të ketë një tjetër treguesin për të filluar me një emër tjetër A. Dhe Bob në fakt shkon mbi këtu. 

Dhe në qoftë se ka një tjetër emër duke filluar me B, ai përfundon deri këtu. Dhe kështu secili prej elementeve të këtij Tabela dy, në qoftë se ne kemi projektuar këtë një pak më shumë cleverly - eja - në qoftë se ne kemi projektuar këtë një pak më shumë cleverly, tani bëhet një adaptive dhënat Struktura, ku nuk ka asnjë kufizim vështirë se sa elementet që ju mund të futni në të, sepse në qoftë se ju keni një përplasje, kjo është në rregull. Vetëm të shkojnë përpara dhe append atë në atë që pamë pak më parë ishte i njohur si një listë e lidhur. 

E pra, le të pauzë për një moment të vetëm. Cili është probabiliteti i një përplasjeje të rëndë në vendin e parë? E drejta, ndoshta unë jam mbi të menduarit, ndoshta Unë jam inxhinieri mbi këtë problem, sepse ju e dini se çfarë? Po, unë mund të dalë me arbitrare shembuj pjesa e sipërme e kokës sime si Allison dhe Aaroni, por në realitet, jepet një shpërndarje uniforme të inputet, që është disa insertions të rastit në strukturën e të dhënave, ajo që është me të vërtetë mundësia e një përplasjeje? E pra rezulton, ajo është në fakt super të lartë. Më lejoni të përgjithësoj këtë Problemi është si kjo. 

Pra, në një dhomë të n CS50 studentëve, çfarë është probabiliteti që të paktën dy studentë në dhomë kanë të njëjtën ditëlindje? Pra, nuk është ajo. një hund pak - 200, 300 njerëz këtu dhe disa qindra njerëz në shtëpi sot. Pra, nëse ju të kërkuar për të pyesni veten se çfarë është probabiliteti i dy njerëzve në këtë dhomë ka të njëjtën ditëlindje, ne mund të kuptoj këtë. Dhe unë pretendojnë fakt ekzistojnë dy njerëzit me të njëjtën ditëlindje. 

Për shembull, e bën dikush kanë ditëlindjen sot? Dje? Nesër? Të gjithë të drejtë, kështu që ai ndjehet si unë jam duke shkuar që të ketë për të bërë këtë 363 ose kështu që më shumë herë që në fakt të kuptoj në qoftë se ne kemi një përplasje. Ose ne mund vetëm të bëjë këtë matematikisht sesa tediously bërë këtë. Dhe të propozojë në vijim. 

Kështu që unë propozoj që ne mund të modelojnë Probabiliteti i dy njerëzve që kanë ditëlindjen e njëjtë si probabilitetin e 1 minus probabilitetin e Asnjëri që ka njëjtën ditëlindje. Pra, për të marrë këtë, dhe kjo është vetëm Mënyra më e sofistikuar për të shkruar këtë, për personi i parë në dhomë, ai ose ajo mund të ketë çdo njëri prej mundur ditëlindjet supozuar ditë 365 në vit, me keqardhjet për personat me ditëlindjen e 29 Shkurt. 

Pra, personi i parë në këtë dhomë është i lirë të ketë ndonjë numër të ditëlindje jashtë mundësive 365 në mënyrë që ne do të bëjmë që ndahen nga 365 365, e cila është një. Personi tjetër në dhomë, në qoftë se qëllimi është për të shmangur një përplasje, mund vetëm kanë ditëlindjen e tij ose të saj në mënyrën se si shumë ditë të ndryshme të mundshme? 364. Pra, termi i dytë në këtë shprehje është në thelb të bërë atë matematikë për ne duke zbritur off një ditë të jetë e mundur. Dhe pastaj ditën tjetër, të nesërmen, nesërmen poshtë në numrin e përgjithshëm e njerëzve në dhomë. 

Dhe nëse ne pastaj e konsiderojnë, çfarë atëherë është probabiliteti i të gjithëve nuk ka ditëlindjet unike, por përsëri 1 minus se, ajo që ne kemi marrë është një shprehje që mund shumë fancifully duket si ky. Por kjo është më interesante për të parë në sy. Kjo është një tabelë ku mbi boshtin x eshte numri i njerëzve në dhomë, Numri i ditëlindje. Në y-aks është probabiliteti e një përplasjeje të rëndë, dy njerëz pasur ditëlindjen njëjtë. 

Dhe takeaway nga kjo kurbë është që sa më shpejt që ju të merrni për të si 40 studentë, ju jeni deri në një probabilitet 90% combinatorically i dy njerëzit apo më shumë kanë njëjtën ditëlindje. Dhe një herë ju merrni për të si 58 njerëz kjo është gati 100% e një shans dy njerëz në dhomë do të ketë ditëlindjen e njëjtë, edhe pse ka 365 ose 366 kova të mundshme, dhe vetëm 58 njerëz në dhomë. Vetëm statistikisht ju jeni të ngjarë të merrni goditjet, e cila në të shkurtër motivon këtë diskutim. Se edhe në qoftë se ne të merrni dashuroj këtu, dhe fillojnë që këto zinxhirët, ne jemi ende do të ketë goditjet. 

Kështu që ngre pyetjen, çfarë është Kostoja e bërë insertions dhe grisjeve në strukturën e të dhënave si kjo? E pra më lejoni të propozoj - dhe më lejoni të shkoj përsëri në ekran gjatë këtu - në qoftë se ne kemi n elementet në listë, kështu që në qoftë se ne jemi duke u përpjekur për të futur Elementet n, dhe ne kemi sa kova totale? Le të thonë se 31 kova totale ne rastin e ditëlindje. Çfarë është gjatësia maksimale e njërit prej këtyre zinxhirëve potencialisht? 

Nëse përsëri nuk ka mundur 31 ditëlindjet në një muaj të caktuar. Dhe ne jemi vetëm drejtim të grumbullimit të të gjithëve - në fakt kjo është një shembull budalla. Le të bëjmë në vend të 26. Pra, nëse në të vërtetë të ketë njerëz emrat e të cilëve fillojnë me A derinë Z, duke dhënë na 26 mundësitë. Dhe ne jemi duke përdorur një strukturë të dhënave si një ne vetëm e pa, ku kemi një grup i pointers, secila prej të cilave pikë për një listë të lidhura, ku të Lista e parë është e të gjithë me Alice Emri. Lista e dyta është me çdo përmendur duke filluar me A, duke filluar me B, dhe kështu me radhë. 

Çfarë është gjatësia e mundshme të secilit prej ato listat në qoftë se ne supozojmë një të pastër të bukur shpërndarja e emrave Një përmes Z nëpër gjithë strukturës të të dhënave? Ka njerëz n në strukturën e të dhënave pjesëtuar me 26, nëse ata janë të bukur të shtrirë mbi tërë Struktura e të dhënave. Pra, gjatësia e secilit prej këtyre Zinxhirët është n ndarë nga 26. Por në simbol Big O, çfarë është ajo? Çfarë është që me të vërtetë? Pra, kjo është me të vërtetë vetëm n, apo jo? Sepse ne kemi thënë në të kaluarën, që ohu ju ndani me 26. Po, në realitet ajo është më e shpejtë. Por në teori, kjo nuk është krejtësisht gjithçka që të shpejtë. 

Pra, ne nuk duket të jetë mbi të gjitha se shumë afër këtij Grail shenjtë. Në fakt, kjo është vetëm koha lineare. Heck, në këtë pikë, pse nuk e bëjmë ne përdorni vetëm një listë të madhe lidhur? Pse nuk e përdorni vetëm një i madh grup për të ruajtur emrat e të gjithë në dhomë? E pra, a ka ende diçka bindëse në lidhje me një tabelë hash? A ka ende diçka bindëse lidhje me strukturën e të dhënave që duket si kjo? Kjo. 

STUDENT: [padëgjueshme]. 

Kryetari 1: drejta, dhe përsëri në qoftë se ajo është vetëm nje algoritmi linear kohë, dhe nje Ora Struktura lineare dhënat, pse nuk kam vetëm për të ruajtur emrin e të gjithëve në një i madh array, ose në një listë të madhe lidhur? Dhe të ndaluar marrjen e CS aq shumë më të vështirë se ajo duhet të jetë? Çfarë është bindëse në lidhje me këtë, edhe pse unë gërvishtem atë? 

STUDENT: [padëgjueshme]. 

Kryetari 1: insertions nuk janë? Shtrenjtë anymore. Pra, insertions potencialisht mund të ende jetë koha konstante, edhe në qoftë se të dhënat tuaja Struktura duket si ky, një rrjet të Pointers, secila prej të cilave është e treguar në potencialisht një listë të lidhura. Si mund të keni arritur të vazhdueshme futje koha e emrave? Ngjit atë në para, e drejtë? 

Nëse ne sakrifikojmë një gol design nga më herët, ku ne të kërkuar për të mbajtur emri i të gjithëve, për shembull, të renditura, ose të gjithë numrat e renditura në skenë, mendoj se ne kemi një Lista unsorted lidhura. Ajo vetëm na kushton një ose dy hapa, si në rastin e Ben dhe Brian më herët, për të futur një element në fillimi i lista. Pra, nëse ne nuk e kujdesit për klasifikim të gjithë prej emrave të filluar me një ose të gjitha emrat që fillojnë me B, ne ende mund të arritur futje konstante në kohë. Tani duke kërkuar deri Alice apo Bob as kujtim më në përgjithësi është ende çfarë? Është i madh o n i ndarë nga 26, në rasti ideal ku gjithkush është uniforme shpërndahet, ku ka aq shumë një të si ka të Z, e cila është ndoshta joreale. Por kjo është ende lineare. 

Por këtu, kemi ardhur përsëri në pikën e simbol asymptotic qenë teorikisht e vërtetë. Por, në botën reale, në qoftë se unë pretendojnë se Programi im mund të bëjë diçka 26 herë më shpejt se sa tuajat, të cilit programi po ju do të preferoni duke përdorur? Juaji apo minave, i cili është 26 herë më të shpejtë? Realisht, personi të cilit është 26 herë më të shpejtë, madje edhe nëse teorikisht Algoritmet tona të kandidojë në të njëjtën asymptotic running kohë. 

Më lejoni të propozojë një tjetër zgjidhje krejt. Dhe në qoftë se kjo nuk do të fryj mendjen tuaj, ne jemi jashtë strukturave të të dhënave. Pra, kjo është një trie - lloj i një emër stupid. Ajo vjen nga retrievals, dhe fjala është shkruar trie, T-r-I-E, për shkak të rikthim kurs tingëllon si trie. Por kjo është historia i trie fjalë. 

Pra, një trie është me të vërtetë një lloj i pemës, dhe kjo është gjithashtu një lojë në atë fjalë. Dhe, edhe pse ju nuk mund të mjaft të shohin atë me këtë vizualizimi, nje trie eshte nje pemë e strukturuar, si një pemë familjare me një paraardhës në krye dhe shumë nga nipërit dhe nipërit e mbesat e mëdha si lë në pjesën e poshtme. Por çdo nyje ne nje trie eshte nje grup. Dhe kjo është në një rrjet - dhe le thjeshtëzoj për një çast - kjo është një grup, në këtë rast, të madhësisë 26, ku çdo nyje përsëri është një koleksion i madhësisë 26, ku 0 element në atë Grup përfaqëson A, dhe fundit element në çdo të tillë array përfaqëson Z. 

Kështu që unë propozoj, atëherë, që këto të dhëna struktura, i njohur si nje trie, mund të jenë përdoret gjithashtu për të ruajtur fjalët. Ne pamë një moment më parë se si ne mund të ruani fjalë, ose në këtë rast emrat, dhe ne pashë më herët se si ne mund të ruajë numrat, por në qoftë se ne të përqëndrohet në emra apo vargjet këtu, njoftim se çfarë është interesante. Pohoj se Maxëell Emri eshte brenda kësaj strukture të dhëna. Ku e shihni ju Maxwell? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Në të majtë. Pra, çfarë është interesante me këtyre të dhënave Struktura është më tepër se dyqan të string M-A-X-W-E-L-L backslash zero, të gjithë pranë njëri tjetrit, çfarë bëni ju në vend është duke ndjekur. Në qoftë se kjo është një trie si strukturën e të dhënave, secili prej nyjeve të cilit është përsëri një grup, dhe ju doni për të ruajtur Maxwell, ju së pari indeksi dhe kështu nyja rrënjë, prandaj të flasin, nyjen larti, at e lokacionit M, e drejtë, kështu që afërsisht në mes. Dhe pastaj nga atje, ju do të ndiqni një tregues për një nyje e fëmijëve, kështu që të flasin. Pra, në kuptimin pemë familjare, ju ndiqni atë në rënie. Dhe që t'ju çojë në një tjetër nyje nga e majta atje, e cila është vetëm një array. 

Dhe pastaj, nëse ju doni të ruajtur Maxwell, ju gjeni që përfaqëson treguesin A, i cili eshte ky nje here. Pastaj ju shkoni në nyjen e ardhshëm. Dhe vini re - kjo është arsyeja pse fotografia e një mashtruese pak - kjo nyje duken super vogël. Por për të drejtën e kjo është e Y dhe Z. Ajo është vetëm autori ka cunguar foto kështu që ju në të vërtetë shohin gjërat. Perndryshe kjo foto do të jetë jashtëzakonisht e gjerë. Deri tani ju e lokacionit indeksi në X, atëherë W, E Pastaj, pastaj L, atëherë L. Atëherë çfarë është ky kuriozitet? 

Epo, në qoftë se ne jemi duke përdorur këtë lloj të ri marrë mbi se si për të ruajtur një varg në një Struktura e të dhënave, ju ende nevojë për të thelb kontrolloni off në të dhënat e strukturë që një fjalë mbaron këtu. Me fjalë të tjera, secila prej këtyre nyjeve disi ka për të kujtuar se ne ndjekur në fakt të gjitha këto pointers dhe po largohen pak thërrime buke në fund këtu e kësaj strukturë për të treguar M-A-x-W-e-L-L është të vërtetë në këtë strukturë të dhëna. 

Pra, ne mund të bëjmë këtë si më poshtë. Secili prej nyjave në foto ne vetëm savs ka një, një grup të madhësisë 27. Dhe kjo është tani 27, sepse në gjashtë p vendosur, ne do të vërtetë të ju jap një apostrof, kështu që ne mund të kemi emra si O'Reilly dhe të tjerët me apostrofat. Por, të njëjtën ide. Secili prej këtyre elementeve në pikë rreshtuan për një struct nyje, kështu që vetëm një nyje. Pra, kjo është shumë e kujton e listës sonë të lidhura. 

Dhe atëherë unë kam një Boolean, të cilën unë do të telefononi fjalë, e cila është vetëm do të jetë e vërtetë në qoftë se një fjalë mbaron në këtë Nyja në pemë. Ajo përfaqëson në mënyrë efektive pak trekëndësh ne pamë një moment më parë. Pra, nëse një fjalë mbaron në atë nyje në pemë, që fusha e fjalës do të jetë e vërtetë, e cila është konceptualisht kontrolluar off, ose ne jemi tërhequr këtë trekëndësh, po ka është një fjalë ketu. 

Pra, kjo është një trie. Dhe tani pyetja është, çfarë është koha iken e saj? A është kjo e madhe O n? A është kjo diçka tjetër? E pra, në qoftë se ju keni n emra në këto të dhëna Struktura, Maxwell duke qenë vetëm një nga ata, çfarë është hera drejtimin e futur apo gjetjen Maxwell? Cila është koha running i futur Maxwell? Nëse ka emra të tjerë n tashmë në tryezë? Po? 

STUDENT: [padëgjueshme]. 

Kryetari 1: Po, kjo është gjatësia e emrit, e drejtë? Pra, M-a-x-W-e-l-l kështu ai ndjehet si kjo Algorithm është i madh o të shtatë. Tani, sigurisht, emri do të ndryshojnë në gjatësi. Ndoshta kjo është një emër të shkurtër. Ndoshta kjo është një emër më të gjatë. Por ajo që është kyç këtu është se kjo është një numër konstant. Dhe ndoshta kjo nuk është e vërtetë konstante, Por Perëndia, qoftë reale, në një , fjalor nuk ka ndoshta disa kufi në numrin e shkronjave në një Emri personi në një vend të veçantë. 

Dhe kështu që ne mund të supozojmë se Vlera është një konstante. Unë nuk e di se çfarë është ajo. Kjo është ndoshta më e madhe se ne mendojmë se është. Sepse ka gjithmonë disa qoshe rasti me një emër të çmendur të gjatë. Pra, le të thërrasë atë k, por ajo është ende një me sa duket konstant, sepse çdo përmendur në të botës, të paktën në një vend të veçantë, është se gjatësia ose të shkurtër, kështu që është konstante. Por, kur e kemi thënë diçka është e madhe O i një vlere konstante, çfarë është që me të vërtetë ekuivalente me? Kjo është me të vërtetë e njëjta gjë të ketë thënë kohë konstante. 

Tani ne jemi lloj i mashtrimit, e drejtë? Ne jemi lloj i leveraging disa teori këtu për të thënë se mirë, rendi i është k Urdhri i vërtetë vetëm një, dhe kjo është koha konstante. Por kjo është me të vërtetë. Sepse Insajt kyç këtu është se në qoftë se ne kemi n emra tashmë në këtë Struktura e të dhënave, dhe ne insert Maxwell, është sasia e kohës që na merr për të Maxwell futur fare prekur nga sa njerëzit e tjerë janë në strukturën e të dhënave? Nuk duket të jetë. Po të kisha një miliard elemente shumë për këtë trie, dhe pastaj futur Maxwell, është ai në të gjithë të prekur? Jo. Dhe kjo është ndryshe nga ndonjë prej të dhënave ditë Strukturat e kemi parë deri më tani, ku Ora drejtimin e algorithm tuaj është plotësisht i pavarur nga sa stuff është ose nuk është tashmë në atë strukturën e të dhënave. 

Dhe aq me teper qe kjo tani është një mundësi për të vendosur p gjashtë, e cila do përsëri të përfshijë zbatimin mesi juaj spell checker, duke lexuar në 150,000 fjalë të tjera, sa më të mirë për të ruajtur që nuk është domosdoshmërisht e qartë. Dhe pse unë kam aspiroi për të gjetur Grail shenjtë, unë nuk bëj pretendojnë se është një trie. Në fakt, një tabelë hash shumë mirë mund të të provojë të jetë shumë më efikase. Por ata janë vetëm - kjo është vetëm një nga vendimet e dizajnit ju do të keni për të bërë. 

Por në mbylljen e le të marrin 50 ose kështu sekonda për të marrë një vështrim në atë që qëndron përpara javën e ardhshme dhe më tej ne tranzicion nga kjo command line nëse botërore programe C për gjëra web bazuar dhe gjuhët si PHP dhe JavaScript dhe Interneti në vetvete, protokollet si HTTP, të cilat ju keni marrë për të dhënë për vite tani, dhe më të shtypur çdo ditë, ndoshta, apo shihet. Dhe ne do të fillojë të zhvishem përsëri Shtresat e çfarë është interneti. Dhe çfarë është kodi që nënvizon mjetet e sotme. Kështu 50 sekonda e këtij teaser këtu. Unë ju jap Warriors e neto. 

[Video playback] 

-Ai erdhi me një mesazh. Me një protokoll të gjithë të tijat. Ai erdhi për një botë të firewalls mizore, routers pakujdesshëm, dhe rreziqet larg keq se vdekja. Ai është i shpejtë. Ai është i fortë. Ai është TCPIP. Dhe ai e mori adresën tuaj. Warriors e neto. 

[VIDEO END rishikim] 

Kryetari 1: Kjo është se si interneti do të punojë si i javës së ardhshme.