[MUSIC KUCHEZA] DAVID J. Malan: All wa kulia. Hii ni CS50. Hii ni wiki tano kuendelea, na sisi kuwa na baadhi ya habari njema na baadhi ya habari mbaya. Hivyo habari njema ni kwamba CS50 lanserar Ijumaa hii. Kama ungependa kujiunga na sisi, kichwa na kawaida URL hapa. Habari Hata bora, hakuna hotuba huu kuja Jumatatu ya 13. Kidogo kidogo habari bora, Jaribio zero ni Jumatano ijayo. Maelezo zaidi yanaweza kuwa kupatikana katika URL hii hapa. Na zaidi ya wanandoa siku tutaweza kuwa na kujaza nafasi zilizoachwa wazi kwa upande wa vyumba kwamba sisi kuwa zimehifadhiwa. Bora habari ni kwamba kuna itabidi kuwa mapitio shaka kote kikao hiki kuja Jumatatu jioni. Stay tuned kwa kozi ya tovuti kwa ajili ya eneo na maelezo. Sehemu, hata kama ni likizo, pia kukutana na kama vizuri. Best habari, hotuba Ijumaa ijayo. Hivyo hii ni mila sisi kuwa, kama per mtaala. Just-- ni kwenda kuwa ajabu. Wewe utaona vitu kama miundo data wakati mara kwa mara na meza hash na miti na anajaribu. Na tutaweza majadiliano juu ya matatizo siku ya kuzaliwa. rundo zima ya mambo watapata Ijumaa ijayo. OK. Hata hivyo. Hivyo kukumbuka kuwa sisi tumekuwa kulenga picha hii ya nini ndani ya kumbukumbu ya kompyuta yetu. Hivyo kumbukumbu au RAM ni ambapo programu kuwepo wakati wewe mbio yao. Kama wewe mara mbili-click icon ya kuendesha mpango baadhi au mara mbili-click icon kufungua baadhi ya faili, ni kubeba kutoka ngumu yako kuendesha gari au gari hali imara ndani ya RAM, Random Access Memory, ambapo ni maisha mpaka nguvu huenda mbali, mfuniko mbali kufunga, au wewe kuacha mpango. 

Sasa kwa kuwa kumbukumbu, ya ambayo pengine 1 gigabyte siku hizi, 2 gigabytes, au hata zaidi, kwa ujumla kuweka nje kwa mpango wa kupewa katika aina hii ya rectangular mtindo wa dhana ambapo tuna stack chini na rundo la mambo mengine kwa juu. Jambo saa ya juu sana tumeona juu ya picha hii lakini kamwe kabla ya kuongelea ni kinachojulikana Nakala sehemu. Nakala sehemu ni njia tu dhana ya kusema zeros na wale ambao kutunga halisi compiled mpango wako. 

Hivyo wakati wewe mara mbili-click Microsoft Word juu ya Mac au PC yako, au wakati wewe kukimbia dot kufyeka Mario juu ya Linux kompyuta katika terminal dirisha yako, zeros na wale ambao kutunga Neno au Mario ni kuhifadhiwa kwa muda katika RAM ya kompyuta yako katika kinachojulikana Nakala sehemu kwa ajili ya mpango fulani. Chini kwamba huenda initialized na data uninitialized. Hii ni mambo kama vigezo kimataifa, kwamba tumekuwa si kutumika wengi wa, lakini juu ya tukio tumekuwa alikuwa vigezo kimataifa au statically defined masharti kwamba ni ngumu coded maneno kama "hello" ambayo si kuchukuliwa katika kutoka kwa mtumiaji kuwa ni ngumu-coded katika mpango wako. 

Sasa, chini chini sisi na kinachojulikana stack. Na stack, hivi sasa, tumekuwa kutumia kwa ajili ya aina gani ya makusudi? Nini stack zimetumika kwa ajili ya? Yeah? 

Watazamaji: Kazi. 

DAVID J. Malan: Kwa kazi? Ni katika maana gani kwa ajili ya kazi? 

Watazamaji: Wakati wewe piga kazi, hoja ni kunakiliwa kwenye stack. 

DAVID J. Malan: Hasa. Wakati wewe piga kazi, yake hoja ni kunakiliwa kwenye stack. Hivyo X yoyote au Y au A au B ya kwamba wewe ni kupita katika kazi ni muda kuweka juu ya kinachojulikana stack, tu kama moja ya Annenberg dining trays ukumbi, na pia mambo kama vigezo mitaa. Kama foo kazi yako au byta yako kazi kuwa na vigezo mitaa, kama temp, wale wawili kuishia juu ya stack. Sasa, sisi si kuzungumza sana kuhusu yao, lakini vigezo hivi mazingira chini tuliona wakati iliyopita wakati Mimi nilikuwa futzing katika keyboard siku moja na mimi kuanza kupata mambo kama argv 100 au argv 1000, tu elements-- mimi kusahau numbers-- lakini kwamba walikuwa si walidhani kuwa kupatikana kwa mimi. Sisi kuanza kuona baadhi alama funky juu ya screen. Wale walikuwa kinachojulikana mazingira vigezo kama mipangilio ya kwa ajili yangu mpango au kwa kompyuta yangu, si lisilohusiana na ya hivi karibuni mdudu kwamba sisi kujadiliwa, Shellshock, kwamba imekuwa inayolikabili kompyuta chache kabisa. 

Sasa mwisho, katika mtazamo wa leo tutaweza hatimaye kuwa juu ya lundo. Hii ni chunk nyingine ya kumbukumbu. Na kimsingi yote haya kumbukumbu ni mambo sawa. Ni vifaa hivyo. Sisi ni tu aina ya kutibu nguzo mbalimbali ya ka kwa malengo tofauti. chungu pia ni kwenda kuwa ambapo vigezo na kumbukumbu kwamba wewe ombi kutoka mfumo wa uendeshaji ni muda kuhifadhiwa. 

Lakini kuna aina ya tatizo hapa, kama picha ina maana. Sisi aina ya wawili meli juu ya collide. Kwa sababu kama wewe kutumia zaidi na zaidi ya stack, na kama sisi kuona leo kuendelea, kama wewe kutumia zaidi na zaidi ya chungu, hakika mambo mabaya yanaweza kutokea. Na hakika, sisi inaweza kutumika kwamba makusudi au bila kukusudia. Hivyo cliffhanger mwisho huo ilikuwa mpango huu, ambao hawakuwa kumtumikia yoyote kazi kusudi wengine kuliko kuonyesha jinsi kama guy mbaya inaweza kweli kuchukua faida ya mende katika mpango wa mtu na kuchukua juu ya mpango au hata zima mfumo wa kompyuta au server. Hivyo tu kwa mtazamo kwa ufupi, wewe taarifa kwamba kuu chini inachukua katika mstari amri hoja, kama per argv. Na ina mwito wa kazi f, kimsingi kazi Nameless kuitwa f, na ni kupita katika argv [1]. 

Kwa hiyo chochote neno aina user katika saa haraka baada ya jina mpango huu, na kisha kazi hii holela up juu, f, inachukua katika kamba, AKA * Char, kama tumeanza kujadili, na ni haki anaiita "bar." Lakini tunaweza kuiita kitu chochote. Na kisha anatangaza, ndani ya ya f, safu ya wahusika kuitwa c-- 12 wahusika kama. 

Sasa, kwa hadithi mimi alikuwa akiwaambia wakati iliyopita, ambapo katika kumbukumbu ni c, au ni wale 12 chars kwenda kuishia? Tu kuwa wazi. Yeah? 

Watazamaji: On stack. 

DAVID J. Malan: On stack. Hivyo c ni variable mitaa. Tunawaomba kwa chars 12 au ka 12. Wale ni kwenda kuishia juu ya kile kinachoitwa stack. Sasa hatimaye ni kazi hii nyingine hiyo ni kweli pretty muhimu, lakini tumekuwa si kweli kutumika wenyewe, strncopy. Ina maana string nakala, lakini tu n barua, n wahusika. Hivyo wahusika n itakuwa kunakiliwa kutoka bar ndani ya c. Na jinsi wengi? urefu wa bar. Hivyo kwa maneno mengine, kwamba mstari mmoja, strncopy, ni kwenda nakala ufanisi bar katika kwa c. 

Sasa, tu aina ya wanatarajia maadili ya hadithi hii, nini ni uwezekano wa matatizo hapa? Hata ingawa sisi ni kuangalia urefu ya bar na kupita katika strncopy, kile gut wako akikuambia ni bado kuvunjwa kuhusu mpango huu? Yeah? 

Watazamaji: Je, si ni pamoja na chumba for null tabia. DAVID J. Malan: Je, si ni pamoja na chumba for null tabia. Uwezekano, tofauti na katika mitindo ya kizamani sisi kufanya hata kuwa na kiasi kama plus 1 kwa malazi kwamba null tabia. Lakini ni mbaya zaidi kuliko hiyo. Nini kingine ni sisi kushindwa kufanya? Yeah? 

