[Powered by Google Translate] [Uge 6, Fortsat] [David J. Malan] [Harvard University] [Dette er CS50.] [CS50.TV] Dette er CS50, og det er i slutningen af ​​uge 6. Så CS50x, en af ​​Harvards første kurser er involveret i EDX-initiativet faktisk debuterede denne sidste mandag. Hvis du ønsker at få et glimt af, hvad andre på internettet følger nu sammen med, kan du hovedet til x.cs50.net. Det vil omdirigere dig til det korrekte sted på edx.org, som var hvor dette og andre kurser fra MIT og Berkeley nu bor. Du bliver nødt til at tilmelde dig en konto, vil du opdage, at materialet er stort set den samme som du har haft dette semester, omend et par forsinkede uger, da vi få alt klar. Men hvad studerende i CS50x vil nu se er en grænseflade helt som denne. Dette er for eksempel Zamyla spidsen for gennemgang for problemet set 0. Når du logger ind på edx.org, ser en CS50x elev den slags ting du ville forvente at se i et kursus: forelæsningen for mandag, foredrag for onsdag, diverse shorts, problemet sæt, walkthroughs, PDF-filer. Hertil kommer, som du ser her, maskinoversættelser af engelske udskrifter til kinesisk, japansk, spansk, italiensk, og en hel masse andre sprog, som vil helt sikkert være ufuldkommen da vi ruller dem ud programmeringsmæssigt bruge noget, der hedder en API, eller application programming interface, fra Google der giver os mulighed for at konvertere engelsk til disse andre sprog. Men takket være den vidunderlige ånd af nogle hundrede plus frivillige, tilfældige mennesker på internettet, der har venligt tilbudt at få inddraget i dette projekt, vil vi gradvist forbedre kvaliteten af ​​disse oversættelser ved at have mennesker rette de fejl, som vores computere har gjort. Så det viser sig, at vi havde nogle flere elever dukke op på mandag, end vi oprindeligt forventede. Faktisk CS50x nu har 100.000 mennesker følger langs derhjemme. Så indser du er alle en del af denne indledende klasse for at gøre dette kursus i datalogi uddannelse mere generelt, mere generelt, tilgængelige. Og virkeligheden er nu, med nogle af disse massive online-kurser, de alle starter med disse meget høje tal, da vi synes at have gjort her. Men målet i sidste ende for CS50x virkelig at få så mange mennesker til målstregen som muligt. Ved design er CS50x vil blive tilbudt fra denne sidste mandag hele vejen gennem 15 April, 2013, således at folk, der har skolen forpligtelser andre steder, arbejde, familie, andre konflikter og lignende, har en smule mere fleksibilitet som at dykke ned i dette kursus, som er det tilstrækkeligt at sige, er ganske ambitiøst gjort, hvis blot i løbet af blot tre måneder i løbet af en sædvanlig semester. Men disse studerende vil tackle det samme problem sæt, ser det samme indhold, har adgang til de samme shorts og lignende. Så indse, at vi er alle virkelig i denne sammen. Og en af ​​de endelige mål CS50x er ikke bare at få så mange folk til målstregen og give dem denne nyfundne forståelse af datalogi og programmering, men også at få dem har denne fælles oplevelse. Et af de vigtigste kendetegn ved 50 på campus, håber vi, har været denne slags fælles oplevelse, for bedre eller værre, til tider, men som har disse mennesker til at vende sig til venstre og til højre, og kontor timer og hackathon og retfærdig. Det er lidt sværere at gøre det personligt med folk online, men CS50x vil indgå i april med den første nogensinde CS50 Expo, som vil være en online tilpasning af vores idé om messen hvor disse tusindvis af studerende vil alle blive opfordret til at indsende et 1 - til 2-minutters video, enten en screencast af deres afsluttende projekt eller video af dem vinke goddag og taler om deres projekt og demoing det, meget gerne dine forgængere har gjort her på campus i messen, så vi ved semesters ende, er det håbet at få en global udstilling af de CS50x studerendes afgangsprojekter, der meget gerne, der venter dig i december her på campus. Så mere om det i de kommende måneder. Med 100.000 studerende, dog kommer et behov for nogle flere kompetente myndigheder. Da du fyre rasende sporet her og tage CS50 flere uger i forvejen af ​​dette materiale udgivelse til folk på EDX, indser vi ville elske at involvere så mange af vores egne studerende som muligt i dette initiativ, både i løbet af semesteret samt denne vinter og det kommende forår. Så hvis du gerne vil blive involveret i CS50x, især at deltage i den CS50x Diskuter, at EDX versionen af ​​CS50 diskutere, som mange af jer har brugt på campus, online opslagstavle, bedes du hovedet til den pågældende webadresse, så lad os vide, hvem du er, fordi vi ville elske at opbygge et hold af studerende og ansatte og fakultet både på campus, der er blot at spille sammen og hjælpe. Og når de ser et spørgsmål, som er velkendt for dem, du hører en studerende rapporterer nogle fejl et eller andet sted derude i nogle land på internettet, og at ringe en klokke, fordi du også havde det samme problem i din d-hallen for nogen tid siden, så forhåbentlig kan du kime i og dele dine egne erfaringer. Så er du deltage, hvis du ønsker. Datalogikurser på Harvard har lidt af en tradition, CS50 blandt dem, for at have nogle tøj, noget tøj, som du kan bære med stolthed ved semesters ende, siger ganske stolt, at du færdig CS50 og tog CS50 og lignende, og vi forsøger altid at involvere de studerende i denne proces så meget som muligt, hvorved vi inviterer, omkring denne tid af semestret, at de studerende indsende designs ved hjælp af Photoshop, eller hvad foretrukne værktøj, du gerne vil bruge hvis du er en designer, til at indsende designs til T-shirts og sweatshirts og paraplyer og små bandanas til hunde vi nu har og lignende. Og alt er så - vinderne hvert år derefter udstillet på kursets hjemmeside store.cs50.net. Alt sælges til kostpris der, men hjemmesiden bare kører selv og giver folk mulighed for at vælge de farver og mønstre, som de kan lide. Så jeg troede, vi ville bare dele nogle af sidste års designs der var på hjemmesiden foruden denne ene her, som er en årlig tradition. "Hver dag jeg Seg Faultn" var et af de indlæg sidste år, som stadig er til rådighed der for alumner. Vi havde denne ene, "CS50, Etableret 1989." En af vores Bowdens, Rob, var meget populær sidste år. "Team Bowden" blev født, blev dette design fremlagt, blandt de bedste sælgere. Som det var denne her. Mange mennesker havde "Bowden Fever" i henhold til salgs-logs. Indse, at det nu kunne være din design der, op på internettet. Flere detaljer om dette i næste problem sæt til at komme. En mere værktøj: du har haft en vis eksponering og forhåbentlig nu nogle hands-on erfaring med GDB, der er naturligvis en debugger og giver dig mulighed for at manipulere Deres program på et forholdsvis lavt niveau, gør hvad slags ting? Hvad betyder GDB lade dig gøre? Ja? Giv mig noget. [Student svar, uforståelig] Godt. Træd ind funktion, så du ikke bare nødt til at skrive løbe og få programmet slag gennem sin helhed, udskrive ting til standard output. I stedet kan du gå gennem den linje for linje, enten skrive næste at gå linje for linje for linje eller skridt til at dykke ind i en funktion, typisk en, som du skrev. Hvad ellers gør GDB lade dig gøre? Ja? [Student svar, uforståelig] Print variabler. Så hvis du ønsker at gøre lidt selvransagelse inde i dit program uden at skulle ty til at skrive printf udsagn over det hele, kan du bare udskrive en variabel eller vise en variabel. Hvad kan du ellers gøre med en debugger som GDB? [Student svar, uforståelig] Præcis. Du kan indstille breakpoints, og du kan sige break udførelse på de vigtigste funktion eller foo funktionen. Du kan sige break udførelse på linie 123. Og breakpoints er en virkelig kraftfuld teknik fordi hvis du har en generel fornemmelse af, hvor dit problem sandsynligvis er, behøver du ikke at spilde tiden med at gå gennem programmets helhed. Du kan i det væsentlige hoppe lige der og derefter begynde at skrive - trinvist gennem det med trin eller næste eller lignende. Men fangsten med noget lignende GDB er, at det hjælper dig, det menneskelige, finde dine problemer og finde dine fejl. Det behøver ikke nødvendigvis finde dem så meget for dig. Så vi introducerede den anden dag style50, som er en kort kommandolinjeværktøj der forsøger at stilisere din kode en lille smule mere rent, end du, det menneskelige, kan have gjort. Men det også er egentlig bare en æstetisk ting. Men det viser sig, der er denne anden værktøj kaldet Valgrind der er lidt mere mystisk at bruge. Dens output er afskyeligt kryptisk ved første øjekast. Men det er vidunderligt nyttigt, især nu, hvor vi er på den del af udtrykket hvor du begynder at bruge malloc og dynamisk allokering af hukommelse. Ting kan gå rigtig, rigtig galt hurtigt. For hvis du glemmer at frigøre din hukommelse, eller du dereference nogle NULL pointer, eller du dereference nogle skrald pointer, hvad er typisk symptom, at resultaterne? Seg fejl. Og du får denne core fil af nogle antal kilobytes eller megabytes der repræsenterer tilstanden af ​​dit program hukommelse, når det styrtede ned, men dit program i sidste ende seg fejl, segmenteringsfejl, som betyder noget slemt skete næsten altid relateret til en memory-relateret fejl, du har foretaget et eller andet sted. Så Valgrind hjælper dig med at finde ting som dette. Det er et værktøj, som du løber, ligesom GDB, efter du har kompileret din program, men i stedet for at køre dit program direkte, du kører Valgrind og du sender til det dit program, ligesom du gør med GDB. Nu brug, for at få den bedste form for produktion, er lidt lang, så lige der på toppen af ​​skærmen kan du se Valgrind-v. "-V" næsten universelt betyder verbose, når du bruger programmer på en Linux-computer. Så det betyder spytte ud flere data end du måske som standard. "- Lækage-check = fuld." Dette er bare at sige check for alle mulige memory leaks, fejl, som jeg kunne have gjort. Også dette er en fælles paradigme med Linux programmer. Generelt, hvis du har en kommandolinje argument, er en "switch", der er meningen at ændre programmets opførsel, og det er et enkelt bogstav, Det er-v, men hvis der er tændt, lige ved design af programmeringsenheden er en komplet ord eller en række ord kommandolinjen argument starter med -. Disse er blot menneskelige konventioner, men du vil se dem i stigende grad. Og så, endelig, "a.out" er vilkårligt navn til programmet i dette særlige eksempel. Og her er nogle repræsentative output. Før vi ser på, hvad det kan betyde, lad mig gå over til en kodestykke herovre. Og lad mig flytte dette ud af den måde, kommer snart, og lad os tage et kig på memory.c, hvilket er denne korte eksempel her. Så i dette program, så lad mig zoome ind på de funktioner og spørgsmål. Vi har en funktion main der kalder en funktion, f, og så hvad betyder f skride til at udføre, i en lidt teknisk engelsk? Hvad betyder f fortsætte at gøre? Hvad med at jeg vil starte med linje 20, og stjernens placering betyder ikke noget, men jeg vil bare være i overensstemmelse her med sidste foredrag. Hvad er linje 20 gør for os? På den venstre side. Vi vil bryde det ned yderligere. Int * x: hvad betyder det så? Okay. Det er at erklære en pegepind, og lad os nu være endnu mere teknisk. Hvad betyder det, meget konkret, at erklære en pointer? Nogen andre? Ja? [Student svar, uforståelig] For langt. Så du læser til højre side af lighedstegnet. Lad os nøjes med at fokusere på den venstre, bare på int * x. Det betyder "angive" en pegepind, men nu lad os dykke dybere til denne definition. Hvad betyder det konkret, teknisk betyde? Ja? [Student svar, uforståelig] Okay. Det er klar til at gemme en adresse i hukommelsen. Godt. Og lad os tage et skridt videre, det er at erklære en variabel, x, der er 32 bit. Og jeg ved, det er 32 bit, fordi -? Det er ikke fordi det er en int, fordi det er en pointer i denne sag. Tilfældighed, at det er én og samme med en int, men det faktum, at der er den stjerne der betyder det er en pegepind og i apparatet, som med mange computere, men ikke alle, pointers er 32 bits. På mere moderne hardware som de nyeste Mac-computere, de nyeste pc'er, kan du have 64-bit pointers, men i apparatet, er disse ting 32 bit. Så vi vil standardisere på det. Mere konkret historien går som følger: Vi "erklærer" en pegepind, hvad betyder det? Vi forbereder at gemme et memory-adresse. Hvad betyder det? Vi opretter en variabel kaldet x, der fylder 32 bits der snart vil gemme adressen på et heltal. Og det er nok lige så præcis, som vi kan få. Det er fint at gå videre til at forenkle verden og bare sige erklære en pointer kaldet x. Erklær en pegepind, men indse og forstå, hvad der rent faktisk sker endda på bare de få tegn. Nu, denne ene er næsten lidt nemmere, selvom det er en længere udtryk. Så hvad er dette gør, det er fremhævet nu: "malloc (10 * sizeof (int));" Ja? [Student svar, uforståelig] Godt. Og jeg vil tage det der. Det er allokering af en luns af hukommelse for ti heltal. Og lad os nu dykke i lidt dybere, det er at afsætte en luns af hukommelse for ti heltal. Hvad er malloc derefter vende tilbage? Adressen på denne chunk, eller mere konkret, adressen på den første byte af denne luns. Hvordan skal jeg, programmøren, at vide, hvor denne bid af hukommelse ender? Jeg ved, at det er sammenhængende. Malloc, per definition, vil give dig en sammenhængende luns af hukommelsen. Ingen huller i det. Du har adgang til alle byte i denne bid, tilbage til ryg mod ryg, men hvordan kan jeg vide, hvis udgangen af ​​denne luns af hukommelse er? Når du bruger malloc? [Student svar, uforståelig] Godt. Du behøver ikke. Du er nødt til at huske. Jeg er nødt til at huske, at jeg brugte værdien 10, og jeg ved ikke engang synes at have gjort det her. Men påhviler det udelukkende på mig. Strlen, som vi er blevet lidt afhængige af for strygere, virker kun på grund af denne konvention for at have \ 0 eller denne specielle nøglesekvens, NUL, ved slutningen af ​​en streng. Det holder ikke for bare vilkårlige bidder af hukommelsen. Det er op til dig. Så linie 20, og derefter tildeler en luns af hukommelse der kan lagre ti heltal, og det gemmer adressen af ​​den første byte af denne luns af hukommelse i variabel kaldet x. Ergo, som er en henvisning. Så linie 21, der desværre var en fejl. Men først, hvad det gør? Det siger butik på placering 10, indekseret 0, af bid af hukommelse kaldet x værdien 0. Så bemærke et par ting der foregår. Selvom x er en pegepind, huske fra et par uger siden at du stadig kan bruge array-stil firkantet beslag notation. Fordi det er faktisk kort hånd notation for den mere kryptiske udseende pointer aritmetik. hvor vi ville gøre noget som dette: Tag adressen x, flytte 10 pletter over, derefter gå der til, hvad adressen er gemt på den pågældende placering. Men helt ærligt, det er bare skrækkeligt at læse og blive fortrolig med. Så verden bruger typisk de firkantede parenteser, bare fordi det er så meget mere menneske-venlig at læse. Men det er, hvad der virkelig foregår under motorhjelmen; x er en adresse, ikke et array, per se. Så dette er lagring 0 ved placering 10 i x. Hvorfor er det dårligt? Ja? [Student svar, uforståelig] Præcis. Vi kun afsat ti int'er, men vi tæller fra 0, når programmering i C, så du har adgang til 0 1 2 3 4 5 6 7 8 9, men ikke 10. Så enten programmet kommer til at seg fejl eller det er ikke. Men vi ved ikke rigtig, det er en slags nondeterministic adfærd. Det er virkelig afhænger af, om vi heldige. Hvis det viser sig, at operativsystemet ikke noget imod, hvis jeg bruger det ekstra byte, selv om det ikke har givet den til mig, kan mit program ikke gå ned. Det er rå, det er buggy, men du kan ikke se, at symptom, eller du kan se det kun en gang imellem. Men virkeligheden er, at fejlen er i virkeligheden der. Og det er virkelig problematisk, hvis du har skrevet et program, som du ønsker at være korrekte, at du har solgt det program, folk bruger, at hver gang i et stykke tid går ned fordi, selvfølgelig, er det ikke godt. Faktisk, hvis du har en Android-telefon eller en iPhone og du downloader apps i disse dage, hvis du nogensinde har haft en app bare afslutte, pludselig det forsvinder, det er næsten altid et resultat af nogle hukommelse-relaterede spørgsmål, hvorved programmøren skruet op og derefereret en pegepind at han eller hun ikke skulle have, og resultatet af iOS eller Android er bare at dræbe programmet helt snarere end at risikere udefinerede adfærd eller anden form for sikkerhed kompromis. Der er en anden fejl i dette program udover denne ene. Hvad andet har jeg skruet op i dette program? Jeg har ikke praktiseret, hvad jeg har prædiket. Ja? [Student svar, uforståelig] Godt. Jeg har ikke befriet hukommelsen. Så tommelfingerregel nu skal være når som helst du kalder malloc, skal du ringe gratis, når du er færdig med at bruge denne hukommelse. Nu ville da jeg ønsker at frigøre denne hukommelse? Sandsynligvis, forudsat denne første linje var korrekt, ville jeg ønsker at gøre det her. Fordi jeg ikke kunne for eksempel gøre det hernede. Hvorfor? Lige uden for rækkevidde. Så selv om vi taler om pegepinde, dette er en uge 2 eller 3 spørgsmål, hvor x er kun i omfang indersiden af ​​krøllede parenteser, hvor det blev anmeldt. Så du absolut ikke kan frigøre det der. Min eneste chance for at frigøre det er nogenlunde efter linie 21. Dette er en forholdsvis simpelt program, det var temmelig nemt, når du slags indpakket dit sind omkring, hvad programmet laver, hvor de fejl var. Og selvom du ikke se det i første omgang, forhåbentlig det er lidt indlysende nu at disse fejl er temmelig nemt løses og nemt gjort. Men når et program er mere end 12 linjer lang, det er 50 linjer lang, 100 linjer lang, gå gennem din kode linje for linje, tænker igennem det logisk, er mulig, men ikke særlig sjovt at gøre, konstant på udkig efter bugs, og det er også vanskeligt at gøre, og det er derfor et værktøj som Valgrind eksisterer. Lad mig gå videre og gøre det: Lad mig åbne min terminal vindue, og lad mig ikke bare køre hukommelse, fordi hukommelsen ser ud til at være fint. Jeg bliver heldig. Gå til den ekstra byte ved udgangen af ​​arrayet synes ikke at være for problematisk. Men lad mig alligevel, gøre en tilregnelighed check, hvilket betyder bare at checke hvorvidt dette faktisk er korrekt. Så lad os gøre Valgrind-v - lækage-check = fuld, og derefter navnet på det program, i dette tilfælde er hukommelse, ikke a.out. Så lad mig gå videre og gøre det. Hit på Enter. Kære Gud. Det er sin produktion, og dette er hvad jeg hentydede til tidligere. Men, hvis du lærer at læse igennem alle de pjat her, det meste af dette er bare diagnostisk output, der er ikke så interessant. Hvad øjet virkelig ønsker at være på udkig efter, er enhver omtale af fejl eller ugyldig. Ord, der tyder på problemer. Og ja, lad os se hvad der går galt hernede. Jeg har en sammenfatning af en slags, "i brug ved afkørsel:. 40 bytes i 1 blokke" Jeg er ikke rigtig sikker på, hvad en blok er endnu, men 40 bytes faktisk føles som om jeg kunne finde ud af hvor det kommer fra. 40 bytes. Hvorfor er 40 bytes i brug ved afkørsel? Og mere specifikt, hvis vi rulle ned her, hvorfor har jeg absolut mistet 40 bytes? Ja? [Student svar, uforståelig] Perfect. Ja, præcis. Der var ti heltal, og hvert af dem er størrelse på 4 eller 32 bit, så jeg har mistet netop 40 bytes fordi, som du foreslog, har jeg ikke kaldt fri. Det er en fejl, og nu lad os se lidt længere ned og se ud for dette, "Ugyldig skrive størrelse 4". Hvad er nu det? Denne adresse er udtrykt hvad basis notation, tilsyneladende? Det er hexadecimal, og hver gang du ser en række starter med 0x, det betyder hexadecimal, som vi gjorde helt tilbage i, tror jeg, Pset 0 sektion af spørgsmål, der var lige til at gøre en opvarmning øvelse, konvertere decimal til hex til binær og så videre. Hexadecimal, blot ved menneskelig konvention, der normalt bruges til at repræsentere pointers eller mere generelt, adresser. Det er bare en konvention, fordi det er lidt lettere at læse, det er lidt mere kompakt end noget som decimal, og binære er ubrugelig for de fleste mennesker at bruge. Så nu hvad betyder det? Tja, det ser ud som om der er en ugyldig skrive af størrelse 4 på linie 21 i memory.c. Så lad os gå tilbage til linie 21, og ja, her er det ugyldigt skrive. Så Valgrind vil ikke helt holde min hånd og fortælle mig, hvad rettelsen er, men det er at opdage, at jeg gør en ugyldig skrive. Jeg rører 4 byte, at jeg ikke skulle være, og tilsyneladende er det fordi, som De påpegede, jeg gør [10] i stedet for [9] maksimalt eller [0] eller noget midt imellem. Med Valgrind, indser enhver tid du nu skriver et program der bruger pegepinde og bruger hukommelse, og allokere mere specifikt, definitivt komme ind i vane med at køre denne lange men meget nemt kopieres og indsættes kommandoen over Valgrind at se om der er nogle fejl i det. Og det vil være overvældende, hver gang du ser output, men bare parse igennem visuelt hele produktionen og se om du ser omtaler af fejl eller advarsler eller ugyldigt eller tabt. Ethvert ord, der lyder som om du skruet op et eller andet sted. Så indse at det er et nyt værktøj i din værktøjskasse. Nu på mandag, havde vi en hel masse folk herop og repræsenterer forestillingen om en linket liste. Og vi introducerede den linkede liste som en løsning på det problem? Ja? [Student svar, uforståelig] Godt. Arrays kan ikke have hukommelse, der tilføjes til dem. Hvis du tildeler en vifte af størrelse 10, det er alt du får. Du kan kalde en funktion som realloc hvis du oprindeligt kaldet malloc, og som kan forsøge at dyrke arrayet, hvis der er plads mod slutningen af ​​den at ingen andre bruger, og hvis der ikke er, vil det bare finde dig en større luns et andet sted. Men så vil det kopiere alle disse bytes i den nye array. Det lyder som en meget korrekt løsning. Hvorfor er dette utiltrækkende? Jeg mener det virker, har mennesker løst dette problem. Hvorfor har vi brug for at løse det på mandag med hægtede lister? Ja? [Student svar, uforståelig] Det kan tage lang tid. Faktisk, hver gang du kalder malloc eller realloc eller calloc, som er endnu et helst du, programmet, taler til operativsystemet, du har tendens til at bremse programmet ned. Og hvis du laver den slags ting i sløjfer, du virkelig langsommere ting ned. Du kommer ikke til at bemærke dette, for den enkleste af "Hello World" type programmer, men i meget større programmer, spørger operativsystemet igen og igen for hukommelse eller giver det tilbage igen og igen tendens til ikke at være en god ting. Plus, det er bare slags intellektuelt - det er et komplet spild af tid. Hvorfor afsætte mere og mere hukommelse, risiko kopiering alt ind i det nye array, hvis du har et alternativ, der giver dig mulighed afsætter kun så meget hukommelse som du rent faktisk har brug for? Så der er plusser og minusser i her. En af plusser nu er, at vi har dynamik. Gør ikke noget, hvor bidder af hukommelse er der er gratis, Jeg kan bare slags skabe disse brødkrummer via pointers at strengen hele min linkede liste sammen. Men jeg betaler mindst én pris. Hvad skal jeg give op med at få hægtede lister? Ja? [Student svar, uforståelig] Godt. Du har brug for mere hukommelse. Nu har jeg brug for plads til disse pejlemærker, og i tilfælde af denne super enkle forbundet liste der er kun forsøger at gemme heltal, som er 4 bytes, vi holder siger godt, en pointer er 4 bytes, så nu har jeg bogstaveligt talt fordoblet mængden af ​​hukommelse jeg har brug for bare at gemme denne liste. Men igen, dette er en konstant afvejning i datalogi mellem tid og rum og udvikling, indsats og andre ressourcer. Hvad er en anden Ulempen ved at anvende et sammenkædet liste? Ja? [Student svar, uforståelig] Godt. Ikke så let at få adgang. Vi kan ikke længere gearing uge 0 principper som del og hersk. Og mere specifikt binær søgning. For selvom vi mennesker kan se nogenlunde, hvor midten af ​​denne liste er, computeren kun ved, at dette linkede liste starter ved adresse kaldet først. Og det er 0x123 eller sådan noget. Og den eneste måde, hvorpå programmet kan finde den midterste element er rent faktisk at søge på hele listen. Og selv da, er det bogstaveligt talt nødt til at søge i hele listen, fordi selv når du når den midterste element ved at følge pegepinde, dig, at programmet, har ingen idé om, hvor længe denne liste er potentielt indtil du rammer slutningen af ​​det, og hvordan kan du vide programmeringsmæssigt at du er i slutningen af ​​en linket liste? Der er en speciel NULL pointer, så igen, en konvention. Snarere end at bruge denne pegepind, vi absolut ikke ønsker det at være nogle garbage værdi peger scenen et eller andet sted, vi ønsker det skal være hånd ned, NULL, således at vi har denne endestation i denne datastruktur, så vi ved, hvor det ender. Hvad hvis vi ønsker at manipulere dette? Vi gjorde det meste af denne visuelt og med mennesker, men hvad nu, hvis vi ønsker at gøre en insertion? Så den oprindelige liste var 9, 17, 20, 22, 29, 34. Hvad hvis vi derefter ønskede at allokere plads til nummer 55, en node for det, og så må vi ønsker at indsætte 55 i listen, ligesom vi gjorde i mandags? Hvordan gør vi det? Nå, Anita kom op og hun hovedsagelig gik på listen. Hun begyndte på det første element, så den næste, det næste, det næste, det næste, det næste. Endelig ramte den venstre hele vejen ned og realiseret åh, det er NULL. Så hvad pointer manipulation måtte gøres? Den person, der var på slutningen, nummer 34, havde brug for hans venstre hånd hævet at pege på 55, 55 havde brug for deres venstre arm peger ned for at være den nye NULL terminator. Udført. Temmelig nemt at indsætte 55 i en sorteret liste. Og hvordan kan det se ud? Lad mig gå videre og åbne op for noget kode eksempel her. Jeg vil åbne op gedit, og lad mig åbne to filer først. Den ene er list1.h, og lad mig blot minde om, at dette var bid af koden som vi brugte til at repræsentere en knude. En node har både en int kaldet n og en pointer kaldet næste, der bare peger på den næste ting på listen. Det er nu i en. H. fil. Hvorfor? Der er denne konvention, og vi har ikke draget fordel af dette en enorm mængde selv, men den person, der skrev printf og andre funktioner gav som en gave til verden alle disse funktioner ved at skrive en fil kaldet stdio.h. Og så er der string.h, og så er der map.h, og der er alle disse h-filer som du måske har set eller brugt i løbetiden er skrevet af andre mennesker. Typisk i dem. H-filer er kun ting som typedefs eller erklæringer om brugerdefinerede typer eller erklæringer af konstanter. Du behøver ikke sætte funktioner 'implementeringer i header-filer. Du sætter i stedet blot deres prototyper. Du sætter ting, du ønsker at dele med verden, hvad de har brug for med henblik på at udarbejde deres kode. Så bare for at komme ind i denne vane, besluttede vi at gøre det samme. Der er ikke meget i list1.h, men vi har lagt noget, der kunne være af interesse for folk i verden der ønsker at bruge vores linkede liste gennemførelse. Nu, i list1.c, vil jeg ikke gå igennem det hele fordi det er en smule lang, dette program, men lad os køre den reelle hurtigt ved prompten. Lad mig samle list1, lad mig derefter køre list1, og hvad du vil se er vi har simuleret en simpel lille program her der kommer til at tillade mig at tilføje og fjerne numre til en liste. Så lad mig gå videre og skrive 3 for menupunktet 3. Jeg ønsker at indsætte nummeret - lad os gøre det første nummer, der var 9, og nu er jeg fortalt listen er nu 9. Lad mig gå videre og gøre en anden indsættelse, så jeg ramte menufunktion 3. Hvilket nummer skal jeg ønsker at indsætte? 17. Enter. Og jeg vil gøre bare én mere. Lad mig indsætte nummer 22. Så vi har begyndelsen på den linkede liste, vi havde i slide formular for et øjeblik siden. Hvordan er denne indsættelse faktisk sker? Faktisk 22 er nu ved afslutningen af ​​listen. Så den historie vi fortalte på scenen på mandag og regummieres lige nu faktisk skal ske i kode. Lad os tage et kig. Lad mig rulle ned i denne fil. Vi glans over nogle af de funktioner, men vi vil gå ned til, siger, indsatsen funktionen. Lad os se, hvordan vi går om at indsætte en ny node i denne linkede liste. Hvor er listen angivne? Nå, lad os rulle hele vejen op i toppen, og bemærke, at min linkede liste væsentlige er erklæret som en enkelt pointer, der er oprindeligt NULL. Så jeg bruger en global variabel her, som vi generelt har prædiket imod fordi det gør din kode lidt rodet at vedligeholde, Det er slags doven, som regel, men det er ikke doven, og det er ikke forkert, og det er ikke dårligt hvis dit program eneste formål i livet er at simulere en sammenkædet liste. Hvilket er præcis, hvad vi laver. Så i stedet erklære dette i main og derefter nødt til at videregive det til hver eneste funktion vi har skrevet i dette program, vi i stedet indse oh, lad os bare gøre det globale fordi hele formålet med dette program er at demonstrere én og kun én linkede liste. Så det føles okay. Her er mine prototyper, og vi vil ikke gå igennem alle disse, men jeg skrev en slette-funktion, en finde funktionen, et indstik funktion, og en travers funktion. Men lad os nu gå tilbage til indsatsen funktionen og se, hvordan det man arbejder her. Insert er på linje - here we go. Indsæt. Så det tager ikke noget argument, fordi vi vil bede brugeren indersiden af ​​denne funktion for det antal, de skal indsættes. Men først vi klar til at give dem noget plads. Dette er slags kopiere og indsætte fra den anden eksempel. I dette tilfælde blev vi tildele en int; denne gang vi afsætte en node. Jeg kan ikke rigtig huske hvor mange bytes en node er, men det er fint. Sizeof kan regne det ud for mig. Og hvorfor jeg tjekker for NULL på linje 120? Hvad kunne gå galt på linje 119? Ja? [Student svar, uforståelig] Godt. Bare kunne være tilfældet, at jeg har bedt om for meget hukommelse eller der er noget galt, og operativsystemet har ikke nok bytes til at give mig, så det signalerer lige så meget ved at returnere NULL, og hvis jeg ikke tjekke for det og jeg bare blindt fortsætte med at bruge den adresse, der returneres, kan det være NULL. Det kunne være en ukendt værdi, ikke en god ting, hvis I - rent faktisk vil ikke være en ukendt værdi. Det kunne være NULL, så jeg ønsker ikke at misbruge det og risikerer dereferere det. Hvis det sker, jeg bare vende tilbage, og vi vil lade som om jeg ikke fik tilbage nogen hukommelse overhovedet. Ellers jeg fortælle brugeren give mig et nummer for at indsætte, jeg kalder vores gamle ven GetInt, og derefter dette var den nye syntaks vi introducerede i mandags. »Newptr-> n 'betyder tage den adresse, som du blev givet ved malloc som udgør den første byte af et nyt knudepunkt objekt, og derefter gå til feltet kaldet n. Lidt trivia spørgsmål: Dette svarer til, hvad mere kryptiske linje kode? Hvor ellers kunne jeg have skrevet det? Ønsker du at tage et stik? [Student svar, uforståelig] Godt. Ved hjælp af. N, men det er ikke helt så simpelt som dette. Hvad skal jeg først nødt til at gøre? [Student svar, uforståelig] Godt. Jeg er nødt til at gøre * newptr.n. Så dette siger ny pointer er naturligvis en adresse. Hvorfor? Fordi det blev returneret af malloc. Den * newptr sige "go there" og derefter når du er der, så du kan bruge den mere velkendte. n, men dette bare ser lidt grimt, især hvis vi mennesker kommer til at tegne pointers med pile hele tiden, verden har standardiseret på denne pil notation, som gør præcis det samme. Så du kun bruge -> notation, når ting til venstre er en pegepind. Ellers, hvis det er et virkeligt struct, skal du bruge. N.. Og så dette: Hvorfor skal jeg initialisere newptr-> ved siden af ​​NULL? Vi ønsker ikke en dinglende venstre hånd væk fra slutningen af ​​scenen. Vi vil have det peger lige ned, hvilket betyder afslutningen på denne liste potentielt kunne være ved dette knudepunkt, så vi bedre sørg for at det er NULL. Og generelt initialisering dine variabler eller dine data medlemmer og structs til noget er bare god praksis. Bare lade skrald eksistere og fortsætte med at eksistere generelt får dig i problemer hvis du glemmer at gøre noget senere. Her er nogle få tilfælde. Dette fører igen til, er indsatsen funktion, og den første ting jeg tjekke for, er, hvis variabel kaldet først, at den globale variabel er NULL, der betyder, at der ikke er nogen linkede liste. Vi har ikke sat nogen numre, så det er trivielt at indsætte denne nuværende antal til listen, fordi bare hører i starten af ​​listen. Så det var da Anita stod bare op her alene, foregiver ingen andre var heroppe på scenen indtil vi tildelt en node, så hun kunne hæve hendes hånd for første gang, hvis alle andre var kommet op på scenen efter hende på mandag. Nu her, dette er en lille kontrol, hvor jeg er nødt til at sige, om den nye node værdi af n er næste, der betyder gå til struct , der bliver peget på af newptr, så her er vi, derned. Så pilen siger få det næste felt, og derefter = siger sætte hvilken værdi der? Den værdi, der var i først, hvilken værdi var i først? Først pegede på dette knudepunkt, så det betyder dette bør nu pege på dette knudepunkt. Med andre ord, ser hvad omend en latterlig rod med min håndskrift, hvad er en simpel idé for bare at flytte disse pile rundt oversætter til kode med bare denne ene liner. Opbevar hvad der er i først i næste felt, og derefter opdatere hvad første rent faktisk er. Lad os gå videre og spole frem gennem nogle af dette, og ser kun på denne hale indsættelse for nu. Antag jeg kommer til det punkt, hvor jeg synes, at det næste felt af nogle node er NULL. Og på dette tidspunkt i historien, en detalje som jeg tilsløre er, at jeg har introduceret en anden pointer op her på linje 142, forgænger pointer. Væsentlige, på dette tidspunkt i historien, når listen bliver lang, Jeg slags nødt til at gå det med to fingre, fordi hvis jeg går for langt, Husk i en enkelt-længde liste, kan du ikke gå baglæns. Så denne idé predptr er min venstre finger, og newptr - ikke newptr. En anden pointer, der er her er min anden finger, og jeg er bare lidt at gå på listen. Det er derfor, der findes. Men lad os kun overveje en af ​​de mere simple sager her. Hvis denne pegepind næste felt er NULL, hvad er den logiske konsekvenser? Hvis du tilbagelæggelse denne liste og du rammer en NULL pointer? Du er i slutningen af ​​listen, og så koden til derefter tilføje dette ekstra element er slags den intuitive vil tage at node, hvis næste pointer er NULL, så dette er i øjeblikket NULL, og ændre det, selv om, for at være adressen på den nye node. Så vi er bare at trække i kode den pil, vi trak på scenen ved at øge en persons venstre hånd. Og sådan, at jeg vil vinke mine hænder på for nu, bare fordi jeg synes det er nemt at fare vild, når vi gør det i denne form for miljø, tjekker til indføring i listens midten. Men lige intuitivt, hvad der skal ske, hvis du ønsker at finde ud af hvor nogle tal hører til i midten er, at du er nødt til at gå det med mere end én finger,, mere end en pointer finde ud af, hvor den hører hjemme ved kontrol er elementet Den nuværende, og når du finder det sted, så er du nødt til at gøre denne form for shell spil, hvor du flytter markørerne rundt meget nøje. Og det svar, hvis du gerne vil følge gennem dette derhjemme på egen hånd, koges ned bare for at disse to linjer kode, men rækkefølgen af ​​disse linjer er super vigtigt. Fordi hvis du taber en hånd og hæve en andens i den forkerte rækkefølge, igen, kan du ende op forældreløst listen. For at opsummere mere begrebsmæssigt, indsættelse på halen er forholdsvis ligetil. Indsættelsen i spidsen er også relativt ligetil, men du skal opdatere en ekstra pointer denne gang at presse nummer 5 til listen her, og derefter indsættelse i midten involverer endnu større indsats, til meget omhyggeligt indsætte tallet 20 i sin korrekte position, som er mellem 17 og 22. Så du er nødt til at gøre noget lignende har det nye knudepunkt 20 point til 22, og derefter, som node pointer skal opdateres sidst? Det er 17, til rent faktisk at indsætte det. Så igen, vil jeg udskyde den faktiske kode for den pågældende gennemførelse. Ved første øjekast er det lidt overvældende, men det er egentlig bare en uendelig løkke der er looping, looping, looping, looping, og for at bryde, så snart du rammer NULL pointer, på hvilket tidspunkt du kan gøre den nødvendige indføring. Det er altså repræsentativ linkede liste indsættelse kode. Det var lidt af et parti, og det føles som om vi har løst et problem, men vi har introduceret en hel anden. Helt ærligt, har vi brugt al denne tid på store O og Ω og kører tid, forsøger at løse problemer hurtigere, og her tager vi et stort skridt tilbage, det føles. Og dog, hvis målet er at lagre data, det føles som den hellige gral, som vi sagde i mandags, ville virkelig være til at gemme ting med det samme. Faktisk formoder, at vi gjorde lægge linkede liste for et øjeblik og vi i stedet indført begrebet en tabel. Og lad os bare tænke på en tabel for et øjeblik som en matrix. Dette array og denne sag her har omkring 26 elementer, 0 til 25, og formoder, at du har brug for nogle luns af storage til navne: Alice og Bob og Charlie og lignende. Og du har brug for nogle datastruktur til at gemme disse navne. Nå, kan du bruge noget i retning af en sammenkædet liste og du kunne gå listen indsætte Alice før Bob og Charlie efter Bob og så videre. Og i virkeligheden, hvis du ønsker at se kode som det som en sidebemærkning vide, at i list2.h, vi gøre netop dette. Vi vil ikke gå gennem denne kode, men dette er en variant af det første eksempel der introducerer en anden struct vi har set før kaldte studerende, og så hvad det egentlig gemmer på den linkede liste er en pointer til en studerende struktur snarere end en simpel lille heltal, n. Så indser at der er kode der, der involverer faktiske strygere, men hvis målet ved hånden virkelig nu er at tage fat effektiviteten problem, ville det ikke være rart, hvis vi er givet et objekt kaldet Alice, vi ønsker at sætte hende ind i det rigtige sted i en datastruktur, det føles som om det ville være virkelig rart at bare sætte Alice, hvis navn begynder med A, i den første placering. Og Bob, hvis navn begynder med B, i den anden placering. Med et array, så lad eller s begynde at kalde det et bord, en hash tabel på det, vi kan gøre netop det. Hvis vi får et navn som Alice, en streng som Alice, hvor vil du sætte A-l-i-c-e? Vi har brug for en hueristic. Vi har brug for en funktion til at tage nogle input som Alice og returnere et svar, "Put Alice på denne placering." Og denne funktion, denne sorte boks, vil blive kaldt en hash-funktionen. En hash-funktion er noget, der kræver et input, som "Alice", og vender tilbage til dig, typisk den numeriske placering i nogle datastruktur hvor Alice hører hjemme. I dette tilfælde bør vores hash-funktionen være forholdsvis enkel. Vores hash-funktionen bør sige, hvis du får "Alice", hvilket tegn skulle jeg bekymre mig om? Den første. Så jeg ser på [0], og så siger jeg, hvis [0] karakter er A, returnere tallet 0. Hvis det er B, returnere 1. Hvis det er C, returnerer 2, og så videre. Alle 0-indekset, og det ville tillade mig at indsætte Alice og derefter Bob og derefter Charlie og så videre i denne datastruktur. Men der er et problem. Hvad hvis Anita kommer sammen igen? Hvor skal vi sætte Anita? Hendes navn er også starter med bogstavet A, og det føles som om vi har lavet en endnu større rod af dette problem. Vi har nu øjeblikkelig indsættelse, konstant tid indsættelse, ind i en datastruktur snarere end worst-case lineær, men hvad kan vi gøre med Anita i dette tilfælde? Hvad er de to muligheder, virkelig? Ja? [Student svar, uforståelig] Okay, så vi kunne have en anden dimension. Det er godt. Så vi kan bygge ting ud i 3D ligesom vi talte om verbalt på mandag. Vi kunne tilføje endnu adgangen her, men formoder, at nej, jeg prøver at holde det simpelt. Hele mål her er at få øjeblikkelig konstant-time adgang, så det er at tilføje for meget kompleksitet. Hvad er andre muligheder, når de forsøger at indsætte Anita i denne datastruktur? Ja? [Student svar, uforståelig] Godt. Så vi kunne flytte alle andre ned, ligesom Charlie nudges ned Bob og Alice, og så sætter vi Anita hvor hun virkelig ønsker at være. Selvfølgelig, nu er der en bivirkning af denne. Denne datastruktur er sandsynligvis nyttigt, ikke fordi vi ønsker at indsætte folk, når men fordi vi ønsker at se, om de er der senere hvis vi ønsker at udskrive alle navnene i datastrukturen. Vi vil gøre noget med disse data i sidste ende. Så nu har vi slags skruet over Alice, der er ikke længere hvor hun skulle være. Det er heller ikke Bob, heller ikke er Charlie. Så måske er det ikke sådan en god idé. Men ja, det er en mulighed. Vi kunne flytte alle ned, eller dælen, Anita kom sent til spillet, hvorfor vi ikke bare sætte Anita ikke her, ikke her, ikke her, lad os bare sætte hende lidt lavere på listen. Men så dette problem begynder at uddelegere igen. Du kan være i stand til at finde Alice straks, baseret på hendes fornavn. Og Bob straks, og Charlie. Men så skal du kigge efter Anita, og du kan se, hmm, Alice er i vejen. Nå, lad mig kontrollere under Alice. Bob er ikke Anita. Charlie er ikke Anita. Åh, der er Anita. Og hvis du fortsætter toget af logik hele vejen, hvad er det værst tænkelige køretid for at finde eller indsætte Anita ind i denne nye datastruktur? Det er O (n), right? Fordi der i værste fald er der Alice, Bob, Charlie. . . hele vejen ned til en person ved navn "Y", så der er kun én plads tilbage. Heldigvis har vi ingen kaldte "Z", så vi sætte Anita allernederst. Vi har ikke rigtig løst dette problem. Så måske vi nødt til at indføre denne tredje dimension. Og det viser sig, hvis vi indfører denne tredje dimension, vi kan ikke gøre det perfekt, men den hellige gral vil være at få konstant tid indføring og dynamiske insertioner således at vi ikke til hårdt kode et array af størrelse 26. Vi kan indsætte så mange navne, som vi vil, men lad os tage vores 5-minutters pause her og derefter gøre det ordentligt. Ok. Jeg satte historien op temmelig kunstigt der ved at vælge Alice og Bob og derefter Charlie og derefter Anita, hvis navn blev naturligvis går til at kollidere med Alice. Men det spørgsmål, vi sluttede mandag med er bare, hvor sandsynligt er det at du ville få den slags sammenstød? Med andre ord, hvis vi begynder at bruge denne tabelstruktur, der er virkelig bare et array, i dette tilfælde af 26 steder, hvad nu hvis vores input i stedet er ensartet fordelt? Det er ikke kunstigt Alice og Bob og Charlie og David og så videre alfabetisk, det er jævnt fordelt over A til Z. Måske vil vi bare heldige, og vi vil ikke have to A'er eller to Bs med meget stor sandsynlighed, men som nogen påpegede, hvis vi generaliseret dette problem og ikke gøre fra 0 til 25 men fx 0 til og med 364 eller 65, ofte antallet af dage i et typisk år og stillet spørgsmålet: "Hvad er sandsynligheden for, at to af os i dette rum har samme fødselsdag?" Sagt på en anden måde, hvad er sandsynligheden for, at to af os har et navn, der starter med A? Den slags spørgsmål er det samme, men denne adresse rum, denne søgning plads, er større i tilfælde af fødselsdage, fordi vi har så mange flere dage i året end bogstaver i alfabetet. Hvad er sandsynligheden for en kollision? Nå, kan vi tænke på dette ved at finde ud af matematik den modsatte vej. Hvad er sandsynligheden for ingen kollisioner? Nå, dette udtryk her siger, at hvad er sandsynligheden hvis der er bare én person i dette rum, at de har en unik fødselsdag? Det er 100%. For hvis der kun er én person i rummet, hans eller hendes fødselsdag kan være enhver af de 365 dage om året. Så 365/365 optioner giver mig en værdi på 1. Så sandsynligheden pågældende i øjeblikket er kun 1. Men hvis der er en anden person i rummet, hvad er sandsynligheden for, at deres fødselsdag er anderledes? Der er kun 364 mulige dage, ignorerer skudår, for deres fødselsdag ikke at kollidere med de andre personer. Så 364/365. Hvis en tredje person kommer ind, det er 363/365, og så videre. Så vi holder multiplicere sammen disse fraktioner, som bliver mindre og mindre, at regne ud, hvad er sandsynligheden for at vi alle har unikke fødselsdage? Men så kan vi jo tage bare svaret og vende det rundt og gøre 1 minus alt dette, et udtryk vi til sidst får hvis du husker på bagsiden af ​​dine matematiske bøger, det ser lidt noget som dette, som er meget lettere fortolket grafisk. Og denne grafik her har på x-aksen antallet af fødselsdage, eller antallet af personer med fødselsdage, og på y-aksen er sandsynligheden for et match. Og hvad dette siger er, at hvis du har, lad os sige, selv, lad os vælge noget lignende 22, 23. Hvis der er 22 eller 23 personer i rummet, sandsynligheden for, at to af de meget få mennesker kommer til at have samme fødselsdag er faktisk super høj, kombinatorisk. 50% odds der i en klasse for blot 22 mennesker, et seminar, stort set, 2 af disse mennesker vil have samme fødselsdag. Fordi der er så mange måder, hvorpå du kan få den samme fødselsdag. Endnu værre, hvis man ser på den højre side af diagrammet, af den tid, du har en klasse med 58 elever i det, sandsynligheden for 2 personer med en fødselsdag er super, super høj, næsten 100%. Nu, det er en slags sjov kendsgerning om det virkelige liv. Men konsekvenserne, nu, for datastrukturer og lagring af oplysninger betyder, at bare forudsat du har en pæn, ren, ensartet fordeling af data og du har en stor nok række til at passe en masse ting betyder ikke, du kommer til at få folk i unikke steder. Du kommer til at have kollisioner. Så denne forestilling om hashing, som det hedder, idet en indgang som "Alice" og masserer det på en eller anden måde og derefter komme tilbage et svar så som 0 eller 1 eller 2. Kom tilbage nogle output fra denne funktion er plaget af denne sandsynlighed for kollision. Så hvordan kan vi håndtere disse kollisioner? Tja, på den ene sag, kan vi tage den idé, der blev foreslået. Vi kan bare flytte alle ned, eller måske en lidt mere enkelt, snarere end flytte alle andre, lad os bare flytte Anita til bunden af ​​den tilgængelige plet. Så hvis Alice er i 0, Bob er i 1, Charlie er i 2, vi bare sætte Anita på location 3. Og det er en teknik i datastrukturer kaldes lineær probing. Lineær fordi du bare gå denne linje, og du er slags sondering for tilgængelige lokationer i datastrukturen. Selvfølgelig overdrages dette i O (n). Hvis datastrukturen er virkelig fuld, er der 25 personer i det allerede, og derefter Anita kommer sammen, at hun ender på hvad der ville være placering Z, og det er fint. Hun stadig passer, og vi kan finde hende senere. Men dette var i strid med målet om at fremskynde tingene op. Så hvad hvis vi i stedet indførte denne tredje dimension? Denne teknik kaldes generelt særskilt kæde eller har kæder. Og hvad en hash tabel er nu, denne tabelstruktur, Deres bord er blot en vifte af pegepinde. Men hvad disse henvisninger peger på, er gæt hvad? En sammenkædet liste. Så hvad hvis vi tager det bedste fra begge disse verdener? Vi bruger arrays til de oprindelige indekser ind i datastrukturen, så vi kan øjeblikkeligt gå til [0] [1], [30] eller så videre, men således at vi har en vis fleksibilitet, og vi kan passe Anita og Alice og Adam og enhver anden Et navn, vi i stedet lade den anden akse vokse vilkårligt. Og vi endelig, som mandag den have, at udtryksmulighed med linkede liste. Vi kan dyrke en datastruktur vilkårligt. Alternativt kunne vi bare gøre en enorm 2-dimensional array, men det vil være en forfærdelig situation, hvis en af ​​rækkerne i en 2-dimensionalt array er ikke store nok til yderligere person, hvis navn sker til at begynde med A. Gud forbyde vi er nødt til at omfordele en enorm 2-dimensional struktur bare fordi der er så mange mennesker ved navn A, især når der er så få mennesker ved navn Z noget. Det er bare at være en meget sparsom datastruktur. Så det er ikke perfekt på enhver måde, men nu har vi i det mindste har mulighed til straks at finde, hvor Alice eller Anita tilhører, i det mindste med hensyn til den lodrette akse, og så må vi bare nødt til at beslutte, hvor at sætte Anita eller Alice i denne linkede liste. Hvis vi er ligeglade med sortering ting, kunne hvor hurtigt vi indsætter Alice i en struktur som denne? Det er konstant tid. Vi indekset i [0], og hvis ingen er der, Alice går ved starten af ​​det linkede liste. Men det er ikke et enormt meget. For hvis Anita så kommer langs nogle række skridt senere, er hvor Anita tilhører? Nå, [0]. OOP. Alice er allerede på det linkede liste. Men hvis vi er ligeglade med sortering af disse navne, vi kan bare flytte Alice over, insert Anita, men selv det er konstant tid. Selv om der er Alice og Adam og alle disse andre A navne, det er egentlig ikke flytte dem fysisk. Hvorfor? Fordi vi bare gjorde her med linkede liste, der kender blev disse knudepunkter er alligevel? Alt du skal gøre er at flytte de brødkrummer. Flyt pilene rundt, og du behøver ikke fysisk at flytte data rundt. Så vi kan indsætte Anita, i dette tilfælde med det samme. Konstant tid. Så vi har konstant tid opslag, og konstant-time indsættelse af en person som Anita. Men sådan oversimplificerer verden. Hvad hvis vi senere ønsker at finde Alice? Hvad hvis vi senere ønsker at finde Alice? Hvor mange trin er, at kommer til at tage? [Student svar, uforståelig] Præcis. Antallet af mennesker, før Alice i den linkede liste. Så det er ikke helt perfekt, fordi vores data struktur, igen, har denne vertikale adgang og så har disse hægtede lister hængende - faktisk, lad os ikke trække det et et array. Det har disse hægtede lister hængende ud af det, der ser lidt noget som dette. Men problemet er, hvis Alice og Adam og alle disse andre A navne ender flere og flere derovre, finde nogen kunne ende med at tage en masse af trin, bcause du nødt til at krydse den linkede liste, som er en lineær funktion. Så meget, da indsættelsen tid sidste ende er O (n), hvor n er antallet af elementer på listen. Divideret med s vilkårligt kalde det m, hvor m er antallet af hægtede lister lade som vi har i denne lodrette akse. Med andre ord, hvis vi virkelig antager en ensartet fordeling af navne helt urealistisk. Der er tydeligvis mere af nogle breve end andre. Men hvis vi antager for øjeblikket en ensartet fordeling, og vi har N Total mennesker, og m total kæder til rådighed for os, så længden af ​​hver af disse kæder ret lette bliver den samlede, n divideret med antallet af kæder. Så n / m. Men her er, hvor vi kan være alle matematisk klog. m er en konstant, fordi der er et bestemt antal af disse. Du kommer til at erklære dit array i starten, og vi er ikke resizing den lodrette akse. Pr. definition forbliver det fast. Det er kun den horisontale akse, så at sige, der er under forandring. Så teknisk set er dette en konstant. Så nu, indsættelsen tid er temmelig meget O (n). Så det føles ikke så meget bedre. Men hvad er sandheden her? Nå, al den tid, i ugevis, vi har sagt O (n ²). O (n), 2 x n ², - n, divideret med to. . . ECH. Det er bare n ². Men nu, i denne del af semestret, vi kan begynde at tale om den virkelige verden igen. Og n / m er absolut hurtigere end bare n alene. Hvis du har tusind navne, og du bryder dem op i flere spande så du har kun ti navne i hver af disse kæder, absolut søge ti ting kommer til at være hurtigere end tusind ting. Og så en af ​​de kommende problem sæt kommer til at udfordre dig at tænke over, nøjagtigt at selv om, ja, asymptotisk og matematisk, det er stadig bare lineær, som suger generelt, når de forsøger at finde ting. I virkeligheden går det at være hurtigere end at på grund af denne divisor. Og så der er igen kommer til at være denne trade-off og denne konflikt mellem teori og virkelighed, og en af ​​knapperne, vil begynde at dreje på dette tidspunkt i semesteret er mere af den virkelighed en som vi slags forberede semster udgang, som vi introducerer en verden af ​​web programmering, hvor virkelig er ydeevnen færd med at tælle, fordi dine brugere vil begynder at føle og værdsætte dårlige designbeslutninger. Så hvordan kan du gå om at gennemføre en sammenkædet - en hash tabel med 31 elementer? Og det forrige eksempel var vilkårligt omkring fødselsdage. Hvis nogen har en fødselsdag 1. januar eller 1. februar vil vi sætte dem i denne spand. Hvis det er den 2. januar 2. februar, 2. marts, vil vi sætte dem i denne spand. Det er derfor, det var 31. Hvordan du erklærer en hash tabel? Det kan være temmelig enkel, node * bordet er mit vilkårligt navn for det, [31]. Dette giver mig 31 henvisninger til noder, og det giver mig mulighed for at have 31 henvisninger til hægtede lister selv om disse kæder er i første omgang NULL. Hvad ønsker jeg at sætte, hvis jeg vil gemme "Alice", "Bob", "Charlie"? Tja, vi er nødt til at pakke disse ting i en struktur fordi vi har brug for Alice at pege på Bob, at pege på Charlie, og så videre. Vi kan ikke bare have navnene alene, så jeg kunne skabe en ny struktur, der kaldes knude her. Hvad er en egentlig knude? Hvad er en node i denne nye linkede liste? Den første ting, der kaldes ord, er for personens navn. LÆNGDE formodentlig angår den maksimale længde af et menneske navn, uanset hvad det er, 20, 30, 40 tegn i skøre hjørne sager, og +1 er for hvad? Det er bare den ekstra NULL karakter, \ 0. Så denne node er indpakning "noget" inde i sig selv, men også erklærer en pointer kaldet næste så vi kan kæde Alice til Bob til Charlie og så videre. Kan være nul, men behøver ikke nødvendigvis at være. Eventuelle spørgsmål vedrørende disse hash tabeller? Ja? [Student spørger spørgsmål, uforståelig] Et array - godt spørgsmål. Hvorfor er dette char ord i et array snarere end blot char *? I dette noget vilkårlige eksempel vidste jeg ikke ønsker at skulle ty at allokere for hver af de oprindelige navne. Jeg ønskede at erklære en maksimal mængde hukommelse til strengen så jeg kunne kopiere ind i strukturen Alice \ 0 og ikke behøver at beskæftige sig med malloc og fri og lignende. Men jeg kunne gøre det, hvis jeg ønskede at være mere bevidst om rummet brug. Godt spørgsmål. Så lad os prøve at generalisere væk fra dette og fokusere resten af ​​i dag på datastrukturer mere generelt og andre problemer, som vi kan løse ved hjælp af de samme grundlæggende selvom datastrukturer selv kan være forskellige i deres oplysninger. Så det viser sig i datalogi, træer er meget almindelige. Og du kan tænke på et træ lidt ligesom et stamtræ, hvor der er nogle rødder, nogle matriark eller patriark, bedstemor eller bedstefar eller tidligere tilbage, hvorunder er mor og far eller forskellige søskende eller lignende. Så en træstruktur har knuder og det har børn, normalt 0 eller flere børn for hver node. Og nogle af de jargon, som du ser på dette billede her er en af ​​de små børn eller børnebørn på kanterne der har ingen pile, der stammer fra dem, det er de såkaldte blade, og alle på indersiden er en indre knude, man kan kalde det noget i den retning. Men denne struktur er temmelig almindelig. Denne ene er lidt vilkårligt. Vi har et barn på venstre, vi har tre børn på højre, to børn på nederst til venstre. Så vi kan have forskellig størrelse træer, men hvis vi begynder at standardisere tingene, og du kan huske det fra Patricks video på binær søgning fra en tidligere kort online, binær søgning ikke skal gennemføres med et array eller stykker papir på en tavle. Antag, at du ønskede at gemme dine numre i en mere sofistikeret datastruktur. Du kan oprette et træ som dette. Du kunne have en node erklæret i C, og at node kan have mindst to elementer inde i den. Den ene er det nummer, du vil gemme, og den anden er - ja, vi har brug for en mere. Den anden er dets børn. Så her er en anden datastruktur. Denne gang er et knudepunkt defineres som lagring af et antal n og derefter to pointere, venstre barn og højre barn. Og de er ikke vilkårlig. Hvad er interessant ved dette træ? Hvad er det mønster i, hvordan vi har lagt det ud eller hvordan Patrick lagde det i sin video? Det er slags indlysende, at der er nogle sortering foregår her, men hvad er den simple regel? Ja? [Student svar, uforståelig] Perfekt. Hvis du kaste et blik på dette, kan du se de små tal til venstre, store tal i venstre, men det er sandt for hver node. For hver knude. Sin venstre barn mindre end det, og dets ret barn større end det Hvad dette betyder nu, er, hvis jeg ønsker at søge denne datastruktur for, siger, at antallet 44, Jeg er nødt til at starte ved roden, fordi som med alle disse mere komplekse datastrukturer nu, vi kun har en pegepind til en ting, begyndelsen. Og i dette tilfælde er begyndelsen roden. Det er ikke den venstre ende, Det er roden til denne struktur. Så jeg ser her er 55, og jeg leder efter 44. Hvilken retning skal jeg hen? Tja, jeg ønsker at gå til venstre, fordi selvfølgelig er til højre vil være for stor. Så opdager her, er du slags konceptuelt hakke træet i halvdelen fordi du aldrig kommer ned til den højre side. Så nu går jeg fra 55 til 33. Det er for lille til et tal. Jeg leder efter 44, men nu ved jeg, om 44 er i dette træ, kan jeg gå selvfølgelig til højre. Så igen, jeg er beskæring træet i halve. Det er stort set identisk begrebsmæssigt til telefonbogen. Det er identisk med hvad vi gjorde med papirerne på tavlen, men det er en mere sofistikeret struktur, der giver os mulighed for rent faktisk at gøre Dette del og hersk by design af algoritmen, og i virkeligheden, gennemkører en struktur som denne - Ups. Gennemkører en struktur som denne, hvor det er kun "gå denne vej, eller gå den vej," betyder alt det kode, der bøjede dit sind først når gennemføre det i afsnit eller gå gennem det derhjemme, for binær søgning, ved hjælp af rekursion eller iteration, det er en smerte i nakken. Find den midterste element, så gør din afrunding op eller ned. Der er en skønhed til dette, fordi vi nu kan bruge rekursion igen, men meget mere rent. Ja, hvis du er på nummer 55, og du vil finde 44, du gå tilbage i dette tilfælde, så hvad gør du så? Du kører præcis samme algoritme. Du kontrollere værdien af ​​den knude, så skal du gå til venstre eller højre. Så kan du kontrollere værdien af ​​den knude, gå til venstre eller højre. Dette er perfekt egnet til rekursion. Så selvom vi tidligere har gjort nogle temmelig vilkårlige eksempler involverer rekursion der ikke behøver at være rekursiv med data Stuctures, især træer, er det en perfekt anvendelse af denne tanken om at tage et problem, krympning det og derefter at løse den samme type, men mindre, program. Så der er en anden datastruktur, at vi kan præsentere. Denne ene er designet ved første øjekast at se kryptisk, men denne her er fantastisk. Så dette er en datastruktur kaldet en Trie, Trie, som er nedarvet fra ordet selektion, som ikke udtales re-try-val, men det er, hvad verden kalder disse ting. Forsøger. T-r-i-e. Det er en træstruktur af en slags, men hver af knudepunkter i et Trie synes at være hvad? Og dette er en smule misvisende, fordi det er lidt forkortet. Men det ligner hvert knudepunkt i denne Trie er faktisk et array. Og selvom forfatteren af ​​dette diagram har ikke vist det, i dette tilfælde, er dette Trie en datastruktur, hvis formål i livet er at gemme ord som A-l-i-c-e eller B-o-b. Og den måde, hvorpå disse data stores Alice og Bob og Charlie og Anita osv. Det anvender en matrix, hvorved at lagre Alice i en trie, vi starter ved roden node, der ligner et array, og det er blevet skrevet i stenografi notation. Forfatteren udeladt abcdefg fordi der var ingen navne med det. De viste kun M og P og T, men i dette tilfælde, lad os gå væk fra Alice og Bob og Charlie til nogle navne, der er her. Maxwell er faktisk i dette diagram. Så hvordan gjorde forfatteren butik M-a-x-w-e-l-l? Han eller hun startede ved roden node, og gik til [M], så groft 13, den 13. placering i arrayet. Så derfra, er der en pointer. En markør, der fører til et andet array. Derfra forfatteren indekseret i den pågældende matrix på placering A, som det er vist der øverst til venstre, og så han eller hun fulgte markøren til en anden array, og gik til markøren på stedet X. I næste array-placering W, E, L, L, og så videre, og endelig, lad os faktisk forsøge at sætte et billede på dette. Hvordan ser en knude se ud i koden? En knude i en Trie indeholder en række henvisninger til flere noder. Men der er også nødt til at være en slags boolean værdi, i det mindste i denne implementering. Jeg tilfældigvis at kalde det is_word. Hvorfor? Fordi når du indsætter Maxwell, du er ikke indsætte noget i denne datastruktur. Du skriver ikke M. Du skriver ikke X. Alt du laver er følgende pejlemærker. Markøren, der repræsenterer M, hvorefter markøren, der repræsenterer A, hvorefter markøren, der repræsenterer X, da W, E, L, L, men hvad du skal gøre i slutningen er slags gå, check, jeg nåede denne placering. Der var et ord, der ender her i datastrukturen. Så hvad en Trie er virkelig fyldt med og forfatteren valgte at repræsentere Disse terminuses med små trekanter. Det betyder blot, at den omstændighed, denne trekant er her, denne boolean værdi af sand betyder, at hvis du går baglæns i træet, det betyder et ord hedder Maxwell er i dette. Men ordet foo, for eksempel er ikke i træet, fordi hvis jeg starter på roden node op her på toppen, Der er ingen f pointer, ingen o pointer, ingen o pointer. Foo er ikke et navn i denne ordbog. Men derimod ringer, t-u-r-i-n-g. Igen, jeg har ikke opbevare t eller u eller r eller jeg eller n eller g. Men jeg gjorde butik i denne datastruktur en værdi af ægte vejen ned her i dette knudepunkt - i træet ved at sætte denne boolean værdi af is_word til sand. Så en trie er en slags denne meget interessante meta struktur, hvor du ikke rigtig gemme de ord, selv for denne form for ordbog. For at være klar, du bare gemme ja eller nej, der er et ord, der ender her. Nu hvad er konsekvenserne? Hvis du har 150.000 ord i en ordbog, som du forsøger at gemme i hukommelsen bruger noget som en linket liste, du kommer til at have 150.000 knudepunkter i din linkede liste. Og at finde et af disse ord alfabetisk kunne tage O (n) tid. Lineær tid. Men i tilfældet her med en Trie, hvad er køretiden for at finde et ord? Det viser sig den skønhed her er, at selvom du har 149.999 ord allerede i denne ordbog, som gennemført med denne datastruktur, hvor meget tid tager det at finde eller indsætte en person mere ind i det, som Alice, Alice? Tja, det er kun 5, måske 6 trin til den bageste karakter. Fordi presense af andre navne i strukturen ikke kommer i vejen for indsættelse af Alice. Desuden finde Alice når der er 150.000 ord i denne ordbog ikke komme i din måde at finde Alice på alle, fordi Alice er. . . . . her, fordi jeg fandt en boolesk værdi. Og hvis der ikke er boolean sandt, så Alice ikke i denne datastruktur af ord. Med andre ord køretiden for at finde ting og indsætte ting i denne nye datastruktur af Trie er O - det er ikke n. Fordi presense af 150.000 mennesker har ingen virkning på Alice, forekommer. Så lad os kalde det k, hvor k er den maksimale længde af et ord på engelsk som typisk ikke mere end 20-noget tegn. Så k er en konstant. Så den hellige gral, vi synes at have fundet nu er, at en Trie, konstant tid for skær, for opslag, for sletninger. Fordi antallet af ting, der allerede i strukturen, der er ikke engang fysisk der. Igen, er de bare slags markeret, ja eller nej, har ingen indflydelse på den fremtidige drift tid. Men der er nødt til at være en fangst, ellers ville vi ikke have spildt så meget tid på alle disse andre datastrukturer bare for endelig at komme til den hemmelige en, der er forbløffende. Så hvilken pris betaler vi for at nå dette storhed her? Space. Denne ting er massiv. Og grunden til, at forfatteren ikke fremlægge det her mærke til, at alle disse ting, der ligner arrays, han ikke trække resten af ​​træet, resten af ​​trie, fordi de er bare ikke relevant for historien. Men alle disse knudepunkter er super bred, og hver node i træet optager 26 eller faktisk, kunne være 27 tegn, fordi der i dette tilfælde var jeg også plads til apostrof så vi kunne have apostrophized ord. I dette tilfælde er disse store arrays. Så selv om de ikke er picutured, det tager op en massiv mængde af RAM. Som kunne være fint, especilly i moderne hardware, men det er afvejning. Vi får mindre tid ved at bruge mere plads. Så hvor er det hele hen? Nå, lad os gøre - lad os se her. Lad os gøre et spring til denne fyr her. Tro det eller ej, så meget sjov som C har været i nogen tid nu, vi nået til et punkt i det semester, hvor det er tid til overgang til tingene mere moderne. Ting på et højere niveau. Og selvom de næste par uger vi vil stadig fortsætte med at fordybe os i en verden af ​​pointers og memory management at få den trøst, som vi derefter kan bygge videre på, slutspillet er i sidste ende at indføre, ironisk nok, ikke dette sprog. Vi vil bruge, ligesom 10 minutter taler om HTML. Alle HTML er et markup sprog, og hvad et kodesprog er er disse serier af åbne bøjler og lukkede parenteser, der siger 'make denne dristige' "Gør dette kursiv '' gøre denne centrerede. Det er ikke alt, intellektuelt interessant, men det er super nyttigt. Og det er helt sikkert allestedsnærværende i disse dage. Men hvad er kraftfuld om verden af ​​HTML, og webprogrammering mere generelt, er ved at opbygge dynamiske ting, at skrive kode i sprog som PHP eller Python eller Ruby eller Java eller C #. Virkelig, uanset dit sprog valg er, og generere HTML dynamisk. Generering noget, der hedder CSS dynamisk. Cascading style sheets, som også er om æstetik. Og så selvom, i dag, hvis jeg gå til nogle hjemmeside som den velkendte Google.com, og jeg går for at se, udvikler, view kilde, som måske du har gjort før, men kommer til at se kilden, det her sandsynligvis ser temmelig kryptisk. Men dette er den underliggende kode, der implementerer Google.com. På den forreste ende. Og faktisk alt dette er fluffy æstetik ting. Det er CSS op her. Hvis jeg holder rulle ned vi vil få nogle farvekodede ting. Det er HTML. Googles kode ligner en rod, men hvis jeg faktisk åbner et andet vindue, vi kan se en vis struktur til dette. Hvis jeg åbner dette op, så læg mærke her, det er en lidt mere læsevenlig. Vi kommer til at se inden længe dette mærke, [word] er et tag, HTML, hoved, krop, div, script, tekstområde, span, centreret, div. Og det er også sortere af kryptisk udseende ved første øjekast, men alt dette rod følger visse mønstre, og gentagelige mønstre, så når vi får det grundlæggende ned, vil du være i stand til at skrive kode som denne og derefter manipulere kode som denne bruger endnu et andet sprog, kaldet JavaScript. Og JavaScript er et sprog, der kører inde i en browser i dag, at vi bruger på Harvard kurser, for kurset shopping værktøj, Google maps bruger at give dig en hel bunke af dynamik, Facebook giver dig mulighed for at vise øjeblikkelige statusopdateringer, Twitter bruger det til at vise dig tweets samme. Alt dette vil vi begynde at fordybe os i. Men for at komme dertil, er vi nødt til at forstå lidt om internettet. Denne klippet her er blot et minut lang, og lad os antage for nu er det i virkeligheden, hvordan internettet fungerer som en teaser for hvad der er ved at komme. Jeg giver dig "Warriors of the Net". [♫ Langsom kor musik ♫] [Mand fortælleren] Han kom med et budskab. Med en protokol al hans egen. [♫ Hurtigere elektronisk musik ♫] Han kom til en verden af ​​cool firewalls, ufølsom routere, og farer langt værre end døden. Han er hurtig. Han er stærk. Han er TCP / IP, og han har din adresse. Krigere af nettet. [Malan] Næste uge, da. Internettet. Web programmering. Det er CS50. [CS50.TV]