[MUZIKO Ludante] DAVID J. Malan: Bone. Jen CS50. Jen semajno kvin daŭrigis, kaj ni havas bonajn novaĵojn kaj iuj malbonaj novaĵoj. Tiel bona novaĵo estas ke CS50 ĵetas ĉi vendredo. Se vi ŝatus aliĝi nin estrus al la kutima URL tie. Eĉ pli bona novaĵo, ne lekcio tiu venanta lundo la 13a. Iomete malpli bona novaĵo, kvizo nulo estas proksima merkredo. Pliaj detaloj povas esti troviĝas ĉe ĉi tiu URL tie. Kaj super la venonta paro tagoj ni estos plenigita de spacoj koncerne al la salonojn ke ni estos rezervitaj. Bona novaĵo estas ke ekzistas timige esti supozita monda recenzo kunsido ĉi venanta Lundo vespere. Sekvu la kurso retejo por ubicación kaj detaloj. Sekcioj, kvankam ĝi estas ferio, ankaŭ renkonti tiel. Bona novaĵo, prelegi proksiman vendredon. Do tio estas tradicio ni havi, kiel por la Syllabus. Just-- gxi tuj estos mirinda. Vi vidos tion kiel konstanta tempo datumstrukturoj kaj hash tabloj kaj arboj kaj provas. Kaj ni parolos pri naskiĝtago problemojn. Tuta aro de aĵoj atendas venontan vendredon. OK. Cxiuokaze. Do memoru, ke ni estis centrante sur tiu bildo de kio estas ene de nia komputilo memoro. Do memoro aŭ RAM estas kie programoj ekzisti dum vi kuras ilin. Se vi duoble alklaku la ikono kuri iuj programo aŭ duoble alklaku la Icon malfermi iun dosieron, ĝi estas ŝarĝita de via fiksita forpeli aŭ solida stato drive en RAM, Random Access Memory, kie vivas ĝis la potenco pafas, la tekkomputilo kovrilon fermas, aŭ vi forlasis la programon. 

Nun ke memoro, de kion vi probable havos 1 gigabajto tiuj tagoj, 2 gigabajtoj, aŭ eĉ multe pli, Ĝenerale elspezata por donita programo en tiu speco de rektangula koncepta modelo per kiu ni havas la stako ĉe la malsupro kaj estas multaj aliaj aĵoj en la supro. La afero ĉe la plejsupro ni vidis en tiu bildo antaŭe sed neniam parolis pri estas la tn teksto segmento. Teksto segmento estas nur ornama metodo diri la nuloj kaj ke formi vian realan kompilita programo. 

Do kiam vi duoble klaki Microsoft Word sur via Mac aŭ PC, aŭ kiam vi kuros dot slash Mario sur Linuksa komputilo ĉe via fina fenestro, la nuloj kaj kiuj formas Vorto aŭ Mario stokas temporalmente en via komputilo RAM en la tn teksto segmento por aparta programo. Malsupre kiu iras inicializado kaj uninitialized datumoj. Tiu estas aĵoj kiel tutmonda variabloj, ke ni ne uzas multaj, sed foje ni havis tutmonda variabloj aŭ statike difinita kordoj kiuj Estas malfacile kodita vortoj kiel "saluton" ke ili ne prenas en de la uzanto ke estas malfacile-kodita en via programo. 

Nun, sube ĉe la malsupro ni havas la tn pilo. Kaj la pilo, tiel malproksima, ni estis uzante por kiajn celojn? Kio la stako estis uzata por? Yeah? 

Publiko: Funkcioj. 

DAVID J. Malan: Por funkcioj? En kiu senco por funkcioj? 

Publiko: Kiam vi nomas funkcio, la argumentoj estas kopiitaj sur la stako. 

DAVID J. Malan: Ĝuste. Kiam vi nomas funkcio, ĝia argumentoj estas kopiitaj sur la stako. Do ajna X aŭ Y estas aŭ A aŭ de B ke vi pasas en funkcio estas provizore surmetis la tn stako, same kiel unu el la Annenberg manĝejo pletoj, kaj ankaŭ tion, kiel lokaj variabloj. Se via foo funkcio aŭ via swap funkcio havas lokajn variablojn, kiel temp, tiuj du finas sur la stako. Nun, ni ne tro parolas pri ilin, sed ĉi tiuj mediovariabloj ĉe la malsupro ni vidis faras tempon kiam Mi futzing ĉe la klavaro tago kaj mi komencis aliri tion kiel argv 100 aŭ argv 1.000, nur elements-- mi forgesas la numbers-- sed ke ne supozis esti alirita per mi. Ni komencas vidante iuj funky simbolojn sur la ekrano. Tiuj estis tn mediovariabloj kiel tutmonda agordojn por mia programo aŭ pro mia komputilo, ne nerilata al la freŝa bug kiu ni diskutis, Shellshock, tio estis plaguing sufiĉe da komputiloj. 

Nun fine, en hodiaŭa fokuso ni finfine estos sur la monteto. Tio estas alia bloko de memoro. Kaj funde ĉiuj ĉi memoro estas la samaj aĵoj. Ĝi estas la sama aparataro. Ni estas nur ia trakti malsamajn vinberarojn de bajtoj por malsamaj celoj. La havaĵo estas ankaŭ tuj estos kie variabloj kaj memoro kiun vi petos de la operaciumo estas provizore stokas. 

Sed estas tipo de problemo ĉi tie, kiel la bildo implicas. Ni ia havas du ŝipoj pri karamboli. Ĉar kiel vi uzas pli kaj pli de la stako, kaj kiel ni vidas hodiaŭ antaŭen, kiel vi uzas pli kaj pli de la amason, verŝajne malbonaj aferoj povus okazi. Kaj efektive, ni povas indukti ke intence aŭ senintence. Do la cliffhanger lasta tempo estis ĉi programo, kiu ne servas neniun funkcian celo alia ol pruvi kiel vi kiel malbona ulo povas reale preni avantaĝon de cimoj en ies programo kaj transpreni programo aŭ eĉ tuta komputila sistemo aŭ servilo. Do ĝuste rigardo mallonge, vi rimarki ke ĉefa malsupre prenas en komanda linio argumentoj, kiel po argv. Kaj ĝi havas alvokon al funkcio f, esence sennoma funkcio nomita f, kaj ĝin pasante en argv [1]. 

Do kion ajn vorton la uzanto tajpas en ĉe la prompto post tiu programo nomon kaj tiam ĉi arbitra funkcio supren supro, f, prenas en ĉeno, AKA char *, kiel ni komencis diskuti, kaj simple nomas ĝin "trinkejo". Sed ni povus nomi ĝin nenion. Kaj tiam ĝi deklaras, enen de f, tabelo de signoj nomata c-- 12 tiajn karakterojn. 

Nun, por la rakonto mi estis rakontanta antaŭ momento, kie en memoro estas c, aŭ estas tiuj 12 signaĵoj tuj finos? Nur por esti klara. Yeah? 

Publiko: Sur la stako. 

DAVID J. Malan: Sur la stako. Do c estas loka variablo. Ni petas 12 signoj aŭ 12 bajtoj. Tiuj tuj finos sur la tiel-nomata pilo. Nun fine estas tiu alia funkcio tio estas vere bela utila, sed ni ne vere uzita gxi mem, strncopy. Ĝi signifas ĉenon kopion, sed nur n leteroj, n gravuloj. Do n karakteroj estos kopiita de trinkejo en c. Kaj kiom? La longo de trinkejo. Do alivorte, ke unu linio, strncopy, tuj kopii efike bari al c. 

Nun, nur por ia anticipi la moralo de tiu rakonto, kio estas potenciale problemaj tie? Eĉ kvankam ni kontrolanta la longo el trinkejo kaj pasante ĝin en strncopy, kio estas via gut diri vin estas ankoraŭ rompita sur tiun programon? Yeah? 

Publiko: Ne inkluzivi spaco por la nula karaktero. DAVID J. Malan: Ne inkluzivi spaco por la nula karaktero. Potenciale, kontraste en estinteco praktiko ni faras eĉ havas tiel kiel plus 1 por akomodi ke nula karaktero. Sed ĝi estas eĉ pli malbona ol tiu. Kion alian ni maltrafas fari? Yeah? 

