>> DAVID J. Malan V redu.
Torej, dobrodošli na prvi CS50 Obdukcija za kviz.
Mislili smo slovesno ta tradicija letos.
In to bo priložnost prehoditi
rešitve za kviz.
In bomo pospešiti ali upočasniti temeljijo v interesu tistih, ki tukaj.
>> Torej, ste verjetno tu, ker ste zanima, kako bi lahko imela ali
bi morali odgovorili na nekaj teh problemov.
Torej, zakaj ne bi pogledali V tem poglavju najprej?
Tako dobili strune.
To ti je dal tri različne verzije programa, ki je bil na koncu
pomenilo, da bi dobili niz od uporabnika.
Ali ne, je to storil, da je bilo prepuščena vam določiti.
>> In smo spraševali v vprašanju 0, Predvidevam, da je verzija 1
zbrati in usmrtili.
Zato bi lahko program segfault?
Na prvi pogled je vse predloge , zakaj?
Ja.
>> PUBLIKA: Torej Spomnim videnje to Prejšnji primer gledanja na
char * s in videnje skeniranje S in vidim, ker je kazalec, kako
ni vplivala, kaj skenirate?
Je S ali naslov s?
>> DAVID J. Malan: OK.
Dobro.
Torej v končni fazi, vir kakršnih koli težav verjetno je šlo za zmanjšanje
na to spremenljivo s.
In to je res spremenljivka.
Podatkovni tip te spremenljivke char *, kar pomeni, da se bo
vsebuje naslov značaja.
In v tem leži vpogled.
To se dogaja, da vsebuje naslov znak ali, bolj splošno,
naslov prvega znaka v cel niz znakov.
>> Vendar ulov je, da skeniranje s, namen v življenje, je dal naslov in dana
koda format, kot% s, preberite niz v kos
spomin na ta naslov.
Ampak zato, ker ni enačaj pred da podpičjem na prvi
vrstica kode, saj smo dejansko ne Dodeljevanje pomnilnika z
malloc, saj dejansko ni dodeliti niz neke velikosti, vse
delaš bere uporabnikov Tipkovnica vhod v nekatere popolna
Smetarsko vrednost, ki je s privzeto.
Torej so možnosti, da boš, če segfault da naslov ne samo zato, da se zgodi
biti vrednost, ki jo lahko, v resnici, pišejo.
Tako slabo, da ne dodeli vaš spomin tam.
>> Torej v vprašanju 1, smo vprašali, Predvidevam, da je verzija 2
zbrati in usmrtili.
Zakaj bi ta program segfault?
Torej, to je eden manj buggy.
In tam je res samo ena očiten način, kjer lahko
sproži segfault tukaj.
In to je tematski.
Vsak čas bomo z uporabo C v spomin, kaj bi lahko naredil za sprožanje segfault
z verzijo 2?
>> PUBLIKA: Če uporabljate ta prispevek v niz, ki je daljši od 49
znake.
>> DAVID J. Malan: Točno tako.
Vsak čas boste videli nekaj fiksne dolžine ko gre za matriko, vaš
radar bi moral iti dol, da bi to lahko bilo problematično, če ne boš preverjanje
Meje matriko.
In to je problem tukaj.
Mi še vedno uporabljate scanf.
Mi še vedno uporabljate% s, kar pomeni, da poskusite brati niz od uporabnika.
To se dogaja, da je treba brati v sekundah, ki je na tej točki, ki je dejansko
naslov kos pomnilnika ali je to enakovredno.
To je ime array znakov pomnilnika.
>> Ampak točno to, če si prebral niz , ki je daljše od 49 znakov, 49
saj boste morali prostor za poševnica nazaj 0, boš overflow
da buffer.
In boste morda dobili srečo in biti sposoben napisati 51. značaj, 52., 53..
Toda na neki točki, OS je reči, ne.
To definitivno ni spomin boste smeli dotakniti.
In program se bo segfault.
>> Tako da bi bilo treba tolči biti vsak Čas imaš fiksno dolžino, imate
se prepričajte, da ocenjujete dolžino ne glede na to je, da poskušate
prebrati vanjo.
>> PUBLIKA: Torej rešiti, da bi lahko so imeli izjavo preverjanje dejansko
je dolžina večja ali manjša od?
>> DAVID J. Malan: Absolutno.
Moraš stanje , ki pravi, če -
oziroma vam ni nujno vedeti vnaprej, koliko znakov
Uporabnik se dogaja na vrsto, saj imate piščanca in jajca.
Ne, dokler ste prebrali se s scanf lahko ugotovimo, kako dolgo je.
Toda na tej točki, da je prepozno, ker ste že prebrali v
nekatere blok pomnilnika.
Tako kot prahi, so CS50 knjižnica izogiba to vprašanje v celoti, odpoklic
z uporabo fgetc.
In to prebere en znak naenkrat, -tip toeing skupaj, vedoč, da vam
ne morejo overflow znak, če si prebral eno naenkrat.
>> Ulov je z getstring odpoklic je da imamo nenehno ponovno velikosti
da je kos pomnilnika, ki je le bolečina.
To je veliko vrstic koda za to.
Tako drugačen pristop bi bilo, da dejansko uporabo bratranca, tako da
rekoc scanf.
Obstajajo variante veliko teh Funkcije, ki dejansko preverjajo
dolžina, koliko znakov boste lahko prebrali maksimalno.
In lahko podate, ne berejo več kot 50 znakov.
Zato, da bi bil še en pristop, vendar manj ustrežljivi večjih vložkov.
>> Torej, vprašanje 2 prosi, domnevam, da je različica 3 se zbirajo in usmrtili.
Zato bi lahko ta program segfault?
Potemtakem se to dejansko enaka odgovori, čeprav
Izgleda malo Ljubitelj.
Mi smo z uporabo malloc, ki se počuti kot smo kar sami več možnosti.
In potem smo se sprostilo, da pomnilnika na koncu.
To je še vedno le 50 bajtov pomnilnika.
Tako da bomo lahko še vedno poskusite prebrati v 51, 52, 1000 bajtov.
To se dogaja, segfault za točno istega razloga.
>> Vendar obstaja še en razlog preveč.
Kaj drugega bi lahko malloc donos poleg naslov kos spomina?
To lahko vrne null.
In ker nismo preverjanje da smo lahko delaš nekaj
neumen, zaradi drugega razloga, ki je, da bomo lahko povedali scanf, preberite
uporabnikov vnosna v 0 lokaciji, AKA null.
In tudi to bo zagotovo sproži segfault.
Torej za namen kviza je, da bomo so sprejeli eno od teh, kot je
tehten razlog.
Ena je identična.
Ena je malo bolj prefinjen.
>> Nazadnje, glede na program, je Uporaba spomina, kako verzija 2
različica 3 razlikujeta?
Torej, za kaj je vredno, bomo videli videz neskončno dobavo mogoče
odgovori na to.
In med odgovori ljudi, kar smo bili v upanju, vendar smo sprejeli drugo
stvari, je nekaj omembe Dejstvo, da je verzija 2 z uporabo
ti dimnika.
Različica 3 je s pomočjo kopice.
In funkcionalno, to sploh ni bi vse, da veliko razliko.
Ob koncu dneva, smo vedno samo še 50 bajtov pomnilnika.
>> Toda to je bil eden od možnih odgovorov da smo gledaš.
Vendar pa boste videli, kakor vam vaš kvizi nazaj na TF, da smo
sprejme druge razprave o njihovih različni načini uporabe spomina, kot tudi.
Ampak kup in kup bi bilo preprost odgovor, da gredo s.
Vsa vprašanja?
Dal ti bom Rob.
>> ROB Bowden: Torej, problem 4.
To je tista, v kateri ste morali izpolniti število bajtov iz vseh
te različne vrste, ki se uporabljajo.
Torej prva stvar, ki jo vidim.
Predvidevam, 32-bitno arhitekturo, kot je ta CS50 aparata.
Tako je eden od temeljnih stvari o 32-bitne arhitekture, ki nam pove,
točno, kako velik kazalec se dogaja da je v strukturi.
>> Tako takoj vemo, da vsak kazalec Tip je 32-bitov ali 4 bajte.
Tako je videti na tej mizi, vozlišče * je kazalcem.
To se dogaja, da je 4 bajte.
Struct node *, ki je dobesedno identična vozlišča zvezdico.
In tako, da bo še 4 bajte.
String, tako da ne izgleda kot kazalec še, vendar typedef,
Niz je samo char *, ki je kazalcem.
Tako da bo še 4 bajte.
>> Torej, ti trije so vsi 4 bajte.
Zdaj vozlišče in študenti pa so na malo bolj zapletena.
Tako je videti na vozlišču in študent, bomo videli vozlišče kot celo število in kazalcem.
In študent dva kazalca v njem.
Tako vsaj našem primeru tukaj, način da smo na koncu izračunavanju
to struct je samo sešteti vse da je znotraj struct.
>> Torej za vozlišče, imamo celo število, ki je 4 bajte.
Imamo kazalec, ki je 4 bajte.
In tako eno vozlišče se dogaja da prevzamejo 8 bajtov.
Podobno velja tudi za študenta, imamo kazalec, da je 4 bajte in drugo
kazalec, da je 4 bajte.
Tako da bo do konca je do 8 bajtov.
Torej vozlišče in študenti pa so na 8 bajtov.
In ti trije so vse 4 bajte.
Vprašanja o tem?
Da.
>> PUBLIKA: Ali je bila 64-bitni arhitekture, ki bi
podvojila vse od njih?
>> ROB Bowden: To ne bi podvojila vse.
Tako 64-bitni arhitekturi, je, še enkrat, Spremembe, ki temeljna stvar, ki
kazalec je zdaj 64 bitov.
Ja.
Torej kazalec je 8 bajtov.
To je torej, da so 4 bajti se bo 8 bajtov.
Študent, ki je bil dva kazalca, dobro, zdaj pa se dogaja, da
biti 8 bajtov, 8 bajtov.
To se dogaja, da 16 bitov.
>> Ampak vozlišče je še vedno 4 bajte.
Tako da je ta kazalec se dogaja kot 8 bitov.
To je 4 bajte.
Torej vozlišče je samo še na 12 bajtov.
Vsa druga vprašanja, na tista?
Torej, naslednjič, to so kode stanja HTTP.
In si moral opisati okoliščine v skladu s katerimi bi se ti lahko
se vrnil v vas.
en problem, da sem slišal nekaj študente , je, da sta se trudila, da bi
napake, se na koncu stranke.
Torej, ko smo poskušali, da bi zahtevo na strežnik, kar gre
narobe na našem koncu.
Ampak na splošno, te oznake so se vrne strežnik.
Zato želimo, da ugotovimo, kaj se dogaja narobe ali prav na strežniku, ki
povzroča te stvari je treba vrniti.
Torej, zakaj bi lahko strežnik vrne Statusna koda 200?
Vsak misli?
>> Ja.
Torej nekaj o uspešno prošnja šla skozi.
In oni lahko vrnejo karkoli zahteval.
Torej je vse v redu.
Kaj pa 302 našel?
Ja.
>> PUBLIKA: Strežnik je iskal za to, kar ste zahtevali.
Ampak to ni mogel najti.
Torej je napaka.
>> ROB Bowden: Torej strežnik je išče tisto, kar si hotel.
Torej samo gledaš tukaj, 302 je pokazala, je bilo mogoče najti.
>> PUBLIKA: Žal mi je.
Najdeno pomeni, da so to storili našli.
Žal mi je.
>> ROB Bowden: Do 302 našel.
Strežnik je uspelo najti kaj si hotel.
>> PUBLIKA: Ampak to ne prikazuje?
>> ROB Bowden: Razlika med Ta 302 in 200 je, da
ve, kaj hočeš.
Ampak to ni točno tam, kjer si hotel vprašati.
Torej 302 je tipično preusmeritev.
Torej ste zahtevali strani.
To ve, oh, hočem vam vrne to.
Ampak to je na različnih URL.
Torej, hej, si dejansko želijo to.
>> DAVID J. Malan: To je del, ki je dejal, da smo dali vidva preusmeritev
funkcija, ki uporablja funkcijo header , ki po vrsti, natisne lokacijo
debelega črevesa in nato URL na katerega želite zavrniti uporabnika.
Čeprav nisi videl 302 eksplicitno, da je tisto, kar PHP
bi čudežno vstaviti kot glava kaj natančno je tam dejal Rob -
najti.
Ampak gre tu namesto tega.
>> ROB Bowden: OK.
Kaj pa 403 tako prepovedano?
>> PUBLIKA: Mislim, da je to strežnik je v bistvu pravi, da stranka
ne morejo dostopati do domače strani.
>> ROB Bowden: Torej, ja.
No, tipičen odgovor smo Pričakujemo, je nekaj takega, kot so datoteke
ustrezno ne chmodded.
To je verjetno v kakšnih okoliščinah ste jih videli.
Vendar pa obstaja razlog, da stranka bi lahko bila kriva tukaj.
Tam je pravzaprav ena koda stanja -
401.
To so zelo podobni.
>> 401 je nedovoljena.
In 403 je prepovedana.
In tako nepooblaščeno ste izključno dobili, če niste prijavljeni
Ampak prijavi lahko pomeni da ste pooblaščeni.
Ampak, če ste že prijavljeni in vam še vedno nimajo dovoljenja, nato pa
lahko dobite tudi prepovedano.
Torej, če ste prijavljeni in nimate dovoljenje, prepovedana je tudi
nekaj, kar lahko dobiš.
>> DAVID J. Malan: In mehanizem, ki ga ki ti problemi so ponavadi
rešiti na strežniku je po katerih ukaz?
Chmod, če je to res, a dovoljenja izda na datoteko ali imenik.
>> ROB Bowden: Potem pa 404 ni bilo mogoče najti.
Ja.
Torej, za razliko od 302, če ni bil ravno kje ste asking, vendar pa ne ve, kaj
hočeš, to, da ima samo ne vem, kaj hočeš.
In ti se ne zahteva Nekaj ​​veljavna.
418 sem čajnik in nato 500 notranji strežnik.
Torej, zakaj bi si ga dobil?
>> Torej segfault -
Pravzaprav ne vem, razvrščanje standard za to.
Toda, če je vaš PHP code imel nekaj narobe v njej, v teoriji, bi lahko
dejansko segfault, v tem primeru je to 500 Notranja napaka strežnika, nekaj
je narobe s vaš strežnik je konfiguracija.
Ali pa je napaka skladnje v vašem PHP kodo.
Ali nekaj slabega se dogaja.
>> DAVID J. Malan: Nismo videli segfault Med odgovori nekaj ljudi.
In tehnično, bi se lahko zgodilo.
Toda, da bi PHP, program z drugimi ljudmi napisal, dejansko
segfaulted, ki le, če ti ljudje zasral in napisal hroščat kodo
njihov tolmač bi PHP sama segfault.
Torej, čeprav 500 je kot segfault v duhu, to je skoraj vedno
posledica izdaje konfiguracijo datoteke z vašega spletnega strežnika ali, kot je dejal Rob,
napaka skladnje, kot si ti ni zaprl ponudbo.
Ali ste izgubili podpičjem nekje.
>> PUBLIKA: Torej, za Shuttle pset sem mislim, ko sem to naredil, ko sem kliknil
brskalnik, vendar ni bilo nič gor, tisto, kar se imenuje bela stran.
Vendar je bilo zaradi kode.
Mislim, da je JavaScript, kajne?
>> ROB Bowden: Ja.
>> PUBLIKA: Bi to napako Še vedno prišel gor?
>> ROB Bowden: Torej ti ne bi dobila ta napaka, ker je vse
z vidika spletnega strežnika je popolnoma v redu.
Ampak ste zahtevali index.html.
Zahtevali ste shuttle.js in service.js.
In je bilo uspešno vrnitev da vas vse te stvari -
200.
OK.
To je samo takrat, ko vaš brskalnik skušal razlagajo JavaScript kodo, ki
To je kot, čakaj, to ni veljavna napaka JavaScript.
Še kakšno vprašanje?
Vse je v redu.
>> DAVID J. Malan: Torej, naslednjič se je število 11.
In 11 je bil najstrašnejši Za veliko ljudi.
Torej, najbolj pomembna stvar, ki sem seznanjen je, da je to res, o
dvojno povezani seznam.
Vendar to ni bila ista kot lani je dvojno povezani seznam problem,
ki vam ni dal opozorilo, da Seznam bi lahko, v resnici, lahko razvrščeni.
>> Torej dejstvo, da je bil seznam unsorted in dejstvo, da je bila ta beseda
poudarili smo tam mišljeno, da gre da je to pravzaprav poenostavitev
kaj bi bilo drugače bolj zahtevna problem
in več po enega.
Tako je bila pogosta napaka tukaj, da bi dal lanska rešitev na vašem enega
pager in nato le slepo kopijo, ki Kot odgovor, ki je prav
odgovoriti na drugo vprašanje pisane v duhu.
Vendar razlik tukaj so bili naslednji.
>> Torej ena, smo vozlišče prijavljeni in definirana v običajnem tukaj.
Potem smo določili seznam je globalna kazalec inicializiran na null.
Potem je očitno, da je obe funkciji imamo prototipov tukaj, vložek
in odstranite.
In potem imamo nekaj vzorčno kodo tukaj delaš kup vstavki.
In potem vas prosimo, da izpolnite izvedba vložka spodaj v kot
tako da vstavlja n v seznamu V enakem času, je tudi poudaril,
tudi če je že prisotna.
>> Tako lepoto, da lahko vstavite V enakem času, je, da to pomeni
da boste morali vstaviti novo vozlišče, kjer?
V sprednji.
Tako da odpravlja na srečo, vsaj eden od primerov, ki se uporabljajo, da zahtevajo
še več vrstic kode, kot je to storila lani in celo v razredu, ko smo
govoril skozi te stvari z ljudmi in z nekaterimi
verbalno pseudo kodo.
Torej, v raztopini tukaj, kaj je preskočil da se da samo, da imajo vizualni
zaslon.
>> Opazimo, da delamo naslednje.
In opazili tudi druge poenostavitve je bil, da tudi če je
že prisoten, tako da to pomeni, čeprav Številka je že tam, si lahko
le slepo vstavite drugo kopija.
In tudi to je bilo mišljeno, da bo poenostavitev, tako da si lahko
osredotočiti, res, nekateri bolj intelektualno zanimiv del in
Ne samo nekatere dodatne preverjanje napak glede na omejen čas.
>> Torej, v tej raztopini vzorca, smo dodeli kazalec na levem
drugo stran tukaj vozlišče.
Zdaj, zavedati, da kazalec, saj Rob je dejal, je le 32 bitov.
In dejansko ne vsebujejo Naslov dokler vas
mu dodelite naslov.
In mi, ki na desni strani strani preko malloc.
Kot dober državljan, da preverimo, da malloc ni v bistvu nič, tako da
ne bomo slučajno ustvariti segfault tukaj.
In kadarkoli boste uporabili malloc v življenju, vam bi bilo treba preverjanje null, da ne
imate subtilno napako.
>> Potem smo inicializacijo to null jih dodeljevanje n in prejšnje in naslednje.
In v tem primeru sem, inicializirana Predhodna za nično, ker ta nova
vozlišče se bo nova začetek mojega seznama.
Tako da se bo nič pred njim.
In hočem, da v bistvu priložila Obstoječi seznam na novo vozlišče, ki ga
Naslednja nastavitev je enaka, da se seznam.
Ampak ne bom naredil samo še.
Torej, če Seznam sama že obstajala, in je bil vsaj eno vozlišče
že v veljavi, če je ta seznam sem in vstavite novo vozlišče sem,
morali zagotoviti, da je moj nekdanji vozlišče poudarja nazaj na mojo novo vozlišče
ker je to spet dvojno povezani seznam.
>> Torej, naredimo pregled razumnosti.
Če seznam ni nična, če pa je že enega ali več vozlišč tam, potem
Dodajajo, da nazaj sklicujejo tako rekoč.
In potem zelo zadnja stvar, ki jo potrebujemo storiti, je dejansko posodabljati univerzalen
spremenljivka Seznam sama s točko do tega novega vozlišča.
Ja.
>> PUBLIKA: V kazalca puščice [Neslišno] enaka nič, ne da
Ukvarjamo se s seznama, ker Seznam je nična?
>> DAVID J. Malan: Nope.
To je preprosto zato ker sem proaktivno previdni, ker če je to my
Prvotni seznam z morda nekaj več vozlišč tukaj in sem vstavljanje my
novo vozlišče tukaj, tam se dogaja da ni nič tukaj.
In želim, da zajame to idejo z določitvijo prejšnja k
nično na novo vozlišče.
In verjetno, če je moja koda pravilna in ni druge poti, da vstavite
razen te funkcije vozlišča, verjetno, čeprav seznam že
enega ali več vozlišč v njem, verjetno Seznam, prvo vozlišče, bi morali
Predhodna kazalec null sama.
>> PUBLIKA: In samo nadaljevanje.
Razlog si dal kazalec naslednjih Rezult Seznam se delaš kazalec
Pred Seznam v tem, da je obrnjena za naslednjo, mislim -
Ne vem -
samo našteva?
>> DAVID J. Malan: Točno tako.
In tako da je dejansko menijo, dva primera Tukaj res, čeprav
Da jih bomo upoštevati ne povsem enako kot koda.
Toda na visoki ravni, če to predstavlja seznam in to je 32-bitni
kazalec, najenostavnejši scenarij da je ta nična privzeto.
In domnevam, da želite vstaviti Številka 50 je bila prva številka.
Torej, jaz grem naprej in dodeliti vozlišče, ki bo vsebovala
tri področja -
n, prejšnje in naslednje.
>> Bom dal številko 50 tu, saj bo to n.
To bo naslednji.
In to bo prejšnja.
Pa kaj naj storim v tem primeru?
No, pravkar sem naredil linijo 1 tukaj.
Pointer n postane n.
Jaz pa pravim, prejšnja naj bi dobili nič.
Torej, to se dogaja, da je nična.
Potem bom rekel next bo dobil seznam.
>> In to preprosto deluje dobro izteklo.
To je nična.
In zato pravim, novo vozlišče je naslednja Polje naj bi se ne glede na to.
Tako da se postavlja drugo null tam.
In potem zadnja stvar Jaz se preveri tukaj.
Če seznam ni enaka NULL, vendar je enaka null, zato smo preskočili, da
celoti.
In tako vse, kar sem naredil, je naslednji seznam dobi kazalec, ki slikovno posledico
sliko, kot je ta.
Tako da je en scenarij.
>> In tisti, ki ste bili sprašuje o posebej je situacija, kot je ta,
kjer že imamo seznam na enem vozlišča.
In če se vrnem v izvirniku Problem izjavo, zraven bova
vstaviti recimo je 34, samo za Zaradi razprave.
Torej bom samo priročno pripraviti, da sem.
Pravkar sem malloced.
Denimo sem preverjanje za nično.
>> Zdaj bom za inicializacijo n biti 34.
In to bo n.
To bo naslednji.
In to bo prejšnja.
Naj bo prepričan, da ni storil to dobil nazaj.
Prejšnja na prvem mestu v definiciji.
Dovolite mi, da to popravimo.
To je od prejšnje.
To je naslednji.
Čeprav sta enaka, Igrajno dosledni.
>> Prejšnja.
To je naslednji.
Tako da sem samo malloced moje sporočilo, preveri za nično, dodeljena 34 v vozlišče.
Prejšnja postane nična.
Tako, da mi daje to.
Naslednja dobi seznam.
Torej seznam je to.
Torej je to enako, kot je zdaj risanje to s puščico, tako da se točka enem
v enaki.
In potem sem samo preverjam, če seznam ni enaka null.
In to ne tokrat.
Potem bom naredil seznam Predhodna postane kazalec.
>> Torej seznam Prejšnji dobi PTR.
Torej, to ima za posledico dajanje grafični arrow tukaj.
In to je že malo valovita, črte.
In potem, končno, sem posodobiti Seznam opozoriti na kazalec.
Torej, zdaj to kaže s tem tipom.
In zdaj, kaj je naredil hitro Preverjanje sanity.
>> Tukaj je seznam, ki je Globalna spremenljivka.
Prvo vozlišče je res, 34, ker Sledim to puščico.
In to je res, ker želim vstaviti na začetku seznama
vsa nova vozlišča.
Njegov naslednji polje me pripelje do tega tipa.
Če jaz nadaljujem, sem udaril naslednji je nična.
Torej ni več seznama.
Če sem udaril prejšnje, dobim nazaj, kjer sem pričakoval.
>> Torej, še vedno je nekaj nasvetov, očitno je, da manipulira.
Toda dejstvo, da si povedal, da ne ta v enakem času vam pomeni le,
imajo končno število stvari ste dovoljeno storiti.
In kaj je ta številka?
Morda bi bilo za en korak.
Morda bi bilo dva.
Morda bi bilo 1000 korakov.
Ampak to je neskončna, kar pomeni, da ne more so vse vrste petlji dogaja
tukaj, brez rekurzije, brez zank.
To je pravkar dobil, da je težko kodirane-linije kode, kot jo imamo v tem vzorcu.
>> Torej nam Naslednji problem 12 zahteva, da zaključi izvajanje nedosegljive
spodaj na tak način, da so odstranjeni n s seznama v linearnem času.
Tako da boste imeli malo več Vrckanje sobo.
Lahko pa sklepamo, da n, če je prisoten na seznamu, bo prisoten
ne več kot enkrat.
In da je tudi mišljeno, da se na osnovi kviz- poenostavitev predpostavka, da
da če dobiš številko 50 nekje na seznamu, vam ni prav
skrbeti še naprej Ponovil, ki išče vse mogoče
Kopijo 50, ki naj bi bili samo prenesejo v nekaterih minucijo v omejenem času.
>> Torej s nedosegljive, tale je definitivno bolj zahtevna in bolj
Koda za pisanje.
Toda na prvi pogled, odkrito povedano, bi bilo poglej prepričljivo in kot nekaj
ni načina, da bi lahko imeli pripravi na kviz.
Če pa se osredotočimo na posamezne korake, Upajmo, da bo to nenadoma
gane, da je vsak od teh posameznih korakov naredi očitno smisel
V retrospektivi.
Torej, kaj si poglejmo.
>> Torej, najprej smo inicializacijo kazalec da bi se seznam.
Ker želim linearni čas, da se sredstva Bom nekaj zanko.
In skupno pot za ponovitev čez vozlišča v strukturi seznama ali kakršnokoli
konstrukcije je iterativno sprejeti kazalec na sprednji strani podatkov
Struktura nato pa šele začetek posodabljanje je in hodi svojo pot
s podatkovno strukturo.
Tako bom naredil točno to.
>> Medtem ko je kazalec, moja začasna spremenljivka, ni enaka null, dajmo
pojdi naprej in preverite.
Sem imel srečo?
Je polje n v vozlišču sem trenutno gledamo na enak
Številka iščem?
In če je tako, dajmo nekaj narediti.
Zdaj, to opazila pogoj obdaja celoten
Naslednje vrstice kode.
To je edina stvar, ki me skrbi - poiskati številko v vprašanju.
Torej ni nobenega drugega, ki poenostavlja Stvari konceptualno malo.
>> Ampak zdaj sem spoznal, in boste morda morali samo to spoznal po tem, ko razmišljate
je skozi nekaj, tam je pravzaprav dva primera tukaj.
Eno je, če je vozlišče na začetku seznama, ki je
malo siten, ker je to poseben primer, saj imate za reševanje
s to stvarjo, ki je samo anomalija.
Povsod drugje v seznamu, to je ista stvar.
Tam je prejšnje vozlišče in naslednja vozlišče, prejšnje vozlišče, poleg vozlišče.
Ampak ta tip je malo posebna če je on na začetku.
>> Torej, če kazalec enak seznam sam, tako da če sem na začetku
seznam in sem ugotovila, n, moram narediti nekaj stvari.
Ena, moram spremeniti seznam opozarjajo na naslednje polje, 50.
Torej predvidevam, da sem poskušal odstraniti 34.
Torej, ta fant mora iti stran čez nekaj trenutkov.
>> Tako bom rekel, seznam postane kazalec naslednji.
No, to je kazalec.
Naslednja kaže tukaj.
Torej se to spreminja to puščico pravice Zdaj kaže na ta fant tukaj.
Zdaj se spomnite, smo začasna spremenljivka.
Torej nismo izgubili starše nobenih vozlišč, ker imam tudi tega tipa v moji
Izvajanje nedosegljive.
Torej, zdaj, če seznam sama po sebi ni nič, Moram popraviti nekaj malega.
>> Moram zdaj prepričati, da je to puščica, ki je prej obrnjena
50-34, ima to oditi, ker če sem poskušal znebiti
od 34, 50 je bolje ne ohranijo vse nekako nazaj sklic nanjo kot
arrow predlagal.
Tako da sem naredil to linijo.
Torej sem naredil.
Ta zadeva je pravzaprav zelo enostavna.
Sekal glave seznama je dokaj preprosta.
>> Na žalost pa je to nadležno drugega bloka.
Torej, zdaj imam, da bo zadevo kjer je nekaj v sredini.
Ampak to ni preveč grozno, razen za sintakso, kot je ta.
Torej, če nisem na začetku Seznam, jaz sem nekje na sredini.
In ta tukaj je rekel, start na kateri koli vozlišče ste na.
Pojdi na prejšnjega vozlišča naslednje polje in poudarjajo, da je na kazalec.
>> Naredimo to slikovno.
To je že zapleteno.
Torej, če imam prejšnjo polja tukaj - dajmo - Naslednja polja tukaj.
Bom poenostaviti svoje kazalce in ne kot pripravi cel kup
stvari naprej in nazaj križanje seboj.
In zdaj, recimo, to je 1, 2, 3 zaradi razpravo, čeprav
čeprav to ne poravnajo z problem v vprašanju.
>> Torej, tukaj je moj povezani seznam.
Jaz sem poskušal odstraniti dva, v tem Zlasti različica zgodbe.
Tako sem posodobljena kazalec se kaže s tem tipom.
Torej, to je PTR.
On je obrnjena tukaj.
To je seznam, ki obstaja na svetovni ravni kot prej.
In on je poudaril tukaj ni važno kaj.
In zdaj, bom poskušal odstraniti dva.
>> Torej, če je kazalec kaže sem, da sem bodo sledili, očitno,
Predhodna kazalec, ki me postavlja na 1.
Jaz pa bom rekel, da je naslednja področje, ki me pripelje čez to
škatla tukaj, se bo enako kazalec naslednji.
Torej, če je ta kazalec, to je naslednji.
To pomeni, da je ta puščica potrebe poudariti, da tega tipa.
>> Torej, kaj ima ta vrstica kode pravkar storjeno je malo tega.
In zdaj, to je videti kot korak v pravo smer.
Mi v bistvu želite snip 2 out od sredine 1 in 3.
Zato je smiselno, da želimo Pot tega kazalca okoli njega.
Torej je to naslednja vrstica preverjanje, če kazalec Naslednja ni nič, pa je
res nekdo s pravico do 2, to pomeni, da moramo tudi storiti
mulo tu.
>> Tako da sem zdaj treba upoštevati ta kazalec in posodobiti prejšnje kazalec na
ta človek narediti malo obidite tukaj točko tukaj.
In zdaj, vizualno je to lepo.
To je grdo, da obstaja nihče ne kaže na 2. anymore.
2 kaže v levo.
In 2 se kaže v desno.
Vendar pa lahko počne kar hoče, saj on je na tem, da se osvobojeni.
In ni važno, kaj te vrednosti so anymore.
>> Kar je pomembno, je, da preostali Fantje so usmerjanje zgoraj
in pod njim.
In res, da je tisto, kar počnemo zraven.
Mi brezplačno kazalec, kar pomeni, da povemo operacijski sistem, ste dobrodošli
za povrnitev tega.
In potem na koncu vrnemo.
Sicer implicitno, če bomo še niso vrnili,
moramo, da je videti.
Torej kazalec znaša kazalec zraven samo pomeni premik tega tipa tukaj.
Premakniti tega tipa tukaj.
Premakniti tega tipa tukaj, če v resnici, nismo našli številko
iščemo še za.
>> Torej odkrito, je popolnoma zgleda velika, mislim, sprva
pogled, še posebej, če si prizadevale s tem v kvizu potem videli
kaj takega.
In ti pat sebe na hrbtni strani.
No, ni načina, da bi lahko imela prišli do, da je na kvizu.
Ampak jaz bi trdijo, da lahko, če ste odmor pa dol v teh posameznih
primerih in le sprehod skozi to previdno, čeprav, priznam, pod
stresne okoliščine.
>> K sreči, slika je vse srečnejši.
Lahko bi to pripraviti v poljubno število načinov.
Vam ni treba storiti križanje stvar tukaj.
Lahko bi to naredil z ravnimi linije je to všeč.
Ampak bistvo tega problema, v splošno je zavedati, da
Slika na koncu je treba pogledati malo kaj takega, saj
konstantna čas je pomenilo, da boste obdržali motenje in motenje in motenje
nova vozlišča na začetku seznama.
Vsa vprašanja?
Verjetno najbolj izzivalne zagotovo kodiranje vprašanja.
>> PUBLIKA: Torej je seznam podobna glavo v prejšnjih primerih.
>> DAVID J. Malan: Točno, točno.
Samo drugačno ime za Globalna spremenljivka.
Po vsem svetu, kaj?
>> ROB Bowden: OK.
Torej, to je tista, v kateri ste moral napisati odstavek.
Nekateri ljudje pisal eseje za to vprašanje.
Vendar si morate za uporabo teh šest izraze opisati, kaj se zgodi, ko
poskusite, da se obrnete facebook.com.
Tako da bom samo govoriti skozi proces uporabo vseh teh izrazov.
Torej v našem brskalniku vpišemo facebook.com in pritisnite tipko Enter.
Torej naš brskalnik bo za izgradnjo HTTP zahteva, da se dogaja, da pošljete
skozi neki proces na Facebook za Facebook, da se odzove na nas s
HTML njegove strani.
>> Torej, kaj je proces, ki ga ki zahteva HTTP
dejansko dobi na Facebooku?
Torej, najprej moramo prevesti Facebook.com.
Torej samo zaradi imena Facebook.com, kjer v resnici počne zahtevka za HTTP
morali iti?
Zato moramo prevesti Facebook.com na IP naslov, ki enolično
opredeljuje, kaj stroj smo dejansko želite poslati to zahtevo.
Vaš laptop je IP naslov.
Kaj povezan z internetom ima naslov IP.
>> Torej DNS, Domain Name System, ki je kaj se dogaja za ravnanje prevod
iz facebook.com na IP naslov, ki si dejansko želijo stopiti v stik.
Tako smo v stik DNS strežnikov in recimo, kaj je facebook.com?
Piše, oh, to je IP naslov 190,212 Nekaj, nekaj, nekaj.
Vse je v redu.
Vem, kaj stroj Želim, da se obrnete.
>> Torej, potem pošljite vašo zahtevo HTTP več na tem računalniku.
Torej, kako priti do tega stroja?
No, prošnja gre od usmerjevalnikih odbijal.
Spomnimo se primera v razredu, kjer smo dejansko videli pot, ki
paketov je, ko smo poskušali za komuniciranje.
Videli smo, da skok čez Atlantik Ocean na eni točki ali karkoli.
>> Torej zadnji izraz pristanišče.
Torej, to je zdaj na vašem računalniku.
Lahko imaš več stvari, ki so trenutno komunikacijo z internetom.
Tako da se bom lahko teče, recimo, Skype.
Morda imam spletnega brskalnika odprto.
Morda imam nekaj, torrenting datotek.
Torej, vse te stvari so komuniciranje z
internet na nek način.
>> Torej, ko računalnik prejme nekaj podatkov iz interneta, kako se to počne
vem, kaj aplikacija dejansko želi podatke?
Kako to vem, ali je to predvsem Podatki so namenjene
torrenting vloge, v nasprotju je spletni brskalnik?
Torej je to namen pristanišč v tem, da vse od teh vlog imajo
trdila, da so vrata na vašem računalniku.
Torej, vaš spletni brskalnik pravi, hej, Jaz sem posluša na vratih 1000.
In tvoj torrenting Program je rekel, Jaz sem posluša na vratih 3000.
Skype in pravi, sem z vrati 4000.
>> Torej, ko boste dobili nekaj podatkov, ki pripada na eno od teh vlog, podatke
je označena s katerimi pristanišča je dejansko je treba poslati skupaj s.
Torej, ta pravi, oh, spadam v pristanišče 1000.
Vem pa moram, naj to skupaj z mojo pomočjo spletnega brskalnika.
Torej razlog, da je tukaj pomembno je, da spletni strežniki ponavadi
poslušate na vrata 80.
Torej, ko se obrnem, Facebook.com, sem komunikaciji z nekaterimi stroju.
Ampak moram reči, katera vrata, ki Stroj Želim komunicirati s.
In spletnih strežnikov so ponavadi posluša na vratih 80.
>> Če bi hoteli, bi ga lahko nastavite navzgor, tako da našteva kot na vratih 7000.
In nato v spletnem brskalniku, bi lahko ročno vnesite Facebook.com: 7000 k
poslati zahtevo za vrata 7000 spletnega strežnika na Facebooku.
>> DAVID J. Malan: In v tem primeru, tudi čeprav mi ni zahtevala, da se ljudje
omenjam, v tem primeru, kaj port bi zahteva dejansko šel za?
Poskusite znova.
Točno tako.
Ne išče, ampak subtilnost da je tam nihče zadnja.
>> ROB Bowden: Torej HTTPS, saj je poslušanje posebej za
šifrirani, je na vratih 4430.
>> Ciljna publika: in e-pošte so 25, kajne?
>> DAVID J. Malan: Outbound elektronske pošte, 25, ja.
>> ROB Bowden: Sploh ne vem, večina - vse nižjih ponavadi
rezervirano za stvari.
Mislim, da je vse pod 1024 je rezervirano.
>> PUBLIKA: Zakaj si rekla 3 je bila napačna številka?
>> ROB Bowden: Ker v IP naslova, tam je štiri skupine številk.
In oni so od 0 do 255..
Torej 192.168.2.1 je skupni lokalnega omrežja IP naslov.
Opazili vse tiste, manj kot 255..
Torej, ko sem začel z 300, ki verjetno ne bi imela
bil eden izmed številk.
>> DAVID J. Malan: Ampak to neumno clip od - je to CSI, kjer so imeli
številko, ki je bila prevelika IP-naslova.
>> ROB Bowden: kakršna koli vprašanja o tem?
Naslednjič, tako popolna sprememba topic, ampak imamo to PHP array za
hiše v quad.
In imamo neurejen seznam.
In želimo natisniti vsak element seznama Pravkar vsebuje ime hišo.
Torej imamo foreach zanke.
Torej, ne pozabite, sintaksa je foreach matrika kot elementa v matriki.
Torej prek vsaki ponovitvi zanke, Hiša se dogaja, da na eni od
Vrednosti znotraj matrike.
>> Na prvi ponovitvi hiše bo Cabot House.
Na drugi ponovitvi, hiša bo biti Courier House in tako naprej.
Torej za vsak quad kot doma, smo le, da bo tiskanje -
lahko bi tudi ponovil -
element seznama in nato ime hišo je in zaprite element seznama.
Zaviti oklepaji so neobvezne tukaj.
>> In potem smo rekli tudi v vprašanju sama po sebi, ne pozabite, da zaprete
Neurejen seznam tag.
Zato moramo za izhod PHP način da bi to naredili.
Ali smo lahko odmevalo zapri neurejen seznam tag.
>> DAVID J. Malan fino Tudi tukaj bi so bili uporabiti staro šolo
zanka z $ i = 0 0 in uporabo knezov do ugotovimo dolžino žarka.
Tudi povsem v redu, samo Malo wordier.
>> PUBLIKA: Torej, če ste bili, da bo [Neslišno], bi naredil -
Sem pozabil, kaj zanka [neslišno] je.
Bi $ quad nosilec i?
>> DAVID J. Malan: Točno tako.
Ja, točno.
>> ROB Bowden: Še kaj drugega?
>> DAVID J. Malan V redu.
Kompromisi.
Tako je bilo grozde odgovorov je lahko vsaka od teh.
Mi smo res samo iščejo nekaj prepričljivih za navzgor in
negativna.
In številka 16 vprašal, potrjevanje uporabnikov strani odjemalca vhod, tako kot pri JavaScript,
namesto na strani strežnika, tako kot pri PHP.
Torej, kaj je narobe z početje client-side?
>> No, ena od stvari, ki smo jih predlagali, je da boste zmanjšali latence, ker vam
ne bi bilo treba ukvarjati stik strežnik, ki lahko traja nekaj
milisekund ali celo nekaj sekund, ob izogibanju in samo
potrjevanje vhodni strani odjemalca uporabnikov s proženje trener na oddajo in je
Samo preverjam, ali pa vnesite nekaj v za ime?
Ali so kaj vpisali v za e-poštni naslov?
Ali pa izberite domu od spustnem meniju?
>> Lahko jim trenutne povratne informacije uporabo GHz računalnik
ali karkoli so, da je dejansko na njihovi mizi.
Torej je to samo bolje uporabnik doživite tipično.
Ampak slaba stran početje odjemalsko validacija, če to storite, ne da bi tudi
početje preverjanje s strani strežnika je, da Najbolj kdo prihaja iz CS50 ve
da lahko samo pošlje vse podatke, ki jih želite s strežnikom poljubno število načinov.
Odkrito povedano, v večini kateremkoli brskalniku, lahko kliknite okrog v nastavitvah in samo
izklopite JavaScript, ki bi Zato, onemogočiti vsakršno obliko
potrjevanje.
>> Ampak tudi vi se verjetno spomnite, da sem celo naredil nekaj Skrivnosten stvari v razredu z uporabo
telnet in dejansko se pretvarja, da se brskalnik s pošiljanjem get
Zahteva za strežnik.
In to zagotovo ni uporabo katere koli JavaScript.
To je samo jaz tipkanje ukazov na tipkovnici.
Torej res, vsak programer v dovolj udobje s spleta in HTTP
lahko pošljete karkoli podatki on ali ona želi na strežnik brez potrditve.
In če vaš strežnik ne tudi preverjanje, pa se mi je ime, je
to dejansko veljaven e-poštni naslov, kajne jih izberejo domu, boste morda na koncu
up vstavljanje lažne ali pa samo prazen podatki v zbirki podatkov, kar je verjetno
se ne bo dobro, če ste bili ob predpostavki, da je tam.
>> Torej je to nadležno realnost.
Ampak na splošno, na strani odjemalca Validacija je super.
Ampak to pomeni dvakrat toliko dela.
Čeprav je naredil obstajajo različne knjižnice, Javascript knjižnice za
na primer, da bi to veliko, mnogo manj glavobolov.
In lahko ponovno nekaj kode na strani strežnika, na strani odjemalca.
Vendar se zavedajo, da je to običajno dodatno delo.
Ja.
>> PUBLIKA: Torej, če smo pravkar je dejal, manj varen -
>> DAVID J. Malan: [smeh]
Ugh.
Tisti, ki so vedno težje tisti, odločati.
>> ROB Bowden: To bi bilo so bile sprejete.
>> DAVID J. Malan: Kaj?
>> ROB Bowden: Ustvaril sem ta problem.
Da bi bili sprejeti.
>> DAVID J. Malan: Ja.
>> PUBLIKA: Cool.
>> ROB Bowden: Ampak nismo sprejeli za prvo -
dobro, kar smo iskali, je nekaj podobnega tebi ne bi bilo treba
komunicira s strežnikom.
Nismo sprejeli samo hitrejši.
>> PUBLIKA: Kaj pa ne osvežite stran?
>> ROB Bowden: Da.
To je bil sprejet odgovor.
>> DAVID J. Malan: Karkoli, kjer smo menili, da je bolj verjetno, kot verjetno ne bo
da boste vedeli, kaj ste bili rekel, kar je težko
linija za izdelavo včasih.
Namesto z uporabo povezani seznam z matriko za ohranitev
razporejene seznam števil.
Torej glavo pogosto navajajo s povezano sezname, ki so spodbudili njihovo celotno
Uvedba je bila dobiš dinamičnost.
Lahko zrastejo.
Ti lahko skrči.
Torej vam ni treba, da skoči skozi obroče dejansko ustvarjajo več pomnilnika
s paleto.
Ali pa nimajo samo pravijo, žal, uporabnik.
Niz se napolni.
Torej, dinamična rast seznama.
Negativna, čeprav povezanih seznamov?
>> PUBLIKA: To je linearna.
Iskanjem na povezanem seznamu je linearna namesto da bi tisto, kar se prijavite
>> DAVID J. Malan: Točno tako.
Iščejo na povezanem seznamu je linearna, tudi če je to urejeno, saj lahko
Samo sledite tem krušne drobtine, ti kazalci, od začetka seznama
do konca.
Ne, ne moreš vzvod bralno in, Tako, binarno iskanje, tudi če je
razporejene, da si lahko storite s paleto.
In tam je tudi dodaten strošek.
Ja.
>> PUBLIKA: Memory neučinkoviti?
>> DAVID J. Malan: Ja.
No, jaz ne bi nujno pravijo neučinkovito.
Ampak to vas bo stalo več pomnilnika, ker morate 32 bitov za vsak
vozlišče za dodatno kazalca, na vsaj za posamezno povezani seznam.
Zdaj, če ste shranjevanje le cela števila in dodajate kazalec, da je
pravzaprav nekako nepomembno.
To je podvojila količino pomnilnika.
Toda v resnici, če ste shranjevanje povezani seznam konstruktov, ki imajo lahko
8 bajtov, 16 bajtov, še bolj kot to, morda je manj
v zelo nizki ceni.
Ampak to je strošek vseeno.
Torej, eden od tistih, ki bi si bil lep, kot slabosti.
>> 18.
Uporaba PHP namesto C, da napišete Program ukazni vrstici.
Torej tukaj, je pogosto hitrejši za uporabo jezik kot PHP ali Ruby ali Python.
Ti samo hitro odpreti up urejevalniku besedil.
Imate veliko več funkcij so vam na voljo.
PHP ima pomivalno korito funkcij, ker je v C, ga
imajo zelo, zelo malo.
Dejstvo je, fantje vedo, na težji način da nimate hash tabel.
Niste mi povezane sezname.
Če želite, da tiste, ki jih imajo na jih izvajajo sami.
>> Tako je eden glavo PHP ali res vse razlagati jezik je hitrost
, s katerim lahko pišete kodo.
Ampak slaba, bomo to videli, ko sem hitro podžigal misspeller
Izvajanje v predavanju z uporabo PHP, je da je uporaba razlagati jezik
navadno počasnejši.
In videli smo, da je dokazljivo z povečanje v času od 0,3 sekunde do 3
sekund, zaradi razlage da se dejansko dogaja.
>> Druga glavo je bil, da vam ne bi bilo treba prevesti.
Tako je tudi pospeši razvoj mimogrede, ker nimate
dva koraka za vodenje programa.
Moraš eno.
In tako, da je precej prepričljiv, kot dobro.
Uporaba SQL baze podatkov, namesto CSV datoteko za shranjevanje podatkov.
Torej SQL baza podatkov za pset7.
CSV niste uporabili veliko.
Ampak jo uporabljamo posredno v pset7 kot tudi s pogovori z Yahoo Finance.
>> Vendar CSV je tako kot Excelove datoteke, vendar super enostavna, kjer so stebri
Samo demarked z vejicami znotraj ki je sicer besedilno datoteko.
In z uporabo baze podatkov SQL je malo bolj prepričljivi.
To je narobe, ker ste dobili stvari kot izbiro in vstavljanje in brisanje.
In dobiš, domnevno indekse, ki MySQL in drugih zbirk podatkov, kot so
Oracle, graditi za vas v spomin, ki pomeni, da vaša izberite verjetno ni
bo linearna zgoraj navzdol.
To se dejansko dogaja, je nekaj kot binarni iskanju ali kaj podobnega
pisane v duhu.
Torej, oni so običajno hitreje.
>> Ampak slaba stran je, da to je samo več dela.
To je več truda.
Morate razumeti podatkovnih baz.
Moraš ga je ustanovil.
Strežnik potrebujete za vožnjo da je baza podatkov o.
Morate razumeti, kako ga nastaviti.
Torej, to so le ti vrste kompromisov.
Ker je datoteka CSV, lahko ga ustvarili z gedit.
In ste na dobri poti.
Ni kompleksnost dlje.
>> Uporaba Trie namesto razpršene tabele z Veriženje za shranjevanje
slovar besed, ki spominjajo od pset5.
Tako poskuša z glavo, v teoriji vsaj, je kaj?
Constant čas, vsaj če ste razpršitev na vsako posamezno
črke v besedi, kot ste vi morda za pset5.
Da bi bilo pet, šest znakov # hashes če obstaja pet ali šest
črke v besedi.
In to je zelo dobro.
In če obstaja zgornja meja o tem, kako Dokler lahko vaše besede lahko, da je
res asimptotično konstantna čas.
>> Ker je razpršena tabela z ločeno veriženje, problem je s tem
vrsta podatkovne strukture je, da uspešnost vaših algoritmov običajno
odvisno od števila stvari že v strukture podatkov.
In to je vsekakor velja verige, pri čemer več stvari si dal
v hash tabelo, več tistih, Verige iti, kar pomeni, da v najslabšem
primera, kar vas bo morda iščete je vse tako na koncu ene
od teh verig, ki učinkovito je naloga v nekaj linearno.
>> Zdaj, v praksi, bi bilo popolnoma se zgodi, da hash tabela z
verige je hitrejši kot ustreza Izvajanje Trie.
Ampak to je zaradi različnih razlogov, med ki se poskuša uporabiti cel kup
pomnilnika, ki se v resnici, počasi stvari dol, ker ne boste dobili lepo
Koristi nekaj, kar ti predpomnjenje, kjer se stvari, ki so blizu skupaj
v pomnilnik lahko dostopen pogosto hitreje.
In včasih lahko prišli do res dober hash funkcijo.
Tudi če imate zapravljati malo pomnilnika, boste morda dejansko lahko
našli stvari hitro in ne tako slabo, kot linearno.
>> Torej na kratko, ni bilo nujno, s katero koli od teh eno ali celo dve
posebne stvari, ki smo jih iskali.
Res nič prepričljiva kot pozitivni in negativni
splošno ujete naše oči.
>> ROB Bowden: Torej, za pozitivni, smo ne sprejme sama "hitreje". You
imel za povedati nekaj o tem.
Tudi če ste teoretično hitreje dejal, smo vedeli, da ste nekako razumel
, da je 0 od 1.
In hash tabelo, v teoriji, ni 0 od 1.
Omenjajo ničesar o času izvajanja na splošno imaš točke.
Toda "hitreje", večina rešitev na velika plošča, ki so bili poskuša
objektivno počasneje kot rešitev da so bile razpršene tabele.
Tako hitreje in sama po sebi v resnici ni res.
>> DAVID J. Malan: Dom de dom dom.
Verjetno sem edini, ki se spozna to je, kako naj bi to
se izgovarja, kajne?
>> ROB Bowden: Imel sem pravzaprav nima pojma.
>> DAVID J. Malan: To je Občutek v moji glavi.
>> ROB Bowden: delam tega.
OK.
Torej, to je tista, v kateri ste morali pripraviti diagram podoben tebi morda
videl na zadnjih izpitih.
Torej, kaj je samo pogled na to.
Torej iz HTML vozlišča, imamo dva otroci, glava in telo.
Zato smo se osamosvojiti - glava in telo.
Glava je naslov tag.
Torej imamo naslov.
>> Zdaj pa ena stvar, veliko ljudi Pozabil je, da te besedilne vozlišča
elementi znotraj tega drevesa.
Torej, tukaj se zgodi, da jih pripravijo, kot elipsi za njihovo razlikovanje od teh
Vrste vozlišč.
Ampak obvestilo tudi tu imamo vrh, srednji in spodnji del na koncu pa
besedilo vozlišča.
Torej smemo pozabiti tistih, ki je bila nekoliko skupne napake.
>> Telo ima tri otroke - ti trije divs.
Torej div, div, div in nato besedilo vozlišče otroci teh divs.
To je v bistvu vse v ta vprašanja.
>> DAVID J. Malan: In to je treba omeniti, čeprav ne živijo na teh
podrobnosti v času, ki ga preživimo na JavaScript, da sklep ne, v
Dejstvo, glede na tehnično.
Torej, če glava pride pred telesom v HTML, nato pa bi se izkazalo, da
levo od telesa, v dejanski DOM.
Da njegova je, na splošno, samo v vednost, nekaj, kar se imenuje dokument, da bi, kadar je to
to ne zadeva.
In če ste bili izvedbeni parser, program, ki bere HTML v stavbi
do drevesa v spomin, če sem iskren, to je intuitivno verjetno tisto, kar
narediti vseeno - od zgoraj navzdol, od leve proti desni.
>> ROB Bowden: Vprašanja o tem?
Naj storim naslednjič?
>> DAVID J. Malan: Seveda.
>> ROB Bowden: OK.
Torej je to medpomnilnika napad vprašanje.
Glavna stvar, ki sem prepozna, je, tudi, kako bi lahko nasprotnik trik
ta program v izvršilni naključne kode?
Torej argv1, prvi ukazni vrstici Argument za ta program, ki se lahko
poljubno dolgo.
Ampak tukaj smo, da uporabljate memcpy kopirati argv1, ki je tu bar.
Mi smo to poteka kot argument.
In tako se je pokazal na imenski vrstici.
>> Torej smo memcpying bar v tem pufru C.
Koliko zlogov smo kopiranje?
Pa vendar mnogi bajti bar zgodi, da uporabljali, dolžino te trditve.
Vendar pa c je le 12 bajtov širok.
Torej, če vpišemo argument v ukazni vrstici , ki je daljša od 12 bajtov, smo
bo overflow to Posamezen pufer.
Zdaj, kako bi nasprotnik trik programiranje v izvršilni poljubno kodo?
>> Torej, ne pozabite, da je tu Glavni kliče foo.
In tako je glavna zahteva foo.
Narišimo to.
Torej imamo kup.
In glavna ima sveženj okvir na dnu.
Na neki točki, glavni klici foo.
No, takoj, glavni klici foo.
In tako foo dobi svoj sveženj okvir.
>> Zdaj, na neki točki, foo se bo vrnil.
In je šel foo donose, moramo vedeti, na kakšna vrstica kode znotraj glavnega smo
je bilo, da bi vedeli, kam bi morali nadaljevati v glavnem.
Mi lahko pokličete foo od celote kup različnih krajih.
Kako vemo, kje se vrnete?
No, moramo hraniti, da nekje.
>> Torej nekje tu nekje hranimo , kjer bi se morali vrniti na enkrat
foo vrne.
In to je naslov povratka.
Torej, kako lahko nasprotnik izkoristi to je dejstvo, da
ta buffer c hrani, dajmo pravijo, tukaj je c.
Torej imamo 12 bytov za c.
To je c.
In to je Foo je kup prstan.
Torej, če zlonamerni uporabnik vnese več bajti od 12 ali pa vnesete ukaz
Argument linija, ki je daljša od 12 znaki, nato pa se bomo
preliva te rezerve.
>> Mi lahko nadaljujem.
In na neki točki, gremo daleč Dovolj je, da začnemo
prepisovanju to povratnega naslova.
Torej, ko smo prepisali naslov pošiljatelja, To pomeni, da kadar foo
donosi, smo se vračajo tja, kjer Zlonamerni uporabnik je tako povedal, da ga
ne glede na vrednost, ki jo je začel, ne glede na znaki uporabnik vnese.
In tako, če je zlonamerni uporabnik bi posebej pameten, da lahko imajo ta
vrnitev na nekje v printDef funkcija ali nekje v malloc
Funkcija, samo kjerkoli samovoljno.
>> Še bolj pameten, kaj če ima uporabnik vrne na tukaj.
In potem začneš izvršitve ti kot vrstic kode.
Torej, na tej točki lahko uporabnik vnese karkoli hoče v tej regiji.
In ima popoln nadzor preko svojega programa.
Vprašanja o tem?
Torej naslednje vprašanje je končano ponovno izvajanje Foo tako
da to ni več ogrožena.
>> Torej je nekaj načinov lahko bi to naredil.
Še vedno imamo samo c počutje dolžine 12.
Lahko bi se to spremenilo kot del vaše rešitve.
Dodali smo tudi preverjanje, da bi Prepričajte bar ni bilo nič.
Čeprav vam ni treba da je za popolno kredit.
Tako da smo se prej posvetovali niz dolžine droga.
Če je večja od 12, potem dejansko ne naredite kopijo.
Tako da je eden od načinov za to določitev.
>> Drug način za to določitev je namesto ob c samo dolžine 12, ima
biti dolžina strlen (bar).
Drug način za pritrjevanje je dejansko samo vrnitev.
Torej, če si se rešil vse to, če bi si izbriše vse
vrstic kode, bi gotten polno kreditno, ker te funkcije
dejansko ne uspe karkoli.
To je kopiranje ukazno vrstico argument v neki niz v
njegova lokalna kup okvir.
In potem stvar, ki se vrača.
In ne glede na to doseči, je več.
Torej donos je bil tudi zadostna način za pridobivanje vse zasluge.
>> DAVID J. Malan: Ni čisto duh Vprašanje, ampak sprejemljivo na
spec vseeno.
>> ROB Bowden: Vprašanja o nič od tega?
Ena stvar, ki jo vsaj potrebno, da se sestavljanje kodo.
Torej, čeprav tehnično niste ranljiva, če je vaša koda ne
zbiranje, nismo sprejeti.
Brez vprašanj?
OK.
>> DAVID J. Malan: Želiš torej ta naziv?
>> ROB Bowden: Ne
>> DAVID J. Malan: Torej, v tem enem, to je bodisi dobra novica ali slaba novica.
To je dobesedno isti problem kot prvi kviz.
In to je skoraj enako problem kot pset1.
Vendar je namenoma poenostavljena biti enostavnejši piramide, tista, ki je lahko
rešen z rahlo enostavnejši ponovitev.
In res, kaj smo dobili na Tu ni bilo toliko logike,
ker je verjetno, s tem, da si bolj udobno kot ste bili
V enem tednu z for zanke ali zakaj zank, ampak res, da draži narazen, da
ste malo všeč Ideja, da je PHP ne le o tem, kaj
programiranje.
To je dejansko lahko uporablja kot jezik pisati programe ukazni vrstici.
>> In res, da je tisto, kar smo poskušali opozoriti, da.
To je PHP program za ukazno vrstico.
Torej C koda tod pa pravilna v C, ni pravilen za PHP.
Toda koda res enaka.
Če primerjate rešitve za kviz 0 proti Quiz 1, boste ugotovili, da
to je skoraj identična, razen za nekateri dolar znaki in za
odsotnost vrste podatkov.
Še posebej, če pogledamo tukaj, boste videli, da smo Ponovil je v tem
primer, od 1 do 7 s.
>> Mi bi to lahko storil 0 indeks.
Ampak včasih, mislim, da je samo psihično lažje razmišljati o stvareh,
od 1 do 7.
Če želite en blok, nato pa dva bloki, nato tri, nato
dot, dot, dot sedem.
Imamo pa j inicializiran na 1 in potem računam na največ i.
In vse, kar je tu drugače identična.
Vendar je vredno omeniti, so nekaj stvari.
Mi vam teh dveh linij, to najprej ena, goofily imenovan kot shebang
za oster pok.
In to samo določa pot, mapa, v kateri lahko biti program
je pokazala, da želite uporabiti interpretirati te datoteke.
>> In potem linija po tem, od Seveda, pomeni vstop PHP način.
In črta na dnu pomeni izhod PHP način.
In to deluje, na splošno, z razlagati jezikov.
To je nekako nadležno, če ste napisali Program v datoteki z imenom foo.php.
In potem bodo uporabniki morali samo ne pozabite, OK, za zagon tega programa, sem
morali vnesti "php vesoljske foo.php." Kind siten, če nič drugega.
In to tudi pokaže, da je vaš program je napisan v PHP, ki ni vse
da svetleča za uporabnika.
>> Torej si lahko odstranite. Php skupaj prikličite iz predavanja.
In lahko dejansko narediti. / Foo, če ste ga chmodded tako, da jo
izvršljiv.
Torej bi chmod + x foo storil.
In če ste tudi dodate shebang tukaj.
Ampak res, problem je bil že na tiskanje nekaj takega.
Brez HTML-ja, no C-code gotovo, samo nekaj PHP.
Torej Milo nato vrnil v problem 25.
In v 25., dobili ste naslednjih skelet koda, ki je bila
Precej enostavno spletno stran.
In sočno del HTML-modrih se je znižal tukaj, če imamo v notranjosti telesa
obrazec, ki je edinstven ID vložkov znotraj katerega je dva vhoda, enega
z idejo o imenu, enega z idejo gumb.
>> Prvi je bil tip besedila, Drugi tipa oddate.
In tako smo vam dali, pravzaprav več sestavine, kot bi bilo treba, samo zato,
vidva imela možnosti, s katerimi za rešitev tega problema.
Vi ne nujno potrebujejo vse te ID-jev.
Ampak to vam omogoča, da reševanje je na različne načine.
In na vrhu, opazili, da Namen je bil, da sproži
okno, kot je ta -
Pozdravljeni, Milo! -
pop up v brskalniku uporabo super preprosto, če
ni grda, funkcija Opozarjanje.
In tako je na koncu, to izvira konceptualno nekako poslušate
Trditve strank stranjo obrazca , Ne pa na strani strežnika, nekako
odziv na te trditve, ki jih oprijemalne vrednost, ki jo uporabnik natipkan
pa tudi na področje imenom, nato ga prikazuje v telesu opozorila.
>> Torej en način lahko to storite z jQuery, ki izgleda nekoliko
skladenjsko Zmešati na prvi.
To lahko storite s čisto DOM kode - document.getelement po ID.
Vendar pa si oglejte na tej različici.
Imam nekaj pomembnih črte prvi.
Torej ena, imamo to vrstico, ki je identična, kar ste lahko videli
leta, verjamem, form2.html iz razreda v 9. tednu.
In to je samo rekel, izvršitev Naslednja koda, ko
Dokument je pripravljen.
Ker je to pomembno le zato, ker HTML strani so prebrali na vrh
spodaj, z leve proti desni.
>> In zato, če boste poskušali narediti nekaj v kodi sem, da bi nekaj DOM
element, nekaj HTML tag, ki je navzdol tukaj, ste to počeli prezgodaj,
ker to sploh ni prebrali v spomin.
Torej z besedami, to document.ready linije, smo govorili
Tukaj je del kode, brskalnik.
Ampak ne izvrši, dokler ta v celoti Dokument je pripravljen, da je DOM
obstaja drevo v spomin.
Ta je malo bolj enostavno, če skladenjsko
malo drugačen, kje sem rekel, grab HTML element, katere edinstvena
identifikator vhodi.
To je tisto, kar hash tag označuje, enolični ID.
In potem bom poklical. Oddajte.
>> Torej. Submit tukaj je funkcija, drugače znana metoda, ki je
Notranjost objekta na levem strani pa, da nisem izpostavil.
Torej, če mislite vhodov kot predmet v spomin - in res je.
To je vozlišče v drevesu -
. Submit sredstva, kadar je ta oblika z predloži ta ID, izvršiti
Naslednja koda.
Ni mi mar, kaj ime Funkcija bom izvršitve.
Torej, tukaj sem z uporabo, kot prej, kar je imenovano funkcijo lambda ali
anonimni funkcija.
To sploh ni razumsko Zanimivo, razen da nima imena,
kar je v redu, če ste le kdaj ga pokličete enkrat.
In tam notri sem dejansko ročaj predložitev obrazca.
Sem najprej razglasi spremenljivko imenovano vrednost.
In kaj potem je učinek tega izpostavil del tu?
Kaj naj bi to storili na visoki ravni za mene?
>> PUBLIKA: To dobi vrednost, ki Uporabnik ni storil v HTML spodaj.
To postane ta ID in potem ugotovi vrednost njo.
>> DAVID J. Malan: Točno tako.
To zagrabi vozlišče, katere edinstvena Identifikacijska oznaka je ime.
Da dobi vrednost v njem, ki je verjetno, kaj uporabnik
njega ali sebe tipkal.
In potem ga shrani da v spremenljivka se imenuje vrednost.
Kot prahi, bi lahko imeli tudi to naredil malo drugače.
Popolnoma sprejemljiva nečesa laž var vrednost dobi
document.getElementById.
In to je razlog, zakaj je malo dolgočasno, da ne uporabljajo jQuery.
"Ime". Vrednost.
Torej povsem sprejemljiv.
Različnih načinov, da to storijo. jQuery samo kaže, da je malo bolj jedrnat in
vsekakor bolj priljubljena med programerji.
>> Zdaj delam malo zdrave pameti preveri, ker v problemu
Izjava smo izrecno rekel, če Uporabnik še ni tipkal njegovo ali njeno
ime, ne kažejo opozorila.
Vendar pa lahko preverite, da jih samo preverjanje za prazen niz za
quote-konec citata, če obstaja nič, dejansko obstaja.
Ampak, če to ni enako citatom-konec citata, Želim poklicati opozorila.
In zanimiv del tukaj je, da smo s pomočjo operaterja plus, ki
za kaj v JavaScript?
Združevanje.
Tako da je kot PHPs dot operaterja.
Isto idejo, nekoliko drugačno sintakso.
In jaz sem samo ustvarjanje niz, ki ste videli na zaslonu strel -
Pozdravljeni, tako in tako.
>> In potem detajl je to.
Zakaj se vrnem lažno notranjost te anonimno funkcijo?
>> PUBLIKA: Ni vrednost.
Si ga v obliki.
To samo pove, če je vrednost ni enako prazno, potem to storite.
Tam je bil prazen, v tej trditvi.
>> DAVID J. Malan: OK.
Previdno, čeprav.
Tam je nihče drug tukaj.
In da vrnitev false je zunaj o, če se razmere.
Torej je to poudarjeno črto, vrne false, izvaja ne glede na to, kaj, ko
Obrazec je predloženi.
Kaj se vračajo napačne notranjosti tega obravnavo dogodkov, kot se temu reče,
zadevnega dogodka da oddajo?
>> PUBLIKA: Ker je Samo se zgodi enkrat.
>> DAVID J. Malan: Samo se zgodi enkrat.
Ne povsem.
Ja?
>> PUBLIKA: To preprečuje, da bi v obliki iz predložitev privzeto vedenje,
ki bi se osvežitvi strani.
>> DAVID J. Malan: Točno tako.
Torej sem preobremenitve izraz predloži tukaj, saj pravim, oblika
bile predložene.
Toda, kot vam predlagamo, da je dejansko ni bili predloženi v pravem HTTP način.
Ko kliknete Pošlji, saj naše onSubmit trener, mi prekriža
da oddajo obrazec tako rekoč.
Mi smo potem počne naša stvar s kodo JavaScript.
Ampak jaz sem namenoma vrača false, ker tisto, kar ne želim, da se zgodi
Delček sekunde kasneje je za celotno obliko Sam je treba predložiti na spletu
Strežnik s ključnimi parov vrednosti s spreminjanjem URL, da bo nekaj podobnega
q = mačke ali karkoli smo storili, na primer, v razredu.
Ne želim, da se to zgodi, ker ni strežnika poslušanje za to
Obrazec za oddajo.
To je povsem storiti v JavaScript kodo.
In zato nisem imel niti Akcijski atribut na mojem obliki, ker sem
Ne nameravam za to, da kdaj šel na strežnik.
>> Torej, to je pa predloženi.
Ampak mi prekriža ta obrazec predložitev in preprečevanje privzeto
Vedenje, ki je dejansko iti vse do strežnika.
>> PUBLIKA: Tako da držimo odjemalsko.
>> DAVID J. Malan: Vodenje je client-side.
Točno tako.
Next up je bil moj oh MySQL.
>> ROB Bowden: OK.
Torej, to Prvo vprašanje je bilo na splošno grobo za ljudi.
Čeprav kasneje tisti šel bolje.
Torej bi morali izbrati pravilen podatkov Vrste za oba stolpcev.
In oboje imajo nekateri stvari o njih, ki
da izbira depresijo.
Torej int ni veljavna tip za številko.
Razlog je 12-mestna račun Številka, int ni dovolj velika, da
shranjevanje celotnih številk.
Torej bi veljavna izbira je velika int če se zgodi, da to veš.
Druga izbira bi lahko bila Polje char dolžine 12.
Torej bi enega od tistih, ki je delal.
Int ne bi.
>> Zdaj, ravnotežje, pomislite na pset7.
Zato smo se uporabljajo izrecno decimalno za shranjevanje vrednosti delnic ali -
>> DAVID J. Malan: Gotovina.
>> ROB Bowden: Gotovina.
Uporabili smo decimalno za shranjevanje količino denar, ki trenutno ima uporabnik.
Torej razlog, da smo to, da je ker je, ne pozabite, plava.
Tam je s plavajočo vejico v natančnosti.
To ni mogoče natančno shranite denar vrednote, kot smo želeli tukaj.
Torej decimalno lahko natančno trgovina nekaj, recimo, na dve decimalni mesti.
Zato ravnovesje, smo ga želeli biti decimalno in ne plavajo.
>> DAVID J. Malan: In tudi, preveč, čeprav to bi lahko bil pameten v drugi
konteksti, da razmišljajo, morda je to je priložnost za notr.
Jaz bom samo slediti stvari v penijev.
Ker smo eksplicitno pokazala privzeto vrednost pa 100,00, da
pomeni, da lahko samo int.
In še ena subtilnosti tudi s številom je bila, da ni bilo mišljeno
da je trik vprašanje.
Vendar pa opozarjajo, da int v MySQL, kot v C, vsaj
aparat, je 32-bitni.
In četudi vam ne pričakujejo, da točno vedeli, koliko cifer, da
sredstvo, se spomnim, da je največje število lahko predstavljajo potencialno
s 32-bitno število je približno kaj?
>> Kaj več pa smo vedno rekli?
2 do 32, kar je tisto, kar v grobem?
Ne boste morali natančno vedeti.
Ampak v grobem je v pomoč pri življenju.
To je približno 4 milijarde.
Zato smo rekli, da nekajkrat.
Vem, da sem rekel, da so nekajkrat.
In to je približno 4 milijarde.
In to je dobro pravilo palca vedeti.
Če imate 8 bitov, 256 je čarobno število.
Če imate 32 bitov, 4 milijard gor ali dol.
Torej, če si zapišite 4000000000, boste videli, da je to manj kot mestno
12, kar pomeni, da je očitno ni Dovolj izraznost, da zajame
Številka 12-mestna račun.
>> ROB Bowden: OK.
Torej, ostale pa so šli bolje.
Torej, predvidevam, da je banka nalaga 20 $ Mesečno
pristojbina za vzdrževanje na vse račune.
S tem, kar SQL poizvedb lahko banka odšteti 20 $ od vsakega števila, čeprav
ima za posledico nekaj negativnih bilancah?
Torej v bistvu, obstajajo štiri Glavne vrste vprašanj -
vstaviti, izberite, posodabljanje in brisanje.
Torej, kaj mislimo, da smo bo tu uporabo?
Posodobiti.
>> Torej, kaj si poglejmo.
Tako da tukaj smo posodabljanje.
Kaj namizni smo posodabljanje računov?
Tako posodabljanje računov.
In potem sintaksa pove, kaj v računovodskih izkazih smo posodabljanje?
No, mi smo določanju ravnotežja, ki je enak Sedanja vrednost ravnotežja minus 20.
Torej bo to posodobi vse vrstice računov, odštevanje
20 $ iz ravnotežja.
>> DAVID J. Malan: pogosta napaka tukaj, čeprav smo včasih ga odpustila,
je bil dejansko PHP kodo tukaj kliče funkcijo poizvedbe ali dajanje
narekovaje vse, kar ni treba biti tam.
>> ROB Bowden: Ne pozabite, da je MySQL samostojen jezik iz PHP.
Se zgodi, da se pisanje MySQL v PHP.
In PHP se ga pošilja prenesejo v strežnik MySQL.
Vendar vam ni treba PHP, da bi komunicirajo s strežnikom MySQL.
>> DAVID J. Malan: Točno tako.
Torej ni spremenljivke z dolarskih znakov bi morala biti v tem kontekstu.
To lahko samo stori vse za matematiko znotraj same baze podatkov.
>> ROB Bowden: OK.
Torej, naslednjič.
Je to drugo?
Ja.
Torej s tem, kar SQL poizvedb lahko banka priklicati številke račun svojih
Najbogatejši kupci, tisti z tehtnice, večje od 1000?
Torej, kateri od štirih glavnih vrst bomo želeli tukaj?
Izberite.
Zato želimo, da izberete.
Kaj želimo izbrati?
Kaj stolpec želimo izbrati?
Bomo posebej želeli Za izbiro.
Ampak, če si rekel zvezda, smo prav tako priznala, da.
>> Torej, izberite številko iz kakšne tabele?
Računi.
In potem pogoj želimo?
Če ravnotežje večja od 1000.
Prav tako smo sprejeli več ali enako.
Zadnja.
S tem, kar SQL poizvedb lahko banka blizu, to je zbrisal vse upoštevati, da
je ravnotežje med 0 $?
Torej, kateri od štirih smo bodo želeli uporabljati?
Izbrisati.
Torej sintaksa za to?
Izbriši iz kakšne tabele?
Računi.
Nato pa pogoj, na katerega želimo izbrisati -
kadar je bilanca enaka nič.
Tako da izbrišete vse vrstice iz računov kjer je stanje nič.
Vprašanja o kateri koli od teh?
Želite na vrsti?
>> DAVID J. Malan: Čakalna vrsta navodila.
Torej, v tem enem, smo vam dali nekoliko poznati strukturo, ki smo raziskali
bit v razredu skupaj z konstruktov, ki je podatke
povezane v duhu struktura.
Razlika čeprav s čakalno vrsto, je da smo morali nekako spomnim se, kdo
je na sprednji vrsti, v veliki del, tako da sva lahko naredila več
učinkovita uporaba spomin, vsaj Če smo s pomočjo niz.
>> Ker odpoklic, če imamo niz, če na primer, to je sprednji del
čakalne vrste, če dobim v čakalni vrsti tukaj, in potem nekdo dobi v skladu
Za mano, za mano, za mano, in ena oseba prekorači mejo, si
lahko, kot smo videli nekaj naših človeških prostovoljci v razredu, imajo vsi
premik v to smer.
Ampak na splošno, saj je vsakdo storiti nekaj, kar ni najbolje izkoristiti čas
v programu, saj to pomeni, da algoritem teče v tisto, kar
asimptotska čas teče?
To je linearna.
>> In jaz se počutim kot, da je nekako neumno.
Če je naslednja oseba v vrsti je naslednja Oseba, ki bi moral iti v
trgovina, nimajo vsi ne skupaj premakniti.
Pusti, da oseba, ki se pulili ko pride čas, na primer.
Tako bomo lahko prihranili nekaj časa tam.
In tako za to, da čeprav je, da sredstva da vodja čakalne vrste ali
Sprednji del vrsti bo postopoma premakniti globlje in globlje
v niz in na koncu morda dejansko ovijte okoli, če bomo s pomočjo
matrika za shranjevanje ljudi v tej vrsti.
Tako da lahko skoraj zamislite matrika kot krožni podatkov
struktura v tem smislu.
>> Tako da boste nekako morali slediti velikost njej ali res konec vsega
in nato, če je začetek tega.
Zato predlagamo, da ga razglasi ena taka vrsta, kliče
da q, samo eno črko.
Potem smo predlagali, da se prednja inicializiran na nič in da je velikost
inicializirati na nič.
>> Torej, zdaj, ni nič notranjost navedene vrste.
In vas prosimo, da izpolnite Izvajanje enqueue spodaj
tako, da je funkcija dodaja n na Konec q in vrne true.
Ampak, če q je poln ali negativen, funkcija bi morala namesto tega vrne false.
In vam dal nekaj predpostavk.
Ampak oni niso res funkcionalno pomembno, samo da bool obstaja,
ker je tehnično bool ne obstajajo v C, razen če vsebujejo
nekatere header datoteke.
Tako da je bil le poskrbite, da niso bile je to trik
Vprašanje takšne stvari.
>> Torej enqueue, smo predlagali v vzorcu rešitev za izvedbo, kot sledi.
Ena, moramo najprej preveriti, enostavnost, nizko viseče sadje je.
Če čakalna vrsta je polna ali številka, ki poskušate vstaviti manj
od nič, kar smo rekli v opredelitev problema smeli
ni dovoljeno, saj smo le želeli ne-negativne vrednosti, potem morate
pravkar vrnil false takoj.
Torej nekaj relativno enostavno Preverjanje napak.
Če temu želite dodati, da je dejanska številko, boste morali narediti malo
razmišljal sem.
In to je, če je malo siten duševno, ker moraš
ugotovimo, kako ravnati ovijajočega.
>> Ampak kalčki ideje tukaj, da je v zanimanje za nas je, da obdajajoča
pogosto pomeni modularna aritmetika in mod operater odstotkov strani,
kjer lahko greš z višjo vrednostjo nazaj na nič, nato pa ena in dva, in
tri in nato nazaj okoli ničle, ena in dva in tri in tako naprej
znova in znova.
Torej način predlagamo to početje je da nam želijo indeks v
Niz se imenuje številke, kjer naša cela laž.
Ampak do tja, smo najprej želeli narediti ne glede na velikost vrsti je vendar
nato dodamo, da karkoli Sprednji del seznama je.
In učinek tega je, da nas je na Pravica položaj v čakalni vrsti in
Ne domnevamo, da je prva oseba, ki je v skladu je na začetku, ki je ali
ona bi popolnoma lahko, če bomo so bile tudi premik vsakogar.
Vendar smo šele ustvarja delo za nas, če smo
da je zlasti pot.
>> Tako smo lahko, da ostane razmeroma preprost.
Mi se moramo, da smo pravkar dodal int v čakalno vrsto.
In potem smo pravkar vrnil res.
Medtem, v dequeue, smo povprašali da narediš naslednje.
Jo izvajati na tak način, da dequeues, da se odstranjuje in donosi,
int na sprednji vrsti.
Če želite odstraniti int, zadošča da pozabi.
Vam ni treba, da preglasijo svojo bit.
Torej je še vedno dejansko tam.
Tako kot podatkov na trdem disku, smo samo ignorira dejstvo,
da je zdaj tam.
In če je q prazna, bi morali namesto da se vrnete negativno 1.
Torej, to čuti samovoljno.
Zakaj donosnost negativna 1 namesto false?
Ja.
>> PUBLIKA: Q shranjevanje pozitivne vrednosti.
Ker ste le shraniti pozitivne vrednote V q, negativen je napaka.
>> DAVID J. Malan: OK, res.
Zato, ker smo le shranjevanje pozitiven vrednosti ali nič, potem je to v redu, da
vrne negativno vrednost kot kontrolnim vrednost, posebno oznako.
Ampak ste reportaža zgodovine tam, ker je razlog, da smo samo
vračanje niso negativne vrednosti je zato, ker želimo, da
imajo Sentinel vrednost.
Torej, še posebej, zakaj ne samo vrne false v primeru napak?
Ja.
>> PUBLIKA: ste ni uspelo vrne celo število.
>> DAVID J. Malan: Točno tako.
In to je, če C dobi zelo omejevalen.
Če pravite, da boste vrne int, imaš
, da se vrnete int.
Ne morete dobiti fancy in začetek vračanja int ali float ali
niz ali nekaj takega.
Zdaj, medtem, JavaScript ter PHP in nekatere druge jezike lahko dejansko
ste se vračajo drugačni Vrste vrednosti.
In to dejansko lahko koristno, če boste mogli vrniti pozitivne Ints, ničle,
Negativni ints, ali napačne ali null tudi, da se označi napake.
Ampak nimamo, da vsestranskost v C.
>> Torej z dequeue, kar smo Predlagamo, da storiti, je -
>> ROB Bowden: Lahko vrne false.
To je samo, da je lažno hash opredelijo false nič.
Torej, če ste vrne false, ste se vrača nič.
In nič je veljavna stvar v naši vrsti, ker so negativni 1 ni, če
false zgodilo, da se negativna 1.
Vendar pa ne bi smeli niti Vedeti morajo, da.
>> DAVID J. Malan: To je zakaj nisem to rekel.
>> ROB Bowden: Ampak to ni res ki jih ni mogoče vrniti false.
>> DAVID J. Malan: Seveda.
Torej dequeue, opazili smo sprejeli izniči njen argument.
In to zato, ker nismo gre nič noter
Pravkar smo želeli odstraniti element na sprednji vrsti.
Torej, kako bi lahko šel o tem?
No, najprej, dajmo Hiter pregled sanity.
Če velikost vrste je 0, obstaja ni treba kaj postoriti.
Vrni se negativna 1.
Končano.
Tako da je nekaj vrstic mojega programa.
Torej le štiri linije ostajajo.
>> Torej, tukaj sem se odločil, da pojemanje velikost.
In učinkovito decrementing velikost pomeni, da sem pozabljam
kaj je notri.
Ampak sem tudi posodobiti, kjer prednja številk so.
Torej za to, moram narediti dve stvari.
Najprej sem si morajo zapomniti, kaj številke je na sprednji vrsti,
ker moram vrniti to stvar.
Torej, ne želim, da pomotoma pozabil o njem in ga nato prepiše.
Jaz bom samo, da se spomnimo na notr.
>> In zdaj, hočem posodobiti q.front se q.front 1.
Torej, če je to prva oseba v linijo, zdaj pa želim narediti plus 1 do
opozoriti na naslednjo osebo v liniji.
Ampak moram ravnati, da ovijajočega.
In če zmogljivost je globalna konstanta, da se dogaja, da mi dovolite, da poskrbite, da
kot sem že opozarjajo na zelo zadnji osebo v linija, bo operacija modulo prinese
me nazaj na ničlo na sprednji čakalne vrste.
In da upravlja z ovitim tukaj.
In potem se lotim, da se vrnete n.
>> Zdaj pa, strogo gledano, nisem morali razglasiti n.
Nisem imel, da ga zgrabi in ga shranite začasno, ker je vrednost
še vedno tam.
Torej, jaz bi samo narediti pravo aritmetično za vrnitev nekdanjega voditelja
čakalne vrste.
Vendar sem čutil, da je to bolj jasno dejansko zgrabi int, ga
v N, in se nato vrnite, da zaradi večje preglednosti, ampak
ni nujno potrebno.
Psst.
Oni so vsi izgovorljivo v moji glavi.
>> ROB Bowden: Torej, prvo vprašanje je binarno drevo problem.
Torej, prvo vprašanje je, da smo saj te številke.
In želimo, da jih nekako vstavite v ta vozlišča, tako da je
veljavno binarno iskalno drevo.
Torej ena stvar, da se spomniš o binarna iskalna drevesa je, da to ni
le da stvar na levi je manj in stvar
Pravica je večja.
To mora biti, da je celotno drevo Levi manj, in drevesne
na desni je večja.
>> Torej, če bi dal 34 tukaj na vrhu, in nato Sem dal 20 tukaj, tako da je veljavna, tako
daleč, saj 34 do tu.
20 se dogaja na levi strani.
Tako da je manj.
Ampak ne morem potem dal 59 tukaj, ker čeprav 59 je na desni strani 20,
je še vedno na levi strani 34.
Torej s tem v mislih omejitev, Najlažji način za reševanje tega verjetno
Problem je, da se nekako od teh številk -
do 20, 34, 36, 52, 59, 106.
In potem vstavite tiste od leve proti desni.
>> Torej 20 gre tukaj.
34. gre tukaj.
36. gre tukaj.
52, 59, 106.
In tudi vi bi pogruntal z nekateri priklopom in uresničevanju,
Oh, počakajte, da nimajo dovolj številk to izpolnite tukaj.
Tako da moram reshift, kaj je moja opomba pot se bo.
Ampak obvestilo, da je v zadnjih treh, če berete od leve proti desni, da je v
naraščajočem vrstnem redu.
>> Torej, zdaj smo želeli opredeliti, kaj struct se bo za
vozlišča v drevesu.
Torej, kaj moramo v binarnem drevesu?
Torej imamo vrednostjo tipa int, tako da nekateri int vrednost.
Ne vem, kaj smo poklicali je v raztopini -
int n.
Moramo kazalec na levi otroka in kazalec na desni otroka.
Tako da se bo izgledala takole.
In to bo dejansko videti, preden kdaj dvojno vezan
Seznam stvari, tako da obvestilo -
Jaz bom moral, da se pomaknete vse Pot nazaj do problema 11.
>> Tako obvestilo je videti identičen temu, razen pravkar zgodilo, da pokličete te
različnimi imeni.
Še vedno imamo celo vrednost in dva kazalca.
To je samo, da namesto zdravila za zdravljenje kazalci, kot kaže na naslednjo stvar
in prejšnja stvar, smo zdravljenje Kazalci, da kažejo na levi otroka
in pravico otrok.
OK.
Tako da je naša struct node.
In zdaj, deluje le moramo izvajati za to prečno, ki
želimo iti čez drevesa, tiskanje od vrednosti drevesa v redu.
>> Tako je videti tukaj, bi želeli natisniti od 20, 34, 36, 52, 59 in 106.
Kako bomo dosegli, da je?
Tako da je precej podobna.
Če ste videli v zadnjem izpitu problem da si je želel, da natisnete
Celoten drevo z vejicami vmes vse, kar je bilo pravzaprav celo
lažje kot to.
Torej, tukaj je rešitev.
To je bilo bistveno lažje Če si to naredil rekurzivno.
Ne vem, če je kdo poskušal to storiti iterativno.
>> Toda najprej imamo osnovno zadevo.
Kaj pa, če korenina je nična?
Potem smo le, da bo vrnil.
Mi ne želimo natisniti ničesar.
Ostalo bomo za prečkanje rekurzivno navzdol.
Natisni celotno levo poddrevo.
Torej natisniti vse manj od moje trenutne vrednosti.
In potem bom sam natisniti.
In potem bom recurse navzdol my Celoten desno poddrevo, tako da je vse
večja od moje vrednosti.
In to se dogaja za tiskanje ven vse v redu.
Vprašanja o tem, kako to dejansko dosega to?
>> PUBLIKA: Imam vprašanje na [neslišno].
>> ROB Bowden: Torej en način približuje vsaka rekurzivna problem je, da samo mislim,
o tem rad moraš razmišljati o vseh primerih vogalu.
Tako menijo, da želimo natisnete celotno drevo.
Torej, vsi se bomo osredotočili na je to predvsem vozlišče -
36.
Rekurzivne klice, se pretvarjamo tistih, ki samo delo.
Torej, tukaj je ta rekurzivni klic, da Prečna, smo celo brez razmišljanja
o tem, samo prečkajo levo tri, si predstavljajte, da že natisne 20
in 34 za nas.
In potem, ko smo na koncu rekurzivno pokličite prečnega nosilca na
Dobro, da bo lahko pravilno natisnili 52, 59 in 106 za nas.
>> Zato ker to lahko natisnete 20, 34, in drugi lahko natisne 52, 59, 108,
vse, kar potrebujemo, da bi lahko storili, je print Sebe v sredini tega.
Torej izpisal vse pred nami.
Natisni Sebe, tako da se natisne trenutni vozel 36, redno printf, nato pa
natisniti vse nas.
>> DAVID J. Malan: To je, če rekurzija postane res lepa.
To je to neverjetno preskok vere, kjer vam najmanjše nekaj dela.
In potem naj nekdo ostalo pa ostalo.
In da je nekdo drug je, ironično, ti.
Torej za resne piškote točk, če pomaknete navzgor na vprašanja -
>> ROB Bowden: Na vprašanja?
>> DAVID J. Malan: In dol malo številke, ali kdo ve, kje
te številke prišel?
>> ROB Bowden: Imam dobesedno nima pojma.
>> DAVID J. Malan: Pojavljajo v celotnem kvizu.
>> PUBLIKA: Ali so iste številke?
>> DAVID J. Malan: Te številke.
Malo Pirh.
Torej za tiste, ki ste gledal na spletu domov, če nam lahko poveste, prek e-pošte
heads@CS50.net kaj pomen od teh ponavljajočih šest številke
v celotnem kvizu 1, vas bomo tuš z neverjetno pozornost na končni
Predavanje in stres žogo.
Lepo, subtilna.
>> ROB Bowden: Poslednje vprašanja približno nič na kvizu?