[Powered by Google Translate] [Afsnit 4] [mindre behagelig] [Nate Hardison] [Harvard University] [Dette er CS50.] [CS50.TV] 

Okay, velkommen tilbage til afsnittet. I denne uges afsnit vil vi gøre et par ting. Vi skal til første opsummere Problem Set 2, som er Cæsar og Vigenère problem sæt. Og så vil vi dykke ned i Quiz 0 anmeldelse og tilbringe en lille smule tid slidbanepålægning hvad vi har talt om i hvert af de foredrag hidtil, og vi vil også gøre et par problemer fra sidste års quizzer. På den måde du fyre har en god måde at forberede sig til det. 

For at starte, jeg har startet op et par gode løsninger for det foregående problem sæt, Set Problem 2, ind i dette rum. Hvis du fyre alle ramt dette link, og hvis du klikker på mit navn, og klik på min første revision vil du se caesar.c, hvilket er præcis, hvad jeg ser på. Lad os tale om det virkelig hurtigt. Dette er blot en prøveopløsning. Dette er ikke nødvendigvis den perfekte løsning. Der er mange forskellige måder at skrive dette, men der er et par ting, jeg ønskede at fremhæve , som jeg så, da jeg var klassificering, almindelige fejl, som jeg tror denne løsning gør et godt stykke arbejde med håndtering. 

Den første er at have en form for header kommentarer på toppen. På linje 1 til 7 du se detaljerne, hvad dette program gør. En god standard praksis, når du skriver C-kode uanset om dit program er indeholdt i en enkelt fil eller uanset om det er delt over flere filer, er at have en form for orientering kommentarer på toppen. Dette er også for folk, der går ud og skrive kode i den virkelige verden. Det er her, de vil lægge oplysninger om ophavsret. Nedenfor er den # omfatter. På linie 16 er der denne # define, som vi vil vende tilbage til i bare en smule. Og derefter en gang funktionen starter, når de vigtigste starter, fordi dette program er blevet alle indeholdt i en enkelt funktion den allerførste ting, der sker, og det er meget idiomatisk og typisk for et C-program der tager i kommandolinjeflag-er, at den straks tjekker 

for argumentet tæller,. argc Lige her ser vi, at dette program forventer 2 argumenter nøjagtigt. Husk der er det første argument, der er den særlige en det er altid navnet på det program, der bliver kørt, navnet på den eksekverbare fil. Og så hvad det gør, er det forhindrer brugeren i at køre programmet med flere eller færre argumenter. Årsagen til at vi ønsker at tjekke for denne ret væk er fordi Vi kan faktisk ikke få adgang til denne argv opstilling lige her pålideligt indtil vi har tjekket for at se, hvor stor den er. 

En af de almindelige fejl jeg så var folk ville straks gå i og grab argv [1]. De havde fat i nøglen argument ud af arrayet og har den en for jeg kontrollere det, og så de ville gøre testen for argc samt den næste test, hvorvidt det første argument var faktisk et helt tal på samme tid, og det ikke virker, fordi der i det tilfælde, at der ikke er nogen leverede argumenter du skal snuppe et argument, der ikke er der, eller forsøger at få fat i en, der ikke er der. 

Den anden store ting, du bør bemærke, er, at du altid ønsker at udskrive en slags nyttige fejlmeddelelse for brugeren at orientere dem. Jeg er sikker på du har alle run programmer, hvor alle af en pludselig det går ned, og du får denne latterlige lille dialogboks, der popper op og siger noget forfærdeligt kryptisk og måske giver dig en fejlkode eller noget i den retning Det giver ingen mening. Det er her, du virkelig ønsker at give noget nyttigt og målrettet til brugeren, så når de kører det de går "Oh," ansigt håndflade. "Jeg ved præcis, hvad de skal gøre. Jeg ved, hvordan man kan løse dette." 

Hvis du ikke udskrive en besked, så du ender faktisk forlader brugeren til at gå undersøge din kildekode at finde ud af hvad der gik galt. Der er også nogle gange, at du skal bruge forskellige fejlkoder. Her har vi bare brugt en til at sige, at der var en fejl, der opstod en fejl, der opstod en fejl. Større programmer, ofte programmer, der kaldes af andre programmer, vil returnere en slags specielle fejlkoder i forskellige scenarier til programmering kommunikere hvad du ellers ville bare bruge en dejlig engelsk besked til. Cool. Når vi arbejder ned, kan du se, at vi trækker nøglen ud. Vi tester for at se om nøglen passer. Vi får en besked fra brugeren. Grunden til at vi gør det i dette do while løkke-og det er noget, vi vil dække i en lille smule-men det viser sig, at hvis du skriver kontrol D når du får at GetString prompt på terminalen hvad det egentlig gør, er det sender et specialtegn til programmet. Det hedder ELF eller slutningen af ​​filen karakter. Og i så fald, vil vores budskab strengen være null, så dette var ikke noget, vi kontrolleres for i opgaven sat sig. 

Men da vi går videre, nu hvor vi er begyndt at tale om pointers og dynamisk allokering af hukommelse på heapen, kontrol af null, når du har en funktion, der kunne returnere null som en værdi er noget, du ønsker at få for vane at gøre. Det er her primært til illustration. Men når du kan se GetString i fremtiden, så fra Problem Set 4 om, vil du ønsker at holde dette i tankerne. Igen, dette er ikke et problem for Problem Set 3 enten fordi vi ikke havde dækket det endnu. Endelig vil vi komme til denne del, hvor vi komme til den vigtigste krypterings loop, og der er et par ting der foregår her. Først skal vi gentage over hele meddelelsen strengen selv. Her har vi holdt strlen opkald i den stand, som nogle af Dem har påpeget, er ikke en god vej at gå. Det viser sig i dette tilfælde er det heller ikke stor, dels fordi vi ændre indholdet af selve meddelelsen inde i for-løkken, så hvis vi har et budskab, der er 10 tegn lang, første gang vi starter at for-løkke strlen vil vende tilbage hvad? 10. 

Men hvis vi så ændre budskab, siger vi ændre sin 5 karakter, og vi smider i et \ 0 tegn i 5. position, på en efterfølgende iteration strlen (message) returnerer ikke hvad den gjorde den allerførste gang, vi gentog, men det vil i stedet returnere 5, fordi vi kastede i det null terminator, og strengens længde er defineret ved placeringen af ​​det \ 0. I dette tilfælde er det en fantastisk måde at gå, fordi vi ændre det på plads. Men du opdager, at dette er faktisk overraskende nemt at kryptere hvis du kan få det math korrekte. Det eneste, der kræves, er at kontrollere, om det brev, som du kigger på er store eller små bogstaver. 

Grunden til at vi kun nødt til at tjekke for det, og vi behøver ikke at tjekke for det er alpha tilfældet er, hvis en karakter er store eller hvis det er små så er det absolut et bogstav, fordi vi ikke har store og små cifre. Den anden ting, vi gør-og det er lidt tricky, er vi har ændret standard Cæsar cipher formel at vi gav i problemet indstillede specifikation. Hvad er anderledes her er, at vi fratrækkes i det store sag kapital A, og så har vi tilføjet kapital A tilbage i slutningen. 