Publiko: [inaudible] DAVID J. Malan: Perfekta. Ni malfacile kodita 12 belaj arbitre. Tio estas ne tiom la problemo, sed la fakto ke ni eĉ ne kontrolanta se la longo de stango estas malpli ol 12, en kies kazo tuj estos sekure metis ĝin en la memoro nomata c ke ni asignitaj. Ja, se stango estas kiel 20 signojn longa, tiu funkcio aperas esti kopiado 20 karakterojn de drinkejo en c, tiamaniere preni almenaŭ 8 bajtoj ke ĝi ne devus esti. Tio estas la implico ĉi tie. 

Do mallonge, rompita programo. Ne tia granda interkonsento. Eble vi ricevas segmentación kulpo. Ni ĉiuj havis cimoj en programoj. Ni ĉiuj havu cimoj en programoj nun. Sed kio estas la implikaĵo? Nu, jen zomita-en versio ke bildon de mia komputilo memoro. Tiu estas la fundo de mia pilo. Kaj efektive, en la tre fundo estas kio estas nomata patro rutinon stako, ornama metodo diri ke estas ĉefa. Tiel ke kiu nomis la funkcio f kiu ni parolas. Do tio estas la fundo de la stako. Reveno adreso estas io nova. Ĝi ĉiam estis tie, ĉiam estis en tiu bildo. Ni simple neniam nomis atenton al ĝi. Ĉar ĝi rezultas la vojo c laboras estas ke kiam unu funkcio vokas alian, Ne nur faras la argumentoj por ke funkcio get puŝis sur la stako, Ne nur faras la funkcion de loka variabloj get puŝis sur la stako, iu nomita reveno adreso ankaŭ akiras metita sur la stako. Specife, se ĉefa alvokoj Foo, ĉefaj La propra adreso en memoro, bovo ion, efike akiras metita sur la pilo tiel ke kiam f estas farita ekzekuti ĝin scias kie saltas reen al la teksto segmenton por daŭrigi ekzekuti. 

Do se ni estos tie koncepte, en ĉefa, tiam f atingas vokis. Kiel f scias kiu mane kontrolo reen? Nu, tiu malmulte breadcrumb ruĝe tie, vokis la reveno adreso, ĝi simple ĉekojn kian reveno adreso? Ho, lasu min saltas reen al ĉefa tie. Kaj tio iomete de simplificación, ĉar la nuloj kaj por ĉefaj estas teknike tien en la tech segmento. Sed tio estas la ideo. f suficas por scii kio kie kontrolo finfine superas. 

Sed la vojo de komputiloj delonge elspezata aferoj kiel lokaj variabloj kaj argumentoj estas kiel ĉi. Do, en la supro de ĉi tiu pentraĵo en blua estas la pilo kadro por f, do ĉiuj el la memoro, ke f specife estas uzanta. Do laŭe, rimarki ke trinkejo estas en tiu bildo. Trinkejo estis lia argumento. Kaj ni asertis ke argumentoj funkcioj get puŝis sur la stako. Kaj c, kompreneble, estas Ankaŭ en ĉi tiu bildo. 

Kaj ĝuste pro notacian celoj rimarki supre maldekstra angulo Estas kio estus c krampo 0 kaj tiam iomete malsupren dekstren estas c krampo 11. Do alivorte, vi povas imagi ke estas krado de bitokoj tie, la unua de kiuj estas supre maldekstre, malsupre de kiuj Estas la lasta de tiuj 12 bajtoj. 

Sed nun provu fasti antaŭen. Kio estas por okazi se ni pasas en string trinkejo kiu estas pli longa ol c? Kaj ni ne kontrolanta se ĝi estas ja pli longa ol 12. Kiun parton de ĉi tiu pentraĵo tuj get anstataŭigata per bitokoj 0, 1, 2, 3, dot dot dot, 11, kaj poste malbona, 12, 13 tra 19? Kio okazos tie, se konkludi el la ordenamiento ke c krampo 0 estas ĉe la supro kaj c krampo 11 estas speco de sube al la dekstra? Yeah? 

Publiko: Nu, ĝi okazas reskribi la signo * stangon. 

DAVID J. Malan: Jes, tio aspektas kiel vi tuj reskribi char * stangon. Malbono, se vi sendas en vere longa kordo, vi eble eĉ anstataŭigi kio? La reveno adreso. Kio denove estas kiel breadcrumb diri la programo kie iri reen al kiam f estas farita vokite. 

Do kio maliculojn tipe fari Estas kvazaŭ ili ektrovas programo ke ili estas scivola ĉu estas explotables, kalesxo tiel ke li aŭ ŝi povas preni avantaĝon de tiu besteto, ĝenerale ili ne ricevas ĉi tiu rajto unuafoje. Ili simple komenci sendi, ekzemple, hazarda kordoj en vian programon, ĉu ĉe la klavaro, aŭ sincere ili probable skribi iom programo simple aŭtomate generi kordoj, kaj komencos batante en via programo per sendo en multaj malsamaj enigoj ĉe malsamaj longoj. 

Kiam via programo kraŝoj, tio estas miriga afero. Ĉar ĝi signifas li aŭ ŝi eltrovis kio estas verŝajne ja cimon. Kaj tiam ili povas akiri pli ruza kaj komenci enfokusigante pli mallarĝa sur kiel eksplodi ke cimoj. En aparta, kion li aŭ ŝi povus fari estas sendi, en la plej bona kazo, saluton. Neniu granda interkonsento. Ĝi estas ĉeno kiu estas sufiĉe mallonga. Sed kio se li aŭ ŝi sendas, kaj ni ĝeneraligi ĝin, atako code-- tiom nuloj kaj kiuj faras aferojn kiel rm-RF, ke forigi ĉiun de la malmola disko aŭ sendu spamon aŭ iel atakas la maŝino? 

Do se ĉiu el tiuj literojn A simple reprezentas, koncepte, atako, atako, atako, atako, iuj malbonaj kodo ke iu alia skribis, sed se tiu persono estas inteligenta sufiĉa ne nur inkludas ĉiuj de tiuj rm-RFS, sed ankaŭ havi sian lastan malmultajn bajtojn esti nombro kiu respondas al la adreso de liaj aŭ ŝia propra atako kodo ke li aŭ ŝi pasis en nur per provizi ĝin ĉe la prompto: vi povas efike trompi la komputilo en rimarkante kiam f estas farita ekzekuti, ho, ke estas tempo por mi salti reen al la ruĝa reveno adreso. Sed ĉar li aŭ ŝi devas iel koincidis ke reveno adreso per sia propra nombro kaj ili estas inteligenta sufiĉa esti agordita ke numeron raporti, kiel vi vidi en la súper supro maldekstra angulo, la realan adreson en la komputilo memoro de kelkaj el siaj atako kodo, malbona ulo povas trompi la komputilo en ekzekuti sian propran kodon. 

Kaj tiu kodo, denove, ĝi povas esti io. Ĝi estas ĝenerale nomata konko kodo, kiu estas nur maniero diri ke ĝi estas ne ĝenerale iu tiel simpla kiel rm-RF. Estas vere iu kiel Bash, aŭ reala programo kiu donas al li aŭ ŝi programa kontrolon ekzekuti io alia, ke ili volas. Do mallonge, tiu tuta derivas de la simpla fakto ke tio cimon implikis ne kontrolanta la limoj de via tabelo. Kaj ĉar la vojo komputiloj verko estas ke uzi la stako de efektive, koncepte, malsupro supren, sed tiam la elementoj vi pelas sur la stako kreskis supre malsupren, tio estas nekredeble problema. Nun, estas formoj por labori ĉirkaŭ tiu. Kaj sincere, ekzistas lingvoj kun kiu labori ĉirkaŭ tiu. Java estas imunaj, ekzemple, al tiu aparta temo. Ĉar ili ne donos al vi punteros. Ili ne donas vin rekta memoro adresoj. Do per tiu potenco kiun ni havas tuŝi ion en la memoro Ni volas venas, rekoni, grandaj risko. 

