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. 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. 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.