[REPRODUCCIÓ DE MÚSICA] DAVID J. Malan: Molt bé. Això és CS50. Aquesta és la cinquena setmana va continuar, i ens tenir algunes bones notícies i males notícies. Així que bona notícia és que CS50 llança aquest divendres. Si vol unir-se a nosaltres, dirigir-se a l'adreça URL habitual aquí. Encara millor notícia, sense conferència dilluns 13. Una mica menys millors notícies, qüestionari de zero és dimecres que ve. Més detalls poden ser trobat en aquest URL aquí. I en els pròxims dies estarem omplint els espais en blanc pel que fa a les habitacions que haurem reservat. Millor notícia és que no vaig a ser un examen de tot el curs sessió el proper Dilluns a la nit. Estiguin atents al curs de lloc web per a la ubicació i detalls. Seccions, tot i que és un dia de festa, també es reunirà també. Millors notícies, conferència divendres que ve. Així que aquesta és una tradició que tenir, segons el pla d'estudis. Sol-- que serà increïble. Vostè veurà coses com estructures de dades de temps constant i taules i arbres i tries de patata. I anem a parlar dels problemes d'aniversari. Un munt de coses espera divendres que ve. Okay. De totes maneres. Així recordem que hem estat centrant-se en la imatge del que està dins de la memòria del nostre ordinador. Així, la memòria o la memòria RAM és on els programes existint mentre vostè els està corrent. Si feu doble clic a una icona per executar algun programa o feu doble clic en un icona per obrir algun arxiu, està carregada del seu disc conduir o unitat d'estat sòlid a la memòria RAM, memòria d'accés aleatori, on viu fins que es desconnecti l'alimentació, la tapa del portàtil es tanca, o sortir del programa. 

Ara que la memòria, de que és probable que tingui 1 gigabyte aquests dies, 2 gigabytes, o fins i tot molt més, generalment es presenta per a un programa donat en aquest tipus de rectangular model conceptual amb la qual cosa tenim la pila a la part inferior i un munt d'altres coses a la part superior. La cosa a la part superior que hem vist en aquesta imatge abans, però mai es parla és l'anomenat segment de text. Segment de text és només una forma elegant de dir els zeros i uns que compondre el seu programa compilat real. 

Així que en fer doble clic Microsoft Word en el seu Mac o PC, o quan s'executa punt slash Mario en un Ordinador amb Linux a la finestra de terminal, els zeros i uns que componen Word o Mario s'emmagatzemen temporalment a la memòria RAM de l'ordinador en l'anomenat segment de text per a un programa en particular. A sota d'això va inicialitzat i dades sense inicialitzar. Això és una cosa similar a les variables globals, que nosaltres no hem fet servir molts, però en ocasions ens hem tingut variables globals o estàticament cordes definit que està codificat paraules com "hola" que no són preses en l'usuari des que estan codificats dur en el seu programa. 

Ara, avall a la part inferior que tenir l'anomenada pila. I la pila, fins ara, hem estat utilitzant per a quin tipus de propòsits? El que la pila s'utilitza? Sí? 

AUDIÈNCIA: Funcions. 

DAVID J. Malan: Per a les funcions? ¿En quin sentit per a les funcions? 

AUDIÈNCIA: Quan es crida a una funció, el arguments es copien a la pila. 

DAVID J. Malan: Exactament. Quan es crida a una funció, la seva arguments es copien a la pila. Així que qualsevol X o Y o A o B de l' que està passant en una funció estan temporalment posar en l'anomenada pila, igual que un dels Annenberg safates de menjador, i també coses com a variables locals. Si la seva funció foo o el seu bescanvi funció té variables locals, com la temperatura, els dos acaben a la pila. Ara, no anem a parlar massa sobre ells, però aquestes variables d'entorn a la part inferior que vam veure fa un temps quan Em barallar en el teclat un dia i vaig començar a accedir a les coses com argv argv 100 o 1000, només elements-- oblit la numbers-- però això no se suposa que és visitada per mi. Comencem a veure algunes símbols de funky a la pantalla. Aquests eren els anomenats variables d'entorn com ajustos globals per a mi programa o per al meu equip, no no relacionat amb la recent error que hem discutit, Shellshock, que ha estat que afecta a un bon nombre d'ordinadors. 

Ara, finalment, en l'enfocament d'avui serem en última instància, en el munt. Aquesta és una altra part de la memòria. I fonamentalment tot això la memòria és la mateixa matèria. És el mateix maquinari. Som només una mena de el tractament de diferents grups de bytes per a diferents propòsits. El munt també estarà on variables i memòria que vostè demani des del sistema operatiu s'emmagatzema temporalment. 

Però hi ha una espècie de problema Aquí, com la imatge implica. Tenim sort de tenir dos vaixells a punt de xocar. Perquè com s'utilitza cada vegada més de la pila, i com el veiem avui en dia endavant, i quan s'utilitza cada vegada més de la munt, segurament les coses dolentes poden succeir. I, de fet, podem induir que amb o sense intenció. Així que el drama de suspens última temps era aquest programa, que no servirà qualsevol funcional propòsit que no sigui per demostrar com vostè com un tipus dolent en realitat pot prendre avantatge dels errors en el programa d'algú i fer-se càrrec d'un programa o fins i tot un sistema informàtic totalitat o servidor. Així que a primera vista breument, que notar que la principal a la part inferior pren en la línia d'ordres arguments, com per argv. I té una crida a una funció f, essencialment una funció sense nom diu f, i està passant en argv [1]. 

Així que qualsevol paraula que l'usuari escriu a l' el símbol darrere del nom d'aquest programa, i després aquesta funció arbitrària fins superior, f, porta en una cadena, conegut com char *, com hem començat a discutir, i que només ho diu "bar". Però podríem anomenar res. I llavors es declara, a l'interior de f, un conjunt de caràcters anomenat C-- 12 d'aquests personatges. 

Ara, per la història que explicava Fa un moment, quan en la memòria és c, o són els 12 Chars va a acabar? Perquè quedi clar. Sí? 

AUDIÈNCIA: A la pila. 

DAVID J. Malan: A la pila. Així que c és una variable local. Estem demanant 12 caràcters o 12 bytes. Aquests van a acabar en l'anomenada pila. Ara, finalment, és aquesta altra funció això és realment molt útil, però nosaltres no hem fet servir realment nosaltres mateixos, strncopy. Això significa còpia de cadena, però només n lletres, n caràcters. Així n caràcters seran copiat de bar al c. I quants? La longitud de la barra. Així, en altres paraules, que una línia, strncopy, va a copiar prohibir de manera efectiva en l'c. 

Ara, només per tipus d'anticipar la moralitat d'aquesta història, el que és potencialment problemàtica aquí? Tot i que estem comprovant la longitud del bar i de passar-ho a strncopy, ¿Quin és el seu intestí dient és encara trencat sobre aquest programa? Sí? 

AUDIÈNCIA: No inclou espai per al caràcter nul. DAVID J. Malan: No inclou espai per al caràcter nul. Potencialment, a diferència de pràctica del passat que ni tan sols tenir tant com un plus de l'1 al acomodar aquest caràcter nul. Però és encara pitjor que això. Què més estem fallant a fer? Sí? 

