[Powered by Google Translate] [Kafli 6: Minna Comfortable] [Nate Hardison] [Harvard University] [Þetta er CS50.] [CS50.TV] Allt í lagi. Velkomin á kafla 6. Í þessari viku erum við að fara að tala um gögn uppbygging í kafla, fyrst og fremst vegna þess að vandamál þessa viku setja á spellr er a heild búnt af mismunandi gögn uppbygging könnun. Það eru fullt af mismunandi leiðir sem þú getur farið með vandamál setja, og fleiri gögn uppbygging sem þú þekkir, því meira kaldur hlutur sem þú getur gert. 

Svo skulum við hefjast handa. Fyrst við erum að fara að tala um stafla, stafla og biðröð gögn uppbygging sem við erum að fara að tala um. Stafla og biðraðir eru mjög hjálpleg þegar við byrjum að tala um gröf, sem við erum ekki að fara að gera svo mikið af núna. En þeir eru mjög gott að skilja einn af stóru grundvallaratriði gögn uppbygging af CS. Í lýsingu á setja vandamál forskrift, Ef þú draga það upp, talar um stöflum sem í ætt við í haug stæði veitingastöðum sem þú hefur í mötuneyti á veitingastöðum sölum þar þegar veitingastöðum starfsfólk kemur og setur veitingastöðum stæði út eftir að þeir hafa hreinsað þá, Þeir hlaða þeim einn ofan á öðrum. Og svo þegar börnin koma í til að fá mat, þeir draga í bökkunum burt, fyrst efst, og síðan einn fyrir neðan það, þá einn fyrir neðan það. Svo í raun, fyrsta bakki sem borðstofa starfsfólk setja niður er sá síðasti sem fær tekið burt. Sú síðasta sem borðstofa starfsfólk setja á er sú fyrsta sem fær tekið burt fyrir kvöldmat. Í sérstakur Vandamálið SET er, sem þú getur sótt ef þú hefur ekki nú þegar, við tölum um líkön gögn stafla stucture með svona strúktúr. 

Svo það sem við höfum hér, þetta er svipað og var kynnt í fyrirlestri, nema í fyrirlestri sem við kynnt þetta með ints öfugt við char * s. Þetta er að fara til vera a stafla sem geymir það? Daniel? Hvað erum við að geyma í stafla? [Daniel] Strings? >> Við erum að geyma strengi í mánudaginn, nákvæmlega. Allt sem þú þarft að hafa í því skyni að búa til stafla er fylki tiltekinnar stöðu, sem í þessu tilviki, getu er að fara að vera í öllum húfur því það er stöðug. Og svo í viðbót við fjölda, allt sem við þurfum að fylgjast með er núverandi stærð fylkisins. Eitt að hafa í huga hér að er góður af kaldur er að við erum að búa til staflað gögn uppbygging ofan á annars gögn uppbygging, array. Það eru mismunandi leiðir til að hrinda í framkvæmd stafla. Við munum ekki gera það alveg enn, en vonandi eftir að gera tengda-lista vandamál, þú munt sjá hvernig þú geta auðveldlega framkvæma stafla ofan á tengda lista eins og heilbrigður. En nú munum við halda fast við fylki. Svo aftur, allt sem við þurfum er fylki og við þurfum bara að fylgjast með stærð fylkisins. [Sam] Því miður, hvers vegna er það að þú segir að stafla er ofan á strengi? Fyrir mér virðist eins og strengirnir eru í stafla. [Hardison] Já. Við erum að búa til, erum við að taka array gögn uppbygging okkar - það er frábær spurning. Svo er spurningin hvers vegna, fyrir fólk sem eru að horfa á þetta á netinu, hvers vegna erum við að segja að stafla er ofan á strengi, því hér lítur það eins og strengir eru inni á mánudaginn? Sem er algerlega málið. Það sem ég var að vísa til var að við höfum fengið gögn array byggingu. Við höfum fengið fjölda char * s, þetta fjölbreytta strengi, og við ætlum að bæta við að til að búa til staflað gögn uppbygging. 

Svo er stafla örlítið flóknari en fylki. Við getum notað fylki til að byggja upp stafla. Svo er það sem við segjum að stafla er byggt ofan á fylki. Sömuleiðis, eins og ég sagði áðan, við getum byggt upp stafla ofan á tengda lista. Stað þess að nota fylki til að halda þætti okkar, við gætum notað tengda listanum að halda þáttum okkar og byggja upp stafla í kringum það. Við skulum ganga í gegnum a par af dæmum, að leita á einhverjum kóða, til að sjá hvað er í raun að gerast hér. Á vinstri, ég hef rifið niður það sem stafla strúktúr myndi líta út eins og í minni ef getu voru # skilgreint að vera fjórir. Við höfum fengið fjögurra þátturinn okkar char * array. Við höfum fengið strengi [0], strengir [1], strengir [2], strengir [3] og svo að síðustu rúm fyrir heiltala stærð okkar. Er þetta skynsamleg? Allt í lagi. Þetta er það sem gerist ef það sem ég á rétt á, sem verður númerið mitt, er bara að lýsa yfir strúktúr, sem staflað strúktúr heitir s. Þetta er það sem við fáum. Það er mælt fyrir um þetta fótspor í minni. Fyrsta spurningin hér er hvað er innihald þessarar stafla strúktúr? Núna þeir eru ekkert, en þeir eru ekki algerlega ekkert. Þeir eru af þessu tagi af rusli. Við höfum ekki hugmynd um hvað er í þeim. Þegar við lýsa stakkur s, við erum bara að henda því niður á toppur af minni. Það er góður af eins og að lýsa yfir int i og ekki Frumstilli það. Þú veist ekki hvað er þarna. Þú getur lesið það sem er þarna, en það gæti ekki verið frábær gagnlegt. Eitt sem þú vilt alltaf að muna eftir að gera er að frumstilla hvað þarf að frumstilla. Í þessu tilfelli erum við að fara að frumstilla stærð til að vera núll, vegna þess að það er að fara að snúa út að vera mjög mikilvægt fyrir okkur. Við gætum farið fram og frumstilla allar ábendingum, allt char * s, að sumir skiljanlegt gildi, líklega null. En það er ekki alveg nauðsynlegt að við gerum það. 

Nú eru tveir helstu aðgerðir á stafla? Hver man úr fyrirlestri hvað þú gerir við stafla? Já? [Stella] þrýsta og pabbi? >> Einmitt. Ýta og pabbi eru tveir helstu aðgerðir á stafla. Og hvað þýðir ýta gera? >> Setur það eitthvað á toppnum á mánudaginn, og þá tekur pabbi hana burt. [Hardison] Einmitt. Svo ýta ýtir eitthvað ofan á stafla. Það er eins og veitingastöðum starfsfólk Setja borðstofu bakkann á borðið. Og pabbi er að taka borðstofu bakka burt af the stakkur. Við skulum ganga í gegnum a par af dæmi um hvað gerist þegar við ýta hlutum í stafla. Ef við vorum að ýta strengnum "Hæ" á þinn stakkur okkar, þetta er það sem skýringarmynd okkar myndi líta út núna. Sjá hvað gerist? Við ýtt í fyrsta þáttur strengi array okkar og við upped stærð telja okkar til að vera 1.. Þannig að ef við skoðum muninn milli skyggnur, hér var 0, hér er fyrir að ýta. Hér er eftir að ýta. Áður en að ýta eftir að ýta. Og nú höfum við einn þáttur í stafla okkar. Það er band "halló", og það er það. Allt annað í fylking, í strengi array okkar, er enn sorp. Við höfum ekki frumstillt það. Við skulum segja að við séum að ýta annað band á stafla okkar. Við ætlum að ýta "heim" á þessum tíma. Svo þú getur séð "heim" hér fer ofan á "halló", og stærð telja fer upp í 2. Nú getum við ýta "CS50", og sem mun fara ofan aftur. Ef við förum til baka, getur þú séð hvernig við erum að þrýsta hluti ofan á stafla. Og nú fáum við að skjóta. Þegar við smella eitthvað burt af stakkur, hvað gerðist? Hver sjá muninn? Það er nokkuð lúmskur. [Námsmaður] Stærð. >> Já, stærð breytt. 

