JASON Hirschhorn: Bine ati venit toată lumea la secțiunea Seven. Suntem în săptămâna de șapte a cursului. Și această viitoare joi este Halloween așa că eu sunt îmbrăcat ca un dovleac. Nu am putut indoi peste și a pus pe pantofii mei, de aceea sunt purtând doar șosete. De asemenea, nu port nimic sub acest lucru, așa că am putea să nu-l scoate, dacă este distrage pentru tine. Îmi cer scuze în avans pentru asta. Nu aveți nevoie să ne imaginăm ceea ce se întâmplă. Sunt poartă boxeri. Deci, totul e bine. 

Eu am o poveste mai lungă despre ce sunt îmbrăcat ca un dovleac, dar am de gând să cu excepția că pentru mai târziu în această secțiune pentru că eu nu vreau să începeți. Avem o mulțime de lucruri interesante pentru a trece peste această săptămână. Cele mai multe dintre ele se referă direct la acest set problemă saptamana, greșeli de ortografie. Vom merge peste legată liste și tabele de dispersie pentru întreaga secțiune. Am pus această listă în fiecare săptămână, o listă a resurse pentru tine pentru a te ajuta cu material de pe acest curs. În cazul în care la o pierdere sau în cazul în care căutarea unor mai multe informații, a verifica afară unul din aceste resurse. 

Din nou, pset6 este greseli de scriere, PSET această săptămână. Și, de asemenea, te încurajează, și eu vă încurajez, să utilizeze alte resurse în mod special pentru acest PSET. În special, cele trei am listate pe ecran - gdb, pe care am fost familiarizați cu și a fost folosind pentru un timp acum, este va fi de foarte mare ajutor în această săptămână. Așa că am pus asta aici. Dar ori de câte ori lucrați cu C, ar trebui să fie întotdeauna folosind gdb la depana programele pe care. În această săptămână, de asemenea, Valgrind. Stie cineva ce Valgrind face? 

Audiența: Se verifică pentru pierderi de memorie? 

JASON Hirschhorn: Valgrind verificări pentru pierderi de memorie. Deci, dacă ai ceva malloc în ta Programul, ceri pentru memorie. La sfârșitul programului dumneavoastră, aveți pentru a scrie liber pe tot ceea ce ai malloced pentru a da memoria înapoi. Dacă nu scriu liber, la sfârșitul și programul dvs. ajunge la o concluzie, totul va fi în mod automat să fie eliberat. Și pentru programe mici, este Nu mare lucru. Dar dacă sunteți scris o funcționare mai program care nu renunta, în mod necesar, în câteva minute sau o câteva secunde, apoi de memorie scurgeri poate deveni o afacere mare. 

Deci, pentru pset6, speranța este că va avea pierderi de memorie la zero cu programul. Pentru a verifica pentru pierderi de memorie, a alerga Valgrind și-l voi da ceva frumos ieșire permițându-vă să știu dacă sau nu totul a fost gratuit. Vom exersa cu el mai târziu astăzi, sperăm. 

În final, comanda dif. Ai folosit ceva similar cu o în pset5 cu instrumentul ochiul. Permis să se uite înăuntru. Puteți, de asemenea folosit diff, de asemenea, pe Problema set spec.. Dar în Ai voie să compara două fișiere. Ai putea compara fișierul bitmap și anteturile informații dintr-o soluție de personal și soluția în cazul în care pset5 ați ales să-l folosească. Diff vă va permite să face acest lucru, la fel de bine. Puteți compara răspunsul corect pentru problema din această săptămână stabilit pentru răspunsul dumneavoastră și a vedea dacă se aliniază sau vedea în cazul în care erorile sunt. 

Deci, acestea sunt cele trei instrumente bune pe care ar trebui să utilizați pentru această săptămână, și verificați cu siguranta programul dvs. cu aceste trei instrumente înainte de a porni-l inch Din nou, așa cum am menționat în fiecare săptămână, dacă aveți orice feedback-ul pentru mine - atât pozitivă și constructivă - nu ezitați să mergeți la site-ul web în partea de jos a acestei diapozitiv și de intrare-l acolo. Apreciez orice și toate feedback-ul. Și dacă-mi dai lucruri specifice pe care Ce pot face pentru a îmbunătăți sau care sunt face bine că v-ar place de mine să continua, eu iau asta la inimă și încearcă într-adevăr greu pentru a asculta pentru feedback-ul dumneavoastră. Nu pot să promit că voi face totul, deși, cum ar fi purtarea un dovleac costum în fiecare săptămână. 

Așa că am de gând să-și petreacă cea mai mare parte a secțiune, așa cum am menționat, vorbesc despre liste legate și tabele de dispersie, care va fi direct aplicabile problema stabilit această săptămână. Liste legate vom merge peste relativ repede pentru că ne-am petrecut un pic echitabil de timp a merge peste ea în secțiunea. Și astfel vom ajunge direct în codificare pentru probleme legate de liste. Și apoi, la sfârșitul vom vorbi despre hash mese și modul în care se aplică această problema săptămână stabilit. 

Ați văzut acest cod înainte. Acesta este un struct, și este definirea ceva nou numit un nod. Și în interiorul unui nod este un număr întreg chiar aici și acolo este un pointer la un alt nod. Am mai văzut asta înainte. Acest lucru a fost vine pentru câteva săptămâni acum. Acesta combină indicii, pe care le-am fost de lucru cu, și structs, care permit ne să combine două tipuri diferite lucrurile într-un singur tip de date. 

Există o mulțime întâmplă pe ecran. Dar toate ar trebui să fie relativ familiarizat cu tine. Pe prima linie, am declara un nou nod. Și apoi în interiorul că noul nod, am stabilit întreg în care nodul la unul. Ne vedem pe linia următoare fac o printf comanda, dar am gri comanda printf pentru că într-adevăr parte importantă este această linie aici - new_node.n. Ce înseamnă punctul spui? 

Audiența: Du-te la nodul și evalua valoarea n pentru ea. 

JASON Hirschhorn: Asta-i exact dreapta. Dot înseamnă acces la n partea din acest nou nod. Această linie viitoare ce face? Michael. 

Audiența: Se creează un alt nod care va indica la noul nod. 

JASON Hirschhorn: Deci, nu a crea un nou nod. Se creează o ce? 

Audiența: Un pointer. 

JASON Hirschhorn: Un pointer la un nod, așa cum este indicat prin acest nod * aici. Deci, se creează un pointer la un nod. Și care nod este o îndreptat la, Michael? 

Audiența: nod nou? 

JASON Hirschhorn: nod nou. Și este îndreptat acolo pentru că ne-am având în vedere că adresa de nod nou. Și acum, în această linie vom vedea două moduri diferite de exprimă același lucru. Și am vrut să subliniez modul în care acestea două lucruri sunt la fel. În primul rând, am dereferire indicatorul. Deci, mergem la nodul. Asta e ceea ce înseamnă acest lucru stea. Am văzut că, înainte cu indicii. Du-te la acel nod. Care este în paranteze. Și apoi a accesa prin intermediul operatorului dot elementul de n acel nod. 

Astfel că, luând sintaxa am văzut aici și acum folosindu-l cu un pointer. Desigur, acesta devine un fel de ocupat în cazul în care sunteți scris aceste paranteze - că stele și acel punct. Ea devine un pic ocupat. Deci avem niște zahăr sintactic. Și aceasta linie de aici - ptr_node-> n. Care face exact același lucru. Deci, cele două linii de cod sunt echivalente și va face exact același lucru. 

Dar am vrut să subliniez acele înainte de a merge mai departe, astfel încât să înțelegeți că într-adevăr acest lucru chiar aici este doar zahăr sintactic pentru dereferencing indicatorul și apoi merge la n partea de care struct. Orice întrebări cu privire la acest diapozitiv? OK. 

Așa că am de gând să treacă printr-un cuplu operațiunilor pe care le puteți face pe liste legate. O listă legată, amintesc, este o serie de noduri care trimit unul altuia. Și, în general, vom începe cu un pointer numit cap, în general, care indică primul lucru pe listă. Deci, pe prima linie de aici, ne-am au L noastră originală primul. Astfel încât lucru vă puteți gândi de - acest text, chiar aici, vă puteți gândi ca doar indicatorul care le-am stocat că undeva puncte la primul element. Și în această listă legată avem patru noduri. Fiecare nod este o cutie mare. Caseta de mare din interiorul Big casetă este partea întreagă. Și atunci avem o parte pointer. 

Aceste cutii nu sunt atrași de scară din cauza cât de mare este un întreg în bytes? Cât de mare acum? Patru. Și cât de mare este un pointer? Patru. Deci, într-adevăr, dacă ar fi să atragă acest lucru la scară ambele cutii ar fi de aceeași dimensiune. În acest caz, dorim să introduceți ceva în lista de legătura. Astfel încât să puteți vedea aici vom introduce cinci Am traversa prin lista legate, găsiți în cazul în care cinci merge, și apoi introduceți-l. 

