DAVID J. MALAN: Selvä. Joten tervetuloa ensimmäinen CS50 jälkipuinti varten tietokilpailu. Ajattelimme vihkiä Tämän perinteen tänä vuonna. Ja tämä on tilaisuus kulkea ratkaisuja tietokilpailuun. Ja me nopeuttaa tai hidastaa perustuu korko näistä täällä. 

Joten olet luultavasti täällä, koska olet kiinnostuneita siitä, miten olisit voinut tai olisi pitänyt vastata joidenkin näistä ongelmista. Joten miksi emme katsomaan tässä osassa ensin? Niin saa jouset. Tämä antoi sinulle kolme eri versiota ohjelma, joka oli lopulta tarkoitus saada merkkijono käyttäjä. Onko se teki sitä oli vasemmalle voit päättää. 

Ja pyysimme kysymyksessä 0, Oletetaan, että versio 1 on käännetty ja teloitettiin. Miksi voisi ohjelman Segfault? Ensi silmäyksellä, mitään ehdotuksia miksi? Joo. 

Yleisö: Niin Muistan nähneeni tämän Edellisen esimerkin tarkastella char * s ja nähdä skannaus s ja nähdä, koska se on osoitin, miten ei se vaikuta siihen, mitä skannataan? Onko se s tai osoitteen s? 

DAVID J. MALAN: OK. Hyvä. Joten lopulta, lähde mitään ongelmaa on oletettavasti menossa vähentää kyseiseen muuttuja s. Ja se on todellakin muuttuja. Tietotyyppi, että muuttuja on char *, mikä tarkoittaa, että se tulee sisältää osoitteen luonne. Ja siinä piilee oivallus. Se tulee sisältämään osoite merkin tai yleisemmin osoitteen ensimmäisen merkin koko lohko merkkiä. 

Mutta saalis on, että scan s, tarkoitukseen elämä, annetaan osoite ja annetaan muotoilukoodi, kuten% s, lue string kimpale muisti kyseisessä osoitteessa. Mutta koska ei ole mitään yhtäläisyysmerkkiä ennen että puolipiste ensimmäisenä koodiriviä, koska emme oikeastaan ohjattava kaikki muisti malloc, koska se ei oikeastaan jakaa joukko joitakin koko, jotka kaikki teet lukee käyttäjän näppäimistöä johonkin täydellinen roskat arvo, joka on s oletuksena. Joten kertoimet ovat aiot Segfault jos että osoite ei vain niin tapahdu olla arvo, jonka voit, itse asiassa kirjoittaa. Niin paha olla jakamatta muistiasi siellä. 

Joten kysymyksessä 1, pyysimme, Oletetaan, että versio 2 on käännetty ja teloitettiin. Mistä tämä voisi ohjelman Segfault? Joten tämä on vähemmän buginen. Ja siellä oikeastaan ​​vain yksi ilmeinen tapa, jossa voit laukaista segfault täällä. Ja tämä on temaattinen. Aina käytämme c muistiin, mitä voisit tehdä aiheuttaa segfault 2. version? 

Yleisö: Jos käytät että panostus merkkijono, joka on pidempi kuin 49 merkkiä. 

DAVID J. MALAN: Aivan. Aina kun näet jotain kiinteä pituus kun se tulee array, sinun tutka pitäisi mennä pois, että tämä voisi olla ongelmallista, jos et ole tarkkailun rajat array. Ja se on ongelma. Olemme edelleen käytössä scanf. Olemme edelleen käytössä% s, mikä tarkoittaa, kokeile lukea merkkijonon käyttäjä. Se menee luettavaksi osaksi s, joka tässä vaiheessa, on tehokkaasti osoite kimpale muisti tai sen vastaavan. Se on nimi array merkkien muistia. 

Mutta juuri näin, jos olet lukenut merkkijono joka on pidempi kuin 49 merkkiä, 49 koska tarvitset tilaa kenoviiva 0, olet menossa ylivuoto että puskuri. Ja saatat saada onnekas ja pystyä kirjoittaa 51st hahmo, 52., 53.. Mutta jossain vaiheessa, OS aikoo sanoa mitään. Tämä varmasti ei ole muistia olet saanut koskea. Ja ohjelma on menossa Segfault. 

Joten ei, heuristiikka pitäisi olla kun olet saanut kiinteää pituutta, sinulla on varmista, että olet tarkkailun pituus mitä se on, jota yrität lukea sitä. 

Yleisö: Niin ratkaista, että voisit on ollut selvitys tarkkailun todella on pituus suurempi tai pienempi kuin? 

DAVID J. MALAN: Ehdottomasti. Sinulla on vain kunnossa joka sanoo, jos - tai pikemminkin et välttämättä tiedä etukäteen, kuinka monta merkkiä käyttäjä on menossa kirjoittaa, koska sinulla on kana ja muna. Vasta olet lukenut sen kanssa scanf voit selvittää, miten kauan se on. Mutta siinä vaiheessa, se on liian myöhäistä, koska olet jo lukenut sen jonkin lohkon muistia. Niin syrjään, CS50 kirjasto välttelee tämän ongelman kokonaan, Recall käyttämällä fgetc. Ja se lukee yhden merkin kerrallaan, tip-toeing pitkin, tietäen, että olet ei voi ylivuoto merkki, jos luet yksi kerrallaan. 

Saalis on kanssa getString Recall on että meidän on jatkuvasti uudelleen koko että kimpale muistia, joka on vain kipua. Se on paljon riviä koodin tehdä. Joten toinen vaihtoehto olisi todella käyttää serkku, joten sanotusti scanf. On olemassa muunnelmia paljon näitä toimintoja, jotka itse tarkistaa pituus, kuinka monta merkkiä saatat lukea maksimaalisesti. Ja voit määrittää, älä lue yli 50 merkkiä. Jotta olisi toinen lähestymistapa, mutta vähemmän otollinen suurempia panoksia. 

Joten kysymys 2 kysyy, olettaa, että versio 3 on käännetty ja teloitettiin. Miksi se mahtaa ohjelma Segfault? Joten tämä on itse asiassa sama vastata, vaikka se näyttää hieman harrastaja. Käytämme malloc, joka tuntuu annamme itsellemme enemmän vaihtoehtoja. Ja sitten me vapauttaa että muisti lopussa. Se on edelleen vain 50 tavua muistia. Joten saatamme silti yrittää lukea 51, 52, 1000 tavua. Se tulee Segfault varten täsmälleen samasta syystä. 

Mutta on toinenkin syy liian. Mitä muuta voisi malloc paluun lisäksi osoitteen kimpale muisti? Se voisi palata null. Ja koska emme tarkistamalla että voisimme tehdä jotain tyhmä muusta syystä, joka on se, että saatamme olla kertomatta scanf, lue käyttäjän näppäinsyötteisin osaksi 0 sijainti, AKA null. Ja sekin varmasti laukaista segfault. Joten tietokilpailu tarkoitus, olisimme ovat hyväksyneet kumpaakaan näistä kuin pätevää syytä. Yksi on sama. Yksi on hieman vivahteikas. 

Lopuksi suhteessa ohjelman muistin käyttö, miten versio 2 ja versio 3 eroavat toisistaan? Joten mitä se kannattaa, näimme loputtomalta tarjonta mahdollista vastauksia tähän. Ja joukossa ihmisten vastauksia, mitä olimme toivoen, mutta me hyväksyimme muut asioita, oli noin maininta Se, että versio 2 käyttää ns pino. Versio 3 käyttää kasaan. Ja toiminnallisesti, tämä ei oikeastaan tehdä kaikki, että paljon eroa. Lopussa päivän, olemme yhä juuri 50 tavua muistia. 

Mutta se oli yksi mahdollisista vastauksista että me tarkastelemme. Mutta näet, kun saat tietokilpailuja takaisin TF: ille, että teimme hyväksyä muita keskusteluja niiden erilaisia ​​käyttötapoja muistia samoin. Mutta pino ja keko olisi ollut helppo vastaus mennä. Kaikki kysymykset? Annan sinulle Rob. 

ROB BOWDEN: Eli ongelma 4. Tämä on yksi, jossa piti täyttää on tavujen pois kaikki nämä erilaiset käyttää. Joten ensimmäinen asia näemme. Oletetaan 32-bittinen arkkitehtuuri, näin CS50 laitetta. Joten yksi perustavista asioita 32-bittisessä arkkitehtuurissa, joka kertoo meille, kuinka suuri osoitin on menossa olevan arkkitehtuurin. 

Joten heti, me tiedämme, että osoitin tyyppi on 32-bittiä tai 4 tavua. Niin etsivät tässä pöydässä, solmu * on osoitin tyyppiä. Se tulee olemaan 4 tavua. Struct solmu *, joka on kirjaimellisesti identtinen solmuun tähden. Ja niin, että tulee olemaan 4 tavua. String, joten se ei näytä osoitin vielä, mutta typedef, merkkijono on vain char *, joka on osoitin tyyppiä. Niin, että tulee olemaan 4 tavua. 

Joten nämä kolme ovat kaikki 4 tavua. Nyt, solmu ja opiskelija ovat hieman monimutkaisempi. Joten etsit solmu ja opiskelija, näemme solmu kokonaisluku ja osoitin. Ja opiskelija on kaksi osoitinta sen sisälle. Joten ainakin meidän tapauksessa täällä, tapa että päädymme koon laskemista tämä struct on vain täsmää kaiken se sisällä struct. 

Joten solmulle, meillä on kokonaisluku, , joka on 4 tavua. Meillä on osoitin, joka on 4 tavua. Ja niin yksi solmu on menossa ryhtyä 8 tavua. Ja vastaavasti opiskelija, meillä on osoitin, joka on 4 tavua ja toinen osoitin, joka on 4 tavua. Niin että menee loppuun asti on 8 tavua. Niin solmu ja opiskelija ovat 8 tavua. Ja nämä kolme ovat kaikki 4 tavua. Kysymyksiä siitä? Kyllä. 

Yleisö: Onko se oli 64-bittinen arkkitehtuuri, jospa kaksinkertaistaa ne kaikki? 

ROB BOWDEN: Se ei olisi kaksinkertaistaa ne kaikki. Joten 64-bittinen arkkitehtuuri, se taas muutoksia, että perusoikeuksia asia, että Osoitin on nyt 64 bittiä. Joo. Joten osoitin on 8 tavua. Joten nämä, jotka olivat 4 tavua tulevat olemaan 8 tavua. Opiskelija, joka oli kaksi osoitinta, No, nyt se tulee olla 8 tavua, 8 tavua. Se tulee tehdä 16 tavua. 

Mutta solmu on edelleen 4 tavua. Joten tämä osoitin on menossa olla 8 tavua. Tämä on 4 tavua. Niin solmu on vain menee olla 12 tavua. Muita kysymyksiä, että yksi? Joten seuraava, nämä ovat HTTP-tilakoodien. Ja sinun pitäisi kuvailla olosuhteita joiden mukaisesti nämä voimin palautetaan sinulle. yksi ongelma, että kuulin jotkut opiskelijat on se, että he yrittivät tehdä virheitä olla asiakkaan loppuun. Joten kun yritämme tehdä pyynnön palvelimeen, jokin menee väärin meidän loppua. Mutta yleensä nämä koodit ovat palautetaan palvelimen. Joten haluamme selvittää, mitä tapahtuu oikeassa tai väärässä palvelimeen, aiheuttaa nämä asiat palautetaan. Joten miksi pitää palvelin palauttaa tilakoodi 200? Mitään ajatuksia? 

Joo. Joten jotain onnistuneesti pyyntö meni läpi. Ja he voivat palata mitä pyysit. Joten kaikki oli kunnossa. Entä 302 löytyi? Joo. 