AUDIÈNCIA: [inaudible] DAVID J. Malan: Perfect. Dur Hem codifiquem 12 bastant arbitrària. Això no és tant la problema, però el fet que ni tan sols estem comprovant si la longitud de la barra és de menys de 12, en aquest cas serà segur per a posar-lo en la memòria anomenat c que hem assignat. En efecte, si la barra és com 20 caràcters de llarg, aquesta funció sembla estar copiant 20 personatges de bar al c, per tant tenint almenys 8 bytes que no ha de ser. Aquesta és la implicació aquí. 

Així que en breu programa, trencat. No com una gran cosa. Potser vostè aconsegueix un error de segmentació. Tots hem tingut errors en els programes. Tots nosaltres podríem tenir errors en els programes en aquests moments. Però quina és la implicació? Bé, aquí hi ha una versió ampliada a d' que la imatge de la memòria del meu ordinador. Aquest és el fons del meu stack. I, en efecte, en la part inferior és el que hi ha anomenada pila rutina pare, forma elegant de dir que és principal. Així que tot el que crida a la funció f que estem parlant. Així que aquesta és la part inferior de la pila. Direcció de retorn és una cosa nova. Sempre ha estat aquí, sempre ha estat en aquesta foto. Nosaltres mai cridem l'atenció sobre ell. Perquè resulta que la forma c funciona és que quan una funció crida a una altra, no només els arguments que funció get inserida en la pila, no només fer local de la funció variables de quedar relegats a la pila, cosa que es diu una adreça de retorn També aconsegueix posar a la pila. En concret, si les trucades principals Foo, principals pròpia direcció en la memòria, el bou alguna cosa, efectivament aconsegueix posar a la pila de manera que quan f es fa executar sap on per saltar de nou a en el text segment per tal de continuar amb l'execució. 

Així que si som aquí conceptualment, en principal, llavors f és cridat. Com se sap que f al control de la mà de tornada? Bé, aquest petit molla de pa en vermell aquí, anomenat el remitent, només xecs, el que és que la direcció del remitent? Oh, deixa saltar de nou al principal aquí. I això és una mica d'una simplificació excessiva, perquè els zeros i uns per principals són tècnicament aquí al segment de tecnologia. Però aquesta és la idea. f només ha de saber el que on el control en última instància es remunta. 

Però la forma en ordinadors han assegut durant molt de temps fora coses com les variables locals i arguments és així. Així que a la part superior d'aquesta imatge en blau és el marc de pila de f, de manera que tot de la memòria que f específicament utilitzeu. Així que en conseqüència, observi que bar està en aquesta foto. Bar era el seu argument. I reclamem que els arguments a funcions quedar relegats a la pila. I C, per descomptat, és També en aquesta imatge. 

I només per a propòsits de notació, compte en la cantonada superior esquerra és el que es c suport 0 i a continuació, una mica cap a la dreta c és el suport 11. En altres paraules, es pot imaginar que hi ha una reixa de bytes allà, primer dels quals és dalt a l'esquerra, part inferior de les quals és l'últim d'aquests 12 bytes. 

Però ara tractar d'avançar ràpidament. Què passarà si passem en un bar de cadena que és més de c? I no estem comprovant si és de fet més de 12. Quina part d'aquesta imatge va a aconseguir sobreescrit per bytes 0, 1, 2, 3, dot dot dot, 11, i després dolent, 12, 13 a través de 19? Què passarà aquí, si vostè deduir de l'ordenament que c abraçadora 0 està en la part superior i c abraçadora 11 és una espècie de sota a la dreta? Sí? 

AUDIÈNCIA: Bé, va sobreescriure bar char *. 

DAVID J. Malan: Sí, sembla que vostè va a sobreescriure char * bar. I pitjor encara, si vostè envia en un temps molt llarg cadena, que fins i tot podria sobreescriure què? La direcció de retorn. Que al seu torn, és igual que un ruta de navegació per dir-li al programa on per anar de nou a quan f es fa la qual crida. 

Llavors, què nois dolents solen fer és si es troben amb un programa que són curiosos si és explotable, amb errors de forma que ell o ella pot prendre avantatge d'aquest error, generalment no reben aquesta bé la primera vegada. Només començar a enviar, per exemple, cadenes aleatòries en el seu programa, ja sigui en el teclat, o francament que probablement escriure un petit programa que acaba d' generen automàticament les cadenes, i començar a colpejar en el seu programa l'enviament de gran quantitat de diferents insums en diferents longituds. 

Tan aviat com els seus errors en el programa, això és una cosa increïble. Com que vol dir que ell o que ha descobert el que probablement és de fet un error. I llavors poden aconseguir més intel · ligent i començar a centrar-se més estretament sobre la forma d'explotar aquest error. En particular, el que ell o ella podria fer és enviar, en el millor dels casos, hola. No és gran cosa. És una cadena que és prou curt. Però i si ell o ella envia, i anem a generalitzar com, atac code-- tan zeros i els que fan les coses com rm-rf, de treure tot des del disc dur o enviar correu brossa o atacar d'alguna manera la màquina? 

Així que si cada un d'aquests lletres A només representa, conceptualment, atac, atac, atac, atac, algunes males codi que algú més va escriure, però si aquesta persona és prou intel · ligent no només per incloure tota d'aquests rm-RFS, sinó també tenir els seus últims bytes ser un número que correspon a la direcció del seu o el seu propi codi d'atac que ell o ella va passar en només proporcionant a l'indicador, es pot enganyar a l'ordinador amb eficàcia en adonar-se quan f es realitza l'execució, oh, és el moment perquè salti de nou a l'adreça de retorn vermell. Però com que ell o ella té d'alguna manera superposades que remet amb el seu propi número, i són prou intel · ligents haver configurat que número de referència, ja que veure en el top fantàstic cantonada esquerra hi ha, l'adreça real a l'ordinador de memòria d'alguns del seu codi d'atac, un noi dolent pot enganyar l'ordinador en l'execució del seu propi codi. 

I aquest codi, de nou, pot ser qualsevol cosa. Generalment, es diu codi shell, que és just una forma de dir que no és generalment una cosa tan simple com rm-rf. En realitat és com Bash, o un programa que li dóna o el seu control de programació per executar qualsevol altra cosa que ells volen. Així que en resum, tot això deriva del simple fet que aquest error en qüestió no comprovació els límits de la matriu. I a causa de la forma en equips de treball és que utilitzar la pila de efectivament, conceptualment, part inferior cap amunt, però després els elements vostè empeny a la pila creixi dalt a baix, això és molt problemàtic. Ara, hi ha maneres d'evitar aquest. I, francament, hi ha llengües amb el qual treballar al voltant d'això. Java és immune, per exemple, a aquest tema en particular. Perquè ells no et donen consells. Ells no et donen adreces de memòria directa. Així que amb aquest poder que tenim tocar res en la memòria volem que ve, sens dubte, un gran risc. 

Així que mantenir un ull cap a fora. Si, francament, en els mesos de o anys per venir, en qualsevol moment vostè llegeixi sobre cert tipus d'explotació d'un programa o un servidor, si vostè veu un indici d'alguna cosa com un atac de desbordament de memòria intermèdia, o desbordament de pila és un altre tipus d'atac, similar en esperit, tant com inspira el lloc web de nomenar, si ho coneix, tot està parlant només d' vessar la mida d'alguns de caràcter matriu o alguna varietat més general. Qualsevol pregunta, llavors, sobre això? No intenteu fer això a casa. 