Să rupe-l jos și du-te un pic mai lent. Am de gând să subliniez la bord. Deci avem nod noastre cinci care am creat în mallocs. De ce este toată lumea de râs? Glumeam. OK. Deci, ne-am malloced cinci. Am creat acest nod în altă parte. Avem gata să meargă. Noi încep de la partea din față a lista cu doi. Și ne-o dorim pentru a insera într-un mod sortat. 

Deci, dacă vom vedea două și ne-o dorim pentru a pune în cinci, ce facem când vedem ceva mai puțin decât noi? Ce? Vrem să inserați cinci în acest lista legate, menținându-l sortate. Vom vedea numărul doi. Deci, ce facem? Marcus? 

Audiența: Sunați la indicatorul următorului nod. 

JASON Hirschhorn: Și de ce mergem la următorul? 

Audiența: Pentru că este următorul nod în listă. Și știm doar că o altă locație. 

JASON Hirschhorn: Cinci este mai mare mult de două, în special. Pentru că vrem să-l păstrați sortat. Deci, cinci este mai mare de doi. Așa că am trece la următoarea. Și acum ajungem la patru. Și ce se întâmplă atunci când vom ajunge la patru? 

Cinci este mai mare de patru. Așa că am continua. Iar acum suntem la șase. Și ce vedem la șase? Da, Carlos? 

Audiența: Șase este mai mare de cinci. 

JASON Hirschhorn: Six este mai mare de cinci. Deci, asta e în cazul în care ne-o dorim pentru a introduce cinci. Cu toate acestea, rețineți că, dacă ne-am au doar un singur indicator de aici - aceasta este pointer nostru suplimentar care este traversează prin lista. Și ne indică la șase. Ne-am pierdut urma a ceea ce vine înainte de șase. Deci, dacă vrem să introduceți ceva în această listă menținându-l sortate, ne-am , probabil, nevoie de cât mai multe indicii? 

Audiența: Two. 

JASON Hirschorn: Two. O pentru a urmări de curent unul și unul pentru a ține evidența cel anterior. Aceasta este doar o listă individual legat. Se merge doar o singură direcție. Dacă am avea o listă de două ori legat, în cazul în care totul a fost îndreptat la lucru după ce și lucrul înainte de a, atunci nu ne-ar trebui să faci asta. Dar în acest caz nu vrem să-și piardă evidența a ceea ce a venit în fața noastră, în cazul în care avem nevoie de a introduce cinci undeva în mijloc. Spune-ne inserarea nouă. Ce s-ar întâmpla, atunci când am ajuns la opt? 

Audiența: Ar trebui să obține acel punct nul. În loc de a avea punctul de nul vei avea pentru a adăuga un element și apoi au l punct de nouă. 

JASON Hirschorn: Exact. Deci, avem opt. Vom ajunge la sfârșitul listei, deoarece acest lucru se indică la null. Și acum, în loc de a se indica nul trebuie să indice către noul nostru nod. Și ne-am stabilit indicatorul în noul nostru nod la null. Are cineva intrebari despre introducerea? Ce se întâmplă dacă nu-mi pasă de actualiza lista sortată? 

Audiența: Stick-l la începutul sau la sfârșitul. 

JASON Hirschorn: Stick-l la la începutul sau la sfârșitul. Care ar trebui să facem? Bobby? De ce cele din urmă? 

Audiența: Pentru că la început este deja plin. 

JASON Hirschorn: OK. Inceputul este deja plin. Cine vrea să argumenta împotriva lui Bobby. Marcus. 

Audiența: Ei bine, probabil că doriți să stick-l la început pentru că în caz contrar, dacă l-ai pus la final va trebui să- traversa întreaga listă. 

JASON Hirschorn: Exact. Deci, dacă ne gândim la rulare, execuție a introduce la sfârșitul ar fi n, dimensiunea acestei. Care este O rulare mare de a introduce la început? Constantă de timp. Deci, dacă nu-mi pasă despre păstrarea ceva sortate, mult mai bine la doar introduce la începutul acestei liste. Și ce se poate face în timp constant. 

OK. Operație următor este să găsească, pe care alte - am formulat acest lucru ca pe căutare. Dar ne vom uita prin Lista de legat pentru un obiect. Ați văzut cod pentru căutare înainte în curs. Dar am un fel de pur și simplu a făcut-o cu introduce, sau cel puțin de a introduce ceva sortate. Te uiți prin, va nod de nod, până când găsiți numărul pe care ești caută. Ce se întâmplă dacă ajunge sfârșitul listei? Spune caut nouă și eu ajunge la sfârșitul listei. Ce facem? 

Audiența: Înapoi fals? 

JASON Hirschorn: Înapoi false. Noi nu l-am găsit. Dacă ajungi la sfârșitul listei și nu ați găsit numărul pe care ești caută, nu e acolo. Orice întrebări cu privire la găsit? În cazul în care acest lucru a fost o listă sortată, ceea ce ar fi fi diferit pentru căutarea noastră? Da. 

Audiența: ar găsi prima valoare care este mai mare decât cea sunteți în căutarea pentru și apoi să se întoarcă false. 

JASON Hirschorn: Exact. Deci, în cazul în care este o listă sortată, dacă ajungem la ceva care este mai mare decât ceea ce căutăm, nu avem nevoie să mergi la sfârșitul listei. La acel moment, ne putem întoarce false pentru că noi nu o să-l găsească. Întrebarea este acum, am vorbit despre păstrarea listelor legate sortate, menținându-le nesortat. Asta va fi ceva de care ești probabil, va trebui să se gândească la atunci când codificare problema stabilit cinci, dacă alege un tabel hash cu separat abordare înlănțuirea, care vom vorbi despre mai târziu. 

Dar este merită să păstreze lista sortate și apoi să fie capabil de a avea, poate, Cautari mai repede? Sau este mai bine pentru a introduce rapid ceva în timpul rulării constant, dar apoi au mai caută? Acesta este un compromis chiar acolo pe care le ajunge pentru a decide ce este mai adecvat pentru problema dvs. specifice. Și nu e neapărat un răspuns absolut corect. Dar este cu siguranță o decizie te de a face, și, probabil, bun pentru a apăra că în, să zicem, un comentariu sau două de ce ai ales unul peste celălalt. 

În cele din urmă, ștergerea. Am văzut ștergerea. Este similar cu căutarea. Ne uităm pentru elementul. Spune-ne încercarea de a șterge șase. Așa că am găsit șase aici. Lucru pe care trebuie să ne asigurăm că face este că orice este îndreptat la șase - așa cum vom vedea în pasul doi aici - orice este îndreptat la șase trebuie să săriți peste șase acum și să fie modificat pentru a indiferent de șase indică spre. Noi nu vrem să orfani tot restul Lista noastră de a uita de a stabili că pointer anterior. Și apoi, uneori, în funcție de privind programul, ei vor doar șterge acest nod în întregime. Uneori, veți dori să se întoarcă valoarea care este în acest nod. Deci, asta e cum ștergerea lucrărilor. Orice întrebări cu privire la ștergeți? 

Audiența: Deci, dacă ai de gând să-l ștergeți ea, ai doar folosi gratuit, deoarece probabil a fost malloced? 

JASON Hirschorn: Dacă doriți să eliberați ceva care este exact corect și tu malloced ea. Spune-am vrut să se întoarcă această valoare. S-ar putea întoarce șase și apoi gratuit acest nod și fără apel pe ea. Sau probabil ne-ar suna gratuit întâi și apoi să se întoarcă șase. 

OK. Deci, haideți să trecem la practica de codificare. Vom cod trei funcții. Primul se numește insert_node. Deci, aveți cod pe care le-am prin e-mail, și dacă te uiți la asta mai târziu puteți accesa codul în linked.c pe site-ul CS50. Dar în linked.c, există unele cod schelet care este deja a fost scris pentru tine. Și apoi există câteva funcții aveți nevoie pentru a scrie. 

În primul rând vom scrie insert_node. Și ce face insert_node IS introduce un număr întreg. Și dai întreg într-o listă de legat. Și, în special, ai nevoie de pentru a menține lista sortată de la cel mai mic la cel mai mare. De asemenea, nu doriți să introduce orice duplicate. În cele din urmă, după cum puteți vedea insert_node returnează un bool. Deci, tu ar trebui pentru a permite utilizatorului știu dacă inserția a fost sau nu de succes de a reveni adevărat sau fals. La finalul acestui program - și pentru acest stadiu nu aveți nevoie de să vă faceți griji cu privire la eliberarea nimic. Deci, tot ce faci este de a lua un întreg și se introduce într-o listă. 

Asta este ceea ce îți cer să faci acum. Din nou, în linked.c, care vă toate au, este codul de schelet. Și ar trebui să vedeți spre partea de jos declarația funcției de probă. Cu toate acestea, înainte de a merge într-o codificare în C, am foarte vă încurajez să mergeți prin măsurile pe care le-am fost practicarea în fiecare săptămână. Am trecut deja prin o imagine de aceasta. Deci, ar trebui să aveți o înțelegere de modul în care funcționează. Dar v-aș încuraja să scrie unele pseudocod înainte de scufundare inch Și vom trece peste pseudocod ca un grup. Și apoi, o dată ce ați scris dvs. pseudocod, și odată ce ne-am scris noastre pseudocod ca un grup, aveți posibilitatea să du-te în ea codificare în C. 

