[Powered by Google Translate] [Setmana 6] [David J. Malan] [Harvard University] [Aquesta és CS50.] [CS50.TV] 

Això és CS50, i aquest és el començament de la Setmana 6, així que un parell de noves eines ja estan disponibles per tu per aprofitar, el primer dels quals es diu CS50 estil. El més probable és que si ets com jo o qualsevol dels companys docents, del que has vist un programa l'estil s'assembla una mica alguna cosa com això. Potser vostè comenci a tallar algunes cantonades a altes hores de la nit, o va a lluitar amb ell més tard, i després un TF o CA ve en horari d'oficina. Llavors és difícil per a nosaltres llegir. Doncs bé, aquest codi és sintàcticament correcta, i compilar voluntat, i s'executarà en realitat. Però definitivament no és un 5 per estil. 

Però ara, si ens endinsem en aquest directori here- i noti que tinc conditions2.c- i em trobo amb aquest nou ordre, style50, en aquesta conditions2.c arxiu, Intro, compte que m'ha informat que ha estat estilitzada. Gedit adonar que l'arxiu ha estat canviat al disc, i si faig clic a recarregar, tots els seus problemes s'han automatitzat. [Aplaudiment] Aquesta és una de les coses que vam fer aquest cap de setmana. Reconeixem que és imperfecte, perquè hi ha una mica de codi que simplement no serà capaç d'estilitzar perfectament, però s'adonen això és ara una eina que pot aprofitar encara que només sigui per posar en ordre alguns dels aparells més equivocadament col · locat claus i similars. 

Però ara és més convincent CS50 Check. Amb CS50 xec, vostè pot realitzar les proves de regularitat mateixos en el seu propi codi que els becaris d'ensenyament són capaços de fer-ho. Aquesta és una utilitat de línia de comandes que es proporciona en l'aparell tan aviat com ho fa un update50 com per pset 4 especificacions, i l'utilitza essencialment com aquest. Executa la comanda check50. Després es passa un argument de línia d'ordres, o més generalment conegut com un interruptor o una bandera. En general, les coses que tenen guions es diu un interruptor a un programa de línia de comandes, de manera que-c especifica els xecs que desitja executar. 

Les proves que desitja executar s'identifiquen individualment per aquesta cadena, 2012/pset4/resize. En altres paraules, això és només una cadena arbitrària però única que utilitzem per identificar de forma exclusiva les proves 4 pset de correcció. I llavors s'especifica una llista separada per espais dels arxius que voleu carregar per CS50 Check per a la seva anàlisi. Per exemple, si entro a la meva solució aquí per resize.c- permetin-me obrir un terminal més gran de finestra i segueixo endavant i executar diguem check50-c 2012/pset4/resize, i després seguir endavant i especificar els noms dels arxius, resize.c, a continuació, premeu la tecla Enter, es comprimeix, que es carrega, es comprova, i m'acaba de fallar un munt de proves. Qui està en vermell a la part superior esquerra que diu resize.c i bmp existeix. Aquesta era la prova. Aquesta va ser la pregunta que ens fèiem. I és trist perquè la resposta era falsa. El text en blanc sota ella diu espera bmp.h d'existir, i això és simplement la meva culpa. Em vaig oblidar de pujar, així que he de pujar dos arxius, resize.c i bmp.h. Però ara notin totes les altres proves són de color groc perquè no s'han executat, de manera que la cara somrient és vertical perquè no és ni alegre ni trist, però hem de corregir aquest problema en vermell abans que aquests altres controls s'executarà. 

Anem a arreglar això. Permetin-me fer un zoom cap a fora i tornar a executar aquesta, aquest cop amb bmp.h també en la línia d'ordres, escriviu, i ara, si tot va bé, que va a revisar i tornar a conseqüència d'aguantar la respiració- tot verd, el que significa que estic fent realment bé en pset 4 fins al moment. Vostè pot veure i deduir del text descriptiu aquí exactament què és el que vam provar. Provem primer què els arxius existeixen? Hem provat llavors es compila resize.c? Després vam provar no canviar la seva mida una BMP de 1x1 píxels quan n, el factor de canvi de mida, és 1. Ara, si vostè no té idea del que n és que una vegada que explorem pset 4, sinó que simplement és un simple control per assegurar-se que vostè no és el canvi de mida una imatge en absolut si el factor de canvi de mida 1. Si, per contra, canvia la mida d'un píxel de 1x1 per a un 1x1 2x2 píxels a BMP correctament quan n és 2, llavors similarment, mina de forma consegüent. 

En definitiva, es pretén, un, prendre la cruïlla dels dits fora de l'equació adequada per a vostè abans de presentar el seu conjunt de processadors. Vostè sabrà exactament el que el seu TF aviat sabrà quan vostè va sobre la presentació d'alguns d'aquests conjunts de problemes, i també la motivació pedagògica és realment posar l'oportunitat davant teu perquè quan es coneix a priori que no hi ha errors en el codi i proves que no es passen, vostè pot posar en més temps efectiu per avançat per resoldre aquests problemes en lloc de perdre punts, obtenir retroalimentació de la seva TF, i després, "Ahh," com jo hauria d'haver imaginat. Ara almenys hi ha una eina per ajudar a trobar això. No va a assenyalar que l'error és, però li dirà el que és un símptoma de la mateixa. 

Ara s'adonen que les proves no són necessàriament exhaustives. El fet que vostè rep una pàgina amb la cares somrients verd no significa que el seu codi és perfecte, però significa que ha passat certes proves prescrites per l'especificació. De vegades no ens donarà a conèixer els xecs. Per exemple, whodunit, un dels aspectes del conjunt de processadors 4, és una mica decebedor si li donem la resposta en quant al que és, i hi ha un nombre de maneres de revelar que la persona està en que el soroll vermell. L'especificació sempre s'especificaran en el futur per pset 5 en endavant quins controls hi per a tu. Es donarà compte de que hi ha aquesta URL blanc a la part inferior. Per ara, això és només la sortida de diagnòstic. Si vas a visitar aquesta URL, tindràs un munt de missatges críptics bojos, que el convidem a mirar a través, però és sobretot per al personal perquè puguem diagnosticar i depurar errors en check50 si mateix. 

Sense preàmbuls, anem a passar a on el deixem. CS50 biblioteca prenem per fet durant algunes setmanes, però la setmana passada, vam començar traient una de les capes de la mateixa. Comencem posant de banda cadena a favor del que en el seu lloc? [Els estudiants] Char. * Char, que ha estat un char * tot aquest temps, però ara no hem de fer veure que és una cadena de dades actual tipus. Més aviat, ha estat un sinònim de tipus de char *, i una cadena és una seqüència de caràcters, Per què té sentit per representar cadenes com char * s? Què fa un char * representen en el context d'aquest concepte d'una cadena? Si. >> [Estudiant] El primer caràcter. Bé, el primer caràcter, però no és el primer caràcter. Són els-[Els estudiants] Direcció. Bé, la direcció del primer caràcter. Tot el que és necessari per representar una cadena a la memòria d'un ordinador és només l'adreça de la seva byte molt primer. Vostè ni tan sols ha de saber quant temps és perquè com pot vostè donar-se compte d'això dinàmicament? [Estudiant] longitud de cadena. Vostè pot trucar longitud de la cadena, excel · lent, però com funciona la cadena de longitud? Què fer? Si. [Estudiant] Segueix endavant fins que arribi el caràcter nul. Sí, exacte, simplement itera amb un bucle for, while, el de * fins al final, i el final està representat per \ 0, el caràcter nul trucada, nul, no confondre amb un valor nul, que és un punter, que entrarà en la conversa de nou avui. 

