>> David Malan: Alle reg.
Welkom terug na CS50.
Dit is die begin van die week 8.
En onthou dat die probleem stel 5 geëindig met 'n bietjie van 'n uitdaging.
So die veronderstelling dat jy herstel van al jou onderrig Fellows en GR se foto's
in die card.raw lêer, kom jy in aanmerking nou vind al die mense, en
een gelukkige wenner sal huis toe stap met een van hierdie dinge, die sprong beweging
toestel wat jy kan gebruik vir die finale projekte, byvoorbeeld.
>> Dit is elke jaar, lei tot 'n bietjie van creepiness.
En so wat ek gedink ek wil doen, is deel met jou 'n paar van die note wat
gegaan heen en weer oor die personeel lys van laat.
Byvoorbeeld, net gisteraand, quote unquote, uit een van die personeel
lede, "Ek het net 'n student klop aan my deur 'n foto met my te neem.
Agtervolgers, sê ek jou "begin. redelik beskrywende en dan het ons verhuis
aan, 'n uur of so later, "Ek het 'n student wag vir my na artikel
en hy het al ons name en foto's op 'n paar velle papier "Alles reg..
So georganiseer, maar nie almal wat creepy nie.
>> Dan, "Ek was uit die dorp die naweek, en toe ek terug was daar een in
my
slaapkamer ". [Gelag]
David Malan: Volgende aanhaling uit 'n personeellid lid ", 'n student by my huis op
Somerville by 04:00 vanoggend "Volgende. personeel, "Ek het na my hotel in San
Francisco en 'n student was die wag vir my aan die gang met drie DSLRs. "
Tipe kamera.
"Ek is nie eens op die personeel van hierdie semester, maar 'n student het gebreek in my huis hierdie
oggend en aangeteken om die hele ding met Google Glass "En dan is. Laastens,
"Ten minste 12 mense is gretig wag vir my wanneer ek uit my
limo, en dan het ek
wakker "Alles reg..
So tussen die foto's, as jy kan onthou, is hierdie man hier, wat jy
kan weet as Milo Banana, wat woon met Lauren Carvalho, ons kop
Mede-onderrig.
Milo, Milo, hier kom seuntjie.
Milo.
Mind u, hy dra Google Glass, so ons sal jou wys al hierdie na.
So is dit Milo as jy wil neem 'n foto saam met hom daarna.
As jy wil om te kyk uit aan die gehoor daar.
OK.
Dit is 'n goeie footage.
Wel, Milo piesang.
O ja, dit nie doen nie.
>> [Gelag]
>> OK.
So 'n woord dan oor wat voorlê, want as ons begin met die oorgang,
hierdie week spesifiek, van C in 'n command line omgewing te PHP en
JavaScript en SQL en HTML en CSS in 'n web-gebaseerde omgewing, sal ons
toe te rus met al die meer kennis vir
potensiaal finale projekte.
In die rigting van die einde, die kursus het 'n tradisie van die hou van seminare wat
is op tangensiaal onderwerpe tot die kursus.
Baie verband hou met ontwikkeling en app ontwikkeling en so meer, maar
nie noodwendig ondersoek deur die kursus se eie leerplan.
>> So as jy dalk belangstel in 'n of meer van hierdie jaar se seminare,
registreer op cs50.net/seminar.
Daar is ouer seminare by cs50.net/seminars.
En op die rooster tot dusver vir hierdie jaar is Amazing Web Apps met Ruby on
Relings, wat is 'n alternatief taal te PHP.
Rekenaarlinguistiek.
Inleiding tot IOS, wat die platform vir die iPhone wat gebruik is en
iPad ontwikkeling.
JavaScript vir Web Apps, sal ons dek dit nie, maar in hierdie seminaar, sal jy gaan
in meer detail.
>> Spring Motion, so ons sal eintlik 'n paar van ons vriende van die sprong Motion,
die maatskappy self, by ons aansluit.
Môre, in werklikheid, te verskaf 'n hands-on seminaar, indien
van belang is vir jou.
Meteor.js, 'n alternatiewe tegniek vir met behulp van JavaScript nie in 'n leser,
maar op 'n bediener.
Node.js, wat baie in dié trant as well.
Glad Android Design.
Android 'n baie gewilde alternatief te IOS en Windows Phone
en ander mobiele platforms.
En Web Security Active verdediging.
>> So in werklikheid, as jy wil om betrokke te raak in hierdie, laat my
maak hiervan kennis.
Ons is baie bly om te sê dat ons vriende by Leap
Beweging, wat is 'n begin -
hierdie toestel regtig net gekom 'n paar maande gelede -
uit genade geskenk het 30 sulke toestelle na die klas vir soveel studente as
jy wil die hardeware te leen teenoor semester se einde en dit gebruik vir
'n werklike finale projek.
Hulle ondersteun 'n aantal tale.
Nie een van hulle C, nie een van hulle PHP, so besef een of meer van die seminare
kan bewys van belang.
En almal van hulle sal verfilm word in die geval dat jy nie in staat is om
persoonlik by te woon.
Die skedule aangekondig word via e-pos as ons stol kamers.
>> En laastens, as jy gaan na projects.cs.50.net, dit is 'n webwerf
Ons hou elke jaar wat ons nooi mense uit die gemeenskap, die fakulteit,
departemente, personeel en beide in 'n buite CS50 te
stel projek idees.
Dinge van belang is vir student groepe.
Dinge van belang is vir departemente.
So draai daar nie as jy sukkel met onsekerheid oor wat jy
jouself wil graag aan te pak.
>> So laaste keer dat ons 'n waarskynlik meer komplekse data struktuur as wat ons wil
gesien in weke verlede.
Ons wil al met behulp van skikkings mooi gelukkig as 'n nuttige indien
eenvoudige data struktuur.
Daarna het ons het dié wat natuurlik gekoppel lyste.
En wat was een van die motivering vir bekendstelling van hierdie data struktuur?
Ja?
Wat is dit?
>> GEHOOR: Dynamic grootte.
>> David Malan: Dynamic grootte.
So terwyl dit in skikking, wat jy hoef te weet sy grootte vooruit
jy ken dit.
In gekoppel lys, wat jy doen nie het om te weet dat.
Jy kan nie net malloc, of meer algemeen, Ken 'n addisionele
knoop, om so te praat, enige tyd wat jy wil meer inligting by te voeg.
En node het geen voorafbepaalde betekenis.
Dit is net 'n generiese term wat 'n soort van houer wat ons is
gebruik in ons data struktuur te stoor 'n item van belang, wat in hierdie
geval gebeur om te wees heelgetalle.
>> Maar daar is altyd 'n nadeel.
So kry ons dinamiese groottes van die data struktuur, maar watter prys betaal ons?
Wat is die negatiewe kant van geskakelde lyste?
Ja?
>> GEHOOR: vereis meer geheue.
>> David Malan: Dit vereis meer geheue, hoe presies?
>> GEHOOR: [onhoorbaar].
>> David Malan: Presies.
So nou het ons wenke neem addisionele geheue wat ons voorheen
het nie nodig nie, omdat die voordeel van 'n skikking, natuurlik, is dat
alles is aangrensend, terug om terug te rug, wat
gee jou ewekansige toegang.
Want net deur die gebruik van vierkante hakies notasie, of meer tegnies wyser
rekenkundige, baie eenvoudige Daarbenewens, kan jy toegang tot enige
elemente in konstante tyd.
En in waarheid te sê, dit is soort van sinspeel op 'n ander prys wat ons betaal met 'n
gekoppel lys.
>> Wat gebeur met die loop van die tyd van iets soos Search, as ek wil
'n paar waarde en binne van 'n geskakelde lys?
Wat beteken my loop tyd geword het?
Big O van n.
As dit gesorteer?
Wat as die data struktuur is gesorteer?
Kan ek doen beter as groot O van n soek?
Nee, want in die ergste geval is dit dalk baie goed gesorteer word, maar die aantal
jy soek dalk groot wees.
Dit mag dalk die getal 100, wat wees kan gebeur om te wees al
die pad aan die einde.
En omdat jy kan net toegang tot 'n gekoppelde lys in die implementering van hierdie deur
weg van sy eerste knoop, jy nog soort van uit van geluk.
Jy het die hele ding te deurkruis vanaf die eerste tot die laaste om uit te vind
dat die groot waarde soos 100.
Of om te bepaal of dit nie eens daar nie.
>> So kan ons nie doen wat algoritme in 'n data struktuur wat lyk soos hierdie?
Ons kan dit nie doen binêre soek, want binêre soek vereis dat ons
ewekansige toegang.
Ons kan net spring van plek tot plek sonder om te volg
hierdie broodkrummels in die vorm van al hierdie wenke.
>> Nou, hoe het ons hierdie?
Wel, as ons na die skerm hier, indien ons kan vinnig reimplement hierdie data
struktuur -
my handskrif is nie al wat groot hier, maar ons sal probeer.
So typedef struct, en wat het ek wil hierdie ding te noem hier?
Knoop.
So ek sal aan die gang kry.
En nou, wat gedoen moet word binne die data struktuur wat afsonderlik
gekoppel lys?
Hoeveel velde?
>> So twee.
Een daarvan is redelik maklik.
So int n.
En ons kan noem n iets is wat ons wil hê, maar dit moet 'n int wees as ons
die implementering van 'n gekoppelde lys vir ints.
En nou wat doen die tweede veld te wees?
Struct node *.
So as ek dit doen struct node *, en dan het ek kan noem dit ook wat ek wil,
Maar net om duidelik te wees Ek bel dit langs, soos ons het om te doen.
En dan sal ek sluit my krullerige draadjies.
>> En nou, as laaste tyd, Ek sit knoop hier.
Maar as ek verklaar dat dit is as 'n knoop, hoekom het ek die moeite om so
verbose hier in verklaar struct knoop * langs, in teenstelling
om net te knoop * volgende?
Ja?
>> GEHOOR: [onhoorbaar].
>> David Malan: Presies.
Presies.
Omdat C neem jy regtig letterlik en kyk net die definisie van node
pad af hier, jy kan nie verwys na dit hier.
So ons het hierdie soort preventive verklaring hier, wat weliswaar
meer verbose.
Struct knoop, wat beteken Ons kan nou toegang tot die
binnekant van die data struktuur.
>> En as 'n eenkant, want dit is besig om 'n bietjie meer subjektiewe nou,
die ster kan tegnies hier gaan, kan dit hier gaan, kan dit
selfs gaan in die middel.
Ons het aangeneem, in die styl gids vir die kursus, die konvensie van die plaas
die ster reg langs die data tipe, wat in hierdie geval,
sou struct node wees.
Maar besef in 'n baie handboeke en aanlyn verwysings, dan kan jy inderdaad
sien dit aan die ander kant.
Maar net besef dat beide sal eintlik werk en jy moet eenvoudig wees
konsekwent.
>> Alle regte.
So dit was ons verklaring van struct knoop.
Maar dan moet ons begin om meer te doen gesofistikeerde dinge.
Byvoorbeeld, het ons besluit om in te voer iets soos 'n hash tafel.
So hier is 'n hash tafel van grootte n, geïndekseer vanaf 0 op die boonste links na n
minus 1 op die links onder.
Dit kan 'n gemors tafel vir enigiets.
Maar watter soort dinge het ons praat oor die gebruik van 'n hash tafel?
Stoor wat?
>> Name.
Ons kan doen name soos ons gedoen het die afgelope tyd.
En regtig, kan jy dit stoor nie.
En ons sal sien dit weer in PHP en in JavaScript.
'N hash tafel is 'n lekker soort van Switserse Army mes wat dit moontlik maak om jou te slaan
pretty much alles wat jy wil binne deur assosieer sleutels met waardes.
Keys met waardes.
>> Nou in hierdie eenvoudige geval, ons sleutels is net nommers.
Ons is die implementering van 'n gemors tafel as 'n skikking.
En so het die sleutels is 0, 1, 2, en so meer.
En so het ons, as mense, het verlede week dat jy weet wat, as ons
gaan om te slaan name, laat ons net arbitrêr, maar redelik redelik,
aanvaar dat Alice, 'n A-naam, sal net geïndekseer word in 0.
En Bob, 'n B naam, sal opgeneem word in 1, en so meer.
So het ons 'n skakel tussen insette, wat stringe, en die hash
plekke, wat is getalle.
>> Sodat proses is algemeen bekend as 'n hash funksie, en jy kan werklik
implementeer dit in die kode.
As ek wou 'n hash funksie te implementeer wat nie presies wat ons
net beskryf van die afgelope tyd, ek kan verklaar 'n funksie wat ', as
insette byvoorbeeld -
en laat ons doen dit op hierdie skerm hier.
As ek wou 'n gemors te implementeer funksie, kan ek sê
iets soos hierdie.
>> Dit gaan 'n int om terug te keer.
Dit gaan om genoem te word hash, en dit is gaan om te aanvaar as 'n argument 'n
string, of kan ons meer behoorlike nou, en sê char *, sal ons noem dit s.
En dan sal al hierdie funksie het om te doen, Uiteindelik is 'n terugkeer int.
Nou, hoe is dit nie wat dalk nie so duidelik nie.
Ek gaan om dit te voer sonder enige vorm van die fout kontrole nou.
Ek gaan net om blindelings sê, terug alles wat op s bracket 0, minus,
kom ons sê, die hoofstad 'n kommapunt.
>> Heeltemal gebreek.
Dit is nie volmaak nie, want een, wat as s is van nul?
Slegte dinge gaan gebeur.
Twee, wat as die eerste letter in hierdie naam is nie 'n hoofletter?
Dit gaan nie om te draai goed uit nie.
Dit mag dalk 'n klein letter wees of nie 'n brief nie.
So totaal ruimte vir verbetering hier, maar dit is die basiese idee.
>> Wat ons beskryf verlede week mondelings as net 'n proses van die kartering van Alice te
0 en Bob tot 1 uitgedruk kan word beslis meer formulaically as 'n C
funksioneer hier.
Genoem weer hash, neem 'n string as insette, en dan nie een of ander manier iets
met die insette 'n uitset te produseer.
Nie in teenstelling met ons swart boks beskrywing dat ons het lank gedoen.
Ek weet nie hoe dit kan wees werk onder die kap.
>> Vir probleem set 6, een van die uitdagings is vir jou om te besluit wat
sal jou hash funksie sal wees?
Wat gaan aan die binnekant van die swart wees boks, en vermoedelik, sal dit 'n
bietjie meer interessant as dit nie, en beslis meer geneig is om fout
nagaan as hierdie spesifieke implementering.
>> Maar probleme kan ontstaan, reg?
As ons 'n data struktuur soos hierdie een, wat is een van die probleme
jy kan hardloop in die verloop van tyd as jy voeg meer en meer name in die
hash tafel?
Jy botsings, reg?
Wat gebeur as jy 'Alice en Aaron, twee mense wie se name gebeur
om te begin met 'n?
Dit lei tot die vraag, waar jy sit die tweede so 'n naam?
>> Wel, kan jy dalk naïef net sit dit waar Bob behoort, maar dan is Bob
soort geskroef as jy probeer om te voeg sy naam langs en
daar is geen plek vir hom.
Sodat jy kan sit Bob waar Charlie is, en jy kan dit baie vinnig dink
wentel in 'n bietjie van 'n gemors.
Iets lineêre in die einde, waar jy net die hele ding om te soek
soek na Alice of Bob of Aaron of Charlie.
>> So in plaas ons voorgestel het, in plaas van net lineêr indringende vir oop ruimtes
en plop die name daar Ons voorgestel dat 'n liefhebber benadering.
'N hash tafel geïmplementeer nog steeds met 'n verskeidenheid van indekse, maar die data tipe
daardie indekse nou was wysers.
Verwysings na wat?
Verwysings na geskakelde lyste.
>> Want onthou dat 'n geskakelde lys is eintlik net 'n verwysing na 'n knoop, en
die knoop het 'n volgende veld, en dat node het 'n volgende veld, en so meer.
So kan jy nou dink van hierdie reeks op die linkerkant van 'n hash tafel
lei tot 'n geskakelde lys.
Die voordeel van dit is as jy 'n botsing tussen Alice en Aaron,
Wat doen jy met die tweede so 'n persoon?
Jy moet net heg hom of haar aan die einde, of selfs die begin
van wat gekoppel lys.
>> En eintlik, laat ons net noodle deur wat vir 'n tweede.
Waar sou maak die meeste sin maak?
As ek voeg Alice en sy beland op die eerste plek, dan het ek probeer om te
voeg Aaron se naam, en daar is natuurlik 'n botsing, moet ek
hom aan die begin van die geskakelde lys?
Dit is op daardie eerste plek, of aan die einde?
>> GEHOOR: [onhoorbaar].
>> David Malan: OK.
Ek het gehoor die begin.
Waarom aan die begin?
>> GEHOOR: [onhoorbaar].
>> David Malan: OK.
Dit is alfabeties, so dit is lekker.
Dit is 'n goeie eiendom.
Dit sal red my 'n paar keer potensieel.
Dit laat my nie doen binêre soek, maar ek kan ten minste in staat wees om weg te breek
van 'n lus as ek besef dat, wel, ek is weg verlede was Aaron sal wees in hierdie
gesorteer geskakelde lys.
Ek het nie my tyd te mors op soek na al die pad na die einde.
So dit is redelik.
Hoekom anders wil jy dalk om in te voeg die botsing naam op die
die begin van die lys?
Wat is dit?
>> GEHOOR: [onhoorbaar].
>> David Malan: Dit kan 'n lang tyd in beslag neem te kry om die einde van die lys.
En in die feit, langer en langer.
Hoe meer name wat jy voeg dat begin met A, die meer wat
ketting gaan kry.
Die meer wat gekoppel lys is die gang te kry.
So jy is regtig net mors jou tyd.
Miskien is jy beter af handhawing konstant te voeg, groot O van 1,
deur altyd die botsing naam op die begin van die geskakelde lys,
en nie bekommerd te wees soveel oor te sorteer.
>> Wat is die beste antwoord?
Dit is onduidelik.
Dit soort van hang af van wat die verspreiding is, wat die patroon is
van die name wat jy inbring.
Dit is nie noodwendig 'n duidelike antwoord.
Maar hier, weer, is 'n ontwerp geleentheid.
>> So het ons dan kyk na hierdie ding, wat is werklik die ander groot geleentheid
vir p-set 6.
En besef, as jy nog nie het nie, Zamyla duik in beide van hierdie, hash
tafels en drieë, in meer detail.
En die video walkthrough is ingesluit in p-set spec.
Dit was 'n Trie -
T-R-I-E. En wat was interessant oor hierdie is dat die loop van die tyd
van die soek na 'n naam, soos Maxwell laaste keer was groot O van wat?
Wat is dit?
>> Publiek: Die aantal letters.
>> David Malan: Aantal letters.
Ek het gehoor twee dinge.
Aantal letters en konstante tyd.
So laat ons gaan met die eerste.
Die aantal letters.
Wel, hierdie data struktuur, onthou, is soos 'n boom, 'n familie boom, elke
wie se knope is gemaak van skikkings.
En dié skikkings is verwysings na ander soos knope, of sodanige ander
skikkings in die boom.
>> So as ons wou bepaal dan of Maxwell is in hier, kan ek gaan
na die eerste skikking, by die top van die boom, die sogenaamde wortel, bo-
die tydstip waarop, en dan volg die m wyser, dan is die 'n wyser, dan is x,
w, e, l, l.
En dan wanneer ek sien 'n paar spesiale simbool, aangedui hier as 'n driehoek.
In die kode wat jy sien ons voor dat u geïmplementeer as 'n Bool, net ja sê
of nie, 'n woord stop hier.
>> Wel, as ons gegaan het om M-A-X-W-E-L-L, voel soos sewe, miskien
agt as ons gaan 'n verlede, agt stappe Maxwell te vind.
Of kom ons noem dit K. Maar onthou verlede tyd, ek het aangevoer dat indien daar
realisties 'n maksimum lengte op 'n woord, soos 40-paar-vreemd karakters, 'n
maksimum lengte impliseer 'n konstante waarde.
So regtig, ja, dit is tegnies groot O van 8 of 7, of baie groot O van K. Maar
As daar is 'n beperkte pet op watter K kan wees, dit is 'n konstante.
En so dit is groot O van 1 by die einde van die dag.
>> Nie in die werklike wêreld.
Nie wanneer jy eintlik begin kyk jou klok as jou program se bestuur.
Dit is absoluut gaan 'n bietjie stadiger as werklik konstant
tyd saam met 'n stap.
Dit gaan wees sewe of agt stappe maar nog steeds dit is baie, baie beter
as 'n algoritme soos 'n groot O van n wat hang af van die grootte van wat in die
data struktuur.
>> Let op die onderstebo hier is wat ons kan voeg 'n miljoen meer name in hierdie
data struktuur, maar hoe baie meer stappe gaan dit om ons te neem om uit te vind
Maxwell in so 'n geval?
Geen.
Hy is nie geraak nie.
En tot op datum, ek dink nie ons het gesien 'n voorbeeld van 'n data struktuur of 'n
algoritme wat was heeltemal onaangeraak deur eksterne
gedrag soos dit.
Maar dit kan nie wees amazing.
Dit kan nie die enigste oplossing vir die p-reeks
>> En dit is nie.
Dit is nie noodwendig die data struktuur wat jy moet aangetrokke tot,
want soos hash tabelle, nadeel.
Wat is die prys wat jy betaal hier?
Geheue.
Ek bedoel, dit is 'n gruwelike bedrag van die geheue.
En jy kan nie heeltemal sien dit hier omdat die skrywer van hierdie foto
natuurlik afgekapte al die skikkings, en ons nie sien nie baie van die A's en
B's en C's en Q's en Y se en Z's in hierdie skikkings.
Maar hulle is daar.
>> Elkeen van hierdie nodes is 'n hele reeks van sowat 26 of meer grepe, elk van
wat 'n brief.
27 In ons geval is, sodat ons kan ondersteun apostrofs in die probleem stel.
So hierdie data struktuur is regtig, regtig dig en breed.
En dit alleen kan uiteindelik stadiger dinge af, of ten minste kos jou 'n
baie meer ruimte.
Maar weereens, kan ons trek vergelykings hier.
>> Onthou 'n rukkie terug, het ons baie bereik meer opwindende loop van die tyd in sortering
wanneer ons saamsmelt soort, maar die prys Ons betaal te bereik n teken vir n saamsmelt
soort nodig dat ons spandeer meer watter hulpbron?
Meer ruimte.
Ons moes 'n sekondêre skikking te kopieer mense in, net soos
ons het hier op die verhoog.
So weer, geen duidelike wenners, maar net subjektiewe ontwerp
besluite gemaak moet word.
>> Alle regte.
So hoe oor dit?
Enigiemand wat erken D-Hall?
OK.
So drie van ons doen.
Mather House.
So dit is vir Mather se eetkamer.
Ek wed al die eetsale het stapels bak soos hierdie.
En dit is eintlik verteenwoordiger van iets wat ons het
duidelik gesien word reeds.
Ons het dit letterlik 'n stapel.
En die stapel, in terme van jou rekenaar se geheue, is waar die data gaan
terwyl funksies word genoem.
>> Byvoorbeeld, watter soort van dinge wat gaan op die stapel met betrekking tot die
geheue uitleg ons bespreek in weke verlede?
Wat is dit?
>> GEHOOR: Oproepe na funksies.
>> David Malan: Ek is jammer.
>> GEHOOR: Oproepe na funksies.
>> David Malan: Oproepe na funksies, maar spesifiek, wat binne in elkeen van
diegene rame?
Watter soort dinge?
Ja.
So plaaslike veranderlikes.
Elke keer wat ons nodig het 'n paar plaaslike stoor, soos 'n argument, of int ek, of int
Temp, of wat ook al die plaaslike veranderlike is, het ons al
om dit op die stapel.
En ons noem dit 'n stapel, want van daardie lae idee.
Net soort van die wedstryde met die werklikheid, die konsep daarvan.
>> Maar dit blyk dat 'n stapel kan ook gesien word as 'n data struktuur, 'n
alternatief tot 'n skikking, 'n alternatiewe aan 'n gekoppelde lys.
Iets konseptueel meer interessant wat nog kan wees
uitgevoer met behulp van een van dié dinge, maar dit is 'n ander soort
data struktuur ondersteun, regtig, slegs twee operasies.
Maar jy kan byvoeg liefhebber funksies as dié nie.
Maar dit is die basiese beginsels -
stoot en pop.
>> En die idee met 'n stapel is dat as ek hier het, met of sonder Annenberg
weet, 'n skinkbord van langsaan met die nommer 9 op dit.
Dus net 'n int.
En ek wil om dit te stoot op die data struktuur, wat tans is leeg.
Beskou dit as die onderkant van die stapel.
Ek wil hierdie nommer 9 druk op die stapel, en nou is dit net daar.
>> Maar die interessante ding oor 'n stapel is dat as ek nou wil stoot
'n ander waarde, soos 17, en ek stoot hierdie op die stapel, ek gaan om dit te doen
die enigste ding wat intuïtief, is ek net gaan dit reg te stel waar ons mense
sou geneig wees om dit te sit, bo-op.
Maar wat interessant is nou is, hoe kry ek op 9?
Jy weet, ek doen nie sonder 'n poging.
>> So, wat is interessant oor 'n stapel is dat deur die ontwerp,
dit is 'n LIFO data struktuur.
Dom manier om te beskryf laaste in, eerste uit.
So het die laaste nommer in in hierdie tyd was 17.
So as ek iets wil pop af van die stapel, kan dit net wees 17.
So is daar 'n verpligte orde van bedrywighede hier, waar die laaste item
in het aan die eerste een uit wees.
Vandaar die akroniem, LIFO.
>> So hoekom kan dit nuttig wees?
Is hulle konteks waarin jy wil wil 'n data struktuur soos hierdie?
Wel, seker dit is nuttig binnekant van 'n rekenaar.
So bedryfstelsels duidelik gebruik om hierdie soort data struktuur vir stapels.
Ons sien ook die dieselfde idee wanneer dit kom by die web bladsye.
So hierdie week en volgende week en verder, en as jy begin met die implementering web
bladsye in 'n taal, die sogenaamde HTML, kan jy eintlik gebruik om 'n data struktuur soos
hierdie om te bepaal of die bladsy is korrek geformateer.
Omdat ons sal sien al die web bladsye volg 'n soort van 'n hiërargie, 'n inkeping
wat aan die einde van die dag is, 'n boom struktuur onder die kap.
So meer op wat in net 'n bietjie.
>> Maar vir nou, laat ons voor te stel vir 'n oomblik, hoe kan ons gaan oor
verteenwoordig wat 'n stapel is?
Laat my voor dat ons implementeer 'n stapel met 'n kode soos hierdie.
So 'n stapel gaan hê binnekant van dit twee dinge, 'n skikking, genaamd bak,
net om te wees in ooreenstemming met die demo.
En elk van die items in die skikking gaan 'n tipe int wees.
En kapasiteit is vermoedelik wat?
Want ek het nie geskryf die volledige definisie hier.
>> Dit is waarskynlik die maksimum grootte van die skikking.
En dit is waarskynlik verklaar as 'n skerp definieer aan die bokant van die lêer, sommige
soort van 'n konstante soos geïmpliseer deur die blote kapitalisasie.
So iewers kapasiteit word gedefinieer as die maksimum grootte.
Intussen het die binnekant van die data struktuur bekend as 'n stapel sal daar
'n heelgetal wees net bekend eenvoudig as grootte.
>> So as ek was om dit te stel nou picturaal, laat ons veronderstel dat hierdie
hele black box verteenwoordig my stapel.
Binnekant van dit is twee veranderlikes.
So ek gaan die te trek eerste een as grootte.
En die tweede een wat ek gaan te trek as 'n skikking.
>> Maar net om dinge te hou ordelike, Normaalweg sou ek 'n skikking trek soos
, maar dit is soort van 'n mooi As ons ooreen met die werklikheid, of
ooreenstem met die geestelike model.
So laat my plaas trek die skikking vertikaal, wat net weer,
kunstenaar se vertoning.
Maak nie regtig saak wat dit is onder die enjinkap.
En ons sal sê dat, by verstek, kapasiteit gaan word drie.
So dit sal plek 0, hierdie sal plek 1, kan dit wees
sal plek wees 2.
>> As ek omkoop met 'n stress bal, sou iemand wil om te kom en die loop
klim hier vir 'n oomblik?
OK, sien jou hand eerste.
Kom up.
Alle regte.
So ek glo dit is Steven.
Kom up.
Alle regte.
>> Maar ons dink nou rewind na die aanvanklike toestand van die wêreld waar ek
het nou net verklaar dat 'n stapel, en dit is gaan wees van kapasiteit drie.
Maar grootte is nog nie bepaal.
Bak het nog nie vasgestel nie.
So 'n paar vrae eerste.
En laat my gee u mic so jy kan deel meer aktief in hierdie.
>> So, wat is die binnekant van grootte op hierdie oomblik in die tyd as al wat ek gedoen het, is
verklaar 'n stapel met een lyn van kode?
>> STEVEN: Nie veel nie.
>> David Malan: OK, nie veel nie.
Ons weet wat binne in grootte, ons weet wat is binne
van hierdie reeks hier?
>> STEVEN: Slegs ewekansige kode, reg?
Net -
>> David Malan: Ja, ek gaan noem dit kode, maar ewekansige -
>> STEVEN: Dinge.
>> David Malan: Dinge soos ewekansige
>> STEVEN: Bits.
>> David Malan: Bits, reg?
So vullis waardes, reg?
So permutasies van 0's en 1's.
Oorblyfsels van die vorige gebruike van die geheue.
En ons weet nie regtig wat die waardes word, sodat ons gewoonlik trek hulle
as vraagtekens.
>> So die eerste ding wat ons is vermoedelik gaan hê om hier te doen nie -
en laat my gee hierdie veld binne van daar 'n naam - bak.
Wat moet ons vermoedelik inisialiseer grootte as ons wil
begin met hierdie stapel?
>> STEVEN: Tray is sub 3.
>> David Malan: So, OK.
Om duidelik te wees, is kapasiteit verklaar elders as drie.
En dit is wat ek gebruik die skikking toe te ken.
Grootte gaan om te verwys na hoeveel bak is tans op die stapel.
>> STEVEN: Zero.
>> David Malan: So dit moet wees nul.
So gaan voort, en met 'n vinger, trek 'n nul in grootte.
Alle regte.
So nou, wat binne in hierdie hier, weet ons nie.
Dit is regtig net vullis waardes.
Sodat ons kan trek vraagtekens, maar Kom ons hou die direksie skoon vir nou
want dit maak nie saak nie Wat is daar.
Ons hoef nie die skikking te inisialiseer aan enigiets nie, want as ons weet dat
die grootte van die stapel is nul, goed, ons moet nie kyk na enigiets in
hierdie verskeidenheid in elk geval op hierdie punt in die tyd.
>> So nou dink dat ek stoot die nommer 9 op die stapel.
Hoe moet ons werk om die data struktuur binnekant van hierdie swart boks?
Watter waardes nodig het om te verander?
>> STEVEN: Binne -
die grootte?
>> David Malan: OK.
Grootte moet word wat?
>> STEVEN: Grootte een sal wees.
>> David Malan: OK.
So grootte moet een word.
So jy kan dit doen in 'n paar maniere.
Kom ek gee jou nou jou vinger is 'n uitveër.
Alle regte.
Dan is dit nou jou vinger is 'n kwas.
Alle regte.
Maar nou, wat anders het om te verander, natuurlik, in die data struktuur?
>> STEVEN: Ons gaan uit bodem tot 9.
>> David Malan: 9.
OK, Good.
So nog steeds maak nie saak wat is op plek een of twee, want hulle is
vullis waardes, maar ons moet nie die moeite soek daar omdat grootte is
om ons te vertel dat slegs die eerste element is eintlik wettig is.
So nou is ek stoot 17 op die lys.
Wat gebeur met hierdie prentjie?
>> STEVEN: So grootte gaan om te gaan vir twee.
>> David Malan: OK.
Jy is uitveër -
Oeps.
Jy is 'n uitveër.
>> STEVEN: Eraser.
>> David Malan: Jy is 'n kwas.
>> STEVEN: Borsel.
>> David Malan: OK.
En wat anders?
>> STEVEN: En dan moet ons -
>> David Malan: Ons gestoot 17.
>> STEVEN: Ons bly op die top 17, so -
>> David Malan: OK, goed.
>> STEVEN: - laat val dit neer.
>> David Malan: Alle reg.
Dit raak maklik nie.
Ek gaan nie om jou te help om hierdie tyd.
Druk 22.
>> STEVEN: gebraai.
Word 'n uitveër.
Ek is besig om 'n kwas.
En dan is ek om 22.
>> David Malan: 22.
Uitstekend.
So een keer.
Ek gaan nou te druk op die stapel 26.
>> STEVEN: Ooh.
Oh gosh.
Jy moet regtig my onkant gevang.
>> David Malan: Jy het nie sien kom?
>> STEVEN: Ek het nie sien kom.
Kan ons weer aanvanklike kapasiteit?
>> David Malan: Dit is 'n goeie vraag.
So het ons soort van geverf onsself in 'n hoek hier.
Daar is regtig geen goeie uit vir Steven want ons het toegeken die verskeidenheid
staties, om so te spreek, binne van die data struktuur.
En ons het in wese hard gekodeer dit van groot drie.
So kan ons regtig nie meer inzetten dit.
>> Ons kan as ons gaan terug in ons geherdefinieer bak om 'n wyser wat wees
Ons gebruik dan malloc om hand geheue.
Want as ons het die geheue van die hoop via malloc, ons
dan kan bevry.
Maar voordat bevry het, kon ons hergebruik van 'n groter deel van die geheue,
werk die wyser, en so meer.
Maar vir nou, dit is regtig die beste wat ons kan doen.
Stoot en pop is vermoedelik gaan het 'n paar foute aan te dui.
>> So byvoorbeeld, ons implementering van die druk kon terugkeer 'n Bool wat
voorheen teruggekeer waar, waar, waar is.
Maar die vierde keer, dit gaan te hê om terug te keer vals is, byvoorbeeld.
Alle regte.
Baie goed gedoen.
Baie geluk.
Jy verdien jou stress ball vandag.
>> [Applous]
>> STEVEN: Dankie.
>> David Malan: Dankie.
OK, so dit blyk te wees nie veel van 'n stap vorentoe, reg?
Ons beskryf hierdie data struktuur.
Dit was dwingende, reg?
Bedryfstelsels soos dit.
Blykbaar het die web kan gebruik maak van hierdie, en ander programme het nog steeds.
Maar wat 'n dom beperking dat ons terug na die soort van week twee grense
waar ons vaste grootte skikkings.
>> So daar is wel 'n paar maniere waarop ons kan oplos nie.
Ons kon dinamiese ken die skikking, nie deur harde kodering dit soos ek
wat hier gedoen word nie, maar eerder weer verklaar hierdie, om net duidelik wees, soos
iets soos hierdie.
Int * bak, nie besluit op 'n kapasiteit nie.
Maar toe ek verklaar dat die stapel elders in my kode, kon ek dan bel malloc,
kry die adres van 'n stuk van geheue, en ek kon opdra
daardie adres te bak.
>> En dan, want dit is net 'n stuk van geheue, kan ek voortgaan om te gebruik vierkante
hakienotasie in die gewone manier.
Omdat weer, daar is soort van hierdie funksionele ekwivalent van skikkings en
stukke van die geheue wat kom terug van malloc.
Ons kan hanteer een as die ander gebruik wyser rekenkundige of
vierkante hakienotasie.
So dit is een benadering.
>> Maar hoe anders kan ons hierdie dieselfde data struktuur, potensieel?
Reg?
Ek voel soos ons net hierdie opgelos probleem soos 'n week gelede.
Wat was die oplossing vir die probleem dat Steven gehardloop in?
So gekoppel lyste, reg.
>> As die probleem is dat ons verf onsself in 'n hoek deur die toekenning
vooruit te min geheue dat ons dan het een of ander manier om dit te hanteer, goed,
Waarom nie net verhoed dat reik altesaam?
Waarom nie net verklaar bak te wees om 'n wyser na 'n knoop, ergo 'n gekoppelde lys
en dan net toeken nuwe nodes elke keer Steven nodig om 'n aan te pas
nommer in die data struktuur.
>> So het die prentjie sou hê om te verander.
Dit gaan nie so skoon en as eenvoudig soos net 'n skikking van drie ints.
Nou gaan dit 'n verwysing na 'n wees struct, en dat struct gaan
het 'n int en 'n volgende wyser.
Dit gaan lei via dat wyser om nog so 'n struct te
nog so 'n struct.
So het die prentjie sou eintlik kry 'n bietjie morsig.
En ons wil pyle het vasmaak alles saam.
>> Maar dit is goed, reg, want Ons het gesien hoe om dit te doen.
En as jy gemaklik implementering van iets soos 'n gekoppelde
lys, wat jy hoef te doen, as jy kies 'n hash tafel te implementeer met
afsonderlike chaining vir p-set 6, kan jy gebruik dit as 'n boublok, of 'n
bestanddeel, of in Scratch praat, 'n prosedure, iets wat jy het, het jy
geskep jou eie legkaart stuk wat jy dan kan onthou.
So werkinge, maar moontlike oplossings dat ons het eintlik gesien het nie.
>> So dikwels, jy sien dit elke jaar of twee wanneer Apple uitgawes
iets nuuts, en al die mal mense line-up buite die Apple
slaan hul marginale te koop gradeer op die hardeware.
Ek sê dit, dit is OK, want Ek is een van daardie mense.
So watter soort data struktuur kan verteenwoordig dit die werklikheid?
>> Wel, kom ons noem dit 'n tou, 'n lyn.
So Britse noem dit tipies 'n ry in elk geval, so dit is 'n mooi naam.
En die twee operasies wat 'n tou sal ondersteun ons sal 'n enqueue noem
werking en 'n dequeue operasie, wat soortgelyk is in
gees te stoot en pop.
Dit is net soort van verskillende in konvensie, wat ons noem hierdie.
Maar om iets te enqueue beteken om by te voeg of plaas dit aan die data struktuur.
Om dequeue beteken om dit te verwyder.
Maar dat 'n stapel was 'n LIFO data struktuur, 'n ry is 'n eerste in,
eerste uit data struktuur.
>> As jy die eerste persoon in die lyn, jy sal die eerste persoon te kry
uit van die lyn en koop jou nuwe toestel.
Stel jou voor hoe ontsteld hierdie mense sou wees As Apple plaas gebruik om 'n stapel, vir
byvoorbeeld, te implementeer die pluk up van jou nuwe speelding.
So toue sin maak, beslis, en ons kan dink van alle vorme van
aansoeke, vermoedelik, vir toue, veral wanneer jy wil regverdigheid.
So, hoe kan ons die uitvoering van hierdie as 'n data struktuur?
>> Wel, ek stel voor dat ons dalk nodig het om te doen dit op hierdie manier.
So ek gaan nou 'nommers.
Dus sal ons hou dit eenvoudig en nie noodwendig praat in terme van bak.
Net getalle wat mense van gekry.
Kapasiteit gaan, weer, los die totale aantal mense wat gebruik kan word in
hierdie lyn, as drie of enige ander waarde.
>> Maar ek stel voor dat ek nodig het om tred te hou nie net van die grootte van die
ry, hoe baie dinge in dit.
So grootte is die huidige grootte, kapasiteit is die maksimum grootte.
Net weer, naam deur konvensie.
Hoekom moet ek 'n bykomende int binne van 'n tou om tred te hou van wat is in
voorkant van die lyn?
Hoekom het ek nodig om dit te doen in hierdie geval?
>> Wel, hoe is hierdie foto gaan verander?
Ek kan waarskynlik onthou van hierdie prentjie.
Laat my gaan voort en vee wat hier is.
Ons gee dit 'n bietjie verskillende name hier.
Kom ons ontslae te raak van die 17, laat ons ontslae te raak van die 9, laat ons ontslae te raak van die 3.
En laat ons voeg 'n ander ding.
Ek stel voor dat ek nodig het om tred te hou van die voorkant van die lys, wat net
gaan na 'n int so goed.
En ons gaan dit eenvoudig te hou.
Geen gekoppel lys vir nou.
>> Ons sal erken dat ons gaan stamp teen hierdie limiet.
Maar wat ek wil sien gebeur hierdie tyd?
So dink ek gaan voort en die eerste persoon kom in lyn, en
dit is die nommer 9.
Ons het stres balle.
Kan ek steel, sê, twee of drie mense?
Een, twee, drie?
Kom up.
Reg van voor, want ons sal hierdie een vinnig.
>> Elkeen van julle is nou gaan wees 'n fan seuntjie in die lyn by Apple.
Jy sal nie ontvang word Apple hardeware aan die einde van hierdie al.
Alle regte.
So jy is die nommer 9 is, is jy nommer 17, nommer 22.
Dit is arbitrêre syfers, soos student ID's of iets anders.
En in 'n oomblik, laat ons begin om te begin om dinge.
En ek sal die raad hier loop hierdie tyd.
>> So in hierdie geval, het ek geïnisialiseer die front te wees -
Ek het eintlik nie regtig omgee wat die Voor is, omdat die grootte is nul.
So dit kan net sowel 'n vraagteken.
Dit is al die vraagtekens.
So nou gaan ons begin om werklik te sien dat sommige mense aantree by die winkel.
>> So as nommer 9, jy is die eerste een daar op 05:00, gaan voort en line-up,
of die nag voor.
OK.
So nou 9 is hier.
So 9 is in die voorkant van die lys.
So ek gaan om voort te gaan en werk die grootte van die huidige data
struktuur nie 0 wees nie, maar om te wees 1.
Ek gaan 9 te sit op die voorkant van die lys.
Laat my gaan voort en skakel die skerm sodat ons kan sien verby ons hier.
>> En nou wat ek wil te stel voor?
Ek gaan om tred te hou dat die voorkant van die tou nou
is by die plek 0.
Want wat volgende gaan gebeur nie?
Wel, dink ek nou enqueue 17 as well.
So hop in lyn is daar.
En weer, die soort van deur tot die winkel gaan om hier te wees.
So nou het ek bygevoeg 17.
En selfs al is hierdie ouens is die sluit die skerm, dit is OK,
want ons kan dit sien hier.
Jammer.
>> Publiek: Ons kan beweeg -
>> David Malan: Nee, dis OK.
Dit is 'n groot daar.
So 17 is nou binnekant van die tou.
Ek nodig het wat om te werk gebied nou al is?
OK, beslis grootte.
En hoe oor die front?
OK, no.
Front moet nie verander nie, omdat In teenstelling met 'n stapel, ons
wil regverdigheid in stand te hou.
So as 9 gekom het in die eerste, ons wil 9 te wees van die eerste uit die lyn
en in die winkel.
>> In werklikheid, laat ons sien dat.
Voordat ons plaas 22, laat gaan voort en dequeue 9.
Wat is jou naam nou weer?
>> Gehoor deur Jake.
>> David Malan: Jake gaan word nou dequeued.
So jy om te loop in die winkel.
En voor te gee dat die winkel is daar.
So nou wat nodig is - hierdie-dit-dit!
Wat moet nou gebeur?
Ontwerp besluit.
Dus nie 'n slegte instink, maar - Wat is jou naam nou weer?
>> GEHOOR: David.
>> David Malan: David.
So wat het Dawid doen?
Hy het probeer om uit te sorteer los die data struktuur en beweeg van sy plek
in Jake se voormalige plek.
En dit is goed as ons bereid is om wat om te aanvaar as 'n
implementering detail.
Maar eers, laat se werk om die data struktuur voordat ons dit doen.
Omdat ek nie hou van die idee van alle die mense verskuiwing in hierdie lyn.
>> Dit is nie 'n groot deal as Dawid doen dit met 'n stap, maar weer, dink terug aan
wanneer ons het agt vrywilligers op die stadium en ons het gedoen soos die inplanting
soort, waar ons gehad het om te begin beweeg almal rondom.
Dit het duur is, reg?
Dit maak my ineenkrimp oor die groot O van N, groot O van n vierkant weer.
Dit is nie gevoel soos 'n ideale uitkoms.
>> So laat ons net werk hierdie.
So het die grootte van die tou is nie meer 2.
Dit is nou net 1.
Maar ek kan nou by iets Ek het nie voor te werk, die
voorkant van die lys.
Ek kon net sê, is dat die plek 1?
So nou het ons vullis waarde hier, vullis waarde hier, en Dawid in die
middel van hierdie gemors.
Maar die data struktuur is nog ongeskonde.
>> En in waarheid te sê, ek het nie eens nodig het om te verander Jake se voormalige nommer
9, omdat wat omgee.
Ek het nie genoeg inligting nou in die grootte wat ek weet daar is een persoon in
hierdie tou.
En ek weet dat daardie persoon is by die plek 1 nie 0.
Ek is nie die tel.
So 1 as well.
So het die data struktuur is nog OK.
>> Wel, wat gebeur volgende?
Let's enqueue -
Wat is jou naam?
>> GEHOOR: Callen.
>> David Malan: Callen.
Kom ons enqueue n Callen, en 22 is nou in die ry.
So nou wat het hier te verander nie?
Front is nie van plan om te verander, natuurlik.
Grootte gaan verander om te wees 2.
En 22 eindig hier, 9 is nog steeds teenwoordig is, maar dit is eintlik 'n
vullis waarde nou.
Dit is net 'n oorblyfsel van Jake verlede.
>> So nou wat gebeur as Ek dequeue Dawid?
Een laaste operasie, dequeue David.
Ons kon skuif, maar ek stel voor laat se doen so min werk as moontlik.
Nou is my data struktuur gaan terug in grootte 2-1.
Maar die voorkant van die tou nou raak 2.
Ek het nie nodig om hierdie getalle te verander net nog nie, want hulle is
net vullis waardes.
>> Maar nou wat gebeur?
Dink ek enqueue myself, 26?
Ek voel soos ek hoort hier.
So word ek waglys.
So ek soort van hier hoort nie.
En selfs al is jy nie heeltemal waardeer dit visueel op die verhoog,
want ons het baie van die kamer, ek moet nie hier staan, hoekom?
>> Publiek: Jy is buite perke.
>> David Malan: Right.
Ek is buite perke.
Ek het geïndekseer buite die grense van die skikking.
Ek het regtig moet in een van die drie moontlike plekke.
Nou, is waar die meeste natuurlike om te gaan?
Ek stel voor ons aged 'n week 'n truuk.
Die mod operateur, persentasie.
Want ek is tegnies staan ​​by plek 3, maar ek doen 3 mod kapasiteit,
so 3, 'n persent teken, 3 -
kapasiteit is 3.
Wat is dit?
Wat is die res as jy deel 3 deur 3?
0.
>> Sodat plaas my is Jake was, Dit is eintlik 'n goeie.
So nou is die implementering van hierdie ding gaan
wees om 'n bietjie van 'n hoofpyn.
Dit is regtig net een lyn van hoofpyn, van die kode.
Maar ten minste nou is daar vullis waarde hier, maar daar is twee
wettige ints hier.
En ek eis dat ons nou gedoen presies wat ons nodig het om so lank as wat dit doen
ons verander wat Jake se waarde was om te wees 26.
>> Ons het nou genoeg inligting steeds die integriteit te handhaaf
van hierdie data struktuur.
Ons is nog steeds soort van geluk wanneer ons wil vier of meer totale te voeg
elemente, maar ek kan ten minste maak mooi doeltreffende gebruik van hierdie konstante
tyd, in werklikheid.
Ek hoef nie te bekommerd wees oor die verskuiwing almal, soos Dawid se neiging was.
>> Enige vrae oor stapels, of die tou?
>> GEHOOR: Is die rede waarom wat jy nodig grootte, sodat jy weet
waar 'n persoon te hê?
>> David Malan: Presies.
Ek moet die grootte van die skikking te weet omdat ek nodig het om te weet presies hoe
baie van hierdie waardes is wettig, en sodat ek kan vind waar om te sit
die volgende persoon.
Presies.
Die grootte is -
Eintlik het ons nie werk hierdie nie.
Ek het ook myself op 26.
Die grootte is nou, nie 1 nie, maar 2.
So nou is dit help my werklik vind die hoof van die lys, wat nie 0 is nie, nie
1, maar is 2.
Die voorkant van die lys is inderdaad nommer 22.
Want hy het in die eerste, so moet hy toegelaat word om in die winkel voor my,
selfs al is visueel Ek staan nader aan die winkel.
>> Alle reg?
'N rondte van applous vir hierdie ouens en ons sal jou laat hulle daar uit.
>> [Applous]
>> David Malan: Ek kon laat jy hou die skinkbord.
Ons kon sien wat gebeur as jy wil, maar miskien nie.
Alle regte.
So, wat nou laat dit ons?
Wel, laat ek stel voor dat daar 'n n paar ander data strukture wat ons kon
begin toe te voeg tot ons gereedskapskis wat eintlik baie, baie relevant wees
ons duik in web dinge.
Wat weer, het 'n soort van die verband aan bome in die vorm van
iets genoem DOM, dokument voorwerp model.
Maar ons sal sien meer van wat kort voor lank.
>> Laat my definitionally stel voor dat ons noem boom nou wat jy dalk ken as
meer van 'n stamboom, waar jy het 'n paar voorloper op die
wortels van die boom.
'N patriargale of 'n matriarg by die top van die boom.
Sonder hul gade, in hierdie geval.
Maar nou het ons wat ons bel kinders, wat nodes wat hang is
af die linker kind of die regte kind, pyle soos aangedui hier.
>> Met ander woorde, in 'n boom data struktuur in die rekenaar, 'n boom het 'n nul
of meer nodes.
As dit het ten minste een knoop, Dit is genoem die wortel.
Dit is die dinge wat visueel ons trek aan die bokant.
En dat knoop, soos enige ander node, kan nul, een, of twee, of drie,
of hoeveel kinders die data struktuur ondersteun.
In hierdie geval, die wortel, die stoor van die waarde een, het twee kinders, 2 en 3,
sodat ons in die algemeen noem 2 links kind en 3 die regte kind.
>> En dan wanneer ons tot 5, 6, en 7, 6 genoem kan word die middelste kind.
As jy het vier kinders, dit raak verwarrend.
So ons ophou om daardie soort van kortpad mondelings.
Maar dit is eintlik net 'n stamboom.
En die blare hier is die nodes wat self het nie kinders nie.
Hulle hang af van die onderkant van die boom.
>> So, hoe kan ons die uitvoering van 'n boom wat het net twee kinders maksimaal?
Ons noem dit 'n binêre boom.
Bi weer beteken dat twee, in hierdie geval, soos met die program nie.
En so kan dit nul, een, of twee kinders maksimaal.
>> Ek sal voorstel dat ons die uitvoering van die knoop vir daardie struktuur met 'n int n,
en dan twee wysers, een wat geroep verlaat het, een wat geroep is reg.
Maar dit is net mooi arbitrêre konvensies.
En wat is nou lekker, veral as jy soort gesukkel konseptueel met
rekursie, of het gedink dat dit was nie regtig 'n oplossing vir enigiets,
veral as jy kon loop uit van die geheue.
Nou dat ons praat oor data strukture en algoritmes wat toelaat
om ons te loop en te manipuleer hulle blyk dat rekursie terug kom in
'n baie meer dwingende Indien nie mooi manier.
>> So het ek stel voor die implementering van 'n soek funksie.
Gegewe twee insette -
so dink van hierdie as 'n swart boks.
Gegewe twee insette, n, 'n int, en 'n wyser aan 'n boom, 'n verwysing na 'n
knoop, of eintlik die wortel van 'n boom, ek eis dat hierdie funksie kan terugkeer
waar of vals is, wat waarde n is die binnekant van die boom.
>> Wat is die binnekant van hierdie swart boks?
Wel, vier takke.
Die eerste net kontroleer.
As boom is nul, net terug vals.
As daar is geen knoop, is daar geen n, daar is geen nommer, net terug vals.
As al is, n, die waarde wat jy op soek is na vir, is minder as boom pyl n, en
net om duidelik te wees, wat beteken dit wanneer Ek skryf boom en dan die pyl
notasie, n?
Presies.
Dit beteken dat dereference wyser genoem boom.
Gaan daar, en dan kry binnekant van daardie knoop en kry sy gebied genoem n.
En vergelyk dan die werklike n wat was geslaag het in Soek daarteen.
>> So as n minder is as die n waarde in die boom knoop self, goed,
wat beteken dit?
Dit beteken niks met die eerste oogopslag.
Reg?
Net soos wanneer jy 'n verskeidenheid van waardes, kan jy wil binêre om aansoek te doen
soek as 'n vorm van skeiding en oorwin.
Maar wat aanname het ons nodig het om te maak vir binêre soektog te op alle werk
in die telefoon boek en vroeër voorbeelde?
>> Hoe om te sorteer word.
So laat verfyn die definisie van die boom hier te wees nie net 'n boom, wat kan
enige aantal kinders.
Nie net 'n binêre boom, wat kan het 0, 1 of 2 maksimaal.
Maar as 'n binêre soek boom, of BST, Dit is net 'n fancy manier om te sê 'n
binêre boom sodanig dat elke node se links kind, indien teenwoordig, is
minder as die knoop.
En elke node se reg om kind, indien teenwoordig, is groter
as die knoop self.
>> So met ander woorde, as jy was om te trek die boom uit, al die getalle
versigtig gebalanseer soos hierdie so dat indien jy het 55 as die wortel, kan 33 gaan
aan die linkerkant, want dit is minder as 55.
77 kan gaan na die reg, want dit is groter as 55.
Maar nou sien, dieselfde definisie, dit is 'n rekursiewe definisie mondelings,
het om aansoek te doen vir 33.
33 se linker kind moet minder wees as dit, en 33 se reg om kind, 44, moet
groter as dit.
>> So dit is 'n binêre soek boom, en Ek stel voor, met behulp van 'n bietjie
rekursie, ons kan nou n.
So as n minder is as die waarde n dis knoop, ek gaan om te gaan
voor en Punt, om so te praat, en net terug te keer wat die antwoord is
soek na n op die boom se linker kind.
Let weer op, hierdie funksie net verwag 'n knoop ster, 'n
wyser na 'n knoop.
So ja, ek kan net doen boom pyl links, wat sal lei
my na 'n ander knoop.
Maar wat is dit nodig?
>> Wel, volgens hierdie verklaring, links is net 'n muis, sodat net
beteken ek is verby die soek funksie 'n ander wyser, naamlik
die een wat verteenwoordig my linker kind se boom.
So in hierdie geval, die wyser na 33, indien dit is ons voorbeeld insette Intussen, as
n groter is as die waarde n by die knoop in die boom, dan is ek
gaan voort en punt gaan in die ander rigting en net sê, ek doen nie
weet as hierdie waarde n is in die boom, maar ek weet nie of dit is, is dit in my
regte tak, om so te praat.
So laat my rekursief noem soek, verby 'n weer, maar die verbygaan in 'n
wyser na my reg kind.
>> Met ander woorde, as ek tans op 55 en ek is op soek na 99, ek weet dat 99
is groter as 55, so net soos ek skeur die telefoon boek weke gelede en ons
het reg, net soos ons is gaan hier gaan.
En ek weet nie of dit is op my reg kind, en dit is nie, 77 daar is nie, maar
Ek weet dit is in daardie rigting.
So ek noem soektog op my regte kind, 77, en laat soek figuur uit
is daar as 99 in hierdie arbitrêre voorbeeld is eintlik daar.
>> Anders, wat is die finale geval?
As boom is van nul is een geval.
As n minder is as die huidige knoop se waarde is 'n ander saak.
As n groter is as die huidige node se waarde is 'n derde geval nie.
Wat is die vierde en laaste geval?
Ek dink ons ​​is uit van die gevalle, reg?
Dit moet wees dat n is in die knoop dat ek op.
>> So as ek is op soek na 55 op hierdie punt in die storie, wat tak van die
boom sou terugkeer waar.
So, wat is interessant hier is dat ons eintlik, in teenstelling weke verlede, het ons soort
van twee basis gevalle.
En hulle het nie aan wees al aan die bokant.
Die top is 'n basis geval, want as die boom is nietig, daar is niks om te doen.
Gaan terug 'n harde gekodeerde waarde van vals.
>> Die onderste tak is 'n soort van die verstek, waardeur as ons nagegaan word vir
nul, het ons gekyk as wat dit moet wees gelaat, maar dit moet nie, het ons
nagegaan word of dit moet reg wees, maar dit moet wees nie, dit duidelik te wees
reg waar ons is.
Dit is 'n basis geval.
So is daar twee gevalle rekursiewe landgebonde daar in die middel.
Maar ek kon geskryf het dit in enige volgorde.
Ek het net gedink dit soort van gevoel natuurlike om eers vir 'n moontlike fout
dan gaan verlaat, dan regs gaan, dan aanvaar dat jy by die knoop
jy is eintlik op soek na.
>> So hoekom kan dit nuttig wees?
So dit blyk -
en laat my spring na 'n teaser hier wat in die web.
Ons gaan om te begin gebruik nie 'n programmeertaal op die eerste, maar 'n
opmaak taal.
'N opmaak taal as een wat soortgelyke in gees tot programmering
taal, maar dit gee jou nie die vermoë om jouself te logies uitdruk.
Dit gee net jy die vermoë om te druk jouself struktureel.
>> Waar wil jy iets om te sit op die bladsy, die webblad?
Wat is die kleur wil jy dit te maak?
Wat lettergrootte wil jy dit te maak?
Watter woorde doen jy eintlik wil op die webblad?
So dit is 'n opmaak taal.
Maar dan sal ons baie vinnig stel JavaScript, wat 'n volwaardige
programmeertaal.
Baie soortgelyk sintakties in voorkoms tot C, maar dit sal 'n paar
mooi, meer kragtige, meer gebruikers vriendelike kenmerke.
>> En een van die frustrasies op hierdie punt in die semester is dat ons sal
gou implementeer speller in veel minder reëls van die kode gebruik van ander tale
as C homself toelaat nie, maar vir die rede se Ons sal gou verstaan.
Dit sal die eerste sodanige webblad wees.
Dit sal heeltemal underwhelming, Die eerste een wat ons maak.
Dit sal net sê, hallo wêreld.
Maar as jy dit nog nooit gesien voor, dit is HTML,
HyperText Markup Language.
>> As jy na 'n sekere opsie in die meeste 'n leser, op 'n webblad op
die internet, kan jy sien die HTML dat sommige mense het om te
skep dat die webblad.
En dit is waarskynlik lyk nie kort of so netjies nie.
Maar dit sal die patroon van hierdie oop tussen hakies en houe en
letters en potensieel nommers.
>> Ek het gedink ek wil vir jou 'n teaser van wat jy sal in staat wees om te doen
nadat CS50.
Laat my gaan cs.harvard.edu / beroof, ons eie Rob Bowden se tuisblad.
Hy het dit vir ons.
So jy sal binnekort in staat wees om dit te doen.
En ook, wat jy hoor vanoggend -
wat jy gehoor het vanoggend -
>> [HAMSTER dansmusiek]
>> - You'll in staat wees om dit te maak.
Wat op ons wag op Woensdag.
Ons sal sien jy dan.
>> [HAMSTER dansmusiek]
David Malan: By die volgende CS50 -