Ca un heads-up, funcția insert_node este, probabil, mai delicată de trei ne-am de gând să scrie pentru că am a adăugat unele constrângeri suplimentare pentru a programarea, în special, că nu sunteți de gând să introduceți orice duplicate și că lista ar trebui să rămână sortat. Deci, acesta este un program non-trivial de care aveți nevoie să cod. Și de ce nu te duci cinci la șapte minute doar pentru a obține de lucru privind pseudocod și codul. Și apoi vom începe merge ca un grup. Din nou, dacă aveți întrebări doar ridica mâna și voi veni în jur. . 

Noi, de asemenea, în general, face aceste - sau eu nu voi spune în mod explicit poate lucra cu oamenii. Dar, evident, am foarte vă încurajez, dacă aveți întrebări, să solicite vecinul care sta langa tine sau chiar de lucru cu cineva altfel, dacă doriți să. Acest lucru nu trebuie să fie un individ activitate tăcut. 

Să începem cu scrierea unele pseudocod pe bord. Cine poate da-mi prima linie de pseudocod pentru acest program? Pentru această funcție, mai degrabă - insert_node. Alden? 

Audiența: Deci, primul lucru pe care am făcut a fost a crea un nou pointer la nodul și I inițializat se indică spre aceeași lucru care listă este îndreptat la. 

JASON Hirschorn: OK. Deci, creați un nou indicator la lista, nu la nodul. 

Audiența: Corect. Da. 

JASON Hirschorn: OK. Și apoi ce vrem sa facem? Ce după asta? Ce despre nodul? Nu avem un nod. Avem doar o valoare. Dacă vrem să insera un nod, ce facem noi trebuie să faceți înainte de a ne putea chiar cred despre introducerea ea? 

Audiența: Oh, îmi pare rău. avem nevoie pentru a malloc spațiu pentru un nod. 

JASON Hirschorn: Excelent. Să facem - OK. Nu se poate ajunge la această mare. OK. Vom merge în jos, și apoi suntem cu ajutorul a două coloane. Nu pot să merg că - OK. A crea un nou nod. Puteți crea un alt pointer la lista sau puteți folosi doar listă ca ea exista. Nu aveți cu adevărat nevoie să faci asta. 

Așa că am crea un nou nod. Mare. Asta e ceea ce facem noi mai întâi. Ce urmează? 

Audiența: Așteaptă. În cazul în care vom crea un nou nod acum sau ar trebui să ne așteptăm să ne asigurăm că nu exista nici duplicate ale nodului pe lista inainte de a le crea? 

JASON Hirschorn: Bună întrebare. Să susțin că pentru mai târziu, deoarece majoritate a timpului, vom crea un nou nod. Deci, vom păstra asta aici. Dar asta este o întrebare bună. Dacă vom crea și noi găsim un duplicat, ceea ce ar trebui să facem înainte de a reveni? 

Audiența: Eliberați-l. 

JASON Hirschorn: Da. Probabil că-l gratuit. OK. Ce facem după ce ne-am a crea un nou nod? Annie? 

Audiența: Am pus număr în nodul? 

JASON Hirschorn: Exact. Am pus numărul - am malloc spațiu. Am de gând să părăsească toate ca o singură linie. Dar ai dreptate. Noi malloc spațiu, și apoi am pus numărul inch Putem chiar să setați indicatorul o parte din ea la null. Asta-i exact corect. Și atunci ce despre după aceea? Am desenat această imagine de pe bord. Deci, ce facem? 

Audiența: Trecem prin lista. 

JASON Hirschorn: Du-te prin lista. OK. Și ce vom verifica de la fiecare nod. Kurt, ce vom verifica pentru la fiecare nod? 

Audiența: A se vedea dacă valoarea n a acel nod este mai mare decât valoarea n de nod noastre. 

JASON Hirschorn: OK. Am de gând să fac - Da, OK. Deci e n - Am de gând să spun, dacă valoarea este mai mare decât acest nod, atunci ce facem? 

Audiența: Ei bine, atunci vom introduce ceea ce trebuie, înainte de asta. 

JASON Hirschorn: OK. Deci, dacă este mai mare decât aceasta, apoi ne-o dorim pentru a insera. Dar vrem să-l inserați chiar înainte de pentru că avem, de asemenea, ar trebui să fie urmarirea, apoi, din ceea ce a fost înainte. Deci, înainte de a insera. Așa că am ratat, probabil, ceva mai devreme. Probabil, avem nevoie să fie păstrarea urmări ce se întâmplă. Dar vom ajunge acolo. Deci, ce valoare este mai mică? Kurt, ce facem dacă valoare este mai mică? 

Audiența: Apoi, doar continui dacă nu e ultima. 

JASON Hirschorn: Imi place asta. Deci, du-te la urmatorul nod. Doar dacă nu e ultima - suntem, probabil, de verificare pentru care în termenii unei condiții. Dar da, nod următor. Și care este prea mic, așa că ne vom muta aici. Dar, în cazul în care - se poate vedea toată lumea acest lucru? Dacă suntem egali, ce facem? În cazul în care valoarea încercăm să introducă este egală cu valoarea acestui nod lui? Da? 

Audiența: [inaudibil]. 

JASON Hirschorn: Da. Având în vedere acest lucru - Marcus are dreptate. Am fi putut face, poate, ceva diferit. Dar având în vedere că ne-am creat-o, aici ar trebui să ne elibereze și apoi să se întoarcă. Oh boy. E mai bine? Cum e asta? OK. Liber și apoi ce facem noi reveni, [imperceptibil]? OK. Ne lipsește ceva? Deci, unde ne-am ține evidența din nodul anterior? 

Audiența: Cred că ar merge după ce a crea un nou nod. 

JASON Hirschorn: OK. Deci, la început vom probabil - Da, putem crea un pointer la un nou nod, ca un pointer nod anterior și un pointer curent nod. Deci, haideți să introduceți asta aici. Crea curente și anterioare indicii de noduri. Dar atunci când ne adapta aceste indicii? În cazul în care vom face ca în codul? Jeff? 

Audiența: - condițiile de valoare? 

JASON Hirschorn: Care unul în special? 

Audiența: Sunt doar confuz. Dacă valoarea este mai mare decât acest nod, nu asta înseamnă că vrei să mergi la nodul următor? 

JASON Hirschhorn: Deci, în cazul în care valoarea noastră este mai mare decât valoarea acestui nod. 

Publicul: Da, atunci ai vrea să merge mai departe în jos linia, corect? 

JASON Hirschhorn: Corect. Așa că nu-l introduceți aici. Dacă valoarea este mai mică decât acest nod, apoi mergem la nodul următor - sau atunci introduce înainte. 

Audiența: Stai, care este aceasta nod și care este valoarea? 

JASON Hirschhorn: Bună întrebare. Valoarea pe această definiție funcție este ceea ce suntem dat. Deci, valoarea este numărul suntem dat. Deci, dacă valoarea este mai mică decât aceasta nod, avem nevoie de timp pentru a insera. Dacă valoarea este mai mare decât acest nod, mergem la nodul următor. Și înapoi la întrebarea inițială, totuși, în cazul în care - 

Audiența: Dacă valoarea este mai mare decât acest nod. 

JASON Hirschhorn: Și așa ce facem aici? Dulce. Că este corect. Sunt doar de gând să scrie actualizare indicii. Dar, da, cu cel actual v-ar actualiza la punct la următoarea. Orice altceva ne lipsește? Așa că am de gând să tastați acest cod în gedit. Și în timp ce eu fac acest lucru, puteți avea un cuplu mai multe minute pentru a lucra la codificare acest lucru în C. 

Așa că am de intrare pseudocod. O notă rapidă înainte de a începe. Noi nu poate fi în măsură să complet termina acest lucru în toate trei dintre aceste funcții. Există soluții corecte pentru a le că voi e-mail de la voi după secțiune, și se va fi postate pe CS50.net. Așa că nu vă încurajez să du-te uita-te la secțiunile. Am să vă încurajez să încercați aceste pe dvs. proprii, iar apoi utilizați practica Probleme pentru a verifica răspunsurile dumneavoastră. Acestea toate au fost concepute pentru a strâns se referă la și să adere la ceea ce trebuie sa faci pe platourile de filmare problemă. Deci, eu vă încurajez să practice acest pe cont propriu și apoi utilizați codul de verifica răspunsurile dumneavoastră. Pentru că eu nu vreau să se mute la hash tabele la un moment dat în secțiunea. Așa că s-ar putea să nu trece prin toate. Dar noi vom face la fel de mult putem acum. 

OK. Să începem. Asam, cum putem crea un nou nod? 

Audiența: Tu struct *. 

JASON Hirschhorn: Deci, ne-am au ca aici. Oh, îmi pare rău. Ce spuneai struct *. 

Audiența: Și apoi [? fel?] nod sau c nod. 

JASON Hirschhorn: OK. Am de gând să-l numesc new_node astfel încât să putem sta consistent. 

