HIZLARIA 1: Guztiak eskubidea eta, beraz, itzuli gara. Ongi etorri CS50. Honek zazpi aste bukaera da. Beraz, azken aldiz gogoratzen duten, hasi ginen pixka bat sofistikatuagoa begira Datu egiturak. Orain arte, guztiak benetan izan dugu gure esku izan da hau, array bat. Baina baztertu dugu array baino lehen ez bezala interesgarria, eta hori da, hain zuzen ere, benetan da, zein dira batzuk sinple honek datu pluses egitura, beraz, orain arte? Zer da ona? Nik, orain arte ikusi dugun bezala? Zer nahi duzu? Ezer ez. Ikaslea: [INAUDIBLE]. HIZLARIA 1: Zer da hori? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 Tamaina finkoa. Ados, beraz, zergatik finkoen tamaina ona da, nahiz eta? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 OK, beraz, eraginkorra da bertan zentzu bat duzula esleitu ahal finkoa espazioaren zenbatekoa, beraz, espero da, hain zuzen, askoz espazio nahi duzun bezala. Beraz, erabat plus bat izan daiteke. Zer array baten aldean, sortu bat da? Bai? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 guztiak - Barkatu? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 memorian kaxak guztiak edo bata bestearen ondoan. Eta hori lagungarria - Zergatik? Hori da egia. Baina nola egia hori ustiatuko dugu? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 Zehazki, pista gorde ahal izango dugun non dena jakitea besterik ez da helbide bat, hau da helbidea memoria duten zatiaren byte lehen. Edo katearen kasuan, lehenengoa helbidea kate horretan char. Eta hortik aurrera, aurkituko dugu katearen amaieran. Bigarren elementu bat, aurkituko dugu Hirugarren elementua, eta abar. Eta, beraz, deskribatzeko modua Fancy duen luzea array ematen digu ausazko sarbidea. Just kortxetea erabiliz idazkera eta zenbaki bat da, ezin duzu salto egin array elementu jakin bat denbora konstante, big O en bat, nolabait esateko. Baina ez da downsides batzuk izan dira. Zer array bat ez oso erraz? Zer da ona, ezta? Ikaslea: [INAUDIBLE]. HIZLARIA 1: Zer da hori? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 tamaina zabalduz. Array downsides, beraz, ez dira Zer esan nahi du, hain zuzen, kontrakoa upsides dira. Beraz downsides bat da dela finkoa tamaina bat. Beraz, ezin duzu benetan hazten da. Handiagoa zatika reallocate dezakezu memoria, eta, ondoren, mugitu zaharrak elementuak berriak array batean. Eta, ondoren, free zaharra array, for Adibidez, malloc edo antzeko bat erabiliz funtzioa deitzen idazketa, eta horrek reallocates memoria. Idazketa, bat alde batera bezala, saiatzen emateko memoria hori array hurrengo dagoeneko duzula. Baina gauzak mugitu zitekeen guztiz inguruan. Baina, azken finean, hori da garestia, ezta? Izan duzu memoria pusketa bat galtzen delako Tamaina hori, baina benetan nahi duzun tamaina hori, eta, gorde nahi duzu jatorrizko elementuak, duzu gutxi gorabehera lineala denbora Kopiatzen behar dela gertatuko tik zaharrak berri array. Errealitatea eta eragilea da eskatuz sistema behin eta berriz, eta berriro memoria zatiak handi daiteke hasteko kostatuko nahi duzu, denbora pixka bat ere bai. Beraz, bai bedeinkazioa eta madarikazio bat da mozorrotzeko ere, multzo horiek tamaina finkoa dira. Baina horren ordez, aurkezten dugun zerbait horrela, lotzen deitzen dugu zerrenda, gutxi upsides bat lortu dugu, eta gutxi batzuk downsides hemen ere. Lotuta zerrenda bat besterik ez da, beraz, datu- egitura osatzen du C structs honetan kasuan, non egitura bat, oroitzapen, besterik ez da zehatz bat edo gehiago edukiontzi bat aldagai motak. Kasu honetan, zer datu motak agertzen egitura baten barruan egon behar duten azken denbora nodo bat deitu dugu? Laukizuzenak horietako bakoitza nodo bat da. Eta txikiagoa laukizuzenak bakoitzean horren barruan datu mota bat da. Zer motatako genuen esan ziren astelehenean dute? Bai? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 A eta aldagai erakuslea, edo zehazki, int bat, n, eta behealdean erakuslea. Horiek biak gertatuko 32 bit izango da, goizeko CS50 hau atsegin ordenagailu batean gutxienez Tresna, eta, beraz, dute Oraindik marraztuta berdin tamaina. Beraz, zer dira erakuslea erabiliz itxuraz egiteko, nahiz eta? Zergatik gehitu gezi hau orain denean array ziren beraz, atsegina eta garbia eta erraza? Zer erakuslea da egiten Gurekin nodo horietako bakoitzean? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 Horixe. Duzu kontatzea da, non hurrengoa da. Beraz, erabili ordenazio dut analogia du hari bat erabiliz ordenatzeko nahi haria nodo horiek elkarrekin. Eta hori zehazki zer ari gara egiten erakusleak horietako bakoitzak delako memoria zatiak daiteke edo ez izan Alboko, atzera itzuli itzuli nahi RAM barruan, aldi bakoitzean duzulako deitu malloc esaten, ematen dit nahikoa berri bat nodo byte, Agian hemen edo hemen egongo da agian. Hemen izan liteke. Hemen izan liteke. Besterik ez duzu, ez dakit. Baina erakusleak erabiliz helbideak de nodo horiek, stitch ditzakezu elkarrekin modu bat bisualki itxura batean zerrenda bat, nahiz eta gauza horiek bezalako guztietara hedatu zure bat edo zehar zure bi edo lau, zure RAM gigabyte zeure ordenagailuan barruan. Arazotxo da, beraz, eta, ondoren, eta lotuta zerrenda bat zer da? Zer prezio bat gara da itxuraz ordainduz? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 leku gehiago, ezta? , Dugu, kasu honetan, bikoiztu zenbatekoa espazioa dugu desagertu delako 32 nodo bakoitzeko bit bakoitzeko tik int, beraz, gaur egun 64 bit dugu delako mantentzeko inguruan erakuslea baita. Eraginkortasun gehiago lortuko duzu zure egiturari bada hau da, gauza sinple baino handiagoa da. Benetan baduzu ikaslea baten barruan horietatik kateak pare bat da izena eta etxea, agian ID zenbakia, agian, beste arlo batzuetan elkarrekin. Beraz, bada nahikoa egitura duzu, agian erakuslea kostua da ez aurre handi bat, besteak beste. Hau txoko kasu bat pixka hori da simple primitibo bat, hala nola ari gara gordetzeko lotuta zerrenda barruan. Baina puntua bera da. Behin betiko zaren gehiago gastatzea memoria, baina lortzean ari zaren malgutasuna. Orain, bada elementu bat gehitu behar delako nahi dut zerrenda honen hasieran, Nodo berri bat esleitu behar dut. Eta besterik gabe, horiek eguneratu behar dut geziak nolabait besterik mugituz Arrasto batzuk inguruan. Nahi dut zerbait sartu behar izanez gero sartu zerrenda erdian, ez dut nahi bultzatu denek alde batera utzi genuen bezala asteetan 'gure boluntario iraganeko nor irudikatzen array bat. Besterik ezin dut berria esleitu nodo eta gero, besterik gabe, geziak seinalatu batean norabide desberdinak ez duelako dute benetako jarraituko memoria benetako line Nik atsegin dut marraztuko hemen pantailan. Eta gero, azkenik, nahi izanez gero, sartu zerrendaren amaieran zerbait, bere are errazagoa. Hau idazkera arbitrarioa moduko bat da, baina 34-ren erakuslea hartu, etxebizitza bat. Zein da bere erakuslea gehienen balioa da litekeena marraztuta Ordena zahar bat bezala eskola antena ez? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 ziurrenik nulua da. Eta hain zuzen ere hori da egilearen null ordezkaritza. Eta nulua da delako, erabat jakin behar non lotutako baten amaiera zerrenda, mantendu duzu ondorengo lest eta eta geziak jarraituz eta hurrengo hauek nahi zabor balio batzuk. Beraz null ez dagoela adierazten ez da izango gehiago 34 eskuinera, nodo, kasu honetan. Beraz, ahal dugun ezartzea proposatzen dugu kodea nodo hau. Eta ikusi dugu mota honetako sintaxia baino lehenago. Typedef besterik mota berri bat definitzen ematen, gurekin sinonimo bezala * karaktere kate bat izan da. Kasu honetan, eman behar da joan takigrafia idazkera, beraz, egitura nodo beharrean besterik ez da idatzi gisa nodoa, eta horrek asko garbiagoa da. Gutxiago xeheak asko da. Nodo baten barruan itxuraz int bat izeneko n, eta ondoren egitura nodo bat * horrek esan nahi du zehatz-mehatz zer nahi dugu geziak, esan nahi da erakuslea bestera berean datu zehatzak mota nodo. Eta hori ezin dugu ezartzea proposatzen dut bilaketa hau atsegin funtzioa, zein Lehenengo begirada batean, agian badirudi konplexua pixka bat. Baina ikus dezagun da testuinguruan. Let me baino gehiago joan tresnara hemen. Let me ireki izeneko fitxategia zerrenda zero dot h. Eta hori bakarrik definizioa dauka dugu ikusi besterik ez duela une honetan datuak mota izeneko nodo bat. Beraz, sartu dela dot h fitxategia jarri dugu. Eta alde batera utzi, nahiz eta hau, nahiz gisa programa zarela ikusi da, gutxi gorabehera konplexua ez duten guztiak, hain zuzen ere, da konbentzio programa bat idazteko jarri gauzak datuak motak bezala, tira batzuetan, barrutik zure konstanteak goiburua fitxategia eta ez dute zertan hasi C Zure fitxategia, eta, zalantzarik gabe, zure programak eskuratu handiagoa eta handiagoa da, beraz, non bi begiratu for badakizu Kasu batzuetan dokumentazioa, edo hau bezalako oinarriak, egiteko mota batzuen definizioa. Dut ireki bada zerrenda zero dot c, nabarituko gauza batzuk. Gutxi batzuk goiburu fitxategiak, gehienak barne hartzen ditu horietatik ikusi dugu aurretik. Bere goiburu fitxategi ditu. Eta alde batera bezala, zergatik hori bikoitza komatxo hemen, baita angelu aurka on lerroan parentesi duten Nabarmendu dut, ez? Ikaslea: [INAUDIBLE]. HIZLARIA 1: Bai, beraz, fitxategi lokal bat da. Hala bada, zure fitxategi lokal bat da, hemen linea 15, adibidez, erabiltzen dituzun komatxo bikoitzaren ordez du angeluarekin parentesien. Orain interesgarri hau antzeko zerbait da. Iragarki ditudan deklaratu global bat Programa honetan aldagai line 18 izeneko lehen, ideia hau da: lehenengo erakuslea izango nire zerrenda lotutako nodoa, eta ez dut null hasieratu da, zeren dudan dut ez egotzitako benetako edozein nodo besterik gabe. Beraz, honek adierazten du, pictorially, zer egiten dugu ikusi momentu bat duela irudian bezala urrun erakuslea duten ezkerraldean. Beraz, oraintxe, erakusle dela ez du gezi bat. Da horren ordez, besterik gabe null. Baina zer izango den adierazten du lehenengo benetako helbide Zerrenda honetan nodo. Beraz inplementatu dut global bat da , Ikusiko duzun bezala ikusteko, izan ere, hori guztia programa ez da bizitzan ezartzeko niretzat zerrenda bat lotuta. Orain lortu dut gutxi batzuk prototipo hemen. Ezaugarri bezala ezartzea erabaki nuen ezabatzeko, txertatzeko bilatzen, eta, eskuratzea - du osoan besterik ez izatearen a pie zerrenda, eta bere elementuak inprimatzeko. Eta orain hemen nire nagusia errutina da. Eta ez dugu gehiegi pasatzeko denbora baita horiek ordenatu, eta espero dugu orain kapela zaharrak. Honako hau egiten dut, Erabiltzaileak, berriz, elkarlanean. Ko, beraz, inprimatu dut menu hori. Eta formateatuta dut gisa garbi nuen bezala. Erabiltzaile bat motak, esan nahi bada zerbait ezabatu nahi dute. Erabiltzaileak bi motak, esan nahi bada zerbait sartu nahi dute. Eta abar. Gero galdetuko dut eta komando bat. Eta, ondoren, GetInt erabili dut. Beraz, hau oso sinplea da menuing interfazea besterik ez duzu idatzi bat mapping zenbaki bat komandoak du. Eta, gaur egun polit bat garbi aldatu behar dut deklarazio hori aldatzeko gertatzen edozein izanik ere, erabiltzaileak idatzitako sartu Eta ondo idatzi dute bat bada, dut deitu ezabatu eta apurtu. Idatzitako bi izanez gero, dut deitu sartu eta hautsi. Eta orain, nabarituko jarri dut bakoitza berean horiek. Hau da, besterik gabe, estiloari erabaki bat. Normalean ikusi dugu zerbait hau atsegin du. Baina erabaki dut, sinceramente, nire programa begiratu irakurgarriagoa delako bakarrik lau kasu izan zen besterik zerrendatu da hau. Guztiz zilegia estilo. Eta hau, beraz, betiere egin nahi dut Erabiltzaileak ez du idatzitako zero, eta horrek I erabaki irten nahi dutela esan nahi izango du. Beraz, orain konturatu naiz zer hemen egingo. Zerrenda askatzeko itxuraz noa. Baina hori on gehiago une batean. Dezagun lehenengo programa honetan. Hargatik handiagoa terminal bat egin zidan leiho, dot barra zerrenda 0. Aurrera joan eta txertatu by noa Idazteko bi, 50 bezalako zenbaki, eta, orain, ikus zerrenda da orain 50 duzu. Eta nire testua besterik ez korritutako gora pixka bat. Beraz, orain konturatu zerrenda du zenbakia 50. Egin dezagun txertatze beste bi hartuz. Dezagun zenbaki bat bezala idatzi. Zerrenda bat da, gaur egun, 50 eta jarraian. Hau besterik ez da, beraz, testu-ordezkaritza zerrenda. Eta dezagun sartu zenbaki bat gehiago bezala kopurua 42 da, hau espero amaituko du erditik doa, izan ere, era honetan, bereziki, programa da Horietako txertatzen bezala elementuak. Beraz, ez da egin behar dugu. Super programa erraza izan erabat erabili array bat, baina ez dut gerta daiteke erabiliz lotuta zerrenda bat besterik ez da, beraz, dinamikoki dut hazten eta txikitu. Hargatik hartu bilaketa begirada bat, badut exekutatu komando hiru, bilatu nahi dut , esan, zenbakia 43. Eta ez da ezer aurkitu zen, itxuraz, dut itzuli delako erantzunik ez. Beraz, egin dezagun berriro. Bilaketa. Dezagun 50, edo, hobeto bilatzeko bilaketa 42, eta horrek atsegina apur sotila esanahia. Eta bizitzaren zentzua aurkitu nuen han. 42 zenbakia, ez baduzu ezagutzen erreferentzia, Google da. Guztiak eskubidea. Beraz, zer programa hau niretzat da? Ari sartu besterik ez da onartzen, beraz, me urrun eta elementuak bilatzeko. Dezagun Aurreratu, eta, ondoren, nahi duten funtzioa at begiratu dugu astelehenean aurkezpenik gisa. Funtzio hau, beraz, aldarrikatzen dut bilaketak batek zerrendako elementu lehenengo ko, erabiltzaileari galdetu, eta ondoren deituz GetInt benetako int bat lortzeko nahi duzun bila. Ondoren, iragarki hau. Aldi baterako aldagai bat sortu nahi dut line 188 izeneko erakuslea - PTR - izeneko aukera izan du ezer egin. Eta nodo bat erakuslea da esan dudalako * nodoa ez dago. Eta berdina izango da, naiz hasieratzean Lehenengo, beraz, eraginkortasunez hori daukat nire hatz, eta, beraz, hitz egiteko oso on zerrendaren lehenengo elementua. Hala bada, nire eskuineko Hemen nago PTR gauza bera seinalatuz lehen da seinalatuz. Beraz, orain atzera kodean, zer gertatzen den hurrengo - hau komuna paradigma bat da errepikatzean bat bezalako egitura baten gainetik lotuta zerrenda. Honako hauek egiteko aukera, berriz, banoa erakuslea ez da berdina Beraz null bitartean nire hatz ez da nulua batzuk seinalatuz balioa, erakuslea gezi-n berdin n. Nabarituko lehen dizugu n horixe da Erabiltzaile GetInts per idatzitako deitu hemen. Eta erakuslea gezi-n zer esan nahi du? Beno, bada, atzera egingo dugu Argazkia hemen, izan nuen hatz bat seinalatuz bada bederatzi, dauzkan lehen nodo duten gezi funtsean esan nahi duten joan nodo eta kokapena n balioa har, kasu horretan, datuak eremuan izeneko n. Bat alde batera bezala - eta pare bat honetan ikusi dugu Duela aste norbaitek galdetu - sintaxia hau ez da berria, baina ez du eskumenak ematen dugu ez zen jadanik. Zein izan zen esaldi hau erabiliz baliokideak dot idazkera eta izar pare bat Duela aste bueltan zuritu dugu geruza honek apur bat behar baino lehenago? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 Zehazki, izarra izan zen, eta ondoren, izar dot n izan zen, eta Parentesi hemen, itxura, sinceramente, asko uste dut críptica gehiago irakurtzeko. Baina izar erakuslea, beti bezala, bitartekoak joaten. Eta behin ez bazara, zer datuak Eremu ez da sartu nahi al duzu? Beno dot idazkera erabili behar dituzu sartzeko bat structs datuak eremuan, eta nik zehazki nahi n. Egia, hau argudiatu nahi nuke da, besterik gabe, zailagoa da irakurri. Zailagoa da non gogoratzeko ez parentesi joateko, izarra, eta hori guztia. Beraz, munduko hartutako sintaktiko batzuk azukrea, nolabait esateko. Just esaten modu sexy bat, hau da, baliokideak dira, eta agian intuitiboagoa. Erakuslea da, hain zuzen ere bada erakuslea da, gezi notazio bidez joan eta han aurkituko kasu honetan eremuan izeneko n. Beraz, bada, iruditzen zait, nabarituko dudana. Inprimatu besterik ez dut, ehuneko i aurkitu dut, int horren balioa plugging. Ko bigarren lo besterik mota deitu dut eteteko pantailan gauzak ematen du erabiltzaileak, bigarren bat xurgatzen zer gertatu da. Eta, ondoren, hautsi nuen. Bestela, zer egin dezaket? Erakuslea eguneratu dut berdina erakuslea gezi ondoan. Beraz, argi izan behar du, horrek esan nahi du joan ez, nire zahar-eskola idazkera erabiliz. Hori esan nahi du, beraz, edozein joan , zein zaren oso seinalatuz Lehenengo kasua at dut seinalatuz bertan bederatzi dituzten egitura du. Beraz, joan nintzen. Eta, ondoren, puntu idazkera esan nahi du, lortzeko balio hurrengo at. Baina balioa, nahiz eta marrazten da estu bat, zenbaki bat besterik ez da. Zenbaki bat da. Kode-lerro hau, beraz, ala ez horrela idatzita, gehiago críptica modu, edo hau bezala, pixka bat gehiago intuizioz, besterik gabe esan nahi du, nire eskua mugitu hurrengo bat nodo lehen, eta, ondoren, hurrengo batean, eta, ondoren, ren ondoan, eta abar. Beraz, ez dugu bestetik dwell txertatu eta ezabatu inplementazioak eta eskuratzea, lehenengo bi dira, nahiko parte hartzen. Eta nahiko erraz iritsi dela uste dut galdu egiten ahoz. Baina, zer egin dugu hemen ahal da saiatu zehaztu nola onenak hori egiteko ikusmen. Proposatuko nuke, zeren galtzen dugun nahi elementuak txertatu honetara dagoen zerrenda, eta horrek bost elementuak - 9, 17, 22, 26, eta 33 - ziren dut hau ezartzeko bada, joan kodea, nola joan kontuan hartu behar dut hau egiten. Proposatu eta haurra urratsak nuke Horren bidez, kasu honetan, esan nahi dut, zer dira ahalik eta eszenatoki dugu oro har, agian topo? Noiz Txertatu ezartzeko lotutako bat zerrenda, eta hori gertatzen da, izan nahi tamaina bost adibide zehatzak. Beno, bada, zenbaki bat sartu nahi baduzu, gustatzen esan zenbaki bat, eta ordenatuko ordena mantenduz, non jakina kopurua, behar bat ez honen adibide zehatz batean joan? Hasieran bezala. Baina zer da interesgarria, ez da hori nahi duzun bat sartu nahi izanez gero hau sartu zerrenda, zer behar bereziak erakuslea eguneratu egin behar da, itxuraz? Lehenengoa. Beraz, argudiatu, nuke lehen kasua da uste dugu, agian, bat eszenatoki batean sartu eta parte hartu zerrendaren hasiera-hasieratik. Dezagun pluck off agian beti bezain erraza, edo are errazagoa kasuan, nahiko hitz egin. Demagun sartu nahi dut 35 ordenan ordenatuko dira. Han, jakina, dagokion tokian. Beraz, zer erakuslea jakina da joan dute, eszenatoki horretan beharreko eguneratzen? 34-ren erakuslea ez nulua bihurtuz baina egitura duen helbidea 35 zenbakia duten. Beraz, hori da, bi kasu. Beraz, dagoeneko, quantizing moduko naiz zenbat hemen lan egin behar dut. Eta, azkenik, begi-bistakoa da, erdiko kasua hain zuzen ere, erdi-erdian, nahi izanez dut sartu say 23 doan antzeko zerbait 23 eta 26 artean, baina Orain, gauzak apur bat gehiago parte hartzen duelako zer erakusleak aldatu behar? 22 jakina behar du, beraz, aldatu egin behar da ahal izan ez delako, 26 seinalatu jada. Berrietara nodo seinalatu behar du: Dute esleitu dut deituz malloc edo baliokidea batzuk. Baina orduan ere behar dut berria nodoa, 23 kasu honetan, bere erakuslea dute nori begira? 26. Eta ez da beti izango da operazioen ordena hemen. Egiten dut, hau bada foolishly, eta nik delako Adibidez hasieran Irteeran for zerrendan, eta nire helburua, 23 txertatzeko. Ikusteko, eta, I ez da sartzen Hemen, bederatzi gertu? N º Ba al da hemen sartzen da, hurrengo 17? N º Ba al du hemen pertenece da hurrengo 22? Bai. Orain banago ero hemen, eta ez honen bitartez pentsatzen dut, agian esleitu nire 23 nodo berria. Erakuslea eguneratzeko liteke I nodo izeneko 22, seinalatuz it berria nodo at. Eta gero, zer egin behar dut eguneratu berriak nodo en erakuslea izan daiteke? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 Horixe. 26 seinalatuz. Baina dammit nuen ez badago eguneratu 22-ren erakuslea lasaia honetan seinalatu, eta orain, umezurtz, gainerako daukat zerrenda, nolabait esateko. Beraz, eragiketa ordena hemen garrantzitsuak izango. Hau egin nahi izan dut lapurtu, esan, sei boluntario. Eta ikus dezagun ezin bada egin, ikusmen beharrean, kode-jakintsua. Eta eder batzuk estresa dugu duzu gaur pilotak. Ados, nola buruz, bi, en itzuli - amaieran daude. hiru, lau, bai, zuk on amaieran guys. Eta bost, sei. Ziur. Bost eta sei. Guztiak eskubidea eta zatoz dugu to you guys hurrengoan. Ondo da, gora etorri. Ondo da, zauden geroztik hemen, litzateke baldarki bat izan nahi duzu Google Glass hemen? Eskubidea, eta, beraz, OK, beira, bideo bat grabatu. Ados, ona joan zaren. Ondo da, beraz, mutilak baino gehiago etortzen bada Hemen, aldez aurretik prestatu dut zenbakiak batzuk. Ongi, zatoz hona. Eta zergatik ez, pixka bat joan gehiago horrela. Eta ikus dezagun, zein da zure izena, Google Glass batera? Ikaslea: Ben. HIZLARIA 1: Ben? Ados, Ben, lehenengo izango duzu, literalki. Beraz bidaliko dizugu etapa amaieran. Guztiak eskubidea, eta zure izena? Ikaslea: Jason. HIZLARIA: 1 Jason, OK izango duzu zenbakia bederatzi izango dira. Beraz, bada, Ben horrela jarraitu nahi duzula. Ikaslea: Jill. HIZLARIA: 1 Jill, ahal izango duzu 17, eta hori egin nuen, bada gehiago intelligently, izan nahi nuke beste muturrean hasi zen. Horrela joan. 22. Eta eres? Ikaslea: Mary. HIZLARIA 1: Maria, 22 izan behar duzu. Eta zure izena? Ikaslea: Chris. HIZLARIA 1: Chris, 26 izan behar duzu. Eta gero, azkenik. Ikaslea: Diana. HIZLARIA 1: Diana, 34 izan behar duzu. Abar, zatoz hona. Guztiak eskubidea, beraz, hobetzeko ordenatuko aginduko du dagoeneko. Eta egin dezagun aurrera, eta hori egin beraz, ezin dugu benetan - Ben zaren besterik bilatzen mota ezerezetik ez da. Ados, beraz, goazen aurrera eta honek erakusten armak erabiliz, asko atsegin dut, izan zen, hain zuzen ere, zer ari den gertatzen. Anima zaitezte eta eman bat oinez edo yourselves artean bi. Eta aurrera eta seinalatu Batetik batekin duenarentzat izango duzu behar seinalatuz honetan oinarritzen da. Eta zauden null bada, besterik gabe, seinalatu Zuzen behera solairuan. Ados, beraz, ona da. Beraz, orain lotuta zerrenda bat dugu, eta niri utzi proposatu rol hori jokatu egingo dut PTR, beraz, ez dut kezkatu honen inguruan hornitutakoa. Eta gero, - norbaitek ergelak konbentzio - ezer honetan nahi duzun dei dezakezu - aurrekoak erakuslea, pred erakuslea - besterik ez da goitizena eman dugu Gure lagina nire ezkerreko kodea. Bestalde duten joan daiteke Conservación Nor dago jarraipena eszenatoki ondoren. Beraz, eman dezagun, lehenik eta behin, off pluck nahi dut txertatzeak lehen adibidea dela, esan 20, zerrendan sartzeko. Beraz, norbait behar dut embody kopurua 20 guretzat. Beraz, behar dut norbait malloc ikusleek. Goazen gora. Zein da zure izena? Ikaslea: Brian. HIZLARIA: 1 Brian, eskubidea guztiak, beraz, Nodoaren duten 20 izango da. Ongi, zatoz hona. Eta jakina, non Brian sartzen ez? Beraz, erdian - benetan, Itxaron minutu bat. Honetan ari gara kanpo. Hau egiten ari gara asko gogorragoa behar baino lehen behar izango da. Ados, libre Brian goaz eta idazketa Brian bost gisa. Ados, eta, beraz, orain sartu nahi dugu Bost Brian. Beraz, zatoz hona ondoan Besterik gabe, une batez Ben. Eta zentzuzkoa dezakezu kontatu non istorio hau da joan. Baina dezagun uste arretaz buruz eragiketak ordena. Eta, hain zuzen da ikusmen honetan hori sortu line joan lagin kodea duten. Beraz, hemen PTR dut, hasieran, seinalatuz Ben ez da, berez, baina edozein dela ere at balioa, baditu zuen eta kasu honetan da - Zein da zure izena berriro? Ikaslea: Jason. HIZLARIA: 1 Jason, bai Ben eta ni dira, beraz, Jason at une honetan seinalatuz. Beraz, orain zehaztu nahi izan dut, non ez Brian sartzen zara? Gauza bakarra, beraz, sarbide daukat oraintxe bere n datuak elementua da. Beraz, begiratu dut, da Brian Jason baino gutxiago? Erantzuna ez da egia. Beraz, zer egin behar da orain gertatuko, zuzena izateko? Zenbat erakusleak eguneratu behar dut istorio honetan, guztira? Non dago nire eskua dago oraindik seinalatuz Jason, eta zure esku - nahi izanez gero jarri zure eskua bezala ordenatu, eta I ez dakit, galdera-marka bat. Ados, ona. Guztiak eskubidea, beraz, ez duzu gutxi hautagai bat. Bai Ben edo I edo Brian edo Jason edo, bestela, pertsona guztiei, eta horrek erakusleak behar aldatzeko? Nola guztira, asko? OK, beraz, bi. Nire erakuslea ez da benetan axola jada naiz dudalako aldi baterako. Beraz, bi mutil hauek da, ustez, Ben bai eta Brian. Hargatik niri proposatu eguneratu dugu Ben, geroztik izan zuen lehenengo. Zerrenda honen lehenengo elementua dago orain, Brian izango. Beraz, Ben Brian puntua. Ongi da, orain zer? Nork nori at adierazi? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 OK, beraz, Brian ditu to Jason puntua. Baina horren erakuslea pista galdu dut? Ez da non Jason ezagutzen dut? Ikaslea: [INAUDIBLE]. HIZLARIA: 1, egin dut geroztik I aldi baterako erakuslea. Eta, ustez, ez dut aldatu berriak nodo puntua. Beraz, besterik gabe, ezin dugu Brian puntua duenak at dut seinalatuz. Eta egiten ari gara. Kasu bat, bertan txertatzeko, beraz, zerrendaren hasiera-hasieratik. Baziren beste bi urrats. Ko, Ben eguneratu behar dugu, eta, ondoren, dugu Brian eguneratzeko. Eta gero, ez dut kezkatu gainerako zehar traipsing zerrenda, izan ere, dagoeneko aurkitu dugu, bere kokapena, delako izan da zuen lehenengo elementu utzi. Ondo da, beraz, nahiko erraza da. Izan ere, sentitzen gara ia bezala hori ere konplikatua egiteko. Hargatik, orain pluck off amaieran zerrendan, eta ikusi non konplexutasuna hasten da. Beraz, bada, esleipenen ikusleek dut. Edonork nahi 55 play? Ondo da, zure eskua ikusi nuen lehenengo. Goazen gora. Bai. Zein da zure izena? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 Habata. Ados, zatoz gora. Kopurua 55 izango zara. Beraz, nola ez, duzu, sartzen zerrendaren amaieran. Hargatik errepikatzea simulazioa nirekin PTR izateagatik, besterik gabe, une batez. Beraz, lehenengo naiz amaitzen joan edozein dela ere Ben seinalatuz. Bai ari gara orain, Brian seinalatuz. 55 Beraz, ez da bost baino gutxiago. Beraz, neure burua eguneratu nahi dut to Brian hurrengo erakuslea, seinalatzen duten Orain, noski Jason da. 55 ez da bederatzi baino gutxiago, beraz, PTR eguneratzeko noa. PTR eguneratzeko noa. PTR eguneratu dut Joan PTR eguneratu behar dut. Eta dut - hmm, zer Zure izena berriro? Ikaslea: Diana. HIZLARIA 1: Diana apuntatzen da, noski, Bere ezkerreko eskuarekin null at. Beraz, ez du benetan Habata sartzen dira, argi eta garbi? Ezkerretara, hemen. Beraz, nola ez, bere jartzea Hemen ezagutzen dut Screwed dut uste dut. Zer da artea delako PTR Une honetan? NULL. Beraz, nahiz eta, ikusmen dezakegu ikusten, jakina, horiek guztiak Zuek hemen eszenatokian. Ez dut mantendu pista aurreko zerrendako pertsona. Ez dut hatz bat seinalatuz, Kasu honetan, nodo kopurua 34. Hargatik, benetan hasi honetan. Beraz, orain ez dut behar bat bigarren tokian tokiko aldagai. Eta hau da, zer ikusten dituzun ikusiko benetako lagina C kodea, non gisa joan nintzen, nire eskuineko eguneratu dut seinalatuko Jason eta, horrela, Brian atzean utzita, I hobeto hasteko nire ezkerreko erabiliz eguneratu non nengoen, beraz, joan nintzen zerrenda honen bidez - gehiago baldarki xedea baino Orain, hemen, ikusmen - To lortu dut zerrendaren bukaeran. Hau da, alde batetik, oraindik null, hau da, nahiko Ezertarako, beste batzuk baino adierazi Argi dut zerrendaren amaieran, baina, orain, gutxienez, hau daukat aurrekoak erakusleak hemen apuntatzen, beraz, orain zer eskuak eta zer esan behar eguneratu egin behar da? Norena da eskua nahi duzu birkonfiguratzeko lehen? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 OK, Diana en, beraz. Nora egin nahi duzu seinalatu Diana en ezkerretara erakuslea at? 55 egun, ustez, beraz, txertatuko dugu han. Eta non behar 55 erakuslea joan? Behera, null ordezkari. Eta nire eskuak, puntu honetan, ez axola ziren, besterik ez delako aldi baterako aldagaiak. Beraz, orain egiten ari gara. Osagarriak konplexutasuna beraz - eta ez da gogorra dela ezartzea, baina bigarren mailako aldagai egin behar dugu Ziur hori mugituko dut nire eskuineko aurretik Bestalde, nire ezker balioa eguneratu dut Bestalde, pred kasu honetan erakuslea, beraz, que tengo amaierako erakuslea segimendua egiteko, non nengoen ere. Orain, bat alde batera utzita ere, ari zaren hori izanez gero, pentsatzen bidez, hau da bezala sentitzen da txiki gogaikarriak mantendu dute honen ezkerreko jarraipena. Zer izango litzateke beste irtenbide bat arazo hau izan da? Lortu diren datuak diseinu nahi baduzu egitura hitz egiten ari gara oraintxe bidez? Hau bakarrik mota sentitzen pixka bat bada gogaikarriak, adibidez, bi erakusleak zerrendan, joan ezin izan duten beste dute, ezin hobea da munduan, mantendu informazioa behar dugu? Bai? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 Horixe. Eskubidea, beraz, ez da benetan interesgarria ideia baten ernamuina. Eta aurreko erakuslea ideia hau, aurreko elementu seinalatuz. Zer dut gauzatuz gero zerrenda beraren barruan? Eta zaila da ikusteko izango da joan honetan paper guztiak gabe lurrera erortzen. Baina demagun guys horiek biak erabiltzen bere eskuetan, aurreko bat izan erakusle eta hurrengo erakuslea eta, horrela, zer bat bider deitu dugu ezartzeko lotuta zerrenda. Hori atzeratzeko of me ordenatzeko aukera litzateke, askoz errazago me gabe, programatzaile, gorde beharrik jarraipena eskuz - benetan eskuz - non izan dut lehenago zerrendan. Beraz, ez dugu hori egiten. Keep it simple dizugu hori delako da prezio bat etorri, bi aldiz joan erakusleak espazio askoz, bigarren bat nahi baduzu. Baina hori da hain zuzen ere, ohikoa Datuen egitura gisa ezaguna bi aldiz lotuta zerrenda. Egin dezagun azken adibide eta hemen jarri beren miseria out mutil hauek. Malloc 20, beraz. Korridore du hortik gora etorri. Guztiak eskubidea, zein da zure izena? Ikaslea: [INAUDIBLE]. HIZLARIA 1: Barkatu? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 Demeron? Ados sortu etorri. 20 izan duzu izango. Jakina dira duzun joan 17 eta 22 artean dira. Beraz, nire ikasgaia ikasten me. Erakuslea hasi nahi dut Brian seinalatuz. Eta nire ezkerreko izan dut bakarrik to Brian eguneratzeko dut mugitu Jason, egiaztapena du 20 bederatzi baino gutxiago? N º 20 17 baino gutxiago? N º 20 22 baino gutxiago? Bai. Beraz, zer edo erakusleak eskuak behar aldatzeko non orain ari dira apuntatzen? Beraz, 17 egin dezakegun 20 seinalatuz. Beraz, hori da isuna. Nora egin nahi dugu, seinalatu Zure erakuslea da orain? 22. 22 eta non dagoen jakin dugu, berriro ere esker nire aldi baterako erakuslea. Ados, beraz, ez gara. Beraz, horregatik aldi baterako biltegiratze Mantendu dut pista non denek da. Eta, orain ikusmen dezakezu non sartu , kide zaren eta, orain, 1, 2, 3, behar dugu, 4, 5, 6, 7, 8, 9, estresa pilotak, eta txalo Kopako for mutil hauek, ezin izan dugu gero. Nicely done. [Txaloak] HIZLARIA 1: Guztiak eskubidea. Eta piezak gorde dezakezu mementos paper gisa. Eskubidea, eta, beraz, konfiantza me asko da errazagoa dela ibiltzeko dituzten gizakiak kodea benetako baino da. Baina, zer besterik gabe, une batean aurkituko duzu gaur egun, bera dela - Oh, eskerrik asko. Eskerrik asko - da bera datuak duzula aurkituko egitura, lotuta zerrenda, benetan behar da, are gehiago, eraikin bloke gisa erabiltzen sofistikatua datuak egiturak. Eta konturatzen gehiegi gaia hemen da erabat sartu dugu gehiago ezartzeko sartu konplexutasuna algoritmo hau. Txertatzeko, eta horren bidez ginen bada, ezabatzeko eta bilaketak, txiki bat da baino gehiago konplikatuak array bat izan zen. Baina dinamismo batzuk irabazten dugu. Moldatzaile bat datuak egitura lortzen dugu. Baina, berriro, batzuk izatearen prezio bat ordaindu behar dugu osagarriak konplexutasuna, bai bertan ezartzeko. Eta gaude amore eman ausazko sarbidea. Eta egia esateko, ez da ez egokia batzuk garbitu diapositiba eman ahal dut dio hemen zergatik lotuta zerrenda bat da da array bat baino hobea da. Eta utzi hartan. Orain, gai reoccurring delako, nahiz eta are gehiago, datozen asteetan, da ez dagoela ez da, nahitaez, Erantzun zuzena da. Hori dela eta, aparteko ardatza dugu arazo multzo baten diseinua. Oso testuinguru sentikorra izango da nahi duzun datu hau erabili ahal izateko edo egitura bat, eta izango da mendeko zer axola dagokionez baliabideak eta konplexutasuna. Baina utzi niri proposatu datuak ezin hobea dela egitura, Santo Grial, litzateke zerbait etengabeko denbora da, kontuan hartu gabe zenbat gauza da Barruan, ez litzateke harrigarria izango da, bada, Datuen egitura itzuli erantzun etengabeko denbora. Bai. Hitz hau zure hiztegi erraldoia da. Edo ez, hitz hori ez da. Edo halako arazoa ez. Beno, ikus dezagun ezin dugu gutxienez bada hartzen duten norabidean urrats bat. Demagun berri bat datu-egitura proposatu dit gauza ezberdinak erabil daitezke, kasu honetan deitzen hash taula bat. Eta, beraz, benetan gara itzuli glancing array bat, kasu honetan, eta, zertxobait arbitrarioki, marrazten dut hau baten Ordena array gisa hash taula bi dimentsioko array - edo, hobeto ari irudikatuta hemen bi dimentsioko array - baina hori besterik ez da, baten tamaina 26 multzo, hala nola galtzen dugun deitu array mahaia, mahai-tarte zero goialdean laukizuzena da. Taula parentesi 25 laukizuzena behealdean. Eta hau da, datuak nola marraztu liteke I egitura eta bertan gorde nahi dut pertsonen izenak. Beraz, adibidez, eta ez dut marraztu gauza osoa hemen Buruak gainean, badut izan array honetan, orain ari naiz joan deitu hash taula bat, eta hau da, berriro ere kokapena zero. Hau da, hemen kokapena bat, eta abar. Nahi dut datu hau erabiltzea aldarrikatzen dut egitura, eztabaidak eztabaida egiteko, pertsonen izenak gordetzeko, Alice eta Bob eta Charlie eta beste batzuk, hala nola, izenak. Beraz, pentsa orain hasiera gisa , esan, hiztegi bat hitz asko. Izenak izan gertatuko dira Adibidez, gure hemen. Eta hau da, guztiak ere germane, agian, behar zuzentzaileari bat garatzen dugu Baliteke arazoa ezarritako sei. Beraz, bada, tamaina, guztira 26 sorta bat daukagu beraz, hau 25ean kokapena da behealdean, eta Alice dela aldarrikatzen dut hiztegiaren hitza lehenengo izenak nahi dut RAM txertatzeko, Datuen egitura honetan sartu da, non daude senak diozu Alice-en izena behar array honetan joan? 26 aukera ditugu. Non bere jarri nahi dugu? Bere nahi dugu tarte zero da, ezta? Alice A dezagun deitzen zero dela. Eta B bat izango da, eta C bi izango dira. Beraz, idatzi dugu Alice izena hemen. Ondoren, sartu bada Bob, bere izena hemen joango dira. Charlie hemen joango dira. Eta abarren bitartez behera Datuen egitura hau. Hau zoragarria da datu-egitura bat da. Zergatik? Beno zer exekutatzen denbora da giza baten izena sartu eta hau sartu Datuen egitura oraintxe? Emandako taula hori horrela, benetan, array gisa. Beno, etengabeko denbora da. Ko ordena da. Zergatik? Beno, nola ez duzu zehaztu Alice non pertenece? Itxura duen gutun bere izena honetan zaude? Lehen. Eta iritsi zaitezke, baina kate bat bada, besterik kate begira parentesi zero. Katearen zeroth pertsonaia beraz. Hori da erraza. Hori egin dugu kripto-en esleipena duela. Eta, ondoren, behin Alice horrek badakizu gutun da kapitala, kendu ahal izango dugu 65 edo kapital bat bera off, ematen digu, zero. Beraz, gaur egun ezagutzen dugun Alice berea dela kokapena zero at. Eta emandako datu honen erakuslea egitura, nolabaiteko, zenbat irauten du Niri hartu kokapena aurkitzeko array batean zero? Just urrats bat, etengabeko denbora eskubidea da ausaz sarbidea dugulako proposatutako array baten ezaugarri bat izan zen. Beraz, azken finean, eta zer kalkulatzen indizea Alice izena da, hau da, urtean Kasu honetan, A da, edo, besterik gabe, horrek ebatzi zero da, non da B eta C bi, hori kalkulatzen out etengabeko denbora da. Izan dut bere lehenengo hizkia begiratu, out kalkulatzen non zero da array da, halaber, etengabeko denbora. Beraz, teknikoki hori bi urrats orain bezala. Baina oraindik ere, konstante. Beraz, bietako bat O big deitzen dugu, beraz, dugu txertatuko Alice taula honetan sartu etengabeko denbora. Baina, jakina, baloia dut inozoa hemen, ezta? Zer dago klase Aaron bat bada? Edo Alicia? Edo beste edozein izen honekin hasten A. Nora jarri dugu pertsona hori, ezta? Esan nahi dut, oraintxe bertan hiru mahai gainean, pertsonak, eta, beraz, agian dugu Aaron jarri behar kokapenean zero, bat, bi, hiru. Eskuin, bat atera nuen hemen. Baina gero, saiatu gara David txertatzeko hartuz gero zerrenda hau, non ez du David joan? Orain gure sistema hasten hausteko behera, eskuinera? Gaur egun, David bueltarik delako hemen Aaron da, benetan bada, hemen. Eta beraz, gaur egun bat izatea ideia osoa honetan garbi egitura datuak ematen dizkigun sarrerak etengabeko denbora ez da jada etengabeko denbora izan delako dut egiaztatzeko, oh, damnit, norbaitek dagoeneko Alice en kokapenean. Dezagun datu hau gainerako probarik egin me egitura, spot bat jarri bila Aaron bere izena bezala norbait. Eta, beraz, gehiegi da abiapuntua lineal denbora hartzeko. Gainera, gaur egun, nahi izanez gero aurkitzeko Datuen egitura honetan Aaron, eta zuk egiaztatzeko, eta Aaron bere izena ez da hemen. Ahal izanez gero, besterik gabe, esango zenuke Aaron en ez da datu-egituran. Baina egiten baduzu hasteko gela egiteko Aaron han izan behar D edo E, zu, kasurik okerrenean, egiaztatu dute osoa datuak egitura, en kasu devolves zerbait da taularen tamainan lineala. Eskubidea, beraz, hau konpondu dut. Arazoa da hemen izan nuen 26 array elementu hau. Demagun aldatu zidan. Whoops. Let me aldatu da, beraz, baizik eta izateko tamaina 26 guztira, nabarituko beheraino indize nahi n ken 1 aldatzen doaz. 26 argi bada txikiegia gizakiak 'egiteko izenak, ez delako da, milaka eta milaka munduko izenak, dezagun, besterik gabe, egin 100 edo 1.000 edo 10.000 ziren. Dezagun, besterik gabe esleitu asko leku gehiago. Beno, horrek ez du zertan gutxiagotu probabilitatea izango dugula ez bi izenak dituzten pertsonak A hasita, eta beraz, bat jartzen saiatu ziren, zoaz at kokapena zero izenak oraindik. Oraindik dute talka gertatzen da, eta horrek esan behar dugu oraindik irtenbiderik jarri Alice eta Aaron eta Alicia eta beste izenak edonon A hasita. Baina zenbat arazo bat da hau? Zer da probabilitatea duzula datu batean talkak hau bezalako egitura? Beno, let me - itzuli gara Galdera hemen. Eta nola genezake begiratu konpontzeko lehen. Let me up tira, proposamen hau hemen. Zer deskribatzen dugu algoritmo bat da, izeneko lineal heuristiko bat Horren bidez, probak, saiatu sartu bada Hemen zerbait datuak honetan egitura, hau da, deitu hash taula bat, eta ez dago gela ez da ez, duzu benetan probarik datuak egitura egiaztatuz, hau da eskuragarri? Eskuragarri dago, hau da hau eskuragarri? Hau da eskuragarri? Eta noiz da azkenean, sartu izendatzeko jatorriz duzun xedea edonon kokapena hartan. Baina txarrena kasuan, bakarrik spot datu bukaerara izan liteke egitura, array amaiera oso. Beraz, lineal, probak txarrena kasuan, lineal bat algoritmoa sartu devolves non Aaron, gertatzen zen txertatuko dira azken bada Datu-egitura honetan, zuen agian Lehenengo kokapena talka, baina ondoren, zorte txarra by amaitzeko oso amaieran. Beraz, hori ez da konstante bat denbora santua Gurekin Grial. Honek elementu txertatu ikuspegi sartu Datuen egitura izeneko egiaztapena taula ez dirudi, etengabeko denbora izango da ez behintzat, oro har, gero. Zerbait lineal sartu ahal izango da devolve. Beraz, zer bada talkak konpontzen ditugu zertxobait ezberdinean? Beraz, hemen sofistikatuagoa da zer da oraindik ere hurbiltzen izeneko hash taula bat. Eta hash, bat alde batera utzita, zer gisa Indizea dela esan nahi dut Aipatu dut lehenago. Hash zerbait izan daiteke pentsatu aditz gisa. Beraz baduzu hash Alice izen bat da, hash funtzio bat, nolabait esateko, zenbaki bat itzuliko da. Kasu honetan zero egin zuen bada kokapena zero, bat bada zuen pertenece kokapena, eta abar. Nire hash funtzioa, beraz, beraz, orain arte izan super simple, bakarrik begira norbaiten izenean gutun lehen. Baina hash funtzio bat bezala hartzen du sarrera batzuk, datu-pieza bat string, int bat, edozein dela ere. Eta spits da normalean zenbaki bat. Eta zenbaki hori da, non datu datu elementu egitura batean pertenece ezaguna hemen hash taula gisa. Beraz, intuizioa, hau da, apur testuinguruan. Egia esan, hau da, adibide bat aipatuz inplikatuz urtebetetzeak, non asko bezala, izan liteke 31 hilabete egunetan. Baina zer pertsona hau erabaki talka gertatuz gero, zer egin? Testuinguru orain, baloia ez talka baten izenak, baina urtebetetzeak talka bat, bi pertsona bera dute urtebetetzea bada an Urriaren 2an, adibidez. Ikaslea: [INAUDIBLE]. HIZLARIA 1: Bai, hemen dugu zerrendak lotuta aprobetxatuz. Beraz, apur bat badirudi modu ezberdinean zirenak baino lehenagokoak dugu. Baina array bat agertzen dugu Ezkerreko aldean. Indize bat da, ez da bereziki arrazoiak. Baina oraindik array bat. Erakusleak sorta bat da. Eta elementu horietako bakoitzak, bakoitzaren zirkulu horiek edo barrak - barra du ordezkari nulua - horietako bakoitzean erakusle da itxuraz to seinalatuz Datuen egitura eta zer? Lotuta zerrenda. Beraz, orain gaitasuna daukagu gure programa bihurtu kodea gogorra taula tamaina. Kasu horretan, ez da inoiz jakin dugu baino gehiago 31 egun, hilabete bat. Hain zaila 31 bezalako balio bat da kodeketa Testuinguru horretan, arrazoizkoa. Izenak testuinguruan, gogor kodeketa 26 ez da unreasonable da pertsonen izenak bakarrik Hasteko, adibidez, alfabetoaren A inplikatuz Z. bidez Denak CRAM dezakegu datuak sartu egitura hain luze, denean bat lortuko dugu talka, ez dugu jarri izenak hemen, zelula horien ordez pentsatzen dugu? kateak ez du bere burua, baina gisa da, esate baterako, Alice erakusleak. Eta, ondoren, Alice erakuslea beste bat izan daiteke, izen batekin hasten A. Eta Bob benetan doa hona. Eta ez beste izen bat hasten bada B, eta ondorioz sortu zen hemen. Eta beraz, elementu bakoitzaren taulan bi, diseinatu badugu, hau little more cleverly - goazen - diseinatu dugu, apur bat gehiago baldin bada cleverly, orain bihurtzen moldatzaile datuak bat egitura, han gogor muga ez da zenbat elementu txertatu dezakezu bertan egiten baduzu duelako talka bat, hori da isuna. Just joan aurretik, eta erantsi zer pixka bat duela ikusi genuen lotuta zerrenda gisa ezagutzen da. Beno dezagun pausa une bat besterik ez da. Zer talka probabilitatea da lehenik? Eskubidea, agian baino gehiago ari naiz pentsatzen agian Naiz arazo hau ingeniaritza baino gehiago dut, badakizu zer delako? Bai, etorri ahal izango dut arbitrario Off nire burua goiko adibide bezala Allison eta Aaron, baina, egia esan, Emandako uniformea ​​banaketa sarrera, hau da, ausazko sarrerak batzuk Datuen egitura batean sartzen da, zer da benetan talka probabilitatea? Beno bihurtzen da, egia da, super altua. Let me orokortu honetan Arazo hau da. Beraz n gela batean CS50 ikasleek, zer probabilitatea gutxienez bi gela ikasleak berdina urtebetetzea? Beraz, ez da egiten. gutxi batzuk hund - 200, 300 pertsona eta hemen hainbat ehun etxean, gaur egun jendea. Beraz, bada, geure buruari galdetu behar zer nahi duzu bi pertsona probabilitatea gela berean urtebetetzea izatea, hori irudikatu ahal izango dugu. Eta benetan erreklamatzeko dut bi bereko urtebetetzea dute. Esate baterako, ez du inor izan urtebetetzea gaur? Atzo? Bihar? Ondo da, beraz banoa bezala sentitzen da 363 hau edo hori egiteko gehiago dute aldiz benetan irudikatu Hala bada dute talka. Edo, besterik ezin dugu egin, matematikoki baizik tediously baino hau egiteko. Proposatu eta honako hau. Beraz, hori ezin dugu eredua proposatzen dut bi pertsona izatea probabilitatea 1 probabilitatea urtebetetzea gisa berean ken bat ez izatearen probabilitatea berean urtebetetzea. Beraz, hori lortzeko, eta, hori besterik ez da Fancy hau idazteko modu bat, egiteko aretoan, lehenengo pertsonan, berak posible bat da edozein izan daiteke, urtebetetzeak 365 egun suposatuz urtean, pertsonen apologies batekin Otsailaren 29an, urtebetetzea. Beraz, gela honetan lehen pertsonan doakoa da urtebetetzeak kopurua alguna 365 dira, aukera hori, beraz, egiten duten 365 banatzen dugu 365, bat da. Gelan pertsona ondoan, helburua bada da talka saihesteko, soilik izan du bere urtebetetzea nola hainbat egun posible? 364. Beraz, adierazpen hau terminoa da bigarrena funtsean, matematika egiten duten Gurekin Off kenduz bat posible da egunez. Eta gero, hurrengo egunean, hurrengo egunean, eta hurrengo behera kopuru osoaren eguna gelan pertsona. Dugu, eta, ondoren, uste baduzu, orduan, zer da guztiek ez izatearen probabilitatea berezia urtebetetzeak, baina berriro ken 1 duten, zer gara adierazpena da hori oso fancifully itxura hau. Baina interesgarria da bisualki begiratu. Hau taula bat, non x ardatzean da pertsonen kopurua, gela batean, urtebetetzeak kopurua. Y ardatzean probabilitatea da talka bat, bi pertsona urtebetetzea berdinak izatea. Eta kurba honetatik aurrera eramateko da bezain laster, 40 lortu nahi duzula ikasleek, sortu bazara% 90eko probabilitatea at combinatorically bi pertsona edo gehiago izatea, berean urtebetetzea. Eta behin 58 pertsona da lortu nahi duzun ia 100 aukera bat, bi,% gelan Jendeak dute joan urtebetetzea berean, nahiz eta ez dago 365 edo 366 posible kuboak, eta bakarrik 58 gela dute. Just estatistikoki litekeena bazara talkak lortzeko, eta horrek, azken finean eztabaida hau motibatzen. Nahiz eta hori Fancy dugu hemen, eta hasteko kateak horiek izatea, eta oraindik ari gara talka izan da. Beraz, galdera da begs, zer da sarrerak eta ezabatzeak egiteko kostua hau bezalako egitura datuak bihurtu? Beno dit proposatuko - eta utzi atzera me pantaila baino gehiago Hemen - dugu elementu galtzen n zerrenda, eta, beraz ari gara txertatzen saiatzean n elementu, eta dugun zenbat osoaren ontziak? Demagun guztira 31 ontzi urtebetetzeak kasuan. Zer ko gehienezko luzera da kateak hauek potentzialki du? 31 berriro ez da posible bada batean emandako hilabete urtebetetzeak. Eta besterik ez gara guztion clumping - benetan duten ergelak adibide bat da. Egin dezagun 26 ordez. Hala bada, benetan izan duten pertsonen izenak Z bidez hasiko da, eta, beraz, uzten aukerak 26 digu. Eta datu-egitura bat erabiltzen ari garen bezala Batetik, ikusi besterik ez dugu, horregatik dugu erakusle bat array, eta horietako bakoitzean bati lotuta zerrenda, puntu Lehenengo zerrenda guztiontzat izena Alice batera. Bigarren zerrendan behin egiten da Izen bat hasita, hasita B, eta abar. Zer bakoitzaren iraupena, litekeena da dutenen zerrendak onartzen dugu nice garbi bat bada A Z bitartez izen-banaketa Datu-egitura osoan zehar? Ez n datuak egitura pertsona 26 banatzen ari dira nicely bada hedatzen osoan Datuen egitura. Horietako bakoitzaren iraupena, beraz, kateak N 26 arabera banatuta. Baina O big idazkera, zer da hori? Zer da benetan? Beraz, benetan besterik n, ezta? Dugu iraganean delako esan, ugh haustura 26 duzu. Bai, egia esan azkarragoa da. Baina teorian, ez da, funtsean, azkarrago duten guztiak. Beraz, ez dugu askoz ere, badirudi hori guztia izateko to Santo Grial hau hurbilago. Izan ere, hau da, besterik gabe, denbora lineala da. Arraioa, puntu honetan, zergatik ez dugu erabili handi bat lotuta dago zerrendan? Zergatik ez erabili besterik ez dugu erraldoi bat array izen gordetzeko gela guztiek? Beno, hor dago oraindik ere, zerbait hash taula bat sinesgarria buruz? Hor dago, oraindik ere, zerbait sinesgarria datu-egitura baten inguruan duten itxura hau? . Honetan Ikaslea: [INAUDIBLE]. HIZLARIA: 1 Eskuin, eta berriro bada, besterik ez da denbora lineal batean bildu, eta lineal denbora egitura, zergatik ez dut besterik gorde guztion izen handi batean array, edo handi bat lotuta dago zerrendan? Eta gelditzeko CS egiten, beraz, askoz zailagoa behar baino gehiago izango da? Zer da hau buruzko sinesgarria, are urratzen dut, nahiz kanpoan? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 sarrerak ez dira? Garestia izango. Beraz, sarrerak potentzialki Could oraindik etengabeko denbora izango da, nahiz eta zure datuak egitura honen itxura, array baten erakusleak, eta horietako bakoitzak da seinalatuz potentzialki loturiko zerrenda bat. Nola liteke etengabeko lortzeko denbora izenak txertatzeko? Itsasten du aurrean, ezta? Sakrifikatu dugu, diseinuaren helburu bat bada lehenago, non gorde nahi izan dugu, guztion izenean, adibidez, ordenatuta, edo etapa zenbaki guztiak ordenatuta, Suposatzen dugula bat Sailkatu lotuta zerrenda. Besterik ez zaizu kostatuko gurekin bat edo bi urrats, Ben eta Brian kasuan bezala lehenago, elementu bat txertatzeko at zerrendaren hasiera-hasieratik. Beraz, bada, ez dugu guztiak ordenatzeko zaintzeko izenak hasita A edo guztiak izenak B hasita, oraindik ere lortzeko, etengabeko denbora txertatzeko. Orain begira Alice edo Bob edo izena edozein oro har, gehiago da oraindik, eta zer? Big n O 26 arabera banatzen da, eta hasi da ideal kasuan, non guztion uniformeki banatzen da, han asko da, A-ren daude Z horrek, hau da, ziurrenik gisa unrealistic. Baina oraindik ere, lineala. Baina, hemen, itzuliko gara puntu idazkera asymptotic izatearen teorikoki egia. Baina mundu errealean, erreklamatzeko galtzen dut nire programa zerbait 26 aldiz egin dezakezu zurea, eta bere programa baino azkarrago dira joan erabiliz nahiago duzu? Zurea edo nirea, eta horrek da 26 aldiz azkarragoa? Errealistan, pertsonaren 26 da aldiz azkarragoa da, nahiz eta teorian bada gure algoritmoak berean exekutatu asymptotic denbora exekutatzen. Let desberdin bat proposatu zidan irtenbide elkarrekin. Eta hau ez bada putz zure kontuan, ari gara datuak egiturak. Beraz, hau da trie bat - ergel bat izen mota. Dator jaitsieren ondorio da, eta hitza ondo idatzita trie, t-r-i-e, delako Ikastaro berreskuratze trie bezalako soinuak. Baina hori historia da hitza trie du. Beraz trie bat da, hain zuzen ere, zuhaitz mota batzuk, eta, gainera, ez da hitz joko bat. Eta nahiz eta ezin duzu ikusi nahiko bistaratzea, hau da, trie bat da zuhaitza egituratuta, familia zuhaitz bat bezala Gehien bat, eta asko at arbaso bilobak eta handia biloben behean gisa uzten. Baina trie bat nodo bakoitzean array bat da. Eta array bat da - eta dezagun une batez oversimplify - oso bat array, kasu honetan, tamaina 26, non nodo bakoitzean berriro tamaina sorta bat da 26, non duten elementu zeroth du array bat adierazten du, eta azken hala nola, bakoitza elementu array adierazten Z. Beraz, proposatzen dut, gero, datu hori egitura, trie bat bezala ezagutzen, ezin izango Gainera, hitz gordetzeko. Une bat duela ikusi dugu nola gorde izan dugu hitz, izen edo kasu honetan, eta guk lehenago ikusi nola zenbakiak gorde ahal izango dugu, baina izen edo kateak ikuspegia ematen badiogu Hemen, nabarituko zer interesgarria. Izena Maxwell dela aldarrikatzen dut Datu egitura honen barruan. Non Maxwell ikusten duzu? Ikaslea: [INAUDIBLE]. HIZLARIA: 1 ezkerrean. Beraz, zer da hori duen datu interesgarri egitura baizik dendan baino katea M-A-X-W-E-L-L backslash zero guztiak contiguously, zer egin duzu ordez jarraitzen ari da. Datu egitura bezala trie bat bada, eta horren nodo bakoitzean berriro array bat, Maxwell eta gorde nahi duzun lehenengo indizea, eta, beraz, erro-nodoa du, beraz, , hitz egiteko lehenbiziko nodoak, kokapena M, eskuinera, beraz, at gutxi gorabehera erdi-erdian sartu. Eta gero, hortik aurrera, jarraitu duzu Umearen nodo bat erakuslea, nolabait esateko. Beraz, familia zuhaitz zentzu, jarraitu duzu beheranzko. Eta eramaten zaitu beste nodo Ezkerraldean dago, hau da, on besterik array bat. Eta, ondoren, nahi duzun Maxwell gorde nahi izanez gero, erakuslea dela adierazten aurkituko duzu Bat, hau da, hemen. Gero, joan hurrengo nodoak duzu. Eta abisua - horregatik irudi horrek apur bat engainatzen - nodo hau begiratzen super txiki-txiki. Baina honen eskubidea Y eta Z. da Honez besterik ez du egileak moztu egin du argazki zu benetan gauzak. Bestela irudi hau izugarri zabala izango litzateke. Beraz, orain indizea kokapena X sartu eta, ondoren, W, E Ondoren, orduan L, orduan L. Orduan, zer jakin-mina da hau? Beno, ari gara berri-mota hau erabiliz gero hartzen nola kate bat gordetzeko batean Datuen egitura, oraindik ere, behar duzu funtsean, egiaztatu off datuen egitura, hitz baten amaiera hemen. Alegia, nodo horietako bakoitzean nolabait esateko, ez du gogoratzen dugu hori benetan jarraitu erakusleak horiek guztiak dira, eta pixka bat utzi ogia behean hemen honen mamia at egitura M-A-X-W-E-L-L adierazi behar da hain zuzen ere, datu egitura honetan. Beraz, hori egin dezakegu, honela. Irudian dugu nodo bakoitzean zerra bat du, tamaina 27 sorta bat. Eta, orain dela 27 p girotutako sei delako, benetan dugu emango dizu Komatxo bat, beraz, O'Reilly izenak izan dezakegu apostrophes eta beste batzuk. Baina ideia bera. Elementu horietako bakoitzaren array egitura bat puntu nodoa da, beraz nodo bat. Beraz, hau da, oso gogora gure zerrendan lotuta dago. Eta, ondoren, boolear bat daukat, eta hori dut deitzeko hitza, hau da, besterik gabe, izango da egia bada hitz bat honetan amaitzen da Zuhaitz nodo. Eraginkortasunez adierazten ditu gutxi triangelu une bat duela ikusi dugu. Beraz, bada hitz bat nodo hori amaitzen Zuhaitz, hitza eremu hori egia izango da, hau da, kontzeptualki off egiaztatuz, edo, hiruki hau marrazten ari gara, bai, han Hitz bat da hemen. Beraz, hau trie da. Eta orain, galdera da, zer da bere iraupena? Da big n O? Zerbait gehiago da? Beno, zuk izen n datuak honetan egitura, Maxwell bat besterik ez izatea horiek, zer exekutatzen denbora da edo txertatu Maxwell aurkitzeko? Zer exekutatzen denbora da Maxwell sartzen? N ez da beste izen bada jada taulan? Bai? Ikaslea: [INAUDIBLE]. HIZLARIA 1: Bai, luzera da izena, ezta? M-a-x-w-e-l-l, beraz, sentitzen atsegin dute hau, beraz, algoritmoa big zazpi O da. Baina, noski, izen luzera izango du aldaketarik. Agian izen labur bat da. Agian, jada izen bat da. Baina, zer gertatzen da hemen gakoa da zenbakia konstante bat da. Eta, agian, ez da benetan etengabea, baina jainkoa, errealistan bada, batean hiztegia, ez da, ziurrenik, muga batzuk letra kopurua batean Pertsona jakin bat herrialde batean izena. Eta, beraz, bere gain hartu ahal izango dugu balioa konstante bat da. Ez dakit zer den. Seguruenik handiago baino uste dugu. Beti delako txoko batzuk luze bat ero izena kasua. Hargatik deitu k, baina oraindik ez da etengabeko ustez, behin delako munduko izendatzea, gutxienez batean bereziki herrialde, luzera edo da laburragoa da, eta, beraz, etengabeko da. Baina, esan dugun zerbait da big Konstante bat, balio O, zer da hori benetan baliokideak? Hori da benetan gauza bera etengabeko denbora esaten gisa. Orain tranpa mota gara, ezta? Teoria batzuk aprobetxatuz mota gara Hemen ondo, k ordena da esatea Benetan bakar Agindua, eta etengabeko denbora da. Baina benetan. Tekla ezagutzeko hemen delako da dugu izen n dagoeneko honetan Datuen egitura, eta guk Txertatu Maxwell, zenbat denbora gurekin behar izaten da Maxwell sartu kaltetutako guztiak zenbat pertsona batzuek datu egitura dutenak? Ez omen du izan. Nuen bat milioi gehiago nahi izanez gero, elementu hau trie, eta, ondoren, Maxwell sartu da, eragina zuen? N º Eta hori da, egun edozein datuak ez bezala da egitura ikusi dugu, beraz, orain arte, eta bertan, zure denbora algoritmoa exekutatzen da erabat zenbat independentea Gauza da, edo ez da jada Datuen egitura horretan. Eta, beraz, honekin batera ematen da, orain duzu p jaurtiketa sei, eta horrek aukera izango du berriro ere inplikatzeko zeure ezartzeko zuzentzaileari, 150.000 irakurketa hitzak, nola onena duten gordetzeko ez da, nahitaez, argi geratu da. Eta ez dut nahi baina aurkitu Santo Grial, ez dut erreklamatzeko trie bat da. Izan ere, hash taula bat oso ondo frogatzeko askoz eraginkorragoa izango da. Baina besterik ez dira - Hori besterik diseinuan erabakiak bat dute egin nahi izango. Baina itxi batean dezagun, beraz, 50 edo segundo zer datza begiratu bat eman nahi aurretik, eta hurrengo astean dugu trantsizioa haratago komando-lerro honetatik mundu C bada gauzak web-programak oinarritzen da, eta PHP bezalako hizkuntza eta Ikusteko Javascript-a eta internet bera, HTTP protokoloak, zeinak dituzun hartu urtez emandako orain, eta idatzitako gehienak egunero egun, agian, edo ikusi. Eta atzeko azala hasiko gara zer geruza internet da. Eta zer kodea duten azpian, gaur egungo tresnak. Beraz, 50 esaldi hau segundotan hemen. Ematen dizut Sare Warriors. [Bideo-erreprodukzioa] -Heldu zen mezu baten bidez. Protokolo bat bere guztiekin. Etorri suebakien cruel mundu bat zen, uncaring router, eta arriskuak urrun heriotza baino okerragoa. Azkarra da. Indartsua da. TCPIP da. Eta berak lortu da zure helbidea. De garbiak Warriors. [END bideo-erreprodukzioa] HIZLARIA 1: Hau da Internet izango da hurrengo aste bezala lan egiten.