Hvað annað myndir þú hafa gert ráð fyrir að breyta? [Námsmaður] strengi líka. >> Einmitt. Strengi líka. Það kemur í ljós að þegar þú ert að gera það með þessum hætti, vegna þess að við erum ekki afrita þá þætti í stafla okkar, við í raun ekki að gera neitt, við getum bara notað stærð til að halda utan um fjölda af hlutum í fylkinu okkar þannig að þegar við skjóta aftur, aftur við lækka bara stærð okkar niður í 1. Það er engin þörf á að í raun og veru að fara í og ​​skrifa eitthvað. Eiginlega angurvær. Það kemur í ljós að við yfirleitt bara láta það eingöngu vegna þess að það er minni vinna fyrir okkur að gera. Ef við þurfum ekki að fara til baka og skrifa eitthvað, þá hvers vegna að gera það? Svo þegar við skjóta tvisvar burt af á mánudaginn, allt sem gerir er lækka stærð nokkrum sinnum. Og aftur, þetta er bara vegna þess að við erum ekki að afrita það inn í stafla okkar. Já? Fara á undan. [Námsmaður, óskiljanlegur] >> Og þá hvað gerist þegar þú ýta eitthvað aftur? Þegar þú ýta eitthvað aftur, hvar er það að fara? Hvar er það að fara, basil? >> Into strengi [1]? >> Einmitt. Hvers vegna er það ekki að fara í band [3]? [Basil] Vegna þess að hún gleymdi að það væri eitthvað í strengi [1] og [2]? [Hardison] Einmitt. Stafla okkar, fyrst og fremst, "gleymdi" að það var að halda á neinu á strengi [1] eða strengir [2], þannig að þegar við ýta "woot", það setur bara að í frumefni á strengi [1]. Eru einhverjar spurningar um hvernig þetta virkar, á undirstöðu stigi? [Sam] Svo þetta er ekki dynamic á nokkurn hátt, í skilmálar af upphæð eða hvað varðar stærð á mánudaginn? [Hardison] Einmitt. Þetta er - tilgangur var að þetta var ekki virk growning stakkur. Þetta er stafla sem halda, í mesta lagi, fjögurra char * s, á flestum fjórum hlutum. Ef við værum að reyna að ýta fimmta hlutur, hvað þér finnst ætti að gerast? [Nemendur, óskiljanlegur] [Hardison] Einmitt. There ert a tala af hlutur sem gæti gerst. Það gæti hugsanlega seg kenna, eftir því hvað við vorum - hvernig nákvæmlega við vorum framkvæmd bak-endir. Það gæti skrifa. Það gæti hafa biðminni flæða sem við ræddum um í bekknum. Hvaða vildi vera the augljós hlutur sem gæti verið skrifað Ef við reyndum að ýta auka hlutur á stafla okkar? Svo þú getið biðminni flæða. Hvað gæti verið hlutur sem myndi fá skrifað yfir eða stomped á ef við overflowed óvart með því að reyna að ýta auka hlutur? [Daniel, óskiljanlegur] >> mögulegt. En í upphafi, hvað gæti gerst? Hvað ef við reyndum að ýta fjórða hlutur? Það gæti yfirskrifa stærð, að minnsta kosti með þessum minni myndinni sem við höfum fengið. 

Í setja vandamál texta, sem er það sem við erum að fara að vera framkvæmd í dag, hvað við viljum gera er bara return false. Ýta aðferð okkar er að fara að skila Boolean gildi, og Boole gildi verður að vera satt ef ýta tekst og rangt ef við getum ekki ýta neitt meira vegna þess að stafla er fullt. Við skulum ganga í gegnum smá að kóða núna. Hér er ýta virka okkar. Ýta virka okkar í stafla er að fara að taka í streng til að setja á mánudaginn. Það er að fara að skila true ef strengurinn tókst ýtt á mánudaginn og falskur annað. Allar ábendingar um hvað gæti verið gott fyrstur hlutur til að gera hér? [Sam] Ef stærð jafnt getu þá return false? [Hardison] Bingo. Nice starf. Ef stærð er getu, við erum að fara að skila falskur. Við getum ekki sett neitt meira í stafla okkar. Annars viljum við að setja eitthvað á the toppur af the stakkur. Hvað er "efst á mánudaginn," í upphafi? [Daniel] stærð 0? >> Stærð 0. Hvað er efst á mánudaginn eftir að það er einn hlutur í stafla? Missy, veistu? [Missy] Ein. >> Stærð er einn, nákvæmlega. Þú halda að bæta við stærð, og í hvert skipti sem þú ert að setja í nýju þáttur í vísitölu stærð á fylki. Við getum gert það með svona einn-Ferja, ef það er vit í. Þannig að við höfum fengið strengi array okkar, við erum að fara að nálgast það á stærð vísitölu, og við erum bara að fara að geyma char * okkar þar. Taktu eftir hvernig það er ekkert band afritun gerast hér, engin dynamic úthlutun minni? Og þá Missy kom upp það sem við höfum nú til að gera, vegna þess að við höfum geymt strenginn á viðeigandi stað í fylkinu, og hún sagði að við þurftum að hækka stærð af einum þannig að við erum tilbúin fyrir næsta ýta. Þannig að við getum gert það með s.size + +. Á þessum tímapunkti höfum við ýtt inn í array okkar. Hvað er það síðasta sem við þurfum að gera? [Nemandi] Return satt. >> Return satt. Svo það er mjög einfalt, mjög einfalt númer. Ekki of mikið. Þegar þú hefur vafði höfuðið í kring hvernig stafla virkar, þetta er frekar einfalt að framkvæma. 

Nú er næsta hluti af þessu er að pabbi streng burt á mánudaginn. Ég ætla að gefa ykkur smá tíma til að vinna á þessu smá. Það er nánast í raun hið gagnstæða á því hvað við höfum gert hér á ýta. Það sem ég hef gert er í raun - Úps. Ég hef stígvélum upp tæki hérna, og í tækið, Ég hef dregið upp vandamál setja 5 forskrift. Ef við rennum hér, getum við séð að ég er á cdn.cs50.net/2012/fall/psets/pset5.pdf. Hefur þú krakkar sótt þetta kóða sem er staðsett hér, section6.zip? Allt í lagi. Ef þú hefur ekki gert það, að gera það núna, mjög fljótt. Ég skal gera það í Telnet mínu. Ég gerði í raun það upp hér. Já. Já, Sam? >> Ég er með spurningu um hvers vegna sagðirðu s.string er sviga af stærð = STR? Hvað er STR? Er það skilgreind einhvers staðar áður, eða - ó, á char * str? [Hardison] Já, nákvæmlega. Það var rök. >> Ó, allt í lagi. Því miður. [Hardison] Við erum að tilgreina band til að ýta inn Önnur spurning sem getur komið upp að við vissum ekki raunverulega tala um hér var tókum sem sjálfsagðan hlut því að við höfðum þetta breytu sem heitir s sem var að umfangi og aðgengilegan okkur. Við tókum sem sjálfsögðum hlut að s var þetta stafla strúktúr. Svo að horfa aftur á þetta ýta kóða, þú sérð að við erum að gera efni með þessum streng sem fékk samþykkt í en svo allt í einu, við erum að fá aðgang s.size, eins og þar var kominn frá? Í kóða sem við erum að fara að horfa á í kaflanum skjalasafn og þá setur efni sem þú munt vera að gera í vandamáli þínu, við höfum gert stafla okkar strúktúr alþjóðlegt breytu þannig að við getum haft aðgang að því á öllum okkar mismunandi valkosti án þess að þurfa að höndunum gefa það í kring og gefa það með tilvísun, gera allt sem svona efni til þess. Við erum bara að svindla smá, ef þú vilt, til að gera hlutina betur. Og það er eitthvað sem við erum að gera hér vegna þess að það er gaman, það er auðveldara. Oft, munt þú sjá fólk gera þetta ef þeir hafa einn stór gögn uppbygging það er verið að ganga á í dagskrá þeirra. 

