JASON HIRSCHHORN: Velkommen alle til § Seven. Vi er i uge syv af kurset. Og denne kommende torsdag er Halloween, så jeg klædt ud som et græskar. Jeg kunne ikke bøje og sættes på mine sko, så det er derfor jeg er blot iført sokker. Jeg er også ikke at bære noget under dette, så kan jeg ikke tage det fra, hvis det er distraherende for dig. Jeg undskylder på forhånd for det. Du behøver ikke at forestille hvad der foregår. Jeg bærer boksere. Så det er alle gode. Jeg har en længere historie om, hvorfor jeg er klædt som et græskar, men jeg har tænkt mig at gemme det til senere i dette afsnit fordi jeg ønsker at komme i gang. Vi har en masse spændende ting at gå over denne uge. De fleste af dem relaterer sig direkte til dette uges problem sæt, stavefejl. Vi kommer til at være at gå over forbundet lister og hash-tabeller for hele afsnittet. Jeg sætter denne liste op hver uge en liste over ressourcer for dig at hjælpe dig med materialet på dette kursus. Hvis der på et tab, eller hvis udkig efter nogle mere information, så tjek en af disse ressourcer. Igen, pset6 er stavefejl, denne uges PSET. Og det også opfordrer dig, og jeg opmuntre dig, at bruge nogle andre ressourcer specifikt til denne PSET. Især de tre jeg har noteret op på skærmen - gdb, som vi har været bekendt med og er blevet brugt et stykke tid nu, er kommer til at være meget nyttige i denne uge. Så jeg sætte det op her. Men når du arbejder med C, bør du altid bruge gdb til debug dine programmer. I denne uge også Valgrind. Er der nogen vide, hvad valgrind gør? PUBLIKUM: Den kontrollerer for memory leaks? JASON HIRSCHHORN: Valgrind checks for memory leaks. Så hvis du allokere noget i dit program, du beder for hukommelse. Ved slutningen af ​​dit program, du har at skrive frit om alt, hvad du har malloced at give hukommelsen tilbage. Hvis du ikke skriver fri ved slutningen og dit program kommer til en konklusion, Alt vil automatisk blive befriet. Og for små programmer, er det ikke så stor en aftale. Men hvis du skriver en længere indkøringsfase program, der ikke holde op, nødvendigvis, i et par minutter eller et par sekunder, så memory leaks kan blive en stor aftale. Så for pset6 er det forventningen, at vil du have nul memory leaks med dit program. At kontrollere for memory leaks, køre valgrind og det vil give dig nogle gode output lade dig vide, om eller ikke alt var gratis. Vi vil øve med den senere i dag, forhåbentlig. Endelig kommandoen diff. Du brugte noget der ligner det i pset5 med peek værktøj. Tilladt dig at kigge indenfor. Du brugte også diff, også, per problemet indstillet spec. Men i givet mulighed for at sammenligne to filer. Du kan sammenligne bitmapfil og info-headers i en personale-løsning og din løsning i pset5 hvis du vælger at bruge det. Diff vil tillade dig at gøre det, så godt. Du kan sammenligne det rigtige svar for denne uges problem indstillet til dit svar og se om det linjer op, eller se hvor fejlene. Så det er tre gode værktøjer, som du skal bruge til denne uge, og helt sikkert tjekke dit program med disse tre værktøjer før du tænder det i. Igen, som jeg har nævnt hver uge, hvis du har feedback til mig - både positiv og konstruktiv - velkommen til at hovedet til hjemmesiden i bunden af ​​dette dias og input det der. Jeg virkelig sætter pris på enhver og alle tilbagemeldinger. Og hvis du giver mig specifikke ting, Jeg kan gøre for at forbedre eller at jeg er klarer sig godt, at du gerne vil have mig til fortsætter, tager jeg det til hjerte og virkelig forsøger hårdt at lytte til din feedback. Jeg kan ikke love jeg tænkt mig at gøre alting, selv om, som at bære en græskar kostume hver uge. Så vi kommer til at tilbringe størstedelen af sektion, som jeg nævnte, tale om hægtede lister og hash-tabeller, som vil være direkte anvendelig for problem indstille denne uge. Hægtede lister vi vil gå over relativt hurtigt, fordi vi har brugt en retfærdig bit af tid at gå over den i afsnit. Og så vi får lige ind i kodning problemer for hægtede lister. Og så i slutningen, vi vil tale om hash tabeller og hvordan de gælder for denne uges problem indstillet. Du har set denne kode før. Dette er en struct, og det definerer noget nyt kaldet en knude. Og inden for en node der er et helt tal lige her og der er en pointer til anden node. Vi har set det før. Dette har været kommer op til et par uger nu. Det kombinerer pegepinde, som vi har været arbejder med, og structs, som tillader os til at kombinere to forskellige ting i én datatype. Der er en masse i gang på skærmen. Men det hele bør være relativt fortrolig med dig. På den første linje, vi erklære en ny node. Og så inde i den nye node, sæt jeg heltallet i dette knudepunkt til én. Vi ser på den næste linje jeg gør en printf kommandoen, men jeg har nedtonet printf kommandoen, fordi de virkelig vigtig del er denne linje her - new_node.n. Hvad betyder prik betyder? PUBLIKUM: Gå til noden og vurdere værdien n for det. JASON HIRSCHHORN: Det er helt rigtigt. Dot betyder adgang n del af denne nye knudepunkt. Denne næste linie gør hvad? Michael. PUBLIKUM: Det skaber en anden node der vil pege på den nye knudepunkt. JASON HIRSCHHORN: så det ikke oprette en ny node. Det skaber en hvad? PUBLIKUM: En pointer. JASON HIRSCHHORN: En pointer til en knude, som angivet af denne node * her. Så det skaber en pointer til et knudepunkt. Og hvilken node er det peger til Michael? PUBLIKUM: Ny knude? JASON HIRSCHHORN: Ny knude. Og det peger der, fordi vi har givet den adressen på nye node. Og nu i denne linje, vi ser to forskellige måder udtrykker det samme. Og jeg ønskede at påpege, hvordan disse to ting er ens. I første linje, vi dereferering markøren. Så vi går til node. Det er, hvad denne stjerne betyder. Vi har set det før med pointere. Gå til dette knudepunkt. Det er i parentes. Og derefter få adgang via prik operatør n element i denne knude. Så det tager syntaksen så vi lige nu og her bruge den med en pegepind. Selvfølgelig, det får lidt travlt, hvis du skriver disse parenteser - at stjerne og prik. Det får lidt travlt. Så vi har nogle syntaktisk sukker. Og denne linje lige her - ptr_node-> n. Det gør nøjagtig de samme ting. Så disse to linjer kode er ækvivalent og vil gøre præcis de samme ting. Men jeg ønskede at påpege dem ud før vi går videre, så du forstår der virkelig denne ting lige her er bare syntaktisk sukker til dereferere markøren, og derefter gå til n del af denne struct. Eventuelle spørgsmål vedrørende denne slide? OK. Så vi kommer til at gå igennem et par af operationer, som du kan gøre på hægtede lister. En sammenkædet liste, husker, er en serie af knudepunkter, der peger på hinanden. Og vi generelt starter med en pegepind kaldes hoved generelt, der peger på den første ting på listen. Så på den første linje her, vi har vores oprindelige L først. Så ting du kan tænke på - det tekst lige her du kan tænke på som bare markøren vi har gemt et eller andet sted, der peger til det første element. Og i denne linkede liste vi har fire noder. Hver node er en stor kasse. Jo større kasse inde i store boks er heltalsdelen. Og så har vi en pegepind del. Disse bokse er ikke tegnet i skala, fordi hvor stort er et heltal i bytes? Hvor stor nu? Four. Og hvor stor er en pointer? Four. Så virkelig, hvis vi skulle tegne dette for at skalere begge bokse ville være den samme størrelse. I dette tilfælde, vi ønsker at indsætte noget i den linkede liste. Så du kan se hernede vi indsætter fem Vi krydse gennem linkede liste, finde hvor fem går, og derefter indsætte det. Lad os bryde det ned og gå en lille smule langsommere. Jeg har tænkt mig at pege på tavlen. Så vi har vores knude fem, vi har skabt i malloc'erers. Hvorfor er alle griner? Just kidding. OK. Så vi har malloced fem. Vi har oprettet denne node et andet sted. Vi har det klar til at gå. Vi starter på forsiden af vores liste med to. Og vi ønsker at indsætte i en sorteret måde. Så hvis vi ser to, og vi ønsker at sætte i fem, hvad gør vi, når vi ser noget mindre end os? Hvad? Vi ønsker at indsætte fem ind i denne linkede liste, holde det sorteret. Vi ser nummer to. Så hvad gør vi? Marcus? PUBLIKUM: Ring markøren til det næste knudepunkt. JASON HIRSCHHORN: Og hvorfor gør vi gå til den næste? PUBLIKUM: Fordi det er den næste node i listen. Og vi ved kun, at anden placering. JASON HIRSCHHORN Og fem er større end to, i særdeleshed. Fordi vi ønsker at holde det sorteres. Så fem er større end to. Så vi gå videre til den næste. Og nu kommer vi til fire. Og hvad sker der, når vi når fire? Fem er større end fire. Så vi holde ud. Og nu vi er ved seks. Og hvad ser vi på seks? Ja, Carlos? PUBLIKUM: Seks er større end fem. JASON HIRSCHHORN: Six er større end fem. Så det er, hvor vi ønsker at indsætte fem. Men husk på, at hvis vi kun har én pointer her - dette er vores ekstra pointer, der er gennemkører gennem listen. Og vi peger på seks. Vi har mistet overblikket over, hvad kommer før seks. Så hvis vi ønsker at indsætte noget i denne liste holde det sorteret, vi sikkert brug for, hvor mange pointers? PUBLIKUM: Two. JASON Hirschorn: Two. En til at holde styr på den aktuelle en og en til at holde styr på den foregående. Dette er kun en enkelt bundet listen. Det går kun én retning. Hvis vi havde en dobbelt linket liste, hvor alt var at pege på ting efter det, og ting, før det, så vi ikke behøver at gøre det. Men i dette tilfælde ønsker vi ikke at tabe styr på, hvad der kom før os i tilfælde vi nødt til at indsætte fem sted i midten. Sig vi indsætte ni. Hvad ville der ske, når vi kom til otte? PUBLIKUM: Du er nødt til at få at nulpunktet. I stedet for at have null punkt, du ville have at tilføje et element og derefter har det peger på ni. JASON Hirschorn: Præcis. Så vi får otte. Vi når til slutningen af ​​listen, fordi dette peger til null. Og nu, i stedet for at have det peger på null vi har det pege på vores nye node. Og vi sætter markøren i vores nye node til null. Er der nogen har nogen spørgsmål om indsættelse? Hvad hvis jeg er ligeglad at listen sorteres? PUBLIKUM: Stick det på starten eller slutningen. JASON Hirschorn: Hold det på begyndelsen eller slutningen. Hvilken en skal vi gøre? Bobby? Hvorfor ende? PUBLIKUM: Da starten er allerede fyldt. JASON Hirschorn: OK. Begyndelsen er allerede fyldt. Hvem ønsker at argumentere imod Bobby. Marcus. PUBLIKUM: Nå du sandsynligvis ønsker at holde det i starten, fordi ellers hvis du sætter det på enden du er nødt til krydse hele listen. JASON Hirschorn: Præcis. Så hvis vi tænker på runtime, den runtime indsætte slutningen ville være n, størrelsen af ​​dette. Hvad er big O runtime indsætte i starten? Konstant tid. Så hvis du er ligeglad om at holde noget ordnet, meget bedre til bare indsætte i begyndelsen af ​​denne liste. Og der kan gøres i konstant tid. OK. Næste operation er at finde, som andre - Vi har formuleret dette som søgning. Men vi kommer til at se gennem forbundet liste til en genstand. I gutter har set kode for søg før i foredraget. Men vi slags gjorde det bare med indsætte, eller i det mindste at indsætte noget sorteres. Du ser igennem, går node efter node, indtil du finder det nummer, du udkig efter. Hvad sker der, hvis du kommer slutningen af ​​listen? Sig Jeg leder efter ni, og jeg nå enden af ​​listen. Hvad gør vi? PUBLIKUM: Tilbage falsk? JASON Hirschorn: Tilbage falsk. Vi kunne ikke finde det. Hvis du når til slutningen af ​​listen og du kunne ikke finde det nummer, du er leder efter, det er der ikke. Eventuelle spørgsmål om at finde? Hvis dette var en sorteret liste, hvad ville være forskellige for vores søgning? Ja. PUBLIKUM: Det vil finde den første værdi der er større end den du leder efter, og derefter vende tilbage falsk. JASON Hirschorn: Præcis. Så hvis det er en sorteret liste, hvis vi kommer til noget, der er større end hvad vi leder efter, har vi ikke brug for holde ud til slutningen af ​​listen. Vi kan på det tidspunkt return false fordi vi ikke kommer til at finde den. Spørgsmålet er nu, har vi talt om holde hægtede lister sorteres, holde dem usorteret. Det kommer til at være noget, du er sandsynligvis nødt til at tænke over når kodning problem sæt fem, hvis du vælge en hash tabel med separat kæde tilgang, der vi vil tale om senere. Men er det værd at holde listen sorteret og derefter kunne måske have hurtigere søgninger? Eller er det bedre til hurtigt at indsætte noget i konstant runtime, men derefter har længere søger? Det er en afvejning, lige der, at du komme til at beslutte, hvad der er mere passende til dit specifikke problem. Og der er ikke nødvendigvis en helt rigtige svar. Men det er helt sikkert en beslutning, du får at gøre, og sandsynligvis god til at forsvare der i, siger, en kommentar eller to, hvorfor du vælger den ene frem for den anden. Endelig sletning. Vi har set at slette. Det svarer til søgningen. Vi ser for elementet. Sig vi forsøger at slette seks. Så finder vi seks lige her. De ting, vi er nødt til at sikre, at vi gøre, er at uanset hvad der peger på seks - som vi ser i trin to hernede - uanset peger til seks behov til spring seks nu og ændres til uanset seks peger på. Vi ønsker ikke at nogensinde forældreløs resten af vores liste ved at glemme at indstille det foregående pointer. Og så nogle gange, afhængigt på programmet, de vil bare slette denne node helt. Nogle gange vil du ønsker at vende tilbage den værdi, der er i denne knude. Så det er, hvordan du sletter værker. Eventuelle spørgsmål vedrørende slette? PUBLIKUM: Så hvis du kommer til at slette det, ville du bare bruge gratis, fordi formentlig blev malloced? JASON Hirschorn: Hvis du ønsker at frigøre noget, der er helt rigtigt, og du malloced det. Sig vi ønskede at vende tilbage denne værdi. Vi vender måske tilbage seks og derefter frit denne node og opkald gratis på den. Eller vi ville nok kalde fri først og derefter vende tilbage seks. OK. Så lad os gå videre til at øve kodning. Vi kommer til at kode tre funktioner. Den første hedder insert_node. Så du har kode, som jeg mailede dig, og hvis du ser dette senere du kan få adgang til koden i linked.c på CS50 hjemmeside. Men i linked.c, er der nogle skelet kode, der allerede er skrevet til dig. Og så er der et par funktioner du nødt til at skrive. Først vil vi skrive insert_node. Og hvad insert_node gør Er indsætter et heltal. Og du giver heltal i en sammenkædet liste. Og i særdeleshed, du har brug for at holde listen sorteres fra den mindste til den største. Også, behøver du ikke ønsker at indsætte dubletter. Endelig, som du kan se insert_node returnerer en bool. Så du er formodes for at lade brugeren vide om indsatsen var eller ikke succes ved at returnere sandt eller falsk. Ved afslutningen af ​​dette program - og til dette tidspunkt behøver du ikke at bekymre sig om at frigøre noget. Så alt du gør, er at tage et heltal og indsætte det i en liste. Det er, hvad jeg beder dig om at gøre nu. Igen i linked.c, som du alle er skelettet kode. Og du bør se mod bunden prøven funktionen erklæring. Men inden jeg går ind i kodning det i C, jeg stærkt opfordre dig til at gå gennem de trin, vi har været øve hver uge. Vi har allerede været igennem et billede af dette. Så du skal have en vis forståelse af hvordan det virker. Men jeg vil opfordre dig til at skrive nogle pseudokode før dykning i. Og vi kommer til at gå over pseudokode som en gruppe. Og så når du har skrevet din pseudokode, og når vi har skrevet vores pseudokode som en gruppe, kan du gå ind kodning det i C. Som en heads up, den insert_node funktion er nok den vanskeligste af de tre vi kommer til at skrive, fordi jeg tilføjet nogle yderligere begrænsninger for din programmering, navnlig du kommer ikke til at indsætte nogen dubletter og at listen bør forblive sorteres. Så dette er en ikke-triviel program at du skal til at kode. Og hvorfor tager du ikke 06:55 minutter bare at få arbejde på pseudokode og koden. Og så vil vi begynde går som en gruppe. Igen, hvis du har spørgsmål bare hæve din hånd, og jeg vil komme rundt. . Vi har også generelt gøre disse - eller jeg ikke udtrykkeligt sige, at du kan arbejde med mennesker. Men selvfølgelig, jeg stærkt opfordre dig til, hvis du har spørgsmål, at spørge nabo sidder ved siden af ​​dig eller endda arbejde med nogen andet, hvis du vil. Dette behøver ikke at være et individ tavse aktivitet. Lad os starte med at skrive nogle pseudokode på tavlen. Hvem kan give mig den første linje i pseudokode til dette program? Til denne funktion, snarere - insert_node. Alden? PUBLIKUM: Så det første jeg gjorde var oprette en ny pointer til knuden, og jeg initialiseret det fører til den samme ting at liste peger på. JASON Hirschorn: OK. Så du opretter en ny pointer til listen, ikke til noden. PUBLIKUM: Right. Ja. JASON Hirschorn: OK. Og hvad vil vi gøre? Hvad er efter det? Hvad node? Vi har ikke et knudepunkt. Vi skal bare have en værdi. Hvis vi ønsker at indsætte en node, hvad gør vi nødt til at gøre først, før vi kan endda tænke indsætter det? PUBLIKUM: Åh, undskyld. vi nødt til at allokere plads til en knude. JASON Hirschorn: Excellent. Lad os gøre - OK. Kan ikke nå så højt. OK. Vi kommer til at gå ned, og derefter vi bruger to kolonner. Jeg kan ikke gå så - OK. Opret en ny node. Du kan oprette en anden pointer til listen eller du kan bare bruge listen som den eksisterer. Du behøver ikke virkelig nødt til at gøre det. Så vi skaber en ny node. Store. Det er, hvad vi gør først. Hvad er det næste? PUBLIKUM: Vent. Skal vi lave en ny node nu eller skal vi vente med at sørge for, at der er ingen dubletter af node på listen, før vi skaber det? JASON Hirschorn: Godt spørgsmål. Lad os holde det til senere, fordi størstedelen af ​​den tid, vi vil skabe et nyt knudepunkt. Så vi vil holde det her. Men det er et godt spørgsmål. Hvis vi skaber det, og vi finder en kopi, hvad skal vi gør før han vendte tilbage? PUBLIKUM: Befri den. JASON Hirschorn: Ja. Sandsynligvis frigøre det. OK. Hvad gør vi, når vi oprette en ny knude? Annie? PUBLIKUM: Vi sætter nummer i knudepunktet? JASON Hirschorn: Præcis. Vi sætter antallet - vi allokere plads. Jeg har tænkt mig at forlade denne alle som én linje. Men du har ret. Vi allokere plads, og derefter vi sætter antallet i. Vi kan endda indstille markøren en del af den til null. Det er helt rigtigt. Og hvad så efter det? Vi tegnede dette billede på tavlen. Så hvad gør vi? PUBLIKUM: Vi går gennem listen. JASON Hirschorn: Gå gennem listen. OK. Og hvad gør vi tjekke for ved hvert knudepunkt. Kurt, hvad skal vi kontrollerer for ved hvert knudepunkt? PUBLIKUM: Se, om n-værdien af dette knudepunkt er større end værdien n vores knudepunkt. JASON Hirschorn: OK. Jeg har tænkt mig at gøre - yeah, OK. Så det er n - Jeg har tænkt mig at sige, hvis værdi er større end denne node, så hvad gør vi? PUBLIKUM: Nå, så vi indsætter den ting lige før det. JASON Hirschorn: OK. Så hvis det er større end denne, så vi ønsker at indsætte. Men vi ønsker at indsætte det lige før fordi vi også skulle være holde styr, så af, hvad der var før. Så indsætte før. Så vi sandsynligvis glip af noget tidligere. Vi sandsynligvis skal holde styr på, hvad der foregår. Men vi vil komme tilbage dertil. Så hvad værdi er mindre end? Kurt, hvad gør vi, hvis værdi er mindre end? PUBLIKUM: Så du bare holde i gang medmindre det er den sidste. JASON Hirschorn: Jeg kan lide det. Så gå til næste node. Medmindre det er den sidste - vi sandsynligvis kontrollere for at i form af en betingelse. Men ja, næste node. Og det er ved at blive for lav, så vi vil flytte over her. Men hvis - kan alle se det? Hvis vi er lige, hvad gør vi? Hvis værdien vi forsøger at indsætte er lig med denne node værdi? Ja? PUBLIKUM: [uhørligt]. JASON Hirschorn: Ja. I betragtning af dette - Marcus er rigtigt. Vi kunne have måske gjort noget andet. Men i betragtning af, at vi har lavet det, her vi skal frigøre og derefter vende tilbage. Oh boy. Er det bedre? Hvordan er det? OK. Fri og så hvad gør vi tilbage, [uhørligt]? OK. Mangler vi noget? Så hvor skal vi holde styr af den forudgående knude? PUBLIKUM: Jeg tror, ​​det ville gå efter at oprette en ny node. JASON Hirschorn: OK. Så i begyndelsen vi sandsynligvis - yeah, kan vi skabe en pointer til en ny node, ligesom en tidligere knude pointer og en aktuel node pointer. Så lad os indsætte det her. Opret nuværende og tidligere pointere til noderne. Men når vi tilpasse disse henvisninger? Hvor gør vi det i koden? Jeff? PUBLIKUM: - value forhold? JASON Hirschorn: Hvilket én i særdeleshed? PUBLIKUM: Jeg er bare forvirret. Hvis værdien er større end denne node, Betyder det ikke, at du ønsker at gå til den næste knude? JASON HIRSCHHORN: Så hvis vores værdi er større end værdien af ​​dette emne. PUBLIKUM: Ja, så du gerne vil gå længere ned linjen, right? JASON HIRSCHHORN: Right. Så vi behøver ikke indsætte det her. Hvis værdien er mindre end denne knude, så vi gå til den næste knude - eller så vi Indsæt før. PUBLIKUM: Vent, der er det knudepunkt, og som er værdi? JASON HIRSCHHORN: Godt spørgsmål. Værdi per denne funktion definition er, hvad vi får. Så værdien er det antal vi er givet. Så hvis værdien er mindre end denne node, vi har brug for tid til at indsætte. Hvis værdien er større end denne node, vi gå til næste node. Og tilbage til det oprindelige spørgsmål, selv, hvor - PUBLIKUM: Hvis værdien er større end denne node. JASON HIRSCHHORN: Og så hvad gør vi her? Sød. Det er korrekt. Jeg skal bare skrive opdatere pointers. Men ja, med den nuværende du vil opdatere det til peger på den næste. Noget andet vi mangler? Så jeg har tænkt mig at skrive dette kode i gedit. Og mens jeg gør dette, kan du have en par minutter mere til at arbejde på kodning dette i C. Så jeg har input pseudokoden. En hurtig bemærkning, inden vi går i gang. Vi kan ikke være i stand til helt afslutte dette i alle tre af disse funktioner. Der er rigtige løsninger på dem at jeg vil e-mail ud til jer efter sektion, og det vil blive lagt på CS50.net. Så jeg ikke opfordre dig til at gå se på sektionerne. Jeg vil opfordre dig til at prøve disse på din ejer, og derefter bruge den praksis problemer med at tjekke dine svar. De er alle blevet designet til nøje forholde sig til og overholde hvad du er nødt til at gøre på problemet sæt. Så jeg opfordre dig til at praktisere denne på egen hånd og derefter bruge koden til tjekke dine svar. Fordi jeg ønsker at gå videre til hash tabeller på et tidspunkt i afsnittet. Så vi kan ikke komme igennem det hele. Men vi vil gøre så meget vi kan nu. OK. Lad os begynde. Asam, hvordan skaber vi en ny knude? PUBLIKUM: Du behøver struct *. JASON HIRSCHHORN: Så vi har det heroppe. Åh, undskyld. Du sagde struct *. PUBLIKUM: Og så [? art?] knude eller c node. JASON HIRSCHHORN: OK. Jeg har tænkt mig at kalde det new_node så vi kan forblive konsekvente. PUBLIKUM: Og du ønsker at indstille, at til hovedet, den første knude. JASON HIRSCHHORN: OK. Så nu dette peger på - så det har ikke skabt en ny knude endnu. Dette er blot peger på første knudepunkt på listen. Hvordan opretter jeg en ny knude? Hvis jeg har brug for plads til at oprette en ny node. Malloc. Og hvor stor? PUBLIKUM: Størrelsen af ​​struct. JASON HIRSCHHORN: Den størrelsen af ​​struct. Og hvad struct hedder? PUBLIKUM: Node? JASON HIRSCHHORN: Node. Så malloc (sizeof (node)); giver os plads. Og er denne linje - én ting er forkert på denne linje. Er new_node en pointer til en struct? Det er et generisk navn. Hvad er det - node nøjagtigt. Det er en node *. Og hvad gør vi lige efter vi allokere noget, Asan? Hvad er det første, vi gør? Hvad hvis det ikke virker? PUBLIKUM: Åh, kontrollere, om det peger på knudepunktet? JASON HIRSCHHORN: Præcis. Så hvis du new_node lig ligemænd null, hvad gør vi? Dette returnerer en bool, denne funktion. Præcis. Ser godt ud. Noget at tilføje der? Vi vil tilføje ting i slutningen. Men der hidtil ser godt ud. Opret nuværende og tidligere pointere. Michael, hvordan gør jeg det? PUBLIKUM: Du ville have til at gøre en knude *. Du er nødt til at gøre en ikke for new_node men for knuder, vi allerede har. JASON HIRSCHHORN: OK. Så den aktuelle node vi er på. Jeg ringer at curr. Ok. Vi har besluttet at vi vil beholde to, fordi vi har brug for at vide hvad der er før den. Hvad får de initialiseres til? PUBLIKUM: Deres værdi på vores liste. JASON HIRSCHHORN: Så hvad er den første ting på vores liste? Eller hvordan kan vi vide, hvor begyndelse på vores liste er? PUBLIKUM: Er det ikke bestået i funktionen? JASON HIRSCHHORN: Right. Det blev vedtaget i lige her. Så hvis det er gået i funktion, starte på listen, hvad skal vi sat strøm svarende til? PUBLIKUM: List. JASON HIRSCHHORN: List. Det er helt rigtigt. Nu har adressen starten på vores liste. Og hvad med tidligere? PUBLIKUM: List minus en? JASON HIRSCHHORN: Der er intet før det. Så hvad kan vi gøre for at betyde noget? PUBLIKUM: Null. JASON HIRSCHHORN: Ja. Det lyder som en god idé. Perfect. Tak. Gå gennem listen. Konstantin, hvor længe skal vi at gå gennem listen? PUBLIKUM: indtil vi når nul. JASON HIRSCHHORN: OK. Så hvis, mens det for løkke. Hvad laver vi? PUBLIKUM: Måske en for-løkke? JASON HIRSCHHORN: Lad os gøre en for-løkke. OK. PUBLIKUM: Og vi siger til - indtil den aktuelle markørposition er ikke lig med nul. JASON HIRSCHHORN: Så hvis vi kender tilstand, hvordan kan vi skrive en løkke baseret off denne betingelse. Hvilken slags en løkke skal vi bruge? PUBLIKUM: Mens. JASON HIRSCHHORN: Ja. Det giver mere mening baseret off af hvad du sagde. Hvis vi bare ønsker at gå ind vi det ville bare vide, at ting, ville det gøre mening at gøre en while-løkke. Selv om den nuværende ikke er lig nul, hvis værdi er mindre end denne node. Akshar, giv mig denne linje. PUBLIKUM: Hvis den aktuelle-> n n mindre end værdi. Eller omvendt, at. Skift at beslaget. JASON HIRSCHHORN: Undskyld. PUBLIKUM: Skift beslaget. JASON HIRSCHHORN: Så hvis det er større end værdi. Fordi det er forvirrende med den ovenstående kommentar, vil jeg gøre det. Men ja. Hvis vores værdi er mindre end dette node, hvad gør vi? Oh. Jeg har det lige her. Indsæt før. OK. Hvordan gør vi det? PUBLIKUM: Er det stadig mig? JASON HIRSCHHORN: Ja. PUBLIKUM: You - new_node-> næste. JASON HIRSCHHORN: Så hvad er der kommer til at svare? PUBLIKUM: Det kommer til at lige strøm. JASON HIRSCHHORN: Præcis. Og så den anden - hvad gør vi brug for at opdatere? PUBLIKUM: Kontroller, om fortiden er lig nul. JASON HIRSCHHORN: Hvis Forrige - så hvis forrige er lig nul. PUBLIKUM: Det betyder, at det vil at blive hovedet. JASON HIRSCHHORN: Det betyder det er blevet leder. Så hvad gør vi? PUBLIKUM: Vi gør hoved lig new_node. JASON HIRSCHHORN: Hoved lig new_node. Og hvorfor hovedet her, ikke liste? PUBLIKUM: Da hovedet er en global variabel, der er udgangsmaterialet sted. JASON HIRSCHHORN: Sød. OK. Og - PUBLIKUM: Så du ellers prev-> næste lig new_node. Og så skal du returnere sandt. JASON HIRSCHHORN: Hvor vi sat new_node ende? PUBLIKUM: Jeg ville - Jeg satte det i starten. JASON HIRSCHHORN: Så hvad linje? PUBLIKUM: Efter hvis erklæring kontrol, hvis det er kendt. JASON HIRSCHHORN: Lige her? PUBLIKUM: Jeg ville gøre new_node-> n lig værdi. JASON HIRSCHHORN: Det lyder godt. Sandsynligvis det er fornuftigt - vi ikke brug for at vide, hvad listen vi er på fordi vi kun har at gøre med én liste. Så en bedre funktion erklæring for det er bare for at slippe for denne helt og bare indsætte en værdi i hovedet. Vi behøver ikke engang at vide hvad liste, vi befinder os i. Men jeg vil holde det for nu, og derefter ændre det ved at opdatere dias og kode. Så det ser godt ud for nu. Hvis værdi - der kan gøre denne linje? Hvis - hvad gør vi her, Noah. PUBLIKUM: Hvis værdien er større end curr-> n - JASON HIRSCHHORN: Hvordan vi gå til næste node? PUBLIKUM: Curr-> n er lig new_node. JASON HIRSCHHORN: So n er hvilken del af struct? Heltallet. Og new_node er en pointer til en node. Så hvad en del af curr skal vi opdatere? Hvis ikke n, hvad er så den anden side? Noa, hvad er den anden side. PUBLIKUM: Åh, næste. JASON HIRSCHHORN: Next, nøjagtigt. Præcis. Næste er den rigtige. Og hvad har vi brug for at opdatere, Noah? PUBLIKUM: The pointers. JASON HIRSCHHORN: So vi opdateret løbende. PUBLIKUM: Forrige-> næste. JASON HIRSCHHORN: Ja. OK, vi vil holde pause. Hvem kan hjælpe os ud her? Manu, hvad skal vi gøre? PUBLIKUM: Du har fået til at indstille det svarer til curr-> næste. Men gør det inden den tidligere linje. JASON HIRSCHHORN: OK. Noget andet? Akshar. PUBLIKUM: Jeg tror ikke, du er beregnet til at ændre curr-> næste. Jeg tror, ​​du betød at gøre Curr ligemænd curr-> Næste for at gå til næste node. JASON HIRSCHHORN: Så ked, hvor? På hvilke linje? Denne linje? PUBLIKUM: Ja. Gør curr lig curr-> næste. JASON HIRSCHHORN: Så det er korrekt fordi de nuværende er en pointer til en node. Og vi vil have det til at pege på den næste node af, hvad der er ved at blive aktuelt pegede på. Curr selv har en næste. Men hvis vi skulle opdatere curr.next, vi ville være at opdatere den faktiske tone selv, ikke hvor dette pointer peger. Hvad med denne linje, selv om. Avi? PUBLIKUM: Forrige-> næste lig curr. JASON HIRSCHHORN: Så igen, hvis forrige er en pointer til en knude, prev-> næste er den faktiske pointer i noden. Så det ville være en opdatering et pointer i en node til curr. Vi ønsker ikke at opdatere en pointer i en knude. Vi ønsker at opdatere tidligere. Så hvordan gør vi det? PUBLIKUM: Det ville bare være prev. JASON HIRSCHHORN: Right. Forrige er en pointer til en node. Nu vi er ved at ændre den til en ny pointer til et knudepunkt. OK Lad os gå ned. Endelig er denne sidste betingelse. Jeff, hvad gør vi her? PUBLIKUM: Hvis værdi er lig curr-> n. JASON HIRSCHHORN: Undskyld. Åh min godhed. Hvad? Value == curr-> n. Hvad gør vi? PUBLIKUM: Du ville befri vores new_node, og så ville du returnere falsk. JASON HIRSCHHORN: Dette er, hvad vi har skrevet hidtil. Er der nogen, der har noget at tilføje, før vi gør? OK. Lad os prøve det. Kontrol kan nå slutningen af et ikke-void funktion. Avi, hvad sker der? PUBLIKUM: Er du formodes at sætte tilbagevenden sand uden for while-løkken? JASON HIRSCHHORN: Jeg ved det ikke. Vil du have mig til? PUBLIKUM: Pyt. Nej. JASON HIRSCHHORN: Akshar? PUBLIKUM: Jeg tror du mente at sætte return false i slutningen af while-løkken. JASON HIRSCHHORN: Så hvor vil du have det til at gå? PUBLIKUM: Ligesom udenfor while-løkken. Så hvis du afslutter, mens løkken, der betyder at du har nået slutningen, og intet er sket. JASON HIRSCHHORN: OK. Så hvad gør vi her? PUBLIKUM: Du vender tilbage falsk der. JASON HIRSCHHORN: Åh, vi gøre det begge steder? PUBLIKUM: Ja. JASON HIRSCHHORN: OK. Skal vi gå? Åh min godhed. Undskyld. Jeg undskylder for skærmen. Det er slags flipper ud på os. Så vælge en indstilling. Zero, pr koden, afsluttes programmet. Man indsætter noget. Lad os indsætte tre. Indsatsen var ikke en succes. Jeg har tænkt mig at printe ud. Jeg har ikke noget. OK. Måske det var bare et lykketræf. Sæt den ene. Ikke lykkes. OK. Lad os køre gennem GDB virkelig hurtigt at tjekke ud, hvad der foregår. Husk gdb. / Navnet på din Programmet får os ind GDB. Er det en masse at håndtere? Det blinkende? Sandsynligvis. Luk øjnene og tage nogle dybe vejrtrækninger hvis du bliver træt af at kigge på det. Jeg er i GDB. Hvad er det første, jeg gør i GDB? Vi har fået at regne ud hvad der foregår her. Lad os se. Vi har seks minutter til figur ud af, hvad der foregår. Break main. Og hvad gør jeg? Carlos? Kør. OK. Lad os vælge en indstilling. Og hvad betyder N gøre? Næste. Ja. PUBLIKUM: Har du ikke nævne - har du ikke sige, at hovedet, det var initialiseres til nul i begyndelsen. Men jeg troede, du sagde, det var OK. JASON HIRSCHHORN: Lad os gå - lad os se i GDB, og så vil vi gå tilbage. Men det lyder som om du allerede har nogle ideer om, hvad der foregår. Så vi ønsker at indsætte noget. OK. Vi har indsætte. Indtast venligst en int. Vi vil indsætte tre. Og så er jeg på denne linje. Hvordan går jeg starte debugging indsatsen kendt funktion? Åh min godhed. Det er en masse. Er det freaking ud en masse? PUBLIKUM: Åh, det døde. JASON HIRSCHHORN: Jeg har lige trak den ud. OK. PUBLIKUM: Måske er det anden ende af tråden. JASON HIRSCHHORN: Wow. Så bundlinjen - hvad sagde du? PUBLIKUM: Jeg sagde ironien i teknisk vanskeligheder i denne klasse. JASON HIRSCHHORN: jeg kender. Hvis bare jeg havde kontrol over denne del. [Uhørligt] Det lyder godt. Hvorfor tager du ikke fyre begynde at tænke hvad vi kunne have gjort forkert, og vi vil være tilbage i 90 sekunder. Avica, jeg har tænkt mig at spørge dig, hvordan du gå inde insert_node at debug det. Så dette er, hvor vi sidst slap. Hvordan kan jeg gå ind insert_node, Avica, at undersøge, hvad der foregår? Hvad GDB kommando? Break ville ikke tage mig indenfor. Er Marquise vide? PUBLIKUM: Hvad? JASON HIRSCHHORN: Hvad GDB kommando Jeg bruger til at gå inde i denne funktion? PUBLIKUM: Step? JASON HIRSCHHORN: Træd via S. Det tager mig indenfor. OK. New_node mallocing noget plads. At alle ligner dens gang. Lad os undersøge new_node. Det fik noget hukommelse adresse. Lad os se - der er alle korrekte. Så alt her synes at arbejder korrekt. PUBLIKUM: Hvad er forskellen mellem P og skærm? JASON HIRSCHHORN: P står for print. Og så spørger du, hvad der er den Forskellen mellem denne og dette? I dette tilfælde, intet. Men generelt er der nogle forskelle. Og du bør kigge i GDB manual. Men i dette tilfælde, intet. Vi er tilbøjelige til at bruge print, selv om, fordi vi behøver ikke at gøre meget mere end udskrive en enkelt værdi. OK. Så vi er på linje 80 i vores kode, indstilling node * curr svarende til listen. Lad os udskrive curr. Det er lig med listen. Sød. Vent. Det er lig med noget. Det virker ikke rigtigt. Der vi går. Det er fordi i GDB, til højre, hvis Det er den linje, du er på det har ikke udført endnu. Så du er nødt til rent faktisk at skrive næste til at udføre den linje før at se resultaterne. Så her er vi. Vi har lige gennemført denne linje, tidligere er lig nul. Så igen, hvis vi udskriver tidligere vil vi ikke se noget underligt. Men hvis vi rent faktisk udfører det linje, så vil vi se, at denne linje arbejdet. Så vi har curr. De er begge god. Right? Nu er vi på denne linje lige her. Mens curr ikke lig nul. Nå, hvad gør curr lige? Vi så bare det umådeholdent null. Vi udskrives det. Jeg vil printe det ud igen. Så er, at mens løkken kommer til at udføre? PUBLIKUM: Nej. JASON HIRSCHHORN: Så når jeg har skrevet, at linje, kan du se vi hoppede hele vejen ned til bunden, return false. Og så vil vi vende tilbage falsk og gå tilbage til vores program, og til sidst udskrive, ligesom vi så, indsatsen ikke var en succes. Så nogen har nogen ideer om, hvad vi nødt til at gøre for at løse dette? Jeg har tænkt mig at vente, indtil jeg ser et par hænder gå op. Vi har ikke udføre dette. Husk på, dette var den første ting vi lavede. Jeg har ikke tænkt mig at gøre et par. Jeg har tænkt mig at gøre et par. Fordi et par betyder to. Jeg venter i mere end to. Den første indsættelse, curr, som standard er lig nul. Og denne løkke kun udfører hvis curr er ikke nul. Så hvordan kan jeg komme uden om dette? Jeg ser tre hænder. Jeg venter på mere end tre. Marcus, hvad tror du? PUBLIKUM: Tja, hvis du har brug for det udføre mere end én gang, skal du bare ændre det til en gør-while-løkke. JASON HIRSCHHORN: OK. Vil det løse vores problem, selvom? PUBLIKUM: I dette tilfælde ikke på grund af den kendsgerning, at listen er tom. Så har du sandsynligvis bare nødt til at tilføje en erklæring om, at hvis loop udgange så har du til at være i slutningen af listen, hvorefter du kan bare indsætte det. JASON HIRSCHHORN: Jeg kan lide det. Det giver mening. Hvis sløjfen udgange - fordi det vil returnere falsk her. Så hvis loop udgange, så vi er på slutningen af ​​listen, eller måske starte på en liste, hvis der ikke er noget i det, som er det samme som ved udgangen. Så nu er vi ønsker at indsætte noget her. Så hvordan gør denne kode ser, Marcus? PUBLIKUM: Hvis du allerede fået den node malloced, kan du bare sige new_node-> næste lig nul, fordi det skal være i slutningen. Eller new_node-> næste lig nul. JASON HIRSCHHORN: OK. Undskyld. New_node-> næste lig nul fordi vi er i slutningen. Det betyder ikke sætte det i. Hvordan kan vi sætte det på listen? Right. Det er bare at sætte den lig med. Nej hvordan gør vi faktisk sætte den på listen? Hvad peger mod slutningen af ​​listen? PUBLIKUM: Head. JASON HIRSCHHORN: Undskyld? PUBLIKUM: Leder peger til slutningen af ​​listen. JASON HIRSCHHORN: Hvis der er noget i listen, hoved peger på den slutningen af ​​listen. Så der vil arbejde for første indsættelse. Hvad hvis der er et par ting på listen? End vi ønsker ikke at sætte hovedet lig new_node. Hvad ønsker vi at gøre der? Ja? Sandsynligvis tidligere. Vil det fungere? Husk på, at tidligere er bare en pointer til et knudepunkt. Og tidligere er en lokal variabel. Så denne linje vil sætte en lokal variabel, tidligere, er lig med eller peger på det nye knudepunkt. Det vil faktisk ikke sige det på vores liste, selv om. Hvordan kan vi sætte det i vores liste? Akchar? PUBLIKUM: Jeg tror, ​​du gør strøm-> næste. JASON HIRSCHHORN: OK. curr-> næste. Så igen, den eneste grund til at vi er nede Her er, hvad betyder aktuel lige? PUBLIKUM: Lig null. JASON HIRSCHHORN: Og hvad så sker der, hvis vi gør nul-> næste? Hvad skal vi komme? Vi får en segmentering fejl. PUBLIKUM: Do curr lig nul. JASON HIRSCHHORN: Det er det samme som forrige, selv om, fordi der er en lokal variabel vi sætte svarende til det nye knudepunkt. Lad os gå tilbage til vores billede indsætte noget. Sig vi indsætter i slutningen af listen, så lige her. Vi har en aktuel pointer, der er peger på null og et tidligere punkt der peger til 8. Så hvad har vi brug for at opdatere, Avi? PUBLIKUM: Forrige-> næste? JASON HIRSCHHORN: Forrige-> næste er, hvad vi ønsker at opdatere, fordi det rent faktisk vil indsætte det på enden af ​​listen. Vi har stadig en bug, selv om, at vi kommer til at løbe ind. Hvad er det bug? Ja? PUBLIKUM: Det kommer til at vende tilbage falsk i denne sag? JASON HIRSCHHORN: Åh, er der kommer til at vende tilbage falsk. Men der er en anden fejl. Så vi bliver nødt til at sætte til gengæld sandt. PUBLIKUM: Er tidligere stadig lige null øverst på listen? JASON HIRSCHHORN: So tidligere stadig lig nul i begyndelsen. Så hvordan kan vi komme over det? Ja? PUBLIKUM: Jeg tror, ​​du kan gøre en check før while-løkken til at se om det er en tom liste. JASON HIRSCHHORN: OK. Så lad os gå her. Gør en check. Hvis - PUBLIKUM: Så hvis hoved lig lig nul. JASON HIRSCHHORN: Hvis hoved lig lig nul - der vil fortælle os, om det er en tom liste. PUBLIKUM: Og så gøre hoved lig nye. JASON HIRSCHHORN: Hoved lig new_node? Og hvad skal vi gøre? PUBLIKUM: Og så returnere sandt. JASON HIRSCHHORN: Ikke helt. Vi mangler et trin. PUBLIKUM: New_node næste skal pege til null. JASON HIRSCHHORN: Præcis, Alden. Og så kan vi vende tilbage sandt. OK. Men det er stadig en god ide at gøre tingene i slutningen af ​​listen, right? Ok. Vi kan stadig faktisk får til slutningen af ​​listen. Så er denne kode fint, hvis vi er på ende af listen, og der er nogle ting på listen? Right? Fordi vi stadig har Marcus idé. Vi kunne forlade denne løkke, fordi vi er i slutningen af ​​listen. Så har vi stadig ønsker dette kode hernede? PUBLIKUM: Ja. JASON HIRSCHHORN: Ja. Og hvad har vi brug for at ændre dette til? Sandt. Lyder godt til alle, indtil videre? Nogen, der har nogen - Avi, har du noget at tilføje? PUBLIKUM: Nej. JASON HIRSCHHORN: OK. Så vi har lavet et par ændringer. Vi har lavet denne kontrol, inden vi gik ind for en tom liste. Så vi har taget sig af en tom liste. Og her tog vi os af at indsætte noget i slutningen af ​​listen. Så det ser ud som dette, mens loop tage sig af ting i mellem, et eller andet sted på listen, hvis der er ting på listen. OK. Lad os køre dette program igen. Ikke lykkes. PUBLIKUM: Du klarede det ikke. JASON HIRSCHHORN: Åh, Jeg klarede det ikke. God pointe, Michael. Lad os tilføje en make forbundet. Linje 87 er der en fejl. Linie 87. Alden, dette var den linje, du gav mig. Hvad er der galt? PUBLIKUM: Det skal være til null. JASON HIRSCHHORN: Excellent. Præcis højre. Det bør være nul. Lad os gøre igen. Kompilere. OK. Lad os indsætte tre. Indsatsen var en succes. Lad os printe det ud. Åh, hvis bare vi kunne kontrollere. Men vi har ikke gjort det udskrive funktion endnu. Lad os komme noget andet. Hvad skal vi ind? PUBLIKUM: Seven. JASON HIRSCHHORN: Seven? PUBLIKUM: Ja. JASON HIRSCHHORN: Vi har en seg fejl. Så vi fik en, men vi klart kan ikke få to. Det er 05:07. Så kunne vi debug dette tre minutter. Men jeg har tænkt mig at forlade os her og gå videre til hash tabeller. Men igen, svarene for denne kode Jeg vil maile den til dig i en bit. Vi er meget tæt på den. Jeg stærkt opfordre dig til at finde ud af hvad der foregår her, og ordne det. Så jeg vil emaile dig denne kode som godt plus løsning - sandsynligvis opløsningen senere. Først denne kode. Den anden ting, jeg ønsker at gøre, før vi finish er vi ikke har frigjort noget. Så jeg vil gerne vise dig, hvad Valgrind ser ud. Hvis vi kører Valgrind grænser på vores program,. / forbundet. Igen, ifølge dette dias, vi skal løbe valgrind med en form for valgmulighed, i dette tilfælde - Lækage-kontrol = fuld. Så lad os skrive valgrind - Lækage-kontrol = fuld. Så dette vil køre valgrind på vores program. Og nu programmet rent faktisk kører. Så vi kommer til at køre det ligesom før, sætte noget i. Jeg har tænkt mig at sætte i tre. Der virker. Jeg har ikke tænkt mig at forsøge at sætte i noget andet fordi vi kommer til at få en seg falsk i denne sag. Så jeg bare at holde op. Og nu kan du se hernede lække og bunke resumé. Det er de gode ting, du ønsker at tjekke ud. Så bunke resumé - det siger i brug ved afkørsel - otte bytes i en blok. Det ene blok er node vi malloced. Michael, du sagde før en node er otte bites, fordi det har heltal og markøren. Så det er vores knudepunkt. Og så står vi brugte malloc syv gange, og vi befriet noget seks gange. Men vi har aldrig kaldt fri, så jeg har ingen idé om, hvad det taler om. Men er det tilstrækkeligt at sige, at når din program kører, malloc bliver kaldt i nogle andre steder, som vi behøver ikke at bekymre sig om. Så malloc var sandsynligvis kaldt nogle steder. Vi behøver ikke at bekymre dig hvor. Men det er virkelig os. Denne første linie er os. Vi forlod denne blok. Og du kan se, at her i lækagen resumé. Stadig nås - otte bytes i en blok. Det betyder, at hukommelsen - Vi har lækket denne hukommelse. Definitely tabt - noget er tabt for altid. Generelt, vil du ikke se noget der. Stadig nås generelt hvor vil du se ting, hvor du ønsker at se på, hvad kode skal du har frigjort, men du glemte at befri. Og hvis dette ikke var tilfældet, hvis vi gjorde fri alt, vi kan kontrollere det. Lad os bare køre programmet ikke at lægge i noget. Du vil se hernede i brug ved afkørsel - nul bytes i nul blokke. Det betyder, at vi ikke havde noget venstre når programmet forlades. Så før du tænder i pset6 køre valgrind og sørg for at du ikke har enhver memory leaks i dit program. Hvis du har nogen spørgsmål med valgrind, velkommen til at nå ud. Men det er hvordan du bruger det. Meget simpelt - se om du har i brug ved afkørsel - eventuelle bytes i alle blokke. Så vi arbejdede på insert node. Jeg havde to andre funktioner her - printe noder og gratis noder. Igen er disse funktioner, der er vil være godt for dig at øve fordi de vil hjælpe dig ikke kun med disse prøve øvelser, men også om problemet indstillet. De kort på temmelig nøje til tingene du er nødt til at gøre i problem indstillet. Men jeg ønsker at sørge vi komme ind på alt. Og hash tabeller er også afgørende for at hvad vi laver i afsnittet dette uge - eller problemet sæt. Så vi kommer til at afslutte afsnittet taler om hash-tabeller. Hvis du bemærker jeg lavet en lidt hash tabellen. Det er ikke, hvad vi taler om, dog. Vi taler om en anden type hash tabeller. Og på sin kerne, en hash tabel er intet mere end en matrix plus en hash-funktion. Vi kommer til at tale lidt bare for at at sikre alle forstår, hvad en hash-funktionen er. Og jeg fortæller dig nu, at det er intet mere end to ting - en matrix og en hash-funktion. Og her er de skridt gennem denne driver. Der er vores array. Der er vores funktion. Navnlig hashfunktioner nødt til at gøre et par ting med dette. Jeg har tænkt mig at tale specifikt om dette problem indstillet. Det er formentlig kommer til at tage i en streng. Og hvad det kommer til at vende tilbage? Hvilke data type? Alden? Din hash funktion tilbage? Et heltal. Så dette er hvad hash tabel består af - en tabel i form af matrix og en hash-funktion. Hvordan fungerer det? Det virker i tre trin. Vi giver det en nøgle. I dette tilfælde, vil vi give det en streng. Vi kalder hashfunktionen per trin et på nøglen, og vi får en værdi. Konkret vil vi sige vi får et heltal. Det heltal, der er meget specifikke grænser for, hvad der heltal kan være. I dette eksempel vores matrix er størrelse tre. Så hvad numre kan det heltal være. Hvad er intervallet af gyldige værdier for at heltal, tilbagesendelse type af denne hash funktion? Nul, en og to. Pointen i hash funktion er at regne ud stedet i array hvor vores nøgle går. Der er kun tre mulige steder her - nul, en eller to. Så denne funktion bedre afkast nul, en eller to. Nogle gyldigt indice i dette array. Og så afhængigt af hvor det vender tilbage, du kan se der matrix åben bracketing værdien. Det er, hvor vi sætter nøglen. Så vi smider i græskar, vi kommer ud nul. På vifte beslag 0, sætter vi græskar. Vi smider i katte, vi får ud en. Vi sætter kat på én. Vi sætter i edderkop. Vi kommer ud to. Vi sætter edderkop vifte beslag to. Det ville være så rart, hvis det virkede sådan. Men desværre, som vi skal se, det er lidt mere kompliceret. Før vi kommer derhen, eventuelle spørgsmål om denne grundlæggende opsætning af en hash tabel? Dette er et billede af præcis hvad vi trak på tavlen. Men da vi trak den på brættet, jeg vil ikke gå ind i det yderligere. Væsentlige nøgler, den magiske sorte boks - eller i dette tilfælde, krikand box - en hash funktion sætter dem i spande. Og i dette eksempel er vi ikke sætte navn. Vi sætter den tilhørende telefon Antallet af navnet i spanden. Men du kunne meget vel bare sætte navn på spanden. Dette er blot et billede af, hvad vi trak på tavlen. Vi har potentielle faldgruber, selv om. Og der er især to glider, at jeg ønsker at gå over. Den første er om en hash-funktion. Så jeg stillede spørgsmålet, hvad gør en god hashfunktion? Jeg giver to svar. Den første er, at det er deterministisk. I forbindelse med hashfunktioner, hvad betyder det? Ja? PUBLIKUM: Det kan finde indeks i konstant tid? JASON HIRSCHHORN: At er ikke, hvad det betyder. Men det er et godt gæt. Nogen andre har et gæt hvad dette betyder? At en god hash funktion er deterministisk? Annie? PUBLIKUM: At en nøgle kun kan kortlægges til ét sted i hash tabellen. JASON HIRSCHHORN: Det er helt rigtigt. Hver gang du lægger i græskar, det altid returnerer nul. Hvis du lægger i græskar og dit hash funktion returnerer nul, men har en sandsynlighed for at returnere noget andet større end nul - så måske kan det vende tilbage en til tider eller to andre tidspunkter - det er ikke en god hashfunktion. Du er helt rigtigt. Din hash-funktionen skal returnere nøjagtig samme tal, i dette tilfælde, for nøjagtig de samme streng. Måske er det returnerer den samme nøjagtige tal for den samme nøjagtige streng uanset kapitalisering. Men i så fald er det stadig deterministisk fordi flere ting afbildes på den samme værdi. Det er fint. Så længe der kun er én output for et givet input. OK. Den anden ting er, at det returnerer gyldige indeks. Vi bragt op, at tidligere. Denne hash-funktion - oh boy - en hash-funktion skal returnere gyldige indeks. Så sige - lad os gå tilbage til dette eksempel. Min hash funktion tæller op bogstaverne i ordet. Det er hash-funktionen. Og returnerer det heltal. Så hvis jeg har ordet A, er det kommer til at vende tilbage en. Og det kommer til at sætte en lige her. Hvad hvis jeg sætter i ordet bat? Det kommer til at vende tilbage tre. Hvor bliver bat hen? Det passer ikke. Men det skal gå et eller andet sted. Dette er min hash tabellen efter alle, og alt skal gå et sted. Så hvor skal bat hen? Nogen tanker? Gæt? Gode ​​gæt? PUBLIKUM: Zero. JASON HIRSCHHORN: Hvorfor nul? PUBLIKUM: Da tre modulo tre er nul? JASON HIRSCHHORN: Tre modulo tre er nul. Det er en stor gæt, og det er korrekt. Så i dette tilfælde skal sandsynligvis gå på nul. Så en god måde at sikre, at denne hash Funktionen returnerer kun gyldige indekser at modulo det af størrelsen af ​​tabellen. Hvis du modulo Hvad det afkast ved tre, er du altid kommer til at få noget mellem nul, en og to. Og hvis det returnerer altid syv, og du altid modulo af tre, er du altid vil få den samme ting. Så det er stadig deterministiske hvis du modulo. Men der vil sikre, at du aldrig få noget - en ugyldig industri. Generelt bør der modulo ske inde i din hash funktion. Så du behøver ikke at bekymre dig om dette. Du skal bare kan sikre, at dette er en gyldig Index. Eventuelle spørgsmål vedrørende denne potentiel faldgrube? OK. Og der går vi. Næste potentiel faldgrube, og dette er den store. Hvad hvis to taster kort til den samme værdi? Så der er to måder at håndtere dette. Den første hedder lineær sondering, som jeg er ikke kommer til at gå over. Men du skal være fortrolig med, hvordan der virker, og hvad det er. Den anden jeg kommer til at gå over fordi det er den, der mange mennesker vil sandsynligvis ende med at beslutte at bruge i deres problem sæt. Selvfølgelig behøver du ikke at. Men problemet sæt mange mennesker en tendens til at vælge at oprette en hash tabel med separat kæde til at gennemføre deres ordbog. Så vi kommer til at gå over, hvad det betyder at skabe en hash tabel med separat kæde. Så jeg sat i græskar. Den returnerer nul. Og jeg sætter græskar her. Derefter sætte jeg i - hvad er en anden Halloween-tema ting? PUBLIKUM: Candy. JASON HIRSCHHORN: Candy! Det er en stor en. Jeg sætter i slik og slik giver mig også nul. Hvad gør jeg? Nogen idéer? Fordi du alle slags kender hvad separat kæde er. Så nogen ideer hvad man skal gøre? Ja. PUBLIKUM: Sætte strengen faktisk i hash tabellen. JASON HIRSCHHORN: Så vi kommer til at trække den gode idé herovre. OK. PUBLIKUM: Have Hashtable [Uhørligt] markøren, der peger på begyndelsen af ​​en liste. Og så har græskar være den første værdi i det linkede liste og slik være den anden værdi i den linkede liste. JASON HIRSCHHORN: OK. Marcus, der var udestående. Jeg har tænkt mig at bryde ned. Marcus siger ikke overskrive græskar. Det ville være dårligt. Må ikke sætte slik et andet sted. Vi kommer til at sætte dem begge på nul. Men vi kommer til at beskæftige sig med sætte dem på nul ved oprette en liste på nul. Og vi kommer til at oprette en liste over alt, hvad der kortlagt til nul. Og den bedste måde, vi har lært at skabe en liste, der kan vokse og krympe dynamisk ikke er inden for andet array. Så ikke en multi-dimensional array. Men bare at oprette en sammenkædet liste. Så hvad han foreslog - Jeg har tænkt mig at få en ny - er at skabe et array med pointere, en vifte af pegepinde. OK. Enhver idé eller hint, hvad den type af denne pointers skal være? Marcus? PUBLIKUM: Tip til at - JASON HIRSCHHORN: Fordi du sagde en sammenkædet liste, så - PUBLIKUM: Node pointers? JASON HIRSCHHORN: Node pointers. Hvis de ting i vores knyttet listen er knudepunkter, så de bør være node pointers. Og hvad gør de lige i begyndelsen? PUBLIKUM: Null. JASON HIRSCHHORN: Null. Så der er vores tomme ting. Græskar returnerer nul. Hvad gør vi? Walk mig igennem det? Faktisk, Marcus allerede gav mig. Nogen ellers gå mig igennem det. Hvad vi gør, når vi - dette ligner meget hvad vi bare gør. Avi. PUBLIKUM: Jeg har tænkt mig at tage et gæt. Så når du får slik. JASON HIRSCHHORN: Ja. Godt, vi fik græskar. Lad os få vores første. Vi fik græskar. PUBLIKUM: OK. Græskar returnerer nul. Så du sætte det i det. Eller faktisk, du sætter det i den linkede liste. JASON HIRSCHHORN: Hvordan kan vi sætte det i den linkede liste? PUBLIKUM: Åh, det faktiske syntaks? JASON HIRSCHHORN: Bare gå - sige mere. Hvad gør vi? PUBLIKUM: Du skal bare indsætte den som det første knudepunkt. JASON HIRSCHHORN: OK. Så vi har vores knude, græskar. Og nu, hvordan indsætter jeg det? PUBLIKUM: Du tildeler det af markøren. JASON HIRSCHHORN: Hvilket pointer? PUBLIKUM: Markøren på nul. JASON HIRSCHHORN: Så hvor gør dette punkt? PUBLIKUM: At null lige nu. JASON HIRSCHHORN: Jamen, det peger til null. Men jeg lægger i græskar. Så hvor skal det pege? PUBLIKUM: At græskar. JASON HIRSCHHORN: At græskar. Præcis. Så dette peger på græskar. Og hvor gør dette pointer i græskar punkt? Til PUBLIKUM: Null. JASON HIRSCHHORN: At null. Præcis. Så vi lige har indsat noget i den linkede liste. Vi har lige skrev denne kode til at gøre dette. Næsten vi næsten fik det helt revnet. Nu indsætter vi slik. Vores slik går også til nul. Så hvad gør vi med slik? PUBLIKUM: Det afhænger af, hvorvidt ikke vi prøver at sortere det. JASON HIRSCHHORN: Det er helt rigtigt. Det afhænger af, hvorvidt vi forsøger at sortere det. Lad os antage, at vi ikke er kommer til at sortere det. PUBLIKUM: Nå da, da vi diskuterede før, er det enkleste bare at sætte det lige i starten, så markøren fra nul point til slik. JASON HIRSCHHORN: OK. Hold ud. Lad mig skabe slik lige her. Så denne pointer - PUBLIKUM: Yeah, bør nu være at pege på slik. Har derefter markøren fra slik point til græskar. JASON HIRSCHHORN: Ligesom det? Og sige, vi fik en anden ting at kortlægge til nul? PUBLIKUM: Nå, du lige gøre det samme? JASON HIRSCHHORN: Gør det samme. Så i dette tilfælde, hvis vi ikke gør ønsker at holde det sorteret det lyder temmelig simpelt. Vi tager markøren i indice afgivet vores hash-funktionen. Vi har dette punkt til vores nye node. Og så hvad det pegede til tidligere - i dette tilfælde nul i andet tilfælde græskar - at uanset hvad det er at pege på tidligere, tilføjer vi ind i den næste af vores nye knudepunkt. Vi indsætter noget i begyndelsen. I virkeligheden er dette en meget enklere end forsøger at holde listen sorteres. Men igen, vil søgningen blive mere kompliceret på her. Vi vil altid nødt til at gå til slutningen. OK. Eventuelle spørgsmål om separate chaining? Hvordan det virker? Spørg dem nu. Jeg virkelig ønsker at sikre, at du hele forstå dette, før vi hovedet ud. PUBLIKUM: Hvorfor kan du sætte græskar og slik i den samme en del af hash bordet? JASON HIRSCHHORN: Godt spørgsmål. Hvorfor har vi sætte dem i samme en del af hash bordet? Tja, i dette tilfælde vores hash funktion returnerer nul for dem begge. Så de har brug for at gå på indice nul fordi det er her vi kommer til at lede efter dem, hvis vi nogensinde ønsker at se dem op. Igen, med en lineær sondering fremgangsmåde vi ville ikke sætte dem begge på nul. Men i den separate kæde fremgangsmåde vi kommer til at sætte dem begge på nul og derefter oprette en liste fra nul. Og vi ønsker ikke at overskrive græskar blot for at fordi så vil vi antager, at græskar var indsættes aldrig. Hvis vi bare holde én ting i placering, der ville være slemt. Så ville der ikke være nogen chance af os nogensinde - hvis vi nogensinde haft en to eksemplarer, så vi ville blot slette vores oprindelige værdi. Så det er derfor gør vi denne fremgangsmåde. Eller det er derfor vi har valgt - men igen, vi valgte separat sammenkædning fremgangsmåde hvor der er mange andre metoder man kunne vælge. Besvarer det dit spørgsmål? OK. Carlos. Lineær probing ville indebære - hvis vi fandt en kollision på nul, vi ville se i den næste sted at se, om det var åbent og sætte det der. Og så ser vi i den næste sport og se, om det var åben, og sætte det der. Så finder vi den næste tilgængelige åbne stedet og sætte det der. Andre spørgsmål? Ja, Avi. PUBLIKUM: Som en opfølgning på det, hvad mener du med næste plet? I hash tabellen eller på en linket liste. JASON HIRSCHHORN: Til lineær programmering, ingen hægtede lister. Det næste sted på hash tabellen. PUBLIKUM: OK. Så hash tabel ville være initialiseres til størrelse - ligesom antallet af strenge at du var at indsætte? JASON HIRSCHHORN: Du ville ønsker det skal være rigtig stort. Ja. Her er et billede af, hvad vi bare trak på tavlen. Igen har vi en kollision lige her. på 152. Og du vil se vi skabt en sammenkædet liste ud af det. Igen, hash tabellen særskilt kæde fremgangsmåde er ikke den, du nødt til at tage for problemer indstillet seks, men er en, en masse studerende har tendens til at tage. Så på dette notat, lad os tale kortvarigt før vi hovedet ud af om problemet seks, og så vil jeg dele en historie med dig. Vi har tre minutter. Problem sæt seks. Du har fire funktioner - belastning, check, størrelse og losse. Load - godt, vi har stået over belastning lige nu. Vi trak belastning på tavlen. Og vi selv begyndte kodning en masse indsættelse i en sammenkædet liste. Så belastningen ikke er meget mere end hvad vi har netop gjort. Check er, når du har noget indlæst. Det er den samme proces som denne. De samme to første dele, hvor du smider noget i hash-funktionen og få sin værdi. Men nu er vi ikke at indsætte det. Nu leder vi efter det. Jeg har prøve kode skrevet til at finde noget i en sammenkædet liste. Jeg vil opfordre dig til at praktisere det. Men intuitivt at finde noget temmelig ligner indsætte noget. Faktisk vi tegnede et billede for at finde noget i en sammenkædet liste, flytter igennem, indtil du fik til slutningen. Og hvis du fik til slutningen og kunne ikke finde den, så er det der ikke. Så det er check, hovedsageligt. Næste er størrelse. Lad os springe størrelse. Endelig har du losser. Unload er, vi har ikke draget på tavlen eller kodet endnu. Men jeg vil opfordre dig til at prøve kodning det i vores prøve linket liste eksempel. Men losse intuitivt svarer til fri - eller jeg mener ligner kontrollere. Bortset fra nu, hver gang du går igennem, du er ikke blot at markere at se om du har din værdi der. Men du tager denne node og frigøre det væsentlige. Det er, hvad unload beder dig om at gøre. Gratis alt hvad du har malloced. Så du går igennem hele listen igen, går gennem hele hash bord igen. Denne gang ikke kontrollere for at se, hvad der er. Bare gratis hvad der er. Og endelig størrelse. Størrelse bør gennemføres. Hvis du ikke gennemfører størrelse - Jeg vil sige det sådan her. Hvis du ikke gennemfører størrelse på præcis én linje kode, herunder returnere erklæring, du er gør størrelse forkert. Så sørg størrelse, fuld design punkter, så gør du det på præcis én linje kode, herunder afkastet erklæring. Og du behøver ikke pakke op endnu, Akchar. Eager Beaver. Jeg ville sige tak gutter for at komme til afsnittet. Har en Happy Halloween. Dette er mit kostume. Jeg vil være iført dette på torsdag hvis jeg ser dig på kontortid. Og hvis du er nysgerrig om nogle mere baggrund som på dette kostume, føle til at tjekke 2011 Afsnit til en historie om, hvorfor jeg er iført græskar kostume. Og det er en trist historie. Så sørg for at du har nogle væv i nærheden. Men den, hvis du har nogen spørgsmål, jeg vil holde rundt udenfor efter afsnit. Held og lykke på problemet sæt seks. Og som altid, hvis du har nogen spørgsmål, så lad mig det vide.