Audiența: Și doriți să setați ca la cap, primul nod. 

JASON Hirschhorn: OK. Deci, acum acest lucru indică spre - astfel încât acest nu a creat un nou nod încă. Acest lucru este pur și simplu indică spre primul nod în listă. Cum pot crea un nou nod? Dacă am nevoie de spațiu pentru a crea un nou nod. Malloc. Și cât de mare? 

Audiența: Dimensiunea struct. 

JASON Hirschhorn: mărimea struct. Și ceea ce se numește struct? 

Audiența: Nod? 

JASON Hirschhorn: Nod. Deci, malloc (sizeof (nod)); ne dă spațiu. Și este această linie - un lucru este incorect pe această linie. New_node este un pointer la o struct? Acesta este un nume generic. Ce este aceasta - nod, exact. Este un nod *. Și ce facem imediat după noi malloc ceva, Asan? Care e primul lucru pe care îl facem? Ce se întâmplă dacă nu funcționează? 

Audiența: Oh, verificați dacă indică nodul? 

JASON Hirschhorn: Exact. Deci, dacă new_node egal la egal la egal null, ce facem? Aceasta returnează un bool, această funcție. Exact. Arata bine. Ceva pentru a adăuga acolo? Vom adăuga lucruri la sfârșitul anului. Dar că până în prezent arată bine. Crea indicii curente și anterioare. Michael, cum fac asta? 

Audiența: Tu ar trebui pentru a face un nod *. Ar trebui să nu o facă pentru new_node dar pentru noduri avem deja. 

JASON Hirschhorn: OK. Deci, nodul curent suntem. Voi suna ca pac. Bine. Ne-am decis că doriți să păstrați două pentru că avem nevoie să știm ceea ce este în fața sa. Ce primesc inițializat la? 

Audiența: Valoarea lor în lista noastră. 

JASON Hirschhorn: Deci, ce este primul lucru pe lista noastră? Sau cum știm unde începând din lista noastră este? 

Audiența: nu este ea a trecut în funcție? 

JASON Hirschhorn: Corect. Acesta a fost adoptată în chiar aici. Deci, dacă este trecut în funcție, începe a listei, ceea ce ar trebui să ne setat curent egal cu? 

Audiența: List. 

JASON Hirschhorn: List. Asta-i exact corect. Acum are adresa începutul listei noastre. Și ce despre anterior? 

Audiența: Lista minus unul? 

JASON Hirschhorn: Nu nimic înainte de a fi. Deci, ce putem face pentru a semnifica nimic? 

Audiența: Null. 

JASON Hirschhorn: Da. Pare a fi o idee bună. Perfect. Mulțumesc. Du-te prin lista. Constantin, cât timp vom pentru a merge prin lista? 

Audiența: Până când vom ajunge la zero. 

JASON Hirschhorn: OK. Deci, dacă, în timp ce, pentru bucla. Ce facem? 

Audiența: Poate o pentru buclă? 

JASON Hirschhorn: Să facem o pentru buclă. OK. 

Audiența: Și noi spunem pentru - până când indicatorul de curent nu este egal cu zero. 

JASON Hirschhorn: Deci, dacă știm condiție, cum putem scrie o buclă bazat pe această condiție. Ce fel de buclă ar trebui să le folosim? 

Audiența: în timp ce. 

JASON Hirschhorn: Da. Care face mai mult sens pe baza off de ceea ce ai spus. Dacă vrem doar să merg în noi că ar fi doar știu că ceva, ar face sens pentru a face o buclă în timp. În timp ce actuala nu este egal cu zero, dacă valoarea este mai mică decât acest nod. Akshar, dă-mi această linie. 

Audiența: Dacă curent-> n n mai putin de valoare. Sau invers asta. Comutator care suport. 

JASON Hirschhorn: Îmi pare rău. 

Audiența: Schimbați suportul. 

JASON Hirschhorn: Deci, dacă este mai mare decât valoarea. Pentru că e confuz cu comentariul de mai sus, am de gând să fac asta. Dar da. În cazul în care valoarea noastră este mai mică decât aceasta nod, ce facem? Oh. Îl am chiar aici. Introduce înainte. OK. Cum facem asta? 

Audiența: Este încă mă? 

JASON Hirschhorn: Da. 

Audiența: Ai - new_node-> următor. 

JASON Hirschhorn: Deci, ce e care merge la egal? 

Audiența: Va curent egal. 

JASON Hirschhorn: Exact. Și astfel de altă parte - ce altceva mai avem nevoie pentru a actualiza? 

Audiența: Verificați dacă trecutul este egal cu zero. 

JASON Hirschhorn: Dacă prev - așa că, dacă prev este egal cu zero. 

Audienta: Asta înseamnă că va pentru a deveni cap. 

JASON Hirschhorn: Asta înseamnă că acesta a devenit cap. Deci, atunci ce facem? 

Audiența: Noi facem cap egal new_node. 

JASON Hirschhorn: Cap este egal cu new_node. Și de ce cap aici, nu lista? 

Audiența: Deoarece cap este un nivel global variabilă, care este locul de pornire. 

JASON Hirschhorn: dulce. OK. Și - 

Audiența: Atunci nu mai prev-> este egal cu următoarea new_node. Și apoi vă întoarceți adevărat. 

JASON Hirschhorn: Unde ne-am stabilit la sfârșitul new_node? 

Audiența: Aș - Am stabilit că la început. 

JASON Hirschhorn: Deci, ce linie? 

Audiența: După if a verifica dacă acesta este cunoscut. 

JASON Hirschhorn: Chiar aici? 

Audiența: Aș face new_node-> n este egal cu valoarea. 

JASON Hirschhorn: Sună bine. Probabil are sens - nu avem Trebuie să știu ce lista suntem pe pentru că avem de-a face doar cu o singură listă. Deci, o declarație funcție mai bun pentru acest lucru este doar pentru a scăpa de această în întregime și doar introduceți o valoare în cap. Nici măcar nu trebuie să știe ceea ce Lista suntem inch Dar voi păstra pentru acum și apoi schimba la actualizarea slide-uri și cod. Astfel că arată bine pentru acum. Dacă valoare - care pot face această linie? În cazul în care - ce facem aici, Noah. 

Audiența: Dacă valoarea este mai mare decât pac-> n - 

JASON Hirschhorn: Cum mergem la nodul următor? 

Audiența: Curr-> n este egal la new_node. 

JASON Hirschhorn: Deci, n este ce face parte din struct? Întreg. Și new_node este un pointer la un nod. Deci, ce parte a curr ar trebui să actualizeze? Dacă nu n, atunci ceea ce este pe de altă parte? Noah, ceea ce este pe de altă parte. 

Audiența: Oh, următorul. 

JASON Hirschhorn: Apoi, exact. Exact. Următorul este cel potrivit. Și ce altceva mai avem nevoie pentru a actualiza, Noah? 

Audiența: The indicii. 

JASON Hirschhorn: Deci, am actualizat curent. 

Audiența: Anterior-> următor. 

JASON Hirschhorn: Da. OK, ne vom opri. Cine ne poate ajuta aici? Manu, ceea ce ar trebui să facem? 

Audiența: Trebuie să setați l egal cu-pac> următor. Dar face acest lucru înainte de linia anterioară. 

JASON Hirschhorn: OK. Altceva? Akshar. 

Audiența: Eu nu cred că ești menirea de a schimba-pac> următor. Cred că ai vrut să faci egal Curr pac-> de lângă pentru a merge la nodul următor. 

JASON Hirschhorn: Îmi pare rău, în cazul în care? Pe ce linie? Această linie? 

Audienta: Da. Face pac egal pac-> următor. 

JASON Hirschhorn: Deci asta e corect deoarece este un curent pointer la un nod. Și vrem să punct la altul nod de ceea ce se obține în prezent a subliniat. Curr sine are un viitor. Dar dacă ar fi să actualizeze curr.next, ne-am ar fi actualizarea nota real în sine, nu unde această pointer a fost îndreptat. Ce zici de această linie, totuși. Avi? 

Audiența: Anterior-> egal următor pac. 

JASON Hirschhorn: Deci, din nou, în cazul în care prev este un pointer la un nod, prev-> următor este pointer real în nodul. Deci, acest lucru ar fi actualizarea o pointer la un nod la pac. Noi nu vrem să actualizați un pointer la un nod. Vrem să actualizeze anterior. Deci, cum facem asta? 

Audiența: Ar fi doar prev. 

JASON Hirschhorn: Corect. Anterior este un pointer la un nod. Acum suntem o schimbare la un nou pointer la un nod. OK Să ne muta în jos. În fine, această ultimă condiție. Jeff, ce facem aici? 

Audiența: Dacă valoare este egal cu pac-> n. 

JASON Hirschhorn: Îmi pare rău. Dumnezeule. Ce? Valoarea == pac-> n. Ce facem? 

Audiența: Ai liber new_node nostru, și apoi te-ai întoarce false. 

JASON Hirschhorn: Aceasta este ceea ce am scris până acum. Are cineva ceva pentru a adăuga înainte de a face? OK. Să încercăm. De control poate ajunge la sfârșitul de o funcție non-gol. Avi, ce se întâmplă? 