Jeg kender et par af jer har gjort dette i din kode. Har nogen af ​​jer gøre dette i dit indlæg? Du gjorde det. Kan du forklare, hvad dette betyder, Sahb? Ved at trække det ud, fordi du gjorde en mod lige efter det, du nødt til at tage det ud, så på den måde får du [hoste] position. Og så ved at tilføje det igen senere du skiftet over den, du ønskede. Ja, præcis. Hvad Sahb sagde, var, at når vi ønsker at tilføje vores budskab og vores nøgle sammen og derefter mod at, mod at ved NUM_LETTERS, hvis vi ikke skalere vores budskab i den passende 0 til 25 rækkevidde først, så vi kan ende med at få en virkelig underlig nummer fordi de værdier, vi kigger på når vi ser på besked [i], når vi ser på den i'te karakter af vores almindelig SMS-besked, er en værdi et eller andet sted i dette 65-122 interval baseret på de ASCII værdier for store bogstaver A gennem små z. Og så når vi at moder det ved 26 eller ved NUM_LETTERS, da det var vores # define øverst til højre op her, der kommer til at give os en værdi, der er i 0 til 25 rækkevidde, og vi har brug for en måde at derefter skalere den tilbage op og få det i den relevante ASCII rækkevidde. Den nemmeste måde at gøre det er at bare skalere alting ned i 0-25 interval til at begynde med, og derefter flytte alt tilbage op i slutningen. 

En anden almindelig fejl, at jeg så folk løber ind i, er, at hvis du ikke rent faktisk gør dette skalering med det samme og du tilføjer besked og tast sammen, og du tilføjer dem, siger, i en char variabel, problem med at er da budskab [i] er et relativt stort antal til at begynde med, husk det er mindst 65, hvis det er et stort bogstav- hvis du har en stor nøgle, siger, noget i retning af 100, og du tilføje dem 2 sammen ind i en underskrevet char du kommer til at få et overløb. Du kommer til at få en værdi, der er større end 127, som er den største værdi, som en char variabel kan holde. Igen, det er derfor du gerne vil gøre den slags ting til at begynde med. Nogle mennesker fik omkring denne sag ved at gøre en hvis ellers og afprøvning at se, om det ville overflow før du gør det, men på denne måde får omkring det. Og så i denne opløsning vi udskrevet hele strengen til allersidst. Andre mennesker udskrives et tegn ad gangen. Begge er awesome. På dette tidspunkt, har du fyre har spørgsmål, bemærkninger om dette? Ting du gerne, ting du ikke kan lide? 

Jeg havde et spørgsmål. Måske jeg savnede det under din forklaring, men hvordan fungerer dette program springe rum til tilslutning af nøglen til længden af ​​teksten? Dette er blot Cæsar cipher. >> Åh, undskyld, ja. Ja, det vil vi se, at. I Caesar cipher vi fik omkring, at fordi vi kun vendt tegn. Vi kun drejet dem, hvis de var store eller små bogstaver. Du fyre følelse temmelig godt om dette? Du er velkommen til at kopiere dette hjem, tage det, sammenligne det med hvad du fyre skrev. Absolut velkommen til at sende spørgsmål om det også. Og igen, indse, at målet her med dit problem sætter er ikke at få jer til at skrive perfekt kode til dit problem sæt. Det er en lærerig oplevelse. Yeah. 

Tilbage til do while-løkken, hvis det er lig nul, så null betyder bare ingenting, de bare tryk enter? Null er en særlig pointerværdi, og vi bruger null, når vi ønsker at sige vi har en pointer variabel, der peger på noget. Og så typisk betyder det, at denne variabel, denne besked variabel er tom, og her, fordi vi bruger CS50 speciel streng type, hvad er den CS50 streng type? Har du set, hvad det er, når David trukket tilbage hætten i foredraget? Det er en funky-det er en pointer, ikke? Okay, ja. >> Det er en char *. Og så virkelig vi kunne erstatte denne lige her med char * besked, og så GetString funktion, hvis det ikke lykkes at en snor fra brugeren, det kan ikke parse en streng, og det ene tilfælde, hvor det ikke kan parse en streng er, hvis brugeren skriver i slutningen af ​​filen karakter, kontrol D, der er ikke noget man typisk gør, men hvis det sker så funktionen vil returnere dette null værdi som en måde at sige "Hey, jeg fik ikke en streng." Hvad ville der ske, hvis vi ikke sætter besked = null, hvilket er noget, vi ikke har gjort endnu? Hvorfor ville det være et problem her? Fordi jeg ved, at vi snakkede lidt i foredrag om memory leaks. Ja, lad os gøre det, og lad os se hvad der sker. 

Basil spørgsmål var, hvad der sker, hvis vi faktisk ikke har denne besked = null test? Lad os rulle op til toppen. I fyre kan kommentere dette. Faktisk vil jeg gemme det i en revision. Dette vil være Revision 3. Hvad du nødt til at gøre for at køre dette program er du nødt til at klikke på dette gear ikon op her, og du bliver nødt til at tilføje et argument til det. Du bliver nødt til at give det afgørende argument, da vi ønsker at passere i en kommandolinje argument. Her vil jeg har tænkt mig at give det et nummer 3. Jeg kan godt lide 3. Nu zoomer ud igen, kører programmet. Det kører, kompilering, bygning. Her går vi. Det venter på at blive spurgt. Hvis jeg skriver i noget lignende hello-hvor gik det? Åh, mit program tog for lang tid at køre. Jeg var jawing for længe. Her går. Nu skriver jeg i hej. Vi ser, at den krypterer korrekt. Nu, hvad der sker, hvis vi ikke gør hurtig GetString at returnere null? Husk, jeg sagde, at vi gjorde det ved at trykke på kontrol D på samme tid. Jeg rulle op her. Vi vil køre det igen. Building. Der det går. Nu når jeg ramte kontrol D Jeg fik denne linje, der siger opt/sandbox50/bin/run.sh, Segmentation fault. Har du fyre set det før? 

[Student] Hvorfor er der ingen >> Undskyld? [Student] Hvorfor er der ingen kerne-dump i dette tilfælde? Kernen dump er-spørgsmålet er, hvorfor er der ingen kerne-dump her? Spørgsmålet er, at der kan være, men kernen dump er en fil der bliver gemt på harddisken. I dette tilfælde har vi deaktiveret kerne lossepladser på flugt serveren, så vi ikke har folk seg fejlagtigt og opbygge tonsvis af centrale lossepladser. Men du kan få en. Core dumps er den slags ting, som du ofte kan deaktivere, og nogle gange du gør. Den segmentering fejl, at besvare dit spørgsmål, Basil, siger, at vi har forsøgt at få adgang til en pegepind der var ikke sat til at pege på noget som helst. Husk Binky i videoen, når Binky forsøger at gå adgang til en pointer, der er ikke peger på noget? I dette tilfælde vil jeg gætte teknisk markøren peger på noget. Det peger på null, der er teknisk 0, men der er defineret til at være i et segment, som ikke er tilgængelige af dit program, så du får en segmenteringsfejl fordi du ikke får adgang til hukommelse, der er i en gyldig segment som dyngen segment eller stakken segment eller datasegment. Cool. Har du flere spørgsmål om Caesar? 

Lad os komme videre. Lad os se på Revision 2 virkelig hurtigt. Det er Vigenère. Her i Vigenère vil vi gå gennem denne ene temmelig hurtigt, fordi, igen, Vigenère og Cæsar er temmelig ens. Header kommentar er før, # Define er før at undgå at bruge disse magiske tal. Det gode er at sige vi ønskede at flytte til et andet alfabet eller noget lignende. Snarere end at skulle gå manuelt ændre alle 26 er i koden vi kunne ændre dette til 27 eller drop det ned hvis vi bruger forskellige alfabeter, forskellige sprog. Igen har vi denne kontrol af argumentet tæller, og virkelig du kan næsten tage dette som en skabelon. Stort set alle program, du skriver bør have- hvis det tager kommandolinjeargumenter-nogle sekvens af linjer , der lyder sådan her i begyndelsen. Det er en af ​​de første tilregnelighed test, du vil gøre. 