Yleisö: palvelin oli etsimässä mitä pyysit. Mutta se ei löytänyt sitä. Joten ei ole virhe. 

ROB BOWDEN: Eli palvelin oli etsivät mitä halusi. Joten katson tässä, 302 löytyy, se oli löytänyt sitä. 

Yleisö: Olen pahoillani. Löytyi tarkoittaa, että he löysivät sen. Anteeksi. 

ROB BOWDEN: So 302 löytynyt. Palvelin pystyy löytämään mitä halusit. 

Yleisö: Mutta se ei ole se näytetään? 

ROB BOWDEN: ero Tämän 302 ja 200 on se, että tietää, mitä haluat. Mutta se ei ole tarkalleen missä halusit kysyä. Joten 302 on tyypillinen uudelleenohjaus. Joten pyysit sivun. Se tietää, oh, haluan palata sinulle tämän. Mutta tämä on eri URL. Joten hei, te todella haluavat tätä. 

DAVID J. MALAN: Se on pala, joka sanoi että annoimme teille uudelleenohjaus toiminto, joka käyttää header-toiminto että puolestaan ​​tulostaa sijainti, paksusuoli, ja sitten URL-osoitteen, joka haluat hylätä käyttäjälle. Vaikka et näe 302 nimenomaisesti siellä, sitähän PHP piti taianomaisesti aseta otsikkomääränpääosoitteena selvää, mitä Rob sanoi, että - löytyi. Mutta täältä sijaan. 

ROB BOWDEN: OK. Entä 403 kiellettyä? 

Yleisö: Minusta se on, että palvelin on pohjimmiltaan sanomalla, että asiakkaan ei voi käyttää etusivulle. 

ROB BOWDEN: Joten kyllä. No, tyypillinen vastaus olimme Odotetaan on jotain, tiedostot ei chmodded asianmukaisesti. Se on luultavasti missä olosuhteissa näit ne. Mutta on syy, että asiakas voisi olla syyllinen täällä. Siellä on todella toinen tila koodi - 401. Joten nämä ovat hyvin samankaltaisia. 

401 on luvaton. Ja 403 on kielletty. Ja niin luvattoman sinua yksinomaan saada, jos et ole kirjautunut sisään Mutta kirjautumalla saattaa tarkoittaa että sinulla on oikeus. Mutta jos olet jo kirjautunut sisään ja vieläkään ei ole lupaa, niin voit myös saada kielletty. Joten jos olet kirjautunut sisään ja ei ole lupaa, kielletty myös jotain voit saada. 

DAVID J. MALAN: Ja mekanismi nämä ongelmat ovat yleensä ratkaistaan ​​palvelin on millaisin komento? Chmod, jos se on todellakin käyttöoikeudet antavat tiedoston tai hakemiston. 

ROB BOWDEN: Sitten 404 ei löytynyt. Joo. Joten toisin kuin 302, jos se ei ollut täsmälleen jos kysyt, mutta se tietää, mitä haluat, tämä, se vain on ei ole aavistustakaan, mitä haluat. Ja et ole vaatinut jotain voimassa. 418 Olen teekannu ja sitten 500 internal server. Joten miksi saattaa sait sen? 

Joten Segfault - En oikeastaan ​​tiedä luokittelu standardi tätä. Mutta jos PHP-koodin oli jotain väärässä siinä, teoriassa se voisi itse asiassa Segfault, jolloin tämä 500 internal server error, jotain vikaa palvelimen kokoonpano. Tai siellä syntaksivirheen oman PHP-koodin. Tai jotain pahaa tapahtuu. 

DAVID J. MALAN: Emme katso segfault keskuudessa harvat vastauksia. Ja teknisesti, se voisi tapahtua. Mutta se olisi PHP, ohjelma kirjoittanut muita ihmisiä, oikeastaan segfaulted, joista vain jos ne ihmiset mokasi ja kirjoitti buginen koodi niiden tulkki olisi PHP itse Segfault. Joten vaikka 500 on kuin segfault hengessä, se on lähes aina tulos asetustiedosto kysymys Web-palvelimen tai, kuten Rob sanoi, syntaksivirhe, kuten sinäkin ei sulje lainaus. Tai olet menettänyt puolipiste jonnekin. 

Yleisö: Joten Shuttle PSET, I ajattelevat, kun tein sen kerran klikkasin selain, mutta mitään ei tullut ylös, mitä he kutsuivat valkoinen sivu. Mutta se johtui koodin. Mielestäni oli JavaScript, eikö? 

ROB BOWDEN: Joo. 

Yleisö: Jospa virhe vielä keksiä? 

ROB BOWDEN: Joten sinulla ei olisi saanut tämän virheen, koska kaikki web-palvelimen näkökulmasta oli täysin kunnossa. Mutta pyysit index.html. Pyysit shuttle.js ja service.js. Ja se kykeni palaamaan teille kaikki nuo asiat - 200. OK. Vasta kun selaimen yritti tulkitsevat JavaScript-koodia, joka Se on kuin, odota, tämä ei ole voimassa JavaScript virhe. Muuta kysyttävää? Selvä. 

DAVID J. MALAN: Joten seuraavan up oli numero 11. Ja 11 oli pelottavin ja paljon ihmisiä. Joten tärkein asia huomata tässä oli, että tämä oli todellakin noin kaksinkertaisesti linkitetty lista. Mutta tämä ei ollut sama kuin viime vuonna kaksin verroin linkitetty lista ongelma, joka ei anna sinulle varoitus, että Listaa voisi itse asiassa olla lajittelemattoman. 

Niin, että luettelo on lajittelematonta ja se, että kyseinen sana oli alleviivattu siellä on tarkoitus välittää että tämä on todella yksinkertaistaminen mitä muuten olisi ollut enemmän haastava ongelma ja pidempi. Niin yleinen virhe täällä oli ryhtyneen viime vuoden ratkaisu ONE hakulaite ja sitten vain sokeasti kopioida, että alas kuin vastaus, mikä on oikea vastaus eri kysymykseen hengeltään samanlainen. Mutta vivahteet täällä olivat seuraavat. 

Joten, olemme solmun ilmoitettu ja määritellään tavalliseen tapaan tässä. Sitten määritellään luettelo olla maailmanlaajuinen osoitin alustetaan nollaksi. Niin ilmeisesti siellä on kaksi tehtävää meillä on prototyyppejä täällä, insert ja poista. Ja sitten meillä on joitakin näyte koodi tähän tehdä joukko lisäyksiä. Ja sitten pyydämme sinua täyttämään täytäntöönpanoa insert alla tällaisissa siten, että se lisää n listaan jatkuvassa aikaan myös korosti, vaikka jo läsnä. 

Joten kauneus pysty lisäämään jatkuvassa aika on, että se merkitsee että sinun täytyy lisätä uusi solmu missä? Etuosaan. Niin se poistaa, onneksi, ainakin yksi niistä tapauksista, joihin ennen tarvittiin vieläkin riviä koodia, kuten se teki viime vuonna ja jopa luokassa, kun me puhui läpi tällainen asia ihmisiin ja joidenkin sanallinen pseudo koodia. Joten ratkaisu täällä, hypätään yli tähän vain on näköyhteys näytön. 

Huomaa, että teemme seuraavan. Ja myös huomata muuta yksinkertaistamista oli se, että vaikka se on jo läsnä, joten tämä tarkoittaa, vaikka numero on jo olemassa, voit vain sokeasti lisää toinen kopio. Ja sekin oli tarkoitus olla yksinkertaistamista, jotta voisitte keskittyä, todella, jotkut enemmän älyllisesti mielenkiintoinen osa ja ei vain joitakin ylimääräisiä virheentarkistusmenetelmiä annetaan rajoitetun ajan. 

Joten tässä näyteliuoksessa, myönnämme osoitin vasen sivulle tästä solmuun. Nyt ymmärtää, että osoitin, koska Rob sanoi, on vain 32 bittiä. Ja se ei varsinaisesti sisällä osoitetta, kunnes määrittää sen osoite. Ja teemme sen oikealla kädellä puoli kautta malloc. Kuten hyvä kansalainen, tarkistamme, että malloc ei ole itse asiassa nolla, niin että emme vahingossa luo segfault täällä. Ja milloin käytät malloc elämässä, sinun pitäisi olla tarkistamatta null, ettei sinulla on hienovarainen bugi. 

Sitten alustaa että null by määrittämällä n ja edellinen ja seuraava. Ja tässä tapauksessa täällä, olen alustettu ennen null, koska tämä uusi solmu tulee olemaan uuden alussa listallani. Joten siellä tulee olemaan mitään ennen sitä. Ja haluan olennaisesti liittää luodun luettelon uuteen solmuun asettamalla vieressä yhtä luetteloa. Mutta en ole tehnyt vielä. Joten jos luettelo itse jo olemassa, ja siellä oli ainakin yhden solmun jo olemassa, jos tämä on luettelo täällä ja asetan uuden solmun täällä, en täytyy varmistaa, että minun entinen solmu huomauttaa taaksepäin minun uusi solmu, koska tämä on jälleen kaksinkertaisesti linkitetty lista. 

Joten emme järki tarkistaa. Jos lista ei ole nolla, jos on jo yhden tai useamman solmun siellä, niin lisätä, että sivuväli niin sanotusti. Ja sitten aivan viimeinen asia, jota tarvitsemme vain todella päivittää maailmanlaajuisen muuttujalista itse osoittamaan sen, että uusi solmu. Joo. 

Yleisö: Kun osoitin nuoli [Äänetön] on yhtä suuri kuin nolla, tekee sen käsitellä luettelosta, koska lista on nolla? 

DAVID J. MALAN: Ehei. Se on yksinkertaisesti minulle on ennakoivasti Varo, että jos tämä on minun alkuperäinen lista ehkä hieman enemmän solmuja tänne ja olen lisäämällä minun uusi solmu tänne, siellä tulee olevan mitään tänne. Ja haluan kaapata ajatus asettamalla ennen null uusi solmu. Ja oletettavasti, jos koodi on oikea ja ei ole muuta keinoa lisätä solmut muuta kuin tätä toimintoa, oletettavasti, vaikka lista on jo yhden tai useamman solmun se, oletettavasti lista, ensimmäinen solmu, olisi edellinen osoitin null itse. 

Yleisö: Ja juuri seurannan. Syynä laitat osoittimen vieressä tasavertaisina Lista on teet osoitin ennen alalta, että se on suunnattu seuraavaan, luulisin - I älkää - vain luetellaan? 

DAVID J. MALAN: Aivan. Ja niin katsotaanpa todella tarkastelemme tilannetta, täällä todella, vaikka Jotta me pitävät heitä ei ole aivan sama kuin koodi. Mutta korkealla tasolla, jos se on luetella ja tämä on 32-bittinen osoitin, yksinkertaisin tilanteessa on että tämä on null oletuksena. Ja kai haluan lisätä numero 50 oli ensimmäinen numero. Joten aion mennä eteenpäin ja jakaa solmu, joka tulee sisältämään kolme kenttää - n, edellinen ja seuraava. 

Aion laittaa numero 50 täällä, koska tämä on n. Tämä on ensi. Ja tämä on edellinen. Ja niin mitä voin tehdä tässä tapauksessa? No, olen juuri tehnyt linja 1 täällä. Pointer n saa n. En sitten sanomalla, edellinen pitäisi saada null. Joten tämä tulee olemaan nolla. Sitten aion sanoa seuraavaksi on menossa luetteloon. 

Ja tämä vain toimii hyvin. Tämä on null. Ja niin minä sanon, uusi solmu seuraava kentän pitäisi saada mitä tämä on. Niin, että tuo toinen null siellä. Ja sitten viimeinen asia En on tarkistaa täältä. Jos luettelo ei ole yhtä suuri kuin nolla, mutta se on yhtä kuin nolla, joten jätä että kokonaan. Ja niin kaikki mitä teen seuraavaksi on lista saa osoitin, joka kuvallisesti johtaa kuva niin. Joten se on yksi skenaario. 

