DAVID Malan: Molt bé. Benvingut de nou a CS50. Aquest és el començament de la setmana 8. I recordar que un problema conjunt maig va acabar amb una mica d'un desafiament. Així que suposant que recuperar tota la seva Els becaris d'ensenyament i fotografies de CA a l'arxiu card.raw, vostè és elegible trobar ara totes aquestes persones, i un afortunat guanyador a casa amb una d'aquestes coses, el moviment de salt dispositiu que es pot utilitzar per a la final de projectes, per exemple. 

Aquest, cada any, porta a una mica d'esgarrifança. I així el que vaig pensar en fer és compartir amb vostès algunes de les notes que tenen anat i vingut durant la llista de personal en els últims temps. Per exemple, la nit anterior, cita Fi de la cita, d'un dels empleats membres ", que acaba de tenir un cop estudiant a la porta per fer una foto amb mi. Assetjadors, els dic. "Va començar, bastant descriptiu i després ens mudem en què, una hora més tard, "Vaig tenir un estudiant m'espera després de la secció i tenia tots els nostres noms i fotos en alguns fulls de paper. "Molt bé. Així organitzada, però no tot el que esgarrifós encara. 

Llavors, "jo estava fora de la ciutat aquest cap de setmana, i quan vaig tornar, hi havia un a el meu dormitori. "[El] DAVID Malan: Pròxima cita d'un personal membre ", un estudiant va venir a casa meva a les Somerville a les 4 hores d'aquest matí. "Next personal: "Jo vaig arribar al meu hotel a San Francesc i estudiant estava esperant em al hall d'entrada amb tres càmeres rèflex digitals. " Tipus de cambra. "Ni tan sols estic en el personal d'aquest semestre, però un estudiant va irrompre a casa meva aquesta matí i registrat tot l'assumpte amb Google Glass. "I després, finalment, "Almenys 12 persones van ser àvidament esperant per mi quan vaig sortir de la meva llim, i després despertar. "Molt bé. Així que entre les fotografies, ja que pot recordar, són aquest home aquí, que et podria saber que Milo plàtan, que viu amb Lauren Carvalho, el nostre cap ensenyar Fellow. Milo, Milo, vine aquí noi. Milo. Milo. Això sí, ell està utilitzant Google Glass, per la li mostrarem tot això després. Així que això és Milo si voleu fer una fotografia amb ell després. Si voleu cercar a l'audiència allà. D'acord. Aquestes són bones imatges. Bé, Milo plàtan. Oh, no facis això. 

[El] 

D'acord. Així que una paraula i després en el que s'acosta, perquè a mesura que comencem a la transició, aquesta setmana específicament, de C en un entorn de línia d'ordres del PHP i JavaScript i SQL i HTML i CSS en un entorn basat en web, estarem et equipa amb tot el un major coneixement de potencials projectes finals. Amb aquesta finalitat, el curs té un tradició de la celebració de seminaris que són sobre temes tangencials al curs. Molt relacionat amb la programació i desenvolupament d'aplicacions, etc, però no necessàriament explorat per propi pla d'estudis del curs. 

Així que si vostè pot estar interessat en una o més dels seminaris d'aquest any, registrar-se a cs50.net/seminar. Hi ha seminaris majors en cs50.net/seminars. I en la llista fins al moment per a aquest any són increïbles aplicacions web amb Ruby on Riells, que és una alternativa llenguatge PHP. Lingüística Computacional. Introducció a la IOS, que és el plataforma que s'utilitza per l'iPhone i l' desenvolupament iPad. Habilitat per a aplicacions web, anem a cobrir , Però en aquest seminari, que anirà en més detalls. 

Leap Motion, així que ja tenim una mica de realitat dels nostres amics del Moviment Leap, la pròpia empresa, uneix-te a nosaltres. Demà, de fet, per proporcionar un seminari pràctic, si d'interès per a vostè. Meteor.js, una tècnica alternativa per usant JavaScript no en un navegador, però en un servidor. Node.js, que és molt en aquest sentit també. Disseny elegant i Android. Android és una alternativa molt popular per iOS i Windows Phone i altres plataformes mòbils. I web Active Defense Security. 

Així que, de fet, si vol a participar en això, permetin-me prengui nota d'això. Estem molt contents de dir que els nostres amics de Salt Moviment, que és un inici - aquest dispositiu realment vi fa uns mesos - gentilment ha donat 30 d'aquests dispositius a la classe per a tants estudiants, si desitja demanar prestat el maquinari cap al final del semestre i utilitzar-lo per un projecte final real. Donen suport a diversos idiomes. Cap d'ells C, cap d'ells PHP, per la compte d'un o més d'aquests seminaris podria resultar d'interès. I tots ells serà filmat en el cas que vostè no és capaç assistir en persona. L'horari serà anunciat a través del correu electrònic a mesura que consolidem habitacions. 

I finalment, si vostè va a projects.cs.50.net, aquest és un lloc web mantenim cada any que us convidem gent de la comunitat, professors, departaments, el personal i els dos a l'exterior del CS50 a proposar idees de projectes. Activitats d'interès per als grups d'estudiants. Activitats d'interès per als departaments. Així que al seu torn no si vostè està lluitant la incertesa quant al que vostè li agradaria abordar. 

Així que l'última vegada que presentem un dubte estructura de dades més complexa del que havia vist en setmanes anteriors. Havíem estat utilitzant arrays força feliçment com un útil si estructura de dades simplista. A continuació, presentem aquests, que per descomptat estan llistes enllaçades. I el que va ser una de les motivacions per la introducció d'aquesta estructura de dades? Sí? Què és això? 

AUDIÈNCIA: mida dinàmic. 

DAVID Malan: mida dinàmic. Així, mentre que en conjunt, cal saber la seva grandària amb anticipació quan el situa. A la llista enllaçada, no ho fa ha de saber això. Vostè pot simplement malloc, o més en general, assignar un addicional node, per així dir-ho, ja que voleu inserir més dades. I el node no ha determinat significat. És només un terme genèric que descriu una mena de contenidor que estem utilitzant en la nostra estructura de dades per emmagatzemar algun element d'interès, que en aquest cas resulten ser nombres enters. 

Però sempre hi ha una solució de compromís. Així que vam arribar mides dinàmics de les dades estructura, però Quin preu que paguem? Quin és el costat negatiu de les llistes enllaçades? Sí? 

AUDIÈNCIA: Requereix més memòria. 

DAVID Malan: Requereix més la memòria, com exactament? 

AUDIÈNCIA: [inaudible]. 

DAVID Malan: Exactament. Així que ara que hem punters prenent memòria addicional que prèviament no calia, ja que l'avantatge d'una matriu, per descomptat, és que tot és contigu, de tornada per tornar a l'esquena, el que li dóna accés aleatori. Perquè només mitjançant l'ús de claudàtors notació, o més tècnicament punter aritmètica, a més molt simple, es pot accedir a qualsevol elements de constant de temps. I de fet, que és una espècie d'al · lusió a un altre preu que estem pagant amb un llista enllaçada. 

