[Tónlist spila] DAVID MALAN: Þetta er CS50. Og þetta er bæði byrjun og end-- eins literally-- næstum lok vikunnar sex. 

Ég hélt ég myndi deila svolítið um skemmtilegt staðreynd. Ég hef dregið þetta upp úr gögn Past önn er sett. Þú getur muna að við biðjum þig á hverjum p sett mynd ef þú hefur horft á netinu eða ef þú hefur sótt í eigin persónu. Og hér eru gögnin. Svo í dag var mjög mikill fyrirsjáanleg. En við vildum að eyða svolítið tíma með þér engu að síður. Ætti einhver vilja að álykta hvers vegna þetta línurit er svo jaggy, upp niður, upp niður, svo stöðugt? Hvað gera hvert toppa og dalir tákna? 

Áhorfendur: [inaudible] DAVID MALAN: Reyndar. Og meira skemmtilega, guð forði, við halda eina fyrirlestur á föstudegi í upphafi misseris, það er það sem við sjáum gerast. Svo í dag, taka þátt við í smá meira um uppbyggingu gagna. Og til að gefa þér meira af a solid andlegt líkan fyrir vandamál í fimm, sem er nú út. Stafsetningarvillur, þar sem, við munum afhenda þér textaskrá sumir 100.000 auk ensk orð og þú ert að fara að hafa að reikna út hvernig á að snjall hlaða þeim í minni, í RAM, með nokkur gögn uppbyggingu vali. 

Nú ein slík gögn uppbygging gæti vera, en sennilega ætti ekki að vera, jafnvel nokkuð einfalt tengd lista, sem við kynnt síðast. Og tengist lista hafði amk Einn kostur yfir fylki. Hvað er einn kostur af a tengda listanum öllum líkindum? 

Áhorfendur: ísetningu. 

DAVID MALAN: ísetningu. Hvað meinarðu með því? 

Áhorfendur: Anywhere eftir Listinn [inaudible]. 

DAVID MALAN: Good. Svo er hægt að setja inn stak þar sem þaà þú vilt í the miðja af the listi án þess að þurfa að stokka neitt, sem við lauk, í flokkun okkar umræður, er ekki endilega gott, því það tekur tíma til að raunverulega færa allar þessar menn til vinstri eða hægri. Og svo með tengda listanum, þú getur bara úthluta með malloc, ný hnút, og þá uppfæra nokkra pointers-- tveir, þrír aðgerðir max-- og við erum fær um að rifa einhvern í hvar í lista. 

Hvað annað var hagstæður um tengda listanum? Já? 

Áhorfendur: [inaudible] DAVID MALAN: Perfect. Perfect. Það er mjög breytilegt. Og að þú ert ekki að fremja, fyrirfram, að einhverju föstu stærð klumpur af minni, eins og þú vildi hafa til með fjölda vegar kosti sem er að þú getur tekið hnúta aðeins á eftirspurn þannig að nota aðeins eins mikið pláss eins og þú þarft í raun og veru. By mótsögn við fjölda, þú gætir óvart úthluta of lítið. Og þá er það bara að fara að vera með verk í hálsi að endurúthluta nýja stærri array, afrita allt yfir, losa gamla array, og fara svo um fyrirtækið þitt. Eða verra, gætir þú tekið hátt meira minni en þú þarft í raun og veru, og svo þú ert að fara að hafa mjög dreifður-byggð array, svo að segja. 

Svo tengd listi gefur þér þessar Kostir krafti og sveigjanleika með ísetningar og úrfellingum. En örugglega það verður að vera verð greitt. Í raun einn af þeim þemum kanna á spurningakeppni núll var par af málamiðlanir við höfum séð hingað til. Svo er það verð greitt eða hæðir á tengda listanum? Já. 

Áhorfendur: No handahófi aðgang. 

DAVID MALAN: No handahófi aðgang. En hver blíðuhót? Random aðgangur ekki hljóð sannfærandi. 

Áhorfendur: [inaudible] DAVID MALAN: Einmitt. Ef þú vilt hafa ákveðinn algorithm-- og láta mig leggja í raun Tvíundarleit einkum, sem er eitt sem við höfum notað nokkuð bit-- ef þú ert ekki af handahófi aðgang, þú getur ekki gert það einföld stærðfræði að finna eins miðju frumefni og stökk rétt við það. Þú hefur þess í stað að byrja á fyrsta frumefni og línulega leita frá vinstri til hægri ef þú vilt að finna miðju eða önnur frumefni. 

Áhorfendur: Það tekur sennilega meira minni. 

DAVID MALAN: Tekur meira minni. Hvar er þessi viðbótar kosta að koma frá í minni? 

Áhorfendur: [inaudible] DAVID MALAN: Einmitt. Í þessu tilfelli hér, við höfðum a tengda listanum fyrir heiltölur, og enn erum við tvöföldun fjárhæð minni þurfum við einnig að geyma þessum ábendingum. Nú minna af a stór samningur sem structs þínir fá stærri og þú ert að geyma ekki tala en kannski nemandi eða einhver annar hlutur. En punkturinn er vissulega. Og svo a tala af starfsemi á tengdum listum voru kallaðir voru stór O í N- línuleg. Hluti eins ísetningu eða leit eða eyða ef stak varð að vera aftast á Listinn hvort sem það er flokkað eða ekki. 

Stundum þú might fá heppinn og svo lægri mörk á þessum aðgerðum gæti líka verið stöðug tími ef þú ert alltaf að horfa á fyrstu frumefni, til dæmis. En að lokum, lofaði við að ná Gral gögn mannvirki, eða sumir nálgun þess, með því föstu tíma. Getum við fundið þætti eða bæta þætti eða fjarlægja atriði úr lista? Við skulum sjá alveg fljótlega. Og það kemur í ljós að einn á ferli sem við erum að fara að byrja að nota í dag, árleg notkun í p setja fimm, er reyndar nokkuð kunnuglegt. Fyrir dæmi, ef þetta er fullt af exam bókum, sem hver um sig hefur nemandi fyrst Nafn og eftirnafn á það, og ég ná þeim upp úr í lok prófi og þeir eru allir frekar mikið í handahófi og við viljum að fara um flokkun þessum prófum þannig að þegar farið það er bara mikið auðveldara og hraðar til hendinni þá aftur út nemendum í stafrófsröð. Hvað myndi eðlishvöt yðar séu fyrir haug af prófum eins og þetta? 

