[Musika jotzen] DAVID J. MALAN: Ondo da. Hau CS50 da. Hau da, astean bost jarraitu zuen, eta guk zenbait albiste ona eta albiste txarra batzuk. Beraz, albiste ona da CS50 Ostiral honetan abian. Gurekin bat egin nahi baduzu, ohiko URL hemen joatea. Berri hobea, hitzaldia ez datorren astelehenean 13an. Zertxobait gutxiago Berri hobea, galdetegi zero hurrengo asteazkenean da. Ondorengo datuak ere izan daiteke URL hau hemen aurki. Eta bikote hurrengo egunetan zehar ditugun hutsuneak egingo betez gelak dagokionez dugun gordeak izango dituzte. Albiste hobe da han egingo duten Jakina-zabal berrikuspen bat izan Saio honetan datozen Arratsaldean, astelehena. Stay ikastaroa egin dute adi kokapena eta xehetasunak ezagutzeko. Sailak, bat badago ere Oporretan, ere bilduko baita. Berri Best, hitzaldia datorren ostiralean. Beraz, hau tradizio dugu bat da , dute curriculumaren arabera. Besterik ez da harrigarria izango. Bezalako gauzak ikusiko duzu Etengabeko denbora datuen egitura eta hash taulak eta zuhaitz eta saiatzen da. Eta egingo urtebetetzea arazoei buruz hitz egiten dugu. Stuff sorta osoa zain dago datorren ostiralean. Ados. Dena dela. Beraz, gogora ekarri ditudan izan gara zer da irudi hau bideratua gure ordenagailuaren memoria barruan. Beraz, memoria edo RAM non programak da existitzen horiek exekutatzen ari zaren bitartean. Duzu bat bi klik eginez gero ikonoa programa batzuk exekutatu edo egin klik bikoitza icon fitxategia batzuk irekitzen dira, nik zure gogorrean kargatzen gidatzeko edo egoera ona drive RAM, Random Access Memory, non sartu bizi da boterea doa off arte, Eramangarriaren tapa ixten, edo programatik irten zaitezke. Orain memoria hori, batzuen ziurrenik behar duzu Egun hauetan 1 gigako, 2 gigabyte, edo are gehiago, askoz gehiago, oro har ezarritako programa jakin batean angeluzuzen moduko honetan Eredu kontzeptuala Horren bidez, pila ditugu behealdean eta beste gauza mordo bat goialdean. Oso goian gauza Nik argazki hau ikusten dugu aurretik, baina inoiz ez buruz hitz egin zuen testu segmentu deiturikoak da. Testu segmentu fancy modu bat besterik ez da zeroen eta bai esaten duen Zure benetako konpilatutako programa konposatzen. Beraz, bi klik eginez Microsoft Word, zure Mac edo PC, edo noiz dot exekutatzen duzun barra Mario batean Linux zure terminal leihoa ordenagailu, osatzen duten zeroen eta bai Word edo Mario aldi baterako gordetzen dira Zure ordenagailuaren deiturikoak ere RAM programa jakin baten testu segmentu. Doan Jarraian hasieratu eta datuak uninitialized. Hau aldagai global bezala stuff da, Nik ez dugula erabiltzen askok, baina behin ditugu aldagai global izan edo estatikoki definitzen kateak gogor kodetuta dago bezala "hello" hitzak Ez diren hartu diren erabiltzaileak eta horrela, zure programan sartu zatekeen. Orain, behealdean behera dugu pila deiturikoak dute. Eta pila, beraz, orain arte, izan gara zer helburu mota erabiliz? Zer da pila dira erabiltzera? Bai? IKUSLEEN: funtzioak. DAVID J. MALAN: funtzio For? Zer zentzu funtzioak egiten direnean? IKUSLEEN: funtzio bat deitzen duzu, argudio pila gainean kopiatzen. DAVID J. MALAN: Zehazki. Funtzio bat deitzen duzu, bere argudio pila gainean kopiatzen. Beraz, X edozein edo Y-ren edo A-ren edo B-ren funtzio bat sartu duzula pasatzen ari aldi baterako jartzen diren pila deiturikoak, besterik Annenberg bat bezala jantokia erretiluak, halaber, gauzak eta aldagai lokalak bezala. Bada zure foo funtzioa edo zure swap funtzioa dute aldagai lokalak, temp bezala, bi horiek azkenean, pilan. Orain, ez dugu hitz gehiegi gauza askorik horiek, baina, ingurune-aldagai horiek behealdean, berriz, duela ikusi dugu Teklatuaren egun batean egiten dut futzing zen eta gauzak sartzean hasi nintzen argv 100 edo argv 1.000 bezala, besterik elementuen ahaztu dut zenbakien du baina horrek ez ziren ustezko me beharreko sar. Batzuk ikusten hasi ginen, pantailan funky sinboloak. Horiek ziren llamado inguruneko aldagaiak ezarpen global bezala nire programa edo nire ordenagailuan, ez dagoen berrienak zerikusirik bug duten aztertu ditugu, Shellshock, hori izan da ordenagailuak batzuk nahiko plaguing. Orain, azkenik, gaur egungo gertutik azken finean zaitugu zeure gainean izan. Hau zatia memoria bat da. Eta, batez ere, hori guztia memoria gauza bera da. Hardware bera da. Besterik ez gara ordenatzeko klusterrak desberdinak tratatzeko ren helburu ezberdinetarako byte. Arazoak izaten ari da, baita ere bertan izango da aldagaiak eta memoria zuk eskatu duten sistema eragilearen aldi baterako gordetzen da. Baina ez da arazo bat mota Hemen, irudi gisa dakar. Ordena ditugu bi buruz itsasontziei talka. Gero eta gehiago erabiltzen duzun bezala delako gaur egun ikusten dugun pilaren, eta gisa aurrerantzean, gero eta gehiago erabiltzen duzun bezala zeure, ziur aski gauza txarrak gerta liteke. Eta hori ere bultzatu ahal izango dugu nahita edo nahi gabe. Beraz cliffhanger azken denbora programa hau izan zen, eta ez dute balioko funtzionalak edozein helburua beste frogatu baino nola ahala tipo txarra benetan hartu ahal bugs abantaila norbaiten programan eta hartu baino gehiago, programa bat edo are informatika-sistema osoa edo zerbitzari. Beraz, begiratu besterik ez labur-labur, zuk behealdean nagusia nabarituko Komando lerro hartzen argumentuak, argv bakoitzeko. Eta f funtzioa dei bat du, funtsean izeneko izenik gabeko funtzio bat f, eta argv ari da pasatzen [1]. Beraz, edozein izanda ere hitza erabiltzaile at motak Programa honen izenaren ondoren gonbitan, eta gero arbitrarioa funtzio hori sortu top, f, kate bat hartzen du, AKA char *, Nik hasia dugu eztabaidatu bezala, eta "bar." deiak besterik ez da Baina ez dugu ezer deitu daiteke. Eta gero deklaratzen da, barruan f, karaktere array baten 12 karaktere esaterako bc izenekoa. Orain, istorioa kontatu nuen Duela momentu bat, non memoria c da, edo horiek 12 karakteretan amaituko da? Just argia izan. Bai? IKUSLEEN: pilan. DAVID J. MALAN: pilan. Beraz, c tokiko aldagai bat da. Dugu 12 chars edo 12 byte eske ari. Horiek, azkenean joan dira pila deiturikoak. Orain, azkenik, beste funtzio hori da hori nahiko baliagarria da benetan, baina ez benetan erabiltzen dugun geure burua, strncopy. Katea kopia esan nahi du, baina gutunak, n karaktere bakarra n. Beraz, n pertsonaiak izango bar kopiatu c sartu. Eta zenbat? Bar luzera. Beraz, beste era batera esanda, hori lerro bat, strncopy, hau kopiatu joan eraginkortasunez bar in c. Orain, besterik gabe, mota horretako aurreratzen istorio honen morala, zer da problematikoa potentzialki hemen? Luzera ikusten ari garen arren bar eta pasatuz strncopy sartu, zer da zure gut diozu da oraindik ere programa honi buruz hautsita? Bai? IKUSLEEN: ez dira null karaktere gela. DAVID J. MALAN: ez dira null karaktere gela. Potentzialki, ez bezala iraganeko praktika ez dugu, nahiz eta hainbeste plus 1 gisa egokitzeko null pertsonaia hori. Hala ere, hori baino okerragoa da. Zer gehiago ari gara egin ezean? Bai? IKUSLEEN: [INAUDIBLE] DAVID J. MALAN: Perfect. Nik gogor kodetuta dugu 12 nahiko arbitrarioki. Hori ez da horrenbeste Arazoa, baina, hain zuzen, ez gara ari egiaztatzen duen bar luzera 12 baino txikiagoa da; eta kasu horretan izan da joan jartzea memorian sartu seguru c deitzen duten esleitu dugu. Izan ere, bada bar bezalakoa da 20 karaktereko luzera, funtzio honetan agertzen kopiatzea nahi Bar c sartu eta, horrela, 20 karaktere gutxienez 8 byte hartzen behar ez dela izango. Hori inplikazioa da hemen. Labur, programa hondatutako beraz. Ez da big aurre. Agian segmentaziuo hutsegitea bat lortuko duzu. Guztiak izan genuen programetan bugs. Baliteke Denok bugs dute oraintxe programetan. Baina zer inplikazioa? Beno, hemen handitutako-en bertsio bat nire ordenagailuaren memoria irudi hori. Hau nire pila behealdean dago. Eta hain zuzen ere, oso behean dago zer da guraso errutina pila deitzen, fancy modu ren esanez hori da nagusia. Beraz duenak funtzioa deitzen f buruz hitz egiten ari gara. Beraz, hau pila behealdean dago. Return helbidea zerbait berria da. Beti egon da, beti irudi hori izan da. Inoiz ez besterik ez dugu arreta deitzen du. Bihurtzen delako C da funtzio bat beste deiak, duten argudioak ez bakarrik egin Funtzio get pila gainean bultzatu, Ez bakarrik ez Funtzio horrek tokiko aldagai get pila gainean bultzatu, bueltan helbide bat zerbait izeneko halaber pila gainean jarri denean. Hain zuzen ere, nagusia deiak foo bada, nagusiaren memoria-helbide propioa, idi zerbait, eraginkortasunez lortzen pila gainean jarri exekutatzea, beraz, f egiten da non atzera joateko testuan daki agindua gauzatzeko jarraitzeko segmentuan. Beraz, hemen gaude, bada, kontzeptualki, nagusian, orduan f lortzen izeneko. Nola f daki nor eskuko kontrola itzuli nahi? Beno, txiki honetan Gorriz breadcrumb hemen, itzulera helbidea deritzo, ez besterik egiaztapen, zer bueltan helbide hori? Oh, dezagun salto me nagusiak hemen. Eta hori apur bat oversimplification bat, zeroen eta bai delako nagusiak dira teknikoki Hemen teknologiako segmentuan up. Baina hori da ideia. f besterik ez du, zer jakin nahi nora kontrola, azken finean, atzera doa. Baina modu ordenagailuen aspalditik ezarritako gauzak aldagai lokalak bezala eta Argumentu hau bezalakoa da. Beraz, argazki honen goiko aldean dauden urdin pila f markoa ez den guztia memoria duten f zehazki da erabiliz. Beraz, horren arabera, nabarituko bar irudi honetan. Bar bere argumentua izan zen. Eta aldarrikatu dugu argumentuak duten funtzio get pila gainean bultzatu. Eta c, noski, gainera, irudi honetan. Eta besterik notational helburuetarako, goiko ezkerreko izkinan at nabarituko da zer c tarte 0 izango litzateke eta gero apur eskubidea behera c bracket 11 da. Beraz, beste era batera esanda, ezin duzu imajinatu ez dagoela byte sare bat da Han, lehenengo dagoen huraxe goiko ezkerreko, beheko horietatik 12 byte horiek azken da. Baina orain saiatu azkar aurreratzeko. Zer da buruz pasatzen badugu gertatuko katea barra bat hori da c baino luzeagoa? Eta ez gara datozen egiaztatzen hain zuzen ere 12 baino luzeagoa da. Zein zati irudi hau da, joan den get gainidatzi byte 0, 1, 2, 3, dot dot dot, 11, eta, ondoren, txarra, 12, 13 19 bidez? Zer gertatuko da joan, infer ordena batetik bada c duen tarte 0 gainean eta c bracket 11 moduko behera eskubidea? Bai? IKUSLEEN: Ba, joan da char * barraren gainidazteko. DAVID J. MALAN: Bai, itxura Char * bar gainidatzi joan zaren. Eta okerrago, benetan luze bat bidali nahi izanez gero katea, agian are gainidatzi zer? The erantzunak emateko. Zein, berriro ere, besterik ez da bat bezala breadcrumb programan bertan kontatzeko itzuli denean f joateko Ari deitu egiten da. Beraz, zer guys txarra normalean egin dagoen programa bat aurkitzen badute Bitxia ala ez ari dira ustiatzeko, modu bat, buggy berak har dezake bug duen abantaila, oro har, ez dute lortu Eskubide hori lehen aldiz. Hasten dira, besterik gabe, bidaliz adibidez, zure barruan ausazko kateak, teklatua ala ez, edo Egia dute seguruenik programa txiki bat idatzi besterik ez Kateak automatikoki sortuko, eta zure programa banging arabera Sarrerek desberdinak asko jartzen ari da luzerak desberdinetan. Bezain laster, zure programa bat kraskatzen gisa, duten gauza harrigarri bat. Esan nahi duelako edo aurkitu ditu zer da, seguruenik, hain zuzen ere akats bat. Eta gero, gehiago clever eskuratu ahal izango dute eta gehiago hertsiki bideratua hasteko bug hori nola ustiatu ahal izateko. Hain zuzen ere, zer zuen agian egin da bidali, kasurik onenean ere, kaixo. Big aurre ez. Kate hori behar bezain laburra da. Baina zer zuen bidaltzen badu, eta hura orokortu egingo dugun bezala, eraso zero beraz, kode eta bai hori egin gauzak rm-rf bezala, dena kendu disko gogorra edo spam bidali edo nolabait eraso makina? Beraz, horietako bakoitzean bada hizki bat adierazten du, kontzeptualki, eraso, eraso, eraso, eraso, txarra kodea batzuk beste norbaitek idatzi du, baina pertsona hori smart nahikoa bada ez bakarrik arte guztien artean, horiek rm-RFS, baina baita bere azken byte gutxi izan dagokion zenbakia izan helbidea idatzi, bere edo bere eraso propioak kodea besterik ez zuen hori gainditu beti ere gonbitan arabera, eraginkortasunez dezakezu ordenagailua engainatu f exekutatzean egina dagoenean ohartu sartu, oh, salto me denbora da Bueltan gorria helbidea itzuli. Baina berak nolabait duelako bueltan helbide hori gainjarria haien kopurua propioa, eta smart ari dira nahikoa konfiguratuta izan duten , erreferentzia zenbakia ahala super top ikusten ezkerreko izkinan han, Benetako ordenagailuaren helbidea da bere erasoa kodea batzuen memoria, tipo txarra ordenagailua engainatu bere kabuz kodea exekutatzean sartu. Eta kode hori, berriro ere, ezer izan daiteke. Honez deritze- shell kodea, besterik ez da ez dela esateko modu bat oro har, zerbait gisa rm-rf bezain erraza. Benetan da Bash antzeko zerbait, edo benetako programa bat ematen zion edo exekutatu bere programazioko kontrol Beste ezer nahi dutela. Beraz, azken finean, honek guztiak Izan ere, simple eratortzen inplikatutako bug hori ez egiaztatzea Zure array mugak. Eta bide delako ordenagailuak lana hauxe litzateke: tik pila erabili eraginkortasunez, kontzeptualki, behetik gora, baina, ondoren, elementu bultza pila gainean hazten top down, hau oso problematikoa. Beno, honen inguruan lan egiteko modu daude. Eta Egia, badira hizkuntzak zein batera honen inguruan lan egiteko. Java immunologikoa da, esate baterako, gai jakin horri. Ez dute erakusleak eman duzulako. Ez dute ematen dizute memoria zuzeneko helbideak. Beraz, eskumen hori dugula ekin ezer ukitzeko oroimenez nahi ateratzen dugu, admittedly, arrisku handia. Beraz, begi bat mantendu. Bada, Egia, hilabeteetan , edo urte etorri nahi anytime irakurri duzu ustiapen batzuei buruzko programa bat edo zerbitzari bat, Inoiz ikusi duzu zerbait iradokizun bat bada buffer gainezkatzea erasoa bezala, edo pilaren gainezkatzea mota bat da Eraso, espiritua antzekoak, askoz inspiratzen web hamarkadan izendatzeko, ezagutzen baduzu, hori guztia, besterik gabe, buruz hitz egiten pertsonaia batzuk tamaina gainezka array edo array batzuk gehiago, oro har. Edozein galdera, eta gero, hau? Ez saiatu etxean. Guztiak eskubidea. Beraz, malloc beraz, orain arte gure berri izan Lagun horretan memoria esleitu ahal izango dugu ez dugu zertan jakin batean aurrera, beraz, ez dugu nahi dugun sartu kodea gogorrean gure 12 bezalako programa zenbakiak. Erabiltzaileari esaten digu behin zenbat Datu berak nahi duen sarrerari, askoz memoria malloc dezakegu. Beraz, malloc bihurtzen da, izateko neurritan izan dugu berau erabiliz, esplizituki azken aldiz, eta, ondoren, you guys erabili dute unknowingly GetString egiteko zenbait aste, malloc memoria guztiak zeure deiturikoak dator. Eta horregatik GetString, esate baterako, memoria dinamikoki esleitu ahal zertan ari zaren jakin gabe aldez aurretik idazten joan, atzera entregatu erakuslea memoria horretan, eta memoria hori zurea da, oraindik ere mantendu, are itzultzen GetString ondoren. Zeren abisuaren finean hori pila etengabe ari da gora eta behera joan, gora eta behera. Eta doa bezain laster behera, edozein memoria esan nahi erabili funtzio hau egin beharko lukete ez da beste norbaitek erabil. Zabor balioak da orain. Baina arazoak izaten ari da hemen. Eta zer polita buruz malloc dela malloc memoria bideratzen denean hemen, Ez da eragin, egiteko Zati handiena, pila arabera. Eta beraz edozein funtzio sartu ahal izan dela malloc'd memoria, are GetString bezalako funtzio bat, bertan itzuliko da ondoren ere. Orain, malloc of converse doakoa da. Eta hain zuzen ere, arau duzu zietenean hasi beharko dagoen edozein, edozein, malloc erabili duzun edozein unetan doan erabili behar duzu zeure burua, azkenean, erakuslea berean. Denbora horretan guztian dute idazten dugu sido buggy, buggy kodea, arrazoi askorengatik. Baina horietako bat izan da CS50 liburutegia erabiliz, eta horrek berak nahita da buggy, memoria filtrazioak da. GetString izeneko duzun Edonoiz iragan asteetan zehar eragilearen galdetzen ari gara sistema, Linux, memoria da. Eta inoiz ez duzu behin harekiko zor. Eta hau ez da, in landu, gauza ona da. Eta Valgrind, bat pset 4 sartu diren tresnak, guztia laguntzen buruz orain horrelako bugs aurkitu. Baina zorionez Pset 4 ez duzu behar CS50 liburutegia edo GetString erabili. Beraz, memoria lotutako edozein bugs dira azken finean, zeure izango. Beraz, malloc baino gehiago da Horretarako komenigarria. Benetan orain konponduko dugu arazoak funtsean ezberdinak, eta funtsean, arazoak konpontzeko gehiago eraginkortasunez astean zero promesa arabera. Horrela, orain arte hau sexiest da datu-egitura izan dugu. Eta datu-egitura by esan nahi dut kontzeptualizatzeko memoria modu bat hori besterik esaten haratago doa modu batean, hau int bat da, hau char bat da. Kluster gauzei batera hasi ahal izango dugu. Beraz, array bat dirudi. Eta zer izan zen inguru batean gakoa array da zuk ematen dion back-to-back zatiak memoria, eta bakoitzak bere da mota bereko izango da, int, int, int, int edo char, char, char, char. Baina bada downsides batzuk bat da. Hau adibidez, tamaina sei array bat. Demagun sei array hau bete zenbakiak eta ondoren, edozein dela arrazoiengatik, Zure erabiltzaile eman nahi du you zazpigarren zenbaki bat. Non jarri duzu? Zein da konponbidea baldin baduzu pila array bat sortu, esate baterako, besterik gabe, aste batera bi idazkera duten sartu dugu, Zenbaki baten barruan kortxete? Beno, nik zu sei hauetan dagoena zenbakiak. Zein da zure sena izango litzateke? Non litzateke jarri nahi al duzu? IKUSLEEN: [INAUDIBLE] DAVID J. MALAN: Barkatu? IKUSLEEN: Jarri da bukaeran. DAVID J. MALAN: Jarri da bukaeran. Beraz, besterik gabe, eskubidea baino gehiago, kutxa honen kanpo. Zein polita izango litzateke, baina bihurtzen da eta ezin duzu hori egin. Nik ez baduzu eskatu duelako zatia memoria honen, kointzidentzia hori idatzia izan zitekeela hau da, beste aldagai batzuk erabiltzen ari guztiz. Think atzera aste bat edo, beraz, noiz ezarri dugu Zamyla eta Davin eta Gabe-izenak out memorian. Literalki ziren back to back back. Beraz, ezin dugu zertan edozein ren fidatu hemen baino gehiago da erabili me eskuragarri. Beraz, zer gehiago egin dezakezu? Beno, behin konturatu zazpi tamaina array bat behar, Besterik ezin duzu sortu bat zazpi tamaina array, ondoren, erabili loop edo, berriz, begizta bat, kopiatu berria array, eta, ondoren, nolabait, besterik kentzeko array honetan edo, besterik gabe gelditu erabiliz. Baina hori ez da bereziki eraginkorra. Azken batean, matrizeak ez utzi dinamikoki tamainaz duzu. Beraz, alde batetik, you get ausazko sarbidea, hau da, harrigarria. Da, aukera ematen duelako gauza egin gurekin zatitzea eta konkistatzeko bezala, bilaketa bitarra, denak ere dugu aipatu pantaila hemen. Baina eskuz margotzen duzu izkina batean. Sakatu bezain laster Zure array amaieran, oso bat egin behar duzu Eragiketa garestiak edo kode sorta oso bat idatzi Arazo horrekin orain aurre. Beraz, zer ordez bada izan genuen zerrenda bat izeneko zerbait, edo lotuta zerrenda bereziki? Zer lortu beharrean, bada laukizuzenak itzuli nahirik, gutxi uzten duten laukizuzenak ditugu wiggle gela pixka haien artean ere? Eta nintzen marrazten nahiz Nik hau Irudi edo argazki hau egokitutako testuak batetik hona itzuli izan back oso ordenatua nahirik, egia esan, laukizuzenak horietako bat crear memorian izan daiteke. Horietako bat sortu hemen izan daiteke. Horietako bat sortu hemen izan daiteke, hemen, eta abarren gainean. Baina genuen zer bada, kasu honetan, geziak nolabait lotzeko horiek laukizuzenak elkarrekin? Izan ere, tekniko bat ikusi dugu, gezi bat Enkarnazio. Zer erabili dugu azken urtean egun hori, kanpaia azpian, gezi baten ordezkaria da? Erakuslea da, ezta? Beraz, zer bada ordez besterik zenbakiak gordetzeko, atsegin 9, 17, 22, 26, 34, zer bada ez gordetzen dugu Zenbaki bat bakarra baina erakuslea esaterako, zenbaki bakoitzaren ondoan? Beraz, askoz ere atsegin duzu haria litzateke oihal sorta osoa bidez orratz, nolabait tying gauzak elkarrekin, era berean, ahal erakusleak, hala egiten dugu geziak incarnated hemen, motatako ehuntzen elkarrekin banakako laukizuzenotan erakuslea eraginkorrean erabiliz Zenbaki bakoitzaren ondoan hurrengo zenbaki batzuk seinalatzen du, puntu hau, aldi berean, hurrengo zenbaki batzuk? Beraz, beste era batera esanda, zer Benetan nahi badugu honen antzeko zerbait ezartzeko? Beno, zoritxarrez, laukizuzenotan, Gutxienez 9 duena, 17, 22, eta abar, horiek ez dira jada Zenbaki bakar karratu polita. Beheko, laukizuzen 9 azpitik, esate baterako, adierazten du zer egin beharko lukete erakuslea, 32 bit izan. Orain, ez naiz oraindik datu-mota edozein jakitun C int bat, ez bakarrik ematen dizu baina erakuslea guztira. Beraz, zein da konponbidea nahi badugu Gure honi erantzuna asmatu? Bai? IKUSLEEN: [INAUDIBLE] DAVID J. MALAN: Zer da hori? IKUSLEEN: egitura berria. DAVID J. MALAN: Bai, eta horregatik hain ez dute egitura berri bat sortu dugu, edo C, egitura bat ere? Ikusi dugu structs aurretik, laburki bada, non landu ikaslea egitura bat dugu hau bezalako, nor izen bat eta etxe bat izan. Pset 3 breakout osoa bat erabili duzu structs-- GRect eta GOvals mordo Stanford Horretarako sortutako Informazio kluster elkarrekin. Beraz, zer ideia hori bera hartzen badugu keywords "typedef" eta "egiturari," eta, ondoren, ikaslea baterakoak gauza batzuk, eta eboluzionatzen honek jarraian sartu: typedef struct nodo eta nodo da besterik informatika orokorrean datu-egitura batean zerbait epe, datu-egitura batean edukiontzi bat. Nodo bat aldarrikatzen dut hori behar du int n bat, erabat sinplea da, eta, ondoren, apur bat gehiago cryptically, Bigarren lerro honetan, egitura nodo * hurrengo. Baina gutxiago termino teknikoetan, zer bigarren lerroa dela kizkur giltza barruan kodearen? Bai? IKUSLEEN: [INAUDIBLE] DAVID J. MALAN: A nodo beste erakuslea. Beraz, admittedly, sintaxia apur bat críptica. Baina hitzez hitz irakurri nahi izanez gero, hurrengo aldagai baten izena da. Zein da bere datu-mota? Luze pixka bat denbora hau da, baina mota egitura nodo da *. Ikusi dugu zerbait izar Edonoiz, hori esan nahi du datu-mota horretan erakuslea da. Beraz, hurrengo itxuraz bat egitura nodo bat erakuslea. Orain, zer egitura nodo bat da? Beno, nabarituko horiek ikusten duzu goiko eskuineko hitz bera. Eta hain zuzen ere, hitza ere ikusiko duzu "Node" behera hemen beheko ezkerreko. Eta hori da, benetan onerako besterik ez. Ohartu gure ikaslea definizioa dela Han hitza "ikaslea" behin bakarrik da. Eta hori da, ikasle bat delako kezka ez zen auto-erreferentziazko. Ez da ikasle baten barruan nothing duten beste ikasle seinalatu behar du, persay. Sort hori izango litzateke mundu errealean bitxi. Baina bat lotune batekin lotuta zerrenda, nodo bat nahi egiten dugu antzeko objektu bat erreferentziala izan nahi du. Eta beraz, nabarituko aldaketa hemen ez da besterik zer kizkur giltza barruan. Baina hitza "node" gehitu dugu goialdean baita gehituz beheraino lieu "ikasle". Eta hau xehetasun tekniko bat baino ez da beraz, berriro ere, zure datu-egitura auto-erreferentziazko izan daiteke, bat, beraz, node esaterako, beste nodo seinalatu. Beraz, zer da hau, azken finean, Gurekin esan nahi joan? Beno, bat, gauzak honen barruan gure nodoaren edukia da. Gauza hau hemen, Goiko eskuineko, besterik ez da, beraz, hori, berriz, geure burua aipatzeko. Eta gero outermost gauzak, node epe berri bat da, nahiz eta, agian, ez da oraindik ikaslea eta zer berdina SPL kanpaia azpian zegoen. Beraz nahi dugu, gaur egun, bada, hasteko lotuta zerrenda hau gauzatzeko, nola liteke itzuli gara Honen antzeko zerbait kodea? Beno, ea besterik gabe bat programa baten adibidea benetan lotuta zerrenda bat erabiltzen du. Artean, gaur egungo banaketa kodea Zerrenda Zero izeneko programa bat da. Eta hau exekutatu bada super bat sortu dut GUI simple, saguaren, baina benetan besterik ez printf. Eta orain ez dut menu bat gutxi eman neure burua options-- ezabatu, Txertatu, bilatu, eta Traverse. Eta Irten. Hauek dira bat-eragiketak besterik ez ohikoa Datuen egitura link zerrenda bat bezala ezagutzen. Orain, ezabatu da joan zerrendako zenbaki bat ezabatzeko. Txertatu Honez gehitzeko joan zerrendako zenbaki bat. Search dago begiratzen joan Zerrendako zenbakia da. Eta traverse fancy modu bat besterik ez da esaten, zerrendan zehar oinez, inprimatu, baina hori da. Ez aldatu inolaz ere. Hargatik saiatu honekin. Dezagun aurrera eta idatzi 2. Eta gero noa joan zenbakia sartu, esaten 9. Sartu. Eta orain nire programa besterik ez da programatutako esan, zerrenda da gaur egun 9. Orain, aurrera joan ahal naiz eta ez Txertatu berriro, utzi aurrera eta mapan handiago eta idatzi 17. Orain nire zerrenda 9 da, eta gero 17. Txertatu berriro egin dut bada, egin dezagun bat. Horren ordez 22koa, irudi bakoitzeko dugu dira hemen begira, aurrera salto me utzi eta sartu 26 hurrengo. Beraz, ez dut 26 idatzi behar du. Zerrenda da, espero nuen bezala. Baina orain, besterik gabe, kode hori gero ikusi da malgua izango da, let me now mota 22, gutxienez kontzeptualki, Oraindik badugu Hau mantentzea ordenatuta, eta hori da hain zuzen ere, taldeari beste gol izateko oraintxe joan, beharko joan 17 eta 26 artean. Beraz Sartu sakatu dut. Izan ere, lan egiten du. Eta, beraz, gaur egun utzi txertatu zidan azkena, argazkia, 34 per. Guztiak eskubidea. Beraz, oraingoz, utzi hau xedatu me Ezabatu eta Traverse eta bilatu egin, Izan ere, lan egiteko. Izan ere, ez dut exekutatu bada Search, dezagun bilatu 22 zenbakia da, Sartu. 22 aurkitu ditu. Beraz, horixe da hau programa zerrenda Zero ez. Baina zer da benetan gertatzen hori inplementatzen hau? Beno, lehenik eta behin agian daukat, eta hain zuzen ere, Izan dut, fitxategi list0.h izenekoa. Eta nonbait ez da hau line, typedef, egitura nodo, gero nire giltza kizkur daukat, int n, eta orduan struct-- zer zen definizioa? Egitura nodo hurrengo. Beraz, izar behar dugu. Orain teknikoki lortzeko sartu ginen hemen marrazketa ohitura. Testu-liburuak ikusi ahal izango duzu, eta online erreferentzia egiten han. It funtzionalki baliokidea. Hain zuzen ere, apur bat gehiago tipikoa da. Baina zer koherentea izango naiz Azken aldiz egin dugu eta hori egin. Eta gero, azkenik, naiz hau egin dut. Beraz Goiburu-fitxategi batean nonbait, list0.h saioa gaur struct definizio hau da, eta, agian, beste gauza batzuk. Bitartean list0c ere ez dago zenbait gauza bat izango da. Baina goaz besterik hasiko da, eta ez hau amaitzeko. List0.h artxibo bat nahi dut nire C fitxategia sartzeko. Eta gero, uneren batean nago int dute, nagusia, baliorik gabe utzi egingo da. Eta gero noa joan eduki batzuk egiteke dago hemen. Dut ere bat izan da joan prototipoa, void, bilatu, int bezala, n, eta horren helburua bizitza da bilatu elementu bat da. Eta gero behera hemen ere aldarrikatzen dut Gaur egungo kodea, void, bilatu, int, n, puntu eta koma ez, baina giltza kizkur irekia. Eta orain, nolabait bilatu nahi dut Zerrenda horretako elementu bat da. Baina ez dugu nahikoa pantailan informazio oraindik. Ez, egia esan, ez daukat zerrenda bera irudikatzen. Beraz, modu batean martxan jarri ahal izan dugu lotutako programa batean zerrenda bat mota da zerbait egin nahi dut bezala aitortzen lotuta sortu hemen zerrenda. Lana errazteko, noa egiteko hau global, are dugu, oro har, nahiz eta behar ez egin hau gehiegi. Baina adibide hau errazteko izango da. Beraz, aldarrikatu nahi dut lotuta zerrenda hemen. Orain, nola liteke hori? Hona hemen zerrenda lotuta baten irudia da. Eta ez dut benetan Oraingoz, nola jakin To ordezkari buruz joan noa bakar batera hainbeste gauza memorian aldagai. Baina uste atzera une bat. Denbora horretan guztian izan dugu kateak, eta bertan dugu, ondoren agerian array izateko pertsonaiak, bertan dugu, ondoren agerian nahiko luke erakuslea Lehen karaktere arte karaktere array bat hori nulua amaitu. Beraz, logika hori, eta honekin argazkia zure pentsamenduak seeding mota, zer dugu benetan ere idatzi behar gure kodea lotutako zerrenda bat irudikatzeko? Zenbat informazio hori egin behar dugu C kodea harrapatzeko, esango zenuke? Bai? IKUSLEEN: nodoaren erakuslea behar dugu. DAVID J. MALAN: nodo bat erakuslea. Zehazki, zein nodo litzateke zure senak izan erakuslea mantendu nahi? IKUSLEEN: lehenengo nodoa. DAVID J. MALAN: Bai, Seguru asko lehena. Eta nabarituko, lehena node beste forma bat da. Bakarrik egitura, tamaina erdia da, hain zuzen ere, erakuslea bakarra delako. Beraz, zer, hain zuzen ere egin dezakezu deklaratzeko lotutako zerrenda bat Nodo mota izan *. Eta dezagun deitu besterik ez da lehenengo eta abiarazi null. Beraz, null, berriz, datozen Irudian hemen sartu. Ez bakarrik null berezi bat bezalakoa gisa erabiltzen da bueltan GetString bezalako gauzak balioa eta malloc, nulua da, halaber, zero erakuslea, erakuslea eza, izango bada. Besterik gabe esan nahi du ezer ez da oraindik hemen. Orain lehen, nik ezin izan dut Ezer deitu. "Zerrenda" I deitu izan zitekeela edo edozein gauza batzuen kopurua. Baina deitzen naiz "lehen", beraz, lerro gora irudi honekin. Beraz, besterik gabe, kate bat bezalakoa izan daiteke bere lehenengo byte helbidea dituzten, beraz, lotuta zerrenda can. Eta beste datu batzuk ikusiko ditugu egiturak ordezkatuta egon erakuslea bakar batekin, 32-bit gezi bat, seinalatuz egituran oso lehen nodo at. Baina orain dezagun aurrea arazo bat. Bakarra naiz gogoratuz gero nire programa helbidean lehen nodoa, lehena datu egitura honetan Laukizuzena, zer hobeto buruzko kasua izan gaurko nire zerrenda gainerako ezartzeko? Zer da hori gertatzen gakoa xehetasun bat hau benetan funtzionatzen bermatzeko? Eta arabera "benetan funtzionatzen" I esan nahi, askoz kate bat bezala, lets go lehen pertsonaia gurekin Davin-ren bigarren izenean, hirugarrenean to, to the laugarren, eta amaieran oso, nola jakin Oraindik amaieran gara, ez dugu itxura hau lotuta zerrenda? Noiz nulua da. Eta sort hau irudikatzen dut Ingeniari elektriko indar bat bezala, dituen oinarri gutxirekin sinboloa da, era askotako. Baina hori besterik esan nahi kasu honetan nulua. Edozein zenbaki marraztu dezakezu formulak, baina egile honen Gertatu sinbolo hau erabili ahal izateko. Beraz, luzea dugu stringing ari gisa nodo horiek guztiak elkarrekin, bakarrik gogoratzeko non lehenengoa da, beraz, luzea Ikur berezi bat jarri dugu at zerrendako azken nodo, eta nulua erabiliko dugu, hori delako zer dugu gurekin eskuragarri, zerrenda hau osatu da. Eta besterik ez bada ere emango dizu erakuslea lehenengo elementua, duzu, programatzailea, zalantzarik gabe, gainerako sar daitezke. Baina dezagun utzi zure adimenak pixka bat ibiltzea, Oraindik ez dute dagoeneko Nahiko wandered-- zer da exekutatzen denbora izango da Zerrenda honetan ezer aurkitzea? Malditos da, big n O da, eta hori ez da txarra, zuzentasuna. Baina lineala da. Amore eman dugu zer Ezaugarri gehiago mugituz Matrizeen dinamikoki Argazki hau lortze ehundutako elkarrekin edo nodoak lotuta? Amore eman dugu ausazko sarbidea. Array bat da, polita delako matematikoki guztia da atzera itzuli Itzuli behar. Nahiz eta argazki hau, nahiz itxura polita, eta are badirudi, nahiz eta nodo horiek bezala nicely bananduta gain, errealitatean edozein lekutan izan dira. OX1, Ox50, ox123, Ox99, horiek nodes edonon izan daiteke. Malloc du memoria esleitu delako arazoak izaten ari da, baina edonon, zeure. Ez dute zertan Badakizu, hori da itzuli itzuli itzuli izango da. Eta, beraz, errealitatearen argazki hau ez nahiko polit hau izango. Beraz, pixka bat hartu du lan funtzioa hau ezartzeko. Hargatik ezartzeko bilaketa orain. Eta ikusiko dugu bat mota clever hau egiteko modu. Beraz, naiz bilaketa funtzio bat bada eta Ez dut jakin, aldagai bat, osokoa n begiratu, jakin behar dut barruan bilatzen sintaxia berria egitura hori of to, n aurkituko adierazi. Beraz, egin dezagun hau. Beraz, lehen ez naiz joango aurrera eta deklaratzeko nodo *. Eta deitu dut joan erakuslea, besterik ez konbentzio. Eta ez dut abiarazi lehen joan. Eta orain hau egin ahal izango dut modu zenbaki bat ere. Baina nago planteamendu komun bat hartzen joan nintzen. Erakuslea ez da berdina bitartean baliogabea eta baliozko sintaxia da. Eta horrek esan nahi du, besterik gabe, honako hau egin, beraz, betiere ezer ez ari zaren seinalatuz. Zer egin nahi dut? Bada erakuslea dot n, utzi zatoz me back horretara, berdin berdin, zer? Zer balio nabil for? Gainditu zen benetako n The. Hortaz, hona hemen ezaugarri bat C eta hizkuntza askotan. Nahiz izeneko egitura nodo arren du balioa n bat, guztiz zilegia tokiko argudio bat ere badute edo n izeneko aldagai. Zeren, nahiz eta dugu, batera giza begiak, bereiz daitezke n hau da ziur aski n hau ezberdinetan. Sintaxia ezberdina delako. Lortu duzu dot eta erakuslea, hau, berriz, besteak beste, gauza ez du. Beraz, hau ondo dago. Hori da OK horiek gauza bera deitzeko. Ez dut hau aurkituko duzu, naiz zerbait egin nahi du bezala iragarriko aurkitu dugun n. Eta gisa utziko dugu iruzkin edo pseudocode kodea. Bestela, eta hemen zati interesgarri, zer egin uneko nodoaren bada egin nahi dut ez da n horri buruz zaintzen dut dauzkaten? Zelan honako hau lortzen dut? Gero, nire hatz at Une PTR da, eta hori da, edozein dela seinalatuz hasiera batean apuntatzen da, nola mugitu nire hatz dut kodea hurrengo nodo nahi? Beno, zer da breadcrumb gara Kasu honetan, jarraitu egingo? IKUSLEEN: [INAUDIBLE]. DAVID J. MALAN: Bai, eta, beraz, hurrengo. Beraz, joan I itzuli bada, nire Hemen kodea, hain zuzen ere, naiz Aurretik joan eta esan erakuslea, joan eta bertan aldi baterako aldagai bat da, ez da Izen bitxi bat, ptr, baina Besterik temp-- bezala Erakuslea ezarri noa edozein dela erakuslea is-- berdina eta, berriro ere, hau da bat izango da joan une dot baten ondoan dagoen buggy txiki. Beste era batera esanda, nik hartu dut nire hatz hori nodo honetan seinalatu eta hemen naiz esan du, badakizu zer, hartu hurrengo eremu begirada bat eta mugitu hatza edozein dela at da seinalatuz. Eta hori da joan errepikatu, errepikatu, errepikatu. Baina nire hatz egiten du gelditzeko ezer egiten? Ahalik eta azkarren zer kodea Jaurtiketa ildotik? IKUSLEEN: [INAUDIBLE] DAVID J. MALAN: bada puntu bitartean erakuslea ez da berdina null. Uneren nire hatz-en null at egon apuntatzen joan eta naiz konturatzen joan nintzen duen zerrenda honen amaieran da. Orain, hau da, pixka bat sinpletasunagatik zuri gezurra. Bihurtzen da, nahiz eta besterik ikasi idazkera dot hau egituren, erakuslea ez da egitura bat. ptr da zer? Just gehiago nitpicky izan. Nodo bat erakuslea da. Ez da nodo bat bera. Izarra ez da hemen izan nuen bada, erakuslea absolutely-- nodo bat da. Honek aste bat bezalakoa da aldagai baten aitorpena, nahiz eta hitza "node" berria da. Baina bat aurkeztu dugu bezain laster izarra, Orain bat, nodo bat erakuslea. Eta zoritxarrez, ezin duzu erabili dot erakuslea for idazkera. Gezi erabili behar duzu idazkera, eta horrek, harrigarria, lehen aldiz pieza edozein da sintaxiaren itxura intuitiboa. Hau literalki gezi baten itxura. Eta, beraz, hori gauza ona da. Eta hemen behera, hitzez hitz gezi baten itxura. Beraz, uste dut hori la-- ez ez dut pentsatzen ari naiz hemen baino gehiago-konpromisoa dut uste duten azken pieza berria ari gara ikusten sintaxia joan. Eta zorionez, hain zuzen ere, apur bat intuitiboagoa. Orain, zuk dutenentzako modu zaharra nahiago izatea, oraindik dot idazkera erabili ahal izango duzu. Baina per Astelehena en bezala elkarrizketa, lehen genuen Hara joan behar, horretara joan helbidera, eta, ondoren, eremuan sartzeko. Beraz, hau zuzena da, gainera. Eta Egia, hau da, little more pedantic. Zu literalki esaten, dereference erakuslea eta Hara joan. Ondoren, har n, eremuaren n izenekoa. Baina, Egia, inork ez du nahi idatzi edo irakurri hau. Eta, beraz, mundu asmatu gezi idazkera, zein baliokidea, berdin-berdina da, besterik azukre sintaktikoa da. Beraz, hau esaten modu fancy bat itxura hobea, edo itxura sinpleagoa. Beraz, gaur egun, naiz beste gauza bat egin behar. Esan "break" behin dut I noa Aurkitu da, beraz, ez dut mantendu da bila. Baina honen funtsa da bilaketa-funtzio baten. Baina errazagoa da, parte amaieran, eta ez kodea ibiltzeko. Hau da, hain zuzen ere ezartzeko formal bila, gaur egungo banaketa kodea. Esan txertatze hori ez da ausartzen naiz bereziki fun to ibiltzeko ikusmen, ezta ezabatu da, nahiz Egunaren amaieran, nahiz behera irakiten nahiko dute heuristics simple. Beraz, egin dezagun hau. Umore me hemen egingo baduzu, egin nuen estresa pilotak mordo bat ekarri. Zenbaki-sorta bat ekarri dut. Eta ezin boluntario gutxiren buruan lortuko dugu 9, 17, 20, 22, 29, eta 34 ordezkari izateko? Beraz, funtsean, denek nor da hemen gaur egun. Hori izan zen, bat, bi, hiru, lau, bost, sei pertsona. Eta Eskatuko dut eta joan egingo ikusteko moduan, atzealdean inork bere eskuetan altxatzen. Ados, bat, bi, hiru, lau, five-- utzi kargatu me balance-- sei. Ados, zatoz sei up. Beste pertsona bat behar dugu. Extra estresa pilotak ekarri dugu. Eta ahal izango banu, zeren Oraingoz, lerro bat besterik ez buruäc besterik Argazki hau hemen bezala. Guztiak eskubidea. Ikus dezagun, zer da zure izena? IKUSLEEN: Andrew. DAVID J. MALAN: Andrew, kopurua 9 zara. Niza zu ezagutzeaz. Hemen duzu joan. IKUSLEEN: Jen. DAVID J. MALAN: Jen. David. Zenbakia 17. Bai? IKUSLEEN: naiz Julia. DAVID J. MALAN: Julia, David. Zenbakia 20. IKUSLEEN: Christian. DAVID J. MALAN: Christian, David. Zenbakia 22. Eta? IKUSLEEN: JP. DAVID J. MALAN: JP. Zenbakia 29. Anima zaitez eta lortu in-- Uh oh. Uh oh. Egonean. 20. Norbaitek dute markatzaile bat? IKUSLEEN: Nik Edukien. DAVID J. MALAN: Edukien bat lortu duzu? Ados. Eta ez da inor izan paper bat? Save hitzaldia. Goazen. IKUSLEEN: Lortu dugu berau. DAVID J. MALAN: Lortu dugu? Ondo da, eskerrik asko. Hemen gara. Hau izan zen duzu? Egun gorde besterik ez duzu. Beraz, 29. Guztiak eskubidea. Gaizki idatzitako dut 29, baina OK. Anima zaitez. Ondo da, emango dizut zure pen atzera une batez. Beraz, Folks horiek baliorik. Dezagun bat bestea. Gabe, ez jolastu nahi duzun Lehenengo elementua hemen? Seinalatuko duzu beharko dugu Folks horiek fina at. Beraz, 9, 17, 20, 22, ordenatu 29, eta gero 34. Ba norbaitek galtzen dugu? 34 bat dudalako. Non OK did--, nahi duenak 34 izateko? OK, goazen gora, 34. Ondo da, hau izango da baita buruko pilota merezi. Zein da zure izena? IKUSLEEN: Peter. DAVID J. MALAN: Peter, goazen gora. Ondo da, beraz, hemen bat nodo sorta osoa. You guys bakoitzak adierazten laukizuzenak horietako bat. Eta Gabe, apur bat bakoitiak man out, lehen adierazten du. Beraz, bere erakuslea da, pixka bat txikiagoa Besteek baino pantailan. Eta, kasu honetan, zure bakoitza utzi eskuetan dago, bai seinalatu behera egingo, horrela null ordezkari gisa, beraz, besterik erakuslea ezean, edo nik apuntatzen joan duzu ondoan nodo batean. Beraz, oraintxe apaintzen baduzu Irudian bezala zuek hemen, aurrera eta puntu elkarrengandik, Gabe with at seinalatuz bereziki kopurua 9 zerrenda adierazteko. Ados, eta zenbaki 34, ezkerraz behar besterik solairuan seinalatuz. Ados, beraz, hau lotutako zerrenda da. Beraz, hau dena delako eszenatokia. Eta, hain zuzen, hau da ordezkari arazo klase baten baliteke kode batekin konpontzen saiatzen zara. Azken finean Txertatu nahi duzu elementu berri bat zerrendan sartu. Kasu honetan, goaz saiatu 55 zenbakia adierazi beharko. Baina ez da joan Kasu ezberdinak kontuan hartu behar dira. Eta, hain zuzen, hau da bat izango da of the big-irudi takeaways hemen, da, Zein dira kasu desberdinetan. Zein dira baldintza bada, edo desberdinak zure programa izan dezake adarrak? Beno, saiatzen ari zaren kopurua txertatze, gaur egun ezagutzen dugun 55 izan behar du, baina ez baduzu jakin Aldez aurretik, I daresay Gutxienez hiru maiteminduko egoera posible. Non liteke elementu berri bat izango ote da? IKUSLEEN: Eta amaieran edo erdian. DAVID J. MALAN: amaieran, in erdian, edo hasieran. Beraz aldarrikatzen dut, ez dago gutxienez hiru arazo konpondu behar dugu. Dezagun zein da agian dudarik gabe, errazena bat, elementu berriak hasieran dagokio. Beraz, ez dut kodea izatea nahiko joan bezalako bilatzeko, idatzi besterik ez dut. Eta ez dut ptr dute, joan eta bertan Hemen adierazten dut nire hatz batera, ohikoa den bezala. Eta gogoratu, zer balio zuten abiarazi ptr dugu? Beraz, hasiera batean NULL hasieratu dugu. Baina orduan zer egin dugu behin gure bilaketa-funtzioa barruan zeuden? Berdintasunarekin ezarri dugu lehenik, Horrek ez du esan nahi lan hau egiteko. Ptr berbera jasotzeko ezarri badut lehen, zer behar dut nire eskua benetan izan seinalatuz? Eskuin. Beraz, Gabe eta biok joan balioak berdinak izan hemen, bi puntu behar dugu kopurua 9. Beraz, hau da gure istorioa hasieran izan zen. Eta orain, hori besterik ez da erraza, sintaxia berria da, nahiz eta. Kontzeptualki honek bilaketa lineala besterik ez da. Is 55 berdinak 9ra? Edo, hobeto esanda, demagun 9 baino gutxiago. Saiatzen ari naiz delako irudikatu non 55 jarri behar da. 9 baino gutxiago, 17 baino gutxiago, gutxiago 20 baino gehiago, 22 baino gutxiago, 29 baino gutxiago, 34 baino gutxiago, ez. Beraz, orain ari garen kasuan Gutxienez hiru bat. 55 baino gehiago txertatzeko hemen nahi badut, zer kodea behar-lerroak exekutatu ahal izateko? Nola irudi hau ez gizakiak aldatu behar? Zer egin behar dut nire ezkerreko eskua? Hau nulua izan behar du, hasiera batean, Ni zerrendako amaieran dudalako. Eta zer gertatu beharko hemen Peter-ekin, ordea? He da, jakina, me seinalatu. Beraz aldarrikatzen dut, gutxienez bi lerro ez dago lagin gaurtik código Kode- hori abian jartzera joan gehituz 55 buztana eszenatokia. Eta norbaitek hop ezin izan dut up eta besterik adierazten 55? Ondo da, zu 55 berria. Beraz, orain zer hurrengoan bada eszenatoki batera dator, eta bertan sartu nahi dugun hasita edo zerrenda honen buru? Eta zein da zure izena, 55 zenbakia? IKUSLEEN: Jack. DAVID J. MALAN: Jack? Ados, politak zu ezagutzeaz. Ongi etorri itsasontzian. Beraz, orain goaz txertatzeko, esan, 5 zenbakia. Hona hemen bigarren kasua Hiru sortu ginen aurretik. Beraz, 5 hasieran jabea bada, ikus dezagun nola duela jakin dugu. Nire ptr hasieratu I kopurua 9 berriro erakuslea. Eta, konturatu nintzen oh, 5 eta 9 baino gutxiago. Beraz, argazki hau guretzat konpondu. Noren eskuetan, Gabe-ren edo Daviden -edo zer da zenbakia 9 izena? IKUSLEEN: Jen. DAVID J. MALAN: Jen en hands-- gure esku eta horrek aldatu behar? Ados, beraz Gabe zer now at puntuak? Me at. Nodo berria naiz. Beraz, besterik gabe, mugimendu-mota egingo dut Hemen da ikusmen ikusteko. Eta bitartean zer egiten duten seinalatu dut? Oraindik non apuntatzen naiz. Beraz, hori da. Benetan Beraz, besterik gabe, kodea konponketak lerro bat gai jakin honetan, badirudi litzateke. Ondo da, beraz, hori ona da. Eta norbaitek 5 biltegia izan? Goazen sortu. Hurrengoan jasoko duzu dugu. Ondo da, beraz, orain eta Bat alde batera utzita, izenak bezala Ez dut esplizitua eskuineko aipamena eginez orain, pred erakuslea, aurrekoak erakuslea eta erakuslea berria, hori da besterik izenak eman lagin erakusle izateko, kodea edo nire esku, hori da mota inguruan seinalatuz. Zein da zure izena? IKUSLEEN: Christine. DAVID J. MALAN: Christine. Ongi etorri itsasontzian. Ondo da, beraz, kontuan hartu dezagun orain Agertoki zertxobait gehiago gogaikarriak bat, Horren bidez sartu nahi dut 26 hau sartu antzeko zerbait. 20? Zer? Hauek are-- gauza ona pen hau dugu. Ondo da, 20. Norbaitek beste pieza bat lortuko balute paper prest, besterik ez eskuineko guztiak kasu horretan ere. Oh, interesgarria. Beno hau adibidea da hitzaldia akatsen bat. Ados, beraz, zer da zure izena berriro? IKUSLEEN: Julia. DAVID J. MALAN: Julia, ezin duzu pop out eta asmoa sekula ez zinen? Ados, hau ez da inoiz gertatu. Eskerrik asko. Beraz, demagun txertatu nahi dugun Julia lotuta zerrenda honetan sartu. 20 zenbakia da. Eta, jakina, zuen da to the at dagozkio joan begin-- ez dute ezer at seinalatu oraindik. Beraz, eskua mota egin ahal izango behera null edo zabor balio batzuk. Dezagun esango istorio azkar. Zenbakia 5 oraingoan dut seinalatuz. Ondoren, egiaztatu dut 9. Gero check I 17. Gero check I 22. Eta, konturatzen naiz ooh, Julia 22era aurretik joan behar du. Beraz, zer behar du gertatuko? Noren eskuetan aldatu behar? Juliaren, nirea,-edo Zein da zure izena berriro? IKUSLEEN: Christian. DAVID J. MALAN: Christian edo? IKUSLEEN: Andy. DAVID J. MALAN: Andy. Christian edo Andy? Andy at seinalatu behar du? Julia. Guztiak eskubidea. Beraz, Andy, ez to Julia at seinalatu nahi duzu? Baina minutu bat itxaron. Beraz, orain arte Istorioa, Alde moduko naiz karga, zentzuan direla erakuslea gauza hori da zerrendan zehar mugitzen. Baliteke Andy izen bat daukagu, baina ez dago aldagai Andy deitzen da. Beste aldagai bakarra da dugun lehenengoa, nor Gabe irudikatzen. Beraz, hau da, benetan, zergatik beraz, arte ez dugu behar den honetan. Baina orain pantailan ez da aipatu berriro pred erakuslea. Hargatik gehiago esplizitua izan dit. Hau da erakuslea da, bada, hobea izan nuen get apur bat gehiago adimentsua Nire iterazio buruz. Ez baduzu axola hemen bidez nire joan berriro, seinalatuz hemen, hemen seinalatuz. Baina utzi dute me pred erakuslea, aurrekoak erakuslea, hori da motatako seinalatuz elementu at nengoen. Beraz, hemen joan nintzen, orain Nire ezkerreko eguneratzeak. Noiz joan naiz nire ezkerreko eskua eguneratzeak. Eta orain izan dut erakuslea, ez bakarrik duten Julia ondoren doa elementua, Oraindik erakuslea izan dut Andy, elementua aurretik. Beraz, sartzeko aukera izango duzu, funtsean, breadcrumbs, izango bada, baldintza erakusle guztiei. Beraz dut seinalatuz bada Andy eta ere naiz seinalatuz Christian, zeinen eskuetan at orain beste leku batean adierazi behar dira? Beraz Andy orain Julia at seinalatu dezake. Julia orain Christian at seinalatu dezake. Kopiatu ahal izango zuen delako nire eskuin eskuko erakuslea. Eta hori modu eraginkorrean jartzen leku hau hemen sartu. Beraz, azken finean, nahiz eta hau, nahiz nolako gurekin hartzearen betiko benetan eguneratu bat lotutako zerrenda, konturatzen eragiketak direla nahiko sinpleak dira. Da bat, bi, hiru Kode lerro azken finean. Baina horiek inguruan bilduta zentzuzkoa kode lerro logika pixka bat da eraginkortasunez galderari, non garen galdetzen? Gara hasieran, erdian, edo bukaera? Orain, ez dira, zalantzarik gabe, beste batzuk eragiketak agian ezarriko ditugu. Eta argazki hauek hemen besterik irudikatzeko zer gizakiak egin besterik ez dugu. Zer kentzea buruz? Nahi badut, adibidez, zenbakia kendu 34 edo 55, Baliteke kodea mota bera behar dut, baina ez dut urrats bat edo bi behar du. Zer berri delako? Kendu dut norbaitek badu bukaeran, zenbaki bezala 55 eta, ondoren, 34, zer ere ez da egin dudan bezala, aldaketa egin du? Ez evict-- daukat Zein da zure izena berriro? IKUSLEEN: Jack. DAVID J. MALAN: Jack. Izan evict-- free Jack bakarra dut, beraz, literalki deitu doan Jack, edo, gutxienez, erakuslea han ere, baina orain, zer behar den Peter batera aldatzeko? Eskuan hobeto hasteko behera seinalatuz. Free deitu nuen bezain laster delako Jack, bada Pedro oraindik Jack seinalatuz eta, beraz zeharkatu mantentzen dut zerrenda eta sarbide erakuslea honetan, hori da gure lagun zaharra segmentazio errua agian benetan jaurtitzeko ere. Eman dugu delako memoria Jack itzuli. Bertan geratuko dezakezu baldarki une bat besterik ez da. Pare bat besterik ez dugulako final eragiketak kontuan hartu behar dira. Zerrenda-burua kentzen, edo beginning-- du eta hau, apur bat gogaikarriak. Duten jakin nahi dugulako Gabe da, mota bereziak programa honetan. Hain zuzen ere, bere erakuslea egin du. Ez du bakarrik ari azpimarratu, ia gainontzeko hemen bezala. Beraz, zerrenda-burua da, kendu, zeinen eskuetan orain aldatu behar? Zein da zure izena berriro? IKUSLEEN: Christine. DAVID J. MALAN: awful naiz izenak, itxuraz. Beraz, Christine eta Gabe, zeinen eskuetan aldatu behar denean Christine kentzeko saiatzen gara, zenbakia 5, irudi batetik? Ados, beraz, egin dezagun Gabe utzi. Gabe da seinalatu, ustez, kopurua 9. Baina zer gertatzen da hurrengo gertatu beharko? IKUSLEEN: Christine beharko lukete nulua izan [INAUDIBLE]. DAVID J. MALAN: Ados, ziurrenik behar dugu make-- "null" entzun nuen nonbait. IKUSLEEN: Null eta free bere. DAVID J. MALAN: nulua, zer? IKUSLEEN: Null eta free bere. DAVID J. MALAN: Null eta free bere. Beraz, hau oso erraza da. Eta ezin hobea da zarela orain ordenatu han zutik, ez barruan. Nik duzulako zerrendatik decoupled. Eraginkortasunez dituzun dira zerrendatik umezurtz. Eta beraz genuen hobeto deitu doan hemendik Christine memoria hori atzera emateko. Bestela aldi bakoitzean dugu Nodo bat ezabatzeko zerrendatik dugu zerrendan egiteko liteke laburragoa da, baina ez benetan jaitsiz memorian tamaina. Eta horrela gehituz jarraituko badugu eta gehituz, gauzak gehituz zerrendan, Nire ordenagailuan motelagoa lortu liteke eta motelagoa eta motelagoa, daudelarik I exekutatzen ari delako memorian, ez naiz, nahiz eta, egia esan, Christine en byte erabiliz oroimenaren jada. Beraz, azkenean, ez dira beste agertokiak, noski kentzea erdiko, kentzea amaieran, ikusi dugun bezala. Baina interesgarria Erronka orain joan zehazki kontuan hartu behar izaten du denbora exekutatzen ari dela. Beraz, ez bakarrik mantendu dezakezu zure paper zatiak,, bada Gabe, ez zela axola ematea guztiontzat estresa baloi bat. Eskerrik asko, beraz, gure lotutako zerrenda askoz Hemen boluntarioen, ahal izango banu. [Txaloak] DAVID J. MALAN: Ondo da. Beraz analitikoa pare bat galdera, ondoren, ahal izango banu. Izendapen hori ikusi dugu lehenago, O big eta omega, goiko mugetatik eta on mugetatik txikiagoa algoritmo batzuen denbora exekutatzen. Beraz, kontuan hartu dezagun, besterik gabe, galdera pare bat. Bat, eta, esan dugun aurretik, zer da korrika Bilaketa bat egiteko garaia O big dagokionez zerrendan? Zer da entzierroa buruzko goi-muga lotuta zerrenda bat bilatzen denbora inplementatu gure boluntarioek bezala hemen? Big n O, lineala da. Kasurik okerrenean ere delako, elementua, 55 bezala, dugu agian izan non bila liteke Jack izan zen, amaieran modu guztiak. Eta zoritxarrez, array bat bezala ezin dugu lortu fancy oraingoan. Gure gizakien guztiak izan ziren arren elementu txiki, 5 eta ordenatuta, handiagoak elementu erabakitzen ditu modu guztiak, 55, hori gauza ona izan ohi da. Baina zer hipotesi egiten duen Jada ez baimendu egiten digu? IKUSLEEN: [INAUDIBLE] DAVID J. MALAN: Esan berriro? IKUSLEEN: Random sarbidea. DAVID J. MALAN: Random sarbidea. Eta, aldi berean, horrek esan ahal dugu inolako jada ahul zero, intuizioa erabili, eta bitarra erabiliz obviousness bilatu eta zatitzea eta konkistatzeko. Nahiz dugulako gizakiak, jakina, ezin izan ikusi Andy edo kristau zirela gutxi gorabehera zerrendan erdian, bakarrik ezagutzen gisa dugun ordenagailu zerrendan skimming arabera du hasiera-hasieratik. Beraz, eman dugu ausazko sarbidea duten. N O hain handia da orain goiko gure bilaketa-denbora lotuak. Zer gure bilaketaren omega buruz? Zer da beheko bila doazen Zerrenda honetan zenbaki batengatik? IKUSLEEN: [INAUDIBLE] DAVID J. MALAN: Esan berriro? IKUSLEEN: Bat. DAVID J. MALAN: Bat. Beraz, denbora etengabe. Kasurik onenean ere, Christine da hain zuzen ere, zerrendaren hasieran. Eta guk nahi zenbakia 5, beraz, bere aurkitu dugu. Beraz, big aurre ez. Baina berak lortu behar du egon kasu honetan, zerrendaren hasieran. Zerbait buruz nolakoak ezabatu? Zer elementu bat ezabatu nahi bada? Zer da goi-muga eta beheko muga bat lotuta zerbait ezabatzen an listado? IKUSLEEN: [INAUDIBLE] DAVID J. MALAN: Esan berriro? IKUSLEEN: n. DAVID J. MALAN: n dago hain zuzen ere, goiko muga da. Kasurik okerrenean ere saiatu dugulako Jack ezabatzeko, egin genuen bezala besterik ez. Amaieran modu guztiak zuen. Garamatza betiko, edo n urratsak haren bila. Beraz, goi-muga bat. Hori da lineala, ziur. Eta kasu horretan, onena denbora exekutatzen, edo txikiagoa onena kasu mugetatik Etengabeko denbora izango litzateke. Agian ezabatu saiatu dugulako Christine, eta lortu besterik ez dugu zortea da hasieran zuen. Orain minutu bat itxaron. Gabe ere izan zen hasiera-hasieratik, eta Gabe eguneratzeko ere izan dugu. Beraz, ez zen beste urrats bat besterik ez da. Beraz, hain zuzen ere, etengabeko Denbora, kasu onenean, elementu txikiena kentzeko? It da, bi izan arren, agian, hiru, edo are 100 kode lerro, kopuru berdina bada lerroak, ez begizta batzuetan, eta tamainaren desberdina Zerrendaren, erabat. Elementu ezabatzen zerrendaren hasiera-hasieratik, to aurre egin behar dugu, nahiz eta Gabe, etengabeko denbora dago oraindik. Beraz, hau dirudienez Urrats masiboa atzeraka. Eta zer hondakin denbora , bada, aste bat eta astean zero bakarra izan genuen pseudocode kodea baina benetako kodea log zerbait ezartzeko base n, edo saioa, hobeto esanda, n, 2 oinarria, bere denborak dagokionez. Beraz, zergatik demontre egiten hasten ziren nahi dugu lotuta zerrenda antzeko zerbait erabiliz? Bai. IKUSLEEN: Beraz gehi dezakezu array elementuak. DAVID J. MALAN: Beraz, ahal duzun array elementuak gehitzeko. Eta hau ere gaikako da. Eta ikusten jarraituko dugu hau, Oreka horrek, askoz bezala ikusi dugu bat merge sort merkataritza-off. Benetan izan dugu arindu bilatu edo sailkatzeko, baizik eta, espazio pixka bat gehiago gastatzen badugu eta memoria bat zati gehigarri bat dute edo merge sort array bat. Baina gehiago gastatzen dugu espazioa, baina, denbora aurreztuko dugu. Kasu honetan, ez gara denbora etsi baina ez gara malgutasuna irabazten, dinamismoa izango bada, hau da, dudarik gabe, Ezaugarri positiboa. Ari jokaleku bat gastatu dugu. Zein zentzu bat dago lotuta Zerrenda garestiagoa array bat baino espazio aldetik? Non dago beste tarte bat datozen? Bai? IKUSLEEN: [INAUDIBLE] erakuslea. DAVID J. MALAN: Bai, dugu Era berean, erakuslea. Beraz, hau da minorly gogaikarriak horretan jada ez nago Int bat gordetzeko I int bat adierazteko. Int bat eta bat gordetzeko, naiz erakuslea ere, hau da, 32 bit. Beraz, naiz literalki bikoiztu dut hartzen duten espazioaren zenbatekoa. Beraz, merkataritza-off bat da, baina int kasuan izan da. Demagun ez zaudela int gordetzeko, baina suposatzen laukizuzenak horietako bakoitzean edo gizakiak horietako bakoitzean zuten ordezkari hitz batean, ingelesezko hitz bat dagoela bost pertsonaiak, 10 izan liteke pertsonaiak, eta beharbada, gehiago. Ondoren, bit 32 besterik gehiago gehituz Aurre handi bat gutxiago izan daiteke. Ikasle bakoitzari Zer bada manifestazio batean literalki ziren ikaslea structs duten Izenak eta etxe eta agian Telefono zenbaki eta Twitter maneiatzen eta antzekoak. Beraz, guztiak eremuen hasi ginen beste egunean buruz hitz egiten, askoz aurre handi bat gutxiago bezala gure nodoak lortu interesgarriagoa eta, gastatzen big to eh, gehigarri bat erakuslea besterik horiek elkarrekin lotzeko. Baina, hain zuzen ere, merkataritza-off bat da. Eta hain zuzen ere, kodea konplexuagoak, ikusiko duzu gisa Ikusten bidez skimming arabera Adibide jakin horretan. Baina zer ez balitz Hemen batzuk santua Grial. Zer bada, ez dugu urrats bat atzeraka baina urrats bat masiboa aurrera eta datuak bat ezartzeko egitura zein bidez dugu Jack edo antzeko elementu aurkitu ahal Christine edo beste edozein elementu Egia denbora etengabe array honetan? Bilaketa konstante da. Ezabatu da konstante. Txertatu konstante da. Eragiketa horiek guztiak izaten dira. Hori da gure Grial santua izango litzateke. Eta hori da, non gauden jaso egingo hurrengoan. Ikusi duzu ondoren.