JASON Hirschhorna: Dobrodošli svima Odsjek Seven. Mi smo u tjedan dana sedam tečaja. I ovaj nadolazeći četvrtak je noć vještica, tako sam ja odjeveni poput bundeve. Nisam mogla naginjati i staviti na moje cipele, pa je to razlog zašto sam Samo nosio čarape. Ja također ne nosim ništa u to, pa ne mogu ga skinuti ako je to odvlače pažnju na vas. Unaprijed se ispričavam zbog toga. Vi ne morate zamisliti što se događa. Ja sam nosio bokserice. Tako da je sve dobro. 

Imam dužu priču o tome zašto sam odjeven kao bundeve, ali ja ću se osim što se za kasnije u ovom poglavlju jer ja ne želim da biste započeli. Imamo puno uzbudljivih stvari ići preko ovog tjedna. Većina njih se odnose izravno na ovo tjedan Problem set, pravopisne pogreške. Mi ćemo se ide preko povezani popisi i hash tablice tijekom cijelog dijela. Stavio sam taj popis svaki tjedan, popis Sredstva za vas da vam pomoći s Materijal na ovoj stazi. Ako na gubitku ili ako u potrazi za neke više informacija, provjeriti jedan od ovi resursi. 

Opet, pset6 je pravopisne pogreške, ovotjedni pset. I ona također potiče, a ja potaknuti vas, da koriste neki drugi sredstva posebno za ovu pset. Konkretno, tri sam navedena na zaslonu - gdb, što smo bili upoznati s i bio koristeći za neko vrijeme sada, je će biti vrlo korisna ovaj tjedan. Zato sam stavio da je ovdje. No, kad god radite s C, trebali biste uvijek koristiti gdb se debug svoje programe. Ovaj tjedan također Valgrind. Zna li itko što Valgrind radi? 

PUBLIKA: Ona provjerava curenje memorije? 

JASON Hirschhorna: Valgrind provjerava curenje memorije. Dakle, ako ste malloc nešto u Program, pitate za pamćenje. Na kraju svog programa, imate pisati slobodno o svemu što ste malloced dati pamćenje. Ako ne pisati besplatno na kraju i Vaš program dolazi do zaključka, sve će automatski biti oslobođen. I za male programe, to je nije neka velika stvar. Ali, ako ste pisanje duže trčanje program koji ne prekida, nu, u roku od par minuta ili A nekoliko sekundi, a zatim curenje memorije može postati ogroman posao. 

Tako je za pset6, očekuje se da ćete imati nula curenje memorije s vaš program. Za provjeru curenja memorije, pokrenuti Valgrind i to će vam dati neke lijepe Izlaz ostavljajući znate li ili ne sve je bilo besplatno. Mi ćemo vježbati s njim kasnije danas, nadam se. 

Konačno, razl naredbe. Nekada si nešto slično tome u pset5 s zavirite alat. Dopustio da izgledaju iznutra. Također se koristi diff, također, po Problem postaviti spec.. No, u koju dopušteno usporediti dvije datoteke. Ti bi mogao usporediti bitmap datoteku i info zaglavlja rješenje osoblja i Vaše rješenje u pset5 ako ste odabrali da ih koriste. Diff će vam omogućiti da to, kao što je dobro. Možete usporediti točan odgovor za Problem ovotjedni postavljen na vašem odgovoru i vidjeti ako to vodovima ili vidjeti gdje su pogreške. 

Dakle, to su tri dobre alati koji te bi trebao koristiti za ovaj tjedan, a svakako provjerite svoj program s ova tri alata prije okreće u. Opet, kao što sam spomenuo svaki tjedan, Ako imate bilo kakve povratne informacije za mene - i pozitivna i konstruktivna - slobodno glavu na web stranici na dnu ovog klizača a ulaz je tamo. Ja stvarno poštovati bilo i sve povratne informacije. A ako mi dati konkretne stvari koje Ja mogu učiniti za poboljšanje ili da sam dobro da bi me voljeli i dalje, ja to uzeti k srcu i jako truditi da slušaju na Vašoj poruci. Ne mogu obećati da ću učiniti sve, iako, kao što je nosio bundeva kostim svaki tjedan. 

Tako ćemo provesti najveći dio sekcija, kao što sam spomenuo, govori o povezane liste i hash tablice, koje će se izravno odnosi se na Problem postaviti ovaj tjedan. Povezane liste ćemo ići preko relativno brzo, jer smo proveli sajam zalogaj vrijeme ide preko njega u sekciji. I tako ćemo dobiti ravno u kodiranje probleme vezane za popise. I onda na kraju ćemo govoriti o Tablice i kako se oni odnose na to tjedan Problem postaviti. 

Vidjeli ste ovaj kod prije. To je rekonstruirati, a definiranje nešto novo zove čvor. A unutar čvorova je cijeli broj upravo ovdje i tamo je kazaljka na još jedan čvor. Vidjeli smo to i prije. To je dolazi za nekoliko tjedana sada. Ona kombinira goniča, koji smo bili rad s, i tvorevina, koje omogućuju us kombinirati dva različita stvari u jednu vrstu podataka. 

Postoji mnogo događa na zaslonu. No, sve to treba biti relativno upoznati s vama. Na prvoj liniji, proglasi novi čvor. I onda u taj novi čvor, postavim broj u tom čvoru na jedan. Vidimo se na sljedećem retku radim printf naredbe, ali sam zasjenjene printf naredbe, jer stvarno Važan dio je ova linija ovdje - new_node.n. Što dot znači? 

PUBLIKA: Idi na čvoru i procijeniti n vrijednost za njega. 

JASON Hirschhorna: To je točno u pravu. Dot znači pristupiti N Part ovog novog čvora. Ovaj sljedeći linija što radi? Michael. 

Ivanković: To stvara još jedan čvor koji će ukazati na novi čvor. 

JASON Hirschhorna: Tako se to ne dogodi stvoriti novi čvor. On stvara što? 

PUBLIKA: pointer. 

JASON Hirschhorna: pokazivač na čvor, kao što je navedeno od strane ove čvor * ovdje. Tako se stvara pokazivač na čvor. A koji čvor je to upućuju da, Michael? 

PUBLIKA: Novi čvor? 

JASON Hirschhorna: Novi čvor. I to pokazuje postoji jer smo dao mu adresu novog čvora. I sada, u ovom retku vidimo dva različita načina izražava istu stvar. I ja sam htjela istaknuti kako se oni Dvije stvari su isti. U prvoj liniji, mi dereference pointer. Dakle, idemo na čvoru. To znači da je ova zvijezda. Vidjeli smo da je prije nego što s pokazivača. Idi na tom čvoru. To je u zagradama. A onda pristupiti putem operatera dot n element tog čvora. 

Tako da je uzimanje sintaksu vidjeli smo ovdje i sada uporabe s pokazivačem. Naravno, ona dobiva u gužvi, ako pišeš one zagrade - da je star i da točka. Ona dobiva malo zauzet. Dakle, imamo neke sintaktičkc šećer. I ova linija upravo ovdje - ptr_node-> n. To se isto točno stvar. Dakle, te dvije linije koda su ekvivalent i da će učiniti točno istu stvar. 

Ali htio sam ukazati onima prije idemo dalje, tako da razumijem da stvarno ova stvar ovdje je samo sintaktička šećer za dereferencing pokazivač, a zatim će se n dio tog Struct. Bilo kakva pitanja o ovom slajdu? OK. 

Tako ćemo proći kroz nekoliko operacija koje možete raditi na povezane liste. Popis povezani, podsjetimo, je serija čvorovi koji ukazuju na jednu drugu. I mi općenito početi s pokazivačem zove glava, općenito, koji ukazuje na Prva stvar na popisu. Dakle, na prvoj liniji ovdje, mi imamo originalnu L prva. Tako da je stvar koju mogu zamisliti - to tekst ovdje možete misliti kako je Samo pointer smo pohranjeni negdje da bodovi na prvi element. I u ovom popisu povezanom imamo četiri čvorišta. Svaki čvor je velika kutija. Veći okvir unutar velike Kutija je cijeli dio. I onda imamo pokazivač dio. 

Ti okviri nisu izvučeni mjerilo jer koliko je velik cijeli broj u bajtovima? Koliko je velik sada? Četiri. A koliko je velika je kazaljka? Četiri. Pa stvarno, ako smo izvući to na ljestvici oba polja će biti iste veličine. U ovom slučaju, želimo umetnuti nešto u popis povezane. Tako možete vidjeti ovdje smo umetanja pet smo prošli kroz povezani popis, naći gdje je pet ide, a zatim ga umetnite. 

Idemo razbiti tu dolje i ići malo sporije. Idem ukazati na brodu. Dakle, mi imamo čvor pet koje koje smo stvorili u mallocs. Zašto se svi smijali? Šalim se. OK. Tako smo malloced pet. Napravili smo ovaj čvor negdje drugdje. Moramo ga spremni ići. Krećemo na prednjoj naš popis s dva. I želimo umetnuti u sortiraju modi. 