Ja joka olit kysyä Erityisesti on tämänkaltaisessa tilanteessa, jossa meillä on jo yksi-yhtymäkohtalistassaan. Ja vaikka minä menen takaisin ylös alkuperäisessä ongelmalausekkeen Seuraavaksi voisi aseta sanoa on 34, vain vuoksi keskustelua. Joten aion vain kätevästi piirtää että tänne. Olen juuri malloced. Oletetaan Olen tarkistanut null. 

Nyt aion alustaa n olevan 34. Ja tämä on n. Tämä on ensi. Ja tämä on edellinen. Varmistetaan että en saat tämän taaksepäin. Edellinen tulee ensin määritelmään. Haluan korjata tämän. Tämä on vanha. Tämä on seuraava. Vaikka ne ovat identtisiä, Pidetään se johdonmukainen. 

Edellinen. Tämä on seuraava. Joten olen juuri malloced viestini, tarkastetaan for null, annettu 34 osaksi solmu. Edellinen saa null. Niin että antaa minulle. Seuraava saa luettelon. Joten lista on tämä. Joten tämä on nyt sama kuin piirustus tämä nuoli, niin että ne viittaavat yhteen samalla. Ja sitten olen tarkistaa, jos lista ei ole yhtä kuin nolla. Ja se ei ole tällä kertaa. Sitten aion tehdä luettelo Edellisen saa osoitin. 

Joten listaan ​​edellinen saa PTR. Joten tämä vaikutus on laskemisesta graafinen nuoli täällä. Ja se on tulossa hieman aaltoileva, linjat. Ja sitten lopuksi päivitän luetella osoittamaan osoitin. Joten nyt tämä viittaa tämä kaveri. Ja nyt, nyt tehdä nopeasti järki tarkistaa. 

Tässä lista, joka on globaali muuttuja. Ensimmäinen solmu on, todellakin, 34, koska Olen jälkeen, että nuoli. Ja se on oikein, koska haluan lisätä alussa luettelon kaikki uudet solmut. Hänen seuraava kenttä pääsenkin tämä kaveri. Jos pidän menossa, osuin seuraavaksi on null. Joten ei ole enää olemassa lista. Jos osuin edellinen, saan takaisin jos odotan. 

Joten on vielä muutaman vinkin, tietenkin, manipuloida. Mutta se, että lääkäri on määrännyt tehdä Tämän jatkuvasti, sitä vain on rajallinen määrä asioita et saa tehdä. Ja mikä on sen numero? Se voisi olla yksi askel. Se voi olla kaksi. Se voi olla 1000 askelta. Mutta se on rajallinen, mikä tarkoittaa, et voi ovat minkäänlaista silmukoiminen tekeillä täällä, ei rekursio, ole silmukoita. Se on vain pakko olla kovakoodatuilla linjat koodin kuten olemme tässä näytteessä. 

Niin seuraava ongelma 12 pyytäneet meitä täydellinen täytäntöönpano remove alle siten, että se poistaa n luettelosta lineaarisessa ajassa. Joten sinulla on hieman enemmän liikkumavaraa nyt. Voit olettaa, että n, jos käytössä luettelossa, on läsnä enintään kerran. Ja sekin on tarkoitus olla tietokilpailu-pohjainen yksinkertaistava oletus, joten että jos löydät numeron 50 jonnekin luettelossa, et myös tarvitse huolehtia edelleen kerrata, etsivät kaikki mahdolliset jäljennös 50, joka olisi vain siirtää johonkin erikoiskohtaa rajoitetun ajan. 

Joten poistaa, tämä oli ehdottomasti haastavampaa ja enemmän koodia kirjoittaa. Mutta ensi silmäyksellä, suoraan sanottuna, se saattaa haitata näyttää ylivoimainen ja jotain ei mitenkään sinulla voisi olla keksiä tietovisa. Mutta jos keskitymme yksittäisiä vaiheita, Toivottavasti se yhtäkkiä iskeä sinua että kukin näistä vaiheet tekee selvää järkeä jälkikäteen. Joten katsotaanpa katsomaan. 

Joten ensin, me alustaa osoitin olevan luetteloa. Koska haluan lineaarisen ajan, että välineet Aion olla silmukka. Ja yleinen tapa kerrata yli solmut Hakemistorakenteessa tai minkäänlaista Rakenteen iteratiivisesti on ottaa osoittimen edessä datan rakennetta ja sitten vain alkaa päivittää se ja kävellä tiesi kautta tietorakenne. Joten aion tehdä juuri näin. 

Vaikka osoitin, väliaikaiset muuttuja, ei ole sama kuin nolla, katsotaanpa mennä eteenpäin ja tarkistaa. Sainko onnekas? Onko n kentän solmuun olen tällä hetkellä tarkastellaan yhtä numero Etsin? Ja jos on, tehdään jotain. Nyt, huomaa tämä, jos ehto ympäröi koko Seuraavat riviä koodia. Tämä on ainoa asia välitän - löytää numero kyseessä. Joten ei ole mitään muuta, mikä yksinkertaistaa asioita käsitteellisesti hieman. 

Mutta nyt tajusin, ja saatat olla vain tajusi tämän jälkeen ajattelu sitä kautta vähän, siellä on oikeastaan ​​täällä kaksi asiaa. Yksi on, jos solmu on alussa lista, joka on vähän harmittaa, koska se on erikoistapaus, koska sinun täytyy käsitellä tämä asia, joka on ainoa poikkeus. Kaikkialla muualla luettelossa se on sama asia. Siellä edellisen solmun ja ensi solmu, edellisen solmun, seuraavaan solmuun. Mutta tämä kaveri on hieman erikoinen jos hän alussa. 

Joten jos osoitin vastaa luettelon itse, joten jos olen alussa luettelo ja olen löytänyt n, tarvitsen tehdä pari asiaa. Yksi, minun täytyy muuttaa luetteloa viittaavat seuraavaan kenttään 50. Joten olettaa, että olen yrittänyt poistaa 34. Joten tämä kaveri sai mennä pois vain hetken. 

Joten aion sanoa, lista saa osoitin seuraavaksi. No, tämä on osoitin. Seuraava osoittaa tänne. Joten tämä on muuttumassa tätä nuolta oikealle nyt osoittamaan tämä kaveri täällä. Muista nyt, meillä on väliaikainen muuttuja. Joten emme ole orpoja mitään solmuja, koska minulla on myös tämä kaveri minun täytäntöönpanon poistaa. Joten nyt, jos lista itsessään ei ole nolla, Minun täytyy korjata jotain. 

Minun täytyy nyt varmistaa, että tämä nuoli, joka on aikaisemmin osoittaa 50-34, tämä on saanut mennä pois, koska jos yritän päästä eroon 34, 50 oli parempi saa pitää eräänlainen takaisin viittaamalla sen nuoli ehdotti. Joten tein tätä linjaa. Niin sitten olen valmis. Tällöin on oikeastaan ​​aika helppoa. Paloittelu pään pois listalta on suhteellisen yksinkertaista. 

Valitettavasti tämä harmittaa muu lohko. Joten nyt minun on harkittava tapaus missä on jotain keskellä. Mutta se ei ole liian kauhea, paitsi syntaksille näin. Joten jos en ole alussa lista, olen jossain keskellä. Ja tämä linja täällä sanoo, alku minä tahansa solmussa olet. Siirry edelliseen solmun seuraavaan kenttään ja osoittele osoitin. 

Tehdään tämä kuvallisesti. Että oli tulossa monimutkainen. Joten jos minulla on edellisen Pellot - tehdään tämä - ensi aloilla täällä. Aion yksinkertaistaa minun viitteitä pikemminkin kuin vetää koko joukko asioita edestakaisin crisscrossing toisiaan. Ja nyt, haluan vain sanoa, tämä on 1, 2, 3 vuoksi keskustelua, jopa kuitenkin, että ei asetu kyseinen ongelma. 

Joten tässä on minun linkitetty lista. Yritän poistaa kaksi tässä Erityisesti versio tarinasta. Joten olen päivittänyt osoitin osoittavan tämä kaveri. Joten tämä on PTR. Hän osoittaa täällä. Tämä on lista, joka on olemassa maailmanlaajuisesti kuin ennen. Hän osoittaa täällä vaikka mitä. Ja nyt yritän poistaa kaksi. 

Joten jos osoitin osoittaa täällä, olen menossa seuraamaan, ilmeisesti, edellinen osoitin, joka asettaa minut 1. Olen niin menee sanoa, että seuraava kenttä, joka tuo minua tähän laatikko täällä on menossa yhtä osoittimen vieressä. Joten jos tämä osoitin, tämä on seuraava. Tämä tarkoittaa, että tätä nuolta tarpeisiin osoittamaan tämä kaveri. 

Niin mitä Koodirivin on juuri tehtävä on hieman tätä. Ja nyt, tämä on näköisenä askel oikeaan suuntaan. Olemme pääasiassa haluavat leikata 2 ulos ja keskellä 1 ja 3. Joten on järkevää, että haluamme Reitin tämä osoitin sen ympärille. Joten tämä seuraava rivi on tarkistaa, jos osoitin seuraava ei ole nolla, siellä todellakin joku oikealle 2, se tarkoittaa, että meidän on myös tehtävä pieni snip täällä. 

Joten minun täytyy nyt seurata tätä osoitinta ja päivittää edellisen osoittimen tämä kaveri tekemään hieman Voit kiertää täällä kohta täällä. Ja nyt, visuaalisesti tämä on mukavaa. Se on vähän sotkuinen, että siellä on kukaan suunnattu 2 enää. 2 on osoittaa vasemmalle. Ja 2 on osoittaa oikealle. Mutta hän voi tehdä mitä hän haluaa, koska hän on saamassa vapautti. Ja se ei ole väliä, mitä nämä arvot ovat enää. 

Tärkeää on, että jäljellä kaverit reititys edellä ja hänen alapuolellaan nyt. Ja todellakin, sitähän me teemme seuraavaksi. Me vapaa osoitin, mikä tarkoittaa kerromme käyttöjärjestelmä, olet tervetullut perimään tätä. Ja sitten lopuksi palaamme. Else implisiittisesti, jos me eivät ole palautuneet vielä, meidän täytyy jatkaa etsimistä. Joten osoitin vastaa osoittimen vieressä vain tarkoittaa siirtää tämä kaveri täällä. Siirrä tämä kaveri täällä. Siirrä tämä kaveri täällä, jos asiassa emme löytäneet numero etsimme vielä. 

Joten rehellisesti, se näyttää täysin ylivoimainen, mielestäni ensin silmäyksellä, varsinkin jos kamppaillut Tämän aikana tietokilpailu sitten nähdä jotain tällaista. Ja voit taputtaa itseäsi selkään. No, ei voi enää mitenkään voisin olla keksiä, että tietokilpailu. Väittäisin kuitenkin, voit jos rikot se alas näihin yksittäisiin tapauksissa ja vain kävellä läpi huolellisesti, vaikkakin tosin alle stressaavaa olosuhteissa. 

Onneksi kuva tehty kaiken onnellisempi. Voisit piirtää tämän kuinka monella tavalla tahansa. Sinun ei tarvitse tehdä crisscrossing juttu täällä. Voisit tehdä sen suoraan linjat kuten tämä. Mutta ydin tämän ongelman Yleensä oli ymmärtää, että kuva lopulta näyttää hieman jotain tällaista, koska vakioaikaisia ​​ymmärtää, että pidät jammailua ja häirintä ja häirintä uudet solmut alussa luettelon. Kaikki kysymykset? Luultavasti kaikkein haastavin varmasti koodaus kysymyksiä. 

