[Powered by Google Translate] [Walkthrough - Problem Set 5] [Zamyla Chan - Harvard University] [Dette er CS50. - CS50.TV] 

OK. Hei, alle sammen, og velkommen til Walkthrough 5. 

Pset5 er feilstavinger, der vi skal gjøre en stavekontroll. Spell-brikker er svært viktig. Har dette noen gang skjedd med deg? Du jobber veldig, veldig hamstre på et papir for et sammenstøt og deretter fortsatt ende opp med å få en veldig glød Rade som en D eller D = og alle fordi du er den liverwurst spoiler i hvalen bred ord. Ja, korrekturlesing dine Peppers er et spørsmål om, den ytterste impotens. Dette er et problem som rammer Manly, Manly studenter. Jeg ble en gang fortalt av min sith klasse torturist at jeg aldri ville komme inn i en god kollega. Og det er alt jeg har ønsket, det er alt en gutt ønsker på min alder, bare for å komme inn i en god kollega. Og ikke hvilken som helst kollega. Nei, jeg ønsket å gå til en Ivory Juridisk kollega. Så hvis jeg ikke forbedring, ville gått være mine drømmer om å gå til Harvard, Jale eller fengsel - du vet, i fengsel, New Jersey. Så jeg fikk meg en stavekontroll. Det er et lite utdrag fra en av mine favoritt talte ord kunstnere, Taylor Mali. Allikevel, som han sier, er betydningen av å ha en stavekontroll svært viktig. 

Så velkommen til Walkthrough 5, der vi skal snakke om pset5: feilstavinger, hvor skal vi gjøre vår egen stavekontroll. Verktøykasse for denne uken, distribusjon koden, kommer til å være viktig å se på bare for å forstå de ulike funksjoner som ordlisten kommer til å ha. Vi blir faktisk kommer til å ha flere. C filer som til sammen utgjør vår pset. Og så ser gjennom de forskjellige aspektene, selv om vi faktisk ikke redigerer en av filene, speller.c, å vite hvordan det fungerer med hensyn til dictionary.c, som vi skal skrive, kommer til å være ganske viktig. Den pset spec inneholder også mye nyttig informasjon i form av ting som du kan anta, regler og sånt, så pass på å lese pset spec nøye for tips. Og når du er i tvil om en regel eller noe sånt, så alltid forholde seg til pset spec eller Diskuter. Dette pset kommer til å stole tungt på pekere, så vi ønsker å sørge for at vi forstår forskjellen mellom å legge stjerner foran pekeren navn og ampersand, hvordan å frigjøre dem, osv. Så å være en mester i pekere kommer til å være svært nyttig i denne oppgaven. Vi kommer til å se nærmere på lenkede lister litt mer, hvor vi har elementer som vi kaller noder som har både en verdi så vel som en peker til neste node, og så egentlig lenking forskjellige elementer etter hverandre. Det er noen forskjellige alternativer for å implementere den faktiske ordbok. Vi kommer til å se nærmere på to hovedmetoder, som er hash tabeller og deretter forsøker. I begge disse, de involverer noen form for oppfatningen av en lenket liste hvor du har elementer knyttet til hverandre. Og så skal vi se over hvordan du kan være i stand til å operere rundt lenkede lister, lage dem, navigere i form av hvordan du for eksempel sette inn en node i det eller fri alle nodene også. I form av frigjør noder, det er veldig viktig at når vi malloc minne, etterpå vi frigjøre den. Så vi vil være sikker på at ingen pekeren går unfreed, at vi ikke har noen minnelekkasjer. Vi kommer til å innføre et verktøy kalt Valgrind som kjører programmet og sjekker om alt minne som du tildelt deretter frigjort. Din pset er ferdig når det fungerer og det har full funksjonalitet, men også, forteller Valgrind du at du ikke har funnet noen minnelekkasjer. Til slutt, for dette pset, jeg virkelig ønsker å understreke - Jeg mener, som vanlig, er jeg definitivt en tilhenger av å bruke penn og papir for oppgavesett, men for dette, tror jeg at penn og papir kommer til å være spesielt viktig når du ønsker å være tegning piler til ting og forstå hvordan ting fungerer. Så definitivt prøve å bruke penn og papir for å trekke ting ut før du får koding fordi det kan bli litt rotete. 

Først, la oss gå inn i koblede lister litt. Koblede Listene består av noder, der hver node har en verdi som assosieres med det, så vel som en peker til den neste noden etter det. Et par ting som er viktig med de koblede listene er at vi trenger å huske der vår første noden er, og deretter når vi vet hvor den første noden er, på den måten kan vi få tilgang til noden som den første noden peker og deretter en etter det og den etter det. Og så det siste elementet i lenket liste er at nodens pekeren er alltid kommer til å peke til NULL. Når en node poeng til NULL, så vet du at du har nådd slutten av listen, at det node er den siste, at det er ingenting etter det. Her i denne skjematiske, ser du at pilene er pekere, og den blå delen er der verdien er lagret, og deretter den røde boksen med pekeren til det er nodens pekeren peker til neste node etter det. Og så du ser her, ville D node peker til NULL fordi det er det siste elementet i listen. 

La oss se på hvordan vi kan definere en struct for en node. Og siden vi ønsker å ha flere noder, dette kommer til å bli en typedef struct hvor vi kommer til å ha flere ulike instanser av noder. Og så skal vi definere det som en ny datatype. Her har vi en typedef struct node. I dette eksempelet, vi arbeider med heltallige noder, så vi har et heltall heter verdi og så har vi en annen pekeren, og i dette tilfellet, er det en peker til en node, så vi har en struct node * kalt neste. Og så skal vi kalle dette hele greia node. Sørg for at du følger denne syntaksen. Legg merke til at noden faktisk referert opp ovenfor, samt under klammeparentes. Så for å holde styr på hvor min første node er i denne lenket liste, da jeg har en node peker kalt hodet, og jeg malloc plass nok for størrelsen på en node. Varsel, er imidlertid at hodet faktisk en node pekeren som motsetning til en faktisk node selv. Så hodet faktisk ikke inneholder noen verdi, den peker bare til hvilken den første noden i min lenket liste er. 