Dakle, ako vidimo dva i želimo staviti u pet godina, što nam je činiti kada smo vidjeli nešto manje od nas? Što? Mi želimo umetnuti pet u ovo povezani popis, imajući to riješeno. Vidimo broj dva. Dakle, što nam je činiti? Marcus? 

PUBLIKA: Poziv pokazivač na sljedeći čvor. 

JASON Hirschhorna: A zašto ne idemo na sljedeći? 

PUBLIKA: Zato što je to Sljedeći čvor na popisu. A mi samo znamo da je drugo mjesto. 

JASON Hirschhorna: A pet je veća nego dvije, posebice. Zato želimo ga zadržati sortirani. Do pet je veća od dva. Tako smo prešli na sljedeći. I sada dolazimo do četiri. A što se događa kada dođemo do četiri? 

Pet je veći od četiri. Tako smo zadržati ide. I sad smo na šest. A što mi vidimo u šest? Da, Carlos? 

PUBLIKA: Šest je veći od pet. 

JASON Hirschhorna: Šest je veći od pet. Dakle, to je mjesto gdje želimo umetnuti pet. Ipak, imajte na umu da, ako smo samo jedan pokazivač ovdje - ovo je naš dodatni pokazivač da je poprijeko kroz popis. I mi smo ukazujući na šest. Mi smo zaboravili za što dolazi prije šest godina. Dakle, ako želimo umetnuti nešto u ovaj popis imajući to riješeno, što Vjerojatno je potrebno koliko upućuje? 

PUBLIKA: Dvije. 

JASON Hirschorn: Dvije. Jedan pratiti struje jedan i pratiti prethodni. To je samo popis pojedinačno povezani. To ide samo u jednom smjeru. Ako smo imali popis s dvostruko povezana, gdje sve što je ukazivao na stvar nakon toga i stvar prije njega, a zatim ne bi trebao to učiniti. No, u ovom slučaju ne želimo izgubiti evidenciju o tome što je bilo prije nas, u slučaju trebamo umetnuti pet negdje u sredini. Recimo da su umetanja devet. Što bi se dogodilo kada dobili smo na osam? 

PUBLIKA: Morali bi dobiti taj nulta točka. Umjesto da nulta točka ne bi se dodati element, a zatim su je ukazati na devet. 

JASON Hirschorn: Točno. Tako smo dobili osam. Mi smo do kraja popisa, jer to se pokazuje na nulu. I sada, umjesto da se upućuju na null smo ga upućivati ​​na naš novi čvor. I mi smo postavili pokazivač u naš novi čvor na nulu. Da li itko ima bilo kakvih pitanja o umetanju? Što ako ja ne brinuti se o vođenja popisa riješeno? 

PUBLIKA: Držite ga na početak ili kraj. 

JASON Hirschorn: Držite ga na početak ili kraj. Koji smo trebali učiniti? Bobby? Zašto na kraju? 

Ivanković: Zbog početak je već popunjena. 

JASON Hirschorn: OK. Početak je već popunjena. Tko želi raspravljati protiv Bobbyja. Marcus. 

Ivanković: Pa vjerojatno želite staviti ga na početku, jer inače, ako ste ga stavili na kraj ne bi se prošli cijeli popis. 

JASON Hirschorn: Točno. Dakle, ako ćemo razmišljati o izvođenja, Trajanje umetanja na kraju biti n, veličina ova. Što je veliki O runtime umetanja na početku? Konstantna vrijeme. Dakle, ako vam nije stalo do vođenja nešto izdvojiti, puno bolje da se samo umetnite na početku ovog popisa. I to može biti učinjeno u stalnom vrijeme. 

OK. Sljedeća operacija se naći, i koji drugi - smo formulirano to kao potragu. Ali ćemo gledati kroz povezani popis za neki objekt. Momci su vidjeli kod za tražiti prije u predavanju. Ali mi vrsta upravo je to učinio s umetanje, ili barem umetanje nešto izdvojiti. Možete gledati kroz, idući čvor po čvor, dok ne pronađete broj koji ste u potrazi za. Što će se dogoditi ako ne dođete kraj popisa? Recimo ja sam u potrazi za devet i ja do kraja popisa. Što nam je činiti? 

Ivanković: Povratak lažna? 

JASON Hirschorn: Povratak lažna. Nismo ga pronašli. Ako do kraja popisa i niste pronašli broj ste u potrazi za, to nije tamo. Sva pitanja oko pronaći? Ako je to bio sortirani popis, što bi biti različit za naše traženje? Da. 

PUBLIKA: On će pronaći prve vrijednosti koja je veća od one tražiš i zatim se vratiti false. 

JASON Hirschorn: Točno. Dakle, ako je to sortirani popis, ako možemo doći do nešto što je veće od onoga što tražimo, mi ne trebaju zadržati ide na kraju popisa. Mi smo u tom trenutku može vratiti false jer nećemo ga naći. Pitanje je sada, mi smo govorili o čuvanje povezane liste razvrstani, držeći ih nerazvrstani. To će biti nešto što si Vjerojatno će se morati razmišljati o kada kodiranje problema postaviti pet ako odabrati hash tablicu s odvojenim ulančavanje pristup, koji ćemo govoriti o kasnije. 

No, je li to vrijedno zadržati popis sortirati, a zatim biti u mogućnosti da možda ima brže pretraga? Ili je bolje da brzo umetanje nešto u stalnom izvođenja, ali onda imati više traži? To je tradeoff tamo da vam ću odlučiti što je prikladnije za svoj specifičan problem. I tu nije nužno jedan apsolutno pravo odgovoriti. No, to je svakako odluka dobivate napraviti, a vjerojatno i dobro braniti da, recimo, komentar ili dva zašto ste izabrali jedan nad drugim. 

Konačno, brisanje. Vidjeli smo brisanja. To je slično kao da se traži. Tražimo elementa. Reci mi pokušavamo izbrisati šest. Tako smo pronašli šest ovdje. Ono što imamo kako bi bili sigurni smo to je da je sve što je ukazuje na šest - kao što smo vidjeli u koraku dvojica ovdje - bez obzira što se pokazuje na šest potrebe za preskočiti šest sada i biti promijenjen god šest upire prstom. Mi ne želimo da se ikada Orphan ostatak naš popis zaboravivši postaviti da natrag pointer. A onda ponekad, ovisno Na programu, oni će jednostavno izbrisali ovaj čvor cijelosti. Ponekad ćete se htjeti vratiti vrijednost koja je u ovom čvoru. Dakle to je kako brisanja djela. Bilo kakva pitanja na brisanje? 

PUBLIKA: Dakle, ako idete za brisanje je, bi li samo koristiti besplatno, jer vjerojatno je malloced? 

JASON Hirschorn: Ako želite da se oslobodite nešto što je točno, a vi malloced ga. Reci mi htjeli vratiti tu vrijednost. Mogli bismo se vratili sa šest, a zatim besplatno ovaj čvor i poziv besplatno na njega. Ili ćemo vjerojatno bih nazvati bez prvog , a zatim se vratiti šest. 

OK. Dakle, idemo dalje prakticirati kodiranja. Idemo to kod tri funkcije. Prvi se zove insert_node. Dakle imate kod koji sam ti e-poštom, a ako gledate to kasnije možete pristupiti kodu u linked.c na web stranici CS50. No, u linked.c, postoji neki Kostur kod koji je već napisano je za tebe. A tu je i par funkcija morate napisati. 

Prvo ćemo pisati insert_node. A što radi insert_node jest unosi cijeli broj. A ti daje cijeli broj u popisu povezana. A posebno, trebate da bi popis sortiran od najmanjih do najvećih. Isto tako, ne želim ulažite duplikate. Na kraju, kao što možete vidjeti insert_node vraća bool. Dakle, ti si trebao pustiti korisnik znati li je ili nije umetak uspješna po povratku istina ili laž. Na kraju ovog programa - i za ovu fazu ne treba brinuti o oslobađanju ništa. Dakle, sve što radite je uzimanje cijeli broj i ubacivanja u popisu. 

To je ono što ja tražim od tebe učiniti sada. Opet, u linked.c, koje svi imaju, je kod kostur. A ti bi trebao vidjeti prema dnu Uzorak funkciju deklaracija. No, prije odlaska u to kodiranja u C, vrlo sam Vam savjetujemo da ide kroz korake smo bili trenirao svaki tjedan. Već smo prošli Slika te. Tako da bi trebao imati neke razumijevanje kako se to radi. No, ja bih vas potaknuti da napiše Neki pseudocode prije ronjenja u. I mi ćemo ići preko pseudocode kao skupina. I onda nakon što ste napisali pseudocode, a jednom smo pisani naši pseudocode kao grupa, možete ulaziti u to kodiranje u C. 