Ens va desprendre una capa de getInt, i després va fer una ullada a GetString, i recordar que aquestes dues funcions, o en realitat, GetString, utilitzava una determinada funció per analitzar en realitat, és a dir, llegir i analitzar, l'entrada de l'usuari. I quina era aquesta nova funció? Scanf o sscanf. En realitat, ve en sabors diferents. Hi ha scanf, hi sscanf, hi fscanf. Per ara, però, ens centrarem en la més fàcilment il · lustrat, i m'ho dius a mi seguir endavant i obrir l'aparell un arxiu d'aquest tipus, scanf1.c. Aquest és un programa super simple, sinó que fa una cosa que mai hem fet sense l'ajuda de la biblioteca CS50. Això aconsegueix un int d'un usuari. Com funciona? Doncs bé, en la línia 16 hi, adonar que declarem una x int anomenat, i en aquest moment de la història, Quin és el valor de x? [Resposta dels estudiants inaudible] [David M.] És clar, qui sap, algun valor potencialment escombraries, de manera que en el 17, que acabem d'indicar a l'usuari dóna'm un nombre, si us plau, i el pas 18 és on es posa interessant. Scanf sembla demanar prestada una idea de printf en que utilitza aquests codis de format entre cometes. D% és per suposat un nombre decimal. Però per què estic passant & x en lloc de x només? El primer és la correcta. Si. [Resposta dels estudiants inaudible] Exactament, si l'objectiu d'aquest programa, igual que el getInt funció en si mateixa, és aconseguir un int per part de l'usuari que pot passar funcions totes les variables que vull, però si no passar-los per referència o per adreça o punter, tots sinònims per als propòsits actuals, després que la funció no té la capacitat de canviar el contingut d'aquesta variable. Això passaria en una còpia de la mateixa manera que la versió amb errors d'intercanvi que ja hem parlat un parell de vegades ara. 

Però en canvi, en fer & x, estic literalment passant a què? [Estudiant] La direcció. >> La direcció de x. És com dibuixar un mapa per a la funció anomenada scanf i dient aquí, aquestes són indicacions de com un tros de memòria a l'ordinador que es pot anar emmagatzemar algun sencer polz Per sscanf fer ara que quin operador, quin tros de sintaxi es va a haver de fer servir encara que no podem veure perquè algú va escriure aquesta funció? En altres paraules - què és això? [Estudiant] X llegir. Serà una mica de lectura, però només pel que fa a x aquí. Si scanf s'està passant la direcció de x, sintàcticament, quin operador està obligat a existir en algun lloc dins de l'aplicació, de manera que scanf scanf en realitat es pot escriure un nombre de 2 a aquesta direcció? Sí, així que l'arxiu *. Recordem que el * és el nostre operador per desfer referències, que essencialment significa anar-hi. 

Quan hagi estat lliurada una adreça, com és el cas aquí, scanf és, probablement-si en realitat es veia voltant del seu codi font- fa * x o l'equivalent d'anar realment a aquesta direcció i posar una mica de valor allà. Ara, pel que fa a com scanf té entrada des del teclat, anem a agitar les nostres mans per avui. Simplement assumeix que el sistema operatiu permet parlar sscanf per el teclat de l'usuari, però en aquest punt ara en línia 19, quan simplement imprimir x, que sembla ser el cas scanf que ha posat en int x. Així és exactament com funciona scanf, i recordar la setmana passada així és exactament com GetString i getInt i la seva altra família de funcions en última instància, funciona, encara que amb una lleugera variació com sscanf, el que significa escanejar una cadena en lloc del teclat. Però donem una ullada a una variació poc d'això. En scanf2, realment fotut. El que està malament, i jo vaig a amagar el comentari que explica tant- el que està malament amb aquest programa, la versió 2? Sigui el més tècnica possible aquest moment. Es veu bastant bé. Està molt ben marcada, però- bé, què hem de podar fins més curtes preguntes? Línia 16. Quina és la línia 16 fa en anglès precisa però tècnica? Aconseguir una mica incòmode. Sí, Michael. [Estudiant] S'assenyala a la primera lletra d'una cadena. 

Bé, prop. Permetin-me d'ajustar una mica. Referint-se a la primera lletra d'una cadena, es declara una variable anomenada memòria intermèdia que apunti a la direcció primera d'una cadena, o més aviat, que s'assenyalen més específicament a un char. Tingueu en compte que no és en realitat apunta enlloc perquè no hi ha cap operador d'assignació. No hi ha cap signe d'igual, així que tot el que estem fent és assignar la memòria intermèdia anomenat variable. Li passa a ser de 32 bits, ja que és un punter, i el contingut del buffer presumiblement eventualment contindrà la direcció d'un char, però per ara, el que conté buffer? Només una mica fals, qui sap, una mica d'escombraries valor, perquè no s'ha inicialitzat explícitament, de manera que no s'ha d'assumir res. Bé, ara la línia 17 és-què significa fer la línia 17? Potser això s'escalfarà això. S'imprimeix una cadena, no? Imprimeix cadena si us plau. 

La línia 18 és una mena de familiar ara que acabem de veure una variació d'aquesta però amb un codi de format diferent, de manera que en la línia 18, li estem dient aquí scanf és la direcció d'un tros de memòria. Vull que soni en una cadena, com es dedueix de% s, però el problema és que no hem fet un parell de coses aquí. Quin és un dels problemes? [Estudiant] Està tractant d'eliminar la referència a un punter nul. Bé, punters nuls o simplement desconeix el contrari. Ets lliurant scanf una direcció, però que acaba de dir fa un moment que aquesta direcció és un valor escombraries perquè en realitat no ens assignar-la a res, i pel que estem dient scanf disponible ens va posar una corda aquí, però no sabem on és aquí encara, pel que no s'han assignat per a la memòria buffer. D'altra banda, el que tampoc són encara comptant scanf? Suposem que es tractava d'un tros de memòria, i no era un valor escombraries, però encara no estàs dient scanf alguna cosa important. [Estudiant] Quan en realitat, el símbol d'unió. Ampersand, pel que en aquest cas, està bé. A causa de límit ja s'ha declarat com un apuntador amb la peça * de sintaxi, no cal utilitzar ampersand perquè ja és una direcció, però crec que el van escoltar aquí. [Estudiant] Com és de gran? Bé, no estem dient scanf el gran que és aquest tampó, el que significa que encara que tampó eren un punter, estem dient scanf, posar una cadena aquí, però aquí podria ser 2 bytes, que pot ser de 10 bytes, que podria ser un megabyte. Scanf té ni idea, i perquè es tracta d'un tros de memòria presumiblement, no és una cadena encara. No és més que una cadena un cop d'escriure caràcters i un 0 \ a que bona part de la memòria. Ara és només una mica de bona part de la memòria. Scanf no se sap quan deixar d'escriure a aquesta adreça. 

Si recorda alguns exemples en el passat en què s'escriuen a l'atzar en el teclat intentant desbordar un buffer, i parlem el divendres sobre exactament això. Si un adversari d'alguna manera injecta en el seu programa una paraula molt més gran o oració o frase després que esperaves pot envair un tros de memòria, que pot tenir conseqüències negatives, com fer-se càrrec de tot el programa en si. Hem d'arreglar això d'alguna manera. Permetin-me fer un zoom cap a fora i entrar a la versió 3 d'aquest programa. Això és una mica millor. En aquesta versió, notarà la diferència. En la línia 16, estic de nou que es declara una variable anomenada memòria intermèdia, però què passa ara? És un conjunt de 16 caràcters. Això és bo perquè significa que ara puc dir scanf aquí és un tros real de memòria. Gairebé es pot pensar a una matriu com punters ara, tot i que no són realment equivalents. Ells es comporten de manera diferent en diferents contextos. Però és cert que memòria intermèdia fa referència 16 caràcters contigus perquè això és el que una matriu és i ha estat durant algunes setmanes. 