Què passa amb el temps d'execució de alguna cosa així com la recerca, si vull trobar algun valor ia l'interior d'una llista enllaçada? El que es converteix en el meu temps corrent? Big O de n. Si s'ordena a? Què passa si l'estructura de dades està ordenat? Puc fer alguna cosa millor que grans O de n per a la recerca? No, perquè en el pitjor dels casos podria molt bé ser ordenats, però el nombre que busca pot ser gran. Pot ser que sigui el número 100, que podria passar a estar la forma a l'extrem. I pel fet que només es pot accedir a una vinculada llista d'aquesta aplicació per camí del seu primer node, ets encara una mica fora de sort. Vostè ha de travessar tot l'assumpte de principi a fi per tal de trobar aquest gran valor, com 100. O, per determinar si és ni tan sols existeix. 

Així que no podem fer el algoritme en una base de dades estructura que s'assembla a això? No podem fer una recerca binària, perquè recerca binària requereix que teníem d'accés aleatori. Podríem saltar d'un lloc a ubicació sense haver de seguir aquestes molles de pa en forma de tots aquests indicadors. 

Ara, com s'implementa això? Bé, si anem a la pantalla d'aquí, si podem tornar a implementar ràpidament aquestes dades estructura - la meva escriptura no és tot el que molt bé aquí, però ho intentarem. Typedef struct Així, i el que van fer I vol anomenar aquesta cosa aquí? Node. Així que vaig a que puguem començar. I ara, què ha d'estar dins del l'estructura de dades perquè individualment llista enllaçada? Quants camps? 

Així que dos. Un d'ells és bastant fàcil. Així int n. I podríem anomenar n tot el que vulguem, però ha de ser un int si estem implementació d'una llista enllaçada de sencers. I ara el que fa el segon camp ha de ser? Struct node *. Així que si ho faig struct node *, i després També podeu trucar a això el que vulgui, però només per ser clars Trucaré al costat, com ho hem estat fent. I després vaig a tancar els meus claus. 

I ara, com l'última vegada, Vaig posar node aquí. Però si estic declarant això és com una node, per què em molesta ser tan detallat aquí a la declaració struct node * següent, en lloc a sol node * següent? Sí? 

AUDIÈNCIA: [inaudible]. 

DAVID Malan: Exactament. Exactament. A causa C realment et porta literalment i només veu la definició de node fins aquí, no es pot referir-s'hi aquí. Així que tenim aquesta classe de preventiu declaració aquí, que és el que més detallat. Struct node, que significa ara podem accedir-hi a l'interior de l'estructura de dades. 

I en un a part, perquè es tracta d' cada vegada una mica més subjectiva ara, l'estrella tècnicament pot anar aquí, pot anar aquí, pot fins i tot anar en el medi. Hem adoptat, a la guia d'estil per a el curs, la convenció de posar l'estrella junt amb les dades tipus, que en aquest cas, seria node d'estructura. Però adonar-se una gran quantitat de llibres de text i referències en línia, vostè pot ser fet veure que a l'altra banda. No obstant això, només s'adonen que tant en realitat treballa i ha de ser simplement consistent. 

Està bé. Així que això va ser la nostra declaració de node d'estructura. Però després vam començar a fer més coses sofisticades. Per exemple, vam decidir introduir alguna cosa així com una taula hash. Així que aquí està una taula hash de grandària n, indexada des de 0 a la part superior esquerra a n menys d'1 en la part inferior esquerra. Això podria ser un hash taula per a res. Però, quin tipus de coses què parlem sobre l'ús d'una taula hash? Emmagatzematge de què? 

Noms. Podríem fer noms com vam fer l'última vegada. I realment, pot emmagatzemar qualsevol cosa. I anem a veure això de nou en PHP i JavaScript. Una taula hash és una bona espècie de Suïssa Navalla que li permet emmagatzemar gairebé tot el que vulguis dins d' que mitjançant l'associació de tecles amb els valors. Tecles amb valors. 

Ara bé, en aquest cas simple, el nostre claus són només números. Estem implementant un hash taula com una matriu. I així les claus són 0, 1, 2, i així successivament. I així nosaltres, com a éssers humans, va decidir el passat setmana que vostè sap què, si estem va a emmagatzemar noms, anem a arbitrària, però bastant raonable, assumir que Alice, una Un nom, només serà indexada en 0. I Bob, el nom de B, s'indexarà a 1, i així successivament. Així que vam tenir una correspondència entre les entrades, que són cadenes, i el hash llocs, que són nombres. 

Per tant aquest procés es coneix generalment com una funció hash, i vostè pot realment implementar en el codi. Si volgués aplicar una funció hash que fa exactament el que s'acaba de descriure de l'última vegada, jo podria declarar una funció que pren com d'entrada, per exemple - i farem això en aquest pantalla per aquí. Si volgués aplicar un hash funció, jo podria dir alguna cosa com això. 

Es va a tornar un int. Serà anomenat hash, i és va a acceptar com a argument un cadena, o podem ser més apropiat ara, i dir char *, l'anomenarem s. I després, aquesta funció té a veure, en última instància, es torna un int. Ara, com es fa això podria no ser tan clara. Vaig a posar en pràctica això sense cap forma de comprovació d'errors en aquests moments. Jo només vaig a dir a cegues, torneu el que estigui a escaire s 0, almenys, diguem, la capital un punt i coma. 

Totalment trencat. No és perfecte, perquè un, el que si s és nul? Les coses dolentes van a passar. Dos, i si la primera lletra en aquest nom no és una lletra majúscula? Això no va a girar fos ben tampoc. Pot ser que sigui una lletra minúscula o no una carta a tots. Així que totalment marge de millora, però aquesta és la idea bàsica. 

El que descrivim la setmana passada verbalment un procés d'assignació d'Alice 0 a 1 i Bob poden expressar sens dubte més formulaically com C funcionar aquí. Crida de nou hash, pren una cadena com d'entrada, i llavors d'alguna manera fa una mica amb aquesta entrada per produir una sortida. No gaire diferent de la nostra descripció quadre negre el que hem fet sempre. No sé com podria ser treball sota de la caputxa. 

Per butlletí de problemes 6, un dels reptes és perquè vostè decideixi què Serà la seva funció hash? Què va a estar dins d'aquest negre caixa, i, presumiblement, serà un poc més interessant que això, i definitivament més propens a errors comprovar que el particular aplicació. 

Però poden sorgir problemes, oi? Si tenim una estructura de dades com aquest un, el que és un dels problemes es pot executar en el temps a mesura que s'insereix més i més noms a la taula hash? Vostè aconsegueix col · lisions, oi? Què passa si vostè té Alice i Aaron, dues persones els noms passat començar amb A? Això planteja la pregunta, en què posar el segon com un nom? 