Watazamaji: [inaudible] DAVID J. Malan: Perfect. Tumekuwa ngumu coded 12 pretty kiholela. Hiyo ni si sana tatizo, lakini ukweli kwamba sisi siyo hata kuangalia kama urefu wa bar ni chini ya 12, katika kesi ambayo ni kwenda kuwa salama ya kuweka ndani ya kumbukumbu kuitwa c kwamba tumekuwa zilizotengwa. Hakika, kama bar ni kama Wahusika 20 kwa muda mrefu, kazi hii inaonekana kuwa kuiga Wahusika 20 kutoka bar ndani ya c, na hivyo kuchukua angalau 8 ka kwamba ni lazima kuwa. Hiyo ni maana hapa. 

Hivyo katika muda mfupi, kuvunjwa mpango. Si kama mpango kubwa. Labda wewe kupata kosa segmentation. Tumekuwa wote walikuwa na mende katika programu. Sisi wote wapate kuwa na mende katika programu hivi sasa. Lakini nini maana? Naam, hapa ni zoomed-katika toleo la picha ya kumbukumbu ya kompyuta yangu. Hii ni chini ya stack yangu. Na hakika, chini sana ni nini kuitwa mzazi wa mara kwa mara stack, dhana njia ya kusema kwamba kuu. Ili kila mtu aitwaye kazi f kwamba sisi ni kuzungumza juu. Hivyo hii ni chini ya stack. Return anwani ni kitu kipya. Ni daima imekuwa pale, daima imekuwa katika picha hiyo. Sisi tu kamwe kuitwa tahadhari hiyo. Kwa sababu ni zamu nje ya njia c kazi ni kwamba wakati kazi moja wito mwingine, si tu kufanya hoja ya kwamba kazi kupata kusukuma kwenye stack, si tu kufanya kazi ya ndani vigezo kupata kusukuma kwenye stack, kitu kinachoitwa anwani kurudi pia anapata kuweka kwenye stack. Hasa, kama wito kuu foo, ya kuu mwenyewe anwani katika kumbukumbu, ng'ombe kitu, ufanisi anapata kuweka kwenye stack hivyo kwamba wakati f ni kosa utekelezaji yake anajua wapi kuruka nyuma katika maandishi sehemu ili kuendelea utekelezaji. 

Hivyo kama tuko hapa conceptually, katika kuu, basi f anapata kuitwa. Jinsi gani f kujua ni nani kwa mkono kudhibiti nyuma? Naam, hii kidogo breadcrumb katika nyekundu hapa, kuitwa anwani kurudi, ni tu hundi, nini ni kwamba kurudi anwani? Oh, napenda kuruka nyuma kwa kuu hapa. Na kwamba ni kidogo ya kurahisisha, kwa sababu zeros na ndio kwa kuu ni kitaalam up hapa katika sehemu tech. Lakini hiyo ni wazo. f tu ana kujua nini ambapo kudhibiti hatimaye inakwenda nyuma. 

Lakini kompyuta njia kwa muda mrefu kuweka nje mambo kama vigezo mitaa na hoja ni kama hii. Hivyo katika juu ya picha hii katika bluu ni stack frame kwa f, hivyo wote ya kumbukumbu kwamba f hasa ni kutumia. Hivyo ipasavyo, taarifa kwamba bar ni katika picha hii. Bar ilikuwa hoja yake. Na sisi alidai kuwa hoja ya kazi kupata kusukuma kwenye stack. Na c, bila shaka, ni pia katika picha hii. 

Na tu kwa madhumuni ya notational, taarifa juu upande wa kushoto kona ni nini itakuwa c bracket 0 na kisha chini kidogo na haki ni c bracket 11. Hivyo kwa maneno mengine, unaweza kufikiria kwamba kuna gridi ya taifa ya ka kuna ya kwanza ambayo ni juu kushoto, chini ya ambayo ni mwisho wa wale ka 12. 

Lakini sasa kujaribu kufunga mbele. Nini ni kuhusu kutokea kama sisi kupita katika kamba bar hiyo ni muda mrefu zaidi ya c? Na sisi ni si kuangalia kama ni kweli kwa muda mrefu kuliko 12. Ambayo ni sehemu ya picha hii ni kwenda kupata overwritten na ka 0, 1, 2, 3, dot dot dot, 11, na kisha mbaya, 12, 13 kupitia 19? Nini kinaendelea kutokea hapa, kama wewe infer kutoka kuagiza kwamba c bracket 0 ni juu na c bracket 11 ni aina ya chini upande wa kulia? Yeah? 

Watazamaji: Naam, ni kwenda overwrite * Char bar. 

DAVID J. Malan: Yeah, inaonekana kama wewe ni kwenda overwrite * Char bar. Na mbaya zaidi, kama kutuma katika kweli kwa muda mrefu kamba, unaweza hata overwrite nini? anwani kurudi. Ambayo tena, ni tu kama breadcrumb kwa kuwaambia mpango ambapo kwenda nyuma wakati f ni kosa kuitwa. 

Hivyo kile wabaya kawaida ya kufanya ni kama wao kuja hela mpango kwamba wao ni curious kama ni exploitable, buggy kwa namna kwamba yeye au yeye anaweza kuchukua faida ya kwamba mdudu, kwa ujumla hawana kupata haki hii mara ya kwanza. Wao tu kuanza kutuma, kwa mfano, masharti random katika mpango wako, iwe katika keyboard, au kusema ukweli wao pengine kuandika mpango kidogo tu moja kwa moja kuzalisha masharti, na kuanza banging juu ya mpango wako na kutuma katika kura ya pembejeo mbalimbali katika urefu tofauti. 

Haraka kama shambulio mpango wako, hiyo ni jambo la kushangaza. Kwa sababu ina maana yeye au yeye ana aligundua nini pengine ni kweli mdudu. Na kisha wanaweza kupata zaidi wajanja na kuanza kuelekeza nguvu zaidi narrowly juu ya jinsi ya kutumia kwamba mdudu. Hasa, nini yeye au anaweza kufanya ni kutuma, katika kesi bora, hello. Hakuna mpango kubwa. Ni string kwamba ni kutosha short. Lakini nini kama yeye au yeye zituma, na tutaweza kujumlisha ni kama, mashambulizi code-- hivyo zeros na wale ambao kufanya mambo kama rm-rf, kwamba kuondoa kila kitu kutoka gari ngumu au kutuma spam au kwa namna fulani kushambulia mashine? 

Hivyo kama kila moja ya haya barua A tu inawakilisha, conceptually, mashambulizi, mashambulizi, mashambulizi, mashambulizi, baadhi ya kanuni mbaya kwamba mtu mwingine aliandika, lakini iwapo mtu huyo ni smart kutosha kwa si tu ni pamoja na kila ya wale rm-RFS, lakini pia na ka yake michache iliyopita kuwa idadi hiyo sambamba kwa anwani ya yake au mashambulizi yake mwenyewe code kwamba yeye au yeye kupita katika tu kwa kutoa hiyo kwa haraka, unaweza ufanisi hila kompyuta ndani ya noticing wakati f ni kosa utekelezaji, oh, ni wakati kwa ajili yangu kuruka nyuma nyekundu kurudi mahali. Lakini kwa sababu yeye au yeye ana namna fulani walipishana kwamba kurudi anwani na idadi yao wenyewe, na wao uko smart kutosha kwa uliyoisanidi kwamba idadi ya rejea, kama wewe kuona katika top super mkono wa kushoto kona kuna, anwani halisi katika kompyuta kumbukumbu ya baadhi ya mashambulizi kanuni zao, guy mbaya inaweza hila kompyuta ndani ya utekelezaji code yake mwenyewe. 

Na kwamba kanuni, tena, inaweza kuwa kitu chochote. Ni kwa ujumla aitwaye shell code, ambayo ni tu njia ya kusema kwamba siyo kwa ujumla kitu rahisi kama rm-rf. Ni kweli kitu kama Bash, au mpango halisi kwamba inampa au kudhibiti yake programu kutekeleza kitu kingine chochote kwamba wanataka. Hivyo katika muda mfupi, hii yote inatokana na ukweli rahisi kwamba hii mdudu kushiriki si kuangalia mipaka ya safu yako. Na kwa sababu njia kompyuta kazi ni kwamba wao kutumia stack kutoka ufanisi, conceptually, chini juu juu, lakini basi mambo kushinikiza kwenye stack kukua juu chini, hii ni incredibly tatizo. Sasa, kuna njia ya kufanya kazi ya kuzunguka hili. Na kusema ukweli, kuna lugha na ambayo kwa kazi ya kuzunguka hili. Java ni kinga, kwa mfano, kwa hasa katika suala hili. Kwa sababu hawana kuwapa kuyatumia. Hawana kukupa kumbukumbu anwani moja kwa moja. Hivyo kwa nguvu hii kwamba tuna kwa kugusa kitu chochote katika kumbukumbu sisi wanataka kuja, admittedly, hatari kubwa. 