Mira, estic dient scanf aquí hi ha un tros de memòria. Aquesta vegada, és en realitat una part de la memòria, però per què és aquest programa encara explotable? Què hi ha de dolent encara? Ho he dit dóna'm 16 bytes però- [Estudiant] I si s'escriu en més de 16? Exactament, què passa si l'usuari escriu en 17 caràcters o caràcters 1700? De fet, anem a veure si no es ensopegui amb aquest error ara. És millor, però no és perfecte. Deixin-me seguir endavant i fer funcionar scanf3 per compilar aquest programa. Deixa córrer scanf3, String si us plau: hola, i sembla que estem bé. Vaig a tractar un lleugerament més llarg, hola. Bé, anem a fer-ho hola com estàs avui, Enter. Aconseguir tipus de sort aquí, anem a dir hola com estàs. Maleïda sigui. Molt bé, així que vam tenir sort. A veure si podem arreglar això. No, no deixarà que em còpia. Anem a intentar-ho de nou. D'acord, espera. Anem a veure quant de temps pot pretendre concentrar sense deixar de fer això. Maleïda sigui. Això és bastant apropiat, en realitat. Aquí anem. Punt de fet. 

Això, compromès encara que també és, també és una de les fonts de gran confusió en escriure programes que tenen errors, ja que es manifesten només de tant en tant de vegades. La realitat és que encara que el codi està completament trencat, només podria ser completament trencat de tant en tant perquè de vegades, el que passa és essencialment el sistema operatiu assigna una mica més de memòria del que realment necessita per qualsevol raó, i perquè ningú més està utilitzant la memòria immediatament després del seu tros de 16 caràcters, així que si vas a 17, 18, 19, el que sigui, no és una gran cosa. Ara, l'equip, encara que no xoc en aquest punt, eventualment podria utilitzar el byte número 17 o 18 o 19 anys per a una altra cosa, moment en què les dades que vostè va posar en el seu lloc, encara que sigui excessivament llarg, serà sobreescrit potencialment per alguna altra funció. No necessàriament ha de romandre intacta, però no necessàriament causarà un error seg. Però en aquest cas, finalment em va proporcionar suficients caràcters que essencialment superat meu segment de la memòria, i bam, el sistema operatiu, va dir: "Em sap greu, això no és culpa bo, segmentació". 

I ara anem a veure si el que queda aquí en el meu directori adonar que tinc aquest arxiu aquí, el nucli. Tingueu en compte que això es va tornar a demanar un bolcat de memòria. Bàsicament es tracta d'un arxiu que conté el contingut de la memòria del programa en el punt en què es va estavellar, i només per provar un petit exemple aquí m'ho dius a mi entrar aquí i executar gdb en scanf3 i especifiqui un tercer argument anomenat nucli, i notar aquí que si la llista de codis, serem capaços, com de costum amb gdb per començar a caminar a través d'aquest programa, i puc córrer i tan bon punt em va colpejar, com a pas amb la comanda a gdb- tan bon punt vaig arribar a la línia potencialment amb errors després d'escriure en una cadena enorme, Vaig a ser capaç d'identificar realment aquí. Més sobre això, però, en la secció en termes de bolcats de memòria i similar, de manera que en realitat es pot furgar a l'interior del bolcat de memòria i veure en quina línia del programa que va fallar. Qualsevol pregunta llavors sobre indicadors i sobre les adreces? Perquè avui en endavant, anem a començar a donar per fet que aquestes coses existeixen i sabem exactament el que són. Sí 

[Estudiant] Com és que vostè no ha de posar un signe al costat de la part- Bona pregunta. Com arribar no havia de posar un signe al costat de la matriu de caràcters com ho vaig fer anteriorment amb la majoria dels nostres exemples? La resposta curta és arrays són una mica especial. Gairebé es pot pensar com un amortidor en realitat ser una adreça, i dóna la casualitat passar que la notació de claudàtors és una conveniència perquè puguem entrar en suport 0, suport 1, suport 2, sense haver d'utilitzar la notació *. Això és una mica d'una mentida piadosa perquè arrays i punters són, de fet, una mica diferent, però poden sovint, però no sempre s'usen de manera intercanviable. En resum, quan una funció espera un punter a un bloc de memòria, vostè pot passar una direcció que va ser retornat per malloc, i veurem malloc nou abans d'hora, o pot passar el nom d'una matriu. No ha de fer arranjaments amb ampersand perquè ja estan essencialment com adreces. Aquesta és l'única excepció. Els claudàtors fan especials. 

Podria posar un signe al costat del buffer? No en aquest cas. Això no funcionaria perquè, de nou, aquest cas de cantonada on les matrius no són realment molt adreces. Però potser tornarem a que en poc temps amb altres exemples. Tractarem de resoldre un problema. Tenim una estructura de dades que hem estat utilitzant des de fa algun temps es coneix com una matriu. El cas en qüestió, això és el que acabem de tenir. Però matrius tenen alguns upsides i desavantatges. Les matrius són agradables per què? Què és una cosa que es vol-en la mesura que t'agrada matrius-sobre les matrius? Què és convenient sobre ells? Què és convincent? Per què els introduïm en el primer lloc? Si. [Estudiant] Es pot emmagatzemar una gran quantitat de dades, i vostè no ha de fer servir una cosa sencera. Pot utilitzar una secció. Bé, amb un arsenal que pot emmagatzemar una gran quantitat de dades, i no necessàriament ha d'utilitzar tot això, així que vostè pot overallocate, que podria ser convenient si vostè no sap per endavant quants d'alguna cosa que esperar. 

GetString és un exemple perfecte. GetString, escrit per nosaltres, no té idea de com chars que cal esperar, de manera que el fet que es pot assignar trossos de memòria contigua és bo. Les matrius també resoldre un problema que vam veure un parell de setmanes ara on el codi comença a delegar en alguna cosa molt mal dissenyat. Recordem que he creat una estructura estudiant anomenat David, i llavors que era en realitat una alternativa, però, a tenir un nom de variable anomenada i una altra variable anomenada, crec, casa, i una altra variable anomenada identificació perquè en aquesta història que llavors volia introduir una mica més Igual que Rob en el programa, de manera que després vaig decidir esperar un minut, He de canviar el nom d'aquestes variables. Anem a trucar a la meva Nom1, ID1, house1. Anem a trucar a Rob nombre2, casa2, ID2. Però espera un moment, què passa amb Tommy? Després vam tenir tres variables més. Hem introduït algun altre, quatre conjunts de variables. El món va començar a causar problemes molt ràpidament, per la qual cosa va introduir les estructures, i el que és atractiu en una estructura? Què fa un struct C permeten fer? És molt difícil avui en dia. Què? >> [Resposta dels estudiants inaudible] Sí, en concret, typedef permet crear un nou tipus de dades, i estructura, la paraula clau struct, li permet encapsular peces relacionades conceptualment de dades, juntament i després d'això en diuen alguna cosa així com un estudiant. 

Això va ser bo, perquè ara podem modelar espècie molt més conceptualment coherent la noció d'un estudiant en una variable en lloc de tenir una forma arbitrària per una cadena, una per a un ID, i així successivament. Les matrius són agradables perquè ens permet començar a netejar el nostre codi. Però el que és un inconvenient ara d'una matriu? El que no pot fer? Si. [Estudiant] Vostè ha de saber el gran que és. Vostè ha de saber el gran que és, així que és un tipus de dolor. Aquells de vostès que tenen experiència prèvia en programació saben que en una gran quantitat d'idiomes, com Java, vostè pot demanar un tros de memòria, en concret una matriu, el gran que ets, amb una longitud, posició econòmica, per dir-ho, i això és molt convenient. En C, ni tan sols es pot trucar strlen en una matriu genèrica perquè strlen, com la paraula ho indica, és només per a cordes, i es pot calcular la longitud d'una cadena a causa d'aquesta convenció humana de tenir un 0 \, sinó una matriu, més genèricament, és només una part de la memòria. Si es tracta d'una matriu d'enters, no serà una cosa de caràcter especial al final t'espera. Cal recordar la longitud d'una matriu. Un altre aspecte negatiu d'una matriu aixecat el cap en GetString si mateix. Quin és altra desavantatge d'una matriu? Senyor, només tu i jo avui. [Resposta dels estudiants inaudible] >> És què? Ha declarat a la pila. D'acord, va declarar a la pila. Per què no t'agrada? [Estudiant] A causa que es reutilitzen. Es reutilitzen. Bé, si s'utilitza una matriu per assignar memòria, no es pot, per exemple, tornar perquè està a la pila. Bé, això és un desavantatge. I una altra amb una matriu? Quan l'assigni, ets una mica fotut si necessita més espai que la matriu té. 

