[Mūzikas atskaņošanai] DAVID J. Malan: Nu labi. Tas ir CS50. Šī ir nedēļa pieci turpinājās, un mēs ir dažas labas ziņas un dažas sliktas ziņas. Tik laba ziņa ir tā, ka CS50 uzsāk šo piektdien. Ja vēlaties mums pievienoties, dodies uz parasto URL šeit. Pat labāk ziņas, ne lekcija tas nāk pirmdiena 13. Nedaudz mazāk labāku ziņas, viktorīna nulle ir nākamo trešdien. Sīkāka informācija var būt atrast šajā URL šeit. Un nākamo pāris dienām mēs būsim aizpildot tukšās attiecībā uz telpām ka mēs esam aizsargātas. Labāka ziņa ir tā, ka tur būs būt pārskatīšanu kursu mēroga sesija šo nāk Pirmdiena vakarā. Sekojiet līdzi kursu s Mājas atrašanās vieta un informāciju. Sekcijas, pat ja tas ir svētki, arī tiksies arī. Labākā ziņa, lekciju nākamajā piektdienā. Tātad šī ir tradīcija mums ir, kā vienu mācību. Just-- tas būs pārsteidzošs. Jūs redzēsiet lietas, piemēram, nemainīgs laika datu struktūras un hash tabulas, kokus un mēģina. Un mēs runājam par dzimšanas dienas problēmām. Viss ķekars sīkumi gaida nākamajā piektdienā. OK. Tik un tā. Tik atgādināt, ka mēs esam bijuši koncentrējoties uz šo ainu par to, kas ir iekšpusē mūsu datora atmiņā. Tātad atmiņu vai RAM ir, ja programmas pastāv, kamēr jūs tos palaižot. Ja jūs dubultklikšķi ikonas, lai palaistu dažas programmas vai veiciet dubultklikšķi ikona atvērt kādu failu, tas ir piekrauts no cietā vadīt vai cietvielu disks RAM, brīvpiekļuves atmiņas, kur tā dzīvo, kamēr atslēdz strāvas padevi, klēpjdators vāks aizveras, vai jūs atmest programmu. Tagad, atmiņa, no kas jums, iespējams, ir 1 gigabaitu šajās dienās, 2 gigabaiti, vai pat daudz vairāk, parasti tiek izklāstīts attiecībā uz konkrētu programmu šāda veida taisnstūra konceptuālais modelis kuru mums ir stack apakšā un ķekars citas lietas augšpusē. Lieta pašā augšā mēs esam redzējuši par šo attēlu agrāk, bet nekad nav runājuši par ir tā saucamā teksta segments. Teksts segments ir tikai iedomātā veids , sakot nullēm un tiem, kas sacerēt savu faktisko apkopoti programmu. Tātad, ja jūs dubultklikšķi Microsoft Word uz jūsu Mac vai PC, vai tad, kad jūs darbināt dot slash Mario uz Linux dators jūsu termināla logā, uz nullēm un tiem, kas veido Vārds vai Mario īslaicīgi tiek uzglabāti Jūsu datora RAM tā saukto teksta segments par konkrētu programmu. Turpmāk, ka iet inicializēts un neinicializētu dati. Tas ir sīkumi, piemēram, globālo mainīgo, ka mēs esam nav izmantoti daudzi, bet reizēm mēs esam bija globālo mainīgo vai statiski noteiktas virknes, kas ir grūti kodēta vārdus kā "hello" , kas nav ņemts no lietotāja kas ir iekodēts savā programmā. Tagad, uz leju apakšā mēs ir ts kaudze. Un kaudze, līdz šim mēs esam bijuši izmantojot, kādos nolūkos? Kas kaudze tikuši izmantoti? Yeah? Mērķauditorija: funkcijas. DAVID J. Malan: For funkcijām? Kādā jēga to funkciju? AUDITORIJA: Kad jūs zvanu funkciju, argumenti tiek kopēti uz kaudze. DAVID J. Malan: Tieši tā. Kad jūs zvanu funkciju, tā argumenti tiek kopēti uz kaudze. Tāpēc jebkuri krustiņus vai Y ir vai ir vai B s ka jūs iet uz funkciju laiku tiek likts uz tā saukto kaudze, tāpat kā viens no Annenberg ēdamzāle paplātes, kā arī lietas piemēram, vietējās mainīgie. Ja jūsu foo funkcija vai jūsu mijmaiņas funkcija ir vietējo mainīgie, tāpat temp, tie divi galu galā uz skursteņa. Tagad, mēs nevarēsim runāt pārāk daudz par viņiem, bet šie vides mainīgajiem apakšā mēs redzējām pirms, bet, kad Man bija futzing pie klaviatūras kādu dienu un es sāku piekļūt lietas piemēram ARGV 100 vai ARGV 1000, vienkārši elements-- es aizmirstu numbers-- bet nebija paredzēts piekļūt ar mani. Mēs sākām redzēt dažus bailīgs simboli ekrānā. Tie bija tā saucamie vides mainīgos tāpat globālo uzstādījumus my programma vai par manu datoru, nevis nesaistīti ar neseno bug, ka mēs apspriedām, Shellshock, ka ir bijis plaguing diezgan dažus datorus. Tagad visbeidzot, mūsdienu fokusā mēs galu galā uz kaudzes. Tas ir vēl viens rieciens atmiņas. Un būtībā tas viss atmiņa ir tās pašas lietas. Tas pats aparatūru. Esam tikai veida apstrādājot dažādus kopu baitu dažādiem mērķiem. Kaudze arī būs kur mainīgie un atmiņas, kas jums pieprasītu no operētājsistēmas tiek īslaicīgi uzglabāti. Bet tur ir sava veida problēma šeit, jo aina nozīmē. Mums veida ir divi kuģiem aptuveni saduras. Jo, kā jūs izmantot vairāk un vairāk skursteņa, un, kā mēs redzam šodien tālāk, kā jūs izmantot vairāk un vairāk kaudze, protams sliktas lietas var notikt. Un tiešām, mēs varam izraisīt, ka tīši vai netīši. Tātad uz cliffhanger pēdējā laiks bija šo programmu, kurā nebija kalpot jebkurš funkcionāla mērķim, kas nav, lai pierādītu kā jūs kā slikts puisis faktiski var veikt priekšrocība bugs kāda programmā un pārņemt programmu vai pat Visa datorsistēma vai serveri. Tik vienkārši skatienu īsi, jums pamanīt, ka main apakšā uzņem komandrindas argumenti, kā vienu ARGV. Un tā ir zvanu uz funkciju f, būtībā nezināms funkciju sauc f, un tas ir kas iet ARGV [1]. Tātad neatkarīgi vārds lietotājs veidi at ātri pēc šīs programmas nosaukumu, un tad tas patvaļīgi funkcija augšu top, f, notiek virknē, AKA char *, kā mēs esam sākuši apspriest, un tas tikai sauc to par "bar". Bet mēs varētu saukt to neko. Un tad paziņo, iekšpusē F, masīva rakstzīmes sauc C- 12 šādiem simboliem. Tagad, ar stāstu man bija spēcīgi Pirms brīža, kad atmiņā ir c, vai arī tiem 12 simboli gatavojas galu galā? Tikai, lai būtu skaidrs. Yeah? AUDITORIJA: Par kaudze. DAVID J. Malan: Par kaudze. Tātad c ir vietējais mainīgs. Mēs prasām 12 rakstzīmēm vai 12 baiti. Tiem, kas gatavojas, lai galu galā uz tā saukto krautnē. Tagad beidzot tas ir citas funkcijas ka patiesībā diezgan noderīgs, bet mēs esam īsti izmantots tā sevi, strncopy. Tas nozīmē virkni kopiju, bet tikai n burtus, n rakstzīmes. Tātad n simboli būs kopēts no bāra uz c. Un cik daudz? Sliedes garumu. Tātad, citiem vārdiem sakot, ka vienā rindā, strncopy, gatavojas kopēt efektīvi bārs, lai c. Tagad, tikai, lai veida prognozēt morālo šo stāstu, to, kas ir potenciāli problemātiska šeit? Pat ja mēs pārbaudīt garumu sliedes un iet to strncopy, kāda ir jūsu zarnu stāsta jums ir joprojām ir sadalīti par šo programmu? Yeah? AUDITORIJA: Neietver telpai null raksturs. DAVID J. Malan: Neietver telpai null raksturs. Potenciāli, atšķirībā iepriekšējā prakse mums nav pat ir tik daudz kā plus 1 līdz uzņemt šo null raksturs. Bet tas ir vēl sliktāk nekā. Ko vēl mēs nedarot? Yeah? Mērķauditorija: [dzirdams] DAVID J. Malan: Perfect. Mēs esam smagi kodēta 12 diezgan patvaļīgi. Tas nav tik daudz problēma, bet fakts ka mēs neesam pat pārbaudīt, ja garums bar ir mazāks par 12, tādā gadījumā tas būs droši nodot to atmiņā sauc c, ka mēs esam piešķirti. Patiešām, ja bārs ir līdzīgi 20 rakstzīmes garš, šī funkcija, šķiet, ir kopēšanas 20 rakstzīmes no bāra uz C, līdz ar to ņemot vismaz 8 baiti , ka tā nedrīkst būt. Tas ir saistība šeit. Tik īsā, bojāta programmas. Nav tik liels darījumu. Varbūt jums segmentāciju vaina. Mēs visi esam bija bugs programmās. Mēs visi varētu būt bugs programmās jau tagad. Bet kāda ir saistība? Nu, šeit ir pietuvināto-in versija ka bilde mana datora atmiņā. Tas ir apakšā mana kaudze. Un tiešām, pašā apakšā ir tas, kas ir sauc mātes rutīnas kaudze, iedomātā veids , sakot, ka ir galvenais. Tā, ka tas, kurš sauc funkciju f, ka mēs runājam par. Tātad šis ir apakšā kaudze. Atgriešanās adrese ir kaut kas jauns. Tas vienmēr ir bijis tur, vienmēr ir bijis šajā attēlā. Mēs vienkārši nekad sauc uzmanību uz to. Jo izrādās ceļš c darbojas, ir ka, ja viena funkcija izsauc otru, ne tikai to argumentus, lai kas funkcija iegūt uzstājām uz steku, ne tikai to funkcija ir vietējā mainīgie iegūt uzstājām uz steku, kaut ko sauc atgriešanās adrese arī izpaužas likts uz skursteņa. Konkrēti, ja galvenās zvani Foo, galvenie s pašu adresi atmiņā, vērsis kaut, efektīvi izpaužas likts uz skursteņa tā, ka tad, kad f tiek darīts izpildes to zina, kur lēkt atpakaļ tekstā segments lai turpinātu izpildes. Tātad, ja mēs esam šeit konceptuāli, pamatdarbā, tad f izpaužas sauc. Kā f zināt, kas uz rokas kontroli atpakaļ? Nu, tas maz atpakaļceļa sarkanā šeit sauc atgriešanās adrese, tā vienkārši pārbaudes, kas ir, ka atgriešanās adrese? Ak, ļaujiet man lēkt atpakaļ uz galveno šeit. Un tas ir mazliet no realitātei, jo nullēm un tiem Maģistrālo ir tehniski up šeit tehnoloģiju segmentā. Bet tas ir ideja. f vienkārši ir jāzina, ko kur kontrole galu galā iet atpakaļ. Bet veids datori jau sen ir izklāstīts lietas piemēram, vietējās mainīgie un argumenti ir līdzīgs šim. Tātad augšpusē bildi zilā ir kaudze rāmis f, lai visi no atmiņas, ka f konkrēti ir izmanto. Tātad attiecīgi, ievērosiet, ka bārs ir šajā attēlā. Bārs bija tā arguments. Un mēs apgalvoja, ka argumenti, lai funkcijas iegūt uzstājām uz skursteņa. C, protams, ir arī šajā attēlā. Un tikai Apzīmējumi mērķiem, paziņojums augšējā kreisajā stūrī ir tas, ko varētu būt c kronšteinu 0 un tad nedaudz uz leju pa labi ir c kronšteins 11. Tātad citiem vārdiem sakot, jūs varat iedomāties ka tur ir režģis baitu tur, no kuriem pirmais ir Augšējā kreisajā, apakšējā no kuriem ir pēdējā no šīm 12 baitu. Bet tagad mēģināt ātri uz priekšu. Kas ir par to, lai notiktu, ja mēs caurlaide tādā stīgu bārā, kas ir ilgāks par c? Un mēs esam ne pārbaudīt, ja tas ir tiešām ilgāk nekā 12. Kura daļa no šī attēla gatavojas get pārrakstīts baitu 0, 1, 2, 3, dot dot dot, 11, un pēc tam slikti, 12, 13, izmantojot 19? Kas notiks šeit, ja jūs secināt no pasūtīšanas ka c bracket 0 ir uz augšu un c kronšteins 11 ir sava veida leju lai labi? Yeah? AUDITORIJA: Nu, tas notiek pārrakstīt char * bar. DAVID J. Malan: Jā, izskatās, ka jūs gatavojas pārrakstīt char * bar. Un sliktāk, ja jūs sūtīt patiešām ilgi string, jūs pat varētu pārrakstīt, ko? Atgriešanās adrese. Kas atkal, ir tāpat kā atpakaļceļa pateikt programmu kur , lai dotos atpakaļ, kad f tiek darīts tiek saukta. Tātad, kādi sliktie puiši parasti darīt ir, ja viņi saskaras ar programmu ka viņi ir ziņkārīgs, vai ir izmantošanu, buggy tādā veidā , ka viņš vai viņa var veikt priekšrocība šī bug, parasti viņi nesaņem šīs tiesības pirmo reizi. Tie sāc nosūtot, piemēram, izlases stīgas uz savu programmu, vai pie klaviatūras, vai atklāti tie, iespējams, uzrakstīt nelielu programmu, lai tikai automātiski ģenerēt stīgas, un sākt banging par savu programmu, nosūtot daudz dažādām ieejām ir dažāda garuma. Tiklīdz jūsu programma avarē, tas ir pārsteidzošs lieta. Jo tas nozīmē, ka viņš vai viņa ir atklājis to, kas ir iespējams, patiešām bug. Un tad viņi var iegūt vairāk gudrs un sākt koncentrēties šaurāka par to, kā izmantot šo bug. Jo īpaši, ko viņš vai viņa varētu darīt, ir sūtīt, labākajā gadījumā, sveiki. Nav liels darījumu. Tas ir virkne, kas ir pietiekami īss. Bet ko tad, ja viņš vai viņa sūta, un mēs vispārināt kā, uzbrukums code-- tik nullēm un tie, kas darīt lietas tāpat kā RM-RF, ka noņemt visu no cietā diska, vai sūtīt surogātpastu vai kaut uzbruktu mašīna? Tātad, ja katrs no šiem burti tikko pārstāv, konceptuāli, uzbrukums, uzbrukums, uzbrukums, uzbrukums, daži slikti kods ka kāds cits rakstīja, bet ja šī persona ir pietiekami gudrs ne tikai ietver visas Šo RM-RFS, bet arī ir viņa pēdējās pāris baiti būt numuru, kas atbilst uz adresi viņa vai viņas pašas uzbrukuma kods , ka viņš vai viņa pagājis tikai nodrošinot to ātru, Jūs varat efektīvi triks datoru vērā pamanījis kad f tiek darīts izpildes, Ak, tas ir laiks man lēkt atpakaļ uz sarkano atgriešanās adresi. Bet tāpēc, ka viņš vai viņa ir kaut pārklājās ka atpakaļadresi ar savu numuru, un viņi pietiekami gudrs , ir konfigurēts, ka numurs atsaukties, kā jūs redzēt super top kreisajā stūrī tur, faktiskā adrese datora atmiņa daži no viņu uzbrukuma kods, slikts puisis var triks datoru uz izpildes savs kods. Un tas kods, atkal, var būt jebkas. Tas ir parasti sauc par apvalks kods, kas ir tikai veids, kā pateikt, ka tas nav vispār kaut kas tik vienkāršs kā RM-RF. Tas ir tiešām kaut kas līdzīgs Bash, vai faktisko programma, kas dod viņam vai viņas programmatiskā kontrole izpildīt kaut kas cits, ka viņi vēlas. Tātad īsumā, tas viss cēlies no vienkāršu faktu ka šī kļūda iesaistīti ne pārbaude robežas jūsu masīvs. Un tāpēc, ka ceļu datoriem darbs, ir tas, ka viņi izmantot kaudzīti no efektīvi, konceptuāli, apakšas uz augšu, bet tad elementi jūs push uz kaudze aug no augšas uz leju, tas ir neticami problemātiska. Tagad tur ir veidi, kā strādāt ap šo. Un godīgi sakot, tur ir valodas ar kuru strādāt ap šo. Java ir imūna, piemēram, uz šo konkrēto jautājumu. Tāpēc, ka viņi nedod jums norādes. Viņi nedod jums tiešie atmiņas adreses. Tātad ar šo spēku, kas mums ir pieskarties kaut atmiņā mēs vēlamies nāk, protams, liels risks. Lai saglabātu acu out. Ja, atklāti sakot, turpmāko mēnešu vai lai gados, jebkurā laikā Jūs lasīt par kādu izmantošanu programmas vai servera, Ja jūs kādreiz redzēt mājienu par kaut ko kā bufera pārpildes uzbrukumu, vai kaudze pārplūdes ir cita veida uzbrukuma, līdzīga garā, cik iedvesmo portāla nosaukums, ja jūs zināt to, tas viss runā par tikko pārpildīta izmēru kādu rakstura masīvs vai kādu masīvs kopumā. Kādi jautājumi, tad, par šo? Nemēģiniet šo mājās. Viss labi. Tātad malloc līdz šim ir bijusi mūsu jaunais draugs, ka mēs varam piešķirt atmiņu , ka mēs ne vienmēr zināt iepriekš, ka mēs gribam, lai mums nav cietā kodu mūsu programmu numuri, piemēram, 12. Tiklīdz lietotājs stāsta mums, cik daudz datus, kurus viņš vai viņa vēlas, lai ievadītu, mēs varam malloc ka daudz atmiņu. Tātad malloc izrādās, lai lielā mērā mēs esam bijis, izmantojot to, tieši pēdējā laikā, un pēc tam jums puiši ir bijis, izmantojot to par getstring neapzināti par vairākas nedēļas, visi malloc atmiņu nāk no tā sauktās kaudzē. Un tas ir iemesls, kāpēc getstring, piemēram, var piešķirt atmiņu dinamiski nezinot, kas tu esi gatavojas rakstīt iepriekš, roku jūs atpakaļ rādītāju uz šo atmiņu, un ka atmiņa ir vēl jūsu, lai saglabātu, pat pēc getstring atdevi. Jo atgādināt galu galā, ka kaudze ir pastāvīgi iet uz augšu un uz leju, uz augšu un uz leju. Un, tiklīdz tas notiek uz leju, tas nozīmē, ka jebkurš atmiņu šī funkcija izmanto vajadzētu nedrīkst izmantot kāds cits. Tas ir atkritumu vērtības tagad. Bet kaudze ir šeit. Un, kas ir jauka par malloc ir tas, ka kad malloc piešķir atmiņu šeit, tas nav ietekmējis, jo lielākā daļa, ko kaudze. Un tāpēc jebkurš funkciju var piekļūt atmiņu, kas ir malloc'd, pat funkciju kā getstring, pat pēc tam tiek atgriezta. Tagad, sarunāties ar malloc ir bez maksas. Un tiešām, jūs noteikums nepieciešams, lai sāktu pieņemot ir jebkurš, jebkurš, jebkurā laikā jūs izmantojat malloc jums ir sevi izmantot bez, galu galā, tajā pašā rādītājs. Visu šo laiku mēs esam rakstiski buggy, buggy kodu, daudzu iemeslu dēļ. Bet viens no kuriem ir izmantojot CS50 bibliotēku, kas pati par sevi ir apzināti buggy, tas noplūdes atmiņu. Jebkurā laikā jūs esat sauc getstring pēdējo nedēļu laikā mēs jautā darboties sistēma, Linux, atmiņu. Un jūs nekad reiz dota to atpakaļ. Un tas nav, kas prakse, ir laba lieta. Un Valgrind, viens no ieviestie PSET 4 instrumenti, ir viss, lai palīdzētu jums Tagad atrast kļūdas, piemēram, ka. Bet par laimi, lai PSET 4 jums nav nepieciešams izmantot CS50 bibliotēku vai getstring. Tātad kādi bugs, kas saistīti ar atmiņu, ir galu galā būs savu. Tātad malloc ir vairāk nekā tikai ērta šim nolūkam. Mēs faktiski tagad var atrisināt fundamentāli atšķirīgas problēmas, un fundamentāli atrisināt problēmas vairāk efektīvi nedēļā nullei solījums. Līdz šim tas ir sexiest datu struktūra mēs esam bija. Un datu struktūra es tikai domāju veids conceptualizing atmiņas tādā veidā, kas pārsniedz vienkārši sakot, Tas ir int, tas ir char. Mēs varam sākt klastera lietas kopā. Tik masīvs izskatījās. Un kāda bija galvenais apmēram masīvs ir, ka tas dod jums back-to-back gabalos atmiņa, no kuriem katrs būs tāda paša veida, int, int, int, int, vai char, palija, palijas, char. Bet tur ir dažas ēnas. Tas, piemēram, ir masīvs izmēra sešiem. Pieņemsim, ka jūs aizpildīt šo masīvu ar sešiem numuri un tam, kādu iemeslu dēļ, jūsu lietotāja vēlas dot Jūs septīto numuru. Ja jūs nodot to? Kāds ir risinājums, ja Jums ir radīja masīvu uz skursteņa, Piemēram, tikai ar nedēļu divi notācija ka mēs ieviesām, kvadrātveida iekavās ar vairākiem iekšā? Nu, jūs esat ieguvuši sešas numuri šajos lodziņos. Kādi būtu jūsu instinkti būt? Kur jūs vēlaties, lai to? Mērķauditorija: [dzirdams] DAVID J. Malan: Sorry? AUDITORIJA: Put to uz beigām. DAVID J. Malan: Put to uz beigām. Tātad tikai nedaudz vairāk pa labi, ārpus šīs kastes. Kas būtu jauki, bet tas Izrādās, jūs nevarat darīt. Jo, ja jūs esat nav jautāts Šim rieciens atmiņas, tas varētu būt sagadīšanās, ka šis tiek izmantota kāda cita mainīgā vispār. Domāju, ka atpakaļ nedēļā, vai arī tad, kad mēs noteikti out Zamyla un Davin un Gabe ir nosaukumi atmiņā. Viņi bija burtiski atpakaļ atpakaļ uz muguras. Tātad, mēs varam ne vienmēr ticu, ka kāda ir nekā šeit ir pieejama man izmantot. Tātad, ko vēl jūs varētu darīt? Nu, vienreiz realizējot jums vajag masīvu izmēra septiņu, jūs varētu tikai radīt masīvs izmēra septiņu tad izmantojiet cilpa vai kamēr cilpa, kopēt to jaunajā masīvs, un tad kaut kā vienkārši atbrīvoties no šis masīvs vai vienkārši pārtraukt to lietot. Bet tas nav īpaši efektīva. Īsāk sakot, masīvi neļaujiet Jūs dinamiski mainīt. Tātad, no vienas puses, jums brīvpiekļuves, kas ir pārsteidzošs. , Jo tas ļauj mums darīt lietas piemēram, skaldi un valdi, bināro meklēšanu, viss, ko mēs esam runāja par uz ekrāna šeit. Bet jūs krāsas sevi stūrī. Tiklīdz jūs hit beigās jūsu masīvs, Jums ir jādara ļoti dārga operācija vai uzrakstīt veselu ķekars kodu tagad galā ar šo problēmu. Tātad, ko tad, ja tā vietā mums bija kaut ko sauc par sarakstu, vai saistīta sarakstu, jo īpaši? Ko darīt, ja tā vietā, taisnstūri atpakaļ atpakaļ uz muguras, mums ir taisnstūri, kas atstāj maz mazliet valstīties telpā starp tām? Un, kaut arī es esmu sastādīts šis attēlu vai pielāgoti šo attēlu no viena uz tekstu šeit, lai būtu atpakaļ atpakaļ atpakaļ ļoti kārtīgi, patiesībā, viens no šiem taisnstūriem varētu būt šeit atmiņā. Viens no tiem varētu būt šeit. Viens no tiem varētu būt šeit, nekā šeit, un tā tālāk. Bet ko tad mēs vērsa, šajā gadījumā, bultas ka kaut kā saistīt šos taisnstūri kopā? Patiesi, mēs esam redzējuši tehnisks iemiesojums bultiņu. Ko mēs esam izmantoti nesen dienas, ka zem motora pārsega, tiek uzrādīts bultiņu? Rādītājs, vai ne? Tātad, ko tad, tā vietā, vienkārši uzglabātu numurus, piemēram, 9, 17, 22, 26, 34, kas notiks, ja mēs uzglabāt ne tikai numurs, bet rādītājs blakus katru šādu numuru? Tā, ka daudz, piemēram, jūs varētu pavedienu adatu cauri visai ķekars auduma, kaut kā sasaisti lietas kopā, tāpat var mēs ar norādes, kā iemiesojies ar bultiņām šeit veida aust kopā individuālie taisnstūri efektīvi izmantojot rādītāju blakus katram numuram norāda uz kādu nākamo numuru, kas punktu, kas, savukārt, daži nākamais numurs? Tātad citiem vārdiem sakot, ja mēs patiesībā gribēju īstenot kaut kas līdzīgs šim? Nu diemžēl šie taisnstūri, Vismaz viens ar 9, 17, 22, un tā tālāk, tie vairs nav jauki laukumi ar vienu numuru. Apakšējā, taisnstūris līdz 9, piemēram, atspoguļo to, ko vajadzētu būt rādītājs, 32 biti. Tagad, es neesmu vēl informēts par jebkādu datu tipa C, kas dod jums ne tikai int bet rādītājs kopumā. Tātad, kas ir risinājums, ja mēs vēlamies izgudrot savu atbildi uz šo? Yeah? Mērķauditorija: [dzirdams] DAVID J. Malan: Kas tas tāds? AUDITORIJA: Jauna struktūra. DAVID J. Malan: Jā, tad kāpēc ne mēs izveidot jaunu struktūru, vai C, struct? Mēs esam redzējuši statņi iepriekš, ja īsi, kur mēs nodarbojas ar studentu struktūru , piemēram, tas, kas bija vārdu un māju. In PSET 3 breakout tu izmanto veselu ķekars structs-- GRect un GOvals ka Stanford izveidota, lai klasteris informāciju kopā. Tātad, ko tad, ja mēs šo pašu domu par atslēgvārdi "typedef" un "struct," un tad dažas studentu specifiskās sīkumi, un attīstās to vērā šādi: typedef struktūrai node-- un mezglu tikai ļoti vispārīgas datorzinātņu termins kaut kādā datu struktūru, konteineru datu struktūrā. Mezgls es varu pieprasīt nāksies int n, pilnīgi vienkārša, un tad nedaudz vairāk cryptically, šī otrā līnija, struct mezglā * nākamo. Bet mazāk tehniskā ziņā, to, kas ir, ka otrā rinda koda iekšpusē cirtaini lencēm? Yeah? Mērķauditorija: [dzirdams] DAVID J. Malan: rādītāju uz citu mezglu. Tātad, protams, sintakses mazliet noslēpumains. Bet, ja jūs lasīt to burtiski, nākamais ir nosaukums mainīgo. Kas ir tās datu tips? Tas ir nedaudz runīgs šoreiz, bet tas ir tipa struct mezglā *. Katru reizi, kad mēs esam redzējuši kaut zvaigzne, ka nozīmē, ka tas ir rādītājs uz šo datu tipu. Tātad nākamais ir acīmredzot rādītāju uz struct mezglā. Tagad, kas ir struct mezglā? Nu, ievērosiet redzat tiem paši vārdi pie augšējā labajā stūrī. Un tiešām, jūs arī redzēt vārdu "Mezgls", noteikti šeit apakšā pa kreisi. Un tas ir faktiski tikai ērtības. Ievērojiet, ka mūsu studentu definīcijā tur ir vārds "students" tikai vienu reizi. Un tas ir tāpēc, ka students objekts bija ne sevi godbijīgs. Tur nekas iekšpusē students kas nepieciešams, lai norādītu uz citu students, persay. Tas būtu sava veida dīvaini reālajā pasaulē. Bet ar mezglu saistīta sarakstu, mēs vēlamies mezglu būt par saistītu ar līdzīgu objektu. Un tā ievērojat izmaiņas šeit nav tikai to, kas ir iekšpusē cirtaini lencēm. Bet mēs pievienojam vārdu "mezglu" augšdaļā, kā arī pievienojot to apakšā vietā "students." Un tas ir tikai tehniska detaļa tā, ka, atkal, jūsu datu struktūra var būt self-saistītie, tā, lai mezglu var norādīt uz citu šādu mezglu. Tātad, kas tas ir galu galā gatavojas nozīmē mums? Nu, viens, šī stuff iekšā ir saturs mūsu mezglā. Šī lieta šeit, augšā pa labi, ir tikai tik ka, atkal, mēs varam atsaukties uz sevi. Un tad attālākajos sīkumi, pat ja mezgls ir jauns termins, varbūt, tas joprojām pats kā students un ko bija zem motora pārsega, kas SPL. Tātad, ja mēs tagad gribēju sākt Īstenojot šo saistīts sarakstu, kā mēs varētu iztulkot kaut kas līdzīgs šo kodu? Nu, pieņemsim tikai redzēt piemērs programmai, kas faktiski izmanto saistīts sarakstu. Starp šodienas izplatīšanas kodu ir programma, ko sauc saraksts Zero. Un, ja es palaist šo es izveidojis super vienkāršu GUI, grafiskā lietotāja saskarne, bet tas tiešām tikai printf. Un tagad es esmu devis sev dažas izvēlni options-- Dzēst, ievietošana, Search, un Traverse. Un Iziet. Šie ir tikai kopīgas operācijas datu struktūra pazīstams kā saite sarakstā. Tagad, Dzēst gatavojas dzēst numuru no saraksta. Ievietot gatavojas pievienot numuru sarakstā. Meklēšana ir gatavojas meklēt par numuru sarakstā. Un traversa ir tikai iedomātā veids , sakot, staigāt pa sarakstu, izdrukāt to ārā, bet tas arī viss. Nemaina to nekādā veidā. Tātad, pieņemsim mēģināt šo. Iesim uz priekšu un 2 tips. Un tad es esmu gatavojas ievietot numuru, saka 9. Enter. Un tagad mana programma ir tikai ieprogrammēts teikt, saraksts tagad ir 9. Tagad, ja man iet uz priekšu un do Ievietojiet atkal, ļaujiet man iet uz priekšu un tālināt un ierakstiet 17. Tagad mans saraksts ir 9, tad 17. Ja es to ievietot atkārtoti, pieņemsim izlaist vienu. Nevis 22, kā vienu attēlu mēs esam ir meklē šeit, ļaujiet man lēkt uz priekšu un ievietojiet 26 nākamo. Tāpēc es esmu gatavojas rakstīt 26. Saraksts ir, kā es gaidīt. Bet tagad, tikai, lai redzētu, vai šo kodu būs elastīga, ļaujiet man tagad 22 tipa, kas ir vismaz konceptuāli, ja mēs esam Paturot to sakārtoti, kas patiešām būs vēl viens mērķis tieši tagad, jāiet starp 17 un 26. Tāpēc es hit Enter. Patiešām, kas darbojas. Un tāpēc tagad ļaujiet man ievietot pēdējais, vienu attēlu, 34. Viss labi. Tātad tagad ļaujiet man noteikt, ka Dzēst un Traverse un Search darīt, patiesībā, strādā. Patiesībā, ja man palaist meklēšanu, pieņemsim meklēt numuru 22, Enter. Tā konstatēja 22. Tātad, kas ir tas, ko šis Programma Saraksts Zero dara. Bet kas patiesībā notiek gada, kas īsteno šo? Nu, vispirms es varētu būt, un patiešām Man ir, failu sauc list0.h. Un kaut kur ir šī līnija, typedef, struktūrai mezglā, Tad man ir cirtaini bikšturi, int n, un tad struct-- kāda bija definīcija? Struct mezglā nākamo. Tāpēc mums ir nepieciešams zvaigzni. Tagad tehniski mēs nokļūt ieradums zīmēšanas to šeit. Jūs varētu redzēt grāmatas un tiešsaistes atsauces darīt tur. Tas ir funkcionāli līdzvērtīgi. Faktiski, tas ir nedaudz vairāk tipisks. Bet es būšu saskaņā ar ko mēs darījām pēdējo laiku un darīt to. Un tad visbeidzot, es esmu gatavojas darīt. Tātad galvenes failā kaut kur, jo list0.h šodien tas ir struct definīcija, un varbūt daži citi sīkumi. Tikmēr list0c tur būs dažas lietas. Bet mēs ejam vienkārši sākuma un nav pabeigta to. List0.h ir fails es gribu iekļaut manu C failā. Un tad kādā brīdī es esmu nāksies int, galvenais, par spēkā neesošu. Un tad es esmu gatavojas ir dažas to-do ir šeit. Es esmu arī nāksies prototips, tāpat kā spēkā neesošu, meklēt, t.sk., n, kuru mērķis dzīvē ir lai meklētu elementa. Un tad noteikti šeit es apgalvot, šodienas kods, spēkā neesošu, meklēt, int, n, nē semikols bet atvērtas cirtaini bikšturi. Un tagad es gribu, lai kaut kā meklēt par elementu šajā sarakstā. Bet mums nav pietiekami daudz informāciju uz ekrāna vēl. Man nav reāli pārstāvēja pašu sarakstu. Tātad viens veids, kā mēs varētu īstenot saistīts saraksts programmā ir es veida gribu darīt kaut ko tāpat deklarēt saistīts saraksts šeit. Vienkāršības labad, es esmu gatavojas darīt šis pasaules, kaut arī kopumā mēs nedrīkst darīt pārāk daudz. Bet tas būs vienkāršot šo piemēru. Tāpēc es gribu paziņot saistīts saraksts šeit. Tagad, kā varētu man darīt? Lūk attēls saistītajā sarakstā. Un man nav īsti zināt brīdī how Es iešu par pārstāvot tik daudz lietas ar tikai vienu mainīgais atmiņā. Bet domāju, ka atpakaļ brīdi. Visu šo laiku mēs esam bija virknes, kas mēs pēc tam atklāja, ka bloki zīmes, kuras mēs pēc tam atklāja vienkārši rādītājs ar pirmo raksturs masīva rakstzīmes kas ir null izbeigta. Tātad, šī loģika, un ar to attēlu veida sētu savas domas, Ko nepieciešams mēs faktiski rakstīt mūsu kods pārstāvēt saistīts sarakstu? Cik daudz no šīs informācijas mēs vajag sagūstīt C kodu, jūs teiktu? Yeah? AUDITORIJA: Mums ir nepieciešams rādītāju uz mezglu. DAVID J. Malan: rādītājs uz mezglu. Jo īpaši, kas mezgls būtu jūsu instinkti būt saglabātu rādītāju? AUDITORIJA: Pirmais mezglā. DAVID J. Malan: Jā, iespējams tikai pirmais. Un paziņojums, pirmais mezgls ir atšķirīgas formas. Tas ir tikai puse lielums struktūrai, tāpēc, ka tas ir tiešām tikai rādītājs. Tātad, ko jūs tiešām varat darīt, ir pasludināt saistīts saraksts būt tipa mezglā *. Un pieņemsim tikai sauc to pirmo reizi un inicializēt to null. Tātad nulle, atkal, ir nāk stājas attēlu šeit. Ne tikai null izmanto kā, piemēram, īpašu atgriešanās vērtību lietām, piemēram getstring un malloc, null ir arī nulle rādītājs, nav rādītājs, Ja jūs. Tas tikai nozīmē, nekas vēl šeit. Tagad pirmo reizi, es varētu esam sauc to neko. Es varētu būt to sauca "saraksts" vai kādu citu lietu skaits. Bet es esmu nosaucot to par "pirmo reizi", lai tā līniju līdz ar šo bildi. Tātad tāpat kā virkne var attēlot ar adresi savu pirmo baitu, tā var saistīts saraksts. Un mēs redzēsim citus datus pārstāvēta struktūras tikai ar vienu rādītāju, 32-bit bulta, norādot pašā pirmajā mezglā struktūrā. Bet tagad pieņemsim paredzēt problēmu. Ja es esmu tikai atceroties manā programmā adresi pirmā mezgla, pirmais taisnstūris šajā datu struktūru, kādi bija labāk lietu par par pārējo manu sarakstu ieviešana? Kas ir galvenais detaļa, kas notiek Lai to nodrošinātu faktiski darbojas? Un "faktiski darbojas" I domāju, līdzīgi virknes, ļauj mums iet ar pirmo rakstzīmi in Davin vārdu uz otro, uz trešo, lai ceturtkārt, uz pašām beigām, kā mēs zinām, kad mēs esam beigās no saistīta sarakstu, kas izskatās šādi? Kad tas ir null. Un es esmu pārstāvēta šāda veida, kā tāpat kā elektromehāniķi spēku, ar nelielu sēkļa simbols, nelāgi. Bet tas tikai nozīmē, null šajā gadījumā. Jūs varat izdarīt to jebkādu skaitu veidos, bet šis autors noticis izmantot šo simbolu šeit. Tik ilgi, kamēr mēs esam rindu visas šīs mezglu kopā, tikai atcerēties, kur Pirmais ir, tik ilgi, kamēr kā mēs pievērsām īpašu simbolu pie Pašā pēdējā mezglu sarakstā, un mēs izmantosim null, jo tas ir kas mums ir pieejami pie mums, šis saraksts ir pilnīgs. Un pat tad, ja man ir tikai jums rādītāju uz pirmais elements, jums, programmētājs, noteikti var piekļūt pārējo tā. Bet pieņemsim ļaujiet jūsu prātus klīst mazliet, ja viņi jau nav diezgan wandered-- kas ir būs darbības laiks atrast kaut ko šajā sarakstā? Damn tas, tas ir liels O n, kas nav slikti, jo taisnīgumu. Bet tas ir lineārs. Mēs esam atteikušies no kāda iezīme par masīvu, pārvietojot vairāk pret šo attēlu dinamiski austi kopā vai saistīti mezglu? Mēs esam atteikušies brīvpieejas. Masīvs ir jauki, jo matemātiski viss ir atpakaļ atpakaļ atpakaļ atpakaļ. Pat ja šo attēlu izskatās diezgan, un pat lai gan tas izskatās šiem mezgliem ir labi atstarpi, patiesībā tie varētu būt jebkur. OX1, Ox50, Ox123, Ox99, šie mezgli varētu būt jebkur. Jo malloc dara piešķirt atmiņu no kaudzes, bet jebkur kaudzē. Jums nav obligāti zināt, ka tas ir būs atpakaļ atpakaļ atpakaļ. Un tāpēc šī aina realitāte s nebūs gluži tas diezgan. Tātad, tas notiek, lai mazliet strādās, lai īstenotu šo funkciju. Tāpēc pieņemsim īstenot meklēšanu tagad. Un mēs redzēsim veida gudrs veids, kā to izdarīt. Tātad, ja es esmu meklēšanas funkciju un Es esmu dota mainīgo, skaitlim n meklēt, man ir nepieciešams zināt Jaunais sintakse meklē iekšā kādas struktūras, kas ir norādīja uz, lai atrastu n. Tāpēc pieņemsim to izdarītu. Tātad vispirms es iešu priekšu un atzīt mezglu *. Un es esmu gatavojas to nosaukt rādītājs, tikai pēc vienošanās. Un es esmu gatavojas, lai sāktu to vispirms. Un tagad es varu darīt vairākos veidos. Bet es esmu gatavojas pieņemt kopēju pieeju. Kamēr rādītājs nav vienāds ar null, un tas ir derīgs sintakse. Un tas nozīmē tikai to, rīkojieties šādi, tāpēc Kamēr jūs neesat norādot pie nekas. Ko es gribu darīt? Ja rādītājs dot n, ļaujiet man atgriezties to, ka, equals-- vienāds ko? Kāda vērtība es meklēju? Faktiskais n, kas tika pieņemts. Tātad, šeit ir vēl viens elements C un daudzās valodās. Pat ja struktūru sauc mezglā ir vērtība N, pilnīgi likumīgu lai ir arī vietējo arguments vai mainīgs sauc n. Tāpēc, ka pat mēs, ar cilvēka acīm, var atšķirt ka tas n ir, iespējams atšķiras no šī n. Jo sintakse ir atšķirīgs. Tev dot un rādītāju, tā kā šis viens nav tādas lietas. Tātad tas ir OK. Tas ir OK, lai izsauktu tās pašas lietas. Ja es jūs atrast, es esmu gatavojas vēlaties darīt kaut ko tāpat kā paziņot, ka mēs atradām n. Un mēs ņemšu atvaļinājumu, ka komentēt vai pseudocode kodu. Cits, un šeit ir Interesantākais, ko es gribu to darīt, ja pašreizējā mezglā tiek nesatur n, ka man rūp? Kā es varu panākt sekojošo? Ja mans pirkstu moments ir PTR, un tas ir norādot jebkādā Pirmais ir norādot uz, kā es varu pārvietot manu pirkstu uz nākamo mezglu kodu? Nu, kas ir atpakaļceļa mēs esam gatavojas sekot šajā gadījumā? AUDITORIJA: [nedzirdama]. DAVID J. Malan: Jā, tā nākamais. Tātad, ja es dodos atpakaļ uz manu kods šeit, protams, es esmu gatavojas iet uz priekšu un saka rādītāju, kas ir tikai pagaidu variable-- tas ir dīvainais nosaukums, PTR, bet tas ir tāpat kā temp-- Es esmu gatavojas noteikt rādītāju vienāds ar kāda rādītāju is-- un atkal, tas būs nedaudz buggy par moment-- dot nākamo. Citiem vārdiem sakot, es esmu gatavojas pieņemt manu pirkstu, kas ir vērsta šajā mezglā šeit, un es esmu gatavojas teikt, jūs zināt ko, ieskatieties nākamo lauku un pārvietot savu pirkstu, lai neatkarīgi no tā norādot uz. Un tas notiek, lai atkārtot, atkārtot, atkārtot. Bet, kad tas savu pirkstu pārtraukt darīt kaut ko vispār? Tiklīdz kāda līnija koda kicks in? Mērķauditorija: [dzirdams] DAVID J. Malan: Ja punkts, bet rādītājs nav vienāds ar null. Kādā brīdī mans pirksta būs norādot uz null un es esmu gatavojas realizēt ka ir beigas šajā sarakstā. Tagad, tas ir maz balta meli vienkāršību. Izrādās, ka pat tad, ja mēs tikko uzzināju šo dot notācija struktūrām, rādītājs nav struktūrai. PTR ir kas? Vien vairāk nitpicky. Tas ir rādītājs, lai mezglu. Tas nav mezglu pati. Ja man nebija zvaigzne šeit, rādītājs absolutely-- tas mezglā. Tas ir tāpat kā nedēļu viens deklarācija ir mainīgs, pat ja vārds "mezgls" ir jauns. Bet, tiklīdz mēs ieviest zvaigzne, tas tagad ir rādītājs, lai mezglu. Un diemžēl jūs nevarat izmantot dot notācija par rādītāju. Jums ir izmantot bultiņu apzīmējums, kas pārsteidzoši, Pirmo reizi kāda no daļām no sintakse izskatās intuitīvi. Tas burtiski izskatās kā bulta. Un tā tas ir laba lieta. Un šeit lejā burtiski izskatās kā bulta. Tāpēc es domāju, ka la-- man nav domāju, ka es esmu pārāk izdarīšanas here-- I domāju, ka ir pēdējais jaunais gabals no sintakses mēs ejam, lai redzētu. Un par laimi, tas ir patiešām nedaudz vairāk intuitīvi. Tagad, tiem no jums, kas varētu dod veco ceļu, Jūs joprojām varat izmantot dot notācija. Bet kā vienu pirmdienas saruna, mēs vispirms jādodas tur, dodieties uz, ka risināt, un pēc tam piekļūt lauku. Tātad tas ir arī pareizi. Un godīgi sakot, tas ir nedaudz vairāk pedantiska. Tu burtiski sakot, dereference rādītājs un iet tur. Tad paķert .n, lauka sauc n. Bet atklāti sakot, neviens negrib rakstīt vai lasīt šo. Un tā pasaule izgudrots bultiņa notācija, kas ir līdzvērtīga, identisks, tas ir tikai sintaktisko cukura. Tātad iedomātā veids, kā sakot izskatās labāk, vai izskatās vienkāršāk. Tāpēc tagad es esmu gatavojas darīt vienu citu lietu. Es esmu gatavojas teikt "pārtraukums", kad es esmu atrada to, lai man nav turēt meklē to. Bet tas ir būtība no meklēšanas funkciju. Bet tas ir daudz vieglāk, jo end, nevis staigāt pa kodu. Tas ir patiešām formāla ieviešana Meklēšanas mūsdienu izplatīšanas kodu. Es uzdrošinos teikt, ka ieliktnis nav īpaši jautri staigāt pa vizuāli, nedz dzēst, pat gan beigās dienā viņi vāra uz leju, lai godīgi vienkāršas heuristics. Tāpēc pieņemsim to izdarītu. Ja jūs humors mani šeit, es darīju celt ķekars stresa bumbas. Es, kas ķekars numuriem. Un mēs varētu saņemt tikai dažus brīvprātīgos pārstāvēt 9, 17, 20, 22, 29 un 34? Tātad būtībā ikviens kurš šeit šodien. Tas ir viens, divi, trīs, četri, pieci, seši cilvēki. Un es esmu lūgts go-- redzēt, ne viens aizmugurē rada viņu rokās. OK, viens, divi, trīs, četru, five-- ļaujiet man slodze balance-- seši. OK, tu seši nākt uz augšu. Mums būs nepieciešams citu cilvēku. Mēs celta papildus stresa bumbas. Un, ja jūs varētu, tikai mirklis, līnijas paši veido tikai patīk šī attēla šeit. Viss labi. Paskatīsimies, kāds ir tavs vārds? AUDITORIJA: Andrew. DAVID J. Malan: Andrew, Jums ir vairāki 9. Prieks iepazīties. Šeit jums iet. AUDITORIJA: Jen. DAVID J. Malan: Jen. David. Numurs 17. Jā? AUDITORIJA: Es esmu Julia. DAVID J. Malan: Julia, David. Numurs 20. AUDITORIJA: Christian. DAVID J. Malan: Christian, David. Numurs 22. Un? AUDITORIJA: JP. DAVID J. Malan: JP. Numurs 29. Tik iet uz priekšu un iegūt in-- Uh oh. Uh oh. Gaidīšanas. 20. Vai kāds ir marķieri? AUDITORIJA: Man Sharpie. DAVID J. Malan: Tev sharpie? OK. Un vai kāds ir papīra? Saglabājiet lekciju. Come on. AUDITORIJA: Mēs esam ieguvuši to. DAVID J. Malan: Mēs saņēmām to? Nu labi, paldies. Šeit mēs iet. Bija tas no jums? Jūs vienkārši saglabāts dienā. Tā 29. Viss labi. Es kļūdaini 29, bet OK. Iet uz priekšu. Nu labi, es došu jums savu pildspalvu atpakaļ momentāni. Tāpēc mums ir šiem ļaudīm šeit. Pieņemsim ir viens otru. Gabe, jūs vēlaties spēlēt šeit pirmais elements? Mums nāksies jūs norādīt pie šiem naudas ļaudīm. Tātad, 9, 17, 20, 22, veida 29, un pēc tam 34. Vai mēs zaudējam kādu? Man ir 34. Kur did-- OK, kurš grib būt 34? OK, nāk uz augšu, 34. Nu labi, tas būs labi vērts kulminācija. Kāds ir tavs vārds? AUDITORIJA: Peter. DAVID J. Malan: Peter, nākt uz augšu. Labi, tāpēc šeit ir viss ķekars mezgliem. Katrs no jums, puiši pārstāv viena no šīm taisnstūri. Un Gabe, nedaudz dīvaina cilvēks, kas pārstāv pirmās. Tātad viņa rādītājs ir nedaudz mazāka uz ekrāna, nekā jebkuram citam. Un šajā gadījumā, katram jūsu kreisi rokas gatavojas nu punktu uz leju, tādējādi pārstāv nulle, tāpēc tikai trūkums rādītājs, vai tas būs vērsta pie mezglu blakus jums. Tātad tagad, ja jūs izgreznot paši, piemēram, attēla šeit, iet uz priekšu un punkts otru, ar Gabe jo īpaši norādot uz numurs 9 pārstāvēt sarakstu. OK, un numuru 34, kreiso roku būtu vienkārši norādot uz grīdas. Labi, tāpēc tas ir saistīts saraksts. Tātad šis ir scenārijs jautājumu. Un tiešām, tas tiek uzrādīts par kādu problēmu ka jūs varētu mēģināt atrisināt ar kodu. Jūs vēlaties, lai galu galā ievietot jauns elements iekļaušanu sarakstā. Šajā gadījumā, mēs ejam mēģiniet ievietojot numuru 55. Bet tur būs Dažādos gadījumus izskatīt. Un tiešām, šis būs viens no big-picture takeaways šeit, ir, kādi ir dažādi gadījumi. Kādas ir citāda, ja apstākļi vai zari, ka jūsu programma varētu būt? Nu, numuru jūs mēģināt ievietot, ko mēs tagad zinām, ir 55, bet, ja jūs nezināt iepriekš, es daresay ietilpst vismaz trīs iespējamās situācijas. Kur varētu jauns elements būt? AUDITORIJA: Un beigās vai vidū. DAVID J. Malan: beigās, it vidējā vai sākumā. Tāpēc es varu pieprasīt tur vismaz Trīs problēmas, mums ir nepieciešams, lai atrisinātu. Pieņemsim izvēlēties to, kas ir iespējams varbūt vienkāršākais viens, kur jaunu elementu pieder sākumā. Tāpēc es esmu nāksies kodu diezgan piemēram, meklēt, ko es tikko uzrakstīju. Un es esmu nāksies PTR, kas Es pārstāvēt šeit ar manu pirkstu, kā parasti. Un atcerieties, kāda vērtība vai mēs sāktu PTR to? Tātad mēs inicializēts to null sākotnēji. Bet tad ko gan mēs darām, kad mēs bija iekšā mūsu meklēšanas funkciju? Mēs noteikti tas ir vienāds ar, pirmkārt, kas nenozīmē to izdarīt. Ja es noteikti PTR ir vienāda ar pirmo, ko būtu mana roka tiešām norādot uz? Labi. Tātad, ja Gabe un es gatavojas lai būtu vienādas vērtības šeit mums ir gan stacionārajiem uz numuru 9. Tātad tas bija sākums mūsu stāsts. Un tagad tas ir tikai vienkāršs, kaut sintakse ir jauns. Konceptuāli tas ir tikai lineārs meklēšanu. Ir 55 vienāds ar 9? Vai drīzāk, teiksim mazāk kā 9. Tā kā es cenšos izdomāt, kur likt 55. Mazāks par 9, mazāks par 17, mazāks par 20, mazāks par 22, mazāks par 29, mazāk nekā 34, Nr. Tāpēc tagad mēs esam gadījumā viena no vismaz trīs. Ja es gribu, lai ievietotu 55 pār šeit, kādi līnijas koda nepieciešamību saņemt izpildīts? Kā šo attēlu cilvēkiem ir jāmaina? Ko man darīt ar manu kreiso roku? Tam vajadzētu būt nulle sākotnēji jo Es beigās sarakstā. Un ko vajadzētu notikt šeit ar Pēteri, tas bija? Viņš acīmredzot gatavojas norādīt uz mani. Tāpēc es pretenziju tur ir vismaz divas rindas Koda parauga kodu no šodienas kas notiek, lai to īstenotu scenārijs pievienojot 55 pie astes. Un es varētu būt kāds hop augšu un tikai pārstāv 55? Nu labi, jums ir jaunais 55. Tāpēc tagad, ko tad, ja nākamais scenārijs nāk kopā, , un mēs vēlamies, lai ievietotu tajā sākas vai vadītājs šo sarakstu? Un kāds ir tavs vārds, numuru 55? AUDITORIJA: Jack. DAVID J. Malan: Jack? OK, nice to meet you. Laipni lūdzam uz klāja. Tāpēc tagad mēs ejam ievietot, teiksim, numuru 5. Lūk otrais gadījums Trīs mēs nāca klajā ar pirms tam. Tātad, ja 5 pieder sākumā, pieņemsim redzēt, kā mēs redzam, ka out. Es sāktu manu PTR rādītāju uz numuru 9 vēlreiz. Un es realizēts, oh, 5 ir mazāks par 9. Tātad noteikt šo priekšstatu par mums. Kuru rokas, Gabe ir vai Dāvida or-- kas ir cipars 9 vārds? AUDITORIJA: Jen. DAVID J. Malan: Jen hands-- kas mūsu rokās ir jāmaina? Labi, tāpēc Gabe norāda uz to, ko tagad? Uz mani. Es esmu jaunā mezglu. Tāpēc es ņemšu tikai veida kustībā šeit, lai redzētu to vizuāli. Un tikmēr, ko es varu norādīt, ka? Still, kur es esmu, norādot. Tāpēc, ka tas arī viss. Tik vienkārši tiešām viena līnija koda labojumi šo konkrēto jautājumu, tā varētu likties. Labi, tā, ka ir labi. Un var kāds būt vietturis 5? Nāciet uz augšu. Mēs tev nākamreiz. Visas tiesības, tāpēc now-- un Kā malā, nosaukumi Es neesmu padarot skaidra norāde uz tiesībām Tagad, pred rādītājs, priekštecis rādītājs un jaunu rādītāju, kas ir tikai vārdi dots parauga kodu uz norādes vai manas rokas, kas ir sava veida norādot apkārt. Kāds ir tavs vārds? AUDITORIJA: Christine. DAVID J. Malan: Christine. Laipni lūdzam uz klāja. Labi, tāpēc pieņemsim apsvērt tagad nedaudz vairāk kaitinošas scenārijs, ar kuru es gribu, lai ievietotu kaut kas līdzīgs 26 stāšanās šis. 20? Kas? Tie are-- laba lieta, mēs esam šo pildspalvu. Nu labi, 20. Ja kāds varētu iegūt citu gabals papīrs gatavs, tikai case-- labi. Ak, interesanti. Nu tas ir piemērs par lekciju bug. Labi, lai to, kas ir jūsu vārds atkal? AUDITORIJA: Julia. DAVID J. Malan: Julia, jūs varat pop , un izlikties, tu nekad tur? Labi, tas nekad nav noticis. Paldies. Tātad pieņemsim, ka mēs gribam ievietot Julia šajā saistīts sarakstā. Viņa ir numurs 20. Un, protams, viņa ir gatavojas piederīgs begin-- neliecina par kaut ko vēl. Tātad jūsu rokas var veida būt leju null vai kādu atkritumu vērtību. Pieņemsim pateikt ātri stāstu. Es esmu norādot uz vairākiem 5 šoreiz. Tad es varētu pārbaudīt 9. Tad es varētu pārbaudīt 17. Tad es varētu pārbaudīt 22. Un es saprotu, ooh, Julia ir jāiet pirms 22. Tātad, kas nepieciešams, lai notiktu? Kuru rokās ir jāmaina? Julia s, raktuves, or-- kāds ir tavs vārds atkal? AUDITORIJA: Christian. DAVID J. Malan: Christian vai? AUDITORIJA: Andy. DAVID J. Malan: Andy. Kristiešu vai Andy? Andy ir nepieciešams norādīt uz? Julia. Viss labi. Tātad Andy, jūs vēlaties norādīt uz Julia? Bet pagaidiet minūti. Stāsts līdz šim, Es esmu veida viena atbild, tādā nozīmē, ka rādītājs ir lieta, kas ir pārvietojas pa sarakstu. Mums varētu būt nosaukumu Andy, bet tur nav mainīgo sauc Andy. Tikai citu mainīgais mums ir Pirmais, kurš pārstāv Gabe. Tātad tas ir faktiski tāpēc, tādējādi šim mēs esam nav nepieciešams to. Bet tagad uz ekrāna ir pieminēt atkal no ieteik rādītāju. Tāpēc ļaujiet man būt precīzāk. Ja tas ir rādītājs, man bija labāk iegūt nedaudz vairāk viedo par manu atkārtojuma. Ja jums nav prātā manu iet cauri šeit atkal, norādot šeit, norādot šeit. Bet man ir ieteik rādītāju, priekšgājējs rādītājs, kas ir veida norādot uz elements Man bija tikai pie. Tātad, kad es iet šeit, tagad manu kreiso roku atjauninājumus. Kad es iet šeit manu kreiso roku atjauninājumus. Un tagad man ir ne tikai rādītāju uz elements, kas iet pēc Julia, Man joprojām ir rādītāju uz Andy, elements pirms. Tātad jums ir piekļuve, būtībā, rīvmaizes, ja jūs, visiem nepieciešamās norādes. Tātad, ja es esmu norādot uz Andy, un es esmu arī norādot pie Kristietis, kura rokās tagad būtu jānorāda citur? Tātad Andy tagad var norādīt uz Julia. Julia tagad var norādīt uz kristiešu. Tāpēc, ka viņa var kopēt manu labā roka ir rādītājs. Un tas faktiski liek jums atpakaļ šajā vietā šeit. Tātad īsumā, kaut arī tas sper mūs veida visiem laikiem faktiski atjaunināt saistīta sarakstu, saprotam ka operāciju ir salīdzinoši vienkārši. Tas ir viens, divi, trīs rindas kods galu galā. Bet aptīt tiem koda rindiņas varbūtējs ir mazliet loģikas, kas efektīvi uzdod jautājumu, kur mēs esam? Vai mēs sākumā, vidējā vai gala? Tagad, ir noteikti daži citi operācijas mēs varētu īstenot. Un šīs bildes šeit vienkārši attēlot tas, ko mēs tikko izdarījām ar cilvēkiem. Kas par noņemšanu? Ja es gribu, lai, piemēram, noņemtu numuru 34 vai 55, Es varētu būt tāda paša veida kodu, bet es esmu gatavojas nepieciešama vienu vai divus soļus. Tāpēc, ka to, kas jauns? Ja es izņemt kāds beigās, piemēram numuru 55, un pēc tam 34, , kas ir arī mainīties, jo man darīt? Man ir ne evict-- kāds ir tavs vārds atkal? AUDITORIJA: Jack. DAVID J. Malan: Jack. Man ir ne tikai evict-- bezmaksas Jack, tik burtiski zvanīt bezmaksas Jack, vai vismaz rādītājs arī tur, bet tagad to, kas ir nepieciešams, lai mainītu ar Pēteri? Viņa roka labāk sākt uz leju. Jo, tiklīdz es aicinu bez maksas Jack, ja Pētera joprojām norādot uz Jack un tāpēc es glabāt šķērso sarakstu un piekļuves šis rādītājs, tas ir tad, kad mūsu vecais draugs segmentācija vaina tiešām var kick. Tāpēc, ka esam radījuši atmiņas atpakaļ uz Jack. Jūs varat palikt tur neveikli tikai brīdi. Tāpēc, ka mums ir tikai pāris gala darbības izskatīt. Noņemot galvu saraksta, vai beginning-- un tas viens ir nedaudz kaitinošas. Tāpēc, ka mums ir jāzina, ka Gabe ir sava veida īpašs šajā programmā. Jo tiešām, viņam ir savs rādītājs. Viņš ir ne tikai tiek norādīja, kā gandrīz visi citi šeit. Tātad, ja galva sarakstā noņemts, kura rokās ir nepieciešams mainīt tagad? Kāds ir jūsu vārds atkal? AUDITORIJA: Christine. DAVID J. Malan: Es esmu šausmīgi pie vārdiem, acīmredzot. Tik Christine un Gabe, kuru rokās ir jāmaina kad mēs cenšamies, lai novērstu Christine, numurs 5, no attēla? Labi, tāpēc pieņemsim do Gabe. Gabe dodas uz punktu, domājams, uz numuru 9. Bet ko nākamo vajadzētu notikt? AUDITORIJA: Christine vajadzētu būt null [nedzirdama]. DAVID J. Malan: Labi, mums vajadzētu, iespējams, make-- es dzirdēju "null" kaut kur. AUDITORIJA: Null un bez viņas. DAVID J. Malan: null, ko? AUDITORIJA: Null un bez viņas. DAVID J. Malan: Null un bez viņas. Tāpēc tas ir ļoti viegli. Un tas ir lieliski, ka jūs tagad kārtošanas Stāvvietu tur, nevis piederību. Tāpēc, ka jūs esat bijis atsaistīts no saraksta. Jūs esat efektīvi bijuši bāreņiem no saraksta. Un tā mums bija labāk zvanīt bez tagad Christine dot šo atmiņu atpakaļ. Pretējā gadījumā katru reizi, kad mēs izdzēst mezglu no saraksta mēs varētu padarīt sarakstu īsāks, bet faktiski samazinās lielums atmiņā. Un tāpēc, ja mēs saglabātu pievienojot un piebilstot, pievienojot lietas sarakstā, mans dators varētu saņemt lēnāk un lēnāk un lēnāk, tāpēc, ka es skrienu no atmiņa, pat ja es neesmu faktiski izmantojot Christine s baiti atmiņas vairs. Tātad beigās ir citi scenāriji, no course-- izņemšanas vidū, izvešana gada beigās, kā mēs redzējām. Bet vairāk interesanti Tagad izaicinājums ir būs izskatīt precīzi kāda darbības laiks ir. Tātad, ne tikai jūs varat saglabāt savu papīra gabalus, ja, Gabe, jūs neiebilstat dodot visi stress bumbu. Paldies jums tik daudz, lai mūsu saistīts sarakstam brīvprātīgo šeit, ja varētu. [Aplausi] DAVID J. Malan: Nu labi. Tātad pāris analītiskā jautājumi, tad, ja es varētu. Mēs esam redzējuši šo pierakstu pirms, big O un omega, augšējo robežas un apakšējā robeža uz darbības laiks kādu algoritmu. Tātad, pieņemsim apsvērt tikko pāris jautājumiem. Viens, un mēs teicām to pirms, kas ir skriešanas laiks meklēt sarakstu ziņā lielo O? Kas ir augšējā robeža uz darbību laiks meklējot saistīts saraksts kas īstenots ar mūsu brīvprātīgie šeit? Tas ir liels O n, lineāra. Jo sliktākajā gadījumā, elements, piemēram, 55, mēs varētu būt meklējat varētu būt tur, kur Jack bija, visu veidu beigās. Un diemžēl, atšķirībā no masīva mēs nevaram iegūt iedomātā šoreiz. Pat ja visiem mūsu cilvēkiem bija kārtoti no maziem elementiem, 5, visu ceļu līdz lielākiem elementu, 55, ka parasti laba lieta. Bet ko dara šo pieņēmumu vairs neļauj mums darīt? Mērķauditorija: [dzirdams] DAVID J. Malan: Say atkal? AUDITORIJA: Brīvpiekļuves. DAVID J. Malan: Brīvpiekļuves. Un, savukārt, tas nozīmē, ka mēs varam ne ilgāk izmantot vāja nullēm, intuīciju, un acīmredzamības izmantojot bināro meklēt un sadalīt un iekarot. Jo, pat ja mēs cilvēki varētu acīmredzami redzēt, ka Andy vai kristietis, bija apmēram vidū sarakstā mēs tikai zinām, ka dators nokrejojot sarakstu no paša sākuma. Tātad mēs esam atteikušies, ka brīva piekļuve. Tik liels O n tagad ir augšējā saistošs mūsu meklēšanas laiku. Kas par omega mūsu meklēt? Kāda ir zemākā robeža uz meklēšanu kādu numuru šajā sarakstā? Mērķauditorija: [dzirdams] DAVID J. Malan: Say atkal? AUDITORIJA: One. DAVID J. Malan: One. Tik nemainīgs laiku. Labākajā gadījumā, Christine ir pat pie saraksta sākumā. Un mēs meklējam numurs 5, tāpēc mēs atradām viņu. Tāpēc nav liels darījumu. Bet viņa ir nokļuvis būt saraksta sākumā šajā gadījumā. Ko par kaut ko, piemēram, dzēst? Ko darīt, ja jūs vēlaties izdzēst elementu? Kas ir augšējo robežu un apakšējo robežu gada dzēšot kaut ko no saistīta uzskaitīt? Mērķauditorija: [dzirdams] DAVID J. Malan: Say atkal? AUDITORIJA: n. DAVID J. Malan: n ir patiešām augšējo robežu. Jo sliktākajā gadījumā mēs cenšamies izdzēst Jack, kā mēs tikko izdarīja. Viņš visu ceļu beigās. Ņem mūs uz visiem laikiem, vai n soļi, lai atrastu viņu. Tā ka ir augšējo robežu. Tas ir lineāra, pārliecināts. Un labākajā gadījumā darba laika, vai apakšējās robežas labākajā gadījumā būtu nemainīgs laiks. Jo varbūt mēs cenšamies izdzēst Christine, un mēs tikai iegūt laimīgs viņa sākumā. Tagad jāgaida minūti. Gabe bija arī gada sākumā, un mums bija arī atjaunināt Gabe. Tā, ka bija ne tikai viens solis. Tātad, tas ir patiešām nemainīgs laiks, labākajā gadījumā, noņemt mazāko elementu? Tas ir, lai gan tas varētu būt divas, trīs, vai pat 100 koda rindiņas, ja tas ir tas pats skaits līnijas, nevis dažās cilpa, un neatkarīgi no lieluma saraksta, absolūti. Dzēšot elementu pie saraksta sākumā, pat tad, ja mums ir tikt galā ar Gabe, joprojām ir nemainīgs laika. Tātad tas šķiet masveida solis atpakaļ. Un kāda laika izšķiešana ja nedēļā vienā un nedēļu nulle mums bija ne tikai pseudocode kods bet faktiskais kods ieviest kaut ko, kas ir žurnāla bāze n, vai ielogojieties, drīzāk, no n, bāze 2, attiecībā uz tās darba laika. Tātad, kāpēc heck vēlētos mēs gribam sākt izmantojot kaut ko līdzīgu saistītajā sarakstā? Jā. AUDITORIJA: Tātad jūs varat pievienot elementi masīva. DAVID J. Malan: Tātad jūs varat pievienot elementus uz masīvu. Un tas arī ir tematiska. Un mēs turpināsim redzēt tam, šis kompromiss, daudz kā mēs esam redzējuši kompromiss ar sapludināšanas kārtošanas. Mēs tiešām varētu paātrināt meklēšanu vai šķirošanu, drīzāk, ja mēs tērēt mazliet vairāk vietas un ir papildu rieciens atmiņas vai masīvs sapludināšanas kārtošanas. Bet mēs tērēt vairāk telpa, bet mums ietaupīt laiku. Šajā gadījumā, mēs esam atmest laiku, bet mēs esam iegūt elastību, dinamika, ja jūs, kas ir neapšaubāmi pozitīva iezīme. Mēs arī izdevumu telpu. Kādā jēga ir saistīta uzskaitīt dārgāks izteiksmē vietas nekā masīva? Ja ir papildu telpas nāk no? Yeah? Mērķauditorija: [dzirdams] rādītājs. DAVID J. Malan: Jā, mēs ir arī rādītājs. Tātad šis ir minorly kaitinošas jo vairs esmu Es glabāšanai tikai int pārstāvēt int. Es esmu glabāšanai int un A rādītājs, kas arī ir 32 biti. Tāpēc es esmu burtiski divkāršojies vietas daudzumu iesaistīti. Tātad tas ir kompromiss, bet kas ir gadījumā int. Pieņemsim, ka jūs neesat glabāšanai int, bet pieņemsim, ka katrs no šiem taisnstūriem vai katrs no šiem cilvēkiem tika pārstāv vārds, angļu vārds, kas varētu būt piecas rakstzīmes, 10 rakstzīmes, varbūt pat vairāk. Tam pievienojot tikai 32 vairāk bitu varētu būt mazāk par lielu darījumu. Ko darīt, ja katrs no studentiem demonstrējumu bija burtiski studentu structs ka ir nosaukumi un māju un varbūt tālruņu numurus un Twitter rokturi un tamlīdzīgi. Tātad visi lauki sākām runājot par citu dienu, daudz mazāk par lielu darījumu, kas Mūsu mezglus iegūt vairāk interesantu un liels tērēt, eh, papildu rādītājs tikai lai savienotu tos kopā. Bet tiešām, tas ir kompromiss. Un tiešām, kods ir sarežģītāka, jo jūs skat nokrejojot cauri ka konkrētais piemērs. Bet ko tad, ja tur bija daži Holy Grail šeit. Ko darīt, ja neņemam soli uz aizmuguri, bet masveida solis uz priekšu un īstenot datu struktūra, caur kuru mēs var atrast elementus, piemēram, Jack vai Christine vai kādi citi elementi šajā masīva patiess konstantu laikā? Meklēšana ir nemainīgs. Dzēst ir nemainīgs. Ieliktnis ir nemainīgs. Visas šīs operācijas ir nemainīgi. Tas būs mūsu svētais Grāls. Un tas ir, ja mēs uzņemt nākamreiz. Tiekamies tad.