Audiența:-ar trebui să pună retur adevărat în afara buclei în timp ce? 

JASON Hirschhorn: Nu știu. Nu vrei să? 

Audiența: Nu contează. Nu. 

JASON Hirschhorn: Akshar? 

Audiența: Cred că ai vrut să pune false întoarcere la sfârșitul din bucla în timp ce. 

JASON Hirschhorn: Deci, în cazul în care vrei să mergi? 

Audiența: La fel ca în afara buclei în timp. Deci, dacă ieși din bucla în timp ce aceea că mijloacele de că ați ajuns la sfârșitul și nimic nu sa întâmplat. 

JASON Hirschhorn: OK. Deci, ce facem aici? 

Audiența: Veți reveni false acolo, de asemenea. 

JASON Hirschhorn: Oh, ne-am o fac în ambele locuri? 

Audienta: Da. 

JASON Hirschhorn: OK. Ar trebui să mergem? Dumnezeule. Îmi pare rău. Îmi cer scuze pentru ecran. Este un fel de speriat de noi. Asa ca alege o opțiune. Zero, pe codul, închide programul. Unul introduce ceva. Să introduce trei. Inserția nu a avut succes. Am de gând să imprima. Nu am nimic. OK. Poate că a fost doar o întâmplare. Introduceți unul. Nu a avut succes. OK. Să fugi prin GDB foarte repede pentru a verifica ce se întâmplă. 

Amintiți-vă gdb. / Numele dvs. Programul ne ajunge în GDB. Este că o mulțime să se ocupe? Intermitent? Probabil. Închide ochii și să ia ceva profund respiră dacă te plictisești de a privi la ea. Sunt în GDB. Care este primul lucru pe care îl fac în GDB? Trebuie să ne dăm seama ceea ce se întâmplă aici. Să vedem. Avem șase minute pentru a cifră ce se întâmplă. Break principal. Și apoi ce fac? Carlos? Rula. OK. Să alegeți o opțiune. Și ce N face? Următor. Da. 

Audiența: Nu ai spus - nu ai spus că șeful, era inițializat la zero la început. Dar am crezut că ai spus că a fost OK. 

JASON Hirschhorn: Să mergem - să ne uităm în GDB, și apoi ne vom întoarce. Dar se pare că aveți deja câteva idei despre ceea ce se întâmplă. Așa că ne-o dorim pentru a introduce ceva. OK. Am introduce. Vă rugăm să introduceți un int. Vom introduce trei. Și atunci eu sunt pe această linie. Cum pot să merg încep de depanare inserția funcție cunoscută? Dumnezeule. Asta e mult. Este că speriat o mulțime? 

Audiența: Oh, ea a murit. 

JASON Hirschhorn: Eu doar a scos-o afară. OK. 

Audiența: Poate e celălalt capăt al firului. 

JASON Hirschhorn: Wow. Deci, linia de jos - Ce-ai spus? 

Audiența: I-am spus ironia de tehnic dificultăți în această clasă. 

JASON Hirschhorn: Știu. Dacă doar am avut control asupra acea parte. [Inaudibil] Asta sună grozav. De ce nu voi începe să gândesc despre ceea ce am fi putut face rău, și vom fi din nou în 90 de secunde. 

Avica, am de gând să vă întreb cum de a merge insert_node interior pentru a depana. Deci, acest lucru este în cazul în care am plecat de pe ultima. Cum pot să merg în interiorul insert_node, Avica, pentru a examina ceea ce se întâmplă? Ce comanda GDB? Break nu m-ar lua în interiorul. Nu știu Marquise? 

Audiența: Ce? 

JASON Hirschhorn: Ce comanda GDB Eu folosesc pentru a merge în această funcție? 

Audiența: Step? 

JASON Hirschhorn: Pasul prin S. Asta mă duce în interior. OK. New_node mallocing spațiu. Că toate arata ca sa mergi. Să examinăm new_node. , Am o anumită adresă de memorie. Să verificăm - care este tot corect. Deci, totul aici pare să fi de lucru corect. 

Audienta: Care este diferența între P și de afișare? 

JASON Hirschhorn: P standuri pentru imprimare. Și astfel încât să ceri ceea ce este diferență între asta și asta? În acest caz, nimic. Dar, în general, există unele diferențe. Și ar trebui să arate în manualul GDB. Dar, în acest caz, nimic. Avem tendința de a folosi de imprimare, deși, pentru că noi nu trebuie să facem mult mai mult decât imprima o singură valoare. 

OK. Deci, suntem pe linia 80 din codul nostru, stabilirea nod * pac egal la lista. Să ne imprima pac. Acesta este egal cu lista. Dulce. Așteaptă. Acesta este egal cu ceva. Asta nu mi se pare corect. Acolo mergem. E pentru că în GDB, drept, în cazul în care este linia esti pe ea nu a executat încă. Deci, ai nevoie să tastați de fapt, lângă executa linia înainte de a vedea rezultatele sale. Deci, aici suntem. Tocmai am executat această linie, precedent este egal cu zero. Deci, din nou, dacă vom imprima anterior nu vom vedea nimic ciudat. Dar dacă am executa de fapt că linie, atunci vom vedea că acea linie a lucrat. 

Deci avem pac. Cei care sunt atât de bună. Corect? Acum suntem pe această linie aici. În timp ce pac nu este egal cu zero. Ei bine, ceea ce face pac egal? Tocmai am văzut-o a fost de nul. Am imprimat. O să-l imprimați din nou. Deci, este că, în timp ce buclă va executa? 

Audiența: Nu. 

JASON Hirschhorn: Deci, când am scris că linie, veți vedea am sărit tot drumul jos la partea de jos, intoarce false. Și apoi vom reveni false și du-te înapoi la programul nostru și în cele din urmă a imprima, cum am văzut, inserția nu a avut succes. Deci, cineva vreo idee cu privire la ceea ce trebuie să facem pentru a remedia acest lucru? Am de gând să aștept până când voi vedea o pereche de mâini du-te în sus. Noi nu am executat acest lucru. Păstrați în minte, acesta a fost primul lucru pe care îl făceam. Eu nu am de gând să fac un cuplu. Am de gând să fac câteva. Pentru ca un cuplu inseamna doi. Voi aștepta mai mult de două. 

La prima introducere, pac, în mod implicit este egal cu zero. Și această buclă execută numai dacă pac nu este nul. Deci, cum pot rezolva aceasta? Văd trei mâini. Voi aștepta mai mult de trei. Marcus, ce crezi? 

Audiența: Ei bine, dacă aveți nevoie de ea pentru a executa mai mult de o dată, tu doar schimba-l la o buclă do-timp. 

JASON Hirschhorn: OK. Va ca rezolva problema noastră, deși? 

Audiența: În acest caz, nu din cauza faptul că lista este goală. Deci, atunci, probabil, ai nevoie doar pentru a adăuga o declarație că, dacă ieșirile bucla atunci va trebui să fie la sfârșitul anului lista, la care punct doar se poate introduce. 

JASON Hirschhorn: Imi place asta. Asta are sens. Dacă bucla iese - deoarece acesta va returna false aici. Deci, dacă ieșirile bucla, atunci suntem la la sfârșitul listei, sau poate începe o listă în cazul în care nu există nimic în aceasta, care este la fel ca la sfârșitul. Deci, acum ne-o dorim pentru a insera ceva aici. Deci, cum poate acest cod arata, Marcus? 

Audiența: Dacă ai deja nodul malloced, ai putea spune doar new_node-> următor este egal cu zero, deoarece trebuie să fie la sfârșit. Sau-new_node> următor este egal cu zero. 

JASON Hirschhorn: OK. Scuze. New_node-> următor este egal cu zero pentru că suntem la sfârșitul anului. Asta nu-l pune inch Cum ne-am pus-o în listă? Corect. Asta e doar o setare egal. Nu cum suntem de fapt pune-l in lista? Ceea ce indică spre la sfârșitul listei? 

Audiența: Cap. 

JASON Hirschhorn: Îmi pare rău? 

Audiența: Head este îndreptat la sfârșitul listei. 

JASON Hirschhorn: Dacă nu e nimic în lista, capul este îndreptat la la sfârșitul listei. Astfel că va lucra pentru în primul rând de inserare. Ce zici dacă există un cuplu lucruri din lista? Mult nu vrem să setați cap egal cu new_node. Ce vrem să facem acolo? Da? Probabil precedent. Va merge? Amintiti-va ca anterior este doar un pointer la un nod. Și anterior este o variabilă locală. Deci, această linie va stabili o variabilă locală, precedent, egal sau arătând spre un nou nod. Că nu se va pune de fapt în lista noastră, deși. Cum ne-am pus-o în lista noastră? Akchar? 

Audiența: Te crezi face curent-> următor. 

JASON Hirschhorn: OK. pac-> următor. Deci, din nou, singurul motiv pentru care suntem în jos aici este, ce face curent egal? 

Audiența: Egal nul. 

JASON Hirschhorn: Și ce se întâmplă dacă facem null-> următor? Ce avem de gând pentru a obține? Vom lua o eroare de segmentare. 

