>> [Muziek]
CAMILLE REKHSON: Hallo, iedereen.
Welkom op de CS50 quiz nul beoordeling sessie.
Ik ben Camille.
En ik ga om te gaan over een aantal onderwerpen met u
jongens vandaag de dag om u te helpen voor te bereiden op de quiz.
Dus hier is onze niet-exhaustieve lijst met onderwerpen die u
bekend voor de quiz moeten zijn.
Deze werden direct genomen van de syllabus.
Ik weet dat het lijkt veel.
Maar geloof me, heb je al geleerd deze dingen in de afgelopen weken.
>> Dus we zullen zeker gaan dan veel van deze vandaag.
Maar ook enige tijd in beslag nemen op uw eigen om deze dingen te herzien.
En als je bekend bent met niet wat sommige van deze dingen zijn,
zorg ervoor dat je een van ons vragen.
Ook voor de officiële woord op de quiz, ga naar deze link.
Dit zal alle informatie met welke kamer je nodig hebt om in te gaan,
opgesplitst alfabetisch, en ook een aantal tips over wat materialen
je moet studeren, en wat voor soort quiz vragen die u kunt verwachten.
Dus zorg ervoor om te controleren dat uit.
>> Ook zijn enkele tips voor wanneer je bereiden zich voor op het examen.
Oefen codering op papier.
Ik weet dat je gewend aan het hebben van de IDE cheque voor je fouten voor u,
en it's-- wanneer u typt het op, het is een beetje anders dan het hebben
om dingen uit te schrijven.
Dus de praktijk doen wat codering.
Enkele goede functies om te oefenen doet zijn strlen en atoi,
zien als je zou kunnen schrijven die op uw eigen.
Wees vertrouwd met het probleem sets.
De meeste jaren zijn vragen die betrekking hebben
sommige van de Probleemverzameling materiaal.
Dus zorg ervoor dat u begrijpt hoe aan alle probleem sets te doen.
>> Probeer een aantal van de oude quizzen doen onder de 75 minuten tijdsdruk.
Een groot deel van de quizzen kan soort lang zijn.
Dus het is een goede manier om te geven je enige oefening,
en hoe lang het zal nemen u mee, en hoe je
moet je tijd verdelen om ervoor te zorgen je alles eindigen met het einde.
En ook, een één pagina krijg je, tweezijdige referentie sheet
dat je kunt schrijven wat je wil op te gebruiken tijdens de quiz.
Dus als je het creëren dat, dat is ook
echt een geweldige manier om te studeren, omdat je soort dingen worden herzien
als je het schrijven ervan.
>> Zodat eventuele algemene vragen over de quiz, of hoe het werkt?
Ja.
>> PUBLIEK: Zal ​​dat de lijst van onderwerpen dat je gewoon toonde voor ons beschikbaar te zijn
online?
>> CAMILLE REKHSON: Deze hele slide show zal worden geplaatst op de website.
Ook de video van beoordeling van vandaag sessie zal zijn op de website.
Dus niet te veel zorgen over te maken het schrijven van dingen naar beneden in.
Het zal er allemaal.
Een andere vragen?
OK, dus laten we beginnen.
>> Dus een ding om vertrouwd te raken met zijn is de verschillende gegevenstypes en de grootte
dat ze nemen.
Dit kan ook een groot ding te zijn noteer op uw referentie vel,
gewoon om ervoor dat u herinner me al deze.
Maar-- dus chars zijn 1 byte.
Ints zijn 4 bytes.
Een lange, lange, die in feite meer ruimte voor een geheel getal is 8 bytes.
Een float is 4 bytes.
Een dubbele, die in feite geeft u meer ruimte om een ​​vlotter te slaan, is 8 bytes.
Dan is een pointer 8 bytes.
Heeft u vragen over deze?
>> Dus binaire is een ander onderwerp wij hebben bedekt een beetje dit semester.
Dus laten we doen wat oefenen met het omzetten
tussen de binaire en decimale.
Dus iemand enig idee wat dat de eerste zou zijn?
Iedereen?
Ja, het is 42.
Dus als je nog, elk van de plaatsen in binaire
is in principe net als 2 aan de macht van die plaats.
>> Zodat de eerste plek is 2 tot de macht 0.
En we hebben er 0, dus niets.
De volgende plaats is 2 tot de eerste stroom.
En we hebben een 1 daar, dus dat is eigenlijk een 2.
De volgende plaats is 2 tot de tweede, die 4.
We hebben niets daar.
De volgende plaats over 2 tot de derde, die 8 zijn.
En we hebben er één.
En we blijven gaan.
Dat last-- het meest naar linker is waar we hebben 32.
En ja, we hebben eigenlijk hebben 32 plus 8 plus 2 te krijgen 42.
Nog vragen?
>> PUBLIEK: Wat is het onderschrift voor?
>> CAMILLE REKHSON: Het onderschrift vertelt ons in feite dat het binaire.
Dus er is een 2 daar.
Als er like-- de komende één, of als we het omzetten van decimaal
binaire, er is een 10 toont ons dat Dit nummer is oorspronkelijk in decimalen.
>> Publiek: Dank je wel.
>> CAMILLE REKHSON: Ja.
Andere vragen op die ene?
OK, dus laten we proberen de volgende men dan, decimaal naar binair.
Zodat het nemen van 50 en zetten die in binaire.
Hoe zou je dat doen?
Ja.
>> Publiek: 110.010.
>> CAMILLE REKHSON: Ja.
Dus een-- een gemakkelijke manier om na te denken over omzetten van decimaal naar binair
is to-- het vaak helpt om uit te schrijven wat de verschillende machten van 2 zijn.
En ga er doorheen, en zie ongeacht de hoogste van die
is dat je in kunt zetten om de decimaal getal zonder erover.
>> Dus in dit geval, een van de bevoegdheden van 2 is 32.
Zo gaat in 50 32.
Maar de volgende power up zou zijn 64, die uiteraard niet past in 50.
Dus de hoogste we hebben is het 32.
De volgende omlaag naar 16.
En 32 plus 16 is slechts 48.
Zodat nog steeds past in 50.
Dus hebben we 1 in deze beide.
En dan, als we blijven naar beneden gaat, het enige wat we hoeven vertrokken
2 meer te krijgen 48-50.
Dus dan hebben we een 1 op die positie, en een 0 in de laatste positie.
Omdat er niets in de 2 naar de 0-ste plaats.
Vragen over het omzetten decimaal naar binair?
>> Dus laten we nu proberen te doen sommige binaire toevoeging.
Wat als je die twee optellen?
Ja.
>> Publiek: 11.100.
>> CAMILLE REKHSON: Ja.
Daarbij toevoeging in binaire is vrij veel hetzelfde als doen in decimalen.
Behalve als je twee 1's wezen Opgeteld 1 plus 1 is 2,
maar 2 in binaire 1 is 0.
Dus je moet dragen de 1, en houdt de uitvoering ervan voor die paar kolommen.
En anders dan dat, voeg dan normaal.
Heeft u vragen over dat?
Ja.
>> PUBLIEK: Sorry, wat is de laatste plaats?
Er is zes nummers.
Dus de linkerkolom, welke waarde is het?
CAMILLE REKHSON: Op de onderste?
PUBLIEK: Op de bovenste, voor 50.
CAMILLE REKHSON: Voor 50?
Oh, dus de meest linkse ene is 32.
>> Publiek: 32?
>> CAMILLE REKHSON: Ja, dus het zou zijn 32, 16, vervolgens 8, 4, 2, 1 of 0--.
Nou, het is 2 de nulde, dat is 1.
Ja.
Andere vragen over dit?
OK, dus dan gaan we doen een beetje met hexadecimaal.
Dus dit misschien een iets minder bekend,
omdat ik weet dat we hebben gedaan veel meer met binaire.
Maar echt een goede manier om na te denken over hexadecimale
is te doorbreken een binair getal in 4-bits brokken.
Omdat elk 4 bits van een binaire getal is eigenlijk
één van de hexadecimale getallen.
>> Dus als we dit eerste, We hebben in feite acht 1 is.
Dus die kunnen worden gesplitst up--
>> Publiek: 255.
>> CAMILLE REKHSON: Zeg dat nog eens.
Publiek: 255 in decimale, of 0xFF in hexadecimaal.
CAMILLE REKHSON: Ja, het is.
Dus, als je splitsen dat tot in twee 4-bits brokken,
We hebben in principe vier reeksen 1.
Dat is de maximum-- principe de maximale
we kunnen krijgen met 4-bits binaire.
En het maximum dat we konden krijgen voor die in hexadecimaal zou zijn F.
Dus zouden we hebben twee F's.
Heeft u vragen over dat?
Ja?
>> PUBLIEK: Kunt u dat herhalen.
CAMILLE REKHSON: Zeker.
Dus elke, in principe, plaats van de hexadecimale is
gelijk aan het 4-bits van een binair.
Dus de makkelijkste manier om dit te doen is het opsplitsen in 4-bits brokken.
Dus in dit geval, hebben we acht 1's.
Dus als we splitsen die in twee 4-bits brokken,
we zouden hebben twee sets van vier 1's.
En elk van deze overeenkomt met F.
Als u denkt dat about-- Ik weet dat onze hersenen
soort bedraad te denken meer door middel van decimaal,
want dat is wat we gewend zijn.
Dus een manier waarop je zou kunnen denken als vier 1 gelijk is aan 15 in decimalen.
En 15 in hexadecimaal is F. Dus dat is een andere manier die je kunt bedenken doorheen.
Ja.
>> PUBLIEK: Wat is het 0x voor?
>> CAMILLE REKHSON: De 0x geeft aan dat het hexadecimaal.
Zodat we alleen dat prefix daar normaal.
Andere vragen over die.
OK, dus laten we proberen te gaan de andere kant op dan.
In dit geval have-- we spijt?
PUBLIEK: [onverstaanbaar].
CAMILLE REKHSON: We gaan naar binair.
Dus, gaan de andere kant op.
Maar in dit geval hebben we 5 en A. Dus als we denken over dit,
Als elk van de those-- 5 en A zijn zowel gaan naar een 4-bit brok vertegenwoordigen,
hoe zou je zeggen 5 in binaire?
>> Publiek: 0101.
>> CAMILLE REKHSON: Ja, dus dat is de 0101 deel.
En hoe zou je zeggen Een in--
>> Publiek: 10.
CAMILLE REKHSON: Zeg het-- spijt?
Publiek: 10.
CAMILLE REKHSON: Ja, dus dat is het tweede deel van het.
En dan, als je deze elkaar, dat
hoe krijg je de volledige binary voor de hexadecimale.
Ja?
>> PUBLIEK: Om te weten dat A 1010, moet je onthouden?
Of kunt u like--
>> CAMILLE REKHSON: Dus als u-- de differe-- zo
wanneer je gaat door binair, eigenlijk binaire
is 0 tot 9 en A door middel van F als zijn 16 dingen.
Als helemaal 0 tot 9-- als u-- 9 en dan A, eigenlijk
als we omgebouwd naar decimaal, A zou zijn 10, B zou zijn als 11.
En als je na te denken over de binary 1010 is 8 en 2,
omdat dat de beide plaatsen die optellen tot 10, die
is precies wat A is gelijk aan.
Dus dat is een soort van een eenvoudig manier om na te denken over.
Andere vragen over hexadecimaal.
>> OK, dus nu gaan we nemen Een blik op bitwise operators.
Dus deze kan zeker komen aan de quiz.
Ik weet dat we niet werkte samen met hen veel.
Maar we gaan gewoon doen een klein overzicht van deze.
Dus hopelijk zullen een beetje meer bekend voorkomen.
Zodat de zes bitwise operators dat we hier hebben opgesomd.
En ze lieten ons te manipuleren individuele bits.
Zodat de operator is een ampersand.
Niet te verwarren met die dubbele ampersand,
dat is de logische en dat laat ons twee dingen te vergelijken.
>> De single en is de manier waarop we kunnen dingen bitsgewijs manipuleren.
Dus dit geeft ons het resultaat van 1 indien beide van de argumenten die we vergelijken
de same-- of 1.
En de verticale balk, OR, geeft ons 1 indien ten minste een van hen is 1.
Dus eigenlijk precies wat de woorden betekenen.
En als de twee bits 1, 1 en 1 geeft ons 1.
Maar met de OR, als het 0 of 1, of 1 of 1, in beide gevallen,
we hebben 1 als een van hen.
Dus dan zouden we een 1 te krijgen.
Publiek: Wat bedoel je dat zegt dat het geeft 1?
>> CAMILLE REKHSON: De resultaat. Soort, zoals jij
would-- als je dat deed 0 en 1, de gevolg van die zou 1-- of 0 zijn
1 en het resultaat van dat zou 0, sorry.
Ja, het was een soort van de Door de expressie.
En dan, dit dakje symbool is de XOR, of exclusieve OR.
Dus dat betekent dat uitsluitend een of precies één van de twee argumenten gelijk aan 1.
En dan zou het je 1.
>> De kleine kronkelende lijn is de NOT operator.
Dus in tegenstelling tot de rest van hen, met toepassing van een paar bits,
de NOT operator duurt slechts een beetje, en zal spiegelen.
Dus als je give-- als je dat doet NIET 0, zou het geven 1.
En als je niet 1, het zou je geeft 0.
Ja?
>> Publiek: Wat is het verschil tussen de OR met één lijn
en de OR met twee?
CAMILLE REKHSON: Dus de OR met twee lijnen de logische OR.
Dus dat is voor het vergelijken twee volledige integers of two--
te zien als dingen zijn gelijk.
Of zoals het doen van dit is gelijk aan deze, OR dit is gelijk aan dit soort dingen.
Overwegende dat de enige bar OR, is voor het doen van dingen bitwise.
Ja.
>> Publiek: Wat bedoel je met bitsgewijze?
>> CAMILLE REKHSON: Dus bitgewijze werkt direct met de bits in binaire.
>> PUBLIEK: Oh, ik zie.
>> CAMILLE REKHSON: Ja, dus werken met 0 en 1 is.
We zullen een paar voorbeelden van dit te doen na, gewoon dus het is niet te verwarrend.
En dan de laatste twee zijn de linker shift en de rechter shift.
Welke zijn twee minder dan tekens of twee groter dan tekens.
En zij verschoven naar bit het opgegeven aantal plaatsen
dat je het in de richting.
Het zou dus ofwel verschuiven naar links of naar rechts.
Ja?
Publiek: Wat is de syntaxis voor het draaien?
>> CAMILLE REKHSON: We gaan gaan door middel van een voorbeeld in een tweede.
Dus hopelijk, dat zal helpen.
Heeft u vragen over net wat is hier, before-- OK.
Dus gaan door enkele voorbeelden.
Laten we beginnen met de en enen.
Wat zouden we krijgen als we 0 en 1?
>> Publiek: 0.
CAMILLE REKHSON: OK, en als we 1 en 1?
Publiek: 1.
CAMILLE REKHSON: Ja, wat als we deden 0 OF één?
Publiek: 1.
CAMILLE REKHSON: Hoe ongeveer 1 of 1?
Publiek: 1.
CAMILLE REKHSON: OK, hoe over 0 XOR 1?
Publiek: 1.
CAMILLE REKHSON: En 1 XOR 1?
Publiek: 0.
CAMILLE REKHSON: Jullie zijn goed.
Hoe zit het niet 0?
>> Publiek: 1.
CAMILLE REKHSON: En niet 1?
Publiek: 0.
CAMILLE REKHSON: OK, en dan deze laatste één is een beetje een met de verschuiven.
Dus als we aanvankelijk x 8 te zijn, en dan is y x naar links 3,
wat zou dat ons?
>> PUBLIEK: [onverstaanbaar].
CAMILLE REKHSON: Zeg dat nog eens.
PUBLIEK: [onverstaanbaar].
CAMILLE REKHSON: Dus, dit eigenlijk geeft ons 64.
PUBLIEK: [onverstaanbaar].
CAMILLE REKHSON: Dus ik ben gewoon ga dit hier te schrijven op,
dus dit maakt het een beetje verstand.
Als we de 2 0, 2 tot 1, 2 naar 2, 2 tot 3 gaat worden 8.
En als we willen verschuiven 3 meer bits naar links, zou die 2 zijn de 4,
2 de 5 en 2 aan de 6, en 2 tot 6 is het 64.
Is dat zinvol?
Ja.
>> PUBLIEK: Heeft die verschuiving alle 1's en 0's van het binaire getal aan the--
>> CAMILLE REKHSON: Ja.
En je zult geen zorgen te maken over de quiz over deze negatief.
We zal je niet omgaan met negatieve verschuivingen in any way.
Een andere vragen over dit?
Ja.
>> Publiek: Als het een verschuiving naar rechts, iets is dat iets dat wasn't--
was oorspronkelijk een deel van het ding 0?
>> CAMILLE REKHSON: Ja, zou je voeg gewoon 0 op in het origineel.
Ja.
>> Publiek: Dus wat is dat 100 naar rechts drie keer?
CAMILLE REKHSON: 100 naar rechts verschoven,
dus dat zou alle nemen 1's en 0's en ze gewoon verschuiven
rechts aantal keren je het te verschuiven naar rechts.
>> PUBLIEK: [onverstaanbaar]?
CAMILLE REKHSON: Nou, 100-- zijn heb je het over 100 in binaire,
of 100 in decimale?
Publiek: Het spijt me, 100 in binaire.
>> CAMILLE REKHSON: 100 in binaire, als je het verschuiven naar de right--
Als u verschuiving naar rechts eenmaal, zou 10 worden.
Als je het verschuiven naar de juiste tweemaal, zou 001 worden.
En dan als je het verschuiven weer, je soort van verliezen het bit.
Ja, dat is gewoon 0.
Andere vragen over dit?
Ja.
>> Publiek: Dus dan wordt het 000.
>> CAMILLE REKHSON: Ja.
OK, dus laten we gaan door middel van een beetje van ASCII wiskunde.
Dus tekens kan in wezen worden behandeld als integers
op basis van hun ASCII-waarden.
Dus als we zaten int A gelijk aan 65, int B gelijk aan A plus 1, int char C gelijk
D minus 1 en char D gelijk 68, wat zou uit te printen op de bodem?
>> Dus, we printen these-- zegenen u-- we
drukken van deze allemaal uit als CHARS basis van het percentage C.
Dus we eigenlijk printen het karakter waarde van alle vier
van deze variabelen.
Als een hint, 65 is de ASCII-waarde van het kapitaal A. Misschien dat hielp.
Wat?
>> Publiek: ABCD.
>> CAMILLE REKHSON: Ja, dus zou dit precies uit te printen
ABCD omdat we stellen int A gelijk aan de ASCII-waarde van A.
Dus als we printen die als een karakter, we gewoon hoofdletter A,
Een plus 1 zou een hoofdletter B in ASCII zijn.
D min 1 zou een hoofdletter C in ASCII zijn.
En 68 is de ASCII-waarde D. Vragen over ASCII?
Ja.
>> Publiek: Dus, de aanhalingstekens rond Een, doet dat verandering Een van de ASCII?
>> CAMILLE REKHSON: Het uses-- is count-- enkele aanhalingstekens rond de A
maakt het een teken.
En als je te maken hebt met in het aantal form--
zodat wanneer, zoals in dit geval, is het wordt behandeld als een int--
dan zou behandelen met het ASCII-waarde.
Ja.
>> Publiek: Heeft u raden we hebben een ASCII verwijzing tafel?
>> CAMILLE REKHSON: Ik denk niet think--
>> PUBLIEK: Of zou het alleen maar te maken hebben met deze?
>> CAMILLE REKHSON: Ik denk dat we zou het doen met eenvoudige dingen.
Ik denk niet dat het zou kwaad om misschien te schrijven
wat hoofdletter A en kleine letters A zijn, net wat die marges zijn te beginnen met.
Maar ik denk niet dat je nodig hebt om alle te nemen speelt geheel ASCII tafel.
Ja.
>> Publiek: Wat is het verschil tussen zeggen int A en C char,
zoals je aan de top?
>> CAMILLE REKHSON: Dus het is gewoon hoe dat in het geheugen opgeslagen.
Maar je kunt het ook zo behandelen.
Zoals we hier zien, printen doen we de A als een karakter.
Publiek: Dus dat is het zelfde als A?
CAMILLE REKHSON: Ja.
Een andere vragen?
>> Publiek: Dus, procent C zegt het afdrukken van een char?
>> CAMILLE REKHSON: Ja.
>> Publiek: Dus zelfs als A heeft slechts gedefinieerd als een integer,
als we proberen om af te drukken char als 65 het would--
CAMILLE REKHSON: Het zou gaan om gaat in principe om ASCII grafiek
en krijgt welke karakters in de ASCII grafiek voor die 65.
>> Publiek: Dank je wel.
>> CAMILLE REKHSON: Ja.
Ja?
>> Publiek: Dus als je dat deed% I, I%, % I, I%, zou het gewoon print--
CAMILLE REKHSON: Ja, als je dat deed alle 4% I's, is het
zou de ASCII uitprinten waarden van alle vier van deze.
Een andere vragen?
OK, dus omvang, in principe is deze helpt ons te bepalen waar
een variabele bestaat in uw programma.
Dus we hebben gesproken over twee verschillende types van scope, globaal en lokaal.
>> Als een variabele globaal wordt scoped, betekent dit dat uw hele programma
toegang tot die variabele.
En als je wereldwijd scope een variabele, je
verklaren voor uw belangrijkste functie.
Dus het is gedaan recht uit de vleermuis.
En dan je hele programma kunt openen.
>> Als het alleen lokaal scoped, dat variabele beperkt is tot een bepaald gebied.
Dus als je verklaart in een lus, alleen dat lus kan openen.
Of als u te verklaren binnen een specifieke functie,
alleen die functie kunt openen.
Vragen over het toepassingsgebied.
>> OK, dus de functie prototyping.
Voornamelijk omdat C, wanneer Het compileert, leest boven naar beneden.
Als u een functie declareren laat in de code,
de compiler niet weet dat die functie bestaat.
Dus wat we gebruiken zijn prototypes, die in feite vertellen de compiler,
Deze functie bestaat, gaat kijken voor het later in de code.
Dus de manier waarop u doen een functie prototype
is precies hoe je begint uit het schrijven van een functie.
U geeft de return type, de naam van de functie,
en dan argumenten dat die functie neemt.
>> Dus, om te kijken naar een snel voorbeeld, in dit onze functie die we hier met behulp van case
is in feite een kubus functie.
Zo nemen in een integer en terugkeer van de kubus die integer.
Omdat we hebben geschreven dat functie onder de belangrijkste functie,
en we willen het gebruiken output van dat-- of we
wil die functie in onze belangrijkste functie,
plaatsen we het prototype weg bovenaan programma.
En toen we noemen het in onze belangrijkste functie,
de compiler weet dat die functie later geschreven, en zal gaan zoeken,
en zal het goed gebruikt.
Vragen over prototyping?
Ja.
>> Publiek: Dus wat is het punt?
Ik heb niet het punt van prototyping krijgen.
Waarom niet gewoon hebben daar beneden?
>> CAMILLE REKHSON: Nou als het is hier beneden, toen
krijg je kubus van lijn x in uw belangrijkste functie,
de compiler zal geen idee hebben dat de kubus functie daadwerkelijk bestaat.
>> Publiek: Kan je niet zet ze gewoon aan de voorkant?
>> CAMILLE REKHSON: Het is betere codering praktijk
om het onder uw belangrijkste functie te zetten.
Dus dat is waarom we zouden doe de prototyping.
Gewoon omdat, als je had veel functies
Het zou wel heel slordig te zijn gelezen door al die functies
voordat je naar vlees van uw programma.
Ja, en je had een q--
>> Publiek: Dus, is te verklaren variabele aan de top
dus je kunt het openen, maken het een globale variabele?
Dat ongeveer zo waar het te verklaren dat
daarboven, zodat het weet dat het gaat om het later toegang
en je kunt het gebruiken?
>> CAMILLE REKHSON: Ja.
Ja.
>> PUBLIEK: Moet the-- bijkomende functies die u sleutel buiten te creëren
van dit ding, of--
>> CAMILLE REKHSON: Ja, als je het creëren van andere belangrijke functions--
zelf de function-- dus als je bent het maken van andere functies,
moeten ze buiten te zijn.
Ja?
>> Publiek: Wat is procent D?
CAMILLE REKHSON: Procent D hetzelfde als percentage I.
Het verwijst naar een integer.
Ja.
>> Publiek: Dus wat is int main doen?
Wat was die leegte?
CAMILLE REKHSON: Void zegt het neemt geen argumenten.
PUBLIEK: [onverstaanbaar].
CAMILLE REKHSON: Kunt u spreekt een beetje luider, sorry?
Publiek: Ja, sorry, waarom deed je verliest om de eerste,
en dan int input voor de tweede?
CAMILLE REKHSON: Oh, voor de twee different-- voor de belangrijkste functie
versus de kubus functie?
Dus in de belangrijkste functie, we leegte gebruiken omdat er
geen parameters worden genomen.
Overwegende dat in de kubus functie, hebben we een ingang.
Dat is waarom het zegt int, input, want er zijn argumenten dat we
nemen in onze functie uit te voeren.
Ja.
Zijn er vragen?
>> OK, en dan snel floating-point onnauwkeurigheid.
Dus we hebben oneindig veel reële getallen.
Maar er zijn slechts een eindig aantal bits
die we kunnen gebruiken om deze weer te geven getallen en hen te vertegenwoordigen.
Dus dan komen we met een aantal onnauwkeurigheid.
En uw nummers zal niet altijd heel wat
je denkt dat ze zijn wanneer je omgaan met floating-point.
Dit is gewoon iets goed om te weten.
Vragen over dit?
Ja.
>> PUBLIEK: Is dit een verwijzing het idee van bit overflow
dat was in het college?
Was dat iets te scheiden?
>> CAMILLE REKHSON: Ze zijn volledig gescheiden, ja.
OK, geweldig.
Pulak Goyal: Hallo, iedereen.
Mijn naam is Pulak, en ik zal te gaan over pointers.
OK, dus laten we eerst denken over wat geheugen eruit ziet.
Dus zoals je hier kunt zien, we neem geheugen en verdelen we het omhoog
in een bos van blokken.
En we verwijzen naar elkaar blokkeren door een adres, toch?
En heeft iemand nog wat soort notatie gebruiken we om een ​​adres aan te duiden?
>> PUBLIEK: Hexadecimaal, 0X.
>> Pulak Goyal: Hexadecimaal, toch?
Dus de 0X betekent dat we over hexadecimaal.
OK, dus hoe kunnen we creëren pointers?
Dus nemen we het type, we zet het-- voeg een ster aan het,
en dan voegen we de naam van de variabele.
Zodat de voorbeelden die we hebben gezien zijn int ster x, char ster y en z beginnen zweven.
Dus als ik zeg int ster x, kan iemand mij vertellen
wat ik soort van praten over daar?
>> Doelgroep: De locatie van de schijf.
>> Pulak Goyal: Sorry, wat?
Kun je dat herhalen?
Doelgroep: De locatie van de schijf.
>> Pulak Goyal: Dus actually-- dus wat Ik bedoel, is wanneer we hebben int ster x,
we zeggen is het creëren een pointer, en
kan het adres van een op te slaan variabele dat is een int, toch?
Dus met char ster y, we zijn het creëren van een pointer
die kan het adres op te slaan van een variabele dat is een char.
Dus die zinvol zijn voor iedereen?
OK, cool
>> OK, dus met verwijzingen, zijn er twee belangrijke operaties die we kunnen doen.
Er is referencing en Er is dereferentie.
Ja?
>> PUBLIEK: Kunt u gaan een beetje langzamer?
>> Pulak Goyal: Zeker.
Ja, so-- ja, vragen stellen als ik ga samen als u-- als er iets is onduidelijk.
Dus we hebben referencing en dereferentie.
Dus als je wilt het adres te krijgen van een variabele, gebruik dan de ampersand.
Dus laten we zeggen dat ik verklaard int x ergens.
En ik wil het adres van die krijgen en doorgeven in, ik zou ampersand x doen.
En als je wilt het krijgen waarde die aan een pointer,
de dereference gebruiken operator, die een ster.
>> Dus laten we zeggen dat ik had int ster x, en Ik had het wijzen op iets.
Als ik wil de waarde van wat het is te krijgen wijzend naar, zou ik gewoon doen ster x.
Is dat duidelijk?
Heeft u vragen over dat?
Ja.
>> Publiek: Dus in het algemeen, u zal niet in staat te doen op x en ster
x met dezelfde x.
Is dat correct?
Want als x een variabele, dan heb je
te doen op x te krijgen dat het een pointer.
Maar als x is een pointer, dan moet je Star x doen om de variabele te krijgen.
>> Pulak Goyal: Ja, zodat de vraag was over wanneer
gebruiken we een star-- bij je zou de ster te gebruiken,
en als we gebruik maken van de ampersand, en kunnen we
gebruiken met hetzelfde type variabele?
Dus meestal als je, bijvoorbeeld een int x,
zou je meestal gebruik maken van de ampersand aan het adres van dat.
Omdat het niet maken zin om eerbied in x.
Overwegende dat, als we hadden int ster x, zou je met behulp van dereferentie operatie
omdat het geen zin zou maken te gebruiken op x in dat geval.
Is dat zinvol?
>> Publiek: Dus je kan niet en, en vervolgens een pointer?
Pulak Goyal: Dus u technisch, eigenlijk
kan het teken van een pointer te doen.
Maar dat is buiten de toepassingsgebied van deze klasse.
Voor de purpose-- voor uw jongens ' doeleinden, wanneer u pointers,
u wilt de dereference operator de waarde die aan dat.
En als je regelmatig hebt variabelen, zoals een int x,
u wilt de ampersand gebruiken exploitant aan het adres van dat.
OK?
>> OK, dus laten we eens kijken naar pointers en wat er onder de motorkap.
Dus het eerste wat ik deed hier is de aangegeven int x gelijk aan 5.
Het adres van deze variabele is 0x04, en de waarde 5.
Dus laten we zien wat er gebeurt met de volgende regel.
Dus nu verklaren wij een pointer.
Zijn adres is 0x08 en de waarde het adres van x.
Heeft dat zin om iedereen?
Heeft u vragen over dat?
>> OK, en nu laten we zien wat gebeurt met de volgende regel.
Dus met deze volgende regel, hebben we het adres van de kopie zijn 0x10,
en bedraagt ​​5.
Dus de reden waarom we kregen vijf is dat we zeiden, we dereferentie
pointer, die we verklaarde een int ster.
En zo went-- wanneer we dereferentie het, het zei, OK, wat er in de gleuf 0x04.
En het ging om dat.
En wat x een x0-- 0x04, en de waarde 5.
Slaat dat ergens op?
Ja?
>> Publiek: Waarom is het adres van de kopie van slechts 4 bytes boven de x wijzer?
>> Pulak Goyal: Ja, dit is een vergissing on--
>> CAMILLE REKHSON: Dus ja, herinner Dit is geschreven in hexadecimaal.
Pulak Goyal: Oh, ja.
CAMILLE REKHSON: Dus dit is eigenlijk 8 en 16
omdat we zeiden dat, de wijzer, vergeet niet,
in onze IO gaat 8 bytes lang.
Pulak Goyal: Ja.
Dus gewoon om duidelijk te zijn, pointers zijn 8 bytes lang.
Een int is 4 bytes.
Dus de reden waarom wat sprong van 0x04 naar 0x08
is omdat we moesten doe een sprong van 8 bytes.
En dan voor-- sinds exemplaar is slechts een int,
Het is 4 bytes, die de helft van 8 bytes.
Dus we springen naar 0x10, dat is twee weg van 0x08.
Een andere vragen?
OK, let's-- ja?
>> Publiek: Waarom is niet de waarde van int kopie
gewoon the-- waarom is het 5 in plaats van 0x04?
>> Pulak Goyal: OK, waarom is het 5?
OK, dus als the-- dus laten we eerst denken over dit in termen van soorten.
Dus ik zeg int kopie is gelijk aan pointer ster.
Dus wat is de aard van de pointer?
Het is een int ster.
En toen ik dereferentie dat, het type wordt een int.
Dus wat we verwachten te slaan Hier is eigenlijk een int.
Slaat dat ergens op?
PUBLIEK: Tuurlijk, beetje.
Pulak Goyal: Dus meestal wanneer je denkt in termen van soorten,
het helpt je te begrijpen wat is het type de waarde die daar moet gaan.
Dus je kunt meestal uitsluiten veel van deze veel voorkomende fouten
door te denken in termen van soorten.
Laat me gaan door middel van een beetje meer dia's.
En we kunnen vragen bij krijgen het einde van de sectie aanwijzer.
OK, dus we hebben een buggy programma hier.
En dat doet anyone-- kan iemand vertellen me wat is er mis met dit programma?
Juist, dus wat we verwacht hier te doen
is-- wat we willen doen is neemt de variabele int x
en draai het-- maken het gelijk 5 in plaats van 3 en vervolgens afdrukken dat.
Maar dat gebeurt niet.
Kan iemand mij vertellen waarom?
Ja?
>> Publiek: Als de functie to_five neemt x als het argument,
wordt geen rekening X zelf, maar in plaats daarvan een kopie gemaakt, a, van het.
En het vormt operaties op dat.
Maar vanwege dat je niet veranderen de werkelijke waarde van x.
Omdat je [onverstaanbaar].
>> Pulak Goyal: Rechts, rechts, dus toen we noemen
de functie to_five, wat we doen is denken,
geef me een kopie van de waarde voor die functie.
Deze functie, dan gaat en het doen van een aantal manipulaties.
Maar zodra het terugkeert, het is nu uit van de omvang van de belangrijkste functie hier.
Zo x stilstaat, in feite, gelijk aan 3, en wij drukken 3.
OK, dus laten we eens kijken hoe dit gebeurt.
>> OK, dus er is niets verklaard.
Dan hier x gelijk aan 3.
En nu is het is-- op positie twee, een nog niet in omvang.
En nu gaan we naar drie plaatsen, waar neemt nu de waarde van 3.
Om vier we nu wijzigen naar een 5.
Maar nu, als we springen terug naar vijf, de print instructie,
een is nu buiten bereik.
En x steeds gelijk aan 3.
Betekent dit zinvol voor iedereen?
OK, dus laten we nu praten over hoe kunnen we pointers gebruiken om dit te bevestigen.
Heeft iemand enig idee hoe we zou dit op te lossen door het gebruik van pointers?
>> PUBLIEK: U neemt in een int ster in plaats van een int voor to_five.
>> Pulak Goyal:? Sorry, je kon spreken
>> PUBLIEK: U neemt in een int ster in plaats van een int voor to_five.
Pulak Goyal: OK, ja.
Dus laten we pass-- plaats van passerende gewoon de waarde, laten doorgeven door verwijzing.
Deze nieuwe functie, toch?
En zo door het passeren van het adres in, we manipulaties kunnen doen op het adres.
En dus zijn we eigenlijk, in feite het veranderen x.
Dus laten we zien hoe dat werkt.
>> OK, dus in dit voorbeeld hebben we opgelost.
We hebben onze handtekening veranderd van to_five te nemen in een int
ster in plaats van alleen een int hier.
Dan zijn we dereference deze een en wijs 5 aan.
En nu dit wil, in feite, print 5.
Dus laten we zien hoe de stappen die hier werken.
>> Dus met de eerste stap, er is nog niets verklaard.
Dus hier, met de tweede stap, we hebben gezegd x gelijk aan 3,
maar is nog steeds buiten bereik.
Nu door de derde lijn, hebben we x is steeds gelijk aan drie.
En nu, wij overgegaan in-- wat opgeslagen in een nu het adres van x.
Heeft dat zin om iedereen, hoe we dat gekregen?
Goed, we hebben de amper-- dat is hoe passeerden we een ampersand x om de functie
to_five.
En dan naar de volgende regel, wat we doen, is dat we een dereference.
>> En door een dereferentie, zijn we in staat de waarde van x te veranderen van 3 tot 5.
Omdat x woont op dat adres 0x12.
En dan, ten slotte, wanneer we weer terug naar de belangrijkste,
hoewel dit een is nu uit scope, we hebben in feite veranderde x.
En het is 5.
Heeft u vragen over dit?
Ja?
>> Publiek: Kunt u mij vertellen wat de ampersand x was?
Ik dacht ampersand was als EN.
>> Pulak Goyal: Ja, dus we maken gebruik van dezelfde symbool voor vele verschillende dingen.
Dus hier, als je have-- in dit geval, als je,
Ik guess-- dus in dit geval, wanneer je te maken hebt met pointers,
wanneer u de ampersand vooraan van een int, een variabele int, of een char,
of een stroom, wat je zegt is, geef mij het adres van deze.
Maar wat je denkt, als anders zou u ampersand gebruikt wordt, laten we zeggen,
in een if-statement.
Je hebt een echte, en sommige variabelen dat evalueren wat Boolean,
en een aantal andere variabelen dat sommige Boolean valideren
en u wilt krijgen en de van.
Dan zou je de ampersand gebruiken.
SPEAKER 1: Ja, dus alleen vandaag, we hebben sprak over drie verschillende toepassingen
van ampersand.
We hebben twee ampersands, dat is wat Pulak net heeft beschreven.
We hebben een ampersand, die is wat Camille beschreven
eerder, één teken.
En dat is voor bitwise AND.
En merk op dat zowel de voorwaardelijke en-- of, sorry,
de logische AND en de bitsgewijze EN, die twee nummers, toch?
Het was iets ampersand ampersand iets,
iets ampersand iets.
Hier, als we gewoon ampersand iets, dat is dereferentie.
>> Pulak Goyal: Ja, grote vraag.
Ja.
>> PUBLIEK: Waarom doet in lijn 5a en een ster geworden N / A?
Waarom doen ze dit niet gewoon een soort behouden dezelfde waarden van de vorige regel?
>> Pulak Goyal: Omdat we hebben de functie verlaten.
En dus wat happens-- dus what-- nu zijn we
buiten het toepassingsgebied van die functie, wat gebeurt er eigenlijk
is deze verwijderd uit het geheugen.
Ja.
>> PUBLIEK: Tussen 3 of 4 sterren een gelijk 5.
Pulak Goyal: Ja.
Publiek: Wat betekent dat precies te duiden?
Pulak Goyal: Wat betekent dat?
Publiek: Ja.
Pulak Goyal: Dus de vraag was, wat is
dat-- wat je online doet als we zeggen, de ster is gelijk aan 5?
Dus vergeet niet de ster van de dereference operator.
Dus wanneer een, in dit geval is een aanwijzer.
Het is een int ster.
Dus toen we dereference een door met behulp van de ster, wat we zeggen
is, naar welke wordt opgeslagen in het adres, opgeslagen in a-- dus take-- dus,
nu, heeft een aantal adres daarin opgeslagen.
Ga naar de plaats waar dat adres punten, en nu veranderen wat dat is tot vijf.
Ja.
>> Publiek: Kunt u zeggen in eenvoudiger bewoordingen?
Verander het adres van een tot 5.
>> Pulak Goyal: We zijn niet veranderen van het adres van een tot 5.
A heeft een aantal adres daarin, dat de adres van de variabele rente.
En dus wat we zeggen als we dereferentie is,
nu willen we change-- we nu referencing
het belang van de variabele direct.
Is dat zinvol?
>> SPEAKER 1: Een andere manier om na te denken ervan wordt gaan-- dus een adres.
De ster zegt naar die aan te pakken en te kijken naar de waarde ervan.
En nu zet de waarde op 5.
Dus het zegt, ga dan naar de adres x, waarvan
gaat worden wat er opgeslagen in een, en verander het naar 5.
Pulak Goyal: Ja?
Publiek: Dus de positie is waar de wijzer gaat, het adres.
Maar de waarde is een toegewezen waarde op basis van het adres.
Pulak Goyal: Ja.
Een andere vragen over dit?
Publiek: Ik heb een vraag.
Pulak Goyal: Ja, sorry.
Publiek: Dus als je zo store-- Als je zegt [onverstaanbaar] a.
Pulak Goyal: Ja.
Publiek: Moet je opslaan van de x met een ampersand?
Waarom kun je niet gewoon zeggen x voordat je int [onverstaanbaar]?
Pulak Goyal: So--
PUBLIEK: [onverstaanbaar].
Pulak Goyal: Dus is uw question-- oh.
Dus je vraag is, waarom kan niet we-- om de functie to_five, kan niet waarom we
net voorbij een x, toch?
>> Publiek: Recht.
>> Pulak Goyal: OK, ja, dus dit opnieuw gaat terug naar onze discussie over de verschillende soorten.
Dus de functie to_five is nu verwacht een type int ster.
Dus wat is het type van x?
X is gewoon een int.
Maar wat deze functie verwacht is een int ster.
Verwacht dus een variabele die heeft een adres opgeslagen in het.
Dus dat is hoe u-- de gestelde ampersand, en dus dat is
hoe we pas in de adres, dat is now--
en interpreteert dat als een int ster, ja.
Grote vraag.
Andere vragen over dit?
OK, cool.
>> OK, dus laten we nu praten over pointer rekenkunde.
Dus hier, optellen en aftrekken i past de aanwijzer
door i keer zo groot het type pointer bytes.
Dus laten we eens kijken hoe dat eruit ziet.
Dus hier hebben we verklaard int x gelijk aan een 5.
En nu gaan we naar een pointer verklaren y, en pas in het adres van x daar.
Dus hebben we dat.
SOx wordt opgeslagen op 0x04.
Nu y gelijk aan die.
En kan iemand mij vertellen wat zij denken er zal gebeuren als we dat doen y plus is gelijk aan 1?
Ja?
>> Publiek: Zal ​​het veranderen naar 0 tijden 0 8?
>> Pulak Goyal: Size en Motortype-
>> PUBLIEK: je beweegt het adres.
Pulak Goyal: Ja, het was-- ja.
Zo waar.
Dus het zal veranderen in 0x08.
En because-- dus zou je dit gebruiken formule 1 keer de grootte van de aanwijzer
en de wijzers zijn van omvang--
>> [STUDENTEN Murmur]
>> Pulak Goyal: Recht.
>> [STUDENTEN Murmur]
>> SPEAKER 1: Dus het type dat de wijzer to--
>> Pulak Goyal: Is, ja, ja, dat is 4 bytes.
>> SPEAKER 1: Dus ints zijn 4 bytes.
>> Pulak Goyal: Dus als we a-- had laten zeggen dat we verklaard, denk ik, een char.
Wat zou dus dat-- laten we zeggen dat we hebben char x gelijk aan een of iets dergelijks.
En we hadden het adres van die in 0x04, wat y zou plus is gelijk aan 1 nu doen?
Sorry, wat?
>> Publiek: 0x05.
Pulak Goyal: 0x05, rechts.
Heeft iedereen dat?
OK, en nu laten we zeggen dat het een float.
Wat zou er gebeuren?
Iedereen?
Dus praalwagens zijn hoeveel bytes?
>> Publiek: 4 bytes.
>> Pulak Goyal: Recht.
Dus het zou hetzelfde als dit zijn.
Koel.
OK, nu laten we praten over pointers en arrays.
Dus je zag dit op het previous twee p sets,
waar we zo arrays kunnen treat-- en pointers zijn niet hetzelfde.
Maar we kunnen arrays behandelen als pointers.
Dus hier hebben we deze array Hier, die drie sleuven heeft.
In de eerste slot-- we één, twee en drie.
>> Dus als we-- zodat we kunnen toewijzen dat door te zeggen, we hebben array,
dereference dat.
En toen we dereferentie dat, wat we eigenlijk aan het doen
verwijst naar dezelfde sleuf.
Dus ster-array is gelijk aan 1.
We kon- hoe kon we schrijven dat-- wat
een alternatieve manier kunnen we schrijven dat?
>> PUBLIEK: Array 0 gelijk 1.
>> Pulak Goyal: Precies, doet iedereen dat?
Dus hetzelfde met hier.
Dus toen hebben we scala plus 1, doen-- we zo even--
onthouden met rekenen dat we net over gesproken, als we dat doen plus 1
of beweeg het over met 4 bytes, rechts.
Heeft iedereen dat?
En die kant, als we dereferentie dat, kunnen we stellen dat voor 2.
En dat is hoe we stellen het volgende blok 2.
En dus een alternatieve manier om te schrijven dat zou ook scala beugel zijn
0 beugel gelijk aan 1.
>> Publiek: Heeft u de haakjes nodig?
>> Pulak Goyal: Ja, omdat je dereferentie de totale hoeveelheid
reeks plus 1.
OK, en hetzelfde voor serie plus 2.
Heeft u vragen over dit?
Ja.
Publiek: Dus array is automatisch ingesteld op 0?
>> Pulak Goyal: Array is-- sorry, wat?
>> Publiek: Array is 0.
Het adres van de array is gewoon 0.
>> Pulak Goyal: Dus de vraag was, is het adres van de array gewoon 0?
Dus, nee, array heeft een aantal adres.
Dus toen we dereferentie het, that's-- zodat je kunt denken about--
letterlijk als een pointer wijst aan het begin van een array.
Dus dat heeft een aantal adres.
We weten niet wat het is.
Maar toen we dereference, we weten dat het begin van de matrix.
En dus toen we verplaatsen door 1, zijn we gewoon bewegen
ten opzichte wanneer dat adres was.
Een andere vragen?
Ja?
>> Publiek: Dus als je scala beugel plus 1--
Pulak Goyal: Sorry, Ik-- kon je spreken?
Publiek: Ja, als je dat doet scala beugel [onverstaanbaar].
Dus dan als je de pointer--
Pulak Goyal: Sorry, ik kan je niet horen.
Kunt u het nog een keer zeggen?
>> PUBLIEK: Je bent OK.
>> Pulak Goyal: OK, sorry.
OK, cool.
Any-- ja.
Dus als je gaat in de serie beugel 3--
>> Pulak Goyal: Ja.
>> PUBLIEK: --isn't er-- zou niet Het vier plekken zoals 0, 1, 2 en 3?
Waarom is het niet opstelling 2 int?
>> Pulak Goyal: Nee, dus gewoon de conventie van C is-- toen we verklaren de array,
we-- het aantal dat we daar te zetten is hoeveel slots we willen.
Maar de indices van de array eigenlijk serie 0, serie 1 en serie 2.
Dus het is gewoon de conventie over hoe we verklaren arrays.
Ja, nog andere vragen?
Ja.
Publiek: Dus we zijn nog steeds praten over pointers, toch?
Pulak Goyal: Ja.
Publiek: Kunt u nog steeds doen ster voor matrix 0 is gelijk aan 1?
Pulak Goyal: Nee, nee, so-- OK, dus de vraag was kon
je gewoon ster scala beugel nul, en dat gelijk is aan 1.
Dus, nee, wat we zeggen hier is dat we kunnen think--
kunnen we arrays behandelen pointers.
Dus we have-- wat we gezegde is hebben we twee manieren
nu verwijzen naar hetzelfde blok.
Dus doing-- als je matrix nul, het type dat nu een int.
En als je de ster te nemen dat, je krijgt een ongeldige zaak.
Dus wat we hier zeggen, is Er zijn twee alternatieve manieren
verwijzen naar hetzelfde blok.
U kunt dit doen scala beugel 0 gelijk is aan 1.
Of u kunt dereferentie doen matrix, en hebben die gelijk is aan 0.
Dus gewoon twee manieren hetzelfde te doen.
Ja.
>> Publiek: Waarom is het niet grootte van int 1 tot to-- voegen
>> Pulak Goyal: Grootte van int 1.
>> Publiek: Want dat is het verplaatsen van een korting.
>> Pulak Goyal: Want dat is alleen de manier waarop C werkt.
Het is gewoon de manier wijzer rekenkunde gedefinieerd.
Het zal de wijzer te nemen.
En dan wat je toevoegen om het, het zal vermenigvuldigen dat
door de grootte van welke de wijzer winkel is, ja.
Ja.
>> Publiek: Dus je zegt dat we kunnen behandelen pointers en arrays hetzelfde,
maar dat ze verschillende.
Dus wat maakt ze anders?
Wat kunnen we niet doen een, maar het andere niet?
>> Pulak Goyal: Voor de toepassing van dit klasse, ik denk it's-- wat doen u--
>> SPEAKER 1: Dus, we-- OK, dus, voor Bijvoorbeeld, als je geheugen toewijzen
en je hebt een pointer naar een integer, bijvoorbeeld.
Als u geprobeerd om te beginnen doet pointer rekenkunde
en verder gaan dan de hoeveelheid geheugen die u toegewezen, zou je tegenkomen fouten.
We weten met arrays, we zeggen van tevoren, OK, ik
wil dit wezen allocate-- zegt, ik wil toewijzen
genoeg ruimte voor drie getallen.
En nu kunnen we het geheugen behandelen alsof we hebben alle drie van die getallen.
Doet dat soort make sense?
>> Pulak Goyal: Ja.
Ja.
>> Publiek: Dus een ster matrix, dat het toewijzen 1
de 0-index van de array?
Pulak Goyal: Ja.
>> Publiek: Dus, wat is na de komende twee lijnen in termen van the-- I
begrijpen dat je probeert naar pointer rekenkundige hier te gebruiken,
maar nogmaals, ik begrijp het niet wat pointer rekenkunde is.
Zodat de reeks plus 1, je bent zeggen dat je nu bent
gaat te willen om over te praten de eerste index in de array.
>> Pulak Goyal: Recht, en zo de reden dat werkt is array,
Hier kunnen we van denken als een int ster.
En dus toen we wijzer rekenkundige op het, denk aan de formule, waar
we the-- ik denk dat wat het huidige adres,
en toen we voegen 1 om het, we eigenlijk
vermenigvuldig 1 door de grootte van het ding we manipuleren.
Dus in dit geval, de grootte van een int.
En dan gaan we er doorsturen door dat veel.
>> SPEAKER 1: Dus pretenderen Je hebt B-array ster.
Pulak Goyal: OK, ja.
SPEAKER 1: Met je hand.
Ga hier.
Pulak Goyal: Of ik kan gewoon-- ja.
Dus hier-- OK, dus scala aan het beginnen, is gewoon hier.
Dus toen we dereferentie array, waren we alleen over het eerste blok in.
Maar nu wanneer ik reeks plus 1 te doen, dat is-- dat pijl is nu hier.
Is dat zinvol?
Juist, want dit blok omvang int die 4 bytes.
En ja, wat we doen is dat we bewegende die wijzer door 4 bytes voorbij.
Wanneer we rekenen doen op, het zal altijd
verplaatsen in stappen van 4 bytes.
Want dit is als een int ster.
Slaat dat ergens op?
OK.
>> Publiek: Dus de dingen die in de array waren 5 bytes, zouden we het te verplaatsen 5 bytes--
>> Pulak Goyal: Rechts, dus als we een char ster, zouden we het te verplaatsen met slechts 1 byte.
Dus in het geval van char sterren, het zou gewoon verplaatsen overgenomen door 1.
PUBLIEK: Om het te krijgen naast je een ster nodig.
Pulak Goyal: Ja, ja, doet dat zinvol?
SPEAKER 1: We kunnen chatten over later meer.
Pulak Goyal: Ja, ja, zeker.
OK, cool.
Laten we verder gaan naar de volgende sectie.
SPEAKER 1: Oh, OK cool.
Ja dat ben ik.
Oké, geweldig.
OK, cool, dus nu zijn we op een beetje meer algemene informatie over het geheugen.
Ook ik waardeer het feit dat ze waren vrij snel gaan.
Het is veel materiaal te krijgen door middel van in een uur en een half.
Maar als er sprake is van onderwerpen die u willen meer diepgaande gaan in,
we gaan te hebben kantooruren deze week
waar u kunt chatten met ons een op een.
Of je kan gewoon komen op de beëindigen en zullen we praten over dingen.
En zoals altijd, het gevoel vrij om vragen te stellen.
Geweldig.
Dus hier is ons beeld van het geheugen dat we hebben gezien in collegezaal een miljard keer.
En we weten dat deze stapel groeit vanaf de onderkant
en de hoop groeit naar beneden.
En wat is het verschil tussen de dingen dat we blijven op de hoop en de dingen
dat we blijven op de stapel?
Iemand gooit iets daarbuiten.
Ja.
>> Publiek: Is het stapelen voor dingen die alleen zijn
vergankelijk variabelen die we gewoon verklaren met behulp van bepaalde functies?
SPEAKER 1: Mooie, ja.
Dus elke tijd waar, laten we zeggen dat we in een functie,
en we hebben slechts enkele lokale variabelen.
Die zullen eindigen op de stapel.
Als, in plaats daarvan, malloc noemen we en eigenlijk het geheugen toe te wijzen,
die altijd afkomstig vanuit de heap.
Dus ja Cool?
>> En dus niet vergeten dat alle geheugen dat u te wijzen met behulp van malloc,
dat gaat eindigen op de heap.
En als je vergeet vrij is, de computer
niet van plan om te weten dat je klaar bent met het.
Dus het is gewoon te hangen er in het geheugen.
En je in wezen bent lekken dat het geheugen.
Je verliest het.
Omdat je nooit de computer verteld, hey ik ben klaar met het gebruik ervan, voel je vrij om te gebruiken,
zet andere dingen zijn er.
Koel.
Heeft u vragen daar?
Ja.
>> Publiek: Dus wat voor soort geheugen is stapel?
Niet dynamische voer, gedelegeerd?
Hoe zou je het noemen?
>> SPEAKER 1: Tuurlijk, dus je kon denk dat het als lokale variabelen.
Eigenlijke gesprekken naar functies gaan stapelen.
Nog iets?
Ja?
Publiek: Hoe doe je gratis het geheugen toegevoegd aan the--
SPEAKER 1: Tuurlijk, dus als je toewijzen geheugen op de heap, malloc bellen.
En dus dan dat geeft je weer een pointer sommige adres in het geheugen.
Dus zeg je dat pointer genoemd, toch?
Dan moet je gewoon zeggen vrij wijzer.
En dat bevrijdt het geheugen.
Koel.
Andere vragen?
Ja.
>> Publiek: Wat doet dynamisch toegewezen betekenen?
>> SPEAKER 1: dynamisch toegewezen middelen in de loop van het programma.
Dus als je malloc bellen het midden van uw programma,
aan het begin van het programma, er is geen geheugen toegewezen.
En als de computer stap door die code,
het gaat om het geheugen toe te wijzen.
Dus dat is wat we bedoelen met dynamisch.
Goede vraag.
Ja?
Publiek: Als u definieert een array met de vierkante haken,
doet dat nog steeds [onverstaanbaar]?
SPEAKER 1: Dat is een goede vraag.
Ik denk dat als je een array toe te wijzen, het eigenlijk zet het op de stapel.
Ik ben niet positief over dat, dus me niet citeren.
>> Luidspreker 2: Ik denk het-- ja Het zet het op de stapel.
>> SPEAKER 1: Zet het op de stapel.
OK, cool, bevestigd.
Andere vragen?
Ja?
>> Publiek: Als je malloc delegeren, doet niet automatisch op de computer
geheugen toewijzen voor variabelen?
SPEAKER 1: Ja, voor uw lokale variabelen,
automatisch zet geheugen op de stack.
Publiek: Dus wat is het punt van het gebruik malloc?
SPEAKER 1: Wat is het punt van het gebruik malloc?
Zo zagen we een heleboel voorbeelden, zoals, bijvoorbeeld, met behulp van swap,
waar we willen de omvang van variabele te zijn wat
dan alleen de functie oproep.
En we willen iets dat we rond kunnen passeren
en dat we toegang uit verschillende plaatsen.
Dat is waar we zouden willen zet geheugen op de heap.
Zodat al deze verschillende functies kunt openen.
>> Publiek: Kun je uitleggen?
>> SPEAKER 1: Dus een optie is-- zodat de vraag was, kunnen we gewoon allocate--
sorry, kunnen we verklaren een globale variabele wezen.
Dat is een optie.
Maar veel van die, die hebben de neiging om echt rommelig.
En we in het algemeen denken van die zo slecht design.
Ja.
Cool, nog andere vragen?
Geweldig.
OK, bewegen op.
Dus dit is eigenlijk hoe we het geheugen toewijzen.
We spraken over een beetje.
Wij gebruiken deze functie genaamd malloc.
En je vertellen hoeveel bytes in geheugen, dus hoeveel bytes op de heap,
jij wil.
En het gaat om het adres terug te keren, dus een pointer naar een stuk geheugen
dat is toegewezen voor u.
Dus het type gaat nietig ster te zijn.
Het gaat om een ​​pointer te zijn wat je ook beslist om daar in te zetten.
Elke keer dat je belt malloc, we al gezegd
je hebt om het te bevrijden, zodat we hebben geen geheugenlekken.
>> Wat is de andere ding die je absoluut
moet elke doen keer dat je malloc noemen?
Oké, je hebt om het te bevrijden.
Wat is de andere ding?
Controleren op null, mooi.
Dus, ja, het klopt er op het bord.
Als je zou proberen toe te wijzen geheugen en je hebt geen geheugen links,
de computer gaat zeggen, Ik heb niets om u te geven.
En het geeft je terug null.
Vragen over dat?
Ja.
>> Publiek: Waarom zou je ooit wilt verklaren een pointer met een specifiek type
wanneer leegte ster aankan alle soorten pointer anyways?
SPEAKER 1: Goede vraag.
Waarom zouden we zeggen int ster in tegenstelling tot sterren ongeldig
wanneer leegte ster alles aankan?
Dus we willen niet ooit expliciet cast pointers.
Het is gewoon een slechte gewoonte.
Maar we zullen praten over int sterren net als een begrip van,
Dit is een pointer naar een integer.
>> Publiek: OK.
>> SPEAKER 1: Ja, en het laat je om de waarden in te manipuleren
als gehele getallen.
>> PUBLIEK: Oh, OK.
En generlei ster zou niet laten je dat doen?
>> SPEAKER 1: Het hangt af van de context Ja, dus maak je geen zorgen
niet te veel zorgen te maken over het type daar.
Weet alleen dat, in het algemeen, malloc geeft een pointer naar iets.
Goede vraag.
>> Publiek: Waarom denk je vermenigvuldigen het tijden 10? [ONHOORBAAR].
>> SPEAKER 1: Tuurlijk, dus ik was gewoon doet willekeurig voorbeeld hier, waar
Ik wilde genoeg om toe te wijzen kamer 10 integers.
Gewoon een willekeurige keuze.
Ja.
Ja, wat is er?
>> Publiek: Wat doe je bedoel door te controleren op null?
Wilt u het controleren wijzer voor null of malloc?
SPEAKER 1: Ja, precies.
Dus de vraag is, wat verstaan ​​we onder controle door null?
We willen to-- wanneer we malloc noemen en we terug een pointer,
we willen zeggen, is wijzer gelijk aan nul?
Dus letterlijk PTR.
PTR is gelijk aan nul.
Ja.
Publiek: Dus, was ik soort van me af, als je
initialiseren van de wijzer in malloc, doet Het wijzen op het begin van malloc?
Want als het een array--
SPEAKER 1: Dat is een grote vraag.
Ja, als je malloc noemen, de pointer die het-- laten we zeggen,
dus even wijzen we 10 bytes van het geheugen.
Dus, het spijt me, genoeg ruimte voor 10 gehele getallen,
we gaan naar het adres van krijgen dat eerste stuk van het geheugen.
Dat is een goede vraag.
Ja.
>> Doelgroep: Door het toewijzen 10 wijdverbreid integers,
kon je eigenlijk gebruiken pointer als like-- bijna
als een array van gehele getallen?
SPEAKER 1: Ja, zo kan je gebruiken als een array van integers?
Ja, precies, dit is wat gewoon Pulak toonde u on-- een paar slides geleden
waar we zeggen, OK, dit is eigenlijk gewoon een soort van-- we
kunnen denken aan het als een reeks van 10 getallen.
Het gebeurt gewoon om op de heap.
Publiek: Maar je kon geen toegang met vierkante haakjesnotering?
SPEAKER 1: Je kon eigenlijk toegang met vierkante haakjesnotering, ja.
Je kunt ze behandelen hetzelfde.
Ja.
>> PUBLIEK: Waarom zou wijzer ooit nul zijn?
>> SPEAKER 1: Waarom zou wijzer ooit nul zijn?
Als je zal gebruik maken van alle het geheugen op de heap.
Als uw programma up eet, het eten, het eten van het geheugen,
en er is niets links, dan malloc gaat say-- als je zegt,
Ik wil nog 100 bytes, het gaat te zeggen, ik heb geen 100 bytes.
Hier is null.
Dat betekent, niet ik.
Ja.
>> PUBLIEK: In dat geval, null is niets, toch?
>> SPEAKER 1: Ja, in die geval, null is niets.
Je hebt geen adres.
Er is geen geheugen.
Oké, bewegen op.
Oké, laten we praten heel snel over buffer overflow.
Wanneer kunnen we tegenkomen buffer overflow?
Laten we zeggen dat we hebben we a-- toewijzen van een stuk van het geheugen,
en we gaan naar de string in te schrijven.
En we gaan om te zeggen, OK, ik ga om te wijzen
genoeg ruimte voor zes tekens.
En ik ga om te vragen de gebruiker voor wat input.
En de gebruiker ingangen, bijvoorbeeld, hallo.
En dat past perfect fijn, want we hebben
ruimte voor alle letters van hello, en de afsluitende null karakter.
Veel ruimte, geen probleem.
>> Maar wat als we de kans geven voor een boze gebruiker om ons programma te gebruiken,
en ze typen in geen zes personages, of niet vijf tekens, maar een miljoen.
Ze houden het typen en het typen, en typen, wat er gaat gebeuren?
Wel geven we alleen de computer enough-- of sorry,
gaven we alleen deze string voldoende ruimte voor 5 tekens.
Dus, gaan we iets krijgen dit, waar de kwade persoon die
typen in ingang kan overschrijven de grootte van de buffer,
en kan eigenlijk voorbij de hoeveelheid dat het oorspronkelijk is toegekend.
En dan wat u kunt doen, de echt kwaad wat je kunt doen,
is overschrijven het retouradres.
Die in feite betekent u kunt soort nemen
controle van het gedrag van het programma.
Dus op een zeer hoog niveau buffer overflow is wanneer
u toe te wijzen een bepaalde hoeveelheid geheugen.
En dan u-- dit omdat je het nemen van input van de gebruiker of iets
zoals dat-- je over de grenzen van wat u oorspronkelijk hebt toegewezen
en start knoeien-up van uw programma.
Ja?
>> PUBLIEK: Waarom zou dat niet alleen terug een segmentation fault?
>> SPEAKER 1: Waarom zou dat niet terug een segmentation fault?
Het zou.
Soms is de compiler of tijdens een van uw runtime
er werkelijk gaande is om te controleren dat.
Als bepaalde dingen gebeuren, en Dit is een soort van een lager niveau,
dan moet je weten.
Maar als je niet het ontwerpen deze systemen goed,
dan heb je de kans hebt van niet vangen en gewoon
zodat de computer take-- de kwade persoon om uw computer te besturen.
Ja.
>> PUBLIEK: [onverstaanbaar]?
SPEAKER 1: Zeker.
Oh, als ik buffer zeggen, ik bedoel alleen de hoeveelheid geheugen die je hebt toegewezen.
Dus hier zei ik, oh, hebben we toegewezen zes char-- genoeg ruimte voor zes tekens.
En ik noem dat mijn buffer waar ik zou kunnen schrijven.
Ja.
Andere vragen over dit?
Ja.
>> Publiek: Hoe doe je het te stoppen?
Hoe doe je het te stoppen?
SPEAKER 1: Awesome vraag.
Hoe doe je het te stoppen?
Hoe doe je buffer overflow te voorkomen?
Ook een manier om het te doen is iets als GetString, waar we voortdurend te verhogen
de hoeveelheid geheugen die we toewijzen Als de gebruiker voert veel tekst.
Een ander ding is het, alleen als je wil zes tekens, doe een snelle controle.
Zeggen alleen ingang zes tekens.
Ja.
Dus laten we zeggen dat je werken on-- we gaan
naar web dingen een beetje later in de course-- maar laten
zeggen dat je werkt op een formulier, zou je slechts beperken hoeveel kon ingeleverd.
Ja.
>> PUBLIEK: GetString trekt geheugen van stapel, toch?
Gewoon om te verduidelijken?
SPEAKER 1: Nog een keer?
PUBLIEK: Doet GetString neem het geheugen van de stapel?
SPEAKER 1: Ik geloof Getm-- get int neemt het geheugen van de hoop
omdat het alloc noemt.
Publiek: Oh.
OK.
SPEAKER 1: Ja, malloc en realloc.
Andere vragen?
Ja.
>> Publiek: Dus door het definiëren de grootte van de buffering,
je iemand uit te voorkomen in staat om code te injecteren
dat kan schuiven langs de [onverstaanbaar].
>> SPEAKER 1: Dus, door het definiëren van de grootte van de buffer,
u hebt gezegd, OK hier is hoe veel geheugen we kunnen gebruiken.
Als u de gebruiker toestaan ​​om te schrijven over het, dan zul je in de problemen.
Zinvol.
Geweldig.
Laten we bewegen langs.
Prima.
Spreken van fouten, hier zijn enkele algemene foutmeldingen
die zou hebben getoond terwijl je codering, werken aan uw probleem sets.
Goede kans dat een van Deze verschijnt op de quiz
als de afgelopen jaren zijn een indicatie.
Dus, antwoorden zijn soort hier op het bord.
Maar gerust wat meer uit te schreeuwen.
>> Waarom zou een segmentation fault gebeuren?
Waarom zou je een segmentation fault krijgen als je het runnen van uw programma?
>> PUBLIEK: [onverstaanbaar].
>> SPEAKER 1: Good.
Ja, als we proberen om toegang te krijgen geheugen dat niet is aan ons gegeven.
Als we dereference een null pointer.
Bijvoorbeeld, als we malloc noemen, en om te controleren of het null,
en we proberen gewoon gebruiken, de computer gaat ons een segmentation fault geven.
Goed.
Hoe zit het met de impliciete verklaring van de functie?
Wat betekent dat?
Publiek: Je probeert een gebruiken functie die u niet hebt gedefinieerd.
SPEAKER 1: Good.
Je probeert een functie te gebruiken dat je niet hebt gedefinieerd.
Zodat zou een van twee dingen.
Misschien was het net als het voorbeeld Camille liet je eerder.
En heb je een belangrijke functie dat vraagt ​​iets genaamd kubus.
En laten we zeggen dat je vergeten bent dit prototype te schrijven.
Je vergat te zeggen, he computer, Ik heb deze functie genaamd kubus.
Je zult het later te zien.
Laten we zeggen dat je vergeten bent om het te schrijven prototype, kunt u deze fout krijgt.
Een ander ding is, laten we zeggen je probeerde te printf gebruiken,
en vergat te nemen de standaard bibliotheek,
dan is het gaan zeggen impliciete verklaring van de functie.
Tenslotte, zwartwerk identifier.
Ja.
>> Publiek: Je hebt een probleem scope.
Zoals misschien je probeert om bel een lokale variabele dat is
in een ander soort omgeving.
SPEAKER 1: Grote, dus als je een variabele die niet in omvang,
en je probeert om het te gebruiken, je gaat in de problemen te komen.
En juist meer in het algemeen, laten we zeggen je probeert om x te gebruiken, met steeds zeggen int
x gelijk is aan 5, dan ben je gaat in de problemen.
Neem me niet kwalijk, vragen over dit?
Ontzagwekkend, chugging rechts langs.
>> OK, recursie, waarom might-- laten see-- Ik verloor mijn sch-- oh hier gaan we,
maar zorg ervoor dat we ruwweg op schema.
Oké, cool.
OK, terugkeer, het algemene idee van recursie, een recursieve functie
is een functie die zichzelf noemt.
OK, dus dat is wat ik verstaan ​​door een programma-concept
waarbij een functie noemt zichzelf.
Wat some-- wat is een zou zijn goede reden om recursie te gebruiken?
Wanneer het misschien nuttig?
Of wat een programma dat echt leent zich voor recursie?
>> Publiek: Binary zoeken.
>> SPEAKER 1: Binaire zoekopdracht leent zich recursie,
omdat je dit probleem dat u kan breken in kleinere stukken,
en continu uit te voeren hetzelfde algoritme op.
Dit leidt tot in veel gevallen meer elegante code die is nauwkeuriger.
We zijn gewoon het voorbeeld van binaire zoeken.
Een ander voorbeeld is het samenvoegen soort.
Soms, als je denkt aan een algoritme, zoals faculteit,
het voelt gewoon recursieve, toch?
Omdat we weten dat de faculteit van 5 een factoriële 4 maal 5.
En dus als je het opzetten van een probleem op die manier, het voelt gewoon recursieve.
Dus dat zou een geweldige manier om het te schrijven.
Vragen?
Ja.
>> Publiek: Wat is een base case?
>> SPEAKER 1: Oh wat is een base case?
Ik zei, vergeet niet een base case te nemen.
Laten we zeggen dat we het schrijven een faculteit-functie,
en we waren faculteit van 5 doen.
En we weten van een faculteit van 5 is 5 keer per faculteit van 4,
blah, blah, blah, blah.
Hoe weten we wanneer te stoppen?
Hoe weten we dat we eigenlijk hebben een aantal?
Want als we bleef roepen faculteit, dan zouden we nooit een antwoord te krijgen, toch?
Dus als we weten hoe stop in het voorbeeld faculteit.
Iedereen, ja.
>> Publiek: Wanneer de 1 faculteit is 1.
SPEAKER 1: Good.
Dus we weten.
Wij kunnen voor lief nemen dat 1 factorial gelijk aan 1.
Dus als we bij het punt waar we roepen faculteit op 1,
gewoon doorgaan en terugkeren 1.
En dat is uw base case.
Omdat we weten dat we een keer geraakt dat, en we altijd zal raken dat, zullen we never--
zullen we niet gewoon blijven altijd gaan.
Andere vragen over recursie?
Ja.
>> Publiek: Dus als je terugkeert 1, het is gewoon automatisch
zal het programma te stoppen, toch?
>> SPEAKER 1: Ja, dus als je noemen return 1, if-- laten we zeggen,
laten we zeggen faculteit van 2 gesprekken faculteit van 1, faculteit van 1
zal gewoon hand terug 1.
En nu faculteit van 2 zal zeggen: OK, 2 keer 1 is 2, en terug te keren dat antwoord.
Ja.
>> Publiek: Hebben we te maken over de reikwijdte in recursie
als je in een algoritme?
>> SPEAKER 1: Ah, ja.
Ja, heb je te maken over scope in het kader van recursie.
Dus alleen de variabelen gedefinieerd in die run van de functie
zullen nuttig zijn.
Ja, goede vraag.
Oké, laten we blijven bewegen langs.
Want we hebben een heleboel materiaal door te komen.
Maar zoals ik al zei, voel je vrij om te raken up kantooruren, of ons na het feit.
>> Dit is gewoon een heel snelle glijbaan.
We hebben veel geleerd over zoekopdrachten en soorten.
Alstublieft alstublieft alstublieft, deze secties zijn online,
Ik geloof in cs50.net/quizzes.
Dus ga nemen deze grafiek en zet het op je beoordeling vel,
want er zullen een vraag over dit.
Gelieve snap het niet verkeerd.
Gewoon heel snel, Wat betekent deze grafiek,
is het over grote o, waarvan we weten de bovengrens van de algoritmen te
looptijd.
En we hebben omega, die gaan de ondergrens te zijn
een runtime algoritmen.
OK?
>> PUBLIEK: [onverstaanbaar].
>> SPEAKER 1: Ja, wat is het laatste wat?
Wat is theta?
Het is als we-- we alleen maar schelen in deze klasse in het geval
waar onze bovengrens en onze ondergrens hetzelfde.
Ja, dat is de enige keer dat het is zal komen in deze klasse.
OK, ik ga om door te gaan.
Als u de foto niet genomen, Ik beloof deze zullen online zijn.
>> OK, geweldige, structuren.
Waarom zouden we willen structuren?
Wat is een handig reden we zouden willen structuren.
Iemand roepen iets uit.
Nou laten we eens kijken naar de Bijvoorbeeld op het bord.
Laten we zeggen dat we te maken hebben met al deze studenten.
Als we maken een programma voor CS50, zijn er net als 800 mensen.
We moeten write-- we gaan moeten veel informatie verwerken
over studenten.
Het zou mooi zijn als zijn we konden soort groep
dit-- alle informatie die heeft te maken met een bepaalde leerling
in één gegevenstype.
Maar we weten dat er geen gegevens typt genoemd, Student, toch?
We hebben een integer, we hebben een vlotter, hebben we een koord of een char ster,
maar we hebben niet een student.
>> Dus we kunnen doen is eigenlijk soort definiëren onze eigen structuur, noem het student,
en we kunnen sommige associëren verschillende gebieden met die structuur.
Dus in dit geval, laten we zeggen dat we een student.
En de dingen die we de zorg over de student ID-nummer
en de naam van de student.
En nu kunnen we dit ID associëren en deze naam met een bepaalde leerling.
Dus laten we zien een aantal voorbeelden.
>> OK, dus hier zeg ik, OK, laten we zeggen dat we willen een student te maken.
Ik noem hem student 1.
En zijn ID-nummer in dit geval, kunnen we toegang
door gewoon te doen van de naam van de student dot het veld we willen openen.
Dus dit gaat gewoon student 1 punt ID, en we stellen dat gelijk is aan 1.
Want vergeet niet, zeiden we dat ID gaat om een ​​integer zijn.
En heel evenzo, kunnen we zeggen, dit Naam student gaat Davin zijn,
bijvoorbeeld.
Dus we kunnen alleen maar toegang tot het veld van een structuur met behulp van deze stip.
Vragen over dat?
Ja.
>> PUBLIEK: Is er een manier om uw variabelen te beschermen?
Is er een manier om variabelen te beschermen van wordt extern bereikbaar?
>> SPEAKER 1: Is er toch om uw variabelen te beschermen
van wordt extern bereikbaar?
Niet in het kader van CS50.
Andere vragen?
Ja.
>> Publiek: Wat is typedef struct?
Wat betekent elk onderdeel betekenen?
SPEAKER 1: Ah, wat is typedef struct?
Wat doet elke component gemiddelde van deze man?
>> Publiek: Ja.
>> SPEAKER 1: OK, cool.
Dus dit zegt, hey computer, I wil een nieuwe structuur te creëren.
En ik ga naar een definitie te definiëren voor het, zodat ik het kon gebruiken
alsof het een soort mijn hele programma.
OK, dus ik wil een structuur definiëren.
En ik ga nu te zijn kunnen gebruiken als een type.
En zijn naam is student.
En hier zijn de velden.
>> Publiek: Dus is dat typedef struct [onverstaanbaar]?
SPEAKER 1: Als u wilt in staat zijn om Gebruik deze structuur in uw programma,
en in de meeste gevallen in CS50 we doen, moeten we zeggen dat het type Def.
En dat maakt het mogelijk om het gebruik van dezelfde manier die we gebruiken, zoals int of float.
De computer zal altijd weet wat het is.
Ja.
>> Publiek: Kunnen we schrijven dit in de header-bestand?
>> SPEAKER 1: Oh, sorry.
Doen we schrijven dit in de header-bestand?
Je zou kunnen schrijven dit aan de bovenkant van uw programma, aan de bovenkant van uw c programma.
Ja, dat zou het meest worden redelijke plek voor het.
Daarginds.
PUBLIEK: Zelfde vraag, dus voordat de belangrijkste?
SPEAKER 1: Juist, dit moet je ergens dat iedereen het kan openen.
Dus voordat belangrijkste in jouw geval, ja.
PUBLIEK: Is er een verschil tussen zetten student aan de bovenkant en aan de onderkant?
SPEAKER 1: Ah, is er een verschil tussen zetten student
op de top of op de bodem?
Let-- redden die vraag, en als we in gelinkte lijsten,
we zullen zien dat, OK?
Dus vasthouden aan dat één seconde.
Het laatste wat ik wil noemen, is in plaats van een structuur,
We hebben een pointer naar een structuur, kunnen we onze notatie veranderen
een beetje mooier.
>> We kunnen zeggen, laten we zeggen dat we hebben een pointer naar een student in plaats van alleen
een student.
Als we willen toegang tot een gebied, in plaats van te doen, goed gaan dereferentie de pointer,
en dan toegang tot het veld.
Deze notatie ziet er een beetje rommelig met de ster in dit punt.
Helemaal correct, maar een soort van schonere manier om het te doen,
is gewoon om aanwijzer naam zeggen.
En dat eigenlijk combineert dereferentie en de toegang in een mooi symbool.
Vragen over dat?
>> PUBLIEK: Zeg enkel dat nog een keer.
>> SPEAKER 1: Zeg dat nog een keer.
>> Publiek: Precies wat je net zei.
SPEAKER 1: Tuurlijk, precies wat ik net zei.
Als we een pointer naar een student in plaats van de student zelf,
we can-- een manier die we kunnen toegang krijgen tot de veld om dereferentie, en dan
toegang naam.
Een andere, leukere manier we kan doen, dat is gewoon
een beetje van de syntactische suiker, is gewoon om aanwijzer naam doen.
En dat gaat de maaidorser dereferentie en de ontsluiting.
Yeah, pretty cool.
Prima.
>> Dus laten we praten over de andere vraag.
Laten we direct naar nodes, die we gaan gebruiken
in gekoppelde lijsten in slechts een seconde.
Dus hier, zult u merken dat er is het woord knooppunt zowel aan de onderkant,
en op de top.
Vroeger, toen we het definiëren student, we hadden net student op de bodem.
We hadden geen student op de top.
Iedereen weet waarom dat zou kunnen zijn?
Wat is het verschil?
Ja.
Publiek: Dus u knooppunt gebruiken is de definitie van knooppunt
dus het is een recursieve ding?
SPEAKER 1: Good.
Ja, onze nodes moeten we moeten pointer naar andere knooppunten.
Dus omdat we gebruik maken van dit type voordat het daadwerkelijk is gedefinieerd,
we moeten het aan de top gewoon zodat het weet wat het is.
Publiek: Dus we nog steeds moet het op de bodem?
SPEAKER 1: Ja.
Publiek: Dus altijd aan de onderkant.
SPEAKER 1: Altijd aan de onderkant.
Dus alles van jou zal hebben onderaan.
Een andere vragen?
Oké, dus laten we eigenlijk praten over gelinkte lijsten heel snel.
Dus gelinkte lijsten zijn-- we ze gebruiken in plaats van arrays in sommige gevallen,
omdat we weten dat arrays zijn een vaste lengte, terwijl gelinkte lijsten
we kunnen groeien en krimpen als we willen.
Dit is dus een voorbeeld van wat een gelinkte lijst eruit zou kunnen zien.
Wat we nodig hebben om te zien is de kop van de lijst.
Dus waar de lijst begint.
En dan knooppunt hij, elke volgende knooppunt is
belast info waar het volgende knooppunt.
Dus in dit geval, het knooppunt dat 1 opslaat is verantwoordelijk voor het weten wanneer 3 is.
De persoon die 3 slaat is verantwoordelijk voor het te weten waar 9 is.
En 9 heeft niemand anders te wijzen.
Het is het einde van de lijst, zo zegt het enkel null.
OK?
>> Publiek: Wat is het punt van dit?
>> SPEAKER 1: Wat is het punt van dit?
>> Publiek: Ja.
SPEAKER 1: Want, laten we zeggen dat we een aantal data.
En we weten niet precies hoe veel gegevens willen we van tevoren.
Dus met een array, laten we zeggen, waar we willen de mensen te tellen in de eerste rij.
De kans is groot dat het niet gaat veranderen.
We kunnen alleen maar zeggen, OK, ik wil een array van grootte van zes.
Maar als we iets willen dat gaat veranderen.
>> Bijvoorbeeld, laten we zeggen dat ik probeerde te houden van de studenten te houden
zoals ze in de kamer komen voor de herziening sessie.
Ik heb geen idee hoeveel van jullie mensen zullen opdagen.
Dus ik zou willen een datastructuur dat ik kan uitzetten en krimpen.
Want misschien iemand zal vertrekken, misschien iemand zal komen.
En dus op elk moment, we kunt toevoegen of verwijderen knooppunten.
Koele, grote vraag.
Ja.
>> Publiek: Als u kunt gebruiken iets als GetString
dat houdt laat je meer gegevens je het nodig hebt, waarom heb je dit ook nodig?
>> SPEAKER 1: Waarom zou je gebruik gelinkte lijst bij
kun je zoiets als GetString gebruiken?
Dat is een goede vraag.
Vergeet niet dat een van Get-- de ondergang van GetString
is dat we niet een zeer deed goede baan te bevrijden dat het geheugen,
en we een heleboel geïntroduceerd geheugenlekken in uw programma?
Je zou het een statisch nemen sized array en blijven groeien het.
Maar je zou moeten vinden nieuwe plaatsen in het geheugen.
Het zou gewoon een veel overhead zijn.
>> Een van de leuke dingen over gekoppelde lijsten tegenover arrays is arrays
allemaal op dezelfde locatie in het geheugen.
Het moet continu beschouwd delen van het geheugen.
Overwegende dat gelinkte lijsten, 2 en 3 mei zijn geheel op verschillende locaties.
Als 2 is hier, en 3 is hier.
Zolang zij een pointer met elkaar, het is prima.
We weten dat we ze kunnen vinden.
Vraag daar?
>> Publiek: GetString is een functie in de CS50 bibliotheek, toch?
Het bestaat niet in echte programma.
>> SPEAKER 1: Correct.
Juist, dat is de andere zaak.
GetString bestaat niet buiten de context van de CS50.
Ja.
>> Publiek: Dus doet het feit dat twee kon echt ver uit elkaar liggen,
doet die invloed hebben op de efficiëntie van de de toegang tot de elementen op de lijst?
SPEAKER 1: Dat is een grote vraag.
De vraag was, doet het effect de efficiëntie van toegang
deze elementen in de lijst.
Eigenlijk ja.
Omdat we weten if-- laten zeggen dat we willen openen
het tweede element van de array, we weten kunnen we gewoon doen scala beugel 1, recht.
Het gaat altijd om worden dezelfde locatie.
Maar als we willen dat 3 te krijgen, We kunnen niet zomaar zeggen, ga je dat 3.
We moeten zeggen, OK, beginnen bij het begin van de lijst,
en nu zijn we eigenlijk te lopen door tot we
vinden het nummer zijn we geïnteresseerd in.
>> Dus in dit geval we zeggen, OK Dit is het eerste cijfer.
Dus in wezen, dat is index 0.
Nu moeten we het tweede nummer te vinden.
Dat is de index 1.
Dus dat is eigenlijk gaat to-- net toegang, gaat N tijd in beslag nemen.
Koele, grote oude N. Yeah.
>> Publiek: Wat zijn elk van de lijsten?
Zijn zij elk arrays, of wat?
SPEAKER 1: Dat is een grote vraag.
Welke elke structuren die ik heb getekend?
Ze zijn nodes.
Dus elk van deze kleine structuur twee delen.
Het heeft een integer die het bezit.
Dat is de feitelijke gegevens dat het vasthouden.
Dat is het soort van nuttig onderdeel.
En dit is wat maakt het een gelinkte lijst,
het heeft een pointer naar de volgende knoop.
Geweldige vraag.
Oké, dus laten we eens kijken erg snel kijken naar enkele voorbeelden van wat
we zouden kunnen doen met gekoppelde lijsten.
>> Dus een zeer snelle voorbeeld is, stel dat we willen een onderzoek doen.
Wat voor soort onderzoek niet kunnen we doen op verbonden lijsten?
>> Publiek: Binary.
>> SPEAKER 1: Binary.
Waarom kunnen we niet gebruiken binary search?
>> PUBLIEK: [onverstaanbaar].
SPEAKER 1: Recht, omdat met binaire search, moesten we vertrouwen op het feit
dat we konden gewoon springen in de rij op elk moment.
We kunnen alleen maar zeggen, ga het middelste element.
Met hier, zoals we al zeiden een beetje eerder,
We kunnen niet zomaar springen het middelste element.
Om eventuele vinden element, we eigenlijk
hoeft te lopen door onze hele lijst.
>> Dus als we wilden om een ​​zoekopdracht te doen, de beste wat we kunnen doen is gewoon een lineair zoeken.
We beginnen bij het hoofd, we check-- laten we zeggen dat we
op zoek naar 9-- beginnen we aan het hoofd.
We zeggen, dit is 9?
Nee.
Is dit 9?
Nee.
Is dit 9?
Ja, we vonden het.
OK, dat is alles.
Hier is een klein beetje van de pseudo-code.
Ik ga dit voor u te verlaten jongens over te churn op uw eigen,
gewoon omdat we bijna een beetje kort op tijd.
>> Laten we praten over inbrengen.
We zagen een echt cool demo van dit in het college waar we zeiden:
Oké, we hebben dit verband overzicht waar iedereen wijst naar elkaar,
en iemand komt op het podium.
Hoe doen we dat in te voegen persoon in onze gelinkte lijst?
Nou, een verkeerde manier te doen, die is dat ik denk dat wat we voor het eerst zag,
wanneer de persoon voorzijde automatisch
wees naar de nieuwe persoon.
En dan hebben we soort van verlaten de tweede helft van de lijst, toch?
Omdat we niet weten waar het in het geheugen meer.
Dus om heel voorzichtig te zijn over de volgorde waarin we voegen dingen.
>> Dus hier, laten we zeggen dat we willen zet 1 op de voorkant van onze lijst.
Ten eerste, we hebben 1 punt aan de tweede element-- of het element
dat bestaat uit 1.
Dus, we dat doen, dus we zijn niet gaan naar de tweede helft te verliezen.
En nu kunnen we het hoofd punt moeten 1.
Dus nogmaals, dit is gewoon als super hoog niveau.
Dit is hoe we een knoop zou voegen.
We hebben een heleboel pseudo-code hier-- sorry,
Ik weet niet waarom ik ben noemen het pseudo-code.
Het eigenlijke code.
U kunt gaan check it out later.
>> Oké, laten we heel quickly-- meer vragen
op gelinkte lijsten voordat ik verplaatsen naar een paar andere gegevens
structuren in de laatste 10 minuten.
>> Publiek: Moeten we nu hoe te schrijven op een test?
>> SPEAKER 1: Moeten we weten hoe to--
>> Publiek: Schrijf het op een test.
>> SPEAKER 1: We moeten to-- je moet bereid zijn
om te schrijven, invoegen, verwijderen en zoek gekoppelde lijsten op de test.
Dat is iets dat we zou verwachten dat je te doen.
Ga gewoon overheen.
Als u vragen heeft over de code, schiet je TF een e-mail,
kom naar de kantooruren.
Er is nog steeds veel tijd om te studeren, geen zorgen te maken.
Oké, welke de andere vragen over gelinkte lijsten?
Ja.
>> Publiek: Dus als je geen gebruik maken van de aanwijzer naar de ene rechts
voordat u de aanwijzer voor gebruik de een aan de linkerkant, dat is
het equivalent schrappen alles, toch?
SPEAKER 1: Ja.
PUBLIEK: [onverstaanbaar].
SPEAKER 1: Juist, omdat we niet kunnen get it, het is eigenlijk nog erger.
Want niet alleen weten we niet waar het is, kunnen we niet langer te gebruiken,
maar we've-- we niet vrijmaken dat het geheugen niet meer.
Dus het is gewoon opknoping rond en niet nuttig zijn omdat we niet kunnen vinden.
Ja, koel vraag.
>> Oké, laten we praten over stacks.
We zagen stapels zeer snel.
Ze zijn voor het eerst in de laatste out datastructuren.
Dus we denken aan de stapels in Annenberg trays waar we stapelen dingen bovenop.
En als je gaat komen halen een dienblad, je bent
altijd naar de ene op de te nemen top, dat is de meest recently--
dat is het ding dat we het meest onlangs boven op de stapel.
Dus je kunt soort denken van dit soort visueel als je denkt van stacks.
En dan hebben we iets popped van de bovenkant van de stapel.
>> Als we zijn-- oh, en de woorden die we gebruiken wanneer we praten over deze gegevens
structuren gewoonlijk, als we zet iets op de stapel,
we zeggen dat we duwen op de stapel.
En als we iets te nemen uit de stapel, we zeggen dat we knallen uit de stapel.
Als je gaat te implementeren een stack-- die ik zeker
raden u out-- proberen je gaat te willen om bij te houden,
laten we zeggen dat je met behulp van een array.
Ik weet dat in het college hebben we gesproken over het gebruik van beide arrays
of verbonden lijsten een stack te implementeren.
Als u gebruik maakt van een array, moet je keep--
excuus mij-- we nodig hebben om bij te houden de grootte en capaciteit.
Dus het maximumaantal dat onze stack kan houden.
Vragen over stapels?
>> Publiek: Wat is het verschil tussen de omvang en capaciteit?
SPEAKER 1: Het verschil tussen omvang en capaciteit, geweldige vraag.
Dus laten we zeggen dat we met behulp van een matrix, en we
toewijzen voldoende ruimte voor 10 gehele getallen.
En we beginnen op te vullen die up.
En duwen we dingen op, en we knallen er op los.
Wij willen houden van de maximale te houden getal we kunnen houden, dat is de capaciteit.
En we willen houden van de te houden huidige aantal die we hebben, dat is de grootte.
Goede vraag.
Iets anders op stapels?
Oké, laten we praten over verrassing, wachtrijen.
>> In tegenstelling tot de stacks, die voor het eerst in de laatste out, deze zijn first in, first out.
Dus dit is like-- denken aan een lijn.
Denk aan de rij bij de Apple Winkel om wat product te krijgen.
En de eerste persoon in de rij moet de eerste persoon die geholpen.
Dus eerst ding dat geduwd is dit het eerste ding dat is geknald.
Koel?
Zeer similarly-- oh, de woorden die we gebruiken in plaats van push en pop--
die ik zojuist gebruikt, Ik ben sorry-- is dat we zeggen:
als we om iets in de wachtrij, zeggen we enqueued het.
Als we nemen iets uit de wachtrij, zeggen we dat we dequeued.
Het.
Ik kan het uitspreken van die verkeerd, maar je krijgt het idee.
En dan weer, net als stacks, als we de tenuitvoerlegging van deze als array,
we nodig hebben om bij te houden van de te houden grootte, het vermogen, en het hoofd.
Wat bedoel ik door het hoofd?
Waarom hebben we moeten blijven spoor van het hoofd?
>> Publiek: Want dat is waar het begin van de lijst is.
SPEAKER 1: Ja, in principe is het hoofd waarbij het begin van onze wachtrij.
Omdat we weten, in tegenstelling tot de stacks, which-- Ik ga proberen om dit way-- gezicht
we weten dat het altijd gaat om krimpen deze manier en groeien op deze manier.
Wachtrijen, mensen komen op het einde en vertrekken vanaf het begin,
dus we moeten houden waar de start.
Dat is wat ik bedoel met dat we nodig hebben om bijhouden waar het hoofd is.
Koel?
Prima.
Acht minuten, paar meer onderwerpen, kunnen we het doen.
>> Oké, hash tafel.
We spraken kort over hash tabellen.
Voor de quiz, moet je gewoon ze te begrijpen op een hoog niveau.
Het basisidee is dat je deze gegevens.
En we willen om toegang te krijgen in de tijd dat sneller dan iets als een gekoppelde
lijst.
Omdat we zeiden, als we zoeken via een gekoppelde lijst,
dat N tijd kon nemen.
Zelfs toegang kan nemen N keer in een gekoppelde lijst.
Hash tabellen geven ons een manier dat we kunnen sneller toegang tot de dingen, en nog veel meer
snel zoeken naar dingen, zonder met de beperkingen van een array
waar we vaste grootte.
>> Dus we denken van een datastructuur, waar, waar we het in de datastructuur
afhankelijk is van dit magische hash-functie.
Dus in dit geval, de magische hash functie is gewoon een woord,
het controleren van wat de eerste letter is, en dan gewoon sorteren het alfabet.
Dus hebben we in wezen zet ze in verschillende bakken.
Als we zien banaan, zeggen we: Oké, laten we in de B-emmer.
Wanneer we zien dat Apple, laten zet het in de A-emmer.
Als we zagen abrikoos, laten we zet in de A-emmer.
OK?
>> Dus stel ik waren op zoek voor-- I weet niet, wat is een ander fruit?
Stel dat ik was op zoek naar oranje.
Waar moet ik op letten?
In de O emmer.
Ja, er is maar één plaats dat oranje zou kunnen zijn, OK?
Dus ik al eerder zei wat er gebeurt if-- goed ik al eerder zei,
laten we zeggen dat we zetten abrikoos in-- maar ik echt te pakken van het feit dat, oh nee,
als ik bessen in te zetten, is het gaan strijd zijn met banaan.
Waar we het als er al iets in onze tafel?
Nou, we hebben een paar opties.
>> Optie nummer één is lineair probing, die in feite betekent,
laten we zeggen dat ik wil proberen zet bessen, en ik zie, oh nee,
bananen er al, Ik zeg OK, laat
me kijken naar de volgende beschikbare plek.
Dus ik loop naar beneden, zeg ik, oh, er is niets in de D emmer.
Ik kan niet echt denken van een fruit die beginnen met de letter D,
dus ik ga gewoon bessen daar zetten.
Durian.
OK, dus omdat er niets daar nog,
Ik kan net zo goed gewoon gebruik maken van die plek.
Wat is het nadeel van die?
>> Publiek: Het is niet in orde.
>> SPEAKER 1: Sorry?
Publiek: Het is niet in orde.
>> SPEAKER 1: Het is out-- rechts, kunnen we eindigen
met dingen die niet in-- opgeslagen in emmers op de manier
dat wij verwachten dat ze zijn.
Dus als we waren op zoek voor bessen, voordat we zeiden:
oh we kunnen kijken in een emmer.
Dit zou slechts één bak.
Maar nu, echt, het zou kunnen zijn in de emmers, toch?
>> OK, hier is een andere optie, aparte chaining--
dat is het idee dat we gaan een beetje later in P set 5 gebruiken.
Liever dan gewoon een ruimte in elke emmer,
waarom doen we niet elke emmer is een verwijzing naar een gekoppelde lijst?
Indien wij zeggen, OK, is er een emmer voor alles dat begint met A.
En er is gewoon om een ​​gekoppelde lijst van vruchten die beginnen met A.
Dus als we een nieuwe fruit, laten we zeggen we get-- we avocado, hebben we appel,
laten we zeggen dat we abrikoos, hoe zouden we in de lijst?
Nou we zouden gaan emmer 0, en we zouden plaatst u gewoon in onze vond lijst
simpel als dat.
>> Nu ik blijf zeggen emmer.
We kunnen dit implementeren in een aantal manieren.
Een typische manier waarop dit soort foto doet vermoeden,
is misschien met een reeks van verwijzingen naar gelinkte lijsten.
Dat is een manier we kunnen implementeren van een hash tabel.
Publiek: Wilt u een ander nodig lijst omdat banaan en bessen uit zijn
van de orde?
SPEAKER 1: Wilt u need-- ah, zou je
een andere lijst omdat banaan nodig en bessen zijn niet in orde?
In dit geval onze hashfunctie, die ons vertelt waar te dingen te zetten
zich niet bekommert om de tweede letter.
Het maakt niet schelen alphabetizing, Het geeft alleen over de eerste letter.
Vraag?
>> Publiek: Wat is de definitie van die functie, en hoe ziet het eruit?
SPEAKER 1: Ah, goed.
OK, dus we hoeven niet te te veel zorgen voor deze quiz.
Dus ik heb niet in de dia's.
We gaan worden ingevoerd om het voor P ingesteld 5.
Maar in principe, het zegt, krijgt een nieuw element, waar moet ik het zeggen?
Of, laten we zeggen dat ik ben op zoek naar een element, waarbij het misschien?
Ja, grote vraag.
>> OK, heel snel, bomen en probeert.
Dus een boom is gewoon een soort georganiseerde datastructuur.
En we gaan een heleboel foto's te zien dat zal deze super duidelijk maken.
En een trie, die we zagen in de klas, is een heel bijzondere soort boom
die in wezen werkt als een multi-level hash tafel.
Het is super cool.
We gaan om het te zien in slechts een seconde.
Oké, dus laten we praten over bomen als eerste.
Dus dit is echt typisch voorbeeld van een boom, waar we enkele hiërarchie.
Je ziet dat men bij de top, toch?
En ik kan zeggen dat de top omdat er duidelijk een bestelling omdat we
hebben deze pijlen naar beneden.
Zodat het ding boven, Ik noem dat de root node.
Dus een is de root node.
En wat aan de onderkant, die niets hebben komende uit hen,
Ik zeg dit zijn de leaf nodes.
Dus 8,9 5, 6, 7, OK.
En meestal de terminologie we kan zeggen is, 1 is 3's ouder.
Dus het is het ding dat komt niveau boven het, en wijst op het.
En 3 is 1 kind.
Het is het ding dat 1 punten.
Vraag?
>> PUBLIEK: Kunt u terug te gaan naar de vorige dia, alstublieft?
>> SPEAKER 1: Kan ik terug te gaan naar de vorige dia?
Tuurlijk.
Vragen over dit?
Of je wilde om naar te kijken?
Publiek: Ik heb gewoon niet doorheen.
>> SPEAKER 1: OK, cool, ja.
Deze zullen alle online zijn dus niet zorgen te maken over het krijgen van elk woord.
En in het belang van tijd, ik ga om te gaan.
Is dat goed?
Geweldig.
OK, cool.
Dus laten we praten over een zeer specifieke kind--
dus we hebben deze algemene structuur van de bomen,
dat is gewoon iets dat ons in staat stelt van de soort rang dingen hiërarchisch.
>> Binaire bomen zijn dingen waar elke knooppunt hooguit twee kinderen.
OK?
En ik zei: OK, dus dat lijkt aan deze beschrijving past.
Ik zei knooppunt, niet een binaire zoekboom.
Wat is een binaire zoekboom?
Het is opgelost.
Zodat u weet dat er in een binaire zoekboom,
alles aan de tree-- alles naar links knooppunten kleiner,
en alles aan de knooppunten rechts is groter.
Dus dit is niet een binaire zoekboom.
Dit is gewoon een binaire boom.
Dus we hebben grote categorie bomen, iets kleiner categorie
van binaire bomen, zoeken op a-- binary search bomen.
Koel?
Prima.
>> En nu, de meeste plezier van alles, we hebben onze pogingen.
Jullie zag dit beeld in college?
Ja, zou het super vertrouwd kijken.
Laten we eens kijken hoe we misschien deze daadwerkelijk uit te voeren.
Of eigenlijk, laten we eens kijken, betekent dat zelfs komen?
Nee.
Oké, we hebben niet eens te zorgen over dat lage niveau spul.
We zullen genoeg tijd om vervolgens te pakken P ingesteld 5.
Maar voor nu, gewoon erg hoog niveau, we weten dat dit is wat het lijkt.
We beschreef het als een soort van een multi-level hash table
where-- wat doet deze winkel?
Dit slaat namen wetenschappers dat we kunnen eigenlijk
zoeken door gewoon een soort van na de verschillende hash tabellen neer, oké?
>> En het doel daarvan is, in theorie, ze zorgen voor een constante tijd opzoeken.
Dus als ik wil om te controleren dat, bijvoorbeeld, die is someone--
Mandel dat in deze trie, kon ik heel snel
in linear-- spijt me, in constante tijd, uitzoeken
ongeacht of het in de Trie.
Maar een oplichter, is kijken hoe groot deze is.
We zijn niet eens dat het opslaan veel data en het is enorm.
Dus een groot nadeel is dat het gebruikt een grote hoeveelheid geheugen.
Ja.
>> Publiek: Waarom heeft het te bieden constante tijd, precies?
>> SPEAKER 1: Nog een keer?
>> Publiek: Wat is de intuïtie want waarom biedt het constante tijd?
>> SPEAKER 1: Goede vraag.
Waarom is het zorgen voor een constante tijd?
Dus wat we kunnen doen is, laten we zeggen dat we op zoek bent naar Mandel.
We weten dat we willen beginnen in het eerste niveau bij M.
We weten dat we willen volgen om E. So Dat is een stap, twee stappen, toch?
We volgen het naar N. volgen we het naar D. We volgen het naar E. volgen we het naar L.
En dan de volgende ding we controleren says-- deze delta zegt Ja, dat is
in onze tafel.
Dat is een woord.
Dat is een geldige inschrijving in onze trie.
Dus je zegt, OK, dat duurde zeven stappen.
Maar als we toegevoegd als een ontelbaar meer wetenschap deze gegevensstructuur,
we zouden niets hebben om te controleren een ontelbaar meer dingen.
We alleen ooit zal moeten nemen zeven stappen, de lengte van de persoon
naam.
>> Dus, we willen denken runtime als, veronderstel
verhogen we de grootte van onze datastructuur, hoeveel langer
gaat het duren?
In dit geval, als we voegen een bos meer wetenschappers, het maakt niet uit.
Het is nog steeds te nemen dezelfde hoeveelheid tijd.
Het is een constante tijd.
Ja.
>> Publiek: Hoe weet je niet scannen over de andere nummers?
SPEAKER 1: Hoe weet ik hoe to--
PUBLIEK: Net als hoe weet je je gaat rechtstreeks van M tot E en geen M A?
SPEAKER 1: Oh, zeker.
Omdat ik wist dat ik was op zoek naar het woord Mandel,
en ik weet gewoon dat het M-E. Dus dat-- ja, ga je gang.
Publiek: Zou je niet hebt kijken naar de andere letters
in de overige [onhoorbaar]
>> SPEAKER 1: Ah, zou ik niet hebben om te kijken naar the-- OK, geweldig.
Dit is een grote vraag.
Het hangt ervan af hoe we implementeren.
Als we implementeren als gewoon als een reeks arrays
waarvan we weten dat E altijd op positie 0,
Ik weet het niet, wat nummer index is.
Ja, we kunnen gewoon constant tijd, doen, doen, doen, doen.
Koel.
Vraag daar?
>> PUBLIEK: Is constante tijd hetzelfde als real-time?
SPEAKER 1: Is constante tijd hetzelfde is real-time?
Ik ben niet echt zeker real time is.
PUBLIEK: Net als de tijd dat letterlijk vordert tweede
door tweede in tegenstelling tot zijn een onafhankelijke variabele.
>> SPEAKER 1: Oh, ja, je kan denken van het op die manier.
Met andere woorden, het is niet afhankelijk de omvang van de datastructuur.
Dat is een manier om te denken.
Een andere vragen?
Misschien in de eerste keer in geschiedenis, hebben we op tijd klaar.
Als u vragen hebt, voel vrij om te komen ons vragen, gaat u naar sectie,
praten met uw TF, kantoor uren zijn 08:00 en 08:30
tot 11.00 uur op maandag en dinsdag, dus het is een beetje anders tijd,
dus zorg ervoor dat je dat mee.
Ja.
>> Publiek: Moeten we weten dingen zoals command line argumenten,
ls dash, dash wat dan ook?
>> SPEAKER 1: Command line argumenten, en Linux-commando's,
ja, moet je die kent.
Very-- het is net als het soort level stuff we behandeld in paragraaf 0,
zo ver als Linux-commando's go.
>> Publiek: Zijn de uren in Annenberg?
SPEAKER 1: Office uren, ik ben niet helemaal zeker waar ze zijn.
Maar je kunt het website, en het zal u vertellen.