For å få en bedre følelse av koblede lister, fordi det er svært viktig å holde styr på å sørge for at du opprettholder kjeden, Jeg liker å tenke på det som folk i en linje holde hender, hvor hver person holder hender med den neste. Du kan ikke se på denne tegningen, men i utgangspunktet de peker til neste person som er i deres kjede. Og så hvis du ønsker å traversere en lenket liste hvor disse menneskene - forestille seg alle disse menneskene har verdier knyttet til dem og peker også på neste person i linjen - Hvis du ønsker å traversere lenket liste, for eksempel, å enten redigere verdiene eller søk etter en verdi eller noe sånt, så vil du ønsker å ha en peker til bestemt person. Så vi kommer til å ha en datatype node pekeren. For dette tilfellet, la oss kalle det markøren. En annen vanlig måte å nevne dette ville være iterator eller noe sånt fordi det er iterating over og faktisk beveger hvilken node den peker til. Dette her vil være vår markøren. Vår markøren vil først peke på det første elementet i listen vår. Og så hva vi ønsker å gjøre er vi ville i utgangspunktet være fortsetter markøren, flytte den fra side til side. I dette tilfellet ønsker vi å flytte den til neste element i listen. Med matriser, hva vi ville gjøre, er vi ville bare si at vi øker indeksen med 1. I dette tilfellet er det vi trenger å gjøre faktisk finne hvilken person denne aktuelle personen peker til, og det kommer til å bli den neste verdien. Så hvis markøren er bare en node peker, så hva vi ønsker å gjøre er vi ønsker å få til verdien som markøren peker på. Vi ønsker å komme til noden, og deretter, når vi er på at node, finne ut hvor den peker til. For å komme til selve noden som markøren peker til, vi vanligvis indikerer det ved (*)-tastene. Som vil gi deg den faktiske noden som markøren peker på. Og så etter det, hva vi ønsker å gjøre er vi ønsker å få tilgang til hva som nodens neste verdi er. For å gjøre det, for å få tilgang til verdiene innsiden av struct, har vi prikken operatør. Så da ville det være (*)-tastene. Neste. Men dette er litt rotete i form av å ha brakettene rundt * markøren, og så erstatter vi dette hele uttalelsen med markør->. Dette er en strek og deretter en større enn tegnet, så gjør en pil. markøren-> neste. Det vil faktisk få deg noden som markøren peker på. Denne verdien er neste. Så i stedet for å ha stjernen og prikken, du erstatte det med en pil. Vær svært forsiktig med å sørge for at du prøver å bruke denne syntaksen. 

Nå som vi har vår markøren, hvis vi ønsker å få tilgang til verdien, før, hadde vi markøren-> neste, men for å få tilgang verdien på noden som markøren peker til, vi bare rett og slett si node-> verdi. Derfra er det av datatype hva vi har definert verdier og noder å være. Hvis det er en int node, deretter markøren-> verdi er bare kommer til å være et heltall. Så vi kan gjøre operasjoner på det, sjekk likheter, tilordne den ulike verdier osv. Så hva du vil gjøre hvis du ønsker å flytte markøren til neste person, du faktisk endre verdien av markøren. Siden markøren er en node peker, endrer du den faktiske pekeren adresse til adressen til den neste node i listen din. Dette er bare noen kode hvor du kan veksle. Hvor jeg har gjør kommentaren noe, det er der du sannsynligvis kommer til å få tilgang til verdien eller gjøre noe å gjøre med det spesifikke noden. Slik starter det, sier jeg at min markøren utgangspunktet kommer til å peke til det første elementet i lenket liste. Og så opp fremover, definerte jeg den som leder av noden. 

Som jeg nevnte tidligere, er å frigjøre veldig viktig. Du ønsker å sørge for at du frigjøre hvert element i listen når du er ferdig med det. Når du ikke trenger å referere noen av disse pekere lenger, du vil være sikker på at du frigjøre alle disse pekere. Men du vil være veldig forsiktig her i at du ønsker å unngå eventuelle minnelekkasjer. Hvis du gratis en person for tidlig, så alle de tips som den noden poeng til kommer til å gå tapt. Går tilbake til den personen eksempel å gjøre det litt mer high stakes, la oss ha disse menneskene, bortsett fra i dette tilfellet er de svever over en innsjø med et monster. Vi vil være sikker på at når vi frigjøre, mister vi ikke og gi slipp på noen noder før vi faktisk har frigjort dem. For eksempel, hvis du skulle bare ringe gratis på denne fyren her, da han ville bli løslatt, men da alle disse gutta vil da gå tapt og de ville drive av og falle ned. Så vi vil være sikker på at i stedet ønsker vi å opprettholde en kobling til resten. Vår hodet pekeren, som peker til det første elementet i listen. Det er typen som et tau forankring den første personen. Hva kan det være lurt å gjøre når du frigjøre en liste har - Hvis du ønsker å frigjøre det første elementet først, så kan du ha en midlertidig peker som peker til hva det første elementet er. Så du har ditt midlertidige pekeren peker her. På den måten har vi tak i den første noden. Og da, siden vi vet at den første noden kommer til å bli frigjort, så kan vi flytte denne tau, dette ankeret, vårt hode, å faktisk peke på hva den første peker til. Så dette hodet peker faktisk til det andre elementet nå. Nå er vi lov til å frigjøre det som er lagret i temp, og så kan vi slette det uten at det truer alle de andre nodene i vår liste. En annen måte at du kunne gjøre dette kan være hver gang du bare frigjøre det siste elementet i listen fordi de er garantert å ikke bli henvist til noe. Så du kan bare frigjøre denne, deretter gratis denne, deretter gratis denne. Det fungerer definitivt, men er litt tregere på grunn av den natur knyttet listene, Vi kan ikke bare hoppe direkte til den siste. Vi må traversere hvert element i lenket liste og sjekk om at man peker til NULL, sjekk hver gang, og deretter når vi kommer til slutten, så gratis som. Hvis du skulle gjøre denne prosessen, vil du faktisk være sjekker her, sjekker her, så sjekker her, frigjør det, deretter gå tilbake, sjekker her, sjekker her, frigjør det, sjekker her, og deretter frigjør det. Det tar litt mer tid. Ja. 

[Student] Vil det være mulig å lage en lenket liste som lagrer en avkjørsel pekeren til slutten? Det ville definitivt være mulig. Å gjenta spørsmålet, er det mulig å ha en lenket liste struktur slik at du har en peker som peker til slutten av lenket liste? Jeg vil si det er mulig, og hver gang du setter noe inn din lenket liste du må oppdatere denne pekeren og sånt. Du ville ha en node * hale, for eksempel. Men når du implementere denne funksjonen, må du tenke på trade-offs, som hvor mange ganger jeg kommer til å bli iterating over dette, hvor vanskelig det kommer til å være å holde styr på halen samt leder så vel som min iterator, og ting som det. Betyr det -? >> [Student] Yeah. Det er mulig, men i form av design beslutninger, må du veie alternativene. 

