>> [REPRODUCCIÓ DE MÚSICA]
>> [REPRODUCCIÓ DE VÍDEO]
>> -Ell És mentir.
>> -Sobre que?
>> -No ho sé.
>> -Llavors, ¿Què en sabem?
>> -Que A les 9:15, Ray Santoya estava al caixer automàtic.
-Sí.
Així que la pregunta és, què estava fent a les 9:16?
>> -Shooting Mil·límetre setembre en alguna cosa.
Potser va veure el franctirador.
>> -O Va ser treballar amb ell.
>> -Espera.
Torna un.
>> -Què veus?
>> -tingui El seu rostre fins pantalla completa.
>> -Els Seus Ulleres.
>> -Hi Ha Una reflexió.
>> -És L'equip de beisbol de Nuevitas.
Aquesta és la seva logotip.
>> -I Ell està parlant amb el que porta la jaqueta.
>> [FI DE REPRODUCCIÓ]
>> DAVID Malan: D'acord.
Això és CS50 i això és una mica més de [inaudible] amb la qual estàs
passos amb el problema d'establir quatre.
Avui comencem a mirar una mica més profundament en aquestes coses anomenades punters,
que tot i que és un tema bastant arcà,
resulta que es va ser el mitjà pel qual ens
pot començar a construir i muntatge programes molt més sofisticats.
Però ho vam fer en dimecres passat per mitjà d'alguns claymation primer.
Així que això, recordar, és Binky i nosaltres el fem servir
a fer una ullada a un programa que realment no fer res interessant,
però sí va revelar alguns problemes.
Així que per començar avui, per què no ens anem ràpidament a través d'alguns d'aquests passos,
tractar de destil·lar en termes d'humans exactament el que està passant aquí
i per què això és dolent, i després seguir endavant i realment començar a construir alguna cosa
amb aquesta tècnica?
Així que aquests van ser els primers dues línies en aquest programa
i en termes simples, el que estan fent aquestes dues línies?
Algú que és raonablement còmode amb el que ha declarat a la pantalla?
Quines són aquestes dues línies que fan?
No és tot el que diferent de setmana un,
però que una novetat símbol especial.
Sí?
Tornar-hi.
>> AUDIÈNCIA: Declarar punters?
DAVID Malan: Digui una altra vegada?
AUDIÈNCIA: Declarar punters?
DAVID Malan: punters declarar i anem a refinar una mica més.
AUDIÈNCIA: [inaudible] direcció x i i.
DAVID Malan: I després abordar.
Així que específicament el que estem fent Som nosaltres vam declarar dues variables.
Aquestes variables, però, van ser de tipus int estrella, que
significa més específicament van a emmagatzemar
la direcció d'un int, respectivament, x i y.
Ara hi ha cap valor?
Hi ha adreces reals en aquests dues variables en aquest punt en el temps?
No.
Simplement ha anomenats valors d'escombraries.
Si en realitat no assigna un variables, el que fos a la memòria RAM
prèviament es va a omplir de zeros i els dos d'aquestes variables.
Però encara no sabem el que són i això és
serà la clau de per què Binky perdut el cap la setmana passada.
>> Així que aquest era el claymation encarnació d'aquesta
pel qual vostè té només dues variables petites peces circulars d'argila,
que pot emmagatzemar variables, però com les fletxes embolicades suggereixen,
no estan realment apuntant a qualsevol lloc conegut per se.
Així que vam tenir aquesta línia, i això era nou la setmana passada, malloc per a la memòria
assignació, que és només una forma elegant de dir-li al sistema operatiu, Linux
o Mac OS o Windows, escolta, dóna'm una mica de memòria,
i tot el que ha de comptar el sistema operatiu
és el que quan se li demana que per a la memòria.
No va a cuidar el que que vas a fer amb ell,
però sí que és necessari per explicar l'operació sistema del que a través de malloc.
Sí?
>> AUDIÈNCIA: Quant?
DAVID Malan: Quant?
Quant en bytes, i així, això, de nou, un exemple artificial, és només dir,
dóna'm la mida d'un int.
Ara, la mida d'un int és de quatre bytes o 32 bits.
Així que això és només una forma de dient, hey, sistema operatiu,
dóna'm 4 bytes de memòria que puc utilitzar a la meva disposició,
i en concret, el que fa retorn malloc respecte
a aquest tros de quatre bytes?
AUDIÈNCIA: Direcció?
DAVID Malan: la direcció.
La direcció d'aquest tros de quatre bytes.
Exactament.
I això és el que està emmagatzemat en última instància, en x i per això no ho fem realitat
cuidar el que el nombre d'aquest direcció és, si es tracta de OX1 o ox2
o alguna adreça hexadecimal críptica.
Ens preocupem pictòricament que aquesta variable x és ara
apuntant al fet que part de la memòria.
Així que la fletxa representa un punter o Més específicament, una adreça de memòria.
Però, de nou, no ens preocupem en general el que aquestes direccions són reals.
Ara, aquesta línia diu el que en termes simples?
Estrella x aconsegueix 42 punt i coma.
Què vol dir això?
Vols anar?
No ratlli el coll.
>> AUDIÈNCIA: La direcció de x està en el 42.
>> DAVID Malan: La direcció de x és als 42.
No exactament.
Tan a prop, però no del tot, perquè hi ha l'estrella que està anteposant aquesta x.
Així que hem d'ajustar una mica.
Sí?
>> AUDIÈNCIA: El valor que el punter x està apuntant és 42.
DAVID Malan: OK.
El valor que el punter x és apuntant a, diguem, seran 42,
o dit d'una altra manera, l'estrella x diu, anar a qualsevol adreça
està en x, ja sigui 1 Oxford Carrer o 33 Oxford Street
o OX1 o OX33, qualsevol que sigui que adreça numèrica és,
estrella de x és el desreferència de x.
Així que anar a aquesta direcció i a continuació, posar el número 42 allà.
Així que seria un manera equivalent a dir això.
Així que això és tot fi i després volem representar la imatge
de la següent manera en què hem afegit la 42 a la part de les quatre
bytes en el costat dret, però aquesta línia era on les coses van sortir malament
i el cap de Binky aparèixer en aquest punt,
perquè les coses dolentes succeeixen quan d'eliminar la referència dels valors d'escombraries
o eliminar la referència no vàlid punters, i em diuen que no vàlid
perquè en aquest punt en el història, el que està dins de i?
Quin és el valor de i en base en els últims passos?
Sí?
Què és això?
>> AUDIÈNCIA: Una adreça.
DAVID Malan: Una adreça.
Ha de ser una adreça però he inicialitzat ell?
Així que no tinc.
Llavors, què se sap que és d'allà?
És només un cert valor de les escombraries.
Podria ser qualsevol adreça de zero a 2000000000 si té dos gigues de RAM,
o zero a 4 milions de dòlars si vostè té té quatre gigabytes de RAM.
És cert valor de les escombraries, però el problema és
que el sistema operatiu, si no s'ha donat
que parteix de la memòria específica que vostè està tractant d'anar,
és generalment va a causar el que hem vist com una fallada de segmentació.
Així que, de fet, qualsevol de vostès que tenen lluitat en problemes en horari d'oficina
o en els problemes que més generalment amb tractant d'esbrinar
un error de segmentació, això significa generalment
estàs tocant un segment de la memòria que no ha de ser.
Estàs tocant de memòria que el sistema operatiu no té
li ha permès tocar, ja sigui per anar massa lluny en la matriu
o a partir d'ara, ja sigui és perquè vostè està tocant
memòria que simplement és un valor de les escombraries.
>> Així que fa l'estrella x aquí es tipus de comportament indefinit.
Vostè mai ha de fer-ho perquè les probabilitats són, el programa només va a xocar,
perquè vostè està dient, anar a aquesta adreça
i vostè no té cap idea d'on que la direcció és en realitat.
Així que el sistema operatiu és probable va estavellar el seu programa
com a resultat i, de fet, això és el que va passar allà per Binky.
Així, en última instància, Binky fixat aquest problema amb això.
Així que el programa en si era defectuós.
Però si vostè mena de seguir endavant i executar aquesta línia en el seu lloc,
i és igual a x només significa el que sigui direcció és una x, també posar-la en i.
>> I així pictòricament, tenim aquesta representat amb dues fletxes
de x i de y apuntant al mateix lloc.
Així semànticament, x és igual a i perquè tots dos d'aquells
s'emmagatzema el mateix direcció, ergo assenyalant a 42,
i ara, quan dius estrelles i, aneu a la direcció en i,
això té un efecte secundari interessant.
Així que la direcció en i és el el mateix que la direcció de x.
Així que si vostè diu anar a l'adreça en i i canvieu el valor a 13,
¿Qui més es veu afectat?
X és, el punt D, per així dir-ho, s'haurien de veure afectats també.
>> I, en efecte, com Nick va fer aquest dibuix en claymation era exactament això.
Tot i que seguim el punter i, que va acabar en el mateix lloc,
i pel que si haguéssim de imprimir terme xo pointee de i,
llavors podríem veure el valor de 13.
Ara, dic pointee sigui coherent amb el vídeo.
Programadors, al meu coneixement, en realitat mai
dir la paraula pointee, el que és punxeguda
a, però per a la consistència amb el vídeo, s'adonen
això és tot el que era significava en aquesta situació.
Així que qualsevol pregunta sobre claymation o punters o malloc encara?
No?
Tot bé.
>> Així que sense més preàmbuls, anem a fer una ullada
a on això té en realitat ha utilitzat durant algun temps.
Així que hem tingut aquesta biblioteca CS50 això té totes aquestes funcions.
Hem utilitzat getInt molt, GetString, Probablement GetLongLong anterior
en el meu PSet un o així, però el que ha estat passant en realitat?
Bé, anem a fer una ullada ràpida sota de la campana en un programa que
inspira opció et dóna l'CS50 biblioteca, i de fet a partir de la setmana passada,
vam començar a prendre les rodes d'entrenament fora.
Així que això és ara ordenades de l'autòpsia del que
ha estat succeint dins la biblioteca CS50,
tot i que ara començarem a moure lluny d'ell per a la majoria dels programes.
>> Així que aquest és un programa anomenat scanf 0.
És súper curt.
Només té aquestes línies, però introdueix una funció anomenada scanf
que estem en realitat va a veure en un moment dins la biblioteca CS50,
encara que en una forma lleugerament diferent.
Així que aquest programa a la línia 16 es declara una variable x.
Així que em donen quatre bytes per a un int.
Ha estat dient usuari, nombre favor i, a continuació,
aquesta és una línia interessant que realitat corbates junts la setmana passada
i això.
Scanf, i després noten que triga un cadena de format, igual que printf,
% I significa un int, i després es necessita un segon argument que es veu una mica
funky.
És signe x, i recordar, només vam veure això un cop passada setmana.
Quin signe x representa?
Què fa el símbol d'unió en C?
Sí?
>> AUDIÈNCIA: La direcció de.
DAVID Malan: La direcció de.
Així que és tot el contrari de l'operador de l'estrella,
mentre que l'operador de l'estrella diu, aneu a aquesta direcció, l'operador de signe
diu, esbrinar el Direcció d'aquesta variable,
i pel que aquesta és la clau, perquè El propòsit de scanf a la vida
és escanejar l'usuari de entrada des del teclat,
depenent del que ell o ella tipus i, a continuació, llegir l'entrada d'aquest usuari
en una variable, però va veure en les últimes dues setmanes
que aquesta funció d'intercanvi que intentat sense esforç per posar en pràctica
s'acaba de trencar.
Recordem que amb la funció d'intercanvi, si ens declarem A i B com sencers,
vam tenir intercanviem amb èxit el dues variables dins de bescanvi
igual que amb la llet i suc de taronja, però tan aviat com va tornar d'intercanvi,
quin va ser el resultat respecte axey, els valors originals?
Res.
Sí.
Res va passar aquell moment, perquè swaps canvien només les seves còpies locals,
que és a dir, tot aquesta vegada, cada vegada que hem
estat passant en els arguments a les funcions, estem
de pas còpies d'aquests arguments.
Vostè pot fer amb això el que vulguis amb ells,
però van a tenir cap efecte sobre els valors originals.
Així que això és problemàtic si vull tenir una funció com scanf
en la vida, el propòsit és escanejar l'entrada de l'usuari des del teclat
i després omplir els espais en blanc, de manera que parlar, és a dir, donar una variable com x
un valor, perquè si jo fos que només ha de passar x per scanf,
si es té en compte la lògica de l'última setmana, scanf pot fer el que vulgui
amb una còpia de x, però no va poder canviar permanentment x menys que donem
scanf un mapa del tresor, per així dir-ho, on x marca el lloc, per la qual cosa
passem a la direcció de x de manera que scanf pot anar-hi i en realitat el canvi
el valor de x.
I així, de fet, tot que aquest programa fa
si faig scanf 0, en la meva font Directori de 5m, fer scanf 0,
punt slash scanf, nombre si us plau 50, gràcies pel 50.
>> Així que no és tan interessant, però el que en veritat passa
és que tan aviat com em dic scanf aquí, el valor de x
s'està canviant de forma permanent.
Ara, això sembla agradable i bo, i de fet,
sembla que realment no necessitem la biblioteca CS50 en tots els més.
Per exemple, anem a córrer això una vegada més aquí.
Permetin-me tornar a obrir-lo per un segon.
Anem a tractar un nombre favor i en comptes de dir 50 com abans,
diguem que no.
OK, això és una mica estrany.
D'ACORD.
I només algunes tonteries aquí.
Per tant, no sembla manejar situacions errònies.
Així que hem de mínimament inici afegint una mica de comprovació d'errors
per assegurar-se que l'usuari té escrit en un nombre real com 50,
perquè les paraules aparentment mecanografia no es detecta com a problemàtic,
però probablement hauria de ser.
>> Fem una ullada a aquesta versió ara que és el meu intent de tornar a implementar GetString.
Si scanf té tot això funcionalitat incorporada,
¿Per què hem estat coquetejant amb ells rodes d'entrenament com GetString?
Bé, aquí és potser la meva pròpia versió simple de GetString
pel que fa una setmana, podria haver dit: dóna'm una cadena i en diuen memòria intermèdia.
Avui, vaig a començar just dient estrelles char, que, recordo,
és només sinònim.
Sembla més por però és exactament el mateix.
Així que em donen un buffer variable anomenada això va a emmagatzemar una cadena,
dir la cadena d'usuari si us plau, i després, igual que abans,
anem a tractar de demanar prestat aquesta lliçó scanf % S aquesta vegada i després passar a tampó.
Ara, una comprovació de validesa ràpid.
Per què no estic dient ampersand esmorteir aquesta vegada?
Deduir l'exemple anterior.
AUDIÈNCIA: Char estrelles és un punter.
DAVID Malan: Exactament, perquè aquesta vegada, char
estrelles ja és un punter, una adreça, per definició d'aquesta estrella ser-hi.
I si scanf espera una adreça, n'hi ha prou només per passar a tampó.
No necessito dir memòria intermèdia signe.
Per als curiosos, podria fer alguna cosa com això.
Hi hauria significat diferent.
Això li donaria un punter a un punter, que és en realitat
una cosa vàlida en C, però per ara, anem a mantenir simple
i mantenir la història consistent.
Jo només vaig a passar tampó i això és correcte.
El problema però és això.
Déjame anar endavant i executar aquest programa després de la compilació.
Fer scanf 1.
Maleïda sigui, el meu compilador de la captura del meu error.
Dóna'm un segon.
Clang.
Diguem scanf-1.c.
D'ACORD.
Cal anar.
Ho necessito.
Identificació CS50 té diversos paràmetres de configuració
que protegeixen contra tu mateix.
Necessitava desactivar les de corrent Clang manualment aquest moment.
Així cadena favor.
Vaig a seguir endavant i escriure en el meu món hola favorit.
OK, nul.
Això no és el que he escrit.
Així que és indicatiu de que alguna cosa va malament.
Déjame anar endavant i escric en una cadena molt llarga.
Gràcies per la nul·la i no sé si jo seré capaç de estavellar.
Intentarem una mica de còpia enganxar i veure si això ajuda.
Només has de enganxar un munt d'això.
És, definitivament, una més gran cadena del que és habitual.
Anem a realment escriure-ho.
No.
Maleït sigui.
No Mana trobat.
Així que això no relacionat.
Això és perquè em vaig enganxar alguns personatges dolents,
però això resulta que no funcionarà.
>> Intentarem una vegada més, perquè és més divertit si realment estavellar.
Anem escrigui això i ara, estic va copiar una cadena molt llarga
i ara anem a veure si ens pot xocar aquesta cosa.
Noti que vaig ometre espais i noves línies i punts i comes
i tots els personatges de funky.
Retorn.
I ara la xarxa només està sent lenta.
Vaig sostenir la tecla Comando-V massa temps, amb claredat.
Maleït sigui!
No Mana trobat.
>> D'ACORD.
Bé, el punt és no obstant, el següent.
Així que el que realment està passant en la present declaració
de tampó estrelles Char en la línia 16?
Així que Què si quan em declaro un punter?
Tot el que estic fent és un valor de quatre bytes anomenada buffer, però el que hi ha dins d'ella
en aquest moment?
És només un cert valor de les escombraries.
Perquè cada vegada que declara una variable en C, és només un valor d'escombraries,
i estem començant a viatge per aquesta realitat.
Ara, quan et dic scanf, anar a aquesta adreça
i posar el que l'usuari escriu.
Si l'usuari escriu en hola món, bé, ¿on ho poso?
Buffer és un valor de les escombraries.
>> Així que això és una mica com una fletxa això està assenyalant qui sap on.
Potser és que apunta aquí en la meva memòria.
I així, quan l'usuari tipus de hola món,
el programa tracta de posar el cadena hello world barra invertida 0
en aquesta part de la memòria.
No obstant això, amb alta probabilitat, però clarament no 100% de probabilitat,
l'equip es va a estavellar a continuació el programa perquè no es tracta
la memòria es em permetés tocar.
Així que en resum, aquest programa és viciat per exactament això.
Jo fonamentalment no estic fent què?
Quins passos he omès, igual que ometem amb el primer exemple de Binky?
Sí?
>> AUDIÈNCIA: assignació de memòria?
>> DAVID Malan: assignació de memòria.
En realitat no he assignat qualsevol memòria d'aquesta cadena.
Així que podem arreglar això en un parell de maneres.
Un, podem mantenir simple i de fet, ara estàs
va començar a veure un desdibuixament de les línies entre el
una matriu és, el que és una cadena, el que és un estrelles char és, el que és un conjunt de caràcters
és.
Heus aquí un segon exemple involucrant cordes i notificació
tot el que he fet en la línia 16 És a dir, en comptes de dir
aquest memòria intermèdia serà un char estrella, un punter a una part de la memòria,
Vaig a donar molt proactiva a mi mateix un tampó durant 16 caràcters,
i de fet, si vostè està familiaritzat amb el terme tampó,
probablement del món dels vídeos, on un vídeo és tampó, tampó,
buffering.
Bé, quin és la connexió aquí?
Bé, aquí a YouTube ia l'interior dels reproductors de vídeo
en general, és una matriu això és més gran que 16.
Pot ser que sigui una matriu de mida d'un megabyte, potser 10 megabytes,
i dins d'aquesta matriu fa el seu navegador descarregar un munt de bytes,
un munt de megabytes de vídeo i el reproductor de vídeo,
YouTube o qui és, comença la lectura dels bytes a partir d'aquest array,
i tota vegada que vegi la paraula tampó, tampó,
això vol dir que el jugador té arribat al final d'aquesta matriu.
La xarxa és tan lent que no té omplir la matriu amb més bytes
i pel que està fora de bits per mostrar a l'usuari.
>> Així memòria intermèdia és un terme adequat aquí en què és només una matriu, un tros de la memòria.
I això ho arreglarà perquè resulta que
que es pot tractar com si arrays són adreces, malgrat tampó
és només un símbol, és un seqüència de caràcters, tampó,
això és útil per a mi, el programador, vostè pot passar el seu nom voltant
com si es tractés d'una punter, com si
van ser la direcció d'un tros de la memòria de 16 caràcters.
Així que això és a dir, puc passar el scanf exactament aquesta paraula
i pel que ara, si faig aquest programa, fer scanf 2, punt slash scanf 2,
i el tipus de hola món, Enter, que temps--
>> Hmm, què va passar?
Cadena favor.
Què vaig fer malament?
Hola món, tampó.
Hola món.
Ah, ja sé el que està fent.
D'ACORD.
Així que ha llegint fins al primer espai.
Així que anem a enganyar per un moment i dic jo només volia escriure alguna cosa
molt llarga com aquesta és una frase llarga aquest és un, dos, tres, quatre, cinc,
sis, set, vuit, nou, 10, 11, 12, 13, 14, 15, 16.
D'ACORD.
De fet, és una llarga condemna.
Així que aquesta frase és més de 16 caràcters
i així quan vaig arribar a Enter, el que va a passar?
Bé, en aquest cas de la memòria intermèdia d'història, havia declarat
de ser en realitat un array amb 16 caràcters llest per anar.
Així que un, dos, tres, quatre, cinc, sis, set, vuit, nou, 10, 11, 12, 13, 14,
15, 16.
Així que 16 caràcters, i ara, quan llegit en alguna cosa com això és un llarg
frase, el que va a succeir és que llegiré en aquest és molt
S-E-N-T-E-N-C-E, sentencia.
>> Així que això és deliberadament una cosa dolenta que jo
seguir escrivint més enllà de la límits de la meva matriu,
més enllà dels límits de la meva memòria intermèdia.
Jo podria tenir sort i el programa mantindrà en marxa i no els importa,
però en termes generals, aquesta serà fet estavellar meu programa,
i és un error en el meu codificar el moment em passo
enllà dels límits d'aquesta matriu, perquè jo
no sé si és necessàriament va a estavellar
o si només tindré sort.
Així que això és problemàtic perquè en aquest cas, no sembla funcionar
i anem a temptar la sort aquí, tot i que l'IDE sembla tolerar una mica
de--
>> Cal anar.
Finalment.
Així que jo sóc l'únic que pot veure això.
Així que acabo de tenir un munt de diversió a escriure 01:00 frase real molt llarg
que sens dubte va superar 16 bytes, perquè jo
escrit en aquest llarg de diverses línies boig frase i, a continuació, donar-se compte del que va passar.
El programa va tractar d'imprimir- i després va obtenir una fallada de segmentació
i errors de segmentació és quan passa una cosa com això
i el sistema operatiu diu no, no pot tocar aquesta memòria.
Anem a matar el programa complet.
>> Així que això sembla problemàtic.
He millorat el programa mitjançant el qual almenys tenir una mica de memòria,
però això sembla confinar el GetString funció per aconseguir
cordes de certa extensió finita 16.
Així que si vols donar suport ja sentències de 16 caràcters,
Què fas?
Bé, es pot augmentar la mida d'aquest buffer per 32
o això sembla classe de curt.
Per què no simplement fer és 1000, però fer retrocedir.
Quina és la resposta intuïtiva de només evitar aquest problema fent
la meva memòria intermèdia més gran, com 1.000 caràcters?
Mitjançant la implementació d'GetString d'aquesta manera.
El que és bo o dolent aquí?
Sí?
AUDIÈNCIA: Si enllaça una gran quantitat de l'espai i no l'utilitza,
llavors no es pot reassignar aquest espai.
DAVID Malan: Per descomptat.
És un malbaratament mesura que si no ho fa realment necessita 900 d'aquests bytes
i no obstant això, vostè està demanant 1.000 en total, de totes maneres,
vostè està consumint més memòria l'ordinador de l'usuari que vostè necessita,
i després de tot, alguns ja has trobat
a la vida que quan estàs corrent un munt de programes
i estan menjant molta memòria, en realitat això pot afectar el rendiment
i l'experiència de l'usuari a l'ordinador.
Així que això és una mena de solució mandrós, amb certesa, i per contra,
que no només és un malbaratament, quin problema segueix sent, fins i tot si faig la meva memòria intermèdia
1000?
Sí?
>> AUDIÈNCIA: La cadena és la longitud de 1.001.
DAVID Malan: Exactament.
Si la cadena és la longitud de 1001, vostè té el mateix problema,
i amb el meu argument, ho faria just en aquest moment que sigui 2000,
però vostè no sap en avançar en el gran que ha de ser,
i, no obstant això, he de compilar el meu programa abans de deixar que la gent fa servir i descàrrega
ella.
Així que aquest és exactament el tipus de coses que els intents de la biblioteca CS50
per ajudar-nos amb i estarem només vista En algunes de la implementació subjacent
aquí, però això és CS50 dot C. Aquest és l'arxiu que ha estat en CS50 IDE
totes aquestes setmanes que ha estat utilitzant.
És pre-compilat i que ha estat utilitzant de forma automàtica
per la naturalesa de tenir el llançar-L bandera CS50 amb estrèpit,
però si em desplaço cap avall a través de tots aquestes funcions, aquí està GetString,
i només per donar-li un mostra del que està passant,
anem a fer una ullada ràpida a la relativa complexitat.
No és un super llarg funció, però no ho vam fer
cal pensar seriosament en tot com fer per aconseguir cadenes.
>> Així que aquí està la meva memòria intermèdia i jo aparentment inicialitzar a null.
Això, per descomptat, és el el mateix que l'estrella char,
però vaig decidir a l'aplicació de la biblioteca CS50
que si anem a ser completament dinàmic,
No sé per endavant el gran d'una usuaris de corda voldran aconseguir.
Així que vaig a començar amb només una cadena buida
i jo vaig a construir la major quantitat la memòria, ja que necessito per adaptar-se a la cadena d'usuari
i si no tinc suficient, vaig a preguntar
el sistema operatiu per a més memòria.
Vaig a moure la seva cadena en un tros més gran de la memòria
i jo vaig a deixar anar o alliberar el insuficientment gran part de la memòria
i només anem per fer això de forma iterativa.
>> Així que una ràpida mirada, aquí és només una variable
amb la qual em vaig a portar un registre de la capacitat del meu buffer.
Quants bytes puc encaixar?
Aquí hi ha una variable n amb que jo seguiré
un registre de quants bytes són realment en el tampó o que l'usuari ha escrit.
Si no has vist això abans, Podeu especificar que una variable com un int
no està signat, que com el seu nom indica, vol dir que és no negatiu, i per què ho faria
Jo mai vull molestar especificant que un int no és només un int,
però és un int sense signar?
És un int no negatiu.
Què fa el [inaudible] vol dir?
>> AUDIÈNCIA: Es descriu una quantitat de memòria que pot ser [inaudible].
>> DAVID Malan: Sí.
Així que si dic sense signar, això és en realitat donant-li un bit de memòria addicional
i sembla una mica tonto, però si tenen un bit de memòria addicional, que
vol dir que té dues vegades més valors que pot representar,
perquè pot ser un 0 o 1 gen.
Així que per defecte, un int pot ser més o menys negatiu de 2 mil milions fins al final
fins positiu 2000000000.
Aquests són grans rangs, però és encara tipus de deixalla
si només es preocupen per mides, que acaba de forma intuïtiva
ha de ser no negatiu o positiu o 0, doncs bé,
¿Per què estàs perdent 2000000000 possibles valors per als nombres negatius
si mai vas a usar-los?
Així dient sense signar, ara la meva int pot estar entre 0 i aproximadament 4 mil milions.
>> Així que aquí és simplement un int C per raons no entrarem en un moment com
a això que és un int en lloc d'un char, però aquí és
l'essència del que està passant endavant, i alguns de vostès
podria estar fent servir, per exemple, el funció fgetc fins i tot en PSet de quatre
oa partir de llavors, ja veurem que de nou en un problema conjunt de cinc,
fgetc és agradable perquè com el seu nom classe de, classe de arcanamente suggereix,
és una funció que aconsegueix un personatge i així,
el que és fonamentalment diferent sobre el que estem fent en GetString
és que no estem utilitzant scanf de la mateixa manera.
Només estem arrossegant al llarg pas a pas més del que l'usuari ha premut,
perquè sempre podem assignar un sol tar, de manera que sempre es pot de manera segura
mirar 1 carbó a la vegada, i la màgia comença a succeir aquí.
Vaig a desplaçar-se cap avall per el mitjà d'aquesta funció
només per presentar breument aquesta funció.
Igual que hi ha un funció malloc, hi ha
una funció realloc on realloc li permet reassignar una part de la memòria
i fer-lo més gran o més petit.
En tant conte i amb una ona de la meva mà per avui,
saber que el GetString està fent és que és una espècie
de l'art de màgia de créixer o la reducció de la memòria intermèdia com l'usuari
tipus en la seva cadena.
>> Així que si l'usuari escriu una cadena curta, aquest codi
només s'assigna suficient memòria per adaptar-se a la cadena.
Si l'usuari manté la tipificació com ho vaig fer una vegada i una altra
i una altra vegada, bé, si el memòria intermèdia d'un principi tan gran
i el programa es dóna compte, a Espera un minut, estic fora de l'espai,
que va a duplicar la mida de la memòria intermèdia
i després doblegar la mida de la memòria intermèdia i el codi que fa la duplicació,
si mirem des d'aquí, és només per aquesta intel·ligent d'una sola línia.
És possible que no hagi vist aquesta sintaxi abans, però si dius estrelles és igual,
aquest és el mateix que dient temps capacitat febrer.
Per tant, només segueix duplicant la capacitat de la memòria intermèdia
i després explicant realloc per donar sí que molt més memòria.
>> Ara, com un a part, hi ha són altres funcions en aquí
que no anem a mirar detall a part de mostrar a getInt,
fem servir GetString en getInt.
Comprovem que no és null, que, recordo,
és el valor especial que significa alguna cosa va sortir malament.
Estem fora de la memòria.
Millor comprovar això.
I tornem un valor sentinella.
Però et remeto als comentaris pel que fa a per què i després fem servir aquest cosí de scanf
diu sscanf i resulta que scanf sscanf, o cadena,
li permet fer una ullada a la línia que l'usuari ha escrit i et deixa
analitzar-essencial i el que estic fent aquí és que estic dient sscanf,
analitzar el que l'usuari té escrit en i assegureu-vos de% i,
no és un nombre sencer a ella, i no ho farem entrar a l'actualitat exactament per què també hi ha
1% c aquí, però que en poques paraules permet ens permet detectar si l'usuari ha escrit
en alguna cosa fals després del número.
Així que la raó per la qual getInt i GetString dir-li a reintentar, reintentar, torni a intentar
és perquè de tots que el codi que hem escrit,
És una espècie de mirar a l'entrada de l'usuari en assegurar-se que és totalment numèric
o es tracta d'un flotant real valor de punts o similar,
depenent de quin valor funció que utilitzeu.
>> Sort.
D'ACORD.
Això va ser un mos però el punt aquí és
que la raó per la que vam tenir aquestes rodes de capacitació sobre
és perquè en el nivell més baix, hi ha tantes coses que
pot sortir malament que volíem per a manejar de forma preventiva
aquestes coses certament en el primeres setmanes de la classe,
però ara amb PSet 04:05 i PSet allà va a veure que és més fins
vostè, però també ets més capaç de resoldre aquest tipus de problemes
vostè mateix.
Teniu alguna pregunta respecte GetString o getInt?
Sí?
>> AUDIÈNCIA: Per què el doble la capacitat de la memòria intermèdia
en comptes de augmentar per la quantitat exacta?
>> DAVID Malan: Bona pregunta.
Per què hauríem de duplicar la capacitat de la memòria intermèdia en oposició
només augmentar- per algun valor constant?
Va ser una decisió de disseny.
Ens vam decidir que ja que tendeix a ser una mica car pel que fa a temps de demanar
el sistema operatiu per a la memòria, no ho vam fer
vol acabar ficant una situació per a les cadenes grans
que estàvem demanant el OS i una altra vegada
i una altra vegada i una altra en successió ràpida per a la memòria.
Així que vam decidir, una cosa arbitràriament però esperem raonablement,
que, ja saps què, anem a tractar de tirar endavant de nosaltres mateixos
i simplement seguir doblant de manera que minimitzem la quantitat de vegades
hem de trucar a malloc o realloc, però una fallada total de
trucar a falta de saber el que els usuaris podrien voler escriure.
Les dues formes poden ser discutibles.
Es podria dir que bona.
>> Així que anem a fer una ullada a un parell d'altres efectes secundaris de la memòria,
coses que poden sortir malament i eines que pot
utilitzar per capturar aquest tipus d'errors.
Resulta que tots vostès, tot i que check50 no li ha dit tant,
s'han escrit amb errors codi des de la setmana un,
fins i tot si totes les proves són check50 passava, i fins i tot si vostè i el seu TF
són super segurs que el codi funciona com està previst.
El codi ha estat buggy o viciat en què tots vostès,
en l'ús de la biblioteca CS50, han estat pèrdues de memòria.
Vostè ha estat demanant el sistema operatiu per la memòria en la majoria dels programes
vostè ha escrit, però tens En realitat mai donada volta.
Vostè ha cridat GetString i getInt i GetFloat,
però amb GetString, tens Mai anomenada unGetString o Donar
Posterior de la seqüència o similars, però hem vist GetString que fa assignar memòria
per mitjà de malloc o aquest realloc funció, que és només
molt similar en esperit, i, no obstant això, hem estat
preguntar al sistema operatiu per la memòria i la memòria una i altra vegada
però mai donar-li l'esquena.
>> Ara, com un a part, resulta que quan un programa es tanca, tota la memòria
s'allibera automàticament.
Així que no ha estat un gran negoci.
No va a trencar el IDE o coses més a poc a poc,
Però quan els programes fan generalment perdre memòria
i s'estan executant durant molt de temps.
Si alguna vegada has vist la petita estúpida pilota de platja en Mac OS o el rellotge de sorra
en Windows, on és una espècie de l'alentiment o el pensament o el pensament
o realment comença per frenar un rastreig,
molt possiblement podria ser el resultat d'una pèrdua de memòria.
Els programadors que van escriure el programari que utilitzeu
demanar al sistema operatiu per a la memòria cada pocs minuts, cada hora.
Però si s'està executant la programari, fins i tot si és
minimitzat en el seu ordinador per hores o dies i dies,
es pot preguntar per més i més la memòria i la realitat mai usar-lo
i pel que el seu codi podria ser, o programes podrien tenir fuites de memòria,
i si vostè comença a perdre memòria, hi ha menys memòria per a altres programes,
i l'efecte és frenar tot.
>> Ara, això és, de lluny, un els programes més atroços
vostè tindrà l'oportunitat per funcionar en la mesura CS50
com la seva sortida és encara més esotèric que so metàl·lic d'o fer d'o qualsevol de les comandes
programes de línia ens hem quedat abans, però afortunadament, incrustat en la seva sortida
és alguns consells molt útils que serà útil tant per PSet de quatre
o segurament PConfigure 05:00.
Així valgrind és una eina que es pot utilitzar per buscar
que no hi hagi fuites de memòria en el seu programa.
És relativament fàcil d'executar.
Executa valgrind i després, fins i tot encara que és una mica prolix,
tauler comprovació de fuites tauler iguals per complet, i després puntejar
tala i el nom del seu programa.
Així valgrind llavors executar el programa i al final del seu programa
corrent abans que tanca i li dóna un altre avís,
que va a analitzar la seva programa mentre s'ha estat corrent
i dius que has de tenir fuites qualsevol memòria i millor encara,
vas tocar memòria que no pertanyen a vostè?
No pot agafar tot, però és bastant bo en la captura de la majoria de les coses.
>> Així que aquí està un exemple de la meva haver corregut aquest programa, que té termini valgrind,
en un programa anomenat memòria, i em vaig
per ressaltar les línies que són en última instància, d'interès per a nosaltres.
Així que fins i tot hi més distraccions que he eliminat de la diapositiva.
Però anem a veure el que aquest programa és capaç de dir-nos.
És capaç de dir-nos coses com escriptura no vàlida de mida 4.
En altres paraules, si es toca la memòria, específicament 4 bytes de memòria
que vostè no ha de tenir, valgrind li pot dir això.
Escriptura no vàlida de mida 4.
Vas tocar quatre octets que no hauria de tenir.
On es fa això?
Aquesta és la bellesa.
La línia de punts c Memòria 21 és on es fotut i és per això que és útil.
Igual que l'BGF, pot ajudar assenyalar en l'error real.
>> Ara, aquest és una mica més detallat, si no confús.
40 Bytes 1 blocs són definitivament perdut en el registre de la pèrdua gener 1.
Què vol dir això?
Bé, només dir que vostè va demanar 40 bytes i mai es va donar volta.
Vostè va cridar malloc o cridar GetString i el sistema operatiu
que 40 bytes, però mai es va donar alliberat o alliberada aquesta memòria,
i per ser justos, mai hem mostrem com tornes la memòria.
Resulta que hi ha un súper funció simple trucada gratuïta.
Pren un argument, la cosa desitja alliberar o donar volta,
però 40 bytes, pel que es veu, en aquest programa
s'han perdut en la línia 20 de la memòria dot c.
>> Així que anem a veure aquest programa.
És super inútil.
Només demostra aquest error en particular.
Així que anem a fer una ullada.
Heus aquí els principals i principals, avís, trucades una funció anomenada torna f tant.
Així que no és tan interessant.
Què fer f?
Noti que no es va molestar amb un prototip.
Volia mantenir el codi el mínim possible.
Així que vaig posar f anterior principal i això està bé, sens dubte,
per a programes curts com aquest.
Així que f no torna res i fa No prengui res, però que sí que fa això.
Declara, igual que en l'exemple de Binky,
un punter anomenat X que va per emmagatzemar la direcció d'un int.
Així que aquest és el costat esquerre.
En Anglès, quin és la costat dret fent?
Qualsevol persona?
Què és aquest fent per nosaltres?
Sí?
>> AUDIÈNCIA: [inaudible] vegades la mida d'un int
que és 10 vegades més gran que [inaudible]
DAVID Malan: Bé i permetin-me resumir.
Així assignar prou espai per a 10 enters o 10, quin és la mida d'un int,
és quatre bytes, de manera que 10 vegades 4 és 40, de manera que a mà dreta que tinc
ressaltat és donar-me 40 bytes i emmagatzemar la direcció del primer byte
en x.
I ara, finalment, i aquí és on aquest programa està lliure d'errors, el que és
malament amb la línia 21 basa en què la lògica?
Què hi ha de dolent en la línia 21?
Sí?
AUDIÈNCIA: No pot índex en x [inaudible].
DAVID Malan: Sí.
Que no hauria índex en x l'estil.
Així sintàcticament, això està bé.
El millor és, igual que pot tractar el nom d'una matriu
com si fos un punter, de manera similar pot tractar a un punter com si fos
una matriu, i així puc sintàcticament dir x suport d'alguna cosa, x suport de i,
però el 10 és problemàtica.
Per què?
>> AUDIÈNCIA: Com que no hi ha dins.
>> DAVID Malan: No és dins d'aquesta part de la memòria.
Què és el valor més gran que ha estar posant en aquests claudàtors?
9, del 0 al 9.
A causa de zero d'indexació.
Així que de 0 a 9 estaria bé.
Suport de 10 no és bo i però, recordar, però, cada vegada que
Em sembla que tractar de fer CS50 IDE accident escrivint en valors falsos,
no sempre coopera, i, de fet, sovint
tenir sort només perquè el sistema operatiu no
adonar que molt lleugerament passar algun tros de la memòria,
perquè vostè es va quedar dins tècnicament seu segment, però més sobre això
en una classe de sistemes operatius, i així alguna cosa com això
podria molt fàcilment passar desapercebuda.
El seu programa mai va a estavellar consistentment però potser en una estona.
>> I així anem a tractar valgrind en això, i aquí està
on arribarem aclaparat per la sortida momentàniament.
Així que la memòria de verificació de fuites valgrind és igual a la memòria barra de punts completa.
I vet aquí per què t'ho prometo això podria aclaparar.
Això és el que valgrind, això és el un programador, alguns anys-
va decidir que seria una bona idea per a la sortida a semblar.
Així que farem sentit d'això.
Així que tot el camí a l'esquerra costat per cap bona raó
és l'ID de procés del programa acabem de córrer, l'identificador únic
per al programa que acabem d'vam córrer.
Hem suprimit que des la diapositiva, però hi ha
hi ha alguna informació útil aquí.
>> Anem a desplaçar-se fins la part superior.
Aquí és on vam començar.
Així que no és tot el que molt de sortida.
Aquí cal escriure invàlida de mida 4 a la línia 21.
Bé, quin va ser la línia 21?
Línia 21 era exactament això i que té sentit
que estic en forma vàlida escriure 4 bytes perquè sóc
tractant de posar aquest sencer, que podria ser qualsevol cosa,
que només passa a ser zero, però estic intentant
per posar-lo en un lloc que no pertany a mi.
D'altra banda, aquí baix, 40 bytes en un blocs estan definitivament perduts en l'expedient 1.
Això és perquè quan dic malloc aquí, jo en realitat mai alliberar la memòria.
>> Llavors, com podem solucionar aquest problema?
Déjame anar per davant i ser una mica més segur i fer 9 allà i em va deixar aquí gratis x.
Aquesta és la nova funció per avui.
Si ara em torneu a executar fer slash dot memòria, anem a córrer valgrind en ell de nou,
maximitzar la finestra i premeu Enter.
Ara, és bo.
Enterren les bones notícies en tot això de sortida.
Tots els blocs de munt eren lliures.
Tornarem al que el munt és, però no hi ha fuites són possibles.
Així que això és només una altra eina per a la seva caixa d'eines
amb el qual es pot començar a troba ara els errors així.
>> Però anem a veure què més pot sortir malament aquí.
De transició Anem ara a en realitat la solució d'un problema.
Com acotació al marge, si això va a alleujar una mica de confusió o de tensió,
això és ara divertit.
Sí.
Això és bastant bo.
A causa que els punters són adreces i direccions
generalment són per convenció escrit amb hexadecimal.
Ha, ha, això és graciós ara.
De totes maneres, així que anem ara realment resoldre un problema.
Aquest ha estat fantàstic, súper baix nivell fins al moment,
i que en realitat podem fer útil coses amb aquests detalls de baix nivell.
>> Així que hem introduït unes setmanes Fa la noció d'una matriu.
Un arsenal era agradable, perquè és difícil de netejar el nostre codi
perquè si volíem escriure una programa amb múltiples estudiants
o múltiples noms i cases i residències i col·legis i tot això,
podríem emmagatzemar tot més netament dins d'una matriu.
Però proposar un desavantatge d'una matriu fins al moment.
Fins i tot si no has patit tu mateix en un programa, simplement per instint,
el que és una mala cosa sobre una matriu, potser?
Sento alguns murmuris.
AUDIÈNCIA: És difícil per canviar la mida.
DAVID Malan: És difícil per canviar la mida.
No es pot canviar la mida d'una matriu, de fet, per se
en C. Podeu assignar una altra matriu, moure tot, des de l'anterior
en el nou, i ara tenir una mica més d'espai,
però no és com un llenguatge com Java o Python
o qualsevol nombre d'una altra llengües amb què alguns de vostès
podria ser familiar on pot simplement seguir afegint coses
fins a la sacietat fins al final d'una matriu.
Quan vostè té una sèrie de mida 6, que és la seva grandària,
i tan semblant a la idea anterior que té un buffer d'una certa mida,
has d'endevinar fora de la porta quina mida és el que vols que sigui?
Si endevina massa gran, perds espai.
Si endevina massa petit, no pot emmagatzemar dades que, almenys
i sense molta feina.
>> Així que avui, gràcies als punters, podem començar unint la nostra pròpia duana
estructures de dades, i en De fet, aquí és una cosa
que es veu una mica més críptica a primera vista,
però això és el que anomenarem 1 lligat llista, i el seu nom tipus d'resumeix
ella.
És una llista de nombres, o en aquest cas, una llista de nombres,
però podria ser una llista de qualsevol cosa, però està vinculat entre si per mitjà de fletxes,
i acaba de prendre una conjectura amb quina tècnica
serem capaços de per cosir junts,
una mena de crispetes de blat de moro amb un fil, una de vinculada llistes rectangles aquí?
Els seus números?
Quina és la característica del llenguatge subjacent?
>> AUDIÈNCIA: Un punter.
>> DAVID Malan: Un punter.
Així que cadascuna d'aquestes fletxes representa aquí un punter o simplement una direcció.
En altres paraules, si vull per emmagatzemar una llista de nombres,
No puc guardar si vull la capacitat de créixer i encongir
la meva estructura de dades en una matriu.
Així que he de tenir una mica de més sofisticació,
de notar que aquesta foto tipus de suggereix
que si vostè acaba d'aconseguir petits fils connectar tot junt,
probablement no és tan difícil de fer espai entre dos dels rectangles
o dos d'aquests nodes, ja que començarem cridant, posar en un nou node,
i després amb una mica de fil nou, just desfer-se dels tres nodes junts,
el primer, l'últim, i el que acaba d'inserir en el medi.
>> I de fet una llista enllaçada, a diferència d'una matriu, és dinàmic.
Pot créixer i pot s'encongeixen i no ho fa
ha de saber o tenir cura per endavant com quantitat de dades que seran l'emmagatzematge,
però resulta que hem de ser una mica cura sobre com implementar això.
Així que primer anem a considerar com implementem un d'aquests petits rectangles.
És fàcil d'implementar un int.
Vostè acaba de dir int n i després vostè aconsegueix 4 bytes per a un int,
però com puc obtenir un int, dir-n, i després un punter, anem a cridar següent.
Podríem cridar a aquests coses el que vulguem
però necessito una estructura de dades personalitzat.
Sí?
>> AUDIÈNCIA: Ampersand [inaudible].
>> DAVID Malan: Així signe que utilitzarem per obtenir l'adreça d'un node potencialment.
Però necessitem un altre funció de C per tal
que em donés la possibilitat de crear aquest rectangle costum, aquest costum
variable si es vol, en la memòria.
AUDIÈNCIA: Una estructura.
DAVID Malan: Una estructura.
Recordem que la setmana passada, vam introduir estructura, aquesta paraula clau relativament simple
que ens permet fer coses com aquesta.
C no va venir amb una dada estructura anomenada estudiantil.
Ve amb int i float i carbó i tals, però no ve amb els estudiants,
però podem crear un tipus de dades dels estudiants, una estructura d'estudiant, amb aquesta sintaxi
aquí.
I veuràs això una i altra vegada.
Així que no et preocupis per memoritzant les paraules clau,
però la paraula clau que és important és només el fet que hem dit struct
i després en diem estudiant ia l'interior l'estudiant era un nom i una casa
o una residència d'estudiants o similars.
>> I el que ara avui, proposarem això.
He afegit algunes paraules, però si vull per implementar aquest rectangle que és
té tant un int i un punter, saps què, jo sóc
va a declarar una estructura anomenada node.
Sóc també, dins d'ella, dirà que un node, aquest rectangle, té un int
i ho anem a cridar ni té un següent punter.
I això és una mica prolix, però si es pensa en això,
les fletxes que es trobaven a la imatge Fa un moment són de quin tipus de dades?
On cada un d'aquests fletxes està apuntant a quin tipus d'estructura de dades?
No és simplement apuntant a un int per se.
S'apunta a la El rectangular sencera
i aquesta cosa rectangular, hem dit, es diu un node.
I així quin tipus d'haver de recursivament definir estatals
que un node, direm, contindrà un int anomenada n
i un punter anomenat següent i el tipus d'estructura de dades a la qual
que els punts de punter és aparentment serà node d'estructura.
>> Així que això és molest detallat i acaba de ser pedant,
la raó per la qual no podem només dir això, que francament
sembla molt més fàcil de llegir, s'ha de recordar que C llegir
coses de dalt a baix, d'esquerra a dreta.
No és fins que tinguem el punt i coma que en realitat hi ha el node de paraules clau.
Així que si volem tenir aquest tipus de referència cíclica dins de les dades
estructura, hem de fer això, on diem node d'estructura en la part superior, el que
ens dóna una manera de descriure això ja cosa, llavors dins diem node d'estructura,
i després en l'última línia diem, tot dret, C, per cert,
simplement truqui a tota aquesta maleïda cosa que un node i detenir
usant la paraula clau struct per complet.
Així que això és només una espècie d'una sintàctica truc que en última instància ens permet crear
cosa que es veu exactament com aquesta.
>> Així que si suposem ara que podem implementar aquesta cosa en C,
com fer que en realitat començar a travessar això?
Bé, de fet, tot el que hem de fer és repetir d'esquerra a dreta i just
tipus d'inserir nodes o eliminar nodes o buscar coses on vulguem,
però per fer això, seguirem endavant i fer les coses una mica més real perquè aquest
ha estat molt baix nivell fins al moment.
A algú li agrada, literalment, ser el primer?
D'ACORD.
Anem cap amunt.
Com et dius?
>> DAVID: David.
DAVID Malan: David.
Encantat de conéixer-te.
Jo també.
Tot bé.
I necessitem un número 9.
No és tan bona com la primera, potser.
OK, número 9.
Un nombre 17, per favor.
Permetin-me tornar una mica més lluny.
Número 22, per favor, i ¿Què hi ha de més enrere
si puc veure cap mà amb tota la llum o no.
Algú es va oferir allà mateix.
Vols venir?
El seu avantbraç va per la força cap amunt.
OK, 17.
22.
26 s'ensorra.
A algú més que vulgui forcefully-- Anem cap amunt.
Un voluntari real.
>> Així que molt ràpidament, si vostès podrien arreglar
Igual que vostès mateixos els nodes a la pantalla.
Gràcies.
I podràs 26.
Totes les presentacions adequades i ràpides.
Així que sóc David i tu també?
DAVID: David.
DAVID Malan: ¿I vostè és?
JAKE: Jake.
SUE: Sue.
ALEX: Alex.
RAPHAEL: Raphael.
TAYLOR: Taylor.
DAVID Malan: Taylor.
Excel·lent.
Així que aquests són els nostres voluntaris per avui i seguir endavant
i canviar una mica d'aquesta manera, i només seguir endavant i mantenir
la celebració dels seus números com vostè o el seu primer signe i l'ús de la mà esquerra,
seguir endavant i simplement aplicar aquestes fletxes, simplement
de manera que la mà esquerra és, literalment, apuntant al que sigui, ha d'introduir
a, i donar-li una mica d'espai perquè podem veure visualment els braços realitat
apuntant, i només pot apuntar tipus de a la planta està molt bé.
>> Així que aquí tenim una llista enllaçada d'un, dos, tres, quatre, cinc nodes inicialment,
i noti que tenim aquest especial punter al principi qui és
clau perquè hem de seguir la pista de la llista de longitud sencera d'alguna manera.
Aquests nois, tot i que un es queda a dreta, esquena amb esquena a la memòria,
que en realitat pot estar en qualsevol lloc en la memòria de l'ordinador.
Així que aquests nois podrien ser de peu en qualsevol lloc a l'escenari
i això està bé, sempre que estiguin realment apuntant l'un a l'altre,
però per mantenir les coses net i senzill, anem a
simplement dibuixar d'esquerra a dreta com això, però podria haver bretxes massives
entre aquests nodes.
>> Ara, si vull inserir en realitat alguns nou valor, seguirem endavant i fer això.
Tenim una oportunitat ara triar un altre node.
Dir que començarem amb mallocing 55.
Algú faria res ser malloc?
OK, anem cap amunt.
Com et dius?
ARC DE SANT MARTÍ: Arc de Sant Martí.
DAVID Malan: Arc de Sant Martí?
Tot bé.
Rainbow malloc.
Anem cap amunt.
Així que ara hem de preguntar-nos a nosaltres mateixos algorítmicament on podem posar 55.
Així que tots sabem, Òbviament, en la qual, probablement,
pertany, si estem tractant per mantenir aquest ordenades
i si vostès podrien prendre 1 un pas enrere perquè no caiguin
l'escenari, que seria genial.
Així que en realitat, arc de Sant Martí, començar de nou aquí amb mi,
perquè com l'equip ara pot només veuen una variable alhora.
Així que si aquest és el primer node.
Recordeu que no és un node, ell és només un indicador,
i és per això que ha dibuixat per ser només la mida d'un punter, no
un d'aquests rectangles complets.
Així que anem a comprovar en cada iteració és 55 menys de 9?
No.
És 55 de menys de 17?
No.
Menys de 22?
Menys de 26?
Menys de 34?
I així és, òbviament, Rainbow pertany al final.
Així que per ser clars, i què era el seu nom, Taylor?
>> TAYLOR: Taylor.
DAVID Malan: Així que entre Taylor mà esquerra i les mans de l'arc de Sant Martí aquí,
la mà ha d'apuntar al que en Per inserir 55 en aquesta llista?
Què necessitem fer?
Sí?
>> AUDIÈNCIA: la mà de Taylor cal assenyalar esquerra.
>> DAVID Malan: Exactament.
Així la inserció d'un node al final de la llista
és bastant simple perquè Taylor acaba ha d'assenyalar, en lloc de a terra
o l'anomenarem nul, nul·la és una espècie d'absència
d'un punter o una especial punter zero, ets
va assenyalar amb la seva esquerra la mà al Rainbow i després de l'arc de Sant Martí,
on deu el seu esquerra Probablement mà punt?
De Down.
No és bo si la mà és una espècie d'assenyalar fora d'aquí o de qualsevol tipus
quin camí.
Això seria considerat un valor d'escombraries,
però si ella apunta algun valor conegut, anem a
cridar zero o nul·la, això està bé perquè tenim un terme en aquest
i sabem que la llista ja està complet.
>> Llavors, quina altra cas relativament simple?
Podríem malloc 5?
Anem cap amunt.
Com et dius?
TIFFANY: Tiffany.
DAVID Malan: Ho sento?
TIFFANY: Tiffany.
DAVID Malan: Tiffany.
Tot bé.
Tiffany ha estat malloced amb el valor 5.
Anem cap amunt.
Aquest és relativament fàcil també, però considerarem l'ordre d'operacions ara.
Era bastant fàcil amb Taylor a l'extrem.
Número 5 és, per descomptat, menys de 9, i per això tenim a David, tenim Tiffany,
i quin era el seu nom?
>> JAKE: Jake.
>> DAVID Malan: Jake.
Tiffany, Jake, i David.
La mà del qual s'ha d'actualitzar primer?
Què vols fer aquí?
Hi ha possibles formes en que un parell, però també hi ha una o més formes equivocades.
>> AUDIÈNCIA: Comenceu amb l'extrem esquerre.
>> DAVID Malan: Comenceu amb l'extrem esquerre.
Qui és el més a l'esquerra aquí, doncs?
AUDIÈNCIA: Primer.
>> DAVID Malan: OK.
Així que comença amb la primera i on fer voleu actualitzar les mans de David per a ser?
AUDIÈNCIA: Cap al maig.
DAVID Malan: OK.
Així que David, a les cinc en punt o Tiffany aquí i ara?
>> AUDIÈNCIA: Tiffany apunta al 9?
DAVID Malan: Perfecte, excepte Binky de cap només una mica va caure, oi?
Perquè el que té de dolent aquesta imatge literalment?
AUDIÈNCIA: Res està apuntant.
DAVID Malan: Res és assenyalant a Jake ara.
Literalment Hem orfes setembre i 17, i hem literalment
filtrat tota aquesta memòria, perquè per actualització de la mà de David primer, això és
bé en la mesura que és correcta assenyalant en Tiffany ara,
però si ningú va tenir la previsió per apuntar a Jake,
llavors hem perdut la totalitat d'aquesta llista.
Així que anem a desfer.
Així que va ser una bona cosa per ensopegar però anem a corregir ara.
Què hem de fer primer el seu lloc?
Sí?
>> AUDIÈNCIA: Tiffany ha d'apuntar al 9?
DAVID Malan: No puc aconseguir que a prop seu.
Qui ha d'apuntar al 9?
>> AUDIÈNCIA: Tiffany.
>> DAVID Malan: D'acord.
Així Tiffany haurien primer punt en el 9.
Així Tiffany ha de prendre en un valor idèntic
David, el que sembla redundant per un moment,
però això està bé, perquè ara, segon pas, podem actualitzar la mà de David
assenyalar amb diamants, i després, si nosaltres, només una mica de netejar les coses
com si això és una espècie de primaveral, ara que és una inserció correcta.
Així excel·lent.
Així que ara ja gairebé estem allà.
Anem a inserir un últim valor com el valor 20.
Si poguéssim malloc un voluntari final?
Anem cap amunt.
Així que aquest és una mica més complicat.
Però en realitat, el codi som escriure, encara que verbalment,
és com tenir un munt si les condicions d'ara, oi?
Vam tenir una condició comprovar si pertany
al final, potser el principi.
Necessitem algun tipus de llaç per trobar el punt en el centre.
Així que anem a fer això amb el que és el seu nom?
>> ERIC: Eric.
>> DAVID Malan: Eric?
Eric.
Encantat de conéixer-te.
Així que tenim 20.
Menys de cinc?
No.
Menys de nou?
No.
Menys de 17?
No.
D'ACORD.
Ell pertany aquí i els seus noms són de nou?
SUE: Sue.
DAVID Malan: Sue.
ALEX: Alex.
DAVID Malan: Sue, Alex, i?
ERIC: Eric.
DAVID Malan: Eric.
Que les seves mans han d'actualitzar-primer?
>> AUDIÈNCIA: Eric.
D'ACORD.
Així que Eric hauria d'apuntar a on?
Als 22 anys.
Bé.
I ara què segueix?
Sue llavors pot apuntar a Eric i ara, si vostès només
fer una mica d'espai, la qual cosa està bé visualment, ara que hem fet de la inserció.
Així que considerarem ara una pregunta, però moltes gràcies als nostres voluntaris.
Molt ben fet.
Vostè pot mantenir aquests, si ho desitja.
I tenim un regal de comiat encantador si que li agrada cadascun per prendre una pilota anti-estrès.
Permetin-me passar això.
Llavors, què és el menjar per emportar de tot això?
Això sembla ser increïble en la mesura que tenim ara
introduït una alternativa a una matriu que no està tan limitat
a una matriu d'una certa mida fixa.
Poden créixer dinàmicament.
>> Però igual que hem vist en setmanes passat, que mai va aconseguir res de forma gratuïta,
com segurament hi ha un trade-off aquí.
Així, amb una alça d'un lligat llista, és aquest dinamisme?
Aquesta capacitat de créixer i, francament, podríem haver fet d'eliminació
i podríem reduir, segons sigui necessari.
Quin preu estem pagant?
El doble d'espai, en primer lloc.
Si ens fixem en la imatge, ja no estic emmagatzemant una llista d'enters.
Estic emmagatzemar una llista de sencers més punters.
Així que estic duplicant la quantitat d'espai.
Ara, potser això no és tal una gran cosa 4 bytes, 8 bytes,
però sens dubte podria afegir per a grans conjunts de dades.
Quin és altra desavantatge?
Sí?
>> AUDIÈNCIA: Hem de travessar ells un per un.
DAVID Malan: Sí.
Hem de travessar ells un per un.
Saps què, ens vam donar per vençuts aquesta super pràctica funció de claudàtors
notació, més pròpiament coneguda com accés aleatori,
en el qual només podem saltar a un element individual
però ara si encara tenia els meus voluntaris aquí,
si volia trobar la número 22, no puc simplement
saltar al suport d'alguna cosa d'alguna cosa.
He de mirar per sobre de la llista, i molt com els nostres exemples de cerca de manera lineal,
per trobar el nombre 22.
Així que sembla que hem pagat un preu allà.
Però podem, però, resoldre altres problemes.
>> De fet, permetin-me presentar només un parell d'imatges.
Així que si vostè ha estat fins De Mather Dining Hall recentment,
vostè recordarà que el seu piles de safates d'aquest tipus,
demanem prestat aquests de Annenberg abans de la classe.
Així que aquesta pila de safates, però, és representativa realitat
d'una estructura de dades informàtica.
Hi ha una estructura de dades en ciències de la computació
conegut com una pila que molt bé es presta a exactament això visual.
Així que si cadascuna d'aquestes safates no és una Safata però igual que un nombre i que volia
per emmagatzemar nombres, podria posar un fins aquí,
i vaig poder posar un altre aquí baix, i continuar apilament números
a la part superior un de l'altre, i el que és potencialment útil sobre aquest
és que el que és la implicació d'aquesta estructura de dades?
Quin nombre puc treure primer més convenient?
El més recent es va ficar allà.
>> Així que això és el que anomenaríem en ciències de la computació una estructura de dades LIFO.
Últim a entrar, primer en sortir.
I veurem en poc temps per què que podria ser útil, però per ara,
n'hi ha prou amb considerar la propietat.
I és una mica estúpid si vostè pensa sobre com el menjador fa.
Cada vegada que les safates netes i posar els més frescos a la part superior,
vostè podria tenir una que ja s'hagi neta però amb el temps molt brut i polsegós
la safata a la part inferior si en realitat mai
arribar al fons d'aquesta pila, ja que acaba de
seguir posant el nou i els nets a la part superior de la mateixa.
El mateix podria succeir en un supermercat també.
Si vostè té una vitrina de llet i cada vegada CVS
o qui obté més llet, que acaba empeny les llets
ja té a l'esquena i posar els nous a la davantera,
vostè va a tenir alguns bastant desagradable llet a l'extrem de l'estructura de dades,
perquè sempre a la part inferior o equivalentment sempre a la part posterior.
>> Però hi ha una altra manera de pensar alineant les dades i, per exemple, aquesta.
Si ets una d'aquestes persones que li agrada per alinear les afores de les botigues d'Apple
quan arriba un nou producte a terme, és probable que
no s'utilitza un dades de la pila estructura perquè
allunyaria a tots els altres que és fent cua per comprar una nova joguina.
Més aviat, és probable que estiguis usant quin tipus d'estructura de dades
o quin tipus de sistema en el món real?
Esperem que sigui una línia, o més adequadament o més britànic-com, una cua.
I resulta que una cua és també un estructura de dades en ciències de la computació,
però una cua té un molt diferent propietat.
No és LIFO.
Últim a entrar, primer en sortir.
Déu no ho vulgui.
És lloc FIFO.
Primer a entrar, primer en sortir.
I això és una bona cosa per causa de la justícia
sens dubte quan s'està alineant fins molt d'hora al matí.
Si arribes primer, voler sortir primer també.
>> I així, totes aquestes dades estructures, cues i piles
i raïms d'altres, resulta que pot pensar en això com una matriu.
Aquesta és una matriu, potser una grandària fixa 4, però seria
ser alguna cosa bona si poguéssim acumular safates gairebé infinitament alt si
tenir aquesta quantitat de safates o números.
Així que potser volem utilitzar una llista enllaçada aquí,
però la compensació serà potencialment que necessitem més memòria,
pren una mica més de temps, però nosaltres no limitar l'alçada de la pila,
molt com vitrina de Mather podria limitar la mida de la pila,
i així es tracta de decisions de disseny o opcions disponibles per a nosaltres en última instància.
Així, amb aquestes dades estructures, que han començat
veure nous límits superiors potencialment en el que abans era súper ràpid
i on deixarem d'avui i on
anem Esperem arribar és el dimecres, anem a
començar a mirar una dada estructura que ens permet busquem
a través de les dades en temps final de registre de nou.
I vam veure que, recordem, en la setmana zero i un altre amb recerca binària o dividir
i conquerir.
Es va a tornar i millor encara, el sant grial per a aquest dimecres
serà la d'arribar a la estructura de dades que s'executa realment
o teòricament en constant de temps, amb la qual cosa
no importa quants milions o milers de milions de coses
que tenim en l'estructura de dades, ho farà portar-nos constant de temps, potser un pas
o dos passos o 10 passos, però els números constants de passos
per buscar a través d'aquesta estructura de dades.
Aquest fet serà el Sant Grial però més que dimecres.
Ens veiem llavors.
>> [REPRODUCCIÓ DE MÚSICA]