Jæja, ef þú ert eins og mig, þú gæti séð að þetta er m, þannig að ég ætla að raða í setja þetta inn, ef þetta er mitt borð eða gólf minn þar Ég er að breiða það out-- eða array minn really-- Ég gæti sett alla MS þar. Oh. Hér er A. Svo ég gæti setja As hérna. Oh. Hér er önnur A. Ég ætla að setja það hérna. Hér er a Z. Hér er annar M. Og svo Ég gæti byrjað að gera hrúgur svona. Og þá kannski myndi ég fara í síðar og svoleiðis mjög nitpicky-Ly konar einstök hrúgur. En punkturinn er að ég myndi líta á inntak að ég er hönd og ég myndi gera sumir reiknað ákvörðun byggist á þeirri inntak. Ef það byrjar með A, setja það þarna. Ef það byrjar með Z, setja það yfir þar, og allt þar á milli. 

Þannig að þetta er tækni sem er almennt þekktur sem hashing-- H-A-S-H-- sem yfirleitt þýðir að taka eins inntak og nota þessi inntak að reikna gildi, yfirleitt tala, og að talan er vísitalan í geymslu gámur, eins fylki. Svo í öðrum orðum, gæti ég hafa kjötkássa virka, eins og ég geri í höfðinu á mér, að ef ég sé einhver er nafn sem byrjar á A, Ég ætla að kortleggja það að núll í höfðinu á mér. Og ef ég sé einhvern með Z, ég er fara að kortleggja þessi til 25 í höfðinu á mér og þá setja það inn í síðasta mest stafli. 

Nú, ef þú hugsa um ekki heilinn minn en C program, hvaða tölur gætu þú treyst á að ná þessu sömu niðurstöðu? Með öðrum orðum, ef þú hafði ASCII staf A, hvernig ákveða hvað fötu til að setja það í? Þú vilt sennilega ekki að setja það inn fötu 65, sem myndi vera eins þarna fyrir neitun góður ástæða. Hvar viltu setja hvað varðar ASCII gildi þess? Hvar viltu gera til ASCII hennar gildi til að koma upp með a snjallari skóflu að setja það í? 

Áhorfendur: Minus A. 

DAVID MALAN: Já. Svo mínus A eða mínus sérstaklega 65 ef það er höfuðborg A. Or 98 ef það er lágstafir a. Og svo sem myndi gera okkur kleift að, mjög einfaldlega og mjög arithmetically, setja eitthvað í fötu eins og þessi. Svo kemur í ljós við gerum í raun þetta eins vel, jafnvel með Skyndipróf. 

Svo þú gætir muna að þú hring þinn Nafn Kennslu náungi er á forsíðu. Og nöfn TF voru skipulögð í þessum dálkum í stafrófsröð, Jæja, þá trúið því eða ekki, þegar öll 80 plús okkur komu saman um daginn til bekk, síðasta skrefið í einkunnakerfi ferli okkar er að kjötkássa á Skyndipróf í stór rými hæð í [inaudible] og að leggja Skyndipróf allra út í nákvæmlega röð TF sinna nöfn á lokinu, Vegna þá er það mun auðveldara fyrir okkur að leita í gegnum það að nota línulega leita eða einhvers konar bragðvísi fyrir TF að finna hans eða Skyndipróf nemenda sinna. 

Þannig þessi hugmynd um hass að þú munt sjá er alveg öflugur er í raun nokkuð hversdagsleg og mjög leiðandi, líkt kannski skipta og Conquer var í viku núll. I Fljótur Áfram til hackathon a par af ár síðan. Þetta var Zamyla og a par af aðrir nemendur starfsfólk kveðja eins og þeir komu inn. Og við höfðum a heild búnt af leggja saman borðið með nafni tags. Og héldum merkjum skipulögð með eins og yfir það og ZS þarna. Og svo einn af TFS mjög snjall skrifaði þetta sem leiðbeiningar fyrir daginn. Og í 12. viku annarinnar þessa allt gert fullkominn skilningarvit og alla vissi hvað ég á að gera. En hvenær sem þú hef bið á sama hátt, þú ert að innleiða Sama hugmynd um kjötkássa. Svo skulum móta það svolítið. Hér er fylki. Það er vakin á að vera svolítið breiður bara að sýna, sjónrænt, að við gætum sett strengi í eitthvað eins og þetta. Og þetta fylki er augljóslega stærð 26. samtals. Og málið er kallað Tafla geðþótta. En þetta er bara flutningur flytjanda um hvað kjötkássa borð væri. 

Svo kjötkássa borð nú er að fara að vera hærra stigi gagnagrind. Í lok dagsins við erum að fara að sjá að þú getur innleiða kjötkássa borð, sem er mikill eins og innritun í línu á hackathon mikið eins og þetta Tafla notað fyrir flokkun exam bækur. En kjötkássa borð er Raða þessa háu stigi hugtak sem gæti nota array undir hetta til að framkvæma það, eða það væri hægt að nota lengd lista, eða jafnvel kannski nokkrar aðrar gögn uppbygging. Og nú er að theme-- taka sumir af þessum grundvallar innihaldsefni eins fjölda og þessari byggingu loka nú að lengd lista og sjá hvað við getum byggt ofan á þeim, eins og innihaldsefni í uppskrift, gera meira og meira áhugaverðar og gagnlegar endanlegar niðurstöður. 

Svo með kjötkássa borð við gætum framkvæma það í minni myndrænan svona, en hvernig gæti það í raun vera á dulmáli upp? Jæja, kannski er eins einfaldlega þetta. Ef getu á öllum húfur, er bara sumir constant-- til dæmis 26, í 26 bókstafir alphabet-- Ég gæti hringt breytilega mitt borð, og ég gæti haldið því fram að ég ætla að setja char stjörnur í það, eða band. Svo það er eins einfalt eins og þetta ef þú vilja innleiða kjötkássa töflunni. Og enn, þetta er í raun bara fylki. En aftur, tæti borð er nú það sem við munum kalla fræðilega gögn gerð sem er bara konar huglægu layering ofan um eitthvað meira mundane nú eins fylki. 