Her er et skjelett av kode som ville tillate deg å frigjøre hvert element i en lenket liste. Igjen, siden jeg gjentar i en lenket liste, jeg kommer til å ønske å ha noen form for markør eller iterator. Vi gjentar til markøren er NULL. Du ønsker ikke å veksle når markøren er NULL fordi det betyr at det ikke er noe i listen. Så da her jeg lage en midlertidig node * peke på hva jeg vurderer er den første på listen min, og da jeg flytter markøren foran en og deretter gratis hva jeg hadde i midlertidig lagring. 

Nå er vi kommet til å sette inn i koblede lister. Jeg har tre noder i min lenket liste, og la oss gå med enkel sak der vi ønsker å sette inn en node på slutten av vår lenket liste. For å gjøre det, er alt vi ville gjøre at vi ville krysse å finne hvor den nåværende slutten av lenket liste er, så uansett hvilken node peker til NULL - det er dette - og deretter si, faktisk, er dette ikke kommer til å være den siste noden; vi faktisk kommer til å ha en annen. Så vi ville ha dette gjeldende ett punkt til hva vi setter inn. Så nå denne røde personen blir her den siste noden i lenket liste. Og så karakteristisk for den siste node i den koblede listen er at den peker til NULL. Så hva vi ville ha å gjøre er å sette denne røde fyren pekeren til NULL. Det. 

Men hva hvis vi ønsket å sette inn en node i mellom andre og tredje? At man ikke er fullt så enkelt fordi vi ønsker å være sikker at vi ikke la gå av enhver node i vår lenket liste. Hva vi ville ha å gjøre er å sørge for at vi anker oss til hver enkelt. For eksempel, la oss kalle dette den andre. Hvis du sa den andre peker nå til denne nye og du nettopp laget en peker der, så det ville resultere i denne fyren går tapt fordi det ikke er noen kobling til ham. I stedet - jeg vil trekke dette igjen. Unnskylde mine kunstneriske evner. Vi vet at vi kan ikke bare direkte link 2 til den nye. Vi må sørge for at vi holder på til siste. Hva vi kanskje vil gjøre er å ha en midlertidig peker til elementet som kommer til å bli lagt på. Så da har vi en midlertidig pekeren der. Siden vi vet at denne tredje blir holdt styr på, 2 kan nå koble til vår nye. Og hvis denne nye rød fyren kommer til å være i mellom 2 og 3, så hva er den fyren pekeren kommer til å peke på? >> [Student] Temp. Temp. Ja. Så da denne røde fyren neste verdi skal være temp. Når du setter inn koblede lister, så vi at vi kunne enkelt legge noe til slutten ved å opprette en midlertidig array, eller hvis vi ønsket å legge noe inn i midten av tabellen vår, så det ville ta litt mer stokking rundt. Hvis du ønsker å, for eksempel, har en sortert lenket liste, så du må slags veie kostnadene og fordelene ved at fordi hvis du ønsker å ha en sortert array, betyr det at hver gang du setter inn i det, det kommer til å ta litt mer tid. Men hvis du ønsker å senere, som vi finner vi vil ønske å, søk gjennom en lenket liste, så kan det være lettere hvis du vet at alt er i orden. Så vil du kanskje å veie kostnadene og fordelene ved det. 

En annen måte å sette inn en lenket liste er å sette inn i begynnelsen av en liste. Hvis vi trekker vårt anker her - dette er vårt hode - og deretter har disse menneskene knyttet til det, og så har vi en ny node som skal settes inn i begynnelsen, så hva kan vi ønsker å gjøre? Hva ville være galt med å bare si jeg ønsker å koble den røde til blå, fordi det er den første? Hva ville skje her? Alle disse tre ville gå tapt. Slik at vi ikke ønsker å gjøre det. Igjen har vi lært at vi må ha noen form for midlertidig pekeren. La oss velge å ha en midlertidig peker til denne fyren. Da kan vi ha den blå ett punkt til den midlertidige og deretter det røde punktet til den blå. Grunnen til at jeg bruker folk her er fordi vi virkelig ønsker å visualisere holde på folk og sørge for at vi har en link til dem før vi gir slipp på en annen hånd eller noe sånt. 

Nå som vi har en følelse av koblede lister - hvordan vi kan skape en lenket liste og skape strukturene for den bestående av den type som definisjon for en node og deretter sørge for at vi har en peker til leder av det lenket liste - når vi har det og vet hvordan vi skal krysse gjennom en matrise, tilgang til ulike elementer, vet vi hvordan vi skal sette inn og vet hvordan vi skal befri dem, så kan vi komme inn feilstavinger. Som vanlig har vi en del spørsmål som vil få deg til å operere med koblede lister og ulike strukturer som køer og stabler. Da kan vi flytte inn feilstavinger. 

Feilstavinger har i fordelingen koden et par filer av betydning. Første vi legger merke til at vi har denne Makefile her, som vi ikke har virkelig møtt før. Hvis du så inne i pset5 mappen, vil du legge merke til at du har en. H fil, da har du to. c-filer. Hva dette Makefile gjør er før, ville vi bare skriver ringe og deretter programnavnet og deretter vil vi se alle disse argumentene og flagg gikk inn til kompilatoren. Hva Makefile gjør er tillater oss å samle flere filer samtidig og passerer i flaggene som vi ønsker. Her har vi bare se det er en header-fil her. Da vi faktisk har to kildefilene. Vi har speller.c og dictionary.c. Du er velkommen til å redigere Makefile hvis du ønsker det. Legg merke til at her hvis du skriver ren, så hva den gjør er faktisk fjerner noe som er kjernen. Hvis du fikk en segmentering feil, i utgangspunktet du får en kjerne dump. Så denne stygge lille filen vises i katalogen som heter kjerne. Det er lurt å fjerne det for å gjøre den ren. Det fjerner eventuelle exe-filer og. O-filer. 