Bé, potser ingènuament, només cal posar on Bob pertany, però Bob és tipus de rosca si intenta inseriu el nom al costat i no hi ha lloc per a ell. Així que es podria posar Bob on Charlie és, i es pot imaginar això molt ràpidament delegar en una mica d'un desastre. Una cosa lineal en el final, on només has de buscar en tot l'assumpte a la recerca d'Alice o Bob o Aaron o Charlie. 

Així que en comptes ens proposa, en lloc de linealment sondeig d'espais oberts i deixant-se els noms allà, proposat un enfocament més elegant. Una taula hash implementat encara amb un array d'índexs, però el tipus de dades aquests índexs ja eren punters. Punters a què? Punters a les llistes enllaçades. 

Perquè recordo que una llista enllaçada és en realitat un punter a un node, i el node té un camp proper, i que el node té un camp següent, i així successivament. Així que ara pot pensar en aquest conjunt de el costat esquerre d'una taula hash com que condueix a una llista enllaçada. L'avantatge que si et donen una col · lisió entre Alice i Aaron, Què fer amb el segona d'aquestes persones? Acabes de connectar o ella a l' final, o fins i tot el principi d'aquesta llista enllaçada. 

I, de fet, anem a través de fideus que per un segon. On tindria la majoria del sentit? Si inserit Alice i ella acaba en el primer lloc, llavors intento inseriu el nom d'Aaron, i hi ha òbviament una col · lisió, hauria de posar ell al principi de la llista enllaçada? Això és pel que el primer lloc, o al final? 

AUDIÈNCIA: [inaudible]. 

DAVID Malan: OK. Vaig sentir començant. Per què al principi? 

AUDIÈNCIA: [inaudible]. 

DAVID Malan: OK. És per ordre alfabètic, per la qual cosa és bo. Aquesta és una bona propietat. Es em va a estalviar una mica de temps potencialment. No em deixa fer recerca binària, però podria almenys ser capaç de trencar d'un bucle si m'adono, bé, jo sóc així passat eren Aaron seria en aquest ordenats llista enllaçada. Jo no he de perdre el temps buscant tot el camí fins al final. Així que això és raonable. Per què més podria voler inserir el nom de xocar a la principi de la llista? Què és això? 

AUDIÈNCIA: [inaudible]. 

DAVID Malan: Podria ser molt llarg per arribar al final de la llista. I, de fet, més i més. Quants més noms que s'insereix començar amb una, més que la cadena es posarà. Com més temps vinculat llista va a aconseguir. Així que vostè és realment just perdent el temps. Potser és millor mantenir temps d'inserció constant, gran O d'1, per sempre posant el nom al xocar el principi de la llista enllaçada, i no preocupar-se tant sobre l'ordenació. 

Quina és la millor resposta? No està clar. És una cosa que depèn del que l' distribució és, quin és el patró dels noms que va a inserir. No és necessàriament una resposta òbvia. Però aquí per, de nou, és una oportunitat de disseny. 

Així que a continuació analitzem això, que és realment l'altra gran oportunitat de p-6 set. I adonar-se, si no ho ha fet, Zamyla submergeix en tots dos, haixix taules i tracta, de forma més detallada. I el tutorial de vídeo és incrustat en p-conjunt d'especificacions. Aquest era un trienni - T-I-I-E. I el que era interessant això va ser que el temps d'execució de la recerca d'un nom, com Maxwell l'última vegada, era gran O de què? Què és això? 

AUDIÈNCIA: El nombre de lletres. 

DAVID Malan: Nombre de lletres. Vaig escoltar dues coses. Nombre de lletres i de temps constant. Així que anirem amb la primera. El nombre de lletres. Doncs bé, aquesta estructura de dades, recuperació, és com un arbre, un arbre de la família, cadascun els nodes es componen de matrius. I aquests arrays són punters a altres tals nodes, o altres tals matrius en l'arbre. 

Així que si volem després determinar si Maxwell és aquí, jo podria anar a la primera sèrie, en la part superior de la l'arbre, l'anomenada arrel, la part superior de el trienni i segueixi el punter m, llavors el un punter, llavors x, w, i, l, l. I quan veig algun símbol especial, denotada aquí com un triangle. En el codi veuràs que proposem que implementat com un bool, només dir que sí o no, una paraula s'atura aquí. 

Bé, una vegada que hem anat a la M-A-X-W-E-L-L, se sent com set, potser vuit si anem un passat, vuit passos per trobar Maxwell. O el anomenarem K. Però recordem última temps, va sostenir que si hi ha realista una longitud màxima d'un paraula, com els personatges de 40 i escaig, un longitud màxima implica un valor constant. Així que en realitat, sí, és tècnicament gran O de 8 o 7, o molt gran O de K. No obstant això, si hi ha un límit finit en el K pot ser, és una constant. I el que és gran O d'1 a al final del dia. 

No hi ha al món real. No és quan realment comença a veure el rellotge del seu funcionament com del seu programa. És absolutament va a ser una mica més lent que veritablement constant temps amb un pas. Serà set o vuit passos, però tot i així és molt, molt millor d'un algorisme com el gran O de n que depèn de la mida del que hi ha a la estructura de dades. 

Observeu el costat positiu aquí és que podem inserir un milió més noms en aquesta estructura de dades, però la quantitat de passos més és que va a portar-nos a trobar Maxwell, en aquest cas? Cap. És afectat. I fins ara, no crec que hàgim vist un exemple d'una estructura de dades o un algoritme que era completament afectat per externa comportaments així. Però això no pot ser increïble. Això no pot ser l'única solució per al p-set 

I no ho és. Això no és necessàriament les dades estructura que ha de gravitar, perquè igual que les taules hash, equilibri. Quin és el preu que es paga? Memòria. És a dir, es tracta d'una atroç quantitat de memòria. I no es pot veure bé aquí perquè l'autor d'aquesta imatge òbviament truncada totes les matrius, i no estem veient un munt d'i B i C i Q i I i Z de en aquestes matrius. Però hi són. 

Cadascun d'aquests nodes és tot un seguit d'uns 26 o més bytes, cadascun dels el que representa una lletra. 27 en el nostre cas, pel que podem donar suport apòstrofs en el conjunt de problemes. Per tant aquesta estructura de dades és realment, molt densa i àmplia. I això només podria acabar la desacceleració les coses, o almenys li costa molt més espai. Però una vegada més, podem treure comparacions aquí. 

Recordem fa un temps, hem aconseguit molt més emocionant temps de funcionament en la classificació quan fem servir merge tipus, però el preu que paguem per aconseguir n log n de fusió tipus requereix que passem més el que els recursos? Més espai. Necessitàvem una matriu secundària a copiar a la gent en, igual que que vam fer aquí a l'escenari. Així que de nou, no hi ha clars guanyadors, però només el disseny subjectiva que es prenguin decisions. 