Kao glava gore, funkcija insert_node je vjerojatno najzahtjevnijim od tri smo ćemo pisati, jer sam dodao neke dodatne ograničenja za Vaš programiranje, a naročito da nećeš umetnuti bilo duplikati i da je popis treba ostati sortirani. Dakle, ovo je ne-beznačajan Program što vam je potrebno za kodiranje. A zašto ne uzeti pet do sedam minuta samo da se radi o pseudocode i kod. A onda ćemo početi ide kao grupa. Opet, ako imate bilo kakvih pitanja samo digne ruku i ja ću doći oko. . 

Također smo općenito raditi to - ili ja ne izričito vam reći može raditi s ljudima. No, očito, vrlo sam Vam savjetujemo, Ako imate pitanja, pitajte Susjeda sjedi pored tebe ili čak i raditi s nekim drugo, ako želite. To ne mora biti pojedinac tiha djelatnost. 

Počnimo s pisanjem neke pseudocode na brodu. Tko mi može dati prvu liniju pseudocode za ovaj program? Za tu funkciju, a ne - insert_node. Alden? 

PUBLIKA: Dakle, prva stvar koju sam učinio je stvoriti novi pokazivač na čvor i ja inicijaliziran da pokazuje na isti Ono što popis pokazuje da. 

JASON Hirschorn: OK. Dakle, ti si stvaranje novog pokazivač na popisu, a ne na čvoru. 

PUBLIKA: Točno. Da. 

JASON Hirschorn: OK. I onda ono što želimo učiniti? Ono što je nakon toga? Što o čvoru? Nemamo čvor. Mi samo imaju vrijednost. Ako želimo umetnuti čvor, što nam je činiti trebate učiniti prije nego što možemo ni razmišljam o tome umetanjem? 

Publika: Oh, ispričavam se. moramo malloc prostor za čvor. 

JASON Hirschorn: Izvrsno. Učinimo - OK. Ne mogu doći da je visok. OK. Mi ćemo ići prema dolje, a zatim koristimo dva stupca. Ja ne mogu ići tako - OK. Stvaranje novog čvora. Možete napraviti još jedan pokazivač na popis ili se samo može koristiti popis kao što postoji. Zapravo ne trebate učiniti. 

Tako smo stvorili novi čvor. Velika. To je ono što mi radimo na prvom mjestu. Što je sljedeće? 

PUBLIKA: Čekajte. Trebamo stvoriti novi čvor sada ili trebamo čekati da se uvjerite da samo da nema kopije čvora na listi prije nego što smo ga stvorili? 

JASON Hirschorn: Dobro pitanje. Idemo drže da je za kasnije, jer Većina vremena mi ćemo biti stvaranje novi čvor. Tako ćemo zadržati ovdje. No, to je dobro pitanje. Ako smo ga stvorili i nađemo duplikat, što bi trebalo činimo prije povratka? 

PUBLIKA: Oslobodite ga. 

JASON Hirschorn: Da. Vjerojatno ga osloboditi. OK. Što nam je činiti nakon što smo stvoriti novi čvor? Annie? 

Ivanković: Mi smo stavili broj u čvoru? 

JASON Hirschorn: Točno. Mi smo stavili broj - mi malloc prostor. Ja ću ostaviti da sve kao jednu liniju. No, u pravu si. Malloc smo prostor, a zatim stavimo broj u. Možemo čak postaviti pokazivač dio toga na nulu. To je točno. A što je onda nakon toga? Došli smo ovu sliku na ploči. Dakle, što nam je činiti? 

Ivanković: Idemo po popisu. 

JASON Hirschorn: Prođite kroz popis. OK. A što ćemo provjeriti na svakom čvoru. Kurt, što ćemo provjeriti za na svaki čvor? 

PUBLIKA: Pogledaj li n vrijednost čvor koji je veći od n vrijednosti našeg čvora. 

JASON Hirschorn: OK. Ja ću učiniti - Da, u redu. Tako da je n - Ja ću reći, ako je vrijednost veća od tog čvora, a zatim što nam je činiti? 

Ivanković: Pa, onda ćemo umetnite stvar neposredno prije toga. 

JASON Hirschorn: OK. Dakle, ako je veći od toga, onda želimo umetnuti. No, želimo ga umetnite neposredno prije jer mi također bi trebao biti praćenje, a zatim, od onoga što je bilo prije. Dakle, prije nego što uložite. Dakle, vjerojatno ćemo nešto propustili ranije. Vjerojatno ćemo morati biti čuvanje evidenciju o tome što se događa. No, mi ćemo se vratiti tamo. Dakle, što je vrijednost manja od? Kurt, što nam je činiti ako je vrijednost je manja od? 

PUBLIKA: Onda samo zadržati ide osim ako je to posljednja. 

JASON Hirschorn: Sviđa mi se to. Dakle, ići na sljedeći čvor. Osim ako je to posljednja - vjerojatno Provjeravamo za to u smislu stanja. Ali da, pored čvora. I to je sve preniska, pa ćemo preseliti ovamo. No, ako je - može svatko vidjeti? Ako smo jednaki, što nam je činiti? Ako vrijednost pokušavamo umetanje jednaka vrijednosti tog čvora? Da? 

PUBLIKA: [nečujan]. 

JASON Hirschorn: Da. S obzirom na to - Marcus je u pravu. Mogli smo možda učinili nešto drugo. No, s obzirom da smo ga stvorili, ovdje trebamo osloboditi, a zatim se vratiti. Oh boy. Je li bolje? Kako ti se čini? OK. Besplatno je i onda ono što radimo vratiti, [nečujan]? OK. Jesmo li mi nedostaje ništa? Pa gdje su mi praćenje od prethodnog čvora? 

Ivanković: Mislim da će to ići nakon što stvorite novi čvor. 

JASON Hirschorn: OK. Tako se na početku vjerojatno ćemo - Da, možemo stvoriti pokazivač na novo čvora, kao prethodni čvor pokazivač i trenutni čvor pointer. Tako ćemo umetnite da je ovdje. Stvaranje struje i natrag upućuje na čvorove. Ali, kada ćemo prilagoditi te naputke? Gdje ćemo to učiniti u kodu? Jeff? 

PUBLIKA: - uvjeti vrijednost? 

JASON Hirschorn: Koji jedan posebno? 

Ivanković: Ja sam samo zbunjena. Ako je vrijednost veća od ovog čvora ne znači da želite otići na sljedeći čvor? 

JASON Hirschhorna: Dakle, ako je naša vrijednost veći od vrijednosti ovog čvora. 

Publika: Da, onda ste željeli ići dalje niz liniju, zar ne? 

JASON Hirschhorna: Točno. Dakle, mi ne ubacite ga ovdje. Ako je vrijednost manja od tog čvora, a zatim idemo na sljedeći čvor - ili onda umetnite prije. 

Publika: Čekaj, što je ovo čvora i koja je vrijednost? 

JASON Hirschhorna: Dobro pitanje. Vrijednost po ovoj definiciji funkcije je ono što mi daje. Tako je vrijednost broj mi dao. Dakle, ako je vrijednost manja od toga čvora, treba nam vremena za umetanje. Ako je vrijednost veća od ovog čvora idemo na sljedeći čvor. I natrag na izvornu pitanje, ipak, gdje je - 

Ivanković: Ako je vrijednost veća od ovog čvora. 

JASON Hirschhorna: I tako Što da radimo ovdje? Sweet. To je točno. Samo ću napisati ažuriranje naputke. Ali da, s trenutne ti bi ga ažurirati ukazuju na sljedeću. Sve drugo što smo nestali? Tako da ću upisati taj kod u gedit. I dok sam to učiniti, možete imati još par minuta da rade na kodiranje ovo u C 

Dakle, imam Unesite pseudocode. Quick note prije nego što započnete. Možda nismo u mogućnosti da u potpunosti ovo dovršiti u svemu tri od tih funkcija. Tu je točna rješenja za njih da ću e-mail na vas dečki Nakon dijelu, a to će biti objavljena na CS50.net. Dakle, ja ne savjetujemo vam da ići pogledati na dionicama. Ohrabrujem vas da se pokušate na svoj posjedovati, a zatim koristiti praksu Problemi Da biste provjerili svoje odgovore. To su sve bili dizajnirani da blisko odnose se i držati se onoga što morate raditi na problemu skupa. Dakle, ja ne potičemo vas da to vježbamo na svoju ruku, a zatim koristiti kod za provjerite svoje odgovore. Jer ja ne želim da se presele na hash tablice u nekom trenutku u odjeljku. Dakle, nismo mogli dobiti kroz sve to. No, mi ćemo učiniti što više možemo sada. 

OK. Počnimo. Asam, kako ćemo stvoriti novi čvor? 

PUBLIKA: Vi ne struct *. 

JASON Hirschhorna: Pa smo ima da se ovdje. Oh, ispričavam se. Govorili ste indetifikaciju *. 

Ivanković: I onda [? vrste?] čvor ili c čvor. 

JASON Hirschhorna: OK. Ja ću ga nazvati new_node tako da možemo ostati dosljedan. 

Ivanković: I vi želite postaviti da na glavu, prvi čvor. 