Förum aftur yfir á tækið. Vissir allir fá tókst section6.zip? Allir renna niður hana með renna section6.zip? Ef þú ferð inn í kafla 6 skrá - aah, um allt - og þú lista það er hér, sérð þú að þú hafir fengið þrjár mismunandi. c skrár. Þú hefur got a biðröð, sem SLL, sem er ein sér-tengda listanum og stafla. Ef þú opnar stack.c, þú getur séð að við höfum fengið þennan strúktúr skilgreint fyrir okkur, nákvæmlega strúktúr sem við ræddum bara um í skyggnur. Við höfum fengið alþjóðlegt breytu okkar fyrir mánudaginn, við höfum fengið ýta virka okkar, og svo höfum við fengið popp virka okkar. Ég setti kóðann fyrir ýta aftur upp á mynd hér en það sem ég vil að þú krakkar að gera er, eftir bestu getu, fara og framkvæma pop virka. Þegar þú hefur innleitt það, getur þú saman þetta með að stafla, og keyra síðan hlýst stafla executable, og það mun keyra allt þetta próf kóða niður hér sem er í helstu. Og helstu sér í raun að gera að ýta og hvellur símtala og gættu þess að allt fer í gegnum allt í lagi. Það Frumstillir einnig stafla stærð hérna svo þú þarft ekki að hafa áhyggjur Frumstilli það. Þú getur gert ráð fyrir að það hefur verið rétt frumstilla eftir þeim tíma sem þú aðgang að honum í pop virka. Er það skynsamleg? Svo hér við fara. Það er ýta kóða. Ég ætla að gefa ykkur 5 eða 10 mínútur. Og ef þú hefur einhverjar spurningar í millitíðinni á meðan þú ert að erfðaskrá, vinsamlegast biðja þá upphátt. Svo ef þú færð að stafur lið, bara að spyrja. Láttu mig vita, láta allir aðrir vita. Vinna með náunga þínum líka. [Daniel] Við erum bara að innleiða pop núna? >> Bara skjóta. Þó að þú getur afritað framkvæmd ýta ef þú vilt svo að prófa að vinna. Vegna þess að það er erfitt að prófa það að fá inn - eða, það er erfitt að prófa pabbi fram úr stafla ef það er ekki neitt í stafla til að byrja með. 

Hvað er popp á að vera aftur? Þáttur frá the toppur af the stakkur. Það er ætlast til að fá hluti burt af the toppur af the stakkur og þá lækka stærð stafla, og nú að þú hafir misst þáttur á toppinn. Og þá aftur þátt á toppinn. [Námsmaður, óskiljanlegur] [Hardison] Svo hvað gerist ef þú gerir það? [Námsmaður, óskiljanlegur] Hvað endar er að gerast þú ert líklega að fá aðgang annaðhvort þáttur sem hefur ekki verið forsniðin enn, svo útreikningnum hvar síðasta þáttur er slökkt. Svo hér, ef þú tekur eftir, í ýta, við erum að fá aðgang strengi á s.size frumefni vegna þess að það er nýtt vísitölu. Það er nýr toppur af the stakkur. En í popp, s.size er að fara til vera the næstur pláss, rými sem er ofan á alla þætti í stafla þinn. Svo er efsta mest þátturinn ekki s.size, heldur er það undir honum. 

The annar hlutur til gera þegar þú - í popp, er að þú þarft að lækka stærð. Ef þú manst aftur litla skýringarmynd okkar hérna, í raun, það eina sem við sáum gerast þegar við kallað pop var að þessari stærð fækkaði, fyrst 2, svo að 1. Svo þegar við ýtt nýr þáttur á, myndi það fara á réttum stað. [Basil] Ef s.size er 2, þá myndi það ekki fara til frumefni 2, og þá þú vilt vilt að skjóta þessi þáttur burt? Svo ef við fórum til - >> Svo skulum líta á þetta aftur. Ef þetta er stafla okkar á þessum tímapunkti og við köllum pop, þar sem vísitalan er efst mest þáttur? [Basil] Á 2, en það er að fara að skjóta 3. >> Einmitt. Svo er það sem stærð okkar er 3, en við viljum að skjóta þáttur í vísitölu 2. Það er það dæmigert konar burt með einn sem þú hefur með núll-flokkun fylki. Svo þú vilt að skjóta þriðja frumefni, en þriðji þátturinn er ekki í vísitölunni 3. Og ástæða þess að við þurfum ekki að gera það mínus 1 þegar við erum að þrýsta er því núna, eftir að þú að toppur-mest þáttur, Ef við vorum að ýta eitthvað annað inn á mánudaginn á þessum tímapunkti, við myndum vilja að ýta því á vísitölu 3. Og það gerist bara svo að stærð og vísitölur stilla upp þegar þú ert að ýta. 

Hver fékk að vinna stafla framkvæmd? Þú hefur fengið að vinna stafla einn. Áttu pop vinna enn? [Daniel] Já. Ég held það. >> Program er í gangi og ekki seg faulting, það er að prenta út? Er það prentað út "árangur" þegar þú keyrir það? Já. Gerðu stafla, keyra hana, ef hún prentar út "árangur" og er ekki að fara uppsveiflu, þá er allt gott. Allt í lagi. Við skulum fara yfir tækið mjög fljótt, og við munum ganga í gegnum þetta. Ef við skoðum hvað er að gerast hérna með popp, Daníel, það var það fyrsta sem þú gerðir? [Daniel] Ef s.size er meiri en 0. [Hardison] lagi. Og hvers vegna gerðir þú að gera það? [Daniel] Til að tryggja að það var eitthvað inni í stafla. [Hardison] Rétt. Þú vilt prófa að ganga úr skugga um að s.size er meiri en 0, annars, hvað þú vilt hafa gerst? [Daniel] Return null? >> Aftur null, nákvæmlega. Svo ef s.size meiri en 0. Hvað þá erum við að fara að gera? Hvað gerum við ef stakkur er ekki tómur? [Stella] Þú lækka stærð? >> Þú lækka stærð, allt í lagi. Svo hvernig did þú að gera það? >> S.size--. [Hardison] Great. Og þá hvað gerðir þú? [Stella] og þá sagði ég aftur s.string [s.size]. [Hardison] Great. Annars aftur null. Já, Sam? [Sam] Hvers vegna er það ekki að vera s.size + 1? [Hardison] Plus 1? >> Já. >> Got það. [Sam] Ég hélt því að þú ert að taka 1 af, þá þú ert að fara að vera aftur ekki þá sem þeir báðu um. [Hardison] Og þetta var bara það sem við vorum að tala um með allri þessari útgáfu 0 vísitölum. Þannig að ef við rennum aftur hérna. Ef við lítum á þennan gaur hérna, getur þú séð að þegar við skjóta, við erum að pabbi er þáttur í vísitölu 2. 

Þannig að við draga stærð okkar fyrst, þá passar stærð okkar vísitölu okkar. Ef við lækka ekki stærð fyrst, þá verðum við að gera stærð -1 og þá lækka. Frábært. Allt gott? Einhverjar spurningar um þetta? There ert a tala af mismunandi leiðir til að skrifa þetta eins og heilbrigður. Í raun getum við gert eitthvað enn - við getum gert einn-Ferja. Við geta gera a einn-lína aftur. Þannig að við getum í raun lækka áður en við aftur með því að gera það. Svo setja á - fyrir s.size. Það gerir línan mjög þétt. Þar sem munurinn á milli -. S stærð og s.size-- er að þetta Postfix - þeir kalla það Postfix því - kemur eftir s.size-- þýðir að s.size er metin í þeim tilgangi að finna vísitölu eins og það er nú þegar þessi lína er keyrð, og þá er þetta - gerist eftir að línan fær framkvæma. Eftir að þátturinn á vísitölu s.size er skoðuð. Og það er ekki það sem við viljum, vegna þess að við viljum að lækka til að gerast fyrst. Othewise, ætlum við að vera að nota array, á áhrifaríkan hátt, út af mörk. Við ætlum að vera að nota frumefni yfir einn sem við viljum í raun og veru til að fá aðgang. Já, Sam? >> Er það hraðar og notað minna vinnsluminni til að gera í einni línu eða ekki? [Hardison] Heiðarlega, fer það virkilega. [Sam, óskiljanlegur] >> Já, fer það. Þú getur gert þýðanda bragðarefur til að fá þýðanda til að viðurkenna það, yfirleitt, ímynda ég. 