Her hvad vi gjorde, var vi sørget for, at søgeordet var gyldig, og det var den anden kontrol, som vi gjorde. Bemærk igen, at vi adskilt denne fra argc og 2. Bemærk, at i dette tilfælde én ting, vi skulle gøre, var i stedet for at bruge en til jeg vi ønskede at validere hele strengen, og for at gøre, at du rent faktisk nødt til at gå tegn for tegn over strengen. Der er ingen god måde at kalde noget om det fordi selv, for eksempel A til I returnerer 0 hvis det ikke kan parse et heltal, så der ikke engang virker. Igen, nice meddelelse til brugeren præcis hvad der skete. Så her, igen, vi også håndtere de tilfælde, hvor brugeren skriver i en kontrolgruppe D tilfældig karakter. 

Og så Charlotte havde et spørgsmål tidligere om, hvordan vi formår at springe rum i vores streng her. Det var slags svarer til, hvad vi gjorde med Myspace program at vi gjorde i snit, og den måde det fungerede er, at vi sporede antallet af bogstaver, som vi havde set. Da vi gik over den besked streng, da vi gik over tegn for tegn, Vi sporede indekset som del af vores for-løkke, og så har vi også spores antallet af bogstaver, så ikke-specialtegn, ikke-tal, ikke-blanktegn at vi havde set i den separat variabel. Og så denne løsning ændrer nøglen at få en nøgle tal, og det gør, at der på den flue, lige før det går så til at kryptere selve budskabet karakter. Der er nogle løsninger, der var helt store også der ville ændre nøglen op ved test for knappens gyldighed. Ud over at sørge for, at tegnet og søgeordet blev et bogstav det også slået det ind i et heltal i 0 til 25 sortimentet derefter springe skulle gøre det senere i denne for-løkke. Igen, du ser her er det virkelig den nøjagtig samme kode som vi anvendte i Caesar på dette tidspunkt. Du gør præcis de samme ting, så det virkelige trick er at finde ud hvordan man kan slå søgeordet i et heltal. 

En ting, som vi gjorde her, er en lille tæt er vi gentaget denne sætning, jeg gætte, du kan kalde det, 3 separate gange på linjerne 58, 59, og 61. Kan nogen forklare, hvad der præcist denne sætning betyder? Det er adgang til en karakter, som du sagde. Ja, det er [uhørligt] et tegn i søgeordet, og så det er antallet af sete bogstaver, fordi du kun bevæger sig langs søgeordet når du har set brevet, så der kommer til at effektivt at springe rum og den slags. Ja, præcis. Og så når du har set søgeordet blank du bare mod, så du flytter tilbage omkring. Præcis. Det er en perfekt forklaring. Hvad Kevin sige er, at vi ønsker at indekset i søgeordet. Vi ønsker at få den num_letters_seen karakter, hvis du vil, men hvis num_letters_seen overskrider længden af ​​søgeordet, den måde, vi kommer tilbage til det passende område er vi bruge mod operatøren til effektivt at ombryde omkring. For eksempel, som på kort vores søgeord er bacon, og det er 5 bogstaver. Men vi har set 6 bogstaver i vores klartekst på dette punkt og krypteret 6. Vi vil ende med at få adgang til num_letters_seen, som er 6, mod længden af ​​nøgleord, 5, og så vil vi få 1, og så hvad vi vil gøre, er at vi får åbne det første tegn indersiden af ​​vores nøgleord ved dette punkt. 

Okay, eventuelle spørgsmål om Vigenère før vi går videre? Du fyre følelse temmelig godt om dette? Cool, stor. Jeg vil være sikker på, at du fyre får chancen for at se koden at vi synes ser godt og har chancen for at lære af det. Dette vil være det sidste, vi kommer til at bruge mellemrum for tiden, og vi vil overgangen nu, og jeg har tænkt mig at gå til cs50.net/lectures så vi kan gøre en lille smule af quiz gennemgang. Den bedste måde jeg tror at begynde at gøre quiz anmeldelse er at komme til denne Forelæsninger side, cs50.net/lectures, og under hver af de uger overskrifter, så hvis jeg ser her i uge 0, Jeg kan se, at vi har en liste over emner, som vi dækket i uge 0. 

Hvis nogen af ​​disse emner synes ukendte for dig du vil helt sikkert ønsker at gå tilbage og gennemsøge forelæsningsnoter og eventuelt selv skimme gennem foredrag, se dem igen, hvis du ønsker at få en fornemmelse for, hvad der sker med hver enkelt af disse emner. Jeg vil sige yderligere i år en af ​​de seje ressourcer, vi har fået er disse shorts, som vi har oprettet, og hvis man ser på uge 0, vi har ikke alle, der er omfattet af de emner, men vi har fået en hel del af dem, nogle af de mere vanskelige dem, så ser disse shorts igen er en god måde at få dig op i fart. I særdeleshed vil jeg sætte i en plug til 3 på bunden, da jeg gjorde dem. Men hvis du kæmper med binær, bits, hex, den slags ting, binær er et godt sted at starte. ASCII er en anden en, der er god til at se også. Du kan endda se mig på 1,5 x hastighed, hvis jeg går for langsomt for dig. Da det er gennemgang, er du velkommen til at gøre det. 

Blot for at starte virkelig hurtigt, vi kommer til at gå igennem et par af disse quiz problemer lige hurtigt churn gennem disse. For eksempel, lad os se på problemet 16, at jeg har lige her oppe på tavlen. Vi har fået dette følgende beregning i binær, og vi ønsker at vise noget arbejde. Okay, jeg vil give denne et skud. I gutter bør følge sammen med papir, og vi vil gøre det virkelig hurtigt. Vi ønsker at udføre følgende beregning i binær. Jeg har 00.110.010. Og jeg har tænkt mig at tilføje til det 00.110.010. For matematiske genier efter sammen derhjemme, Dette er effektivt gange med 2. Lad os starte. Vi kommer til at følge samme tilsætning algoritme, at vi gør når vi tilføjer decimaltal sammen. Virkelig den eneste forskel her er, at vi løkke tilbage omkring når vi har 1 + 1 i stedet for når vi kommer til 10. 

Hvis vi starter fra højre, virkelig hurtigt, hvad er det første ciffer? [Student] 0. >> [Nate H.] 0. Store, det andet ciffer? [Student] 1. [Nate H.] Er det en 1? 1 + 1? [Student] 10. [Nate H.] Præcis, så hvad er det ciffer, jeg skriver lige under de 2 dem lægges sammen? [Student] 1, 0 eller 0 og derefter bære 1. [Nate H.] 0 og bære et 1, præcis. Næste en op, Basil, du er oppe. Hvad er den tredje? >> [Basil] 1. [Nate H.] 1, perfekt. Kevin? [Kevin] 0. >> [Nate H.] 0, Charlotte? [Charlotte] 0. >> [Nate H.] Ja, og hvad gør jeg? [Student] The 1. [Nate H.] Og hvad skal jeg gøre? Og så kan jeg bære den 1. Perfekt, Sahb? >> [Sahb] Nu har du 1. [Nate H.] Og gør jeg noget her? [Sahb] Så for det næste du har 1, fordi du gennemførte over 1. [Nate H.] Godt, så her kan vi afslutte det op. Cool. [Student] Har 0 + 0 = 0? 0 + 0 = 0. 1 + 1, som du sagde, er 10 eller 1, 0, snarere. 10 er en misvisende, fordi for mig 10 betyder tallet 10, og det er den ejendommelighed, hvordan vi repræsenterer det, når vi skriver det. Vi repræsenterer tallet 2 med 1, 0, og antallet 10 er en smule anderledes. 

