[Powered by Google Translate] [6. jagu vähem mugavad]
[Nate Hardison] [Harvardi Ülikool]
[See on CS50.] [CS50.TV]
Hea küll. Tere 6. jagu.
Sel nädalal läheme räägime andmestruktuurid punktis,
peamiselt seetõttu, et selle nädala probleem seatud spellr
Kas terve hulk erinevaid andmeid struktuuri uurimine.
Seal on hunnik erinevaid viise saab minna lahendamist,
ja rohkem andmestruktuurid sa tead, seda rohkem lahedaid asju saab teha.
>> Nii et hakkame pihta. Esiteks me ei kavatse rääkida korstnad,
korstnat ja järjekorda andmestruktuurid et me ei kavatse rääkida.
Hoidla ja järjekorrad on tõesti kasulik, kui me hakkame rääkima graafikud,
mis me ei kavatse teha nii palju kohe.
Aga nad on tõesti hea mõista üks suur fundamentaalne andmestruktuurid CS.
Kirjeldus lahendamist spetsifikatsioon,
kui te tõmmake see üles, räägib korstnad nagu sarnane
kuhja söögituba plaate, et teil on kohviku juures söögisaali
kus kui söögituba personal tuleb ja paneb söögituba plaate välja pärast olen puhastada neid,
nad virna neid üks peal teine.
Ja siis kui lapsed tulevad, et süüa saada,
nad tõmmake plaate välja esimene top üks, siis teine ​​selle all seda, siis üks allpool seda.
Niisiis, tegelikult, esimene plaat, mis söögituba personal panema on viimane, mis saab maha võetud.
Viimane, et söökla töötajad panna on esimene, mis saab maha võetud õhtusöögile.
Kui probleem kogumi spec, mille saate alla laadida kui te seda juba teinud pole,
me räägime modelleerimine korstnat andmete plokk kasutades sellist struct.
>> Mida meil siin, see on sarnane sellele, mis oli esitatud loeng,
välja arvatud loeng tutvustasime seda ints mitte char * s.
See saab olema korstnat, mis salvestab mida?
Daniel? Mida me ladustamiseks selles korstnat?
[Daniel] stringid? >> Me stringide salvestamiseks, see korstna täpselt.
Kõik, mida vaja on, et luua pinu on massiiv
konkreetse võimsus, mis antud juhul
võimsus saab olema kõik mütsid, sest see on pidev.
Ja siis lisaks massiivi kõik peame lugu on praegune suurus massiiv.
Üks asi märkida siin, et on selline lahe
on see, et me luua laotud andmestruktuur peal teine ​​andmestruktuur, massiiv.
On erinevaid viise, kuidas rakendada korstnad.
Me ei tee seda päris veel, kuid loodetavasti pärast teeme seotud nimekirja probleemid,
näete, kuidas saate hõlpsasti rakendada korstna peal lingitud nimekiri samuti.
Aga nüüd, me jääda massiivid.
Nii et taas, kõik me vajame, on massiiv ja me lihtsalt vaja jälgida suurusest massiivist.
[Sam] Vabandust, miks on nii, et sa ütlesid, et korstnat on peal stringid?
Mulle tundub, stringid kuuluvad pinu.
[Hardison] Jah. Loome me viime meie massiivi andmestruktuur -
see on hea küsimus. Seega on küsimus selles, miks inimesed, kes vaatavad seda online,
Miks me öelda, et korstnat on peal stringid,
sest siin tundub, stringid on sees korstna?
Mis on täiesti puhul.
Mida ma viitasin oli see, et meil on massiiv andmete struktuuri.
Meil array char * s, seda massiivi stringe,
ja me lisada, et selleks, et luua laotud andmestruktuur.
>> Nii et korstnat on veidi keerulisem kui massiivi.
Me saame kasutada massiivi luua pinu.
Nii et kui me ütleme, et pakk on ehitatud peal massiivi.
Samamoodi nagu ma juba ütlesin, me saame ehitada korstna peal seotud nimekirja.
Selle asemel, kasutades massiivi hoida meie elemente,
saaksime kasutada seotud nimekirja hoida meie elemendid ja ehitada korstna ümber selle.
Vaatame läbi kõndida paar näidet vaadates mingi kood,
näha, mis tegelikult toimub siin.
Vasakul olen visati alla, mida see korstna struct näeks mälu
kui tootmisvõimsuse # defineeritud neli.
Meil meie nelja-element char * massiiv.
Meil stringid [0], stringid, [1] stringid [2], stringid, [3]
ja siis see viimane ruumi meie suurus täisarv.
Kas see on mõttekas? Okei.
Nii juhtub, kui ma teen paremal
mis on minu kood, on lihtsalt kuulutada struct, laotud struct nimetatakse s.
See on see, mida me saame. Selles sätestatakse see jalajälg mällu.
Esimene küsimus on see, mida on sisu see korstna struct?
Just nüüd on nad midagi, kuid nad ei ole täiesti midagi.
Nad on selline prügi. Meil pole aimugi, mis see neile.
Kui me kuulutame korstnat s, me lihtsalt viskamine et alla peal mälu.
See on selline nagu kuulutatakse int i ja ei lähtestamisel.
Sa ei tea, mis seal sees on. Te saate lugeda, mis seal on,
kuid see ei pruugi olla super abivalmis.
Üks asi, mida tahame alati meeles, et vaja on initsialiseerida iganes tuleb initsialiseerida.
Sel juhul me ei kavatse initsialiseerida suurus on null,
sest et läheb osutuda meie jaoks väga oluline.
Võiksime minna ja initsialiseerida kõik suunanäitajaks, kõik char * s,
olema mingi arusaadav väärtus, ilmselt null.
Aga see ei ole täiesti vajalik, et me seda teeme.
>> Nüüd, kaks peamist tegevust korstnad on?
Keegi mäletab alates loeng mida te teete korstnad? Jah?
[Stella] lükkamine ja popping? >> Täpselt.
Lükkamine ja popping on kaks peamist tegevust korstnad.
Ja mida see lükke teha? >> See paneb midagi peale üles
virna ja siis paugu võtab selle ära.
[Hardison] Täpselt. Nii surudes vajutab midagi peal virnas.
See on nagu söökla personal paneb söögituba kandikut kohta counter.
Ja popping võtab söögituba plaat välja pinu.
Vaatame läbi kõndida paar näidet sellest, mis juhtub
kui vajutada asjad virna.
Kui me push string "tere" peale meie korstnat
see on see, mida meie diagramm näeks nüüd.
Vaata, mis juhtub?
Me tõugatakse esimene osa meie stringide massiiv
ja me upped meie suuruste arv on 1.
Nii et kui me vaatame vahe kahe slaidid, siin oli 0, siin on enne viik.
Siin on pärast viik.
Enne push pärast viik.
Ja nüüd on meil üks osa meie pinu.
See on string "tere", ja ongi kõik.
Kõik muu massiiv, meie stringide massiiv, on ikka prügi.
Me pole käivitatud, siis.
Oletame, et me push teise stringi peale meie pinu.
Me läheme push "maailma" kohta seekord.
Nii et näete, "maailm" siin läheb peale "tere",
ja suurus kokku ulatub kuni 2.
Nüüd saame push "CS50", ja et lähen peal jälle.
Kui me tagasi minna, saate näha, kuidas me surudes asju pinu.
Ja nüüd saame pop.
Kui me hüppasid midagi välja virna, mis juhtus?
Kas keegi nägi midagi? See on päris peen.
[Student] suurus. >> Jah, suurust muuta.
>> Mis muidu olete muutu?
[Student] stringid, liiga. >> Õigus. Stringid liiga.
Tuleb välja, et kui sa teed seda nii,
sest me ei kopeerimist elemendid meie korstnat
me tegelikult ei pea midagi tegema, me võime lihtsalt kasutada suurus
jälgida mitmeid asju meie massiivi
nii et kui me pop uuesti, jälle me lihtsalt kahandab meie suurus kuni 1.
Ei ole vaja tegelikult minna ja kirjutada midagi.
Kuidagi kahtlane.
Tuleb välja, et me tavaliselt lihtsalt jätta asju üksi, sest see on vähem tööd meile, mida teha.
Kui me ei pea minema tagasi ja kirjuta midagi, siis miks seda teha?
Nii et kui me pop kaks korda maha virna, kõik mis teeb on aland suurus paar korda.
Ja jälle, see on ainult sellepärast, et me ei kopeerimise asjad meie pinu.
Jah? Lase käia.
[Student, arusaamatult] >> Ja mis siis juhtub, kui vajutada midagi jälle?
Kui vajutada midagi uuesti, kus see kadus?
Kuhu see viib, Basil? >> Into stringid [1]? >> Õigus.
Miks ei ta lähe stringid? [3]
[Basiilik] Sest see unustasin, et seal oli midagi stringid [1] ja [2]?
[Hardison] Täpselt. Meie stack sisuliselt, "unustas", et ta hoiab kinni midagi
palmikutes [1] või stringid [2], nii et kui me push "woot"
see lihtsalt paneb seda arvesse element on string [1].
Kas on mingeid küsimusi selle kohta, kuidas see töötab, on algtasemel?
[Sam] Nii see ei ole dünaamiline kuidagi, nii summa
või nii suuruse korstnat?
[Hardison] Täpselt. See on - mõte oli, et see ei olnud dünaamiliselt growning pinu.
See on pinu, mis mahutab kõige rohkem neli char * s, kõige rohkem neli asja.
Kui me proovida ja push 1/5 asja, mida peaks teie arvates juhtub?
[Õpilased, arusaamatult]
[Hardison] Täpselt. On mitmeid asju, mis võib juhtuda.
See võiks seg süü, sõltuvalt sellest, mida me olime -
kuidas täpselt me ​​rakendamisel back-end.
See võiks kirjutada. See võiks olla, et buffer overflow, et me rääkisime klassis.
Mis oleks kõige ilmsem asi, mis võib üle kirjutada
kui üritasime suruda pildi asi meie korstnat?
Nii et te mainisite buffer overflow.
Mis võib olla asi, et saaksin üle kirjutada või stomped
kui me ajama kogemata üritab suruda pildi asi?
[Daniel, arusaamatult] >> Võimalikud.
Aga esialgu, mis võib juhtuda? Mida teha, kui üritasime suruda Neljas asi?
See võib hävitada suurus, vähemalt selle mälu diagramm, mis meil on.
>> Kui probleem komplekt spetsifikatsioon, mida me ei kavatse rakendamisel täna,
mida me tahame teha, on lihtsalt tagasi false.
Meie tõukemeetod läheb tagasi tõeväärtuse,
ja et tõeväärtuse on tõsi, kui push õnnestub
ja vale, kui me ei saa sundida midagi rohkem, sest stack on täis.
Vaatame läbi kõndida natuke, et kood kohe.
Siin on meie push funktsioon.
Meie push funktsioon stack läheb võtta stringi panna virna.
See läheb tagasi true, kui string on edukalt surunud
kohta virna ja vale teisiti.
Kõik ettepanekud, mida võiks olla hea esimene asi, mida siin teha?
[Sam] Kui suurus võrdub võimsusega siis tagasi false?
[Hardison] Bingo. Tubli töö.
Kui suur on võimsus, me lähme tagasi false.
Me ei saa panna midagi rohkem meie pinu.
Muidu me tahame panna midagi peal virnas.
Mis on "pinu" esialgu?
[Daniel] Suurus 0? >> Suurus 0.
Mis on pinu pärast on üks asi pakis? Missy, sa tead?
[Missy] Üks. >> Suurus on üks, täpselt. Sa hoida lisades suurus,
ja iga kord, kui paned uue elemendi indeksi suurus massiiv.
Me saame seda teha koos seda liiki ühe-liner, kui see on mõistlik.
Nii et meil on meie stringide massiiv, me ei kavatse seda lugeda suurus indeks,
ja me lihtsalt läheb salvestada oma char * seal.
Märka, kuidas seal ei ole string kopeerimine toimub siin,
ei dünaamiline jaotamine mälu?
Ja siis Missy üles kasvanud, mida me nüüd peame tegema,
sest me oleme salvestatud stringi sobiv koht massiivi,
ja ta ütles, et me pidime juurdekasvu suurus ühe, nii et me oleme valmis järgmiseks viik.
Nii saame teha, et s.size + +.
Sel hetkel oleme tõugatakse meie massiivi. Mis on viimane asi, mida me peame tegema?
[Student] Tagasi tõsi. >> Tagasi tõsi.
Nii et see on üsna lihtne, üsna lihtne kood. Mitte liiga palju.
Kui oled murtud oma pea ümber, kuidas korstnat töötab,
see on üsna lihtne rakendada.
>> Nüüd järgmine osa sellest on popping string off pinu.
Ma annan teile kutid mõnda aega tööd selle natuke.
See on peaaegu sisuliselt vastupidine sellele, mida me oleme teinud siin viik.
Mida ma olen teinud, on tegelikult - oih.
Olen käivitatud seadme üle siin, ja aparaat,
Olen tõmmata probleem seatud 5 spetsifikatsioon.
Kui me suumimiseks siin näeme, ma olen cdn.cs50.net/2012/fall/psets/pset5.pdf.
Kas te olete alla laadinud seda koodi see asub siin, section6.zip?
Hea küll. Kui te pole seda teinud, seda teha just nüüd, tõesti kiiresti.
Ma teen seda minu terminaliakent.
Ma tegelikult tegin seda siin üleval. Jah.
Jah, Sam? >> Mul on küsimus, miks sa ütlesid s.string on sulgudes size = str?
Mis on str? Kas see on määratletud kuskil enne või - oh, et char * str?
[Hardison] Jah, just. See oli argument. >> Oh, okei. Vabandust.
[Hardison] Me täpsustades string suruda sisse
Teine küsimus, mis võiks tulla, et me tegelikult ei räägi siin oli
võtsime enesestmõistetavaks, et meil oli see muutuja nimega s
et oli oma ulatuselt ja kättesaadav meile.
Võtsime iseenesestmõistetavaks, et s oli see virna struct.
Nii et vaadata tagasi selle push-koodi,
te näete, et me teeme asju selle stringiga, mis sai möödunud aastal
aga siis äkki, me tutvumise s.size, nagu, kust on pärit?
Kui koodi, et me ei kavatse vaadata jaos arhiiv
ja siis värk, et saate teha oma probleem seab,
oleme teinud meie korstnat vatseti globaalne muutuja
nii et meil on juurdepääs see kõik meie erinevad funktsioonid
ilma käsitsi andke seda ümber ja andke seda viitena,
teha kõik, et sellist kraami ta.
Me lihtsalt petmine natuke, kui soovite, et muuta asju kenamaks.
Ja see on midagi, mida me siin teeme, sest see on lõbus, see on lihtsam.
Tihti näete inimesed teevad seda, kui neil on üks suur andmestruktuur
mis kuramuse opereeritaks oma programmi.
>> Lähme tagasi üle seadme.
Kas igaüks edukalt saada section6.zip?
Igaüks unzip see kasutades unzip section6.zip?
Kui te lähete lõik 6 kataloog -
aah, kogu koht -
ja te nimekirja, mis siin, näed, et sul on kolm erinevat. c faile.
Sul sabas, sll, mis on üksikult seotud loetelu ja korstnat.
Kui te avada stack.c,
näete, et meil on see struct määratletud meie jaoks
täpse struct, et me lihtsalt rääkisime slaidid.
Meil meie globaalse muutuja korstnat
meil meie push funktsioon,
ja siis pole meil meie pop funktsioon.
Ma panen koodi tagurdamise üles slaidi siin,
aga mida ma tahaksin teiega teha on, et parima teie võimet,
minna ja rakendada pop funktsioon.
Kui olete rakendanud, saate kompileerida seda tegema korstnat
ja seejärel käivitage tulemuseks korstna käivitatava,
ja mis kestab kogu selle testi koodi siia alla see on peamine.
Ja peamine hoolitseb tegelikult teeb push ja pop kõned
ning tagada, et kõik läheb läbi küll.
Samuti käivitab stäki suurus siinsamas
nii et sa ei pea muretsema initsialiseerimisel seda.
Võite eeldada, et see on õigesti vormindatud
ajaks, mil te seda kasutada on pop funktsioon.
Kas see on loogiline?
Nii et siin me läheme. Seal on push-koodi.
Ma annan sulle poisid 5 või 10 minutit.
Ja kui teil on küsimusi vahepeal, kui oled kodeerimine,
küsige neid valjusti.
Nii et kui sa saad torkekoha, küsige.
Anna teada, lase kõik teised teavad.
Töö oma naabri liiga.
[Daniel] Me lihtsalt rakendamise pop praegu? >> Lihtsalt pop.
Kuigi saate kopeerida rakendamise push kui soovite
nii et katsetamine töötab.
Sest see on raske katsetada asju sattumist -
või, see on raske testida popping asjad läbi korstna, kui ei ole midagi pakis alustada.
>> Mis on pop peaks olema tagasi? Element pinu.
See peaks saama element off Pinu
ja siis kahandab suurus korstnat
ja nüüd oled kaotanud elemendi peal.
Ja siis tagasi osa peal.
[Student, arusaamatult]
[Hardison] Mis juhtub, kui sa seda tegid? [Student, arusaamatult]
Mis jõuab juhtub, on sul ilmselt tutvumise kas
element, mis ei ole vormindatud veel, nii et teie arvutus
kus viimane element on välja lülitatud.
Nii et siin, kui te märkate, et push, me tutvumise stringid s.size element
sest see on uus indeks.
See on uus pinu.
Arvestades, pop, s.size saab olema järgmise ruumi,
ruumi, mis on peal kõik elemendid oma korstnat.
Nii et kõige ülemisele element ei ole kell s.size,
vaid pigem, et see on selle all.
>> Teine asi, mida teha, kui sa - pop,
on sul on ainult kahandab suurus.
Kui te mäletate tagasi meie väike diagram siin,
tõesti, ainus asi, mida me nägime juhtub, kui me kutsusime pop
oli see, et suurus langenud, esimene 2, siis 1.
Siis, kui me lükatakse uue osa kohta, see oleks minna õigel kohapeal.
[Basiilik] Kui s.size on 2, siis kas ei oleks minna element 2,
ja siis tahaks pop see element ära?
Nii et kui me läksime - >> Nii et vaatame seda uuesti.
Kui see on meie stack selles punktis
ja me kutsume pop,
kus indeks on kõige ülemisele element?
[Basiilik] 2., kuid see läheb Pop 3. >> Õigus.
Nii et kui meie suurus on 3, kuid me tahame pop elemendi indeks 2.
See on see tüüpiline selline välja üks, et teil on null-indekseerimine massiivid.
Nii et sa ei taha pop kolmas element, aga kolmas element ei ole kell indeks 3.
Ja põhjus, miks me ei pea seda tegema miinus 1, kui me surudes
on, sest just nüüd, märkate, et kõige ülemisele element,
kui me olime suruda midagi muud peale virna selles punktis,
me tahaks vajutage neid indeks 3.
Ja see lihtsalt nii juhtub, et suurus ja indeksid rivistama, kui sa lükates.
>> Kellel on töö korstnat rakendamise?
Sul on töö virna üks. Kas teil on pop töötab veel?
[Daniel] Jah. Ma arvan küll.
>> Programmi töötab ja ei seg Murrang, see prindib?
See välja printida "edu" kui sa jooksed ta?
Jah. Tee korstnat, käivitage see, kui ta prindib välja "edu" ja ei lähe buumi,
siis kõik on hea.
Hea küll. Lähme üle seadmele tõesti kiiresti,
ja me käime läbi selle.
Kui me vaatame, mis toimub siin popmuusika,
Daniel, mis oli esimene asi, mis sa tegid?
[Daniel] Kui s.size on suurem kui 0.
[Hardison] Okei. Ja miks sa seda tegid?
[Daniel] Et veenduda, et seal oli midagi sees pinu.
[Hardison] Õigus. Sa tahad katsetada veendumaks, et s.size on suurem kui 0;
muidu, mida sa tahad on juhtunud?
[Daniel] Tagasi null? >> Tagasi null, täpselt.
Nii et kui s.size on suurem kui 0. Mida me siis nüüd teeme?
Mida me teeme, kui korstnat ei ole tühi?
[Stella] Sa kahandab suurus? >> Sa kahandab suurus, eks.
Niisiis, kuidas sa seda tegid? >> S.size--.
[Hardison] Tore. Ja siis mida sa tegid?
[Stella] Ja siis ma ütlesin tagasi s.string [s.size].
[Hardison] Tore.
Vastasel naasete null. Jah, Sam?
[Sam] Miks see ei pea olema s.size + 1?
[Hardison] Pluss 1? >> Jah. >> Sain.
[Sam] Ma arvasin, sest te võtate 1-,
siis sa lähed tuleb tagasi mitte üks, et nad palusid.
[Hardison] Ja see oli just see, mida me rääkisime kogu see teema on 0 indeksid.
Nii et kui me suumida tagasi siia.
Kui me vaatame seda meest siin, näete, et kui me pop,
me popping elemendi indeks 2.
>> Nii et me vähendada meie suurus ja seejärel meie suurus sobib meie kataloogi.
Kui me ei aland suurus, seejärel me peame tegema suurus -1 ja siis muutu.
Suur. Kõik hea?
Kõik küsimused selle kohta?
On mitmeid erinevaid viise, kuidas kirjutada see samuti.
Tegelikult me ​​saame midagi teha ka - me saame teha Sutkaus.
Me saame teha ühe liini edasi-tagasi.
Nii saame tegelikult kahandab enne kui me tagasi tehes seda.
Nii paneb - enne s.size.
See teeb liin tõesti tihe.
Kui vahe - s. Suurus ja s.size--
on see, et postfix - nad kutsuvad seda postfix sest - tuleb pärast s.size--
tähendab, et s.size hinnatakse jaoks leida indeksi
kuna see on hetkel, kui see liin on täidetud,
ja siis see - juhtub pärast rida saab teostada.
Pärast elemendi indeks s.size pääseb.
Ja see pole see, mida me tahame, sest me tahame aland juhtub esimesena.
Othewise, me ei kavatse olla juurdepääsu massiivi, tõhusalt, audis.
Me ei kavatse tutvumise osa kohal üks, mida me tegelikult tahame pääseda.
Jah, Sam? >> Kas see kiiremini või kasutada vähem RAM teha ühel real või mitte?
[Hardison] Ausalt, see tõesti sõltub.
[Sam, arusaamatult] >> Jah, see sõltub. Seda saab teha kompilaator trikke
saada kompilaator tunnistada, et tavaliselt, ma kujutan ette.
>> Nii oleme mainitud natuke selle kompilaatori optimeerimine värk
mida saate teha koostamisel,
ja see on selline asi, et tõlkija oleks võimalik aru saada,
nagu Oh, hei, äkki ma suudan seda kõike ühe operatsiooni
mitte laadimise suurus muutuja RAM,
degressioon see, talletades seda tagasi viia, ja siis laadimist see uuesti
töödelda ülejäänud seda operatsiooni.
Aga tavaliselt, ei, see ei ole mingisugune asi
et läheb teeb oma programmi oluliselt kiiremini.
Enam küsimustele korstnad?
>> Nii surudes ja popping. Kui te tahate proovida häkker väljaanne,
mida me oleme teinud häkker väljaanne on tegelikult läinud
ja teinud seda virna kasvatada dünaamiliselt.
Väljakutse on eelkõige siia üles push funktsioon,
välja nuputada, kuidas teha, et massiivi kasvada
nagu te hoida surudes rohkem ja rohkem elemente, et korstnat.
See on tegelikult mitte liiga palju lisakood.
Lihtsalt üleskutse - sa pead meeles pidama, et saada kõnesid malloc seal korralikult,
ja siis aru saada, kui sa lähed helistada RealLOC.
See on lõbus väljakutse, kui oled huvitatud.
>> Aga praegu, liigume edasi, ja räägime järjekorrad.
Leidke siit läbi.
Järjekord on lähedal vend virna.
Nii et pakis, asju, mis pandi viimane
olid esimesed asjad, siis oleks võimalik taastada.
Meil seda viimast sisse, esimesena välja, või LIFO, tellimine.
Arvestades järjekorras, nagu te ootaksite kui sa seisad kooskõlas,
esimene inimene saada kooskõlas, esimene asi sattuda järjekorda,
on esimene asi, et saab laaditakse järjekorda.
Järjekorrad kasutatakse sageli ka siis, kui me tegeleme graafikud,
nagu me rääkisime põgusalt korstnad,
ja järjekorrad on ka mugav hunnik muid asju.
Üks asi, mis kerkib sageli üritab säilitada, näiteks,
järjestatud elementide loetelu.
Ja seda saab teha koos massiivi. Te saate säilitada järjestatud nimekiri asjadest massiivi,
kuid kui see saab keeruline on siis alati leidma
sobiv koht lisada järgmine asi.
Nii et kui teil on array numbrite 1 kuni 10,
ja siis sa tahad laieneda, et kõikide numbrid 1 kuni 100,
ja te saate neid numbreid juhuslikus järjekorras ja üritab hoida kõik
järjestatud kui sa lähed läbi, siis lõpuks oleks vaja teha palju muutuvad.
Teatud tüüpi järjekorrad ja teatud alusvara andmestruktuure
tegelikult võite hoida seda üsna lihtne.
Sa ei pea midagi lisada ja siis ümberkujundamist kogu asi iga kord.
Ega sa pead tegema palju nihkumise sisemisi elemente ümber.
Kui me vaatame järjekorda, näed, et - ka queue.c jaos kood -
struct et me oleme sulle andnud on tõesti sarnane struct mis meie Teile andsime jaoks virna.
>> On üks erand sellest ja et ühe erandiga
on see, et meil on see täiendav täisarv nimetatakse pea,
ja pea siin on jälgida, pea järjekorda,
või esimene element järjekorda.
Mis korstnat, suutsime jälgida element, et me olime umbes toomiseks,
või magasini tippu, kasutades ainult suurus,
arvestades, järjekorda, me tegelema otsades.
Me püüame tack asju lõpus, kuid siis tagasi asju ees.
Nii et tegelikult, peaga, meil on indeks alguses järjekorda,
ja suurus annab meile indeks lõpuks järjekorda
nii et me saame kätte asjad peast ja lisada asju, et saba.
Ning arvestades, pinu, olime ainult kunagi tegelevad pinu.
Me ei ole kunagi olnud juurdepääsu põhja korstnat.
Me ainult lisatud asjad üles ja võttis asjad välja ülemise
nii et me ei vaja, et ekstra valdkonnas sees meie struct.
Kas see üldiselt mõtet?
Hea küll. Jah, Charlotte? [Charlotte, arusaamatult]
[Hardison] See on hea küsimus, ja see oli üks, mis tuli üles loeng.
Ehk jalgsi läbi mõned näited illustreerivad miks
me ei taha kasutada stringe [0] juhina järjekorda.
>> Seega kujutada, et meil on meie sabas, me nimetame seda järjekorda.
Alguses, kui me just instantiated see,
kui me just kuulutanud, et me ei ole vormindatud midagi.
See kõik prügi. Nii et loomulikult me ​​tahame veenduda, et me initsialiseerida
nii suuruse ja pea väljad olema 0, midagi mõistlikku.
Me võiksime ka minna ja tühjaks välja elemente meie sabas.
Ja teha seda skeemi järgi, on märgata, et nüüd meie järjekorda saab omada ainult kolm elementi;
arvestades, et meie stack võiks olla neli, meie järjekorda saab omada ainult kolm.
Ja see on ainult, et diagramm sobib.
Esimene asi, mis juhtub on meil Lisa järjekorda string "Tere".
Ja just nagu me tegime koos korstna, midagi kohutavalt erinev siin,
me visata nöör kell stringid [0] ja juurdekasvu meie suurus 1.
Meil Lisa järjekorda "Bye", siis saab panna.
Nii et see näeb välja nagu pinu enamasti.
Me alustasime siin, uus element, uus element, suurus hoiab tõusevad.
Mis juhtub sel hetkel, kui me tahame dequeue midagi?
Kui me tahame dequeue, mis on element, mida me tahame dequeue?
[Basiilik] Strings [0]. >> Zero. Täpselt õige, basiilik.
Me tahame vabaneda esimene string, see üks, "tere".
Mis siis oli teine ​​asi, mis on muutunud?
Teade, kui me hüppasid midagi välja virna, me lihtsalt muutunud suurus,
kuid siin, meil on paar asja, mis muutus.
Mitte ainult ei suurus muutus, kuid pea muudatusi.
See läheb tagasi Charlotte'i punkt varem:
miks me peame seda pea ka?
Kas on mõtet nüüd, Charlotte? >> Liik.
[Hardison] Kind of? Mis siis juhtus, kui me dequeued?
Mida pead tegema, et nüüd on huvitav?
[Charlotte] Oh, sest see muutunud - eks. Mõistan.
Sest pea - kui juht on suunatud muutustele vastavalt asukohale.
See ei ole enam alati null indeks üks. >> Jah, täpselt.
Mis juhtus oli see, kui dequeueing kõrge element
tehtud ja meil ei olnud see pea valdkonnas
sest meil oli alati kutsudes seda stringi 0 indeks pea meie sabas,
siis oleks meil suunata ülejäänud järjekorda alla.
Meil oleks nihutada "Bye" alates alates stringid [1] stringid [0].
Ja stringid [2] sätestatakse, et stringide [1].
Ja me peame seda tegema kogu elementide loetelu,
kogu massiivi elemente.
Ja kui me teeme seda massiivi, et saab tõesti kulukas.
Nii et siin, see ei ole suur asi. Meil on lihtsalt kolm elementi meie massiivi.
Aga kui meil oleks järjekorda tuhat elemente või miljoni elemente,
ja siis äkki, kui hakkame tegema kamp dequeue kutsub kõiki tsüklina
asjad on tõesti aeglustada kui see nihutab kõike ette pidevalt.
Tead, vahetustega 1., vahetustega 1., vahetustega 1., vahetustega 1..
Selle asemel me kasutame seda peas, me nimetame seda "osuti", kuigi see ei ole tõesti pointer
sõna otseses mõttes, see pole osutiloendurid.
See ei ole int * või char * või midagi sellist.
Aga see on suunatud või näidates pea meie sabas. Jah?
>> [Student] Kuidas dequeue tea lihtsalt pop off iganes eesotsas?
[Hardison] Kuidas dequeue tea, kuidas pop off iganes on otsas? >> Õigus, jah.
>> Mis see vaadates on lihtsalt mida iganes pea väli on seatud.
Nii et see esimene juhtum, kui me vaatame siin,
meie peas on 0, indeks 0.. >> Õigus.
[Hardison] Nii see lihtsalt ütleb okei, noh, elemendi indeks 0, string "Tere",
on element eesotsas meie sabas.
Nii et me ei kavatse dequeue et kutt.
Ja see on element, mis saab tagastada helistaja.
Jah, Saad? >> Nii pea põhimõtteliselt seab - kui sa lähed indeks on?
See on algusest on? >> Jah. >> Okei.
[Hardison] See on saamas uus algus meie massiivi.
Nii et kui te dequeue midagi, kõik mida sa pead tegema, on avada elemendi indeks q.head,
ja see on element, mida soovite dequeue.
Sul on ka kahandab suurus.
Me näeme natuke koht, kus asjad veidi keeruline seda.
Me dequeue, ja nüüd, kui meil Lisa järjekorda uuesti,
kus me Lisa järjekorda?
Kust järgmise elemendi minna meie sabas?
Ütle tahame Lisa järjekorda string "CS".
Kuhu indeks läks? [Õpilased] Strings [2]. >> Kaks.
Miks 2 ja mitte 0?
[Basiilik] Sest nüüd on pea 1, seega see on nagu algust nimekirja?
[Hardison] Õigus. Ja mis tähistab loendi lõppu?
Mida me kasutame, et tähistada lõpuks meie sabas?
Pea on pea meie sabas, alguses meie sabas.
Mis on lõpuks meie sabas? [Õpilased] Suurus. >> Suurus täpselt.
Nii et meie uued elemendid minna kell suurus, ning vahendid, mida me startida tulnud maha pea.
Kui me Lisa järjekorda järgmise elemendi, me paneme selle juures suurusest.
[Student] Enne paned et kuigi suurus oli 1, eks?
[Hardison] Õigus. Nii ei ole päris kell suurus. Suurus +, mitte 1, vaid + pea.
Sest me nihkunud kõike peast summa.
Nii et siin, praegu meil järjekorda suurus 1, mis algab kell indeks 1.
Saba on indeks 2. Jah?
>> [Student] Mis juhtub, kui sa dequeue stringid [0], ja stringid "teenindusaegade mälu
lihtsalt saada tühjendada, põhiliselt, või lihtsalt unustatud?
[Hardison] Jah. Selles mõttes, et me lihtsalt ei unusta neid.
Kui olime ladustamiseks neist koopiaid jaoks -
palju andmestruktuurid sageli salvestada oma koopiad elemendid
nii et isiku juhtimisel andmestruktuur ei pea muretsema
umbes seal, kus kõik suunanäitajaks lähevad.
Andmestruktuur hoiab kõike, hoiab kõiki koopiaid,
veenduda, et kõik püsib sobivalt.
Kuid sellisel juhul need andmestruktuurid lihtsalt, lihtsuse,
ei tee koopiaid midagi, et me ladustamiseks neid.
[Student] Nii on see pidev array -? >> Jah.
Kui me vaatame tagasi, mida mõiste oli selle struktuuri, see on.
See on lihtsalt tavaline massiiv nagu olete näinud,
array char * s.
Kas see -? >> Jah, ma just mõtlesin,
kui sa lõpuks otsa mälu, teatud määral,
kui teil on kõik need tühjad kohad oma massiivi?
[Hardison] Jah, see on hea punkt.
>> Kui me vaatame, mis nüüd juhtus sel hetkel,
oleme täis meie sabas, tundub.
Aga me ei ole tõesti täis meie sabas
sest meil on järjekord see on suurus 2, kuid see algab kell indeks 1,
sest see on kui meie peas osuti on.
Nagu sa ütlesid, et element on string [0], on indeks 0, ei ole tegelikult olemas.
See ei ole meie järjekorda enam.
Me lihtsalt ei viitsinud minna ja üle kirjutada, kui me dequeued ta.
Nii et kuigi tundub, et me oleme otsa mälu, me tõesti ei ole.
See koht on saadaval meie jaoks kasutada.
Asjakohane käitumine, kui me proovida ja esimene dequeue midagi
meeldib "Bye", mis oleks pop bye maha.
Nüüd on meie sabas algab indeks 2 ja on suurusega 1.
Ja nüüd, kui me püüame Lisa järjekorda midagi jälle öelda, 50,
50 peaks minema selle koha juures indeks 0.
sest see on ikka saadaval siin. Jah, Saad?
[Saad] Kas see juhtub automaatselt?
[Hardison] See ei juhtu üsna automaatselt. Sa pead tegema matemaatika
teha seda tööd, kuid sisuliselt mida me oleme teinud, on meil lihtsalt pakitud ümber.
[Saad] Ja see on okei, kui see on auk keskel on?
[Hardison] See on, kui me suudame teha matemaatika töötada välja korralikult.
>> Ja selgub, et tegelikult ei ole nii raske teha mod operaator.
Nii nagu me tegime koos Caesar ja krüpto värk,
kasutades mod, saame asju murtakse ja jätkame
ringi ja ringi ja ringi meie sabas,
hoides, et pea kursorit ringi liikudes.
Pange tähele, et suurus on alati kinni mitmeid elemente tegelikult jooksul järjekorda.
Ja see on lihtsalt pea osuti, mis hoiab jalgrattaga läbi.
Kui me vaatame, mis juhtus siin, kui me läheme tagasi algusesse,
ja sa lihtsalt vaadata, mis juhtub peaga
kui me Lisa järjekorda midagi ei juhtunud midagi pähe.
Kui me enqueued midagi muud, midagi ei juhtunud pähe.
Niipea kui me dequeued midagi, pea läheb ühe võrra ülespoole.
Me enqueued midagi ei juhtu midagi pähe.
Kui me dequeue midagi, äkki pea saab suurendatakse.
Kui me Lisa järjekorda midagi ei juhtu midagi pähe.
>> Mis juhtuks sel hetkel, kui me dequeue midagi jälle?
Kõik mõtted? Mis juhtuks pähe?
Mis peaks juhtuma, et pea
kui me dequeue midagi muud?
Pea kohe on indeks 2,
mis tähendab, et juht järjekord on stringid. [2]
[Student] mis tagastab 0? >> See peaks tagastama kuni 0. See peaks wrap tagasi umbes, täpselt.
Seni iga kord me kutsusime dequeue, oleme olnud lisades ühe pea,
lisada ühe pea, lisada üks pea, lisada üks pea.
Niipea, et pea osuti jõuab viimase indeks meie massiiv,
siis peame murrab ta tagasi umbes aasta algusega, mine tagasi 0.
[Charlotte] Mis määrab võime järjekord korstna?
[Hardison] Sellisel juhul oleme lihtsalt kasutanud # määratletud konstantne. >> Okei.
[Hardison] Tegeliku. C fail, saab minna ja sopp seda natuke
ja teha see nii suur või nii vähe kui soovite.
[Charlotte] Nii et kui sa üritad seda järjekorda, kuidas sa teha arvuti tea
kuidas suur soovite korstnat olla?
[Hardison] See on hea küsimus.
Seal on paar võimalust. Üks on lihtsalt määratleda seda rindel
ja öelda, et see saab olema järjekorras, mis on 4 elementi või 50 elementi või 10.000.
Teine võimalus on teha seda, mida häkker väljaanne inimesed teevad
ja luua funktsioone, et teie järjekord kasvab dünaamiliselt kui veel asjad lisatud sisse
>> [Charlotte] Nii minna esimese variandi, mida süntaks te kasutate
öelda programmi, mis on suuruse järjekorras?
[Hardison] Ah. Nii et lähme siit.
Ma olen ikka stack.c siin, nii et ma lihtsalt lähen üles kerimiseks üles siin.
Kas te näete seda siin? See on # define mahuga 10.
Ja see on peaaegu täpselt sama süntaksit, et meil on järjekord.
Välja arvatud järjekorda, meil, et pildi struct valdkonnas siia.
[Charlotte] Ma arvasin, mahutavus tähendas võime string.
[Hardison] Ah. >> Et see on pikim sõna. >> Sain.
Jah. Suutlikkuse siin - see on suurepärane punkt.
Ja see on midagi, mis on keeruline
sest me oleme siin deklareerida on array char * s.
Massiivi osuti.
See on array tähemärki.
See on ilmselt, mida olete näinud, kui olete olnud kuulutab oma puhvrid Faili I / O,
kui olete olnud luua stringe käsitsi pinu.
See, mida meil siin on array char * s.
Seega on massiivi osuti.
Tegelikult, kui me suumida tagasi välja ja vaatame, mis siin toimub
esitlemisel, näed, et tegelik elemendid, märkandmeid
ei ole salvestatud massiivi ise.
Mis salvestatud meie massiivi siin on vihjeid iseloomuga andmeid.
Okei. Nii et me oleme näinud, kuidas suuruse järjekorras on nagu koos korstna,
suurus alati austab elementide arvuga praegu järjekorras.
Pärast tegemise 2. enqueues, suurus on 2.
Pärast seda dequeue suurus on nüüd 1.
Pärast seda teise Lisa järjekorda suurus on tagasi kuni 2.
Nii suurus kindlasti austab elementide arvu järjekorras,
ja siis pead muudkui jalgrattaga.
See läheb 0-1-2, 0-1-2, 0-1-2.
Ja iga kord, kui me helistada dequeue, pea kursorit saab suurendatakse järgmise indeks.
Ja kui pea hakkab minema üle ning see silma tagasi umbes 0-ga.
Nii et, saame kirjutada dequeue funktsioon.
Ja me ei kavatse lahkuda Lisa järjekorda funktsioon kutid rakendada asemel.
>> Kui me dequeue element välja meie sabas,
Mis oli esimene asi, mis Taaniel tegi, kui me hakkasime kirjalikult pop funktsioon korstnad?
Las ma kuulen keegi, kes ei ole rääkinud veel.
Vaatame, Saad, kas sa mäletad, mida Daniel tegi kui esimene asi, kui ta kirjutas pop?
[Saad] Seal oli, see oli - >> Ta proovis midagi.
[Saad] Kui suurus on suurem kui 0. >> Täpselt.
Ja mis see oli testimine?
[Saad] See oli katse, et näha, kas seal on midagi sees massiiv.
[Hardison] Jah. Täpselt. Nii et sa ei saa pop midagi välja pinu kui see on tühi.
Samuti ei saa te dequeue midagi järjekorda, kui see on tühi.
Mis on esimene asi, mida me peaksime tegema meie dequeue funktsioon siin, sa arvad?
[Saad] Kui suurus on suurem kui 0? >> Jah.
Sel juhul, ma olen tegelikult lihtsalt katsetada, et näha, kas see on 0.
Kui see on 0, me saame naasta null.
Aga täpselt sama loogikat.
Ja olgem jätkata seda.
Kui suurus ei ole 0, kus on element, mida me tahame dequeue?
[Saad] tipus? >> Täpselt.
Me ei saa lihtsalt tõmmake esimene osa meie sabas
, pääsedes element eesotsas.
Miski hull.
Pärast seda, mida me peaksime tegema? Mis peab juhtuma?
Milline oli teine ​​asi, mis me rääkisime dequeue?
Kaks asjad peavad juhtuma, sest meie järjekord on muutunud.
[Daniel] suuruse vähendamiseks. >> Meil ​​on suuruse vähendamiseks ja suurendada pea? Täpselt.
Suurendada pea, ei saa me lihtsalt pimesi tõsta pea meeles.
Me ei saa lihtsalt teha queue.head + +.
Peame ka see mod poolt võimsust.
Ja miks me Mod by võimsus, Stella?
[Stella] Sest see peab ümbritsev. >> Täpselt.
Me mod poolt läbilaskevõime, sest see on wrap tagasi umbes 0-ga.
Nii et nüüd, sel hetkel, saame teha seda, mida Daniel ütles.
Saame kahandab suurus.
Ja siis me saame lihtsalt tagasi element, mis oli tipus järjekorda.
Tundub selline gnarly alguses. Sul võib olla küsimus. Vabandust?
>> [Sam] Miks on esimene ülaosas järjekorda? Kuhu see kadus?
[Hardison] See pärineb neljanda rea ​​alt.
Pärast me testida veendumaks, et meie järjekorda ei ole tühi,
me tõmmake char * Esiteks, me tõmba element, mis istub eesotsas indeks
meie massiiv, meie stringide massiiv, >> ja kõne, et esimesena?
[Hardison] Ja me kutsume seda esimesena. Jah.
Lihtsalt jälgida, et miks sa arvad, me pidime seda tegema?
[Sam] Iga Esimene on lihtsalt tagasi q.strings [q.head]? >> Jah.
>> Sest me seda teeme muutmine q.head koos mod funktsioon,
ja ei ole viis seda teha jooksul tagasi rida ka.
[Hardison] Täpselt. Sa oled kohapeal. Sam on täiesti kohapeal.
Seetõttu pidime tõmmake esimene element meie järjekorda ja salvestada see muutuja
sest see rida, kus olime just q.head,
seal mod operaator seal ei ole midagi, mida me saame teha
ja on see jõustub pea ilma - ühele joonele.
Nii et me tegelikult tõmmake esimene element, siis reguleeri pea,
suurust kohandada, ja siis tagasi element, mis me välja tõmmatud.
Ja see on midagi, mida me näeme tulla hiljem
seotud nimekirjades, nagu me mängida nendega.
Sageli, kui sa vabastades või kõrvaldamise seotud nimekirjad
tuleb meeles pidada järgmise elemendi, järgmise pointer seotud nimekirja
Enne kõrvaldamise praegune.
Sest muidu sa visata informatsiooni sellest, mis on jäänud nimekirja.
Nüüd, kui sa lähed oma seade, kui avada queue.c--x läbi selle.
Nii et kui ma avada queue.c, lubage mul suurendada siin,
te näete, et teil on sarnase välimusega faili.
Sarnase välimusega faili, mis meil oli varem stack.c.
Meil meie struct jaoks järjekorda määratletud nagu nägime slaidid.
>> Meil on meie Lisa järjekorda funktsioon, mis on sinu jaoks teha.
Ja meil on dequeue funktsioon siin.
Dequeue funktsiooni fail on rakendamata,
aga ma panen selle tagasi üles PowerPoint, nii et saate tippige see, kui soovite.
Nii, et järgmise 5 minutit või nii, kutid töötavad Lisa järjekorda
mis on peaaegu täpselt vastupidine dequeue.
Sa ei pea kohandama pea kui sa enqueueing, aga mida sa pead muuta?
Suurus. Nii et kui teil Lisa järjekorda, pea jääb puutumata, suurus saab muuta.
Aga see võtab natuke - siis on mängida, et moderaator
välja nuputada täpselt, mida indeksi uus element tuleks lisada juures.
Nii et ma annan sulle poisid natuke, pane dequeue tagasi üles klapp
ja kui te on küsimusi, karjuda neid, et saaksime
kõik räägivad nad rühmana.
Samuti suurusele sa ei - kui te suurust kohandada, saad alati lihtsalt -
sa pead mod suurus kunagi? [Daniel] No >> Sul ei ole mod suurus, eks.
Sest suurus alati, kui Sa - eeldades haldate asju õigesti,
suurus on alati 0 ja 3.
Kui teil mod kui sa teed Lisa järjekorda?
[Student] Ainult pea. >> Ainult pea, täpselt.
Ja miks sa pead mod üldse Lisa järjekorda?
Kui on olukord, kus soovid on mod?
[Student] Kui teil on kraami ruumid meeldi ruumid 1 ja 2,
ja siis vaja midagi lisada 0.
[Hardison] Jah, täpselt. Nii et kui su pea osuti on päris lõpus,
või kui teie suurus pluss teie pea on suurem, või pigem läheb ümbritsev järjekorda.
>> Nii et selles olukorras, et meil on siin üleval objektiklaasil just nüüd,
kui ma tahan Lisa järjekorda midagi just nüüd,
tahame Lisa järjekorda millegi indeks 0..
Nii et kui te vaatate, kui 50 läheb, ja ma kutsun Lisa järjekorda 50,
see läheb sinna allosas. See läheb indeks 0..
See asendab "tere", mis oli juba dequeued.
[Daniel] Ära sa hoolitseda, et dequeue juba?
Miks see midagi peale hakata pea Lisa järjekorda?
[Hardison] Ah, et sa ei muuda pea, vabandust.
Aga sa pead kasutama mod operaator kui olete juurdepääsusoovide
element, mida soovite Lisa järjekorda, kui olete juurdepääsusoovide
Järgmise osa oma järjekorda.
[Basiilik] Ma ei teinud seda, ja ma sain "edu" seal.
[Daniel] Oh, ma saan aru, mida sa räägid.
[Hardison] Nii et sa ei - sa lihtsalt tegi q.size?
[Basiilik] Jah. Kolisin just pool, ma ei teinud midagi peaga.
[Hardison] Sa ei tegelikult on taastada pea olema midagi,
aga kui sa indeks stringid massiivi
sa tegelikult minna ja arvutada, kui järgmine element on,
sest väät korstna kõrval osa oma korstnat oli alati
kell indeks, mis vastab suurusele.
Kui me vaatame tagasi üles meie pinu push funktsioon,
me võiks alati kõmakas meie uus element paremale indeksi suurus.
Ning arvestades, järjekorda, me ei saa seda teha
sest kui me oleme selles olukorras,
kui me enqueued 50 Meie uus string läheks otse stringid [1]
mida me ei taha teha.
Me tahame uus string minna kell indeks 0..
>> Kas keegi - jah? [Student] Mul on küsimus, kuid see ei ole tõesti seotud.
Mida see tähendab, kui keegi lihtsalt nõuab midagi pred pointer?
Mis on selle nime lühend? Ma tean, see on lihtsalt nimi.
[Hardison] pred pointer? Vaatame. Mis kontekstis?
[Student] See oli Lisa. Võin küsida hiljem, kui soovite
sest see ei ole tõesti seotud, aga ma lihtsalt -
[Hardison] Alates Davidi sisestada koodi loeng?
Me ei tõmba, et üles ja räägi sellest.
Me räägime, et järgmisel, kui saame lingitud nimekirjad.
>> Nii et olgem tõesti kiiresti pilk Lisa järjekorda funktsioon välja näeb.
Mis oli esimene asi, mida inimesed püüdnud teha oma Lisa järjekorda rida? Sellesse järjekorda?
Sarnane sellele, mida sa tegid korstnat surudes.
Mida sa tegid, Stella?
[Stella, arusaamatult]
[Hardison] Täpselt. Kui (q.size == CAPACITY) -
Mul on vaja panna minu traksid õiges kohas - tagasi false.
Suurenda natuke. Okei.
Nüüd Mis on järgmine asi, mis me tegema pidime?
Just nagu pinu, ja sisestatud õiges kohas.
Ja mis oli õiges kohas lisada seda?
Mis stack oli indeksi suurus, seda, et see pole päris nii.
[Daniel] Mul on q.head--või - >> q.strings? >> Jah.
q.strings [q.head + q.size mod MAHT]?
[Hardison] Me ilmselt taha panna sulgudesse selle ümber
nii et saame sobiva järjestuse ja nii see on cleart kõigile.
Ja seatud, et võrdne? >> STR? >> Et tn. Suur.
Ja mis nüüd on viimane asi, mida me peame tegema?
Just nagu me tegime korstna. >> Kasvatab suurus? >> Kasvatab suurus.
Poom. Ja siis, kuna starter koodi just tagasi vale vaikimisi
me tahame muuta seda tõeseks, kui kõik läheb läbi ja kõik läheb hästi.
Hea küll. See on palju informatsiooni osas.
Me pole päris üle. Me tahame rääkida tõesti kiiresti umbes üksikult seotud nimekirju.
Ma panen selle üles, et saaksime minna tagasi hiljem.
Aga lähme tagasi meie esitus vaid paar rohkem slaide.
Nii Lisa järjekorda on TODO, nüüd olen seda teinud.
>> Nüüd võtame pilk üksikult seotud nimekirju.
Me rääkisime neist natuke rohkem loeng.
Kui paljud kutid nägid demo, kus me pidime inimesi
kohmakalt osutades üksteist ja osaluse numbrid? >> Olin seda.
>> Mida te poisid arvate? Kas see loodetavasti demüstifitseerida neid natuke?
Mis nimekiri, tuleb välja, et me käsitleme seda tüüpi, et me ei kavatse helistada sõlme.
Ning arvestades, järjekorda ja korstnat meil oli structs et me tahaks helistada järjekorda korstnat
meil oli neid uusi järjekorda pinu tüüpe,
Siin nimekirjas on tõesti vaid koosneb hunnik tippe.
Samamoodi, et stringid on lihtsalt hunnik sümboleid kõik rivistatud üksteise kõrval.
Seotud loetelu on vaid sõlme ja teise sõlme ja teise sõlme ja teise sõlme.
Ja mitte oivaline kõik sõlmed kokku ja ladustamiseks neid contiguously
Olgu üksteise kõrval mälus,
võttes selle järgmisele pointer annab meile võimaluse salvestada sõlmede kus iganes, juhuslikult.
Ja siis mingi traat neid kõiki koos juhtida ühest teiseni.
>> Ja mis oli suur eelis, et see oli üle hulga?
Üle ladustamiseks kõik contiguously lihtsalt kinni üksteise kõrval?
Sa mäletad? Jah? >> Dünaamiline mälu eraldamise?
>> Dünaamiline mälu eraldamise siis mis mõttes?
[Student] Sel saate hoida muutes suurem ja te ei pea liikuda kogu oma massiivi?
[Hardison] Täpselt. Nii massiiv, kui sa tahad panna uus element keset seda,
teil on suunata kõik ruumi teha.
Ja nagu me rääkisime järjekorda,
Sellepärast me hoiame, et pea pointer,
nii et me ei ole pidevalt minnes asju.
Sest mis saab kallis, kui sul on suur massiiv
ja teed sageli need juhuslikult sisestamisel.
Arvestades nimekirja, millel on kõik, mida pead tegema, on visata see uus sõlm,
kohandada viiteid, ja sa oled teinud.
Mis imeb selle kohta?
Jättes kõrvale asjaolu, et see ei ole nii lihtne töötada massiiv? Jah?
[Daniel] Noh, ma arvan, et see on palju raskem pääseda konkreetse elemendi seotud nimekirja?
[Hardison] Sa ei saa lihtsalt hüpata suvalise elemendi keset oma seotud nimekirja.
Kuidas sa pead tegema selle asemel? >> Sa pead sammult läbi kogu asi.
[Hardison] Jah. Sa pead minema läbi ühe korraga, ükshaaval.
See on tohutu - see on valu.
Mis muud - seal on teine ​​kokkuvarisemine, et see.
[Basiilik] Sa ei saa minna edasi ja tagasi? Sa pead minema ühes suunas?
[Hardison] Jah. Niisiis, kuidas me lahendame, et mõnikord?
[Basiilik] Topeltränistuv seotud nimekirjad? >> Täpselt. Seal on kahekordselt seotud nimekirju.
On ka - kahju?
>> [Sam] Kas see on sama, kui kasutada pred asi, mis -
Mul tuli just meelde, ei ole see, mida pred asi on?
Kas pole vahel kahekordselt ja üksikult?
[Hardison] Vaatame, mida täpselt ta teeb.
Nii et siin me läheme. Siin on nimekiri kood.
Siin on meil predptr, siin. Kas see, mida sa räägid?
Nii see oli - ta vabastades nimekirja ja ta üritab hoida kursor ta.
See ei ole kahekordselt, üksikult seotud-nimekirju.
Me võime rääkida rohkem sellest hiljem, sest see räägib vabastades nimekirja
ja ma tahan näidata mõned muud asjad kõigepealt.
aga see on lihtsalt - see on meeles väärtus ptr
[Student] Oh, see on eelmistel pointer? >> Jah.
Nii et saame siis juurdekasvu ptr ise enne kui me siis vaba mida predptr on.
Kuna me ei saa tasuta ptr ja siis helistada ptr = ptr kõrval, eks?
See oleks halb.
Nii et vaatame, tagasi see kutt.
>> Teine halb asi nimekirjad on, et arvestades massiivi
me lihtsalt peame kõik elemendid ise laotud üksteise kõrval,
siin on meil ka sisse see pointer.
Nii et seal on veel tüki mälu, et meil oli kasutada
iga element, et me hoidmine meie nimekirjas.
Me saame paindlikkust, kuid see on oma hind.
Kaasas seda ajakulu,
ja see on kaasas selle mälu hind liiga.
Aeg selles mõttes, et meil on nüüd läbima iga element massiivi
leida ükshaaval punktid 10, või et oleks olnud punktidele 10 massiivis.
>> Lihtsalt tõesti kiiresti, kui me skeem välja need nimekirjad,
tavaliselt me ​​kinni hoida eesotsas nimekirja või esimese osuti nimekirja
ja pange tähele, et see on tõsi pointer.
See on lihtsalt 4 baiti. See ei ole tegelik sõlme ise.
Nii et näete, et ei ole int väärtust see ei Järgmise osuti ta.
See on sõna otseses mõttes lihtsalt kursor.
See saab viidata midagi, mis on tegelik tipp struktuure.
[Sam] osuti nimetatakse sõlm? >> See on - ei. See on viit midagi tüüpi sõlme.
See on viit tipu struct. >> Oh, okei.
Diagramm vasakul, kood paremal.
Me ei sea see null, mis on hea viis alustamiseks.
Kui diagramm, sa kas kirjutada see null või paned läbiv joon seda nii.
>> Üks lihtsamaid viise töö nimekirjad,
ja me palume teil nii nimedele ja lisab näha erinevusi nende kahe vahel,
kuid prepending on kindlasti lihtsam.
Kui ülaloleva on see, kus sa - kui nimedele (7)
te lähete ja luua sõlme struct
ja seate esimene käsk, sest nüüd, sest me faili nimele see,
see saab olema alguses nimekirja.
Kui me nimedele (3), mis loob teise sõlme, kuid nüüd 3 tuleb enne 7..
Nii et me sisuliselt surudes asju peale meie nimekirjas.
Nüüd te näete, et nimedele, mõnikord inimesed kutsuvad seda lükkama,
sest sa oled surudes uus element peale oma nimekirja.
Samuti on lihtne kustutada esiotsas nimekirja.
Nii et inimesed sageli helistada, et pop.
Ja sel moel saab jäljendada virna kasutades seotud loetelu.
Ups. Vabandust, nüüd oleme sattumist append. Nii et siin me faili nimele (7), nüüd nimedele (3).
Kui me faili nimele midagi muud peale selle nimekirja, kui me faili nimele (4)
siis oleks meil 4 ja siis 3 ja siis 7.
Siis võiksime pop ja eemaldage 4, eemaldada 3, eemaldage 7.
Sageli intuitiivsem viis mõelda on see, mille lisab.
Nii et ma olen diagrammina, mis see näeks välja koos lisada siin.
Siin lisatud (7) ei paista teistsugune
sest seal on ainult üks element nimekirjas.
Ja kleebi (3) annab selle aasta lõpuks.
Võib-olla näete kohe trikk append
on see, et kuna me ainult teada, kus alguses nimekiri on
lisama loendisse sa pead kõndima kogu aeg nimekirja
saada lõpuks lõpetada, siis ehitada oma sõlme ja kõmakas kõike ette.
Ühenda kõik asjad üles.
Nii nimedele, kui me lihtsalt rebis selle kaudu väga kiiresti,
kui sa ülaloleva loendile, see on üsna lihtne.
>> Sa teed endale sõlme, millega kaasnevad teatav dünaamiline mälu eraldamisel.
Nii et siin me teeme sõlme struct kasutades malloc.
Nii malloc me kasutame, sest et ma kõrvale mälu meiega hiljem
sest me ei taha seda - me tahame seda mälu püsida kaua aega.
Ja me saame kursor ruumi mälu, et me lihtsalt eraldatud.
Me kasutame suurus sõlm, me ei liida valdkondades.
Me ei käsitsi genereerida baitide arv,
selle asemel me kasutame sizeof nii et me teame, me saada vajalikul arvul baiti.
Oleme veendunud, et testida, et meie malloc kõne õnnestunud.
See on midagi, mida sa teha tahad üldiselt.
On kaasaegsete masinatega, otsa mälu ei ole midagi, mida on lihtne
kui sa eraldades tonni kraami ja tegemist tohutu nimekiri,
aga kui sa oled hoone värk, ütleme, nagu iPhone või Android,
sul on piiratud mälu ressursse, eriti kui sa teed midagi intensiivne.
Seega on hea, et saada tegelikkuseks.
>> Pange tähele, et olen kasutanud paar erinevat funktsiooni siin
et sa oled näinud, et on mingi uus.
Nii fprintf on nagu printf
välja arvatud selle esimene argument on oja, millele soovite printida.
Sellisel juhul me tahame printida standard veastring
mis erineb standard outstream.
Vaikimisi näitab üles samas kohas.
Samuti prindib terminali, kuid saab -
nende käskude kasutamise juttu, ümbersuunamise tehnika
oli juttu ka Tommy video probleem komplekt 4, saate suunata see
eri valdkondades; lõpeta, siinsamas, väljapääsud oma programmi.
See on sisuliselt nagu naasnud peamine,
välja arvatud me kasutame väljumise sest siin tagasi ei tee midagi.
Me ei ole peamine, et tagasi ei välju programmist nagu me tahame.
Nii et me kasutame väljumise funktsioon ja annab veakoodi.
Siis siin seadsime uut sõlme väärtuse väljal, selle i valdkonnas olema võrdne i, ja siis me traat see üles.
Oleme loonud uue sõlme järgmisel kursori punkti esimese,
ja siis esimene on nüüd punkt uue sõlme.
Need esimesed read koodi, me tegelikult hoone uus sõlm.
Mitte kaks viimast rida selle funktsiooni, kuid esimene neist.
Võite tegelikult tõmmake sisse funktsiooni sisse abistaja funktsiooni.
See on sageli, mida ma teen on, ma välja tõmmata funktsioon,
Ma kutsun seda midagi ehitada sõlm,
ja mis hoiab nimedele funktsiooni üsna väike, see on lihtsalt 3 rida siis.
Ma helistada minu build sõlme funktsiooni, ja siis ma traat kõik üles.
>> Lõplik asi, mida ma tahan teile näidata,
ja ma lasen sul append ja kõik, mis oma,
on see, kuidas itereerime nimekirja.
Seal on hunnik erinevaid viise itereerime nimekirja.
Sellisel juhul me leiame pikkuse nimekirja.
Nii alustame pikkus = 0.
See on väga sarnane kirjalikult strlen jaoks string.
See on see, mida ma tahan teile näidata, seda silmus siin.
Tundub suht funky, see pole tavaline int i = 0, i <iganes, i + +.
Selle asemel on see initsialiseerimisel meie muutuja n olevat loetelu alguses.
Ja siis kui meie iteraatori muutuja ei ole null, me jätkame.
Seda seetõttu, kokkuleppeliselt, lõpuks meie nimekirjas on null.
Ja siis juurdekasvu, mitte tehes + +,
seotud nimekirja ekvivalent + + on n = n-> next.
>> Ma lasen teil täita lüngad siin, sest me aeg otsas.
Kuid pidage seda meeles, kui te töötate oma spellr psets.
Seotud nimekirjades, kui sa rakendamisel hash tabelit,
Kindlasti tulevad väga mugav.
Ja millel see idioom jaoks silmuspõletamise üle asjad teevad elu palju lihtsamaks, loodetavasti.
Kõik küsimused, kiiresti?
[Sam] Kas sa saata täidetud SLL ja ks?
[Hardison] Jah. Ma saadan välja lõpule slaidid ja lõpetatud SLL korstnat ja queue.cs.
[CS50.TV]