[Powered by Google Translate] [Vika 6, Áframhaldandi] [David J. Malan] [Harvard University] [Þetta er CS50.] [CS50.TV] Þetta er CS50 og þetta er í lok 6. viku. Svo CS50x, eitt af fyrstu námskeið Harvard er þátt í EDX frumkvæði reyndar frumraun síðasta mánudag. Ef þú vildi eins og til að fá innsýn í það sem aðrir á Netinu eru nú eftir með, getur þú höfuð á x.cs50.net. Það verður sent þig til viðeigandi stað á edx.org, sem var þar sem þetta og önnur námskeið frá MIT og Berkeley nú lifa. Þú þarft að skrá þig sem notanda, þú munt komast að því að efnið er að mestu leyti sama eins og þú hafir fengið þessa önn, að vísu nokkurra vikna seinkun, eins og við fá allt tilbúið. En hvað nemendur í CS50x mun nú sjá er tengi alveg eins og þessi. Þetta til dæmis, er Zamyla leiða walkthrough fyrir setja vandamál 0. Við innskráningu í edx.org, a CS50x nemandi sér tegund af hlutur þú vildi búast við að sjá í námskeiði: á fyrirlestur í Monday, fyrirlestur í Wednesday, ýmsar stuttbuxur, vandamálið setur á, walkthroughs, PDFs. Auk, eins og þú sérð hér, vél þýðingar á ensku afrit í kínversku, japönsku, spænsku, ítölsku, og a heild búnt af öðrum tungumálum sem verður örugglega ófullkomin eins og við rúlla þá út kerfisbundið að nota eitthvað sem heitir API, eða umsókn forritun tengi, frá Google sem gerir okkur kleift að umbreyta ensku þessum tungumálum. En takk fyrir frábæra anda nokkrum hundrað plús sjálfboðaliðum, handahófi fólk á Netinu, sem hafa boðið boðið að taka þátt í þessu verkefni, munum við smám saman að bæta gæði þeirra þýðingar með því að hafa menn leiðrétta mistök sem tölvur okkar hafa gert. 

Svo kemur í ljós að við höfðum nokkur nemendur mæta á mánudaginn en við reiknuðum upphaflega. Í staðreynd, nú hefur CS50x 100.000 manns eftirfarandi eftir heima. Svo grein fyrir að þú ert öll hluti þessa vígslu flokki að þessu námskeiði í tölvunarfræði menntun almennt, í víðara samhengi, aðgengileg. Og raunin er nú, með nokkrum af þessum stórfellda online námskeið, þeir byrja allir með þessum mjög miklu magni, eins og við virðast hafa gert hér. En markmiðið, að lokum, að CS50x er í raun að fá eins og margir að ljúka við lína eins og kostur er. Með hönnun, CS50x er að fara að vera í boði frá þessu síðasta Mánudagur alla leið í gegnum 15 Apr, 2013, þannig að fólk sem hefur skóla skuldbindingar annars staðar, vinna, fjölskylda, önnur átök og eins, hafa aðeins meiri sveigjanleika sem að kafa í þessu námskeiði, sem nægja að segja, er alveg ambitiously gert ef aðeins á meðan aðeins þrjá mánuði á venjulegum önn. En þessir nemendur verða að takast á við sömu setur vandamál, skoða sama efni, hafa aðgang að sömu stuttbuxur og þess háttar. Svo grein fyrir því að við erum öll í raun í þessu saman. Og einn af the endir markmiðum CS50x er ekki bara til að fá sem margir gott fólk til að ljúka við lína og gefa þeim þessa nýfundinni skilning á tölvunarfræði og forritun, en einnig að hafa þá með þessa hluti reynslu. Eitt af skilgreina eiginleika 50 á háskólasvæðinu, við vonum, hefur verið svona samfélagsleg reynslu, fyrir betri eða verri, stundum, en hafa þetta fólk að snúa sér að vinstri og hægri, og skrifstofa klukkustundir og hackathon og sanngjarnt. Það er svolítið erfiðara að gera það í eigin persónu með fólkinu á netinu, en CS50x lýkur í apríl með fyrsta sinn CS50 Expo, sem verður að vera á netinu í aðlögun hugmynd okkar um sanngjörn þar sem þessar þúsundir nemenda allt verður boðið að senda inn 1 - til 2-mínútna vídeó, annaðhvort screencast um lokaverkefni þeirra eða vídeó af þeim veifa halló og tala um verkefni þeirra og demoing það, mikið eins og forveri þinn hefur gert hér á háskólasvæðinu á gangvirði, þannig að í lok hverrar annar, er ætlunin að hafa alþjóðlegt sýningu endanlega verkefni CS50x nemenda, eins og það sem bíður þér þetta desember hér á háskólasvæðinu. Svo meira um það á næstu mánuðum. 

Með 100.000 nemendur, þó kemur, þörf fyrir nokkra CAS. Í ljósi þess að þú krakkar eru að ryðja brautina hér og taka CS50 nokkrar vikur áður en gefa út þetta efni er til gott fólk á EDX, grein við myndum elska að taka eins og margir af eigin nemendum okkar og hægt er í þessu verkefni, bæði á önn auk vetur og þetta kemur vor. Svo ef þú vilt taka þátt í CS50x, sérstaklega að taka þátt í á CS50x ræða, þá EDX útgáfa af CS50 ræða, sem margir ykkar hafa verið að nota á háskólasvæðinu, the online bulletin borð, skaltu ekki höfuð til að vefslóð, láttu okkur vita hver þú ert, vegna þess að við myndum elska að byggja upp lið af nemendum og starfsfólki og kenndu jafnt á háskólasvæðinu, sem eru einfaldlega að spila með og hjálpa út. Og þegar þeir sjá spurningu sem er kunnuglegt við þá, þú heyrir nemandi skýrslur sumir padda einhvers staðar þarna úti í einhverju landi á Netinu, Og það hringir bjöllu vegna þess að þú hafði líka þessi sömu mál í þínu d-sal fyrir nokkru, vonandi þá getur Chime í og ​​deila eigin reynslu. Svo skaltu ekki taka þátt ef þú vilt. 

Tölvunarfræði námskeið við Harvard hafa a hluti af hefð, CS50 meðal þeirra, af því að hafa nokkur fatnaður, föt, sem hægt er að klæðast með stolti í lok hverrar annar og sagði alveg stoltur að þú lokið CS50 og tók CS50 og þess háttar, og við reynum alltaf að taka nemendur í þessu ferli eins mikið og mögulegt er, þar sem við bjóðum, í kringum þennan tíma önn, nemendur að skila hönnun nota Photoshop eða hvað tól sem þú velur þú vilt nota Ef þú ert hönnuður, til að leggja hönnun fyrir T-skyrta og sweatshirts og regnhlífar og lítil bandanas fyrir hunda sem við höfum nú og þess háttar. Og allt er svo - sigurvegari á hverju ári er þá sýnd á heimasíðu Námskeiðið er á store.cs50.net. Allt er selt á kostnaðarverði þar, en website bara rekur sig og leyfa fólki að velja liti og hönnun, sem þeir vilja. Þannig að ég hélt að við myndum bara deila sumir af hönnun á síðasta ári sem voru á vefsíðu auk þessa hér, sem er árleg hefð. "Á hverjum degi Ég Seg Faultn" var eitt af uppgjöf á síðasta ári, sem er enn til staðar þarna fyrir Alumni. Við höfðum þetta einn, "CS50, Stofnað 1989." Einn af Bowdens okkar, Rob, var mjög vinsæl í fyrra. "Team Bowden" fæddist, var þessi hönnun lögð meðal efstu seljendur. Eins var þetta hérna. Margir höfðu "Bowden Fever" í samræmi við sölu logs. Gera sér grein fyrir að það gæti nú verið hönnun þar, upp á Netinu. Nánari upplýsingar um þetta í næsta vandamál setur að koma. 

Einn fleiri tól: þú hefur haft nokkur áhrif og vonandi er sumir snertið ekki-á reynsla með GDB, sem er, auðvitað, a aflúsara og gerir þér kleift að stjórna program á tiltölulega lágu stigi, að gera hvers konar hluti? Hvað er GDB láta þig gera? Já? Gefðu mér eitthvað. [Námsmaður svar, óskiljanlegur] Gott. Skref í aðgerð, þannig að þú ert ekki bara að slá hlaupa og hafa forritið blása gegnum heild sinni, prenta út það við hefðbundna framleiðslu. Frekar er hægt að stíga í gegnum hann línu fyrir línu, annaðhvort skrifa næst að fara línu fyrir línu eða skref til að kafa í aðgerð, venjulega einn sem þú skrifaðir. Hvað annað er GDB láta þig gera? Já? [Námsmaður svar, óskiljanlegur] Prenta breytur. Svo ef þú vilt gera smá sjálfsskoðun inni í forritinu án þess að þurfa að grípa til að skrifa printf yfirlýsingar um allt, þú getur bara prentað breytu eða birta breytu. Hvað annað er hægt að gera með aflúsara eins gdb? [Námsmaður svar, óskiljanlegur] Einmitt. Þú getur stillt Rofstaðir, þú getur sagt brjóta framkvæmd á meginvirkni eða foo virka. Það má segja að brjóta framkvæmd í línu 123. Og breakpoints eru mjög öflug tækni því ef þú ert með almenna tilfinningu um hvar vandamálið líklega er, þú þarft ekki að eyða tíma stepping í heild áætlunarinnar. Þú getur í raun hoppa þarna og þá byrja að slá - stepping í gegnum það með skref eða næsta eða eins. En aflinn með eitthvað eins og gdb er að það hjálpar þér, manna, finna vandamál og finna galla þínum. Það þýðir ekki endilega að finna þá svo mikið fyrir þig. 

