[Powered by Google Translate] [Semajno 6, daŭrigis] [Davido J. Malan] [Universitato Harvard] [Jen CS50.] [CS50.TV] Ĉi tiu estas CS50 kaj ĉi tiu estas la fino de semajno 6. Do CS50x, unu el Harvard unuaj kursoj implikita en la edX iniciato ja debutis la pasinta lundo. Se vi ŝatus ricevi bildon de aliaj en la interreto nun sekvi kune kun vi povas direkti al x.cs50.net. Tio alidirektilo vin al la taŭga loko sur edx.org, kiu estis kie ĉi tiu kaj aliaj kursoj de MIT kaj Berkeley nun vivas. Vi devos registri konton, vi trovos ke la materialo estas plejparte la sama kiel vi havis ĉi semestro, kvankam kelkaj semajnoj prokrastis, kiam ni atingos ĉiu lerta. Sed kion studentoj en CS50x nun vidas estas interfaco tute kiel ĉi tiu. Ĉi tio, ekzemple, estas Zamyla stirante la walkthrough por problemo aro 0. Sur ensalutante al edx.org, a CS50x studento vidas la varoj de aĵoj vi atendus vidi en kurso: la prelego por la lundo, prelego dum Merkredo, diversaj mallongaj, la problemo aroj, la walkthroughs, PDFs. Krome, kiel vi vidas tie, maŝino tradukoj de la angla transskriboj en la ĉinan, japanan, Hispana, Itala, kaj tuta amaso de aliaj lingvoj kiuj certe estos malperfekta kiel ni ruliĝi ilin el programmatically uzante iun nomita API, aŭ apliko programado interfaco, de Google kiu nin permesas konverti angla al tiuj aliaj lingvoj. Sed danke al la mirinda spirito de iu cent-plus volontuloj, hazarda homoj en la Interreto kiuj afable proponis al implikiĝi en ĉi tiu projekto, ni iom post iom plibonigi la kvaliton de tiuj tradukoj por havi la homoj korekti la erarojn ke nia komputiloj faris. Do rezultas ni kelkajn pli studentoj aperas lunde ol ni komence atendis. Fakte, nun CS50x havas 100.000 homoj sekvi kune hejme. Do realigi vi ĉiuj estas parto de tiu inaŭgura klaso de fari ĉi tiu kurso en komputiko eduko pli ĝenerale, pli vaste, atingebla. Kaj la realaĵo estas nun, kun kelkaj el tiuj amasaj retaj kursoj, ili ĉiuj starti kun tiuj tre altaj nombroj, kiel ni ŝajnas esti farita tie. Sed la celo, finfine, por CS50x estas vere akiri tiom da homoj al la linio fino ebla. Por dezajno, CS50x tuj proponos el tiu pasinteco lundo tuta vojo tra Aprilo 15, 2013, por ke homoj, kiuj havas lernejon devontigoj aliloke, laboro, familio, aliaj konfliktoj kaj similaj, havas iom pli fleksebleco kun kiu bucear en cxi tiun kurson, kiu, sufiĉas diri, estas sufiĉe ambicie farita se nur super la kurson de nur tri monatoj dum kutima semestro. Sed tiuj studentoj estos tuŝas la saman problemon aroj, vidante la sama enhavo, havi aliron al la sama pantalono kaj similaj. Do realigi ke ni ĉiuj vere en ĉi kune. Kaj unu el la fino celoj de CS50x ne estas nur por ricevi tiom da uloj al la linio kaj donu al ili tiun ĵus malkovrita kompreno de komputiko kaj programado sed ankaŭ havi ilin havas ĉi dividis sperto. Unu el la difinaj trajtoj de 50 en la campus, ni esperas, estis ĉi tia komunuma sperto, por pli bona aŭ por malbona, kelkfoje, sed havante tiujn homojn turni al la maldekstra kaj la dekstra, kaj oficejo horoj kaj la hackathon kaj la foiro. Ĝi estas iom pli malfacile fari tion persone kun uloj en linio, sed CS50x finos en aprilo kun la unua iam CS50 Expo, kiu estos interreta adapto de nia ideo de la foiro kie tiuj miloj da studentoj estos ĉiuj esti invitita al prezenti 1 - 2-minuta video, ĉu screencast de ilia fina projekto aŭ video el ili flirtis saluton kaj rakontis pri sia projekto kaj demoing ĝin, multe ŝatas vian antaŭuloj faris tie sur kampuso en la foiro, por ke per semestro la fino, la espero estas havi tutmondan ekspozicio de la CS50x studentoj 'fino projektoj, multe kiel tiu, kiu vin atendas ĉi decembro ĉi tie sur campus. Do pli en kiuj en la monatoj veni. Kun 100.000 studentoj, tamen, venas bezono por kelkaj pli CAS. Donita ke vi infanoj estas brilis la pulbazaro tie kaj prenante CS50 pluraj semajnoj anticipe de ĉi tiu materialo ĵeto al la homoj sur edX, realigi ni amus impliki kiel multaj de niaj propraj studentoj kiel eble en tiu iniciato, ambaŭ dum la semestro tiel kiel ĉi tiu vintro kaj ĉi venas printempo. Do se vi ŝatus implikiĝi en CS50x, aparte aliĝi en sur CS50x diskuti, la edX versio de CS50 diskuti, kiu multaj de vi estas uzanta la kampuso, la linio bulteno tabulo, bonvolu fari kapon por ke URL, ni scias, kiu vi estas, ĉar ni ŝatus konstrui teamo de studentoj kaj personaro kaj fakultato egale sur kampuso kiuj simple ludas kune kaj helpi eksteren. Kaj kiam ili vidas demando kiu estas familiara al ili, vi aŭdas lernanto informis iu cimo ie tie en iu lando en la interreto kaj ke ringoj sonorilo ĉar vi tro havis tiun saman demandon en via d-salono iun tempon, mi esperas vi povas chime en kaj dividi viajn propra sperto. Do bonvolu partopreni, se vi ŝatus. Komputika kursoj en Harvard havas iom de la tradicio, CS50 inter ili, havi kelkajn vestojn, iuj vestojn, por ke vi povas porti fiere ĉe semestro la fino, dirante sufiĉe alten, ke vi finis CS50 kaj prenis CS50 kaj similaj, kaj ni ĉiam provas impliki studentoj en ĉi tiu procezo kiel eble plej multe, per kiu ni invitas, ĉirkaŭ ĉi tempo de la semestro, studentoj submeti dezajnoj uzante Photoshop, aŭ kion ajn ilo de elekto vi ŝatus uzi se vi estas reĝisoro, submeti dezajnoj por T-ĉemizoj kaj sweatshirts kaj ombreloj kaj iom bandanas por hundoj ni nun havas kaj similaj. Kaj ĉio estas tiam - la gajnantoj ĉiujare estas poste elmetis en la paso de afiŝinto ĉe store.cs50.net. Ĉio estas vendita je kosto tie, sed la retejo ĵus kuras mem kaj permesas al la homo elektus la koloroj kaj desegnoj, ke ili ŝatas. Do mi pensis ke ni volas nur konigi kelkajn el la pasinta jaro dezajnoj kiuj estis sur la retejo krom ĉi tie, kiu estas jara tradicio. "Ĉiu tago mi seg Faultn" estis unu el la sendoj pasinta jaro, kio estas ankoraŭ disponebla tie por lernantoj. Ni havis ĉi tiu, "CS50, Fondita 1989." Unu el niaj Bowdens, Rob, estis tre populara pasintjare. "Team Bowden" naskiĝis, tiu dezajno donita, inter la supro vendistoj. Kiel estis tiun ĉi tie. Multaj homoj havis "Bowden Febro" laŭ la vendoj protokolojn. Rimarkas ke tiu povis nun estos via dezajno tie, sur la interreto. Pliaj detaloj sur ĉi en la sekva problemo aroj veni. Unu pli ilo: vi havis iun ekspozicion kaj espereble nun iuj manoj sur sperto kun GDB, kiu estas, kompreneble, erarserĉilo kaj permesas manipuli via programo ĉe sufiĉe malalta nivelo, fari kion specoj de aferoj? Kion GDB lasu vin fari? Yeah? Donu al mi ion. [Studenta respondo, nekomprenebla] Bona. Paŝo en funkcio, do vi ne nur devas tajpi kuri kaj havas la programon bato per sia tuteco, presi el aferojn cxefeligo. Pli ĝuste, vi povas treti tra ĝi linio por linio, ĉu tajpi sekva iri linio por linio por linio aŭ paŝo bucear en funkcio, tipe kiu vi skribis. Kion alian ne GDB lasu vin fari? Yeah? [Studenta respondo, nekomprenebla] Presi variabloj. Do se vi volas fari iom introspekto ene de via programo sen devi recurrir al skribi printf deklaroj tuta loko, vi povas simple presi variablo aŭ vidigi variablo. Kion alian vi povas fari kun erarserĉilo kiel GDB? [Studenta respondo, nekomprenebla] Ekzakte. Vi povas agordi breakpoints; vi povas diri ripozon ekzekuto ĉe la ĉefa funkcio aŭ la foo funkcio. Vi povas diri ripozon ekzekuto ĉe linio 123. Kaj breakpoints estas vere potenca tekniko ĉar se vi havas ĝeneralan senton de kie via problemo probable estas, vi ne devas perdi tempon tretante per la programo totalo. Vi povas esence salti rajtas tie kaj tiam komenci tajpi - tretante tra ĝi kun paŝo aŭ apud aŭ similaj. Sed la kaptita kun iu kiel GDB estas ke ĝi helpas vin, la homo, trovi vian problemojn kaj trovi vian cimojn. Ĝi ne nepre trovos ilin tiom por vi. Do ni enkondukis la alia tago style50, kiu estas mallonga komandlinio ilo kiu provas stylize via kodo iom pli pure ol vi, la homo, povus havi farita. Sed tio, ankaŭ, estas vere nur estetika afero. Sed ĝi rezultas tie estas tio alia ilo nomita Valgrind ke estas iom pli arcano uzi. Lia eligo estas atrociously críptico unuavide. Sed estas mirinde utila, speciale nun ke ni estas en la parto de la termino kie vi komencas uzi malloc kaj dinamika memoro atribuo. Aĵoj povas iri vere, vere malĝusta rapide. Ĉar se vi forgesos liberigi vian memoron, aŭ vi dereference iuj NULL pointer, aŭ vi dereference iuj rubo pointer, kio estas tipe la simptomo, ke rezultoj? Seg kulpo. Kaj vi ricevos tiun kernon dosiero de iu nombro da kilobajtoj aŭ megabajtoj kiu reprezentas la staton de via programo memoro kiam frakasis, sed via programo finfine seg kulpoj, segmentación kulpo, kiu signifas iun malbona okazis preskaŭ ĉiam rilatigita al la memoro-rilatajn eraro, ke vi faris ie. Do Valgrind helpas vin trovi aĵojn kiel ĉi tio. Ĝi estas ilo kiu vi kuros, kiel GDB, post vi kompilis vian programon, sed anstataŭ kuri via programo rekte, vi kuros Valgrind kaj pasas al ĝi vian programon, kiel vi faras kun GDB. Nun, la uzado, por atingi la plej bonaj speco de eligo, Estas iom longa, do dekstre tie sur la pinto de la ekrano, vi vidos Valgrind-v. "-V" preskaŭ universale signifas abundajn kiam vi uzas programojn sur Linukso komputilo. Do tio signifas kraĉi el pli datumoj ol vi povus defaŭlte. "- Fugon-check = plena." Tiu estas nur diras ĉeko por ĉiuj eblaj memoro fugoj, erarojn ke mi faris. Ĉi tio, ankaŭ, estas komuna paradigmo kun Linukso programoj. Ĝenerale, se vi havas komandlinio argumento kiu estas "switch", ke tio devus ŝanĝi la programon de la konduto, kaj ĝi estas sola litero, estas-v, sed se ke tio ŝanĝis, kun nur dezajno de la programisto, estas plena vorto aŭ serio da vortoj, la komanda linio argumento komenciĝas per -. Ĉi tiuj estas nur homaj konvencioj, sed vi vidas ilin ĉiam pli. Kaj poste, fine, "a.out" estas la arbitra nomo por la programo en ĉi tiu aparta ekzemplo. Kaj jen iuj reprezentanto eligo. Antaŭ ol ni rigardu kion tio povus signifi, ke mi transiru al fragmento de kodo super tie. Kaj lasu min movi tiun de la vojo, baldaŭ, kaj ni rigardu memory.c, kiu estas tiu mallonga ekzemplo tie. Do en tiu programo, mi zomi en la funkcioj kaj demandoj. Ni havas funkcion ĉefa kiu nomas funkcio, f, kaj tiam kion signifas f procedi por fari, en iomete teknika angla? Kion f procedi fari? Kion pri mi komencu per linio 20, kaj la stelo situo ne gravas, sed mi nur esti konsekvenca tie kun lasta prelego. Kio estas linio 20 vi por ni? Sur la maldekstra flanko. Ni rompos ĝin plu. Int * x: kion signifas tiu fari? Okay. Ĝi estas deklari pointer, kaj nun ni estos eĉ pli teknika. Kion tio signifas, tre konkrete, por deklari puntero? Iu alia? Yeah? [Studenta respondo, nekomprenebla] Tro multe. Do vi legas la dekstra flanko de la egala signo. Ni enfokusigi nur maldekstre, ĝuste sur int * x. Tiu signifas "deklari" puntero, sed nun estu la plonĝi en profundan al tiu difino. Kion tio konkrete, teknike signifas? Yeah? [Studenta respondo, nekomprenebla] Okay. Oni preparas por savi adreson en memoro. Bona. Kaj ni prenos ĉi unu paŝon; ĝi estas deklari variablon, x, jen 32 bitoj. Kaj mi scias ke estas 32 bitoj ĉar -? Ne ĉar ĝi estas int, ĉar ĝi estas puntero en ĉi tiu kazo. Koincido, ke ĝi estas unu kaj la sama kun int, sed la fakto ke estas la stelo ne signifas ĉi estas puntero kaj en la aparaton, kiel kun multaj komputiloj, sed ne ĉiuj, punteros estas 32 bitoj. Sur pli moderna aparataro kiel la lasta Macs, la lasta PC, vi eble havas 64-bitan punteros, sed en la aparaton, tiuj aferoj estas 32 bitoj. Do ni normigi sur tio. Pli konkrete, la historio iras tiel: Ni "deklari" puntero; kion tio signifas? Ni preparos por stoki memoro adreso. Kion tio signifas? Ni krei variablon nomitan x kiu okupas 32 bitoj kiu baldaŭ stoki la adreson de entjero. Kaj tio estas probable pri kiel preciza kiel ni povas akiri. Ĝi estas bone movi antaŭen al simpligi la mondo kaj nur diras deklari puntero nomata x. Deklari pointer, sed rimarkas kaj komprenas kio vere okazas eĉ en nur tiuj malmultaj gravuloj. Nun, ĉi tiu estas preskaŭ iom pli facila, kvankam ĝi estas pli longa esprimo. Do kio estas tiu faras, ke tio emfazita nun: "malloc (10 * sizeof (int))," Jes? [Studenta respondo, nekomprenebla] Bona. Kaj mi prenos ĝin tie. Oni atribuas la eron de memoro por dek entjeroj. Kaj nun ni plonĝi en iomete pli profunde; ĝi estas atribuo eron de memoro por dek entjeroj. Kio malloc tiam reveni? La adreso de tiu bloko, aŭ, pli konkrete, la adreso de la unua bitoko de tiu bloko. Kiel do mi, la programisto, scii kie tio eron de memoro finoj? Mi scias, ke ĝi estas apuda. Malloc, per difino, donos al vi apudan eron de memoro. Neniu mankojn en ĝi. Vi havas aliron al ĉiu bajto en tiu bloko, malantaŭo al malantaŭo al malantaŭo, sed kiel mi scias kie la fino de ĉi tiu bloko de memoro estas? Kiam vi uzas malloc? [Studenta respondo, nekomprenebla] Bona. Vi ne. Vi devas memori. Mi devas memori ke mi uzis la valoron 10, kaj mi eĉ ne ŝajnas esti farita, ke ĉi tie. Sed la onus estas tute en mi. Strlen, kiu ni fariĝis iomete dependis por kordoj, laboras nur pro tiu konvencio havi \ 0 aŭ tiu speciala nul karaktero, NUL, fine de linio. Tio ne veras por nur arbitra pecoj de memoro. Ĝi dependas de vi. Do linio 20, tiam, allocates eron de memoro kiu povas stoki dek entjeroj, kaj stokas la adreso de la unua bitoko de tiu bloko de memoro en la variablo nomata x. Ergo, kiu estas puntero. Do linio 21, bedaŭrinde, estis eraro. Sed unue, kio estas tio faras? Oni diras vendejo en loko 10, 0 indeksita, de la bloko de memoro nomata x la valoron 0. Do rimarki kelkajn aferojn okazas. Kvankam x estas puntero, memori el paro semajnoj ke vi povas ankoraŭ uzi la tabelo-stilo kvadrata krampo skribmaniero. Ĉar tio estas vere mallonga mano skribmaniero por la pli kripta-aspekta puntero aritmetiko. kie ni devus fari ion kiel jene: Prenu la adreso x, movi 10 makuloj super, tiam iri tien al kiom adreso estas stokita en tiu loko. Sed sincere, ĉi tiu estas nur abomena por legi kaj akiri komforta kun. Do la mondo kutime uzas la rektaj krampoj nur ĉar ĝi estas tiel multe pli homa-amika legi. Sed tio kio vere okazas sub la kapuĉo; x estas adreso, ne tabelo, per si mem. Do tiu estas stokante 0 je situo 10 en x. Kial ĉi tiu malbona? Yeah? [Studenta respondo, nekomprenebla] Ekzakte. Ni nur atribuis dek ints, sed ni kalkulu de 0 kiam programado en C, do vi havas aliron al 0 1 2 3 4 5 6 7 8 9, sed ne 10. Do ĉu la programo tuj seg kulpo aŭ ĝi ne estas. Sed ni ne vere scias, kio estas speco de _nondeterministic_ konduto. Vere dependas sur ĉu ni preni bonŝanca. Se ĝi rezultas ke la mastruma sistemo ne gravas se mi uzas tiun ekstran bajto, kvankam ne donis ĝin al mi, mia programo eble ne frakasi. Estas kruda, estas kalesxon, sed vi povus ne vidi ke simptomo, aŭ vi povus vidi ĝin nur tempaltempe. Sed la realo estas ke la cimo estas, fakte, ne. Kaj estas vere problema se vi skribis programon kiu volas esti ĝentila, ke vi vendis la programo, ke homoj uzas ke ĉiu tempaltempe kraŝas ĉar, kompreneble, ĉi tio ne estas bona. Fakte, se vi havas Android telefonon aŭ iPhone kaj vi elŝuti apps tiuj tagoj, se vi iam havis programo nur quit, subite malaperas, ke estas preskaŭ ĉiam la rezulto de iu memoro-rilatajn afero, per kiu la programisto ŝraŭbita supren kaj dereferenced puntero ke li aŭ ŝi ne havas, kaj la rezulto de iOS aŭ Android estas nur mortigi la programo tute anstataŭ risko nedefinita konduto aŭ ia sekureco kompromison. Estas unu alia cimo en la programo krom ĉi tiu. Kion alian mi ŝraŭbita en tiu programo? Mi ne praktikis kion mi predikis. Yeah? [Studenta respondo, nekomprenebla] Bona. Mi ne liberigis la memoro. Do la regulo de thumb nun devas esti ajna momento vi nomas malloc, vi devas nomi liberaj kiam vi faris uzante tiu memoro. Nun, kiam estus mi volas liberigi ĉi memoro? Probable, supozante tiun unuan linion estis korekta, mi volas fari ĝin ĉi tie. Ĉar mi ne povis, ekzemple, faru ĝin ĉi tie. Kial? Ĝuste ekster atingo. Do eĉ se ni parolas pri punteros, ĉi tiu estas semajno 2 aŭ 3 demando, kie x estas nur en la medio interne de la frizita krampoj kie estis deklarita. Do vi certe ne povas liberigi ŝin tie. Mia sola ŝanco por liberigi estas proksimume post linio 21. Tio estas sufiĉe simpla programo; estis sufiĉe facila kiam oni ia envolvis via menso ĉirkaŭ kio la programo faras, kie la eraroj estis. Kaj eĉ se vi ne vidis gxin, unue, espereble ĝi estas iom evidenta nun ke tiuj eraroj bela facile solvitaj kaj facile faras. Sed kiam programo estas pli ol 12 linioj longaj, estas 50 linioj longaj, 100 linioj longaj, promenante tra via kodo linio por linio, pensante per ĝi logike, Eblas, sed ne aparte amuze fari, senĉese serĉas cimojn, kaj estas ankaŭ malfacila por fari, kaj tial ilo kiel Valgrind ekzistas. Lasu min kaj fari tion: mi malfermas mian fina fenestro, kaj lasu min ne nur kuri memoro, ĉar memoro ŝajnas esti bone. Mi ricevas bonŝanca. Irante al tiu plia bajto je la fino de la tabelo Ne ŝajnas esti tro problema. Sed mi, tamen, fari prudento ĉeko, kiu ĵus signifas por kontroli ĉu ĉi tiu estas vere ĝentilaj. Do ni faru valgrind-v - fugon-check = plena, kaj tiam la nomo de la programo en ĉi tiu kazo estas memoro, ne a.out. Do mi faru tion. Hit Eniru. Kara Dio. Ĉi tiu estas sian produktadon kaj ĉi tiu estas kion mi aludis al pli frua. Sed, se vi lernas legi tra ĉiuj sensencaĵon tie, plej de tio estas simple diagnozaj eligo tio ne tiu interesa. Kio via okulo vere volas esti serĉante estas ajna mencio de eraro aŭ malvalida. Vortoj kiuj sugestas problemojn. Kaj efektive, vidu kio okazas erara cxi tie. Mi havas resumon de iu varo, "en uzo ĉe eliro: 40 bitokoj en 1 blokoj." Mi ne vere certas kion bloko ankoraux, sed 40 bitokoj vere sentas mi povus eltrovi kie tiu venas de. 40 bajtoj. Kial 40 bitokoj en uzo ĉe eliro? Kaj pli konkrete, se ni rulumu malsupren tie, kial mi definitive perdis 40 bitokoj? Yeah? [Studenta respondo, nekomprenebla] Perfekta. Yeah, precize. Tie estis dek entjeroj, kaj ĉiu el tiuj estas grandeco de 4, aŭ 32 bitoj, tiel mi perdis precize 40 bitokoj ĉar, kiel vi proponis, mi ne nomas libera. Tio estas unu cimon, kaj nun ni rigardu malsupren iom for kaj vidi apud ĉi tio, "Nevalida skribi de grandeco 4." Nun kio estas tio? Tiu adreso estas esprimita kion bazo skribmaniero, ŝajne? Ĉi tiu estas deksesuma, kaj iam vi vidas numeron ekde 0x, ĝi signifas deksesuma, kion ni faris vojon reen en, mi kredas, pset 0 La sekcio de demandoj, kiu estis nur fari warmup ekzerco, konvertanta dekuma al deksesumajn al binaraj ks. Deksesuma, kun nur homaj konvencio, estas kutime uzata por reprezenti punteros aŭ, pli ĝenerale, adresoj. Estas nur konvencio, ĉar ĝi estas iom pli facile legi, estas iom pli kompaktaj ol iu kiel decimala, kaj binara estas netaŭga por la plimulto homoj por uzi. Do nun kion tio signifas? Nu, tio aspektas kiel ekzistas nevalidan skribu de grandeco 4 en linio 21 de memory.c. Do ni revenu al la linio 21, kaj ja, jen estas tiu nevalida skribu. Do Valgrind ne tuj tute teni mian manon, kaj diru al mi kion la riparas estas, sed detekti ke mi faras nevalidan skribu. Mi tuŝas 4 bajtoj, ke mi ne estos, kaj ŝajne tio estas ĉar, kiel vi atentigis, mi faras [10] anstataŭ [9] maksimume aŭ [0] aŭ io inter ili. Kun Valgrind, realigi ajn vi nun skribas programo kiu uzas punteros kaj uzas memoron kaj malloc pli specife, definitive eniri la kutimo de kuri ĉi tiu longa sed tre facile kopiitaj kaj pasted komando de Valgrind por vidi, ĉu ekzistas iuj eraroj en tie. Kaj estos blindiga ĉiufoje kiam vi vidos la eliron, sed ĝuste analizi tra vide ĉiujn eligo kaj vidu se vi vidas mencioj de eraroj aŭ avertoj nek nevalida aŭ perditaj. Ajna vortoj kiuj sonas same kiel vi ŝraŭbita supren ie. Do rimarkas ke estas nova ilo en via ilaron. Nun lundon, ni havis tutan faskon da uloj venos supren ĉi tien kaj reprezenti la nocio de ligitaj listo. Kaj ni enkondukis la ligitaj listo kiel solvo al kio problemo? Yeah? [Studenta respondo, nekomprenebla] Bona. Arrays ne povas havi memoron aldonis ilin. Se vi destini tabelo de amplekso 10, kiu estas ĉio vi ricevas. Vi povas nomi funkcion kiel realloc se vi komence nomis malloc, kaj kiu povas provi kreski la tabelo se estas spaco al la fino de tio ke neniu alia uzas, kaj se ne, gxi simple trovi vin pli grandan parton aliloke. Sed tiam ĝin kopios ĉiuj el tiuj bajtoj en la nova tabelo. Ĉi sonas kiel tre ĝentila solvo. Kial estas ĉi enuaj? Mi volas diri ĝi funkcias, la homoj solvis tiun problemon. Kial ni bezonas solvi ĝin lunde kun ligitaj listoj? Yeah? [Studenta respondo, nekomprenebla] Ĝi povis porti longa tempo. Fakte, ajna tempo vi vokas malloc aŭ realloc aŭ calloc, kiu estas ankoraŭ alia, ajn vi, la programo, parolas al la mastruma sistemo, vi emas prokrasti la programo sube. Kaj se vi faras tiajn aferojn en cikloj, vi vere malrapidiĝanta aĵoj sube. Vi ne tuj rimarkas tion por la plej simpla el "saluton mondo" tipo programoj, sed en multe pli granda programoj, petante la mastruma sistemo denove kaj denove por memoro aŭ doni ĝin reen kaj denove inklinas ne esti bona afero. Plus, ĝi estas nur ia intelekte - ĝi estas kompleta perdo de tempo. Kial atribui pli kaj pli memoro, risko kopii ĉion en la nova tabelo, se vi havas alternativon kiu ebligas vin atribui nur tiel memoro kiel vi vere bezonas? Do tie estas pluses kaj malpli en ĉi tie. Unu el la pluses nun estas ke ni havas dinamismo. Ne gravas kie la pecoj de memoro estas ke estas libera, Mi povas nur ordigi de krei tiujn pano panpecetoj tra punteros al string mia tuta ligitaj listo kune. Sed mi pagas almenaŭ unu prezo. Kion mi devas rezigni en gajni ligitaj listoj? Yeah? [Studenta respondo, nekomprenebla] Bona. Vi bezonas pli memoro. Nun mi bezonas spacon por tiuj indikoj, kaj en la kazo de ĉi tiu super simpla ligitaj listo ke nur provas gardi entjeroj, kio estas 4 bitokoj, ni parolas tiele bone, puntero estas 4 bajtoj, do nun mi laŭvorte duobliĝis la kvanto de memoro mi bezonas nur por stoki tiu listo. Sed denove, ĉi tiu estas konstanta tradeoff en komputiko inter tempo kaj spaco kaj disvolviĝo, penado kaj aliaj rimedoj. Kio estas alia malavantaĝo de uzante ligitaj listo? Yeah? [Studenta respondo, nekomprenebla] Bona. Ne tiel facila por aliri. Ni jam ne povas utiligi semajno 0 principoj kiel dividi kaj venki. Kaj pli specife, duuma serĉo. Ĉar eĉ se ni homoj povas vidi proksimume kie la mezo de ĉi tiu listo estas, la komputilo nur scias ke ĉi ligitaj listo komenciĝas ĉe adreso nomita unue. Kaj tio estas 0x123 aŭ io kiel tio. Kaj la sola maniero la programo povas trovi la mezo elemento estas vere sercxi la tuta listo. Kaj eĉ tiam, ĝi laŭvorte devas serĉi en la tuta listo ĉar eĉ kiam vi atingos la meza ero sekvante la punteros, vi, la programo, havas neniun ideon kiel longe tiu listo estas, potenciale, ĝis vi batis la fino de ĝi, kaj kiel vi scias programmatically ke vi estas ĉe la fino de ligitaj listo? Ekzistas speciala NULL pointer, do denove, konvencio. Anstataŭ uzi ĉi pointer, ni definitive ne deziras ke ĝi estu iu rubo valoro indikante sur scenejo ie; ni volas ke ĝi estu mano malsupren, NULL, por ke ni havas ĉi termino en ĉi datumstrukturo tiamaniere ni scias kie ĝi finiĝas. Kio se ni volas manipuli tio? Ni faris la plimulton de ĉi vide, kaj kun homoj, sed kio se ni volas fari inserción? Do la originala listo havis 9, 17, 20, 22, 29, 34. Kio se ni tiam volis malloc spaco por numero 55, nodo por tio, kaj poste ni volas enmeti 55 en la listo kiel ni faris lunde? Kiel ni faru tion? Nu, Anita venis kaj ŝi esence piediris la listo. Ŝi komencis je la unua elemento, tiam la sekva, la sekva, la sekva, la sekva, la sekvanta. Fine batis la maldekstra mano la tuta vojo malsupren kaj realigita oh, tio estas NULL. Do kio puntero manipulado bezonas fari? La persono kiu estis sur la pinto, numero 34, bezonis lian maldekstran manon levis atentigi je 55, 55 bezonis lian maldekstran brakon montrante malsupren por esti la nova NULL finilo. Faris. Bela facile enigi 55 en ordo listo. Kaj kiel povus tiu aspektas? Lasu min kaj malfermu iun kodo ekzemple ĉi tie. Mi malfermu gedit, kaj lasu min malfermi du dosierojn unua. Unu estas list1.h, kaj lasu min nur memorigi ke tio estas la bloko de kodo kiun ni uzas por reprezenti nodo. Nodo havas ambaŭ kiel int nomis n kaj puntero nomis sekva ke ĵus antaŭ la proksima afero en la listo. Tio estas nun en al. H dosiero. Kial? Estas ĉi tiu konvencio, kaj ni ne eluzis ĉi grandega kvanto ni mem, sed la persono kiu skribis printf kaj aliajn funkciojn donis kiel donaco al la mondo ĉiuj tiuj funkcioj skribante dosieron nomata stdio.h. Kaj tiam ekzistas string.h, kaj tiam tie estas map.h, kaj tie estas ĉiuj tiuj h dosieroj ke vi vidis aŭ uzis dum la termino skribita de aliaj personoj. Tipe en tiuj. H dosieroj estas nur aĵoj kiel typedefs aŭ deklaroj de kutimo tipoj aŭ deklaroj de konstantaj. Vi ne metis funkcioj 'implementaciones en header files. Vi metis, anstataŭ, ĝuste iliaj prototipoj. Vi metis tion vi volas dividi kun la mondo, kion ili bezonas por kompili sian kodon. Do nur por eniri ĉi kutimo, ni decidis fari la samon. Ne ekzistas multe en list1.h, sed ni metis iun kiu povus esti de intereso al la homo en la mondo kiuj volas uzi nian ligillisto efektivigo. Nun, en list1.c, mi ne iros tra tiu tuta afero ĉar ĝi estas iom longa, tiu programo, sed ni kuras ĝi realan rapide ĉe la prompto. Lasu min kompili list1, lasu min tiam kuras list1, kaj kion vi vidos estas Ni simulita simpla iom programo tie ke tuj permesos ke mi aldoni kaj forigi nombroj al listo. Do lasu min antaŭeniri kaj tajpu 3 por la menuo eblo 3. Mi volas enmeti la numeron - ni faru la unua numero, kiu estis 9, kaj nun mi diris al la listo estas nun 9. Lasu min kaj faru alian inserción, do mi batis menuo 3. Kio nombro mi volas enmeti? 17. Eniri. Kaj mi faros nur unu pli. Lasu min enmeti la numeron 22. Do ni havas la komencoj de la ligitaj listo por ke ni havis en slide formo antaŭ momento. Kiel tiu inserción vere okazas? Ja, 22 estas nun ĉe la fino de la listo. Do la rakonton ni diris en la scenejo lundon kaj recapped gxuste nun devas vere povus okazi en kodo. Ni rigardu. Lasu min rulumi malsupren en ĉi tiu dosiero. Ni glosan super iu el la funkcioj, sed ni iros malsupren por, ni diru, la insert funkcio. Ni vidos kiel ni iru sur la enmeto de nova nodo en tiun ligitaj listo. Kie estas la listo deklaris? Nu, ni rulumi la tuta vojo ĝis al la supro kaj rimarki ke mia ligitaj listo estas esence deklaris kiel sola puntero jen komence NULL. Do mi uzas malloka variablo tie, kiu ĝenerale ni predikis kontraŭ ĉar ĝi faras vian kodo iom senorda subteni, ĝi estas speco de mallaborema, kutime, sed ne estas pigra kaj ne erara kaj ne malbona se via programo sola celo en la vivo estas por simuli unu ligillisto. Kio estas ĝuste tio, kion ni faras. Do anstataŭ deklari tion en ĉefaj kaj tiam devas pasi ĝin al ĉiu funkcio ni skribis en tiu programo, ni anstataŭ realigi oh, ni nur faras tutmonda ĉar la tuta celo de tiu programo estas pruvi unu kaj nur unu ligitaj listo. Por ke sentu bone. Jen mia prototipoj, kaj ni ne iros tra ĉiuj el tiuj, sed mi skribis delete funkcio, oni trovos funkcio, oni insert funkcio, kaj través funkcio. Sed ni nun reiru malsupren al la insert funkcio kaj vidi kiel ĉi tiu laboras tie. Insert estas ĉe linio - tie ni iru. Enmetu. Do ĝi ne prenas neniun argumentojn, ĉar nin tuj demandas la uzanto ene de ĉi tiu funkcio por la nombro ili volas enŝovu. Sed unue, ni preparas por doni al ili iun spacon. Tio estas speco de kopio kaj alglui el la alia ekzemplo. En tiu kazo, ni estis atribui al int; ĉi tempo ni atribui nodo. Mi ne vere memoras kiom da bitokoj nodo estas, sed tio estas bone. Sizeof povas kompreni ke por mi. Kaj kial mi kontrolanta por NULL en linio 120? Kio povus erari en linio 119? Yeah? [Studenta respondo, nekomprenebla] Bona. Nur povus esti la kazo ke mi petis tro da memoro aŭ io la malbonon kaj la mastruma sistemo ne havas sufiĉe da bitokoj por doni al mi, tial ĝi markas tiel por reveni NULL, kaj se mi ne kontroli por ke kaj mi simple blinde procedi por uzi la adreson revenis, ĝi povus esti NULL. Ĝi povus esti iu nekonata valoro; ne estas bona afero se mi - efektive ne estos nekonataj valoro. Ĝi povus esti NULL, do mi ne volas trouzi kaj riski dereferencing ĝin. Se tio okazas, mi simple reveni kaj ni ŝajnigi kiel mi ne reiros ajna memoro ajn. Alie, mi diras al la uzanto doni al mi kelkajn insertar, mi vokas nia malnova amiko GetInt, kaj tiam ĉi estis la nova sintakso ni enkondukis lundon. 'Newptr-> n' signifas preni la adreso, kiun vi estis donita per malloc kiu reprezentas la unua bajto de nova nodo objekto, kaj poste iru al la kampo nomata n. Iom vidindaĵoj demando: Ĉi tiu estas ekvivalento al kio pli kripta linio de kodo? Kiel alie povus mi skribis tion? Volas preni ponardopiko? [Studenta respondo, nekomprenebla] Bona. Uzante la. N, sed ĝi ne estas tiom simpla kiel tiu ĉi. Kion mi unue bezonas fari? [Studenta respondo, nekomprenebla] Bona. Mi bezonas fari * newptr.n. Do tiu estas jene nova puntero estas evidente adreson. Kial? Ĉar ĝi revenis por malloc. La * newptr dirante "iri tien," kaj poste kiam vi estas tie, vi povas uzi la pli familiara. n, sed ĉi nur aspektas iom malbela, speciale se ni homoj tuj desegni punteros kun sagoj tutan tempon; la mondo havas normigita sur ĉi sago skribmaniero, kiu faras ĝuste la samon. Do vi nur uzu la -> notacio kiam la afero sur la maldekstra estas puntero. Alie, se ĝi estas reala struct, uzu la. N. Kaj tiam tiu: Kial mi pravalorizi newptr-> apud nula? Ni ne volas pendantaj maldekstra mano for de la fino de la scenejo. Ni volas ĝin montrante rekte malsupren, kio signifas la finon de ĉi tiu listo povus potenciale esti en ĉi tiu nodo, tial ni pli bone certigi estas NULL. Kaj, ĝenerale, inicializar vian variabloj aŭ viajn datumojn membroj kaj structs al io estas nur bona praktiko. Nur lasi rubo ekzisti kaj daŭre ekzistas ĝenerale ricevas vin en mizero se vi forgesas fari ion poste. Jen kelkaj kazoj. Ĉi tio, denove, estas la insert funkcio, kaj la unua afero, kiun mi kontroli estas se la variablo nomita unue, ke tutmonda variablo estas NULL, tio signifas ne estas ligitaj listo. Ni ne insertos ajna nombroj, do ĝi estas bagatela por enmeti ĉi aktuala nombro en la listo, ĉar ĝi simple apartenas al la komenco de la listo. Do ĉi estis kiam Anita ĵus piedo tie sola, ŝajnigante neniu alia estis ĉi tie sur la scenejo, ĝis ni destinis nodo, tiam sxi povis levi sian manon por la unua fojo, se ĉiuj aliaj venis sur la scenejo post ŝi lundon. Nun ĉi tie, ĉi tiu estas iom ĉeko kie mi devas diri se la nova nodo valoron de n estas sekva, kiu signifu iri al la struct ke tio esti notita al by newptr, do jen ni estas, iru tien. Tiam la sago diras akiri la proksimaj kampo, kaj tiam la = diras metis kio valoro tie? La valoro kiu estis en unua, kion valoro estis en la unua? Unue estis montrante tiun nodon, por ke signifas ĉi devus nun notas en tiu nodo. En aliaj vortoj, kio aspektas kvankam ridinda salaton kun mia manskribo, kio estas simpla ideo de nur kopii tiujn sagoj ĉirkaŭ tradukas kodo kun nur ĉi tiu Liner. Stoki kio estas en la unua en la sekvanta kampo kaj tiam ĝisdatigi kion unua reale estas. Ni iru antaŭen kaj rapida antaŭen tra kelkaj el ĉi tio, kaj rigardu nur en ĉi tiu vosto inserción por nun. Supozu mi alvenas al la punkto, kie mi trovos, ke la venonta kampo de iu nodo estas NULL. Kaj je tiu punkto en la historio, detalo kiun mi glosando super estas ke mi enkondukis alian puntero ĝis tie en linio 142, antaŭulo puntero. Esence, je ĉi tiu punkto en la historio, tuj la listo ricevas longa, Mi ia bezonas promeni ĝin per du fingroj ĉar se mi iras tro malproksime, memori en sola longa listo, vi ne povas iri malantaŭen. Do tiu ideo de predptr estas mia maldekstra fingro, kaj newptr - ne newptr. Alia puntero jen tie estas miaj aliaj fingroj, kaj mi estas nur speco de marŝante la listo. Tial ke ekzistas. Sed ni nur konsideras unu el la pli simplaj kazoj tie. Se tio puntero La sekva kampo estas NULL, kio estas la logika implikacio? Se vi trairas la listo kaj vi batis NULL puntero? Vi estas ĉe la fino de la listo, kaj tiel la kodo al la tiam aldonas ĉi tiu plia elemento estas varo de la intuicia prenos ke nodo kies sekva puntero estas NULL, tial ĉi estas nuntempe NULL, kaj ŝanĝi ĝin, tamen, esti la adreso de la nova vertico. Do ni simple desegni en kodo la sago, ke ni tiris la scenejo de levante ies maldekstra mano. Kaj la kazo ke mi skuos mian manon je nuntempe, nur ĉar mi kredas ke estas facile perdas kiam ni faras en ĉi tiu speco de medio, estas kontrolanta por inserción en la listo la mezo. Sed ĝuste intuicie, kion bezonas okazi, se vi volas eltrovi kie iu nombro apartenas en la mezo estas vi devas promeni ĝin kun pli ol unu fingro, pli ol unu pointer, decidi kie ĝi apartenas de kontrolanta estas la elemento La aktuala, kaj iam vi trovas tiun lokon, tiam vi devas fari ĉi speco de konko ludo kie vi movas la punteros ĉirkaŭ tre atente. Kaj tiun respondon, se vi ŝatus kialo tra tiu hejme sur via propra, abscesoj malsupren nur por tiuj du linioj de kodo, sed la ordo de tiuj linioj estas super grava. Ĉar se vi falas ies mano kaj levi iun alian estas en la malĝusta ordo, denove, vi povus fini orphaning la listo. Resumi pli koncepte, la inserción ĉe la vosto estas relative simpla. La inserción ĉe la kapo estas ankaŭ relative simpla, sed vi bezonas ĝisdatigi plia puntero ĉi tiu tempo al elpremi numero 5 en la listo ĉi tie, kaj tiam inserción meze engaĝas eĉ pli penado, al tre zorgeme enmeti la numeron 20 en ĝia ĝusta loko, kio estas inter 17 kaj 22. Do vi bezonas fari ion kiel havi la nova vertico 20 punkton al 22, kaj poste, kion nodo puntero bezonas esti ĝisdatigita lasta? Estas 17, por fakte enŝovu ĝin. Do denove, mi prokrastas la reala kodo por tiu aparta efektivigo. Je unua rigardo, estas iom blindigaj, sed estas vere nur senfina ciklo ke tio looping, looping, looping, looping, kaj rompante tiel frue kiel vi batis la NULL pointer, je kiu punkto oni povas fari la necesan inserción. Jen, do, estas reprezenta ligitaj listo inserción kodo. Tio estis ia multe, kaj sentas ni solvas unu problemon, sed ni enkondukis tuta alia. Sincere, ni pasigis tiun tutan tempon sur granda a kaj Ω kaj rula tempo, provante solvi problemojn pli rapide, kaj tie ni prenas grandan paŝon malantaŭen, ĝi sentas. Kaj tamen, se la celo estas gardi datumojn, sentas la Holy Grail, kiel ni diris lundon, estus vere esti stoki aferojn momento. Fakte, supozu ke ni faris al flanko ligitaj listo dum momento kaj ni anstataŭ enkondukis la nocion de tablo. Kaj ni nur opinias de tablo por momento tiel tablo. Tiu tabelo kaj tiu kazo tie havas iujn 26 elementoj, 0 tra 25, kaj supozu ke vi bezonas iun eron de stokado por nomoj: Alice kaj Bob kaj Charlie kaj similaj. Kaj vi bezonas iun datumstrukturo stoki tiuj nomoj. Nu, vi povus uzi ion kiel ligitaj listo kaj vi povis marŝi la listo enmeto Alico antaŭ Bob kaj Charlie post Bob ks. Kaj fakte, se vi volas vidi kodo tiel kiel flanken, scias ke en list2.h, ni faru ekzakte tion. Ni ne iros tra tiu kodo, sed ĉi tiu estas varianto de la unua ekzemplo kiu enkondukas unu alia struct ni vidis antaŭe nomita studento, kaj tiam kio fakte stokas en la ligillisto estas puntero al studento strukturo prefere ol simpla iom entjero, n. Do realigi ekzistas kodo tie kiu implikas reala kordoj, sed se la celo alproksimiĝis vere nun estas alparoli la efikeco problemo, ĉu ne estus bela se ni donita objekto nomita Alico, ni volas meti sxin en la dekstra situo en datumstrukturo, sentas ĝin estus vere agrable ĵus metis Alico, kies nomo komenciĝas per A, en la unua loko. Kaj Bob, kies nomo komenciĝas per B, en la dua loko. Kun tabelo, aŭ ni komencu nomante ĝin tablo, hash tablo en tiu, ni povas fari precize tion. Se ni estas donita nomo kiel Alice, ĉenon kiel Alice, kie vi metis A-l-i-c-e? Ni bezonas hueristic. Ni bezonas funkcion por preni iujn enigo kiel Alice kaj revenu respondon, "Metu Alico en ĉi loko." Kaj ĉi tiu funkcio, ĉi nigra skatolo, tuj estos nomata hash funkcio. Al krada funkcio estas iu kiu prenas enigo, kiel "Alico", kaj revenas al vi, tipe, la nombra situo en iu datumstrukturo kie Alico apartenas. En ĉi tiu kazo, nia hash funkcio devus esti relative simpla. Nia hash funkcio devus diri, se vi donas "Alico", kiu karaktero mi zorgas pri? La unua. Do mi rigardu [0], kaj tiam mi diros, se [0] karaktero estas A, kaj revenu al la nombro 0. Se estas B, revenu 1. Se ĝi estas C, revenu 2, kaj tiel plu. Ĉiuj 0 indekso, kaj kiu permesus min enmeti Alice kaj tiam Bob kaj tiam Charlie kaj tiel plu en ĉi tiun datumstrukturo. Sed estas problemo. Kio se Anita venas kune denove? Kie ni metas Anita? Ŝia nomo, tro, komenciĝas kun la litero A, kaj sentas ni faris ankoraŭ pli granda katastrofo de tiu problemo. Ni nun havas tujan inserción, konstanta tempo inserción, en datumstrukturo anstataŭ malbona-kazo lineara, sed kion ni faru kun Anita en ĉi tiu kazo? Kio estas la du ebloj, vere? Yeah? [Studenta respondo, nekomprenebla] Konsentite, do ni povus havi alian dimension. Tio estas bona. Do ni povas konstrui el meze en 3D kiel ni parolis pri parole lundon. Ni povus aldoni alian aliron tie, sed supozas ke ne, mi provas teni ĉi simpla. La tuta celo tie estas havi tujan konstanta tempo aliron, tiel ke tio aldonante tro multe komplekseco. Kio estas aliaj ebloj klopodinte enmeti Anita en tiun datumstrukturo? Yeah? [Studenta respondo, nekomprenebla] Bona. Do ni povus movi ĉiuj aliaj sube, kiel Charlie nudges malsupren Bob kaj Alice, kaj poste ni metos Anita kie ŝi vere volas esti. Kompreneble, nun, estas flanka efiko de tio. Ĉi datumstrukturo estas probable utila ne ĉar ni volas enmeti homoj unufoje sed ĉar ni volas kontroli se ili estas tie poste se ni deziras presi ĉiujn nomojn en la datumstrukturo. Ni tuj fari ion kun tiu datumo eventuale. Do nun ni ia ŝraŭbita super Alico, kiu ne plu kie ŝi supozis esti. Nek estas Bob, nek Charlie. Do eble ĉi tio ne estas tiom bona ideo. Sed ja, tio estas unu eblo. Ni povus ŝanĝi ĉiujn suben, aŭ heck, Anita venis malfrue al la ludo, kial ni ne nur metis Anita ne tie, ne ĉi tie, ne ĉi tie, ni nur metis sian iom pli malalta en la listo. Sed tiam tiu problemo komencas devolve denove. Vi eble povos trovi Alico tuj, bazita sur ŝia unua nomo. Kaj Bob tuj, kaj Charlie. Sed tiam vi serĉas Anita, kaj vi vidos, hmm, Alice estas en la vojo. Nu, mi kontrolu sub Alico. Bob ne estas Anita. Charlie ne Anita. Ho, tie estas Anita. Kaj se vi daŭrigas tiu trajno de logiko tuta vojo, kio estas la plej malbona-kazo rula tempo de trovo aŭ enmeto Anita en tiu nova datumstrukturo? Estas O (n), ĉu ne? Ĉar en la plej malbona kazo, estas Alico, Bob, Charlie. . . tuta vojo malsupren al iu nomita "Y", do ne estas nur unu loko restis. Feliĉe, ni ne havas unu nomita "Z", do ni metis Anita je la tre fundo. Ni ne vere solvis tiun problemon. Do eble ni bezonas enkonduki tiun trian dimension. Kaj ĝi rezultas, se ni enkonduki tiun trian dimension, ni ne povas fari ĉi perfekte, sed la Holy Grail tuj estos atingi konstanta tempo inserción kaj dinamika inserciones por ke ni ne devas forte-kodo tabelo de amplekso 26. Ni povas enmeti tiom da nomoj kiel ni volas, sed ni prenos nian 5-minuta paŭzo tie kaj poste fari tion ĝuste. Bone. Mi fiksis la rakonton ĉe bela artefarite tie elektante Alice kaj tiam Bob kaj tiam Charlie kaj tiam Anita, kies nomo estis evidente tuj kolizias kun Alice. Sed la demando ni finiĝis lundon kun estas ĝuste kiel probabla estas ke vi ricevas tiajn koliziojn? En aliaj vortoj, se ni ekuzas tiun tabular strukturo, kiu estas vere nur tabelo, en ĉi tiu kazo de 26 lokoj, kion se nia enigoj male estas unuforme distribuita? Ne artefarite Alice kaj Bob kaj Charlie kaj David kaj tiel plu alfabete, ĝi estas unuforme distribuita sur A tra Z. Eble ni simple akiri bonŝanca kaj ni ne tuj havas du A aŭ du B kun tre alta probablo, sed kiel iu atentigis, se ni ĝeneraligita tiun problemon kaj ne faru 0 al 25 sed, diru, 0 tra 364 aŭ 65, ofte la nombro de tagoj en tipa jaro, kaj demandis la demando, "Kio estas la probablo ke du el ni en tiu ĉambro havas la saman naskiĝtagon?" Alivorte, kio estas la probablo ke du el ni havas nomon ekde la A? La speco de demando estas la sama, sed ĉi tiu adreso spaco, ĉi serĉo spaco, estas pli granda en la kazo de naskiĝtago, ĉar ni havas tiom da pli tagoj en la jaro ol literoj en la alfabeto. Kio estas la probablo de kolizio? Nu, ni povas pensi pri tio per elŝeligi la math la kontraŭa vojo. Kio estas la probablo de neniu kolizioj? Nu, ĉi tie esprimo diras ke kio estas la probablo se estas nur unu persono en ĉi tiu ĉambro, ke ili havas unikan naskiĝtago? Estas 100%. Ĉar se estas nur unu persono en la ĉambron, lia aŭ ŝia naskiĝtago povas esti iu ajn el la 365 tagoj el la jaro. Do 365/365 opcioj donas al mi valoron de 1. Do la probablo en demando nuntempe estas nur 1. Sed se estas dua persono en la ĉambron, kio estas la probablo ke ilia naskiĝtago estas malsamaj? Estas nur 364 eblaj tagoj, ignorante superjaroj, por ilia naskiĝtago ne kolizias kun la aliaj homoj. Do 364/365. Se tria persono venas en, estas 363/365, kaj tiel plu. Do ni observu multiplikante kune tiujn frakcioj, kiuj estas pli kaj pli malgrandiĝas, elŝeligi kio estas la probablo ke ni ĉiuj havas unika naskiĝtago? Sed tiam ni povas, kompreneble, nur prenu ke respondo kaj klaki ĝin ĉirkaŭ kaj faru 1 minus ĉiuj de tiu, esprimo ni eventuale akiri se vi memoras la dorso de via math libroj, ĝi aspektas iom io tiamaniere, kiu estas multe pli facile interpretita grafike. Kaj ĉi grafikaĵo tie havas sur la x akso la nombro de naskiĝtago, aŭ nombro de homoj kun naskiĝtago, kaj sur la y akso estas la probablo de turniro. Kaj kion tio diras, ke se vi havas, diru, inkluzive, ni elektos iun kiel 22, 23. Se estas 22 aŭ 23 personoj en la ĉambron, la probablo ke du el tiuj tre malmultaj personoj tuj havi la sama naskiĝtago estas fakte super alta, combinatorially. 50% probabloj ke en klaso de nur 22 personoj, seminario, preskaŭ, 2 el tiuj personoj tuj havi la sama naskiĝtago. Ĉar tie estas tiom da manieroj en kiu vi povas havi la saman naskiĝtagon. Eĉ pli malbone, se vi rigardas la dekstra flanko de la tabulo, por kiam vi havas klason kun 58 studentoj en ĝi, la probablo de 2 homoj havante naskiĝtago estas super, super alta, preskaŭ 100%. Nun, jen speco de amuza fakto pri la reala vivo. Sed la implikaĵoj, nun, por datumoj strukturoj kaj provizon informoj signifas ke nur supozante ke vi havas belan, puran, uniforma distribuo de datumoj kaj vi havas sufiĉe granda tabelo por ĝustigi faskon da aĵoj ne signifas ke vi ricevos popolo en unika lokoj. Vi tuj havos kolizioj. Do tiu nocio de Regionoj, kiel ĝi estas nomata, prenante enigo kiel "Alice" kaj massaging ĝin iel kaj tiam contrarestar respondon kiel 0 aŭ 1 aŭ 2. Contrarestar iuj eligo de tiu funkcio estas tuŝita de ĉi probablo de kolizio. Do kiel ni povas manipuli tiujn koliziojn? Nu, en unu kazo, ni povas preni la ideo kiu estis sugestita. Ni povas nur ŝanĝi ĉiuj sube, aŭ eble, iom pli simple, anstataŭ movi ĉiuj aliaj, ni simple movi Anita al la fundo de la disponebla loko. Do, se Alice estas en 0, Bob estas en 1, Charlie estas en 2, ni nur metis Anita je situo 3. Kaj jen estas tekniko en datumstrukturoj nomita lineara tuŝoprobado. Lineara ĉar vi ĵus promenis ĉi tiu linio, kaj vi estas ia tuŝoprobado por disponebla makuloj en la datumstrukturo. Kompreneble, ĉi devolves en O (n). Se la datumstrukturo vere plena, estas 25 personoj en ĝi jam, kaj tiam Anita venas kune, ŝi finiĝos ĉe kio estus loko Z, kaj tio estas fajna. Ŝi ankoraŭ havas, kaj ni povas trovi ŝin poste. Sed tio estis kontraŭe al la celo de akceli aĵojn. Do kio se ni anstataŭ enkondukis tiun trian dimension? Ke tekniko estas ĝenerale nomata apartaj ĉeni, aŭ havanta ĉenoj. Kaj kia hash tablo nun estas, ĉi tabular strukturo, via tablo estas nur tabelo de punteros. Sed kion tiuj punteros indikas estas guess kio? Al ligitaj listo. Do kio se ni prenas la plej bona el ambaŭ mondoj? Ni uzas tabeloj por la komenca indeksas en la datumstrukturo do ni povas tuj iri al [0] [1], [30] aŭ ks, sed por ke ni havas kelkajn fleksebleco kaj ni povas persvadi Anita kaj Alice kaj Adam kaj iu ajn alia A nomo, ni anstataŭ lasi la alia akso kreski arbitre. Kaj ni fine, ekde lundo, havi tiun esprima kapablo kun ligillisto. Ni povas kreski datumstrukturo arbitre. Alternative, ni povus simple grandega 2-dimensia tabelo, sed tio okazas al esti terura situacio se unu el la vicoj en 2-dimensia tabelo ne estas sufiĉe granda por la plia persono kies nomon okazas komenci kun A. Dio gardu ni devas reallocate grandega 2-dimensia strukturo nur ĉar tie estas tiom da homoj nomis A, speciale kiam ekzistas tiom malmultaj personoj nomata Z ion. Ĝi estas nur tuj estos tre maldensa datumstrukturo. Do ĝi ne estas perfekta por ajna duona, sed nun ni almenaŭ havas la kapablon al tuj trovi kie Alico aŭ Anita apartenas, almenaŭ en terminoj de la vertikala akso, kaj poste ni nur devas decidi kie meti Anita aŭ Alico en ĉi ligitaj listo. Se ni ne zorgas pri ordigi aferojn, kiel rapide ni povus enmeti Alico en strukturo kiel tiu? Estas konstanta tempo. Ni indekson en [0], kaj se neniu de tie, Alico iras al la komenco de tiu ligitaj listo. Sed tio ne estas grandega traktadon. Ĉar se Anita tiam venas kune iu nombro de paŝoj poste, kiel tio Anita apartenas? Nu, [0]. OOP. Alico jam en tiu ligitaj listo. Sed se ni ne zorgas pri ordigi tiujn nomojn, ni povas nur movi Alico plus insert Anita, sed eĉ tio estas konstanta tempo. Eĉ se estas Alice kaj Adam kaj ĉiuj tiuj aliaj A nomoj, ĝi ne vere sxangxigxantaj ilin fizike. Kial? Ĉar ni ĵus faris tie kun ligitaj listo, kiu scias ili tiuj nodoj estas ĉiuokaze? Vi nur devas fari estas movi la pano panpecetoj. Movu la sagojn ĉirkaŭ; vi ne devas fizike movas neniu datumo ĉirkaŭe. Do ni povas enigi Anita, en tiu kazo, la momento. Konstanta tempo. Do ni havas konstantan tempo lookup, kaj konstanta tempo inserción de iu kiel Anita. Sed ia oversimplifying la mondo. Kio se ni poste volas trovi Alice? Kio se ni poste volas trovi Alice? Kiom da paŝoj estas ke tuj prenos? [Studenta respondo, nekomprenebla] Ekzakte. La nombro de homoj antaux Alico en ligitaj listo. Do ĝi ne tute perfekta, ĉar nia datumstrukturo, denove, havas ĉi vertikala aliro kaj tiam ĝi havas tiuj ligitaj lertaj pendanta - efektive, ni ne desegni ĝin tabelo. Ĝi tiuj ligitaj lertaj pendantaj ekstere de ĝi ke aspektas iom io tiamaniere. Sed la problemo estas se Alice kaj Adam kaj ĉiuj tiuj aliaj A nomoj finos pli kaj pli tie, trovi iu povis fini prenante faskon da paŝoj, bcause vi devas trairi la ligillisto, kiu estas lineara operacio. Do vere, tiam, la inserción tempo finfine estas O (n), kie n estas la nombro de elementoj en la listo. Dividita de, ni arbitre nomas ĝin m, kie m estas la kvanto de kunligita lertaj ke ni havas en tiu vertikala akso. En aliaj vortoj, se ni vere supozas uniforma distribuo de nomoj, tute nerealisma. Estas evidente pli de kelkaj literoj ol aliaj. Sed se ni supozu por la momento uniforma distribuo, kaj ni n tuta popolo, kaj m tuta ĉenoj disponebla por ni, tiam la longo de ĉiu el ĉi tiuj katenoj sufiĉe simple tuj estos la tuta, n dividita per la nombro de ĉenoj. Do n / m. Sed ĉi tie estas kie ni povas esti ĉiuj matematike lerta. m estas konstanta, ĉar ne estas fiksa nombro de tiuj. Vi tuj deklari vian tabelo komence, kaj ni ne regrandigi la vertikala akso. Per difino, ke restas fiksaj. Estas nur la horizontala akso, por tiel diri, ke tio ŝanĝas. Do teknike, ĉi tiu estas konstanto. Do nun, la inserción tempo estas preskaux O (n). Por ke ne sentas cxiuj multe pli bone. Sed kio estas la vero tie? Nu, ĉiuj ĉi tiuj datoj, ĉar semajnoj, ni estis dirante O (n ²). O (n), 2 x n ², - n, dividita per 2. . . ech. Estas nur n ². Sed nun, en ĉi tiu parto de la semestro, ni povas komenci paroli pri la reala mondo denove. Kaj n / m estas absolute pli rapide ol n sola. Se vi havas mil nomojn, kaj vi rompi ilin en multnombraj siteloj por ke vi havas nur dek nomoj en ĉiu el tiuj ĉenoj, absolute serĉado dek aferojn tuj estos pli rapida ol mil aĵoj. Kaj tiel unu el la venontaj problemo aroj tuj defias vin pensi ĝuste ke kvankam, yeah, asimptote kaj matematike, ĉi tiu estas ankoraŭ nur lineara, kiu suĉas ĝenerale kiam provante trovi aĵojn. Fakte, ĝi tuj estos pli rapida ol tiu pro ĉi tio dividanto. Kaj do tie estas denove tuj estos ĉi komerco-off kaj tiu konflikto inter teorio kaj realo, kaj unu el la kapetoj komencos plenumi en ĉi tiu punkto en la semestro estas pli de la realo oni kiel ni ia prepari semster la fino, kiel ni enkonduki la mondo de ttt programado, kie vere, rendimento tuj rakontos ĉar via uzantoj tuj komenci senti kaj estimi malriĉa dezajno decidoj. Do kiel vi irados tra implementando kunligita - hash tablo kun 31 eroj? Kaj la antaŭa ekzemplo estis arbitre pri naskiĝtago. Se iu havas naskiĝtagon de januaro 1 aŭ februaro 1, ni metos ilin en la sitelo. Se temas pri januaro 2, februaro 2, marto 2, ni metos ilin en la sitelo. Tial ĝi estis 31. Kiel vi deklari hash tablo? Ĝi povas esti sufiĉe simplaj, nodo * tablo estas mia arbitraj nomo por tio, [31]. Tio donas min 31 punteros al nodoj, kaj kiu min permesas havi 31 punteros al ligitaj listoj eĉ se tiuj ĉenoj estas komence NULL. Kion mi volas meti se mi volas konservi "Alice", "Bob", "Charlie"? Nu, ni bezonas kovri tiujn aferojn en strukturo ĉar ni bezonas Alico atentigi al Bob, atentigi al Charlie, ks. Ni ne povas nur havi la nomojn sola, do mi povis krei novan strukturon nomita nodo tie. Kio estas reala nodo? Kio estas nodo en ĉi tiu nova ligitaj listo? La unua afero, nomita vorto, estas por la persono nomo. Longo, supozeble, raportu al la maksimuma longo de homa nomo, kion ajn tio estas, 20, 30, 40 karakteroj en freneza angulo kazoj, kaj +1 estas por kio? Estas nur la ekstra NULL karaktero, \ 0. Do tiu nodo estas envolviendo "iu" ene de si mem, sed ankaŭ deklaras puntero nomis sekva por ke ni povu ĉeno Alico al Bob al Charlie ks. Povas esti NULL sed ne nepre devas esti. Demandojn pri tiuj hash tabloj? Yeah? [Studenta petante demando, nekomprenebla] An tabelo - bona demando. Kial estas ĉi char vorto en tabelo anstataŭ nur char *? En ĉi tiu iom arbitra ekzemplo, mi ne volas havi recurrir al malloc por ĉiu el la originalaj nomoj. Mi volis deklari maksimuman kvanton de memoro por la kordo por ke mi povus kopii en la strukturo Alico \ 0 kaj ne devas trakti malloc kaj libera kaj similaj. Sed mi povus fari tion, se mi volis esti pli konsciaj de spaco uzo. Bona demando. Do ni provu ĝeneraligi for de ĉi kaj enfokusigi la resto de hodiaŭ sur datumstrukturoj pli ĝenerale kaj aliaj problemoj kiujn ni povas solvi per la sama fundamentojn kvankam la datumstrukturoj sin povus diferenci en siaj detaloj. Do rezultas en komputiko, arboj estas tre ofta. Kaj vi povas pensi pri arbo ia kiel familio arbo, kie estas kelkaj radikoj, iuj matriarca aŭ patriarko, avino aŭ avo aŭ antaŭe reen, sub kiuj estas panjo kaj paĉjo aŭ pluraj gefratoj aŭ similaj. Do arbo strukturo havas nodoj kaj ĝi havas infanojn, kutime 0 aŭ pli infanoj por ĉiu nodo. Kaj iuj el la ĵargono, kiun vi vidas en tiu bildo ĉi tie estas ajna el la malgrandaj infanoj aŭ grandkids sur la randoj kiu ne havas sagojn emanas de ili, tiuj estas la tiel nomata folioj, kaj al neniu en la interno estas ena nodo; vi povas nomi ĝin io kune tiujn liniojn. Sed tiu strukturo estas sufiĉe komuna. Ĉi tiu estas iom arbitra. Ni havas unu infano maldekstre, ni havas tri infanojn sur la dekstra, du infanoj sur la fundo lasis. Do ni povas havi malsamajn grandeco arboj, sed se ni komencos normigi tion, kaj vi eble memoras tiun de Patricio video sur duuma serĉo de antaŭa mallonga linio, duuma serĉo ne devas esti realigita kun tabelo aŭ pecoj de papero sur tabulon. Supozu ke vi volis konservi viajn nombroj en pli kompleksaj datumstrukturo. Vi povus krei arbon kiel ĉi tio. Vi povus havi nodo deklaris en C, kaj tiu nodo povas havi almenaŭ du elementoj ene de ĝi. Unu estas la nombro vi volas konservi, kaj la alia estas - nu, ni bezonas unu pli. La alia estas liaj filoj. Do jen alia datumstrukturo. Ĉi-foje, nodo estas difinita kiel provizon nombro n kaj tiam du punteros; maldekstra infano kaj dekstra infano. Kaj ili estas ne arbitra. Kio estas interesa pri tiu arbo? Kio estas la ŝablono en kiel ni kuŝigis tiun ekster aŭ kiel Patrick metis ĝin en lia video? Estas speco de preterlasas ke ekzistas iu ordigo okazas ĉi tie, sed kio estas la simpla regulo? Yeah? [Studenta respondo, nekomprenebla] Perfekta. Se vi rigardis en tiu, vi vidos la malgrandaj nombroj maldekstre, grandaj nombroj maldekstre, sed tio estas vera por ĉiu nodo. Por ĉiu nodo, lia maldekstra infano malpli ol tio, kaj lia dekstra infano pli granda ol ĝi. Kion ĉi tio signifas nun estas se mi volas serĉi ĉi datumstrukturo por, ni diru, la numero 44, Mi devas komenci ĉe la radiko, ĉar kiel kun ĉiu el tiuj pli kompleksaj datumstrukturoj nun, ni nur havas puntero al unu afero, la komenco. Kaj en ĉi tiu kazo, la komenco estas la radiko. Ĝi ne estas la ekstrema maldekstra, ĝi estas la radiko de tiu strukturo. Do mi vidas jen 55, kaj Mi serĉas 44. Kiu direkto mi volas iri? Nu, mi volas iri al la maldekstra, ĉar evidente, dekstre tuj estos tro granda. Do rimarki tie, vi estas ia koncepte batante la arbo en duono ĉar vi neniam iras malsupren al la dekstra flanko. Do nun mi iras de la 55 al la 33. Ĝi estas tro malgranda de nombro. Mi serĉas 44, sed nun mi scias se 44 estas en ĉi tiu arbo, mi povas iri evidente al dekstre. Do denove, mi rikoltiloj la arbo en duono. Estas preskaux identaj koncepte al la telefono libro. Estas identa al kion ni faris kun la paperoj sur la tabulon, sed ĝi estas pli kompleksa strukturo kiu permesas al ni efektive fari ĉi dividi kaj venki per dezajno de la algoritmo, kaj fakte, lauxiris strukturon kiel tiu - whoops. Lauxiris strukturon kiel tiu, kie ĝi estas nur "iri tiun vojon aŭ iri tiun vojon," signifas ĉiuj kiuj kodo kiu fleksiĝis via menso unue kiam apliki ĝin en sekcio aŭ marŝante tra ĝi hejme, por duuma serĉo, uzante rekursio aŭ ripeta, ĝi estas doloro en la kolo. Trovu la mezo elemento, tiam faru viajn rondigas supren aŭ malsupren. Jen beleco al ĉi ĉar ni povas nun uzi rekursio denove, sed multe pli pure. Ja, se vi estas en la nombro 55 kaj vi volas trovi 44, vi iros restis en cxi tiu kazo, tiam kion vi faras? Vi kuras la ĝusta sama algoritmo. Vi kontrolu la valoron de la nodo, tiam vi iru maldekstren aŭ dekstren. Tiam vi kontrolu la valoron de la nodo, iru maldekstren aŭ dekstren. Ĉi tiu estas perfekte taŭgaj por rekursio. Do eĉ se en la pasinteco ni faris kelkajn sufiĉe arbitraj ekzemploj engaĝante rekursio kiu ne bezonas esti rekursie, kun datumoj stuctures, speciale arboj, ĝi estas perfekta apliko de tiu ideo de prenante problemo, ŝrumpanta ĝin, kaj tiam solvi la sama tipo de, sed pli malgranda, programo. Do tie estas alia datumstrukturo ke ni povas prezenti. Ĉi tiu estas desegnita unuavide por serĉi críptico, sed ĉi tiu estas mirinda. Do ĉi tiu estas datumstrukturo nomata trie, trie, kiu heredis de la vorto reakiro, kiu ne estas prononcata re-try-val, sed tio estas kion la mondo nomas tion. Pretendas. T-r-i-kaj. Ĝi estas arbo strukturo de iu tipo, sed ĉiu el la nodoj en trie ŝajnas esti kio? Kaj jen estas iom iluzia ĉar ĝi estas speco de mallongigita. Sed ĝi aspektas kiel ĉiu nodo en ĉi trie estas fakte tabelo. Kaj kvankam la aŭtoro de ĉi tiu figuro ne montris ĝin, en ĉi tiu kazo, ĉi trie estas datumstrukturo kies celo en la vivo estas por stoki vortoj kiel Al-l-i-c-e aŭ B-o-b. Kaj la maniero en kiu ĉi tiuj datumoj tendencas Alice kaj Bob kaj Charlie kaj Anita kaj tiel plu Estas ĝi uzas aron per kiu stoki Alico en trie, ni starti je la radika vertico kiu aspektas kiel tabelo, kaj ĝi estas skribite en stenografio skribmaniero. La aŭtoro preterlasis abcdefg ĉar ne estis nomoj kun tiu. Ili nur montris M kaj P kaj T, sed en ĉi tiu kazo, ni movi sin de Alice kaj Bob kaj Charlie por iuj nomoj, kiuj estas ĉi tie. Maxwell estas vere en ĉi tiu figuro. Do kiel faris la aŭtoro vendejo M-a-x-w-e-l-l? Li aŭ ŝi komencis je la radika vertico, kaj iris al [M], do proksimume 13, la 13-a loko en la tabelo. Tiam el tie, ne estas puntero. Al puntero kondukante al alia tabelo. De tie la aŭtoro indeksita en tiun tabelo en loko A, kiel priskribita tie ĉe supre maldekstre, kaj tiam li aŭ ŝi sekvis tiun puntero al alia tabelo, kaj iris al la puntero je situo X. Tiam en la sekvanta tabelo situo W, E, L, L, kaj tiel plu, kaj fine, ni vere provas meti bildon al ĉi tio. Kion faras nodon aspekti en kodo? Nodo en trie enhavas aron de punteros al pli nodoj. Sed estas ankaŭ alvenis al esti ia bulea valoro, almenaŭ en ĉi efektivigo. Mi hazarde nomas ĝin is_word. Kial? Ĉar kiam vi enmeto Maxwell, vi ne enmeto ion en tiun datumstrukturo. Vi ne skribas ro Vi ne skribas X. Ĉiuj vi faras estas post punteros. La puntero kiu reprezentas M, tiam la puntero kiu reprezentas A, tiam la puntero kiu reprezentas X, tiam W, E, L, L, sed kion vi bezonas fari fine estas ia iru, kontrolu, mi atingis ĉi loko. Okazis vorto kiu finiĝas ĉi tie en la datumstrukturo. Do kia trie estas vere plena kaj la aŭtoro elektis por reprezenti tiuj terminuses kun malmulta trianguloj. Tiu simple volas diri ke la fakto ĉi tiu triangulo estas ĉi tie, ĉi bulea valoro de vera signifas se vi iras malantaŭen en la arbo, kiu signifu la vorto nomata Maxwell estas en ĉi. Sed la vorto foo, ekzemple, ne estas en la arbo, ĉar se mi komencas je la radika vertico ĝis tie en supro, Ne f pointer, ne o pointer, ne o puntero. Foo ne estas nomo de ĉi tiu vortaro. Sed kontraste, Turing, t-u-r-i-n-g. Denove, mi ne stoki t aŭ u aŭ r aŭ mi aŭ n aŭ g. Sed mi faris vendejo en ĉi datumstrukturo valoron de vera vojo cxi tie en ĉi tiu nodo - en la arbo per opcio ĉi bulea valoro de is_word al vera. Tial trie estas speco de ĉi tre interesa meta strukturo, kie vi ne vere stoki la vortoj mem por tiu speco de vortaro. Por esti klaraj, vi simple stoki jes aŭ ne, estas vorto, kiu finiĝas tie. Nun kio estas la implikaĵon? Se vi havas 150.000 vortojn en vortaro ke vi provas konservi en memoro uzante iu kiel ligitaj listo, vi tuj havos 150.000 nodoj en via ligitaj listo. Kaj trovinte unu el tiuj vortoj alfabete povus preni O (n) tempo. Lineara tempo. Sed en la kazo tie de trie, kio estas la rula tempo de trovanta vorto? Rezultas la beleco ĉi tie estas, ke eĉ se vi havas 149,999 vortoj jam en ĉi tiu vortaro, kiel implementado kun ĉi datumstrukturo, kiom da tempo estas bezonata por trovi aŭ enmeti pli persono en tiun, kiel Alice, Alice? Nu, estas nur 5, eble 6 paŝoj por la fina signo. Ĉar la ĉeesto de aliaj nomoj en la strukturo ne ricevas laux la vojo de enmeto Alico. Cetere, trovante Alico iam estas 150.000 vortoj en tiu ĉi vortaro ne ricevas en via maniero de trovado Alico tute ne, ĉar Alico estas. . . . . ĉi tie, ĉar mi trovis bulea valoro. Kaj se ne estas bulea vera, tiam Alico ne estas en tiu datumstrukturo de vortoj. En aliaj vortoj, la rula tempo de trovanta aĵoj kaj enmeto aĵoj en tiu nova datumstrukturo de trie estas O de - ĝi estas ne n. Ĉar la ĉeesto de 150.000 personoj havas nenian efikon sur Alice, ŝajne. Do ni nomas ĝin k, kie k estas la maksimuma longeco de vorto en la angla kiu estas tipe ne pli ol 20-iu gravuloj. Do k estas konstanto. Do la Holy Grail ni ŝajnas esti trovita nun estas tiu de trie, konstanta tempo por enmetas, por serĉoj, por forigoj. Ĉar la nombro de aĵoj jam en la strukturo, kiu eĉ fizike tie. Denove, ili estas nur ordigi de kontrolis for, jes aŭ ne, havas nenian efikon sur lia estonteco rula tempo. Sed estas alvenis al esti catch, alie ni ne estus malŝparis tiom da tempo en ĉiuj tiuj aliaj datumstrukturoj nur por fine atingi la sekreta kiu estas miriga. Do kio prezo ni pagas por atingi tiun grandecon ĉi tie? Spaco. Tiu afero estas amasa. Kaj la kialo, ke la aŭtoro ne prezenti ĝin ĉi tie, rimarki ke ĉiuj tiuj aĵoj kiuj similas arrays, li ne eltiris la resto de la arbo, la resto de la trie, ĉar ili estas simple ne konvenas al la rakonto. Sed ĉiuj tiuj nodoj estas super larĝa, kaj ĉiu nodo en la arbo reprenas 26 aŭ reale, povus esti 27 signojn ĉar en tiu kazo mi estis inter ili spacon por la apostrofo por ke ni povus havi apostrophized vortoj. En ĉi tiu kazo, tiuj estas larĝaj tabeloj. Do eĉ se ili ne picutured, ĉi okupas amasan kvanton de RAM. Kiu povus esti bone, especilly en moderna aparataro, sed jen la tradeoff. Ni preni malpli da tempo por pasi pli da spaco. Do kie estas tiu tuta iras? Nu, ni faru - ni vidu ĉi tie. Ni faru salton al ĉi ulo tie. Kredu ĝin aŭ ne, tiel amuza kiel C estis dum iom da tempo nun, ni atingi la punkton en la semestro kie estas momento de transiro al aĵoj pli moderna. Aĵoj sur pli alta nivelo. Kaj kvankam dum la sekvaj du semajnoj ni ankoraŭ daŭre mergi nin en la mondo de punteros kaj memoro mastrumado atingi, ke konsolo, per kiu ni povas tiam konstrui, la fino ludo estas finfine enkonduki, ironie, ne ĉi lingvo. Ni pasigas, kiel 10 minutoj parolas HTML. Ĉiuj HTML estas estas markado lingvon, kaj kia markado lingvo estas Estas tiuj serioj de malferma krampoj kaj fermitaj krampoj kiuj diras 'fari ĉi bold' 'Fari ĉi kursivo' 'fari ĉi centrita. Ne ĉiuj kiuj intelekte interesa, sed ĝi estas super utila. Kaj estas certe omnipresente tiuj tagoj. Sed kio estas potenca sur la mondo de HTML, kaj retejo programado pli ĝenerale, konstruas dinamika aĵoj; skribi kodon en lingvoj kiel PHP aŭ Python aŭ Ruby aŭ Java aŭ C #. Vere, kion ajn via lingvo de elekto estas, kaj generante HTML dinamike. Generante iu nomita CSS dinamike. Akvofalo stilo littukoj, kiu estas ankaŭ pri estetiko. Kaj tial, kvankam, hodiaŭ, se mi iras al iu retejo kiel la familiara Google.com, kaj mi iras por rigardi, programisto, redakti, kiun eble vi faris antaŭe, sed tuj vidi fonton, ĉi stuff probable aspektas bela kamufla. Sed ĉi tiu estas la suba kodo kiu implementa Google.com. Sur la antauxa fino. Kaj efektive ĉio ĉi estas lanugaj estetiko stuff. Jen CSS tien. Se mi gardas movo malsupren ni ricevos iun koloron-kodita stuff. Ĉi tiu estas HTML. Google kodo aspektas kiel salato, sed se mi vere malfermi alian fenestron, ni povas vidi kelkajn strukturo al ĉi tio. Se mi malfermos ĉi supre, rimarki tie, estas iom pli legebla. Ni tuj vidos nelonge ĉi etikedo, [vorto] estas etikedo, HTML, kapo, korpo, div, skripto, tekstujo, naski, centrita, div. Kaj jen estas ankaŭ ordigi de kripta-aspekta al unua vido, sed ĉio ĉi salaton sekvas iuj ŝablonoj, kaj repetible ŝablonoj, por ke iam ni atingos la fundamentojn sube, vi povos skribi kodo kiel tiu kaj tiam manipuli kodo kiel ĉi uzante alian lingvon, nomata JavaScript. Kaj JavaScript estas lingvo kiu funkcias ene de retumilo hodiaŭ ke ni uzas en Harvard kursoj, por la kurso komerca ilo ke Google mapoj uzas doni al vi tutan faskon de dinamismo, Facebook donas al vi montri momenteto stato ĝisdatigoj, Twitter uzas ĝin por montri al vi tweets momento. Ĉio ĉi ni komencos mergi nin in Sed alveni, ni bezonas kompreni iom ion pri la interreto. Ĉi klipo tie estas nur unu minuto longe, kaj ni supozu por nun ĉi tio estas, fakte, kiel la Interreto funkcias kiel teaser por kio estas venonta. Mi donas al vi "Soldatoj de la Reto." [♫ Malrapida ĥoro muziko ♫] [Vira rakontanto] Li venis kun mesaĝo. Kun protokolo cxiuj liaj propraj. [♫ Faster elektronika muziko ♫] Li venis al mondo de cool firewalls, uncaring routers, kaj danĝeroj multe pli malbone ol morto. Li estas rapida. Li estas forta. Li estas TCP / IP, kaj li havas vian adreson. Soldatoj de la Reto. [Malan] Sekva semajno, tiam. Interreto. Retejo programado. Ĉi tiu estas CS50. [CS50.TV]