>> Parolanto 1: Bone, do ni estas dorso.
Bonvenon CS50.
Jen la fino de semajno sep.
Do memoru ke lasta fojo, ni komencis rigardas iomete pli kompleksa
datumstrukturoj.
De supre ĝis nun, ĉio ni havis vere je nia dispono, estis jena: tabelo.
>> Sed antaŭ ol ni forĵeti la tabelo kiel ne cxion, kio interesa, kiu efektive
efektive estas, kiaj estas kelkaj el la pluses de tiu simpla datumoj
strukturon tiel multe?
Kio estas tio bona?
Ĝis nun, kiel ni vidis?
Kion vi havas?
Nenio.
>> Lernanto: [inaudibles].
>> Parolanto 1: Kio estas tio?
>> Lernanto: [inaudibles].
>> Parolanto 1: Fiksa grandeco.
Bone, do kial estas fiksita grandeco bona kvankam?
>> Lernanto: [inaudibles].
>> Parolanto 1: Bone, do ĝi estas efika en la senso ke oni povas atribui al
fiksa sumo de spaco, kiu espereble Estas ĝuste tiel
spaco kiel vi volas.
Por ke povus esti absolute a alpago.
>> Kio estas alia ĉe flanko de tabelo?
Jes?
>> Lernanto: [inaudibles].
>> Parolanto 1: Ĉiuj - sorry?
>> Lernanto: [inaudibles].
>> Parolanto 1: Ĉiuj skatoloj en memoro aŭ apud la alia.
Kaj tio estas utila - kial?
Tio estas tute vera.
Sed kiel ni povas ekspluati kiun veron?
>> Lernanto: [inaudibles].
>> Parolanto 1: Ekzakte, ni povu kontroli kiu kie ĉiu estas nur sciante
unu adreso, nome la adreso de la unua bitoko de tiu eron de memoro.
Aŭ en la kazo de la kordo, la adreso de la unua
char en tiu linio.
Kaj de tie, ni povas trovi la finon de la kordo.
Ni povas trovi la dua elemento, la tria elemento, kaj tiel plu.
>> Kaj tial la ornama metodo de priskribi ke trajto estas ke arrays doni al ni
hazarda aliron.
Nur uzante la kvadrata krampo skribmaniero kaj numero, vi povas salti al
specifa elemento en la tabelo en konstanta tempo, granda O
de unu, por tiel diri.
>> Sed jam pasis kelkaj downsides.
Kio tabelo ne tre facile?
Kio estas tio Ne bona?
>> Lernanto: [inaudibles].
>> Parolanto 1: Kio estas tio?
>> Lernanto: [inaudibles].
>> Parolanto 1: Pligrandigi en grandeco.
Do la downsides de la tabelo estas precize la malo de kion la
upsides estas.
Do unu el la downsides estas ke ĝi estas fiksa grandeco.
Do vi ne povas vere kreski ĝin.
Vi povas reallocate pli grandan parton de memoro, kaj poste movi la malnovaj elementoj
en la nova tabelo.
Kaj poste libera la malnova tabelo, por Ekzemple, uzante malloc aŭ similan
funkcio nomita realloc, kiu reallocates memoro.
>> Realloc, kiel flanken, provas doni al vi memoro kiu estas apud la tabelo
ke vi jam havas.
Sed ĝi povus movi aĵojn ĉirkaŭ aro.
Sed en mallonga, tio estas multekosta, ĉu ne?
Ĉar se vi havas eron de memoro de tiun grandecon, sed vi vere volas unu
de tiu grandeco, kaj vi volas konservi la originalaj elementoj, vi havas
proksimume lineara tempo kopiado procezo kiu bezonas por pasi de
malnova tabelo al nova.
Kaj la realo estas demandi la mastruma sistemo denove kaj denove kaj
denove por grandaj pecoj da memoro povas komenci kostos vin iom da tempo ankaŭ.
Do ĝi estas tiel benon kaj malbenon en maski, la fakto ke tiuj arrays
estas de fiksa grandeco.
Sed se ni enkonduki anstataŭ io kiel tiu, kiun ni nomas kunligita
listo, ni preni kelkajn upsides kaj kelkaj downsides tie ankaŭ.
>> Do ligitaj listo estas simple datumoj strukturo formita de C structs en ĉi
kazo, kie struct, revokon, estas nur ujo por unu aŭ pli specifajn
tipojn de variabloj.
En ĉi tiu kazo, kion fari la datumtipoj ŝajnas esti ene de la struct ke
lasta tempo ni nomas nodon?
Ĉiu de ĉi tiuj ortanguloj estas nodo.
Kaj ĉiu el la plej malgrandaj ortanguloj ene de ĝi estas datumtipo.
Kio tipoj ni diru ili estis lunde?
Jes?
>> Lernanto: [inaudibles].
>> Parolanto 1: A ŝanĝiĝema kaj puntero, aŭ pli specife, la int, por n,
kaj puntero malsupre.
Ambaŭ el tiuj hazarde estas 32 bitoj, ĉe Almenaŭ en komputilo kiel ĉi CS50
Aparato, kaj tiel ili estas desegnita same en grandeco.
>> Do kio estas uzanta la puntero kvankam por ŝajne?
Kial aldoni tiun sagon nun kiam arrays estis tiom bela kaj pura kaj simpla?
Kio estas la puntero fari por ni en ĉiu el tiuj nodoj?
>> Lernanto: [inaudibles].
>> Parolanto 1: Ekzakte.
Oni diras al vi kie la sekvanta oni estas.
Do mi specon de uzi la analogio de uzante fadeno ordigi de
enhebrar tiuj nodoj kune.
Kaj tio estas ĝuste kion ni faras kun montriloj ĉar ĉiu el tiuj
pecoj de memoro povas aŭ ne esti Bela, malantaŭo al malantaŭo apogi
ene de RAM, ĉar ĉiufoje kiam vi voki malloc dirante: donu al mi sufiĉe
bajtoj por nova nodo, ĝi povus esti ĉi tie aŭ povus esti ĉi tie.
Povus esti ĉi tie.
Vi simple ne scias.
>> Sed uzante indikoj en la adresojn de tiujn nodojn, vi povas punkto ilin
kune en maniero kiu similas vide kiel lerta eĉ se ĉi tiuj aferoj estas
ĉiuj etendis en viaj unu aŭ viaj du aŭ vian kvar gigabajtoj de RAM
ene de via propra komputilo.
>> Do la malavantaĝo, ĉar, de lerta kunligita estas kio?
Kio estas prezo ni estas ŝajne pagi?
>> Lernanto: [inaudibles].
>> Parolanto 1: Pli spaco, ĉu ne?
Ni, en ĉi tiu kazo, duobligis la kvanto de spaco ĉar ni foriris
de 32 bitoj por ĉiu nodo, por ĉiu int, tiel nun 64 bitoj ĉar ni devos
teni ĉirkaŭ puntero tiel.
Vi ricevas pli efikeco se via struct estas pli granda ol tiu simpla afero.
Se vi efektive havas studento ene el kiuj estas paro de ŝnuroj por
nomo kaj domo, eble oni ID numeron, eble iuj aliaj kampoj entute.
>> Do se vi havas sufiĉe granda struct, tiam eble la kosto de la puntero estas
Ne tia granda interkonsento.
Tiu estas iom de angulo kazo en tiu ni stokante tia simpla komenca
ene de la ligitaj listo.
Sed la punkto estas la sama.
Vi certe pasi pli memoro, sed vi fariĝas
fleksebleco.
Ĉar nun se mi volas aldoni elementon komence de ĉi tiu listo,
Mi devas atribui nova nodo.
Kaj mi devas nur ĝisdatigi tiujn sagoj iel por nur movas
iuj indikoj ĉirkaŭe.
>> Se mi volas enmeti ion en la Meze de la listo, mi ne devas
puŝi ĉiuj flanken kiel ni faris en semajnoj estinteco kun niaj volontuloj kiuj
reprezentis tabelo.
Mi povas nur atribui nova nodo kaj tiam simple notas la sagoj en
malsamaj direktoj ĉar ĝi ne devas resti en reala
memoro veran linion kiel mi desegnis ĝin ĉi tie en la ekrano.
>> Kaj poste laste, se vi volas enmeti ion al la fino de la listo, estas
eĉ pli facila.
Ĉi tiu estas speco de arbitra skribmaniero, sed 34 La pointer, prenu konjekton.
Kiu estas la valoro de lia puntero plej verŝajne desegnita ia kiel malnova
lernejo anteno tie?
>> Lernanto: [inaudibles].
>> Parolanto 1: Estas probable nula.
Kaj ĝuste tiu estas unu aŭtoro reprezento de nula.
Kaj estas nulaj ĉar vi absolute bezonas scii kie la fino de kunligita
listo estas, ke vi observu sekva kaj sekvante kaj sekvante tiujn sagoj
al iu rubo valoro.
Do nula estos signifi ke ne estas pli nodoj al la rajto de la numero 34,
en ĉi tiu kazo.
>> Do ni proponas ke ni povas apliki tiu nodo en kodo.
Kaj ni vidis tian de sintakso antaŭe.
Typedef ĝuste difinas nova tipo por ni, donas al ni sinonimo kiel
kordo estis por char *.
En tiu kazo, ĝi tuj doni al ni stenografio skribmaniero por ke struct nodo
povas anstataŭ simple esti skribita kiel nodo, kiu estas multe pli pura.
Ĝi estas multe malpli verbose.
>> Ene de nodo estas ŝajne int vokis n, kaj tiam struct nodo *
kio signifas ekzakte kion ni deziris la sagojn por signifi, puntero al alia
nodo de la ĝusta sama datumtipo.
Kaj mi proponas ke ni povus efektivigi serĉo funkcio kiel tiu, kiu en
unuavide povus ŝajni iom kompleksa.
Sed ni vidu ĝin en kunteksto.
>> Permesu al mi iri al la aparato tie.
Permesu al mi malfermi dosieron nomatan Listo nula punkto h.
Kaj tio nur enhavas la difinon ni nur vidis antaŭ momento por ĉi datumoj
tipo nomita nodo.
Do ni metis tiun en dot h dosiero.
>> Kaj kiel flanken, kvankam ĉi programo kiu vi estas, por vidi estas
Ne ĉiuj kiuj kompleksaj, estas ja konvencion kiam skribi programon por
meti aĵojn kiel datumtipoj, tiri konstantoj kelkfoje, ene de via
header dosiero kaj ne nepre en via C dosiero, certe kiam via
programoj akiri pli kaj pli grandaj, tiel ke vi scias kie serĉi ambaŭ por
dokumentaro en kelkaj kazoj, aŭ por fundamentojn kiel ĉi tio, la
difino de iu tipo.
>> Se mi nun malfermi liston nula punkto c, rimarki kelkajn aferojn.
Ĝi inkludas kelkajn header files, plej pri kiu ni vidis antaŭe.
Ĝi inkludas lia propra header dosiero.
>> Kaj kiel flanken, kial tio estas duobla citilojn tie, kontraste al la angulo
krampoj en la linio kiu Mi reliefigis tie?
>> Lernanto: [inaudibles].
>> Parolanto 1: Jes tuj kiam estas loka dosiero.
Do, se ĝi estas loka dosiero de via propra ĉi tie on line 15, ekzemple, oni uzas
citiloj anstataŭ de la angled krampoj.
>> Kaj jen estas ia interesa.
Rimarku, ke mi deklaris tutmonda variablo en tiu programo on line 18
nomita unue, la ideo esti ĉi estas tuj estos referenco al la unua
nodo en mia ligillisto, kaj mi havas inicializado ĝin al nula, ĉar mi havas
ne asignitaj ajna reala nodoj nur ankoraŭ.
>> Do tio reprezentas, pictóricamente, kion ni vidis antaŭ momento en la bildo kiel
ke puntero sur la fora forlasis flanko.
Do nun, ke puntero ne havas sagon.
Ĝi anstataŭe estas nur nula.
Sed reprezentas kio estos la adreso de la unua efektiva
nodo en tiu listo.
Do mi implementado ĝi estas tutmonda ĉar, kiel vi vidas, ĉiuj ĉi
programo faras en la vivo estas implemento lerta kunligita por mi.
>> Nun mi havas kelkajn prototipojn tie.
Mi decidis apliki karakterizaĵoj kiel forigo, inserción, serĉado, kaj
trairado -
la lasta nur esti promenado tra la listo, presi el ĝiaj eroj.
Kaj nun jen mia ĉefa rutino.
Kaj ni ne pasigas tro da tempo sur tiuj ekde ĉi tiu estas speco de, mi esperas
malnova ĉapelo de nun.
>> Mi tuj faros la sekvajn, dum la uzanto kunlaboras.
Do, mi tuj presi tiun menuon.
Kaj mi formatita kiel pure kiel mi povis.
Se la uzanto tajpas en unu, tio signifas ili volas forigi ion.
Se la uzanto tajpas en du, kiu signifas ili volas enŝovu ion.
Kaj tiel plu.
Mi tuj poste instigas tiam por komando.
Kaj poste mi iros por uzi GetInt.
>> Do tiu estas vere simpla menuing interfaco kie vi nur devas tajpi
nombro surĵeto al unu el tiuj komandoj.
Kaj nun mi havas belan pura ŝaltilo aserto, ke tuj ŝalti
kion ajn la uzanto tajpas in
Kaj se ili tajpis unu, mi instruos vin voki forviŝi kaj rompi.
Se ili enigis du, mi instruos vin voki insertar kaj rompi.
>> Kaj nun rimarki Mi metis ĉiu de ĉi tiuj sur la sama linio.
Ĉi tio estas nur stila decido.
Tipe ni vidis ion kiel ĉi tio.
Sed mi ĵus decidis, sincere, mia programo aspektis pli legebla ĉar
estis nur kvar kazoj nur printi ĝin kiel ĉi tio.
Plene legitima uzo de stilo.
Kaj mi faros ĉi tiel longe kiel la uzanto ne tajpis nulo, kiun mi
decidis signifos ili volas forlasi.
>> Do nun rimarkas kion mi tuj faros ĉi tie.
Mi tuj liberigi la listo ŝajne.
Sed pli sur tiu en nur momento.
Ni unue kuri ĉi tiu programo.
Do lasu min fari pli grandan fina fenestro, ĝi pentras oblikvo listo 0.
Mi tuj iros antaŭen kaj enmeti per tajpante du, numero kiel 50, kaj nun
vi vidos la listo estas nun 50.
Kaj mia teksto nur scrolled supren iom.
Do nun rimarkas la listo enhavas la nombro 50.
>> Ni faru alian insert per prenante du.
Ni entajpi la numeron kiel unu.
Listo estas nun unu, sekvita de 50.
Do tiu estas nur teksta prezento el la listo.
Kaj ni enigi pli numeron kiel la numero 42, kiu estas espereble
tuj finos en la mezo, ĉar tiu programo en aparta klaso ĝin
elementoj kiel ĝi enmetas ilin.
Do ni havas ĝin.
Super simpla programo kiu povis absolute uzis tabelo, sed mi
okazi esti uzanta ligillisto nur tiel mi povas dinamike
kreski kaj retiri ĝin.
>> Do ni rigardu por serĉo, se mi kuri komando tri, mi volas serĉi
por, ni diru, la numero 43.
Kaj nenio ŝajne trovis, ĉar mi reiris neniu respondo.
Do ni faru ĉi denove.
Serĉi.
Ni serĉu 50, aŭ pli ĝuste serĉi por 42, kiu havas belan
iom subtila signifon.
Kaj mi trovis la signifon de la vivo tie.
Numero 42, se vi ne scias, la referenco, Google ĝin.
Ĉio bone.
Do kio tiu programo farita por mi?
Ĝi simple permesis al mi enmeti tiel for kaj serĉo de elementoj.
>> Ni rapide antaŭen, tiam, tiu funkcio ni rigardis
lundon kiel teaser.
Do tiu funkcio, mi asertas, serĉoj por elementon en la listo per unua
unu, instigante la uzanto kaj tiam nomante GetInt akiri realan int
ke vi volas serĉi.
>> Tiam rimarki tion.
Mi tuj kreos provizoran variablo en linio 188 nomis puntero -
PTR -
povus esti nomata ĝi nenion.
Kaj ĝi estas puntero al nodo ĉar mi diris nodo * tie.
Kaj mi inicializar ĝin esti egala al unua tiel, ke mi efektive havas mian
fingro, por tiel diri, en la tre unua ero de la listo.
Do, se mia dekstra mano jen PTR mi montrante la saman aferon tiu unua
notas ĉe.
>> Do nun denove en kodo, kio okazas poste -
ĉi tiu estas komuna paradigmo kiam ripetanta super strukturo kiel
ligitaj listo.
Mi tuj faros la sekvajn dum pointer ne estas egala al nula Do dum
mia fingro ne montras al iuj nulaj valoro, se puntero sago n egalas n.
Ni rimarkas unue ke n estas kion la uzanto tajpita en po GetInts nomas ĉi tie.
>> Kaj puntero sago n signifas kion?
Nu, se ni reiru al la bildo tie, se mi havas fingro montrante
tiu unua nodo enhavas naŭ, la sago esence signifas iri al tiu
nodo kaj ekpreni la valoro je situo n, en ĉi tiu kazo, la datumoj kampo nomata n.
>> Kiel flanken - kaj ni vidis tiun paron de semajnoj kiam iu demandis -
tiu sintakso estas nova, sed ne doni al ni povojn kiujn ni
ne jam havas.
Kio estis tiu frazo ekvivalenta al uzante dot notacio kaj stelo paro
de semajnoj, kiam ni senŝeligita reen ĉi tiu mantelo iom antaŭtempe?
>> Lernanto: [inaudibles].
>> Parolanto 1: Ekzakte, estis stelo, kaj tiam estis stelo dot n, kun
parentezoj tie, kiu aspektas, sincere, mi pensas multe
pli kripta legi.
Sed stelo pointer, kiel ĉiam, per iri tien.
Kaj kiam vi estas tie, kio datumoj kampo vi volas aliri?
Nu vi uzas la skalara skribmaniero por aliri oni structs datumoj kampon, kaj mi
specife volas n.
>> Sincere, mi argumentas ĉi estas nur malfacile legi.
Estas pli malfacile memoras kie do la parantezoj iru, la
stelo kaj ĉiuj tion.
Do la mondo adoptis iujn sintaksa sukero, por tiel diri.
Nur sexy maniero diri, ĉi tiu estas ekvivalento, kaj
eble pli intuicia.
Se puntero estas ja pointer, la saga skribmaniero signifas iri tien por trovi
la kampo en tiu kazo nomata n.
>> Do, se mi trovas ĝin, rimarkos, kion mi faros.
Mi simple presi, mi trovis procento i, ŝtopanta en la valoro por int.
Mi nomas dormi por dua nur speco de paŭzo aĵoj en la ekrano por
doni al la uzanto dua sorbi kio ĵus okazis.
Kaj tiam mi rompos.
Alie, kion mi faru?
Mi ĝisdatigos puntero al egala pointer sago tuj.
>> Do nur por esti klara, tio signifas iri tie, uzante mian malnovan-lernejo skribmaniero.
Do tio nur signifas iri al kiom vi fingromontrante, kio en la tre
unua kazo estas mi indik la struct kun naŭ en ĝi.
Do mi iris tie.
Kaj tiam la skalara skribmaniero signifas, atingi la valoro je proksimaj.
>> Sed la valoro, kvankam ĝi estas desegnita kiel mallarĝa, estas nur nombro.
Ĝi estas nombraj adreso.
Do ĉi tiu linio de kodo, ĉu skribita kiel ĉi tio, la pli kripta
maniero, aŭ kiel ĉi tio, la iomete pli intuicia maniero, nur signifas movi mian manon
de la unua nodo al la sekva, kaj tiam la sekva, kaj tiam la
sekva, kaj tiel plu.
>> Do ni ne loĝas sur la alia realigoj de enigi kaj forigi
kaj trairado, la du unuaj de kiuj estas sufiĉe implikitaj.
Kaj mi kredas ke estas sufiĉe facile akiri perdis farinte ĝin parole.
Sed kion ni povas fari ĉi tie estas provi determini kiel
bona por fari ĉi vide.
Ĉar mi proponus, ke se ni volas enmeti elementojn en tiun
ekzistanta listo, kiu havas kvin elementoj -
9, 17, 22, 26, kaj 33 -
se mi tuj apliki tion en kodo, mi bezonas konsideri kiel iri
pri fari ĉi tion.
>> Mi proponus porti bebon paŝoj per kiu, en tiu kazo mi volas diri, kio estas
la eblaj scenaroj, ke ni povus renkonti ĝenerale?
Kiam apliki insert por kunligita listo, tiu simple okazas al esti
specifa ekzemplo de grandeco kvin.
Nu, se vi volas enmeti numeron, kiel diras la nombro unu kaj
subteni ordo ordo, kie evidente plenumas la numero oni bezonas
iri en ĉi tiu specifa ekzemplo?
Kiel en la komenco.
>> Sed kio estas interesa estas ke se vi volas enmeti unu en tiun
listo, kion speciala puntero bezonas esti ĝisdatigita ŝajne?
Unua.
Do mi dirus, tiu estas la unua kazo ke ni volas konsideri, oni
scenaro engaĝante enmeto en la komenco de la listo.
>> Ni desxiri ekstere eble estas tiel facila aŭ eĉ facilan kazon, relative parolas.
Supozu mi volas enmeti la numero 35 en ordo ordo.
Ĝi evidente apartenas tie.
Do kio puntero evidente tuj devas esti ĝisdatigita en tiu scenaro?
34 La puntero igante ne nula sed la adreso de la struct
enhavanta la nombron 35.
Do jen kazo du.
Do jam mi estas speco de cuantizando kiom da laboro mi devas fari ĉi tie.
>> Kaj fine, la evidenta mezo kazo estas ja, meze, se mi volas
enŝovu iun kiel diras 23, kiu iras inter la 23 kaj la 26, sed
nun aĵoj iom pli implikitaj pro kio
montriloj bezonas esti ŝanĝita?
Do 22 evidente bezonas esti ŝanĝita ĉar li ne povas atentigi al 26 anymore.
Li bezonas atentigi al la nova nodo ke Mi devos atribui nomante
malloc aŭ iu ekvivalento.
>> Sed tiam mi ankaŭ bezonas, ke nova nodo, 23 en ĉi tiu kazo, havi lian puntero
indik kiu?
26.
Kaj tuj esti ordo de operacioj tie.
Ĉar se mi tion faras malsagxe kaj mi ekzemple komenco komence de
la listo, kaj mia celo estas enigi 23.
Kaj mi kontrolu, ĉu ĝi apartenas ĉi tie, proksime naŭ?
No
Ĉu ĝi apartenas ĉi tie, apud 17?
No
Ĉu ĝi apartenas tie apud 22?
Jes.
>> Nu, se mi estas malsaĝa tie, kaj ne pensante ĉi, Mi povus
destini mia nova nodo por 23.
Mi povus ĝisdatigi la puntero de la nodo vokis 22, montrante
ĝin ĉe la nova nodo.
Kaj tiam kion mi devas ĝisdatigi la nova nodo puntero esti?
>> Lernanto: [inaudibles].
>> Parolanto 1: Ekzakte.
Indik 26.
Sed damne, se mi ne jam ĝisdatigi 22 La puntero atentigi en ĉi ulo, kaj
nun mi havas orfoj, la resto de la listo, tiel diri.
Do ordo de operacioj tie tuj estos grava.
>> Por fari tion mi povus sxtelu; diru, ses volontuloj.
Kaj vidu se ni ne povas fari ĉi vide anstataŭ kodo-saĝa.
Kaj ni havas kelkajn belajn streso pilkoj por vi hodiaŭ.
OK, kiel pri unu, du, en la reen - sur la pinto tie.
tri, kvar, ambaŭ de vi infanoj je la fino.
Kaj kvin, ses.
Certe.
Kvin ses.
Bone kaj ni venos al vi infanoj proksima fojo.
Bone, venu supren.
>> Bone, ĉar vi ĝis tie unue, vi ŝatus esti tiu mallerte
en Google Vitra tie?
Bone, do, bone, Pokalo, gravuri video.
OK, vi estas bona iri.
>> Bone, do se vi infanoj povas veni pli ĉi tie mi preparis anticipe
iujn numerojn.
Bone, venu al ĉi tie.
Kaj kial vi ne iru iom plu tiel.
Kaj vidu, kio estas via nomo, kun la Google Vitra?
>> Lernanto: Ben.
>> Parolanto 1: Ben?
OK, Ben, vi estos la unua, laŭvorte.
Do ni tuj sendos al la fino de la scenejo.
Bone, kaj via nomo?
>> Lernanto: Jason.
>> Parolanto 1: Jason, OK vi instruos vin esti numero naŭ.
Do se vi volas sekvi Ben tiu vojo.
>> Lernanto: Jill.
>> Parolanto 1: Jill, vi tuj estos 17, kiu se mi faris tion pli
inteligente, mi havus komenciĝis ĉe la alia fino.
Vi iras tiun vojon.
22.
Kaj vi estas?
>> Lernanto: Maria.
>> Parolanto 1: Mary, vi estos 22.
Kaj via nomo estas?
>> Lernanto: Chris.
>> Parolanto 1: Chris, vi estos 26.
Kaj poste persiste.
>> Lernanto: Diana.
>> Parolanto 1: Diana, vi estos 34.
Do vi venu ĉi tien.
>> Bone, do perfektigi ordo ordigi jam.
Kaj ni iru antaŭen kaj faros cxi tiel ke ni povas vere -
Ben vi estas nur speco de rigardi Tra nenie tie.
Bone, do ni iru antaŭen kaj priskribas tiun uzante armilojn, multe kiel mi estis, precize,
kio okazas.
Do iru antaŭen kaj dedicxu vin al piedo aŭ du inter vi mem.
Kaj iru antaŭen kaj atentigi per unu mano al kiu ajn vi devu indik
surbaze de tio.
Kaj se vi estas nula nur atentigi rekte sur la plankon.
Bone, do bone.
>> Do nun ni havas ligitaj liston, lasu min proponas ke mi ludos la rolon de
PTR, do mi ne ĝeni portante ĉi ĉirkaŭe.
Kaj poste - iu stulta konvencio - vi povas nomi tiun ion vi volas -
antaŭulo pointer, pred puntero -
estas nur la alnomon ni donis en nia specimeno kodon al mia maldekstra mano.
La alia mano, kiu tuj estos gardi spuri de kiu estas kiu en la
post scenejoj.
>> Do supozu, unue, mi volas desxiri ekstere tiu unua ekzemplo de enmeto, diru
20, en la listo.
Do mi tuj bezonas iun al enkorpigi la numero 20 por ni.
Do mi bezonas malloc iu de la aŭskultantaro.
Venu supren.
Kio estas via nomo?
>> Lernanto: Brian.
>> Parolanto 1: Brian, ĉiuj rajtas, tiel vi estos la nodo enhavis 20.
Bone, venu al ĉi tie.
Kaj evidente, kie ne Brian apartenas?
Do, en la mezo de - efektive, atendi minuton.
Ni faras ĉi paneas.
Ni faris ĉi multe pli malfacila ol ĝi bezonas esti en komenco.
Bone, ni iras al libera Brian kaj realloc Brian kiel kvin.
>> Bone, do nun ni volas enmeti Brian kiel kvin.
Do venu ĉi tien apud Ben por nur momento.
Kaj vi povas supozeble diri kie ĉi tiu rakonto tuj.
Sed ni zorge pripensi la ordo de operacioj.
Kaj estas ĝuste ĉi tiu vida ke tuj laŭliniigi
kun tiu specimeno kodo.
Do jen mi PTR indikante komence ne je Ben, per, sed je ajn
taksas Li enhavas, kiu en ĉi tiu kazo estas - kio estas via nomo denove?
>> Lernanto: Jason.
>> Parolanto 1: Jason, tial ambaŭ Ben kaj mi estas indik Jason en ĉi tiu momento.
Do nun mi devas determini, kie ne Brian apartenas?
Do la sola afero mi havas aliron al nun estas lia n elemento de datumoj.
Do mi iros por kontroli, estas Brian malpli ol Jason?
La respondo estas vera.
>> Do kio nun devas okazi, en la ĝusta ordo?
Mi bezonas ĝisdatigi kiom da referencoj en tuta en cxi tiu rakonto?
Kie mia mano ankoraŭ indik Jason kaj vian manon - se vi volas
metu vian manon kiel, ia, mi ne scias, demandosigno.
Bone, nu.
>> Bone, do vi havas kelkaj kandidatoj.
Aux Ben aŭ mi aŭ Brian aux Jason aŭ ĉiuj aliaj, kiuj
montriloj bezonas ŝanĝi?
Kiom entute?
>> Bone, do du.
Mia puntero ne vere gravas anymore ĉar mi estas nur dumtempa.
Do estas tiuj du infanoj, supozeble, ambaŭ Ben kaj Brian.
Do mi proponas ke ni ĝisdatigi Ben, ĉar li estas unua.
La unua ero de tiu ĉi listo nun tuj estos Brian.
Do Ben punkto je Brian.
OK, nun kion?
>> Kiu akiras notita al kiu?
>> Lernanto: [inaudibles].
>> Parolanto 1: Bone tiel Brian havas atentigi ĉe Jason.
Sed mi miskalkulis ke puntero?
Ĉu mi scias, kie Jason estas?
>> Lernanto: [inaudibles].
>> Parolanto 1: Mi faros, kiam mi estas la provizora puntero.
Kaj supozeble mi ne ŝanĝiĝis atentigi ĉe la nova nodo.
Do ni povas simple havi Brian punkto en kiu ajn mi fingromontrante.
Kaj ni faris.
Do kazo, inserción en la komencante de la listo.
Estis du ŝlosilaj paŝoj.
Unu, ni devas ĝisdatigi Ben, tiam ni ankaŭ devas ĝisdatigi Brian.
Kaj tiam mi ne devas ĝeni traipsing tra la resto de la
listo, ĉar ni jam trovis sian situo, ĉar li apartenis al la
maldekstre de la unua ero.
>> Bone, do sufiĉe simpla.
Fakte, ĝi sentas kiel ni estas preskaŭ farante ĉi tro komplika.
Do ni nun desxiri ekstere de la fino el la listo, kaj rigardu, kie
la komplekseco startas.
Do se nun mi alloc de la aŭskultantaro.
Ĉiu volas ludi 55?
Bone, mi vidis vian manon unue.
Venu supren.
Jes.
Kio estas via nomo?
>> Lernanto: [inaudibles].
>> Parolanto 1: Habata.
OK, venu supren.
Vi estos la nombro 55.
Do vi, kompreneble, ili apartenas fine de la listo.
Do ni Replay la simulado kun mi esti la PTR por nur momento.
Do mi unue iri al punkto en kion ajn Ben estas indik.
Ni ambaŭ montrante nun Brian.
Do 55 estas ne malpli ol kvin.
Do mi tuj ĝisdatigi min per indikante Brian sekva pointer, kiu
nun estas kompreneble Jason.
55 Ne malpli ol naŭ, tiel Mi tuj ĝisdatigi PTR.
Mi tuj ĝisdatigi PTR Mi tuj ĝisdatigi PTR.
Kaj mi tuj - hmm, kio estas Via nomo denove?
>> Lernanto: Diana.
>> Parolanto 1: Diana notas, kompreneble, ĉe nula per sia maldekstra mano.
Do kie faras Habata reale apartenas klare?
Al la maldekstra, ĉi tie.
Do kiel mi scias meti sxin tie Mi kredas ke mi ŝraŭbita supren.
Ĉar kio estas PTR arto ĉi tiu momento en tempo?
Nula.
Do kvankam, vide, ni povas evidente vidi ĉiujn tiujn
infanoj tie sur la scenejo.
Mi ne gardis spuro de la antaŭa persono en la listo.
Mi ne havas fingron markante, en ĉi tiu kazo, la nodo numero 34.
>> Do ni vere komencos tion.
Do nun mi vere ne bezonas duan loka variablo.
Kaj jen estas, kion vi vidos en la reala specimeno C kodo, kie kiel mi foriras,
kiam mi ĝisdatigos mian dekstran manon por noti Jason, tiel lasante Brian malantaŭe, mi
pli bone komenci per mia maldekstra mano ĝisdatigi kie mi estis, tiel ke, kiel mi foriras
tra ĉi tiu listo -
pli mallerte ol mi intencis nun tie vide -
Mi tuj alvenos al la fino de la listo.
>> Tiu mano ankoraŭ estas nula, kiu estas sufiĉe senutila, krom por indiki
Mi estas klare al la fino de la listo, sed nun almenaŭ mi havas
antaŭulo puntero indikante ĉi tie, do nun kio manoj kaj kio montriloj bezonas
esti ĝisdatigita?
Kies mano vi volas por reagordi unua?
>> Lernanto: [inaudibles].
>> Parolanto 1: Bone, do Diana aj jaroj.
Kie vi volas atentigi Diana la maldekstra puntero at?
Je 55, supozeble, por ke ni insertos tie.
Kaj kie devus 55 puntero iras?
Malsupren, reprezentante nula.
Kaj de miaj manoj, je ĉi tiu punkto, ne gravas ĉar ili estis nur
temporal variabloj.
Do nun ni faris.
>> Do la aldonan komplekseco tie - kaj ĝi ne estas tiel malfacila por apliki,
sed ni bezonas malĉefan variablo fari certa, ke antaŭ ol mi movi mian rajton
Unuflanke, mi ĝisdatigos la valoro de mia maldekstra mano, pred puntero en ĉi tiu kazo, tiel
ke mi havas trenante puntero konservi spuron de kie mi estis.
Nun kiel flanken, se vi pensas ĉi tra, tiu sentas kiel ĝi estas
iom ĝena devos konservi spuri de ĉi tiu maldekstra mano.
>> Kion farus alian solvon al tiu problemo estis?
Se vi alvenis al restrukturi la datumoj strukturo ni parolas
tra ĝuste nun?
Se tio nur speco de sentas iom ĝena havi, ŝati, du montriloj
irante tra la listo, kiu alia povus esti, en ideala mondo, subtenitaj
informo kiun ni bezonas?
Jes?
>> Lernanto: [inaudibles].
>> Parolanto 1: Ekzakte.
Ĝuste tiel ne estas vere interesa ĝermo de ideo.
Kaj ĉi tiu ideo de antaŭa pointer, montrante la antaŭa ero.
Kio se Mi nur enkorpigita ke ene de la listo mem?
Kaj ĝi tuj estos malfacile bildigi ĉi tio sen tuta papero
fali sur la plankon.
Sed supozu ke tiuj infanoj uzis ambaŭ de siaj manoj havi antaŭan
pointer, kaj proksima pointer, tiamaniere apliki kion ni vokos duoble
ligitaj listo.
Tio permesus min ordigi de rebobinado, multe pli facile sen mi, la
programisto, devi teni spuri permane -
vere permane -
el kie mi estis estinta antaŭe en la listo.
Do ni ne faros tion.
Ni tenu gxin simpla ĉar tio tuj venos al prezo, duoble
da spaco por la montriloj, se vi volas dua.
Sed tio estas ja komuna datumstrukturo konata kiel
duoble ligitaj listo.
>> Ni faros la fina ekzemplo tie kaj meti ĉi tiuj infanoj el ilia mizero.
Do malloc 20.
Venu supren for de la koridoro tie.
Bone, kio estas via nomo?
>> Lernanto: [inaudibles].
>> Parolanto 1: Pardonu?
>> Lernanto: [inaudibles].
>> Parolanto 1: Demeron?
OK veni supren.
Vi estos 20.
Vi evidente tuj apartenas inter 17 kaj 22.
Do mi lernas mian lecionon.
Mi tuj komencos puntero indik Brian.
Kaj mi tuj devos mia maldekstra mano nur ĝisdatigi al Brian kiel Mi movi al
Jason, kontrolanta faras 20 malpli ol naŭ?
No
Estas 20 malpli ol 17?
No
Estas 20 malpli ol 22?
Jes.
Do kio montriloj aŭ manoj bezonas ŝanĝi kie ili estas montrante nun?
>> Do ni povas fari 17 indik 20.
Por ke estas bone.
Kie ni volas atentigi via puntero nun?
Je 22.
Kaj ni scias, kie 22 estas, denove dankon al mia provizora puntero.
Do ni estas okej tie.
Do pro tio provizora stokado Mi tenis spuro de kie ĉiuj estas.
Kaj nun vi povas vide iru en kie vi apartenas, kaj nun ni bezonas 1, 2, 3,
4, 5, 6, 7, 8, 9 streso pilkoj, kaj ronda da aplaŭdoj por
ĉi tiuj infanoj, se ni povus.
Bele farita.
>> [Aplaŭdo]
>> Parolanto 1: Bone.
Kaj vi rajtas konservi la pecoj de papero kiel mementos.
>> Bone, do, fidu min ĝi estas multe facile marŝi tra tiu kun
homoj ol estas kun reala kodo.
Sed kion vi trovos en nur momenton nun, estas tiu sama - ho, dankon.
Dankon -
estas ke vi trovos ke la samaj datumoj strukturo, lerta kunligita, ĉu vere
esti uzata kiel konstruaĵo bloko al eĉ pli kompleksa datumstrukturoj.
>> Kaj realigi tro la temo estas, ke ni absolute enkondukis pli
komplekseco en la efektivigo de ĉi tiu algoritmo.
Insertion, kaj se ni iris tra ĝi, protokolo pri forigado kaj serĉado, estas iom
pli komplika ol ĝi Estis kun tabelo.
Sed ni gajnas iom dinamismo.
Ni ricevas adapta datumstrukturo.
>> Sed denove, ni pagas prezon de havi iun aldona komplekseco, ambaŭ en
apliki ĝin.
Kaj ni rezignis hazarda aliron.
Kaj por esti honesta, tie ne estas iu agrabla purigi diapozitivoj mi povas doni al vi, ke
diras jen kial ligitaj listo estas pli bona ol tabelo.
Kaj lasi ĝin ĉe tio.
Ĉar la temo reoccurring nun, eĉ pli en la venontaj semajnoj, estas
ke tio ne nepre ĝentilan respondon.
>> Jen kial ni havas la apartan akso de dezajno por problemo aroj.
Estos tre kuntekston sentiva ĉu vi volas uzi tiun datumoj
strukturo aŭ tiu, kaj volo dependi sur kio gravas al vi en terminoj
de rimedoj kaj komplekseco.
>> Sed mi proponas ke la ideala datumoj strukturo, la Holy Grail, estus
iu kiu estas konstanta tempo, sendepende de kiom materialo estas
interne de ĝi, ĉu ne estus mirinda se datumstrukturo revenis respondojn en
konstanta tempo.
Jes.
Tiu vorto estas en via grandega vortaro.
Aŭ ne, tiu vorto ne estas.
Nek ion tian problemon tie.
Nu vidu, se ni ne povas almenaŭ paŝon al tio.
>> Permesu al mi proponi novan datumstrukturo kiun povas uzi por malsamaj aferoj,
en ĉi tiu kazo nomata hash tablo.
Kaj tiel ni fakte reen al ekrigardante en tabelo, en ĉi tiu kazo, kaj
iom arbitre, mi desegnis tiun hash tablo tiel tablo kun speco de
du-dimensia tabelo -
aŭ pli ĝuste ĝi estas reprezentita tie kiel du dimensia tabelo - sed tio estas nur
tabelo de amplekso 26, tia, ke se ni vokas la tabelo tablo, tabulo krampo
nulo estas la rektangulo ĉe la supro.
Tabelo krampo 25 estas la rektangulo ĉe la malsupro.
Kaj ĉi tiu estas kiel mi povus desegni datumoj strukturo, en kiu mi volas konservi
popola nomoj.
>> Tiel ekzemple, mi ne eltiris la tuta afero ĉi tie sur la superkape, se mi
havis ĉi tabelo, kiun mi nun iras al voki hash tablon, kaj tiu estas denove
situo nulo.
Ĉi tie estas situo unu, kaj tiel plu.
Mi asertas, ke mi volas uzi ĉi datumoj strukturo, pro diskuto,
stoki popola nomoj, Alice kaj Bob kaj Charlie kaj aliaj tiaj nomoj.
Tiel pensas pri tiu nun kiel la komencoj de, ekzemple, vortaro
kun multe da vortoj.
Ili hazarde estas nomoj en nia ekzemplo tie.
Kaj jen estas ĉiuj tro germane, eble, apliki sorĉas kontrolilo, kiel ni
eble pro problemo starigis ses.
>> Do, se ni havas tabelo de tuta grandeco 26 por ke cxi tiu estas la 25-a loko
ĉe la malsupro, kaj mi asertas ke Alico trovas la unua vorto en la vortaro de
nomoj kiuj mi volas enmeti en RAM, en ĉi tiu datumstrukturo, kie estas
instinktoj diras al vi ke Alicio nomo devus iri en ĉi tiu tabelo?
>> Ni havas 26 ebloj.
Kie ni volas meti sxin?
Ni volas ke ŝi en krampo nulo, ĉu ne?
A por Alico, ni nomas tion nulo.
Kaj B estos unu, kaj C estos du.
Do ni tuj skribos Alicio nomon ĉi tie.
Se ni do enigi Bob, lia nomo iros tien.
Charlie iros tien.
Kaj tiel plu malsupren tra tiu datumstrukturo.
>> Tio estas mirinda datumstrukturo.
Kial?
Nu, kio estas la rula tempo de enmeto de homa nomo en tiun
datumstrukturo ĝuste nun?
Donita ke ĉi tiu tablo estas implementado, vere, kiel tabelo.
Nu estas konstanta tempo.
Ĝi estas ordo de unu.
Kial?
>> Nu kiel vi determini kie Alico apartenas?
Vi aspektas en kiu letero de ŝia nomo?
La unua.
Kaj vi povas atingi tien, se ĝi estas ĉeno, por nur rigardante kordo
krampo nulo.
Do la nula karaktero de la kordo.
Tio estas facila.
Ni faris tion en la kripto asigno semajnoj.
Kaj tiam tuj sciu ke Alico letero estas ĉefurbo, oni povas subtrahi
for 65 aŭ ĉefurbo A sin, kiu donas al ni nulo.
Tiel ni nun scias, ke Alico apartenas ĉe situo nulo.
>> Kaj donita puntero al ĉi datumoj strukturon, de iu speco, kiel longe faras
ĝin prenu min por trovi situo nulo en tabelo?
Nur unu paŝon, dekstra Estas konstanta tempo pro la hazarda aliro ni
proponita estis karakteriza de tabelo.
Do mallonge, decidi kio la indekso de Alicio nomo estas, kio estas,
tiu kazo, estas A, aŭ ni simple solvi ke al nulo, kie B estas unu kaj C estas
du, imagante, ke el estas konstanta tempo.
Mi nur devas rigardi sian unuan leteron, elŝeligi kie nulo estas
tabelo estas ankaŭ konstanta tempo.
Do teknike tio kiel du paŝoj nun.
Sed tio ankoraŭ konstanto.
Do ni nomas tiu granda O de unu, tiel ni insertos Alico en tiun tablon en
konstanta tempo.
>> Sed kompreneble, mi esti naiva tie, ĉu ne?
Kio se tie estas Aaron en la klaso?
Aŭ Alicia?
Aŭ ajna alia nomoj komencante per A. Kien ni iras meti
tiu persono, ĉu ne?
Mi volas diri, nun ekzistas nur tri homoj sur la tablo, do eble ni
devus meti al Aaron sur la situo nulo unu du tri.
>> Ĝuste, mi povus meti A tie.
Sed tiam, se ni provu enmeti David en tiu listo, kie tio David iris?
Nun nia sistemo komencas rompi malsupren, ĉu ne?
Ĉar nun Davido finas ĉi tie se Aaron estas efektive tie.
Kaj tial nun tiu tuta ideo de havi pura datumstrukturo kiun donas al ni
konstanta tempo inserciones ne plu estas konstanta tempo, ĉar mi devas
kontroli, ho, damnit, iu estas jam ĉe Alicio loko.
>> Lasu min sondi la resto de ĉi datumoj strukturo, serĉante lokon por meti
iu kiel la nomon de Aaron.
Kaj por ke tro komencas preni lineara tempo.
Cetere, se vi nun volas trovi la Aaron en tiu datumstrukturo, kaj vi
kontrolu, kaj Aaron nomo ne estas tie.
Ideale, vi simple diru Aaron ne en la datumstrukturo.
Sed se vi faras komenci farante lokon por Aaron kie devus esti D
aŭ E, vi, plej malbona kazo, devas kontroli la tuta datumstrukturo, en
kies kazo devolves en ion lineara en la grandeco de la tablo.
>> Do bone, mi riparos tion.
La problemo estas, ke mi havis 26 eroj en ĉi tiu tabelo.
Lasu min ŝanĝi ĝin.
Whoops.
Lasu min ŝanĝi ĝin tiel ke prefere esti de grandeco 26 entute, rimarki la fundo
indekso tuj ŝanĝos al n minus 1.
Se 26 estas klare tro malgranda por homoj ' nomoj, ĉar tie estas miloj da
nomoj de la mondo, ni simple faru en 100 aŭ 1000 aŭ 10.000.
Ni nur malŝparas multan pli da spaco.
>> Nu, kiu ne nepre malpliigi la probablo, ke ni ne havas du
personoj kun nomoj komencante kun A, kaj tiel, vi tuj provi meti A
nomoj en loko nulo ankoraŭ.
Ili estas ankoraŭ tuj kolizias, kiu signifas ke ni ankoraŭ bezonas solvon meti
Alice kaj Aaron kaj Alicia kaj aliaj nomoj komencante kun A aliloke.
Sed kiom de problemo estas tio?
Kio estas la probablo ke vi havi kolizioj en datumoj
strukturon kiel tiu?
>> Nu, lasu min - ni revenos al tiu demando tie ĉi.
Kaj rigardu kiel ni povus solvi ĝin unue.
Lasu min eltiri supren tiu propono ĉi tie.
Kion ni jxus priskribita estas algoritmo, heŭristika nomita lineara
sondado per kiu, se vi provus insertar io tie en ĉi tiu datumoj
strukturo, kiu nomiĝas hash tablo, kaj ne estas loko tie, vi
vere sondi la datumstrukturo kontrolanta, estas ĉi disponebla?
Ĉu ĉi Disponeblaj estas ĉi disponebla?
Ĉu tio estas havebla?
Kaj kiam fine, vi enmeti la enoficigi ke vi origine intencis
aliloke en tiu loko.
Sed en la plej malbona kazo, la sola loko eblus la tre fundo de la datumoj
strukturo, la fino de la tabelo.
>> Do lineara sondado, en la plej malbona kazo, devolves enen lineara algoritmo kie
Aaronon, se li pasas al insertos lasta en ĉi tiu datumstrukturo, li povus
kolizias kun tiu unua loko, sed tiam kabo por malbona sorto en la fino.
Do tiu estas ne konstanto tempo Holy Grail por ni.
Ĉi tiu alproksimiĝo de enmeto de elementoj en oni datumstrukturo nomata hash
tablo ne ŝajnas esti konstanta tempo almenaŭ ne en la ĝenerala kazo.
Ĝi povas devolve en iu lineara.
>> Do kio se ni solvi koliziojn iom malsame?
Do jen pli kompleksa alproksimigi al kio ankoraŭ
nomata hash tablo.
Kaj per hash, kiel flanken, kion Mi volas diri estas la indico, ke
Mi raportis al pli frua.
Por hash io povas esti penso de kiel verbo.
>> Do se vi hash Alico estas nomo, kradon funkcio, por tiel diri,
devus reveni numero.
En ĉi tiu kazo estas nulo se ŝi apartenas al situo nulo, unu, se ŝi apartenas al
situo, kaj tiel plu.
Do mia hash funkcio tiel nun estis super simpla, nur rigardante la
unua letero en ies nomon.
Sed hash funkcio prenas kiel enigo iu peco de datumoj,
kordo, oni int, kion ajn.
Kaj ĝi sputas el tipe numero.
Kaj tiu nombro estas kie tiu datumo elemento apartenas en datumstrukturo
montrigxos kiel hash tablo.
>> Do nur intuicie, tio estas iomete malsama kunteksto.
Tiu fakte estas referenco al ekzemplo engaĝante naskiĝtago, kie
povus esti tiom, kiom 31 tagoj en la monato.
Sed kion tiu persono decidas fari en kazo de kolizio?
Kunteksto nun esti, ne estas kolizio de nomojn, sed kolizio de naskiĝtago,
se du personoj havas la saman naskiĝtagon sur la 2-a de oktobro, ekzemple.
>> Lernanto: [inaudibles].
>> Parolanto 1: Jes, ankaŭ ĉi tie ni havas la utiligante de lertaj kunligitaj.
Tiel ĝi aspektas iom alie ol ni tiris ĝin pli frue.
Sed ni ŝajne devos tabelo sur la maldekstra flanko.
Tio estas unu indico, ĉar neniu aparta kialo.
Sed estas ankoraŭ tabelo.
Ĝi estas aro de montriloj.
Kaj ĉiu el tiuj elementoj, ĉiu el tiuj rondoj aŭ slashes - la oblikvo
reprezentas nula - ĉiu de tiuj montriloj estas ŝajne montrante
kio datumstrukturo?
Al ligitaj listo.
>> Do nun ni havas la kapablon malmola kodon en nia programo
la grandeco de la tablo.
En tiu kazo, ni scias ke estas neniam pli ol 31 tagoj en monato.
Tiel forta kodigo valoron kiel 31 estas racia en tiu kunteksto.
En la kunteksto de nomoj, malmola kodigo 26 ne estas senkaŭza ĝin popola
nomoj nur starti kun, ekzemple, la alfabeto engaĝante A tra Z.
>> Ni povas Cram ilin ĉiujn en kiun datumoj strukturon tiel longe kiel, kiam ni preni
kolizio, ni ne meti la nomojn ĉi tie, ni anstataŭ pensi pri tiuj ĉeloj
ne kiel kordoj mem, sed kiel montriloj al, ekzemple, Alice.
Kaj tiam Alico povas havi alian puntero al alia nomo komencante per
A. Kaj Bob vere iras tien.
>> Kaj se estas alia nomo startanta kun B, li finas ĉi tie.
Kaj tiel ĉiu el la elementoj de tiu tablo du, se ni desegnis ĉi tio
Iom pli lerte -
come on -
se ni desegnis ĉi iom pli lerte, nun iĝas adapta datumoj
strukturo, kie ne estas malfacila limo sur kiom da elementoj vi povas enmeti
en ĝin ĉar se vi ja havas kolizio, ke estas bone.
Nur antaŭeniri kaj postglui al kion ni vidis iom antaŭe estis
konata kiel lerta kunligita.
>> Nu ni paŭzo por nur momento.
Kio estas la probablo de kolizio en la unua loko?
Ĝuste, eble mi pli pensas, eble Mi estas super Engineering tiu problemo,
ĉar vi scias kion?
Jes, mi povas veni supren kun arbitraj ekzemploj sur la supro de mia kapo, kiel
Allison kaj Aaronon, sed en realeco, donita uniforma distribuo de
enigoj, tio estas iom hazarda inserciones en datumstrukturo, kio vere estas
la probablo de kolizio?
Nu rezultas, fakte super altaj.
Lasu min ĝeneraligi ĉi problemo estas kiel ĉi tio.
>> Do en ĉambro de n CS50 studentoj, kio estas la probablo ke almenaŭ
du studentoj en la cxambro havas la saman naskiĝtagon?
Do ne estas kion. kelkaj Hund -
200, 300 homoj tie kaj pluraj cent homoj hejme hodiaŭ.
Do se vi volis demandi nin kio estas la probablo de du personoj
en ĉi tiu ĉambro havante la saman naskiĝtagon, ni povas kompreni tion ĉi.
Kaj mi asertas efektive estas du personoj kun la sama naskiĝtago.
>> Ekzemple, ĉu iu havas naskiĝtagon hodiaŭ?
Hieraŭ?
Morgaŭ?
Bone, do ĝi sentas kiel mi iros havi tion fari 363 aŭ tiel plu
fojoj por fakte elkompreni se ni faras havi kolizio.
Aŭ ni povus simple fari ĉi matematike anstataŭ tediously
fari tion.
Kaj proponas la sekvajn.
>> Do mi proponas ke ni povus modeligi la probablo de du personoj havanta la
sama naskiĝtago kiel la probablon de 1 minus la probablo de neniu,
la saman naskiĝtagon.
Do por atingi ĉi, kaj ĉi tiu estas nur la ornama metodo por skribi ĉi, por la
unua persono en la ĉambron, li aŭ ŝi povas havi iu el la eblaj
naskiĝtago supozante 365 tagoj en la jaro, kun pardonpetoj al personoj kun
la 29-a de februaro naskiĝtago.
>> Do la unua persono en ĉi tiu ĉambro estas libera havi ajnan numeron de naskiĝtago
el la 365 eblecojn por ke ni faros ke 365 dividita per 365,
kiu estas unu.
La sekva persono en la ĉambron, se la celo estas eviti kolizion, povas nur
havi sian naskiĝtagon pri kiel multaj malsamaj eblaj tagoj?
364.
Do la dua termino en tiu esprimo estas esence faras ke matematiko por ni
per subtrahanta for unu ebla tago.
Kaj tiam la sekva tago, la sekva tago, la sekvanta tago malsupren al la tuta nombro
de personoj en la ĉambro.
>> Kaj se ni tiam rigardu, kio tiam estas la probablo ne de ĉiuj havanta
unika naskiĝtago, sed denove 1 minus ke, kio ni atingos estas esprimo
kiu povas tre fancifully aspekti kiel ĉi tio.
Sed estas pli interesa rigardi vide.
Tio ĉi estas abako kie sur la x-akso estas la nombro de homoj en la ĉambro, la
numeron de naskiĝtago.
Sur la y-akso estas la probablo de kolizio, du personoj
havantaj la saman naskiĝtagon.
>> Kaj la takeaway el tiu kurbo estas ke tuj kiam vi atingos like 40
studentoj, vi estas supren je 90% probablo combinatorically de du
homoj aŭ pli havanta la saman naskiĝtagon.
Kaj iam vi atingos like 58 homoj estas preskaŭ 100% de la ŝanco de la du
homoj en la ĉambro tuj havos la saman naskiĝtagon, kvankam ekzistas
365 aŭ 366 eblaj siteloj, kaj nur 58 personoj en la ĉambro.
Nur statistike vi supozeble akiri kolizioj, kiuj en mallonga
motivas ĉi tiu diskuto.
Ke eĉ se ni preni imago tien, kaj komenci havi tiuj ĉenoj, ni ankoraŭ
tuj havas kolizioj.
>> Por ke petegas la demando, kio estas la kosto de fari interpolaciones kaj forigoj
en datumstrukturo tiel?
Nu mi proponas -
kaj mi reiros al la ekrano pli tie - se ni n elementoj en la
listo, do se ni provas enmeti n eroj, kaj ni havas
kiom da tutaj siteloj?
Diru 31 entute siteloj en la kazo de naskiĝtago.
Kio estas la maksimuma longo de unu de ĉi tiuj katenoj potenciale?
>> Se denove ekzistas 31 eblaj naskiĝtago en donita monato.
Kaj ni nur clumping ĉiuj -
fakte tio estas stulta ekzemplo.
Ni faru 26an anstataŭe.
Do, se efektive havas personoj kies nomojn komenci kun A tra Z, donante
ni 26 eblecojn.
Kaj ni uzas datumstrukturo kiel tiu, kiun ni ĵus vidis, per kiu ni havas
tabelo de montriloj, ĉiu el kiuj notas al ligillisto kie la
unua listo estas ĉiuj kun la nomo Alico.
La dua listo estas ĉiu kun la enoficigi komencante kun A, komencante
kun B, kaj tiel plu.
>> Kio estas la probabla longo de ĉiu el tiuj listoj se ni supozas belan pura
dissendo de nomoj A tra Z trans la tuta datumstrukturo?
Estas n popolo en la datumstrukturo dividita de 26, se ili estas bele
etendis super la tuta datumstrukturo.
Do la longecon de ĉiu el tiuj ĉenoj estas n dividita per 26.
Sed en granda a skribmaniero, kio estas tio?
Kio estas tio vere?
Do estas vere nur n, ĉu ne?
Ĉar ni diris en la pasinteco, ke uf vi dividi per 26.
Jes, en la realo estas pli rapida.
Sed en teorio, ne estas fundamente cxio, kion pli rapida.
>> Do ni ne ŝajnas esti tiom multe pli proksima al tiu sankta Grail.
Fakte, ĉi tiu estas nur lineara tempo.
Heck, je ĉi tiu punkto, kial ni ne nur uzi unu grandega ligitaj listo?
Kial ni ne simple uzi unu grandega tabelo por stoki la nomojn de
ĉiuj en la ĉambro?
Nu, estas tie ankoraŭ ion konvinka pri hash tablo?
Ĉu ekzistas ankoraŭ io konvinka pri datumstrukturo
kiu similas al tio?
Ĉi tiu.
>> Lernanto: [inaudibles].
>> Parolanto 1: Dekstra, kaj denove se estas nur lineara tempa algoritmo, kaj
lineara tempo datumstrukturo, kial mi ne nur stoki ĉies nomon en granda
tabelo, aŭ en granda ligitaj listo?
Kaj ĉesas fari CS tiel malfacila ol ĝi bezonas esti?
Kio estas konvinka pri tio, eĉ kvankam mi gratis gxin?
>> Lernanto: [inaudibles].
>> Parolanto 1: inserciones ne?
Multekosta plu.
Do inserciones potenciale povus ankoraŭ esti konstanta tempo, eĉ se via datumoj
strukturo similas tiun, tabelo de montriloj, ĉiu el kiuj estas indik
potenciale ligillisto.
Kiel vi povis atingi konstanto tempo inserción de nomoj?
Trae en la antaŭa, ĉu ne?
>> Se ni oferas dezajnon golo de antaŭe, kie ni volis subteni
ĉies nomon, ekzemple, ordo, aŭ ĉiuj el la numeroj en la scenejo ordo,
supozu ke ni havas unsorted ligitaj listo.
Ĝi nur kostas al ni unu aŭ du paŝojn, kiel en la kazo de Ben kaj Brian
antaŭe, por enmeti ero ĉe la komenco de la listo.
Do, se ni ne zorgas pri ordiga ĉiuj de la nomoj komencante kun A aŭ ĉiuj
la nomoj komencante kun B, ni povas ankoraŭ atingi konstanta tempo inserción.
Nun suprenrigardinte Alico aŭ Bob aŭ ajna nomo pli ĝenerale estas ankoraŭ kio?
Estas granda O de n dividita de 26, en la ideala kazo kie ĉiuj estas unuforme
distribuita, kie ekzistas tiom da A kiel estas Z, kiu verŝajne estas
nerealisma.
Sed tio ankoraŭ lineara.
>> Sed ĉi tie, ni revenu al la punkto de asimptota skribmaniero esti
teorie vera.
Sed en la reala mondo, se mi pretendas, ke mia programo povas ion fari 26 fojoj
rapida ol la via, kies programo vi intencas preferas uzi?
Via aŭ mia, kiu estas 26 fojoj pli rapida?
Realisme, la persono kies estas 26 fojojn pli rapide, eĉ se teorie
nia algoritmoj kuri en la sama asimptota rula tempo.
>> Permesu al mi proponi malsamajn solvo entute.
Kaj se tio ne blovu via menso, ni estas el datumstrukturoj.
Do tiu estas ĝin trie -
speco de stultan nomon.
Ĝi devenas retrievals, kaj la vorto estas literumita trie, t-r-i-kaj, pro
Kompreneble reakiro sonas trie.
Sed tio estas la historio de la vorto trie.
>> Do trie ja estas ia arbo, Kaj ĝi estas ankaŭ ludo de tiu vorto.
Kaj eĉ se vi ne povas sufiĉe vidu kun ĉi videbligo, en trie estas
arbo strukturitaj, kiel familio arbo kun unu praulo al la kapo kaj multaj
de nepoj kaj pranepoj kiel ĝi lasas sur la fundo.
Sed ĉiu nodo en trie estas tabelo.
Kaj ĝi estas en tabelo - kaj Ni oversimplify dum momento - ĝi estas
tabelo, en ĉi tiu kazo, de amplekso 26, kie ĉiu nodo denove estas tabelo de grandeco
26, kie la nula ero en tiu tabelo reprezentas A, kaj la lasta
elemento en chiu tia tabelo reprezentas Z.
>> Do mi proponas, do, ke ĉi datumoj strukturo, konata kiel trie, povas esti
uzata ankaŭ por stoki vortoj.
Ni vidis antaŭ momento kiel povus stoki vortoj, aŭ en ĉi tiu kazo nomojn, kaj ni
vidis antaŭe kiel ni povas stoki nombroj, sed se ni enfokusigi nomoj aŭ kordoj
ĉi tie, rimarki kio estas interesa.
Mi asertas ke la nomo de Maxwell estas ene de ĉi datumstrukturo.
Kie vi vidas Maxwell?
>> Lernanto: [inaudibles].
>> Parolanto 1: Maldekstre.
Do kio estas interesa kun ĉi datumoj strukturo estas iom ol tendencas la
kordo M-Al-X-W-E-L-L backslash nulo, ĉiuj contiguously, kion vi anstataŭ fari
sekvas.
Se ĉi tiu estas trie kiel datumstrukturo, ĉiu el kies verticoj estas denove tabelo,
kaj vi volas konservi Maxwell, vi unue indekso kaj do la radiko de nodo, tial
paroli, la plejsupra nodo, ĉe situo M, dekstra, do
proksimume en la mezo.
Kaj tiam el tie, vi sekvu la puntero al infanaj verticoj, por tiel diri.
Do, en la familio arbo senso, vi lin sekvas sube.
Kaj tio kondukas vin al alia nodo sur la maldekstra, kiu estas
nur alia tabelo.
>> Kaj poste se vi volas konservi Maxwell, vi trovos la puntero kiu reprezentas
A, kio estas ĉi tie.
Tiam vi iros al la sekva nodo.
Kaj avizo - tiu ĉi estas kial la bildon de iom trompanta -
tiu nodo rigardu super eta.
Sed al la rajto de ĉi tiu estas Y kaj Z. Ĝi estas nur la aŭtoro detranĉis la
bildo por ke vi efektive vidi tion.
Alie ĉi tiu bildo Estus ege larĝa.
Do nun vi indekson en situo X, tiam W, tiam E, tiam L, tiam L. Tiam kio estas
ĉi vidindaĵo?
>> Nu, se ni uzas ĉi tia nova alpreni kiel memori ĉenon en
datumstrukturo, vi ankoraŭ bezonas esence kontroli ekstere en la datumoj
strukturo ke vorto finiĝas tie.
En aliaj vortoj, ĉiu el tiuj nodoj iel devas memori, ke ni
efektive sekvis ĉiuj de ĉi tiuj indikoj kaj estas lasante iom
pano panero ĉe la malsupro de ĉi tie strukturo indiki M-Al-X-W-E-L-L estas
ĝuste en ĉi tiu datumstrukturo.
>> Do ni povus fari tion jene.
Ĉiu el la nodoj en la bildo kiun ni ĵus montaro havas unu, tabelo de amplekso 27.
Kaj estas nun 27, ĉar en p metis ses, ni vere donas al vi apostrofo,
do ni povas havi nomojn kiel O'Reilly kaj aliaj kun apostrofoj.
Sed sama ideo.
Ĉiu de ĉi tiuj elementoj en la tabelo notas al struct
nodo, tial nur nodo.
Do tiu estas tre memorigas de nia ligillisto.
>> Kaj tiam mi havas Bulea, kiun Mi instruos vin voki vorto, kiu estas ĝuste tuj estos
vera se vorto finas en tiu nodo en la arbo.
Ĝi efektive reprezentas la malgrandan triangulo kiun ni vidis antaŭ momento.
Do, se vorto finas en tiu nodo en la arbo, tiu vorto kampo estos vera,
kiu koncepte kontrolanta malproksime, aŭ ni desegnante ĉi tiu triangulo, jes
estas vorto ĉi tie.
>> Do tiu estas trie.
Kaj nun la demando estas, kion estas lia rula tempo?
Ĉu granda O de n?
Ĉu io alia?
Nu, se vi n nomoj en ĉi datumoj strukturo, Maxwell esti nur unu el
ili, kio estas la rula tempo de enmeto aŭ trovo Maxwell?
Kio estas la rula tempo de enmeto de Maxwell?
Se tie estas n aliaj nomoj jam en la tablo?
Jes?
>> Lernanto: [inaudibles].
>> Parolanto 1: Jes, ĝi estas la longo de la nomo, ĉu ne?
Do M-a-x-w-e-l-l tiel sentas kiel tiu algoritmo estas granda a de sep.
Nun, kompreneble, la nomo estos varii de longitudo.
Eble estas mallonga nomo.
Eble estas pli longa nomo.
Sed kio estas ŝlosilo estas, ke ĝi estas konstanta nombro.
Kaj eble ĝi ne estas vere konstanto, sed dio, se realisme, en
vortaro, estas probable iu limo pri la nombro de literoj en
persono nomon en aparta lando.
>> Kaj tial ni povas supozi ke valoro estas konstanta.
Mi ne scias kion ĝi estas.
Estas probable pli granda ol ni pensas ĝi estas.
Ĉar ĉiam iu angulo kazo kun freneza longa nomo.
Do ni nomas ĝin k, sed estas ankoraŭ konstanta supozeble, ĉar ĉiu
enoficigi en la mondo, almenaŭ en aparta lando, estas ke longo aŭ
mallonga, do ĝi estas konstanto.
Sed kiam ni diras ion aĝas Ho de konstanta valoro, kio estas tio
vere ekvivalenta al?
Tio estas vere la sama afero kiel dirante konstanta tempo.
>> Nun ni estas speco de kaptiloj, ĉu ne?
Ni estas speco de utiligante iuj teorio tie por diri, ke bone, komisio de k estas
vere nur petita de unu, kaj estas konstanta tempo.
Sed vere estas.
Ĉar la ŝlosilo komprenon tie estas ke se ni n nomoj jam en ĉi tiu
datumstrukturo, kaj ni insert Maxwell, estas la kvanto de tempo nin portas
enŝovu Maxwell tute tuŝitaj por kiel multaj aliaj personoj
estas en la datumstrukturo?
Ne ŝajnas esti.
Se mi havus unu miliardo pli elementoj al ĉi tiu trie, kaj poste enigi Maxwell, estas
li tute tuŝita?
No
Kaj tio estas malsimila al ĉiu de la tago datumoj strukturoj kiujn ni vidis ĝis nun, kie
la rula tempo de via algoritmo estas tute sendepende de kiom
aĵoj estas aŭ ne estas jam en tiu datumstrukturo.
>> Kaj tial kun ĉi havigas al vi nun estas ŝanco por p aro ses, kiuj volas
denove impliki apliki vian propran ortografia kontrolilo, legante en 150.000
vortoj, kiel plej bone stoki ke ne estas nepre evidentaj.
Kaj kvankam mi aspiris trovi the Holy Grail, mi ne
laŭ kiuj trie estas.
Fakte, hash tablo povas tre bone pruvi al esti multe pli efika.
Sed tiuj estas nur -
tio estas nur unu el la decidoj de dezajno vi devos fari.
>> Sed en fermi ni prenu 50 aŭ tiel sekundoj preni peek je kio kuŝas
antaŭen proksima semajno kaj preter ni transiro el tiu komandlinio
mondo se C programoj al aĵoj retejo starigi kaj lingvoj kiel PHP kaj
JavaScript kaj la interreto mem, protokoloj kiel HTTP, kion vi havas
memkompreneble, dum jaroj nun, kaj tajpita plej ĉiu
tago, eble, aŭ vidis.
Kaj ni komencos ŝelo redonas la tavoloj de kio estas la interreto.
Kaj kio estas la kodo kiu kuŝas sub la hodiaŭa iloj.
Do 50 sekundoj de ĉi teaser tie.
Mi donas al vi Soldatoj de la Reto.
>> [VIDEO reprodukto]
>> -Li venis kun mesaĝo.
Kun protokolo ĉiuj liaj propraj.
Li venis al mondo de kruela cortafuegos, uncaring routers, kaj danĝeroj malproksime
pli malbona ol morto.
Li estas rapida.
Li estas forta.
Li estas TCPIP.
Kaj li havas vian adreson.
Soldatoj de la Reto.
>> [FINO reprodukto de vídeo]
>> Parolanto 1: Tio estas kiel la interreto gxi funkcios ekde proksima semajno.