Nú, hvernig eigum við að fara um að leysa vandamál? Jæja, áðan hafði lúxus af því að hafa nóg borð pláss hér þannig að ég gæti sett Skyndipróf hvar ég vildi. Svo eins gæti farið hér. Zs gæti farið hér. Ms gæti farið hér. Og svo ég hafði smá auka pláss. En þetta er hluti af a svindla hægri nú vegna þess að þetta borð, ef ég virkilega hugsaði um það sem fylki, er bara fara að vera eitthvað fast stærð. 

Svo tæknilega, ef ég toga upp spurningakeppni annars nemandans og sjá, ó, þessi manneskja er nafn byrjar með A líka, Ég vil konar að setja það þar. En um leið og ég setti hana þar, ef Þessi tafla sýnir örugglega fylki, Ég ætla að vera hnekkir eða clobbering sá quiz þessa nemanda er. Hægri? Ef þetta er fylki, aðeins eitt getur fara í hvert af þessum frumum eða þætti. Og svo ég hef svona að velja og velja. 

Nú áðan konar sviknir og gerðu þetta eða I bara svona staflað þá er hér að ofan hvert annað. En það er ekki að fara að fljúga í kóða. Svo gæti ég setti annað nemandi hét er A ef allt sem ég þurfti er þetta boði borð pláss? Og ég hef notað þrjár rifa og það lítur út eins og það er bara nokkrum öðrum. Hvað gætir þú gert? Áhorfendur: [inaudible] DAVID MALAN: Já. Kannski skulum halda bara það einfalt. Hægri? Það passar ekki þar sem ég vil að setja það. Þannig að ég ætla að setja það tæknilega þar sem B myndi fara. Nú, auðvitað, ég byrja að mála mig út í horn. Ef ég fæ að nemandi en nafn er í raun B, nú B er að fara að vera flutt smá áfram, sem gæti gerzt, Já, ef þetta er B, nú hefur það að fara hér. 

Og svo þetta mjög fljótt gæti orðið erfið, en það er tækni sem raunverulega er vísað til sem línuleg leit, þar sem þú telur bara þín array að vera meðfram línu. Og þú bara svona rannsaka eða skoða hvert laus frumefni leita laust staðnum. Og um leið og þú finnur einn, falla þér það þar. 

Nú, en verðið er greitt núna fyrir þessa lausn er það? Við erum með fasta stærð array, og þegar ég setja nöfn inn í það, að minnsta kosti í upphafi, hvað er Keyrslutíminn ísetningar fyrir að setja stúdent Skyndipróf í rétta fötu? Big O hvað? 

Áhorfendur: n. DAVID MALAN: Ég heyrði stór O á n. Ekki satt. En við munum stríða sundur hvers vegna í aðeins augnablik. Hvað annað gæti það verið? 

Áhorfendur: [inaudible] DAVID MALAN: Og láta mig gera það sjónrænt. Svo Segjum þetta er bókstafurinn S. 

Áhorfendur: Það er eitt. DAVID MALAN: Það er eitt. Hægri? Þetta er fylki, sem þýðir að við höfum handahófi aðgang. Og ef við hugsum um þetta núll og þetta sem 25, og við skiljum að, ó, hér er inntak S mitt, Ég get vissulega umbreyta S, sem ASCII staf, til samsvarandi fjölda milli núll og 25 og þá strax setja það þar sem það tilheyrir. 

En auðvitað, um leið og ég kem á annar maður, sem er nafn er A eða B eða C lokum, ef ég hef notað línuleg leit og lausnin mín, Keyrslutíminn af innsetning í versta tilfelli er í raun að fara að flytjast í það? Og ég gerði heyra það hér rétt snemma. Áhorfendur: [inaudible] DAVID MALAN: Svo það er n örugglega einu þú ert nægilega stór gögn sett. Svo, annars vegar, ef array er nógu stór og gögn er dreifður nóg, þú fá þessa fallegu stöðugt sinn. En um leið og þú byrjar að fá fleiri og fleiri þætti, og bara tölfræðilega þú færð fleiri einstaklingar með bréfi A eins og nafn þeirra eða bréf B, gæti það hugsanlega flytjast í fúlustu línuleg. Svo ekki alveg fullkominn. Svo gætum við gert betur? 

Jæja, hvað var okkar lausn fyrir þegar við langar að hafa meiri kraft en eitthvað eins og array leyft? Áhorfendur: [inaudible] DAVID MALAN: Hvað gerði við kynna? Já. Svo tengd lista. Jæja, við skulum sjá hvað tengdur listi gæti gert fyrir okkur í staðinn. Jæja, láttu mig leggja til að vér teikna myndina sem hér segir. Nú er þetta öðruvísi mynd frá dæmi frá mismunandi texta, reyndar, að er í raun að nota fjölbreytta stærð 31. Og þessi höfundur einfaldlega ákvað að kjötkássa strengi ekki byggð á nöfn viðkomandi, en byggt á birthdates sínum. Óháð mánaðarins, mynstrağur þeir Ef þú ert fæddur á fyrsta mánuði eða 31. mánuð, höfundur mun kjötkássa við þann verðmæti, svo sem til að dreifa nöfnum út smá meira en bara 26 blettur gæti leyfa. Og kannski er það svolítið jafnari en að fara með stafrófsröð bréf, því að sjálfsögðu að það er sennilega fleiri fólk í heiminum með nöfn að byrja með A en vissulega nokkrar aðrar bókstafir. Svo kannski er þetta svolítið jafnari, miðað jafnri dreifingu barna yfir mánuð. 

En, auðvitað, þetta er enn ófullkomin. Hægri? Við erum með árekstra. Margfeldi fólk í þessu gagnagrind eru enn með sama fæðingardag að minnsta kosti þú ert óháð mánuði. En hvað hefur höfundur gert? Jæja, það lítur út eins og við höfum fjölda á vinstri hönd hlið dregin lóðrétt, en það er bara flutningur flytjanda. Það skiptir ekki máli hvað átt þú draga fylki, það er samt array. Hvað er þetta fylki af virðist? 

Áhorfendur: tengda listanum. 