Þannig að við kynntum um daginn style50, sem er stutt stjórn lína tól sem reynir að stylize númerið þitt svolítið meira eðlilega en þú,, manna gæti hafa gert. En það líka er í raun bara fagurfræði hlutur. En það kemur í ljós að það er þetta önnur tól gestur Valgrind sem er lítið meira Bogagöng að nota. Framleiðsla hennar er atrociously Cryptic við fyrstu sýn. En það er frábærlega vel, sérstaklega núna þegar við erum á hluta tíma þar sem þú ert að byrja að nota malloc og dynamic minni úthlutun. Hlutur getur farið mjög, mjög rangt fljótt. Vegna þess að ef þú gleymir að losa minni þitt, eða þú dereference sumir NULL músina, eða þú dereference sumir sorp músina, það er yfirleitt einkenni sem niðurstöður? Seg kenna. Og þú færð þessa algerlega skrá einhvers fjölda kílóbæti eða megabæti sem sýnir stöðu minni program þegar það hrundi, en program seg lokum galla, skiptingu kenna, sem þýðir eitthvað slæmt gerðist nánast alltaf tengd á minni sem tengist mistök sem þú gerðir eitthvað. Svo hjálpar Valgrind að finna hluti eins og þetta. Það er tól sem þú keyrir, eins gdb, eftir að þú hefur safnað saman program, heldur en að keyra forrit beint, hlaupa þú Valgrind og þú fara að því program, rétt eins og þú gerir við GDB. Nú, notkun, til að fá bestu konar framleiðsla, er svolítið langur, svo þarna efst á skjánum sem þú munt sjá Valgrind-v. "-V" nánast almennt þýðir fjölorður þegar þú ert að nota forrit á Linux tölvu. Svo þýðir það spýta út fleiri upplýsingar en þú gætir sjálfgefið. "- Leka-stöðva = fullur." Þetta er bara að segja stöðva fyrir öllum mögulegum leka minni, mistök sem gætu hafa ég gerði. Þetta líka, er sameiginlegt mynstur með Linux forrit. Almennt, ef þú hafa a lína rifrildi sem er "rofi", sem er ætlað að breyta hegðun forritsins, og það er eitt bréf, það er-V, en ef það er kveikt, bara með hönnun forritari, er fullt orð eða röð af orðum, stjórn lína rifrildi byrjar -. Þetta eru bara menn samninga, en þú munt sjá þá í auknum mæli. Og svo, að lokum, "a.out" er handahófskennt nafn fyrir the program í þessu tiltekna dæmi. Og hér er einhver fulltrúi framleiðsla. 

Áður en við lítum á það sem gæti þýtt, láta mig fara yfir í kóða hérna. Og láta mig færa þetta út af the vegur, kemur bráðum, og við skulum kíkja á memory.c, sem er þessi stutta dæmi hér. Svo í þessari áætlun, að láta mig stækka aðgerðir og spurningar. Við höfum fall helstu sem kallar fall, F, og þá hvað er f halda áfram að gera, í aðeins tæknilega ensku? Hvað f halda áfram að gera? Hvernig væri að ég ætla að byrja með línu 20, og staðsetningu stjarnan er ekki máli, en ég ætla bara að vera í samræmi hér við síðasta fyrirlestur. Hvað er lína 20 gera fyrir okkur? Á vinstri hönd. Við munum brjóta niður frekar. Int * x: hvað þýðir það að gera? Allt í lagi. Það að lýsa yfir með músina, og nú skulum vera enn meira tæknilega. Hvað þýðir það, mjög concretely, að lýsa yfir músina? Einhver annar? Já? [Námsmaður svar, óskiljanlegur] of langt. Svo þú ert að lesa á the réttur-hönd hlið af the jafna tákn. Við skulum einblína bara á vinstri, bara á int * x. Þetta er "lýsa" bendi, en nú skulum kafa í dýpra í þeirri skilgreiningu. Hvað þýðir að concretely, tæknilega meina? Já? [Námsmaður svar, óskiljanlegur] Allt í lagi. Það er að undirbúa að vista veffang í minni. Gott. Og við skulum taka þetta einu skrefi lengra, það er að lýsa yfir breytu, x, sem er 32 bita. Og ég veit að það er 32 bita vegna þess að -? Það er ekki vegna þess að það er int, því það er bendi í þessu tilfelli. Tilviljun að það er eitt og hið sama með int, en sú staðreynd að það er stjarna þarna þýðir þetta er bendillinn og í tækinu, eins og með margar tölvur, en ekki allir, eru ábendingum 32 bits. Á fleiri nútíma vélbúnaði eins nýjustu Macs, nýjustu tölvur, þú might hafa 64-bita punkta, en í tækinu eru þetta 32 bita. Svo munum við staðla á því. Meira concretely, sagan fer sem hér segir: Við "lýsa" bendi, hvað þýðir það? Við undirbúning að geyma minni heimilisfang. Hvað þýðir það? Við að búa til breytu kallað X sem tekur upp 32 bita sem mun brátt geyma veffang heiltala. Og það er líklega um eins nákvæm og við getum fengið. Það er í lagi að færa fram til að einfalda heiminn og segja bara lýsa bendi heitir x. Kunngjörið bendi, en átta sig og skilja hvað er í raun að gerast jafnvel í aðeins þeim nokkrum stöfum. 

Nú, þetta er nánast svolítið auðveldara, jafnvel þótt það sé lengri tjáningu. Svo hvað er þetta að gera, það er lögð áhersla á núna: "malloc (10 * sizeof (int));" Já? [Námsmaður svar, óskiljanlegur] Gott. Og ég tek það þar. Það er úthlutun klumpur af minni fyrir tíu heiltölur. Og nú skulum kafa örlítið dýpra, það er úthlutun klumpur af minni fyrir tíu heiltölur. Hvað er malloc aftur þá? Heimilisfang þess klumpur, eða fleiri concretely, heimilisfang fyrstu bæti þess klumpur. Hvernig þá er ég forritari, að vita hvar þessi klumpur af endum minni? Ég veit að það er samliggjandi. Malloc, samkvæmt skilgreiningu, mun gefa þér samfelldu klumpur af minni. Engar eyður í henni. Þú hefur aðgang að öllum bæti í því klumpur, aftur til baka til baka, en hvernig veit ég hvar í lok þessa klumpur af minni er? Þegar þú notar malloc? [Námsmaður svar, óskiljanlegur] Good. Þú gerir það ekki. Þú þarft að muna. Ég verð að muna að ég notaði verðmæti 10, og ég er ekki einu sinni virðist hafa gert það hér. En kvöð er algjörlega á mig. Strlen, sem við höfum orðið örlítið reiðir sig á fyrir strengi, virkar einungis vegna þessa samnings að hafa \ 0 eða þetta sérstaka NUL karakter, NUL, í lok streng. Það þýðir ekki að halda að aðeins handahófi klumpur af minni. Það er komið að þér. Svo línu 20, þá úthlutar, klumpur af minni sem getur geymt tíu heiltölur, og það geymir veffang fyrstu bæti þess klumpur af minni í breytu sem heitir x. Ergo, sem er stiga. Svo línu 21, því miður, voru mistök. En fyrst, hvað er það að gera? Það er að segja verslun á stað 10, 0 verðtryggð, á klumpur af minni kallast x gildi 0. 

Svo taka a par af hlutur að fara á. Jafnvel þó að x er bendillinn, muna frá fáeinum vikum að þú getur samt notað array-stíl ferningur krappi tákn. Vegna þess að það er í raun stutt-hönd tákn fyrir meira Cryptic-útlit músina tölur. þar sem við myndum gera eitthvað eins og this: Taktu heimilisfang x, færa 10 blettur yfir, þá fara þar til hvað netfang er geymd á þeim stað. En hreinskilnislega, þetta er bara grimmilegur að lesa og fá þægilegri með. Svo notar heimurinn vanalega hornklofum bara vegna þess að það er svo miklu fleiri manna-vingjarnlegur að lesa. En það er það sem er raunverulega að gerast undir hetta, x er heimilisfang, ekki fylki, í sjálfu sér. Þannig að þetta er að geyma 0 í stað 10 í x. Af hverju er þetta slæmt? Já? [Námsmaður svar, óskiljanlegur] Einmitt. Við úthlutað aðeins tíu ints, en við telja frá 0 þegar forritun í C, þannig að þú hefur aðgang að 0 1 2 3 4 5 6 7 8 9 en ekki 10. Svo annað hvort forritið er að fara að seg kenna eða það er ekki. En við í raun ekki vita, þetta er tegund af nondeterministic hegðun. Það fer alveg eftir hvort við heppinn. Ef það kemur í ljós að stýrikerfið er ekki sama hvort ég nota þessi auka bæti, jafnvel þótt það hafi ekki gefið mér það, program minn gæti ekki hrun. Það er hrár, það er þrjótur, en þú might ekki sjá þessi einkenni, eða þú gætir séð hana aðeins einu sinni í a á meðan. En raunin er að villan sé í raun. Og það er mjög erfitt ef þú hefur skrifað forrit sem þú vilt vera rétt, að þú hefur selt forrit sem fólk notar að sérhver einu sinni í a á meðan hrun vegna þess, að sjálfsögðu, þetta er ekki gott. Í staðreynd, ef þú ert með Android símann eða iPhone og þú sækir forrit þessa dagana, ef þú hefur einhvern tímann fengið app bara hætta, allt í einu að það hverfur, það er nánast alltaf afleiðing af minni sem tengist mál, þar sem forritari ruglaður upp og dereferenced bendi að hann ætti ekki að hafa, og afleiðing af IOS eða Android er bara að drepa forrit öllu frekar en áhættu óskilgreindu hegðun eða einhvers konar málamiðlun öryggi. 

Það er einn annar galla í þessu forriti nema þessu. Hvað annað hef ég ruglaður upp í þessu forriti? Ég hef ekki æft það sem ég hef boðað. Já? [Námsmaður svar, óskiljanlegur] Good. Ég hef ekki frelsi minni. Svo þumalputtaregla nú þarf að vera hvenær sem þú kalla malloc, þú verður að hringja frítt þegar þú ert búinn að nota þessi minni. Nú, þegar ég myndi vilja til að losa þetta minni? Sennilega, miðað þessi fyrsta lína var rétt, myndi ég vilja til að gera það hér. Þar sem ég gat ekki, til dæmis, gera það hérna. Hvers vegna? Bara út af umfangi. Svo jafnvel þó að við erum að tala um ábendingum, þetta er viku 2 eða 3 mál, þar sem x er aðeins í umfangi inni á hrokkið axlabönd þar var lýst. Svo þú ákveðið getur ekki losa það þar. Eina von mín til losa það er um það bil eftir línu 21. Þetta er frekar einfalt forrit, það var nokkuð auðvelt þegar þú vafði konar hugann um hvaða forrit er að gera, þar sem mistök voru. Og jafnvel ef þú hefur ekki séð hann í fyrstu, vonandi er það svolítið augljóst nú að þessi mistök eru nokkuð auðvelt að leysa og auðveldlega gert. En þegar forrit er meira en 12 línur lengi, það er 50 línur lengi, 100 línur lengi, ganga í gegnum línu númer með því að línu, hugsa um það rökrétt, er mögulegt en ekki sérstaklega gaman að gera, stöðugt að leita að galla, og það er líka erfitt að gera, og það er ástæðan fyrir tól eins Valgrind til. Leyfðu mér að fara á undan og gera þetta: láta mig opna Terminal gluggann minn, og láta mig ekki bara að keyra minni, því minni virðist vera fínn. Ég ætla að fá heppinn. Fara til að auka bæti í lok fylkisins virðist ekki vera of erfið. En láta mig, engu að síður, gera geðheilsu stöðva, sem þýðir bara að athuga hvort þetta er í raun rétt. 