La oss ta en titt inn dictionary.h. Dette sier at det erklærer en ordbok funksjonalitet. Vi har en maksimal lengde for alle ord i ordlisten. Vi sier at dette kommer til å være lengst mulig ord. Det er av lengde 45. Så vi kommer ikke til å ha noen ord som overstiger den lengden. Her har vi bare har funksjonen prototyper. Vi har ikke den faktiske gjennomføringen fordi det er hva vi skal gjøre for denne pset. Men hva dette betyr er siden vi har å gjøre med større filer her og funksjonalitet på en større skala, er det nyttig å ha en. h fil slik at noen andre lese eller bruke koden kan forstå hva som skjer. Og kanskje de ønsker å gjennomføre prøver hvis du gjorde hash tabeller eller vice versa. Da ville de si min last funksjon, selve gjennomføringen kommer til å variere, men denne prototypen vil ikke endres. Her har vi sjekker, som returnerer true hvis et gitt ord er i ordboken. Da har vi last, som i utgangspunktet tar i en ordbok fil og laster den med til noen datastruktur. Vi har størrelse, som, når den kalles, returnerer størrelsen ordboken, hvor mange ord er lagret i det, og deretter losse, som frigjør alle minne som du kan ha tatt opp mens du gjør ditt ordbok. 

La oss ta en titt på dictionary.c. Vi ser at det ser veldig lik dictionary.h, bortsett fra nå det bare har alle disse Todos i den. Og så er jobben din. Til slutt, vil du være å fylle ut speller.c med alle denne koden. Dictionary.c, når du kjører, ikke er virkelig kommer til å gjøre noe, så vi ser mot speller.c å se den faktiske gjennomføringen av stavekontrollen. Selv om du ikke skal redigere noe av denne koden, det er viktig å lese, forstå når er belastningen ringt, når jeg ringer sjekk, bare for å forstå, kartlegge det ut, se hvordan funksjonen fungerer. Vi ser at det er kontroll for riktig bruk. I hovedsak, når noen kjører stavekontroll, indikerer dette at det er valgfritt for dem å passere i en ordbok fil fordi det kommer til å bli en standard ordliste fil. Og så må de passere i teksten for å være stavekontrolleres. rusage avtaler med tid fordi en del av denne pset som vi vil håndtere senere er ikke bare å få en fungerende stavekontroll arbeider men faktisk få det til å være rask. Og så da det er der rusage kommer til å komme i. Her ser vi den første samtalen til en av våre dictionary.c filer, som er belastningen. Belastning returnerer sant eller usant - sann på suksess, falsk ved feil. Så hvis ordboken ikke er lagt riktig, så speller.c vil returnere en og avslutte. Men hvis den gjør belastningen riktig, så det kommer til å fortsette. Vi fortsetter, og vi ser noen fil I / O her, hvor det kommer til å være håndtere åpne tekstfilen. Her, hva dette betyr er spell-sjekker hvert eneste ord i teksten. Så hva speller.c gjør her er iterating over hver av ordene i tekstfilen og deretter sjekke dem i ordlisten. Her har vi en boolsk feilstavet som vil se om sjekken returnerer sant eller ikke. Hvis ordet er faktisk i ordboken, så sjekk vil returnere true. Det betyr at ordet ikke er stavet feil. Så feilstavet ville være falsk, og det er derfor vi har bang der, indikasjonen. Vi holder på å gå, og da det holder styr på hvor mange feilstavede ord det er i filen. Den fortsetter og lukker filen. Så her, rapporteres det hvor mange feilstavede ord du hadde. Den beregner hvor mye tid det tok å laste ordboken, hvor mye tid det tok å sjekke det, hvor mye tid det tok å beregne størrelsen, som, som vi vil gå på, bør være svært liten, og deretter hvor mye tid det tok å laste ordboken. Her opp over ser vi kallet til å lesse her. Hvis vi sjekke for størrelsen her, så ser vi at her er kallet til størrelse der det avgjør størrelsen på ordlisten. Awesome. 

Vår oppgave for denne pset er å implementere last, som vil aktivere ordboken datastruktur - avhengig av hva du velger, det være seg en hash tabell eller en prøve - med ord fra ordboken filen. Da har du størrelse, som vil returnere antall ord i ordlisten. Og hvis du implementerer belastning på en smart måte, så størrelse bør være ganske enkelt. Da har du sjekke, noe som vil sjekke om et gitt ord er i ordboken. Så speller.c passerer i en streng, og deretter må du sjekke om strengen er inneholdt i ordboken. Legg merke til at vi generelt har standard ordbøker, men i dette pset, gikk i utgangspunktet en ordbok i på alle språk. Så vi kan ikke bare anta at ordet THE er inni. Ordet Foobar kan defineres i en viss ordbok som vi passerer i. Og så har vi losse, som frigjør ordlisten fra minnet. 

Først vil jeg gjerne gå over hash table metoden om hvordan vi kan implementere alle disse fire funksjonene, og så skal jeg gå over prøver metoden, hvordan vi gjennomfører disse fire funksjonene, og på slutten snakke om noen generelle tips når du gjør det pset og også hvordan du kan være i stand til å bruke Valgrind å se etter minnelekkasjer. 