Yleisö: Niin on lista samanlainen pää edellisissä esimerkeissä. 

DAVID J. MALAN: Aivan, aivan. Vain toinen nimi globaali muuttuja. Maailmanlaajuinen mitä? 

ROB BOWDEN: OK. Joten tämä on yksi, jossa voit piti kirjoittaa kohtaan. Jotkut ihmiset kirjoittivat esseitä tähän kysymykseen. Mutta sinun tarvitsee vain käyttää nämä kuusi termejä kuvaamaan, mitä tapahtuu, kun yrität ottaa yhteyttä facebook.com. Joten minä vain puhua läpi prosessin käyttäen kaikkia näitä ehtoja. Joten meidän selain, kirjoitamme facebook.com ja paina Enter. Joten meidän selain tulee rakentaa HTTP-pyynnön, että se tulee lähettää läpi joitakin prosessin Facebookiin Facebook vastata meille HTML sen sivun. 

Joten mikä on prosessi, joka HTTP-pyynnön todella saa Facebookiin? Ensin meidän täytyy kääntää Facebook.com. Joten juuri antanut nimen Facebook.com, jos todella tekee HTTP-pyynnön täytyy mennä? Joten meidän täytyy kääntää Facebook.com IP-osoite, joka yksiselitteisesti määritellään, mitä kone me oikeastaan haluat lähettää tämän pyynnön. Kannettava tietokone on IP-osoite. Mitään yhteydessä internetiin on IP-osoite. 

Joten DNS, Domain Name System, joka on mitä tulee käsitellä käännös alkaen facebook.com IP-osoitteen, joka te todella haluavat ottaa yhteyttä. Joten otamme yhteyttä DNS-palvelimet ja sanoa, mikä on facebook.com? Siinä sanotaan, oh, se on IP-osoite 190,212 jotain, jotain, jotain. Selvä. Nyt tiedän mitä kone Haluan yhteyden. 

Niin sitten lähetät HTTP-pyynnön yli automaatista. Joten miten se päästä, että kone? No, pyyntö menee reitittimen mukaan terhakka. Muista Esimerkiksi luokassa, jossa me itse nähnyt reitti, joka paketit otti kun yritimme kommunikoida. Näimme sen hypätä yli Atlantin Ocean jossain vaiheessa tai mitä tahansa. 

Joten viimeinen termi satamaan. Joten tämä on nyt tietokoneellesi. Sinulla voi olla useita asioita tällä hetkellä kommunikoida Internetissä. Joten en voi olla käynnissä, vaikkapa Skype. Saatan olla web-selain auki. Minulla saattaa olla jotain, torrenting tiedostoja. Joten kaikki nämä asiat ovat kommunikoida Internet jollakin tavalla. 

Joten kun tietokone vastaanottaa joitakin tietoja Internetistä, kuinka se tietää, mitä sovellus todella haluaa tietoa? Miten se tietää, onko tässä nimenomaisessa data on tarkoitettu torrenting sovellus vastakohtana Web-selaimeen? Joten tämä on tarkoitus satamien että Kaikki nämä sovellukset ovat väitti porttiin. Joten selaimessasi sanoo, hei, Olen kuuntelee porttia 1000. Ja torrenting ohjelma sanoo, Olen kuuntelee porttia 3000. Ja Skype sanoo, olen käyttäen portin 4000. 

Joten kun saat joitakin tietoja, joka kuuluu yksi näistä sovelluksista, data on merkitty, mihin satamaan se tosiasiallisesti tulee lähettää pitkin. Joten tämä kertoo, oh, minä kuulun porttiin 1000. Tiedän, silloin minun täytyy välittämään tämän pitkin minun selaimella. Niin syy on merkitystä tässä on, että web-palvelimet ovat yleensä tarkkaile porttia 80. Joten kun otan yhteyttä Facebook.com, olen tiedonsiirrossa joidenkin koneella. Mutta minun täytyy sanoa, mihin satamaan kyseisen kone Haluan kommunikoida. Ja web-palvelimet ovat yleensä kuuntelee porttia 80. 

Jos he halusivat, he voisivat asettaa sen niin se luettelee portissa 7000. Ja sitten web-selain, voisin manuaalisesti tyyppi Facebook.com: 7000 lähetä pyyntö porttiin 7000 Facebookin web-palvelin. 

DAVID J. MALAN: Ja tässä tapauksessa, vaikka Vaikka emme edellytä, että ihmiset Mainitsen tämän, tässä tapauksessa mitä porttia olisi pyynnön itse mennä? Yritä uudelleen. Täsmälleen. Eivät etsi sitä, mutta hienovaraisuutta että siellä mikään viimeinen. 

ROB BOWDEN: Niin HTTPS, koska se on kuuntelee nimenomaan salattu, se on portissa 4430. 

Yleisö: Ja sähköpostit ovat 25, eikö? 

DAVID J. MALAN: Outbound sähköposteja, 25, jep. 

ROB BOWDEN: En edes tiedä useimmat - kaikki alemmat yleensä varattu asioita. Mielestäni kaikki alle 1024 on varattu. 

Yleisö: Miksi sanoit 3 oli väärä numero? 

ROB BOWDEN: Koska IP-osoitteen, siellä on neljä ryhmää numeroita. Ja he ovat 0-255. Joten 192.168.2.1 on yhteinen lähiverkon IP-osoite. Huomaa kaikki nämä ovat alle 255. Joten kun aloitin 300, että ei mitenkään ole voinut ollut yksi numeroita. 

DAVID J. MALAN: Mutta se typerä clip alkaen - oli se CSI, jossa heillä oli numero, joka oli liian suuri IP-osoitteen. 

ROB BOWDEN: Kysyttävää tästä? Seuraava, niin täydellinen muutos topic, mutta meillä on tämä PHP array talot quad. Ja meillä on Järjestämätön lista. Ja haluamme tulostaa kunkin kohdan vain joka sisältää talon nimi. Joten meillä on foreach silmukka. Muista siis, syntaksi on foreach array kohde array. Joten läpi kunkin iterointia silmukan, talo vie yksi arvojen sisällä array. 

On ensimmäistä iterointia, talo tulee Cabot House. On toinen variaatio, talo olla Courier talo ja niin edelleen. Joten jokaisen quad kuin talo, olemme juuri menossa painoon - voit myös voi ovat toistaneet - luettelon kohtaan ja sitten talon nimi ja sulje luettelon kohtaan. Aaltosulkeita ovat valinnaisia ​​täällä. 

Ja sitten me myös sanoi kyseessä itse, muista sulkea Järjestämätön lista tag. Joten meidän täytyy poistua PHP tilassa voidakseen tehdä tämän. Tai voisimme ovat toistaneet Sulje Järjestämätön lista tag. 

DAVID J. MALAN: Myös hieno tässä olisi on ollut käyttää vanhaa koulua silmukka $ i = 0 0 ja käyttämällä laskurien selvittää pituus säde. Täysin kunnossa myös, vain hieman wordier. 

Yleisö: Joten jos olit menossa [Äänetön], tekisitkö - Unohdan mitä silmukka [kuultavissa] on. Voisitko $ quad kiinnike i? 

DAVID J. MALAN: Aivan. Joo, aivan. 

ROB BOWDEN: Jotain muuta? 

DAVID J. MALAN: Selvä. Kompromisseja. Joten oli risuryppäät vastauksia mahdollista, että kukin näistä. Olimme oikeastaan ​​vain etsimässä jotain pakottavia ylösalaisin ja kääntöpuolensa. Ja numero 16 kysyi, validointi käyttäjien input client-side, kuten JavaScript, sijasta server-side, kuten PHP. Joten mitä ylösalaisin tekee client-side? 

No, yksi niistä asioista, ehdotimme on että voit vähentää latenssi, koska olet ei tarvitse vaivautua yhteyttä palvelin, joka saattaa kestää muutaman millisekuntia tai jopa pari sekuntia välttämällä että ja vain validointi käyttäjien panos client-side by liipaisu paikan esittää ohjaajan ja vain tarkistaa, he kirjoita jotain nimelle? Oliko he kirjoittavat jotain in sähköpostiosoitetta? He valitsivat asuntolan alkaen pudotusvalikosta? 

Voit antaa heille hetkellinen palautetta käyttäen gigahertsin tietokone tai mitä ne ovat, että on itse asiassa niiden vastaanotto. Joten se on vain parempi käyttäjä kokevat tyypillisesti. Mutta haittapuoli tehdä client-side validointi, jos teet sen ilman myös tekee server-side validointi on, että useimmat kukaan tulossa ulos CS50 tietää että voit vain lähettää tietoja haluat palvelimeen monella tavalla tahansa. Suoraan sanottuna, useimmissa tahansa selaimella, voit klikkaa ympäri asetukset ja juuri sammutettava JavaScript, joka siinä tapauksessa, siis poistaa kaikenlainen validointi. 

Mutta voit myös ehkä muistaa, että vaikka en teki joitakin mystistä asioita luokassa käyttäen telnet ja todella teeskentelee olla selaimen lähettämällä get pyyntöjä palvelimelle. Ja se ei todellakaan ole jollakin JavaScript. Se on vain minun kirjoittamalla komentoja klo näppäimistö. Siis todella, mitä tahansa ohjelmoija sisällä tarpeeksi mukavuutta web ja HTTP voisi lähettää mitä tietoja hän haluaa palvelimeen ilman vahvistusta. Ja jos palvelin ei myös tarkistaa, he antoivat minulle nimi, on tämä todella toimiva sähköpostiosoite, teki he valitsevat asuntolan, saatat päätyä ylös työntämällä vääriä tai vain tyhjiä tiedot tietokantaan, joka todennäköisesti ei tule olemaan hyvä, jos olit olettaen, että se oli siellä. 

Joten tämä on ärsyttävää todellisuutta. Mutta yleensä, client-side validointi on suuri. Mutta se tarkoittaa kaksi kertaa niin paljon työtä. Vaikka ovat olemassa eri kirjastot, JavaScript kirjastot Esimerkiksi, jotka tekevät tästä paljon, paljon vähemmän päänsärkyä. Ja voit käyttää uudelleen joitakin koodi server-side, client-side. Mutta älä ymmärrä, että se on tyypillisesti lisätyötä. Joo. 

Yleisö: Eli jos me vain sanoi vähemmän turvallinen - 

DAVID J. MALAN: [LAUGHS] Ugh. Ne ovat aina vaikeampaa niitä ratkaista. 

ROB BOWDEN: Se olisi on hyväksytty. 

DAVID J. MALAN: Mitä? 

ROB BOWDEN: Loin tämän ongelman. Että olisi hyväksytty. 

DAVID J. MALAN: Joo. 

Yleisö: Cool. 

ROB BOWDEN: Mutta me emme hyväksy että ensimmäinen - No, mitä etsimme on jotain sinun ei tarvitse palvelimen kanssa. Emme hyväksy vain nopeammin. 

Yleisö: Entä älä enää käytä sivun? 

ROB BOWDEN: Kyllä. Se oli hyväksytty vastaus. 

DAVID J. MALAN: Anything jossa tunsimme se oli todennäköisempää kuin todennäköistä että tietäisit, mitä olit sanomalla, joka on kova line tehdä joskus. Käyttämällä linkitetyn listan sijaan array säilyttää lajiteltu kokonaislukujen lista. Joten ylösalaisin me usein mainitsevat kanssa sidoksissa luettelot, jotka motivoivat heidän koko käyttöönotto oli saat dynaamisuutta. Ne voivat kasvaa. Ne voivat kutistua. Joten sinun ei tarvitse hypätä kautta vanteet itse luoda enemmän muistia kanssa array. Tai sinun ei tarvitse vain sanoa, anteeksi, käyttäjän. Array on täynnä. Joten dynaaminen kasvu luettelosta. Huonona puolena tosin on linkitetty lista? 