JASON Hirschhorna: OK. Dakle, sada je to ukazivanje na - tako da je ovo nije stvorio novi čvor još. To samo pokazuje da prvi čvor u popisu. Kako stvoriti novi čvor? Ako mi treba prostor za stvaranje novog čvora. Malloc. I koliko je velik? 

PUBLIKA: veličina struct. 

JASON Hirschhorna: veličina Struct. A što se rekonstruirati zove? 

PUBLIKA: čvor? 

JASON Hirschhorna: čvor. Dakle malloc (sizeof (čvor)); daje nam prostora. A je to linija - jedna stvar je netočno na ovoj liniji. Je new_node pointer na struct? To je generički naziv. Što je to - čvora, točno. To je čvor *. I što nam je činiti odmah nakon smo malloc nešto, Asan? Što je prvo što nam je činiti? Što ako to ne radi? 

Publika: Oh, provjerite je li to ukazuje na čvoru? 

JASON Hirschhorna: Točno. Dakle, ako ste new_node jednako dosegne null, što nam je činiti? To vraća bool, ovu funkciju. Točno. Izgleda dobro. Bilo što dodati tamo? Mi ćemo dodati stvari na kraju. No, kako je do sada izgleda dobro. Stvaranje sadašnje i prijašnje naputke. Michael, kako mogu to učiniti? 

PUBLIKA: Ti bi napraviti čvor *. Morao bi napraviti jedan ne za new_node ali za čvorovi već imamo. 

JASON Hirschhorna: OK. Dakle, trenutni čvor smo na. Nazvat ću to valuta. U redu. Mi smo odlučili želimo zadržati dva, jer moramo znati ono što je prije njega. Što im se inicijalizira na? 

PUBLIKA: Njihova vrijednost u našem listu. 

JASON Hirschhorna: Dakle, što je Prva stvar na našem popisu? Ili kako znamo gdje na početku našeg popisa je? 

Ivanković: Nije li to prošlo u funkciji? 

JASON Hirschhorna: Točno. To je prošlo u redu ovdje. Dakle, ako je prošlo u funkciji, početak popisa, što bismo mi postaviti struje jednaka? 

PUBLIKA: Popis. 

JASON Hirschhorna: Popis. To je točno. Sada ima adresu početak našeg popisa. A što je s prethodnih? 

PUBLIKA: Popis minus jedan? 

JASON Hirschhorna: Postoji ništa prije toga. Dakle, što možemo učiniti kako bi se pokazalo ništa? 

PUBLIKA: Null. 

JASON Hirschhorna: Da. To zvuči kao dobra ideja. Savršeno. Hvala Vam. Prođite kroz popis. Konstantin, koliko ćemo dugo proći kroz popis? 

Ivanković: Dok smo doći null. 

JASON Hirschhorna: OK. Dakle, ako, dok je, za petlju. Što da radimo? 

PUBLIKA: Možda za petlje? 

JASON Hirschhorna: Idemo raditi za petlju. OK. 

Ivanković: I mi reći - do tekuće pokazivač nije jednak nuli. 

JASON Hirschhorna: Dakle, ako znamo stanje, kako možemo napisati petlju temelji off tom stanju. Kakav petlje trebamo koristiti? 

Ivanković: Dok. 

JASON Hirschhorna: Da. To ima više smisla na temelju off od onoga što je rekao. Ako mi samo želimo ići u smo da bi samo znam da je stvar, to bi smisla raditi while petlja. Iako trenutna ne odgovara null, Ako je vrijednost manja od ovog čvora. Akshar, daj mi tu liniju. 

Ivanković: Ako trenutni-> n n manje od vrijednosti. Ili obrnuto da. Prebacite taj nosač. 

JASON Hirschhorna: Žao mi je. 

Ivanković: Promjena nosača. 

JASON Hirschhorna: Dakle, ako je to veći od vrijednosti. Budući da je zbunjujuće s komentirati gore, ja ću to učiniti. No, da. Ako je naša vrijednost je manje od toga čvora, što nam je činiti? Oh. Imam ga ovdje. Umetnite prije. OK. Kako ćemo to učiniti? 

PUBLIKA: Je li to još uvijek ja? 

JASON Hirschhorna: Da. 

PUBLIKA: Vi - new_node-> next. 

JASON Hirschhorna: Zato što je Hoće li to biti jednak? 

Ivanković: Bit će jednake struje. 

JASON Hirschhorna: Točno. I tako drugi - što još trebamo ažurirati? 

PUBLIKA: Provjerite je li prošlost jednako null. 

JASON Hirschhorna: Ako prev - pa ako pret jednaka null. 

Ivanković: To znači da će postati glava. 

JASON Hirschhorna: To znači da to je postalo glavu. Dakle, što nam je činiti? 

Ivanković: Mi radimo glavu jednaka new_node. 

JASON Hirschhorna: Voditelj jednako new_node. A zašto glavu ovdje, ne popis? 

Ivanković: Zbog glava je globalni varijabla koja je polazno mjesto. 

JASON Hirschhorna: Sweet. OK. I - 

PUBLIKA: Onda još ne prev-> Sljedeći jednako new_node. A onda se vratite istina. 

JASON Hirschhorna: Kamo postavili smo new_node kraj? 

PUBLIKA: Bih - Postavio sam da je na početku. 

JASON Hirschhorna: Pa što crta? 

PUBLIKA: Nakon if ček ako je poznato. 

JASON Hirschhorna: Ovdje? 

Publika: Ja bih to new_node-> n jednaka vrijednosti. 

JASON Hirschhorna: Zvuči dobro. Vjerojatno ima smisla - ne znamo Trebate znati što popis smo na jer mi smo samo bave s jednom popisu. Dakle, bolje funkciju deklaracija za to je samo da biste dobili osloboditi od ovaj cijelosti i samo stavite vrijednost u glavu. Mi čak ne trebate znati Popis onoga što smo u. Ali ja ću ga zadržati za sada i zatim ga promijeniti nakon ažuriranja dijapozitive i Kodeksa. Tako da izgleda dobro za sada. Ako vrijednost - tko može napraviti ovu liniju? Ako - Što da radimo ovdje, Noah. 

Ivanković: Ako je vrijednost veća nego valuta-> n - 

JASON Hirschhorna: Kako napraviti idemo na sljedeći čvor? 

PUBLIKA: Curr.Pharm.Des-> n jednak new_node. 

JASON Hirschhorna: Tako je n što dio struct? Cijeli broj. I new_node je pokazivač na čvor. Dakle, što je dio valuta trebamo ažurirati? Ako ne nje, onda ono što je drugi dio? Noah, što je drugi dio. 

Publika: Oh, naprijed. 

JASON Hirschhorna: Dalje, točno. Točno. Sljedeća je onaj pravi. I što još trebamo ažurirati, Noah? 

PUBLIKA: The pokazivače. 

JASON Hirschhorna: Tako ažuriramo struje. 

PUBLIKA: Prethodna-> next. 

JASON Hirschhorna: Da. OK, mi ćemo pauzirati. Tko nam može pomoći? Manu, što bi trebali učiniti? 

PUBLIKA: Moraš postaviti je jednak valuta-> Next. No, to prije prethodne linije. 

JASON Hirschhorna: OK. Bilo što drugo? Akshar. 

Ivanković: Ne mislim da si trebao promijeniti Curr-> next. Mislim da smo trebali učiniti valuta dosegne valuta-> next ići na sljedeći čvor. 

JASON Hirschhorna: Žao mi je, gdje? Na što crta? Ova linija? 

Publika: Da. Provjerite valuta jednaka valuta-> next. 

JASON Hirschhorna: Pa to je točno jer struja pokazivač na čvor. I želimo ukazati na sljedećoj čvora što je sve trenutno Pokazao je. Valuta sebi ima naprijed. Ali, ako bismo se ažurirati curr.next, mi će biti ažuriranje stvarni znanje sama, a ne gdje je to pointer je pokazivao. Što o ovoj liniji, iako. Avi? 

PUBLIKA: Prethodna-> next jednako valuta. 

JASON Hirschhorna: Pa opet, ako je pret pokazivač na čvor, pret-> next je Stvarni pokazivač u čvor. Dakle, to bi se ažuriranje pokazivač na čvor valuta. Mi ne želimo da se ažurirati pokazivač na čvor. Želimo da se ažurirati natrag. Pa kako ćemo to učiniti? 

Ivanković: To bi samo biti prev. 

JASON Hirschhorna: Točno. Prošli je pokazivač na čvor. Sada smo ga mijenja na Nova pokazivač na čvor. OK Neka nas premjestiti prema dolje. Konačno, ovaj posljednji uvjet. Jeff, što mi radimo ovdje? 

Ivanković: Ako je vrijednost jednak akt-> n. 

JASON Hirschhorna: Žao mi je. Ajme meni. Što? Vrijednost == valuta-> n. Što nam je činiti? 

PUBLIKA: Vi bi oslobodili našu new_node, a onda bih se vratiti false. 