La oss komme inn i hash table metoden. En hash tabell består av en liste med bøtter. Hver verdi, hvert ord, kommer til å gå inn i en av disse skuffer. En hash table ideelt jevnt distribuerer alle disse verdiene som du passerer i og fyller dem deretter i bøtte slik at hver bøtte har omtrent et likt antall verdier i den. Strukturen for en hash table, har vi en rekke knyttet lister. Hva vi gjør er når vi passerer i en verdi, sjekker vi hvor denne verdien skal tilhøre, som bøtte den tilhører, og deretter plassere den i lenket liste som er knyttet til bøtte. Her, hva jeg har er en hash-funksjon. Det er en int hash table. Så for første bøtte, noen heltall under 10 gå inn i den første bøtta. Eventuelle heltall over 10, men under 20 gå inn i de andre, og da så videre og så videre. For meg er hver bøtte representerer disse tallene. Men jeg sier var å passere i 50, for eksempel. Det synes som om den første tre inneholder en rekke av ti tall. Men jeg ønsker å la min hash tabell for å ta i noen form for heltall, så da jeg måtte filtrere ut alle tall over 30 inn i den siste bøtta. Og så så det ville resultere i en slags ubalansert hash table. For å gjenta, er en hash tabell bare en rekke bøtter der hver bøtte er en lenket liste. Og så å finne ut hvor hver verdi går, som bøtte den går inn, du kommer til å ønske det som kalles en hash-funksjon som tar en verdi og så sier denne verdien svarer til en bestemt bøtte. Så opp ovenfor i dette eksempelet, tok min hash-funksjon hver verdi. Det sjekket om det var mindre enn 10 år. Hvis det var, ville det sette det inn i den første bøtta. Det sjekker om det er mindre enn 20, setter den i andre hvis det er sant, sjekker om det er mindre enn 30, og deretter setter den i tredje bøtte, og deretter alt annet faller bare til fjerde bøtte. Så når du har en verdi, din hash-funksjon vil plassere denne verdien inn i den aktuelle bøtte. Den hash-funksjon utgangspunktet trenger å vite hvor mange bøtter du har. Din hash table størrelse, antall bøtter du har, som kommer til å bli et fast antall som er opp til deg, for deg å bestemme, men det kommer til å bli et fast antall. Så din hash-funksjon vil være avhengig av at for å avgjøre hvilken bøtte hver tast går inn slik at det er jevnt fordelt. I likhet med vår gjennomføring av koblede lister, nå hver node i hash table faktisk kommer til å ha en type røye. Så vi har en char array kalt ord og deretter en annen pekeren til neste node, som er fornuftig fordi det kommer til å bli en lenket liste. Husker du da vi hadde knyttet lister, gjorde jeg en node * kalte hue som var peker til den første noden i lenket liste. Men for vår hash table, fordi vi har flere koblede lister, hva vi ønsker er vi ønsker at våre hash table å være som, "Hva er en bøtte?" En bøtte er bare en liste over node pekere, og så hver element i bøtte er faktisk peker til den tilsvarende lenket liste. Å gå tilbake til denne skjematiske, ser du at de bøtter selv er pilene, ikke faktiske noder. En viktig egenskap hash funksjoner er at de er deterministisk. Det betyr at når du hasj nummer 2, det skal alltid returnere samme bøtte. Hver enkelt verdi som går inn i hash-funksjon, hvis det gjentas, har for å få den samme indeksen. Så din hash-funksjonen returnerer indeksen i matrisen hvor denne verdien tilhører. Som jeg nevnte tidligere, er antall bøtter fast, og slik at indeksen at du returnerer må være mindre enn antall bøtter men større enn 0. Grunnen til at vi har hash funksjoner i stedet for bare én lenket liste eller en enkelt rekke, er at vi ønsker å være i stand til å hoppe til en bestemt del lettest hvis vi vet karakteristisk for en verdi - i stedet for å måtte søke gjennom hele hele ordboken, å være i stand til å hoppe til en viss del av den. Din hash-funksjon bør ta hensyn til at ideelt sett hver bøtte har omtrent samme antall nøkler. Siden hash table er en serie med koblede lister, da de koblede listene selv kommer til å ha mer enn én node. I forrige eksempel to forskjellige tall, selv om de ikke var like, når hashed, vil returnere samme indeks. Så når du arbeider med ord, ett ord når hashed ville være den samme hash verdi som et annet ord. Det er hva vi kaller en kollisjon, når vi har en node som, når hashed, den koblede listen på den bøtte er ikke tom. Teknikken som vi kaller det er lineær sondering, hvor du går inn i lenket liste, og deretter finne ut hvor du vil sette noden fordi du har en kollisjon. Du kan se at det kan være en trade-off her, ikke sant? Hvis du har en svært liten hash table, et svært lite antall bøtter, så du kommer til å ha mye av kollisjoner. Men så hvis du gjør en veldig stor hash table, du sannsynligvis kommer til å minimere kollisjoner, men det kommer til å bli et veldig stort datastruktur. Det kommer til å bli trade-offs med det. Så når du gjør ditt pset, prøv å spille rundt mellom kanskje lage en mindre hash table men så vet at det kommer til å ta litt lengre tid å krysse de ulike elementene av disse koplede listene. 

Hvilken last kommer til å gjøre er iterere over hvert ord i ordlisten. Det går i en peker til ordlisten fil. Så du kommer til å dra nytte av fil I / O-funksjoner som du mestrer i pset4 og iterere over hvert eneste ord i ordlisten. Du vil hvert ord i ordboken for å bli en ny node, og du kommer til å plassere hver og en av disse nodene innsiden av ordbok datastruktur. Når du får et nytt ord, vet du at det kommer til å bli en node. Så du kan gå straks og malloc en node peker for hvert nytt ord som du har. Her Jeg ringer min node pekeren new_node og jeg mallocing hva? Størrelsen på en node. Så for å lese selve strengen fra en fil, fordi ordboken er faktisk lagret med et ord, og deretter en ny linje, hva vi kan dra nytte av er funksjonen fscanf, hvor filen er ordlistefilen at vi er gått inn, så det skanner filen etter en streng og steder som streng i det siste argumentet. Hvis du husker tilbake til en av forelesningene, når vi gikk over og slags skrelles lagene tilbake på CS50 biblioteket, vi så en implementering av fscanf der. Å gå tilbake til fscanf, har vi filen vi leser fra, Vi leter etter en streng i denne filen, og så skal vi plassere det inn her har jeg new_node-> ord fordi new_node er en node peker, ikke en faktisk node. Så da jeg sier new_node, jeg ønsker å gå til noden som den peker til og deretter tildele denne verdien til ordet. Vi ønsker å deretter ta det ordet og sett den inn i hash tabellen. Innse at vi har gjort new_node en node peker fordi vi kommer til å ønske å vite hva adressen til noden er når vi setter den inn fordi strukturen av nodene selv, av struct, er at de har en peker til en ny node. Så hva er adressen til noden skal peke til? At adressen skal være new_node. Gjør det fornuftig, hvorfor vi gjør new_node en node * i motsetning til en node? Okay. Vi har et ord. Denne verdien er new_node-> ord. Som inneholder ordet fra ordboken som vi ønsker å legge inn. Så det vi ønsker å gjøre er vi ønsker å ringe vår hash-funksjon på strengen fordi vår hash-funksjon tar i en streng og returnerer oss et heltall, hvor det heltall er indeksen der hashtabellen på at indeksen representerer den bøtte. Vi ønsker å ta den indeksen og deretter gå til den indeksen i hash table og deretter bruke denne lenket liste for å sette noden new_node. Husk at uansett hvordan du velger å sette inn node, enten det er i midten Hvis du ønsker å sortere det eller i begynnelsen eller på slutten, bare sørg for at din siste node peker alltid til NULL fordi det er den eneste måten vi vet hvor det siste elementet i vår lenket liste er. 