Hivyo kuweka jicho nje. Kama, kusema ukweli, katika kipindi cha miezi au miaka ijayo, wakati wowote wewe kusoma kuhusu baadhi unyonyaji ya mpango au server, kama wewe milele kuona ladha ya kitu kama mashambulizi buffer kufurika, au stack kufurika ni aina nyingine ya mashambulizi, sawa katika roho, vile kuwahamasisha tovuti ya jina, kama wewe kujua, ni wote kuzungumza juu ya tu wingi na ukubwa wa baadhi ya tabia safu au safu baadhi zaidi kwa ujumla. Maswali yoyote, basi, juu ya hili? Je, si kujaribu hili nyumbani. 

Wote haki. Hivyo malloc hivi sasa imekuwa wetu mpya rafiki katika kwamba tunaweza kutenga kumbukumbu kwamba hatuna lazima kujua katika mapema kwamba tunataka hivyo hatuna na kanuni ngumu katika yetu namba mpango kama 12. Mara baada ya user anatueleza jinsi gani data yeye au yeye anataka kwa pembejeo, tunaweza malloc kumbukumbu kwamba mengi. 

Hivyo malloc ni zamu nje, kwa kiwango tumekuwa kutumia hiyo, wazi mara ya mwisho, na kisha nyie wamekuwa kutumia kwa GetString kutojua kwa wiki kadhaa, yote ya kumbukumbu malloc ya linatokana na kinachojulikana chungu. Na hii ni kwa nini GetString, kwa mfano, unaweza kutenga kumbukumbu dynamically bila kujua nini wewe ni kwenda aina mapema, mkono wewe nyuma pointer kwa kuwa kumbukumbu, na kwamba kumbukumbu ni bado yako ya kutunza, hata baada ya GetString anarudi. Kwa sababu kukumbuka baada ya yote stack ni mara kwa mara kwenda juu na chini, juu na chini. Na kama hivi karibuni kama unaendelea chini, hiyo ina maana yoyote kumbukumbu kazi hii kutumika lazima si kutumiwa na mtu mwingine yeyote. Ni maadili takataka sasa. 

Lakini chungu ni up hapa. Na nini ni nzuri kuhusu malloc ni kwamba wakati malloc kutenga kumbukumbu hadi hapa, ni si wanashikiliwa, kwa sehemu kubwa, na stack. Na hivyo kazi yoyote wanaweza kupata kumbukumbu ambayo imekuwa malloc'd, hata kwa kazi kama GetString, hata baada ya kurudi huko. 

Sasa, kinyume cha malloc ni bure. Na hakika, utawala wewe haja ya kuanza kupitisha ni yoyote, yoyote, wakati wowote wewe kutumia malloc lazima wewe mwenyewe kutumia bure, hatimaye, juu ya kwamba pointer huo. Muda wote huu tumekuwa kuandika buggy, buggy code, kwa sababu nyingi. Lakini moja ya ambayo imekuwa kutumia maktaba CS50, ambayo yenyewe ni kwa makusudi buggy, ni uvujaji kumbukumbu. Wakati wowote umetumia GetString katika wiki chache zilizopita sisi ni kuuliza uendeshaji mfumo, Linux, kwa ajili ya kumbukumbu. Na una kamwe mara moja kutokana na nyuma. Na hii si, katika mazoezi, jambo zuri. 

Na Valgrind, mmoja wa zana ilianzisha katika pset 4, ni wote kuhusu kusaidia sasa kupata mende kama hiyo. Bali nashiriki kwa pset 4 huna haja ya kutumia maktaba CS50 au GetString. Hivyo mende yoyote kuhusiana na kumbukumbu ni hatimaye kwenda kuwa yako mwenyewe. 

Hivyo malloc ni zaidi ya rahisi kwa ajili ya lengo hili. Tunaweza kweli sasa kutatua matatizo kimsingi tofauti, na kimsingi kutatua matatizo zaidi ufanisi kama kwa wiki zero ya ahadi. Hivi sasa hii ni sexiest muundo data tumekuwa alikuwa. Na kwa muundo data I just maana njia ya kufafanua kumbukumbu kwa njia ambayo inakwenda zaidi ya kusema tu, hii ni int, hii ni char. Tunaweza kuanza nguzo mambo pamoja. 

Hivyo safu inaonekana kama hii. Na nini ilikuwa muhimu katika kuhusu safu ni kwamba anatoa wewe nyuma-ya-nyuma chunks ya kumbukumbu, ambayo kila mmoja ni kwenda kuwa ya aina moja, int, int, int, int, au char, char, char, char. Lakini kuna downsides wachache. Hii kwa mfano, ni safu ya ukubwa sita. Tuseme wewe kujaza safu hii na sita namba na kisha, kwa sababu yoyote, user yako anataka kuwapa wewe idadi ya saba. Ambapo gani unaweza kuweka it? 

Nini suluhisho kama una kuundwa safu juu ya stack, kwa mfano, tu na wiki mbili nukuu kwamba sisi kuletwa, ya mabano mraba na idadi ndani? Naam, nimepata sita idadi katika masanduku hayo. Gani hisia zako kuwa? Ambapo unataka kuiweka? 

Watazamaji: [inaudible] 

DAVID J. Malan: Sorry? 

Watazamaji: Weka ya mwisho. 

DAVID J. Malan: Weka ya mwisho. Hivyo tu juu ya upande wa kulia, nje ya boksi hii. Ambayo itakuwa nzuri, lakini anarudi nje huwezi kufanya hivyo. Kwa sababu kama umefanya si aliuliza kwa chunk hii ya kumbukumbu, inaweza kuwa kwa bahati mbaya kwamba hii ni kutumiwa na baadhi variable nyingine kabisa. Fikiria nyuma wiki au hivyo wakati sisi kuweka nje Zamyla na Davin na Gabe ya majina katika kumbukumbu. Walikuwa literally nyuma kwa nyuma kwa nyuma. Hivyo tunaweza si lazima imani kwamba kila ya zaidi ya hapa ni inapatikana kwa ajili yangu kutumia. 

Hivyo kile kingine inaweza kufanya nini? Naam, mara moja kutambua wewe haja safu ya ukubwa saba, unaweza kujenga tu safu ya ukubwa saba kisha kutumia a kwa kitanzi au kitanzi wakati, nakala yake katika safu mpya, na kisha kwa namna fulani tu kujikwamua safu hii au tu kuacha kutumia hiyo. Lakini si kwamba hasa ufanisi. Kwa kifupi, arrays si basi wewe dynamically resize. 

Hivyo kwa upande mmoja, kupata upatikanaji random, ambayo ni ya ajabu. Kwa sababu unatuwezesha kufanya mambo kama kugawanya na kushinda, search binary, ambayo yote tumekuwa aliyesema kuhusu juu ya screen hapa. Lakini wewe mwenyewe rangi katika kona. Haraka kama wewe hit mwisho wa safu yako, una kufanya sana operesheni ghali au kuandika rundo zima la code kwa sasa kukabiliana na tatizo hilo. 

Basi nini kama badala tulikuwa kitu kinachoitwa orodha, au wanaohusishwa orodha hasa? Nini kama badala ya kuwa rectangles nyuma kwa nyuma kwa nyuma, tuna rectangles kwamba kuondoka kidogo kidogo ya wiggle chumba katika kati yao? Na hata kama nimekuwa inayotolewa hii picha au ilichukuliwa picha hii kutoka kwa mmoja wa maandiko hapa kuwa nyuma ya nyuma kwa nyuma utaratibu sana, katika hali halisi, moja ya rectangles wale inaweza kuwa hapa up katika kumbukumbu. Mmoja wao inaweza kuwa juu hapa. Mmoja wao inaweza kuwa juu hapa, zaidi ya hapa, na kadhalika. 

Lakini nini kama sisi akauchomoa, katika kesi hii, mishale kwamba kwa namna fulani kuhusisha haya mistatili pamoja? Hakika, tumeona kiufundi mwili wa mshale. Nini sisi kutumika katika hivi karibuni siku hiyo, chini ya Hood, ni mwakilishi wa arrow? pointer, haki? 

Basi nini kama, badala ya tu kuhifadhi namba, kama 9, 17, 22, 26, 34, nini kama sisi kuhifadhiwa si tu idadi lakini pointer karibu na kila idadi kama hiyo? Hivyo kwamba kiasi kama ungependa thread sindano kwa njia ya rundo zima la kitambaa, mambo kwa namna fulani tying pamoja, vile vile unaweza sisi na kuyatumia, kama incarnated kwa mishale hapa, aina ya weave pamoja rectangles haya ya mtu binafsi kwa kutumia vyema pointer karibu na kila idadi hiyo anazungumzia baadhi ya idadi ya pili yake, anazungumzia, kwa upande wake, baadhi ya idadi ijayo? Hivyo kwa maneno mengine, nini kama sisi kweli alitaka kutekeleza kitu kama hii? Naam kwa bahati mbaya, mistatili haya, angalau moja na 9, 17, 22, na kadhalika, haya ni tena mraba nzuri na namba moja. chini, mstatili chini 9, kwa mfano, inawakilisha kile lazima kuwa pointer, 32 bits. Sasa, mimi nina bado na ufahamu wa aina yoyote data katika C kwamba anatoa si tu int lakini pointer kabisa. 