JASON Hirschhorna: To je ono što smo do sada napisano. Ima li itko išta dodati prije nego što ćemo napraviti? OK. Idemo probati. Kontrola može doći do kraja od ne-praznina funkcije. Avi, što se događa? 

PUBLIKA: Jeste li trebao staviti povrat istina izvan while petlje? 

JASON Hirschhorna: Ne znam. Da li mi želimo? 

Ivanković: Nema veze. Ne. 

JASON Hirschhorna: Akshar? 

Ivanković: Mislim da je značilo da stavi povratak false na kraju while petlje. 

JASON Hirschhorna: Pa gdje želiš to ići? 

PUBLIKA: Poput izvan while petlje. Dakle, ako ste izašli iz while petlje to znači da ste došli do kraja i ništa se nije dogodilo. 

JASON Hirschhorna: OK. Dakle, što nam je činiti u ovdje? 

PUBLIKA: Vraćate lažna kao i tamo. 

JASON Hirschhorna: Oh, mi učinite to na oba mjesta? 

Publika: Da. 

JASON Hirschhorna: OK. Hoćemo li ići? Ajme meni. Žao mi je. Ispričavam se na zaslonu. To je vrsta šiziti na nas. Dakle, odabrati opciju. Zero, po kodu, zatvara program. Jedan unosi nešto. Idemo umetnite tri. Umetak nije bila uspješna. Idem isprintati. Ja nemam ništa. OK. Možda je to bio samo slučajnost. Umetnite jedan. Ne uspješna. OK. Trčimo preko GDB jako brzo provjeriti što se događa. 

Zapamti gdb. / Naziv vašeg Program nas dobiva u GDB. Je li to puno za nositi? Treperi? Vjerojatno. Zatvorite oči i uzeti neke duboke diše, ako se umorite gleda na to. Ja sam u GDB. Što je prvo što mi je činiti u GDB? Moramo shvatiti ono što se ovdje događa. Idemo vidjeti. Imamo šest minuta na slici što se događa. Break glavna. I onda što da radim? Carlos? Run. OK. Idemo odaberite opciju. A što N čini? Next. Da. 

PUBLIKA: Jeste li se ne spominju - Zar nisi rekao da je glava, bilo je inicijalizira na nulu na početku. Ali mislio sam da si rekao da je u redu. 

JASON Hirschhorna: Idemo - pogledajmo u GDB, a onda ćemo se vratiti. No, to zvuči kao da već imate neke ideje o tome što se događa. Na taj način želimo umetnuti nešto. OK. Mi smo umetnuli. Unesite int. Mi ćemo umetnuti tri. I onda sam na ovoj liniji. Kako mogu ići početi ispravljanje pogrešaka umetak poznat funkciju? Ajme meni. To je puno. Je li to izluđuje puno? 

Publika: Oh, da je umro. 

JASON Hirschhorna: Upravo sam ga izvadio. OK. 

PUBLIKA: Možda je to drugi kraj žice. 

JASON Hirschhorna: Wow. Dakle, dno crta - Što ste rekli? 

PUBLIKA: Rekao sam ironija tehničku poteškoće u ovoj klasi. 

JASON Hirschhorna: Znam. Kad bih imala kontrolu nad tim dijelom. [Nečujan] Zvuči sjajno. Zašto se vi, dečki početi razmišljati o ono što smo mogli učiniti u redu, , a mi ćemo se vratiti u 90 sekundi. 

Avica, ja ću vas pitati kako to ide unutar insert_node to debug. Dakle, ovo je mjesto gdje smo zadnji put stali. Kako mogu ući insert_node, Avica, ispitati što se događa? Što GDB naredba? Break me ne bi unutra. Da li Marquise znate? 

PUBLIKA: Što? 

JASON Hirschhorna: Što GDB naredba Koristim ići u ovu funkciju? 

PUBLIKA: korak? 

JASON Hirschhorna: Korak putem S. To mi unutra. OK. New_node mallocing neki prostor. To sve izgleda da je idući. Neka je ispitati new_node. On je dobio neku memorijsku adresu. Pogledajmo - da je sve točno. Dakle, sve što je ovdje čini se raditi ispravno. 

PUBLIKA: Koja je razlika između P i zaslon? 

JASON Hirschhorna: P stoji za tisak. I tako me pitate što je Razlika između toga i ovo? U tom slučaju, ništa. No, općenito postoje neke razlike. A ti bi trebao izgledati u GDB priručniku. No, u tom slučaju, ništa. Mi imaju tendenciju da koriste otisak, iako je, zbog ne trebamo učiniti mnogo više nego ispisati jednu vrijednost. 

OK. Dakle, mi smo na liniji 80 našeg koda, postavljanje čvora * Curr jednak popisu. Neka nam ispisati valuta. To je jednako popis. Sweet. Čekaj. Ona iznosi nešto. To ne izgleda dobro. Tu smo. To je zato što je u GDB, zar ne, ako je to je linija ste na njemu još nije izvršena. Dakle, potrebno je zapravo tip uz izvršavanje crtu prije nego što vidim svoje rezultate. Dakle, tu smo. Upravo smo izvršiti ovu liniju, natrag jednaka null. Pa opet, ako ćemo ispisati natrag nećemo vidjeti ništa čudno. Ali ako mi zapravo izvršiti da crta, pa ćemo vidjeti da cijev radio. 

Dakle, imamo valuta. Oni su i dobra. Zar ne? Sada smo na ovoj liniji ovdje. Dok valuta nije jednak null. Pa, što to valuta jednaka? Upravo smo vidjeli da iznosio null. Ispisala smo. Ja ću ga ispisati ponovo. Tako je da while petlja će se izvršiti? 

Ivanković: Ne. 

JASON Hirschhorna: Pa kad sam upisali da linije, vidjet ćete skočio smo skroz dolje na dnu, povratak false. A onda ćemo se vratiti false i vratite se u naš program i na kraju isprintati, kao što smo vidjeli, umetak nije bio uspješan. Dakle, svatko tko ima bilo kakve ideje o tome što što trebate učiniti kako bi riješili ovaj? Ja ću čekati dok ne vidim par ruku ići gore. Nismo izvršiti to. Imajte na umu, ovo je bio prvi put što smo radili. Neću napraviti par. Ja ću učiniti malo. Zbog par znači dvoje. Ja ću čekati za više od dva. 

Prvi prvom stavljanju, Curr, po defaultu jednak null. I ova petlja samo izvršava ako valuta nije null. Pa kako mogu dobiti oko ovoga? Ja vidim tri ruke. Ja ću čekati za više od tri. Marcus, što vi mislite? 

Ivanković: Pa, ako je to potrebno da se izvršiti više od jednom, samo ga promijeniti na do-while petlje. 

JASON Hirschhorna: OK. Hoće li to riješiti naš problem, iako? 

Ivanković: U ovom slučaju ne radi Činjenica da je popis prazan. Pa onda vjerojatno samo treba dodati izjavu da će, ako se petlja izlazi onda morate biti na kraju Popis, na kojem vas uputiti samo mogu umetnuti. 

JASON Hirschhorna: Sviđa mi se to. To ima smisla. Ako petlje izlazi - jer ćete se vratiti false ovdje. Dakle, ako na petlji izlaza, onda smo na kraj popisa, ili možda početak popisa, ako u njemu nema ničega to, što je isti kao i na kraju. Dakle, sada želimo umetnuti Nešto je ovdje. Pa kako se to kod izgleda, Marcus? 

Ivanković: Ako ste već dobili čvor malloced, možete samo reći new_node-> next jednako null, jer to mora biti na kraju. Ili new_node-> next jednako null. 

JASON Hirschhorna: OK. Oprostite. New_node-> next jednako null zato što smo na kraju. To ne staviti ga u. Kako ćemo to staviti na popisu? Točno. To je samo postavljanje jednaka. No kako smo to zapravo stavite ga na popisu? Što se upućuju na kraj popisa? 

Ivanković: voditelj. 

JASON Hirschhorna: Žao mi je? 

PUBLIKA: Voditelj pokazuje na kraju liste. 

JASON Hirschhorna: Ako ovdje nema ničega Popis, glava se upućuju na kraj popisa. Tako da ću raditi za Prvi umetanja. Što ako postoji par stvari na popisu? Nego što mi ne želimo postaviti glavu jednaka new_node. Što želimo tamo raditi? Da? Vjerojatno natrag. Hoće li to raditi? Sjetite se da je samo natrag pokazivač na čvor. I prethodni je lokalna varijabla. Dakle, ova linija će postaviti lokalnu varijablu, natrag, jednak ili pokazujući na taj novi čvor. To nije zapravo će ga staviti u našem listu, iako. Kako ćemo to staviti na našem popisu? Akchar? 

Ivanković: Mislim da ti napraviti trenutni-> next. 

JASON Hirschhorna: OK. valuta-> next. Pa opet, jedini razlog zbog kojeg smo dolje ovdje je, što se sadašnja jednaka? 

PUBLIKA: Jednako null. 

JASON Hirschhorna: Pa što će se dogoditi ako nam je činiti nul-> next? Što ćemo dobiti? Mi ćemo dobiti grešku segmentaciju. 