Do subteni okulon ekstere. Se, sincere, en la monatoj aŭ jaroj por veni, ĉiutempe Vi legas pri iuj ekspluatado de programo aŭ servilo, Se vi iam vidis aludon pri io kiel buffer overflow atakon, aŭ stack overflow estas alia tipo de atako, simila en spirito, kiom inspiru la TTT-ejo nomo, se vi konas ĝin, ĝi estas cxiuj parolas nur disversxigxinta la grandeco de iu gravulo tabelo aŭ iu tabelo pli ĝenerale. Demandojn, tiam, sur tiu? Ne provu ĉi hejme. 

Bone. Do malloc tiel multe estis nia nova amiko en kiu povas atribui memoron ke ni ne nepre scias antaŭeniri ke ni volas do ni ne havas malmolaj kodon en nian programo nombroj kiel 12. Iam la uzanto diras ni kiom datumoj li aŭ ŝi volas enigi, ni povas malloc ke multa memoro. 

Do malloc rezultas, ke la mezuro ni estis uzante ĝin, eksplicite lastan fojon, kaj tiam vi uloj estis uzante ĝin por getstring scii por pluraj semajnoj, ĉiuj malloc memoro devenas la tn havaĵon. Kaj tio estas kial getstring, ekzemple, povas atribui memoron dinamike sen scii kion vi estas tuj tajpi anticipe, transdonos vin puntero al tiu memoro, kaj tiu memoro estas ankoraŭ via teni, eĉ post getstring revenas. Ĉar recall post ĉio, kion la pilo senĉese iras supren kaj malsupren, supren kaj malsupren. Kaj post kiam ĝi iras malsupren, tio signifas ajnan memoron tiu funkcio uzata devus ne estos uzata de iu ajn alia. Ĝi estas rubo valoroj nun. 

Sed la havaĵon estas ĉi tie. Kaj kio estas agrabla pri malloc estas ke kiam malloc atribuas memoro tien, ĝi ne efikis, por la Plejparte, la stako. Kaj tial ajna funkcio povas aliri memoro kiu estis malloc'd, eĉ per funkcio kiel getstring, eĉ post kiam ĝi revenis. 

Nun, la reo de malloc estas libera. Kaj efektive, la regulo vin bezonas komenci adoptante Estas neniu, ia, ia tempo vi uzas malloc Vi devas mem uzi liberan, eventuale, sur tiu sama montrilo. Ĉiuj ĉi tiu tempo ni estis skribante kalesxo, kalesxo kodo, por multaj kialoj. Sed unu el kiuj estis uzanta la CS50 biblioteko, kiu sin estas intence kalesxo, ĝi filtras la memoro. Ajna tempo vi nomis getstring super la pasintaj semajnoj ni demandas la mastruma sistemo, Linukso, por memoro. Kaj vi neniam iam donis ĝin reen. Kaj tio ne estas, praktiki, estas bona afero. 

Kaj Valgrind, unu el la iloj enkondukita en Pset 4 Estas ĉio pri helpas vin nun trovi insektojn kiel tio. Sed dankeme por Pset 4 Vi ne bezonas uzi la CS50 biblioteko aŭ getstring. Do cimojn rilataj al memoro estas fine tuj estos via. 

Do malloc estas pli ol nur konvena por tiu celo. Ni povas fakte nun solvi fundamente malsamaj problemoj, kaj fundamente solvi problemojn pli efike kiel por semajno nulo promeson. Tiel nun tio estas la pli sexy datumstrukturo ni havis. Kaj per datumstrukturo Mi nur volas diri manieron de koncepti memoro en maniero kiu iras preter nur diras, tio estas int, tio estas char. Ni povas komenci cluster aferojn kune. 

Do tabelo aspektis kiel ĉi. Kaj kio estis ŝlosila en proksimume tabelo estas kiu donas al vi back-to-back pecojn de memoro, ĉiu el kiuj tuj estos la sama tipo, int, int, int, int, aŭ signo, char, char, char. Sed estas kelkaj downsides. Ĉi ekzemple, estas tabelo de amplekso ses. Supozi vi plenigos ĉi tabelo kun ses nombroj kaj tiam, por kiaj kialoj, via uzanto volas doni vi sepa nombro. Kie vi metis ĝin? 

Kio estas la solvo, se vi havas kreis tabelon sur la stako, ekzemple, nur per la semajno du notacio ke ni enkondukas, de kvadrataj krampoj kun numero ene? Nu, vi havas ses nombroj en tiuj skatoloj. Kio estus via instinktoj esti? Kie vi volas meti ĝin? 

Publiko: [inaudible] 

DAVID J. Malan: Pardonu? 

Publiko: Metu ĝin sur la pinto. 

DAVID J. Malan: Remetu ĝin sur la pinto. Do ĝuste super la rajto, ekster tiu skatolo. Kiu estus bela, sed rezultas vi ne povas fari tion. Ĉar se vi ne petis por tio eron de memoro, ĝi povus esti por coincidencia ke tiu estas uzata de iu alia variablo entute. Pensu reen semajno aŭ tiel kiam ni metis el Zamyla kaj Davin kaj Gabe nomoj en memoro. Ili estis laŭvorte malantaŭo al malantaŭo al dorso. Do ni ne povas nepre esperas ke cxio estas tien disponeblas por mi uzi. 

Do kion alian povus fari? Nu, iam rimarki vin bezonas tabelo de amplekso sep, Vi povus simple krei tabelo de amplekso sep tiam uzi a por buklo aŭ dum buklo, kopii ĝin en la nova tabelo, kaj do iel simple forigi tiu tabelo aŭ simple ĉesi uzi ĝin. Sed tio ne estas aparte efika. Mallonge, arrays ne lasu vi dinamike regrandigi. 

Tiel unuflanke vi ricevas hazarda aliro, kiu estas mirinda. Ĉar ĝi permesas nin fari tion kiel dividu kaj regu, duuma serĉo, ĉiuj el kiuj ni parolis sur la ekrano tie. Sed vi pentri vin en angulon. Tuj kiam vi batis la finon de via tabelo, Vi devos fari tre multekosta operacio aŭ skribi tutan faskon da kodo nun trakti kun tiu problemo. 

Do kio se anstataŭ ni devis iu nomita lerta, aŭ ligillisto en aparta? Kio se anstataŭ devi rektanguloj Reen al malantaŭo al malantaŭo, ni havos rektanguloj kiuj lasas malmulte iom de menea ĉambron inter ili? Kaj kvankam mi desegnis tiun bildo aŭ adaptita ĉi bildo de unu el la tekstoj tie esti reen al malantaŭo al malantaŭo tre bonorda, en realo, unu el tiuj rektanguloj povus esti ĝis tie en la memoro. Unu el ili povus esti ĉi tie. Unu el ili povus esti ĝis tie, tien, kaj tiel plu. 

Sed kio se ni tiris, en tiu kazo, Sagojn ke iel ligas tiujn rektanguloj kune? Ja, ni vidis teknikan personigo de sago. Kion ni uzis dum la lastaj tagojn kiuj, sub la kapuĉo, estas reprezentanto de sago? A montrilo, dekstra? 

Do kio se, anstataŭ nur stokante la numerojn, kiel 9, 17, 22, 26, 34, kio se ni stokas ne nur numero sed puntero apud ĉiu tia nombro? Tiel ke multe kiel vi ŝpinas a kudrilo tra tuta fasko da ŝtofo, iel ligante aferoj kune, simile povas ni kun montriloj, kiel korpigitaj de sagoj tie, ia teksas kune tiuj individuaj rektanguloj per efike uzi puntero apud ĉiu numero kiu antaŭ iu proksima nombro, ke notas al tio, siavice, iuj apud numeron? Do alivorte, kion se ni vere volas implementar iu kiel ĉi tiu? Nu, bedaŭrinde, tiuj rektanguloj, almenaŭ unu per 9, 17, 22, ks, tiuj ne plu nice kvadratoj kun sola nombroj. La fundo, rektangulo sub 9, ekzemple, reprezentas kio devus esti montrilo, 32 bitoj. Nun, mi ne rimarkis ian datumtipo en C kiu donas ne nur int sed puntero entute. 