Hvad er lidt rart, om binære er, at der virkelig er ikke så mange sager, du har brug for at lære. Der er 0 + 0 = 0, 0 + 1 = 1, 1 + 1 er 0, og så foretage et 1, og så kan du se her på den tredje kolonne fra højre Vi havde denne 1, 1 og 1. Og 1 + 1 + 1 er et 1, og du bære en anden 1. Når du laver binær desuden ret simpelt. Jeg ville gøre et par mere af disse til tilregnelighed kontrollere jer selv før du går i, fordi det er sandsynligvis noget, som vi vil se på quizzen. Lad os nu gøre det næste en så godt. Lad os gøre problem 17. Vi kommer til at konvertere følgende binære tal til decimal. Jeg har 10100111001. Husk i det binære video, som jeg gjorde Jeg gik gennem et par eksempler, og jeg viste, hvordan alt fungerer, når du laver det i decimal. Når du arbejder i decimal repræsentation jeg tror, ​​vi er på dette tidspunkt i vores liv, så flydende i det at det er ret nemt at tilsløre mekanik, hvordan det rent faktisk virker. 

Men for at gøre en hurtig opsummere, hvis jeg har det nummer 137 det virkelig betyder-og igen, dette er i decimal repræsentation- nummeret 137 i decimal betyder, at jeg har 1 x 100 + 3 x 10 + 7 x 1. Dette er så opholder sig på skærmen. Og så hvis man ser på disse tal lige her, 100, 10 og 1, kan du se, at de er faktisk alle potenser af 10. Jeg har 10 ², 10 ¹, og 10 til nul. Vi har en lignende slags ting i binær, bortset fra at vores base, som vi kalder det, er 2 i stedet for 10. Disse 10'erne, som jeg skrev ned her i bunden, denne 10 ², 10 ¹, 10 til nul, 10 er vores base, og eksponenten, 0, 1, eller 2, kan udledes af positionen af ​​det ciffer i det tal, vi skriver. 1, hvis vi ser på det, denne 1 er i 2. position. The 3 er i 1. positionen, og 7 er i 0. Position. Det er, hvordan vi får de forskellige eksponenter nedenfor for vores baser. 

Efter alt dette we'll-faktisk, ved du hvad? Vi vil gøre, hvor har min fortryd knap hen? Der det går. Jeg elsker denne fortryde ting. Efter denne jeg tror for mig i det mindste den nemmeste måde at begynde at konvertere et binært tal eller et hexadecimalt tal, hvor basen er 16 og ikke 10 eller 2 er at gå videre og skrive ud grundlaget og eksponenter for alle numrene i mit binære tal øverst. Hvis vi starter fra venstre til højre igen, som er lidt ulogisk, Jeg skifter tilbage til sort her, vi har 2 til den 0:e position, og så har vi 2 ¹, 2 ², og derefter 2 til 3, 2 til 4, 2 til 5, 6, 7, 8, 9 og 10. Disse tal jeg har skrevet ud, er alle eksponenter. Jeg kun skrev baser her i de første 3 bare for rummet. 

På dette punkt, jeg har tænkt mig at gå videre, og jeg faktisk kommer til at slette de ting, vi gjorde i decimal, hvis det er okay. Du har alle fået det. De af jer, se online jeg er sikker på vil være i stand til at spole tilbage mig, hvis du har lyst. Skift tilbage til pennen. Nu, hvad vi kan gøre,-hvis du fyre ikke er helt op til hastighed på dine kræfter på 2, det er helt cool. Det sker. Jeg forstår. Jeg havde engang en jobsamtale, hvor jeg fik at vide, jeg skulle kende alle potenser af 2 op gennem 2 til d.30. Det var ikke et job, jeg fik. Anyway, kan du fyre gå videre og gøre det math her, men med binær det ikke rigtig mening, og heller ikke mening med decimal eller hexadecimale enten, at gøre det math ud af, hvor du har nuller. Du kan se jeg har 0 her, en 0 her, 0 her, 0 her, 0 her, 0 her. Hvorfor kan det ikke mening at gøre det faktiske math til at beregne den relevante potens af 2 for denne holdning? Præcis ligesom Charlotte sagde, vil det være 0. Kan lige så godt spare dig tid, hvis beregningen potenser af 2 ikke er din stærke trop. I dette tilfælde behøver vi kun at beregne det for 2 til 0, hvilket er-? [Student] 1. [Nate H.] 1, 2 til 3, som er-? [Student] 8. >> [Nate H.] 8. 2 til 4? [Student] 2. Jeg er ked af, 1. [Nate H.] 2 til 4 er 16, præcis. 2 til 5, Kevin? >> 32. [Nate H.] 32, 2 til 8? [Student] 32 x 8, 256. [Nate H.] Perfect. Og 2 til 10? [Student] 1024. [Nate H.] Yeah, 1024. 

Når vi har fået disse tal kan vi sammenfatte dem alle op. Og det er her, det er virkelig vigtigt at gøre et par ting. Den ene er at gå langsomt og tjek dit arbejde. Du kan fortælle, at der er en 1 i slutningen af ​​dette nummer, så jeg burde helt sikkert få et ulige antal som mit resultat, fordi alle de andre dem vil være lige numre da det er et binært tal. Den anden ting at gøre, er, hvis du kommer til dette punkt på prøve og du har skrevet det ud så langt og du kører ud af tid se på det antal point, at dette problem er værd. Dette problem, som du kan se, hvis jeg vende tilbage til min laptop virkelig hurtigt- dette problem er værd 2 point, så dette er ikke den form for tilsætning du skal gå igennem, hvis du virkelig er presset på for tiden. Men vi vil skifte tilbage til iPad, og vi vil gå igennem det virkelig hurtigt. 

Jeg kan godt lide at gøre de små tal 1:e fordi jeg synes, at lettere. Jeg kan godt lide 32 og 8, fordi de går sammen temmelig let, og vi får 50. 16 og 1 får 17. Der får vi 57, og så kan vi gøre resten af ​​dette, så vi kan gøre 57, 156. Kom nu. Mand, ja, lad os se. Vi havde 57, 256, og 1024. På dette tidspunkt ville jeg hellere bare gå igennem. Jeg har ingen anelse. Jeg har helt klart brug for at læse op på dette. 7, 6 og 4, får du 17. 1, 5, 5, 2, 13. Derefter får vi 3, og så får vi 1. 1337. Påske æg, nogen? Nogen genkende dette nummer? Chris genkender nummeret. Hvad betyder det, Chris? [Chris] Leet. Leet, så hvis du ser på det, det ligner leet. Hacker stuff. Hold øje med den slags ting om midtvejsrevisionen eller quiz, snarere. Hvis du ser den slags ting, og du spekulerer "Huh," , som rent faktisk betyder noget. Det ved jeg ikke. David kan godt lide at sætte det i. Det er en god måde at tilregnelighed kontrollere det. Ligesom okay, kan jeg se, hvad der foregår. 

Det er Week 0/Week 1 ting. Hvis vi skifter tilbage til vores bærbare nu, zoome ud, og et par andre ting. Der er ASCII, som vi har gjort en masse af med problemet sæt. Denne opfattelse af kapital A. Hvad er det egentlig? Vel vidende at det er den decimale heltal. 65 er hvad det er kortlagt i ASCII-tabellen, og det er derfor, hvordan computeren skriver det, og det er, hvordan vi har været at få væk med rent faktisk at skrive tegnet kapital A og karakteren små bogstaver en i nogle af disse løsninger og problematiske sæt, som du har gjort. Et par andre ting. Vi har udsagn, boolske udtryk, betingelser, løkker, variabler og tråde. 