Ivanković: Do valuta jednaka null. 

JASON Hirschhorna: To je ista stvar kao prev, ipak, jer postoji područna promjenljiva smo postavljanje jednaka je ovaj novi čvor. Vratimo se na našu sliku umetanja nešto. Reci mi umetanja na kraju popisa, tako da upravo ovdje. Imamo trenutni pokazivač koji je ukazujući na nulu i prethodne točke koja upućuju na 8.. Dakle, ono što mi je potrebno ažurirati, Avi? 

PUBLIKA: Prethodna-> next? 

JASON Hirschhorna: Prethodna-> next je ono želimo ažurirati, jer to zapravo će ga stavite na kraj popisa. Još uvijek imamo jednu grešku, ipak, da ćemo upasti u. Što je to bug? Da? 

Ivanković: Bit će da se vrate netočno u ovom slučaju? 

JASON Hirschhorna: Oh, je je će se vratiti false. Ali postoji još jedan bug. Dakle, mi ćemo morati staviti u povratku pravog. 

PUBLIKA: Da li natrag dalje jednaka null na vrhu popisa? 

JASON Hirschhorna: Pa natrag dalje jednaka null na samom početku. Pa kako možemo prijeći preko toga? Da? 

Ivanković: Mislim da možete učiniti provjeriti Prije while petlja vidjeti je li to Popis prazna. 

JASON Hirschhorna: OK. Dakle, idemo ovdje. Da li ček. Ako - 

PUBLIKA: Dakle, ako glava jednaka jednaka null. 

JASON Hirschhorna: Ako glava jednaka jednaka null - koji će nam reći ako je prazan list. 

Ivanković: I onda ste učiniti glava jednaka novo. 

JASON Hirschhorna: Voditelj jednako new_node? I što još trebamo učiniti? 

Ivanković: I onda se vratite istina. 

JASON Hirschhorna: Ne baš. Nedostaje nam jedan korak. 

PUBLIKA: New_node iduće treba ukazivati ​​na nulu. 

JASON Hirschhorna: Točno, Alden. A onda se možemo vratiti istinito. OK. No, to je još uvijek dobra ideja za napraviti stvari na kraju popisa, zar ne? U redu. Mi smo još uvijek zapravo mogli dobiti na kraju liste. Tako je to kod redu ako smo na kraju popisa, a tu su i neke stvari na popisu? Zar ne? Budući da još uvijek imamo Marcus ideju. Mogli bismo izašli iz ove petlje, jer mi smo na kraju popisa. Tako ćemo i dalje žele to kod ovdje dolje? 

Publika: Da. 

JASON Hirschhorna: Da. I ono što mi je potrebno da se to promijeni kako bi? Istina. To zvuči dobro svima do sada? Bilo tko imati bilo - Avi, imate li što dodati? 

Ivanković: Ne. 

JASON Hirschhorna: OK. Tako smo napravili par promjena. Mi smo napravili ovu provjeriti prije nego što otišao je u prazno popisu. Tako smo pobrinuti prazan popisu. I tu smo se pobrinuo za umetanje nešto na kraju liste. Dakle, čini se kao što je ovaj, dok loop preuzimanju brigu o stvarima između, negdje u popisu ako su stvari na popisu. 

OK. Neka nam pokrenuti ovaj program. Ne uspješna. 

PUBLIKA: Nisi uspjeti. 

JASON Hirschhorna: Oh, Nisam to napraviti. Dobro pitanje, Michael. Dodajmo make povezani. Line 87 postoji greška. Line 87. Alden, to je linija koju mi ​​je dao. Što ne valja? 

Ivanković: To mora biti na nulu. 

JASON Hirschhorna: Izvrsno. Točno u pravu. To bi trebao biti nula. Idemo napraviti opet. Sastaviti. OK. Idemo umetnite tri. Umetak je uspješna. Idemo ga isprintati. Oh, kad bismo mogli provjeriti. No, nismo učinili ispisati još funkciju. Idemo ući nešto drugo. Što bismo trebali ući? 

PUBLIKA: Seven. 

JASON Hirschhorna: Sedam? 

Publika: Da. 

JASON Hirschhorna: Imamo grešku SEG. Tako smo dobili jedan, ali mi je jasno Ne mogu dobiti dva. Bilo je 05:07. Tako smo mogli debug to za tri minute. Ali idem da nas ostaviti ovdje i prelazak na hash tablice. Ali opet, odgovore za ovaj broj Ja ću ga na e-mail za vas u malo. Mi smo vrlo blizu tome. Vrlo Ohrabrujem vas shvatiti ono što se ovdje događa i to popraviti. Dakle, ja ću vam e-mail ovaj kod kao i plus rješenje - Vjerojatno kasnije rješenje. Prvo ovaj broj. 

Druga stvar koju želim učiniti prije nego što smo završila je nismo oslobodili ništa. Dakle, želim vam pokazati što Valgrind izgleda. Ako ćemo pokrenuti Valgrind granice Na našem programu. / povezani. Opet, sukladno ovom klizača, što treba pokrenuti Valgrind s nekim vrstama mogućnost, u ovom slučaju - Curenje-check = puni. Tako ćemo pisati Valgrind - Curenje-check = puni. Dakle, to će pokrenuti Valgrind na našem programu. I sad program zapravo radi. Tako ćemo ga pokrenuti baš kao i prije, staviti nešto u. Ja ću staviti u tri. To radi. Neću se pokušati staviti u nečemu drugo, jer si mi ide na dobiti SEG False na tom slučaju. Tako ću i prestati. 

I sad vidite ovdje curiti i hrpa sažetak. Ovo su dobre stvari koje želite provjeriti. Dakle hrpa sažetak - piše, u uporabi na izlazu - osam bajtova u jednom bloku. To je jedan blok čvora smo malloced. Michael, rekli ste prije čvor je osam ugriza jer ima cijeli broj i pokazivač. Dakle, to je naša čvor. I onda je, kaže koristili smo malloc sedam puta, a mi oslobodili nešto šest puta. No, mi nikada ne zove slobodna, tako da nemam Ideja o čemu se govori. 

No, dovoljno je reći da kada vaš Program traje, malloc se zove u nekim drugim mjestima koje smo ne morate brinuti o tome. Dakle malloc vjerojatno zvao u nekim mjestima. Mi ne trebamo brinuti gdje. Ali ovo je stvarno nas. Ova prva linija nam. Ostavili smo taj blok. I možete vidjeti da je ovdje u sažetku curenja. Još uvijek dostupna - osam bajtova u jednom bloku. To znači da je pamćenje - smo procurila tog sjećanja. Definitivno izgubili - nešto što je izgubljeno zauvijek. Općenito, nećete vidim ništa tamo. Ipak dostupna je općenito gdje vidjet ćete stvari, gdje ćete željeti gledati da se vidi što kod treba li su oslobođeni, ali ste zaboravili da se oslobodi. 

A onda, ako to nije bio slučaj, ako smo učinili sve što je besplatno, možemo provjeriti. Ajmo pokrenuti program Ne stavljajući u ništa. Vidjet ćete ovdje u upotrebi na izlazu - nula bajtova u nula blokova. To znači da smo imali više ničega kada je ovaj program izašao. Dakle, prije uključivanja u pset6, pokrenuti Valgrind i pazite da ne morate bilo memorije curi u svom programu. Ako imate bilo kakvih pitanja s Valgrind, slobodno doprijeti. No, to je način kako ste ga koristiti. Vrlo jednostavno - vidjeti ako ima u uporabi na izlazu - bilo bajtova u svim blokovima. 

Tako smo radili na insert čvor. Imao sam i druge dvije funkcije ovdje - ispis čvorova i besplatne čvorove. Opet, to su funkcije koje će biti dobro za vas na praksi jer oni će vam pomoći ne samo s testni vježbe, ali i na problem postavljen. Oni map na prilično usko stvari ti si idući u morati učiniti u Problem postaviti. Ali ja ne želim da se uvjerite Dotaknut ćemo o svemu. I Tablice su od ključnog značaja za što radimo u ovom poglavlju tjedan - ili u set problema. 

Tako ćemo završiti poglavlje govori o hash tablice. Ako primijetite sam napravio Malo hash tablicu. To nije ono što mi govorimo o tome, međutim. Radi se o drugačija vrsta hash tablica. I u svojoj srži, a hash tablicu nije ništa više od Niz plus hash funkcija. Idemo razgovarati malo samo bi bili sigurni svatko razumije što je hash funkcija. A ja ti govorim sada da je to ništa više od dvije stvari - polje i hash funkcija. I ovdje su koraci kroz koji to radi. 