Audiența: Do curr este egal cu zero. 

JASON Hirschhorn: E același lucru ca prev, deși, pentru că există o variabilă locală suntem setarea egal cu acest nou nod. Să ne întoarcem la imaginea noastră de a insera ceva. Spune-ne de a introduce la sfârșitul anului a listei, astfel încât chiar aici. Avem un pointer curent care este arătând spre null și un punct anterior care este îndreptat la 8. Deci, ceea ce avem nevoie pentru a actualiza, Avi? 

Audiența: Anterior-> următoare? 

JASON Hirschhorn: Inapoi-> următoare este ceea ce ne-o dorim pentru a actualiza pentru că se va introduce de fapt la sfârșitul listei. Încă mai avem un bug, totuși, că vom rula în. Ce-i asta bug? Da? 

Audiența: O să se întoarcă false în acest caz? 

JASON Hirschhorn: Oh, este este O să se întoarcă false. Dar există un alt bug. Deci, vom avea nevoie pentru a pune în schimb adevărat. 

Audiența: Are anterior încă egal nul în partea de sus a listei? 

JASON Hirschhorn: încă Deci anterior este egal cu zero la început. Deci, cum putem trece peste asta? Da? 

Audiența: Cred că pot face o verificare înainte bucla în timp ce pentru a vedea dacă este o listă goală. 

JASON Hirschhorn: OK. Deci, haideți să mergem aici. Face o verificare. În cazul în care - 

Audiența: Deci, dacă cap este egal este egal cu zero. 

JASON Hirschhorn: cazul în care capul este egal cu egal nul - care ne va spune dacă este o listă goală. 

Audiența: Și apoi face cap este egal cu noi. 

JASON Hirschhorn: Cap este egal cu new_node? Și ce altceva mai trebuie să facem? 

Audiența: Și atunci vă întoarceți adevărat. 

JASON Hirschhorn: Nu chiar. Ne lipsește un singur pas. 

Audiența: New_node următor trebuie să indice null. 

JASON Hirschhorn: Exact, Alden. Și atunci ne putem întoarce adevărat. OK. Dar este încă o idee bună de a face lucrurile la sfârșitul listei, corect? Bine. Noi încă s-ar putea obține de fapt, la sfârșitul listei. Deci, este acest cod în regulă dacă suntem la sfârșitul listei și există unele lucruri din lista? Corect? Pentru că încă mai avem idee a lui Marcus. Am putea ieși din această buclă, deoarece suntem la sfârșitul listei. Deci, nu ne mai dorim acest lucru codul de aici? 

Publicul: Da. 

JASON Hirschhorn: Da. Și de ce avem nevoie pentru a schimba acest lucru? Adevărat. Sună bine pentru toată lumea până acum? Oricine are orice - Avi, ai ceva de adăugat? 

Audiența: Nu. 

JASON Hirschhorn: OK. Așa că am făcut o serie de schimbări. Am făcut această verificare înainte de a ne intrat pentru o listă goală. Deci, ne-am ocupat de o listă goală. Și aici am avut grija de a introduce ceva la sfârșitul listei. Deci, se pare ca aceasta luare în timp ce buclă grijă de lucruri în între, undeva în listă, dacă există sunt lucruri pe lista. 

OK. Să alergăm din nou acest program. Nu a avut succes. 

Audiența: Tu nu-l face. 

JASON Hirschhorn: Oh, Nu l-am face. Bun punct, Michael. Să adăugăm o face legat. Linia 87 nu este o eroare. Linia 87. Alden, aceasta a fost linia pe care mi-ai dat. Ce sa întâmplat? 

Audiența: Trebuie să fie la null. 

JASON Hirschhorn: Excelent. Exact dreapta. Aceasta ar trebui null. Să facem din nou. Compila. OK. Să introduce trei. Inserția a fost de succes. Hai să-l imprimați. Oh, dacă am putea verifica. Dar nu am făcut Funcția de imprimare încă. Hai să intrăm altceva. Ce ar trebui să intrăm? 

Audiența: Seven. 

JASON Hirschhorn: Seven? 

Publicul: Da. 

JASON Hirschhorn: Avem un defect segment. Așa că am luat unul, dar am în mod clar nu se poate obține două. Este 05:07. Deci, am putea depana această timp de trei minute. Dar am de gând să ne lase aici și trece la hash mese. Dar, din nou, răspunsurile pentru acest cod Voi e-mail pentru a vă într-un pic. Suntem foarte aproape de ea. Am foarte vă încurajez să dau seama ceea ce se întâmplă aici și fixați-l. Așa că vom trimite acest cod ca bine plus soluția - Probabil soluția mai târziu. În primul rând acest cod. 

Celălalt lucru pe care vreau să fac înainte de a ne finisaj este de nu ne-am eliberat nimic. Deci, vreau să-ți arăt ce Valgrind arata ca. Dacă vom rula limite Valgrind în programul nostru,. / legate. Din nou, în conformitate cu acest diapozitiv, ne ar trebui să ruleze Valgrind cu un anumit tip de opțiune, în acest caz, - Scurgeri de check-= complet. Deci, haideți să scrie Valgrind - Scurgeri de check-= complet. Deci, aceasta va rula Valgrind în programul nostru. Iar acum programul rulează de fapt. Așa că am de gând să-l rulați la fel ca înainte, a pus ceva inch Am de gând să pună în trei. Care funcționează. Eu nu am de gând să încerce să pună în ceva altfel pentru că am de gând să a obține o falsă segment în acest caz. Așa că eu sunt doar de gând să renunțe. 

Și acum tu vezi aici scurgeri și rezumat grămadă. Acestea sunt lucrurile bune pe care pe care doriți să verificați. Deci, rezumatul heap - se spune, în uz la ieșire - opt bytes într-un singur bloc. Că un bloc este nod am malloced. Michael, ai spus mai devreme un nod este de opt muscaturi deoarece are un număr întreg și indicatorul. Deci, asta e nod nostru. Și apoi se spune am folosit malloc de șapte ori și ne-am eliberat ceva de șase ori. Dar niciodată nu am numit liber, așa că nu am nici o idee ce acest lucru este vorba. 

Dar este suficient să spunem că, atunci când vă ruleaza programe, malloc se numește în alte locuri pe care le nu trebuie să vă faceți griji. Deci, malloc a fost, probabil, numit în unele locuri. Nu avem nevoie să vă faceți griji în cazul în care. Dar acest lucru este într-adevăr ne. Această primă linie este noi. Am plecat din acel bloc. Și puteți vedea că aici în rezumatul scurgere. Mai accesibil - opt bytes într-un singur bloc. Asta înseamnă că de memorie - ne-au scurs ca memorie. Cu siguranta pierdut - ceva este pierdut pentru totdeauna. În general, nu se va vezi ceva acolo. Totuși, în general, în cazul în care este accesibil veți vedea lucrurile, în cazul în care veți dori să se uite pentru a vedea ce cod ar trebui să s-au eliberat, dar ai uitat să elibereze. 

Și apoi, dacă acest lucru nu a fost cazul, dacă am făcut totul gratuit, putem verifica asta. Să rula programul nu pune în nimic. Veți vedea aici în uz, la ieșire - de zero la zero bytes în blocuri. Asta înseamnă că am avut mai rămas nimic atunci când acest program ieșit. Deci, înainte de a porni în pset6, rula Valgrind și asigurați-vă că nu aveți orice scurgeri de memorie în programul dumneavoastră. Dacă aveți orice întrebări cu Valgrind, nu ezitați să ajungă. Dar acest lucru este modul în care îl utilizați. Foarte simplu - a se vedea dacă au în uz la ieșire - orice bytes în orice blocuri. 

Așa că am fost de lucru pe insert nod. Am avut alte două funcții aici - imprima noduri și nodurile libere. Din nou, acestea sunt functii care sunt va fi bine pentru tine de a practica , deoarece acestea vă vor ajuta nu numai cu aceste exerciții eșantion, dar, de asemenea, pe problema setat. Ei harta pe destul de strâns de lucruri ai de gând să aibă de a face în problemă set. Dar vreau să vă asigurați ne atinge pe toate. Și tabele de dispersie sunt, de asemenea, cruciale pentru ceea ce facem în această secțiune săptămână - sau în setul problemă. 

Așa că am de gând să termin secțiunea vorbesc despre tabele de dispersie. Dacă observați am făcut o tabel hash mic. Asta nu este ceea ce vorbim despre, cu toate acestea. Vorbim despre un alt tip de tabele de dispersie. Și la bază, un tabel de hash nu este nimic mai mult decât o matrice plus o funcție hash. Vom vorbi de un pic doar pentru a asigurați-vă că toată lumea înțelege ceea ce o Funcția hash este. Și vă spun acum că este nimic mai mult decât de două lucruri - o matrice și o funcție hash. Și aici sunt pașii prin care aceasta funcționează. 