De, der alle synes at give mening for det meste? Noget af denne terminologi er lidt funky til tider. Jeg kan godt lide at tænke på en erklæring, som for det meste noget, der slutter med et semikolon. Udtalelser såsom x = 7, som fastsætter en variabel, formentlig kaldet x = 7. Antagelig x er også en type, der kan gemme nummeret 7, så det er en int eller eventuelt en float eller en kort eller en char, noget lignende. En boolean udtryk bruger disse dobbelt lig og bang lig eller ikke lig med, mindre end, større end, mindre end eller lig med, al den slags ting. Forhold så er om Else udsagn. Jeg vil huske, at du ikke kan have en anden uden en tilsvarende hvis. Ligeledes kan du ikke have en andet, hvis uden en tilsvarende hvis. Loops, minde om de 3 slags løkker vi har hamring ind i dig for de sidste par afsnit og problemstillinger sæt. Der må mens når du får input fra brugeren, ved hjælp mens løkker, indtil en bestemt betingelse er sand, og derefter bruge dem, for sløjfer, hvis du skal vide, hvilken iteration af løkken, du er i øjeblikket på, er, hvordan jeg tænker over det. Eller hvis du laver en for hvert tegn i en streng jeg ønsker at gøre noget, for hvert element i et array jeg ønsker at gøre noget for dette element. 

Tråde og arrangementer. Disse har vi ikke dækket så eksplicit i C, men huske dette fra Scratch. Det er forestillingen om at have forskellige scripts. Dette er også denne forestilling om udsendelse af en begivenhed. Nogle mennesker har ikke brug udsendelse i deres projekter i første omgang, som er helt cool, men disse er 2 forskellige måder at håndtere denne større problem kaldet concurrency, som er, hvordan får du programmer til at udføre eller tilsyneladende udføre på samme tid? Forskellige opgaver kører, mens andre opgaver også kører. Dette er, hvordan dit operativsystem synes at virke. Det er derfor, selv om, for eksempel, Jeg har fået min browser kører, kan jeg også tænde Spotify og spille en sang. Det er mere en begrebsmæssig ting at forstå. Jeg ville tage et kig på trådene korte Hvis du gerne vil vide mere om det. 

Lad os se, jeg tror, ​​at der kunne have været et problem på denne i en af ​​disse. Igen, jeg tror tråde og begivenheder er ikke noget, vi vil dække i C bare fordi det er betydeligt vanskeligere end i Scratch. Du bør ikke bekymre dig om det der, men absolut forstå de begreber, forstå, hvad der foregår. Før vi går videre, spørgsmål om uge 0 materiale? Alle følelse temmelig god? Forståelse variabler og hvad en variabel er? 

Flytning af. Uge 1. Et par ting her, som ikke var særligt dækkede i quizzen gennemgang nødvendigvis og også er mere konceptuelle ting at tænke på. Den første er denne opfattelse af, hvad kildekode, compilere og objekt kode er. Nogen? Basil. Er objekt code-jeg mener kildekode er hvad du putter i Klang, og objekt kode er, hvad klang lægger ud, så din computer kan læse programmet. Præcis. Kildekode er den C-kode, som du faktisk skrive op. Objektkode er hvad du får ud af klang. Det er den 0'er og 1-taller i denne binært format. Så hvad der sker, er, når du har en masse objekt filer, siger du kompilerer et projekt eller et program, der bruger flere kildekodefiler, som efter sædvane får. c. filtypenavnet. Det er derfor vi har caesar.c, vigenère.c. Hvis du skriver Java-programmer, du giver dem forlængelsen. Java. Python-programmer har filtypenavnet. Py ofte. 

Når du har flere. C-filer, du samle dem. Klang spytter alt dette binære junk. Så fordi du kun ønsker 1 program har du linker link alle disse objekt filer sammen i 1 eksekverbar fil. Dette er også, hvad der sker, når du bruger CS50 bibliotek, for eksempel. Det CS50 bibliotek er både det. H header fil at du læser, at # includecs50.h. Og så er det også en særlig binær biblioteksfil der er blevet udarbejdet som er 0'er og 1'ere, og at-l flag, så hvis vi går tilbage til vores rum, og vi ser virkelig hurtigt på, hvad der foregår her, når vi ser på vores klang kommando, hvad vi har, er det er vores kildekode fil lige her. Det er en flok kompiler-flag. Og så til allersidst, i disse-l-flag link de faktiske binære filer til disse 2 biblioteker, det CS50 bibliotek og derefter math bibliotek. 

Forståelse hver type filer 'formål i udarbejdelsen proces er noget, du ønsker at være i stand til at opnåelse af i det mindste et højt niveau oversigt over. Kildekode kommer ind Objektkode kommer ud. Objekt kode filer sammenkæde, og du får en smuk, eksekverbar fil. Cool. Det er også her du kan få fejl på flere punkter i processen til kompilering. Det er her, for eksempel, hvis du tager ud denne sammenkædning flag, det CS50 flag, og du udelader det i Spaces, eller når du kører din kode, det er her du får en fejl i sammenkædningen fase, og linkeren vil sige: "Hey, du kaldte en funktion GetString der er i den CS50 bibliotek. " "Du fortalte mig det var i CS50 biblioteket, og jeg kan ikke finde koden til det." Det er, hvor du er nødt til at forbinde det med, og det er særskilt fra en compiler fejl, fordi compileren ser på syntaks og den slags ting. Det er godt at vide, hvad der sker hvornår. 

Andre ting at vide om. Jeg vil sige, du helt sikkert ønsker at tage et kig på den kort på typecasting udført af Jordan at forstå, hvad int'er er under kølerhjelmen, hvilke tegn er under kølerhjelmen. Når vi taler om ASCII og vi faktisk ser på den ASCII-tabellen, hvad der gør, er at give os en under kølerhjelmen udseende på, hvordan computeren faktisk repræsenterer kapitalen A og tallet 7 og et komma og et spørgsmålstegn. Computeren har også særlige måder at repræsentere tallet 7 som et heltal. Den har en særlig måde at repræsentere tallet 7 som et decimaltal, og dem er meget forskellige. Typecasting er, hvordan du fortælle computeren "Hey, jeg vil have dig til at konvertere fra én repræsentation til en anden repræsentation. " Hvorfor vi ikke tage et kig på det. 

Jeg vil også tage et kig på den korte på biblioteker og den korte på compilers. Dem snak om processen med udarbejdelse, hvad et bibliotek er, og gå over nogle af disse spørgsmål, som du kan få spurgt. Spørgsmål om Uge 1-materiale? Er der nogen emner herinde, der synes skræmmende som du gerne vil dække? Jeg forsøger at blæse gennem det meste af disse tidligere emner, så vi kan komme til pointere og gøre en lille smule af rekursion. Tanker? Noget at dække? Tid til lidt chokolade måske? Du fyre arbejder igennem det. Jeg har tænkt mig at holde sipping på min kaffe. Uge 2. Godt opkald, god opkald. I uge 2 snakkede vi lidt mere om funktioner. 

I de første par problematiske sæt vi ikke virkelig skrive nogen funktioner på alle andet end hvilken funktion? [Student] Main. >> Main, præcis. Og så har vi set de forskellige kostumer, der main slidt. Der er den, hvor det tager ingen argumenter, og vi bare sige tomrum i mellem parenteserne, og så er der den anden, hvor vi ønsker at tage kommandolinjeargumenter, og da vi så, det er hvor du har int argc og streng argv arrayet eller nu, at vi faktisk har udsat streng at være den char *, at det er vi vil begynde at skrive det som char * argv og derefter parentes. I Problem Set 3, så gutter en flok af funktioner, og du implementeret en masse funktioner, tegne, se op, kapløbet. Prototyperne blev alle skrevet der for dig. 

