[Powered by Google Translate] [Sehemu ya 6: Chini Starehe] [Nate Hardison] [Chuo Kikuu cha Harvard] [Hii ni CS50.] [CS50.TV] Wote haki. Karibu sehemu ya 6. Wiki hii, sisi ni kwenda kuzungumza kuhusu miundo ya data katika sehemu, hasa kwa sababu tatizo hili la wiki hii kuweka juu ya spellr anafanya rundo zima la utafutaji data muundo tofauti. Kuna kundi la njia tofauti unaweza kwenda na kuweka tatizo, na data zaidi miundo wewe kujua kuhusu mambo zaidi cool unaweza kufanya. 

Basi hebu kuanza. Kwanza sisi ni kwenda kuzungumza kuhusu mwingi, stack na foleni data miundo kwamba sisi ni kwenda kuzungumza kuhusu. Mwingi na foleni ni kweli kusaidia wakati tunaanza kuzungumza kuhusu grafu, ambayo sisi siyo kwenda kufanya hivyo mengi ya hivi sasa. Lakini wao ni mzuri wa kuelewa moja ya miundo kubwa msingi data ya CS. maelezo katika vipimo kuweka tatizo, kama wewe vuta it up, mazungumzo kuhusu mwingi kama sawa na rundo la trays dining kwamba una katika mkahawa katika kumbi dining ambapo wakati wafanyakazi dining huja na unaweka trays dining nje baada wameweza kusafishwa yao, wao stack nao moja juu ya nyingine. Na kisha wakati watoto kuja katika kupata chakula, wao kuvuta trays mbali, kwanza moja ya juu, basi moja chini, basi moja chini ya kwamba. Hivyo, katika athari, tray kwanza kwamba wafanyakazi dining kuweka chini ni moja ya mwisho kwamba anapata kuchukuliwa mbali. moja ya mwisho kwamba wafanyakazi dining kuweka ni moja ya kwanza ya kwamba anapata kuchukuliwa mbali kwa chakula cha jioni. Katika spec kuweka tatizo, ambayo unaweza kushusha kama wewe si tayari, sisi majadiliano juu ya Modeling data stack stucture kutumia aina hii ya struct. 

Hivyo kile sisi tumepewa hapa, hii ni sawa na kile iliwasilishwa katika hotuba, isipokuwa katika hotuba hii na sisi yaliyowasilishwa ints kinyume na Char * s. Hii ni kwenda kuwa stack kwamba maduka nini? Danieli? Nini sisi hifadhi katika stack hii? [Daniel] Strings? >> Sisi ni hifadhi masharti katika stack hii, hasa. Wote unahitaji kuwa ili kujenga stack ni safu ya uwezo fulani, ambayo katika kesi hii, uwezo ni kwenda kuwa katika mechi zote kwa sababu ni mara kwa mara. Na kisha kwa kuongeza safu, wote tunahitaji kufuatilia ni ukubwa wa sasa wa safu. Jambo moja kukumbuka hapa kwamba ni aina ya baridi ni kwamba sisi ni kujenga sifa data muundo juu ya nyingine muundo data, safu. Kuna njia tofauti ya kutekeleza mwingi. Sisi si kufanya hivyo kabisa bado, lakini hopefully baada ya kufanya matatizo zilizounganishwa-orodha, utaona jinsi urahisi unaweza kutekeleza stack juu ya orodha wanaohusishwa pia. Lakini kwa sasa, tutaweza fimbo na arrays. Hivyo tena, wote tunahitaji ni safu na sisi tu haja ya kufuatilia ukubwa wa safu. [Sam] Samahani, kwa nini ni kwamba wewe alisema stack ni juu ya masharti? Kwangu mimi inaonekana kama ni masharti ndani ya stack. [Hardison] Yeah. Sisi ni kujenga, sisi ni kuchukua safu data muundo wetu - hiyo ni swali kubwa. Hivyo swali ni kwa nini, kwa watu ambao ni kuangalia hii online, kwa nini sisi kusema kwamba stack ni juu ya masharti, kwa sababu hapa inaonekana kama masharti ni ndani ya stack? Ambayo ni kabisa kesi. Nini mimi alikuwa akimaanisha kwamba sisi tumepewa data safu muundo. Sisi tumepewa safu ya Char * s, hii safu ya masharti, na sisi ni kwenda kuongeza kwamba ili kujenga sifa data muundo. 

Hivyo stack ni changamano zaidi kuliko safu. Tunaweza kutumia safu kujenga stack. Hivyo hiyo ambapo sisi kusema kwamba stack umejengwa juu ya safu. Aidha, kama nilivyosema awali, tunaweza kujenga stack juu ya orodha zinazoungwa. Badala ya kutumia safu kushikilia mambo yetu, tunaweza kutumia orodha zilizounganishwa kushikilia mambo yetu na kujenga stack kuzunguka kwamba. Hebu kutembea kwa njia ya wanandoa wa mifano, kuangalia code baadhi, kuona nini hasa kinachotokea hapa. Upande wa kushoto, nimekuwa kutupwa chini nini kwamba struct stack bila kuangalia kama katika kumbukumbu kama uwezo walikuwa # hufafanuliwa kuwa nne. Sisi tumepewa wetu nne kipengele Char * safu. Sisi tumepewa masharti [0], masharti [1], masharti [2], masharti [3], na kisha kuwa nafasi ya mwisho kwa ukubwa integer yetu. Je, hii mantiki? Sawa. Hii ni kile kinachotokea kama ninafanya juu ya haki, ambayo itakuwa code yangu, ni tu kutangaza struct, struct sifa kuitwa s. Hii ni nini sisi kupata. Ni huutoa hii footprint katika kumbukumbu. Swali la kwanza hapa ni nini ni yaliyomo ya struct hii stack? Hivi sasa wao ni kitu, lakini wao siyo kabisa kitu. Wao ni aina hii ya takataka. Sisi hatuna wazo nini katika yao. Wakati sisi kutangaza s stack, tuko tu kutupa kwamba chini juu ya kumbukumbu. Ni aina ya kama kutangaza int i na si initializing yake. Huwezi kujua nini huko. Unaweza kusoma nini huko, lakini inaweza kuwa super kusaidia. Jambo moja unataka daima kumbuka kufanya ni initialize chochote inahitaji initialized. Katika kesi hiyo, tunakwenda initialize kawaida kuwa sifuri, sababu ambayo inaenda kugeuka kutoka kuwa muhimu sana kwa sisi. Tunaweza kwenda mbele na initialize yote ya kuyatumia, char wote * s, kuwa baadhi ya thamani ya kueleweka, pengine null. Lakini si lazima kabisa kwamba sisi kufanya hivyo. 

Sasa, wawili shughuli kuu juu ya moshi huo? Anybody kukumbuka kutoka hotuba nini kufanya na mwingi? Ndiyo? [Stella] Kusukuma na popping? >> Hasa. Kusukuma na popping ni wawili shughuli kuu juu ya mwingi. Na nini kushinikiza kufanya? >> Ni unaweka kitu kwenye kilele ya stack, na kisha popping inachukua ni mbali. [Hardison] Hasa. Hivyo kusukuma inasukuma kitu juu ya stack. Ni kama wafanyakazi dining kuweka tray dining chini juu ya kukabiliana. Na popping ni kuchukua tray dining mbali ya stack. Hebu kutembea kwa njia ya wanandoa wa mifano ya nini kinatokea wakati sisi kushinikiza mambo kwenye mkusanyiko. Kama tulikuwa kushinikiza string 'hujambo' kwenye stack yetu, hii ni nini mchoro wetu bila kuangalia kama sasa. Angalia kinachotokea? Sisi kusukuma ndani ya kipengele kwanza ya safu yetu masharti na sisi upped kawaida yetu kuhesabu kuwa 1. Hivyo kama sisi kuangalia tofauti kati ya slaidi mbili, hapa alikuwa 0, hapa kabla ya kushinikiza. Hapa ni baada ya kushinikiza. Kabla ya kushinikiza, baada ya kushinikiza. Na sasa sisi moja ya kipengele katika stack yetu. Ni string "hello", na hiyo ni yake. Kila kitu kingine katika safu, katika safu yetu ya masharti, bado ni takataka. Sisi si initialized yake. Hebu sema sisi kushinikiza mwingine kamba kwenye stack yetu. Sisi ni kwenda kushinikiza "dunia" katika wakati huu. Hivyo unaweza kuona "ulimwengu" hapa unaendelea juu ya "hello", na kuhesabu kawaida huenda juu kwa 2. Sasa tunaweza kushinikiza "CS50", na kwamba itabidi kwenda juu tena. Kama sisi kurudi nyuma, unaweza kuona jinsi sisi ni kusukuma mambo juu ya stack. Na sasa sisi kupata pop. Wakati sisi popped kitu mbali ya stack, nini kilitokea? Anybody kuona tofauti? Ni pretty hila. [Mwanafunzi] kawaida. >> Yeah, ukubwa iliyopita. 