Există gama noastră. Nu este funcția noastră. În special, funcțiile hash trebuie să face o serie de lucruri cu aceasta. Am de gând să vorbesc în mod special despre această problemă set. Este, probabil, va ia într-un șir. Și ce-o să se întoarcă? Ce tip de date? Alden? Funcția hash-ul se întoarcă? Un întreg. Deci, aceasta este ceea ce hash tabel este format din - o masă sub formă de matrice și o funcție hash. Cum funcționează? Acesta funcționează în trei etape. Ne da o cheie. În acest caz, vom da un șir. Noi numim funcția de distribuire pe un singur pas la cheie și vom obține o valoare. 

În mod specific, vom spune vom obține un număr întreg. Că întreg, nu sunt foarte specifice limite la ceea ce poate fi că întreg. În acest exemplu, gama noastră este de dimensiune trei. Deci, ce numere pot fi faptul că întreg. Care este intervalul de valori valide pentru ca întreg, tipul de returnare a acestei Funcția hash? Zero, unu și doi. Punctul de funcția de distribuire este de a dau seama de locul în matrice în cazul în care cheia noastră se întâmplă. Există doar trei posibile locuri de aici - zero, unu, sau doi. Deci, această funcție mai bine de retur zero, unu, sau doi. Unele indice valabil în această matrice. 

Și apoi, în funcție de cazul în care se întoarce, puteți vedea acolo matrice deschis încadreze valoarea. Acolo am pus cheia. Deci, ne-am arunca în dovleac, ieșim la zero. La suport matrice 0, am pus dovleac. Ne arunca la pisici, avem unul. Am pus pisica la unul. Am pus în păianjen. Ieșim doi. Am pus păianjen la matrice suport doi. Ar fi atât de frumos în cazul în care a lucrat ca asta. Dar, din păcate, așa cum vom vedea, E un pic mai complicat. 

Înainte de a ajunge acolo, întrebări despre acest lucru de bază set-up a unui tabel hash? Aceasta este o imagine de exact ceea ce ne-am desenat pe tablă. Dar din moment ce l-am desenat pe tablă, am Nu am de gând să meargă în ea mai departe. În esență, chei, magie cutia neagră - sau, în acest caz, cutie teal - de o Funcția hash le pune în găleți. Și în acest exemplu suntem nu pune numele. Punem la telefon asociat numărul de nume în găleată. Dar ai putea foarte bine doar a pus numele în găleată. 

Aceasta este doar o imagine a ceea ce ne-am desenat pe tablă. Avem potențiale capcane, totuși. Și acolo sunt două, în special slide-uri pe care vreau să merg peste. Primul este de aproximativ o funcție hash. Așa că am pus întrebarea, ce face o funcție hash bun? Eu dau două răspunsuri. Primul este că este determinist. In contextul funcții hash, Ce înseamnă acest lucru? Da? 

Audiența: Se poate găsi index în timp constant? 

JASON Hirschhorn: A nu este ceea ce înseamnă. Dar asta este o presupunere bun. Mai are cineva o presupunere la ce înseamnă acest lucru? Ca o funcție hash bună este determinist? Annie? 

Audienta: Asta o cheie poate fi mapate numai la un loc în tabelul hash. 

JASON Hirschhorn: Asta-i exact dreapta. De fiecare dată când pune în dovleac, returnează întotdeauna zero. Dacă ați pus în dovleac și hash-ul Funcția returnează zero, dar are un probabilitate de a se întoarce ceva altceva mai mare decât zero - asa ca poate se poate returna unul, uneori, sau alte două ori - care nu este o funcție hash bună. Ai dreptate. Funcția hash-ul ar trebui să returneze același întreg exact, în acest caz, pentru același șir exact. 

Poate se întoarce în același întreg exact pentru același șir exact indiferent de capitalizare. Dar în acest caz este încă deterministic pentru că multe lucruri sunt mapate pe aceeași valoare. Asta e bine. Atâta timp cât există o singură ieșire pentru o anumită intrare. 

OK. Al doilea lucru este că întoarce indicii valide. Ne-am adus mai devreme. Această funcție hash - oh boy - o funcție hash ar trebui reveni indicii valide. Deci, spune - să ne întoarcem la acest exemplu. Funcția hash mea contează în sus literele din cuvântul. Asta e funcția de distribuire. Și se întoarce ca întreg. Deci, dacă am cuvinte A, este O să se întoarcă unul. Și se va pune un drept aici. Ce se întâmplă dacă am pus în liliacul cuvânt? O să se întoarcă trei. În cazul în care se merge bat? 

Nu se potrivește. Dar ea trebuie să meargă undeva. Aceasta este masa mea hash la urma urmei, și tot ceea ce trebuie să meargă undeva. Deci, în cazul în care ar trebui să bat meargă? Orice gândurile? Ghicește? Presupuneri bune? 

Audiența: Zero. 

JASON Hirschhorn: De ce la zero? 

Audiența: Pentru trei modulo trei este zero? 

JASON Hirschhorn: Trei modulo trei este zero. Aceasta este o mare presupunere, și asta e corect. Deci, în acest caz, ar trebui probabil, du-te la zero. Deci, o modalitate buna de a se asigura că acest hash Funcția returnează numai indicii valide este să-l modulo de mărimea mesei. Dacă aveți orice modulo acest întoarce de trei, esti mereu de gând pentru a obține ceva între zero, unu, doi. Și dacă acest lucru se întoarce mereu șapte, și întotdeauna modulo de trei, tu ești întotdeauna merge pentru a obține același lucru. 

Deci e încă deterministe dacă modulo. Dar asta se va asigura că nu obține ceva - o industrie invalid. În general, că modulo trebui să se întâmple în funcția hash. Deci, nu aveți nevoie să vă faceți griji despre acest lucru. Trebuie doar poate asigura că aceasta este o indice valid. Orice întrebări cu privire la acest potențial capcană? 

OK. Și acolo mergem. Următor potențial capcană, și acesta este unul mare. Ce se întâmplă dacă două chei hartă la aceeași valoare? Deci, există două moduri de a rezolva aceasta. Primul se numește liniar sondare, care sunt nu va trece peste. Dar ar trebui să fie familiarizați cu modul în care care funcționează și ceea ce este. 

Cea de a doua am de gând să merg peste pentru că este cel care mulți oameni, probabil, se va termina decide pentru a utiliza în setul lor probleme. Desigur, tu nu trebuie sa. Dar pentru setul de probleme, multe persoane au tendința de a alege pentru a crea un tabel hash cu înlănțuirea separată a pune în aplicare dicționar lor. Așa că am de gând să merg peste ceea ce înseamnă pentru a crea un tabel hash cu înlănțuirea separată. 

Așa că am pus în dovleac. Returnează zero. Și am pus dovleac aici. Apoi m-am pus in - ceea ce este un alt lucru Halloween-tematice? 

Audiența: Candy. 

JASON Hirschhorn: Candy! Acesta este un mare unul. Am pus în bomboane, și bomboane De asemenea, îmi dă zero. Ce să fac? Orice idei? Pentru că tot felul de know- ceea ce înlănțuirea separată este. Deci, orice idei ce să fac? Da. 

Audiența: Punerea șirul de fapt, în tabelul de hașiș. 

JASON Hirschhorn: Deci vom atrage ideea de bine aici. OK. 

Audiența: Au Hashtable [Inaudibil] indicatorul care indică începutul unei liste. Și apoi au dovleac fi prima valoare în această listă legat și bomboane fie a doua valoare în această listă legat. 

JASON Hirschhorn: OK. Marcus, care a fost remarcabil. Am de gând să rupă acea jos. Marcus este de a spune nu suprascrie dovleac. Asta ar fi rău. Nu pune bomboane în altă parte. Vom le-a pus atât la zero. Dar am de gând să se ocupe de sa le puna la zero, prin crearea unei liste de la zero. Și vom crea o listă de tot ceea ce mapate la zero. Și cel mai bun mod am învățat pentru a crea o listă care poate crește și micșora dinamic nu este în un alt tablou. Deci, nu o matrice multi-dimensionale. Dar pentru a crea o listă de legat. 

Deci, ceea ce a propus - Mă duc pentru a obține un nou - este de a crea un tablou cu indicatori, o serie de indicii. OK. Orice idee sau sugestie ce tipul din acest indicii ar trebui să fie? Marcus? 

Audiența: indicii pentru a - 

JASON Hirschhorn: Pentru că a declarat o listă legată, așa - 

Audiența: indicii nod? 

JASON Hirschhorn: indicii nod. Dacă lucrurile din legate noastră listă sunt noduri, atunci ele ar trebui să fie indicii de noduri. Și ce fac ei egala inițial? 

Audiența: Null. 

JASON Hirschhorn: Null. Deci, nu e treaba noastră gol. Se întoarce de dovleac la zero. Ce facem? Plimbare mine prin ea? De fapt, Marcus mi-a dat deja. Altcineva mi-plimbare prin ea. Ce facem atunci când ne - acest lucru arata foarte similar cu ceea ce ne-am face doar. Avi. 

Audiența: am de gând să ia o presupunere. Deci, atunci când vei ajunge bomboane. 

JASON Hirschhorn: Da. Ei bine, avem dovleac. Să trecem primul unul. Avem dovleac. 