DAVID MALAN: Já. Það lítur út eins og það er array af tengda listanum. Svo aftur, að þessum tímapunkti af tagi að nota þessi gögn uppbygging nú sem hráefni til fleiri áhugaverðar lausnir, þú getur alveg tekið grundvallaratriði, eins og fjölda, og þá taka eitthvað meira áhugavert eins tengda listanum og jafnvel sameina þær í enn áhugaverðari gagnagrind. Og reyndar, þetta of myndi vera kölluð kjötkássa borð, þar sem array er virkilega kjötkássa borð, en það kjötkássa borð hefur keðjur, svo að segja, sem geta vaxið eða skreppa byggt á fjöldi staka sem þú vilt setja inn. 

Nú, í samræmi við það, hvað er Keyrslutíminn núna? Ef ég vil setja einhvern sem afmæli er 31. október, hvar hann eða hún að fara? Allt í lagi. Á mjög botn þar sem það segir 31. Og það er fullkominn. Það var stöðug skipti. En hvað ef við finnum einhvern annan sem afmæli er, við skulum sjá, Október, nóvember, desember 31? Hvar er hann eða hún að fara? Sami hlutur. Tvö skref þó. Það er stöðug þó er það ekki? Allt í lagi. Á því augnabliki sem það er. En í almennu tilfelli, fleira fólk við að bæta við, probabilistically, ætlum við að fara að fá fleiri og fleiri árekstrar. 

Nú er þetta svolítið betra því tæknilega nú keðjur mín gæti verið í versta hversu lengi? Ef ég set inn n fólk í þetta meira háþróuð gagnagrind, n fólk, í versta tilfelli það er að fara að vera n. Hvers vegna? 

Áhorfendur: Vegna þess að ef allir hefur sömu afmæli, þeir eru að fara að vera ein lína. DAVID MALAN: Perfect. Það gæti verið svolítið háttuð, en sannarlega í versta tilfelli, ef allir eru með sama afmæli, ljósi inntak sem þú hefur, þú ert að fara að hafa a gegnheill löng keðja. Og svo, þú kalla það kjötkássa borð, en í raun er það bara gegnheill tengda listanum með a heild einhver fjöldi af sóa pláss. En almennt, ef við gerum ráð fyrir að amk afmælisdagar eru uniform-- og það er sennilega ekki. Ég er að gera það upp. En ef við gerum ráð fyrir, að sakir umræðu að þeir eru, þá í orði, ef þetta er lóðrétt framsetning í fylkinu, og þá vonandi þú ert fara að fá keðjur sem eru, þú veist, um það bil sama lengd þar sem hver af þessarra dagur mánaðarins. 

Nú ef það er 31 dagar í mánuðinum, sem þýðir hlaupandi tíma minn raunverulega er stór O n yfir 31, sem finnst betra en línuleg. En hvað var einn af okkar skuldbindingar a par af vika síðan þegar það kom til að tjá Keyrslutíminn af reiknirit? Bara aðeins að líta á öfluga tíma. Hægri? 31 er örugglega gagnlegt. En þetta er samt stór O á n. En einn af þeim þemum af Heimadæmi fimm er að fara að vera að viðurkenna að algerlega, aðfellu, fræðilega þessi gögn uppbygging er ekki betri en bara einn gegnheill tengda listanum. Og reyndar, í versta tilfelli, þetta kjötkássa borð gæti flytjast inn í það. 

En í hinum raunverulega heimi, með okkur menn að eigin Macs eða tölvur eða hvað og eru í gangi raunverulega heimi hugbúnaður á alvöru World Data, sem reiknirit ætlar þú að kjósa? Sá sem tekur enda sporin eða einn sem tekur n deilt með 31. skrefum að finna einhverja stykki af gögnum eða að líta upp einhverjar upplýsingar? Ég meina, endilega 31 gerðum munur á hinum raunverulega heimi. Það er 31 sinnum hraðar. Og við mennirnir eru vissulega fara að þakka það. 

Svo átta sig á slag þar á milli í raun tala um hluti fræðilega og aðfellu sem vissulega hefur gildi eins og við höfum séð, en í hinum raunverulega heimi, Ef þér þykir vænt um bara gera manna ánægður fyrir almenna inntak, þú might mjög vel vilja til að samþykkja Sú staðreynd að, já, þetta er línuleg, en það er 31 sinnum hraðar en línulegur væri. Og enn betra, við ekki bara að gera eitthvað handahófskennt eins afmælisdeginum, við gætum eytt smá meiri tíma og slungin og hugsa um hvað við gætum gert, gefið nafn einstaklingsins og kannski fæðingardegi þeirra að sameina þá efni til að reikna út eitthvað sem er sannarlega meira samræmda og minna jaggy, svo að segja en þessa mynd nú bendir það gæti verið. Hvernig gætum við innleiða þetta í kóða? Jæja, láttu mig leggja til að vér bara láni sumir setningafræði við höfum notað nokkrum sinnum hingað til. Og ég ætla að skilgreina hnút, sem aftur er almenn orð fyrir bara gámur fyrir sumir gögn uppbygging. Ég ætla að leggja til að a band er að fara í það. En við erum að fara að byrja að taka þá þjálfun hjól burt núna. 

Ekkert meira CS50 bókasafn raun, nema þú viljir að nota það til endanlegrar þína Verkefnið, sem er fínn, en nú erum við að fara að draga til baka fortjald og segja að það er bara bleikju stjarna. Þannig að orði að það sé að fara að nafn viðkomandi ræðir. Og nú hef ég tengil hér í næsta hnút þannig að þetta tákna hver af tengipunkta í keðjunni, hugsanlega, af tengdum lista. 

Og nú hvernig ég lýsa kjötkássa borð sjálft? Hvernig get ég lýsa alla þessa múra? Jæja, í raun, eins og ég notaði músina við bara fyrsta þáttur lista áður, á sama hátt get ég sagt bara Ég þarf bara fullt af ábendingum að framkvæma þetta allt kjötkássa töflunni. Ég ætla að hafa array kallað borð fyrir kjötkássa borð. Það er að fara að vera af stærð getu. Það er hversu margir þættir geta passa í það. Og hver af þeim þáttum í þessari array er að fara til vera a hnút stjarna. Hvers vegna? Jæja, og á þessari mynd, það sem ég er framkvæmd kjötkássa borð eins raun í byrjun er bara Fylkið sem við höfum dregið lóðrétt, hvert sem ferninga táknar bendi. Að þau sem hafa skástrik gegnum þá eru bara null. Og þau sem hafa Örvar að fara til hægri eru raunveruleg ábendingum að raunverulegum hnúður, Ergo upphaf tengda listanum. 