Hvis størrelsen er et heltall som representerer antall ord i en ordbok, deretter én måte å gjøre dette på er at når størrelsen kalles vi går gjennom hvert element i vår hash table og deretter iterate gjennom hver lenket liste i hash table og deretter beregne lengden av det, å øke vår telleren 1 til 1. Men hver gang størrelsen kalles, som kommer til å ta lang tid fordi vi kommer til å være lineært sondering hver eneste lenket liste. I stedet kommer det til å være mye lettere hvis du holde oversikt over hvor mange ord gått i. Så hvis du inkluderer en teller i lasten funksjon at oppdateringer som er nødvendig, deretter teller, hvis du setter den til en global variabel, vil kunne nås med størrelse. Så hvilken størrelse kan bare gjøre er på én linje, bare returnere disken verdi, størrelsen av ordlisten, som du allerede omhandlet i last. Det er hva jeg mente da jeg sa at hvis du implementerer belastning på en nyttig måte, deretter størrelsen kommer til å være ganske lett. 

Så nå får vi se. Nå vi har å gjøre med ord fra inngang tekstfil, og så vi kommer til å sjekke om alle disse innspill ord er faktisk i ordboken eller ikke. I likhet med Scramble, ønsker vi å tillate tilfelle ufølsomhet. Du ønsker å være sikker på at alle ordene gikk i, selv om de er blandet sak, når kalt med streng sammenligne, er likeverdige. Ordene i ordlisten tekstfiler er faktisk små bokstaver. En annen ting er at du kan anta at hvert ord bestått i, hver streng, kommer til å være enten alfabetisk eller inneholde apostrofer. Apostrofer kommer til å være gyldig ord i ordlisten vår. Så hvis du har et ord med apostrof S, som er en faktisk legitime ord i ordboken som kommer til å bli en av nodene i din hash table. Sjekk opererer med hvis ordet finnes, så det er nødt til å være i vår hash table. Hvis ordet er i ordboken, så alle ordene i ordlisten er i hash table, så la oss se på dette ordet i hash tabellen. Vi vet at siden vi gjennomført vår hash-funksjon slik at hver unike ord er alltid hashed til samme verdi, da vet vi at i stedet for å lete gjennom hele vår hele hash table, Vi kan faktisk finne lenket liste som dette ordet skal tilhøre. Hvis det var i ordboken, så det ville være i den bøtta. Hva vi kan gjøre, hvis ordet er navnet på vår streng vedtatt i, Vi kan bare hash det ordet og se på lenket liste på verdien av hashtabellen [hash (word)]. Derfra hva vi kan gjøre er at vi har en mindre undergruppe av noder for å søke etter dette ordet, og slik at vi kan traversere lenket liste, bruke et eksempel fra tidligere i walkthrough, og deretter ringe streng sammenligne på ordet der markøren peker til, det ordet, og se om de sammenligne. Avhengig av måten du organiserer din hash-funksjon, hvis det er sortert, kan du være i stand til å returnere falsk litt tidligere, men hvis det er usortert, da du vil fortsette å krysse gjennom lenket liste til du finner det siste elementet i listen. Og hvis du fortsatt ikke har funnet ordet av tiden du har nådd slutten av lenket liste, som betyr at ordet ikke finnes i ordlisten, og slik at ordet er ugyldig, og sjekk bør return false. 

Nå kommer vi til å lesse, hvor vi ønsker å frigjøre alle nodene som vi har malloc'd, så fri alle nodene innsiden av vårt hashtabell. Vi kommer til å ønske å iterere over alle de koblede lister og gratis alle nodene i det. Hvis du ser ovenfor i gjennomgangen til eksempelet der vi frigjøre en lenket liste, så vil du ønsker å gjenta denne prosessen for hvert element i hash tabellen. Og jeg skal gå over dette mot slutten av gjennomgangen, men Valgrind er et verktøy der du kan se om du har riktig frigjort hver node som du har malloc'd eller noe annet som du har malloc'd, noe annet peker. Så det er hash tabeller, der vi har et endelig antall bøtter og en hash-funksjon som vil ta en verdi og deretter tildele denne verdien til en viss bøtte. 

Nå er vi kommet til prøver. Prøver slags utseende som dette, og jeg vil også trekke ut et eksempel. I utgangspunktet har du en hel rekke potensielle bokstaver, og deretter når du konstruere et ord, bokstaven kan knyttes til en ordbok til et bredt spekter av muligheter. Noen ord starter med C, men fortsett med A, men andre fortsetter med O, for eksempel. En trie er en måte å visualisere alle mulige kombinasjoner av disse ordene. En trie kommer til å holde orden på rekkefølgen av bokstaver som utgjør ord, forgrening av når det er nødvendig, når en bokstav kan etterfølges av et multiplum av bokstaver, og på slutten indikerer på hvert punkt hvorvidt det ordet er gyldig eller ikke fordi hvis du stave ordet MAT, er MA Jeg tror ikke et gyldig ord, men MAT er. Og så i trie, ville det tyde på at etter MAT det er faktisk et gyldig ord. Hver node i trie vår er faktisk kommer til å inneholde en rekke node pekere, og vi kommer til å ha, spesielt 27 av disse node pekere, en for hver bokstav i alfabetet samt Apostrofen. Hvert element i denne matrisen er selv kommer til å peke på en annen node. Så hvis det node er NULL, hvis det er ingenting etter det, da vet vi at det er ingen ytterligere bokstaver i det ordet sekvens. Men hvis det noden er ikke NULL, betyr det at det er flere bokstaver i det brevet sekvens. Og så videre, viser hver node enten det er det siste tegnet i et ord eller ikke. 