Tu je naša polja. Tu je naša funkcija. Konkretno, funkcija raspršivanja je potrebno napraviti par stvari s tim. Ja ću posebno razgovarati o tome je problem postaviti. Vjerojatno će uzeti u nizu. A što će to vratiti? Koji tip podataka? Alden? Vratiti Vaš hash funkcija? Cijeli broj. Dakle, to je ono mljeveno meso Tablica se sastoji od - stol u obliku niza i hash funkcija. Kako to radi? Ona radi u tri koraka. Dajemo mu ključ. U ovom slučaju, mi ćemo mu dati niz. Pozivamo hash funkciju po korak jedan na ključu, a mi dobili vrijednost. 

Naime, mi ćemo reći smo dobili cijeli broj. Taj broj, tu su vrlo specifične ograničenja na ono da je cijeli broj može biti. U ovom primjeru, naš niz je veličine tri. Dakle, što se brojevi mogu biti da cijeli. Što je raspon važećih vrijednosti za da broj, tip ovog povratnog hash funkciju? Nula, jedan i dva. Točka hash funkcije je shvatiti mjesto u nizu gdje je naš ključni ide. Postoje samo tri moguća mjesta ovdje - nijedan, jedan ili dva. Dakle, ova funkcija bolji povratak nijedan, jedan ili dva. Neki vrijedi indeksom u ovom polju. 

A onda, ovisno o tome gdje se vraća, možete vidjeti postoji niz open zagrada vrijednost. To je mjesto gdje možemo staviti ključ. Dakle bacamo u bundevu, ćemo izaći na nulu. U polje zagrada 0, stavili smo bundevu. Poklanjamo u mačaka, izađemo jedan. Mi smo stavili mačka u jednom. Mi smo stavili u pauka. Mi smo dobili iz dva. Mi smo stavili pauka u polje zagrada dva. Bilo bi lijepo ako je to je radio tako. No, na žalost, kao što ćemo vidjeti, to je malo složeniji. 

Prije nego što smo se tamo, na sva pitanja o tome osnovni set-up od hash tablice? To je slika točno ono što mi je nacrtao na ploči. No, budući da ga je nacrtao na ploči, ja neću ići u njega i dalje. U osnovi tipke, magija crna kutija - ili u ovom slučaju, tirkizna kutija - od hash funkcija stavlja ih u kante. I u ovom primjeru smo Ne stavljajući ime. Mi smo stavljanjem pripadajući telefon broj imena u kantu. No, što bi mogao vrlo dobro samo stavi ime u kantu. 

To je samo slika onoga mi je nacrtao na ploči. Imamo potencijalne zamke, ipak. A tu su i dva osobito slajdovi da želim ići preko. Prvi je o tome hash funkcija. Zato sam pitao pitanje, što čini dobru funkciju ljestve? Dajem dva odgovora. Prvi je da je deterministička. U kontekstu hash funkcija, Što to znači? Da? 

Ivanković: To se može pronaći Indeks je u stalnom vrijeme? 

JASON Hirschhorna: Da nije ono što to znači. No, to je dobar pogodak. Ima li još netko pogađati na što to znači? To je dobra funkcija hash je deterministička? Annie? 

Ivanković: To ključ može se preslikati samo na jednom mjestu u hash tablicu. 

JASON Hirschhorna: To je točno u pravu. Svaki put kada se stavi u bundevu, to se uvijek vraća na nulu. Ako ste stavili u bundevu i vaše mljeveno meso Funkcija vraća na nulu, ali ima vjerojatnost povratka nešto još veći od nule - pa možda to može vratiti jednu ponekad ili druga dva puta - to nije dobro funkcija hash. Vi ste upravo pravo. Vaš hash funkcija trebala vratiti Isti broj točan, u ovom slučaju, jer Isti točan niz. 

Možda se vrati na isti točan cijeli broj za istu točnim nizu bez obzira kapitalizacije. No, u tom slučaju to je još uvijek deterministička jer više stvari se preslikati na istu vrijednost. To je u redu. Tako dugo dok je samo jedan izlaz za određenu ulaz. 

OK. Druga stvar je da je vraća valjane indekse. Doveli smo se da je i ranije. Ovaj hash funkcija - oh boy - hash funkcija treba povratak valjane indekse. Tako kažu - Idemo natrag u ovom primjeru. Moj hash funkcija broji do slova u riječi. To je hash funkcija. I vraća da cijeli broj. Dakle, ako imam riječi A, to je će se vratiti jedan. I to će se staviti ovdje. Što ako sam stavio u riječi palicom? To će se vratiti tri. Odakle bat ide? 

To se ne uklapa. Ali, to treba da ide negdje. Ovo je moja hash tablicu, nakon svega, i sve treba da ide negdje. Pa gdje bi trebao ići šišmiša? Bilo misli? Pogodi? Dobri nagađanja? 

PUBLIKA: Zero. 

JASON Hirschhorna: Zašto nula? 

Ivanković: Zbog tri modulo tri nula? 

JASON Hirschhorna: Tri modulo tri nula. To je velika pretpostavka, i to je točno. Dakle, u ovom slučaju to bi trebalo vjerojatno ići na nulu. Dakle, dobar način da se osigura da se ovaj hash Funkcija vraća samo valjane indekse se to modulo veličinom stola. Ako modulo štogod ove povrate od tri, uvijek ćeš dobiti nešto između nula, jedan, dva i. A ako se to uvijek vraća sedam, a ti uvijek modulo trojica, ti si Uvijek će dobiti istu stvar. 

Dakle, to je još uvijek deterministička ako modulo. No, to će se pobrinuti da Vam nikada dobiti nešto - nevažeća industrija. Općenito, to bi se trebalo dogoditi modulu unutar hash funkciji. Dakle, ne morate brinuti o tome. Vi samo mogu osigurati da to vrijedi s indeksom. Bilo kakva pitanja na ovaj potencijalna zamka? 

OK. I tamo idemo. Sljedeća potencijalna zamka, a ovo je velika stvar. Što ako se dvije tipke Karta na istoj vrijednosti? Dakle, postoje dva načina da se to srediti. Prvi se zove linearni sondiranje, koji sam neće ići preko. No, trebali biste biti upoznati s načinom koji radi i što je to. 

Drugi ću ići preko jer to je onaj koji su mnogi ljudi će vjerojatno završiti odlučivanju za korištenje u njihov problem setu. Naravno, ne morate se. No, za rješavanje problema skupa, mnogi ljudi imaju tendenciju da se odlučite za stvaranje hash tablicu sa zasebnim ulančavanje za provedbu njihov rječnik. Tako ćemo ići preko onoga što to znači stvoriti hash tablicu s odvojeno ulančavanje. 

Zato sam stavio u bundevu. On se vraća na nulu. I sam stavio bundevu ovdje. Onda sam stavio u - ono što je još jedan Halloween-tematske stvar? 

PUBLIKA: Candy. 

JASON Hirschhorna: Candy! To je jedan veliki. Stavio sam u slatkišima i bombonima također mi daje nulu. Što da radim? Bilo koji ideja? Zato što svi nekako znali ono odvojeno ulančavanje je. Dakle, bilo koji ideja što da radim? Da. 

PUBLIKA: Stavljanje niz zapravo u hash tablicu. 

JASON Hirschhorna: Pa idemo u nacrtati dobru ideju ovamo. OK. 

PUBLIKA: Jeste hashtable [Nečujan] pokazivač koji upućuje na Početak popisu. A onda su se bundeve biti prva vrijednost u tom povezanom popisu i slatkiša biti Druga vrijednost u tom povezanom popisu. 

JASON Hirschhorna: OK. Marcus, koji je bio izvanredan. Ja ću razbiti taj niz. Marcus je rekao ne prebrisati bundevu. To bi bilo loše. Nemojte staviti slatkiše negdje drugdje. Mi ćemo ih staviti i na nulu. Ali ćemo se nositi s stavljajući ih na nulu stvaranja popisa na nuli. I mi ćemo stvoriti popis sve što se preslikava na nulu. A najbolji način smo naučili stvoriti Popis koja može narasti i smanjiti dinamički nije unutar još jedan niz. Dakle, ne višedimenzionalni niz. No, kako bi samo stvoriti popis povezana. 

Dakle, ono što je on predložio - Ja ću dobiti novi - je stvoriti niz s pokazivače, Niz pokazivača. OK. Imate li ideju ili savjet što tip ovog pokazivače treba biti? Marcus? 

PUBLIKA: upućuje na - 

JASON Hirschhorna: Zato što vam rekao Popis povezani, pa - 

PUBLIKA: Čvor upućuje? 

JASON Hirschhorna: Čvor naputke. Ako se stvari u našem povezani Popis su čvorovi onda oni trebao biti čvor naputke. A što oni jednaki početku? 

PUBLIKA: Null. 

JASON Hirschhorna: Null. Dakle, tu je naš prazna stvar. Vraća bundeve nulu. Što nam je činiti? Šetnja me kroz njega? Zapravo, Marcus već mi je dao. Netko drugi me provesti kroz to. Što nam je činiti kada smo - ovo izgleda vrlo slično ono što smo upravo radili. Avi. 

Ivanković: Idem uzeti pogodak. Dakle, kada ste dobili slatkiše. 

JASON Hirschhorna: Da. Pa, dobili smo bundevu. Idemo naš prvi. Imamo bundevu. 