Audiența: OK. Se întoarce de dovleac la zero. Deci, l-ai pus în asta. Sau de fapt, l-ai pus în lista de legătura. 

JASON Hirschhorn: Cum ne pune-l în lista de legat? 

Audiența: Oh, sintaxa real? 

JASON Hirschhorn: Doar de mers pe jos - spun mai mult. Ce facem? 

Audiența: Tocmai ai introduce ca primul nod. 

JASON Hirschhorn: OK. Deci avem nodul nostru, dovleac. Și acum cum l-am introduce? 

Audiența: Ai atribui se la indicatorul. 

JASON Hirschhorn: Care pointer? 

Audiența: indicatorul la zero. 

JASON Hirschhorn: Deci, în cazul în care face acest punct? 

Audiența: Pentru null chiar acum. 

JASON Hirschhorn: Ei bine, se indică la null. Dar eu pun în dovleac. Deci, în cazul în care ar trebui să arate? 

Audiența: Pentru a dovleac. 

JASON Hirschhorn: Pentru a dovleac. Exact. Deci, acest lucru indică dovleac. Și în cazul în care face acest lucru pointer la punctul de dovleac? La 

Audiența: Null. 

JASON Hirschhorn: la NULL. Exact. Deci, ne-am introdus ceva în lista de legătura. Tocmai am scris acest cod pentru a face acest lucru. Aproape aproape am ajuns complet spart. Acum vom introduce bomboane. Bomboane nostru, de asemenea, duce la zero. Deci, ce facem cu bomboane? 

Audiența: Depinde dacă sau nu încercăm să-l rezolve. 

JASON Hirschhorn: Asta-i exact dreapta. Depinde dacă sau nu noi încercăm să-l rezolve. Să presupunem că nu suntem de gând să-l rezolve. 

Audiența: Ei bine, atunci, așa cum am discutat înainte, este mai simplă doar să-l puneți chiar de la început, astfel încât indicatorul de la zero puncte la bomboane. 

JASON Hirschhorn: OK. Stai. Permiteți-mi crea bomboane chiar aici. Deci, acest indicator - 

Publicul: Da, ar trebui acum să fie îndreptată la bomboane. Apoi, au indicatorul de Punct de bomboane de dovleac. 

JASON Hirschhorn: Cum ar fi asta? Și spun că un alt lucru pentru a mapa la zero? 

Audiența: Ei bine, tu doar face acelasi lucru? 

JASON Hirschhorn: Faceți același lucru. Deci, în acest caz, dacă nu o facem Vreau să-l păstrați-l sortate Pare destul de simplu. Ne ia indicatorul în indicelui care dat de funcția noastră hash. Avem ca punct de noul nostru nod. Și apoi tot ce a fost îndreptat a anterior - în acest caz nul, în caz al doilea dovleac - că, oricare ar fi acesta este îndreptat la în prealabil, se adaugă în următoarea a noul nostru nod. Suntem introducerea ceva la început. De fapt, aceasta este mult mai simplu decât încearcă să mențină lista sortată. Dar, din nou, căutarea va fi mai complicat pe aici. Vom avea mereu pentru a merge până la capăt. 

OK. Orice întrebări cu privire la înlănțuirea separată? Cum funcționează? Vă rugăm să cereți-le acum. Eu chiar vreau să vă asigurați că toate înțelege acest lucru înainte de capul afară. 

Audiența: De ce ai pus de dovleac și bomboane în același o parte din tabelul hash? 

JASON Hirschhorn: Bună întrebare. De ce nu le-am pus în aceeași o parte din tabelul hash? Ei bine, în acest caz, funcția noastră hash revine la zero pentru ambele dintre ele. Așa că au nevoie pentru a merge la indice zero, pentru că în cazul în care vom uita-te pentru ei, dacă ne-am vreodată doriți să le căutați. Din nou, cu o abordare liniar de sondare nu le-ar pune atât la zero. Dar în abordarea separată lanț, am de gând să le pună, atât la zero și apoi a crea o listă de pe zero. 

Și nu vrem să suprascrie dovleac pur și simplu pentru că pentru că atunci vom presupune că a fost dovleac niciodată introdus. Dacă vom păstra doar un singur lucru în locație care ar fi rău. Atunci nu ar fi nici o Șanse de noi vreodată - dacă am avut vreodată un duplicat, apoi ne-am ar șterge doar valoarea noastră inițială. Deci, de ce facem această abordare. Sau de aceea am ales - dar, din nou, ne-am a ales abordarea separată înlănțuirea, care există multe alte abordări s-ar putea alege. Asta răspunde la întrebarea dvs.? 

OK. Carlos. Linear de sondare ar implica - în cazul în care am găsit-o coliziune la zero, ne-am ar arăta în locul următor pentru a vedea dacă a fost deschis și a pus-o acolo. Și apoi ne-am uita la sport următor și a se vedea dacă a fost deschisă și a pus-o acolo. Așa că am găsi următorul disponibile loc deschis și a pus-o acolo. Orice alte întrebări? Da, Avi. 

Audiența: Ca o continuare la faptul că, ce vrei sa spui de la fața locului viitor? În tabelul hash sau într-o listă înlănțuită. 

JASON Hirschhorn: Pentru liniar programare, liste legate. Următorul loc pe tabelul hash. 

Audiența: OK. Deci, tabelul hash ar fi inițializat la dimensiunea - cum ar fi numărul de șiruri că ai fost introducerea? 

JASON Hirschhorn: Ai vrea vrei sa fie foarte mare. Da. Aici este o imagine a ceea ce ne-am doar a atras de pe bord. Din nou, avem o coliziune aici. la 152. Și veți vedea am creat o listă legat de pe ea. Din nou, tabelul hash înlănțuirea separată abordarea nu este cea pe care o trebuie să ia pentru problemele de set șase dar este una care o mulțime de elevii au tendința de a lua. Deci, pe această notă, să ne vorbim pe scurt înainte de a ne capul afară de problema șase, și apoi voi împărtăși o poveste cu tine. Avem trei minute. 

Problema stabilit șase. Ai patru funcții - încărcare, verificați, dimensiune, și descărcare. Încărcare - bine, am fost de gând peste sarcină tocmai acum. Am atras sarcina pe bord. Și chiar am început de codificare o mulțime de introducerea într-o listă legat. Deci, sarcina nu este cu mult mai mult decât ceea ce ne-am face doar. 

Verificare este dată ai ceva încărcat. Este același proces ca aceasta. Aceleași primele două părți în cazul în care arunca ceva în funcția de distribuire și să obțină valoarea sa. Dar acum nu-l introduce. Acum suntem în căutarea pentru el. Am mostre de cod scris pentru găsirea ceva într-o listă legat. Am să vă încurajez pentru a practica acest lucru. Dar găsirea intuitiv ceva este destul de similar cu introducerea ceva. Într-adevăr, am desenat o imagine a găsi ceva într-o listă legată, în mișcare prin intermediul până când a ajuns la sfârșitul anului. Și dacă ai până la capăt și nu a putut se pare, atunci ea nu e acolo. Deci, asta e cec, în esență. 

Următorul este dimensiunea. Să trecem peste dimensiune. În cele din urmă ați descărca. Descarcare este unul care nu au atras pe bord sau codificate încă. Dar am să vă încurajez să încercați să-l codificare în eșantionul nostru legat Lista exemplu. Dar descărca intuitiv este similar cu gratuit - sau vreau să spun este similară pentru a verifica. Cu excepția acum de fiecare dată când te duci prin, tu nu esti pur si simplu de verificare a a se vedea dacă aveți o valoare acolo. Dar sunteți luați ca nod și eliberându-se, în esență. Asta e ceea ce descărcare îți cere să faci. Tot gratuit ai malloced. Deci, te duci prin toata lista din nou, merge prin toată hash masă din nou. De data aceasta nu se verifica pentru a vedea ce este acolo. Doar elibera ceea ce-i acolo. 

Și, în sfârșit dimensiune. Dimensiune ar trebui să fie puse în aplicare. Dacă nu pune în aplicare dimensiune - Eu voi spune ca aceasta. Dacă nu pune în aplicare dimensiune în exact o linie de cod, inclusiv reveni declarație, sunteți face dimensiunea incorect. Deci, asigurați-vă că dimensiunea, de proiectare complet puncte, o faci în exact o linie de cod, inclusiv declarația de returnare. 

Și nu bagajele încă, Akchar. Castor Eager. Am vrut să-ți mulțumesc baieti pentru a veni la secțiune. Au un Halloween fericit. Acesta este costumul meu. Voi purta acest joi dacă te văd la ore de birou. Și dacă ești curios despre ceva mai mult fundal ca la acest costum, se simt liber pentru a verifica 2011 Secțiunea pentru o poveste despre de ce sunt purtând costumul dovleac. Și aceasta este o poveste tristă. Deci, asigurați-vă că aveți unele tesuturile din jur. Dar pe care, dacă aveți orice întrebări voi lipi în jurul în afara după secțiune. Mult noroc pe probleme stabilit șase. Și, ca întotdeauna, în cazul în care aveți orice întrebări, să-mi spuneți.