A continuació presentem, recordar, malloc, que ens va donar la capacitat d'assignar dinàmicament la memòria. Però, i si intentem un món totalment diferent? Què passa si volem resoldre un parell d'aquests problemes així que en comptes, la meva ploma s'ha adormit aquí- I si en lloc volia crear essencialment un món que ja no és així? Aquesta és una matriu, i, per descomptat, aquest tipus d'es deteriora un cop es prem el final de la matriu, i ara ja no té espai per a un altre nombre enter o un altre caràcter. Què passaria si una espècie de forma preventiva dir així, per què no relaxar Aquest requisit que tots aquests trossos de memòria siguin contigus esquena amb esquena, i per què no, quan necessito un int o char a, m'acaba de donar espai per a una d'elles? I quan necessito un altre, dóna'm un altre espai, i quan necessito un altre, dóna'm un altre espai. L'avantatge que ara és que si algú més pren la memòria per aquí, res de l'altre món. Em quedo amb aquest tros addicional de memòria aquí i després d'aquest. 

Ara, l'únic problema aquí és que aquest gairebé se sent com si tingués un munt de diferents variables. Això se sent com cinc diferents variables potencialment. Però i si ens roben una idea de les cadenes d'alguna manera com puguem vincular aquestes coses conceptualment, i el que si em va fer això? Aquest és el meu fletxa molt mal dibuixat. Però suposem que cada un d'aquests trossos de la memòria va assenyalar a l'altra, i aquest noi, que no té germans, a la seva dreta, no té cap fletxa tals. Això és de fet el que s'anomena una llista enllaçada. Aquesta és una nova estructura de dades que ens permet assignar un bloc de memòria, després un altre, després un altre, després un altre, cada vegada que vulguem durant un programa, i recordem que tots estan d'alguna manera relacionats amb literalment encadenar junts, i ho vam fer aquí gràficament amb una fletxa. Però en el codi, quin seria el mecanisme a través del qual vostè pot connectar d'alguna manera, gairebé com Scratch, un fragment a un altre tros? Podríem utilitzar un punter, oi? Perquè, en realitat la fletxa que va des de la plaça superior esquerra, aquest tipus aquí a aquesta, podria contenir dins d'aquest quadrat no només alguns sencers, no només alguns char, però el que si realment assignats una mica més d'espai perquè ara, cada un dels meus trossos de la memòria, tot i que això costarà, ara es veu una mica més rectangular on un dels trossos de memòria s'utilitza per a un nombre, com el número 1, i després, si aquest noi emmagatzema el número 2, aquest fragment altre de memòria s'utilitza per una fletxa, o més concretament, un punter. I suposo que guardar el número 3 per aquí mentre jo faig servir això per apuntar a aquest tipus, i ara aquest tipus, suposarem que només vol tres trossos com de la memòria. Vaig a dibuixar una línia a través d'això, el que indica nul. No hi ha un caràcter addicional. 

De fet, així és com podem anar sobre l'aplicació una cosa que es diu una llista enllaçada. Una llista enllaçada és una estructura de dades nova, i és un pas endavant cap a molt més elegants estructures de dades que comencen a resoldre problemes al llarg de les línies dels problemes de tipus Facebook i Google problemes de tipus on hi ha enormes conjunts de dades, i ja no es talla per emmagatzemar tot contigua i usar alguna cosa com a recerca lineal o fins i tot alguna cosa com a recerca binària. Vols encara millors temps de carrera. De fet, un dels sants Grials parlarem més endavant aquesta setmana o la propera és un algorisme el temps d'execució és constant. En altres paraules, sempre es pren la mateixa quantitat de temps, sense importar el gran que és l'entrada, i que de fet seria convincent, fins i tot més que alguna cosa logarítmica. Què és això a la pantalla aquí? Cadascun dels rectangles és exactament el que acaba de dibuixar a mà. Però el que tot el camí de l'esquerra és una variable especial. Serà un únic punter perquè el Gotcha 01:00 amb una llista enllaçada, com es diuen aquestes coses, és que vostè ha de penjar en un extrem de la llista enllaçada. 

Igual que amb una cadena, vostè ha de saber la direcció del primer caràcter. Mateix tracte per les llistes enllaçades. Vostè ha de saber la direcció del primer fragment de memòria perquè a partir d'allà, es pot arribar a qualsevol altre. El dolent. Quin preu estem pagant per aquesta versatilitat de tenir una dinàmica estructura de dades important que si mai necessita més memòria, està bé, només assignar un tros més i dibuixar un punter de la vella a la nova cua de la llista? Si. [Estudiant] Es necessita espai d'aproximadament dues vegades més. Es necessita espai doble, així que això és definitivament un desavantatge, ja que hem vist aquest equilibri entre abans de temps i espai i flexibilitat on per ara, no necessitem 32 bits per a cada un d'aquests nombres. Realment necessitem 64, 32 per al nombre i 32 per al punter. Però bé, tinc 2 GB de RAM. Un augment de 32 bits aquí i aquí no sembla tan gran d'un acord. No obstant això, per als conjunts de dades enormes, que sens dubte es suma a, literalment, el doble. Quin és altra desavantatge ara, o quina funció li donem cap amunt, si representem llistes de coses amb una llista enllaçada i no una matriu? [Estudiant] No es pot recórrer cap enrere. No es pot recórrer cap enrere, així que ets una mica fotuts si tu te'n vas d'esquerra a dreta utilitzant un bucle o un bucle while i llavors te n'adones, "Oh, jo vull anar de nou al principi de la llista." No és possible perquè aquests punters només van d'esquerra a dreta, com indiquen les fletxes. 

Ara, vostè pot recordar el principi de la llista amb una altra variable, però això és una complexitat a tenir en compte. Una matriu, no importa el lluny que vagi, sempre pot fer menys, menys, menys, menys i torna d'on vas venir. Quin és altra desavantatge aquí? Si. [Pregunta estudiant inaudible] Podria, per la qual cosa ha fet que acaba de proposar una estructura de dades anomenada llista doblement enllaçada, i, de fet, hauria afegir un altre punter a cada un d'aquests rectangles que va l'altra direcció, l'avantatge que Ara es pot recórrer d'anada i tornada, el desavantatge que ara s'està utilitzant tres vegades més memòria que fem servir per i també afegir complexitat en termes del codi que ha d'escriure per fer-ho bé. Però tots aquests són potser les compensacions raonables, si la inversió és més important. Si. [Estudiant] Tampoc es pot tenir una llista enllaçada 2D. Bé, realment no es pot tenir una llista 2D vinculat. Podries. No és tan fàcil com una matriu. Igual que una matriu, fer claudàtor obert, suport tancat, suport obert, tancat suport, i s'obté una estructura de 2 dimensions. Es podria implementar una llista de 2 dimensions vinculades Si ho fa, com vostè proposa-un tercer indicador per a cadascuna d'aquestes coses, i si penses en una altra llista que li arriba estil 3D de la pantalla per a tots nosaltres, que és una altra cadena d'algun tipus. Podríem fer-ho, però no és tan simple com escriure obertura de claudàtors, claudàtors. Si. [Pregunta estudiant inaudible] Bé, així que això és un truc real. 

Aquests algorismes que hem sospirat altra vegada, com oh, recerca binària, vostè pot buscar en una matriu de nombres en el tauler o una llibreta de telèfons molt més ràpidament si utilitza divideix i venceràs i un algorisme de recerca binària, però la recerca binari requereix dos supòsits. Un d'ells, que les dades van ser ordenats. Ara, podeu mantenir aquesta resolt, així que potser això no és una preocupació, però també suposa la recerca binària que tenia accés aleatori a la llista de números, i una gran varietat li permet tenir accés a l'atzar, i per l'accés aleatori, Vull dir que si et donen una sèrie, quant de temps li pren per arribar al suport de 0? Una operació, vostè només ha d'utilitzar [0] i ja hi és. Quants passos es necessiten per arribar a la ubicació 10? Un pas, vostè només ha d'anar a [10] i que ets. Per contra, com s'aconsegueix que el sencer 10 en una llista enllaçada? Cal començar pel principi, ja que només està recordant el començament d'una llista enllaçada, igual que una cadena es recorda per la direcció del seu primer caràcter, i en veure que int 10 o que el caràcter 10 º en una cadena, vostè ha de buscar tota la maleïda cosa. 