Nini kingine ingekuwa wewe inatarajiwa kubadilisha? [Mwanafunzi] masharti, pia. >> Haki. masharti pia. Ni zinageuka kuwa wakati wewe kufanya hivyo kwa njia hii, kwa sababu sisi siyo kuiga mambo kwenye mkusanyiko wetu, sisi kweli hawana kufanya chochote tunaweza tu kutumia ukubwa kuweka wimbo wa idadi ya mambo katika safu yetu ya hivyo kwamba wakati sisi pop tena, tena sisi tu pungufu kawaida yetu chini ya 1. Hakuna haja kwa kweli kwenda katika na overwrite chochote. Aina ya funky. Ni zinageuka kuwa sisi kawaida tu kuacha mambo peke yake kwa sababu ni chini ya kazi kwa ajili yetu kufanya. Kama hatuna kwenda nyuma na overwrite kitu, basi kwa nini kufanya hivyo? Hivyo wakati sisi pop mara mbili mbali ya stack, wote kwamba hana ni pungufu ukubwa michache ya nyakati. Na tena, hii ni kwa sababu tu sisi siyo kuiga mambo kwenye mkusanyiko wetu. Ndiyo? Kwenda mbele. [Mwanafunzi, unintelligible] >> Na kisha kile kinachotokea wakati kushinikiza kitu tena? Wakati wewe kushinikiza kitu tena, yanakwenda wapi? Yanakwenda wapi, Basil? >> Into masharti [1]? >> Haki. Kwa nini si ni kwenda katika masharti [3]? [Basil] Kwa sababu alisahau kuwa kulikuwa na kitu chochote katika masharti [1] na [2]? [Hardison] Hasa. Stack yetu, kimsingi, "alisahau" kuwa ni kufanya juu ya kitu chochote katika masharti [1] au masharti [2], hivyo wakati sisi kushinikiza "woot", tu kwamba unaweka ndani ya kipengele katika masharti [1]. Je, kuna maswali juu ya jinsi hii matendo, katika ngazi ya msingi? [Sam] Hivyo hii si nguvu kwa njia yoyote, katika suala la kiasi au katika suala la ukubwa wa stack? [Hardison] Hasa. Hii ni - Suala ni kuwa hii haikuwa stack dynamically growning. Hii ni stack kwamba wanaweza kushikilia, saa wengi, nne Char * s, katika mambo ya nne. Kama tulikuwa na kujaribu kushinikiza jambo tano, unafikiri nini kitokee? [Wanafunzi, unintelligible] [Hardison] Hasa. Kuna idadi ya mambo ambayo inaweza kutokea. Ni inaweza uwezekano seg kosa, kutegemea na nini sisi walikuwa - jinsi gani hasa sisi walikuwa kutekeleza nyuma-mwisho. Inawezekana overwrite. Inaweza kuwa kwamba kufurika buffer kwamba kuongelea katika darasa. Nini itakuwa jambo dhahiri zaidi kwamba ili kuwa overwritten kama tulijaribu kushinikiza jambo ziada juu ya stack yetu? Hivyo wewe zilizotajwa kufurika buffer. Nini kinaweza kuwa kitu bila kupata umeandikwa au kanyaga kama sisi ilifurika ajali kwa kujaribu kushinikiza jambo ziada? [Daniel, unintelligible] >> Inawezekana. Lakini awali, nini kinaweza kutokea? Nini kama tulijaribu kushinikiza kitu ya nne? Ni wanaweza overwrite kawaida, angalau kwa hili mchoro kumbukumbu kwamba sisi tumepewa. 

Katika vipimo kuweka tatizo, ambayo ni nini tunakwenda kuwa utekelezaji wa leo, nini sisi kufanya wanataka kufanya ni tu kurudi uongo. Tunashinikiza mbinu ni kwenda na kurudi thamani bulin, na kwamba thamani ya bulin itakuwa kweli kama kushinikiza inafanikiwa na uongo kama hatuwezi kushinikiza chochote zaidi kwa sababu stack ni kamili. Hebu kutembea kwa njia ya kidogo ya kificho kwamba hivi sasa. Hapa ni tunashinikiza kazi. Tunashinikiza kazi kwa stack ni kwenda kuchukua katika kamba ya kuweka kwenye stack. Ni kwenda na kurudi kweli kama kamba mara kwa mafanikio kusukuma juu ya vinginevyo stack na uongo. Mapendekezo yoyote juu ya nini inaweza kuwa nzuri kwanza jambo la kufanya hapa? [Sam] Kama ukubwa sawa na uwezo kisha kurudi uongo? [Hardison] Bingo. Nice kazi. Kama kawaida ni uwezo, sisi ni kwenda na kurudi uongo. Hatuwezi kuweka chochote zaidi katika stack yetu. Vinginevyo, sisi tunataka kuweka kitu juu ya stack. Nini ni "juu ya mnara," awali? [Daniel] Ukubwa 0? >> Ukubwa 0. Je, ni juu ya mnara baada kuna jambo moja katika stack? Missy, unajua? [Missy] Moja. >> Ukubwa ni moja, hasa. Wewe kuendelea kuongeza ya kawaida, na kila wakati wewe ni kuweka katika kipengele mpya katika ukubwa index katika safu. Tunaweza kufanya hivyo pamoja na kwamba aina ya mjengo moja, kama kwamba inafanya hisia. Hivyo sisi tumepewa masharti yetu safu, tunakwenda kupata hiyo katika index kawaida, na sisi ni tu kwenda kuhifadhi * yetu Char huko. Angalia jinsi kuna hakuna kuiga string kinachoendelea hapa, hakuna mgao wa nguvu ya kumbukumbu? Na kisha Missy nililelewa nini sisi sasa kuwa na kufanya, kwa sababu tumekuwa kuhifadhiwa kamba katika mahali sahihi katika safu, na yeye alisema kwamba alikuwa na increment kawaida na mmoja hivyo kuwa tuko tayari kwa msukumo ijayo. Hivyo tunaweza kufanya hivyo na s.size + +. Katika hatua hii, tumekuwa kusukuma ndani ya safu yetu. Nini jambo la mwisho tuna kufanya? [Mwanafunzi] Kurudi kweli. >> Kurudi kweli. Hivyo ni rahisi pretty, code pretty rahisi. Si sana. Mara ve amefungwa kichwa yako karibu jinsi stack kazi, hii ni pretty rahisi kutekeleza. 

Sasa, sehemu ya pili ya hii ni popping string mbali ya stack. Mimi naenda kukupa baadhi guys wakati wa kufanyia kazi kidogo kidogo hii. Ni karibu kimsingi kinyume na kile ambacho tumekuwa kufanyika hapa katika kushinikiza. What I ve kufanyika ni kweli - oops. Nimekuwa booted up appliance zaidi ya hapa, na katika appliance, Nimekuwa anapigiwa tatizo kuweka 5 vipimo. Kama sisi zoom katika hapa, tunaweza kuona mimi nina katika cdn.cs50.net/2012/fall/psets/pset5.pdf. Je, guys kupakuliwa hii kificho kwamba ziko hapa, section6.zip? Wote haki. Kama hujafanya hivyo, kufanya hivyo sasa hivi, kweli haraka. Nitafanya hivyo katika terminal dirisha yangu. Mimi kwa kweli alifanya hivyo hapa. Yeah. Ndiyo, Sam? >> Nina swali kuhusu nini wewe kusema mabano s.string 's ya ukubwa = str? Nini ni str? Ni kwamba defined mahali fulani kabla, au - oh, katika str Char *? [Hardison] Ndiyo, hasa. Hiyo ilikuwa hoja. >> Oh, sawa. Sorry. [Hardison] Sisi ni inayobainisha string kushinikiza in swali nyingine ambayo inaweza kuja kuwa hatukuwa kuzungumzia hapa ilikuwa sisi alichukua nafasi ya kwamba tulikuwa na hii variable kuitwa s kwamba alikuwa katika upeo na kupatikana kwetu. Sisi alichukua nafasi ya kwamba s ilikuwa hii struct stack. Hivyo kuangalia nyuma katika kanuni hii kushinikiza, unaweza kuona kwamba sisi ni kufanya mambo ya ajabu na hii kamba kwamba got kupita katika lakini kisha kwa ghafla, sisi ni kupata s.size, kama, ambako alifanya s kuja kutoka? Katika kificho kwamba sisi ni kwenda kuangalia katika archive sehemu na kisha stuff kwamba utasikia kuwa kufanya katika tatizo lako seti, tumekuwa kufanywa stack wetu struct variable kimataifa ili tuweze kuwa na huduma hiyo katika kazi yetu yote tofauti bila ya kuwa na manually kupita ni kuzunguka na kupita kwa kumbukumbu, kufanya aina hiyo ya mambo hayo. Sisi ni tu cheating kidogo, kama wewe, kufanya mambo nicer. Na kwamba ni kitu sisi ni kufanya hapa kwa sababu ni kwa ajili ya kujifurahisha, ni rahisi zaidi. Mara nyingi, utaona watu kufanya hili kama wana moja data kubwa muundo hiyo kuwa kazi juu ya ndani ya programu yao. 

