>> DAVID Malan: Oke, welkom terug.
Dit is CS50.
Dit is het begin van week zeven.
Dus het is al een tijdje, dus ik dacht dat we neem een ​​wervelwind tour van waar we
ophield en waar we nu gaan.
>> Dus dit ding hier zou kunnen hebben veroorzaakte enige angst op het eerste.
Maar hopelijk, je begint te wennen aan wat dit geeft hier -
ster die een pointer, die net wat, in termen meer leek?
Dus het is een adres.
>> Dus het is het adres van iets in het geheugen.
En we begonnen te pellen van de lagen een paar weken geleden, dingen zoals
GetString en andere dergelijke functies al die tijd hebben terug te keren
adressen van zaken in het geheugen, zoals de adres van het eerste teken in
sommige volgorde.
>> Zodat we ook geïntroduceerd valgrind, die zult u beginnen om te gebruiken voor dit probleem
stellen, met name voor de volgende probleem te stellen ook.
En valgrind doet wat voor ons?
Het controleert voor het geheugen lekken, en het controleert ook voor misbruik van het geheugen.
>> Het kan, met enige waarschijnlijkheid, detecteren of uw code gaat het geheugen raken
dat het gewoon niet moeten doen.
Dus niet per se een lek, maar als je gaan dan de grenzen van een aantal
array, en je daadwerkelijk gereden valgrind en veroorzaken dat gedrag tijdens
valgrind draait in uw programma is loopt binnenkant van het, krijg je
berichten zoals deze - "ongeldige schrijven van maat 4, "die, roepen een paar
weken geleden betekende dat ik had per ongeluk zoals op een int te ver
buiten de grenzen van een array.
En dus maat 4 betekent hier de grootte van dat int.
>> Dus neem de herverzekering voor het feit dat valgrind de output, het formaat ervan,
is gewoon afschuwelijk.
Het is echt moeilijk te zien door de rommel voor de interessante informatie.
Dus wat we hier hebben gedaan is gewoon fragment enkele paar meer
interessante lijnen.
Maar beseffen dat 80% van de valgrind's uitgang gaat een beetje een te zijn
afleiding.
>> Gewoon zoeken naar patronen als deze - ongeldige recht, ongeldig te lezen, 40 bytes
en sommige aantal blokken zijn zeker verloren, trefwoorden als dat.
En wat u zult hopelijk zien is wat soort spoor van welke functie de
fout is eigenlijk inch
In dit geval hier, in welke regel van mijn code was de fout blijkbaar?
>> 26 in een bestand genaamd memory.c, dat was het voorbeeld dat we aan het spelen waren met
op dat moment.
Dus het is waarschijnlijk niet in malloc.
Het was waarschijnlijk in mijn code plaats.
Dus zullen we dit opnieuw zien en opnieuw vóór lang.
>> Dus scanf, dit kwam in een paar vormen tot nu toe.
We zagen sscanf kort.
Het was iets wat een aantal je dook in uw
voorbereidingen voor de quiz.
En scanf is eigenlijk wat de CS50 bibliotheek is al met behulp van onder de
hood al geruime tijd in orde om invoer van de gebruiker.
>> Bijvoorbeeld, als ik dan naar de CS50 apparaat hier, laat me open te stellen een
bijvoorbeeld vandaag dat scanf-0.c heet En het is super simpel.
Het is slechts een paar regels code.
Maar het toont echt hoe getInt heeft gewerkt al die tijd.
>> Hier in dit programma, in lijn 16 , Mede dat ik verklaar een int.
Dus geen pointers, niets magisch daar, gewoon een int.
Vervolgens in lijn 17, ik prompt de gebruiker voor een nummer, alstublieft.
Toen in de late 18, gebruik ik scanf hier.
En ik heb opgegeven, net zoiets als printf, dat verwacht ik citeer
unquote procent i.
>> Dus percent i natuurlijk geeft een int.
Maar let op wat de tweede argument om scanf is.
Hoe zou je de tweede beschrijven argument na de komma?
Wat is dat?
>> Het is het adres van x.
Dit is zo nuttig omdat door het verstrekken scanf met het adres van x, wat doet
dat die functie in staat stellen om te doen?
Niet alleen gaan er, maar ook wat doen?
>> Maak een wijziging van het.
Want je kunt er naartoe, het is een soort van als een kaart om een ​​locatie in het geheugen.
En zolang u scanf, of een functie met een dergelijke kaart, die
functie kunnen er terecht, en niet alleen kijken naar de waarde, maar het kan ook
verandering die waarde, die handig als is het doel in het leven van scanf is om
scan input van de gebruiker, in het bijzonder het toetsenbord.
En de f geeft opgemaakte, net als printf, de f staat voor een geformatteerde
snaar die u wilt afdrukken.
>> Dus in het kort, deze lijn 18 zegt eenvoudig, proberen om een ​​int van de gebruiker lezen
toetsenbord en slaan binnenkant van x op welk adres x toevallig wonen.
En dan tot slot, lijn 19 net zegt, bedankt voor de int, in dit geval.
>> Dus laat me ga je gang en maken dit.
Dus zorg scanf 0.
Laat me ga je gang en vergroten
Ik ga lopen dit met stippen slash scanf 0.
Nummer, alstublieft?
50.
Bedankt voor de 50.
Dus het is heel simpel.
>> Nu, wat is het niet te doen?
Het is niet te doen een hele hoop van foutcontrole.
Bijvoorbeeld, als ik niet meewerken, en ik denk niet typen in een getal, maar
plaats ik iets als "hello", schrijven dat is gewoon een beetje vreemd.
En dus een van de dingen die de CS50 bibliotheek heeft gedaan voor ons voor enige
tijd is dat reprompting en reprompting.
>> De retry zinsnede recall was in cs50.c, en dat is de reden dat getInt in
de CS50 bibliotheek is eigenlijk een hele stelletje regels lang, omdat we
het controleren op stomme dingen zoals dit.
Heeft de gebruiker niet geven ons, in feite, een int?
Heeft hij of zij iets geven ons als een alfabetische letter?
Als dat zo is, willen we op te sporen die en schreeuwen tegen hen.
>> Maar dingen interessanter in het volgende voorbeeld.
Als ik naar scanf-1.c, wat is het een wat fundamenteel veranderd
het volgende voorbeeld?
Ik gebruik char *, natuurlijk, in plaats van int.
>> Dit is zo interessant, omdat char *, herinneren, is eigenlijk alleen maar de
Hetzelfde als string.
Dus het voelt alsof misschien is dit een super eenvoudige implementatie van GetString.
Maar ik heb de laag geschild terug van de CS50 bibliotheek, dus ik ben
roepen deze char * nu.
Dus laten we zien waar, indien ergens, we gaan mis.
>> Line 17 -
Ik zeg nogmaals, geef me iets, in dit geval, een string.
En dan in de volgende regel, roep ik scanf, weer, waardoor het een formaat code,
maar deze keer procent s.
En dan deze keer, ben ik waardoor het buffer.
>> Let nu op, ik ben niet met behulp van de ampersand.
Maar waarom is hier dat waarschijnlijk OK?
Want wat is buffer al?
Het is al een pointer.
Het is al een adres.
>> En laten we dit woord "verwarren," laat me noem het s, bijvoorbeeld voor
eenvoud.
Maar ik heb wel het bufferen omdat in algemeen, in de programmering, als u een
stuk van het geheugen, die een string echt gewoon is, zou je het noemen een buffer.
Het is een plek om informatie op te slaan.
>> Vergelijkbaar met zaken als YouTube, wanneer ze bufferen, zo te zeggen, dat
betekent gewoon dat het is gedownload bits van het internet en ze op te slaan in een
lokale array, een lokale brok van geheugen, zodat dat je het later kunt kijken zonder
het overslaan of opknoping op u tijdens het afspelen.
>> Dus er is een probleem hier wel, want ik zeg scanf, verwachten een
koord van de gebruiker.
Hier is het adres van de een stuk van het geheugen.
Zet er die string.
Waarom is dat gebonden te geven ons probleem, hoewel?
>> Wat is dat?
Mag ik toegang dat deel van het geheugen?
Weet je, ik weet het niet.
Omdat er buffer geïnitialiseerd naar iets?
Niet echt.
En dus is het wat we hebben te bellen een vuilnisbak waarde, die
is geen formeel woord.
Het betekent alleen dat we geen idee hebben wat stukjes zijn in de vier bytes die
Ik heb toegewezen als buffer.
>> Ik heb niet geroepen malloc.
Ik heb absoluut niet geroepen GetString.
Dus wie weet wat is eigenlijk binnenkant van buffer?
En toch vertellen scanf blind, gaan er en zetten wat de gebruiker heeft ingevoerd.
>> Dus wat zou kunnen leiden tot in onze code als we lopen het?
Waarschijnlijk een segfault.
Misschien niet, maar waarschijnlijk een segfault.
En ik zeg misschien niet want soms je doet, soms
je krijgt niet een segfault.
Soms heb je gewoon geluk, maar het is niettemin gaat worden
een bug in ons programma.
>> Dus laat me ga je gang, en slaat deze.
Ik ga het de oude school manier te doen.
Dus clang dash 0, scanf-1, scanf-1.c, Enter.
Oeps, te oud school.
Laten we eens kijken.
Waar ging ik heen?
Oh, char * buffer.
Oh, dank je wel -
Opslaan, OK -
zeer oude school.
Oke, het is al een tijdje.
>> Dus ik heb net het bestand na opgeslagen maken van die tijdelijke
veranderen een moment geleden.
En nu heb ik het gecompileerd handmatig met Clang.
En nu ga ik om verder te gaan en run scanf-1, Enter.
String alsjeblieft.
Ik type in "hello."
>> En nu, hier is waar, eerlijk gezegd, printf kan is een beetje vervelend.
Het is niet daadwerkelijk gaat segfault in dit geval.
Printf is een beetje speciaal, omdat het is zo super vaak gebruikt dat
wezen printf doet ons een plezier en realiseren,
dat is geen geldige pointer.
Laat ik neem het op me om gewoon af te drukken buiten haakjes null, zelfs
maar het is niet per se wat we ons verwacht.
>> Dus we kunnen niet echt gemakkelijk leiden tot een segfault met deze, maar het is duidelijk dit
is niet het gedrag dat ik wilde.
Dus wat is de eenvoudige oplossing?
Nou, in scanf-2, laat me voorstellen dat in plaats van eigenlijk alleen toewijzing van een
char *, laat me een beetje slimmer over Dit, en laat me buffer toewijzen
als een opeenvolging van 16 tekens.
>> Dus kan ik dit doen in een paar manieren.
Ik zou absoluut gebruik malloc.
Maar ik kan terug naar week twee bij Ik heb gewoon een hele hoop nodig
tekens.
Dat is gewoon een array.
Dus laat mij in plaats herdefiniëren buffer om een ​​array van 16 tekens zijn.
>> En nu, toen ik pas buffer in -
en dit is iets wat we niet praten over in week twee -
maar je kunt een array als behandelen al is het een adres.
Technisch gezien, zoals we hebben gezien, zijn ze een beetje anders.
Maar scanf zal het niet erg als je het door te geven de naam van een array, want wat
Clang te doen voor ons is in wezen de behandeling van de naam van die array als de
adres van de brok van 16 bytes.
>> Dus dit is beter.
Dit betekent nu dat ik kan hopelijk doet u het volgende.
Laat me uit te zoomen voor een moment en doe make scanf-2, OK samengesteld.
Nu laat ik heb gekregen slash scanf-2.
String alsjeblieft. "Hallo." En leek deze keer het werk.
>> Maar kan iemand een scenario voor te stellen waar het misschien niet nog steeds werken?
Yeah?
Iets langer dan 16 tekens.
En eigenlijk kunnen we er een beetje nauwkeuriger.
Iets langer dan 15 tekens, want echt moeten we in gedachten houden
dat we moeten dat backslash nul impliciet aan het eind van de tekenreeks
dat is een terzijde scanf zal doorgaans verzorgen voor ons.
>> Dus laat ik zoiets doe -
Soms kunnen we gewoon laat het zo.
OK, dus we hebben nu geïnduceerde onze segmentation fault.
Waarom?
Want ik typte om meer dan 15 personages, en dus we hebben eigenlijk
aangeraakt geheugen dat ik eigenlijk mag niet.
>> Dus wat is eigenlijk de oplossing hier?
Nou, wat als we een langere snaar nodig?
Nou ja, misschien maken we het 32 ​​bytes.
Nou, wat als dat niet lang genoeg?
Hoe zit het met 64 bytes?
Wat als dat niet lang genoeg?
Hoe zit het met 128 of 200 bytes?
Wat is eigenlijk de oplossing hier in het algemene geval, als we niet weten in
vooruit wat de gebruiker gaat typen?
>> Het is gewoon een soort van een grote pijn in de kont, om eerlijk te zijn, dat is de reden waarom de
CS50 bibliotheek heeft enkele tientallen regels code die gezamenlijk implementeren
GetString snaar op een manier die wij niet moeten weten van tevoren wat de
gebruiker gaat typen.
In het bijzonder, als je terugkijkt op cs50.c van twee weken geleden, zie je
dat GetString eigenlijk doet Gebruik scanf op deze manier.
Integendeel, leest een teken tegelijk.
>> Omdat het een leuke het lezen van een teken is dat we kunnen
garanderen onszelf altijd ten minste een char.
Ik kan gewoon een char te verklaren, en neem dan deze echt kleine stapjes om gewoon
lees een teken in op een tijd vanaf het toetsenbord.
En dan, wat je ziet GetString doet is elke keer het loopt uit,
zeggen 16 bytes geheugen, gebruikt malloc, of een neef daarvan, te
toewijzen meer geheugen, het kopiëren van de oude geheugen in de nieuwe, en dan kruipen
langs, het krijgen van een teken tegelijk, en wanneer het loopt uit dat
stuk van het geheugen, gooit het weg, grijpers een groter stuk van het geheugen, kopieert oud
in nieuwe en herhalingen.
En het is echt een pijn om daadwerkelijk iets eenvoudigs als het implementeren
krijgt input van een gebruiker.
>> Dus je kunt scanf gebruiken.
U kunt gebruik maken van andere vergelijkbare functies.
En veel van studieboeken en online voorbeelden te doen, maar ze zijn allemaal
kwetsbaar voor dit soort problemen.
En uiteindelijk, het krijgen van een segfault is soort vervelend.
Het is niet goed voor de gebruiker.
>> Maar in het ergste geval, wat doet het fundamenteel uw zetten
code risico op?
Een soort aanval, mogelijk.
We spraken over een dergelijke aanval - overlopen de stack.
Maar in het algemeen, als je mag overflow een buffer, zoals wij deden een
paar weken geleden, met alleen het schrijven meer dan "hallo" op de stapel, je
kan inderdaad overnemen, potentieel, een computer, of op zijn minst te krijgen op gegevens die
hoort niet bij jou.
>> Dus in het kort, dit is waarom we hebben die zijwieltjes.
Maar nu, beginnen we ze af, als onze programma's niet meer nodig,
se, input van de gebruiker.
Maar in het geval van problemen stellen zes, Uw inbreng zal komen uit een enorme
woordenboek bestand met 150 enkele oneven duizend woorden.
>> Zodat u geen zorgen te maken over willekeurige invoer van de gebruiker.
Wij geven u een aantal veronderstellingen te geven over dat bestand.
Voor vragen over pointers of scanf of invoer van de gebruiker in het algemeen?
>> Oke, dus een snelle blik toen op een trailing onderwerp van twee weken geleden.
En dat was het idee van een structuur.
Niet dat - dit begrip een struct, die was wat?
Wat deed struct voor ons doen?
>> Definieer -
spijt?
Definieer een variabele soort.
Dus soort van.
We zijn eigenlijk een combinatie van twee onderwerpen.
Dus met typedef, herinneren dat we kunnen verklaren een soort van onze eigen, als een
synoniem, net string voor char *.
Maar met behulp van typedef en struct, we kunnen maak echt onze eigen datastructuren.
>> Bijvoorbeeld, als ik terug in gedit hier voor slechts een moment, en ik ga je gang
en doe iets als, laat me sparen dit als, laten we zeggen, structs.c
tijdelijk, ik ga gewoon om verder te gaan en omvatten
standardio.h, int main leegte.
En dan hier, stel dat ik wil om een ​​programma dat opslaat schrijven
meerdere studenten van meerdere huizen, bijvoorbeeld.
Dus het is als een registrarial database van een soort.
>> Dus als ik de naam een ​​student, ik misschien iets doen als char * naam,
en ik zal iets doen als -
eigenlijk, laten we gebruik maken van de CS50 bibliotheek voor slechts een moment om dit een te maken
iets eenvoudiger, zodat we kunnen lenen die tientallen regels code.
En laten we het simpel houden.
We houden het koord, en nu getString.
>> Dus ik beweren nu dat ik de naam heb opgeslagen van een aantal studenten, en het huis van
enkele student, gewoon met behulp van variabelen zoals wij deden en in week een.
Maar stel dat ik nu wil steunen meerdere studenten.
Oke, dus mijn instincten te doen snaar name2, krijgt GetString, touwtje
house2 krijgt GetString.
En dan is onze derde student, laten we name3 GetString.
>> Oke, dus dit is hopelijk opvallende u als een soort van domme,
omdat dit proces is eigenlijk nooit gaat eindigen, en het zal alleen maar
maak mijn code er slechter uitzien en erger en erger.
Maar we loste ook dit in week twee.
Wat was onze relatief schone oplossing toen hadden we meerdere variabelen van de
hetzelfde gegevenstype die allemaal gerelateerd zijn, maar we niet willen dat deze gruwelijke puinhoop
van de gelijknamige variabelen?
Wat hebben we in plaats daarvan doen?
>> Dus ik denk dat ik hoorde een paar plaatsen.
We hadden een array.
Als u wilt meerdere exemplaren van iets, waarom doen we dit allemaal schoon
up en gewoon zeggen, geef mij array met de naam namen?
>> En voor nu, laten we harde code 3.
En geef me dan een andere array riep huizen, en laat mij voor
nu harde code 3.
En ik heb massaal opgeruimd de rotzooi die ik net gemaakt.
Nu, ik heb nog steeds hard gecodeerd 3, maar zelfs de 3 kan dynamisch uit de
gebruiker, of argv, of dergelijke.
Dus dit is nu al schoner.
>> Maar wat is vervelend over dit is dat Nu, zelfs al een naam is een of andere manier
fundamenteel verbonden een student house -
het is een student die ik echt willen vertegenwoordigen -
Ik heb nu twee arrays die parallel zijn in de zin dat ze de
dezelfde grootte, en namen beugel 0 vermoedelijk kaarten om huizen beugel 0,
en namen beugel 1 kaarten om huizen beugel 1.
Met andere woorden, student woont dat huis, en dat de andere student
woont in dat andere huis.
Maar zeker dit kan worden gedaan, zelfs schoner.
>> Nou, het kan, in feite.
En laat mij ga je gang en open up structs.h, en je zult
zie hier dit idee.
Merk op dat ik typedef heb gebruikt, zoals u gezinspeeld op een moment geleden te verklaren onze
eigen gegevens type.
Maar ik ben ook met behulp van deze andere trefwoord riep struct die me een nieuwe geeft
gegevensstructuur.
>> En deze datastructuur Ik eis gaat twee dingen binnenin
het - een string genaamd naam, en een string genaamd huis.
En de naam die ik ga geven aan Deze gegevensstructuur gaat
te noemen student.
Ik kon het noemen wat ik wil, maar dit semantisch maken
zin om mij in mijn gedachten.
>> Dus nu, als ik open een betere versie van het programma dat ik begon te schrijven
daar, laat mij gaat u naar de top.
En er is nog meer regels code hier, maar laat me richten voor
het ene moment.
Ik heb een constante genaamd studenten verklaard en hard gecodeerd 3 voor nu.
Maar nu, merken hoe schoon mijn code begint te krijgen.
>> In lijn 22, verklaar ik serie van studenten.
En merken dat student is blijkbaar nu een data type.
Omdat op de top van dit bestand, merkt Ik heb begrepen dat de header file
dat Ik trok slechts een moment geleden.
En die header file gewoon had Deze definitie van een student.
>> Dus nu heb ik mijn eigen aangepaste data gecreëerd type dat de auteurs van C jaar
geleden dacht niet dat van te voren.
Maar geen probleem.
Ik kan het zelf maken.
Dus dit is een matrix genoemd studenten, elk waarvan de leden
is een student structuur.
En ik wil drie van die in de array.
>> En nu, wat doet de rest van dit programma doen?
Ik iets een beetje arbitrair nodig.
Dus van online 24 verder, Ik itereren van 0 tot 3.
Toen ik de gebruiker te vragen de naam van de student.
En dan gebruik ik getString als voorheen.
Dan vraag ik voor het huis van de student, en ik getString als voorheen.
>> Maar merk - iets nieuw stuk van de syntax -
Ik kan nog steeds index aan de i-de student, maar hoe kom ik aan de specifieke data
veld binnen de struct?
Nou, wat is blijkbaar de nieuw stuk van syntax?
Het is gewoon de puntoperator.
>> We hebben niet echt eerder gezien.
Je hebt het gezien in pset vijf als je hebt gedoken in reeds met bitmap-bestanden.
Maar de stip betekent gewoon binnenkant van deze struct of meerdere velden, geven dot
naam, of geef me dot huis.
Dat betekent naar binnen gaan van de struct en krijgen die bepaalde gebieden.
>> Wat doet de rest van dit programma doen?
Het is niet zo sexy.
Merk op dat ik weer herhalen van 0 tot 3, en ik gewoon maak een Engels
frase als zo en zo is in dergelijke en zo'n huis, passeren in dot naam uit
de i-de hun studenten en huis ook.
>> En dan tot slot, nu we beginnen te krijgen anal over dit, nu we
vertrouwd zijn met wat malloc en andere functies zijn
doen al die tijd.
Waarom moet ik zowel naam bevrijden en het huis, hoewel ik
heb malloc niet bellen?
>> GetString deed.
En dat de dirty little secret voor was een aantal weken, maar GetString heeft
gelekt geheugen over de hele plaats alle semester tot nu toe.
En Valgrand zal uiteindelijk openbaren aan ons.
>> Maar het is geen big deal, want ik weet dat ik gewoon kan bevrijden van de naam
en het huis, hoewel technisch gezien, om super, super veilig, zou ik
doen wat foutcontrole hier.
Wat zijn uw instincten vertellen?
Wat moet ik controleren voordat ik vrij wat is een
koord, alias die een char *?
>> Ik moet echt worden gecontroleerd of studenten beugel i dot naam niet
gelijk nul.
Dan is het wel OK zijn om vooruit en gratis gaan dat pointer, en dezelfde of andere
een als goed.
Als studenten beugel i dot huis is niet gelijk aan nul, dit nu zal beschermen
tegen de hoek geval waarin GetString keert iets als null.
En we zagen een moment geleden, printf zal bescherm ons hier door gewoon te zeggen
null, die zal raar kijken.
Maar in ieder geval zal het niet segfault, zoals we hebben gezien.
>> Nou, laat mij een ding hier. structs-0 is een beetje een domme programma
want ik voer al deze gegevens, en vervolgens het is verloren wanneer het programma eindigt.
Maar laat me ga je gang en doe dit.
Laat ik de terminal raam een ​​beetje groter.
Laat me structs-1, die een nieuwe versie van.
>> Ik zal inzoomen een beetje.
En nu laat ik dot draaien slash structs-1.
Naam van de student -
David Mather, laten we het doen Rob Kirkland, laten we Lauren Leverett.
Wat interessant is, is nu bericht -
en ik weet alleen dit omdat Ik schreef het programma -
er is een bestand nu op mijn huidige directory genaamd students.csv.
Sommigen van u zou kunnen hebben gezien deze in de echte wereld.
>> Wat is een CSV-bestand?
Comma-separated values.
Het is een soort als een arme man versie van een Excel-bestand.
Het is een tafel van rijen en kolommen die u kunt openen in een programma zoals Excel,
of Numbers op een Mac.
>> En als ik dit bestand hier openen op gedit, kennisgeving - en de getallen zijn er niet.
Dat is gewoon gedit vertellen me regelnummers.
Merkt op de eerste regel van dit bestand is David en Mather.
De volgende regel is Rob komma Kirkland.
En de derde lijn is Lauren komma Leverett.
>> Dus wat heb ik gemaakt?
Ik heb nu een C-programma geschreven dat effectief kunnen spreadsheets genereren
die kan worden geopend in een programma zoals Excel.
Niet al die dwingende een data set, maar als je veel grotere brokken van
gegevens die u daadwerkelijk wilt manipuleren en maak grafieken van en de
willen, is dit misschien wel een manier om die gegevens te maken.
Bovendien CSV zijn eigenlijk super gemeenschappelijke net voor het opslaan van eenvoudige data -
Yahoo Finance, bijvoorbeeld, als je aandelenkoersen via hun zogenaamde
API, de gratis service waarmee je krijg huidige up-to-the-date voorraad
offertes voor bedrijven, ze de data terug te geven in de
super eenvoudige CSV-formaat.
>> Dus hoe hebben we dat gedaan?
Wel merken, de meeste van deze programma's bijna hetzelfde.
Maar let hier beneden, in plaats van druk de studenten uit, on line 35
verder, ik beweer dat ik ben aan het sparen de studenten naar de schijf, dus een bestand op te slaan.
>> Dus zie ik ben waarbij een FILE * -
Nu, dit is een soort van een anomalie in C. Om wat voor reden, BESTAND hoofdletters,
dat is niet zoals de meeste andere soorten gegevens in C. Maar dit is een ingebouwde
datatype, FILE *.
En ik ben waarbij een pointer naar een bestand, is hoe je kunt bedenken dat.
>> fopen betekent geopend bestand.
Wat bestand wilt u openen?
Ik wil een bestand te openen dat zal ik doen willekeurig noemen students.csv.
Ik kon dat alles wat ik wil noemen.
>> En neem dan een gok.
Wat doet het tweede argument om fopen waarschijnlijk betekenen?
Rechts, w voor schrijven, kon worden r voor lezen.
Er is een voor append als u willen rijen en niet toe te voegen
overschrijven van de hele zaak.
>> Maar ik wil gewoon dit bestand te maken een keer, dus ik citeer unquote w gebruiken.
En ik weet dat alleen van te hebben gelezen de documentatie of de man pagina.
Als het bestand niet null is - met andere woorden, als er niets mis ging er -
laat me itereren over de studenten van 0 tot 3.
>> En nu merkt dat er iets ooit zo iets anders
over lijn 41 hier.
Het is niet printf.
Het is fprintf voor bestand printf.
Dus het gaat om schrijven naar bestand.
Welk bestand?
Degene wiens aanwijzer die u opgeeft als eerste argument.
>> Dan geven wij een format string.
Dan geven wij wat snaar we willen plug in voor de eerste procent s, en
dan nog een variabele of de tweede procent s.
Sluit we het bestand met fclose.
Dan ik vrij het geheugen als voorheen, alsof Ik zou terug gaan in en voeg
sommige controles voor null.
>> En dat is het.
fopen, fprintf, fclose geeft mij de mogelijkheid om tekstbestanden te maken.
Nu, zie je in de problemen set vijf, welke beelden gaat, zult u met behulp van
binaire bestanden in plaats.
Maar fundamenteel, het idee is hetzelfde, hoewel de functies die u zult
zien zijn een beetje anders.
>> Dus wervelwind tour, maar je krijgt maar al te bekend met file I/O--
input en output - met pset vijf.
En vragen over de initiële basics hier?
Yeah?
>> Wat als je probeert om een ​​null-waarde te bevrijden?
Ik geloof, tenzij gratis heeft gekregen een beetje meer gebruikersvriendelijk, kunt u
potentieel segfault.
Het doorgeven null is slecht omdat ik niet geloof vrij stoort om te controleren voor u,
omdat het mogelijk zou zijn een verspilling tijd om zich ervan te doen
iedereen in de wereld.
Goede vraag, dat wel.
>> Oke, dus dit soort krijgt ons naar een interessant onderwerp.
Het thema van het probleem set vijf is forensisch onderzoek.
Dat is tenminste een gedeelte van de probleemstelling.
Forensics algemeen verwijst naar de herstel van de informatie die al dan
mogen niet zijn verwijderd bewust.
En dus ik dacht dat ik je een korte voorproefje van wat er echt gaande is alle
ditmaal onder het motorkap van uw computer.
>> Bijvoorbeeld, als je de binnenkant van je laptop of desktop computer een
harde schijf, het is ofwel een mechanisch apparaat dat eigenlijk spint -
er is circulaire dingen genoemd platters dat nogal uitzien als wat ik
net op het scherm hier, hoewel Dit is steeds old school.
Dit is een drie-en-een-half-inch harde schijf.
En drie en een halve centimeter verwijst van met het ding als je het installeert
in een computer.
>> Velen van jullie nu in uw laptops hebben solid-state drives, of SSD's,
tegenkomen die geen bewegende delen.
Ze zijn meer zoals RAM en minder als deze mechanische inrichtingen.
Maar de ideeën zijn nog steeds hetzelfde, beslist zij betrekking
om probleem stellen vijf.
>> En als je erover nadenkt nu een harde schijf vertegenwoordigt zijnde een cirkel, die
Ik zal hier tekenen als deze.
Wanneer u een bestand op uw computer te maken, of het nu een SSD, of in
dit geval een oudere school-harde schijf, dat bestand bestaat uit meerdere bits.
Laten we zeggen dat het is dit 0 en 1, een hele hoop van 0s en 1s.
Dit is dus mijn hele harde schijf.
Dit is blijkbaar een vrij groot bestand.
En het is met behulp van de 0s en 1s op dat deel van de fysieke platter.
>> Nou, wat is dat fysieke gedeelte?
Nou, het blijkt dat op een harde schijf, althans van dit type is er
deze minuscule kleine magnetische deeltjes.
En ze wezen moeten noorden en zuidpool aan hen, zodat als je
draai een van die magnetische deeltjes op deze manier, zou je kunnen zeggen dat het
die een 1.
En als het ondersteboven zuiden naar noorden, zou je kunnen zeggen dat het
wat neerkomt op een 0.
>> Dus in de echte fysieke wereld, dat is hoe je iets in zou kunnen vertegenwoordigen
binaire toestand van de 0 en een 1.
Dus dat is al een bestand is.
Er is een hele hoop van magnetische deeltjes dat hun op deze manier of zijn
op deze manier, het creëren van patronen van 0s en 1s.
>> Maar het blijkt dat wanneer u een bestand opslaat, wat informatie wordt apart opgeslagen.
Dus dit is een kleine tafel, een directory, zo te zeggen.
En ik zal deze kolom naam noemen, en Ik zal deze kolom te bellen.
>> En ik ga zeggen, veronderstel dit is mijn CV.
Mijn RESUME.DOC wordt opgeslagen bij locatie, laten we zeggen 123.
Ik kies altijd voor dat nummer.
Maar het volstaat te zeggen dat, net als in het RAM, kunt u een harde schijf te nemen
dat is een gigabyte of 200 gigabytes of een terabyte, en je kan
nummer al van de bytes.
U zal kunnen tellen alle stukjes van 8 bits.
>> Dus we zullen zeggen dat dit is locatie 123.
Dus deze directory binnenkant van mijn besturingssysteem systeem onthoudt dat mijn
CV is op locatie 123.
Maar het wordt interessant wanneer je een bestand verwijdert.
>> Dus bijvoorbeeld -
en gelukkig, het grootste deel van de wereld heeft gevangen op dit - wat er gebeurt als
u een bestand sleept naar uw Mac OS Prullenbak of uw Windows Prullenbak?
Wat is het doel van dat te doen?
Het is natuurlijk om zich te ontdoen van het bestand, maar wat doet de handeling van het slepen en
te laten vallen in uw prullenbak of uw Prullenbak doen op een computer?
>> Absoluut niets, echt.
Het is net als een map.
Het is een speciale map, om zeker te zijn.
Maar is het eigenlijk het bestand te verwijderen?
>> Nou, nee, want sommigen van u waarschijnlijk hebben zoals geweest, oh damn, dat deed je niet
betekenen om dat te doen.
Zodat u dubbelklikt op het Prullenmand.
Je hebt gepord rond en je hebt hersteld het bestand gewoon door het te slepen
er uit.
Zo duidelijk, het is niet per se verwijderen.
>> OK, je bent slimmer dan dat.
U weet dat het juist in het slepen Prullenbak of Prullenbak betekent niet
je bent het legen van de prullenbak.
Dus ga je naar het menu, en je zegt Prullenbak leegmaken of Prullenbak leegmaken.
Wat gebeurt er dan?
>> Ja, dus het is meer zo verwijderd.
Maar alles wat er gebeurt is het volgende.
De computer vergeet waar RESUME.DOC was.
>> Maar wat is er blijkbaar niet veranderd op de foto?
De bits, de 0s en 1s dat ik beweren zijn op het terrein van een aantal fysieke aspect van
de hardware.
Ze zijn er nog steeds.
Het is gewoon de computer heeft vergeten wat ze zijn.
>> Dus het is in wezen bevrijd van het bestand stukjes zodat zij kunnen worden hergebruikt.
Maar niet totdat je meer bestanden maken, en meer bestanden en meer bestanden zullen
probabilistisch, die 0s en 1s, die magnetische deeltjes, word hergebruikt,
ondersteboven of rechtop, voor andere bestanden, 0s en 1s.
>> Dus je hebt dit venster van de tijd.
En het is niet van voorspelbare lengte, echt.
Het hangt af van de grootte van uw harde rijden en hoeveel bestanden je hebt en
hoe snel je nieuwe te maken.
Maar er is een venster van de tijd tijdens die dat bestand is nog steeds perfect
vergoeding in aanmerking.
>> Dus als je ooit gebruik maken programma's als McAfee of Norton om te proberen te herstellen
gegevens, alles wat ze doen is proberen om herstellen van deze zogenaamde directory te
erachter te komen waar uw bestand was.
En soms Norton en zal zeggen, bestand is 93% herbruikbaar.
Nou, wat betekent dat?
Dat betekent gewoon dat een ander bestand toevallig belandde met, zeg,
die stukjes uit je oorspronkelijke bestand.
>> Dus wat er werkelijk betrokken in het herstellen van gegevens?
Nou, als je niet zoiets hebben Norton vooraf geïnstalleerd op uw computer,
het beste wat je kunt soms doen is kijken op de hele harde schijf op zoek naar
patronen van bits.
En een van de thema's van het probleem set vijf is dat je zal zoeken de
equivalent van een harde schijf, een forensisch beeld van een compact flash kaart van een
digitale camera, op zoek naar de 0s en 1s die typisch met hoge
waarschijnlijkheid, vertegenwoordigen begin een JPEG-beeld.
>> En jullie kunnen herstellen die beelden door veronderstelling, als ik zie dit patroon van
bits op de forensische afbeelding, met hoge waarschijnlijkheid, dat markeert
de start van een JPEG.
En als ik zie hetzelfde patroon weer, dat waarschijnlijk markeert het begin van
andere JPEG en andere JPEG en andere JPEG.
En dit is typisch hoe data recovery zal werken.
Wat is er leuk aan JPEG's is ook al het bestandsformaat zelf enigszins
complex, het begin van elk zodanig bestand is eigenlijk vrij herkenbaar
en eenvoudig, zoals u zult zien, Als je hebt nog niet.
>> Dus laten we eens een kijkje eronder de afzuigkap aan wat is geweest
gaande is, en wat deze 0s en 1s zijn, om u een beetje meer van een te geven
context voor deze uitdaging.
>> [VIDEO AFSPELEN]
>> -Waar je PC meeste slaat van haar vaste data.
Om dat te doen, de gegevens reist van RAM samen met software signalen die vertellen
de harde schijf hoe die gegevens op te slaan.
De harde schijf circuits vertalen deze signalen in elektrische spanning
schommelingen.
Deze op zijn beurt, de controle van de harde schijf bewegende delen, enkele weinig
bewegende delen links in de moderne computer.
>> Sommige besturingssignalen een motor welk metaal-gecoate platters spint.
Uw data wordt daadwerkelijk opgeslagen op deze schotels.
Andere signalen bewegen het lezen / schrijven koppen te lezen of
schrijven van gegevens op de platters.
Deze machines zo nauwkeurig dat een mens haar kon zelfs niet passeren tussen de
hoofden en spinnen platters.
Maar toch, het werkt allemaal op geweldige snelheden.
>> [END VIDEO AFSPELEN]
>> DAVID Malan: Zoom in een klein dieper nu naar wat
daadwerkelijk op die platters.
>> [VIDEO AFSPELEN]
>> -Laten we eens kijken naar wat we net zag in slow motion.
Bij een korte puls van elektriciteit is aan de lees / schrijfkop, indien flips
op een kleine elektromagnetische voor een fractie van een seconde.
De magneet zorgt voor een gebied, dat verandert de polariteit van een klein, klein
gedeelte van de metaaldeeltjes die coat elke platter oppervlak.
>> Een patroon reeks van deze kleine, gebracht-up gebieden op de schijf
betekent een bit van gegevens in het binaire getal
dat door computers.
Nu, wanneer de stroom wordt gestuurd op een manier door de lees / schrijfkop, de stippellijn
is gepolariseerd in een richting.
Als de stroom wordt verzonden in de tegenovergestelde richting, de
polarisatie omgekeerd.
>> Hoe u gegevens van de harde schijf te krijgen?
Gewoon het proces omkeren.
Dus het is de deeltjes op de schijf dat de huidige te krijgen in de
lees / schrijfkop beweegt.
Zet samen miljoenen van deze gemagnetiseerd segmenten en
je hebt een bestand.
>> Nu, de stukjes van een bestand kan worden verspreid over een schijf
schotels, zoiets als de puinhoop papieren op uw bureau.
Dus een speciale extra bestand houdt de sporen van waar alles is.
Heb je niet willen dat je had zoiets?
>> [END VIDEO AFSPELEN]
>> DAVID MALAN: OK, waarschijnlijk niet.
Dus hoeveel van jullie opgegroeid met deze?
OK, dus het is minder en minder handen ieder jaar.
Maar ik ben blij dat je op zijn minst vertrouwd met hen, omdat deze en onze eigen
boek demo, helaas, sterven een zeer langzame dood hier van vertrouwdheid.
>> Maar dit is wat ik althans weer middelbare school, gebruikt gebruik voor back-ups.
En het was geweldig, want je 1.4 megabytes kunnen opslaan op
dit disk.
Dit was de hoge dichtheid versie zoals aangegeven door de HD, dat is
wat betekent dat voor de huidige HD-video's.
>> Standaard dichtheid was 800 kilobytes.
En daarvoor waren er 400-kilobyte schijven.
En daarvoor, waren er 5 en 1/4 inch schijven, die echt slap waren,
en een beetje breder en hoger dan deze dingen hier.
Maar je kunt eigenlijk zien de zogenaamde floppy aspect van deze schijven.
>> En functioneel, ze zijn eigenlijk redelijk vergelijkbaar met harde schijven van ten
tenminste dit type.
Nogmaals, SSD's in nieuwere computers werkt een beetje anders.
Maar als je dat tabblad kleine metalen bewegen, je daadwerkelijk kunt zien een beetje koekje,
of schotel.
>> Het is niet metal zoals deze.
Deze is eigenlijk een goedkoper kunststof.
En je kan soort wiebelen het.
En je hebt trully net geveegd enkele aantal bits of magnetische deeltjes
van deze schijf.
>> Zo gelukkig, er is niets op.
Als dat ding in de weg - en bedek uw ogen en die van uw buurman -
je kunt gewoon een soort van trekken deze hele omhulsel eraf als dat.
Maar er is een beetje lente, dus wees bewust van dat met je ogen.
Dus nu heb je echt een diskette.
>> En wat is er opmerkelijk aan deze dat voor zover het een
kleinschalige voorstelling van een grotere harde schijf, deze dingen zijn super,
super eenvoudig.
Als je de onderkant van het knijpen, nu dat dat metalen ding is af, en schil
ze open, alles wat er is twee stukken vilt en de zogenaamde floppy disk
met een stuk metaal aan de binnenkant.
>> En daar gaat de helft van de inhoud van mijn schijf.
Daar gaat weer de helft van hen.
Maar dat is alles wat draaide binnen van uw computer in weleer.
>> En nogmaals, om dit in perspectief te zetten, hoe groot is het grootste deel van uw
harde schijven tegenwoordig?
500 gigabyte, een terabyte, misschien in een desktop computer, 2 terabyte, 3
terabytes, 4 terabyte, toch?
Dit is een megabyte, geven of te nemen, die zelfs niet kan passen in een typische MP3
meer deze dagen, of een soortgelijke muziekbestand.
>> Dus een beetje souvenir voor u vandaag, en ook om te helpen contextualiseren wat
We nemen voor lief nu in de problemen van de vijf.
Dus dat zijn jou te houden.
Dus laat ik de overgang naar waar zal zijn de besteding van de volgende pset ook.
Dus we hebben nu ingesteld deze pagina voor - oh, een paar aankondigingen snel.
>> Deze vrijdag, als je zou willen aansluiten CS50 voor de lunch, ga dan naar de gebruikelijke plaats,
cs50.net/rsvp.
En laatste project -
dus per de syllabus, hebben we postte de afstudeerproject specificatie reeds.
Realiseer je dat dat betekent niet dat het is te wijten bijzonder snel.
Het is geplaatst, echt, alleen maar om jullie denken.
En inderdaad, een super significant percentage van jullie zullen aanpakken
afstudeerprojecten op materiaal dat we zijn nog niet eens gekregen om in de klas,
maar zal zo vroeg volgende week.
>> Mededeling, hoewel, dat de spec vraagt ​​om een paar verschillende onderdelen van de
afstudeerproject.
De eerste, in een paar weken, een pre-voorstel, een vrij casual email naar
uw TF om hem te vertellen of wat je bent na te denken over voor uw project, met
Geen langdurige verbintenissen.
Voorstel zal uw specifieke commitment, zeggende, hier, dit is wat
Ik zou willen doen voor mijn project.
Wat denk je?
Te groot?
Te klein?
Is het beheersbaar?
En zie je de spec voor meer details.
>> Een paar weken na dat is de status verslag dat een soortgelijke
toevallige email naar uw TF te zeggen hoe ver achter je in je laatste
project implementatie, gevolgd door de CS50 Hackathon waaraan iedereen
is uitgenodigd, die zal een gebeurtenis uit zijn 20:00 Op een avond tot 07:00
AM de volgende ochtend.
Pizza, zoals ik in de week kunnen zijn genoemd nul, zul worden geserveerd op 09:00,
Chinees eten in 01:00.
En als je nog wakker om 5:00 AM, we brengen je naar IHOP voor het ontbijt.
>> Dus Hackathon is een van de meer memorabele ervaringen in de klas.
Dan is de uitvoering te wijten, en dan is de climax CS50 Fair.
Meer informatie over al deze in de komende weken.
>> Maar laten we terug gaan naar iets oude school -
weer een array.
Dus een array was leuk, want het lost problemen, zoals we zagen slechts een
daarnet met student structuren een beetje uit de hand als we
willen student een, student twee, hebben student drie, student dot dot dot,
een willekeurig aantal studenten.
>> Dus arrays, een paar weken geleden, dook in en opgelost al onze problemen van niet
van tevoren te weten hoeveel dingen van een soort we zouden willen.
En we hebben gezien dat structs ons kan helpen onze code verder te organiseren en te houden
begripsmatig overeenstemmen variabelen, zoals een naam en een huis, samen, zodat we
kunnen ze te behandelen als een entiteit, binnen waarvan er kleinere stukken.
>> Maar arrays hebben een aantal nadelen.
Wat zijn de nadelen we hebben ondervonden
met arrays dusver?
Wat is dat?
Vaste grootte - dus zelfs al heb je misschien kunt geheugen toewijzen voor een
array, als je eenmaal weet hoeveel studenten je hebt, hoeveel tekens je hebt
van de gebruiker, als je eenmaal hebt toegewezen de array, je hebt soort van geschilderde
jezelf in een hoek.
>> Omdat je nieuwe elementen niet kan invoegen in het midden van een array.
U kunt geen meer elementen aan het einde van een array.
Echt, moet je toevlucht nemen tot het creëren van een geheel nieuwe serie, zoals we hebben besproken,
kopiëren van de oude naar de nieuwe.
En nogmaals, dat is de hoofdpijn die GetString behandelt voor u.
>> Maar nogmaals, je kunt niet eens invoegen iets in het midden van de array
Als de prijs is niet helemaal gevuld.
Bijvoorbeeld, als deze array hier omvang zes heeft slechts vijf dingen erin,
goed, je kon gewoon overstag iets op het einde.
Maar wat als je iets wilt invoegen in het midden van de
matrix, hoewel het misschien vijf van de zes dingen in het?
>> Nou, wat hebben we gedaan toen we hadden allemaal van onze menselijke vrijwilligers op het podium in
weken voorbij?
Als we wilden iemand hier zetten, ofwel deze mensen hoe dit te verplaatsen
manier, of deze mensen hoe dit te verplaatsen manier, en dat werd duurder.
De verschuiving van mensen binnen een serie eindigde het optellen en kostprijsberekening
ons tijd, dus veel van onze n kwadraat looptijden zoals insertion sort, voor
Bijvoorbeeld, in het ergste geval.
Dus arrays zijn geweldig, maar je moet tevoren weten hoe groot je ze wilt.
>> Nou ja, hier is een oplossing.
Als ik niet weet op voorhand hoeveel studenten die ik zou kunnen hebben, en ik weet dat een keer
Ik besluit, hoewel, ik zit vast met die veel studenten, waarom ik niet gewoon altijd
toewijzen twee keer zoveel ruimte als ik zou denken ik nodig?
Is dat niet een redelijke oplossing?
>> Realistisch, ik denk niet dat dat we gaat meer dan 50 slots nodig
in een array voor een middelgrote klasse, dus laten we gewoon naar boven afronden.
Ik zal 100 sleuven te maken in mijn array, net zodat we kunnen zeker de
aantal studenten verwacht ik in sommige middelgrote klasse.
Dus waarom niet gewoon afronden en toewijzen meer geheugen, typisch voor een serie
dan u denkt u misschien nog nodig?
Wat is dit eenvoudige pushback aan dat idee?
>> Je bent gewoon verspilt geheugen.
Letterlijk elk programma dat u dan schrijven is misschien wel twee keer zoveel geheugen als
je eigenlijk nodig hebt.
En dat voelt niet als een bijzonder elegante oplossing.
Bovendien vermindert alleen de waarschijnlijkheid van een probleem.
Als je toevallig een populaire cursus hebben een semester en je hebt 101
studenten, het programma is nog steeds fundamenteel geconfronteerd met hetzelfde probleem.
>> Zo gelukkig, er is een oplossing voor Deze advertentie al onze problemen in de vorm
van datastructuren die complexer dan die
we hebben tot nu toe gezien.
Dit, ik beweer, is een gelinkte lijst.
Dit is een lijst met nummers -
9, 17, 22, 26, en 34 -
die zijn met elkaar verbonden door van wat ik heb getekend als pijlen.
>> Met andere woorden, als ik wilde vertegenwoordigen een array, kon ik doen
zoiets als dit.
En ik zal dit op de overhead in slechts een moment.
Ik kon doen -
hello, oke.
Stand-by.
Nieuwe computer hier, duidelijk -
oke.
>> Dus als ik deze nummers in de reeks -
9, 17, 22, 26, 24 -
niet noodzakelijk op schaal.
Oke, dus hier is mijn matrix -
oh mijn god.
Oke, dus hier is mijn array.
Oh mijn god.
>> [Lachen]
>> DAVID Malan: Pretend.
Het is te veel moeite om terug te gaan en vast te stellen dat, dus er -
26.
Dus we hebben deze array van 9, 17, 22, 26 en 34.
Voor degenen onder u ziet de pijnlijke fout die ik maakte,
daar is het.
>> Dus ik beweren dat dit een zeer efficiënte oplossing.
Ik heb toegewezen zoveel ints als Ik heb - een, twee, drie,
vier, vijf, of zes -
en ik heb vervolgens opgeslagen de nummers binnen deze array.
Maar stel, dan, ik wil invoegen een waarde als de nummer 8?
Nou ja, waar gaat het naartoe?
Stel dat ik wil invoegen een getal als 20.
Nou ja, waar gaat het naartoe?
Daar ergens in het midden, of het getal 35 te gaan
ergens eind.
Maar ik ben al uit de ruimte.
>> En dus dit is een fundamentele uitdaging van arrays die niet de oplossing zijn.
Ik beweerde een moment geleden, getString lost dit probleem op.
Als u wilt een zesde cijfer wilt invoegen in deze array, wat tenminste een
oplossing die u kunt terugvallen op zeker, net zoals we doen met GetString?
Wat is dat?
>> Nou, maak het groter wordt makkelijker gezegd dan gedaan.
We kunnen niet per se de array groter, maar wat kunnen we doen?
Maak een nieuwe array die is groter, de grootte 6, of misschien maat 10, als we willen
om de zaken vooruit te krijgen, en kopieer de oude array naar de nieuwe, en dan
bevrijden van de oude array.
>> Maar wat is de looptijd nu van dat proces?
Het is groot O van n, omdat het kopiëren gaat kosten u een aantal eenheden van
tijd, dus niet zo ideaal als we moeten toewijzen van een nieuwe serie, die gaat
twee keer zoveel consumeren geheugen tijdelijk.
Kopieer oud naar nieuw -
Ik bedoel, het is gewoon een hoofdpijn, die is, nogmaals, waarom wij schreven
GetString voor u.
>> Dus wat kunnen we in plaats daarvan doen?
Nou, wat als onze datastructuur heeft eigenlijk lacunes in het?
Stel dat ik ontspannen mijn doel van het hebben van aaneengesloten delen van het geheugen, waarbij 9
ligt pal naast 17, dat is naast 22, enzovoort.
>> En stel dat 9 hier in kan zijn RAM, en 17 kan hier worden oververtegenwoordigd in RAM,
en 22 kunnen hier worden oververtegenwoordigd in het RAM.
Met andere woorden, ik heb ze niet nodig zelfs terug meer naar terug.
Ik moet gewoon een of andere manier draad een naald door elk van deze nummers of elke
van deze knooppunten, zoals we zullen noemen de rechthoeken zoals ik ze heb getekend, om
herinner me hoe je naar de laatste dergelijke knooppunt van de eerste.
>> Dus wat is het programmeren bouwen we hebben vrij recent gezien waarmee ik
kan die draad te voeren, of hier getekend, waarmee ik kan
implementeren die pijlen?
Dus pointers, toch?
Als ik wijzen niet alleen een int, maar een knoop - en
knoop, ik bedoel gewoon container.
En visueel, bedoel ik een rechthoek.
Dus een knooppunt blijkbaar nodig heeft om twee waarden bevatten -
het int zelf, en dan, zoals gesuggereerd door de onderste helft van de rechthoek,
genoeg ruimte voor een int.
>> Dus gewoon vooruitdenken hier, hoe groot is dit knooppunt, dit
container in kwestie?
Hoeveel bytes voor de int?
Vermoedelijk 4, als het hetzelfde als normaal.
En dan hoeveel bytes voor de pointer?
4.
Dus deze container, of dit knooppunt, is naar een 8-byte structuur.
Oh, en dat is een gelukkig toeval dat we gewoon introduceerde dit begrip
een structuur, of een C-structuur.
>> Dus ik beweren dat ik een stap wilt nemen richting van deze meer geavanceerde
uitvoering van een lijst van nummers, een gelinkte lijst van nummers, ik moet een doen
weinig meer denken aan de voorkant en verklaren niet alleen een int, maar een structuur
dat ik bel, conventioneel hier, knooppunt.
We kunnen het noemen wat we willen, maar knooppunt gaat thematische zijn in veel
van de dingen die we gaan kijken naar nu.
>> Binnenkant van dat knooppunt is een int n.
En dan deze syntaxis, een beetje raar op het eerste gezicht -
struct knoop * next.
Nou picturaal, wat is dat?
Dat is de onderste helft van de rechthoek die we zagen
slechts een moment geleden.
>> Maar waarom zeg ik struct knoop * in tegenstelling tot enkel knooppunt *?
Want als dat pointer wijst op een ander knooppunt, het is gewoon de
adres van een node.
Dat is in overeenstemming met wat we hebben gesproken over pointers tot nu toe.
Maar waarom, als ik beweer deze structuur is genaamd knooppunt, moet ik zeggen struct
knooppunt binnen hier?
>> Precies.
Het is een soort van een domme realiteit van C. De typedef, om zo te zeggen, heeft niet
nog niet gebeurd.
C is super letterlijke.
Het leest de code boven aan beneden, van links naar rechts.
En totdat hij raakt dat puntkomma aan het bottom line, wat denk je wel niet
bestaan ​​als een data type?
Node, citaat unquote knooppunt.
>> Maar vanwege de uitgebreidere verklaring deed ik op de eerste lijn -
typedef struct knoop -
want dat kwam voor het eerst, voordat de accolades, dat is een soort als
pre-opleiden Clang dat, je weet je wat, geef me een struct
riep struct knoop.
Eerlijk gezegd, ik hou niet van bellen dingen struct knoop, struct knooppunt alle
heel mijn code.
Maar ik zal slechts een keer gebruiken, net binnen, zodat ik kan effectief
creëren een soort cirkelvormige referentie, niet een pointer mezelf per se, maar een
pointer naar de andere van een identiek type.
>> Dus het blijkt dat op een datastructuur als dit, is er een paar
bewerkingen die kunnen worden voor ons van belang.
We zouden willen invoegen in een lijst als deze.
We zouden willen verwijderen uit een lijst als deze.
We zouden willen de lijst voor een zoeken waarde, of meer algemeen, traverse.
En traverse is gewoon een mooie manier om zeggend beginnen bij de linker en verplaatst u alle
helemaal naar rechts.
>> En merk, zelfs met deze iets meer geavanceerde datastructuur, laat
ik stel voor dat we een aantal van kunnen lenen de ideeën van de afgelopen twee weken en
uitvoeren van een functie genaamd zoeken als deze.
Het gaat om waar te keren of vals, wat aangeeft, ja of
nee, n in de lijst.
Het tweede argument is een pointer aan de lijst zelf, dus een
pointer naar een knooppunt.
>> Alles wat ik ga doen is dan te verklaren een tijdelijke variabele.
We noemen het ptr volgens afspraak, voor de aanwijzer.
En ik wijs deze gelijk is aan de het begin van de lijst.
>> En let nu op de while lus.
Zolang pointer niet gelijk op null, ga ik om te controleren.
Is aanwijzer n gelijk aan de n die in was geslaagd?
En wacht een minuut - nieuw stuk van de syntax.
Wat is pijl ineens?
Yeah?
>> Precies.
Dus terwijl een paar minuten geleden, gebruikten we de dot-notatie om iets te
binnenkant van de structuur, als de variabele je hebt niet de struct
zelf, maar een pointer naar een struct, gelukkig, een stuk van de syntaxis die
maakt eindelijk intuïtief gevoel.
De pijl geeft de aanwijzer volgen, zoals onze pijlen doorgaans betekenen
pictorially, en gaan op dataveld binnen.
Dus pijl is hetzelfde als stip, maar u het gebruiken als je een pointer.
>> Dus gewoon om samen te vatten dan, als het veld n binnenkant van de struct genaamd aanwijzer
gelijk gelijk n, return true.
Anders, deze lijn hier - wijzer gelijk pijltje.
Dus wat dit doet, mededeling, is als ik ben momenteel wijzend op de structuur
met 9, en 9 is niet het aantal Ik ben op zoek naar - veronderstel ik zoek
voor n gelijk aan 50 -
Ik ga mijn tijdelijke pointer updaten om niet wijzen op dit knooppunt
meer, maar wijzer pijl naast, die gaat me hier zetten.
>> Nu, realiseerde ik is een wervelwind introductie.
Op woensdag gaan we eigenlijk doen met een aantal mensen en met wat meer
code in een langzamer tempo.
Maar beseffen, zijn we nu het maken van onze gegevens structuren complexer, zodat onze
algoritmen kunnen krijgen efficiënter, die zal worden vereist voor
PSET zes, toen we laden, nogmaals, die 150.000 woorden, maar moeten doen
efficiënt, en idealiter, maak een programma dat draait voor onze gebruikers niet in
lineaire, niet in n kwadraat, maar constante tijd, in het ideaal.
>> We zien je op woensdag.
>> SPEAKER: Bij de volgende CS50, David vergeet zijn basisscenario.
>> DAVID Malan: En dat is hoe je stuur tekstberichten met C. Wat de -
>> [DIVERSE TEKSTBERICHT AANMELDING SOUNDS]