Ivanković: U redu. Vraća bundeve nulu. Znači li to staviti u to. Ili zapravo, da ga stavi u popisu povezane. 

JASON Hirschhorna: Kako nam je činiti stavite ga na popisu povezanom? 

Publika: Oh, stvarna sintakse? 

JASON Hirschhorna: Dovoljno je prošetati - reći više. Što nam je činiti? 

PUBLIKA: Vi samo stavite je kao prvi čvor. 

JASON Hirschhorna: OK. Dakle, mi imamo čvor, bundeve. I sad kako sam ga umetnite? 

PUBLIKA: Vi dodijeliti da pokazivača. 

JASON Hirschhorna: Koji pointer? 

PUBLIKA: pointer na nuli. 

JASON Hirschhorna: Pa gdje to upućuje? 

PUBLIKA: Da nulu upravo sada. 

JASON Hirschhorna: Pa, to ukazuje na nulu. Ali sam stavljajući u bundevu. Pa gdje bi trebao ukazati? 

Publikom: bundeva. 

JASON Hirschhorna: Da bundeve. Točno. Dakle, to ukazuje na bundeve. A gdje je taj pointer u bundeve trenutku? Na 

PUBLIKA: Null. 

JASON Hirschhorna: na nulu. Točno. Pa jednostavno umetnuti nešto u popisu povezane. Upravo smo pisali ovaj kod za to. Gotovo smo skoro ga dobio potpuno puknut. Sada smo umetnuli slatkiše. Naš candy također ide na nulu. Dakle, što nam je činiti s bombonima? 

Ivanković: To ovisi o tome hoće li ili Ne pokušavamo to riješiti. 

JASON Hirschhorna: To je točno u pravu. To ovisi o tome hoće li ili ne pokušavamo to riješiti. Pretpostavimo da nismo će se to riješiti. 

Ivanković: Pa onda, kao što smo razgovarali prije, to je najjednostavniji samo da ga stavi odmah na početku, tako kazaljka s nula bodova do slatkiša. 

JASON Hirschhorna: OK. Držite se. Dopustite mi stvorili slatkiše ovdje. Dakle, ovo pokazivač - 

Publika: Da, trebali sada se upućuju na slatkiše. Tada su pokazivač iz candy točka na bundeve. 

JASON Hirschhorna: Kao ovo? I kažu mi imamo još jedan stvar mapirati na nulu? 

Ivanković: Pa, vi samo učiniti istu stvar? 

JASON Hirschhorna: Da li ista stvar. Dakle, u ovom slučaju, ako to ne učinimo želim ga zadržati ga razvrstani Zvuči prilično jednostavna. Mi se pokazivač u indeksom dao našoj hash funkciji. Imamo tu točku na naše nove čvora. A onda je sve što je pokazivao ranije - u ovom slučaju null, u Drugi slučaj bundeve - da, bez obzira na to što ukazuje na ranije, dodamo u najbližu naš novi čvor. Mi smo nešto umetanja u početku. U stvari je to puno jednostavnije nego pokušavajući zadržati popis sortiran. Ali opet, u potrazi će biti složeniji ovdje. Uvijek ćemo morati ići do kraja. 

OK. Sva pitanja o zasebnom ulančavanje? Kako se to radi? Molimo pitajte ih sada. Stvarno želim da biste bili sigurni da svi Razumijem to, prije nego što krenete. 

Ivanković: Zašto ste stavili bundevu i bombona u isto dio hash tablice? 

JASON Hirschhorna: Dobro pitanje. Zašto smo ih staviti u isti dio hash tablice? Pa, u tom slučaju naš hash funkcija se vraća na nulu za obojicu. Zato što im je potrebno ići na nulu indeksom , jer je to mjesto gdje ćemo potražite ih ako mi ikada želim ih gledati. Opet, s linearnim pristupom sondiranja ne bismo ih stavili i na nulu. No, u odvojenom lanca pristupa, ćemo ih i na nulu a zatim napraviti popis od od nule. 

A mi ne želimo da se prebrisati bundeve samo za to, jer onda ćemo Pretpostavljamo da je bundeva Nikada umetnuta. Ako smo samo zadržati jednu stvar u mjesto koje bi bilo loše. Tada ne bi bilo šanse od nas ikad - Ako smo ikada imali duplikat, onda smo samo bi izbrisali našu početnu vrijednost. Dakle, to je razlog zašto smo napraviti ovaj pristup. Ili je to razlog zašto smo izabrali - ali opet, mi izabrao poseban ulančavanje pristup, koji postoje mnogi drugi pristupi nije mogao birati. Je li to odgovor na vaše pitanje? 

OK. Carlos. Linearni sondiranje će uključivati ​​- ako smo našli sudar na nuli, mi će izgledati u sljedećem licu mjesta kako bi vidjeli je li to je bio otvoren i staviti ga tamo. I onda gledamo u sljedećem sportu i vidjeti ako to je bio otvoren i staviti ga tamo. Tako ćemo naći sljedeći slobodni otvoren mjesto i staviti ga tamo. Bilo koja druga pitanja? Da, Avi. 

PUBLIKA: Kao nastavak na to, Što misliš sljedećem licu mjesta? U hash tablicu ili na popisu povezane. 

JASON Hirschhorna: Za linearne programiranje, nema povezane liste. Sljedeći mjesto na hash tablicu. 

Ivanković: U redu. Dakle hash tablica će biti inicijalizira na veličinu - kao broj nizova da li su umetanjem? 

JASON Hirschhorna: ti bi želim da to bude stvarno velika. Da. Ovdje je slika onoga što smo Upravo je nacrtao na ploči. Opet, imamo sudar upravo ovdje. na 152. I vidjet ćete da je stvorio povezani Popis izvan nje. Opet, hash tablicu zasebna ulančavanje pristup nije ona koju morati uzeti za set problemi šest, ali je onaj koji puno studenti imaju tendenciju da se. Dakle, na to, idemo ukratko razgovarati Prije nego što krenete o problemu šest, a onda ću podijeliti priču s vama. Imamo tri minute. 

Problem postaviti šest. Imate četiri funkcije - opterećenja, ček, veličina, i rasteretiti. Load - Pa, mi smo bili ide tijekom opterećenja tek sada. Mi nacrtao teret na brodu. A mi ni počeo kodiranja puno umetanje u popis povezane. Dakle opterećenje ne mnogo više od ono što smo upravo radili. 

Provjerite je nakon što su nešto učita. To je isti proces kao ovaj. Isti prva dva dijela gdje se bacaju nešto u hash funkcije i dobiti svoju vrijednost. Ali, sada nam nije umetnuti. Sada smo u potrazi za njom. Imam uzorak kod napisan za pronalaženje nešto u popisu povezana. Ohrabrujem vas da praksa da. Ali intuitivno pronalaženje nešto je prilično sličan umetanja nešto. Doista, došli smo sliku o pronalaženju nešto u popisu povezanom, kreće kroz sve što je dobio na kraju. A ako je dobio na kraju i nije mogao ga naći, onda to ne postoji. Tako da je ček, u biti. 

Sljedeća je veličina. Idemo preskočiti veličinu. Konačno ste iskrcati. Iskrcati jedan nismo izvučeni na brodu ili još kodirane. No, ja Vam savjetujemo da pokušate to kodiranja u našem uzorka povezane s popisom primjer. Ali iskrcati intuitivno sličan je besplatno - ili mislim slična provjeriti. Osim za sada svaki put idete putem, niste jednostavno provjerite da vidjeti ako imate svoju vrijednost postoji. Ali ste uzimajući da je čvor i ga osloboditi, u biti. To je ono što ste izvadili pita za napraviti. Besplatno je sve što ste malloced. Tako da ideš kroz cijeli popis opet, prolazi kroz cijelu mljeveno meso Tablica opet. Ovaj put ne provjerite vidjeti što je tamo. Samo osloboditi onoga što je tamo. 

I na kraju veličina. Veličina trebao biti proveden. Ako ne provede veličinu - Ja ću reći ovako. Ako ne provede veličinu u točno jedna linija koda, uključujući vratiti izjavu, koju su radi veličine pogrešno. Na taj način osigurati veličinu, za puni dizajn boda, radite to u točno jednom linija koda, uključujući Izjava povratak. 

I ne spakirati još, Akchar. Željni dabar. Htio sam reći hvala vam dečki za dolazak na dijelu. Imati sretan Halloween. Ovo je moj kostim. Ja ću se nositi ovo u četvrtak ako sam vas vidjeti u uredovno vrijeme. A ako ste znatiželjni o tome nešto više pozadina kao da taj kostim, osjećam slobodno provjeriti 2011 Odjel za priču o tome zašto sam nosio kostim bundeve. I to je tužna priča. Dakle, pobrinite se da imate neki tkiva u blizini. No, na to, ako imate bilo Pitanja ću staviti oko izvan nakon dijelu. Sretno na problemu postaviti šest. I kao i uvijek, ako imate bilo pitanja, javite mi.