Þannig að við höfum getið svolítið um þessa hagræðingu þýðanda efni sem þú getur gert að safna saman, og það er góður af hlutur sem þýðandinn gæti verið fær um að reikna út, eins og ó, hey, kannski ég get gert þetta allt í einni aðgerð, eins og til að hlaða stærð breytu í frá RAM, decrementing það, geyma það aftur út, og þá setja hann inn aftur að vinna restina af þessari aðgerð. En venjulega, nei, þetta er ekki svoleiðis það er að fara að gera program verulega hraðar. Einhverjar fleiri spurningar um stafla? 

Svo ýta og pabbi. Ef þú krakkar vilja til reyna út tölvusnápur útgáfa, það sem við höfum gert á spjallþráð útgáfa er í raun farið og gerði þennan stafla vaxa virk. Áskorunin er aðallega hérna á ýta virka, að reikna út hvernig á að gera það fylki vaxa eins og þú halda áfram að þrýsta meira og meira atriði á að stafla. Það er í raun ekki of mikið til viðbótar kóða. Bara hringja til - þú verður að muna að fá símtöl á malloc þar almennilega, og þá reikna út hvenær þú ert að fara að hringja realloc. Það er gaman áskorun ef þú hefur áhuga. 

En um sinn, við skulum fara, og við skulum tala um biðraðir. Flettu í gegnum hér. Biðröð er náinn bróðir á mánudaginn. Svo á mánudaginn, var það að setja í síðasta var það fyrsta sem að þá vera sótt. Við höfum fengið þessa síðustu í, fyrst út, eða LIFO, röðun. En í biðröð, eins og þú vilt búast við frá þegar þú ert að standa í línu, fyrsta manneskjan til að komast í línu, the fyrstur hlutur til að komast í biðröð, er það fyrsta sem fær sóttir af biðröð. Biðraðir eru líka oft notað þegar við erum að fást við gröf, eins og við ræddum um stuttlega við stafla, og biðraðir eru einnig vel fyrir fullt af öðrum hlutum. Eitt sem kemur upp oft er að reyna að halda, til dæmis, a raðað lista af þáttum. Og þú getur gert þetta með fjölda. Þú getur haldið raðað lista af hlutum í fylki, en þar sem verður erfiður er þá verður þú alltaf að finna viðeigandi stað til að setja næsta hlutur. Svo ef þú ert með fjölda af tölum, 1 til 10, og þá þú vilt auka að öllum tölurnar 1 til 100, og þú ert að fá þessar tölur af handahófi og reyna að halda öllu raðað eins og þú fara í gegnum, enda þú upp að þurfa að gera a einhver fjöldi af að breytast. Með ákveðnum tegundum biðraðir og ákveðnar tegundir af undirliggjandi gögn uppbygging, þú getur í raun og veru að halda það nokkuð einfalt. Þú þarft ekki að bæta eitthvað og stokka allt hlutur í hvert skipti. Né hefur þú að gera a einhver fjöldi af að breytast í innri þætti í kring. Þegar við lítum á biðröð, sérðu að - einnig í queue.c í kafla númer - the struct sem við höfum gefið þér er í raun svipað og strúktúr sem við gáfum þér að stafla. 

Það er ein undantekning á þessu, og að ein undantekning er að við höfum þetta viðbótar heiltölu kallast höfuð, og höfuð er hér fyrir því að halda utan um höfuðið á biðröð, eða fyrsti þáttur í biðröð. Með stafla, við varúlfur fær til að halda utan um atriði sem við vorum að fara að sækja, eða efst á mánudaginn, nota bara stærð, en með biðröð, við erum að þurfa að takast á við móti endar. Við erum að reyna að tittur það á í lokin, en þá aftur það að framan. Svo í raun, með höfuð, höfum við vísitölu upphafi biðröð, og stærð gefur okkur vísitölu í lok biðröð svo að við getum sótt það úr höfðinu og bæta það á að rófu. Þar með á mánudaginn, við vorum bara alltaf að takast á við toppur af the stakkur. Við þurftum aldrei að opna neðst á stafla. Við bættum við bara það til the toppur og tók það burt af the toppur þannig að við ekki þurfum að auka sviði inni strúktúr okkar. Er að gera almennt skynsamleg? Allt í lagi. Já, Charlotte? [Charlotte, óskiljanlegur] [Hardison] Það er frábær spurning, og það var eitt sem kom upp í fyrirlestrinum. Kannski ganga í gegnum nokkur dæmi munu skýra hvers vegna við viljum ekki að nota Strings [0] sem forstöðumanns biðröð. 

Svo ímynda sér að við höfum biðröð okkar, við erum að fara að kalla það biðröð. Í upphafi, þegar við höfum bara instantiated það, þegar við höfum bara lýst henni, við höfum ekki frumstillt neitt. Það er allt sorp. Svo auðvitað við viljum tryggja að við frumstilla bæði stærð og höfuð sviðum til að vera 0, eitthvað sanngjarnt. Við gætum líka farið á undan og null út þætti í biðröð okkar. Og til að gera þetta línurit passa, eftir að nú biðröð okkar getur aðeins haldið þrjá þætti; en stafla okkar gæti haldið fjóra, biðröð okkar getur aðeins halda þrjú. Og það er bara að gera á myndinni passa. The fyrstur hlutur sem gerist hér er að við e, the band "hæ". Og rétt eins og við gerðum við á mánudaginn, ekkert hræðilega öðruvísi hér, við henda strenginn á á strengi [0] og hækka stærð okkar með 1. Við e, "bless", verður það sett á. Þannig lítur þetta út eins og stafla að mestu leyti. Við byrjaði hér nýr þáttur, nýr þáttur, stærð heldur að fara upp. Hvað gerist á þessum tímapunkti þegar við viljum dequeue eitthvað? Þegar við viljum dequeue, sem er þáttur sem við viljum dequeue? [Basil] Strengir [0]. >> Zero. Einmitt rétt, Basil. Við viljum losna við fyrsta band, þetta einn, "hæ". Svo það var annar hlutur sem breytt? Takið eftir þegar við smella eitthvað burt af stafla, breyting við bara stærð, En hér höfum við fengið nokkra hluti sem breyting. Ekki eini hjartarskinn the stærð breytast, en höfuðið breytingar. Þetta er að fara til baka til að benda Charlotte fyrr: hvers vegna höfum við þetta höfuð eins og heilbrigður? Er það gera vit nú, Charlotte? >> Eiginlega. [Hardison] Eiginlega? Og hvað gerðist þegar við dequeued? Hvað gerði höfuð að gera það nú er áhugavert? [Charlotte] Oh, því það breyttist - lagi. Ég sé. Þar sem höfuð - þar sem höfuðið er að benda á að breytingar í skilmálar af staðsetningu. Það er ekki lengur alltaf núll vísitölu einn. >> Já, nákvæmlega. Það sem gerðist var ef dequeueing hátt þáttur var gert og við ekki hafa þetta höfuð sviði vegna þess að við vorum alltaf að kalla þetta band á 0 vísitölu yfirmaður biðröð okkar, þá viljum við að færa restina af biðröð niður. Við myndum þurfa að skipta "bless" frá frá strengi [1] á strengi [0]. Og strengir [2] niður strengi [1]. Og við myndum þurfa að gera þetta fyrir alla lista af þáttum, allt array af þáttum. Og þegar við erum að gera það með fjölda, sem fær mjög dýrt. Svo hér, það er ekki stór samningur. Við höfum bara þrjá þætti í fylking okkar. En ef við hefðum biðröð af þúsund þætti eða milljón þætti, og þá allt í einu, við byrjum að gera fullt af dequeue kallar allt í lykkju hlutirnir eru í raun að fara að hægja á eins og það færist allt niður stöðugt. Þú veist, breyting um 1, vakt um 1, breyting um 1, breyting um 1. Stað, við notum þetta höfuð, sem við köllum það "bendillinn" jafnvel þó að það er ekki raunverulega a bendi í strangasta skilningi, er það ekki bendillinn tegund. Það er ekki int * eða char * eða eitthvað svoleiðis. En það að benda eða kynna höfuð biðröð okkar. Já? 

