>> Tagapagsalita 1: Ang lahat ng mga karapatan, kaya hindi namin pabalik.
Maligayang pagdating sa CS50.
Ito ang katapusan ng linggo pitong.
Kaya isipin ang na huling panahon, nagsimula kaming tumitingin sa bahagyang mas sopistikadong
data istraktura.
Dahil hanggang ngayon, ang lahat ng nagkaroon kami talaga sa aming pagtatapon ay ito, isang array.
>> Ngunit bago namin itapon ang mga array bilang hindi lahat ng mga kagiliw-giliw na, na sa katunayan ito
talaga ay, kung ano ang ilan sa mga plus ito ng simpleng data
istraktura kaya ngayon?
Ano ang mahusay na ito sa?
Sa ngayon bilang namin ang iyong nakita?
Ano ang nakukuha mo?
Walang anuman.
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Ano iyon?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Fixed laki.
OK, kaya kung bakit ay nakapirming laki mahusay na bagaman?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: OK, kaya mahusay sa ang pakiramdam na maaari kang magtalaga ng isang
nakapirming halaga ng puwang, na sana ay ay tumpak na bilang magkano
space hangga't gusto mo.
Kaya na maaaring maging ganap ng plus.
>> Ano ang isa pang up bahagi ng isang array?
Oo?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Lahat ng mga - paumanhin?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Ang lahat ng mga kahon sa memory o sa tabi ng bawat isa.
At iyan ay kapaki-pakinabang - bakit?
Iyan ay medyo totoo.
Ngunit paano namin maningning na tagumpay na katotohanan?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Mismong, maaari naming subaybayan ang mga kung saan lahat ng bagay ay sa pamamagitan lamang ng pag-alam
isang address, lalo na sa address ng unang byte ng na tipak ng memory.
O sa kaso ng mga string, ang address ng unang
pansamantalang trabaho sa na string.
At mula doon, maaari naming makita sa dulo ng string.
Maaari naming mahanap ang pangalawang elemento, ang ikatlong elemento, at iba pa.
>> At kaya ang magarbong paraan ng naglalarawan na tampok ay na array bigyan kami ng
random access.
Lamang sa pamamagitan ng paggamit ng mga square bracket pagtatanda at isang numero, maaari mong tumalon sa
isang tukoy na elemento sa array sa pare-pareho ang oras, malaki O
ng isa, kaya na magsalita.
>> Ngunit mayroong nangyaring ng ilang mga downsides.
Ano ang isang array hindi gawin napaka madali?
Ano itong hindi magandang sa?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Ano iyon?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Pagpapalawak sa laki.
Kaya ang downsides ng array ay tumpak ang katapat ng kung ano ang
upsides ay.
Kaya ang isa sa mga downsides ay na ito ay isang nakapirming laki.
Kaya hindi ikaw talaga ay maaaring lumaki ito.
Maaari mong reallocate ng mas malaking tipak ng memorya, at pagkatapos ay ilipat ang mga lumang mga elemento
sa bagong array.
At pagkatapos ay libre sa lumang array, para sa Halimbawa, sa pamamagitan ng paggamit malloc o isang katulad na
function na tinatawag na realloc, na reallocates memory.
>> Realloc, bilang isang tabi, sinusubukan upang bigyan ka ng memorya na katabi ng array
na mayroon ka.
Ngunit maaari itong ilipat ang mga bagay sa paligid nang sama-sama.
Ngunit sa maikling salita, na mahal, tama?
Dahil kung mayroon kang isang tipak ng memorya ng sukat na ito, ngunit gusto mo talagang isa
na ganito ang laki, at nais mong panatilihin ang ang orihinal na mga elemento, mayroon kang
halos isang oras linear proseso ng pagkopya na kailangang mangyari mula sa
lumang array sa bagong.
At ang katotohanan ay humihingi sa operating sistema muli at muli at
muli para malaki chunks ng memorya maaaring magsimula upang magdulot sa iyo ng ilang oras pati na rin.
Kaya ito ay pareho ng isang pagpapala at isang sumpa sa magkaila, ang katunayan na ang mga array
ng mga nakapirming laki.
Ngunit kung namin ipakilala sa halip ng isang bagay tulad nito, na kung saan namin na tinatawag na naka-link
listahan, kumuha kami ng ilang upsides at ang ilang mga downsides dito pati na rin.
>> Kaya naka-link na listahan ay isang simpleng data istraktura na binubuo ng C structs ito sa
kaso, kung saan ang isang struct, isipin ang, ay lamang isang lalagyan para sa isa o higit pang mga tiyak na
mga uri ng variable.
Sa kasong ito, kung ano ang ginagawa ng mga uri ng data lumitaw na maging sa loob ng struct na
huling beses namin na tinatawag na node?
Ang bawat isa sa mga parihaba ay isang node.
At bawat isa sa mga mas maliit na parihaba sa loob nito ay isang uri ng data.
Anong mga uri ay sinasabi namin sila ay sa Lunes?
Oo?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Ang isang variable at isang pointer, o higit na partikular, sa isang int, para sa n,
at isang pointer sa ibaba.
Pareho sa mga mangyari na maging 32 bit, sa hindi bababa sa isang computer tulad nito CS50
Appliance, at sa gayon ang mga ito ay iguguhit nang pantay-pantay sa laki.
>> Kaya kung ano ang ginagamit mo ang pointer kahit na para sa malas?
Bakit idagdag ang arrow na ngayon kapag array ay kaya maganda at malinis at simple?
Ano ang pointer ng paggawa para sa sa amin sa bawat isa sa mga node?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Mismong.
Ito ay nagsasabi sa iyo kung saan sa susunod na isa ay.
Kaya ako uri ng gamitin ang pagkakatulad ng gamit ang isang thread upang ayusin ng
Thread mga node magkasama.
At iyon mismo kung anong ginagawa namin sa payo dahil bawat isa sa mga
chunks ng memorya ay maaaring o hindi maaaring magkadikit, bumalik upang i-back-back
sa loob ng RAM, dahil sa bawat oras na tumawag malloc sinasabi, akong bigyan ng sapat na
bytes para sa isang bagong node, maaari itong maging dito o maaari itong maging dito.
Maaaring maging dito.
Ikaw lamang ay hindi alam.
>> Ngunit gamit ang mga payo sa mga address ng mga mga node, maaari mong tahiin ang mga ito
magkasama sa isang paraan na mukhang biswal tulad ng isang listahan kahit na ang mga bagay na ito ay
lahat maikalat sa buong iyong isa o iyong dalawa o apat ang iyong gigabytes ng RAM
sa loob ng iyong sariling computer.
>> Kaya ang downside, pagkatapos, ng isang naka-link na ang listahan ng kung ano?
Ano ang isang presyo na namin tila nagbabayad?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Higit pang mga puwang, tama?
Kami, sa kasong ito, Dinoble ang halaga ng espasyo dahil hindi namin nawala
mula sa 32 bits para sa bawat node, para sa bawat int, kaya ngayon 64 bits dahil mayroon kaming upang
panatilihin sa paligid ng isang pointer pati na rin.
Makakuha ka ng mas maraming kahusayan kung ang iyong struct ay mas malaki kaysa ito simpleng bagay.
Kung ang iyong aktwal na magkaroon ng isang mag-aaral sa loob na kung saan ay isang pares ng mga string para sa
pangalan at bahay, marahil ng isang ID number, marahil ilang mga iba pang mga patlang sama-sama.
>> Kaya kung mayroon kang isang malaking sapat struct, pagkatapos siguro ang gastos ng pointer ay
Hindi tulad ng isang malaking pakikitungo.
Ito ay isang bit ng isang kaso sa sulok na kami ay pag-iimbak tulad ng isang simpleng primitive
sa loob ng nakaugnay sa listahan.
Ngunit ang punto ay pareho.
Talagang ka gumagastos higit pa memorya, ngunit nakakakuha ka ng
kakayahang umangkop.
Dahil ngayon kapag gusto kong magdagdag ng isang elemento sa simula ng listahan na ito,
Mayroon akong upang magtalaga ng isang bagong node.
At mayroon akong upang i-update lamang ang mga mga arrow sa paanuman lamang sa pamamagitan ng paglipat ng
ilang mga payo sa paligid.
>> Kung gusto kong magpasok ng isang bagay sa gitna ng listahan, hindi ko kailangang mag-
itulak lahat ng tao bukod tulad ng ginawa namin sa linggo 'nakaraan sa aming mga boluntaryo sino
kinakatawan ng isang array.
Maaari ko lang ang magtalaga ng isang bagong node at pagkatapos lamang ituro ang mga arrow sa
iba't ibang direksyon dahil ito ay hindi kailangang manatili sa aktwal na
memorya ng tunay na linya tulad ko na iginuhit ito dito sa screen.
>> At pagkatapos ay bilang wakas, kung gusto mong isingit isang bagay sa dulo ng listahan, ito ay
mas madali.
Ito ay isang uri ng arbitrary notation, ngunit 34 ang pointer, kumuha nang isang hula.
Ano ang halaga ng kanyang pinaka-pointer malamang iginuhit uri ng tulad ng isang lumang
paaralan antena doon?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Ito ay marahil null.
At tunay nga na isang may-akda representasyon ng null.
At ito ay walang bisa dahil kung talagang kailangan mong malaman kung saan ang dulo ng isang naka-link na
ang listahan, baka panatilihin kang sumusunod at pagsunod at pagsunod sa mga arrow na ito
sa ilang mga basura na halaga.
Kaya null ay magpahiwatig na walang higit pang mga nodes sa kanan ng numero 34,
sa kasong ito.
>> Kaya naming imungkahi na maaari naming ipatupad ito node sa code.
At nakakita kami uri na ito syntax ng bago.
Typedef lamang tumutukoy sa isang bagong uri para sa amin, nagbibigay sa amin ng isang kasingkahulugan tulad ng
string ay para sa pansamantalang trabaho *.
Sa kasong ito, ito ay pagpunta sa magbibigay sa amin shorthand notation sa gayon ay struct node
Maaari lamang sa halip na nakasulat bilang node, na kung saan ay marami mas malinis.
Ito ay isang maraming mas mababa maligoy.
>> Sa loob ng isang node ay tila isang int tinatawag n, at pagkatapos ay isang struct node *
na nangangahulugan nang eksakto kung ano ang gusto namin ang mga arrow upang sabihin, isang pointer sa isa pang
na node ng ang eksaktong parehong uri ng data.
At ipanukala ko na kami maaaring ipatupad ang search function na tulad nito, na sa
unang sulyap ay maaaring mukhang medyo kumplikado.
Ngunit sabihin makita ito sa konteksto.
>> Hayaan akong pumunta sa ibabaw ng mga appliance dito.
Hayaan akong magbukas ng isang file na tinatawag na listahan zero tuldok h.
At na naglalaman lamang ang kahulugan namin Nakita lamang ng ilang sandali ang nakalipas para sa data na ito
uri ng tinatawag na node.
Kaya namin inilagay ang mga iyon sa isang file na tuldok h.
>> At bilang isang tabi, kahit na ito programa na ikaw ay tungkol sa upang makita ang
hindi lahat na kumplikado, ito ay sa katunayan convention kapag sumusulat ng isang programa sa
maglagay ng mga bagay tulad ng mga uri ng data, upang hilahin constants minsan, sa loob ng iyong
header na file at hindi kinakailangan sa ang iyong mga file C, tiyak na kapag ang iyong
mga programa makakuha ng mas malaki at mas malaki, sa gayon ay alam mo kung saan upang tumingin para sa kapwa
dokumentasyon sa ilang mga kaso, o para sa mga pangunahing kaalaman tulad nito, ang
kahulugan ng ilang mga uri.
>> Kung ako ngayon buksan up listahan zero na tuldok c, mapapansin ang ilang mga bagay.
Kabilang dito ang ilang mga file header, pinaka- ng kung saan nasaksihan namin dati.
Kabilang dito ang kanyang sariling header file.
>> At bilang isang bukod, bakit na double quotes dito, bilang kabaligtaran sa mga anggulo
bracket sa linya na Ako nai-highlight doon?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Oo kaya ito ay isang lokal na file.
Kaya kung ito ay isang lokal na file ng iyong sarili dito on line 15, halimbawa, gamitin mo
ang double quote sa halip ng angled bracket.
>> Ngayon ito ay uri ng kawili-wiling.
Pansinin na aking ipinahayag isang pandaigdigang variable sa programang ito sa linya 18
tinatawag na unang, ang ideya pagiging ito ay pagpunta sa maging isang pointer sa unang
node sa aking naka-link na listahan, at ako ay nag nasimulan ito sa null, dahil nag ko
hindi inilaan anumang aktwal mga node pa lamang.
>> Kaya ito ay kumakatawan, pictorially, kung ano ang aming Nakita ng ilang sandali ang nakalipas sa larawan bilang
na pointer sa malayong iniwan bahagi.
Kaya ngayon, na pointer Walang isang arrow.
Ito ay sa halip lamang null.
Ngunit ito ay kumakatawan sa kung ano ang magiging address ng unang aktwal
node sa listahang ito.
Kaya naipatupad ko na ito ay isang pandaigdigang dahil, bilang makikita mo, ang lahat ng ito
programa ay sa buhay ay ipatupad naka-link na listahan para sa akin.
>> Ngayon Mayroon akong ilang mga modelo dito.
Ko nagpasya upang ipatupad ang mga tampok tulad ng pagtanggal, pagpapasok, paghahanap, at
traversal -
ang huling lamang pagiging lakad sa buong listahan, pag-print out nito elemento.
At ngayon, narito ang aking pangunahing routine.
At hindi namin gastusin ng masyadong maraming panahon sa dahil ang mga ito ay isang uri ng, sana
lumang sumbrero sa pamamagitan ng ngayon.
>> Pupunta ako sa gawin ang mga sumusunod, habang gumagamit ang cooperates.
Kaya isa, pupuntahan ko i-print out sa menu na ito.
At ko na format ito bilang nang malinis bilang ako ng dati.
Kung gumagamit ang mga uri sa isa, na nangangahulugan na gusto nilang tanggalin ang isang bagay.
Kung gumagamit ang mga uri sa dalawa, na nangangahulugan na gusto nilang magpasok ng isang bagay.
At iba pa.
Pupuntahan ko pagkatapos ay i-prompt pagkatapos ay para sa isang command.
At pagkatapos ay ako pagpunta sa gamitin GetInt.
>> Kaya ito ay isang talagang simple menuing interface kung saan mo na lang ay i-type ang
isang numero ng pagma-map sa isa ng mga utos.
At ngayon, mayroon akong isang masarap na malinis ang switch pahayag na pupuntahan lumipat sa
ano ang gumagamit na nai-type in
At kung sila ay nag-type ng isa, idedetalye ko call na tanggalin at masira.
Kung sila ay nag-type ng dalawa, idedetalye ko tumawag isingit at masira.
>> At ngayon mapansin Naglagay ako sa bawat sa mga ito sa parehong linya.
Ito ay lamang ng isang pangkakanyahan desisyon.
Karaniwan nakakita kami ng isang bagay ganito.
Ngunit ko lang napagpasyahan, lantaran, ang aking mga programa Tiningnan pa nababasa dahil
ito ay lamang apat na mga kaso sa maglista lamang ito tulad nito.
Ganap lehitimong paggamit ng estilo.
At ako pagpunta sa gawin ito hangga't ang gumagamit ay hindi nai-type zero, na kung saan ako
Nagpasya ang kahulugan ng nais nilang tumigil.
>> Kaya ngayon mapansin kung ano ako pagpunta sa gawin dito.
Pupunta ako sa magbakante ang listahan sa malas.
Ngunit higit pa sa na sa loob lamang ng ilang sandali.
Sabihin unang patakbuhin ang program na ito.
Kaya hayaan mo akong gumawa ng mas malaking terminal window, dot slash listahan 0.
Pupuntahan ko sige at ipasok sa pamamagitan ng pag-type ng dalawa, isang numero tulad ng 50, at ngayon
makikita mo ang listahan na ngayon 50.
At ang aking mga teksto lamang scrolled up ng isang bit.
Kaya ngayon mapansin ang listahan ay naglalaman ng ang bilang 50.
>> Natin gawin isa pang insert sa pamamagitan ng pagsasagawa ng dalawang.
Sabihin type ka sa numero tulad ng isa.
Listahan na ngayon ang isa, na sinusundan ng 50.
Kaya ito ay lamang ng isang tekstuwal representasyon ng listahan.
At sabihin magpasok ng isa pang numero tulad ng ang bilang 42, na sana ay
pagpunta sa mga end up sa gitna, dahil ang program na ito sa mga partikular na uri ito
elemento tulad ng mga pagpapasok sa kanila.
Kaya doon kami ay may ito.
Super simpleng programa na maaari talagang ginamit ang isang array, ngunit ko
nangyari mang gamit ang isang naka-link na listahan kaya lang ang maaari kong pabago-bago
lumalaki at pag-urong ito.
>> So sabihin kumuha ng isang hitsura para sa paghahanap, kung ako magpatakbo ng command tatlo, gusto kong maghanap
para sa, sabihin nating, ang bilang 43.
At walang ay tila natagpuan, dahil Nakatanggap ako pabalik walang tugon.
Kaya sabihin gawin ito muli.
Maghanap.
Sabihin sa paghahanap para sa 50, o sa halip maghanap para sa 42, na may isang maganda
maliit na banayad na kahulugan.
At nakita ko ang kahulugan ng buhay doon.
Number 42, kung hindi mo alam ang sanggunian, ang Google ito.
Ayos lang.
Kaya kung ano ang program na ito tapos para sa akin?
Ito lamang ang pinapayagan sa akin upang ipasok kaya malayo at paghahanap para sa mga sangkap.
>> Sabihin fast forward, pagkatapos, upang na function na namin glanced sa
sa Monday bilang isang teaser.
Kaya ito function, inaangkin ko, mga paghahanap para sa isang elemento sa listahan sa pamamagitan ng unang
isa, pagdikta sa gumagamit at pagkatapos ay pagtawag GetInt upang makakuha ng isang aktwal na int
na nais mong maghanap para sa.
>> Pagkatapos mapansin ito.
Pupunta ako upang lumikha ng isang pansamantalang variable sa line 188 pointer na tinatawag na -
PTR -
sana tinatawag na ito kahit ano.
At ito ay isang pointer sa isang node dahil sinabi ko node * doon.
At ako Sinisimulan ito upang maging katumbas ng una kaya ko na epektibo ang aking
daliri, kaya na magsalita, sa pinakadulo unang elemento ng listahan.
Kaya kung ang aking kanang kamay dito ay PTR ako pagturo sa parehong bagay na una
ay tumuturo sa.
>> Kaya ngayon bumalik sa code, kung ano ang susunod na mangyayari -
ito ay isang pangkaraniwang tularan kapag iterating sa ibabaw ng isang istraktura tulad ng isang
naka-link na listahan.
Pupunta ako sa gawin ang mga sumusunod habang pointer ay hindi katumbas ng null Kaya habang
ang aking daliri ay hindi tumuturo sa ilang mga null halaga, kung ang pointer ng arrow n katumbas n.
Susubukan naming mapansin muna na n ay kung ano ang gumagamit na nai-type sa bawat GetInts tumawag dito.
>> At pointer arrow n ibig sabihin kung ano?
Well kung pumunta kami pabalik sa mga larawan dito, kung mayroon akong isang daliri na nakaturo sa
na unang node na naglalaman ng siyam, ang arrow mahalagang ay nangangahulugan na pumunta sa na
node at grab ang mga halaga sa lokasyon n, sa kasong ito, ang data ng patlang na tinatawag n.
>> Bilang isang tabi - at nakita natin ito ng ilang ng mga linggo na nakalipas kapag may isang taong nagtanong -
syntax na ito ay bago, ngunit hindi bigyan kami ng mga kapangyarihan na namin
ay hindi mayroon.
Ano ang katumbas na parirala sa paggamit dot notation at bituin ng dalawang
ng mga linggo na nakalipas kapag kami peeled likod ang layer na ito ng kaunti maaga?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Mismong, ito ay bituin, at pagkatapos ito ay bituin tuldok n, may
panaklong dito, na kamukha, lantaran, tingin ko ng maraming
mas misteriyoso na basahin.
Ngunit star pointer, gaya ng lagi, Nangangahulugan ang pumunta doon.
At sa sandaling nandoon ka, kung ano ang data field ang gusto mong i-access?
Well mong gamitin ang tuldok notasyon upang ma-access structs isang patlang ng data, at ako
partikular, gusto n.
>> Nang tapat, Gusto ko magtaltalan na ito lamang ang mas mahirap basahin.
Ito ay mas mahirap matandaan kung saan huwag ang mga panaklong pumunta, ang
bituin at lahat ng iyon.
Kaya mundo ang nagpatibay ng ilang mga sintaktik asukal, kaya na magsalita.
Lamang ng isang sexy paraan ng sinasabi, ito ay katumbas ng, at
marahil mas madaling maunawaan.
Kung pointer ay talagang isang pointer, ang arrow pagtatanda paraan pumunta doon at mahanap
ang patlang sa kasong ito na tinatawag n.
>> Kaya kung makita ko ito, mapapansin kung ano ang ginagawa ko.
Ko lang i-print out, nakita akong porsiyento i, i-plug in ang halaga para sa na int.
Tinatawag kong matulog para sa isang segundo lamang sa uri i-pause ng mga bagay sa screen upang
bigyan ang gumagamit ng isang pangalawang na maunawaan kung ano lamang ang nangyari.
At pagkatapos ay ako masira.
Kung hindi, ano ang gagawin ko?
I-update ang pointer sa pantay na pointer ng arrow sa tabi.
>> Kaya lamang maging malinaw, ang ibig sabihin nito pumunta doon, gamit ang aking lumang-paaralan pagtatanda.
Kaya ito ay nangangahulugan lamang na pumunta sa kahit anong ka na tumuturo sa, na sa pinakasentro
unang kaso ay ako na nakaturo sa ang struct may siyam sa loob nito.
Kaya ko na nawala doon.
At pagkatapos ay ang tuldok ay nangangahulugan notation, makuha ang halaga sa susunod.
>> Ngunit ang halaga, kahit na ito ay iguguhit bilang isang makitid, lamang ang isang numero.
Ito ay isang numerong address.
Kaya ang isang linya ng code, kung nakasulat na tulad nito, mas misteriyoso
paraan, o ganito, ang bahagyang higit pa madaling gamitin na paraan, nangangahulugan lamang ilipat ang aking mga kamay
mula sa unang node sa susunod na isa, at pagkatapos ay sa susunod na isa, at pagkatapos ay ang
susunod na isa, at iba pa.
>> Kaya hindi namin tumira sa kabilang pagpapatupad ng isingit at tanggalin
at traversal, ang unang dalawa sa na kung saan ay medyo kasangkot.
At sa tingin ko ito ay medyo madali upang makakuha ng mawawala kapag ginagawa ito sa bibig.
Ngunit kung ano ang maaari naming gawin dito ay subukan upang matukoy kung paano
pinakamahusay na gawin ito biswal.
Dahil nais kong imungkahi na kung namin nais upang ipasok elemento sa ito
umiiral na listahan, na May limang mga sangkap -
9, 17, 22, 26, at 33 -
kung saan ako pagpunta sa ipatupad ito sa code, kailangan ko upang isaalang-alang kung paano pumunta
tungkol sa paggawa nito.
>> At Gusto ko iminumungkahi ng pagkuha hakbang na sanggol kung saan, sa kasong ito Ibig kong sabihin, kung ano ang mga
ang mga posibleng mga sitwasyon na namin maaaring makaharap sa pangkalahatan?
Kapag ang pagpapatupad ng insert para sa isang naka-link na listahan, ito lamang ang mangyayari na maging isang
tiyak na halimbawa ng laki ng limang.
Well kung gusto mong ipasok ang isang numero, gustong sabihin ang bilang ng isa, at
pagpapanatili pinagsunod-sunod-sunod, kung saan malinaw naman ang ipinapakita ng numero ng isa upang
pumunta sa ang partikular na halimbawa?
Nagustuhan sa simula.
>> Ngunit kung ano ang kawili-wiling mayroong na kung gusto mong isingit ang isa sa na ito
listahan, kung ano ang mga espesyal na pangangailangan pointer ma-update sa malas?
Una.
Kaya Gusto ko magtaltalan, ito ang unang kaso na maaari naming isaalang-alang, isang
sitwasyong kinasasangkutan ng pagpasok sa sa simula ng listahan.
>> Sabihin pumitas off siguro bilang isang madaling o kahit mas madali ang kaso, relatibong pagsasalita.
Ipagpalagay na gusto kong ipasok ang numero 35 sa pinagsunod-sunod-sunod.
Ito ay malinaw naman ay kabilang banda roon.
Kaya kung ano ang pointer ay malinaw naman pagpunta sa kailangang ma-update sa na sitwasyon?
34 pointer ng pagiging hindi null ngunit ang mga address ng struct
na naglalaman ng mga numero 35.
Kaya iyon ang kaso dalawa.
Kaya pa, ako uri ng quantizing kung magkano gumana kailangan kong gawin dito.
>> At sa wakas, ang kaso halata gitna ay sa katunayan, sa gitna, kung gusto kong
magpasok ng isang bagay tulad ng halimbawa 23, na napupunta sa pagitan ng 23 at 26 ang, ngunit
ngayon ang mga bagay makakuha ng kaunti pa kasangkot dahil ano
payo kailangang baguhin?
Kaya 22 malinaw naman kailangang mabago dahil hindi siya maaaring tumuro sa 26 na ngayon.
Siya ay kailangang ituro sa bagong node na Kukuha ako upang maglaan sa pamamagitan ng pagtawag
malloc ilan o katumbas.
>> Ngunit pagkatapos ay ako din kailangan na bagong node, 23 sa kasong ito, upang magkaroon nito pointer
pagturo sa kanino?
26.
At mayroong pagpunta sa maging isang pagkakasunud-sunod ng mga operasyon dito.
Dahil kung gagawin ko ito maloko, at ako halimbawa simula sa simula ng
ang listahan, at ang aking layunin ay upang ipasok 23.
At check ko, ang ibig nabibilang dito, malapit siyam?
Hindi.
Gumagana ba ito nabibilang dito, sa tabi ng 17?
Hindi.
Gumagana ba ito ay kabilang dito sa tabi ng 22?
Oo.
>> Ngayon kung ako ungas dito, at hindi pag-iisip na ito sa pamamagitan, maaari ko
magtalaga ng aking bagong node para sa 23.
Maaari kong i-update ang pointer mula sa node ang tinatawag na 22, na nakaturo
ito sa bagong node.
At pagkatapos ay kung ano ang kailangan kong i-update pointer sa bagong node upang maging?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Mismong.
Pagturo sa 26.
Ngunit dammit kung hindi ko na-update 22 ni pointer upang ituro sa tao na ito, at
ngayon Mayroon akong orphan, ang natitira ng listahan, kaya na magsalita.
Kaya pagkakasunud-sunod ng mga operasyon dito ay magiging mahalaga.
>> Upang gawin ito kaya kong magnakaw, sabihin nating, anim na mga boluntaryo.
At sabihin makita kung hindi namin maaaring gawin ito biswal sa halip ng code-matalino.
At kami ay may ilang mga kaibig-ibig ng stress bola para sa iyo ngayong araw.
OK, kung paano tungkol sa isa, dalawa, sa bumalik - sa dulo doon.
tatlo, apat, pareho ng sa iyo guys sa dulo.
At lima, anim.
Oo naman.
Limang at anim.
Ang lahat ng mga karapatan at kami ay sa iyo guys susunod na pagkakataon.
Ang lahat ng mga karapatan, dumating sa up.
>> Ang lahat ng mga karapatan, dahil ikaw ay hanggang dito muna, Gusto mo bang maging ang isa awkwardly
sa Google Glass dito?
Ang lahat ng mga karapatan, sa gayon, OK, Glass, record ng video.
OK, ikaw ay handa na upang patakbuhin.
>> Ang lahat ng mga karapatan, kaya kung ikaw guys ay maaaring dumating sa ibabaw dito, ako handa nang maaga
ilang numero.
Ang lahat ng mga karapatan, darating sa paglipas dito.
At bakit hindi ka pumunta ng kaunti higit na paraan.
At sabihin makita, kung ano ang iyong pangalan, gamit ang Google Glass?
>> MAG-AARAL: Ben.
>> Tagapagsalita 1: Ben?
OK, Ben, ikaw ang magiging unang, literal.
Kaya kami ay pagpunta sa magpadala sa iyo sa dulo ng entablado.
Ang lahat ng mga karapatan, at ang iyong pangalan?
>> MAG-AARAL: Jason.
>> Tagapagsalita 1: Jason, OK bibigyan ka maging numero siyam.
Kaya kung nais mong sundin Ben na paraan.
>> MAG-AARAL: Jill.
>> Tagapagsalita 1: Jill, ikaw ay pagpunta sa maging 17, na kung Gusto ko nagawa ito nang higit pa
intelligently, nais kong magkaroon Magsimula sa kabilang dulo.
Pumunta ka na paraan.
22.
At ikaw?
>> MAG-AARAL: Mary.
>> Tagapagsalita 1: Mary, magiging 22.
At ang iyong pangalan ay?
>> MAG-AARAL: Chris.
>> Tagapagsalita 1: Chris, magiging 26.
At bilang wakas pagkatapos.
>> MAG-AARAL: Diana.
>> Tagapagsalita 1: Diana, magiging 34.
Kaya dumating ka sa paglipas dito.
>> Ang lahat ng mga karapatan, kaya maperpekto pinagsunod-sunod mag-order na.
At sabihin sige at gawin ito sa gayon maaari naming talaga -
Ben handa ka lamang uri ng hinahanap out sa wala kahit saan doon.
OK, kaya sabihin sige at ilarawan ito paggamit ng mga armas, tulad ng ako ay, eksakto,
ano ang nangyayari sa.
Kaya't sige at bigyan ang inyong sarili ng isang paa o dalawang sa pagitan ng inyong sarili.
At sige at ituro sa isa kamay upang kung sinuman ang dapat mong i-pagturo sa
batay sa mga ito.
At kung ikaw ay walang bisa lamang ituro ang diretso pababa sa sahig.
OK, kaya mabuti.
>> Kaya ngayon kami ay may isang naka-link na listahan, at ipaalam sa akin ipanukala na kailangan ko i-play ang papel na ginagampanan ng
PTR, kaya hindi ako ay mag-abala nagdadala ito sa paligid.
At pagkatapos ay - isang tao nakababagod convention - Maaari kang tumawag ito anumang bagay na gusto mo -
hinalinhan pointer, pointer pred -
ito lamang ay ang palayaw na binigay namin sa aming sample code sa aking kaliwang kamay.
Ang iba pang mga kamay na pagpunta sa ma-pagpapanatiling subaybayan ng kung sino sino ay sa
sumusunod na mga sitwasyon.
>> Kaya ipagpalagay, una, gusto kong i-off ang lakas ng loob na ang unang halimbawa ng pagpasok, sabihin
20, sa listahan.
Kaya pupuntahan ko kailangan ng isang tao upang isama ang numero ng 20 para sa amin.
Kaya kailangan kong mag-malloc isang tao mula sa madla.
Halika sa up.
Ano ang inyong pangalan?
>> MAG-AARAL: Brian.
>> Tagapagsalita 1: Brian, lahat ng karapatan, kaya mo ang magiging node na naglalaman ng 20.
Ang lahat ng mga karapatan, darating sa paglipas dito.
At malinaw naman, kung saan Brian ay nabibilang?
Kaya, sa gitna ng - talaga, maghintay ng isang minuto.
Ginagawa namin ito out sa pagkakasunud-sunod.
Gumagawa kami ng ito ng maraming mas mahirap kaysa sa kinakailangan nito upang maging sa unang.
OK, kami ay pagpunta sa libreng Brian at realloc Brian bilang lima.
>> OK, kaya ngayon gusto naming isingit Brian bilang lima.
Kaya dumating sa paglipas dito sa tabi ng Ben para lamang ng ilang sandali.
At maaari mong marahil sabihin kuwento kung saan ito ay pagpunta.
Ngunit sabihin isip-isipin ang pagkakasunud-sunod ng mga operasyon.
At ito ay tiyak ang visual na pupuntahan pumila
may sample na code.
Kaya dito ko pa PTR pagturo sa una hindi sa Ben, per se, ngunit sa kahit anong
Pinahahalagahan siya ay naglalaman, na sa kasong ito ay - kung ano ang iyong pangalan muli?
>> MAG-AARAL: Jason.
>> Tagapagsalita 1: Jason, kaya pareho Ben at ako ay tumuturo sa Jason sa panahon na ito.
Kaya ngayon mayroon akong upang matukoy, kung saan ay Brian nabibilang?
Kaya ang tanging bagay Mayroon akong access sa ngayon ay ang kanyang mga item n data.
Kaya pupuntahan ko check, ay Brian mas mababa sa Jason?
Ang sagot ay totoo.
>> Kaya kung ano ngayon ay kailangang mangyari, sa tamang pagkakasunud-sunod?
Kailangan kong i-update ang kung gaano karaming mga payo sa kabuuan sa kuwentong ito?
Saan ang aking mga kamay ay pa rin sa pagturo Jason, at ang iyong mga kamay - kung nais mong
ilagay ang iyong mga kamay tulad ng, uri ng, ko hindi alam, isang tandang pananong.
OK, mabuti.
>> Ang lahat ng mga karapatan, sa gayon mayroon kang ng ilang mga kandidato.
Alinman sa Ben o ako o Brian o Jason o ang iba, na
payo kailangang baguhin?
Gaano karaming sa kabuuang?
>> OK, kaya dalawa.
Aking pointer ay hindi talagang mahalaga ngayon dahil ako lamang pansamantalang.
Kaya ito ay ang dalawang guys, siguro, parehong Ben at Brian.
Kaya ipaalam sa akin imungkahi na-update namin Ben, dahil siya ang unang.
Ang unang elemento ng listahang ito ngayon ay pagpunta sa maging Brian.
Kaya Ben punto sa Brian.
OK, ngayon kung ano?
>> Sino ang makakakuha ng tulis sa kanino?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: OK kaya Brian ay upang ituro sa Jason.
Ngunit na Nawala ko ang track na ng pointer?
Ko alam kung saan ay Jason?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: gagawin ko, dahil ako ang pansamantalang pointer.
At siguro, hindi ko pa nabago upang ituro sa mga bagong node.
Kaya maaari naming simpleng Brian punto sa kung sinuman ako na tumuturo sa.
At tapos na kami.
Kaya isa kaso, sa pagpapasok ng simula ng listahan.
Mayroong dalawang pangunahing mga hakbang.
Ang isa, mayroon kaming upang i-update Ben, at pagkatapos ay kami ay mayroon ding upang i-update Brian.
At pagkatapos ay hindi ko na kailangang mag-abala traipsing sa pamamagitan ng ang natitirang bahagi ng
listahan, dahil kami ay natagpuan ang kanyang lokasyon, dahil siya ay pag-aari ng
kaliwa ng unang elemento.
>> Ang lahat ng mga karapatan, kaya medyo tuwiran.
Sa katunayan, tulad ng pakiramdam ng hindi namin halos paggawa ito masyadong kumplikadong.
Kaya natin ngayon pumitas off ang dulo ng listahan, at makita kung saan
ang pagiging kumplikado ng mga pagsisimula.
Kaya kung ngayon, ako alloc mula sa madla.
Sinuman na nais upang i-play 55?
Ang lahat ng mga karapatan, Nakita ko ang iyong unang kamay.
Halika sa up.
Oo.
Ano ang inyong pangalan?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Habata.
OK, dumating sa up.
Ikaw ang numero 55.
Kaya mo, siyempre, nabibilang sa dulo ng listahan.
Kaya natin i-replay ang simulation sa akin pagiging PTR para lamang ng ilang sandali.
Kaya unang pupuntahan ko ituro sa kahit anong Ben ay tumuturo sa.
Kami ay parehong nagtuturo ngayon sa Brian.
Kaya 55 ay hindi mas mababa sa limang.
Kaya ako ng pagpunta sa i-update ang sarili ko sa pamamagitan ng tumuturo sa susunod na pointer ni Brian, na
ngayon ay siyempre Jason.
55 ay hindi mas mababa sa siyam, kaya Pupunta ako sa i-update ang PTR.
Pupunta ako sa i-update ang PTR Ako pagpunta sa i-update ang PTR.
At pupuntahan ko - Hmm, kung ano ang ang iyong pangalan muli?
>> MAG-AARAL: Diana.
>> Tagapagsalita 1: Diana ay pagturo, siyempre, sa null sa kanyang kaliwang kamay.
Kaya kung saan ang ibig Habata talaga nabibilang malinaw?
Sa kaliwa, dito.
Kaya paano ko malaman upang ilagay ang kanyang Dito Sa tingin ko ko na screwed up.
Dahil kung ano ang PTR art sandaling ito sa oras?
Null.
Kaya kahit na, biswal, aming makakaya malinaw naman makita ang lahat ng mga
guys dito sa entablado.
Hindi ko na pinananatiling track ng dating tao sa listahan.
Hindi ko magkaroon ng isang daliri pagturo out, sa kasong ito, ang node bilang 34.
>> Kaya sabihin talagang simulan ito sa paglipas ng.
Kaya ngayon ko talagang kailangan isang pangalawang lokal na variable.
At ito ay kung ano ang makikita mo sa aktwal na sample C code, kung saan bilang pumunta ko,
kapag ako ay nag-update ang aking kanang kamay upang ituro Jason, at dahil doon umaalis Brian sa likod, ko
mas mahusay na simulan ang paggamit ng aking kaliwang kamay upang update kung saan ako ay, sa gayon ay bilang pumunta ko
sa pamamagitan ng listahan na ito -
higit pa kaysa awkwardly ko nilalayon ngayon dito biswal -
Pupuntahan ko na makuha ang dulo ng listahan.
>> Kamay na ito ay pa rin walang bisa, na kung saan ay medyo walang silbi, maliban sa upang ipahiwatig
Ako ay malinaw na sa dulo ng listahan, ngunit ngayon ay hindi bababa sa Mayroon akong ito
hinalinhan pointer na nakaturo dito, kaya ngayon kung ano ang mga kamay at kung ano ang payo kailangan
ma-update?
Kaninong mga kamay ang nais mong i-reconfigure ang unang?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: OK, kaya ni Diana.
Saan mo gustong upang ituro Kaliwa pointer ni Diana sa?
Sa 55, siguro, kaya na kami ipinasok doon.
At kung saan dapat 55 pointer pumunta?
Down, na kumakatawan null.
At ang aking mga kamay, sa puntong ito, hindi magawa mahalaga dahil sila ay lamang
pansamantalang variable.
Kaya ngayon tapos na kami.
>> Kaya ang karagdagang kumplikado doon - at ito ay hindi mahirap na ipatupad,
ngunit kailangan namin ng isang pangalawang variable upang gawing Siguraduhin na bago ilipat ko ang aking karapatan
banda, i-update ko ang halaga ng aking kaliwa banda, pred pointer sa kasong ito, kaya
na mayroon akong isang trailing pointer upang masubaybayan kung saan ako ay.
Ngayon bilang isang bukod, kung pinag-iisipan mo ito sa pamamagitan ng, ito nararamdaman tulad ng ito ay isang
maliit na nakakainis na magkaroon upang panatilihing subaybayan ito ng kaliwang kamay.
>> Ano ang gagawin ng isa pang solusyon upang ang problemang ito ay naging?
Kung nakukuha mo sa disenyo ng data Istraktura ng pinag-uusapan natin
sa pamamagitan ng ngayon?
Kung ito lamang ang uri ng pakiramdam ng isang maliit na nakakainis na magkaroon, i, dalawang payo
pagpunta sa pamamagitan ng mga listahan, sino pa ang maaaring pa, sa isang perpektong mundo, pinananatili
impormasyon na kailangan namin?
Oo?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Mismong.
Right kaya walang aktwal na isang kawili-wiling mikrobiyo ng isang ideya.
At ito ideya ng isang nakaraang pointer, pagturo sa nakaraang elemento.
Paano kung ko lang na katawanin sa loob ng listahan mismo?
At ito ay pagpunta sa maging mahirap upang mailarawan ang ito nang walang ang lahat ng mga papel
pagbagsak sa sahig.
Ngunit ipagpalagay na ang mga guys ginamit ang parehong ng kanilang mga kamay upang magkaroon ng isang nakaraang
pointer, at ng susunod na pointer, at dahil doon pagpapatupad ng kung ano ang makikita namin tumawag sa isang doble
naka-link na listahan.
Iyon ay magpapahintulot sa akin upang ayusin ng rewind, mas madali nang hindi sa akin, ang
programmer, pagkakaroon upang panatilihing subaybayan nang mano-mano -
tunay na mano-manong -
ng kung saan ako ay naging dati sa listahan.
Kaya hindi namin gawin iyon.
Susubukan naming panatilihin itong simple dahil iyon ang pagpunta sa dumating sa isang presyo, dalawang beses bilang
magkano ang space para sa mga payo, kung gusto mo ng pangalawang isa.
Ngunit iyon sa katunayan ng isang karaniwang istraktura ng data na kilala bilang isang
doble na naka-link listahan.
>> Tayo'y gawin ang panghuling halimbawa dito at ilagay mga guys out ng kanilang paghihirap.
Kaya malloc 20.
Halika sa up mula sa pasilyo doon.
Ang lahat ng mga karapatan, kung ano ang iyong pangalan?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Paumanhin?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Demeron?
OK dumating sa up.
Ikaw ay magiging 20.
Ikaw ay malinaw naman pagpunta sa nabibilang sa pagitan ng 17 at 22.
Kaya hayaan mo akong malaman ang aking mga aralin.
Pupunta ako upang simulan ang pointer pagturo sa Brian.
At pupuntahan ko ang aking kaliwang kamay i-update lamang sa Brian bilang ilipat ko sa
Jason, checking ang ibig 20 mas mababa sa siyam?
Hindi.
20 Ay mas mababa sa 17?
Hindi.
20 Ay mas mababa sa 22?
Oo.
Kaya kung ano ang payo o mga kamay kailangang baguhin kung saan sila nagtuturo ngayon?
>> Kaya maaari naming gawin 17 na tumuturo sa 20.
Kaya na fine.
Saan nagpupunta ang mga nais naming ituro ang iyong pointer ngayon?
Sa 22.
At alam namin kung saan 22 ay, muli salamat sa aking pansamantalang pointer.
Kaya hindi namin OK doon.
Kaya dahil sa ito pansamantalang imbakan Ko na pinananatiling track ng kung saan ang lahat ng tao ay.
At ngayon maaari mong biswal pumunta sa kung saan nabibilang mo, at ngayon ay kailangan naming 1, 2, 3,
4, 5, 6, 7, 8, 9 ng stress ball, at isang ikot ng papuri para sa
mga guys, kung magagawa namin.
Maayos na Natapos.
>> [Palakpakan]
>> Tagapagsalita 1: Ang lahat ng mga karapatan.
At maaari mong panatilihin ang mga piraso ng papel bilang mementos.
>> Ang lahat ng mga karapatan, sa gayon, nagtitiwala sa akin ito ng maraming mas madaling maglakad sa pamamagitan ng na may
mga kawani na tao kaysa ito ay may aktwal na code.
Ngunit kung anong makikita mo sa loob lamang ng ilang sandali ngayon, ay ang parehong - oh, salamat sa iyo.
Salamat sa iyo -
ay na makikita mo na ang parehong data istraktura, isang naka-link na listahan, maaari talaga
magamit bilang isang gusali block sa kahit na higit pa sopistikadong mga istraktura ng data.
>> At napagtanto masyado ang tema dito ay na talagang ipinakilala namin ang higit pa
pagiging kumplikado sa pagpapatupad ng algorithm na ito.
Insertion, at kung namin nagpunta sa pamamagitan nito, pagtanggal at searching, ay isang maliit na
mas komplikado kaysa ito ay may isang array.
Ngunit kami makakuha ng ilang dynamism.
Kumuha kami ng isang agpang istraktura ng data.
>> Ngunit muli, babayaran namin ang isang presyo ng pagkakaroon ng ilang mga karagdagang kumplikado, parehong sa
pagpapatupad ng mga ito.
At kami ay ibinigay up random access.
At upang maging matapat, mayroong ilang mga hindi magaling linisin slide ang maaari kong bigyan ka na
sabi dito ay kung bakit ang isang naka-link na listahan ay mas mahusay kaysa sa isang array.
At iwanan ito sa na.
Dahil ang tema reoccurring ngayon, kahit na higit pa kaya sa mga darating na linggo, ay
na mayroong hindi kinakailangang isang tamang sagot.
>> Ito ay kung bakit mayroon kaming ang nakahiwalay axis ng disenyo para sa mga hanay ng problema.
Ito ay magiging lubhang konteksto sensitive kung nais mong gamitin ang data na ito
istraktura o na ang isa, at kalooban ito depende sa kung ano ang mahalaga sa iyo sa mga tuntunin
ng mga mapagkukunan at kumplikado.
>> Ngunit ipaalam sa akin imungkahi na ang perpektong data istraktura, ang banal na Kopita, ay magiging
isang bagay na pare-pareho ang oras, hindi isinasaalang-alang ng kung magkano ang mga bagay-bagay ay
sa loob nito, hindi magiging kahanga-hangang kung ang isang data istraktura ibinalik na sagot sa
pare-pareho ang panahon.
Oo.
Salita na ito ay nasa iyong napakalaking diksyunaryo.
O wala na, ang salitang ito ay hindi.
O anumang katulad na problema doon.
Well sabihin makita kung hindi namin maaari nang hindi bababa sa kumuha ng isang hakbang patungo sa na.
>> Hayaan akong magpanukala ng isang bagong istraktura ng data na maaaring gamitin para sa iba't ibang mga bagay,
sa kasong ito na tinatawag na hash table.
At sa gayon kami ay talagang pabalik sa glancing sa isang array, sa kasong ito, at
medyo mang, ko ang iginuhit na ito hash talahanayan bilang isang array na may isang uri ng isang
dalawang-dimensional array -
o sa halip ito ay itinatanghal dito bilang isang dalawang dimensional array - ngunit ito lamang ang
isang array ng size 26, tulad na kung namin tawagan ang array talahanayan, table bracket
zero ay ang rektanggulo sa tuktok.
Table 25 bracket ay ang parihaba sa ibaba.
At ito ay kung paano ako gumuhit ng data istraktura na kung saan gusto kong mag-imbak
tao pangalan.
>> Kaya halimbawa, at hindi ko ay gumuhit ang buong bagay dito sa overhead, kung ako
nagkaroon ito array, na sa ngayon ay pupuntahan ko tawagan ng hash talahanayan, at ito ay muli
lokasyon zero.
Ito dito ay lokasyon isa, at iba pa.
Inaangkin ko na gusto kong gamitin ang data na ito istraktura, alang-alang sa talakayan,
mag-imbak ng mga tao mga pangalan, Alice at Bob at Charlie at ibang tulad ng mga pangalan.
Kaya sa tingin ng mga ito ngayon bilang ang Beginnings ng, sabihin nating, isang diksyunaryo
na may maraming mga salita.
Mangyari ang mga ito upang maging pangalan sa aming mga halimbawa dito.
At ito ay ang lahat ng masyadong dyermeyn, marahil, upang pagpapatupad ng isang spell checker, bilang namin
Maaaring para sa problema itakda anim.
>> Kaya kung kami ay may isang array ng kabuuang sukat na 26 kaya na ito ang ika-25 ng lokasyon
sa ibaba, at i-claim ko na Alice ay ang unang salita sa diksyunaryo ng
mga pangalan na gusto kong ipasok sa RAM, sa ang istraktura ng data, kung nasaan
instincts nagsasabi sa iyo na ni Alice pangalan dapat pumunta sa array na ito?
>> Mayroon kaming 26 na mga pagpipilian.
Kung saan gusto naming ilagay ang kanyang?
Gusto naming siya sa mga bracket zero, tama?
Isang para sa Alice, sabihin call na zero.
At B ay magiging isa, at C ay magiging dalawang.
Kaya kami ay pagpunta sa isulat Alice ang pangalan up dito.
Kung kami pagkatapos ay ipasok Bob, ang kanyang pangalan ay pupunta dito.
Charlie ay pumunta dito.
At iba pa pababa sa pamamagitan ng ang data na istraktura.
>> Ito ay isang kahanga-hangang istraktura ng data.
Bakit?
Well kung ano ang oras ng paggana ng pagpasok ng pangalan ng isang tao ay sa ito
data istraktura ngayon?
Given na talahanayan na ito ay ipinatupad, tunay, bilang isang array.
Well ito ay pare-pareho ang panahon.
Ito ay sunod ng isa.
Bakit?
>> Well paano mo matutukoy kung saan nabibilang ang Alice?
Tumingin ka sa kung aling mga titik ng kanyang pangalan?
Ang unang.
At maaari kang makakuha ng doon, kung ito ay isang string, sa pamamagitan lamang ng pagtingin sa string
bracket zero.
Kaya ang 0 karakter ng string.
Iyon ay madali.
Aming ginawa na sa crypto pagtatalaga linggo na ang nakaraan.
At pagkatapos ay sa sandaling alam mo na ni Alice titik ay capital A, maaari naming ibawas
off 65 o capital A mismo, na nagbibigay sa amin ng zero.
Kaya namin ngayon malaman na nabibilang Alice lokasyon sa zero.
>> At ibinigay na isang pointer upang ang data na ito istraktura, ng ilang mga uri, kung gaano katagal ang ibig
tumagal sa akin upang mahanap ang lokasyon zero sa isang array?
Lamang isang hakbang, kanan Ito ay pare-pareho ang oras dahil sa mga random access namin
ipinanukalang ay isang tampok ng isang array.
Kaya sa maikling salita, ang pag-uunawa kung ano ang index ng Alice ni ang pangalan, na kung saan ay, sa
kasong ito, ay A, o sabihin lamang malutas na sa zero, kung saan ang B ay isa at C ay
dalawa, pag-uunawa na out ay pare-pareho ang panahon.
Ko na lang ay upang tumingin sa kanyang mga unang titik, ang pag-uunawa kung saan zero ay isang
array ay din pare-pareho ang panahon.
Kaya technically na tulad ng dalawang hakbang na ito ngayon.
Ngunit iyon pa rin pare-pareho.
Kaya tinatawag namin na malaki O ng isa, kaya na namin Ipinasok Alice sa talahanayan na ito sa
pare-pareho ang panahon.
>> Ngunit siyempre, ako pagiging walang muwang dito, tama?
Paano kung mayroong isang Aaron sa klase?
O Alicia?
O anumang iba pang mga pangalan na nagsisimula sa A. Saan na tayo ng pagpunta sa ilagay
ang taong iyon, tama?
Ibig kong sabihin, sa ngayon mayroon lamang tatlong mga tao na nasa mesa, kaya siguro namin
dapat ilagay Aaron sa lokasyon zero isa dalawa tatlo.
>> Kanan, maaari ko bang ilagay ang isang dito.
Ngunit pagkatapos, kung susubukan namin upang ipasok David sa listahan na ito, kung saan ay pumunta David?
Ngayon, ang aming system ay nagsisimula pagsira pababa, tama?
Dahil ngayon si David ay nagtatapos up dito kung Aaron ay talagang dito.
At kaya ngayon ang buong ideya ng pagkakaroon ng malinis na istraktura ng data na nagbibigay sa amin
pare-pareho ang mga pagpapasok ng oras ay wala na pare-pareho ang oras, dahil mayroon akong upang
check, oh, damnit, may isang taong na- sa Alice ng lokasyon.
>> Hayaan akong suriin ang natitirang bahagi ng ang data na ito istraktura, hinahanap ang isang lugar upang ilagay
may isang taong katulad ni Aaron pangalan.
At nang sa gayon ay masyadong ay nagsisimula gumawa ng linear oras.
Dagdag pa rito, kung ikaw ngayon ay nais upang mahanap ang Aaron sa istraktura ng data, at ikaw
suriin, at Aaron ang pangalan ay hindi dito.
May perpektong, gusto mo lamang ang sinasabi ni Aaron wala sa istraktura ng data.
Ngunit kung gagawin mo nang kumita ng room para sa Aaron kung saan dapat ay naging isang D
o isang E, mo, pinakamasama kaso, mayroon upang suriin ang buong istraktura ng data, sa
Kung saan ito devolves sa isang bagay linear sa laki ng table.
>> Kaya ang lahat ng karapatan, makikita ko aayusin ito.
Ang problema dito ay na ako ay nagkaroon 26 mga elemento sa array na ito.
Hayaan akong baguhin ito.
Oops.
Hayaan akong baguhin ito nang sa gayon ay sa halip ng pagiging size 26 sa kabuuan, mapapansin sa ibaba
index ay pagpunta upang baguhin n minus 1.
Kung 26 ay malinaw na masyadong maliit para sa mga kawani na tao ' mga pangalan, dahil mayroong libu-libong mga
mga pangalan ng mundo, sabihin lang gumawa sa 100 o 1,000 o 10,000.
Sabihin lamang maglaan ng maraming mas maraming espasyo.
>> Well na ay hindi kinakailangang bawasan ang posibilidad na hindi namin ay magkakaroon ng dalawang
mga taong may mga pangalan na nagsisimula sa A, at gayon, ikaw ay pagpunta sa subukan upang ilagay ang isang
mga pangalan ng lokasyon sa zero pa rin.
Pa rin ang mga ito ay pagpunta sa nagbanggaan, na Nangangahulugan pa rin namin kailangan ng isang solusyon upang ilagay
Alice at Aaron at Alicia at iba pang mga mga pangalan na nagsisimula sa A sa ibang lugar.
Ngunit kung magkano ng isang problema ito?
Ano ang posibilidad na ikaw may banggaan sa isang data
kaayusan tulad ng mga ito?
>> Well, ipaalam sa akin - ipapakita namin bumalik sa na pinag-uusapan dito.
At tumingin sa kung paano maaari naming malutas muna ito.
Hayaan akong hilahin pataas ang panukalang ito dito.
Ano inilarawan namin ay isang algorithm, isang hyuristiko tinatawag na linear
probing kung saan, kung sinubukan mong isingit isang bagay dito sa data na ito
istraktura, na kung saan ay tinatawag na hash table, at mayroong walang room doon, mo
tunay na suriin ang data ng istraktura pagsusuri, ito ay magagamit?
Ay ito Magagamit na ito ay magagamit?
Ba ito magagamit?
At kapag ito ay sa wakas, ipasok mo ang pangalanan na iyong orihinal na nilalayon
sa ibang lugar sa lokasyong iyon.
Ngunit sa pinakamasama kaso, ang tanging lugar maaaring ang pinakailalim ng data
istraktura, pinakadulo ng array.
>> Kaya linear probing, sa pinakamasama kaso, devolves sa isang linear algorithm kung saan
Aaron, kung siya ang mangyayari sa mga na ipasok ang huling sa ganitong istraktura ng data, maaari siya
sumalungat sa mga ito unang lokasyon, ngunit pagkatapos magtapos sa pamamagitan ng malas sa pinakadulo.
Kaya ito ay hindi isang constant oras banal na Kopita para sa amin.
Ang diskarte ng pagpasok ng mga elemento sa isang istraktura ng data na tinatawag na hash
talahanayan ay hindi tila na maging pare-pareho ang oras hindi bababa sa hindi sa pangkalahatang kaso.
Maaari itong malipat sa isang bagay linear.
>> Kaya kung ano malutas namin banggaan medyo naiiba?
Kaya narito ang isang mas sopistikadong lapitan sa kung ano pa rin
tinatawag na hash table.
At sa pamamagitan ng hash, bilang isang tabi, kung ano Ibig kong sabihin ay ang index na
Ako refer sa mas maaga.
Upang mag-hash ng isang bagay na maaaring maging naisip ng bilang isang pandiwa.
>> Kaya't kung ikaw hash Alice ang isang pangalan, isang hash, kaya na magsalita,
dapat ibalik ang isang numero.
Sa kasong ito ay zero kung siya ay kabilang sa lokasyon zero, isa kung siya ay kabilang sa
isa lokasyon, at iba pa.
Kaya ang aking hash kaya ngayon ay naging sobrang simple, lamang ng pagtingin sa mga
unang titik sa pangalan ng isang tao.
Ngunit isang hash tumatagal ng bilang input ng ilang mga piraso ng data, isang
string, isang int, kahit anong.
At ito spits out karaniwang isang numero.
At bilang na kung saan ang data na iyon elemento nabibilang sa isang istraktura ng data
Kilala dito bilang isang hash table.
>> Kaya lamang intuitively, ito ay isang bahagyang naiiba konteksto.
Ito talaga ay nagre-refer sa isang halimbawa kinasasangkutan ng mga kaarawan, kung saan
maaaring magkaroon ng maraming mga bilang 31 araw sa buwan.
Ngunit kung ano ang taong ito upang magpasya gawin sa kaganapan ng isang banggaan?
Konteksto ngayon pagiging, hindi isang banggaan ng mga pangalan, ngunit isang banggaan ng kaarawan,
kung ang dalawang tao ay may parehong kaarawan sa ang Oktubre 2, halimbawa.
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Oo, kaya dito mayroon kami ang paggamit ng mga naka-link na mga listahan.
Kaya ito hitsura ng kaunti naiiba kaysa namin iginuhit mo ito nang mas maaga.
Ngunit lumitaw namin na magkaroon ng sa isang array sa kaliwang bahagi.
Iyon ang isa index, para sa walang partikular na dahilan.
Ngunit ito pa rin isang array.
Ito ay isang array ng mga payo.
At sa bawat isa sa mga elementong iyon, ang bawat isa ng mga lupon o slashes - ang slash
na kumakatawan sa null - bawat isa sa mga pointer ay tila na tumuturo sa
kung ano ang data kaayusan?
Ang isang naka-link na listahan.
>> Kaya ngayon kami ay may mga kakayahan na matapang na code sa aming programa
ang laki ng table.
Sa kasong ito, alam namin mayroong hindi kailanman higit sa 31 araw sa isang buwan.
Kaya mahirap coding ng halaga tulad ng 31 ay makatwirang sa na konteksto.
Sa konteksto ng mga pangalan, hard coding 26 ay hindi wala sa katwiran ito tao
mga pangalan lamang magsimula sa, halimbawa, ang alpabeto na kinasasangkutan A sa pamamagitan ng Z.
>> Maaari naming siksikin ang lahat ng ito sa data na iyon istraktura hangga't, kapag kami makakuha ng isang
banggaan, hindi namin ilagay ang mga pangalan dito, namin sa halip sa tingin ng mga cell na ito
hindi bilang mga string ang kanilang mga sarili, ngunit bilang payo upang, halimbawa, Alice.
At pagkatapos ay Alice ay maaaring magkaroon ng isa pang pointer sa ibang pangalan na nagsisimula sa
A. At Bob talagang napupunta sa paglipas dito.
>> At kung mayroong ibang pangalan nagsisimula may B, siya ay nagtatapos up sa paglipas dito.
At sa gayon ang bawat isa sa mga elemento ng ito dalawang talahanayan, kung dinisenyo namin ito ng
kaunti pa cleverly -
dumating sa -
kung dinisenyo namin ito ng kaunti pa cleverly, na ngayon ay nagiging isang agpang data
istraktura, kung saan walang mahirap na limitasyon sa kung paano maraming mga sangkap na maaari mong isingit
sa ito dahil sa kung mayroon kang mga isang banggaan, na fine.
Lang sige at ikabit ito sa kung ano ang nakita natin ng kaunti ang nakalipas noon ay
kilala bilang isang naka-link na listahan.
>> Well sabihin i-pause para lamang ng ilang sandali.
Ano ang posibilidad ng isang banggaan sa unang lugar?
Right, siguro sa paglipas ako nag-iisip, siguro Ako ay mahigit sa engineering ang problemang ito,
dahil alam mo kung ano?
Oo, maaari ba akong makabuo ng mga di-makatwirang halimbawa off sa tuktok ng aking ulo tulad ng
Allison at Aaron, ngunit sa katotohanan, ibinigay na isang pare-parehong pamamahagi ng
input, na ang ilang mga random na mga pagpapasok ng sa isang istraktura ng data, kung ano talaga ang
ang posibilidad ng isang banggaan?
Well lumiliko out, ito ay talagang sobrang mataas.
Hayaan akong magbigay ng tuntuning panlahat na ito problema ay ang bilang na ito.
>> Kaya sa isang kuwarto ng n CS50 mga mag-aaral, kung ano ang ang posibilidad na hindi bababa sa
dalawang mag-aaral sa kuwarto magkaroon ng parehong kaarawan?
Kaya mayroong kung ano. Ilang hund -
200, 300 mga tao dito at ilang daang mga tao sa bahay ngayon.
Kaya kung nais mong hilingin sa ating sarili kung ano ang ang posibilidad ng dalawang tao
sa kuwartong ito ang pagkakaroon ng parehong kaarawan, maaari naming malaman ito out.
At inaangkin ko ang aktwal na mayroong dalawang mga tao na may parehong kaarawan.
>> Halimbawa, ang sinuman may kaarawan ngayon?
Kahapon?
Bukas?
Ang lahat ng mga karapatan, kaya ito nararamdaman tulad ng pupuntahan ko upang magkaroon upang gawin ito 363 o kaya higit pa
beses upang aktwal na malaman kung mayroon kaming isang banggaan.
O maaari naming lamang gawin ito mathematically sa halip na tediously
ginagawa ito.
At ipanukala ang mga sumusunod na.
>> Kaya ko magpanukala na maaari kaming gawing modelo ang posibilidad ng dalawang tao ang pagkakaroon ng
parehong kaarawan bilang ang posibilidad ng 1 minus ang posibilidad ng hindi pagkakaroon ng isa
ang parehong kaarawan.
Kaya upang makakuha ng mga ito, at ito ay lamang ang magarbong paraan ng pagsulat na ito, para sa mga
unang tao sa kuwarto, siya ay maaaring magkaroon ng kahit isa sa mga posibleng
kaarawan ipagpalagay na 365 araw sa taon, may pasensiya sa mga taong may
ang kaarawan Pebrero 29.
>> Kaya ang unang tao sa kuwartong ito ay libre upang magkaroon ng anumang bilang ng mga kaarawan
sa labas ng 365 mga posibilidad upang ang gagawin namin na 365 na hinati sa pamamagitan ng 365,
na kung saan ay isa.
Ang susunod na tao sa kuwarto, kung ang layunin ay upang maiwasan ang isang banggaan, maaari lamang
magkaroon ng kanyang kaarawan sa kung paano maraming iba't ibang posibleng mga araw?
364.
Kaya ang ikalawang termino sa expression na ito ay mahalagang paggawa na matematika para sa amin
sa pamamagitan ng pagbabawas off ang isa posibleng araw.
At pagkatapos ay ang susunod na araw, sa susunod na araw, ang susunod na araw pababa sa kabuuang bilang
ng mga tao sa kuwarto.
>> At kung namin pagkatapos isaalang-alang, kung ano pagkatapos ay ang posibilidad ng hindi pagkakaroon ng lahat ng tao
natatanging kaarawan, ngunit muli minus 1 na, kung ano ang nakukuha namin ay isang expression
na maaari napaka fancifully ganito ang hitsura.
Ngunit ito ay mas kawili-wiling tumingin sa mga biswal.
Ito ay isang tsart kung saan sa x-axis ay ang bilang ng mga tao sa kuwarto, ang
bilang ng mga kaarawan.
Sa y-axis ay ang probabilidad ng isang banggaan, dalawang tao
nagkakaroon ng parehong kaarawan.
>> At ang mga takeaway mula sa curve ay na sa lalong madaling makakuha ka upang gustuhin 40
mga mag-aaral, ikaw ay hanggang sa isang 90% posibilidad combinatorically ng dalawang
mga tao o higit pa sa pagkakaroon ang parehong kaarawan.
At sa sandaling makakuha ka upang gustuhin 58 taong ito halos 100% ng isang pagkakataon ang dalawang
mga tao sa kuwarto ay pagpunta sa may parehong kaarawan, kahit na mayroong
365 o 366 posibleng mga bucket, at lamang 58 mga tao sa kuwarto.
Lamang-istatistika ikaw ay malamang na makakuha ng banggaan, na sa maikling
motivates ang talakayang ito.
Na kahit na makuha namin magarbong dito, at simulan ang pagkakaroon ng mga chain, hindi namin pa rin
pagpunta sa magkaroon ng banggaan.
>> Kaya na begs ang tanong, ano ang gastos ng paggawa ng mga pagpapasok at pagtanggal
sa isang data na istraktura tulad nito?
Well ipaalam sa akin imungkahi -
at hayaan mo akong bumalik sa screen sa ibabaw dito - kung kami n mga elemento sa
listahan, sa gayon kung sinusubukan naming isingit n elemento, at mayroon kami
kung gaano karaming mga kabuuang mga bucket?
Sabihin nating 31 kabuuang mga bucket sa kaso ng mga kaarawan.
Ano ang maximum na haba ng isa ng mga potensyal na chain?
>> Kung muli mayroong 31 posible kaarawan sa isang ibinigay na buwan.
At lang kami clumping lahat ng tao -
tunay na isang bobo halimbawa.
Natin gawin 26 sa halip.
Kaya kung mayroon talagang mga tao ang mga pangalan magsimula sa pamamagitan ng A Z, sa gayong paraan ng pagbibigay
sa amin 26 mga posibilidad.
At kami gumagamit ka ng data kaayusan tulad ng ang isa pa lang namin nakita, kung saan mayroon kaming
isang array ng mga payo, ang bawat isa mga punto sa isang naka-link na listahan kung saan ang
muna ang listahan ng lahat ng tao may pangalan Alice.
Ang pangalawang listahan ay tuwing may mga pangalanan na nagsisimula sa A, simula
may B, at iba pa.
>> Ano ang malamang haba ng bawat isa sa mga listahan ng kung ipinapalagay namin gandang malinis
pamamahagi ng mga pangalan ng A sa pamamagitan ng Z sa buong istraktura ng data?
Mayroong n tao sa mga istraktura ng data hinati sa 26, kung ang mga ito ay mabuti
maikalat sa buong istraktura ng data.
Kaya ang haba ng bawat isa sa mga chain ay N na hinati sa pamamagitan ng 26.
Ngunit sa malaking O notation, ano iyon?
Ano na ba talagang?
Kaya ito ay talagang lamang n, tama?
Dahil namin ang sinabi sa nakaraan, na he hatiin mo sa pamamagitan ng 26.
Oo, sa katotohanan ito ay mas mabilis.
Ngunit sa teorya, ito ay hindi sa panimula lahat na mas mabilis.
>> Kaya hindi namin mukhang lahat na magkano mas malapit sa ito Kopita banal.
Sa katunayan, ito lamang ang linear oras.
Ano ba, sa puntong ito, kung bakit hindi namin lamang gamitin ang isa sa malaking naka-link listahan?
Bakit hindi namin lamang gamitin ang isa sa malaking array na mag-imbak ng mga pangalan ng
lahat ng tao sa room?
Well, ay doon pa rin ng isang bagay nakahihimok tungkol sa isang hash talahanayan?
Mayroon bang pa rin ng isang bagay na nakakahimok tungkol sa isang istraktura ng data
na ganito ang hitsura?
Ito.
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: I-right, at muli kung ito lamang isang linear algorithm oras, at isang
linear oras data istraktura, bakit hindi ko lamang mag-imbak pangalan ng lahat sa isang malaking
array, o sa isang malaking naka-link listahan?
At tumigil sa paggawa ng CS kaya mas mahirap kaysa ito ay kailangang maging?
Ano ang tungkol sa nakahihimok na ito, kahit na bagaman ako scratched ito out?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Ipinasok ang hindi?
Mahal na ngayon.
Kaya pagpapasok ng potensyal pa rin ng dati maging pare-pareho ang oras, kahit na ang iyong data
istraktura mukhang ganito, isang array ng payo, ang bawat isa ay tumuturo sa
potensyal na isang naka-link na listahan.
Paano mong makamit ang pare-pareho oras ng pagpapasok ng mga pangalan?
Dumikit ito sa harap, tama?
>> Kung namin isakripisyo ang isang disenyo ng layunin mula sa mas maaga, kung saan gusto naming panatilihing
pangalan ng lahat, halimbawa, pinagsunod-sunod, o lahat ng mga numero sa entablado pinagsunod-sunod,
ipagpalagay na kami ay may isang unsorted naka-link listahan.
Ito lamang ay nagkakahalaga sa amin ng isa o dalawang hakbang, gusto sa kaso ng Ben at Brian
mas maaga, sa magpasok ng isang elemento sa sa simula ng listahan.
Kaya kung hindi namin pakialam tungkol sa pagbubukod-bukod ng lahat ng mga pangalan na nagsisimula sa A o lahat
ang mga pangalan na nagsisimula sa B, maaari pa rin namin makamit ang pare-pareho ang oras sa pagpapasok.
Ngayon hinahanap ang Alice o Bob o anumang pangalan higit pa sa pangkalahatan ay pa rin kung ano?
Ito ay malaki ng O n hinati sa 26, sa tamang-tama kaso kung saan ang lahat ng tao ay pantay
ibinahagi, kung saan mayroong maraming bilang A bilang mayroong Z, na kung saan ay marahil
hindi makatotohanang.
Ngunit iyon pa rin linear.
>> Ngunit dito, dumating kami pabalik sa punto ng asymptotic pagtatanda ng pagiging
theoretically totoo.
Ngunit sa tunay na mundo, kung i-claim ko na ang aking mga programa ay maaaring gawin ang isang bagay 26 beses
mas mabilis kaysa sa iyo, na ang program ay mo pagpunta sa mas gusto ginagamit?
Taos-pusong o minahan, na ay 26 beses na mas mabilis?
Realistically, ang mga tao na kung saan ay 26 beses nang mas mabilis, kahit na theoretically
ang aming mga algorithm tumakbo sa parehong asymptotic tumatakbo oras.
>> Hayaan akong magpanukala ng ibang solusyon sama-sama.
At kung ito ay hindi pumutok ang iyong isip, Ikinalulungkot namin out ng mga istraktura ng data.
Kaya ito ay ito ng isang trie -
uri ng isang ugok pangalan.
Nagmumula ito sa retrievals, at ang salita ay naisulat trie, t-r-i-e, dahil sa
Siyempre pagbawi Mukhang trie.
Ngunit iyon ang kasaysayan ng salitang trie.
>> Kaya isang trie talaga ang ilang mga uri ng puno, at ito ay din ng isang pag-play sa salitang iyon.
At kahit na hindi pa ninyo ang maaaring makakita nito may ganitong visualization, trie isang ay isang
puno nakaayos, tulad ng isang puno ng pamilya sa isa ninuno sa tuktok at maraming
ng mga inapo at mahusay na inapo bilang nag-iiwan sa ibaba.
Subalit ang bawat node sa isang trie ay isang array.
At ito ay sa isang array - at sabihin oversimplify para sa isang sandali - ito ay isang
array, sa kasong ito, laki ng 26, kung saan bawat node muli ay isang hanay ng mga laki
26, kung saan ang 0 sangkap sa na array ay kumakatawan sa A, at ang huling
sangkap sa bawat tulad array ay kumakatawan Z.
>> Kaya ko magpanukala, pagkatapos, na ang data na ito istraktura, na kilala bilang isang trie, maaaring maging
ginagamit din upang mag-imbak salita.
Nakakita kami ng ilang sandali ang nakalipas kung paano kami maaaring mag-imbak salita, o sa mga pangalan ng kaso, at kami
Nakita mas maaga kung paano namin maaaring iimbak ng mga numero, ngunit kung namin tumutok sa mga pangalan o mga string
dito, mapapansin kung ano ang kawili-wili.
Inaangkin ko na ang pangalan ay Maxwell sa loob ng data na ito istraktura.
Saan mo makita Maxwell?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Sa kaliwang.
Kaya kung ano ang mga kagiliw-giliw na may data na ito istraktura ay sa halip na tindahan ng
string M-A-X-W-E-L-L backslash zero, ang lahat ng contiguously, kung ano ang iyong gagawin sa halip
Sumusunod.
Kung ito ay isang trie tulad ng data ng istraktura, sa bawat isa sa kung saan ang mga node ay muli isang array,
at nais mong iimbak Maxwell, mo munang index at kaya node sa root ng, sa gayon
upang makipag-usap, ang kataas-taasan node, sa lokasyon M, kanan, sa gayon
humigit-kumulang sa gitna.
At pagkatapos ay mula doon, sundin mo ang isang pointer sa isang node bata, kaya na magsalita.
Kaya sa kamalayan family tree, sundin mo ito pababa.
At na humahantong sa iyo sa isa pang node sa kaliwa doon, na kung saan ay
lamang ng isa pang array.
>> At pagkatapos ay kung nais mong iimbak Maxwell, mahanap mo ang pointer na kumakatawan
A, na kung saan ay ang isang ito dito.
Pagkatapos mong pumunta sa susunod na node.
At notice - ito ay kung bakit ang larawan ni medyo deceiving -
node na ito hitsura sobrang napakaliit.
Ngunit sa kanan ng ito ay Y at Z. Lamang Ito ay ang may-akda ay pinutol ang
larawan sa gayon ikaw talaga makita ang mga bagay.
Kung hindi man ang larawang ito magiging hugely lapad.
Kaya ngayon mo sa index ng lokasyon X, pagkatapos ay W, E Pagkatapos, pagkatapos ay i-L, pagkatapos L. Pagkatapos ay kung ano ang
ang pag-usisa?
>> Well, kung ginagamit namin ang ganitong uri ng mga bagong kumuha sa kung paano i-imbak ang isang string sa isang
istraktura ng data, kailangan mo pa ring mahalagang suriin off sa data
istraktura na ang isang salita ay nagtatapos dito.
Sa ibang salita, ang bawat isa sa mga ito ang mga node kahit paano ay may na tandaan na namin
talagang sinundan ang lahat ng mga payo at ay umaalis ng kaunti
tinapay mumo sa ilalim dito ng mga ito istraktura upang ipahiwatig M-A-X-W-E-L-L ay
sa katunayan sa data na ito istraktura.
>> Kaya maaari naming gawin ito tulad ng sumusunod.
Ang bawat isa sa mga node sa larawan lang namin Nakita ay may isa, ang isang hanay ng mga sukat 27.
At ngayon 27, dahil sa p-set anim, ipapakita namin talagang magbibigay sa iyo ng isang kudlit,
upang maaari naming magkaroon ng mga pangalan tulad ng O'Reilly at iba pa na may apostrophes.
Ngunit parehong ideya.
Ang bawat isa sa mga elemento sa array mga punto sa isang struct
node, kaya lang ang isang node.
Kaya ito ay napaka nakapagpapagunita sa aming mga naka-link na listahan.
>> At pagkatapos ay mayroon akong isang Boolean, na kung saan bibigyan ko call na salita, na kung saan ay lamang ng pagpunta sa maging
totoo kung ang isang salita ay nagtatapos sa node sa tree.
Ito ay epektibong ay kumakatawan sa mga maliit tatsulok nakita namin ng ilang sandali ang nakalipas.
Kaya kung ang isang salita ay nagtatapos sa na node sa tree, ang salitang iyon patlang ay magiging totoo,
na kung saan ay conceptually check off, o kami ay pagguhit ng tatsulok na ito, yes doon
ay isang salita dito.
>> Kaya ito ay isang trie.
At ngayon, ang tanong ay, kung ano ang ay nito tumatakbo oras?
Ito ba ay malaki O ng n?
Ito ba ay iba pang dahilan?
Well, kung mayroon kang n pangalan sa data na ito istraktura, Maxwell pagiging isa lamang sa
mga ito, ano ang oras ng paggana ng pagpapasok o paghahanap ng Maxwell?
Ano ang pagtakbo ng oras ng pagpasok ng Maxwell?
Kung mayroong n iba pang mga pangalan na sa table?
Oo?
>> MAG-AARAL: [hindi marinig].
>> Tagapagsalita 1: Oo, ito ay ang haba ng pangalan, tama?
Kaya M-a-x-w-e-l-l kaya palagay ng ganito algorithm ay malaki O ng pito.
Ngayon, siyempre, ang pangalan ay mag-iiba sa haba.
Siguro ito ay isang maikling pangalan.
Marahil, ito ay isang mas mahabang pangalan.
Ngunit kung ano ang key dito ay na ito ay isang hindi nagbabagong numero.
At marahil ito ay hindi talaga pare-pareho, ngunit diyos, kung realistically, sa isang
diksyonaryo, doon ay marahil ilang mga limitasyon sa bilang ng mga titik sa isang
pangalan ng taong ito sa isang partikular na bansa.
>> At sa gayon ay maaari naming ipagpalagay na ang halaga ay isang pare-pareho.
Hindi ko alam kung ano ito ay.
Marahil ay mas malaki kaysa sa sa tingin namin ito ay.
Dahil mayroong palaging ng ilang mga sulok kaso may isang nakatutuwang mahaba pangalan.
Kaya sabihin call ito k, ngunit ito ay pa rin ng isang pare-pareho siguro, dahil bawat
pangalanan sa mundo, hindi bababa sa isang partikular na bansa, ay ang haba o
maikli, upang mas pare-pareho.
Ngunit kapag namin ang sinabi ng isang bagay ay malaki O ng isang pare-pareho ang halaga, kung ano ang na
talaga katumbas?
Iyon ay talaga ang parehong bagay tulad ng sinasabi ng pare-pareho ang panahon.
>> Ngayon kami ay uri ng pagdaraya, tama?
Humihingi kami ng uri ng pagdaragdag ng ilang mga teorya dito upang sabihin na rin, pagkakasunud-sunod ng k ay
talaga lang mag-order ng isa, at ito ay pare-pareho ang panahon.
Ngunit ito ay talagang.
Dahil ang mga key pananaw dito ay na kung kami n mga pangalan na ito sa
istraktura ng data, at insert namin Maxwell, ay ang halaga ng oras na aabutin upang amin
isingit Maxwell sa lahat ng mga apektadong sa pamamagitan ng kung gaano karaming mga iba pang mga tao
ay nasa istraktura ng data?
Mukhang hindi maging.
Kung ako ay nagkaroon ng isang bilyong higit pang mga elemento na ito sa trie, at pagkatapos ay ipasok Maxwell, ay
siya sa lahat ng apektado?
Hindi.
At iyan ay hindi tulad ng alinman sa mga araw ng data kaayusan nasaksihan namin kaya sa ngayon, kung saan
ang oras ng paggana ng iyong mga algorithm ay ganap na independiyenteng ng kung magkano
bagay-bagay ay o hindi pa sa data na istraktura.
>> At kaya may ito affords mo ngayon ay isang pagkakataon para p set anim, na kalooban
muli kasangkot sa pagpapatupad ng iyong sariling spell checker, pagbabasa sa 150,000
mga salita, kung paano pinakamahusay na mag-imbak na ay hindi nangangahulugang halata.
At bagaman ko na aspired upang mahanap ang ang banal na Kopita, gagawin ko hindi
i-claim na ang isang trie ay.
Sa katunayan, isang hash talahanayan maaari nang napakahusay patunayan na maging lubos na mas mahusay.
Ngunit iyon lamang ang -
ito lamang ay isa sa mga pagpapasya disenyo magkakaroon ka ng gumawa.
>> Ngunit sa pagsasara sabihin tumagal ng 50 o kaya segundo upang kumuha ng isang silip sa kung ano ang namamalagi
Magpatuloy sa susunod na linggo at lampas namin transition mula sa command line
mundo kung C programa sa mga bagay web batay at mga wika tulad ng PHP at
JavaScript at sa internet mismo, mga protocol tulad ng HTTP, na kung saan ikaw ay
kinuha para sa ipinagkaloob ng maraming taon ngayon, at nai-type na pinaka-araw-
araw, marahil, o nakikita.
At magsisimula kami upang alisan ng balat pabalik ang patong ng kung ano ay ang internet.
At kung ano ay ang code na underlies tool ngayon.
Kaya 50 segundo ng teaser na ito dito.
Ako magbibigay sa iyo ng Warriors ng Net.
>> [Video playback]
>> -Siya ay dumating sa isang mensahe.
Gamit ang isang protocol ang lahat ng kanyang sariling.
Siya ay dumating sa isang mundo ng malupit na firewall, uncaring router, at panganib sa ngayon
mas masahol pa kaysa kamatayan.
Siya ay mabilis.
Siya ay malakas.
Siya ay TCPIP.
At siya ay nakuha ang iyong address.
Mandirigma ng Net.
>> [END-playback ng video]
>> Tagapagsalita 1: Iyon ay kung paano ang internet ay dapat gumana tulad ng susunod na linggo.