[Powered by Google Translate] [Walk Through - Probleem Stel 5]
[Zamyla Chan - Harvard Universiteit]
[Hierdie is CS50. - CS50.TV]
>> Alles reg. Hallo, almal, en welkom by Walk Through 5.
>> Pset5 is spelfoute, wat ons sal wees om 'n speltoetser.
Speltoetsers is uiters belangrik.
Het dit ooit met jou gebeur?
Jy is baie werk, baie skat op 'n vraestel vir 'n botsing
en dan nog steeds eindig om 'n baie gloei rade soos 'n D of 'n D =
en omdat jy is die leverworst verwoester in die walvis-Wye Woord.
Ja, proeflees jou soetrissies is 'n saak van die uiterste impotensie.
Dit is 'n probleem wat manhaftig, manlike studente.
Ek was een keer vertel deur my sith graad folteraar dat ek nooit sou kry in 'n goeie kollega.
En dit is al wat ek ooit wou hê, dis al enige kind wil op my ouderdom,
net om te kry in 'n goeie kollega.
En nie net 'n kollega. Nee, ek wou om te gaan na 'n Ivory Legal kollega.
So as ek het nie te verbeter, sou gegaan my drome gaan na Harvard,
Jale, of Gevangenis - jy weet, in die gevangenis, New Jersey.
So ek het vir myself 'n speltoetser.
Dit is 'n klein uittreksel uit een van my gunsteling gesproke woord kunstenaars, Taylor Mali.
In elk geval, soos hy sê, die belangrikheid van 'n speltoetser is baie belangrik.
>> So welkom om Walk Through 5, waarin ons sal praat oor pset5: spelfoute,
wat ons sal wees om ons eie speltoetser.
Die toolbox vir hierdie week, die verspreiding kode, gaan belangrik wees om na te kyk
net die verskillende funksies wat jou woordeboek gaan hê om te verstaan.
Ons is eintlik gaan word met verskeie c lêers wat saam ons pset maak.
En so soek deur die verskillende aspekte, selfs al het ons eintlik is nie redigering
een van die lêers, speller.c, te weet hoe dit werk met betrekking tot dictionary.c,
wat ons sal skryf, gaan redelik belangrik.
Die pset spec bevat ook 'n baie nuttige inligting
in terme van die dinge wat jy kan aanneem, reëls en dinge soos wat,
so seker wees dat die pset spec sorgvuldig deur te lees vir wenke.
En toe in twyfel van 'n reël of iets soos dit, dan verwys altyd na die pset spec
of Bespreek.
Gaan Hierdie pset is swaar op pointers,
sodat ons wil hê om seker te maak dat ons verstaan ​​die verskil tussen die toevoeging van sterre
in die voorkant van die wyser se naam en-karakters, hoe om hulle te bevry, ens.
So 'n meester van wysers gaan wees baie nuttig in hierdie probleem stel.
Ons gaan kyk 'n bietjie meer in geskakelde lyste,
waar ons elemente wat ons noem nodes wat beide 'n waarde sowel as 'n wyser
aan die volgende node, en so in wese wat verskillende elemente een na die ander.
Daar is 'n paar verskillende opsies van die uitvoering van jou werklike woordeboek.
Ons gaan in twee hoof-metodes, wat hash tabelle en dan probeer om te kyk.
In beide van hulle, hulle betrek 'n soort van die idee van 'n geskakelde lys
waar jy elemente aan mekaar verbind.
En so gaan ons te kyk oor hoe jy dalk in staat wees om te bedryf rondom geskakelde lyste,
skep, opgevolg in terme van hoe om, byvoorbeeld, voeg 'n nodus in
of gratis al die nodes sowel.
In terme van bevry nodes, wat is regtig belangrik
dat wanneer ons daarna malloc geheue, is ons vry om dit.
Daarom wil ons maak seker dat geen wyser gaan unfreed, dat ons nie enige geheue lekkasies.
Ons gaan 'n hulpmiddel genaamd Valgrind wat jou program loop in te voer
en tjeks of al die geheue wat jy toegeken word dan vrygelaat.
Voltooi Jou pset word slegs wanneer dit werk en dit het volle funksionaliteit,
maar ook Valgrind jou vertel dat jy nie gevind het nie enige geheue lekkasies.
Ten slotte, vir hierdie pset, ek wil regtig om te beklemtoon -
Ek bedoel, soos gewoonlik, is ek beslis 'n ondersteuner van die gebruik van pen en papier vir jou probleem stelle,
maar vir hierdie een, ek dink dat pen en papier gaan wees veral belangrik
wanneer jy wil teken pyle om dinge te doen en te verstaan ​​hoe dinge werk.
So beslis probeer om pen en papier te gebruik om dinge uit te trek voordat jy kodering
want dit kan 'n bietjie slordig.
>> Eerstens, laat ons gaan 'n bietjie in geskakelde lyste.
Geskakelde lyste bestaan ​​van nodes, waar elke node het 'n waarde wat verband hou met dit,
sowel as 'n wyser na die volgende node nadat dit.
'N paar van die dinge wat belangrik is met die geskakelde lyste is wat ons nodig het om te onthou
waar ons eerste node is, en dan weer ons weet waar die eerste node is,
dié manier kan ons toegang tot die knoop wat die eerste nodus van punte te
en dan die een daarna en die een daarna.
En dan die laaste element in jou geskakelde lys is dat die node se wyser
is altyd gaan om te wys word VRYGEMAAK.
Wanneer 'n node punte aan nul is, dan weet jy dat jy die einde van die lys bereik het,
dat node is die laaste een, dat daar is niks daarna.
Hier in hierdie skematiese, sien jy dat die pyle is die wysers,
en die blou gedeelte is waar die waarde gestoor word,
en dan die rooi blokkie met die wyser na die node se wyser
verwys na die volgende node nadat dit.
En so sien jy hier, die D-node wys word VRYGEMAAK, want dit is die laaste element in die lys.
>> Kom ons kyk na hoe ons kan 'n struct definieer vir 'n knoop.
En omdat ons wil verskeie nodes te hê,
dit gaan om 'n typedef struct
wat ons gaan verskeie gevalle van nodes te hê.
En so het ons dit definieer as 'n nuwe datatipe.
Hier het ons 'n typedef struct node.
In hierdie voorbeeld, is ons te make met integer nodes,
so ons het 'n heelgetal genoem waarde en dan het ons nog 'n wyser,
en in hierdie geval, dit is 'n wyser na 'n node, so ons het 'n struct node * genoem volgende.
En dan het ons die roeping van hierdie hele ding node.
Maak seker dat u hierdie sintaksis.
Let daarop dat node is eintlik gekla bo sowel as onder die kode tussen krulhakies.
Dan om tred te hou van waar my eerste node is in hierdie geskakelde lys,
dan het ek 'n node pointer genoem kop, en ek malloc genoeg ruimte vir die grootte van 'n node.
Kennisgewing, egter, dat die kop is eintlik 'n node wyser as in teenstelling met 'n werklike node self.
So die kop eintlik nie enige waarde bevat,
Dit wys net na wat ookal die eerste node in my geskakelde lys is.
>> 'N beter begrip van geskakelde lyste te kry, want dit is baie belangrik
om tred te hou om seker te maak dat jy die ketting in stand te hou,
Ek hou daarvan om te dink aan dit as mense in 'n lyn hande vashou,
waar elke persoon hou hande met die volgende een.
Jy nie kan sien in hierdie tekening, maar basies het hulle verwys na die volgende persoon
wat in die ketting.
En so, as jy wil 'n geskakelde lys waar hierdie mense om oor te steek -
dink al die mense het waardes wat verband hou met hulle
en ook verwys na die volgende persoon in die lyn -
as jy wil die geskakelde lys te verken, byvoorbeeld, om óf die waardes wysig
of soek vir 'n waarde of iets soos dit,
dan moet jy 'n wyser na die spesifieke persoon te hê.
So ons gaan 'n data tipe node wyser te hê.
Vir hierdie geval, laat ons noem dit wyser.
Nog 'n algemene manier om dit te noem Iterator of iets soos dit sou wees
want dit is iterating oor en eintlik beweeg watter node dit verwys na.
Dit hier sal ons wyser wees.
Ons wyser sal eers verwys na die eerste element in ons lys.
En so wat ons wil doen, is ons sou basies die voortsetting van die wyser,
om dit van kant tot kant.
In hierdie geval, ons wil om dit te skuif na die volgende element in die lys.
Met skikkings, wat ons sou doen, is ons net sou sê dat ons die indeks verhoog deur 1.
In hierdie geval, is eintlik wat ons nodig het om te doen vind watter persoon die huidige persoon wys,
en wat gaan die volgende waarde wees.
So as wyser is net 'n node wyser, dan wat ons wil doen
is ons wil te kry om die waarde wat die wyser wys.
Ons wil te kry om daardie node en dan, sodra ons op daardie node, waar dit verwys na.
Te kry om die werklike node dat die wyser wys,
gewoonlik dui ons dit deur (* wyser).
Dit sou gee jou die werklike node dat die wyser wys.
En dan na dat, wat ons wil doen, is wat ons wil om toegang te verkry tot
wat dit ook al node se volgende waarde is.
Dit te doen, om toegang te verkry tot die waardes binnekant van die struct, ons het die dot-operateur.
So dan is dit sou wees (* wyser). Volgende.
Maar dit is 'n bietjie slordig in terme van die hakies om die * wyser,
en so het ons hierdie hele verklaring vervang met muis->.
Dit is 'n bietjie en dan 'n groter as teken, sodat die maak van 'n pyl.
muis-> Volgende.
Wat eintlik kry jy die knoop wat die wyser punte. Dat die waarde van die volgende is.
Dus, in plaas van met die ster en die dot jy die vervanging met 'n pyl.
Wees baie versigtig wees om seker te maak dat jy probeer om hierdie sintaksis te gebruik.
>> Nou dat ons ons wyser as ons wil hê om toegang te verkry tot die waarde,
voor, het ons wyser-> Volgende
maar die waarde op die knoop om toegang te verkry dat die wyser wys, het ons net net sê
node-> waarde.
Van daar, dit is van datatipe wat ons ook al die waardes en die nodes om te wees het gedefinieer.
As dit is 'n int node, dan muis-> waarde is net gaan om 'n heelgetal te wees.
Sodat ons bedrywighede kan doen, gaan gelijkheid, toewys verskillende waardes, ens.
So dan wat jy wil doen as jy jou muis om te beweeg na die volgende persoon,
jy eintlik die waarde van die wyser verander.
Sedert die wyser is 'n node pointer, jy verander die werklike pointer adres
aan die adres van die volgende node in jou lys.
Dit is net 'n paar Poskode waar jy kan itereer.
Waar ek die opmerking om iets te doen,
dis waar jy waarskynlik gaan om toegang te verkry tot die waarde
of doen iets om te doen met daardie spesifieke nodus.
Dit aan die gang, ek sê dat my wyser aanvanklik
gaan om te wys op die eerste element in die geskakelde lys.
En so wat voorlê, ek het dit gedefinieer as die hoof van die node.
>> Soos ek voorheen genoem, bevry is werklik belangrik is.
Jy wil om seker te maak dat jy bevry elke element in die lys sodra jy klaar is met dit.
As jy hoef nie enige van daardie wysers meer verwysing,
jy wil om seker te maak dat jy vry om al van daardie wysers.
Maar jy wil baie versigtig te wees hier in wat jy wil enige geheue lekkasies te voorkom.
As jy gratis een persoon vroeg, dan is al die wenke dat node punte
verlore gaan.
Terug te gaan na die persoon voorbeeld te maak dit 'n bietjie meer high stakes,
laat ons hierdie mense, behalwe in hierdie geval het hulle beweeg oor 'n dam met 'n monster.
Ons wil hê om seker te maak dat wanneer ons gratis, maar ons verloor nie
en laat gaan van enige nodes voordat ons het hulle eintlik bevry.
Byvoorbeeld, as jy was om te noem net gratis op hierdie man hier,
dan sou hy vrygelaat word, maar dan al hierdie ouens sal dan verlore wees
en hulle sou wegraak en val neer.
Sodat ons wil hê om seker te maak dat in plaas daarvan, ons wil 'n skakel na die res te handhaaf.
Ons hoof pointer, wat wys na die eerste element in die lys.
Dit is soort van soos 'n tou anker die eerste persoon.
Wat wil jy dalk om te doen wanneer jy vry is 'n lys het -
As jy wil hê dat die eerste element eerste vrye, dan kan jy 'n tydelike pointer
wat dui op alles wat die eerste element is.
Sodat jy jou tydelike wyser wys hier.
Op dié manier, ons het 'n houvas van die eerste nodus.
En dan, omdat ons weet dat die eerste nodus gaan word bevry,
dan kan ons hierdie tou, hierdie anker, ons hoof beweeg,
om werklik te wys wat die eerste een wys.
So is hierdie kop wys eintlik nou tot die tweede element.
Nou is ons toegelaat om te bevry wat gestoor word in temp,
en so kan ons vee sonder dat dit in gevaar stel al die ander nodusse in ons lys.
Nog 'n manier dat jy dit kan doen, kan
elke keer as jy net vry om die laaste element in die lys
want hulle is gewaarborg om nie gewys word tot niks.
Sodat jy kan net vry om hierdie een, dan vry om hierdie een, dan is gratis hierdie een.
Dit werk beslis, maar is 'n bietjie stadiger, want deur die aard van die geskakelde lyste,
ons kan net nie dadelik spring tot die laaste een.
Ons het elke element in die geskakelde lys te verken
en kyk of dat 'n mens verwys na VRYGEMAAK, so elke keer,
en dan wanneer ons aan die einde, dan is gratis dat.
As jy hierdie proses was om te doen, jy sou eintlik beheer word,
kontrolering hier, dan kontroleer hier, bevry dit,
dan weer terug, nagaan hier, nagaan hier, bevry dit,
nagaan, en dit dan bevry.
Dit neem 'n bietjie meer tyd. Ja.
>> [Student] Sou dit moontlik wees om 'n geskakelde lys te maak wat 'n afrit wyser aan die einde slaan?
Dit sou beslis moontlik wees nie.
Die vraag te herhaal, is dit moontlik 'n geskakelde lys struktuur te hê
van so 'n aard dat jy het 'n wyser wys aan die einde van die geskakelde lys?
Ek sou sê dit is moontlik, en elke keer wat jy plaas iets in jou geskakelde lys
wat jy wil hê dat die wyser en dinge soos wat te werk.
Jy sal 'n node * stert, byvoorbeeld.
Maar wanneer jy hierdie funksie is die uitvoering van, jy het om te dink van die trade-offs,
graag hoeveel keer gaan ek word iterating oor hierdie,
hoe moeilik dit gaan wees spoor van die stert te hou, sowel as die hoof
sowel as my Iterator, en dinge soos dat.
Beteken dit? >> [Student] Ja.
Dit is moontlik, maar in terme van ontwerp besluite te neem, moet jy die opsies op te weeg.
>> Hier is 'n geraamte van die kode wat sal toelaat dat jy elke element in 'n geskakelde lys te bevry.
Weereens, want ek is meer as 'n geskakelde lys iterating, ek gaan om te wil 'n soort van die muis te hê
of Iterator.
Ons is iterating totdat die wyser is NULL.
Jy nie wil hê om te itereer wanneer jou merker NULL
want dit beteken dat daar is nie iets wat in die lys.
So, hier is Ek maak 'n tydelike node *
verwys na wat ek oorweeg is die eerste van my lys,
en dan het ek my wyser beweeg voor 1 en dan vry alles wat ek gehad het in die tydelike stoor.
>> Nou kom ons by invoeging in geskakelde lyste.
Ek het drie nodes in my geskakelde lys, en laat ons saam met die eenvoudige geval
waar ons wil hê ander node te voeg aan die einde van ons geskakelde lys.
Dit te doen, alles wat ons wil doen, is om ons wil deurkruis
om uit te vind waar die einde van die geskakelde lys is, so ook al node wys word VRYGEMAAK -
wat is hierdie een -
en dan sê, eintlik, hierdie een is nie van plan om die laaste nodus wees;
ons eintlik gaan 'n ander een te hê.
So sou ons die huidige een punt wat ons die invoeging.
So nou die rooi persoon word hier die laaste nodus in die geskakelde lys.
En so het die kenmerk van die laaste nodus in die geskakelde lys is dat dit dui op VRYGEMAAK.
So dan wat ons wil hê om dit te doen, is stel die rooi man se wyser word VRYGEMAAK. Daar.
>> Maar wat as ons wou 'n node in tussen die tweede en derde een te voeg?
Dat 'n mens nie heeltemal so eenvoudig nie, want ons wil om seker te maak
wat ons laat gaan nie van enige node in ons geskakelde lys.
Wat ons wil hê om dit te doen, is om seker te maak dat ons onsself anker aan elke een.
Byvoorbeeld, kom ons noem dit die tweede een.
As jy sê die tweede een wys nou na die nuwe een
en jy het net 'n wyser gemaak het, wat tot gevolg sal hê in hierdie man verlore
want daar is nie 'n skakel na hom.
In plaas daarvan - ek sal trek dit weer. Verskoon my artistieke vermoëns.
Ons weet dat ons net kan nie direk koppel 2 na die nuwe een.
Ons het om seker te maak dat ons hou op die laaste een.
Wat ons wil doen is om 'n tydelike pointer
die element wat gaan word aangeheg.
So dan het ons 'n tydelike wyser daar.
Omdat ons weet dat hierdie derde een is die baan gehou word,
2 kan nou 'n skakel na ons nuwe een.
En as hierdie nuwe rooi man is gaan om te wees in tussen 2 en 3,
wat dan daardie man se wyser gaan om aan te dui? >> [Student] Temp.
Temp. Ja.
So dan die rooi man se waarde gaan wees temp.
Wanneer jy die invoeging in geskakelde lyste, sien ons dat ons kon
maklik iets byvoeg tot die einde deur die skep van 'n tydelike skikking,
of as ons wou iets by te voeg in die middel van ons verskeidenheid,
dan sou dit 'n bietjie meer skuifel rond.
As jy wil, byvoorbeeld, het 'n gesorteerde geskakelde lys,
dan moet jy soort van weeg die koste en voordele van daardie
want as jy wil 'n gesorteerde skikking te hê, beteken dit dat elke keer wat jy plaas in dit,
dit gaan om 'n bietjie meer tyd te neem.
Maar, as jy wil later op, soos ons sal vind sal ons wil,
soektog deur 'n geskakelde lys, dan is dit dalk makliker wees as jy weet dat alles in orde is.
Sodat jy dalk wil om te weeg die koste en voordele van daardie.
>> Nog 'n manier om in te voeg in 'n geskakelde lys is in die begin van 'n lys te voeg.
As ons ons anker trek hier - dit is ons hoof -
en dan het hierdie mense wat daaraan gekoppel is,
en dan het ons 'n nuwe node ingevoeg word in die begin,
dan wat sou ons wil om dit te doen?
Wat sou verkeerd wees met net sê: Ek wil die rooi om te skakel na die blou,
want dit is die eerste een?
Wat sou hier gebeur?
Al van hierdie drie sou verlore raak.
Sodat ons nie wil hê om dit te doen.
Weer, het ons geleer dat ons moet 'n soort van tydelike wyser te hê.
Kom ons kies 'n tydelike punt aan hierdie man te hê.
Dan kan ons die blou een punt na die tydelike
en dan die rooi punt na die blou.
Die rede waarom ek gebruik mense hier is omdat ons regtig wil om te visualiseer
vashou aan mense en om seker te maak dat ons 'n skakel na hulle
voordat ons laat gaan van 'n ander hand of iets soos dit.
>> Nou dat ons 'n gevoel van geskakelde lyste - hoe ons kan skep 'n geskakelde lys
en die skep van die strukture wat bestaan ​​uit die tipe definisie vir 'n node
en dan om seker te maak dat ons 'n wyser na die hoof van die geskakelde lys -
wanneer ons dit en ons weet hoe om te deurkruis deur middel van 'n skikking,
toegang tot verskillende elemente, ons weet hoe om te voeg en ons weet hoe om hulle te bevry,
dan kan ons in spelfoute.
Soos gewoonlik het ons 'n afdeling van vrae wat sal jy gebruik om te werk met geskakelde lyste
en verskillende strukture soos toue en stapels.
Dan kan ons beweeg in spelfoute.
>> Spelfouten het in die verspreiding-kode 'n paar van die lêers van belang.
Eerste keer wat ons opmerk dat ons hierdie makefile hier,
wat ons regtig nie vantevore teengekom.
As jy kyk binne die pset5 gids, sal jy agterkom dat jy 'n h-lêer.
dan moet jy twee c lêers.
Wat hierdie makefile doen is voor, ons sou net tik maak en dan die program se naam
en dan sal ons sien al hierdie argumente en vlae geslaag het in die vertaler.
Wat die makefile doen, is stel ons in staat om verskeie lêers in 'n keer op te stel
en slaag in die vlae wat ons wil hê.
Hier het ons net sien daar is 'n header-lêer hier.
Dan het ons eintlik twee bronkodelêers.
Ons het speller.c en dictionary.c.
Jy is welkom om die makefile te wysig as jy wil.
Let op dat hier as jy tik skoon is, dan is wat dit doen nie eintlik iets verwyder
wat is die kern.
As jy 'n segmentering skuld, basies jy 'n kern dump.
So sal hierdie lelike klein lêer verskyn in jou gids genoem kern.
Jy sal wil hê om te verwyder dat dit skoon te maak.
Dit verwyder enige exe lêers en o lêers.
>> Kom ons neem 'n blik in dictionary.h.
Dit sê dat dit 'n woordeboek se funksionaliteit verklaar.
Ons het 'n maksimum lengte vir 'n woord in die woordeboek.
Ons sê dat dit gaan om die langste moontlike woord wees. Dit is van lengte 45.
So gaan ons nie enige woorde wat oorskry lengte te hê.
Hier het ons net die funksie prototipes.
Ons het nie die werklike implementering, want dit is wat ons sal moet doen vir hierdie pset.
Maar wat dit doen omdat ons te doen het met groter lêers hier
en funksionaliteit op 'n groter skaal, is dit nuttig om 'n H-lêer te hê
sodat iemand anders te lees of te gebruik om jou kode kan verstaan ​​wat aangaan.
En miskien is hulle wil om te implementeer, probeer as jy gedoen het hash tabelle of vice versa.
Dan sal hulle sê my vrag funksie,
die werklike implementering gaan verskil, maar hierdie prototipe sal nie verander nie.
Hier het ons gaan, wat terugkeer waar as 'n gegewe woord in die woordeboek.
Dan het ons 'n las, wat basies neem in 'n woordeboek lêer
en laai dan is dit in sommige data struktuur.
Ons het grootte, wat, toe hy geroep is, gee die grootte van jou woordeboek,
Hoeveel woorde is gestoor in dit,
en dan los, wat bevry al die geheue wat jy geneem het
terwyl die maak van jou woordeboek.
>> Kom ons neem 'n blik op dictionary.c.
Ons sien dat dit lyk baie soortgelyk na dictionary.h, behalwe nou is dit net het al van hierdie Todos.
En so het dit is jou werk. Uiteindelik, sal jy vul word speller.c met al van hierdie kode.
Dictionary.c, toe loop, is regtig nie van plan om iets te doen,
so ons kyk na speller.c die werklike implementering van die speltoetser te sien.
Selfs al is jy nie van plan om die wysiging van enige van hierdie kode,
dit is belangrik om te lees, verstaan ​​wanneer vrag genoem, wanneer Ek roep tjek,
net om te verstaan, kaart dit uit, sien hoe die funksie werk.
Sien ons dat dit kontroleer vir die korrekte gebruik.
Wese, wanneer iemand loop speller, dit dui daarop dat dit is opsioneel
vir hulle om te slaag in 'n woordeboek lêer, want daar gaan 'n standaard woordeboek lêer.
En dan sal hulle het om te slaag in die teks te wees spelling nagegaan.
rusage handel met die verloop van tyd, omdat 'n deel van hierdie pset wat ons sal hanteer later
is nie net om 'n funksionerende speltoetser werk
maar eintlik om dit te vinnig.
En so dan is dit waar rusage gaan kom.
Hier, sien ons die eerste oproep na een van ons dictionary.c lêers wat vrag.
Load terugkeer waar of onwaar is - waar op sukses, valse op mislukking.
So as die woordeboek is nie gelaai, dan sal die speller.c terug 1 en stop.
Maar as dit nie vrag behoorlik, dan is dit gaan om voort te gaan.
Ons gaan voort, en ons sien 'n paar lêer I / O hier,
waar dit gaan om te word wat met die opening van die tekslêer.
Hier, wat dit doen spell-kontrole elke enkele woord in die teks.
So, wat speller.c is reg hier is iterating oor elk van die woorde in die tekslêer
en dan kyk hulle in die woordeboek.
Hier het ons 'n Boolese verkeerd gespelde wat sal sien as die tjek terug waar is of nie.
As die woord is eintlik in die woordeboek, kyk dan waar sal terugkeer.
Dit beteken dat die woord nie verkeerd gespel.
So verkeerd gespel sou vals wees, en dit is hoekom ons die bang is, is die aanduiding.
Ons hou op gaan, en dan is dit hou van hoe baie verkeerd gespelde woorde
daar is in die lêer.
Dit gaan voort op en sluit die lêer.
Dan is hier, is dit verslae hoe baie verkeerd gespelde woorde jy het.
Dit bereken hoe lank dit geneem het om die woordeboek te laai,
hoe lank dit geneem het om dit te sien,
hoeveel tyd wat dit neem om die grootte te bereken,
wat, as ons gaan op baie klein moet wees,
en dan hoe lank dit geneem het om die woordeboek af te laai.
Hier bo sien ons die oproep om hier te los.
As ons kyk vir die grootte,
dan sien ons dat hier is die oproep tot grootte waar dit bepaal die grootte van die woordeboek.
Awesome.
>> Ons taak vir hierdie pset is om vrag te implementeer, wat die woordeboek sal laai
data struktuur - wat ook al jy kies, is dit 'n hash tafel of 'n probeer -
met die woorde uit die woordeboek lêer.
Dan moet jy 'n grootte, wat sal die aantal woorde in die woordeboek terugkeer.
En as jy vrag in 'n slim manier te implementeer, dan grootte moet wees redelik maklik.
Dan het jy gaan, wat sal kyk of 'n gegewe woord in die woordeboek.
So speller.c slaag in 'n tou, en dan moet jy of daardie string om seker te maak
is vervat in jou woordeboek.
Let daarop dat ons oor die algemeen standaard woordeboeke,
maar in hierdie pset, basies enige woordeboek in enige taal geslaag het.
Sodat ons kan nie net aanvaar dat die woord van die binnekant.
Die woord Foobar kan gedefinieer word in 'n bepaalde woordeboek dat ons slaag.
En dan het ons los, wat bevry die woordeboek uit die geheue.
>> Eerste, wil ek graag om te gaan oor die hash tafel metode
oor hoe ons kan al die vier funksies te implementeer,
en dan sal ek gaan oor die probeer metode, hoe ons die vier funksies te implementeer,
en aan die einde praat oor 'n paar algemene wenke wanneer jy die pset
en ook hoe jy dalk in staat wees om te gebruik Valgrind vir die geheue lekkasies na te gaan.
>> Kom ons kry in die hash tafel metode.
'N hash tafel bestaan ​​uit 'n lys van emmers.
Elke waarde, elke woord, gaan om te gaan in een van hierdie emmers.
'N hash tafel versprei ideaal eweredig al hierdie waardes dat jy verby in
en vult hulle dan in die emmer sodanig dat elke emmer
het ongeveer 'n gelyke aantal waardes in.
Die struktuur vir 'n hash tafel, het ons 'n verskeidenheid van geskakelde lyste.
Wat doen ons wanneer ons in 'n waarde, gaan ons waar daardie waarde moet behoort,
watter emmer dit behoort aan, en plaas dit dan in die geskakelde lys wat verband hou met daardie emmer.
Hier, wat ek het is 'n hash funksie.
Dit is 'n int hash tafel.
So vir die eerste emmer, enige heelgetalle onder 10 gaan in die eerste emmer.
Enige heelgetalle bo 10 maar onder 20 gaan in die tweede,
en dan so aan en so voort.
Vir my, is elke emmer hierdie getalle verteenwoordig.
, Sê egter ek was in 50 te slaag, byvoorbeeld.
Dit wil voorkom asof die eerste drie bevat 'n reeks van tien nommers.
Maar ek wil toelaat dat my hash tafel te neem in 'n soort van heelgetalle,
so dan sou ek al die getalle bo 30 in die laaste emmer uit te filter.
En so is daar dan wat sal lei tot 'n soort van 'n ongebalanseerde hash tafel.
Te herhaal, 'n hash tafel is net 'n verskeidenheid van emmers
waar elke emmer is 'n geskakelde lys.
En so om te bepaal waar elke waarde gaan, welke emmer gaan dit in,
jy gaan om te wil hê wat 'n hash funksie genoem
wat nie 'n waarde en dan sê hierdie waarde stem ooreen met 'n sekere emmer.
So bo in hierdie voorbeeld, my hash funksie het elke waarde.
Dit nagegaan of dit was minder as 10.
As dit was, sou dit sit dit in die eerste emmer.
Dit kontroleer of dit is minder as 20, plaas dit in die tweede as dit waar is,
tjeks as dit is minder as 30, en dan sit dit in die derde emmer,
en dan alles val net om die vierde emmer.
So as jy 'n waarde, jou hash funksie
sal daardie waarde plaas in die toepaslike emmer.
Die hash funksie moet basies te weet hoeveel emmers jy het.
Jou hash tafel grootte, die aantal van emmers wat jy het,
dit gaan 'n vaste getal wat is aan jou, vir jou om te besluit,
maar dit gaan om 'n vaste getal wees.
Sodat jou hash funksie sal vertrou op dit om te bepaal watter emmer elke sleutel gaan in
van so 'n aard dat dit eweredig versprei.
Soortgelyk aan die implementering van geskakelde lyste, nou elke node in die hash tafel
is eintlik 'n tipe char te hê.
Sodat ons 'n char skikking met die naam woord en dan nog 'n wyser na die volgende node,
wat sin maak, want dit gaan om 'n geskakelde lys.
Onthou toe ons geskakelde lyste, ek het 'n node * genoem kop
wat verwys na die eerste nodus in die geskakelde lys.
Maar vir ons hash tafel, want ons het verskeie geskakelde lyste,
Wat ons wil hê, is dat ons wil ons hash tafel te wees soos, "Wat is 'n emmer?"
'N emmer is net 'n lys van node pointers,
en so elke element in die emmer is eintlik verwys na die ooreenstemmende geskakelde lys.
Om terug te gaan na hierdie skematiese, sien jy dat die emmers self is die pyle,
nie die werklike nodes.
Een van die noodsaaklike eiendom van hash funksies is dat hulle deterministiese.
Dit beteken dat wanneer jy hash die nommer 2,
dit moet altyd dieselfde emmer terug.
Elke enkele waarde wat gaan in die hash funksie, as dit herhaal word,
het dieselfde indeks te kry.
Sodat jou hash funksie gee die indeks van die skikking
waar daardie waarde behoort.
Soos ek voorheen genoem, is die getal van die emmers vas,
en so jou indeks wat jy terugkeer het minder wees as die getal van emmers
maar groter as 0.
Die rede waarom ons het hash funksies in plaas van slegs 'n enkele geskakelde lys
of een array is wat ons wil in staat wees om te spring na 'n sekere afdeling die maklikste
as ons weet wat die eienskap van 'n waarde -
in plaas van om te soek deur die hele hele woordeboek,
in staat is om te spring na 'n sekere deel van dit.
Jou hash funksie moet in ag neem dat ideaal,
elke emmer het ongeveer dieselfde aantal sleutels.
Sedert die hash tafel is 'n reeks van geskakelde lyste,
dan is die geskakelde lyste self gaan om meer as een node te hê.
In die vorige voorbeeld, twee verskillende nommers, selfs al is hulle nie gelyke,
wanneer hashed, sou terugkeer dieselfde indeks.
So wanneer jy te doen het met woorde, een woord wanneer hashed
dieselfde hash waarde as 'n ander woord sou wees.
Dit is wat ons noem 'n botsing, wanneer ons 'n node dat, wanneer hashed,
die geskakelde lys op daardie emmer is nie leeg nie.
Die tegniek wat ons noem daar is lineêre ondersoekende,
waar jy gaan in die geskakelde lys en dan vind waar jy wil te voeg dat die node
want jy het 'n botsing.
Jy kan sien dat daar dalk 'n trade-off hier te wees, reg?
As jy 'n baie klein hash tafel, 'n baie klein aantal van emmers,
dan is jy gaan 'n baie botsings te hê.
Maar dan as jy 'n baie groot hash tafel,
is jy waarskynlik gaan om die botsings te verminder,
maar dit gaan 'n baie groot data struktuur wees.
Daar gaan trade-offs met.
So wanneer jy jou pset jy maak, probeer om te speel
tussen miskien om 'n kleiner hash tafel
maar dan die wete dat dit gaan om 'n bietjie langer neem om die verskillende elemente te verken
van hierdie geskakelde lyste.
>> Watter lading gaan doen is itereer oor elke woord in die woordeboek.
Dit gaan in 'n wyser na die woordeboek-lêer.
So jy gaan om voordeel te trek van die lêer I / O-funksies wat jy bemeester pset4
en itereer oor elke woord in die woordeboek.
Jy wil elke woord in die woordeboek na 'n nuwe node word,
en jy gaan elke een van daardie nodes te plaas binnekant van jou woordeboek datastruktuur.
Wanneer jy 'n nuwe woord, jy weet dat dit gaan om 'n nodus.
Sodat jy kan dadelik gaan en malloc 'n node wyser vir elke nuwe woord wat jy het.
Hier is ek roep my node pointer new_node en ek mallocing wat? Die grootte van 'n node.
Toe het die werklike string uit 'n lêer te lees, omdat die woordeboek is eintlik gestoor
deur 'n woord, en dan 'n nuwe lyn, wat ons kan neem voordeel van
is die funksie fscanf,
waardeur lêer is die woordeboek leer dat ons geslaag het in,
sodat dit skanderings die lêer vir 'n string en plekke wat die string in die laaste argument.
As jy onthou terug na een van die lesings, toe het ons oor
en soort van geskilde die lae terug op die CS50 biblioteek,
ons het 'n implementering van fscanf daar.
Om terug te gaan na fscanf, ons het die lêer dat ons lees van,
ons is op soek vir 'n string in die lêer, en dan is ons plaas dit in
Ek het hier new_node-> woord omdat new_node is 'n node pointer,
nie 'n werklike node.
So dan moet ek sê new_node, ek wil om te gaan na die node dat dit verwys na
en dan wys dat die waarde te woord.
Ons wil dan daardie woord en plaas dit in die hash tafel.
Besef dat ons new_node 'n node pointer
want ons gaan om te wil weet wat die adres van daardie node is
wanneer ons plaas dit in omdat die struktuur van die nodes self, van die struct,
is dat hulle 'n wyser na 'n nuwe node.
So wat is dan die adres van daardie node gaan om aan te dui?
Dat die adres gaan wees new_node.
Beteken dit sin maak, hoekom maak ons ​​'n nodus * new_node in teenstelling met 'n nodus?
Okay.
Ons het 'n woord. Dat die waarde is new_node-> woord.
Dit bevat 'n woord uit die woordeboek wat ons wil invoer.
So, wat ons wil doen, is ons wil ons hash funksie aan te roep op daardie string
omdat ons hash funksie neem in 'n tou en dan terug keer ons 'n heelgetal,
waar daardie heelgetal is die indeks waar hashtable op daardie indeks verteenwoordig die emmer.
Ons wil hê dat die indeks te neem en dan gaan na die indeks van die hash tafel
en gebruik dan daardie geskakelde lys om die knoop te voeg by new_node.
Onthou dat jy egter besluit om jou node te voeg,
of dit nou in die middel as jy dit wil hê om te sorteer
of aan die begin of aan die einde, maar maak seker dat jou laaste node altyd na VRYGEMAAK
want dit is die enigste manier waarop ons weet waar die laaste element van ons geskakelde lys is.
>> Indien die grootte is 'n heelgetal wat verteenwoordig die aantal woorde in 'n woordeboek,
dan is een manier om dit te doen, is dat wanneer grootte genoem word
ons gaan deur elke element in ons hash tafel
en dan itereer deur elke geskakelde lys in die hash tafel
en bereken dan die lengte van die verhoging van ons counter 1 deur 1.
Maar elke keer dat die grootte genoem word, wat gaan 'n lang tyd te neem
want ons gaan lineêr indringende elke enkele geskakelde lys.
In plaas daarvan, gaan dit 'n baie makliker wees as jy hou van hoeveel woorde geslaag.
Daarom dan, as jy 'n toonbank binne jou vrag funksie
dat updates as wat nodig is, dan is counter, as jy dit aan 'n globale veranderlike,
sal kan verkry word deur die grootte.
So watter grootte kan eenvoudig doen, is in een lyn, net die toonbank waarde terug,
die grootte van die woordeboek, wat jy reeds in die vrag hanteer.
Dit is wat ek bedoel het toe ek gesê het as jy implementeer las op 'n nuttige manier,
dan grootte gaan redelik maklik te wees.
>> So nou het ons kry om te kyk.
Nou het ons te doen het met woorde uit die insette teks lêer,
en so ons gaan om te kontroleer of al van daardie inset woorde
is eintlik in die woordeboek of nie.
Soortgelyk aan Scramble, ons wil om voorsiening te maak vir die geval onsensitiwiteit.
Jy wil om seker te maak dat al die woorde geslaag, selfs al het hulle is gemengde geval,
wanneer dit met 'n tou vergelyk genoem word, is ekwivalent.
Die woorde in die woordeboek teks lêers is eintlik alle kleinletters.
Nog 'n ding is dat jy kan aanneem dat elke woord in elke string geslaag het,
gaan wees óf alfabetiese of bevat apostrofes.
Apostrofs gaan om geldig te wees woorde in ons woordeboek.
So as jy 'n woord met afkappingsteken S, dit is 'n werklike wettige woord in jou woordeboek
wat gaan om te wees een van die nodusse in jou hash tafel.
Maak seker as die woord bestaan, dan is dit het om te wees in ons hash tafel.
As die woord in die woordeboek is nie, dan is al die woorde in die woordeboek is in die hash tafel,
so laat ons kyk vir hierdie woord in die hash tafel.
Ons weet dat, aangesien ons ons hash funksie geïmplementeer
van so 'n aard dat elke unieke woord is altyd aan die dieselfde waarde hashed,
dan weet ons dat in plaas van soek deur ons hele hele hash tafel,
ons kan eintlik die geskakelde lys vind dat woord hoort.
As dit in die woordeboek was, dan sou dit in die emmer.
Wat ons kan doen, as die woord is die naam van ons string geslaag,
Ons kan nie net hash dat woord en kyk na die geskakelde lys
op die waarde van hashtable [hash (woord)].
Van daar is, wat ons kan doen, is ons het 'n klein subset van die nodes om te soek vir hierdie woord,
en so kan ons die geskakelde lys deurkruis, met behulp van 'n voorbeeld van vroeër in die instruksies,
en dan bel string vergelyk op die woord waar die wyser wys,
dat die woord, en kyk of daardie vergelyk.
Afhangende van die manier waarop jy organiseer jou hash funksie,
as dit gesorteer is, kan jy in staat wees om valse 'n bietjie vroeër terugkeer,
maar as dit ongesorteerde, dan kan jy wil om voort te gaan kameelkoei deur jou geskakelde lys
totdat jy die laaste element van die lys.
En as jy nog nie gevind nie die woord deur die tyd wat jy aan die einde van die geskakelde lys,
wat beteken dat jou woord bestaan ​​nie in die woordeboek,
en so dat die woord is ongeldig,
en die tjek moet terugkeer vals.
>> Nou kom ons by los, waar ons wil al die nodes dat ons malloc'd te bevry,
so vry al die nodes binnekant van ons hash tafel.
Ons gaan om te wil itereer oor die hele van die geskakelde lyste en vry al die nodes in daardie.
As jy kyk in die instruksies hierbo na die voorbeeld waar ons vry 'n geskakelde lys,
dan sal jy wil om die proses te herhaal vir elke element in die hash tafel.
En ek gaan oor na die einde van die walkthrough,
maar Valgrind is 'n hulpmiddel waar jy kan sien as jy behoorlik bevry
elke node wat jy malloc'd of enigiets anders wat jy malloc'd, enige ander wyser.
So dit is hash tabelle, waar ons 'n eindige aantal emmers
en 'n hash funksie wat 'n waarde sal neem en dan wys dat waarde tot 'n sekere emmer.
>> Nou kom ons by drieë.
Probeer om 'n soort van kyk soos hierdie, en ek sal ook 'n voorbeeld.
Basies, jy het 'n hele verskeidenheid van potensiële letters,
en dan wanneer jy die bou van 'n woord,
daardie brief gekoppel kan word vir 'n woordeboek na 'n wye verskeidenheid van moontlikhede.
Sommige woorde begin met C, maar gaan dan voort met 'n,
maar ander gaan voort met O, byvoorbeeld.
'N Trie is 'n manier van die visualisering van al die moontlike kombinasies van daardie woorde.
'N Trie gaan om tred te hou van die volgorde van letters wat uit woorde,
vertakking wanneer dit nodig is, wanneer een letter kan gevolg word deur 'n veelvoud van briewe,
en aan die einde dui by elke punt of daardie woord geldig is of nie
want as jy die spelling van die woord MAT, MA Ek dink nie 'n geldige woord, maar MAT is.
En so in jou Trie, sou dit aandui dat na MAT wat eintlik 'n geldige woord.
Elke node in ons Trie is eintlik van plan om 'n verskeidenheid van node verwysings te bevat,
en ons gaan te hê, spesifiek, 27 van daardie node pointers,
een vir elke letter in die alfabet, asook die Apostrof.
Elke element in die skikking self gaan om te wys na 'n ander node.
So indien daardie node is NULL, indien daar is niks daarna,
dan weet ons dat daar is geen verdere letters in die woord volgorde.
Maar as daardie node nie NULL is nie, wat beteken dat daar meer briewe in daardie brief ry.
En dan verder, moet elke node dui aan of dit is die laaste karakter van 'n woord of nie.
>> Kom ons gaan na 'n voorbeeld van 'n Trie.
Ek het eers ruimte vir 27 nodusse in die skikking.
As ek die woord BAR -
As ek die woord bar en ek wil hê dat te voeg,
die eerste letter B, so as my Trie is leeg,
B is die tweede letter van die alfabet, so ek gaan om te kies om dit hier te plaas op hierdie indeks.
Ek gaan B hier te hê.
B gaan na 'n node wat wys na 'n ander verskeidenheid van al die moontlike karakters te wees
wat kan volg na die letter B.
In hierdie geval, ek handel met die woord bar, so 'n kom hier.
Na 'n, ek het die letter R, so dan 'n nou punte op sy eie kombinasie,
en dan R hier sal wees.
BAR is 'n volledige woord, so dan sal ek gaan R punt na 'n ander node
wat sê dat woord is geldig.
Dat node is ook van plan om 'n verskeidenheid van nodes te hê,
maar diegene sou wees NULL.
Maar basies, dit kan voortgaan soos dit.
Dit sal 'n bietjie meer duidelik wanneer ons na 'n ander voorbeeld,
so met my dra.
Nou het ons BAR binnekant van ons woordeboek.
Nou sê ons het die woord BAZ.
Ons begin met B, en ons het reeds B as een van die briewe wat in ons woordeboek is.
Dit is gevolg met A. Ons het 'n reeds.
Maar dan plaas daarvan, ons het Z volgende.
So is daar dan 'n element in die skikking gaan wees Z,
en so dan dat 'n mens gaan om te wys na 'n ander geldige einde van die woord.
So sien ons dat wanneer ons voortgaan om deur B en dan 'n
daar is twee verskillende opsies vir die woorde wat tans in ons woordeboek wat begin met B en A.
Sê dat ons wou die woord te voeg Foobar.
Dan sou ons 'n inskrywing maak by F.
F is 'n nodus wat dui op 'n hele reeks.
Ons O sou vind, gaan na O, O skakel dan na 'n hele lys.
Ons B wil hê en gaan dan voort, het ons het 'n en dan R.
So dan Foobar deurkruis al die pad af tot Foobar is 'n korrekte woord.
En so dan is dit 'n geldige woord sou wees.
Nou sê ons volgende woord in die woordeboek is die woord FOO.
Ons sou sê F. Wat volg F?
Ek het eintlik reeds 'n ruimte vir O, so ek gaan om voort te gaan.
Ek hoef nie 'n nuwe een te maak. Voort te gaan.
FOO is 'n geldige woord in hierdie woordeboek is, so dan gaan ek om aan te dui
dat dit geldig is.
As ek stop my ry daar, sou dit korrek wees.
Maar as ons het voortgegaan om ons volgorde van ANDY C na B
en moes net FOOB FOOB is nie 'n woord, en dit is nie aangedui as 'n geldige een.
In 'n Trie, het jy elke node wat aandui of dit is 'n geldige woord of nie,
en dan is elke node het ook 'n verskeidenheid van 27 node pointers
wat dan punt nodes hulself.
>> Hier is 'n manier van hoe jy dalk wil om dit te definieer.
Egter, net soos in die hash tafel voorbeeld, waar ons 'n node * Hoof
die begin van die geskakelde lys om aan te dui, is ons ook gaan om te wil
een of ander manier om te weet waar die begin van ons Trie is.
Sommige mense noem probeer bome, en dit is waar die wortel kom uit.
So wil ons die wortel van ons boom om seker te maak dat ons bly gegrond
te waar ons Trie is.
Ons het reeds soort van het oor
die manier waarop jy kon dink oor die laai van elke woord in die woordeboek.
Wese, vir elke woord wat jy gaan om te wil om te itereer deur jou Trie
en die wete dat elke element in die kinders - ons noem dit kinders in hierdie geval -
ooreenstem met 'n ander brief, jy gaan wil om daardie waardes na te gaan
op daardie betrokke indeks wat ooreenstem met die brief.
So dink al die pad terug na die keiser en Vigenere,
die wete dat elke brief wat jy kan soort kaart terug na 'n alfabetiese indeks,
beslis 'n deur Z gaan redelik maklik te wees om te karteer 'n alfabetiese letter,
maar ongelukkig apostrofes is ook 'n aanvaarde karakter in woorde.
Ek is nie eens seker wat die ASCII-waarde is,
so dat as jy wil om 'n indeks te vind om te besluit of jy dit wil hê om die eerste een te wees
of die laaste een, het jy 'n harde gekodeerde tjek vir daardie te maak
en dan sit dit in die indeks 26, byvoorbeeld.
So is julle dan die beheer van die waarde op kinders [i]
waar [i] ooreenstem met watter letter jy.
As dit is NULL, wat beteken dat daar nie tans enige moontlike letters
die gevolg is van daardie vorige volgorde, so jy gaan wil malloc
en maak 'n nuwe node en dat kinders [i] punt om dit te
, sodat jy - wanneer ons 'n brief in die reghoek plaas -
die maak van kinders nie-nul en punt in dat die nuwe node.
Maar as dit nie NULL is nie, soos in ons geval van FOO
wanneer ons reeds Foobar, gaan ons voort,
en ons is nooit die maak van 'n nuwe node, maar eerder net die opstel is_word na ware
aan die einde van daardie woord.
>> So dan as voorheen, want hier het jy te doen het met elke brief op 'n tyd,
dit gaan makliker wees vir jou grootte, in plaas van om te bereken
en gaan deur die hele boom en bereken hoeveel kinders het ek
en dan vertakking, onthou hoeveel is aan die linkerkant en aan die regterkant
en dinge soos wat, gaan dit 'n baie makliker vir jou
as jy net hou van hoeveel woorde wat jy wil byvoeg in
wanneer jy te doen het met vrag.
En so is daar dan dié manier grootte kan net 'n globale veranderlike grootte terug.
>> Nou kom ons te kontroleer.
Dieselfde standaarde as voorheen, waar ons wil om voorsiening te maak vir die geval onsensitiwiteit.
So goed, ons aanvaar dat die snare is slegs alfabetiese karakters of die apostrofes
omdat kinders is 'n verskeidenheid van 27 lank,
so al die letters van die alfabet, plus die afkappingsteken.
Vir check wat jy wil doen, is wat jy sal wil begin by die wortel
omdat die wortel sal verwys na 'n verskeidenheid wat die volgende bevat
al die moontlike begin letters van 'n woord.
Jy gaan om daar te begin,
en dan moet jy gaan om te kyk, is hierdie waarde NULL of nie,
want as die waarde is NULL, wat beteken dat die woordeboek nie enige waardes
wat bevat dat die brief in daardie spesifieke volgorde.
As dit is NULL, dan beteken dit dat die woord dadelik verkeerd gespel.
Maar as dit is nie NULL, dan kan jy voortgaan,
sê dat die eerste brief is 'n moontlike eerste letter in 'n woord,
maar nou is ek wil om te kyk of die tweede brief, daardie volgorde, is binne-in my woordeboek.
So jy gaan om te gaan na die indeks van die kinders van die eerste node
en kyk of daardie tweede brief bestaan.
Dan moet jy die proses herhaal om te kontroleer of daardie volgorde geldig is of nie
binne jou Trie.
Wanneer die node kinders op daardie indekspunte null,
jy weet dat daardie volgorde nie bestaan ​​nie,
maar dan as jy aan die einde van die woord wat jy ingetik het,
dan moet jy nou wil seker dat ek hierdie reeks voltooi het
en gevind dat dit binne my Trie, is dat die woord geldig is of nie?
En so dan kan jy wil om seker te maak dat, en dis toe dat as jy daardie volgorde gevind het,
dan kan jy wil om te kyk of die woord geldig is of nie
want onthou terug in die vorige geval dat ek getrek het waar ons moes FOOB,
dit was 'n geldige ry dat ons gevind, maar was nie 'n werklike geldige woord self.
>> Net so, los in die drieë wat jy wil al die nodes in jou Trie af te laai.
Jammer. Soortgelyk aan die hash tabelle waar los ons bevry al die nodusse,
in die drieë wat ons wil ook vry al die nodes.
Los sal eintlik werk maklikste van onder na bo
want dit is in wese geskakelde lyste.
Daarom wil ons seker maak dat ons hou op al die waardes
en vry almal van hulle uitdruklik.
Wat jy gaan om te wil doen as jy die werk met 'n Trie
is 'n reis na die onderkant en vry om die laagste moontlike node eerste
en gaan dan aan al die kinders en dan gratis al daardie,
optrek en dan gratis, ens.
Soort van soos die hantering van die onderste laag van die oor die eerste
en dan gaan tot bo wanneer jy alles bevry het.
Dit is 'n goeie voorbeeld van waar rekursiewe funksie kan handig te pas kom.
Sodra jy die onderste laag van jou Trie bevry,
dan is jy op die res van dit los noem,
om seker te maak dat jy bevry elke mini -
Jy kan soort van visualiseer dit as mini drieë.
So jy hoef jou wortel hier.
Ek is net te vereenvoudig dit so ek het nie 26 van hulle te trek.
So jy het hierdie, en dan hierdie verteenwoordig rye van woorde
waar al die van hierdie klein sirkels is briewe wat is geldig volgordes van letters.
Laat ons net 'n bietjie meer voortgaan.
Wat jy gaan om te wil doen, is die bodem hier en dan vry hierdie een
en dan vry om hierdie een aan die onderkant voordat jy vry om die boonste een hier
want as jy vrye iets in die tweede vlak,
dan is jy eintlik sou hierdie waarde hier verloor.
Dit is hoekom dit belangrik is in los vir 'n Trie om seker te maak dat jy eerste op die bodem bevry.
Wat wil jy dalk om te doen is om te sê vir elke node
Ek wil al van die kinders af te laai.
>> Nou dat ons het gegaan oor los vir die hash tafel metode sowel as die oor die metode,
ons gaan om te wil om te kyk na Valgrind.
Loop jy Valgrind met die volgende opdragte.
Jy het valgrind-v.
Jy kontrolering vir alle lekkasies wanneer jy speller hierdie sekere teks
omdat speller te neem in 'n tekslêer.
So Valgrind sal vir jou 'n program hardloop, vertel hoeveel bytes jy toegeken,
hoeveel bytes jy bevry, en dit sal jou vertel of jy bevry net genoeg
of jy het nie vry genoeg,
of soms kan jy selfs oor vry, soos vry om 'n nodus wat reeds bevry
en dit sal u laat terugkeer foute.
As jy gebruik Valgrind, sal dit gee jou 'n paar boodskappe
aandui of jy het bevry minder as genoeg, net genoeg,
of meer as genoeg tyd.
>> 'N deel van hierdie pset, dit is opsioneel The Big Raad uit te daag.
Maar wanneer ons te doen het met hierdie datastrukture
dit is soort van pret om te sien hoe vinnig en hoe doeltreffend jou datastrukture kan wees.
Is jou hash funksie gevolg in 'n baie van botsings?
Of is jou data grootte regtig groot?
Neem dit 'n baie tyd om te verken?
In die log van die speller, dit uitgange hoeveel tyd wat jy gebruik om te laai,
om seker te maak, grootte te voer en af ​​te laai,
en so dié gepos in The Big Raad,
waar jy kan meeding teen jou klasmaats
en 'n paar personeellede om te sien wie die vinnigste speltoetser het.
Een ding wat ek wil om daarop te let oor die hash tabelle
is dat daar is 'n paar redelik eenvoudige hash funksies wat ons kan dink.
Byvoorbeeld, jy het 26 emmers, en so elke emmer
ooreenstem met die eerste letter in 'n woord,
maar dit gaan om te lei tot 'n redelik ongebalanseerde hash tafel
want daar is 'n baie minder woorde wat begin met 'n X as begin met M, byvoorbeeld.
Een manier om te gaan oor die speller is as jy wil al die ander funksies om af te kry,
dan net 'n eenvoudige hash funksie gebruik om in staat wees om jou kode aan die gang te kry
en gaan dan terug en verander die grootte van jou hash tafel en die definisie.
Daar is 'n baie van die hulpbronne op die internet vir hash funksies,
en so is dit vir hierdie pset hash funksies word toegelaat om navorsing te doen op die internet
vir 'n paar wenke en inspirasie so lank as wat jy maak seker om te noem waar jy het dit uit.
Jy is welkom om te kyk en te interpreteer sommige hash funksie wat jy kry op die internet.
Terug na daardie, kan jy in staat wees om te sien as iemand 'n Trie gebruik
of die implementering daarvan is vinniger as jou hash tafel of nie.
Jy kan verskeie kere aan The Big Raad.
Dit sal jou mees onlangse inskrywing te teken.
So miskien het jy verander jou hash funksie en dan besef dat dit eintlik 'n baie vinniger
of 'n baie stadiger as voorheen.
Dit is 'n bietjie van 'n prettige manier.
Daar is altyd 1 of 2 personeellede wat probeer om die stadigste moontlike woordeboek te maak,
so dit is altyd pret om na te kyk.
>> Die gebruik vir die pset is jy hardloop speller met 'n opsionele woordeboek
en dan 'n verpligte teks lêer.
By verstek wanneer jy speller met net 'n teks lêer en spesifiseer nie 'n woordeboek,
dit gaan die woordeboek teks lêer, die groot een om te gebruik
in die cs50/pset5/dictionaries-lêergids.
Dat 'n mens meer as 100,000 woorde.
Hulle het ook 'n klein woordeboek, wat aansienlik minder woorde
wat CS50 vir jou gemaak het.
Kan egter baie maklik jy net maak jou eie woordeboek
as jy net wil om saam te werk in klein voorbeelde -
Byvoorbeeld, as jy wil gdb te gebruik en jy weet die spesifieke waardes
wat jy wil jou hash tafel te karteer aan.
So jy kan net jou eie teks lêer net met BAR, BAZ, FOO en Tapper,
maak dat in 'n tekslêer, skei dié elk met 1 lyn,
en maak dan jou eie teks lêer wat letterlik net miskien 1 of 2 woorde bevat
sodat jy presies weet wat die uitset moet wees.
Sommige van die monster teks lêers wat The Big Raad wanneer jy uitdaging sal kontroleer
Oorlog en Vrede en 'n Jane Austen roman of iets soos dit.
So wanneer jy begin, dit is 'n baie makliker om jou eie teks lêers te maak
wat bevat slegs 'n paar woorde, of miskien 10
sodat jy kan voorspel wat die uitkoms moet wees
en dan gaan dit teen so meer van 'n beheerde voorbeeld.
En so omdat ons te doen het met die voorspelling en die dinge rondom,
Ek wil weer aan te moedig jy pen en papier te gebruik
want dit is regtig gaan om jou te help met hierdie een -
die tekens van die pyle, hoe die hash tafel of hoe jou Trie lyk,
wanneer jy iets waar die pyle gaan bevry,
hou jy genoeg, sien jy enige skakels verdwyn
en val in die afgrond van geheue gelek.
So asseblief, probeer om dinge uit te trek selfs nog voordat jy kode skryf neer.
Teken dinge uit, sodat jy verstaan ​​hoe dinge gaan werk
want dan het ek waarborg jy hardloop in minder pointer muddles daar.
>> Alles reg.
Wil ek wens jou die beste van geluk met hierdie pset.
Dit is waarskynlik die moeilikste een.
So probeer om te vroeg te begin, teken dinge uit, teken dinge uit, en baie geluk.
Dit was Walk Through 5.
>> [CS50.TV]