[Nemandi] Hvernig dequeue veit bara að skjóta burt hvað sem er í forsvari fyrir? [Hardison] Hvernig dequeue vita hvernig á að skjóta á hvað sem er í forsvari fyrir? >> Einmitt, já. >> Hvað það er að horfa á er bara allt höfuðið svæðið er sett í. Þannig að í þessu fyrsta tilfelli, ef við horfum hérna, höfuð okkar er 0, vísitölu 0. >> Einmitt. [Hardison] Svo það segir bara allt í lagi, vel, þáttur í vísitölu 0, strengurinn "hæ", er þáttur í höfuðið á biðröð okkar. Þannig að við erum að fara að dequeue manninn. Og það verður þáttur sem verður aftur til þess sem hringir. Já, Saad? >> Svo setur höfuð grundvallaratriðum - þar sem þú ert að fara að kemba henni? Það er að byrja á því? >> Já. >> Lagi. [Hardison] Það er að verða nýtt upphaf fyrir fylking okkar. Svo þegar þú dequeue eitthvað, allt sem þú þarft að gera er að opna hluti við vísitölu q.head, og það mun vera þáttur sem þú vilt dequeue. Þú þarft einnig að lækka stærð. Við munum sjá á hluti þar sem hlutirnir fá smá erfiður með þetta. Við dequeue, og nú, ef við e, aftur, hvar e, við? Hvar er næsta þáttur að fara í biðröð okkar? Segjum að við viljum e, the band "CS". Inn sem vísitalan mun það fara? [Nemendur] Strengir [2]. >> Two. Hvers vegna 2 og ekki 0? [Basil] Þar sem nú er höfuð 1, svo það er eins og byrjun á listanum? [Hardison] Rétt. Og hvað táknar að listanum er lokið? Hvað vorum við að nota til að tákna lok biðröð okkar? Höfuðið er yfirmaður biðröð okkar, upphaf biðröð okkar. Hvað er endir biðröð okkar? [Nemendur] stærð. >> Stærð, nákvæmlega. Svo ný atriði okkar fara í á stærð, og þá þætti sem við tökum burt koma utan á höfuð. Þegar við e, á næsta þátt, við erum að setja þau á stærð. [Nemandi] Áður en þú setur það í þó, stærð var 1, ekki satt? [Hardison] Rétt. Svo ekki alveg á stærð. Size +, ekki 1, en + höfuð. Þar sem við færst allt með höfuð upphæð. Svo hér, nú höfum við fengið biðröð af stærð 1 sem byrjar á 1 er vísitala neysluverðs. The hali er vísitalan 2. Já? 

[Nemandi] Hvað gerist þegar þú dequeue strengir [0], og rifa strengi 'í minni bara að tæma, í grundvallaratriðum, eða bara gleymt? [Hardison] Já. Í þessum skilningi, erum við bara að gleyma þeim. Ef við vorum að geyma afrit af þeim fyrir - margir gögn uppbygging verður oft geyma eigin eintök þeirra þátta þannig að sá sem stjórna gögn uppbygging þarf ekki að hafa áhyggjur um þar sem allir þessir ábendingar eru að fara. Gögnin uppbygging hefur á öllu, heldur á öllum eintökum, að ganga úr skugga um að allt heldur áfram á viðeigandi hátt. Hins vegar í þessu tilfelli, þessi gögn uppbygging bara fyrir einfaldleika, eru ekki að gera afrit af neinu sem við erum að geyma í þeim. [Nemandi] Svo er þetta samfelld fylking af -? >> Já. Ef við lítum til baka á það sem skilgreining var þessa uppbyggingu, er það. Það er bara staðall array eins og þú hefur séð, fylki af char * s. Er það -? >> Já, ég var bara að spá Ef þú munt að lokum keyra út af minni, að vissu marki, Ef þú hefur öll þessi tóm blettur í fylking þinni? [Hardison] Já, það er góður punktur. 

Ef við lítum á það sem gerðist nú á þessum tímapunkti, við höfum fyllt upp biðröð okkar, það lítur út eins og. En við höfum í raun ekki fyllt upp biðröð okkar vegna þess að við höfum biðröð sem er stærð 2, en það hefst á vísitölu 1, vegna þess að þar höfuð músina okkar er. Eins og þú varst að segja, að þáttur á strengi [0] á vísitölu 0, er ekki raunverulegt. Það er ekki í biðröð okkar lengur. Við bara ekki nenna að fara í og ​​skrifa það þegar við dequeued það. Svo jafnvel þó að það lítur út eins og við höfum keyrt út af minni, höfum við í raun ekki. Þessi blettur er í boði fyrir okkur að nota. Viðeigandi hegðun, ef við vorum að reyna og fyrstu dequeue eitthvað eins og "bless", sem myndi skjóta bless burt. Nú byrjar biðröð okkar á vísitölu 2 og er stærð 1. Og nú ef við reynum og e, eitthvað aftur, segja 50, 50 ætti að fara í stað á vísitölu 0 því það er enn í boði fyrir okkur. Já, Saad? [Saad] Er það gerast sjálfkrafa? [Hardison] Það gerist ekki alveg sjálfkrafa. Þú verður að gera stærðfræði til að gera það vinna, en í raun það sem við höfum gert er að við höfum bara vafið um. [Saad] Og er það allt í lagi ef það er gat í miðju það? [Hardison] Það er ef við getum gert stærðfræði vinna út almennilega. 

Og það kemur í ljós að það er í raun ekki það erfitt að gera við unga fólkið rekstraraðila. Svo bara eins og við gerðum með keisarans og dulritunarstjórneiningunni efni, með unga fólkið, getum við fengið það að vefja í kring og halda áfram kring og í kring og kring með biðröð okkar, halda að höfuð músina hreyfingu. Takið eftir að stærð er alltaf virða fjölda staka í raun í biðröð. Og það er bara höfuð músina sem heldur hjólreiðum gegnum. Ef við lítum á það sem gerðist hér, ef við förum aftur í upphafi, og þú horfa á það sem gerist á höfuðið þegar við e, eitthvað, ekkert gerðist í höfuð. Þegar við enqueued eitthvað annað, ekkert gerðist í höfuð. Fljótt og við dequeued eitthvað, sem höfuðið fer upp um einn. Við enqueued eitthvað, ekkert gerist í höfðinu. Þegar við dequeue eitthvað, yfirmaður allt í einu fær incremented. Þegar við e, eitthvað, ekkert gerist í höfðinu. 

Hvað myndi gerast á þessum tímapunkti ef við vorum að dequeue eitthvað aftur? Allar hugsanir? Hvað myndi gerast í höfðinu? Hvað ætti að gerast á höfuðið Ef við værum að dequeue eitthvað annað? Höfuðið núna er á vísitölu 2, sem þýðir að yfirmaður biðröð er strengir [2]. [Nemandi] sem skilar 0? >> Það ætti aftur á 0. Það ætti að vefja aftur í kring, nákvæmlega. Svo langt, í hvert skipti sem við kölluðum dequeue, höfum við verið að bæta eitt á höfði, bæta við einum til höfuðs, bæta við einum til höfuðs, bæta við einum á höfuðið. Um leið og þessi höfuð bendi fær til síðasta vísitölu í fylkingu okkar, þá verðum við að vefja hana aftur um í upphafi, að fara aftur til 0. [Charlotte] Hvað ákvarðar getu biðröð í stafla? [Hardison] Í þessu tilfelli höfum við bara verið að nota a # skilgreint stöðug. >> Lagi. [Hardison] í raun. C-skrá, þú getur farið í og ​​Muck með það svolítið og gera það eins stór eða eins litlu og þú vilt. [Charlotte] Svo þegar þú ert að gera það biðröð, hvernig gera þú tölva vita hversu stór þú vilt að stafla til að vera? [Hardison] Það er frábær spurning. There ert a par af leiðir. Eitt er bara að skilgreina það upp fyrir framan og segja að þetta er að fara að vera biðröð sem hefur 4 þætti eða 50 þætti eða 10.000. Hin leiðin er að gera það sem útgáfa spjallþráð fólk eru að gera og búa til aðgerðir til að hafa biðröð vaxa dynamically eins og fleiri hlutir fá bætt inn 