La oss gå inn et eksempel på en trie. Først må jeg plass til 27 noder i denne matrisen. Hvis jeg har ordet BAR - Hvis jeg har ordet BAR og jeg ønsker å sette det i, den første bokstaven er B, så hvis min trie er tom, B er den andre bokstaven i alfabetet, så jeg kommer til å velge å sette dette her på denne indeksen. Jeg kommer til å ha B her. B kommer til å være en node som peker til en annen rekke av alle mulige tegn som kan følge etter bokstaven B. I dette tilfellet, er jeg håndtere ordet BAR, så A vil gå her. Etter A, har jeg bokstaven R, så da en nå peker på sin egen kombinasjon, og deretter R vil være her. BAR er en komplett ord, så da kommer jeg til å ha R punkt til et annet node som sier at dette ordet er gyldig. Noden skal også ha en rekke noder, men de kan være NULL. Men i utgangspunktet, kan det fortsette sånn. Det vil bli litt mer tydelig når vi går til et annet eksempel, så bare bære med meg der. Nå har vi BAR innsiden av ordboken vår. Nå sier vi har ordet BAZ. Vi starter med B, og vi har allerede B som en av bokstavene som finnes i ordlisten vår. Det er fulgt med A. Vi har A allerede. Men da i stedet har vi Z følgende. Så da et element i matrisen vår kommer til å være Z, og så da at man kommer til å peke til en annen gyldig slutten av ordet. Så vi ser at når vi fortsetter gjennom B og deretter A, det er to forskjellige alternativer for tiden i ordboken vår etter ord som begynner med B og A. Si at vi ønsket å sette inn ordet foobar. Da ville vi lage en oppføring i F. F er en node som peker til en hel rekke. Vi ville finne O, gå til O, knytter O deretter til en hel liste. Vi ville ha B og deretter fortsette, ville vi ha A og deretter R. Så da Foobar traverser hele veien ned til Foobar er et riktig ord. Og så da dette ville være et gyldig ord. Nå sier vår neste ord i ordlisten er faktisk ordet FOO. Vi vil si F. Det som følger F? Jeg har faktisk allerede en plass for O, så jeg kommer til å fortsette. Jeg trenger ikke å lage en ny en. Fortsette. FOO er et gyldig ord i denne ordlisten, så da kommer jeg til å indikere at det er gyldig. Hvis jeg stoppe min sekvens der, ville det være riktig. Men hvis vi fortsatte vår sekvens fra FOO ned til B og bare hadde FOOB, er FOOB ikke et ord, og det er ikke angitt som gyldig. I en trie, har du hver node som indikerer om det er et gyldig ord eller ikke, og deretter hver node har også en rekke av 27 node pekere som deretter peker til noder selv. 

Her er en måte på hvordan du kan ønsker å definere dette. Men akkurat som i den hash table eksempel, der vi hadde en node * hode for å angi begynnelsen av vår lenket liste, vi også kommer til å ønske noen måte å vite hvor begynnelsen av trie vår er. Noen kaller prøver trær, og det er der roten kommer fra. Så vi ønsker roten av treet vårt for å sørge for at vi holder oss jordet dit vår trie er. Vi har allerede slags gikk over måten du kan tenke lasting hvert ord i ordlisten. Hovedsak, for hvert ord du kommer til å ønske å veksle gjennom trie din og vite at hvert element i barn - vi kalte det barn i dette tilfellet - tilsvarer en annen bokstav, du kommer til å ønske å kontrollere disse verdiene ved denne bestemte indeks som tilsvarer bokstaven. Så tenker hele veien tilbake til Cæsar og Vigenere, vel vitende om at hver bokstav du kan slags kartet tilbake til en alfabetisk indeks, definitivt A til Z kommer til å være ganske lett å tilordne til en alfabetisk brev, men dessverre, apostrofer er også en akseptert karakter i ord. Jeg er ikke engang sikker på hva ASCII-verdien er, så for at hvis du ønsker å finne en indeks for å avgjøre om du vil den skal være enten den første eller den siste, må du utføre en hard kodet sjekk for at og deretter sette den i 26-indeksen, for eksempel. Så da du sjekker verdien på barn [i] hvor [i] tilsvarer hva bokstaven du er på. Hvis det er NULL, betyr det at det er for øyeblikket ikke alle mulige tegn stammer fra den forrige sekvens, slik at du kommer til å ønske å malloc og lage en ny node og har som barn [i] peke på det slik at du lager - når vi satt et brev til rektangelet - gjør barn non-NULL og peker inn i den nye noden. Men hvis det ikke er NULL, som i vår forekomst av FOO når vi allerede hadde Foobar, fortsetter vi, og vi er ikke alltid å lage en ny node, men heller bare sette is_word til sann på slutten av ordet. 

Så da som før, fordi her du arbeider med hver bokstav om gangen, det kommer til å bli enklere for deg for størrelse, i stedet for å måtte beregne og gå gjennom hele treet og beregne hvor mange barn har jeg og deretter branching off, husker hvor mange er på venstre side og på høyre side og ting som det, kommer det til å være mye enklere for deg hvis du bare holde styr på hvor mange ord du legger i når du arbeider med last. Og så da at måten størrelse kan bare returnere en global variabel størrelse. 

Nå kommer vi til å sjekke. Samme standarder som før, der vi ønsker å tillate for saken ufølsomhet. I tillegg antar vi at strengene er bare alfabetiske tegn eller apostrofer fordi barn er en matrise av 27 lang, så alle bokstavene i alfabetet pluss apostrof. For sjekk hva du ønsker å gjøre er du ønsker å starte ved roten fordi roten vil peke på en matrise som inneholder alle mulige første bokstavene i et ord. Du kommer til å starte der, og du kommer til å sjekke er denne verdien NULL eller ikke, fordi hvis verdien er NULL, betyr det at ordlisten ikke har noen verdier som inneholder bokstaven i det aktuelle rekkefølge. Hvis det er NULL, så det betyr at ordet er feilstavet med en gang. Men hvis det ikke er NULL, så du kan fortsette, si at første bokstaven er en mulig første bokstaven i et ord, så nå vil jeg sjekke om den andre bokstaven, den sekvensen, er innenfor min ordbok. Så du kommer til å gå til indeks over barn den første noden og sjekke om det andre brevet eksisterer. Så du gjenta denne prosessen for å sjekke om den sekvensen er gyldig eller ikke innenfor trie din. Når nodenavnene barn på den indekspoeng til NULL, du vet at sekvensen ikke eksisterer, men så hvis du kommer til slutten av ordet som du har lagt inn, så du ønsker å sjekke nå som jeg har fullført denne sekvensen og fant det innen trie min, er at ordet gyldig eller ikke? Og så så du ønsker å sjekke det, og det er da hvis du har funnet ut at sekvensen, så du ønsker å sjekke om det ordet er gyldig eller ikke fordi husker tilbake i forrige sak som jeg trakk der vi hadde FOOB, det var en gyldig sekvens som vi har funnet, men var ikke en faktisk gyldig ordet selv. 