Hebu kwenda nyuma zaidi kwa appliance. Je kila mtu kupata mafanikio section6.zip? Kila mtu unzip hilo kutumia section6.zip unzip? Kama kwenda katika saraka ya sehemu 6 - Aah, kila mahali - na wewe kuorodhesha nini katika hapa, unaweza kuona kwamba nimepata tatu tofauti files. c. Nimepata foleni, SLL, ambayo ni moja moja-zilizounganishwa orodha, na stack. Kama wewe kufungua stack.c, unaweza kuona kwamba sisi tumepewa hii struct hufafanuliwa kwa ajili yetu, struct halisi kwamba sisi tu kuongelea katika slaidi. Sisi tumepewa variable wetu wa kimataifa kwa ajili ya stack, sisi tumepewa tunashinikiza kazi, na kisha sisi tumepewa kazi yetu pop. Mimi itabidi kuweka code kwa kushinikiza nyuma hadi kwenye slide hapa, lakini kile Ningependa wewe guys kufanya ni, kwa kadri ya uwezo wako, kwenda na kutekeleza kazi ya pop. Mara ve kuutekeleza, unaweza kukusanya hii na kufanya stack, na kisha kukimbia matokeo stack executable, na kwamba inakwenda yote ya maadili ya mtihani huu chini hapa kwamba katika kuu. Na kuu inachukua huduma ya kweli ikitoa shinikizo na wito pop na kuhakikisha kwamba kila kitu huenda kwa njia ya haki yote. Ni pia initializes ukubwa stack haki hapa hivyo huna kuwa na wasiwasi kuhusu initializing kwamba. Unaweza kudhani kwamba imekuwa ni vizuri initialized kwa muda wa kwamba wewe kupata hiyo katika kazi ya pop. Je, hiyo mantiki? Hivyo hapa sisi kwenda. Kuna code kushinikiza. Mimi nitakupa guys 5 au dakika 10. Na kama una maswali yoyote katika muda mfupi wakati wewe coding, tafadhali waulize kwa sauti. Hivyo kama wewe kupata kwa uhakika sticking, kuuliza tu. Napenda kujua, basi kila mtu mwingine kujua. Kazi na jirani yako pia. [Daniel] Sisi ni tu kutekeleza pop hivi sasa? >> Tu pop. Ingawa unaweza nakala utekelezaji wa msukumo kama Ningependa ili kupima kazi. Kwa sababu ni vigumu kujaribu mambo kupata katika - au, ni vigumu kujaribu mambo popping nje ya stack kama kuna kitu chochote katika stack kwa kuanzia. 

Nini ni pop zinatakiwa kurudi? kipengele kutoka juu ya mnara. Ni walidhani kupata kipengele mbali ya juu ya mnara na kisha kuongezwa ukubwa wa stack, na sasa ve waliopotea kipengele juu. Na kisha kurudi kipengele juu. [Mwanafunzi, unintelligible] [Hardison] Hivyo kile kinachotokea kama wewe kufanya hivyo? [Mwanafunzi, unintelligible] Nini mwisho juu kinachotokea ni wewe pengine kupata aidha kipengele kwamba haijawahi initialized bado, hivyo wako hesabu ya mwisho ni kipengele ambapo ni mbali. Hivyo hapa, kama taarifa, katika kushinikiza, sisi ni kupata masharti katika kipengele s.size sababu ni ripoti mpya. Ni juu mpya ya stack. Wakati katika pop, s.size ni kwenda kuwa nafasi ya pili, nafasi hiyo ni juu ya mambo yote katika stack yako. Hivyo kipengele juu-wengi ni si wakati s.size, lakini badala yake, ni chini ya hiyo. 

Jambo jingine la kufanya wakati wewe - katika pop, ni wewe kuwa na kuongezwa ukubwa. Kama unakumbuka nyuma mchoro yetu kidogo hapa, kweli, kitu pekee tuliyoiona kinachotokea wakati sisi kuitwa pop ilikuwa kwamba ukubwa huu imeshuka, wa kwanza 2, basi kwa 1. Kisha wakati sisi kusukuma kipengele mpya juu, ingekuwa kwenda katika doa sahihi. [Basil] Kama s.size ni 2, basi ingekuwa si ni kwenda kipengele 2, na kisha wewe d wanataka pop kwamba kipengele mbali? Hivyo kama sisi akaenda - >> Basi hebu angalia hii tena. Kama hii ni stack wetu katika hatua hii na sisi kuwaita pop, ambayo ni kipengele index ya juu-wengi? [Basil] Katika 2, lakini inaenda pop 3. >> Haki. Hivyo hiyo ambapo kawaida yetu ni 3, lakini tunataka pop kipengele katika index 2. Ni kwamba aina ya kawaida ya mbali kwa moja kwamba una kwa Indexing sifuri-ya arrays. Hivyo huna wanataka pop kipengele tatu, lakini kipengele cha tatu ni si katika index 3. Na sababu hatuna la kufanya kwamba 1 bala wakati sisi ni kusukuma ni kwa sababu sasa hivi, utaona kwamba kipengele juu-wengi, kama tulikuwa kushinikiza kitu kingine kwenye stack katika hatua hii, sisi wanataka kuiondoa katika index 3. Na tu hivyo hutokea kwamba ukubwa na fahirisi line up wakati wewe ni kusukuma mbele. 

Nani got kazi stack utekelezaji? Nimepata stack kazi moja. Je, una pop kazi bado? [Daniel] Ndiyo. Nadhani hivyo. >> Programu ya mbio na si seg faulting, ni uchapishaji nje? Je magazeti nje "mafanikio" wakati wewe kukimbia? Yeah. Matokeo stack, kukimbia, kama Prints nje "mafanikio" na haina kwenda boom, kisha wote ni vizuri. Wote haki. Hebu kwenda juu kwa appliance kweli haraka, na tutaweza kutembea kwa njia hii. Kama sisi kuangalia nini kinaendelea hapa na pop, Daniel, nini ilikuwa jambo la kwanza kwamba alifanya? [Daniel] Kama s.size ni mkubwa kuliko 0. [Hardison] Sawa. Na kwa nini umefanya hivyo? [Daniel] Ili kuhakikisha kuwa kuna kitu fulani ndani ya stack. [Hardison] Haki. Unataka kupima ili kuhakikisha kuwa s.size ni mkubwa kuliko 0; vinginevyo, unataka nini kuwa kutokea? [Daniel] Kurudi null? >> Return null, hasa. Hivyo kama s.size ni mkubwa kuliko 0. Kisha ni nini sisi kwenda kufanya? Tufanye nini kama stack si tupu? [Stella] Wewe pungufu kawaida? >> Wewe pungufu kawaida, sawa. Hivyo ni jinsi gani unaweza kufanya hivyo? >> S.size--. [Hardison] Mkuu. Na kisha mlifanya nini? [Stella] Na ndipo nikasema kurudi s.string [s.size]. [Hardison] Mkuu. Vinginevyo wewe kurudi null. Ndiyo, Sam? [Sam] Kwa nini ni haja ya kuwa s.size + 1? [Hardison] Plus 1? >> Yeah. >> Nimeipata. [Sam] Nilidhani kwa sababu wewe ni kuchukua 1 nje, basi wewe ni kwenda kuwa kurudi si mmoja wao akaomba. [Hardison] Na hii ilikuwa tu kile sisi walikuwa wanazungumza juu ya suala hili zima la fahirisi 0. Hivyo kama sisi zoom nyuma zaidi ya hapa. Kama sisi kuangalia guy haki hii hapa, unaweza kuona kwamba wakati sisi pop, sisi ni popping kipengele katika index 2. 

Hivyo sisi kupungua kawaida yetu ya kwanza, basi kawaida yetu mechi index yetu. Kama hatuwezi pungufu kawaida kwanza, basi sisi kufanya ukubwa -1 na kisha pungufu. Mkuu. Yote mema? Maswali yoyote juu ya hili? Kuna idadi ya njia tofauti na kuandika hii pia. Kwa kweli, tunaweza kufanya kitu hata - tunaweza kufanya moja-mjengo. Tunaweza kufanya kurudi moja-line. Hivyo tunaweza kweli pungufu kabla sisi kurudi kwa kufanya hivyo. Hivyo kuweka - kabla s.size. Hiyo hufanya mstari kweli mnene. Ambapo tofauti kati - size s na. S.size-- ni kwamba hii postfix - wanayaita postfix kwa sababu - anakuja baada s.size-- ina maana kwamba s.size ni tathmini kwa madhumuni ya kutafuta index kama sasa ni wakati mstari huu ni kunyongwa, na kisha hii - kitatokea baada ya mstari anapata kunyongwa. Baada ya kipengele katika s.size index ni kupatikana. Na si kwamba tunataka nini, kwa sababu tunataka pungufu kutokea kwanza. Othewise, sisi wanaenda kupata safu, kwa ufanisi, nje ya mipaka. Sisi wanaenda kupata kipengele hapo juu moja kwamba sisi kweli wanataka kupata. Yeah, Sam? >> Je, ni kwa kasi au kutumia chini ya RAM ya kufanya katika mstari mmoja au? [Hardison] Kusema kweli, ni kweli inategemea. [Sam, unintelligible] >> Yeah, ni inategemea. Unaweza kufanya tricks compiler kupata compiler kutambua kuwa, kwa kawaida, mimi kufikiria. 