Basi nini ufumbuzi kama tunataka mzulia jibu yetu wenyewe na hii? Yeah? 

Watazamaji: [inaudible] 

DAVID J. Malan: Nini hiyo? 

Watazamaji: muundo mpya. 

DAVID J. Malan: Yeah, hivyo kwa nini si sisi kujenga muundo mpya, au katika C, struct? Tumeona structs kabla ya, kama kwa ufupi, ambapo sisi kushughulikiwa na muundo mwanafunzi kama huyo, ambaye alikuwa jina na nyumba. Katika pset 3 kuzuka unaweza kutumika zima rundo la structs-- GRect na GOvals kwamba Stanford kuundwa kwa habari nguzo ya pamoja. Basi nini kama sisi kuchukua wazo hili hili la maneno "typedef" na "struct," na kisha baadhi mwanafunzi maalum stuff, na kufuka hii katika yafuatayo: typedef struct nodi node-- na ni tu generic sana sayansi ya kompyuta mrefu kwa ajili ya kitu katika muundo data, chombo katika muundo data. node mimi kudai ni kwenda kuwa na int n, kabisa moja kwa moja, na kisha kidogo zaidi isiyoeleweka kirahisi, line hii ya pili, struct nodi * ijayo. Lakini katika suala chini ya kiufundi, ni nini kwamba mstari wa pili wa kanuni ndani ya braces curly? Yeah? 

Watazamaji: [inaudible] DAVID J. Malan: A pointer nodi nyingine. Hivyo admittedly, syntax kidogo cryptic. Lakini kama wewe kusoma literally, pili ni jina la kutofautiana. Ni aina yake data nini? Ni verbose kidogo wakati huu, lakini ni ya aina struct nodi *. Wakati wowote tumeona kitu nyota, kwamba ina maana ni pointer kwa ajili ya aina kwamba data. Hivyo ijayo ni inaonekana pointer kwa struct nodi. 

Sasa, ni nini struct nodi? Naam, taarifa yenu kuona wale maneno yale yale katika haki juu. Na hakika, wewe pia kuona neno "Node" chini hapa chini kushoto. Na hii ni kweli tu urahisi. Taarifa kwamba katika yetu mwanafunzi ufafanuzi kuna neno "mwanafunzi" mara moja tu. Na hiyo ni kwa sababu mwanafunzi hicho kilikuwa ni si binafsi rejea. Kuna kitu ndani ya mwanafunzi kwamba mahitaji kwa uhakika na mwanafunzi mwingine, persay. Hiyo itakuwa aina ya weird katika ulimwengu wa kweli. 

Lakini pamoja na node katika wanaohusishwa orodha, sisi kufanya unataka node kuwa rejea kwa sawa kitu. Na hivyo taarifa ya mabadiliko ya hapa ni si tu nini ndani braces curly. Lakini sisi kuongeza neno "node" saa ya juu kama vizuri kama akiongeza kuwa chini badala ya "mwanafunzi." Na hii ni tu kina ya kiufundi hivyo tena kuwa, muundo yako data inaweza kuwa self-rejea, ili node unaweza kumweka kwa node mwingine vile. 

Hivyo ni nini hii hatimaye kwenda maana kwa ajili yetu? Naam, moja, mambo haya ndani ya ni yaliyomo ya node yetu. Jambo hili hapa juu, haki ya juu, ni hivyo tu tena kuwa, tunaweza kutaja wenyewe. Na kisha mambo yttersta, ingawa node ni mpya mrefu, labda, bado huo kama mwanafunzi na kile Ilikuwa chini ya Hood katika SPL. 

Hivyo kama sisi sasa alitaka kuanza utekelezaji wa orodha hii wanaohusishwa, jinsi gani sisi kutafsiri kitu kama hii na kanuni? Naam, hebu tu kuona mfano wa mpango huo kwa kweli matumizi ya orodha wanaohusishwa. Miongoni mwa leo usambazaji code ni programu inayoitwa Orodha ya Zero. Na kama mimi kukimbia hii mimi umba super GUI rahisi, Graphical User Interface, lakini ni kweli tu printf. Na sasa nimepata kutokana na mwenyewe menu chache options-- Futa, Insert, Search, na Traverse. Na kuacha. Hizi ni shughuli ya kawaida tu juu ya muundo data inayojulikana kama orodha ya kiungo. 

Sasa, Futa ni kwenda kufuta idadi kutoka kwenye orodha. Insert kwenda kuongeza idadi ya orodha. Search ni kwenda kuangalia kwa idadi katika orodha. Na traverse ni njia tu dhana ya kusema, kutembea kwa njia ya orodha, magazeti ya nje, lakini hiyo ni yake. Je, si mabadiliko hayo kwa njia yoyote. 

Basi hebu jaribu hii. Hebu kwenda mbele na aina 2. Na kisha mimi nina kwenda kuingiza simu, kusema 9. Kuingia. Na sasa mpango wangu ni tu iliyowekwa kusema, orodha ni sasa 9. Sasa, kama mimi kwenda mbele na je Ingiza tena, basi mimi kwenda mbele na zoom nje na aina katika 17. Sasa orodha yangu ni 9, kisha 17. Kama mimi kufanya kuingiza tena, hebu ruka moja. Badala ya 22, kama per picha tumekuwa wamekuwa kuangalia hapa, napenda kuruka mbele na kuingiza 26 ijayo. Hivyo mimi nina kwenda aina 26. orodha ni kama mimi kutarajia. Lakini sasa, tu kuona kama kanuni hii ni kwenda kuwa rahisi, napenda sasa aina 22, ambayo angalau conceptually, kama sisi ni kushika hii namna, ambayo ni kweli kwenda kuwa lengo lingine sasa hivi, anatakiwa kwenda katika kati ya 17 na 26. Hivyo mimi hit Enter. Hakika, kwamba kazi. Na hivyo sasa napenda kuingiza mwisho, kwa picha, 34. 

Wote haki. Hivyo kwa sasa napenda inasema kuwa Kufuta na Traverse na Tafuta kufanya, kwa kweli, kazi. Kwa kweli, kama mimi kufanya kukimbia Search, hebu kutafuta namba 22, kuingia. Ni kupatikana 22. Hivyo kwamba ni nini hii mpango Orodha ya Zero gani. 

Lakini nini ni kweli kwenda juu ya kwamba zana hii? Naam, kwanza nipate kuwa, na kwa kweli Mimi kuwa, faili inayoitwa list0.h. Na mahali fulani katika kuna hii line, typedef, struct nodi, basi nina braces yangu curly, int n, na kisha struct-- nini ilikuwa ufafanuzi? Struct nodi ijayo. Hivyo tunahitaji nyota. Sasa kitaalam sisi kupata katika tabia ya kuchora hapa. Unaweza kuona vitabu vya kiada na marejeo online kufanya hivyo huko. Ni functionally sawa. Kwa kweli, hii ni kidogo zaidi ya kawaida. Lakini mimi itabidi kuwa thabiti na kile sisi alifanya mara ya mwisho na kufanya hili. Na kisha mwisho, mimi nina kwenda kufanya hivyo. 

Hivyo katika header ya faili mahali fulani, katika list0.h leo ni hii ufafanuzi struct, na labda baadhi ya mambo mengine. Wakati huo huo katika list0c kuna kwenda kuwa mambo kadhaa. Lakini sisi ni kwenda tu kuanza na si kumaliza hii. List0.h ni faili nataka ni pamoja na katika wangu C file. Na kisha wakati fulani mimi nina kwenda na int, kuu, utupu. Na kisha mimi nina kwenda na baadhi ya-do hapa. Mimi pia kwenda na mfano, kama batili, search, int, n, kusudi lake katika maisha ni kutafuta kipengele. Na kisha chini hapa mimi kudai katika code ya leo, batili, search, int, n, hakuna semicolon lakini wazi braces curly. Na sasa mimi nataka namna fulani kutafuta kwa kipengele katika orodha hii. Lakini hatuna kutosha habari juu ya screen bado. Nina si kweli kuwakilishwa orodha yenyewe. Hivyo njia moja tunaweza kutekeleza orodha wanaohusishwa katika mpango ni mimi aina ya kutaka kufanya kitu kama kutangaza wanaohusishwa orodha hapa. Kwa unyenyekevu, mimi nina kwenda kufanya hii ya kimataifa, ingawa kwa ujumla sisi haipaswi kufanya hii sana. Lakini itakuwa kurahisisha mfano huu. Hivyo nataka kutangaza orodha wanaohusishwa hapa. Sasa, jinsi gani mimi kufanya hivyo? 

Hapa ni picha ya orodha wanaohusishwa. Na mimi si kweli kujua wakati jinsi Mimi nina kwenda juu anayewakilisha mambo mengi na moja tu variable katika kumbukumbu. Lakini kufikiri nyuma sasa. Muda wote huu tulikuwa na masharti, ambayo sisi basi umebaini kuwa arrays ya wahusika, ambayo sisi kisha umebaini kuwa tu pointer kwa tabia ya kwanza katika safu ya wahusika hiyo null terminated. Hivyo kwa mantiki hiyo, na kwa hili picha aina ya mbegu mawazo yenu, nini haja ya sisi kweli kuandika katika yetu code kwa kuwakilisha orodha wanaohusishwa? Ni kiasi gani cha habari hii tunahitaji kukamata katika C code, ungeweza kusema? Yeah? 