Do kio estas la solvo, se ni volas elpensi nian propran respondon al tio? Yeah? 

Publiko: [inaudible] 

DAVID J. Malan: Kio estas tio? 

Publiko: Nova strukturo. 

DAVID J. Malan: Jes, do kial ni ne kreu novan strukturon, aŭ en C, struct? Ni vidis structs antaŭe, se mallonge, kie oni pritraktis studento strukturo kiel tiu, kiu havis nomon kaj domo. En Pset 3 Breakout vi uzas tutan faskon da structs-- GRect kaj GOvals ke Stanford kreis cluster informo kune. Do kio se ni prenas tiun saman ideon de la ŝlosilvortoj "typedef" kaj "struct" kaj tiam iuj studento-specifajn aferojn, kaj evolui ĉi en la jenaj: typedef struct node-- kaj nodo estas nur tre genérico komputiko termino por io en datumstrukturo, ujo en datumstrukturo. Nodo mi asertas tuj havos kiel int n, tute simpla, kaj do iom pli enigme, tiu dua linio, struct nodo * sekva. Sed en malpli teknika terminoj, kio estas tiu dua linio de kodo ene la frizita krampoj? Yeah? 

Publiko: [inaudible] DAVID J. Malan: A Pointer al alia nodo. Do rekoni, sintakso iom kamufla. Sed se vi legis ĝin laŭvorte, sekvanta estas la nomo de variablo. Kio estas ĝia datumtipo? Estas iom parolema, ĉi tiu fojo, sed estas de tipo struct nodo *. Ajna tempo ni vidis ion stelo, kiu signifas ke estas puntero al tiu datumtipo. Do sekvanta estas ŝajne puntero al struct nodo. 

Nun, kio estas struct nodo? Nu, rimarkos vi vidas tiujn samaj vortoj ĉe supre dekstre. Kaj efektive, vi ankaŭ vidas la vorton "Nodo" cxi tie malsupre maldekstre. Kaj tio efektive estas nur oportuneco. Rimarku, ke en nia studenta difino ekzistas la vorto "studento" nur unufoje. Kaj tio estas ĉar lernanto objekto ne estis mem-referenca. Tie estas nenio ene de lernanto kiu bezonas marki al alia lernantino, persay. Tio estus ia bizara en la reala mondo. 

Sed kun nodo en kunligita lerta, ni volas nodo esti referenca al simila objekto. Kaj tiel rimarkos la ŝanĝon tie ne nur kio estas interne de la frizita krampoj. Sed ni aldonu la vorto "nodo" supre tiel kiel aldoni ĝin al la fundo anstataŭ "studento". Kaj tio estas nur teknika detalo tiel ke, denove, via datumstrukturo povas esti mem-referenca, tiel ke nodo povas noti al alia tia nodo. 

Do kio estas tiu finfine tuj signifos por ni? Nu, oni, ĉi stuff interne estas la enhavo de niaj nodo. Tion ĉi tie, supre dekstre, estas ĝuste tiel ke, denove, ni povas raporti al ni mem. Kaj tiam la plej ekstera stuff, kvankam nodo estas nova termino, eble, ĝi estas ankoraŭ la sama kiel studento kaj kion Estis sub la kastris en SPL. 

Do se ni nun volis komenci implementando ĉi ligillisto, kiom eble ni traduki io tiamaniere kodigi? Nu, ni nur vidas Ekzemplo de programo kiu fakte uzas ligillisto. Inter hodiaŭa dissendo kodo estas programo nomata Listo Zero. Kaj se mi kuros mi kreis la super simpla GUI, grafika interfaco de uzanto, sed ĝi vere nur printf. Kaj nun mi donis min kelkaj menuo options-- Delete, Enmeti, Search, kaj Traverse. Kaj Quit. Ĉi tiuj estas nur komuna operacioj datumstrukturo scias kiel ligilo listo. 

Nun, Forigi tuj forviŝi nombro el la listo. Enmeti tuj aldonu nombro al la listo. Serĉu tuj serĉos por nombro en la listo. Kaj través estas nur ornama metodo diri, trairu la liston presi ĝin, sed tio estas ĝi. Ne ŝanĝu ĝin en ajna formo. 

Do ni provu tion. Ni iru antaŭen kaj tajpi 2. Kaj poste mi iros enmeti la numeron, diru 9. Eniri. Kaj nun mia programo estas ĝuste programita diri, listo estas nun 9. Nun, se mi iru antaŭen kaj ĉu Enmetu denove, lasu min antaŭeniri kaj malzomi kaj tajpu en 17. Nun mia listo estas 9, tiam 17. Se mi faras enmeti denove, ni salti unu. Anstataŭ 22, kiel por la bildo ni estis rigardante tien, mi saltas antaŭen kaj enmeti 26 proksimaj. Do mi tuj tajpi 26. La listo estas kiel mi atendis. Sed nun, nur por vidi se tiu kodo tuj estos fleksebla, lasu min nun tipo 22, kiu almenaŭ koncepte, se ni Subtenante ĉi ordo, kiu estas ja tuj estos alia golo nun, iru en inter 17 kaj 26. Do mi batis Enter. Ja, kiu funkcias. Kaj nun lasu min enmeti la lasta, por la pentraĵo, 34. 

Bone. Do nun lasu min kondiĉas ke Forigi kaj Traverse kaj Serĉo fari, fakte, labori. Fakte, se mi kuros Serĉu, ni serĉi la numero 22, Enter. Ĝi troviĝas 22. Do kiu estas kion ĉi programo Listo Nulo faras. 

Sed kio vere tuj sur tiu implementa ĉi? Nu, unue mi havu, kaj ja Mi havas, dosiero nomata list0.h. Kaj ie tie estas tiu linio, typedef, struct nodo, tiam mi havos mian frizita krampoj, int n, kaj tiam struct-- kio estis la difino? Struct nodo proksima. Do ni bezonas la stelo. Nun teknike ni eniras la kutimo desegni ĝin tien. Vi povus vidi lernolibroj kaj Interreto referencoj fari ĝin tie. Ĝi estas funkcie ekvivalentaj. Fakte, ĉi tiu estas iom pli tipa. Sed Mi estos kohera kun kion ni faris lasta momento kaj faros. Kaj poste laste, mi tuj faros. 

Do en kaplinion dosieron ie, en list0.h hodiaŭ estas ĉi struct difino, kaj eble iuj aliaj aĵoj. Dume en list0c ekzistas tuj estos kelkon. Sed ni tuj simple komenci kaj ne fini ĉi. List0.h dosiero mi volas inkluzivi en mian C dosiero. Kaj tiam, je iu punkto mi tuj havi int, ĉefa, detruos. Kaj poste mi iros havi iun por-do estas ĉi tie. Mi ankaŭ tuj havos prototipo, kiel dezerta, serĉo, int, n, kies celo en la vivo serĉi elementon. Kaj poste malsupren tie mi asertas en hodiaŭa kodo, dezerta, serĉo, int, n, neniu punktokomo sed malfermita krispa krampoj. Kaj nun mi volas iel serĉo por ero en tiu listo. Sed ni ne havas sufiĉan informo sur la ekrano ankoraŭ. Mi ne reale reprezentis la listo mem. Do unu vojo ni povus implementar ligillisto en programo Estas mi specon de voli fari ion kiel deklaras ligillisto tien. Por simpleco, Mi iras fari tiu tutmonda, kvankam ĝenerale oni ne devus fari ĉi tro multe. Sed estos simpligi ĉi ekzemplo. Do mi volas deklari ligillisto tien. Nun, kio povus tion fari? 