Hvad jeg ønskede at tale om her med funktioner virkelig hurtigt er, at der er 3 dele til dem, når du skriver en funktion. Du skal angive returtype for funktionen. Du skal angive et navn for den funktion, og så er du nødt til at specificere argumentet listen eller parameterlisten. For eksempel, hvis jeg skulle skrive en funktion til at opsummere en flok af heltal og derefter vende tilbage til mig det beløb, hvad der ville være mit returtype hvis jeg ønskede at opsummere heltal og derefter returnere summen? Derefter navnet på funktionen. Hvis jeg gå videre og skrive i grøn, denne del er returtype. Denne del er navnet. Og så i parentes er der, hvor jeg giver de argumenter, ofte forkortet som args, undertiden kaldet params for parametre. Og hvis du har en, du bare angive én. Hvis du har flere du adskille hver med et komma. Og for hvert argument, du giver det 2 ting, som er-Kevin? [Kevin] Du er nødt til at give type og derefter navnet. Og derefter navnet, og navnet er det navn, du vil bruge at henvise til dette argument i sum-funktionen, inden den funktion, du i øjeblikket er ved at skrive. 

Du behøver ikke at for eksempel, hvis jeg har tænkt mig at opsummere, sige, et array af heltal-vi do int array, og jeg vil give mig selv nogle krøllede parenteser der- så når jeg passerer et array til summen funktion Jeg passerer det i den første position af argumentet listen. Men det array, jeg passerer i behøver ikke at have navnet arr.. Arr. vil være, hvordan jeg henvise til dette argument i kroppen af ​​funktionen. Den anden ting, vi er nødt til at tage hensyn til, og det er lidt anderledes end funktioner, men jeg tror, ​​det er en vigtig pointe, er, at i C, når jeg skriver en funktion som denne hvordan kan jeg vide, hvor mange elementer er i denne array? Det er noget af et trick spørgsmål. Vi talte om dette en lille smule i sidste uges afsnit. Hvordan kan jeg vide, hvor mange elementer inde et array i C? Er der en måde? 

Det viser sig, at der er ingen måde at vide. Du er nødt til at lade det separat. Der er et trick, du kan gøre hvis du er i samme funktion, hvor arrayet er erklæret, og du arbejder med en stak array. Men det fungerer kun, hvis du er i samme funktion. Når du har bestået et array til en anden funktion, eller hvis du har erklæret et array og du lægger det datatabel på heapen, har du brugt malloc  og den slags ting, så er alt håb ude. Så er du faktisk nødt til at passere rundt en særlig argument eller en anden parameter fortæller dig hvor stor array er. I dette tilfælde ville jeg ønsker at bruge et komma-Undskyld, går det væk fra skærmen her- og jeg vil passere i en anden argument  og kalder det int len ​​for længden. 

En ting, der kan komme op på quizzen beder dig om at skrive eller opfylde en særlig funktion kaldet noget. Hvis vi ikke giver dig prototypen, så det hele her, hele denne rod kaldes funktionen angivelse eller funktion prototype, dette er en af ​​de første ting, du ønsker at søm ned, hvis det ikke er givet til dig med det samme på quizzen. Den anden trick jeg har lært, er, at siger, at vi giver dig en prototype for en funktion, og vi siger, "Hey, har du fået at skrive det." Inde i de krøllede parenteser, du har på quizzen hvis du bemærker, at der er en returtype og du bemærker, at returtypen er noget andet end hulrum, hvilket betyder, at funktionen ikke returnerer noget, så en ting du absolut ønsker at gøre, er at skrive en slags tilbagevenden erklæring i slutningen af ​​funktionen. Return, og i dette tilfælde, vil vi sætte en blank, fordi vi ønsker at udfylde det tomme. Men det får du tænker på den rigtige måde, hvordan skal jeg gribe dette problem? Og det minder dig du er nødt til at returnere en værdi til den opkaldende af funktionen. 

Ja. >> [Student] Er stil gælder, når vi skriver kode på quizzen? Såsom indrykning og den slags ting? >> [Student] Yeah. Nej, ikke så meget. Jeg tror en masse af-dette er noget, vi vil tydeliggøre på quizzen på dagen for, men typisk bekymre sig om # omfatter og den slags ting, det er lidt udenfor. [Student] Har du brug for at kommentere din håndskrevne kode? Har du brug for at kommentere din håndskrevne kode? Kommentering er altid godt, hvis du er bekymret for delvis kredit eller du ønsker at kommunikere din hensigt til grader. Men jeg, igen, vil afklare om quizzen selv og i quiz dag, men jeg tror ikke, at du vil blive bedt om at skrive kommentarer, nej. Typisk ikke, men det er helt sikkert den slags ting, hvor du kan kommunikere din hensigt, som "Hey, det er her jeg har tænkt mig med det." Og nogle gange, der kan hjælpe med delvis kredit. Cool. 

Basil. [Basil] Hvad er forskellen mellem at erklære, siger, int lang i de argumenter eller parametre kontra erklære en variabel i funktionen? Wow, kaffe gik ned i luftrøret. [Basil] Ligesom der ting, vi ønsker at sætte i argumenter. Ja, det er et godt spørgsmål. Hvordan vælger du hvilke ting du ønsker at sætte i de argumenter forhold til, hvad ting du skal gøre inde i funktionen? I dette tilfælde har vi inkluderet begge disse som argumenter fordi de er noget, som den, der kommer til at bruge funktionen SUM nødt til at præcisere disse ting. 

Funktionen SUM, ligesom vi talte om, har ingen mulighed for at vide hvor stort array er den går fra sin opkalds eller hvem der bruger funktionen SUM. Det har ingen mulighed for at vide hvor stor den opstilling er. Grunden til at vi passerer i denne længde lige her som et argument er, fordi det er noget, som vi dybest set er at fortælle den, der ringer af funktionen, uanset hvem der kommer til at bruge den sum funktion, "Hey, ikke kun du nødt til at give os et array af int'er du også nødt til at fortælle os, hvor stort array, du har givet os, er. " [Basil] De vil begge være kommandolinjeargumenter? Nej, disse er faktiske argumenter, som du ville passere til funktionen. 

Lad mig gøre en ny side her. [Basil] Ligesom navn ville passere- [Nate H.] Hvis jeg har int main (void), og jeg har tænkt mig at sætte i min tilbagevenden 0 herned i bunden, og sige, at jeg vil kalde funktionen SUM. Jeg vil gerne sige int x = sum (); Hvis du vil bruge funktionen SUM jeg nødt til at passere i både array, som jeg ønsker at opsummere og længden af ​​array'et, så det er her hvis jeg havde en matrix af int'er, siger jeg havde int numbaz [] = 1, 2, 3, form for brug, der hacket op syntaks lige der, så hvad jeg ville gøre, er i sum, jeg ønsker at passere i både numbaz og tallet 3 at fortælle sum funktionen "Okay, her er array jeg vil have dig til at opsummere." "Her er dens størrelse." Giver det mening? Besvarer det dit spørgsmål? 