Svo skulum gera valgrind-v - leka-stöðva = fullur, og þá er nafn af the program í þessu tilfelli minni, ekki a.out. Svo láta mig fara á undan og gera það. Hit inn. Kæri Guð. Þetta er afrakstur hennar, og þetta er það sem ég benti á áðan. En ef þú lærir að lesa í gegnum allt bull hér, flest af þessu er bara sjúkdómsgreiningar framleiðsla sem er ekki áhugavert. Hvaða auga þitt raunverulega vill að leita að er minnst á villur eða öryrki. Orð sem stinga vandamál. Og reyndar, við skulum sjá hvað er að gerast rangt hérna. Ég er með yfirlit af einhverju tagi, "í notkun á brottför:. 40 bæti í 1 blokkum" Ég er ekki alveg viss hvað blokk er enn, en 40 bæti raunverulega líður eins og ég gæti fundið út hvar það kemur frá. 40 bæti. Hvers vegna er 40 bæti í notkun á hætta? Og sérstaklega, ef við skruna niður hér, Hvers vegna hef ég misst örugglega 40 bæti? Já? [Námsmaður svar, óskiljanlegur] Perfect. Já, nákvæmlega. Það voru tíu heiltölur, og hver þeirra er stærð 4, eða 32 bita, þannig að ég hef misst nákvæmlega 40 bæti, því eins og þú lagt, ég hef ekki kallað frjáls. Það er ein villa, og nú skulum líta niður aðeins lengra og sjá við hliðina á þessu, "Ógilt skrifa af stærð 4." Nú hvað er þetta? Þetta netfang er lýst hvaða stöð tákn, virðist? Þetta er sextánskur, og hvenær þú sérð númer byrjar á 0x, það þýðir sextánskur, sem við gerðum leið aftur í, ég held, kafla pset 0 um spurningum, sem var bara að gera warmup æfa, umbreyta aukastaf að álög til tvöfaldur og svo framvegis. Sextánskt, bara með því að mönnum venju, er oftast notuð til að tákna punkta eða, almennt, fjallar um. Það er bara venju, því það er svolítið auðveldara að lesa, það er a lítill fleiri samningur en eitthvað eins og tugabrot, og tvöfaldur er gagnslaus fyrir flest menn að nota. Svo nú hvað þýðir þetta? Jæja, það lítur út eins og það er ógilt skrifa stærð 4 á línu 21 í memory.c. Svo við skulum fara aftur á línu 21, og reyndar, hér er það ógilt skrifa. Svo Valgrind er ekki að fara að alveg að halda í hendina á mér og segja mér hvað festa er, en það er að finna að ég er að gera ógilt skrifa. Ég er snerta 4 bæti sem ég ætti ekki að vera, og greinilega er það vegna þess, eins og þú bent á, ég er að gera [10] í stað [9] hámarks eða [0] eða eitthvað þar á milli. Með Valgrind, átta sig hvenær sem þú ert nú að skrifa forrit sem notar ábendingum og notar minni og malloc nánar tiltekið, ákveðið að fá inn í vana að keyra þetta lengi en mjög auðvelt að afrita og líma stjórn Valgrind til að sjá hvort það er einhver villa þar. Og það verður yfirþyrmandi hvert skipti sem þú sérð framleiðsla, en bara flokka í gegnum sjónrænt öll framleiðsla og sjá hvort þú sérð nefnir villur eða varnaðarorð eða ógilt eða glataður. Hvaða orð sem hljóma eins og þú ruglaður upp einhvers staðar. Svo átta sig á að það er nýtt tæki í tól þitt. 

Nú á mánudaginn, við höfðum a heild búnt af fólkinu komið upp hér og tákna hugmynd um tengda lista. Og við kynntum tengda listanum sem lausn á því vandamál? Já? [Námsmaður svar, óskiljanlegur] Good. Fylki er ekki minni við þá. Ef úthluta á fjölbreytta stærð 10, það er allt sem þú færð. Þú getur hringt í virka eins realloc ef þú kallaðir upphaflega malloc, og að geta reynt að vaxa array ef það er pláss undir lok þess sem enginn annar er að nota, og ef það er ekki, það verður bara að finna þér stærri klumpur annars staðar. En þá er það mun afrita allar þessar bæti í nýju fylki. Þetta hljómar eins og mjög réttri lausn. Hvers vegna er þetta óaðlaðandi? Ég meina það virkar, hafa menn leyst þetta vandamál. Af hverju gerði við þurfum að leysa það á mánudaginn með tengd listum? Já? [Námsmaður svar, óskiljanlegur] Það gæti tekið langan tíma. Í raun, á meðan þú ert að hringja malloc eða realloc eða calloc, sem er enn einn, hvenær sem þú, the program, eru að tala um stýrikerfi, þú hættir að hægja forritið niður. Og ef þú ert að gera þessar tegundir af hlutum í lykkjur, þú ert virkilega hægur hlutur dúnn. Þú ert ekki að fara að taka þetta fyrir einföldustu "Halló heimur" tegund programs, en í miklu stærri verkefnum, spyrja stýrikerfið aftur og aftur fyrir minni eða gefa það aftur og aftur hefur tilhneigingu til að vera gott. Auk, það er bara svoleiðis intellectually - það er alger tímasóun. Hvers vegna skiptir meira og meira minni, hætta að afrita allt í nýju fylki, Ef þú ert með val sem gerir þér kleift að úthluta aðeins eins mikið minni og þú þarft í raun og veru? Svo er það plús og mínus hér. Eitt af plús-merkjum nú að við höfum kraft. Skiptir ekki máli hvar klumpur af minni eru sem eru ókeypis, Ég get bara svona að búa til þessar brauð mola með ábendingum til band alla tengda listanum mínum saman. En ég borga amk eitt verð. 

Hvað þarf ég að gefa upp á að ná tengd listum? Já? [Námsmaður svar, óskiljanlegur] Good. Þú þarft meira minni. Nú þarf ég pláss fyrir þessum ábendingum, og í tilfelli þessarar frábær einfalt tengd lista sem er aðeins að reyna að geyma heiltölur, sem eru 4 bytes, halda við að segja Jæja, er bendillinn er 4 bæti, svo nú hef ég bókstaflega tvöfaldast magn af minni sem ég þarf bara að geyma þennan lista. En aftur, þetta er stöðug tradeoff í tölvunarfræði milli tíma og rúmi og þróun, fyrirhöfn og öðrum auðlindum. Hvað er annar ókostur við að nota tengda listanum? Já? [Námsmaður svar, óskiljanlegur] Gott. Ekki eins auðvelt að nálgast. Við getum ekki lengur skiptimynt viku 0 meginreglur eins og skipta og sigra. Og nánar tiltekið, tvöfaldur leit. Því jafnvel þó að við mennirnir getur séð um það bil þar sem miðja þessum lista er tölvan veit bara að þetta tengist listinn byrjar á netfangið heitir fyrst. Og það er 0x123 eða eitthvað svoleiðis. Og eina leiðin sem forritið finnur miðju þáttur er að í raun að leita á alla lista. Og jafnvel þá, það hefur bókstaflega að leita á alla lista þar jafnvel þegar þú nærð miðju þáttur með því að fylgja ábendingar, þú, the program, hafa ekki hugmynd um hversu lengi þessi listi er, hugsanlega, þar til þú högg í lok þess, og hvernig veistu kerfisbundið að þú ert á the endir af a tengda listanum? Það er sérstakt NULL músina, svo aftur, samningur. Frekar en að nota þetta bendi, ákveðið að við viljum ekki að það sé einhver sorp gildi bendir á stig einhvers staðar, við viljum það til að vera hönd niður, NULL, þannig að við höfum þetta Terminus í þessum gögnum uppbyggingu svo við vitum hvar það endar. 

Hvað ef við viljum vinna þetta? Við gerðum mest af þessu sjónrænt og með mönnum, En hvað ef við viljum gera á innsetningu? Svo upprunalega lista var 9, 17, 20, 22, 29, 34. Hvað ef við vildum þá malloc pláss fyrir fjölda 55, tengipunktur fyrir það, og þá viljum við að setja 55 inn á listann eins og við gerðum á mánudaginn? Hvernig gerum við þetta? Jæja, Anita kom upp og hún gekk í meginatriðum á listanum. Hún byrjaði á fyrstu frumefni, þá næst, næst, næst, næst, næst. Lokum högg the vinstri-hönd alla leið niður og áttaði ó, þetta er NULL. Svo hvað bendillinn meðferð þarf að gera? Sá sem var á enda, númer 34, þurfti vinstri hönd hans upp að benda á 55, 55 þarf vinstri handlegg sínum vísar niður til að vera nýr NULL Terminator. Lokið. Pretty auðvelt að setja 55 í raðaða lista. Og hvernig getur þetta útlit? 

