[Powered by Google Translate] [Info] [Quiz 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard University]
>> [Dit is CS50.] [CS50.TV]
>> Hey, iedereen.
Welkom bij de herziening sessie voor Quiz 0, die plaatsvindt deze woensdag.
Wat we gaan doen vanavond, ik ben met 3 andere TFS,
en samen gaan we om te gaan door middel van een overzicht van wat we hebben gedaan in de loop tot nu toe.
Het gaat niet om 100% volledig, maar het geeft je een beter idee
van wat je al hebt naar beneden en wat je nog moet studeren voor woensdag.
En voel je vrij om je hand op te steken met vragen als we gaan mee,
maar houd in gedachten dat we ook een beetje van de tijd aan het eind-
als we door met een paar minuten te reserveonderdelen op algemene vragen te doen,
dus hou dat in gedachten, en dus gaan we beginnen bij het begin met Week 0.
>> [Quiz 0 Review!] [Deel 0] [Lexi Ross] Maar voordat we dat doen laten we het eens hebben over
de logistiek van de quiz.
>> [Logistiek] [Quiz vindt plaats op woensdag 10/10 in plaats van lezing]
>> [(Zie http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf voor details)] Het is op woensdag 10 oktober.
>> Dat is deze woensdag, en als je naar deze URL hier,
dat is ook toegankelijk vanuit CS50.net-er is een link naar het-
U kunt informatie over waar te gaan op basis van
uw achternaam of school affiliatie en
hij vertelt over wat de quiz worden opgenomen en de aard van de vragen die je gaat krijgen.
Houd er rekening mee dat u ook zult de kans om voor de quiz herzien doorsnede te hebben,
zodat uw TFs zou moeten gaan over een aantal praktijk problemen,
en dat is een goede kans om te zien waar je moet nog steeds te studeren voor de quiz.
Laten we beginnen bij het begin met Bits 'n' Bytes.
Vergeet niet een beetje is gewoon een 0 of een 1,
en een byte is een verzameling 8 van die bits.
Laten we eens kijken naar deze collectie stukjes hier.
We moeten in staat zijn om erachter te komen hoeveel bits er zijn.
Waar rekenen we er slechts 8 van hen, acht 0 of 1 stuks.
En aangezien er 8 bits, dat is 1 byte,
en laten we het te converteren naar hexadecimaal.
Hexadecimaal is basis 16, en het is vrij gemakkelijk om te zetten in
een getal in binaire, wat dat wil zeggen een in hexadecimale.
Alles wat we doen is dat we kijken naar groepen van 4,
en we ze converteren naar de juiste hexadecimaal getal.
We beginnen met de meest rechtse groep 4, dus 0011.
Dat gaat als een 1 en een 2, dus samen dat maakt 3.
En dan laten we eens kijken naar de andere blok van 4.
1101. Dat gaat als een 1, een 4 en een 8.
Samen is dat gaat worden 13, waardoor D.
En we herinneren dat in hexadecimale we niet alleen 0 gaan en met 9.
We gaan 0 tot en met F, dus na 9, 10 komt overeen met A,
11 B, et cetera waar F 15.
Hier 13 is een D,
dus om het te converteren naar decimaal alles wat we doen is dat we eigenlijk
behandelen elke positie een macht van 2.
Dat is een 1, een 2, nul 4s, nul 8s, een 16, et cetera,
en het is een beetje moeilijk te berekenen in je hoofd, maar als we naar de volgende dia
zien we het antwoord op die.
>> In wezen gaan we aan de overkant van rechts naar links,
en we vermenigvuldigen elk cijfer door de overeenkomstige macht van 2.
En vergeet niet, voor hexadecimale noteren we deze getallen met 0x aan het begin
zodat we niet verwarren met een decimaal getal.
Verdergaand is dit een ASCII tabel,
en wat wij ASCII te gebruiken voor het in kaart brengen van de personages om numerieke waarden.
Vergeet niet in de cryptografie PSET maakten we veelvuldig gebruik van de ASCII-tabel
om verschillende methoden cryptografie,
de Caesar en de Vigenère cipher, om verschillende letters om te zetten
in een string volgens de sleutel die door de gebruiker.
Laten we eens kijken een beetje ASCII wiskunde.
Naar 'P' + 1, in karaktervorm dat zou Q,
en vergeet niet dat '5 '≠ 5.
En hoe precies zou zetten we tussen die 2 vormen?
Het is eigenlijk niet te hard.
Om 5 te trekken we '0 '
want er zijn 5 plaatsen tussen de '0 'en de '5'.
Met het oog op de andere manier waarop we gewoon toe te voegen op de 0 te gaan,
dus het is een beetje als gewone rekenkunde.
Vergeet niet dat als er iets quotes heeft er omheen is het een teken
, hetgeen overeenkomt met een waarde in de ASCII-tabel.
Verhuizen naar meer algemene informatica onderwerpen.
We hebben geleerd wat een algoritme is en hoe we het programmeren
om algoritmes te implementeren.
Enkele voorbeelden van algoritmen zijn iets heel simpels als
controleren of een getal even of oneven is.
Voor dat vergeet niet dat we het getal mod door 2 en controleer of het resultaat 0.
Als dat zo is, is het zelfs. Zo niet, het is vreemd.
En dat is een voorbeeld van een heel basic algoritme.
>> Een beetje een meer betrokken men is binair zoeken,
die we later gaan over in de review-sessie.
En de programmering is de term die we gebruiken voor het nemen van een algoritme
en om te zetten naar de computer code kan lezen.
2 voorbeelden van de programmering is Scratch,
en dat is wat we gedaan hebben in week 0.
Hoewel we niet echt typ de code het is een manier van de uitvoering van
Dit algoritme dat wordt afgedrukt getallen 1-10,
en hier zijn we hetzelfde doen in de C programmeertaal.
Dit zijn functioneel gelijkwaardig, maar geschreven in verschillende talen of syntaxis.
Vervolgens hebben we geleerd over booleaanse uitdrukkingen,
en een boolean is een waarde die is waar of onwaar,
en hier vaak Booleaanse uitdrukkingen
naar binnen gaan van de voorwaarden, dus als (x ≤ 5),
goed, we reeds x = 5, dus aan die voorwaarde zal evalueren om waar te zijn.
En als het waar is, wat code is onder de voorwaarde
zal worden geëvalueerd door de computer, zo die reeks te bedrukken
naar standaard uitvoer, en de term conditie
verwijst naar wat er tussen de haakjes van de if-statement.
Vergeet niet alle operatoren.
Vergeet niet het is && en | | wanneer we proberen te combineren 2 of meer voorwaarden,
== Niet = om te controleren of 2 dingen gelijk zijn.
Vergeet niet dat = is voor de toewijzing terwijl == is een booleaanse operator.
≤, ≥ en dan de laatste 2 spreken voor zich.
Een algemeen overzicht van de Booleaanse logica hier.
En booleaanse uitdrukkingen zijn ook belangrijk in lussen,
die we nu gaan voorbij.
We leerden over 3 soorten lussen tot nu toe in CS50, for, while, en te doen terwijl.
En het is belangrijk te weten dat, hoewel voor de meeste doeleinden
kunnen we eigenlijk over het algemeen gebruik maken van elk type lus
zijn er bepaalde soorten doeleinden of gemeenschappelijke patronen
in de programmering die specifiek vragen om een ​​van deze lussen
waardoor het de meest efficiënte of elegante om het te coderen op die manier.
Laten we naar wat deze lussen gewoonlijk gebruikt voor het vaakst.
>> In een lus for we over het algemeen al weten hoe vaak we willen herhalen.
Dat is wat we in de aandoening.
Voor, i = 0, i <10, bijvoorbeeld.
We weten al dat we iets willen 10 keer doen.
Nu, voor een while-lus, over het algemeen hebben we niet per se
weten hoe vaak we voor de lus wilt uitvoeren.
Maar we weten wel een soort van voorwaarde dat we het willen
altijd waar of altijd onwaar.
Zo wordt tijdens het instellen.
Laten we zeggen dat is een boolean variabele.
Terwijl dat is waar we willen dat de code te evalueren,
dus een beetje meer uitbreidbaar, een beetje meer algemeen dan een for-lus,
maar elke for-lus kan ook worden omgezet in een while lus.
Tot slot doen terwijl lussen, die misschien wel de lastigste om meteen te begrijpen,
worden vaak gebruikt wanneer we de code eerst evalueren
voor de eerste keer dat we de toestand.
Een vaak gebruikte methode voor een doe while loop
is wanneer u wilt input van de gebruiker te krijgen, en je weet dat je de gebruiker wilt vragen
voor input ten minste een keer, maar als ze niet geven u goede input meteen
je wilt blijven vragen totdat ze geven u de goede input.
Dat is het meest voorkomende gebruik van een niet while-lus,
en laten we kijken naar de werkelijke structuur van deze lussen.
Ze meestal altijd de neiging om deze patronen te volgen.
>> Op de for-lus binnen in je hebt 3 componenten:
initialisatie, meestal iets als int i = 0 waarbij i de teller,
staat, waar we willen zeggen dat dit draaien lus, zolang deze toestand nog steeds bekleedt,
als i <10, en ten slotte, update, dat is hoe verhogen we
de teller variabele op elk punt in de lus.
Een veel voorkomende ding om daar te zien is gewoon i + +,
wat betekent verhogen i met 1 elke keer.
U kunt ook iets doen als ik + = 2,
wat betekent voeg 2 tot i elke keer dat je door de lus.
En het doen alleen verwijst naar een code daadwerkelijk wordt uitgevoerd als deel van de lus.
En voor een while-lus, deze keer hebben we eigenlijk de initialisatie buitenkant van de lus,
dus bijvoorbeeld, laten we zeggen dat we proberen om hetzelfde soort lus zoals ik zojuist beschreven doen.
Wij zouden zeggen int i = 0 voor de lus begint.
Dan zouden we kunnen zeggen, terwijl ik <10 dit doen,
zodat dezelfde codeblok als voorheen
en deze keer de update een deel van de code, bijvoorbeeld, i + +,
eigenlijk gaat de binnenkant van de lus.
En tenslotte, voor een doen, terwijl, het is vergelijkbaar met de while-lus,
maar we moeten niet vergeten dat de code een keer zal evalueren
voordat de conditie wordt gecontroleerd, dus het maakt veel meer zin
als je kijkt naar het in opdracht van boven naar beneden.
In een doe while loop van de code evalueert voordat je zelfs kijken naar de zolang voorwaarde,
terwijl een while-lus, controleert het eerst.
Verklaringen en variabelen.
Als we willen een nieuwe variabele te maken willen we eerst te initialiseren.
>> Bijvoorbeeld, int bar initialiseert de variabele bar,
maar het is niet geef het een waarde, dus wat is nu bar waarde?
We weten het niet.
Het kan een aantal vuilnis waarde die eerder werd opgeslagen er in het geheugen zijn,
en we willen niet dat de variabele gebruiken
totdat we daadwerkelijk geven hem de waarde,
zodat we hier verklaren.
Dan gaan we initialiseren te zijn 42 hieronder.
Nu, natuurlijk, we weten dat dit kan worden gedaan op een regel, int bar = 42.
Maar gewoon om te worden duidelijk de verschillende stappen die aan de hand,
de verklaring en de initialisatie worden afzonderlijk gebeuren hier.
Het gebeurt op een stap, en de volgende, int baz = bar + 1,
deze verklaring, die in stappen baz, zodat aan het eind van deze code blok
Als we de waarde van baz drukken zou 44
omdat we declareren en initialiseren deze in op 1> bar bedragen,
en dan verhogen we het nog een keer met de + +.
We gingen over dit mooie kort, maar het is goed om een ​​algemene
begrip van wat draden en gebeurtenissen zijn.
We hebben voornamelijk deden dit in Scratch,
dus je kunt bedenken draden als meerdere sequenties van de code
die op hetzelfde moment.
In werkelijkheid is waarschijnlijk niet draait tegelijkertijd,
maar soort van abstract kunnen we denken aan het op die manier.
>> In Scratch, bijvoorbeeld, hadden we de meerdere sprites.
Men kan verschillende uitvoerende code tegelijk.
Men zou kunnen lopen, terwijl de ander zegt iets
in een ander deel van het scherm.
Evenementen zijn een andere manier van het scheiden van de logica
tussen de verschillende elementen van de code,
en in Scratch waren we in staat om gebeurtenissen te simuleren met behulp van de uitzending,
en dat is eigenlijk wanneer ik ontvangen, niet als ik hoor,
maar in wezen is het een manier om informatie te verzenden
ene naar de andere sprite.
Bijvoorbeeld, kunt u om het spel te zenden over,
en wanneer een andere sprite ontvangt game over,
reageert op een bepaalde manier.
Het is een belangrijk model om te begrijpen voor de programmering.
Gewoon te gaan over de basis Week 0, wat we gegaan tot nu toe,
Laten we eens kijken naar dit eenvoudige C programma.
De tekst kan een beetje klein van hier te zijn, maar ik zal gaan over het echt snel.
We zijn met 2 header-bestanden aan de top, cs50.h en stdio.h.
We dan het definiëren van een constante genaamd limiet op 100.
We vervolgens de implementatie van onze belangrijkste functie.
Aangezien we hier niet gebruiken command line argumenten moeten we leegte zetten
als de argumenten voor de belangrijkste.
We zien int boven hoofd. Dat is de return type, dus 0 terug aan de onderkant.
En we gebruiken CS50 functie uit de bibliotheek te krijgen int
aan de gebruiker om invoer te vragen, en we slaan in deze variabele x,
dus we hierboven verklaren x, en we het initialiseren met x = GetInt.
>> Vervolgens kijken we om te zien of de gebruiker gaf ons goede input.
Als het ≥ LIMIT willen we een foutcode van 1 terug te keren en er een foutbericht af te drukken.
En tenslotte, als de gebruiker heeft ons goede input
we gaan het getal wilt kwadrateren en af ​​te drukken die het gevolg zijn.
Gewoon om ervoor te zorgen dat degenen die alle getroffen huis
kunt u de labels van verschillende delen van de code hier.
Ik noemde constante, header-bestanden.
Oh, int x. Zorg ervoor om te onthouden is dat een lokale variabele.
Dat contrasteert het van een globale variabele, die gaan we praten over
een beetje later in de review-sessie,
en wij roepen de bibliotheek functie printf,
dus als we hadden niet het stdio.h header-bestand
zouden we niet in staat zijn om printf bellen.
En ik geloof dat de pijl die werd afgesneden hier af wijst naar de% d,
dat is een opmaak tekenreeks in printf.
Het zegt print deze variabele als een getal,% d.
En dat is het voor Week 0.
Nu Lucas zal blijven.
He, jongens. Mijn naam is Lucas.
Ik ben een tweedejaars in de beste huis op de campus, Mather,
en ik ga een beetje vertellen over week 1 en 2,1.
[Week 1 en 2,1!] [Lucas Freitas]
Zoals Lexi zei, toen we begonnen het vertalen van uw code van Scratch naar C
een van de dingen die we hebben gemerkt is dat je niet zomaar
schrijf uw code en voer het uit met behulp van een groene vlag meer.
Eigenlijk moet je een aantal stappen te gebruiken om uw C-programma te maken
uitgegroeid tot een uitvoerbaar bestand.
Eigenlijk wat je doet als je het schrijven van een programma is dat
je vertaalt uw idee in een taal die een compiler kan begrijpen,
dus als je het schrijven van een programma in C
wat je doet is eigenlijk het schrijven van iets dat je compiler gaat begrijpen,
en dan de compiler zal die code te vertalen
in iets dat uw computer zal begrijpen.
>> En het ding is, de computer is eigenlijk heel dom.
Uw computer kan alleen begrijpen 0s en 1s,
dus eigenlijk in de eerste computers mensen meestal geprogrammeerd
met behulp van 0s en 1s, maar nu niet meer, God zij dank.
We hoeven niet te de sequenties voor 0s en 1s onthouden
een lus of een while enzovoort.
Daarom hebben we een compiler.
Wat een compiler doet is het in principe de C-code vertaalt,
in ons geval, een taal die uw computer zal begrijpen,
die het voorwerp code, en de compiler dat we met behulp van
heet clang, dus dit is eigenlijk het symbool voor clang.
Wanneer u uw programma hebben, dan moet je 2 dingen doen.
Ten eerste, moet je je programma te compileren, en dan zul je je programma uit te voeren.
Om uw programma te compileren heb je een veel opties om dat te doen.
De eerste is om te doen clang program.c
in welk programma is de naam van uw programma.
In dit geval kunt u ze alleen maar te zeggen: "He, mijn programma samen te stellen."
Je zegt niet: "Ik wil deze naam voor mijn programma" of wat dan ook.
>> De tweede optie is het geven van een naam aan uw programma.
Je kunt zeggen clang-o en vervolgens de naam die u wilt
het uitvoerbare bestand om zo en dan program.c worden genoemd.
En u kunt dit ook doen met het programma make, en zie hoe in de eerste 2 gevallen
Ik zette. C, en in de derde Ik heb alleen programma's?
Ja, je eigenlijk niet te zetten. C wanneer u te maken.
Anders wordt de compiler er werkelijk gaande te schreeuwen naar je.
En ook, ik weet niet of jullie herinneren,
maar een heleboel keer hebben we ook gebruikt-lcs50 of-lm.
Dat heet koppelen.
Het vertelt alleen de compiler dat je die bibliotheken gebruiken daar,
dus als je wilt cs50.h gebruiken je eigenlijk hoeft te typen
clang program.c-lcs50.
Als je dat niet doet, is de compiler niet van plan om te weten
dat u het gebruik van deze functies in cs50.h.
En als u wilt uw programma uit te voeren heb je 2 opties.
Als je dat deed clang program.c heb je een naam niet geven aan uw programma.
Je moet het uit te voeren met behulp van. / A.out.
A.out is een standaard naam die clang uw programma geeft als je het niet geef het een naam.
Anders ga je. / Programma doen als je gaf een naam aan uw programma,
en ook als je maakte het programma de naam die een programma gaat krijgen
al zal worden geprogrammeerd dezelfde naam als het bestand c.
Dan hebben we gesproken over data types en data.
>> In principe gegevenstypen zijn hetzelfde als doosjes die ze gebruiken
om waarden op te slaan, zodat datatypes zijn eigenlijk net als Pokemons.
Ze komen in alle soorten en maten.
Ik weet niet of die analogie is logisch.
Het gegevensformaat hangt eigenlijk van de architectuur van de machine.
Alle gegevens maten die ik ga hier laten zien
eigenlijk voor een 32-bits machine, hetgeen het geval van onze apparatuur,
maar als je echt coderen van uw Mac of in een Windows-ook
waarschijnlijk zul je een 64-bits machine,
dus denk eraan dat de gegevens maten die ik ga hier om te tonen
zijn voor de 32-bit machine.
De eerste die we zagen was een int,
dat is vrij eenvoudig.
U gebruikt int naar een geheel getal op te slaan.
We zagen ook het karakter, de char.
Als u een brief of een beetje symbool te gebruiken bent u waarschijnlijk gaat om een ​​char te gebruiken.
Een char heeft 1 byte, waarvan 8 bits, zoals Lexi gezegd betekent.
In principe hebben we een ASCII-tabel die 256 heeft
mogelijke combinaties van 0s en 1s,
en dan als je een char typ het gaat vertalen
het teken dat ingangen die u een nummer dat u in de ASCII-tabel, zoals Lexi gezegd.
We hebben ook de vlotter, die we gebruiken om decimale getallen op te slaan.
Als u wilt 3,14 kiezen, bijvoorbeeld, zul je een float te gebruiken
of een dubbele die meer precisie heeft.
Een vlotter is 4 bytes.
Een dubbele heeft 8 bytes, dus het enige verschil is de precisie.
We hebben ook een lange die wordt gebruikt voor integers,
en u kunt zien voor een 32-bit machine een int en een lange hebben dezelfde grootte,
dus het maakt niet echt zin om een ​​lange te gebruiken in een 32-bits machine.
>> Maar als je een Mac gebruikt en 64-bits machine, eigenlijk een lange heeft maat 8,
dus het is echt afhankelijk van de architectuur.
Voor de 32-bit machine heeft het geen zin om echt gebruik maken van een lange.
En een lange lange, daarentegen, heeft 8 bytes,
dus het is heel goed als je wilt een langere integer te hebben.
En tot slot hebben we string, dat is eigenlijk een char *,
Dit is een pointer naar een char.
Het is heel makkelijk om te denken dat de grootte van de string gaat als zijn
het aantal tekens dat je er hebt,
maar eigenlijk de char * zelf
heeft het formaat van een pointer naar een char, die 4 bytes.
De grootte van een char * 4 bytes is.
Het maakt niet uit of u een klein woord of een brief of wat dan ook.
Het gaat worden 4 bytes.
We hebben ook geleerd een beetje over gieten,
zodat u kunt zien, als je bijvoorbeeld een programma dat zegt
int x = 3 en dan printf ("% d", x / 2)
Weten jullie wat het gaat om af te drukken op het scherm?
>> Iemand? >> [Studenten] 2.
1. >> 1, ja.
Wanneer u 3/2 doen het gaat om 1,5 te krijgen,
maar aangezien we met behulp van een geheel getal dat het gaat om het decimale gedeelte negeren,
en je gaat 1 hebben.
Als u niet wilt dat dit gebeurt wat u kunt doen, bijvoorbeeld,
is een vlotter vast y = x.
Vervolgens x die voorheen 3 gaat nu 3,000 in y.
En dan kunt u afdrukken de y / 2.
Eigenlijk zou ik een 2. daar.
Het zal 3.00/2.00 doen,
en je gaat naar 1,5 te krijgen.
En we hebben dit .2 f alleen maar om te vragen voor 2 decimale eenheden in het decimale gedeelte.
Als u .3 f het gaat om daadwerkelijk 1,500.
Als het 2 gaat het om 1,50.
Wij hebben ook dit geval.
Als je float x = 3,14 en dan heb je printf x
je gaat naar 3,14 te krijgen.
En als je x = het int van x,
wat betekent dat de behandeling van x als een int en u afdrukt x nu
je gaat naar 3,00 te hebben.
Is dat logisch?
Omdat je het eerst behandelen x als een integer, dus je negeert het decimale gedeelte,
en dan u afdrukt x.
En ten slotte, kunt u dit ook doen,
int x = 65, en dan declareer je een char c = x,
en dan als u afdrukt de c je eigenlijk gaat krijgen
A, dus in principe wat je hier doet
is het vertalen van de integer in het karakter,
net als de ASCII-tabel doet.
We hebben ook gesproken over wiskundige operatoren.
De meeste van hen zijn vrij eenvoudig, dus +, -, *, /,
en ook hebben we gesproken over mod, die de rest van een deling van 2 getallen.
Als u 10% 3, bijvoorbeeld,
het betekent delen 10 door 3, en wat is de rest?
Het zal op 1, dus het is eigenlijk heel nuttig voor een groot deel van de programma's.
Voor Vigenère en Caesar ik ben er vrij zeker van dat jullie allemaal mod gebruikt.
Over wiskundige operatoren, heel voorzichtig zijn bij het combineren van * en /.
>> Bijvoorbeeld, als je dat doet (3/2) * 2 wat ga je krijgen?
[Studenten] 2.
Ja, 2, omdat 3/2 zal zijn 1,5,
maar omdat je aan het doen bent operaties tussen 2 gehele getallen
je eigenlijk alleen maar naar 1 te overwegen,
en dan 1 * 2 gaat worden 2, dus heel, heel voorzichtig
bij het doen van rekenen met gehele getallen, omdat
je zou kunnen krijgen dat 2 = 3, in dat geval.
En ook heel voorzichtig zijn over voorrang.
Je moet meestal haakjes gebruiken om er zeker van dat je weet wat je doet.
Handige sneltoetsen natuurlijk men i + + i + of = 1
of het gebruik van + =.
Dat is hetzelfde als het doen van i = i + 1.
U kunt ook i - of i - = 1,
die hetzelfde is als i = i -1,
iets wat jullie gebruiken veel in voor loops, op zijn minst.
Ook voor *, als u * = en als je dat doet, bijvoorbeeld,
i * = 2 is hetzelfde als zeggen i = i * 2,
en hetzelfde voor divisie.
Als je i / = 2 is hetzelfde als i = i / 2.
>> Nu over functies.
Jullie geleerd dat functies zijn een zeer goede strategie om code op te slaan
terwijl je het programmeren, dus als je wilt om dezelfde taak uit te voeren
in code opnieuw en opnieuw, waarschijnlijk u een functie wilt gebruiken
maar dat je het niet hoeft te kopiëren en de code te plakken over en weer.
Eigenlijk belangrijkste is een functie, en als ik u het formaat van een functie
zul je zien dat dat is vrij duidelijk.
We gebruiken ook functies van een aantal bibliotheken,
bijvoorbeeld printf, GETIN, dat de CS50 bibliotheek
en andere functies, zoals toupper.
Al deze functies worden daadwerkelijk uitgevoerd in andere bibliotheken,
en als je die ketting bestanden in het begin van het programma
je zegt kunt u mij de code voor deze functies
dus ik hoef ze niet te implementeren in mijn eentje?
En u kunt ook uw eigen functies, dus als je programma in te gaan
realiseer je je dat niet bibliotheken niet alle functies die je nodig hebt.
Voor de laatste PSET, bijvoorbeeld, schreven we tekenen, door elkaar husselen en opzoeken,
en het is heel erg belangrijk om te kunnen functies schrijven
omdat ze nuttig zijn, en we gebruiken ze de hele tijd in de programmering,
en het bespaart een hoop code.
Het formaat van een functie is deze.
We hebben return type in het begin. Wat is het rendement type?
Het is gewoon als je de functie gaat om terug te keren.
Als u een functie, bijvoorbeeld, faculteit,
dat gaat een faculteit van een integer berekenen,
waarschijnlijk dat het gaat om een ​​geheel getal ook terugkeren.
Dan is de return type gaat worden int.
Printf eigenlijk een terugkeer type void
omdat je niet wat terugstuurt.
Je bent gewoon afdrukken dingen op het scherm
en het verlaten van de functie na afloop.
Dan heb je de naam van de functie die u kunt kiezen.
Je moet een beetje redelijk, zoals niet kiezen voor een naam als xyz
of zoals x2F.
Probeer om make-up een naam die zinvol is.
>> Bijvoorbeeld, als het factorial we zeggen factoriële.
Als het een functie die gaat iets te tekenen, noem maar op te tekenen.
En dan hebben we de parameters, die ook worden genoemd argumenten,
die net als de middelen die uw functie moet
van uw code om zijn taak uit te voeren.
Als u wilt dat de faculteit van een getal te berekenen
Waarschijnlijk moet je een nummer hebben om een ​​factorieel berekenen.
Een van de argumenten die je gaat hebben is het nummer zelf.
En dan dat het gaat om iets te doen en de waarde op het einde
tenzij het een leegte functie.
Laten we eens een voorbeeld.
Als ik wil een functie die alle getallen vat in een array van integers te schrijven,
allereerst wordt de return type zal zijn int
want ik heb een array van integers.
En dan ga ik naar de functie naam zoals sumArray hebben,
en dan is het gaat om de array zelf te nemen, om int nums,
en vervolgens de lengte van de array, zodat ik weet hoeveel nummers ik moet samenvatten.
Dan moet ik een variabele genaamd bedrag, bijvoorbeeld op 0 initialiseren
en elke keer zie ik een element in de array moet ik toevoegen aan som, dus ik heb een for-lus.
Net zoals Lexi zei, je doet int i = 0, i <lengte en i + +.
En voor elk element in de array ik som + = nums [i],
en dan heb ik het bedrag terug, dus het is zeer eenvoudig, en het scheelt een hoop code
als je gebruik maakt van deze functie een heleboel keer.
We namen een kijkje op voorwaarden.
We hebben als, anders, en anders als.
Laten we eens kijken wat is het verschil tussen deze.
Neem een ​​kijkje op deze 2 codes. Wat is het verschil tussen hen?
De eerste is-eigenlijk de codes wil dat je te vertellen
of een getal +, -, of 0.
De eerste zegt dat als het> 0 dan dat het positief is.
Als het = aan 0 dan is het 0, en als het <0 dan is het negatief.
>> En de andere aan het doen is, indien, anders als, anders.
Het verschil tussen de twee is dat dit daadwerkelijk zal
controleren of> 0, <0 of = 0 drie keer,
dus als je de nummer 2, bijvoorbeeld, gaat het om hier te komen en zeggen:
if (x> 0), en het gaat om ja te zeggen, dus ik print positief.
Maar hoewel ik weet dat het> 0 en het is niet van plan om 0 of <0
Ik ben nog steeds ga doen is het 0, is het <0,
dus ik ben eigenlijk naar binnen van mitsen dat ik niet hoefde te
omdat ik al weet dat het niet gaat om een ​​van deze voorwaarden te voldoen.
Ik kan gebruik maken van de if, else if, else statement.
Het zegt in feite als x = 0 print ik de positieve.
Als het niet, ik ga ook testen.
Als het 2 niet ik ga om dit te doen.
In principe als ik x = 2 zou je zeggen
if (x> 0), ja, zo afdrukken.
Nu ik weet dat het> 0 en dat het voldeed aan de eerst als
Ik ben niet eens gaan deze code uit te voeren.
De code loopt sneller, eigenlijk, 3 keer zo snel als u deze.
We hebben ook geleerd over en en of.
Ik ben niet van plan om te gaan door omdat Lexi al gesproken over hen.
Het is gewoon de && en | | operator.
>> Het enige wat ik zeg is voorzichtig te zijn wanneer u 3 voorwaarden.
Gebruik haakjes want het is erg verwarrend wanneer u een aandoening heeft
en nog een of een andere.
Gebruik haakjes gewoon om zeker te zijn dat uw omstandigheden zinvol
omdat in dat geval, bijvoorbeeld, kun je je voorstellen dat
het zou de eerste toestand en een of de ander door
of de 2 voorwaarden gecombineerd in een en
of de derde, dus wees voorzichtig.
En tot slot hebben we gesproken over schakelaars.
Een switch is erg handig wanneer u een variabele.
Laten we zeggen dat je een variabele als n hebben
dat kan 0, 1, of 2, en voor elk van deze gevallen
je gaat om een ​​taak uit te voeren.
Je kunt zeggen zet de variabele, en het geeft aan dat
de waarde is dan als waarde1 ga ik om dit te doen,
en dan breek ik, wat betekent dat ik ben niet van plan om te kijken naar een van de andere gevallen
omdat we al tevreden dat geval
en dan waarde2 en ga zo maar door, en ik kan ook een standaard schakelaar.
Dat betekent dat als het niet voldoet aan een van de gevallen die ik had
dat ik ga iets anders doen, maar dat is optioneel.
Dat is alles voor mij. Laten we nu eens Tommy.
Oke, dit gaat Week 3-ish te zijn.
Dit zijn enkele van de onderwerpen die we zullen behandelen, crypto, scope, arrays, et cetera.
Gewoon een snelle woord over crypto. We gaan niet naar dit huis hamer.
>> We deden dit in PSET 2, maar voor de quiz zorg ervoor dat je weet dat het verschil
tussen de Caesar cipher en de Vigenère cipher,
hoe deze beide cijfers werk en hoe het is om te coderen
en decoderen van tekst met behulp van deze 2 cijfers.
Vergeet niet, de Caesar cipher draait gewoon aan elk teken met hetzelfde bedrag,
voor dat u mod door het aantal letters in het alfabet.
En Vigenère cijfer, anderzijds, roteert elk teken
door een ander bedrag, dus in plaats van te zeggen
elk karakter geroteerd met 3 Vigenère draait elk karakter
een verschillende hoeveelheid afhankelijk van een zoekwoord
waar elke letter in het trefwoord vertegenwoordigt zo'n ander bedrag
de duidelijke tekst draaien.
Laten we eerst praten over variabele bereik.
Er zijn 2 verschillende typen variabelen.
We hebben lokale variabelen, en deze zullen worden gedefinieerd
buiten hoofd-of buiten een functie of blok,
en deze zullen overal toegankelijk zijn in uw programma.
Als u een functie en in die functie is een while-lus
de grote globale variabele is overal toegankelijk.
Een lokale variabele, daarentegen, is binnen het bereik van de plaats waar het is gedefinieerd.
>> Als u een functie hier, bijvoorbeeld, hebben we deze functie g,
en binnenkant van g er variabele hier genoemd y,
en dat betekent dat dit een lokale variabele.
Hoewel deze variabele y heet
en deze variabele wordt genoemd y deze 2 functies
hebben geen idee wat elkaars lokale variabelen zijn.
Anderzijds, hier we zeggen int x = 5,
en dit is buiten het bereik van elke functie.
Het is buiten het bereik van de belangrijkste, dus dit is een globale variabele.
Dat betekent dat de binnenkant van deze 2 functies als ik zeg x - of x + +
Ik ben toegang tot dezelfde x waarbij deze y en dit y verschillende variabelen.
Dat is het verschil tussen een globale variabele en een lokale variabele.
Qua vormgeving betreft, soms is het waarschijnlijk een beter idee
te houden variabelen lokale wanneer je kan
omdat het hebben van een bos van globale variabelen kan erg verwarrend zijn.
Als u een aantal functies al het wijzigen van de hetzelfde
je zou kunnen vergeten wat als deze functie per ongeluk wijzigt deze wereldwijde,
en deze andere functie niet weten,
en het is behoorlijk verwarrend als je meer code.
Het houden van variabelen lokale wanneer je kan
is alleen een goed ontwerp.
Arrays, vergeet niet, zijn gewoon lijsten van elementen van hetzelfde type.
Binnenkant van CI kan niet over een lijst, zoals 1, 2.0, hallo.
We kunnen gewoon niet doen.
>> Wanneer we een array verklaren C alle elementen moeten van hetzelfde type.
Hier heb ik een serie van 3 gehele getallen.
Hier heb ik de lengte van de array, maar als ik ben gewoon te verklaren het in deze syntax
waar ik aangeven wat alle elementen zijn ik technisch niet dit 3 nodig.
De compiler is slim genoeg om erachter te komen hoe groot de array zou moeten zijn.
Nu wanneer ik wil krijgen of de waarde van een array
dit is de syntax om dat te doen.
Dit ook daadwerkelijk te wijzigen het tweede element van de array, omdat, onthoud,
nummering begint bij 0, niet bij 1.
Als ik wil dat afgelezen waarde ik kan zeggen iets als int x = array [1].
Of als ik wil dat waarde in te stellen, zoals ik hier doe,
Ik kan zeggen array [1] = 4.
Die tijd toegang tot elementen door hun index
of de positie of wanneer zij in de array,
en die lijst begint bij 0.
We kunnen ook arrays van arrays
en dit wordt een meerdimensionale array.
Wanneer we een meerdimensionale array
dat betekent dat we kunnen hebben iets als rijen en kolommen,
en dit is slechts een manier om te visualiseren deze of erover na te denken.
Toen ik een multi-dimensionale array hebben dat betekent dat ik ga beginnen nodig
meer dan 1 index, want als ik een raster
gewoon zeggen wat rij je in geeft ons niet een nummer.
Dat is echt alleen maar om ons een lijst met getallen.
Laten we zeggen dat ik hier deze array.
Ik heb een array met de naam net, en ik zeg het is 2 rijen en 3 kolommen,
en dus dit is een manier van visualiseren.
Als ik zeg dat ik het element wilt krijgen op [1] [2]
dat betekent dat omdat deze rijen en vervolgens de kolommen
Ik ga springen naar rij 1, omdat ik zei 1.
>> Dan ga ik om hier te komen naar kolom 2, en ik ga om de waarde te krijgen 6.
Make sense?
Multi-dimensionale arrays, vergeet niet, zijn technisch slechts een array van arrays.
We kunnen arrays van arrays van arrays.
We kunnen blijven gaan, maar echt een manier om na te denken over
hoe dit wordt aangelegd en wat er aan de hand is om te visualiseren dat
in een raster als dit.
Als we arrays om functies passeren, gaan ze zich gedragen
een beetje anders dan wanneer we passeren regelmatig variabelen om functies
zoals het passeren van een int of een float.
Toen we langs in een int of char of een van deze andere soorten gegevens
we namen een kijkje op als de functie wijzigt
de waarde van die variabele die verandering is niet van plan om zich te verspreiden naar boven
naar de aanroepfunctie.
Met een array, daarentegen, zal gebeuren.
Als ik pas in een array een functie en die functie tot enkele van de elementen,
wanneer ik een back-up naar de functie die het genoemd
mijn array gaat nu om anders te zijn, en de woordenschat van die
is arrays worden doorgegeven door middel van verwijzing, zoals we later zullen zien.
Dit is gerelateerd aan hoe pointers werken, waar deze fundamentele data types,
Anderzijds zijn waarde doorgegeven.
>> We kunnen denken aan dat als het maken van een kopie van een aantal variabele en vervolgens passeren in de kopie.
Het maakt niet uit wat we doen met die variabele.
De aanroepende functie zal niet van bewust dat het werd veranderd.
Arrays zijn net een beetje anders in dat opzicht.
Bijvoorbeeld, zoals we net zagen, de belangrijkste is gewoon een functie
dat kan in 2 argumenten.
Het eerste argument van de belangrijkste functie is argc, of het aantal argumenten,
en het tweede argument wordt genoemd argv,
en dat zijn de werkelijke waarden van deze argumenten.
Laten we zeggen dat ik een programma genaamd this.c,
en ik zeg maken dit, en ik ga deze draaien op de opdrachtregel.
Nu in een aantal argumenten door te geven aan mijn programma noemde dit,
Ik zou zoiets als zeggen. / Dit is cs 50.
Dit is wat we ons voorstellen David te doen elke dag op de terminal.
Maar nu de belangrijkste functie binnenkant van dat programma
heeft deze waarden, dus argc is 4.
Het is misschien een beetje verwarrend, want eigenlijk zijn we slechts terloops in is cs 50.
Dat is slechts 3.
Maar vergeet niet dat het eerste element van argv of het eerste argument
is de naam van de functie zelf.
Dus dat betekent dat we 4 dingen hier hebben,
en het eerste element zal worden. / dit.
En wordt dit weergegeven als een string.
Vervolgens de resterende elementen zijn wat we getypt na de naam van het programma.
Dus net als een terzijde, want we waarschijnlijk zagen in PSET 2,
vergeet niet dat de snaar 50 wordt het gehele getal 50 ≠.
Dus we kunnen niet iets zeggen als, 'int x = argv 3.'
>> Dat is gewoon niet zinvol, want dit is een string, en dit is een geheel getal.
Dus als je wilt converteren tussen de 2, vergeet niet, we gaan
hebben deze magische functie genaamd atoi.
Dat neemt een string en geeft het geheel getal vertegenwoordigde binnenkant van die string.
Dus dat is een makkelijk fout te maken op de quiz,
net te denken dat dit automatisch zal zijn van het juiste type.
Maar weet alleen dat deze altijd zal zijn strings
zelfs indien de string alleen een geheel getal of een teken of een float.
Dus nu laten we praten over lopende tijd.
Als we al deze algoritmen die al deze gekke dingen te doen,
wordt het pas echt nuttig om de vraag te stellen: "Hoe lang duren ze? '
Wij vertegenwoordigen dat met iets genaamd asymptotische notatie.
Dus dit betekent dat - nou ja, laten we zeggen dat we geven ons algoritme
sommige echt, echt, echt grote ingang.
We willen de vraag stellen: "Hoe lang gaat dat duren?
Hoeveel stappen duurt het ons algoritme te lopen
als functie van de grootte van de input? "
Dus de eerste manier waarop we kunnen draaien tijd te beschrijven is met grote O.
En dit is onze worst-case nalooptijd.
Dus als we een array wilt sorteren, en we geven ons algoritme een reeks
dat is, in dalende volgorde als het zou moeten zijn in oplopende volgorde,
dat gaat het ergste geval te zijn.
Dit is onze bovengrens in de maximale lengte van de tijd ons algoritme zal nemen.
Anderzijds bevindt het Ω gaat best-case looptijd beschrijven.
Dus als we een reeds gesorteerde array naar een sorteer-algoritme,
hoe lang zal het duren om het te sorteren?
En dit dan beschrijft een ondergrens op looptijd.
Dus hier zijn slechts enkele woorden die een aantal gemeenschappelijke looptijden te beschrijven.
Deze zijn in oplopende volgorde.
De snelste looptijd hebben we heet constant.
>> Dat betekent dat ongeacht hoeveel elementen die we ons algoritme te geven,
het maakt niet uit hoe groot ons aanbod is, het sorteren hiervan
of doen wat we doen om de array zal altijd de dezelfde hoeveelheid tijd.
Dus kan vertegenwoordigen dat alleen een 1, welke een constante.
We hebben ook gekeken naar logaritmische runtime.
Dus iets als binair zoeken is logaritmisch,
waar we snijden het probleem in de helft elke keer
en dan dingen gewoon hoger te komen van daar.
En als je ooit het schrijven van een O van een faculteit algoritme,
je waarschijnlijk niet overwegen dit als uw dagelijkse werk.
Wanneer we looptijden vergelijken is het belangrijk om in gedachten te houden deze dingen.
Dus als ik een algoritme dat is O (n), en iemand anders
heeft een algoritme O (2n) bestaat eigenlijk asymptotisch equivalent.
Dus als we voorstellen dat n een groot getal als eleventy miljard:
dus als we het vergelijken eleventy miljard naar iets als eleventy miljard + 3,
plotseling dat +3 niet echt meer een groot verschil maken.
Daarom gaan we gaan nadenken over deze dingen gelijkwaardig te zijn.
Dus dingen zoals deze constanten hier, er is 2 x dit, of het toevoegen van een 3,
dit zijn slechts constanten en deze gaan dalen up.
Dus dat is waarom al 3 van deze run tijden zijn hetzelfde als zeggen dat ze O (n).
Evenzo, als we 2 andere looptijden, laten we zeggen dat O (n ³ + 2n ²), we kunnen toevoegen
+ N, + 7, en dan hebben we nog een run time dat is slechts O (n ³).
Ook dit zijn hetzelfde omdat deze - dit zijn niet hetzelfde.
Dit zijn dezelfde dingen, sorry. Dus deze hetzelfde omdat
deze n ³ gaat deze 2n ² domineren.
>> Wat is niet hetzelfde is als we geen tijden als O (n ³) en O (n ²)
omdat dit n ³ is veel groter dan deze n ².
Dus als we exponenten, plotseling begint dit belangrijk voor,
maar als we alleen te maken met factoren als wij zijn hier,
dan is het niet van plan om toe omdat ze gewoon uit te vallen.
Laten we eens een kijkje nemen op enkele van de algoritmen die we tot nu toe hebben gezien
en praten over hun looptijd.
De eerste manier van kijken naar een getal in een lijst, die we zagen, was lineair zoeken.
En de implementatie van lineair zoeken is super eenvoudig.
We hebben een lijst, en we gaan op elk afzonderlijk element kijken in de lijst
totdat we het getal dat we op zoek zijn.
Dat betekent dat in het slechtste geval O (n).
En het ergste geval kan hier als het element
het laatste element, vervolgens met behulp van lineair zoeken we kijken naar elk element
tot we bij de laatste om te weten dat het eigenlijk in de lijst.
We kunnen gewoon niet halverwege opgeven en zeggen: "Het is waarschijnlijk niet daar."
Met lineair zoeken moeten we kijken naar de hele zaak.
De best-case nalooptijd, daarentegen, is constant
want in het beste geval het element die we zoeken is slechts de eerste in de lijst.
Dus het gaat duren ons precies 1 stap, maakt niet uit hoe groot de lijst is
als we op zoek naar het eerste element elke keer.
>> Dus wanneer u zoekt, vergeet niet, is het niet nodig dat onze lijst worden gesorteerd.
Omdat we gewoon gaan om te kijken over elk element, en het maakt eigenlijk niet uit
welke volgorde deze elementen zijn binnen
Een intelligenter zoekalgoritme is zoiets als binaire zoekopdracht.
Vergeet niet dat de uitvoering van binair zoeken is wanneer je gaat
blijven kijken het midden van de lijst.
En omdat we kijken naar het midden, wij eisen dat de lijst is gesorteerd
of anders weten we niet waar het midden is, en we hebben om te kijken over
de hele lijst om het te vinden, en dan op dat moment zijn we gewoon tijd te verspillen.
Dus als we een gesorteerde lijst en we vinden het midden, we gaan naar het midden te vergelijken
om het element dat we op zoek zijn.
Als het te hoog is, dan kunnen we vergeten de rechter helft
omdat we weten dat als ons element is al te hoog
en alles rechts van dit element nog hoger,
dan hebben we niet nodig om er niet meer te kijken.
Wanneer aan de andere kant, als onze element te laag is,
we weten dat alles aan de linkerkant van dat element is ook te laag is,
dus het maakt niet echt zin om daar te kijken, ook niet.
Op deze manier, met elke stap en elke keer als we kijken naar het midden van de lijst,
we gaan ons probleem gehalveerd omdat we ineens weten
een hele hoop nummers die niet kan worden degene die we zoeken.
>> In pseudocode zou dit er als volgt uitzien,
en omdat we het snijden van de lijst in de helft elke keer,
onze worst-case run time springt van lineair naar logaritmisch.
Zo plotseling hebben we log-in stappen om een ​​element in een lijst te vinden.
De beste geval looptijd, is echter nog steeds een constante
want nu, laten we gewoon zeggen dat het element we zoeken is
altijd het exacte midden van de oorspronkelijke lijst.
Dus we kunnen groeien onze lijst zo groot als we willen, maar als het element die we zoeken is in het midden,
dan is het alleen maar om ons 1 stap.
Dus dat is waarom we O (log n) en Ω (1) of constant.
Laten we eigenlijk binair zoeken op deze lijst uit te voeren.
Dus laten we zeggen dat we zijn op zoek naar het element 164.
Het eerste wat we gaan doen is het vinden het middelpunt van deze lijst.
Het is gewoon zo gebeurt het dat het midden gaat in vallen tussen deze 2 nummers,
dus laten we gewoon willekeurig zeggen, elke keer als het middelpunt valt tussen 2 nummers,
laten we gewoon naar boven afronden.
We moeten alleen zorgen dat we dit doen bij elke stap van de weg.
Dus we gaan naar boven afgerond en we gaan om te zeggen dat 161 is het midden van onze lijst.
So 161 <164, en elk element aan de linkerkant van 161
is ook <164, dus we weten dat het niet gaat om ons te helpen op alle
op zoek gaan naar hier omdat het element die we zoeken kan er niet zijn.
Dus wat we kunnen doen is kunnen we gewoon vergeten dat hele linkerhelft van de lijst,
en nu alleen naar het recht van de 161 verder.
>> Dus nogmaals, dit is het middelpunt; laten we gewoon naar boven afronden.
Nu 175 is te groot.
Dus we weten dat het niet gaat om ons te helpen op zoek hier of hier,
dus we kunnen gooien dat weg, en uiteindelijk zullen we raken de 164.
Eventuele vragen over binary search?
Laten we verder gaan van het zoeken door middel van een reeds gesorteerde lijst
om daadwerkelijk het nemen van een lijst met nummers in een willekeurige volgorde
en het maken van die lijst in oplopende volgorde.
Het eerste algoritme hebben we gekeken naar heette bubble sort.
En dit zou eenvoudiger zijn van de algoritmen die we zagen.
Bubble sort zegt dat wanneer een 2 elementen in de lijst zijn niet op zijn plaats,
betekent dat er een groter aantal links van een kleiner aantal,
dan gaan we om ze te verwisselen, want dat betekent dat de lijst zal zijn
"Meer gesorteerd" dan voorheen.
En we gaan gewoon om dit proces weer voort te zetten en opnieuw en opnieuw
totdat uiteindelijk de elementen soort zeepbel op hun juiste plaats en we hebben een gesorteerde lijst.
>> De looptijd van deze gaat worden O (n ²). Waarom?
Wel, omdat in het ergste geval, we gaan elk element te nemen, en
we gaan uiteindelijk te vergelijken met ieder ander element in de lijst.
Maar in het beste geval hebben we een reeds gesorteerde lijst, bubble sort's
gewoon om te gaan door een keer te zeggen: "Nee. Ik heb geen swaps te maken, dus ik ben klaar."
Dus hebben we een best-case looptijd van Ω (n).
Laten we bubble sort draaien op een lijst.
Of, laten we gewoon kijken naar een aantal pseudo-code heel snel.
We willen zeggen dat we willen bijhouden, in elke iteratie van de lus,
bijhouden van al dan niet veranderden we alle elementen.
Dus de reden daarvoor is, gaan we stoppen wanneer we nog niet verwisseld alle elementen.
Dus op het begin van onze lus hebben we niet geruild niets, dus we zullen zeggen dat valse is.
Nu, we gaan om te gaan door de lijst en element vergelijken i tot element i + 1
en als het zo is dat er een groter aantal links van een kleiner aantal,
dan kunnen we gaan gewoon om ze te verwisselen.
>> En dan gaan we niet vergeten dat we een element verwisseld.
Dat betekent dat we verder moeten gaan door de lijst in ieder geval nog 1 keer
omdat de toestand waarin we gestopt wanneer de gehele lijst al gesorteerd,
dit betekent dat we hebben geen swaps gemaakt.
Dus dat is de reden waarom onze toestand hier beneden is 'terwijl sommige elementen zijn verwisseld.'
Dus nu laten we gewoon kijken naar deze draait op een lijst.
Ik heb de lijst 5,0,1,6,4.
Bubble sort gaat helemaal links beginnen, en het gaat om te vergelijken
het i elementen, dus 0 tot i + 1, dat element 1.
Het gaat om te zeggen, nou 5> 0, maar nu 5 is aan de linkerkant,
dus ik moet de 5 en de 0 te wisselen.
Als ik ze te verwisselen, opeens krijg ik dit andere lijst.
Nu 5> 1, dus we gaan om ze te verwisselen.
5 is niet> 6, dus we hoeven niet te doen hier niets.
Maar 6> 4, dus we moeten wisselen.
Nogmaals, we moeten lopen door de hele lijst om uiteindelijk te ontdekken
dat deze buiten de orde, we ruilen ze,
en op dit punt moeten we lopen door de lijst nog 1 keer
om ervoor te zorgen dat alles in zijn beschikking, en op dit punt bubble sort is voltooid.
Een ander algoritme voor het nemen van een aantal elementen en het sorteren ervan is selectie sorteren.
Het idee achter selection sort is dat we gaan het opbouwen van een gesorteerd deel van de lijst
Een element per keer.
>> En de manier waarop we dat doen is door het opbouwen van het linker segment van de lijst.
En eigenlijk, elke - op elke stap, we gaan naar het kleinste element die we nog hebben te nemen
dat is nog niet gesorteerd, en we gaan om het te verplaatsen in die gesorteerd segment.
Dat betekent dat we moeten voortdurend vinden van de minimale ongesorteerde element
en neem dan dat minimum element en ruilen met wat
meest linkse element dat niet is gesorteerd.
De looptijd van deze gaat worden O (n ²), omdat in het ergste geval
We moeten alle elementen te vergelijken elk ander element.
Omdat we zeggen dat als we beginnen bij de linker helft van de lijst, moeten we
om door de gehele rechter segment het kleinste element vinden.
En dan, nogmaals, we moeten gaan over de gehele rechter segment en
blijven gaan over die over en over en weer.
Dat gaat n ². We gaan een behoefte aan lus binnenkant van een ander for-lus
wat suggereert n ².
In het beste geval denken, laten we zeggen dat we geven het een reeds gesorteerde lijst;
we eigenlijk niet beter dan n ².
Omdat selectie sorteren heeft geen manier om te weten dat
de minimale element is slechts degene die ik toevallig te kijken.
Het moet nog steeds om ervoor te zorgen dat dit eigenlijk het minimum.
>> En de enige manier om ervoor te zorgen dat het de minimale, met behulp van dit algoritme,
is om weer te kijken naar elk element.
Dus echt, als je het - als je selectie sorteren een reeds gesorteerde lijst,
het is niet van plan om beter te doen dan het geven van een lijst die nog niet is gesorteerd.
By the way, als het gebeurt om het geval dat er iets is O (iets)
en de omega van iets, kunnen we alleen maar zeggen meer kort en bondig dat het θ van iets.
Dus als je ziet dat overal komen, dat is wat precies dat betekent.
>> Als er iets is theta van n ², is het zowel grote O (n ²) en Ω (n ²).
Zodat je best case en worst case, is het niet een verschil maken,
het algoritme gaat om hetzelfde te doen elke keer.
Dus dit is wat pseudocode voor selectie sorteren eruit zou kunnen zien.
We principe gaan om te zeggen dat ik wil itereren over de lijst
van links naar rechts, en bij elke herhaling van de lus, ik ga verhuizen
de minimale element in deze gesorteerd deel van de lijst.
En als ik daar te bewegen iets, ik heb nooit moeten opnieuw kijken naar dat element.
Want zodra ik een element wisselen in het linker segment van de lijst, het is gesorteerd
want we doen alles wat in oplopende volgorde met behulp van minima.
Dus we zeiden, oke, we zijn op positie i, en we moeten om naar te kijken alle elementen
rechts van i om de minimum vinden.
Dat betekent willen we van i + 1 zien op het einde van de lijst.
En nu, als het element dat we op dit moment op zoek bent naar minder dan het minimale tot nu toe,
die, vergeet niet dat we het starten van de minimum uit om gewoon
wat element zijn we momenteel op, ik ga ervan uit dat is het minimum.
Als ik een element dat is kleiner dan dat, dan ga ik zeggen, oke,
goed, heb ik gevonden een nieuwe minimum.
Ik ga om te onthouden waar dat minimum was.
>> Dus nu, nadat ik heb doorgemaakt dat recht ongesorteerd segment,
Ik kan zeggen dat ik ga tot het minimum element te wisselen met het element dat in staat i.
Dat gaat bouwen mijn lijst, mijn gesorteerd deel van de lijst van links naar rechts,
en we niet ooit opnieuw te kijken naar een element wanneer het eenmaal in dat gedeelte.
Zodra we geruild.
Dus laten we selection sort draaien op deze lijst.
De blauwe element hier gaat de i, en de rode element zal de minimum element.
Dus ik begint helemaal links van de lijst zodat bij 5.
Nu moeten we de minimale ongesorteerde element te vinden.
Dus we zeggen 0 <5, dus 0 is mijn nieuwe minimum.
>> Maar ik kan niet stoppen, want ook al kunnen we herkennen dat 0 is de kleinste,
we moeten doorlopen om de andere elementen van de lijst om er zeker van.
Dus 1 is groter, 6 is groter, 4 is groter.
Dat betekent dat na het bekijken van al deze elementen, die ik heb bepaald 0 is de kleinste.
Dus ik ga naar de 5 en de 0 te wisselen.
Zodra ik dat wisselen, ga ik een nieuwe lijst te krijgen, en ik weet dat ik nooit opnieuw te kijken naar dat 0
want zodra ik heb geruild, ik heb losten het en we zijn klaar.
Nu is het gewoon zo gebeurt het dat de blauwe element weer is het 5,
en we moeten kijken naar de 1, de 6 en de 4 die een vast
is de kleinste minimale element, dus we wisselen de 1 en de 5.
Nogmaals, we moeten kijken naar - vergelijk de 5 naar de 6 en de 4,
en we gaan naar de 4 en de 5 te wisselen, en ten slotte, te vergelijken
die 2 nummers en wisselen ze totdat we onze gesorteerde lijst.
Hebt u vragen over de selectie sorteren?
Oke. Laten we hier naar het laatste onderwerp, en dat is recursie.
>> Recursie, onthoud, is dit echt meta ding waarin een functie
herhaaldelijk noemt zichzelf.
Dus op een gegeven moment, terwijl onze fuction wordt herhaaldelijk die zichzelf,
moet er een bepaald punt waar we stoppen met bellen onszelf.
Want als we dat niet doen, dan zijn we gaan gewoon door te gaan voor altijd doen,
en ons programma is gewoon niet van plan om te beëindigen.
We noemen deze toestand het nulalternatief.
En het nulalternatief zegt, in plaats van het aanroepen van een functie weer,
Ik ga gewoon een bepaalde waarde terug te keren.
Dus zodra we terug een waarde, hebben we gestopt met bellen onszelf,
en de rest van de gesprekken die we tot nu toe gemaakt kunt ook terugkeren.
Het tegenovergestelde van het nulalternatief is de recursieve geval is.
En dit is wanneer we willen nog een oproep te doen aan de functie die we op dit moment zijn binnen
En we waarschijnlijk, hoewel niet altijd, wil je verschillende argumenten te gebruiken.
>> Dus als we een functie genaamd f, en f heeft net gebeld neem 1 argument,
en we blijven noemen f (1), f (1), f (1), en het gewoon zo gebeurt het dat
het argument 1 valt in recursieve geval zijn we nog steeds niet van plan te stoppen.
Zelfs als we een basisscenario, moeten we ervoor zorgen dat we uiteindelijk gaan dat base case te raken.
We hebben niet alleen te houden een verblijf in deze recursieve geval.
Over het algemeen, als we onszelf noemen, we waarschijnlijk gaan om een ​​ander argument hebben elke keer.
Hier is een heel eenvoudige recursieve functie.
Dus berekent de faculteit van een getal.
Up Top hier hebben we ons basisscenario.
In het geval dat n ≤ 1, we niet nog een keer te bellen faculteit.
We gaan om te stoppen, we gaan gewoon naar een bepaalde waarde terug te keren.
Als dit niet waar is, dan gaan we onze recursieve geval geraakt.
Let hier op dat we niet alleen maar bellen faculteit (n), want dat zou niet erg behulpzaam.
We gaan noemen faculteit van iets anders.
>> En zodat u kunt zien, uiteindelijk als we een faculteit (5) of iets voorbij,
we gaan bellen faculteit (4) en ga zo maar door, en uiteindelijk gaan we dit referentiemodel te raken.
Dus dit ziet er goed uit. Laten we eens kijken wat er gebeurt als we daadwerkelijk uitvoeren van deze.
Dit is de stapel, en laten we zeggen dat de belangrijkste zal deze functie aan te roepen met een argument (4).
Dus zodra faculteit ziet en = 4, factorieel belt zelf.
Nu, plotseling, we hebben factorial (3).
Dus deze functies zullen blijven groeien totdat uiteindelijk raken we ons basisscenario.
Op dit punt, de return waarde van deze is de terugkeer (nx de return waarde van deze),
de return waarde hiervan is nx de return waarde van deze.
Uiteindelijk moeten we een getal te raken.
Op de top hier, zeggen we terug 1.
Dat betekent dat als we eenmaal terug dat aantal kunnen we knallen dit uit de stapel.
Dus factorial (1) wordt gedaan.
Bij een rendement, dit faculteit (1) retourneert, deze terugkeer naar 1.
De return waarde van deze, onthoud, was nx de return waarde van deze.
Zo plotseling, deze man weet dat ik wil 2 terug te keren.
>> Dus onthoud, return waarde van dit is gewoon nx de return waarde hier boven.
Dus nu kunnen we zeggen 3 x 2, en tot slot, hier kunnen we zeggen
dit is gewoon gaat worden 4 x 3 x 2.
En zodra dit weer, we aan de slag om een ​​enkel geheel getal binnenkant van de belangrijkste.
Eventuele vragen over recursie?
Oke. Dus er is meer tijd voor vragen aan het eind,
maar nu Jozef zal betrekking hebben op de resterende onderwerpen.
>> [Joseph Ong] Oke. Dus nu hebben we gesproken over recursies,
Laten we een beetje praten over wat samenvoegen soort is.
Samenvoegen soort is in feite een andere manier van het sorteren van een lijst met getallen.
En hoe het werkt is, met merge sort heb je een lijst, en wat we doen is
we zeggen, laten we deze opgesplitst in 2 helften.
We zullen eerst rennen weer samenvoegen sorteren op de linker helft,
dan zullen we lopen samen te voegen sorteren op de rechter helft,
en dat geeft ons nu 2 helften die worden gesorteerd, en nu gaan we combineren deze helften.
Het is een beetje moeilijk te zien zonder een voorbeeld, dus we gaan door de bewegingen en zie wat er gebeurt.
Dus je begint met deze lijst, hebben we het opgesplitst in 2 helften.
We lopen samen te voegen sorteren op de linker helft eerst.
Dus dat is de linker helft, en nu hebben we ze nogmaals uit te voeren door middel van deze lijst
die wordt doorgegeven in merge sort, en dan kijken we, nogmaals,
aan de linkerkant van deze lijst en we lopen samen te voegen sorteren op.
Nu krijgen we tot een lijst met 2 nummers,
en nu de linkerhelft is slechts 1 element lang, en we kunnen niet
splitsen van een lijst die is slechts 1 element in de helft, dus we zeggen, als we 50 hebben,
Dit is slechts 1 element, het is al gesorteerd.
>> Zodra we klaar zijn met dat, kunnen we zien dat we kunnen
overgaan tot de rechter helft van deze lijst,
en 3 wordt ook gesorteerd, en dus nu dat beide helften van deze lijst zijn gesorteerd
we kunnen lid worden van deze nummers weer bij elkaar.
Dus we kijken bij 50 en 3, 3 kleiner dan 50, zo gaat in en vervolgens 50 wordt in
Nu, dat is gedaan, gaan we terug naar die lijst en soort het is rechter helft.
42 is een eigen nummer, dus het is al gesorteerd.
Dus nu vergelijken we deze 2 en 3 is kleiner dan 42, zodat wordt gezet in de eerste,
nu 42 wordt gezet in, en 50 wordt zetten inch
Nu, dat is gesorteerd, gaan we helemaal terug naar de top, 1337 en 15.
Nou, we nu kijken naar de linker helft van deze lijst; 1337 is op zichzelf dus het is gesorteerd en hetzelfde met 15.
Dus nu combineren we deze 2 nummers aan die oorspronkelijke lijst, 15 <1337 te sorteren,
zo gaat het in de eerste, dan is 1337 gaat binnen
En nu hebben we beide helften van de oorspronkelijke lijst gesorteerd boven.
En alles wat we hoeven te doen is combineren.
We kijken naar de eerste 2 nummers van deze lijst, 3 <15, dus het gaat in het soort reeks eerste.
15 <42, dus het gaat inch Nu, 42 <1337, dat gaat binnen
50 <1337, dus het gaat inch En merken dat we slechts 2 nummers nam af van deze lijst.
Dus we zijn niet alleen afwisselend tussen de 2 lijsten.
We zijn gewoon op zoek naar het begin, en we nemen het element
dat is kleiner en dan zetten het in ons aanbod.
Nu hebben we samengevoegd alle helften en we zijn klaar.
>> Heeft u vragen over samenvoegen soort? Ja?
[Student] Als het splitsen in verschillende groepen, waarom ze niet gewoon splitsen keer
en je hebt 3 en 2 in een groep? [Rest van vraag onverstaanbaar]
De reden - dus de vraag is, waarom kunnen we niet gewoon samen te voegen in die eerste stap nadat we ze hebben?
De reden dat we dit kunnen doen, beginnen bij de meest linkse elementen van beide zijden,
en neem dan de kleinere en zet het in, is dat we dat deze weten
individuele lijsten zijn in gesorteerd orders.
Dus als ik ben op zoek naar de meest linkse elementen van beide helften,
Ik weet dat ze gaan de kleinste elementen van die lijsten.
Dus ik kan ze in het kleinste element plekjes van deze grote lijst.
Aan de andere kant, als ik kijk naar deze 2 lijsten in het tweede niveau daar,
50, 3, 42, 1337 en 15, zijn deze niet gesorteerd.
Dus als ik kijk naar 50 en 1337, ga ik 50 eerste in mijn lijst.
Maar dat betekent niet echt zinvol, want 3 is het kleinste element uit al die.
Dus de enige reden dat we dit kunnen combineren stap te doen is omdat onze lijsten al zijn gesorteerd.
Daarom moeten we naar beneden helemaal tot op de bodem
want als we slechts een enkel nummer hebt, weet je dat een enkel nummer
in en van zichzelf is al een gesorteerde lijst.
>> Nog vragen? Nee?
Complexiteit? Nou, je kunt zien dat bij elke stap is er eind nummers,
en we kunnen verdelen een lijst in de helft log n keer,
dat is waar we dit n x log n complexiteit.
En je zult zien het beste geval voor merge sort is n log n, en het gewoon zo gebeurt
dat de slechtste of de Ω daar, ook n log n.
Iets om in gedachten te houden.
Moving on, laten we verder gaan met een aantal super basic file I / O.
Als je keek naar Scramble, zult u merken dat we hadden een soort van systeem
waar je kon schrijven naar een logbestand als je leest door de code.
Laten we eens kijken hoe je zou kunnen doen.
Nou, we hebben fprintf, die u kunt zien als gewoon printf,
maar slechts afdrukken naar een bestand plaats, en daarmee de f begin.
Dit soort code hier, wat het doet is, zoals je misschien al hebt gezien in Scramble,
gaat het door uw 2-dimensionale array uitprinten rij voor rij wat de nummers zijn.
In dit geval, printf drukt om uw terminal of wat wij noemen de standaard output van een hoofdstuk.
>> En nu, in dit geval, alles wat we moeten doen is het vervangen printf met fprintf,
vertellen wat bestand dat u wilt afdrukken, en in dit geval gewoon print deze aan dat bestand
in plaats van deze af te drukken naar uw terminal.
Nou, dan is dat roept de vraag op: Waar we dit soort bestand te krijgen van, toch?
We passeerden in te loggen om deze fprintf fuction, maar we hadden geen idee waar het vandaan kwam.
Nou, in het begin van de code, wat we hadden was dit stuk code hier,
die in feite zegt dat open het bestand log.txt noemt.
Wat wij doen na dat is dat we ervoor moeten zorgen dat het bestand daadwerkelijk succesvol geopend.
Dus het kan mislukken om verschillende redenen, je niet genoeg ruimte hebt op je computer, bijvoorbeeld.
Dus het is altijd belangrijk voordat u eventuele werkzaamheden met het bestand
dat we controleren of dat bestand met succes is geopend.
Dus wat dat een, dat is een argument om fopen, nou ja, kunnen we een bestand openen op vele manieren.
Wat we wel kunnen is doen, kunnen we doorgeven w, wat betekent overschrijven het bestand als het reeds verlaat,
We kunnen passeren een a, die zij toevoegen aan het einde van het bestand in plaats van het dwingende,
of we kunnen specificeren r, dat wil zeggen, laten we het bestand openen als alleen-lezen.
Dus als het programma probeert om eventuele wijzigingen aan te brengen in het bestand,
schreeuwen tegen hen en laat ze niet doen.
Ten slotte, wanneer we klaar zijn met het bestand, klaar mee operaties op het,
moeten we ervoor zorgen dat we het bestand sluiten.
En dus aan het eind van uw programma, ga je weer doorgeven
dit bestand die u hebt geopend, en gewoon sluiten.
Dus dit is iets belangrijks dat je moet zorgen dat je doet.
Dus onthoud u een bestand kunt openen, dan kunt u schrijven naar het bestand,
doen operaties in het bestand, maar dan moet je het bestand te sluiten aan het eind.
>> Hebt u vragen over fundamentele file I / O? Ja?
[Student vraag, onverstaanbaar]
Precies hier. De vraag is, betekent dit log.txt bestand verschijnen waar?
Nou, als je gewoon geven log.txt, creëert het in dezelfde map als het uitvoerbare bestand.
Dus als je bent - >> [Student vraag, onverstaanbaar]
Ja. In dezelfde map, of in dezelfde directory, zoals jij dat noemt.
Nu geheugen, stack en heap.
Dus hoe is het geheugen vastgelegd in de computer?
Nou, kun je je voorstellen als een soort geheugen van dit blok hier.
En in het geheugen hebben we wat de hoop vast daar, en de stapel dat is daar beneden geroepen.
En de heap groeit naar beneden en de stapel omhoog groeit.
Dus als Tommy genoemd - oh, goed, en we hebben die andere 4 segmenten die ik zal krijgen in een tweede -
Zoals Tommy al eerder zei, je weet hoe zijn functies noemen zichzelf en elkaar bellen?
Ze bouwen dit soort stack frame.
Nou, als de belangrijkste oproepen foo, foo wordt op de stapel gelegd.
Foo noemt, bar krijgen de op de stapel gelegd, en dat wordt op de stapel gelegd na.
En als ze terugkeren, ze krijgen elk genomen uit de stapel.
Wat moet elk van deze locaties en het geheugen te houden?
En de top, welke de tekst segment bevat het programma zelf.
Dus de machine code, dat er, zodra het samenstellen van je programma.
Vervolgens alle globale variabelen geïnitialiseerd.
>> Dus je hebt globale variabelen in je programma, en je zegt als, a = 5,
die wordt gezet in dat segment, en rechts onder dat,
u nog niet geïnitialiseerde gegevens opslaat, die net is int a,
maar je hoeft niet zeggen dat het gelijk is aan wat dan ook.
Realiseer dit zijn globale variabelen, zodat ze buiten de belangrijkste.
Dus dit betekent dat elke globale variabelen die worden gedeclareerd maar niet geïnitialiseerd.
Dus wat er in de hoop? Geheugen toegewezen met behulp van malloc, die we zullen krijgen in een beetje.
En ten slotte, met de stapel u lokale variabelen
en alle functies die u zou kunnen noemen in een van hun parameters.
Het laatste wat, hoef je niet echt te weten wat de omgevingsvariabelen te doen,
maar wanneer je programma uit te voeren, er is geassocieerd iets, zoals
dit is de gebruikersnaam van de persoon die liep van het programma.
En dat gaat om een ​​soort van op de bodem.
In termen van het geheugen-adressen, die zijn hexadecimale waarden,
de waarden aan de top beginnen bij 0, en ze gaan helemaal naar beneden naar de bodem.
In dit geval, als je op de 32-bits systeem,
het adres aan de onderkant gaat worden 0x, gevolgd door af, want dat is 32 bits,
dat 8 bytes, en in dit geval 8 bytes overeenkomt met 8 hexadecimale cijfers.
Dus hier beneden je gaat te hebben, zoals, 0xFFFFFF, en daar zul je 0.
Dus wat zijn pointers? Sommigen van u kunnen niet hebben behandeld in de rubriek voor.
maar we hebben er overheen te gaan in college, dus een pointer is gewoon een gegevenstype
welke winkels, in plaats van een soort van waarde zoals 50, dan het adres van een locatie in het geheugen worden opgeslagen.
Net als dat het geheugen [onverstaanbaar].
Dus in dit geval, wat wij hebben is, hebben we een pointer naar een integer of een int *,
en het bevat dit hexadecimale adres van 0xDEADBEEF.
>> Dus wat we hebben is, nu, deze pointer wijst naar een locatie in het geheugen,
en dat is nog maar een, de waarde 50 is op dit geheugenlocatie.
Op sommige 32-bits systemen, op alle 32-bits systemen, pointers nemen 32 bits of 4 bytes.
Maar bijvoorbeeld op een 64-bits systeem pointers zijn 64 bits.
Dus dat is iets wat je wilt in gedachten te houden.
Dus op een eind-bits systeem, een pointer is eind bits lang.
Pointers zijn een soort van moeilijk te verteren zonder extra dingen,
dus laten we gaan door een voorbeeld van dynamisch geheugen toewijzing.
Wat dynamisch geheugen toewijzing voor je doet, of wat wij noemen malloc,
het laat je toe te wijzen een soort van gegevens buiten de set.
Zodat deze gegevens soort meer permanent voor de duur van het programma.
Want zoals u weet, als je verklaart x binnenkant van een functie, en die functie terugkeert,
u niet langer toegang tot de gegevens die opgeslagen zijn in x.
Wat pointers laat ons doen, is ze ons laten slaan geheugen of op te slaan waarden
in een ander segment van het geheugen, namelijk de heap.
Nu als we eenmaal uit de terugkeer van functie, zolang we een pointer hebben
naar die locatie in het geheugen, dan wat we kunnen doen is dat we kunnen gewoon kijken naar de waarden daar.
Laten we eens kijken naar een voorbeeld: Dit is ons geheugen lay-out weer.
En we hebben deze functie, de belangrijkste.
Wat het doet is - oke, zo simpel, toch? - Int x = 5, dat is gewoon een variabele op de stack in de belangrijkste.
>> Anderzijds, nu verklaren een pointer die de functie giveMeThreeInts noemt.
En nu gaan we in deze functie en maken we een nieuwe stack frame voor.
Echter, in deze stack frame, verklaren wij int * temp,
die in mallocs 3 gehele getallen voor ons.
Dus grootte van int zal ons hoeveel bytes deze int is,
en malloc geeft ons dat veel bytes aan ruimte op de heap.
Dus in dit geval, hebben wij voldoende ruimte voor 3 integers,
en de hoop is weg daar, dat is waarom ik getekend heb het hoger.
Zodra we klaar zijn, we terug komen hier, hoeft u alleen maar 3 ints terug,
en geeft het adres in dat geval het waar dat geheugen.
En we wijzer = switch, en daar hebben we gewoon een pointer.
Maar wat die functie terugkeert is hier gestapeld en verdwijnt.
Dus temp verdwijnt, maar we hebben nog steeds het adres van waar
die 3 getallen bevinden zich binnenin net.
Dus in deze set, de pointers zijn scoped lokaal voor de gestapelde frame,
maar het geheugen waarnaar zij verwijzen in de heap.
>> Is dat logisch?
[Student] Kunt u dat herhalen? >> [Joseph] Ja.
Dus als ik terug een beetje, zie je dat temp toegewezen
wat geheugen op de heap daar.
Dus als deze functie giveMeThreeInts terug, deze stapel hier gaat verdwijnen.
En daarmee een van de variabelen in dit geval pointer die is toegewezen in gestapelde frame.
Dat gaat verdwijnen, maar sinds we terug temp
en we wijzer = temp, wijzer nu gaat om hetzelfde geheugen van locatie als temperatuur was wijzen.
Dus nu, ook al verliezen we temp, dat de lokale aanwijzer,
we hebben nog steeds het geheugenadres van wat het was te wijzen op de binnenkant van die variabele pointer.
Vragen? Dat kan een soort van een verwarrend onderwerp zijn als je dat nog niet gegaan over het in sectie.
Wij kunnen, zal uw TF zeker gaan erover en natuurlijk kunnen we vragen beantwoorden
aan het einde van het sessie voor deze.
Maar dit is een soort van een complex onderwerp, en ik heb meer voorbeelden die gaan verschijnen
dat zal duidelijker worden wat pointers eigenlijk zijn.
>> In dit geval pointers gelijkwaardig zijn aan arrays,
dus ik kan deze pointer net als hetzelfde als een int array.
Dus ik ben het indexeren in 0, en het veranderen van de eerste gehele getal 1,
veranderende tweede gehele getal 2 en de 3e gehele getal 3.
Dus meer op pointers. Nou, Binky te roepen.
In dit geval hebben we toegewezen een pointer, of we uitgeroepen tot een pointer,
maar in eerste instantie, toen ik net een pointer verklaard, het is niet te wijzen op ergens in het geheugen.
Het is gewoon vuilnis waarden binnen het.
Dus ik heb geen idee waar deze pointer naar wijst.
Het heeft een adres dat net is gevuld met 0 en 1, waar het in eerste instantie werd verklaard.
Ik kan niets doen met deze totdat ik noem malloc op het
en dan geeft me een beetje ruimte op de heap waar ik kan binnen zetten waarden.
Dan weer, ik weet niet wat er in dit geheugen.
Dus het eerste wat ik moet doen is controleren of de installatie voldoende geheugen had
om mij terug 1 geheel getal in de eerste plaats, dat is de reden waarom ik dit doe controleren.
Als wijzer nul is, dat betekent dat het niet genoeg ruimte of een andere fout is opgetreden,
dus ik moet af te sluiten van mijn programma.
Maar als het wel lukt, nu kan ik gebruik maken van dat pointer
en wat * pointer doet is het volgende waar het adres is
waar die waarde, en stelt deze gelijk aan 1.
Dus hier zijn we te controleren of dat het geheugen bestaan.
>> Als je eenmaal weet dat het bestaat, kun je erin steekt
welke waarde u wilt erin steekt, in dit geval 1.
Zodra we klaar zijn met het, moet je die pointer bevrijden
want we moeten terug naar het systeem dat geheugen dat u gevraagd om in de eerste plaats.
Omdat de computer weet niet wanneer we klaar zijn met het.
In dit geval zijn we expliciet te vertellen, oke, we zijn klaar met dat geheugen.
Als een ander proces nodig heeft, een ander programma nodig heeft, voel je vrij om verder te gaan en mee te nemen.
Wat we ook kunnen doen is dat we kunnen gewoon het adres van de lokale variabelen op de set.
Dus int x is binnen de gestapelde frame van de belangrijkste.
En als we dit teken te gebruiken, dit en operator, wat het doet is
duurt x en x is slechts enkele gegevens in het geheugen, maar het heeft een adres.
Het is ergens bevindt. Dus door te bellen & x, wat dit doet is het geeft ons het adres van x.
Door dit te doen, maken we wijzer punt waar x is in het geheugen.
Nu hebben we gewoon iets als * x, we gaan naar 5 terug te krijgen.
De ster wordt genoemd dereferentie het.
Je volgt het adres en je krijgt de waarde van het daar opgeslagen.
>> Nog vragen? Ja?
[Student] Als u dit niet doet de 3-puntige ding, is het nog steeds compileren?
Ja. Als u dit niet doet de 3-pointer ding, het is nog steeds te compileren,
maar ik zal je laten zien wat er gebeurt in een tweede, en zonder dat te doen,
dat is wat wij noemen een geheugenlek. Je geeft het systeem
terug zijn geheugen, dus na een tijdje het programma gaat ophopen
geheugen dat het niet gebruikt, en niets anders kan gebruiken.
Als je ooit hebt gezien Firefox met 1,5 miljoen kilobytes op uw computer,
in de task manager, dat is wat er gaande is.
Je hebt een geheugenlek in het programma dat ze niet hanteren.
Dus hoe werkt pointers werk?
Nou, pointers is een soort van indexering in een array.
In dit geval, ik heb een pointer, en wat ik doe is ik maak pointer wijzen op het eerste element
van deze array van 3 gehele getallen die ik heb toegewezen.
Dus nu wat ik doe, ster aanwijzer verandert alleen het eerste element in de lijst.
Star aanwijzer +1 punten hier.
Dus aanwijzer op hier, wijzer +1 is hier voorbij, aanwijzer +2 is hier.
>> Dus gewoon het toevoegen van 1 is hetzelfde als het verplaatsen langs deze array.
Wat wij doen is, als we wijzer +1 krijgt u dan het adres hier,
en om de waarde in hier te komen, zet je een ster in de gehele uitdrukking
het dereference.
Dus, in dit geval, waarin ik de eerste locatie in deze array 1,
tweede locatie 2 en derde locatie 3.
Dan wat ik doe hier is dat ik onze pointer +1 afdrukken,
die geeft gewoon me 2.
Nu ben ik het verhogen pointer, zodat pointer gelijk pointer +1,
die beweegt deze naar voren.
En dus nu als ik print pointer +1, pointer +1 is nu 3,
in dit geval afgedrukt 3.
En om gratis iets, de pointer die ik geef het
moet wijzen op het begin van de array die terug kreeg ik van malloc.
Dus, in dit geval, als ik tot 3 noemen hier, zou dit niet juist zijn,
omdat het in het midden van de array.
Ik moet aftrekken om naar de oorspronkelijke locatie
de eerste eerste plek voordat ik het kan bevrijden.
Dus, hier is een meer betrokken voorbeeld.
In dit geval we verdeling 7 karakters in een karakter array.
>> En in dit geval wat we doen is dat we een lus over de eerste 6 van hen,
en we zijn oprichting ervan tot Z.
Dus voor int i = 0, i> 6, i + +,
Dus, pointer + zal ik geef ons, in dit geval,
pointer, pointer +1, pointer +2, aanwijzer +3, en zo verder en zo voort in de lus.
Wat het gaat doen, is het wordt dat adres, referentie aan het te krijgen van de waarde,
en wijzigingen die waarde een Z.
Dan herinner aan het einde dit is een string, toch?
Alle strings moeten eindigen met de nul eindigt karakter.
Dus, wat ik doe is in pointer 6 Ik, de null-terminator karakter zetten inch
En nu, wat ik eigenlijk aan het doen ben hier wordt printf tenuitvoerlegging door een string, toch?
>> Dus, als printf nu als het aan het einde van een string?
Als het de nul eindigt karakter raakt.
Dus, in dit geval mijn oorspronkelijke wijzer naar het begin van deze array.
Ik print het eerste teken uit. Ik beweeg het over een.
Print ik dat karakter uit. Ik beweeg het over.
En ik blijf dit doen tot ik het einde bereikt.
En nu het einde * pointer zal dereference deze en de nul eindigt karakter terug te krijgen.
En dus mijn while loop wordt alleen uitgevoerd wanneer die waarde niet de nul eindigt karakter.
Zo, nu ik uit te sluiten van deze lus.
En dus als ik aftrekken 6 van deze pointer,
Ik ga helemaal terug naar het begin.
Vergeet niet, ik doe dit omdat ik moet naar het begin om het te bevrijden.
>> Dus, ik weet dat was veel. Zijn er nog vragen?
Alsjeblieft, ja?
[Student vraag onverstaanbaar]
Kunt u zeggen dat harder? Sorry.
[Student] Op de laatste dia vlak voordat je de aanwijzer bevrijd,
waar was je eigenlijk het veranderen van de waarde van de pointer?
[Joseph] Dus, hier. >> [Student] Oh, oke.
[Joseph] Dus, ik heb een pointer minus minus, rechts,
die beweegt het ding terug een, en dan zal ik bevrijden,
omdat deze pointer moet worden gewezen op het begin van de array.
[Student] Maar dat zou niet nodig was je gestopt na die lijn.
[Joseph] Dus als ik was gestopt na deze, zou dit worden beschouwd als een geheugenlek,
omdat ik niet lopen het gratis.
[Student] I [onverstaanbaar] na de eerste drie regels waar je moest aanwijzer +1 [onverstaanbaar].
[Joseph] Uh-huh. Dus, wat is de vraag daar?
Sorry. Nee, nee. Ga, ga, alsjeblieft.
[Student] Dus, je bent niet het veranderen van de waarde van pointers.
Je zou het niet hebben moeten aanwijzer minus minus doen.
[Joseph] Ja, precies.
Dus, als ik wijzer +1 en +2 pointer te doen,
Ik doe pointer gelijk pointer +1.
Dus blijft de aanwijzer precies die op het begin van de array.
Het is pas als ik dat doe plus plus dat het zich de waarde terug in de aanwijzer,
dat het beweegt eigenlijk dit samen.
Oke.
Meer vragen?
>> Nogmaals, als dit is een soort van overweldigend, zal dit worden behandeld in sessie.
Vraag uw onderwijs collega over, en we kunnen vragen te beantwoorden op het einde.
En meestal hebben we niet graag dit minus ding te doen.
Dit heeft te verlangen mij het bijhouden van hoeveel ik heb gecompenseerd in de array.
Dus, in het algemeen, is dit gewoon uit te leggen hoe pointers werken.
Maar wat we meestal willen doen is dat we graag een kopie van de wijzer te maken,
en dan zullen we gebruik maken van die kopie als we bewegen in de string.
Dus, in deze het geval u gebruik maken van de kopie aan de gehele reeks af te drukken,
maar we hoeven niet te doen alsof wijzer min 6 of bijhouden hoeveel we verhuisden in deze,
alleen maar omdat we weten dat onze oorspronkelijke punt nog steeds gewezen op het begin van de lijst
en alles wat we veranderd was dit exemplaar.
Dus, in het algemeen, te wijzigen kopieën van uw originele aanwijzer.
Probeer niet te sorteren van soortgelijke - Doe niet wijzigen originele exemplaren.
Proberen om alleen kopieën van uw originele te veranderen.
Dus, je opvalt als we langs de string in printf
je hoeft niet om een ​​ster in de voorkant van het als we met alle andere referentie aan, toch?
Dus, als je drukt de volledige tekenreeks% s verwacht is een adres,
en in dit geval een pointer of in dit geval als een array van karakters.
>> Karakters, char * s, en arrays zijn hetzelfde.
Pointer is om tekens, en karakter arrays zijn hetzelfde.
En dus, is alles wat we moeten doen passeren in aanwijzer.
We hebben geen geschiedde in zoals * pointer of iets dergelijks.
Dus, arrays en pointers zijn hetzelfde.
Als je iets doet als x [y] hier voor een array,
wat het doet onder de motorkap is het zegt, oke, het is een karakter array,
dus het is een pointer.
En dus x zijn hetzelfde,
en dus wat het doet is het voegt y naar x,
dat is hetzelfde als vooruit in het geheugen dat veel.
En nu x + y geeft ons een soort van adres,
en we dereference het adres of volg de pijl
naar de plaats waar die locatie in het geheugen is en krijgen we de waarde uit die locatie in het geheugen.
Zo, zo deze twee zijn precies hetzelfde.
Het is gewoon een syntactische suiker.
Ze doen hetzelfde. Ze zijn gewoon anders syntactics voor elkaar.
>> Dus, wat kan verkeerd gaan met pointers? Zoals, heel veel. Oke. Dus, slechte dingen.
Sommige slechte dingen die je kunt doen is niet na te gaan of uw malloc oproep null retourneert, toch?
In dit geval, ik vraag het systeem voor mij te geven - wat is dat nummer?
Als 2 miljard keer 4, omdat de grootte van een geheel getal van 4 bytes.
Ik vraag het voor als 8 miljard bytes.
Natuurlijk is mijn computer is niet van plan te zijn in staat om mij dat veel geheugen terug.
En we hadden toch niet controleren of deze nul is, dus als we proberen om dereference het daar -
volg de pijl naar de plaats waar het gaat om - hebben we niet dat het geheugen.
Dit is wat we noemen dereferentie een null pointer.
En dit zorgt ervoor dat in wezen je segfault aan.
Dit is een van de manieren waarop u kunt segfault.
Andere slechte dingen die je kunt doen - oh well.
Dat was dereferentie een null pointer. Oke.
Andere slechte dingen - nou ja, om vast te stellen dat je gewoon een cheque in daar te zetten
die controleert of de aanwijzer null is
en uit te sluiten van het programma als het gebeurt dat malloc geeft een null pointer.
Dat is de xkcd comic. Mensen begrijpen het nu. Soort van.
>> Dus geheugen. En ik ging dit.
We noemen malloc in een lus, maar elke keer als we noemen malloc
we verliezen bij waar deze pointer wijst naar,
omdat we beuken het.
Dus, het eerste contact met malloc geeft me het geheugen hier.
Mijn wijzer verwijzingen naar deze.
Nu, ik het niet vrij, dus nu noem ik malloc weer.
Nu wijst hier. Nu is mijn geheugen wijst hier.
Wijzend hier. Wijzend hier.
Maar ik heb verloren spoor van de adressen van al het geheugen hier dat ik toegewezen.
En dus nu heb ik niet meer om het even welke verwijzing naar hen.
Dus ik kan niet bevrijden buiten deze lus.
En dus om iets als dit op te lossen,
als je vergeet om geheugen vrij te en je krijgt dit geheugenlek,
Je moet de geheugen vrij binnenkant van deze lus als je eenmaal klaar bent met het.
Nou, dit is wat er gebeurt. Ik weet dat velen van jullie een hekel aan.
Maar nu - yay! Je krijgt net als 44.000 kilobytes.
Dus, je bevrijden aan het einde van de lus,
en dat gaat gewoon vrij het geheugen elke keer.
In wezen gaat het programma niet meer een geheugenlek.
>> En nu iets anders dat je kunt doen is geheugen vrij dat u gevraagd twee keer.
In dit geval moet u malloc iets, u die waarde wijzigen.
Je bevrijden het een keer, omdat je zei dat je er klaar mee.
Maar dan moeten we bevrijd het weer.
Dit is iets dat is vrij slecht.
Het gaat niet in eerste instantie segfault,
maar na een tijdje wat dit doet is dubbel bevrijden dit corrumpeert uw hoop structuur,
en je krijgt een beetje meer te leren over dit als je ervoor kiest om een ​​klasse te nemen als CS61.
Maar in wezen na een tijdje de computer gaat in de war raken
over wat geheugen locaties zijn waar en waar het is opgeslagen -
waarin gegevens worden opgeslagen.
En dus het vrijmaken van een pointer twee keer is een slechte zaak dat je niet wilt doen.
>> Andere dingen die fout kunnen gaan is niet met behulp van sizeof.
Dus, in dit geval malloc 8 bytes,
en dat is hetzelfde als twee gehele getallen, toch?
Dus, dat is volkomen veilig, maar is het?
Nou, zoals Lucas het over op verschillende architecturen,
integers zijn van verschillende lengte.
Dus, op het apparaat dat u gebruikt, gehele getallen zijn ongeveer 4 bytes,
maar op een ander systeem ze ook mogen zijn 8 bytes of ze kunnen worden 16 bytes.
Dus, als ik gewoon dit nummer te gebruiken hier,
dit programma zou kunnen werken op het apparaat,
maar het is niet genoeg geheugen op een ander systeem toe te wijzen.
In dit geval is wat de sizeof operator wordt gebruikt.
Wanneer noemen we sizeof (int), wat dit doet is
het geeft ons de grootte van een geheel getal op het systeem dat het programma wordt uitgevoerd.
Dus, in dit geval sizeof (int) terug 4 op zoiets als het apparaat
en nu dit wil 4 * 2, dat is 8,
die net de ruimte nodig voor twee integers.
Op een ander systeem, als een int is als 16 bytes of 8 bytes,
het is gewoon genoeg bytes terug te keren naar dat bedrag op te slaan.
>> En tot slot, structs.
Dus, als je wilde een sudoku bord op te slaan in het geheugen, hoe kunnen we dit doen?
Je zou kunnen denken van als een variabele voor het eerste ding,
een variabele voor de tweede zaak, een variabele voor de derde ding,
een variabele voor de vierde ding - slecht, toch?
Dus, een verbetering kunt u top van deze is om een ​​9 x 9 array.
Dat is prima, maar wat als je wilde om andere dingen te associëren met de sudoku bord
als wat de moeilijkheid van het bord is,
of, bijvoorbeeld, wat uw score is, of hoeveel tijd het is genomen om dit forum op te lossen?
Nou, wat je kunt doen is kunt u een struct.
Wat ik eigenlijk wil zeggen is dat ik deze structuur definiëren hier,
en ik ben het definiëren van een sudoku boord die bestaat uit een raad van bestuur die is 9 x 9.
>> En wat het heeft het heeft verwijzingen naar de naam van het level.
Het heeft ook x en y, die de coördinaten van waar ik nu.
Het heeft ook tijd besteed [onverstaanbaar], en het heeft het totale aantal zetten ik tot nu toe ingevoerd.
En dus in dit geval, kan ik een hele hoop gegevens groeperen in een enkele structuur
in plaats van het hebben van het als vliegen rond in als verschillende variabelen
dat kan ik niet echt bijhouden.
En dit laat ons hebben gewoon leuk syntaxis voor soort verwijzen naar verschillende dingen binnenkant van dit struct.
Ik kan gewoon board.board, en ik krijg de sudoku bord terug.
Board.level, krijg ik hoe moeilijk het is.
Board.x en board.y geef me de coördinaten van waar ik zou kunnen zijn in het bestuur.
En dus ik ben toegang tot wat wij noemen velden in de struct.
Dit definieert sudokuBoard, dat is een soort die ik heb.
En nu zijn we hier. Ik heb een variabele genaamd "board" van het type sudokuBoard.
En dus nu kan ik toegang krijgen tot alle velden die deel uitmaken van deze structuur hier.
>> Heeft u vragen over structs? Ja?
[Student] Voor int x, y, u heeft verklaard zowel op een lijn? >> [Joseph] Uh-huh.
[Student] Dus, zou je dat te doen met elk van hen?
Net als in x, y komma keer dat de totale?
[Joseph] Ja, dat kan zeker doen, maar de reden dat ik x en y op dezelfde lijn -
en de vraag is waarom kunnen we gewoon dit doen op dezelfde lijn?
Waarom gaan we niet zomaar al deze op dezelfde lijn is
x en y zijn gerelateerd aan elkaar
en dit is slechts stilistisch meer correct is, in zekere zin,
omdat het groeperen van twee dingen op dezelfde lijn
dat als soort hebben betrekking op hetzelfde.
En ik splitsen deze uit elkaar. Het is gewoon een stijl ding.
Het maakt functioneel geen enkel verschil.
Alle andere vragen over structs?
U kunt een Pokedex met een struct.
Een Pokemon heeft een nummer en het heeft een brief, een eigenaar, een type.
En dan als je een array van Pokemon, kunt u een Pokedex, toch?
Oke, cool. Dus vragen over structs. Dat zijn gerelateerd aan structs.
>> Tenslotte GDB. Wat doet GDB laten doen? Het laat je debuggen uw programma.
En als je niet hebt gebruikt GDB, zou ik raden het kijken naar de korte
en gewoon gaan over wat GDB is, hoe je er mee werkt, hoe u het te gebruiken,
en test het op een programma.
En dus wat GDB kunt u doen is het laat pauzeren [onverstaanbaar]-up van uw programma
en een praktische lijn.
Bijvoorbeeld, ik wil om te pauzeren uitvoering op als lijn 3 van mijn programma,
en terwijl ik op regel 3 Ik kan uitprinten alle waarden die er zijn.
En dus wat wij noemen als het pauzeren in een lijn
is noemen we dit zetten een breakpoint op die lijn
en dan kunnen we printen de variabelen over de toestand van het programma op dat moment.
>> We kunnen dan van daaruit stap door het programma lijn per lijn.
En dan kunnen we kijken naar de staat van de stack op het moment.
En dus om GDB, wat we doen is dat we clang een beroep doen op de C-bestand te gebruiken,
maar we moeten doorgeven the-ggdb vlag.
En zodra we klaar zijn met dat we gewoon gdb draaien op de resulterende output file.
En zo krijg je een aantal achtige massa van tekst als deze,
maar werkelijk alles wat je hoeft te doen is typen in commando's aan het begin.
Breek belangrijkste zet een breakpoint op de belangrijkste.
Lijst 400 geeft de lijnen van de code rond regel 400.
En dus in dit geval kun je gewoon rondkijken en zeggen: oh,
Ik wil een breekpunt op lijn 397, die deze lijn in te stellen,
en vervolgens uw programma loopt in die stap en het zal breken.
Het gaat om te pauzeren daar, en u kunt afdrukken, bijvoorbeeld, de waarde van lage of hoge.
En zo zijn er een heleboel commando's die je moet weten,
en deze slideshow zal omhoog gaan op de website,
dus als je gewoon wilt dat deze verwijzen of zoals ze op je spiekbriefjes, voel je vrij.
>> Cool. Dat was Quiz Beoordeling 0, en we zullen blijven hangen als u vragen hebt.
Oke.
>> [Applaus]
>> [CS50.TV]