[Powered by Google Translate] [Wiki 6, Inaendelea] [David J. Malan] [Chuo Kikuu cha Harvard] [Hii ni CS50.] [CS50.TV] Hii ni CS50 na hii ni mwisho wa wiki 6. Hivyo CS50x, moja ya kozi Harvard ya kwanza ya kushiriki katika mpango edX kweli hii ilipata kushika nafasi ya Jumatatu iliyopita. Kama ungependa kupata glimpse ya wengine ni nini kwenye Internet sasa kufuatia pamoja na, unaweza kichwa kwa x.cs50.net. Hiyo redirect wewe kwa sehemu husika kwenye edx.org, ambayo ilikuwa ambapo hii na kozi nyingine kutoka MIT na Berkeley sasa kuishi. Itabidi kuingia kwenye akaunti; utapata kwamba ni nyenzo kiasi kikubwa sawa kama umeshapata hii muhula, angalau wiki chache kuchelewa, kama sisi kupata kila kitu tayari. Lakini nini wanafunzi katika CS50x sasa kuona ni interface kabisa kama hii moja. Hii, kwa mfano, ni Zamyla kuongoza walkthrough kwa tatizo kuweka 0. Juu ya kuingia katika edx.org, mwanafunzi CS50x anaona aina ya mambo gani wanatarajia kuona katika mwendo: hotuba kwa Jumatatu, hotuba kwa Jumatano, mbalimbali kaptula, seti tatizo, walkthroughs, PDFs. Aidha, kama unaweza kuona hapa, mashine Tafsiri wa nakala ya Kiingereza ndani ya Kichina, Kijapani, Kihispania, Kiitaliano, na rundo zima la lugha nyingine ambayo hakika kuwa si mkamilifu kama sisi roll yao nje programmatically kutumia kitu kinachoitwa API, au maombi ya programu interface, kutoka Google ambayo inaruhusu yetu kubadili Kiingereza kwa lugha hizi nyingine. Lakini, shukrani kwa roho ya ajabu ya kujitolea baadhi mia-plus, random watu kwenye mtandao ambao kindly inayotolewa kujihusisha katika mradi huu, tutaweza kuwa na kuboresha hatua kwa hatua ubora wa tafsiri wale kwa kuwa binadamu kusahihisha makosa kwamba kompyuta yetu kuwa alifanya. Hivyo zinageuka tulikuwa wachache zaidi wanafunzi show juu ya Jumatatu kuliko sisi awali inatarajiwa. Kwa kweli, sasa ina watu 100,000 CS50x kufuatia pamoja nyumbani. Hivyo kutambua wewe ni sehemu ya darasa hili uzinduzi wa kufanya kozi hii katika sayansi ya kompyuta elimu kwa ujumla zaidi, pana zaidi, kupatikana. Na ukweli ni sasa, na baadhi ya kozi hizi kubwa online, wao wote kuanza na nambari hizi juu sana, kama sisi tunaonekana kuwa na kufanyika hapa. Lakini lengo, hatimaye, kwa CS50x ni kweli kupata watu wengi kama mstari wa kumaliza iwezekanavyo. Kwa design, CS50x anaenda kutolewa kutoka Jumatatu hii iliyopita njia zote 15 Aprili 2013, ili folks ambao wana ahadi shule mahali pengine, kazi, familia, migogoro mengine na kama, kuwa na kidogo zaidi kubadilika na ambayo kwa kupiga mbizi katika kozi hii, ambayo, inatosha kusema, ni kabisa ambitiously kufanyika kama tu juu ya mwendo wa miezi mitatu tu wakati wa muhula wa kawaida. Lakini wanafunzi hawa itakuwa kukabiliana seti tatizo moja, viewing maudhui sawa, kuwa upatikanaji wa kaptula sawa na kama. Hivyo kutambua kwamba sisi wote ni kweli katika hii pamoja. Na moja ya malengo ya mwisho wa CS50x si tu kupata folks kama wengi mstari wa kumaliza na kuwapa ufahamu huu newfound wa sayansi ya kompyuta na programu lakini pia kuwa na wao wana uzoefu huu pamoja. Moja ya tabia kufafanua wa 50 juu ya chuo, ni matumaini yetu, imekuwa ya aina hii ya uzoefu wa jumuiya, kwa bora au mbaya, wakati mwingine, lakini baada ya kuwa watu hawa kurejea kwa kushoto na kulia, na ofisi ya masaa na hackathon na wa haki. Ni ngumu kidogo kufanya hivyo katika mtu na folks online, lakini CS50x tutahitimisha katika Aprili na Expo kwanza milele CS50, ambayo itakuwa kukabiliana online ya wazo yetu ya haki ambapo hizi maelfu ya wanafunzi wote wataalikwa kuwasilisha 1 - 2 na video ya dakika, aidha screencast ya mradi wao wa mwisho au video wao akipunga hujambo na kuzungumza kuhusu mradi wao na demoing yake, kiasi kama watangulizi wako wamefanya hapa juu ya chuo katika haki, hivyo kuwa na mwisho wa muhula, matumaini ni kuwa na maonyesho ya kimataifa wa miradi ya wanafunzi CS50x 'mwisho, kiasi kama yale zakulaiki hii Desemba hapa juu ya chuo. Hivyo zaidi juu ya kwamba katika miezi ijayo. Pamoja na wanafunzi 100,000, ingawa, huja haja ya CAS chache zaidi. Kutokana na kwamba wewe guys ni mkali uchaguzi hapa na kuchukua CS50 wiki kadhaa kabla ya kutolewa nyenzo hii kwa folks juu ya edX, kutambua upendo tunataka kuhusisha kama wengi wa wanafunzi wetu wenyewe kama inawezekana katika mpango huu, wote wakati wa muhula kama vile baridi hii na hii spring ijayo. Hivyo kama ungependa kushiriki katika CS50x, hasa juu ya kujiunga katika CS50x Diskutera, toleo edX ya CS50 Diskutera, ambayo wengi wenu wamekuwa kutumia juu ya chuo, online bulletin bodi, tafadhali kufanya kichwa kwa URL kwamba, hebu kujua wewe ni nani, kwa sababu tunatarajia upendo wa kujenga timu ya wanafunzi na wafanyakazi na kitivo sawa juu ya chuo ambao ni tu kucheza pamoja na kusaidia nje. Na wanapo kuona swali hilo ni familiar nao, wewe kusikia mwanafunzi kuripoti baadhi mdudu mahali fulani huko nje katika nchi baadhi ya mtandao, na pete kengele kwa sababu wewe pia alikuwa na kwamba suala hilo hilo katika yako d-hall baadhi ya wakati uliopita, hopefully basi unaweza chime katika na kubadilishana uzoefu wako mwenyewe. Hivyo tafadhali wanayo haki kama ungependa. Kompyuta kozi ya sayansi katika Harvard kuwa na kidogo ya mapokeo, CS50 kati yao, ya kuwa na baadhi ya mavazi, baadhi ya nguo, kwamba unaweza kuvaa kujigamba mwishoni muhula, kwa kusema kabisa kujigamba kwamba wewe kumaliza CS50 na alichukua CS50 na kama, na sisi daima kujaribu kuhusisha wanafunzi katika mchakato huu kama iwezekanavyo, ambapo sisi kuwakaribisha, karibu wakati huu wa muhula, wanafunzi kuwasilisha miundo kutumia Photoshop, au chochote chombo cha uchaguzi Ningependa kutumia kama wewe ni designer, kuwasilisha miundo kwa ajili ya fulana na mashati na miavuli bandanas kidogo na kwa ajili ya mbwa na sisi sasa kuwa kama. Na kila kitu ni basi - washindi kila mwaka ni basi exhibited kwenye tovuti kozi ya saa store.cs50.net. Kila kitu ni kuuzwa kwa gharama huko, lakini tovuti anaendesha tu yenyewe na inaruhusu watu kuchagua rangi na miundo kwamba wao kama. Hivyo nimeona tunatarajia kushiriki tu baadhi ya miundo ya mwaka jana waliokuwa kwenye tovuti hii badala ya moja hapa, ambayo ni mapokeo ya kila mwaka. "Kila siku mimi nina Seg Faultn" ilikuwa moja ya maoni mwaka jana, ambayo bado inapatikana huko kwa Mbegu. Tulikuwa na hii moja, "CS50, Ilianza mwaka 1989." Moja ya Bowdens yetu, Rob, ulikuwa maarufu sana mwaka jana. "Timu ya Bowden" alizaliwa, design hii ilikuwa in, miongoni mwa wauzaji wa juu. Kama ilikuwa hii moja hapa. Watu wengi walikuwa "Bowden Homa" kulingana na magogo ya mauzo. Kutambua kwamba kwamba inaweza sasa kuwa design yako huko, juu ya mtandao. Maelezo zaidi juu ya hili katika tatizo inayofuata inatoa kuja. Moja zaidi chombo: umeshapata baadhi yatokanayo na hopefully sasa baadhi ya uzoefu wa mikono juu na GDB, ambayo ni, bila shaka, debugger na utapata kuendesha mpango wako katika ngazi ya haki Asili, kufanya nini aina ya mambo? Je GDB basi wewe kufanya? Yeah? Nipe kitu. [Mwanafunzi jibu, unintelligible] Nzuri. Hatua katika kazi, hivyo si tu kuwa na aina kukimbia na kuwa na pigo mpango kupitia ukamilifu wake, kuchapa nje ya mambo ya pato standard. Badala yake, unaweza hatua kupitia line hiyo kwa mstari, ama kuandika ijayo kwenda mstari kwa mstari kwa mstari au hatua kwa kupiga mbizi katika kazi, kawaida moja kwamba aliandika. Nini kingine haina GDB basi wewe kufanya? Yeah? [Mwanafunzi jibu, unintelligible] Magazeti vigezo. Hivyo kama unataka kufanya kujichunguza kidogo ndani ya mpango wako bila ya kuwa na mapumziko kwa kuandika kauli printf kila mahali, unaweza tu magazeti variable au kuonyesha kutofautiana. Nini kingine unaweza kufanya na debugger kama GDB? [Mwanafunzi jibu, unintelligible] Hasa. Unaweza kuweka breakpoints; unaweza kusema mapumziko utekelezaji katika kazi kuu au kazi foo. Unaweza kusema mapumziko utekelezaji katika mstari wa 123. Na breakpoints ni mbinu kweli nguvu kwa sababu kama una maana ya jumla ya ambapo tatizo lako pengine ni, huna kupoteza muda wanazidi kupitia ukamilifu wa programu hiyo. Unaweza kimsingi kuruka haki pale na kisha kuanza kuandika - wanazidi kupitia kwa hatua au ijayo au kama. Lakini samaki na kitu kama GDB ni kwamba inasaidia wewe, binadamu, kupata matatizo yako na kupata Bugs yako. Haina lazima kupata yao sana kwa ajili yenu. Hivyo sisi ilianzisha nyingine siku style50, ambayo ni fupi ya mstari amri chombo ambayo inajaribu stylize code yako kidogo zaidi cleanly kuliko wewe, binadamu, wanaweza kuwa na kufanyika. Lakini, pia, ni kweli tu kitu aesthetic. Lakini zinageuka kuna chombo hiki nyingine iitwayo Valgrind, ambayo ni kidogo zaidi arcane kutumia. Pato lake ni atrociously cryptic katika mtazamo wa kwanza. Lakini ni ajabu muhimu, hasa sasa kwamba sisi ni saa sehemu ya muda ambapo wewe ni mapya kwa kutumia malloc na mgao nguvu kumbukumbu. Mambo yanaweza kwenda kweli, kweli makosa haraka. Kwa sababu kama wewe kusahau huru kumbukumbu yako, au wewe dereference baadhi pointer null, au wewe dereference baadhi pointer takataka, ni nini dalili ya kawaida kwamba matokeo? Seg kosa. Na wewe kupata faili hii ya msingi ya baadhi ya idadi ya kilobytes au megabaiti kwamba inawakilisha hali ya kumbukumbu ya mpango wako ilipokwama, lakini programu yako hatimaye seg makosa, segmentation kosa, ambayo ina maana ya kitu mbaya kilichotokea daima karibu kuhusiana kwa makosa yanayohusiana na kumbukumbu kwamba alifanya mahali fulani. Hivyo Valgrind husaidia kupata mambo kama hayo. Ni chombo kwamba wewe kukimbia, kama GDB, baada ve compiled mpango wako, lakini badala ya kuendesha programu yako moja kwa moja, wewe kukimbia Valgrind na wewe kupita kwa hiyo programu yako, kama wewe kufanya na GDB. Sasa, matumizi, ili kupata aina bora ya pato, ni kidogo kwa muda mrefu, hivyo haki pale atop ya screen utaona Valgrind-v. "-V" karibu ulimwenguni kote ina maana verbose wakati unatumia programu kwenye kompyuta Linux. Hivyo ina maana mate nje data zaidi kuliko wewe nguvu na default. "- Leak-kuangalia = kamili." Hii ni kusema tu hundi kwa uvujaji wote inawezekana kumbukumbu, makosa ili nipate kuwa alifanya. Hii pia, ni dhana ya kawaida na mipango ya Linux. Kwa ujumla, kama una mstari amri hoja kwamba "kubadili", kwamba walidhani kubadili tabia ya mpango wa, na ni barua moja, ni-v, lakini kama hiyo ni switched, tu kwa kubuni programu, ni neno kamili au mfululizo wa maneno, mstari amri hoja huanza na -. Hizi ni baadhi tu ya binadamu makongamano, lakini utaona yao inazidi. Na kisha, hatimaye, "a.out" ni jina kwa ajili ya mpango holela katika mfano huu hasa. Na hapa ni baadhi ya pato mwakilishi. Kabla ya sisi kuangalia nini kwamba tupate maana, nivuke kwa snippet ya maadili ya juu hapa. Na napenda hoja hii nje ya njia, upesi, na hebu tuangalie memory.c, ambayo ni mfano huu mfupi hapa. Hivyo katika mpango huu, napenda kuvuta kazi na maswali. Tuna kazi kubwa ambayo inatoa wito kazi, f, na kisha nini f kuendelea kufanya, kwa Kiingereza kidogo kiufundi? Nini f kuendelea kufanya nini? Vipi kuhusu mimi itabidi kuanza na mstari 20, na mahali nyota Haijalishi, lakini mimi itabidi kuwa thabiti hapa na hotuba ya mwisho. Nini mstari 20 kufanya kwa ajili yetu? Upande wa kushoto. Tutaweza kuvunja chini zaidi. Int * x: nini kwamba kufanya? Sawa. Ni kutangaza pointer, na sasa hebu kuwa hata zaidi ya kiufundi. Ina maana gani, sana concretely, kutangaza pointer? Mtu mwingine? Yeah? [Mwanafunzi jibu, unintelligible] Too mbali. Hivyo wewe ni kusoma kwa upande wa kulia wa ishara sawa. Hebu mkazo tu upande wa kushoto, tu juu ya int * x. Hii haina "kutangaza" pointer, lakini sasa wacha kupiga mbizi katika undani kwa ufafanuzi huo. Je, hiyo concretely, kitaalam maana? Yeah? [Mwanafunzi jibu, unintelligible] Sawa. Ni kuandaa kuokoa anuani katika kumbukumbu. Nzuri. Na hebu kuchukua hatua hii moja zaidi; ni kutangaza variable, x, hiyo ni 32 bits. Na mimi najua ni 32 bits kwa sababu -? Siyo kwa sababu ni int, kwa sababu ni pointer katika kesi hii. Bahati mbaya kuwa ni moja na sawa na int, lakini ukweli kwamba kuna nyota kuna maana ya hii ni pointer na katika appliance, kama na kompyuta wengi, lakini si wote, kuyatumia ni 32 bits. Juu ya vifaa za kisasa zaidi kama Macs karibuni, PC karibuni, unaweza kuwa na kuyatumia 64-bit, lakini katika appliance, mambo haya ni ya 32 bits. Hivyo tutaweza standardize juu ya hilo. Zaidi concretely, hadithi inakwenda kama ifuatavyo: Sisi "kutangaza" pointer; gani kwamba mean? Sisi kuandaa kuhifadhi anwani kumbukumbu. Hiyo ina maana gani? Sisi kujenga variable inayoitwa x kwamba inachukua hadi 32 bits kwamba hivi karibuni kuhifadhi anwani ya integer. Na kwamba pengine kuhusu kama sahihi kama tunaweza kupata. Ni faini ya kusonga mbele kwa kurahisisha dunia na kusema tu kutangaza pointer kuitwa x. Kutangaza pointer, lakini kutambua na kuelewa nini hasa kinachoendelea hata katika wale tu wahusika wachache. Sasa, hii ni karibu rahisi kidogo, hata kama ni kujieleza tena. Hivyo ni nini hii kufanya, kwamba ni yalionyesha sasa: "malloc (10 * sizeof (int));" Yeah? [Mwanafunzi jibu, unintelligible] Nzuri. Na mimi itabidi kuchukua ni pale. Ni kugawa chunk ya kumbukumbu kwa integers kumi. Na sasa hebu kupiga mbizi katika kidogo zaidi; ni kugawa chunk ya kumbukumbu kwa integers kumi. Nini malloc kisha kurudi? anuani ya chunk kwamba, au, zaidi concretely, anuani ya Byte kwanza ya chunk kwamba. Jinsi ndipo ninapokuwa, programu, kujua ambapo kwamba chunk ya ncha kumbukumbu? Mimi najua kuwa ni contiguous. Malloc, kwa ufafanuzi, nitakupa chunk contiguous ya kumbukumbu. Hakuna mapengo katika hilo. Unaweza kupata kila Byte katika chunk kwamba, nyuma kwa nyuma kwa nyuma, lakini jinsi gani mimi kujua ambapo mwisho wa hii chunk ya kumbukumbu ni? Wakati matumizi malloc? [Mwanafunzi jibu, unintelligible] Good. Huna. Una kukumbuka. Mimi na kukumbuka kwamba mimi kutumika thamani 10, na mimi si hata wanaonekana wamefanya hivyo hapa. Lakini Wajibu ni kabisa juu yangu. Strlen, ambayo tumekuwa kuwa kidogo kujitegemea juu kwa masharti, kazi tu kwa sababu ya hii mkataba wa kuwa \ 0 au hii maalum nul tabia, NUL, mwisho wa kamba. Kuwa haina kushikilia kwa chunks tu holela wa kumbukumbu. Ni juu yako. Hivyo mstari 20, basi, kutenga chunk ya kumbukumbu kwamba wanaweza kuhifadhi integers kumi, na huweka anuani ya Byte kwanza ya kwamba chunk ya kumbukumbu katika x variable kuitwa. Ergo, ambayo ni pointer. Hivyo mstari 21, kwa bahati mbaya, ilikuwa ni makosa. Lakini kwanza, ni nini ni kufanya? Ni kusema duka katika eneo 10, 0 indexed, ya chunk ya kumbukumbu iitwayo x 0 thamani. Hivyo taarifa michache ya mambo ni kwenda juu. Hata ingawa x ni pointer, wanakumbuka kutoka wiki kadhaa zilizopita kwamba bado unaweza kutumia safu-style mraba bracket nukuu. Kwa sababu hiyo ni kweli mfupi mkono nukuu kwa hesabu zaidi cryptic-kuangalia pointer. ambapo tunataka kufanya kitu kama hii: Chukua x anuani, hoja spots 10 juu, kisha kwenda huko kwa kila anuani ni kuhifadhiwa katika eneo hilo. Lakini kusema ukweli, hii ni mauaji ya kusoma na kupata starehe na. Hivyo dunia kawaida anatumia mabano mraba tu kwa sababu ni hivyo zaidi ya binadamu ya kirafiki ya kusoma. Lakini hiyo ni nini kweli kinachoendelea chini ya Hood; x ni anwani, si safu, per se. Hivyo hii ni hifadhi 0 katika eneo 10 katika x. Kwa nini hii ni mbaya? Yeah? [Mwanafunzi jibu, unintelligible] Hasa. Sisi tu zilizotengwa ints kumi, lakini sisi kuhesabu kutoka 0 wakati programu katika C, hivyo unaweza kupata 10 0 1 2 3 4 5 6 7 8 9, lakini si. Hivyo aidha mradi ni kwenda kosa seg au siyo. Lakini sisi si kweli kujua, hii ni aina ya tabia nondeterministic. Ni kweli inategemea kama sisi kupata bahati. Kama zinageuka kuwa mfumo wa uendeshaji haina akili kama mimi kutumia Byte ziada, hata ingawa haijatoa ni mimi, mpango wangu ili si ajali. Ni mbichi, ni Buggy, lakini unaweza kuona kuwa dalili, au unaweza kuona mara moja tu kwa wakati. Lakini ukweli ni kwamba mdudu ni, kwa kweli, kuna. Na ni kweli tatizo kama umefanya imeandikwa mpango kwamba unataka kuwa sahihi, kwamba ve kuuzwa mpango kwamba watu ni kutumia kwamba kila mara moja kwa wakati shambulio kwa sababu, bila shaka, hii si nzuri. Kwa kweli, kama una simu Android au iPhone na wewe download programu siku hizi, kama wameweza milele alikuwa App tu kujiondoa, ghafla ni kutoweka, hiyo ni karibu daima matokeo ya baadhi ya suala kumbukumbu-kuhusiana, ambapo programu Star up na dereferenced pointer kwamba yeye au yeye anapaswa kuwa na matokeo ya iOS au Android ni kuua tu mpango kabisa badala ya tabia hatarishi undefined au aina fulani ya mapatano ya usalama. Kuna moja nyingine mdudu katika mpango huu badala ya moja huu. Nini kingine mimi Star up katika mpango huu? Nimekuwa si mazoezi kile nimepata njema. Yeah? [Mwanafunzi jibu, unintelligible] Good. Mimi si huru kumbukumbu. Hivyo utawala wa kidole gumba sasa ina kuwa wakati wowote wewe piga malloc, lazima kuwaita bure wakati wewe ni kufanyika kwa kutumia kwamba kumbukumbu. Sasa, wakati nataka huru kumbukumbu hii? Pengine, kuchukua line hii ya kwanza ilikuwa sahihi, napenda wanataka kufanya hivyo hapa. Sababu sikuweza, kwa mfano, kufanya hivyo chini hapa. Kwa nini? Tu nje ya upeo. Hivyo hata kama sisi ni kuzungumza juu ya kuyatumia, hii ni wiki 2 au 3 suala hilo, ambapo x ni tu katika wigo ndani ya braces curly ambapo ilikuwa alitangaza. Hivyo wewe dhahiri hayawezi kumwondolea pale. Nafasi yangu tu ya bure ni takribani baada ya mstari 21. Hii ni programu ya haki rahisi, ilikuwa haki rahisi mara moja aina ya amefungwa akili yako kuzunguka kile anachokifanya mpango, ambapo makosa walikuwa. Na hata kama hakuwa na kuona kwa mara ya kwanza, hopefully ni kidogo dhahiri sasa kwamba makosa hayo ni pretty urahisi na kutatuliwa kwa urahisi kufanywa. Lakini wakati mpango ni zaidi ya 12 mistari ya muda mrefu, ni 50 mistari ya muda mrefu, 100 mistari ya muda mrefu, kutembea kwa njia ya kificho wako mstari kwa mstari, kufikiri kwa njia ya mantiki, inawezekana lakini si hasa fun kufanya, daima kutafuta mende, na pia ni vigumu kufanya hivyo, na kwamba sababu ya chombo kama Valgrind lipo. Hebu kwenda mbele na kufanya hili: napenda kufungua terminal yangu dirisha, na basi mimi si kukimbia tu kumbukumbu, kwa sababu kumbukumbu inaonekana kuwa faini. Nina kupata bahati. Kwenda Byte kwamba ziada mwishoni mwa safu haionekani kuwa pia tatizo. Lakini basi mimi, hata hivyo, kufanya kuangalia sanity, ambayo ina maana ya kuangalia kama hii ni kweli sahihi. Basi hebu kufanya valgrind-v - leak-kuangalia = kamili, na kisha jina la mpango katika kesi hii ni kumbukumbu, si a.out. Hivyo basi mimi kwenda mbele na kufanya hili. Hit Ingiza. Mpendwa Mungu. Hii ni pato lake, na hii ni kile alluded mapema. Lakini, kama wewe kujifunza kusoma kwa njia zote za nonsense hapa, zaidi ya hii ni uchunguzi pato kwamba si kwamba kuvutia. Nini jicho lako kweli anataka kuwa na kuangalia kwa ni kutaja ya makosa au batili. Maneno kwamba zinaonyesha matatizo. Na kwa kweli, hebu angalia nini kinaendelea makosa chini hapa. Nina muhtasari wa aina fulani, "katika matumizi ya exit. 40 ka katika vitalu 1" Mimi nina uhakika nini kuzuia ni bado, lakini 40 bytes kweli anahisi kama mimi naweza kufikiri ambapo ule unaokuja kutoka. 40 bytes. Kwa nini ni ka 40 katika matumizi ya exit? Na hasa zaidi, kama sisi kitabu chini hapa, mbona mimi dhahiri waliopotea ka 40? Yeah? [Mwanafunzi jibu, unintelligible] Perfect. Yeah, kwa uhakika. Kulikuwa kumi integers, na kila mmoja wa wale ni ukubwa wa bits 4, au 32, hivyo nimekuwa waliopotea ka just 40 kwa sababu, kama wewe mapendekezo, mimi si kuitwa bure. Hiyo ni moja mdudu, na sasa hebu angalia chini kidogo zaidi na kuona ijayo na hii, "Batili kuandika ukubwa wa 4." Sasa ni nini hii? Anuani hii ni walionyesha nini msingi nukuu, inaonekana? Hii ni hexadesimoli, na wakati wowote unaweza kuona idadi kuanzia na 0x, maana hexadesimoli, ambayo sisi alifanya njia ya nyuma katika, nadhani, pset 0 wa sehemu ya maswali, ambayo ilikuwa tu kufanya zoezi warmup, kuwabadili decimal kwa hex kwa binary na kadhalika. Hexadesimoli, tu kwa mkataba wa binadamu, ni kawaida kutumika kuwakilisha kuyatumia au, kwa ujumla zaidi, anwani. Ni tu mkataba, kwa sababu ni rahisi kidogo kusoma, ni zaidi kidogo kuliko Compact kitu kama decimal, na kisha ni bure kwa ajili ya wengi binadamu kutumia. Hivyo sasa nini maana ya hii? Naam, inaonekana kama kuna kuandika batili ya ukubwa 4 kwenye mstari 21 ya memory.c. Basi hebu kwenda nyuma ya mstari 21, na kwa kweli, hapa ni kwamba kuandika batili. Hivyo Valgrind si kwenda kabisa kushikilia mkono wangu na kuniambia nini fix ni, lakini ni kuchunguza kwamba mimi nina kufanya kuandika batili. Mimi kugusa ka 4 kwamba nisiwe, na inaonekana kwamba kwa sababu, kama wewe alisema, mimi nina kufanya [10] badala ya [9] Upeo au [0] au kitu katika kati. Kwa Valgrind, kutambua wakati wowote wewe ni sasa kuandika mpango kwamba anatumia kuyatumia na anatumia kumbukumbu, na malloc zaidi hasa, dhahiri kupata katika tabia ya kuendesha kwa muda mrefu lakini kwa urahisi sana kunakiliwa na pasted amri ya Valgrind kuona kama kuna baadhi ya makosa katika huko. Na utakuwa ni balaa kila wakati unaweza kuona pato, lakini tu Hazrat kupitia kuibua wote wa pato na kuona kama unaweza kuona inataja wa makosa au maonyo au batili au kupotea. Yoyote maneno kwamba sauti kama wewe Star up mahali fulani. Hivyo kutambua kwamba ni chombo kipya katika toolkit yako. Sasa siku ya Jumatatu, tulikuwa na rundo zima la folks kuja hapa na kuwakilisha dhana ya orodha zinazoungwa. Na sisi ilianzisha orodha wanaohusishwa kama ufumbuzi wa tatizo nini? Yeah? [Mwanafunzi jibu, unintelligible] Good. Arrays hawezi kuwa na kumbukumbu aliongeza kwao. Kama wewe kutenga safu ya kawaida 10, kwamba ni yote wewe kupata. Unaweza kuita kazi kama realloc kama awali kuitwa malloc, na kwamba unaweza kujaribu kukua safu kama kuna nafasi kuelekea mwisho wa kwamba hakuna mtu mwingine ni kutumia, na kama kuna si, itakuwa tu kupata wewe chunk kubwa mahali pengine. Lakini basi itakuwa nakala yote ya ka wale katika safu mpya. Hii inaonekana kama ufumbuzi sahihi kabisa. Kwa nini hii ni unattractive? I mean ni kazi, binadamu kuwa wametatua tatizo hili. Kwa nini tunahitaji kutatua Jumatatu na orodha wanaohusishwa? Yeah? [Mwanafunzi jibu, unintelligible] Ni inaweza kuchukua muda mrefu. Kwa kweli, wakati wowote wewe ni wito malloc au realloc au calloc, ambayo bado mwingine mmoja, wakati wowote, mpango, ni kuzungumza na mfumo wa uendeshaji, wewe huwa na kupunguza mpango chini. Na kama wewe ni kufanya aina hii ya mambo katika tanzi, wewe ni kweli kupunguza mambo chini. Wewe hutaenda kwa taarifa hii kwa rahisi ya "hello dunia" programu aina, lakini katika mipango kubwa sana, kuuliza mfumo wa uendeshaji tena na tena kwa kumbukumbu au kutoa ni nyuma tena na tena huelekea si kwa kuwa ni jambo jema. Plus, ni tu aina ya kielimu - ni kupoteza kamili ya muda. Mbona kutenga zaidi na zaidi ya kumbukumbu, hatari kuiga kila kitu ndani ya safu mpya, kama una mbadala ambayo inakuwezesha kutenga tu kama kumbukumbu kubwa zaidi kama wewe kweli wanahitaji? Hivyo kuna pluses na minuses katika hapa. Moja ya pluses sasa ni kwamba tuna mabadiliko. Haijalishi ambapo chunks ya kumbukumbu ni kwamba ni bure, Naweza tu ya aina ya kujenga makombo haya mkate kupitia kuyatumia kwa kamba wanaohusishwa wangu wote orodha pamoja. Lakini mimi kulipa angalau moja ya bei. Nifanye uwachane katika kupata orodha wanaohusishwa? Yeah? [Mwanafunzi jibu, unintelligible] Good. Unahitaji kumbukumbu zaidi. Sasa mimi wanahitaji nafasi kwa kuyatumia haya, na katika kesi ya orodha hii super rahisi wanaohusishwa kwamba ni tu kujaribu kuhifadhi integers, ambayo ni 4 ka, sisi kuendelea kusema vizuri, pointer ni 4 ka, hivyo sasa nimepata literally mara mbili kiasi cha kumbukumbu nahitaji tu kuhifadhi orodha hii. Lakini tena, hii ni mara kwa mara katika tradeoff sayansi ya kompyuta kati ya muda na nafasi na maendeleo, juhudi na rasilimali nyingine. Nini mwingine upande wa chini ya kutumia orodha wanaohusishwa? Yeah? [Mwanafunzi jibu, unintelligible] Nzuri. Kama si rahisi kupata. Tunaweza tena kujiinua wiki kanuni 0 kama kugawanya na kushinda. Na hasa zaidi, binary tafuta. Kwa sababu hata kama sisi binadamu unaweza kuona takribani ambapo katikati ya orodha hii ni, kompyuta tu anajua kwamba hii orodha wanaohusishwa kuanza saa anuani kuitwa kwanza. Na kwamba 0x123 au kitu kama hicho. Na njia pekee ya mpango unaweza kupata kipengele katikati ni kweli kutafuta orodha nzima. Na hata basi, ni literally inapaswa kutafuta orodha nzima kwa sababu hata mara moja wewe kufikia katikati ya kipengele kwa kufuata kuyatumia, wewe, mpango, hawana wazo jinsi ya muda mrefu orodha hii ni, uwezekano, mpaka hit mwisho wake, na jinsi gani unajua programmatically kwamba uko katika mwisho wa orodha wanaohusishwa? Kuna maalum null pointer, hivyo tena, mkataba. Badala ya kutumia hii pointer, sisi dhahiri hawataki kuwa ni baadhi ya thamani ya takataka akizungumzia hatua mbali mahali fulani; sisi nataka kuwa mkono chini, null, hivyo kwamba tuna hii terminus katika muundo huu data hivyo tunajua ambapo ni mwisho. Nini kama tunataka kuendesha hii? Sisi gani zaidi ya huu kuibua, na kwa binadamu, lakini nini kama tunataka kufanya insertion? Hivyo orodha ya awali ilikuwa 9, 17, 20, 22, 29, 34. Nini kama sisi basi alitaka nafasi malloc kwa idadi 55, nodi kwa ajili yake, na kisha tunataka Insert 55 katika orodha tu kama tulivyofanya Jumatatu? Tutafanyaje hili? Naam, Anita alikuja na yeye kimsingi kutembea orodha. Alianza katika kipengele kwanza, kisha ya pili, pili, pili, pili, pili. Hatimaye hit mkono wa kushoto njia yote chini na barabara oh, hii ni null. Basi nini pointer ghiliba zinahitajika kufanyika? mtu ambaye alikuwa juu ya mwisho, idadi 34, zinahitajika mkono wake wa kushoto alimfufua kwa uhakika ya 55, 55 zinahitajika mkono wao wa kushoto akizungumzia chini kuwa mpya null Terminator. Done. Pretty rahisi Insert 55 katika orodha Iliyopangwa. Na jinsi inaweza hii kuangalia? Hebu kwenda mbele na kufungua baadhi mfano code hapa. Mimi itabidi kufungua gedit, na napenda kufungua files mbili kwanza. Moja ni list1.h, na napenda tu kuwakumbusha kwamba hii ilikuwa chunk ya maadili ya kwamba sisi kutumika kuwakilisha nodi. nodi ina wawili int kuitwa n na pointer iitwayo ijayo kwamba tu pointi kwa Kilichofuata katika orodha. Hiyo ni sasa katika faili h.. Kwa nini? Kuna mkataba huu, na sisi si kuchukuliwa kwa faida ya kiasi hiki kikubwa wenyewe, lakini mtu ambaye aliandika kazi printf na nyingine alitoa kama zawadi kwa ulimwengu wote wa kazi hizo kwa kuandika faili inayoitwa stdio.h. Na kisha kuna string.h, na kisha kuna map.h, na kuna files haya yote h kwamba unaweza kuwa na kuonekana au kutumika wakati wa muda imeandikwa na watu wengine. Kawaida katika wale h files. Ni mambo tu kama typedefs au maazimio ya aina desturi au maazimio ya constants. Huwezi kuweka utekelezaji kazi 'katika files header. Kuweka, badala yake, prototypes tu wao. Wewe kuweka mambo unataka kushiriki na duniani wanahitaji nini ili kukusanya kanuni zao. Hivyo tu kwa kuingia katika tabia hii, tuliamua kufanya kitu kimoja. Kuna si sana katika list1.h, lakini tumekuwa kuweka kitu ambayo inaweza kuwa ya manufaa kwa watu katika ulimwengu ambao wanataka kutumia orodha yetu zilizounganishwa utekelezaji. Sasa, katika list1.c, mimi si kwenda kwa jambo hili zima kwa sababu ni kidogo kwa muda mrefu, programu hii, lakini hebu kukimbia kweli haraka katika haraka. Hebu kukusanya list1, napenda kisha kukimbia list1, na kile utaona ni tumekuwa simulated rahisi kidogo mpango hapa ambayo inaenda naomba kuongeza na kuondoa idadi ya orodha. Hivyo basi mimi kwenda mbele na aina 3 kwa 3 chaguo menu. Mimi nataka kuingiza idadi - wacha kufanya idadi ya kwanza, ambayo ilikuwa 9, na sasa mimi nina aliiambia orodha ni sasa 9. Hebu kwenda mbele na kufanya mwingine insertion, hivyo mimi hit menu chaguo 3. Nini idadi mimi nataka Insert? 17. Kuingia. Na mimi itabidi kufanya moja tu zaidi. Hebu Insert namba 22. Hivyo tuna mwanzo wa orodha wanaohusishwa kwamba tulikuwa katika fomu slide wakati iliyopita. Jinsi ni insertion hii kwa kweli yanatokea? Hakika, 22 ni sasa mwisho wa orodha. Hivyo hadithi tunaambiwa juu ya hatua ya juu ya Jumatatu na recapped tu sasa lazima kweli kuwa kinachotokea katika code. Hebu tuangalie. Hebu kitabu chini katika faili hii. Tutaweza Gloss juu ya baadhi ya kazi, lakini tutaweza kwenda chini, wanasema, kazi Insert. Hebu angalia jinsi sisi kwenda juu ya inserting nodi mpya katika orodha hii zinazoungwa. Ambapo ni orodha alitangaza? Naam, hebu kitabu njia yote hadi saa ya juu, na taarifa kwamba orodha yangu wanaohusishwa ni kimsingi alitangaza kama pointer moja kwamba awali null. Basi, mimi nina kutumia variable kimataifa hapa, ambayo kwa ujumla tumekuwa alihubiri dhidi ya kwa sababu inafanya code yako messy kidogo ili kudumisha, ni aina ya wavivu, kwa kawaida, lakini si wavivu na si vibaya na si mbaya kama mpango wako lengo pekee katika maisha ni kuiga moja zilizounganishwa orodha. Ambayo ni sawa kabisa sisi ni kufanya. Hivyo badala ya kutangaza hii katika kuu na kisha kuwa na kupita kwa kila kazi tumekuwa yaliyoandikwa katika mpango huu, sisi badala kutambua oh, hebu tu kufanya hivyo kimataifa sababu lengo zima la mpango huu ni kuonyesha moja na moja tu wanaohusishwa orodha. Hivyo kwamba anahisi sawa. Hapa ni prototypes wangu, na sisi si kwenda kwa yote haya, lakini mimi aliandika kazi ya kufuta, kazi kupata, kazi Insert, na kazi tindanga. Lakini hebu sasa kwenda nyuma chini na kazi Insert na kuona jinsi hii moja kazi hapa. Insert ni juu ya mstari - hapa sisi kwenda. Ingiza. Hivyo haina kuchukua hoja yoyote, kwa sababu sisi ni kwenda kuuliza ndani ya mtumiaji wa kazi hii kwa idadi wanataka Insert. Lakini kwanza, sisi kujiandaa ili kuwapa baadhi ya nafasi. Hii ni aina ya nakala na kuweka mfano kutoka nyingine. Katika kesi hiyo, tulikuwa kugawa int; wakati huu tuko kugawa nodi. Mimi si kweli kumbuka jinsi wengi ka nodi ni, lakini hiyo ni nzuri. Sizeof wanaweza kufikiri kuwa nje kwa ajili yangu. Na kwa nini mimi kuangalia kwa null katika mstari 120? Je, inaweza kwenda vibaya katika mstari 119? Yeah? [Mwanafunzi jibu, unintelligible] Nzuri. Tu inaweza kuwa kesi kwamba nimepata aliuliza kwa kumbukumbu sana au kitu vibaya na mfumo wa uendeshaji haina ka kutosha kutoa yangu, hivyo ni ishara sana kwa kurudi null, na kama si kuangalia kwa kuwa na mimi tu upofu kuendelea kutumia anuani wakarudi, inaweza kuwa null. Ni inaweza kuwa baadhi ya thamani haijulikani; si jambo zuri isipokuwa mimi - kweli si kuwa thamani haijulikani. Ni inaweza kuwa null, hivyo sitaki dhuluma hiyo na kuhatarisha dereferencing yake. Kama kwamba hutokea, mimi tu kurudi na tutaweza kujifanya kama sikuweza kupata nyuma yoyote kumbukumbu wakati wote. Vinginevyo, mimi kuwaambia mtumiaji nipe namba Insert, mimi kuwaita rafiki yetu ya zamani GetInt, na kisha hii ilikuwa syntax mpya sisi ilianzisha Jumatatu. 'Newptr-> n' ina maana kuchukua anuani kwamba walipewa kwa malloc ambayo inawakilisha Byte kwanza ya kitu mpya wa nodi, na kisha kwenda shamba iitwayo n. kidogo trivia swali: Hii ni sawa na mstari nini zaidi cryptic ya maadili? Jinsi mwingine inaweza nimeandika hii? Wanataka kuchukua kumchoma? [Mwanafunzi jibu, unintelligible] Nzuri. Kutumia n., Lakini siyo kabisa kama rahisi kama hii. Nifanye kwanza haja ya kufanya? [Mwanafunzi jibu, unintelligible] Nzuri. Mimi haja ya kufanya * newptr.n. Hivyo hii ni kusema pointer mpya ni wazi anuani. Kwa nini? Sababu ilikuwa akarudi na malloc. Newptr * akisema "kwenda huko," na kisha mara moja uko pale, basi unaweza kutumia zaidi ya ukoo n., lakini hii tu inaonekana kidogo ugly, hasa kama sisi binadamu ni kwenda kuteka kuyatumia kwa mishale wakati wote; dunia ina sanifu kwenye nukuu hii mshale, ambayo haina hasa kitu kimoja. Hivyo matumizi tu -> nukuu wakati kitu upande wa kushoto ni pointer. Vinginevyo, kama ni struct halisi, matumizi n.. Na kisha hii: Kwa nini mimi initialize newptr-> ijayo null? Hatutaki dangling kushoto mbali ya mwisho ya hatua. Tunataka hiyo unaelekea chini, ambayo ina maana ya mwisho wa orodha hii inaweza uwezekano wa kuwa kwenye nodi hii, hivyo sisi ni bora kuhakikisha kuwa ni null. Na, kwa ujumla, initializing vigezo au data yako wanachama na structs kwa kitu ni mazoezi mazuri. Just kuruhusu takataka kuwepo na kuendelea kuwepo kwa ujumla anapata shida katika kama wewe kusahau kufanya kitu baadaye. Hapa ni kesi chache. Hii, tena, ni kazi Insert, na jambo la kwanza mimi kuangalia kwa ni kama variable iitwayo ya kwanza, kwamba variable kimataifa ni null, kwamba maana hakuna orodha zinazoungwa. Sisi si kuingizwa idadi yoyote, hivyo ni trivial kuingiza idadi hii ya sasa katika orodha, kwa sababu tu ni wakati wa kuanza kwa orodha. Hivyo hii ilikuwa wakati Anita mara tu alisimama hapa peke yake, akijifanya hakuna mtu mwingine alikuwa hapa juu ya hatua mpaka sisi zilizotengwa nodi, kisha aliweza kunyanyua mkono wake kwa mara ya kwanza, kama kila mtu mwingine waliokuja juu ya hatua baada yake juu ya Jumatatu. Sasa hapa, hii ni hundi kidogo ambapo mimi kusema kama thamani ya nodi ya mwezi wa n ni ijayo, kwamba maana ya kwenda struct kwamba ni kuwa alisema katika na newptr, hivyo hapa sisi ni, kwenda huko. Kisha mshale ni kusema kupata shamba ijayo, na kisha = ni kusema kuweka thamani gani huko? thamani hiyo ilikuwa katika kwanza; thamani gani ilikuwa katika kwanza? Kwanza alikuwa akizungumzia nodi katika hili, hivyo kwamba maana hii lazima sasa kumweka kwenye nodi hii. Kwa maneno mengine, kile inaonekana angalau fujo ridiculous kwa mwandiko wangu, nini wazo rahisi ya kusonga tu mishale hizi karibu tafsiri ya kificho na mjengo tu hii moja. Hifadhi ni nini katika kwanza katika uwanja ijayo na kisha update nini kwanza kweli ni. Hebu kwenda mbele na kufunga-mbele kupitia baadhi ya hii, na kuangalia tu katika insertion hii mkia kwa sasa. Tuseme mimi kupata kwa uhakika ambapo mimi kupata kwamba shamba ya pili ya nodi baadhi ni null. Na katika hatua hii ya hadithi, undani kwamba mimi nina glossing juu ya ni kwamba nimepata ilianzisha mwingine pointer hapa juu katika mstari 142, mtangulizi pointer. Kimsingi, katika hatua hii ya hadithi, mara moja orodha anapata muda mrefu, Mimi aina ya haja ya kutembea kwa vidole viwili kwa sababu kama mimi kwenda mbali mno, kumbuka katika orodha moja-urefu, huwezi kurudi nyuma. Hivyo hii ni wazo la predptr kidole wangu wa kushoto, na newptr - si newptr. Mwingine pointer kwamba hapa ni kidole yangu nyingine, na mimi nina aina tu ya kutembea orodha. Hiyo ndiyo sababu kwamba ipo. Lakini hebu fikiria tu moja ya kesi rahisi hapa. Kama kwamba pointer wa shamba la pili ni null, nini maana mantiki? Kama wewe ni traversing orodha hii na wewe hit pointer null? Wewe ni mwisho wa orodha, na hivyo kanuni na kisha append hii moja ya ziada ya kipengele ni aina ya Intuitive itachukua kwamba nodi ambaye ijayo pointer ni null, hivyo hii sasa ni null, na mabadiliko hayo, ingawa, kwa kuwa na anwani ya node mpya. Hivyo sisi ni tu kuchora katika code mshale tulianzisha juu ya hatua kwa kuongeza mtu mkono wa kushoto. Na kesi ya kwamba mimi itabidi kukitikisa mikono yangu katika kwa sasa, tu kwa sababu nadhani ni rahisi kupata waliopotea wakati sisi kufanya hivyo katika hii aina ya mazingira, ni kuangalia kwa Infogande katika orodha ya katikati. Lakini tu intuitively, nini mahitaji ya kutokea kama unataka kufikiri ambapo idadi baadhi ni katikati ni una kutembea ni kwa kidole zaidi ya moja, zaidi ya moja pointer, takwimu nje ambapo ni kwa kuangalia ni kipengele Moja ya sasa, na mara moja kupata kwamba mahali, basi una kufanya aina hii ya mchezo shell ambapo wewe hoja kuyatumia kuzunguka kwa makini sana. Na kwamba jibu, kama Ningependa kwa sababu kwa njia hii nyumbani juu yako mwenyewe, majipu chini tu kwa mistari hii miwili ya kificho, lakini utaratibu wa wale mistari ni super muhimu. Kwa sababu kama wewe kuacha mkono wa mtu na kuongeza mtu mwingine ili makosa, tena, unaweza kuishia orphaning orodha. Kwa muhtasari zaidi conceptually, insertion katika mkia ni rahisi. insertion katika kichwa pia ni kiasi moja kwa moja, lakini unahitaji update pointer ziada wakati huu itapunguza idadi 5 katika orodha hapa, na kisha kuingizwa katika katikati inahusisha hata zaidi juhudi, kwa makini sana kuingiza idadi 20 katika eneo lake sahihi, ambayo ni kati ya 17 na 22. Hivyo haja ya kufanya kitu kama kuwa mwezi nodi 20 uhakika na 22, na kisha, pointer ambayo nodi ya mahitaji ya kuwa updated mara ya mwisho? Ni 17, kwa kweli kuingiza. Hivyo tena, mimi itabidi kuahirisha code halisi kwa ajili ya utekelezaji huo. Kwa mtazamo wa kwanza, ni kidogo mno, lakini ni kweli tu kitanzi usio hiyo looping, looping, looping, looping, na kuvunja haraka kama wewe hit pointer null, ambapo kiwango unaweza kufanya insertion zinazohitajika. Hii basi, ni mwakilishi wanaohusishwa orodha insertion code. Hiyo ilikuwa ni aina ya mengi, na anahisi kama tumekuwa kutatuliwa tatizo moja, lakini tumekuwa ilianzisha mzima nyingine moja. Kusema ukweli, tumekuwa alitumia muda wote huu juu ya kubwa O na Ω na mbio wakati, kujaribu kutatua matatizo ya haraka zaidi, na hapa sisi ni kuchukua hatua kubwa nyuma, anahisi. Na bado, kama lengo ni kuhifadhi data, anahisi kama Grail Mtakatifu, kama sisi alisema Jumatatu, ingekuwa kweli kuwa kuhifadhi vitu instantly. Kwa kweli, tuseme kwamba sisi tulikuwa kuweka kando wanaohusishwa orodha kwa muda na sisi badala ilianzisha dhana ya meza. Na hebu tu kufikiri ya meza kwa muda kama safu. Hii safu na kesi hii hapa ina baadhi ya vipengele 26, 0 kupitia 25, na kudhani kwamba zinahitajika baadhi chunk ya hifadhi kwa ajili ya majina: Alice na Bob na Charlie na kama. Na unahitaji baadhi muundo data kuhifadhi majina hayo. Naam, unaweza kutumia kitu kama orodha wanaohusishwa na unaweza kutembea orodha inserting Alice kabla Bob na Charlie baada ya Bob na kadhalika. Na, kwa kweli, kama unataka kuona kanuni kama kwamba kama kando, kujua kwamba katika list2.h, sisi kufanya hasa kwamba. Sisi si kwenda kwa njia ya kanuni hii, lakini hii ni lahaja ya mfano wa kwanza kwamba utangulizi moja nyingine struct tumeona kabla mwanafunzi kinachoitwa, na kisha nini ni kweli maduka katika orodha zilizounganishwa ni pointer muundo mwanafunzi badala ya rahisi kidogo integer, n. Hivyo kutambua kuna code kuna ambayo inahusisha masharti halisi, lakini kama lengo katika mkono kweli sasa ni kushughulikia tatizo ufanisi, bila kuwa nzuri kama sisi ni kupewa kitu inayoitwa Alice, tunataka kuweka wake katika mahali sahihi katika muundo data, anahisi kama ni d kuwa nzuri kwa kweli kuweka tu Alice, ambaye jina lake huanza na, katika mahali ya kwanza. Na Bob, ambaye jina lake huanza na B, katika eneo la pili. Na safu, au hebu kuanza kuiita meza, meza hash saa kwamba, tunaweza kufanya hasa ile. Kama sisi ni kupewa jina kama Alice, kamba kama Alice, wapi kuweka-l-i-c-e? Tunahitaji hueristic. Tunahitaji kazi ya kuchukua baadhi ya pembejeo kama Alice na kuwajibu, "Rudisha Alice katika eneo hili." Na kazi hii, hii sanduku nyeusi, ni kwenda kuitwa kazi hash. kazi hash ni kitu kwamba inachukua pembejeo, kama "Alice", na anarudi kwa wewe, kawaida, eneo numeric katika muundo baadhi data ambapo Alice ni mwanachama. Katika kesi hiyo, kazi yetu hash lazima rahisi kiasi. Kazi yetu hash lazima kusema, ikiwa wewe ni kupewa "Alice", ambayo tabia shugulike juu? moja ya kwanza. Hivyo mimi kuangalia [0], na kisha mimi kusema kama [0] tabia ni, kurudi idadi 0. Kama ni B, kurudi 1. Kama C ni, kurudi 2, na kadhalika. Yote index 0, na kwamba ingekuwa naomba Insert Alice na kisha Bob na kisha Charlie na kadhalika ndani ya muundo huu data. Lakini kuna tatizo. Nini kama Anita huja pamoja tena? Wapi sisi kuweka Anita? Jina lake, pia, huanza na barua, na anahisi kama tumekuwa alifanya fujo hata kubwa ya tatizo hili. Sisi sasa kuwa insertion haraka, mara kwa mara wakati insertion, katika muundo wa data badala ya mbaya ya kesi linear, lakini nini tunaweza kufanya na Anita katika kesi hii? Je, ni chaguzi mbili, kweli? Yeah? [Mwanafunzi jibu, unintelligible] Sawa, hivyo tunaweza kuwa na mwingine mwelekeo. Hiyo ni nzuri. Hivyo tunaweza kujenga mambo ya nje katika 3D kama kuongelea maneno Jumatatu. Tunaweza kuongeza upatikanaji mwingine hapa, lakini tuseme kwamba hakuna, mimi nina kujaribu kuweka hii rahisi. Lengo zima hapa ni kuwa na haraka ya mara kwa mara-wakati upatikanaji, hivyo hiyo ni kuongeza sana utata. Je, ni chaguzi nyingine wakati akijaribu Insert Anita ndani ya muundo huu data? Yeah? [Mwanafunzi jibu, unintelligible] Good. Hivyo sisi inaweza hoja kila mtu mwingine chini, kama Charlie nudges chini Bob na Alice, na kisha sisi kuweka Anita ambapo yeye kweli anataka kuwa. Bila shaka, sasa, kuna athari ya hili. Hii muundo data pengine ni muhimu si kwa sababu tunataka Insert watu mara moja lakini kwa sababu tunataka kuangalia kama uko huko baadaye kama tunataka magazeti nje yote ya majina katika muundo data. Sisi ni kwenda kufanya kitu kwa data hii hatimaye. Hivyo sasa tumekuwa aina ya Star zaidi ya Alice, ambaye tena ambapo yeye walidhani kuwa. Wala Bob, wala Charlie. Hivyo labda hii si wazo nzuri. Lakini kwa kweli, hii ni chaguo moja. Tunaweza kuhama kila mtu chini, au heck, Anita alikuja marehemu kwa mchezo, kwa nini sio sisi tu ya kuweka Anita si hapa, si hapa, si hapa, hebu tu kuweka wake mdogo punde katika orodha. Lakini basi tatizo hili kuanza kukabidhi tena. Unaweza kuwa na uwezo wa kupata Alice instantly, kwa kuzingatia jina yake ya kwanza. Na Bob instantly, na Charlie. Lakini basi ukiangalia kwa Anita, na unaweza kuona, hmm, Alice ni katika njia. Vizuri, basi mimi kuangalia chini Alice. Bob si Anita. Charlie si Anita. Oh, kuna Anita. Na kama wewe kuendelea kuwa treni ya mantiki njia yote, nini mbaya zaidi kesi mbio wakati wa kutafuta au inserting Anita ndani ya muundo huu mpya data? Ni O (n), sawa? Kwa sababu katika hali mbaya, kuna Alice, Bob, Charlie. . . njia yote chini kwa mtu aitwaye "Y", hivyo kuna mmoja tu doa kushoto. Nashiriki, hatuna moja inayoitwa "Z", hivyo sisi kuweka Anita chini sana. Sisi si kweli kwamba tatizo kutatuliwa. Hivyo labda hatuna haja ya kuanzisha hii dimension ya tatu. Na zinageuka, kama hatuwezi kuanzisha hii mwelekeo wa tatu, hatuwezi kufanya hii kikamilifu, lakini Grail Mtakatifu anaenda kuwa kupata mara kwa mara-wakati insertion na insertions nguvu ili hatuna kwa bidii-code safu ya ukubwa 26. Tunaweza Insert kama majina mengi kama tunataka, lakini hebu wetu 5-dakika kuvunja hapa na kisha kufanya hivyo vizuri. Wote haki. Mimi kuweka hadithi juu pretty artificially kuna kwa kuchagua Alice na kisha Bob na kisha Charlie na kisha Anita, ambaye jina lake ni wazi anaenda yanapogongana na Alice. Lakini swali sisi kumalizika Jumatatu na ni jinsi tu kinachowezekana ni kwamba ungependa kupata aina hii ya collisions? Kwa maneno mengine, kama tunataka kuanza kutumia mfumo huu tabular, ambayo ni kweli tu safu, katika kesi hii ya maeneo 26, nini kama pembejeo zetu badala enhetligt kusambazwa? Ni si artificially Alice na Bob na Charlie na Daudi na kadhalika alphabetically, ni enhetligt kusambazwa juu ya njia ya Z. Labda tutaweza tu kupata bahati na sisi siyo kwenda kuwa na mbili au mbili B na uwezekano juu sana, lakini kama kuna mtu alisema, kama sisi jumla na tatizo hili na si kufanya 0-25 lakini, sema, 0 kupitia 364 au 65, mara nyingi idadi ya siku katika mwaka wa kawaida, na aliuliza swali, "Nini uwezekano kwamba sisi wawili katika chumba hiki na kuzaliwa sawa?" Kuweka njia nyingine, nini uwezekano kwamba mbili ya sisi kuwa na jina kwa kuanzia na? aina ya swali ni sawa, lakini nafasi hii anuani, nafasi hii tafuta, ni kubwa katika kesi ya siku za kuzaliwa, sababu tuna mengi zaidi ya siku katika mwaka kuliko barua katika alfabeti. Nini uwezekano wa mgongano? Naam, tunaweza kufikiria hili kwa kuhesabia math njia ya kinyume. Nini uwezekano wa migongano hakuna? Naam, hii kujieleza hapa anasema kwamba nini uwezekano kama kuna mtu mmoja tu katika chumba hiki, kwamba wana kuzaliwa kipekee? Ni 100%. Kwa sababu kama kuna mtu mmoja tu katika chumba, yake au siku ya kuzaliwa inaweza kuwa yoyote ya siku 365 kati ya mwaka. Hivyo 365/365 chaguzi anitiaye thamani ya 1. Hivyo uwezekano katika swali kwa sasa ni 1 tu. Lakini kama kuna mtu wa pili katika chumba, nini uwezekano kwamba kuzaliwa kwao ni tofauti? Kuna tu 364 iwezekanavyo siku, kupuuza leap miaka, kwa siku ya kuzaliwa yao si kwa yanapogongana na watu wengine. Hivyo 364/365. Kama mtu wa tatu unakuja, ni 363/365, na kadhalika. Hivyo sisi kuweka kuzidisha pamoja FRACTIONS haya, ambayo ni kupata na ndogo ndogo, kufikiri nini ni uwezekano kwamba sisi sote tuna kuzaliwa kipekee? Lakini basi tunaweza, bila shaka, kuchukua tu kwamba jibu na flip ni kuzunguka na kufanya 1 bala yote ya kwamba, ya kujieleza tutaweza hatimaye kupata kama wewe kumbuka nyuma ya vitabu yako math, inaonekana kitu kidogo kama hii, ambao ni muhimu sana kwa urahisi zaidi kufasiriwa graphically. Na hii graphic hapa ana kwenye mhimili x idadi ya siku za kuzaliwa, au idadi ya watu na siku za kuzaliwa, na kwenye mhimili y ni uwezekano wa mechi. Na nini hii ni kusema ni kwamba kama una, hebu sema, hata, hebu kuchagua kitu kama 22, 23. Kama kuna 22 au 23 watu katika chumba, uwezekano kwamba mbili ya wale watu wachache sana wanaenda kuwa na siku ya kuzaliwa sawa ni kweli super juu, combinatorially. 50% ya tabia mbaya kwamba katika darasa la watu 22 tu, semina, kivitendo, 2 ya watu wale ni kwenda na siku ya kuzaliwa sawa. Kwa sababu kuna njia nyingi ambazo unaweza kuwa na siku ya kuzaliwa sawa. Hata mbaya, kama ukiangalia katika upande wa kulia ya chati, na wakati una darasa na wanafunzi 58 katika hilo, uwezekano wa watu 2 ya kuwa siku ya kuzaliwa ni super, super juu, karibu asilimia 100%. Sasa, hiyo ni aina ya ukweli kuhusu fun maisha halisi. Lakini matokeo, sasa, kwa data miundo na hifadhi habari ina maana kwamba tu kuchukua una nzuri, safi, sare usambazaji wa data na una kubwa ya kutosha safu walionao rundo la vitu haina maana wewe ni kwenda kupata watu katika maeneo ya kipekee. Wewe utaenda kuwa na migongano. Hivyo wazo hili la hashing, kama ni kuitwa, kuchukua pembejeo kama "Alice" na massaging ni katika baadhi ya njia na kisha kupata nyuma jibu kama 0 au 1 au 2. Kupata nyuma baadhi ya pato kutoka kazi ambayo yanakabiliwa na uwezekano wa mgongano huu. Hivyo ni jinsi gani tunaweza kushughulikia migongano hizo? Naam, katika kesi moja, tunaweza kuchukua wazo kwamba ilipendekezwa. Tunaweza tu kuhama kila mtu chini, au labda zaidi kidogo tu, badala ya hoja ya mtu mwingine, hebu tu hoja Anita kwa chini ya doa inapatikana. Hivyo kama ni Alice katika 0, Bob ni katika 1, Charlie ni katika 2, tutaweza tu kuweka Anita katika eneo 3. Na hii ni mbinu katika miundo data kuitwa linear probing. Linear sababu wewe tu kutembea line hii, na wewe ni aina ya uchunguzi kwa matangazo inapatikana katika muundo data. Bila shaka, hii warithi katika O (n). Kama muundo data kweli kamili, kuna watu 25 ndani yake tayari, na kisha Anita huja pamoja, yeye kuishia katika nini itakuwa mahali Z, na hiyo ni faini. Yeye bado inafaa, na tunaweza kupata wake baadaye. Lakini hii ilikuwa kinyume na lengo la kuongeza kasi ya mambo juu. Basi nini kama sisi badala ilianzisha hii dimension ya tatu? Hiyo ni kwa ujumla mbinu kuitwa tofauti chaining, au kuwa na minyororo. Na nini meza hash sasa ni, muundo huu tabular, meza yako ni safu ya kuyatumia. Lakini nini wale kuyatumia uhakika na ni nadhani nini? orodha zinazoungwa. Basi nini kama sisi kuchukua bora wa wote wa dunia hizi? Sisi kutumia arrays kwa bahati ya awali ndani ya muundo wa data ili tuweze instantly kwenda kwenye [0] [1], [30] au kadhalika, lakini hivyo kwamba tuna baadhi kubadilika na tunaweza fit Anita na Alice na Adam na nyingine yoyote ya jina, sisi badala basi mhimili nyingine kukua kiholela. Na sisi hatimaye, kama ya Jumatatu, na kwamba uwezo expressive na orodha zilizounganishwa. Tunaweza kukua muundo data kiholela. Vinginevyo, tunaweza tu kufanya kubwa 2-dimensional safu, lakini kwamba itakuja kuwa hali ya kutisha kama moja ya mistari katika safu 2-dimensional si kubwa ya kutosha kwa ajili ya mtu ziada ambaye jina kinachotokea kwa kuanza na A. Mungu apishe tuna reallocate kubwa 2-dimensional muundo tu kwa sababu kuna watu wengi hivyo jina lake, hasa wakati kuna watu wachache aitwaye Z kitu. Ni tu kwenda sana sparse data muundo. Hivyo si kamilifu kwa njia yoyote, lakini sasa sisi angalau kuwa na uwezo instantly kupata ambapo Alice au Anita ni, angalau katika suala la mhimili wima, na kisha sisi tu kuamua wapi kuweka Anita au Alice katika orodha hii zinazoungwa. Kama sisi hawajali kuhusu kuchagua mambo, jinsi ya haraka tunaweza kuingiza Alice katika muundo kama hii? Ni mara kwa mara wakati. Sisi index katika [0], na kama hakuna mtu huko, Alice huenda mwanzo wa orodha hiyo zinazoungwa. Lakini si kwamba mpango mkubwa. Kwa sababu kama Anita kisha huja pamoja baadhi Idadi ya hatua ya baadaye, ambapo gani Anita ni mali? Naam, [0]. OOP. Alice ni tayari katika orodha ya kuwa wanaohusishwa. Lakini kama sisi hawajali kuhusu kuchagua majina haya, tunaweza tu hoja juu ya Alice, Insert Anita, lakini hata hilo ni mara kwa mara wakati. Hata kama kuna Alice na Adamu na mengine yote haya majina, siyo kweli shifting yao kimwili. Kwa nini? Kwa sababu sisi tu alifanya hapa kwa orodha wanaohusishwa, ambaye anajua walikuwa hawa nodes ni anyway? Wote una kufanya ni hoja makombo chakula. Hoja ya mishale kote; huna kimwili hoja data yoyote duniani. Hivyo tunaweza kuingiza Anita, katika kesi hiyo, instantly. Mara kwa mara wakati. Hivyo tuna mara kwa mara-wakati Luke, na mara kwa mara-wakati insertion ya mtu kama Anita. Lakini aina ya oversimplifying dunia. Nini kama sisi baadaye unataka kupata Alice? Nini kama sisi baadaye unataka kupata Alice? Jinsi hatua nyingi ni kwamba kwenda kuchukua? [Mwanafunzi jibu, unintelligible] Hasa. idadi ya watu kabla ya Alice katika orodha zinazoungwa. Hivyo si kabisa kamilifu, kwa sababu data muundo wetu, tena, ana hili upatikanaji wima na basi ina orodha hizi zilizounganishwa kunyongwa - kweli, basi si kuteka ni safu. Ni haya orodha wanaohusishwa kunyongwa mbali ya hiyo kwamba inaonekana kitu kidogo kama hii. Lakini tatizo ni kama Alice na Adamu na mengine yote haya majina kuishia zaidi na zaidi zaidi ya hapo, kutafuta mtu unaweza kuishia kuchukua rundo la hatua, bcause una traverse orodha zilizounganishwa, ambayo ni operesheni linear. Hivyo kweli, basi, wakati insertion hatimaye ni O (n), ambapo n ni idadi ya vipengele katika orodha. Kugawanywa na, hebu kiholela kuiita m, ambapo m ni idadi ya orodha zilizounganishwa kwamba sisi katika mhimili huu wima. Kwa maneno mengine, kama kweli sisi kudhani usambazaji sare ya majina, kabisa unrealistic. Kuna wazi zaidi ya barua baadhi kuliko wengine. Lakini kama tunasadiki kwa sasa usambazaji sare, na tuna n watu jumla, na m minyororo jumla inapatikana kwa sisi, basi urefu wa kila minyororo ya haya uungwana tu ni kwenda kuwa jumla, n kugawanyika kwa idadi ya minyororo. Hivyo n / m. Lakini hapa ni mahali ambapo tunaweza wote mathematically wajanja. m ni mara kwa mara, kwa sababu kuna idadi maalum ya haya. Utaenda kutangaza safu yako katika mwanzo, na sisi siyo resizing mhimili wima. Kwa ufafanuzi, kwamba anakaa fasta. Ni tu mhimili usawa, hivyo kusema, kwamba ni kubadilika. Basi kitaalam, hii ni mara kwa mara. Hivyo sasa, wakati insertion ni kiasi pretty O (n). Hivyo kwamba hana kujisikia wote kuwa bora zaidi. Lakini nini ni ukweli hapa? Naam, muda wote huu, kwa wiki, tumekuwa akisema O (n ²). O (n), 2 x n ², - n, kugawanywa na 2. . . ech. Ni tu n ². Lakini sasa, katika sehemu hii ya muhula, tunaweza kuanza kuzungumza juu ya ulimwengu halisi tena. Na n / m kabisa kwa kasi zaidi kuliko tu n peke yake. Kama una majina elfu, na wewe kuvunja yao juu katika ndoo nyingi ili una kumi tu ya majina katika kila moja ya minyororo ya haya, kabisa kutafuta mambo kumi ni kwenda kuwa kasi zaidi kuliko mambo elfu. Na hivyo moja ya seti ujao tatizo ni kwenda changamoto kufikiri kuhusu hasa kwamba hata ingawa, yeah, asymptotically na kihisabati, hii bado tu linear, ambayo sucks kwa ujumla wakati akijaribu kupata mambo. Katika hali halisi, ni kwenda kuwa kasi zaidi kuliko kuwa sababu ya kigawanyo hii. Na hivyo kuna tena kwenda kuwa hii biashara-off na mgogoro huu kati ya nadharia na ukweli, na moja ya knobs kuanza kugeuka katika hatua hii katika muhula ni zaidi ya ukweli moja kama sisi aina ya kujiandaa kwa ajili ya mwisho wa semster, kama sisi kuanzisha ulimwengu wa programu ya mtandao, ambapo kwa kweli, utendaji ni kwenda kuhesabu kwa sababu watumiaji wako ni kwenda kuanza kuhisi na kufahamu design maamuzi maskini. Hivyo ni jinsi gani wewe kwenda juu ya utekelezaji zilizounganishwa - hash meza na vipengele 31? Na mfano uliopita ilikuwa kiholela kuhusu siku za kuzaliwa. Kama mtu ana siku ya kuzaliwa ya Januari 1 au Februari 1, tutaweza kuwaweka katika ndoo hii. Kama ni ya Januari 2, 2 Februari, Machi 2, tutaweza kuwaweka katika ndoo hii. Hiyo ndiyo ilikuwa 31. Jinsi gani unaweza kutangaza meza hash? Inaweza kuwa pretty rahisi, nodi * meza ni jina langu holela kwa ajili yake, [31]. Hii inanipa kuyatumia 31 kwa nodes, na kwamba inaruhusu yangu kuwa kuyatumia 31 kwa orodha wanaohusishwa hata kama wale minyororo ni awali null. Nini nataka kuweka kama nataka kuhifadhi "Alice," "Bob," "Charlie"? Naam, tunahitaji wrap mambo hayo katika muundo sababu tunahitaji Alice kwa uhakika na Bob, kwa uhakika na Charlie, na kadhalika. Hatuwezi tu majina peke yake, ili niweze kujenga muundo mpya iitwayo nodi hapa. Nini ni nodi halisi? Nini ni nodi katika orodha hii mpya wanaohusishwa? Jambo la kwanza, iitwayo neno, ni kwa jina la mtu. LENGTH, labda, inahusiana na upeo wa urefu wa jina binadamu, chochote kile, 20, 30, 40 wahusika katika kesi mambo kona, na 1 ni kwa nini? Ni tu ni ziada null tabia, \ 0. Hivyo nodi hii wrapping "kitu" ndani ya yenyewe, lakini pia inatangaza pointer iitwayo ijayo ili tuweze mnyororo Alice kwa Bob kwa Charlie na kadhalika. Inaweza kuwa null lakini siyo lazima kuwa. Maswali yoyote juu ya mbao hizo hash? Yeah? [Mwanafunzi kuuliza swali, unintelligible] safu - nzuri swali. Kwa nini hii ni neno Char katika safu badala tu ya Char *? Katika mfano huu kwa kiasi fulani holela, mimi sitaki kuwa na kuamua kwa malloc kwa kila moja ya majina ya awali. Nilitaka kutangaza kiasi cha upeo wa kumbukumbu kwa kamba ili niweze nakala katika muundo Alice \ 0 na si kuwa na kushughulika na malloc na bure na kama. Lakini mimi naweza kufanya kwamba kama nilitaka kuwa zaidi ufahamu wa matumizi ya nafasi. Nzuri swali. Basi hebu jaribu kujumlisha mbali haya na kuzingatia salio ya leo kwenye miundo ya data zaidi kwa ujumla na matatizo mengine ya kwamba tunaweza kutatua kutumia misingi sawa ingawa miundo data wenyewe ili tofauti katika maelezo yao. Hivyo zinageuka katika sayansi ya kompyuta, miti ni ya kawaida sana. Na unaweza kufikiria aina ya mti kama mti wa familia, ambapo kuna baadhi ya mizizi, baadhi matriarch au dume, bibi au babu au mapema nyuma, zipitazo ni mama na baba au ndugu mbalimbali au kama. Hivyo muundo mti ina nodes na ana watoto, kawaida 0 au zaidi ya watoto kwa kila node. Na baadhi ya jargon kwamba unaweza kuona katika picha hii hapa ni mojawapo ya watoto wadogo au grandkids pembeni ambao wana mishale hakuna vikiwemo kutoka kwao, wale ni majani kinachojulikana, na mtu yeyote juu ya ndani ya ni nodi ndani; unaweza kuiita chochote pamoja wale mistari. Lakini muundo huu ni pretty kawaida. Hii moja ni kidogo kiholela. Tuna mtoto mmoja upande wa kushoto, tuna watoto watatu juu ya haki, watoto wawili juu ya chini kushoto. Ili tuweze kuwa na miti mbalimbali ya ukubwa, lakini kama sisi kuanza kwa standardize mambo, na unaweza kukumbuka hii kutoka video Patrick juu tafuta binary kutoka mfupi uliopita online, tafuta binary haina kutekelezwa na safu au vipande vya karatasi juu ya ubao. Tuseme kwamba ulitaka kuhifadhi nambari yako katika muundo kisasa zaidi data. Unaweza kuunda mti kama huu. Unaweza kuwa na nodi alitangaza katika C, na node ya kwamba unaweza kuwa na vipengele angalau mbili ndani yake. Moja ni idadi unataka kuhifadhi, na nyingine ni - vizuri, tunahitaji moja zaidi. nyingine ni watoto wake. Hivyo hapa ni mwingine muundo data. Wakati huu, nodi hufafanuliwa kama hifadhi ya idadi n na kisha kuyatumia mbili; kushoto mtoto na mtoto wa kulia. Na wao siyo holela. Nini kuvutia kuhusu mti huu? Nini mfano katika jinsi tumekuwa kuweka hii nje au jinsi Patrick nieleza katika video yake? Ni aina ya dhahiri kwamba kuna baadhi ya kuchagua kinachoendelea hapa, lakini nini utawala rahisi? Yeah? [Mwanafunzi jibu, unintelligible] Perfect. Kama mtazamo saa hii, unaweza kuona idadi ndogo upande wa kushoto, kubwa idadi ya juu kushoto, lakini hiyo ni kweli kwa kila nodi. Kwa kila node, mtoto wake wa kushoto chini ya hilo, na mtoto wake wa kulia zaidi kuliko yake. Nini maana ya hii sasa ni kama nataka kutafuta muundo huu data kwa, kusema, idadi 44, Nina kuanza katika mizizi, kwa sababu kama na wote wa miundo hii ngumu zaidi data sasa, sisi tu pointer jambo moja, mwanzo. Na katika kesi hii, ni mwanzo wa mizizi. Ni sio mwisho wa kushoto, ni mizizi ya muundo huu. Hivyo naona hapa ni 55, na mimi nina kuangalia kwa 44. Ambayo mwelekeo mimi nataka kwenda? Naam, mimi nataka kwenda kushoto, kwa sababu ni wazi, kwa haki ni kwenda kuwa kubwa mno. Hivyo taarifa hapa, wewe ni aina ya conceptually chopping mti katika nusu kwa sababu wewe kamwe kwenda chini ya upande wa kulia. Hivyo, kwa sasa nakwenda 55-33. Ni ndogo sana ya idadi. Mimi nina kuangalia kwa 44, lakini sasa mimi kujua kama ni 44 katika mti huu, naweza kwenda wazi kwa haki. Hivyo tena, mimi nina kupogoa miti katika nusu. Ni pretty much kufanana conceptually kwa kitabu cha simu. Ni kufanana na kile sisi alivyofanya kwa karatasi ubaoni, lakini ni muundo kisasa zaidi ambayo inaruhusu sisi kwa kweli kufanya hii kugawanya na kushinda kwa kubuni ya algorithm, na kwa kweli, traversing muundo kama hii - Lo. Traversing muundo kama hii, ambapo ni tu "kwenda njia hii au kwenda kwa njia hiyo," maana kificho kwamba yote bent akili yako kwa mara ya kwanza wakati utekelezaji katika sehemu au kutembea njia hiyo ya nyumbani, kwa ajili ya kutafuta binary, kwa kutumia recursion au iteration, ni maumivu ya shingo. Kupata kipengele katikati, kisha kufanya rounding yako juu au chini. Kuna uzuri kwa hili kwa sababu sisi sasa unaweza kutumia recursion tena, lakini zaidi cleanly. Hakika, kama wewe ni katika idadi 55 na unataka kupata 44, kwenda kushoto katika kesi hii, basi nini nini? Wewe kukimbia exact algorithm. Wewe kuangalia thamani ya nodi, basi wewe kwenda kushoto au kulia. Kisha wewe kuangalia thamani ya nodi, kwenda kushoto au kulia. Hii ni kikamilifu inafaa kwa recursion. Hivyo hata kama huko nyuma tumekuwa kufanyika baadhi ya mifano uungwana holela kuwashirikisha recursion kwamba hakuwa na haja ya kuwa na kujirudia, na stuctures data, hasa miti, ni matumizi kamili ya wazo hili la kuchukua tatizo, kushuka, na kisha kutatua aina moja ya, lakini vidogo, mpango. Hivyo kuna mwingine muundo data kwamba tunaweza kuanzisha. Hii moja ni iliyoundwa katika mtazamo wa kwanza kuangalia cryptic, lakini hii ni ajabu. Hivyo hii ni muundo data kuitwa trie, trie, ambayo ni kurithiwa kutoka retrieval neno, ambayo si hutamkwa re-kujaribu-Val, lakini kwamba ni nini dunia wito mambo haya. Anajaribu. T-r-i-e. Ni muundo mti wa aina fulani, lakini kila mmoja wa nodi katika trie inaonekana kuwa nini? Na hii ni kidogo kupotosha kwa sababu ni aina ya abbreviated. Lakini inaonekana kama kila nodi katika trie hii ni kweli safu. Na hata kama mwandishi wa mchoro huu haijaonyesha hiyo, katika kesi hii, trie hii ni muundo data ambao lengo katika maisha ni ya kuhifadhi maneno kama-l-i-c-e au B-o-b. Na njia ambayo hiki data maduka Alice na Bob na Charlie na Anita na kadhalika ni inatumia safu ambapo kuhifadhi Alice katika trie, sisi kuanza nodi katika mizizi ambayo inaonekana kama safu, na ni kuandikwa katika nukuu shorthand. mwandishi omitted abcdefg kwa sababu kulikuwa hakuna majina na kwamba. Wao tu ilionyesha M na P na T, lakini katika kesi hii, hebu kuondokana na Alice na Bob na Charlie kwa majina baadhi ya kwamba ni hapa. Maxwell ni kweli katika mchoro huu. Hivyo ni jinsi gani kuhifadhi mwandishi M--x-w-e-l-l? Yeye au yeye kuanza nodi katika mizizi, na akaenda [M], hivyo takribani 13, eneo ya 13 katika safu. Halafu kutoka hapo, kuna pointer. pointer kuongoza safu nyingine. Kutoka huko mwandishi indexed katika safu kwamba katika eneo, kama alivyoonyeshwa huko juu kushoto, na kisha yeye au yeye ikifuatiwa kuwa pointer safu mwingine, na akaenda katika eneo pointer X. Kisha katika safu ijayo mahali W, E, L, L, na kadhalika, na hatimaye, hebu kweli kujaribu kuweka picha hii. Gani kuangalia nodi kama katika code? nodi katika trie ina safu ya kuyatumia kwa nodes zaidi. Lakini kuna pia got kuwa baadhi ya aina ya thamani ya bulin, angalau katika utekelezaji huu. Mimi kutokea kwa kuiita is_word. Kwa nini? Kwa sababu wakati wewe ni kuingiza Maxwell, wewe si inserting kitu chochote ndani ya muundo huu data. Wewe si kuandika M. Wewe si kuandika X. Wote wewe kufanya ni kufuatia kuyatumia. pointer kwamba inawakilisha M, basi pointer kwamba inawakilisha, kisha pointer kwamba inawakilisha X, kisha W, E, L, L, lakini nini unahitaji kufanya mwishoni ni aina ya kwenda, angalia, mimi kufikiwa hii mahali. Kulikuwa na neno kwamba mwisho hapa katika muundo data. Basi nini trie ni kweli kujazwa na mwandishi alichagua kuwakilisha haya terminuses na pembetatu kidogo. Hii ina maana kwamba tu ukweli pembetatu hii hapa, hii thamani ya kweli ya bulin ina maana kama wewe kurudi nyuma katika mti, kwamba maana ya neno aitwaye Maxwell ni katika hili. Lakini foo neno, kwa mfano, si katika mti, kwa sababu kama mimi kuanza nodi katika mizizi hapa juu kwa juu, Hakuna pointer f, hakuna pointer o, hakuna pointer o. Foo si jina katika kamusi hii. Lakini kwa kulinganisha, Turing, t-u-r-i-n-g. Tena, sikuweza kuhifadhi t au u au r au i au n au g. Lakini mimi kuhifadhi katika muundo huu data thamani ya njia ya kweli chini hapa kwenye nodi huu - kwa mti kwa kuweka thamani hii bulin ya is_word kwa kweli. Hivyo trie ni aina gani ya muundo huu kuvutia sana meta, ambapo wewe si kweli kuhifadhi maneno yenyewe kwa aina hii ya kamusi. Kuwa wazi, wewe tu kuhifadhi ndiyo au hapana, kuna neno kwamba mwisho hapa. Sasa nini maana? Kama una maneno 150,000 katika kamusi ya kwamba wewe ni kujaribu kuhifadhi kumbukumbu katika kutumia kitu kama orodha wanaohusishwa, wewe ni kwenda na nodes 150,000 katika orodha yako zinazoungwa. Na kutafuta mtu wa maneno hayo alphabetically inaweza kuchukua O (n) wakati. Linear wakati. Lakini katika kesi ya hapa trie, nini wakati mbio za kutafuta neno? Ni zinageuka uzuri hapa ni kwamba hata kama una 149,999 maneno tayari katika kamusi hii, kama kutekelezwa kwa muundo huu data, kiasi gani wakati gani kuchukua kupata au Insert moja zaidi mtu ndani ya kwamba, kama Alice, Alice? Naam, ni 5 tu, labda 6 hatua kwa ajili ya tabia trailing. Kwa sababu presense ya majina mengine katika muundo haina kupata njia ya kuingiza Alice. Aidha, kutafuta Alice mara moja kuna maneno 150,000 katika kamusi hii haina kupata njia yako ya kutafuta Alice wakati wote, kwa sababu ni Alice. . . . . hapa, kwa sababu nimeona thamani ya bulin. Na kama hakuna bulin kweli, basi ni Alice si katika muundo huu data ya maneno. Kwa maneno mengine, wakati mbio za kutafuta mambo na kuingiza mambo katika hii mpya data muundo wa trie ni O ya - ni si n. Kwa sababu presense ya watu 150,000 ina hakuna athari kwenye Alice, inaonekana. Basi hebu kuiita k, ambapo k ni upeo wa urefu wa neno katika lugha ya Kiingereza ambayo ni kawaida hakuna zaidi ya 20-kitu wahusika. Hivyo k ni mara kwa mara. Hivyo Grail Mtakatifu sisi wanaonekana kuwa kupatikana sasa ni kwamba wakati wa trie, mara kwa mara kwa ajili ya kuwekeza, kwa lookups, kwa kufuta maneno. Kwa sababu idadi ya mambo tayari katika muundo, ambayo ni hata kimwili huko. Tena, wao ni tu aina ya checked mbali, ndiyo au hapana, haina athari yoyote kwa wakati wake baadaye mbio. Lakini kuna got kuwa samaki, vinginevyo tusingeweza kupita muda kiasi juu ya miundo haya mengine yote data tu na hatimaye kupata kwa moja siri hiyo ni ajabu. Basi nini bei ni sisi kulipa ili kufikia ukuu hapa? Nafasi. Jambo hili ni kubwa. Na sababu ya kuwa mwandishi haijawasilisha hapa, taarifa kwamba mambo yote haya ili kuangalia kama arrays, hakuwa kuteka ya mapumziko ya mti, wengine wa trie, kwa sababu wao ni si tu muhimu kwa hadithi. Lakini yote ya nodi hiyo ni super pana, na kila nodi katika mti inachukua hadi 26 au kweli, inaweza kuwa 27 wahusika kwa sababu katika kesi hii nilikuwa pamoja na nafasi kwa apostrophe hivyo kwamba tunaweza kuwa na maneno apostrophized. Katika kesi hiyo, hizi ni pana arrays. Hivyo hata kama wao siyo picutured, hii inachukua hadi kiasi kikubwa cha RAM. Ambayo inaweza kuwa faini, especilly katika vifaa vya kisasa, lakini hiyo ni tradeoff. Sisi kupata muda kidogo kwa kutumia zaidi nafasi. Hivyo ambapo ni hii yote kwenda? Naam, hebu kufanya - hebu angalia hapa. Hebu kufanya kuruka kwa guy hii hapa. Amini au sio, fun kama vile C imekuwa kwa muda mrefu sasa, sisi ni kufikia hatua katika muhula ambapo ni wakati wa mpito kwa mambo ya kisasa zaidi. Mambo katika ngazi ya juu. Na hata kama kwa michache ijayo ya wiki tutaweza bado wanaendelea kutumbukiza wenyewe katika dunia ya kuyatumia na usimamizi kumbukumbu kupata kwamba faraja ambayo tunaweza kujenga juu kisha, mchezo wa mwisho ni hatimaye kuanzisha, hazijaingizwa si lugha hii. Tutaweza kutumia, kama dakika 10 kuzungumza juu ya HTML. Zote HTML ni ni lugha ghafi, na lugha gani ghafi ni ni hayo mfululizo wa mabano wazi na mabano funge kwamba kusema 'kufanya hii koze' 'Kufanya hii italics' kufanya hii kujivuna. ' Ni wale wote kielimu ya kuvutia, lakini ni super manufaa. Na hakika omnipresent siku hizi. Lakini nini nguvu kuhusu dunia ya HTML, na mtandao programu kwa ujumla zaidi, ni kujenga mambo ya nguvu; kuandika code katika lugha kama PHP au chatu au Ruby au Java au C #. Kweli, yo lugha yako ya uchaguzi ni, na kuzalisha HTML dynamically. Kuzalisha kitu kinachoitwa CSS dynamically. Kuachia mtindo shuka, ambayo pia ni kuhusu aesthetics. Na hata ingawa, leo, kama mimi kwenda kwa baadhi ya tovuti kama Google.com utambuzi, na mimi kwenda kuona, developer, mtazamo chanzo, ambayo labda umefanya kosa kabla, lakini kwenda kuona chanzo, stuff pengine hii inaonekana pretty cryptic. Lakini hii ni code msingi ambayo kutekeleza Google.com. Juu ya mwisho wa mbele. Na kweli, haya yote ni fluffy aesthetics stuff. Hii ni CSS hapa juu. Kama mimi kuweka scrolling chini tutaweza kupata baadhi ya mambo rangi-coded. Hii ni HTML. Code Google inaonekana kama fujo, lakini kama mimi kweli kufungua dirisha tofauti, tunaweza kuona baadhi muundo huu. Kama mimi kufungua hili, taarifa hapa, ni kidogo zaidi someka. Sisi ni kwenda kuona kabla ya muda mrefu hii tag, [neno] ni tag, HTML, kichwa, mwili, div, script, Nakala eneo hilo, span, unaozingatia, div. Na hii pia ni aina ya cryptic-kuangalia katika mtazamo wa kwanza, lakini wote wa fujo hii ifuatavyo ruwaza fulani, na mwelekeo wa repeatable, hivyo kwamba mara sisi kupata misingi chini, wewe utakuwa na uwezo wa kuandika code kama hii na kisha kuendesha code kama hii kwa kutumia bado lugha nyingine, kuitwa JavaScript. Na javascript ni lugha ya kwamba anaendesha ndani ya browser leo kwamba sisi kutumia juu ya Harvard kozi, kwa chombo bila shaka ununuzi kwamba anatumia Google ramani kukupa rundo zima la mabadiliko, Facebook inakupa kuonyesha updates hadhi papo, Twitter kuitumia kuonyesha tweets instantly. Yote hii tutaanza kutumbukiza wenyewe in Lakini kufika huko, tunahitaji kuelewa kitu kidogo kuhusu mtandao. Hii picha ya video hapa ni dakika tu kwa muda mrefu, na hebu kudhani kwa sasa hii ni, kwa kweli, jinsi Internet kazi kama teaser kwa nini kuhusu kuja. Mimi kukupa "Warriors ya Net." [♫ Slow chorus muziki ♫] [Kiume msimuliaji] Yeye alikuja na ujumbe. Pamoja na itifaki ya yote peke yake. [♫ Faster elektroniki muziki ♫] Alikuja dunia ya mpenyo baridi, asiyejali ruta, na hatari mbaya zaidi kuliko kifo. Yeye ni kufunga. Yeye ni hodari. Yeye ni TCP / IP, na yeye got anwani yako. Wapiganaji wa Net. [Malan] Ifwatayo wiki, basi. Internet. Mtandao programu. Hii ni CS50. [CS50.TV]