Leyfðu mér að fara á undan og opna upp smá kóða dæmi hér. Ég opna gedit, og láta mig opna tveir skrá fyrst. Einn er list1.h, og láta mig minna bara að þetta var klumpur af kóða sem við notuðum til að tákna hnút. A hnútur er með bæði int sem heitir N og bendilinn heitir næst að bara benda á næsta hlutur í listanum. Það er nú í. Klst skrá. Hvers vegna? Það er þetta venju, og við höfum ekki nýtt sér þetta mikið sjálf, en sá sem skrifaði printf og aðrar aðgerðir gaf sem gjöf til heimsins allar þessar aðgerðir með því að skrifa til skrá sem kallast stdio.h. Og þá er það string.h, og þá er map.h, og það er öll þessi h skrár sem þú gætir hafa séð eða notuð á tíma skrifuð af öðru fólki. Venjulega á þeim. H skrár eru aðeins hluti eins typedefs eða yfirlýsingar af sérsniðnum gerðum eða yfirlýsingum um Fastar. Þú setur ekki gerð virka 'í skrá haus. Þú setur í staðinn, bara frumútgáfur þeirra. Þú setur það sem þú vilt til að deila með heiminum hvað þeir þurfa í því skyni að safna saman kóðann. Svo bara til að komast inn í þennan vana, ákváðum við að gera það sama. Það er ekki mikið í list1.h, en við höfum sett eitthvað sem gæti haft áhuga á fólki í heiminum sem vilja nota tengda listanum framkvæmd okkar. Nú, í list1.c, ég mun ekki fara í gegnum þetta allt hlutur vegna þess að það er dálítið langur, þetta forrit, en við skulum hlaupa það raunverulegur fljótt við áminningu. Leyfðu mér að taka saman List1, láttu mig hlaupa þá List1, og það sem þú munt sjá er við höfum herma einfalt lítið forrit hér sem er að fara að leyfa mér að bæta við og fjarlægja númer til lista. Svo láta mig fara á undan og gerð 3 fyrir valkostina 3. Mig langar að setja inn númerið - við skulum gera fyrstu töluna, sem var 9, og nú er ég sagði listinn er nú 9. Leyfðu mér að fara á undan og gera aðra innsetningu, svo ég högg matseðill valkostur 3. Hvaða númer ég vil að setja? 17. Enter. Og ég geri bara eitt. Leyfðu mér að setja númer 22. Þannig að við höfum upphaf tengda listanum sem við höfðum í formi renna í smá stund síðan. Hvernig er þetta innsetning gerast í raun? Reyndar, 22 er nú í lok listanum. Sagan við sagt á sviðinu á mánudaginn og recapped bara núna verður í raun að vera að gerast í kóða. Við skulum taka a líta. Leyfðu mér að fletta ofan í þessari skrá. Við munum gljái yfir nokkrar af þeim aðgerðum, en við förum niður, segja, setja virka. 

Við skulum sjá hvernig við förum um að setja nýjan hnút í þessu tengda lista. Hvar er listinn lýst? Jæja, við skulum fletta alla leið upp á toppinn, og taka eftir því að tengjast minn listi er í raun lýst sem einu bendill sem er upphaflega NULL. Þannig að ég er að nota alþjóðlegt breytu hér, sem almennt við höfum boðað gegn vegna þess að það gerir númerið þitt smá sóðalegur til að viðhalda, það er tegund af latur, venjulega, en það er ekki latur og það er ekki rangt og það er ekki slæmt ef eini tilgangur program í lífinu er að gera sér einn tengda listanum. Sem er einmitt það sem við erum að gera. Svo frekar en að lýsa þessu í aðal og þá þarf að gefa það til allra virka við höfum skrifað í þessari áætlun, við skiljum í stað ó, við skulum bara gera það alþjóðlegt vegna þess að allt tilgangur þessarar áætlunar er að sýna fram á eitt og aðeins eitt tengda listanum. Svo finnst það í lagi. Hér eru frumgerðir mín, og við munum ekki fara í gegnum allar þessar, en ég skrifaði eyða stjórna, finna fallið, að setja inn virka og fara virka. En við skulum nú fara til baka niður í snertingu við virka og sjá hvernig þetta virkar hérna. Setja er á línu - hér við fara. Setja. Þannig að það tekur ekki neina rök, vegna þess að við erum að fara að spyrja notandi inni á þessum möguleika fyrir fjölda sem þeir vilja til að setja inn. En fyrst, búa við að gefa þeim pláss. Þetta er tegund af afrita og líma úr öðrum dæmi. Í því tilfelli, við vorum að úthluta við int, í þetta sinn við erum að úthluta í hnút. Ég er ekki alveg að muna hversu margir bæti hnút er, en það er allt í lagi. Sizeof geta tala það út fyrir mig. Og hvers vegna er ég að athuga for null í línu 120? Hvað gæti farið úrskeiðis í línu 119? Já? [Námsmaður svar, óskiljanlegur] Gott. Bara gæti verið raunin að ég hef beðið um of mikið minni eða eitthvað er rangt og stýrikerfi er ekki nóg bæti til að gefa mér, þannig merki það eins mikið með aftur núll, og ef ég stöðva ekki fyrir að og ég að halda áfram bara í blindni að nota heimilisfangið aftur, gæti það verið tómt. Það gæti verið einhver óþekkt gildi, ekki gott nema ég - í raun mun ekki vera óþekkt gildi. Það gæti verið NULL, svo ég vil ekki að misnota það og hætta dereferencing það. Ef það gerist, aftur ég bara og við munum láta eins og ég vissi ekki að fá aftur allir minni yfirleitt. 

Annars, ég segi notandi gefið mér númer til að setja inn, ég kalla gamla vini GetInt okkar, og þá var nýja setningafræði við kynnt á mánudag. 'Newptr-> n "þýðir að taka á það heimilisfang sem þú varst gefið malloc sem táknar fyrsta bæti nýs hnút hlut, og þá fara að því sviði sem kallast n. Smá fróðleiksmoli spurning: Þetta jafngildir hvað meira dulinn línu af kóða? Hvernig annars gæti ég skrifað þetta? Viltu taka stunga? [Námsmaður svar, óskiljanlegur] Gott. Notkun. N, en það er ekki alveg eins einfalt og þetta. Hvað þarf ég fyrst að gera? [Námsmaður svar, óskiljanlegur] Gott. Ég þarf að gera * newptr.n. Þannig að þetta er að segja nýja bendillinn er augljóslega netfang. Hvers vegna? Vegna þess að hún var aftur með malloc. Á * newptr segja "fara þangað," og svo þegar þú ert þarna, þá er hægt að nota fleiri kunnugleg. N, en þetta lítur bara svolítið ljót, sérstaklega ef við mennirnir eru að fara að draga ábendingum með örvum alla tíma, heimurinn hefur staðlað á þessum ör merki, sem gerir nákvæmlega það sama. Svo þú notar aðeins -> tákn þegar hlutur vinstri er músina. Annars, ef það er í raun strúktúr, nota. N. Og þá er þetta: Hvers vegna frumstilla ég newptr-> hliðina á NÚLL? Við viljum ekki hangandi vinstri hönd burt í lok áfanga. Við viljum því benda beint niður, sem þýðir í lok þessa lista gæti hugsanlega verið á þessum hnút, þannig að við gert betur úr skugga um það er NULL. Og almennt, Frumstilli breytur eða gögn meðlimir og structs að eitthvað er bara gott starf. Bara að láta sorp hendi og halda áfram að vera yfirleitt fær þér í vandræði Ef þú gleymir að gera eitthvað síðar. 

Hér er nokkur dæmi. Þetta aftur er að setja virka, og það fyrsta sem ég athuga er hvort breyta heitir fyrst, sem alþjóðlegt breytu er NULL, sem þýðir að það er ekkert tengt lista. Við höfum ekki sett neinar tölur, þannig að það er léttvæg til að setja þennan núverandi fjölda í listanum, því það tilheyrir bara á the byrjun af the listi. Þannig að þetta var þegar Anita var bara að standa upp hér einn, þykjast enginn annar var upp hér á sviðinu þar til við úthlutað hnút, svo hún gæti aukið hönd hennar í fyrsta sinn, Ef allir aðrir voru komnir upp á svið á eftir henni á mánudaginn. Nú hér, þetta er smá athuga þar sem ég verð að segja ef nýjan hnút á gildi á n er <verðmæti n í núverandi fyrstu hnút, sem þýðir að það er tengda listanum sem er hafin. Það er að minnsta kosti einn hnút á listanum, en þetta nýja strákur tilheyrir áður en það, þannig að við þurfum að færa hlutina í kring. Með öðrum orðum, ef listinn er hafin við bara, við skulum segja, bara númer 17, það er - í raun, við getum gert þetta betur. Ef við byrjum sögu okkar með músina hér heitir fyrst, og fyrst það er NULL, og við setja númer 9, númer 9 tilheyrir greinilega í upphafi listanum. Svo skulum láta okkur malloced bara heimilisfang eða númer 9 og setja það hér. Ef fyrsta er 9 sjálfgefið, fyrsta atburðarás við ræddum þýðir bara benda skulum þessi strákur hér, hafðu þetta eins NULL, nú höfum við númer 9. Næsta tala við viljum að setja er 17. 17 tilheyrir hérna, þannig að við erum að fara að gera sumir rökrétt stíga í gegnum þetta. Svo skulum í staðinn, áður en við gerum það, við skulum láta sem við vildum að setja númer 8. 

Svo bara fyrir sakir þægindi er, ég ætla að draga hér. En mundu, malloc getur sett það mest hvar sem er. En fyrir sakir teikningu er, mun ég setja það hér. Svo þykjast Ég hef bara úthlutað hnút fyrir fjölda 8, þetta er NULL sjálfgefið. Hvað þarf nú að gerast? A par af hlutum. Við gerðum þetta mistök á sviðinu á mánudaginn þar sem við uppfært bendi svona, þá var þetta, og þá erum við krafa - við munaðarlaus allir aðrir á sviðinu. Þar sem þú skóf - röð aðgerða hér er mikilvægt, því að nú höfum við misst þennan hnút 9 sem er bara svona fljótandi í geimnum. Svo þetta var ekki rétt nálgun á mánudaginn. Við höfum fyrst að gera eitthvað annað. Ástandið í heiminum lítur svona út. Upphaflega hefur 8 verið úthlutað. Hvað væri betri leið til að setja 8? Í stað þess að uppfæra þessa músina fyrst, bara uppfæra þetta einn hér í staðinn. Þannig að við þurfum línu af kóða sem er að fara að snúa þessu NÚLL staf í raunveruleg músina sem er að benda á hnútinn 9, og þá getum við örugglega breytt fyrstur til að benda á þennan gaur hérna. Nú höfum við lista, sem tengist lista, af tveimur þáttum. Og hvað þýðir það líta út í raun eins og hér? Ef við lítum á kóðann, eftir að ég hef gert nákvæmlega það. Ég hef sagt newptr, og í þessari sögu, newptr var að benda á þennan mann. 