[Charlotte] Svo til að fara með fyrsta valkost, ekki hvað setningafræði þú notar að segja forrit hvað er stærð af the biðröð? [Hardison] Ah. Svo skulum við fá út úr þessu. Ég er enn í stack.c hér, þannig að ég ætla bara að fara að fletta upp á toppinn hér. Getur þú séð þetta hérna? Þetta er # skilgreina getu 10. Og þetta er næstum nákvæmlega sama setningafræði sem við höfum fyrir biðröð. Nema í biðröð, þá erum við að auka strúktúr sviði hér. [Charlotte] Ó, ég hélt að getu þýddi getu fyrir band. [Hardison] Ah. >> Að það er hámarks lengd orðsins. >> Got það. Já. The getu hér - það er frábært lið. Og þetta er eitthvað sem er erfiður vegna þess hvað við höfum lýst hér er fylki af char * s. An array af ábendingum. Þetta er fylki af tákn. Þetta er líklega það sem þú hefur séð þegar þú hefur verið að lýsa biðminnin þínum að skrá I / O, þegar þú hefur verið að skapa strengi höndunum á mánudaginn. En það sem við höfum hér er fylki af char * s. Svo það er fylki af ábendingum. Reyndar, ef við rennum aftur út og við lítum á það sem er að gerast hér í framsetningu, sérðu að í raun frumefni, eðli gögn er ekki geymt innan fylkisins sjálfs. Hvað er geymt í fylkingu okkar hér eru ábendingar um eðli gagna. Allt í lagi. Þannig að við höfum séð hvernig stærð biðröð er bara eins og með á mánudaginn, stærð virðir alltaf fjölda staka nú í biðröð. Eftir að 2 enqueues, stærð er 2. Eftir að dequeue stærð er nú 1. Eftir að annað e, stærð er aftur upp í 2. Svo virðir stærð ákveðið fjölda staka í biðröð, og þá heldur höfuð bara hjólreiðum. Það fer frá 0-1-2, 0-1-2, 0-1-2. Og í hvert skipti sem við köllum dequeue, fær höfuð bendi incremented til næsta vísitölu. Og ef hausinn er um það bil að fara yfir, lykkjur það aftur um að 0. Svo með það, við getum skrifað dequeue virka. Og við erum að fara að fara á e, virka fyrir ykkur að koma í staðinn. 

Þegar við dequeue stak úr biðröð okkar, hvað var það fyrsta sem Daníel gerði þegar við byrjuðum að skrifa pop virka fyrir stafla? Leyfðu mér að heyra frá einhverjum sem hefur ekki talað enn. Við skulum sjá, Saad, manstu hvað Daniel gerði sem fyrsta sem hann skrifaði pop? [Saad] Það var, það var - >> hann prófa eitthvað. [Saad] Ef stærð er meiri en 0. >> Einmitt. Og hvað var það próf fyrir? [Saad] Það var próf til að sjá hvort það er eitthvað inni í array. [Hardison] Já. Einmitt. Svo þú getur ekki skjóta neitt út á mánudaginn ef það er tómt. Sömuleiðis, þú getur ekki dequeue neitt úr biðröð ef það er tómt. Hvað er það fyrsta sem við ættum að gera í aðgerð dequeue okkar hér, heldur þú? [Saad] Ef stærð er meiri en 0? >> Já. Í þessu tilfelli, ég hef reyndar bara prófað að sjá hvort það er 0. Ef það er 0, þá getum við aftur null. En nákvæmlega sama röksemdafærsla. Og við skulum halda áfram með þetta. Ef stærð er ekki 0, hvar er atriði sem við viljum að dequeue? [Saad] Á höfðinu? >> Einmitt. Við getum bara draga út fyrsta frumefnið í biðröð okkar með aðgang að þáttur í höfuðið. Ekkert brjálaður. Eftir það, hvað eigum við að gera? Hvað þarf að gerast? Hver var annar hlutur sem við ræddum um í dequeue? Tveir hlutir að gerast, vegna þess að biðröð okkar hefur breyst. [Daniel] minnka. >> Við verðum að draga úr stærð og auka höfuð? Einmitt. Til að auka höfuð, getum við ekki bara í blindni að auka höfuð, man. Við getum ekki bara gert queue.head + +. Við verðum einnig að láta þetta unga fólkið með getu. Og hvers vegna unga fólkið við með getu, Stella? [Stella] Vegna þess að það þarf að vefja í kring. >> Einmitt. Við unga fólkið við getu þar sem það þarf að vefja aftur um að 0. Svo nú, á þessum tímapunkti, getum við gert það sagði Daníel. Við getum lækka stærð. Og þá getum við bara aftur á atriði sem var efst í biðröð. Það lítur konar gnarly í fyrstu. Þú gætir hafa spurningu. Því miður? 

[Sam] Hvers vegna er fyrsta efst í biðröð? Hvar er það að fara? [Hardison] Það kemur frá fjórða línu frá botni. Eftir að við próf til að ganga úr skugga um að biðröð okkar er ekki tómur, við draga út char * fyrst, draga okkur út þáttur sem situr á höfuð vísitölu um fjölda okkar, strengja array okkar >> og kalla það fyrsta? [Hardison] Og við köllum það fyrst. Já. Bara að fylgja eftir því, hvers vegna heldur þú að við þurftum að gera það? [Sam] Hver fyrsta er bara aftur q.strings [q.head]? >> Já. >> Þar sem við erum að gera þetta að breytast í q.head með mod virka, og það er engin leið að gera það innan línu aftur líka. [Hardison] Einmitt. Þú ert blettur á. Sam er alveg spot on. Ástæðan að við þurftum að draga út fyrsta frumefnið í biðröð okkar og geyma það í breytu er vegna þessa línu þar sem við höfðum bara q.head, Það er unga fólkið rekstraraðila í það er eitthvað sem við getum ekki og hafa tekið það áhrif á höfuðið án - í einni línu. Þannig að við höfum í raun og veru að draga út fyrsta frumefnið, þá stilla höfuð, stilla stærð, og síðan aftur um hluti sem við dreginn út. Og þetta er eitthvað sem við munum sjá koma upp síðar með tengd listum, eins og við leika í kring með þeim. Oft þegar þú ert frjáls eða ráðstafa tengd listum þú þarft að muna eftir næsta þátt, næsta músina í tengda listanum áður ráðstafa núverandi einn. Vegna annars henda upplýsingar um hvað er eftir í listanum. Nú, ef þú ferð til tæki þitt, opnast upp queue.c--X af þessu. Svo ef ég opna queue.c, láta mig zoom hér, þú munt sjá að þú ert með svipuð-útlit skrá. Líkur-útlit skrá hvað við höfðum áður við stack.c. Við höfum fengið strúktúr okkar fyrir biðröð skilgreint eins og við sáum á glærum. 

Við höfum e, virka okkar sem er fyrir þig að gera. Og við höfum dequeue virka hér. The dequeue virka í skrá er unimplemented, en ég ætla að setja það aftur upp á PowerPoint þannig að þú getur slegið það inn, ef þú vilt. Svo næstu 5 mínútur eða svo, þið vinna á e, sem er nánast bara hið gagnstæða á dequeue. Þú þarft ekki að stilla höfuðið þegar þú ert enqueueing, en hvað hefur þú að stilla? Stærð. Svo þegar þú e,, höfuð dvöl ósnortið, fær stærð breyst. En það er að taka smá - þú verður að leika í kring með því að unga fólkið að reikna út nákvæmlega hvað vísitala nýja þáttur ætti að vera sett á. Svo ég ætla að gefa ykkur smá, setja dequeue aftur upp á mynd, og eins og þú krakkar hafa spurningar, hrópa þá út svo að við getum allt tal um þá sem hóp. Einnig, með það sem þú áttina - þegar þú stilla stærð, getur þú alltaf bara - þú þarft að unga fólkið stærð alltaf? [Daniel] Nei >> Þú þarft ekki að unga fólkið á stærð, ekki satt. Þar sem stærð verður alltaf, ef Ertu - hrokafullur þú ert að stjórna það á viðeigandi hátt, stærð verður alltaf að vera á milli 0 og 3. Hvar telur þú að unga fólkið þegar þú ert að gera e,? [Nemandi] Aðeins fyrir höfuð. >> Aðeins fyrir höfuð, nákvæmlega. Og af hverju þarftu að unga fólkið á allt í e,? Hvenær er ástand þar sem þú vilt að unga fólkið? [Nemandi] Ef þú hefur efni á rými, eins og á bilum 1 og 2, og þá þarf að bæta eitthvað á 0. [Hardison] Já, nákvæmlega. Svo ef höfuð bendillinn er á enda, eða ef stærð þinni plús höfuðið er stærri, eða öllu heldur, er að fara að vefja í kringum biðröð. 