Bé. Així malloc fins ara ha estat el nostre nou amic en què podem assignar memòria que no sabem necessàriament en avancem que volem el que no tenim a codificar en la nostra números de programes com 12. Una vegada que l'usuari ens diu quant dades que ell o ella vol d'entrada, podem malloc que gran part de la memòria. 

Així malloc resulta, a la mesura que hem estat utilitzant, explícitament l'última vegada, i després vostès han estat utilitzant getString per saber-ho per diverses setmanes, tots els de la memòria de malloc prové de l'anomenada pila. I és per això getString, per exemple, pot assignar memòria dinàmicament sense saber el que ets va a escriure per endavant, de tornar un punter a la memòria, i que la memòria segueix sent teu per sempre, fins i tot després GetString rendiments. Perquè record després de tot el que l' pila està constantment pujant i baixant, amunt i avall. I tan aviat com va baix, això significa que qualsevol memòria aquesta funció emprada ha No ser utilitzat per cap altra persona. És valors d'escombraries ara. 

Però el munt és aquí dalt. I el que és bo de malloc és que quan malloc assigna memòria fins aquí, no està afectada, per a la major part, per la pila. I pel que qualsevol funció pot accedir memòria que s'ha malloc'd, fins i tot per una funció com getString, fins i tot després que es retorna. 

Ara, el contrari del malloc és gratis. I, en efecte, la regla que que hagi de començar a adoptar és qualsevol, qualsevol, qualsevol moment vostè utilitza malloc ha de vostè utilitzar lliure, amb el temps, en aquest mateix punter. Durant tot aquest temps hem estat escrivint amb errors, codi erroni, per moltes raons. Però un dels quals ha estat utilitzant la biblioteca d'CS50, que sí que és deliberadament amb errors, es perd memòria. Cada vegada que ha anomenat getString durant les últimes setmanes estem fent l'operació sistema, Linux, per a la memòria. I vostè mai una vegada donat per tu. I això no és, en practicar, una bona cosa. 

I Valgrind, un dels eines introduïdes en el joc de paràmetres 4, es tracta d'ajudar vostè ara trobar errors com aquest. Però per sort per Pset 4 no cal utilitzar la biblioteca CS50 o getString. Així que qualsevol error relacionats amb la memòria són en última instància, serà la seva. 

Així malloc és més que convenient per a aquest propòsit. En realitat, ara podem resoldre fonamentalment diferents problemes, i resoldre fonamentalment els problemes més eficaçment com per la promesa de la setmana zero. Fins al moment aquesta és la més sexy estructura de dades que hem tingut. I per l'estructura de les dades que acabo de dir una forma de memòria conceptualitzar d'una manera que va més enllà de només dir, aquest és un int, aquest és un char. Podem començar al costat de les coses de dispersió. 

Així que una matriu es veia així. I el que va ser clau en aproximadament una array és que et dóna back-to-back trossos de memòria, cadascun dels quals serà del mateix tipus, int, int, int, int o char, char, char, Char. Però hi ha alguns desavantatges. Això per exemple, és una matriu de mida 6. Suposem que vostè ompli aquesta matriu amb sis números i després, per les raons que siguin, l'usuari vol donar que un setè número. On el vas posar? 

Quina és la solució si vostè té creat una matriu a la pila, per exemple, només amb la setmana 02:00 notació que hem introduït, d'claudàtors amb els números de l'interior? Bé, vostè té sis els nombres en aquestes caixes. Quins serien els seus instints? On t'agradaria posar? 

AUDIÈNCIA: [inaudible] 

DAVID J. Malan: Ho sento? 

AUDIÈNCIA: Posa-ho al final. 

DAVID J. Malan: Posa-ho a l'extrem. Així que una mica més a la dreta, fora d'aquesta caixa de text. Què estaria bé, però resulta que no pot fer això. Perquè si no ho has demanat per aquesta part de la memòria, podria ser per casualitat que aquesta està sent utilitzat per alguna altra variable completament. Penseu de nou una setmana o així que quan ens fiquem al llit els noms Zamyla i Davin i Gabe de en la memòria. Eren, literalment, esquena amb esquena amb esquena. Així que no podem necessàriament confiar que qualsevol de aquí està disponible perquè jo usi. 

Llavors, què més podria fer? Bé, una vegada que adonar-se que necessitarà una matriu de mida 7, vostè podria crear un matriu de mida 7 després utilitzeu un bucle for o un bucle while, copiar-lo en la nova matriu, i llavors d'alguna manera simplement desfer-se de aquesta matriu o simplement deixi d'usar-lo. Però això no és particularment eficient. En resum, les matrius no deixen canviar la mida de forma dinàmica. 

Així que per una banda s'obté accés aleatori, que és increïble. Com que ens permet fer coses com divideix i venceràs, recerca binària, la qual cosa hem parlat a la pantalla aquí. Però es pinta a si mateix en una cantonada. Tan aviat com es va colpejar Al final de la seva matriu, vostè ha de fer un molt operació costosa o escriure un munt de codi de lluitar ara amb aquest problema. 

I què si el seu lloc, teníem cosa que es diu una llista, o una llista vinculada en particular? Què passa si en lloc d'haver rectangles esquena amb esquena amb esquena, hem rectangles que deixen una mica poc de marge de maniobra enmig d'ells? I tot i que he dibuixat aquest foto o adaptat aquesta foto d'un dels textos aquí per estar de nou a esquena amb esquena molt ordenada, en la realitat, un d'aquests rectangles podria ser de fins a aquí a la memòria. Un d'ells podria ser aquí. Un d'ells podria ser aquí dalt, aquí, i així successivament. 

Però el que si dibuixem, en aquest cas, les fletxes que d'alguna manera vincular rectangles junts? De fet, hem vist una tècnica encarnació d'una fletxa. Què hem utilitzat en els últims dia que, sota la campana, és representativa d'una fletxa? Un punter, oi? 

I què si, en lloc de emmagatzemar només els números, com 9, 17, 22, 26, 34, ¿I si no emmagatzemem només un nombre, però un punter costat de cada un d'aquests nombre? Així que igual que enfilar una agulla a través d'un grapat sencer de la tela, coses d'alguna forma de vinculació junts, de manera similar pot que amb els punters, com encarnat per fletxes aquí, tipus de teixir aquests rectangles individuals per la utilització eficaç d'un punter un al costat del número que apunta alguns següent nombre, que assenyala, al seu torn, alguns següent nombre? Així que en altres paraules, el que si en realitat volíem per implementar alguna cosa com això? Bé per desgràcia, aquests rectangles, almenys l'un amb 9, 17, 22, i així successivament, aquests ja no són boniques places amb números individuals. La part inferior, rectangle per sota de 9, per exemple, representa el que ha de ser un punter, 32 bits. Ara, encara no estic al corrent de qualsevol tipus de dades en C que li dóna no només un int però un punter per complet. 

Llavors, ¿quina és la solució si volem inventar la nostra pròpia resposta a això? Sí? 