Svo hér, þá er, hvernig við gætum innleiða kjötkássa töflu sem útfærir aðskilda chaining. Nú getum við gert betur? Allt í lagi ég lofaði síðasta skipti sem við gætum náð föstu tíma. Og ég konar gaf þér föstu tíma hér, en þá sagði í raun ekki föstu tíma því það er enn háð allra fjöldi staka þú ert inputting inn gögn uppbygging. En geri ráð fyrir að við gerðum þetta. Leyfðu mér að fara aftur á skjáinn hérna. Leyfðu mér einnig verkefni þessu upp hér, tær skjáinn og býst ég gerði þetta. Segjum að ég vildi setja nafn Daven í inn gögn uppbygging minn. 

Þannig að ég vil að setja band Daven í gagnagrind. Hvað ef ég nota ekki kjötkássa borð, en ég nota eitthvað sem er meira tré-eins eins ættartré, þar þið hafið einhverjar rót á hafið efst og þá hnúður og blöð að fara niður og út á við. Segjum svo, að ég langar að setja inn Daven er í hvað er nú tómt listi. Ég ætla að gera eftirfarandi: Ég er fara að búa til hnút í þessari fjölskyldu tré-eins og gögn uppbygging sem lítur svolítið eins og þetta, sem hver um sig ferhyrninga hefur, segjum, Fyrir nú 26 þættir í henni. Og hver af frumunum í þessu fylki er að fara að tákna stafinn af stafrófinu. 

Sérstaklega, ég er að fara að meðhöndla þetta er A, þá B, þá C, þá D, þetta hér. Þannig að þetta er að fara að í raun tákna stafinn D. En að setja alla Daven er nafn ég þarf að gera aðeins meira. Þannig að ég ætla fyrst að fara til kjötkássa, svo að segja. Ég ætla að horfa á fyrsta staf í Daven, sem er augljóslega D, og ég ætla að úthluta hnút sem lítur eins this-- stórt rétthyrning stór nóg að passa allt stafrófið. 

Nú D er gert. Nú er A. D-A-V-E-N markmiðið. Svo nú hvað ég ætla að gera er þetta. Um leið og ég byrjaði D tilkynningu það er engin bendi þar. Það er sorp gildi um þessar mundir, eða ég gæti frumstilla það að núll. En láta mig halda áfram með þessi hugmynd um að byggja upp tré. Leyfðu mér að úthluta annað af þessum hnúður sem eru 26 einingar í henni. 

Og þú veist hvað? Ef þetta er bara hnútur í minni sem Ég búin með malloc, með strúktúr eins og við munum fljótlega sjá, Ég ætla að gera this-- Ég ætla að draga ör úr hlutur sem fulltrúi D niður þessa nýju hnút. Og nú, fyrst næst stafurinn í nafni Daven er, V-- D-A-V-- ég ætla að fara á undan og draga annað hnút eins og þetta, þar, V þætti hér, sem við munum draga fyrir instance-- Úpps. Við munum ekki draga það. Það er að fara að fara hér. 

Svo ætlum við að telja þetta vera V. Og svo niður hér við erum að fara að kemba niður úr V í það sem við munum íhuga E. Og síðan frá hér við erum að fara að fara hafa einn af þessum hnúður hér. Og nú erum við með spurningu til að svara. Ég þarf einhvern veginn til kynna að við erum í lok band Daven. Svo ég gæti bara láta það null. 

En hvað ef við höfum Daven er fullt nafn líka, sem er, eins og við höfum sagt, Davenport? Svo hvað ef Daven er raun hlutstreng, Forskeyti af miklu lengri streng? Við getum ekki bara varanlega segja ekkert er að fara að fara þangað, vegna þess að við gátum aldrei að setja inn orð eins Davenport í þessum gögnum uppbyggingu 

Svo það sem við gætum gert er í staðinn meðhöndla hvert þessara þátta eins kannski að hafa tvö þættir innra með þeim. Eitt er bendillinn, örugglega, eins og ég hef verið að gera. Svo hver af þessum kassa er ekki bara einn klefi. En hvað ef efst one-- botn einn er fara að vera núll, því það er engin Davenport bara ennþá. Hvað ef efst einn er einhver sérstakur gildi? Og það er að fara til vera a lítill erfitt að draga það þessari stærð. En geri ráð fyrir að það er bara merkið. Athuga. D-A-V-E-N er band í þessum gögnum uppbyggingu. 

Sama tíma, ef ég hefði meira pláss hér, gæti ég gert P-O-R-T, og ég gæti sett stöðva í hnút sem hefur stafinn T aftast. Þannig að þetta er gegnheill flókin-útlit gögn uppbygging. Og rithönd mín vissulega ekki hjálpa. En ef ég vildi setja eitthvað annað, íhuga hvað við myndum gera. Ef við vildum að setja Davíð í, viljum við fylgja sömu rökfræði, D-A-V, en nú ég myndi benda á næsta þáttur ekki frá E, en frá I til D. Þannig að það er að fara að vera fleiri hnútar í þessu tré. Við ætlum að hafa hringt malloc meira. En ég vil ekki að gera a Heill skipta um þessa mynd. Svo skulum staðinn líta á einn sem hefur verið fyrirfram mótuð svona með ekki punktur, punktur, punktar, en bara skammstafanir fylki. En hver af hnúður í þessu tré upp hér táknar sömu thing-- fylki Ray stærð 26. 

Eða ef við viljum vera virkilega réttur nú, hvað ef nafn einhvers sem úrfellingarmerki, skulum gera ráð fyrir að hver hnútur hefur í raun eins 27 Vísitölur í henni, ekki bara 26. Þannig að þetta nú er að fara til vera a gögn uppbygging kallast trie-- T-R-I-E. A trie, sem er talið sögulega snjall nafn fyrir tré sem er bjartsýni fyrir sókn, sem að sjálfsögðu, er stafsett með I-E svo það er trie. En það er saga af trie. 