Està bé. Així que què hi ha d'això? Qualsevol persona reconeix que D-Hall? D'acord. Així que tres de nosaltres. Mather House. Així que això és per un sopar de Mather. Aposto a tots els menjadors tenen piles de safates els agrada. I això és realment representativa d'alguna cosa que hem òbviament vist. En diem literalment una pila. I la pila, en termes de la seva la memòria de l'ordinador, és on va dades mentre que les funcions estan sent cridats. 

Per exemple, quin tipus de coses van a la pila que fa a la disseny de la memòria que hem discutit en les últimes setmanes? Què és això? 

AUDIÈNCIA: Les crides a funcions. 

DAVID Malan: Ho sento. 

AUDIÈNCIA: Les crides a funcions. 

DAVID Malan: Les crides a funcions, però en concret, el que hi ha dins de cada un els marcs? Quin tipus de coses? Si. Per tant les variables locals. Cada vegada que necessitàvem alguna cosa d'emmagatzematge local, com un argument o int I, o int temp, o el que sigui el local variable, hem estat posar que a la pila. I en diem una pila perquè d'aquesta idea d'estratificació. Només tipus de partits amb la realitat, el concepte dels mateixos. 

Però resulta que una pila pot també ser vist com una estructura de dades, un alternativa a una matriu, una alternativa d'una llista enllaçada. Una mica conceptualment més interessant que encara pot ser implementat mitjançant un dels coses, però és un tipus diferent de estructura de dades de suport, de veritat, només dues operacions. Però pots afegir més elegant característiques que aquests. Però aquests són els fonaments - inserir i extreure. 

I la idea amb una pila és que si jo tenim aquí, amb o sense Annenberg saber, una safata del costat amb el número 9 en ell. Així que un int. I vull portar aquest a les dades estructura, que actualment està buida. Penseu en això la part inferior de la pila. M'agradaria portar aquest número 9 en el pila, i ara hi és. 

Però l'interessant d'una pila és que si ara vull empènyer algun altre valor, com 17, i empenyo aquesta a la pila, ho faré l'única cosa intuïtiva, només vaig per posar les coses bé quan els éssers humans m'inclinaria a posar, a la part superior. Però el que és interessant ara És a dir, com puc aconseguir a les 9? Vostè sap, jo no sense cert esforç. 

Així que l'interessant d' una pila és que per disseny, que és una estructura de dades LIFO. Manera tonta de descriure últim a entrar, primer a sortir. Així que l'últim nombre de en aquest moment tenia 17 anys. Així que si vull fer esclatar una mica de de la pila, només pot ser 17. Així que hi ha una ordre obligatòria de operacions aquí, on l'últim element in ha de ser el primer a sortir. D'aquí l'acrònim, LIFO. 

Per què pot ser això útil? Són els contextos en què havia volen una estructura de dades com aquest? Bé, ha estat sens dubte útil a l'interior d'un ordinador. Per tant els sistemes operatius utilitzen clarament tipus d'estructura de dades per a piles. També veurem la mateixa idea quan es tracta de pàgines web. Així que aquesta setmana i la propera setmana i més enllà, i en començar l'aplicació web pàgines en un llenguatge anomenat HTML, pot realment utilitzar una estructura de dades com això per determinar si la pàgina és el format correcte. Perquè anem a veure totes les pàgines web segueixen una mena de jerarquia, una escotadura que, al final del dia, ser un estructura d'arbre sota de la caputxa. Per tant més d'això en una mica. 

Però per ara, anem a proposar una Actualment, com podem anar sobre representant el que és una pila? Permetin-me proposar que implementem una pila amb un codi com aquest. Així que una pila va a tenir dins d'ella dues coses, una gran varietat, anomenats safates, només per estar en consonància amb la demo. I cada un dels elements de la matriu serà un tipus int. I la capacitat és de suposar que el que? Perquè jo no he escrit el la definició completa aquí. 

És probablement el màxim mida de la matriu. I és probable que va declarar com un fort definir en la part superior de l'arxiu, alguns espècie de constant, obtingut per la mera capitalització. Així en algun lloc capacitat es defineix com la mida màxima possible. Mentrestant, a l'interior de l'estructura de dades conegut com una pila haurà ser un enter només coneguda simplement com grandària. 

Així que si jo fos a representar aquesta empresa pictòricament, suposem que aquest quadre negre representa tota la meva pila. A l'interior de la mateixa és dues variables. Així que vaig a assenyalar a la primer un com grandària. I el segon que vaig per dibuixar com una matriu. 

Però només per mantenir les coses en ordre, Normalment m'agradaria anomenar una matriu com això, però és una mica agradable si coincideixen amb la realitat, o coincideixi amb el model mental. Així que em baso en lloc de la matriu verticalment, que és just, de nou, interpretació de l'artista. Realment no importa el que que hi ha sota el capó. I direm que, per defecte, capacitat va a ser tres. Així que aquesta serà la posició 0, serà ubicació 1, aquest serà ubicació 2. 

Si subornar amb una bola de la tensió, ho faria a algú li agrada pujar i executar el abordar aquí per un moment? Bé, vaig veure la mà primer. Anem amunt. Està bé. Així que crec que és Steven. Anem amunt. Està bé. 

Però suposem ara que rebobinar fins al primer estat del món en què només han declarat una pila, i és tindrà una capacitat de tres. Però la mida encara no s'ha determinat. Safates encara no ha estat determinada. Així que un parell de preguntes primer. I et donaré micròfon perquè pugui participar més activament en això. 

Així que el que hi ha dins de la seva grandària en aquest moment a temps si tot el que he fet és declarat una pila amb una línia de codi? 

STEVEN: No gaire. 

DAVID Malan: OK, no gaire. Sabem que hi ha dins de la seva grandària, sabem el que hi ha dins d'aquesta varietat aquí? 

STEVEN: Just codi aleatori, oi? Just - 

DAVID Malan: Sí, vaig a cridar codi, però l'atzar - 

STEVEN: Coses. 

DAVID Malan: Coses com l'atzar 

STEVEN: Bits. 

DAVID Malan: Bits, oi? Per tant els valors de fem, oi? Així permutacions de 0 i 1 de. Les restes d'usos anteriors d'aquesta memòria. I no se sap molt bé quins són els valors estem, pel que normalment els allunyarem com a signes d'interrogació. 

Així que el primer que estem suposadament voldrà fer aquí - i et donaré aquest camp dins d'aquí el nom - safates. Què hem de suposar inicialitzar mida si volem començar a utilitzar aquesta pila? 

STEVEN: Tray és sub 3. 

