DOUG LLOYD: Svo í CS50, höfum við fjallað a einhver fjöldi af mismunandi gögn uppbygging, ekki satt? Við höfum séð fylki, og tengd listum, og kjötkássa borð, og reynir, stafla og biðraðir. Við munum einnig læra smá um tré og hrúga, en í raun þetta allt enda upp tilvera afbrigði á þema. Það eru í raun þessir konar fjórum grunnhugmyndir sem allt annað er hægt að sjóða niður til. Fylki, tengd listum, kjötkássa borð, og reynir. Og eins og ég sagði, það breytileiki á þeim, en þetta er nokkuð mikið að gerast til að draga saman allt sem við erum að fara að tala um í þessum flokki hvað varðar C. En hvernig þetta allt mál upp, ekki satt? Við höfum talað um kosti og galla hvert í sérstökum myndböndum á þeim, en það er mikið af tölum fá kastað í kring. There 'a einhver fjöldi af almennt Hugsanir fá kastað í kring. Við skulum reyna að styrkja það í bara einum stað. Skulum vega kosti á móti gallar, og íhuga sem gögn uppbygging gæti verið rétt gögn uppbygging fyrir aðstæðum þínum, hvað konar gögn þú ætlar að geyma. Þú þarft ekki endilega alltaf að nota frábær fljótur innsetningu, eyða, og útlit af Trie ef þú virkilega ekki sama um að setja og eyða of mikið. Ef þú þarft bara fljótt handahófi aðgang, kannski er fylki betra. Svo skulum drjúpa það. Við skulum tala um hver af fjórum helstu tegundir af gögn uppbygging sem við höfum talað um, og bara sjá þegar þær eru svo góðar, og þegar þeir gætu ekki verið svo gott. Svo skulum byrja með fylki. Svo ísetningu, það er góður af slæmur. 

Innsetning í lok fylki er í lagi, ef við erum að byggja fjölda sem við förum. En ef við þurfum að setja þættir í miðjunni, hugsa til baka til ísetningar tegund, það er mikið breytast til að passa stak í það. Og svo ef við erum að fara að setja hvar en í lok fylki, það er sennilega ekki svo mikill. 

Á sama hátt, eyðingu, nema við séum eyða frá lokum fylki, er sennilega ekki svo mikill ef við viljum ekki að fara tóm eyður, sem venjulega við gerum ekki. Við viljum að fjarlægja stak og þá tegund af gera það snug aftur. Og svo eyða þætti úr fylki, heldur ekki svo mikill. 

Útlit, þó, er mikill. Við höfum handahófi aðgang, fasti tími útlit. Við segjum bara sjö, og við förum að array flutning sjö. Við segjum 20, með farðu array flutning 20. Við þurfum ekki að árétta yfir. Það er nokkuð gott. 

Fylki eru einnig tiltölulega auðvelt að raða. Í hvert skipti sem við töluðum um að flokka reiknirit, td val tagi, innsetning flokka, kúla raða, sameinast tegund, sem við notuðum alltaf fylki til að gera það, því fylki eru nokkuð auðvelt að tegund, miðað við þau gögn sem mannvirki við höfum séð hingað til. 

Þeir eru einnig tiltölulega lítill. Það er ekki mikið af auka rúm. Þú stillir bara til hliðar nákvæmlega eins mikið eins og þú þarft til að halda gögnunum, og það er ansi mikið það. Svo þeir eru ansi lítið og duglegur í þá áttina. En annar ókostur, þó, er að þeir eru fastir í stærð. Við verðum að lýsa nákvæmlega hvernig stór viljum array okkar til að vera, og við fáum aðeins eitt skot á það. Við getum ekki vaxa og minnka það. 

Ef við þurfum að vaxa eða minnka það, við þarf að lýsa alveg nýtt fylki, afrita alla þætti sem Fyrsta array í seinni array. Og ef við misreiknaði að tími, þurfum við að gera það aftur. Ekki svo mikill. Svo fylki gefa okkur ekki svigrúm til að hafa breytilegan fjölda þátta. 