Watazamaji: Tunahitaji pointer nodi. DAVID J. Malan: pointer nodi. Hasa, ambayo node ingekuwa yako hisia kuwa kuweka pointer kwa? 

Watazamaji: node kwanza. 

DAVID J. Malan: Yeah, pengine tu kwanza. Na taarifa, kwanza node ni sura tofauti. Ni tu nusu ya ukubwa wa struct, kwa sababu ni kweli tu pointer. Basi nini unaweza kweli kufanya ni kutangaza orodha wanaohusishwa na kuwa ya aina nodi *. Na hebu tu kuiita kwanza na initialize kwa null. Hivyo null, tena, ni kuja katika picha hapa. Si tu ni null kutumika kama kama maalum thamani ya kurudi kwa mambo kama GetString na malloc, null ni pia zero pointer, ukosefu wa pointer, kama wewe. Ni tu ina maana hakuna kitu bado hapa. Sasa kwanza, mimi naweza wameweza kuitwa kitu huu. Mimi naweza kuwa na kuitwa kuwa ni "orodha" au idadi yoyote ya mambo mengine. Lakini nina wito ni "kwanza" ili hayo yanaendana na picha hii. Hivyo tu kama kamba inaweza kuwakilishwa na anwani ya Byte wake wa kwanza, hivyo unaweza orodha wanaohusishwa. Na tutaweza kuona data nyingine miundo kuwa kuwakilishwa na pointer moja tu, 32-bit mshale, akizungumzia nodi kwanza sana katika muundo. 

Lakini sasa hebu wanatarajia tatizo. Kama mimi nina tu kukumbuka katika mpango wangu anwani ya nodi ya kwanza, kwanza Mstatili katika muundo huu data, nini alikuwa bora kuwa kesi kuhusu utekelezaji wa mapumziko ya orodha yangu? Nini undani muhimu kwamba kinaendelea kuhakikisha hii kwa kweli kazi? Na kwa "kweli kazi" Mimi maana, kiasi kama kamba, unatufanya kwenda kutoka tabia ya kwanza katika jina Davin ya pili, kwa wa tatu, mpaka nne, na mwisho sana, jinsi gani sisi kujua wakati tuko mwishoni ya orodha wanaohusishwa kwamba inaonekana kama hii? Wakati ni null. Na nimepata kuwakilishwa aina hii ya kama kama nguvu ya umeme mhandisi, na kutuliza kidogo ishara, ya kila aina. Lakini kwamba tu maana null katika kesi hii. Unaweza kuteka ni idadi yoyote ya njia, lakini mwandishi huyu kilichotokea kwa kutumia alama hii hapa. 

Hiyo kwa muda mrefu kama sisi ni stringing wote wa nodes hizi pamoja, tu kukumbuka ambapo moja ya kwanza ni, hivyo muda mrefu kama sisi kuweka alama maalum katika node mwisho sana katika orodha, na tutaweza kutumia null, kwa sababu hiyo nini tuna inapatikana kwa sisi, orodha hii ni kamili. Na hata kama mimi tu kukupa pointer kwa kipengele kwanza, wewe, programu, Unaweza shaka kupata mapumziko ya yake. Lakini hebu basi akili yako tanga kidogo, kama uko tayari kabisa wandered-- nini kwenda kuwa wakati mbio ya kutafuta kitu chochote katika orodha hii? Damn hilo, ni O kubwa ya n, ambayo si mbaya, katika haki. Lakini ni linear. Sisi wameacha kipengele kile ya arrays na kusonga zaidi kuelekea picha hii ya dynamically kusuka pamoja au wanaohusishwa nodes? Tumekuwa aliyopewa up upatikanaji random. safu ni nzuri kwa sababu mathematically kila kitu ni nyuma kwa nyuma kwa nyuma kwa nyuma. Hata ingawa picha hii inaonekana pretty, na hata ingawa inaonekana kama nodes hizi ni nicely spaced mbali, katika hali halisi wao inaweza kuwa mahali popote. OX1, Ox50, Ox123, Ox99, hizi nodes inaweza kuwa mahali popote. Kwa sababu gani malloc kutenga kumbukumbu kutoka chungu, lakini mahali popote katika chungu. Wewe si lazima kujua kwamba ni kwenda kuwa nyuma kwa nyuma kwa nyuma. Na hivyo picha hii katika hali halisi ya si kwenda kuwa kabisa hii pretty. 

Hivyo ni kwenda kuchukua kidogo ya kazi ili kutekeleza kazi hii. Basi hebu kutekeleza tafuta sasa. Na tutaweza kuona aina ya njia wajanja wa kufanya hivyo. Hivyo kama mimi ni kutafuta kazi na Mimi nina aliyopewa variable, integer n kwa kuangalia, mimi haja ya kujua syntax mpya kwa ajili ya kuangalia ndani ya ya muundo hiyo ni alisema kwa, ili kupata n. Basi hebu kufanya hili. 

Hivyo kwanza mimi nina kwenda mbele na kutangaza nodi *. Na mimi nina kwenda kumwita pointer, tu kwa mkataba. Na mimi nina kwenda initialize kwa kwanza. Na sasa siwezi kufanya hivyo katika idadi ya njia. Lakini nina kwenda kuchukua njia ya kawaida. Wakati pointer ni si sawa na null, na kwamba ni halali syntax. Na ni tu ina maana kufanya yafuatayo, hivyo muda mrefu kama wewe si akionyesha chochote. Nini nataka kufanya? 

Kama pointer dot n, basi mimi kuja nyuma na kwamba, equals-- sawa na nini? Nini thamani mimi kuangalia kwa? n halisi kwamba ilipitishwa katika. Hivyo hapa ni kipengele mwingine ya C na lugha nyingi. Hata ingawa muundo kuitwa node ina thamani n, kabisa halali na pia kuwa na hoja za mitaa au variable kuitwa n. Kwa sababu hata sisi, pamoja na macho ya binadamu, wanaweza kutofautisha kwamba hii ni labda n tofauti na n huu. Kwa sababu syntax ni tofauti. Nimepata dot na pointer, ambapo hii moja ina hakuna kitu kama hicho. Hivyo hii ni sawa. Hiyo ni sawa kuwaita mambo sawa. 

Kama mimi kupata hii, mimi nina kwenda wanataka kufanya kitu kama kutangaza kwamba sisi kupatikana n. Na tutaweza kuondoka kwamba kama maoni au pseudocode code. Mwingine, na hapa ni kuvutia sehemu, nini kufanya mimi wanataka kufanya kama nodi sasa si vyenye n kwamba mimi huduma ya juu? Je, mimi kufikia yafuatayo? Kama kidole yangu katika sasa ni PTR, na ni akionyesha chochote kwanza ni akizungumzia katika, jinsi gani mimi hoja kidole yangu kwa node ya pili katika kanuni? Naam, nini breadcrumb tuko kwenda kufuata katika kesi hii? Watazamaji: [inaudible]. DAVID J. Malan: Yeah, hivyo ijayo. Hivyo kama mimi kwenda nyuma yangu code hapa, kwa kweli, mimi nina kwenda mbele na kusema pointer, ambayo ni tu variable-- muda ni jina weird, PTR, lakini ni tu kama temp-- Mimi nina kwenda kuweka pointer sawa na chochote pointer is-- na tena, hii ni kwenda kuwa buggy kidogo kwa ajili ya moment-- dot ijayo. Kwa maneno mengine, mimi nina kwenda kuchukua yangu kidole hiyo akionyesha node hii hapa na mimi nina kwenda kusema, unajua nini, kuangalia uwanja ijayo na hoja kidole kwa chochote ni akizungumzia katika. Na hii ni kwenda kurudia, kurudia, kurudia. Lakini wakati gani kidole yangu kuacha kufanya kitu chochote wakati wote? Haraka kama nini mstari wa kanuni mateke katika? Watazamaji: [inaudible] DAVID J. Malan: Kama hatua wakati pointer ni si sawa na null. Wakati fulani kidole yangu kwenda kuwa akionyesha null na mimi nina kwenda kwa kutambua hiyo ni mwisho wa orodha hii. Sasa, hii ni kidogo uongo nyeupe kwa urahisi. Ni zinageuka kuwa hata kama sisi tu kujifunza dot nukuu hii kwa ajili ya miundo, pointer ni si struct. PTR ni nini? Tu kuwa zaidi nitpicky. Ni pointer nodi. Siyo node yenyewe. Kama sikuwa na nyota hapa, pointer absolutely-- ni nodi. Hii ni kama wiki moja tamko la variable, ingawa neno "node" ni mpya. 