Yleisö: Se on lineaarinen. Haetaanko linkitetty lista on lineaarinen sen sijaan mitä kirjaudu sisään 

DAVID J. MALAN: Aivan. Hakuja linkitetty lista on lineaarinen, vaikka se lajitellaan, koska voit vain seuraa näitä korppujauhoja, nämä osoittimet, alusta alkaen luettelon loppuun. Et voi hyödyntää random access ja näin, binäärihaku, vaikka se on lajiteltu, että voisit tehdä array. Ja siellä on myös toinen kustannuksia. Joo. 

Yleisö: Muisti tehotonta? 

DAVID J. MALAN: Joo. No, en olisi välttämättä sanovat tehotonta. Mutta se maksaa enemmän muistia, koska tarvitset 32 ​​bittiä jokaisen solmu ylimääräisiä osoitin kello ainakin yksittäin linkitetty lista. Nyt, jos olet vain tallentaa kokonaislukuja ja lisäät osoitin, joka on oikeastaan ​​eräänlainen ei-triviaali. Se kaksinkertaistaa muistin määrä. Mutta todellisuudessa, jos olet tallentaa linkitetty lista structs, jotka saattavat olla 8 tavua, 16 tavua, vielä kuin, että ehkä se on vähemmän of rajakustannus. Mutta se on kustannus kuitenkin. Joten joko näistä olis ollut hieno kuin haittoja. 

18. PHP sijaan C kirjoittaa komentorivin ohjelma. Joten tässä, se on usein nopeampi käyttää kuten PHP tai Ruby tai Python. Sinä vain nopeasti avata up tekstieditori. Sinulla on paljon enemmän toimintoja käytössäsi. PHP on tiskiallas toimintoja, kun taas C, sinun on hyvin, hyvin vähän. Itse asiassa kaverit tietää kantapään kautta että sinulla ei ole hash taulukoita. Sinulla ei ole linkitettyjä listoja. Jos haluat ne, sinun täytyy toteuttaa ne itse. 

Joten yksi Ylösalaisin PHP tai oikeastaan ​​mitään tulkittu kieli on nopeus jolla voit kirjoittaa koodia. Mutta haittapuoli, näimme tämän, kun nopeasti lyöty jopa Misspeller täytäntöönpano luento PHP, on että käyttämällä tulkittava kieli on yleensä hitaampaa. Ja näimme, että todistettavasti kanssa kasvaa aika 0,3 sekuntia 3 sekuntia, koska tulkinta että todella tapahtuu. 

Toinen ylösalaisin oli, että ei tarvitse kääntää. Niin se myös nopeuttaa kehitystä muuten, koska sinulla ei ole kaksi askelta käynnissä ohjelma. Sinulla on vain yksi. Ja niin se on aika pakottavia samoin. Käyttäen SQL-tietokannan sijasta CSV-tiedoston tallentamiseen. Joten SQL-tietokannan käytetään pset7. CSV-tiedostoja et käyttänyt paljon. Mutta käytit sitä välillisesti pset7 kuin hyvin puhumalla Yahoo Finance. 

Mutta CSV on aivan Excel-tiedoston, mutta Super yksinkertainen, jossa sarakkeet ovat vain demarked pilkuilla sisällä on muuten tekstitiedosto. Ja käyttämällä SQL-tietokanta on hieman enemmän pakottavia. Se on ylösalaisin, koska saat asiat kuten valita ja lisätä ja poistaa. Ja saat oletettavasti indeksien MySQL ja muita tietokantoja, kuten Oraakkeli, rakentaa sinulle muistiin, jossa tarkoittaa valitse ei luultavasti ole olemaan lineaarista ylhäältä alas. Se on oikeastaan ​​olemaan jotain kuten binäärihaku tai jotain hengeltään samanlainen. Joten he ovat yleensä nopeammin. 

Mutta haittapuoli on, että se on vain enemmän työtä. Se on enemmän vaivaa. Sinun täytyy ymmärtää tietokantoihin. Sinun täytyy asettaa se. Tarvitset palvelimen suoritettavaksi että tietokanta. Sinun täytyy ymmärtää miten määrittää se. Joten nämä ovat vain näitä erilaisia ​​kompromisseja. Ottaa huomioon, että CSV-tiedosto, voit luoda sitä gedit. Ja olet hyvä mennä. Ei ole monimutkaisia ​​pidemmälle. 

Käyttämällä triestä sijaan hajautustaulun erillisellä ketjutus tallentaa sanakirja sanoja mieleen of pset5. Joten yrittää ylösalaisin, teoriassa ainakin on mitä? Jatkuva aikaa, ainakin jos olet hajautus on kunkin yksittäisen kirjaimet sana, kuten sinäkin saattaa olla varten pset5. Se voisi olla viisi hash, kuusi hash jos on viisi tai kuusi sanan kirjainten. Ja se on aika hyvä. Ja jos on yläraja, miten pitkä sanasi voisi olla, se on todellakin asymptoottisesti vakioaikaisia. 

Ottaa huomioon, että tiiviste erillisellä ketjuttamalla ongelma siellä, että Tällainen tietorakenne on, että suorituskykyä algoritmien yleensä riippuu monia asioita jo tietorakennetta. Ja se on ehdottomasti tapauksessa ketjut, jolloin enemmän tavaraa laitat osaksi tiiviste, enää niitä ketjut mennä, mikä tarkoittaa pahimmassa tapauksessa asia, saatat olla etsimässä on aina lopussa yhden näistä ketjuista, joka tehokkaasti lankeaa jotain lineaarinen. 

Nyt käytännössä, se voisi aivan olla, että hash-taulukko, jossa on ketjut on nopeampi kuin vastaava trie täytäntöönpanoa. Mutta se on eri syistä, muun jotka yrittää käyttää paljon muistin, joka voi itse asiassa, hidas asioita alas, koska et saa mukavaa hyödyistä jotain kutsutaan välimuistin jos asioita, jotka ovat lähellä toisiaan muistia voidaan käyttää usein nopeammin. Ja joskus voi keksiä todella hyvä hajautusfunktio. Vaikka joudut tuhlaamaan hieman muistia, kyseessä saattaa todellakin pystyä löytää asioita nopeasti eikä niin paha kuin lineaarisesti. 

Joten lyhyt, ei ollut välttämättä mitään näistä yksi tai jopa kaksi tiettyjä asioita etsimme. Oikeastaan ​​mitään vakuuttava kuin positiiviset ja negatiiviset yleensä kiinni meidän silmään. 

ROB BOWDEN: Joten ylösalaisin, teimme ei hyväksy omasta "nopeammin." Sinua piti sanoa jotain. Vaikka sanoit teoreettisesti nopeammin, Tiesimme, että olet sellainen ymmärtänyt että se on 0 1. Ja tiiviste, teoriassa, ei ole 0 1. Viittaavat mitään runtime yleensä sai sinut pistettä. Mutta "nopeammin", useimmat ratkaisut iso board jotka yrittää olivat objektiivisesti hitaampaa ratkaisuja jotka olivat hash taulukoita. Joten nopeammin ja itse ei ole oikeasti totta. 

DAVID J. MALAN: Dom de Dom dom. Olen luultavasti ainoa, joka tajuaa näin, joka on tarkoitus lausutaan, eikö? 

ROB BOWDEN: Minulla oli oikeastaan ​​aavistustakaan. 

DAVID J. MALAN: Se teki järkeä päähäni. 

ROB BOWDEN: Teen tämän yhden. OK. Joten tämä on yksi, jossa piti piirtää kaavio samanlainen saatat nähneet viimeisen tentit. Joten katsokaa tätä. Joten HTML-solmu, meillä on kaksi lapset, pään ja kehon. Joten me haara - pään ja vartalon. Pää on otsikko tag. Joten meillä on otsikko. 

Nyt yksi asia paljon ihmisiä Unohdin on, että nämä teksti solmut ovat elementit tämä puu. Joten tässä satumme tehdä niitä ovaaleina erottamaan niitä näitä tyyppisiä solmuja. Mutta ilmoitus myös täällä meillä on top, keski-ja pohja on lopulta teksti solmut. Joten unohtamatta niitä oli jonkin verran of yleinen virhe. 

Elin on kolme lasta - Näiden kolmen divs. Joten div, div, div ja sitten teksti solmun lapset näiden divs. Se on aika paljon se että kysymyksiin. 

DAVID J. MALAN: Ja on syytä huomata, vaikka emme asua näissä yksityiskohtia käytämme aikaa JavaScript, että määräys ei, Itse asiassa teknisesti. Joten jos pää tulee ennen elimen HTML, sen pitäisi näyttää jäljellä kehon todellinen DOM. Että hänen on yleensä vain FYI, jotain kutsutaan asiakirja järjestyksessä, jossa sillä on väliä. Ja jos olit täytäntöön jäsennin, ohjelma, joka lukee HTML rakentamisessa ylös puuhun muistissa, ollakseni rehellinen, se intuitiivisesti luultavasti mitä tehdä joka tapauksessa - ylhäältä alas, vasemmalta oikealle. 

ROB BOWDEN: Kysymyksiä tähän? Pitäisi tehdä seuraava? 

DAVID J. MALAN: Toki. 

ROB BOWDEN: OK. Joten tämä on puskurin ylivuoto hyökkäys kysymys. Tärkeintä on tunnistaa tässä, hyvin, miten voisi vastustaja temppu Tämä ohjelma täytäntöönpanosta mielivaltaisen koodin? Joten argv1, ensin komentoriviltä argumentti tähän ohjelmaan, joka voi olla mielivaltaisesti pitkiä. Mutta tässä käytämme memcpy kopioida argv1, joka tässä on baari. Jossa olemme sitä väitettä. Ja niin se on saamassa nimeä baarissa. 

Joten olemme memcpying bar tähän puskuriin c. Kuinka monta tavua me kopiointi? No kuitenkin monta tavua bar sattuu käyttää, pituus tämän väitteen. Mutta c on vain 12 tavua leveä. Jos siis kirjoitat Komentoriviargumentti joka on pidempi kuin 12 tavua, olemme menossa ylivuoto tämän Erityisesti puskuri. Nyt, miten voisi vastustaja huijata ohjelmoida täytäntöönpanovaltion mielivaltaisen koodin? 

Niin muista, että täällä Tärkein soittaa foo. Ja niin sitten tärkein puhelut fooksi. Katsotaanpa piirtää tämän. Joten meillä on pino. Ja tärkein on pinokehyksen alareunassa. Jossain vaiheessa, tärkeimmät puhelut fooksi. No, heti, tärkeimmät puhelut fooksi. Ja niin foo saa oman pinokehyksen. 

Nyt, jossain vaiheessa, foo aikoo palata. Ja meni foo palaa, meidän on tiedettävä milloin mitä koodiriviä sisällä tärkein me olivat kunnossa tietää, missä meidän pitäisi jatkaa pää. Voimme soittaa foo alkaen koko joukko eri paikoissa. Mistä tiedämme minne palata? No, meidän täytyy tallentaa se jonnekin. 

Joten jossain täälläpäin Tallennamme jossa meidän pitäisi palata kerran foo palaa. Ja tämä on palautusosoite. Joten miten vastustaja voi hyödyntää tästä on se, että tämä puskuri C on tallennettu, katsotaanpa sanoa, täällä on c. Joten meillä 12 tavua c. Tämä on c. Ja tämä on foo pinon rengas. Joten jos ilkeä käyttäjä syöttää lisää tavut kuin 12 tai ne tulevat komento argumentti, joka on pidempi kuin 12 merkkejä, niin aiomme ylivuoto tämä puskuri. 