Svo láta mig draga eitt í viðbót, og ég ætti að hafa skilið smá meira pláss fyrir þetta. Svo fyrirgefið litla teikningu. Þessi strákur heitir newptr. Það er breyta sem við lýst nokkrum línum áður í takt - bara yfir 25. Og það er að benda á 8. Svo þegar ég segi newptr-> næsta, sem þýðir að fara á strúktúr sem er verið að benda á með newptr, svo hér erum við, fara þangað. Þá örin er að segja að fá næsta sviði, og þá = er að segja setja það gildi þar? Gildið sem var í fyrstu, hvaða gildi var í fyrsta? Fyrst var að benda á þennan hnút, svo það þýðir að þetta ætti nú að benda á þennan hnút. Með öðrum orðum, það sem lítur að vísu fáránlega vandræðum með rithönd mína, það er einföld hugmynd um bara að færa þessar örvarnar í kringum þýðir að kóða með aðeins þetta eina Ferja. Geymið það í fyrst í næsta reit og síðan uppfæra það fyrst raunverulega er. Við skulum fara á undan og fljótur-áfram í gegnum eitthvað af þessu, og líta aðeins á þessu hali sett í bili. Segjum að ég fá til the benda hvar ég finn að næsta sviði einhverjum hnút er NULL. Og á þessum tímapunkti í sögunni, er smáatriði sem ég glossing yfir er að ég hef kynnt aðra músina upp hér í línu 142, forvera músina. Í meginatriðum, á þessum tímapunkti í sögunni, þegar fær listinn langur, Ég þarf svona að ganga hann með tveimur fingrum því ef ég fer of langt, muna í einum lengd lista, getur þú ekki farið aftur á bak. Svo er þessi hugmynd um predptr vinstri fingur minn, og newptr - ekki newptr. Annar músina sem er hér er annar fingur minn, og ég er bara svona að ganga á listanum. Það er hvers vegna það er. En við skulum aðeins íhuga eitt af einfaldari málum hér. Ef næsta sviði sem bendillinn er NULL, hvað er rökrétt vísbendingu? Ef þú ert að fara yfir þennan lista og þú högg NULL músina? Þú ert í lok listanum og svo númerið að þá bæta þetta einn til viðbótar þáttur er tegund af leiðandi tekur þessi hnút lét næsta bendillinn er NULL, þannig að þetta er nú NULL, og breyta því, þó að heimilisfang nýja hnút. Þannig að við erum bara að teikna í kóða á örina sem við brá á sviðinu með því að hækka vinstri hönd einhvers. 

Og ef að ég veifa höndum í bili, bara vegna þess að ég held að það er auðvelt að villast þegar við gerum það í þessa tegund af umhverfi, er að leita að innsetningu á miðjum lista er. En bara innsæi, hvað þarf að gerast ef þú vilt að reikna út þar sem sumir tala tilheyrir í miðjunni er að þú þarft að ganga hana með fleiri en einum fingri, meira en einn músina, reikna út þar sem það tilheyrir með því að haka er þáttur <núverandi einn, > Núverandi einn, og þegar þú kemst að því að stað, þá verður þú að gera þessa tegund af leiknum skel þar sem þú færir ábendingum um mjög vel. Og það svar, ef þú vilt ástæðu gegnum þetta heima á eigin spýtur, snýst um bara að þessum tveimur línum af kóða, en röð af þessum línum er frábær mikilvægt. Vegna þess að ef þú missir hönd einhvers og hækka einhver annar er í rangri röð, aftur, gætir þú endað orphaning lista. Til að draga fleiri hugtök, innsetningu á hali er tiltölulega einfalt. Ísetningu á höfði er líka tiltölulega einfalt, en þú þarft að uppfæra til viðbótar bendi þessum tíma að kreista númer 5 í listanum hér og felur í sér innsetningu í miðju enn meira átak, að mjög vel að setja númer 20 í réttan stað, sem er á milli 17 og 22. Svo þú þarft að gera eitthvað eins og að hafa nýja hnút 20 benda til 22, og þá músina sem tengipunktur er þarf að vera uppfærð síðast? Það er 17, að í raun setja það. Svo aftur, ég fresta raunverulegri kóða fyrir viðkomandi framkvæmd. 

Við fyrstu sýn, það er svolítið yfirþyrmandi, en það er í raun bara óendanlegur lykkja sem er lykkja, lykkja, lykkja, lykkja, og brjóta um leið og þú högg the NULL músina, á hver benda þú getur gert nauðsynlegar innsetningu. Þetta, þá er fulltrúi tengda listanum innsetningu kóða. Það var góður af a einhver fjöldi, og mér finnst eins og við höfum leyst eitt vandamál, en við höfum kynnt í heild hitt. Frankly, höfum við eytt öllum þessum tíma á stóra O og Ω og hlaupandi tíma, að reyna að leysa vandamál hraðar, og hér erum við að taka stórt skref aftur á bak, það líður. Og enn, ef markmiðið er að geyma gögn, mér finnst eins og Gral, eins og ég sagði á mánudag, myndi virkilega vera að geyma það þegar í stað. 

Í staðreynd, gera ráð fyrir að við fengum að setja til hliðar tengist lista fyrir smá stund og við kynntum í staðinn hugmyndina um borð. Og við skulum bara hugsa um borð í smástund sem fylki. Þessi fylki og þetta mál hefur hér nokkrar 26 þætti, 0 í 25, og geri ráð fyrir að þú þurfti klumpur af geymslu fyrir nöfn: Alice og Bob og Charlie og eins. Og þú þarft sumir gögn uppbygging til að geyma þau nöfn. Jæja, getur þú notað eitthvað eins og tengda lista og þú gætir gengið lista innsetning Alice fyrir Bob og Charlie eftir Bob og svo framvegis. Og í raun, ef þú vilt sjá kóðann svona sem innskot, vita að í list2.h við gera nákvæmlega það. Við munum ekki fara í gegnum þennan kóða, en það er afbrigði af fyrstu dæmi sem kynnir eitt annað strúktúr sem við höfum séð áður kallað nemanda, og þá hvað það geymir í raun í tengda listanum er bendi á nemandi uppbyggingu fremur en a einfaldur lítill heiltala, n. Svo átta sig á það er númerið þar sem felur raunverulegt strengi, en ef markmiðið fyrir hendi í raun nú er að takast á við skilvirkni vandamál, myndi það ekki vera gott ef við erum gefið hlut sem heitir Alice, við viljum að setja hana inn á réttum stað í gögn uppbygging, mér finnst eins og það væri mjög gaman að bara setja Alice, hét byrjar með, í fyrsta stað. Og Bob, sem nafn byrjar með B, á öðrum stað. Með fjölda, eða við skulum byrja að kalla það töflu, kjötkássa borð í það, getum við gert nákvæmlega það. Ef við erum að fá nafn eins og Alice, a band eins og Alice, hvar þú setja A-l-i-c-e? Við þurfum hueristic. Við þurfum að virka til að taka inntak eins Alice og aftur svar, "Put Alice á þessum stað." Og þetta virka, þetta svartur kassi, er að fara að vera kölluð kjötkássa virka. 

A kjötkássa virka er eitthvað sem tekur inntak, eins og "Alice", og aftur til þín, yfirleitt, tölugildi stað í nokkur gögn uppbygging þar sem Alice tilheyrir. Í þessu tilfelli, kjötkássa virka okkar ætti að vera tiltölulega einfalt. Kjötkássa virka okkar ætti að segja, ef þú ert að fá "Alice", sem staf að hugsa um? Sú fyrsta. Svo ég horfi á [0], og þá segi ég ef [0] eðli er A, skila fjölda 0. Ef það er B, aftur 1. Ef C það er, aftur 2, og svo framvegis. Allir 0 vísitölu, og sem myndi leyfa mér að setja Alice og þá Bob og þá Charlie og svo framvegis í þessum gögnum uppbyggingu. En það er vandamál. Hvað ef Anita kemur með aftur? Hvar setjum Anita? Nafn hennar, líka byrjar með stafinn A, og mér finnst eins og við höfum gert enn stærri óreiðu á þessu vandamáli. Við höfum nú strax innsetningu, stöðug tími ísetningar, í gögn uppbygging en verr ef línuleg, En hvað getum við gert við Anita í þessu tilviki? Hvað eru tveir valkostir, virkilega? Já? [Námsmaður svar, óskiljanlegur] Jæja, svo að við gætum hafa aðra vídd. Það er gott. Þannig að við getum byggt það út í 3D eins og við ræddum um munnlega á mánudaginn. Við gætum bætt annan aðgang hérna, en geri ráð fyrir að enginn, ég er að reyna að halda þetta einfalt. Í heild Markmið hér er að hafa strax föstu-tíma aðgang, Svo að bæta of mikið flókið. Hvað eru aðrir kostir við að reyna að setja Anita í þessum gögnum uppbyggingu? Já? [Námsmaður svar, óskiljanlegur] Good. Þannig að við gætum flutt allir aðrir niður eins og Charlie nudges niður Bob og Alice, og þá erum við að setja Anita þar sem hún vill í raun að vera. 

Auðvitað, nú, það er aukaverkun af þessu. Þessi gögn uppbygging er sennilega gagnlegur ekki vegna þess að við viljum að setja fólk þegar en vegna þess að við viljum athuga hvort þeir eru það síðar Ef við viljum prenta út allar nöfn í gögn uppbygging. Við erum að fara að gera eitthvað við þessum gögnum endanum. Svo nú höfum við svona ruglaður yfir Alice, sem er ekki lengur þar sem hún á að vera. Né er Bob, né er Charlie. Svo kannski er þetta ekki svo góð hugmynd. En reyndar, þetta er einn kosturinn. Við gætum skipta öllum niður, eða Heck, Anita kom seint til leiks, hví ekki að við setjum bara Anita ekki hér, ekki hér, ekki hér, við skulum bara setja hana aðeins lægri á listanum. En þá byrjar þetta vandamál að flytjast aftur. Þú might vera fær til finna Alice stað, byggt á fyrsta nafnið hennar. Og Bob stað, og Charlie. En þá að leita að Anita, og þú sérð, Hmm, Alice er í leiðinni. Jæja, láttu mig athuga neðan Alice. Bubbi er ekki Anita. Charlie er ekki Anita. Oh, það er Anita. Og ef þú heldur áfram að lest rökfræði alla leið, hvað er versta hlaupandi tíma að finna eða setja Anita í þessari nýju gögn uppbygging? Það er O (n), ekki satt? Vegna þess að í versta falli, það er Alice, Bob, Charlie. . . alla leið niður til að einhver sem heitir "Y", þannig að það er aðeins einn blettur eftir. Sem betur fer, höfum við engan sem heitir "Z", þannig að við setjum Anita á mjög botn. 

