[Powered by Google Translate] [Week 4] [David J. Malan] [Harvard Universiteit] [Hierdie is CS50.] [CS50.TV] Alles reg, dit is CS50, en dit is die begin van die week 4, en dit is een van die stadigste moontlike sorteer-algoritmes. Watter een is dit dat ons net daar gekyk? Dit was borrel soort, ten einde groot O (n ^ 2) + som, en inderdaad ons is nie die enigstes is wat in hierdie wêreld lyk om te weet watter borrel soort is of sy looptyd. Trouens, dit was 'n onderhoud met Eric Schmidt van Google en voormalige senator Barack Obama net 'n paar jaar gelede. Nou, Senator, jy is hier op Google, en ek hou daarvan om te dink van die presidensie as 'n werksonderhoud. Nou, dit is moeilik om 'n werk te kry as president, en jy gaan nou deur middel van die pogings. Dit is ook moeilik om 'n werk te kry by Google. Ons vrae het, en ons vra ons kandidate vrae, en hierdie een is van Larry Schwimmer. Julle dink ek grap? Dit is reg hier. Wat is die mees doeltreffende manier om 'n miljoen 32-bit heelgetalle te sorteer? [Lag] Goed Ek is jammer >> Nee, nee, nee, nee. Ek dink die borrel soort sou die verkeerde manier om te gaan. Kom op, wat hom dit vertel? Verlede week onthou ons het 'n onderbreking van die kode, ten minste vir 'n dag, en begin fokus op 'n hoër vlak idees en probleemoplossing meer in die algemeen in die konteks van die soek-en sorteer, en ons iets dat ons nie klap hierdie naam op verlede week bekend gestel, maar asimptotiese notasie, die Big O, die Big Omega, en soms ook die Big Theta-notasie, en dit was eenvoudig maniere van die beskrywing van die looptyd van algoritmes, hoeveel tyd wat dit neem vir 'n algoritme om te hardloop. En jy kan onthou dat jy gepraat het oor die loop van die tyd in terme van die grootte van die insette, wat ons oor die algemeen n bel, wat die probleem kan wees, waar n die aantal mense in die kamer, die aantal bladsye in 'n telefoon boek, en ons begin om dinge uit te skryf soos O (n ^ 2) of O (n) of O (n log n), en selfs wanneer die wiskunde het nie heeltemal uit te werk so perfek en dit was 'n ² - n / 2 of iets soos dit ons wil net plaas weggooi sommige van die laer orde terme, en die motivering daar is dat ons regtig 'n soort van objektiewe manier om te evalueer die prestasie van programme of die prestasie van algoritmes wat aan die einde van die dag het niks om te doen nie, byvoorbeeld, met die spoed van jou rekenaar vandag. Byvoorbeeld, as jy borrel soort te implementeer, of jy implementeer om saam te smelt soort of seleksie soort op vandag se rekenaar, 'n 2 GHz-rekenaar, en jy hardloop dit, en dit neem 'n paar sekondes, volgende jaar is daar is 'n 3 GHz of 'n 4 GHz rekenaar, en jy kan dan beweer dat "Wow, my algoritme is nou twee keer so vinnig, "wanneer dit in werklikheid wat natuurlik nie die geval nie. Dis net die hardeware gekry het vinniger, maar jou rekenaar het nie, en sodat ons regtig wil hê om weg te gooi dinge soos veelvoude van 2 of veelvoude van 3 wanneer dit kom by die beskrywing van hoe vinnig of hoe stadig 'n algoritme is en regtig net fokus n of 'n faktor daarvan, 'n krag daarvan soos in die geval van die vorme van verlede week. En onthou dat met die hulp van merge soort ons was in staat om dit te doen veel beter as borrel soort en keuring soort en selfs invoeging soort. Ons het 'n log n, en weer, onthou dat log n algemeen verwys na iets wat groei stadiger as n, so n log n tot dusver was 'n goeie want dit was minder as n ². Maar om te bereik n log n merge soort wat was die basiese kiem van 'n idee wat ons gehad het om te hefboom dat ons ook aged terug in die week 0? Hoe het ons die sorteer probleem aanpak slim met merge soort? Wat is die sleutel insig, miskien? Enigeen op almal. Goed, kom ons neem 'n stap terug. Beskryf saamsmelt soort in jou eie woorde. Hoe het dit gewerk? Okay, sal ons roei terug na week 0. Okay, ja. [Onhoorbaar-student] Goed, goed, sodat ons die skikking van getalle verdeel in 2 stukke. Ons gesorteer elk van dié stukke vleis, en dan saamgesmelt hulle, en ons het gesien dat hierdie idee voor van die neem van 'n probleem wat hierdie groot en kap dit in 'n probleem wat is hierdie groot of hierdie groot. Onthou die telefoon boek voorbeeld. Herinner aan die self-telling algoritme van weke gelede, so saamsmelt soort is opgesom deur hierdie pseudokode hier. Wanneer jy n elemente is gegee, die eerste dit was gesonde verstand gaan. As n <2 dan doen nie enigiets op alle want as n <2 dan n natuurlik 0 of 1, en so as dit is óf 0 of 1 is daar niks om te sorteer. Jy klaar is. Jou lys is trivially reeds gesorteer is. Maar anders as jy 2 of meer elemente het voort te gaan en hulle verdeel in 2 helftes, links en regs. Sorteer elk van daardie helftes, en dan smelt die gesorteerde helftes. Maar die probleem hier is dat met die eerste oogopslag dit voel soos ons vaar. Dit is 'n omsendbrief definisie in as ek het jou gevra om hierdie n elemente te sorteer en jy vir my sê "All right, fyn, ons sal dié n / 2 en diegene N / 2 elemente sorteer," dan is my volgende vraag gaan wees "Fine, hoe kan jy die n / 2 elemente sorteer?" Maar as gevolg van die struktuur van hierdie program, want daar is die basis geval, om so te praat, hierdie spesiale geval wat sê as N > Sara, alles reg. Kelly. >> Kelly en? Willy >> Willy, Sara, Kelly, en Willy. Reg nou is ek is gevra om die vraag deur iemand hoeveel mense is op hierdie stadium, en ek het geen idee. Dit is 'n baie lang lys, en so plaas ek gaan om hierdie truuk te doen. Ek gaan die persoon langs my te vra om die meeste van die werk te doen, en sodra sy doen die meeste van die werk gedoen Ek gaan die minste hoeveelheid van die werk moontlik te doen en voeg net 1 wat haar antwoord is ja, hier gaan ons. Ek het gevra hoeveel mense is op die verhoog. Hoeveel mense is op die toneel aan die linkerkant van jou? Die linkerkant van my >> Goed, maar nie verneuk nie. Dit is goed, dit is korrek, maar as ons wil hierdie logika om voort te gaan Kom ons neem aan dat jy soortgelyke wil punt om hierdie probleem aan die linkerkant van jou, so eerder as antwoord direk voort te gaan en net die bok slaag. O, hoe baie mense is aan die linkerkant van my? Hoeveel mense is aan die linkerkant? 1. [Lag] Okay, so 0, so wat nou Willy gedoen het is jy het jou antwoord terug hierdie rigting sê 0. Nou, wat moet jy doen? >> 1. Okay, so jy is die 1, so jy sê, "Alles reg, ek gaan 1 te voeg watter Willy se telling was, "so 1 + 0. Jy is nou 1 sodat jou antwoord aan die regterkant is nou- 1. >> En myne sou wees 2. Goed, so jy neem die vorige antwoord van 1, die byvoeging van die minimale bedrag van die werk wat jy wil doen, wat is 1. Jy het nou 2, en jy dan oorhandig my watter waarde? 3, ek bedoel, jammer, 2. Goed. Wel, ons het 0 aan die linkerkant. Dan het ons 1, en dan voeg ons 2, en nou is jy die uitreiking van my die nommer 2, en so het ek gesê: okay, 1, 3. Daar is inderdaad 3 mense staan ​​langs my op hierdie stadium, sodat ons kan natuurlik gedoen het dit baie lineêr, baie in die voor-die-hand-liggende manier, maar wat ons het regtig doen? Ons het aanvanklik 'n probleem van grootte 3. Ons het toe dit afgebreek in 'n probleem van grootte 2, dan 'n probleem van die grootte 1, en dan uiteindelik die basis geval was regtig, oh, daar is niemand daar, op watter punt Willy teruggekeer effektief 'n harde-gekodeerde antwoord 'n paar keer, en die tweede een is dan geborrel, geborrel, geborrel het, en dan deur die toevoeging van hierdie een addisionele 1 het ons hierdie basiese idee van rekursie geïmplementeer. Nou, in hierdie geval het dit nie regtig 'n probleem op te los enige meer effektief dan het ons tot dusver gesien het. Maar dink oor die algoritmes wat ons op die verhoog gedoen het tot dusver. Ons het 8 stukkies papier op die skryfbord, op video wanneer Sean was op soek vir die getal 7, en wat het hy werklik doen? Wel, hy het dit nie doen enige soort van verdeel en oorwin. Hy het nie enige soort van rekursie. Eerder het hy net hierdie lineêre algoritme. Maar toe ons die idee van gesorteer getalle op die verhoog lewe verlede week dan het ons hierdie instink van gaan na die middel, op watter punt ons het 'n kleiner lys van grootte 4 of 'n ander lys van grootte 4, en dan het ons die presies dieselfde probleem gehad het, sodat ons herhaal, herhaal, herhaal. Met ander woorde, ons recursed. Baie dankie aan ons 3 vrywilligers hier vir die toon van rekursie met ons. Kom ons kyk as ons kan nie dit maak nou 'n bietjie meer konkrete, die oplossing van 'n probleem wat ons weer kan redelik maklik, maar ons sal dit gebruik as 'n stepping stone na die implementering van hierdie basiese idee. As ek wil die opsomming van 'n klomp van die nommers te bereken, Byvoorbeeld, as jy slaag in die nommer 3, Ek wil om te gee jy die waarde van sigma 3, sodat die som van 3 + 2 + 1 + 0. Ek wil terug te kry die antwoord 6, so ons sal die uitvoering van hierdie sigma funksie, hierdie opsomming funksie wat, weer, in inset neem, en dan gee die opsomming van daardie getal al die pad af na 0. Wat ons kan doen dit redelik eenvoudig, reg? Ons kan dit doen met 'n soort van herhaling struktuur, so laat my gaan voort en kry hierdie begin. Sluit stdio.h. Laat ek myself in die hoof om hier te werk. Kom ons red dit as sigma.c. Dan gaan ek hier om te gaan, en ek gaan 'n int n te verklaar, en ek gaan om die volgende te doen terwyl die gebruiker nie saam nie. Terwyl die user het nog nie vir my 'n positiewe getal laat my gaan voort en gevra hulle vir n = getint, en laat my gee hulle 'n paar instruksies wat om te doen, so printf ("positiewe heelgetal asseblief"). Net iets relatief eenvoudig soos hierdie, sodat ons getref deur die tyd lyn 14 ons het nou 'n positiewe heelgetal is vermoedelik in n. Laat ons nou iets te doen met dit. Laat my gaan voort en bereken die opsomming, so int som = sigma (n). Sigma is net opsomming, so ek net skryf dit in die liefhebber manier. Ons sal net noem dit sigma daar. Dit is die som, en nou is ek gaan om die resultaat te druk, printf ("Die som is% d \ n", som). En dan sal ek terugkeer 0 vir 'n goeie maatreël. Ons het gedoen alles wat hierdie program vereis, behalwe die interessante deel, wat die sigma funksie is om werklik te implementeer. Laat my gaan hier aan die onderkant, en laat my verklaar funksie sigma. Dit het 'n veranderlike te neem, dit is van die tipe Integer, en watter datatipe wil ek vermoedelik terugkeer van sigma? Int, want ek wil dit my verwagtinge aan te pas on line 15. In hier laat my voort te gaan en te implementeer in 'n redelik eenvoudige manier. Kom ons gaan voort en sê int som = 0, en nou is ek gaan om te gaan 'n bietjie vir lus het hier dit gaan om iets soos hierdie te sê, (int i = 0; I <= getal; i + +) som + = i. En dan gaan ek som om terug te keer. Ek geïmplementeer kan dit in 'n aantal maniere. Ek kon gebruik het om 'n while lus. Ek kan oorgeslaan het met behulp van die som veranderlike as ek regtig wou, maar in kort, ons moet net 'n funksie dat indien ek nie domkop verklaar som 0. Dan is dit iterate up deur die getal van 0, en op elke iterasie voeg dat die huidige waarde te som en dan terugkeer som. Nou, daar is 'n effense optimalisering hier. Dit is waarskynlik 'n gemors stap, maar dit is so. Dit is goed vir nou. Ons is ten minste deeglike en 0 al die pad op tot. Nie baie hard en redelik eenvoudig, maar dit blyk dat ons met die sigma-funksie het dieselfde geleentheid as ons hier op die verhoog gedoen het. Ons net op die verhoog getel hoeveel mense was langs my, maar in plaas daarvan as ons wou die getal 3 + 2 + 1 te tel ons af na 0 kan insgelyks punt na 'n funksie dat ek sal plaas beskryf as rekursiewe. Hier laat ons kyk 'n vinnige gesonde verstand en maak seker dat ek nie domkop. Ek weet daar is ten minste een ding in hierdie program wat ek het iets verkeerds doen nie. Toe ek tik ek gaan enige vorm van skree op my te kry? Wat gaan ek geskree oor? Ja, ek het vergeet om die prototipe, so ek is die gebruik van 'n funksie genoem sigma on line 15, maar dit is nie tot line 22 verklaar, sodat ek die beste proaktief gaan hier en 'n prototipe te verklaar, en ek sal sê int sigma (int), en dit is dit. Dit is aan die onderkant geïmplementeer. Of 'n ander manier wat ek kan oplos, Ek kon die funksie beweeg daar, wat is nie sleg nie, maar ten minste wanneer jou programme begin om lang, eerlik, Ek dink daar is 'n bietjie waarde in om altyd 'n hoof by die top sodat jy in die leser kan die lêer oop te maak en dan dadelik sien wat die program doen sonder om te soek deur dit soek vir daardie hooffunksie. Kom ons gaan af na my terminale venster hier probeer maak sigma sigma maak, en ek screwed up ook hier. Implisiete verklaring van die funksie getint beteken dat ek vergeet het om te doen wat anders? [Onhoorbaar-student] Goed, so blykbaar 'n algemene fout, so laat ons sit dit op hier, cs50.h, en nou, laat ons gaan terug na my terminale venster. Ek sal die skerm skoon te maak, en Ek sal heruitzend maak sigma. Dit lyk saamgestel het. Laat my tog hardloop sigma. Ek sal tik in die nommer 3, en ek het 6, so nie 'n streng tjek, maar ten minste is dit blyk te werk met die eerste oogopslag, maar laat ons nou skeur dit uitmekaar, en laat gebaseer is eintlik die idee van rekursie, weer, in 'n baie eenvoudige konteks so dat in 'n paar weke se tyd wanneer ons begin verken liefhebber van datastrukture as skikkings ons het 'n ander instrument in die toolkit waarmee manipuleer die data strukture soos ons sal sien. Dit is die iteratiewe benadering, die lus-gebaseerde benadering. Laat ek eerder nou doen. Laat my plaas sê dat die opsomming van die aantal na 0 is regtig dieselfde ding as nommer + sigma (nommer 1). Met ander woorde, net soos op die verhoog het ek aan elkeen van die mense langs my gestamp, en hulle het op sy beurt gehou vaar totdat ons eindelik die onderste draaipunt bereik het Willy, wat het 'n harde-gekodeerde antwoord soos 0 om terug te keer. Nou hier ons insgelyks vaar sigma dieselfde funksie as oorspronklik genoem, maar die sleutel insig hier is dat ons nie bel sigma identies. Ons is nie verby in n. Ons is duidelik wat in getal - 1, so 'n effens kleiner probleem, effens kleiner probleem. Ongelukkig is dit nie heeltemal 'n oplossing nie, en voor ons los wat kan spring uit as die voor die hand liggend by sommige van julle laat my gaan voort en heruitzend maak. Dit lyk okay te stel. Laat my heruitzend sigma met 6. Oeps, laat my heruitzend sigma met 6. Ons het gesien dat dit voor, al is dit per ongeluk laaste keer as well. Hoekom het ek hierdie kriptiese segmentering skuld kry? Ja. [Onhoorbaar-student] Daar is geen basis geval, en meer spesifiek, wat waarskynlik gebeur? Dit is 'n simptoom van watter gedrag? Sê dat dit 'n bietjie harder. [Onhoorbaar-student] Dit is 'n oneindige lus effektief, en die probleem met 'n oneindige lusse wanneer hulle behels rekursie in hierdie geval, 'n funksie roep self, wat gebeur elke keer as jy bel 'n funksie? Wel, dink terug aan hoe ons uitgelê die geheue in 'n rekenaar. Ons het gesê dat daar is hierdie stuk van die geheue genoem die stapel wat is aan die onderkant, en elke keer as jy bel 'n funksie 'n bietjie meer geheue kry sit op hierdie sogenaamde stapel met daardie funksie se plaaslike veranderlikes of parameters, so as sigma noem sigma oproepe sigma noem sigma  noem sigma waar hierdie storie einde? Wel, dit uiteindelik overschrijdingen die totale bedrag geheue wat u beskikbaar het op jou rekenaar. Jy oorrompel die segment wat jy veronderstel is om te bly binne, en jy kry hierdie segmentering skuld, kern gestort, en wat die kern gestort beteken is dat ek nou 'n lêer genaamd kern wat is 'n lêer met nulle en ene wat eintlik in die toekoms sal wees diagnosties nuttige. As dit is nie duidelik waar jy jou fout is wat jy kan doen om 'n bietjie van die forensiese ontleding, om so te praat, op hierdie kern dump lêer, wat, weer, is net 'n hele klomp van nulle en ene wat verteenwoordig hoofsaaklik die toestand van jou program in die geheue die oomblik is dit op hierdie manier neergestort het. Die fix hier is dat ons net kan nie blindelings terug sigma, die nommer + sigma van 'n effens kleiner probleem. Ons moet 'n soort van die basis-geval hier te hê, en wat die basis geval moet seker wees? [Onhoorbaar-student] Okay, so lank as wat die nommer is positief ons eintlik moet terugkeer, of 'n ander manier, as nommer is, sê, <= 0 jy weet wat, ek vooruit sal gaan en terug 0, baie soos Willy gedoen het, en anders, ek gaan om voort te gaan en keer terug, so dit is nie dat baie korter as die iteratiewe weergawe wat ons eerste opgesweep met behulp van 'n for-lus, maar sien dat daar is hierdie soort van elegansie om dit te. In plaas van die terugkeer van 'n paar nommer en die verrigting van al hierdie wiskunde en die toevoeging van dinge met plaaslike veranderlikes jy plaas sê: "Goed, as dit is 'n super maklike probleem, soos die nommer is <0, laat my dadelik terug 0. " Ons gaan nie die ondersteuning van negatiewe getalle te pla, so ek gaan hard-kode om die waarde van 0. Maar andersins, te implementeer hierdie idee van 'n opsomming al hierdie getalle bymekaar jy effektief kan neem 'n klein byt uit van die probleem, baie soos ons gedoen het hier op die verhoog, dan punt die res van die probleem aan die volgende persoon, maar in hierdie geval die volgende persoon is jouself. Dit is 'n identies genoem funksie. Slaag dit net 'n kleiner en kleiner en kleiner probleem elke keer, en selfs al het ons nie heeltemal geformaliseer dinge in die kode hier dit is presies wat aan die gang was in week 0 met die telefoon boek. Dit is presies wat aan die gang was in die afgelope weke met Sean en met ons demonstrasies van die soek van getalle. Dit is die neem van 'n probleem en verdeel dit weer en weer. Met ander woorde, daar is 'n manier van die vertaling hierdie werklike wêreld konstruk, hierdie hoër vlak konstruk verdeel en oorwin en weer en weer om iets te doen in die kode, so dit is iets wat ons weer sal sien met verloop van tyd. Nou, as 'n eenkant, as jy nuut vir rekursie jy moet ten minste verstaan ​​nou waarom dit is snaaks. Ek gaan om te gaan na google.com, en ek gaan om te soek vir 'n paar tips en tricks op rekursie, betree. Vertel die persoon langs jou as hulle nie lag nou. Bedoel jy rekursie? Did you mean-ah, daar gaan ons. Okay, nou wat is die res van almal. 'N bietjie paaseier ingebed iewers daar in Google. As 'n eenkant, een van die skakels wat ons op die kursus se webblad vir vandag is net hierdie rooster van verskillende sorteer-algoritmes, wat sommige van ons kyk na die laaste week, maar wat mooi oor hierdie visualisering as jy probeer om jou verstand te draai om verskeie dinge met betrekking tot algoritmes weet dat jy kan nou baie maklik begin met verskillende soorte van insette. Al die insette omgekeer, die insette meestal gesorteer, die insette random en so meer. As jy probeer om weer, onderskei hierdie dinge in jou gedagtes besef dat hierdie URL op die kursus se webblad op die Lesings bladsy kan jou help gevolg deur 'n paar van daardie. Vandag het ons uiteindelik kry om hierdie probleem op te los van 'n ruk terug, wat was dat hierdie swap funksie net nie werk nie, en wat was die fundamentele probleem met hierdie funksie swap, waarvan die doel was, weer, hier en hier om 'n waarde te ruil van so 'n aard dat dit gebeur? Dit het eintlik nie werk nie. Hoekom? Ja. [Onhoorbaar-student] Presies, die verduideliking vir hierdie bugginess was eenvoudig omdat wanneer jy noem funksies in C en daardie werksaamhede neem argumente, soos a en b hier, jy verby in afskrifte van watter waarde jy aan daardie funksie. Jy is nie die verskaffing van die oorspronklike waardes self, so ons het dit gesien in die konteks van buggyc, buggy3.c, wat lyk 'n bietjie iets soos hierdie. Onthou dat ons x en y geïnisialiseer aan 1 en 2, onderskeidelik. Ons dan uitgedruk wat hulle was. Ek het toe beweer dat ek hulle uitruiling deur die roeping van die swap van x, y. Maar die probleem was dat die uitruiling gewerk het, maar slegs in die omvang van die swap funksie self. So gou as ons getref lyn 40 daardie verruil waardes is weggegooi, en sodat daar niks in die oorspronklike funksie hoof was eintlik verander nie, so as jy terug dink dan as wat dit lyk in terme van ons geheue indien dit linkerkant van die raad verteenwoordig- en ek sal my bes doen vir almal om dit te sien as dit linkerkant van die raad verteenwoordig, sê, jou geheue, en die stapel gaan om te groei op hierdie manier, en ons noem 'n funksie soos hoof, en die belangrikste 2 plaaslike veranderlikes, x en y, Kom ons beskryf as x, en laat beskryf hierdie as y hier, en laat ons in die waardes 1 en 2, so hier is die hoof, en as hoof roep die swap funksie om die bedryfstelsel gee die swap funksie sy eie swath van die geheue op die stapel, sy eie raam op die stapel, om so te praat nie. Dit ken ook 32 bisse vir hierdie ints. Dit gebeur met hulle noem: a en b, maar dit is 'n heeltemal arbitrêre. Dit kan genoem het wat dit ook al wil, maar wat gebeur as hoof oproepe swap is dit neem om hierdie 1, sit daar 'n kopie, sit daar 'n kopie. Daar is 1 ander plaaslike veranderlike in ruil, hoewel genoem wat? >> Tmp. Tmp, so laat my gee myself 'n ander 32 stukkies hier, en wat het ek gedoen in hierdie funksie? Ek het gesê int tmp kry 'n, so het 'n 1, so ek het dit gedoen toe ons laas gespeel met hierdie voorbeeld. Dan is 'n kry b, so b 2, so dit raak nou 2, en nou b kry temp, so temp is 1, so nou word b. Dit is 'n groot. Dit het gewerk. Maar dan so gou as die funksie opbrengste swap se geheue verdwyn effektief sodat dit hergebruik kan word deur 'n paar ander funksie in die toekoms, en die belangrikste is natuurlik heeltemal onveranderd. Ons moet 'n manier van fundamenteel oplossing van hierdie probleem, en vandag sal ons uiteindelik 'n manier om dit te doen waardeur ons kan stel iets genoem 'n wyser. Dit blyk dat ons kan hierdie probleem op te los nie deur afskrifte van x en y maar plaas deur in wat, dink jy, aan die swap funksie? Ja, wat oor die adres? Ons het nie regtig gepraat oor adresse in baie detail, maar indien hierdie bord my rekenaar se geheue kan ons seker begin met die numering van die grepe in my RAM en sê dit is byte # 1, dit is byte # 2, byte # 3, byte # 4, byte # ... 2 miljard as ek het 2 GB RAM, sodat ons kan sekerlik kom met 'n paar arbitrêre nommeringstelsel skema vir al die individuele grepe in my rekenaar se geheue. Wat as plaas as ek roep swap eerder as slaagpunt in die afskrifte van x en y hoekom ek nie plaas in die adres van x, die adres van y hier, veral die posadres van x en y, want dan ruil, as hy in kennis gestel van die adres in die geheue van x en y, dan ruil, indien ons opgelei hom 'n bietjie, hy potensieel kan ry na daardie adres, om so te praat, x, en daar die aantal te verander, dan ry na die adres van y, die nommer verander, selfs terwyl jy nie eintlik afskrifte van daardie waardes homself kry, so selfs al het ons gepraat oor hierdie as hoof se geheue en as swap die geheue van die magtiges en die gevaarlike deel van die C is dat enige funksie geheue kan op enige plek in die rekenaar raak, en dit is 'n kragtige in die sin dat jy baie fancy dinge kan doen met rekenaarprogramme in C. Dit is gevaarlik, want jy kan ook skroef baie maklik. Trouens, een van die mees algemene maniere vir programme hierdie dae uitgebuit word nog steeds vir 'n programmeerder nie om te besef dat hy of sy is besig om 'n data geskryf moet word in 'n plek in die geheue wat nie bedoel is. Byvoorbeeld, hy of sy verklaar 'n verskeidenheid van grootte 10 maar dan probeer om per ongeluk 11 bytes te sit in dat die verskeidenheid van geheue, en jy begin om dele van die geheue wat nie meer geldig te raak. Net om te kontekstuele hierdie, kan sommige van julle weet dat sagteware vra dikwels vir reeksnommers of registrasie sleutels, Photoshop en Woord en programme soos hierdie. Daar bestaan ​​krake, soos sommige van julle weet, aanlyn waar jy kan 'n klein program hardloop, en voila, nie meer versoek om 'n reeksnommer. Hoe word dat die werk? In baie gevalle is hierdie dinge is net bevinding in die rekenaars teks segmente in die rekenaar se werklike nulle en ene waar is die funksie waar die reeksnommer is versoek, en jy oorskryf daardie ruimte, of terwyl die program loop jy kan uitvind waar die sleutel is eintlik gestoor die gebruik van iets genoem 'n debugger, en jy kan sagteware wat manier kraak. Dit is nie te sê dat dit is ons doelwit vir die volgende paar dae, maar dit het 'n baie werklike wêreld gevolge. Dat 'n mens gebeur diefstal van die sagteware te betrek, maar daar is ook kompromie van die hele masjiene. Trouens, wanneer webtuistes hierdie dae uitgebuit word en gekompromitteer en data uitgelek en wagwoorde word gesteel dit hou baie dikwels tot swak bestuur van 'n mens se geheue, of, in die geval van databasisse, versuim verwag adversarial insette, sodat meer op dat in die komende weke, maar vir nou net 'n voorsmakie van die soort van die skade wat jy kan doen nie heeltemal te verstaan ​​hoe dinge werk onder die kap. Kom ons gaan oor die verstaan ​​waarom hierdie is gebreek met 'n instrument wat sal meer en meer nuttig as ons programme kry meer kompleks. So ver as jy het 'n fout in jou program hoe het jy gegaan oor ontfout? Wat het jou tegnieke tot dusver, hetsy deur jou TF geleer of net self-geleer? [Studente] printf. Printf, so printf het waarskynlik was jou vriend in dat as jy wil om te sien wat gaan aan die binnekant van jou program jy net printf hier, printf hier, printf hier. Dan moet jy hardloop, en jy kry 'n hele klomp van die dinge op die skerm wat jy kan gebruik om dan aflei wat is eintlik verkeerd gaan in jou program. Printf is geneig om 'n baie kragtige ding wees, maar dit is 'n baie handleiding proses. Jy het 'n printf hier te plaas, 'n printf hier, en as jy dit binne 'n lus wat jy kan kry 100 lyne van die uitset wat jy dan hoef te sif. Dit is nie 'n baie gebruikers vriendelik of interaktiewe meganisme vir die ontfouting van programme, maar gelukkig bestaan ​​daar alternatiewe. Daar is 'n program, byvoorbeeld, genoem GDB, die GNU Debugger, wat is 'n bietjie arcane in hoe jy dit gebruik. Dit is 'n bietjie ingewikkeld, maar eerlik, dit is een van daardie dinge waar as jy in hierdie week en volgende die ekstra uur iets soos GDB te verstaan dit sal jou waarskynlik tien uur in die lang termyn, Dus met wat, laat my gee u 'n teaser van hoe hierdie ding werk. Ek is in my terminale venster. Laat my gaan voort en stel hierdie program, buggy3. Dit is reeds tot op datum. Laat ek loop dit net soos ons het 'n ruk terug, en inderdaad, dit is gebreek. Maar hoekom is dit? Miskien het ek verfrommeld die swap funksie. Miskien is dit a en b. Ek is nie heeltemal beweeg hulle rond korrek. Laat my gaan voort en doen dit. Eerder as om net buggy3 hardloop laat my plaas hierdie program GDB, en ek gaan om dit te vertel buggy3 uit te voer, en ek gaan 'n command line argument, tui te sluit, en ons sal dit in die toekoms probleme op spec te herinner. En nou is dit swart-en-wit koppelvlak opkom dat, weer, is 'n bietjie oorweldigend op die eerste, want daar is al hierdie inligting oor die waarborg af hier, maar ten minste is daar is iets bekend is. In die bokant van die venster is my werklike kode, en as ek scroll hier laat my Scroll na die top van my lêer, en inderdaad, daar is buggy3.c, en kennis aan die onderkant van hierdie venster Ek het hierdie GDB prompt. Dit is nie dieselfde as my normale John Harvard prompt. Dit is 'n vinnige gaan om my GDB te beheer. GDB is 'n debugger. 'N debugger is 'n program waarmee jy loop deur uitvoering van jou program lyn deur reël vir reël, langs die pad om iets te doen wat jy wil tot die program, selfs funksies, of op soek is, nog belangriker, op verskeie veranderlike se waardes. Kom ons gaan voort en doen dit. Ek gaan om voort te gaan en tik in die loop GDB se vinnige, so let op die links onder van die skerm Ek het getypt loop, en ek het getref betree, en wat het dit te doen? Dit het letterlik gehardloop my program, maar ek het eintlik nie veel sien gaan hier want ek het eintlik nie aan die debugger om stil te staan ​​by 'n spesifieke oomblik in tyd. Net tik run hardloop die program. Ek eintlik nie sien nie. Ek kan nie manipuleer. In plaas daarvan laat my dit doen. Op hierdie GDB prompt laat my plaas breek tik, tik. Dis nie wat ek bedoel om te tik. Kom ons plaas tik breek hoof. Met ander woorde, ek wil iets genoem 'n breekpunt te stel, wat is gepas vernoem, want dit sal breek of breek uitvoering van jou program op daardie spesifieke plek. Main is die naam van my funksie. Let op dat GDB is redelik slim. Dit uitgepluis het dat die hoof gebeur ongeveer begin lyn 18 van buggy3.c, en dan hier raaksien links bo b + is reg langs die lyn 18. Dit is wat my herinner dat ek 'n breekpunt het op lyn 18. Hierdie keer wanneer ek tik run, ek gaan my program uit te voer tot dit wat breekpunt tref, sodat die program sal breek vir my op lyn 18. Hier gaan ons, hardloop. Niks blyk te gebeur, maar kennisgewing aan die onderkant links die begin van program, buggy3, breekpunt 1 in die hoof op buggy3.c lyn 18. Wat kan ek nou doen? Sien ek kan begin tik om dinge soos druk, nie printf, print x, en nou is dit is vreemd. Die $ 1 is net 'n nuuskierigheid, soos ons sal sien elke keer as jy iets druk kry jy 'n nuwe $ value. Dit is sodat jy kan terug verwys na die vorige waardes net in geval, maar vir nou is wat druk vertel my is dat die waarde van x op hierdie punt in die verhaal is blykbaar 134.514.032. Wat? Waar dit nie eens kom uit? [Onhoorbaar-student] Trouens, dit is wat ons sal noem 'n gemors waarde, en ons het nog nie gepraat oor hierdie, maar die rede dat jy inisialiseer veranderlikes is natuurlik so dat hulle het 'n paar waarde wat jy wil om dit te hê. Maar die vangs onthou dat jy veranderlikes kan verklaar soos ek gedoen het 'n oomblik gelede in my sigma voorbeeld sonder eintlik gee hulle 'n waarde. Onthou wat ek gedoen het oor hier in sigma. Ek verklaar dat n, maar watter waarde het dit gee ek aan? Geen, want ek het geweet dat daar in die volgende paar lyne Getint sou sorg van die probleem om 'n waarde binnekant van n. Maar op hierdie punt in die verhaal van die lyn 11 en lyn 12 en lyn 13 en lyn 14 gedurende daardie paar lyne wat is die waarde van n? In C jy net nie weet nie. Dit is oor die algemeen 'n paar vullis waarde, sommige heeltemal random getal wat oorgebly het in wese van sommige vorige funksie nadat hardloop, so as jou program loop onthou dat funksie kry funksie, funksie, funksie. Al hierdie rame kry op die geheue, en dan dié funksies terugkeer, en net soos ek voorgestel met die uitveër hul geheue is uiteindelik hergebruik. Wel, dit gebeur net so dat hierdie veranderlike x in hierdie program blyk te wees wat sommige vullis waarde soos 134514032 van sommige vorige funksie, nie een wat ek geskryf het. Dit kan iets wat effektief met die bedryfstelsel, 'n funksie onder die kap. Oukei, dis fyn, maar laat ons nou bevorder na die volgende lyn. As ek tik "volgende" by my GDB prompt en ek druk Enter opmerk dat die klem op beweeg af na lyn 19, maar die logiese implikasie is dat die lyn 18 het nou klaar is met die uitvoering, so as ek weer tik "print x" Ek moet nou 1, en inderdaad, ek doen. Weereens, die $ dinge is 'n manier van GDB herinner u wat die geskiedenis van die druk wat jy gedoen het. Laat My dan nou voort te gaan en uit te druk y, en inderdaad, y is 'n paar gek waarde sowel, maar geen groot deal, want ons is in lyn 19 om dit te wys die waarde 2, so laat my weer tik "volgende" nie. En nou is ons op die printf lyn. Laat my print x. Laat my print y. Om eerlik te wees, ek is 'n bietjie moeg van die druk van hierdie. Laat my plaas tik "display x" en "display y," en nou elke keer as ek tik 'n bevel in die toekoms Ek sal daaraan herinner word van wat x en y, wat x en y, wat x en y. Ek kan ook as 'n eenkant, tik in "info inwoners." Info is 'n spesiale opdrag. Locals beteken dit wys my die plaaslike veranderlikes. Net in geval ek vergeet of dit is 'n gek, ingewikkelde funksie dat ek of iemand anders geskryf info locals sal jou vertel wat is al die plaaslike veranderlikes binne hierdie plaaslike funksie dat jy dalk omgee as jy wil om te poke. Nou, is printf oor om uit te voer, so laat my gaan voort en tik net "Volgende." Want ons is in hierdie omgewing wat ons eintlik nie sien nie dit voer sit hier, maar sien dit raak 'n bietjie verminkte hier. Maar let op die skerm oorheersende daar, so dit is nie 'n perfekte program hier, maar dit is okay, want ek kan altyd rondom steek met druk as ek wil. Laat my die volgende weer tik, en nou hier is die interessante deel. Op hierdie punt in die verhaal y is 2, en x is 1, soos wat hier voorgestel word, en weer, die rede waarom dit word outomaties vertoon nou is, omdat ek die opdrag gebruik VERTOON X en vertoon y, sodat die oomblik toe ek tik die volgende in teorie x en y word omgeruil. Nou, ons weet reeds wat gaan nie die geval te wees, maar ons sal sien in 'n oomblik hoe kan ons duik dieper om uit te vind waarom dit is waar. Volgende, en ongelukkig, y is steeds 2 en x is nog 1, en ek kan soveel bevestig. Print x, print y. Inderdaad, geen uitruiling eintlik gebeur het, so laat ons begin dit oor. Duidelik swap is gebreek. Kom ons plaas weer tik "run". Laat my sê ja, ek wil dit van die begin af weer te begin, tik. Nou is ek terug op lyn 18. Let nou op x en y is vullis waardes weer. Volgende, volgende, volgende, volgende. As ek verveeld ek kan ook net tik n volgende. Jy kan dit aan die kortste moontlike volgorde van die karakters afkorten. Ruil nou gebreek. Kom ons duik in, so in plaas van tik die volgende, nou gaan ek stap sodat ek binne die intensivering van hierdie funksie te tik sodat ek kan loop deur, so ek getref stap en dan gaan. Let daarop dat die klem op spring laer in my program lyn 36. Nou wat is die plaaslike veranderlikes? Informasie locals. Niks net nog nie, omdat ons nie gekry het nie aan daardie lyn, so laat ons gaan voort en sê: "die volgende." Nou het ons lyk tmp, print tmp te hê. Garbage waarde, reg? Ek dink nie so nie. Hoe gaan dit print, print b, 1 en 2? In 'n oomblik, so gou as ek tik die volgende weer tmp gaan te neem op 'n waarde van 1, hopelik, omdat tmp gaan word wat die waarde van 'n. Nou laat druk, print b nie, maar nou druk tmp, en dit is inderdaad 1. Laat my die volgende doen. Laat my die volgende doen. Ek het klaar die swap funksie. Ek nog steeds binnekant van dit in reël 40, so laat my druk, print b, en ek gee nie om wat tmp is. Dit lyk soos swap korrek is wanneer dit kom by die uitruiling van a en b. Maar as ek nou volgende tik, ek spring terug na lyn 25, en natuurlik, as ek tik in x en print y hulle is nog steeds onveranderd, so ons het nie 'n vaste die probleem. Maar diagnosties nou miskien met hierdie GDB-program ons het ten minste gekry het een stap nader aan begrip wat verkeerd gaan sonder om rommel te strooi nie ons kode deur 'n printf hier, printf hier printf hier en dan loop dit weer en weer probeer om uit te vind wat verkeerd gaan. Ek gaan om voort te gaan en stop dit heeltemal met ophou. Dit gaan dan sê, "Verlaat in elk geval?" Ja. Nou is ek terug op my normale vinnige, en ek is gedoen met behulp van GDB. As 'n eenkant, hoef jy nie hierdie-tui vlag te gebruik. In werklikheid, as jy dit weglaat jy in wese die onderste helfte van die skerm. As ek tik dan breek hoof en dan hardloop Ek kan nog steeds loop my program, maar wat dit sal doen is meer teksgerigte wys my net die huidige lyn een op 'n tyd. Die-tui, tekstuele gebruikerskoppelvlak, wys jou net meer van die program in 'n keer, wat waarskynlik konseptueel 'n bietjie makliker. Maar inderdaad, ek kan net doen volgende, volgende, volgende, en ek gaan 'n lyn op 'n tyd om te sien, en as ek regtig wil om te sien wat gaan aan Ek kan tik lys en sien 'n hele klomp van die naburige lyne. Daar is 'n video wat ons het gevra dat jy kyk vir die probleem stel 3 wat Nate dek sommige van die verwikkeldheid van die GDB, en dit is een van daardie dinge, eerlik, waar 'n nie-triviale persentasie van jou sal nooit raak GDB, en dit sal 'n slegte ding wees omdat letterlik sal jy uiteindelik spandeer meer tyd later in die semester jaag down foute dan sou jy as jy in daardie 1/2 uur / uur hierdie week en volgende leer te kry gemaklik met GDB. Printf was jou vriend. GDB moet nou jou vriend wees. Enige vrae oor GDB? En hier is 'n vinnige lys van sommige van die mees kragtige en bruikbare instruksies. Ja. >> Kan jy druk 'n string? Kan jy druk 'n string? Absoluut. Dit hoef nie te wees net heelgetalle. As 'n veranderlike s is 'n string tik net in die gedrukte s. Dit sal jou wys wat string veranderlike is. [Onhoorbaar-student] Dit sal vir jou die adres gee en die tou self. Dit sal jou wys beide. En een laaste ding, net omdat dit is goed te ken. Sleepspoor en raam, laat my duik in hierdie een laaste keer, presies dieselfde program met GDB. Laat my voort te gaan en uit te voer die tekstuele user weergawe, breek hoof. Laat my voort te gaan en hardloop weer. Hier is ek. Nou laat my gaan volgende, volgende, volgende, volgende, volgende, stap, betree. En nou dink ek nou doelbewus in ruil, maar ek is soos "Damn, wat die waarde van x?" Ek kan dit nie doen x nie. Ek kan dit nie doen y omdat hulle nie in omvang. Hulle is nie in konteks, maar nie 'n probleem nie. Ek kan tik sleepspoor. Dit wys my al die funksies wat uitgevoer tot hierdie punt in die tyd. Let daarop dat die een op die bodem, hoof, lyne met die belangrikste op die onderkant van ons foto hier. Die feit dat swap is bo dit in lyn is met swap bogenoemde is dit hier in die geheue, en as ek wil terug te kry na die hoof tydelik ek kan sê: "raam." Watter getal? Main raam # 1. Ek gaan om voort te gaan en sê: "raam 1." Nou is ek terug in die hoof, en ek kan druk x, en ek kan druk y, maar ek kan nie print a of b. Maar ek kan as ek sê: "Goed, wag 'n minuut Waar was die ruillêer." Laat my gaan voort en sê: "raam 0." Nou is ek terug waar ek wil wees, en as 'n eenkant, daar is ander opdragte, soos as jy regtig verveeld tik volgende, volgende, volgende, volgende kry, jy kan oor die algemeen sê dinge soos "die volgende 10," en dit sal stap vir stap deur die volgende 10 lyne. Jy kan ook skryf "Gaan voort" as jy regtig gevoed opstaan ​​met die versterking deur middel van dit. Voortgaan om jou program loop sonder onderbreking totdat dit ander breekpunt tref, hetsy in 'n lus of laer af in jou program. In hierdie geval het ons voortgegaan om tot die einde toe, en die program opgewonde normaalweg. Dit is 'n fancy manier minderwaardig proses. Net jou program opgewonde normaalweg. Meer oor wat in die video en in ontfouting sessies by te kom. Dit was 'n baie. Kom ons neem ons 5-minute breek hier, en ons sal terugkeer met structs en lêers. As jy in hierdie week se pset geduik het reeds sal jy weet wat ons gebruik in die verspreiding kode, die bron-kode wat ons aan u voorsien as 'n beginpunt, 'n paar nuwe tegnieke. In die besonder, het ons hierdie nuwe sleutelwoord genoem struct, vir struktuur, sodat ons kan skep persoonlike veranderlikes van spesies. Ons het ook die idee van lêer I / O, lêer inset en uitset, en dit is so dat ons kan red van die staat van jou Scramble raad na 'n lêer op skyf sodat die onderrig genote en ek kan verstaan wat gaan op die binnekant van jou program sonder om met die hand te speel dekades van speletjies van Scramble. Ons kan dit doen meer automatedly. Hierdie idee van 'n struct 'n redelik dwingende probleem oplos. Veronderstel dat ons wil hê om 'n program te implementeer wat verhoed dat een of ander manier 'n spoor van inligting oor studente, en studente mag hê, byvoorbeeld, 'n ID, 'n naam en 'n huis op 'n plek soos Harvard, so dit is 3 stukke van inligting ons wil hê om rond te hou, so laat my gaan voort en begin met die skryf van 'n klein program hier, sluit stdio.h. Laat my sluit cs50.h. En dan begin my hooffunksie. Ek sal nie die moeite met 'n command line argumente, en hier wil ek 'n student te hê, so ek gaan om te sê moet 'n student 'n naam, so ek gaan om te sê "string naam." Dan gaan ek om te sê dat 'n student ook 'n ID, so int id, en 'n student van 'n huis, sodat ek ook gaan om te sê "string huis." Dan sal ek om hierdie 'n bietjie meer skoon soos hierdie. Okay, nou het ek 3 veranderlikes wat 'n student voor te stel, so "'n student." En nou wil ek hierdie waardes aan te vul, so laat my gaan voort en sê iets soos "Id = 123." Naam is Dawid te kry. Kom ons sê die huis gaan Mather te kry, en dan gaan ek om iets te doen arbitrêr soos printf ("% s, wie se ID is% d, woon in% s. En nou, wat wil ek hier in te prop, een na die ander? Naam, ID, huis; terugkeer 0. Okay, tensy ek geskroef iewers hier Ek dink ons ​​het 'n baie goeie program wat 'n student slaan. Natuurlik, dit is nie al wat interessant. Wat gebeur as ek wil 2 studente te hê? Dit is geen big deal nie. Ek kan 2 mense ondersteun. Laat my gaan voort en beklemtoon dit en gaan af hier, en ek kan sê "id = 456" vir iemand soos Rob wat woon in Kirkland. Okay, wag, maar ek kan nie noem dit dieselfde ding, en dit lyk asof ek gaan te hê om dit te kopieer, so laat my sê dat dit sal Dawid se veranderlikes, En laat ek 'n paar afskrifte van hierdie vir Rob. Ons noem hierdie Rob se, maar dit is nie van plan om te werk nou want ek wag, laat ons verander om my te ID1, NAME1 en house1. Rob sal wees 2, 2. Ek het dit hier, hier, hier, hier, hier, hier te verander nie. Wag, wat oor Tommy? Kom ons doen dit weer. Natuurlik as jy dink nog steeds dit is 'n goeie manier om dit te doen nie, dit is nie, so kopieer / plak slegte. Maar ons opgelos dit 'n week gelede. Wat was ons oplossing toe ons wou verskeie gevalle van dieselfde datatipe te hê? [Studente] 'n skikking. 'N skikking, so laat ek probeer om dit skoon te maak. Kom ek maak 'n paar ruimte vir myself aan die bokant, en laat my plaas doen dit hier. Ons sal noem hierdie mense, en in plaas daarvan het ek gaan om te sê "int ids," en ek gaan 3 van ons te ondersteun vir nou. Ek gaan om te sê "string name," en ek sal 3 van ons ondersteun, en dan gaan ek om te sê "string huise," en ek gaan 3 van ons te ondersteun. Nou hier in plaas van Dawid, om sy eie plaaslike veranderlikes ons kan ontslae raak van daardie. Dit voel goed dat ons hierdie is die skoonmaak van. Ek kan dan sê Dawid gaan wees [0] en name [0] en huise [0]. En dan Rob ons insgelyks kan red. Laat ons dit hier neer sit, so hy gaan arbitrêr ids [1]. Hy gaan wees name [1], en dan laastens, huise [1]. Nog 'n bietjie vervelig, en nou moet ek dit uit te figuur, so laat ons sê "name [0], id [0], huise [0], en laat se meervoudig hierdie. IDS, IDS, ids. En weer, ek dit is besig, dit weer doen, ek reeds wend om te kopieer / plak weer, so die kans is daar is 'n ander oplossing. Ek kan waarskynlik hierdie up skoon verder met 'n lus of iets soos dit, Dus, in kort, dit is 'n bietjie beter, maar nog steeds voel soos Ek wend om te kopieer / plak, maar selfs dit, ek beweer, is nie regtig die regte oplossing fundamenteel omdat wat as ons besluit om iewers weet jy wat? Ons moet regtig gewees het die stoor van e-pos adresse vir Dawid en Rob en almal anders in hierdie program. Ons moet ook telefoonnommers stoor. Ons moet ook nood kontak nommers stoor. Ons het al die stukke van die data wat ons wil op te slaan, so hoe gaan jy te werk om dit te doen? Jy verklaar 'n skikking aan die bokant, en dan moet jy handmatig te voeg 'n e-pos adres [0], e-pos adres [1] vir Dawid en Rob en so meer. Maar daar is regtig net 'n aanname onderliggend aan hierdie ontwerp dat ek met behulp van die eer om te weet dat [I] in elk van die verskeie skikkings gebeur net so om te verwys na dieselfde persoon, so [0] in ids is nommer 123, en ek gaan om aan te neem dat name [0] is die dieselfde persoon se naam en huise [0] is die dieselfde persoon se huis en so meer vir al die verskillende skikkings wat Ek skep. Maar let op dat daar geen fundamentele skakeling onder diegene 3 stukke van inligting, id, naam en huis, selfs al is die entiteit wat ons probeer om 'n model in hierdie program is nie skikkings. Skikkings is net hierdie programmatiese manier om dit te doen. Wat ons regtig wil in ons program te modelleer, is 'n persoon soos Dawid, 'n persoon soos Rob binnekant van wat of vat is 'n naam en ID en 'n huis. Kan ons die een of ander manier hierdie idee van die inkapseling uitspreek waardeur 'n persoon 'n ID, 'n naam en 'n huis en geen plek om werklik hierdie hack waardeur ons net vertrou dat bracket iets verwys na die menslike entiteit in elk van hierdie verskillende skikkings? Ons kan eintlik doen. Laat my gaan hierbo belangrikste vir nou, en laat my my eie datatipe werklik vir die eerste keer. Ons gebruik hierdie tegniek in Scramble, maar hier is ek gaan om voort te gaan en 'n datatipe te skep, en weet jy wat, ek gaan om dit te noem student of persoon, en ek gaan om te gebruik typedef vir 'n tipe definieer. Ek gaan om te sê dat hierdie is 'n struktuur, en dan is hierdie struktuur is gaan te wees van die tipe student, sal ons sê, selfs al is dit 'n bietjie gedateer nou vir my. Ons sal sê "int id." Ons sal sê: "string naam." Dan sal ons sê: "string huis" sodat nou deur die einde van hierdie paar reëls van die kode Ek het net geleer kletteren dat daar 'n data tipe behalwe ints verdubbel, behalwe snare, behalwe, behalwe dryf. Soos van hierdie oomblik in die tyd lyn 11, is daar nou 'n nuwe datatipe genoem studente, en nou kan ek 'n student veranderlike waar ek wil verklaar, so laat my scroll down hier aan mense. Nou kan ek ontslae raak van hierdie, en ek kan terug gaan na Dawid hier, en vir Dawid is ek eintlik kan sê dat Dawid ons kan letterlik die naam van die veranderlike na myself, gaan wees van die tipe student. Dit kan 'n bietjie vreemd lyk, maar dit is nie al dat verskillende van iets as 'n int of 'n string of 'n float te verklaar. Dit gebeur net so word genoem student nou, en as ek wil om iets te sit binnekant van die struktuur Ek het nou 'n nuwe stuk van die sintaksis te gebruik, maar dit is redelik eenvoudig, david.id = 123, david.name = "David" in hoofletters D, en david.house = "Mather," en nou kan ek ontslae raak van hierdie dinge hier. Kennisgewing ons het nou herontwerp ons program in regtig 'n baie beter manier in wat nou ons program weerspieël die werklike wêreld. Daar is 'n werklike wêreld idee van 'n persoon of 'n student. Hier het ons nou 'n C-weergawe van 'n persoon of meer spesifiek 'n student. Binnekant van daardie persoon is die relevante kenmerke, ID, naam en huis, so Rob word in wese dieselfde ding hier onder, sodat student beroof, en nou rob.id = 456, rob.name = "Rob." Die feit dat die veranderlike genoem Rob is 'n soort van betekenisloos. Ons kon genoem het nie x of y of z. Ons het net die naam dit Rob semanties konsekwent, maar werklik die naam is binnekant van die veld self, so nou het ek dit. Dit ook nie voel soos die beste ontwerp in die sin dat ek Dawid hard gekodeer. Ek het hard gekodeer Rob. En ek nog steeds 'n beroep tot 'n kopie en elke keer as ek wil nuwe veranderlikes te plak. Verder, ek het om te glo gee elk van hierdie veranderlikes 'n naam, alhoewel Ek wil veel eerder hierdie veranderlikes te beskryf  meer generies as studente. Nou het ons die idees wat is goed vir ons werk kan saamsmelt en in plaas daarvan sê, "Jy weet wat, gee my 'n veranderlike genoem studente, en laat ons dit van grootte 3, "so nou kan ek verfyn dit verder, ontslae te raak van die handmatig verklaar Dawid, en ek kan in plaas daarvan sê iets soos studente [0] hier. Ek kan dan sê studente [0] hier, studente [0] hier, en so meer, en ek kan gaan rond en skoon dat vir Rob. Ek kon ook gaan nou miskien die toevoeging van 'n lus en die gebruik van GetString en getint om werklik te kry hierdie waardes van die gebruiker. Ek kon gaan oor die toevoeging van 'n konstante, want dit is oor die algemeen swak praktyk hard-kode 'n arbitrêre getal soos 3 hier en dan net onthou dat jy nie meer as 3 studente moet in dit. Dit sou waarskynlik beter wees om te gebruik definieer # op die top van my lêer faktor wat uit, so wel, laat my gaan voort en veralgemeen hierdie. Laat my oop te maak 'n voorbeeld wat onder vandag se voorbeelde in advance, structs1. Dit is 'n meer volledige program wat gebruik maak van # define hier en sê ons gaan 3 studente te hê by verstek. Hier is ek verklaar 'n klas waarde van studente, so 'n klaskamer van die studente, en nou is ek met behulp van 'n lus net om die kode 'n bietjie meer elegante, vul die klas met die gebruiker se insette, so itereer van i = 0 op tot studente, wat 3. En dan het ek gevra om die gebruiker in hierdie weergawe  wat is die student se ID, en ek kry dit met getint. Wat is die student se naam, en dan kry ek dit met GetString. Wat is die student se huis? Ek kry dit met GetString. En dan op die bodem hier Ek het net besluit om te verander hoe ek dit gaan uit te druk en te gebruik en 'n lus, en wat ek druk? Volgens die kommentaar ek druk iemand in Mather, en dit is dit so Rob en Tommy en ensovoorts eintlik Tommy's in Mather. Tommy en Dawid sou in hierdie geval gedruk word, maar hoe word hierdie werk? Ons het nie gesien hierdie funksie voor, maar neem 'n raaiskoot as wat dit doen. Vergelyk snare. Dit is 'n bietjie nie-voor-die-handliggende hoe dit vergelyk snare, want dit blyk uit indien dit terugkeer 0 wat beteken dat die snare is gelyk. As dit gee 'n -1 dit beteken dat mens alfabeties kom voor die ander, en as dit terug 1 wat beteken dat die ander woord kom alfabeties voor die aangesig van die ander, en jy kan kyk aanlyn of by die man-bladsy om te sien presies watter manier is wat, maar dit alles nou doen, is dit sê indien die [i]. huis is gelyk aan "Mather" dan voort te gaan en druk uit so en so is in Mather. Maar hier is iets wat ons nie gesien het nie voor, en ons kom terug na hierdie. Ek kan nie onthou ooit om dit te doen in enige van my programme. Gratis blykbaar verwys na geheue, bevry geheue, maar wat die geheue Ek glo bevry in hierdie lus aan die onderkant van hierdie program? Dit lyk asof ek bevry van 'n persoon se naam en 'n persoon se huis, maar hoekom is dit? Dit blyk uit al die weke wat jy GetString al met behulp van ons het soort van die invoering van 'n fout in elke een van jou programme. GetString deur ontwerp ken geheue sodat dit kan terugkeer na jou 'n string, soos Dawid, of Rob, en jy kan doen wat jy wil dat die string in jou program, omdat ons die geheue vir jou het voorbehou. Die probleem is al die tyd elke keer as jy bel GetString ons die skrywers van GetString, is die bedryfstelsel te vra te gee vir ons 'n bietjie van die RAM vir hierdie string. Gee vir ons 'n bietjie van die RAM vir die volgende string. Gee vir ons 'n paar meer RAM vir die volgende string. Wat jou, die programmeerder, het nog nooit doen gee ons dat die geheue terug, so is dit vir hierdie paar weke van die programme wat jy geskryf het gehad het wat 'n geheue sprong genoem waardeur hulle hou die gebruik van meer en meer geheue elke keer as jy bel GetString, en dit is fyn. Ons het doelbewus doen wat in die eerste weke, want dit is nie so interessant hoef te bekommer oor waar die tou kom. Alles wat jy wil, is die woord Rob om terug te kom wanneer die gebruiker tipes. Maar vorentoe beweeg ons nou het om te begin om meer gesofistikeerde hieroor. Enige tyd wat ons geheue toeken ons beter handig dit uiteindelik terug. Anders in die werklike wêreld op jou Mac of PC wat jy kan soms ervaar simptome waar jou rekenaar maal tot stilstand uiteindelik of die dom spin strandbal is net wat op die rekenaar se volle aandag en jy kan nie die dinge doen. Dit kan verduidelik word deur 'n aantal foute, maar onder diegene moontlike foute is dinge geheue lekkasies genoem waardeur iemand wat daardie stukkie van die sagteware geskryf het wat jy gebruik het nie onthou om te vry geheue dat hy of sy gevra om die bedryfstelsel vir, nie die gebruik van GetString, want dit is 'n CS50 ding, maar deur gebruik te maak van soortgelyke funksies wat vra die bedryfstelsel vir die geheue. As jy of hulle skroef en nooit eintlik dat die geheue terug 'n simptoom van wat kan wees dat 'n program stadiger en stadiger en stadiger tensy jy onthou om te bel gratis. Ons kom terug na wanneer en waarom jy sou noem, maar laat voort te gaan net vir 'n goeie maatreël en probeer om hierdie spesifieke program. Dit is genoem structs1, tik. Laat my voort te gaan en uit te voer structs1, 123, David Mather, 456, Rob Kirkland, 789, Tommy Mather, en ons sien Dawid se in Mather, Tommy's in Mather. Dit is net 'n bietjie gesonde verstand check dat die program werk. Nou, helaas, hierdie program is 'n bietjie frustrerend in daardie Ek het alles wat werk, ek getik in 9 verskillende stringe, druk Enter meegedeel is wat in Mather, maar tog natuurlik ek het geweet wat was reeds in Mather omdat ek dit getik. Dit sou ten minste lekker wees as hierdie program is meer soos 'n databasis en dit onthou eintlik wat ek het getik in sodat ek nooit weer hierdie student rekords insette. Miskien is dit soos 'n registrarial stelsel. Ons kan dit doen met behulp van hierdie tegniek bekend as lêer I / O, lêer inset en uitset, 'n baie generiese manier om te sê enige tyd wat jy wil lêers te lees of lêers skryf kan jy dit doen met 'n sekere stel van funksies. Laat my voort te gaan en maak hierdie voorbeeld structs2.c, wat is byna identies, maar laat ons sien wat dit nou doen. Op die top van die lêer Ek verklaar 'n klas van studente. Ek dan vul die klas met die gebruiker se insette, so daardie reëls van die kode is presies voor te hou. Dan as ek scroll down hier het ek die druk van almal wat in Mather arbitrêr soos voorheen maar dit is 'n interessante nuwe funksie. Hierdie reëls van die kode is nuwe, en hulle voer iets hier, Lêer, alle pette, en dit het * hier sowel. Laat my beweeg dit hier, 'n * hier sowel. Hierdie funksie het ons nie gesien het nie voor, fopen, maar dit beteken lêer oop, so laat ons vlugtig deur hierdie, en dit is iets wat ons sal terug kom in die toekoms psets, maar hierdie lyn hier open in wese 'n lêer met die naam van databasis, en dit maak dit spesifiek in so 'n manier dat dit wat om dit te kan doen? [Onhoorbaar-student] Reg, sodat "w" beteken dit net die bedryfstelsel vertel Open hierdie lêer in so 'n manier dat ek kan skryf nie. Ek wil nie hê om dit te lees. Ek wil nie om net te kyk na dit. Ek wil om dit te verander en dinge potensieel voeg om dit te, en die lêer gaan word genoem databasis. Dit kan genoem word enigiets. Dit kan wees database.txt. Dit kan wees db. Dit kan 'n woord soos cat, maar ek arbitrêr besluit het die lêer databasis te noem. Dit is 'n bietjie gesonde verstand check dat ons sal terug kom in groot detail oor tyd, indien fp, vir die lêer wyser nie gelyk NULL wat beteken dat alles goed gaan. Lang storie kort, funksies soos fopen soms misluk. Miskien is die lêer nie bestaan ​​nie. Miskien is jy uit disketspasie. Miskien het jy nie toestemming om die gids, so as fopen terugkeer null iets sleg gebeur. Omgekeerd, indien fopen kom nie terug nie null alles is goed en ek kan begin deur skriftelik daarvoor aansoek te doen by hierdie lêer. Hier is 'n nuwe truuk. Dit is 'n for-lus wat iterating oor elk van my studente, en dit lyk so soortgelyk aan wat ons voorheen gedoen, maar hierdie funksie is 'n neef van printf genoem fprintf vir lêer printf, en let op dit is anders in net 2 maniere. Een, dit begin met f in plaas van p, maar dan is sy eerste argument is blykbaar wat? [Studente] File. >> Dit is 'n lêer. Hierdie ding genoem fp, wat ons uiteindelik uitmekaar te terg wat 'n lêer wyser is, maar vir nou fp verteenwoordig net die lêer wat ek oopgemaak het, so fprintf hier sê print hierdie gebruiker se ID na die lêer, nie na die skerm. Druk die gebruiker se naam na die lêer, nie op die skerm, die huis na die lêer, nie op die skerm, en dan hier, natuurlik, maak die lêer, en dan af hier gratis aan die geheue. Die enigste verskil tussen hierdie weergawe 2 en weergawe 1 is die bekendstelling van die fopen en hierdie lêer met 'n * en hierdie idee van fprintf, so laat ons sien wat die eindresultaat is. Laat my gaan in my terminale venster. Laat ek hardloop structs2, tik. Lyk soos dit is alles goed. Laat se heruitzend structs2. 123, David Mather, 456, Rob Kirkland, 789, Tommy Mather, betree. Lyk asof dit Gedra hulle dieselfde, maar as ek nou doen ls Let op watter lêer is hier onder my hele kode, databasis, so laat dat gedit van die databasis, en kyk na wat oop. Dit is nie die sexyste van lêer formate. Dit is regtig 'n stuk van die data lyn per lyn per lyn, maar dié van julle wat Excel of CSV-lêers gebruik, deur kommas geskei waardes, Ek kon seker fprintf gebruik het om plaas miskien iets soos hierdie te doen sodat ek kon eintlik die ekwivalent van 'n Excel-lêer skep deur dinge met kommas, nie net nuwe lyne te skei. In hierdie geval het as ek eerder gebruik kommas in plaas van nuwe lyne Ek kon letterlik hierdie databasis lêer oopmaak in Excel as ek plaas dit so lyk. In kort, nou dat ons die mag het om te skryf aan lêers kan ons nou begin volgehoue ​​data, hou dit rond op die skyf sodat ons inligting kan hou om weer en weer. Let op 'n paar ander dinge wat nou 'n bietjie meer vertroud. Op die top van die C-lêer het ons het 'n typedef want ons wou 'n datatipe wat 'n woord te skep, sodat hierdie tipe genoem woord, en binnekant van die struktuur dit is nou 'n bietjie liefhebber. Hoekom is 'n woord wat blykbaar 'n verskeidenheid? Wat is 'n woord net intuïtief? Dit is 'n verskeidenheid van die karakters. Dit is 'n reeks van karakters terug Terug na. Hoofletters gebeur om te wees ons arbitrêr sê die maksimum lengte van 'n woord in die woordeboek wat ons gebruik vir Scramble. Waarom het ek nie 'n 1? Die null karakter. Onthou wanneer ons het die Bananagrams voorbeeld wat ons nodig het 'n spesiale waarde aan die einde van die woord ten einde tred te hou waar woorde eintlik geëindig, en as die probleem stel spesifikasie sê hier is ons assosieer met 'n gegewe woord 'n Boolese waarde, 'n vlag, om so te praat, waar of vals is. Het jy hierdie woord gevind het, omdat ons besef ons regtig nodig het nie net 'n manier om te onthou wat 'n woord in die Scramble maar of jy nie, die mens, het gevind dat dit sodat as jy nie kry die woord "die" jy kan net tik nie, voer, die voer, die voer en kry 3 punte 3 punte 3 punte 3 punte. Ons wil in staat wees om daardie woord aan ander Wil jy deur die opstel van 'n Bool op waar as jy reeds daar gevind, en so dit is die rede waarom ons vervat in hierdie struktuur. Nou, af hier in Scramble daar is hierdie ander struct genoem woordeboek. Afwesig hier is die woord typedef want in hierdie geval ons nodig het om die idee van 'n woordeboek te omsluit, en 'n woordeboek bevat 'n hele klomp van die woorde, soos geïmpliseer deur hierdie verskeidenheid, en hoeveel van daardie woorde is daar? Wel, wat hierdie veranderlike genoem grootte sê. Maar ons hoef net 'n woordeboek. Ons hoef nie 'n data tipe genoem woordeboek. Ons hoef net een van hulle, so dit blyk in C dat as jy nie sê nie typedef, jy moet net sê struct, dan binne-in die kode tussen krulhakies jy jou veranderlikes, dan kan jy die naam. Dit is waarby een veranderlike genoem woordeboek wat lyk soos hierdie. In teenstelling hiermee, is hierdie lyne die skep van 'n herbruikbare data struktuur genoem woord dat jy kan skep veelvuldige kopieë van, net soos ons geskep veelvuldige kopieë van studente. Wat beteken dit uiteindelik toelaat dat ons te doen? Laat my gaan terug in, kom ons sê, 'n eenvoudiger voorbeeld uit eenvoudiger tye, en laat my oop te stel, laat ons sê, compare1.c. Die probleem hier by die hand is om werklik te skil terug die laag van 'n string en begin om hierdie opleiding wiele af omdat dit blyk dat 'n string al die tyd soos ons belowe in week 1 regtig net 'n bynaam, 'n sinoniem van die CS50 biblioteek vir iets wat lyk 'n bietjie meer kriptiese, char *, en ons het gesien dat hierdie ster voor. Ons het dit gesien in die konteks van lêers. Kom ons nou sien waarom ons het weggekruip hierdie detail vir 'n geruime tyd nou. Hier is 'n lêer genaamd compare1.c, en dit vra blykbaar die gebruiker vir 2 snare, s en t, en dan is dit probeer om die snare te vergelyk vir gelykheid in line 26, en as hulle gelyke dit sê, "Jy getik dieselfde ding," en as hulle nie gelyke dit sê, "Jy getik verskillende dinge." Laat my hierdie program voort te gaan en uit te voer. Laat my gaan in my bron directory, maak 'n compare1. Dit saamgestel okay. Laat ek hardloop compare1. Ek sal zoom in, tik. Iets sê. Hello. Ek sal weer iets sê. Hello. Ek het beslis nie tik verskillende dinge. Kom ek probeer dit weer. Bye bye. Beslis nie anders, so wat gaan hier aan? Wel, regtig wat vergelyk word in lyn 26? [Onhoorbaar-student] Ja, so dit blyk dat 'n string, data tipe, is 'n soort van 'n wit leuen. 'N string is 'n char *, maar wat is 'n char *? 'N char *, soos hulle sê, is 'n wyser, en 'n wyser is effektief 'n adres, 'n som plek in die geheue, en as jy gebeur om getik in 'n woord soos HELLO, onthou uit vorige besprekings van snare dit is soos die woord Hello. Onthou dat 'n woord soos HELLO voorgestel kan word as 'n verskeidenheid van karakters soos hierdie en dan met 'n spesiale karakter aan die einde genoem die null karakter, as die \ dui. Wat is eintlik 'n string? Let daarop dat hierdie is verskeie stukke van die geheue, en in werklikheid, is net die einde van dit bekend wanneer jy kyk deur die hele string soek vir die spesiale null karakter. Maar as dit is 'n stuk van die geheue van my rekenaar se geheue, laat ons na willekeur sê dat hierdie string het net gelukkig, en dit het heel aan die begin van my rekenaar se RAM geplaas. Dit is byte 0, 1, 2, 3, 4, 5, 6 ... Wanneer ek iets sê soos GetString en ek doen string s = GetString wat werklik terug? Vir die afgelope paar weke, is regtig wat gestoor word in s hierdie string per se is nie, maar in hierdie geval wat gestoor is die getal 0 want wat GetString eintlik nie is dit nie fisies nie terugkeer nie 'n string. Wat nie eens werklik konseptuele sin maak. Wat beteken dit terugkeer is 'n getal. Dat die nommer is die adres van Hello in die geheue, en string s dan, as ons hierdie laag skil terug, string nie regtig bestaan ​​nie. Dit is slegs 'n vereenvoudiging in die CS50 biblioteek. Dit is regtig iets genoem char *. Char sin maak, want wat is 'n woord, soos HELLO? Wel, dit is 'n reeks van karakters, 'n reeks van karakters. Char * beteken die adres van 'n karakter, so wat beteken dit 'n string om terug te keer? 'N mooi, eenvoudige manier van die terugkeer van 'n string is eerder as om te probeer om uit te vind hoe ek terugkeer na 5 of 6 verskillende grepe laat my terug te keer na die adres wat byte? Die eerste een. Met ander woorde, laat my gee u die adres van 'n karakter in die geheue. Dit is wat char *, die adres van 'n enkele karakter in die geheue. Noem dat die veranderlike s. Store in s dat spesifieke adres, wat ek arbitrêr gesê is 0, net om dinge eenvoudig te hou, maar in werklikheid is dit is oor die algemeen 'n groter getal. Wag 'n minuut. As jy net gee my die adres van die eerste karakter, hoe kan ek weet wat die adres is van die tweede karakter, die derde, die vierde en die vyfde? [Onhoorbaar-student] Jy moet net weet waar die einde van die string is deur middel van hierdie handige trick, so wanneer jy iets soos printf, wat neem printf letterlik as sy argument, onthou dat ons hierdie% s place holder, en dan sal jy slaag in die veranderlike wat die stoor van 'n string. Wat jy regtig verby is die adres van die eerste karakter van die string. Printf gebruik dan 'n lus of 'n while lus na ontvangs van daardie adres, byvoorbeeld, 0, so laat ek dit nou doen, printf ("% s \ n" s); As ek roep printf ("% s \ n" s), wat ek regtig die verskaffing van printf met is die adres van die eerste karakter in, wat in hierdie arbitrêre geval is H. Hoe printf weet presies wat om te vertoon op die skerm? Die persoon wat geïmplementeer printf geïmplementeer om 'n while lus of 'n for-lus wat sê dat hierdie karakter gelyk aan die spesiale null karakter? Indien nie, druk dit. Hoe gaan dit met hierdie een? As dit nie druk nie, druk dit, druk dit, druk dit. O, hierdie een is spesiaal. Stop druk en terug te keer na die gebruiker. En dit is letterlik alles wat gebeur onder die kap, en dit is 'n baie om te verteer in die eerste dag van 'n klas, maar vir nou is dit regtig die bousteen van begrip alles wat gaan op die binnekant van ons rekenaar se geheue, en uiteindelik sal ons terg hierdie apart met 'n bietjie hulp van een van ons vriende by Stanford. Professor Nick Parlante by Stanford het hierdie wonderlike video volgorde gedoen van alle vorme van verskillende tale wat lei hierdie klein Claymation karakter Binky. Die stem wat jy oor om te hoor in net 'n paar tweede sneak preview is dié van 'n Stanford professor, en jy kry net 5 of 6 sekondes van hierdie reg nou, maar dit is die noot waarop ons sal sluit vandag en begin op Woensdag. Ek gee jou Pointer Pret met Binky, die voorskou. [♪ Musiek ♪] [Professor Parlante] Hey, Binky. Wakker word nie. Dis tyd vir pointer pret. [Binky] Wat is dit? Meer inligting oor die wenke? O, goody! Ons sal sien dat jy op Woensdag. [CS50.TV]