[Powered by Google Translate] [Setmana 4]
[David J. Malan] [Harvard University]
[Aquesta és CS50.] [CS50.TV]
>> Molt bé, això és CS50, i aquest és el començament de la setmana 4,
i aquest és un dels algorismes d'ordenació més lenta possible.
Quin era el que acabo de veure allà?
Això era una mena de bombolla, per gran O (n ^ 2) + resum,
i de fet no som els únics en aquest món sembla saber
quin tipus bombolla o és el seu temps d'execució.
En efecte, es tractava d'una entrevista amb Eric Schmidt de Google
i l'ex senador Barack Obama només uns pocs anys enrere.
>> Ara, el senador, que és aquí a Google,
i m'agrada pensar en la presidència com una entrevista de treball.
Ara, és difícil aconseguir una feina com a president, i vostè va a través dels rigors ara.
També és difícil aconseguir una feina a Google.
Tenim preguntes, i li demanem a les nostres preguntes candidats,
i aquest és el de Larry Schwimmer.
Vostès pensen que estic fent broma? Està just aquí.
Quina és la forma més eficient per ordenar un milió d'enters de 32 bits?
[Rialles]
Well-
Em sap greu. >> No, no, no, no.
Crec que l'ordenament de bombolla seria el camí equivocat.
>> Anem, qui li va dir això?
La setmana passada recordar que prenem un descans de codi, si més no per un dia,
i va començar a concentrar-se en algunes idees d'alt nivell i resolució de problemes de manera més general
en el context de recerca i classificació,
i hem introduït una cosa que no teníem un copet aquest nom en la setmana passada,
però notació asimptòtica, el Big O, l'Omega Big,
i de vegades la notació gran Theta, i aquests eren simplement formes
de descriure el temps d'execució d'algorismes,
la quantitat de temps que li pren a un algoritme per executar.
>> I vostè pot recordar que vostè va parlar sobre el temps d'execució en funció de la grandària
de l'entrada, que generalment anomenem n, sigui quin sigui el problema que sigui,
on n és el nombre de persones a l'habitació,
el nombre de pàgines d'un llibre de telèfon, i ens vam posar a escriure les coses
com O (n ^ 2) o O (n) o O (n log n),
i fins i tot quan les matemàtiques no va tenir els resultats esperats amb tanta perfecció
i va ser n ² - n / 2 o alguna cosa per l'estil
que en canvi només llençar alguns dels termes d'ordre inferior,
i la motivació no és que de veritat volem un
espècie de manera objectiva d'avaluar
l'acompliment dels programes o el rendiment dels algorismes
que al final del dia no té res a fer, per exemple,
amb la velocitat del seu equip avui.
>> Per exemple, si implementa l'ordenació de bombolla,
o implementar fusionar sort sort o selecció a l'ordinador d'avui,
un equip de 2 GHz, i que l'executi,
i es necessita un cert nombre de segons, l'any que ve hi ha un 3 GHz
o un ordinador de 4 GHz, i vostè pot llavors afirmar que "Wow, el meu algorisme
Ara és el doble de ràpid ", quan en realitat això no és òbviament el cas.
És només el maquinari s'ha tornat més ràpid, però l'equip
no té, i el que realment volen desfer-se de coses com
múltiples de 2 o múltiples de 3, quan es tracta de descriure
què tan ràpid o lent com un algorisme és just i realment es centren
en n o algun factor d'aquest,
una mica d'energia dels mateixos com en el cas de les classes de la setmana passada.
I recordar que, amb l'ajuda de l'espècie de barreja
hem estat capaços de fer-ho molt millor que l'ordenació de bombolla i ordenament per selecció
i fins i tot la inserció de classificació.
>> Ens vam posar mans a la n log n, i una altra,
Recordem que log n generalment es refereix a alguna cosa que creix
més lentament n, de manera que n log n fins ara era bo
perquè era menys de ² n.
Però per aconseguir n log n amb una mena de barreja
el que va ser el germen d'una idea bàsica que havíem d'aprofitar
que també va aprofitar de nou a la setmana 0?
Com abordem el problema de classificació intel · ligent amb una mena de barreja?
Quina va ser la idea clau, potser?
Qualsevol persona en absolut.
Bé, anem a fer un pas enrere.
Descriure merge sort en les seves pròpies paraules.
Com funciona?
Bé, anem a remar de nou a 0 la setmana.
Bé, sí.
[Inaudible-alumne]
Bé, bé, així que divideix el conjunt dels nombres en 2 peces.
Hem classificat cadascuna d'aquestes peces, i després els van fusionar,
i hem vist aquesta idea abans de prendre un problema que és tan gran
i picant cap amunt en un problema que és tan gran o voluminós, aquesta.
>> Recordem l'exemple guia telefònica.
Recordem l'algorisme d'auto-recompte de setmanes enrere,
espècie per fusionar va ser resumit per aquest pseudocodi aquí.
Quan et donen n elements, primer va ser comprovació de validesa.
Si n <2, llavors no faig res en absolut
perquè si n <2 llavors n és 0 o 1, òbviament,
i el que si és 0 o 1, no hi ha res a ordenar.
Això és tot.
La llista ja està trivialment ordenat.
Però d'altra banda, si tens dos o més elements que endavant i dividir
en 2 meitats, esquerra i dreta.
Classifiqueu cadascuna d'aquestes meitats, i després fusionar les dues meitats ordenades.
Però el problema aquí és que a primera vista això sembla que estem batea.
Aquesta és una definició circular en què si jo he demanat que ordenar aquests n elements
i que m'estàs dient "Està bé, està bé, anem a ordenar els elements n / 2 in aquells / 2"
llavors la meva pregunta ve serà "bé, com classificar el n / 2 elements?"
>> Però a causa de l'estructura d'aquest programa,
perquè no és aquest el cas base, per així dir-ho,
aquest cas especial que diu que si n és <un valor fix com 2 volta immediatament.
No respongui amb aquesta resposta circular mateix.
Aquest procés, aquesta ciclicitat finalment acabarà.
Si et pregunto "Sort aquests n elements," i vostè diu: "Està bé, ordenar aquests n / 2"
llavors dius, "una espècie bé, aquests n / 4, n / 8, N/16,"
eventualment podràs dividir per un nombre prou gran
que tindrà només un element de l'esquerra, moment en què es pot dir,
"Aquí, aquí hi ha un element ordenats simple".
A continuació, la brillantor d'aquest algorisme aquí és derivar del fet
que una vegada que tingui totes aquestes llistes individualment ordenats,
tots els quals són de grandària 1, que sembla ser inútil,
una vegada que iniciï la seva fusió i la fusió
construir l'edifici finalment com Rob va fer en el vídeo finalment una llista ordenada.
>> Però aquesta idea s'estén molt més enllà de la classificació.
Hi ha aquesta idea incrustada en aquest programa es coneix com recursió,
de manera que la idea és un programa,
i per resoldre algun problema que et digui,
o posar en el context dels llenguatges de programació que estan en funció,
i amb la finalitat de resoldre un problema, la funció diu a si mateix
una i altra vegada i una altra, però la funció
no pot cridar-se a si mateix infinites vegades.
Finalment, té fins arribar al fons, per dir-ho,
i tenen alguna condició de base rígida que diu
en aquest moment deixa de cridar vostè mateix perquè tot el procés
Finalment és de fet aturar.
Què significa això en realitat, a recurse?
>> A veure si podem fer un exemple simple, trivial amb, diguem,
3 persones amb mi fins aquí a l'escenari, si algú se senti còmode.
1, anem a dalt, 2 i 3.
3 Si volen venir aquí.
Si vols estar al meu costat aquí a una línia, suposem que el problema en qüestió
és molt trivial comptar el nombre de persones que són aquí.
Però, francament, estic cansat de tots aquests exemples de comptatge.
Això va a portar el seu temps, 1, 2, i punt, punt, punt.
Això trigarà una eternitat.
Prefereixo punt aquest problema en conjunt amb l'ajuda de quin és el teu nom?
Sara. >> Sara, està bé.
Kelly. >> Kelly i?
>> Willy. >> Willy, Sara, Kelly, i Willy.
Ara mateix m'he fet la pregunta per algú
nombre de persones que estiguin en aquesta etapa, i no tinc ni idea.
Aquesta és una llista molt llarga, de manera que en lloc d'això faré aquest truc.
Vaig a demanar a la persona al meu costat per fer la major part de l'obra,
i una vegada que es porta a terme fent la majoria del treball
Vaig a fer el mínim de treball possible i només ha d'afegir un
al que la seva resposta és, així que aquí anem.
M'han preguntat quantes persones hi ha a l'escenari.
Quantes persones hi ha a l'escenari a l'esquerra de vostè?
L'esquerra de mi? >> Està bé, però no facis trampa.
Això és bo, això és correcte, però si volem seguir aquesta lògica
suposarem que vol de manera similar a aclarir aquest problema a l'esquerra de vostè,
així que en lloc de contestar directament endavant, passeu la pilota.
Oh, quantes persones hi ha a l'esquerra de mi?
Quantes persones hi ha a l'esquerra?
1.
[Rialles]
Bé, 0, així que el que ha fet ara Willy
s'ha tornat la seva resposta dient aquesta adreça 0.
Ara, què ha de fer? >> 1.
Bé, així que vostè és l'1, pel que diuen: "Està bé, vaig a afegir un
a qualsevol nombre de Willy era, "així 1 + 0.
Vostè és ara 1 pel que la seva resposta a la dreta és ara
1. >> I el meu seria 2.
Bé, pel que està prenent la resposta anterior d'1,
l'addició de la quantitat mínima de treball que vol fer, que és +1.
Ara té 2, i després la mà que em valor?
3, és a dir, ho sento, 2.
Bé.
>> Bé, vam tenir 0 a l'esquerra.
Després vam tenir una, i després afegim 2,
i ara m'estàs donant el número 2,
i pel que estic dient, bé, +1, 3.
Hi ha en realitat tres persones de peu al meu costat en aquesta etapa,
així que podria haver fet això, òbviament, molt lineal,
en gran mesura de la manera òbvia, però què fem realment?
Prenem un problema de tamany 3 inicialment.
A continuació, es va trencar en un problema de mida 2,
llavors un problema de mida 1 i, a continuació, finalment, el cas base
Va ser molt, oh, no hi ha ningú allà,
moment en què Willy va tornar efectivament una resposta codificada d'un parell de vegades,
i el segon es va fer bombollejar després cap amunt, brollava, bombollejava,
i després afegint en aquest addicional 1
hem implementat aquesta idea bàsica de la recursivitat.
>> Ara, en aquest cas, realment no resoldre un problema
qualsevol forma més eficaç llavors que hem vist fins ara.
Però pensa en els algoritmes que hem fet a l'escenari fins al moment.
Vam tenir a 8 fulls de paper a la pissarra,
Al vídeo quan Sean estava buscant el número 7, i què va fer realment?
Bé, ell no va fer cap tipus de divideix i venceràs.
Ell no va fer cap tipus de recursió.
Més aviat, ell acaba de fer aquest algorisme lineal.
No obstant això, quan es va introduir la idea de nombres ordenats a l'escenari en viu la setmana passada
després vam tenir aquest instint d'anar cap al centre,
moment en el qual teníem una llista més petita de mida 4 o altra llista de mida 4,
i després vam tenir el mateix problema, de manera que repeteix, repeteix, repeteix.
En altres paraules, recursed.
Moltes gràcies als nostres 3 voluntaris aquí per demostrar la recursivitat amb nosaltres.
>> A veure si podem fer això ara concretar una mica més,
la solució d'un problema que una vegada més podem fer amb força facilitat,
però utilitzarem com a punt de partida per a l'aplicació d'aquesta idea bàsica.
Per calcular la suma d'un munt de nombres,
per exemple, si es passa al número 3,
Vull donar-li el valor de sigma 3,
de manera que la suma de 3 + 2 + 1 + 0.
Vull tornar a la resposta 6,
així que anem a implementar aquesta funció sigma, aquesta funció suma
que, de nou, presa en entrada i, a continuació torna la suma
d'aquest nombre tot el camí cap avall a 0.
Podríem fer això bastant simple, no?
Podem fer això amb algun tipus d'estructura de bucle,
així que vaig a seguir endavant i que això vagi.
>> Incloure stdio.h.
Déjame entrar principal per treballar aquí.
Anem a guardar això com sigma.c.
Llavors em vaig a anar d'aquí, i vaig a declarar un int n,
i jo vaig a fer el següent mentre l'usuari no cooperar.
Mentre l'usuari no m'ha donat un nombre positiu
m'ho dius a mi anar davant i li demanarà que per an = getInt,
i m'ho dius a mi donar-los algunes instruccions sobre què fer,
així printf ("enter positiu si us plau").
Només és fàcil en com aquest, així que per quan arribem a la línia 14
ara tenim un nombre enter positiu, presumiblement al n.
>> Ara farem alguna cosa amb ell.
Deixa anar per davant i calcular la suma, de manera que int suma = sigma (n).
Sigma és només la suma, així que estic escrivint en la forma més elegant.
Anem a cridar sigma allà.
Aquesta és la suma, i ara em vaig a imprimir el resultat,
printf ("La suma és% d \ n", suma).
I després vaig a tornar 0 per a una bona mesura.
Hem fet tot el que aquest programa requereix excepte la part interessant,
que és per aplicar a la pràctica la funció de sigma.
>> Deixa aquí baix a la part inferior, i m'ho dius a mi declarar funció sigma.
Ha de prendre una variable és de tipus sencer,
i quin tipus de dades és el que vull tornar presumiblement de sigma?
Int, perquè vull que les meves expectatives en la línia 15.
En aquí m'ho dius a mi seguir endavant i posar en pràctica aquest
d'una manera força senzilla.
>> Seguirem endavant i dir: int suma = 0,
i ara em vaig a anar a prendre una mica de bucle aquí
que dirà alguna cosa com això,
for (int i = 0; I <= nombre, i + +) suma + = i.
I després em vaig a tornar suma.
Que podria haver implementat aquest en qualsevol nombre de maneres.
Podria haver fet servir un bucle while.
Podria haver omès utilitzant la variable suma si realment volia,
però en fi, només tenim una funció que si no ho feia babau declara suma és 0.
Llavors es repeteix des de 0 a dalt a través del número,
i en cada iteració s'afegeix que el valor actual de suma i després torna suma.
>> Ara, hi ha una lleugera optimització d'aquí.
Això és probablement un pas perdut, però que així sigui. Això està bé per ara.
Estem almenys ser exhaustiu i va tot el camí de 0 a endavant.
No és molt dur i directe bonic,
però resulta que amb la funció sigma tenim la mateixa oportunitat
com ho vam fer aquí a l'escenari.
A l'escenari que acabem de comptar quantes persones estaven al meu costat,
però en canvi si volem comptar el número 3 + 2 + 1
cap avall a 0 vam poder similar punt a una funció
que en lloc descriurem com recursiu.
Aquí farem un judici ràpid comprovar i assegurar-se que no em babau.
>> Sé que hi ha almenys una cosa en aquest programa que em va fer mal.
Quan vaig arribar a entrar aconseguiré qualsevol tipus de cridar?
Què vaig a cridar a això?
Sí, es va oblidar el prototip, així que estic fent servir una funció anomenada sigma en la línia 15,
però no es va declarar fins a la línia 22, així que millor manera proactiva pujar aquí
i declarar un prototip, i diré sigma int (int número), i això és tot.
S'implementa a la part inferior.
>> O una altra manera que pogués resoldre això,
Podia moure la funció-hi, cosa que no és dolent,
però almenys quan els programes comencen a fer llarga, francament,
Crec que hi ha alguna cosa de valor a tenir sempre principal a la part superior
perquè en el lector pot obrir l'arxiu i veure immediatament
el que està fent el programa sense haver de buscar a través d'ella
buscant que la funció principal.
Anirem a la meva finestra de terminal aquí, tracti de fer sigma sigma fer,
i vaig ficar la pota aquí també.
Declaració implícita de la funció getInt significa que m'hagi oblidat de fer allò altre?
[Inaudible-alumne]
Bé, per la qual cosa pel que sembla un error molt comú, així que anem a posar això aquí,
cs50.h, i ara anem a tornar a la meva finestra de terminal.
>> Vaig a esborrar la pantalla, i vaig a fer tornar a executar sigma.
Sembla que s'ha compilat. Permetin-me ara s'executen sigma.
Vaig a escriure el número 3, i em van donar 6, així que no és un xec rigorós,
però almenys sembla estar funcionant a primera vista, però ara anem a destrossar,
i anem a gaudir de la idea de la repetició, de nou,
en un context molt simple, així que d'aquí a unes setmanes
quan vam començar a explorar més elegants estructures de dades d'arrays
tenim una altra eina en la caixa d'eines amb les quals
manipular les estructures de dades, com veurem.
Aquest és l'enfocament iteratiu, l'enfocament basat en bucle.
>> Permetin-me ara fer aquesta vegada.
Permetin-me dir que en lloc de la suma del nombre de
baix a 0 és realment la mateixa cosa que
nombre + sigma (nombre - 1).
En altres paraules, igual que en l'escenari em va trepitjar a cadascuna de les persones al meu,
i ells al seu torn manté expulsar fins que finalment va tocar fons en Willy,
qui va haver de tornar una resposta codificada com a 0.
Aquí ara estem igualment bat per sigma
la mateixa funció que va ser anomenat originalment, però aquí la idea clau
és que no estem cridant sigma idèntica.
No estem de pas en el núm.
Estem passant clarament en nombre - 1,
de manera que un problema una mica més petit, lleugerament més petit problema.
>> Malauradament, això no és del tot una solució, però, i abans de fixar
el que podria saltar tan evident en alguns de vostès
m'ho dius a mi seguir endavant i tornar a executar fer.
Sembla que compili bé.
Permetin-me tornar a executar sigma amb 6.
Vaja, deixa tornar a executar sigma amb 6.
Hem vist això abans, encara que sigui accidentalment temps passat també.
Per què em surt aquest error de segmentació críptic? Si.
[Inaudible-alumne]
No hi ha cas base, i més específicament, el que probablement va succeir?
Aquest és un símptoma del que el comportament?
Diguem que una mica més fort.
[Inaudible-alumne]
És un bucle infinit eficaçment, i el problema amb els bucles infinits
quan impliquen recursió en aquest cas, una funció que es fa dir,
el que passa cada vegada que es crida a una funció?
Bé, pensi en la manera com va exposar la memòria en un ordinador.
Hem dit que hi ha aquesta quantitat de memòria anomenat la pila que està en el fons,
i cada vegada que es crida a una funció de memòria una mica més es va posar
en aquesta pila de trucada que conté les variables locals de la funció o paràmetres,
pel que si sigma sigma sigma Les trucades crida sigma
diu sigma on acaba aquesta història?
>> Bé, amb el temps els excessos de la quantitat total
de memòria que té disponible al seu ordinador.
Vostè envair el segment que se suposa que has de romandre a l'interior,
i s'obté aquest error de segmentació, el nucli de dúmping,
i què core dumped significa és que ara tinc un arxiu anomenat nucli
que és un arxiu que conté zeros i uns
que en realitat en el futur serà útil per al diagnòstic.
Si no et resulta obvi que el seu error és
en realitat es pot fer una mica d'anàlisi forense, per dir-ho,
a l'arxiu bolcat de memòria, que, de nou, és només un munt de zeros i uns
que en essència representa l'estat del seu programa a la memòria
el moment en què va caure d'aquesta manera.
>> La solució aquí és que no podem tornar a cegues sigma,
el nombre sigma + d'un problema una mica més petit.
Hem de tenir algun tipus de cas base aquí,
i el que el cas base probablement ser?
[Inaudible-alumne]
Està bé, sempre que el nombre és positiu que en realitat hauria de tornar això,
o dit d'una altra manera, si el nombre és, per exemple, <= a 0
Saps què, vaig a seguir endavant i tornar 0,
igual que Willy ho va fer, i una altra cosa, jo seguiré endavant
i tornar aquest, pel que no és molt més curt
que la versió iterativa que fustigar primer usant un bucle for,
notar que hi ha aquest tipus d'elegància a la mateixa.
En lloc de tornar un nombre i realitzar tota aquesta matemàtica
i l'addició de les coses amb les variables locals
Quan estiguis dient: "Bé, si això és un problema fàcil de super,
igual que el nombre és <0, deixa immediatament tornarà 0. "
>> No anem a molestar suport nombres negatius,
així que vaig a codificar el valor de 0.
Però d'altra banda, per posar en pràctica aquesta idea de sumar
tots aquests nombres junts que efectivament pot fer un mos petit
per sortir del problema, igual que ho vam fer aquí a l'escenari,
llavors bat la resta del problema a la següent persona,
però en aquest cas la següent persona és un mateix.
Es tracta d'una funció amb el mateix nom.
Només has de passar un problema cada vegada més petits i més petits cada vegada,
i tot i que no tenen les coses molt formalitzats en el codi aquí
això és exactament el que estava passant a la setmana 0 amb la guia telefònica.
Això és exactament el que estava succeint en les últimes setmanes amb Sean
i amb les nostres demostracions de la recerca de nombres.
Es tracta de prendre un problema i dividint una i altra vegada.
>> En altres paraules, hi ha una manera de traduir ara
aquesta construcció del món real, aquesta construcció d'alt nivell
de dividir i conquerir i fer alguna cosa una i altra vegada
en el codi, així que això és una cosa que anem a veure una vegada més amb el temps.
Ara, en un apart, si ets nou en la recursivitat almenys d'entendre ara
per què això és divertit.
Vaig a anar a google.com,
i jo vaig a buscar alguns consells i trucs sobre la recursivitat, introdueixi.
Digues a la persona al teu costat si no estiguessin rient ara.
Vols dir la recursivitat?
Potser volíeu dir-ah, aquí anem.
Bé, ara que està la resta de tot el món.
Una mica ou de Pasqua incrustat en algun lloc a Google.
Com acotació al marge, un dels enllaços que posem a la pàgina web del curs
d'avui és precisament aquesta xarxa de diversos algoritmes d'ordenació,
algunes de les quals vam veure la setmana passada, però el bo d'aquesta visualització
a mesura que tracten d'embolicar la seva ment al voltant de diverses coses relacionades amb algoritmes
Sabia que pot molt fàcilment ara començar amb diferents tipus d'entrades.
Les entrades de tots invertida, sobretot les entrades ordenades, les entrades a l'atzar i així successivament.
En intentar, una vegada més, distingir aquestes coses en la teva ment
adonar-se que aquesta adreça URL a la pàgina web de l'assignatura a la pàgina de Conferències
podria ajudar a raonar a través d'alguns d'ells.
>> Avui finalment podem resoldre aquest problema des de fa un temps,
que era que aquesta funció d'intercanvi no va funcionar,
i quin va ser el problema fonamental amb aquest canvi funció,
l'objectiu va ser, de nou, per intercanviar un valor aquí i aquí
de tal manera que això passa?
Això en realitat no funciona. Per què?
Si.
[Inaudible-alumne]
Exactament, l'explicació d'aquest bugginess
simplement perquè quan es diu a funcions en C
i aquestes funcions prendre arguments, com aib aquí,
està de pas en les còpies de qualsevol valor que estem oferint a aquesta funció.
No està proporcionant els valors originals ells mateixos,
així que vam veure això en el context de buggyc,
buggy3.c, que semblava una mica alguna cosa com això.
>> Recordem que teníem x i i inicialitza a 1 i 2, respectivament.
A continuació, imprimeix el que eren.
Llavors em va dir que jo els estava cridant intercanvi swap de x, i.
Però el problema era que l'intercanvi de treball,
però només en l'àmbit d'aplicació de la pròpia permuta funcionar.
Així que vam arribar a la línia 40 els valors intercanviats
van ser rebutjats, i per tant res
en la funció original va ser canviat realment en absolut,
llavors si li sembla llavors que l'aspecte que té en termes de la nostra memòria
si aquesta part esquerra de la placa representació
i vaig a fer el meu millor esforç perquè tots la vegin això: si aquesta part esquerra de la taula
representa, per exemple, la memòria RAM, i la pila es creixerà en aquesta forma,
i cridem a una funció com a principal i principal té 2 variables locals, x i i,
descriurem a aquells que x aquí, i anem a descriure com i aquí,
i posarem en els valors 1 i 2, de manera que aquesta aquí és principal,
i quan es crida a la funció principal d'intercanvi del sistema operatiu
dóna la funció d'intercanvi en la seva pròpia franja de memòria a la pila,
seu propi marc a la pila, per així dir-ho.
També assigna 32 bits per aquests sencers.
Li passa a cridar-a i b, però això és totalment arbitrària.
Podria haver anomenat el que vulgui, però el que passa quan principal
intercanvi de trucades és que pren aquest 1, posa una còpia allà, posa una còpia allà.
>> Hi ha una altra variable local a swap, però, diu què? Tmp. >>
Tmp, així que em dono altres 32 bits d'aquí,
I què faig en aquesta funció?
Vaig dir int tmp rep una, pel que té 1, així que ho vaig fer l'última vegada que va jugar amb aquest exemple.
A continuació, es posa a b, llavors b és 2, de manera que ara això es converteix en 2,
i ara arriba b temp, temp així és 1,
de manera que ara es converteix en aquest b.
Això és genial. Va funcionar.
Però tan bon punt la funció retorna
d'intercanvi de memòria de forma eficaç desapareix perquè pugui ser reutilitzat
per alguna altra funció en el futur, i principal és òbviament completament inalterat.
Necessitem una manera de resoldre aquest problema fonamental,
i avui per fi vaig a tenir una manera de fer això mitjançant el qual
podem introduir una cosa que es diu un punter.
Resulta que podem resoldre aquest problema
no passant en còpies de x i i
però no pel que passa a, creus que, a la funció d'intercanvi?
Sí, què passa amb la direcció?
Realment no hem parlat sobre les adreces en molt detall,
però si això pissarra representa la memòria del meu ordinador
sens dubte podríem començar a numerar els bytes de RAM en el meu
i dir que aquest és el byte # 1, aquest és el byte # 2, # 3 byte,
byte # 4, # byte ... 2 milions de dòlars si tinc 2 GB de RAM,
per la qual cosa sens dubte podria arribar a algun esquema de numeració arbitrari
per a tots els bytes individuals en la memòria del meu ordinador.
>> Què passa si en lloc quan dic intercanvi
en lloc de passar còpies de x i y
¿Per què no en lloc de passar la direcció de x aquí,
la direcció de i aquí, essencialment l'adreça postal
de x i i perquè després d'intercanvi, si està informat
de la direcció en la memòria de x i y,
després d'intercanvi, si ho va entrenar una mica,
que potencialment podria conduir a aquesta direcció, per així dir-ho,
x, i canviar el nombre allà, després en cotxe a la direcció de i,
canviar el nombre allà, encara que en realitat no obtenir còpies d'ell mateix aquests valors,
així que, encara que ja parlem d'això com memòria principal
i aquest swap com la memòria dels poderosos i la part perillosa de C
és que qualsevol funció pot tocar qualsevol part de la memòria de l'ordinador,
i això és de gran abast en la qual es poden fer coses molt elegants amb programes d'ordinador en C.
Això és perillós perquè també es pot ficar la pota molt fàcilment.
De fet, una de les formes més comunes per als programes d'aquests dies per ser explotats
encara no és per a un programador per realitzar
que ell o ella està permetent una dada
per ser escrita en una ubicació de memòria que no es pretenia.
>> Per exemple, ell o ella declara una matriu de mida 10
però, accidentalment, tracta de posar 11 bytes en la matriu de la memòria,
i comences a tocar parts de la memòria que ja no són vàlids.
Només per aquest context, alguns de vostès sabran que
programari sovint li demana els números de sèrie o claus de registre,
Photoshop i Word i programes com aquest.
Hi ha esquerdes, com alguns de vostès saben, en línia on vostè pot executar un petit programa,
i llest, no demanar més d'un número de sèrie.
Com és que funciona?
En molts casos, aquestes coses són simplement trobar en els ordinadors
segments de text en zeros reals de l'ordinador i éssers
On és aquesta funció en la qual es demana el número de sèrie,
i sobreescriure aquest espai, o mentre el programa s'està executant
vostè pot esbrinar on la clau s'emmagatzema
utilitzen una part anomenat un depurador, i es pot esquerdar programari d'aquesta manera.
Això no vol dir que aquest és el nostre objectiu per al pròxim parell de dies,
però té molt reals ramificacions.
Que un li passa a implicar el robatori de programari,
però també hi ha compromís de les màquines senceres.
>> De fet, quan aquests llocs web dia són explotats
i compromesa i les dades es van filtrar i contrasenyes robades es
molt sovint es relaciona amb la mala gestió de la memòria,
o, en el cas de bases de dades, manca d'anticipació
entrada contradicció, de manera que més que en les pròximes setmanes,
però per ara només un avançament de la classe de dany que es pot fer
per no prou entendre com funcionen les coses sota la caputxa.
Anem a anar sobre la comprensió de per què això està trencat
amb una eina que es farà més i més útil
ja que els nostres programes es tornen més complexos.
Fins ara quan s'ha tingut un error en el seu programa
Com ha anat depurant sobre ell?
Quines han estat les teves tècniques fins ara, ja sigui impartit pel TF
o simplement autodidacta?
[Estudiant] printf.
Printf, així printf probablement ha estat el seu amic que si vostè vol veure
el que està succeint dins del seu programa de
vostè acaba de posar printf aquí, printf aquí, printf aquí.
A continuació, executar, i et donen un munt de coses a la pantalla
que es pot utilitzar per deduir llavors el que realment està passant malament en el seu programa.
>> Printf tendeix a ser alguna cosa molt poderós,
però és un procés molt manual.
Has de posar un printf aquí, un printf aquí,
i si ho poses dins d'un bucle podria obtenir 100 línies
de sortida que vostè llavors ha de tamisar a través.
No és un mecanisme molt fàcil d'utilitzar o interactius per als programes de depuració,
però per sort hi ha alternatives.
Hi ha un programa, per exemple, diu GDB, el depurador de GNU,
que és un arcà molt poc en com l'utilitza.
És una mica complex, però, francament,
aquesta és una d'aquelles coses que si vostè posa en aquesta setmana i la propera
l'hora extra a entendre alguna cosa com GDB
que li estalviarà probablement desenes d'hores al llarg termini,
Així que amb això, et vaig a donar un avançament de com funciona això.
>> Estic en la meva finestra de terminal.
Deixin-me seguir endavant i compilar aquest programa, buggy3.
Ja està actualitzat.
Deixa córrer tal com ho vam fer fa un temps, i de fet, està trencada.
Però per què és això? Potser el arruïni la funció d'intercanvi.
Potser és a i b. No estic molt a moure correctament.
Deixa anar endavant i fer-ho.
En comptes de córrer buggy3 m'ho dius a mi en lloc d'executar aquest programa de GDB,
i jo ho diré a executar buggy3,
i vaig a incloure un argument de línia d'ordres,-tui,
i posarem això en futurs problemes d'especificació per recordar.
I ara aquesta interfície en blanc i negre que va aparèixer, de nou,
És una mica aclaparador al principi, perquè hi ha tota aquesta
informació sobre la garantia aquí, però almenys hi ha alguna cosa familiar.
A la part superior de la finestra és el meu codi actual,
i si em desplaço fins aquí permetin-me desplaçar a la part superior del meu arxiu,
i, de fet, hi ha buggy3.c i observi en la part inferior d'aquesta finestra
Tinc aquest missatge GDB.
>> Aquest no és el mateix que el meu suau de John Harvard.
Aquest és un missatge que permetrà que controli GDB.
GDB és un depurador.
Un depurador és un programa que li permet caminar a través de
execució del seu programa de línia a línia per línia,
en el camí fent el que vulguis amb el programa,
fins i tot trucar a funcions, oa la recerca, sobretot,
en valors de les variables de diversos.
Seguirem endavant i fer això.
Vaig a seguir endavant i escriure en carrera en el símbol del BGF,
per notarà en la part inferior esquerra de la pantalla que he escrit córrer,
i he prem enter, i què va fer això?
És, literalment, corrent el meu programa, però que en realitat no veig molt anar d'aquí
perquè jo no ho he dit el depurador
per fer una pausa en un moment particular en el temps.
Simplement escrivint run executa el programa.
Jo en realitat no veig res. No ho puc manipular.
>> En el seu lloc farem això.
En aquest missatge GDB m'ho dius a mi en comptes escrigui break, entrar.
Això no és el que vaig voler escriure.
En lloc d'això escriure ruptura principal.
En altres paraules, vull parlar d'una cosa que es diu un punt d'interrupció,
que es nomena convenient perquè va a trencar o fer una pausa
execució del seu programa en aquest lloc en particular.
Principal és el nom del meu funció.
Recordeu que GDB és molt intel · ligent.
Es va descobrir que la principal passa a començar aproximadament a la línia 18
de buggy3.c i observi aquí, a la part superior esquerra
+ B és just al costat de la línia 18.
Això em recorda que he posat un punt d'interrupció en la línia 18.
Aquesta vegada, quan jo escrigui run, em vaig a córrer el meu programa
fins que arribi a aquest punt de ruptura,
de manera que el programa farà una pausa per a mi en la línia 18.
Aquí anem, corre.
Res sembla haver passat, però va deixar avís a la part inferior
programa d'inici, buggy3, 1 a punt d'interrupció en la línia principal buggy3.c 18.
Què puc fer ara?
>> Recordeu que començar a escriure coses com la impressió,
No printf, print x, i això sí que és estrany.
Els $ 1 és només una curiositat, com veurem
cada vegada que imprimeixi alguna cosa que s'obté un nou valor $.
Això és el que es pot fer referència als valors anteriors per si de cas,
però per ara el que em diu impressió és que el valor de x en aquest punt de la història
és aparentment 134514032.
Què? D'on vi que fins i tot ve?
[Inaudible-alumne]
De fet, això és el que anomenarem a un valor escombraries, i nosaltres no hem parlat d'això, però,
però la raó per la qual establir variables
òbviament perquè tinguin algun valor que desitja que tinguin.
Però el problema és recordar que vostè pot declarar variables
com ho vaig fer fa un moment al meu exemple sigma
sense arribar a donar un valor.
Recordem el que vaig fer aquí a sigma.
Declarar n, però quin valor tenia el dono?
Cap, perquè sabia que en les pròximes línies
GetInt s'ocuparia del problema de posar un valor dins de n.
>> Però en aquest punt de la història de la línia 11
i la línia 12 i la línia 13 i la línia 14
al llarg d'aquestes línies de diversos quin és el valor de n?
En C simplement no ho sé.
En general és un valor escombraries, un nombre completament a l'atzar
que sobra essencialment d'alguna funció anterior
després d'haver estat executat, i també el programa s'executa
Recordem que la funció té funció, la funció, la funció.
Tots aquests marcs d'aconseguir posar en la memòria i després els retornen les funcions,
i igual que vaig suggerir amb la goma d'esborrar la seva memòria és eventualment reutilitzats.
Bé, el que passa és que aquesta variable x en aquest programa
sembla haver contingut algun valor com escombraries 134514032
d'alguna funció anterior, no un que jo vaig escriure.
Podria ser una cosa que ve efectivament amb el sistema operatiu,
alguna funció sota la caputxa.
>> Està bé, està bé, però ara anem a passar a la següent línia.
Si escric "següent" en el meu GDB ràpid i vaig arribar a entrar,
compte que el selector es desplaça fins a la línia 19,
sinó la conseqüència lògica és que la línia 18
ha acabat d'executar, de manera que si torno a escriure "print x"
Ara heu de veure 1, i de fet, així és.
Un cop més, les coses $ és una forma de GDB li recorda
el que la història de les impressions són que vostè ha fet.
Ara vaig a seguir endavant i imprimir i, de fet, i és un valor boig també,
però no és gran cosa ja que a la línia 19 estem a punt de cedir
el valor 2, així que vaig a escriure "Següent" de nou.
I ara estem en la línia printf.
Permetin-me fer x impressió.
Déjame fer i d'impressió. Francament, estic una mica cansat de la impressió d'aquest.
Deixa en comptes escriure "x pantalla" i "i la pantalla",
i ara cada vegada que escrigui una ordre en el futur
Vaig a recordar el que és x i i, el que és x i i, el que és x i i.
>> També puc, en un apart, escriviu "locals d'informació."
Info és comandes especials.
Els locals significa que em mostra les variables locals.
Només en cas d'oblit o es tracta d'una funció boig i complicat
que jo o algú més va escriure vilatans informació li dirà
¿Quines són les variables locals dins d'aquesta funció local
que és possible que es preocupen per si vols tafanejar.
Ara, printf està a punt d'executar, així que vaig a seguir endavant i només has d'escriure "següent".
Perquè estem en aquest entorn no estem realment veient
executar fins aquí, però noti que està fent una mica destrossat aquí.
Però noti que està anul · lant la pantalla hi ha,
així que no és un programa perfecte aquí, però això està bé, perquè sempre puc furgar
mitjançant impressió si vull.
>> Deixa escriure al costat de nou, i ara ve la part interessant.
En aquest punt de la història i és 2, i x és 1,
com es suggereix aquí, i de nou,
la raó d'això és automàticament mostrant ara és perquè he utilitzat la comanda
display x i i visualització, de manera que el moment de tipus I següent
en teoria x i i s'han de convertir intercanvien.
Ara, ja sabem que no serà el cas,
però ja veurem d'aquí a un moment com podem aprofundir més per entendre per què això és cert.
A continuació, i per desgràcia, i és encara 2 x segueix sent 1, i puc confirmar el mateix.
Imprimir x, imprimir i.
De fet, cap intercanvi que realment ha succeït, així que començarem aquest cop.
Clarament intercanvi està trencat.
En lloc d'això escriu "Executar" de nou.
Permetin-me dir que sí, vull que reiniciar des del principi, entrar.
>> Ara estic de tornada cap amunt en la línia 18.
Ara noti x i i són valors d'escombraries de nou.
Següent, següent, següent, següent.
Si m'avorreixo jo també puc poseu n pel proper.
Es pot abreujar amb la seqüència més curta possible de caràcters.
Intercanviar està trencat.
Anem a bussejar, així que en comptes de teclejar següent,
ara vaig a escriure el que pas Estic caminant dins d'aquesta funció
perquè jo pugui caminar a través d'ell, així que em va colpejar pas i després entra.
Recordeu que els salts que destaquen més avall en el meu programa a la línia 36.
Ara, quines són les variables locals?
Informació dels locals.
No hi ha res encara perquè no hem arribat a aquesta línia,
així que seguirem endavant i dir "següent".
Ara sembla que tenim tmp tmp impressió.
Valor escombraries, no? Crec que sí.
Què tal una impressió, impressió b, 1 i 2?
En un moment, així que em escrigui de nou al costat
tmp tindrà un valor d'1, amb sort,
tmp perquè serà assignat el valor de a.
>> Ara farem imprimir a, b, impressió,
però ara imprimir tmp, i és de fet 1.
Deixa fer a continuació. Deixa fer a continuació.
He acabat la funció d'intercanvi.
Estic encara dins de la mateixa en la línia 40, així que em imprimiu una,
print b, i no m'importa el que tmp és.
Sembla intercanvi és correcte quan es tracta d'intercanvi de a i b.
Però si ara introduït a continuació, salt de nou a la línia 25,
i per descomptat, si escric en x i i d'impressió
segueixen sent sense canvis, de manera que no han solucionat el problema.
No obstant això, el diagnòstic ara potser amb aquest programa GDB
hem aconseguit almenys un pas més a prop d'entendre
el que va malament sense necessitat d'escombraries nostre codi per posar un printf aquí,
printf aquí, printf aquí i després s'executa una i altra vegada
tractant d'esbrinar el que va malament.
>> Vaig a seguir endavant i deixar fora d'aquest conjunt amb deixar de fumar.
Això dirà a continuació, "Sortir de totes maneres?" Sí
Ara estic de tornada en el meu sistema normal, i he acabat amb GDB.
Com acotació al marge, no cal utilitzar aquesta bandera-tui.
De fet, si ho omet obtenir essencialment la meitat inferior de la pantalla.
Si a continuació, escriviu ruptura principal i executeu
Encara puc executar el meu programa, però el que farà és més textual
només em mostra la línia actual al mateix temps.
El tui-, la interfície d'usuari textual,
només li mostra més del programa al mateix temps, que és probablement una mica conceptualment més fàcil.
Però, en realitat, només es pot fer següent, següent, següent,
i vaig a veure una línia al mateix temps, i si realment vols veure el que està passant
Em pot escriure la llista i veure un munt de línies veïnes.
>> Hi ha un vídeo que li hem demanat que vostè mira per a butlletins de problemes 3
en la qual Nate es tracten algunes de les complexitats de GDB,
i aquesta és una d'aquestes coses, de veritat, on un percentatge no trivial que
mai tocarà GDB, i això serà una cosa dolenta
perquè, literalment, vostè acabarà gastant més temps a finals d'aquest semestre
perseguint els insectes llavors vostè tindria si vostè posa en aquesta mitja hora / hora
aquesta setmana i l'aprenentatge al costat de sentir còmode amb GDB.
Printf era el seu amic.
GDB ara ha de ser el seu amic.
>> Teniu alguna pregunta respecte GDB?
I aquí hi ha una llista ràpida d'alguns dels comandaments més poderosos i útils.
Si. >> Pot imprimir una cadena?
Pot imprimir una cadena? Per descomptat.
No ha de ser només nombres enters.
Si una variable s és una cadena que, simplement introduïu s d'impressió.
Se li mostrarà el que és variable de cadena.
[Inaudible-alumne]
Se li donarà la direcció i la pròpia cadena.
Es mostrarà als dos.
I una última cosa, només perquè es tracta d'un notable coneixement massa.
Backtrace i el marc, deixa submergir-se en aquesta última vegada,
mateix programa amb GDB.
Deixin-me seguir endavant i executar la versió de la interfície d'usuari textual,
trencar principal.
Deixin-me seguir endavant i córrer de nou. Sóc aquí.
Ara aniré a següent, següent, següent, següent, següent, pas, entrar.
>> I ara suposo que ara estic en intercanvi deliberadament, però jo sóc com "Maleïda sigui, ¿quin era el valor de x?"
No puc fer x més.
No puc fer-ho i perquè no estan en el seu abast.
No estan en el seu context, però no hi ha problema.
Puc escriure backtrace.
Això em mostra totes les funcions que s'han realitzat fins aquest punt en el temps.
Observeu que l'una en la part inferior, la principal, s'alinea amb principal
estar en el fons de la nostra imatge aquí.
El fet que està per sobre de canvi que s'alineï amb el canvi d'estar per sobre d'ella en la memòria aquí,
i si vull tornar a principal temporalment el que puc dir "marc".
Quin nombre? Principal és el quadre número 1.
Vaig a seguir endavant i dir "quadre 1".
>> Ara estic de tornada en main, i puc imprimir x, i puc imprimir i,
però no puc imprimir a ob.
Però puc si dic: "Bé, esperi un minut. On era el canvi?"
Deixin-me seguir endavant i dir "0 marc".
Ara estic de tornada on vull estar, i en un apart,
hi ha altres ordres també, com si realment estàs aconseguint mecanografiar avorrit següent, següent, següent, següent,
en general, es pot dir coses com "el 10", i que passarà pels següents 10 línies.
També pot escriure "continuar" quan realment fart de caminar a través d'ella.
Continuar s'executarà el programa sense interrupció fins que arriba a un altre punt d'interrupció,
ja sigui en un bucle o més avall en el seu programa.
>> En aquest cas es va continuar fins al final, i el programa surt normalment.
Aquesta és una forma elegant, procés inferior.
Només el seu programa va acabar normalment.
Més sobre això en el vídeo i en la depuració de les sessions per venir.
Això era molt.
Anem a prendre el nostre fill de 5 minuts de descans aquí, i anem a tornar amb les estructures i els arxius.
>> Si ha bussejat en conjunt de processadors d'aquesta setmana ja
vostè sabrà que utilitzem en el codi de distribució,
la font de codi que us proporcionem a vostè com un punt de partida, algunes tècniques noves.
En particular, hem introduït aquesta nova paraula clau es diu estructura, l'estructura,
de manera que puguem crear variables personalitzades de tot tipus.
També va introduir la noció d'arxiu de l'arxiu d'entrada d'E / S i de sortida,
i això és el que podem guardar l'estat
del seu tauler Scramble en un arxiu en disc
perquè els companys docents i comprenc
el que està succeint dins del seu programa sense haver de jugar de forma manual
desenes de jocs de baralla.
Podem fer-ho més automatitzadament.
>> Aquesta idea d'una estructura resol un problema bastant convincent.
Suposem que volem implementar algun programa
que d'alguna manera fa un seguiment de la informació sobre els estudiants,
i els estudiants podrien tenir, per exemple, una identificació, un nom
i una casa en un lloc com Harvard, així que aquests són tres peces d'informació
volem mantenir al seu voltant, així que permetin-me seguir endavant i començar a escriure un petit programa aquí,
incloure stdio.h.
Deixa fer incloure cs50.h.
I després començar la meva funció principal.
No em molestaré amb els arguments de línia de comandes,
i aquí vull tenir un estudiant, així que vaig a dir
un estudiant té un nom, així que vaig a dir "nom de cadena."
Llavors jo vaig a dir un estudiant també té un ID, aneu int així,
i un estudiant té una casa, així que també vaig a dir "casa de corda".
Llavors vaig a demanar aquest una mica més neta d'aquesta manera.
Bé, ara tinc 3 variables amb les que representen a un estudiant, de manera que "un estudiant".
>> I ara vull omplir aquests valors, així que vaig a seguir endavant i dir alguna cosa com
"Aneu = 123".
Nom es posarà a David.
Diguem que la casa es posarà Mather,
i després em vaig a fer alguna cosa arbitràriament com printf ("% s,
amb identificador% d, viu a% s.
I ara, què és el que vull connectar aquí, una després de l'altra?
Nom, id, casa, retorna 0.
Bé, llevat que vaig ficar la pota en algun lloc aquí
Crec que tenim un programa molt bo que emmagatzema un estudiant.
Per descomptat, això no és tan interessant. I si vull tenir 2 estudiants?
Això no és gran cosa. Puc suportar 2 persones.
Deixin-me seguir endavant i posar en relleu aquest i baixar aquí,
i el que puc dir "id = 456" per algú com Rob que viu a Kirkland.
>> Bé, espera, però no puc cridar a aquests el mateix,
i sembla que vaig a haver de copiar això,
així que permetin-me dir que aquests seran variables de David,
i em deixes algunes còpies d'aquests per Rob.
Anomenarem a aquests Rob, però això no funcionarà ara
perquè he-espera, canviarem a ID1, Nom1 i house1.
Rob serà 2, 2.
He de canviar això aquí, aquí, aquí, aquí, aquí, aquí.
Espera, què passa amb Tommy? Farem això de nou.
Òbviament, si vostè encara pensa que això és una bona manera de fer això, no ho és,
així copiar / enganxar malament.
Però hem resolt aquest fa una setmana.
>> Quina era la nostra solució quan volíem tenir diverses instàncies del mateix tipus de dades?
[Els estudiants] Matriu.
Una matriu, així que tractarem de netejar això.
Vull deixar una mica d'espai per a mi mateix a la part superior, i m'ho dius a mi fer això en lloc aquí.
Anomenarem a aquestes persones, i en el seu lloc vaig a dir "ids int"
i jo vaig a donar suport a 3 de nosaltres per ara.
Vaig a dir "noms de cadena," i vaig a donar suport a 3 de nosaltres,
i després vaig a dir "cases de corda", i jo vaig a donar suport a tres de nosaltres.
Ara aquí en lloc de David obtenir les seves pròpies variables locals
podem desfer-nos d'ells.
Això se sent bé que estem netejant això.
Llavors puc dir que David serà [0] i noms [0]
i cases [0].
I després tenim a Rob semblant pot estalviar en això.
Anem a posar això aquí, així que serà arbitràriament ids [1].
Ell serà noms [1],
i després, finalment, les cases [1].
>> Encara una mica tediós, i ara he de resoldre això,
així que anem a dir "noms [0], id [0], cases [0],
i anem a pluralitzar això.
Ids, IDS, IDS.
I de nou, ho estic fent, així que de nou, ja estic recorrent a copiar / enganxar de nou,
el més probable és que hi ha una altra solució aquí.
És probable que pugui netejar això més lluny amb un bucle o alguna cosa així,
Així que en resum, és una mica millor, però encara se sent com
Estic recorrent a copiar / enganxar, però fins i tot això, sostinc,
és realment no és fonamentalment la solució adequada perquè
I si en algun moment vam decidir que vostè sap què?
En realitat, hauríem d'haver estat emmagatzemant les adreces de correu electrònic de David i Rob
i tots els altres en aquest programa.
També cal guardar els números de telèfon.
També cal guardar els números de contacte d'emergència.
Tenim totes aquestes peces de dades que voleu emmagatzemar,
Llavors, com fa vostè per fer això?
>> Vostè declara altra matriu a la part superior, a continuació, afegir manualment
una adreça de correu electrònic [0], l'adreça de correu electrònic [1]
per David i Rob i així successivament.
Però no hi ha realment només una suposició subjacent en aquest disseny
que estic fent servir el sistema d'honor saber que
[I] en cada un dels diversos arrays
que passa és que es refereixen a la mateixa persona,
de manera que [0] a ids és el número 123,
i vaig a assumir que els noms [0]
és la mateixa persona el nom i cases [0]
és la casa de la mateixa persona i així successivament per a tots els arrays diferents que creen.
Però cal notar que no hi ha vincle fonamental
entre els 3 trossos d'informació, id, nom i la casa,
tot i que l'entitat que estem tractant de modelar en aquest programa no és arrays.
Les matrius són precisament d'aquesta manera programàtica de fer-ho.
El que realment volem per modelar en el nostre programa és una persona
igual que David, una persona com Rob dins dels quals
o encapsulació és un nom i una ID i una casa.
>> Podem d'alguna manera expressar aquesta idea de l'encapsulació
mitjançant el qual una persona té una identitat, un nom i una casa
i no recórrer a aquest truc pel que realment ens
Confiem que alguna cosa suport
es refereix a la mateixa entitat humana en cada un d'aquests conjunts diferents?
De fet, podem fer això.
Deixa anar més important per ara, i em deixa crear el meu propi tipus de dades
realment per primera vegada.
Es va utilitzar aquesta tècnica en Scramble,
però aquí vaig a seguir endavant i crear un tipus de dades,
i saps què, jo vaig a dir estudiant o persona,
i jo vaig a utilitzar typedef per definir un tipus.
Vaig a dir que es tracta d'una estructura,
i després aquesta estructura serà d'estudiant tipus, direm,
encara que és una mica antiquat ara per a mi.
Direm "int id."
Anem a dir "nom de cadena."
Llavors direm "casa de Cordes",
de manera que ara el final d'aquestes línies de codi
Acabo ensenyat so metàl · lic que hi ha
a més d'un tipus de dades sencers, a més de cordes, a més de dobles, a més de carrosses.
>> A partir d'aquest moment en la línia de temps de 11, ara hi ha un nou tipus de dades anomenat als estudiants,
i ara puc declarar una variable d'estudiant en qualsevol lloc que desitgi,
així que em baixi aquí a la gent.
Ara puc desfer d'això, i puc anar de nou a David aquí,
i David realment puc dir que David,
literalment podem anomenar la variable de mi mateix,
serà de tipus estudiantil.
Això pot semblar una mica estrany, però això no és tan diferent
de declarar una cosa com un enter o una cadena o un flotador.
El que passa a dir-se estudiant ara,
i si vull posar alguna cosa dins d'aquesta estructura
Ara he de fer servir una nova peça de sintaxi, però és bastant senzill,
david.id = 123, david.name = "David" a la capital de D,
i david.house = "Mather,"
i ara puc desfer d'aquesta cosa aquí.
Notificació ara hem redissenyat el nostre programa en realitat una forma molt millor
en què ara el nostre programa reflecteix el món real.
>> Hi ha una noció real d'una persona o un estudiant.
Aquí tenim ara una versió C d'una persona o més específicament un estudiant.
A l'interior d'aquesta persona són aquestes característiques pertinents,
ID, nom i casa, així que Rob es converteix essencialment la mateixa cosa aquí baix,
estudiant per robar, i ara rob.id = 456,
rob.name = "Rob".
El fet que la variable es diu Rob és una espècie de sentit.
Podríem haver dit x o i z.
Ens va cridar a Rob a ser semànticament consistent,
però en realitat el nom és dins d'aquest mateix camp,
així que ara tinc això.
Això també no se sent com el millor disseny que he codificat David.
He codificat Rob.
I encara he de recórrer a una còpia i pega cada vegada que vull noves variables.
D'altra banda, he de donar-li pel que sembla cadascuna d'aquestes variables un nom,
encara que jo preferiria descriure aquestes variables
estudiants més genèricament.
>> Ara podem combinar les idees que han estat treballant bé per a nosaltres
i en lloc de dir: "Saps què, dóna'm uns estudiants anomenats variables,
i haurem de ser de mida 3 ", de manera que ara pot refinar més a fons,
desfer-se del manual declarar David,
i que en el seu lloc pot dir una cosa així com estudiants [0] aquí.
Llavors puc dir que els estudiants [0] aquí,
estudiants [0] aquí, i així successivament, i em pot donar la volta
i netejar això per Rob.
Jo també podria anar I ara potser afegint un bucle
i l'ús de GetString i getInt per aconseguir realment aquests valors per part de l'usuari.
Podria seguir sobre com afegir una constant perquè això és generalment una mala pràctica
per codificar un nombre arbitrari com 3 aquí
i llavors només recorda que has de triar un màxim de 3 alumnes al mateix.
Probablement seria millor fer servir # defineix a la part superior del meu arxiu
i el factor que fos, així que en realitat, deixa seguir endavant i generalitzar això.
>> Permetin-me obrir un exemple que es troba entre l'actual
exemples d'antelació, structs1.
Es tracta d'un programa més complet que utilitza # defineix aquí
i diu que tindrem 3 estudiants per defecte.
Aquí estic declarant un valor de classe dels estudiants,
de manera que un saló de classes dels estudiants, i ara estic fent servir un bucle
només per fer el codi una mica més elegant, popular la classe
amb l'entrada de l'usuari, de manera iterar des i = 0 en fins a estudiants, que és 3.
I llavors demanar a l'usuari en aquesta versió
Quin és l'ID de l'estudiant, i ho aconsegueix amb getInt.
Quin és el nom de l'estudiant, i després em poso amb GetString.
Què és la casa de l'estudiant? Ho entenc amb GetString.
I després al final aquí em vaig decidir a canviar
com estic imprimint aquests i utilitzar realment un bucle,
I qui sóc jo imprimir?
D'acord amb el comentari que estic imprimint a ningú en Mather,
i això és tot el que Rob i Tommy i així successivament en realitat-de Tommy en Mather.
Tommy i David s'imprimiria en aquest cas, però, com funciona això?
No hem vist aquesta funció abans, però prendre una conjectura pel que fa al que fa.
Compara cadenes.
>> És una mica no és evident com es compara cadenes perquè resulta
si retorna 0, que significa que les cadenes són iguals.
Si torna un -1 significa que un ve alfabèticament abans que l'altre,
i si retorna una paraula que significa l'altre ve alfabèticament
abans que l'altre, i es pot veure en línia oa la pàgina de manual
per veure exactament on és el que, però tot això està fent ara és el que està dient
si el [i]. casa és igual a "Mather"
a continuació, seguir endavant i imprimir això i allò altre està en Mather.
Però això és una cosa que no hem vist abans, i tornarem a això.
Jo no recordo haver hagut de fer això en qualsevol dels meus programes.
Gratuït aparentment en referència a la memòria, alliberant la memòria,
però el que la memòria m'estic alliberant pel que sembla en aquest bucle a la part inferior d'aquest programa?
Sembla que m'estic alliberant a nom d'una persona
i la casa d'una persona, però per què és això?
>> Resulta que totes aquestes setmanes que he estat usant GetString
hem anat introduint tipus d'un error en cada un dels seus programes.
GetString per disseny assigna memòria perquè pugui tornar a que una cadena,
com David, o Rob, i llavors pot fer el que vulguis
amb aquesta cadena en el seu programa, ja que hem reservat la memòria per a vostè.
El problema és que tot aquest temps cada vegada que truqui GetString
Nosaltres, els autors de GetString, han estat sol · licitant al sistema operatiu
per donar-nos una mica de RAM per a aquesta cadena.
Dóna'ns una mica de RAM per a aquesta cadena següent.
Dóna'ns una mica més RAM per a aquesta cadena següent.
El que vostè, el programador, mai han estat fent
que ens està donant de nou la memòria,
de manera que per a aquestes setmanes tots els programes que has escrit
han tingut el que es diu un salt memòria pel de seguir utilitzant
més memòria i més cada vegada que truqui GetString, i això està bé.
Ens deliberadament fer que en les primeres setmanes, perquè no és tan interessant
haver de preocupar d'on la cadena està venint.
Tot el que vull és la paraula Rob tornar quan l'usuari ho tipus polz
>> Però avançar ara hem de començar a aconseguir més sofisticat sobre això.
Cada vegada que assignar memòria serà millor que eventualment tornar.
En cas contrari, en el món real en el teu Mac o PC que pugui tenir de tant en tant amb experiència
símptomes que el seu equip està a punt de paralitzar-eventualment
o la pilota de platja estúpid gir s'acaba d'ocupar l'ordinador de
atenció sencera i no pots fer les coses.
Això pot ser explicat per qualsevol nombre d'errors, però entre els possibles errors
són coses que es diuen pèrdues de memòria mitjançant el qual una persona que va escriure aquest tros de programari
que està utilitzant no recordava per alliberar memòria
que ell o ella li va demanar al sistema operatiu per,
no utilitzar GetString, perquè això és una cosa CS50, però utilitzant funcions similars
que demanen que el sistema operatiu per a la memòria.
Si vostè o fiquen la pota i que en realitat mai tornar memòria
un símptoma que pot ser que un programa s'alenteix i retarda i redueix la velocitat
llevat que recordi trucar gratis.
>> Tornarem a quan i per què es diu lliure,
però seguirem endavant només per si de cas i tractar d'executar aquest programa en especial.
Això va ser anomenat structs1, introdueixi.
Deixin-me seguir endavant i executar structs1, 123, David Mather,
456, Rob Kirkland, 789,
Tommy Mather, i veiem a David en Mather, de Tommy en Mather.
Això és només una prova de seny poc que el programa està funcionant.
Ara, per desgràcia, aquest programa és una mica frustrant que
Vaig fer tot aquest treball, vaig escriure en 9 diferents cordes, prem enter,
se li va dir que estava en Mather, però òbviament jo sabia que estava en Mather i perquè el va escriure.
Seria bo si almenys aquest programa s'assembla més a una base de dades
i que en realitat recorda el que he escrit en
així que mai més hagi d'introduir aquests registres estudiantils.
Potser és com un sistema registrarial.
>> Podem fer això usant aquesta tècnica coneguda com a entrada d'arxiu de l'arxiu d'E / S i de sortida,
una manera molt genèrica de dir en qualsevol moment que desitgi llegir o escriure arxius dels arxius
vostè pot fer això amb un cert conjunt de funcions.
Deixin-me seguir endavant i obrir aquest structs2.c exemple,
que és gairebé idèntic, però anem a veure el que fa ara.
A la part superior de l'arxiu de declarar una classe d'estudiants.
I a continuació, omplir la classe amb l'entrada de l'usuari,
de manera que aquestes línies de codi són exactament com abans.
Llavors, si em desplaço fins aquí puc imprimir tots els que estan en Mather arbitràriament com abans,
però aquesta és una nova característica interessant.
Aquestes línies de codi són nous, i introdueixen alguna cosa aquí,
De arxius, tot en majúscules, i té * aquí també.
Permetin-me passar això aquí, a * per aquí també.
>> Aquesta funció no hem vist abans, fopen,
però significa obrir l'arxiu, així que anem a llegir-lo a través d'ells,
i això és una cosa que anem a tornar a conjunts de processadors futurs,
però aquesta línia aquí essencialment obre un arxiu anomenat base de dades,
i, específicament, s'obre de manera que pot fer el que a ell?
[Inaudible-alumne]
Bé, llavors "w" només vol dir que està dient al sistema operatiu
obrir aquest arxiu de manera que podia escriure-hi.
No vull que ho llegeixi. Jo no vull mirar només a ell.
Vull canviar i afegir coses potencialment a la mateixa,
i l'arxiu es dirà base de dades.
Això podria anomenar qualsevol cosa.
Això podria ser database.txt. Això podria ser. Db.
Això podria ser una paraula com foo, però arbitràriament va escollir el nom de la base de dades d'arxiu.
Aquesta és una prova de seny poc que tornarem en detall en el temps,
si dóna, per al punter d'arxiu, no significa NULL com tot està bé.
>> Llarga història curta, funciona com fopen vegades fallen.
Potser el fitxer no existeix. Potser t'has quedat sense espai de disc.
No sé si vostè té permís per a aquesta carpeta,
pel que si fopen retorna alguna cosa nul dolent ha passat.
En canvi, si no torna fopen nul tot està bé
i puc començar a escriure en aquest arxiu.
Aquest és un truc nou.
Es tracta d'un bucle perquè es itera sobre cadascun dels meus estudiants,
i això es veu molt similar al que hem fet abans,
però aquesta funció és un cosí de l'anomenada printf printf fprintf per arxiu,
i nota que és diferent en tan sols 2 maneres.
Un d'ells, que comença amb F en lloc de p,
però després el seu primer argument és aparentment el que?
[Els estudiants] de l'arxiu. >> Es tracta d'un arxiu.
Aquesta cosa anomenada fp, que finalment va separar el que és un apuntador d'arxiu,
però per ara simplement fp representa l'arxiu que he obert,
fprintf aquí per imprimir aquesta dient ID de l'usuari a l'arxiu, no a la pantalla.
Imprimir el vostre nom en el fitxer, no a la pantalla,
la casa a l'arxiu, no a la pantalla, i després aquí, òbviament,
tancar el fitxer, i després cap avall aquí lliurement la memòria.
>> L'única diferència entre aquesta versió i la versió 1 feb
és la introducció d'fopen i aquest fitxer *
i aquesta noció de fprintf, així que anem a veure el que el resultat final és.
Deixa anar al meu finestra de terminal.
Deixa córrer structs2, introdueixi.
Sembla que tot està bé. Anem a tornar a executar structs2.
123, David Mather, 456, Rob Kirkland,
789, Tommy Mather, introdueixi.
Sembla que es comportaven de la mateixa, però si ara faig ls
compte del que està a l'arxiu aquí entre tota la meva codi, base de dades,
així que anem a obrir aquesta, gedit de base de dades, i veure això.
No és la més sexy de formats d'arxiu.
Realment és un tros de línia de dades per línia per línia,
però aquells de vostès que fan servir arxius d'Excel o CSV, valors separats per comes,
Certament podria haver utilitzat fprintf fer en el seu lloc potser una mica com això
pel que jo podia crear l'equivalent d'un arxiu d'Excel
en separar amb comes coses, no només les noves línies.
>> En aquest cas, si hagués utilitzat en lloc comes en lloc de línies noves
Jo, literalment, podria obrir el fitxer de base de dades en Excel si en canvi ho va fer veure com això.
En resum, ara que tenim el poder per escriure en arxius
ara podem començar a dades persistents, mantenint al voltant del disc
perquè puguem mantenir la informació al voltant d'una i una altra.
Tingueu en compte un parell de coses més que ara són una mica més familiar.
A la part superior d'aquest arxiu C tenim un typedef
perquè volíem crear un tipus de dades que representa una paraula,
pel que aquest tipus s'anomena paraula, ia l'interior d'aquesta estructura
que és una mica més de luxe ara.
Per què és una paraula composta de semblar una matriu?
Què és una paraula que només intuïtivament?
>> És una sèrie de caràcters.
És una seqüència de caràcters esquena amb esquena amb esquena.
Lletres en majúscules resulta ser arbitràriament dir la longitud màxima
de qualsevol paraula al diccionari que utilitzeu per Scramble.
Per què tinc un +1?
El caràcter nul.
Recordem quan vam fer l'exemple Bananagrams necessitàvem un valor especial
al final de la paraula per tal de seguir la pista
d'on les paraules en realitat va acabar, i com l'especificació del conjunt de problema, diu
aquí estem associant amb una paraula donada un valor boolean,
una bandera, per dir-ho, certa o falsa.
Has trobat ja aquesta paraula, perquè ens adonem de
Realment necessitem una manera de recordar no només el que una paraula està en Scramble
però si no és així, l'humà, ho he trobat
així que si vostè troba la paraula "the" No es pot escriure el, entrar, el, entrar, la, introduïu
i obtenir 3 punts, 3 punts, 3 punts, 3 punts.
Volem ser capaços de posar en llista negra la paraula mitjançant l'establiment d'un bool
en true si ja l'has trobat, i per això ens
encapsulada en aquesta estructura.
>> Ara, aquí a Scramble hi ha aquesta altra estructura anomenada diccionari.
En absència d'aquí és la paraula typedef perquè en aquest cas
necessitàvem per encapsular la idea d'un diccionari,
i un diccionari conté un munt de paraules,
com es dedueix d'aquesta matriu, i quantes d'aquestes paraules hi ha?
Bé, sigui aquesta mida variable anomenada diu.
Però només tenim un diccionari.
No necessitem un tipus de dades anomenat diccionari.
Només tenim un d'ells, pel que resulta en C
que si no dius typedef, que acaba de dir struct, a continuació, dins de les claus
vostè posa les seves variables, a continuació, posar el nom.
Això es declara una variable anomenada diccionari
que són aquestes.
Per contra, aquestes línies estan creant una estructura de dades reutilitzable anomenat paraula
que es poden crear múltiples còpies d', igual que hem creat
diverses còpies dels estudiants.
>> Què significa aquest darrer terme ens permet fer?
Deixa tornar a, diguem, un exemple més simple de temps més senzills,
i em va deixar obrir, diguem, compare1.c.
El problema en qüestió és en realitat pelar
la capa d'una cadena i començar a enlairar aquestes rodes d'entrenament
perquè resulta que una cadena tot aquest temps
és com vam prometre en la setmana 1 realment només un sobrenom,
un sinònim de la biblioteca CS50 per a alguna cosa que s'assembla una mica més críptic,
char *, i hem vist aquest estel abans.
Ho vam veure en el context dels arxius.
>> Ara veurem per què hem estat ocultant aquest detall des de fa algun temps.
Aquí hi ha un arxiu anomenat compare1.c,
i, pel que sembla, li demana a l'usuari 2 cadenes, s i t,
i després es tracta de comparar aquestes cadenes per a la igualtat en la línia 26,
i si són iguals es diu, "Vostè va escriure la mateixa cosa"
i si no som iguals diu: "Ha escrit coses diferents".
Deixin-me seguir endavant i executar aquest programa.
Deixa anar al meu directori d'origen, faci una compare1. Es compila bé.
Deixa córrer compare1.
Vaig a apropar, introduir.
Digui alguna cosa. HELLO.
Vaig a dir alguna cosa nova. HELLO.
Sens dubte no escrigui coses diferents.
>> Déjame intentar-ho de nou. BYE BYE.
Definitivament no és diferent, així que el que està passant aquí?
Bé, el que realment es comparen en la línia 26?
[Inaudible-alumne]
Sí, pel que resulta que una cadena, tipus de dades, és una mena de mentida piadosa.
Una cadena és un char *, però el que és un char *?
Un char *, com es diu, és un punter,
i un punter és una adreça efectiva,
suma una ubicació en la memòria, i, si per casualitat vostè ha escrit en una paraula com HOLA
Recordo les discussions anteriors de cadenes
això és com la paraula HOLA.
Recordeu que una paraula com HOLA es pot representar
com una sèrie de personatges com aquest
i després amb un caràcter especial a l'extrem anomenat el caràcter nul,
com la denota \.
Què és en realitat una cadena?
Observi que aquest és diversos fragments de memòria,
i de fet, al final d'ella només es coneix un cop vista a través de tota la cadena
buscant el caràcter nul especial.
Però si això és un tros de memòria de la memòria del meu ordinador,
direm arbitràriament que aquesta cadena només vam tenir sort,
i es va quedar col · locat al començament mateix de la RAM del meu ordinador.
Aquest byte és 0, 1, 2, 3, 4, 5, 6 ...
>> Quan dic alguna cosa com GetString i faig string s = GetString
el que realment es retorna?
Per aquestes últimes setmanes, el que realment està sent emmagatzemat en s
no és aquesta cadena per se, però en aquest cas és el que s'està emmagatzemat
el nombre 0, perquè el que en realitat fa GetString
és que no físicament tornar una cadena.
Això no té molt sentit conceptual.
El que fa de retorn és un nombre.
Aquest nombre és l'adreça de HOLA en la memòria,
i la cadena de s llavors, si pelar aquesta capa, la cadena no existeix realment.
No és més que una simplificació a la biblioteca CS50.
>> Això realment és una cosa que es diu char *.
Char té sentit perquè, què és una paraula, com HOLA?
Bé, és una sèrie de caràcters, una sèrie de caràcters.
Char * vol dir que la direcció d'un personatge,
així que, què significa per tornar una cadena?
Una manera agradable i senzilla de retornar una cadena
és més aviat que tractar d'esbrinar com torno a 5 o 6 bytes diferents
permetin-me tornar a la direcció de la qual byte?
La primera d'elles.
En altres paraules, et vaig a donar la direcció d'un personatge en la memòria.
Això és el que representa char *, la direcció d'un únic caràcter en la memòria.
Truqui a aquesta variable s.
Conservar en aquesta direcció particular s, el que em va dir és arbitràriament 0,
només per mantenir les coses simples, però en realitat és en general un nombre més gran.
>> Espera un minut.
Si només em dóna la direcció del primer caràcter, com puc saber quina és la direcció és
el segon caràcter, la tercera, la quarta i cinquena de la?
[Inaudible-alumne]
Només se sap on és el final de la cadena és per mitjà d'aquest truc molt útil,
així que quan vostè fa servir alguna cosa com printf, el que printf, literalment, pren com a argument,
Recordem que usem aquest marcador de posició% s, i després es passa a
la variable que s'emmagatzema una cadena.
El que en realitat passa és la direcció del primer caràcter de la cadena.
Printf continuació, utilitza un bucle for o un bucle while com rebi l'esmentada direcció,
per exemple, 0, així que vaig a fer això ara,
printf ("% s \ n", s);
Quan dic printf ("% s \ n", s), el que realment estic proporcionant amb printf
és la direcció del primer caràcter en si, que en aquest cas és arbitrari H.
>> Com printf saber què és exactament el que es mostrarà a la pantalla?
La persona que va implementar printf implementat un bucle while o bucle for
que diu que aquest personatge és igual al caràcter nul especial?
Si no, ho imprimeixi. Com va aquest?
Si no s'imprimeix, imprimir, imprimir, imprimir-la.
Oh, aquest és especial. La impressió s'atura i retorna a l'usuari.
I això és literalment tot el que ha estat succeint per sota de la campana,
i això és molt per pair el primer dia de classe,
però per ara és realment la clau de volta de tot enteniment
que ha estat succeint dins de la memòria del nostre ordinador,
i, finalment, anem a molestar aquest part amb una mica d'ajuda
d'un dels nostres amics de Stanford.
>> El professor Nick Parlant de Stanford ha fet aquesta seqüència meravellós vídeo
de tot tipus de llengües diferents que van introduir
aquest Claymation poc Binky caràcter.
La veu que vostè està a punt d'escoltar un avançament en només pocs segons Sneak
és el d'un professor de Stanford, i vostè està rebent
només 5 o 6 segons d'això ara mateix,
però aquesta és la nota en la que celebrarem avui
i començarà dimecres.
Et dono Fun punter amb Binky, la vista prèvia.
[♪ ♪ Music] [Professor Parlant] Hey, Binky.
Desperta. És temps per a la diversió punter.
[Binky] Què és això? Aprendre sobre els punters?
Oh, que bé!
>> Ens veiem el dimecres.
[CS50.TV]