Jen la bildo de ligillisto. Kaj mi ne vere konas nuntempe kiel Mi tuj iros pri reprezenti tantas aĵoj kun nur unu ŝanĝiĝema en memoro. Sed pensas reen momente. Ĉiuj ĉi tiu tempo ni havis kordoj, kiujn oni tiam rivelis esti arrays de signoj, kiujn ni poste malkaŝitaj al esti simple puntero al la unua karaktero en tabelo de signoj ke estas nula finita. Do per tiu logiko, kaj kun tiu bildo ia semante viaj pensoj, kion ni bezonas vere skribi en nia kodo por reprezenti ligillisto? Kiom de tiu informo ni bezonas kapti en C kodo, vi dirus? Yeah? 

Publiko: Ni bezonas puntero al nodo. DAVID J. Malan: A puntero al nodo. En aparta, kiu nodo farus vian instinktoj estu teni puntero al? 

Aŭdienco: La unua nodo. 

DAVID J. Malan: Jes, Probable nur la unua. Kaj rimarki, la unua nodo estas malsama formo. Ĝi estas nur duono de la grandeco de la struct, ĉar ĝi estas ja nur puntero. Do kion vi povas ja fari estas deklari ligillisto esti de tipo nodo *. Kaj ni simple nomas ĝin unue kaj pravalorizi ĝin nula. Do nula, denove, estas venanta en la bildo tie. Ne nur estas nula uzita kiel speciala reveno valoro por aĵoj kiel getstring kaj malloc, nula ankaŭ la nulo pointer, la manko de puntero, se vi volas. Ĝi simple signifas nenion ankoraux tie. Nun unue mi povus esti vokis ĉi nenion. Mi povus esti nomis ĝin "listo" aŭ ajna numero de aliaj aĵoj. Sed mi vokas ŝin "unua" por ke ĝi linioj kun tiu bildo. Do ĝuste kiel kordo povas esti reprezentita kun la adreso de lia unua bajto, tiel povas ligillisto. Kaj ni vidos aliaj datumoj strukturoj esti reprezentita kun nur unu montrilo, 32-bitoj sago, montrante je la unua nodo en la strukturo. 

Sed nun ni anticipas problemo. Se mi nur memorante en mia programo la adreso de la unua vertico, la unua rektangulo en tiu datumstrukturo, kion prefere estu la kazo pri la efektivigo de la resto de mia lerta? Kio estas ŝlosila detalo kiu okazas certigi ĉi efektive funkcias? Kaj per "vere funkcias" Mi signifas, multe kiel kordo, lasas nin iri de la unua karaktero en Davin nomon al la dua, la tria, la kvara, por la fino, kiel ni scias, kiam ni fine de ligillisto kiuj aspektas kiel tiu? Kiam ĝi estas nula. Kaj mi reprezentis tian kiel kiel elektra inĝeniero heroajxoj, kun la iom Grounding simbolo de varoj. Sed tio nur signifas nulan en tiu kazo. Vi povas desegni ĝin ajna nombro manieroj, sed tiu aŭtoro okazis uzi tiun simbolon ĉi tie. 

Tiel longe kiel ni stringing ĉiuj tiuj nodoj kune, nur memori kie la unua estas, tiom longe kiel ni metas specialan simbolo la lasta nodo en la listo, kaj ni uzos nula, ĉar tio kion ni havas disponeblaj al ni, tiu listo estas kompleta. Kaj eĉ se mi nur donos vin puntero al la unua elemento, vi, la programisto, certe povas aliri la resto de ĝi. Sed ni lasu vian menson vagadi iom, se ili ne estas jam tute wandered-- kio estas tuj estos la rula tempo de trovinte ion en tiu listo? Damn ĝin, ĝi estas granda O de n, kiu ne estas malbona, juste. Sed estas lineara. Ni forlasis kio trajto de arrays movante pli kun tiu bildo de dinamike kunplektitaj aŭ ligita nodoj? Ni forlasis hazarda aliro. Tabelo estas bela ĉar matematike ĉio Estas malantaŭo al malantaŭo al malantaŭo al malantaŭo. Eĉ kvankam ĉi bildo aspektas bela kaj eĉ kvankam ĝi aspektas kiel tiuj nodoj Estas bele interspacigitaj, reale ili povus esti ie. Ox1, Ox50, Ox123, Ox99, tiuj nodojn povus esti ie. Ĉar malloc faras atribui memoron el la sxlimo, sed ie en la havaĵo. Vi ne nepre scias ke ĝi estas tuj revenos al malantaŭo al malantaŭo. Kaj ĉi tiu portreto en realeco la Ne tuj estos tute tiu bela. 

Do tuj prenos iom el labori por implementar ĉi tiu funkcio. Do ni implementar serĉo nun. Kaj ni vidos specon de saĝa maniero fari tion. Do se mi serĉo funkcio kaj Mi donis variablo, entjero n serĉi, mi bezonas scii la nova sintakso por rigardi interne de strukturo tio indikis, trovi n. Do ni faros. 

Do unue mi tuj iros antaŭeniris kaj deklari nodo *. Kaj mi tuj vokos ŝin pointer, nur konvencio. Kaj mi tuj pravalorizi ĝin unue. Kaj nun mi povas fari tion en kelkaj manieroj. Sed Mi iras preni komunan alproksimiĝon. Dum puntero estas ne egala al nula, kaj tio validas sintakso. Kaj ĝi simple signifas fari la sekvan, do longe kiel vi ne indikas nenion. Kion mi volas fari? 

Se montrilo dot n, lasu min reveni por ke, equals-- egalas kio? Kio valoron mi serĉas? La efektiva n kiu estis pasita en. Do jen alia trajto de C kaj multaj lingvoj. Eĉ kvankam la strukturo nomita nodo havas valoro n, totalmente leĝa ankaŭ havas lokajn argumento aŭ variablon nomis n. Ĉar eĉ ni, kun homaj okuloj povas distingi ke tiu n estas supozeble malsama tiu n. Ĉar la sintakso estas malsama. Vi havas punkton kaj puntero, dum ĉi tiu ne havas tian aferon. Do tio estas okej. Tio estas OK por voki la samaj aferoj. 

Se mi vin trovos ĉi tion, mi tuj volas fari ion kiel anonci ke ni trovis n. Kaj ni lasos tion kiel diri aŭ _pseudocode_ kodon. Alie, kaj jen la interesa parto, kio mi volas fari, se la nuna nodo ne enhavanta n ke mi zorgas pri? Kjel mi atingi la sekva? Se mia fingro en la momento estas PTR, kaj estas fingromontrante ajn unue fingromontrante, kiom mi movi mian fingron al la sekva nodo en kodo? Nu, kio estas la breadcrumb ni tuj sekvas en ĉi tiu kazo? Publiko: [inaudible]. DAVID J. Malan: Jes, tiel proksimaj. Do se mi reiros al mia kodo tie, ja, mi estas tuj iros antaŭen kaj diru montrilo, kio estas nur portempa variable-- estas bizara nomo, PTR, sed estas simple kiel temp-- Mi tuj starigis montrilo egala al ĉiu montrilo is-- kaj denove, tiu tuj estos iom kalesxo por moment-- dot proksima. En aliaj vortoj, mi tuj prenu mian fingro kiu'S fingromontrante tiu nodo tie kaj mi tuj diros, vi scias kio, rigardu la sekvan kampo kaj movi vian fingron kion ajn ĝi estas fingromontrante. Kaj tio tuj ripeti, ripeti, ripeto. Sed kiam faras mian fingron ĉesi fari ion ajn? Apenaŭ kion linio de kodo piedbatoj en? Publiko: [inaudible] DAVID J. Malan: Se punkto dum puntero estas ne egala al nula. En iu punkto de mia fingro La tuj estos fingromontrante nula kaj mi tuj rimarki tio estas la fino de ĉi tiu listo. Nun, tiu estas iom blanka mensogo por simpleco. Ĝi rezultas ke eĉ kvankam ni nur lernis ĉi dot skribmaniero por strukturoj, puntero estas ne struct. PTR estas kio? Nur por esti pli nitpicky. Ĝi estas puntero al nodo. Ne nodo mem. Se mi ne havus stelon tie, montrilo absolutely-- estas nodo. Ĉi tio estas kiel semajno unu deklaro de variablo, kvankam la vorto "nodo" estas nova. 