Lakini kwa haraka kama sisi kuanzisha nyota, ni sasa pointer nodi. Na kwa bahati mbaya huwezi kutumia dot nukuu kwa pointer. Una kutumia mshale nukuu, ambayo, strikingly, ni mara ya kwanza kipande yoyote ya syntax inaonekana Intuitive. Hii ina inaonekana kama mshale. Na hivyo kwamba ni jambo jema. Na hapa chini literally inaonekana kama mshale. Hivyo nadhani hiyo ni la-- mimi si kufikiri mimi nina juu-kufanya here-- mimi nadhani hiyo ni mwisho mpya kipande ya syntax tunakwenda kuona. Na nashiriki, ni kweli kidogo Intuitive zaidi. 

Sasa, kwa wale ambao kingependa njia ya zamani, bado unaweza kutumia dot nukuu. Lakini kama per Jumatatu mazungumzo, sisi kwanza haja ya kwenda huko, kwenda kuwa kushughulikia, na kisha kupata shamba. Hivyo hii ni pia sahihi. Na kusema ukweli, hii ni kidogo zaidi pedantic. Wewe ni literally akisema, dereference pointer na kwenda huko. Kisha kunyakua .n, shamba iitwayo n. Lakini kusema ukweli, hakuna mtu anataka aina au kusoma hii. Na hivyo dunia zuliwa arrow nukuu, ambayo ni sawa, kufanana, ni tu Kiwango cha kisintaksia sukari. Hivyo njia dhana ya kusema hii inaonekana zaidi, au inaonekana rahisi. 

Hivyo sasa mimi nina kwenda kufanya jambo moja nyingine. Mimi nina kwenda kusema "kuvunja" mara moja nimekuwa kupatikana hivyo mimi si kuendelea kutafuta kwa ajili yake. Lakini hii ni kiini ya kazi ya utafutaji. Lakini ni rahisi sana, katika mwisho, si kwa kutembea kwa njia ya kificho. Hii ni kweli utekelezaji rasmi ya kutafuta katika leo usambazaji code. Mimi kuthubutu kusema kwamba Insert ni si hasa furaha kwa kutembea kwa njia ya kuibua, wala ni kufuta, hata ingawa mwisho wa siku wao jipu chini kwa haki rahisi heuristics. 

Basi hebu kufanya hili. Kama wewe utakuwa ucheshi mimi hapa, mimi kuleta rundo la mipira stress. Mimi kuletwa rundo la idadi. Na tunaweza kupata kujitolea chache tu kuwakilisha 9, 17, 20, 22, 29, na 34? Hivyo kimsingi kila mtu ambaye ni hapa leo. Hiyo ilikuwa moja, mbili, tatu, nne, tano, sita watu. Na nimekuwa aliuliza kwa go-- kuona, hakuna moja katika nyuma huwafufua mikono yao. OK, moja, mbili, tatu, nne, five-- napenda mzigo balance-- sita. OK, wewe sita kuja juu up. Tutaweza haja watu wengine. Sisi kuletwa mipira ya ziada stress. Na kama unaweza, kwa muda tu, line maisha yenu juu tu kama picha hii hapa. 

Wote haki. Hebu angalia, nini jina lako? 

Watazamaji: Andrew. 

DAVID J. Malan: Andrew, wewe ni namba 9. Nice kukutana na wewe. Hapa kwenda. Watazamaji: Jen. DAVID J. Malan: Jen. Daudi. Namba 17. Ndiyo? 

Watazamaji: Mimi nina Julia. 

DAVID J. Malan: Julia, David. Idadi 20. Watazamaji: Christian. DAVID J. Malan: Christian, David. Idadi 22. Na? 

Watazamaji: JP. DAVID J. Malan: JP. Idadi 29. Hivyo kwenda mbele na kupata in-- Uh oh. Uh oh. Kusubiri. 20. Je, mtu yeyote kuwa na marker? Watazamaji: Mimi nimepata Sharpie. DAVID J. Malan: You got Sharpie? OK. Na je, mtu yeyote kuwa na kipande cha karatasi? Ila hotuba. Kuja juu. Watazamaji: Sisi tumepewa yake. DAVID J. Malan: Sisi got it? Zote haki, asante. Hapa sisi kwenda. Ilikuwa hii kutoka kwenu? Wewe tu kuokolewa siku. Hivyo 29. Wote haki. Mimi misspelled 29, lakini OK. Kwenda mbele. Haki wote, mimi nitakupa kalamu yako nyuma momentarily. Hivyo tuna folks hizi hapa. Hebu kuwa na mtu mwingine. Gabe, je, unataka kucheza kipengele kwanza hapa? Tutaweza haja ya wewe kwa uhakika hizi folks faini. Hivyo 9, 17, 20, 22, aina ya 29, na kisha 34. Je, sisi kupoteza mtu? Mimi kufanya kuwa 34. Ambapo did-- OK, ambaye anataka kuwa 34? OK, kuja juu juu, 34. Zote haki, hii itakuwa pamoja na thamani ya kilele. Nini jina lako? 

Watazamaji: Peter. 

DAVID J. Malan: Peter, kuja juu up. Haki wote, hivyo hapa ni rundo zima la nodes. Kila mmoja wenu guys inawakilisha moja ya rectangles haya. Na Gabe, kidogo isiyo ya kawaida mtu nje, inawakilisha kwanza. Hivyo pointer yake ni kidogo kidogo juu ya screen kuliko mtu mwingine. Na katika kesi hii, kila mmoja wa wako wa kushoto mikono ni kwenda aidha uhakika chini, hivyo anayewakilisha null, hivyo tu kukosekana kwa pointer, au ni kwenda akizungumzia nodi karibu na wewe. 

Hivyo sasa hivi kama wewe kupamba wenyewe kama picha hapa, kwenda mbele na hatua kwa kila mmoja, na Gabe katika akizungumzia hasa katika namba 9 ya kuwakilisha orodha. OK, na idadi 34, mkono wako wa kushoto lazima tu akizungumzia katika sakafu. 

OK, hivyo hii ni orodha wanaohusishwa. Hivyo hii ni mazingira katika swali. Na hakika, hii ni mwakilishi wa darasa la matatizo kwamba unaweza kujaribu kutatua na kanuni. Unataka hatimaye kuingiza kipengele mpya katika orodha. Katika kesi hiyo, tunakwenda kujaribu kuingiza idadi 55. Lakini kuna kwenda kuwa matukio mbalimbali ya kuzingatia. Na hakika, hii ni kwenda kuwa moja ya big-picha Takeaways hapa, ni, nini ni kesi tofauti. Je, ni tofauti kama hali au matawi kwamba mpango wako wanaweza kuwa na? 

Naam, idadi wewe ni kujaribu Insert, ambayo sisi kujua sasa kuwa 55, lakini kama wewe hakujua mapema, mimi daresay unaingia angalau tatu inawezekana hali. Ambapo wanaweza kipengele mpya kuwa? Watazamaji: Na mwisho au katikati. DAVID J. Malan: Mwishoni, katika katikati, au mwanzoni. Hivyo mimi kudai kuna angalau matatizo matatu sisi haja ya kutatua. Hebu kuchagua nini labda arguably rahisi moja, ambapo kipengele mpya mali mwanzoni. Hivyo nina kwenda kuwa na code kabisa kama kutafuta, ambayo mimi tu aliandika. Na mimi nina kwenda kuwa na PTR, ambayo Mimi itabidi kuwakilisha hapa kwa kidole yangu, kama kawaida. 

Na kumbuka thamani, nini gani sisi initialize PTR kwa? Hivyo sisi initialized kwa null awali. Lakini basi nini sisi kufanya mara moja sisi walikuwa ndani ya kutafuta kazi yetu? Sisi kuweka sawa na ya kwanza, ambayo haina maana kufanya hivyo. Kama mimi kuweka PTR sawa na kwanza, nini lazima mkono wangu kweli kuwa akionyesha? Haki. Hivyo kama Gabe na mimi ni kwenda kuwa na maadili sawa hapa, tunahitaji wote wawili uhakika katika namba 9. 

Hivyo hii ilikuwa mwanzo wa hadithi yetu. Na sasa hii ni moja kwa moja, ingawa syntax ni mpya. Conceptually hii ni search linear. Ni 55 sawa na 9? Au tuseme, hebu sema chini ya 9. Kwa sababu mimi nina kujaribu kufikiri mahali pa kuweka 55. Chini ya 9, chini ya 17, chini ya ya 20, chini ya 22, chini ya 29, chini ya 34, hakuna. Hivyo sasa tuko katika kesi moja ya angalau tatu. 

Kama mimi nataka kuingiza 55 zaidi ya hapa, nini mstari wa kanuni haja ya kupata kuuawa? Ni kwa jinsi gani picha hii ya binadamu haja ya kubadili? Je, mimi kufanya na mkono wangu wa kushoto? Hii inapaswa kuwa null awali, kwa sababu mimi nina mwishoni mwa orodha. Na kile lazima kutokea hapa pamoja na Petro, kwa nani? Yeye ni wazi kwenda kwa uhakika na mimi. Hivyo mimi kudai kuna mistari angalau mbili wa kanuni katika sampuli kificho kutoka leo kwamba kinaendelea kutekeleza hili mazingira ya kuongeza 55 katika mkia. Na naweza kuwa na mtu hop up na tu kuwakilisha 55? Haki wote, wewe ni mpya 55. 