Svo er a trie Þetta tré-eins og gögn uppbyggingu eins ættartré að lokum hegðar sér eins og þessi. Og hér er bara annað dæmi um a allt fullt af nöfnum annarra. En spurningin núna hendi er hvað hefur við fengið með því að kynna öllum líkindum meira flókið gagnagrind, og einn, hreinskilnislega, sem notar mikið minni. 

Því jafnvel þó, í augnablikinu, ég er bara nota D's músina og A og V og Es og Ns, Ég er að sóa Heck fullt af minni. En þar sem ég eyða eitt úrræði, ÉG hafa tilhneigingu til að gera ná til baka annað. Svo ef ég ætla að eyða meira pláss, hvað er líklega von? Að ég er að eyða minna það? Áhorfendur: Minni tíma. DAVID MALAN: Time. Nú hvers vegna gæti það verið? Jæja, hvað er innsetning tíma, í skilmálar af stór O nú, um nafn eins Daven eða Davenport eða David? Jæja, Daven var fimm skrefum. Davenport væri níu skref, svo það væri nokkur atriði. David yrði fimm spöl. Þannig að þeir eru steypu tölur, en örugglega er það skilgreina efri mörk á lengd nafni einhvers. Og reyndar, í því vandamáli sett af fimm forskrift, við erum að fara að leggja að það er eitthvað það er 40-sumir-stakur persónur. 

Raunhæft, enginn hefur óendanlega lengi nafn, sem er að segja að lengd a nafn eða lengd streng við gæti hafa viss ástand uppbygging er að öllum líkindum hvað? Það er stöðug. Hægri? Það gæti verið stór fasti eins 40-eitthvað, en það er stöðug. Og það hefur engin ánauðar á hversu margar önnur nöfn eru í þessum gögnum uppbyggingu. Með öðrum orðum, ef I vildi nú setja Colton eða Gabriel eða Rob eða Zamyla eða Alison eða Belinda eða einhver önnur nöfn frá starfsfólki í þessum gögnum uppbygging, er í gangi tími að setja önnur nöfn að fara að vera á öllum áhrifum því hversu mörgum öðrum þáttum eru í gögn uppbygging þegar? Það er ekki. Hægri? Vegna þess að við erum í raun að nota þetta multi-lag kjötkássa töflunni. Og gangi tími eitthvað af þessum aðgerðum er háð ekki á fjölda þættir sem eru í gögn uppbygging eða sem eru loksins að fara að vera í gögn uppbygging, en á lengd hvað sérstaklega? 

Strengurinn vera sett, sem gerir þetta aðfellu fasti time-- stór O einn. Og hreinskilnislega, bara í hinum raunverulega heimi, þetta þýðir að setja nafn Daven tekur eins og fimm skref, eða Davenport níu skref, eða David fimm skrefum. Það er laglegur fjári lítil gangi sinnum. Og reyndar, það er mjög gott, sérstaklega þegar það er ekki háð allra fjöldi staka í þar. Svo hvernig gæti við innleiða þetta konar uppbyggingu í kóða? Það er a lítill fleiri flókið, en samt er það bara beitingu undirstöðu kubbar. Ég ætla að endurskilgreina US hnút eins og hér segir: bool kallaði word-- og þetta mætti ​​nefna neitt. En bool táknar það sem ég dró sem hakað. Já. Þetta er í lok streng í þessum gögnum uppbyggingu. 

Og, auðvitað, hnúturinn stjörnu það er að vísa til barna. Og reyndar rétt eins fjölskyldu tré, þú myndi íhuga hnúður sem eru hangandi burt af the botn af einhverjum foreldri þáttur til að vera börn. Og svo börnin er að fara að vera fylki af 27, 27 einn bara að vera fyrir úrfellingarmerki. Við erum að fara að raða sérstakt tilfelli að. Svo þú getur haft viss nöfn með úrfellingarmerki. Kannski jafnvel bandstrik ættu fara í það, en þú munt sjá í p sett 5. við aðeins umönnun um bréfum og úrfellingarmerki. 

Og þá hvernig þú ert í forsvari gögnin uppbyggingu sig? Hvernig gera þú tákna rót þessarar trie, svo að segja? Jæja, bara eins og með tengda listanum, þú þurfa bendi á fyrstu frumefni. Með trie þú þarft bara einn bendi á rót þessa trie. Og þaðan sem þú getur kjötkássa leið niður dýpra og dýpra að öll önnur hnút í uppbyggingu. Svo einfaldlega með þetta getur að tákna að strúktúr. 

Nú Meanwhile-- Oh, spurningu. 

Áhorfendur: Hvað er bool orð? 

DAVID MALAN: Bool orð er bara þetta C holdgun af því sem ég lýsti í þessum kassa hér, þegar Ég byrjaði að skipta hvert af þættir í tveimur stykki Array er. Eitt er bendillinn í næsta hnút. The annar þarf að vera eitthvað eins og kassann að segja já, það er a Orðið Daven sem endar hér, vegna þess að við viljum ekki, Á því augnabliki, Dave. 

Jafnvel þótt Dave er að fara til vera a lögmæt orð, hann er ekki í trie enn. Og D er ekki orð. Og D-A er ekki orð eða nafn. Þannig að hakað sýnir aðeins einu sinni þig högg þessi hnútur er Fyrri slóð af stöfum raun band sem þú hefur sett inn. Svo er það allt bool það er að gera fyrir okkur. 

Allar aðrar spurningar um reynir? Já. 

Áhorfendur: Hvað er skarast? Hvað ef þú ert með Dave og Daven? DAVID MALAN: Perfect. Hvað ef þú ert með Dave og Daven? Þannig að ef við setja, segja gælunafni fyrir David-- Dave-- D-A-V-E? Þetta er í raun frábær einfalt. Þannig að við erum bara að fara að taka fjögur skref. D-A-V-E. Og hvað þarf ég að gera þegar ég lenti sem fjórða hnút? Bara að fara til að athuga. Við erum nú þegar gott að fara. Lokið. Fjögur skref. Constant tími aðfellu. Og nú höfum við til kynna að bæði Dave og Daven eru strengir á skipulagi. Svo ekki vandamál. Og taka eftir hvernig tilvist af Daven ekki gera það taka allir meiri tíma eða minna tími fyrir Dave og öfugt. 