Sed tuj kiam ni enkonduki stelo, estas nun puntero al nodo. Kaj bedaŭrinde vi ne povas uzi la skalara skribmaniero por puntero. Vi devas uzi la sagon skribmaniero, kiu, surprize, Estas la unua fojo ajna peco de sintakso aspektas intuicia. Ĉi laŭvorte similas sago. Kaj tio estas bona afero. Kaj cxi tie laŭvorte aspektas kiel sago. Do mi kredas ke tio estas la la-- mi ne kredas ke mi tro farante here-- mi kredas ke tio estas la lasta nova peco de sintakso ni tuj vidos. Kaj dankeme, estas ja iom pli intuicia. 

Nun, por tiuj el vi, kiuj eble preferas la malnovan vojon, vi povas ankoraŭ uzi la skalara skribmaniero. Sed kiel ĉiu lundo de konversacio, ni unue bezonas iri tien, iru al tiu alparoli, kaj tiam aliri la kampo. Do ĉi tiu estas ankaŭ korekta. Kaj sincere, tiu estas iom pli pedanta. Vi laŭvorte dirante dereference la puntero kaj iri tie. Tiam kaptu .n, la kampo nomata n. Sed sincere, neniu volas tajpi aŭ legi ĉi. Kaj tial la mondo elpensis la saga skribmaniero, kiu estas ekvivalentaj, identa, ĝi estas nur sintaksa sukero. Do fantazio maniero diri ĉi aspektas bona, aŭ aspektas pli simpla. 

Do nun mi faros unu alia afero. Mi intencis diri "break" iam mi havas trovis tiel mi ne observos serĉante ĝin. Sed tio estas la esencon de serĉo funkcio. Sed estas multe pli facila, en la Fine, ne iru tra la kodon. Tio vere estas la formala efektivigo de serĉo en la hodiaŭa dissendo kodo. Mi kuraĝas diri ke insert ne aparte amuza marŝi tra vide nek estas forviŝi, eĉ kvankam al la fino de la tago ili bolas malsupren sufiĉe simpla heurísticas. 

Do ni faros. Se vi humuro min tien, mi faris alporti faskon de streso pilkojn. Mi alportis faskon de nombroj. Kaj ni povus nur kelkaj volontuloj reprezenti la 9, 17, 20, 22, 29, kaj 34? Do esence ĉiuj kiu estas tie hodiaŭ. Tio estis unu, du, tri, kvar, kvin, ses homoj. Kaj mi petis go-- vidu, neniu unu en la dorso levas siajn manojn. OK, unu, du, tri, kvar, five-- lasu min ŝarĝi balance-- ses. OK, vi ses veni supren. Ni bezonos aliaj homoj. Ni alportis ekstra streso pilkojn. Kaj se vi povis, por nur momente, linio vin sur simple ŝatas ĉi foton tie. 

Bone. Vidu, kia estas via nomo? 

Publiko: Andrew. 

DAVID J. Malan: Andrew, Vi estas nombro 9. Agrable renkonti vin. Tie vi iru. Publiko: Jen. DAVID J. Malan: Jen. David. Numero 17. Jes? 

Publiko: Mi Julia. 

DAVID J. Malan: Julia, Davido. Numero 20. Publiko: kristano. DAVID J. Malan: Christian, David. Numero 22. Kaj? 

Publiko: JP. DAVID J. Malan: JP. Numero 29. Do iru antaŭen kaj akiri in-- Uh oh. Uh oh. Standby. 20. Ĉu iu havas markilon? Publiko: mi hvas Sharpie. DAVID J. Malan: Vi ricevis Sharpie? OK. Kaj ĉu iu havas pecon de papero? Konservu la prelego. Venu. Publiko: Ni havas ĝin. DAVID J. Malan: Ni havas ĝin? Bone, dankon. Ĉi tie ni iru. Estis tiu de vi? Vi nur savis la tagon. Do 29. Bone. Mi malbone skribita 29, sed bone. Antaŭeniri. Bone, mi donos al vi via plumo reen momente. Do ni havas tiujn ulojn tie. Ni havas unu alia. Gabe, ĉu vi volas ludi La unua ero tie? Ni bezonas vin atentigi ĉe tiuj fajnaj homoj. Do 9, 17, 20, 22, varo de 29, kaj tiam 34. Ĉu ni perdas iun? Mi havas 34. Kie did-- OK, kiu volas esti 34? OK, venu supren, 34. Bone, tiu estos bone valoras la klimakso. Kio estas via nomo? 

Publiko: Peter. 

DAVID J. Malan: Petron veni supren. Bone, do jen oni tuta aro de nodoj. Ĉiu el vi uloj reprezentas unu el tiuj rektanguloj. Kaj Gabe, la iomete stranga viro eksteren, reprezentas unue. Do lia puntero estas iom pli malgranda sur la ekrano ol ĉiuj aliaj. Kaj en ĉi tiu kazo, ĉiu el via maldekstra manoj tuj aŭ punkto malsupren tio reprezentas nula, do nur la foresto de puntero, aŭ tuj esti indikante ĉe nodo apud vi. 

Do nun, se vi garnas vi ŝatas la foton tie, iru antaŭen kaj punkto reciproke, kun Gabe en apartaj pintan ĉe numero 9 reprezenti la listo. OK, kaj numeron 34, via maldekstra mano devus ĝuste esti indikante la plankon. 

OK, do tio estas la ligillisto. Do tio estas la scenaro en demando. Kaj efektive, tio estas reprezentanto de klaso de problemoj ke vi eble provu solvi kun kodo. Vi volas finfine enmeti nova elemento en la listo. En ĉi tiu kazo, ni tuj provu la enmeto de la nombro 55. Sed tuj estos malsamaj kazoj por konsideri. Kaj efektive, tiu tuj estos unu de la granda bildo takeaways tie, estas, kio estas la malsamaj kazoj. Kio estas la malsamaj se kondiĉoj aŭ branĉojn ke via programo povus havi? 

Nu, la nombro kiun vi provas insert, kion ni nun scias ke 55, sed se vi ne konas anticipe, mi daresay falas en almenaŭ tri eblaj situacioj. Kie povus nova ero estos? Publiko: Kaj la fino aŭ meze. DAVID J. Malan: Fine, en meze aux komence. Do mi asertas ke estas almenaŭ tri problemojn ni devas solvi. Ni elekti kio estas eble eble la plej simpla , kie la nova elemento apartenas komence. Do mi tuj devos kodo tute kiel esplori, kion mi ĵus skribis. Kaj mi tuj devos PTR, kiu Mi reprezentas ĉi tie kun mia fingro, kiel kutime. 

Kaj memoru, kio valoro ni pravalorizi PTR al? Do ni inicializado ĝin Nula komence. Sed tiam kion ni faros kiam ni interne nia serĉo funkcio? Ni starigis ĝin egala al la unua, kiu ne signifas tion faris. Se mi starigis PTR egala al la unua, kio do mia mano vere fingromontrante? Ĝuste. Do se Gabe kaj mi iras esti egalaj valoroj tie, Ni bezonas ambaŭ punkto je numero 9. 

Do tio estis la komenco de nia historio. Kaj nun jen estas nur simpla, kvankam la sintakso estas nova. Koncepte ĉi estas nur lineara serĉo. Estas 55 egalas 9? Aŭ pli ĝuste, ni diru malpli ol 9. Ĉar mi provas elkompreni kie meti 55. Malpli ol 9, malpli ol 17, malpli ol 20, malpli ol 22, malpli ol 29 malpli ol 34, Ne. Do nun ni estas en kazo unu el almenaŭ tri. 

Se mi volas enigi 55 tie, kio linioj de kodo neceso get ekzekutita? Kiel faras ĉi tiun bildon de homoj bezonas ŝanĝi? Kion mi faru kun mia maldekstra mano? Tio devus esti nula komence, ĉar mi estas ĉe la fino de la listo. Kaj kio devus okazi tie kun Petro, ĉu? Li evidente tuj atentigi min. Do mi asertas ke estas almenaŭ du linioj de kodo en la specimeno kodo de hodiaŭ ke tuj implementar ĉi scenejo de aldoni 55 ĉe la vosto. Kaj mi povus havi iu hop kaj ĝuste reprezentas 55? Bone, vi estas la nova 55. 