Þannig að í þessu ástandi sem við höfum fengið upp hér á mynd núna, ef ég vil e, eitthvað núna, við viljum e, eitthvað á vísitölu 0. Svo ef þú horfir á þar sem 50 fer og ég kalla e, 50, það fer niður á botn. Það fer í 0 vísitölunni. Það kemur í stað "hæ" sem var þegar dequeued. [Daniel] Ert þú ekki að hugsa um að í dequeue þegar? Hvers vegna er það að gera eitthvað með höfuðið í e,? [Hardison] Ó, svo þú ert ekki að breyta í höfuðið, því miður. En þú verður að nota unga fólkið rekstraraðila þegar þú ert að fá aðgang þáttur sem þú vilt e, þegar þú ert að fá aðgang næsta þáttur í biðröð þinn. [Basil] Ég vissi ekki að gera það, og ég fékk "árangri" á það. [Daniel] Ó, ég skil hvað þú ert að segja. [Hardison] Svo þú didn't - þú gerðir bara á q.size? [Basil] Já. Ég var að breyta hliðar, gerði ég ekki að gera neitt með höfuð. [Hardison] Þú þarft í raun ekki að endurstilla hann höfuð til að vera eitthvað, en þegar þú vísitölu í strengi fylking, þú ert í raun að fara á undan og reikna hvar næsta þáttur er, því withe á mánudaginn, næsta þáttur í stafla þinn var alltaf á vísitölu samsvarar stærð. Ef við lítum til baka upp á stafla ýta virka okkar, við gætum alltaf plunk í nýja frumefni okkar rétt á stærð vísitölu. Þar með biðröð, getum við ekki gert það því ef við erum í þessu ástandi, ef við enqueued 50 okkar nýr strengur myndi fara rétt á strengi [1] sem við viljum ekki gera. Við viljum hafa nýja band fara á vísitölu 0. 

Hver hjartarskinn - já? [Nemandi] Ég er með spurningu, en það er í raun ekki tengt. Hvað þýðir það þegar einhver bara kalla eitthvað eins og pred músina? Hvað er það nafn stytting? Ég veit að það er bara nafn. [Hardison] pred músina? Við skulum sjá. Í hvaða samhengi? [Nemandi] Það var að setja inn. Ég get spurt þig seinna ef þú vilt því það er í raun ekki tengd, en ég bara - [Hardison] Frá kóða setja inn Davíðs frá fyrirlestri? Við getum draga það upp og tala um það. Við munum tala um það næst, þegar við komumst í tengdum listum. 

Svo skulum mjög fljótt að líta á það sem e, virka lítur út. Hvað var það fyrsta sem að fólk reyndi að gera í e, línu? Í þessari biðröð? Líkur á því sem þú gerðir fyrir stafla þrýsta. Hvað gerðir þú, Stella? [Stella, óskiljanlegur] [Hardison] Einmitt. Ef (q.size == getu) - Ég þarf að setja axlabönd mína á réttum stað - return false. Zoom í smá. Allt í lagi. Nú hvað er það næsta sem að við þurftum að gera? Rétt eins og með á mánudaginn, og sett á réttum stað. Og svo það sem var rétti staðurinn til að setja þetta? Með stafla var vísitölu stærð, með þessu það er ekki alveg svo. [Daniel] Ég q.head--eða - >> q.strings? >> Já. q.strings [q.head + q.size unga Stærð]? [Hardison] Við viljum líklega að setja sviga um þetta þannig að við erum að fá viðeigandi forgang og svo er cleart við alla. Og setja það jafnt? >> Að str? >> Til str. Frábært. Og nú er það síðasta sem að við verðum að gera? Rétt eins og við gerðum á mánudaginn. >> Vöxtur stærð? >> Vöxtur stærð. Boom. Og svo, þar sem ræsir kóða bara aftur rangt við vanræksla, við viljum breyta þessu til sönn ef allt fer í gegnum og allt gengur vel. Allt í lagi. Það er a einhver fjöldi af upplýsingar um kafla. Við erum ekki alveg yfir. Við viljum tala í raun fljótt um ein sér-tengd listum. Ég setti þetta upp þannig að við getum farið aftur að því síðar. En við skulum fara aftur til kynningu okkar fyrir aðeins nokkrum fleiri glærum. Svo er e, TODO, nú höfum við gert það. 

Nú skulum taka a líta á ein sér-tengd listum. Við ræddum um þetta svolítið meira í fyrirlestrinum. Hversu margir af ykkur sá kynningu þar sem við höfðum fólk awkwardly benda hver öðrum og halda tölur? >> Ég var í því. >> Hvað gerðir þú krakkar hugsa? Gerði það, vonandi demystify þessar smá? Með lista, snýr það út að við að takast á við þessa tegund sem við erum að fara að hringja í hnút. En við biðröð og stafla við höfðum structs sem við myndum kalla biðröð í mánudaginn, við höfðum þessar nýju biðröð í tegundum stafla, hér listi er í raun bara byggt upp af fullt af hnúður. Á sama hátt og strengir eru bara fullt af chars allt raðað upp við hliðina á hvort öðru. A tengd listi er bara hnút og annar hnútur og annar hnútur og annar hnútur. Og frekar en frábær alla hnúta saman og geyma þá contiguously allt í lagi við hliðina á hvor aðra í minni, hafa þetta á næsta músina gerir okkur kleift að geyma hnúður hvar, af handahófi. Og svo konar vír þá alla saman til að benda frá einum til annars. 

Og það var stór kostur að það hafði yfir fylki? Yfir geyma allt contiguously bara fastur við hliðina á hvort öðru? Þú manst? Já? >> Dynamic minni úthlutun? >> Dynamic minni úthlutun í hvaða skilningi? [Nemandi] Í því að þú getur haldið að gera það stærri og þú þarft ekki að færa alla array þinn? [Hardison] Einmitt. Svo með fjölda, þegar þú vilt að setja nýja hluti í the miðja af það, þú þarft að skipta öllu til að gera pláss. Og eins og við ræddum um við biðröð, þessi 'hvers vegna við höldum að höfði músina, þannig að við erum ekki stöðugt að breytast hlutina. Vegna þess að það verður dýrt ef þú hefur got a stór fylki og þú ert stöðugt að gera þessar handahófi ísetningar. Þar með lista, allt sem þú þarft að gera er að henda hana á nýjan hnút, stilla ábendingum, og þú ert búinn. Hvað sjúga um þetta? Innskot frá þeirri staðreynd að það er ekki eins auðvelt að vinna með eins og fylki? Já? [Daniel] Jæja, ég held að það er miklu erfiðara að fá aðgang að tiltekna þáttur í tengda listanum? [Hardison] Þú getur ekki bara hoppað til handahófi þáttur í the miðja af tengslum þínum. Hvernig ert þú að gera það í staðinn? >> Þú þarft að stíga í gegnum allt hlutur. [Hardison] Já. Þú þarft að fara í gegnum einn í einu, einn í einu. Það er mikið - það er sársauki. Hvað er annað - það er annað fall á þessu. [Basil] Þú getur ekki farið fram og aftur á bak? Þú þarft að fara eina átt? [Hardison] Já. Svo hvernig leysa við það, stundum? [Basil] tvöfalt tengdar listum? >> Einmitt. Það eru tvöfalt-tengd listum. Það eru einnig - því miður? 

[Sam] Er það það sama og að nota pred hlutur að - Ég mundi bara, er það ekki það sem pred hlutur er fyrir? Er það ekki á milli tvöfalt og ein sér? [Hardison] við skulum líta á hvað nákvæmlega hann var að gera. Svo hér við fara. Hér er listi kóða. Hér höfum við predptr, hér. Er þetta það sem þú varst að tala um? Svo þetta var - hann er frjáls lista og hann er að reyna að geyma bendi til þess. Þetta er ekki tvöfalt, eintengdum-listum. Við getum talað meira um þetta seinna þar sem þetta er að tala um frjáls lista og ég vil að sýna annað efni fyrst. en það er bara - það er að muna gildi PTR [Nemandi] Ó, það er undanförnum músina? >> Já. Svo að við getum þá hækka PTR sig áður en við þá frjáls hvað predptr er. Þar sem við getum frjáls PTR og þá ekki kalla PTR = PTR næst, ekki satt? Það væri slæmt. Svo skulum við sjá, aftur á þennan gaur. 