AUDIÈNCIA: [inaudible] 

DAVID J. Malan: Què és això? 

AUDIÈNCIA: Nova estructura. 

DAVID J. Malan: Sí, i per què Per què no creem una nova estructura, o en C, una estructura? Hem vist estructures abans, encara que breument, on ens topem amb una estructura estudiant com aquest, que tenia un nom i una casa. En Pset 3 breakout vostè utilitza en el seu conjunt manat de GRect structs-- i GOvals que Stanford creat per informació de clúster junts. I què si prenem aquesta mateixa idea les paraules clau "typedef" i "struct" i després una mica de matèria específica de l'estudiant, i evolucionar això en el següent: typedef struct node-- i node és només una ciència de la computació molt genèric termini per a alguna cosa en una estructura de dades, un contenidor en una estructura de dades. Un node reclam tindrà 1 int n, totalment senzill, i després una mica més críptica, aquesta segona línia, el node struct * següent. Però en termes menys tècnics, el que és que la segona línia de codi dins de les claus? Sí? 

AUDIÈNCIA: [inaudible] DAVID J. Malan: Un punter a un altre node. Així que sens dubte, la sintaxi una mica críptic. Però si vostè llegeix literalment, següent és el nom d'una variable. Quin és el seu tipus de dades? És una mica verbós aquest moment, però és de tipus struct node *. Cada vegada que hem vist alguna cosa de l'estrella, que significa que és un punter a aquest tipus de dades. Així que la propera és pel que sembla un punter a un node d'estructura. 

Ara, què és un node d'estructura? Bé, s'observa que vegi els mateixes paraules a la part superior dreta. I, en efecte, es veu també la paraula "Node" aquí baix a la part inferior esquerra. I això és en realitat només una conveniència. Tingueu en compte que en la nostra definició estudiant aquí està la paraula "estudiant" només una vegada. I és que un estudiant objecte no era auto-referencial. No hi ha res a l'interior d'un estudiant que ha d'apuntar a un altre estudiant, persay. Això seria una mena de rar en el món real. 

Però amb un node en una lligat llista, si volem un node ser referencial a un objecte similar. I així compte del canvi aquí no és només el que està dins de les claus. Però afegim la paraula "node" a la part superior, així com d'afegir a la part inferior en lloc de "estudiant". I això és només un detall tècnic de manera que, de nou, l'estructura de dades pot ser auto-referencial, de manera que un node pot apuntar a una altra tal node. 

Llavors, què és aquesta última instància significarà per a nosaltres? Bé, un, això dins és el contingut del nostre node. Aquesta cosa aquí, a dalt a la dreta, és tan que, de nou, podem referir-nos a nosaltres mateixos. I després les coses més externa, tot i que el node és un nou terme, potser, que segueix sent el mateix que els estudiants i el que estava sota la caputxa en SPL. 

Així que si ara volíem començar l'aplicació d'aquesta llista enllaçada, ¿Com podríem traduir alguna cosa com això per a codificar? Bé, anem a veure un exemple d'un programa que en realitat utilitza una llista enllaçada. Entre codi de distribució d'avui és un programa que es diu Llista Zero. I si em quedo aquesta vaig crear un super GUI simple, interfície gràfica d'usuari, però no deixa de ser printf. I ara jo mateix he donat uns quants menú options-- Eliminar, Inserir, Cercar, i Traverse. I a Surt. Aquestes són operacions comuns en un sol estructura de dades coneguda com una llista d'enllaços. 

Ara, Eliminar va a suprimir un número de la llista. Inseriu va a afegir un número a la llista. La recerca es va a veure de nombre en la llista. I travessa és només una forma elegant de dir, caminar a través de la llista, imprimir-lo, però això és tot. No canvieu de cap manera. 

Així que anem a provar això. Seguirem endavant i tipus 2. I després vaig a inserir el nombre, per exemple 9. Intro. I ara el meu programa és només programada dir, la llista és ara 9. Ara, si em vaig per davant i no Inseriu de nou, deixar que em vaig per davant i allunyar i escric en 17. Ara la meva llista és 9, llavors de 17 anys. Si ho faig s'insereixi de nou, anem a saltar un. En lloc de 22, d'acord amb la imatge que hem estat veient aquí, deixa anar per davant i inseriu el 26 proper. Així que vaig a escriure 26. La llista és la que espero. Però ara, només per veure si el codi serà flexible, deixeu-me que ara tipus 22, que almenys conceptualment, si estem Tenint això ordenades, que és de fet serà un altre dels objectius en aquest moment, ha d'anar en entre el 17 i el 26. Així que vaig prémer Enter. De fet, això funciona. I ara permetin-me inserir el passat, per la imatge, 34. 

Bé. Així que per ara m'ho dius a mi estipulo que Esborrar i Traverse i Search fan, de fet, treballar. De fet, si jo corro recerca, anem a buscar el número 22, Enter. S'han trobat 22. Així que això és el que aquesta programa de llista Zero fa. 

Però el que realment està passant que implementa això? Bé, primer vaig a tenir, i de fet Jo tinc, un arxiu anomenat list0.h. I en algun lloc existeix aquest línia, typedef, struct node, llavors tinc els meus claus, int n, i llavors struct-- quina és la definició? Struct node següent. Així que tenim l'estrella. Ara tècnicament ens fiquem en l'hàbit de dibuixar aquí. És possible que vegi els llibres de text i referències en línia ho fan allà. És funcionalment equivalent. De fet, aquest és una mica més típic. Però seré coherent amb el que que vam fer l'última vegada i fem això. I després, finalment, vaig a fer això. 

Així que en un arxiu de capçalera en algun lloc, en list0.h avui és aquesta definició struct, i potser algunes altres coses. Mentrestant, en list0c hi serà un parell de coses. Però anem a simplement iniciar i no acabar això. List0.h és un arxiu que vull incloure en el meu arxiu C. I després, en algun moment m'estic tindrà int, principal, anul·larà. I després vaig a tenen algunes coses per fer aquí. Jo també vaig a tenir una prototip, com buit, recerca, int, n, el propòsit a la vida és per buscar un element. I llavors aquí jo reclam a el codi d'avui, nul recerca, int, n, hi ha punt i coma, però les claus obertes. I ara vull buscar alguna manera un element en aquesta llista. Però nosaltres no tenim prou informació a la pantalla encara. No tinc en realitat representada la pròpia llista. Així que una manera que podríem aplicar una llista enllaçada en un programa està com que vull fer alguna cosa com declaren llista enllaçada aquí. Per simplificar, faré aquest mundial, tot i que en general, ens No hauríeu de fer massa. Però va a simplificar aquest exemple. Així que vull declarar una llista enllaçada aquí. Ara, com podria jo fer això? 

Aquí hi ha la foto d'una llista enllaçada. I realment no em conèixer al moment com Vaig a anar sobre el que representa tantes coses amb un sol variable en la memòria. Però pensar de nou un moment. Durant tot aquest temps que hem tingut cordes, que després revelat a ser matrius de personatges, que després revelat a ser només un punter fins al primer caràcter en una matriu de caràcters això està acabada en nul. Així que per aquesta lògica, i amb aquest foto tipus de sembrar els seus pensaments, el que necessitem realment escrivim en la nostra codi per representar una llista enllaçada? Quina part d'aquesta informació necessitem capturar en codi C, què li diries? Sí? 

