[MUSIC JOC]
David J. MALAN: Bine.
Acest lucru este CS50.
Aceasta este saptamana cinci au continuat, iar noi vești bune și vești proaste.
Deci, o veste bună este că CS50 lanseaza vineri.
Dacă doriți să ni se alăture, cap de la URL-ul obișnuit aici.
Chiar mai bine de știri, nu prelegere aceasta vine luni al 13-lea.
Ceva mai bine de știri, Quiz zero este miercurea viitoare.
Mai multe detalii pot fi găsite la această adresă URL aici.
Și în următoarele două zile vom umple golurile
în ceea ce privește camerele că vom avea rezervate.
Mai bine de știri este că nu va mai fi o revizuire curs larg
sesiune de acest vin Luni seara.
Stay tuned pentru a cursului site-ul de localizare și detalii.
Secțiunile, chiar dacă acesta este un vacanță, se va întâlni, de asemenea, de asemenea.
Cel mai bun de știri, prelegeri vinerea viitoare.
Deci, aceasta este o tradiție noi au, conform programei analitice.
Doar-- că va fi uimitor.
Veți vedea lucruri, cum ar fi structuri de date de timp constant
și tabele de dispersie și copaci și încearcă.
Și vom vorbi despre problemele de ziua de naștere.
O grămadă de chestii așteaptă vinerea viitoare.
OK.
Oricum.
>> Deci amintesc că am fost concentrându-se pe această imagine a ceea ce este
în interiorul memoriei calculatorului nostru.
Deci, memorie RAM sau este în cazul în care programele de Există în timp ce le execută.
Dacă faceți dublu-clic pe un pictogramă pentru a rula unele programe
sau dublu-clic pe un pictogramă pentru a deschide un fisier,
e încărcat de pe hard-ul conduce vehicule sau de pe unitatea SSD
în memoria RAM, Random Access Memory, în cazul în care trăiește până ce alimentarea înceteazã,
capacul laptop se închide, sau te-ai lasat programul.
>> Acum, că memoria, de care, probabil, va trebui
1 Gigabyte aceste zile, 2 gigabytes, sau chiar mult mai mult,
este, în general, prevăzute pentru un anumit program
în acest fel de formă dreptunghiulară model conceptual
prin care avem stiva în partea de jos și o grămadă de alte chestii în partea de sus.
Lucru la foarte de sus am vazut pe această imagine
înainte, dar niciodată nu a vorbit despre este așa-numitul segment de text.
Segment text este doar un mod fantezist de a spune zerouri și cele care
compune programul compilat real.
>> Deci, atunci când dublu-clic Microsoft Word pe Mac sau PC-ul dvs.,
sau atunci când rulați punct slash Mario pe o Calculator Linux la fereastra ta terminale,
zerouri și cele care compun Word sau Mario sunt depozitate temporar
în memoria RAM a computerului în așa-numitul segment de text pentru un anumit program.
Mai jos, care merge inițializat și date neinițializate.
Acest lucru este chestii de genul variabile globale, că noi nu am folosit multe din,
dar uneori ne-am a avut variabile globale
sau static siruri de caractere definit ca este greu codificate cuvinte ca "Bună ziua"
care nu sunt luate de la utilizator care sunt greu codificate în programul tău.
>> Acum, in partea de jos ne au așa-numitele stivă.
Și stiva, până acum, am fost folosind pentru ce tipuri de scopuri?
Ce stiva fost folosit pentru?
Da?
>> Audiența: Funcții.
>> David J. MALAN: Pentru funcții?
În ce sens pentru funcții?
>> Audiența: Când apelați o funcție, Argumentele sunt copiate pe stiva.
>> David J. MALAN: Exact.
Când apelați o funcție, sa Argumentele sunt copiate pe stiva.
Deci, orice X sau Y sau lui A sau B de că sunteți trecerea într-o funcție
sunt puse temporar pe așa-numita stiva,
la fel ca unul din Annenberg tăvi sală de masă, și, de asemenea lucruri
ca variabile locale.
În cazul în care funcția foo sau de swap-ul Funcția avea variabile locale,
cum ar fi temperatura, cei doi ajung pe stiva.
Acum, nu vom vorbi prea mult despre ei, dar aceste variabile de mediu
în partea de jos am văzut în urmă cu ceva timp, atunci când Am fost jucându la tastatură o zi
și am început accesarea lucruri ca argv 100 sau argv 1000,
doar elements-- am uitat Numere de, dar că
nu ar fi trebuit să fie accesate de către mine.
Am început să văd unele simboluri ciudate pe ecran.
Acestea au fost așa-numitele variabilele de mediu
ca setări globale pentru meu program sau pentru calculatorul meu, nu
nu au legătură cu recenta bug care am discutat,
Shellshock, care a fost care afectează destul de câteva calculatoare.
>> Acum în cele din urmă, în centrul atenției astăzi vom fi în cele din urmă pe heap.
Acesta este un alt segment de memorie.
Și fundamental toate acestea memorie este aceleasi lucruri.
Este același hardware.
Suntem un fel de tratarea grupuri diferite
de bytes pentru diferite scopuri.
Heap este, de asemenea, va fi în cazul în care variabile și memorie pe care le solicita
din sistemul de operare sunt stocate temporar.
>> Dar există un fel de problemă aici, ca imagine implică.
Avem un fel de avea două navele despre a ciocni.
Pentru că așa cum vă folosiți mai mult și mai mult a stivei, și după cum vom vedea astăzi
mai departe, pe măsură ce utilizați mai mult și mai mult din morman, cu siguranță lucruri rele s-ar putea întâmpla.
Și într-adevăr, putem induce că în mod intenționat sau neintenționat.
Deci Cliffhanger trecut timp a fost acest program,
care nu au servit nici o funcțională alt scop decât de a demonstra
cum ca un om rău poate lua de fapt, avantaj de bug-uri în programul cuiva
și preia un program sau chiar un sistem informatic integral sau server.
Deci, doar pentru a arunca o privire rapidă, tu observa ca principal în partea de jos
ia în linie de comandă argumente, ca pe argv.
Și are un apel la o funcție f, în esență, o funcție fără nume numit
f, și se trece în argv [1].
>> Deci, indiferent de cuvânt a utilizatorului Tipuri de la prompt după numele acestui program,
și apoi această funcție arbitrară în sus top, f, are într-un șir, AKA char *,
cum am început să discutăm, și ea doar o numește "bar".
Dar am putea numi nimic.
Și atunci se declară, în interiorul f, o serie de personaje
numit C- de 12 astfel de caractere.
>> Acum, de povestea i-am spus acum un moment, în cazul în care în memorie
este c, sau sunt cele 12 caractere de gând să ajung?
Ca să fie clar.
Da?
>> Audiența: pe stiva.
>> David J. MALAN: pe stiva.
Deci c este o variabilă locală.
Cerem de 12 caractere sau 12 biti.
Cei care vor să ajungă pe așa-numita stiva.
Acum, în cele din urmă este această altă funcție care este de fapt destul de util,
dar noi nu am folosit într-adevăr ea ne, strncopy.
Aceasta înseamnă copie șir, dar doar pentru n scrisori, n caractere.
Deci, n caractere vor fi copiate de la bar în c.
Și cât de mulți?
Lungimea bar.
Deci, cu alte cuvinte, că o linie, strncopy,
se va copia bar eficient în a c.
>> Acum, doar la fel de anticipa Morala acestei povești,
ceea ce este potențial problematic aici?
Chiar dacă suntem de verificare lungimea de bar și se trece în strncopy,
ceea ce este instinctul spune ce este încă rupt despre acest program?
Da?
>> Audiența: Nu include cameră pentru caracterul nul.
David J. MALAN: Nu include cameră pentru caracterul nul.
Potențial, spre deosebire de practicile din trecut nu ne face chiar
au atât de mult ca un plus de 1 la găzdui acest caracter nul.
Dar e chiar mai rău decât atât.
Ce altceva putem faptul că nu a făcut?
Da?
>> Audiența: [inaudibil]
David J. MALAN: Perfect.
Am codat greu de 12 destul de arbitrar.
Asta nu este atât de mult problemă, dar faptul
că nu suntem chiar a verifica dacă lungimea de bare este mai mică de 12,
caz în care va fi în condiții de siguranță să-l pună în memoria
numit C pe care le-am alocat.
Într-adevăr, în cazul în bar este ca 20 de caractere,
această funcție pare să fie copierea 20 de personaje din bar în c, astfel
având cel puțin 8 bytes că aceasta nu ar trebui să fie.
Asta e implicația aici.
>> Deci, pe scurt programul, rupt.
Nu este o astfel de afacere mare.
Poate că veți obține o eroare de segmentare.
Am avut toate bug-uri în programe.
Noi toți ar putea avea bug-uri în programe chiar acum.
Dar ceea ce este implicația?
Ei bine, aici este o versiune mărită-in de poza din memoria computerului meu.
Aceasta este partea de jos a stivei meu.
Și, într-adevăr, în partea de jos este ceea ce-i numit stivă de rutină părinte, un fel de lux
de a spune că e principal.
Așa că oricine numit funcția f că vorbim despre.
Deci, aceasta este baza stivei.
Adresa de returnare este ceva nou.
A fost mereu acolo, fost întotdeauna în acea imagine.
Noi doar nu a atras atenția să-l.
Pentru că se pare că modul în care funcționează este c că, atunci când o funcție apelează o alta,
nu numai că argumentele pentru care Funcția împinși pe stiva,
nu numai local, funcția de variabile împinși pe stiva,
ceva numit o adresă de retur De asemenea, se pune pe stiva.
Mai precis, în cazul în care apelurile principale Foo, a principalelor adresa proprie în memorie, bou ceva,
în mod eficient este pus pe stiva astfel că atunci când se face f executarea ei
știe unde să sări înapoi la text segment în scopul de a continua executarea.
>> Deci, dacă noi suntem aici conceptual, în principal, atunci f este chemat.
Cum f știe cine la un control de mână înapoi?
Ei bine, acest mic pesmet în roșu aici,
numita adresa de revenire, doar verificări, ceea ce este că adresa de retur?
Oh, lasă-mă să sări înapoi la principal aici.
Si asta e un pic de o simplificare,
deoarece zerourile și cele pentru principal sunt punct de vedere tehnic
aici, în segmentul de tehnologie.
Dar asta e ideea. f doar trebuie să știe ce
la care controlul în cele din urmă se întoarce.
>> Dar modul în care calculatoarele s-au pus de mult lucruri
ca variabile locale și argumente este ca aceasta.
Deci, în partea de sus a acestei imagini în albastru este cadrul stiva pentru f, astfel încât toate
de memorie care f în mod special este utilizarea.
Deci prin urmare, observăm că bar este în această imagine.
Bar a fost argumentul său.
Și am susținut că argumentele pentru Funcțiile împinși pe stiva.
Și c, desigur, este De asemenea, în această imagine.
>> Și doar pentru scopuri de notație, observa în colțul din stânga sus
este ceea ce s-ar fi c suport 0 și apoi ușor în jos la dreapta
este c suport 11.
Deci, cu alte cuvinte, vă puteți imagina că există o grilă de bytes
acolo, prima dintre acestea fiind din stânga sus, de care partea de jos
este ultima din cele 12 bytes.
>> Dar acum, încercați pentru a derula înainte.
Ce se va întâmpla dacă vom trece într-un bar șir care este mai mult de c?
Și nu ne verifica dacă este într-adevăr mai mult de 12.
Care parte din această imagine este de gând să te schimbată de octeți 0, 1, 2, 3,
dot dot dot, 11, și apoi rău, 12, 13 și 19?
Ce se va întâmpla aici, dacă deduce din ordinea
care c este 0 suport pe partea de sus și c suport 11 este un fel de jos
spre dreapta?
Da?
>> Audiența: Ei bine, se întâmplă pentru a suprascrie char * bar.
>> David J. MALAN: Da, se pare ca ai de gând să suprascrie char * bar.
Și mai rău, dacă vă trimite într-un foarte lung șir, ceea ce s-ar putea suprascrie chiar?
Adresa de returnare.
Ceea ce, din nou, este la fel ca un pesmet pentru a spune programului în cazul în care
pentru a merge înapoi la când f se face fiind numit.
>> Deci, ce baietii rai de obicei, face este în cazul în care au venit peste un program de
că sunt curios dacă este de exploatat, buggy în așa fel
că el sau ea poate lua profitând de faptul că bug-ul,
în general, ei nu primesc acest drept pentru prima dată.
Ei doar începe să trimiteți, de exemplu, siruri de caractere aleatorii în programul tău,
dacă la tastatură, sau sincer ei, probabil,
scrie un mic program pentru doar genera în mod automat siruri de caractere,
și începe să trage cu privire la programul dumneavoastră de trimiterea în o mulțime de diferite intrări
la lungimi diferite.
>> De îndată ce se blochează de program, asta e un lucru uimitor.
Pentru că înseamnă că sau ea a descoperit
ceea ce este, probabil, într-adevăr, o problemă.
Și atunci ei pot obține mai inteligent și începe concentrându-se mai strict
cu privire la modul de a exploata bug.
În special, ceea ce el sau ea s-ar putea faceți este să trimiteți, în cel mai bun caz, salut.
Nu e mare lucru.
Este un șir care este suficient de scurt.
Dar dacă el sau ea trimite, și vom generaliza ca,
atac code-- așa zerouri și cele care fac lucruri
ca rm-rf, care elimina tot de pe hard disk sau trimite spam-uri
sau cumva ataca masina?
>> Deci, dacă fiecare dintre acestea literele A reprezintă doar,
conceptual, atac, atac, atac, atac, un cod rău
că altcineva a scris, dar în cazul în care persoana este suficient de inteligent
pentru a nu numai să includă toate acestor rm-RFS, dar, de asemenea
au ultimele sale câteva bytes fie un număr care corespunde
la adresa lui sau codul ei de atac propriu
că el sau ea a trecut în doar furnizându-i în linia de,
puteți păcăli în mod eficient computerul în observe când f se face executarea,
oh, e timpul pentru mine să sar înapoi la adresa de returnare roșu.
Dar pentru că el sau ea are într-un fel suprapus că adresa expeditorului
cu numărul lor, și acestea sunt destul de inteligent
pentru a fi configurat ca număr să se refere, în timp ce
a se vedea în partea de sus super- colțul din stânga-acolo,
adresa efectivă în anii calculator memoria unora dintre codul lor atac,
un tip rău pot păcăli computerul în executarea propriu cod lui sau a ei.
>> Și asta cod, din nou, poate fi orice.
Se numește în general Codul coajă, care este doar
un fel de a spune că nu este în general, ceva la fel de simplu ca rm-rf.
Este de fapt ceva de genul Bash, sau un program de real pe care-l dă
sau de control o programatic pentru a executa orice altceva care doresc să.
Deci, pe scurt, toate astea derivă din faptul simplu
că această problemă a implicat nu verifica limitele de matrice dumneavoastră.
Și pentru că modul în care computere lucru este că ei
folosesc stiva de în mod eficient, conceptual,
de jos in sus, dar apoi elementele ai împinge pe stiva crește de sus în jos,
acest lucru este incredibil de problematic.
Acum, există modalități de a lucra în jurul acest lucru.
Și sincer, sunt limbi cu care să lucreze în jurul acestui.
Java este imun, de exemplu, la această problemă.
Pentru că ei nu vă dau indicii.
Ei nu-ți dau adrese de memorie directe.
Deci, cu această putere pe care o avem pentru a atinge nimic din memorie
Vrem vine, desigur, de mare risc.
>> Deci, ține un ochi.
În cazul în care, sincer, în lunile sau anii care vor veni, oricand
ai citit despre unele exploatare de un program sau un server,
dacă ați văzut vreodată un indiciu de ceva ca un atac buffer overflow,
sau stivă overflow este un alt tip de atac, similară în spirit,
mult ca inspiră site-ului nume, dacă îl cunoașteți,
totul vorbește despre doar revărsare mărimea unele caractere
matrice sau matrice unele mai mult, în general.
Orice întrebări, atunci, pe aceasta?
Nu incercati asta acasa.
>> În regulă.
Deci, malloc până acum a fost noul nostru prieten în care să putem aloca memorie
că nu știm în mod necesar în avansa pe care ne-o dorim, asa ca nu avem
codul greu în nostru Numerele de programe, cum ar fi 12.
Odată ce utilizatorul ne spune cât de mult Date el sau ea vrea să de intrare,
putem malloc că multă memorie.
>> Deci, malloc se pare, la măsură am fost folosind-o,
explicit ultimul timp, și apoi voi au fost folosind-o
pentru getString în necunoștință de câteva săptămâni, toate de memorie malloc lui
vine de la așa-numita grămadă.
Și acesta este motivul pentru getstring, de exemplu, poate aloca memorie dinamic
fără a ști de ce ești O să tastați în avans,
te dai înapoi un pointer la care memoria, și că memoria este încă a ta de a păstra,
chiar și după getString întoarce.
Deoarece amintesc după toate că stiva este în mod constant merge în sus și în jos,
în sus și în jos.
Și, de îndată ce merge jos, înseamnă că orice memorie
această funcție ar trebui folosit nu fi folosit de oricine altcineva.
Este valori de gunoi acum.
>> Dar heap este de până aici.
Și ce e frumos despre malloc este că când malloc alocă memorie de până aici,
nu este afectat, pentru cea mai mare parte, prin stivă.
Și astfel orice funcție poate accesa memorie care a fost malloc'd,
chiar printr-o funcție ca getstring, chiar și după ce acesta este returnat.
>> Acum, reciproca de malloc este gratuit.
Și într-adevăr, regula va nevoie pentru a începe de adoptare a
este orice, orice, orice dată când utilizați malloc trebuie să te folosească gratuit, în cele din urmă,
pe care același indicator.
În tot acest timp am fost scris buggy, cod buggy, pentru mai multe motive.
Dar dintre care unul a fost folosind biblioteca CS50, care
în sine este în mod deliberat buggy, ea pierderi de memorie.
De fiecare dată când am sunat getstring în ultimele câteva săptămâni
cerem de operare sistem, Linux, pentru memorie.
Și tu nu au mai dat o dată înapoi.
Și acest lucru nu este, în practica, un lucru bun.
>> Și Valgrind, unul dintre instrumente introduse în PSET 4,
este totul despre ajutându-vă acum găsi bug-uri de genul asta.
Dar, din fericire pentru PSET 4 nu ai nevoie de să utilizeze biblioteca CS50 sau getString.
Deci, orice bug-uri legate de memorie sunt în cele din urmă va fi a ta.
>> Deci, malloc este mai mult decât convenabil pentru acest scop.
Putem de fapt, acum rezolva fundamental diferite probleme,
și de a rezolva în mod fundamental mai multe probleme eficient ca pe promisiunea săptămână la zero lui.
Până în prezent aceasta este cea mai sexy structură de date care le-am avut.
Și de structură de date doar vreau sa spun o cale de memorie conceptualiza
într-un mod care merge dincolo de doar spun, aceasta este o int, acesta este un char.
Putem începe la lucruri de grup împreună.
>> Deci, o serie arata ca aceasta.
Și ceea ce a fost esențial în aproximativ o matrice este că vă oferă
back-to-back bucăți de memorie, fiecare dintre acestea
va fi de același tip, int, int, int, int, sau char, char, char,
char.
Dar există câteva dezavantaje.
Aceasta, de exemplu, este o serie de dimensiuni șase.
Să presupunem că vă umple acest tablou cu șase numere și apoi, din diverse motive,
dvs. de utilizator vrea să dea te un număr al șaptelea.
Unde l-ai pus?
>> Care este soluția în cazul în care aveți a creat o matrice pe stiva,
de exemplu, doar cu săptămâna două notație că am introdus,
de paranteze pătrate, cu un număr de interior?
Ei bine, ai șase numere în aceste cutii.
Ce-ar fi instinctele tale?
În cazul în care ai vrea să-l puneți?
>> Audiența: [inaudibil]
>> David J. MALAN: Imi pare rau?
>> Audiența: Pune-l pe final.
>> David J. MALAN: Pune-l pe final.
Deci, doar pe la dreapta, in afara de aceasta cutie.
Care ar fi frumos, dar ea se dovedește că nu poți face asta.
Pentru că dacă tu nu ai cerut pentru acest segment de memorie,
ar putea fi de o coincidență faptul că această este utilizat de către o altă variabilă
cu totul.
Gandeste-te o săptămână sau asa ca atunci cand am pus în numele Zamyla și Davin și Gabe
în memorie.
Ei au fost literalmente spate în spate la spate.
Deci, nu putem neapărat încredere că tot ceea ce a
aici este disponibil pentru mine de a utiliza.
>> Deci, ce altceva ar putea face?
Ei bine, odată ce și dea seama au nevoie de o serie de dimensiuni șapte,
ai putea crea doar un matrice de dimensiune șapte apoi utilizați
pentru o buclă sau o buclă în timp ce, copiați-l în noua matrice,
și apoi într-un fel chiar a scăpa de această matrice sau doar nu o mai utilizați.
Dar asta nu e deosebit de eficient.
Pe scurt, tablouri nu lasa tu redimensiona dinamic.
>> Deci, pe de o parte te cu acces aleator, care este uimitor.
Pentru că ne permite să facem lucruri ca divide și cuceri,
binar de căutare, toate de care ne-am a vorbit despre pe ecran aici.
Dar vopsea te într-un colț.
De îndată ce te-a lovit la sfârșitul anului matrice dumneavoastră,
ce trebuie să faci un foarte operație costisitoare
sau scrie o grămadă de cod să se ocupe acum de această problemă.
>> Deci, ce se întâmplă dacă în loc am avut ceva numit-o listă,
sau o listă legată în special?
Ce dacă în loc de a avea dreptunghiuri spate în spate în spate,
avem dreptunghiuri care lasă un pic pic de loc de manevră între ele?
Și chiar dacă mi-am atras acest imagine sau adaptat această imagine
de la unul dintre textele aici pentru a reveni la spate în spate foarte ordonat, în realitate,
unul dintre aceste dreptunghiuri ar putea fi aici în memorie.
Una dintre ele ar putea fi de până aici.
Una dintre ele ar putea fi de până aici, aici, și așa mai departe.
>> Dar dacă ne-am desenat, în acest caz, săgeți
care se leagă într-un fel aceste dreptunghiuri împreună?
Într-adevăr, am văzut o tehnică încarnare a unei săgeți.
Ce am folosit în ultimii ani zile în care, sub capota,
este reprezentativ pentru o săgeată?
Un pointer, corect?
>> Și ce dacă, în loc de doar stochează numerele,
cum ar fi 9, 17, 22, 26, 34, ceea ce, dacă noi nu este stocat
doar un număr, ci un pointer lângă fiecare astfel de număr?
Așa că de mult ca tine ar firul o ac printr-o grămadă de material,
lucrurile într-un fel de legare împreună, în mod similar se poate
noi cu indicii, ar fi încarnat de săgeți aici,
fel de a tese împreună aceste dreptunghiuri individuale
prin utilizarea în mod eficient un pointer lângă fiecare număr care
indică un numar viitor, care subliniază, la rândul său, un numar viitor?
Cu alte cuvinte, ce dacă ne-am dorit de fapt
să pună în aplicare ceva de genul asta?
Ei bine, din păcate, aceste dreptunghiuri, cel puțin unul cu 9, 17, 22,
și așa mai departe, acestea nu mai sunt pătrate frumos cu numere unice.
De jos, dreptunghi 9 de mai jos, de exemplu,
reprezinta ceea ce ar trebui să să fie un pointer, 32 de biți.
Acum, eu nu sunt încă conștienți de orice tip de date în C, care vă oferă nu numai un int
dar un pointer cu totul.
>> Deci, care este solutia, dacă vrem pentru a inventa propria noastră răspuns la acest lucru?
Da?
>> Audiența: [inaudibil]
>> David J. MALAN: Ce-i asta?
>> Audiența: structura noua.
>> David J. MALAN: Da, așa că de ce nu ne-am crea o nouă structură,
sau într-C, o struct?
Am văzut structs înainte, dacă pentru scurt timp, în cazul în care ne-am ocupat cu o structură de student
ca aceasta, care a avut un nume și o casă.
În PSET 3 Breakout ați utilizat un întreg buchet de GRect structs-- și GOvals
că Stanford creat pentru a informații grup împreună.
Deci, dacă am lua această aceeași idee de cuvintele cheie "typedef" și "struct"
și apoi unele chestii-elev specific, și să evolueze în acest următoarele:
typedef struct node-- și nod este doar un informatică foarte generic
Termenul pentru ceva într-o structură de date, un recipient într-o structură de date.
Un nod eu pretind va avea un int n, total simplu,
și apoi un pic mai criptic, această a doua linie, nod struct * viitor.
Dar, în termeni tehnici mai puțin, ceea ce este că a doua linie
de cod în interiorul acolade?
Da?
>> Audiența: [inaudibil]
David J. MALAN: A pointer la un alt nod.
Deci, desigur, sintaxa un pic criptic.
Dar dacă l-ai citit literal, următor este numele unei variabile.
Care este tipul de date?
Este un pic verbose acest timp, dar e de nod struct tip *.
De fiecare dată când am văzut ceva stele, care înseamnă că este un pointer la acest tip de date.
Deci, data viitoare este aparent o pointer la un nod struct.
>> Acum, ceea ce este un nod struct?
Ei bine, observați ce vedeți pe cei aceleași cuvinte de la dreapta sus.
Și într-adevăr, veți vedea, de asemenea, cuvântul "Nod" aici, la stânga jos.
Și aceasta este de fapt doar o comoditate.
Observați că în definiția noastră de student acolo este cuvântul "elev" doar o singură dată.
Și asta pentru că un elev obiect nu a fost auto-referențială.
Nu e nimic în interiorul unui elev care trebuie să indice un alt student,
persay.
Asta ar fi un fel de ciudat în lumea reală.
>> Dar, cu un nod într-o legătură Lista, noi vrem un nod
să fie referențial pentru un obiect similar.
Și astfel observa schimbarea de aici nu este doar ceea ce este în interiorul acolade.
Dar vom adăuga cuvântul "nod" în partea de sus, precum și
adăugându-l la partea de jos în loc de "elev".
Și acesta este doar un detaliu tehnic astfel încât, din nou, structura de date
poate fi auto-referențială, astfel încât o nod poate indica un alt astfel de nod.
>> Deci, ce este aceasta în cele din urmă va însemna pentru noi?
Ei bine, unul, chestia asta interior este conținutul nod noastre.
Acest lucru aici, dreapta sus, este doar atât
că, din nou, ne putem referi la noi înșine.
Și atunci lucrurile exterior, chiar dacă nodul este un termen nou,
poate, este încă la fel ca elev și ce
a fost sub capota din SPL.
>> Deci, dacă am vrut acum să înceapă punerea în aplicare a acestei liste legate,
Cum am putea traduce ceva de genul asta de cod?
Ei bine, hai sa vedem un exemplu de program care
de fapt utilizează o listă de legat.
Printre cod de distribuție de astăzi este un program numită lista Zero.
Și dacă am alerga aceasta am creat un super- GUI simplu, Interfață grafică pentru utilizator,
dar este de fapt doar printf.
Și acum mi-am dat un meniu câteva options-- Delete, Insert, Căutare,
și Traverse.
Și ieși.
Acestea sunt operațiuni de doar comune cu privire la un structura de date cunoscut ca o listă de link.
>> Acum, Delete se va șterge un număr din lista.
Introduceți va adăuga un număr la lista.
Căutare este de gând să se uite pentru un număr în listă.
Și traverse este doar un mod fantezist de a spune, mers pe jos prin listă,
imprimare-l, dar asta este.
Nu-l schimba în niciun fel.
>> Așa că hai să încercăm.
Să mergem mai departe și de tip 2.
Și apoi am de gând să introduce numărul, spune 9.
Enter.
Și acum programul meu este doar programat să spun, lista este acum 9.
Acum, dacă am merge mai departe și introduceți din nou, să
mă duc mai departe și zoom out și de tip în 17.
Acum, lista mea este 9, atunci 17.
Dacă fac introduce din nou, să sărim unul.
În loc de 22, ca pe imaginea care le-am au uitat la aici, lasă-mă să sară înainte
și introduceți 26 următor.
Așa că am de gând să tastați 26.
Lista este ca ma astept.
Dar acum, doar pentru a vedea dacă acest cod va fi flexibil, lasă-mă acum
tip 22, care cel puțin conceptual, dacă suntem
menținându acest sortate, care este într-adevăr Va fi un alt obiectiv chiar acum,
ar trebui să meargă în între 17 și 26.
Așa că am lovit Enter.
Într-adevăr, care funcționează.
Iar acum lasă-mă să introduceți trecut, pe imaginea, 34.
>> În regulă.
Deci, de acum lasă-mă să stipuleze că Ștergeți și Traverse și Căutare fac,
în fapt, locul de muncă.
De fapt, dacă am fugi de căutare, să caută numărul 22, Enter.
Aceasta a constatat 22.
Deci, asta este ceea ce această Programul Lista Zero face.
>> Dar ceea ce se intampla de fapt pe care implementeaza aceasta?
Ei bine, în primul rând s-ar putea avea, și într-adevăr Eu am, un fișier numit list0.h.
Și undeva acolo este aceasta linie, typedef, nod struct,
atunci am bretele mele cret, int n, și atunci struct-- ce a fost definiția?
Nod Struct următor.
Deci, avem nevoie de steaua.
Acum punct de vedere tehnic de a intra în obiceiul de a atrage aici.
S-ar putea vedea manualele și referințe on-line se face acolo.
Este echivalent funcțional.
De fapt, acesta este un pic mai tipic.
Dar voi fi în concordanță cu ceea ce am făcut ultima dată și de a face acest lucru.
Și apoi în cele din urmă, am de gând să fac asta.
>> Deci, într-un fișier antet undeva, în list0.h
astăzi este această definiție struct, și poate alte chestii.
Între timp, în list0c există O să fie câteva lucruri.
Dar vom doar începe și nu termin asta.
List0.h este un fișier vreau să includă în dosarul meu C.
Și apoi, la un moment dat am Va trebui int, principal, anularea.
Și apoi am de gând să au unele probleme de rezolvat aici.
Am, de asemenea, de gând să aibă o prototip, cum ar fi gol, căutare, int,
n, al cărei scop în viață este pentru a căuta un element.
Și apoi aici am pretinde în Codul de astăzi, gol, căutare, int, n,
nu virgulă dar acolade deschise.
Și acum vreau să caute într-un fel pentru un element din această listă.
Dar noi nu avem suficient informații pe ecran încă.
Nu am de fapt, reprezentat lista sine.
Deci, într-un fel am putea pune în aplicare o listă legat într-un program
este am un fel de vrei să faci ceva ca să declare lista inlantuita aici.
Pentru simplitate, am de gând să facă acest globală, chiar dacă, în general, ne
nu ar trebui să facă acest lucru prea mult.
Dar va simplifica acest exemplu.
Deci, vreau să declar o listă legat aici.
Acum, cum s-ar putea să fac asta?
>> Iată imaginea unei liste legate.
Și eu nu prea știe în acest moment cât de
Am de gând să merg despre reprezentarea atât de multe lucruri cu un fel
variabilă în memorie.
Dar gandeste-te înapoi o clipă.
În tot acest timp am avut siruri de caractere, pe care apoi
dovedit a fi matrici de personaje, pe care apoi
dovedit a fi doar un pointer la primul caracter
într-o matrice de caractere care este nul reziliat.
Deci, conform acestei logici, și cu această imagine fel de însămânțare gandurile tale,
ceea ce trebuie să ne scrie de fapt în nostru cod pentru a reprezenta o listă înlănțuită?
Cât de mult de această informație avem nevoie pentru a capta în cod C, ai spune?
Da?
>> Audiența: Avem nevoie de un pointer la un nod.
David J. MALAN: Un pointer la un nod.
În special, care nod ar ta Instinctele fi de a păstra un pointer la?
>> Audiența: primul nod.
>> David J. MALAN: Da, probabil doar primul.
Și observați, primul nod este o formă diferită.
E doar jumătate din dimensiunea struct, pentru că este într-adevăr doar un pointer.
Deci, ce se poate face într-adevăr este declara o listă înlănțuită a fi de tip nod *.
Și hai să-i spunem întâi și se inițializa la null.
Deci nul, din nou, este venirea în imaginea de aici.
Nu numai ca este nul folosit ca ca un special Valoarea de retur pentru lucruri cum ar fi getstring
și malloc, nul este de asemenea zero pointer, lipsa unui pointer,
dacă vrei.
Aceasta înseamnă doar nimic nu este încă aici.
Acum întâi, am fi putut numit acest ceva.
Aș fi putut numit-o "listă" sau orice număr de alte lucruri.
Dar eu voi spune "primul", astfel încât Liniile-l cu această imagine.
Deci, la fel ca un șir poate fi reprezentat cu adresa de primul octet,
deci poate o listă înlănțuită.
Și vom vedea alte date Structurile fi reprezentat
cu doar un singur indicator, o săgeată pe 32 de biți, arătând
chiar la primul nod în structură.
>> Dar acum să anticipeze o problemă.
Dacă am doar amintindu- în programul meu adresa
din primul nod, primul dreptunghi în această structură de date,
ceea ce a avut mai bine în dosarul punerea în aplicare a restului lista mea?
Ce este un detaliu cheie care va pentru a asigura acest lucru funcționează de fapt?
Și prin "funcționează de fapt" I Adică, mai mult ca un șir de caractere,
ne permite să mergem de la primul caracter în nume Davin la a doua,
a treia, pentru a al patrulea, până la capăt,
cum știm când suntem la sfârșitul de o lista inlantuita care arata ca aceasta?
Când este nul.
Și l-am reprezentat acest tip de ca ca o putere inginer electric,
cu mic impamantare simbol, de felul.
Dar asta înseamnă doar nul în acest caz.
Puteți să-l trage orice număr de moduri, dar acest autor
sa întâmplat de a folosi acest simbol aici.
>> Atât timp cât suntem înșirare toate aceste noduri împreună,
numai amintindu unde Prima dintre ele este, atât de mult timp
ca am pus un simbol special la ultimul nod din lista,
și vom folosi nul, pentru că asta e ceea ce avem la dispoziție pentru a ne,
această listă este completă.
Și chiar dacă doar vă dau un pointer la primul element, tu, programator,
pot accesa cu siguranță restul.
Dar să-l lăsăm mințile voastre rătăcesc un pic,
în cazul în care nu sunt deja destul de wandered-- ceea ce-i
va fi timpul de execuție a găsi ceva în această listă?
La naiba, e O mare de n, care nu este rău, în corectitudine.
Dar este liniară.
Am renunțat la ceea ce caracteristică de tablouri de mișcare mai mult
față de această imagine de dinamic țesute împreună sau noduri legate?
Am renunțat acces aleator.
Un tablou este frumos, pentru că matematic totul
este spate în spate la spate în spate.
Chiar dacă această imagine pare destul, și chiar
deși se pare că aceste noduri sunt bine distanțate, în realitate
acestea ar putea fi oriunde.
OX1, Ox50, Ox123, Ox99, acestea noduri ar putea fi oriunde.
Pentru ca malloc nu aloca memorie din grămada, dar oriunde în grămada.
Nu știi neapărat că este Va fi înapoi la spate în spate.
Și astfel, această imagine în realitate lui nu va fi destul de acest frumos.
>> Deci, va fi nevoie de un pic de de lucru pentru a pune în aplicare această funcție.
Deci, haideți să pună în aplicare de cautare acum.
Și vom vedea un fel de mod inteligent de a face acest lucru.
Deci, dacă eu sunt o funcție de căutare și Am dat o variabilă, întreg n
să caute, am nevoie să știu nou sintaxă pentru căutarea în interiorul
unei structuri care este a subliniat, pentru a găsi n.
Deci, hai sa facem acest lucru.
>> Deci, primul am de gând să merg înainte și să declare un nod *.
Și am de gând să-l numesc pointer, doar prin convenție.
Și am de gând să-l inițializa la primul.
Și acum pot face acest lucru într-un număr de moduri.
Dar am de gând să ia o abordare comună.
In timp ce indicatorul nu este egal cu nul, și asta e valabil sintaxă.
Și aceasta înseamnă doar procedați în felul următor, așa timp cât nu te îndreptat la nimic.
Ce vreau să fac?
>> În cazul în care indicatorul punct n, lasă-mă să vin înapoi pentru că, equals-- este egal cu ce?
Ce valoare caut?
N efectiv care a fost trecut în.
Deci, aici este o altă caracteristică de C și mai multe limbi.
Chiar dacă structura numita nodul n are o valoare, cu totul legitim
să aibă, de asemenea, un argument locală sau variabilă numită n.
Deoarece chiar noi, cu ochii omului, se poate distinge
că această n este probabil diferit de acesta n.
Deoarece sintaxa este diferită.
Ai un punct și un pointer, întrucât acesta nu are un astfel de lucru.
Deci, acest lucru este OK.
Asta e OK să-i numească aceleași lucruri.
>> Dacă eu ți se pare acest lucru, eu sunt O să vrei să faci ceva
ca anunțăm că am găsit n.
Și vom lăsa ca pe un comentariu sau cod pseudocod.
Altfel, și aici e parte interesant, ceea ce
nu vreau să fac în cazul în care nodul curent nu se conțin n care îmi pasă?
Cum pot obține următoarele?
Dacă degetul meu de la moment este PTR, și este
arătând la orice Primul este îndreptat la,
cum pot muta degetul meu la urmatorul nod din cod?
Ei bine, ceea ce e de pesmet suntem va urma în acest caz?
Audiența: [inaudibil].
David J. MALAN: Da, așa următor.
Deci, dacă mă întorc la meu Codul aici, într-adevăr, eu sunt
merge mai departe și spune pointer, care este doar un variable-- temporar este
un nume ciudat, ptr, dar e la fel ca temp--
Am de gând să se stabilească pointer egal cu orice pointer este--
și din nou, acest lucru va fi o puțin buggy pentru un punct moment-- următor.
Cu alte cuvinte, am de gând să-mi iau deget care este îndreptat la acest nod
aici și am de gând să spun, știi ceea ce, arunca o privire la următorul câmp
și mișcați-vă degetul orice este îndreptat la.
Și acest lucru se întâmplă pentru Repet, repet, repeta.
Dar când nu-mi degetul nu mai faci nimic, la toate?
De îndată ce ceea ce linie de lovituri de cod în?
Audiența: [inaudibil]
David J. MALAN: Dacă punctul în timp ce pointer nu este egal cu NULL.
La un moment dat mi degetul lui va fi îndreptată la nul
și am de gând să dau seama că e sfârșitul acestei liste.
Acum, acest lucru este un pic minciună albă pentru simplitate.
Se pare că, deși noi doar învățat această notație punct
pentru structuri, indicatorul nu este o struct.
ptr este ceea ce?
Doar pentru a fi mai nitpicky.
Este un pointer la un nod.
Nu este un nod în sine.
Dacă aș fi avut nici o stea aici, pointer absolutely-- este un nod.
Aceasta este ca o saptamana declarație a unei variabile,
chiar dacă cuvântul "nod" este nou.
>> Dar, de îndată ce vom introduce o stele, este acum un pointer la un nod.
Și, din păcate, nu puteți utiliza notația punct de un pointer.
Trebuie să utilizați săgeata notație, care, surprinzător,
este pentru prima dată orice piesă de sintaxă arată intuitiv.
Acest lucru pur și simplu arată ca o săgeată.
Și așa că e un lucru bun.
Și aici literalmente arata ca o săgeată.
Deci, eu cred că e la-- eu nu fac că am peste-comiterea aici-- I
Cred că e ultima piesă nouă de sintaxă vom vedea.
Și din fericire, este într-adevăr un pic mai mult intuitiv.
>> Acum, pentru cei dintre voi care s-ar putea prefera vechiul mod,
puteți utiliza în continuare notația punct.
Dar, conform luni de conversație, am primul
Trebuie să mergem acolo, du-te la asta adresa, iar apoi accesați acest domeniu.
Deci, acest lucru este, de asemenea, corect.
Și sincer, aceasta este o puțin mai pedant.
Ești pur și simplu spunând dereference indicatorul și du-te acolo.
Apoi apuca .n, câmpul numit n.
Dar, sincer, nimeni nu vrea pentru a introduce sau de a citi acest lucru.
Și astfel lumea a inventat notația săgeată, care
este echivalent, identic, e doar zahăr sintactic.
Deci, un mod elegant de a spune acest lucru arata mai bine, sau arata mai simplu.
>> Așa că acum am de gând să fac un lucru.
Am de gând să spun "pauză" o dată am Am găsit-o așa că nu sa mai caut pentru ea.
Dar aceasta este esența de o funcție de căutare.
Dar e mult mai ușor, în end, pentru a nu umbla prin codul.
Aceasta este într-adevăr implementarea formală de căutare în codul de distributie de astăzi.
Îndrăznesc să spun că inserție nu este mai ales distractiv de a merge prin
vizual, nici nu este șterge, chiar deși la sfârșitul zilei
se fierbe până la destul de euristici simple.
>> Deci, hai sa facem acest lucru.
Dacă veți umor mine aici, am făcut aduce o grămadă de mingi de stres.
Am adus o grămadă de numere.
Și am putea obține doar câteva voluntari pentru a reprezenta 9, 17, 20, 22, 29, și 34?
Deci, în esență, toată lumea cine e aici azi.
Asta a fost una, două, trei, patru, cinci, șase oameni.
Și am fost rugat să go-- vedea, nu una în partea din spate ridică mâinile lor.
OK, unu, doi, trei, patru, cinci-- lasă-mă să încarce balance-- șase.
OK, ai șase haide sus.
Vom avea nevoie de alte persoane.
Am adus bile suplimentare de stres.
Și dacă ai putea, pentru doar o clipă, linie
vă în sus doar mult de această imagine aici.
>> În regulă.
Să vedem, care e numele tău?
>> Audiența: Andrew.
>> David J. MALAN: Andrew, sunteti numărul 9.
Mă bucur să te cunosc.
Aici te duci.
Audiența: Jen.
David J. MALAN: Jen.
David.
Numărul 17.
Da?
>> Audiența: Eu sunt Julia.
>> David J. MALAN: Julia, David.
Numărul 20.
Audiența: Christian.
David J. MALAN: Christian, David.
Numărul 22.
Și?
>> Audiența: JP.
David J. MALAN: JP.
Numărul 29.
Deci, mergeți mai departe și a obține in-- Uh oh.
Uh oh.
Standby.
20.
Are cineva un marker?
Audiența: Am un Sharpie.
David J. MALAN: Ai un Sharpie?
OK.
Și nimeni nu avea o bucată de hârtie?
Salvați curs.
Haide.
Audiența: L-am prins.
David J. MALAN: Ne-am prins?
Bine, mulțumesc.
Aici vom merge.
A fost aceasta de la tine?
Tocmai ai salvat ziua.
Deci, 29.
În regulă.
Am scris gresit 29, dar OK.
Dă-i drumul.
Bine, eu voi da pen-ul înapoi pentru moment.
Deci avem acesti oameni aici.
Hai să o alta.
Gabe, vrei să joci primul element aici?
Avem nevoie de tine la punctul la acesti oameni fine.
Deci 9, 17, 20, 22, sortare de 29, apoi 34.
Am pierdut pe cineva?
Am un 34.
În cazul în care did-- OK, care vrea să fie 34?
OK, hai sus, 34.
Bine, acest lucru va fi bine în valoare de punctul culminant.
Care e numele tău?
>> Audiența: Peter.
>> David J. MALAN: Peter, haide sus.
În regulă, așa că aici e un grămadă de noduri.
Fiecare dintre voi reprezintă unul dintre aceste dreptunghiuri.
Și Gabe, ușor ciudat om, reprezinta primul.
Deci, indicatorul său este un pic mai mic pe ecran decât oricine altcineva.
Și în acest caz, fiecare din stânga mâini este de gând să fie punctul de jos,
reprezentând astfel null, așa doar absenta unui pointer,
sau o să fie îndreptat la un nod de lângă tine.
>> Deci, acum, dacă împodobesc vă cum ar fi imaginea
aici, mergeți mai departe și punct unul la altul, cu Gabe
în îndreptat special la numărul 9 a reprezenta listă.
OK, și numărul 34, mâna stângă doar ar trebui să fie îndreptată la podea.
>> OK, deci aceasta este lista legat.
Deci, acesta este scenariul în cauză.
Și într-adevăr, aceasta este reprezentativ a unei clase de probleme
care s-ar putea încerca să rezolve cu cod.
Vrei să inserați în cele din urmă un element nou în listă.
În acest caz, vom încercați să introduceți numărul 55.
Dar nu va fi cazuri diferite să ia în considerare.
Și într-adevăr, acest lucru va fi un de-imaginea de ansamblu takeaways aici, este,
care sunt diferite cazuri.
Care sunt diferitele cazul în care condițiile sau ramuri care programul ar putea avea?
>> Ei bine, numărul pe care încercați să inserție, care știm acum să fie 55,
dar dacă nu știai în prealabil, îndrăznesc să spun
se încadrează în cel puțin trei situații posibile.
În cazul în care s-ar putea fi un element nou?
Audiența: Și la sfârșitul sau mijlocul.
David J. MALAN: La sfârșitul anului, în la mijloc, sau la început.
Așa că pretind că sunt cel puțin trei probleme trebuie să rezolve.
Să alegem ce este, probabil, fără îndoială, cea mai simplă
unul, în cazul în care noul element aparține la început.
Așa că am de gând să aibă cod destul de cum ar fi de căutare, pe care am scris doar.
Și am de gând să aibă ptr, care Voi reprezenta aici cu degetul,
ca de obicei.
>> Și amintiți-vă, ce valoare am inițializa ptr a?
Deci, l-am pregătit pentru a null inițial.
Dar atunci ce am face o dată ne-am au fost în funcție de căutare?
Ne-am propus o egal cu primul, ceea ce nu înseamnă a face acest lucru.
Dacă am setat ptr egal cu primul, ceea ce ar trebui să fie într-adevăr mâna arătând spre?
Corect.
Deci, dacă Gabe și cu mine vom a fi valori egale aici,
avem nevoie de atât punct la numărul 9.
>> Deci asta a fost inceputul povestii noastre.
Iar acum acest lucru este doar simplu, chiar dacă sintaxa este nou.
Conceptual acest lucru este doar de căutare liniară.
Este 55 egal cu 9?
Sau, mai degrabă, să spunem mai puțin de 9.
Pentru că încerc să dau seama unde să pună 55.
Mai puțin de 9, la mai puțin de 17, mai puțin mult de 20, mai mic de 22, mai mic de 29,
mai puțin de 34, nr.
Deci, acum suntem în caz unul din cel puțin trei.
>> Dacă vreau să insera peste 55 de ani aici, ceea ce de linii de cod au nevoie pentru a obține executat?
Cum această imagine de oamenii au nevoie pentru a schimba?
Ce să fac cu mana stanga?
Acest lucru ar trebui să fie nul inițial, pentru că eu sunt de la sfârșitul listei.
Și ce ar trebui să se întâmple aici cu Peter, a fost?
El, evident, va indica mine.
Așa că pretind că sunt cel puțin două linii de cod în codul proba de azi
care va pune în aplicare această scenariu de adăugarea de 55 la coada.
Și aș putea avea cineva hop și chiar reprezintă 55?
Bine, tu esti nou 55.
>> Deci, acum, ce se întâmplă dacă următorul scenariu vine,
și dorim să introduceți la început sau capul acestei liste?
Și care e numele tău, numărul 55?
>> Audiența: Jack.
>> David J. MALAN: Jack?
OK, mă bucur să te cunosc.
Bine ai venit la bord.
Deci, acum vom introduce, de exemplu, numărul 5.
Aici este al doilea caz de trei am venit cu înainte.
Deci, dacă 5 aparține la început, hai sa vedem cum putem afla asta.
Am inițializa ptr meu pointer la numărul 9 din nou.
Și am realizat, oh, 5 este mai mică de 9.
Deci rezolva această imagine pentru noi.
Al cui mâinile, lui Gabe sau lui David sau-- care e numele lui numărul 9?
>> Audiența: Jen.
>> David J. MALAN: hands-- lui Jen care de mâinile noastre trebuie să se schimbe?
OK, deci Gabe arată la ce acum?
La mine.
Eu sunt noul nod.
Deci, eu doar un fel de mișcare aici pentru a vedea vizual.
Și între timp ce eu subliniez asta?
Totuși unde am îndreptat.
Deci, asta este.
Așa că într-adevăr o linie de remedieri de cod această problemă, s-ar părea.
În regulă, așa că e bine.
Și poate cineva să fie un substituent pentru 5?
Hai sus.
Vă vom lua data viitoare.
>> În regulă, așa acum-- și Ca o paranteza, numele
Nu fac referire în mod explicit de drept acum, pointer pred, predecesorul pointer
și noi pointer, care este doar numele dat
în codul eșantion de indicii sau mâinile mele că e un fel de indicare în jurul.
Care e numele tău?
>> Audiența: Christine.
>> David J. MALAN: Christine.
Bine ai venit la bord.
Bine, să luăm în considerare acum un scenariu ceva mai enervant,
prin care vreau să inserați ceva de genul 26 în asta.
20?
Ce?
Acestea esti-- lucru bun avem acest stilou.
În regulă, 20.
În cazul în care cineva ar putea primi o altă bucată de hârtie gata, doar în case-- bine.
Oh, interesant.
Ei bine, acesta este un exemplu de un bug curs.
OK deci care e numele tau?
Audiența: Julia.
David J. MALAN: Julia, puteți pop afară și te prefaci că nu au fost niciodată acolo?
OK, nu sa întâmplat acest lucru.
Mulțumesc.
Deci, să presupunem că vrem introduce Julia în această listă înlănțuită.
Ea este numărul 20.
Și, desigur, e O să fac la
incepem nu punct la nimic încă.
Deci, mâna ta poate fi un fel de jos null sau o valoare gunoi.
Să spun povestea rapid.
Am îndreptat în număr de 5 acest moment.
Apoi am verificat 9.
Apoi am verifica 17.
Apoi am verifica 22.
Și îmi dau seama, ooh, Julia trebuie să meargă înainte de 22.
Deci, ceea ce trebuie să se întâmple?
A cui mâini nevoie pentru a schimba?
Julia, a mea, sau-- Care e numele tău?
>> Audiența: Christian.
>> David J. MALAN: Christian sau?
>> Audiența: Andy.
>> David J. MALAN: Andy.
Christian sau Andy?
Andy trebuie să arate la?
Julia.
În regulă.
Deci Andy, vrei sa arate la Julia?
Dar stai un minut.
În povestea până acum, Eu sunt genul de unul
responsabil, în sensul că pointer este un lucru care este
se deplasează prin lista.
Am putea avea un nume pentru Andy, dar nu exista nici o variabilă numită Andy.
Singura variabilă avem este în primul rând, care este reprezentat de Gabe.
>> Deci, acesta este de fapt motivul pentru astfel acum nu am nevoie de asta.
Dar acum pe ecran este vorbim din nou de pointer pred.
Așa că lasă-mă să fiu mai explicit.
În cazul în care acest lucru este pointer, am avut mai bine obține un pic mai inteligent
despre repetare mea.
Dacă nu te superi mea trece printr aici din nou, arătând aici, arătând aici.
Dar permiteți-mi să aibă un pointer pred, predecesorul pointer, care este
fel de îndreptat la Element Am fost doar la.
Așa că atunci când merg aici, acum actualizările mele din stânga.
Când mă duc aici actualizările mele de la mâna stângă.
Și acum am nu numai un pointer la elementul care merge după Julia,
Mai am un pointer la Andy, elementul înainte.
Deci, aveți acces, în esență, pesmet, dacă vreți,
la toate indicii necesare.
>> Deci, dacă am îndreptat la Andy și eu sunt, de asemenea, indică
la Christian, ale căror mâini acum trebuie să se arate în altă parte?
Deci, Andy poate indica acum la Julia.
Julia pot indica acum la Christian.
Pentru că ea poate copia mea pointer mâna dreaptă a lui.
Și pe care le pune în mod eficient înapoi în acest loc aici.
Deci, pe scurt, chiar dacă aceasta este de a lua noi un fel de pentru totdeauna
pentru a actualiza de fapt o Lista legate, realiza
că operațiunile sunt relativ simple.
Este de unul, doi, trei de linii de cod în cele din urmă.
Dar înfășurat în jurul celor de linii de cod probabil în
este un pic de logică pe care în mod eficient pune întrebarea, unde suntem?
Suntem la început, la mijloc, sau la sfârșit?
>> Acum, există cu siguranță o altă operațiuni s-ar putea pune în aplicare.
Și aceste poze aici doar descrie ceea ce tocmai am făcut-o cu oamenii.
Ce despre eliminarea?
Dacă vreau să, de exemplu, elimina numărul 34 sau 55,
S-ar putea avea același tip de cod, dar am de gând să nevoie de unul sau doi pași.
Pentru că ce mai e nou?
Dacă am scoate cineva la sfârșitul anului, cum ar fi numărul 55 și apoi 34,
ceea ce are, de asemenea, să se schimbe ca să fac asta?
Nu am să evict-- Care e numele tău?
>> Audiența: Jack.
>> David J. MALAN: Jack.
Trebuie să nu numai evict-- liber Jack, astfel suna literalmente liber Jack, sau cel puțin
indicatorul acolo, dar acum ceea ce trebuie să se schimbe cu Peter?
Mâna lui mai bine începe cu vârful în jos.
Pentru că, de îndată ce suna gratuit la Jack, dacă Petru încă îndreptat la Jack
și eu, prin urmare, să păstreze traversează lista și accesa acest indicator,
atunci prietenul nostru segmentare vechi vina s-ar putea lovi cu piciorul în fapt.
Pentru că ne-am dat memorie înapoi la Jack.
>> Poți să stai acolo neîndemânatic pentru doar o clipă.
Pentru ca avem doar un cuplu operațiuni finale să ia în considerare.
Scoaterea capul listei, sau beginning-- și asta e
un pic enervant.
Pentru că trebuie să știm că Gabe este un fel de special la acest program.
Pentru că, într-adevăr, el are propria lui pointer.
El nu a fost doar a subliniat, la, ca este aproape oricine altcineva de aici.
>> Deci, atunci când capul listei este îndepărtat, ale cărui mâini au nevoie pentru a schimba acum?
Care e numele tău?
>> Audiența: Christine.
>> David J. MALAN: Sunt groaznic la nume, aparent.
Deci, Christine și Gabe, ale căror mâini au nevoie pentru a schimba
atunci când încercați să eliminați Christine, numărul 5, de la imaginea?
OK, așa că hai să facem Gabe.
Gabe se va indica, probabil, la numărul 9.
Dar ce viitor trebuie să se întâmple?
Audiența: Christine ar trebui fi nul [neauzit].
David J. MALAN: OK, ar trebui, probabil, make-- am auzit "nul" pe undeva.
Audiența: Null și liber ei.
David J. MALAN: NULL ce?
Audiența: Null și liber ei.
David J. MALAN: Null și liber ei.
Deci, acest lucru este foarte simplu.
Și e perfect ca esti acum un fel de a sta acolo, nu aparțin.
Pentru că ai fost decuplat din lista.
Ai fost efectiv orfani din listă.
Și așa ne-am numi mai bine gratuit acum pe Christine a da ca memoria înapoi.
În caz contrar, de fiecare dată când șterge un nod din lista
am putea fi a face lista mai scurt, dar nu chiar în scădere
dimensiunea în memorie.
Și așa, dacă am păstra adăugarea și adaugand, adăugând lucruri de pe lista,
calculatorul meu s-ar putea obține mai lent și mai lent și mai lent,
pentru că eu sunt pe punctul de a memorie, chiar dacă eu nu sunt de fapt
folosind bytes Christine de memorie mai.
>> Deci, în cele din urmă, există alte scenarii, de îndepărtare bineinteles--
în mijloc, eliminarea la sfârșitul anului, așa cum am văzut.
Dar mai interesant provocare acum este
va fi să ia în considerare exact ceea ce este timpul de execuție.
Deci, nu numai că puteți să vă păstrați bucăți de hârtie, în cazul în care, Gabe,
nu te superi da toată lumea o minge de stres.
Vă mulțumesc foarte mult pentru a lista noastră legată de voluntari aici, dacă ai putea.
>> [Aplauze]
>> David J. MALAN: Bine.
Deci, un cuplu de analiză întrebări atunci, dacă aș putea.
Am văzut această notație înainte, O mare și omega, limite superioare
și limite mai mici de pe Timp de câteva algoritm care rulează.
Deci, să luăm în considerare doar câteva întrebări.
>> O, și am spus-o înainte, ceea ce este în funcțiune
timp de căutare pentru a Lista în termeni de mare O?
Ce este o limită superioară de funcționare timp de a căuta o listă înlănțuită
puse în aplicare de către voluntarii nostri aici?
Este O mare de n, liniare.
Pentru că, în cel mai rău caz, elementul, cum ar fi 55,
am putea fi în căutarea de ar fi în cazul în care Jack a fost, tot drumul de la sfârșitul.
Și, din păcate, spre deosebire de o matrice nu putem obține de lux de data asta.
Chiar dacă toți oamenii noștri au fost clasificate în funcție de elementele de mici, 5,
tot drumul până la elementul mai mare, 55, care este de obicei un lucru bun.
Dar ceea ce face ca ipoteza nu mai ne permit să facem?
Audiența: [inaudibil]
David J. MALAN: Spune din nou?
Audiența: acces aleator.
David J. MALAN: acces aleator.
Și la rândul său, înseamnă că putem să nu mai folosi zerouri slab, intuiție,
și evidență a folosi binar de căutare și diviza și cuceri.
Pentru că, chiar dacă ne-am oamenii ar putea, evident,
vedea că Andy sau creștin-au aproximativ în mijlocul listei,
Știm doar că în calitate de calculator de skimming pe lista
de la bun început.
Așa că am renunțat la care acces aleator.
>> O atât de mare de n acum este superioară legat pe timp de căutare.
Ce despre omega de căutare nostru?
Care este cea mai mică legat la căutare pentru un numar din această listă?
Audiența: [inaudibil]
David J. MALAN: Spune din nou?
Audiența: Unul.
David J. MALAN: Unu.
Deci timp constantă.
În cel mai bun caz, Christine este într-adevăr, la începutul listei.
Și căutăm numărul 5, asa ca am găsit-o.
Deci, nu e mare lucru.
Dar ea trebuie să fie la începând din lista din acest caz.
Ce zici de ceva de genul Delete?
Ce se întâmplă dacă doriți să ștergeți un element?
Care este limita superioară a și limita inferioară la ștergerea ceva de la o legătură
lista?
Audiența: [inaudibil]
David J. MALAN: Spune din nou?
Audiența: n.
David J. MALAN: n este într-adevăr, limita superioară.
Pentru că, în cel mai rău caz vom încerca pentru a șterge Jack, ca tocmai am făcut-o.
El e tot drumul la sfârșitul anului.
Ne ia pentru totdeauna, sau n pași să-l găsească.
Deci, asta e o limită superioară.
Asta e liniar, sigur.
Și cel mai bun caz temporizare, sau limitele inferioare, în cel mai bun caz
ar fi timp constant.
Pentru că poate că încercați să ștergeți Christine, și ne-am noroc
ea e la început.
Acum, așteptați un minut.
Gabe a fost, de asemenea, la început, și am avut, de asemenea, pentru a actualiza Gabe.
Așa că nu a fost doar un pas.
Deci, este într-adevăr constant timp, în cel mai bun caz,
pentru a îndepărta cel mai mic element?
Este, cu toate că ar putea fi de două, trei, sau chiar 100 de linii de cod,
dacă e același număr de linii, nu în unele buclă,
și independent de dimensiunea listei, absolut.
Ștergerea elementului la începutul listei,
chiar dacă avem de-a face cu Gabe, este încă timp constant.
>> Deci, aceasta pare a fi o pas masiv înapoi.
Și ce o pierdere de timp în cazul în care, în săptămâna de o săptămână și
zero, am avut nu numai Codul pseudocod dar codul actual
să pună în aplicare ceva care este log de bază n, sau jurnal, mai degrabă, de n, baza 2,
în ceea ce privește timpul de rulare.
Deci, de ce naiba ne-ar dori să înceapă folosind ceva de genul o listă de legat?
Da.
>> Audiența: Deci, puteți adăuga elemente la matrice.
David J. MALAN: Deci, poți adăuga elemente la matrice.
Și acest lucru este de asemenea tematic.
Și vom continua pentru a vedea aceasta, acest compromis, mult
ca am vazut-o trade-off cu îmbinare tip.
Am putea accelera într-adevăr în sus căutare sau de sortare, mai degrabă,
dacă ne petrecem un pic mai mult spațiu și au o bucată suplimentară a unei memorii
sau o serie de îmbinare fel.
Dar ne petrecem mai mult spațiu, dar ne-am economisi timp.
În acest caz, suntem renunțarea la timp, dar suntem
câștigă flexibilitate, dinamism, dacă vrei,
care este, fără îndoială, o trăsătură pozitivă.
>> Ne petrecem de asemenea spațiu.
În ce sens este o legătură Lista mai scump
în termeni de spațiu decât un tablou?
În cazul în care este spatiul in plus vine de la?
Da?
>> Audiența: [inaudibil] pointer.
>> David J. MALAN: Da, ne-am au, de asemenea, indicatorul.
Deci, aceasta este minorly enervant în care nu mai sunt
Am stocarea doar un int pentru a reprezenta un întreg.
Am stocarea un int și un pointer, care este de asemenea de 32 de biți.
Deci, eu sunt literalmente dublarea cantitatea de spațiu implicat.
Deci, asta e un compromis, dar care este în cazul Int.
Să presupunem că nu ești stocarea int, dar să presupunem că fiecare dintre aceste dreptunghiuri
sau fiecare dintre acesti oameni a fost reprezentând un cuvânt, un cuvânt englezesc, care
ar putea fi de cinci caractere, 10 caractere, poate chiar mai mult.
Apoi, adăugând doar 32 mai mulți biți s-ar putea să fie mai puțin de o afacere mare.
>> Ce se întâmplă dacă fiecare dintre elevi în demonstrația
au fost literalmente o structura de studenți care au nume și case și poate
numere de telefon și Twitter mânere și altele asemenea.
Așa că toate câmpurile am început vorbim despre ieri,
mult mai puțin de o afacere de mare ca noduri noastre devin mai interesante
și mare să-și petreacă, nu-i așa, o suplimentare de pointer doar pentru a le lega împreună.
Dar, într-adevăr, este un compromis.
Și într-adevăr, codul este mai complex, după cum veți
a se vedea de skimming prin acel exemplu particular.
Dar dacă s-au unele Sfântul Graal aici.
Ce se întâmplă dacă nu luăm un pas înapoi, dar un pas înainte masiv
și să pună în aplicare o de date structură prin care noi
Puteți găsi elemente, cum ar fi Jack sau Christine sau orice alte elemente
în această matrice în adevăratul timp constant?
Search este constant.
Ștergeți este constantă.
Introduceți este constantă.
Toate aceste operațiuni sunt constante.
Asta ar fi Graal nostru sfânt.
Și că este în cazul în care ne-am va ridica data viitoare.
Ne vedem atunci.