Við höfum í raun ekki að leysa þessi vandamál. Svo kannski að við þurfum að kynna þetta þriðja vídd. Og það kemur í ljós, ef við kynna þetta þriðja vídd, við getum ekki gert þetta fullkomlega, en Gral sé að fara að fá föstu-tíma innsetningu og dynamic ísetningar þannig að við þurfum ekki að harða kóða fylki af stærð 26. Við getum sett inn eins mörg nöfn eins og við viljum, en við skulum taka 5-mínútna hlé okkar hér og þá gera það almennilega. Allt í lagi. Ég setti söguna upp nokkuð tilbúnar þarna með því að velja Alice og þá Bob og þá Charlie og svo Anita, hét augljóslega að fara að rekast á við Alice. En spurningin sem við lauk á mánudag með er bara hversu líklegt er það sem þú vilt fá þessar tegundir af árekstrum? Með öðrum orðum, Ef við byrjum að nota þessa töflu uppbyggingu, sem er í raun bara fylki, í þessu tilviki 26 stöðum, hvað ef aðföng eru í staðinn jafnt dreift? Það er ekki tilbúnar Alice og Bob og Charlie og Davíð og svo framvegis í stafrófsröð, það er jafnt dreift yfir með Z. 

Kannski við verðum bara að fá heppinn og við ætlum ekki að hafa tvö A-eða tveir er B með mjög miklar líkur, en eins og einhver benti á, ef við almenn þetta vandamál og ekki 0-25 en, segjum, 0 í 364 eða 65, oft fjölda daga í a dæmigerður ári, og spurði, "Hvað er að líkurnar á því að tveir af okkur í þessu herbergi hafa sama afmæli?" Setja það annar vegur, hvað er líkurnar á því að tveir af okkur hafa nafn sem byrjar á A? Eins konar spurning er það sama, en það heimilisfang rúm, þessari leit rúm, er stærri um er að ræða afmæli, vegna þess að við höfum svo marga fleiri daga á ári en bréf í stafrófinu. Hver er líkur á árekstri? Jæja, við getum hugsað um þetta með því að vangaveltur út stærðfræðina gagnstæða leið. Hvað er líkurnar á engum árekstrum? Jæja, þetta mál hér segir að það er líkur ef það er bara einn maður í þessu herbergi, sem þeir hafa einstakt afmæli? Það er 100%. Vegna þess að ef það er aðeins einn maður í herberginu, hans eða afmæli hennar getur verið af 365 daga úr árinu. Svo gefur 365/365 valkostir mér gildi 1. Svo eru líkurnar á að ræða í augnablikinu bara 1. En ef það er annað maður í herberginu, hvað er líkurnar á því að afmælið þeirra er öðruvísi? Það er aðeins 364 mögulegar daga og hunsa stökk ár, fyrir afmæli þeirra ekki rekast með öðrum einstaklingum. Svo 364/365. Ef þriðji maður kemur í, það er 363/365 og svo framvegis. Svo við höldum margfalda saman þessum brotum, sem eru að fá minni og minni, til að reikna út hvað eru líkurnar á að öll okkar hafa einstakt afmæli? En þá getum við að sjálfsögðu bara taka það svar og flettir því í kring og gera 1 mínus öll þessi, tjáning munum loksins fá Ef þú manst aftan á bækur stærðfræði, það lítur svolítið eitthvað eins og þetta, sem er mun auðveldara að túlka myndrænt. Og þetta grafík hér hefur á x ásnum fjölda afmæli, eða fjöldi fólks með afmæli, og á y ás er líkurnar á leik. Og hvað þetta er að segja er að ef þú ert með, við skulum segja, jafnvel, skulum velja eitthvað eins og 22, 23. Ef það er 22 eða 23 manns í herbergi, líkurnar á því að tveir af þeim mjög fáir eru að fara að hafa sama afmæli er í raun frábær hár, combinatorially. 50% líkur að í flokki aðeins 22 manns, námskeið, nánast, 2 af þeim eru að fara að hafa sama afmæli. Vegna þess að það er svo margar leiðir sem hægt er að hafa sama afmælisdag. Jafnvel verra, ef þú horfir á the réttur-hönd hlið af the sjókort, þann tíma sem þú ert með bekk og 58 nemendur í það, líkurnar á 2 menn sem hafa afmæli er frábær, frábær hár, næstum 100%. Nú, það er eins konar skemmtileg staðreynd um raunveruleikanum. 

En afleiðingarnar, nú, fyrir mannvirki gögn og geyma upplýsingar þýðir að bara hrokafullur þú hafa a ágætur, hreinan og samræmda dreifingu gagna og þú ert nógu stór fylking að passa fullt af hlutum þýðir ekki að þú ert að fara að fá fólk í einstaka stöðum. Þú ert að fara að hafa fyrir árekstra. Svo þessi hugmynd um hakkast, eins og það er kallað, taka inntak eins og "Alice" og nudda það á einhvern hátt og þá fá aftur svar eins 0 eða 1 eða 2. Getting bak sumir framleiðsla frá því aðgerð er plága þessi líkur á árekstri. Og hvernig getum við séð þá árekstra? Jæja, á einu máli, getum við tekið þá hugmynd sem var leiðbeinandi. Við getum bara vakt alla niður, eða kannski, svolítið meira einfaldlega, frekar en allir færa annað, við skulum bara fara Anita til the botn af the laus blettur. Svo ef Alice er í 0, Bob er í 1, Charlie er í 2, við verðum bara að setja Anita í stað 3. Og þetta er tækni í gagnauppbyggingu kallast línuleg leit. Línuleg vegna þess að þú ert bara að ganga þessa línu, og þú ert svona leit að tiltækum stöðum í gögn uppbygging. Auðvitað, þetta devolves í O (n). Ef gögn uppbygging er mjög fullur, það er 25 manns í það nú þegar, og þá kemur Anita eftir, endar hún upp á hvað væri staðsetning Z, og það er allt í lagi. Hún passar ennþá, og við getum fundið hana seinna. 

En þetta var þvert á markmið hraðakstur það upp. Og hvað ef við kynna staðinn þetta þriðja vídd? Þessi tækni er almennt kallað sérstakt chaining, eða hafa keðjur. Og hvað kjötkássa borð er nú þetta tabular uppbyggingu, taflan er bara fylki af ábendingum. En hvað þessir ábendingum benda á er giska hvað? A tengda listanum. Og hvað ef við tökum það besta af báðum þessum heimum? Við notum fylki fyrir fyrstu vísitölur í gögn uppbygging svo við getum þegar í stað að fara til [0] [1], [30] eða svo framvegis, en svo að við höfum sumir sveigjanleika og við getum passa Anita og Alice og Adam og önnur heiti, Við skulum þess í stað öðrum ás vaxa geðþótta. Og við að lokum, eins og með mánudagur, hafa þessi tjáningu getu með tengda listanum. Við getum vaxa gögn uppbygging geðþótta. Einnig gætum við bara gert mikið 2-víddar array, en það er að fara að vera ansi ástand ef einn af línum í 2-víddar array er ekki nógu stórt til viðbótar mann, hvers nafn kemur til að byrja með A. Guð forði okkur að reallocate mikið 2-víddar uppbygging bara vegna þess að það er svo margir sem heita A, sérstaklega þegar það er svo fáir sem heitir Z eitthvað. Það er bara að fara að vera mjög dreifður gögn uppbygging. Svo það er ekki fullkominn með öllum tiltækum ráðum, en nú erum við að hafa að minnsta kosti möguleika að þegar í stað að finna þar sem Alice eða Anita tilheyrir, að minnsta kosti hvað varðar lóðrétta ásnum, og þá erum við bara að ákveða hvar á að setja Anita eða Lísa í tengda listanum. Ef við gerum sama um flokka hluti, hversu fljótt gætum við setja Alice í uppbyggingu eins og þetta? Það er stöðug skipti. Við vísitölu í [0], og ef enginn er, Alice fer í byrjun að tengja lista. En það er ekki a gríðarstór samningur. Vegna þess að ef Anita kemur þá með sumir tala af skrefum síðar, þar er Anita tilheyra? Jæja, [0]. OOP. Alice er nú þegar í að tengja lista. 

En ef við gerum sama um flokkun þessum nöfnum, við getum bara flutt Alice yfir, setja Anita, en jafnvel það er stöðug skipti. Jafnvel ef það er Alice og Adam og öll þessi hinn nöfn, það er í raun ekki að breytast þá líkamlega. Hvers vegna? Þar sem við gerðum bara hér með tengda listanum, hver veit voru þessi hnútar eru samt? Allt sem þú þarft að gera er að flytja brauð mola. Færa örvarnar í kring, þú þarft ekki að líkamlega færa nein gögn um. Þannig að við getum sett Anita, í því tilfelli, þegar í stað. Constant tíma. Þannig að við höfum stöðugt-tími útlit og föstu-tíma Ísetning einhvern eins Anita. En svona oversimplifying heiminn. Hvað ef við viljum síðar að finna Alice? Hvað ef við viljum síðar að finna Alice? Hversu mörg skref er að fara að taka? [Námsmaður svar, óskiljanlegur] Einmitt. Fjölda fólks fyrir Lísa í tengda listanum. Svo það er ekki alveg fullkominn, vegna þess að gögn uppbygging okkar, aftur hefur þetta lóðrétt aðgang og þá hefur það þessi tengd lista hangandi - reyndar, við skulum ekki draga það sem fylki. Það hefur þessi tengd listum hangandi burt af því sem lítur svolítið eitthvað eins og this. En vandamálið er ef Alice og Adam og öll þessi hinn nöfn enda fleiri og fleiri þarna, finna einhver gæti endað að taka fullt af skrefum, bcause þú þarft að fara yfir tengda lista, sem er línuleg aðgerð. Svo í raun, þá er innsetning tími er endanlega O (n), þar sem n er fjöldi staka í listanum. Skipt eftir, skulum geðþótta kalla það m, þar sem m er fjöldi tengdra lista sem við höfum í þessum lóðrétta ásinn. Með öðrum orðum, ef við gerum ráð fyrir sannarlega samræmda dreifingu nöfn, algerlega óraunhæft. Það er augljóslega meira af sumum stöfum en aðrir. 