AUDIÈNCIA: Necessitem un punter a un node. DAVID J. Malan: Un punter a un node. En particular, el que faria amb el seu node instints ser mantenir un punter? 

AUDIÈNCIA: El primer node. 

DAVID J. Malan: Sí, probablement només la primera. I noti, la primera node és una forma diferent. És només la meitat de la grandària de l'estructura, perquè és de fet només un punter. Així que el que realment pot fer és declarar una llista enllaçada sigui de node de tipus *. I anem a anomenar primer i inicialitzar a null. Així nul, de nou, és procedent en la imatge aquí. No només s'utilitza null com com un especial valor de retorn per a coses com getString i malloc, null és també el zero punter, la falta d'un punter, si es vol. Només vol dir que encara no hi ha res aquí. Ara en primer lloc, que hauria pogut cridat a aquest res. Jo podria haver anomenat "llista" o qualsevol nombre d'altres coses. Però jo estic anomenant "primer" perquè línies amunt amb aquesta imatge. Així que igual que una cadena es pot representar amb la direcció del seu primer byte, pel que pot una llista enllaçada. I veurem altres dades poden representar estructures amb només un punter, una fletxa de 32 bits, assenyalant en el primer node de l'estructura. 

Però ara anem a anticipar un problema. Si jo només estic recordant en el meu programa de la direcció del primer node, la primera rectangle en aquesta estructura de dades, el que havia ser millor el cas sobre el execució de la resta de la cistella? Què és un detall clau que està passant per assegurar que funciona en realitat? I per "realment funciona" I dir, com un string, ens deixa anar des del primer caràcter en el nom de Davin a la segona, a la tercera, a la quart, fins al final, Com sabem quan estem al final d'una llista enllaçada que té aquest aspecte? Quan és nul. I jo he representat aquest tipus de com com una força enginyer elèctric, amb la poca terra símbol, de tota mena. Però això només significa nul en aquest cas. Vostè pot dibuixar qualsevol nombre maneres, però aquest autor passat a utilitzar aquest símbol aquí. 

Mentre estem encadenant tots aquests nodes entre si, només recordar on la primera és, sempre com posem un símbol especial a l'últim node de la llista, i farem servir nul, perquè això és el que tenim a la nostra disposició, aquesta llista és completa. I encara que jo només li donen un punter a el primer element, vostè, el programador, sens dubte pot accedir a la resta de la mateixa. Però anem a deixar que les seves ments passejar una mica, si no ho són ja bastant wandered-- el que és serà el temps d'execució de trobar res en aquesta llista? Maleïda sigui, és gran O de n, qual cosa no és dolent, per ser justos. Però és lineal. Hem renunciat al que característica d'arrays movent més a la imatge de manera dinàmica entrellaçats o nodes vinculats? Hem renunciat accés aleatori. Una matriu és agradable perquè tot matemàticament ha tornat a l'esquena amb esquena amb esquena. Tot i que aquesta foto es veu bastant, i fins i tot encara que sembla que aquests nodes estan ben separats, en realitat podrien estar en qualsevol part. Ox1, OX50, Ox123, Ox99, aquests nodes podrien estar en qualsevol part. A causa de malloc fa assignar memòria de la pila, però en qualsevol lloc en el munt. No necessàriament sap que és estarà esquena amb esquena amb esquena. I així aquesta foto a la realitat de No serà bastant aquesta bonica. 

Així que prendrà una mica de treballar per implementar aquesta funció. Així que anem a posar en pràctica la recerca ara. I anem a veure una mena de forma intel ligent de fer-ho. Així que si jo sóc una funció de recerca i Em donen una variable, sencer n a buscar, necessito saber la nova sintaxi per mirar dins d'una estructura que és assenyalat, per trobar n. Així que farem això. 

Així que primer vaig a anar endavant i declarar un node *. I jo vaig a dir- punter, només per convenció. I jo vaig a inicialitzar a primera. I ara que puc fer això en un nombre de maneres. Però em vaig a prendre un enfocament comú. Mentre punter no és igual a nul, i això és una sintaxi vàlida. I només significa fer el següent, de manera que sempre que vostè no està apuntant al no-res. Què vull fer? 

Si dot punter n, deixar-me tornar perquè, equals-- igual què? Quin valor que estic buscant? El major real que va passar. Així que aquí està una altra de les característiques de C i molts idiomes. Tot i que el node d'estructura anomenada té un valor de n, totalment legítim tenir també un argument locals o variable anomenada n. Perquè nosaltres també, amb els ulls humans, poden distingir que aquest n és presumiblement diferent d'aquest n. Com que la sintaxi és diferent. Tens un punt i un punter, mentre que aquest no té tal cosa. Així que això està bé. Això està bé trucar les mateixes coses. 

Si jo et trobo això, estic voldrà fer alguna cosa com vam anunciar que ens trobem n. I això l'hi deixem com comentar o codi pseudocodi. Si no, i aquí hi ha la L'interessant, el que faig el que vull fer si el node actual no conté n que m'importa? Com puc aconseguir el següent? Si el meu dit a l' moment és PTR, i és que apunta al que sigui primer està apuntant a, Com puc moure el meu dit al següent node en el codi? Bé, quina és la ruta de navegació que estem seguirà en aquest cas? AUDIÈNCIA: [inaudible]. DAVID J. Malan: Sí, així que la propera. Així que si torno al meu codi aquí, de fet, estic seguirà endavant i dir punter, que és només una variable-- temporal és un nom estrany, ptr, però és com temp-- Vaig a establir punter igual al que sigui punter és-- i de nou, això serà un d'errors, per inserir un punt moment-- següent. En altres paraules, em vaig a prendre el meu dit que està assenyalant a aquest node aquí i jo vaig a dir, ja saps què, mireu el següent camp i moure el dit per com sigui que s'assenyala a. I això va a repetir, repetir, repetir. Però quan ho fa el meu dit deixar de fer res en absolut? Tan aviat com quina línia de codi a puntades? AUDIÈNCIA: [inaudible] DAVID J. Malan: Si el punt mentre punter no és igual a null. En algun moment de la meva dit de estarà apuntant a nul i jo vaig a fer aquest és el final d'aquesta llista. Ara, això és una mica mentida piadosa per la simplicitat. Resulta que tot i que acaba d'assabentar aquesta notació de punts per a estructures, punter no és una estructura. ptr és què? Només per ser més primmirada. És un punter a un node. No és un node en si. Si no tingués l'estrella aquí, punter absolutely-- és un node. Això és com una setmana declaració d'una variable, tot i que la paraula "node" és nova. 

Però tan aviat com s'introdueix un estrella, ara és un punter a un node. I, per desgràcia no es pot utilitzar la notació de punts per a un punter. Vostè ha de fer servir la fletxa notació, que, sorprenentment, és la primera vegada que un tros de sintaxi sembla intuïtiu. Això es veu, literalment, com una fletxa. I això és una bona cosa. I aquí baix, literalment, s'assembla a una fletxa. Així que crec que aquesta és la la-- no ho faig Crec que estic massa cometre aquí-- I Crec que és l'última peça nova de la sintaxi que veurem. I per sort, és de fet una mica més intuïtiu. 