DAVID Malan: Llavors, OK. Per ser clars, la capacitat es declara en altres llocs com tres. I això és el que he fet servir per assignar la matriu. La mida es va a fer referència a la quantitat de safates són actualment a la pila. 

STEVEN: Zero. 

DAVID Malan: Així ha de ser zero. Així que endavant, i amb un dit, dibuixar un zero en grandària. Està bé. Així que ara, el que hi ha dins d'aquest aquí, no sabem. Aquests són en realitat els valors de fem. Així que podríem dibuixar signes d'interrogació, però Anem a mantenir el tauler net per ara , Ja que no importa el que hi ha. No necessitem per inicialitzar la matriu per a res, perquè si sabem que la mida de la pila és zero, bé, no s'ha de mirar res en aquesta matriu de totes formes en aquest punt en el temps. 

Així que ara suposo que pols el número 9 a la pila. Com hem d'actualitzar l'estructura de dades dins d'aquest requadre negre? Quins valors hi ha necessitat de canviar? 

STEVEN: Distància - la mida? 

DAVID Malan: OK. Mida hauria de ser què? 

STEVEN: Mida seria un. 

DAVID Malan: OK. Així que mida ha de ser un. Així que vostè pot fer això en un parell de maneres. Et vaig a donar, ja que la seva dit és un esborrany. Està bé. Llavors ara el dit és un raspall. Està bé. I ara, què més ha de canviar, òbviament, en l'estructura de dades? 

STEVEN: Anem a inferior a 9. 

DAVID Malan: 9. Bé, bé. Així que encara no importa el que està en ubicació d'un o dos, perquè són valors d'escombraries, però no han de preocupar buscant allà perquè la mida és que ens diu que només el primer element en realitat és legítima. Així que ara em empenta 17 a la llista. Què passa amb aquesta imatge? 

STEVEN: Així que la mida va a anar a dues. 

DAVID Malan: OK. Ets esborrany - Ui. Vostè és un esborrany. 

STEVEN: Esborrany. 

DAVID Malan: Ets un raspall. 

STEVEN: Brush. 

DAVID Malan: OK. I què més? 

STEVEN: I llavors - 

DAVID Malan: Ens va empènyer 17. 

STEVEN: Ens enganxem 17 a la part superior, de manera que - 

DAVID Malan: OK, bo. 

STEVEN: - caure cap avall. 

DAVID Malan: Molt bé. S'està posant fàcil. Jo no vaig a ajudar-te aquesta vegada. Empenta 22. 

STEVEN: Fet. Convertir-se en un esborrany. M'estic convertint en un raspall. I llavors em poso 22. 

DAVID Malan: 22. Excel · lent. Així que una vegada més. Ara vaig a empènyer a la pila 26. 

STEVEN: Ooh. Oh Déu meu. Realment em va prendre per sorpresa. 

DAVID Malan: No ho vas fer veure venir això? 

STEVEN: No ho vaig veure venir. Podríem capacitat de tornar a primera? 

DAVID Malan: Aquesta és una bona pregunta. Així que hem tipus de pintem en un racó aquí. Realment no hi ha bona per Steven perquè hem assignat aquest array estàticament, per així dir-ho, a l'interior de l'estructura de dades. I hem codificat essencialment dur que sigui de la mida de tres. Així que en realitat no podem reassignar. 

Podríem Si tornem, ens redefinits safates per ser un punter que , Utilitzem la memòria malloc mà. Perquè si tenim la memòria d' la pila a través de malloc, que llavors podria alliberar-lo. Però abans d'alliberar-la, podríem reassignar un tros més gran de la memòria, actualitzar el punter, i així successivament. Però per ara, això és realment El millor que podem fer. Push i pop van presumiblement a haver d'indicar algun error. 

Així, per exemple, la nostra implementació d'empenta podria tornar un bool que prèviament retornat true, true, true. Però el quart temps, que tindrà perquè torni false, per exemple. Està bé. Molt ben fet. Enhorabona. T'has guanyat la bola de la tensió actual. 

[Aplaudiments] 

STEVEN: Gràcies. 

DAVID Malan: Gràcies. OK, així que això sembla ser no gaire d'un pas endavant, no? Hem descrit aquesta estructura de dades. Ha estat convincent, ¿no? Els sistemes operatius agrada. Segons sembla, la web pot fer ús d'aquest, i altres aplicacions fixes. Però el que és una limitació estúpids que som tornar al tipus de setmana dos límits on hem fixat matrius de mida. 

Així que de fet hi ha un parell de formes en que podrien resoldre això. Podríem assignar dinàmicament la matriu, no per la força de codificació com he fet aquí, però en el seu lloc tornar a declarar això, per ser clars, com alguna cosa com això. Int * safates, no decidir en una capacitat encara. Però quan em declaro la pila en altres llocs en el meu codi, podria llavors cridar a malloc, obtenir la direcció d'un tros de memòria, i podria assignar que la direcció de les safates. 

I després, perquè és només un tros de memòria, podria seguir utilitzant quadrat notació de claudàtors de la forma habitual. Perquè de nou, hi ha una espècie d'aquest equivalent funcional de les matrius i trossos de memòria que vénen darrere de malloc. Podem tractar a un com l'altre mitjançant aritmètica de punters o la notació de claudàtors. Així que aquest és un dels enfocaments. 

Però, com més podem posar en pràctica aquesta mateixa estructura de dades, potencialment? Cert? Em sento com si haguéssim resolt aquest problema com fa una setmana. Quina va ser la solució a aquest problema que es va trobar amb Steven? Així llistes vinculades, cert. 

Si el problema és que estem pintant a nosaltres mateixos en una cantonada per l'assignació de en molt poca memòria endavant que ens llavors ha de tractar d'alguna manera amb, bé, ¿Per què no evitar que emetre en total? Per què no declaren safates per ser un punter a un node, ergo una llista enllaçada, i després simplement assignar nous nodes cada vegada que Steven necessari per ajustar a un nombre en l'estructura de dades. 

Així que la imatge hauria de canviar. No serà tan net i tan simple com un conjunt de tres enters. Ara que serà un punter a una estructura, i que es va a struct tenir un int i un punter de següent. Es durà a través d'aquest punter a un altre tal estructura a altra com a estructura. Així que la imatge en realitat ser una mica desordenat. I ens hem fletxes lligar tot junt. 

Però això està bé, bé, perquè hem vist com fer això. I una vegada que vostè se senti còmode alguna cosa com una aplicació vinculada llista, que haurà de fer si triar implementar una taula hash amb encadenament separat per p-set 6, pot usar-lo com un bloc de construcció, o un ingredient, o esgarrapades dir, un procediment, cosa que es posa, que crear la seva pròpia peça del trencaclosques que després es pot tornar a utilitzar. Compensacions que sí, però les possibles solucions que hem vist realment abans. 