Un cop més, no anem a resoldre tots els nostres problemes. Estem introduint altres nous, però realment depèn del que estiguis tractant de dissenyar per. Quant a l'aplicació d'aquesta, es pot demanar prestada una idea que l'estructura dels estudiants. La sintaxi és molt similar, excepte que ara, la idea és una mica més abstracte que la casa i el nom i DNI. Però jo proposo que podria tenir una estructura de dades en C que es diu node, com l'última paraula a la diapositiva indica, dins d'un node, i un node és un contenidor genèric en ciències de la computació. En general es dibuixa com un cercle o un quadrat o un rectangle com ho hem fet. I en aquesta estructura de dades, tenim un enter, n, pel que és el número que voleu emmagatzemar. Però què és aquesta segona línia, struct node * següent? Per què és correcte o quin paper té aquesta cosa, encara que és una mica críptic, a primera vista? Si. [Resposta dels estudiants inaudible] Exactament, de manera que el tipus de botí * que és un punter d'algun tipus. El nom d'aquest punter és arbitràriament proper, però ens podria haver anomenat qualsevol cosa que vulguem, però què té això punter a punt? [Estudiant] Un altre node. >> Exactament, apunta a un altre node tal. 

Ara, això és una mena de curiositat de C. Recordem que C és llegit per un compilador dalt a baix, d'esquerra a dreta, el que significa que si, això és una mica diferent del que hem fet amb l'estudiant. Quan definim un estudiant, que en realitat no va posar una paraula allà. Simplement va dir typedef. Després vam tenir id int nom, cadena, cadena de casa, i després estudiant a la part inferior de l'estructura. Aquesta declaració és una mica diferent, ja que, de nou, el compilador de C és una mica ximple. És només va a llegir de dalt a baix, així que si arriba a la 2 ª línia aquí on es declara pròxim i ho veu, oh, aquí hi ha una variable anomenada següent. És un punter a un node d'estructura. El compilador es donarà compte del que és un node d'estructura? Mai he sentit parlar d'això abans, perquè el node de paraula d'una altra manera no podria aparèixer fins a la part inferior, de manera que és aquesta redundància. Has de dir struct node aquí, que després es pot escurçar més tard gràcies a typedef aquí baix, però és perquè estem fent referència a l'estructura en si mateixa a l'interior de l'estructura. Aquest és el Gotcha ningú allà. 

Alguns problemes interessants sorgiran. Tenim una llista de nombres. Com inserir-hi? Com podem buscar? Com esborrar d'ella? Sobretot ara que hem de gestionar tots aquests consells. Vostè va pensar que eren punters espècie d'al · lucinant quan tenia un d'ells tractant de llegir un int a ella. Ara hem de manipular la pena una llista sencera. Per què no ens prenem el nostre fill de 5 minuts de descans aquí, i després vaig a portar algunes persones a l'escenari per fer exactament això. 

C és molt més divertit quan és representada. Que literalment vol ser el primer? Molt bé, anem a dalt. Vostè està en primer lloc. Qui vol ser 9? Bé, 9. Què hi ha de 9? 17? Una camarilla poc aquí. 22 i 26 a la fila davantera. I llavors què hi ha algú per aquí que se la mira. Vostè és 34. Bé, de 34 anys, anem a dalt. En primer lloc és allà. Bé, els quatre de vostès. I qui li diem a 9? Qui és el nostre 9? Qui realment vol ser 9? Molt bé, anem, a les 9. Aquí anem. 34, ens trobarem allà. La primera part és fer-vos veure així. 26, 22, 17, bo. Si pots suportar de banda, perquè ens malloc en un moment. 

Bé, bé. Està bé, excel · lent, així que anem a fer-li un parell de preguntes. I en realitat, quin és el teu nom? >> Anita. Anita, està bé, vine aquí. Anita ens ajudarà a resoldre un tipus de pregunta bastant simple en principi, que és com trobar si un valor és a la llista? Ara, notin que la primera, representada aquí per Lucas, és una mica diferent, de manera que el seu paper és deliberadament de banda perquè no és tan alt i no ocupa tants bits, tot i que tècnicament té la mateixa mida de paper que acaba de girar. Però és una mica diferent, ja que té només 32 bits per a un punter, i tots aquests nois són de 64 bits, la meitat dels quals és el nombre, la meitat dels quals és un punter. No obstant això, el punter no es representa, per tant si vostès podrien torpemente usi la mà esquerra per apuntar a la persona al teu costat. I tu ets el número 34. ¿Et dius? Ari. Ari, pel que en realitat, mantingui el paper a la mà dreta i la mà esquerra va cap avall. Vostè declara nul l'esquerra. 

Ara la nostra imatge humana és molt consistent. Això és realment com funcionen els punters. I si es pot arrugar una mica aquesta manera així que no estic en el teu camí. Anita aquí, em trobareu el número 22, però suposen una restricció dels éssers humans no suporta fulls de paper, però aquesta és una llista, i només té Lluc per començar perquè és, literalment, el primer indicador. Suposem que vostè mateix és un punter, i pel que també tenen la capacitat d'apuntar a alguna cosa. Per què no començar per assenyalar exactament el que Lluc està assenyalant? Bé, i dóna'm promulgar això per aquí. Només pel bé de la discussió, deixa que tiri cap amunt una pàgina en blanc aquí. Com s'escriu el teu nom? >> Anita. Bé, Anita. Diguem node * anita = lucas. Bé, no us crida lucas. Hauríem trucar a vostè primer. Per què és de fet compatible amb la realitat aquí? Un, en primer lloc ja existeix. En primer lloc s'ha assignat presumiblement en algun lloc per aquí. Node * primer, i s'ha assignat una llista d'alguna manera. No sé com va succeir. Això va passar abans que comencés la classe. Aquesta llista vinculada dels éssers humans ha estat creada. I ara, en aquest moment de la història, tot això succeeix en Facebook, aparentment després- en aquest punt de la història, Anita s'ha inicialitzat a ser igual al primer, el que no significa que els punts d'Anita a Lluc. Més aviat, apunta al que apunta perquè la mateixa direcció que està dins dels 32 bits - Lluc 1, 2, 3 - és ara també a l'interior d'Anita 32 bits - 1, 2, 3. 

Trobi ara 22. Com faria vostè per fer això? Què és aquest punt? >> Per al que sigui. Assenyaleu el que sigui, així que endavant i representar el millor que pots aquí. Bé, bé, i ara vostè està assenyalant, quin és el teu nom amb 22? Ramon. >> Ramon, de manera que Ramon és la celebració de 22. Ara ha fet un xec. Té Ramon == 22, i si és així, per exemple, es pot tornar realitat. Permetin-me, mentre aquests nois són aquí alguna cosa maldestre- m'ho dius a mi fer alguna cosa ràpidament com bool trobar. Vaig a seguir endavant i dir (llista de nodes *, int n). Estaré de tornada amb vostès. Només he d'escriure una mica de codi. I ara vaig a seguir endavant i fer això, el node * anita list =. I seguiré endavant i dir while (anita! = NULL). 

La metàfora aquí és aconseguir una mica estirat, però al mateix temps (anita! = NULL), què és el que vull fer? Necessito alguna manera de fer referència a el sencer que Anita està assenyalant. En el passat, quan vam estructures, que és un node, hem utilitzat la notació de punts, i ens diria alguna cosa així com anita.n, però el problema aquí és que Anita no és una estructura en si. Què és? Ella és un punter, així que realment, si volem utilitzar aquesta notació punt- i això va a semblar una mica críptic deliberadament- hem de fer alguna cosa com anar a mà esquerra el que Anita està apuntant a i després el camp anomenat núm. Anita és un punter, però el que és * anita? Què trobes quan vas al que Anita està assenyalant? Una estructura, un node, i una retirada node,, té un camp anomenat n perquè ha, recorden, aquests dos camps, pròxims i N, que vam veure fa un moment aquí. 