En ef við gerum ráð fyrir stundu a samræmdu dreifingu, og við höfum n alls fólk og m alls keðjur í boði fyrir okkur, þá er lengd hvers af þessum fjötrum nokkuð einfaldlega er að fara að vera alls, N deilt með fjölda keðjur. Svo N / m. En hér er þar sem við getum verið allt stærðfræðilega snjallt. m er stöðug, því að það er fastur fjöldi þeirra. Þú ert að fara að lýsa array þinn í upphafi, og við erum ekki að breyta stærð á lóðrétta ásinn. Samkvæmt skilgreiningu sem helst fastur. Það er aðeins lárétt ás, svo að segja, sem er að breytast. Svo tæknilega, það er stöðug. Svo nú er innsetning tíma er ansi mikið O (n). Svo að ekki finnst öllum það mikið betur. En hvað er sannleikurinn hér? Jæja, allt að þessu sinni, í margar vikur, við höfum verið að segja O (n ²). O (n), 2 x N ², - n, deilt með 2. . . ECH. Það er bara N ². En nú, í þessum hluta misseris, getum við byrjað að tala um raunverulega heimi aftur. Og N / m er algerlega hraðar en bara n einn. Ef þú ert með þúsund nöfn, og þú brýtur þau upp í mörgum fötunum þannig að þú hefur aðeins tíu nöfn á öllum þessum fjötrum, algerlega að leita tíu hluti er að fara að vera hraðari en þúsund hlutum. Og svo einn af the komandi setur vandamál er að fara að skora á þig að hugsa um einmitt að jafnvel þó, já, aðfellu og stærðfræðilega, þetta er samt bara línuleg, sem sýgur í almennt þegar að reyna að finna það. Í raun og veru, það er að fara að vera hraðari en vegna þessa divisor. Og þannig að það er aftur að fara að vera svona málamiðlun og þetta átök milli kenningar og veruleika, og einn af hnappa byrja beygja á þessum tímapunkti í önn er meira um raunveruleika eitt eins og við að undirbúa eins konar fyrir lok semster er, eins og við kynna the veröld af forritun vefur, þar raunverulega, árangur er að fara að telja vegna þess að notendur þínir eru að fara til byrja að finna og þakka fátækum ákvarðanir hönnun. 

Svo hvernig gera þú fara óður í framkvæmd tengd - kjötkássa borð með 31 þætti? Og dæmið var geðþótta um afmæli. Ef einhver á afmæli 1. janúar eða 1. febrúar munum við setja þá í fötu. Ef það er 2. janúar 2. febrúar 2. mars munum við setja þá í fötu. Það er hvers vegna það var 31. Hvernig lýsa þér kjötkássa borð? Það getur verið frekar einfalt, hnút Tafla er handahófskennt nafn mitt fyrir það, [31]. Þetta gefur mér 31 ábendingum til hnúður, og að leyfa mér að hafa 31 ábendingar til að tengjast listum jafnvel þótt þær keðjur eru upphaflega NULL. Hvað vil ég setja ef ég vil geyma "Alice", "Bob", "Charlie"? Jæja, þurfum við að vefja þá hluti í uppbyggingu vegna þess að við þurfum Alice að benda á Bob, að benda á Charlie, og svo framvegis. Við getum ekki bara nöfnin ein, þannig að ég gæti búið til nýtt skipulag kallast hnút hér. 

Hvað er raunverulegt hnút? Hvað er hnúturinn í þessu nýja tengda listanum? The fyrstur hlutur sem kallast orð, er fyrir nafn viðkomandi. Lengd, væntanlega til, að hámarks lengd nafni manna er, hvað það er, 20, 30, 40 stafir í brjálaður tilvikum horn, og 1 er fyrir hvað? Það er bara auka NULL karakter, \ 0. Svo þessi hnútur er umbúðir "eitthvað" inni í sig, en það lýsir líka bendi heitir næsta svo að við getum keðja Alice til Bob til Charlie og svo framvegis. Getur verið NULL en ekki endilega að vera. Einhverjar spurningar um þessi kjötkássa matskeið? Já? [Námsmaður spyrja spurningu, óskiljanlegur] An array - góð spurning. Hvers vegna er þetta bleikja orð í fjölda frekar en bara char *? Í þessu nokkuð handahófskennt dæmi, gerði ég ekki vilja til að grípa að malloc fyrir hvert upphaflegu nöfnum. Mig langaði til að lýsa hámarks magn af minni fyrir streng svo að ég gæti afrita í uppbyggingu Alice \ 0 og ekki þurfa að takast á við malloc og frjáls og þess háttar. En ég gæti gert það ef ég vildi vera meira meðvitaður um notkun rúm. Góð spurning. Svo skulum reyna að alhæfa frá þessu og einbeita sér afganginn í dag á gagnauppbyggingu almennt og önnur vandamál sem við getum leyst með sömu grundvallaratriði jafnvel þótt gögn uppbygging sjálfir getur verið mismunandi í einstökum atriðum þeirra. 

Svo kemur í ljós í tölvunarfræði, eru tré mjög algeng. Og hægt er að hugsa um tré konar eins og ættartré, þar er sumir rætur, sumir matriarch eða patriarcha, amma eða afi eða fyrr til baka, undir sem eru mamma og pabbi og ýmsir systkini eða þess háttar. Svo hefur tré uppbyggingu hnúður og það hefur börn, yfirleitt 0 eða fleiri börn fyrir hvern hnút. Og sumir af the hrognamál sem þú sérð á þessari mynd hér er einhver af litlu krökkunum eða grandkids á brúnir sem hafa ekki örvarnar berast frá þeim, þeir eru svokölluð lauf, og einhver á inni er innri hnút, þú getur hringt í það neitt meðfram þeim línum. En þessi uppbygging er ansi algengt. Þessi er svolítið handahófskennt. Við höfum eitt barn til vinstri, höfum við þrjú börn á hægri, tvö börn á the botn vinstri. Þannig að við getum haft mismunandi-stór tré, en ef við byrjum að staðla hlutina, og þú gætir muna þetta frá vídeó Patrick um tvöfaldur leit frá fyrri stutt netinu, tvöfaldur leita þarf ekki að koma til framkvæmda með fjölda eða stykki af pappír á karta. Segjum að þú vildir geyma númer þitt í flóknari gögn uppbygging. Þú getur búið til tré eins og this. Þú gætir hafa hnút lýst í C, og að hnúturinn getur haft að minnsta kosti tvo þætti innan þess. Einn er númerið sem þú vilt geyma, og hitt er - ja, við þurfum eitt. Hin er börn þess. Svo er hér önnur gögn uppbygging. This tími, er hnút skilgreind sem geyma númer N og þá tveir ábendingum, vinstri barn og hægri barn. Og þeir eru ekki handahófskennt. Hvað er áhugavert um þetta tré? 

Hvað er mynstur í því hvernig við höfum sett þetta út eða hvernig Patrick lagði fram í myndbandinu hans? Það er góður af augljóst að það er einhver flokkun gerast hér, en það er einföld regla? Já? [Námsmaður svar, óskiljanlegur] Perfect. Ef þú litið á þetta, þú sérð litla tölur til vinstri, stór númer á vinstri, en það er satt fyrir hvern hnút. Fyrir hvern hnút, vinstri barn hennar minna en það, og hægri barn hennar meira en það. Hvað þýðir þetta er nú ef ég vil leita þessi gögn uppbygging fyrir, segjum, fjölda 44, Ég verð að byrja á rót, því eins og við öll þessi flóknari gögn uppbygging nú, við höfum bara bendi á eitt, í byrjun. Og í þessu tilfelli, upphafið er rót. Það er ekki vinstri enda, það er rót þessa uppbyggingu. Svo sé ég hérna er 55, og ég er að leita að 44. Hvaða átt ég vil fara? Jæja, ég vil fara til vinstri, því augljóslega, til hægri er að fara að vera of stór. Svo taka hér, þú ert konar eðli chopping gegnum tréð í helmingur vegna þess að þú ert aldrei að fara niður á hægra megin. Svo nú er ég að fara frá 55 til 33. Það er of lítið af mörgum. Ég er að leita að 44, en nú veit ég hvort 44 er í þessu tré, ég get farið augljóslega til hægri. Svo aftur, ég pruning trénu í tvennt. Það er ansi mikið eðli eins símaskránni. Það er eins og það sem við gerðum með pappíra á töfluna, en það er flóknari mannvirki sem gerir okkur kleift að í raun að gera þetta skipta og sigra með hönnun reiknirit, og í raun fara yfir skipulag eins og þetta - Úpps. Fara yfir skipulag eins og þetta, þar sem það er bara "fara þessa leið eða fara þessa leið," þýðir öll þessi númer sem beygði hug þinn í fyrstu þegar útfæra hana í kafla eða ganga í gegnum það heima, að tvöfaldur leit með endurkvæmni eða endurtekning, það er sársauki í hálsinum. Finndu miðju frumefni, þá gera lokið máli mínu upp eða niður. 

Það er fegurð í þessu vegna þess að við getum nú notað endurkvæmni aftur en miklu meira eðlilega. Reyndar, ef þú ert á númer 55 og þú vilt að finna 44, þú ferð eftir í þessu tilfelli, þá hvað gerir þú? Þú keyra nákvæmlega sama reiknirit. Þú athuga gildi hnút, þá fara til vinstri eða hægri. Síðan sem þú athuga gildi hnút, fara til vinstri eða hægri. Þetta er fullkomlega til þess fallin að endurkvæmni. Svo jafnvel þó í fortíðinni sem við höfum gert nokkrar nokkuð handahófskennt dæmi felur endurkvæmni það þarf ekki að vera endurkvæma með stuctures gögn, einkum tré, það er fullkominn umsókn um þessa hugmynd um að taka vandamál, skar það, og þá leysa sömu tegund, en minni, program. 