Voimme jatkaa. Ja jossain vaiheessa, menemme pitkälle riitä, että alamme päälle tämä palautusosoite. Kun siis korvata paluuosoite, Tämä tarkoittaa, että kun foo palaa, olemme palaamassa missä pahantahtoinen käyttäjä kertoo sen mukaan arvosta riippumatta se tuli, millä tahansa merkkiä käyttäjä kirjoittaa. Joten jos pahantahtoinen käyttäjä ollaan erityisen taitava, hän voi olla tässä palata jossain printDef toiminto tai jossain malloc toiminto, juuri missään mielivaltainen. 

Mutta vielä fiksu on mitä jos hänellä on käyttäjä palaa täällä. Ja sitten aloitat täytäntöönpanosta näitä riviä koodia. Joten tässä vaiheessa, käyttäjä voi syöttää mitä hän haluaa tälle alueelle. Ja hän on täydellinen hallinta yli oman ohjelman. Kysymyksiä siitä? Joten seuraava kysymys on valmis uudelleen toteutus foo siten, että se ei enää vaarassa. 

Niin siellä pari tapaa olisit voinut tehdä tämän. Meillä on vielä c vain on pituuden 12. Olet olisivat saattaneet muuttaa tätä osana ratkaisua. Lisäsimme myös tarkistaa, jotta Varmista baari ei ollut null. Vaikka et tarvitse että täydet pisteet. Joten me tarkastamme ensin merkkijonon pituus bar. Jos se on yli 12, niin eivät itse tehdä kopio. Joten se on yksi tapa vahvistaa sitä. 

Toinen tapa vahvistaa on sen sijaan ottaa c vain olla pituudeltaan 12, on se olla pituudeltaan strlen (bar). Toinen tapa vahvistaa on todella vain palata. Joten jos sinulla oli juuri päässyt eroon kaikista Tässä, jos olisit juuri poistanut kaikki riviä koodia, olisit saanut täydet pisteet, sillä tämä toiminto ei oikeastaan ​​mitään aikaiseksi. Se kopioimalla komentoriviltä argumentti johonkin array sen paikalliset pinokehyksen. Ja sitten asia on palaamassa. Ja mitä se aikaan on mennyt. Joten paluu oli myös riittävä tapa saada täydet pisteet. 

DAVID J. MALAN: Ei aivan henkeä kysymys, mutta hyväksyttävää kohti spec kuitenkin. 

ROB BOWDEN: Kysymyksiä mitään siitä? Yksi asia, että olet ainakin tarvitaan on koota koodia. Joten vaikka teknisesti et ole haavoittuvaisia, jos koodia ei koota, emme hyväksy sitä. Ei kysymyksiä? OK. 

DAVID J. MALAN: Haluatko sanoa tämän otsikon? 

ROB BOWDEN: Ei. 

DAVID J. MALAN: Joten tämä, tämä oli joko hyvä uutinen tai huono uutinen. Tämä on kirjaimellisesti sama ongelma kuin ensimmäinen tietokilpailu. Ja se on lähes sama ongelma pset1. Mutta se oli tarkoituksella yksinkertaistettu olevan yksinkertaisempi pyramidi, joka voi olla ratkaistu hieman yksinkertaisempi iterointia. Ja oikeastaan, mitä olimme tulossa at tässä ei ollut niinkään logiikkaa, koska luultavasti tässä vaiheessa, olet mukavampaa kuin olit viikolla yksi silmukoita tai miksi silmukoita, mutta todella erottaa toisistaan, että olet hieman mukava ajatus, että PHP ei ole vain siitä, mitä ohjelmointi. Se voi todella käyttää kieltä kirjoittaa komentoriviltä ohjelmia. 

Ja todellakin, se mitä yritimme kiinnittää huomiota. Tämä on komentoriviltä PHP-ohjelma. Joten C-koodia täällä, kun oikea C, ei korjata PHP. Mutta koodi todella on sama. Jos vertaa ratkaisuja Quiz 0 vastaan ​​Quiz 1, huomaat, että se on lähes identtinen, lukuun ottamatta jotkut dollarin merkkejä ja puuttuessa tietotyyppi. Erityisesti jos me katsomaan täällä, näet, että me kerrata tässä tapauksessa 1 läpi 7. 

Olisimme voineet tehdä sen 0-indeksi. Mutta joskus, mielestäni se on vain henkisesti helpompi miettiä asioita 1-7. Jos haluat yhden korttelin, sitten kaksi lohkot, sitten kolme, sitten dot, piste, piste seitsemän. Olemme j alustetaan 1 ja sitten luotan jopa i. Ja täällä kaikki on muuten samanlainen. Mutta huomionarvoisia ovat pari asiaa. Annamme sinulle nämä kaksi riviä, tämä ensin yksi, goofily nimettiin shebang terävät bang. Ja että vain määrittää polun, kansio, jossa ohjelma voi olla totesi, että haluat käyttää tulkita tämän tiedoston. 

Ja sitten linja jälkeen, ja tarkoittaa tietenkin syötä PHP-tilaan. Ja linja alareunaan tarkoittaa exit PHP tilassa. Ja tämä toimii, yleisesti, ja tulkita kielillä. Se on tavallaan ärsyttävää jos kirjoitat ohjelman tiedosto nimeltä foo.php. Ja sitten käyttäjien tarvitsee vain muistaa, OK, ohjelman suorittamiseen, I täytyy kirjoittaa "php tilaa foo.php." Laji harmittaa jos ei muuta. Ja se paljastaa myös, että ohjelma on kirjoitettu PHP, joka ei ole kaikkien että valaisevat käyttäjälle. 

Joten voit poistaa. Php kokonaan muistamme luento. Ja voit itse tehdä. / Foo jos olet chmodded sitä tekemällä siitä executable. Joten chmod + x foo olisi tehnyt niin. Ja jos sinulla on myös lisätä roska täällä. Mutta oikeasti, ongelma oli saada at tulostaa jotain tällaista. Ei HTML, ei C-koodia varmasti, vain joitakin PHP. Joten Milo palasi ongelmatilanteissa 25. Ja 25, saitte seuraavan luuranko-koodi, joka oli melko yksinkertaisia ​​web-sivulle. Ja mehukas osa HTML-viisas laski täällä, missä meillä on rungon sisältä lomake, jossa on yksilöllinen tunnus tuotantopanosten jonka sisällä oli kaksi tuloa, yksi idean nimi yksi joiden ajatus-painiketta. 

Ensimmäinen oli kirjoittaa tekstiä, toisen tyypin lähettävät. Ja niin me annoimme teille, oikeastaan ​​enemmän ainesosia kuin mitä tarvitaan, juuri niin te oli mahdollisuuksia, joita Tämän ongelman ratkaisemiseksi. Sinun ei ehdottomasti tarvitse kaikki nämä tunnukset. Mutta sen avulla voit ratkaista sitä eri tavoin. Ja ylös huipulla, huomaa, että Tavoitteena oli käynnistää ikkuna näin - Hei, Milo! - pop up-selaimen avulla Super yksinkertainen, jos ei ruma, hälytystoiminto. Ja niin lopulta tämä kuihtuu käsitteellisesti jotenkin kuuntelee lausumat muodossa client-side , Ei server-side, jotenkin vastata, että näkökannan tarttumalla Arvo, joka kirjoitetaan sisään nimen kenttään ja se näytetään kielellä elin hälytys. 

Joten yksi tapa voit tehdä tämä on kanssa jQuery, joka näyttää hieman rakenteeltaan hämmentävää aluksi. Voit tehdä tämän kanssa puhdasta DOM-koodi - document.getelement ID. Mutta katsotaanpa katsomaan tätä versiota. Minulla on pari tärkeää linjat ensin. Joten meillä on tämä linja, joka on identtinen, mitä olet ehkä nähnyt vuonna, uskon, form2.html luokan viikolla 9. Ja tämä on vain sanoa, suorita seuraava koodi, kun asiakirja on valmis. Tämä on tärkeää vain siksi, HTML sivut luetaan ylhäältä alhaalta, vasemmalta oikealle. 

Ja siksi, jos yrität tehdä jotain koodin tänne jossain DOM elementti, jotkut HTML-tunniste, se alas täällä, teet sen liian aikaisin, koska tämä ei ole edes luettu muistiin. Joten sanon tämän document.ready line, me sanomme, tässä hieman koodia, selain. Mutta eivät suorita tätä kunnes koko asiakirja on valmis, että on DOM puu olemassa muistissa. Tämä yksi on hieman yksinkertaista, jos syntaktisesti vähän erilainen, jos sanon, tartu HTML-elementti, jonka ainutlaatuinen tunniste on tuloa. Sitähän hash-tunniste tarkoittaa, yksilöllinen tunnus. Ja sitten soitan. Lähetä. 

Joten. Esittää tässä funktio, toisin tunnetaan menetelmä, joka on sisällä objektin vasen puolella, että en korosta. Joten jos luulet tuotantopanosten esine muistiin - ja se todellakin on. Se solmu puussa - . Esittää keinoja, kun tämän lomakkeen tämä tunnus on toimitettu, suorita seuraava koodi. En välitä mitä nimi toiminto on olen täytäntöönpanosta. Joten tässä olen käyttäen, kuten ennen, mikä on kutsutaan lambda-toiminto tai Nimetön toiminto. Se ei ole ollenkaan älyllisesti mielenkiintoinen muuta kuin se ei ole nimeä, mikä on hienoa, jos olet vain ikinä kutsua sitä kerran. Ja sisällä on olen itse hoitaa jättämisen muodossa. Haluan ensin julistaa muuttuja nimeltään arvo. Ja mitä sitten on vaikutus tämän korostettu osa täällä nyt? Mitä tämä tekemistä korkeatasoinen minulle? 

Yleisö: Se saa arvon, joka Käyttäjä ei itse HTML alla. Se saa että tunnus ja sitten toteaa sen arvoa. 

DAVID J. MALAN: Aivan. Se tarttuu solmu, jonka ainutlaatuinen tunniste on nimi. Se saa arvon osalta, joista on, oletettavasti, mitä käyttäjä kirjoituskoneella itseään. Ja sitten se tallentaa että muuttuja nimeltä arvoa. Sivuhuomautuksena, sinulla voisi olla myös tehnyt tätä hieman eri tavalla. Täysin hyväksyttävää tekemällä jotain valhe var arvo saa document.getElementById. Ja siksi se on vähän ikävä käytä jQuery. "Nimi". Arvon. Niin täysin hyväksyttävää. Erilaisia ​​tapoja tehdä tätä. jQuery vain taipumus olla hieman täsmällisemmin ja varmasti suositumpi keskuudessa ohjelmoijia. 

Nyt olen tekemässä hieman järki tarkistaa, koska ongelma lausuma me nimenomaan sanoi, jos Käyttäjä ei ole vielä kirjoittanut hänen Nimi, älä näytä hälytyksiä. Mutta voit tarkistaa, että vain tarkistamalla tyhjä merkkijono quote-lainaus jos on mitään todella olemassa. Mutta jos se ei ole sama kuin quote-lainaus, Haluan soittaa hälytykset. Ja mielenkiintoinen osa tässä on se, että käytämme plus toimija, joka tekee mitä JavaScript? KETJUTA. Joten se on kuin PHPs dot operaattori. Sama idea, hieman eri syntaksia. Ja olen vain luoda merkkijono, joka näit kuvakaappaus - Hei, niin ja niin. 

Ja sitten viimeistä yksityiskohtaa on tämä. Miksi return false sisällä Tämän Nimetön toiminto? 

Yleisö: Ei ole arvoa. Laitat sen muodossa. Se vain kertoo, jos arvo ei ole yhtä tyhjä, niin tee se. Oli tyhjä tätä väitettä. 