Tilsvarende for losse i forsøk du vil lesse alle nodene i trie din. Unnskyld. I likhet med hash tabeller hvor i losse frigjøres vi alle nodene, i forsøk ønsker vi å frigjøre alle nodene. Losse faktisk vil fungere lettest fra bunn til topp fordi disse er i hovedsak knyttet lister. Så vi ønsker å sørge for at vi holder på til alle verdiene og fri alle av dem eksplisitt. Hva du kommer til å ønske å gjøre hvis du arbeider med en Trie er å reise til bunnen og gratis lavest mulig node første og deretter gå opp til alle disse barna og deretter gratis alle av dem, gå opp og deretter gratis, etc. Typen som arbeider med det nederste laget av Trie første og deretter gå opp toppen når du har frigjort alt. Dette er et godt eksempel på hvor rekursiv funksjon kan komme til nytte. Når du har frigjort botnlaget av trie din, så du kaller lesse på resten av det, å sørge for at du frigjøre hver mini - Du kan slags visualisere det som mini forsøk. Så har du ditt rot her. Jeg bare forenkle det så jeg ikke trenger å trekke 26 av dem. Så har du disse, og da disse representerer sekvenser av ord hvor alle disse små sirkler er bokstaver som er gyldige sekvenser av bokstaver. La oss fortsette bare litt mer. Hva du kommer til å ønske å gjøre er gratis bunnen her og deretter gratis denne og deretter gratis denne nederst før du frigjøre den øverste her oppe fordi hvis du gratis noe i det andre nivået her, da du faktisk ville miste denne verdien her. Det er derfor det er viktig i losse for en trie å sørge for at du frigjøre bunnen først. Hva kan det være lurt å gjøre er å si for hver node Jeg ønsker å losse alle barna. 

Nå som vi har gått over lesse for hash table metoden samt Trie metoden, vi kommer til å ønske å se på Valgrind. Du kjører Valgrind med følgende kommandoer. Du har Valgrind-v. Du sjekker for alle lekkasjer når du kjører stavekontroll gitt denne bestemt tekst fordi stavekontroll må ta i en tekstfil. Så Valgrind vil kjøre programmet, fortelle deg hvor mange bytes du tildelt, hvor mange byte du frigjort, og det vil fortelle deg om du frigjort akkurat nok eller om du ikke fri nok, eller noen ganger kan du selv over-free, som gratis en node som allerede er frigjort og slik vil det returnere deg feil. Hvis du bruker Valgrind, vil det gi deg noen meldinger angir om du har frigjort enten mindre enn nok, akkurat nok, eller mer enn nok ganger. 

En del av denne pset, er det valgfritt å utfordre The Big Board. Men når vi har å gjøre med disse datastrukturer det er like gøy å se hvor raskt og hvor effektiv din datastrukturer kunne være. Har din hash-funksjon resultat i en rekke kollisjoner? Eller er din data størrelsen virkelig store? Tar det mye tid å krysse? I loggen stavekontroll, utganger det hvor mye tid du bruker til å laste, å sjekke, gjennomføre størrelse, og å losse, og så de er lagt ut i The Big Board, hvor du kan konkurrere mot dine klassekamerater og noen stabsmedlemmer å se hvem som har den raskeste stavekontrollen. En ting som jeg ønsker å merke seg om hash tabeller er at det er noen ganske enkle hash funksjoner som vi kunne tenke på. For eksempel, har du 26 bøtter, og så hver bøtte tilsvarer første bokstav i et ord, men det kommer til å resultere i en ganske ubalansert hash table fordi det er en mye mindre ord som begynner med X enn start med M, for eksempel. En måte å gå om stavekontroll er hvis du ønsker å få alle de andre funksjonene ned, så bare bruke en enkel hash-funksjon for å kunne få koden kjører og deretter gå tilbake og endre størrelsen på hash table og definisjonen. Det er mange ressurser på Internett for hash funksjoner, og så for denne pset du har lov til å forske hash funksjoner på Internett for noen hint og inspirasjon, så lenge du sørge for å sitere hvor du fikk det fra. Du er velkommen til å se og tolke noen hash-funksjon som du finner på Internett. Tilbake til det, kan du kanskje å se om noen har brukt en trie om gjennomføringen er raskere enn din hash table eller ikke. Du kan sende til The Big Board flere ganger. Det vil ta den siste oppføringen. Så kanskje du endrer hash-funksjon, og deretter innse at det er faktisk mye raskere eller mye tregere enn før. Det er litt av en morsom måte. Det er alltid en eller to ansatte som prøver å gjøre den tregeste mulig ordbok, så det er alltid gøy å se på. 

Bruken for pset er du kjører stavekontroll med en valgfri ordbok og deretter en obligatorisk tekstfil. Som standard når du kjører stavekontroll med bare en tekstfil og ikke angir en ordbok, det kommer til å bruke ordboken tekstfil, den store i cs50/pset5/dictionaries mappen. At man har over 100.000 ord. De har også en liten ordliste som har betydelig mindre ord at CS50 har gjort for deg. Men kan du veldig enkelt bare lage din egen ordliste Hvis du bare ønsker å jobbe i små eksempler - for eksempel, hvis du ønsker å bruke gdb og du kjenner den spesifikke verdier som du vil at hash table å kartlegge ut til. Slik at du bare kan lage din egen tekstfil bare med BAR, BAZ, FOO, og Foobar, gjøre det i en tekstfil, skiller de hver med en linje, og deretter lage din egen tekstfil som bokstavelig talt bare inneholder kanskje 1 eller 2 ord slik at du vet nøyaktig hva resultatet skal være. Noen av prøven tekstfiler som The Big Board når du kjører utfordring vil sjekke er Krig og fred og en Jane Austen roman eller noe sånt. Så når du starter opp, er det mye lettere å lage dine egne tekstfiler som inneholder bare et par ord eller kanskje 10 slik at du kan forutsi hva utfallet bør være og deretter sjekke den mot det, så mer av en kontrollert eksempel. Og så siden vi har å gjøre med å forutsi og tegne ting rundt, igjen jeg vil oppfordre deg til å bruke penn og papir fordi det er virkelig kommer til å hjelpe deg med dette - tegne piler, hvordan hash tabellen eller hvordan trie ser ut, når du frigjør noe der pilene går, er du holder på å nok, ser du noen linker forsvinner og falle ned i avgrunnen av lekket minne. Så vær så snill, prøv å trekke ut ting selv før du kommer til å skrive kode ned. Tegne ting ut slik at du forstår hvordan ting kommer til å jobbe fordi da jeg garanterer at du vil støte på mindre pekeren FORVIRRENDE der. 

OK. Jeg vil ønske deg lykke til med dette pset. Det er trolig den vanskeligste. Så prøv å starte tidlig, tegne ting ut, tegne ting ut, og lykke til. Dette var Walkthrough 5. 

[CS50.TV]