Tip:
Highlight text to annotate it
X
>> DAVID MALAN: Greit, velkommen tilbake.
Dette er CS50.
Dette er starten på uke syv.
Så det har gått en stund, så jeg trodde vi skulle ta en rask tur hvor vi
slapp og hvor vi er nå i gang.
>> Så denne tingen her kan ha forårsaket noen angst i begynnelsen.
Men forhåpentligvis, du begynner å akklimatisere seg til hva dette betyr her -
stjerne representerer en peker, som er akkurat det, i mer lekmann vilkår?
Så det er en adresse.
>> Så det er adressen til noe i minnet.
Og vi begynte å skrelle tilbake lagene et par uker siden, ting liker
GetString og andre slike funksjoner hele denne tiden har vært tilbake
adressene til ting i minnet, som Adressen til det første tegnet i
noen sekvens.
>> Så vi også innført Valgrind, som du vil begynne å bruke for dette problemet
angitt, spesielt for den neste Problemet apparat i tillegg.
Og Valgrind gjør hva for oss?
Den sjekker for minnelekkasjer, og det også sjekker for misbruk av minne.
>> Det kan, med en viss sannsynlighet, oppdage om koden din kommer til å berøre minne
at det rett og slett ikke burde.
Så ikke nødvendigvis en lekkasje, men hvis du gå utover grensene for noen
array, og du faktisk kjøre Valgrind og indusere at atferd mens
Valgrind kjører i programmet er kjører inne i den, vil du få
meldinger som dette - "ugyldig skrive av størrelse 4 ", som husker et par
uker siden betydde at jeg hadde et uhell som på en int for langt
over grensene av en matrise.
Og så størrelse 4 her betyr størrelsen av den aktuelle int.
>> Så ta oppmuntring i det faktum at Valgrind utgang, formatet på det,
er bare fryktelig.
Det er virkelig vanskelig å se gjennom rotet for interessant informasjon.
Så det vi har gjort her er bare utdrag noen av de par mer
interessante linjer.
Men innser at 80% av Valgrind er produksjonen kommer til å være litt av en
distraksjon.
>> Bare se etter mønstre som dette - ugyldig høyre, ugyldig lese, 40 bytes
og et antall blokker er definitivt tapt, søkeord sånn.
Og hva vil du forhåpentligvis se er noen slags spor av hvilken funksjon
feil er faktisk i.
I dette tilfellet er her, i hvilken linje koden min var feilen tilsynelatende?
>> 26 i en fil kalt memory.c, som var eksempelet vi lekte med
på den tiden.
Så det er nok ikke i malloc.
Det var trolig i koden min i stedet.
Så får vi se dette igjen og igjen før lenge.
>> Så scanf, kom dette opp i en par av skjemaer så langt.
Vi så sscanf kort.
Det var noe en rekke du stupte inn i din
forberedelsene til quiz.
Og scanf er faktisk hva CS50 Biblioteket er brukt under
hette i ganske lang tid for å få input fra brukeren.
>> For eksempel, hvis jeg flytter over til CS50 apparatet her, la meg åpne opp en
eksempel i dag som kalles scanf-0.c Og det er super enkelt.
Det er bare noen få linjer med kode.
Men det viser egentlig hvor getInt har arbeidet hele denne tiden.
>> I dette programmet her, på linje 16. Legg merke til at jeg erklære en int.
Så ingen pekere, ingenting magisk der, bare en int.
Så i linje 17, ber jeg brukeren etter et nummer, takk.
Så i slutten av 18, jeg bruker scanf her.
Og jeg er spesifisert, type som printf, at jeg venter sitat
unquote prosent i.
>> Så prosent I selvsagt betegner en int.
Men legg merke til hva den andre argumentet til scanf er.
Hvordan vil du beskrive den andre argumentet etter kommaet?
Hva er det?
>> Det er adressen til x.
Så dette er nyttig fordi ved å gi scanf med adressen til x, hva gjør
som mulig for den funksjonen å gjøre?
Ikke bare gå dit, men også gjøre det?
>> Gjøre en endring til det.
Fordi du kan gå der, det er liksom som et kart til et sted i minnet.
Og så lenge du gir scanf, eller noen funksjon med et slikt kart, som
Funksjonen kan gå dit, og ikke bare se på verdien, men det kan også
endre denne verdien, noe som er nyttig hvis hensikten i livet til scanf er å
skanne input fra brukeren, spesielt fra tastaturet.
Og f betegner formatert, akkurat som printf, betegner f en formatert
streng som du vil skrive ut.
>> Så kort sagt, denne linjen 18 bare sier, prøver å lese en int fra brukerens
tastatur og lagre den på innsiden av x, på uansett adresse x tilfeldigvis lever.
Og så til slutt, linje 19 bare sier, takk for int, i dette tilfellet.
>> Så la meg gå videre og gjøre dette.
Så gjør scanf 0.
La meg gå videre og zoome inn
Jeg skal gå og kjøre denne med prikker slash scanf 0.
Nummer, please?
50.
Takk for 50.
Så det er ganske enkel.
>> Nå hva er det ikke å gjøre?
Det er ikke å gjøre en hel haug av feilsjekking.
For eksempel, hvis jeg ikke samarbeider, og jeg ikke skriver inn et nummer, men
stedet jeg skriver noe sånt som "hallo", det er bare ganske rar.
Og så en av de tingene CS50 Biblioteket har gjort for oss for noen
Klokken er at reprompting og reprompting.
>> Retry setning tilbakekallingen var i cs50.c, og det er grunnen til at getInt i
den CS50 biblioteket er faktisk en hel haug med linjer lange, fordi vi er
sjekker for dumme ting som dette.
Visste brukeren ikke gi oss, faktisk, en int?
Har han eller hun gi oss noe som en alfabetisk brevet?
I så fall ønsker vi å oppdage det og kjefte på dem.
>> Men ting blir mer interessant i denne neste eksempel.
Hvis jeg går til scanf-1.c, er hva en ting som er fundamentalt endret i
dette neste eksempel?
Jeg bruker char *, selvfølgelig, i stedet for int.
>> Så dette er interessant, fordi røye *, husker, er egentlig bare
samme som streng.
Så det føles som kanskje dette er en super enkel implementering av GetString.
Men jeg har skrelles tilbake layer av CS50-biblioteket, så jeg er
kalle dette røye * nå.
Så la oss se der, hvis noe, vi går galt.
>> Linje 17 -
Jeg igjen si, kan du gi meg noe, i dette tilfellet, en streng.
Og så i neste linje, kaller jeg scanf, igjen, gir det et format kode,
men denne gangen prosent s.
Og så denne gangen er jeg gir det buffer.
>> Legg merke til nå, er jeg ikke bruker -tegnet.
Men hvorfor er det sannsynligvis OK her?
Fordi det er buffer allerede?
Det er allerede en peker.
Det er allerede en adresse.
>> Og la oss dette ordet "forvirre", la meg bare kalle det er, for eksempel, for
enkelhet.
Men jeg har kalt det bufre fordi i Generelt, i programmering, hvis du har en
del av minnet som en streng virkelig bare er, kan du kalle det en buffer.
Det er et sted å lagre informasjon.
>> I likhet med ting som YouTube, da de er bufring, så å si, at
betyr bare at det er nedlasting av biter fra Internett og lagre dem i en
lokale array, en lokal del av minnet slik at du kan se det senere uten
det hoppe eller henger på deg mens du spiller.
>> Så det er et problem her skjønt, fordi jeg forteller scanf, forventer en
strengen fra brukeren.
Her er adressen til en del av minnet.
Sett at strengen der.
Hvorfor er det bundet gi problemer for oss, skjønt?
>> Hva er det?
Har jeg lov til å få tilgang den del av hukommelsen?
Du vet, jeg vet ikke.
Fordi har buffer blitt initialisert til noe?
Ikke egentlig.
Og så det er hva vi har ringt en søppel verdi, hvilken
er ikke en formell ord.
Det betyr bare vi har ingen anelse om hva bits er innsiden av de fire byte som
Jeg har avsatt som buffer.
>> Jeg har ikke kalt malloc.
Jeg har definitivt ikke kalt GetString.
Så hvem vet hva som faktisk er innsiden av buffer?
Og likevel fortelle scanf blindt, går det og plassere hva brukeren har skrevet.
>> Så hva er sannsynlig å forårsake i koden vår hvis vi kjøre den?
Sannsynligvis en segfault.
Kanskje ikke, men sannsynligvis en segfault.
Og jeg sier kanskje ikke fordi noen ganger du gjør, noen ganger
du får ikke en segfault.
Noen ganger får du bare heldig, men det likevel kommer til å være
en bug i programmet vårt.
>> Så la meg gå videre og kompilere dette.
Jeg kommer til å gjøre det på den gamle skolen måte.
Så klang dash 0, scanf-en, scanf-1.c, Enter.
Oops, også gamle skolen.
La oss se.
Hvor gikk jeg?
Oh, char * buffer.
Oh, takk -
Lagre, OK -
svært gamle skolen.
Greit, det har vært en stund.
>> Så jeg har nettopp reddet filen etter noe som gjør at midlertidig
endre et øyeblikk siden.
Og nå har jeg samlet det manuelt med Clang.
Og nå skal jeg gå videre og kjøre scanf-en, Enter.
String behage.
Jeg skal skrive inn "hei."
>> Og nå, her er der, ærlig, printf kan er litt irriterende.
Det er faktisk ikke kommer til segfault i dette tilfellet.
Printf er litt spesiell fordi det er så super vanlig at
hovedsak printf gjør oss en tjeneste og realisere,
det er ikke en gyldig peker.
La meg ta det på meg å bare skrive ut i parentes null, selv
men det er ikke nødvendigvis hva vi selv forventet.
>> Så vi kan egentlig lett indusere en segfault med dette, men klart dette
er ikke oppførselen jeg ønsket.
Så hva er den enkle løsningen?
Vel, i scanf-2, la meg foreslå at i stedet for å faktisk bare tildeling av en
char *, la meg være litt smartere om dette, og la meg allokere buffer
som en sekvens av 16 tegn.
>> Så jeg kan gjøre dette i et par måter.
Jeg kunne absolutt bruke malloc.
Men jeg kan gå tilbake til uke to når Jeg trengte bare en hel haug med
tegn.
Det er bare en matrise.
Så la meg i stedet omdefinere buffer å være en matrise av 16 tegn.
>> Og nå, når jeg passerer buffer i -
og dette er noe vi ikke snakke om i uke to -
men du kan behandle en matrise som om det er en adresse.
Teknisk sett, som vi har sett, er de litt annerledes.
Men scanf vil ikke tankene hvis du passerer det navnet på en matrise, fordi det
Clang vil gjøre for oss er egentlig behandle navnet på denne matrisen som
adressen til blings av 16 byte.
>> Så dette er bedre.
Dette betyr nå at jeg kan forhåpentligvis gjør du følgende.
La meg zoome ut et øyeblikk og gjør scanf-2, utarbeidet OK.
Nå la meg gjøre fikk slash scanf-2.
String behage. "Hello". Og det syntes å fungere denne gangen.
>> Men kan noen foreslå et scenario der ikke kan det fortsatt virke?
Yeah?
Noe lengre enn 16 tegn.
Og faktisk, kan vi være litt mer presis.
Noe lenger enn 15 tegn, fordi vi virkelig trenger å huske på
at vi trenger at backslash null implisitt ved enden av strengen,
som er en side scanf vil typisk ta vare på for oss.
>> Så la meg gjøre noe sånt -
Noen ganger kan vi bare la det sånn.
OK, så vi har nå indusert vår segmentering feil.
Hvorfor?
Fordi jeg skrev til mer enn 15 tegn, og så vi har faktisk
rørte minne som jeg faktisk ikke burde ha.
>> Så hva er egentlig løsningen her?
Vel, hva om vi trenger en lengre streng?
Vel, vi kanskje gjøre det 32 bytes.
Vel, hva om det ikke er lenge nok?
Hvordan ca 64 bytes?
Hva hvis det ikke er lenge nok?
Hva med 128 eller 200 bytes?
Hva er egentlig løsningen her i generelle tilfellet, hvis vi ikke vet i
avansere hva brukeren kommer til å skrive?
>> Det er bare slags en stor smerte i ræva, for å være ærlig, det er derfor den
CS50 Biblioteket har et par dusin linjer kode som kollektivt implementere
GetString streng på en måte som vi ikke må vite på forhånd hva
brukeren kommer til å skrive.
Spesielt hvis du ser tilbake på cs50.c fra to uker siden, vil du se
at GetString faktisk gjør Ikke bruk scanf på denne måten.
Snarere, leser det ett tegn gangen.
>> Fordi en fin ting om lese ett tegn er at vi kan
garantere oss til alltid har minst en røye.
Jeg kan bare erklære en røye, og deretter ta disse virkelig små steg til bare
lese ett tegn på at en tid fra tastaturet.
Og så, hva du vil se GetString gjør er hver gang den går tom for,
si, 16 byte minne, bruker den malloc, eller en fetter av denne, til
tildele mer minne, kopiere gamle minnet inn i det nye, og deretter krypende
sammen, får ett tegn om gangen, og når den går ut av det
del av minnet, kaster det bort, griper en større del av minnet, kopierer gamle
inn i nye, og gjentar.
Og det er virkelig en smerte å faktisk gjennomføre noe så enkelt som
få innspill fra en bruker.
>> Så du kan bruke scanf.
Du kan bruke andre lignende funksjoner.
Og mange av lærebøker og online eksempler gjør, men de er alle
sårbare for problemer som dette.
Og til slutt, får en segfault er litt irriterende.
Det er ikke bra for brukeren.
>> Men i verste fall, hva gjør det fundamentalt sette
kode i fare for?
En slags angrep, potensielt.
Vi snakket om et slikt anfall - overfylte stabelen.
Men generelt, hvis du har lov til overflow en buffer, som vi gjorde en
par uker siden, med bare å skrive mer enn "hei" på stakken, du
kan faktisk ta over, potensielt, en datamaskin, eller i det minste få på data som
ikke tilhører deg.
>> Så kort sagt, dette er grunnen til at vi har de trening hjul.
Men nå begynner vi å ta dem av, som våre programmer ikke trenger lenger,
nødvendigvis, input fra brukeren.
Men i tilfelle av problemet satt seks, dine innspill vil komme fra et stort
ordlistefilen med 150 noen Odd tusen ord.
>> Så du slipper å bekymre deg for brukerens vilkårlig inngang.
Vi vil gi deg noen forutsetninger om filen.
Eventuelle spørsmål om pekere eller scanf eller brukerundersøkelser generelt?
>> Ok, så en rask *** da på en etterfølgende tema fra to uker siden.
Og det var denne tanken om en struct.
Ikke det - denne tanken om en konstruere, som var det?
Hva gjorde struct gjøre for oss?
>> Definer -
beklager?
Definere en variabel type.
Så liksom.
Vi faktisk kombinere to emner.
Så med typedef, husker at vi kan erklære en type vår egen, som en
synonym, som snor etter røye *.
Men ved hjelp av typedef og struct, kan vi skape virkelig våre egne datastrukturer.
>> For eksempel, hvis jeg går tilbake til gedit her for en liten stund, og jeg går videre
og gjøre noe sånt, la meg spare dette som, la oss si, structs.c
midlertidig, jeg bare kommer å gå videre og omfatte
standardio.h, int main ugyldig.
Og så i her, antar at jeg vil å skrive et program som lagrer
flere studenter fra flere hus, for eksempel.
Så det er som en registrarial database av noe slag.
>> Så hvis jeg trenger navnet en student, jeg kan gjøre noe sånt char * navn,
og jeg skal gjøre noe sånt -
faktisk, la oss bruke CS50 bibliotek for bare et øyeblikk å gjøre dette til en
litt enklere, så vi kan låne de dusinvis av linjer med kode.
Og la oss holde bare det enkelt.
Vi vil holde det streng, og nå GetString.
>> Så jeg hevder nå at jeg har lagret navnet av noen student, og huset
noen student, bare ved hjelp av variabler som vi gjorde, og i uke en.
Men antar jeg nå ønsker å støtte flere studenter.
All right, så mine instinkter er å gjøre string navn2, blir GetString, string
house2 får GetString.
Og da er vår tredje student, la oss gjøre NAME3 GetString.
>> Ok, så dette er forhåpentligvis slående du som en slags dum,
fordi denne prosessen er egentlig aldri kommer til å ende, og det er bare kommer til
gjøre mitt koden ser verre og verre og verre.
Men vi løste dette også i uke to.
Hva var vår relativt ren løsning når vi hadde flere variabler av
samme datatype som alle er i slekt, men vi ønsker ikke dette fryktelig rot
av lignende navn variabler?
Hva gjorde vi i stedet?
>> Så jeg tror jeg hørte noen steder.
Vi hadde en matrise.
Hvis du vil ha flere forekomster av noe, hvorfor ikke vi rydde alt dette
opp og bare si, gi meg matrise kalt navn?
>> Og for nå, la oss hardt kode tre.
Og så gi meg en annen matrise kalt hus, og la meg for
nå hardt kode tre.
Og jeg har massivt ryddet opp rotet som jeg nettopp opprettet.
Nå har jeg fortsatt hard kodet tre, men selv 3 kan den dynamisk komme fra
brukeren, eller argv eller lignende.
Så dette er allerede renere.
>> Men det som er irriterende om dette er at nå, er at selv om et navn eller annen måte
fundamentalt knyttet til en student hus -
det er en student som jeg virkelig ønsker å representere -
Jeg har nå to arrays som er parallelle i den forstand at de er
samme størrelse, og navnene brakett 0 formodentlig kart til hus brakett 0,
og navnene brakett en maps til hus bracket en.
Med andre ord, at studenten bor i det huset, og at andre student
bor i det andre huset.
Men sikkert dette kan være gjort enda mer renslig.
>> Vel, det kan, faktisk.
Og la meg gå videre og åpne opp structs.h, og du vil
se denne ideen her.
Legg merke til at jeg har brukt typedef, som du hentydet til et øyeblikk siden å erklære vår
egen datatype.
Men jeg er også bruker denne andre søkeord kalt struct som gir meg en ny
datastruktur.
>> Og dette datastruktur jeg påstå kommer ha to ting på innsiden av
det - en streng kalt navn, og en streng kalt huset.
Og navnet jeg kommer til å gi til dette datastruktur kommer
å bli kalt student.
Jeg kan kalle det hva jeg vil, men dette semantisk gjøre
mening for meg i mitt sinn.
>> Så nå, hvis jeg åpner opp en bedre versjon av programmet begynte jeg å skrive
der, la meg bla til toppen.
Og det er noen flere linjer med kode her, men la meg fokusere for
øyeblikket på en.
Jeg har erklært en konstant kalt studenter og hardkodet 3 for nå.
Men nå merke til hvor rent min kode begynner å få.
>> I tråd 22, erklærer jeg spekter av studenter.
Og legg merke til at studenten er tilsynelatende nå en datatype.
Fordi på toppen av denne filen, merker Jeg har tatt med at header-fil
at jeg trakk opp bare et øyeblikk siden.
Og at header-fil rett og slett hadde denne definisjonen av en student.
>> Så nå har jeg laget mine egne data type som forfatterne av C år
siden ikke tenke på på forhånd.
Men ikke noe problem.
Jeg kan gjøre det selv.
Så dette er en matrise som kalles studenter, hver av medlemmene
er en student struktur.
Og jeg vil ha tre av de i matrisen.
>> Og nå, hva gjør resten av dette programmet gjøre?
Jeg trengte noe litt vilkårlig.
Så fra online 24 og framover, Jeg iterere 0-3.
Jeg deretter be brukeren om studentens navn.
Og så jeg bruker GetString som før.
Så jeg ber om studentens huset, og jeg bruker GetString som før.
>> Men legg merke til - litt nytt stykke syntaks -
Jeg kan fortsatt indeksen til i-te student, men hvordan får jeg på spesifikke data
Feltet innsiden av struct?
Vel, hva er tilsynelatende nytt stykke av syntaks?
Det er bare prikken operatør.
>> Vi har egentlig ikke sett dette før.
Du har sett det i PSett fem hvis du har kastet seg allerede med bitmap-filer.
Men prikken betyr bare innsiden av denne struct eller flere felt, gi dot
navn, eller gi meg dot huset.
Det betyr gå på innsiden av struct og få de aktuelle feltene.
>> Hva gjør resten av dette programmet?
Det er ikke alle som sexy.
Legg merke til at jeg iterere 0-3 igjen, og jeg bare lage en engelsk
setning som så og så er i en slik og et slikt hus, passerer i dot navn fra
i-te student og deres huset også.
>> Og så til slutt, nå skal vi begynne å bli *** om dette, nå som vi er
kjent med hva malloc og andre funksjoner har vært
gjør hele denne tiden.
Hvorfor trenger jeg å frigjøre både navn og hus, selv om jeg
ikke kalle malloc?
>> GetString gjorde.
Og det var den skitne lille hemmelighet for flere uker, men GetString har
vært lekker minne over hele plassere alle semester så langt.
Og Valgrand vil til slutt avsløre dette til oss.
>> Men det er ikke en stor avtale, fordi jeg vet at jeg kan rett og slett frigjøre navnet
og huset, men teknisk, til være super, super trygg, bør jeg være
gjøre noen feilsjekking her.
Hva er dine instinkter forteller deg?
Hva bør jeg se etter før jeg frigjøre hva som er en
string, aka som en røye *?
>> Jeg burde egentlig være å sjekke om elevene brakett i dot navnet ikke er
lik null.
Da kan det være OK å gå videre og gratis som peker, og samme eller den annen
en også.
Hvis elevene brakett i dot huset er ikke lik null, dette nå vil beskytte
mot hjørnet tilfelle hvor GetString returnerer noe sånt null.
Og vi så for et øyeblikk siden, printf vil beskytte oss her oppe ved å bare si
null, som kommer til å se rart.
Men minst det ikke vil segfault, som vi har sett.
>> Vel, la meg gjøre en annen ting her. structs-0 er en slags dum program
fordi jeg inn alle disse dataene, og deretter det er tapt når programmet avsluttes.
Men la meg gå videre og gjøre dette.
La meg gjøre terminalen vinduet litt større.
La meg gjøre structs-1, som er en ny versjon av denne.
>> Jeg vil zoome inn litt.
Og nå la meg kjøre dot slash structs-en.
Studentens navn -
David Mather, la oss gjøre Rob Kirkland, la oss gjøre Lauren Leverett.
Det interessante er nå varsel -
og jeg bare vet dette fordi Jeg skrev programmet -
det er en fil nå på min nåværende katalog kalt students.csv.
Noen av dere har kanskje sett disse i den virkelige verden.
>> Hva er en CSV-fil?
Komma-separerte verdier.
Det er liksom som en fattig mann versjon av en Excel-fil.
Det er en tabell med rader og kolonner som du kan åpne i et program som Excel,
eller Numbers på en Mac.
>> Og hvis jeg åpner denne filen her på gedit, varsel - og tallene er ikke der.
Det er gedit bare forteller meg linjenummer.
Legg merke på den første linje i denne filen er David og Mather.
Den neste linjen er Rob komma Kirkland.
Og den tredje linjen er Lauren komma Leverett.
>> Så hva har jeg laget?
Jeg har nå skrevet et C-program som effektivt kan generere regneark
som kan åpnes i en program som Excel.
Ikke alle som overbevisende et datasett, men hvis du har mye større biter av
data som du faktisk ønsker å manipulere og lage grafer av og
liker, er dette kanskje en måte å skape disse dataene.
Videre CSVs er faktisk super felles bare for lagring av enkle data -
Yahoo Finance, for eksempel, hvis du får aksjekurser via deres såkalte
API, gratis tjeneste som lar deg får strøm up-to-the-date lager
sitater for selskapene, de gi dataene tilbake i
super enkelt CSV-format.
>> Så hvordan gjorde vi det?
Vel merke, det meste av dette programmets nesten den samme.
Men legg merke til her nede, snarere enn ut elevene ut, på linje 35
framover, hevder jeg at jeg sparer den studenter til disk, så sparer en fil.
>> Så merker jeg erklære en FIL * -
nå, er denne typen av en anomali i C. For uansett grunn, er FIL alle caps,
som ikke er som de fleste andre datatyper i C. Men dette er en innebygd
datatype, FILE *.
Og jeg erklære en peker til en fil, er hvordan du kan tenke på det.
>> fopen betyr åpen fil.
Hvilken fil du vil åpne?
Jeg ønsker å åpne en fil som jeg vil vilkårlig ringe students.csv.
Jeg kan kalle det hva jeg vil.
>> Og deretter ta en gjetning.
Hva gjør det andre argumentet til fopen trolig bety?
Høyre, w for skriving, kunne være r for lese.
Det er en for append hvis du ønsker å legge til rader og ikke
overskrive hele greia.
>> Men jeg ønsker bare å opprette denne filen gang, så jeg skal bruke quote unquote w.
Og jeg vet at det bare fra å ha lest dokumentasjonen, eller mannen siden.
Hvis filen ikke er null - med andre ord, hvis noe gikk galt der -
la meg iterere over studenter 0-3.
>> Og nå merker det er noe aldri så litt annerledes
om linjen 41 her.
Det er ikke printf.
Det er fprintf for fil printf.
Så det kommer til å skrive til fil.
Hvilken fil?
Den ene som pekeren du angir som det første argumentet.
>> Da kan vi angi et format streng.
Da kan vi spesifisere hva strengen vi ønsker å plug in for første prosent s, og
deretter en annen variabel eller den andre prosent s.
Da vi lukke filen med fclose.
Enn jeg frigjøre minne som før, skjønt Jeg skal gå tilbake og legge
noen sjekker for null.
>> Og det er det.
fopen, fprintf, gir fclose meg evne til å skape tekstfiler.
Nå vil du se i oppgavesettet fem, som innebærer bilder, vil du skal bruke
binære filer i stedet.
Men fundamentalt, er tanken den samme, selv om funksjonene du vil
se er litt annerledes.
>> Så rask tur, men du vil få altfor kjent med fil I/O--
inngang og utgang - med PSett fem.
Og på spørsmål om innledende grunnleggende her?
Yeah?
>> Hva om du prøver å frigjøre en nullverdi?
Jeg tror, med mindre gratis har fått en litt mer brukervennlig, kan du
potensielt segfault.
Passerer det null er dårlig fordi jeg ikke tror gratis gidder å sjekke for deg,
fordi det ville potensielt være bortkastet tid for den å gjøre seg selv for
alle i verden.
Godt spørsmål, though.
>> Greit, så denne typen blir oss til et interessant tema.
Temaet for oppgavesettet fem er etterforskning.
Minst som er en del av problemet settet.
Forensics refererer vanligvis til gjenoppretting av informasjon som kan eller
kanskje ikke har blitt slettet bevisst.
Og så jeg tenkte jeg skulle gi deg en rask smak av hva som egentlig skjer hele
denne gang under panseret på datamaskinen.
>> For eksempel, hvis du har på innsiden av din bærbare eller stasjonære datamaskinen en
harddisk, er det enten en mekanisk enhet som faktisk spinner -
det er sirkulære ting som kalles fat som ser ganske like det jeg
bare hadde opp på skjermen her, skjønt dette er stadig gamle skolen.
Dette er en tre-og-en-halv-tommers harddisk.
Og tre og en halv inches refererer til med på ting når du installerer den
i en datamaskin.
>> Mange av dere gutta i din bærbare nå har SSD-disker eller SSD,
som ikke har noen bevegelige deler.
De er mer som RAM og mindre som disse mekaniske enheter.
Men ideene er fortsatt den samme, sikkert som de forholder
til problemet satt fem.
>> Og hvis du tenker på nå en harddisk representerer være en sirkel, som
Jeg skal tegne som dette her.
Når du oppretter en fil på datamaskinen, enten det er en SSD, eller i
dette tilfellet, en eldre skole harddisk, at filen består av flere biter.
La oss si at det er dette 0 og 1, en hel haug med 0'er og 1'ere.
Så dette er min hele harddisken.
Dette er tydeligvis en ganske stor fil.
Og det er å bruke opp 0'er og 1'ere på den del av den fysiske tallerken.
>> Vel, hva er det fysiske delen?
Vel, det viser seg at på en harddisk, i det minste av denne type, er det
disse bitte små magnetiske partikler.
Og de i hovedsak har nord og sør poler til dem, slik at hvis du
snu en av de magnetiske partiklene denne måten, kan du si at det er
representerer en en.
Og hvis det er opp ned sør til nord, kan du si at det er
representerer en 0.
>> Så i den virkelige fysiske verden, det er hvordan du kan representere noe i
binær tilstand av 0 og 1.
Så det er alt en fil er.
Det er en hel haug med magnetisk partikler som er deres denne måten, eller
på denne måten, skaper mønstre av 0'er og 1'ere.
>> Men det viser seg når du lagrer en fil, litt informasjon lagres separat.
Så dette er et lite bord, en katalog, så å si.
Og jeg skal kalle denne kolonnen navn, og Jeg vil kalle denne kolonnen plassering.
>> Og jeg kommer til å si, anta dette er min CV.
Min resume.doc lagres på plassering, la oss si 123.
Jeg går alltid for dette nummeret.
Men nok det å si at akkurat som i RAM, kan du ta en harddisk
det er en gigabyte eller 200 gigabyte eller en terabyte, og du kan
antall alle bytes.
Du kan telle alle biter av 8 bits.
>> Så vi vil si at dette er beliggenheten 123.
Så denne katalogen innsiden av drifts min Systemet husker at min
CV er på stedet 123.
Men det blir interessant når du sletter en fil.
>> Så for eksempel -
og heldigvis, har de fleste av verdens fanget inn dette - hva som skjer når
du drar en fil til Mac OS Trash eller Windows papirkurven?
Hva er hensikten med å gjøre det?
Det er åpenbart for å bli kvitt filen, men hva betyr det lov å dra og
slippe inn i papirkurven eller din Recycle Bin gjøre på en datamaskin?
>> Absolutt ingenting, egentlig.
Det er akkurat som en mappe.
Det er en spesiell mappe, for å være sikker.
Men betyr det faktisk slette filen?
>> Vel, nei, fordi noen av dere sikkert har vært som, oh faen, det gjorde du ikke
mener å gjøre det.
Så du dobbeltklikker på Papirkurven eller papirkurven.
Du har lett rundt, og du har gjenopprettet filen bare ved å dra den
ut av det.
Så klart, det er ikke nødvendigvis slette den.
>> OK, du er smartere enn som så.
Du vet at bare dra den inn i Trash eller papirkurven betyr ikke
du tømme papirkurven.
Så du går opp til menyen, og du sier Tøm papirkurv eller Tøm papirkurven.
Hva skjer da?
>> Ja, så det er slettes mer.
Men alt som skjer er dette.
Datamaskinen glemmer hvor resume.doc var.
>> Men hva har ikke forandret tilsynelatende i bildet?
Bitene, den 0'er og 1'ere som jeg hevder er på stedet av noen fysiske aspektet av
maskinvaren.
De er fortsatt der.
Det er bare at datamaskinen har glemt hva de er.
>> Så det er egentlig frigjort filens biter, slik at de kan brukes på nytt.
Men ikke før du oppretter flere filer, og flere filer, og flere filer vil
probabilistically, de 0'er og 1'ere, de magnetiske partikler, får gjenbrukt,
opp eller høyre side opp, for andre filer, 0'er og 1'ere.
>> Så du har dette vindu av tid.
Og det er ikke for forutsigbar lengde, egentlig.
Det avhenger av størrelsen på harddisken din stasjonen og hvor mange filer du har og
hvor raskt du lage nye.
Men det er dette vindu av tid under som at filen er fortsatt helt
gjenvinnbart.
>> Så hvis du noen gang bruke programmer som McAfee eller Norton å forsøke å gjenopprette
data, alt de gjør forsøk på å gjenopprette denne såkalte katalogen til
finne ut hvor filen var.
Og noen ganger Norton og vil si, Filen er 93% gjenvinnbare.
Vel, hva betyr det?
Det betyr bare at noen andre filer tilfeldigvis endte opp med, sier
de bitene ut av den opprinnelige filen.
>> Så hva er egentlig involvert i å gjenopprette data?
Vel, hvis du ikke har noe sånt Norton forhåndsinstallert på datamaskinen,
det beste du kan noen ganger gjøre er å se på hele harddisken på jakt etter
punktmønstre.
Og en av temaene i oppgavesettet fem er at du vil søke på
tilsvarer en harddisk, en rettsmedisinsk bilde av et Compact Flash-kort fra en
digitalkamera, søker etter 0s og 1s som typisk, med høy
sannsynlighet, representerer starten på et JPEG-bilde.
>> Og dere kan gjenopprette disse bildene ved forutsatt, hvis jeg ser dette mønsteret av
biter på den rettsmedisinske bilde, med høy sannsynlighet, som markerer
starten på en JPEG.
Og hvis jeg ser det samme mønsteret igjen, som markerer starten på sannsynligvis
annet JPEG, og en annen JPEG, og en annen JPEG.
Og dette er typisk hvordan data utvinning vil fungere.
Hva er fint om JPEG er selv om filformatet i seg selv er noe
kompleks, i begynnelsen av hver slik filen er egentlig ganske identifiserbare
og enkel, som du vil se, hvis du har ikke allerede.
>> Så la oss ta en nærmere *** under hetten som til nøyaktig hva som har vært
skjer, og hva disse 0'er og 1'ere er, for å gi deg litt mer av en
kontekst for denne utfordringen.
>> [VIDEOAVSPILLING]
>> -Hvor din PC lagrer mest av sine faste data.
For å gjøre det, reiser data fra RAM sammen med programvare signaler som forteller
harddisken hvordan å lagre disse dataene.
Harddisken kretser oversette disse signalene til spenning
svingninger.
Disse i sin tur, kontrollere harddiskens bevegelige deler, noen av de få
bevegelige deler igjen i moderne datamaskin.
>> Noen av de signaler som styrer en motor som spinner metall-belagt fat.
Dine data er faktisk lagret på disse platene.
Andre signaler flytte lese / skrive hoder til å lese eller
skrive data på platene.
Dette maskineriet så presis at et menneske hår ikke engang kunne passere mellom
hoder og spinning fat.
Likevel, det fungerer alt på kjempefint hastigheter.
>> [END VIDEOAVSPILLING]
>> DAVID MALAN: Zoom inn litt dypere nå på hva som er
faktisk på disse platene.
>> [VIDEOAVSPILLING]
>> -La oss se på hva vi nettopp så i slow motion.
Når en kort puls av elektrisitet er sendes til lese / skrive-hodet, hvis flipper
på en liten elektromagnetisk for en brøkdel av et sekund.
Magneten skaper et felt, som endrer polaritet av en bitteliten
del av de metallpartikler som frakk hver tallerken overflaten.
>> Et mønster serie av disse små, ladet opp områder på disken
representerer en enkelt bit av data i det binære tallet
system som brukes av datamaskiner.
Hvis nå strømmen sendes en vei gjennom lese / skrive-hodet, området
er polarisert i en retning.
Hvis strømmen blir sendt i motsatt retning,
polarisering er reversert.
>> Hvordan du får data fra harddisken?
Bare reversere prosessen.
Så det er partiklene på disken som får strømmen i
lese / skrive-hodet i bevegelse.
Sette sammen millioner av disse magnetisert segmenter, og
du har en fil.
>> Nå, biter av en enkelt fil kan bli spredt over et stasjonens
fat, type som rotet papirer på pulten din.
Så en spesiell ekstra fil holder styr hvor alt er.
Tror ikke du ønske du hadde noe sånt?
>> [END VIDEOAVSPILLING]
>> DAVID MALAN: OK, sannsynligvis ikke.
Så hvor mange av dere vokste opp med disse?
OK, så det er færre og færre hender hvert år.
Men jeg er glad du er minst kjent med dem, fordi dette og vår egen
bok demo, dessverre, er å dø en svært langsom død her av fortrolighet.
>> Men dette er hva jeg, i hvert fall, tilbake i videregående skole, brukte bruk for sikkerhetskopier.
Og det var fantastisk, fordi du kunne lagre 1,4 megabyte på
denne disken.
Og dette var det høy tetthet versjon, som indikert av HD, som har
noe som betyr at før dagens HD-videoer.
>> Standard tetthet var 800 kilobyte.
Og før det, var det 400-kilobyte disker.
Og før det, var det 5 og 1/4 tommers disker, som var virkelig floppy,
og litt bredere og høyere enn disse tingene her.
Men du kan faktisk se den såkalte floppy aspekt av disse diskene.
>> Og funksjonelt, de er faktisk ganske lik harddisker av ved
minst denne typen.
Igjen, SSD i nyere datamaskiner fungerer litt annerledes.
Men hvis du flytter den lille metal-kategorien, du kan faktisk se en liten informasjonskapsel,
eller tallerken.
>> Det er ikke metall som denne.
Dette er faktisk litt billigere plastmateriale.
Og du kan slags vrikke den.
Og du har slett bare tørkes av noen antall biter eller magnetiske partikler
fra denne disken.
>> Så heldigvis, det er ingenting på det.
Hvis den tingen er i veien - og dekke øynene og de av din nabo -
du kan bare slags trekke dette Hele kappe av sånn.
Men det er en liten fjær, så vær klar over at med øynene.
Så nå har du virkelig en diskett.
>> Og hva er bemerkelsesverdig om dette er at i så mye som dette er en
liten-skala fremstilling av en større harddisk, disse tingene er super,
super enkelt.
Hvis du klemme bunnen av det, nå som at metall ting er av, og skrell
dem åpne, er alt det er to stykker av filt og den såkalte diskett
med et stykke metall på innsiden.
>> Og det går halvparten av min disk innholdet.
Det går en halv av dem.
Men det er alt som var spinning inne av datamaskinen i en svunnen tid.
>> Og igjen, for å sette dette i perspektiv, hvor stor er det meste av din
harddisker i disse dager?
500 gigabyte, en terabyte, kanskje i en stasjonær datamaskin, to terabyte, 3
terabytes, 4 terabyte, ikke sant?
Dette er en megabyte, gi eller ta, som ikke selv passer en typisk MP3
lenger i disse dager, eller noen lignende musikkfil.
>> Så en liten suvenir for deg i dag, og også å bidra til å kontekstualisere hva
Vi skal ta for gitt nå i problemet satt fem.
Så de er ditt for alltid.
Så la meg overgang til der vil være tilbringe neste PSett også.
Så vi har nå satt denne siden for - oh, et par kunngjøringer raskt.
>> Denne fredagen, hvis du ønsker delta CS50 til lunsj, gå til den vanlige plassen,
cs50.net/rsvp.
Og endelig prosjekt -
så per pensum, har vi lagt ut siste prosjektet spesifikasjonen allerede.
Innse at det betyr ikke at det er på grunn særlig snart.
Det er lagt ut, egentlig, bare for å få dere tenke på det.
Og ja, en super betydelig prosentandel av dere vil bli taklinger
siste prosjekter på materiale som vi har ikke engang fått til i klassen,
men vil så tidlig som neste uke.
>> Legg imidlertid merke til at spesifikasjonen krever noen forskjellige komponenter i
endelige prosjektet.
Den første, i et par uker, er en pre-proposal, en ganske uformell e-post til
din TF å fortelle ham eller hva du er tenker for prosjektet, med
ingen forpliktelse.
Forslaget vil være din spesielle engasjement, sa her, dette er hva
Jeg ønsker å gjøre for mitt prosjekt.
Hva tror du?
For stor?
For liten?
Er det overkommelig?
Og ser du spec for flere detaljer.
>> Par uker etter at det er status rapporten, som er en tilsvarende
uformell e-post til TF for å si akkurat hvor langt bak du er i den endelige
prosjektets gjennomføring, etterfulgt av den CS50 Hackathon som alle
er invitert, som vil være en hendelse fra 20:00 på en kveld til 07:00
AM neste morgen.
Pizza, som jeg kanskje har nevnt i uken null, bli wil servert på 9:00,
Kinesisk mat på 1:00.
Og hvis du fortsatt er våken på 05:00, vi tar deg til IHOP for frokost.
>> Så Hackathon er en av de mer minneverdige opplevelser i klassen.
Da gjennomføringen skyldes, og da den klimatiske CS50 skyet.
Flere detaljer på samtlige av disse i ukene som kommer.
>> Men la oss gå tilbake til noe gamle skolen -
igjen, en matrise.
Så en matrise var hyggelig, fordi det løser problemer som vi så bare en
øyeblikk siden med student strukturer å få litt ut av kontroll hvis vi
ønsker å ha student en, student to, student tre, student dot dot dot,
noen vilkårlig antall studenter.
>> Så arrays, for noen uker siden, slo inn og løste alle våre problemer av ikke
vite på forhånd hvor mange ting av noen type kan vi ønsker.
Og vi har sett at structs kan hjelpe oss ytterligere organisere vår kode og holde
konseptuelt lignende variabler, som en navn og et hus sammen, slik at vi
kan behandle dem som en enhet, inne som det er mindre biter.
>> Men matriser har noen ulemper.
Hva er noen av ulempene vi har støtt på
med matriser så langt?
Hva er det?
Fast størrelse - så selv om du kanskje være i stand til å fordele minne for en
array, når du vet hvor mange studenter du har, hvor mange tegn du har
fra brukeren, når du har tildelt rekken, har du slags malt
selv inn i et hjørne.
>> Fordi du ikke kan sette inn nye elementer inn i midten av en matrise.
Du kan ikke sette inn flere elementer ved slutten av en matrise.
Virkelig, må du ty til å skape en helt ny array, som vi har diskutert,
kopiere den gamle til den nye.
Og igjen, er at hodepine som GetString avtaler med for deg.
>> Men igjen, du kan ikke engang sette inn noe inn i midten av matrisen
hvis prisen ikke er helt fylt.
For eksempel, hvis denne matrise av størrelse her seks har bare fem ting i det,
Vel, du kan bare tack noe mot slutten.
Men hva hvis du vil sette inn noe inn i midten av den
matrise, selv om det kan ha fem av seks ting i det?
>> Vel, hva vi gjør når vi hadde alle av våre frivillige på scenen i
uker tidligere?
Hvis vi ønsket å sette noen her, enten disse menneskene hvordan de skal flytte dette
måte, eller disse menneskene hvordan de skal flytte dette måte, og det ble dyr.
Skiftende av mennesker inne i en matrise endte opp med å legge opp og kostnadskalkyle
oss tid, derav mye av vår n kvadrat kjøretider som innsetting sortere, for
eksempel, i verste fall.
Så arrays er flott, men du må vet på forhånd hvor store du vil ha dem.
>> Så OK, her er en løsning.
Hvis jeg ikke vet på forhånd hvor mange studentene jeg kan ha, og jeg vet en gang
Jeg bestemmer meg, men jeg er stuck med det mange studenter, hvorfor gjør jeg ikke bare alltid
allokere dobbelt så mye plass som jeg kanskje tror jeg trenger?
Er det ikke en rimelig løsning?
>> Realistisk, tror jeg ikke at vi er kommer til å trenge mer enn 50 plasser
i en matrise for en middels stor klasse, så la oss bare runde opp.
Jeg skal lage 100 plasser i matrise min, bare slik at vi kan definitivt få
antall studenter jeg forventer å være i noen mellomstore klassen.
Så hvorfor ikke bare runde opp og fordele mer minne, typisk, for en matrise
enn du tror du kanskje trenger?
Hva er dette enkle pushback til at ideen?
>> Du bare sløse minne.
Bokstavelig talt hvert program du skriver deretter er kanskje å bruke dobbelt så mye minne som
du faktisk trenger.
Og det bare føles ikke som en spesielt elegant løsning.
Dessuten minsker det bare Sannsynligheten for et problem.
Hvis du tilfeldigvis har en populær kurs ett semester og du har 101
studenter, er programmet fortsatt fundamentalt overfor det samme problemet.
>> Så heldigvis, det er en løsning å denne annonsen alle våre problemer i form
av datastrukturer som er mer kompleks enn de
vi har sett så langt.
Dette, jeg hevder, er en lenket liste.
Dette er en liste med tall -
9, 17, 22, 26, og 34 -
som er koblet sammen ved hjelp av hva jeg har tatt som piler.
>> Med andre ord, hvis jeg ønsket å representere en matrise, kunne jeg gjøre
noe sånt som dette.
Og jeg skal sette dette på overhead på bare et øyeblikk.
Jeg kunne gjøre -
hallo, all right.
Stand by.
Ny datamaskin her, klar -
all right.
>> Så hvis jeg har disse tallene i array -
9, 17, 22, 26, 24 -
ikke nødvendigvis å skalere.
Ok, så her er min array -
oh my god.
Ok, så her er min array.
Oh my god.
>> [Latter]
>> DAVID MALAN: Pretend.
Det er for mye krefter på å gå tilbake og fikse det, så det -
26.
Så har vi denne matrisen av 9, 17, 22, 26, og 34..
For de av dere kan se pinlig tabbe jeg bare gjort,
det er det.
>> Så jeg påstå at dette er en svært effektiv løsning.
Jeg har tildelt så mange ints som Jeg trenger - en, to, tre,
fire, fem og seks -
og jeg har da lagret tallene innsiden av denne matrisen.
Men sett, så ønsker jeg å sette inn en verdi som nummer 8?
Vel, hvor det går?
Anta ønsker jeg å sette inn et tall som 20.
Vel, hvor det går?
Et sted der i midten, eller tallet 35 må gå
et eller annet sted på slutten.
Men jeg er alt for liten plass.
>> Og så dette er en grunnleggende utfordring av matriser som ikke er løsningen.
Jeg hevdet en stund siden, GetString løser dette problemet.
Hvis du vil sette inn en sjette nummer inn i denne matrise, hvilken er i det minste ett
løsning du kan falle tilbake på for sikker, akkurat som vi gjør med GetString?
Hva er det?
>> Vel, gjøre den større er lettere sagt enn gjort.
Vi kan ikke nødvendigvis gjøre matrisen større, men hva kan vi gjøre?
Lag en ny matrise som er større, av størrelse 6, eller kanskje størrelse 10, hvis vi ønsker
å komme i forkant av ting, og deretter kopiere den gamle matrisen i den nye, og deretter
frigjøre den gamle array.
>> Men hva er kjøretiden nå av denne prosessen?
Det er stor O n, fordi kopiering kommer til å koste deg noen enheter av
tid, så ikke så ideelt hvis vi må tildele en ny rekke, som kommer
å konsumere to ganger så mye minne midlertidig.
Kopier gamle til nye -
Jeg mener, det er bare en hodepine, som er, igjen, hvorfor vi skrev
GetString for deg.
>> Så hva kan vi gjøre i stedet?
Vel, hva om vår datastruktur faktisk har hull i det?
Anta at jeg slapp mitt mål om å ha sammenhengende biter av minne, der ni
er rett ved siden av 17, som er like ved 22, og så videre.
>> Og anta at 9 kan være over her i RAM og 17 kan være over her i RAM,
og 22 kan være over her i RAM.
Med andre ord, jeg trenger dem selv rygg til rygg lenger.
Jeg bare må liksom træ en nål gjennom hver av disse tallene, eller hvert
av disse nodene, som vi kaller rektangler som jeg har tegnet dem, til
huske hvordan du får til den siste slik node fra den første.
>> Så hva er programmering konstruere vi har sett ganske nylig som jeg
kan implementere den tråden, eller trukket her, som jeg kan
implementere disse pilene?
Så pekere, ikke sant?
Hvis jeg bevilge ikke bare en int, men en node - og ved
node, jeg mener bare container.
Og visuelt, mener jeg et rektangel.
Så en node trenger tydeligvis å inneholde to verdier -
den int seg selv, og da som følger av den nederste halvdelen av rektangelet,
nok plass til en int.
>> Så bare tenke fremover her, hvor stor er denne noden, dette
container i spørsmålet?
Hvor mange byte for int?
Antagelig 4, hvis det er det samme som vanlig.
Og deretter hvor mange byte for pekeren?
4.
Så denne beholderen, eller denne noden, er kommer til å være en 8-byte struktur.
Oh, og det er en lykkelig tilfeldighet at vi nettopp introdusert denne oppfatningen av
en struct, eller en C-struktur.
>> Så jeg påstår at jeg ønsker å ta et skritt mot dette mer sofistikerte
gjennomføring av en liste med tall, en lenket liste med tall, jeg trenger å gjøre en
litt mer tenkning opp foran og erklære ikke bare en int, men en struct
at jeg skal ringe, konvensjonelt her, node.
Vi kan kalle det noe vi ønsker, men node skal være tematisk i mange
av de tingene vi begynne å se på nå.
>> Innsiden av den noden er en int n.
Og så dette syntaks, litt merkelig ved første øyekast -
struct node * neste.
Vel billedlig, hva er det?
Det er den nedre halvdelen av rektangelet som vi så
bare et øyeblikk siden.
>> Men hvorfor jeg sier struct node * i motsetning til bare node *?
Fordi hvis det pekeren peker på en annen node, det er bare det
adressen til en node.
Som er i samsvar med det vi har diskutert om pekere så langt.
Men hvorfor, hvis jeg hevder denne strukturen er kalt node, må jeg si struct
node inni her?
>> Nettopp.
Det er liksom en dum virkelighet C. Den typedef, så å si, har ikke
skjedd ennå.
C er super bokstavelig.
Den leser koden topp til bunn, venstre til høyre.
Og inntil treffer det at semikolon på bunnlinjen, gjett hva som ikke
eksistere som en datatype?
Node, sitat unquote node.
>> Men på grunn av den mer utførlig Erklæringen jeg gjorde på første linje -
typedef struct node -
fordi det kom først, før klammeparentes, det er liksom som
pre-utdanne Clang at du Vet du hva, gi meg en struct
kalt struct node.
Ærlig talt, jeg liker ikke ringer ting struct node, struct node alle
hele koden min.
Men jeg skal bare bruke det en gang, rett innenfor, slik at jeg kan effektivt
skape en slags sirkulær referanse, ikke en peker til meg per se, men en
pekeren til en annen av en identisk type.
>> Så det viser seg at på en datastruktur som dette, det er noen
operasjoner som kan være av interesse for oss.
Vi ønsker kanskje å sette inn inn i en liste som dette.
Vi ønsker kanskje å slette fra en liste som dette.
Vi ønsker kanskje å søke i listen for en verdi, eller mer generelt, travers.
Og travers er bare en fancy måte å sier start på venstre og flytte alle
vei til høyre.
>> Og legg merke til, selv med dette litt mer sofistikerte data struktur, la
meg foreslå at vi kan låne noen av ideene til de siste to ukene og
implementere en funksjon som heter søke som dette.
Det kommer til å returnere true eller falsk, som indikerer, ja eller
nei, er n i listen.
Sin andre argument er en peker til listen selv, slik at en
peker til en node.
>> Alt jeg skal da gjøre er å erklære en midlertidig variabel.
Vi kaller det ptr av konvensjonen, for pekeren.
Og jeg tilordne den lik begynnelsen av listen.
>> Og nå merke til mens loop.
Så lenge pekeren er ikke lik til null, kommer jeg til å sjekke.
Er Pekerpilen n lik n som ble vedtatt i?
Og vent litt - ny stykke syntaks.
Hva er pilen plutselig?
Yeah?
>> Nettopp.
Så mens noen minutter siden, brukte vi dot notasjon for å få tilgang til noe
innsiden av en struct, hvis den variable du har ikke den struct
seg selv, men en peker til en struct, heldigvis, et stykke syntaks som
endelig gjør intuitiv følelse.
Pilen betyr å følge pekeren, som våre piler vanligvis bety
billedlig, og gå på data felt inne.
Så pilen er det samme som prikk, men du bruke den når du har en peker.
>> Så bare for å gjenerobre da, hvis n-feltet innsiden av struct kalles pekeren
lik lik n, returnere true.
Ellers denne linjen her - pekeren tilsvarer markøren ved siden.
Så hva dette gjør, varsel, er hvis jeg er for tiden peker på struct
inneholdende 9, og 9 er ikke antallet Jeg ser etter - antar jeg ser
for n tilsvarer 50 -
Jeg kommer til å oppdatere min midlertidig pekeren å ikke peke på denne noden
lenger, men peker pilen ved siden av, som kommer til å sette meg opp her.
>> Nå innså jeg er en virvelvind introduksjon.
På onsdag skal vi faktisk gjøre dette med noen mennesker, og med litt mer
koden på et langsommere tempo.
Men skjønner, er vi nå gjøre våre data strukturer mer komplisert, slik at våre
algoritmer kan få mer effektive, noe som kommer til å være nødvendig for
seks PSett, når vi legger i igjen, de 150 000 ord, men trenger å gjøre det
effektivt, og ideelt, skape en program som kjører for våre brukere ikke er i
lineære, ikke i N kvadrat, men i konstant tid, i det ideelle.
>> Vi ser deg på onsdag.
>> SPEAKER: Ved neste CS50, David glemmer sin base case.
>> DAVID MALAN: Og det er hvordan du sender tekstmeldinger med C. Hva i -
>> [DIVERSE TEKSTMELDING Varslingslydene]