Ara, per a aquells de vostès que podrien preferir la manera antiga, encara pot utilitzar la notació de punts. Però segons Dilluns de conversa, primer que hagi d'anar-hi, anar a aquest abordar, i després accedir al camp. Així que això també és correcte. I, francament, aquest és un poc més pedant. Vostè està literalment dient desreferenciar el punter i anar-hi. Llavors agafa .n, el camp anomenat n. Però, francament, ningú vol per escriure o llegir això. I així el món va inventar la notació fletxa, que és equivalent, idèntic, és només el sucre sintàctica. Així que una forma elegant de dir això es veu millor, o es veu més simple. 

Així que ara me'n vaig a fer una altra cosa. Vaig a dir "break" Una vegada que he trobar, així que no la guardo a la recerca d'ella. Però aquesta és l'essència d'una funció de cerca. Però és molt més fàcil, al final, no caminar a través del codi. Aquesta és de fet l'aplicació formal de recerca de codi de distribució actual. M'atreveixo a dir que la inserció no és particularment divertit caminar per visualment, ni tampoc eliminar, fins i tot encara que al final del dia es redueixen a bastant heurístiques simples. 

Així que farem això. Si vostè humor amb mi aquí, ho vaig fer portar un munt de boles d'estrès. Em va portar un munt de nombres. I podríem aconseguir uns pocs voluntaris per representar 9, 17, 20, 22, 29, i 34? Així que, essencialment tot el món qui està aquí avui. Aquest va ser un, dos, tres, quatre, cinc, a sis persones. I m'han demanat que ir-- veure, no una a la part posterior aixeca les seves mans. Bé, un, dos, tres, quatre, cinc-- m'ho dius a mi carregar balanç-- 06:00. OK, anem fins a sis. Necessitarem altres persones. Vam portar boles d'estrès addicionals. I si pogués, per un moment, la línia vostès just t'agrada aquesta foto aquí. 

Bé. Anem a veure, com et dius? 

AUDIÈNCIA: Andrew. 

DAVID J. Malan: Andrew, ets el número 9. Encantada de conèixer-te. Aquí tens. AUDIÈNCIA: Jen. DAVID J. Malan: Jen. David. Número 17. Sí? 

AUDIÈNCIA: Sóc Julia. 

DAVID J. Malan: Julia, David. Número 20. AUDIÈNCIA: Cristià. DAVID J. Malan: Cristiano, David. Número 22. I? 

AUDIÈNCIA: JP. DAVID J. Malan: JP. Número 29. Així que endavant i obtenir en-- Uh oh. Uh oh. Standby. 20. Algú té un marcador? AUDIÈNCIA: Tinc un Sharpie. DAVID J. Malan: Tens 1 Sharpie? Okay. I algú té un tros de paper? Deseu la conferència. Vingui. AUDIÈNCIA: el tenim. DAVID J. Malan: ho aconseguim? Molt bé, gràcies. Aquí anem. ¿Era això de tu? Acabes de salvar el dia. Així 29. Bé. El escric malament el 29, però no està malament. Seguir endavant. Molt bé, et donaré la seva ploma cap enrere momentàniament. Així que tenim a aquesta gent aquí. Anem a tenir un altre. Gabe, vols jugar el primer element en aquesta llista? Et necessitem perquè apunti a aquesta bona gent. Així que 9, 17, 20, 22, espècie de 29, i després 34. ¿Vam perdre a algú? Tinc un 34. On hizo-- bé, que vol ser 34? Bé, anem cap amunt, 34. Molt bé, això serà bé val la pena el clímax. Quin és el teu nom? 

AUDIÈNCIA: Peter. 

DAVID J. Malan: Peter, anem a dalt. Molt bé, així que aquí té un tot grup de nodes. Cada un de vosaltres representa un d'aquests rectangles. I Gabe, el poc estrany l'home, representa en primer lloc. Així que el seu punter és una mica més petit a la pantalla de tots els altres. I en aquest cas, cadascun de la seva esquerra mans va a apuntar cap avall o bé, qual cosa representa una nul, de manera que només l'absència d'un punter, o que estarà apuntant en un node al costat de vostè. 

Així que ara mateix, si adornes vostès com la imatge aquí, seguir endavant i punt l'un a l'altre, amb Gabe en particular, apuntant a número 9 per representar la llista. Acceptar, i el número 34, la mà esquerra només han d'estar apuntant cap a terra. 

Acceptar, pel que aquesta és la llista enllaçada. Així que aquest és l'escenari en qüestió. I, de fet, això és representatiu d'una classe de problemes que vostè pot tractar de resoldre amb el codi. Vostè vol inserir en última instància un nou element a la llista. En aquest cas, anem a tractar d'inserir el número 55. Però no serà diferents casos a considerar. I, de fet, això serà una de la gran imatge menjar per emportar aquí, és, ¿Quins són els diferents casos. Quins són els diferents si les condicions o branques que el seu programa podria tenir? 

Bé, el número al qual està intentant inserció, que ara sabem que ser 55, però si vostè no ho sabia per endavant, m'atreveixo a dir cau en almenys tres possibles situacions. On podria ser un nou element? AUDIÈNCIA: I al final o al mig. DAVID J. Malan: Al final, en el mitjà, o al principi. Així que jo reclam que hi ha almenys tres problemes que han de resoldre. Anem a triar el que és potser possiblement el més simple un, quan l'element nou pertany al principi. Així que vaig a tenir prou codi com la recerca, que només vaig escriure. I jo tindré ptr, que Vaig represento aquí amb el dit, com sempre. 

I recorda, quin valor vam inicialitzem ptr a? Així que hem inicialitzat en null inicialment. Però llavors què vam fer una vegada que estaven dins de la nostra funció de cerca? La fixem igual al primer, el que no vol dir fer això. Si fix ptr igual al primer, el que ha de ser realment la mà apuntant a? Dreta. Així que si Gabe i jo anem ser valors iguals aquí, necessitem tant el punt en el número 9. 

Així que aquest va ser el començament de la nostra història. I ara això és només senzill, tot i que la sintaxi és nova. Conceptualment això és només cerca lineal. Is 55, igual a 9? O més aviat, diguem menys de 9. Perquè jo estic tractant d' esbrinar on posar 55. Menys de 9, a menys de 17, menys de 20, menys de 22, menys de 29, menys de 34, no. Així que ara estem en el cas un almenys tres. 

Si vull inserir 55 per aquí, el que línies de necessitat codi s'executen? Com funciona aquest quadre de els éssers humans han de canviar? Què faig amb la meva mà esquerra? Això hauria de ser nul inicialment, perquè estic al final de la llista. I el que hauria de passar aquí amb Peter, oi? Ell, òbviament, va apuntar a mi. Així que jo reclam que hi ha almenys dos línies de codi en el codi d'exemple a partir d'avui això va a implementar aquest escenari de l'addició de 55 a la cua. I podria tenir algú hop i només representen el 55? Molt bé, vostè és el nou 55. 

Així que ara el que si que ve escenari es presenta, i volem inserir al començant o el cap d'aquesta llista? I quin és el seu nom, el número 55? 