Per imitar aquest fet en el codi, podríem fer això i dir if ((* anita). == n n), la núm que jo estic buscant. Observeu que la funció es va aprovar en el nombre que m'importa. Llavors puc seguir endavant i fer alguna cosa com a veritable retorn. Si no, si aquest no és el cas, què és el que vull fer? Com tradueixo per codificar el que Anita va fer intuïtivament a peu a través de la llista? Què he de fer aquí per simular Anita donar aquest pas a l'esquerra, aquest pas cap a l'esquerra? [Resposta dels estudiants inaudible] >> Què és això? [Resposta dels estudiants inaudible] Bé, no és una mala idea, però en el passat, quan hàgim fet això, hem fet anita + + perquè això augmentaria el nombre 1 a Anita, que normalment apuntar a la següent persona, igual que Ramon, o la persona al seu costat, o la persona al seu costat de la línia. Però això no és molt bo, perquè el que aquí està aquesta cosa sembla a la memòria? No és això. Hem de desactivar això. Sembla que aquest en la memòria, i encara que he dibuixat 1 i 2 i 3 prop un de l'altre, si realment fer veure que aquesta-can nois, sense deixar d'apuntar a la mateixa gent, Potser alguns de vosaltres fer un pas enrere a l'atzar, alguns de vosaltres un pas endavant a l'atzar? 

Aquest desordre és encara una llista enllaçada, però aquests nois poden estar en qualsevol lloc en la memòria, així anita + + no funcionarà això? El que està en posició anita + +? Qui sap. És un altre valor que el que passa és que s'interposa entre tots aquests nodes d'atzar perquè no estem utilitzant una matriu. Hem assignat cadascun d'aquests nodes de forma individual. Bé, si vostès mateixos poden netejar de nou. Permetin-me proposar que en lloc de anita + +, que en comptes fer anita es- bé, per què no ens anem al que Anita està assenyalant i després fer. després? En altres paraules, anem a Ramon, que està sostenint el número 22, i llavors. següent és com si Anita es copia el punter esquerre. Però ella no va voler anar més enllà de Ramon perquè trobem 22. Però aquesta seria la idea. Ara, això és un embolic espantós. Honestament, potser hem oblidat aquesta sintaxi, i per sort, en realitat és una mica deliberada-oh, no va veure el que vaig escriure. Això seria més convincent si pogués. Voila! 

Darrere de les escenes, estava resolent el problema d'aquesta manera. Anita, per fer el pas a l'esquerra, en primer lloc, que et vagis a l'adreça que Anita està apuntant a i en la qual es troba no només n, que acaba de comprovar per efectes de comparació, però també es troba a prop - en aquest cas, Ramon mà esquerra apuntant al següent node a la llista. Però aquest és l'embolic espantós al qual m'he referit abans, però resulta que C ens permet simplificar això. En lloc d'escriure (* anita), es pot en comptes de escriure anita-> n, i és exactament el mateix funcionalment, però és molt més intuïtiu, i és molt més coherent amb la imatge que hem vingut assenyalant tot aquest temps utilitzant fletxes. 

Finalment, què és el que hem de fer al final d'aquest programa? Hi ha una línia de codi restant. Tornar què? Fals, perquè si arribem a través de tot el cicle while i Anita és, de fet, null, això vol dir que ella va ser tot el camí fins al final de la llista on ella assenyalava, quin és el teu nom? Mà esquerra Ari. >> Ari, que és nul. Anita és ara nul, i m'adono que vostè està aquí de peu amb malaptesa als llimbs perquè m'estic anant per un monòleg aquí, però et involucren de nou en un moment. Anita és nul en aquest punt de la història, de manera que el bucle while acaba, i hem de tornar falsa, perquè si ella té tot el camí a punter nul Ari llavors no hi havia un nombre que va buscar a la llista. Podem netejar això també, però aquesta és una aplicació molt bona llavors d'una funció de recorregut, una funció per trobar una llista enllaçada. Encara recerca lineal, però no és tan simple com un punter + + + + O una variable i perquè ara no podem endevinar on cada un d'aquests nodes són a la memòria. Hem de seguir literalment el rastre de molles de pa o, més específicament, punters, per anar d'un node a un altre. 

Ara anem a provar amb l'altra. Anita, vols tornar aquí? Per què no seguir endavant i assignar a una altra persona de l'audiència? Malloc-com et dius? >> Rebecca. Rebecca. Rebecca ha estat malloced de l'audiència, i ella està emmagatzemant el número 55. I l'objectiu que ens ocupa ara és que Anita per inserir Rebecca a la llista enllaçada aquí en el seu lloc apropiat. Vine aquí un moment. Jo he fet alguna cosa com això. He fet * node. I quin és el teu nom? Rebecca. >> Rebecca, està bé. Rebecca es malloc (sizeof (node)). Igual que hem destinat coses com els estudiants i altres coses en el passat, necessitem la mida del node, de manera que Rebecca ara està assenyalant en què? Rebecca té dos camps dins d'ella, un dels quals és 55. Anem a fer el que, Rebecca-> = 55. Però llavors Rebecca-> servidor ha d'-com ara, amb la mà és una espècie de qui sap? Està apuntant a un cert valor escombraries, així que per què no fer una bona mesura que almenys fer això perquè la mà esquerra està ara al seu costat. Ara Anita, a partir d'aquí. Cal Rebecca se li hagin assignat. Seguir endavant i trobar on hem de posar Rebecca. Bé, molt bé. Bé, bé, i ara necessitem que ens proporcioni una mica de direcció, pel que ha arribat a Ari. La seva mà esquerra és nul, però Rebecca pertany clarament a la dreta, així que com hem de modificar aquesta llista enllaçada amb la finalitat d'inserir Rebecca en el lloc apropiat? Si vostè pot literalment moure les mans de la gent d'esquerra al voltant de com sigui necessari, arreglarem el problema d'aquesta manera. Bé, bé, i mentrestant, la mà esquerra de Rebecca és ara al seu costat. 

Això va ser massa fàcil. Tractarem d'assignar-estem gairebé llestos, 20. Molt bé, anem a dalt. 20 ha estat assignat, així que vaig a seguir endavant i dir una altra vegada aquí que acabem de fer SAAD node *. Tenim malloc (sizeof (node)). A continuació, fer la mateixa sintaxi exacta com ho vam fer abans per a 20, i jo faré el següent = NULL, i ara li toca a Anita que s'insereix en la llista enllaçada, si poguessis jugar aquest mateix paper exacte. Executar. Bé, bé. Ara pensa detingudament abans de començar a moure les mans esquerra al voltant. Vostè té, amb molt, el paper més difícil avui en dia. La mà es va moure per primera vegada? Bé, espera, estic escoltant alguns no. Si algunes persones cortesament li agradaria ajudar a resoldre una situació difícil aquí. La mà esquerra ha de ser actualitzat primer, potser? Si. [Estudiant] Saad. Bé, Saad, per què, doncs? [Resposta dels estudiants inaudible] Bé, perquè si ens movem, quin és el teu nom? >> Marshall. Marshall, si movem la mà primer i deu en null, ara hem literalment orfes a quatre persones en aquesta llista perquè era l'únic que assenyala al Ramón i tothom a l'esquerra, de manera que l'actualització primer indicador era dolent. Anem a desfer això. Bé, i ara seguir endavant i moure la mà esquerra apuntant a l'adequat Ramon. Això se sent una mica redundant. Ara hi ha dues persones apuntant a Ramon, però això està bé perquè ara quina altra manera podem actualitzar la llista? El que per altra banda s'ha de moure? Molt bé, ara hem perdut la memòria? No, tot va bé, anem a veure si no podem trencar una vegada més. 