Hivyo tumekuwa zilizotajwa kidogo kuhusu mambo haya optimization compiler kwamba unaweza kufanya katika kuandaa, na kwamba ni aina ya kitu compiler ili kuwa na uwezo wa kufikiri, kama oh, hey, labda naweza kufanya hii yote katika operesheni moja, kinyume na upakiaji variable ukubwa katika kutoka RAM, decrementing yake, hifadhi hiyo nyuma nje, na kisha upakiaji na nyuma katika tena mchakato wengine wa operesheni hii. Lakini kwa kawaida, hakuna, hii si aina ya kitu hiyo ni kwenda kufanya mpango wako kwa kiasi kikubwa kasi. Maswali yoyote zaidi juu ya mwingi? 

Hivyo kusukuma na popping. Kama wewe guys unataka kujaribu toleo hacker, kile ambacho tumefanya katika toleo hacker ni kweli wamekwenda na alifanya stack hii kukua dynamically. Changamoto kuna kimsingi hapa juu katika kazi kushinikiza, kufikiri jinsi ya kufanya safu kwamba kukua kama wewe kushika kusukuma mambo zaidi na zaidi juu ya stack. Ni kweli si sana ziada code. Tu wito kwa - una kukumbuka kwa kupata wito kwa malloc huko vizuri, na kisha kufikiri wakati wewe ni kwenda kuwaita realloc. Hiyo ni changamoto fun kama wewe ni nia. 

Lakini kwa wakati huu, hebu hoja juu, na hebu majadiliano juu ya foleni. Kitabu kupitia hapa. foleni ni ndugu wa karibu wa stack. Hivyo katika stack, mambo ambayo walikuwa kuweka katika mwisho walikuwa mambo ya kwanza na kisha kuwa retrieved. Sisi tumepewa hii ya mwisho, kwanza nje, au LIFO, kuagiza. Wakati katika foleni, kama wewe d kutarajia kutoka wakati wewe ni amesimama katika mstari, mtu wa kwanza kupata katika mstari, jambo la kwanza kupata katika foleni, ni jambo la kwanza kwamba anapata Rudishwa kutoka foleni. Foleni mara nyingi pia kutumika wakati sisi ni kushughulika na grafu, kama sisi aliyesema kuhusu ufupi na mwingi, na foleni ni pia Handy kwa rundo ya mambo mengine. Jambo moja kwamba anakuja juu mara nyingi ni kujaribu kudumisha, kwa mfano, orodha ya mambo ya Iliyopangwa. Na unaweza kufanya hili na safu. Unaweza kudumisha orodha Iliyopangwa ya mambo katika safu, lakini ambapo anapata Tricky ni basi daima kuwa na kupata mahali sahihi na kuingiza jambo la pili. Hivyo kama una safu ya idadi, 1 kwa njia ya 10, na kisha unataka kuwa kupanua na idadi yote 1 kupitia 100, na wewe ni kupata namba hizi ili random na kujaribu kuweka kila kitu sorted kama kupitia, unaishia kuwa na kufanya mengi ya shifting. Pamoja na baadhi ya aina ya foleni na baadhi ya aina ya miundo ya msingi data, unaweza kweli kushika ni haki rahisi. Huna kuongeza kitu na kisha mvurugo jambo zima kila wakati. Wala kufanya mengi ya shifting ya mambo ya ndani duniani. Wakati sisi kuangalia foleni, unaweza kuona kwamba - pia katika queue.c katika sehemu code - struct kwamba tumekuwa kupeni ni kweli sawa na struct kwamba tuliyowapeni kwa stack. 

Kuna tofauti moja na hii, na kwamba tofauti moja ni kwamba tuna hii integer ziada kuitwa kichwa, na kichwa hapa ni kwa ajili ya kuweka wimbo wa kichwa cha foleni, au kipengele kwanza katika foleni. Pamoja na stack, tulikuwa na uwezo wa kuweka wimbo wa kipengele kwamba sisi walikuwa kuhusu retrieve, au juu ya mnara, kwa kutumia tu ukubwa, ambapo kwa foleni, sisi ni kuwa ili kukabiliana na ncha kinyume. Sisi ni kujaribu tack mambo juu ya mwishoni, lakini kisha kurudi mambo kutoka mbele. Hivyo kwa ufanisi, pamoja na kichwa, tuna index ya mwanzo wa foleni, na ukubwa inatupa index ya mwisho wa foleni ili tuweze retrieve mambo kutoka kichwa na kuongeza mambo kwenye mkia. Ambapo kwa stack, tulikuwa tu milele kushughulika na juu ya mnara. Sisi kamwe alikuwa kupata chini ya stack. Sisi tu aliongeza mambo ya juu na alichukua mambo mbali ya juu hivyo sisi hakuwa na haja ya kuwa uwanja wa ziada ndani ya struct yetu. Je, kwamba kwa ujumla kufanya akili? Wote haki. Ndiyo, Charlotte? [Charlotte, unintelligible] [Hardison] Hiyo ni swali kubwa, na kwamba alikuwa mmoja kwamba walifika katika hotuba. Labda kutembea kupitia mifano michache itaonyesha kwa nini hatutaki kutumia masharti [0] kama mkuu wa foleni. 

Hivyo kufikiria kwamba tuna foleni yetu, sisi ni kwenda kumwita foleni. Katika mwanzo, wakati tumekuwa tu instantiated yake, wakati tumekuwa tu amekiri kuwa ni, sisi si initialized chochote. Ni wote takataka. Hivyo bila shaka tunataka kuhakikisha kwamba sisi initialize wote ukubwa na mashamba kichwa kuwa 0, kitu nafuu. Tunaweza pia kwenda mbele na null nje vipengele katika foleni zetu. Na kufanya hii inafaa mchoro, taarifa kwamba sasa foleni yetu inaweza kushikilia tu mambo matatu; ambapo stack yetu inaweza kushikilia nne, foleni yetu inaweza tu kushikilia tatu. Na kwamba ni tu kufanya fit mchoro. Jambo la kwanza kwamba kinachotokea hapa ni sisi enqueue string "hi". Na kama tu sisi alivyofanya kwa stack, kitu sana tofauti hapa, sisi kutupa kamba juu katika nyuzi [0] na increment kawaida yetu kwa 1. Sisi enqueue "bye", anapata kuvaa. Hivyo hii inaonekana kama stack kwa sehemu kubwa. Sisi ilianza hapa, kipengele mpya, kipengele, ukubwa anaendelea kwenda juu. Nini kinatokea katika hatua hii wakati tunataka dequeue kitu? Wakati tunataka dequeue, ambayo ni kipengele kwamba tunataka dequeue? [Basil] Strings [0]. >> Zero. Hasa haki, Basil. Tunataka kujikwamua string kwanza, hii moja, "hi". Basi nini ilikuwa jambo nyingine kwamba iliyopita? Angalia wakati sisi popped kitu mbali ya stack, sisi tu iliyopita kawaida, lakini hapa, sisi tumepewa michache ya mambo ambayo mabadiliko. Si tu haina mabadiliko kawaida, lakini mabadiliko ya kichwa. Hii ni kwenda nyuma kwa uhakika Charlotte wa mapema: kwa nini tuna hii kichwa pia? Je, ni mantiki sasa, Charlotte? >> Aina ya. [Hardison] Aina ya? Hivyo kile kilichotokea wakati sisi dequeued? Nini kichwa kufanya hivyo sasa ni ya kuvutia? [Charlotte] Oh, kwa sababu ni iliyopita - sawa. Naona. Kwa sababu ya kichwa - ambapo kichwa ni akizungumzia mabadiliko katika suala la mahali. Ni tena daima sifuri index moja. >> Yeah, kwa uhakika. Nini kilichotokea ilikuwa kama dequeueing kipengele high ilifanywa na hatukuwa na uwanja huu kichwa kwa sababu sisi walikuwa daima wito huu string saa 0 index kichwa ya foleni yetu, basi tunatarajia kuwa kuhama mapumziko ya foleni chini. Tunatarajia kuwa kuhama "bye" kutoka kutoka masharti [1] kwa masharti [0]. Na masharti [2] chini ya masharti [1]. Na tunatarajia kufanya hili kwa orodha nzima ya vipengele, safu nzima ya vipengele. Na wakati sisi ni kufanya hii na safu, kwamba anapata kweli gharama kubwa. Hivyo hapa, si kubwa mpango huo. Sisi tu mambo matatu katika safu yetu. Lakini kama sisi alikuwa na foleni ya vipengele elfu au mambo milioni, na kisha kwa ghafla, sisi kuanza kufanya rundo la dequeue wito wote katika kitanzi, mambo ni kweli kwenda polepole chini kama ni mabadiliko ya kila kitu chini daima. Unajua, kuhama kwa 1, kuhama kwa 1 kuhama, na 1, kuhama kwa 1. Badala yake, sisi kutumia kichwa, tunasema "pointer" hata kama si kweli pointer katika hisia kali, ni si aina pointer. Siyo * int au * Char au kitu kama hicho. Lakini ni akizungumzia au kuonyesha kichwa cha foleni yetu. Yeah? 