Svo hvað annað getum við gert núna? Við höfum notað þessa samlíking áður bakka fulltrúi eitthvað. En það kemur í ljós að stafla af stæði er í raun sýnileg annars abstrakt gögnum type-- hærra stigi gögn uppbygging að í lok daginn er bara eins fjölda eða tengdan lista eða eitthvað meira mundane. En það er meira áhugavert hugmyndafræðilegs hugtak. A stafla, eins og þessir Bakkar hér í Mather, eru yfirleitt kallaðir bara that-- stafla. 

Og í þessari tegund af gögn uppbygging þú hefur tvær operations-- þú ert einn sem heitir ýta bæta eitthvað að stafla, eins og að setja annan bakka aftur á toppur af stafla. Og þá skjóta, sem þýðir að þú taka hæstur bakki burt. En hvað er lykillinn um stafla er að það er got this forvitinn eiginleika. Eins matsalur starfsfólk eru endurskipuleggja stæði fyrir næsta máltíð, hvað er að fara að vera satt um hvernig nemendur samskipti við þessum gögnum uppbyggingu? Áhorfendur: Þeir eru að fara að skjóta einn burt. DAVID MALAN: Hann ætlar að skjóta einn burt, vonandi á toppinn. Annars er það bara svona heimskur að fara alla leið til botns. Hægri? Gögnin uppbygging er í raun ekki að leyfa þér að grípa botn bakki amk auðveldlega. Svo er það þetta forvitinn eign til stafla að síðasta atriði í er fara til vera the fyrstur einn út. Og tölva vísindamenn kalla þetta LIFO-- varað í, fyrst út. Og það í raun er að hafa áhugavert forrit. Það er ekki endilega eins augljóst eins og sumir aðrir, en það getur reyndar verið gagnlegt, og það getur reyndar verið útfærð í nokkra mismunandi vegu. 

Svo einn, og í raun, láta mér ekki að kafa inn í það. Við skulum gera þetta í staðinn. Við skulum líta á eitt sem er nánast Sama hugmynd, en það er a lítill sanngjarnari. Hægri? Ef þú ert einn af þessum aðdáandi drengja eða stelpur sem raunverulega finnst Apple vörur og þú vaknaðir í 03:00 að stilla upp á einhverjum verslun að fá mjög nýjustu iPhone, þú gæti hafa bið svona. 

Nú biðröð er mjög vísvitandi heitir. Það er lína vegna þess að það er sumir sanngirni við það. Hægri? Það myndi konar sogast ef þú hefur fékk það fyrst á Apple Store en þú ert í raun að bottommost bakki vegna Apple starfsmenn þá skjóta síðasta manneskja sem reyndar fékk í línu. Svo stöflum og biðröðum, jafnvel þó virkni þeir eru eiginlega same-- það er bara þetta safn auðlinda sem er að fara að vaxa og shrink-- there ' þessi sanngirni þáttur að það, að minnsta kosti í hinum raunverulega heimi, þar sem aðgerðir sem þú hreyfir eru í grundvallaratriðum ólík. A stack-- biðröð rather-- er sagður hafa tvær aðgerðir: n biðröð og d biðröð. Eða þú getur hringt í þá allir tala um hlutina. En þú vilt bara til að handtaka sú hugmynd að einn er að bæta og einn er á endanum að draga. 

Nú undir hetta, bæði stafla og biðröð hægt væri að útfæra hvernig? Við munum ekki fara inn í kóða það vegna þess að hærra stigi Hugmyndin er tegund af meira augljóst. Ég meina, hvað menn gera? Ef ég er fyrsta manneskjan á Apple Geyma og þetta er framan dyrnar, þú veist, ég er að fara að standa hér. Og næsta manneskja er að fara að standa hér. Og næsta manneskja er að fara að standa hér. Svo hvaða gögn uppbygging lánar sig til biðröð? 

Áhorfendur: A biðröð. DAVID MALAN: Jæja, biðröð. Jú. Hvað annað? 

Áhorfendur: A tengda listanum. 

DAVID MALAN: A tengd lista sem þú gætir framkvæma. Og tengist listi er ágætur því þá getur það að vaxa geðþótta lengi öfugt að hafa nokkur ákveðinn fjölda af fólki í versluninni. En kannski a föst tala stöðum er lögmætur. Vegna þess að ef þeir hafa aðeins eins og 20 iPhone á fyrsta degi, kannski þeir þurfa aðeins á fjölbreytta stærð 20 til að tákna að biðröð, sem er aðeins að segja nú þegar við byrjum að tala um þessar hærri stigi vandamál, þú getur innleiða hana í allir tala af lifnaðarhættir. Og það er líklega bara að fara að vera a viðskipti burt í tíma og rúmi eða bara í eigin kóða flókið þinn. 

Hvað um reykháf? Jæja, stafla, höfum við séð of gæti bara verið þessi stæði. Og þú gætir framkvæma þetta fylki. En á einhverjum tímapunkti ef þú notar array, hvað er að fara að gerast á bökkunum þú ert að reyna að setja niður? Allt í lagi. Þú ert bara að fara að vera fær um að fara svo hátt. Og ég held að í Mather þeir eru reyndar Innfelld í þeirri opnun. Svo reyndar er það nánast eins Mather notar fylki á fasta stærð, vegna þess að þú getur aðeins passa svo mörg stæði í þeirri opnun í vegg niður fyrir hné fólks. Og svo að gæti verið sagður vera array, en við gátum vissulega innleiða það almennt með tengda listanum. 

Jæja, hvað um annars gögn uppbygging? Leyfðu mér að draga upp eitt annað sjón hér. Eitthvað eins og hvernig óður í this einn hér? Hvers vegna gæti það verið gagnlegt að hafa ekki eitthvað eins ímynda sem trie, sem við sáum var þessi mjög breiður hnúður, sem hver um sig er í fylki? En hvað ef við gerum eitthvað meira einfaldlega, eins og gamlan skóla ættartré, hver af sem hnútar hér er bara að geyma númer. Í stað þess að nafn eða afkomandi er bara að geyma fjölda svona. 