Hivyo sasa nini kama ya mazingira huja pamoja, na tunataka kuingiza katika mwanzo au mkuu wa orodha hii? Na nini jina lako, idadi ya 55? 

Watazamaji: Jack. 

DAVID J. Malan: Jack? OK, nzuri ya kukutana na wewe. Karibu ndani. Hivyo sasa sisi ni kwenda kuingiza, kusema, namba 5. Hapa ni kesi ya pili ya tatu sisi kuja na kabla ya. Hivyo kama 5 yanakuwa mwanzoni, hebu angalia jinsi sisi kupata kwamba nje. Mimi initialize PTR yangu pointer kwa namba 9 tena. Na mimi barabara, oh, 5 ni chini ya 9. Hivyo kurekebisha picha hii kwa ajili yetu. Ambao mikono, Gabe au Daudi or-- namba 9 ya jina ni nini? 

Watazamaji: Jen. 

DAVID J. Malan: hands-- Jen ya ambayo ya mikono yetu haja ya kubadili? OK, hivyo Gabe anasema nini sasa? Saa yangu. Mimi ni node mpya. Hivyo mimi itabidi tu aina ya hoja hapa kuona kuibua. Na wakati huo huo je, mimi uhakika kwamba? Bado ambapo mimi nina akizungumzia. Hivyo hiyo ni yake. Hivyo tu kweli line moja ya kanuni fixes hasa katika suala hili, ingekuwa kuonekana. Haki zote, hivyo hiyo ni nzuri. Na mtu anaweza kuwa placeholder kwa 5? Kuja juu juu. Sisi itabidi kupata wewe mara ya pili. 

Haki zote, hivyo now-- na kama kando, majina Mimi si kufanya wazi kutaja ya haki sasa, pred pointer, mtangulizi pointer na pointer mpya, hiyo ni tu majina aliyopewa katika sampuli kificho kwa kuyatumia au mikono yangu hiyo ni aina ya kuonyesha kote. Nini jina lako? 

Watazamaji: Christine. 

DAVID J. Malan: Christine. Karibu ndani. Haki zote, hivyo hebu fikiria sasa kidogo zaidi annoying mazingira, ambapo mimi unataka Insert kitu kama 26 katika hili. 20? Nini? Hizi are-- jambo zuri tuna kalamu hii. Zote haki, 20. Kama mtu anaweza kupata kipande kingine cha karatasi tayari, tu katika case-- haki yote. Oh, kuvutia. Naam hii ni mfano ya hotuba mdudu. OK hivyo nini jina yako tena? Watazamaji: Julia. DAVID J. Malan: Julia, unaweza pop nje na kujifanya wewe walikuwa kamwe huko? OK, hii kamwe kilichotokea. Asante. Hivyo tuseme tunataka kuingiza Julia katika orodha hii wanaohusishwa. Yeye ni namba 20. Na bila shaka yeye ni kwenda ni katika begin-- hawana uhakika katika chochote bado. Hivyo mkono wako unaweza aina ya kuwa chini null au baadhi thamani takataka. Hebu kuwaambia hadithi ya haraka. Mimi nina akionyesha namba 5 wakati huu. Kisha mimi kuangalia 9. Kisha mimi kuangalia 17. Kisha mimi kuangalia 22. Na mimi kutambua, ooh, Julia mahitaji ya kwenda kabla ya 22. Basi nini mahitaji ya kutokea? Ambao mikono haja ya kubadili? Julia ya, yangu, or-- nini jina yako tena? 

Watazamaji: Christian. 

DAVID J. Malan: Christian au? 

Watazamaji: Andy. 

DAVID J. Malan: Andy. Mkristo au Andy? Andy mahitaji ya kumweka katika? Julia. Wote haki. Hivyo Andy, unataka kumweka katika Julia? Lakini kusubiri dakika. Katika hadithi hivi sasa, Mimi nina aina ya moja katika malipo, kwa maana kwamba pointer ni jambo kwamba kuhamia kwa njia ya orodha. Tuweze kuwa na jina kwa Andy, lakini hakuna variable kuitwa Andy. tu variable mwingine tuna ni kwanza, ambaye ni kuwakilishwa na Gabe. 

Hivyo hii ni kweli kwa nini hivyo mbali tumekuwa si zinahitajika huu. Lakini sasa juu ya screen kuna kutaja tena ya pred pointer. Hivyo basi mimi kuwa wazi zaidi. Kama hii ni pointer, mimi alikuwa bora kupata akili kidogo zaidi kuhusu iteration yangu. Kama huna akili yangu kwenda kwa njia ya hapa tena, akizungumzia hapa, akizungumzia hapa. Lakini ngoja na pointer pred, mtangulizi pointer, hiyo ni aina ya akionyesha kipengele Mimi mara tu saa. Hivyo wakati mimi kwenda hapa, sasa mkono wangu wa kushoto updates. Wakati mimi kwenda hapa wangu updates mkono wa kushoto. Na sasa nina si tu pointer kwa kipengele kwamba huenda baada ya Julia, Mimi bado wana pointer kwa Andy, kipengele kabla ya. Hivyo unaweza kupata, kimsingi, breadcrumbs, kama wewe, yote ya kuyatumia zinazohitajika. 

Hivyo kama mimi nina akionyesha Andy na mimi nina pia akizungumzia Christian, ambaye mikono lazima sasa kuwa alisema mahali pengine? Hivyo Andy sasa wanaweza kumweka katika Julia. Julia sasa wanaweza kumweka katika Kikristo. Kwa sababu yeye anaweza nakala yangu upande wa kulia ya pointer. Na kwamba kwa ufanisi unaweka nyuma katika nafasi hii hapa. Hivyo katika muda mfupi, hata ingawa hii ni kuchukua us aina ya milele kwa kweli update wanaohusishwa orodha, kutambua kwamba shughuli za ni rahisi kiasi. Ni ya moja, mbili, tatu mstari wa kanuni hatimaye. Lakini kung'ata wale mstari wa kanuni labda ni kidogo ya mantiki kwamba ufanisi anauliza swali, ambapo ni sisi? Je, sisi mwanzoni, katikati, au mwisho? 

Sasa, kuna shaka baadhi ya wengine shughuli tupate kutekeleza. Na picha hizi hapa depict tu kile sisi tu alivyofanya kwa binadamu. Nini juu ya kuondolewa? Kama mimi nataka, kwa mfano, kuondoa namba 34 au 55, Nipate kuwa aina hiyo ya kificho, lakini mimi nina kwenda haja ya hatua moja au mbili. Kwa sababu nini mpya? Kama mimi kuondoa mtu mwishoni, kama idadi ya 55 na kisha 34, nini pia ina mabadiliko kama mimi kufanya hivyo? Nina si evict-- nini jina yako tena? 

Watazamaji: Jack. 

DAVID J. Malan: Jack. Nina si tu evict-- bure Jack, hivyo literally wito bure Jack, au angalau pointer huko pia, lakini sasa nini inahitaji mabadiliko na Petro? Mkono wake bora kuanza akizungumzia chini. Sababu kwa haraka kama mimi wito bure juu ya Jack, kama Petro bado akionyesha Jack na mimi hivyo kuweka apitaye orodha na upatikanaji pointer hii, kwamba wakati wetu wa kale rafiki segmentation kosa ili kweli kick katika. Kwa sababu tumekuwa aliyopewa kumbukumbu nyuma Jack. 

Unaweza kukaa huko awkwardly kwa muda tu. Kwa sababu tuna michache tu shughuli ya mwisho ya kuzingatia. Kuondoa mkuu wa orodha, au beginning-- na hii moja ya kidogo annoying. Kwa sababu tuna kujua kwamba Gabe ni aina ya pekee katika mpango huu. Kwa sababu kwa kweli, yeye ana pointer yake mwenyewe. Yeye si tu kuwa alisema katika, kama ni karibu kila mtu mwingine hapa. 

Hivyo wakati mkuu wa orodha ni kuondolewa, ambao mikono haja ya kubadili sasa? Nini jina yako tena? 

Watazamaji: Christine. 

DAVID J. Malan: Mimi nina kubwa katika majina, inaonekana. Hivyo Christine na Gabe, ambao mikono haja ya kubadili wakati sisi kujaribu kuondoa Christine, namba 5, kutoka picha? OK, hivyo hebu kufanya Gabe. Gabe kinaendelea kwa uhakika, labda, katika namba 9. Lakini nini ijayo lazima kutokea? Watazamaji: Christine lazima kuwa null [inaudible]. DAVID J. Malan: Sawa, sisi lazima pengine make-- nikasikia "null" mahali fulani. Watazamaji: Null na bure yake. DAVID J. Malan: null nini? Watazamaji: Null na bure yake. DAVID J. Malan: Null na bure yake. Hivyo hii ni rahisi sana. Na ni kamili kwamba wewe ni sasa aina ya amesimama pale, si wa mali. Kwa sababu tumekuwa frikopplas kutoka kwenye orodha. Ve ufanisi imekuwa yatima kutoka kwenye orodha. Na hivyo sisi alikuwa bora wito bure sasa juu ya Christine kutoa kwamba kumbukumbu nyuma. Vinginevyo kila wakati sisi kufuta nodi kutoka orodha tupate kuwa maamuzi orodha mfupi, lakini si kweli kupungua ukubwa katika kumbukumbu. Na hivyo kama sisi kuendelea kuongeza na kuongeza, akiongeza mambo kwenye orodha, kompyuta yangu ili kupata polepole na polepole na polepole, kwa sababu mimi nina mbio nje ya kumbukumbu, hata kama nina si kweli kutumia ka Christine ya ya kumbukumbu tena. 