Hin slæmur hlutur óður í listum er að þar með fjölda við höfum bara öll þau atriði sjálfir staflað við hliðina á hvort öðru, hér við einnig hafa kynnt þetta bendi. Svo er það til viðbótar klumpur af minni sem við erum að þurfa að nota fyrir hvert atriði sem við erum að geyma á listanum okkar. Við fáum sveigjanleika, en það kemur á kostnað. Það kemur með þessum tíma kostnaður, og það kemur með þessu minni kostnað líka. Tími í þeim skilningi sem við höfum nú til að fara í gegnum hvert frumefni í fylkinu að finna einn á vísitölu 10, eða sem hefði verið vísitölu 10 í fylki. 

Bara mjög fljótt, þegar við skýringarmynd úr þessum listum, yfirleitt við að halda áfram til höfuð á listanum eða fyrstu músina á listanum og athugið að þetta er satt músina. Það er bara 4 bæti. Það er ekki raunverulegt hnút sjálft. Svo þú sérð að það hefur ekkert int gildi í það, ekki næsta músina í henni. Það er bókstaflega bara músina. Það er að fara að benda á eitthvað sem er í raun hnút strúktúr. [Sam] A bendillinn kallast hnút? >> Er þetta - enginn. Þetta er bendi á eitthvað af hnút tegund. Það er bendillinn í hnút strúktúr. >> Ó, allt í lagi. Skýringarmynd á vinstri, númer á hægri. Við getum sett það á NULL, sem er góð leið til að byrja. Þegar þú skýringarmynd það, skrifa annaðhvort það sem núll eða þú setur línu í gegnum það eins og það. 

Ein af auðveldustu leiðum til að vinna með lista, og við biðjum að þú bæði prepend og bæta til að sjá muninn á milli tveggja, en prepending er ákveðið auðveldara. Þegar þú prepend, þetta er þar sem þú - þegar þú prepend (7), þú ferð og búa til hnút strúktúr og þú setur fyrst að benda á það, því að nú, þar sem við prepended það, það er að fara að vera í upphafi listanum. Ef við prepend (3), sem skapar annan hnút, en nú 3 kemur fyrir 7. Þannig að við erum í raun að þrýsta það á listanum okkar. Nú getur þú séð að prepend, stundum fólk kalla það ýta, vegna þess að þú ert að ýta nýja hluti á listanum þínum. Það er einnig auðvelt að eyða fyrir framan lista. Svo fólk verður oft kalla að skjóta. Og á þann hátt, er hægt að líkja stafla með því að nota tengda listanum. Úpps. Því miður, nú erum við að fá inn auka. Svo hér við prepended (7), nú erum prepend (3). Ef við prepended eitthvað annað á þessum lista, ef við prepended (4), þá við myndum hafa 4 og svo 3 og svo 7. Svo við gætum skjóta og fjarlægja 4, Fjarlægja 3, fjarlægja 7. Oft er meira innsæi leið til að hugsa um þetta með auka. Þannig að ég hef diagrammed út hvað það myndi líta út eins og auka hér. Hér fylgja (7) ekki líta allir öðruvísi vegna þess að það er bara einn þáttur í listanum. Og appending (3) setur það í lokin. Kannski er hægt að sjá núna að bragð með auka er að þar sem við vitum bara hvar byrjunin á listanum er, til að bæta við lista sem þú þarft að ganga alla leið í gegnum að fá að enda, hætta, þá byggja hnút og plunk allt niður. Víra allt draslið upp. Svo með prepend, eins og við morðingi bara í gegnum þetta mjög fljótt, þegar þú prepend til lista, það er frekar einfalt. 

Þú gerir nýjan hnút þinn, taka sumir dynamic minni úthlutun. Svo hér erum við að gera hnút strúktúr með malloc. Svo malloc við erum að nota vegna þess að það verður sett til hliðar minni fyrir okkur þar til seinna vegna þess að við viljum ekki þetta - við viljum þetta minni að hverfa í langan tíma. Og við fáum bendi á pláss í minninu sem við úthlutað bara. Við notum stærð hnút, við summa ekki reitina. Við gerum ekki handvirkt að búa til fjölda bæti, í stað notum við sizeof svo að við vitum að við erum að fá viðeigandi fjölda bæti. Við tryggjum að prófa að malloc kalla okkar tók. Þetta er eitthvað sem þú vilt gera almennt. Á nútíma vélar, keyra út af minni er ekki eitthvað sem er auðvelt nema þú ert að úthluta tonn af efni og gera a gríðarstór listi, en ef þú ert að byggja upp efni fyrir, segja, eins og iPhone eða Android, þú ert takmarkað fjármagn minni, sérstaklega ef þú ert að gera eitthvað mikil. Svo það er gott að komast í framkvæmd. 

Takið eftir að ég hef notað nokkrar mismunandi aðgerðir hér sem þú hefur séð sem eru eins konar nýr. Svo fprintf er bara eins og printf nema fyrstu röksemd hennar er straum sem þú vilt prenta. Í þessu tilviki, við viljum að prenta á staðalskekkja band sem er mismunandi frá venjulegu outstream. Við vanræksla það sýnir sig á sama stað. Það prentar einnig út á flugstöðina, en þú getur - nota þessar skipanir sem þú lært um, aðlögun tækni þú lært um í vídeó Tommy fyrir setja vandamál 4, er hægt að stjórna því á mismunandi sviðum, þá hætta, hérna, hættir program. Það er í raun eins og aftur úr helstu, nema við notum hætta því hér aftur mun ekki gera neitt. Við erum ekki í aðal, svo aftur ekki loka forritinu eins og við viljum. Þannig að við notum að hætta virka og gefa það villa merkjamál. Þá hér við setja gildi sviði nýja Hnútur er, i sínu sviði til að vera jafn i, og þá erum við vír það upp. Við setjum næstu músina nýja Hnútur til að benda á fyrst, og þá fyrst verður nú að benda á nýjan hnút. Þessar fyrstu línur af kóða, erum við í raun að byggja upp nýjan hnút. Ekki síðustu tvær línur af þessari aðgerð en hinar fyrri. Þú getur í raun draga út í aðgerð, í hjálpar virka. Það er oft það sem ég er, draga ég það út í aðgerð Ég kalla það eitthvað eins og að byggja hnút, og það heldur prepend virka frekar lítið, það er bara 3 línur þá. Ég að hringja í minn byggja hnút virka, og þá er ég vír allt upp. 

Endanleg sem ég vil að sýna þér, og ég ætla að láta þig gera auka við og allt það á eigin spýtur, er hvernig á að iterate á lista. Það eru fullt af mismunandi leiðir til að iterate á lista. Í þessu tilfelli erum við að fara að finna lengd lista. Svo erum við að byrja með lengd = 0. Þetta er mjög svipað og að skrifa strlen fyrir streng. Þetta er það sem ég vil að sýna þér, þetta fyrir lykkju hérna. Það lítur soldið angurvær, það er ekki venjulega int i = 0, i <hvað, i + +. Þess í stað er Frumstilli breytu n okkar að vera upphafið af listanum. Og svo meðan Iterator breyta okkar er ekki núll, halda við að fara. Þetta er vegna þess að með því að venju, enda lista okkar verður null. Og þá að hækka, frekar en að gera + +, tengda lista jafngildir + + er n = n-> Næsta. 

Ég læt þig fylla í eyðurnar hér vegna þess að við erum út á tíma. En að hafa þetta í huga þegar þú vinnur á psets spellr þínum. Tengd listum, ef þú ert að framkvæma kjötkássa borð, mun örugglega koma sér einstaklega vel. Og hafa þetta orðfæri til að lykkja yfir það mun gera líf mun auðveldara, vonandi. Einhverjar spurningar, fljótt? [Sam] Ætlarðu að senda út lokið SLL og SC? [Hardison] Já. Ég sendi út lokið skyggnur og lauk SLL stafla og queue.cs. [CS50.TV]