Do kion se la sekvanta scenaro venas kune, kaj ni volas enmeti en la komencante aŭ kapo de tiu listo? Kaj kio estas via nomo, la numero 55? 

Publiko: Jack. 

DAVID J. Malan: Jack? OK, agrable renkonti vin. Bonvenon surŝipe. Do nun ni tuj enigi, diru, la numero 5. Jen la dua kazo de la tri ni venis supren kun antaŭe. Do se 5 apartenas al la komenco, ni vidu kiel ni trovos ke ekstere. Mi pravalorizi mia PTR puntero al numero 9 denove. Kaj mi komprenis, ho, 5 estas malpli ol 9. Do ripari ĉi bildon por ni. Kies manoj, Gabe estas aŭ David or-- kio estas numero 9 estas nomata? 

Publiko: Jen. 

DAVID J. Malan: Jen la hands-- kiu el niaj manoj devas ŝanĝi? OK, do Gabe notas al kio nun? Ĉe mi. Mi estas la nova nodo. Do mi simple speco de movado tie por vidi ĝin vide. Kaj dume Kion mi notas, ke? Ankoraŭ kie mi montras. Do jen ĝi. Do nur vere unu linion de kodo korektoj tiu aparta temo, ĝi similus. Bone, do tio estas bona. Kaj ĉu iu esti lokokupilon por 5? Venu supren. Ni ekiru venontfoje. 

Bone, do now-- kaj kiel flanken, la nomoj Mi ne farante eksplicita mencio de dekstra Nun pred montrilo, antaŭulo montrilo kaj novaj montrilo, tio nur la nomoj donitaj en la specimeno kodon por la punteros aŭ miaj manoj, ke la speco de indikante ĉirkaŭe. Kio estas via nomo? 

Publiko: Christine. 

DAVID J. Malan: Christine. Bonvenon surŝipe. Bone, do ni konsideru nun iomete pli ĝena scenaro, per kiu mi volas enigi iu kiel 26 en tiun. 20? Kio? Tiuj are-- bona afero, kiun ni havas ĉi plumo. Bone, 20. Se iu povus ricevi alian pecon de papero preta, nur en case-- gxuste. Ho, interesa. Nu tio estas ekzemplo de prelego cimon. OK do kio estas via nomo denove? Publiko: Julia. DAVID J. Malan: Julia, vi povas pop eksteren kaj ŝajnigi ke vi neniam? OK, ĉi tio neniam okazis. Dankon. Do supozu ni volas enmeti Julia en ĉi ligillisto. Ŝi estas la numero 20. Kaj sendube ŝi tuj aparteni al la begin-- ne noti al io ankoraŭ. Do via mano povas ia esti malsupren nula aŭ iu rubo valoro. Ni diras al la rapidan rakonton. Mi indik numero 5 tiu tempo. Tiam mi kontrolu 9. Tiam mi kontrolu 17. Tiam mi kontrolu 22. Kaj mi rimarkas, Ooh, Julia bezonas iri antaux 22. Do kio devas okazi? Kies manoj bezonos ŝanĝi? Julia, Mia or-- kio estas via nomo denove? 

Publiko: kristano. 

DAVID J. Malan: kristana aŭ? 

Publiko: Andy. 

DAVID J. Malan: Andy. Kristano aŭ Andy? Andy bezonas noti al? Julia. Bone. Do Andy, ĉu vi volas noti al Julia? Sed atendu momenton. En la rakonto tiel multe, Mi estas la speco de unu zorge, en la senco ke montrilo estas la afero tio movante tra la listo. Ni povus havi nomon por Andy, sed ne estas variablo nomis Andy. La sola alia variablo ni estas unua, kiu estas reprezentita de Gabe. 

Do tiu estas efektive kial tiel nun ni ne bezonas tion. Sed nun la ekrano estas mencii denove pred montrilo. Do lasu min esti pli eksplicitaj. Se tiu estas puntero, mi havis pli bonan preni iom pli inteligenta pri mia ripeto. Se vi ne atentas miajn irante tra ĉi tie denove, indikante tie, indikante tie. Sed lasu min havi pred montrilo, antaŭulo montrilo, tio ia fingromontrante la elemento Mi estis ĉe. Do kiam mi iros tien, nun mia maldekstra mano ĝisdatigojn. Kiam mi iras tien mian maldekstran manon ĝisdatigojn. Kaj nun mi devas ne nur puntero al la elemento kiu iras post Julia, Mi ankoraŭ havas puntero al Andy, la elemento antaŭe. Do vi havas aliron, esence, breadcrumbs, se vi volas, al ĉiu el la kondiĉo punteros. 

Do se mi indik Andy kaj mi ankaŭ montrante ĉe kristana, kies manoj nun devus esti rimarkigite aliloke? Do Andy povas nun notas al Julia. Julia povas nun notas al kristano. Ĉar ŝi povas kopii mian dekstra mano la montrilo. Kaj tio efektive metas vin reen en tiu loko tie. Do mallonge, kvankam ĉi prenas al ni specon de ĉiam por vere ĝisdatigi ligillisto, realigi ke la operacioj estas relative simpla. Ĝi estas unu, du, tri linioj de kodo finfine. Sed envolvis ĉirkaŭ tiuj linioj de kodo supozeble Estas iom da logiko kiun efike demandas la demandon, kie ni estas? Ĉu ni komence, la mezo, aŭ la fino? 

Nun, estas certe iu alia operacioj ni povus apliki. Kaj tiuj bildoj tie apenaŭ bildigas kion ni ĵus faris kun homoj. Kio pri forigo? Se mi volas, ekzemple, forigi la numero 34 aŭ 55, Mi ne havas la saman specon de kodo, sed mi bezonos unu aŭ du paŝojn. Pro kio novas? Se mi forigi iu fine, kiel numero 55 kaj tiam 34, kio ankaŭ devas ŝanĝi kiel tion fari? Mi devas ne evict-- kio estas via nomo denove? 

Publiko: Jack. 

DAVID J. Malan: Jack. Mi devas ne nur evict-- libera Jack, tiel laŭvorte nomas libera Jack, aŭ almenaŭ la montrilo tie, sed nun kion bezonas ŝanĝi kun Petro? Lia mano bona komenci indikante malsupren. Ĉar kiam mi vokas libera je Joĉjo, se Petro ankoraŭ fingromontrante Joĉjo kaj mi observu petolanta la listo kaj aliron ĉi puntero, tio estas kiam nia malnova amiko segmentación fault povus efektive piedbati en. Ĉar ni donis la memoron reen al Jack. 

Vi povas resti tie mallerte por nur momento. Ĉar ni havas nur paro fina operacioj al konsideri. Forigado la kapo de la lerta, aŭ beginning-- kaj ĉi onia iom ĝena. Ĉar ni devas scii ke Gabe Estas speco de speciala en tiu programo. Ĉar efektive li havas sian propran montrilo. Li ne nur esti indik, kiel estas preskaŭ ĉiuj aliaj tie. 

Do kiam la estro de la listo estas forigita, kies manoj bezonos ŝanĝi nun? Kio estas via nomo denove? 

Publiko: Christine. 

DAVID J. Malan: Min multe ĉe nomoj, ŝajne. Do Christine kaj Gabe, kies manoj bezonos ŝanĝi kiam oni provas forigi Christine, numero 5, de la bildo? OK, do ni faru Gabe. Gabe tuj atentigi, supozeble, en la numero 9. Sed kion proksima devus okazi? Publiko: Christine devus nula [inaudible]. DAVID J. Malan: Bone, ni devus verŝajne make-- mi aŭdis "nula" ie. Publiko: Nulaj kaj libera sxin. DAVID J. Malan: NULL kio? Publiko: Nulaj kaj libera sxin. DAVID J. Malan: Nulaj kaj libera sxin. Do tio estas tre facila. Kaj ĝi estas perfekta ke vi estas nun speco de starantaj tie ne apartenas. Ĉar vi estis disparigita de la listo. Vi efektive estis orfinoj el la listo. Kaj do ni prefere nomas libera nun Christine doni tiun memoron reen. Alie ĉiufoje ni forigi nodon de la listo ni povus fari la lerta pli mallonga, sed fakte ne malkreskanta la grandeco en memoro. Kaj tiel, se ni plenumas aldonante kaj aldono, aldonante tion al la listo, mia komputilo povus akiri pli malrapida kaj pli malrapida kaj pli malrapida, ĉar mi kurante el memoro, eĉ se mi ne vere uzante Christine bitokoj de memoro anymore. 