Jæja, hrognamál við notum í gögn uppbygging er bæði reynir og tré, þar sem trie, aftur, er bara einn sem hnútar eru fylki, er enn það sem þú gætir nota frá grunnskóla þegar þú gerðir fjölskyldu tree-- lauf og rót af trénu og barna foreldri og systkini þeirra. Og við gætum innleiða tré, til dæmis, eins og einfaldlega þar sem þetta. A tré, ef það sem hnút, einn af þessum hringjum sem hefur a tala, það er ekki að fara að hafa einn músina, en tveir. Og um leið og þú bætir annað músina, þú geta reyndar nú gera Raða af tvívíð gögn mannvirki í minni. Líkt og tveggja vídda array, þú getur hafa konar tvívíð tengd listum en sjálfur að fylgja mynstri þar er engin hringrás. Það er sannarlega tré með einum afa leið upp hér og þá sumir foreldrar og börn og barnabörn og barnabarnabörn. og svo framvegis. 

En hvað er í raun sniðugt um þetta líka, bara til að stríða þér með smá kóða, Muna endurkvæmni frá stund aftur, þar þú skrifa fall sem kallar sig. Þetta er falleg tækifæri að innleiða eitthvað eins endurkvæmni, vegna íhuga þetta. 

Þetta er tré. Og ég hef verið lítið endaþarms með hvernig Ég setti heiltölur í götu. Svo mikið svo að það hefur sérstaka name-- tvíleitartré. Nú höfum við heyrt um tvöfaldur leita, en þú getur vinna aftur á bak frá nafni þetta er? Hvað er mynstur af hvernig ég sett á heiltölur í þessu tré? Það er ekki handahófskennt. There 'sumir mynstur. Já. 

Áhorfendur: Smærri sjálfur á vinstri. 

DAVID MALAN: Já. Smærri ríkin eru á vinstri. Stærri eru til hægri. Þannig að a satt staðhæfing er a foreldri er meiri en vinstri barn hennar, en minna en hægri barn hennar. Og það eitt og sér er jafnvel endurkvæma munnleg skýring vegna þess að þú getur sótt það Sama rökfræði hverjum hnút og það aðeins botn út, grunnur tilfelli ef þú mun, þegar þú högg einn af lauf, svo að segja, þar laufblað hefur engin börn frekar. 

Nú hvernig gætir þú fundið númerið 44? Þú myndir byrja á rót og segja, HM. 55 er ekki 44 Svo ég vil að fara hægri eða ég vil að fara til vinstri? Jæja, augljóslega þú vilt að fara til vinstri. Og svo er það bara eins og í símanum bók dæmi í tvöfaldur leit almennt. En við erum að útfæra hana nú lítið meira virk en fylki gæti leyfa. Og í raun, ef þú vilt að líta á kóðann, við fyrstu sýn viss. Það lítur út eins og a heild búnt af línum. En það er fallegur einfalt. Ef þú vilt að framkvæma aðgerð kölluð Leita tilgangur í lífinu er að leita að verðmæti eins og n, heil tala, og þú ert leidd í einum pointer-- bendi á hnút rótum, Frekar, trés sem þú getur fengið aðgang að allt annað, eftir hversu einfaldur þú getur innleiða rökfræði. Ef tré er null, augljóslega er það ekki þar. Skulum aftur bara rangar. Hægri? Ef þú lætur það ekkert, það er ekkert þar. 

Annars, ef n er minna en tré arrow n- nú arrow n, muna við kynntum super stuttlega um daginn, og það bara þýðir de-tilvísun á músina og líta á sviði sem kallast n. Svo það þýðir að fara þangað og líta á sviði sem kallast n. Svo ef n er gildið sem þú ert að gefa, er minna en verðmæti í trjánum heiltala, Hvar viltu að fara? Til vinstri. 

Svo taka endurkvæmni. Ég ætla returning-- ekki satt. Ekki rangar. Ég ætla að skila hvað svarið er frá símtali við sjálfan mig, liggur N aftur, sem er óþarfi, En hvað er nú örlítið öðruvísi? Hvernig er ég að gera vandamálið minna? Ég er brottför í sem annað rök, ekki rót af trénu, en vinstri barn í þessu tilfelli. Þannig að ég ætla að brottför í vinstri barn. 

Á meðan, ef n er stærra en hnúturinn Ég er nú að horfa á, Ég leita á hægri hlið. Annars, ef tré er ekki null, og ef þátturinn er ekki til vinstri og það er ekki til hægri, hvað er frábærlega raunin? Við höfum reyndar fundið hnút í spurning, og svo við aftur satt. 

Þannig að við höfum bara klóra yfirborðið nú sumir af þessum gögn uppbygging. Í Heimadæmi fimm þú munt kanna þetta enn frekar, og þú munt gefa hönnun val um hvernig á að fara um þetta. Það sem ég vil að gera á er bara a 30 second Teaser hvað bíður í næstu viku og víðar. 

Eins og við begin-- betur fer þú gætir think-- umskipti okkar rólega úr heimi C og lægra stigi framkvæmd upplýsingar, að heimi þar sem við getum tekið fyrir veitt að einhver annar hefur loksins framkvæmda þessara gagna mannvirki fyrir okkur, og við munum byrja að skilja raunverulega heimi þýðir að innleiða vefur-undirstaða forrit og vefsíður almennt og einnig mjög öryggi afleiðingar sem við höfum aðeins farnir að klóra yfirborð. Hér er það sem bíður okkar á næstu dögum koma. 

[VIDEO Spilun] 

-Hann Kom með skilaboðum með siðareglur alla sína eigin. Hann kom til a veröld af grimmur eldveggir, uncaring leið, og hættum miklu verra en dauðinn. Hann er fljótur. Hann er sterkur. Hann er TCP / IP, og hann fékk netfangið þitt. "Warriors á Netinu." [END vídeó spilun] DAVID MALAN: Tilkoma næstu viku. Við munum sjá þig þá. [VIDEO Spilun] -Og Nú, "Deep Thoughts" eftir Daven Farnham. -David Byrjar alltaf fyrirlestrar með, "Allt í lagi." Hvers vegna ekki, "Hér er lausnin til þessa viku Heimadæmi " eða "Við erum að gefa ykkur að A?" [Book] [END vídeó spilun]