AUDIÈNCIA: Jack. 

DAVID J. Malan: Jack? Bé, encantat de conèixer-te. Benvingut a bord. Així que ara anem a inserir, per exemple, el número 5. Aquí hi ha el segon cas de la 3 se'ns va ocórrer abans. Així que si 5 pertany al principi, anem a veure com ens trobem amb que fos. Puc inicialitzar meu ptr punter a número 9 de nou. I em vaig adonar, oh, 5 és menor que 9. Així que arreglar aquesta imatge per a nosaltres. ¿Quines mans, Gabe o David de o-- ¿com es diu el número del 9? 

AUDIÈNCIA: Jen. 

DAVID J. Malan: mans-- de Jen quina de les nostres mans que hagi de canviar? OK, així que Gabe assenyala en què ara? En mi. Jo sóc el nou node. Així que vaig a classe de moviment aquí per veure-ho visualment. I mentrestant, què he d'assenyalar que? Encara on sóc apuntant. Així que és això. Així que en realitat una línia d'arranjaments de codi aquest tema en particular, el que sembla. Molt bé, així que això és bo. I algú pot ser un marcador de posició per al 5? Anem amunt. Et portarem la propera vegada. 

Molt bé, així que ara-- i Com acotació al marge, els noms No faré esment explícit del dret Ara, pred punter, punter predecessor i nou punter, que és només els noms donat en el codi d'exemple als punters o les meves mans, que és una espècie de apuntant voltant. Quin és el teu nom? 

AUDIÈNCIA: Christine. 

DAVID J. Malan: Christine. Benvingut a bord. Molt bé, així que considerarem ara un escenari lleugerament més molest, pel qual vull inserir alguna cosa així com 26 en això. 20? Què? Aquests són-- bona cosa que tenim aquesta ploma. Molt bé, 20. Si algú pot aconseguir una altra peça de paper a punt, per si cas-- bé. Oh, interessant. Bé, això és un exemple d'un error de conferències. Acceptar quin és el teu nom? AUDIÈNCIA: Julia. DAVID J. Malan: Júlia, pot esclatar i pretendre que mai van estar aquí? OK, això mai va succeir. Gràcies. Així que suposem que volem inserir Julia a aquesta llista enllaçada. Ella és la número 20. I, per descomptat, ella és va a pertànyer al begin-- no connecti amb res encara. Així que la teva mà pot ser tipus de baix nul o algun valor escombraries. Diguem la història ràpida. Estic assenyalant en el número 5 d'aquest temps. Llavors comprovo setembre. Després reviso 17. Després reviso 22. I m'adono, ooh, Julia ha d'anar abans dels 22. Llavors, què ha de succeir? ¿Quines mans han de canviar? Júlia, la meva, o-- Quin és el teu nom? 

AUDIÈNCIA: Cristià. 

DAVID J. Malan: Cristiano o? 

AUDIÈNCIA: Andy. 

DAVID J. Malan: Andy. Cristià o Andy? Andy ha d'apuntar a? Júlia. Bé. Així que Andy, què vols apuntar a Júlia? Però esperi un minut. En la història fins al moment, Jo sóc el tipus d'un a càrrec, en el sentit que punter és la cosa que és movent-se a través de la llista. Pot ser que tinguem un nom per Andy, però no hi ha variable anomenada Andy. L'única altra variable que tenim és en primer lloc, que està representat per Gabe. 

Així que això és en realitat la raó per tant Fins aquí no hem necessitat això. Però ara a la pantalla no és esmentar de nou de punter pred. Així que permetin-me ser més explícit. Si aquesta és punter, vaig tenir una millor ser una mica més intel · ligent sobre la meva iteració. Si no us importa la meva passar per aquí de nou, assenyalant aquí, assenyalant aquí. Però m'ho dius a mi tenir un punter pred, punter predecessor, que és espècie que apunta a la element que estava just a. Així que quan vaig aquí, ara les actualitzacions mà esquerra. Quan vaig allà a les actualitzacions de la mà esquerra. I ara tinc no només un punter a l'element que va darrere de Julia, Encara tinc un punter a Andy, l'element abans. Així que vostè té accés, en essència, pa ratllat, si es vol, a tots els punters necessaris. 

Així que si jo estic apuntant a Andy i jo també estic apuntant en cristià, les mans ara ha de ser assenyalat en un altre lloc? Així que Andy ara pot apuntar a Julia. Julia ara pot apuntar Cristiano. Perquè ella pot copiar el meu punter de la mà dreta. I això et posa amb eficàcia de nou en aquest lloc aquí. Així que en resum, tot i que aquesta ens està prenent classe de sempre per actualitzar en realitat un llista enllaçada, s'adonen que les operacions són relativament simples. És d'un, dos, tres línies de codi en última instància. Però embolicat al voltant dels línies de codi, presumiblement, és que efectivament una mica de lògica fa la pregunta, ¿on som? Estem en el començament, el mitjà, o al final? 

Ara, sens dubte hi ha alguna altra operacions que podríem posar en pràctica. I aquestes fotos aquí només representen el que acabem de fer amb els éssers humans. Què passa amb l'eliminació? Si vull, per exemple, treure el número 34 o 55, Podria ser el mateix tipus de codi, però necessitaré un o dos passos. Perquè el que hi ha de nou? Si elimino algú al final, com el nombre 55 i després 34, el que també ha de canviar com jo que? He de no evict-- Quin és el teu nom? 

AUDIÈNCIA: Jack. 

DAVID J. Malan: Jack. He de no només evict-- lliure Jack, tan literalment trucar gratis Jack, o almenys el punter allà també, però ara el que cal canviar amb Peter? La seva mà millor començament que apunta cap avall. Perquè tan aviat com jo en dic gratuït Jack, si segueix apuntant de Pere en Jack i per tant segueixo recorrent la llista i l'accés aquest punter, que és quan el nostre amic segmentació d'edat criticar realitat podria posar en. Perquè ens hem donat la tornar la memòria a Jack. 

Pot quedar-s'hi maldestrament per un moment. Perquè tenim només un parell operacions finals a tenir en compte. Extracció del cap de la llista, o la principi-- i aquest de una mica molest. Perquè hem de saber que Gabe és una espècie d'especial en aquest programa. Perquè de fet, ell té el seu propi punter. Ell simplement no està sent assenyalat, com gairebé tots els altres aquí. 

Així que quan el cap de la llista és eliminat, les mans que hagi de canviar ara? Quin és el teu nom? 

AUDIÈNCIA: Christine. 

DAVID J. Malan: Sóc horrible en noms, pel que sembla. Així Christine i Gabe, les mans necessiti canviar quan tractem d'eliminar Christine, número 5, de la foto? OK, així que anem a fer-ho Gabe. Gabe va a apuntar, presumiblement, al número 9. Però el següent que hauria de passar? AUDIÈNCIA: Christine ha ser nul [inaudible]. DAVID J. Malan: OK, probablement hauríem make-- vaig sentir "nul" en algun lloc. AUDIÈNCIA: Null i alliberar-la. DAVID J. Malan: null què? AUDIÈNCIA: Null i alliberar-la. DAVID J. Malan: Null i alliberar-la. Així que això és molt fàcil. I és perfecte que ara ets una espècie de peu allà, que no pertany. Perquè has estat desacoblat de la llista. Has estat efectivament orfes de la llista. I així ens havíem millor trucar gratis ara Christine de donar aquest memòria. En cas contrari, cada vegada que eliminar un node de la llista que podríem estar fent la llista més curt, però en realitat no disminuint la mida en memòria. I pel que si estem afegint i afegint, afegint coses a la llista, el meu equip podria aconseguir més lent i més i més lent, perquè m'estic quedant sense memòria, encara que no estic realment usant bytes de Christine de la memòria més. 