DAVID J. MALAN: OK. Kuitenkin varovainen. Ei kukaan muu täällä. Ja että paluu vääriä ulkopuolella ja jos olosuhteet. Joten tämä korostetun rivin, return false, toteuttaa mitä tahansa, kun lomake lähetetään. Mitä palaavat vääriä sisäosat Tapahtumakäsittelijän kuten sitä kutsutaan, kyseiseen tapahtumaan ollessa jättämisestä? 

Yleisö: Koska se tapahtuu vain kerran. 

DAVID J. MALAN: tapahtuu vain kerran. Ei aivan. Joo? 

Yleisö: Se estää lomakkeen toimittavat oletustoimintaa, joka tekisi sivun reload. 

DAVID J. MALAN: Aivan. Joten olen ylikuormitusta aikavälillä esittää täällä, koska minä sanon, muoto on esittämisestä. Mutta kuten ehdotatte, se ei todellisuudessa ole jätetty tosi HTTP tavalla. Kun valitset Lähetä, koska meidän onsubmit käsittelijä, olemme kuuntelua että lomakkeen lähettäminen niin sanotusti. Me sitten tekee meidän juttu JavaScript-koodin. Mutta olen tietoisesti palaamassa vääriä, sillä se, mitä en halua tapahtuvan Sekunnin murto myöhemmin on koko lomake itse toimitetaan web palvelimelle keskeinen arvo pareja muuttamalla URL olla jotain q = kissoja tai mitä teimme, esimerkiksi luokassa. En halua että näin tapahtuu, koska ei ole palvelin kuuntelee tätä lomakkeen lähettäminen. Se on puhtaasti tapahtuu JavaScript-koodia. Ja siksi en edes ole toiminta määritteen minun muodossa, koska olen aio tähän kohteeseen koskaan mene palvelimelle. 

Joten se on toimitettu. Mutta emme kuuntelua, että lomake esittämisen ja estää oletuksena käyttäytyminen, joka on todella mennä aina palvelimelle. 

Yleisö: niin pitää se client-side. 

DAVID J. MALAN: Keeping se client-side. Aivan oikein. Seuraavaksi oli minun oh MySQL. 

ROB BOWDEN: OK. Joten tämä ensimmäinen kysymys oli yleensä karkea ihmisille. Vaikka myöhemmin niistä meni paremmin. Joten sinulla oli valittava oikeat tiedot tyyppejä molemmat näistä sarakkeita. Ja molemmat on joitakin asioita heille, että tekevät valinnan vaikeaksi. Joten int ei ollut voimassa kirjoita numeron. Syynä on 12-numeroinen tunnus numero, int ei ole tarpeeksi suuri tallentaa yhteensä numeroa. Joten voimassa valinta olisi ollut iso int jos satut tietää, että. Toinen vaihtoehto olisi voinut olla char alalla pituus 12. Joten jompikumpi näistä olisi toiminut. Int eivät. 

Nyt, tasapaino, muistelen pset7. Joten me nimenomaan käytetään desimaali tallentaa osakkeiden arvo tai - 

DAVID J. MALAN: Cash. 

ROB BOWDEN: Cash. Käytimme desimaalin tallentaa määrä rahaa, että käyttäjä on tällä hetkellä. Joten syy teemme joka on koska muistan, kellukkeet. Ei liukuluku tarkkuus. Se ei voi tarkasti tallentaa käteistä arvoja, kuten me haluamme täällä. Joten desimaalin pystyy tarkasti tallentaa jotain, sano, kahden desimaalin tarkkuudella. Siksi tasapaino, haluamme sen olla desimaalin eikä kellua. 

DAVID J. MALAN: Ja myös, liian, vaikka se olisi voinut olla fiksu muissa yhteyksissä ajatella, ehkä tämä on mahdollisuus int. Otan vain seurata asioita penniä. Koska me nimenomaan osoitti oletus arvo on 100,00, että Sen voisi vain olla int. Ja toinen hienovaraisuus liian kanssa numero oli, että se ei ollut tarkoitus olla kompakysymys. Mutta muistuttaa, että int MySQL, kuten C, ainakin laite, on 32-bittinen. Ja vaikka emme odota sinun tietää tarkalleen, kuinka monta numeroa että keinot, älä muistaa, että eniten voit edustavat mahdollisesti 32-bittinen numero on suunnilleen mitä? 

Mikä numero me aina sanoa? 2 32, joka on mitä suurin piirtein? Sinun ei tarvitse tietää tarkasti. Mutta karkeasti on hyödyllistä elämässä. Se on noin 4 miljardia euroa. Joten olemme sanoneet, että muutaman kerran. Tiedän, että olen sanonut, että muutaman kerran. Ja se on noin 4 miljardia euroa. Ja se on hyvä sääntö peukalo tietää. Jos sinulla on 8 bittiä, 256 on maaginen numero. Jos sinulla on 32 bittiä, 4 miljardia antaa tai ottaa. Joten jos vain kirjoittaa 4 miljardia, huomaat, että se on vähemmän numeroita kuin 12, mikä tarkoittaa, että ei selvästikään tarpeeksi ilmaisukyky kaapata 12-numeroinen tilinumero. 

ROB BOWDEN: OK. Joten toisilla meni paremmin. Joten olettaa, että pankki asetetaan 20 dollaria kuukaudessa Yhtiövastike kaikkiin tileihin. Millä SQL-kysely voisi pankki vähentää 20 dollaria jokaisesta luottaa, vaikka se johtaa joissakin negatiiviset saldot? Joten periaatteessa on neljä päätyyppiä kyselyt - lisätä, valitse, päivittää ja poistaa. Niin mitä luulemme aio käyttää täällä? Päivitä. 

Joten katsotaanpa katsomaan. Joten tässä olemme päivittää. Mitä taulukossa me päivittää tilejä? Joten päivittää tilejä. Ja sitten syntaksin sanoo, mitä tileillä me päivittää? No, olemme arvostelemassa tasapaino yhtä nykyinen arvo tasapaino miinus 20. Joten tämä päivittää kaikki rivit Tilien, vähentämällä 20 dollaria tasapainoa. 

DAVID J. MALAN: Yleinen virhe tässä, vaikka joskus anteeksi sitä, oli oikeastaan ​​PHP täällä soittamalla hakutoiminto tai käyttöön lainausmerkkeihin kaiken, ei tarvitse olla siellä. 

ROB BOWDEN: Muista, että MySQL on erillinen kieli PHP. Satumme olla kirjallisesti MySQL PHP. Ja PHP on sitten sen lähettämistä yli MySQL-palvelimen. Mutta sinun ei tarvitse PHP voidakseen kommunikoida MySQL-palvelimen. 

DAVID J. MALAN: Aivan. Joten ei muuttujat dollarin merkkejä tulisi olla tässä yhteydessä. Se voi vain tehdä kaikki matematiikka tietokannassa itse. 

ROB BOWDEN: OK. Joten seuraava. Onko tämä seuraava? Joo. Joten mitä SQL-kysely voisi pankki noutaa tilinumerot sen rikkain asiakkaita, joilla on saldot yli 1000? Joten mikä on neljä päätyyppiä aiomme haluat täällä? Valitse. Joten haluamme valita. Mitä me haluamme valita? Mitä sarake haluamme valita? Me nimenomaan haluamme Valitse numero. Mutta jos olet sanonut tähden, me myös, että. 

Joten valitse numero mitä pöytään? Tilit. Ja sitten kunnon haluamme? Jossa tasapaino on suurempi kuin 1000. Olemme myös hyväksynyt suuremman tai yhtä suuri kuin. Viimeinen. Millä SQL-kysely voisi pankki lähellä, ts. poistaa jokaisen huomioon, että on tasapaino 0 dollaria? Joten mikä neljästä olemme menossa haluavat käyttää? Poista. Joten syntaksin? Poista mitä pöytään? Tilit. Ja sitten, millä ehdolla haluamme poistaa - jos saldo on nolla. Joten poistaa kaikki rivit tilit jos saldo on nolla. Kysymyksiä mitään näistä? Haluatko jonoon? 

DAVID J. MALAN: Jono opas. Joten tässä yksi, me annoimme teille hieman tuttu rakenne, joka selvitimme bittinen luokassa rinnalla structs, joka oli tiedot rakenne liittyvät hengessä. Ero joskin jono on että meidän piti jotenkin muistaa, kuka oli jonon, suurissa osittain siten, että voisimme tehdä enemmän tehokas käyttö muistia, ainakin jos käytimme array. 

Koska muistaa, jos meillä on erilaisia, jos Esimerkiksi, tämä on edessä jono, jos saan jonoon täällä, ja sitten joku saa linjassa takanani, takanani, takanani, ja yksi henkilö astuu ulos linja, voit voisi, kuten näimme joitakin ihmisen vapaaehtoisia luokassa, ovat kaikki siirtää tällä tavalla. Mutta yleensä, joilla jokainen tehdä jotain ei ole parasta aikaa ohjelmassa, koska se tarkoittaa, että algoritmi on käynnissä missä asymptoottinen ajoaika? Se on lineaarinen. 

Ja minusta tuntuu, että on typerää. Jos seuraava henkilö on vuorossa seuraava henkilö, joka on tarkoitus mennä myymälä, ne eivät kaikki ole liikkua yhdessä. Päästä tämä henkilö repelin kun se aika tulee, esimerkiksi. Jotta voimme säästää hieman aikaa siellä. Ja niin tehdä, että kuitenkin, että keinot että jonon tai jonon on menossa edetä asteittain syvemmälle ja syvemmälle osaksi array ja lopulta ehkä todella kietoa jos käytämme array tallentaa ihmisiä tässä jonossa. Joten voit melkein ajatella array pyöreä tiedot rakenne siinä mielessä. 

Joten jotenkin täytyy seurata koko sitä tai oikeastaan ​​lopussa se ja sitten jos alussa on. Joten ehdotamme, että ilmoitatte Yksi tällainen jono, kutsuvan se q, vain yksi kirjain. Sitten ehdotamme, että edessä on alustetaan nollaksi, ja että koko alustetaan nollaan. 

Joten nyt, ei mitään sisällä jonoa. Ja pyydämme sinua täyttämään täytäntöönpanoa enqueue alla siten, että toiminto lisää n- loppuun q ja palauttaa sitten totta. Mutta jos q on täynnä tai negatiivinen, toiminto pitäisi sen sijaan palauttaa false. Ja me annoimme teille pari oletuksia. Mutta ne todellisuudessa ole toiminnallisesti asiaa, vain että bool olemassa, koska, teknisesti, bool ei olemassa C ellet sisällyttää tietyt header-tiedosto. Niin että oli vain varmistaa, ettei ollut tämä temppu Kysymys sellainen asia. 

Joten enqueue ehdotimme näytteessä ratkaisuja toteuttaa seuraavasti. Yksi, tarkistamme ensin helppous, matalalla roikkuvat hedelmät. Jos jono on täynnä tai numero yrität lisätä on vähemmän kuin nolla, jonka totesimme erittely ongelma pitäisi ei voida sallia, koska me vain haluamme ei-negatiivisia arvoja, niin kannattaa vain return false välittömästi. Joten jotkut suhteellisen helppoa virheentarkistukset. Jos vaikka haluat lisätä, että todellinen numero, sinun piti tehdä vähän Tarkoitan nyt. Ja tässä se on vähän ärsyttävää henkisesti, koska sinun täytyy selvittää, miten käsitellä kaareva. 