[Mwanafunzi] Jinsi gani dequeue kujua tu pop mbali viliomo katika kichwa? [Hardison] Jinsi gani dequeue kujua jinsi ya pop mbali chochote ni katika kichwa? >> Haki, yeah. >> Nini ni kuangalia ni tu ya konde lolote kichwa ni kuweka. Hivyo katika kesi hii kwanza, kama sisi kuangalia haki hapa, kichwa wetu ni 0, index 0. >> Haki. [Hardison] Hivyo tu anasema sawa, vizuri, kipengele katika index 0, kamba "hi", ni kipengele katika kichwa cha foleni yetu. Hivyo sisi ni kwenda dequeue kwamba guy. Na kwamba itakuwa kipengele kwamba anapata akarudi kwa mpigaji. Ndiyo, Saad? Hivyo kichwa >> kimsingi seti - ambapo utaenda index yake? Hiyo ni mwanzo wa hivyo? >> Yeah. >> Sawa. [Hardison] Hiyo ni kuwa mwanzo mpya kwa ajili ya safu yetu. Hivyo wakati wewe dequeue kitu, wote una kufanya ni kupata kipengele katika index q.head, na kwamba itakuwa kipengele kwamba unataka dequeue. Unaweza pia kuwa na kuongezwa ukubwa. Tutaweza kuona katika kidogo ambapo mambo kupata gumu kidogo kwa hili. Sisi dequeue, na sasa, kama sisi enqueue tena, wapi sisi enqueue? Wapi kipengele ijayo kwenda katika foleni zetu? Sema tunataka enqueue string "CS". Ndani ambayo index itakuwa kwenda? [Wanafunzi] Strings [2]. >> Mbili. Mbona 2 na si 0? [Basil] Kwa sababu sasa kichwa ni 1, hivyo ndiyo kama mwanzo wa orodha? [Hardison] Haki. Na nini inaashiria mwisho wa orodha? Nini walikuwa sisi kutumia kuashiria mwisho wa foleni zetu? kichwa ni kichwa cha foleni yetu, mwanzo wa foleni yetu. Je, ni mwisho wa foleni zetu? [Wanafunzi] Ukubwa. >> Ukubwa, hasa. Hivyo mambo yetu mpya kwenda katika saa kawaida, na mambo ambayo sisi kuchukua mbali kufika mbali katika kichwa. Wakati sisi enqueue kipengele ijayo, sisi ni kuweka katika saa kawaida. [Mwanafunzi] Kabla ya kuweka kwamba katika ingawa, ukubwa alikuwa 1, haki? [Hardison] Haki. Hivyo si kabisa katika kawaida. Ukubwa +, si 1, lakini kichwa +. Kwa sababu sisi kubadilishwa kila kitu kwa kiasi kichwa. Hivyo hapa, sasa sisi tumepewa foleni ya kawaida ya 1 kwamba huanza saa index 1. mkia ni index 2. Ndiyo? 

[Mwanafunzi] Nini kinatokea wakati wewe dequeue masharti [0], na nyuzi 'inafaa katika kumbukumbu tu kupata alijipunguzia, kimsingi, au tu wamesahau? [Hardison] Yeah. Kwa maana hii, sisi ni tu kuyasahau. Kama tulikuwa hifadhi kopi zake kwa - wengi data miundo mara nyingi kuhifadhi nakala zao za mambo ya ili mtu kusimamia muundo data hana wasiwasi kuhusu ambapo kuyatumia wale wote wataenda. muundo data ana juu kwa kila kitu, ana juu ya nakala zote, kuhakikisha kwamba kila kitu likiendelea ipasavyo. Hata hivyo, katika kesi hii, miundo data hizi tu, kwa unyenyekevu, si kutengeneza nakala ya kitu chochote kwamba sisi ni hifadhi ndani yao. [Mwanafunzi] Basi ni hii safu ya kuendelea -? >> Ndiyo. Kama sisi kuangalia nyuma katika kile ufafanuzi ilikuwa ya muundo huu, ni. Ni tu safu ya kiwango kama wewe ve kuonekana, safu ya Char * s. Je, hiyo -? >> Yeah, mimi mara wanashangaa tu kama wewe utakuwa hatimaye kukimbia nje ya kumbukumbu, kwa kiwango fulani, kama una matangazo haya tupu wote katika safu yako? [Hardison] Yeah, hiyo ni hatua nzuri. 

Kama sisi kuangalia nini kilichotokea sasa katika hatua hii, tumekuwa kujazwa juu foleni zetu, inaonekana kama. Lakini sisi si kweli kujazwa juu foleni wetu sababu tuna foleni hiyo ni kawaida 2, lakini inaanza katika index 1, kwa sababu hiyo ambapo kichwa wetu pointer ni. Kama wewe walikuwa wakisema, kwamba kipengele katika masharti [0], katika index 0, si kweli huko. Ni si katika foleni wetu tena. Sisi tu haikujali kwenda katika na overwrite wakati sisi dequeued yake. Hivyo hata kama inaonekana kama tumekuwa kukimbia nje ya kumbukumbu, sisi kweli hawana. Kwamba doa inapatikana kwa sisi kutumia. tabia sahihi, kama tulikuwa na kujaribu na kwanza dequeue kitu kama "bye", kwamba ingekuwa pop bye mbali. Sasa foleni zetu huanza saa 2 na index ni ya kawaida ya 1. Na sasa kama sisi kujaribu na enqueue kitu tena, kusema 50, 50 lazima kwenda katika doa hii ifikapo index 0 kwa sababu bado ni inapatikana kwa sisi. Ndiyo, Saad? [Saad] Je, hiyo kutokea moja kwa moja? [Hardison] Haitatokea kabisa moja kwa moja. Una kufanya math kufanya kazi yake, lakini kimsingi ni nini tumefanya ni tumekuwa tu na kung'ata. [Saad] Na ni sawa kama hii ina shimo katikati ya hilo? [Hardison] Ni kama tunaweza kufanya math kazi nje vizuri. 

Na zinageuka kuwa hiyo ni kweli si vigumu kufanya na operator Mod. Hivyo tu kama tulivyofanya kwa Kaisari na stuff crypto, kutumia Mod, tunaweza kupata mambo kufungia na kuendelea kuzunguka na kuzunguka kwa foleni yetu, kuweka kwamba pointer kichwa kusonga karibu. Ona kwamba ukubwa daima ni kuheshimu idadi ya vipengele kweli ndani ya foleni. Na ni tu pointer kichwa kwamba anaendelea baiskeli kupitia. Kama sisi kuangalia nini kilitokea hapa, kama sisi kwenda nyuma ya mwanzo, na wewe tu kuangalia nini kinatokea kwa kichwa wakati sisi enqueue kitu, hakuna kitu kilichotokea kwa kichwa. Wakati sisi enqueued kitu kingine, kitu kilichotokea kwa kichwa. Haraka kama sisi dequeued kitu, kichwa huenda juu kwa moja. Sisi enqueued kitu, hakuna kinachotokea kwa kichwa. Wakati sisi dequeue kitu, kwa ghafla kichwa anapata incremented. Wakati sisi enqueue kitu, hakuna kinachotokea kwa kichwa. 

Nini kitatokea katika hatua hii kama sisi tulikuwa na dequeue kitu tena? Mawazo yoyote? Nini kingetokea kwa kichwa? Nini kitokee kwa kichwa kama tulikuwa na dequeue kitu kingine? kichwa sasa hivi ni saa index 2, ambayo ina maana ya kuwa kichwa cha foleni ni masharti [2]. [Mwanafunzi] Ambayo anarudi 0? >> Ni lazima kurudi 0. Ni lazima wrap nyuma kote, hasa. Hadi sasa, kila wakati sisi kuitwa dequeue, tumekuwa kuongeza moja kwa kichwa, kuongeza moja kwa kichwa, kuongeza moja kwa kichwa, kuongeza moja kwa kichwa. Haraka kama kwamba pointer kichwa anapata index mwisho katika safu yetu, basi tuna wrap ni nyuma karibu na mwanzo, kurudi nyuma kwa 0. [Charlotte] Nini huamua uwezo wa foleni katika stack? [Hardison] Katika kesi hiyo, sisi been tu kutumia mara kwa mara # defined. >> Sawa. [Hardison] Katika halisi. Faili c, unaweza kwenda katika na muck na ni kidogo kidogo na kufanya hivyo kama kubwa au kidogo kama unataka. [Charlotte] Basi wewe ni kufanya ni foleni, jinsi gani ya kufanya kompyuta kujua jinsi kubwa unataka stack kuwa? [Hardison] Hiyo ni swali kubwa. Kuna michache ya njia. Moja ni tu kufafanua juu mbele na kusema huu ni kwenda kuwa foleni kwamba ina mambo 4 au vipengele 50 au 10,000. Njia nyingine ni kufanya nini toleo hacker folks ni kufanya na kujenga kazi kwa kuwa na foleni yako kukua dynamically kama mambo zaidi kupata aliongeza in 