På mange måder det gør parallel, hvad vi gør med de vigtigste når vi har de kommandolinjeargumenter. Et program som Cæsar cipher, for eksempel, er nødvendig at kommandolinjeargumenter ville ikke være i stand til at gøre noget. Det ville ikke vide, hvordan man kryptere hvis du ikke fortælle, hvad nøglen til at bruge eller hvis du ikke fortælle, hvad streng du ønskede at kryptere. Tilskyndelse for input, det er her vi har 2 forskellige mekanismer for at tage input fra brugeren, for at tage information fra brugeren. For Problem Set 1 vi så dette GetInt, GetString, GetFloat måde af forespørgsel om input, og det hedder med standard input stream. Det er lidt anderledes. Det er noget, du kan gøre på én gang i modsætning til når du starter programmet, når du starter programmet kører. De kommandolinjeargumenter alle er specificeret, når du starter programmet kører. Vi har blande de to af dem. Når vi bruger argumenter til en funktion, det er meget ligesom kommandolinjeargumenter til main. Det er, når du påberåbe den funktion, du har brug for at fortælle det hvad den behøver for at kunne udføre sine opgaver. En anden god ting at se på-og jeg vil lade dig se på det i din fritid, og det blev dækket i quizzen, var denne opfattelse af anvendelsesområdet og lokale variable versus globale variable. Gør opmærksom på det. 

Nu, hvor vi får på denne anden ting, i uge 3 vi begyndte at snakke om søgning og sortering. Søgning og sortering, i det mindste i CS50, er i høj grad en introduktion til nogle af de mere teoretiske dele af datalogi. Problemet med søgning, problemet med sortering er store, kanoniske problemer. Hvordan finder du et bestemt antal i en vifte af milliarder af heltal? Hvordan finder du et bestemt navn i en telefonbog der er gemt på din bærbare computer? Og så introducerer vi denne idé om asymptotiske driftstid til virkelig at kvantificere hvor længe, ​​hvor hårdt disse problem er, hvor lang tid de tager at løse. I, tror jeg, 2011 er quiz der er et problem, som jeg tror fortjener dækker meget hurtigt, hvilket er den her, problem 12. O nej, det er Omega. 

Her taler vi om den hurtigst mulige køretid for en bestemt algoritme, og derefter den langsomste mulige driftstid. Denne Omega og O er virkelig bare genveje. De er notational genveje for at sige hvor hurtigt i den bedst mulige tilfælde vil vores algoritme køre, og hvor langsomme i den værst tænkelige tilfælde vil vores algoritme køre? Lad os gøre et par af disse, og disse blev også dækket på kort på asymptotisk notation, som jeg stærkt anbefale. Jackson gjorde et virkelig godt stykke arbejde. Med binær søgning, taler vi om binær søgning som værende en algoritme, og vi normalt taler om det på grund af sin store O. Hvad er den store O? Hvad er den langsomste mulige driftstid af binær søgning? [Student] N ²? Close, jeg gætte svarende til den. Det er meget hurtigere end det. [Student] Binary? >> Ja, binær søgning. [Student] Det er log n. Log n, så hvad betyder log n betyde? Det halverer det hver iteration. Præcis, så i den langsomste mulige tilfælde, sige, hvis du har en sorteret opstilling af en million heltal og det nummer, du leder efter er enten det første element i arrayet eller den sidste element i grupperingen. Husk, at binære søgealgoritme virker ved at kigge på den midterste del, se, om det er den kamp, ​​som du leder efter. Hvis det er, så stor, du fandt den. 

I det bedst mulige tilfælde har hvor hurtigt binær søgning løb? [Studerende] 1. 1, er det konstant tid, big O i 1. Yeah. [Student] Jeg har et spørgsmål. Når du siger logger af n, du mener med hensyn til basen 2, right? Ja, så det er den anden ting. Vi siger log n, og jeg gætte, da jeg var i high school Jeg har altid antaget, at log var basis 10. Ja, så ja, log base 2 typisk er, hvad vi bruger. Igen, går tilbage til binær søgning, hvis du søger efter enten elementet til allersidst eller elementet i begyndelsen, fordi du starter i midten og derefter du kassere uanset hvilken halv opfylder ikke de kriterier, du leder efter, og du gå til den næste halvdel og den næste halve og den næste halvdel. Hvis jeg søger efter det største element i million integer array Jeg har tænkt mig at halvere det højst log på 1 million gange før jeg endelig teste og se, at elementet jeg leder efter er i den største eller i det højeste indeks af arrayet, og det vil tage log af n, skal du logge på 1 million gange. 

Bubble slags. Kan du fyre huske den boble slags algoritme? Kevin, kan du give mig en hurtig resumé af, hvad der skete i den boble slags algoritme? [Kevin] Dybest set det går igennem alt på listen. Det ser på de to første. Hvis det første er større end den anden det swaps dem. Derefter sammenlignes andet og tredje, samme ting, swaps, tredje og fjerde, hele vejen ned. Større tal vil følge op til slutningen. Og efter uanset hvor mange sløjfer du er færdig. Præcis, så hvad Kevin sagde, er, at vi vil se større tal boble op til udgangen af ​​arrayet. For eksempel, har du noget imod walking os gennem dette eksempel, hvis dette er vores array? [Kevin] Du tager 2 og 3. 3 er større end 2, så du bytte dem. [Nate H.] Højre, så vi bytte dem, og så vi får 2, 3, 6, 4 og 9. [Kevin] Så du sammenligne 3 og 6. 3 er mindre end 6, så du forlader dem, og 6 og 4, ville du bytte dem fordi 4 er mindre end 6. [Nate H.] Right, så jeg får 2, 3, 4, 6, 9. [Kevin] Og 9 er større end 6, så du forlader den. Og du vil gå tilbage igennem det igen. 

[Nate H.] Er jeg gjort på dette punkt? >> [Kevin] Nej. Og hvorfor er jeg ikke gjort på dette punkt? Fordi det ligner min opstilling er sorteret. Jeg kigger på det. [Kevin] Gå igennem det igen og sørg for, at der ikke er flere swaps før du fuldt ud kan stoppe. Præcis, så du skal holde går igennem, og sørg for, at der ikke er nogen swaps at du kan gøre på dette punkt. Det var virkelig bare heldig, som du sagde, at vi endte med kun at skulle lave 1 passerer gennem og vi er sorteret. Men for at gøre dette i det generelle tilfælde vil vi faktisk nødt til at gøre det igen og igen. Og i virkeligheden var dette et eksempel på den bedst mulige sag, ligesom vi så i problemet. Vi så, at den bedst mulige sag var N. Vi gik gennem opstillingen 1 gang. Hvad er det værst tænkelige tilfælde for denne algoritme? [Kevin] N ². Og hvad ligner det? Hvad ville et array ligne det ville tage n ² tid? [Kevin] [uhørlig] sorteres. Præcis, så hvis jeg havde arrayet 9, 7, 6, 5, 2, først 9 ville boble hele vejen op. Efter 1 iteration ville vi have 7, 6, 5, 2, 9. Derefter 7 vil boble op, 6, 5, 2, 7, 9, og så videre og så videre. 

Vi er nødt til at gå gennem hele arrayet n gange, og du kan faktisk få en anelse mere præcis end dette fordi når vi har flyttet den 9 hele vejen op i sin sidste mulige position Vi ved, at vi aldrig behøver at sammenligne med dette element igen. Når vi begynder gennembobling af 7 op Vi ved, at vi kan stoppe når 7 er lige før 9 da vi allerede har sammenlignet den 9 til den. Hvis du gør dette på en smart måde, det er ikke rigtig, tror jeg, at meget tid. Du kommer ikke til at sammenligne alle de mulige [uhørlige] kombinationer hver eneste gang du går igennem hver iteration. Men alligevel, når vi taler om denne øvre grænse vi siger, at du kigger på n ² sammenligninger hele vejen igennem. 

Lad os gå tilbage, og da vi er begyndt at få lidt kort til tiden Jeg vil sige, bør du helt sikkert gå gennem resten af ​​denne tabel, udfylde det hele ud. Tænk på eksempler. Tænk på konkrete eksempler. Det er virkelig praktisk og nyttigt at gøre. Trække den ud. Det er den slags tabel, som du går igennem i datalogi du bør virkelig begynde at kende disse udenad. Det er den slags spørgsmål, du får i interviews. Det er slags ting, der er godt at vide, og tænke over disse kanter sager, virkelig finde ud af at tænke vel vidende, at for boble sortere den værst mulige opstilling at sortere med det er en, der er i omvendt rækkefølge. 