Així que molt sovint, es veu això tots els any o dos quan llançaments d'Apple alguna cosa nova, i tots els bojos alineació exterior de l'illa botiga a comprar el seu marginal actualitzar el maquinari. Dic això, està bé, perquè Jo sóc una d'aquestes persones. Llavors, quin tipus d'estructura de dades podria representar aquesta realitat? 

Bé, anem a anomenar una cua, una línia. So British diria que és típicament un cua de totes maneres, així que és un nom bonic. I les dues operacions que una cua donarà suport anomenarem 1 enqueue funcionament i una operació de treure de la cua, els quals són similars a esperit per inserir i extreure. És només una mena de diferent en Convenció, el que anomenem aquests. Però per posar en cua alguna cosa significa afegir o inserir-lo en l'estructura de dades. Per treure de la cua consisteix en la seva eliminació. No obstant això, mentre que una pila de dades LIFO era un estructura, una cua és una primera a, primer a l'estructura de dades. 

Si vostè és la primera persona de la fila, vostè serà la primera persona a arribar fora de línia i comprar el seu nou dispositiu. Imagina't el mal que serien aquestes persones si Apple utilitza en el seu lloc una pila, per exemple, per implementar la recol · lecció de la seva nova joguina. Així cues tenen sentit, sens dubte, i podem pensar en tot tipus de aplicacions, presumiblement, per les cues, especialment quan es vol justícia. Així que com podem posar en pràctica aquests com una estructura de dades? 

Bé, jo proposo que podria ho ha de fer d'aquesta manera. Així que vaig a tenir ara números. Així que anem a mantenir simple i no necessàriament parlar en termes de safates. Només els números que la gent de hagudes. La capacitat es va a, una altra vegada, fixar el nombre total de persones que poden estar en aquesta línia, ja que tres o qualsevol altre valor. 

Però proposo que necessito per realitzar un seguiment no només de la mida de la cua, quantes coses hi ha. Així que la mida és la mida actual, la capacitat de és la mida màxima. Només una vegada més, la nomenclatura per convenció. ¿Per què necessito un int addicional dins d'una cua per realitzar un seguiment de qui està dins davant de la línia? Per què he de fer això en aquest cas? 

Bé, com és aquesta imatge canviarà? És probable que pugui tornar a utilitzar més d'aquesta imatge. Deixin-me seguir endavant i esborrar el que hi ha aquí. Donarem això una mica nom diferent aquí. Anem a desfer-nos dels 17, anem a desfer del 9, anem a desfer dels 3. I anem a afegir una cosa més. Proposo que he de portar un registre de al capdavant de la llista, que és només serà un sencer també. I anem a mantenir simple. No hi ha una llista vinculada per ara. 

Anem a admetre que anem a topen amb aquest límit. Però, ¿què és el que vull veure succeirà aquesta vegada? Així que suposo que vaig per davant i la primera persona que apareix en la línia, i és el número 9. Tenim boles de la tensió. Puc robar, per exemple, dues o tres persones? Un, dos, tres? Anem amunt. Des del front, perquè farem això ràpid. 

Cada un de vosaltres està ara serà un noi de ventilador en línia d'Apple. No va a rebre els equips d'Apple al final d'això, però. Està bé. Així que vostè és el número 9, que està número 17, número 22. Aquests són nombres arbitraris, com ID d'estudiant o el que sigui. I en un moment, anem a començar per començar a afegir coses. I vaig a córrer el tauler aquí aquesta vegada. 

Així que en aquest cas, he inicialitza el front que sigui - En realitat no m'importa el que el davant és, perquè la mida és zero. Així que pot ser que també acaba de ser un signe d'interrogació. Tots aquests són signes d'interrogació. Així que ara anem a començar a veure realment alguns gent fent cua a la botiga. 

Així que si el nombre 9, que és el primer a les 5 AM, seguir endavant i alinear, o de la nit anterior. D'acord. Així que ara 9 està aquí. Així és 9 a la part frontal de la llista. Així que seguiré endavant i actualitzar la mida d'aquestes dades actuals estructura perquè no sigui 0 més, però per ser 1. Me'n vaig a posar en el 9 capdavant de la llista. Deixin-me seguir endavant i canviar la pantalla pel que podem veure més enllà de nosaltres. 

I ara, ¿què és el que vull posar al capdavant? Vaig a fer un seguiment que l' capdavant de la cua en aquest moment està en la posició 0. Perquè el que està al costat passarà? Bé, suposo que ara em Enqueue 17 també. Així que saltar en línia allà. I de nou, el tipus de porta a la botiga va a ser aquí. Així que ara he afegit 17. I malgrat que aquests nois estan bloquejant la pantalla, això està bé, perquè podem veure-ho aquí. Ho sento. 

AUDIÈNCIA: Podem moure - 

DAVID Malan: No, això està bé. És enorme allà. Així 17 és ara dins de la cua. Necessito actualitzar el que camps, tot i que ara? Bé, definitivament mida. ¿I què hi ha davant? Bé, no. Davant no ha de canviar, perquè a diferència d'una pila, que vol mantenir l'equitat. Així que si 9 va arribar en primer lloc, volem setembre per ser el primer a sortir de la línia de i dins de la botiga. 

De fet, anem a veure això. Abans que ens inserim 22, anem a seguir endavant i treure de la cua 9. Quin és el teu nom? 

AUDIÈNCIA: Jake. 

DAVID Malan: Jake va ser llevades ara. Així que has de caminar a la botiga. I pretendre que la botiga és per aquí. Així que ara el que cal - dit-dit-dit! ¿Què ha de passar ara? Decisió de disseny. Així que no és un mal instint, però - Quin és el teu nom? 

AUDIÈNCIA: David. 

DAVID Malan: David. Així ho va fer David? Ell estava tractant d'ordenar de fixar les dades estructura i el moviment de la seva ubicació en primer lloc de Jake. I això està bé si estem disposats acceptar que com detall d'implementació. Però primer, anem a actualitzar les dades estructura abans de fer això. Perquè jo no m'està agradant la idea de tots el poble el canvi en aquesta línia. 

No és gran cosa si David ho fa amb un pas, però de nou, pensi en quan hem tingut vuit voluntaris en el escenari i el que hem fet com la inserció Ordena, on vam haver de començar moure tots al seu voltant. Això va fer car, no? Això em fa tremolar sobre Big O de N, O gran de n al quadrat de nou. No se sent com un resultat ideal. 

Així que anem a actualitzar això. Per tant la mida de la cua ja no és 2. Ara és simplement 1. Però ara puc actualitzar alguna cosa No vaig actualitzar abans, la capdavant de la llista. Jo podria dir és que la ubicació 1? Així que ara tenim el valor d'escombraries aquí, Valor d'escombraries aquí, i David al mitjà d'aquestes escombraries. No obstant això, l'estructura de dades encara està intacta. 