[Charlotte] Basi kwenda na chaguo la kwanza, nini syntax gani unatumia kuwaambia mpango gani ni ya kawaida ya foleni? [Hardison] Ah. Basi hebu kupata nje ya hii. Mimi bado katika stack.c hapa, hivyo mimi nina kwenda tu na kitabu hadi juu hapa. Je, unaweza kuona haki hii hapa? Hii ni # define uwezo 10. Na hii ni karibu exact syntax kwamba tuna kwa foleni. Isipokuwa katika foleni, sisi tumepewa kwamba ziada struct shamba katika hapa. [Charlotte] Oh, nilifikiri uwezo maana uwezo kwa kamba. [Hardison] Ah. >> Hiyo ni upeo wa urefu wa neno. >> Nimeipata. Yeah. uwezo hapa - hiyo ni hatua kubwa. Na hili ni jambo ambalo ni gumu kwa sababu kile ambacho tumekuwa alitangaza hapa ni safu ya Char * s. safu ya kuyatumia. Hii ni safu ya chars. Hii ni pengine unapomwona wakati tumekuwa kutangaza buffers yako kwa ajili ya faili I / O, wakati tumekuwa kujenga masharti manually juu ya stack. Hata hivyo, nini sisi tumepewa hapa ni safu ya Char * s. Hivyo ni safu ya kuyatumia. Kweli, kama sisi zoom nyuma nje na sisi kuangalia nini kinaendelea hapa katika mada, unaweza kuona kwamba mambo halisi, data tabia si kuhifadhiwa ndani ya safu yenyewe. Nini kuhifadhiwa ndani ya safu yetu hapa ni kuyatumia na data tabia. Sawa. Hivyo tumeona jinsi ukubwa wa foleni ni sawa kama stack, ukubwa daima inaheshimu idadi ya vipengele hivi sasa katika foleni. Baada ya kufanya enqueues 2, ukubwa ni 2. Baada ya kufanya dequeue kawaida sasa ni 1. Baada ya kufanya mwingine enqueue ukubwa ni nyuma hadi 2. Hivyo ukubwa dhahiri inaheshimu idadi ya vipengele katika foleni, na kisha kichwa kuvaa tu baiskeli. Ni inakwenda kutoka 0-1-2, 0-1-2, 0-1-2. Na kila wakati sisi kuwaita dequeue, pointer kichwa anapata incremented kwa index ijayo. Na kama kichwa ni kuhusu kwenda juu, ni tanzi nyuma karibu na 0. Hivyo, pamoja na kwamba, tunaweza kuandika kazi dequeue. Na sisi ni ataondoka kazi enqueue kwa guys kutekeleza badala yake. 

Wakati sisi dequeue kipengele nje ya foleni yetu, nini ilikuwa jambo la kwanza kwamba Danieli alifanya wakati sisi kuanza kuandika kazi pop kwa mwingi? Hebu kusikia kutoka mtu ambaye hajazungumza bado. Hebu angalia, Saad, je, unakumbuka kile Daniel wakafanya kama jambo la kwanza wakati yeye aliandika pop? [Saad] Kulikuwa, ilikuwa - >> Alimjaribu kwa kitu fulani. [Saad] Kama kawaida, ni mkubwa kuliko 0. >> Hasa. Na nini ilikuwa kwamba kwa ajili ya kupima? [Saad] Hiyo ilikuwa kupima ili kuona kama kuna kitu chochote ndani ya safu. [Hardison] Yeah. Hasa. Hivyo unaweza si pop kitu chochote nje ya stack kama ni tupu. Aidha, huwezi dequeue kitu chochote kutoka foleni kama ni tupu. Je, ni jambo la kwanza tunapaswa kufanya kazi katika dequeue yetu hapa, unafikiri? [Saad] Kama kawaida, ni mkubwa kuliko 0? >> Yeah. Katika kesi hiyo, Nimekuwa kwa kweli tu kupimwa ili kuona kama ni 0. Kama ni 0, tunaweza kurudi null. Lakini exact mantiki. Na hebu kuendelea na hii. Kama kawaida si 0, ambapo ni kipengele kwamba tunataka dequeue? [Saad] Katika kichwa? >> Hasa. Tunaweza tu kuvuta nje ya kipengele kwanza katika foleni zetu kwa kupata kipengele katika kichwa. Hakuna mambo. Baada ya kuwa, tunapaswa kufanya nini? Nini kitokee? Ni jambo gani mengine ambayo kuongelea katika dequeue? Mambo mawili ni lazima yatokee, kwa sababu foleni yetu imebadilika. [Daniel] Punguza ukubwa. >> Tuna kupunguza ukubwa, na kuongeza kichwa? Hasa. Kuongeza kichwa, hatuwezi tu upofu kuongeza kichwa, kumbuka. Hatuwezi tu kufanya queue.head + +. Inabidi pia ni pamoja na hii Mod na uwezo. Na kwa nini sisi Mod na uwezo, Stella? [Stella] Kwa sababu ina kufungia. >> Hasa. Sisi Mod na uwezo kwa sababu ina wrap nyuma karibu na 0. Hivyo sasa, katika hatua hii, tunaweza kufanya nini Daniel alisema. Tunaweza pungufu kawaida. Na kisha tunaweza tu kurudi kipengele kwamba ilikuwa saa juu ya foleni. Inaonekana aina ya gnarly mara ya kwanza. Unaweza kuwa na swali. Samahani? 

[Sam] Kwa nini ni ya kwanza katika juu ya foleni? Wapi kwamba kwenda? [Hardison] Ni huja kutoka mstari wa nne kutoka chini. Baada ya sisi mtihani kuhakikisha kuwa foleni yetu si tupu, sisi kujiondoa * Char kwanza, sisi kujiondoa kipengele ambacho ameketi index kichwa wa safu yetu, ya masharti yetu safu, >> na wito kwamba kwanza? [Hardison] Na tunasema kwanza. Yeah. Tu kufuatilia kwamba, kwa nini unafikiri sisi ilibidi kufanya hivyo? [Sam] Kila kwanza tu kurudi q.strings [q.head]? >> Yeah. >> Sababu sisi ni kufanya mabadiliko ya hii q.head na kazi Mod, na hakuna njia ya kufanya hivyo ndani ya mstari kurudi pia. [Hardison] Hasa. Wewe ni doa juu. Sam 's kabisa doa juu. sababu tulikuwa na kujiondoa katika foleni ya kipengele kwanza yetu na kuhifadhi katika variable ni kwa sababu line hii ambapo sisi alikuwa tu q.head, kuna operator Mod huko si kitu ambacho tunaweza kufanya na kuwa ni kuchukua athari kwenye kichwa bila - katika mstari mmoja. Hivyo sisi kweli kuwa kujiondoa kipengele kwanza, kisha kurekebisha kichwa, kurekebisha na ukubwa, na kisha kurudi kipengele kwamba sisi vunjwa nje. Na hii ni kitu ambacho tutaweza kuona kuja baadaye na wanaohusishwa orodha, kama sisi kucheza karibu na wao. Mara nyingi wakati wewe ni kumkomboa au kutupa orodha wanaohusishwa unahitaji kukumbuka kipengele ijayo, pointer ya pili ya orodha wanaohusishwa kabla ya kutupa moja sasa. Kwa sababu vinginevyo wewe kutupa habari ya nini kushoto katika orodha. Sasa, kama wewe kwenda appliance yako, wewe kufungua x queue.c-nje ya hii. Hivyo kama mimi kufungua queue.c, basi mimi zoom katika hapa, utaona kwamba una faili sawa-kuangalia. Sawa-kuangalia faili kile tulikuwa mapema na stack.c. Sisi tumepewa struct yetu kwa foleni hufafanuliwa tu kama tuliona juu ya slaidi. 

Tuna kazi yetu enqueue ambayo ni kwa ajili ya kufanya. Na tuna kazi dequeue hapa. kazi dequeue katika faili ni unimplemented, lakini mimi itabidi kuiweka nyuma juu ya PowerPoint ili uweze kucharaza katika, kama Ningependa. Hivyo kwa dakika 5 ijayo au hivyo, you guys kazi enqueue ambayo ni karibu tu kinyume cha dequeue. Huna kurekebisha kichwa wakati wewe enqueueing, lakini je, una kurekebisha? Kawaida. Hivyo wakati wewe enqueue, kichwa anakaa untouched, ukubwa anapata iliyopita. Lakini haina kuchukua kidogo kidogo ya - itabidi kucheza karibu na Mod kwamba kufikiri nini hasa index kipengele mpya zinapaswa kuingizwa katika. Hivyo mimi nitakupa guys kidogo, kuweka dequeue nyuma hadi kwenye slide, na kama wewe guys na maswali, kelele yao nje ili tuweze wote majadiliano kuhusu wao kama kundi. Pia, kwa kawaida wewe don't - wakati wewe kurekebisha na ukubwa, unaweza daima tu - Wewe una Mod ukubwa milele? [Daniel] No >> Huna kwa Mod kawaida, kulia. Kwa sababu kawaida daima, kama you're - kuchukua wewe ni kusimamia mambo ipasavyo, ukubwa daima kuwa kati ya 0 na 3. Wapi una Mod wakati unafanya enqueue? [Mwanafunzi] tu kwa kichwa. >> Tu kwa kichwa, hasa. Na kwa nini una Mod wakati wote katika enqueue? Wakati ni hali ambayo wewe d na Mod? [Mwanafunzi] Kama una stuff saa mazingira, kama katika maeneo ya 1 na 2, na kisha wewe zinahitajika kuongeza kitu katika 0. [Hardison] Yeah, kwa uhakika. Hivyo kama kichwa yako pointer ni mwishoni sana, au kama kawaida yako plus kichwa yako ni kubwa, au tuseme, ni kwenda kufungia foleni. 