Mutta alkiot Ideana se on etua meille on, että ympäröivä edellyttää usein modulaarinen aritmeettinen ja mod-operaattori prosenttia puolella, jossa voit siirtyä suuremman arvon takaisin nollaan ja sitten yksi ja kaksi ja kolme ja sitten takaisin noin nollaan, yksi ja kaksi ja kolme ja niin edelleen uudelleen ja uudelleen. Joten miten me ehdotamme tehdä tämä on että haluamme indeksinä array kutsutaan numerot meidän kokonaislukuja valehdella. Mutta sinne, haluamme ensin tehdä koosta riippumatta jono, mutta lisätään sitten, että mitä tahansa edessä lista on. Ja vaikutus, joka on tehnyt meistä oikeaan asentoon jonossa ja oleta, että ensimmäinen henkilö vastaa on alussa, jonka hän tai hän ehdottomasti voisi olla, jos me Myös siirtymässä kaikille. Mutta olemme vain työllistää itsellemme jos otimme että tiettyä polkua. 

Jotta voimme pitää sitä suhteellisen yksinkertainen. Meillä täytyy muistaa, että me vain lisätty int jonoon. Ja sitten me vain palata totta. Samaan aikaan dequeue, pyysimme voit tehdä seuraavaa. Toteuttaa se siten, että se dequeues, että on Poistaa ja palauttaa, int edessä jonossa. Voit poistaa int, riittää unohtaa sen. Sinun ei tarvitse ohittaa sen vähän. Joten se on silti todella olemassa. Aivan kuten tiedot kiintolevyltä, me vain sivuutettu se tosiasia, että se on nyt siellä. Ja jos q on tyhjä, meidän pitäisi sen sijaan palata negatiivinen 1. Joten tämä tuntuu mielivaltainen. Miksi palata negatiivinen 1 sijasta vääriä? Joo. 

Yleisö: Q tallentaa positiivisia arvoja. Koska sinulla on vain tallentaa positiivisia arvoja Q, negatiivinen on virhe. 

DAVID J. MALAN: OK, totta. Niin, koska olemme vain säilytykseen positiivinen arvoja tai nolla, niin se on hienoa palautettava kielteinen arvo Sentinel arvo, erikoissymboli. Mutta olet kirjoittamasta historiaa siellä, koska syy me olemme vain paluu ei-negatiivisia arvoja on koska haluamme on Sentinel arvoa. Joten tarkemmin, miksi ei vain return false virhetapauksissa? Joo. 

Yleisö: Olet epäonnistui palata kokonaisluku. 

DAVID J. MALAN: Aivan. Ja tämä on C saa melko rajoittava. Jos sanot aiot palata int, sinulla palata int. Et voi saada hienoja ja palautuvan bool tai float tai merkkijono tai jotain. Nyt puolestaan ​​JavaScript ja PHP ja joillakin muilla kielillä voi itse asiassa, oletko palaamassa eri tyyppisiä arvoja. Ja se voi todella olla hyötyä, jos voisit palata positiivinen ints, nollia, negatiivinen ints tai vääriä tai null jopa merkitä virhe. Mutta meillä ei ole, että monipuolisuutta C. 

Joten dequeue, mitä me aikoo tehdä on - 

ROB BOWDEN: Voit palauttaa false. Se on vain, että väärä on hash määritellä vääriä nollaan. Joten jos palaat vääriä, palaat nolla. Ja nolla on voimassa asia meidän jonossa, Kielteisten 1 ei ole, jos false sattui olemaan negatiivinen 1. Mutta sinun ei pitäisi edes täytyy tietää, että. 

DAVID J. MALAN: Tuo miksi en sano sitä. 

ROB BOWDEN: Mutta se ei ollut totta että et voi palata vääriä. 

DAVID J. MALAN: Toki. Joten dequeue, huomaa hyväksymme mitätöidä argumenttina. Ja se johtuu siitä emme ole ohimennen mitään sisään Haluamme vain poistaa elementin edessä jonossa. Joten miten me saatamme edetä näin? No, ensinnäkin, tehdään tämä nopeasti järki tarkistaa. Jos jonon koko on 0, siellä ei tehtävää. Palata negatiivinen 1. Valmis. Niin, että muutaman rivin minun ohjelma. Joten vain neljä riviä jäljellä. 

Joten tässä päätän dekrementoidaan kokoa. Ja pienentämällä kokoa tehokkaasti tarkoittaa sitä, että olen unohtanut jotain on siellä. Mutta minulla on myös päivittää, jos edessä numerot. Niin tehdä, että tarvitsen tehdä kaksi asiaa. Haluan ensin täytyy muistaa, mitä numero on jonon, koska minun täytyy palata, että asia. Joten en halua vahingossa unohtaa siitä ja sitten korvata sen. Olen juuri menossa muistaa int. 

Ja nyt haluan päivittää q.front voidaan q.front +1. Joten jos tämä oli ensimmäinen henkilö linja, nyt haluan tehdä plus 1 osoitat seuraava henkilö linjassa. Mutta minun täytyy käsitellä sitä ympäröivä. Ja jos kapasiteetti on maailmanlaajuinen vakio, että menee saanen varmistaa kuten Osoitan hyvin viimeinen henkilö linja, modulo-operaation tuo minut takaisin nollaan jonon. Ja joka käsittelee ympäröivä täällä. Ja sitten lähden palata n. 

Nyt, tarkkaan ottaen, en on julistaa n. Minulla ei ollut napata se ja säilytä sitä väliaikaisesti, koska arvo on edelleen olemassa. Niin voisin vain tehdä oikea aritmeettinen palata entisen johtajan jonon. Mutta minä vain tuntui, että tämä oli selvempi todella napata int, laita se N, ja palata sitten, että selvyyden vuoksi, mutta ole ehdottoman välttämätöntä. Psst. He kaikki lausuttavia päähäni. 

ROB BOWDEN: Eli ensimmäinen kysymys on binääripuu ongelma. Joten ensimmäinen kysymys on, olemme antanut näitä numeroita. Ja haluamme jotenkin lisätä ne nämä solmut siten, että se on voimassa binäärihakupuu. Joten yksi asia muistaa binäärihaku puita on, että se ei ole vain, että asia vasemmalle on vähemmän ja asia oikeus on suurempi. Sen on oltava, että koko puun vasemmalla on vähemmän, ja koko puu oikealla on suurempi. 

Joten jos laitan 34 täällä huipulla, ja sitten Laitoin 20 täällä, niin se on voimassa niin pitkälle, koska 34 täällä. 20 on menossa vasemmalle. Niin, että vähemmän. Mutta en voi sitten laittaa 59 täällä, koska vaikka 59 on oikealla puolella 20, se on edelleen vasemmalla puolella 34. Niin, että rajoitus mielessä, Helpoin tapa lienee ratkaista tämä Ongelmana on vain eräänlainen näistä numeroista - niin 20, 34, 36, 52, 59, 106. Ja asenna ne vasemmalta oikealle. 

Joten 20 menee täällä. 34 menee täällä. 36 menee täällä. 52, 59, 106. Ja voit myös voinut tajunnut kanssa jotkut kytkemällä ja toteuttamisessa, Odota, minulla ei ole tarpeeksi numeroita täyttämään tämän tänne. Joten minun täytyy reshift mitä minun reitti huomautus tulee olemaan. Mutta huomaa, että kolmessa viimeisessä, jos luet vasemmalta oikealle, se on kasvavassa järjestyksessä. 

Joten nyt haluamme julistaa mitä struct tulee olemaan varten solmut tässä puussa. Mitä me tarvitsemme binääripuun? Joten meillä on arvo tyyppiä int, joten jotkut int arvo. En tiedä, mitä me kutsutaan se ratkaisu - int n. Meidän osoitin vasen lapsi ja osoitin oikea lapsi. Joten se tulee näyttää tältä. Ja se tulee todella näyttävät ennen Milloin kaksinkertaisesti sidottu lista tavaraa, joten ilmoitus - Aion tarvitse vierittää kaikki Paluumatkalla alas ongelmaan 11. 

Niin huomaa se näyttää identtinen tämän, paitsi me vain sattuvat kutsua näitä eri nimiä. Meillä on vielä kokonaisluku arvo ja kaksi osoitinta. Se on vain, että sen sijaan hoitoon osoittimet viittaavat myös seuraava asia ja edellinen asia, olemme hoitoon osoittimet osoittamaan vasen lapsi ja oikea lapsi. OK. Niin, että meidän struct solmu. Ja nyt, ainoa tehtävä meidän toteuttaa tähän on Traverse, joka haluamme mennä yli puiden, tulostus ulos arvot puun järjestyksessä. 

Joten katson tässä, me haluaisi tulostaa pois 20, 34, 36, 52, 59, ja 106. Miten me sen aikaan? Joten se on melko samanlainen. Jos näit aiemmin tentti ongelma että halusit tulostaa koko puun pilkuilla välillä kaikki, se oli itse asiassa jopa helpompaa kuin se. Joten tässä on ratkaisu. Tämä oli huomattavasti helpompaa jos teit sen rekursiivisesti. En tiedä, jos joku yritti tehdä se iteratiivisesti. 

Mutta ensin meillä on perusta tapauksessa. Entä jos juuri on nolla? Sitten me vain aio palata. Emme halua tulostaa mitään. Else aiomme kulkea rekursiivisesti alas. Tulosta koko vasemman alipuun. Joten tulostaa kaiken vähemmän kuin minun nykyinen arvo. Ja sitten aion tulostaa itse. Ja sitten aion recurse alas minun koko oikea alipuu, joten kaikki suurempi kuin minun arvo. Ja tämä on menossa painoon ulos kaikki kunnossa. Kysymyksiä siitä, miten tämä todella aikaan, että? 

Yleisö: Minulla on kysymys on [kuultavissa]. 

ROB BOWDEN: Joten yksi tapa lähestyä mitään rekursiivinen ongelma on ajatelkaa siitä kuin sinun on ajateltava kaikista nurkassa tapauksissa. Mieti siis, että haluamme tulosta tämä kokonaisen puun. Joten kaikki aiomme keskittyä on tässä solmu - 36. Rekursiokutsua, me teeskennellä nämä vain toimivat. Joten tässä, tämä rekursiivinen kutsu poikittainen, me edes ajattelematta siitä, vain liikkumisesta vasen kolme, kuvitella, että jo tulostaa 20 ja 34 meille. Ja sitten kun me lopulta rekursiivisesti soittaa Traverse on oikeus, joka oikein tulostaa 52, 59 ja 106 meille. 

Joten koska tämä voi tulostaa 20, 34, ja muut voivat tulostaa 52, 59, 108, kaikki mitä meidän tarvitsee pystyä tekemään on tulosta ourself keskellä sitä. Joten tulostaa kaikki ennen meitä. Tulosta itsestämme, joten nykyinen solmu tulosta 36, säännöllinen printf, ja sitten tulostaa kaiken meidän jälkeemme. 

DAVID J. MALAN: Täällä rekursio saa todella kaunista. On tämä uskomaton harppaus uskosta, jossa teet pienimmätkin vähän työtä. Ja sitten annat jonkun muu hoitaa loput. Ja että joku muu on, ironista kyllä, voit. Niin vakavia tonttu pistettä, jos selaat ylös kysymykset - 

ROB BOWDEN: On kysymyksiä? 

DAVID J. MALAN: Ja alas vähän numerot, ei kukaan tiedä, missä nämä luvut tulevat? 

ROB BOWDEN: Minulla ei kirjaimellisesti ole aavistustakaan. 

DAVID J. MALAN: Ne näkyvät koko tietokilpailu. 

Yleisö: Ovatko ne samat numerot? 

DAVID J. MALAN: Nuo luvut. Pikku pääsiäismunia. Joten ne teistä katsomassa netissä kotiin, jos voit kertoa meille sähköpostitse heads@CS50.net mitä merkitystä Näiden toistuvien kuusi numeroa ovat koko Quiz 1, me suihku sinulle hämmästyttävän huomiota lopullisessa luento ja stressipallo. Kiva, hienovarainen. 

ROB BOWDEN: Viimeisiä kysymykset noin mitään tietovisa?