Mallocing per última vegada, el número 5. Tot el camí de tornada, anem cap avall. És molt emocionant. [Aplaudiment] ¿Et dius? >> Ron. Ron, està bé, està malloced com el número 5. Acabem d'executar codi que és gairebé idèntica a aquests amb un nom diferent. Excel · lent. Ara, Anita, bona sort inserir el número 5 a la llista ara. Bé, i? Molt bé, així que això és realment el tercer dels tres casos totals. Primer vam tenir algú a la final, Rebecca. Després vam tenir algú en el medi. Ara tenim a algú al començament, i en aquest exemple, que ara havia de actualitzar Lluc per primera vegada perquè el primer element a la llista ara ha de apuntar a un nou node, que, al seu torn, s'assenyala en el nombre de node 9. 

Aquesta va ser una demostració enormement difícil, estic segur, de manera que un gran aplaudiment per aquests nois si poguessis. Molt ben fet. Això és tot. Vostè pot guardar els seus trossos de paper com una mica de memòria. Resulta que fent això en el codi no és tan simple com moure les mans al voltant de i apuntant els punters en diferents coses. Però adonar-se que quan arribi el moment de posar en pràctica una mena una llista enllaçada o una variant d'aquest, si et centres en realitat aquests fonaments bàsics, els problemes de mida d'un mos que he de esbrinar, És aquesta mà o la mà d'això, adonar-se que el que és un programa bastant complex pot, de fet, ser reduït a elements bàsics bastant simples com aquest. 

Anem a prendre les coses en una direcció més sofisticat encara. Ara tenim la noció de la llista enllaçada. També tenim, gràcies al suggeriment de tornar-hi, una llista doblement enllaçada, que es veu gairebé el mateix, però ara tenim dos punters dins de l'estructura en comptes d'un, i probablement podríem anomenar els punters anterior i següent o cap a l'esquerra o cap a la dreta, però, de fet, la necessitat de dos d'ells. El codi hauria de ser una mica més complicat. Anita hauria hagut de fer més feina aquí a l'escenari. Però sens dubte podríem posar en pràctica aquest tipus d'estructura. En termes de temps d'execució, però, quin seria el temps d'execució per Anita de trobar un nombre n en una llista enllaçada ara? Així i gran O de n, així que no és millor que la recerca lineal. No podem fer una recerca binària, encara que, de nou. Per què va ser així? No es pot saltar al voltant. Tot i que, òbviament, veure tots els humans a l'escenari, i Anita podria haver eyeballed i va dir: "Aquí està la meitat de la llista," ella no sap que si ella fos el programa d'ordinador perquè l'únic que havia de aferrar-se a al començament de l'escenari va ser Lucas, que va ser el primer indicador. Ella necessàriament hauria de seguir aquests vincles, comptant el seu camí fins que va trobar aproximadament la meitat, i tot i així, ella no sabrà quan ella va arribar a la meitat llevat que hi va tot el camí fins al final per saber quants són, després fa marxa enrere, i això també seria difícil a menys que vostè tenia una llista doblement enllaçada d'algun tipus. 

Solució de problemes avui, però introduint altres. Què passa amb una estructura de dades completament diferent? Aquesta és una fotografia de les safates en Mather House, i en aquest cas, tenim una estructura de dades també hem de tipus ja s'ha parlant. Parlem d'una pila en el context de la memòria, i que és una espècie de anomenat perquè deliberadament una pila en els termes de la memòria és efectivament una estructura de dades que té més coses i més capes a la part superior de la mateixa. Però l'interessant d'una pila, com és el cas en la realitat, és que és un tipus especial d'estructura de dades. És una estructura de dades mitjançant el qual el primer element de és l'últim element fora. Si és la primera safata que es posa a la pila, que serà desgraciadament l'última safata a ser retirat de la pila, i això no és necessàriament una cosa bona. Per contra, es pot pensar que a l'inrevés, és l'últim dels primers a sortir. 

Ara, algun escenari vénen a la ment les de tenir una pila estructura de dades on s'ha de la propietat l'últim a entrar, primer a sortir, és realment convincent? ¿Això és bo? ¿Això és dolent? És definitivament una cosa dolenta si les safates no eren tots idèntics i tots eren diferents colors especials o el que sigui, i el color que vull és tot el camí a la part inferior. Per descomptat, vostè no pot aconseguir que, sense gran esforç. Cal començar per la part superior i treballi cap avall. De la mateixa manera, què passaria si fos un d'aquests nois del ventilador que espera tota la nit tractant d'aconseguir un iPhone i comarca en un lloc com aquest? ¿No seria agradable si la botiga d'Apple eren una estructura de dades de la pila? Yay? Nay? Només és bo per les persones que apareixen en l'últim minut i després es va treure de la cua. I de fet, el fet que estava inclinat de manera que dir cua en realitat és consistent amb el que podríem anomenar aquest tipus d'estructura de dades, una realitat on l'ordre no importa, i desitja que el primer a ser el primer a sortir encara que només sigui pel bé de la justícia humana. En general, vaig a trucar a això una estructura de dades cua. 

Resulta que a més de les llistes enllaçades, podem començar a utilitzar aquestes mateixes idees bàsiques i començar a crear nous i diferents tipus de solucions als problemes. Per exemple, en el cas d'una pila, que podria representar una pila utilitzant una estructura de dades com aquest, m'agradaria proposar. En aquest cas, he declarat una estructura, i ho he dit en l'interior d'aquesta estructura és una matriu de nombres i després una variable anomenada, i jo vaig a trucar a això una pila. Ara, per què aquesta realitat? En el cas d'una pila, podria treure això de manera efectiva a la pantalla com una matriu. Aquí està el meu stack. Aquests són els meus números. I anem a dibuixar com això, això, això, això, això. I després tinc algun membre de dades diferent aquí, que s'anomena grandària, de manera que aquest és la mida, i això és nombres, i col · lectivament, l'iPad sencer aquí representa una estructura de pila. Ara, per defecte, la mida presumiblement ha de ser inicialitzat a 0, i el que hi ha dins de la matriu de nombres inicialment quan per primera vegada assignar una matriu? Garbage. Qui sap? I en realitat no importa. Tant se val si és 1, 2, 3, 4, 5, completament a l'atzar per la mala sort emmagatzemada en l'estructura del meu perquè mentre jo sé que la mida de la pila és 0, llavors sé programació, no es veuen en cap dels elements de la matriu. No importa el que hi ha. No miris a ells, com seria la implicació d'una mida de 0. 

Però suposem ara segueixo endavant i inseriu alguna cosa a la pila. Vull inserir el número 5, de manera que posar aquí el número 5, i després ho poso aquí baix? Ara realment posar 1 per la mida, i ara la pila és de grandària 1. Què passa si segueixo endavant i afegir el nombre, diguem, 7 després? Això després s'actualitza a 2, i després farem 9, i després aquesta s'actualitza a 3. Però ara la característica interessant d'aquesta pila és que Se suposa que he de treure l'element que si vull fer esclatar alguna cosa fora de la pila, per així dir-ho? 9 seria el primer que ha d'anar. Com ha de canviar la imatge si vull treure un element de la pila, Igual que una safata en Mather? Si. >> [Estudiant] Fixar la mida a 2. Exactament, l'únic que fer és ajustar la mida a 2, i ho faig amb la matriu? Jo no he de fer res. Podria, només per ser anal, posar un 0 o -1 allà o alguna cosa per significar que aquest no és un valor de fiar, però això no importa perquè Puc gravar fora de la pròpia matriu quant temps és perquè jo sàpiga només es veu en els dos primers elements d'aquesta matriu. Ara, si em vaig i afegir el número 8 d'aquesta sèrie, com canviar la imatge a continuació? Això es converteix en 8, i això es converteix en 3. Vaig a tallar algunes cantonades aquí. Ara tenim 5, 7, 8, i estem de tornada a una mida de 3. Això és bastant fàcil d'implementar, però quan anem a lamentar aquesta decisió de disseny? Quan les coses comencen a anar malament, molt malament? Si. [Resposta dels estudiants inaudible] Quan vulgui tornar enrere i obtenir el primer element que vostè posa endins 