Svo er það önnur gögn uppbygging sem við getum kynna. Þessi er hönnuð við fyrstu sýn að líta dulinn, en þetta er ótrúlegt. Þannig að þetta er gögn uppbygging kallast trie, trie, sem er arfur af orðinu sókn, sem er ekki áberandi aftur TRY-Val, en það er það sem heimurinn kallar þetta. Reynir. T-r-i-e. Það er tré uppbyggingu einhvers konar, en hver af hnúður í trie virðist vera það? Og þetta er svolítið villandi vegna þess að það er eins konar styttur. En það lítur út eins og hver hnútur í trie er í raun fylki. Og jafnvel þó að höfundur þessarar myndinni hefur ekki sýnt það, í þessu tilfelli, þetta trie er gögn uppbygging sem tilgangur í lífinu er að geyma orð eins og A-l-i-c-e eða B-o-B. Og með hvaða hætti þessi gögn birgðir Alice og Bob og Charlie og Anita og svo framvegis það notar fylki þar á að geyma Lísa í trie, við byrjum á rót hnút, sem lítur út eins og fylki, og það hefur verið skrifað í merki shorthand. Höfundur sleppt ABCDEFG því það voru engin nöfn með því. Þeir sýndu bara M og P og T, en í þessu tilviki, við skulum fara burtu frá Alice og Bob og Charlie að sumir nöfn sem eru hérna. Maxwell er í raun í þessari mynd. Svo hvernig did höfundur verslun M-a-x-W-E-L-L? Hann byrjaði á rót hnút, og fór til [M], svo u.þ.b. 13, 13. stað í fylkinu. Þaðan, það er bendir. Bendi leiðir til annað fylki. Þaðan höfundur verðtryggð í þessi fylki á stað A, eins og sjá má þar efst til vinstri, og þá er hann eða hún eftir að bendi til annars fylking, og fór í músina á staðsetningu X. Síðan í næsta array staðsetningu W, E, L, L, og svo framvegis, og að lokum, við skulum í raun að reyna að setja mynd í þetta. Hvað hnút líta út í kóða? A hnútur í trie inniheldur fjölbreytta ábendingum til fleiri hnúta. En það er einnig fengið að vera einhvers konar Boolean gildi, að minnsta kosti í þessari framkvæmd. Ég gerst að kalla það is_word. Hvers vegna? Því þegar þú ert að setja Maxwell, þú ert ekki að setja eitthvað í þessum gögnum uppbyggingu. Þú ert ekki að skrifa M. Þú ert ekki að skrifa X. Allt sem þú ert að gera er að fylgja ábendingum. Músina sem sýnir m, síðan á músina sem sýnir A, þá bendillinn sem táknar X, þá W, E, L, L, en það sem þú þarft að gera í lok er tegund af að fara, skoða, náði ég þessa staðsetningu. Það var orð sem endar hér í gögn uppbygging. 

Svo hvað trie er mjög fyllt með og höfundur valdi til að tákna þessi terminuses með lítið þríhyrninga. Þetta bara þýðir að sú staðreynd Þessi þríhyrningur er hér, þetta Boole gildi satt þýðir að ef þú ferð aftur í trénu, sem þýðir orð heitir Maxwell er í þessu. En orð foo, til dæmis, er ekki í trénu, því að ef ég byrja á rót hnút hérna efst, Það er engin f músina, ekki o músina, ekki o músina. Foo er ekki nafn á þessari orðabók. En með því móti, Turing, T-U-r-i-n-g. Aftur, var ég ekki að geyma t eða u eða r eða ég eða n eða g. En ég gerði verslun í þessum gögnum uppbyggingu gildið satt vegur niður í hnút - í trénu með því að setja þetta Boolean gildi is_word satt. Svo er trie konar þetta mjög áhugavert meta uppbyggingu, þar sem þú ert í raun ekki að geyma orðin sig af þessu tagi orðabók. Til að vera skýr, þú ert bara að geyma já eða nei, það er orð sem endar hér. 

Nú hvað er óbeint? Ef þú ert með 150.000 orð í orðabók sem þú ert að reyna að geyma í minni að nota eitthvað eins og tengda listanum, þú ert að fara að hafa 150.000 hnúta í tengda listanum þínum. Og finna einn af þessum orðum í stafrófsröð gæti tekið O (n) tíma. Línulegum tíma. En í tilviki hér á trie, hvað er í gangi þegar að finna orð? Það kemur í ljós fegurð hér er að jafnvel ef þú hefur 149.999 orð þegar í þessari orðabók, sem útfærð með þessum gögnum uppbyggingu, hversu mikinn tíma tekur það að finna eða setja eina í viðbót í það, eins og Alice, Alice? Jæja, það er bara 5, kannski 6 skref fyrir slóð staf. Þar sem presense annarra nöfn í uppbyggingu ekki að komast í the vegur af að setja Alice. Þar að auki, finna Alice þegar það eru 150.000 orð í þessari orðabók ekki fá í leiðinni að finna Alice yfirleitt, því Alice er. . . . . hér, vegna þess að ég fann Boolean gildi. Og ef það er engin Boolean satt, þá Alice er ekki í þessum gögnum uppbyggingu orða. Með öðrum orðum, að keyra tíma að finna hluti og setja hluti í þessu nýja gögn uppbyggingu trie er O - það er ekki n. Þar sem presense af 150.000 manns hefur ekki áhrif á Alice, virðist. Svo við skulum kalla það k, þar sem k er Hámarkslengd orð í ensku sem er yfirleitt ekki meira en 20-eitthvað stafir. Svo er k fasti. Svo Gral við virðast hafa fundið nú er þessi af a trie, stöðug tíma fyrir sett inn, í leit fyrir úrfellingum. Vegna þess að fjöldi af hlutur þegar í uppbyggingu, sem eru ekki einu sinni líkamlega þar. Aftur, þeir raða bara af köflóttur út, já eða nei, hefur engin áhrif á framtíð í gangi á sínum tíma. 

En það hlýtur að vera a grípa, annars myndum við ekki sóa svo miklum tíma á öllum þessum gagnauppbyggingu bara að lokum fá til the leyndarmál einn sem er ótrúlegt. Svo hvaða verð erum við að borga til að ná þessu hátignar hér? Space. Þessi hlutur er gegnheill. Og ástæða þess að höfundur ekki kynna það hér, eftir að allir þessir hlutir sem líta út eins og fylki, hann ekki draga restina af trénu, en afgangurinn af trie, vegna þess að þeir eru bara ekki viðeigandi að sögunni. En öll þessi hnúður er frábær breiður, og sérhver hnútur í trénu tekur upp 26 eða í raun, gæti verið 27 stafir því í þessu tilfelli var ég þar pláss fyrir úrfellingarmerki svo að við gætum hafa apostrophized orð. Í þessu tilfelli er þetta breiður fylki. Svo jafnvel þótt þeir séu ekki picutured, þetta tekur allt gríðarlegt magn af vinnsluminni. Sem gæti verið fínn, especilly í nútíma vélbúnaði, en það er tradeoff. Við fáum minni tíma með því að eyða meira pláss. Hvar er þetta að fara allt? Jæja, við skulum gera - við skulum sjá hér. Við skulum gera stökk til þetta strákur hér. 

Trúa það eða ekki, eins skemmtilegt og C hefur verið um nokkurt skeið, við erum að ná að benda á önn þar sem það er kominn tími til að skipta yfir í það meira nútíma. Hlutina á hærra stig. Og jafnvel þó að á næstu vikum við munum samt halda áfram að sökkva okkur í heimi ábendingum og minni stjórnun að fá þessi þægindi sem við getum þá byggja á, enda leikur er að lokum að kynna, kaldhæðni, ekki þetta tungumál. Við munum eyða, eins og 10 mínútur að tala um HTML. Allt HTML er er Markup Language, og hvað Markup Language er er þessi röð af opnum sviga og loka sviga sem segja 'gera þetta feitletrað' "Gera þetta skáletrun 'gera þessa miðju." Það er ekki allt sem vitsmunalega áhugavert, en það er frábær gagnlegt. Og það er vissulega omnipresent þessa dagana. En hvað er öflugur um heim HTML og vefur forritun almennt, er að byggja dynamic hluti, skrifa kóða í tungumálum eins og PHP eða Python eða Ruby eða Java eða C #. Raunverulega, hvað tungumál þitt val er, og búa til HTML virk. Búa eitthvað sem kallast CSS virk. Cascading Style Sheets, sem er einnig um fagurfræði. Og svo jafnvel þó, í dag, ef ég fer til einhvers website eins kunnuglega Google.com, og ég fer að skoða, verktaki, skoða uppspretta, sem kannski þú hefur gert áður, en að fara að skoða uppspretta, þetta efni lítur sennilega nokkuð dulinn. En þetta er undirliggjandi kóða sem útfærir Google.com. Á framenda. Og í raun er þetta allt Fluffy fagurfræði efni. Þetta er CSS upp hér. Ef ég halda að fletta niður fáum við lit-dulmáli efni. Þetta er HTML. Kóða Google lítur út eins og óreiðu, en ef ég opna reyndar upp aðra glugga, getum við séð nokkur uppbygging að þessu. Ef ég opna þetta upp, taka hér, það er svolítið læsilegri. Við ætlum að sjá áður en langt þetta merki, [orðið] er tag, HTML, höfuð, líkama, div, handrit, texta svæði, span, miðju, div. Og þetta er líka svona Cryptic-útlit á fyrstu sýn, en alla þessa óreiðu fylgir ákveðin mynstur og repeatable mynstur, þannig að þegar við fá grunnatriði niður, munt þú vera fær um að skrifa kóða svona og þá vinna númer svona með enn öðru tungumáli, sem heitir JavaScript. Og JavaScript er tungumál sem keyrir inni í vafra dag sem við notum á Harvard námskeiðum, til að versla auðvitað tól sem Google Maps notar til að gefa þér allt fullt af krafti, Facebook gefur þér til að sýna augnablik stöðu uppfærslur, Twitter notar það til að sýna þér kvak stað. Allt þetta munum við byrja að sökkva okkur inn En til að fá það þurfum við að skilja lítið eitthvað um internetið. Þetta myndband hér er bara mínútu löng, og við skulum gera ráð fyrir því að nú er þetta í raun, hvernig Netið virkar sem beitu fyrir hvað er um að koma. Ég gefa þér "Warriors á Netinu." 

[♫ Slow kór tónlist ♫] [Male sögumaður] Hann kom með skilaboð. Með siðareglur allt sitt. [♫ Festa Raftónlist ♫] Hann kom í heiminn á flottum eldveggir, uncaring leið, og hættum miklu verra en dauðinn. Hann er fljótur. Hann er sterkur. Hann er TCP / IP, og hann er með netfangið þitt. Warriors á Netinu. [Malan] Næsta vika, þá. The Internet. Vefur forritun. Þetta er CS50. [CS50.TV]