Hivyo katika hali hii kwamba sisi tumepewa hapa slide sasa hivi, kama nataka enqueue kitu sasa hivi, tunataka enqueue kitu katika index 0. Hivyo kama wewe kuangalia ambapo 50 huenda, na mimi simu enqueue 50, unaendelea chini huko chini. Unaendelea katika 0 index. Ni nafasi ya 'hi' kwamba alikuwa tayari dequeued. [Daniel] Wala wewe kuchukua huduma ya kwamba katika dequeue tayari? Kwa nini ni kufanya kitu chochote kwa kichwa katika enqueue? [Hardison] Oh, hivyo wewe si kubadilisha kichwa, pole. Lakini una kutumia operator Mod wakati wewe ni kupata kipengele kwamba unataka enqueue wakati wewe ni kupata kipengele ijayo katika foleni yako. [Basil] sikuweza kufanya hivyo, na mimi got "mafanikio" ya huko. [Daniel] Oh, mimi kuelewa unachosema. [Hardison] Basi wewe didn't - wewe tu alivyofanya katika q.size? [Basil] Yeah. Mimi tu iliyopita pande, sikuweza kufanya chochote kwa kichwa. [Hardison] Wewe si kweli kuwa upya kichwa kuwa kitu chochote, lakini wakati index katika safu masharti, wewe kweli kuwa kwa kwenda mbele na mahesabu ambapo kipengele ijayo ni, kwa sababu withe stack, kipengele ijayo katika stack yako alikuwa daima katika index sambamba na ukubwa. Tukiangalia nyuma hadi katika hafla ya stack wetu kushinikiza, tunaweza daima plunk katika kipengele wetu mpya wa kulia kwa ukubwa index. Ambapo kwa foleni, hatuwezi kufanya hivyo kwa sababu kama tuko katika hali hii, kama sisi enqueued 50 wetu string mpya aliamua kwenda kulia kwa masharti [1] ambayo hatutaki kufanya. Tunataka kuwa na kamba mpya kwenda katika index 0. 

Mtu yeyote gani - ndiyo? [Mwanafunzi] Nina swali lakini si kweli kuhusiana. Ina maana gani wakati mtu tu wito kitu kama pointer pred? Ni jina gani kwamba fupi kwa ajili ya? Najua ni tu jina. [Hardison] Pred pointer? Hebu angalia. Katika mazingira gani? [Mwanafunzi] Ilikuwa kwa Insert. Naweza kukuuliza baadaye kama unataka kwa sababu si kweli kuhusiana, lakini mimi tu - [Hardison] Kutoka Insert Daudi code kutoka hotuba? Tunaweza kuvuta kwamba na kuzungumza juu ya hilo. Tutazungumzia kwamba ijayo, mara sisi kupata orodha zilizounganishwa. 

Basi hebu kweli haraka kuangalia nini kazi enqueue inaonekana kama. Nini ilikuwa jambo la kwanza kwamba watu walijaribu kufanya katika line yako enqueue? Katika foleni hii? Sawa na nini alifanya kwa stack kusukuma. Ulifanya nini, Stella? [Stella, unintelligible] [Hardison] Hasa. Kama (q.size == UWEZO) - Nahitaji kuweka braces yangu katika mahali pa haki - kurudi uongo. Zoom katika kidogo. Sawa. Sasa nini jambo la pili kwamba tulikuwa na nini? Tu kama na stack, na kuingizwa katika mahali pa haki. Na hivyo kile ilikuwa mahali pa haki Insert kwamba? Pamoja na stack ilikuwa index kawaida, na hii siyo kabisa kwamba. [Daniel] nina q.head-au - q.strings? >> >> Yeah. q.strings [q.head + q.size Mod UWEZO]? [Hardison] Sisi pengine wanataka kuweka mabano kuzunguka hili hivyo kwamba sisi ni kupata precedence sahihi na hivyo ndiyo cleart kwa kila mtu. Na kuweka sawa sawa? Ili >> str? Ili >> str. Mkuu. Na sasa nini jambo la mwisho kwamba tuna nini? Tu kama tulivyofanya katika stack. >> Increment kawaida? >> Increment kawaida. Boom. Na kisha, tangu code starter tu akarudi uongo na default, tunataka hii mabadiliko ya kweli kama yote inakwenda kwa njia na yote inakwenda vizuri. Wote haki. Hiyo ni habari nyingi kwa sehemu. Sisi siyo kabisa juu. Tunataka kuzungumza kweli haraka kuhusu orodha moja moja-zilizounganishwa. Mimi itabidi kuweka hii up ili tuweze kwenda nyuma ya baadaye. Lakini hebu kwenda nyuma ya uwasilishaji wetu kwa slides chache tu zaidi. Hivyo enqueue ni TODO, sasa tumefanya hivyo. 

Sasa hebu tuangalie orodha moja moja-zilizounganishwa. Kuongelea hizi zaidi kidogo katika mihadhara. Jinsi wengi wa guys ulizoziona demo ambapo tulikuwa watu awkwardly akizungumzia idadi ya kila mmoja na kufanya? >> Mimi nilikuwa katika ile. >> Nini guys kufikiri? Gani kwamba, hopefully demystify haya kidogo kidogo? Pamoja na orodha, zinageuka kuwa sisi kukabiliana na aina hii ya kwamba sisi ni kwenda kuwaita nodi. Ambapo kwa foleni na stack tulikuwa structs kwamba tunatarajia kuwaita foleni katika stack, tulikuwa na hizi foleni mpya katika aina stack, hapa orodha ni kweli tu alifanya juu ya rundo za nodi. Katika njia sawa kwamba masharti ni dhorobu tu ya chars wote lined up karibu na kila mmoja. orodha wanaohusishwa ni tu nodi na mwingine nodi na mwingine nodi na mwingine wa nodi. Na badala ya smashing nodes wote pamoja na kuzihifadhi contiguously wote haki karibu na kila mmoja katika kumbukumbu, kuwa hii pointer ijayo inaruhusu sisi kuhifadhi nodes popote, katika random. Na kisha aina ya waya wote pamoja kwa uhakika kutoka kwa mmoja hadi mwingine. 

Na kile ambacho faida kubwa kwamba hii alikuwa na zaidi ya safu? Zaidi ya kila kitu hifadhi contiguously tu kukwama karibu na kila mmoja? Unakumbuka? Yeah? >> Dynamic kumbukumbu mgao? >> Dynamic kumbukumbu mgao kwa namna gani? [Mwanafunzi] Katika kwamba unaweza kuendelea kuifanya kubwa na huna hoja safu yako yote? [Hardison] Hasa. Hivyo, pamoja na safu, wakati unataka kuweka kipengele mpya katika katikati yake, una kuhama kila kitu kwa kutoa nafasi. Na kama kuongelea na foleni, kwamba ni kwa nini sisi kuendelea kuwa pointer kichwa, hivyo kwamba sisi siyo daima shifting mambo. Kwa sababu kuwa anapata ghali kama nimepata safu kubwa na wewe daima kufanya insertions haya random. Ambapo kwa orodha, wote una kufanya ni kutupa juu ya nodi ya mwezi, kurekebisha kuyatumia, na wewe ni kosa. Nini sucks kuhusu hili? Mbali na ukweli kwamba siyo rahisi kama kufanya kazi na kama safu? Yeah? [Daniel] Naam, mimi nadhani ni vigumu sana kupata nyenzo mahsusi katika orodha wanaohusishwa? [Hardison] Huwezi tu wanaruka na kipengele holela katikati ya orodha yako zinazoungwa. Jinsi gani unaweza kufanya hivyo badala yake? >> Wewe ikaingilia kupitia jambo nzima. [Hardison] Yeah. Una kwenda kwa njia ya moja kwa wakati mmoja, moja kwa wakati mmoja. Ni kubwa - ni maumivu. Nini nyingine - kuna mwingine kuanguka kwa hii. [Basil] Huwezi kwenda mbele na nyuma? Una kwenda mwelekeo mmoja? [Hardison] Yeah. Hivyo ni jinsi gani sisi kutatua kwamba, wakati mwingine? [Basil] doubly-wanaohusishwa orodha? >> Hasa. Kuna doubly-wanaohusishwa orodha. Kuna pia - sorry? 

[Sam] Je, hiyo ni sawa na kutumia kitu pred kwamba - I just ikumbukwe, ni kwamba yale kitu pred ni kwa? Je, si kwamba katika kati ya doubly na mmoja? Kuangalia [Hardison] Hebu saa nini hasa alikuwa akifanya. Hivyo hapa sisi kwenda. Hapa ni orodha code. Hapa tuna predptr, katika hapa. Ni hivi kile walikuwa wanazungumza juu ya? Hivyo hii ilikuwa - yeye kumkomboa orodha na yeye kujaribu kuhifadhi pointer yake. Hii si mara mbili, moja moja wanaohusishwa-orodha. Tunaweza kuzungumza zaidi kuhusu hili baadaye tangu hii ni kuzungumza juu ya kumkomboa orodha na mimi nataka kuonyesha baadhi ya mambo mengine ya kwanza. lakini ni tu - ni kukumbuka thamani ya PTR [Mwanafunzi] Oh, ni preceeding pointer? >> Yeah. Ili tuweze basi increment PTR yenyewe kabla ya sisi kisha bure kile predptr ni. Kwa sababu hatuwezi bure PTR na kisha piga PTR = PTR ijayo, haki? Hiyo itakuwa mbaya. Basi hebu angalia, nyuma ya guy. 