Með tengda listanum, innsetning er nokkuð auðvelt. Við tittur bara á the andlit. Eyðingu er einnig nokkuð auðvelt. Við verðum að finna þá þætti. Sem fela í sér sumir leitar. 

En þegar þú hefur fundið þáttur þú ert að leita að, allt sem þú þarft að gera er að breyta músina, hugsanlega tveir ef þú ert tengdur list-- a tvöfalt tengda listanum, rather-- og þá getur þú bara losa hnút. Þú þarft ekki að skipta allt í kring. Þú breytir bara tvær ábendingum, svo það er nokkuð fljótur. 

Útlit er slæmt þó, ekki satt? Í röð fyrir okkur að finna þáttur í tengda listanum, hvort ein sér eða tvöfalt tengd, við verðum að línuleg leita það. Við verðum að byrja á byrjun og færa enda, eða byrja í lok ferðinni á byrjun. Við höfum ekki handahófi aðgang lengur. Þannig að ef við erum að gera a mikið af leit, kannski tengdur listi er ekki alveg svo gott fyrir okkur. 

Þeir eru einnig mjög erfitt að raða, ekki satt? The eini vegur þú geta virkilega raða tengdan lista er að flokka það sem þú reisa það. En ef þú raða það eins og þú reisa það, þú ert ekki lengur gera fljótur innsetning lengur. Þú ert ekki bara að tacking það á the andlit. Þú þarft að finna rétt blettur til að setja það, og þá innsetningu þína verður bara um eins slæmt sem setja inn í array. Svo tengd listar eru ekki svo mikill fyrir flokkun gagna. 

Þeir eru líka nokkuð lítil, stærð-vitur. Tvöfalt tengd lista örlítið stærri en ein tengd listum, sem eru örlítið stærri en fylki, en það er ekki a gríðarstór magn af sóa plássi. Svo ef pláss er á yfirverði, en ekki mjög mikil iðgjald, þetta gæti verið rétta leiðin til að fara. 

Kjötkássa matskeið. Að setja inn í kjötkássa borð er nokkuð augljóst. Það er tveggja þrepa ferli. Fyrst þurfum við að keyra gögn okkar með a kjötkássa virka til að fá kjötkássa kóða, og þá erum við að setja þáttur í að kjötkássa borð á þeim kjötkássa kóða staðsetningu. 

Eyðingu, svipað tengda listanum, er auðvelt þegar þú finnur frumefni. Þú þarft að finna það fyrst, en svo þegar þú eyðir því, þú þarft bara að skiptast á a par af ábendingum, ef þú ert að nota sérstakan chaining. Ef þú ert að nota leit, eða ef þú ert ekki nota chaining á öllum í kjötkássa töflunni, eyðingu er í raun mjög auðvelt. Allt sem þú þarft að gera er að kjötkássa gögn, og þá fara að þeim stað. Og miðað við að þú ert ekki hefur einhverjar árekstra, þú munt vera fær um að eyða mjög fljótt. 

Nú, útlit er þar sem hlutirnir fá svolítið flóknara. Það er að meðaltali betra en tengd listum. Ef þú ert að nota chaining, þú ert enn í tengda listanum, sem þýðir að þú hefur enn Leita tjóns tengdan lista. En vegna þess að þú ert að taka þinn tengd lista og skipta því yfir 100 eða 1.000 eða n þættir í kjötkássa töflunni, þú ert tengd listum erum öll eitt NTH stærð. Þeir eru allir verulega minna. Þú n tengd lista í stað einn tengda listanum af stærð n. 

Og svo þetta raunverulegur-veröld stöðug þáttur, sem við almennt ekki tala um í tíma flókið, það er í raun og veru að gera a mismunur hér. Svo leit er enn línuleg leita ef þú ert að nota chaining, en lengd á listanum þú ert að leita í gegnum er mjög, mjög stutt í samanburði. Aftur, ef flokkun er þinn Markmiðið hér, kjötkássa borð er sennilega ekki rétt leið til að fara. Nota bara array ef flokkun er mjög mikilvægt fyrir þig. 