Així que al final hi ha una altra escenaris, de l'eliminació descomptat-- en el medi, l'eliminació al final, com hem vist. Però el més interessant repte ara és serà considerar exactament el que el temps d'execució és. Així que no només es pot mantenir un trossos de paper, si, Gabe, que no li importaria donar tots una bola de la tensió. Moltes gràcies a la nostra llista enllaçada de voluntaris aquí, si pogués. 

[Aplaudiments] 

DAVID J. Malan: Molt bé. Així que un parell d'analítica preguntes després, si pogués. Hem vist aquesta notació abans, gran O i omega, límits superiors i cotes inferiors de la temps d'algun algorisme s'executa. Així que anem a considerar només un parell de preguntes. 

Un, i ho vam dir abans, el que és la gestió temps de cerca d'un llista en termes de gran O? Què és un límit superior en el funcionament temps de recerca una llista enllaçada tal com s'aplica pels nostres voluntaris aquí? És gran O de n, lineal. Com que en el pitjor dels casos, l'element, com 55, podríem estar buscant podríem estar on Jack era, tot el camí al final. I, per desgràcia, a diferència d'una matriu no podem aconseguir la suposició aquest moment. Malgrat tots els nostres éssers humans eren ordenats d'elements petits, 5, tot el camí fins l'element més gran, 55, que sol ser una bona cosa. Però què té aquesta suposició ja no ens permet fer? AUDIÈNCIA: [inaudible] DAVID J. Malan: Digui una altra vegada? AUDIÈNCIA: Accés aleatori. DAVID J. Malan: Accés aleatori. I al seu torn, això significa que pot no ia utilitzar zeros feble, la intuïció, i l'evidència de la utilització de binari buscar i dividir i conquerir. Perquè tot i que els éssers humans podien òbviament veure que Andy o cristià van ser més o menys en el medi de la llista, només sabem que com ordinador amb una lectura ràpida de la llista des del principi. Així que ens hem donat fins que l'accés aleatori. 

Així que gran O de n ara és el superior amb destinació en el nostre temps de recerca. Què passa amb l'omega de la nostra recerca? Quin és el límit inferior en la recerca per a algun nombre en aquesta llista? AUDIÈNCIA: [inaudible] DAVID J. Malan: Digui una altra vegada? AUDIÈNCIA: Una. DAVID J. Malan: Una. Així que el temps constant. En el millor dels casos, Christine és de fet, al principi de la llista. I estem buscant número 5, de manera que la va trobar. Així que no és gran cosa. Però ella ha d'estar al a partir de la llista en aquest cas. Què tal alguna cosa com ¿Eliminar? Què passa si vostè vol suprimir un element? Quin és el límit superior i el límit inferior sobre l'eliminació d'alguna cosa d'un vinculat enumerar? AUDIÈNCIA: [inaudible] DAVID J. Malan: Digui una altra vegada? AUDIÈNCIA: n. DAVID J. Malan: n és de fet, el límit superior. Com que en el pitjor dels casos que tractem eliminar Jack, com nosaltres ho vam fer. Ell és tot el camí al final. Ens porta per sempre, o n passos per trobar-lo. Així que això és un límit superior. Això és lineal, segur. I el temps el millor dels casos en execució, o els límits inferiors en el millor dels casos seria constant de temps. Perquè potser tractem d'eliminar Christine, i acabem de tenir sort ella està en el començament. Espera un minut. Gabe també era al principi, i també vam haver de actualitzar Gabe. Així que no era només un pas. Pel que és de fet constant temps, en el millor dels casos, per eliminar l'element més petit? És, tot i que podria ser dues, 3, o fins i tot 100 línies de codi, si és el mateix nombre de línies, no en un bucle, i independent de la mida de la llista, és clar. Eliminar l'element a el principi de la llista, fins i tot si hem de fer front a Gabe, encara estem a temps constant. 

Així que això sembla una enorme pas enrere. I el que una pèrdua de temps si, en la primera setmana i la setmana zero no només vam tenir codi pseudocodi però el codi real per posar en pràctica una cosa que és registre base de n, o ingressi, més aviat, de n, base 2, quant al seu temps d'execució. Així que per què diables hauria que vulgueu començar usant alguna cosa com una llista enllaçada? Sí. 

AUDIÈNCIA: Així que vostè pot afegir elements a la matriu. DAVID J. Malan: Així que vostè pot afegir elements a la matriu. I això també és temàtic. I seguirem per veure això, aquesta compensació, molt com hem vist un trade-off amb merge sort. Realment podríem accelerar buscar o ordenar, més aviat, si ens passem una mica més d'espai i tenir un tros addicional d'una memòria o una matriu de tipus de combinació. Però gastem més espai, però ens estalviem temps. En aquest cas, estem renunciar a temps, però estem guanyar flexibilitat, dinamisme si es vol, que és sens dubte una característica positiva. 

També ens estem gastant l'espai. En quin sentit és un lligat enumerar més car en termes d'espai d'una matriu? On és l'espai extra ve? Sí? 

AUDIÈNCIA: [inaudible] punter. 

DAVID J. Malan: Sí, també tenen el punter. Així que això és molest minorly en què ja no sóc Jo emmagatzemar només un int per representar un int. Estic emmagatzemant 1 int i un punter, que també és de 32 bits. Així que estic literalment duplicar la quantitat d'espai involucrat. Així que això és un trade-off, però això és en el cas d'int. Suposem que vostè no està emmagatzemant int, però suposem que cada un d'aquests rectangles o cada un d'aquests éssers humans representava una paraula, una paraula en anglès que podria ser 5 caràcters, 10 personatges, potser fins i tot més. Després d'afegir només 32 més bits podria ser menys de gran cosa. 

Què passaria si cada un dels estudiants a la manifestació Estàvem literalment estructures estudiantils que tenen noms i cases i potser números de telèfon i Twitter mànecs i similars. Així que tots els camps que vam començar parlant l'altre dia, molt menys d'un gran problema ja nostres nodes es posen més interessants i gran per gastar, eh, un addicional indicador acaba de vincular entre si. Però de fet, és un trade-off. I, en efecte, el codi és més complex, ja que tindràs veure amb una lectura ràpida a través aquest exemple particular. Però i si hagués algun sant grial aquí. Què passa si no prenem un pas cap enrere, però un gran pas cap endavant i implementar una dada estructura a través de la qual pot trobar elements com Jack o Christine o qualssevol altres elements en aquesta matriu en la veritable constant de temps? Hi és constant. Eliminar constant. Inseriu és constant. Totes aquestes operacions són constants. Aquest seria el nostre sant grial. I aquí és on estem recollirà la propera vegada. Ens veiem llavors.