[Powered by Google Translate] [Tjedan 6, Nastavak] [David J. Malan] [Sveučilište Harvard] [Ovo je CS50.] [CS50.TV] Ovo je CS50 i to je kraj tjedna 6. Dakle CS50x, jedan od Harvard prvih tečajeva uključeni u inicijativu EDX Doista je debitirao prošlog ponedjeljka. Ako želite dobiti uvid u ono što drugima na internetu sada slijedi uz, možete krenuti na x.cs50.net. To će vas preusmjeriti na odgovarajuće mjesto na edx.org, koji je bio gdje je to i drugi predmeti iz MIT-a i Berkeley sada živi. Morat ćete se prijavili za račun; vidjet ćete da je materijal uglavnom isti kao što ste imali ovaj semestar, ali nekoliko tjedana kasniti, kao što smo dobili sve spremno. No, ono što studenti u CS50x sada će se vidjeti je sučelje prilično kao što je ovaj jedan. To je, na primjer, je Zamyla vodeći prohod za problematiku set 0. Nakon prijave na edx.org, CS50x učenik vidi i svašta što bi se očekivati ​​da vidite u tijeku: predavanje za ponedjeljak, Predavanje za srijedu, razne gaćice, problem setovi, Walkthroughs, PDF-ova. Osim toga, kao što ste vidjeli ovdje, stroj prijevodi engleskih transkripata u kineski, japanski, španjolski, talijanski, i cijela hrpa drugih jezika koje će sigurno biti nesavršen kao što smo ih razvaljati programski koristeći nešto što se zove API ili sučelje za programiranje aplikacija, iz Googlea koji nam omogućava da pretvoriti Engleski ovim drugim jezicima. No, zahvaljujući prekrasnom duhu nekih sto-plus volontera, slučajnih ljudi na internetu koji su ljubazno ponudio da se uključe u ovom projektu, postupno će se poboljšanje kvalitete tih prijevoda tako da ljudi ispraviti pogreške koje su naši računala napravili. Tako ispada da je još nekoliko studenata pojavio se u ponedjeljak nego što smo prvobitno očekivali. U stvari, sada CS50x ima 100.000 ljudi sljedeće zajedno kod kuće. Dakle, shvatili ste svi dio toga nastupni klase izrade ovaj tečaj u informatici obrazovanje općenito, šire, dostupni. A realnost je sada, s nekim od tih masivnih online tečajeva, svi oni početi s tim vrlo visokim brojevima, kao mi se čini da su to učinili ovdje. No, cilj, u konačnici, za CS50x stvarno dobiti što mnoge ljude do cilja što je više moguće. Po dizajnu, CS50x će biti ponuđen na ovom prošlom ponedjeljak sve put kroz 15. travnja 2013, tako da ljudi koji imaju školske obveze drugdje, posao, obitelj, ostali sukobi i slično, imaju malo više fleksibilnosti s kojima zaroniti u ovaj tečaj, koji, dovoljno je reći, je prilično ambiciozno radi samo ako tijekom samo tri mjeseca tijekom uobičajenog semestra. Ali ti studenti će biti rješavanju istog problema seta, gledanje isti sadržaj, imaju pristup istim gaćice i slično. Dakle, shvatili da smo svi doista u to zajedno. A jedan od krajnjih ciljeva CS50x je ne samo da se što više ljudi do cilja i dati im ovaj novootkriveni razumijevanje računalnih znanosti i programiranje, ali i da ih se ovaj zajednički doživljaj. Jedan od definiranja karakteristika 50 na kampusu, nadamo se, je ova vrsta komunalne iskustva, za bolje ili za lošije, ponekad, ali da ti ljudi da se okrenu na lijevoj i na desnoj strani, i radno vrijeme i hackathon i pošteno. To je malo teže to učiniti u osobi s ljudi online, ali CS50x će zaključiti u travnju prvi ikad CS50 Expo, koji će biti online adaptacija našoj ideji fer gdje ti tisuće studenata sve će biti pozvani da dostave 1 - do 2-minutnog videa, bilo Screencast svog konačnog projekta ili video od njih maše pozdraviti i govori o svojim projektima i to demoing, baš kao i vaši prethodnici su učinili ovdje na kampusu na sajmu, tako da po semestru kraja, nada se da imaju globalnu izložbu od CS50x učeničkih finalnih projekata, slično kao što čeka vas ovaj prosinac ovdje na kampusu. Dakle, više o tome u mjesecima koji dolaze. Sa 100.000 studenata, ipak, dolazi potreba za još nekoliko CA. S obzirom da su ti dečki plamen trag ovdje i uzimanje CS50 Nekoliko tjedana prije ovog materijala je puštanje na narod na EDX, shvatiti voljeli bismo uključiti što veći broj naših studenata što je više moguće u ovoj inicijativi, kako tijekom semestra, kao i ove zime, a ovaj dolazak proljeća. Dakle, ako želite da se uključe u CS50x, Posebno se pridružio u na CS50x raspravljati, EDX verzija CS50 raspravljati, koji su mnogi od vas su pomoću na kampusu, online oglasne ploče, molimo učinite glavu na tom URL-u, javite nam tko ste, jer bismo voljeli da podigne ekipu studenata i osoblja i fakultet podjednako na kampusu koji jednostavno igraju zajedno i pomaže. A kad su vidjeli pitanje koji je upoznat s njima, čujete student izvještavanja neki bug negdje vani u nekoj zemlji na Internetu, i da zvoni zvono, jer vi imali taj isti problem u d-dvorani prije nekog vremena, nadam se onda može zvoniti i podijeliti svoje iskustvo. Dakle, nemojte sudjelovati ako želite. Računalna znanost tečajevi na Harvardu imaju malo tradicije, CS50 među njima, vlasništvo neke odjeće, nešto odjeće, koje možete nositi s ponosom u semestru kraja, rekavši prilično ponosno da ste završili CS50 i uzeo CS50 i slično, a mi uvijek pokušati uključiti studente u tom procesu koliko god je to moguće, pri čemu mi pozivamo, oko tog vremena semestra, studenti podnijeti dizajna koristeći Photoshop, ili što god alat izbora želite koristiti ako ste dizajner, podnijeti dizajna za majice i veste i suncobrani i malo bandanas za pse sada imamo i slično. I sve je onda - pobjednici svake godine onda su izloženi na stazi web stranici store.cs50.net. Sve se prodaje po cijeni tamo, ali samo se radi web stranica i omogućava ljudima da odaberete boje i dizajna koji im se sviđaju. Pomislio sam da bih samo podijeliti neke od prošlogodišnjih dizajna da su na internetskoj stranici osim ove jedne ovdje, što je godišnja tradicija. "Svaki dan sam SEG Faultn" je bio jedan od podnesaka prošle godine, koji je još uvijek na raspolaganju ima za alumni. Imali smo taj jedan, "CS50, osnovana 1989." Jedan od naših Razmaci, Rob je bio vrlo popularan prošle godine. "Tim Bowden" rođen, ovaj dizajn je podnesen, među najboljih prodavača. Kao što je bio ovaj ovdje. Mnogi su ljudi imali "Bowden Fever" prema prodaji trupaca. Shvatite da je sada mogao biti vaš dizajn tamo, na internetu. Više pojedinosti o tome u sljedećem problemu postavlja doći. Još jedan alat: vi ste imali neke izloženost i nadamo sada neki kazaljka-na iskustvo sa GDB, koji je, naravno, debugger i omogućuje vam da manipuliraju vaš program na prilično niskoj razini, radi ono što vrste stvari? Što GDB neka vam je činiti? Da? Daj mi nešto. [Studentski odgovor, nerazumljivo] Dobro. Korak u funkciji, tako da ne samo da upišite pokrenuti i imaju program udarac kroz cijelosti, ispis stvari na standardni izlaz. Umjesto toga, možete korak kroz to liniju po liniju, ili upisivanjem sljedeće ići redak po redak po redak ili korak da se upuste u funkciji, obično onaj koji ti napisao. Što drugo ne GDB neka vam je činiti? Da? [Studentski odgovor, nerazumljivo] Ispis varijable. Dakle, ako želite napraviti malo introspekcije unutar svog programa bez posezanja za pisanje printf izjave sve više mjesta, možete jednostavno ispisati varijablu ili prikazati varijablu. Što još možete učiniti s debugger poput GDB? [Studentski odgovor, nerazumljivo] Točno. Možete postaviti prijelomnih točaka, možete reći prijelom izvršenje na glavna funkcija ili foo funkciju. Možete reći prijelom izvršenje na liniji 123. I prijelomnih točaka su jako moćna tehnika jer ako imate opći osjećaj gdje je vaš problem Vjerojatno je, da ne moraju gubiti vrijeme koračni kroz program cijelosti. Vi zapravo možete skočiti tamo i onda počnite tipkati - koračni kroz nju s korak ili neposredno ili slično. No, kvaka s nešto poput GDB je da vam pomaže, ljudsko, pronaći svoje probleme i naći svoje greške. To ne mora nužno ih naći toliko za vas. Tako smo uveli drugi dan style50, koji je kratko alat naredbenog retka koji pokušava stilizovati kôd malo više čisto od vas, čovjek, možda učinio. Ali to je, također, je zapravo samo estetski stvar. No, ispostavilo se da je ovo drugi alat zove Valgrind da je malo više kompliciranih koristiti. Njegova proizvodnja je atrociously grobni na prvi pogled. Ali to je predivno korisna, pogotovo sada kada smo u dijelu mandata gdje ste počinju koristiti malloc i dinamička dodjela memorije. Stvari mogu ići jako, jako krivo brzo. Jer, ako ste zaboravili osloboditi svoju memoriju, ili ste dereference neke NULL pokazivač, ili ste dereference neke smeće pokazivač, što je obično simptom koji rezultati? SEG kvar. A ti ovaj core datoteku nekog broja kilobajta ili megabajtima koji predstavlja stanje svoga programa memorije kada se srušio, ali vaš program konačnici SEG mane, segmentacije grešku, što znači da se nešto loše dogodilo gotovo uvijek povezana do memorije vezane greške koje ste napravili negdje. Dakle Valgrind pomaže vam stvari kao što je ovaj. To je alat koji naiđete, poput GDB, nakon što ste sastavili svoj program, ali umjesto da pokrenete svoj program izravno, naiđete Valgrind i da prođe na njega svoj program, baš kao što učiniti s GDB. Sada, korištenje, kako bi dobili najbolju vrstu proizvodnje, je malo dugo, pa tamo na vrhu na ekranu ćete vidjeti Valgrind-V. "-V" gotovo univerzalno znači verbose kada koristite programe na Linux računalu. Dakle, to znači ispljunuti više podataka nego što bi po defaultu. "- Curenja provjerite = puni." To samo govori provjeru svih mogućih memorijskih curenja, greške koje sam možda napravio. To je, također, je čest paradigma s Linux programa. Općenito, ako imate argument naredbenog retka da je "prekidač", koji je trebao promijeniti program ponašanje, a to je slovo, to je-v, ali ako to je uključen, samo po dizajnu programera, je punu riječ ili niz riječi, argument naredbenog retka počinje s -. Ovo su samo ljudska konvencija, ali vidjet ćete ih sve. I onda, konačno, "a.out" je proizvoljan naziv za program u ovom konkretnom primjeru. I ovdje je neki predstavnik izlaz. Prije nego što pogledamo što bi to moglo značiti, da me pusti preko na isječku koda ovamo. I neka mi premjestiti ovu zabit, uskoro, i neka je pogledati memory.c, koji je ovaj kratki primjer ovdje. Dakle, u ovom programu, neka mi povećali na funkcijama i pitanja. Imamo funkciju glavnog koji poziva funkciju, F, i što onda ne ž nastaviti raditi, u nešto tehničkoj engleskom? Što ž nastaviti raditi? Kako o Ja ću početi s linije 20, a zvijezde lokacija ne smeta, ali samo ću biti u skladu s ovdje zadnjem predavanju. Što je linija 20 ne za nas? Na lijevoj strani. Mi ćemo ga razbiti dalje. Interesi * x: Što to učiniti? Ok. To je proglašenje pokazivač, a sada budimo još tehnički. Što to znači, vrlo konkretno, da proglasi pokazivač? Netko drugi? Da? [Studentski odgovor, nerazumljivo] predaleko. Pa što čitate na desnoj strani znaka jednakosti. Neka se usredotočiti samo na lijevoj, samo na int * x. To znači "proglasi" pokazivač, ali sada neka je roniti u dublje toj definiciji. Što to konkretno, tehnički znači? Da? [Studentski odgovor, nerazumljivo] Ok. To je priprema za spremanje adresu u memoriji. Dobro. I neka se ovaj jedan korak dalje, to je deklariranje varijabli, X, koji je 32 bita. I znam da je 32 bita, jer -? To nije zato što je int, jer je pokazivač u ovom slučaju. Slučajnost da je jedan te isti s int, ali je činjenica da postoji zvijezda tamo znači ovo je pokazivač i uređaja, kao i sa mnogim računalima, ali ne i sve, pokazivači su 32 bita. Na više modernom hardveru poput najnovijih Mac, najnovije PC, možda ćete imati 64-bitne naputke, ali u aparatu, te stvari su 32 bita. Tako ćemo standardizirati na to. Konkretnije, priča ide kako slijedi: Mi "proglasiti" pokazivač, što to znači? Mi pripremiti za pohranu memorijsku adresu. Što to znači? Mi stvaramo varijablu x koja traje do 32 bita da će uskoro pohraniti adresu cijeli broj. I to je vjerojatno oko kao precizan kao što možete dobiti. To je u redu kreće naprijed pojednostaviti svijet i samo reći proglasiti pokazivač zove x. Objavite pokazivač, ali shvatite i razumjeti što se zapravo događa na čak iu samo tih nekoliko likova. Sada, ovo je gotovo malo lakše, iako je to više izraz. Pa što je ovo događaj, koji je istaknuo sada: "malloc (10 * sizeof (int));" Da? [Studentski odgovor, nerazumljivo] Dobro. I ja ću ga odvesti tamo. To je dodjelom komad memorije za deset brojeva. A sada idemo roniti u nešto dublje, to je dodjelom komad memorije za deset brojeva. Što je malloc zatim se vraćaju? Adresa tog komad, ili, konkretnije, adresa prvom bajtu tom komad. Kako onda sam ja, programer, da znam gdje da komad memorije krajevima? Znam da je to granično. Malloc, po definiciji, će vam dati granični komad memorije. Nema praznine u njemu. Imate pristup svakom bajtu u tom komad, natrag na natrag na leđa, ali kako da znam gdje je kraj ovoj komad memorije je? Kada koristite malloc? [Studentski odgovor, nerazumljivo] Dobro. Vi ne. Morate zapamtiti. Moram se sjetiti da sam koristio vrijednost 10, a ja čak i ne čini se da su to učinili ovdje. No, teret je u potpunosti na mene. Strlen, koji smo postali malo oslanja na za gudače, radi samo zbog ove konvencije da \ 0 ili je ovo posebna NUL znak, NSK, na kraju niza. To ne vrijedi za samo proizvoljnim komade memorije. To je do vas. Dakle liniji 20, dakle, izdvaja komad memorije koji se može pohraniti deset cijelih brojeva, i to pohranjuje adresu prvog byte te komad memorije u varijablu x.. Ergo, što je pokazivač. Dakle liniji 21, na žalost, bio pogreška. Ali prvo, što se to radi? To govori dućan na lokaciji 10, 0 indeksirane, o komad memorije zove x vrijednost 0. Dakle primijetiti par stvari se događa. Iako je x pokazivač, podsjećaju iz prije par tjedana da još uvijek možete koristiti niz stilu zapis nosača kvadrata. Jer to je zapravo kratki ruka notacija za više zagonetan izgleda pokazivač aritmetike. gdje bismo učiniti nešto ovako: Uzmite adresu x, premjestiti 10 mjesta više, onda ići tamo bez obzira adresa je pohranjena na toj lokaciji. Ali iskreno, to je samo zločest pročitati i dobiti udoban sa. Dakle, svijet se obično koristi uglate zagrade samo zato što je tako mnogo više ljudskih-friendly čitati. Ali to je ono što se stvarno događa ispod haube; x je adresa, a ne niz, po sebi. Dakle, ovo je spremanje 0 na mjestu 10 u x.. Zašto je to loše? Da? [Studentski odgovor, nerazumljivo] Točno. Mi samo izdvojila deset Ints, ali možemo računati od 0 kada programiranje u C, tako da imate pristup 0 1 2 3 4 5 6 7 8 9, ali ne i 10. Dakle, ili program će SEG kriv ili nije. Ali mi stvarno ne znam, a to je vrsta nedeterminističkim ponašanja. To stvarno ovisi o tome hoće li nam se posreći. Ako se ispostavi da je operativni sustav ne smeta ako sam koristiti taj dodatni byte, iako ga nije dao za mene, moj program ne može srušiti. To je sirovi, to je lud, ali nije mogao vidjeti da je simptom, ili možda ćete ga vidjeti samo jednom u neko vrijeme. No, stvarnost je da je bug je, u stvari, ima. I to je stvarno problematično ako ste napisali program koji želite biti točni, da ste prodali program koji ljudi koriste da svaki jednom u neko vrijeme ruši jer, naravno, to nije dobro. U stvari, ako imate Android telefon ili iPhone i preuzimanje aplikacije ovih dana, ako ste ikada imali app samo prestati, sve odjednom nestane, to je gotovo uvijek rezultat neke memorije povezane pitanju, pri čemu programer zeznuo i dereferenced pokazivač da on ili ona ne bi trebala imati, a rezultat iOS ili Android je ubijati program uopce umjesto rizika nedefinirano ponašanje ili neku vrstu sigurnosti kompromisa. Tu je još jedan bug u tom programu, osim ovog jednog. Što drugo sam zeznuo u ovom programu? Nisam trenirao ono što sam propovijedao. Da? [Studentski odgovor, nerazumljivo] Dobro. Nisam oslobodio memoriju. Dakle, pravilo sada mora biti u bilo koje vrijeme nazvati malloc, morate nazvati besplatno kada se obavlja pomoću tog memorije. Sada, kad bih htjela osloboditi tu memoriju? Vjerojatno, pod pretpostavkom da je ovo prva linija bila točna, ja bi htio to učiniti ovdje. Budući da nisam mogao, na primjer, to ovdje dolje. Zašto? Samo iz djelokruga. Dakle, iako govorimo o pokazivače, ovo je tjedan 2 ili 3 pitanje, gdje je x samo u okviru unutar vitičastih zagrada gdje je proglašen. Tako da definitivno ne može ga osloboditi tamo. Moja jedina šansa da ga oslobodi je otprilike nakon linije 21. To je prilično jednostavan program, to je prilično lako nakon što vrsta omotan svoj um oko čega se program radi, gdje su greške bile. A čak i ako to nismo vidjeli na početku, nadamo se da je malo očito sada da ove greške su prilično lako riješiti i jednostavno napravio. No, kada je program i više od 12 linija dugo, to je 50 redaka dugo, 100 linija dugo, hodanje kroz koda liniju po liniju, razmišljanja kroz njega logično, je moguće, ali nije osobito zabavno raditi, stalno u potrazi za bubama, i to je također teško učiniti, i to je razlog zašto alat poput Valgrind postoji. Pusti me naprijed i to: neka mi otvoriti moj prozor terminala, i neka mi ne samo pokrenuti pamćenje, jer memorije čini se da je u redu. Ja sam uzimajući sretan. Odlazak na tom pomoćnom bajtu na kraju niza ne čini se previše problematično. Ali neka mi, ipak, učiniti razum ček, što samo znači da biste provjerili hoće li ili ne to je zapravo točno. Tako ćemo učiniti valgrind-V - curenja provjerite = puni, , a zatim naziv programa u ovom slučaju je memorija, a ne a.out. Pa neka mi ići naprijed i učiniti. Hit Enter. Dragi Bože. To je njegov izlaz, a to je ono što sam aludirala na ranije. Ali, ako ste saznali da pročitate kroz sve gluposti ovdje, većina to je samo dijagnostički izlaz da nije tako zanimljivo. Što vaše oči stvarno želi biti u potrazi za bilo kakav spomen pogreške ili neispravne. Riječi koje sugeriraju probleme. I doista, neka je vidjeti što se događa u krivu ovdje dolje. Imam sažetak o nekakvoj ", u uporabi na izlazu:. 40 bajtova u jednom blokova" Nisam siguran što je blok, no 40 bajtova zapravo osjeća kao što sam mogao shvatiti gdje da dolazi iz. 40 bajtova. Zašto su 40 bajtova u uporabi na izlazu? I točnije, ako mi dođite ovamo, Zato sam definitivno izgubio 40 bajtova? Da? [Studentski odgovor, nerazumljivo] Savršeno. Da, točno. Bilo je deset cijelih brojeva, a svaki od njih je veličina 4, ili 32 bita, tako da sam izgubio upravo 40 bajtova jer, kao što ste predložili, nisam pozvan besplatno. To je jedan bug, a sada pogledajmo što se razbije malo dalje i vidjeti pored toga, "Nevažeći pisati o veličini četiri." Sada što je to? Ova adresa je izrazio što osnovni zapis, očito? Ovo je heksadecimalni, i svaki put kad vidi broj počevši s 0x, to znači heksadecimalni, što smo radili davne, mislim, pset 0 u dijelu pitanja, koji je bio samo napraviti vježbe zagrijavanja, pretvaranje decimalnog hex u binarni i tako dalje. Heksadecimalni, samo ljudske konvenciji, obično se koristi za predstavljanje pokazivače ili, općenito, obraća. To je samo konvencija, jer to je malo lakše čitati, to je malo više kompaktan nego nešto poput decimale, i binarni je beskoristan za većinu ljudi koristiti. Pa sad, što to znači? Pa, to izgleda kao da je nevažeća zapisivanja veličine 4 na liniji 21 memory.c. Dakle, vratimo se na liniji 21, i doista, ovdje je to valjan pisati. Dakle Valgrind ne ide u potpunosti držite ruku i reći mi ono što je popraviti, ali to je otkrivanje da radim nevažeći pisati. Ja sam dira 4 bajta da ne bih trebao biti, i očito da je to zato, kao što je istaknuo, radim [10] umjesto [9] maksimalno ili [0] ili nešto između. S Valgrind, ostvariti bilo koje vrijeme sada pišete program koji koristi pokazivače i koristi memoriju, i malloc točnije, definitivno ući u naviku trčanje ovako dugo ali vrlo jednostavno kopirati i zalijepiti naredbu Valgrind vidjeti ako ima neke pogreške u tamo. I to će biti neodoljiv svaki put kad vidim izlaz, ali samo analizirati kroz vizualno sve snage i vidjeti ako vidite spominje pogrešaka ili upozorenja ili nevažeći ili izgubljeni. Bilo riječi koje zvuče kao tobom pijan negdje. Dakle, shvatite da je novi alat u kompletu. Sada je u ponedjeljak, imali smo hrpu ljudi dolaze ovamo i predstavljaju pojam povezane liste. A uveli smo povezani popis kao rješenje ono problem? Da? [Studentski odgovor, nerazumljivo] Dobro. Polja ne može imati memorije dodan na njih. Ako izdvojiti niz veličine 10, to je sve što ste dobili. Možete nazvati funkciju kao realloc ako u početku zove malloc, i da mogu pokušati rasti niz ako postoji prostor prema kraju njega da nitko drugi ne koristi, a ako ne postoji, to je samo naći će vam veći komad negdje drugdje. Ali onda će kopirati sve one bajtova u novom polju. To zvuči kao vrlo ispravnom rješenju. Zašto je to neprivlačan? Mislim da radi, ljudi su taj problem riješili. Zašto moramo ga riješiti u ponedjeljak s povezanim listama? Da? [Odgovor Student, nerazumljivo] To bi moglo potrajati dugo vremena. U stvari, svaki put kada zovete malloc ili realloc ili calloc, što je još jedan, bilo koje vrijeme, program se govori u operacijskom sustavu, imaju tendenciju da se usporiti program prema dolje. A ako radite ovakve stvari u petlji, ste stvarno usporava stvari dolje. Nećeš primjetiti ovo najjednostavniji "Hello World" tipa programa, ali u puno većim programima, tražeći operativni sustav i opet za pamćenje ili ga vraćam i opet teži ne biti dobra stvar. Plus, to je samo vrsta intelektualno - to je potpuni gubitak vremena. Zašto izdvajati više i više memorije, rizik kopiranje sve u novom ruhu ako imate alternativu koja vam omogućuje da dodijeliti samo koliko memorije kao što je zapravo potrebno? Dakle, tu je pluses i minusa u ovdje. Jedan od pluses sada je da imamo dinamizam. Nije bitno gdje su komadi memorije su da su slobodni, Ja samo mogu sortirati u stvaranje tih mrvice kruha preko pokazivače string cijeli moj povezanog popisa zajedno. Ali ja platiti barem jednu cijenu. Što moram odreći dobivanjem vezane liste? Da? [Studentski odgovor, nerazumljivo] Dobro. Trebate više memorije. Sada trebam prostor za ove naputke, te u slučaju ovog super jednostavnog povezanoj popisu da samo pokušava pohraniti prirodna broja, koji su četiri bajta, držimo rekavši dobro, pokazivač je 4 bajta, tako da sada Doslovce sam udvostručila količina memorije trebam samo za pohranu ovaj popis. Ali opet, to je konstanta tradeoff u informatici između vremena i prostora i razvoja, truda i drugih resursa. Što je još jedan downside korištenja povezan popis? Da? [Studentski odgovor, nerazumljivo] Dobro. Nije tako lako pristupiti. Mi više ne mogu utjecati tjedan 0 načela poput podijeli pa vladaj. I točnije, binarno pretraživanje. Jer iako mi ljudi možete vidjeti gdje otprilike sredinom ovog popisa je, računalo samo zna da je to povezano popis počinje na adresi zove prvi. I to je 0x123 ili nešto slično. A jedini način program može pronaći srednji elementa je zapravo traži cijeli popis. A čak i tada, to je doslovno za pretraživanje cijeli popis, jer čak i nakon što dođete na srednju elementa slijedeći naputke, ti, program, nemam pojma koliko dugo ovaj popis je, potencijalno, dok ne pogoditi kraj njega, a kako znate programski da si na kraju povezane popisu? Tu je posebna NULL pokazivač, pa opet, konvencija. Umjesto da koristite ovaj pokazivač, definitivno ne želim da to bude neko smeće vrijednost pokazujući s pozornice negdje, želimo da se ruka dolje, NULL, tako da imamo ovu terminalla u ovom strukture podataka, tako da znamo gdje to završava. Što ako želimo manipulirati to? Napravili smo većinu ovom vizualno, i sa ljudima, ali što ako želimo napraviti umetanje? Dakle, izvorni popis bio 9, 17, 20, 22, 29, 34. Što ako smo tada htjeli malloc prostora za broj 55, čvor za njega, i onda želimo umetnuti 55 u popisu kao što smo učinili u ponedjeljak? Kako ćemo to učiniti? Pa, Anita je došao i ona je u suštini hodao popis. Počela je na prvi element, onda je sljedeći, sljedeći, sljedeći, sljedeći, sljedeći. Konačno pogodio lijevi skroz i shvatio oh, ovo je NULL. Dakle, ono što pokazivač manipulacije potrebni da se radi? Osoba koja je na kraju, broj 34, potrebna mu je lijeva ruka podignuta ukazati na 55, 55 potrebno svoju lijevu ruku prema dolje da bude novi NULL Terminator. Gotovo. Prilično lako umetanje 55 u sortirani popis. I kako bi to moglo izgledati? Pusti me naprijed i otvoriti neke koda primjer ovdje. Ja ću otvoriti gedit, i neka mi otvoriti dvije datoteke prvi. Jedan je list1.h, i neka mi samo podsjetiti da je to komad koda da smo se predstavljaju čvor. Čvor ima i int n zove i upustvo zove sljedeći koji samo ukazuje na sljedeću stvar na popisu. To je sada u. H datoteci. Zašto? Tu je ta konvencija, a nismo iskoristili ovo ogroman sami, ali osoba koja je napisao printf i druge funkcije dao kao dar na svijetu svih tih funkcija pišući datoteku pod nazivom stdio.h. A onda je tu string.h, a zatim tu je map.h, a tu je sve ove h slika koje ste možda vidjeli ili koristili tijekom trajanja pisanog od strane drugih ljudi. Obično u tim. H datoteke su samo stvari poput typedefs ili deklaracije prilagođene vrste ili prijavljivanjem konstanti. Vi ne stavi funkcije 'implementacije u zaglavlju datoteke. Možete staviti, umjesto toga, samo svoje prototipove. Možete staviti stvari koje želite podijeliti sa svijetom ono što im je potrebno kako bi se sastaviti svoj kod. Dakle, samo da se u ovu naviku, odlučili smo napraviti istu stvar. Ne postoji puno u list1.h, ali mi smo stavili nešto što bi moglo biti od interesa za ljude u svijetu koji žele koristiti naše povezanu popis provedbu. Sada, u list1.c, neću ići kroz ovaj cijelu stvar jer to je malo dugo, ovaj program, ali ajmo pokrenuti to pravi brzo na provjeru. Dopustite mi sastaviti List1, neka mi onda pokrenuti List1, a ono što ćete vidjeti je mi smo simulirani jednostavan mali program ovdje da će mi dopustiti da dodavanje i uklanjanje brojeva na popisu. Pa neka mi ići naprijed i upišite 3 za tri izbornika opcija. Želim umetnuti broj - ajmo napraviti prvi broj, koji je bio 9, i sada sam rekla popis je sada devet. Dopustite mi ići naprijed i učiniti još jedan umetanje, pa sam udario izbornika tri. Koji broj želim umetnuti? 17. Upišite. I ja ću to učiniti samo još jedan. Dopustite mi da stavite broj 22. Dakle, imamo početke povezanog popisa koji smo imali u slide obliku trenutak prije. Kako je to umetanje zapravo događa? Doista, 22 je sada na kraju popisa. Dakle, priča mi je rekao na pozornici u ponedjeljak i recapped upravo sada mora biti zapravo događa u kodu. Idemo pogledati. Dopustite mi da se pomaknite prema dolje u ovoj datoteci. Mi ćemo prijeći preko neke od funkcija, ali ćemo ići prema dolje, recimo, funkcija umetak. Idemo vidjeti kako ćemo ići o umetanja novog čvora u ovom povezane liste. Gdje je popis proglašen? Pa, neka je pomicanje skroz gore na vrhu, i primijetiti da moj povezani popis bitno je proglašen kao jedan pokazivač koji je u početku NULL. Dakle, ja sam koristeći globalnu varijablu ovdje, što općenito smo propovijedali protiv jer se čini koda malo neuredan za održavanje, to je vrsta lijen, obično, ali to nije lijen i to nije u redu i to nije loše Ako je vaš program je jedina svrha u životu je da simulira jedan povezanu listu. Koji je točno ono što mi radimo. Dakle, umjesto da proglasi to glavna, a zatim su ga prođe na svakom funkciji smo zapisano u ovom programu, umjesto toga shvatiti, oh, neka je samo da je to globalna jer cijela svrha ovog programa je pokazati jedan i samo jedan vezan popis. Dakle, da se osjeća dobro. Ovdje su moji prototipovi, a mi nećemo proći kroz sve to, ali sam napisao brisanje funkciju, a pronaći funkciju, umetnuti funkciju, i poprijeko funkciju. Ali ajmo sad vratiti dolje priložene funkciji i vidjeti kako je to netko radi ovdje. Insert je na liniji - ovdje mi ići. Umetnite. Dakle, to ne poduzimati nikakve argumente, jer ćemo pitati korisnik unutar ove funkcije za broj ih želite umetnuti. Ali prvo, mi pripremamo da im daju neki prostor. To je vrsta kopirati i zalijepiti iz druge primjer. U tom slučaju, mi smo bili dodjele int; ovaj put smo dodjele čvor. Ja stvarno ne sjećam koliko bajtova čvor je, ali to je u redu. Sizeof mogu shvatiti da se za mene. A zašto sam ja provjere NULL u skladu 120? Što bi moglo poći po zlu u skladu 119? Da? [Studentski odgovor, nerazumljivo] Dobro. Samo bi mogao biti slučaj da sam pitao za previše memorije ili nešto nije u redu, a operativni sustav nema dovoljno bajtova da me daju, tako da signalizira koliko po povratku NULL, a ako ja ne provjerite da a ja samo slijepo nastaviti koristiti adresa se vratio, to bi mogao biti NULL. To bi mogao biti neki nepoznati vrijednost; nije dobra stvar ako ja - zapravo neće biti nepoznata vrijednost. To bi mogla biti NULL, tako da ja ne želim da ga zlostavljati i riskirati ga dereferencing. Ako se to dogodi, samo sam se vratiti, a mi ćemo se pretvarati kao da nisam dobila natrag bilo sjećanje na sve. Inače, kažem korisnik će mi dati broj za umetanje, pozivam naše stare prijatelju GetInt, i onda je to nova sintaksa uveli smo u ponedjeljak. 'Newptr-> n' znači uzeti adresu koju je dao malloc što predstavlja prvi byte novog čvora objekta, , a zatim otići na području zvanom n. Malo trivijalnost pitanje: To je ekvivalent za ono što više grobni liniju koda? Kako bi inače ja sam napisao ovo? Želite li se ubosti? [Studentski odgovor, nerazumljivo] Dobro. Koristeći. N, ali to nije sasvim jednostavno kao ovo. Što mi je prvo trebate učiniti? [Studentski odgovor, nerazumljivo] Dobro. Trebam napraviti * newptr.n. Dakle, ovo je rekao novi pokazivač je očito adresa. Zašto? Budući da je vraćen od strane malloc. * Newptr rekavši "tamo" i onda kad ste tamo, onda možete koristiti više poznato. N, ali to samo izgleda malo ružno, pogotovo ako mi ljudi idu na privući pokazivače sa strelicama svih vremena, svijet ima standardizirani na ovom strelice zapis, koji ne točno istu stvar. Dakle, samo koristiti -> notaciju kada je stvar na lijevoj strani je pokazivač. Inače, ako je to stvarna struct, koristiti. N. I onda ovo: Zašto sam inicijalizirati newptr-> uz NULL? Mi ne želimo visećim lijevu ruku off kraja pozornice. Želimo to pokazuje ravno dolje, što znači kraj ovom popisu mogao potencijalno biti na tom čvoru, pa smo bolje bi bili sigurni da je NULL. I, općenito, inicijalizacije svoje varijable ili podatkovne članove i tvorevina nešto je samo dobra praksa. Samo ostavljajući smeće postoje i dalje postojati općenito dobiva u nevolji ako ste zaboravili učiniti nešto kasnije. Evo nekoliko slučajeva. To je, opet, je umetak funkcija, i prva stvar koju sam provjeriti je li varijabla zove prvi, da je globalna varijabla je NULL, to znači da ne postoji povezani popis. Nismo umetnuta nikakve brojeve, tako da je trivijalno umetnuti ovaj trenutni broj u popis, jer to jednostavno spada na početku popisa. Dakle, ovo je bio kad Anita samo stajao ovdje sam, praveći nitko drugi nije bio ovdje na bini dok smo dodijeljen čvor, onda je ona mogla podići ruku po prvi put, ako su svi ostali došli na pozornicu nakon nje u ponedjeljak. Sada ovdje, ovo je malo provjeriti gdje moram reći da ako je nova čvora vrijednost n je next, to znači ići na struct koja se ukazao na po newptr, pa ovdje smo, otići tamo. Tada se strelica rekavši dobiti sljedeći polje, a zatim = govori staviti ono vrijednost tamo? Vrijednost koja je u prvi, što je vrijednost bila u prvom? Prvo je pokazujući na ovom čvoru, pa to znači da je sada treba ukazati na ovom čvoru. Drugim riječima, ono što izgleda iako smiješnom zabrljati sa mojim rukopisom, što je jednostavna ideja samo pomicanjem ove strelice oko prevodi na kodu samo s tom jednom brod. Čuvajte ono što je u prvi u sljedećem polju, a zatim ažurirati ono prvi zapravo jest. Idemo naprijed i brzo naprijed kroz neke od toga, i gledati samo na ovom repa za sada. Pretpostavimo da sam doći do točke gdje sam naći da je sljedeće polje nekog čvora je NULL. I u ovom trenutku u priči, detaljno da sam prešućuju je da sam upoznao još pokazivač ovdje u skladu 142, prethodnik ciljnikom. U suštini, u ovom trenutku u priči, jednom je popis gets dugo, Nekako mi je potrebno da ga hodati s dva prsta jer ako odem predaleko, sjećam u jednom duljine popisu, ne možete ići unatrag. Dakle, ova ideja predptr je moj lijevo prst, a newptr - ne newptr. Drugi pokazivač koji je ovdje je moj drugi prst, a ja sam samo vrsta hodanja popis. Zato što postoji. Ali ajmo uzeti u obzir samo jedan od jednostavnijih slučajeva ovdje. Ako te pokazivača sljedeće polje je NULL, što je logična implikacija? Ako ste prešli taj popis i pogodio NULL pokazivač? Vi ste na kraju popisa, i tako kod onda dodati ovaj jedan dodatni element je vrsta intuitivno će se taj čvor čija sljedeći pokazivač je NULL, tako da je ovo trenutno NULL, i to promijeniti, ipak, biti adresa novi čvor. Dakle, mi smo samo crtanje u kodu strelicu da mi je nacrtao na pozornici podizanje nečiju lijevu ruku. I slučaj da ću mahati moje ruke na za sada, Upravo zato mislim da je lako izgubiti kada ćemo to učiniti u ovom vrstom okoliš, je provjera za ubacivanje na popisu je sredini. No, samo intuitivno, ono što se treba dogoditi, ako želite shvatiti gdje neki broj pripada u sredini je što moram ga hodati s više od jednog prsta, više od jedne pokazivač, shvatiti gdje joj je i mjesto po provjeri je element Struja jednom, i jednom naći to mjesto, onda morate učiniti ovu vrstu ljuska igra u kojoj se krećete na naputke oko vrlo pažljivo. I da odgovor, ako želite razloga kroz to kod kuće na svoje, svodi samo na ove dvije linije koda, ali bi od tih linija je super važno. Jer ako ispadne nečiju ruku i podići netko drugi u pogrešnom redoslijedu, opet, mogli završiti orphaning popis. Da sumiramo više konceptualno, umetanja na začelju je relativno jednostavan. Umetanja na glavi je također relativno jednostavan, ali morate ažurirati Dodatne pokazivač ovaj put ugurati broj 5 u popis ovdje, a zatim umetanje u sredini uključuje još više truda, do vrlo pažljivo umetnite broj 20 u svom pravom mjestu, koja je između 17 i 22 godine. Dakle, što trebate učiniti nešto poput imaju novi čvor 20 točku 22, a zatim, koji čvora pokazivač treba biti obnovljeno zadnji? To je 17, zapravo ga umetnite. Pa opet, ja ću odgoditi stvarni kod za tu određenu primjenu. Na prvi pogled, to je malo neodoljiv, ali to je zapravo samo beskonačna petlja koji je petlje, petlje, petlje, petlje, i razbijanje čim pogodio NULL pokazivač, U tom trenutku možete učiniti potrebnu umetanje. To je, dakle, prikazuje povezani popis umetanje koda. To je vrsta puno, i da se osjeća kao da smo riješili jedan problem, ali uveli smo cijeli drugi. Iskreno, mi smo proveli cijelo ovo vrijeme na velikom O i Ω i trčanje vremena, pokušava riješiti probleme brže, i ovdje smo uzimanje veliki korak unatrag, to se osjeća. A opet, ako je cilj za pohranu podataka, ona se osjeća kao Svetim Gralom, kao što smo rekli u ponedjeljak, stvarno bi bilo za pohranu stvari odmah. U stvari, pretpostavljam da smo stavili na stranu povezan popis za trenutak a mi umjesto da uvodi pojam tablici. I neka je samo misliti na stolu za trenutak kao niz. Ovo polje i to ovdje slučaj ima neke elemente 26, 0 do 25, i pretpostavimo da vam je potreban neki komad za pohranu za imena: Alice i Bob i Charlie i slično. I vi trebate neke strukturu podataka za pohranu ta imena. Pa, što bi moglo koristiti nešto poput povezane liste i ti mogao hodati popis umetanjem Alisa prije Bobom i Charlie nakon Bob i tako dalje. A, u stvari, ako želite vidjeti kod kao što je to, kao na stranu, znam da je u list2.h, radimo upravo to. Nećemo ići preko ovog koda, ali to je varijanta prvom primjeru koji uvodi jedan drugi struct smo vidjeli prije tzv učenika, i onda što to zapravo sprema u povezanoj listi je pointer na studentskoj strukturi nego jednostavno malo broj, n. Dakle, shvaćam da je kod tu koja uključuje stvarne konce, ali ako je cilj na dohvat ruke stvarno sada je za rješavanje problema učinkovitost, Ne bi li bilo lijepo da smo s obzirom na objekt zove Alice, želimo joj staviti u pravo mjesto u bogatu strukturu, ona se osjeća kao da bi bilo jako lijepo da samo stavite Alisa, čije ime počinje s, u prvom položaju. I Bob, čije ime počinje sa B, u drugom mjestu. Uz niz, ili počnimo nazivajući ga stol, hash tablice u to, možemo učiniti upravo to. Ako smo dati ime poput Alice, Niz poput Alice, gdje ste stavili A-L-I-c-e? Trebamo hueristic. Trebamo funkciju uzeti neki ulaz poput Alice i vratiti odgovor, "Put Alisa u ovom mjestu." I ova funkcija, ova crna kutija, koja će se zvati hash funkcija. Hash funkcija je nešto što traje ulaz, kao što je "Alice", i vraća se u vama, obično, numerička mjesto u nekom strukture podataka gdje je Alice pripada. U ovom slučaju, naša hash funkcija trebala biti relativno jednostavan. Naš hash funkcija treba reći, ako ste dati "Alice", koji lik trebam stalo? Prvi. Dakle, gledam [0], a onda sam rekao, ako [0] Lik je, vratiti broj 0. Ako je B, vratiti jedan. Ako je to C, vratiti dva, i tako dalje. Sve 0 indeks, te da će dopustiti mene za umetanje Alice, a zatim Bob i onda Charlie i tako dalje u ovom strukturom podataka. No, tu je problem. Što ako Anita dolazi zajedno opet? Kamo ćemo staviti Anita? Njezino ime je, također, počinje slovom A, i da se osjeća kao da smo napravili još veći nered ovom problemu. Mi sada imamo izravan umetanje, konstantna vrijeme unosa, u strukture podataka nego gore-slučaju linearno, ali ono što možemo učiniti s Anita u ovom slučaju? Koje su dvije opcije, stvarno? Da? [Studentski odgovor, nerazumljivo] Ok, tako da smo mogli imati još jednu dimenziju. To je dobro. Dakle, možemo izgraditi stvari u 3D kao što smo razgovarali o verbalno ponedjeljak. Mogli bismo dodati još jedan pristup ovdje, ali pretpostavljam da ne, ja pokušavam zadržati ovaj jednostavan. Cijeli cilj je da se ovdje imaju neposredne konstanta-time pristup, tako da se dodavanjem previše složenosti. Koje su druge mogućnosti kada pokušava ubaciti Anita u ovom strukture podataka? Da? [Studentski odgovor, nerazumljivo] Dobro. Tako smo mogli kretati svi drugi dolje, kao Charlie nudges dolje Bob i Alice, a onda smo stavili Anita gdje ona stvarno želi biti. Naravno, sada, tu je nuspojava toga. Ova struktura podataka je vjerojatno korisno ne zato što želimo umetnuti ljudi odjednom ali zato želimo provjeriti da li su oni tamo kasnije ako želimo ispisati sva imena u strukture podataka. Mi ćemo učiniti nešto s tim podacima na kraju. Tako sada imamo takav pijan nad Alice, koji više nije gdje je ona trebala biti. Niti je Bob, niti je Charlie. Dakle, možda to i nije tako dobra ideja. Ali doista, to je jedna od opcija. Mi smo mogli prebaciti sve dolje, ili pakao, Anita je došao kasno u igri, zašto ne bismo stavili Anita Ne ovdje, ne ovdje, ne ovdje, neka je samo stavi malo niže na popisu. No, tada taj problem počne dopasti opet. Možda ćete biti u mogućnosti pronaći Alice odmah, na temelju njezina imena. I Bob odmah, a Charlie. Ali onda tražiti Anita, i vidjet ćete, hm, Alice je na putu. Pa, dopustite mi da provjerite u nastavku Alice. Bob je nije Anita. Charlie nije Anita. Oh, tamo je Anita. A ako ste i dalje taj vlak logike skroz, što je najgore slučaj trčanje vrijeme pronalaženje ili umetanjem Anita u ovom novom strukturom podataka? To je O (n), zar ne? Budući da je u najgorem slučaju, tu je Alice, Bob, Charlie. . . skroz nekome pod nazivom "Y", tako da je samo jedno mjesto ulijevo. Srećom, mi nemamo jedan pod nazivom "Z", pa smo stavili Anita na samom dnu. Nismo stvarno riješiti taj problem. Dakle, možda trebamo uvesti ovu treću dimenziju. I to ispada, ako ne možemo predstaviti ovu treću dimenziju, ne možemo to učiniti savršeno, ali Sveti Gral će biti uzimajući konstantnog vrijeme umetanja i dinamičke ubacivanja, tako da mi nemamo na hard-code niz veličine 26. Možemo umetnuti kao mnogim imenima kao što smo željeli, ali neka se naš 5-minutni predah ovdje i onda to ispravno. U redu. Postavio sam priču se prilično umjetno postoji odabirom Alice, a zatim Bob i onda Charlie, a zatim Anita, čije ime je očito ide sudariti s Alice. No, pitanje koje je završio u ponedjeljak je koliko je to vjerojatno da bi dobili ove vrste sudara? Drugim riječima, ako ćemo početi koristiti ovaj tablični strukturu, što je zapravo samo niz, u ovom slučaju 26 lokacija, što ako su naši ulazi umjesto toga su ravnomjerno raspoređena? To nije umjetno Alice i Bob i Charlie i David i tako dalje abecednim redom, to ravnomjerno je raspoređen kroz Z. Možda ćemo samo dobiti sretan i nećemo imati dvije-a ili dva B-a s vrlo visokom vjerojatnošću, ali kao što je netko istaknuo, ako ćemo generalizirati taj problem, a ne raditi 0-25 ali, kažu, od 0 do 364 ili 65, često broj dana u tipičnom godine, i postavio pitanje: "Što je vjerojatnost da su dva od nas u ovoj sobi imaju isti rođendan?" Stavite to na drugi način, što je vjerojatnost da nas dvoje imaju ime počinje s? Vrsta pitanje je ista, ali ovaj adresni prostor, to traži prostor, je veći u slučaju rođendane, zato što imamo toliko mnogo više dana u godini nego slova u abecedi. Što je vjerojatnost sudara? Pa, možemo razmišljati o tome koje figuring out matematike na suprotan način. Što je vjerojatnost bez sudara? Pa, ovaj izraz ovdje kaže da je ono što je vjerojatnost ako postoji samo jedna osoba u ovoj sobi, da oni imaju jedinstvenu rođendan? To je 100%. Jer, ako postoji samo jedna osoba u sobi, njegov ili njezin rođendan može biti bilo koji od 365 dana u godini. Dakle, 365/365 opcija mi daje vrijednost 1. Dakle vjerojatnost u pitanju u ovom trenutku je samo jedan. Ali ako postoji druga osoba u sobi, što je vjerojatnost da je njihov rođendan je drugačiji? Tu je samo 364 mogućih dana, ignoriranje prijestupnih godina, za rođendan ne sudaraju s drugim osobama. Dakle, 364/365. Ako treća osoba dolazi u, to je 363/365, i tako dalje. Tako smo zadržati množenjem zajedno ove frakcije, koje su sve manji i manji, shvatiti kolika je vjerojatnost da su svi od nas imaju jedinstvene rođendane? No, tada možemo, naravno, samo se taj odgovor i okretanje oko i to jedan minus sve to, izraz kraju smo ćete dobiti ako se sjećate leđa svojim matematičkim knjigama, to izgleda malo ovako nešto, koji je mnogo lakše protumačiti grafički. I ovaj grafički ovdje ima na x osi broj rođendane, ili broj ljudi s rođendane, i na y osi je vjerojatnost utakmici. A što je to rekao je da ako imate, recimo, čak, ajmo izabrati nešto poput 22, 23. Ako je 22 ili 23 ljudi u sobi, vjerojatnost da su dva od tih rijetkih ljudi će imati isti rođendan je zapravo super visoka, combinatorially. 50% šanse da je u klasi od samo 22 ljudi, seminarskih, praktički, 2 od tih ljudi će imati isti rođendan. Budući da je toliko mnogo načina na koje možete imati isti rođendan. Još gore, ako pogledate na desnoj strani ljestvice, u trenutku imate klasu sa 58 učenika u njega, vjerojatnost dvije osobe imaju rođendan je super, super visoke, gotovo 100%. Sada, to je neka vrsta zabave činjenice o stvarnom životu. Ali implikacije, sada, za strukture podataka i pohranu podataka znači da samo pod pretpostavkom da imate lijepu, čistu, ujednačenu distribuciju podataka i imate dovoljno veliki niz stane hrpa stvari ne znači da ćeš dobiti ljude u jedinstvenim lokacijama. Ti ćeš imati sudara. Dakle, ovaj pojam hashing, kao što se zove, uzimanje ulaz kao "Alice" i masirati na neki način , a zatim vratiti odgovor kao što je 0 ili 1 ili 2. Vratimo neki izlaz iz te funkcije je udario po ovom vjerojatnost sudara. Pa kako možemo nositi one sudara? Pa, na jednom slučaju, možemo uzeti ideju da je predložen. Mi samo možemo prebaciti sve dolje, ili možda, malo više jednostavno, nego potez i svi drugi, neka je samo premjestiti Anita na dnu dostupnih mjesta. Dakle, ako Alice je u 0, svaki je u 1, Charlie je u 2, samo ćemo staviti Anita na lokaciji tri. A to je tehnika u strukturama podataka zove linearni sondiranja. Linearni jer ste samo hodanje ovu liniju, a vi ste vrsta sondiranja dostupnih mjesta u strukture podataka. Naravno, to prerasta u O (n). Ako struktura podataka je jako puno, tu je 25 ljudi u njemu, već a zatim Anita dolazi zajedno, ona završi u što će biti mjesto Z, i to je u redu. Ona je još uvijek odgovara, a možemo ju pronaći kasnije. Ali to je bilo u suprotnosti s ciljem ubrzanja njegovih stvari. Pa što ako smo umjesto uveo ovu treću dimenziju? To tehnika općenito se zove odvojen ulančavanje, ili imaju lance. A što hash tablicu je sada, ovaj tablični struktura, Vaš stol je samo niz pokazivača. No, ono što ti pokazivače ukazati je pogodite što? Povezani popis. Pa što ako uzmemo najbolje od oba svijeta? Mi koristimo polja za prvih indeksa u strukturu podataka, tako da odmah mogu ići na [0] [1], [30] ili slično, ali tako da imamo neke fleksibilnost i možemo stati Anita i Alice i Adam i bilo koje drugo ime, smo umjesto neka druga os rastu proizvoljno. I napokon smo, od ponedjeljka, ima tu izražajnu sposobnost s povezanom popisu. Možemo rasti strukturu podataka samovoljno. Alternativno, samo smo mogli napraviti veliki 2-dimenzionalni niz, ali to će biti strašno ako se situacija jedan od redaka u 2-dimenzionalni niz nije dovoljno velik za dodatnu osobu čije ime se događa početi s A. Ne daj Bože moramo preusmjeriti veliki 2-dimenzionalnu strukturu samo zato što je toliko ljudi zove, pogotovo kad je tako malo ljudi zove Z nešto. Upravo će to biti vrlo rijetka struktura podataka. Dakle, to nije savršeno na bilo koji način, ali sada smo barem imaju sposobnost da odmah pronaći gdje je Alice ili Anita pripada, barem u smislu vertikalne osi, i onda mi samo morati odlučiti gdje staviti Anita ili Alice u ovom povezan popisu. Ako mi ne stalo sortiranje stvari, kako brzo bismo mogli umetnuti Alisa u strukturi kao što je ovaj? To je konstanta vrijeme. Mi indeks u [0], a ako nitko ne dođe, Alice ide na početku tog povezanog popisa. No, to nije velika stvar. Jer ako Anita onda dolazi zajedno neki broj koraka kasnije, gdje se Anita pripadaju? Pa, [0]. OOP. Alice je već u tom povezane liste. Ali ako mi nije stalo sortiranje tih imena, mi samo možemo premjestiti Alice više, umetak Anita, ali čak i da je konstantna vrijeme. Čak i ako postoji Alice i Adam i svi ovi ostali A imena, to nije stvarno ih prebacuje fizički. Zašto? Budući da smo upravo učinio ovdje s povezanog popisa, tko zna bili ti čvorovi su ionako? Sve što morate učiniti je premjestiti mrvice kruha. Pomicanje strelice oko, vi ne morate fizički premjestiti sve podatke okolo. Dakle, možemo ubaciti Anita, u tom slučaju, odmah. Konstantna vrijeme. Dakle, imamo stalni vremenu lookup, i stalno vremenu umetanje netko poput Anita. Ali vrsta pretjeranog pojednostavljivanja svijet. Što ako kasnije želite pronaći Alice? Što ako kasnije želite pronaći Alice? Koliko koraka je da će to trajati? [Studentski odgovor, nerazumljivo] Točno. Broj osoba prije Alisa u zemlji povezanog popisa. Dakle, to nije sasvim savršen, jer je naša struktura podataka, opet, ima tu vertikalnu pristup i onda ima ove povezane liste visi - zapravo, nemojmo izvući ga polje. To je ta povezani popisi visi od nje da izgleda malo nešto ovako. No, problem je ako su Alice i Adam i svi ovi ostali A imena završiti sve više i više postoji, pronalaženje netko mogao završiti uzimanje hrpa koraka, bcause morate proći povezanu listu, koja je linearna operacija. Pa stvarno, a zatim, umetanja vrijeme konačnici je O (n), gdje je n broj elemenata u popisu. Podijeljen, ajmo proizvoljno ga zovu m, gdje je m broj linkova popisima da smo u tom vertikalnoj osi. Drugim riječima, ako smo doista pretpostaviti jedinstvenu raspodjelu imena, potpuno nerealno. Tu je očito više od nekih pisama od drugih. Ali ako pretpostavimo za trenutak uniformu distribucije, i mi smo n ukupno ljude i M ukupne lance dostupni nama, onda je duljina svake od ovih lanaca prilično jednostavno će biti ukupno, n podijeljena po broju lanaca. Dakle, n / m. No, ovdje je mjesto gdje možemo biti svi matematički pametan. m je konstantna, jer postoji određeni broj njih. Ideš proglasiti svoj niz na početku, i nismo resize vertikalnoj osi. Po definiciji, koja ostaje fiksna. To je samo horizontalna os, da tako kažemo, da se mijenja. Dakle, tehnički, to je konstanta. Tako sada, umetanja vrijeme je prilično O (n). Tako da se ne osjeća sve što je puno bolje. No, ono što je istina ovdje? Pa, sve ovo vrijeme, za nekoliko tjedana, mi smo bili rekavši O (n ²). O (n), 2 x n ², - n, podijeljen 2. . . ech. To je samo n ². Ali sada, u ovom dijelu semestra, možemo početi govoriti o stvarnom svijetu ponovno. I n / m je apsolutno brže nego samo n sami. Ako imate tisuću imena, a vi ih razbiti u više ćelija tako da imate samo deset imena u svakom od tih lanaca, Apsolutno potrazi deset stvari će biti brži od tisuću stvari. I tako jedan od nadolazećih problema setovima će vam izazov razmišljati o točno da je, iako, da, asimptotski i matematički, to je još uvijek samo linearno, koje sranje općenito kada pokušavate pronaći stvari. U stvarnosti, to će biti brži od toga zbog toga djelitelj. I tako se ponovno će biti ovaj trade-off i ovaj sukob između teorije i stvarnosti, i jedan od ručice će početi okretati u ovom trenutku u semestru je više od stvarnosti kao što smo jedna vrsta pripreme za semster kraja, kao što smo uvesti u svijet web programiranje, gdje je stvarno, nastup će se računati jer su vaši korisnici će početi osjećati i cijeniti loše dizajnerske odluke. Pa kako idete o provedbi linked - hash tablicu s 31 elemenata? I prethodna primjer je samovoljno o rođendanima. Ako netko ima rođendan 1. siječnja ili 1. veljače, mi ćemo ih u ovom kantu. Ako je 2. siječnja, 2. veljače, 2. ožujka, mi ćemo ih u ovom kantu. To je razlog zašto je 31. Kako proglasiti hash tablicu? To može biti prilično jednostavna, čvor * tablica je moja proizvoljna ime za njega, [31]. To mi daje 31 upućuje na čvorove, i da mi omogućuje da imaju 31 upućuje na povezane liste čak i ako ti lanci su u početku NULL. Što želim staviti ako želim spremiti "Alice", "Bob", "Charlie"? Pa, moramo završiti te stvari u strukturi jer moramo Alice ukazati na Boba, ukazati na Charlie, i tako dalje. Ne možemo samo imati imena sama, tako da sam mogao stvoriti novu strukturu zove čvor ovdje. Što je stvarni čvor? Što je čvor u ovom novom povezan popisu? Prva stvar, zove riječ, je za ime osobe. DULJINA, vjerojatno, odnosi na maksimalnu duljinu ljudskog ime, što god da je, 20, 30, 40 znakova u ludim kutak slučajevima, i jedan je za što? To je samo dodatni NULL karakter, \ 0. Dakle, ovo je čvor wrapping "nešto" iznutra sebi, ali također izjavljuje pokazivač zove sljedeći tako da možemo lanac Alisa se Bob Charlieju i tako dalje. Može biti NULL, ali ne mora nužno biti. Sva pitanja o tim hash tablice? Da? [Studentski molba pitanje, nerazumljivo] array - dobro pitanje. Zašto je to char riječ u polje, nego samo char *? U ovom pomalo proizvoljnom primjer, ja ne želim morati posegnuti da malloc za svaki od originalnih imena. Htjela sam da proglasi maksimalnu količinu memorije za string tako da sam mogao kopirati u strukturi Alice \ 0, a ne moraju nositi s malloc i free i slično. Ali ja mogao učiniti da ako sam htjela biti više svjesni korištenja prostora. Dobro pitanje. Tako ćemo pokušati generalizirati daleko od toga i usredotočiti se ostatak danas na podatkovnim strukturama općenito i drugi problemi koje možemo riješiti pomoću iste osnove iako su strukture podataka i sami mogu razlikovati u svojim pojedinostima. Tako ispada u informatici, stabla su vrlo česte. A možete misliti stabla vrste poput obiteljskog stabla, tamo gdje je neki korijeni, neki matriarch ili patrijarha, baka ili djed ili ranije vratiti, ispod kojeg su mama i tata ili razne braća ili slično. Dakle, struktura stabla ima čvorove i ima djecu, obično 0 ili više djece za svaki čvor. A neki od žargona koje vidite na ovoj slici ovdje je bilo od male djece ili grandkids na rubovima koji nemaju strelice proizlaze iz njih, one su tzv lišće, i svatko na unutrašnjost je unutarnji čvor, možete ga nazvati ništa duž tih linija. No, ova struktura je prilično čest. Ovo je malo proizvoljna. Imamo jedno dijete na lijevoj strani, imamo troje djece na desno, dvoje djece na dnu lijevo. Dakle, možemo imati različite veličine stabla, ali ako počnemo standardizirati stvari, a možda podsjetiti ovo od Patrika video na binarnom traženju iz prethodnog kratkog online, binarno pretraživanje ne moraju se provoditi s nizom ili komada papira na ploči. Pretpostavimo da ste željeli pohraniti svoje brojeve u više sofisticirane strukture podataka. Ti bi mogao stvoriti stablo ovako. Ti bi mogao imati čvor deklariranih u C, i da čvor može imati najmanje dva elementa unutar njega. Jedan je broj koji želite pohraniti, a drugi je - dobro, moramo još jednom. Druga je njegova djeca. Dakle, ovdje je još jedan struktura podataka. Ovaj put, čvor je definirana kao čuvanje broj n i onda dva upućuje; lijevo i desno dijete dijete. A oni nisu proizvoljni. Što je zanimljivo o ovom stablu? Što je uzorak u tome što smo položili ovo van ili kako Patrick ga iznio u svom videu? To je vrsta očito da postoji neki sortiranje se ovdje događa, ali ono što je jednostavno pravilo? Da? [Studentski odgovor, nerazumljivo] Savršeno. Ako pogled na to, vidjet ćete male brojeve na lijevoj strani, veliki brojevi na lijevoj strani, ali to je istina za svaki čvor. Za svaki čvor, njegova lijeva dijete manje od njega, a njegovo pravo dijete veće od njega. Što to znači sada je, ako želim tražiti ovu strukturu podataka za, recimo, broj 44, Moram početi u korijenu, jer kao i sa svim tim složenijih struktura podataka sada, imamo samo pokazivač na jednu stvar, početak. I u ovom slučaju, početak je korijen. To nije lijevi kraj, to je korijen ove strukture. Dakle, vidim ovdje je 55, a ja sam u potrazi za 44. U kojem smjeru želim ići? Pa, ja želim ići na lijevoj strani, jer očito, na desnoj strani će biti prevelika. Dakle primijetiti, ti si vrsta konceptualno cijepanje stablo na pola jer nikad ne ide dolje na desnoj strani. Dakle, sada idem iz 55 do 33. To je premala broja. Ja sam u potrazi za 44, ali sada znam da je 44 u tom stablu, mogu otići očito desno. Pa opet, ja sam orezivanje stabala na pola. To je prilično puno identičan koncepcijski u telefonski imenik. To je identičan onome što smo učinili s radovima na ploči, ali to je više sofisticiran struktura koja omogućuje nam da se zapravo ne to podijeli pa vladaj po dizajnu algoritma, i zapravo, poprijeko strukturu ovako - ups. Prolaskom strukturu ovako, gdje je samo "ići ovaj put ili ići na taj način," znači sav taj kod koji Bent svoj um na prvi kada ga provodi u odjeljku ili šetnju kroz njega kod kuće, za binarnog pretraživanja, koristite rekurzija ili iteraciji to je bol u vratu. Nađi srednji element, zatim raditi svoj zaokruživanje gore ili dolje. Tu je ljepota na to, jer sada možemo koristiti rekurziju opet, ali mnogo više čisto. Doista, ako si na broju 55, a vi želite pronaći 44, idete lijevo, u ovom slučaju, onda što ćete učiniti? Možete pokrenuti isti algoritam. Možete provjeriti vrijednost čvora, onda idete lijevo ili desno. Onda ste provjeriti vrijednost čvora, ići lijevo ili desno. To je savršeno pogodna za rekurzije. Dakle, iako je u prošlosti smo napravili neke prilično proizvoljnih primjera uključuju rekurziju da nije potrebno da se rekurzivna, s podacima struktura tamo, osobito drveće, to je savršena primjena ove ideje uzimanja problem, ga smanjuje, a zatim rješavanje isti tip, ali manji, program. Dakle, postoji još jedna struktura podataka da možemo uvesti. To je osmišljen na prvi pogled izgleda zagonetan, ali ovo je nevjerojatno. Dakle, ovo je struktura podataka zove trie, trie, koji je naslijedio od riječi dohvat, koji se ne izgovara ponovno probati-Val, ali to je ono što svijet naziva te stvari. Pokušava. T-r-i-e. To je stablo struktura neke vrste, ali svaki od čvorova u trie Čini se da je ono što? A to je malo zabludu, jer to je vrsta skraćeno. No, izgleda da svaki čvor u ovom trie je zapravo niz. I iako autor ovog dijagrama ga nije pokazala, u ovom slučaju, to trie je struktura podataka čija je svrha u životu je pohraniti riječi Poput-l-I-c-e ili B-O-B. A način na koji je taj podatak pohranjuje Alice i Bob i Charlie i Anita i tako dalje se koristi niz kojim se pohraniti Alisa u trie, možemo početi na korijen čvor koji izgleda kao niz, i to je bio napisan u stenogram notaciji. Autor izostavljen abcdefg jer nije bilo imena s tim. Oni su samo pokazali M i P i T, ali u ovom slučaju, krenimo od Alice i Bob i Charlie nekim imenima koja su ovdje. Maxwell je zapravo u ovom dijagramu. Pa kako je autora dućan M--x-w-e-l-ja? On ili ona je počela na korijen čvor, te je otišao na [M], tako otprilike 13, 13. mjesto u polju. Onda od tamo, tu je pokazivač. Pokazivač dovodi do drugog niza. Od tamo autor indeksirane u tom polju na lokaciji A, kao što je prikazano tamo na gornjem lijevom kutu, i onda on ili ona je slijedila taj pokazivač na drugo polje, i otišao na pokazivač na mjesto X. Zatim u sljedećem polja lokacije W, E, L, L, i tako dalje, i na kraju, neka je zapravo pokušati staviti sliku na ovo. Što čvor izgleda u kodu? Čvor u trie sadrži niz upućuje na daljnje čvorova. No, tu je također dobio biti neka vrsta Boolean vrijednosti, barem u ovom provedbu. Ja se dogoditi da ga zovu is_word. Zašto? Jer kad ste umetanja Maxwell, niste umetanja ništa u ovom strukturom podataka. Vi ne pišeš M. Vi ne pišeš X. Sve što radite je nakon pokazivače. Pokazivač koji predstavlja m, zatim pokazivač koji predstavlja, zatim pokazivač koji predstavlja X, zatim W, E, L, L, ali ono što vam je potrebno učiniti na kraju je nekako ide, provjerite, došao sam do ovu lokaciju. Tu je riječ koja završava ovdje u strukture podataka. Dakle, ono što trie stvarno je ispunjen, a autor je izabrao da predstavljaju ove terminuses s malim trokutima. To samo znači da je činjenica to trokut je ovdje, to boolean vrijednost istina znači, ako idete natrag u stablu, to znači da je riječ zove Maxwell je u tome. No, riječ foo, na primjer, nije u stablu, jer ako krenem na korijen čvor se ovdje na vrhu, Nema ž pokazivač, ne o pokazivač, ne o pokazivač. Foo nije ime u ovom rječniku. No s druge strane, Turing, t-u-r-i-n-g. Opet, nisam pohraniti t ili u ili R ili ja ili n ili g. Ali sam dućan u ovom strukture podataka vrijednost istinske putu prema dolje, ovdje u ovom čvoru - u stablo postavljanjem ovog boolean vrijednost is_word na true. Dakle trie je vrsta ovog vrlo zanimljivog meta strukture, gdje niste stvarno spremanje riječi se za ovu vrstu rječniku. Da bude jasno, vi ste samo čuvanje da ili ne, tu je riječ koja završava ovdje. Sada ono što je implikacija? Ako imate 150.000 riječi u rječniku da ste pokušavate spremiti u memoriju koristite nešto poput povezane liste, ćete imati 150.000 čvorova u vašem povezane liste. I pronalaženje jednog od tih riječi po abecednom redu moglo potrajati O (n) vremena. Linearno vrijeme. No, u slučaju ovdje od trie, što je trčanje vrijeme pronalaženje riječ? Ispada ljepotu ovdje je da, čak i ako imate 149.999 riječi već u ovom rječniku, kao proveden s ovom strukturom podataka, koliko vremena je potrebno pronaći ili umetnuti još jednu osobu na to, kao i Alice, Alice? Pa, to je samo pet, možda šest koraka za prateći karaktera. Zbog presense drugih imena u strukturi ne dobiti na način umetanja Alice. Štoviše, pronalaženje Alice kada postoji 150.000 riječi u ovom rječniku ne dobiti u svoj način pronalaženja Alisa uopće, jer je Alice. . . . . ovdje, jer sam pronašao boolean vrijednost. A ako nema boolean istina, onda je Alice nije u ovom podataka strukturi riječi. Drugim riječima, radi vrijeme pronalaženje stvari i umetanjem stvari u ovaj novi podaci struktura trie je O od - to nije n. Zbog presense od 150.000 ljudi nema nikakvog utjecaja na Alice, čini se. Dakle, nazovimo ga k, gdje je k Maksimalna duljina riječi u engleskom jeziku koji je obično ne više od 20 i nešto znakova. Tako je k konstanta. Dakle, Sveti Gral mi se čini da su našli sada je da je trie, stalnom vremena za umetaka za dohvate, za brisanje. Zbog nekoliko stvari koje su već u strukturi, koji nisu ni fizički tamo. Opet, oni su samo vrsta provjeravaju off, da ili ne, nema utjecaja na njezino buduće vrijeme rada. No, tu je dobio biti kvaka, inače ne bismo izgubiti toliko vremena na svim tim drugim strukturama podataka samo konačno doći do tajnog onaj koji je nevjerojatna. Dakle, ono što cijena plaćamo da bi se postigao ovaj veličinu ovdje? Prostor. Ova stvar je masivan. A razlog da autor nije ga predstaviti ovdje, primijetiti da sve ove stvari koje izgledaju kao polja, nije izvući ostatak stabla, ostatak trie, jer oni samo nisu relevantni za priču. No, sve ove čvorove su super široka, a svaki čvor u stablu zauzima 26 ili zapravo, mogao biti 27 znakova, jer je u ovom slučaju bio sam uključujući prostor za apostrofa tako da smo mogli imati apostrophized riječi. U ovom slučaju, to su široke polja. Dakle, iako oni ne picutured, to traje do masivan iznos od RAM-a. Koji bi moglo biti u redu, especilly u modernom hardveru, ali to je tradeoff. Mi smo dobili manje vrijeme trošiti više prostora. Dakle, gdje je sve ovo ide? Pa, hajdemo napraviti - ajmo vidjeti ovdje. Ajmo napraviti skok s ovim tipom ovdje. Vjerovali ili ne, koliko zabavno kao C je za neko vrijeme sada, mi smo dostizanje točke u semestru u kojem je vrijeme za prijelaz na stvari više modernih. Stvari su na višoj razini. I iako za narednih nekoliko tjedana svejedno ćemo nastaviti da se uroniti u svijetu upućuje i memorije upravljanje da biste dobili taj komfor s kojima smo tada može graditi na, Kraj igra je konačno uvesti, ironično, nije taj jezik. Prespavat ćemo, kao i 10 minuta govori o HTML-u. Sve HTML je jezik za označavanje, a ono što je jezik za označavanje je to niz otvorenih i zatvorenih zagrada zagrade da kažu "da je ovo podebljano ' 'Čine ovaj kurziv' 'čine ovaj centered. " To nije sve što je intelektualno zanimljiv, ali to je super korisno. I to je sigurno sveprisutni ovih dana. No, ono što je snažan o svijetu HTML i web programiranje općenito, gradi dinamične stvari; pisanja koda u jezicima kao što su PHP ili Python ili Ruby ili Jave ili C #. Stvarno, bez obzira na vaš jezik izbora je, i generira HTML dinamički. Generiranje nešto što se zove CSS dinamički. Cascading Style Sheets, što je također o estetici. I tako, iako, danas, ako odem na neku web stranicu kao što je poznato Google.com, i idem na pregled, programer, pogled izvor, koji možda ste učinili prije, ali ide na pregled izvora, ova stvar vjerojatno izgleda prilično zagonetan. No, to je temeljni kod koji implementira Google.com. Na prednjem kraju. A zapravo sve je to pahuljasto estetika stvari. Ovo je CSS ovdje. Ako držim pomicanje dolje ćemo dobiti neki color-coded stvari. Ovo je HTML. Googleov kod izgleda kao nered, ali ako sam zapravo otvoriti drugu prozor, možemo vidjeti neke strukture za to. Ako sam otvoriti ovaj gore, primjetiti ovdje, to je malo više čitati. Idemo vidjeti prije dugo tu oznaku, [riječ] je oznaka, HTML, glava, tijelo, div, skripta, tekst područje, opseg, usmjeren, div. I to je također vrsta zagonetna izgleda na prvi pogled, ali sve ove nered slijedi određene obrasce i ponovljive uzorke, tako da nakon što smo dobili osnove dolje, vi ćete biti u mogućnosti pisati kod ovako i onda manipulirati kod ovako pomoću još jedan jezik, zove JavaScripta. A JavaScript je jezik koji se izvodi unutar pregledniku danas da mi koristimo na Harvard tečajeva, za alat kolegija trgovačkog da Google maps koristi da vam cijela hrpa dinamike, Facebook vam daje pokazati trenutak ažuriranja statusa, Twitter koristi ga da vam pokazati tweets odmah. Sve to ćemo početi da se uroniti u. Ali doći, moramo shvatiti nešto o internetu. Ovaj isječak ovdje je samo minutu, i pretpostavimo za sada je to, u stvari, kako internet funkcionira kao teaser za ono što je oko doći. Dajem vam "Ratnici na Netu." [♫ Sporo refren glazba ♫] [Muško pripovjedač] On je došao s porukom. Uz protokola sve njegove vlastite. [♫ brže elektronske glazbe ♫] On je došao na svijet cool firewall, uncaring routera, i opasnosti daleko gorih od smrti. On je brzo. On je jak. On je TCP / IP, a on je dobio svoju adresu. Ratnici Net. [Malan] Sljedeći tjedan, onda. Internet. Web programiranje. Ovo je CS50. [CS50.TV]