Hivyo katika mwisho kuna wengine matukio, ya course-- kuondolewa katikati, kuondolewa mwishoni, kama sisi kuona. Lakini zaidi ya kuvutia Changamoto sasa ni kwenda kuwa kwa kuzingatia hasa nini wakati mbio ni. Hivyo si tu unaweza kuweka yako vipande vya karatasi, kama, Gabe, isingekuwa akili kutoa kila mtu stress mpira. Asante sana kwa orodha yetu wanaohusishwa wa kujitolea hapa, kama unaweza. 

[Makofi] 

DAVID J. Malan: All wa kulia. Hivyo wanandoa wa uchambuzi maswali basi, kama mimi naweza. Tumeona nukuu hii kabla, O kubwa na Omega, mipaka juu na mipaka ya chini juu ya mbio wakati wa baadhi ya algorithm. Hivyo hebu fikiria tu wanandoa wa maswali. 

Moja, na sisi alisema kabla ya, nini mbio wakati wa kutafuta kwa orodha katika suala la kubwa O? Nini amefungwa juu ya kuendesha wakati wa kutafuta orodha wanaohusishwa kama kutekelezwa na kujitolea yetu hapa? Ni O kubwa ya n, linear. Kwa sababu katika hali mbaya zaidi, kipengele, kama 55, sisi kuwa na kuangalia kwa inaweza kuwa ambapo Jack alikuwa, njia yote mwishoni. Na kwa bahati mbaya, tofauti na safu hatuwezi kupata dhana wakati huu. Hata ingawa yote ya binadamu wetu walikuwa sorted kutoka mambo madogo, 5, njia yote hadi kipengele kubwa, 55, hiyo ni kawaida jambo zuri. Lakini ni nini dhana kwamba tena kuruhusu sisi kufanya nini? Watazamaji: [inaudible] DAVID J. Malan: Sema tena? Watazamaji: Random upatikanaji. DAVID J. Malan: Random upatikanaji. Na kwa upande hiyo ina maana tunaweza hakuna tena kutumia zeros dhaifu, Intuition, na udhahiri wa kutumia binary kutafuta na kugawanya na kushinda. Kwa sababu hata kama sisi binadamu inaweza wazi kuona kwamba Andy au Kikristo walikuwa takribani katikati ya orodha, sisi tu kujua kwamba kama kompyuta na skimming orodha tangu mwanzo. Hivyo tumekuwa wamekata kwamba upatikanaji random. 

O Hivyo kubwa ya n sasa ni juu amefungwa juu ya search wakati wetu. Nini juu ya omega ya search yetu? Nini chini amefungwa juu ya kutafuta kwa baadhi ya idadi katika orodha hii? Watazamaji: [inaudible] DAVID J. Malan: Sema tena? Watazamaji: One. DAVID J. Malan: One. Hivyo wakati mara kwa mara. Katika kesi bora, Christine ni kweli mwanzoni mwa orodha. Na sisi ni kuangalia kwa namba 5, hivyo sisi kupatikana yake. Hivyo hakuna mpango kubwa. Lakini yeye ni got kuwa katika mwanzo wa orodha katika kesi hii. Nini juu ya kitu kama Futa? Nini kama unataka kufuta kipengele? Nini amefungwa juu na chini amefungwa juu ya kufuta kitu kutoka wanaohusishwa orodha? Watazamaji: [inaudible] DAVID J. Malan: Sema tena? Watazamaji: n. DAVID J. Malan: n ni kweli juu amefungwa. Kwa sababu katika kesi mbaya sisi kujaribu kufuta Jack, kama sisi tu hawakuwa. Yeye ni njia yote mwishoni. Inachukua sisi milele, au n hatua ya kumpata. Hivyo hiyo ni amefungwa juu. Hiyo ni linear, uhakika. Na kesi bora mbio wakati, au mipaka ya chini katika kesi bora itakuwa ni mara ya mara kwa mara. Kwa sababu labda sisi kujaribu kufuta Christine, na sisi tu kupata bahati yeye ni mwanzoni. Sasa kusubiri dakika. Gabe mara mwanzoni pia, na sisi pia alikuwa na update Gabe. Hivyo hiyo haikuwa hatua moja tu. Hivyo ni kweli mara kwa mara wakati, katika kesi bora, kuondoa kipengele madogo? Ni, hata ingawa inaweza kuwa mbili, tatu, au hata 100 mstari wa kanuni, kama ni idadi sawa ya mistari, si katika baadhi kitanzi, na uhuru wa ukubwa ya orodha, kabisa. Kufuta kipengele katika mwanzo wa orodha, hata kama sisi kuwa na kushughulika na Gabe, ni wakati wa mara kwa mara bado. 

Hivyo hii inaonekana kama hatua kubwa nyuma. Na nini kupoteza muda kama, katika wiki moja na wiki zero tulikuwa si tu pseudocode code lakini code halisi kutekeleza kitu ambacho ni logi msingi n, au kuingia, badala yake, ya n, msingi 2, katika suala la mbio yake wakati. Hivyo kwa nini heck ingekuwa tunataka kuanza kutumia kitu kama orodha wanaohusishwa? Yeah. 

Watazamaji: Hivyo unaweza kuongeza mambo ya safu. DAVID J. Malan: Hivyo unaweza kuongeza mambo kwa safu. Na hii pia ni ufadhili. Na tutaweza kuendelea kuona hii, biashara-off, kiasi kama tumeona biashara-off na kuunganisha aina. Tunaweza kweli kasi ya kutafuta au kuchagua, badala yake, kama sisi kutumia nafasi kidogo zaidi na na chunk ya ziada ya kumbukumbu au safu kwa kuunganisha aina. Lakini sisi kutumia zaidi nafasi, lakini sisi kuokoa muda. Katika kesi hiyo, sisi ni kutoa up wakati lakini sisi ni kupata mabadiliko, mabadiliko kama wewe, ambayo ni arguably kipengele chanya. 

Sisi ni pia kutumia nafasi. Ni katika maana gani ni wanaohusishwa orodha ghali zaidi katika suala la nafasi zaidi safu? Ambapo ni nafasi ya ziada kuja kutoka? Yeah? 

Watazamaji: [inaudible] pointer. 

DAVID J. Malan: Yeah, sisi pia kuwa pointer. Hivyo hii ni minorly annoying kwa kuwa sipo Mimi kuhifadhi tu int kuwakilisha int. Mimi nina kuhifadhi int na a pointer, ambayo pia ni 32 bits. Hivyo mimi nina literally mara mbili kiasi cha nafasi ya kushiriki. Hivyo hiyo ni biashara-off, lakini hiyo ni katika kesi ya int. Tuseme kwamba wewe si kuhifadhi int, lakini nadhani kila mmoja wa rectangles haya au kila mmoja wa hawa binadamu mara anayewakilisha neno, neno la Kiingereza kuwa inaweza kuwa wahusika tano, 10 wahusika, labda hata zaidi. Kisha kuongeza bits 32 tu zaidi inaweza kuwa chini ya mpango kubwa. 

Nini kama kila mmoja wa wanafunzi katika maandamano walikuwa literally mwanafunzi structs kwamba kuwa na majina na nyumba na labda namba za simu na Twitter Hushughulikia na kadhalika. Basi wote wa mashamba tulianza kuzungumza juu ya siku nyingine, kiasi kidogo ya mpango kubwa kama nodes wetu kupata zaidi ya kuvutia na kubwa kwa kutumia, eh, ziada pointer tu kwa kiungo wao pamoja. Lakini kwa kweli, ni biashara-off. Na hakika, kanuni na ni zaidi tata, kama wewe utakuwa kuona kwa kupitia skimming kuwa mfano fulani. Lakini nini kama kulikuwa na baadhi grail takatifu hapa. Nini kama hatuwezi kuchukua hatua nyuma lakini hatua kubwa mbele na kutekeleza data muundo kupitia ambayo sisi Unaweza kupata mambo kama Jack au Christine au mambo mengine yoyote katika safu hii katika wakati kweli mara kwa mara? Search ni mara kwa mara. Kufuta ni mara kwa mara. Insert ni mara kwa mara. Wote wa shughuli hizo ni mara kwa mara. Hiyo itakuwa grail zetu takatifu. Na kwamba ni wapi sisi pick up wakati ujao. Tazama wewe hapo.