Tiel en la fino estas aliaj scenaroj, de course-- forigo en la mezo, forigo fine, kiel ni vidis. Sed la plej interesa defio nun estas tuj estos konsideri ĝuste kion la rula tempo estas. Do ne nur vi povas teni vian pecoj de papero, se, Gabe, Vi ne gravas donante ĉiuj streso pilko. Dankon tiel al nia ligillisto de volontuloj tie, se vi povus. 

[Aplaŭdo] 

DAVID J. Malan: Bone. Do kelkaj analizaj demandojn tiam, se mi povus. Ni vidis ĉi notacio antaŭ, big O kaj omega, superaj baroj kaj subaj baroj sur la rula tempo de iuj algoritmo. Do ni konsideru nur kelkaj demandoj. 

Unu, kaj ni diris antaŭe, kio estas la kurado tempo de Serĉi lerta en terminoj de granda a? Kio estas supera baro sur la kurado tempo de serĉado ligillisto kiel realigitajn de niaj volontuloj tie? Estas granda O de n, lineara. Ĉar en la plej malbona kazo, la elemento, kiel 55, ni povus serĉi povus esti kie Jack, la tutan vojon al la fino. Kaj bedaŭrinde, kontraste tabelo Ni ne povas imagi tiun tempon. Kvankam ĉiuj niaj homoj estis ordo el malgrandaj elementoj, 5 la tutan vojon ĝis la pli granda elemento, 55, kiuj estas kutime bona afero. Sed kion faras tiu supozo ne plu permesos al ni fari? Publiko: [inaudible] DAVID J. Malan: Diru denove? Publiko: Hazarda aliro. DAVID J. Malan: Hazarda aliro. Kaj siavice, kiu signifas, ke ni ne kapablas plu uzi malforta nuloj, intuicio, kaj evidenteco de uzanta duuma esplorrigardi kaj dividi kaj venki. Ĉar kvankam ni homoj povis evidente vidu ke Andy aŭ kristano estis proksimume en la mezo de la lerta, Ni nur scias ke kiel komputilo komencis trakuri la elenco ekde la komenco. Do ni forlasis ke hazarda aliro. 

Tiel granda O de n nun estas la supra ligis sur nia serĉo tempo. Kio pri omega de nia serĉo? Kio estas la suba baro sur serĉado por iu cifero en tiu listo? Publiko: [inaudible] DAVID J. Malan: Diru denove? Publiko: Unu. DAVID J. Malan: Unu. Do konstanta tempo. En la plej bona kazo, Christine estas ĝuste en la komenco de la listo. Kaj ni serĉas numero 5, do ni trovis ŝin. Do ne estas granda interkonsento. Sed ŝi alvenis al esti en la komencante de la listo en ĉi tiu kazo. Kio pri iu kiel Forigi? Kio, se vi volas forigi elementon? Kio supera baro kaj suba baro sur viŝante ion de kunligita listo? Publiko: [inaudible] DAVID J. Malan: Diru denove? Publiko: n. DAVID J. Malan: n estas ja la supera baro. Ĉar en la plej malbona kazo ni klopodos forviŝi Jack, kiel ni ĵus faris. Li estas la tuta vojo al la fino. Nin por ĉiam, aŭ n paŝoj al trovi lin. Do tio estas supera baro. Tio estas lineara, certas. Kaj la plej bona kazo rula tempo, aŭ la subaj baroj en la plej bona kazo estus konstanta tempo. Ĉar eble ni provu forigi Christine, kaj ni metas bonŝanca ŝi komence. Nun atendu minuton. Gabe estis ankaŭ ĉe la komenco, kaj ni ankaŭ devis ĝisdatigi Gabe. Por ke ne estis nur unu paŝo. Do ĉu vere konstanto tempo, en la plej bona kazo, forigi la plej malgranda ero? Ĝi estas, kvankam ĝi povus esti du, tri, aŭ eĉ 100 linioj de kodo, se ĝi estas la sama nombro de linioj, ne en iu ciklo, kaj sendepende de la grandeco el la listo, absolute. Viŝante la elemento ĉe la komenco de la listo, eĉ se ni devas trakti Gabe, ankoraŭ estas konstanta tempo. 

Do tio ŝajnas kiel amasa paŝo malantaŭen. Kaj kio tempoperdo se, en la semajno kaj semajno nulo ni havis ne nur _pseudocode_ kodo sed reala kodo implementar iu kiu estas log bazo n, aŭ ensalutu, prefere, de n, bazo 2, en terminoj de lia rultempo. Do kial la heck estus ni volas komenci uzante iun kiel ligillisto? Yeah. 

Publiko: Do ​​vi povas aldoni elementoj por la tabelo. DAVID J. Malan: Do vi povas aldoni elementojn al la tabelo. Kaj ĉi tiu estas ankaŭ temáticas. Kaj ni daŭre vidos tiu, tiu komerco-off, multe kiel ni vidis komerco-off kun merge varo. Ni povus vere akceli serĉu aŭ ordiga prefere se ni elspezos iom pli da spaco kaj havi plian eron de memoro aŭ tabelo por merge varo. Sed ni elspezos pli spaco, sed ni ŝpari tempon. En ĉi tiu kazo, ni rezignante tempo sed ni estas gajnante fleksebleco, dinamismo se vi volas, kio estas defendeble pozitiva karakterizaĵo. 

Ni ankaŭ elspezante spaco. En kiu senco estas kunligita listo pli multekostaj en terminoj de spaco ol tabelo? Kie estas la ekstra spaco devenante? Yeah? 

Publiko: [inaudible] montrilo. 

DAVID J. Malan: Jes, ni ankaŭ la montrilo. Do tiu estas minorly ĝena en kiu jam ne estas Mi stoki nur int reprezenti int. Mi stokante la int kaj montrilo, kio ankaŭ estas 32 bitoj. Do mi laŭvorte duobliganta la kvanton de spaco implikitaj. Do tio estas la komerco-off, sed tio estas en la kazo de int. Supozu ke vi ne stokante int, sed supozu ĉiu el tiuj rektanguloj aŭ ĉiu de tiuj homoj reprezentis vorto, angla vorto, kiu eble kvin karakteroj, 10 karakteroj, eble eĉ pli. Tiam aldonante nur 32 pli bitoj povus esti malpli granda interkonsento. 

Kio se ĉiu el la studentoj en la manifestacio verdire studento structs ke havas nomojn kaj domoj kaj eble telefonnumerojn kaj Twitter manipulas kaj similaj. Do ĉiuj kampoj ni komencis parolante pri la alia tago, multe malpli grandan interkonsenton kiel niaj nodoj akiras pli interesa kaj granda por elspezi, he, plia puntero simple ligi ilin kune. Sed ja ĝi estas komerco-off. Kaj efektive, la kodo estas pli kompleksaj, kiel vi vidu per komencis trakuri tra ke aparta ekzemplo. Sed kio se ne estis iuj Holy Grail tie. Kio se ni ne prenas paŝo malantaŭen sed amasa paŝo antaŭen kaj implementar datumoj strukturo tra kiu ni povas trovi elementojn kiel Jack aŭ Christine aŭ ajna alia elementoj en tiu tabelo en vera konstanta tempo? Search estas konstanto. Forigi estas konstanta. Enmeti estas konstanta. Ĉiuj de ĉi tiuj operacioj estas konstanto. Tio estus nia Sankta Grial. Kaj tio estas kie ni reprenos venontfoje. Vidi vin tiam.