I, de fet, jo ni tan sols necessito canviar exnúmero de Jake 9, ia qui li importa. No tinc prou informació ara al mida que sé que hi ha una persona en aquesta cua. I sé que aquesta persona està en la posició 1, no 0. No estic explicant. Així gener també. Així que l'estructura de dades és tot i així està bé. 

Bé, què passa després? Posarem en col - Quin és el teu nom? 

AUDIÈNCIA: Callen. 

DAVID Malan: Callen. Posarem en cua un Callen i 22 és ara a la cua. Així que ara el que ha de canviar aquí? Davant no va a canviar, òbviament. Mida canviarà per ser de nou 2. I 22 acaba aquí, el 9 és encara present, però és efectivament un valor de les escombraries ara. És només un romanent de Jake passat. 

¿I ara què passa si I dequeue David? Una última operació, dequeue David. Podem canviar, però anem a proposar fer el menor treball possible. Ara la meva estructura de dades es una còpia en grandària de 2 a 1. No obstant això, la part davantera de la cua ara es converteix en 2. No necessito canviar aquests nombres però just, perquè són només els valors d'escombraries. 

Però ara, què passa? Suposem que Enqueue mi mateix, 26? Sento que pertanyo aquí. Així que estic sent en cua. Així que tipus de pertanyo aquí. I tot i que no arriben apreciar aquesta visuals a l'escenari, perquè tenim un munt d'espai, el que hauria no ser aquí, per què? 

AUDIÈNCIA: Vostè està fora dels límits. 

DAVID Malan: Sí. Estic fora dels límits. He s'indexen més enllà de la límits d'aquesta matriu. Realment hauria d'estar en un dels tres possibles ubicacions. Ara, on és més natural que anar? Proposo que palanquejats una setmana un truc. L'operador mod, percentatge. Perquè estic tècnicament peu a localització 3, però jo sí la capacitat de 3 mod, so 3, un signe de percentatge, 3 - la capacitat de 3. Què és això? Què és el que queda quan es divideix 3 per 3? 0. 

Així que això em posa Jake es va anar, que és realment bo. Així que ara l'aplicació d'aquesta cosa va a ser una mica d'un mal de cap. És realment una sola línia de mal de cap, de codi. Però almenys ara hi ha deixalles valor aquí, però no hi ha dos ints legítims aquí. I afirmo que ara hem fet exactament el que hem de fer, sempre que canviem el de Jake Valor anava a ser 26. 

Ara tenim prou informació encara per mantenir la integritat d'aquesta estructura de dades. Encara estem una mica fora de sort quan voleu inserir quatre o més totals elements, però almenys puc fer força ús eficient d'aquesta constant temps, de fet. Jo no he de preocupar pel canvi tots, ja que la inclinació de David era. 

Qualsevol pregunta sobre les piles, o aquesta col? 

AUDIÈNCIA: És la raó per la vostè necessita mida perquè vostè sàpiga on té una persona? 

DAVID Malan: Exactament. Necessito saber la mida de la matriu perquè he de saber exactament com molts d'aquests valors són legítims, i perquè jo pugui trobar on posar la següent persona. Exactament. La mida és - En realitat, no ens actualitzem això encara. Jo vaig agregar jo en 26. La mida és ara, no 1, però 2. Així que ara aquest fet ajuda a trobar la cap de la llista, que no és 0, no 1, però és 2. El front de la llista és de fet el nombre 22. A causa de que va arribar en primer lloc, pel que ha de ser admesos a la botiga abans de mi, tot i que visualment estic parat més a prop de la botiga. 

D'acord? Un aplaudiment per a aquests nois i deixarem que treure'ls d'allà. 

[Aplaudiments] 

DAVID Malan: podia deixar que a mantenir la safata. Vam poder veure el que passa si que vulgui, però potser no. Està bé. ¿I ara què ens deixa això? Bé, permetin-me proposar que hi ha un algunes altres estructures de dades que vam poder començar a afegir al nostre conjunt d'eines que en realitat ser molt, molt rellevant com ens submergim en coses web. Que al seu torn, té algun tipus de connexió als arbres en la forma d' cosa que es diu DOM, document model d'objectes. Però anem a veure més que en poc temps. 

Permetin-me proposar per definició que truqui al arbre ja ho deus saber com més d'un arbre, en el qual tenir algun avantpassat en el arrels de l'arbre. Una matriarca patriarcal o en la part més alta de l'arbre. Sense la seva cònjuge, en aquest cas. Però ara tenim el que anomenem els nens, que són els nodes que pengen fos el fill esquerre o el dret de l'infant, fletxes com s'il · lustra aquí. 

En altres paraules, en una estructura de dades en arbre a l'ordinador, un arbre té zero o més nodes. Si té almenys un node, que es diu l'arrel. Són les coses visualment que ens basem en la part superior. I aquest node, com qualsevol altre node, pot tenir zero, un, o dos, o tres, o però molts nens estructura de dades compatible. En aquest cas, l'arrel, l'emmagatzematge de la valor d'un, té dos fills, de 2 i 3, pel que generalment anomenem 2 de la esquerra nens i 3 el fill dret. 

I després, quan ens posem mans a la 5, 6 i 7, 6 podria ser cridat el fill del medi. Si vostè té quatre fills, es torna confús. Així que deixem d'usar aquest tipus d'accés directe verbalment. Però no deixa de ser un arbre genealògic. I les fulles aquí són els nodes que ells no tenen fills. Es pengen de la part inferior de l'arbre. 

Llavors, com podríem implementar un arbre que només té dos fills al màxim? L'anomenarem un arbre binari. Bi nou significa dues, en aquest cas, igual que amb el binari. I pel que pot tenir zero, un, o dos nens al màxim. 

Jo proposo que implementem el node perquè l'estructura amb una n int, i després dos punts, un anomenat a l'esquerra, un anomenat dreta. Però aquests són només agradables convencions arbitràries. I el que és bo ara, sobretot si tipus de lluitar conceptualment amb recursió, o pensar que no era realment una solució a res, especialment si es pogués quedar-se sense memòria. Ara que estem parlant de dades estructures i algorismes que permeten nosaltres travessem i manipular-los, Resulta que la recursivitat torna a una forma molt més convincent si no bonic camí. 

Així que proposo és la implementació d'una funció de cerca. Donades dues entrades - de manera que pensar en això com un quadre negre. Donades dues entrades, n, un enter i un punter a un arbre, un punter a una node, o en realitat l'arrel d'un arbre, afirmació que aquesta funció pot retornar vertader o fals, que el valor de n està dins d'aquest arbre. 

Què hi ha dins d'aquest quadre de negre? Bé, quatre branques. Comprova la primera justa. Si l'arbre és nul · la, torna falsa. Si no hi ha un node, no hi ha n, no hi ha un nombre, simplement return false. Si, però, n, el valor que està buscant per, és menys d'arbre de fletxa n, i només perquè quedi clar, el que vol dir quan Escric arbre i després la fletxa notació, n? Exactament. Això significa eliminar la referència que punter diu arbre. Anar-hi i, a continuació, entrar d'aquesta node i aconseguir el seu camp anomenat núm. I a continuació, comparar el núm real que era passat a la recerca contra ell. 