Og þeir geta keyrt tónstigi stærð. Það er erfitt að segja hvort kjötkássa borð er lítill eða stór, vegna þess að það fer alveg hversu stór kjötkássa borð er. Ef þú ert bara að fara að vera að geyma fimm þættir í kjötkássa töflunni, og þú ert með kjötkássa borð 10.000 þáttum í það, þú ert líklega að sóa a einhver fjöldi af rúm. Andstæður vera Þú getur einnig hafa mjög samningur kjötkássa matskeið, en minni kjötkássa borð fær, því lengur hvert þessara tengd listum fær. Og svo er það í raun engin leið til að skilgreina nákvæmlega á stærð við kjötkássa borð, en það er líklega óhætt að segja að það er yfirleitt að fara að vera stærri en tengdur Listinn geyma sömu gögn, en minni en Trie. 

Og reynir eru fjórða þessara mannvirkja sem við höfum verið að tala um. Innsetning í Trie er flókið. There 'a einhver fjöldi af dynamic minni úthlutun, sérstaklega í upphafi, eins og þú ert að byrja að byggja. En það er stöðug tími. Það er aðeins mannlegur þáttur hér gerir það erfiður. Að þurfa að lenda núll músina, malloc rúm, fara þangað, hugsanlega malloc pláss þaðan aftur. The tegund af hótunum þáttur ábendingum í dynamic minni úthlutun er þröskuldur að hreinsa. En þegar þú hefur eytt því, innsetning í raun kemur alveg einfalt, og það er vissulega stöðug tími. 

Niðurfelling er auðvelt. Allt sem þú þarft að gera er að sigla niður par af ábendingum og ókeypis hnút, svo það er nokkuð gott. Útlit er einnig nokkuð hratt. Það er aðeins byggt á lengd gögnunum. Svo ef öll gögn er fimm eðli strengir, til dæmis, þú ert að geyma fimm táknstrengja í Trie þinn, það tekur aðeins fimm skref til finna það sem þú ert að leita að. Fimm er bara stöðug þáttur, svo aftur, innsetning, eyðingu, og útlit hér eru allir föstu tíma, á áhrifaríkan hátt. 

Annar hlutur er að Trie er í raun eins konar þegar raðað, ekki satt? Í krafti hvernig við erum felldur þætti, með því að fara staf fyrir staf af lykill, eða stafa af tölustaf á takkann, yfirleitt, Trie endar að vera konar raðað eins og þú að byggja það. Það skiptir í raun ekki gerir vit til að hugsa um flokkun á sama hátt við að hugsa um það með fylki eða tengd listum, eða kjötkássa matskeið. En í einhverjum skilningi, þinn Trie er raðað eins og þú ferð. 

The hæðir, að sjálfsögðu, er að a Trie verður fljótt mikil. Frá hverjum mótum tímapunkti, þú gætir have-- ef lykillinn samanstendur af tölustöfum, Þú hefur 10 önnur stöðum sem þú getur farið, sem þýðir að hverjum hnút inniheldur upplýsingar um þau gögn sem þú vilt geyma á þeim hnút, auk 10 ábendingum. Sem á CS50 IDE, er 80 bæti. Svo það er að minnsta kosti 80 bæti fyrir hver hnútur sem þú býrð, og það er ekki einu sinni að telja gögn. Og ef hnútar eru bréf stað tölustöfum, nú þú hafa 26 ábendingum frá hverjum stað. Og 26 sinnum 8 er sennilega 200 bytes, eða eitthvað svoleiðis. Og þú hefur fé og lowercase-- þú getur sjá hvar ég er að fara með þetta, ekki satt? Hnútar geta fá mjög stór, og svo Trie sjálft, í heild, getur fá mjög stór líka. Svo ef pláss er a hár iðgjald á kerfinu þínu, a Trie gæti ekki verið rétt leið til að fara, jafnvel þó að aðrir kostir þess koma inn í leik. Ég er Doug Lloyd. Þetta er CS50.