nyingine mbaya kitu kuhusu orodha ni kwamba wakati ambapo pamoja na safu sisi tu vipengele vyote wenyewe sifa karibu na kila mmoja, hapa sisi pia ilianzisha hii pointer. Hivyo kuna chunk ya ziada ya kumbukumbu kwamba sisi ni kuwa na matumizi ya kwa kila kipengele kwamba sisi ni hifadhi katika orodha yetu. Sisi kupata mabadiliko, lakini inakuja kwa gharama. Inakuja na gharama wakati huu, na inakuja na gharama kumbukumbu hii pia. Muda katika maana ya kwamba sisi sasa kuwa na kwenda kupitia kipengele kila katika safu kupata moja katika index 10, au kwamba ingekuwa index 10 katika safu. 

Tu kweli haraka, wakati sisi mchoro nje orodha hizi, kawaida sisi kushikilia kichwa cha orodha au pointer ya kwanza ya orodha na kumbuka kuwa hii ni pointer kweli. Ni tu 4 ka. Ni si nodi halisi yenyewe. Hivyo unaweza kuona kwamba haina thamani int ndani yake, hakuna pointer ijayo ndani yake. Ni literally tu pointer. Ni kwenda kwa uhakika na kitu ambacho ni halisi nodi struct. [Sam] pointer kuitwa nodi? >> Hii ni - hapana. Hii ni pointer kitu ya nodi aina. Ni pointer struct nodi. >> Oh, sawa. Mchoro kwenye code kushoto, juu ya haki. Tunaweza kuweka kwa null, ambayo ni njia nzuri ya kuanza. Wakati wewe ni mchoro, ama kuandika ni kama null au kuweka line hiyo kama kama hiyo. 

Moja ya njia rahisi ya kufanya kazi na orodha, na sisi kuuliza huna wote prepend na append kuona tofauti kati ya wawili, lakini ni dhahiri prepending rahisi. Wakati wewe prepend, hii ni wapi - wakati wewe prepend (7), kwenda na kujenga struct nodi na kuweka kwanza kwa uhakika na hilo, kwa sababu sasa, tangu sisi prepended yake, itakavyo kuwa katika mwanzo wa orodha. Kama sisi prepend (3), ambayo inajenga mwingine wa nodi, lakini sasa 3 inakuja kabla ya 7. Hivyo sisi ni kimsingi kusukuma mambo kwenye orodha yetu. Sasa, unaweza kuona kwamba prepend, wakati mwingine watu kuiita kushinikiza, kwa sababu wewe ni kusukuma kipengele kipya kwenye orodha yako. Ni rahisi pia kufuta mbele ya orodha. Hivyo watu mara nyingi wito kwamba pop. Na kwa njia hiyo, unaweza kuiga stack kutumia orodha zinazoungwa. Whoops. Samahani, sasa sisi ni kupata katika append. Hivyo hapa sisi prepended (7), sasa sisi prepend (3). Kama sisi prepended kitu kingine kwenye orodha hii, kama sisi prepended (4), basi tunatarajia kuwa na 4 na kisha 3 na kisha 7. Hivyo basi tunaweza pop na kuondoa 4, kuondoa 3, kuondoa 7. Mara nyingi ni njia zaidi Intuitive kufikiri juu ya hili ni pamoja na append. Hivyo nimekuwa diagrammed nje ni nini bila kuangalia kama na append hapa. Hapa, umeongezewa (7) haina kuangalia tofauti yoyote sababu kuna moja tu ya kipengele katika orodha. Na appending (3) kuiweka mwishoni. Labda unaweza kuona haki sasa hila na append ni kwamba tangu sisi tu kujua ambapo mwanzo wa orodha ni, kwa append kwa orodha una kutembea njia zote orodha kupata hadi mwisho, kuacha, kisha kujenga nodi yako na kila kitu plunk chini. Waya mambo yote juu. Hivyo, pamoja na prepend, kama sisi tu ripped kupitia hii kweli haraka, wakati wewe prepend kwa orodha, ni haki rahisi. 

Unaweza kufanya nodi ya mwezi mpya, kuhusisha baadhi ya nguvu ya kumbukumbu mgao. Hivyo hapa sisi ni kufanya struct nodi kutumia malloc. Hivyo malloc sisi ni kutumia kwa sababu kwamba kutakuwa na kuweka kando kumbukumbu kwa ajili yetu kwa baadaye kwa sababu hatutaki hii - tunataka kumbukumbu hii kuendelea kwa muda mrefu. Na sisi kupata pointer nafasi katika kumbukumbu ya kwamba sisi tu zilizotengwa. Sisi kutumia ukubwa wa nodi, hatuwezi kuhitimisha mashamba. Hatuna manually kuzalisha idadi ya ka, badala ya sisi kutumia sizeof ili tujue sisi ni kupata idadi sahihi ya ka. Sisi kuhakikisha kwamba mtihani malloc wetu wito imefanikiwa. Hii ni kitu unataka kufanya kwa ujumla. Kwenye mashine ya kisasa, kukimbia nje ya kumbukumbu si kitu ambacho ni rahisi isipokuwa wewe ni kugawa tani ya mambo na kufanya orodha kubwa, lakini kama wewe ni kujenga mambo kwa, kusema, kama iPhone au Android, una rasilimali kumbukumbu mdogo, hasa kama wewe ni kufanya kitu makali. Hivyo ni vizuri kupata katika mazoezi. 

Ona kwamba nimepata kutumika wanandoa kazi tofauti tofauti hapa kwamba ve kuonekana kwamba ni aina ya mpya. Hivyo fprintf ni kama tu printf ila hoja yake ya kwanza ni mkondo ambayo unataka na magazeti. Katika kesi hiyo, tunataka magazeti kwa kamba kiwango makosa ambayo ni tofauti na outstream standard. By default inaonyesha up katika eneo moja. Ni pia Prints nje terminal, lakini unaweza - kutumia amri wale ulichojifunza kuhusu, mbinu redirection ulichojifunza kuhusu katika video Tommy kwa tatizo kuweka 4, unaweza kuielekeza maeneo mbalimbali; kisha exit, haki hapa, exits programu yako. Ni kimsingi kama kurudi kutoka kuu, ila sisi kutumia exit kwa sababu hapa kurudi haiwezi kufanya kitu chochote. Sisi siyo katika kuu, hivyo kurudi haina mpango kama exit tunataka. Hivyo sisi kutumia kazi exit na kuwapa code makosa. Ndipo hapa sisi kuweka thamani mpya wa nodi shamba, i yake shamba kuwa sawa na i, na kisha sisi waya it up. Sisi kuweka mpya wa nodi ijayo pointer kwa uhakika na ya kwanza, na kisha kwanza itakuwa sasa kuelekeza kwenye nodi mpya. Hizi mistari ya kwanza ya kificho, na sisi ni kweli ujenzi nodi mpya. Si mwisho mistari miwili ya kazi hii lakini ndio kwanza. Unaweza kweli kujiondoa katika kazi, katika kazi msaidizi. Hiyo mara nyingi nini mimi ni, mimi kuvuta ni nje ndani ya kazi, Naita kitu kama nodi kujenga, na kwamba anaendelea kazi prepend pretty ndogo, ni 3 tu mistari kisha. Mimi kufanya wito kwa kazi yangu kujenga nodi, na kisha mimi kila kitu waya up. 

Jambo la mwisho nataka kuonyesha wewe, na mimi itabidi basi kufanya append na yote juu yako mwenyewe, ni jinsi ya iterate juu ya orodha. Kuna kundi la njia tofauti iterate juu ya orodha. Katika kesi hii, sisi ni kwenda kupata urefu wa orodha. Hivyo sisi kuanza na urefu = 0. Hii ni sawa na kuandika strlen kwa kamba. Hii ni nini mimi nataka kuonyesha wewe, hii kwa kitanzi haki hapa. Inaonekana kinda funky, ni si kawaida int i = 0, i <chochote, i + +. Badala yake ni initializing n wetu kutofautiana kuwa mwanzo wa orodha. Na kisha wakati variable wetu iterator si null, sisi kuendelea. Hii ni kwa sababu, kwa mkataba, mwisho wa orodha yetu itakuwa null. Na kisha kwa increment, badala ya kufanya + +, wanaohusishwa orodha sawa ya + + ni n = n-> ijayo. 

Mimi itabidi basi kujaza mapengo hapa kwa sababu tuko nje ya muda. Lakini kuweka hii katika akili kama wewe kazi yako psets spellr. Wanaohusishwa orodha, kama wewe ni kutekeleza meza hash, itakuwa dhahiri kuja katika Handy sana. Na kwa kuwa hii idiom kwa looping juu ya mambo nitafanya maisha rahisi sana, hopefully. Maswali yoyote, kwa haraka? [Sam] Je kutuma nje SLL kukamilika na sc? [Hardison] Yeah. Mimi nitawapelekeni nje slides kukamilika na stack kukamilika SLL na queue.cs. [CS50.TV]