Aquí és tot i que una pila és una matriu sota la caputxa, aquestes estructures de dades que hem començat parlant també es coneix generalment com estructures abstractes de dades de manera que la forma en què s'implementen és completament en aquest punt. Una estructura de dades com una pila que se suposa per afegir suport operacions com d'empenta, que empeny una safata a la pila, i el pop, que elimina un element de la pila, i això és tot. Si es va a descarregar codi d'una altra persona que ja ha implementat això que s'anomena una pila, aquesta persona hauria escrit només dues funcions per a vostè, empenta i pop, amb un únic propòsit en la vida seria fer exactament això. Vostè o ell o ella qui va implementar aquest programa hauria estat completament el que decideix com implementar la semàntica d'empènyer i fer esclatar sota de la caputxa o la funcionalitat d'empènyer i fer esclatar. I he pres una decisió una mica miop aquí mitjançant la implementació del meu stack amb aquesta estructura de dades simple per què? Quan es fa aquesta ruptura estructura de dades? En quin moment he de tornar un error quan l'usuari crida push, per exemple? [Estudiant] Si no hi ha més espai. Exactament, si hi ha espai no més, si m'he excedit la capacitat, que és tot en majúscules, ja que suggereix que es tracta d'una espècie de constant global. Bé, llavors em vaig a haver de dir: "Ho sento, no puc empènyer altre valor a la pila ", igual que en Mather. 

En algun moment, arribaran a la part superior d'aquest armari petit. No hi ha més espai o la capacitat de la pila, moment en què hi ha algun tipus d'error. Han de posar l'element en un altre lloc, la safata en un altre lloc, o res en absolut. Ara, amb una cua, podríem aplicar una mica diferent. Una cua és una mica diferent en què sota la campana, es pot implementar com una matriu, però per què, en aquest cas, estic proposant tenir també un element de cap que representa el cap de la llista, al capdavant de la llista, la primera persona a la fila a la botiga d'Apple, a més de mida? Per què necessito una peça addicional de les dades en aquesta llista? Penseu en el que els números es si he elaborat la següent manera. Suposem que aquesta és ara una cua en lloc d'una pila, amb la diferència-igual que la botiga d'Apple-cua és just. La primera persona en línia al començament de la llista, el número 5 en aquest cas, ell o ella es deixarà a la primera botiga. Farem això. Suposem que aquest és l'estat del meu cua en aquest moment en el temps, i ara la botiga d'Apple s'obre i la primera persona, número 5, és conduït a la botiga. Com puc canviar la imatge ara que he de-cua la primera persona a la part davantera de la línia? Què és això? >> [Estudiant] Canvieu la cua. Canvieu el cap, així que 5 desapareix. En realitat, és com si-la millor manera de fer això? En realitat, és com si aquest home desapareix. Quin seria el número 7 en fer una botiga real? Es donaria un pas endavant molt important. 

Però què hem arribat a apreciar el que es fa a les matrius i movent coses de lloc? Això és una mica d'una pèrdua de temps, oi? Per què has de ser tan anal com per tenir la primera persona en l'inici de la línia en físicament l'inici de la porció de la memòria? Això és completament innecessari. Per què? Què podria jo recordi en el seu lloc? >> [Inaudible resposta dels estudiants] Exactament, jo només podia recordar amb aquest cap de membre de dades addicional que ara el cap de la llista ja no és 0, el que era fa un moment. Ara en realitat és el número 1. D'aquesta manera, si una optimització lleu. El fet que he de-cua a algú de línia a l'inici de la línia a la botiga d'Apple no vol dir que tothom ha de canviar, el que recordo és una operació lineal. Jo en canvi constant poden passar temps sol i aconseguir llavors una resposta molt més ràpida. Però el preu que estic pagant és el que guanyar que el rendiment addicional i no haver de canviar tot el món? Si. >> [Inaudible resposta dels estudiants] Podeu afegir més persones, bé, aquest problema és ortogonal al fet que no estem canviant la gent al seu voltant. Encara és una matriu, de manera que si no canviem tots o no- Oh, ja veig el que vols dir, està bé. En realitat, estic d'acord amb el que dius que és gairebé com si estem ara mai va a utilitzar l'inici d'aquesta sèrie ja perquè si em trec 5, llavors em trec 7. Però jo només posar a la gent a la dreta. 

Se sent com que estic perdent l'espai, i amb el temps la meva cua es desintegra en el no res, de manera que només podria tenir envoltant persones, i podríem pensar en aquesta sèrie realment com una mena d'estructura circular, però el fem servir operador en C per fer aquest tipus d'envolupant? [Resposta dels estudiants inaudible] >> L'operador de mòdul. Seria una mica molest per pensar en com es fa l'envoltant, però podríem fer-ho, i podríem començar a posar a les persones en el que va ser el front de la línia, però només recorda amb aquesta variable cap que el cap real de la línia és en realitat. I si, per contra, el nostre objectiu en última instància, però, va anar a buscar nombres, com ho vam fer aquí a l'escenari amb Anita, però realment volen el millor de tots aquests mons? Volem més sofisticació que permet array perquè volem que la capacitat de créixer de forma dinàmica l'estructura de dades. Però no vull haver de recórrer a una cosa que hem assenyalat a la primera conferència no va ser un algoritme òptim, que de recerca lineal. Resulta que es pot, de fet, aconseguir o almenys prop de la constant de temps, de manera que algú com Anita, si es configura l'estructura de dades per no ser una llista enllaçada, de no ser una pila, per no ser una cua, podria, de fet, arribar a una estructura de dades que li permet mirar les coses, fins i tot paraules, no només números, en el que anomenarem constant de temps. 

I de fet, mirant cap endavant, un dels conjunts de processadors d'aquesta classe és gairebé sempre una implementació d'un comprovador d'ortografia, mitjançant el qual et donem una altra vegada algunes paraules angleses 150.000 i l'objectiu és carregar a la memòria d'aquells i ràpidament ser capaços de respondre a les preguntes de la forma aquesta paraula s'escriu correctament? I realment seria un fàstic si ha de recórrer els 150.000 paraules per contestar això. Però, de fet, veurem que podem fer en un temps molt, molt ràpid. I va a implicar alguna cosa aplicació anomenada taula hash, i encara que a primera vista aquesta cosa anomenada taula hash es va a anem a aconseguir aquests temps súper ràpids de resposta, resulta que existeix de fet un problema. Quan arriba el moment de posar en pràctica aquesta cosa anomenada de nou, ho estic fent de nou. Jo sóc l'únic aquí. Quan arriba el moment de l'aplicació d'aquesta cosa anomenada taula hash, haurem de prendre una decisió. Què tan gran ha de ser aquesta cosa en realitat? I quan vam començar a inserir nombres en aquesta taula hash, Com podem guardar-los de forma que puguem tornar a sortir tan ràpid com ens les van donar en? Però ja veurem d'aquí a poc, que aquesta qüestió de quan és l'aniversari de tots en la classe serà molt afí. Resulta que en aquesta sala, tenim uns pocs centenars de persones, així que les probabilitats que dues de nosaltres tenim el mateix aniversari és probablement bastant alt. Què passa si només hi havia 40 de nosaltres en aquesta sala? Quines són les probabilitats de que dues persones tinguin el mateix aniversari? [Els estudiants] Més del 50%. Si, més de 50%. De fet, fins i tot em va portar una carta. Resulta que-i això és realment només un avançament de vista prèvia si només hi ha 58 de nosaltres en aquesta sala, la probabilitat que 2 de nosaltres tinguin el mateix aniversari és enormement alt, gairebé el 100%, i això va a causar una gran quantitat de dany per a nosaltres el dimecres. 

Dit això, anem a aixecar la sessió aquí. Ens veiem el dimecres. [Aplaudiment] [CS50.TV]