Pointers. Lad os snakke lidt om pointers. I de sidste par minutter, vi har her Jeg ved, det er noget sammen med fil I / O, som er temmelig ny. Når vi taler om pegepinde årsagen til at vi ønsker at tale om pointers er fordi, en, når vi arbejder i C Vi er virkelig på et forholdsvis lavt niveau sammenlignet med de fleste moderne programmeringssprog. Vi er faktisk i stand til at manipulere de variable i hukommelsen, regne ud, hvor de er faktisk beliggende inden for vores RAM. Når du har gået på at tage operativsystemer klasser, du vil se , at det er, igen, sådan en abstraktion. Det er faktisk ikke tilfældet. Vi har virtuel hukommelse, der gemmer disse oplysninger fra os. 

Men for nu kan du antage, at når du har et program, for eksempel, der kører, når du starter din Cæsar cipher program- Jeg vil skifte tilbage til min iPad virkelig hurtigt- at der ved begyndelsen dit program, hvis du har, sige, 4 GB RAM på din bærbare computer, du får afsat denne luns, og vi vil kalde denne RAM. Og det starter på et sted, vi vil kalde 0, og det ender på et sted, som vi vil kalde 4 gigabyte. Jeg kan virkelig ikke skrive. Mand, er, at hacket. Når dit program udfører operativsystemet skærer op RAM, og det angiver forskellige segmenter for forskellige dele af dit program til at leve i. Hernede dette område er lidt af en ingenmandsland. Når du går op lidt længere her du har fået faktisk det sted, hvor koden for dit program liv. Det faktiske binære kode, som eksekverbar fil faktisk bliver indlæst i hukommelsen når du kører et program, og den lever i kodesegmentet. Og som dit program udfører processoren ser på dette kodesegmentet at regne ud, hvad er det næste instruktion? Hvad er den næste linje kode jeg har brug for at udføre? 

Der er også en data segment, og det er her de strengkonstanter få gemt at du har brugt. Og så videre deroppe er dette sted kaldet den bunke. Vi adgang hukommelse derinde ved hjælp af malloc, og derefter mod selve toppen af ​​dit program der er stakken, og det er her vi har spillet i det meste af begyndelsen. Dette er ikke i skala eller noget. Meget af dette er meget maskine afhængig, operativsystem afhængige, men det er relativt hvordan tingene bliver chunked op. Når du kører et program, og du erklærer en variabel kaldet x- Jeg har tænkt mig at tegne en anden kasse nede, og det vil være RAM så godt. Og jeg har tænkt mig at se. Vi vil tegne takkede linjer for at angive dette er blot en lille del af RAM og ikke det hele som trækker vi øverst. 

Hvis jeg erklærer en heltalsvariabel kaldet x, så hvad jeg egentlig får, er en kortlægning der er gemt i symbol tabellen i mit program der forbinder navnet x til denne region af hukommelse, som jeg har tegnet lige her mellem de lodrette bjælker. Hvis jeg har en linje kode i mit program, der siger x = 7 processoren kender "Åh, okay, jeg ved, at x lever på dette sted i hukommelsen." "Jeg har tænkt mig at gå videre og skrive en 7 der." Hvordan virker det ved, hvad placering dette er i hukommelsen? Nå, det hele foregår ved oversættelsen. Compileren tager sig af fordelingen, hvor hver af de variable kommer til at gå og skabe en særlig kortlægning eller snarere forbinde prikkerne mellem et symbol og hvor den skal hen, en variabel navn og hvor det kommer til at leve i hukommelsen. Men det viser sig, at vi faktisk kan få adgang til det i vores programmer så godt. Dette får betydning, når vi begynder at tale om nogle af de datastrukturer, som er et koncept, som vi vil introducere senere. 

Men for nu, er, hvad du kan vide, at jeg kan oprette en pegepind til denne placering, x. For eksempel kan jeg oprette en pointer variabel. Når vi opretter en pointer variabel bruger vi stjernen notation. I dette tilfælde siger, at dette jeg har tænkt mig at oprette en pegepind til en int. Det er en type, ligesom alle andre. Vi giver det en variabel som y, og så satte vi det lige til adressen, til en adresse. I dette tilfælde kan vi sætte y til at pege på x ved at tage adressen på x, som vi gør med denne tegnet, og så satte vi y til at pege på den. Hvad dette hovedsagelig gør, er, hvis vi ser på vores RAM dette skaber en separat variabel. Det kommer til at kalde det y, og når denne linje kode henretter det er faktisk kommer til at skabe en lille pointer, som vi typisk trække så en pil, og det sætter y til at pege på x. Ja. [Student] Hvis x er allerede en pegepind, ville du bare gøre int * y = x i stedet for at have tegnet? Ja. Hvis x er allerede en pointer, så du kan indstille 2 pointers svarende til hinanden, i hvilket tilfælde y ville ikke pege på x, men det ville pege på, hvad x peger på. Vi kan desværre for sent. 

Hvad jeg ville sige på nuværende tidspunkt, kan vi tale om det offline, men jeg vil sige begynde at arbejde gennem dette problem, # 14. Du kan se der er allerede en lille smule udfyldt for dig her. Du kan se, at når vi erklærer 2 pointere, int * x og * y, og bemærk, at pege * ved siden af ​​den variable var noget, der blev gjort sidste år. Det viser sig, at dette svarer til, hvad vi gør i år. Det betyder ikke noget, hvor du skriver *, når du erklære markøren. Men vi har skrevet * ud for den type fordi det gør det meget klart, at du erklære en pointer variabel. Du kan se at erklære de 2 pointere giver os 2 æsker. Her når vi sætter x lig med malloc hvad dette siger er at afsætte hukommelse i bunke. Denne lille boks lige her, denne cirkel, er placeret på den bunke. X peger på den. Bemærk, at y stadig ikke peger på noget. For at få hukommelse til at gemme nummer 42 i x vi ville bruge, hvad notation? [Student] * x = 42. Præcis, * x = 42. Det betyder, følg pilen, og smide 42 derinde. Her hvor vi sætter y og x har vi y peger på x. Igen, dette ligesom hvad Kevin sagde, hvor vi sat y lig x. Y ikke er rettet til x. Snarere er det at pege på, hvad x peger på så godt. 

Og så til sidst i denne sidste kasse er der 2 mulige ting, vi kunne gøre. Den ene er, at vi kunne sige * x = 13. Den anden ting er, at vi kunne sige-Alex, ved du hvad vi kunne gøre her? Man kan sige * x = 13 or- [Student] Man kan sige int whatever. [Nate H.] Hvis dette blev omtalt som en int variabel vi kunne gøre det. Vi kunne også sige * y = 13, fordi de er begge peger på den samme plads, så vi kunne bruge enten variabel til derhen. Ja. >> [Student] Hvad ville det se ud, hvis vi bare sige int x er 13? Det ville være at erklære en ny variabel kaldet x, som ikke ville virke. Vi ville have en kollision, fordi vi erklæret x at være en pegepind op her. [Student] Hvis vi bare havde denne udtalelse af sig selv, hvad ville det se ud i forhold til cirklen? Hvis vi havde x = 13 så ville vi have en kasse, og snarere end at have en pil kommer ud af boksen, vi ville trække det som bare en 13. [Student] I kassen. Okay. 

Tak for at se, og held og lykke på Quiz 0. [CS50.TV]