JASON Hirschhorn: Velkommen alle sammen til Seksjon Seven. Vi er i uke syv av kurset. Og denne kommende torsdag er Halloween så jeg er kledd seg ut som et gresskar. Jeg kunne ikke bøye seg og sette på skoene mine, så det er derfor jeg er bare iført sokker. Jeg er heller ikke på seg noe under dette, så jeg kan ikke ta det av hvis det er distraherende til deg. Jeg beklager på forhånd for det. Du trenger ikke å forestille seg hva som skjer. Jeg iført boksershorts. Så det er alt bra. Jeg har en lengre historie om hvorfor jeg er kledd som et gresskar, men jeg kommer til å lagre det for senere i dette avsnittet fordi jeg ønsker å komme i gang. Vi har mange spennende ting å gå over denne uken. De fleste av dem er knyttet direkte til denne ukes problem sett, feilstavinger. Vi kommer til å gå over knyttes lister og hash tabeller for hele delen. Jeg satte denne listen opp hver uke, en liste over ressurser for å hjelpe deg med materialet på dette kurset. Hvis du på et tap eller hvis du leter etter noen mer informasjon, sjekk ut en av disse ressursene. Igjen, er pset6 feilstavelser, denne ukens PSett. Og det også råder deg, og jeg oppfordrer deg til å bruke noen andre ressurser spesielt for denne PSett. Spesielt de tre jeg har listet opp på skjermen - gdb, som vi har vært kjent med og blitt brukt en stund nå, er kommer til å være svært nyttig denne uken. Så jeg satte det opp her. Men når du arbeider med C, du bør alltid bruke gdb til feilsøke programmene dine. Denne uken også Valgrind. Er det noen som vet hva Valgrind gjør? PUBLIKUM: Den sjekker for minnelekkasjer? JASON Hirschhorn: Valgrind sjekker for minnelekkasjer. Så hvis du malloc noe i ditt program, er du ber for minne. På slutten av programmet, må du å skrive gratis på alt du har malloced å gi minnet tilbake. Hvis du ikke skrive fri på slutten og programmet kommer til en konklusjon, alt vil automatisk bli frigjort. Og for små programmer, er det ikke så stor en avtale. Men hvis du skriver en lengre innkjørings program som ikke slutte, nødvendigvis, i et par minutter eller et par sekunder, deretter minnelekkasjer kan bli en stor avtale. Så for pset6, er en forventning om at du vil ha null minnelekkasjer med programmet. For å sjekke om minnelekkasjer, kjøre Valgrind og det vil gi deg noen fine utgang slik at du vet om eller ikke alt var gratis. Vi skal øve med det senere i dag, forhåpentligvis. Til slutt, diff-kommandoen. Du brukte noe som ligner på det i pset5 med titte verktøyet. Tillater deg å se inni. Du har også brukt diff, også, per oppgavesettet spec. Men i lot deg sammenligne to filer. Du kan sammenligne bitmap fil og info overskrifter av en stab løsning og løsningen i pset5 hvis du valgte å bruke den. Diff vil tillate deg å gjøre det, også. Du kan sammenligne det riktige svaret for denne ukens oppgavesettet til ditt svar og se om det linjer eller se hvor feilene er. Så de er tre gode verktøy som du bør bruke for denne uken, og definitivt sjekke programmet med disse tre verktøyene før du slår det i. Igjen, som jeg har nevnt hver uke, hvis du har noen tilbakemeldinger for meg - både positiv og konstruktiv - gjerne ta turen til nettsiden nederst på dette lysbildet og innspill det der. Jeg virkelig setter pris på noen og alle tilbakemeldinger. Og hvis du gir meg konkrete ting som Jeg kan gjøre for å forbedre eller at jeg er gjør det bra at du vil jeg skal fortsette, jeg tar det til hjerte og virkelig prøver hardt å lytte på tilbakemeldinger. Jeg kan ikke love jeg kommer til å gjøre alt, skjønt, som iført en gresskar kostyme hver uke. Så vi kommer til å tilbringe mesteparten av delen, som jeg nevnte, snakker om lenkede lister og hash tabeller, som vil være direkte relevant for den Problemet satt denne uken. Koblede lister vi skal gå over relativt raskt fordi vi har brukt en god bit tid gå over det i avsnittet. Og så vi får rett inn i koding problemer for lenkede lister. Og så på slutten skal vi snakke om hash tabeller og hvordan de gjelder for dette ukes oppgavesettet. Du har sett denne koden før. Dette er en struct, og det er å definere noe nytt som kalles en node. Og i en node er et heltall akkurat her, og det er en peker til en annen node. Vi har sett dette før. Dette har kommet opp for et par uker nå. Den kombinerer pekere, som vi har vært arbeider med, og structs, som tillater oss å kombinere to forskjellige ting i én datatype. Det er mye som skjer på skjermen. Men all den bør være relativt kjent med deg. På den første linjen, vi erklære en ny node. Og så inne i det nye node, satt jeg heltallet ved at noden til en. Vi ser på neste linje jeg gjør en printf-kommandoen, men jeg har nedtonet printf-kommandoen fordi den egentlig viktig del er denne linjen her - new_node.n. Hva prikken bety? PUBLIKUM: Gå til noden og vurdere verdien n for det. JASON Hirschhorn: Det er helt riktig. Prikk betyr tilgang til n del av denne nye node. Denne neste linje gjør hva? Michael. PUBLIKUM: Det skaper en annen node som vil peke til den nye noden. JASON Hirschhorn: Så det gjør ikke opprette en ny node. Det skaper en hva? PUBLIKUM: En peker. JASON Hirschhorn: En peker til en node, som angitt ved denne noden * her. Så det skaper en peker til en node. Og hvilken node er det peker til, Michael? PUBLIKUM: Ny node? JASON Hirschhorn: Ny node. Og det peker det fordi vi har gitt det adressen til ny node. Og nå i denne linjen ser vi to forskjellige måter uttrykker det samme. Og jeg ønsket å påpeke hvordan disse to tingene er de samme. I den første linjen, Dereference vi pekeren. Så vi går til noden. Det er hva denne stjernen betyr. Vi har sett det før med pekere. Gå til den noden. Det er i parentes. Og deretter få tilgang via dot operatør n element av den noden. Så det tar syntaksen vi så akkurat her og nå bruker den med en peker. Selvfølgelig, det blir litt travelt hvis du skriver disse parentes - som stjerne, og som prikken. Det blir litt travelt. Så vi har litt syntaktisk sukker. Og denne linjen her - ptr_node-> n. Det gjør de samme ting. Så de to kodelinjer er tilsvarende og vil gjøre akkurat det samme. Men jeg ønsket å peke dem ut før vi går videre, slik at du forstår som virkelig denne tingen her er bare syntaktisk sukker for dereferencing pekeren og deretter gå til n del av denne strukturen. Eventuelle spørsmål om dette lysbildet? OK. Så vi kommer til å gå gjennom et par av operasjoner som du kan gjøre på lenkede lister. En lenket liste, husker, er en serie av noder som peker mot hverandre. Og vi vanligvis starter med en peker kalt hodet, generelt, peker på at det første på listen. Så på den første linjen her, vi har vår opprinnelige L først. Slik at ting du kan tenke på - dette tekst akkurat her du kan tenke på som bare pekeren vi har lagret at et sted poeng til det første element. Og i denne lenket liste vi har fire noder. Hver node er en stor boks. Den store boksen inni den store boksen er heltallsdelen. Og så har vi en peker del. Disse boksene er ikke trukket til skala fordi hvor stor er et heltall i byte? Hvor stor nå? Fire. Og hvor stor er en peker? Fire. Så egentlig, hvis vi skulle trekke dette for å skalere begge boksene vil være av samme størrelse. I dette tilfellet ønsker vi å sette inn noe inn i lenket liste. Så du kan se ned her vi setter inn fem Vi krysser gjennom lenket liste, finne hvor fem går, og deretter sette det inn. La oss bryte det ned og gå litt saktere. Jeg kommer til å peke til styret. Så vi har vår node fem som vi har skapt i mallocs. Hvorfor er alle ler? Bare tuller. OK. Så vi har malloced fem. Vi har opprettet denne noden et annet sted. Vi har den klar til å gå. Vi starter foran vår liste med to. Og vi ønsker å sette inn i en sortert mote. Så hvis vi ser to, og vi ønsker å sette i fem, hva gjør vi når vi ser noe mindre enn oss? Hva? Vi ønsker å sette inn fem inn i dette lenket liste, holder det sortert. Vi ser nummer to. Så hva gjør vi? Marcus? PUBLIKUM: Ring pekeren til den neste noden. JASON Hirschhorn: Og hvorfor vi går til den neste? PUBLIKUM: Fordi det er den neste node i listen. Og vi vet bare at annet sted. JASON Hirschhorn: Og fem er større enn to, i særdeleshet. Fordi vi ønsker å holde det sortert. Så fem er større enn to. Så vi går videre til neste. Og nå kommer vi fire. Og hva skjer når vi nå fire? Fem er større enn fire. Så vi holde det gående. Og nå er vi på seks. Og hva ser vi på seks? Ja, Carlos? PUBLIKUM: Seks er større enn fem. JASON Hirschhorn: Seks er større enn fem. Så det er der vi ønsker å sette inn fem. Men husk at hvis vi bare har én pekeren her - dette er vår ekstra peker som er traversering gjennom listen. Og vi peker til seks. Vi har mistet oversikten over hva kommer før seks. Så hvis vi ønsker å sette noe inn denne listen holde det sortert, vi sannsynligvis trenger hvor mange pekere? PUBLIKUM: Two. JASON HIRSCHORN: Two. En til å holde oversikt over gjeldende én og én for å holde styr på det foregående. Dette er bare en enkeltvis lenket liste. Det går bare i en retning. Hvis vi hadde en dobbelt lenket liste, der alt var å peke på ting etter det og ting før det, så vi ville ikke trenger å gjøre det. Men i dette tilfellet ønsker vi ikke å miste rede på hva som kom før oss i tilfelle vi må sette inn fem et sted i midten. Si vi sette inn ni. Hva ville skje når vi kom til åtte? PUBLIKUM: Du måtte få det null poeng. I stedet for å ha null punktet du vil ha å legge til et element og deretter har det peker på ni. JASON HIRSCHORN: Nettopp. Så får vi åtte. Vi kommer til slutten av listen fordi dette peker til null. Og nå, i stedet for at det peker på null vi har det peker til vår nye noden. Og vi setter pekeren i vår nye noden til null. Er det noen som har noen spørsmål om å sette inn? Hva om jeg ikke bryr seg om holde listen sortert? PUBLIKUM: Hold den på begynnelsen eller slutten. JASON HIRSCHORN: Hold den på begynnelsen eller slutten. Hvilken bør vi gjøre? Bobby? Hvorfor slutten? PUBLIKUM: Fordi begynnelsen er allerede fylt. JASON HIRSCHORN: OK. Begynnelsen er allerede fylt. Hvem ønsker å argumentere mot Bobby. Marcus. PUBLIKUM: Vel du sannsynligvis ønske å stikke den i begynnelsen fordi ellers hvis du setter den på Til slutt vil du måtte traversere hele listen. JASON HIRSCHORN: Nettopp. Så hvis vi tenker runtime, den runtime med å sette inn på slutten ville være n, størrelsen på denne. Hva er den store O runtime med å sette inn i begynnelsen? Konstant tid. Så hvis du ikke bryr deg om å holde noe sortert, mye bedre å bare Sett i begynnelsen av denne listen. Og det kan gjøres i konstant tid. OK. Neste operasjon er å finne, som andre - vi har formulert dette som søk. Men vi kommer til å se gjennom lenket liste for enkelte objekt. Dere har sett kode for søke før i forelesningen. Men vi liksom bare gjorde det med sette inn, eller i det minste å sette inn noe sortert. Du ser gjennom, går node ved node, til du finner nummeret som du er leter etter. Hva skjer hvis du kommer slutten av listen? Si jeg leter etter ni og jeg kommer til slutten av listen. Hva gjør vi? PUBLIKUM: Return falsk? JASON HIRSCHORN: return false. Vi fant ikke det. Hvis du kommer til slutten av listen og du ikke finne nummeret du er på jakt etter, er det ikke der. Eventuelle spørsmål om å finne? Hvis dette var en sortert liste, hva ville være annerledes for vår søke? Yeah. PUBLIKUM: Det ville finne den første verdien som er større enn den du leter etter, og deretter return false. JASON HIRSCHORN: Nettopp. Så hvis det er en sortert liste, hvis vi får til noe som er større enn hva vi leter etter, trenger vi ikke å holde det gående til slutten av listen. Vi kan på det tidspunktet return false fordi vi ikke kommer til å finne den. Spørsmålet er nå, vi har snakket om holde lenkede lister sortert, holde dem usortert. Det kommer til å være noe du er sannsynligvis nødt til å tenke på når koding problem satt fem hvis du velge en hash tabell med separat chaining tilnærming, som vi skal snakke om senere. Men er det verdt det å holde listen sortert og da kunne kanskje ha raskere søk? Eller er det bedre å raskt sette inn noe i konstant runtime, men da har lenger søke? Det er en avveining der at du får bestemme hva som er mer passende for ditt spesifikke problem. Og det er ikke nødvendigvis en helt rett svar. Men det er absolutt en avgjørelse du får å gjøre, og sannsynligvis bra for å forsvare som i for eksempel en kommentar eller to hvorfor du valgte en over den andre. Endelig sletting. Vi har sett sletting. Det er likt søking. Vi ser for elementet. Si vi prøver å slette seks. Så finner vi seks her. Det som vi må sørge for at vi gjør er at uansett hva som peker til seks - som vi ser i trinn to ned her - Uansett hva som peker til seks behovene til hoppe over seks nå og endres til uansett seks peker til. Vi ønsker ikke å noensinne foreldreløs resten av vår liste ved å glemme å sette det forrige pekeren. Og deretter av og til, avhengig på programmet, vil de bare slette denne noden helt. Noen ganger vil du ønsker å returnere den verdi som finnes i denne noden. Så det er slik sletting fungerer. Eventuelle spørsmål om du vil slette? PUBLIKUM: Så hvis du kommer til å slette det, ville du bare bruke gratis fordi antagelig det ble malloced? JASON HIRSCHORN: Hvis du ønsker å frigjøre noe som er helt riktig, og du malloced det. Si at vi ønsket å returnere denne verdien. Vi kan gå tilbake seks og deretter gratis denne noden og Ring gratis på den. Eller ville vi trolig kalle fri første og deretter returnere seks. OK. Så la oss gå videre til å praktisere koding. Vi kommer til å kode tre funksjoner. Den første heter insert_node. Så du har kode som jeg mailet deg, og hvis du ser på dette senere du kan få tilgang til koden i linked.c på CS50 nettstedet. Men i linked.c, det er noen skjelett kode som allerede er blitt skrevet for deg. Og så er det et par funksjoner du trenger å skrive. Først skal vi skrive insert_node. Og hva insert_node gjør Er setter inn et heltall. Og du gir heltallet inn i en lenket liste. Og i særdeleshet, trenger du for å holde listen sorteres fra minst til størst. Dessuten trenger du ikke ønsker å sette inn eventuelle duplikater. Til slutt, som du kan se insert_node returnerer en bool. Så du skal la brukeren vite hvorvidt innsatsen var vellykket ved å returnere sant eller usant. På slutten av dette programmet - og for dette stadiet trenger du ikke å bekymre seg om å frigjøre noe. Så alt du gjør er å ta et heltall og sette det inn i en liste. Det er det jeg spør deg om å gjøre nå. Igjen, i linked.c, som du alle har, er skjelettet koden. Og du bør se mot bunnen prøven funksjon erklæring. Men før du går inn i koding det i C, jeg sterkt oppfordre deg til å gå gjennom trinnene har vi vært praktisere hver uke. Vi har allerede gått gjennom et bilde av denne. Så du bør ha en viss forståelse av hvordan dette fungerer. Men jeg vil oppfordre deg til å skrive noen pseudo før dykking i. Og vi kommer til å gå over pseudo som en gruppe. Og så når du har skrevet din pseudo, og når vi har skrevet vår pseudo som en gruppe, kan du gå inn koding det i C. Som en heads up, den insert_node funksjon er trolig den vanskeligste av de tre vi kommer til å skrive fordi jeg lagt noen ekstra restriksjoner til programmering, spesielt at du kommer ikke til å sette inn noen duplikater og at listen bør forbli sortert. Så dette er en ikke-triviell program at du trenger å kode. Og hvorfor ikke ta fem på syv minutter bare for å få jobbe på pseudo og koden. Og så vil vi starte går som en gruppe. Igjen, hvis du har noen spørsmål bare rekk opp hånden, og jeg vil komme rundt. . Vi har også vanligvis gjør disse - eller jeg ikke eksplisitt si deg kan arbeide med mennesker. Men selvsagt, jeg sterkt oppfordre deg, Hvis du har spørsmål, å be Naboen sitter ved siden av deg eller arbeide med noen annet hvis du vil. Dette trenger ikke å være et individ lydløs aktivitet. La oss starte med å skrive litt pseudo på brettet. Hvem kan gi meg den første linjen i pseudo for dette programmet? For denne funksjonen, heller - insert_node. Alden? PUBLIKUM: Så det første jeg gjorde var opprette en ny peker til noden, og jeg initialisert den peker til den samme ting som liste peker til. JASON HIRSCHORN: OK. Så du oppretter en ny peker til listen, for ikke å noden. PUBLIKUM: Høyre. Yeah. JASON HIRSCHORN: OK. Og hva gjør vi ønsker å gjøre? Hva er etter det? Hva om noden? Vi har ikke en node. Vi har bare en verdi. Hvis vi ønsker å sette inn en node, hva gjør vi må gjøre først før vi kan til og med tenke på å sette den? PUBLIKUM: Oh, sorry. vi trenger å malloc plass til en node. JASON HIRSCHORN: Excellent. La oss gjøre - OK. Kan ikke nå så høyt. OK. Vi kommer til å gå ned, og deretter vi bruker to kolonner. Jeg kan ikke gå så - OK. Lag en ny node. Du kan opprette en annen pekeren til listen eller du kan bare bruke listen som den eksisterer. Du trenger egentlig ikke trenger å gjøre det. Så vi oppretter en ny node. Flott. Det er hva vi gjør først. Hva blir det neste? PUBLIKUM: Vent. Skal vi lage en ny node nå eller bør vi vente med å sørge for at det er ingen duplikater av noden på listen før vi lage det? JASON HIRSCHORN: Godt spørsmål. La oss holde det for senere fordi mesteparten av tiden vi skal opprette en ny node. Så vi skal holde at her. Men det er et godt spørsmål. Hvis vi lage det og vi finner et duplikat, hva skal vi gjør før retur? PUBLIKUM: Frigjør den. JASON HIRSCHORN: Yeah. Sannsynligvis frigjøre den. OK. Hva skal vi gjøre etter at vi opprette en ny node? Annie? PUBLIKUM: Vi setter nummer i node? JASON HIRSCHORN: Nettopp. Vi setter tallet - vi malloc plass. Jeg kommer til å forlate det alle som én linje. Men du har rett. Vi malloc plass, og deretter vi sette antallet i. Vi kan til og med sette pekeren en del av den til null. Det er helt riktig. Og hva om etter det? Vi tegnet dette bildet på brettet. Så hva gjør vi? PUBLIKUM: Vi går gjennom listen. JASON HIRSCHORN: Gå gjennom listen. OK. Og hva sjekker vi for hver node. Kurt, hva gjør vi sjekke for ved hver node? PUBLIKUM: Se om n verdien av at node er større enn verdien n vår node. JASON HIRSCHORN: OK. Jeg kommer til å gjøre - ja, OK. Så det er n - Jeg kommer til å si hvis verdien er større enn denne noden, så hva gjør vi? PUBLIKUM: Vel, da vi setter inn tingen rett før det. JASON HIRSCHORN: OK. Så hvis det er større enn dette, så vi vil sette inn. Men vi ønsker å sette det rett før fordi vi også trenger å være holde orden, da, av det som var før. Så setter du inn før. Så vi trolig gått glipp av noe tidligere. Vi trenger nok å være å holde styr på hva som skjer. Men vi vil komme tilbake dit. Så hva verdien er mindre enn? Kurt, hva gjør vi hvis verdien er mindre enn? PUBLIKUM: Da har du bare holde det gående med mindre det er den siste. JASON HIRSCHORN: Jeg liker det. Så går du til neste node. Med mindre det er det siste - vi trolig se etter at i form av en tilstand. Men ja, neste node. Og det begynner å bli for lavt, så vi vil flytte over hit. Men hvis - alle kan se dette? Hvis vi er lik hva gjør vi? Hvis verdien vi prøver å sette inn er lik denne noden verdi? Yeah? PUBLIKUM: [uhørbart]. JASON HIRSCHORN: Yeah. Gitt dette - Marcus er riktig. Vi kunne ha kanskje gjort noe annerledes. Men gitt at vi har skapt det, her vi bør frigjøre og deretter tilbake. Oh boy. Er det bedre? Hvordan er det? OK. Gratis og så hva gjør vi tilbake, [uhørbart]? OK. Er vi mangler noe? Så hvor skal vi holde styr av den tidligere node? PUBLIKUM: Jeg tror det ville gå etter å skape en ny node. JASON HIRSCHORN: OK. Så i begynnelsen vil vi sannsynligvis - ja, kan vi lage en peker til en ny node, som en tidligere node pekeren og en gjeldende node peker. Så la oss sette det her. Lag nåværende og tidligere pekere til nodene. Men da trenger vi justere disse pekere? Hvor skal vi gjøre det i koden? Jeff? PUBLIKUM: - verdiforhold? JASON HIRSCHORN: Hvilke ett spesielt? PUBLIKUM: Jeg er bare forvirret. Hvis verdien er høyere enn denne node, betyr ikke det at du vil gå til neste node? JASON Hirschhorn: Så hvis vår verdi er større enn verdien for denne noden. PUBLIKUM: Ja, så du vil ønske å gå lenger ned linjen, ikke sant? JASON Hirschhorn: Høyre. Så vi ikke sett det her. Hvis verdien er lavere enn denne node, deretter vi går til neste node - eller så vi sett før. PUBLIKUM: Vent, som er denne node, og som er verdi? JASON Hirschhorn: Godt spørsmål. Verdi per denne funksjonen definisjon er hva vi får. Så verdien er antall vi er gitt. Så hvis verdien er mindre enn dette node, trenger vi tid til å sette inn. Hvis verdien er høyere enn denne node, vi går til neste node. Og tilbake til det opprinnelige spørsmålet, skjønt, hvor - PUBLIKUM: Hvis verdien er større enn denne noden. JASON Hirschhorn: Og så hva gjør vi her? Søt. Det er riktig. Jeg skal bare skrive oppdatere pekere. Men ja, med den nåværende du vil oppdatere den til peke til den neste. Noe annet vi mangler? Så jeg kommer til å skrive dette koden på gedit. Og mens jeg gjør dette, kan du ha en par minutter å jobbe med koding dette i C. Så jeg har lagt inn den pseudo. En rask kommentar før vi kommer i gang. Vi kan ikke være i stand til helt føre dette i det hele tatt tre av disse funksjoner. Det er riktige løsninger på dem at jeg vil sende ut til dere etter avsnitt, og det vil bli lagt ut på CS50.net. Så jeg ikke oppfordre deg til gå og se på delene. Jeg oppfordrer deg til å prøve disse på din eier, og deretter bruke den praksisen problemer å sjekke svarene dine. Disse har alle blitt konstruert for å tett forholde seg til og følge hva du har å gjøre på problemet settet. Så jeg oppfordrer deg til å praktisere dette på egen hånd og deretter bruke koden til sjekke svarene dine. Fordi jeg ønsker å gå videre til hasj bord på et tidspunkt i seksjonen. Så vi kan ikke komme gjennom det hele. Men vi skal gjøre så mye vi kan nå. OK. La oss begynne. Asam, hvordan skaper vi en ny node? PUBLIKUM: Du trenger struct *. JASON Hirschhorn: Så vi har det her oppe. Oh, beklager. Du sa struct *. PUBLIKUM: Og så [? slag?] node eller c node. JASON Hirschhorn: OK. Jeg kommer til å kalle det new_node slik at vi kan være konsekvent. PUBLIKUM: Og du vil angi at til hodet, den første noden. JASON Hirschhorn: OK. Så nå dette peker til - så dette har ikke opprettet en ny node ennå. Dette er bare peke på første noden i listen. Hvordan lager jeg en ny node? Hvis jeg trenger plass til å lage en ny node. Malloc. Og hvor stor? PUBLIKUM: Størrelsen på struct. JASON Hirschhorn: The Størrelsen på struct. Og hva struct heter? PUBLIKUM: Node? JASON Hirschhorn: Node. Så malloc (sizeof (node)); gir oss plass. Og er denne linjen - en ting er feil på denne linjen. Er new_node en peker til en struct? Det er et generisk navn. Hva er det - node, akkurat. Det er en node *. Og hva gjør vi rett etter vi malloc noe, Asan? Hva er det første vi gjør? Hva hvis det ikke fungerer? PUBLIKUM: Oh, sjekk om det peker til noden? JASON Hirschhorn: Nettopp. Så hvis du new_node tilsvarer likemenn null, hva gjør vi? Dette returnerer en bool, denne funksjonen. Nettopp. Ser bra ut. Noe å legge til det? Vi vil legge til ting på slutten. Men at så langt ser bra ut. Lag nåværende og tidligere pekere. Michael, hvordan gjør jeg dette? PUBLIKUM: Du ville ha å gjøre en node *. Du måtte gjøre en ikke for new_node men for noder vi allerede har. JASON Hirschhorn: OK. Så gjeldende node vi er på. Jeg kaller det curr. OK. Vi har besluttet vi ønsker å holde to fordi vi trenger å vite hva er før det. Hva er det de får initialisert til? PUBLIKUM: Deres verdi i vår liste. JASON Hirschhorn: Så hva er det første på vår liste? Eller hvordan vet vi hvor begynnelsen av vår liste er? PUBLIKUM: Er det ikke gått inn i funksjonen? JASON Hirschhorn: Høyre. Det ble vedtatt i høyre her. Så hvis det er gått inn i funksjonen, den starter av listen, hva skal vi satt nåværende lik? PUBLIKUM: List. JASON Hirschhorn: List. Det er helt riktig. Nå har det adressen til starten på vår liste. Og hva om tidligere? PUBLIKUM: Liste minus en? JASON Hirschhorn: Det er ingenting før det. Så hva kan vi gjøre for å betegne noe? PUBLIKUM: Null. JASON Hirschhorn: Yeah. Det høres ut som en god idé. Perfekt. Takk. Gå gjennom listen. Constantine, hvor lenge skal vi å gå gjennom listen? PUBLIKUM: Inntil vi nå null. JASON Hirschhorn: OK. Så hvis, mens, for loop. Hva gjør vi? PUBLIKUM: Kanskje en for loop? JASON Hirschhorn: La oss gjøre en for-løkke. OK. PUBLIKUM: Og vi sier for - inntil den gjeldende peker er ikke lik null. JASON Hirschhorn: Så hvis vi kjenner tilstand, hvordan kan vi skrive en løkke basert av den tilstanden. Hva slags løkke bør vi bruke? PUBLIKUM: Selv. JASON Hirschhorn: Yeah. Det er mer fornuftig basert ut av hva du sa. Hvis vi ønsker bare å gå inn vi det ville bare vet at ting, ville det gjøre fornuftig å gjøre en stund loop. Mens nåværende ikke er lik null, Hvis verdien er lavere enn denne noden. Akshar, gi meg denne linjen. PUBLIKUM: Hvis strøm> n n mindre enn verdien. Eller snu denne. Slå at braketten. JASON Hirschhorn: Beklager. PUBLIKUM: Endre braketten. JASON Hirschhorn: Så hvis det er større enn verdien. Fordi det er forvirrende med comment ovenfor, kommer jeg til å gjøre det. Men ja. Hvis vår verdi er mindre enn dette node, hva gjør vi? Oh. Jeg har det rett her. Sett før. OK. Hvordan gjør vi det? PUBLIKUM: Er det fortsatt meg? JASON Hirschhorn: Yeah. PUBLIKUM: Du - new_node-> neste. JASON Hirschhorn: Så hva er som kommer til å like? PUBLIKUM: Det kommer til å like aktuell. JASON Hirschhorn: Nettopp. Og så den andre - hva annet trenger vi å oppdatere? PUBLIKUM: Sjekk om fortiden er lik null. JASON Hirschhorn: Hvis prev - så hvis prev lik null. PUBLIKUM: Det betyr at det kommer å bli leder. JASON Hirschhorn: Det betyr det er blitt hodet. Så hva gjør vi? PUBLIKUM: Vi gjør hodet tilsvarer new_node. JASON Hirschhorn: Leder tilsvarer new_node. Og hvorfor hodet her, ikke liste? PUBLIKUM: Fordi hodet er en global variable, som er startstedet. JASON Hirschhorn: Søt. OK. Og - PUBLIKUM: Da du ellers prev-> neste lik new_node. Og så du returnere true. JASON Hirschhorn: Hvor vi satt new_node slutt? PUBLIKUM: Jeg ville - Jeg satt som i starten. JASON Hirschhorn: Så hvilken linje? PUBLIKUM: Etter hvis setningen sjekke om det er kjent. JASON Hirschhorn: Akkurat her? PUBLIKUM: Jeg ville gjøre new_node-> n lik verdi. JASON Hirschhorn: Høres bra ut. Sannsynligvis er det fornuftig - vi gjør ikke trenger å vite hva liste vi er på fordi vi bare håndtere med en liste. Så en bedre funksjon erklæring for dette er bare for å bli kvitt dette helt og bare sette inn en verdi inn i hodet. Vi trenger ikke engang å vite hva liste vi er i. Men jeg vil holde det for nå og så endre det ved å oppdatere lysbilder og kode. Så det ser bra ut for nå. Hvis verdien - som kan gjøre denne linjen? Hvis - hva gjør vi her, Noah. PUBLIKUM: Hvis verdien er større enn curr-> n - JASON Hirschhorn: Hvordan vi går til neste node? PUBLIKUM: Curr-> n er lik new_node. JASON Hirschhorn: Så n er hvilken del av struct? Den heltall. Og new_node er en peker til en node. Så hvilken del av curr skal vi oppdatere? Hvis ikke n, så hva er den andre delen? Noah, hva er den andre delen. PUBLIKUM: Oh, neste. JASON Hirschhorn: Next, akkurat. Nettopp. Neste er den rette. Og hva annet trenger vi å oppdatere, Noah? PUBLIKUM: Pekerne. JASON Hirschhorn: Så vi oppdatert strøm. PUBLIKUM: Forrige-> neste. JASON Hirschhorn: Yeah. OK, vi skal ta en pause. Hvem kan hjelpe oss her? Manu, hva skal vi gjøre? PUBLIKUM: Du er nødt til å sette det lik curr-> neste. Men gjør det før den forrige linje. JASON Hirschhorn: OK. Noe mer? Akshar. PUBLIKUM: Jeg tror ikke du er ment å endre curr-> neste. Jeg tror du er ment å gjøre Curr likemenn curr-> neste for å gå til neste node. JASON Hirschhorn: Så sorry, hvor? På hvilken linje? Denne linjen? PUBLIKUM: Yeah. Gjør curr tilsvarer curr-> neste. JASON Hirschhorn: Så det er riktig fordi strøm er en peker til en node. Og vi vil at den skal peke til neste node av hva som får tiden pekte på. Curr selv har en neste. Men hvis vi skulle oppdatere curr.next, vi ville være å oppdatere selve notatet seg selv, ikke hvor dette pekeren pekte. Hva om denne linjen, though. Avi? PUBLIKUM: Forrige-> neste lik curr. JASON Hirschhorn: Så igjen, er hvis prev en peker til en node, forrige-> neste er den Selve pekeren i noden. Så dette ville være å oppdatere en pekeren i en node til curr. Vi ønsker ikke å oppdatere en peker på en node. Vi vil oppdatere tidligere. Så hvordan gjør vi det? PUBLIKUM: Det ville bare bli prev. JASON Hirschhorn: Høyre. Prev er en peker til en node. Nå er vi endre den til ny peker til en node. OK La oss gå ned. Til slutt, den siste betingelsen. Jeff, hva gjør vi her? PUBLIKUM: Hvis verdien er lik curr-> n. JASON Hirschhorn: Beklager. Oh my goodness. Hva? Verdi == curr-> n. Hva gjør vi? PUBLIKUM: Du vil frigjøre vår new_node, og da vil du return false. JASON Hirschhorn: Dette er hva vi har skrevet så langt. Er det noen som har noe å legge til før vi gjør? OK. La oss prøve det. Kontroll kan nå slutten av et ikke-void funksjon. Avi, hva er det som skjer? PUBLIKUM: Har du tenkt å sette retur sant utenfor mens loop? JASON Hirschhorn: Jeg vet ikke. Vil du at jeg skal? PUBLIKUM: Never mind. Nei. JASON Hirschhorn: Akshar? PUBLIKUM: Jeg tror du mente å sette return false på slutten av mens loop. JASON Hirschhorn: Så hvor vil du at den skal gå? PUBLIKUM: Like utenfor mens loop. Så hvis du avslutter mens loop Det betyr at du har nådd slutten og ingenting har skjedd. JASON Hirschhorn: OK. Så hva gjør vi her? PUBLIKUM: Du return false der også. JASON Hirschhorn: Åh, vi gjøre det på begge steder? PUBLIKUM: Yeah. JASON Hirschhorn: OK. Skal vi gå? Oh my goodness. Jeg beklager. Jeg beklager for skjermen. Det er en slags galne på oss. Så velg et alternativ. Zero, per koden, avsluttes programmet. Man setter inn noe. La oss sette inn tre. Innsatsen var ikke vellykket. Jeg kommer til å skrive ut. Jeg har ikke noe. OK. Kanskje det var bare et lykketreff. Sett ett. Ikke vellykket. OK. La oss kjøre gjennom GDB veldig raskt for å sjekke ut hva som skjer. Husk gdb. / Navnet ditt Programmet får oss til GDB. Er det mye å håndtere? Den blinkende? Sannsynligvis. Lukk øynene og ta noen dype åndedrag hvis du blir lei av å se på det. Jeg er i GDB. Hva er det første jeg gjør i GDB? Vi er nødt til å finne ut hva som skjer her. La oss se. Vi har seks minutter til figur ut hva som skjer. Bryt hoved. Og så hva gjør jeg? Carlos? Kjør. OK. La oss velge et alternativ. Og hva gjør N? Neste. Yeah. PUBLIKUM: Har du ikke nevne - gjorde du ikke si at hodet, det var initialisert til null ved begynnelsen. Men jeg trodde du sa at det var OK. JASON Hirschhorn: La oss gå - la oss se i GDB, og da vil vi gå tilbake. Men det høres ut som du allerede har noen ideer om hva som skjer. Så vi ønsker å sette inn noe. OK. Vi har sett. Vennligst skriv inn en int. Vi vil sette inn tre. Og da er jeg på denne linjen. Hvordan går jeg starte feilsøking innsatsen kjent funksjon? Oh my goodness. Det er mye. Er det galne mye? PUBLIKUM: Å, det døde. JASON Hirschhorn: jeg bare trakk den ut. OK. PUBLIKUM: Kanskje det er andre enden av ledningen. JASON Hirschhorn: Wow. Så bunnlinjen - hva sa du? PUBLIKUM: Jeg sa det ironiske i teknisk vanskeligheter i denne klassen. JASON Hirschhorn: Jeg vet. Hvis bare jeg hadde kontroll over den delen. [Uhørbart] Det høres flott ut. Hvorfor ikke dere begynne å tenke på hva vi kunne ha gjort galt, og vi vil være tilbake i 90 sekunder. Avica, jeg kommer til å spørre deg hvordan du skal gå inne insert_node å feilsøke det. Så dette er hvor vi sist slapp. Hvordan går jeg inne insert_node, Avica, å undersøke hva som skjer? Hva GDB kommandoen? Break ville ikke ta meg inn. Har Marquise vet? PUBLIKUM: Hva? JASON Hirschhorn: Hva GDB kommando Jeg bruker å gå inne i denne funksjonen? PUBLIKUM: Step? JASON Hirschhorn: Step via S. Det tar meg inne. OK. New_node mallocing litt plass. Det hele ser ut som det kommer. La oss undersøke new_node. Det fikk noen minneadresse. La oss sjekke - det er alt riktig. Så alt her synes å skal. PUBLIKUM: Hva er forskjellen mellom P og skjerm? JASON Hirschhorn: P står for print. Og så du spør hva som er den Forskjellen mellom det og dette? I dette tilfellet, ingenting. Men generelt er det noen forskjeller. Og du bør se i GDB manualen. Men i dette tilfellet, ingenting. Vi har en tendens til å bruke print, skjønt, fordi vi trenger ikke å gjøre mye mer enn skrive ut en enkelt verdi. OK. Så vi er på linje 80 av vår kode, innstilling node * curr lik listen. La oss skrive ut curr. Det tilsvarer listen. Søt. Vent. Det tilsvarer noe. Det virker ikke riktig. Det vi går. Det er fordi i GDB, ikke sant, hvis det er den linjen du er på det har ikke utført ennå. Så du må faktisk skrive ved å utføre linjen før du ser resultatene. Så her er vi. Vi bare henrettet denne linjen, forrige lik null. Så igjen, hvis vi skriver ut forrige vi vil ikke se noe rart. Men hvis vi faktisk utføre det linje, så får vi se at den linjen fungerte. Så vi har curr. De er begge gode. Høyre? Nå er vi på denne linjen her. Mens curr ikke lik null. Vel, hva gjør curr lik? Vi så bare det tangert null. Vi skrev den ut. Jeg skal skrive den ut på nytt. Så er at mens loop kommer til å kjøre? PUBLIKUM: Nei. JASON Hirschhorn: Så når jeg skrev at linje, ser du vi hoppet hele veien ned til bunnen, return false. Og så skal vi return false og gå tilbake til vårt program og til slutt skrive ut, som vi så, innsatsen var ikke vellykket. Så, noen har noen ideer om hva vi trenger å gjøre for å fikse dette? Jeg kommer til å vente til jeg ser et par hender gå opp. Vi gjorde ikke utføre dette. Husk, dette var den første ting vi gjorde. Jeg kommer ikke til å gjøre et par. Jeg kommer til å gjøre noen. Fordi et par betyr to. Jeg skal vente på mer enn to. Den første innsetting, curr, som standard er lik null. Og denne sløyfen bare utfører hvis curr er ikke null. Så hvordan kan jeg komme rundt dette? Jeg ser tre hender. Jeg skal vente på mer enn tre. Marcus, hva tror du? PUBLIKUM: Vel, hvis du trenger det til utføre mer enn én gang, du bare endre den til en do-while-loop. JASON Hirschhorn: OK. Vil det løse vårt problem, skjønt? PUBLIKUM: I dette tilfellet nei på grunn av det faktum at en liste er tom. Så da har du sannsynligvis bare trenger å legge en erklæring om at hvis loop utganger da må du være på slutten av listen, og da du kan bare sette det inn. JASON Hirschhorn: Jeg liker det. Det er fornuftig. Hvis loopen går ut - fordi det vil return false her. Så hvis loop utganger, så vi er på slutten av listen, eller kanskje starte på en liste hvis det ikke er noe i det, som er den samme som utgangen. Så nå ønsker vi å sette inn noe her. Så hvordan ser den koden, Marcus? PUBLIKUM: Hvis du allerede har noden malloced, kan du bare si new_node-> neste lik null fordi det må være på slutten. Eller new_node-> neste lik null. JASON Hirschhorn: OK. Unnskyld. New_node-> neste lik null fordi vi er på slutten. Det betyr ikke sette det i. Hvordan kan vi sette det på listen? Høyre. Det er bare å sette den lik. Nei hvordan gjør vi faktisk sette den på listen? Hva er det som peker til slutten av listen? PUBLIKUM: Head. JASON Hirschhorn: Sorry? PUBLIKUM: Leder peker til enden av listen. JASON Hirschhorn: Hvis det ikke er noe i listen, er hodet peker mot slutten av listen. Så det vil arbeide for første innsetting. Hva om hvis det er et par ting i listen? Enn vi ikke ønsker å sette hodet lik new_node. Hva ønsker vi å gjøre det? Yeah? Sannsynligvis tidligere. Vil det fungere? Husker at forrige er bare en peker til en node. Og forrige er en lokal variabel. Så denne linjen vil sette en lokal variabel, forrige, lik eller peker til denne nye noden. Som ikke vil faktisk si det i vår liste, skjønt. Hvordan kan vi sette det i vår liste? Akchar? PUBLIKUM: Jeg tror du gjøre gjeldende-> neste. JASON Hirschhorn: OK. curr-> neste. Så igjen, den eneste grunnen til at vi er nede her er, hva gjør gjeldende lik? PUBLIKUM: Er lik null. JASON Hirschhorn: Og hva så skjer hvis vi gjør null-> neste? Hva vi skal gjøre for å få? Vi får en segmentering feil. PUBLIKUM: Do curr lik null. JASON Hirschhorn: Det er det samme som forrige, men fordi det er en lokal variabel vi sette lik denne nye noden. La oss gå tilbake til vårt bilde med å sette inn noe. Si at vi setter inn på slutten av listen, så akkurat her. Vi har en gjeldende peker som er peker til null og et tidligere tidspunkt som peker til åtte. Så hva trenger vi å oppdatere, Avi? PUBLIKUM: Forrige-> neste? JASON Hirschhorn: Forrige-> neste er hva vi ønsker å oppdatere fordi det vil faktisk sette det på enden av listen. Vi har fortsatt en bug, skjønt, at vi kommer til å kjøre inn. Hva er det bug? Yeah? PUBLIKUM: Det kommer til å komme tilbake usant i denne saken? JASON Hirschhorn: Åh, er det kommer til å returnere false. Men det er en annen bug. Så vi må sette i retur sant. PUBLIKUM: Har tidligere fortsatt lik null på toppen av listen? JASON Hirschhorn: Så forrige fremdeles lik null helt i begynnelsen. Så hvordan kan vi komme over det? Yeah? PUBLIKUM: Jeg tror du kan gjøre en sjekk før mens loop for å se om det er en tom liste. JASON Hirschhorn: OK. Så la oss gå her. Gjøre en sjekk. Hvis - PUBLIKUM: Så hvis hodet lik lik null. JASON Hirschhorn: Hvis hodet lik lik null - som skal fortelle oss om det er en tom liste. PUBLIKUM: Og så du gjøre hodet lik ny. JASON Hirschhorn: Leder tilsvarer new_node? Og hva annet trenger vi å gjøre? PUBLIKUM: Og så du returnere true. JASON Hirschhorn: Ikke helt. Vi mangler ett trinn. PUBLIKUM: New_node neste har å vise til null. JASON Hirschhorn: Akkurat, Alden. Og så kan vi returnere true. OK. Men det er fortsatt en god idé å gjøre ting ved enden av listen, rett? OK. Vi fortsatt kan faktisk få til enden av listen. Så er denne koden fint hvis vi er på ende av listen, og det er noen ting i listen? Høyre? Fordi vi har fortsatt Marcus idé. Vi kan avslutte denne sløyfen fordi vi er på slutten av listen. Så gjør vi fortsatt ønsker dette kode her nede? PUBLIKUM: Ja. JASON Hirschhorn: Yeah. Og hva trenger vi å endre dette til? Sant. Høres det bra til alle så langt? Noen som har noen - Avi, har du noe å tilføye? PUBLIKUM: Nei. JASON Hirschhorn: OK. Så vi har gjort et par endringer. Vi har gjort denne kontrollen før vi gikk inn for en tom liste. Så vi har tatt vare på en tom liste. Og her vi tok vare på å sette inn noe på slutten av listen. Så det virker som dette mens loop taking vare på ting i mellom, et eller annet sted i listen dersom det er ting på listen. OK. La oss kjøre dette programmet på nytt. Ikke vellykket. PUBLIKUM: Du gjorde ikke det. JASON Hirschhorn: Oh, Jeg gjorde ikke det. Godt poeng, Michael. La oss legge en make koblet. Linje 87 er det en feil. Linje 87. Alden, var dette den linjen du ga meg. Hva er galt? PUBLIKUM: Det må være til null. JASON Hirschhorn: Excellent. Helt riktig. Det burde være null. La oss gjøre igjen. Kompilere. OK. La oss sette inn tre. Innsatsen var vellykket. La oss skrive det ut. Oh, hvis bare vi kunne sjekke. Men vi har ikke gjort det utskriftsfunksjonen ennå. La oss gå inn noe annet. Hva bør vi gå inn? PUBLIKUM: Seven. JASON Hirschhorn: Seven? PUBLIKUM: Ja. JASON Hirschhorn: Vi har et segment feil. Så vi fikk en, men vi klart kan ikke få to. Det er 05:07. Så vi kunne feilsøke dette i tre minutter. Men jeg kommer til å forlate oss her og gå videre til hasj tabeller. Men igjen, svarene for denne koden Jeg vil sende den til deg i en bit. Vi er svært nær den. Jeg sterkt oppfordre deg til å finne ut hva er det som skjer her og fikse det. Så jeg skal sende deg denne koden som vel pluss løsning - sannsynligvis løsningen senere. Først denne koden. Den andre tingen jeg vil gjøre før vi finishen er vi har ikke frigjort noe. Så jeg ønsker å vise deg hva Valgrind ser ut. Hvis vi kjører Valgrind grenser på vårt program,. / koblet. Igjen, i henhold til dette lysbildet, vi bør kjøre Valgrind med noen form for utstyr, i dette tilfellet - Lekkasje-check = full. Så la oss skrive Valgrind - Lekkasje-check = full. Så dette vil kjøre Valgrind på vårt program. Og nå programmet faktisk kjører. Så vi kommer til å kjøre det akkurat som før, sette noe i. Jeg kommer til å sette i tre. Som fungerer. Jeg kommer ikke til å prøve å sette i noe annet fordi vi kommer til å få et segment false i dette tilfellet. Så jeg bare kommer til å slutte. Og nå kan du se ned her lekke og heap sammendrag. Dette er de gode tingene som du ønsker å sjekke ut. Så haugen oppsummering - det står, er i bruk ved avkjørsel - åtte bytes i en blokk. At ett kvartal er node vi malloced. Michael, sa du før en node er åtte biter fordi den har heltallet og pekeren. Så det er vårt node. Og så står det vi brukte malloc syv ganger og vi frigjort noe seks ganger. Men vi har aldri kalt fri, så jeg har ingen anelse om hva dette er snakk om. Men det er nok å si at når programmet kjøres, vises malloc blir kalt i noen andre steder som vi trenger ikke å bekymre seg for. Så malloc ble trolig kalt noen steder. Vi trenger ikke å bekymre deg der. Men dette er egentlig oss. Denne første linjen er oss. Vi forlot den blokken. Og du kan se at her i lekkasjen sammendraget. Fortsatt kan nås - åtte bytes i en blokk. Det betyr at minne - vi har lekket dette minnet. Definitivt tapt - noe er tapt for godt. Vanligvis vil du ikke se noe der. Fortsatt kan nås er generelt der vil du se ting, hvor du vil å se å se hva koden skal du har frigjort, men du glemte å frigjøre. Og så hvis dette ikke var tilfelle, hvis vi gjorde gratis alt, vi kan sjekke det. La oss bare kjøre programmet ikke å sette i noe. Du vil se her nede i bruk ved avkjørsel - null byte i null blokker. Det betyr at vi hadde ingenting igjen når dette programmet gått ut. Så før du slår i pset6, kjøre Valgrind og pass på at du ikke har noen minnelekkasjer i ditt program. Hvis du har noen spørsmål med Valgrind, gjerne nå ut. Men dette er hvordan du bruker den. Veldig enkelt - se om du ha i bruk ved avkjørsel - noen bytes i noen blokker. Så vi jobber med innsatsen node. Jeg hadde to andre funksjoner her - skrive ut noder og gratis noder. Igjen, dette er funksjoner som er kommer til å være bra for deg å øve fordi de vil hjelpe deg ikke bare med disse eksempel øvelser, men også på oppgavesettet. De kartlegge på ganske nært til ting du er nødt til å gjøre i oppgavesettet. Men jeg ønsker å være sikker vi rører på alt. Og hash tabeller er også avgjørende for hva vi gjør i avsnittet dette uke - eller på problemet settet. Så vi kommer til å fullføre seksjonen snakker om hash tabeller. Hvis du merker at jeg har gjort en lite hash table. Det er ikke det vi snakker om, men. Vi snakker om en annen type hash tabeller. Og i sin kjerne, en hash table er ikke noe mer enn en matrise pluss en hash-funksjon. Vi kommer til å snakke for litt bare for å sørge for at alle forstår hva en hash funksjon er. Og jeg forteller deg nå at det er ingenting mer enn to ting - en matrise og en hash-funksjon. Og her er fremgangsmåten gjennom som dette opererer. Det er vårt spekter. Det er vår funksjon. Spesielt hash funksjoner må gjøre et par ting med dette. Jeg kommer til å snakke spesifikt om dette oppgavesettet. Det er trolig kommer til å ta i en streng. Og hva kommer det til å komme tilbake? Hva datatype? Alden? Din hash-funksjon tilbake? Et heltall. Så dette er hva hash tabell består av - et bord i form av matrisen og en hash-funksjon. Hvordan fungerer det? Det fungerer i tre trinn. Vi gir det en nøkkel. I dette tilfellet, vil vi gi det en streng. Vi kaller den hash-funksjon per trinn én på tasten, og vi får en verdi. Spesielt vil vi si vi får et helt tall. Det helt tall, er det svært spesifikke grenser for hva som heltall kan være. I dette eksempelet vårt spekter er størrelsen av tre. Så hva tallene kan det heltall være. Hva er det gyldige verdier for som heltall, returtype denne hash-funksjon? Null, en og to. Poenget med hash funksjon er å finne ut av sted i matrisen hvor vår nøkkel går. Det er bare tre mulige steder her - null, en eller to. Så dette fungerer bedre avkastning null, en eller to. Noen gyldig indice i denne matrisen. Og så avhengig av hvor den kommer tilbake, du kan se det matrise åpen braketten verdien. Det er der vi sette nøkkelen. Så vi kaste inn gresskar, vi kommer ut null. På rekke brakett 0, satte vi gresskar. Vi kaster i katter, vi får ut en. Vi satte katten på en. Vi satt i edderkopp. Vi får ut to. Vi legger edderkopp på rekke brakett to. Det ville være så fint om det virket sånn. Men dessverre, så vi får se, det er litt mer komplisert. Før vi kommer dit, noen spørsmål om denne grunnleggende oppsett av en hash table? Dette er et bilde av akkurat hva vi trakk på brettet. Men siden vi trakk den på tavlen, jeg har ikke tenkt å gå inn i det videre. Hovedsak nøkler, den magiske svarte boksen - eller i dette tilfellet, blågrønn boks - av en hash-funksjon setter dem i bøtter. Og i dette eksempelet er vi ikke å sette navnet. Vi setter det tilknyttede telefon antall navn i bøtta. Men du kan godt bare sette navnet i bøtta. Dette er bare et bilde av hva vi trakk på brettet. Vi har potensielle fallgruver, though. Og det er to i særdeleshet lysbilder som jeg ønsker å gå over. Den første er om en hash-funksjon. Så jeg stilte spørsmålet, hva gjør en god hash-funksjon? Jeg gir to svar. Den første er at det er deterministisk. I sammenheng med hash funksjoner, hva betyr dette? Ja? PUBLIKUM: Det kan finne indeksen i konstant tid? JASON Hirschhorn: That er ikke hva det betyr. Men det er en god gjetning. Noen andre som har en gjetning til hva dette betyr? At en god hash-funksjon er deterministisk? Annie? PUBLIKUM: At en nøkkel kan bare kartlegges til et sted i nøkkeltabell. JASON Hirschhorn: Det er helt riktig. Hver gang du putter i gresskar, den returnerer alltid null. Hvis du putter i gresskar og din hash funksjonen returnerer null, men har en sannsynligheten for å returnere noe annet større enn null - så kanskje det kan returnere en noen ganger eller to ganger - det er ikke en god hash-funksjon. Du er helt riktig. Din hash funksjonen skal returnere den samme eksakte tall, i dette tilfellet, for den samme nøyaktige strengen. Kanskje det returnerer samme nøyaktige heltall for den samme nøyaktige strengen uavhengig av kapitalisering. Men i så fall er det fortsatt deterministisk fordi flere ting er kartlagt på samme verdi. Det er fint. Så lenge det bare er én utgang for et gitt inngangssignal. OK. Det andre er at den returnerer gyldige indekser. Vi tok opp det tidligere. Denne hash-funksjon - oh boy - en hash-funksjon bør returnere gyldige indekser. Så si - la oss gå tilbake til dette eksemplet. Min hash funksjonen legger opp bokstavene i ordet. Det er hash-funksjon. Og returnerer som heltall. Så hvis jeg har ordet A, er det kommer til å returnere en. Og det kommer til å sette en riktig her. Hva hvis jeg legger i ordet balltre? Det kommer til å returnere tre. Hvor kommer balltre gå? Det passer ikke. Men det må gå et sted. Dette er min hash table tross alt, og alt må gå et sted. Så hvor skal bat gå? Noen tanker? Gjetter? Gode ​​gjetninger? PUBLIKUM: Zero. JASON Hirschhorn: Hvorfor null? PUBLIKUM: Fordi tre modulo tre er null? JASON Hirschhorn: Tre modulo tre er null. Det er en stor gjetning, og det er riktig. Så i dette tilfellet bør det sannsynligvis gå i null. Så en god måte å sikre at dette hash Funksjonen returnerer bare gyldige indeksene er til modulo den ved størrelsen av bordet. Hvis du modulo hva dette avkastning ved tre, er du alltid kommer til å få noe mellom null, en, og to. Og hvis dette alltid returnerer syv, og du alltid modulo av tre, er du alltid kommer til å få det samme. Så det er fortsatt determinis hvis du modulo. Men det vil sikre at du aldri få noe - en ugyldig industrien. Generelt bør det modulo skje inni hash-funksjon. Så du trenger ikke å bekymre deg for dette. Du bare kan sikre at dette er en gyldig indice. Eventuelle spørsmål om dette potensiell fallgruve? OK. Og der vi går. Neste potensiell fallgruve, og dette er den store. Hva hvis to taster kartet til samme verdi? Så er det to måter å håndtere dette. Den første er kalt lineære sondering, som jeg er ikke kommer til å gå over. Men du bør være kjent med hvordan som fungerer og hva som er. Den andre en jeg kommer til å gå over fordi det er den som mange folk vil trolig ende opp med å avgjøre å bruke i problemet sitt sett. Selvfølgelig trenger du ikke må. Men for problemet sett, mange mennesker en tendens til å velge å opprette en nøkkeltabell med separat kjeding å implementere deres ordbok. Så vi kommer til å gå over hva det betyr for å opprette en nøkkeltabell med separat kjeding. Så jeg satt i gresskar. Den returnerer null. Og jeg legger gresskar her. Da jeg satt i - hva er en annen Halloween-tema greia? PUBLIKUM: Candy. JASON Hirschhorn: Candy! Det er en stor en. Jeg satt i godteri, og godteri også gir meg null. Hva gjør jeg? Noen ideer? Fordi dere alle vet liksom hva separat kjeding er. Så noen ideer hva jeg skal gjøre? Yeah. PUBLIKUM: Å sette strengen faktisk i hash tabellen. JASON Hirschhorn: Så vi kommer til å tegne den gode ideen over her. OK. PUBLIKUM: Har hashtabellen [Uhørbart] pekeren som peker til begynnelsen på en liste. Og så har gresskar være den første verdien i at lenket liste og godteri være den andre verdien ved at lenket liste. JASON Hirschhorn: OK. Marcus, som var enestående. Jeg kommer til å bryte det ned. Marcus sier ikke skrive gresskar. Det ville være dårlig. Ikke legg godteri et annet sted. Vi kommer til å sette dem begge på null. Men vi kommer til å forholde seg til sette dem på null ved lage en liste på null. Og vi kommer til å lage en liste over alt som kartlagt til null. Og den beste måten vi lærte å lage en liste som kan vokse og krympe dynamisk er ikke innenfor annen rekke. Derfor er ikke en flerdimensjonal matrise. Men å bare lage en lenket liste. Så hva han foreslo - Jeg kommer til å få en ny - er å lage en matrise med pekere, en rekke pekere. OK. Noen ide eller hint hva type av denne pekere bør være? Marcus? PUBLIKUM: Pekere til - JASON Hirschhorn: Fordi du sa en lenket liste, så - PUBLIKUM: Node pekere? JASON Hirschhorn: Node pekere. Hvis de tingene i vår knyttet Listen er noder da de bør være nodepekere. Og hva gjør de like i utgangspunktet? PUBLIKUM: Null. JASON Hirschhorn: Null. Så det er vår tomt ting. Gresskar returnerer null. Hva gjør vi? Gå meg gjennom det? Egentlig, Marcus har allerede gitt meg. Noen andre gå meg gjennom det. Hva vi gjør når vi - dette ser veldig lik hva vi var bare å gjøre. Avi. PUBLIKUM: Jeg kommer til å ta en gjetning. Så når du får godteri. JASON Hirschhorn: Yeah. Vel, fikk vi gresskar. La oss få vår første. Vi fikk gresskar. PUBLIKUM: OK. Gresskar returnerer null. Så du setter den i det. Eller faktisk, du setter det i lenket liste. JASON Hirschhorn: Hvordan kan vi sette den i lenket liste? PUBLIKUM: Oh, selve syntaksen? JASON Hirschhorn: Bare gå - si mer. Hva gjør vi? PUBLIKUM: Du bare setter inn det som den første noden. JASON Hirschhorn: OK. Så vi har vår node, gresskar. Og nå hvordan kan jeg sette det? PUBLIKUM: Du tildeler det til pekeren. JASON Hirschhorn: Hvilken pekeren? PUBLIKUM: Pekeren på null. JASON Hirschhorn: Så hvor gjør dette punktet? PUBLIKUM: Å null akkurat nå. JASON Hirschhorn: Vel, Den peker til null. Men jeg setter i gresskar. Så hvor skal det peke? PUBLIKUM: Å gresskar. JASON Hirschhorn: Til gresskar. Nettopp. Så dette peker til gresskar. Og hvor kommer denne pekeren i gresskar poenget? Å PUBLIKUM: Null. JASON Hirschhorn: Å null. Nettopp. Så vi bare satt inn noe inn i lenket liste. Vi skrev denne koden for å gjøre dette. Nesten vi nesten fikk det helt sprukket. Nå setter vi godteri. Vår godteri går også til null. Så hva skal vi gjøre med godteri? PUBLIKUM: Det avhenger av hvorvidt ikke vi prøver å sortere det. JASON Hirschhorn: Det er helt riktig. Det avhenger av om eller ikke vi prøver å sortere det. La oss anta at vi ikke er kommer til å sortere det. PUBLIKUM: Vel da, som vi diskuterte før, er det enkleste bare å sette den helt i begynnelsen så pekeren fra null poeng til godteri. JASON Hirschhorn: OK. Hold ut. La meg lage godteri her. Så denne pekeren - PUBLIKUM: Ja, skal nå peke til godteri. Da har pekeren fra godteri punkt til gresskar. JASON Hirschhorn: Sånn? Og si vi fikk en annen ting å kartlegge til null? PUBLIKUM: Vel, du bare gjøre det samme? JASON Hirschhorn: Gjør det samme. Så i dette tilfellet, hvis vi ikke gjør det ønsker å holde det sortert det høres ganske enkel. Vi tar pekeren i indice gitt av vår hash-funksjon. Vi har som peker til vår nye noden. Og så hva det var peker til tidligere - i dette tilfelle null, i andre tilfellet gresskar - at, uansett hva det er å peke på tidligere, legger vi inn den neste av vår nye node. Vi setter inn noe i begynnelsen. Faktisk er dette en mye enklere enn prøver å holde listen sorteres. Men igjen, vil søker bli mer komplisert på her. Vi vil alltid ha for å gå til slutten. OK. Eventuelle spørsmål om egen kjeding? Hvordan det virker? Spør dem nå. Jeg virkelig ønsker å sikre at du alle forstå dette før vi drar ut. PUBLIKUM: Hvorfor legger man gresskar sukkertøy og inn i samme del av nøkkeltabell? JASON Hirschhorn: Godt spørsmål. Hvorfor setter vi dem i samme del av nøkkeltabell? Vel, i dette tilfellet vår hash-funksjon returnerer null for dem begge. Så de trenger å gå på indice null fordi det er der vi kommer til å se etter dem hvis vi noen gang ønsker å se dem opp. Igjen, med en lineær tilnærming sondering vi ville ikke sette dem begge på null. Men i det separate kjede tilnærming, vi kommer til å sette dem begge på null og deretter lage en liste av av null. Og vi ønsker ikke å overskrive gresskar rett og slett for at fordi så får vi anta at gresskar var aldri satt inn. Hvis vi bare holde én ting i plassering som ville være dårlig. Da ville det ikke være noen sjanse av oss noensinne - hvis vi noen gang hatt en kopi, så vi ville bare slette vår opprinnelige verdien. Så det er derfor vi gjør denne tilnærmingen. Eller det er derfor vi valgte - men igjen, vi valgte separat kjeding tilnærming, som det er mange andre tilnærminger man kunne velge. Besvarer det spørsmålet ditt? OK. Carlos. Lineær sondering ville innebære - hvis vi fant en kollisjon på null, vi ville se i neste sted for å se om det var åpent, og la den der. Og så ser vi i neste idrett og se om det var åpent og sette den der. Så vi finner den neste tilgjengelige åpent sted og la den der. Eventuelle andre spørsmål? Ja, Avi. PUBLIKUM: Som en oppfølging til det, hva mener du med neste sted? I nøkkeltabell eller i en lenket liste. JASON Hirschhorn: For lineær programmering, ingen lenkede lister. Det neste punktet på hash tabellen. PUBLIKUM: OK. Så hash tabellen ville være stilt i henhold til størrelsen - like antall strenger at du var å sette inn? JASON Hirschhorn: Du ville vil at det skal være veldig stor. Ja. Her er et bilde av hva vi bare trakk på brettet. Igjen har vi en kollisjon her. ved 152. Og du vil se vi opprettet en lenket liste ut av det. Igjen, hash table separat kjeding tilnærming er ikke den du må ta for problemene satt seks, men er en som en masse studenter har en tendens til å ta. Så på dette notatet, la oss snakke kort før vi setter kursen ut om problemet seks, og så skal jeg dele en historie med deg. Vi har tre minutter. Problem satt seks. Du har fire funksjoner - belastning, sjekk, størrelse, og losse. Load - vel, vi har gått Overbelastning akkurat nå. Vi trakk belastning på brettet. Og vi selv startet koding mye sette inn en lenket liste. Så last er ikke mye mer enn hva vi har nettopp gjort. Check er når du har noe lastet. Det er den samme prosessen som dette. De samme to første delene der du kaster noe inn i hash-funksjon og får sin verdi. Men nå vi ikke setter det inn. Nå er vi på jakt etter det. Jeg har eksempelkode skrevet for å finne noe i en lenket liste. Jeg oppfordrer deg til å praktisere det. Men intuitivt å finne noe er ganske lik å sette inn noe. Faktisk, trakk vi et bilde av å finne noe i en lenket liste, flytting gjennom før du kom til slutten. Og hvis du kom til slutten og kunne ikke finner det, så er det ikke det. Så det er sjekk, egentlig. Neste er størrelsen. La oss hoppe størrelse. Endelig har du lesse. Losse er en vi har ikke trukket i styret eller kodet ennå. Men jeg oppfordrer deg til å prøve koding det i vårt utvalg lenket liste eksempel. Men losse intuitivt er lik den fri - eller jeg mener er lik for å sjekke. Bortsett fra nå hver gang du kommer gjennom, du er ikke bare å sjekke for å se om du har din verdi der. Men du tar den noden og frigjør det, egentlig. Det er det losse ber deg om å gjøre. Gratis alt du har malloced. Så du går gjennom hele listen igjen, går gjennom hele hash tabellen igjen. Denne gangen ikke sjekke å se hva som er der. Bare frigjøre hva som er der. Og endelig størrelse. Størrelse bør iverksettes. Hvis du ikke implementere størrelse - Jeg vil si det slik. Hvis du ikke implementere størrelse på nøyaktig en kodelinje inkludert tilbake uttalelsen, er du gjør størrelsen feil. Så sørg for størrelse, for full design poeng, du gjør det i nøyaktig ett linje med kode, inkludert avkastningen uttalelse. Og ikke pakke opp ennå, Akchar. Eager beaver. Jeg ønsket å si takk folkens for å komme til seksjonen. Ha en Happy Halloween. Dette er min drakt. Jeg skal være iført dette på torsdag hvis jeg ser deg på kontortid. Og hvis du er nysgjerrig på noen mer bakgrunn som til denne drakten, føler fri til å sjekke ut 2011-delen for en historie på hvorfor jeg er iført gresskar kostyme. Og det er en trist historie. Så sørg for at du har noen vev i nærheten. Men på det, hvis du har noen spørsmål jeg vil holde rundt utenfor etter seksjon. Lykke til på oppgavesettet seks. Og som alltid, hvis du har noen spørsmål, gi meg beskjed.