Així que si n és menor que, el valor de n en el node de l'arbre en si, bé, Què significa això? Això no vol dir res a primera vista. Cert? Igual que quan vostè té una gran varietat de valors, que et poden agradar aplicar binari buscar una forma de divisió i conquerir. Però, quines hipòtesis ens hem de fer de recerca binària per treballar en totes les a la guia telefònica i exemples anteriors? 

Com ser ordenats. Així que anem a refinar la definició d'arbre aquí no per ser només un arbre, que pot tenir qualsevol nombre de fills. No és només un arbre binari, el que pot tenir 0, 1 o 2 com a màxim. Però, com un arbre de cerca binària, o BST, que és només una forma elegant de dir que una arbre binari de manera que cada node fill esquerre, si està present, és menys que el node. I el dret de tot infant de node, si està present, és més gran que el mateix node. 

En altres paraules, si fos a dibuixar el cap de l'arbre, tots els números són curosament equilibrada com aquest, així que si Té 55 com l'arrel, 33 poden anar a la seva esquerra, ja que és menys de 55. 77 pot anar a la dreta, perquè és major de 55 anys. Però ara compta, la mateixa definició, és una definició recursiva verbalment, ha de demanar 33. Fill esquerre de 33 ha de ser menor del que, i el fill dret de 33, 44, ha de ser més gran del que. 

Així que aquest és un arbre binari de recerca, i Proposo, amb una mica de recursivitat, ara podem trobar n. Així que si n és menor que el valor de n que és node actual, aniré endavant i batea, per així dir-ho, i només tornar el que la resposta és de la recerca de n en la fill esquerre de l'arbre. Note una vegada més, aquesta funció només espera un estel node, 1 punter a un node. Així que sens dubte jo puc fer arbre fletxa cap a l'esquerra, el que conduirà em a un altre node. Però, què és aquest node? 

Bé, d'acord amb aquesta declaració, esquerra és només un punter, pel que només vol dir que estic passant a la funció de cerca un punter diferent, a saber, el que representa l'arbre del meu fill esquerre. Així doncs, en aquest cas, el punter a 33, si aquesta és la nostra entrada de la mostra Mentrestant, si n és major que el valor de n en la node actual en l'arbre, llavors jo sóc va a seguir endavant i rebuig en l'altra direcció i dir, jo no saber si aquest valor de n està en l'arbre, però sé que si ho és, és per la meva branca dreta, per així dir-ho. Així que em diuen recursivament recerca, passar un n altra vegada, però que passa en un punter al meu fill dret. 

En altres paraules, si estic actualment en 55 i estic a la recerca de 99, jo sé que el 99 és més gran que 55, pel que igual que jo vaig arrencar la setmana de l'agenda i ens fa va anar a la dreta, de la mateixa manera som va a anar aquí. I jo no sé si és a la meva dreta nen, i no és, el 77 hi és, però Sé que és en aquesta direcció. Així que dic cerca en el meu fill dret, 77, i deixar que figura recerca des si hi ha 99 en aquest arbitrària exemple és realment allà. 

Si no, quin és l'últim cas? Si l'arbre és nul · la és un dels casos. Si n és menor que el node actual de valor és un altre cas. Si n és més gran que el corrent el valor de node és un tercer cas. Quin és el quart i últim cas? Crec que estem fora dels casos, no? Deu ser que n està en el node actual que estic. 

Així que si estic a la recerca de 55 en aquest moment en la història, aquesta branca de la arbre tornaria realitat. Així que el que és interessant aquí és que En realitat, a diferència de setmana passat, quin tipus tenen de dos casos de base. I ells no han de estar a la part superior. La part superior és un cas base, perquè si el arbre és nul, no hi ha res a fer. Simplement envieu un disc codificat valor false. 

La branca inferior és una espècie de per defecte, de manera que si hem comprovat en null, hem comprovat si ha de ser a l'esquerra, però no ha de ser, tenim comprovar si s'ha d'estar en el cert, però no ha de ser, clarament, ha de ser just on som. Això és un cas base. Així que hi ha dos casos recursius intercalat en el medi. Però jo podria haver escrit això en qualsevol ordre. Només vaig pensar que semblava una mica naturals comprovar primer per a un possible error, a continuació, comproveu l'esquerra, a continuació, comprovar bé, llavors se suposa que està en el node en realitat estàs buscant. 

Per què pot ser això útil? Així que resulta - i m'ho dius a mi saltar a un teaser aquí que hi ha al web. Anem a començar a utilitzar no és un llenguatge de programació al principi, però una llenguatge de marques. Un llenguatge de marques és un que és similars en esperit a la programació llenguatge, però no li dóna la capacitat d'expressar-lògicament. Només li dóna la capacitat de expressar estructuralment. 

On vol posar alguna cosa a la pàgina, la pàgina web? De quin color és el que vols fer això? Quina mida de la lletra és el que vols fer això? Quines paraules et fan realitat vulgui a la pàgina web? Així que això és un llenguatge de marques. Però anem a introduir ràpidament JavaScript, que és un fet i dret completa llenguatge de programació. Molt similar en aparença sintàcticament a C, però tindrà algun agradable, més potent, més característiques d'ús fàcil. 

I una de les frustracions en aquest punt en el semestre és que anem a aviat aplicar corrector ortogràfic en un nombre molt menor línies de codi que utilitzen altres idiomes que la mateixa C permet, però per raons de aviat anem a entendre. Aquesta serà la primera tals pàgina web. Serà completament decebedor, el primer que fem. És simplement dir hola món. Però si mai ho has vist abans, aquest és HTML, Llenguatge de marcat d'hipertext. 

Si vostè va a una opció de menú determinat en més qualsevol navegador, en qualsevol pàgina web en l'Internet, vostè pot veure el codi HTML que algunes persones van escriure a crear aquesta pàgina web. I probablement no es veu tan breu o tan net com aquest. Però va seguir el patró d'aquests suports oberts i talls i les lletres i els números potencialment. 

Vaig pensar que et donaria un teaser del que serà capaç de fer després de prendre CS50. Déjame anar a cs.harvard.edu / rob, pàgina d'inici del nostre propi Rob Bowden. Ell va fer això per nosaltres. Així que aviat serà capaç de fer això. I també, què has sentit aquest matí - el que has sentit aquest matí - 

[Hàmster DANSA MÚSICA] 

- Vostè serà capaç de fer això. Que ens espera dimecres. Ens veiem llavors. 

[Hàmster DANSA MÚSICA] DAVID Malan: En la següent CS50 -